# Question
Title: Calculating modulus of large non-factored numbers
The internet is full of algorithms to calculate the modulo operation of large numbers that have the form $a^e \bmod p$. How about numbers with unknown factorization. More precisely, let's say I have a 4-byte sized modulus prime $p$, and a large number $a$ stored in memory as an array of bytes, that is, $a = \[a\_{k-1}, a\_{k-2},\dots, a\_0\]$, where $ k \gg 4$.

How to calculate the modulo operation $a \bmod p$ efficiently? Please, cite a reference for your algorithm if it is possible.

# Answer
The map from natural numbers to the ring of remainders is a homomorphism, which is a way to say that it has all sorts of nice properties with respect to operations `+` and `*`. In particular, `a+b` has the same remainder as `mod_p(a) + mod_p(b)` and `a*b`, the same as `mod_p(a)*mod_p(b)`.

So, `mod_p(a_0 + a_1*2^8 + a_2*2^16 + ...) = mod_p(mod_p(a_0) + mod_p(a_1)*mod_p(2^8) + mod_p(a_2)*mod_p(2^16) + ...)`.
> 5 votes

# Answer
The modulo operation is one of the basic arithmetic operations. As such, you can use the division algorithm you learned in school (if they still teach it) to calculate $a \bmod p$, which is the remainder in the division of $a$ by $p$. Efficient implementations are also available in libraries like GMP.
> 2 votes

---
Tags: algorithms, modular-arithmetic
---


title: Heuristic analysis of Bloom filters

text:
# Question
Title: Heuristic analysis of Bloom filters
I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.

It's all based on the following assumption:

> All $h\_{i}(x)$'s are uniformly random and independent (across different $i$'s and $x$'s)

Setup:

* Bloom filter of length $n$ bits.
* Data set $S$ is inserted into the Bloom filters.

The professors claims that for each bit of array $A$, the probability that it has been set to 1 is (under above assumption, and after data set has been inserted): $1 - (1 - 1/n)^{k|S|}$, where $k$ is the number of hash functions.

I am trying to understand why that's the probability.

He explains that as each of the $|S|$ objects gets inserted (0 or 1), there are $k$ "darts" thrown uniformly at random and independent from each other thrown into the array, so that gives me the intuition of why $k$ is being multiplied by $|S|$. He then says the probability that a given "dart" is one of the $n$ bits is $1/n$. Since there are a total of $k|S|$ "darts" thrown at the end, it makes sense that after the whole set $S$ has been inserted, the probability that a given bit has been hit is $(1/n)^{k|S|}$, and the probability that it hasn't been hit is $(1-1/n)^{k|S|}$. But I don't understand why all that is being subtracted from $1$ at the end to end up being $1 - (1 - 1/n)^{k|S|}$, so clearly I'm missing something...

Can somebody explain this to me?

# Answer
A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$.

We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is *not* hit. For a bit not to be hit, it has to be missed each time. Since it has $k|S|$ opportunities to be hit, and each time it is missed with probability $1-1/n$, in total a bit is missed with probability $(1-1/n)^{k|S|}$. Thus a bit is *not* missed with probability $1-(1-1/n)^{k|S|}$.
> 2 votes

---
Tags: probability-theory, hashing, bloom-filters
---


# Question
Title: Computing $n$th lexicographically smallest permutation of length up to $k$
I wonder how to tackle such problem, to be more specific:

> Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say that the permutation is valid if its length is *up to* $k$ (inclusive).

Here's an example: $S$ = {a, b, c}, $k$ = 4, $n$ = 15

a aa aaa aaaa aaab aaac aab aaba aabb aabc aac aaca aacb aacc ab

Output should be: "ab" as it's the n-th lexicographically smallest permutation of length up to k of this set.

How to do this efficiently?

# Answer
> 1 votes
Your kind of problem reduces to the problem of *enumeration*. For example, suppose that you wanted to know the first letter of the $n$th lexicographically smallest non-empty string of length at most $k$ over the alphabet $S$. You could easily solve that if you could calculate the number of strings of length at most $k$ that start with a given letter.

More generally, the enumeration problem you have to solve in your case is:

> How many strings of length up to $k$ over the alphabet $S$ start with the prefix $w$?

This is not such a hard problem, and I'll let you solve it on your own. I'll also let you figure out how to use the result in order to solve your problem.

---
Tags: algorithms, efficiency, permutations
---


# Question
Title: Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape
Lets say I have a random number generator that spits out uniform numbers from 0 to 1

Next, I have a shape defined by a series of vertices, like { \[0, 0.4\], \[0.5, 0.2\], \[1, 0.4\] }

In those vertices, the first value determines the position and second the distribution weight in that point (interpolated in between).

Now I need a magic function to redistribute the uniform random numbers into a distribution that would statistically match the shape of the vertices provided.

Essentially, if I were to run 10000 random numbers through the function, sort them into buckets like { \[0 - 0.1\], \[0.1 - 0.2\] ... } and count the buckets so that \[x = x, y = count\], it should produce a shape similar to if I were to use the original shape as \[x, y\].

To illustrate

ms paint at its finest.

Anyways, the question - I'm looking for an algorithm to build that magic function.

The shapes that I want to feed it would be based on real world statistics which often don't fit any of the neat looking distributions like gauss or normal, I've seen all kinds of wonky lines.

# Answer
Here is a simple algorithm. Suppose that the shape is given by a sequence $$ (x\_0,y\_0), \ldots, (x\_n,y\_n). $$ Define $A\_i = (x\_i - x\_{i-1}) \cdot (y\_{i-1} + y\_i)$ for $1 \leq i \leq n$, and let $A = \sum\_{i=1}^n A\_i$, $\alpha\_i = A\_i/A$, and $\beta\_i = \sum\_{j=1}^i \alpha\_i$.

> Sample a value $x$ uniformly on $\[0,1\]$, and determine $1 \leq i \leq n$ such that $\beta\_{i-1} \leq x \< \beta\_i$. Let $c = (x-\beta\_{i-1})/(\beta\_i-\beta\_{i-1})$.

Note that $c$ is uniform on $\[0,1\]$.

Here is what we have accomplished so far:

* The probability of obtaining a specific $i$ is proportional to the probability that a random point generated according to the desired density lies between $x\_{i-1}$ and $x\_i$.

This is because the area below the density curve between $x\_{i-1}$ and $x\_i$ is $(x\_i - x\_{i-1}) \frac{y\_{i-1}+y\_i}{2}$.

Consider now the function $$ \begin{align\*} \varphi\_i(t) &= \int\_{x\_{i-1}}^t y\_{i-1} + (y\_i-y\_{i-1}) \frac{t-x\_{i-1}}{x\_i-x\_{i-1}} \\, dt \\ &= y\_{i-1} (t-x\_{i-1}) + (y\_i - y\_{i-1})\frac{(t-x\_{i-1})^2}{2(x\_i-x\_{i-1})} \end{align\*} $$ and its normalized cousin $$ F\_i(t) = \frac{\varphi\_i(t)}{\varphi\_i(x\_i)} = \frac{2y\_{i-1}}{y\_{i-1}+y\_i} \frac{t-x\_{i-1}}{x\_i-x\_{i-1}} + \frac{y\_i-y\_{i-1}}{y\_i+y\_{i+1}} \left(\frac{t-x\_{i-1}}{x\_i-x\_{i-1}}\right)^2, $$ which is the CDF of your density function restricted to the interval $\[x\_{i-1},x\_i\]$.

> Output $F\_i^{-1}(c)$.

Since $c \sim U(0,1)$, the resulting element has CDF $F\_i$, and so has the correct distribution. It remains to explicitly invert $F\_i$. Let $a = \frac{y\_i-y\_{i-1}}{y\_i+y\_{i-1}}$, $b = \frac{2y\_{i-1}}{y\_i+y\_{i-1}}$, and $s = \frac{t-x\_{i-1}}{x\_i-x\_{i-1}}$ (note that $0 \leq s \leq 1$). If $F(t) = c$ then $as^2 + bs = c$, and so we can calculate the output $t$ as $$ s = \frac{-b + \sqrt{b^2+4ac}}{2a}, \qquad t = x\_{i-1} + (x\_i - x\_{i-1}) s. $$ The formula for $s$ simplifies to $$ s = \frac{\sqrt{(1-c) y\_{i-1}^2 + c y\_i^2} - y\_{i-1}}{y\_i-y\_{i-1}}. $$ We can thus rephrase the second step as

> Output $$ x\_{i-1} + (x\_i - x\_{i-1}) \frac{\sqrt{(1-c) y\_{i-1}^2 + c y\_i^2} - y\_{i-1}}{y\_i-y\_{i-1}}. $$

---

Another option for the second step is rejection sampling. Let $A$ be the area below the rectangle bounded by $(x\_{i-1},0),(x\_{i-1},y\_{i-1}),(x\_i,y\_i),(x\_i,0)$, and let $R$ be the upper bounding rectangle $(x\_{i-1},0),(x\_{i-1},y),(x\_i,y),(x\_i,0)$, where $y = \max(y\_{i-1},y\_i)$. Generate random points $(x,y)$ in $R$ repeatedly until one of them belongs to $A$, and output its ordinate $x$. Since the area of $A$ is at least half the area of $R$, on average this requires at most two samples.

---

In the first step you have to determine $i$ such that $\beta\_{i-1} \leq x \< \beta\_i$. While a naive implementation would take time $O(n)$, or $O(\log n)$ using binary search trees, you can use the alias method to reduce sampling time to $O(1)$.
> 2 votes

# Answer
You can use the inverse transform sampling method, as described in Wikipedia. See also https://stats.stackexchange.com/q/176955/2921 and https://en.wikipedia.org/wiki/Ziggurat\_algorithm.
> 1 votes

---
Tags: algorithms, sets, statistics
---


# Question
Title: How to partition the rows of a matrix in such a way that every column satisfies a given condition?
The input is: Given a matrix $\mathbf{A}=\left\[a\_{ij}\right\]$ of nonnegative integers for all $i\in\\{1,\ldots, m\\}$ and $j\in\\{1,\ldots, n\\}$ (where $n\<m$). Nonnegative integers $V\_j$ for all $j\in\\{1,\ldots,n\\}$.

The question is: Find $n$ disjoint sets $S\_j$ of $\\{1,\ldots,m\\}$ such that $$\bigcup\limits\_{j=1}^{n} S\_j=\\{1,\ldots,m\\},$$ $$\quad\quad\quad\\;\\,\sum\_{i\in S\_j}a\_{ij}\geqslant V\_j, \forall\\,j\in\\{1,\ldots,n\\}.$$

So for example, given the matrix

$$ \begin{pmatrix} 7 & 4 & 3\\ 3 & 2 & 7\\ 2& 3 & 4\\ 1 & 1& 5\\ 6 & 10 & 8 \end{pmatrix}, $$ where $n=3$, $m=5$ and $V\_1=12$, $V\_2=10$ and $V\_3=5$.

Then, a solution is $S\_1=\\{1,2,3\\}$, $S\_2=\\{5\\}$ and $S\_3=\\{4\\}$.

I think the difficulty of solving this problem comes from the fact that we would like to partition the rows of a given matrix in such a way that every column satisfies a given condition.

Even though the problem seems related to the exact cover problem, I cannot find a good way to solve it.

Can you suggest a method/algorithm that finds solutions to such problem? If it is a known problem, do you know any reference?

# Answer
As suggested by Yuval Filmus, reduce PARTITION to my problem.

Given an instance of PARTITION, that is a set of nonnegative integers $\\{b\_1, \ldots, b\_k\\}$, is there a subset $S\subset\\{1,\ldots,k\\}$, such that $\sum\_{i\in S}b\_i=\sum\_{i\notin S}b\_i=\frac{\sum\_{i=1}^kb\_i}{2}$?

Let $n=2$, $m=k$, $a\_{ij}=b\_i$ for all $(i,j)\in\\{1,\ldots,k\\}\times\\{1,2\\}$ and $V\_1=V\_2=\frac{\sum\_{i=1}^kb\_i}{2}$.

This is clearly created in polynomial-time.

PARTITION is solved if and only if my problem is solved.

1. If PARTITION is solved: there is a set $S\subset\\{1,\ldots,k\\}$, such that $\sum\_{i\in S}b\_i=\sum\_{i\notin S}b\_i=\frac{\sum\_{i=1}^kb\_i}{2}$. Take $S\_1=S$ and $S\_2=\\{1,\ldots,k\\}\backslash S$. Clearly, $S\_1\cup S\_2=\\{1,\ldots,k\\}$ and $S\_1$ and $S\_2$ are disjoint. Further, we have $$\sum\_{i\in S\_1}a\_{i1}=\sum\_{i\in S\_1}b\_i=V\_1\geqslant V\_1,\\ \sum\_{i\in S\_2}a\_{i2}=\sum\_{i\in S\_2}b\_i=V\_2\geqslant V\_2,$$ and my problem is solved.
2. If my problem is solved: there are disjoint $S\_1$ and $S\_2$ such that $$S\_1\cup S\_2=\\{1,\ldots,k\\},\\ \sum\_{i\in S\_1}a\_{i1}=\sum\_{i\in S\_1}b\_i\geqslant V\_1,\\ \sum\_{i\in S\_2}a\_{i2}=\sum\_{i\in S\_2}b\_i\geqslant V\_2.$$ Since $V\_1=V\_2=\frac{\sum\_{i=1}^kb\_i}{2}$ and $\sum\_{i\in S\_1}b\_i+\sum\_{i\in S\_2}b\_i=\sum\_{i=1}^kb\_i$, we must have $$\sum\_{i\in S\_1}b\_i=\sum\_{i\notin S\_2}b\_i=\frac{\sum\_{i=1}^kb\_i}{2},$$ and PARTITION is solved.

Therefore, my problem is NP-hard.

To solve the problem, let us write it as integer programming problem as suggested by Yuval Filmus. To do so, introduce the binary variable $x\_{ij}$ that is equal to $1$, if $i$ is in set $S\_j$, and, $0$ otherwise.

\begin{align} & {\underset{\mathbf{ x }}{\text{maximize}}} & & 0\\\\[6pt\] & \text{subject to} & & \sum\_{i=1}^ma\_{ij}x\_{ij}\geqslant V\_j,\forall\\, j\in\\{1,\ldots,n\\},\tag{C1}\\\\[6pt\] & & & \sum\_{j=1}^nx\_{ij}=1, \forall\\, i\in\\{1,\ldots,m\\},\tag{C2}\\\\[6pt\] & & & x\_{ ij }\in\\{0, 1\\}, \forall (i,j)\in\\{1,\ldots,k\\}\times\\{1,\ldots,n\\}\tag{C3}. \end{align}

Even though this solves my problem, I need to develop a greedy algorithm for it, can I do that?
> 4 votes

---
Tags: algorithms
---


title: Variant of Turing machine

text:
# Question
Title: Variant of Turing machine
How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the accept state, and this action does not change the acceptance outcome.

# Answer
> 1 votes
In order to prove that your modified Turing machine is equivalent to a standard Turing machine, you need to do two things:

1. Given a standard Turing machine $T\_1$, give a modified Turing machine $T\_2$ such that $L(T\_1) = L(T\_2)$.
2. Given a modified Turing machine $T\_3$, give a standard Turing machine $T\_4$ such that $L(T\_3) = L(T\_4)$.

Good luck!

# Answer
> 1 votes
You need to begin with a formal definition of a Turing Machine, such as the one given (from a common textbook) in Wikipedia:

The 7-tuple: $\<Q,\Gamma,b,\Sigma,\delta,q\_{0},F\>$

Here $F$ is given as the Final or Acceptance States. In your example the Acceptance states are not final, and so the definitions of $\delta$ and $F$ will need to change, perhaps by introducing a new category $A$. So you can construct a second, slightly different definition of a Turing Machine as the variant.

Then the question is to establish that if the original definition accepts string $\<x\>$ so does the variant and vice-versa.

---
Tags: turing-machines, computation-models, simulation
---


# Question
Title: How to deal with arrays during Hoare-style correctness proofs
In the discussion around this question, Gilles mentions correctly that any correctness proof of an algorithm that uses arrays has to prove that there are no out-of-bounds array accesses; depending on the runtime model, this would cause a runtime error or access to non-array elements.

One common technique to perform such correctness proofs (at least in undergrad studies and probably in automated verification) is by using Hoare logic. I am not aware that the standard set of rules containes anything relating to arrays; they seem to be restricted to monadic variables.

I can imagine adding axioms of the form

$\qquad \displaystyle \frac{}{\\{0 \leq i \lt A.\mathrm{length} \land {P\[A\[i\]/E\]} \\}\ A\[i\] := E;\ \\{P\\}}$

However, it is not clear to me how you would deal with an array access on the right hand side, i.e. if it is part of a complex expression $E$ in some statement $x := E$.

> How can arrays accesses be modelled in Hoare logic so that the absence of invalid accesses can and has to be proven for program correctness?

Answers may assume that we disallow array elements to be used in statements other than $A\[i\] := E$ or as part of some $E$ in $x := E$ as this does not restrict expressiveness; we can always assign a temporary variable the desired value, i.e. write $t := A\[i\];\ \mathtt{if} ( t \> 0 ) \dots$ instead of $\mathtt{if} ( A\[i\] \> 0 )\dots$.

# Answer
Your axiom is not really an axiom, it's missing hypotheses. Simple presentations of Hoare logic manipulate formulas of the form $\\{P\\} C \\{P'\\}$ where $P$ and $P'$ are logical formulas and $C$ is a command. You do need to **ensure that $C$ is well-formed**. In simple languages such as the ones often used for a first introduction to Hoare logic, well-formedness is syntactic: it's typically a matter of checking that $C$ conforms to a context-free grammar, and possibly that the free variables are within a permitted set. If the language includes constructs that have a semantic correctness, such as accesses to array elements, you need to add hypotheses to express this semantic correctness.

Formally, you can add judgements to express the correction of expressions and commands. If expressions have no side effects, they need no postconditions, only preconditions. For example, you can write well-formedness rules such as $$ \dfrac{\\{P\\} \\;\\; E \text{ wf}} {\\{P \wedge 0 \le E \< \mathrm{length}(A)\\} \\;\\; A\[E\] \text{ wf}} \qquad \dfrac{\\{P\\} \\;\\; E\_1 \text{ wf} \qquad \\{P\\} \\;\\; E\_2 \text{ wf}} {\\{P\\} \\;\\; E\_1 + E\_2 \text{ wf}} $$ and only allow well-formed expressions in commands: $$ \dfrac{\\{P\[x\leftarrow E\]\\} \\;\\; E \text{ wf}} {\\{P\[x\leftarrow E\]\\} \\;\\; x := E \\{P\\}} $$

A different approach is to treat all expressions as well-formed, but to make any expression involving an ill-formed calculation have a special value $\mathbf{error}$. In languages with run-time bounds checking, $\mathbf{error}$ means “this program raised a fatal exception”. You would then keep track of whether a program errored out through a logical predicate $\mathbf{Error}$; a program is only valid if you can prove that its postcondition implies $\neg\mathbf{Error}$. $$ \dfrac{} {\\{P\[x\leftarrow E\]\\} \\;\\; x := E \\;\\; \\{P \vee \mathbf{Error}\\}} \qquad \dfrac{P\[x\leftarrow E\] \implies E \not\rightarrow \mathbf{error}} {\\{P\[x\leftarrow E\]\\} \\;\\; x := E \\;\\; \\{P\\}} $$

Yet another approach is to consider a Hoare triple to hold only if the program terminates correctly. This is the usualy approach for nonterminating programs: the postcondition holds when the command terminates, which might not always happen. If you treat run-time errors as non-termination, you sweep all correctness issues under the hood. You will still need to prove the correctness of the program somehow, but it need not be in Hoare logic if you prefer some other formalism for that task.

By the way, note that expressing what happens when a compound variable such as an array is modified is more involved that what you wrote. Suppose $P$ was, say, $\mathrm{IsSorted}(A)$: the substitution $A\[i\]\leftarrow E$ would not change $P$, yet the assignment $A\[i\] \leftarrow P$ might invalidate $P$. Even if you restrict the syntax of predicates to only talk about atoms, consider the assignment $A\[A\[0\]-1\] := A\[0\]$ under the precondition $A\[0\] = 2 \wedge A\[1\] = 3$: you cannot make a simple substitution to obtain the correct postcondition $A\[0\] = 1 \wedge A\[1\] = 1$, you need to evaluate $A\[0\]$ (which can be difficult in general, since the precondition might not specify a single possible value for $A\[0\]$). You need to perform the substitution on the array itself: $A \leftarrow A\[i\leftarrow E\]$. Mike Gordon's lecture notes have a good presentation Hoare logic with arrays (but without error checking).
> 9 votes

# Answer
As mentioned by Gilles, there is an array assignment axiom (see Gordon's notes, Sec. 2.1.10): $$ \dfrac{} {\\{Q\[A \mapsto A.store(i,expr) \] \\} \\;\\; A\[i\] = expr \\;\\;\\{ Q \\}} $$ In words, if you have an array assignment, then replace the original array by array `A.store(i,expr)` which has at position `i` the value `expr`. Note that if you already have `A.store(i,vi)` on the post, and assign `A[j]=vj`, then you should get `A.store(j,vj).store(i,vi)` as the pre (yes, in this order -- recent update is executed first!).

Additionally, we need the array access axiom: `A.store(i,v)[i]` can be replaced by `v` ("if you access $i$th element that you just updated, then return the assigned value").

I think in order to prove a program with arrays is correct ("no out-of-bound accesses"), the above axioms are enough. Let's consider the program:

```
...
A[i] = 12
...

```

We would annotate this program:

```
...
@ {0<i<A_length}
A[i] = 12
...

```

where `A_length` is a variable that specifies the array length. Now try to prove the annotation -- namely, work it out backwards (from bottom to top, "as usually" in Hoare proofs). If on top you get `{false}`, then the out of bound access can happen, otherwise, the expression you got is the precondition under which no out-of-bound accesses are possible. (also, we need to ensure that when array is created like `int A=int[10];` then in the post-condition we have `{A_length==10}`).
> 1 votes

---
Tags: proof-techniques, semantics, arrays, hoare-logic, software-verification
---


# Question
Title: Is the set of strings $0^{2k}10^{2k}10^{k}$ for $k \geq 0$ context-free?
I am able to solve $0^{k}10^{k}10^{j}$ where $ k \< j$. and I was able to see that this is also a concatenation of two strings. How to do it for $0^{2k}10^{2k}10^{k}$ for $k \ge 0$?

# Answer
> 6 votes
There is no context free grammar that can accept those two sets. You can show that using the pumping lemma for CFLs.

Suppose $L = \\{x \in \\{0,1\\}^\* \mid x = 0^{2k}10^{2k}10^{k}, k \geq 0 \\}$
Let $n$ be the pumping lemma constant.
I can choose $z = 0^{2n}10^{2n}10^{n} $. Clearly $|z| \geq n$. Now let $z = uvwxy$ be any decomposition of $z$ such that $|vwx| \leq n$ and $|vx| \> 0$.

**Case 1**: Either $v$ or $x$ contains at least one $1$. Then the string $z^\prime = uv^0wx^0y = uwy$ contains strictly less that two $1$s, so $z^\prime \notin L$.

**Case 2**: Both $v$ and $x$ entirely consist of $0$s. Note that since $|vwx| \leq n$, therefore $vwx$ can cover at most 2 'parts' (contiguous substring of $0$s) of the original string $z$. So, we again choose the string $z^\prime = uv^0wx^0y = uwy$. The third 'part' of the string which is not covered by $vwx$ will then violate the condition and $z^\prime \neq 0^{2m}10^{2m}10^m $. So, $z^\prime \notin L$.

So, $L$ is *not* a context-free language. A similar proof can be given for $0^{k}10^{k}10^{2k}$. I have no idea how you were able to 'solve' this one!

## EDIT

The question was edited from context-free grammars to context sensitive grammars. The language $L = \\{x \in \\{0,1\\}^\* \mid x = 0^{2k}10^{2k}10^{k}, k \geq 0 \\}$ can indeed be generated from a context-sensitive grammar.

$$ \begin{align} S^\prime &\rightarrow WS \\ S &\rightarrow LRS0 \mid 1 \\ RL &\rightarrow RM \\ RM &\rightarrow LM \\ LM &\rightarrow LR \\ WL &\rightarrow WV \\ WV &\rightarrow LV \\ LV &\rightarrow LW \\ W &\rightarrow 1 \\ L1 &\rightarrow 001 \\ L0 &\rightarrow 000 \\ 1R &\rightarrow 100 \\ 0R &\rightarrow 000 \end{align} $$

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


# Question
Title: How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$
Lately, I asked this question to find the maximal set of elements $S$ of a given array $T$ such that every element of $S$ is greater than or equal to the cardinality of $S$.

My question is now different. How to find ***all*** maximal sets $S\_i$ of a given array $T$ such that every element of $S\_i$ is greater than or equal to the cardinality of $S\_i$.

For example, if $T=\[9, 8, 2, 2, 1\]$, then all maximal sets that satisfy the condition are $S\_1=\[9, 8\]$, $S\_2=\[9, 2\]$, $S\_3=\[9, 2\]$, $S\_4=\[8, 2\]$, $S\_5=\[8, 2\]$ and $S\_6=\[2, 2\]$.

My recursive solution or the solutions given in the previous question do not generate ***all*** maximal sets.

Is there any efficient algorithm that finds ***all*** maximal sets of such problem?

I think one way to solve the problem is to find *a* maximal set $S$ and return its size $|S|$--using any algorithm from this question. Then, generate all combinations $\displaystyle\binom{|T|}{|S|}$ and find which one of these combinations satisfies the condition. But can we do better?

# Answer
Assuming that by *maximal sets* you mean sets of maximal size (rather than sets which are inclusion-maximal), then there is a very simple algorithm. First, find the maximal size $s$. Second, filter out all elements smaller than $s$. Third, output all subsets of size $s$ of the remaining elements.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Prove that L = { wu; wu in {a,b}* and |w| = |u| } is not regular
Prove that $L = \\{wu, wu \in \\{a,b\\}^\* \ \land |w| = |u| \\}$ is not regular.

I'm trying to approach this problem with the pumping lemma.

So I know I have to pick a string *s*, which can be split into *xyz* components in terms of the pumping length, *p*.

But I cannot seem to find an s.

For example using $ s = a^p b^p$ or $s = a^p a b^p b $, since $|xy| \le p \land |y| \> 0$, then *y* must contain some *a*'s. So we can try to pump $x y^i z$ to see the new string is still in L.

The issue is that if y contains an even number of *a*'s it can always be pumped because the resulting string will have even length so *w* can be the first half and *u* be the second half.

# Answer
As Rick Decker said $L$ is a regular language. For example: $$L= \mathscr{L}(\\,(aa | ab | ba | bb)^\*\\,)$$

If your teacher asked you to prove that $L$ is not regular in an exam then he is a big troll. Otherwise remember that the pumping lemma is only usefull to prove that a language is not regular and if you fail to find the contradiction in the lemma then that doesn't prove anything. $L$ can be regular or irregular at that point.

In this answer I covered some common mistakes when students use the pumping lemma: Common Mistakes
> 1 votes

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


# Question
Title: Shortest path between two points with n hops
Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just give the trivial answer of $A\to B$. I'd like to find an $n$-edge path (e.g. for $n=4$, find $C$, $D$ and $E$ which minimize total path length of $A\to C\to D\to E\to B$).

# Answer
If vertices can be visited more than once, then yes: you can create $n+1$ copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v\_1, \dots, v\_{n+1}$ and each edge $uv$ in the original graph becoming the set of edges $u\_iv\_{i+1}$ for all $1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex $A\_1$ and end vertex $B\_{n+1}$. Intuitively, each edge traversed in any path necessarily takes you to the next "level" of the graph.

If vertices cannot be visited more than once, then there's no known poly-time algorithm, since setting setting $n$ to one less than the number of vertices would solve the NP-hard Hamiltonian Path problem. (Although the HP problem technically asks for *any* path that visits all vertices exactly once, a poly-time algorithm for the simple-paths version of your problem would nevertheless give you a poly-time algorithm for HP: just run it $O(n^2)$ times, one for each possible pair of start and end vertices.)
> 11 votes

# Answer
I will describe an algorithm that will solve any hamiltonian path problem in any number of dimensions in polynomial time. Due to triangle inequality we know the solution to a hamiltonian path problem will be a perimeter( on the euclidian plane). The brute force practice of finding every possible path can be pared in to polynomial time by only finding sufficiently short possible perimeters. The data sets of distances between points(in any number of dimensions) will be sorted. The three shortest distances will form a triangle. For each side of this triangle the next shortest point to include will be found by finding the closest point to include along each side. Using the sorted tables the computer will find the next closest non-included point and then sum with the path the other point on the perimeter. These possible inclusions can be stored in a sorted list so that as every new point is added only two new line segments will need to find their next closest points. This continues until the first possible solution is found. This solution becomes the goal post and will be no longer than 200% of the actual solution. From my initial thought errors induced would have to be under 15% of the next closest point inclusions. The algorithm would then be able to go thru the data and construct new possible solutions by including the next shortest points up to 15% longer than the first path. Recursive addition will then construct a new possible perimeter until it becomes the new goalpost or passes it.
> -2 votes

---
Tags: graphs, shortest-path, traveling-salesman
---


# Question
Title: How to partition a set into disjoints subsets each of given size?
The input: Given a set $U=\\{1, \ldots, k\\}$ called the universe. Let $C=\\{S\_1, \ldots, S\_n\\}$ be a collection of subsets of $U$ and let $ s\_j$ be a nonnegative integer for all $j=1,\ldots,n$ such that $\sum\_{j=1}^{n} s\_j=k$.

The question: Are there $n$ subsets $A\_j$ of $S\_j$ (i.e., $A\_j\subset S\_j$) such that

$$ \quad\bigcup\limits\_{j=1}^{n}A\_j=U,\\ \quad \quad\\;\\;\\;\\,\\;\\;\\,A\_j \cap A\_i = \emptyset, i\neq j,\\ |A\_j|=s\_j. $$

Is this problem NP-hard?

I was trying to reduce PARTITION to this problem by setting $n=2$ and $k$ an even number and $s\_j=k/2$ but the constraints $|A\_j|=k/2$ do not help me.

# Answer
> 7 votes
When $s\_j = 1$ for all $j$, the problem is the same as deciding whether a bipartite graph has a perfect matching. In the general case, we can solve it using maximum flow.

Set up a flow network with the following components:

* A source $s$, a sink $t$, a vertex $S\_j$ for each set, and a vertex $x\_i$ for each element in the universe.
* Connect $s$ to each $S\_j$ with an edge of capacity $s\_j$.
* For each $x\_i \in S\_j$, connect $S\_j$ to $x\_i$ with an infinite capacity edge.
* Connect each $x\_i$ to $t$ with an edge of capacity $1$.

Now compute the maximum flow. If it equals $|U|$ then the instance has a solution. Moreover, you can extract the solution from a maximum integer flow.

The max flow min cut theorem also gives us a Hall-like criterion: a solution exists if for every set $X$ of elements, $$ \sum\_{j\colon S\_j \cap X \neq \emptyset} s\_j \geq |X|. $$ That is, if we sum the "capacities" $s\_j$ for all sets $S\_j$ that intersect $X$, then we need to get at least $|X|$. This is clearly a necessary condition, and the max flow min cut theorem shows that it is sufficient.

---
Tags: reductions
---


# Question
Title: How to "convert" nested loops into code taking advantage of parallel computing?
Let's say that an algorithm uses several nested loops to accomplish it's task, for instance :

* An algorithm treating voxels on several frames, so there would be four dimensions : t (for time), x, y and z.
* An algorithm evaluating a function that takes n entries, searching for which entries there is a certain result. For instance if we search f(a, b, c, d, e) = 2001 where each variable is tested between 0 and 100.

From what I understand, several APIs make you model the way your kernel is executed by the GPU with a 1-2-3d grid, but many of them don't provide n-dimensional grids for execution.

So if I had to treat a simple 2D image of 1024x2048 pixels, I could have simply made my kernel execute itself over a grid of that size instead of having to nest loops, but since most grids seem to be limited to 3 dimensions, what to do when I need to execute work for more than 3 dimensions (like in my second example) ?
Should I put loops directly in my kernels ?

Thank you.

**EDIT :**
Some pseudocode : Let's say that I want to test for which inputs a given function has a certain value, I could have some *brute force* approach like that :

```
for a in 1...100 {
for b in 1...100 {
for c in 1...100 {
for d in 1...100 {
     if f(a,b,c,d) == 1984 {
        equationSolutions.append((a,b,c,d))
     }
}

```

Now with grids, a certain kernel can be executed *over* the grid (sorry, I may not use the right term, there is a much better explaination about grids here), so if you want to treat each pixel of an image of 2048x512 pixels, instead of doing :

```
for x in 0...imageWidth {
for y in 0...imageHeight {
   treatPixel(x,y)
}

```

You will define grid as a 2D grid of size 2048x512 and then your kernel won't contain any loop, it will just get it's position on the grid as an argument : func myPixelFunction(positionInGrid) { treatPixel(positionInGrid.x, positionInGrid.y) }

My question is that, since most grids are limited to 3 dimensions, what to do if you want to execute code that requires *more* than 3 dimensions ? (like my code trying to solve a function ?).

From what I understand, in cases like the ones I showed, grids make more sense than loops on GPUs since grids enable to parallelise the work, making several threads work in parallel on the same function/kernel, but while it's really easy to simply use position in grid when you are treating data that is representable by the grid, I don't understand how to write code using grids when I needs to word on "additional dimensions".

**EDIT #2 :** This SE question is similar to mine.

# Answer
Let's say you want to iterate over `a,b,c,d` each ranging from `0..99`. There are two ways to do that.

## Approach #1: fewer nested loops

Set up a 100x100 grid, which will handle `a,b`. Handle `c,d` by explicit nested loops:

```
treatPixel(a,b):
for c in 0..99:
    for d in 0..99:
        doSomething(a,b,c,d)

```

## Approach #2: bigger grid

Set up a 10,000x10,000 grid. Then decode the x-coordinate to `a,b` and the y-coordinate to `c,d`, like this:

```
treatPixel(x,y):
a := floor(x/100); b := x mod 100
c := floor(y/100); d := y mod 100
doSomething(a,b,c,d)

```

## Which to choose?

Either one should work.

Assuming the number of iterations greatly exceeds the number of compute elements in the GPU, the difference between the two probably comes down to different memory locality effects. You can try implementing both of them, benchmarking, and seeing if one is faster. If there is little or no memory access and `doSomething()` is compute-bound, they'll probably both run at about the same speed.
> 2 votes

---
Tags: parallel-computing
---


# Question
Title: Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows:

> A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q\_0,\square,F)$ (as in the definition of TM) with the restriction that $\Sigma$ must contain two symbols $\[$ and $\]$, such that $\delta(q\_i,\[)$ can contain only elements of the form $(q\_j,\[,R)$ and $\delta(q\_i,\])$ can contain only elements of the form $(q\_j,\],L)$

Informally this can be interpreted as follows:

> In linear bounded automata, we allow the Turing machine to use only that part of the tape occupied by the input. The input can be envisioned as bracketed by left end marker $\[$ and right end marker $\]$. The end markers cannot be rewritten, and RW head cannot move to the left of $\[$ or to the right of $\]$.

Now I read that context sensitive grammar imitates the function of LBA and is defined as follows:

> A grammar is CSG if all productions in context sensitive grammar takes form $$x\rightarrow y,$$ where $x,y\in(V\cup T)^+$ and $|x|\leq|y|$

Now people say that CSG cannot contain lambda or empty production (which takes form: $x\rightarrow \lambda$) as it will make make it impossible to meet the requirement $|x|\leq|y|$ and this can be understood.

However, what I don't understand is how informal interpretation of the working of LBA given above explains ***why LBA cannot accept empty string*** (which is why CSG does not have lambda production). Can anyone explain?

# Answer
Linear-bounded automata are able to accept the empty string. The equivalence between linear-bounded automata and context-sensitive grammars needs to be cognizant of this discrepancy between the two models. Usually a context-sensitive grammar is allowed one extra product to optionally produce the empty string. Alternatively, there is an equivalence between LBAs not accepting the empty string and CSGs.
> 7 votes

---
Tags: automata, context-sensitive
---


# Question
Title: What is the complexity of a variation of the Coupon collector's problem?
I need to know the complexity of the following algorithm:

Draw elements from a set of size $m$, one by one, randomly, with replacement, until coming across $n$ different elements from the set ($n\le m$). We do not care what are the numbers drawn, and halt once $n$ different numbers were seen during this process.

This is a variation of the Coupon collector's problem, where one continues picking until seeing all $m$ elements of the set.

Example:

We draw numbers from the set $\\{1,2,3,4,5\\}$, $n=3$, $m=5$. The output $\\{1,5,2\\}$ is produced by the following series of draws:

$1,1,5,1,5,2$

from the pool $\\{1,2,3,4,5\\}$. In this case, we halt after $6$ operations.

What is the expected time complexity of this algorithm?

# Answer
When $m$ is much larger than $n$, the expected number of trials is basically linear in $n$. We can make this more precise, as shown below.

Let $T\_n$ be the random variable which counts the number of trials up to seeing $n$ different elements, where the elements are picked uniformly at random from a set of size $m$.

You can write $T\_n$ as the sum of geometric random variables

$$T\_n=1+G\left(1-\frac{1}{m}\right)+G\left(1-\frac{2}{m}\right)+...+G\left(1-\frac{n-1}{m}\right)$$

where $G(p)$ is a geometric random variable with parameter $p$ (number of trails up to the first success, where success happens with probability $p$ (I leave it to you to prove the equivalence).

Using linearity of expectation:

$$\begin{align\*} \mathbb{E}\left\[T\_n\right\]&=\sum\limits\_{i=0}^{n-1}\mathbb{E}\left\[G\left(1-\frac{i}{m}\right)\right\]\\ &=\sum\limits\_{i=0}^{n-1}\frac{m}{m-i}\\ &=m\left(\frac{1}{m}+\frac{1}{m-1}+...+\frac{1}{m-n+1}\right)\\ &=m\left(H\_m-H\_{m-n}\right) \end{align\*}$$

where $H\_k$ is the harmonic sum, which satisfies $\frac{1}{2(k+1)}\le H\_k-\ln k - \gamma\le \frac{1}{2k}$, where $\gamma$ is the Euler–Mascheroni constant (see Wolfram's page on harmonic numbers). Using these bounds for harmonic numbers we have:

$$\begin{align\*} \mathbb{E}\left\[T\_n\right\]&\le m\left(\frac{1}{2m}+\ln m +\gamma -\left(\frac{1}{2(m-n+1)}+\ln(m-n)+\gamma\right)\right)\\ &\le m\left(\frac{1}{2m}+\ln\frac{m}{m-n}\right)=\frac{1}{2}+m\ln\frac{m}{m-n}. \end{align\*}$$

Note that $m\ln\frac{m}{m-n}=m\ln\left(1+\frac{n}{m-n}\right)\approx n$ when $n\ll m$, so for $m$ much larger than $n$, the expected number of trials is linear in $n$.
> 6 votes

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


# Question
Title: What is the advantage of seperate chaining over open addressing?
Hash tables resolve collisions through two mechanisms,

1. separate chaining or open hashing and
2. open addressing or closed hashing.

Though the first method uses lists (or other fancier data structure) in hash table to maintain more than one entry having same hash values, the other uses complex ways of skipping n elements on collsion.

Since, while searching, both mechanisms requires looking up for more entries on collision and Seperate chaining may require lesser number of searches to find the match.

What kind of advantages does it have over separate chaining?

# Answer
> 4 votes
Suppose that you have a very large number of sufficiently uniform elements, $n$, that you want to hash. We want to minimize lookup time, obviously.

If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is sufficiently uniform or not, but for the sake of simplicity we can assume that it is. What are the downsides of this? Linked lists and most other data structures that we would use to do this make heavy use of pointers. A single query takes $O(n)$ pointer dereferences.

Now consider two typical methods of open addressing: linear probing and quadratic probing. Linear probing traverses the space allot for open addressing and places the element that it is hashing at the first available memory location (at the $i^\text{th}$ step, we look at index $i$ to see if it is free). Quadratic probing traverses by incrementing the index by $i^2$ on each step. This can lead to immense speed-up due to its cache-friendliness (as mentioned in the first comment, this is called spatial locality -- I'd suggest reading this if you're unfamiliar).

# Answer
> 4 votes
In addition to what everyone else has said, you can get some of the locality back in a separate chaining scenario by unrolling the linked list.

Assuming a C-esque language, separate chaining might naively be implemented with a structure like this:

```
struct hash_node {
    unsigned hash_value;
    void* data;
    struct hash_node* next;
};

```

There are plenty of variants on this. If you have some control over the data that is being stored in the hash table, for example, you might be able to store the "next" pointers in there. If fast removal is important, you might use a doubly-linked list. You get the idea.

However, if you expect hash slots to collide far more often than hash values, this is an alternative:

```
#define HASH_UNROLL  4

struct hash_node {
    unsigned hash_values[HASH_UNROLL];
    void* data[HASH_UNROLL];
    struct hash_node* next;
};

```

The hash nodes are a little bigger, but all of the hash values to check are in the same cache line. If you're particularly lucky, the compiler may even turn this into a SIMD operation for you.

If the hash table is stored on disk, variations of this technique can improve locality much more than open addressing, at the cost of using extra space. See, for example, extendible hashing.

Some additional tradeoffs are:

* Resizing a hash table *can* be faster with separate chaining if worst-case performance (as opposed to amortised) is an issue.
* It's much simpler to implement deletion with separate chaining, although "ease of implementation" is not necessarily your biggest concern. Look up Robin Hood hashing for details on how to arrange an open addressing hash table to support efficient deletion.
* It's much simpler to make a separate chaining-based hash table concurrent, since you can lock each chain separately. Of course, there are concurrent variants of open addressed hash tables, such as hopscotch hashing (a variant on cuckoo hashing), which seem to perform well in practice.

# Answer
> 1 votes
In addition to what Bharadwaj said, you don't have to use an association list to implement separate chaining. For example, Java 8 uses red-black trees instead of linked lists for `HashMap`. Theoretically, this reduces the worst-case scenario of a hash table from $O(n)$ to $O(\log n)$. Of course, in instances where your buckets remain small (e.g. small hash tables, or if you dynamically resize your table as more elements are added) this may or may not be faster than just searching a linked list linearly.

---
Tags: data-structures, hash-tables, dictionaries
---


# Question
Title: Finding coprimes closest to a certain target
Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$.

Where $m$ is odd, I have no problem producing an outcome close to the target, simply by squaring $2$ until close enough to the target.

When $m$ is even, I have a bit more trouble. I have tried a few different methods with no success. I have tried starting with $p = 3$, then multiplied $p\cdot\mathrm{gcd}(p-1, m)$ until $p$ and $m$ share all factors (in other words, until $\mathrm{gcd}(p-1, m) = 1$). This eventually finds a coprime, but there is no guarantee that it is close to the target, and I'm not sure how to operate on the number from here to get another coprime closer to the target.

The algorithm needs to be able to handle massive numbers with hundreds of digits, so it needs to be pretty efficient.

I'm not sure if I'm missing a necessary fact about coprime numbers, or if I'm just misinterpreting the info I have. Can anyone point me in the right direction? Maybe a fact about coprime numbers that I'm missing?

# Answer
> 2 votes
If you want the truely closest coprime to $\frac 4 7m$, you could start with $n = \mathrm{round}(\frac 4 7m)$. Then, while $\gcd(n,m) \neq 1$, try again with $n$ being the closest number to $\frac 4 7 m$ such that $n - q \not \equiv 0 \mod \gcd(q,m)$ for any previously checked number $q$ (keep track of previously checked numbers and gcds in a list)

Checking one candidate has complexity $\mathcal O(\log(m))$. The probability of any two numbers being coprime is $\frac 6 {\pi^2} \approx 60\\%$ so the numbers of candidates to check should be $\mathcal O(1)$ on average.

Overall this should find you the closest coprime in $\mathcal O(\log(m))$ operations.

# Answer
> 1 votes
Let m = 7i + j, 0 ≤ j \< 7. Let p = 4i + k for some small k. When we calculate gcd (p, m) we get the following pairs:

```
7i + j, 4i + k // subtract right hand side from left and exchange
4i + k, 3i + j - k // subtract right hand side from left and exchange
3i + j - k, i + 2k - j // subtract 3x right hand side
i + 2k - j, 4j - 7k

```

so we need gcd (m, 4j - 7k) = 1. i and j are fixed. Check values k in the right order (the order is 0, 1, -1, 2, -2, 3, -3, 4, except you swap each pair if j ≥ 4). Ignore k where 4j - 7k = 0. For each k find the prime factors of 4j - 7k and check if m has any of these factors. If there are no common prime factors you found p = 4· i + k.

To make the search faster, you would collect as many prime factors as possible with a product P, as long as gcd (m, P) can be calculated quickly.

Worst case is when m has all the prime factors of 4j - 7k for many consecutive values k, but the number of different prime factors that a number m can have is quite limited, something like $\log m / \log \log m$

---
Tags: algorithms, primes
---


# Question
Title: Decidability algorithm, whether substring belongs to L
It isn't very hard to decide if **word** belongs to language L. CYK algorithm should do here.

Occured thought, can CYK be modified to detect if **all words** of language L contain some specific *subword*?

# Answer
On the contrary, it can be arbitrarily hard to decide if a word is in a language. Not only are there undecidable languages (such as the halting language), but there is an infinite hierarchy of undecidable languages, each one even harder than the previous one!

It also seems unlikely that an algorithm for deciding membership in a language would be easily modified to decide if every string in a language has some particular property. That's a completely different problem, requiring completely different analysis.
> 2 votes

---
Tags: context-free, decision-problem
---


# Question
Title: What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?
During a programming contest I was asked to find just smallest prime number to given number N. As Sieve cannot be used and brute force also doesn't work.

So, I was wondering is there any other faster implementation.

Here N -\> (2, 10^18).

# Answer
By fast primary testing you can test whether a given number is probably prime or not, actually methods like Miller Rabin are very fast and because we know the gap of size $O(\log n)$, between two consecutive primes, you can expect that when you start from $N$, you should visit few numbers by fast primarily testing, also, in most cases, fast primarily testing algorithms for the range you mentioned are correct.

In your case, because your numbers are bounded just few composite numbers can pass the miller rabin test which are:

2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321

You can see them in this list, So you just need to check the number that passed the Miller Rabin test, is in above list or not, and by using this code, is possible to do it in less than a second.
> 4 votes

# Answer
Use a sieve first before running the probabilistic primality testing algorithm. Make a list of the first $L$ primes (you'll have to decide on $L$, which should depend on $N$), and compute $N \pmod {p\_i}$ for each of these primes. Now create an array of size $C\log N$ covering the $C\log N$ numbers culminating in $N$ (you'll have to decide on the constant $C$), and using the values of $N \pmod{p\_i}$, mark off all multiples of $p\_i$. When you're done going over the first $L$ primes, you will have a substantially reduced collection of integers to test for primality.

As a simple illustration, if you just mark off even numbers, your algorithm will run twice as fast; also multiples of $3$, thrice as fast; in general, the speedup factor is $(1-1/p\_1)\ldots(1-1/p\_L) \approx 1/\log L$. Using this approximation, you should be able to estimate what value of $L$ you should choose (but be sure to try it out anyway).
> 1 votes

# Answer
If n ≤ $10^{18}$ then checking whether n is prime by doing trial division would be reasonably fast; you can use only divisors that are not divisible by 2, 3 and 5 (8 out of 30) or not divisible by 2, 3, 5 and 7 (48 out of 210), meaning about 230 million divisions.

You can implement a sieve for the numbers n - 500 to n at quite exactly the same speed. That lets you find the next smallest prime in maybe 3 or 4 seconds.

Finding the next smaller probable prime using the Miller-Rabin test should be significantly faster, but then it is probabilistic.
> 0 votes

---
Tags: algorithms, primes
---


title: integer factoring using Fermat's method

text:
# Question
Title: integer factoring using Fermat's method
Reading an article on integer factorization I implemented the following - rather inefficient - factorization method:

> Every odd composite can be factored as a difference of squares: $$ ab = \left\[\tfrac{1}{2}(a+b)\right\]^2 - \left\[\tfrac{1}{2}(a-b)\right\]^2$$ We can look at values of $f(x) = x^2 - n$ until we find a perfect square and factor.

Here's my implementation in Python.

```
def fermat(n):
    x = int(np.sqrt(n))+1
    y = int(np.sqrt(abs(y*y - n)))

    while( n - x*x + y*y != 0):
        x += 1
        y = int(np.sqrt(abs(x*x - n)))

    return x, y

```

How expensive are the square root calculations here? Are they necessary? In order to check I have a perfect square, I compute $\lfloor \sqrt{x^2-n}\rfloor$ many times.

# Answer
> 4 votes
Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing *floating-point* square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and moreover the range of floating-point numbers is limited. Use a *bignum* package instead.

# Answer
> 3 votes
You absolutely don't have to compute most of the square roots.

You want to know whether the square root of $x^2 - n$ is an integer, that is you want to know whether $x^2 - n$ itself is a square. You don't need to know the actual square root as long as you know it is no integer.

Take d = 20,160 and create a bitmap of which integers are a square modulo 20,160 - only one in 30 is. Check whether ($x^2 - n$) modulo 20,160 is in the table. In 29 out of 30 cases the answer is "no", and $x^2 - n$ is not a square.

Also, less than one in 7 integers are squares modulo 20,387, 21,607, 17,641, or 22,231. If you add these tests then calculating a square root is needed in less than one 72,000 cases.

---
Tags: algorithms, number-theory, factoring
---


title: Noncontext free for quotient

text:
# Question
Title: Noncontext free for quotient
Have such exercise: Let $L\_1=\\{a^{2n}b^n|n\geq1\\}^\*$

and $L\_2=\\{b^na^n|n\geq 1\\}^\*b$

Prove, that $L\_1, L\_2$ are context free, while quotient $L\_1/L\_2$ is not context-free.

(This is home exercise, which I am not sure what to make of it. 3rd one)

Anyway, proving $L\_1, L\_2$ are CFL is trivial.

For $L\_1$:

S-\>aaSb|$\epsilon$

For $L\_2$

S-\>Ab

A-\>bAa|$\epsilon$

So far so good, grammar can be constructed, i.e CFL. Fine.

But quotient.. Lets list few words for $L\_1$: $\epsilon$ then: aab, aabaab, aabaabaab, $\dots$ then aaaabb, aaaabbaaaabb, $\dots$ and so on - string under Kleene, which contains twice as much $a$ than $b$

Now about $L\_2$ words: b then bab,babab,bababab,$\dots$ then bbaab,bbaabbaab,$\dots$, ie - $(b^na^n)^\*b$

But.. Only words in $L\_1$ are of format which ends in suffix ...ab are where $n=1$: $aab,aabaab,\dots$, moreover - if we take string from $L\_1$, for example $aabaab$, we kinda remove trailing $b$ ($aabaa$), after which we can't really remove anything else, in this particular case we would have to remove suffix $bbaa$, but there is no such suffix in word from $L\_1$

So, all in all - quotient, to my understanding is $L\_1$, with only difference that there is very last b always removed. And it feels to me like CF, what am I doing wrong?

Edit: According to comment, I have mistake in my thoughts, which is reasonable, we dont have to Kleenize $n$ in each substring.

Ie $aaaabbaab$ for $L\_1$ is possible. Ok, now lets look exactly at $aaaabbaab$ - first remove trailing $b$, get $aaaabbaa$. Now $bbaa$ - resulting in $aaaa$.. So all in all, quotient is still $L\_1$, which has some arbitrary suffix removed. Still feels CF to me

# Answer
Work backwards, from right to left. Try to find which strings of the form $a^\*$ belong to $L\_1/L\_2$. So find matches of strings $w\_1\in L\_1$ and $w\_2\in L\_2$ such that at the start only a string of the form $a^\*$ sticks out: $w\_1= a^k w\_2$.
> 1 votes

---
Tags: context-free
---


title: Why does 3 % 5 give 3 in C ? % >(mod )

text:
# Question
Title: Why does 3 % 5 give 3 in C ? % >(mod )
I know what mod does it gives you the remainder but why is it that (smaller integer) % (bigger integer) = smaller integer e.g ( 3%5 = 3 ) or
( 4%5= 4 ) why does this happen i cant figure it out

# Answer
> 5 votes
Notice that with the mod operator ($\\%$), you're using *integer* division, much as you are when you use the division operator ($/$) with two `int`s (at least in most (all?) C style languages). So $3/5$ gives the result of $0$, $7/5$ gives $1$. It's essentially the old kindergarten division - "how many times does five go into three".

Now $\\%$ then provides the other half of integer division; five goes into three *zero* times with *three* left over, i.e. the remainder of $3/5$ is $3$.

So between $/$ and $\\%$, we can get the two results from integer division that solve the following equation: $$x\times5 + y = 3$$

$/$ gives $x$ and $\\%$ gives $y$.

# Answer
> 2 votes
Hint: By definition.

$$a\mod n \equiv a, $$ when $0 \leq a \<\leq n$.

The congruence $b \equiv a\mod n$ actually means that exists a $k,b\in \mathbb{N}$ such that $n\*k = b - a$. Then, for the statement above, we have $a - a = 0 = 0\*n$, with $b=a$, and $k = 0$.

---
Tags: discrete-mathematics, number-theory
---


# Question
Title: Every connected graph on more than 3 vertices has two vertices whose removal doesn't disconnect it
> Prove that every undirected connected graph with $|V| \> 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected. Describe an efficient algorithm to find two such vertices.

How would I go about solving this?

# Answer
> 5 votes
> Prove that every undirected connected graph with |V | \> 2 has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected.

If your graph is connected, then you always have a Spanning Tree, now you can reduce the problem to proving that Every Finite Non-Trivial Tree has at Least 2 Leaf Nodes.

> Describe an efficient algorithm to find two such vertices.

A very obvious way would be just to find 2 leaf nodes of your Spanning Tree.

---
Tags: graphs
---


# Question
Title: On complexity of the sieve, start crossing at the square of p - Part II
Ok, this is a follow up question to this, about the Erathostenes Sieve.

If we look at this paper (page 3, footnotes), the author says:

> If we start crossing off at $p^2$ rather than $p$, the number of composites we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor

The total cost counting crossings is:

$$\sum\_{p\leq n}\bigl(\frac{n}{p}-p+1\bigr)=n\sum\_{p\leq n}\frac{1}{p}-\sum\_{p\leq n}p+\sum\_{p\leq n}1$$

The first sum would give us the known $O(n\log\log n)$. But I don't see the second sum to be an "irrelevant $O(n/\log n)$", so how is that?

According to this post in math overflow an upper bound for the sum of the primes up to $n$ is: $$\frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$

# Answer
The sum only goes up to $\sqrt{n}$. You can see that in the big display at the bottom of page 3, where only the first $\pi(\sqrt{n})$ primes are considered. Substituting $\sqrt{n}$ for $n$ in your formula, we get $n/\log n + O(n/\log^2 n)$.
> 3 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$
How many matrices satisfy the following constraints?

1. $n$ rows
2. $n$ columns
3. Cell values are either $0$ or $1$
4. Sum of any row is at most $m$
5. sum of any column is at most $m$

Is there a formula or an efficient algorithm to solve this problem?

# Answer
> 4 votes
Given $1 \leq m \leq n$, we want to determine the **cardinality** of the following set

$$\\{ \mathrm X \in \\{0,1\\}^{n \times n} \mid \mathrm X 1\_n \leq m 1\_n \\,\land\\, \mathrm 1\_n^{\top} \mathrm X \leq m \mathrm 1\_n^{\top} \\}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain

$$\bigg\\{ \tilde{\mathrm x} \in \\{0,1\\}^{n^2} : \begin{bmatrix} 1\_n^{\top} \otimes \mathrm I\_n\\ \mathrm I\_n \otimes \mathrm 1\_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1\_n\\ \mathrm 1\_n\end{bmatrix} \bigg\\}$$

or,

$$\bigg\\{ \tilde{\mathrm x} \in \[0,1\]^{n^2} : \begin{bmatrix} 1\_n^{\top} \otimes \mathrm I\_n\\ \mathrm I\_n \otimes \mathrm 1\_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1\_n\\ \mathrm 1\_n\end{bmatrix} \bigg\\} \cap \mathbb Z^{n^2}$$

Thus, we want to count the number of integer points inside a convex polytope, or, in other words, to count the number of solutions a given integer program (IP) has. Take a look at De Loera's survey \[0\] and the references therein.

---

\[0\] Jesús De Loera, The Many Aspects of Counting Lattice Points in Polytopes, 2005.

---
Tags: algorithms, combinatorics, matrices
---


title: $\mathsf{PP=RP}$ consequences

text:
# Question
Title: $\mathsf{PP=RP}$ consequences
We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level.

What are the other non-trivial collapses and consequences?

# Answer
> 7 votes
$\newcommand{\co}{\mathsf{co}\text{-}}$ $\newcommand{\class}\[1\]{\mathsf{#1}}$

If $\class{PP}=\class{RP}$ then you have a collapse to the first level, namely $\class{PH}=\class{NP}$.

Assume $\class{PP}=\class{RP}$, since $\class{PP}$ is closed under complement we have $\mathsf{RP}=\co{\class{RP}}=\class{ZPP}$, thus $\class{PP}=\class{ZPP}$.

Using Toda's theorem:

$\class{PH}\subseteq\class{P^{\class{PP}}}=\class{P}^{\class{ZPP}}=\class{ZPP}\subseteq{\class{NP}}$.

You actually get something stronger, if $\class{PP}=\class{RP}$, then the hierarchy collapses to $\class{ZPP}$.

In fact, you could show that the counting hierarchy collapses to $\class{ZPP}$, using simpler arguments than Toda's theorem, and acheive $\class{PH}\subseteq\class{CH}\subseteq\class{ZPP}$.

A tempting argument would be to say that since $\class{PP}=\class{ZPP}$, and $\class{ZPP}$ is low for itself, i.e. $\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ then $\class{PP}^{\class{PP}}=\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ and $\class{CH}$ collapses to $\class{ZPP}$. This is obviously false, since $\class{A}=\class{B}$ where $\class{A},\class{B}$ are sets of languages "decidable" by specific types of Turing machines (types $\class{A}$ and $\class{B}$), does not imply $\class{A}^{\mathcal{O}}=\class{B}^{\mathcal{O}}$ for any oracle $\mathcal{O}$. See this answer for further explanation.

What you actually need to show, in order to obtain $\class{CH}\subseteq{ZPP}$ (of course, under the original assumption of $\class{PP}=\class{RP})$, is that $\class{ZPP}$ is low for $\class{PP}$, i.e. $\class{PP}^{\class{ZPP}}=\class{PP}$. If this holds, then $\class{PP}^{\class{PP}}=\class{PP}^{\class{ZPP}}=\class{PP}=\class{ZPP}$, and thus $\class{CH}\subseteq\class{ZPP}$. Fortunately, this is not too difficult (and can even be strengthened to $\class{BPP}$ is low for $\class{PP}$).

Let $L$ be a language in $\class{PP}^{\class{ZPP}}$, then there exists a probabilistic polynomial time Turing machine with access to a $\class{ZPP}$ oracle $\mathcal{O}$, call it $M\_{\mathcal{O}}$, such that:

$x\in L\Rightarrow \Pr\left\[M\_{\mathcal{O}} \text{ accepts x}\right\]\>\frac{1}{2}$, and

$x\notin L\Rightarrow \Pr\left\[M\_{\mathcal{O}} \text{ accepts x}\right\]\le\frac{1}{2}-\frac{1}{2^{n^c}}$.

Where $n^c$ is the running time of $M\_{\mathcal{O}}$ (in the standard definition, the second inequality appears with $\le\frac{1}{2}$, however it can be improved to $\<\frac{1}{2}$ and thus to the above).

Suppose that the Turing machine which decides $\mathcal{O}$ has expected runtime $n^d$. Now, let us look at the machine $M$, which replaces each oracle call of $M\_{\mathcal{O}}$ by a $t$ steps simulation of the $\class{ZPP}$ machine for $\mathcal{O}$, and repeats this simulation $k$ times. If we come upon an oracle call, for which this process did not result in an answer (none of the $k$ $t$-steps simulations halted), then $M$ rejects.

Let $H$ denote the event that all of the simulations halted in the given time, then:

$\Pr\left\[\text{M accepts x}\right\]=\Pr\left\[\text{M accepts x} | H\right\]\Pr\[H\]+\Pr\left\[\text{M accepts x}\Big| \overline{H}\right\]\Pr\left\[\overline{H}\right\]=\Pr\left\[\text{M accepts x} | H\right\]\Pr\[H\]=\Pr\left\[M\_{\mathcal{O}} \text{ accepts x}\right\]\Pr\[H\]$.

Thus, we have:

$x\in L\Rightarrow \Pr\left\[\text{M accepts x}\right\]\>\frac{1}{2}\Pr\[H\]$, and

$x\notin L\Rightarrow \Pr\left\[\text{M accepts x}\right\]\le\left(\frac{1}{2}-\frac{1}{2^{n^c}}\right)\Pr\[H\]\le \frac{1}{2}-\frac{1}{2^{n^c}}$.

By Markov's inequality, a single simulation does not halt with probability $\le \frac{n^d}{t}$, so $k$ $t$-steps simulations do not output an answer with probability $\le \left(\frac{n^{d}}{t}\right)^k$. By the union bound we have $\Pr\[H\]\ge 1-n^c\left(\frac{n^{d}}{t}\right)^k\ge 1-\frac{1}{2^{n^c}}$, for $t=2n^d$ and $k=2n^c$. In this case $M$ acheives the following separation:

$x\in L\Rightarrow \Pr\left\[\text{M accepts x}\right\]\>\frac{1}{2}\left(1-2^{-n^c}\right)$, and

$x\notin L\Rightarrow \Pr\left\[\text{M accepts x}\right\]\le \frac{1}{2}-2^{-n^c}\<\frac{1}{2}-\frac{1}{2}2^{-n^c}$

Which proves $L\in \class{PP}$, since we can replace the constant $\frac{1}{2}$ with any function $f(x)\in \class{FP}$. See this question for a proof to why we can replace $\frac{1}{2}$ with any rational constant, and convince yourself that it generalizes immediately to any $f\in \class{FP}$.

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


title: is $P_{CTC} = BPP_{path}$?

text:
# Question
Title: is $P_{CTC} = BPP_{path}$?
I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic.

This is my reasoning, and I would like to know if (1) this is already known or (2) I misunderstood something or (3) I just found out something useful:

$P\_{CTC}$ is the class of problems that can be solved by putting polynomial amounts of data in a time machine.

$BPP\_{path}$ is the class of problems that can be solved by postselecting in a probabilistic Turing machine, i.e. ignoring cases you do not care about.

$P\_{CTC}\subseteq BPP\_{path}$ because you can simulate a closed time-like curve with postselection like this: Scan the entire program in the beginning, both state and memory. Then, after processing, do so again and postselect so that you only return if the state & memory now are exactly equal to the start state & memory (except for a single bit that says whether or not this is the first iteration, to prevent an infinite loop).

$BPP\_{path}\subseteq P\_{CTC}$ because you can simulate postselection like this: If the message from the future starts with $1$, send the message $0$ into the past. Otherwise proceed as normal. When you get to the step where you would normally post-select, send a 1 into the past iff. you want to ignore this timeline, else a $0$. The only consistent version is now the one where you both receive and send a 0 because you were satisfied with the results.

# Answer
> 0 votes
I believe I have found the answer: The proof is wrong. BPP\_PATH is not in P\_CTC because P\_CTC is required to give a single definite answer, while BPP\_PATH is a probabilistic algorithm, so the second reduction does not work. For it to work, one would have to use the time-travel information to count the number of successes of the probabilistic algorithm vs the number of its failures. I have no idea how to do this, or if it even can be done (probably not).

---
Tags: complexity-theory, complexity-classes, quantum-computing
---


# Question
Title: Bottom-Up Parser With Leftmost Derivation
I'm reading the book *Parsing Techniques* by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization:

> \[...\] a parser can produce a list of rule numbers instead, which means that it *linearizes* the parse tree. There are three main ways to linearize a tree, prefix, postfix and infix.

Those are explained using the following grammar:

and this particular production tree (the grammar is spuriously ambiguous):

(The numbers at the nodes are semantic attributes.)

Prefix notation is explained first:

> In *prefix notation*, each node is listed by listing its number followed by prefix listings of the subnodes in left-to-right order; this gives us the leftmost derivation \[...\]:
>
> leftmost: 2 2 1 3c 1 3e 1 3a

Postfix notation follows:

> In *postfix notation*, each node is listed by listing in postfix notation all the subnodes in left-to-right order, followed by the number of the rule in the node itself; this gives us the rightmost derivation \[...\]:
>
> rightmost: 3c 1 3e 1 2 3a 1 2

---

Before the linearizations, there is a "leftmost" and "rightmost," respectively. Does that mean prefix notation only works with top-down and postfix notation with bottom-up parsing? But then why? If we start from the rightmost non-terminal and build the parsing tree from the top down, wouldn't the linearization with the "leftmost" in front be the result? Aren't the notations semantically independent?

Furthermore, I've read about LL and LR parsers, which yield a leftmost or rightmost derivation and use a top-down or bottom-up algorithm, respectively. Does that mean a bottom-up parser can only work with a rightmost derivation? Why not with a leftmost one? I don't see the problem with that, similarly to how prefix notation seems to imply a leftmost derivation.

# Answer
> 2 votes
"Linearizing" here is equivalent to superimposing a total ordering on what is a partial order. If your grammar is context-free, this partial order can always be conveniently represented by a tree. Other types of grammars will be able to produce derivations orders that are not tree-like, and that is why we generally avoid them.

This total order is meant to allow for sequential algorithms to be written, *because the input will be read sequentially*. That's all, no magic here.

What happens is that different criteria for linearization will serve different algorithms: if you are going to *reduce* the input, you will go "from the bottom up", metaphorically, so the linear order that suits you (if you are reading the input left-to-right - because your language has an indo-european flavor), is postfix. If not, prefix.

---
Tags: formal-grammars, parsers
---


# Question
Title: Find proportion of 'important' edge among all edges in a graph
I met this problem when dealing with a social network problem. It is a subproblem of that. The problem is like that:

We look at a graph $G(V,E)$, where $V$ is the set of vertices and $E$ set of edges. We define $x \in V$ as an 'important' vertex if at least $\frac 1 3 deg(x)$ ($deg(x)$ refers to the degree of $x$)of the vertices in $x$'s neighborhood have degree no more than degree of $x$. We then define 'important ' edge as the edge when either one of the two vertices of the edge or both are 'important' vertices. We define the set of 'important' edge as $E\_1$.

We want to show $|E\_1| \geq \frac 1 2 |E|$. I cannot really think out any method. Could anyone provide some suggestions?

Many thanks.

# Answer
> 4 votes
The problem you asked can be actually generalized to an arbitrary total order $\mathcal{O}$ on the vertices: a vertex $x$ is important iff at least $\frac{1}{3}$ of its neighbors are smaller than $x$ according to $\mathcal{O}$. For the order on degrees we can break the ties arbitrarily, which will only make important vertices and thus important edges less.

We prove it by the adjacency matrix $M$. Suppose the vertices are ordered: $x\_1\<\_\mathcal{O}\cdots\<\_\mathcal{O}x\_n$, where $n=|V|$. Then $M\in\\{0,1\\}^{n\times n}$ with $M\_{i,j}=1$ iff $(x\_i,x\_j)\in E$. In the rest part of the proof we abuse the notation of $M\_{i,j}$ to represent the grid in the matrix $M$, and for a set of grids $S$ we use $|S|$ to denote the number of $1$'s among these grids.

The matrix $M$ is naturally divided into two triangles: $$L=\\{M\_{i,j}\mid i\>j\\},\quad U=\\{M\_{i,j}\mid i\<j\\}.$$ Denote the $i$-th row by $R\_i$, so $|R\_i|=\deg(x\_i)$. Now $x\_i$ is important iff $|L\cap R\_i|\geq \frac{1}{2}|U\cap R\_i|$. On the other hand, since $|L|=|U|=|E|$ which means $\sum\_i |L\cap R\_i|=\sum\_i |U\cap R\_i|=|E|$, we know $$\begin{align\*} |E\_1|&\geq\sum\_i\left\\{\\,|L\cap R\_i|\\;\middle|\\; |L\cap R\_i|\geq \textstyle\frac{1}{2}|U\cap R\_i|\\,\right\\}\\ &=|E|-\sum\_i\left\\{\\,|L\cap R\_i|\\;\middle|\\; |L\cap R\_i|\<\textstyle\frac{1}{2}|U\cap R\_i|\\,\right\\}\\ &\>|E|-\frac{1}{2}\sum\_{i=1}^n|U\cap R\_i|=\frac{1}{2}|E|. \end{align\*}$$

---
Tags: algorithms, graphs
---


title: What is "extended polynomials"

text:
# Question
Title: What is "extended polynomials"
I've heard that the functions that are definable in simply-typed $\lambda$-calculus is the class of extended polynomials.

However, it is still not clear to me what exactly is extended polynomials. Could someone explain that to me? Some pointers would be good as well.

Thanks.

# Answer
It turns out the definition is straightforward as seen in \[1\]. And as an example, exponentiation is not definable in simply-type $\lambda$-calculus.

> The class of extended polynomials is the smallest class of func- tions over N which contains:
>
> 1. the constant functions: 0 and 1,
> 2. projections,
> 3. addition,
> 4. multiplication,
> 5. the function ifzero(n, m, p) = if n = 0 then m else p

---

1. Definable functions in the simply typed lambda-calculus by M. Zakrzewski (2007)
> 5 votes

---
Tags: lambda-calculus
---


# Question
Title: Can you solve 3D Tic Tac Toe with Minimax?
I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable.

The only thing is that the board looks like this:

```
_ _ _
 _ _
_ _ _

```

rather than this:

```
_ _ _
_ _ _
_ _ _

```

There are a total of 3 boards stacked on top of each other, and any lines of 3 x's or o's grant a point. When the board is full, all points are tallied and the winner is announced.

I used the minimax algorithm with alpha-beta pruning.

But my algorithm is only able to get the optimal move if the board is full to a certain degree. When there are less moves, it takes a really, really long time to find the optimal move.

Is there some way to speed up my minimax? I have already researched ways to speed up minimax, but I need an answer specifically related to my situation.

Is it possible to solve to optimal move quickly using minimax? Or do I have to use a different algorithm?

EDIT: Please note that the game uses gravity, like in the connect-four game. I.e. the x's and y's stack.

# Answer
You could precompute the optimal move for all possible configurations, and store that in a lookup table. Once that's done (and it only needs to be done once), it would make your program extremely fast at runtime.

Your board has a total of 24 cells (8 cells at each level, times 3 levels), so there are at most a total of $3^{24}$ possible calculations. Therefore, as a naive upper bound, your table will need to have at most $3^{24}$ entries.

In fact, due to gravity plus the fact that you don't need to store configurations where one player has already won, there will be many fewer configurations that you need to store in your table. Call a configuration *relevant* if no one has won yet, and it is a reachable configuration (i.e., it doesn't violate the gravity rules). Then your table can be stored as a dictionary/map: for each relevant configuration, it stores the optimal move when in that configuration and which player will win assuming optimal play (first-player win, second-player win, tie). Now your job is to precompute that dictionary, with one element per relevant configuration.

It is possible to show that the number of relevant configurations is at most $13^8 \approx 2^{29.6}$: in particular, the number of configurations that satisfies gravity and has no vertical win is $13^8$. This is only an upper bound; the true number of relevant configurations is even smaller still, as this estimate doesn't take into account that there's no need to store any configuration containing a horizontal or diagonal win.

To speed up the precomputation, you can avoid repeating effort (i.e., use "dynamic programming"). For instance, one approach would be to start by enumerating all relevant configurations containing 23 full cells and compute the optimal move for each; then enumerate all relevant configurations containing 22 full cells and compute the optimal move for each; and so on. At each stage, when you compute the optimal move, you add it to the table along with who ultimately wins. Notice that this makes it very easy to compute the optimal move at each stage, since you only need to search at depth 1 and then you can immediately look up what will happen thereafter in the table.

The running time of the precomputation will be some small constant times $N$, where $N$ is the number of relevant configurations. We know that $N$ is smaller than $2^{29.6}$, and probably substantially smaller. Therefore, I expect this precomputation to be something you could run within a few days on a modern PC, and store on the filesystem in a reasonable amount of space.

As a further optimization, you can use symmetry to further reduce the number of configurations you need to compute or store. In particular, given any configuration, you can find a bunch of other equivalent configurations through symmetry (flip horizontally, flip vertically, rotate). For each set of equivalent configurations, you only need to consider and store one. In particular, given a configuration, the first thing you'd do is map it to a canonical equivalent configuration (so that all equivalent configurations map to the same canonical); then you only need to compute or store canonical configurations in the lookup table. I suspect this will reduce $N$ by a factor of 8 or so.
> 1 votes

---
Tags: optimization, artificial-intelligence, program-optimization
---


# Question
Title: Question regarding coin change algorithm (DP and greedy)
The question goes something like this:

Suppose you are living in a country where coins have values that are powers of p, V = \[1, 3, 9, 27\]. How do you think the dynamic programming and greedy approaches would compare?

Intuitively I want to answer that DP will be faster because greedy runs the same number of comparisons regardless of the relationship between the elements in V. But DP is a recursive call on previous elements, so the fact that there is always a ratio of p between each denomination of V would suggest that DP will end up making less recursive calls. Can anyone confirm my answer or tell me why I'm wrong?

# Answer
> 0 votes
In terms of running time, the greedy algorithm is still going to be faster than the DP algorithm. DP will always produce the optimal solution regardless of values in V. Greedy, on the other hand, takes advantage of extra structure present in some value choices that allow it to effectively ignore possible ways of getting to the goal value. A coin system where the values are powers of p would allow the greedy algorithm to also consistently produce the optimal solution.

---
Tags: algorithm-analysis, dynamic-programming, greedy-algorithms
---


title: Is every NP-hard problem computable?

text:
# Question
Title: Is every NP-hard problem computable?
Is it required that a NP-hard problem must be computable?

I don't think so, but I am not sure.

# Answer
> 16 votes
No, an $NP$-hard problem need not be computable. The definition is fairly complete: a problem $L$ is $NP$-hard if that problem having a poly-time solution implies every problem in $NP$ has a poly-time solution (that is, a reduction to $L$ exists for every problem in $NP$.).

Uncomputable problems are then vacuously hard: suppose we could solve one in polynomial time. Then we use the proof that it's uncomputable to derive that it's both computable and uncomputable, a contradiction. From this falsehood, we can derive anything, namely that there is a polynomial time algorithm for whatever $NP$ problem we are looking at.

For example, consider the halting problem $H$. We can reduce any $NP$ language $A$ to $H$ as follows, assuming we have a polytime checker $f(s,c)$ which checks if $c$ is a certificate for $s\in A$:

* Given input $s$
* Construct (but don't run) Turing Machine $M$ which takes input $x$ tries every certificate $c$ and halts if $c$ is a certificate verifying that $s\in A$.
* Return $H(M,x)$ (that is, return true iff $M$ halts on input $x$)

Thus, with a single call to a poly-time algorithm solving the Halting Problem, we can solve any $NP$ problem in polynomial time.

Such a reduction is not useful, because all it does is tells if "if false then something". We already know that there's no polytime algorithm for uncomputable problems.

# Answer
> 18 votes
There appears to be some considerable confusion in this community regarding this question. I'll give a detailed answer in the hope of clearing up the water and illuminating the relationship between computability and NP-hardness.

First, I believe that being clear and explicit about the various definitions involved will resolve a lot of the confusion.

> A **string** is a finite sequence of characters from some fixed finite alphabet.
>
> A **decision problem** is a set of strings. (This set is typically infinite.) Think of the decision problem as testing strings for some property: the strings with the property are in the set, and the strings without the property are not.
>
> Assume we have two decision problems, $A$ and $B$. Say $A$ is **polynomial-time reducible** to $B$ if there is some polynomial $p(x)$ and algorithm some algorithm $M$ such that, for all strings $s$,
>
> * If you provide $M$ with input $s$, $M$ halts in fewer than $p(|s|)$ steps (where $|s|$ is the length of the string $s$) and outputs a string $M(s)$.
> * $s$ is in $A$ if and only if $M(s)$ is in $B$.
>
> A decision problem $B$ is **NP-hard** if, for every NP decision problem $A$, $A$ is polynomial-time reducible to $B$.
>
> A decision problem is **computable** if there is an algorithm $M$, that, for all strings $s$,
>
> * If you provide $M$ with input $s$, $M$ halts and outputs either "yes" or "no".
> * The output is "yes" if $s$ is in $A$ and "no" otherwise.

With the above definitions, we can immediately clarify what I think might be the root confusion in your question: nothing in the definitions of decision problem, reductions, or NP-hardness requires the decision problems to be computable. The definitions make perfect sense thinking of decisions problems as arbitrary sets of strings, and these sets can be very nasty indeed.

---

That leaves two questions on the table:

1. The definitions leave open the possibility that non-computable functions might be NP-hard. Are there *actually* non-computable, NP-hard functions?
2. There is an intuition that saying a problem is NP-hard is saying that it is hard to solve. Saying that it is non-computable is like saying it's "really hard" to solve. So, are *all* non-computable problems NP-hard?

---

Question 1 is easier to answer. There are two particularly important ways to find non-computable decision problems that are NP-hard. The first is the halting problem: the halting problem, $H$, has the property that every *computable* decision problem is polynomial-time reducible to $H$. Since NP problems are computable, every NP problem is polynomial-time reducible to $H$, so $H$ is NP-hard.

The other important way to build a non-computable, NP-hard problem is to observe that we can combine any known NP-hard problem with any known non-computable problem. Let $A$ be NP-hard and $B$ be non-computable. Form the decision problem $A \oplus B$ as follows: $A \oplus B$ contains those strings of the form "0, followed by a string in $A$" and those of the form "1, followed by a string in $B$". $A \oplus B$ is NP-hard because we can turn any reduction (of any problem) to $A$ into a reduction to $A \oplus B$: just tweak the algorithm to output an extra "0" at the front of its output string. $A \oplus B$ is non-computable, since computing $A \oplus B$ requires deciding which strings that start with "1" are in the set; this is impossible, since $B$ is non-computable.

---

Question 2 is considerably tricker, but in fact there are non-computable decision problems that are not NP-hard (assuming P $\neq$ NP). Yuval's fine answer constructs such a decision problem explicitly. (For any computability theorists in the room, any "Cohen $\Pi^0\_1$-generic" will do the trick, as well.) I'll break down why the intuition that "NP-hard problems are hard, non-computable problems are harder" is wrong.

NP-hardness and non-computability both say that a problem is "hard" in a very general sense, but they are *very* different and shouldn't be lumped together as the same kind of phenomenon. Specifically, NP-hardness is a "positive" property: **an NP-hard problem $A$ is hard in the sense that, given access to a cheat sheet for $A$, you *can* solve a hard class of problems**. On the other hand, non-computability is a "negative" property: **a non-computable problem $A$ hard in the sense that you *cannot* solve $A$ with a given class of resources**.

("Forcing," by the way, is the technique used to produce the "Cohen $\Pi^0\_1$ generic" that I mentioned. To be very very vague, forcing is a general way to produce things that are "generic" in that they have no positive properties and every negative property. That's why forcing can directly produce a problem that's neither computable nor NP-hard.)

# Answer
> 12 votes
Nope. NP-Hard means it is as hard, or harder, than the hardest NP-problems. Intuitively, being uncomputable will make it a lot more difficult than NP.

Wikipedia:

> There are decision problems that are NP-hard but not NP-complete, for example the halting problem.

Everyone knows that is not computable

# Answer
> 10 votes
For completeness, let us prove the following theorem:

> There exists an uncomputable language which is not NP-hard if and only if P$\neq$NP.

If P=NP then any non-trivial language (one which differs from $\emptyset,\\{0,1\\}^\*$) is NP-hard (exercise), and in particular any uncomputable language is NP-hard.

Now suppose that P$\neq$NP. Let $T\_i$ be some enumeration of all Turing machines. We will construct the required language $L$ in stages. At each stage we will keep a $\\{0,1,?\\}$ coloring of $\\{0,1\\}^\*$ which we also denote by $L$; here $0$ means that we have decided that the string is not in $L$, $1$ means that we have decided that the string is in $L$, and $?$ means that we haven't decided yet. All but finitely many strings will be colored $?$.

In step $2i$, we think of $T\_i$ as a machine which either accepts its input, rejects it, or never halts. If $T\_i$ doesn't always halt then we don't do anything. If $T\_i$ always halts then we find a string $x$ such that $L(x) = ?$, and set $L(x) := 0$ if $T\_i(x)$ accepts and $L(x) := 1$ if $T\_i(x)$ rejects.

In step $2i+1$, we think of $T\_i$ as a machine computing a (possibly) partial function on its input. If $T\_i$ isn't total, or if it is total but doesn't run in polynomial time, or if it is total but its range is finite, we don't do anything. If $T\_i$ is total, runs in polynomial time, and has infinite range, then we find a string $x$ such that $L(T\_i(x)) = ?$. If $x \in \mathrm{SAT}$ (that is, if $x$ encodes a satisfiable CNF) then we set $L(x) := 0$, and otherwise we set $L(x) := 1$.

After infinitely many steps, we get a $\\{0,1,?\\}$ coloring of $\\{0,1\\}^\*$ which we complete to an actual language in an arbitrary way.

The resulting language $L$ isn't computable: step $2i$ ensures that $T\_i$ doesn't compute it. It also isn't NP-hard, but here the reasoning is a bit more delicate. Suppose that $T\_i$ is a polytime reduction from SAT to $L$. If the range of $T\_i$ is finite then we can turn $T\_i$ into a polytime machine deciding SAT, by listing the truth table of $L$ on the range of $T\_i$. This is impossible by the assumption P$\neq$NP. Thus $T\_i$ has infinite range, but then step $2i+1$ rules out its being a reduction from SAT to $L$.

# Answer
> 4 votes
A language $L$ is NP-hard if for every $L' \in \mathrm{NP}$ we have that $L'$ is polynomial-time reducible to $L$. The acceptance problem for nondeterministic Turing machines

$$ A\_{\mathsf{NTM}} = \\{ \langle M,w \rangle \mid M \text{ is a nondeterministic Turing machine that accepts } w \\}$$

is undecidable and is NP-hard. For consider an $L' \in \mathrm{NP}$. $L'$ is decided by some nondeterministic Turing machine $M'$ with polynomial time complexity. A poly-time reduction $f$ from $L'$ to $A\_{\mathsf{NTM}}$ is given by

$$f(x) = \langle M,x \rangle$$

# Answer
> 4 votes
I think what causes people to think there is no uncomputable NP-hard problem is that they miss the point that NP-hardness is a lower bound on the hardness of a problem, not an upper bound on their hardness like P or NP.

A language L being NP-hard means that it is above language in NP and that is. Now if you understand this what need is to show that there are arbitrary harder problem.

Let $A$ be a language. Consider algorithms augmented with a black-box that they can use to deciding membership in $A$. Let's denote them by $\mathsf{C}^A$. It is easy to see that the halting problem for $\mathsf{C}^A$, $Halt\_{\mathsf{C}^A}$ is not in $\mathsf{C}^A$.

In computablity theory this is called *jump* of $A$ and is denoted by $A'$. So $A \< A'$ strictly. And nothing stops us from repeating this: $A\<A'\<A''\<A'''\<...$

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


# Question
Title: How can the Operating System run on the same chip it is supposed to be managing?
From my readings about Operating Systems (reading the basic material on Wikipedia, tech sites, etc) I've learned that the Operating System is a program that allows programs and applications to interact with the hardware in an efficient and safe way.

However I'm confused about how the Operating System oversees the computer's operation when it itself needs to be operated.

What do I mean? Well, the way I would imagine an Operating System to work, is that on a computer, there would be two CPUs. One that runs the OS all the time, and another that the OS uses to run the computer. However, it turns out that the OS is running on the same CPU that the other processes are. This is like a manager having to work on the same production line as his employees, and only gets to use the power tools when another employee is done with them. He would not be a very effective manager, since he wouldn't have the ability to issue orders if his employee is even slightly undisciplined.

**So how can it be that the OS only runs part of the time on the same CPU that has to be shared between all the other processes? How does this end up working out?**

# Answer
Modern CPUs are aware of the OS up to a certain degree. They provide some "power tools" for the first one who claims them. Usually this is the boot loader, which then hands over control to the OS. One usually speaks of "kernel mode" vs "user mode" or "ring 0" vs "ring 3" to distinguish between the one process with the extra privileges and the rest.

These "power tools" are certain privileges for resource management: Control the memory, access to the hardware and how long user level code may be executed without interruption.

The CPU executes the OS with its special privileges when one of the following events occurs:

1. A user mode process explicitly hands over the control to the kernel mode process. This is called a syscall.
2. The kernel mode process can use its special privileges to register for certain events (e.g. external hardware sends a special signal to the CPU or a user space process tries to access a reserved resource). When such an even occurs, the CPU stops the user mode process immediately and hands over the control the the kernel mode process. Usually one speaks from an interrupt.

So the OS can run on the same chip because the chip is built for this. It can reserve special privileges for itself. The CPU may interrupt all other pieces of code without these special privileges anytime and hand over the control to the OS.

Some chips with very limited support (e.g. a microcontroller) don't have this support for special privileged code. These chips usually run without an OS. There is only one big program running, that can access the hardware directly, must respond to the hardware interrupts and can access any resources anytime. If that program makes one mistake, usually the whole thing crashes.
> 16 votes

# Answer
In their most primitive form, operating systems rely on processes being well-behaved and handing control back to the operating system from time-to-time. If a process is not well-behaved, then indeed it can happen that the operating system freezes.

Most CPU's however, have *interrupts*: an interrupt pauses the current process (preemption) and hands control back to the operating system. You can schedule interrupts to happen at specific intervals, or be triggered externally (for instance pushing the reset button).

Basically, the CPU switches back and forth between running the OS and running processes at a blazingly fast speed. Furthermore, CPU's have "user mode" and "kernel mode". Processes run in user mode and the OS runs in kernel mode. Running in user mode prevents a process from executing restricted commands (such as IO). If a process wants to write to the disk, it has to ask the OS to do so. The OS switches to kernel mode and does the write on behalf of the process (after making sure the process has the required permissions).
> 17 votes

# Answer
You don't need two different processor for microprocessor to run userspace and kernel space code. Basically it works in this way when you turn your computer on your Bios loads Bootloader( 512kb code on disk which ends 55aa bootloader signature) to ram and thru this bootloader your kernel get loaded to ram and runs forever till you shut your computer down. And your kernel manages memory and doesn't allow your kernel code which sits on ram won't get overwritten by user space code. For this purpose there are system calls which userspace code invoked by using these system calls and add your userspace code to ram and start to execute it. In operating systems this concept is researched as a Memory Management. Here is the link you can read it is very good for starting https://www.cs.bham.ac.uk/~exr/lectures/opsys/10\_11/lectures/os-dev.pdf
> 1 votes

# Answer
To build on other answers, it is easier to understand if you think that the kernel itself is not a process but a management code. Any user process can shift from user mode to kernel mode and execute kernel code(priviledged instructions) by using some part of the kernel space. Then the process can go back to user mode and run in the user space again.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: Reading CLRS analysis of hashing with chaining
I'm currently reading an analysis hashing with chaining, and it goes over two examples:

> In the first, the search is unsuccessful; no element in the table has key k. In the second, the search successfully finds an element with key k.

(This is all under the assumption of simple uniform hashing). I understood the analysis for the first case, but the second confuses me. The book goes:

> The situation for a successful search is slightly different, since each list is not equally likely to be searched. Instead, the probability that a list is searched is proportional to the number of elements it contains.

The above sentences are what confuses me. Why is each list not equally likely to be searched if both operate under assumption of simple uniform hashing? And why in the world would the number of elements a list contains have any effect at all on the probability that the list is searched? I would think it's the opposite...the number of elements searched in a list depends on the probability that a key is hashed to a particular index (where the list is).

# Answer
> 2 votes
I assume that you are talking about the hash-table that uses an adjacency list for the elements that have the same hash key (hash table using chaining). Let's look at a very simple example.

We have a hash table such as the following:

```
key : like list of elements
1   : x_11 -> x_12 -> ... -> x_11000000 -> NULL  // 1000000 elements
2   : NULL                                       // 0 element
3   : x31 -> NULL                                // 1 element

```

If you look at keys 1 and 3, which one is more likely to be visited? The answer is 1, because it has more elements than all other lists. Therefore, we are more likely to find the mysterious element in 1's linked list.

---
Tags: probability-theory, hash, hash-tables, hashing
---