# Question
Title: Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?
I was given a question and don't really know to solve it.

> Given a regular language $L$, is the following language also regular? $$L\_1 = \\{ w \mid \text{each prefix of } w \text{ of odd length is in $L$} \\}.$$

I think that $L\_1$ should be regular, but I don't have a clue how to prove it.

Thank you for any input.

# Answer
> 2 votes
Try constructing an NFA for $\hat L:=\\{w|$ there is an odd length prefix of $w$ that is $\notin L\\}$, given a DFA for $\overline L$, and then show $L\_1=\overline {\hat L} $.

If I'm not mistaken, this should work out.

# Answer
> 0 votes
There is a more economical solution for DFAs.

Suppose that $\langle Q,\Sigma,q\_0,\delta,F \rangle$ is a DFA for $L$. We construct a DFA $\langle Q', \Sigma', q'\_0, \delta',F' \rangle$ for $L\_1$ as follows:

* $Q' = Q \times \\{0,1\\} \cup \\{ q\_{\mathit{sink}} \\}$.
* $q'\_0 = \langle q\_0, 0 \rangle$.
* If $\delta(q,\sigma) \in F$ then $\delta'(\langle q,0 \rangle, \sigma) = \langle \delta(q,\sigma),1 \rangle$.
* If $\delta(q,\sigma) \notin F$ then $\delta'(\langle q,0 \rangle, \sigma) = q\_{\mathit{sink}}$.
* $\delta'(\langle q,1 \rangle, \sigma) = \langle \delta(q,\sigma), 0 \rangle$.
* $\delta'(q\_{\mathit{sink}}, \sigma) = q\_{\mathit{sink}}$.
* $F' = Q \times \\{0,1\\}$.

What's going on here? The states $Q \times \\{0,1\\}$ keep track of both the state of the original automaton, and the parity of the current number of letters read. We are in one of these states as long as the condition "every odd-length prefix is in $L$" holds. If it stops holding, we move to a sink state.

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


# Question
Title: Efficient way to reduce a binomial coefficient as a fraction
Here is the full problem.

> *You need to calculate Euler's totient function of a binomial coefficient $C\_n^k$*.
>
> **Input**
>
> *The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$*.
>
> **Output**
>
> *Print one number $\varphi (C\_n^k)$ modulo $10^9+7$*.

**My thoughts:**

It is known that $$\varphi(a)=a \prod\_{p|a}(1-\frac{1}{p}) $$ where $p$ are prime numbers divide $a$.

Hence, if we can obtain somehow `vector<int> multipliers` that contains divisors of $C\_n^k$ then we can easily do the following steps in order to calculate $\varphi(C\_n^k)$:

1. Multiply all elements of that vector modulo $10^9+7$. Let's call the result by `result`
2. Then we can iterate through all prime numbers that divide any element of `multipliers`(these prime numbers can be obtained by a minor modification of sieve of Eratosthenes). Since $1-\frac{1}{p}=\frac{p-1}{p}$ we can update the `result` by:

```
result = divideMod(multiplyMod(result, p-1), p)

```

where `divideMod` and `multiplyMod` are functions doing corresponding operations modulo $10^9+7$.

And yes, we can do modulus division since $10^9+7$ is prime.

By doing all that stuff we get what we needed: $\varphi(C\_n^k)$ modulo $10^9+7$. This all idea now requires just a vector `multipliers`. Here is my attempt to get it:

I need to write a function calculates the combinations number $C\_n^k$. The function shouldn't return the total result of the operation(because it can be too large since $(0 \le k \le n \le 500000)$). It should return the `vector<int>` which contains divisors of that number. Let's do some math:

$$ C\_n^k = \frac{n!}{(n-k)! k!} \\ =\frac{n(n-1)(n-2)...(n-k+1)}{k(k-1)(k-2)...1} $$

So now I need to reduce this fraction. And the question is: what is the most efficient way to do this(in terms of time)?

I've tried the following. Consider the numerator and denominator are represented by `vector<int> numerator={n, n-1, ..., n-k+1}` and `vector<int> denominator={k, k-1, ..., 1}` respectively.

```
    vector<long> numerator(k);
    vector<long> denominator(k);
    for (int i = 0; i<k; i++) {
        numerator[i] = n-i;
        denominator[i] = k-i;
    }

    vector<long> multipliers;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (numerator[i] == 1)
                break;

            long greatest_common_divisor = gcd(numerator[i], denominator[j]);
            numerator[i] /= greatest_common_divisor;
            denominator[j] /= greatest_common_divisor;
        }
        if (numerator[i] != 1)
            multipliers.push_back(numerator[i]);
    }

```

As you can see I just go through all numbers in numerator and denominator and divide them by their greatest common divisor.

Time complexity of this algorithm is $O( k^2 log(nk) )$

It's too big and for this solution contest system returns time limit exceeded.($0 \le k \le n \le 500000$)

Does there exist more efficient way?

# Answer
> 2 votes
The formula $\varphi(a)=a \prod\_{p|a}(1-\frac{1}{p})$ tells us to approach the problem by the prime factors.

Here is another useful formula.

**Legendre's formula.** For any prime number $p$ and any positive integer $n$, let $\nu \_{p}(n)$ be the exponent of the largest power of $p$ that divides $n!$, i.e, $p^{\nu\_{p}(n)}$ divides $n!$ but $p^{\nu \_{p}(n)+1}$ does not divide $n!$. We have, $$\nu \_{p}(n)=\lfloor\frac np\rfloor + \lfloor\frac n{p^2}\rfloor + \lfloor\frac n{p^3}\rfloor + \cdots,$$ where the ellipsis means the addition go on until the term becomes 0. (For a proof, check that Wikipedia link.)

Applying Legendre's formula, we see that $n!=\prod\_{\text{prime } p\le n} p^{\nu\_p(n)}$ for all $n$. Since $C\_n^k = \frac{n!}{(n-k)! k!}$, we have $C\_n^k=\prod\_{\text{prime } p\le n}p^{\nu\_p(n)-\nu\_p(k)-\nu\_p(n-k)}$.

---

Here is the outline of the algorithm.

1. Find all primes numbers not larger than $n$.
2. Initialize $answer$ to 1. Iterate over all prime p not larger than $n$.
    1. Compute $e = \nu\_p(n)-\nu\_p(k)-\nu\_p(n-k)$.
    2. If $e\ge1$, replace $answer$ by $answer * p^{e-1} * (p-1) \pmod{10^9+7}$
3. return $answer$.

The complexity of the algorithm is $O(n\log n)$ time and $O(n)$ space.

---

Here is code in Java (which is almost valid c/c++ code as well). It takes less than a hundredth of a second to compute $C\_{500000}^{250000}$ on my computer.

```
final static int MOD = 1000000007;

static long totientOfBinomialCoefficient(final int n, final int k) {
    boolean[] isComposite = new boolean[n + 1];
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            for (int j = 2 * i; j <= n; j += i) {
                isComposite[j] = true;
            }
        }
    }

    long answer = 1;
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            int exp = exponentInFactorial(i, n) - exponentInFactorial(i, k) - exponentInFactorial(i, n - k);
            if (exp > 0) {
                answer = answer * powerMod(i, exp - 1) % MOD * (i - 1) % MOD;
            }
        }
    }

    return answer;
}

static int exponentInFactorial(int prime, int n) {
    int answer = 0;
    while (n >= prime) {
        n /= prime;
        answer += n;
    }
    return answer;
}

static long powerMod(int base, int exp) {
    long answer = 1;
    while (exp >= 1) {
        answer = answer * base % MOD;
        exp--;
    }

    return answer;
}

```

Some further micro-optimization can be done. However, they are not needed for this problem.

# Answer
> 2 votes
You store the numbers n-k+1 to n in an array.

Then for each prime number p ≤ k: Find which power of p is a factor of k! (Thats k/p + k/p^2 + k/p^3 ... ) Then remove that power from the array: Find the first number divisible by p (that would be the number at index 0 if n-k+1 is divisible by p, otherwise at index p - ((n-k+1) modulo p)). That number is divisible by p, possible by p^2 etc., and the next number divisible by p is at the index p higher).

You are now left with an array of k numbers that you need to multiply.

---
Tags: algorithms, time-complexity, number-theory, c++, factorial
---


# Question
Title: Find a list of actions that result in desired state
I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem.

In the system we have a list of actions that a user has previously taken. The possible actions are:

* User creates item of type A.
* User creates item of type B.
* User creates item of type C.

The date and time the action was taken is also recorded.

We have a function **passesRules** which takes the list of all actions the user has previously taken as input, and applies a set of rules and returns a boolean. The boolean is true if any of the rules are true, and false if none of the rules are true.

There are many possible rules, but in general they take the form of:

* Has user created 5 items of type A in the last 10 days?
* Has user created 2 items of type B in the last 3 days?
* Has user created more than 6 items of type C in last 5 days, AND created 3 items of type A in the last 10 days?

What I want to do is to create a function **predictActions** which predicts the actions the user must take so that **passesRules** returns true.

Obviously with the rules described above there are multiple different sets of actions that could make **passesRules** return true. I would like **predictActions** to return an array where each element in the array is a list of actions the user could take to make **passesRules** return true.

**predictActions** should take the following parameters:

* The list of actions the user has previously taken.
* The list of rules.
* The current date.

---

I'm not asking for a solution, but I don't know what area of computer science to investigate further to model and solve this problem. Something from graph theory, or some type of constraint solver?

Thanks!

# Answer
It depends on what the rules are. For your particular rules, this can be handled very simply by counting the number of events of each type seen in the given time window; then predictActions can easily compute the additional number of each type of action needed.
> 0 votes

---
Tags: algorithms, graphs, sat-solvers
---


# Question
Title: Difference between assignment, binding, and substitution?
I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration, and citations from computer science wiki/articles/textbooks are welcome.

# Answer
> 5 votes
All three notions are related to variables. You can think of variables as named placeholders for *some* expression.

When introducing/declaring a new variable, you create a placeholder for an abstract expression (abstract in the sense that the variable does not represent a particular expression). Every variable declaration creates also a *scope* for that variable. A variable's scope is the part of the program that can refer to that variable. For example, in the line below (written in pseudocode)

```
add(a, b) = a + b;

```

variables `a` and `b` are being declared and their scope is the body of the `add` function. This means that any reference to `a` and `b` from within the body of `add` will refer to `add`'s parameters. And any reference to `a` and `b` from outside the body of `add` will be meaningless (so you get a compilation error) or will refer to some other variables (which happen to have the same name, but have been declared outside of the function's body).

* Altogether, this behavior is summarized in the sentence "Once a variable is declared, it becomes *bound* within its scope". Or, specific to this example, `add` binds the two variables `a` and `b`.

There's a third variable being declared in the pseudocode above and that is the `add` variable. So `add` is another placeholder, but this time the expression that `add` represents is not abstract, but a concrete value: it is the function that takes two expressions and returns their sum. Thus,

* Assigning a value to a variable means that, while retaining the functionality of a placeholder, the variable does not represent some abstract expression any more, but an actual concrete expression.

The action of assigning an expression to a variable is closely related to substituting an expression for a variable. One difference is that variable assignment happens explicitly by the programmer at design time, while substitution is an internal mechanism of the language and happens at runtime. Another difference is that, while variable assignment is itself an expression (it is part of the syntax of a language) and keeps the variable in scope, substitution is an action over expressions (it transforms expressions) and it entirely wipes away all occurrences of a variable from that expression. In other words, it eliminates the variable.

The relation between assigned variables and substitution is that all variables that have been assigned a value are internally substituted by their assigned values. This does not mean that substitution is triggered only through variable assignment. Another way is through function application (look up "beta-reduction" for more details).

---
Tags: formal-languages, programming-languages, type-theory, variable-binding
---


title: Modified shortest path problem

text:
# Question
Title: Modified shortest path problem
For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^\*(p)=\varSigma(w(v\_i,v\_{i+1}) -max\\{w(v\_i,v\_{i+1})) | 1\leq i \leq k$}

The complexity needs to be $O(V+E\log V)$. Obviously i thought about dijkstra, define a new weight function s.t shortest path according to that weight function is the shortest path we looking for, and that just run dijkstra algorithm on the graph using the new weight function, however I cant think about such function, does anyone have an idea? Thanks in advance.

# Answer
> 4 votes
Notice that if you allow **once** jumping without paying the weight cost, then the shortest path is exactly what you need.

Create 2 copies of $G: G\_1,G\_2$. For every edge $e=(v,u)\in G$ also add an edge $(v\_1,u\_2)$ between the node $v$ of $G\_1$ and $u$ of $G\_2$. Make those edge's weight to $0$.

Now, find a shortest path between $s\_1$ and $t\_2$ (using Djikstra)

---
Tags: algorithms, graphs, shortest-path, dijkstras-algorithm
---


title: Graph theory : Trees

text:
# Question
Title: Graph theory : Trees
I need to determine all the trees on 25 vertices for which there exists an integer m ≥ 2, such that the degree of each vertex gives the same remainder when divided by m.

Can somebody help ?

# Answer
> 1 votes
Suppose $G = (V, E)$ is a tree with 25 vertices such that there exist some constants $c \geq 0$ and $m \geq 2$ such that $\operatorname{deg} v \equiv\_m c$ for all $v$. Note that we can equivalently write $\operatorname{deg} v = a\_v m + c$ for some $a\_v \geq 0$.

Since $G$ is connected by definition, we get that it must have 24 edges in total, giving us $$ \sum\_{v \in V} \operatorname{deg} v = 2 \cdot |E| = 48.$$ We can express this sum using the aforementioned decomposition of the degrees in $G$ to get $$ \begin{align\*} \sum\_{v \in V} \operatorname{deg} v &= \sum\_{v \in V} a\_v m + c \\ &= c |V| + m \sum\_{v \in V} a\_v \\ &= 48. \end{align\*} $$ Due to the both terms in the rewritten sum being non-negative, we get that $c$ must be 1 if we are to find any solutions. Hence we get that $m$ must divide $48 - c|V| = 23$, which implies $m = 23$ as we required $m \geq 2$.

At this point, we know that any such $G$ satisfying your conditions does so with $c = 1$ and $m = 23$. By using our new formula again, we find that the sum of our $a\_v$ must also equal 1 and therefore, $G$ must be isomorphic to a tree with 1 internal node and 24 leaves, which is also known as the star graph $S\_{24}$.

---
Tags: graphs
---


# Question
Title: How to prove that replacing a character in a string in both C and JavaScript is equivalent?
I would like to try some different proofs, specifically in proving equivalence of the implementation of some feature in two different programming languages (C and JS in this question).

This is about proving that **replacing one character in a string** is equivalent in C and JS.

In JS, for example, strings are *immutable*, while in C, strings are *mutable*. So in JS you might have to do this:

```
functioni replaceAt(string, index, replacement) {
  return string.substr(0, index) + replacement + string.substr(index + replacement.length)
}

```

While in C you might just do something like this:

```
#include<stdio.h>

int
main() {
  char string[11] = "hello world";
  string[1] = 'i';
  printf("%s", string);
  return 0;
}

```

Basically, I am trying to come up with an example where, the *perceived effect* or *desired outcome* is *for all intents and purposes* **the same**. That is, the end result is that the character was replaced at a specific position (the same position in each language). Even though in one language the string was *mutable*, while in the other, it was *immutable*. What needs to be taken into account here to make a proof saying these are equivalent? How do we capture the notion of "partial equivalence" or "perceived equivalence"? (By that I mean, the outcome is roughly the same, so we want to make a proof statement that these are the same with regard to some spec).

# Answer
I would start by creating a formal definition of the function that you want and then proving for correctness each of the implementations.

Consider the following axiomatic definition:

$$replaceAt: string * \mathbb Z \*char \to string$$

$$\forall c:char . ( \forall i \in \mathbb Z~.~replaceAt(\`\`,i,c) = \`\` )$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~replaceAt(s,i,c)\[i\] = c ))$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~len(replaceAt(s,i,c)) = len(s) ))$$

$$\forall c:char .(\forall s:string . ( \forall i,j \in 0..len(s)-1 . i \neq j \implies replaceAt(s,i,c)\[j\] = s\[j\] ))$$

$$\forall c:char .(\forall s:string . ( \forall i \in \mathbb Z . i \geq len(s) \implies replaceAt(s,i,c) = s ))$$

If you can prove the correctness of each implementation to these axioms I'd say they're equivalent. At the moment your *C* implementation is not even a function. Your *Javascript* function takes a string and not a char. None of them are defined for indexes greater than your input.

I don't think comparing implementation to implementation makes sense as there are lot of differences in the implementation models of each language.
> 2 votes

---
Tags: programming-languages, proof-techniques, formal-methods
---


# Question
Title: Why frame must be longer than generator polynomial?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

> When the polynomial code method is employed, the sender and receiver must agree upon a **generator polynomial**, $G(x)$, in advance. Both the high- and low-order bits of the generator must be $1$. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is why to compute the CRC for some frame with $m$ bit corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial?

I tried to search for the reason but couldn't really find the exact answer, so in my opinion, if the generator polynomial is longer than the frame, it will create check bit that is more than data bit which is redundant because CRC is used in error detecting code and error detecting code is used in places where fewer error occur. But is that true?

# Answer
The easiest way to see this is from the receiver side. As in the excerpt, "If there is a remainder, there has been a transmission error." Implicitly, if there is no remainder, there is no transmission error.

The case of no transmission error, with no remainder means that if the checksummed frame is $M'(x)$, then there is a non-zero polynomial $A(x)$ such that

$$M'(x) = G(x)A(x)$$

where

$$\hbox{d}(M'(x)) = \hbox{d}(G(x)) + \hbox{d}(A(x))$$

and $\hbox{d}()$ means the degree of the polynomial (it's "length"). Since $\hbox{d}(A(x)) \ge 1$, then

$$\hbox{d}(M'(x)) \> \hbox{d}(G(x))$$

which means the frame is longer than the generator polynomial.
> 0 votes

# Answer
If the CRC polynomial is $m$-bit long, then in order to create $M'$ from $M$, you need to add $m$ bits (or perhaps $m-1$ bits). In particular, the final message $M'$ is at least $m$-bit long.
> 0 votes

---
Tags: error-correcting-codes, crc
---


# Question
Title: Shortest unambiguous representation of a graph over an alphabet
I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:

> Given the graph with the matrix representation \begin{bmatrix}0&0&1&1\\0&0&1&1\\0&1&0&1\\0&0&0&0\\\end{bmatrix} what is its shortest possible unambiguous representation over the boolean alphabet? How about over any alphabet?

Thank you :)

# Answer
Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.

A representation for the graph will be said to be **Unambiguous** if the graph can be reconstructed from that representation.

Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \\{0,1\\}$. If we had an additional symbol $|$ in our alphabet, then we can easily encode the graph matrix as $0011|0011|0101|0000$.

But, as we dealing with only boolean symbols, we have to come up with some encoding that doesn't need the separator $|$. An easy way for doing this could be making each 5th bit special. If it is $0$ then it will mark a separator, else the next four bits are also encoding a single row of the matrix, and it won't mark a separator. If the encoding of row doesn't need additional four bits, then make the extra bits $0$. (You need few more such rules to make this encoding "unambiguous").

For example, your matrix can simply be encoded 0011 **0** 0011 **0** 0101 **0** 0000.

Of course, there are much better possible encodings which might utilize the presence of patterns in the matrix (like *sparse matrix*).

But, your question asks: *Given a matrix representation of a graph, what is its shortest possible unambiguous representation over the boolean alphabet?* Well, we can easily come up with a trivial encoding: the empty string $\epsilon$ represents the given graph and all other strings represent the graph as per the encoding described above.

So, the smallest unambiguous representation of the given graph matrix would be of length $0$.

This will also hold for any other alphabet.
> 1 votes

---
Tags: graphs, formal-languages, theory
---


# Question
Title: Check if intersection of several 2D half-planes is empty
I have a large set of half-planes $a\_ix+b\_iy + c\_i \geq 0$.
What I need is is the fastest way to determine if they have at least one common point.
Currently I build a convex polygon by adding half-planes sequentially, there are $O(n^2)$ checks if a point belongs to a half-plane.
I need an algorithm that does $O(n \log n)$ or $O(n)$ checks.

# Answer
> 4 votes
Your problem can be solved in linear time.

This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question).

In your case $m=2$ therefore the resulting time complexity is $O(n)$.

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


# Question
Title: Why does linear search have $\frac{n}{2}$ comparisons on average?
I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $n$ cases corresponding to when the target value is the $1$st, $2$nd, ..., $n$th entry of the list. There is also the case where the entry is not in the list at all, so we have $n + 1$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $1, 2, \dots, n$ comparisons respectively. For the case where the target value is not in the list, we need $n$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $\frac{n}{2}$.

May I where is the fallacy in my reasoning? Thank you!

# Answer
It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a probability distribution for the input. As an example, it is well known that the average running time of naive quicksort is $\Theta(n \log n)$, but that result is dependent on assuming that the input arrays are uniformly distributed over the elements of the symmetric group of size $n$. If we choose different distributions, the result changes reflecting our choice.

Therefore, it is impossible to give a reasonable answer to your question without making assumptions of statistical nature on what queries you expect. In particular, the average number of comparisons is deeply impacted by what is the ratio of the inputs for which the search fails to find a matching element.

Intuitively, if the input distribution is such that you expect to miss almost every time, your average number of comparisons will be very close to $n$.
> 4 votes

# Answer
Let us assume that required element is **equally likely** to be in any position between $1$ and $n$. Let $x \_i $ be a random variable. Random variable $x\_i = 1$ means required element is in ith position and vice-versa. Now probability that required element is in position between $1$ and $n$ is $$ Pr\[x\_i = 1\] = \frac{1}{n}$$ Now Expected value is given by $$\mathbb{E}(x) = 1 \times\frac{1}{n} + 2 \times \frac{1}{n} + 3 \times \frac{1}{n} +\cdots + n \times\frac{1}{n} $$ which can be written as $$\mathbb{E}(x) = \frac{n(n+1)}{2n} = \frac{(n+1)}{2}$$ which is a required answer

**Reference** : https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node56.html
> 6 votes

# Answer
Let us assume that we are given a real number $x$ and a list of $n$ distinct real numbers. The linear search algorithm, described below,

```
   linearsearch(x, a1,a2,...an):

        i:=1
        while(i<=n and x not equal to ai):
              i:=i+1
        if i<=n:
             loc:=i
        else:
             loc:=0

```

locates $x$ by successively comparing it to each element in the list, terminating when $x$ is located or when all the elements have been examined and it has been determined that $x$ is not in the list.

**What is the average-case computational complexity of the linear search algorithm if the probability that $x$ is in the list is $p$ and it is equally likely that $x$ is any of the $n$ elements in the list?** (There are $n + 1$ possible types of input: one type for each of the $n$ numbers in the list and a last type for numbers not in the list, which we treat as a single input.)

Now $i$ comparisons are used if $x$ equals the $i$ th element of the list and, there are $n$ comparisons are used if x is not in the list. The probability that $x$ equals $a\_i$ , the $i$ th element in the list, is $\frac{p}{n}$, and the probability that $x$ is not in the list is $q = 1 − p$.

It follows that the average-case computational complexity of the linear search algorithm is

$$E= \frac{p}{n} + \frac{2p}{n} +···+ \frac{np}{n} + nq$$

$$= \frac{p}{n}(1+2+···+n) + nq$$

$$= \frac{p}{n}.\frac{n(n+1)}{2}+nq$$

$$= p.\frac{n+1}{2}+nq$$

Now if we plug in the probability that

$$p = \frac{n}{n+1}$$ and hence $$q=\frac{1}{n+1}$$ then

$$E = \frac{n}{n+1}\frac{n+1}{2}+n.\frac{1}{n+1} = \frac{n}{2}+ \frac{n}{n+1} = \frac{n^{2}+3n}{2n+2}$$

Now again if we plug in,

$$p=1$$ and hence $$q=0$$ then we have,

$$E= 1.\frac{n+1}{2}+n.0 = \frac{n+1}{2} $$
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, average-case, lists, searching
---


# Question
Title: How does an enumerator for machines for languages work?
In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :

"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks."

How exactly do you do what he is talking about for any r.e. collection of functions/languages (or complexity class like P)--enumerate the machines that solve the languages in the collection? Normally, when speaking about an enumerator, you talk about enumerating the words of a language, not a collection of languages.

# Answer
> 3 votes
Kozen answers this in your quote: what you enumerate is *Turing machines* that accept all languages in P. This makes sense in many contexts, for example if you want to diagonalize against all languages in P.

It is not a priori clear how to enumerate P (as Turing machines). The problem is that given a Turing machine, it is (provably) impossible to tell whether it halts in polynomial time. The trick is to force the machine to halt in polynomial time.

The enumerator goes over all pairs $(T,p)$, where $T$ is a Turing machine and $p$ is a polynomial. For each such pair, it creates a new machine $M(T,p)$ which simulates $T$ for $p(n)$ steps (where $n$ is the input length), and then halts. The machine $M(T,p)$ is guaranteed to run in polynomial time, and so whatever language it accepts is in P. Conversely, for any P-time machine $T$, there is a polynomial $p$ such that $T$ and $M(T,p)$ are equivalent, and so the enumerator goes over all languages in P.

---
Tags: turing-machines, enumeration
---


# Question
Title: Determine whether given f is shortest path function
I have the following question: Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every other vertex, i.e $0\leq dist(s,v) \< \infty$. Let $f\colon V \to \mathbb R$ a given function. Describe an algorithm that runs in $O(|V| + |E|)$ that determines wethter this given $f$ is the shortest path function from $s$, i.e $\forall v \in V :f(v)=dist(s,v)$.

What I thought about was to check for every $v \in V$ whether $f$ fulfill the two following demands:

1. $f(s)=0$
2. $f(v) \leq f(u) + w(uv)$ for all $u \in V$ and $uv \in E$

This runs in the proper complexity. I thought to prove it by showing that $f(v) \leq dist(s,v) \land f(v) \geq dist(u,v) \Rightarrow f(v) = dist(f,v)$

I proved that $f(v) \leq dist(s,v)$, but I am stuck at proving that $f(v) \geq dist(s,v)$.

# Answer
Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function.

You need to strengthen your second condition.
> 2 votes

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


# Question
Title: Efficient Data Structure for Closest Euclidean Distance
The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show\_problem&problem=1628.

> A network of autonomous, battery-powered, data acquisition stations has been installed to monitor the climate in the region of Amazon. An order-dispatch station can initiate transmission of instructions to the control stations so that they change their current parameters. To avoid overloading the battery, each station (including the order-dispatch station) can only transmit to two other stations. The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map). You are commissioned by Amazon State Government to write a program that decides if, given the localization of each station, messages can reach all stations.

The naive algorithm of course would build a graph with stations as vertices and calculate the edges from a given vertex by searching through all other vertices for the closest two. Then, we could simply run DFS/BFS. Of course, this takes $O(V^2)$ time to construct the graph (which does pass the test cases). My question, though, is if we can build the graph any faster with an appropriate data structure. Specifically, given an arbitrary query point $p$ and a given set of points $S$, can we organize the points in $S$ in such a way that we can quickly find the two closest points in $S$ to $p$ (say, in $\log V$ time?).

# Answer
If I understand this correctly, most spatial indexes could be used.

Spatial indexes typically have about $O(log{V})$ insertion time and similar lookup time for nearest neighbors. Of course you can create a Voronoi diagram from that, but you can also use the index directly to find the closest neighbors whenever you need them.

For low dimensionality (2D, 3D), The common families of spatial indexes are kd-trees (quite simple and generally good, but tend to have problems with dense clusters of points), quadtrees (a bit harder to implement yourself because numerical precision can be tricky) and R-Tree (hardest to implement, but give best guaranteed performance, especially the R\*Tree (R-Star-Tree)).

In case you are using C++, have a look at libSpatialIndex or the Boost R-Tree. If you are using Java, have a look at my TinSpIn library.

The technical term for this is "$k$ nearest neighbor queries" or "$k$-NN queries", with $k$ referring to the number of nearest neighbors you want to find.
> 3 votes

# Answer
It seems that the relevant data structure might be a dynamic Voronoi diagram.

Voronoi diagrams are often the answer when a set of points on the plane is involved.

In this case, since the point set is evolving, you want a dynamic version.
> 3 votes

---
Tags: data-structures, computational-geometry, search-algorithms, graph-traversal, nearest-neighbour
---


# Question
Title: Number of circuits with at most $m$ logic gates
I'm working on the same exercise as described in this post:

How to show that hard-to-compute Boolean functions exist?

In the answer there I don't understand how the number of circuits with at most $m$ gates was found to be $O(m^{4m})$. My construction of the number of gates required:

Let any logic gate in the circuit take 2 inputs, which could be any of the $n$ inputs or any of the $m-1$ other logic gates. Then there are ${{m+n-1}\choose{2}}$ possibilities for the inputs into any logic gate. There are 16 different functions that act on 2 inputs, so let there be $16{{m+n-1}\choose{2}}$ possibilities for the inputs and type for any logic gate. Lastly, since there are $m$ gates, there will be $16^m {{m+n-1}\choose{2}}^m$ possibilities for the entire circuit.

Now we can say ${{m+n-1}\choose{2}}^m \< \frac{1}{2^m}(m+n-1)^{2m} \< \frac{1}{2^m}(2m)^{2m}$ when $m = 2^n/\log n$ (or $2^n/n$), so $16^m {{m+n-1}\choose{2}}^m \< (32m^2)^m$. So we would want to show that $(32m^2)^m$ is less than $2^{2^n}$. This doesn't seem to be true anywhere, so I must have made a mistake somewhere.

I've looked online a bit and have found three different sources say that the number of circuits with at most $m$ inputs is $m^2$, $2^m$, and something similar to what I came up with. I understand that which gates to use is vague, but these are fundamentally different functions, and I'm very confused.

# Answer
> 2 votes
I would recommend reading the Circuit Complexity lecture notes by Jonathan Katz, in which he discusses the problem clearly.

You start off on the right foot. For two-input, single-output gates, there are 16 different possible logical functions. Each of the two gate inputs can either be from another of the $m$ gates or from one of the $n$ inputs, which leaves $16(m+n)^2$ possibilities for the type of each gate. Since there are $m$ gates, at first glance there should be $(16(m+n)^2)^m$ different circuits we could construct from these gates.

However, we should also specifically select for the output gate, so we multiply the number of circuits by $m$ to account for this choice: thus we have a bound of $m\cdot(16(m+n)^2)^m$ different possible circuits of size $m$.

The crucial step that you are missing is that the labels we assigned to each of our gates were arbitrary, and thus we can divide our bound by $m!$ to compensate for our overcounting.

We thus have a tighter bound of $$\frac{m \cdot (16 (m+n)^2)^m}{m!}$$ for the number of circuits of size $m$.

If we assume $m = (1-\epsilon)\frac{2^n}{n}$, for any $\epsilon\>0$, one can (and Katz does) show that this is less than $2^{2^n}$.

---
Tags: circuits
---


# Question
Title: What is implied probability, in the context of universal codes?
From Wikipedia:

> Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by $ p(i) ={2}^{-\ell(i)} $ where $\ell(i)$ is the length of the $i$th codeword and $p(i)$ is the corresponding symbol's probability

What is "implied probability"?

Given that prefix code are not fix-length codes, then I don't get what "implied probability" means, for example, given a 3 bits length code, implied probability is ${2}^{-3} = \frac{1}{8}$ but what does it mean? is it about choosing the code between others? or choosing random between all possible of three bits? as here we are talking about prefix codes, so length will vary among codes, so there could be only one code of three bits, so probability of get it would be 1? Any clarification will help!

# Answer
> 2 votes
The idea is the following:

the following tree $T$

$ \\ \emptyset \\ | \ \setminus \\ | \ \ \ \setminus \\ 0 \ \ \ \ \ 1 \\ | \ \setminus \\ | \ \ \ \setminus \\ 00 \ \ \ \ \ 01\\ \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \ 011 $

of depth 3 is constructed by

1. Taking an object *labeled as $\emptyset$* that has probability 1 and splitting it in half into two pieces *which we label as $0,1$;* who each acquire equal probabilities 1/2 individually.
2. Taking the object *labeled as $0$* that has probability 1/2 and splitting it in half into two pieces *which we label as $00,01$;* who acquire equal probabilities 1/4 individually.
3. Taking the object *labeled as $01$* that has probability 1/2 and splitting it in half into two pieces *which we label as $010,011$;* who each acquire equal probabilities 1/8 individually.

This is essentially the "unwrapping the Huffman algorithm in reverse." **You are asking the wrong question, you should be asking *"Why label it this way?"***

The idea behind the Huffman coding scheme is that

1. $0,1$ each cost 1 unit of "communication complexity" or "space complexity" depending on your interests
2. $00,01$ each cost 2 units of "communication complexity"
3. $010,011$ each cost 3 units of "communication complexity"

You should read chapter 5 of Cover and Thomas

and this Wikipedia article on the kraft inequality is probably helpful too. however, if you want a proof of the infinite kraft inequality you need chapter 5 of Cover and Thomas.

The idea is to continue this (type of) procedure unto infinity so that we get a something the following tree $T\_\infty$

$ \\ \emptyset \\ | \ \setminus \\ | \ \ \ \setminus \\ 0 \ \ \ \ \ 1 \\ | \ \setminus \\ | \ \ \ \setminus \\ 00 \ \ \ \ \ 01\\ \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \ 011 \\ \ \ \ \ \ \ \ \ \ \ | \ \setminus \\ \ \ \ \ \ \ \ \ \ \ | \ \ \ \setminus \\ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ 0101 $

which has infinite depth. **Each time you "split" a string, you maintain a "partition of unity" *i.e.,* you maintain a probability distribution. The kraft inequality states that if your code was constructed in this manner, *i.e.,*** $$ \sum\_{i : \text{leaf of }T\_\infty} 2^{-l(i)} = 1 $$ **then the code is optimal.**

> In other words if you have a set of binary strings $\mathcal{S}$ and the function $$p(s) = 2^{-l(s)}$$ turns out to actually satisfy the kraft inequality, *i.e.,* $$ \sum\_{s \in \mathcal{S}} 2^{-l(i)} = 1, $$ then it is an optimal code. **Therefore forming a probability distribution and being an optimal code are equivalent.**

One can further prove that all such codes have a tree that witnesses their optimality.

---

# Answer
> 1 votes
It has to do with information theory. Suppose we have a random source that outputs symbols with some fixed probability distribution $P$ over an alphabet $X$. Shannon's theory says that any coding scheme must use at least $H(P) = \sum\_{x \in X} P(x) \log\_2 (1/P(x))$ bits per symbol on average. The value $H(P)$ is called the entropy $P$. A full prefix code is always optimal for *some* distribution $P$, in the sense that it matches the $H(P)$ lower bound. That distribution is called the implied distribution of the code.

For example, suppose we have a prefix-code over the alphabet $\\{a,b,c,d\\}$ with code words $a$ = "000", $b$ = "001", $c$ = "01" and $d$ = "1". By your formula, the implied probability distribution is $P(a) = 1/8$, $P(b) = 1/8$ and $P(c) = 1/4$ and $P(d) = 1/2$. The entropy of this distribution is

$$\frac{1}{8} \log 8 + \frac{1}{8} \log 8 + \frac{1}{4} \log 4 + \frac{1}{2} \log 2 = \frac{3}{8} + \frac{3}{8} + \frac{2}{4} + \frac{1}{2} = \frac{7}{4}$$

The expected length of the code words is the sum of code lengths, each weighted by their probability:

$$ \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot 3 + \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 1 = \frac{7}{4} $$

This matches the entropy bound, and hence the code is optimal for this distribution.

# Answer
> 0 votes
First of all, you are mis-parsing the phrase 'implied probability distribution'. There is no such thing as 'implied probability'. What Wikipedia is saying is: Given a self-delimiting coding scheme, there is an 'obvious' or 'natural' *(here a mathematician would, I suspect, use the term 'canonical')* way to assign numbers to legal codewords, in such a way that the numbers constitute a probability distribution over the set of all legal codewords. The naturalness of this assignment means that it is not necessary to expend any great mental effort to explicitly construct this distribution, which is why it is 'implied'.

---
Tags: information-theory, huffman-coding
---


title: What's the name of this DFS variation

text:
# Question
Title: What's the name of this DFS variation
***Classical DFS:***

A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS is usually used to find an ordering of the tasks that satisfies all of the precedence constraints, classical DFS algorithm can do it by building the sequence step by step.

***An extension:***

Consider now the following variation. Each node $j$ is weighted by a value $w\_j$. When we are currently at node $j$, this weight will determine the next node to visit (the one with the higher weight).

Moreover, imagine that each time a node is added to the list, we recompute the weight for the unvisited nodes using a given function (we don't care about the nodes that has already been added to the sequence). Thus at step $t$, the $w\_j(t)$ of node $j$ can be different from its weight at step $t+1$.

---

**Questions:** Is there a name of this problem ? How to solve it efficiently? (e.g If a node has several successors, one needs to determine the successor with highest weight, so which data structure to use?)

**N.B** The image is only used for an illustration purpose. The graph is **not** assumed to be a binary tree.

Edit: the graph is assumed to be connected

# Answer
> 2 votes
This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function `w`. This strategy uses a priority queue (e.g. a heap, in this case a max heap).

Consider the following algorithm. $G=(V,E)$ is a graph with vertex set $V$ and edge set $E$, $w(j,t)$ is the weight function taking a vertex $j \in V$ and a timestep $t$, and $S \subseteq V$ is the list of start vertices (one in each connected component of $G$). $G$ is not necessarily connected.

```
BestFirstTraversal(G=(V,E), w(j,t), S)
    visited = []
    t = 0

    # from [0, t):   heap is the order in which the vertices are visited
    # from [t, end]: heap is a max heap
    heap = S  # from t to the end is max heap

    # loop until all vertices have been visited
    while len(visited) != |V| do
        u = heap[t]  # get the max element

        # do something with u

        append u to visited
        append neighbors of u (not in visited) to heap
        t = t+1

        heapify(heap[t:])  # based on w at step t
    end while
end

```

Let $n = |V|$ be the number of vertices.

Run Time: `BestFirstTraversal` runs in $O(n^2)$.

Notice $S$ is a list of vertices, one for each connected component of $G$. This is necessary because there must be a starting point for each connected component. If we started from a single node in a graph with more than one connected component, we would never be able to visit the other connected components. Thus the loop will visit each node in $G$ from one of the starting vertices.

Thus the while loop runs $n$ times. Appending neighbors and heapify takes up to $O(n)$ work. Hence, $n * (2 * O(n)) = O(n^2)$.

Note, heap will contain the order of the vertices visited at the end `BestFirstTraversal`.

Hope that helps!

---
Tags: graphs, graph-traversal, weighted-graphs, scheduling, depth-first-search
---


# Question
Title: Uncapacitated facility location problem using local search
I'm studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help with it.

In few words the UFLF deals with finding a subset of facilities from a given set of potential facility locations to meet the demands of all the customers such that the sum of the opening cost for each of the opened facilities and the service cost (or connection cost) is minimized

We can do the following local steps on current solution:

1. We can open one additional facility an “add” move.
2. We can close one facility that is currently open a “delete” move.
3. We can do both of these simultaneously a “swap” move.

> Let's assume we have optimal solution and let $S^\*$ be its open facilities, and let $\sigma^\*$ denote the corresponding optimal assignment of clients to open facilities. To compare the cost of this optimal solution to the current, locally optimal solution of the algorithm, we let $F$ and $F^\*$ denote, respectively, the total facility cost of the current solution and the optimal one, and similarly let $C$ and $C^\*$ denote their respective total assignment costs. The optimal value OPT is clearly $F^\*+C^\*$. Note that now $F$ stands for both the set of facilities and the cafility cost of the current solution, but the meaning at any given point should be clear from the context.

**What I need help with:**

> **Lemma 9.1:** *Let $S$ and $\sigma$ be a locally optimal solution. Then* $$ C \leq F^\* + C^\* = \mathrm{OPT}. $$

Proof from the book page 235:

> Consider some facility $i^\* \in S^\* - S$, and suppose that we open the additional facility $i^\*$, and reassign to that facility all of the clients that were assigned to $i^\*$ in the optimal solution: that is, we reassign all clients $j$ such that $\sigma^\*(j) = i^\*$. Since our current solution $S$ and $\sigma$ is locally optimal, we know that the additional facility cost of $i^\*$ is at least as much as the improvement in cost that would result from reassigning each client optimally to its nearest open facility; hence, $f\_{i^\*}$ must also be more than the improvement resulting from our specific reassignments; that is, $$ f\_{i^\*} \geq \sigma\_{j\colon \sigma^\*(j) = i^\*} (c\_{\sigma(j)j} - c\_{\sigma^\*(j)j}). $$

Not clear what is "open the additional facility $i^\*$".

Isn't $i^\* \in S^\*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?

**I also need help with:**

Proof from page 237:

> Let $\phi(i^\*)$ denote the facility in $S$ closest to $i^\*$.
>
> **Lemma 9.3:** *Let $S$ and $\sigma$ be a locally optimal solution. Then* $$F \leq F^\* + 2C^\*.$$
>
> Consider a facility $i$ that is not safe (or, in other words, is unsafe), and let $R \subseteq S^\*$ be the (non-empty) set of facilities $i^\* \in S^\*$ such that $\phi(i^\*) = i$; among those facilities in $R$, let $i’$ be the one closest to $i$. We will derive one inequality for each member of $R$, based on an add move for each member of $R - \\{i’\\}$, plus one swap move closing the facility at $i$, while opening a facility at $i’$.
>
> First let us derive an inequality for each add move corresponding to $i^\* \in R - \\{i’\\}$. As in the proof of Lemma 9.3, we open a facility at $i^\*$, and for each client $j$ that is assigned to $i$ in the locally optimal solution and is assigned to $i^\*$ in the optimal solution, we reassign client $j$ to $i^\*$. The change in cost caused by this move must also be non-negative, and we derive the inequality $$ f\_{i^\*} + \sum\_{j\colon \sigma(j) = i \text{ & } \sigma^\*(j)=i^\*} (c\_{\sigma^\*(j)j}-c\_{\sigma(j)j}) \geq 0. $$

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)

There is a typo and it's not Lemma 9.3 but Lemma 9.1 in the second paragraph, my second question here is also similar to the first question: what is $i^\*$ here?

Any clarification will be happily welcome.

# Answer
> 0 votes
> Not clear what is "open the additional facility $i^\*$".
>
> Isn't $i^\* \in S^\*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?

As the proof explicitly says, $i^\* \in S^\* - S$. In words, it is a facility which is open in the optimal solution but not in the locally optimal solution.

The phrase "open the additional facility $i^\*$" indicates modifying the locally optimal solution $S$ by opening the additional facility $i^\*$. This is clear from context, sine as you write, $i^\*$ is already open in $S^\*$, but is closed in $S$.

The facility $i^\*$ is marked with a star since that's how the author chose to name this variable. The name of the variable isn't important. That said, $i^\*$ is chosen by taking some facility which is open in $S^\*$ but not in $S$. That is, it is part of the optimal solution but not of the locally optimal one. So the notation makes sense to me. It is using the convention that stars denote parts of the optimal solution.

> If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)

The set $R$ consists of all facilities in $S^\*$ whose closest facility in $S$ is $i$. If $S = \\{i\\}$, then $R = S^\*$, and in particular, $R$ could contain more than one facility. Out of all facilities in $R$, we choose the one closest to $i$, and denote it $i'$.

> What is $i^\*$ in the second paragraph?

As the proof explicitly says, $i^\*$ is an arbitrary element of $R$ different from $i'$.

---
Tags: approximation
---


# Question
Title: Reference asking: phase transition in SAT
This is not a technical question, I hope this community has a room for such questions, but I will delete it in case this is inappropriate.

It has been experimentally observed (e.g. here) that when choosing a $3$-SAT formula by the following process:

On input $(n, \alpha n)$: choose $\alpha n$ clauses uniformly at random from the set of all clauses of $3$ literals over $x\_1, \ldots, x\_n$, and return the conjunction of these clauses.

The probability that the outputted formula is satisfiable depends on $\alpha$: if $\alpha \ll c$ the probability is very close to $1$, and if $\alpha \gg c$ the probability is very close to $0$ (it has been observed for a general $k$-SAT instances).

My question is what is the theoretical understanding of this problem? To the best of my knowledge, for other problems it is possible to prove similar claims quite easily (e.g. the probability that a random graph $G(n,p)$ has a clique of size $4$ is almost $1$ when $p(n) = \omega(n^{-2/3})$ and is almost $0$ when $p(n) = o(n^{-2/3})$, and it can be proven by a basic use of second moments).

However, for SAT I couldn’t find proofs. Do you know of any progress in this problem?

# Answer
The two most relevant rigorous results are:

1. Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-SAT problem. This paper (with an appendix by Jean Bourgain) shows that $k$-SAT exhibits a sharp threshold. However, a priori this threshold could depend on $n$ (i.e., this method cannot show that $\alpha$ is constant).
2. Jian Ding, Allan Sly, Nike Sun, Proof of the satisfiability conjecture for large $k$. The authors determine the exact value of $\alpha$ for $k \geq k\_0$. This value of $\alpha$ had been calculated by physicists using the cavity method, but their arguments are not rigorous.

Related work discusses the geometry of the solution space of $k$-SAT around various thresholds. See for example Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, On the solution‐space geometry of random constraint satisfaction problems.
> 1 votes

---
Tags: complexity-theory, reference-request, satisfiability, randomness, random-graphs
---


# Question
Title: Decidability of a language and inclusion between two other languages
I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer:

*"Let L₁, L₂ be decidable languages.<br>For every language L s.t. L₁ ⊆ L ⊆ L₂, L is decidable too*

My first idea was to use the Halting Problem Language as L and show that is not decidable to prove the statement is false.

I tried to ask the Professor and he confirmed me that the assignment is false but he gave me a hint about explicitly describing the two languages L₁ and L₂, but I don't know which one would fit for this scope.

Thank you!

# Answer
> 2 votes
Your statement is false. Indeed, if $L$ is any language over $\Sigma$, then $$ \emptyset \subseteq L \subseteq \Sigma^\*.$$

---
Tags: undecidability, closure-properties
---


# Question
Title: Average Case Analysis of Insertion Sort as dealt in Kenneth Rosen's "Discrete Mathemathematics and its Application"
I was going through *"Discrete Mathematics and its Application" by Kenneth Rosen* where I came across the following algorithm of the Insertion Sort and also its analysis. The algorithm is quite different from the one dealt with in the CLRS so I have shared the entire algorithm below. Note that they have considered a machine where only comparisons are considered are significant and hence have proceeded according. The problem which I face is in the analysis portion given here in bold. Moreover the specific doubts which I have , have been pointed out by me at the very end of this question.

**ALGORITHM** **The Insertion Sort.**

---

**procedure** insertion sort($a\_1,a\_2,...,a\_n$: real numbers with $n \geqslant 2 $ )

```
for j:= 2 to n
begin
    i:=1
    while aj > ai
        i:=i+1
    m := aj
    for k:= 0 to j-i-1
        aj-k := aj-k-1
     ai:=m
end {a1,a2,...,an is sorted}

```

> THE INSERTION SORT: The insertion sort is a simple sorting algorithm, but it is usually not the most efficient. To sort a list with $n$ elements, the insertion sort begins with the second element. The insertion sort compares this second element with the first element and inserts it before the first element if it does not exceed the first element and after the first element if it exceeds the first element. At this point, the first two elements are in the correct order. The third element is then compared with the first element, and if it is larger than the first element, it is compared with the second element; it is inserted into the correct position among the first three elements.
>
> In general, in the $y$ th step of the insertion sort, the $y$ th element of the list is inserted into the correct position in the list of the previously sorted $j — 1$ elements. To insert the $y$ th element in the list, a linear search technique is used; the $y$ th element is successively compared with the already sorted $j — 1$ elements at the start of the list until the first element that is not less than this element is found or until it has been compared with all $j — 1$ elements; the $y$ th element is inserted in the correct position so that the first $j$ elements are sorted. The algorithm continues until the last element is placed in the correct position relative to the already sorted list of the first $n — 1$ elements. The insertion sort is described in pseudocode in Algorithm above.

**Average-Case Complexity of the Insertion Sort**: What is the average number of comparisons used by the insertion sort to sort $n$ distinct elements?

Solution: We first suppose that $X$ is the random variable equal to the number of comparisons used by the insertion sort to sort a list $a\_1 ,a\_2 ,...,a\_n$ of $n$ distinct elements. Then $E(X)$ is the average number of comparisons used. (Recall that at step $i$ for $i = 2,...,n$ , the insertion sort inserts the $i$ th element in the original list into the correct position in the sorted list of the first $i − 1$ elements of the original list.)

We let $X\_i$ be the random variable equal to the number of comparisons used to insert $a\_i$ into the proper position after the first $i − 1$ elements $a\_1 ,a\_2,...,a\_{i−1}$ have been sorted. Because

$X=X\_2+X\_3+···+X\_n$,

we can use the linearity of expectations to conclude that

$E(X) = E(X\_2 + X\_3 +···+X\_n) = E(X\_2) + E(X\_3) +···+E(X\_n).$

**To find $E(X\_i )$ for $i = 2, 3,...,n$ , let $p\_j (k)$ denote the probability that the largest of the first $j$ elements in the list occurs at the $k$ th position, that is, that $max(a\_1 ,a\_2 ,...,a\_j ) = a\_k$ , where $1 ≤ k ≤ j$ . Because the elements of the list are randomly distributed, it is equally likely for the largest element among the first $j$ elements to occur at any position. Consequently, $p\_j (k) = \frac{1}{j}$ .If $X\_i (k)$ equals the number of comparisons used by the insertion sort if $a\_i$ is inserted into the $k$ th position in the list once $a\_1,a\_2 ,...,a\_{i−1}$ have been sorted, it follows that $X\_i (k) = k$ . Because it is possible that $a\_i$ is inserted in any of the first $i$ positions, we find that**

$E(X\_i)$ = $$\sum\_{k=1}^{i} p\_i(k).X\_i(k) = \sum\_{k=1}^{i} \frac{1}{i}.k = \frac {1}{i}\sum\_{k=1}^{i} k = \frac{1}{i}.\frac{i(i+1)}{2} = \frac{i+1}{2}$$

It follows that

$E(X)$ = $$\sum\_{i=2}^{n} E(X\_i) = \sum\_{i=2}^{n} \frac{i+1}{2} =\frac{n^{2} + 3n -4}{4}$$

**My doubt**

---

Now here while we are considering the calculation of $E(X\_i)$ we are first considering the probability of the maximum element between $a\_1,a\_2,...,a\_i$ being at position $k$. Then they are saying that the number of comparisons when $a\_i$ is placed into the $k$ th position in the list $a\_1,a\_2,...,a\_{i-1}$ (which is already sorted) is $k$. Why are they considering the insertion of $a\_i$ into the position of the maximum of the elements $a\_1,a\_2,...,a\_i$. $a\_i$ as per the algorithm should be placed at the first position (while scanning the array from left) when we find an element which is $\geqslant a\_i$ and not the maximum element of the sublist $a\_1,a\_2,...,a\_i$.

Moveover they say that the max element of the sublist $a\_1,a\_2,...,a\_i$ is any arbitrary position $k$ th and the probability of it being $\frac{1}{i}$. But if we see that $a\_1,a\_2,...,a\_{i-1}$ is sorted then the max of $a\_1,a\_2,...,a\_i$ is either $a\_{i-1}$ or $a\_i$.

# Answer
> 1 votes
The probability $1/i$ is correct, since it refers to the relative order of $a\_1,\ldots,a\_i$ before sorting the first $i-1$ elements.

However, the argument seems wrong. The relevant probability is not $p\_i(k)$, but rather $q\_i(k)$, which is the probability that $a\_i$ is the $k$'th smallest element out of $a\_1,\ldots,a\_i$ (*before* sorting). This probability is $1/i$, independent of $k$.

---
Tags: algorithms, algorithm-analysis, sorting, average-case
---


# Question
Title: Algorithm to turn gray-scale text into legible binary black and white text
I have an image with gray-scale anti-aliased text produced by Chromium and need to convert this into pure binary black and white text. Applying a simple binary threshold pass over the image causes artifacts, either missing edges or weird protrusions and text being too bold depending on the chosen threshold.

Below an example of the input, the perfect outcome (as this is how the text *would* be rendered without AA) and the current outcome based on binary threshold (I think this is a 0.6 threshold). Sadly, it's not possible to instruct Chromium to render the text without anti-aliasing, so a conversion is the only option.

I was wondering if there was an established algorithm for this kind of problem or in what direction I would have to look to find something that could be adapted to work here. Any algorithm would need to be able to run in semi-realtime, no offline solutions.

# Answer
It is possible that the literature on image vectorization might be useful. That basically tries to reconstruct the strokes that produced the image. However, I think this is going to be challenging when the width of the strokes is narrower than two pixels or so, and it is possible that standard techniques might work poorly in that domain. I would recommend that you try increasing the font size or the resolution, and then try standard methods.

For your example image, I get somewhat more reasonable results by using a better threshold (0.8), but I think you'll do a lot better if you can increase the resolution.

If you know in advance what font and font size will be used, it might be feasible to render each possible character and capture an image of the anti-aliased rendered result for each possible character, in a few random locations, and then use simple pattern matching.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method
> Show by induction that any solution to a recurrence of the form $ T(n) \le 2T(n/3) + c\log\_3 n $ is $O(n\log\_3 n)$.

Hoping someone can help me with the correct solution. I attempted two ways to get the solution (but I think that they're both incorrect):

## SOLUTION A

\begin{align} T(n) &\le 2T(n/3) + c \log\_3 n \\ &\leq 2\[k(n/3)\log\_3(n/3)\] + c\log\_3 n \\ &= (2/3)kn(\log\_3 n-1) + c\log\_3 n \\ &= (2/3)(kn)\log\_3 n \\ &= (2/3)kn + c\log\_3n \\ &= \[(2/3)kn + c\]\log\_3n - (2/3)kn \end{align}

## SOLUTION B

\begin{align} T(n) &\le 2T(n/3) + c \log\_3n \\ &\le 2 \[ k(n/3)\log\_3(n/3) \] + c \log\_3n \\ &= (kn - kn/3)(\log\_3n - 1) + c \log\_3n \\ &= (kn)\log\_3n - (kn/3)\log\_3n - kn + c\log\_3n \\ &= (kn)\log\_3n - (2/3)kn + (c - kn/3)\log\_3n \end{align}

# Answer
> 1 votes
Here is what happens when you use the substitution method, assuming a base case of $T(1) = 0$ and $c=1$: \begin{align} T(3^m) &\leq m + 2T(3^{m-1}) \\ &\leq m + 2(m-1) + 2^2T(3^{m-2}) \\ &\leq m + 2(m-1) + 2^2(m-2) + 2^3T(3^{m-3}) \\ &\leq \ldots \\ &\leq m + 2(m-1) + 2^2(m-2) + \cdots + 2^{m-1}(1) + 2^m T(1) \\ &= m + 2(m-1) + 2^2(m-2) + \cdots + 2^{m-1}(1) \\ &= m(1 + 2 + \cdots + 2^{m-1}) - (2 + 2^2 + \cdots + 2^{m-1}) - (2^2 + \cdots + 2^{m-1}) - \cdots - (2^{m-1}) \\ &= m(2^m-1) - (2^m-2) - (2^m-2^2) - \cdots - (2^m-2^{m-1}) \\ &= m(2^m-1) - (m-1)2^m + (2 + 2^2 + \cdots + 2^{m-1}) \\ &= m(2^m-1) - (m-1)2^m + (2^m-2) \\ &= 2^{m+1}-m-2. \end{align} This shows that $T(n) = O(n^{\log\_32})$.

---
Tags: recurrence-relation
---


# Question
Title: Finding the upper bound of states in Minimal Deterministic Finite Automata
I have a task to determine the upper bound of states in the **Minimal Deterministic Finite Automata** that recognizes the **language**: $ L(A\_1) \backslash L(A\_2) $, where $ A\_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A\_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.

The way I am trying to solve the problem:

1. $ L(A\_1) \setminus L(A\_2) = L(A\_1) \cap L(\Sigma^\* \backslash L(A\_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
2. Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.

Am I right?

# Answer
> 3 votes
This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of $$2^{nm}. $$ This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound $$ n2^m. $$

This bound is tight for infinitely many values of $n,m$. Consider the language $L\_2$ of all words over $\Sigma^\*\\{\sigma\_1,\ldots,\sigma\_2\\}$ that *do not* contain all letters. There is an NFA for $L\_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L\_2}$ needs to contain at least $2^m$ states. Since $\overline{L\_2} = \Sigma^\* \setminus L\_2$ and $\Sigma^\*$ can be accepted by a single-state DFA, we see that the bound above is optimal.

You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^\*$ with $(\Sigma^n)^\*$.

---
Tags: computability, automata, regular-languages, finite-automata
---


title: Why is this grammar an LL(2) grammar?

text:
# Question
Title: Why is this grammar an LL(2) grammar?
I had a question regarding LL($k$) grammars. I came across a problem that I attempted to solve, but my answer varied from the solution and I wasn't sure why.

$$L = \\{a^{n + 2}b^mc^{n + m}\ :\ n \ge 1,\ m \ge 1\\}$$

The grammar I came up with is:

$$ \begin{align} S & \rightarrow aaA \\ A & \rightarrow aAc\ \vert\ bBc \\ B & \rightarrow bBc\ \vert\ bc \\ \end{align} $$

According to the solution, this given language has an LL($2$) grammar, but the answer I came up with was LL($4$).

My reasoning is that since the start of the language has at least three $a$'s, you need to check the fourth position in order to see which production to use afterwards. Then you can "slide" the window one position to the right to check subsequent productions.

Why is it considered LL($2$)?

Thank you.

# Answer
An LL parse produces a leftmost derivation, which means that at each point in the derivation, the leftmost non-terminal must be replaced by one of its productions. The issue is to decide which production to use.

A grammar is LL(k) if the production to be used in the leftmost derivation can always be determined by examining only the terminals prior to the first non-terminal and the $k$ following terminals in the input. (These will be the next $k$ symbols in the input if we're doing a left-to-right parse; the terminals prior to the non-terminal will already have been input.)

In your grammar, neither $S$ nor $A$ present any problems at all. $S$ only has one production, so there is no need to examine any terminal at all to make a decision. $A$ has two productions, but their first terminal differs so it is trivial to predict which one to select: if the next input symbol is $a$, select the first alternative; if it is $b$, select the second one.

$B$ also has two productions, but both of them start with a $b$. So we need to look at least one symbol further in the input. Now, what is the second symbol in a derivation starting with each production for $B$? For $B \to b c$, the second symbol is clearly $c$. In $B \to b B c$, the second symbol must be the first symbol in some derivation of $B$. But, as we've just observed, every derivation of $B$ starts with $b$. So the second symbol in $B \to b B c$ must be a $b$.

With that, we have a complete decision procedure:

* If the non-terminal to expand is $S$:
    + choose the production $S \to a a A$
* If the non-terminal to expand is $A$:
    + If the next input is $a$:
        - choose the production $A \to a A c$
    + If the next input is $b$:
        - choose the production $A \to b B c$
* If the non-terminal to expand is $B$:
    + If the next two input symbols are $bb$
        - choose the production $B \to b B c$
    + If the next two input symbols are $bc$
        - choose the production $B \to b c$
* If there is no non-terminal left
    + Report success
* If none of the above rules apply
    + Report failure

The longest sequence of terminals we need to examine in any of those rules is 2. So the grammar is LL(2).
> 3 votes

# Answer
You can easily transform this grammar to LL(1) by extracting the common prefix $b$ in both productions of $B$, a procedure called left-factoring.

You get this:

$B \to b B'$

$B' \to B c$

$B' \to c$

Then $B$ always starts with $b$ and $B'$ starts either with $b$ or with $c$ which can be desided by looking at only one input symbol.
> 2 votes

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


# Question
Title: How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Let us consider the following Context-Free Grammar

G = ({S,A,B,C,D},{a, b}, S, P) with production rules P:

S → SSA | Bb

A → BSA

B → A | Cb

C → AD | Cb | ɛ

D → a | b | ɛ

Let L be the language produced by G. Design a single state Pushdown Automaton that accepts L. Indicate the relevant functions of transitions and draw the Automaton.

The solution I came up with is that L will be **(b^n: n\>1)** and that A won't produce any strings )

Example: {bbbb,bbbbbbbbbbbbbbbbbbbbbbbb,bb,bbb

or Remove A and the L produced will be **(a+b^n)**

ALso What will happen at AD?

# Answer
I recommend to use this explanation on how to transform a CFG into a (1 state) PDA
> 0 votes

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


# Question
Title: Where is the theory about "binary toggling games"?
Let us -- using parameters $M, N$ and $L$ --

1. create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V\_k\[i\] = b \sim Bin(n=1, p=0.5)\ \forall i \in \\{0\ ..\ N-1\\}, \forall k \in \\{0\ ..\ M-1\\}$.
2. create an N-bit long vector $A\_0$ and initialize it to ones.
3. create an $M$-bit long vector $S$ and initialize it randomly in the same manner as any $V\_k$.
4. for $i$ from $0$ to $M$, if $S\[i\] = 1$, then $A\_i = A\_{i-1} \oplus V\_i$, otherwise $A\_i = A\_{i-1}$, resulting in $A\_M$ after $M$ steps
5. present an agent/player with $A\_M$ together with all vectors $V\_k$ and make him return $S$ or the set of indices of vector $S$ where $S\[i\] = 1$. It follows that $A\_M \oplus V\_{i\_0} \oplus V\_{i\_1} \oplus V\_{i\_2} \oplus\ ...\ \oplus V\_{i\_{last}} = A\_0$.

A simple example with $N=4$ and $M=3$:

$A\_M = \[0, 1, 0, 1\]$, $V\_0 = \[1, 1, 0, 1\]$, $V\_1 = \[0, 0, 1, 1\]$, $V\_2 = \[0, 1, 1, 1\]$

solution $\rightarrow S = \[1, 0, 1\],$ because $A\_M \oplus V\_0 \oplus V\_2 = \[1, 1, 1, 1\]$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the "binary toggling game".

What I wonder is:

* what are "binary toggling games" really called
* what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

Could you please provide links? I hope they exist.

# Answer
"Binary toggling games" are generally just arithmetic problems over GF(2).

Your particular problem is equivalent to the following over GF(2):

$$\sum\_i V\_iS\_i = 1 + A\_M $$

If we write $\vec{S} = \[S\_1, S\_2, \dots\]^T$ and $V = \[V\_1, V\_2, \dots\]^T$ we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A\_M$$

You can solve this problem using Gaussian elimination over GF(2). In your example:

$$\left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 \end{array}\right) \longrightarrow \left(\begin{array}{ccc|c@} \color{red}1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &\color{red}1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &1 & 0 & 0\\ 0 & 0 & \color{red}1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right) $$

From which we can read off that $S\_1 = 1$, $S\_2 = 0$ and $S\_3 = 1$.
> 2 votes

---
Tags: complexity-theory, combinatorics, binary, computer-games, xor
---


title: Exit a deadlock cycle

text:
# Question
Title: Exit a deadlock cycle
Suppose i have the following resource allocation graph with a deadlock cycle, i see why it is a deadlock cycle, what i don't get is how to recover from this cycle

i'm thinking about aborting a process, any process here will lead to non-deadlock situation, but doesn't that cause the other process to not execute and hence the program won't execute as we're expecting it to be, i think this is a correct answer, but is there another way to do such that all processes will eventually run ?

# Answer
You don’t exit a deadlock cycle. Once you are in a deadlock situation, you lost. You do your best to avoid deadlocks.

With server software, you may be able to have a process that watches other processes and kills them if they are stuck due to a deadlock. Doing this *correctly* and make your software continue to run correctly is extremely difficult. It’s so difficult that i wouldn’t even try. In addition it is an absolute pain to test (and you don’t want software that isn’t tested). For normal software running in anything from workstation to mobile phone, it’s just not done. Remember that you have two tasks that are trying to do something and one or both of them have to be killed, that is hard to recover from.

What you do in practice: 1. Instead of locking a mutex you check if it is lockable which avoids deadlocks. 2. You add code that detects situations where a deadlock is *possible*. And if you find a *possible* deadlock you fix your code. 3. Write sensible code in the first place.
> 1 votes

---
Tags: deadlocks
---


# Question
Title: Are the empty string and some words of even length words of this language?
$L = \\{w \in \\{a,b\\}^\*\mid \text{the first, the middle, and the last characters of $w$ are identical}\\}$.

I have my answers, but I need confirmation:

Is the empty string $\epsilon \in L$? Yes. Reason: there is no first, middle, or last character to break the rule.

A word of even length, assuming the first and last character of it are identical, again, must be in $L$, as there is no middle character in it to break the rule.

This is in the context of theory of computation.

# Answer
> 1 votes
Yes, since "the first, the middle, and the last characters of $w$ are identical" is not really well defined here (so there might be ambiguities like is $\epsilon\in L$?)

Probably it wont really matter for the question if you assume $\epsilon\in L$ or $\epsilon \notin L$ (other than some small change in the PDA or CFG) But if you really want to make sure everything is ok, then write (in the answer for the question) that there are ambiguities and this is how you interpeted them.

---
Tags: formal-languages, terminology, sets
---


# Question
Title: Alternatives to multiplication/division/modulo for encoding choices?
The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number \[0, n) and set x = n * x + s, decoded with s = x % n, x = x / n.

Is this optimal if the only constraint is that the encoded result must be a bitstring? Would \*+/% still be the choice if they were not available as instructions?

I know arithmetic coding (and ANS) exists, but it also can't avoid big integer arithmetic without giving up some entropy.

# Answer
You can implement ANS using only additions, masks and shifts. Take a look at Finite State Entropy (FSE), it's a performance-focused version of ANS with accurate compression.
> 1 votes

---
Tags: data-compression
---


# Question
Title: Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?
What is the difference between the Magnitude and the Phase Spectrum of the Fourier Transform?

# Answer
Fourier Transform changes basis from time (spatial data) to frequency. To encode frequency we need amplitude (magnitude) to know how strong is signal at given frequency and phase to know when sine started - in what moment of its phase we are now.

Example: take input signal $5\sin(x + \pi)$, here phase is $\pi$ and magnitude is $5$.
> 1 votes

---
Tags: fourier-transform
---


# Question
Title: What makes a nested function in gcc so complicated?
Disclaimer: I'm not a compiler expert, but some of my best friends are! :)

I do a lot of embedded systems programming where stack (and other memory) is limited. Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage. Here's an example of what I had in mind:

(Though the algorithm isn't important for this question, assume that `list_traverse` takes a pointer to a list head and a function. The `contains_aux()` function gets called with each element in turn.)

```
bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  void contains_aux(list_t *list) {
    if (list == item) {
      found = true;
    }
  }
  list_traverse(head, contains_aux);
  return found;
}

```

I *assumed* that the nested `contains_aux()` function would be able to directly reference its lexically closed variables (`found` and `item`). But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the `contains_aux()` function.

I know that `contains_aux()` can't share the same stack frame as `list_contains()` because there's an intervening function on the stack (`list_traverse()`), but -- geez -- it seems like the compiler could pass the frame pointer from `list_contains()` so `contains_aux()` could access its locals.

Is there a reason it doesn't work this way? Is there a way I could torture the compiler into doing that? Or should I just resign myself using un-nested functions and passing a "context" object to `contains_aux()`?

# Answer
I don't see any obvious reason why the compiler could not inline the call to `list_traverse`, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily valid, but a reason can be just a suspicion.)

Without inlining, though, it's very difficult to see how the trampoline could be avoided. The frame containing the variables has to be passed through `list_traverse` so that it can be handed off to `contains_aux`. But presumably `list_traverse` is used elsewhere, and those other calls might not even involve a nested function, in which case there would be no stack frame to be passed through. There's nothing in `list_traverse`'s prototype which specifies that it might be called with a nested function, so if it has external linkage, it needs to be usable with the standard calling convention, which has no room for hidden parameters. And if it is called with a nested function, there is no guarantee that the nested function it is called with was nested in the same way. (For example, there might be more than one stack frame which needs to accompany the closure, if the bound variables come from different places in the call stack.)

So aside from inlining, the only safe solution is to manufacture something which can be called like an ordinary function, thereby conforming with the type of `list_traverse`'s first argument.

As evidence that inlining is possible, I offer the following C++ program, in which the same compiler happily inlines the lambda:

```
struct list_t {
    int value;
    list_t* next;
};

template<typename F>
void list_traverse(list_t* head, F check) {
    while (head && check(head))
        head = head->next;
}

bool list_contains(list_t *head, list_t* item) {
    bool found = false;
    list_traverse(head, [&](list_t *list)->auto {
        return list == item ? (found = true, false) : true;
        });
    return found;
}

```

(Alternatively, with a strangely bloated result: https://gcc.godbolt.org/z/s9XqW7).

I do understand that inlining might not be exactly what you're looking for, though.
> 2 votes

---
Tags: lexical-analysis, code-generation
---


# Question
Title: Marginal Probability of Generating a Tree
Fix some finite graph $G = (V, E)$, and some vertex $x$.

Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows:

1. Let $T\_0 = \\{ x \\}$.
2. For $0 \< n \leqslant N$

i. Let $B\_n$ be the set of neighbors of $T\_{n-1}$ outside of $T\_{n-1}$.

ii. Form $T\_n$ by

* Sample a pair $(x\_n, y\_n) \in E(G) \cap \left( V (T\_{n-1}) \times B\_n \right)$, with probability $q\_n (x\_n, y\_n | T\_{n-1} )$,
    * Add $y\_n$ to $V(T\_{n-1})$, and add $(x\_n, y\_n)$ to $E (T\_{n-1})$.
3. Return $T\_N$.

Suppose also that $q\_n ( x\_n, y\_n | T\_{n-1} )$ can be computed easily for all $(T\_{n-1}, x\_n, y\_n)$. I am interested in efficiently and exactly calculating the marginal probability of generating the tree $T\_N$, given that I began growing it at $T\_0 = \\{ x \\}$, i.e.

$$P(T\_N | T\_0 = \\{ x \\}) = \sum\_{x\_{1:N}, y\_{1:N}} \prod\_{n = 1}^N q\_n (x\_n, y\_n | T\_{n-1} ).$$

**My question** is essentially whether I should expect to be able to find an efficient (i.e. polynomial-time) algorithm for this, and if so, what it might be.

Some thoughts:

* Naively, the sum has exponentially-many terms, which precludes trying to evaluate the sum directly.
* On the other hand, this problem is also highly-structured (trees, recursion, etc.), which might suggest that some sort of dynamic programming approach would be feasible. I'm not sure of exactly how to approach this.
* Relatedly, I know how to calculate unbiased, non-negative estimators of $P(T\_N | T\_0 = \\{ x \\})$, which have reasonable variance properties, by using techniques from Sequential Monte Carlo / particle filtering. This suggests that the problem is at least possible to approximate well in a reasonable amount of time.

# Answer
No. If $q(x\_n,y\_n|T\_{n-1})$ is arbitrary -- there can be an arbitrary dependence on $T\_{n-1}$ -- then this requires exponential time.

Consider a tree $T\_N$ that has a single root node, $N-1$ leaves, and an edge from the root to each leaf. There are $2^N$ subtrees of $T\_N$, and in particular, there are $2^N$ possible values of $T\_n$ that can occur in the expression

$$\sum\_{x, y} \prod\_{n = 1}^N q\_n (x\_n, y\_n | T\_{n-1} ).$$

One can use a simple adversary argument to prove that evaluating this expression requires exponential time. Suppose that we evaluate $q\_n(x\_n,x\_n|T\_{n-1})$ by querying an oracle with $x\_n,y\_n,T\_{n-1}$. Suppose there is a single tree $T$ that is never queried to the oracle as any $T\_{n-1}$. Choose all of the $q\_n(\cdots)$ values to be strictly positive. Then since $q\_n(x\_n,y\_n|T)$ wasn't queried during execution, we can choose it after observing the output of the algorithm; but by varying it, we can choose a value that makes the algorithm's output wrong (in particular, the value of the expression depends on $q\_n(x\_n,y\_n|T)$ but the algorithm's output doesn't depend on $q\_n(x\_n,y\_n|T)$, so the algorithm's output cannot correct). We have proven that, to produce the correct output, any correct algorithm must query the oracle for all $2^N$ possible subtrees of $T\_N$. It takes at least $O(1)$ time to query an oracle.

In conclusion, this argument proves that any correct algorithm for computing this expression must take $\Omega(2^N)$ time.

I don't know whether it can always be done in $O(2^N)$ time, or whether perhaps $O(N!)$ time might be required.
> 2 votes

---
Tags: graphs, trees, recursion, randomized-algorithms, random-graphs
---


# Question
Title: How to understand definition of $\Pi_k$ in arithmetical heirarchy
Am reading a text about computability theory, and according to the text, at each level $k$ of the arithmetical hierarchy, we have two sets, $\Sigma\_k$ and $\Pi\_k$, where $\Pi\_k$ is defined as:

$$ \Pi\_k=co-\Sigma\_k $$

So that for $k=0$, we have the class of decidable sets and $\Sigma\_0=\Pi\_0$, and for $k=1$, we have $\Sigma\_1$ as the class of computably enumerable (c.e.) sets and $\Pi\_1$ as the class of not computably enumerable sets (not c.e.)....

Let $L(M\_e)$ denote the language recognized by Turing Machine $M\_e$ with Godel number $e$. I came across the following language $E$, where:

$$E=\\{e|L(M\_e)=\Sigma^\*\\}$$

i.e. $E$ is the language of all Turing Machine codes $e$ that are computably enumerable. By a diagonalization argument, it can be shown that $E$ is not c.e. This implies that:

$$ E \in \Pi\_1 $$

However, if $E \in \Pi\_1$, it means that $E = co-A$, for some $A \in \Sigma\_1$, using the definition in the above statement... However, the complement of $E$ is:

$$ \overline{E}=\overline{\\{e|L(M\_e)=\Sigma^\*\\}} $$

which (I guess) means that $\overline{E}$ is the language of all Turing Machines $e$ such that on some inputs, $e$ diverges... However, it has been shown that $\overline{E} \equiv\_m K^{2}$, i.e. $\overline{E} \equiv\_m K^K$, so that, where given two sets $A$ and $B$, we have $A \equiv\_m B$ iff $A \leq\_m B$ and $B \leq\_m A$, and $\leq\_m$ refers to a many-to-one reduction:

$$ \overline{E} \equiv\_m K^K \in \Sigma\_2 $$

Given that $\Sigma\_2 \neq \Sigma\_1$, it looks like that $\overline{E}$ is not computably enumerable... But doesn't this contradict the definition of $\Pi\_1$ which states that the complement of a not c.e. set is c.e. ?

I think am missing something in my understanding of the definitions ...

# Answer
> 3 votes
For $k$ even, a language $L$ is in $\Pi\_k$ if there exists a recursive predicate $R$ such that $$ x \in L \Longleftrightarrow \forall y\_1 \exists y\_2 \cdots \forall y\_{k-1} \exists y\_k \\, R(x,y\_1,\ldots,y\_k) $$ The quantifiers alternate between $\forall$ and $\exists$.

When $k$ is odd, the same definition works, but the last quantifier is $\forall$: $$ x \in L \Longleftrightarrow \forall y\_1 \exists y\_2 \cdots \exists y\_{k-1} \forall y\_k \\, R(x,y\_1,\ldots,y\_k) $$

For example, the language of all total Turing machines is $\Pi\_2$ since $$ x \in \mathsf{TOT} \Longleftrightarrow \forall y \exists z \\, \text{"Machine $x$ halts on input $y$ within $z$ steps"} $$

The class $\Sigma\_k$ is defined in the same way, with the first quantifier being $\exists$ rather than $\forall$.

If you complement a language in $\Sigma\_k$ you get one in $\Pi\_k$, and vice versa. This is due to de Morgan's laws for quantifiers, and the fact that the negation of a recursive predicate is also recursive.

For example, the language of *non*-total Turing machines is $\Sigma\_2$ since $$ x \in \mathsf{NTOT} \Longleftrightarrow x \notin \mathsf{TOT} \Longleftrightarrow \exists y \forall z \\, \text{"Machine $x$ doesn't halt on input $y$ within $z$ steps"} $$

---
Tags: complexity-theory, computability
---


# Question
Title: Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls
> We are given $2n - 1$ boxes with a total of $B$ black and $W$ white balls. In the $i$-th, box there are $w\_i$ white and $b\_i$ black balls. It is required to choose $n$ boxes so that, the sum of the white balls is at least $W/2$, and the sum of black balls is at least $B/2$. Solve for $O(n\log{n})$.

What I am currently thinking is this:

Generate some hashtable to be able to track the boxes that we chose.
Sort the boxes by the quantity of the white (in increasing order) balls and chose the last $n$ balls every time keeping them in our hashtable.
Sort by the quantity of the black balls and do the same. Check every time to see if we already chose the box or not. Here comes the problem: Suppose we didn't. Then we can face a situation where we already have $n$ boxes that have in total at least $W/2$ white balls but at the same time, they have in total less than $B/2$ black balls. How can we overcome this problem?

We can't just switch the chosen boxes that have the least number of white balls with the one that have the maximum available number of black balls since the box with white balls can contain significant amount of black balls on its own.

# Answer
> 5 votes
Let $B^\*, B\_1, B\_2, \dots, B\_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^\*$.

Consider the two groups $G\_E = \\{ B^\* \\} \cup \\{B\_i \mid i \text{ is even} \\}$ and $G\_O = \\{ B^\* \\} \cup \\{B\_i \mid i \text{ is odd} \\}$. Clearly $|G\_E| = |G\_O| = 1 + \frac{2n-2}{2} = n$.

Moreover, each of $G\_E$ and $G\_O$ contains at least $W/2$ white balls. This is true since since for each bin not in $G\_E$ (resp. $G\_O$) the previous bin in the sorted order must be in $G\_E$ (resp. $G\_O$). That is, the total number of white balls in $G\_E$ (resp. $G\_O$) is at least as large as the number of white balls not in $G\_E$ (resp. $G\_O$).

Now, total the number of black balls in at least one group $G^\* \in \\{G\_E, G\_O\\}$ must be at least $B/2$. This is easy to see since $\\{G\_E, G\_O \setminus \\{B^\*\\}\\}$ is a partition of the set of bins, and hence the bins in at least one set of the partition (which is either $G\_E$ or a subset of $G\_O$) must contain at least half the black balls.

---
Tags: algorithms, sorting
---


# Question
Title: Designing CFG that accepts $b^m a^n$ ($m ≤ n$)
I am trying to design a CFG that generates the language $\\{a^k b^m a^n a^k \mid m \leq n\\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?

# Answer
> 1 votes
You can write this language as $$ \\{ a^k b^m a^m a^\ell a^k \mid k,m,\ell \in \mathbb{N} \\}. $$ This description easily lends itself to conversion into a context-free grammar.

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


# Question
Title: When our two-state PDA constructed from CFG is non-deterministic PDA?
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule which applied for differing between DCFG and non-Deterministic-CFG also applied here. i mean when we have non-Deterministic δ (delta) implied non-Deterministic edge in our PDA. if my suspicion is right , then for every DCFL exist at least one DPDA with two state. Am i right?

```
R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

```

# Answer
> 1 votes
Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$"

In general PDA is deterministic if there is no configuration in which two different instructions can be applied. So, no two instructions in the same state, the same input symbol, and the same top of stack. Looking back at the CFG that means there are no two productions of the form $A \to a \alpha$, $A \to a \alpha' $, with $\alpha\neq \alpha' $. If there are two such productions, then in configuration $(q,aw,A\gamma)$ \- state $q$, string $aw$ to be read, and $A\gamma$ on the stack, the PDA can make to moves, pushing $\alpha$ or $\alpha'$.

This analysis is not complete. There are two additional instructions $(q,\varepsilon,Z) \mapsto (q,SZ')$ ("on initial stack symbol $Z$ push the axiom of the grammar") and $(q,\varepsilon,Z') \mapsto (f,Z')$ ("when the stack is empty, derivation has ended, move to final state"). Although these are $\varepsilon$ instructions, they can only be applied when none of the CFG rules is applicable (start and end) so they will not cause nondeterminism.

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


title: How to enumerate all Turing machines?

text:
# Question
Title: How to enumerate all Turing machines?
Why is this true: “There are countably many Turing Machines”

In the top answer for this question a description of how to enumerate all Turing machines is given.

It all is clear except for one part: how do you know if a string is a valid encoding of a Turing machine? In step 3 the algorithm needs to check if a string is a valid encoding of a Turing machine. How is this done?

# Answer
A turing machine has a representation as a string. more specifically, you write the **transition function**. to do this, simply think of it as one big table, having in each row two states a letter, and a head transition (L for left or R for right).

Now, encode every entry of the transition function table, and space between them with 3 zeroes (its like a "magic number" so we would know where entries start and end). every entry will contain two numbers - each number representing one state, another bit for the letter and another bit for the head transition (say 1 would be R and 0 is L).

between the two numbers and the other bits put 2 more zeroes, just so you would be able to distinguish between them.

Now, to enumerate on all of the turing machines, just enumerate on all strings and check if they are in the format described above
> 3 votes

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


# Question
Title: Calculate the number of iterations in unusual nested loop
I am trying to calculate the number of iterations of a sequence of nested loops of the form:

\begin{equation} N = \sum\_{j=0}^{j\_T} \sum\_{k=0}^{j} \sum\_{l=0}^{k} \sum\_{n=n\_0}^{n\_T} 1 \end{equation}

where $j\_T\ge 0$ and $n\_T\ge 0$ are known constants.

For $n\_0 = 0$ the case is trivial and can be calculated using the standard procedure (Sum number of times statement is executed in triple nested loop)

The problem is that in my case $n\_0$ is given by a more complex expression:

$$ n\_0 = \begin{cases} 0 &\text{ if } k-2l\lt0,\\ n\_T &\text{ if }k-2l\gt n\_T,\\ k-2l &\text{ otherwise.} \end{cases} $$

Basically, the initial value of $n$ in the last sum is $k-2l$, except when its value is lower/greater than the lower/greater limits of the sum, in which case it gets replaced by the corresponding extreme value of the interval (either $0$ or $n\_T$).

Any ideas?

# Answer
If you want to compute an upper bound of the asymptotic complexity, you can consider the maximum value for the most inside sum. Hence,$\sum\_{n=n\_0}^{n\_T}1 \leqslant n\_T + 1$. Therefore, we will have:

$$ N \leqslant \sum\_{j=0}^{j\_T}\sum\_{k=0}^j\sum\_{l=0}^k (n\_T+1) = \sum\_{j=0}^{j\_T}\sum\_{k=0}^j (n\_T+1) (k+1) = (n\_T+1) \sum\_{j=0}^{j\_T}\sum\_{k=0}^j (k+1) = $$ $$ (n\_T+1)\sum\_{j=0}^{j\_T}\frac{(j+1)(j+2)}{2} = \Theta(n\_T (j\_T)^3) $$

Therefore, $N = O(n\_T (j\_T)^3)$.
> 0 votes

---
Tags: runtime-analysis, loops, summation
---


# Question
Title: Is FACTORIZATION or PRIMES known to be in LOGSPACE
Are the integer factorization and PRIMES known to be in LOGSPACE?

Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.

# Answer
> 7 votes
Factoring is *not known* to be even in $\mathsf{P}$.

Primality is *not known* to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).

# Answer
> 0 votes
If the number is unary, yes, both are logspace. Sum up the 1's to find the number. Use trial division.

If the number is in binary, then logspace is in terms of the length of binary input. It's unknown.

Note that some semi-prime's smallest factor is approximately the square root of the number, which has `O(n)` digits.

Also note that logspace is in P (there are only polynomial state configurations with logspace), so factorization in logspace would imply factorization in P.

---
Tags: complexity-theory, space-complexity, factoring
---