# Question
Title: Is there a faster than O(n^2) solution for Box stacking problem?
The Box Stacking problem is as follows:

> You are given a set of $n$ types of rectangular 3-D boxes, where the $i^{th}$ box has height $h\_i$, width $w\_i$ and depth $d\_i$ (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

Is there a solution faster than the $O(n^2)$ solution given here?

# Answer
> 1 votes
This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question:

As in the link, for a box in the input with dimensions $(w\_i, d\_i, h\_i)$, consider all rotations of the box, but maintain the property that the first dimension is always $\ge$ the second dimension. So each input box corresponds to three boxes, and consider all these $3n$ boxes, and sort them in decreasing area of the base (ie. the product of the first two dimensions).

Let this sorted sequence be $(a\_1, b\_1, c\_1), (a\_2, b\_2, c\_2), \ldots, (a\_{3n}, b\_{3n}, c\_{3n})$.

Let $DP\[i\]$ be the maximum height that you can achieve using the first $i$ boxes in this sequence, such that the topmost box is the $i^{th}$ box. Initially $DP\[i\] = 0$ for all $i$. The recurrence is

$DP\[i\] = c\_i + \max\_{\substack{j \< i \\ a\_j \> a\_i \\ b\_j \> b\_i}} DP\[j\]$

Now, instead of spending $\mathcal{O}(n)$ time to find this optimal $j$, we will do it faster using some data structures. Think of each box $(a\_j, b\_j, c\_j)$ as a point $(a\_j, b\_j)$ in a 2D plane, which has a value $DP\[j\]$. Now what we want to find is the point in the rectangle $\[a\_i + 1, INF\] \times \[b\_i + 1, INF\]$ which has the maximum value. Note that we can ignore the constraint $j \< i$ because it will be implicitly satisfied from the dimensional constraints.

For this, construct a 2D Segment Tree aka Fenwick Tree (look at the section 'Compression of 2D Segment Tree'), using $a\_i$ as the values in the outer Segment Tree, and $b\_i$ as the values in the inner Segment Trees. You can also use most other 2D Range Query data structures for this.

You can query for the maximum value in that rectangle in $\mathcal{O}(\log^2{}n)$ time, and once you have computed $DP\[i\]$, you will have to update that value in all the $\mathcal{O}(\log{}n)$ inner Segment Trees, which would take a total of $\mathcal{O}(\log^2{}n)$ time.

Hence, the problem can be solved in $\mathcal{O}(n\log^2{}n)$ time, and $\mathcal{O}(n\log{}n)$ space.

---
Tags: algorithms, data-structures, dynamic-programming, binary-trees, binary-search
---


title: Are all computer viruses man-made?

text:
# Question
Title: Are all computer viruses man-made?
I'm curious if the origin of any successful computer virus is known to NOT have an intentional, human originator. To put it another way, do computer viruses ever "spontaneously" originate through the process of natural selection in the same way biological viruses originate; without an intentional "designer?"

I imagine (though I'm not sure) that it's possible for sufficiently knowledgable software engineer to make use of software engineering tools like neural networks, genetic algorithms, adversarial networks, etc to write a virus according to his/her specifications, but that's not what I want to know. I want to know if computer viruses ever begin on their own, and if they don't, why not?

The three core tenets of evolution by natural selection are descent with modification, variable fitness, and resource limitation. Some scientists say that wherever these conditions are in place, evolution occurs necessarily. Importantly, being alive is not a prerequisite, which is why biological viruses continue to evolve even though they are not technically alive. Richard Dawkins says that thoughts and ideas survive and proliferate through the same mechanism. So, does computer code ever evolve organically without human intervention to form a successfully self-replicating entity? If not, why not?

# Answer
> 6 votes
Interesting question. I think the biggest barrier preventing something like that from happening is that **computers are engineered to be extremely robust to random, non-human errors**. Computers will do what programmers instruct them to do, and unless the hardware is being pushed beyond its limits or subjected to extreme environments like cosmic radiation in space, they do not deviate from programmer instruction.

It is necessary for computers to have these near-zero error rates due to the sheer quantity of operations they perform. An error rate of one in a million seems pretty good...until you consider that a modern desktop computer is capable of performing about 100 billion operations per second. A one in a million error rate would result in 100,000 errors per second, rendering your computer completely unusable due to constant crashes!

The same reasoning applies to storage mediums as well. If you assume that one in a million bits stored on a 1TB drive gets corrupted every day, then that would result in 360 megabytes of corrupted data per year!

The necessary low error rates are achieved through a combination of robust engineering and manufacturing, as well as software tricks to detect and repair errors such as checksums and error-correcting codes. In situations where these measures are insufficient, such as on spacecraft computers where cosmic radiation can wreak havoc, fully redundant computers check each others' results though voting.

Therefore I'd argue that "descent with modification" doesn't really exist here. Computers operate more or less deterministically and without error by design, so it would be very difficult for an unexpected program to spontaneously emerge.

If we designed computers that were much more error-prone, then it would be more likely that such an event could happen. But such a computer is also likely to be pretty useless, so we don't build computers like that.

# Answer
> 4 votes
There hasn't been any such virus or worm created so far, that was successful enough, to make a noticeable impact. Let's take a look at the circumstances, why this is probably the case.

1. **Such a virus needs a host program.** Software doesn't start running magically by itself on a computer. And even if it would, the structure of an executable file is too complex to originate by chance without an evolutionary process. Therefore, such a virus can only develop with reasonable chance by random mutations of an existing program.
2. **Self-replicating software is rare.** We need a self-replicating host program, but most software components do not self-replicate, especially not with a high frequency. This is a core requirement for evolution though, because it relies on gradual improvements. Almost all mutations in nature are inferior to their original and will not pass the test of time. It is very rare for a mutation to perform so well, that it surpasses the original in the long run. If the mutated software does not self-replicate frequently, the mutation will not replicate as well.
3. **Programs rarely compete for resources for reproduction.** Let's assume we bypassed issue 1 and 2, meaning we have a mutation in a self-replicating program. Now both the original and the mutated version must find themselves in an environment, where they compete against each other and the mutated version has an advantage. Such scenarios can be designed - which would mean human intervention and is not in scope of this question - but will hardly happen in a real computer environment.
4. **The mutated software must be able to spread to other systems.** The chance for any mutation to happen is already very low in today's computer systems. Hardware has a high fault tolerance, checksum verification is prevalent in many protocols and self-repair mechanisms will detect and fix many errors. This means we need a huge and diverse environment to increase the chance of undetected mutations. And we will need a lot of them, because almost none of them will be successful mutations anyway. To find such an environment, our self-replicating, mutating, with other programs competing host program must be able to spread to other systems as well. Assuming that our local mutations somehow developed a way to communicate with other systems through evolution and maybe even find an exploit to spread is of course pure science fiction. This means, our host program must have been designed to spread itself over the network in the first place.
5. **The process must happen undetected by humans.** The list can be extended with several more technical requirements, but we are already able to see, that almost no potential host software in existence provides the environment for an evolutionary process to take place. But there is one more aspect to consider - human intervention! Let's assume there is such a host software, that undergoes mutations which are spread around and a selection process takes place that benefits fitter copies of the software. Still, most of the mutations will perform worse and not only that - the majority will not work at all. Now we are talking about a software that's running on many machines, so it is probably kind of important to many people. If mutations happen often enough for evolution to occur, there will be a significant amount of copies crashing. People will very likely investigate and identify the flaw, that's allowing the mutations. And since that's a bug and not a feature, it will probably be fixed, which ends our fantasy of random artificial evolution.

# Answer
> 3 votes
This cannot happen for the same reasons a wristwatch can't turn into a microwave given enough time.

Code is deterministic. Undesired states in code follow lines of entropy, not increased complexity.

The best you are going to get is "buggy code" not new functions from the code.

Can ***running*** code degrade to have undesired effects? Sure. But that's not a virus.

# Answer
> 0 votes
In specialized environment like Core Wars, you have the conditions for evolutionary viruses. The classical core wars is for only two competing programs. But that is or can be expanded. The language is simple enough that random generators can create useful code, reproduction is important for both competitors and done all the time.

Another environment would be the Game of Life. Start with a random field and you will find self-reproducing structures.

---
Tags: theory, artificial-intelligence
---


# Question
Title: Probability that two elements are compared in randomized quicksort
I am having an issue in a specific part of the randomized quick-sort analysis.

As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random index, instead of just choosing a specific index each time.

Now suppose that we give an array of size say $n$ to our randomized quicksort algorithm.

Now I request to have a look at the proof of lemma-7.1 in the text given below. Now we have given an array to our algorithm which can be of any permutation of the elements, but in the *paragraph just after the proof of* $lemma-7.1$.

*why is the author considering a sorted instance of our input array while doing the analysis?*

Moreover if look at the text after equation $(7.2)$ where there have justified their logic of finding the probability that $z\_i$ shall be compared with $z\_j$ in our algorithm. Now in that they are considering the subset {$z\_i$,...,$z\_j$}. Isn't this case of comparison of $z\_i$,$z\_j$ getting too specific if we consider that specific subset only? I mean to say we are using randomized approach and the probability of comparison might be derived using a more broader look, such as a permutation of all possible cases or so.

That we are using a specific subset and that too sorted is not convincing as to how are we getting the correct probability for our algorithm...

```
     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

```

And the probability of $1/(j-i+1)$ -\> total no. of elements in the subset is also fixed for specific $i$ and $j$

In considering the probability of comparison of $z\_i$,$z\_j$, the subset in which the two elements are there and which is to be partitioned can be anything(i.e composed of any possible element) and of any size (not just $j-i+1$)...

May be the randomization condition is actually taking everything in account but I am not getting it. Please can you explain me the logic they are using to find the said probability and also please convince me that we are correctly finding the probability of comparison.

*For reference i am attaching the corresponding pages of INTRODUCTION TO ALGORITHMS 3RD ED-- CLRS*

# Answer
> 2 votes
A very simple proof: I claim that if there are d integers with values between x and y, and there are n ≥ 2 elements in the array, then the probability that x and y are compared is 2 / (d + 2), independent of n.

Proof by induction: If n = 2 then clearly d = 0, so the claim is that x and y are compared with probability 2 / (0 + 2) = 1. This is also clearly correct, since x and y must be compared.

Now let n ≥ 3. For the first partitioning, we choose a pivot at random. Every array element is compared against the pivot, and no other comparisons are made. So if by coincidence we choose x or y as the pivot, x and y will be compared. The probability for that is 2 / n. If by coincidence we choose one of the d elements with values between x and y, then the partitioning will move x to one partition and y to the other, so they are never compared. If we choose one of the other n - d - 2 elements, then x and y end up in the same partition, and by induction they will be compared with probability 2 / (d + 2).

So the probability that x and y are compared is

```
2 / n + (n - d - 2) / n * 2 / (d + 2) =

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) =

2 / (d + 2) qed.

```

That's of course the same result as Yuval's, since |j - i| = d + 1. The randomising makes the analysis quite easy - if we said for example "if n \> 5 then we pick 5 elements at random and pick the median of those 5 as the pivot", the analysis would be much more complex.

PS. The proof in the paper is much easier: As you partition the array, $x\_i$ and $x\_j$ remain in the same sub-partition until a pivot with i \<= pivot \<= j is used. If that pivot is i or j then $x\_i$ and $x\_j$ are compared, otherwise they are not compared. So the chance is 2 / (abs (j-i) + 1).

# Answer
> 2 votes
The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is the $i$th smallest element in the array and that $y$ is the $j$th smallest element in the array, then the probability that $x,y$ are compared is $\frac{2}{|j-i|+1}$.

This is not a special case – every element $x$ in the array is the $i$th smallest element, for some value of $i$. This is just the pertinent information that allows us to calculate the probability that $x$ and $y$ are compared.

---
Tags: algorithms, time-complexity, probability-theory, randomized-algorithms, quicksort
---


# Question
Title: Why are primitive types stored in a stack in systems level software?
Firstly 2 disclaimers, I am very new to the concept of a stack at a low level. I've only encountered it because I'm learning rust and the docs mention it. Secondly, I am aware of another similar question on this site, but it doesn't address a very specific concern.

My understanding of a stack is that it follows First In Last Off and cannot be searched, this confuses me if I do this.

```
variable a = 22;
variable b = 33;
variable c = 44;

```

Then my understanding is that c will be on top of the stack. So if I want to do something with a and b, will the system have to pop c and dig deeper for a and b? This seems inefficient. And an indexed array seems better.

# Answer
You've probably encountered the simplest definition of a stack, which is a data structure with two operations `push` and `pop`, and some basic properties:

* If you call `push` on a value and then `pop`, the value you get from the `pop` is the value passed to `push`, and the stack is returned to its original state.
* `pop` is invalid on a stack where there has never been a `push` (empty stack).
* These properties also apply if the stack is modified in the middle, as long as these modifications return the stack to its state before the modifications.

There are many equivalent formulations of these axioms. The point here is that with this definition, `push` and `pop` are the *only* things you're allowed to do on a stack.

With the metaphor of a stack as being like a stack of plates, you can't “peek” at a value that isn't at the top of the stack (the most recently pushed value). (Note that I'm describing a stack that grows upwards. Unfortunately there's no standard for that: some stacks are described as growing down. But even with downward-growing stacks, the word “top” usually means the most recently pushed value.) But when a stack is a data structure, it's often possible to access values anywhere in the stack.

The same word “stack” can mean any variant of the basic data structure, supporting other operations apart from `push` and `pop`. There's no completely universal limit for what can be called “stack”, but generally, if a data structure is called a “stack”, it means that it's a collection of values where the only way to add an item is `push` and the only way to remove an item is `pop`. Other operations may be supported, such as:

* Reading the stack size.
* Peeking, i.e. reading any of the values on the stack (not just the top one).
* Modifying a value on the stack.

---

Let's look at programming languages now. Almost every programming language has a concept of function (or procedure, subroutine, method, etc. — the distinction is not relevant here). Function calls have certain properties:

* If the code in function `f` calls a function `g` and then `g` returns, you're back to `f`, in the same context as before (“context” here means the values of local variables).
* You can't return from the top level of the program that's not inside a function. (Depending on the programming language, this may not even be a thing: the program may start directly by calling a certain function, so that there's no way to have code outside of any function. Or a ”return“ statement outside of any function may exit the program instead.)
* These properties also apply if there are additional sequences of function calls involved that return back to the original function.

Looks familiar? Yep, the function calls form a stack. (Many programming languages have ways to break the stack structure, such as exceptions which can pop many values from the function call stack in a single statement, or even more complex things that I won't go into.)

The way the function call stack is implemented on a processor is usually through a stack of return addresses. Each function call does a `push` of the current value of the instruction pointer before jumping to the code of the called function, and returning from a function is a `pop` in that stack and a jump to the popped address.

Each time a function is called, its local variables come into existence. So the variables, in turn, form a stack. Calling a function pushes a new entry on the variable stack for this function's variables, and returning from a function pops an entry from the variable stack. (You can model this either with a single entry for all of a function's variables and a single push/pop per call/return, or with one entry per variable and as many push/pop per call/return as the function has variables.)

Note that variables are associated with a *function call*, not just with a function. When a function is called recursively, or more generally as part of a chain of calls of mutually recursive functions, each function call has its own variables, even if they happen to be calls to the same function. Conversely, local variables of a function don't “exist” while the function isn't being called. (Some of the very first programming languages had one storage area per routine, which existed all the time. These languages did not permit recursive calls. No modern programming language works that way, but some hardware description languages do.)

In a language with dynamic scoping, if a function `f` calls a function `g`, the code of `g` can access the variables of `f` by name. This is an example of a stack with extra operations: the code of `g` can read and modify the variables of `f`. The code of `g` can't create new variables of `f` or destroy variables of `f`, so this is still a stack. In a language with \[lexical scoping\]9https://en.wikipedia.org/wiki/Scope\_(computer\_science)#Lexical\_scoping), the code of `g` can't access the variables of `f` by name, but it may nonetheless be able to access and modify their value if it can see a pointer or reference to a variable of `f`.

---

So far I've described how almost every programming language works. The specifics of what “the variables of a function call” means depends on the programming language. There's the association between the variable name and its value, and there's the value itself. Most programming languages have three classes of storage: global (exists for the whole lifetime of the program), stack (lasts as long as a function call), and heap (can be created and destroyed arbitrarily). But how apparent this is depends heavily on the language. In most higher-level languages, these classes of storage are a detail of how the compiler or runtime environment works, because storage allocation and destruction is automatic. Variables have a scope (the parts of the program where a certain name refers to that variable). Storage usually doesn't have an explicit scope in higher-level languages, but it does in lower-level languages.

In Rust, the scope of storage is explicit. A variable's storage lives as long as the variable lives, i.e. until the function returns. It lives longer if the value is returned from the function. Heap storage requires explicitly *boxed* values.

---

Now that I've described what a stack is as an abstract data structure, and how it arises when describing the theory of programming languages, I'm finally read to discuss how it works in the implementation of a programming language. Here, I'm going to describe how most implementations of most programming languages work when compiled to native code. (Languages compiled to byte code are typically fairly similar, but may be a bit further from this simplified description.) It's possible to do things differently, but unusual. I'm also going to keep things simple and not go into details that aren't important to understand the basic concept, such as registers, function parameters, return values, block scope, etc.

The typical way to implement a function call stack is to store the return addresses and the local (unboxed) storage for its variables in a single memory area. This specific method of implementing the stack abstract data structure is also called a “stack”. The stack of memory management for function calls works this way:

* There's an array of memory which is reserved for the stack.
* Pushing means copying a value to the top of the stack and incrementing the *stack pointer*, which is an index into the array of memory.
* Popping means reading the value at the top of the stack, then decrementing the stack pointer.
* To call a function, push the current value of the instruction pointer, then push enough storage for the function's local variables. The set of things pushed at this stage constitute a *stack frame*.
* To return from a function, pop the stack frame and jump to the return address.

As long as a function call is in progress, its variables are in its stack frame. To access them, you need to know their address. To access a variable of the current function, all you need to know is its position in the stack frame. And the address of the stack frame of the current function is the top of the stack minus the frame size. So for example, let's imagine a simple (unoptimized) compiler for a simple programming language and the following program fragment in a function:

```
variable a = 22;
variable b = 33;
variable c = 2 * a;

```

This is compiled as: * Allocate a frame with room for three variables. * Write 22 to the address `sp - 3` where `sp` is the stack pointer. (For simplicity, in this example, I assume that all variables have the size 1. Having differently-sized variables just requires keeping track of their sizes and doing additions at compile time.) * Write 33 to the address `sp - 2`. * Read a value from the address `sp - 3`, multiply the value by 2, and write the result to the address `sp - 1`.

As you can see, accessing a variable doesn't require popping to it. This is because computer memory itself is not a stack, but random-access memory. The stack that contains the local variables is a stack only because it grows and shrinks according to a stack pattern, not because it's impossible to access elements that are not at the top.

Accessing a variable of a function which isn't the current one doesn't require popping to it either. It does require knowing the address of that variable. If a variable has access to another function's variable, this can be either because the variable was passed as a parameter, or because the current function has access to a *reference* (pointer) to that variable. In either case, what happens under the hood is that the address of the variable is stored somewhere where the called function can access it.
> 2 votes

# Answer
What you looked at was the simplest form of a stack, where you can put one item on the top of the stack, remove one item from the top of the stack, and access the item on the top of the stack.

You can instead use a *slightly* more complex version of the stack, where you can add k items on the top of the stack, remove those same k items, and access the k items on the top of the stack.

In your example, you needed space for three variables, so you add space for three variables on the stack when the function is entered, you remove space for three variables when the function is removed, and can access all three variables on the top of the stack. Each function has a different number of variables it needs to make space for on the stack. And in most languages, there is indeed no way to access variables higher up in the stack (nested functions in Pascal are a rare exception).
> 1 votes

---
Tags: memory-management, memory-access, stacks
---


title: Hoare Logic for Factorial

text:
# Question
Title: Hoare Logic for Factorial
I came across this hoare logic for factorials but I don't quite understand it. We multiply F and X but we're not adding up all values of F so how do we get the sum/factorial at the end?

**Precondition:** $\\{ X \> 0 \land X = x \\}$

1. $F := 1$
2. **while** $X \> 0$ **do**
3. $\quad F := F \cdot X$
4. $\quad X := X - 1$
5. **od**

**Postcondition:** $\\{F = x!\\}$

# Answer
> 0 votes
What the Hoare invariant state is the following:

> If you run the code with $X$ equal to some value $x \> 0$, then at the end, $F$ will have the value $x!$ ($x$ factorial).

You can check that this is indeed the case.

---
Tags: logic, discrete-mathematics, hoare-logic, loop-invariants
---


# Question
Title: For $T(n) = 16T(n/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$
Define: $ \lg x = \log\_2x $.

Let $ f(n), g(n) $ be some non-negative functions.

Define $ f(n) = \Theta (g(n)) $ if $$ \exists c\_1,c\_2 \in R\colon 0 \< c\_1g(n) \leq f(n) \leq c\_2g(n) $$

I want to prove that the function defined by the recurrence relation $ T(n) = 16(T/4) + n^2\lg^3n $ has the asymptotics $ T(n) = \Theta(n^2\lg^3n) $

I wanted to prove that by substitution method:

$$ T(n/4) \leq n^2\lg^3n $$

Now,

$$ T(n) \leq 16(n^2\lg^3n) + n^2\lg^3n = 17n^2\lg^3n $$

But in order for the proof to work, I should have gotten

$$ T(n) \leq n^2\lg^3n $$

I also need to show that this is a lower bound, but I want to start by showing that it's an upper bound.

What is the right way to prove these things?

# Answer
What you want to prove is false.

$T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$.

To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$.

Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log\_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem to conclude that $T(n) = \Theta(n^{ \log\_b a } \cdot \log^{k+1} n)$.
> 1 votes

---
Tags: algorithms, asymptotics, efficiency
---


# Question
Title: What is µ A below ~ x in the Fuzzy Logic
I am reading the book "Fuzzy Logic with Engineering" written by Timothy J. Ross and there is a phrase in the book at page 90, he mentions about the "Features of the Membership Function". He says:

> The support of a membership function for some fuzzy set A under ~ is defined as that region of the universe that is characterized by nonzero membership in the set A under ~. That is, the support comprises those elements x of the universe such that μ A under ~ (x)\>0.

He denotes it as a graphical representation:

what is μ A under ~ (x) in this context? Thanks in advance.

Edit Post The μ A under ~ (x) in this context is membership function. https://www.tutorialspoint.com/fuzzy\_logic/fuzzy\_logic\_membership\_function.htm

# Answer
> 0 votes
Here μ A˜(∙) μA~(∙) membership function of A˜ this assumes values in the range from 0 to 1, i.e., μ A ˜ (∙)∈\[0,1\] μA~(∙)∈\[0,1\] . The membership function μ A ˜ (∙) μA~(∙) maps U to the membership space M . The dot (∙) in the membership function described above, represents the element in a fuzzy set; whether it is discrete or continuous.

In classical set theory, it is either 1 or 0.

source:

https://www.tutorialspoint.com/fuzzy\_logic/fuzzy\_logic\_membership\_function.htm

---
Tags: fuzzy-logic
---


title: Large DFA to regex?

text:
# Question
Title: Large DFA to regex?
For an assignment for one of my courses, one of the questions is to provide a regular expression for the language:

"*the set of strings such that the number of 0’s is divisible by six, and the number of 1’s is divisible by five.*" over the alphabet {0, 1}.

I made a DFA for this language and it has 30 states. However, going to turn this DFA to a regular expression through state reduction is proving to be very time consuming.

What could be the better or easier way to do create a regular expression that describes that language?

# Answer
> 2 votes
The regular expression for this DFA is indeed going to be very large. I don't believe that it is feasible to generate it by hand, and unless the assignment requests a machine-readable version, it is going to be pretty difficult to validate.

There is a good discussion on how to algorithmically convert a DFA to a regular expression in this reference post, and I used one of the algorithms presented there to do a quick-and-dirty Python program. Using two different state elimination orders, it found regular expressions of 13,420,632 and 14,680,071 characters.

It's worth noting that the regular expressions generated automatically can usually be simplified considerably, and furthermore that the order in which you eliminate states does have an impact on the size of the regular expression produced. So it's certain there is a much shorter regular expression which would work, but I suspect that the shorter regular expressions are still pretty long.

All of this makes me wonder whether the original assignment asked for a regular *grammar* rather than a regular expression. The regular grammar precisely follows the DFA state transitions, so it is of manageable size: 30 non-terminals (each corresponding to a state) with a total of 60 productions (each corresponding to a transition). Writing that out by hand would be tedious but it could be generated with a much simpler program than the one needed to produce regular expressions.

# Answer
> 1 votes
This is near cheating, but to convert such a monster DFA to a RE by hand is cruel and unusual punishment...

Check out software, like the acclaimed JFLAP, for this. If you *do* use it, be sure to credit it properly.

# Answer
> 0 votes
Copying my approach for a similar language, only the numbers are (fortunately!) smaller. Here, the number of 0's is divisible by 2 and the number of 1's is divisible by 3. Maybe it scales for your case. The hard part is the first step, where you need to figure out all combinations of 11-sized strings with six 0's and five 1's, but you can track all possibilities with the help of a tree!

So, here it is:

**Step 1:** Words accepted by this language should be built up from combinations of the basic strings 00, 111, 10101, 01101, 01011, 10110 and 11010. The first two regard words where 0's and 1's are grouped together, while the rest regard words such that 0's and 1's are intertwined. However, the regular expression $$(00\mid 111\mid 10101\mid 01101\mid 01011\mid 10110 \mid 11010)^\*$$ produces only part of the language. For example, it does not produce 01110.

**Step 2:** To produce such words, in the first basic string, we should allow groups of 1's to appear between the two 0's, and in the second we should allow groups of 0's between the 1's. Now we have $$(0(111)^\*0\mid 1 (00)^\* 1 (00)^\* 1\mid 10101\mid 01101\mid 01011\mid 10110 \mid 11010)^\*$$ This regular expression still does not completely determine the language. For example, it does not allow the word $10\color{teal}{00}101$.

**Step 3:** To overcome this, in the last five choices of the regular expression, for every sequence of 1's that does not start at the beginning of the string, if the sequence is followed by a 0, then we add $(111)^\*$ in between. Similarly, for every sequence of 0's that does not start at the beginning of the string, if the sequence is followed by a 1, then we add $(00)^\*$ in between. The reason why sequences that start at the beginning of the string are not considered is because of the outer kleene star and the first two choices. The final regular expression is: $$\left(\\!\begin{aligned} & 0(111)^\*0 \mid 1 (00)^\* 1 (00)^\* 1\mid \\ & 10 (00)^\* 1(111)^\*0 (00)^\* 1 \mid 011(111)^\*0(00)^\*1\mid \\ & 01(111)^\*0(00)^\*11 \mid 10(00)^\*11(111)^\*0 \mid 110(00)^\*1(111)^\*0 \end{aligned}\right)^\*$$ This is already a great mess for multiples of only 2 and 3, the first two primes.

---
Tags: formal-languages, automata, regular-languages, finite-automata, regular-expressions
---


title: When does this algorithm fail?

text:
# Question
Title: When does this algorithm fail?
***The problem***

Given $n$ stacks of $k$ integers each. What is the maximum sum that can be achieved by removing exactly $p$ integers?

The following example illustrates the problem.

$n$ = 3, $k$ = 4, $p$ = 3

*stack 1*: 2, 5, 12, 5

*stack 2*: 10, 3, 12, 50

*stack 3*: 7, 4, 20, 20

Note that the top of a stack is the leftmost element.

Here, the optimal solution is to pick all the first three numbers from stack 3, which gives a sum of 31.

***The algorithm***

I came up with the following algorithm.

The idea is to calculate the best possible sum for each stack if all $p$ elements were chosen from that particular stack. This sum only considers the integers that can possibly be taken.

Then, greedily take the top element from the stack with the best possible sum. And update the sum for all stacks because now only $p-1$ integers need to be popped.

***The question***

is this algorithm always going to produce a correct answer? If not, when would this fail?

***Disclaimer***

I am aware that a dynamic programming solution can solve the problem in $O(npk)$ time.

This is based on the following problem from a previous contest on google coding competitions platform. (https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb)

# Answer
Here is a counterexample, with $p = 2$:

* stack 1: $600,600$.
* stack 2: $1000,0$.
* stack 3: $1000,0$.

Your algorithm will choose the top element from stack 1 and one of the top elements from the other stacks, but it is better to choose the top elements of stack 2 and stack 3.

Disclaimer: This is based on your description of the algorithm. I don't understand some of the notation in the algorithm itself.
> 2 votes

---
Tags: correctness-proof, greedy-algorithms
---


# Question
Title: Algorithms that run in polynomial time if P=NP
On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking them up and couldn't find any.

# Answer
Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for *any* problem in NP, not just SUBSET-SUM.
> 7 votes

---
Tags: algorithms, time-complexity, decision-problem, polynomial-time, p-vs-np
---


# Question
Title: Maximize rental income given a set of date intervals
Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out.

For example: Given intervals: `[[1, 10], [2, 5], [7, 20], [23, 30]]` \- you could rent it out `[2, 5], [7, 20] and [23, 30]`

Another example: `([[1, 2], [1, 11], [5, 8], [4, 33], [18, 72]])` = `66`

Note: Start and end times of the interval are inclusive

I implemented a brute force solution to this problem. First I sort by start time, then I create all possible subsets and take the longest possible value. This works. But I want to do this using Dynamic programming.

This problem screams DP, but I am not able to figure out if this has an optimal substructure.

My recurrence relation: `f(i, j) = f(i + 1, j) or f(i + nums[i], j) if nums[i].start > f[i].end`

Can someone help me figure out the thought behind the dp solution for the sub-problem?

Note: this problem is slightly different from job scheduling.

# Answer
The most common subproblems where a particular subsequence should be selected are parametrized by the index of the last element selected. The classical, simple and brilliant example is Kadane's algorithm.

Let the given intervals are $I\_1, I\_2,\cdots, I\_n$, where $I\_j=\[l\_j, r\_j\]$.

The subproblem $DP\[i\]$, where $1\le i\le n$ is the maximum rent if **the last interval rented** is the $i$-th interval. The answer is $\max\_iDP\[i\]$.

We could add an artificial base case, $DP\[0\]=0$, which says that the maximum rent is 0 if there is no interval rented.

The recurrence relation is $$DP\[i\] = \text{Length}(I\_i) + \max\_{r\_j\lt l\_i} DP\[j\].$$

That is it, basically. There is a minor problem with the above recurrence relation, however. When we compute $DP\[i\]$, not all of $DP\[j\]$ with $r\_j\lt l\_i$ has been computed. I will leave it for you to resolve this minor obstacle.
> 0 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Algorithm to find the size of a quotient of a free group
Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like {a,b: a^8=b^2=1, ab=ba^3} (a quasidihedral group), and the output would be the integer 16, since there are 16 different ways to write a string formed of a's and b's if you treat aaaaaaaa and bb as the empty string, and the string ab as the same as the string baaa.

Ideally the algorithm would also be able to say if a group was infinite. It's not obvious by looking at the presentation what the size of the group is, and I think it's a fairly interesting question that I've comes across a few times in my algebra class, so I was surprised that I couldn't find a tool to solve it for me or any papers talking about it, it seems that computers should be good at this. Wondering if anyone has any good ideas.

# Answer
> 2 votes
I think you're asking: given a group presentation $\langle X | R \rangle$, determine the size of the group.

Unfortunately, it is undecidable to determine whether the group is finite or infinite. See the Adian-Rabin theorem.

For some additional references, see also https://math.stackexchange.com/a/606/14578, https://math.stackexchange.com/q/3106606/14578, https://math.stackexchange.com/q/2756802/14578, https://math.stackexchange.com/q/1516849/14578, or the following lecture notes: Presentation of Groups. Derek Holt.

---
Tags: algorithms, group-theory, algebra
---


# Question
Title: Trading States for Symbols with a Turing Machine
Show that for each string $w ∈ \\{0, 1\\}^∗$ there exists a stay-put Turing machine

$$M\_w = (Q, \\{0, 1\\}, \Gamma, \delta, s, q\_{\mathit{accept}}, q\_{\mathit{reject}})$$

with $|Q| ≤ 5$ states that starts on a blank tape in state $s$ and ends in state $q\_{\mathit{accept}}$ with the tape content $w$ beginning in the first cell and the head under that cell.

That is, starting on a blank tape, the machine outputs $w$ and stops in $q\_{\mathit{accept}}$.

I know that if there were infinite states then we could put each letter into its own state so that we could print the letter when needed, but I don't know how to reduce it to 5 states.

# Answer
> 1 votes
Here is one idea. Let $|w| = n$. We will have a tape symbol for each number in $\\{0,1,\ldots,n\\}$, which we will denote by $\langle i \rangle$. The machine starts by writing $\langle n \rangle$ on the tape. Then it repeatedly performs the following steps:

* Read $\langle i \rangle$.
* Depending on the value of $i$ and on $w$, switch to a write-0 or a write-1 state.
* In write-$b$ step, move right until reaching the first blank, write $b$, then move left until reaching a cell of the form $\langle j \rangle$.
* Replace $\langle j \rangle$ with $\langle j-1 \rangle$, or terminate if $j = 0$.

The exact implementation of this algorithm depends on your exact model. In your model, you might be able to do it using 5 states. But in any reasonable model, $O(1)$ states are needed, regardless of $w$.

---
Tags: turing-machines
---


# Question
Title: Can I find all the common subsequences between 2 sequences by using dynamic programming?
I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one.

Thank you.

# Answer
Denote the two strings by $s = s\_1,\ldots, s\_n$ and $t = t\_1,\ldots, t\_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s\_1,\ldots,s\_i$ and $t\_1,\ldots,t\_j$ which contain $s\_i$ and $t\_j$. Let $\mathcal{U}(\leq i,j)$ be the union of $\mathcal{U}(I,j)$ over all $i \leq I$, and define $\mathcal{U}(i,\leq j),\mathcal{U}(\leq i, \leq j)$ similarly. These multisets obey the recurrences: $$ \mathcal{U}(i,j) = \begin{cases} \emptyset & \text{if } s\_i \neq t\_j, \\ \\{ w s\_i : w \in \mathcal{U}(\leq i-1,\leq j-1) \\} & \text{if } s\_i = t\_j. \end{cases} \\ \mathcal{U}(\leq i,j) = \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j) \\ \mathcal{U}(i,\leq j) = \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(i,j) \\ \mathcal{U}(\leq i,\leq j) = \mathcal{U}(\leq i-1,\leq j-1) \cup \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j) $$ with the base cases $\mathcal{U}(0,0) = \\{\epsilon\\}$ and $\mathcal{U}(k,0) = \mathcal{U}(0,k)$ for $k \> 0$.

If you want you can even keep track of the indices from which the subsequences are taken. The recurrences above ensure that each pair of matching subsequences is counted exactly once.

If you want instead to count the number of common subsequences, all you need to do is to keep track of the size of the multisets involved. Similarly, if you want instead to determine the longest common subsequence, all you need to do is keep track of that. In the latter case, double counting of subsequences is allowed (since we are only interested in the maximum length anyhow), and this simplifies the recurrence.

Indeed, if you are interested just in the *set* of common subsequences, then you can use a simpler recurrence. Let $\mathcal{V}(i,j)$ denote the set of common subsequences of $s\_1,\ldots,s\_i$ and $t\_1,\ldots,t\_j$. The sets $\mathcal{V}(i,j)$ obey the recurrence: $$ \mathcal{V}(i,j) = \mathcal{V}(i,j-1) \cup \mathcal{V}(i-1,j) \cup \begin{cases} \emptyset & \text{if } s\_i \neq t\_j, \\ \\{ws\_i : w \in \mathcal{V}(i-1,j-1)\\} & \text{if } s\_i = t\_j, \end{cases} $$ with base cases $\mathcal{V}(i,0) = \mathcal{V}(0,j) = \\{\epsilon\\}$. This is the form of the standard recurrence for longest common subsequence.

If you're interested in multisets but prefer a simpler recurrence, you can use the geekstogeeks idea, which requires multiset subtraction to avoid double counting. Let $\mathcal{W}(i,j)$ denote the multiset of common subsequences of $s\_1,\ldots,s\_i$ and $t\_1,\ldots,t\_j$, which obeys the following recursion: $$ \mathcal{W}(i,j) = \mathcal{W}(i,j-1) \cup (\mathcal{W}(i-1,j) \setminus \mathcal{W}(i-1,j-1)) \cup \begin{cases} \emptyset & \text{if } s\_i \neq t\_j, \\ \\{ws\_i : w \in \mathcal{W}(i-1,j-1)\\} & \text{if } s\_i = t\_j, \end{cases} $$ with base cases $\mathcal{W}(i,0) = \mathcal{W}(0,j) = \\{\epsilon\\}$. Depending on the application, the operation of multiset subtraction could be unavailable, and in this case you can use the idea outlined at the beginning of the answer.
> 2 votes

---
Tags: algorithms, dynamic-programming, subsequences, bioinformatics, longest-common-substring
---


title: Converting this NFA-e to DFA

text:
# Question
Title: Converting this NFA-e to DFA
I came across this question about NFA-e and thought to convert it into DFA:

This is what I did.

$\begin{array}{|c|c|} \hline & a \\ \hline q\_1&q\_2 \\ \hline q\_2&\phi \\ \hline q\_3&\phi \\ \hline \end{array}$

Found epsilon closure of states:

$\varepsilon(q\_1) = q\_1$

$\varepsilon(q\_2) = \[q\_2, q\_3, q\_1\] = P$ (let)

$\varepsilon(q\_3) = \[q\_3, q\_1\] = Q$ (let)

Defined new transition rule for the states:

$\delta'(q\_1, a) = \varepsilon\\{\delta(q\_1, a)\\} = \varepsilon(q\_2) = P$

$\delta'(P, a) = \varepsilon\\{\delta(q\_2, a) \cup\delta(q\_3, a) \cup \delta(q\_1,a)\\}=\varepsilon\\{\phi\ \cup\ \phi\ \cup q\_2\\}=P$

$\delta'(Q,a)=\varepsilon\\{\delta(q\_3,a) \cup \delta(q\_1,a)\\}=\varepsilon\\{\phi \cup q\_2\\}=P$

$\begin{array}{|r|r|} \hline &a\\\hline q\_1&P\\\hline \*P&P\\\hline Q&P\\\hline \end{array}$

Now I'm stuck on how to make the FSM. There is no transition to $Q$ from $q\_1$ or $P$. What did I do wrong?

# Answer
Alright we've to remove the *unreachable* state that is $Q$, for which we have to follow these steps:

1. Initialize a set $R$ containing the initial state.
2. Create a set $M$ which'll contain the states which are reachable from states in $R$ in single transition.
3. Perform $R = R\cup M$.
4. Repeat from step 2 until $R$ stops getting new states.
5. Remove states from complement of $R$.

Create set $R = \\{q\_1\\}$.

Calculate $M$ by finding states which can be reached from $\\{q\_1\\} = \\{P\\}$.

Perform $R = R\cup M:\\{q\_1\\}\cup\\{P\\}=\\{q\_1, P\\}$.

Calculate $M$ again from $\\{q\_1,P\\}=\\{P\\}$.

Perform $R=R\cup M:\\{q\_1,P\\}\cup\\{P\\}=\\{q\_1,P\\}$. $R$ has no new states to add. Therefore, we'll remove states from complement of $R: \\{q\_1, P, Q\\} - \\{q\_1,P\\}=\\{Q\\}$. The FSM will be:

I learned this here http://www.cs.um.edu.mt/gordon.pace/Research/Software/Relic/Transformations/FSA/remove-unreachable.html
> 0 votes

---
Tags: automata
---


# Question
Title: Does the underlying computational calculus in type theories affect decidability?
I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers.

I understand that *modern* type theory is inspired by Curry-Howard correspondence. From the Wikipedia article on Curry-Howard correspondence:

> The correspondence has been the starting point of a large spectrum of new research after its discovery, leading in particular to a new class of formal systems designed to act both as a proof system and as a typed functional programming language. ... This field of research is usually referred to as modern type theory.

Looking at the various type theories proposed and under development, I have a few basic questions:

**1.** Most modern type theories marry a *type system* with *lambda calculus*. Are there examples where a type theory uses a *computational calculus* other than lambda calculus?

**2.** At a very high level, if every modern type theory is a *bundle of a type system and a computational calculus* and the computational calculus is turing-complete (like lambda calculus), does the computational calculus in any way *affect* the decidability of decision problems like *type checking*, *type inference*, etc.? (AFAIK modern type theories tweak the type system while keeping the associated turing-complete computational calculus intact and just tweaking the type system affects decidability of *type checking*, *type inference*, etc.)

**EDIT**

**NB**: The distinction between *Type Theory 1* and *Type Theory 2* is based on their application in *formal verification of programs* and not based on the *philosophy of type theory research*. Also, the **Program/Computation/Dynamic** blocks are bigger as I guess existing programming languages have higher *computational complexity* than the type theories used for formal verification of their programs.

W.R.T. to the illustration above:

1) In **type theory 1** methods, are type theories used both *consistent* and *complete* (w.r.t. Godel’s incompleteness theorem)? If there are type theories in proof assistants that are *incomplete*; leading to undecidable decision problems, how does the *undecidability* manifest in practical applications (like proving the correctness of a complex distributed systems protocol)?

2) In **type theory 2** methods, what are the limitations of type theories in static analysis (w.r.t. Rice’s theorem)? Here, is decidability in type theories also affected by the computational model of programming language (eg. imperative vs functional languages)?

# Answer
> 4 votes
I don't think that the term "modern" helps distinguish anything. One way to explain is to draw a distinction between "behavioral", or "semantic", type theories and "formal", or "syntactic", type theories.

Behavioral type theories start with a notion of computation (say, an operational semantics of some kind), and define types as descriptions of program behavior, ie specifications. For example, one might specify that a function takes primes to primes as a description of how it behaves. Membership in a type is a matter of *truth*, not *formal proof*, and is never remotely axiomatizable, by Gödel's Theorem.

Formal, or syntactic, type theories are given by a collection of rules, including axioms as no-premise rules. They are inherently recursively enumerable, and never come close to any notion of truth. In particular such type theories, which often enjoy a (n empty) correspondence with a logical system (the poorly named C-H Correspondence), have no inherent meaning, computational or not. They are mere formalisms.

The two concepts may be linked by stipulating a priori that programs must be "well-typed" in the formal sense, with specifications of behavior refining types (for example, isolating the primes among the naturals). There are good reasons to take this viewpoint, namely that the rules prevent you from writing the code that you didn't want to write (eg, enforcing abstraction boundaries). But they also prevent you from writing the code that you do want to write (they define up-front what are the programs). The benefit of such restrictions is something called "the fundamental theorem", which states that syntactically well-formed programs enjoy behavioral properties associated to their types, a generalization of "type safety". In particular, the parametricity theorem is an example; it expresses that abstraction is properly enforced.

# Answer
> 3 votes
You are probably looking for computational type theory and you should probably look into realizability theory as well, which explains how to interpret type theory (and higher-order logic) on top of almost any kind of computational model.

Type theories based on a computational models that are Turing complete typically does not have decidable equality. An example of such a type theory is NuPRL.

---
Tags: lambda-calculus, type-theory, type-checking, type-inference, curry-howard
---


# Question
Title: Efficient algorithm for retrieving the transitive closure of a directed acyclic graph
I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A\_v$ is a set containing all the connections of $v$. My task is to find which vertices are reachable from each vertex $v\in V$. The solution I use has a complexity of $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me another way (with better complexity) to solve the transitive closure problem in a DAG?

# Answer
> 12 votes
The fact that our graph is acyclic makes this problem much simpler.

Topological sort can give us an ordering of the vertices $v\_1,v\_2,\dots,v\_n$ such that, if $i \< j$, then there is no edge from $v\_j$ back to $v\_i$. We've listed the vertices such that all edges in go "forward" in our list.

(edited to fix analysis and give slightly faster algorithm)

Now we just go backwards through this list, starting at the last vertex $v\_n$. $v\_n$'s transitive closure is just itself. Also add $v\_n$ to the transitive closure of every vertex with an edge to $v\_n$.

For each other vertex $v\_i$, going from the end backwards, first add $v\_i$ to its own transitive closure, then add everything in the transitive closure of $v\_i$ to the transitive closure of all the vertices with an edge to $v\_i$.

The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure.

Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c\_j$ |= $c\_i$. (Binary OR operation.)

For $n \> 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.

Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.

# Answer
> 1 votes
Purdom's algorithm computes the transitive closure of a DAG in $\mathcal{O}\left(\vert E \vert + \mu \vert V\vert \right)$ , where $\mu \le \vert V \vert $ is the number of strongly connected components of the graph. Since $\vert E\vert = \mathcal{O}\left(\vert V \vert^2\right)$, Purdom's runtime is $\mathcal{O}\left(\vert V \vert^2\right)$, i.e. faster than your stated $\mathcal{O}\left(\vert V \vert^3\right)$ algorithm.

---
Tags: algorithms, graphs
---


# Question
Title: center selection problem: Simple greedy algorithm
I am trying to understand the following text which defines a greedy algorithm for center selection problem:

> It would put the first center at the best possible location for a ***single center***, then keep adding centers so as to reduce the covering radius, each time, by as much as possible. It turns out that this approach is a bit too simplistic to be effective: there are cases where it can lead to very bad solutions.
>
> Kleinberg, Jon. Algorithm Design (p. 607). Pearson Education. Kindle Edition.

Is the term "single center" typo for "single site"?

Some body please guide me how by adding centers we can reduce the covering radius?

Zulfi.

# Answer
Given a set of points, the task is to find a set of centers minimizing the *covering radius*, defined below. The centers themselves could be arbitrary points in space, or sometimes must be selected among the points or among a set of potential centers.

The covering radius is the minimum $r$ such that each point in the set is at distance at most $r$ from a center. Clearly, adding centers can only reduce the radius, and in general it does. As a very extreme examples, given $n$ distinct points, for any $n-1$ centers that we choose, the covering radius will be positive, while if we take all the points as centers, the covering radius drops to zero.

As another example, consider three points on the real line at locations $-1,0,1$. The best choice for a single center is $0$, with covering radius $1$. The best choice for two centers is $-1/2,1/2$, with covering radius $1/2$. However, if we first put a center at $0$, no choice for the second center will reduce the covering radius.
> 3 votes

---
Tags: graphs, greedy-algorithms
---


# Question
Title: Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?
I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\Theta(\log(g(n)))$. Is it true?

# Answer
An obvious counter example is $g(n) = \sqrt{n}$. If $f(n) = \Theta(\sqrt{\log n})$, you can't conclude that $f(n) = \Theta(\log{\sqrt{n}}) = \Theta(\log{n})$.
> 2 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?
Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC.

I'm writing an optimized version of Bellman-Ford's Shortest Path Algorithm on a directed, weighted graph. When I give it a regular graph with no NWC's, it works fine, and finds the answer correctly. But when I give it a NWC, it loops forever. So, I put a system into the implementation where it finds out if there is a NWC, which it does correctly, but now I'm stuck on what to do once I find it.

My first thought was to just go on regularly while setting every vertex in the cycle to negative infinity, but every single vertex after that becomes negative infinity too, and soon enough, a huge chunk of the graph becomes negative infinity and I'm getting bugs left and right because I'm subtracting to negative infinity, adding to negative infinity, while also setting the distance to negative infinity. I technically could fix all the bugs, but then lot's of valuable information on the other vertices is lost because of one little NWC.

My next thought was to just terminate the program, but then again lot's of information is lost on the other vertices.

So, what is the correct action to be taken when you find a NWC?

# Answer
> 4 votes
You say that your implementation of Bellman-Ford loops forever. This leads me to believe that you are only stopping when no computed distance changes in one iteration.

You can always stop at the $(n-1)$-th iteration since, in the $i$-th iteration, all finite distances towards the vertices at hop-distance at most $i+1$ from the source must have correctly been computed.

Then, you can perform a single additional iteration. If a distance to a vertex $v$ changes during this iteration, then $v$ must be part of negative weight cycle (and you will find at least one such vertex $v$ per cycle). If $V$ is the set of these vertices $v$, you can mark all vertices reachable by those in $V$ has having "negative infinity" distance (you can do this in linear time w.r.t. the size of the graph by performing any graph visit).

---
Tags: graphs, shortest-path
---


# Question
Title: How to find a minimum cut of a network flow?
I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph.

Could someone explain how to find the minimum cut of this graph? I THINK the minimum capacity is 4.

# Answer
> 12 votes
The minimum cut is a partition of the nodes into two groups.

Once you find the max flow, the minimum cut can be found by creating the **residual graph**, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.

# Answer
> 0 votes
For this specific graph, yes, the minimum cut does have capacity $4$: if you only delete one edge, there's still a path from $s$ to $t$, so you need to delete at least two edges. Deleting the edges $sB$ and $At$ disconnects $s$ from $t$ and those edges have total capacity $4$; any other pair of edges has higher capacity, so $4$ is the minimum.

# Answer
> 0 votes
minimum cut gives the maximum capacity, not the minimum capacity in above network, on deleting `sB` and `At`, you get the max-flow as 4 the min-flow can be 0 in any network without circulation, for which you dont need to determine the min-cut.

To find min-cut, you remove edges with minimum weight such that there is no flow possible from `s` to `t`. The sum of weights of these removed edges would give you the max-flow

# Answer
> 0 votes
The cut you are after is from sB through BA through At.

The sB arrow comes from the left to the right. This direction determines the rest of the calculations. Count it as 2.

But the BA arrow comes from the right to the left. This is discarded, and counted as zero.

The At arrow comes from left to the right. It is counted as 2.

Thus the total, and the maximum flow, is 4. As you state, correctly.

I am still searching for an example where the minimum cut is not equal to (i.e. it is inevitably greater than) the maximum flow. The problem is that for complex examples, finding the minimum cut is not trivial. Theory says that there is always a minimum cut, and it is always equal to the maximum flow.

---
Tags: graphs, network-flow
---


# Question
Title: Shuffling a collection too large for memory
I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index. I'm curious if there's a standard way to shuffle this set, a pseudo-shuffle is acceptable and expected.

I imagine a function that is initialized with some parameters, including the size of the set to be shuffled, and that I can call repeatedly, getting unique and pseudo-random indexes each time that I can use to generate the corresponding value in my set. I also imagine that this function is periodic and repeats after I've gone through all values once (so there's some mod relation).

This function need not be cryptographically secure but rather be easy to construct and hold in memory so that the next "random" value of the set may be generated.

---

Here's a concrete formulation of the problem. I want to iteratively generate "random" colors in the RGB spectrum without repeats. I don't want to create an array of 256^3 elements and shuffle them. I want a function that on each call provides an index in the range that I have not yet received, until I've exhausted the range.

How might you construct a function that satisfies the above?

# Answer
> 1 votes
Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value. Use format-preserving encryption to construct a random permutation $\sigma:\\{1,\dots,n\\} \to \\{1,\dots,n\\}$. Define $g(i) = f(\sigma(i))$. Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently.

---

To address your concrete problem, you'd pick a random permutation on $\\{0,1\\}^{24}$, i.e., $\sigma : \\{0,1\\}^{24} \to \\{0,1\\}^{24}$. This can be done using format-preserving encryption: format-preserving encryption will give you a block cipher $E:K \times \\{0,1\\}^{24} \to \\{0,1\\}^{24}$ such that if you pick a key $k \in K$ random, $E\_k$ will be (indistinguishable from) a random permutation on $\\{0,1\\}^{24}$. Moreover, $E\_k$ can be efficiently evaluated. Then, if you want $m$ random RGB colors, you'd pick a random key $k$ and output the $m$ colors $E\_k(0), E\_k(1), \dots, E\_k(m-1)$.

A reasonable way to build a 24-bit block cipher is to use a Feistel cipher on 24 bits: say, 4 rounds, where in the $i$th round you map the input $L||R$ to the output $R||(L \oplus f\_k(R,i))$, where $L,R$ are each 12 bits long and $f\_k$ is a PRF, say $f\_k = AES\_k(R||i)$, and $||$ denotes concatenation of bits. You can adjust the number of rounds (fewer rounds is faster; more rounds gives higher amount of pseudorandomness; you probably want at least 3 rounds), and you can adjust the choice of $f$ (for instance, instead of a cryptographic-based construction, you could use any fast, non-cryptographic hash function). This is the construction proposed in https://en.wikipedia.org/wiki/Format-preserving\_encryption#FPE\_from\_a\_Feistel\_network. I suggest referring to the Wikipedia link I shared above for an overview of standard constructions for format-preserving encryption.

---
Tags: algorithms, data-structures, randomness
---


# Question
Title: Unambiguous grammars with different right and left hand derivations
I read recently that for an unambiguous grammar the left hand derivation need not necessarily be equal to the right hand derivation. Can someone give an example of this?

# Answer
> 3 votes
Consider the following simple grammar: $$ S\to AB \\ A\to a \\ B\to b $$ Here is a leftmost derivation of $ab$: $$ S\to AB \to aB \to ab $$ Here is a rightmost derivation of $ab$: $$ S \to AB \to Ab \to ab $$ You can see that they look different. However, they correspond to the same parse tree:

More generally, each leftmost derivation corresponds to a parse tree, and this correspondence is a bijection; and the same holds for rightmost derivations. Therefore each leftmost derivation has a corresponding rightmost derivation, sharing the same parse tree.

---
Tags: formal-languages, context-free
---


title: "Unrolling" a recurrence relation

text:
# Question
Title: "Unrolling" a recurrence relation
```
int function(int n)
{
   int i;

   if (n <= 0) {
       return 0;
   } else {
       i = random(n - 1);
       return function(i) + function(n - 1 - i);
   }
}

```

**Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range \[0,n\]. If the average processing time is T(n), what is the value of T(6)T(6)?**

(Assume that all instructions other than the random cost a negligible amount of time.)

---

This question was on Brilliant and I was following along their solution

```
              T(n)=T(i)+T(n−1−i)+1
              T(n)=T(0)+T(n−1)+1
              T(n)=T(1)+T(n−2)+1
                    ....
              T(n)=T(n−2)+T(1)+1
              T(n)=T(n−1)+T(0)+1

       nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)
       (n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2)

```

Subtract 1 from 2

```
            nT(n)−(n−1)T(n−1)=2T(n−1)+1

```

$\frac{T(n)}{n+1}$ = $\frac{T(n-1)}{n}$ \+ $\frac{1}{n(n+1)}$. They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$\frac{T(n)}{n+1}$ = $\frac{1}{(1)(2)}$ \+ $\frac{1}{(2)(3)}$ \+ ... + $\frac{1}{n(n+1)}$ = $\frac{n}{n+1}$. I do not understand how they got to this equation from the previous.

# Answer
Let $S(n) = T(n)/(n+1)$. Notice that $S(0) = 0$ and $S(n) = S(n-1) + 1/n(n-1)$. Thus $$ S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + S(n-2) = \cdots $$ Continuing in this way, for any $i \geq 0$ we get $$ S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(i+1)(i+2)} + S(i). $$ In particular, for $i = 0$ we get $$ S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(1)(2)}. $$

---

Alternatively, you can prove by induction that $S(n) = n/(n+1)$. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$: $$ S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{n-1}{n} = \frac{1+(n-1)(n+1)}{n(n+1)} = \frac{n^2}{n(n+1)} = \frac{n}{n+1}. $$

---

Alternatively, we can prove directly that $T(n) = n$ by induction. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$: $$ T(n) = \frac{n+1}{n} T(n-1) + \frac{n+1}{n(n+1)} = \frac{n+1}{n} \cdot (n-1) + \frac{1}{n} = \frac{(n+1)(n-1)+1}{n} = \frac{n^2}{n} = n. $$
> 1 votes

---
Tags: recurrence-relation, big-o-notation
---


# Question
Title: The existence of a cycle in a directed graph is a NL-complete?
Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem.

I have already successfully demonstrated that this problem $\in NL$. But I'm stuck on how to take it apart that it's $NL-hard$.

To show that the problem is $NL-hard$, we can start from problem $s; t-connectivity$ ($s$ = source and $t$ = target ) and as an intermediate step, create a acyclic graph $G^a$ which is $s’; t’- connected$ if and only if the original graph $G$ is $s; t- connected$. Using the length of the paths of a vertex $x$ at a vertex $y$.

Thank you for your help

# Answer
Briefly, you create $n$ copies $(v,1),\ldots,(v,n)$ of each vertex $v$, adding an edge $(a,i)\to(b,i+1)$ for every original edge $a\to b$. So far the graph is a DAG. Now you add edges $(t,i)\to(s,0)$ for all $i$. I'll let you figure out why that works.
> 1 votes

---
Tags: space-complexity
---


# Question
Title: Some Questions related to Linear programming
I have some question related to the Linear Programming problem:

1. If we have an objective function that needs to be maximized and let the feasible region be unbounded such that there is no finite optimum solution. My question is what is the meaning of "finite" here?
2. If we need to solve LP using the simplex method, we need to transform any constrain that is written as an inequality equation to equality equation using the addition of the slack variables, so my question is by doing this modification did we change the problem? I mean that we have added an extra variable so I think that we have created a new constraint?
3. Also to solve the LP using simplex method, we need to have a maximization problem, so if we have to minimize an objective function, in this case to transform it to a maximization problem all we need to do is to negate the coefficients? For example, we need to minimize $3x+y=2$; is this equivalent to maximizing $-3x-y=2$?

# Answer
> 9 votes
Let me answer your questions one by one:

1. The solution of the linear program $\max x$ is $\infty$. This is an example with not finite optimum solution. This is the same as just having no optimum solution.
2. When adding slack variables, the optimum value remains unchanged. As an example, you change $x \geq y$ to the equivalent $x = y+z$, where $z \geq 0$.
3. You never minimize $3x+y=2$. What you minimize is a linear function, not an equation. Minimizing $3x+y$ and maximizing $-(3x+y)$ are the same.

---
Tags: linear-programming
---


# Question
Title: Sizing a Cuckoo filter for a subset of elements
## Question

I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs:

1. There are over $n = 30 000$ first names that exists in the whole world
2. I have a Cuckoo filter storing the names of people who gave me a gift at least once
3. I am certain that the Cuckoo filter will not have to store more than **600** names
4. The names the Cuckoo filter will store are evenly distributed across the 30 000 names
5. Of course the final goal is to be able to know which names gave me a gift at least once, **I might have to query for any of the 30 000 names**.

I would like to design my filter for 600 elements; however the original paper about Cuckoo filters considers that the number of buckets $m$ is a multiple of $n$.

> Now consider a construction process that inserts $n$ random items to an empty table of $m=cn$ buckets for a constant $c$

Am I supposed to size the filter according to set of all names in the world ? Is there something I am missing ? This is not addressed in the original publication.

## Constraints

**Size** : The Cuckoo filter will be transmitted over the network. But it will be done in an asynchronous way (let's say an update every 2 hours). So this will weigh in the size constraint.

**Time** : The real constraint is time. When I query the filter I would like my response in less than 5 seconds.

**False positive** : I also hope to have false positive rate of at most 20%.

**Security** : In my example I store names, but in reality I will store sensitive data that should be protected and anonymized under GDPR. After a statistical analysis I concluded that the data's entropy is too low to store as a list of hashes.

**Other options** : I'm open minded by nature. I always welcome other options.

## Attempt at a self answer

Considering that the fingerprint is $f$ bits long, and I have $m$ buckets, the probability that the name Bob has the same features (index and fingerprint) as the name Alice is :

$$ \frac{1}{2^f} \cdot \frac{1}{m} $$

Which means that the probability that there is another name colliding with the name Anna is:

$$ (n - 1) \cdot \frac{1}{2^f} \cdot \frac{1}{m} $$

With 30 000 names, a fingerprint of 8 bits and 600 buckets, the result is $0.39$ which means a false positive rate of **39 %**.

To reduce the false positive rate I can either increase the fingerprint size or the number of buckets. Using 6000 buckets instead of 600 gives me a false positive rate of **3.9%**. This hack might be working in my example case but in reality we are talking of $10^{19}$ names in the whole world and $10000$ names to store in the filter.

It seems to me that Cuckoo filter were not designed with this use case in mind, and when people are using Cuckoo filter, they hope to store almost every existing item in there at some point.

# Answer
As discussed in the comments it turns out that, yes, I need to size my Cuckoo filter for the set of every existing name. That being said, it is not much of a problem in the end if I only send the buckets with fingerprints in it, which shouldn't be more than 600.

In addition to that, my attempt at a self answer was very wrong. The probability that there is another name colliding with the name Anna is actually:

$$P\left(\bigcup\_{i = 1}^n A\_i\right) = \sum\_{k = 1}^n (-1)^{k+1} \sum\_{1 \le i \lt j ... \lt k \le n} P(A\_i \cap A\_j ... \cap A\_k)$$

This is the inclusion-exclusion principle. Because of my hypotheses, the probability can be simplified as:

$$P\left(\bigcup\_{i = 1}^n A\_i\right) = 1 - (1 - p)^n$$

As highlighted in the original paper, we also have to take into account that $$2b/2^f \le \epsilon$$.
> 1 votes

---
Tags: data-structures, probabilistic-algorithms
---


# Question
Title: Nondeterministic Logarithmic-space in directed graph
I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the following problem.

Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem. To show that the problem is $NL-hard$, start from problem $s; t-connectivity$ and as an intermediate step, create a acyclic graph $G^a$ which is $s’; t’- connected$ if and only if the original graph $G$ is $s; t- connected$.

The author has set as hint: use the length of the paths of a vertex $x$ at a vertex $y$.

# Answer
To show that the problem is in NL: guess a directed edge $(u,v)$ of the graph that is part of a cycle, and check (using the connectivity algorithm as a black-box, or by guessing each step of a walk) whether $v$ is connected to $u$ in $G$.

To show that the problem is NL-Hard create a new graph $G'$ as follows:

* For each vertex $v$ of $G$ add $n$ vertices $v^{(0)},\dots,v^{(n-1)}$ to $G'$.
* For each edge $(u,v)$ of $G$, and for each $i=0,\dots,n-2$, add the edge $(u^{(i)}, v^{(i+1)})$ to $G'$.
* For each $i=0,\dots,n-2$, add the edge $(t^{(i)}, t^{(i+1)})$ to $G'$.

It is easy to see that $G'$ is acyclic and that $s^{(0)}$ and $t^{(n-1)}$ are connected in $G'$ iff $s$ and $t$ are connected in $G$.

Now, consider the graph $G''$ obtained by adding the edge $e=(t^{(n-1)}, s^{(0)})$ to $G'$.

If $s^{(0)}$ and $t^{(n-1)}$ were connected by a path $P$ in $G'$, $G''$ contains the cycle $C = P + e$. The opposite direction is also true: if there is a cycle $C$ in $G''$ then $C$ must include $e$ and this means that of $C-e$ is a path between $s^{(0)}$ and $t^{(n-1)}$ in $G'$.
> 3 votes

---
Tags: space-complexity
---


title: Non Deterministic Turing Machine

text:
# Question
Title: Non Deterministic Turing Machine
Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?

# Answer
> 3 votes
There is no such problem. All problems that can be solved (i.e., decided) by a non-deterministic Turing machine $T$ can also be solved by a deterministic Turing machine that simulates $T$.

---
Tags: turing-machines, automata, nondeterminism
---


# Question
Title: Whats an elegant way to tour a hypercube, in distance order:
Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$.

I've been working on a problem where I want to generate the (exponentially many) corners of this cube (as a list of 0's and 1's) but I want to generate them in "distance" order. That is starting from a corner (0,0,0...) I will generate a sequence of points $p\_0, p\_1 ... $ with the property that the distance of each point $p\_k$ from the origin $p\_0$ is either constant or increasing. (Naturally this means (1,1,...) will be the very last point in the sequence) and you can visualize this as "snaking around the cube".

To be more explicit in $\mathbb{R}^3$, a sample list I could generate would be:

$$\begin{pmatrix} 0,0,0 \\\ 1,0,0 \\\ 0,1,0 \\\ 0,0,1 \\\ 1,1,0 \\\ 1,0,1 \\\ 1,1,0 \\\ 1,1,1 \end{pmatrix} $$

This is not the ONLY solution. For any two entries $e\_i$, $e\_j$ if the number of "1"'s in the entries is equal, then a new list could be generated by "swapping" the entries in the original list.

## My Work So Far:

## A very inefficient solution:

I could generate the list of all binary numbers from $0$ to $2^{n} - 1$ with $n$ digits and then attempt to sort them by assigning an "magnitude" function that simply counts the number of "1's". This is very expensive especially given the exponential size of the data set and moreover cannot be done in a "batch" or online manner.

## A slightly better solution:

For a positive integer $n$ and dimension $d$ define the following

Generator($n$, $d$)

if $n == 0$ then we return a vector of $d$ 0's.

If $n \> 0$ then we consider the partially formed lists L\_1 = $(1)$, L\_2= $(0,1)$ , L\_3 = $(0,0,1)$ ... $(0,0,0...1)$

Then we calculate Generator($n-1$, $d-r$) where r ranges from 1 to the length of L\_max, and for each r we append to it the prefix list L\_r.

Then calling Generator(0,n), Generator(1,n) ... Generator(n,n), as if it were one continuous list would yield our distance order tour of the cube.

# Answer
> 3 votes
For all $k=1, \dots, n$, you can easily generate all bit strings of length $n$ with exactly $k$ bits set.

The lexicographically smallest bit string has the $k$ ones in the $k$ least significant bits. If you interpret this string string as an integer, and it fits in a constant number of words, you can use bit tricks to find the next string in a constant number of operations.

See the section "Compute the lexicographically next bit permutation" here, and this answer for an explanation.

---
Tags: computational-geometry
---


title: 2D interval scheduling problem

text:
# Question
Title: 2D interval scheduling problem
Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\\{(w\_i, h\_i, x\_i) \mid i \in \\{0, \ldots, n - 1\\}\\}$, as well as a bound $(y\_\mathrm{min}, y\_\mathrm{max})$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $O(n^3)$) approximation algorithm that gives a sequence $\\{y\_0, \ldots, y\_{n - 1}\\}$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $y\_\mathrm{max} = 10$ and $h\_k = 3$, then $y\_k = 9$ would be invalid, since the top edge would be at $12$ which is more than $10$.

# Answer
> 0 votes
This is called the offline dynamic storage allocation problem. Check out the papers cited by https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 for a good review of the literature.

---
Tags: algorithms, optimization, approximation, scheduling, intervals
---


title: A non-polynomial reduction

text:
# Question
Title: A non-polynomial reduction
Given two problems $P\_1$ and $P\_2$. $P\_1$ is NP-complete in the strong sense and we want to prove that $P\_2$ is also NP-complete but the reduction from $P\_1$ to $P\_2$ is not polynomial. Can we say that $P\_2$ is NP-complete?

# Answer
> 1 votes
No. As a counterexample pick any non-trivial problem $P\_2$, i.e., a problem with at least one yes instance $I\_{\text{yes}}$ and at least one no instance $I\_{\text{no}}$.

To reduce an instance $I\_1$ of $P\_1$ to an instance $I\_2$ of $P\_2$ first solve $I\_1$ (e.g., by brute force). If the answer to $I\_1$ is yes, then let $I\_2 = I\_{\text{yes}}$, otherwise $I\_2 = I\_{\text{no}}$.

---
Tags: complexity-theory, np-complete, reductions, polynomial-time-reductions
---


# Question
Title: How to prove this language is context free?
There's lots of ways to prove a language is *not* context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.

$L = \\{a^{(n+1)} b^{(m+2)}c^{(n+4)}\ |\ m, n ≥ 0 \\}$

I see that the langauge is equivalent to $L = \\{aa^nbbb^mccccc^n\\}$, but I'm not sure if that helps at all.

Maybe breaking the language apart into a concatenation of three languages like $\\{a^{n+1} | n\>= 0\\}.\\{b^{m+2} | m \>= 0\\}.\\{c^{n+4} | n\>=0\\}$ might be helpful, because we can do a rule separately for each? The n has to be equal for the left and right side though, which I'm having difficulty with.

Any help would be much appreciated!

# Answer
> I see that the language is equivalent to $L = \\{aa^nbbb^mccccc^n\\}$,

Indeed

> but I'm not sure if that helps at all.

Well, maybe not. How about if we write the equivalent language ever-so-slightly differently:

$$L = \\{a^nabbb^mccccc^n\\}$$

That's the same as

$$\begin{align}L &= \\{a^nMc^n\\}\\ M &= \\{abbb^mcccc\\}\\ \end{align}$$ And then $$\begin{align}L &= \\{a^nMc^n\\}\\ M &= \\{abbNcccc\\}\\ N &= \\{b^m\\}\\ \end{align}$$ Which seems pretty straight-forward.

Or, to put it another way: Look for symmetries. Or try to create them.
> 2 votes

# Answer
The ways to prove a language context free are to (1) exhibit a context free grammar for it; (2) exhibit a PDA accepting it; (3) construct it using closure properties. Here I'll go for (1).

Words in the language have a number of $a$ at the beginning and end that almost match, and an arbitrary (almost) number of $b$ in the middle. So a grammar is as follows:

$\begin{align\*} S &\to a S a \mid a A a a a a \\ A &\to A b \mid bb \end{align\*}$

The idea is that the first production for $S$ adds $a$ at both ends, the second one fills up the start and end numbers (1 and 4, respectively) and hands the task over to $A$. Now $A$ adds $b$ in the first production, finishes off with $b b$ to complete at least two of them.

The other alternatives I leave as an exercise. For a PDA, think how you would check that the word is of the required form, reading a symbol at a time and having only a stack as memory.
> 1 votes

---
Tags: formal-languages, automata, finite-automata, context-free, formal-grammars
---


title: Duplicating ACKs and Window Sizes

text:
# Question
Title: Duplicating ACKs and Window Sizes
After reading an answer at this link:

https://serverfault.com/questions/503345/three-duplicate-acknowledgementss

I am confused. Do ACK values repeat when a packet is lost or when an out of sequence packet is received? For example in the diagram, the ACK values are same at the 12th and 13th segment. However, there's a drastic change in the window size. What exactly is the link?

I also read that selective acknowledgments could be used in segement 8. I know what they do by definition but I don't understand why we could use them here in segment 8 particularly. Any ideas? If it's because of the same SEQ & ACK numbers in the corresponding segments, it would be the same for segment 10, right?

# Answer
> 1 votes
In simple words: ack is the way of the receiver to tell you "i got data until *some num* now send me from this num",now if a packet is lost it means the reciver will not get its data.

If i understood your question right then we can see the acks in the 12th and 13th packets are identical,the reason is because not data was sent between them to the reciver

Now why the window size is bigger?its simply because the receiver reads the data in a certain speed and the buffer now has more space in it

So th reason they have same acks its because no data was sent to the receiver And the reason why the window size is bigger is because the receiver reads from the buffer

---
Tags: computer-networks, tcp
---


# Question
Title: How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm
I am stuck on solving this problem and cannot understand how is the ceiling function omitted or solved. Please help.

The equation:

$\sum\_{h=0}^{\lfloor\lg n\rfloor} \lceil\frac{n}{2^{h+1}}\rceil O(h) $.

But this transformed to:

$O\left(n \sum\_{h=0}^{\lfloor\lg n\rfloor} \frac{h}{2^h}\right)$

My question concerns on omitting the ceiling function. I'm not clear on whether it was omitted or solved.

This has been taken from CLRS Section $6.3$ **Building a Heap**.

Please help me out. Thank you.

# Answer
$$ \begin{align\*} \sum\_{h=0}^{\lfloor\lg n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h) &\< \sum\_{h=0}^{\lfloor\lg n\rfloor} \left(1+ \frac{n}{2^{h+1}}\right) O(h) \\ &\< \sum\_{h=0}^{\lfloor\lg n\rfloor} \left(\frac{n}{2^h} + \frac{n}{2^h}\right) O(h) = 2n \sum\_{h=0}^{\lfloor\lg n\rfloor} \frac{ O(h) }{2^h} = O\left(n \sum\_{h=0}^{\lfloor\lg n\rfloor} \frac{ h }{2^h}\right). \end{align\*} $$.
> 3 votes

---
Tags: heaps, heap-sort
---


# Question
Title: Need help analyzing the runtime analysis of this algorithm/algorithms in general
This is the algorithm I was trying to find the runtime of (doSomething) -

```
Procedure findMinMax(int A[], int start, int end)
int min = max = A[start]
int i = j = start
for(int k = start; k <= end; k++)
if(A[k] < min)
i = k
min = A[k]
if(A[k] > max)
j = k
max = A[k]

end for
return {i, j}
end findMinMax

Procedure swap(int A[], int i, int j)
int temp = A[i]
A[i] = A[j]
A[j] = temp
end swap

Algorithm doSomething(A[])
Input: array A of N integers
Output: ?
int i = 0
int j = N-1
while(j - i > 0)
int[] minMax = findMinMax(A, i, j)
int min = minMax[0]
int max = minMax[1]
if(min == j && max == i)
swap(A, min, max)
else if(min == j)
swap(A, i, min)
swap(A, j, max)
else if(max == i)
swap(A, j, max)
swap(A, i, min)
else
swap(A, i, min)
swap(A, j, max)
i++
j--
end while
return A
end doSomething

```

The indenting of the code is bad in the code block, so here is an image of the code with proper indenting if that helps -

The while loop runs n/2 times. This is because i is always incremented by 1 at the end of the while loop and j is always decremented by 1. None of the helper methods called inside of the while loop and none of the other constant time statements called changes i and j, so the while loop ALWAYS runs n/2 times.

Inside of the while loop, the swap functions are called. These are of O(1) constant time and don't affect the runtime. But, findMinMax is also called, which has an O(N) runtime.

In my eyes, I thought that the overall runtime of doSomething would be O(NlogN). The while loop running n/2 times would be equivalent to something like: "for(int i = 0; i \< N; i += 2)". That for loop by itself (not considering what is inside of it) has a runtime of O(logN). I figured the same logic applies here and that the while loop has a runtime of O(logN). Multiply that by the runtime of findMinMax which is inside of the while loop body and you get O(NlogN).

However, the answer key disagrees. The answer key states that the runtime of the algorithm is O(N^2).

The reasoning is -

That doesn't really make sense to me. Why was a summation used? I thought they were only used to find runtimes when there was an inner loop dependent on the outer loop. Furthermore, why does 2k or 2k + 1 go inside of the summation?

I also tried using a summation for something like -

```
for(int i = 0; i < N; i+=2) {
   //O(1) operation
}

```

I got the summation -

which simplifies to N/2, and thus O(N), since the 1/2 constant gets factored out.

I obviously do not see why a summation was used for the doSomething algorithm runtime calculation, especially since there was no inner loop which depended on the outer loop (i.e. "for(j = i + 1)"). The summation logic didn't even work for that other code block I posted just above.

Any help/clarifications would be appreciated!

# Answer
> 1 votes
I figured out why the runtime is O(N^2).

Yes, the while loop does run N/2 times. However, that is equivalent to -

"for(int i = 0; i \< N; i+=2)" which has a runtime of O(N) still.

I confused it with -

"for(int i = 0; i \< N; i \*= 2)" which has a runtime of O(logN).

The summation also results in the correct answer in this instance.

# Answer
> 1 votes
The OP has already understood the solution, but still:

findMinMax procedure given above is just finding the maximum and minimum element in the array. It has a runtime of O(N).

swap procedure just swaps two array elements given by their indices, which is O(1).

doSomething is an interesting procedure. It seems to be some kind of a variant of selection sort, where minimum element is always swapped with i and maximum element is swapped with j.

The while loop in doSomething runs a total of N/2 times. (i goes from 0 to N/2 and j goes from N-1 to N/2.)

The total time complexity will be (number of times the while loop is run) * (runtime of each while loop).

However, here, the time complexity of findMinMax is not always N. It is O(end-start). Hence, if we just multiply the runtimes, we will get an upper bound, but not necessarily a tight upper bound.

To get the tight upper bound on the runtime, we need to find this sum: (Assuming N is even) $$ \begin{align} \sum\_{start=0, end=N-1, start\<end}^{} (end-start) & = N + N-2 + N-4 + ... + 4 + 2 \\ & = 2 * (N/2 + (N/2 -1) + (N/2 -2) + ... + 2 + 1) \\ & = 2 * \frac{(N/2)\*(N/2 + 1)}{2} \\ & = O(N^2) \end{align} $$

To OP: No, one does not need an inner loop dependent on an outer loop to sum their runtimes. Just having a nested loop means the total time will be (the number of times the outer loop runs) * (the number of times the inner loop runs) * (complexity of the inner loop). Anyway, it's better to find complexity through the basic concepts and avoid such shortcut rules.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting, big-o-notation
---


# Question
Title: Least common ancestor relative to an arbitrary vertex as root
Consider following problem:

> Given an undirected tree answer following type of queries. (No. of queries and vertices can be as high as $10^5$)
>
> $\text{LCA}(r, u, v)$: Find the Lowest Common Ancestor of vertices $u$ and $v$ assuming vertex $r$ as the root.

---

Now, in solution it's given that answer will always be one this: $r, u, v, \text{LCA}(r, u), \text{LCA}(r, v), \text{LCA}(u, v).$

Where $\text{LCA}(u,v)$ denotes Lowest Common Ancestor of vertices $u$ and $v$ if we assume vertex number $1$ as the root.

---

So I'm looking for a proof for claim made in a solution.

# Answer
Let us consider several possibilities:

* The root is $r$. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
* The root is $u$, and $r,v$ are contained in different branches. In this case, $\mathrm{LCA}(r,u,v) = u$.
* The root is $u$, and $r,v$ are contained in the same branch. If $r$ is an ancestor of $v$, then $\mathrm{LCA}(r,u,v) = r$. If $v$ is an ancestor of $r$, then $\mathrm{LCA}(r,u,v) = v$. Otherwise, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
* The root is none of $r,u,v$, and all of $r,u,v$ belong to different branches. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v) = 1$.
* The root is none of $r,u,v$, the vertex $r$ belongs to one branch, the vertices $u,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
* The root is none of $r,u,v$, the vertex $u$ belongs to one branch, the vertices $r,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
* The root is none of $r,u,v$, and all of $r,u,v$ belong to a single branch, say rooted by a child $s$ of $r$. We apply induction to the subtree rooted at $s$.

To convince yourself of the various claims, I suggest drawing some diagrams, and using the characterization of $\mathrm{LCA}(r,u,v)$ as the vertex on the unique path from $u$ to $v$ which is closest to $r$.
> 1 votes

---
Tags: trees
---


# Question
Title: Multiplication mod 2 without extra registers
For an arbitrary bitstring $(x\_1, x\_2,\ldots, x\_n)$ and an $n\times n$ invertible binary matrix $M$ (fixed ahead of time), I would like to construct a circuit $C$ acting on these $n$ bits whose output will be such a bitstring $(y\_1, y\_2,\ldots, y\_n)$ that: $$ \begin{pmatrix} y\_1 \\ y\_2 \\ y\_3 \\ \ldots \\ y\_n \end{pmatrix} = M \begin{pmatrix} x\_1 \\ x\_2 \\ x\_3 \\ \ldots \\ x\_n \end{pmatrix} \bmod 2 \ , $$ The extra registers are not allowed. The circuit $C$ should only contain $NOT$ and $CNOT$ gates (where $CNOT(x, y) = (x, x+y \bmod 2) $). The matrix $M$ is such that it permits for a reversible calculation.

The lower bound is trivially given by $O(n^2)$ operations. (That's how you would usually multiply matrices, if you had access to the original values of registers all the time. The question, however, is inspired by quantum computation, where one cannot store the initial values, and extra qubits are expensive.)

A known fact from quantum information is that such circuit can be constructed with at most $O(\exp(n))$ gates. The goal is to design it using a sub-exponential number of gates.

# Answer
> 2 votes
Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.

---
Tags: algorithms, arithmetic, circuits
---


# Question
Title: Functional dependencies on relational schema
Given a relational schema $R(V,W,X,Y,Z)$ with functional dependencies $F = \\{VW \to X, X \to YZ, W \to VX, V \to W, Z \to XY\\}$. What are the keys of $R$?

Is the key just $V$? If so, is $\\{ R\_2(V,W,Z), R\_3(V,X,Y) \\}$ the lossless-join decomposition of $R$?

# Answer
I assume, by key, you mean the candidate key.

Let's check whether V is a candidate key:

closure(V) = {V, W, X, Y, Z}

Hence, V is a candidate key.

closure(W) = {W, V, X, Y, Z}

Hence, W is also a candidate key.

closure(X) = {X, Y, Z}

closure(Y) = {Y}

closure(Z) = {Z, X, Y}

By checking all the other possible keys, one can see that only V and W are candidate keys.

The lossless-join decomposition of R does not have to be unique.

One can be described as follows:

R = {R1(V, W, X), R2(X, Y, Z)}

Since R1 ⋂ R2 = {X} And X -\> {X, Y, Z}.

Hence, X -\> R2.

Hence, R1 ⋂ R2 -\> R2. Hence, this decomposition is a lossless join decomposition.

R2 can be further divided as R2 = {R3(X, Y), R4(X, Z)}

Similarly, R1 = {R5(V, W), R6(W, X)}

Hence R = {R5(V, W), R6(W, X), R3(X, Y), R4(X, Z)}
> 1 votes

---
Tags: relational-algebra, functional-dependencies
---


# Question
Title: Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$
Is there a way to solve this recurrence using master theorem:

$$T(n) = 4T(n/2) + Θ(n^2/\log n)$$

# Answer
As mentioned by @Yuval Filmus in the comment, you can use the extension of the master theorem (case 2b). The result is $T(n) = \Theta(n^2 \log\log{n})$.
> 3 votes

---
Tags: recurrence-relation, master-theorem
---