title: Bin packing problem or not?

text:
# Question
Title: Bin packing problem or not?
Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items):

Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to maximize the number of items in the bins subject to:

* One bin contains at most one item.
* If item $i$ is on bin $j$ then $g\_{ij}\geq1$ must hold now if all other bins are empty.
* If item $i$ is on bin $j$ (so $g\_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$, then $g\_{ij}\geq g\_{ij^\prime}$ and $g\_{i^\prime j^\prime}\geq g\_{i^\prime j}$ must both hold now.
* If item $i$ is on bin $j$ (so $g\_{ij}\geq1$ must hold now) and item $i^\prime$ is on bin $j^\prime$ (so $g\_{ij}\geq g\_{ij^\prime}$ and $g\_{i^\prime j^\prime}\geq g\_{i^\prime j}$ must both hold now) and item $i^{\prime\prime}$ is on bin $j^{\prime\prime}$, then $g\_{ij}\geq g\_{ij^\prime}+g\_{ij^{\prime\prime}}$ and $g\_{i^\prime j^\prime}\geq g\_{i^\prime j}+g\_{i^\prime j^{\prime\prime}}$ and $g\_{i^{\prime\prime} j^{\prime\prime}}\geq g\_{i^{\prime\prime} j}+g\_{i^{\prime\prime} j^{\prime}}$ must all hold now.
* And so on and so forth.
* In general I will have the following constraint: $g\_{ij}x\_{ij}\geq\sum\limits\_{i^\prime=1,\\;i^\prime \neq i}^{M}\sum\limits\_{j^\prime=1,\\;j^\prime \neq j}^{N}g\_{ij^\prime}x\_{i^\prime j^\prime}$, where $x\_{ij}$ equals $1$ if item $i$ is in bin $j$ and equals $0$ otherwise.

Finally, I have the following problem:

Maximize $\sum\limits\_{i=1}^{M}\sum\limits\_{j=1}^{N}x\_{ij}$

subject to

* $\frac{g\_{ij}x\_{ij}}{\sum\limits\_{i^\prime=1,\\;i^\prime \neq i}^{M}\sum\limits\_{j^\prime=1,\\;j^\prime \neq j}^{N}g\_{ij^\prime}x\_{i^\prime j^\prime}}\geq x\_{ij},\\; \forall i, j,$ (C1)
* $\sum\limits\_{j=1}^{N}x\_{ij}\leq1,\\; \forall i,$ (C2)
* $\sum\limits\_{i=1}^{M}x\_{ij}\leq1,\\; \forall j,$ (C3)

and $x\_{ij}\in\\{0, 1\\},\\; \forall i, j,$ (C4)

The input of the problem is $M$, $N$, and $g\_{ij},\\;\forall i,j$. The right hand side of constraint (C1) is to say that when item $i$ is not in bin $j$ (i.e., $x\_{ij}=0$) then (C1) is not violated. (C2) and (C3) say that one item goes to one bin and one bin contains one item, respectively. Finally, (C4) is the variable of the problem which is a binary variable.

My question is: Can I say that this problem is a bin packing problem and it is therefore NP-hard? If not, Can you suggest a reduction idea from an NP-complete problem?

Thank you for your help.

# Answer
> 9 votes
You can't simply say: "This is a bin packing problem and therefore NP-hard."
Consider the problem of $N$ unit bins and $M$ unit items with the target of maximizing the usage of the bins. Clearly this is also a bin packing problem, but it is not NP-hard.

However, you can reduce to the decision variant of your problem from partition:

> Given a set of items with sizes $a\_1, \dotsc, a\_k$, can it be partitioned into two subsets of equal size.

Given items $a\_1, \dotsc, a\_k$, we construct an instance of your problem as follows:

* Let $A\_i = \sum\_{j=1}^i a\_j$ amd $A=A\_k$.
* We introduce $2A+2$ items and $2A+2$ bins.
* $g\_{i,j} = \begin{cases} A-a\_l & A\_{l-1}\<i=j\leq A\_l\\ A-a\_l & A+A\_{l-1}\<i=j\leq A+A\_l\\ 0 & A\_{l-1}\<i,j\leq A\_l,~ i\neq j\\ 0 & A+A\_{l-1}\<i,j\leq A+A\_l,~ i\neq j\\ 2 & A\_{l-1}\<i\leq A\_l,~ A+A\_{l-1}\<j\leq A+A\_l\\ 2 & A+A\_{l-1}\<i\leq A+A\_l,~ A\_{l-1}\<j\leq A\_l\\ 0 & j\>2A,~ i\neq j\\ \frac A2 & i=j\>2A\\ 0 & i=2A+1,~ j\leq A\\ 0 & i=2A+2,~ A\<j\leq 2A\\ 1 & \text{otherwise} \end{cases}$
* We ask for an assignment with $\sum\_{i=1}^{A}\sum\_{j=1}^{A} x\_{i,j} \geq A+2$.

The construction works as follows:

* Any solution will satisfy $x\_{i,j}=1 \Rightarrow i=j$.
* Items/bins $i$ with $A\_{l-1} \< i \leq A\_l$ resp. $A+A\_{l-1} \< i \leq A+A\_l$ correspond to $a\_l$. In a solution, exactly one of the groups will be taken, corresponding to $a\_l$ being in the first resp. second set of the partition.
* The threshold can only be reached, if the last two items are placed, ensuring that the partition is into two sets of size $\frac A2$.

---
Tags: complexity-theory, np-complete, optimization, np-hard
---


# Question
Title: Finding constants C and k for big-O of fraction of polynomials
I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the constants $C$ and $k$ in the definition of big-O $$ |f(x)| \leq C|g(x)|, x \> k, $$ when the function $f(x)$ is a fraction of polynomials.

I have tried to concoct my own method, but I am unsure of its correctness. I was inspired by the easy method of finding $C$ and $k$ for a polynomial where for example we can show that $x^3+2x+3$ is $O(x^3)$ by $$ x^3+2x+3 \leq x^3+2x^3+3x^3 = 6x^3 $$ to find $C = 6$ and $k = 1$.

Now, for a fraction of polynomials I am unsure what to do with the denominator. My attempt at a general method is as follows. I would like to show that $\frac{x^4+x^2x1}{x^3+1}$ is $O(x)$. First I divide by the highest term in the denominator to get a $1$ in the denominator: $$ \frac{(x^4+x^2+1)/x^3}{(x^3+1)/x^3} = \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} $$ Now I argue, somewhat analogously to the previous example, that the fractions in the numerator must be less than (when x \> 0) x, and since a smaller denominator makes the expression smaller, setting all the terms in denominator except the $1$ to $0$, I obtain the inequality $$ \frac{x+\frac{1}{x}+\frac{1}{x^2}}{1+\frac{1}{x^3}} \leq \frac{x+x+x}{1+0} = 3x $$ and I find $C = 3$ and $k = 1$.

Now my question is, does this homebrewed method actually work or is it complete nonsense? And if it is nonsense, does anybody know of another general method for finding $C$ and $k$ in instances like this?

Note that I need to find the constants $C$ and $k$, not just show that a given function is big-O of some other function, and the students have had no course in calculus, so I can use no concepts from there, such as limits.

# Answer
> 4 votes
Remember that $O(-)$ is just an upper bound.

Given a rational function $p(x)/q(x)$, you already know how to find $c$, $k$ and $x\_0$ such that $|p(x)|\leq c|x^k|$ for $x\>x\_0$. By similar arguments, you can show that $|q(x)|\ge 1$ for all $x$ greater than some $x\_1$. Therefore, for all $x\>\max\\{x\_0,x\_1\\}$, we have $|p(x)/q(x)| \leq |p(x)| \leq c|x^k|$ so $p(x)/q(x) = O(x^k)$.

# Answer
> 6 votes
It works if the denominator doesn't have negative coefficients. Consider, however, $$ \frac{x}{x-1}. $$ As $x$ tends to infinity, this is $O(1)$. However, your method would give $$ \frac{x}{x-1} = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-1} = \infty, $$ which is not very helpful. The problem is that when $x = 1$, the denominator is not positive. In this case it is zero, but for an example like $$ \frac{x}{x-2} = \frac{1}{1-\tfrac{2}{x}} \leq \frac{1}{-1} = -1, $$ the inequality is in fact wrong.

Often when considering $O(f(x))$, we assume that $f(x)$ is always positive. But sometimes it isn't, and then the assumption that we're making is that $f(x)$ is *eventually* positive. This is not usually explained when big O notation is defined, but it's the reason behind the extra quantifier "for large enough $x$" which appears in the full definition of big O; this quantifier is only needed when $f(x)$ is not always positive but only eventually positive.

The way to fix the argument is now clear. If $f(x)$ is eventually positive, then take some $y$ such that $f(x) \> 0$ for all $y \geq x$, and now apply the method. For example, if $f(x) = x/(x-1)$ then any $y \> 1$ would do, say $y = 2$. In that case we have $$ f(x) = \frac{1}{1-\tfrac{1}{x}} \leq \frac{1}{1-\frac{1}{2}} = 2 $$ for $x \geq 2$.

More generally, suppose that $f(x) = C p(x)/q(x)$, where $p,q$ are monic polynomials (leading coefficient is $1$) and are eventually positive, and $C \> 0$. Then for all $\epsilon \> 0$ there is $y$ such that for all $x \geq y$, $$ (C-\epsilon) x^{\deg p - \deg q} \< f(x) \< (C+\epsilon) x^{\deg p - \deg q}. $$ (Exercise.)

# Answer
> -1 votes
Compare the definition of the Bachman-Landau notations to the definition of a limit when $n \to \infty$, the relation between them is enough for cars like this.

---
Tags: asymptotics, polynomials
---


# Question
Title: What memory locations will the CPU fetch instructions from with instruction length of 16bits
While reading Stallings OS Internals and Design, I run into problem. Here is example from the book.

> For example, consider a simplified computer in which each instruction occupies one 16-bit word of memory. Assume that the PC is set to the location 300. On succeeding instruction cycles, it will fetch instructions from locations 301, 302, ...

My question is: If the length of instructions is 16bits, and the smallest addressable unit of the memory is 1B, why on succeeding instruction cycles it will fetch instructions from locations 301 and 302, and not multiples of two, 302 and 304?

Is the memory then organised as a sequence of 16bit long memory words?

# Answer
I too read the book. If Dr. Stallings has quoted this, the memory locations 301 and 302 must be referring to word-wise and not byte-wise locations.
> 1 votes

---
Tags: operating-systems, memory-management
---


# Question
Title: What languages does a (1-way) quantum finite state automata recognize?
Sorry if this is well known, but most of the research is paywalled.

So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down.

Thanks!

# Answer
@Vor's answer was great, but incomplete. I found an amazing paper, the introduction of which answered virtually every question I had (and confirmed or disproved many of my suspicions):

*Characterizations of one-way general quantum finite automata*

(Theoretical Computer Science, Volume 419, 17 February 2012, Pages 73-91, ISSN 0304-3975)

* Lvzhou Li
* Daowen Qiu
* Xiangfu Zou
* Lvjun Li
* Lihua Wu
* Paulo Mateus

You can download the paper at Paulo Mateus' website: http://sqig.math.ist.utl.pt/pub/MateusP/12-LQZLWM-qfamix.pdf

Abstract:

> Generally, unitary transformations limit the computational power of quantum finite automata (QFA). In this paper, we study a generalized model named one-way general quantum finite automata (1gQFA), in which each symbol in the input alphabet induces a trace-preserving quantum operation, instead of a unitary transformation. Two different kinds of 1gQFA will be studied: measure-once one-way general quantum finite automata (MO-1gQFA) where a measurement deciding to accept or reject is performed at the end of a computation, and measure-many one-way general quantum finite automata (MM-1gQFA) where a similar measurement is performed after each trace-preserving quantum operation on reading each input symbol.
>
> We characterize the measure-once model from three aspects: the closure property, the language recognition power, and the equivalence problem. We prove that MO-1gQFA recognize, with bounded error, precisely the set of all regular languages. Our results imply that some models of quantum finite automata proposed in the literature, which were expected to be more powerful, still cannot recognize non-regular languages.
>
> We prove that MM-1gQFA also recognize only regular languages with bounded error. Thus, MM-1gQFA and MO-1gQFA have the same language recognition power, in sharp contrast with traditional MO-1QFA and MM-1QFA, the former being strictly less powerful than the latter. Finally, we present a necessary and sufficient condition for two MM-1gQFA to be equivalent.

Thank you everyone who responded.
> 2 votes

# Answer
Quantum finite automata (**QFA**s) are quantum counterparts of the usual finite automata.

In \[1\] it is shown that 1-way QFAs recognize a proper subset of the regular languages:

**Proposition 6**: Let $L$ be any language recognized by a 1QFA with bounded error. Then $L$ is regular.

**Proposition 7**: The language $L = \\{a,b\\}^\*a$ cannot be recongized by a 1QFA with bounded error.

However in \[2\] :

... Our first results consider relations between 1-way QFAs and 1-way reversible automata. Clearly, a 1-way reversible automaton is a special case of a QFA and, therefore, cannot recognize all regular languages. It is a natural question whether 1-way QFAs are more powerful than 1-way reversible automata. Interestingly, the answer depends on the accepting probability of a QFA. If a QFA gives a correct answer with a large probability (greater than 7/9), it can be replaced by a 1-way reversible automaton. However, this is not true for 0.68... and smaller probabilities.

Then, we show that QFAs can be much more space-efficient than deterministic and even probabilistic finite automata. Namely, there is a 1-way QFA that can check whether the number of letters received from the input is divisible by a prime p with only $O(\log p)$ states (this is equivalent to $\log \log p$ bits of memory). Any deterministic or probabilistic finite automaton needs p states ($\log p$ bits of memory). We think that this space-efficient quantum algorithm may be interesting for design of other quantum algoritms as well....

For a quick introduction see:
> 6 votes

---
Tags: finite-automata, quantum-computing
---


# Question
Title: Selecting random points at general position
How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line?

The following algorithm eventually works, but seems highly inefficient:

1. Select $n$ points at random.
2. Check all $O(n^3)$ triples of points. If any of them are on the same line, then discard one of the points, select an alternative point at random, and go back to 2.

Is there a more efficient algorithm?

# Answer
Here's an approach that I think achieves $O(n^2)$ running time, as long as the points are not too dense (as long as $n$ is not too large compared to the size of the region).

Store the set of all slopes of lines between any pair of points. There are $O(n^2)$ pairs of points, and each pair of points determines line; add that line to the set. I suggest you store this as a hash table that maps the slope $s$ to the set of pairs $(P,Q)$ of points which are at slope $s$ from each other.

Now to add a new point, pick a point $R$ uniformly at random. Pair $R$ up with each other point, say $P$. Compute the slope of the line from $P$ to $R$. Look up that slope in the hash table, and see whether the corresponding set contains the point $P$. The latter can be done in $O(1)$ expected time if you use suitable data structures for the hash table and for storing the set (in particular, the entry corresponding to slope $s$ can be a hash-set of all of the points that participate in a pair whose slope is $s$). Since $R$ can be paired up with $n$ other points, this check will take $O(n)$ expected time.

Now as long as the number of points is not too dense (so that you don't reject a point more than a constant fraction of the time), the expected running time will be $O(n^2)$.
> 3 votes

# Answer
You can improve on your algorithm while keeping the general idea:

1. Draw 2 points at random and add them to the (previously empty) set of selected points.
2. Draw a new point at random. Check all triples involving two of the previously selected points and the new point. If one of them fails, dicard the new point. Otherwise add it to the set of selected points.
3. If you have $n$ nodes selected, terminate. Otherwise goto 2.
> 2 votes

# Answer
There's a simple approach with running time proportional to $2000 n^2$ (for your example parameters).

Keep a hash table that stores all of the points that are forbidden. For each pair of points $P,Q$, you extend the line from $P$ to $Q$ and add to the hash table all points with integral coefficients that are on that line. Each time you pick a new point, you check it against the hash table (if it is forbidden, go back and pick a new one), then you pair it up with all other points and add to the hash table.

This might work well in practice if the specified range is small, but if the range is large, it will scale poorly.
> 2 votes

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


# Question
Title: Asymptotic Runtime of Interrelated Functions
I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me...

How would I find the asymptotic runtime $S(n)$ and $T(n)$?

$$ \begin{align\*} S(n) &= 2S(n/4) + T(n/4) \\ T(n) &= S(n/2) + 2T(n/2) \end{align\*} $$

# Answer
> 3 votes
You can expand the definition of $T(n)$ as follows: $$ \begin{align\*} T(n) &= S(n/2) + 2T(n/2) \\ &= S(n/2) + 2S(n/4) + 4T(n/4) \\ &= S(n/2) + 2S(n/4) + 4S(n/8) + 8T(n/8) \\ &= \dots \\ &= S(n/2) + 2S(n/4) + 4S(n/8) + \dots. \end{align\*} $$ Substituting this in the definition of $S(n)$, we get $$ S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + \dots. $$ Let's try to estimate the value of $S(n)$. Guessing $S(n) = n^\alpha$ and eliminating the common term $n^\alpha$, we get $$ \begin{align\*} 1 &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} + \frac{2}{16^\alpha} + \frac{4}{32^\alpha} + \dots \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} \left(1 + \frac{2}{2^\alpha} + \frac{4}{4^\alpha} + \dots\right) \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha} \frac{1}{1-2/2^\alpha} \\ &= \frac{2}{4^\alpha} + \frac{1}{8^\alpha-2 \cdot 4^\alpha} \\ &= \frac{2\cdot 8^\alpha - 3 \cdot 4^\alpha}{32^\alpha -2\cdot 16^\alpha} \\ &= \frac{2\cdot 2^\alpha - 3}{8^\alpha -2\cdot 4^\alpha}. \end{align\*} $$ Letting $\beta = 2^\alpha$, we get the equation $2\beta - 3 = \beta^3 - 2\beta^2$, with solutions $\beta = 1, (1\pm \sqrt{13})/2$ and so $\alpha = 0, \log\_2(1+\sqrt{13})-1$. The second solution is $\alpha \approx 1.20337$, and is the dominant one. We conclude that $S(n) \approx n^\alpha$, at least in the sense that $\log\_n S(n) \to \alpha$. (See below for a more thorough argument.)

Since $S(n) \geq T(n/4)$ and $T(n) \geq S(n/2)$, also $\log\_n T(n) \to \alpha$.

---

I have claimed that the recurrence for $S(n)$ implies a certain asymptotics for $S(n)$. Here is how to formally prove this using the Akra–Bazzi theorem. We can cut the recurrence after $k+2$ terms to obtain a *lower bound* recurrence: $$ S\_k(n) = 2S\_k(n/4) + S\_k(n/8) + \dots + 2^kS\_k(n/2^{k+3}). $$ Clearly $S(n) \geq S\_k(n)$. The Akra–Bazzi theorem states that $S\_k(n) = \Theta\_k(n^{p\_k})$, where $p\_k$ is the unique solution of $$ \frac{2}{4^{p\_k}} + \frac{1}{8^{p\_k}} + \dots + \frac{2^k}{2^{(k+3)p\_k}} = 1. $$ We conclude that $S(n) = \Omega\_k(n^{p\_k})$ for all $k$. As $k\to\infty$, it is not hard to check that $p\_k \to \alpha$, and so $S(n) = \Omega\_{\epsilon}(n^{\alpha-\epsilon})$ for all $\epsilon \> 0$.

In order to obtain an estimate from above, we have to work a bit harder. Start with the expression $$ \begin{align\*} T(n) &= S(n/2) + 2S(n/4) + \dots + 2^{k-1}S(n/2^k) + 2^kT(n/2^k) \\ &\leq S(n/2) + 2S(n/4) + \dots + 2^{k-1}S(n/2^k) + 2^kS(n/2^{k-2}), \end{align\*} $$ since $T(m/4) \leq S(m)$. Now we can set up an upper bound recurrence: $$ S'\_k(n) = 2S'\_k(n/4) + S'\_k(n/8) + \dots + 2^{k-1}S'\_k(n/2^{k+2}) + 2^kS'\_k(n/2^k). $$ Clearly $S'\_k(n) \geq S(n)$. Again using the Akra–Bazzi theorem we can estimate $S'\_k(n) = \Theta\_k(n^{q\_k})$, where $q\_k$ is a solution of $$ \frac{2}{4^{p\_q}} + \frac{1}{8^{p\_q}} + \dots + \frac{2^{k-1}}{2^{(k+2)q\_k}} + \frac{2^k}{2^{kq\_k}} = 1. $$ Again we see that $q\_k \to \alpha$, and so for all $\epsilon \> 0$, $S(n) = O\_\epsilon(n^{\alpha + \epsilon})$.

Together, upper and lower bound easily imply $\log\_n S(n) \to \alpha$.

# Answer
> 4 votes
Here is one approach. Plug in the definition of $T(n)$ into your first equation, and we get

$$S(n) = 2S(n/4) + S(n/8) + 2T(n/8).$$

Now plug in again and we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4T(n/16).$$

Keep plugging in and eventually we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + 8S(n/64) + \dots + O(1).$$

Now solve that recurrence relation for $S(n)$, noting that now you have a single function (you don't have two interrelated functions any longer).

# Answer
> 2 votes
Use the substitution $n = 2^k$, the result is a system of linear recurrences that is easy to solve.

# Answer
> 1 votes
This answer expands on vonbrand's suggestion. Define $s(m) = S(2^m)$ and $t(m) = T(2^m)$. Then $$ \begin{align\*} s(m) &= 2s(m-2) + t(m-2), \\ t(m) &= s(m-1) + 2t(m-1). \end{align\*} $$ We write this in matrix notation: $$ \begin{pmatrix} s(m) \\ t(m) \\ s(m-1) \\ t(m-1) \end{pmatrix} = \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} s(m-1) \\ t(m-1) \\ s(m-2) \\ t(m-2) \end{pmatrix} $$ The eigenvalues of this matrix are $(1 \pm \sqrt{13})/2,1,0$; the Perron–Frobenius eigenvalue is $(1+\sqrt{13})/2$, and its eigenvector is strictly positive. This means that asymptotically, $s(m),t(m) = \Theta(((1+\sqrt{13})/2)^m)$. Substituting $n = 2^m$, we obtain $S(n),T(n) = \Theta(n^\alpha)$, where $\alpha = \log\_2 \frac{1+\sqrt{13}}{2}$.

We can find the exact constants by diagonalizing the matrix: $$ \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \tfrac{1}{2}(1-\sqrt{13}) & 0 \\ 0 & 0 & 0 & \tfrac{1}{2}(1+\sqrt{13}) \end{pmatrix} \begin{pmatrix} 0 & -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} \\ -\tfrac{1}{3} & \tfrac{1}{3} & -\tfrac{2}{3} & -\tfrac{1}{3} \\ \tfrac{-3+3\sqrt{13}}{18\sqrt{13}} & \tfrac{-9+3\sqrt{13}}{8\sqrt{13}} & -\tfrac{2}{3\sqrt{13}} & -\tfrac{1}{3\sqrt{13}} \\ \tfrac{3+3\sqrt{13}}{18\sqrt{13}} & \tfrac{9+3\sqrt{13}}{8\sqrt{13}} & \tfrac{2}{3\sqrt{13}} & \tfrac{1}{3\sqrt{13}} \end{pmatrix} $$ Therefore $$ \begin{align\*} \begin{pmatrix} s(m+1) \\ t(m+1) \\ s(m) \\ t(m) \end{pmatrix} &= \begin{pmatrix} 0 & 0 & 2 & 1 \\ 1 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}^m \begin{pmatrix} s(1) \\ t(1) \\ s(0) \\ t(0) \end{pmatrix} \\ &= \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & (\tfrac{1}{2}(1-\sqrt{13}))^m & 0 \\ 0 & 0 & 0 & (\tfrac{1}{2}(1+\sqrt{13}))^m \end{pmatrix} \begin{pmatrix} 0 & -\tfrac{1}{3} & \tfrac{1}{3} & \tfrac{2}{3} \\ -\tfrac{1}{3} & \tfrac{1}{3} & -\tfrac{2}{3} & -\tfrac{1}{3} \\ \tfrac{-1+\sqrt{13}}{6\sqrt{13}} & \tfrac{-3+\sqrt{13}}{6\sqrt{13}} & -\tfrac{2}{3\sqrt{13}} & -\tfrac{1}{3\sqrt{13}} \\ \tfrac{1+\sqrt{13}}{6\sqrt{13}} & \tfrac{3+\sqrt{13}}{6\sqrt{13}} & \tfrac{2}{3\sqrt{13}} & \tfrac{1}{3\sqrt{13}} \end{pmatrix} \begin{pmatrix} s(1) \\ t(1) \\ s(0) \\ t(0) \end{pmatrix} \\ &= \begin{pmatrix} 0 & -1 & \tfrac{1}{2}(5+\sqrt{13}) & \tfrac{1}{2}(5-\sqrt{13}) \\ 0 & 1 & \tfrac{1}{2}(1-\sqrt{13}) & \tfrac{1}{2}(1+\sqrt{13}) \\ -1 & -1 & \tfrac{1}{2}(-3-\sqrt{13}) & \tfrac{1}{2}(-3+\sqrt{13}) \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ \tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) \\ \frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) \\ \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)) \end{pmatrix} \end{align\*} $$ Finally, $$ \begin{align\*} s(m) &= -\tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) -\tfrac{1}{2}(3+\sqrt{13})\frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) + \tfrac{1}{2}(\sqrt{13}-3) \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)), \\ t(m) &= \tfrac{1}{3} (-s(1)+t(1)-2s(0)-t(0)) +\frac{(\tfrac{1}{2}(1-\sqrt{13}))^m}{6\sqrt{13}} ((-1+\sqrt{13})s(1)+(-3+\sqrt{13})t(1)-4s(0)-2t(0)) + \frac{(\tfrac{1}{2}(1+\sqrt{13}))^m}{6\sqrt{13}} ((1+\sqrt{13})s(1)+(3+\sqrt{13})t(1)+4s(0)+2t(0)). \end{align\*} $$

---
Tags: algorithms, algorithm-analysis, asymptotics, search-algorithms, master-theorem
---


title: Recursive Algorithm Analysis

text:
# Question
Title: Recursive Algorithm Analysis
$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$

I have been trying to solve this question but I could not find anything.

My approach:

$n = 2^k$

$S(k) = T(2^n)$ and $S(k/2) = T(2^{n/2})$

Finally: $S(k) = 2^{1+k/2} \cdot S(k/2) + c \cdot \lg(k) $

After that, I tried to build recursion tree but I can not find the sum. Do you have any ideas?

Thanks in advance.

# Answer
Let's consider the recurrence without the big $\Theta$. Then (using base two logarithms) $$ \begin{align\*} T(n) &= 2n^{1-1/2} T(n^{1/2}) + \log n \\ &= 4n^{1-1/4} T(n^{1/4}) + \log n (1 + n^{1-1/2}) \\ &= 8n^{1-1/8} T(n^{1/8}) + \log n (1 + n^{1-1/2} + n^{1-1/4}) \\ &= \cdots \\ &= (\log n) n^{1-1/\log n} T(n^{1/\log n}) + \log n (1 + n^{1-1/2} + n^{1-1/4} + \dots + n^{1-1/\log n}) \\ &= 2n\log n T(2) + n\log n \left(\frac{1}{n} + \frac{1}{n^{1/2}} + \dots + \frac{1}{2}\right) \\ &= \Theta(n\log n). \end{align\*} $$
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: A string representation of any Turing machine
The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble seeing how this could be true.

If we formally define a Turing machine as having a tape language $\\{0, 1, \sqcup, x\\}$ and input language $\\{0, 1\\}$, then I can sort of see how any Turing machine could be encoded.

However, many books allow other symbols, such as $a$ or $3$, etc., to be part of the input language. I've heard people say that this is okay because we could represent such characters as a string like $0101$ or $1011$ or whatever, much like how Unicode represents code points consisting of multiple code units, or just how any computer represents anything at all!

But here is my problem with this. If we are trying to construct an actual function $f$ from the set of all Turing machines $\mathscr{M}$ to $\mathbb{N}$, then every Turing machine must be encoded in the same way. That is, we can't have encodings of different lengths, so that 01 represents $01$ for one Turing machine and represents $3$ for another. That is, unless we have some encoding at the beginning of each Turing machine which explains how the machine is to be decoded. But even then, this encoding itself must be universal.

The problem is much like the charset problem for HTML pages. That is, that a web browser must know the encoding of the page before it can decipher a command in the HTML to encode the page a certain way. This was solved for web pages by having the encoding command characters (`meta charset=utf-8` for example) be the same in all encodings. But then the encoding itself is stored elsewhere.

Anyway, my question is how we resolve this apparent conundrum. How does one encode a Turing machine with a finite input language of any length so that one can make **one** function from $\mathscr{M}$ to $\mathbb{N}$?

# Answer
> 7 votes
Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet is $\\{1,\ldots,n\\}$ and the states are $\\{1,\ldots,m\\}$. We will encode this Turing machine as the following sequence of statements in English: (the notation $\langle n \rangle$ means to replace $n$ with its decimal representation)

* The number of tape symbols is $\langle n \rangle$.
* The number of states is $\langle m \rangle$.
* The starting state is $\langle s\_0 \rangle$. \[Replace $s\_0$ with the starting state\]
* The accepting states are $\langle s\_1 \rangle$, ..., $\langle s\_k \rangle$. \[Replace $s\_1,\ldots,s\_k$ with the accepting states\]
* When in state 1, upon reading symbol 1, write symbol $\langle \sigma \rangle$ and move $\langle D \rangle$ \[Replace $\sigma$ with the tape symbol and $D$ with either "left" or "right"\]
* ...

This is a description in English over a finite alphabet. In particular, it can be represented in ASCII. So there are only countably many descriptions.

---

As usul mentions, we tacitly assume that the underlying representation of everything in mathematics is a set, just like the description of everything in computers is in binary. Not all sets are finite, but if you only use hereditarily finite sets, then you can avoid forcing the tape alphabet to be $\\{1,\ldots,n\\}$, and instead allow arbitrary hereditarily finite sets. However, that doesn't buy you anything (unless you care about this point for philosophical reasons).

More generally, you might be worried that when I describe a Turing machine I use the symbol $\diamond$, a symbol not covered by the above (it's a set-theoretic "atom"), so this Turing machine doesn't have a description in my formalism. To counter this, I suggest you provide the description of your Turing machine as a LaTeX document (which is what I used when describing the machine in the first place). LaTeX has a finite alphabet (or finitely many possible finite alphabets), so again everything is countable.

---
Tags: turing-machines, encoding-scheme
---


# Question
Title: Can someone interpret what this is asking for
I have this programming problem, but I really cant figure out what it wants me to do. Heres what it is:

> The cube root of a number can be found based on the observation that, if $t$ is an approximation of the cube root of $a$, then $\tfrac13\left(\tfrac{a}{t^2} + 2t\right)$ is a better approximation.
>
> Create a method `double betterCubeRoot(double a, double t)` that will find the cube root of $a$ accurate enough so that the difference between $t^3$ and $a$ is less than 0.0001. Use recursion.
>
> Then write the method `double cubeRoot(double a)` that makes use of the method with 1 as the initial value of $t$. Write a program that will test values both positive and negative.

Can someone please explain what this means. I dont understand how I am supposed to find the cube root of 'a' using the given equation. Thanks.

Here is what i have done:

```
public static double betterCubeRoot (double a, double t)
{
    double tCubed = Math.pow (t, 3);
    double dif = Math.abs (tCubed - a);

    double eq = ((a / (t * t)) + 2 * t) / 3;

    if (dif < 0.001)
    {
        return eq;
    }
    else
    {
        return betterCubeRoot (eq, t) ;
    }
}

```

# Answer
> 2 votes
Guess anything at all for the cube root of $a$: call that value $t$. $t′=\tfrac13(a/t^2+2t)$ is closer to $\sqrt\[3\]{a}$ than $t$ is, so use $t′$ as your next guess. Keep going.

---
Tags: approximation, numerical-analysis
---


# Question
Title: Do the polynomials in "polynomial time" have integer, real or complex coefficients?
This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients?

Everywhere I looked it just says "polynomial expression". I am guessing the polynomial must have integer coefficients?

# Answer
When people say polynomial time, they mean that the time has *polynomial growth*, that is if we denote the time by $T(n)$, then $T(n) = O(n^c)$ for some real $c$. We get the same definition if we only allow integer $c$. Since $T(n)$ is real-valued, it wouldn't make sense to consider complex polynomials here.

The exact running time need not actually be a polynomial. For example, an algorithm running in time $n\log n$ (exactly) still runs in polynomial time, since (for example) $n\log n = O(n^2)$.
> 4 votes

# Answer
What would it even mean to say that "The Turing machine $M$ runs in time at most $(3i+2)n^3$ when given input of length $n$"? So, clearly, the coefficients are real.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: What's the purpose of the "o(1-o)" in the back propagation algorithm
I'm not sure what the purpose of the o(1-o) in the back propagation algorithm achieves? I'm guessing it's related to using the sigmoid function on the output but I'd like to have a proper understanding of the math behind it. Thanks!

# Answer
Backpropagation is a gradient descent algorithm for minimizing the squared error of the learned network on the data given. In order to minimize by following the gradient, you need to know where the gradient points, this is done using calculus.

Along the way of calculating the gradient, you have to find the derivative of the activation function. When you take the most common activation function, i.e. the logistic rule or sigmoid function $o(z) = \frac{1}{1 - e^{-z}}$ and you differentiate it with respect to the neurons' input $z$ then you get $do/dz = o(1 - o)$. Hence, you are correct, this is related to the use of the sigmoid function, and figuring out in which direction the gradient points.

If you want a more thorough description then consult these notes (pdf).
> 1 votes

---
Tags: neural-networks
---


# Question
Title: find a regular expression and FA that each define $L_1 \cap L_2$
I am trying to find a `regular expression` and `finite automaton` that each define $L\_1 \cap L\_2$, where $L\_1 = (ab^\*)^\*$ and $L\_2 = b(a+b)^\*$.

How would I start doing this problem?

So I would draw a FA and when I draw it I would have a complement meaning take anywhere you have a plus, get rid of it and anywhere you didn't have a plus add one in. Am I on the right track?

# Answer
> 6 votes
Hint: Every non-empty string in $L\_1$ starts with $a$. Every string in $L\_2$ starts with $b$.

# Answer
> 4 votes
Hint: Go back and re-read the material in your textbook on regular languages, regular expressions, and finite automata. You might look especially closely at the material on closure properties of regular languages, on computing the intersection of regular languages, on the product construction, and on converting regexps to finite automata. This is a standard textbook exercise that you should be able to solve easily if you understand those topics (and those topics should be covered in any good textbook on finite automata).

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


# Question
Title: A question from Computer Organization on Peak Clock Frequency
Given below are 3 different pipelined processors:

$P\_1:\ 4\ stages\ with\ delays\ \ \ \ 0.6\_{ms}\ \ 0.8\_{ms}\ \ 0.6\_{ms}\ \ 1.1\_{ms}\\ P\_2:\ 4\ stages\ with\ delays\ \ \ \ 2.0\_{ms}\ \ 1.8\_{ms}\ \ 2.0\_{ms}\ \ 1.0\_{ms}\\ P\_3:\ 5\ stages\ with\ delays\ \ \ \ 1.0\_{ms}\ \ 0.8\_{ms}\ \ 1.0\_{ms}\ \ 1.5\_{ms}\ \ 1.5\_{ms}$

One has to find the **Peak Clock Frequencies** of each $\mathbf{P\_i}$. Pipeline buffer register latency is Zero.

I don't know how to solve this, but I've come up with an intuitive formula for calculating peak frequency of clock for processor $P\_i$ as $$\mathcal{C\_{p.f}}=\frac{1}{max(d\_i)}$$ where $d\_i$ is individual stage delay for processor $P\_i$. For example for $P\_2$ it's $\frac{1}{2}KHz = 0.5 KHz$.

```
Now I don't know whether it's the correct way to calculate peak frequency.
If it's not, can anyone tell me what is it?

P.S: I also don't know whether this is the right place to ask this question.
But I didn't have any idea about where to post it otherwise.

```

# Answer
The peak possible frequency is, no doubt, equal to the inverse of maximum time supported by each stage. The stage consuming maximum time is the limiting condition and your anwer is correct.
> 2 votes

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: How fast can we decide whether a given DFA is minimal?
Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA $\mathscr{A}$, compute a corresponding minimal DFA accepting the same language as $\mathscr{A}$. Most of these algorithms run in polynomial time.

However, I wonder whether the decision variant of this problem - "given a DFA $\mathscr{A}$, is $\mathscr{A}$ minimal?" - can be solved more efficiently than actually computing the minimal automaton. Obviously, this can also be done efficiently by running for example Hopcroft's partition-refinement algorithm and then deciding whether all partitions contain precisely one state.

As Yuval Filmus suggests in his answer, the decidability variant can be solved faster, possibly by using the standard algorithms. Unfortunately, I cannot see how (I hope I am not missing an obvious point here).

Yuval points out in the comments here that the best known algorithms (like the one above) run in time $\mathcal{O}(n \log n)$ for constant-sized alphabets. Therefore, I am not only interested in asymptotically significant gains in runtime, as these seem rather unlikely. What bothers me most is that I cannot imagine any "shortcut" that might be drawn from the fact that we are only interested in a yes-no-answer - not even a shortcut that allows for saving an asymptotically negligible amount of time. I feel that every sensible algorithm that decides the minimality of a DFA would have to actually minimize the DFA and see if anything changes during the process.

# Answer
> 6 votes
This might not be exactly the sort of answer you are looking for, but since you asked about decision problems, I thought you might be interested in the complexity of the problem. It is $\mathsf{NL}$-complete.

Now, what does it mean for a DFA to be minimal? There are two properties:

1. Every state is reachable: $\forall q \in Q \\; \exists w \in \Sigma^\*$ such that we can reach $q$ from the start state $s$ by following $w$; in symbols: $s \rightarrow\_w q$.
2. Every pair of states is distinguishable: $\forall q,r \in Q$ with $q \neq r$ $\exists w \in \Sigma^\*$ such that $q \rightarrow\_w s$ and $r \rightarrow\_w t$ and $|\\{s,t\\} \cap F| = 1$ (only one of $s,t$ is an accept state).

Notice that the $x \rightarrow\_w y$ can be computed in log-space (i.e. $\mathsf{L}$; just track your current position as you follow $w$ one letter at a time). Further, there is only a finite number of alternations between $\forall$ and $\exists$ so as a consequence of the Immerman-Szelepcsenyi theorem, we have that the problem is in $\mathsf{NL}$.

The easiest way to see that it is hard for $\mathsf{NL}$ is to notice that property 1 solves $s$-$t$ directed unreachability, which is the prototypical hard problem. But even if you consider only reachable DFAs, the problem is still hard (i.e. property 2 is $\mathsf{NL}$-hard) and you can find a relatively straightforward proof in Lemma 2.2 of Cho & Huynh (1992).

Of course, I used non-determinism, so it is a bit of a cough-out in the way it differs from Hopcroft's algorithm. But we know that $\mathsf{NL} \subseteq \mathsf{L}^2$, so you can use those constructions to get yourself a more space-efficient algorithm than Hopcroft (which by its very nature has to keep track of $n$ many partitions).

---
Tags: algorithms, formal-languages, finite-automata
---


# Question
Title: Maximum Enclosing Convex Polygon of a Given Area
My question is very similar to another solved question. As the title indicates, the major difference in my question is that I need to find the **convex polygon** that encloses the maximum number of points with a given **area** (*instead* of finding the **circle** that encloses the maximum number of points with a given **radius**).

So my question is as the following:

> Given $n$ points $p\_1,\dots,p\_n$ in the plane and an area $A$, find a convex polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

I already checked on the Minimum bounding box algorithms and Convex hull algorithms. I also found some implementations for Minimum bounding polygon. However, those previous algorithms don't consider the concept of determining the convex polygon that encloses **as many points as possible** of a given set of points and **a given area**. Finally I invented an approach to solve the problem but it doesn't work in some cases.

The idea of my approach is to start by finding **the minimum bounding box** for all the points. If the resulting polygon's area is greater than the given area, I cut off one of the edge points according to some technique, then I re-compute the minimum bounding box and test the area. I keep looping until I reach the desired area. I won't get into details with my approach as it's not working properly.

**EDIT**

As a simplified solution, finding **any rectangle** (it doesn't have to be axis-aligned) that encloses the maximum number of points with a given area would be very beneficial and works as a temporary solution for my problem.

# Answer
It sounds like your problem is the following:

> Given $n$ points $p\_1,\dots,p\_n$ in the plane and an area $A$, find a polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

This problem looks pretty tough to me, and I don't have a great algorithm for it, but I'll suggest two schemes. The first solves a simplified version of this problem (for rectangles instead of arbitrary polygons), and the second is a heuristic algorithm that might or might not work "well enough" on real-world instances.

## Simplified variant: rectangles

Suppose we focus on the easier case where $\mathcal{P}$ must be an axis-aligned rectangle. Then I can give a $O(n^2 (\lg n)^2)$ time algorithm.

Without loss of generality, the $x$-coordinate of the left and right sides of this rectangle must agree with the $x$-coordinate of some pair of points, and similarly for the top and bottom sides.

So, guess the $x$-coordinate of the left side of the rectangle (there are $\le n$ possibilities), say $x\_L$. Now, do a binary search on the width of the rectangle (there are $\le n$ possibilities), using the following ideas.

Given a guess at the width $w$ of the rectangle, you can calculate the maximum number of points that can fit in an allowable rectangle with those $x$-coordinates for the left and right sides, as follows. Start by filtering out all points whose $x$-coordinate is not in $\[x\_L,x\_L+w\]$. Sort the remaining points by their $y$-axis. Now look for the $y$-value $y\_B$ for the bottom side of the rectangle, which maximizes the number of remaining points whose $y$-coordinate is in the range $\[y\_B,y\_B+A/w\]$. This can be found with a straightforward linear scan of the remaining points (with two pointers advancing monotonically).

With this, given $x\_L$, you can do a binary search for $w$. Each guess at $w$ takes $O(n \lg n)$ work to compute the maximum number of points that can be fit into a rectangle of that sort. Since there are $\le n$ possible values for $w$, you'll do $O(\lg n)$ iterations in the binary search. Since there are $\le n$ possibilities for $x\_L$, the overall running time is $O(n^2 (\lg n)^2)$.

Since a rectangle is a convex polygon, this gives you a lower bound on the number of points that can be covered by a convex polygon with area $\le A$. It might not be an especially tight lower bound, but maybe it's a start.

## Heuristic for arbitrary polygons

We could use branch-and-bound type techniques here.

Define a directed acyclic graph (dag), the search dag, where each vertex is a convex polyhedron $\mathcal{P}$ obtained as the convex hull of some subset of the $n$ points, and there is an edge from $\mathcal{P}$ to $\mathcal{Q}$ if there is some point $p\_i$ not in $\mathcal{P}$ such that the convex hull of $\mathcal{P},p\_i$ is $\mathcal{Q}$. The root of this graph is the empty polyhedron, which covers no points. Call any node of this graph that has no out-edges a "leaf". The best polyhedron must be some leaf.

A naive approach would be to do a breadth-first search on this dag. Unfortunately, the dag is probably exponential in size, so this naive approach will probably be too slow.

You might do better using branch-and-bound techniques. Define the "quality" of a leaf in this graph to be the number of points covered by its associated polyhedron. Also, define the "quality" of a node $x$ in this graph to be the maximum of the quality of all of the leaves that are reachable from $x$. Of course, we cannot compute the quality of a node without exploring everything reachable from it (which is too expensive), but we can estimate it.

In particular, we can compute an upper bound on the quality of any given node. This is enough to do branch-and-bound. We basically iteratively explore the graph. At each stage, we keep track of the "best" solution we've found so far: i.e., among all the polyhedron $\mathcal{P}$ corresponding to some node we've visited, keep track of the maximum number of points covered by any of these. Say this number is $b$. Now if we reach a node $x$ where our upper bound on its quality implies that the quality of $x$ is $\le b$, then we don't need to visit $x$ or any of its descendants. This might help us reduce the search space.

How do we get an upper bound on the quality of a node? Well, here's one way. Suppose we have precomputed, for each $i=1,2,\dots,k$, the minimal area of any convex polygon that contains $i$ points, call it $\alpha(i)$. Now if we have a node $x$ that corresponds to a polyhedron $\mathcal{P}\_x$ of area $A\_x$, and if $A\_x+\alpha(i) \> A$, then here's an upper bound on the quality of $\mathcal{P}$: it must be at most the number of points contained in $\mathcal{P}$, plus $i-1$. This could be a somewhat loose bound, but it is something.

How do we do the precomputation? Well, that's basically an easier instance of the same problem, with a smaller value for $A$. So, we can do the precomputation via a recursive or iterative application of this algorithm, for increasing values of $A$ (or via similar ideas).
> 4 votes

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


# Question
Title: Why doesn't a time cutoff convert NP problems into co-NP?
Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations.

You make a tweak to the verifier program, so that if it takes more than $f(n)$ operations, it unconditionally rejects. Then you place it into an NP machine and run it on all possible certificates for some instance of the problem where you're not sure if it has a solution. The unconditional reject after $f(n)$ operations ensures the computation terminates within $f(n)$ operations, even when rejecting. So this NP machine can solve the co-NP dual of the NP problem, where you want to reject in polynomial time when there is no solution.

Except that can't be right, because it seems to imply $\mathsf{NP}=\mathsf{coNP}$ and that's not believed to be true. I have an incorrect assumption or inference somewhere. What is it? Why can't I avoid NP's "negatives might run for a long time or even forever" with algorithm-specific time cutoffs?

A concrete example: suppose you have a 3-SAT verifier that takes no more than $42 n^2$ operations to check a solution to an $n$-clause problem (involving up to $3n$ variables). You then make an NP program like "non-deterministically choose a variable assignment, run verifier for up to $42 n^2$ steps, return its result else reject if it didn't finish". So within $42 n^2$ operations we'll have an answer, and flipping it gives the "is there no satisfying assignment" answer. Why is this not an NP algorithm for the co-NP problem of determining if there is no satisfying assignment to a 3-SAT problem?

# Answer
> 9 votes
The mistake I made was in the very last step: flipping the result. Doing that requires more than an $\mathsf{NP}$ machine, because I'm recombining the massively parallel computation *then doing something else*. $\mathsf{NP}$ machines *finish* with the merging, they can't continue on.

To run my algorithm I'd need a machine with the ability to query an $\mathsf{NP}$ machine then continue. A $\mathsf{P^{NP}}$ machine can do that... but it makes sense that $\mathsf{P^{NP}}$ would contain $\mathsf{coNP}$.

See also: Oracle Machines (Complexity Classes), and the Polynomial Hierarchy.

---
Tags: complexity-theory, np, co-np
---


# Question
Title: How should $\lambda x. \lambda y. f z x y \stackrel{\eta}{=} \lambda x. f z x$ be read?
I'm currently learning untyped $\lambda$-calculus and especially the $\eta$-reduction.

The professor hat the following in his slides:

$$\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$$

I don't know how to read and understand this. Could you please explain it to me?

## My try

On the left side and the right side is a function and they are $\eta$-equivalent.

The right side seems simpler, so I start with that.

It is a $\lambda$ function with one bound parameter $x$ and two unbound parameters $f$ and $z$. But here start my problems: What does $f~z~x$ mean? Is this a triple? Is it a function $f$ and a function $z$ and a function $x$?

I think in $\lambda$-calculus everything can be viewed as a $\lambda$-function, so $f$, $z$ and $x$ are functions. So the right side is the same as

$$\lambda(x) = f(z(x))$$

correct?

Applying the same logic on the left side, I get:

\begin{align} \lambda x. \lambda y. f~z~x~y &= \lambda(x)\\ &= f(z(x(y))) \end{align}

As $y$ is not in $\lambda(x)$ it is not bound. So we can simply remove it. Correct?

I think this could work. But I still don't know how to read it. I guess it will be something like:

"The lambda-function with the parameter $x$ that is a lambda function with a parameter y is f applied to z applied to x applied to y is eta-equivalent to the lambda function with the paramter x that is f applied to z applied to x".

# Answer
Applications in Lambda calculus are assumed to be left associative, this means that $f~z~x~y$ is the same as $((f~(z))~(x))~(y)$.

With this is mind eta-conversion makes more sense. Wikipedia says:

> Eta-conversion expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments. Eta-conversion converts between λx.(f x) and f whenever x does not appear free in f.

This means that $\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$ is assumed to be true because $y$ does not change the result of the application $f~z~x$, its value is applied after $f~z~x$ is already evaluated.

You can find out more about eta-conversion by playing with it in the Haskell REPL:

```
Prelude> let z = 1
Prelude> let f x y = (+) ((+) z x) y
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3
Prelude> let f x = (+) ((+) z x)
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3

```

As you can se, it is easily possible to leave out a the parameter `y` without changing the meaning of your program.
> 2 votes

# Answer
You do not have to try to interpret each side of the equality. This may be far too complicated in some cases, and $\lambda$-calculus is a formal calculus to begin with. It is better to know the calculus rules and apply them.

This said, you still have to read the expressions correctly:

$\lambda x.fzx$ is to be read as $\lambda x.((fz)x)$, that is a function that takes an argument $x$ and then returns the result from applying the function $f$ to $z$, and then applying the resulting function to $x$.

By definition of $\eta$-conversion you have: $\lambda x.fx \stackrel{\eta}{=} f$ whenever $x$ does not occur free in $f$

Though $\lambda$-calculus is a formal calculus, which can be analyzed without interpretation, you can try to understand intuitively the intent of such a rule. Essentially it says that if you have a function $f$ and you build from it a function $g=\lambda x.fx$ which takes one argument (here called $x$) and applies $f$ to it, then $g$ is equal to $f$. The idea is that $f$ and $g$ will both give the same result when applied to any argument.

Of course, in this definition, $f$ stands for any lambda expression.

There is however the requirement that no free variable named $x$ appear in $f$. The reason is that a free variable names something in the outer environment where $f$ is used. But, if $g$ replaces $f$, such an occurence of $x$ in $g$ would refer to the "parameter" $x$ in the definition of $g$, hence no longer to whatever it named in the outer environment.

But much of this explanation is for your intuition. The lambda game is formal, even though it does have interpretations.

Hence, if you apply this definition to the $\lambda$-expression $fzx$ , you get: $\lambda y.fzxy \stackrel{\eta}{=} fzx$ since the variable y does not appear free in $fzx$

Being equal, they can be substituted for each other in any context (precisely because of the restriction on free variables).

Hence $\lambda x.\lambda y.fzxy \stackrel{\eta}{=} \lambda x.fzx$

All this is of course remindful of scope rules in many programming languages, and that is not due to chance.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: Relation between space and time complexity for machines with write once read many (WORM) memory
While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A "human computer" is limited to use write once read many (WORM) memory when processing large amounts of data. Pure functional programming also seems to favor a WORM memory model. In fact, it seems to me that the WORM memory model is so natural that classifying it as unconventional computing might underestimate its importance. (Understanding the strengths and limitations of the computing resources available to humans is important.)

What is known about the relation between space and time complexity for machines with WORM memory? What are the keywords to google for available material related to these questions? Do we known whether the time complexity will remain the same, if a small (for example C\*log(WORM memory)^n) amount of normal memory is added?

# Answer
> 3 votes
> What are the keywords to google for available material related to these questions?

The Wang B-machine is a very simple Turing machine with only WORM memory. A Turing machine with only WORM memory is commonly referred to as a "non-erasing Turing machine".

> What is known about the relation between space and time complexity for machines with WORM memory?

Let's assume a Turing machine with $q$ internal states and a binary tape alphabet. If the machine halts after $t$ steps, having written $m$ marks on the tape and "visited" $p$ positions of tape, then $t \leq (m+1) \cdot pq$. The reasoning behind this bound is simple. As long as the machine doesn't write a new mark, there are only $pq$ distinct configurations. As the machine didn't cycle, it can have taken at most $pq$ steps between two write events, and there were only $m$ such write events.

> Do we known whether the time complexity will remain the same, if a small (for example C\*log(WORM memory)^n) amount of normal memory is added?

Already Wang himself showed that a non-erasing Turing machine can simulate a normal Turing machine with only a polynomial slowdown. It was shown recently that the same is also true for the Wang B-machine. Hence it's not really interesting to investigate the change of time complexity when adding a small amount of normal memory to the machine. It would be more interesting to investigate (for different algorithms) how much the normal space complexity can be reduced by allowing for a separate non-erasable space complexity. Not sure how to apply this to pure functional programming.

---
Tags: time-complexity, runtime-analysis, space-complexity
---


# Question
Title: How is this problem related to the study of algorithms and big O notation?
I'm taking a graduate computer science course on algorithms and analysis. The current subject is big O notation and recursion. How is the following problem related to the study of algorithms, recursion, and big O notation? I know and understand the solution to the problem, but I just don't see how this is relevant to the subject matter.

*Given an $x$, show that $x^{62}$ can be computed with only eight multiplications (A general algorithm can not accomplish it).*

# Answer
> 10 votes
You need to be more patient. This problem is hinting at the *repeated squaring* algorithm for powering. The more general question is: *How long does it take to compute $x^n$?* Naively, you might think that it takes $n$ multiplications, but the repeated squaring algorithm can do it using $O(\log n)$ multiplications.

Repeated squaring is very important for cryptographic applications. Many cryptographic algorithms rely on computing modular powers: $x^p \pmod{n}$, where in general $p$ and $n$ could be very large (say roughly $2^{1024}$). It makes a huge difference whether you do it in $O(p)$ or in $O(\log p)$ time.

# Answer
> 0 votes
let's first take x now:

```
 x^2 = x * x
 x^4 = x^2 * x^2
 x^8 = x^4 * x^4
x^16 = x^8 * x^8
x^32 = x^16 * x^16
x^64 = x^32 * x^32
x^62 = x^64 / x^2

```

Seems like you can do this in 7 steps actually if you use multiplication and division. The trick relies on the mathematical equation of $x^a\*x^b=x^{(a+b)}$ and $x^a/x^b=x^{(a-b)}$. As such it shows that once can compute $x^n$ in $O(\log n)$ multiplications and divisions.

---
Tags: algorithms, asymptotics
---


# Question
Title: Adding words to DFA, maintaining minimality
How can we add new words to DFA, maintaining minimality?

Maybe, you can advise some completely different approach to solve the following problem:

> A program must process two types of queries:
>
> 1. Add new word to the language.
> 2. Check if some word of the language occurs in the input string as a substring.
>
> Time and space complexity should be as low as possible.

The only solution that I know so far is to rebuild an automaton from scratch every time, using Aho-Corasick algorithm, but, you know, it's really-really inefficient.

I've performed some search on Internet and found some papers like "Incremental Construction of Minimal Acyclic Finite-State Automata", but, unfortunately, algorithm described there produces and maintains just a minimal trie (not a complete FSM with suffix links, like an automaton produced by Aho-Corasick algo).

# Answer
For number 2, I think you would just check if the DFA ever enters an accept state, instead of just checking if it ends in an accept state. So just run the algorithm as normal, but halt and accept as soon as the automation transitions to an accept state, instead of waiting until the end of the input. (The number of times the automation enters an accept state is the number of substrings of the language contained in the input string)

Not sure about number 1 though. I am not sure what operations (if any) minimal DFAs are closed under, but I think the number of operations required by a slightly modified version of Hopcraft's algorithm would be proportional to the size of a word you add via union.
> 1 votes

---
Tags: algorithms, finite-automata
---


# Question
Title: How to devise an algorithm that suggests feasible cooking recipes?
I once had a veteran in my course that created an algorithm that would suggest cooking recipes. At first, all sort of crazy recipes would come out. Then, she would train the cooking algorithm with real recipes and eventually it would suggest very good ones.

I believe she used something related to Bayes Theorem or Clustering, but she is long gone and so is the algorithm. I have searched the internet but looking for cooking recipes will yield any sort of results but not the one I am looking for. So, my question is:

> What techniques can be used to devise an algorithm that (randomly) suggests feasible recipes (without using a database of fixed recipes)?

Why would I bother looking for a cooking algorithm? Well, it was a very good example of a real world application of the underlying concepts, and such algorithm could be useful in different settings that are closer to the real world.

# Answer
Hmm, using Bayes Theorem to make new recipes out of old recipes. I imagine you first would want the algorithm to pull apart the ingredients into a form it understands (not sure if we are using NLP for that, or if you manually enter the data in yourself, that's neither here nor there.) From there...

I envision something like this.

Test Data analyzed. Now we have a list of recipes and the probabilities that each ingredient will take place alongside another ingredient, and in what quantities. After we have this data then you would have the program randomly make the new recipes. First it cycles through a list of all the known ingredients, then randomly selects a main ingredient, from there it uses the probabilities of an ingredient given another ingredient to start throwing in more random ingredients, all the while matching appropriate trained data for quantities and compatible ingredients.

Might I suggest that when creating a new recipe the program be given information like, I want something sweet, or something sour, or for instance something mostly made up of wheat.

Hopefully this helps a bit.
> 4 votes

# Answer
For a broad US-centric dataset of nearly 2000 recipes you could look at the Armed Forces Recipe Service. This does not answer your question, but would provide you with real-world training data.

The requirements for the problem are probably difficult to articulate for most people and the selected approach will likely end up implicitly adjusting fitness in the way you have suggested. Foods in geenral are very culture-specific and the approach would probably travel very poorly without extensive tuning.

This also needs substantial sematic, and domain, knowledge to prepare more than just a list of ingredients. After all, coffee-flavoured ice-cream with wafer, cafe au lait and a croissant and tira misu would otherwise be indistinguishable.
> 3 votes

# Answer
Recipe generation is commonly used as an example application for Case Based Reasoning systems. It is even used as an example on the Wikipedia Page. A google search for "case based reasoning recipes" yields numerous results.
> 3 votes

# Answer
The class of algorithms you are looking for is the bandits one. They are usually used to handle the exploration part of a classification problem.

A basic approach would be to represent the recipes as a limited bag of components (a vector of booleans with at most k non 0 values) and to use LinUCB to select a set of components. Then the feedback would be 'like' or 'dont like'. Of course if you are a bayesian you could prefer to use Trueskill (using the Adpredictor variant).

Something less basic would require to use a kernel instead of a linear separation. Kernel ucb can help to handle that part. But at some point I think it would become usefull to pay attention to the chemical compositions of the aliments because at the end you probably want to achieve a balance between different basic tastes.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, modelling, recommendation-systems
---


# Question
Title: What does an input string of epsilon mean?
I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA:

I was following it until I read the following :

> Practice with it to satisfy yourself that it accepts the strings ϵ, a, baba and baa...

What does an input string of ϵ mean?

# Answer
> 5 votes
In the context of NFAs, $\epsilon$ marks state transitions that do not consume input. These transitions thus express the non-determinism of the automaton.

When discussing the *acceptance* of $\epsilon$, the symbol marks the empty string (this is equivalent to the condition that an accepting state is reachable by a sequence of $\epsilon$-transitions from the start state). to avoid confusion, some authors use a different symbol for the empty string (often $\lambda$).

---
Tags: finite-automata
---


# Question
Title: Classification algorithm for high dimensional data which is uniquely definable in a very small sub-space
I am new to machine learning, so forgive me if I am doing something absolutely absurd.

I have a classification task (~100 classes) and have about 2 million training data points in a 2000-dimensional space. Coordinates of data points are integers (discrete). All points have non-zero coordinates only for \< 10 dimensions. That is, each point can be uniquely defined in \< 10 dimensional sub-space.

If I use a Gaussian Mixture Model (GMM) for each class, I will end up with ~100 GMMs in a 2000-dimensional space. I feel that given the fact that each point is uniquely definable in less than 10 dimensional space, there can possibly be a better way of doing it.

What am I missing here?

# Answer
Since your data are extremely sparse, using GMMs or a traditional SVM will result in an over-fit model. By employing methods that exploit the sparsity of the structure, you should get much better results. Regression methods typically add some penalty function as a measure of the amount of non-zero values. This is usually referred to as "regularization". Doing this exactly (under the $L\_0$ norm) is difficult, so relaxations are used (lasso: $L\_1$, ridge: $L\_2$).

If you are comfortable with Python, SciKit Learn has implementations for several approaches that utilize either lasso or ridge penalties. Here is an example of Lasso penalty for an SVM model. I would try that and see how well it works. It may require a parameter to adjust the regularization amount. You can do cross-validation to find what parameter works best.
> 3 votes

---
Tags: machine-learning, classification
---


# Question
Title: Hardness of mixed 3-SAT and 2-SAT formula
It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals.

We can solve this case in polynomial time, separating and solving in a brute force manner the 3 literal clause and then for each satisfying assignment try to solve the rest $n-1$ 2-literal clauses. This method can work till $O(\log n)$ clauses with 3 literals. If we consider a more general case with e.g $\frac{n}{2}$ clauses with 2 literals and $\frac{n}{2}$ clauses with 3 literals does the problem remain $\sf NP$-complete?

It is a bit confusing because we have a subproblem approximately the same size, implying it is difficult and another one roughly the same size implying it is easy. Is there probably a better method than the one I proposed?

# Answer
> 10 votes
First of all, these are not subproblems but different types of problems. In one your promise me that $n/2$ of the clauses only have 2 literals, and in the other your promise me that only $\log n$ of the clauses have 3 literals. These are simply different problems.

For the general case, it is easier to think about if you let $n = n\_2 + n\_3$ with $n\_2$ being the number of 2-literal clauses, and $n\_3$ being the number of 3-literal clauses. Let $f$ be a function such that $n = f(n\_3)$. If $f$ is polynomial then the question is $NP$-complete by padding. If $f$ is super-polynomial (but not exponential) then we do not know the complexity of the problem. If $f$ is exponential then your approach of brute-force shows that the problem is in $P$.

Note that for every $f$ you could choose, you have a *different* problem. They just look similar.

# Answer
> 5 votes
If you have $\frac{n}{2}$ of the clauses with 3 literals the problem is trivially NP-complete by a reduction from 3-SAT.

Given a 3-SAT formula $\phi$ with $n$ clauses, ask whether $\psi = \phi \wedge\_{i\in\[n\]}(y\lor \bar{y})$ is satisfiable (i.e. add $n$ dummy clauses with a new variable $y$).

Clearly, $|\psi|\leq 2\cdot|\phi|$, hence if your algorithm is polynomial in $|\psi|$ it is polynomial in $|\phi|$.

If you are looking for other smaller number of 3SAT clauses, keep in mind that the exponential time hypothesis is that $n$-clause 3SAT can't be solved in time $2^{o(k)}$.

This means that if ETH is true, and you have $n$ 3SAT clauses in your formula, and $poly(n)$ 2SAT clauses the running time of any algorithm will be strictly exponential. (without ETH, it's still NPC, as @Marzio mentioned).

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


# Question
Title: Single big BST vs multiple smaller BSTs? Which is faster for search?
Lets say that I am storing `10^9` keys in a single BST. Compared to having lets say having multiple BSTs of sizes `10^6` containing chunk of the bigger tree? Search through all of them executing in parallel.

I am talking about only search performance here, Given that processing power is not a bottle neck.

# Answer
Searching among $N$ in a BST takes (roughly) $\log\_2 N$ comparisons. So searching in $10^9 \approx 2^{30}$ takes around 30 comparisons. Searching in $10^6 \approx 2^{20}$ takes 20 comparisons. The cost of farming out the work to 1000 processors, collecting the results and figuring out the answer is surely costlier than 10 comparisons.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: How to stop genetic algorithm population converging to a single value
I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem. All seven variables are floating point numbers. The problem is that the entire population seems to converge to very nearly the same point in the solution space within about 20 generations, even if I increase the population size by 10x.

**Attempted solutions**

Starting with a parent population $\vec{x}^{(j)}$, where $j$ is the individual's index in the population, I take the best 10% (i.e. highest fitness scores) to reproduce. First I perform cross-over producing 2 children for every randomly selected pair of parents. The parents can be re-used (is that a problem?). About 5% of the children get mutated randomly.

I've tried two variations of cross-over but both have the same problem:

1. Calculating a 7 element weights vector $\[w\_i\]$ and calculating the children's elements as $c\_i^{(1)}=w\_i x\_i^{(1)} + (1-w\_i)x\_i^{(2)}$ and $c\_i^{(2)}=(1-w\_i)x\_i^{(1)} + w\_i x\_i^{(2)}$. The parents ith elements are $x\_i^{(1)}$ for parent 1 and $x\_i^{(2)}$ for parent 2. Each weight is a sample from a uniform random variable in $\[0.0;1.0)$.
2. Confining the weights $w\_i$ to be either $0.0$ or $1.0$, i.e. randomly exchanging elements of the two parents genomes to create the children.

The mutation operation consists of randomly choosing one of the child's 7 elements and adding some Gaussian noise to it. The standard deviation of that noise differs for each element since the elements have different physical units.

Afterwards, I evaluate the fitness of the children and keep the best few hundred or thousand (setting that I choose at the start of the algorithm) out of the combined population of parents and children to give the next generation. Note that the parents do not get mutated, especially since I want to preserve the best from the parent generation in case none of the children improve on it.

I've tried population sizes from 1024 to 20480 and have also tried increasing the probability of mutating a child from 5% to 50% but I still have the problem that all the individuals in the population become very similar within the first 20 or so iterations. Please advise on what I'm doing wrong.

I should point out that the algorithm, despite this problem, does get fairly close to the optimal solution. I know this because the quantity to maximise is the correlation between between two things (no more details, sorry) and I can get to about 0.94 (the maximum physically possible is always 1.0). However, I am concerned that the GA is not covering enough of the solution space, causing it to miss the global maximum.

**My questions**

1. Are either of the above cross-over methods correct?
2. Is it ok to re-use parents in cross-over? Stated another way, is polygamy a good idea in this algorithm or should I change that part to ensure that no parent gets used more than once?
3. Should I mutate the parents as well?
4. What should I do with the 90% of parents that did not get used in the reproduction?

# Answer
> 4 votes
Your selection method may lie at the root of this. You are currently using truncation selection, which applies a very high selective pressure and reduces diversity by not allowing elements from worse solutions to be preserved to possibly be useful again in future generations.

You should try different selection methods, in particular roulette selection or tournament selection, and see if that makes a difference. Most implementations I have seen also keep **all** generated offspring, regardless of quality. The intuition is that, if a child has low quality they will eventually die out anyway, and they might still carry useful information.

---
Tags: optimization, genetic-algorithms
---


# Question
Title: There is equivalence in an NP-hardness proof or not?
I want to show that some problem $P\_1$ is NP-hard. I have a problem $P\_2$ that is NP-complete. From an instance of $P\_2$ I created in polynomial time an instance of the problem $P\_1$.

My question is: Should I verify both direction ($\Leftrightarrow$) or only one direction ($\Rightarrow$)? More precisely, which one to show from these two:

* Solve $P\_1\\;\Leftrightarrow$ solve $P\_2$
* Solve $P\_1\\;\Rightarrow$ solve $P\_2$

# Answer
You only need to show that solving $P\_1$ allows you to solve $P\_2$ (and, hence, every other problem in **NP**).

$P\_1$ might not be in **NP** so it's not necessarily the case that solving $P\_2$ allows you to solve $P\_1$. On the other hand, if $P\_1$ is in **NP**, then you already know that solving $P\_2$ allows you to solve $P\_1$, by definition of **NP**-completeness.
> 2 votes

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


# Question
Title: Relaxed graph coloring, with penalties for assigning adjacent vertices the same color
Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d\_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in \[N\]$. Thus the diagonal entries of $D$ are all zero and $d\_{ij}=d\_{ji}$ so $D$ is symmetric.

Then there is a set of $k$ colors. I want to assign these colors to the $N$ nodes such that the minimum metric of a common color between any pair of nodes is maximized. So if $c(i)$ is the color assigned to $i\in \[N\]$ by the assignment $a\in A$, where $A$ is the set of all possible color assignments, we are looking for $$\max\_{a\in A} \min\_{i,j} \\{d\_{ij}:c(i)=c(j)\\}.$$

Is this problem NP-hard? If it is, what sort of reduction can be used to show that this problem is NP-hard?

# Answer
> 7 votes
Yes. Reduce from graph coloring.

$D$ is given by $d\_{i,j} = \begin{cases} 0 & \text{ if } i=j \\ 1 & \text{ if } i \text{ is adjacent to } j \\ 2 & \text{ else}\end{cases}$.

---
Tags: complexity-theory, reductions, np-hard, colorings
---


# Question
Title: Proving NP-completeness of a graph coloring problem
Given a graph $G=(V,E)$ and a set of colors $k\<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they have the same color.)

I want to prove the above problem is NP-complete. Call the above problem P1.

Answer: I am trying to reduce the k-coloring problem.

P2: Given a graph $G=(V,E)$ and set of colors $k\<V$ is the graph k-colorable (zero conflicts)?

P2 is feasible iff P1 has optimal value is exactly $0$. Therefore if P1 is solved we know solution to P2.

Is this solution correct? Is it what is suggested by the first comment of user G.Bach in A variation of the graph coloring problem ?

# Answer
First of all, you haven't formulated your problem as a decision problem (a problem that has a YES/NO answer). The decision problem corresponding to your optimization problem is: Given a graph $G$, an integer $k$ and another integer $\ell$, is there a $k$-coloring of $G$ with at most $\ell$ monochromatic edges?

In order to show NP-completeness of a problem $P$, you need to do two things:

1. Show that $P$ is in NP. This is usually easy. It just means that a putative solution can be verified.
2. Show that $P$ is NP-hard. In practice, this is (almost) always done by showing that some other NP-hard problem $Q$ is many-one reducible to $P$. This implies that $P$ itself is NP-hard.

A many-one reduction from $Q$ to $P$ is a function $f$, computable in polynomial time, which maps an instance $x$ of $Q$ to an instance $f(x)$ of $P$ such that $x \in Q$ iff $f(x) \in P$.

In your case, it is easy to see that your problem (let's call it MIN-MONOCHROMATIC) is in NP: the NP machine guesses a $k$-coloring of $G$, and verifies (in polynomial time) that there are at most $\ell$ monochromatic edges. In order to show that it is NP-hard, we come up with a many-one reduction $f$ from the NP-hard problem K-COLORING to MIN-MONOCHROMATIC. The reduction $f$ takes a graph $G$ and an integer $k$, forming an instance of K-COLORING, to the instance $(G,k,0)$ of MIN-MONOCHROMATIC (i.e., with $\ell=0$). The definition of coloring implies that $(G,K)$ is in K-COLORING iff $(G,k,0)$ is in MIN-MONOCHROMATIC. Also, clearly $f$ can be computed in polynomial time. So $f$ is a polytime many-one reduction from an NP-hard problem K-COLORING to MIN-MONOCHROMATIC, so we conclude that the latter is NP-hard. Since it is also in NP, it is NP-complete.

As you see, this is the same proof as yours, only with a lot of fluff. At this stage of your education, this fluff is important, since you need to makes sure that you understand the definitions not only intuitively but also formally (both are important). Once you're past this stage, all the details you really need are the ones explained in your current proof.
> 6 votes

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


title: Compressing normally distributed data

text:
# Question
Title: Compressing normally distributed data
Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, it should be possible to store any value $x$ using $$\frac{1}{2} \mathrm{log}\_2(2\pi\sigma^2)+\frac{x^2}{2\sigma^2}\rm{log}\_2\rm{e} \\;\text{ bits.}$$
Arithmetic coding should provide perfect compression. In principle it's not too hard. I can calculate the interval boundaries from the cumulative distribution function of the Gaussian. In practice, I hit considerable difficulties because when using floating point operations I cannot achieve perfect reproduction of the results, and I have no idea how to do this without FP operations. Perfect reproduction is necessary because the uncompressing code must come up with exactly the same interval boundaries as the compressing code.

So my question is: How do I compute the interval boundaries? Or is there any other way to achieve (near) perfect compression of such data?

Strictly speaking, the normal distribution is defined only for continuous variables. So what I mean here are integers x with a probability distribution function $$P(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\rm e^{-\frac{x^2}{2\sigma^2}}.$$
This distribution does not sum up exactly to 1. However, for $\sigma\>100$ the difference from 1 is less than $10^{-1000}$ and hence it's more precise than any practical calculation would be.

# Answer
> 5 votes
In what follows, I'm going to assume that $x \ge 0$, and then try to put that back later.

First, we'll simplify the notation a little. The length of the code for $x$ should be:

$$L\_m(x) = a + b \left(\frac{x}{\sigma}\right)^2 + \log\_2 \sigma$$

where:

$$a = \frac{\log\_2 2\pi}{2} \approx 1.325$$ $$b = \frac{1}{2 \ln 2} \approx 0.721$$

This suggests that you should divide $x$ by $\sigma$, encode the remainder in $\log\_2 \sigma$ bits, then encode the quotient $q$ in $a + bq^2$ bits (say, using arithmetic coding). Instead of storing $20002$ codes using Yuval's method, you now only need $20$ or so.

In a sense, what you're doing here is converting the normal distribution to a standard distribution. Moreover, if you move $\sigma$ to the nearest power of 2, the division can be done using bit shifts and masks. $\sigma=1024$ is close enough to $1000$, so that part of the operation is extremely cheap.

However, there is a catch. To arithmetic code $L\_0(10)$, you need about 60 bits. On a 64-bit machine, this is pushing the practical limit of an efficient arithmetic coder. So you should probably consider partitioning the space for more efficient encoding.

One possibility is to use binary arithmetic coding, with one binary symbol per $\sigma$. The probability that $x$ is within $\sigma$ of the mean is $0.6826895$ (or so). The probability that $x$ is within $2\sigma$ given that it is not within $\sigma$ is $0.85660651$ (or so), and so on. I calculate the code length for the $8\sigma$ symbol to be around 27.3 bits, and trying to calculate the length for $9\sigma$ breaks into numeric instability using the simple calculation that I did.

No matter what you try, representing numbers that are more than about $8\sigma$ from the mean is going to be difficult to do well, but given that those numbers are extremely rare, perhaps you should just fall back to a universal code (e.g. one of the Elias codes) for that case.

So in summary, here's the representation that I'd try.

1. Divide $\left| x \right|$ by $\sigma$. Call the quotient $q$ and the remainder $r$.
2. Store the sign of $x$ as a single bit.
3. Arithmetic encode $q$ using a sequence of binary variables:
    1. Use a single binary symbol with $p\_0 = 0.6826894921370859$. Store $0$ if $q=0$, or $1$ if $q\>0$.
    2. If you stored $1$, use another binary symbol with $p\_0 = 0.8566065013011934$. Store $0$ if $q=1$, or $1$ if $q\>1$.
    3. ...and so on. Stop when you get to $q \ge 8$).
4. If $q\<8$, binary encode $r$ in $\log\_2 \sigma$ bits.
5. If $q\ge 8$, use a universal binary code of choice (Elias gamma is a popular choice) to store $x - 8\sigma$.

Now having said all this, a common approach used in many compression standards, which works fairly well when $\sigma$ is small, is to use exp-Golomb coding. It's not theoretically perfect, but seems to work well in practice.

# Answer
> 2 votes
Let $P(x)$ be the quantity mentioned in your question, define a sequence $a\_0,\ldots$ by $$ 0,1,-1,2,-2,3,-3,4,-4,\ldots, $$ and let $Q(n) = P(0) + \cdots + P(n-1)$. You're interested in computing the values $Q(n)$ in a consistent way across different computers. Your actual implementation is going to store these values only up to a certain accuracy. You can compute the exact numbers to that accuracy using software floating-point arithmetic. You can then store the results in some table. The table won't be too long, since the probability that $|x| \> 10\sigma$ is smaller than $2^{-75}$, and so it is enough to store $20002$ values.

By the way, if you want to store the numbers as floating-point reals, you are constrained by the size of the mantissa: a long double, for example, has a mantissa of length $63$ bits on Intel CPUs, and so you cannot handle events with probably on the order of $2^{-64}$ or smaller (which is probably not a problem). If you are adamant about handling such events, you will need to store these values as fixed-point reals, which is perhaps what your arithmetic coding code expects anyway.

---
Tags: information-theory, randomness, data-compression, entropy
---


title: Why are pushdown automata countable?

text:
# Question
Title: Why are pushdown automata countable?
I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.

The problems in this section are pretty confusing and I honestly don't know how to begin them because I'm not 100% on what they mean when they say "countable".

Can anyone help walk me through this problem in the book, that simply states;

> Show that the number of push-down automatons is countable.

# Answer
Actually the proof is not so easy. It is not technically hard, but you have to be very careful about definitions.

First, of course, you need to know what countable means, and that was given in @Raphael's answer.

The proof relies on the fact that the set of finite sequences of elements of a countable set is itself countable. You may try to prove this. Look at the proof that rational numbers are countable.

You can read that more intuitively as implying that anything that has a finite description using a finite set of symbols is countable.

Then a possible way to answer your question is to check whether this is the case for pushdown automata.

We know from the definition that they are all finitely described. Then the remaining question is whether the set of symbols used is itself countable. But short of defining that set (how?), we cannot answer that question.

The simple answer is to state that PDAs are defined up to an isomorphism. Actually a very simple isomorphism, which is a simple renaming of symbols used in the description, which has to be finite for each PDA. Then it is always possible to take the symbols in a given countable set, for example the integers.
> 4 votes

# Answer
Since you don't provide any attempt on your own part, note two things.

1. The definition of countability.

> A set $A$ is countable if and only if $A$ is finite or there is a bijection $f : A \to \mathbb{N}$.
2. How do you represent pushdown automata in a formal way?

If you digest the first item and answer the second, the answer should become apparent.
> 5 votes

---
Tags: terminology, automata, pushdown-automata, uncountability
---


# Question
Title: Mapping intuitionistic logic to the modal logic S4
In his famous Semantical Analysis of Intuitionistic Logic, S. Kripke speaks of the "well-known mappings of intuitionistic logic into the modal system S4". I'm not sure which mappings Kripke means. One guess would be K. Gödel's "Eine Interpretation des Intuitionistischen Aussagenkalküls" (translated into English as "An Interpretation of the Intuitionistic Propositional Calculus". I don't have access to either.)

Could somebody please point me towards a text that details these translations?

# Answer
> 9 votes
That is the right paper, but there are actually several equivalent embeddings.

The book *Basic Proof Theory* by Troelstra and Schwichtenberg gives two such embeddings. Here's one. If $P$ is atomic but not $\bot$:

$$P^\circ := P$$ $$\bot^\circ := \bot$$ $$(A \wedge B)^\circ := A^\circ \wedge B^\circ$$ $$(A \vee B)^\circ := \square A^\circ \vee \square B^\circ$$ $$(A \rightarrow B)^\circ := \square A^\circ \rightarrow B^\circ$$ $$(\exists x A)^\circ := \exists x \square A^\circ$$ $$(\forall x A)^\circ := \forall x A^\circ$$

Here's the other:

$$P^\square := \square P$$ $$\bot^\square := \bot$$ $$(A \wedge B)^\square := A^\square \wedge B^\square$$ $$(A \vee B)^\square := A^\square \vee B^\square$$ $$(A \rightarrow B)^\square := \square (A^\square \rightarrow B^\square)$$ $$(\exists x A)^\square := \exists x A^\square$$ $$(\forall x A)^\square := \square \forall x A^\square$$

They are equivalent in the sense that $S4 \vdash \square A^\circ \leftrightarrow A^\square$, and the embeddings are sound and faithful. The proofs are left as an exercise, or you can dig out the book.

# Answer
> 6 votes
In addition to the two translations Pseudonym mentions in his/her reply, I found another one here: It's from intuitionistic propositional logic to GL, the logic of provability. GL is characterised by the following axioms.

* $\square(A \rightarrow B) \rightarrow \square A \rightarrow \square B$.
* $\square A \rightarrow A$.
* $\square A \rightarrow \square \square A$.
* $\square (\square A \rightarrow A) \rightarrow \square A$.

Now the embedding is given by the following clauses.

* $p^{\triangle} := p \wedge \square p$.
* $\bot^{\triangle} := \bot$.
* $(A \wedge B)^{\triangle} := A^{\triangle} \wedge B^{\triangle}$.
* $(A \vee B)^{\triangle} := A^{\triangle} \vee B^{\triangle}$.
* $(A \rightarrow B)^{\triangle} := ( A^{\triangle} \rightarrow B^{\triangle}) \wedge \square ( A^{\triangle} \rightarrow B\ ^{\triangle})$.

We can show that $\vdash A$ in intuitionistic propositional logic iff $\vdash\_{GL} A^{\triangle}$ in GL.

---
Tags: reference-request, logic
---


# Question
Title: What is the difference between storage media and storage devices
I am having a rather distressing confusion about whether `storage media` and `storage devices` are the same terms. I found on this yahoo answers page that there is a subtle difference but very tricky to understand.

I have googled a lot but cannot find the satisfying answer.

Can anyone kindly explain the difference between these two terms with easy-to-understand examples.

Regards

# Answer
Media is what holds the information, e.g. disk platen, CD, magnetic stripe.
Device is what uses the media and provides a physical interface.

For devices that have removable media, such as CD/DVD players the distinction is easy. For other devices where the media is an integral part of the device, the distinction is not so easy because the media is not designed to be removed, e.g. hard drive, thumb drive.
> 3 votes

# Answer
Media is a medium on which data is saved. e.g CD Devices are something which run a Media on it. eg CD player.
> -1 votes

---
Tags: storage
---


# Question
Title: What values do $y_i$ in training data for binary classification problems attain?
In case of binary classification problem, what are the $y\_i$ 's in the training data set $\\{(x\_1, y\_1), (x\_2, y\_2), \dots (x\_n, y\_n)\\}$?

I guess they are from $\\{1,-1\\}$. Now I see a method for finding a scoring function $f(x) = w^Tx + b$ by minimizing the squared error between the $f(x\_i)$'s and $y\_i$'s over $w$ and $b$. Now is it correct to minimize the error between $f(x\_i)$'s and $y\_i$? The latter is a sign while the former is a value? They seem incomparable to me.

# Answer
> 2 votes
If your prediction is $f(x) = \text{sign}(w^T x + b)$ then the 0-1 loss will simply be $$ L\_{\text{0-1}}(w) = \sum\_{i=1}^n \mathbb{I}\\{y\_i \neq f(x\_i)\\}, $$ where $\mathbb{I}$ is the indicator function, i.e., $\mathbb{I}\\{a\\} = 1$ if $a$ is true and $0$ otherwise. If you were to minimize this directly using subgradient descent you would get the perceptron algorithm. A more common approach is to upperbound the 0-1 loss with some other function, like the hinge loss, log loss, squared loss, etc and minimize that.

# Answer
> 1 votes
Actually your prediction will be sign(f(x)), not just f(x). So the prediction of the model will be +1 or -1.

---
Tags: terminology, machine-learning, classification
---


# Question
Title: If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?
Is there a non-regular language over unary alphabet $\\{a\\}$ which has a Myhill-Nerode equivalence class that is not a singleton?

# Answer
I'm guessing you are talking about Myhill-Nerode classes.

We can view $L$ as a subset of $\mathbb N$, since only the length of the word is important on $\\{a\\}$. Moreover two numbers $i,j$ are equivalent iff for any $n$, $i+n\in L$ iff $j+n\in L$. Assume there are $i\<j$ equivalent, and let $k=j-i$. Then for any $n$, we have $n\in L$ iff $n \bmod k\in L$, since you can replace $j$ by $i$ as many times as you want. This means $L$ is regular, because it depends only of the congruence classes modulo $k$.

So the answer to your question is Yes: if $L$ is nonregular, all classes are singletons.
> 7 votes

---
Tags: formal-languages, automata
---


# Question
Title: Finding representatives of equivalence classes
I have a table of pairs of objects, which defines an equivalence relation. How can I extract a single object from each of the equivalence classes using relational algebra?

It can easily be done with iteration. For example, associate a unique `classId` with every object, then for every pair `(a, b)` set `classId(a) = classId(b) = min(classId(a), classId(b))`, until all pairs share the same `classId` on both ends.
I wouldn't know how to do it more efficiently.

# Answer
The most efficient way known of doing this is the union-find algorithm. The idea is to keep a forest (but with links "upwards", not downwards), and squash long branches. You start with each element in its own forest. To make $a$ and $b$ equivalent, you check it $a$ and $b$ are already in the same class by following their links to the respective roots. If the roots are different, make the smaller tree a subtree of the larger one. And each time you follow a chain to a root, afterwards revisit all nodes on the path and make them point directly to the root, effectively making later searches take one step.

This is rather simple to program with an array for the nodes, and array indices for links.
> 1 votes

---
Tags: relational-algebra
---


# Question
Title: Modelling 2 object situation with Propositional Logic
I'm reading up on propositional logic, and I'm completely stuck on this example - spent the past few hours trying to figure it out! Any pointers would be appreciated.

There's 2 trees, each with signs on.

Sign 1/Tree 1: There are leaves on this tree, and no leaves on the other

Sign 2/Tree 2: There are leaves on one of these trees, but none on the other.

Exactly one of the signs is true, and the other is false. Which tree has leaves on (without looking)?

I'm starting to doubt that it's possible to tell, but I'm sure there's some logic that says otherwise!

# Answer
> 1 votes
Let $P\_1$ indicate that Tree 1 has leaves (i.e. $P\_1$ is true if Tree 1 has leaves), and $P\_2$ indicate that Tree 2 has leaves. Sign 1 states $S\_1 = P\_1 \land \lnot P\_2$, and Sign 2 states $S\_2 = (P\_1 \land \lnot P\_2) \lor (\lnot P\_1 \land P\_2)$. We are given that $R = (S\_1 \land \lnot S\_2) \lor (\lnot S\_1 \land S\_2)$.

In order to solve this, we simply calculate $S\_1,S\_2$ for each of the possible truth assignments of $P\_1,P\_2$: $$ \begin{array}{cc|cc|c} P\_1 & P\_2 & S\_1 & S\_2 & R \\\hline F & F & F & F & F \\ F & T & F & T & T \\ T & F & T & T & F \\ T & T & F & F & F \end{array} $$ The only truth assignment for which $R$ holds is $P\_1 = F$, $P\_2 = T$. We conclude that Tree 1 has no leaves and Tree 2 does have leaves.

---
Tags: logic
---


# Question
Title: Has Anyone Actually Created a System that Writes Computer Programs from specification?
Has anyone ever actually written a system (software or detailed explanation on paper with simple examples) that generates computer programs? I input $Prime(x) \wedge x\<10$ and it creates a program that lists the prime numbers less than 10. $Prime(x)$ is simply defined as $$1\<x \wedge \not\exists A\\; s.t. 1\<A \wedge A\<x \wedge x=A\times B,\mbox{ with } A,B\in \mathbb{N}$$ Professors say they can but nobody gives actual complete examples.

# Answer
This is a very active research topic, very promising, though full automation of program generation probably has intrinsic limitations (but are human beings any better?). But the idea is still be very useful in assisting considerably the creation of programs by mechanizing many steps, and by automatically checking the correctness of the program generation.

It is strongly related to a result in logic, called the Curry-Howard correspondance (or isomorphism), that shows that computer programs and mathematical proofs are very similar.

So the idea is that the system will take your program specification as a theorem to be proved. In the case of your example, it would be something like (informally): "there is a set of all prime numbers smaller than 10".

Then, you will attempt to prove that theorem, and existing systems will assist you in doing the proof, automating some parts, possibly the whole proof, and making sure you never make errors.

From that proof one can then extract a program that actually computes the wanted list of prime numbers that had been initially specified.

Several systems were developed in the past to elucidate these ideas. One of the better known was LCF by Robin Milner, who created the language ML for that purpose. One of the currently most advanced systems is Coq.

There are examples fully worked out, some of them quite complex. You may find some in the following article, though it is in no way simple reading and requires advanced knowledge of Logic.
> 11 votes

# Answer
The wag answer: Yes, but at the time of writing, for most nontrivial programs the specifications seem to be just as hard to write and debug as the programs would be.

More seriously, babou's answer is good, but I'm also going to suggest checking out the area of dependent types. There's a rather good book using Coq (full disclaimer: written by a friend of mine), but there's also Epigram, Agda, and Idris. Isabelle/HOL is also worth checking out.

These are all based on the calculus of constructions. If you want to know the theoretical basis, look up Martin-Löf type theory. There are some great introductions around.
> 9 votes

# Answer
Going off in a tangent here, program generators (i.e., systems that given a high-level description of something in some special language) have been around forever. Any compiler is one of those, as is any of the many parser generators. Back in the day systems called "third generation languages," which generated (most of the) code of a typical business application given a high-level description and a catalog of available data were popular.
> 4 votes

# Answer
Logic Programming and, more generally, Declarative Programming take as a premise exactly what you propose: namely, from a logical specification, return a result fulfilling that specification.

One area which seems to specifically address the "primes less than 10" example you give is Constraint Programing which tries to find solutions to problems involving certain constraints, including integer constraints like those you gave.

You might want to try ECLiPSe for a specific (open source) implementation of such a system.
> 1 votes

---
Tags: logic, type-theory, coq, proof-assistants
---