title: AND operator of many functions

text:
# Question
Title: AND operator of many functions
Suppose we have a set of functions $f\_i: \mathbb Z \rightarrow \\{0,1\\}, i=1, \dots,n $, with the following property:

For each $i =1,\dots ,n$, there exists an $x\in \mathbb Z$ such that $f\_i(x)=0$ and $f\_j(x)=1$ for each $j\in \\{1,\dots,i-1,i+1,\dots,n\\}$. Also, there exists an $x \in \mathbb Z$ such that $ f\_i(x)=1$ for each $i$.

Let $x\in \mathbb Z$. In order to determine whether $f\_1(x)$ AND $f\_2(x)$ AND ... AND $f\_n(x)$, is it necessary to compute each $f\_i(x)$ until one of these functions is found to be zero or until all functions are found to be one, which would take $\Omega(n)$ time in the worst case scenario?

Added to clarify: The functions $f\_i$ are known. The input is $x \in \mathbb Z$.

# Answer
> 5 votes
When $f\_i$ are given as black boxes, it takes $\Omega(n)$ in the worst case to compute their AND.

The constraints that the question puts on the functions $f\_i$, don't really tell anything about $f\_i$ and their behavior, maybe except for a very small subset of inputs. For instance, we can assume that over the inputs $x=0,...,n$ each $f\_i$ is 1, except for the case where $x=i$. This satisfies all the constraints stated. But if $x\>n$ we have no idea how $f\_i$ behaves. As a trivial example, it can be that each $f\_i$ has some infinite kernel (=values of $x$ that zeroize it), but the union of all the kernels doesn't cover the entire $\mathbb{Z}$. As a block box, it is not clear that you even have a compact way to describe each kernel, and you have no choice but querying the black box.

Even if the kernel of each function is known (and has a compact description), it can be that the most compact description of their union is "the union of the kernel of $f\_1$ and $f\_2$ and ...", which hints that one must compute each $f\_i$ separately to know their AND value. For instance, if $f\_1$ is the indicator function of all the prime numbers, and $f\_2$ is the indicator of all odd numbers whose binary representation has an equal number of ones and zeros. Probably simpler examples can be found.

# Answer
> 3 votes
If we only have black-box access to the functions $f\_i$ (they are provided as oracles), then yes, it takes $\Omega(n)$ time. For instance, suppose $f\_i(1000+i)=0$ and $f\_i(1000+j)=1$ for $j\ne i$. This does not constrain the behavior of $f\_i$ for $x\<1000$, so does not provide any useful information about the $f\_i$'s. Then it is possible to prove a $\Omega(n)$ time bound for queries about $x$ (when $x\<1000$) using an adversary argument.

*However,* don't mis-interpret this! Don't assume this means that $\Omega(n)$ time is needed when the algorithm has access to a description of the $f\_i$'s. An algorithm that is provided circuits or code for the $f\_i$'s might well be able to do better.

For instance, suppose all the $f\_i$'s come from the class if affine functions ($f\_i(x)=\alpha\_i x + \beta\_i$), and we are given a mathematical expression for each $f\_i$ (we are given the $\alpha\_i$'s and $\beta\_i$'s). Then there is an algorithm that uses $o(1)$ time, in this scenario. In particular, we know that $f\_i(x)=0$ if and only if $x\_i = -\beta\_i/\alpha\_i$. Therefore, we can precompute the value of all $-\beta\_i/\alpha\_i$; either they are all equal to some value, say $c$, or they are not all equal. If they are not all equal, then the answer to any query about any particular $x$ is always "False". If they are all equal to $c$, then the answer to a query about a particular $x$ is always "True if $x=c$, False otherwise". In both cases, you can answer queries about a particular $x$ in $O(1)$ time.

So, the $\Omega(n)$ time bound I mentioned in the first paragraph probably will not apply to most real-world situations that arise in practice.

# Answer
> 0 votes
Suppose we define $f\_i$ so that $f\_i(x)=1$ for each $i=1,\dots,n$ whenever $x$ is even and $f\_i(x)=0$ for some $i \in \\{1,\dots,n\\}$ whenever $x$ is odd so that the functions satisfy the constraints given in the question. Then we can compute $f\_1(x)$ AND $f\_2(x)$ AND ... AND $f\_n(x)$ by just checking whether $x$ is even or odd. \[For instance, if $n=3$, we could define $f\_1(1)=0, f\_2(1)=f\_3(1)=1$, $f\_1(3)=f\_3(3)=1, f\_2(3)=0$, $f\_2(5)=f\_3(5)=1, f\_1(5)=0$ and $f\_i(x)=1$ whenever $x$ is even and it will satisfy the constraints. It is possible do this for general $n$.\]

So the answer to the question is that it is not necessarily true that one must compute each function $f\_i(x)$ until one is found to be zero or until all are found to be one.

---
Tags: complexity-theory, time-complexity
---


title: Online generation of uniform samples

text:
# Question
Title: Online generation of uniform samples
A source provides a stream of items $x\_1, x\_2,\dots$ . At each step $n$ we want to save a random sample $S\_n \subseteq \\{ (x\_i, i)|1 \le i \le n\\}$ of size $k$, i.e. $S\_n$ should be a uniformly chosen sample from all $\tbinom{n}{k}$ possible samples consisting of seen items. So at each step $n \ge k$ we must decide whether to add the next item to $S$ or not. If so we must also decide which of the current items to remove from $S$ .

State an algorithm for the problem. Prove its correctness.

# Answer
> 9 votes
Due to the dubious nature of the question, I only provide hints.

Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?

For a proof, you will have to proceed inductively. In the step, you assume that $S\_{n-1}$ is indeed a uniform sample. From this and the way you choose whether to include $x\_n$ and which element to drop, you have to get that $S\_n$ is a uniform sample, too.

Try if you can prove above idea correct. If it is not, find out where the problem is and fix it. See this answer to a similar question for a detailed application of this technique.

# Answer
> -1 votes
The best algorithm for your problem is Reservoir Sampling Algorithm. Read this

---
Tags: algorithms, probability-theory, randomized-algorithms, randomness, online-algorithms
---


# Question
Title: Which pass do you look at for Radix Sort stability?
I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.

So in Radix Sort, you go digit by digit from least significant to most significant, and along the way you are swapping elements around. When considering the case where two digits are the same, do you look at the original array to decide which should come first, or do you look at the previous iteration?

In one case you would have to store the original to look back on, so my guess is it's not that, but I can't tell which provides the correct result by my own examples. Let me know if I need to describe my question better and I will try.

# Answer
Radix sort always uses the results of the previous pass, not the original array. It does not attempt to store the original value of the array. You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property.

As Wikipedia describes, radix sort is stable if you sort the digits starting from least significant and moving on to most significant.
> 2 votes

---
Tags: algorithms, sorting, radix-sort
---


title: Tower Of Hanoi Time Calculation

text:
# Question
Title: Tower Of Hanoi Time Calculation
I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution.

The setup is the standard Towers of Hanoi, except that moving the smallest disk costs one unit of time, moving the second-smallest disk takes two units of time and so on.

What is the total minimum time solving towerOfHanoi?

# Answer
Hint. Set up a recurrence relation similar to the one for the standard Towers of Hanoi. Then use the techniques from our reference question on recurrence relations to solve the recurrence.
> 2 votes

# Answer
Starting from this system:

$$ \begin{cases} T(1) = 1 \\ T(n) = 2T(n-1) + n \end{cases} $$

To use repertoire method to solve the system, we'll generalize it as this:

$$ \begin{cases} T(1) = \alpha \\ T(n) = 2T(n-1) + \beta n + \gamma \end{cases} \tag 0 $$

The result must look like this:

$$ T(n) = A(n) \alpha + B(n) \beta + C(n) \gamma $$

**I. Let's try T(n) = 1** $$ \begin{cases} T(1) = 1 = \alpha \\ T(n) = 1 = 2T(n-1) + \beta n + \gamma = 2 \cdot 1 + \beta n + \gamma \end{cases}$$ Thus: $$ (\alpha, \beta, \gamma) = (1, 0, -1) $$ Which means that $$ T(n) = A(n) - C(n) = 1 \tag 1 $$.

**II. Now try T(n) = n** $$ \begin{cases} T(1) = 1 = \alpha \\ T(n) = n = 2T(n-1) + \beta n + \gamma = 2n - 2 + \beta n + \gamma \end{cases}$$ Thus: $$ (\alpha, \beta, \gamma) = (1, -1, 2) $$ Which means that $$ T(n) = A(n) - B(n) + 2 C(n) = n \tag 2 $$.

**III. Also, for $ (\alpha, \beta, \gamma) = (1, 0, 0) $:** $$\begin{cases} T(1) = 1 \\ T(n) = 2T(n-1) = 2^n \end{cases}$$ Which means that $$ T(n) = A(n) = 2^{n-1} \tag 3$$.

From (1) and (3): $$ 2^{n-1} - 1 = C(n) $$

Now from this equation and (2): $$2^{n-1} - B(n) + 2 (2^{n-1} -1) = n$$ $$2^{n-1} - n + 2^n -2 = B(n) $$

Final result for $ (\alpha, \beta, \gamma) = (1, 1, 0) $: $$ T(n) = A(n) + B(n) $$ $$ T(n) = 2^{n-1} + 2^{n-1} - n + 2^n -2 $$ $$ T(n) = 2^{n+1} - n - 2$$
> 3 votes

---
Tags: discrete-mathematics, towers-of-hanoi
---


# Question
Title: Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$
An array $a\[1,\ldots,n\] \subseteq \\{1,\ldots, k\\}$ is given, where $k \< \sqrt{n}$.
Our goal is a project algorithm which sorts it in place and in time $O(n\log k)$.
We assume that $k \< \sqrt{n}$ - otherwise $O(n\log k) = O(n\log n)$ - then we may use HeapSort.

We may assume that we know $k$. I try to do it. The only thing that I can do is finding all $k$ distinct elements and bring them on beginning of array in $O(n\log k)$ - I use binary search.

However I have no idea how to solve it. Any ideas?

# Answer
> 3 votes
Here is an idea. Use a variant of quicksort with a twist:

1. Find the median $m$ in-place in time $O(n)$ (this could jumble the array).
2. Partition the array around $m$ using the quicksort partition routine.
3. Divide the array into three parts: smaller than $m$, equal to $m$, and larger than $m$, and recurse on the first and the last.

Consider a recursion tree for this algorithm. The tree has depth $\log n$ and $k$ nodes. Imagine "compressing" the tree by short-circuiting all nodes having only one child. You get a tree with depth $\log k$. Can you justify this short-circuiting and prove a running time of $O(n\log k)$? Or is there a counterexample?

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Are there any articles or software which can infer original shapes from overlapping shapes?
Given that some shapes overlap in an image, are there any papers or articles or code which can infer the original shapes from the overlapping?

I am thinking to apply some machine learning to this since I can generate overlapping shapes using code and use a neural network to try to work out the original shapes. Perhaps another way is just heuristic rules.

# Answer
I'd suggest you start with image segmentation, to identify each of the separate (potentially occluded) shapes in the image.

If there was no occlusion, the problem would then be easy. For each shape in the image, you could compare it each possible shape in your library of shapes and see if it's a match. If you don't have to deal with pose/rotation, only possible variation in the size and location of the shape, that will be easy to do: given a shape $S$ from the image and a shape $S'$ from your library of shapes, you first normalize their sizes, then check if they are a match using normalized cross-correlation or something similar. If you do have to deal with variation in pose/rotation as well, you could use something like SIFT to align $S$ to $S'$, then proceed from there.

However in your example you have to deal with occlusion, and it's occlusion that makes the problem more challenging. So, let's re-formulate the problem. You get a bunch of partial shapes $S\_1,\dots,S\_k$ from your image. For each $S\_i$, you can also derive an occlusion mask $M\_i$ that indicates which pixels were occluded by other shapes. Now you want a way to test whether $S\_i,M\_i$ is a match to some shape $S'$ in your library. How to do this?

If you only had to deal with variation in location but not rotation/size/pose, then this would be easy. It basically comes to checking that $S\_i$ matches $S'$ at the non-occluded pixels (they don't have to match at the pixels indicated by $M\_i$, but they do have to match elsewhere), i.e., whether $S\_i \lor M\_i = S' \lor M\_i$, where $\lor$ denotes bitwise OR.

So the remaining challenge is how to deal with variation in size and/or rotation/pose. One approach that might work is to extract all the points on the boundary of $S\_i$ (ignoring "boundaries" caused by occlusion) and all points on the boundary of $S'$, and then see if there's a way to make them line up. Note that we'll have to allow an incomplete match, because the occlusion may mean that the inferred boundary of $S\_i$ is incomplete. One approach for finding a match might be to use RANSAC to estimate a homography between the two sets of points. (This is vaguely reminiscent of SIFT, but we're using the points on the boundary as the keypoints rather than using SIFT's methods to derive keypoints.)

If you have to deal with more complex images, more complex shapes, or other more complex situations, you could look at the literature on shape analysis and shape context.
> 2 votes

---
Tags: computational-geometry, image-processing, computer-vision
---


# Question
Title: dynamic programming exercise on cutting strings
I have been working on the following problem from this book.

> A certain string-processing language offers a primitive operation which splits a string into two pieces. Since this operation involves copying the original string, it takes n units of time for a string of length n, regardless of the location of the cut. Suppose, now, that you want to break a string into many pieces. The order in which the breaks are made can affect the total running time. For example, if you want to cut a 20-character string at positions $3$ and $10$, then making the first cut at position $3$ incurs a total cost of $20 + 17 = 37$, while doing position 10 first has a better cost of $20 + 10 = 30$.

I need a dynamic programming algorithm that given $m$ cuts, finds the minimum cost of cutting a string into $m +1$ pieces.

# Answer
The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.

In formula:

$\qquad \displaystyle \operatorname{mino}(s, C) = \begin{cases} |s| &, |C| = 1 \\ |s| + \min\_{c \in C} \left\[ \begin{align}&\operatorname{mino}(s\_{1,c}, \\{c' \in C \mid c' \< c\\})\ \\ +\ &\operatorname{mino}(s\_{c+1,|s|}, \\{c' - c \in C \mid c' \> c\\}) \end{align}\right\] &, \text{ else} \end{cases}$

Note that applying memoisation to this recursion actually saves work as switching the order of any successively applied pair of cuts results in the same three subproblems being solved.
> 11 votes

# Answer
It is always a good idea to find a recursive algorithm first and then turn it into a table.

1. $f(C,n)$
2. $~~$if(C = $\emptyset$) return 0;
3. $~~$else
4. $~~~~$opt = infinity;
5. $~~~~$for each $c\in C$ do
6. $~~~~~~D=\\{d\in C:d\<c\\}$
7. $~~~~~~E=\\{e-c:e\in D,e\>c\\}$
8. $~~~~~~opt = min\\{opt,f(D,c)+f(E,n-c)\\}$
9. $~~~~$return $opt+n$;

So you may ask: isn't there too many subsets of C to be put in a table? Observe that only 'consecutive' subsets are needed. And there are only $n \choose 2$ of them.(why?) Another problem is: some entries will change value in $E$. We can walk around this by indicating start and end in each $f$ rather than just specifying the length.
> 2 votes

# Answer
This is very similar to Quicksort on a multiset; it's optimal when the cut point is closest to the middle, and then we recurse.

If I gave you a shuffled version of the multiset M = {1,1,1..1,2,2...2,....,m,m..m} where the runs end at each cut point, you would optimally quicksort it by picking a cut $s\_k$ nearest the middle as the pivot. The operation of splitting the elements into left and right partitions takes n operations the same way that string splitting does, so you can use the same arguments as Quicksort to show that the median is optimal.
> 0 votes

---
Tags: algorithms, combinatorics, strings, dynamic-programming
---


title: how to binarize an image?

text:
# Question
Title: how to binarize an image?
I don't want to binarize a certain image through another program, I want to know how to binarize things myself. All I know is that there is something to do with a threshold and if it is above the threshold it is either 1 or 0 and the opposite if below. My images are using RGB but I can also use HSB or HSV. I just want the algorithm to do so . :)

# Answer
There is Otsu method to use variance when splitting.

Taking your own steps you should convert RGB to grayscale (simple mean like $(R+G+B)/3$, or use luminance grayscale).

The next step is to give some threshold, from Otsu or arbitrary given by your choice, and operating on grayscale image everything below (or equal) is 0, so it will be black, and greater than threshold is 1 (white).

Operations on other scheme like HSL is exactly taking luminance, but the full change RGB -\> HSL is not needed because you discard color info.

Situation when values are out of range does not occur, so do not worry.
> 1 votes

---
Tags: algorithms, image-processing
---


# Question
Title: Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?
I'm trying to figure out if:

1. $\log^2n = O(n)$ and
2. $ n = O(\log^2n)$

are true or if one or both are false.

So far I've concluded that both are false because if $n = 8$ for the first one, then $\log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$.

For the second one, I believe it to be false as well because if $n = 1024$ or (some other big number), you get $1024 = O(\log^2 1024)$ which simplifies to $1024 = O(100)$. And 1024 does not belong to $O(100)$.

Am I right or is one of these true? Thanks.

# Answer
> 6 votes
You're right about the second one, but your reasoning for both is sketchy. The definition of $f(n)=O(g(n))$ is that there exist constants $c,N$ both greater than zero such that $f(n)\le c\cdot g(n)$ for all $n\ge N$.

Trying a single value for $n$ won't generally give anything in the way of an answer. Consider, though, the intuition we get from trying $n=4, 8, 16, 32, \dotsc$: $$\begin{array}{lcccc} n: & 4 & 8 & 16 & 32 & 64 & 128\\ \log^2 n: & 4 & 9 & 16 & 25 & 36 & 49 \end{array}$$

It seems to be the case that $n$ grows much faster than $\log^2n$. In fact, for this example we have that at least for powers of 2, $\log^2(n)=\log^2(2^k)=k^2\le 1\cdot2^k=1\cdot n$ for all $n \ge 16$, so we might suspect that $\log^2n=O(n)$, which is indeed the case, as it happens.

What is most helpful is to get an intuition of the big-O relationship between frequently-used functions. Here are some examples (all of which should be proved, but that'll be up to you do do or look up). Assuming everything in sight is positive, then:

1. $\log n = O(n^k)$ for any $k\>0$. (polynomials beat logs, eventually)
2. If $a \le b$, then $n^a=O(n^b)$. (polynomials behave as expected, by degree)
3. If $a\>1$, then $n^k=O(a^n)$. (exponentials beat polynomials)

and so on. The point here is that it's far better to develop your intuition and only use the definition of big-O when faced with a problem where intuition doesn't give you any help. That's what the experts do.

---
Tags: asymptotics, landau-notation
---


title: Variation of the Partition Problem

text:
# Question
Title: Variation of the Partition Problem
Is the variation of partition problem where instead the sum of the sets only be equal to a value $B$, they could also differ by two ( i.e., the sum of one set could be $B-1$ and the other $B+1$ ) still $NP$-complete?

# Answer
Yes.  To reduce the ordinary partition problem to this variant, just multiply each element by 3. Now, the case where the weights of the two partitions differ by two cannot arise so, if the instance is a yes instance, it must be because there's an equal-weight partition.
> 2 votes

---
Tags: np-complete
---


# Question
Title: Problems that don't have polykernel when parametrized by vertex cover
Are there any problems **apart from chromatic number**, which is $FPT$ when parametrized by (the size of a minimum) vertex cover, and that does not admit a polykernel when parametrized by (the size of a minimum) vertex cover (under standard complexity assumptions)?

# Answer
Yes, consider the clique problem (W\[1\]-hard for the parameter solution size). The problem is FPT when parameterized by the vertex cover number: any clique can contain at most one vertex outside the vertex cover, so it is enough to look at only $2^\tau(n-\tau+1)$ possible solutions, where $\tau$ is the vertex cover number.

On the other hand, the clique problem has no kernel of polynomial size (unless $\text{NP} \subseteq \text{coNP/poly}$). See e.g. the arXiv version

Bodlaender, Hans L., Bart MP Jansen, and Stefan Kratsch. "Cross-composition: A new technique for kernelization lower bounds." arXiv preprint arXiv:1011.4224 (2010).

The same is true for weighted feedback vertex set according to the paper.
> 2 votes

---
Tags: algorithms, algorithm-analysis, parameterized-complexity
---


# Question
Title: Union and intersection of a regular and a non-regular language
Lets say we have $L\_1$, which is a regular language and $L\_2$ which is not. Are $L\_1 \cap L\_2$, $L\_1 \cup L\_2$ , $L\_1$ \ $L\_2$ and $L\_1 \cdot L\_2$ are always non-regular languages?

We know that two regular languages always gives us a regular language under all of the above. I can't find anywhere any proof that combination of two languages, one regular and one non-regular results always in a regular or a non-regular language. It seems for me that it should be a non-regular in all above cases. Am I wrong?

# Answer
Note that the languages $\emptyset$, $\\{\epsilon\\}$ and $\Sigma^\*$ are regular. Let $L\_2$ be any non-regular language over $\Sigma$.

**Union.** $\emptyset \cup L\_2 = L\_2$, which is non-regular; $\Sigma^\*\cup L\_2 = \Sigma^\*$, which is regular.

**Intersection.** $\Sigma^\*\cap L\_2 = L\_2$; $\emptyset\cap L\_2 = \emptyset$.

**Subtraction.** $\Sigma^\*\setminus L\_2 = \overline{L\_2}$, which is non-regular, since regular languages are closed under complementation. That is, if $\overline{L\_2}$ were regular, then $\overline{\overline{L\_2}}=L\_2$ would also have to be regular. $\emptyset\setminus L\_2 = \emptyset$, which is regular.

**Concatenation.** $\\{\epsilon\\}\cdot L\_2 = L\_2$; $\emptyset\cdot L\_2 = \emptyset$.
> 21 votes

# Answer
Let $L\_1$ be a regular language and let $L\_2$ be an irregular language.

We are going to prove that your intuition($L\_1 \cup L\_2$, $L\_1 \cap L\_2$, $L\_1 \setminus L\_2$, $L\_1 \cdot L\_2$ are always irregular) is false using counterexamples.

1)For $L\_1 \cup L\_2$ consider the following counterexample:

$L\_1= \mathscr{L}(a^\*b^\*)$ and

$L\_2=\\{a^nb^n |n \geq 0\\}$

$L\_1\cup L\_2= L\_1$

2)For $L\_1 \cap L\_2$ consider the following counterexample:

$L\_1= \mathscr{L}(c^\*)$ and

$L\_2=\\{a^nb^n |n \geq 0\\}$

$L\_1\cap L\_2=\emptyset$

3)For $L\_1 \setminus L\_2$ consider the following counterexample:

$L\_1= \mathscr{L}(c^\*)$ and

$L\_2=\\{a^nb^n |n \geq 0\\}$

$L\_1\setminus L\_2= L\_1$

4)For $L\_1 \cdot L\_2$ consider the following counterexample:

$L\_1= \emptyset$ and

$L\_2=\\{a^nb^n |n \geq 0\\}$

$L\_1 \cdot L\_2= L\_1 = \emptyset$

Finally we can't guarantee that the union. intersection, subtraction or concatenation of this languages are irregular always.
> 5 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Has the graph isomorphism problem been solved?
Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not sophisticated enough to follow the reasoning in the paper.

I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.

So, is the graph isomorphism problem solved?

# Answer
No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm.

As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.
> 24 votes

# Answer
No, the graph isomorphism problem has not been solved. The paper you link to is from 2007–2008, and hasn't been accepted by the wider scientific community. (If it had been, I would have known about it.)

Graph isomorphism, like many other famous problems, attracts many attempts by amateurs. They are almost always wrong. I would advise against trying to tackle this problem without first becoming competent in research-level mathematics.
> 18 votes

# Answer
I would be very dubious that it has (in the sense of the proof of existence of a polynomial time algorithm). While it is not impossible that the paper is correct, there are a number of warning signs:

1. The author has not published the result in a peer reviewed venue (even after 7 years).
2. The author does not seem to have published anything else, anywhere.
3. The paper presents the algorithms, but the claim of correctness is an informal handwaving argument about the complexity.
4. For a problem that has resisted the attempts of some very clever people, the maths in the paper is too simple.
5. The author doesn't appear to be affiliated with an academic institution. The new version of the paper clarifies this.

Again, without someone identifying a flaw in the paper, these are not fool proof signs. Maybe the author had a unique flash of insight and then moved on to a completely different life, but the weight of probability is against it - extraordinary claims require extraordinary evidence.

To elaborate on (4) given recent news, László Babai recently claimed a major improvement on known graph isomorphism algorithm (no preprint yet, but a decent running commentary on his public lecture can be found here), giving a pseudo-polynomial time algorithm. Babai and his colleagues are definitely very smart people, and the mathematics used to obtain this result is difficult, deep and spans graph theory and group theory. Given the weight of probability, this is the expected level for a significant advance on a problem like this.
> 8 votes

# Answer
Laszlo Babai has claimed to have found a quasipolynomial solution for the graph isomorphism problem as of November 11th 2015.

... and retracted the claim yesterday (4/1/2017):

Source: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/
> 4 votes

---
Tags: complexity-theory, reference-request, time-complexity, graph-isomorphism
---


# Question
Title: Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable?
I have two questions as in the title:

1. TM M accepts some string of length greater than 100
2. TM M accepts some string of length at most 100

Since 1. is infinite, we can rephrase question as "does TM accept a string", which is clearly undecidable and there are many proofs for that.

2nd question on the other hand is finite and all finite languages are decidable.

Is my reasoning correct? I can't find any confirmation of my theories.

# Answer
I might be wrong ( ignore if you understand it correctly, I am beginner myself ), but I think you are misunderstanding the Rice Theorem. Broadly speaking any non-trivial property of the *languages* recognized by Turing machines is not decidable. A property is trivial if it holds for all or for none of the languages recognized by Turing machines. There are various posts explaining/regarding the theorem. For example I referred to the answer here How to show that a function is not computable? while learning the theorem. ( Skip to end if you only needed hint )
Coming to your case, the languages are $L\_1=\\{\langle M \rangle \\;| \\; \text{M accepts some string of length greater than 100} \\}$ and $L\_2=\\{\langle M \rangle \\;| \\; \text{M accepts some string of length less than equal to 100} \\}$
It is not difficult to see that in both the cases you are trying to decide non-trivial properties and thus both $L\_1$ and $L\_2$ are *undecidable*. As for your reasoning it is flawed as I commented, because knowing that size of a language is finite and being able to construct a Turing machine deciding it, is different from being able to decide whether an arbitrary Turing machine recognizes a language of finite size.
On a side note you could have approached the problem by first seeing that if both of the languages were decidable, the halting problem would become decidable which we no is not true.
> 2 votes

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?
I've seen circuit level implementations of ALU's before, but how are NOT/AND/ADD performed **mechanically**?

# Answer
Babbage's arithmetic unit (ALU) for the Analytical Engine was originally called the mill. It wasn't constructed out of binary logic gates (AND, OR, NOT). Instead it works on the basis of counting gear teeth and escapements.

The mill is essentially an entire Difference Engine designed to be mechanically controllable/programmable (rather than needing humans to set the input gears to the correct number). The Difference Engine is much more primitive than what we would call a "calculator" today. It is bascially a mechanical abacus. Only, instead of beads it represents numbers by the rotation of gears.

I haven't tried building one so can't quite tell you the exact detail of how it works but in general it works like this:

1. Two rows of input gears are spun to set it to two numbers.
2. The gears are connected together in such a way that when you rotate them one "cycle" both will rotate another row of output gears to produce a result. Note that a "cycle" literally means what it means - there is a crank on one end of the machine that you rotate with your arms one round to get the result.
3. The operation can either add the sum of the input gears or it can subtract one input from another.

That's all it can do, nothing else.

Given that it can do addition and subtraction, and given that we can calculate multiplication by repeated addition and division by repeated subtraction, we can perform any calculation.

In reality Babbage optimized his mill to do more than simply add or subtract (though, the machine can indeed do that). The gears are stacked on top of each other with the output of each stage being used as input for the next stage to calculate polynomials (somehow, I don't know the details). So you can arrange the output rows to represent multipliers in a polynomial equations and you can cycle the mill `x` number of times to get the result for `f(x)`. But that's more to do with the Difference Engine. The mill for the Analytical Engine could do less specialized calculations.

So Babbage didn't design his "logic" the way a digital designer would design a circuit. He designed it the way a Swiss watch maker would design a complex feature for a handcrafted watch (moon phase display for example).
> 5 votes

# Answer
If your "mechanical" means real mechanical logic gates, this you tube clip may help you: https://www.youtube.com/watch?v=XBqleRTjDno&app=desktop.

This clips shows how to build a half adder with LEGO: https://www.youtube.com/watch?v=5X\_Ft4YR\_wU
> 1 votes

# Answer
Mechanical arithmetic existed before Babbage. That's the "easy" part. The hard part is implementing a mechanical control unit. That's why the Analytical Engine was so ahead of its time.
> 1 votes

# Answer
a video of a working version built in 2008 in the Computer History Museum, at: http://www.computerhistory.org/babbage/
> -1 votes

---
Tags: logic, computer-architecture, arithmetic, history
---


# Question
Title: Shortest path that visits maximum number of strongly connected components
Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.

# Answer
> 3 votes
For ease of writing, I'm going to say "component" instead of "strongly connected component." This should cause no confusion, since it's the only kind of component we're interested in.

Let $G$ be your directed graph. Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$. Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.

Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink. So, we need to find the longest paths in $H$. We can't just produce a list of them because there might be exponentially many. So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.

* Topologically sort the vertices.
* Set $\ell(x) = 0$ for each sink $x$.
* Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\\,\\{\ell(y\_1), \dots, \ell(y\_k)\\}$ for each vertex $x$ with out-neighbours $y\_1, \dots, y\_k$.

Note that the topological ordering guarantees that we've already computed $\ell(y\_i)$ for each out-neighbour $y\_i$. When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.

Now, produce a graph $H'$ from $H$ as follows.

* Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
* Let $m = \max\\,\\{\ell(x)\mid x\text{ is a source in }H\\}$ (this is the length of the longest path in $H$).
* Iteratively delete every source $y$ with $\ell(y)\<m$.

$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$). In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.

Now, produce a graph $G'$ from $G$ as follows.

* Delete from $G$ any component $C$ such that $h(C)\notin H'$.
* Delete from $G$ any edge from component $C\_1$ to component $C\_2$ if there is no edge $(h(C\_1),h(C\_2))$ in $H'$.

Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$. The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.

Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.

---
Tags: algorithms, graphs, shortest-path, graph-traversal
---


# Question
Title: If the universe were predetermined, would non-deterministic automata still make sense?
If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense? Or would it not, but we wouldn't know it?

# Answer
It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them.

For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form *"as long as the set is not empty, take out an element and compare it with the current max value"*. This algorithm is non-deterministic because I did not explain how one chooses what element to pick. I did not explain it because it is not important for the correctness of the method (and because deciding in advance how to pick an element would blur the issues and limit the scope of my algorithm).

Note that, in all likelihood, all actual implementations of the algorithm will run deterministic code. But it is useful for me to think in term of the more abstract, more generic, non-deterministic algorithms. You may give it a different name but non-determinism is an essential concept.

Here is another way to see that non-determinism in mathematical models is not related to non-determinism in the actual world : your question is similar to me asking *if the universe is governed by predeterminism, does the $P\not=NP$ question make sense?*
> 8 votes

# Answer
Nondeterministic automata would make perfect sense in a predetermined universe, because, in the sense it is used in computer science, "nondeterministic" does not mean "not predetermined."

In particular, the acceptance criterion of nondeterministic machines is defined in terms of the existence of a path of a particular kind through the state transition graph. The definition of the state transition graph doesn't depend on whether or not the universe is predetermined and nor doest the existence of any particular path through it. So the definition of nondeterministic computation doesn't depend on whether or not the universe is predetermined.

phs mentiones the P-vs-NP question and that's a good example. Again, regardless of whether the universe really is predetermined, it makes perfectly good sense to ask, "Are there problems where it's easier to check an answer than to produce one?" That question doesn't mention nondeterminism explicity but it turns out that nondeterminism, in the sense that the term is used in computer science, is central to it.
> 8 votes

---
Tags: automata, nondeterminism, philosophy
---


# Question
Title: Significance of including $S \to ε$ production rule in regular grammar?
Why a production rule $S\to ε$ has been included in the definition of regular grammar? In that case, why it is restricted for $S$ (start symbol) to be present on right hand side of any production rule?

# Answer
> 5 votes
This production rule allows the grammar to generate the empty string. We restrict it to the start symbol so that it can fulfill its function but not interfere with the properties of the grammar in any other way.

In short, it's a hack to allow regular grammars to generate the empty string.

---
Tags: formal-languages, regular-languages, formal-grammars
---


# Question
Title: Mapping reducibility vs. Turing reducibility
Let $A$ and $B$ be two languages. If $A \le\_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A \le\_{T} B$, then if $B$ is decidable so is $A$. But I can't say the same thing for recognizability which I can see by example when $A \equiv L\_{\phi}$ ( the empty language ) and if $B \equiv A\_{TM}$ ( acceptance language ). I know this is because of the fact that we assume the orcale to *decide* $B$ while proving $A \le\_{T} B$. Why is it so that we assume the oracle to decide and not recognize $B$ while comparing relative difficulty of two two languages ? Sorry for vague terminology of *relative difficulty*, I have not yet begun reading about complexity theory and hierarchies and for now only have a vague idea about it.

# Answer
You can define a notion of reducibility which will ensure that if $A$ reduces to $B$ and $B$ is recognizable then so is $A$. The definition allows an oracle call to $B$, but the semantics are different: if the contents of the oracle tape are in $B$ then the machine continues, and otherwise it gets stuck (never halts).

The problem with this definition is that it is pretty weak. While the other property (with recognizability replaced by decidability) still holds, it never helps you that $B$ is decidable. Compare this with mapping reducibility: there you are using the full power of decidability.

Still, the definition could be useful. Assuming you aren't the first to come up with this idea, the only conclusion is that this definition doesn't lead to a nice enough theory. It's also possible that you came up with a nice concept which you could develop to a nice theory. A third possibility is that a theory has been developed, but I am unaware of it.
> 2 votes

---
Tags: computability, reductions, semi-decidability
---


# Question
Title: Can a vectorized computation always be parallelized?
If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, Mathematica, Matlab, or seek clarification.

Are there situations when a **vectorized** (aka *element-wise application of a function* or *array programming* (AP)) computation cannot be **parallelized**?

When coding, I frequently replace loops with a vectorized computation, if possible. At times, it's an interesting exercise or (arguably) makes the code more readable. Other times, in hopes of parallelizing it in the future, if need be.

Is there a constraint that would prevent me from parallelizing a vectorized code.

**Vectorization example** Note that even seemingly tight loop can be vectorized. For example, cumulative sum of vector elements `(1, 2, 3)` can be transformed to a matrix form `((1,1,1),(0,2,2),(0,0,3))` and then vectorization is done as column sums producing the desired `(1,3,6)` cumulative sum. However, vectorization of fibonacci sequence is unlikely(?).

Many thanks for your explanations and references.

# Answer
> 2 votes
If there are dependencies between loop iterations, then the loop cannot be parallelized. Depending upon the precise definition of "vectorized" you have in mind, your definition might imply that there are no dependencies -- or it might not.

Some examples:

```
foreach i in S:
    B[i] = f(A[i])

```

is parallelizable if `f` is a pure function and `A,B` don't alias (have no overlap). (But it is in general not parallelizable if `f` writes to global state or performs any kind of I/O.) More generally

```
foreach i in S:
    B[i] = f(i, x, y, ..)

```

is parallelizable if `f` is pure and does not access `B` (for reading or writing) and none of the arguments alias `B`. However,

```
foreach i in S:
    B[i] = B[A[i]]

```

is not parallelizable, as there are dependencies between loop iterations. (At least, it is not trivially parallelizable, if `A` is not known at compile time.)

I've written using `foreach` syntax but you can translate each example to `map` or `apply` and the same comments apply.

---
Tags: parallel-computing, performance, loops
---


title: What is dynamic programming about?

text:
# Question
Title: What is dynamic programming about?
Sorry in advance if this question sounds dumb...

As far as I know, building an algorithm using dynamic programming works this way:

1. express the problem as a recurrence relation;
2. implement the recurrence relation either via memoization or via a bottom up approach.

As far as I know, I have said everything about dynamic programming. I mean: dynamic programming does not give tools/rules/methods/theorems for expressing recurrence relations, nor for turning them into code.

So, what's special about dynamic programming? What does it give you, other than a vague method for approaching a certain kind of problems?

# Answer
> 32 votes
Dynamic programming gives you a way to think about algorithm design. This is often very helpful.

Memoization and bottom-up methods give you a rule/method for turning recurrence relations into code. Memoization is a relatively simple idea, but the best ideas often are!

Dynamic programming gives you a structured way to think about the running time of your algorithm. The running time is basically determined by two numbers: the number of subproblems you have to solve, and the time it takes to solve each subproblem. This provides a convenient easy way to think about the algorithm design problem. When you have a candidate recurrence relation, you can look at it and very quickly get a sense of what the running time might be (for instance, you can often very quickly tell how many subproblems there will be, which is a lower bound on the running time; if there are exponentially many subproblems you have to solve, then the recurrence probably won't be a good approach). This also helps you rule out candidate subproblem decompositions. For instance, if we have a string $S\[1..n\]$, defining a subproblem by a prefix $S\[1..i\]$ or suffix $S\[j..n\]$ or substring $S\[i..j\]$ might be reasonable (the number of subproblems is polynomial in $n$), but defining a subproblem by a subsequence of $S$ is not likely to be a good approach (the number of subproblems is exponential in $n$). This lets you prune the "search space" of possible recurrences.

Dynamic programming gives you a structured approach to look for candidate recurrence relations. Empirically, this approach is often effective. In particular, there are some heuristics/common patterns you can recognize for common ways to define subproblems, depending on the type of the input. For instance:

* If the input is a *positive integer* $n$, one candidate way to define a subproblem is by replacing $n$ with a smaller integer $n'$ (s.t. $0 \le n' \le n$).
* If the input is a *string* $S\[1..n\]$, some candidate ways to define a subproblem include: replace $S\[1..n\]$ with a prefix $S\[1..i\]$; replace $S\[1..n\]$ with a suffix $S\[j..n\]$; replace $S\[1..n\]$ with a substring $S\[i..j\]$. (Here the subproblem is determined by the choice of $i,j$.)
* If the input is a *list*, do the same as you'd do for a string.
* If the input is a *tree* $T$, one candidate way to define a subproblem is to replace $T$ with any subtree of $T$ (i.e., pick a node $x$ and replace $T$ with the subtree rooted at $x$; the subproblem is determined by the choice of $x$).
* If the input is a pair $(x,y)$, then recursively look at the type of $x$ and the type of $y$ to identify a way to choose a subproblem for each. In other words, one candidate way to define a subproblem is to replace $(x,y)$ by $(x',y')$ where $x'$ is a subproblem for $x$ and $y'$ is a subproblem for $y$. (You can also consider subproblems of the form $(x,y')$ or $(x',y)$.)

And so on. This gives you a very useful heuristic: just by looking at the *type signature* of the method, you can come up with a list of candidate ways to define subproblems. In other words, just by looking at the problem statement -- looking only at the *types* of the inputs -- you can come up with a handful of candidate ways to define a subproblem.

This is often very helpful. It doesn't tell you what the recurrence relation is, but when you have a particular choice for how to define the subproblem, often it's not too hard to work out a corresponding recurrence relation. So, it often turns design of a dynamic programming algorithm into a structured experience. You write down on scrap paper a list of candidate ways to define subproblems (using the heuristic above). Then, for each candidate, you try to write down a recurrence relation, and evaluate its running time by counting the number of subproblems and the time spent per subproblem. After trying each candidate, you keep the best one that you were able to find. Providing some structure to the algorithm design process is a major help, as otherwise algorithm design can be intimidating (there's such a huge space of possible approaches, without some structure it can be unclear how to even get started).

# Answer
> 12 votes
Your understanding of dynamic programming is correct (afaik), and your question is justified.

I think the additional design space we get from the kind of recurrences we call "dynamic programming" can best be seen in comparison to other schemata of recursive approaches.

Let's pretend our inputs are arrays $A\[1..n\]$ for the sake of highlighting the concepts.

1. **Inductive Approach**

Here the idea is to make your problem smaller, solve the smaller version and derive a solution for the original one. Schematically,

$\qquad f(A) = g\bigl( f(A\[1..n-c\]), A \bigr)$

with $g$ the function/algorithm that translates the solution.

*Example:* Finding superstars in linear time
2. **Divide & Conquer**

Partition the input into several smaller parts, solve the problem for each and combine. Schematically (for two parts),

$\qquad f(A) = g\bigl(f(A\[1..c\]), f(A\[c+1..n\]), A\bigr)$.

*Examples:* Merge-/Quicksort, Shortest pairwise distance in the plane
3. **Dynamic Programming**

Consider *all* ways of partitioning the problem into smaller problems and pick the best. Schematically (for two parts),

$\qquad f(A) = \operatorname{best} \Bigl\\{ g\bigl(f(A\[1..c\]), f(A\[c+1..n\])\bigr) \Bigm| 1 \leq c \leq n-1 \Bigr\\}$.

*Examples:* Edit distance, Change-making problem

*Important side note:* dynamic programming is *not* brute force! The application of $\operatorname{best}$ in every step reduces the search space considerably.

In a sense, you know *less and less* statically going from top to bottom, and have to make more and more decisions dynamically.

The lesson from learning about dynamic programming is that it is *okay* to try all possible partitionings (well, it's required for correctness) because it can still be efficient using memoization.

# Answer
> 6 votes
Dynamic Programming allows you to trade memory for computation time. Consider the classic example, Fibonacci.

Fibonacci is defined by the recurrence $Fib(n)=Fib(n-1)+Fib(n-2)$. If you solve using this recursion, you end up doing $O(2^n)$ calls to $Fib(\cdot)$, since the recursion tree is a binary tree with height $n$.

Instead, you want to calculate $Fib(2)$, then use this to find $Fib(3)$, use that to find $Fib(4)$, etc. This only takes $O(n)$ time.

DP also provides us with basic techniques for translating a recurrence relation into a bottom-up solution, but these are relatively straightforward (and generally involve using an $m$ dimensional matrix, or a frontier of such a matrix, where $m$ is the number of parameters in the recurrence relation). These are well explained in any text about DP.

# Answer
> 6 votes
Here is another slightly different way of phrasing what dynamic programming gives you. Dynamic programming collapses an exponential number of candidate solutions into a polynomial number of equivalence classes, such that the candidate solutions in each class are indistinguishable in some sense.

Let me take as an example the problem of finding the number of increasing subsequences of length $k$ in an array $A$ of lenght $n$. It is useful to partition the set of all subsequences into equivalence classes such that two subsequences belong to the same class if and only if they have the same length and end in the same index. All of the $2^n$ possible subsequences belong to exactly one of the $O(n^2)$ equivalence classes. This partitioning preserves enough information so that we can define a recurrence relation for the sizes of the classes. If $f(i, \ell)$ gives the number of subsequences which end in index $i$ and have length $\ell$, then we have:

$$f(i,\ell) = \sum\_{j \< i \textrm{ such that} A\[j\] \< A\[i\]} f(j,\ell-1)$$ $$f(i,1) = 1 \textrm{ for all } i = 1 \ldots n$$

This recurrence solves the problem in time $O(n^2k)$.

---
Tags: algorithms, dynamic-programming, algorithm-design
---


# Question
Title: Practical Implementation for Refinement Order on Integer Partitions
The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda\_1,\dots,\lambda\_k)\leq\mu=(\mu\_1,\dots,\mu\_\ell)$ if there is a partition of the parts of $\lambda$ into blocks whose sums are the parts of $\mu$.

It is known that the problem of deciding whether $\lambda\leq\mu$ is NP-complete. However, for a practical application I would need an algorithm which performs reasonably when $n$ is around $200$. Ideally, this algorithm would already have a (free) implementation...

I tried the following naive approach:

* find the last index $j$ such that $\mu\_j\>\lambda\_1$
* if $\mu\_{j+1} = \lambda\_1$ remove $\mu\_{j+1}$ from $\mu$ and $\lambda\_1$ from $\lambda$ and recurse
* otherwise, for $j\in\\{j,j-1,\dots,1\\}$:
    + subtract $\lambda\_1$ from $\mu\_j$ and reorder to obtain a new partition, and recurse with this partition and the rest of $\lambda$

Although this seems to work reasonably well for many pairs $(\lambda,\mu)$ of partitions of size around $200$, it performs poorly when $\lambda$ has many small parts but is not a refinement of $\mu$.

# Answer
> 3 votes
I suggest you try using integer linear programming. Introduce $k\ell$ zero-or-one variables $x\_{i,j}$, with the constraints

$$\sum\_j x\_{i,j} \lambda\_j = \mu\_i$$

and

$$\sum\_i x\_{i,j} = 1.$$

Feed it to an off-the-shelf ILP solver. If it can find a feasible solution for you, then you know that $\lambda \le \mu$. If it can determine that no solution exists, then you know that $\lambda \not\le \mu$.

---
Tags: algorithms, integers, integer-partitions
---


# Question
Title: How to understand the storing mechanism used in external merge sort
I was reading about `external merge sort` from the wikipedia article link, according to it:

> External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.

Suppose we have a RAM which can only hold `2 chunks` of data and we have `6 chunks` of data to sort. Please see the below diagram:

Since our memory can hold `2 chunks of data` so the first `step 1` sounds plausible since we are sorting only pairs of numbers (5,6), (3,4) (1,2). In the `step 2` we merge the data and now our chunk size is `4`. My question is how do you now load this `4 chunk of data` into memory now? Since your memory cannot accept more than 2 chunks of data then how do you load and sort them? How did you sort while merging chunks of data here? I have visited several links, but not able to understand this concept.

You must be performing some kind of sorting while merging the data as well right?

# Answer
How do you load that entire list into memory? You don't. You have a bit of a misunderstanding about how Merge works, in this setting.

It's tempting to think that Merge should work as follows: load both input lists into memory, in their entirety; merge them; then write the result back out to storage. But that wouldn't work -- we won't have enough memory to load the entire lists into memory.

Instead, Merge works *without* loading either input list into memory all at once. Take a look at the pseudocode for Merge, and you'll see that it only needs to have two list items in memory at a time: one list node from somewhere in the first list, and one from somewhere in the second node. Merge finds which one of those two items is smaller, outputs it, and then loads the next item from the input list it came from. You can see that Merge only needs $O(1)$ memory to merge two sorted lists, even if the sorted lists are stored in external storage -- it never needs to load the input lists into memory in their entirety.
> 1 votes

---
Tags: algorithms, algorithm-analysis, sorting, quicksort
---


title: Unification Functions

text:
# Question
Title: Unification Functions
I need to apply the unification function to unify the following expression:

foo(X,X,Y) and foo(Z,p(Z),w)

So far, I've determined that I must substitute 'w's for occurances of 'Y', making

foo(X,X,w) and foo(Z,p(Z),w)

Then, I can saw X/Z (replaces 'Z' with 'X'), making:

foo(X,X,w) and foo(X,p(X),w)

Now all that's left is making p(X) equivalent to X

My question here is, is it allowed to replace this P(X) with X using the substitution X/p(X)? Or am I going about the question in the wrong pattern?

Thank you!

# Answer
Rather than thinking about this in terms of substitutions, you might find it useful to think about this in terms of equalities that you can infer.

In the first step, you inferred that $w=Y$.

In the second step, you inferred that $X=p(Z)$.

In the third step, you inferred that $X=Z$.

It follows that you can infer $Z=p(Z)$. So we know $X=Z=p(Z)$ and $w=Y$.

Of course, if you can infer that two things are equal, you can substitute one for the other. But maybe it's easier to think about unification as being a way to keep track of which things are equal (which in turn helps you know which substitutions you can make). Hope this helps make this kind of situation feel more intuitive.
> 1 votes

---
Tags: artificial-intelligence, unification
---


# Question
Title: Are some Integer programming formulations completely useless for relaxation?
I was tasked with constructing an integer programming formulation for an **NP**-hard problem, and then with specifying its LP relaxation and the resulting approximation factor.

The problem is that, while my integer programming formulation is correct and clever (I like to think), it seams that its relaxation is completely useless. In fact, the LP relaxation seams like it would always lead to the worst possible solution to the original problem.

Is this possible? Is there some known way of deriving a proof that an LP relaxation of an IP problem can only be so good, some way of telling you when to quit looking?

# Answer
> 5 votes
Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing *integrality gaps*. For a minimization problem, an integrality gap of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding mechanism cannot guarantee an approximation ratio better than $k$.

As a simple example, consider the relaxation of the vertex cover IP $x\_i + x\_j \geq 1$ for every edge $(i,j) \in E$ (the variables are $x\_i$ for every vertex $i$, and they are constrained to lie in $\[0,1\]$). A *triangle* has minimum vertex cover 2, but the LP has a solution with value only 3/2 (namely, all vertices get the value 1/2). This is an integrality gap of 4/3. There are more complicated integrality gaps of $2-\epsilon$ for every $\epsilon \> 0$.

---
Tags: linear-programming, integer-programming
---


# Question
Title: Use dynamic programming to find a subset of numbers whose sum is closest to given number M
Given a set $A$ of $n$ positive integers $a\_1, a\_2,\ldots, a\_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying to find a subset $A′$ of $A$ such that the absolute value $|M - \sum\_{a∈A′}a|$ is minimized. I only need to return the sum of the elements of the solution subset $A′$ without reporting the actual subset $A′$.

For example, if we have $A$ as $\\{1, 4, 7, 12\\}$ and $M = 15$, then the solution subset is $A′ = \\{4, 12\\}$, and thus the algorithm only needs to return $4 + 12 = 16$ as the answer.

The dynamic programming algorithm for the problem should run in $O(nK)$ time in the worst case, where $K$ is the sum of all numbers of $A$.

# Answer
Hint: Use the classical dynamic programming algorithm to find *all* sums of subsets, and from that information deduce the sum closest to $M$.

You can actually improve this algorithm in two ways. First, you can improve the running time to $O(n\min(K,M))$, using the fact that the optimal sum is at most $2M$ (why?). Second, you can also find the optimal set $A'$ itself within the same time bound: just use the very same technique used to accomplish that for the usual SUBSET-SUM.
> 0 votes

---
Tags: dynamic-programming, knapsack-problems
---


title: Partitioning any language to regular?

text:
# Question
Title: Partitioning any language to regular?
One time I saw a theorem that says something like any language can be partitioned into regular languages, but I can't remember exactly what the theorem is. Could somebody tell me, is this true? What is this theorem?

# Answer
> 5 votes
Every language can be partitioned into a countable union of singleton languages (languages of the form $\\{w\\}$). Since singleton languages are regular, we get that every language can be partitioned into infinitely many regular languages.

# Answer
> 5 votes
Myhill-Nerode. A language $L$ is regular iff it is the union of equivalence classes of a right-invariant equivalence relation $E$ of finite index.

This is slightly more general than the statement given on wikipedia where $E$ is taken to be a fixed equivalence $E\_L$ determined by $L$ as follows: for two strings $x,y$ we have $x\\,E\_L\\, y$ whenever, for every string $z$, $xz\in L$ iff $yz\in L$. Meaning $x$ and $y$ cannot be distinguished by extending them in the same way.

---
Tags: formal-languages
---


# Question
Title: Number of possible search paths when searching in BST
I have the following question, but don't have answer for this. I would appreciate if my method is correct :

Q. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root node containing the value 60?

(A) 35 (B) 64 (C) 128 (D) 5040

From the question, I understand that all nodes given have to be included in traversal and ultimately we have to reach the key, 60. For example, one such combination would be :

10, 20, 40, 50, 90, 80, 70, 60.

Since we have to traverse all nodes given above, we have to start either with 10 or 90. If we start with 20, we will not reach 10 (since 60 \> 20 and we will traverse right subtree of 20)

Similarly, we cannot start with 80, because we will not be able to reach 90, since 80\>60, we will traverse in left sub tree of 80 & thus not reaching 90.

Lets take 10. The remaining nodes are 20, 40, 50, 70, 80, 90. Next node could be either 20 or 90. We cannot take other nodes for same earlier mentioned reason.

If we consider similarly, at each level we are having two choices. Since there are 7 nodes, two choices for first 6 & no choice for last one. So there are totally

$2\*2\*2\*2\*2\*2\*1$ permutations = $2^6$ = $64$

1. Is this a correct answer?
2. If not, whats the better approach?
3. I would like to generalize. If $n$ nodes are given then total possible search paths would be $2^{n-1}$

# Answer
If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order.

Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller numbers are) and we never meet numbers larger than $K$. Hence the numbers 90, 80, 70 must occur along the search in that order.

The sequences 10, 20, 30, 40, 50 and 90, 80, 70 can then be shuffled together, as long as their subsequences keep intact. Thus we can have 10, 20, 40, 50, 90, 80, 70, but also 10, 20, 90, 30, 40, 80, 70, 50.

We now can compute the number, choosing the position of large and small numbers. See the comment by Aryabhata. We have two sequences of 4 and 3 numbers. How many ways can I shuffle them? In the final 7 positions I have to choose 3 positions for the larger numbers (and the remaining 4 for the smaller numbers). I can choose these in $7 \choose 3$ ways. After fixing these positions we know the full sequence. E.g., my first example has positions S S S S L L L the second has S S L S L L S.

You ask for a generalization. Always the $x$ numbers less than the number found, and the $y$ numbers larger are fixed in their relative order. The smaller numbers must go up, the arger numbers must go down. The number is then $x+y \choose y$.

PS (edited). Thanks to Gilles, who noted that 30 is not in the question.
> 18 votes

# Answer
We will convert Moves to Text. It is given that During Search we have Traversed these nodes

as it can be seen that Red ones are bigger than 60 and blue ones are smaller than 60.

Path to node 60 has involved those nodes. So, one of the possible solution to the problem is $$\\{S,S,S,S,L,L,L\\}$$ any other solution will contains these moves only. coz at a time on a node we can get directions as S or L on comparison and since its given that those nodes were encountered it means directions were picked from that set.

Hence, total number of possible solutions = all Permutations of that set, which is given by $$\frac{7!}{4! \times 3!} = 35$$ answer = **option A**
> 1 votes

---
Tags: data-structures, combinatorics, binary-trees, search-trees, graph-traversal
---


# Question
Title: Equivalence relations with $\cap$, $\cup$ and $\circ$
I have the relations $E\_1$ and $E\_2$.

A reflexive, symmetric and transitive property shows that two relations are equivalent to each other. I need to prove if this is true for the following

a) $E\_1 ∩ E\_2$

b) $E\_1 ∪ E\_2$

c) $E\_1 ∘ E\_2$

I found out that a) is true, but I am not sure about it. This is my proof for transitivity:

$E\_1 ∩ E\_2 ⇒ (a, b, c) ∈ E\_1 ∧ (a, b, c) ∈ E\_2 ⇒ \\\((a, b) ∈ E\_1 ∧ (b, c) ∈ E\_1 → (a, c) ∈ E\_1) ∧ ((a, b) ∈ E\_2 ∧ (b, c) ∈ E\_2 → (a, c) ∈ E\_2)$

Also I found different arguments on the internet, so I'm pretty unsure about this.

Regarding b) $E\_1 ∪ E\_2$ a friend found out that this is not transitive and they wanted to prove it with an example. The example is the following:

$A = \\{1,2,3\\}$

$E\_1 = \\{(1,2), (2,1), (2,2)\\}$

$E\_2= \\{(1,3), (3,1), (3,3)\\}$

$E\_1 ∪ E\_2 = \\{(1,2), (2,1), (2,2), (1,3), (3,1), (3,3)\\}$

This is transitive, isn't it? If not, what is it what I did not understand?

And maybe you can help me with with c), as well.

# Answer
> 1 votes
Here are some hints:

a) If $E\_1,E\_2$ are equivalence relations then so is $E\_1 \cap E\_2$. The proof is just by "unpacking" the definitions. (More generally, every class defined by universal statements – those of the form $\forall x\_1,\ldots,x\_n \phi(x\_1,\ldots,x\_n)$ – is closed under intersection.)

b) When trying to prove that $E\_1 \cup E\_2$ is transitive, we get stuck in the following case: if $a E\_1 b$ and $b E\_2 c$ then we have to show that $a E\_1 c$ or $a E\_2 c$, though there is no reason to believe that this must be the case. This helps you construct a counterexample.

c) When trying to prove that $E\_1 \circ E\_2$ is symmetric, we get stuck: if $a E\_1 x E\_2 b$ then there is no particular reason that $b E\_1 y E\_2 a$ for some $y$. This helps you construct a counterexample.

---
Tags: mathematical-foundations
---


# Question
Title: Why do we distinguish between term abstraction and type abstraction in System F?
In System F, we distinguish between types and terms. Types are defined by the following BNF:

\begin{align} A, B ::=&~\alpha && \text{(type variable)} \\ &|~A \rightarrow B && \text{(function type)} \\ &|~\forall \alpha. B && \text{(universal quantification)} \end{align}

Terms are defined by the following BNF:

\begin{align} t, u ::=&~x && \text{(variable)} \\ &|~\lambda x : A. t && \text{(term abstraction)} \\ &|~t~u && \text{(term application)} \\ &|~\Lambda \alpha. t && \text{(type abstraction)} \\ &|~t~A && \text{(type application)} \end{align}

Can term abstraction and type abstraction be combined into a single binder? Similarly, for term application and type application? As a programmer, this distinction between terms and types at the term level seems wasteful to me. However, I'm sure that there must be a good reason for it.

# Answer
> 5 votes
Well there should be a distinction between types and terms somehow. If we had a "plus 10" function it wouldn't make any sense to apply it to a type. What is a type plus 10? So we need some kind of type system that differentiates between types and terms. This much is unavoidable. I suspect that this is the brunt of your issue.

But lets try and consolidate things a bit.

$$ \begin{align} t, u ::=&~x && \text{(variable)} \\ &|~\lambda x : A. t && \text{(term abstraction)} \\ &|~t~u && \text{(application)} \\ &|~\lambda \alpha : Type. t && \text{(type abstraction)}\\ \end{align} $$

where Type is a new keyword. Then applications can be type checked to ensure that only terms that have types of the form $\forall a. t$ can have types applied to them and that terms of the form $\lambda x : Type. t$ have type $\forall x. t$

This is however just a rebranding of System-F! All I have done is unified the syntax a bit. This does manage to consolidate application but you might then ask what happens when we say "Type is a Type too!" so that we can have only one kind of abstraction as well. So you might try and define things like this

$$ \begin{align} A, B ::=&~\alpha && \text{(type variable)} \\ &|~A \rightarrow B && \text{(function type)} \\ &|~\forall \alpha. B && \text{(universal quantification)}\\ &|~Type && \text{(type of types)} \\ \end{align} $$

and then try something like this for terms

$$ \begin{align} t, u ::=&~x && \text{(variable)} \\ &|~\lambda x : A. t && \text{(abstraction)} \\ &|~t~u && \text{(application)} \\ \end{align} $$

Now I have introduced some terms I didn't want to! like $\lambda x : Type \to Type. t$. We don't even have the proper machinery to use something like that! So it doesn't seem like we can consolidate much further than our first attempt lest we introduce functions on types which would take us outside of system F! Infact the above move takes us outside of system-$F\omega$ as well! Consider the term $\lambda x : \forall a. a \to Type. t$. That's a dependent type!

If we morph the system into something closer to dependent types we eventually can drop the distinction if we are very carful. Such a system would not be System-F however and thus the distinction is needed as long as we are in System-F.

---
Tags: lambda-calculus, type-theory, functional-programming
---


# Question
Title: What does Godels Incompleteness theorem "true but unprovable" mean?
I have asked this on the "computer science chat" ( vzn tried to explain me ) . I even watched a couple a videos to understand the theorem but still cannot convince myself. The following is the way the Godel's Incompleteness theorem is proved in Sipsers, where it is shown not all true statements are provable:
**Notations, assumptions and preliminaries**

1. The statements being considered are assumed to be in prenex form ( with boolean operations $\neg,\vee,\wedge$ ). The model is $(\mathbb{N},+,\*)$ ie. variables can take values from the set of natural numbers and relations are addition and multiplication. The set of true statements in this model is denoted by $Th(\mathbb{N},+,\*)$. $Th(\mathbb{N},+,\*)$ is shown to be undecidable by reducing $A\_{TM}$ to it. The reduction is given as, on input $\langle M,w\rangle$ construct statement $\psi=\exists c \[ \phi\_{\langle M,w \rangle}\]$, where, $\psi$ is true if and only if $c$ is an accepting computation history of string $w$ given as input to turing machine $M$.
2. Proof of a statement $\phi$ is ( loosely speaking ), a sequence of statements, $S\_1, S\_2, . .. ,S\_i$, where $S\_i = \phi$. Each $S\_i$ follows from the preceding statements and certain basic axioms about numbers, using simple and precise rules of implication. The proof a statement is denoted by $\pi$.
3. The language $L=\\{\langle \pi,\phi \rangle | \\; \pi \text{ is a proof for } \phi \\}$ is decidable ie. I can check the correctness of a proof for a statement. The Turing machine deciding $L$ is denoted by $D$.
4. All provable statements are true.
5. $P$ is a Turing machine that takes as input a statement $\phi$ tries to find a proof for it by giving $\langle \pi,\phi\rangle$ as input to $D$ for all proofs $\pi$ and accepting if $D$ accepts $\langle \pi,\phi\rangle$ for some $\pi$ ( if proof does not exist for $\phi$ $P$ does not halt ).

**Proof**
Construct the Turing machine $S$ such that
$S$ = "On input any input

1. Obtain own description $\langle S \rangle $.
2. Construct the statement $\psi=\neg \exists c \[ \phi\_{\langle S,0\rangle} \]$ ( $0$ is some specific input string ).
3. Give statement $\psi$ as input to $P$.
4. If preceding step accepts, accept. If it rejects reject. "

The reasoning given by Sipsers is if $P$ is able to find a proof for $\psi$ it means $S$ will accept $0$, but then statement $\psi$ will be false and a false statement can't have a proof which is a contradiction. The only option is that $P$ does not find a proof for $\psi$, but then $S$ won't halt on $0$ and $\psi$ becomes true. Thus $\psi$ is a true but unprovable statement.
My doubt is, isn't the reasoning given above that $\psi$ is true a proof in itself ? I expected the proof would be of sort where I am able to construct a statement $s$ and prove that neither $s$ nor $\neg s$ is provable. Am I misunderstanding something ? I can improve if my explanation of the problem is incorrect or vague.

**EDIT**

In the proof $\phi\_{\langle S,0 \rangle}$ is a formula with a single free variable $c$, such that the sentence $\exists c \[\phi\_{\langle S,0 \rangle}\]$ is true if and only if there is an accepting computation history $c$ of input $0$ to Turing machine $S$.

# Answer
> 4 votes
Your difficulties are hinting toward Gödel's second incompleteness theorem. The proof system $\Pi$ can formalize most steps in the proof, other than its own consistency – the fact that $\Pi$ cannot prove a statement and its negation. Following exactly this train of though, Gödel showed that a sufficiently strong proof system cannot prove its own consistency.

For more information, I suggest looking up resources on Gödel's second incompleteness theorem.

---
Tags: logic, type-theory
---


title: Is Post Correspondence Problem in NP?

text:
# Question
Title: Is Post Correspondence Problem in NP?
I just read some pages in Sipser's book Introduction to Theory of Computation about Post Correspondence Problem, and I'm thinking that PCP is actually in NP. The certifier is: for an input configuration of pile $$(t\_1/b\_1, t\_2/b\_2,...t\_n/b\_n)$$ concatenating $t\_1, t\_2,...,t\_n$ as a string $t$ and concatenating $b\_1, b\_2, ..., b\_n$ as a string $b$, then compare $t$ and $b$ to see if the two are equal and then conclude that the input is actually a solution to PCP.

# Answer
> 19 votes
The Post correspondence problem is undecidable, and in particular it is *not* in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the PCP *instance*). It turns out that in this case there isn't always a polynomial size solution even when the problem is solvable. In fact, there is no computable bound on the size of a potential solution, since otherwise the problem would be decidable!

# Answer
> 11 votes
Your witness is polynomial in the size of the *solution* not in the size of the input. You have no way of bounding the length of potential solutions. Your proof shows that PCP is recursively enumerable.

---
Tags: complexity-theory, decision-problem, np
---


# Question
Title: How to implement graph search to solve Sudoku puzzle
My teacher pointed out to us during lectures that we could use **Graph Search** to help us solve Sudoku puzzles which has left me puzzled .

I dont see how this is possible as **Graph Search** is mostly about getting from Node A to Node B. He mentioned about how its a directed graph where the nodes correspond to partially completed puzzle

What is the general idea behind using **Graph Search** to solve Sudoku Puzzle

# Answer
A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a vertex is a board configuration and an edge from configuration $a$ to configuration $b$ exists if $b$ is obtained from $a$ by inserting a number in an empty cell of $a$. There are $(9^2)^9$ possible configurations; searching this graph for a solution will take a lot of time but you will find one eventually. Many of the configurations are invalid Sudoku grids so you can eliminate lots of them.

A typical Sudoku solver would search an implicit graph: the solver is not given a graph as input but it is given a procedure to generate candidate configurations given some configuration. One such procedure may be described as:

```
generate_candidates(config) {
  candidates = [] is a list of configs
  for every empty cell (call it C) in config
    for every number in [1..9]
      C = number
        if config is a valid grid
          add copy of config to candidates
}

```

In the implicit graph, the edges are the ones that look like 'config $\to$ candidate' where config is the input to `generate_candidates` and candidate is a configuration generated by `generate_candidates`. Of course you have to generate new candidates from the ones just generated; you keep growing that list of candidates until no more can be generated or you've found a solution.
> 4 votes

# Answer
Let node **A** be start state of sudoku. Suppose, you are in some state $s$ of sudoku, now you can put a number in some square without violating the conditions. At this stage, you don't know if putting such number will yield the final solution or not. You just check that it doesn't violate any conditions *now*. Let the state of sudoku obtained after putting the number be $t$. Put $t$ as a node and put an edge from $s$ to $t$. Continue this process starting from **A**. Your aim is to reach a state in which every square is filled. Look for all such nodes that you have obtained in this graph. Let a set of them be called $S$. In this graph, if **A** has a solution, then there is a path from **A** to some element in $S$. This is the path finding problem but with a modification that destination vertex is not a single node, but rather a set of nodes.
> 2 votes

# Answer
One graph searching technique you can use for solving a Sudoku puzzle is *backtracking*. Suppose you are given a partially filled Sudoku puzzle. Choose some empty cell, and assign 1 to it. Check if there are any conflicts. If so, erase that 1 you just put in, and put in 2. Keep repeating this until you find a number that causes no conflicts. Now repeat this procedure until the puzzle is solved. It is not hard to see you will eventually find a solution using this strategy, because it will in the worst case try all possible ways filling the puzzle.

And when you think of it, the Sudoku puzzle actually *is* about getting from node $A$ to node $B$. In this setting, your node A is the partially filled puzzle given to you initially. Node $B$ is a completely filled puzzle with no conflicts. Choosing an empty cell and assign a value to it (corresponding to the situation described in the first paragraph), means you are moving from $A$ to $A\_2$, where $A\_2$ is a partially solved puzzle. Moving along from here will hopefully make you eventually find $B$, which is a *goal state*. In this way, you can indeed see the puzzle solving process as a directed graph.

You can see backtracking in action here.
> 2 votes

# Answer
One way to solve Sudokus using graph theory:

Construct a graph of 81 (9x9) vertices. These are the squares of the puzzle. Now, for each vertex in the graph; add an edge from all vertices in the same row, the same column and in the same box. Use the "colors" `{1..9}` and color vertices already "filled in" in the puzzle to solve. The problem is now solveable using graph coloring algorithms.

https://en.wikipedia.org/wiki/Graph\_coloring#Greedy\_coloring
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


title: Is {ww^r ww^r} a context-free language?

text:
# Question
Title: Is {ww^r ww^r} a context-free language?
Is the language $L = \\{w w^r w w^r \mid w \in \Sigma^\*\\}$ context-free? ($w^r$ is the reversal of $w$.)

I heard that by using the pumping lemma, we can only prove that a language is not context-free, but can't prove that a language is context-free. I tried the pumping lemma and we can produce the language by repeating $v$ and $x$ by taking first $ww^r$ as $v$ and the second $ww^r$ as $x$ which again belongs to the same language. However I'm not able to build any grammar or build a PDA with one stack. I know that may if someone tries harder than me they may be able to construct it, but I'm thinking this may not be a context-free language. Does anyone have any idea about this language?

# Answer
> 7 votes
It's not context free for the same reason that $L' = \\{w w \mid w \in \Sigma^\*\\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the pumping lemma:

Choose the string $0^p1^p1^p0^p0^p1^p1^p0^p$, (which is $\omega \omega^r \omega \omega^r$ where $\omega = 0^p 1^p$). \[Note 1\] Now any $vwx$ whose length is no greater than $p$ is either entirely within the first half of the string, entirely within the second half of the string, or entirely within the central span of $0^{2p}$. Repeating $v$ and $x$ 0 times -- that is, changing $vwx$ to $w$ -- must make the first half of the string different from the second half, either because only one of the halves is altered, or because changing the suffix of one half and the prefix of the other half renders the two halves distinct. So the result is not in $L$.

Since for any $p$, we can find a string which cannot be pumped, we can conclude that there is no pumping length $p$ for the language. That contradicts the pumping lemma, which states that every context-free language has a pumping length. So the language is not context-free.

---

You can't “take the first $ww^r$ as $v$” because of the restriction that the length of $vwx$ is no greater than the pumping length $p$. So, whatever $p$ is (if it exists) there is some $ww^r$ which is longer, and for the corresponding string $ww^rww^r$ in $L$, $v$ cannot be $ww^r$.

---

### Notes:

1. I could have chosen a shorter string, such as $\omega = 0^m1^n$ where $m\>0, n\>0, 4mn\>=p$. But there are no prizes for parsimony here; the string I chose makes the proof less verbose.

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


# Question
Title: Assumptions when selecting an algorithm or data structure
As I understand it the nature of data access (sequential or random) will determine the optimal algorithm/data structure to use when manipulating data.

What other assumptions need to be checked before selecting an algorithm or data structure for the manipulation of data?

# Answer
You can categorize data structures by their need of memory or processing power. Each rated for writing or reading purpose. Some data structures are optimized for searching, some only for fast storing.

Ask yourself how many data you're going to store. If it's a lot, you have to choose the right algorithm, if not it doesn't really matter.

Another question could be, do you need a growing data structure or just a ring buffer for example.

Regarding data manipulation with algorithms, there is a bunch of considerations to make. With growing data, how much does memory usage, processing power, external storage capacity and access times grow? The big O notation would be a term to refer to. Here too, it's important if your 'manipulation' is reading, searching or writing?

You will find an algorithm or a data structure out there for every use case.
> 1 votes

---
Tags: algorithms, data-structures, applied-theory
---


# Question
Title: $2$-sorted array. How to sort it in minimal number of comparisons ?
It is given array $2$-sorted array $a\[1..n\]$. $2$-sorted denotes that $a\[1\]\le a\[3\]\le...\le$ and $a\[2\]\le a\[4\]\le ..\le$

Obviously we may split array into two sorted arrays and then merge two arrays - it requires $n-2$ comparisons. However I think about lower bound. I believe that $n-2$ is lower bound number of comparisons, but I can't see a way to prove it. Can you give me a clue ?

# Answer
> 4 votes
Hint:Show that the algorithm must compare the following pairs: $$ (a\[1\],a\[2\]), (a\[2\],a\[3\]), (a\[3\],a\[4\]), \ldots, (a\[n-1\],a\[n\]). $$

For each comparison $(a\[i\],a\[i+1\])$, assume that you haven't compares $a\[i\]$ to $a\[i+1\]$ but you have done *all* other comparisons. Show that you still don't know the correct sorted order of the array.

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: Example of height-balanced tree that is not weight-balanced
Following this question : Two definitions of balanced binary trees

I am having a hard time making sense of the proofs provided and I'm looking for an example of a simple binary tree that is *height-balance*d but not *weight-balanced*.

This would mean that we could clearly see the height differences of two sub-trees being more than one while the maximum depth difference of any two leave nodes would never be more than one.

Does such an example exist?

**EDIT:** This question was asked because I misunderstood the *inner-node* concept. I was looking for a tree example where the height of two sub trees differed by more than one while the the maximum depth and minimum depth had a difference of no more than one.

# Answer
> 3 votes
Take a complete binary tree of height 2 (with 7 vertices), and add two children to the two left leaves. The tree is height-balanced but the root is not weight-balanced.

---
Tags: data-structures, binary-trees, search-trees, balanced-search-trees
---


title: Context-free language and undecidable

text:
# Question
Title: Context-free language and undecidable
I am working on my midterm sample problems and got stuck on this one. Is this language undecidable?

$\qquad L = \\{\langle G\_1, G\_2 \rangle: G\_1, G\_2 \text{ are CFG and have strings that can be parsed in both grammars }\\}$

Is this one the same as $L' = \\{\langle G\_1, G\_2 \rangle: L(G\_1) \cap L(G\_2) \ne \emptyset\\}$? My professor said the above problem can be reduced to Post Correspondence Problem but I found it closer to the decidable of $L'$.

# Answer
Yes, they are the same languages: $L=L'$ (at least the way that I understand the definition of $L$). We say that the grammar $G\_1$ can parse a string $x$ iff $x \in L(G\_1)$. It follows that $L=L'$. $L$ is defined in a somewhat informal way; good for you for finding a way to provide a more precise formal statement of it.

Indeed, the problem of deciding whether two CFLs have a non-empty intersection is undecidable, so neither $L$ nor $L'$ is decidable.
> 1 votes

---
Tags: computability, context-free, formal-grammars
---


# Question
Title: Most Efficient Way to Map Generic Input To Generic Output
Lookup tables are one way to map x values to f(x) values. This lets you do computation in advance, and can give a low cost (performance wise) answer to complex calculations when they are needed in performance intensive applications.

Another method to map x values to f(x) values is to use the chinese remainder theorem to encode values into a (often large) number and use modulus to get the values back out

For instance, if the modulus "lookup table" was the number 27, it could encode the values 2,1,0 by using divisors 5,2,3 respectively:

$\begin{array}{c|c} \text{Input (x)} & \text{Math} & \text{Output (f(x))} \\ \hline 0 & 27 \\% 5 & 2 \\ 1 & 27 \\% 2 & 1 \\ 2 & 27 \\% 3 & 0 \\ \end{array} $

(More info on that technique here: http://blog.demofox.org/2015/11/13/hiding-a-lookup-table-in-a-modulus-operation/)

The modulus method seems like it would always be slower and take more memory than a straight lookup table.

Is there a more efficient mapping of input values to output values than just using a table?

I'm interested mainly in efficiency of computation time to pull a result out of a mapping, but memory efficiency is also interesting, as well as efficiency in creating the object to begin with, if anyone has any interesting info on that.

Thanks!

# Answer
> 2 votes
From an asymptotic perspective: No, there's no more efficient mapping than just using a table. Lookup in a table is $O(1)$, and you can't beat $O(1)$.

From a practical perspective: The answer will depend upon the exact application domain. For instance, sometimes using a cache will speed up things (by only a constant factor, but in practice constant factors can help), if the access pattern exhibits some locality. It's impossible to give a general answer without knowing the specifics of the particular way you plan to use the lookup table.

However, no, you shouldn't expect there to be some clever number theory trick to build a faster lookup table. Roughly speaking, a lookup table is as fast as you can get; all that remains is some practical optimizations.

---

Memory efficiency is a different matter, and depends upon the function `f`. Sometimes it can be faster to compute `f(x)` from scratch than to look up `x` in the table. Sometimes, if you've previously computed `f(x')` and if `x'` is "close" to `x`, then you can efficiently compute `f(x)`. It all depends on the function.

---
Tags: computability, encoding-scheme
---


# Question
Title: Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials
I want to find the minimal period of any state of an LFSR (except the initial state of all zeroes) whose characteristic polynomial is the product of two primitive polynomials.

In particular, $f(x),g(x) \in GF(2)\[x\]$ are primitive polynomials of order $n$, and the characteristic polynomial of the LFSR is given by: $$c(x)=f(x)g(x).$$ What is the minimal period of any state of this LFSR, other than the all-zeros state?

I've tried to say that if $c(x)$ is a product of two primitives then it has a period of $$\pi=2^{2n}-1 $$ but my math gets me to $$\pi =2^{n+1}-2$$ What did I do wrong?

# Answer
The states of a LFSR with characteristic polynomial $p(x)$ correspond to elements of the multiplicative group of $GF(2)\[x\]/(p(x))$. The period of a LFSR state is the order of the corresponding group element. So, we can rephrase this as a group theory question, and use facts we know from group theory to answer the question.

The LFSR state with minimal period is exactly the group element $g \in G$ with minimal order, where here $G\_c$ is the multiplicative group of $GF(2)\[x\]/(c(x))$.

The LFSR state with minimal period (other than the all-zeros state) is the group element with minimal order (other than the identity element).

Thus, to find the minimal period you want, you need to find the order of the minimal-order group element of $G\_c$ (other than the identity element $1$).

Assuming $f,g$ have no common factor (i.e., $f\ne g$), the structure of $G\_c$ is $G\_c \cong G\_f \times G\_f$, where $G\_f$ is the multiplicative group of $GF(2)\[x\]/(f(x))$ and $G\_g$ is the multiplicative group of $GF(2)\[x\]/(g(x))$. This follows from an analog of the Chinese remainder theorem.

Let $g\_1$ be the group element of minimal order in $G\_f$, and $g\_2$ the group element of minimal order in $G\_g$. From what we know about the structure of $G\_c$, the group element of minimal order in $G\_c$ is either $(g\_1,1)$ or $(1,g\_2)$. So it suffices to find the group elements of minimal order in $G\_f$ and $G\_g$.

From the fact that $f$ and $g$ are primitive, we know that $G\_f,G\_g$ are cyclic groups of order $2^{n\_f}-1$, $2^{n\_g}-1$, respectively, where $n\_f = \deg f$ and $n\_g = \deg g$. Per Lagrange's theorem, we know that the divisors of $2^n-1$ correspond to the orders of the group elements of $G\_f,G\_g$.

Let $d\_f$ be the smallest divisor of $2^{n\_f}-1$ (such that $d\_f\>1$), and similarly for $d\_g$. Then the group element of minimal order in $G\_f$ will have order $d\_f$, and the group element of minimal order in $G\_g$ will have order $d\_g$. It follows that the group element of minimal order in $G\_c$ will have order $d=\min(d\_f,d\_g)$, and the LFSR state of minimal period will have period $d$.

So, the answer to your question is: the minimal period (other than the all-zeros state) is exactly $\min(d\_f,d\_g)$ where $d\_f$ is the smallest divisor of $2^{\deg f}-1$ (other than 1) and $d\_g$ is the smallest divisor of $2^{\deg g}-1$ (other than 1).
> 1 votes

---
Tags: polynomials, pseudo-random-generators
---


title: Language Reduction for any Language

text:
# Question
Title: Language Reduction for any Language
Given two languages $L\_1$ and $L\_2$, give a language $L'$ that both $L\_1$ and $L\_2$ reduce to.

I'm not quite how to do this. I know the solution is fairly simple. I know I can somehow represent $L'$ in terms of $L\_1$ and $L\_2$. Then I need to create a computable function that maps $L\_1$ to $L'$ and either use the same function, or create a separate function that maps $L\_2$ to $L'$.

# Answer
> 2 votes
**Hint**: Try $L=0L\_1\cup1L\_2$. Can you see how to map $L\_1$ to $L$ and $L\_2$ to $L$? You have to be slightly clever; you might want to use prefixes other than 0 and 1.

---
Tags: computability, reductions
---


# Question
Title: Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular
I'm trying to use pumping lemma to prove that $L = \\{(01)^m 2^m \mid m \ge0\\}$ is not regular.

This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider any pumping decomposition $w = xyz$ such that $|y| \>0$ and $|xy| \le p$.

I'm not sure what to do next.

Am I on the right track? Or am I way off?

# Answer
Hint: You need to consider what all the decompositions $w=xyz$ look like, so what are all the possible things $x$, $y$ and $z$ can be given that $xyz=(01)^p2^p$. Then you pump each one and see whether you get a contradiction, which will be a word not in your language. Each case needs to lead to a contradiction, which would then be a contradiction of the pumping lemma. Voila! The language would not be regular.

Of course, you need to work through the details and consider all the possible splittings.
> 6 votes

# Answer
You have a decomposition $xyz = (01)^p 2^p$ and a length constraint $|xy| \le p$. What does this say about how $x$, $y$ and $z$ can fit in the decomposition? In particular, the pumping lemma allows you to repeat $y$, so your objective is to find some way in which repeating $y$ many times (or removing $y$, sometimes this is simpler) will irremediably perturbate the pattern that defines the language.

There's an obvious boundary in the pattern: the first part contains repetitions of $01$, the second part contains only $2$'s. The interesting thing is where $y$ falls down. Is $y$ always contained in one of these parts, or can it straddle the two?

> Since $|xy| \le p$, $xy$ is entirely contained in the $(01)^p$ part, and $z$ contains all the $2$'s. So if you repeat $y$ one more time, you get a longer first part, but the $2^p$ part remains the same. I other words, $xyyz$ ends with exactly $p$ letters $2$. To finish the proof properly, show that $xyyz$ contains too many letters $0$ and $1$ to fit the regular expression.
> 5 votes

# Answer
Three years later we are going to prove that $L = \\{(01)^m 2^m \mid m \ge0\\}$ with $\Delta=\\{0,1,2\\}$ is not regular by contradiction using closure properties(a faster way than using the pumping lemma).

First we suppose that $L$ is regular. We know that regular languages are closed under inverse homomorphism.

Consider the homomorphism $h:\Sigma^\* \rightarrow \Delta^\*$ with:

$\Sigma = \\{a,b\\}$

$h(a)= 01$

$h(b)= 2$

The inverse homomorphism of $L$ is:

$h^{-1}(L)= \\{a^nb^n| n\geq 0 \\} = L'$

This generate a contradiction because $L'$ is a canonical example of an irregular language so $L$ can't be regular.
> 4 votes

# Answer
I am going to give a non-answer to this question, since this isn't exactly the pumping lemma, but maybe sheds light on what the idea of the pumping lemma is. Here is a basic fact about deterministic finite state automata, which is the essence of the Myhill-Nerode theorem: *If two strings $a$ and $b$ drive the FSA to the same state, then for any $c$, either both of $ac$ and $bc$ are accepted, or neither is.*

Back to your problem, suppose that a deterministic automaton for you language has $n$ states. Then at least two of $(01)^1$, $(01)^2$, $\ldots$, $(01)^{n+1}$, say $(01)^p$ and $(01)^q$ with $p\neq q$, drive the automaton to the same state (this is the pigeon-hole principle). According to the fact, then either both of $(01)^p2^p$ and $(01)^q2^p$ are in $L$ or neither is, which is a contradiciton.
> 3 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---