title: Is the following language context free?

text:
# Question
Title: Is the following language context free?
Is $L = \\{ a^nb^nc^j \mid n \le j\\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.

# Answer
$L$ is not context free. You can use the Ogden's lemma to show it.

I'll use the Wikipedia notation linked above.

For every $p$ take the word $a^pb^pc^p$. For a the marking where only c are marked whatever the decomposition $uxyzv$ you take, $ux^iyz^iv$ will not be in $L$. Four cases: $z\in c^\*$ then it fails for $i=0$ or $z\notin c^\*$ then it fails for $i\>0$. And the symmetric cases for $x$.

Hope it helps.
> 1 votes

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


title: How do convolution matrices work?

text:
# Question
Title: How do convolution matrices work?
How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work from left to right and from up to bottom or from up to bottom first and then left to right?

Why does this kernel (Edge enhance):

turn into this image:

# Answer
Convolution matrix are mean to change your image so you have to treat all the pixels.

For pixels without surrounding pixels there are different way to treat than dependently of the result you expect. You can ignore them and get a smaller image. Put an arbitrary value for their surrounding. Or consider the surrounding being symmetrical to the image.

Since the matrix apply on the image it doesn't mater if you apply it up to bottom, left to right or whatever. Each pixel of the result is computed as a local result of the convolution on the image.

For example for an image $$\begin{pmatrix} a &b&c&d\\ e&f&g&h\\ i&j&k&l\\ m&n&o&p \end{pmatrix} $$ If we discard the surrounding pixels the result of the convolution with you matrix will be :

$$\begin{pmatrix} f-e&g-f\\ j-i&k-j \end{pmatrix} $$

So for your convolution, a pixel $(i,j)$ is defined as $I\_{(i,j)}-I\_{(i,j-1)}$. So this convolution stress the differences between pixels hence show the edges.

I hope its clear.
> 1 votes

---
Tags: matrices, image-processing
---


# Question
Title: NP-complete and polynomial time reduction
A decision problem is NP-complete if it is in NP and all other problems in NP can be reduced to it by a reduction that runs in polynomial time. Why it is important to require that the reduction runs in polynomial time, as opposed to accepting any computable reduction.

# Answer
> 3 votes
If there is no resource bound for the reduction and you want to reduce problem A to problem B then there is a trivial "reduction" algorithm for any computable A - simply compute the answer for problem A.

# Answer
> 1 votes
In order to fully understand this, think about the purpose of reductions. Ideally, given a language (or problem) $L$, you would design an algorithm deciding $L$ and prove that no other algorithm can do better than your algorithm. The latter part implies proving a lower bound for the problem $L$. Designing an algorithm is the easiest part, but proving a lower bounds for most of the problems we care about may be extremely difficult. Indeed, for many problems we have no idea of how to prove a lower bound. So what to do about? Instead of proving a lower bound, we relate the difficulty of problems to each other using reductions, and prove that a problem is a hardest problem in a complexity class through completeness. Reductions are a powerful, and useful surrogate for our inability of proving lower bounds. For $NP-Complete$ problems, no one succeeded until now in proving a polynomial lower bound or proving a super-polynomial lower bound.

We can use reductions in two different ways, either in positive or negatively. For a positive usage example, consider a new problem $L\_1$, reduce it to $L$ that you know already to be in $P$. Now you can conclude that $L\_1 \in P$ as well. This formalizes in some way the idea that $L\_1$ is as easy as $L$. For a negative usage example, reduce $L\_1$ to $L$ that you believe this time not to be in $P$. You may now conclude that $L\_1$ does not belong to $P$ if $L$ does not belong to $P$. This formalizes the idea that $L\_1$ is as hard as $L$. Completeness formalizes the idea that a language $L$ is one of the hardest problems in a complexity class $C$. In order for the previous ideas to work we require that reductions must be "efficient", i.e. polytime.

For the positive usage example given above, if the reduction algorithm were super-polynomial, the entire reasoning would be useless: even knowing a polynomial time algorithm for $L$ (a function $g$) would not help to solve $L\_1$ in polynomial time, since you need to "transform" the polynomial solution for $L$ in the corresponding solution for $L\_1$ via the reduction (a function $f$). If the reduction is super-polynomial, the the compositions $f(g(x))$ and $g(f(x))$ of this two functions are not polynomial.

In particular, for $NP-Complete$ problems, if we find a polynomial time algorithm for one, we automatically have found one for $all$ $NP$ problems. But this only works if we restrict reductions to be polytime computable.

---
Tags: terminology, np-complete, reductions
---


title: Problem Solving in MapReduce Framework

text:
# Question
Title: Problem Solving in MapReduce Framework
I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is appreciated!

# Answer
Mapreduce does not seem to have received significant academic attention and/or widespread enthusiasm nor does it seem to have yet been integrated into much of the large previously-existing literature and theory on parallelism. This is partly due to it being relatively new, but there may be other reasons.

One possible angle: this is apparently not widely acknowledged or recognized but MapReduce seems mainly oriented towards & optimized for what are known as embarrassingly parallel problems where the problem space can easily be partitioned into independent parts requiring virtually no intercommunication, i.e. the "map" step. (this is partly the basis of some criticism of the simplicity of the model as in the Wikipedia article.)

The "reduce" step is a communication-heavy step of merging/combining/aggregating the separate results into a combined structure. \[1\] are slides on the background & structure of typical embarrassingly parallel problems, which classic examples are:

Another angle is that MapReduce has some similarities to the "master-slave" design pattern where the "master" distributes jobs and also handles collecting the results, and some surveys on "master-slave" decomposition of parallel problems may be available.

Embarrassingly parallel problems are also naturally "finely granular" and Mapreduce seems especially suited to "fine-grained" parallelism problems (such that the "fine grains" can be highly distributed over many computing machines). "Fine-grained" parallelism is possibly not studied as much from an academic point of view because its intrinsically theoretically less problematic.

Another angle: it's similar to "Bulk Synchronous Parallel" \[4\]. The reduce step is similar to "barrier synchronization".

A survey from 2006 by academic parallelism experts \[2\] that was meant to be very comprehensive and forward-looking at the time identified 7 widespread "dwarves" or basic parallelism structures found in algorithms (Section 3.2). Conspicuously and surprisingly, none have a MapReduce-like structure; i.e. MapReduce type problems are absent from the survey (but note Monte Carlo methods are one of the "dwarves" and is again regarded as embarrassingly parallel).

This would also tend to support the view that MapReduce is a kind of "toy" parallelism model. *However!* that point is not meant to detract from its widespread usefulness in many applications. Particularly with parallelism there can be great value in simpler models that avoid complexity and thereby also various pitfalls.

\[1\] Embarrassingly parallel overview

\[2\] The landscape of parallel computing: the view from Berkeley

\[3\] Current parallel models for computation tcs.se

\[4\] Is the mapreduce framework a type of BSP tcs.se
> 5 votes

---
Tags: algorithms, reference-request, parallel-computing
---


# Question
Title: How to get expected running time of hash table?
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much for an expected running time. Am I making a mistake here?

# Answer
If you think of $1000$ as a constant, then yes, the running time is terrible. The idea of hash tables is that if the hash table is moderately bigger than the amount of data stored in it, then operations are very fast. Suppose for example that the hash table has size $m = 2n$. Then each operation takes constant time in expectation.

In implementations of hash tables, the hash table expands as more entries are inserted, to ensure that the ratio $\alpha$ is reasonable. Amortized analysis shows that this does not cause a performance hit in terms of the total running time, though individual operations might be slower (this is only a problem if you're writing a real-time application).
> 2 votes

---
Tags: algorithms, algorithm-analysis, hash-tables, hash, probabilistic-algorithms
---


# Question
Title: How to get expected running time of hash table?
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much. Am I making a mistake here?

# Answer
Why not sort the array, then iterate over the sorted array, comparing the current number to the previous number.

n\*log(n) for the sort, n for the iteration = 2n\*log(n)
> 0 votes

---
Tags: data-structures, runtime-analysis, average-case
---


title: Height of a full binary tree

text:
# Question
Title: Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far:

I am considering the worst case of a full binary tree in which each right node has a subtree, and each left node is a leaf. In this case:
$N = 2x - 1$
$H = x - 1$
I am going nowhere trying to prove that $H = O(\log(N))$

Furthermore, we know that leaves l is bounded by $h+1 \<l\<2^h$.
Internal nodes is bounded by $h\<i\<2^{h-1}$.
All this proves is that number of nodes $n=i+e$ is $\<= 2^{h+1} - 1$ i.e. $\log(n) \<= h$. But this does not take me anywhere closer to prove that $H = O(\log(n))$

# Answer
Your claim is incorrect (which might make it really hard to prove...) Indeed, as you describe, you can have a full binary tree of height $O(n)$: Let every right child be a leaf, and every left child have 2 children, until some level in which it has two leaf-children.

It holds that $x-1\in \theta(2x-1)$, and in particular, $x-1\in \omega(\log(2x-1))$, so $H\notin O(\log N)$.
> 4 votes

---
Tags: graphs, combinatorics, binary-trees, trees
---


# Question
Title: Methods for Finding Asymptotic Lower Bounds
I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n\_0$ for the lower bound. I'm using Corman's definition of $\Theta$:

$$\exists c\_1,c\_2\>0\in\mathbb{R}:\forall n\geq n\_0: 0 \leq c\_1 g(n)\leq f(n)\leq c\_2 g(n)$$

Showing the upper bound usually doesn't give me too much trouble, but for the lower bound I allot of times find myself using limits. And even though I'm getting the right answers, I'm a bit worried that my method isn't very rigorous and that maybe I'm doing a bit of hand waving in the process.

For example, problem 2.17 from Skiena's Algorithm Design Manual:

Show that for any $a,b\in \mathbb{R}: b\>0$ that $(n+a)^b = \Theta(n^b)$

In this case I used limits to help find both constants.

For the upper limit I decided to look for some $c$ such that $(n+a)^b \leq c^bn^b$. So taking the $b$th root of each side and dividing by $n$ I have $\frac{n+a}{n}\leq c$ which gives me $1 + \frac{a}{n} \leq c$. For any $a\in\mathbb{R}$, $\lim\_{n\to\infty }1+\frac{a}{n}=1$. If I pick $n\_0\>|a|$, then for $a\<0$ the expression approaches 1 from the left starting arbitrarily close to $0$. If $a\>0$ then the expression approaches 1 from the right starting arbitrarily close to 2. So choosing $c=2$ will satisfy the inequality and we have $c\_2=2^b$.

Now for the lower bound. I'm looking at the same expression except with the inequality pointing the other way. In this case I'm trying to find $n\_0$ and $c$ such that $c\leq 1+\frac{a}{n}$. The value of $n\_0$ has to be greater than $|a|$ because otherwise we would have $c\leq 0$ which isn't allowed. This puts us in the same range of values between $0$ and $2$ approaching 1 from each side. So I choose any $c,n\_0$ such that $n\_0\>|a|$ and $0 \< c\leq 1-|\frac{a}{n\_0}|$. So I could choose $n\_0=3|a|$ and $c=\frac{2}{3}$.

Thus we have $0 \< (\frac{2}{3})^bn^b \leq (n+a)^b \leq 2^bn^b$ for any $n \geq 3|a|$.

**Is there an easier way to do this?**

Normally when looking for upper limit constants where the two functions are of the same magnitude I simply eliminate negative lower order terms and change positive ones into multiples of the highest order term such as :

$$3n^2+15n-5\leq 3n^2+15n^2=18n^2$$

But when looking for the constant for the lower bound I find myself typically resorting to looking at limits. **Is there any kind of short cut to finding the lower bound constant like there is for the upper bound constant?**

# Answer
You can codify your method in the following lemma.

Lemma. If $f(n)/g(n) \rightarrow C$, where $C \> 0$, then $f(n) = \Theta(g(n))$.

The proof is the same as the one you gave. After you prove this lemma once and for all, you can use it forever. That's actually a good way of verifying $f(n) = \Theta(g(n))$.

Note that the converse to the lemma isn't true. For example, let $f(n) = n$ and let $g(n) = \exp\lfloor\log n\rfloor$. The ratio $f(n)/g(n)$ moves inside the interval $\[1,e)$, and in particular does not tend to a constant limit.
> 5 votes

# Answer
Depending what $f$ and $g$ are precisely, you can use l'Hôpital's rule. The description from Wolfram Mathworld is quite good (the Wikipedia leaves out some cases leaving the definitions not quite correct).

In short (for the purposes of algorithmic analysis), if $\lim\_{n\rightarrow\infty} f(n) = \lim\_{n\rightarrow\infty} g(n) = 0$ or $\infty$, then: $$ \lim\_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \lim\_{n\rightarrow\infty}\frac{f'(n)}{g'(n)} $$ (as long as $\lim\_{n\rightarrow\infty}\frac{f'(n)}{g'(n)}$ exists)

So as long as you have fairly normal functions for your running time, and you remember some calculus, you can repeatedly apply this rule to determine whether $\lim\_{n\rightarrow\infty}\frac{f(n)}{g(n)} = c$ for some constant $c$.

As a side note, the other cases still apply, so you can apply l'Hôpital's rule until you get one of three cases, the limit is $0$, $\infty$ or a constant, concluding that $f(n)\in O(g(n))$, $f(n)\in\Omega(g(n))$ or $f(n)\in\Theta(g(n))$ respectively.

The same caveat on the converse that Yuval mentions is of course still true here.

Raphael also gives some important limitations on using l'Hôpital with discrete functions (in that strictly you can't). See his comments here.
> 2 votes

---
Tags: asymptotics, landau-notation, lower-bounds
---


# Question
Title: Mutual information and moment generating functions
I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough knowledge to understand what it means. Then, I did some research but I still have some confusion. I am wondering if someone who has more knowledge about this can clarify things for me. Here are my questions:

* Mutual information is usually calculated by bin functions to estimate the probability of two random variables which can be a case of two vectors $X$ and $Y$. Is the moment generating function another way to estimate probability?
* If moment generating functions can present the probability of $X$ and $Y$, how do we calculate it?
* Does a MI have a moment generating function?
* If MI has a moment generating function, how can we present a MI of $X$ and $Y$ by its moment functions?

# Answer
> 6 votes
The moment generating function $M\_X$ is a property of a random variable $X$. It's defined by the expected value of $e^{tX}$ (where $t$ is the argument).

Since the exponential function $e^x = \sum\_0^\infty \frac{x^n}{n!}$ contains all natural powers of its argument as a summand, the expected value of a sum is the sum of the expected values ($\mathbb{E}(\sum\_i X\_i)=\sum\_i\mathbb{E}(X\_i)$) and the expected value of a natural power of $X$ ($\mathbb{E}(X^n)$) is called it's $n$-th moment, the $n$-th moment is present in the $n$-th summand:

$$M\_X(t)=\mathbb{E}(e^{tX})=\sum\_{i=0}^\infty \frac{t^i\mathbb{E}(X^i)}{i!} \quad .$$

If you now consider the $k$-times derivative of $M\_X$:

$$M\_X^{(k)}(t)=\mathbb{E}(e^{tX})=\sum\_{i=0}^\infty \frac{\mathbb{E}(X^{i+k})}{i!} \quad ,$$

and use $0$ as an argument, you get $$M\_X^{(k)}(0)=\mathbb{E}(X^k)\quad,$$

so the $k$-th moment was generated.

---

Now look at the mutual information:

$$I(X,Y) = \sum\_{(x,y)}P(X=x,Y=y)\log\left(\frac{P(X=x,Y=y)}{P(X=x)\cdot P(Y=y)}\right) = \mathbb{E}(\mathrm{PMI}(X,Y)), $$

which is the expected value of the pointwise mutual information (it's likely that they actually deal with the continuous case where $I$ and $\mathrm{PMI}$ are defined using integrals and densities, respectively). So mutual information does not have a moment (or moment generating function), but it **is** the first moment of a random variable, so:

$$I(X,Y) = M\_{\mathrm{PMI}(X,Y)}'(0)\quad.$$

---
Tags: probability-theory, information-theory, bioinformatics
---


# Question
Title: An algorithm for fitting a rectangle inside a polygon
I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.

# Answer
Let $P=(p\_1,\dots,p\_n)$ be the polygon and $\overline{P}$ the set of points it contains.

Let $R=(a,b,c,d)$ be the rectangle of width $w$ and length $l$ with $l\ge w$ (and we assume $d(a,b)=w$) and $\overline{R}$ the set of points it contains.

You want $\overline{R}\subset \overline{P}$.

---

Suppose $\overline{R} \subset \overline{P}$.

Let $q=a+\cfrac{1}{2}\vec{ab}$ and $r=c+\cfrac{1}{2}\vec{cd}$.

Since $q\in \[ab\]\subset \overline{R}$ and $r\in \[cd\]\subset \overline{R}$, $\[qr\]\subset \overline{P}$.

Since $q\not=r$, we can find $s$ and $t$ on the border of $P$ so that $(qr)=(st)$.

---

Now suppose you are given a convex $P$

Here's the algorithm:

* $\forall i \in \[1,n\]$

+ $\forall j \in \[i+1,n\]$

    - If $\max \\{d(x,y),x\in\[p\_ip\_{i+1}\],y\in\[p\_jp\_{j+1}\]\\}\ge l$

        * $s = p\_i + k\_1 \vec{p\_ip\_{i+1}}$
            * $t = p\_k + k\_2 \vec{p\_jp\_{j+1}}$
            * $q = s + k\_3 \vec{st}$
            * $r = q + \cfrac{l}{\\|\vec{st}\\|}\vec{st}$
            * $\vec{v}:=$ a vector so that $\vec{sr}\perp \vec{v}$ and $\\|\vec{v}\\|=\cfrac{w}{2}$
            * $a := s - v, b:= s + v, c := r+v,d:= r-v$
            * $S:=solve(\\{"k\_1\in \[0,1\]", "k\_2 \in \[0,1\]", "k\_3 \in \[0,1\]", "a,b,c,d\in P"\\}$
            * If $S\not= \emptyset$, return true
* return false

The way this algorithm works is it chooses an orientation and an ax for the rectangle by choosing two arbitrary points $s$ and $t$ somewhere on two arbitrary segments of $P$. Then it takes an arbitrary $q$ in $\[st\]$ and expresses $a,b,c,d$ in terms of the constants $k\_i$ determining $s,t$ and $q$. Then for a point, you know how to determine if it is in a convex polygon so you just need to solve those linear inequalities (in $k\_1,k\_2,k\_3$) for all $4$ points. And if you have solutions, $R$ fits in $P$. Otherwise, you just try another one. And if none worked, since we know that if $R$ fits in $P$, then at least one must work, we know $R$ doesn't fit in $P$.

NB: $\max \\{d(x,y),x\in\[p\_ip\_{i+1}\],y\in\[p\_jp\_{j+1}\]\\}=\max\\{d(p\_i,p\_{i+1}),d(p\_j,p\_{j+1}),d(p\_i,p\_j),d(p\_{i+1},p\_{j+1})\\}$

---

Then for the non-convex case, you loose the fact that: $a,b,c,d\in \overline{P}\Rightarrow \overline{R}\subset \overline{P}$. So I'm not sure how to do it.

If I had to try, I'd break $P$ into several convex polygons and try to apply a similar algorithm except that I'd try every recombination of $A,B,C,D$ with $a\in A,\dots,d\in D$ with $A,B,C,D$ different convex polygons forming $P$ and then check that the segments of $R$ don't cross segments of $P$...
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Landau Notation, Definitions: Limits vs. Corman's
When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.:

$$o(g(n))=\\{ f(n): \forall c\>0:\exists n\_0\>0:\\; 0\leq f(n) \< cg(n): \\; \forall n\geq n\_0 \\}$$

and some texts use limit based definitions such as:

$$\lim\_{n\to\infty}\frac{f(n)}{g(n)}=0\Rightarrow f(n)\in o(g(n))$$

Is there any inherent advantage to one definition or the other? Or is it more a matter of the author's personal preference?

# Answer
To expand on Raphael's answer, both definitions are equivalent. The second definition is Landau-style (i.e. number theory style), while the first definition is computer science style.

The Landau-style definition is clearly more succinct and I personally prefer it. There are two reasons to state the definition in the computer science style:

1. Textbook writers don't want to assume that their readers know calculus.
2. The Landau-style definition for $f = \Theta(g)$ is more awkward: $\lim\inf f/g \> 0$, $\lim\sup f/g \< \infty$.
> 7 votes

# Answer
The second definition is often handy when comparing functions w.r.t asymptotic growth since evaluating one limit is (usually) easier than showing something for all $c$.
> 6 votes

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


# Question
Title: What algorithm would compute the maximum choices from two sets?
Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two vectors with extra zeros inserted into the shorter vector to make up for the size difference?

For example, consider the following two vectors as inputs:

```
[8 1 4 5]
[7 3 6]

```

The choices for inserting the zero and the resulting sum are:

```
[0 7 3 6]  => Maximums: [8 7 4 6]  =>  Sum is: 25
[7 0 3 6]  => Maximums: [8 1 4 6]  =>  Sum is: 19
[7 3 0 6]  => Maximums: [8 3 4 6]  =>  Sum is: 21
[7 3 6 0]  => Maximums: [8 3 6 5]  =>  Sum is: 22

```

Therefore, in this case, the algorithm should return 25.

I could do this by brute force by calculating for all permutations of placing zeros into the smaller vector (as just done above) but this would be computationally expensive, and worst in the case when one vector is exactly half the size of the other.

Is there a way to compute the answer in linear time proportional to the length of the longer vector even when the vectors differ in length? If not, can we do better than the number of factorial permutations being chosen?

# Answer
Hint: Use dynamic programming. For each $z,l$, compute the optimal way to insert $z$ zeroes to the prefix of length $l$ of the smaller array.
> 6 votes

---
Tags: algorithms, optimization
---


# Question
Title: A "natural" decidable problem not in $\mathsf{NP}$?
Are there any "natural" examples of decidable problems that are definitively known not to be in **NP**? The decidable languages I know of that are not contained in **NP** are usually derived from the time hierarchy theorem, which produces "artificial" languages based on diagonalization.

# Answer
From an answer to a related question on **NP**-hard problems which are not contained in **NP**: probably the most natural example is determining whether two regular expressions (including the Kleene star for arbitrary repetition, and a squaring operation to allow compact expressions of very large fixed numbers of repetitions) are equivalent. The resulting problem is **EXPSPACE** complete. Because **EXPSPACE** contains **NEXP**, which contains **NP** strictly (by the time hierarchy theorem), this is a decideable problem which is not in **NP**.
> 12 votes

# Answer
a variation of Posts Correspondence Problem for bounded length input (but *not* the standard "bounded" version eg in Garey/Johnson that is called "bounded PCP" that limits the number of blocks in the solution to the cardinality of the block set) is complete for NEXPSpace and therefore larger than NP which is properly in Pspace. \[1\]

ie let there also be an input parameter $n$ specified in binary that determines the maximal length of the PCP answer. this is apparently complete for NEXPSpace via a straightfwd proof. havent seen a proof in the literature. it proceeds in a way similar to the construction relating it to TMs in \[2\]

note that all problems that are known to be larger than NP are also larger than PSpace. otherwise it (a proof of a language that is not in NP but is still in PSpace) might be something close to a coNP$\neq$NP and therefore also P$\neq$NP proof (because P is closed under complement), or resolve some other "nearby" currently open complexity class separation.

\[1\] Decidable restrictions of the Post Correspondence Problem

\[2\] A polynomial reduction from any NP-complete problem to bounded PCP
> 0 votes

---
Tags: np
---


# Question
Title: Image pattern detection - Finding similarities in same image
The problem: Only pattern-like images are supposed to be uploaded and be used as backgrounds to a site, photos should not. How would you detect if an image looks enough like itself to be regarded as a pattern?

# Answer
I'm no expert in image processing, but generally, repeating patterns can be identified relatively easily in the frequency domain. This is true for signal as well as image processing.

From what I understand of your question, you want to check that each image is composed almost completely of some repeating pattern, and reject those which are not (for example, photos).

You might want to try a Fast Fourier Transform of the image, and look for peaks in the frequency domain. Here is a similar question on SO, and this accepted answer gives good suggestions - try FFT, Wavelet analysis and auto-correlation, in that order of chance of working effectively. The other answers also give links to good references, especially this link.

A google search for "Detect repeating pattern in images" should give you good references, such as this, this, this and this.

Most of these references look for unknown repeating patterns in a given image, and locate those patterns. You would need to perform some post-processing on this that ensures that the repeating pattern (almost) completely covers your image, and not a small portion of the image. This should rule out repeating patterns in parts of the image, say the pattern on a person's shirt.
> 2 votes

---
Tags: image-processing
---


# Question
Title: Division modulo a prime in modular arithmetic
I am looking for a way to implement division in modular arithmetic using modulo prime.

The method I found in math books is to **try** $u$ such that

$au \equiv 1 \pmod{p}$

$b/a \equiv bu \pmod{p}$

where $a, b, u \in Z\_p$ (remainder class modulo a prime $p$). But trying things is probably not a good and *fast* approach (as it seems to me it has linear complexity and my $p$ can be *big*, up to $10^9$). What is the right way to do division in modulo prime?

# Answer
> 10 votes
To divide $b$ by $a$, you follow two steps: first you find $u$ such that $au \equiv 1 \pmod{p}$, and then you compute $bu \pmod{p}$. To find $u$, you run the extended GCD algorithm on $a$ and $p$. If it is indeed the case that $a \not\equiv 0 \pmod{p}$, then since $p$ is prime $(a,p) = 1$. So the GCD algorithm will come up with numbers $u,v$ such that $$ au + pv = 1. $$ In other words, $au \equiv 1 \pmod{p}$.

---
Tags: arithmetic
---


# Question
Title: Show that the Kleene star of any unary language is regular
An exercise asks me to show that the Kleene star of any unary language $L$ is regular. $E$ is the alphabet, $E = \\{ 1 \\}$

Here's my reasoning :

* $L$ is regular $\implies$ $L^\*$ is regular (closure property)
* $L$ is not regular
    + $L$ contains the word of length 1 $\implies$ $L^\* = E^\* \cup \\{\epsilon\\}$ $\implies$ $L^\*$ is regular (since $E^\*$ is regular, and the union of two regular languages is regular)
    + $L$ does not contain the word of length 1 -\> ... ?

This is where I'm stuck. I don't know what to do if $L$ does not contain the word of length 1. I do not think that there exists a relation between $L^\*$ and $(L \text{ complement})^\*$.

Does anyone have any idea to continue this proof ? Thank you.

# Answer
Let $p$ be the $\gcd$ of the lengths of all the words in $L$. We claim that there exists $N$ such that for all $n\>N$, $1^n\in L$ iff $p|n$.

Observe that one direction is trivial: $p|n$ for every $1^n\in L$ by definition.

The converse is less trivial, you can find good guidelines in the answers here

Given this claim, you can write $L^\*$ as the union of the relevant words up to length $N$, and then $1^{pi}$ for all large enough $i$.
> 3 votes

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


# Question
Title: Deciding whether a given language is regular
I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes:

> Decide if the following language is regular or not and prove your claim.
>
> $$L=\\{a^{i\_{1}}ba^{i\_{2}}ba^{i\_{3}}ba^{i\_{4}}ba^{i\_{5}}ba^{i\_{6}}ba^{i\_{7}}b|i\_{1}\>i\_{2}\>i\_{3}\>i\_{4}\>i\_{5}\>i\_{6}\>i\_{7};i\_{1}\<100\\}$$

So, how do I go about doing so? Is there a thumb rule that might help? I was trying to use the pumping lemma to prove that it is not regular, but couldn't do it. I'm not even sure it really is not regular.

Any suggestions?

# Answer
> 5 votes
Hint: Consider how many words are in $L$. The answer will then be immediate.

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


# Question
Title: Hashing algorithm for millions of variable length strings (URLs)
The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. The strings are URLs. They tend to begin much the same way and end much the same way (e.g. h t t p:// or w w w. and ".c o m", ".e d u", "a s p x" and so forth) and show their greatest variation in the latter half of the string, except for the final few characters.

What's a good algorithm that would accept the string and the number of slots as inputs, and return a number between 0 and SlotCount-1, and satisfy the uniform-distribution requirement?

# Answer
> 2 votes
Any string hashing algorithm designed for ASCII text should work fine. Take a look at the Wikipedia article, consider if the set could be manipulated by an adversary to create pile-ups (algoritmic vulnerabilities). If that isn't an issue, at strchr and partow several "classical" hash algorithms are given and compared. Get a subset of your data and use the parameters suggested there for your own comparison. And please tell us the results.

---
Tags: algorithms, hash
---


# Question
Title: Interval Scheduling Problem with more than One Resource
Consider the interval scheduling problem, see also here.

In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest finish time, choose the next compatible one, and so on.

Now, let us say we have two resources instead of one. How do I schedule my jobs now? As my idea goes, again you start by sorting the requests in order of finish time. My problem is, how do I proceed after that? Do I choose the resources in sequential or in an alternate fashion?

If I go for sequential manner, I schedule all the possible jobs in the first resource and then do the same for second resource with the jobs yet to be scheduled.

If I go for alternate fashion, I choose the first possible job in the first resource, then second possible job in the second resource and so on.

In each case we will have take in to account the chosen jobs being compatible, needless to say.

I can not decide which of these is going to be optimal.

Any input will be appreciated.

# Answer
> 1 votes
Plot the intervals for all the jobs (sorted by earliest finishing time) on the x axis. Start with y = 1.

If two jobs overlap, then plot the intervals of the later job on a higher y -- i.e., above the already plotted job interval. Stop when all jobs have had their intervals plotted. Sort the levels such that the bottom most level has the maximum number of jobs and the top most level has the least number of jobs.

Now, start at the lowest bottom most level of your plot (i.e., y = 1). Allocate all the jobs at this level to machine 1. Then move to y = 2 and allocate all these jobs to machine 2. Repeat till all available machines have jobs.

The number of jobs that can be allocated to k machines is optimal (simple greedy exchange argument).

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Pumping Lemma for regular languages proof doubt - Sipser Book
I was reading the proof of pumping lemma from Sipser's book. I couldn't understand certain things mentioned there.

In the second paragraph he has written, "because $r\_l$ occurs among first $p+1$ places, we have $l \le p+1$". Here, does $l$ denotes the number of states visited?

Also he wrote "We know that $j \neq l$, so $|y| \> 0$; and $l \le p+1$; so $|xy| \le p$"

What I didn't understand is

1. $j \neq l$
2. $j \neq l$, so $|y| \> 0$
3. $l \le p+1$; so $|xy| \le p$

# Answer
> 5 votes
You missed what $j$ and $l$ are. Read the paragraph again. They are the two indices of the same state in the list of visited states. For example if some automata goes from $s\_1$ to $s\_3$ to $s\_5$ to $s\_3$ to $s\_7$, then you could pick $j = 2$ and $l = 4$, because both $2$nd and $4$th elements in the sequence are $s\_3$.

1. They are always (and, assuming $n \> p$, can always be) chosen different.
2. $y$ was defined as the substring which takes $r\_j$ to $r\_l$. $j \neq l$ and you need at least one symbol to change state, hence $|y| \> 0$.
3. The substring $xy$ takes $r\_1$ to $r\_l$. A string of length $x$ visits $x+1$ states, so if we know that $xy$ visited $l \leq p+1$ states then $|xy| = l-1 \leq p$.

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


title: How to Prove E $\subsetneq$ EXP?

text:
# Question
Title: How to Prove E $\subsetneq$ EXP?
I want to prove that $E \subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem

I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof:

* $E\subseteq TIME(2^{cn})$
* $TIME(2^{cn}) \subsetneq TIME(n^2 \cdot (2^{cn})^2)$ Time Hierarchy Theorem
* $E \subsetneq EXP$

Is this correct ?

---

I have done something similar with $P\subsetneq EXP$:
**PROOF IDEA**:

* $P\subseteq TIME(2^n)$
* $TIME(2^n)\subsetneq TIME(n^2\cdot (2^n)^2) \ \text{Time Hierarchy Theorem}$
* $TIME(n^2\cdot (2^n)^2)\subseteq EXP$
* $P\subsetneq EXP$

---

> **Complexity class E:** $E=\bigcup\_{c\ge 0}TIME(2^{cn})$
> **Complexity Class EXPTIME:** $EXP=\bigcup\_{c\ge 0}TIME(2^{n^c})$
> **Time Hierarchy Theorem:** $TIME(f(n)) \subsetneq TIME(n²\cdot (fn)²)$

The ***Time Hierarchy Theorem*** shows that allowing Turing Machines more computation time strictly increases the class of languages that they can decide. Recall that a function $f : N → N$ is a time-constructible function if there is a Turing machine that, given the input $1^n$ , writes down $1^{f(n)}$ on its tape in $O(f (n))$ time.

# Answer
The time hierarchy theorem states that if $f(n)$ is a reasonable function (technically, *time-constructible*), then there are some languages computable in time $f(n)$ that require (almost) time $f(n)$. More accurately, for any $g(n)$ satisfying $$ \frac{g(n)\log f(n)}{f(n)} \longrightarrow 0, $$ there is a function computable in time $f(n)$ but not in time $g(n)$.

Intuitively, this is saying that if we have more time ($f(n)$ rather than $g(n)$), then we can compute more languages. The theorem is a time-bounded version of the undecidability of the halting problem, and is proved in a very similar way.

In your case, you want to show that time $O(2^{n^\gamma})$ is more powerful than time $O(2^{cn})$. Here is one naive attempt: pick some $f(n) \in O(2^{n^\gamma})$ such that for all $g(n) \in O(2^{cn})$, the prerequisites of the time hierarchy theorem are satisfied. This shows that for each particular $c$, there is a language in EXP not computable in time $O(2^{cn})$. However, for all we know it can be computed in time $O(2^{(c+1)n})$, and so this doesn't show that EXP is larger than E.

Instead, you want to find a *single* language in EXP which is simultaneously not computable in time $O(2^{cn})$ for *all* $c$. To ensure that, you need to pick $g(n)$ judiciously, and I'll leave you to that.
> 5 votes

# Answer
While the answer of Yuval Filmus is absolutely correct, the comments and the correct proof for P in the question indicate that the problem of the OP is finding the intermediate class $\mathcal{C}$ between $\mathsf{E}$ and $\mathsf{EXP}$ ($\mathsf{E} \subseteq \mathcal{C}\subsetneq \mathsf{EXP}$).

As Yuval Filmu also indicates ("you want to find a *single* language $\dots$") you actually don't need to explicitly construct such a class if you use the proof of the theorem and not the theorem itself, as all you need is the *diagonal language* of this class, which will work as a counterexample for all subclasses (like $\mathsf{E}$) too.

This diagonal language is for the class $\mathsf{DTIME}(f)$

$$D\_f = \\{ (w, x) \mid M\_w \text{ accepts } x \text{ in } f(|x|) \text{ steps} \\}\quad.$$

Of course it does not work for $\mathsf{DTIME}(\mathcal{O}(f))$ (let alone $\mathsf{DTIME}(2^{\mathcal{O}(f)})$):

$$D\_{\mathcal{O}(f)} = \\{ (w, x) \mid M\_w \text{ accepts } x \text{ in } \mathcal{O}(f(|x|)) \text{ steps} \\}\quad.$$

How shall the poor Turing Machine know which $f$ is relevant while deciding $D\_{\mathcal{O}(f)}$?

So instead of $\mathcal{F}=\mathcal{O}(f)$ (or generally any class of functions $\mathcal{F}$) you need a $g$ that grows at least as fast as any function in $\mathcal{F}$. In most cases you need a function that grows faster than any $f\in \mathcal{F}$, because if it grows as fast as a function in $\mathcal{F}$, you'll find a function in $\mathcal{F}$ that grows faster than $g$.

As stated in the question $g(n)=2^n$ is a good choice for $\mathsf{P}$, if you want to show its relation to $\mathsf{EXP}$, for $\mathsf{E}$ $g(n)=2^{n^k}$ for any $k\>1$ will do the trick.

---

Resumé of the possible "proofs":

1. $\mathsf{E}=\mathsf{DTIME}(2^{\mathcal{O}(n)}) \subsetneq \mathsf{EXP}$ via THT (does **not** work)
2. $\mathsf{E}\subseteq\mathsf{DTIME}(2^{n^{k}}) \subsetneq \mathsf{EXP}$ via THT (works if $k\>1$)
3. $D\_f \in \mathsf{EXP}\setminus\mathsf{E}$, where $f(n)=2^{n^{k}}$ (works analogously to a proof for the THT if $k\>1$)
> 2 votes

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


title: Perfect shuffle in parallel processing

text:
# Question
Title: Perfect shuffle in parallel processing
How is Perfect shuffle a better interconnect scheme for parallel processing? For example if we consider a problem of sum reduction, I want to understand how this scheme is useful when implementing sum reduction in parallel , for example on a GPU?

# Answer
> 3 votes
The perfect shuffle alone has never been used as an interconnection network; it always included exchange links, in order to allow for a worst-case $O(\lg n)$ routing algorithm. Algorithms for reduction, broadcast, parallel prefix, transpose etc are given in

Yosi Ben-Asher , David Egozi , Assaf Schuster, SIMD Algorithms for 2-D Arrays in Shuffle Networks.

Stone was the first researcher to provide algorithms for the perfect shuffle network, including algorithms for the FFT, matrix transpose etc.

This network has been used in several parallel machines, but mostly in multi-stage shuffle-exchange networks such as the Omega network (which uses the perfect shuffle between stages). An example is the IBM SP3 machine.

Note that these are message-passing algorithms, whilst you refer to a GPU, which is instead a shared-memory device.

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: Prove finding a near clique is NP-complete
An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if there exists $S \subseteq V$ where $|S| = k$ and $u,v \in S$ where $(u,v) \not\in E$, and $S$ forms a clique in $(V,E \cup \\{(u,v)\\})$. How can I show finding a near clique of size $k$ in $G$ is NP-complete?

# Answer
I think the following reduction works (unless I missed something):

Given $G=(V,E)$ and $k$, output $G'$ which is obtained from $G$ by adding $2$ new vertices $\\{x,y\\}$. that are each connected to all the vertices in $V$ (but not to each other). Finally, the output is to search for a $k+2$ near clique.

Clearly this is polynomial (linear).

If there exists a $k+2$ near clique in $G'$, then if $k+1$ of its vertices are contained in $V$, then $G$ has a $k$-clique. If less than $k+1$ vertices are from $V$, then at least $k$ of them are, since $x$ and $y$ are not connected between them. But then, the $k$ remaining vertices in $G$ must form a clique.

Conversely, if $G$ has a $k$-clique, then just add the two new vertices $x,y$ to get a $k+2$-near clique.
> 7 votes

---
Tags: complexity-theory, graphs, np-complete
---


# Question
Title: Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?
Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?

What difference does it make if the input of a strongly NP-hard problem is unary encoded? I mean, if I take for instance the weakly NP-complete Knapsack problem, it is NP-complete when binary encoded but can be solved in polynomial time by dynamic programming when unary encoded. Maybe it has some implications for hardness of higher levels of the polynomial time heirarchy?

Does the notion of strongly ...-hard also hold for other complexity classes, e.g. higher classes of the polynomial time hierarchy?

I previously asked this question at stackoverflow.com but it was pointed out that it is more appropriate here.

# Answer
> 4 votes
A problem size of $N$ encoded in unary is size $N$ and $\log N$ if binary. If the time taken is $F(N)$, this is $F(\text{size})$ in the first case and $F(2^{\text{size}})$ in the second case. So an algorithm that is polynomial for the first case will probably be exponential for the second. The encoding of the problem can so change the complexity of an algorithm radically.

# Answer
> 3 votes
## No.

If you change the encoding of the input, you've changed the formal definition of the problem, which means it's a **different problem**. The complexity of the original problem doesn't change, for the same reason that pointing at a different light in the sky does not change the mass of the moon.

# Answer
> 2 votes
The short answer is, that if the input is unary encoded, then it is *longer*. It is *exponentially* longer. Now, an algorithm that works in polynomial time **in the size of the input** has "enough time" to solve the problem, just because the input itself is exponentially longer than in the original problem.

# Answer
> 1 votes
Seeing past the formulation issue pointed out in JeffE's answer, the answer is yes.

Consider the Knapsack problem. It does have a pseudo-polynomial algorithm, that is one with runtime bounded by a polynomial in a number encoded in the input. Because in unary encoding values correspond to length, this is a polynomial-time algorithm for the unary version.

In fact, every weakly NP-complete problem falls into this category.

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


title: Local Search vs Classical Search

text:
# Question
Title: Local Search vs Classical Search
I have some questions regarding local search / optimization as explained in chapter 4 of the book : http://aima.cs.berkeley.edu/

In classical search (Chap 3), the search starts from an initial node, then the search continues based on strategies of BFS, DFS, etc. What I am unsure of is the process of local search (Chap 4).

1. Does the local search algorithm start from one node in state space? Check if constraints are satisfied? If Yes, this is goal? If not, move to neighbours?
2. Is the entire state space considered goal state? Even nodes that don't satisfy the constraints?
3. In optimization, the search is conducted in a part of search space where all constraints are met, but tries to find a better solution. In that case, what if the search algorithm moves to nodes where they don't satisfy the constraints?

# Answer
> 4 votes
Classical local search works as follows. We're trying to optimize some function under some constraints. We start with some feasible point (a point satisfying all constraints). At each step, we consider small changes to the current point which (1) keep it feasible, (2) improve the objective function. If we find such a small change, we modify the point accordingly. Eventually, we reach a local optimum, and we hope that it's not too bad relative to the global optimum.

A classical example is the simplex algorithm for linear programming. The algorithm starts with some feasible point (it's not immediately obvious how to do it; a trick is required). At each step, we try to modify the point by switching one tight constraint with another in a way that improves the objective function while keeping the point feasible. Eventually we reach a local optimum, which turns out to be a global optimum (in this particular case).

The interior-point algorithm for linear programming work differently. They start at some point, and move in a direction that (1) makes the point more feasible, and (2) improves the objective function. In the end, you get close to a feasible local optimum, which turns out to be a global optimum. This is not local search, but it's an example of an algorithm which does not maintain a feasible solution.

Non-oblivious local search is a variant on the theme of local search, in which instead of trying to optimize the actual objective function, you direct the local search using an auxiliary objective function. Sometimes this improves the quality of the local optimum. You can read all about it in a recent PhD thesis by Justin Ward.

# Answer
> 4 votes
> Does the local search algorithm start from one node in state space? Check if constraints are satisfied? If Yes, this is goal? If not, move to neighbours?

A local search would typically start from an arbitrary solution. For example in the case of SAT, each variable could be assigned either a 0 or a 1 with independent equal 1/2 probability. What you describe next is not related to what you start with. But yes, you could then follow a general strategy of checking whether or not you have a feasible solution, and perhaps move on to the neighboring states following some strategy.

> Is the entire state space considered goal state? Even nodes that don't satisfy the constraints?

A goal state is a state which satisfies your constraints. For example in the case of 8-queens, a goal state would be any placement of the queens so that they don't attack each other. All other states are not goal states.

> In optimization, the search is conducted in a part of search space where all constraints are met, but tries to find a better solution. In that case, what if the search algorithm moves to nodes where they don't satisfy the constraints?

In general, it would be more accurate to say that the search is conducted in the whole search space, which includes all possible states. The rest of your question depends totally on the search method used. For example, you could try to greedily improve on the solution found so far. If you then encounter a solution that is not better anymore, or as you say not even a valid solution, you would return the last known best solution.

---
Tags: artificial-intelligence, search-algorithms
---


title: Network modem question

text:
# Question
Title: Network modem question
How would I solve the following can anyone help me.I know MIPS is basically how many instruction the processor can do per second but what should I do?

Assume that we are receiving a message across a network using a modem with a rate of 56,000 bits/second. Furthermore assume that we are working on a workstation with an instruction rate of 500 mips. How many instructions can the processor execute between the receipt of each individual bit of the message?

# Answer
There are not enough details in the question. Yuval's answer gives the basic arithmetic answer. I'll just add that usually modems do not transfer the information "as-is" but encode it (see Asynchronous serial communication).

The most common encoding is 8N1, which means 10 symbols are sent per 1 byte of the message. The baud rate (56,000) is the number of symbols per second, rather than the number of bits per second.

So 8 bits of the message take 10 symbols, that is 1/5600 second. 1 bit takes 1/44800 sec. During that time, with 500MIPS you have $\approx 11200$ instructions.

(of course, if the rate is indeed 56000 **bits**/sec, then the 8/10 factor is not necessary.)
> 1 votes

# Answer
Hint: Suppose that the processor manages to execute $N$ instructions between the receipt of each individual bit. Executing the $N$ instructions takes time $T\_1$. The time interval between the receipt of each individual bit is $T\_2$. Set up an inequality and solve for $N$.
> 1 votes

---
Tags: computer-architecture, coding-theory, arithmetic
---


title: Assignment problem with no cost

text:
# Question
Title: Assignment problem with no cost
I have a problem that I was able to conceptualize as following:

## Problem

We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of these people, I want to check if it is a diverse group.

A diverse group is a group that satisfies several requirements, each requirement is of the form "at least $k\_i$ persons in the group belong to subset $S\_i$". Here is the tricky part, one person can only be used to satisfy one requirement. As in, you can't use him/her for multiple requirements.

## Example:

Given:

At least two people from Hispanic= {a,b,c}

At least two people from African={a,d,e}

Is the group {a,c,d} a diverse group?

The group {a,c,d} is not diverse because you cant count a as Hispanic and African. But, the group {a,c,d,e} is diverse because we have two Hispanics a and c and two African d and e.

## Attempt:

I think this is an instance of the Assignment problem. The jobs are the ethnicity and we can put as many ethnicity as the requirement dictate. For example, if we need two Hispanic, then we put two Hispanic jobs. However there only some people are able to do a particular job. Is there a name for such a problem? any algorithms somewhere in the internet? If not how would the implementation look like?

This is my attempt so far:

I will construct a bipartite graph with the set of people $P$ on one hand and the set of ethnicity on the other $S$. We will put an edge between a person $p\_i$ and an ethnicity $S\_i$ if he/she belongs to the ethnicity. Now, we will modify the graph, for every ethnicity $S\_i$ duplicate it $k\_i$ times ($S\_{i,1}, S\_{i,2}, ... , S\_{i,k\_i}$). And add new edges accordingly. Find the maximum matching M of this graph.

Now, merge the $S\_{i,j}$s into one $S\_i$ and there you have a diverse group. However, a maximum matching is only a possible solution to to the problem. And my problem is a decision problem, I want to check if a given group is a solution or not.

# Answer
> 1 votes
Let $P$ be the set of people and $\mathcal{S}$ be the modified multi-set of subsets. By checking if an $\mathcal{S}$-saturated matching into $P$ exists (i.e. Hall's condition) you are indeed finding a diverse group. If you are checking that some group $P$ is a putative solution the procedure is the exactly the same.

This can be done quickly via the Hopcraft-Karp algorithm (as you don't have weights over edges) or by implementing this as a Max-flow LP and using a solver. I'm willing to bet the solvers will work much faster in practice.

---
Tags: graphs, bipartite-matching, matching, assignment-problem
---


# Question
Title: Prove Matrix Correspondence is NP-complete
Consider the following problem. Given a $m \times n$ integer matrix $A$ and a $p \times q$ integer matrix $B$, do there exist one-to-one functions $$r:\\{1,2,...,m\\} \rightarrow \\{1,2,...,p\\}$$ $$c:\\{1,2,...,n\\} \rightarrow \\{1,2,...,q\\}$$ where for all $1 \leq i \leq m$ and $1 \leq j \leq n$, $A\[i,j\] \leq B\[r(i),c(j)\]$?

What is the best way to show this problem is NP-complete? I am currently considering reducing the clique problem to this problem.

# Answer
As you mentioned, we can reduce maximum clique problem to this. In fact we can reduce the more general subgraph isomorphism problem to this one easily. Given graphs $G$ and $H$, define $A$ and $B$ as their (undirected) incidence matrices. Then we can see that solving the matrix correspondence tells whether $G$ is isomorphic to some subgraph of $H$, which is an NP-complete problem.
> 6 votes

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


# Question
Title: Show that a function belongs to grade of incline
This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$

I need to show and proof to which of these function grades does the function: $n^7$ belong to. I didn't get a chance to ask my professor on this topic so I'm not sure how to solve this problem.

# Answer
The term of $O(...)$ means representation of the performance of a solution. It is not entirely clear what you see under the expression n ^ 7. And because it is a representation of the complexity of the algorithm is needed to know how this power will count. There can be several calculation algorithms, each of which will have a different expression of the complexity. If you used the algorithm to multiply numbers, then you can, for example, the multiplication using konvolučního algorithm for the discrete Fourier transform. Performance of such algorithm is the maximum $O(7\cdot n \cdot log\space n)$, where n is the number of components of the vector needed for representation of numbers using the discrete Fourier transform. Otherwise, if this is just a number, then I can also provide your own custom algorithm that takes advantage of the symmetry of the multiplication, exponentiation, and in case there is no need to perform a transformation for the convolution and there would be performance requirements could be smaller.
> 0 votes

---
Tags: complexity-theory, asymptotics, landau-notation
---


# Question
Title: Upper Bound on Runtime of Memoized DP Algorithms
I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive functions.

However, I am now trying to determine a "Big-O" for a DP problem I've memoized. I don't really care about the answer to this specific problem, but am more interested in a method I can use for other programs I write, or a resource that I can read to learn how to analyze this type of program.

In case a concrete example helps, the following is my program to solve this box stacking problem. (I wrote my solution before looking at theirs, which appears to use bottom-up DP instead of top-down/memoization. Thus, I don't think I can cross-apply their time complexity to my algorithm.)

Below is the pseudo-code for my solution. Assume that putting something on the memo and checking the memo can be done in constant time.

```
Let a box have parameters width (w), height (h), and depth (d)
reward(maxW, maxD, elementH):
  Zero max1, max2, max3
  If memo contains key (maxW, maxD), return associated value.

  for each box B in the list of input boxes:
    //If the box fits in any orientation, put it on the pile and recurse
    if (B.w < maxW AND B.d < maxD) OR (B.w < maxD AND B.d < maxW)):
      max1 = max(max1, reward(B.w, B.d, B.h) + B.h)
    if (B.h < maxW AND B.d < maxD) OR (B.h < maxD AND B.d < maxW)):
      max2 = max(max2, reward(B.h, B.d, B.w) + B.w)
    if (B.h < maxW AND B.w < maxD) OR (B.h < maxD AND B.w < maxW)):
      max3 = max(max3, reward(B.h, B.w, B.d) + B.d)

  put (maxW, maxD) onto memo, associated with max(max1, max2, max3)

  return max(max1, max2, max3)

```

# Answer
> 5 votes
A general trick that works for a lot of DP problems is to look at the parameters in your recursion -- the run time is then $O(n \times max(parameter\_1) \times \dots \times max(parameter\_k))$ where $n$ is the number of iterations (or, the number of inputs).

Consider for example a DP to solve the subset sum -- the recursion is given by $Q(i,s) := MIN(Q(i − 1,s), Q(i − 1,s − x\_i)) $ where $0 \leq s \leq T$ and $T$ is the target sum.

The run time is then $O(n \times max(s)) = O(nT)$. And of course, this trick works with memoization only. If you have not done memoization, it is truly exponential (not pseudo-polynomial).

Why does this work? In each iteration $i$, we have to look at at-most $T$ different sub-problems (post memoization) before we hit the base case.

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, memoization
---


# Question
Title: Does hardness of a special case imply hardness of a general case?
I am wondering in general if it is correct to claim that **if a special case of a problem is NP-Hard, the general case of that problem is NP- Hard too?**

For example: Min Set-Cover is NP-Hard does it imply without having to prove that Min Set-k-Cover where each element needs to be covered k times is NP-Hard too?

# Answer
> 5 votes
If frafl's answer doesn't give it away immediately, perhaps think in the reverse direction, if the special case is NP-hard, what would be implied by the general case being in P?

# Answer
> 3 votes
To show that a general problem $G=\\{(w,k)\mid \text{Property}\\}$ is NP-complete you need a polynomial time computable many-one reduction function $f$ from e.g. $S\_l =\\{w\mid (w,l) \in G\\}$ to $G$. How could $f$ look like?

# Answer
> 2 votes
A problem is a set of instances. We consider a problem "hard" if there are instances that require lots of resources to solve (time, space, brain cells, whatever). If a subset of the problem is hard, then the problem is hard. If a subset is easy, that doesn't mean the problem is easy (there might be hard instances elsewhere). Think of the hardness as a "worst possible case" measure.

\[Yes, I know this is horribly non-rigorous.\]

---
Tags: complexity-theory, terminology, np-hard
---


# Question
Title: Finding the language generated by a context-free grammar
This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):

> What language is generated by this grammar?
>
> $S \rightarrow a S b S \mid b S a S \mid \epsilon$

I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):

> a language is the set of all words that can be produced by any parse tree.

So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.

# Answer
> 7 votes
Hint: What can you say about the number of $a$s and $b$s in the produced words?

> It would be very helpful if someone were able to provide some tips on solving these sorts of problems.

There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.

# Answer
> 6 votes
Hint: Construct some words that are generated by this grammar. Do you see a pattern? Can you describe some properties of all words generated by the grammar, just by looking at the rules? Once you have a (correct) guess as to the language generated by the grammar, it won't be too difficult to prove it.

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


# Question
Title: Is there a data-structure for semilattices similar to a tree data-structure?
If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (more or less) efficiently. In the case of a tree, a data structure which would enable this would be to store for each element in the corresponding node a pointer to the parent and a distance measure to the root. (Actually, a labeling based on topological sort usually used for "a distance measure to the root", effectively all that is needed is a compatible partial order which can be evaluated efficiently).

Each finite join-semilattice can be represented as a set of subsets of a finite set with containment as order such that the least upper bound is given by the union of the sets. Hence, representing each element by a finite number of tags, and computing the least upper bound by the union of the corresponding tags would be one possible data structure. (By looking at the complement, one sees that defining the least upper bound as the intersection of the corresponding tags would also be possible.) A much more common data-structure is to simply use a matrix to store all results of "a \<= b" or even all results of "join(a,b)".

However, using such a data-structure to represent a tree would be sort of strange. Are there more tree-like data-structures for join-semilattices, which still allow (more or less) efficient computation of the (unique) least upper bound of two elements? (Perhaps some sort of directed acyclic graph with additional information in the nodes similar to the distance measure to the root for the tree?)

# Answer
> 8 votes
This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg. Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

The first two data structures discussed are the adjacency list representation of the transitive reduction graph (=Hasse diagram/cover relation) and transitive closure graph (=poset relation). A remark about the advantages of using a topological sort to label the nodes precedes that discussion. Note that the labels of topological sort would be good enough as "a distance measure to the root", which was one part of the data-structure for a tree in the question.

The other discussed representations are "Skeletal Representation", "Matrix Representation" and "Dimension Based Representation". The "Skeletal Representation" is interesting and useful, but based on a (=any) chain decomposition of the poset. The "Matrix Representation" might seem trivial, but its probably be the best representation for most practical problems. The "Dimension Based Representation" represents the poset as the subset of the Cartesian product of linear orders, but computing the minimal representation of this kind is NP-hard.

In conclusion, the most treelike representation of these is the adjacency list representation of the transitive reduction together with a labeling of the nodes by a topological sort (instead of "a distance measure to the root"). This is actually one of the representations used by Sage (the other is the "Matrix Representation").

---
Tags: data-structures, lattices
---


# Question
Title: Lowest common ancestor similar algorithm for a graph
I'm working on a type system and hit upon a problem that seems similar to lowest common ancestor. Given two types, I need to find the smallest sequence of conversions which will result in the same target type. If I had a simple type tree I know how to get the result, but unfortunately I have a slightly more complex graph structure.

That graph has a few key points. It is unidirectional and no loops are ever formed. Due to an unlimited number of types however it cannot be produced statically. The distance of a path is generally quite low. It "feels" more like a tree with a bunch of shortcut edges.

Initially I looked at lowest common ancestor, but it is mainly described as a tree algorithm. I've not yet given up hope that I could adapt it. The other possibility would be a more generic path-finding algorithm.

I'm hoping somebody has seen this problem before, or a similar one, and can give me some references on how to further approach it. It seems familiar enough that I assume something must exist and I'm just searching for the wrong terms/names.

---

Here's my attempt to describe this more formally.

Let there be a graph $G = \\{ V \\}$ such that each vertex has a set of outgoing edges $V = \\{ E=V\_x \\}$. Note, as the graph is dynamic, possibly infinite, there is no way to construct the form $G = \\{V, E=(V\_x,V\_y)\\}$ for the entire graph.

A path is formed from a vertex by following any of the available edges from that node. $Pnm\_x = V\_n, ..., V\_m$. The length of this path is equal to the number of vertices in the sequence. There is no cycle possible. The set of all paths between two nodes is expressed as $Pnm = \\{ V\_n, ..., V\_m \\}$.

Note that $Pnm$ can be determined to be empty in a finite number of steps. Enumerating the entire $Pnm$ set is not practically possible.

The problem is finding the shortest path from two vertices to a third vertex. That is, given $V\_a, V\_b$, find $V\_c$ such that paths $Pac\_x$ and $Pbc\_y$ exist and $length(Pac\_x) + length(Pbc\_y)$ is minimal.

# Answer
> 5 votes
If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime complexity is not as good as I would have expected intuitively. I asked a related question some time ago, but was too lazy to write an answer after I found the relevant solution in the "literature". I just wrote the answer now, and it starts as follows:

> This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg. Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

Here is the relevant part from chapter 2.3.1:

> We now give an $O(n + |e\_\prec|)$ algorithm to compute the join of two elements $x$ and $y$. The algorithm returns $null$ if the join does not exist. We first assume that we are using the cover relation. To compute $join(x,y)$, we proceed as follows:
>
> * Step 0: Color all nodes white.
> * Step 1: Color all nodes reachable from $x$ as grey. This can be done by a BFS or a DFS starting from node $x$.
> * Step 2: Do a BFS/DFS from node $y$. Color all grey nodes reached as black.
> * Step 3: We now determine for each black node $z$, the number of black nodes that point to $z$. Call this number $inBlack\[z\]$ for any node $z$. This step can be performed in $O(n + |e\_\prec|)$ by going through the adjacency lists of all black nodes and maintaining cumulative counts for $inBlack$ array.
> * Step 4: We count the number of black nodes $z$ with $inBlack\[z\]$ equal to $0$. If there is exactly one node, we return that node as the answer. Otherwise, we return $null$.

---
Tags: algorithms, graphs
---


# Question
Title: Constraint violation and efficiency in search
It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:

1. Start with a feasible solution and expand search until constraints are tight and solution is maximal (or minimal).
2. Begin with violated constraints and search for maximal (or minimal) feasible approach.

For the Max-Flow problem Ford-Fulkerson satisfies condition (1), while Push-Relabel satisfies condition (2). An interesting point is that Push-Relabel is a more efficient algorithm than Ford-Fulkerson. My question is this:

> What other examples are there where (2)-based approaches outperform their (1)-based counterparts?

A follow up is:

> Do there exist meta-theorems regarding approaches based on condition (2)?

# Answer
> 4 votes
Another example is interior-point algorithms for convex optimizations, which (if I remember correctly) start at an arbitrary point and try to simultaneously get into the feasible region and optimize the objective function. They are provable and (to some extent) practically faster than the simplex algorithm (and related algorithms like the criss-cross algorithm), which does a local search inside the feasible polytope.

# Answer
> 3 votes
As encouraged in the comments, I'm giving a more general answer regarding constraint violation or constraint propagation in search in the context of CSP solvers. In a sense, the theory of search in CSP/SAT majorizes other approaches. My answer deals with complete search methods, although hybrids exist (combine local search with inference).

A constraint satisfaction problem (CSP) as a triple $\langle X,D,C \rangle$, where $X$ is a set of variable, $D$ a set of domains (one for each variable), and $C$ is a set of constraints that limit or specify allowable combinations of values. Solving CSP problems is obviously hard (SAT is a special case). Also, the obvious way of solving a problem is search. Search can be replaced or at least combined with a specific kind of inference called constraint propagation. For example, consider modeling a Sudoku puzzle as a CSP. After a variable has been assigned to some value (a number placed into a cell), we an call an algorithm, that propagates the consequences of that variable assignment. If we notice this leads to a non-solution, we undo that variable assignment, and try another one. Many different algorithms for propagation exist, such as Mackworth's AC-3. As is with the type of inference used, the variable and value selection heuristics all play a major role in the efficiency of the solver.

A key aspect that was noticed early on was that effective heuristics were "fail-first heuristics". Whatever we choose (what variable to assign next, what value to assign to it), it should be most likely to fail soon, thereby pruning the search tree.

A popular heuristic for choosing a variable is the minimum-remaining values (MRV) heuristic: pick the variable with the fewest legal values. This is a "fail-first heuristic" that was already proposed in 1965 by Golomb and Baumert. Much effort has since gone into understanding and enhancing this already powerful heuristic. It was noted that MRV only exploits information about the current state of the problem. The heuristic can be made adaptive by exploiting the information about the previous states as well. The so called dom/wdeg heuristic proposed in 2004 is still widely considered to be the most effective general approach known. The idea is as follows:

1. Associate each constraint with a weight, initially set to 1
2. Everytime a constraint is responsible for a dead-end, its weight is incremented
3. When choosing a variable, first choose the one with fewest legal values
4. In case there are multiple choices, broke ties by dividing with the weighted degree, which is the sum of weights of the constraints involving the variable in question, and at least one other unassigned variable

What good does this do? Well, the weight on the hard constraints increases as the search progresses. In other words, the search is being guided towards hard parts of the problem. Once again, obviously one is more likely to fail when faced with a hard problem, and here we again see the "fail-first principle" in work.

By the way, the dom/wdeg heuristic has been observed to have a nice synergy with specific random restart strategies in 2008 by Grimes \[1\]. Grimes observed the so-called geometric strategy was the most suited one, making the dom/wdeg even more powerful.

---

\[1\] Grimes, D. (2008). A study of adaptive restarting strategies for solving constraint satisfaction problems. In Proc. 19th Irish Conference on Artificial Intelligence and Cognitive Science-AICS (Vol. 8, pp. 33-42).

---
Tags: algorithms, optimization, lower-bounds
---


# Question
Title: Controlled NOT gate a type of measurement?
I'm trying to understand the theory of quantum computing, and I'm a bit confused on a particular circuit:

Would the controlled NOT gate be a type of measurement, causing Q1 to be either |0\> or |1\>, or would the circuit be in a superposition of the |00\> and |11\> states until an actual measurement of Q1 or Q2 took place?

# Answer
> 4 votes
A controlled-NOT gate is meant to be a reversible operation which, for ordered pairs of bits $(a,b) \in \\{0,1\\}^2$, performs the operation $$ \mathrm{CNOT} (a,b)\\; = \\;(a, b \oplus a)$$ where conventionally we represent the "control" by the first bit and the "target" by the second. (In a physical implementation, essentially the same physical interaction but in a different orientation would be used to implement the transformation $(a,b) \mapsto (a\oplus b, b)$ and so this is also called a "controlled-NOT", rarely with any distinction from the one described above.) This gate is obviously reversible, as one can easily verify that $\mathrm{CNOT} \circ \mathrm{CNOT} = \mathrm{id}\\,$.

As is usual in quantum computation, we "lift" reversible operations such as $\mathrm{CNOT}$ to distributions over inputs by describing it as a permutation of computational basis states. In particular, because $$\begin{align\*} (0,0) \\;&\xrightarrow{\\;\mathrm{CNOT}\\;\\;}\\; (0,0) \\ (0,1) \\;&\xrightarrow{\\;\phantom{\mathrm{CNOT}}\\;\\;}\\; (0,1) \\ (1,0) \\;&\xrightarrow{\\;\phantom{\mathrm{CNOT}}\\;\\;}\\; (1,1) \\ (1,1) \\;&\xrightarrow{\\;\phantom{\mathrm{CNOT}}\\;\\;}\\; (1,0) \end{align\*}$$ the permutation matrix which we use to represent $\mathrm{CNOT}$ is $$ \mathrm{CNOT} \\;=\\; \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\\; .$$ It is easy to verify that this (and all other permutation matrices) are unitary. This is the operation which transforms the state of the first two qubits. Because the state of those two qubits just before the $\mathrm{CNOT}$ gate is given by $$ |\psi\_1\rangle \\;=\\; (H \otimes \mathbf 1) |0\rangle |0\rangle \\;=\\; \tfrac{1}{\sqrt 2} \Bigl\[ |0\rangle |0\rangle + |1\rangle |0\rangle \Bigr\] \\;=\\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \\,,$$ the state that we obtain afterwards is given by $$ |\psi\_2\rangle \\;=\\; \mathrm{CNOT} |\psi\_1\rangle \\;=\\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \\;=\\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix} \\;=\\; \tfrac{1}{\sqrt 2} \Bigl\[ |0\rangle |0\rangle + |1\rangle |1\rangle \Bigr\] \\,.$$ In this case, it's probably easiest to see that you can apply the action of $\mathrm{CNOT}$ on the standard basis states $|0\rangle|0\rangle$ and $|1\rangle|0\rangle$ separately, which form the components of $|\psi\_1\rangle$, to obtain components $|0\rangle|0\rangle$ and $|1\rangle|1\rangle$ respectively; this is possible because the $\mathrm{CNOT}$ operation (and all other permutations and unitary operators) is linear.

---
Tags: quantum-computing
---


# Question
Title: Grammar for describing boolean expressions with AND, OR and NOT
I wrote the following LL(1) grammar to describe the set of boolean expressions involving `AND` ,`OR` an `NOT` only. This, as can be seen, also reflects the precedence of the operators (ie., 'AND' is done before 'OR', etc).

Is it correct?

```
    1.  E   ::=  T E’
    2.  E’  ::= OR T E’
    3.  E’  ::=  ε
    4.  T   ::=  F T’
    5.  T’  ::= AND F T’
    6.  T’  ::= ε
    7.  F   ::= NF'
    8.  N   ::= NOT
    9.  N   ::= ε
   10.  F'  ::= (E)
   11.  F'  ::= id

```

# Answer
> 4 votes
Here is an EBNF grammar with precedence of operators enforced.

$\text{exp} \to \text{term } \\{ \text{OR term}\\};$

$\text{term} \to \text{factor } \\{\text{AND factor}\\};$

$\text{factor} \to \text{id};$

$\text{factor} \to \text{NOT factor};$

$\text{factor} \to \text{LPAREN exp RPAREN};$

TRUE and FALSE are id's. Try this online tool to check your grammar.

# Answer
> 2 votes
It is an almost copy of the grammar Wirth gives for arithmetic expressions in "Algorithms + data structures = programs" (as far as I can remember it; I might be wrong with the source, though). So I strongly believe it is correct.

Write the corresponding recursive descent parser, and try it on some correct strings, and some badly built ones. Get somebody else, without coaching on your part, come up with examples and broken cases. Also generate some random combinations to try.

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


title: Fastest Algo to separate the 0s and 1s

text:
# Question
Title: Fastest Algo to separate the 0s and 1s
Suppose, I have an array of length 100. I have 0s at some positions and 1s at some other positions. What is the ***fastest method*** by which I can separate the **0s** and **1s**, so that we get all the 0s at the beginning and all the 1s at the remaining positions / vice-versa?

# Answer
> 2 votes
Here is another version of Yuval's algorithm that uses two loops only.

```
int number_of_ones = 0;
for(int i = 0; i < 100; ++ i)
{   number_of_ones += A[i];
    A[i] = 0;
}
for(i = 100 - number_of_ones; i < 100; ++ i)
{   A[i] = 1;
}

```

# Answer
> 5 votes
```
i=0, j=size(ar)-1;
while(true)
   increase i to position of first 1;
   decrease j to position of first 0;
   if(i>=j) break;
   ar[i]=0, ar[j]=1;

```

# Answer
> 3 votes
Here is vonbrand's solution.

```
int C = 0, i;
for (i = 0; i < 100; i++)
  C += A[i];
C = 100 - C;
for (i = 0; i < C; i++)
  A[i] = 0;
for (; i < 100; i++)
  A[i] = 1;

```

This solution has the advantage that we only scan the array forwards. Also, there are no conditionals.

The idea can be adapted to arrays with any constant number of values, say decimal digits. Instead of `C += A[i]`, you use `C[A[i]]++`.

---
Tags: program-optimization
---


title: Recurrence relation with sum

text:
# Question
Title: Recurrence relation with sum
This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help?

The problem asks to solve the following recursion $T(n)=\frac{1}{n} \sum\_{i=1}^{n-1}(T(i)+T(n-i))+cn$. The problem also warns that unwrapping is going to be the wrong approach and the right strategy would be to guess the solution and prove it by induction. As the first step it suggests to start with $nT(n) -(n - 1)T(n -1)$.

# Answer
> 2 votes
The trick here is to get rid of the sum. Note that the sum is up and down, it can be replaced by twice up: $$ \begin{align\*} (n + 1) T(n + 1) &= 2 \sum\_{1 \le k \le n} T(k) + c (n + 1)^2 \\ n T(n) &= 2 \sum\_{1 \le k \le n - 1} T(k) + c n^2 \\ (n + 1) T(n + 1) - n T(n) &= 2 T(n) + c (2 n + 1) \end{align\*} $$ This is a linear, first order, non-homogeneous recurrence.

**Update:** Solution to the recurrence.

The recurrence can be written: $$ \frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1} = c \frac{2 n + 1}{(n + 1)(n + 2)} $$ This reduces to a sum: $$ \begin{align\*} \frac{T(n)}{n + 1} &= T(0) + c \sum\_{0 \le k \le n - 1} \frac{2 k + 1}{(k + 1) (k + 2)} \\ &= T(0) + c \sum\_{0 \le k \le n - 1} \left( \frac{3}{k + 2} - \frac{1}{k + 1} \right) \\ &= T(0) + 3 c (H\_{n + 1} - 1 - \frac{1}{2}) - c (H\_n - 1) \\ &= 2 c H\_n + (T(0) - 2 c) + \frac{3c}{n + 1} \\ T(n) &= 2 c (n + 1) H\_n + (T(0) - \frac{7 c}{2}) (n + 1) + 3 c \\ &\sim 2 c n \ln n \end{align\*} $$ Here $H\_n$ is the $n$-th harmonic number: $$ H\_n = \sum\_{1 \le k \le n} \frac{1}{k} = \ln n + \gamma + O(1/n) $$

---

The recurrence $x\_{n + 1} - a\_n x\_n = f\_n$ can always be reduced to a telescoping sum at the left side by multiplying by the *summing factor*: $$ (a\_n a\_{n - 1} \ldots a\_0)^{-1} $$ $$ \frac{x\_{n + 1}}{a\_n a\_{n - 1} \ldots a\_0} - \frac{x\_n}{a\_{n - 1} \ldots a\_0} = \frac{f\_n}{a\_{n + 1} a\_n \ldots a\_0} $$

---
Tags: recurrence-relation
---


# Question
Title: How are data types related to information theory?
I was just reading from wikipedia the following about information:

> From the stance of information theory, information is taken as a sequence of symbols from an alphabet, say an input alphabet χ, and an output alphabet ϒ. Information processing consists of an input-output function that maps any input sequence from χ into an output sequence from ϒ. The mapping may be probabilistic or determinate. It may have memory or be memoryless.

I'm just guessing here, but is the input alphabet the two states of a bit (0 and 1) and the output alphabet governed by the datatypes of the executing program when those bits are accessed?

# Answer
**Interpretation: The Link Between Data Types and Information Theory**
I believe the missing link between these two topics, information theory and data types, is interpretation. Interpretation is essentially the "input-output function" for which output (meaning) is derived from input (data). Whether the interpretation is being performed by a computer, at compile-time or run-time, or a human is relative to the task at hand.

At any rate, data types are language-defined/user-defined interpretations of an input alphabet to an output alphabet. Also, language-defined data types usually have a direct relation to the size of storage locations on a computer.

**Probabilistic vs. Deterministic "Mapping"**
When determining the output based on a given input, is the output definite (deterministic) or is the output uncertain/ambiguous (probabilistic)?

**Memory vs. Memoryless "Mapping"**
When determining the output based on a given input, does the determining process require memory?
> 5 votes

---
Tags: programming-languages, information-theory
---


# Question
Title: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?
$L = \\{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \\} $

Is this language a context free language? If yes give a PDA. If no, give a proof.

The pumping lemma for context free languages doesn't seem to work here.

Let $p\>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$.

For any string of the form $a^ib^j \ s.t.$:

1. $ j\lt i-1$ choose $v=a, \ x=\epsilon, \ y=\epsilon$
2. $ j\gt 2i+1$ choose $v=\epsilon, \ x=\epsilon, \ y=b$
3. $ j = i-1$ choose $v=a, \ x=\epsilon, \ y=b$
4. $ j = 2i+1$ choose $v=a, \ x=\epsilon, \ y=b$
5. $ j\gt i,\ j\lt 2i $ choose $v=a, \ x=\epsilon, \ y=b$

# Answer
> 5 votes
It is context Free.

You can see it as a union of two languages: $L\_1$ where $j\>2i$ and $L\_2$ which is very similar to the one of this question.

More information you can find in this question.

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


# Question
Title: Matching Lemma with infinitely many symbols
I was reading about Universal Turing Machines.

I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number of ones.

This is used to match strings of ones between two tapes.

Now I wonder, would there also be a TM or a method of implementation of a TM which can match two strings? To me it intuitively appears, that inifinitely many symbols implies infinitely many states for the machine, and an example workflow may look like: found symbol X, enter state stateX, exit stateX to state readnextchar if again X was found on the second tape.

Would that not mean an infinitely long transition table? or is there an way to represent a table in a smaller way?

if the symbols are represented via some kind of place value system, e.g. decimal, binary, would that shorten the transition table length?

# Answer
> 3 votes
You can allow inifite alphabets because they can be modeled to fit the original Turing machine model.

Assume without loss of generality¹ that the alphabet is $\mathbb{N}$. Then, any tape content

$\qquad n\_1 n\_2 \dots n\_k$

can be translated to a $\\{0,1\\}$-encoded TM tape like this:

$\qquad \\# \operatorname{bin}(n\_1) \\# \operatorname{bin}(n\_2) \\# \dots \\# \operatorname{bin}(n\_k) \\#$,

where $\operatorname{bin}(a)$ is the binary encoding of $a$.

Of course you also have to translate the transition function. So, if you have $(a,q) \to (b,q')$ in the original machine, you'll need a chain of otherwise irrelevant states that accepts $\operatorname{bin}(a)$ while moving from $q$ to $q'$.

Now, this assumes you'll still have a finite state graph and transition function. Note that this is not a restriction: you can easily implement counters *on the tape* (as opposed to in the states).

---

1. There are models on uncountable alphabets; these are not compatible in general.

# Answer
> 4 votes
Turing machines can simulate whatever algorithm you can actually program. So if you can solve your problem by writing a program in C or python (for example), then a Turing machine can also solve your problem.

The most general statement of this principle - everything that is computable can be computed using a Turing machine - is known as the Church-Turing hypothesis. For the specific case of languages like C or python, we know that this hypothesis is true - in principle you can convert every program in C or python to an equivalent Turing machine. The Turing machine would be a lot slower, though. (But only by a polynomial amount!)

For your specific problem, you can allocate a specific location in the tape for your the variables you need, and then update them as you go. The number of states in the Turing machine is proportional (more or less) to the number of instructions in assembly code for your algorithm. Actually programming Turing machines is hard and somewhat pointless. Memory handling is particularly awkward, but Turing machines can implement arrays, tables, and other data structures by allocating special areas on the tape and maintaining them. Perhaps you will hear more about that later in your class.

Finally, for the reason you mention, the tape alphabet is always finite. Without loss of generality, we can assume that it contains only zero and one, though that might make programming the Turing machine even harder. Data structures such as strings and numbers can be encoded in just the same way that they are encoded in your computer - as a string of zeroes and ones.

---
Tags: turing-machines, machine-models
---


title: Length-preserving one-way functions

text:
# Question
Title: Length-preserving one-way functions
Unfortunately my background in computational complexity is still weak, but I am working on it.

As I understand, the question of existence of one-way functions is very important in the field.

Assume there are one way-functions, how it can be shown that there exist one-way functions which are length preserving?

# Answer
Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$.

Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|g(x)| \le p(|x|)$ for all $x$ Define

$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way.

We now have to force $|x| = |f(x)|$.

This we can do by taking $p(|x|)$ bits as input and taking only $|x|$ of it into account, i.e

$f(x||y) = g'(x)$ for $|y| = p(|x|) - |x| + 1$.

Strong one-wayness of $f$ follows from the strong one-wayness of $g'$.

Had $f$ not been strongly one way, we could query a PPT adversary of $f$ for $z = f(y)$ get $x = x\_1 || \ldots || x\_n$ back and try for each $m \in \[n\]$ whether $g'(x\_1||\ldots||x\_m) = z$ and eventually find a preimage of $z$ under $g'$ in polynomial time with non negligible probability. Conradiction.

*See the original proof here.*
> 7 votes

---
Tags: complexity-theory, cryptography, one-way-functions
---


# Question
Title: Is there a strictly non-deterministic one-counter language whose complement is one-counter?
Let $A= \\{L \mid L \\;\text{is one-counter and \\(\bar{L}\\) is also one-counter} \\}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $ A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example, let $P =\\{ ww^r\\}$. Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic. Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?

# Answer
In response to Shaull's comment above :

The first one is an image of 1-counter accepting $a^ib^j$ s.t. $j\<i$

The secong one is an image of 1-counter accepting $a^ib^j$ s.t. $j\>i,\ j\<2i$

The third one is an image of 1-counter accepting $a^ib^j$ s.t. $j\>2i$

Here a/-/plus means on seeing a, irrespective of the counter value, increment the counter. b/\>1?/sub means on seeing b, if counter value is greater than 1, then decrement the counter.

nop =\> no operation

$\lambda $ =\> empty string
> -1 votes

---
Tags: formal-languages, automata, closure-properties, pushdown-automata
---


# Question
Title: Does closure against countable union survive union of classes?
A class of languages $\mathcal{C}$ is *closed under countable union* (*cucu*) if for all series of languages in $\mathcal{C}$ ($(L\_i)\_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language $\bigcup\_{i\in\mathbb{N}}L\_i = \\{x\mid \exists i\in\mathbb{N}: x \in L\_i\\}$ is an element of $\mathcal{C}$.

As we know most (if not all but $\mathsf{ALL} = \wp(\Sigma^\*)$) interesting complexity classes are not closed under countable union as every Language $L$ is the countable union of some singleton Laguages $\\{w\_i\\}$.

However there are some classes of **decidable** languages which are cucu like:

* $\\{\\{w\in\Sigma^\*\mid |w| \leq i\\}\mid i\in\mathbb{N}\\}$
* $\\{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\\}$
* every $\mathcal{C}$ s.t. every $L \in \mathcal{C}$ is cofinite

---

My questions:

1. Let $\mathcal{C},\mathcal{C'} \subset \mathsf{REC}$ be two classes of decidable languages s.t. both are cucu. Is $\mathcal{C} \cup \mathcal{C'}$ cucu?
2. Is there some "real" complexity class (i.e. defined by some machine model, grammar type, $\lambda$-calculus restriction etc.) that is cucu? (You may restrict it artificially (e.g. NFA, where each final state has a path to another final state), if it fits otherwise.)
3. **Edit** (after Yuval Filmus' answer): Given $\mathcal{C},\mathcal{C'}$, as in (1), does the closure of $\mathcal{C} \cup \mathcal{C'}$ under countable union only contain decidable languages?

(1) is the main question, (2+3) only addenda.

# Answer
> 2 votes
The answer to (3) is yes. Suppose that $S \subseteq \mathcal{C} \cup \mathcal{C}'$. Then $S$ is countable, because $\mathcal{C}\cup\mathcal{C'}$ contains only decidable languages of which there are only countable many. Now let $T = S \cap \mathcal{C}$, $T' = S \cap \mathcal{C}'$. By assumption $L = \bigcup T \in \mathcal{C}$, $L' = \bigcup T' \in \mathcal{C}'$. Since $L,L'$ are decidable, $L \cup L'$ is decidable.

# Answer
> 2 votes
The answer to (1) is **no**:

Given $L \in \mathcal{C} = \\{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\\}$ and $L' \in \mathcal{C'} = \\{n\text{-}\mathrm{UNSAT}\mid n\in\mathbb{N}\\}$ the union $L\cup L'$ does contain satisfiable and unsatisfiable formulas, which non of the languages in $\mathcal{C}\cup\mathcal{C'}$ do.

---

As Yuval Filmus indirectly pointed out the countable union of sets in $\mathcal{C}\cup\mathcal{C'}$ is just a finite union of languages $L \in \mathcal{C}$ and $L' \in \mathcal{C'}$ since they both are closed under countable union and any series of languages in $\mathcal{C}\cup\mathcal{C'}$ can be partitioned into two series of languages in $\mathcal{C}$ and $\mathcal{C'}$ respectively.

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


# Question
Title: Does Peterson's 2-process mutual exclusion algorithm account for dying processes?
I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the critical section.

In the picture, if process 1 is stopped, the rest of the processes behind process 1 will execute up to where of process 1 is but then loop.

What happens if the process that reaches the critical section first dies before leaving it?

# Answer
> 1 votes
This depends on how locks are implemented. If you do it as in the Wikipedia article, i.e. guarding the critical section with one boolean per process¹, you are certainly in trouble. If one process dies, it never resets its flag so the other process loops forever.

In practice, you can safeguard your code against many ways of dying. For example, take this Java-style implementation:

```
flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

```

This will make sure the flag is reset whatever happens in the critical section, as long as the system is handling the error. In Java, that is true even for stack and heap overflows. So unless the process literally vanishes (`kill`², processor failure, network disconnect, ...) you are safe. Note that most non-critical software fails in these cases -- how can it handle an error it it's not running? -- so that has to be accepted in many cases. You can handle inconsistencies upon restart if necessary.

If you use proper, language-level locks, the runtime system may handle vanishing lock owners, i.e. release locks with dead owners. You can simulate this yourself by giving each process a dead man's switch the others can read, or check directly whether the lock owning process is still alive (if the system supports it).

---

1. That does not scale well, anyway.
2. In Java, I think `finalize` should execute even on `kill`, but this is not guarenteed by the spec. `kill -9` is probably a death sentence for any solution that requires the dying process to do something.

# Answer
> 1 votes
Look at the assumptions, specifically that no process stays in the critical section indefinitely (that certainly includes just going away). I don't think there is a way to solve that general problem with any synchronization mechanism.

This solution is also *only* for two processes, there are solutions for $n$ processes around.

---
Tags: programming-languages, concurrency, mutual-exclusion
---