# Question
Title: Why recording non-existent children in the pre-order traversal will differentiate different binary trees?
I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can help me to understand. First of all, two binary trees with different structures can have the same preorder result and that is the first problem in the leetcode solution they are going to solve.

Tree one (T1):

```
      a
     /
    b

```

Preorder result = \[a,b\]

Tree two (T2):

```
      a
       \
        b

```

Preorder result = \[a,b\]

T1 != T2 but they have the same preorder result as you can see above.

Now when they (leetcode) do preorder search they append nulls values ("N") to the result and that solves this problem such that every two different trees must have different result. But I don't understand why this is happening and how can I prove it mathematically that all two different trees must have different preorder result after this change? (Example bellow)

Tree one (T1):

```
      a
     / \
    b   N
   / \
  N   N

```

preorder result = \[a,b,N,N,N\]

Tree two (T2):

```
        a
       / \
      N   b
         / \
        N   N

```

preorder result = \[a,N,b,N,N\]

More Info about this trick can be found in the Cracking the Coding Interview book on page 265:

# Answer
When we change each non-existent child of each leaf node into a special node , a binary tree becomes a **full Binary tree** with **distinguished leaf nodes**.

* A full binary tree is a special type of binary tree in which every node has either two or no children. For example, the logo/favicon of this site is a full binary tree!
* A distinguish leaf node means a node that its value or its representation (as recorded in a tree traversal) alone tells that it is a leaf node. For example, the nodes with value "N" as in LeetCode or the nodes that are represented by a special character "X" in the Cracking the Coding Interview book. (Once those non-existent nodes or NULL nodes are represented or stored, we consider them as real nodes in the corresponding full binary tree.)

For example, the binary tree T1 of two nodes in the question becomes a full binary tree of five nodes, which is also denote T1 in the question. Note that each node in the first T1 becomes an internal node in the second T1 while each non-existent child node in the first T1 becomes a distinguished leaf node in the second T1.

---

**Claim 1**. The number of leaves in a full binary tree is one more than the number of its internal nodes.
**Proof**. Every node is a child of an internal node except the root. Since each internal node has two children, the number of all nodes is one more than double the number of the internal nodes. Subtracting the number of internal node from both sides, we arrive at the claim. $\checkmark$.

---

**Corollary 2**. If we traverse a full binary tree in preorder, then the leaf nodes visited so far are always no more than internal nodes visited so far at each step, except at the end of the traversal when leaf nodes are one more than than the internal nodes.
**Proof**: Use induction since each subtree of a full binary tree is also a full binary tree. Detail is left as an exercise. $\checkmark$

---

**Corollary 3**. Let $F$ be a full binary tree with distinguished leaf nodes. Let $\[u\_0, u\_1, \cdots, u\_{n-1}\]$ be the preorder traversal of $F$, where $n\ge3$ is the number of nodes in $F$. Scanning that list of nodes from left to right, let $d$ be the first index when we have scanned the same number of leaf nodes as the number of internal nodes. Then

* $\[u\_1, \cdots, u\_d\]$ is the preorder traversal of the left subtree of $F$ and
* $\[u\_{d+1}, \cdots, u\_{n-1}\]$ is the preorder traversal of the right subtree of $F$.

**Proof**. Since leaf nodes are distinguished, we know whether each node is a leaf node or an internal node by looking at its value/representation in that list. This corollary follows from Corollary 2, noting that the first node visited, $u\_0$, the root node is an internal node. $\checkmark$

---

**Claim 4**. A full binary tree with distinguished leaf nodes is determined uniquely by the result of its preorder traversal.
**Proof**.

* Sure if the unknown full binary tree is a single-node tree.
* Otherwise, Corollary 3 shows that we can recover the unknown full binary tree recursively given its preorder traversal. $\checkmark$

---

What LeetCode or Cracking the Coding Interview book does is expanding a given binary tree into a full binary tree by changing the non-existent children as distinguished leaf nodes. Given a preorder traversal of that full binary tree with distinguished leaf nodes, we can recover that full binary tree, thanks to Claim 4. From that full binary tree, we can recover the given binary tree by removing all leaf nodes.

Since we can recover the given binary tree from the preorder traversal of its corresponding full binary tree, different binary trees must lead to different preorder traversal of their corresponding full binary trees.

---

**Exercise 1**. What happens to the postorder traversal of a binary tree?

**Exercise 2**. What happens to the inorder traversal of a binary tree?
> 1 votes

---
Tags: algorithms, trees, binary-trees, graph-traversal
---


# Question
Title: Is there a problem that had exponential time complexity but later was proven to be solvable in polynomial time?
Pretty much the title. I watched a video talking about P vs NP and it mentioned that the event that sparked this entire debate was the fact that some exponential time problems were shown to be solvable in polynomial time. So here I am hunting for some examples so that I can dive deeper into how they were cleverly changed.

# Answer
Dantzig's simplex algorithm to solve linear programming problems is exponential in the (extremely unlikely) worst case, the above article cites several polynomial algorithms.
> 2 votes

---
Tags: complexity-theory
---


title: Number of comparisons for mergesort

text:
# Question
Title: Number of comparisons for mergesort
In their book *An introduction to the Analysis of Algorithms*, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C\_N$ the number of compares that Mergesort uses to sort $N$ elements, and come up with the recurrence relation $$ C\_N = C\_{\lfloor N/2 \rfloor} + C\_{\lceil N/2 \rceil} + N $$ for $N \geq 2$, with a base case of $C\_1 = 0$. When $N$ is a power of 2, this becomes $$ C\_{2^n} = 2C\_{2^{n-1}} + 2^n $$ for $n \geq 1$, with a base case of $C\_1 = 0$. They solve this recurrence, thus deducing that $$ C\_N = N\lg N $$ whenever $N$ is a power of 2. At this point, they claim that

> the theorem for general $N$ follows from \[the original recurrence\] by induction.

The claimed theorem states that $C\_N = N\lg N + O(N)$ (for all $N$).

How does the theorem follow by induction after proving the special case in which $N$ is a power of 2?

# Answer
> 1 votes
The inductive proof doesn't actually use the formula $C\_N = N\lg N$ for $N = 2^n$. Rather, once we know that the solution is about $N\lg N$, we can just prove it by induction, as I show below. But first, let me comment that it is easy to prove by induction that $C\_N$ is monotone, and so conclude that $C\_N = \Theta(N\log N)$, by approximating $N$ above and below by powers of 2.

Let's prove that $C\_N \geq N\lg N$ by induction. The base case trivially holds. For the induction step to hold, we need the following to hold for all $N \geq 2$: $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \geq N\lg N. $$ The function $f(x) = x\lg x$ is convex, and so satisfies $$ f(x\_1) + f(x\_2) \geq 2f\left(\frac{x\_1+x\_2}{2}\right). $$ In our case, we take $x\_1 = \lfloor N/2 \rfloor$, $x\_2 = \lceil N/2 \rceil$, and $(x\_1+x\_2)/2 = N/2$, concluding that $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \geq N \lg \frac{N}{2} + N = N\lg N. $$

Similarly, let's prove that $C\_N \leq N\lg N + N - 1$ by induction. The base case trivially holds. For the induction step to hold, we need the following to hold for all $N \geq 2$: $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lfloor \frac{N}{2} \right\rfloor - 1 + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + \left\lceil \frac{N}{2} \right\rceil - 1 + N \leq N\lg N + N - 1. $$ After some cancellation, this is the same as $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \leq N\lg N + 1. $$

Recall now the entropy function $h(p) = p\lg(1/p) + (1-p) \lg(1/(1-p))$. We have $$ h\left(\frac{\lfloor N/2 \rfloor}{N}\right) = \frac{\lfloor N/2 \rfloor}{N} \lg \frac{N}{\lfloor N/2 \rfloor} + \frac{\lceil N/2 \rceil}{N} \lg \frac{N}{\lceil N/2 \rceil} = \lg N - \frac{\left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil}{N}. $$ Substituting this, our inequality is equivalent to $$ N\lg N - Nh\left(\frac{\lfloor N/2 \rfloor}{N}\right) + N \leq N\lg N + 1, $$ or in other words, $$ h\left(\frac{\lfloor N/2 \rfloor}{N}\right) \geq 1 - \frac{1}{N}. $$ If $N$ is even then the left-hand side is $1$, and so the inequality clearly holds. If $N=2M+1$ is odd, where $M \geq 1$, then $\frac{\lfloor N/2 \rfloor}{N} = \frac{M}{2M+1} = \frac{1}{2} - \frac{1/2}{2M+1} = \frac{1}{2} - \frac{1}{2N}$, and so it suffices to prove the inequality $$ h(1/2 - x) \geq 1 - 2x. $$ Now $h(1/2 - x) - (1-2x)$ is concave and vanishes at $x=0$ and $x=1/2$, hence must be nonnegative for all $x \in \[0,1/2\]$.

# Answer
> 0 votes
You can merge two sorted arrays with a total of N items to one sorted array with at most (N-1) comparisons. To be exact, in N-k steps if the k largest elements are in the same of the two arrays.

We can show be induction that for every k, if N \<= 2^k then any array of N elements can be sorted with N * k comparisons. This is obviously true for k=0 and k=1. Let N \<= 2^(k+1). We can split the array into two sub arrays of length L, R \<= 2^k with N=L+R. By inducting, the sub arrays can be sorted with Lk and Rk comparisons, for a total of (L+R)k = Nk comparisons. Merging the two sorted arrays can be done in less than N comparisons, for a total of N(k+1) comparisons qed.

So the number of comparisons is at most N * ceil(log N).

Someone might want to check if the number of comparisons can be slightly reduced by splitting a large array in the best way. For example if N=3 x 1024 splitting into 1024 and 2048 item subarrays, sorting one in 1024x10 and the other in 2048x11 steps, instead of splitting into 2x1536 items each sorted in 11x1536 steps.

# Answer
> 0 votes
I think the number of comparisons is minimised by splitting an array into sub arrays in the following way:

Let N = 2^k + j, 0 \<= j \<= 2^k.

If j \<= 2^(k-1) then split into subarrays of size 2^(k-1) and 2^(k-1) + j. If j \>= 2^(k-1) then split into subarrays of size j and 2^k.

The number of comparisons is at most (k+1)N + 1 - 2^(k+1).

---
Tags: asymptotics, sorting, mergesort
---


# Question
Title: Given an array of n points of the form (x,y), the distance between two points (x1,y1) and (x2,y2) is defined as min(abs(x1-x2), abs(y1-y2))
We need to find mth smallest possible distance by considering all possible pairs. I solved this problem by considering all possible pairs and maintaining a max priority queue. If the max priority queue size is less than m I push the current distance into it. Otherwise, if the size of the priority queue is greater than equal to m I check whether top of priority queue is greater than it. If so, I pop it and push this distance. The time complexity of this solution seems to be O(N^2 logn) while space complexity O(m). Can we do better than this? Especially can we do this in O(1) extra space.

# Answer
> 0 votes
There is a $O(n \log n)$ solution by divide and conquer, see for example here for Euclidean distances (shouldn't make much of a difference for this problem).

---
Tags: algorithms, data-structures
---


# Question
Title: Why was the fast inverse square root algorithm so ingenious?
In 2005 ID software open source the game Quake 3 Arena. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root.

The easy way to calculate the inverse of a square root being

```
float y = 1 / sqrt(x);

```

But then again this functionality has already been figured out and can be used with the `#include <math.h>` directive.

The code from the game being...

```
 float InvSqrt(float x){
    float xhalf = 0.5f * x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

```

So what exactly is the purpose of calculating the inverse of a square root in a non-standard way. Also, why would a game engine be interested in calculating the inverse of a square root anyway?

# Answer
Inverse square root is used a lot for vector normalisation :

$$xn = \frac{x }{ \sqrt{x^2 + y^2 + z^2}}$$

Which has many uses in computer graphics, such as calculating illumination.

With a traditional FPU, even a good one, this is a very time consuming operation : the multiplications and additions are fast (and some can be paralleled) but division is slow (tens of cycles), square root is slower (or just as slow as division).

$\frac{1 }{ \sqrt{x}}$ can be calculated directly (instead of square root then division) by using the Newton-Raphson root finding method, that converges quite fast with this function.

While floating-point units offers great precision, computer graphics don't need that much, as everything is constrained into a few thousands pixels and hundreds of colours hues.

So, here is the need of a quick algorithm that gives a good enough value. And this is the brilliant solution.

There are two parts :

```
float xhalf = 0.5f * x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1);
x = *(float*)&i;

```

This first part calculates an approximate value, it does floating point calculations using integers, using some tricks. Floating point numbers have a exponent part 2^N and a mantissa between 1.0 and 1.9999. An integer shift does something like a square root for the exponent part ($\frac{1 }{ \sqrt{2^N}} = 2^{-N/2}$) : This is what does "-(i \>\> 1)" part above. The 0x5f3759df constant does a good enough interpolation for the mantissa.

```
x = x*(1.5f - xhalf*x*x);
return x;

```

The second part is a application of the Newton-Raphson algorithm, to add more precision to the result. It can be repeated for even more accurate results. But, again, for graphics, it's good enough.
> 2 votes

# Answer
What you can take away from this: When you are given a problem, it is often possible to solve the problem, without solving obvious sub-problems. Like here, where you can calculate 1/sqrt(x) significantly faster than calculating the square root, and dividing 1 by the square root. ( On many implementations it is actually so fast, if you need a square root, the fastest known way is to calculate 1/sqrt(x) with this method and multiplying by x).

Another problem: Determine the number of primes from 1 to 10^20. The obvious way is finding primes and counting them. Not much slower than O(N). But who said we want to know the primes? Nobody said that. What we want is *the number* of primes. And that can be found in about O(N^(2/3)). (There are two simple algorithms that calculate the number of primes \<= N in O(N / log N) and O(N / log^2 N)).

Simpler case: we want the 10 largest elements of an array. Obviously you sort it and take the last 10 elements. But nobody asked you to sort the array, and you can find the largest 10 elements a lot faster.
> 2 votes

# Answer
A simple reason for wanting this non-standard way is to think about how many operations you would need to do in finding sqrt(x), and by extension 1/sqrt(x).

One approach to finding sqrt(x) is as follows: you have to establish a lower bound, an upper bound, and a guess. You can start with lower bound is 0, upper bound is max(x,1), and your guess can be any number between your lower and upper bounds. You could choose a default guess "g" that's the minimum of 2^n for some fixed number n and the average of your bounds. Now you need to compute g^2 and compare that with x and adjust a lower or upper bound accordingly and repeat the process. Next update g and repeat. Do this loop over and over again until g^2 is sufficiently close to x. And then you can compute 1/g to get 1/sqrt(x).

How many times will you have to do this loop? If you got a lucky number, maybe less than a handful. If you got an unlucky number, 10s or even 100s of times. Clearly this is rarely if ever as quick as the fast inverse square root function.

Why would a game engine need this? Games use graphics, and graphics use the pythagorean theorem for computing distances, which implies the use of square roots.
> 2 votes

# Answer
Why would you need 1 / sqrt(x) ?

If you try calculating sqrt(x) and 1 / sqrt(x) using Newton iteration, you’ll find that the first requires a division in each iteration step, while the latter can be done using only multiplications. And multiplications are _ a lot\_ faster than divisions. So 1 / sqrt(x) is *a lot* faster to calculate than sqrt(x) using Newton iteration. So much faster that on many processors x * sqrt(1/x) is faster to calculate than sqrt(x).

Sometimes you need y / sqrt(x), so you change this to y * sqrt(1/x). x^1.5 is x^2 * sqrt(1/x). y / sqrt(x^1.5) = y * (1 / sqrt(x^3)). Each of these is much faster to calculate.

Note that a similar method allows calculating 1/x using Newton iteration without any divisions.
> 1 votes

---
Tags: algorithms, algorithm-analysis, software-engineering, c
---


# Question
Title: Checking whether given measures qualify as computational resources
Do the following measures qualify as computational resources?

1. number of even-numbered states that the machine $M$ visits on input $x$
2. number of times that the machine $M$, when run on input $x$, rewrites symbols on the tape

# Answer
You haven't defined what you mean by a computational resource, but I'll answer the question using the definition by the Blum axioms. To paraphrase the Wikipedia page in the notation here, a *computational resource* is a partial computable function $\Phi$ such that

1. $\Phi$ takes two arguments -- a Turing machine and an input word -- and evaluates to a natural number,
2. $\Phi(M, w)$ is defined iff $M(w)$ is, and
3. given $M, w, k$ it's decidable whether $\Phi(M, w) = k$.

In this formalism your first example is not a computational resource (it doesn't satisfy the last axiom, by a reduction from the halting problem), but the second one is (it's decidable whether a given Turing machine will rewrite at least one more symbol from a given configuration, since if it doesn't, it will soon enter an infinite loop).
> 1 votes

# Answer
"Computational resource" is a bit of an open-ended notion, but it always signifies a *capacity* for a program to use, control, or inspect something that is external to the program itself.

According to this understanding your suggestions are *not* computational resources. They are closer to something like "observations about the behavior of the program" or "analysis of how the resource is used". To make the contrast more explicit:

1. The tape is a resource (namely mutable state).
2. Measuring how much tape has been used by a machine constitutes *analysis* of its space complexity, i.e., how much of the available resource has actually been used.

Your suggestions are more like 2 above. Still more explicit:

1. The water supply in your house is a resource available to you.
2. The amount of water you use is not a resource, it is a measure of your water-complexity.
3. How much water you used on odd-numbered days is still just a measure of your water-complexity, albeit a strange one.
> 1 votes

---
Tags: computability
---


# Question
Title: In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?
This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result in a 'yes' from the solver. For subset-sum, this would be inputs that do have a subset that sums to T.

My question is this: do inputs that result in a 'no' from the solver matter at all to the P=?NP problem? That is if you built an algorithm for subset-sum that runs in P time for every 'yes' input, would you have proved P==NP? OR, would you need to have an algorithm that runs in P time for EVERY input to subset-sum to have such a proof?

NOTE: I say you would have proved P==NP because subset-sum is NP-Complete and so all NP problems reduce to it in P time.

# Answer
> 2 votes
From the paper:

> We say that $M$ runs in polynomial time if there exists $k$ such that for all $n$, $T\_M(n) \leq n^k + k.$

which means that after $T$ runs for $n^k + k$ steps and hasn't accepted, it can reject because it would have already gone into the 'accept' state if the word were in the language. So 'no' answers are trivially dealt with by such an algorithm.

---
Tags: complexity-theory, p-vs-np, subset-sum
---


# Question
Title: Best algorithm for solving $A[i] + B[j] = m$
Suppose $A$ and $B$ are arrays of real numbers of length $n$, and $M$ is another real number. One algorithm for finding indices $i$ and $j$ such that $A\[i\] + B\[j\] = M$ is to comparison-sort $B$ and run binary search with argument $M - A\[i\]$ on it $n$ times, which gives an $O(n\log n)$ algorithm. The source I have claims that this is "the best" algorithm for solving this problem. Why is this the best?

I think by best it means in terms of worst-case time complexity, i.e. its worst-case time complexity is better than any other algorithm, or equivalently, the worst-case time complexity of any algorithm solving this problem is $\Omega(n\log n)$.

Is this somehow related to theory of computation? The source is not famous that's why I won't mention its name. I guess we should also pay attention to the fact that the only tool we have is comparison so maybe the lower bound $\Omega(n\log n)$ for the worst-case of comparison-sort is somehow going to help us.

# Answer
> 2 votes
The kind of algorithm that you consider can be formalized in the algebraic decision tree model. In this model, there is an $\Omega(n\log n)$ lower bound on solving the *set intersection* problem, which is equivalent to your problem. See for example lecture notes of Jeff Erickson.

---
Tags: algorithms, time-complexity
---


# Question
Title: Does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that an NPC problem could have polynomial time algorithms on *almost* any input?
I do not have too much background in complexity theory, so please feel free to let know if my question is ill defined.

My question is, does $\mathcal{P}\neq \mathcal{NP}$ preclude the possibility that an NPC problem could have polynomial time algorithms on *almost* any input?

I am thinking something along the lines of the simplex algorithm; while the simplex algorithm takes exponential time in worst case, its complexity is polynomial assuming smoothed analysis.

Is it possible that $\mathcal{P}\neq \mathcal{NP}$ and there exists a polynomial time algorithm $P$ for an NPC problem that, while is exponential in worst case, is "smoothed-polynomial"/polynomial on almost all inputs?

# Answer
> 2 votes
Russell Impagliazzo described five possible worlds in his classic paper A personal view of average-case complexity. In one of them, Heuristica, P is different from NP, but NP is easy on average (in some specific technical case).

Recent work in meta-complexity has been aiming at ruling out Heuristica. See for example recent work of Shuichi Hirahara.

---
Tags: complexity-theory
---


# Question
Title: What are the differences/relationship between 2D Turing Machines and Cellular Automata
I have been reading up on 2D Turing machines on wolframscience and I am kind of confused about what exactly is the relationship between 2D Turing machines (like Paterson's worm and Langton's Ant) and Cellular Automata. I understand that they are both defined pretty differently but I keep seeing references between one and the other.
For example, this article regarding Langton's Ant suggests that "the ant can simulate cellular automata and is thus computationally universal." Why is this true?
Any additional resources or general guidance for this would be great. Thanks in advance!

# Answer
> 0 votes
In a cellular automaton, every cell on the lattice is a finite state automaton that updates its state at each time step based on the prior state of itself and its neighbors. In other words, all cells are treated as "active" and capable of changing state simultaneously in parallel, although some may be in stable states where they will remain, at least until some of their neighboring cells change state.

A 2D Turing machine, however, just like its one-dimensional counterpart, consists of a *passive* lattice or tape of cells, and a (usually) single "head" (such as the "ant" in Langton's Ant) which can move around on the lattice and modify both its own internal state and the state of the cell at its current location. The lattice cells themselves, however, are only able to *store* a state, but can only *change* state in the presence of the head.

There is, of course, a rather straightforward and natural way of "embedding" a 2D Turing machine (2DTM) in a cellular automaton (CA). Basically, instead of having a single head that *moves* on the lattice, you equip each CA cell with enough possible states to let it store both every possible state of the head (plus one extra state for "head not present") as well as every possible state of a 2DTM lattice cell. (So, for a 2DTM with $m$ cell states and $n$ head states, you end up with a CA with $m(n+1)$ states per cell.) And then you define the state transition rules of the CA so that, whenever the head in the 2DTM would move to a different cell, the CA cell currently storing its state transitions to a "head not present" state, and the neighboring cell which the head would move into transitions into a state encoding the new state of the head. So, in effect, instead of a single active finite state machine "head" moving over a passive lattice, you have a lattice filled with active finite state machines cooperating in such a way as to pass the *role* of being the head around.

Thus, a CA can simulate a 2DTM in a direct manner, with each CA time step simulating one 2DTM time step and each CA cell storing the state of one 2DTM lattice cell (plus, possibly, the state of the head). The only inefficiency in this simulation is that the CA cells typically need a lot more states than the 2DTM cells in order to allow them to simulate the 2DTM head.

On the other hand, for a 2DTM to simulate even a single time step of a general CA, the head must somehow visit every cell on the lattice that might require a state update, carry out those updates (which typically requires also examining all neighboring cells) and then return to its starting point. This requires a lot of time, making simulating a CA by a 2DTM a rather slow process.

That said, this simulation *can* still be done in polynomial time: starting from a finite collection of active CA cells (i.e. ones not in a stable quiescent state) on a 2D lattice, the number of such cells can grow at most as a quadratic function of time, and so a 2DTM simulating such a CA needs to spend at most a quadratically growing number of steps to simulate each CA time step. So, if you follow the standard complexity-theoretic practice of treating any polynomial-time reduction as efficient, then a 2DTM can in fact "efficiently" simulate a CA.

(In particular, the way a 2DTM can simulate a CA isn't really all that different from how a real-world computer — also consisting of a single active CPU and a large number of passive memory cells — would simulate one. So the fact that we can practically simulate CA on a computer does indicate that, in practice, such simulation isn't *that* inefficient.)

---
Tags: turing-machines, cellular-automata
---


# Question
Title: Given a source and destination, find the path with minimum stress level in a Graph
I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't find any problem with my logic. Maybe I made some implementation mistake during the contest (I'm not sure). But now I have my solution and I don't know if it's correct or not. I have tried it on multiple graphs and it gives correct answer on all of them. But yes a single case is enough to prove an algorithm wrong. So below I provide the details. Please help me validate the solution.

**Problem** Given an **un-directed graph (can be disconnected)** with **N nodes** and **E edges**. The **stress level** of the path is defined as the **maximum weight of an edge present on this path**. Given a source **U** and destination **V** you need to tell the **minimum stress level** from node U to node V. **If you cannot reach V from U, return -1.**

**My Solution**

```
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

int minStressLevel(vector<vector<pair<int, int> > > &adj, set<pair<int, int> >
&visited, int src, int dst) {
    if(src == dst) return 0;

        int ans = INT_MAX;
        for(auto to: adj[dst]) {
        int v = to.first;
        int w = to.second;

        if(!visited.count({dst, v})) {
            visited.insert({dst, v});
            visited.insert({v, dst});
            ans = min(ans, max(minStressLevel(adj, visited, src, v), w));
        }
    }

    return ans;
}

int32_t main() {
    int t;
    cin >> t;

    for(int d = 0; d < t; d++) {
        int n, e;
        cin >> n >> e;

        vector<vector<pair<int, int> > > adj(n + 1);

        for(int i = 0; i < e; i++) {
            int u, v, w;
            cin >> u >> v >> w;

            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector<int> dp(n + 1, INT_MAX);
        set<pair<int, int> > visited;

        int source, destination;
        cin >> source >> destination;

        int ans = minStressLevel(adj, visited, source, destination);
        cout << "Case #" << d << ": ";
        if(ans == INT_MAX) cout << -1 << endl;
        else cout << ans << endl;
    }
}

```

**Explanation** The solution is based on this recurrence: minStressLevel(V) = min{max(minStressLevel(K), edge\_weight(K, V))} over all neighbours K of V.

I keep a set of pairs to keep track of what edges have been visited so that I don't get into infinite loops. **This is different than a simple Breadth First Search where we stop once we discover a vertex and do not visit it again.**

**Time Complexity** I think time complexity is O(E), where E is the number of edges. **Constraints** N \<= 1e5 E \<= 1e5 edge\_weight \<= 1e9

# Answer
> 1 votes
I don't think your algorithm is correct, but keep in mind that I haven't read your code carefully; consider replacing the code with pseudocode.

One solution that could work in $O(m \log m)$ time is to binary search for the stress level and do BFS on only edges with lower weight.

---
Tags: algorithms, graphs, dynamic-programming, recurrence-relation, dijkstras-algorithm
---


# Question
Title: What empirical evidence do we have for or against a correlation between fault density and LOC?
LOC = lines of code

KLOC = Thousand lines of code

Fault (or defect) density = number of reported bugs per line of code.

Software artifact = function, class, module

Reading research papers on fault density and fault prediction, it seems a bit hard to get an overview, because there are lots of studies, and lots of different technologies used, both statistics and machine learning.

The rational behind a correlation between fault density and LOC is that with higher LOC of a software artifact comes higher complexity, and it gets harder for the programmer to change the code; changeability decreases, which leads to more bugs. Note that this is not a question about a correlation between fault density and complexity, even if there might be such a connection too.

I guess what I'm looking for is a study or a book that has an overview over current research in this topic. :)

Here's one study claiming there is such a correlation: https://www.gwern.net/docs/dual-n-back/1997-hatton.pdf

Here's another one claiming there isn't: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.452.8933&rep=rep1&type=pdf

Edit: Google Scholar has an option to search for only review articles, so I'll dig into this. Will post anything interesting.

Edit 2: One review article: https://media.neliti.com/media/publications/90270-EN-a-systematic-literature-review-of-softwa.pdf

> However, even though various defect prediction methods have been proposed, but none has been proven to be consistently accurate (Challagulla et al., 2005) (Lessmann et al., 2008). The accurate and reliable classification algorithm to build a better prediction model is an open issue in software defect prediction. There is a need for an accurate defect prediction framework which has to be more robust to noise and other problems associated with on datasets

And another: https://romisatriawahono.net/lecture/rm/survey/software%20engineering/Software%20Fault%20Defect%20Prediction/Radjenovic%20-%20Software%20fault%20prediction%20metrics%20-%202013.pdf

# Answer
> 2 votes
Not an easy question to answer, because LOC can mean many different things:

* A large function
* A large class (or module in FP)
* A large library
* A large file
* A large code-base

In some of these cases (function and class), LOC can be a proxy for complexity \[citation needed\]. You can also normalize complexity based on size.

The Software fault prediction metrics: A systematic literature review paper contains a section on LOC in fault prediction research, which I will quote fully below. The conclusion is in the last sentence:

> the overall effectiveness of the LOC metric was estimated as moderate

The comparison to other metrics is the interesting part, however.

(A description of the different metrics is available in appendix C.)

The first metrics are complexity measures that work on all languages. The middle part is metrics only applicable to object-oriented code. The last part is metrics that relate to process and change in the code.

It's interesting to note the effectiveness of metrics in the pre- and post-release scenarios. LOC is noted as being more predictive before the release.

Full section:

> 4.3.1. RQ2.1: Are size metrics useful for fault prediction?
>
> The simplest, the easiest to extract and the most frequently used metric, i.e. LOC, is still being discussed to this day. There are many studies investigating the relationship between lines of code and number of faults. The simplest studies have ranked the modules according to their size to find out whether a small number of large modules are responsible for a large proportion of faults. E.g. in Zhang \[151\] three versions of Eclipse were used to investigate pre-release and post-release ranking ability of LOC at the package level. This study showed that 20% of the largest modules were responsible for 51–63% of the defects.
>
> Ostrand et al. \[130\] used the negative binomial regression model on two large industrial systems. In the simple model, using only LOC, the percentage of faults, contained in the 20% of the files that were the largest in terms of the number of lines of code, was on average 73% and 74% for the two systems. In a richer model, where other metrics were used, the top-20% of files ordered by fault count contained, on average, 59% of the lines of code and 83% of the faults. The top-20% of files contained many large files, because the model predicted a large number of faults in large files. In analyzing which files were likely to contain the largest number of faults relative to their size, they used the model’s predicted number of faults and the size of each file to compute a predicted fault density. The top-20% of files contained, on average, only 25% of the lines of code and 62% of the faults. Sorting files by predicted fault density was not as effective as sorting files according to fault count at finding large numbers of faults, but it does result in considerably less code in the end.
>
> Fenton and Ohlsson \[84\] investigated, among many hypotheses, the Pareto principle \[28\] and the relationship between size metrics and the number of faults. They used a graphical technique called the Alberg diagram \[127\] and two versions of a telecommunication software. As independent variables LOC, McCabe’s cyclomatic complexity and SigFF metrics were used. In pre-release 20% of the modules were responsible for nearly 60% of the faults and contained just 30% of the code. A replicated study by Andersson and Runeson \[59\] found an even larger proportion of faults, in a smaller proportion of the modules. This result is also in agreement with \[130,151\]
>
> Fenton and Ohlsson also tested the hypothesis of whether size metrics (such as LOC) are good predictors of pre-release and post-release faults in a module and whether they are good predictors of a module’s pre-release and post-release fault density. They showed that size metrics (such as LOC) are moderate predictors of the number of pre-release faults in a module, although they do not predict the number of post-release failures in a module, nor can they predict a module’s fault density. Even though the hypothesis was rejected, the authors concluded that LOC is quite good at ranking the most fault-prone modules. Andersson and Runeson, on the other hand, got varying results. The first two projects did not indicate any particularly strong ranking ability for LOC. However, in the third project, 20% of the largest modules were responsible for 57% of all the faults
>
> Koru et al. \[35,104\] reported that defect proneness increases with size, but at a slower rate. This makes smaller modules proportionally more problematic compared with larger ones
>
> In \[34,59\], it is noted that relating size metrics to fault density may be misleading, as there will always be a negative correlation between size metrics and fault density, because of the functional relationship between the variables \[47\]. However, no studies using fault density as dependent variable were excluded from the review because we wanted to represent the entire research field. In this section, studies using fault density are compared with LOC size ranking ability to assess the LOC predictive capabilities
>
> To some extent, size correlates with the number of faults \[130,151,154,112,83,78\], but there is no strong evidence that size metrics, like LOC, are a good indicator of faults \[84,59\]. A strong correlation was observed between the size metric LOC and fault proneness in pre-release and small studies, while in post-release and large studies, only a weak association was found (Table 5). This may indicate that studies with lower validity (smaller data sets) gave greater significance to the LOC metric than studies with high- er validity (larger data sets). Therefore, the reliability of the studies in terms of study quality assessment was taken into account and the overall effectiveness of the LOC metric was estimated as moderate.

So there you go. :)

# Answer
> 0 votes
There are several factors that affect both number of faults and lines of code, but sometimes in opposite directions.

You can increase the number of lines of code by writing code that is simple, clear, contains self-tests, is well-documented, handles border cases correctly etc, and this will be more code with fewer bugs.

You can increase the number of lines of code by not understanding the problem and writing overly complicated code that just works by coincidence in many cases, and any bug found creates changes that make the code even bigger and worse. So you will have more code with more bugs.

And keep in mind that we can never correlate between code size and errors - we can only correlate between code size and *detected* errors! Which are also related in a strange way. More errors will produce more detected errors. But more detected errors will lead to errors getting fixed and therefore the number of errors going down.

---
Tags: statistics
---


# Question
Title: Algorithm to find the path with minimum bending points on a square grid board
Let's suppose we have a square grid board like the one shown in the picture below:

I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) between two given squares ("Start" and "Finish"). The board has some impediments or broken squares on it (Black squares).

I tried to run a BFS algorithm and find all of the minimum cost paths and then pick up the one with minimum bending points, but this won't give us the optimal answer.

Is there a way to efficiently solve this problem?

Motivation: I was trying to solve a computer game using A\* algorithm, and I figured out I can use the solution to this problem as a heuristic function to solve the game.

# Answer
> 1 votes
Create an undirected weighted graph $G$ with two vertices $h\_c$, $v\_c$ for each (non-obstacle) cell $c$ of the grid. Intuitively $h\_c$ encodes entering $c$ from the left or right and $v\_c$ encodes entering $c$ from the top or bottom.

For each pair of horizontally adjacent cells $c, c'$ add the edge $(h\_c, h\_{c'})$ with weight $0$. For each pair of vertically adjacent cells $c, c'$ add the edge $(v\_c, v\_{c'})$ with weight $0$. For each cell $c$, add the edge $(v\_c, h\_c)$ of cost $1$ (this encodes changing direction).

If the starting cell is $s$, add a new vertex $s^\*$ along with the edges $(s^\*, h\_s)$ and $(s^\*, v\_s)$ of cost $0$. Similarly, if the target cell is $t$, add a new vertex $t^\*$ along with the edges $(h\_t, t^\*)$ and $(v\_t, t^\*)$ of cost $0$.

The path with the minimum number of bends in the grid is the one corresponding to the shortest path between $s^\*$ and $t^\*$ in $G$. Such a shortest path can be found in time $O(n)$ where $n$ is the number of cells (since weights are non-negative and bounded by a constant, there are $2n+2$ vertices, and each vertex has degree at most $4$).

---
Tags: algorithms, graphs, search-algorithms, shortest-path, square-grid
---


# Question
Title: Minimize the expected value of money spent on boxes until the prize is found
There are $n$ closed boxes and one and only one box of them contains a prize. The $i$-th box has probability $p\_i$ of containing a prize. A player must pay $c\_i$ coins to open the $i$-th box. The player must open boxes until the prize is found, then the game ends. Find the optimal box opening strategy that minimizes the expected money spent before obtaining the prize.

For example, let there be two boxes: $p\_1 = 0.8$, $p\_2 = 0.2$, $c\_1 = 3$, $c\_2 = 2$. There are two possible variants: 1-2 and 2-1 (a player can open box 1 or box 2 first).

Expected value of spent money for 1-2 order is $0.8\times3+0.2\times(3+2)=3.4$ coins.

Expected value of spent money for 2-1 order is $0.2\times2+0.8\times(3+2)=4.4$ coins.

Therefore 1-2 order is better.

Is there an algorithm that solves this problem faster than brute force $O(n!)$? What is the optimal algorithm for solving this task?

# Answer
> 4 votes
The algorithm is simple. Just sort the boxes from highest $p/c$ value to lowest. This takes $O(n \log n)$ time.

The proof is a little more complicated.

Consider a box-picking strategy $S$, and number the boxes in the order that strategy $S$ picks boxes. The expected cost of picking boxes in this order is $c\_1+(1-p\_1)c\_2 + (1-p\_1-p\_2)c\_3 + \cdots$. We definitely incur a cost of $c\_1$ to open the first box, then we have a $1-p\_1$ probability of having to open the second box and pay $c\_2$, and a $(1-p\_1-p\_2)$ probability that the prize wasn't in either of those boxes, and so on.

A necessary (though not obviously sufficient) condition for a strategy to be optimal is that we can't swap the order of two consecutive box picks and get a better strategy. If we compare the expected cost of strategy $S$ and the expected cost of strategy $S\_i$, where box $i+1$ is picked before box $i$, we find that these costs differ in only two terms, corresponding to the costs associated with picking boxes $i$ and $i+1$.

For strategy $S$, these terms are $$(1-p\_1-p\_2-\cdots-p\_{i-1})c\_i + (1-p\_1-p\_2-\cdots-p\_{i-1}-p\_i)c\_{i+1}$$

For strategy $S\_i$, these terms are $$(1-p\_1-p\_2-\cdots-p\_{i-1})c\_{i+1} + (1-p\_1-p\_2-\cdots-p\_{i-1}-p\_{i+1})c\_i$$

If we eliminate the $(1-p\_1-p\_2-\cdots-p\_{i-1})(c\_i+c\_{i+1})$ component from both sides, we find that strategy $S\_i$ wins if $$-p\_ic\_{i+1} \>-p\_{i+1}c\_i$$

or equivalently, if $$p\_i/c\_i\<p\_{i+1}/c\_{i+1}$$

so strategy $S\_i$ wins if box $i+1$ has a higher $p/c$ value than box $i$.

For a strategy to be optimal, each box must have a $p/c$ value greater than or equal to the next box in picking order. This can be achieved with a simple sort. If all $p/c$ values are distinct, then there is only one possible outcome of this sort, and the resulting order is the single optimal strategy. If there are duplicate $p/c$ values, then we can order boxes with the same $p/c$ value arbitrarily, since (by a variation of the above logic) shuffling boxes within a group of equal $p/c$ value will not change the expected cost of a strategy.

# Answer
> 2 votes
There's a simple dynamic programming algorithm which runs in time $O^\*(2^n)$. For a set $S$, let $C(S)$ be the cost of opening just the boxes in $S$ in the optimal order. Then $C(\emptyset) = 0$ and for $S \neq \emptyset$, $$ C(S) = \min\_{i \in S} \left\[ C(S \setminus \\{i\\}) + p\_i \sum\_{j \in S} c\_j \right\]. $$ You are interested in $C(\\{1,\ldots,n\\})$.

---
Tags: algorithms, optimization
---


# Question
Title: Polynomial-time algorithm for distribution of arbitrary symbols
Is there a polynomial-time algorithm for distribution of clauses of arbitrary symbols (i.e. similar to multiplication distributing over addition)? For simplicity, let's assume the distributive operation is concatenation and the symbols are letters in the English alphabet. For example, the clause `(a b c)` distributed with the clause `(d e f)` would result in: `ad ae af bd be bf cd ce cf`. The clauses need not be the same length, but they are here for simplicity. It's clear that the length of the result grows exponentially with respect to the amount of clauses, but does that mean any algorithm to generate the result must then be in exp-time? Or is there a more efficient way of generating such results?

# Answer
> 1 votes
If the output of the algorithm takes exponential space, then any algorithm must take exponential time. It takes at least N steps of computation even to output N characters (even ignoring the time it takes to figure out what to output), so the length of the output is a lower bound on the running time of the algorithm.

---
Tags: algorithms, time-complexity
---


title: Reader / writer locking algorithm

text:
# Question
Title: Reader / writer locking algorithm
I'm pretty sure there's a textbook solution to this problem, but I haven't figured it out.

I have fixed-size blocks of data arranged in a sequence: block 0, block 1, etc.. There are reader threads that read through the blocks sequentially. There are writer threads that append new data to the empty space in the last block, and then allocate a new block and continue writing if there is overflow.

You can only have one writer at a time, obviously, or they will clobber each other. You can have multiple readers at a time.

I have primitives available to add a read-lock or a write-lock to a block. The system will block until the appropriate lock is available.

I have complete control over the contents of each block. I can add flags, pointers, anything. I can also do copy-on-write and swap in blocks atomically.

So, what algorithm do I use to minimize contention?

The naive algorithm is for readers to get a read lock on the first block before they read, and writers to get a write lock on the first block before they write. A writer will then be able to write safely, but readers will all be blocked. This is essentially a single global lock.

I'm pretty sure there's a better way. What is it?

# Answer
> 1 votes
I *think* you should be able to do it with a single read/write lock and a single atomic integer variable.

Here's what I propose.

The global data:

```
in_last_block : rwlock
last_block : atomic int <- 0

```

A writer thread would look something like this:

```
acquire an exclusive lock on in_last_block
repeat
    write data into last_block
    if the last block is full then
        append a new block
        memory write barrier
        atomic increment last_block <- last_block + 1
until writing is done
release the exclusive block on in_last_block

```

A reader thread would look something like this:

```
current_block <- 0
last_known_block <- atomic read last_block

do
    memory read barrier
    while current_block < last_known_block:
        scan current_block
        current_block <- current_block + 1
    last_known_block <- atomic read last_block
while current_block < last_known_block

acquire a shared lock on in_last_block
    last_known_block <- atomic read last_block
    while current_block <= last_known_block do
        scan current_block
        current_block <- current_block + 1
release the shared lock on in_last_block

```

Intuitively, `in_last_block` protects only last partly-filled (or possibly empty) block. The atomic variable `last_block` records which block is unsafe to read in a lock-free manner.

Then reader threads are allowed to freely do anything before, but not including, the last block. They only must acquire the shared lock in order to read the last block.

Exercises:

* What happens if a writer thread appends something while a scanner thread is between the do/while loop and the shared lock?
* Why are the memory barriers needed?
* Why is a memory barrier *not* needed in the last loop of the reader thread?

---
Tags: algorithms, threads, deadlocks
---


# Question
Title: Can one show NP-completeness by showing a reduction to 3SAT?
The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the other way, i.e., if L $\leq $ 3SAT?

Wouldn't that be one one step way of showing that the language $L$ is in NP-complete?

# Answer
Here is a counterexample to your proof method. The empty language reduces to 3SAT, yet it isn't NP-hard.

If you reduce $L$ to 3SAT, then you can conclude that $L$ is in NP, that's it.
> 2 votes

---
Tags: np-complete, reductions, decision-problem
---


# Question
Title: best and worst case number of key comparisons of an algorithm
Consider the following algorithm:

```
function randomQueries(A, n <- A.size)
if n > 1 then
    p <- n - 1;
    x <- partition(A, p);
    randomQueries(A[0,1,...,x-1], x)
    randomQueries(A[x+1,...,n-1], n-1-x);
    for y = 1 to x do
        for z = x + 1 to n - 1 do
            query(A, y, z);
else if n = 1 then
    query(A,0,0);

```

> partition is Hoare's partition-routine (so after the partition, all keys in A\[0,...,x-1\] are \<= A\[x\] and all keys in A\[x+1,...,n-1\] are \>= A\[x\]. But I think it only really matters that partition performs n key comparisons. Also, query(A, y, z) uses one key comparison.

> Deduce with justification, asymptotically tight bounds for the worst and best case number of key comparisons.

I think the best case is $\Theta(n^2)$; choosing $x=n/2$ each time (which is possible if you arrange the array so that the last element of each subarray visited by the randomQueries function is always the median of the subarray) shows that the best case number $T^{best}(n) \leq n + n/2(n/2-1) + T^{best}(n/2) + T^{best}(n/2-1) \leq n^2 + 2T^{best}(n/2)$ for n large enough, which simplifies to $O(n^2).$ Also, each call takes $n$ key comparisons and there are $\Omega(n)$ calls because as long as $n \> 1,$ there will be a recursive call and each call "removes" one index (x) each time.

Similarly, if one always chooses the last element ($x=\frac{n}2$), the worst case runtime should be at least $n + T^{worst}(n-1)$, which evaluates to $\Omega(n^2).$ I'm not sure how to find an upper bound for the worst case.

# Answer
> 1 votes
Denote by $T(n)$ the number of comparisons on a list of length $n$. Then $T(0) = 0$, $T(1) = 1$, and $$ T(n) = n + T(x) + T(n-1-x) + x(n-1-x) $$ for some value of $x$ that could depend on the array.

Let us prove by induction that $T(n) = n(n+1)/2$, whatever $x$ is. This holds when $n = 0$ and $n = 1$. For $n \> 1$, we have $$ T(n) = n + \frac{x(x+1)}{2} + \frac{(n-1-x)(n-x)}{2} + x(n-1-x) = \frac{n(n+1)}{2}. $$ You can also prove this combinatorially: every two elements get compared, including an element and itself.

---
Tags: algorithms, time-complexity, algorithm-analysis, asymptotics, big-o-notation
---


# Question
Title: NP-completeness of satisfiability of formula over 50 variables
Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?

# Answer
If you have a fixed number of variables, then you have a fixed number of assignments $2^{|\text{vars}|}$, so there's a polynomial time algorithm for checking all possible assignments.
> 3 votes

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


# Question
Title: Encoding a binary sequence with shift in MILP
I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP.

Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x\_0,x\_1,x\_2,x\_3,x\_4,x\_5,x\_6,x\_7$ I want to restrict my MILP program such that it takes up one of the following:
\begin{align} (x\_0,x\_1,x\_2,x\_3,x\_4,x\_5,x\_6,x\_7) & = (0,1,1,0,0,0,0,1)\text{ or} \\ (x\_7,x\_0,x\_1,x\_2,x\_3,x\_4,x\_5,x\_6) & = (0,1,1,0,0,0,0,1)\text{ or} \\ (x\_6,x\_7,x\_0,x\_1,x\_2,x\_3,x\_4,x\_5) & = (0,1,1,0,0,0,0,1)\text{ or} \\ \vdots \\ (x\_1,x\_2,x\_3,x\_4,x\_5,x\_6,x\_7,x\_0) & = (0,1,1,0,0,0,0,1) \end{align}

I understand that the rotation can be easily solved by just extending the sequence. But I find myself creating multiple MILP instances, each instance corresponding to exactly one of the cases. If this is infeasible, why?

# Answer
In constraint programming this particular type of constraint is known as a table constraint. It is generally said to be an existential constraint, since many other constraints can be encoded using a table constraint. As such, it is often better to use the underlying structure when possible (I don't see a way around it in this case), although tables have been proven to be very effective in constraint programming solvers.

To encode a table constraint in MILP, the generally idea is to create a new zero one variable $s$ for every row in the table that signifies whether the row is selected. There are then two kinds of constraints. $$ \sum\_{i \in rows} s\_i = 1 $$

$$ \sum\_{j \in col} table\_{ij}\*s\_i = x\_i ,\forall\_{i \in rows} $$

This is how the MiniZinc constraint modelling language would also encode this constraint for MILP solvers: https://github.com/MiniZinc/libminizinc/blob/master/share/minizinc/linear/fzn\_table\_int.mzn
> 1 votes

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


# Question
Title: Difference between BPP, IP and AM complexity?
I just can't figure out the difference between these three classes of complexity, does anyone know the difference and can explain it in a simple, direct way without too many definitions involved? Thank you very much!

# Answer
> 1 votes
All of these classes can be described as consisting of languages accepted by certain Arthur–Merlin games. In these games, Merlin, an unlimited but potentially dishonest party, tries to convince Arthur, a probabilistic Turing machine, that the input $x$ belongs to the language $L$. We ask that if $x \in L$ then some Merlin convinces Arthur with probability at least $2/3$, and if $x \notin L$ then every Merlin convinces Arthur with probability at most $1/3$.

Without any further limitations, we get the class IP (which equals PSPACE). If we only allow a constant number of rounds of interaction, we get the class AM (it is known that without loss of generality, there are only *two* rounds). If we don't allow any interaction (Merlin gets no chance to speak), then we get BPP.

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: How to find the big O notation of $\log^b x$
How would you determine big O notation for $\log^b x$? I don't think you can simply say $O(\log^b x)$, can you?

If you can, then here is a better question: $x^3 + \log^b x$. How would you know if it's $O(x^3)$ or something else depending on the $b$ value?

# Answer
> 2 votes
> How would you determine big o notation for this? I don't think you can simply do O(log(x)^b) can you?

$\mathcal O\left(\log^b x\right)$ or $\mathcal O\left(\left(\log x\right)^b\right)$ is correct.

> x^3 + log(x)^b

Assuming $b$ is a constant. You always take the fastest growing term in a polynomial. $T(x)=\mathcal O\left(\log^b x\right)$ is called *polylogarithmic time*. In this case, $\mathcal O\left(x^3\right)$ grows faster than $\mathcal O\left(\log^b x\right)$.

You can see a list of different complexities (sorted from lowest to highest) here.

# Answer
> 2 votes
To answer any question about $O(-)$ notation, you need to check the definition, which is that, for functions $f$ and $g$, $f=O(g)$ if, and only if, there are constants $x\_0$ and $k$ such that $|f(x)|\leq k|g(x)|$ for all $x\geq x\_0$.

$O(-)$ is often treated as some fixed hierarchy of functions, "logarithms are $O$(polynomials), polynomials are $O$(exponentials)" and so on, leading students to believe that you can only write $O(g)$ for some very special or very nice functions $g$. This is quite simply not true: the definition allows you to write $O(g)$ for any function of one variable that you want to. For constant $b$, you can write $O(\log^b x)$. Heck, you can write $O\big(\sin\\,(\cos\tfrac{1}{x^2})+3\big)$, if you want to, though you probably never will want that.

# Answer
> 0 votes
A good "rule of thumb" to use with asymptotic notation is: $O(n^n) \> O(k^n) \> O(n^k \log^l n) \> O(n^k) \> O(log^k n) \> O(1)$

So if you have $n^3 + log^b n$, the $n^3$ term will dominate, giving you $O(n^3)$.

# Answer
> 0 votes
Usually in O(f(n)) notation, we well try to find a *simple* function f, and we will try to find one that isn't growing much faster than the left hand side. (So we wouldn't say that n + 3 = O(n^2) usually even though it is completely true). We would probably write that (2 + sin (n^2)) n = O (n), because it's true, it's a simple function, and it is quite close - the left side is *not* little-O(n); it's always between n and 3n.

And it's relatively easy to show that x^3 is NOT O (log^b n) for any b.

In your case, O (log^b n) is perfectly fine. There's nothing that is both simpler and close to log^b n.

---
Tags: asymptotics
---


# Question
Title: Is the first distance that gets assigned to a node in BFS always the shortest distance?
Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$.

I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct distances.

However, I'm not sure if it would still work if $G$ is directed and unweighted. Basically, what I'm asking is this:

Is the first (non-infinity) distance that gets assigned to each node in bfs always the smallest distance from $s$ if our graph is directed and unweighted?

# Answer
> 1 votes
Yes.

You can imagine that instead of pop one node at a time, you can pop all nodes. Then enqueue all unvisited nodes that connected from one of the popped nodes. This imagination does not change the actual algorithm at all.

At the first batch operation, the source node $s$ is popped out. The nodes connected from $s$ are all the nodes of distance 1. They are enqueued.

At the next batch operation, all nodes of distance 1 are popped out and all nodes of distance 2 are enqueued.

At the next batch operation, all nodes of distance 2 are popped out and all nodes of distance 3 are enqueued.

And so on.

The above understanding/reasoning works for undirected graph as well as directed graph.

(Similarly, Dijkstra's algorithm works the same for both weighted undirected graph and weighted directed graph.)

---
Tags: graphs, search-algorithms, directed-graphs, breadth-first-search
---


# Question
Title: Why equality is decidable for regular language but not for $CFL?$
There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$ But also there are infinitely many different $DFA$ exists for same regular language. So why equality of regular is decidable but not for $CFL?$

# Answer
The short (and not very useful) answer is that we can prove that PDA equivalence is undecidable, and we can prove that DFA equivalence is decidable.

It is important to realize that formally, the above is the only mathematically valid "reason". What you are asking is more about the intuition for this result.

The fact that there are infinitely many DFAs and PDAs that represent the same language is not really important, since in checking equivalence, you are given two fixed automata, and you are checking their equivalence.

The fundamental difference between PDAs and DFAs is their *configuration space*: you can represent the current "configuration" of a DFA by simply saying what state of the DFA the run is currently at, and from there you can continue reading the word. That is, the state gives you all the information you need to continue.

In contrast, in a PDA you need to know the state of the PDA as well as the entire contents of the stack, otherwise you might not know how to continue the run. Since the stack is unbounded, the number of possible configurations of a PDA is infinite.

Usually, the "reason" problems become undecidable is that there is some underlying infinite configuration space. This is not mathematically accurate, but it's a good intuition.

Thus, when you're checking the equivalence of two automata, you essentially ask "is there a word that reaches a different configuration in the two automata?" (more precisely, can you reach an accepting configuration in one and not in the other). Now, clearly if there is such a word, then there is also such a word such that the runs of the two automata on it don't repeat their configuration. This is because if a configuration is repeated, you can truncate the word and find a shorter one.

When you apply this reasoning to DFAs $A,B$, you get that they are not equivalent iff there is such a word of length at most $|A|\cdot |B|$. This is due to their finite configuration space. This is actually sufficient to prove that their equivalence is decidable.

When you apply this reasoning to PDAs, you don't really get anything, since the configuration space is infinite. Note that this is **not** sufficient to prove that equivalence is undecidable, but it does suggest that maybe we should look for a proof of undecidability.
> 8 votes

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


title: Validity of proof by contradiction

text:
# Question
Title: Validity of proof by contradiction
I had a doubt in the proof by contradiction technique.

Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a consistent system cannot have a contradiction, so our assumption must be false and the original statement must be true.

The doubt here is, is the proof by contradiction valid if the statement we contradict is the assumption itself. That is I start with wanting to prove q, assume negation q to be true, and then reach q eventually, leading to a contradiction and hence concluding q at the end?

It would be helpful if someone can explain this with the help of a concrete example, if it exists.

# Answer
> 2 votes
There is no problem with assuming $ \neg q$ towards a contradiction and showing that this implies $q$.

Here is an example, adapted from Euclid's proof that there are infinitely many primes.

Let $p$ be a prime number and suppose we want to prove "there exists a prime number larger than $p$". We proceed by contradiction, i.e., we assume that "all prime numbers are smaller than or equal to $p$".

Let $P$ be the set containing all prime numbers and define $x = \prod\_{p \in P} p + 1$. If $x$ is not prime then, by our assumption, there must be some $p^\* \in P$ that divides $x$. However our choice of $x$ ensures that $x \bmod p^\* = 1$ for every $p^\* \in P$. Therefore $x$ is a prime larger than $p$, a contradiction.

# Answer
> 0 votes
I'll add some steps to make it very clear. You want to prove q.

You can take any statement s, then say "either s or not s is true", and then prove "if s is true then q is true" and "if not s is true then q is true". That happens actually quite often; you might have the statement "x ≤ 1" and you can prove that if x ≤ 1 then q is true for some reasons, and if x ≥ 1 then q is true for totally different reasons.

Instead of taking *any* statement s, you can take the statement q itself. Then you say "either q or not q is true". Then you prove "If q is true then q is true" which is very, very obvious, and you prove "if q is not true then q is true". That's just a normal proof, you don't even have to call it "proof by contradiction".

---
Tags: logic, proof-techniques, propositional-logic
---


# Question
Title: A heuristic for finding the vector that is maximally distant from a set of vectors
I have two sets of vectors: `A` and `B`. I want to find the vector `B<sub>i</sub>` in set `B` that is maximally distant from the vectors in set `A`, either by average distance or closest distance. I know that I can accomplish this by comparing every vector `A<sub>i</sub>` in `A` with every vector `B<sub>i</sub>` in `B`, but that will be very costly. It is acceptable for the solution to be approximate. Is there a heuristic algorithm that can solve this problem more efficiently?

# Answer
> 1 votes
Just to answer with some ideas.

If you have too many dimensions, you can use the Johnson–Lindenstrauss lemma to reduce the dimensions while keeping distances approximately the same (some $\epsilon$ away from original distances).

You can find a 3-approximation for the point in $B$ that is farthest away from any point in $A$ (pick any $b' \in B$, then find an $a \in A$ that is farthest away from $b'$, and then pick a $b \in B$ that is farthest away from $a$). This should be a 3-approximation for the farthest $A$-$B$-points.

However, you want to minimize the point in $B$ farthest away from all of $A$, so maybe you can try to find the centroid $c(A)$ and find the point in $B$ that is farthest away from $c(A)$? Note that this only works if *most* points in $A$ are *close* to $c(A)$. You can also try to remove outliers first.

A randomized approach could be to choose e.g. a constant fraction of the points in $A$ and perform the centroid algorithm, and repeat as many times as you see fit. Or you can choose, say $\log |A|$ many points in $A$ and find the point in $B$ farthest away from this set. Repeat as many times as you can.

These are all suggestions where we don't know *anything* about $A$ and $B$. How are they generated? Do they follow some probability distribution? If you use the knowledge you have about these sets, you will very likely get better algorithms.

Finally, you can see if you can use a $k$-d tree to come up with a better algorithm.

---
Tags: sets, clustering, euclidean-distance
---


# Question
Title: Algorithm best compare similarities between two data sets in percentage
I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions.

Example:

Q1: Do you prefer physically demanding tasks? A1: Nope Maybe Yes --\> Subject\_1 Choose **Maybe** / Subject\_2 choose **Yes**

Q1: Do you prefer the outdoors? A1: Nope Maybe Yes --\> Subject\_1 Choose **Yes** / Subject\_2 choose **Yes**

from this data, we are able to see the likey percentage they match.

Forgive me I'm new. Thank you in advance.

# Answer
> 1 votes
You'll need two algorithms (definitions, actually) here:

1. one to define a distance between answers with in questions
2. one to define a distance between complete questionnaires

It makes working with 2 easier if you choose 1 such that they are all compatible, or normalized. (For example, you can assign a distance of 1 to total disagreement like in "Nope" vs "Yes" and a distance 0.5 for "Maybe" and anything not-maybe. If you then have questions like "rate on a scale from 1 to 10", a ratings 1 vs 10 would have a distance of 1, whereas 4 vs 5 would have a distance of 1/9. Identical answers always have a distance of 0).

Then, you can define a distance between questionnaires; most easily by adding them up (which gives you the "Taxicab distance"), and possibly normalizing to a range from 0 to 1 again by dividing by the number of questions.

If you want to express these distances in terms of similarity, you *can* just subtract them from 1 and multiply by 100%. That *does* have the effect that identical answers are "100% similar", but only completely opposite answers are "0% similar". (I.e. you will probably never see "0% similar" in practice). This is to be expected, however, considering there is "99% similarity" between the human and chimpanzee genome, or "70%" between human and fish.

What you make of that will depend on your use case. If you can expect your users to understand what these values mean you can use them as they are; if you want just a quick and easily understood score (like in those online "How much of an X are you?" tests), it may make sense to just stretch the scale and clip to 0%. (I.e. take the distance $d$, calculate $sim = (1 - 3 \times d) \times 100%$ and show any negative values as "0% match", where the factor 3 depends on the size of your questionnaire and the diversity of the answers). That won't be a highly scientific metric, but then again, "percent match" often are not.

---
Tags: algorithms, probability-theory, matching, comparison, equality
---


# Question
Title: Iteration over long linked lists and trees instead recursion
For example exist linked list with thousands (maybe million) elements or very deep tree which some branches are very long and have only one child, but exists other short branches with many children. How process this lists and trees changing very deep recursion to iteration? I have

```
struct Node {
  Node* next;
};

```

but also can exists other types and have more pointers:

```
struct Node1: public Node {
  Node* next1;
  Node* next2;
};

```

Now I want use recursion if have \> 1 non empty pointers, but iterate over long series ..next-\>next-\>next-\>... I don't know which pointer will have long or short series.

# Answer
> 2 votes
When processing a node, follow the unique outgoing path until reaching a node with two children, and only then recurse.

In pseudocode:

```
process-all(node v):
  loop
    process v
    split into cases according to the number of children that v has:
      no children: quit the entire procedure
      one child: replace v with its unique child
      two children: break out of the loop
  end loop
  process-all(first child of v)
  process-all(second child of v)

```

---
Tags: linked-lists, tail-recursion
---


title: Disadvantages of Huffman Encoding

text:
# Question
Title: Disadvantages of Huffman Encoding
Two main disadvantages of Huffman encoding is that it makes two passes over data:

1. **First pass**: Find out sequences frequencies $f(\cdot)$ of letters $c \in C$ in the document $D$. Then constructing Huffman optimal tree before transmitting the tree to the receiver.
2. **Second pass**: encode and transmit the letters themselves based on tree structure.

**Problem**: Why we don't just transmit Huffman Tree over network to the receiver please? Why we need the second pass?

# Answer
> 2 votes
The second pass corresponds to the message you want to transmit. If you don't do it, the receiver will only receive the tree, and have information on the frequency of letters in your message, but not the message itself.

---
Tags: algorithms, huffman-coding
---


# Question
Title: Why finiteness problem of CFL is decidable?
We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?

# Answer
The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^\* \alpha A \beta$. This is easy to check.
> 2 votes

---
Tags: context-free, undecidability, pushdown-automata, decidability
---


# Question
Title: Are there any programming languages that don't support concurrency out of the box?
My class had a discussion prompt that stated "Many programming languages, especially older ones, provide no language support for concurrency. C and C++ are examples of such languages." I thought C had the fork() command, maybe it's talking about an older version? I was then curious whether there were more languages that don't support it and couldn't find anything on Google.

# Answer
`fork()` is a posix API, not a primitive of the C language. Not all OSes even implement `fork()`. For example Windows doesn't.

In C++ multi-threading support was only recently standardized and, AFAIK, there is no standard way to execute another process.
> 4 votes

# Answer
Programming languages that have concurrency built-in are in fact rare, where it is handled it is usually bolted on (like using the POSIX API around `fork(2)` and process handling or the equivalent functionality under Windows in C, this even if the language is used routinely to write concurrent programs like operating system kernels) they are becoming more common with the current tendency of CPU performance increasing not by making operations faster but doing many operations in parallel (multi core, hyperthreading, ...).

Part of the reason is that we are wired to think in terms of doing one thing, then another, concurrency isn't really natural. Synchronization is a complex matter (see e.g. Downey's The Little Book of Semaphores, take a peek at the variety of primitives available for different uses in the Linux kernel). What are useful, easy to use primitives, that are efficient in a wide enough variety of uses and platforms is still not settled.
> 2 votes

---
Tags: concurrency
---


# Question
Title: How should i face the cluster editing problem?
The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can anyone helps me to face the problem?

# Answer
Here's my thoughts on it. Create a tree with the root node containing $G$. If the graph in a node contains a forbidden induced subgraph $P\_3$ then it will have children containing the resulting graphs after applying each of the 3 branching rules. As you continue down the tree, each successive graph becomes one edit closer to satisfying the condition of disjoint cliques. Apply BFS to find the first node with no children - that node will not have a forbidden induced subgraph $P\_3$ and is a graph $S$ of disjoint cliques solving the problem. Since the depth of the tree corresponds with the number of edits made, $S$ will have the minimum number of edits required.

Now, I'm not sure how to prove that a solution $S$ will exist for every $G$ by applying the branching rules. If you can show this tree contains all permutations of edges of $G$ then the search ought to be exhaustive. You will also need to prove a graph not containing a forbidden induced subgraph $P\_3$ is a solution. I believe that is the case but I can't think of a proof off the top of my head.
> 1 votes

---
Tags: algorithms, graphs, clustering
---


# Question
Title: What boolean algebra simplification is applied in this Shannon's expansion?
Found this question about Shannon's expansion. While I am trying to follow its logic, found one super convenience simplification used. Can we do this in general while dealing with boolean algebra? or only in Shannon's expansion?

Can we just turn b+d into 1 while we have (+)⋅1 previously in the equation?

Also + into 1 while we have (+)⋅1 previously in the equation?

Picture from that question:

# Answer
They applied the *Absorption Law 1* from Boolean Algebra. According to this law, the following is true:

$$x \land (x \lor y) = x$$

Sometimes the operator "$\land$" is replaced by multiplication, and also the operator "$\lor$" - by addition. That's why:

$$(b+d) \cdot 1 \cdot (b+c+d+e+f)=(b+d) \cdot ((b+d)+c+e+f)=b+d$$ $$1 \cdot (b+c) \cdot (b+c+d+e+f)=(b+c) \cdot ((b+c)+d+e+f)=b+c$$

Yes, appearance of $1$ in $(1+c+e+f)$ and $(1+d+e+f)$ terms looks strange to me as well - may be, they teach this kind of simplifications this way, it's difficult to say without looking at your textbook.

(By the way, pictures like this aren't welcomed on this site)
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: Upper-bounding the out-going degree of a graph
Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree.

For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$'s arboricity by simply assigning all vertices that have at most $2\cdot a$ unassigned neighbours to a set. Then, marking these vertices as assigned and moving on. It can be shown that in each phase, enough vertices are being assigned. This will give me an orientation with an out-bound of $\approx 2\cdot a(G)$.

(I did not extend regarding the above in too much detail, as I only meant it as an example for what I am looking for)

However, I'm looking for other ways, to build a different orienation with an out-degree as small as possible. This out-degree does not have to depend on the arboricity, it can depend on other parameters of the graph (free to choose), aiming for a lower bound as small as possible.

**Edit:** The orientation must be acyclic (or such that can be transformed to an acyclic without increasing its degree too much).

# Answer
> 3 votes
The problem of finding an *acyclic* orientation with minimum outdegree is equivalent to finding the degeneracy of the graph, which can be solved optimally in linear time. The following algorithm due to Matula and Black is copied from the above-linked Wikipedia page:

* Initialize an output list $L$.
* Compute a number $d\_v$ for each vertex $v$ in $G$, the number of neighbors of $v$ that are not already in $L$. Initially, these numbers are just the degrees of the vertices.
* Initialize an array $D$ such that $D\[i\]$ contains a list of the vertices $v$ that are not already in $L$ for which $d\_v = i$.
* Initialize $k$ to 0.
* Repeat $n$ times:
    + Scan the array cells $D\[0\], D\[1\], \dots$ until finding an $i$ for which $D\[i\]$ is nonempty.
    + Set $k$ to $\max(k,i)$
    + Select a vertex $v$ from $D\[i\]$. Add $v$ to the beginning of $L$ and remove it from $D\[i\]$.
    + For each neighbor $w$ of $v$ not already in $L$, subtract one from $d\_w$ and move $w$ to the cell of $D$ corresponding to the new value of $d\_w$.

At the end of the algorithm, $k$ contains the degeneracy of $G$ and $L$ contains a list of vertices in an optimal ordering for the coloring number.

---
Tags: algorithms, graphs, partitions
---


# Question
Title: How to prove that the set of recursive primitive functions is closed under
the scheme of iteration ?

Here is the scheme of iteration : for $g : \mathbb{N}^p\to \mathbb{N}$ and $h:\mathbb{N}^{p+1}\to \mathbb{N}$ two primitive recursive functions we associate $f: \mathbb{N}^{p+1}\to \mathbb{N}$ defined by :

$f(\bar a, 0)=g(\bar a)\\ f(\bar a, x+1)=h(\bar a, f(\bar a, x)).$

Here is my attempt :

Let consider a primitive recursive function $F: \mathbb{N}^{p+1}\to \mathbb{N}$.

Then by the primitive recursion : $F(\bar a,0))=k(\bar a) \\ F(\bar a, x+1)= l(\bar a, x, F(\bar a,x))$ where $k$ and $l$ are recursive primitive functions.

We want $F$ to check the scheme of iteration. First we can take $k\equiv g$ and then how can make a link with $h$ and $l$ ?

Thanks in advance !

# Answer
Take $l(\bar{a}, x, y) = h(\bar{a},y)$. More precisely, writing $\pi\_i$ for the $i$-th projection from $\mathbb{N}^{p+2}$ to $\mathbb{N}$, we see that $l$ is the composition of $h$ and projections, as follows: $$ l(a\_1, \ldots, a\_p, x, y) = h(\pi\_1(a\_1, \ldots, a\_p, x, y), \ldots, \pi\_p(a\_1, \ldots, a\_p, x, y), \pi\_{p+2}(a\_1, \ldots, a\_p, x, y)) $$
> 2 votes

---
Tags: computability, primitive-recursion
---


# Question
Title: Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb \[0, \infty\[$ be a function defined over this graph. This graph represents all possible paths a particle can take to go from a starting node $s$ to a final node $t$. Every weight represents the amount of energy the particle loses when traversing an edge, and the particle cannot traverse an edge if it doesn't have the energy to do so (assume that the energy cannot be negative). The function $L(u)$ represents the energy boost the particle receives after reaching node $u$. If $L(s) = E$, find the maximum energy the particle can have when reaching the final node $t$.

I'm stuck at this problem. First, I tried to solve the alternative problem in which $L(u) = 0$ for every $u \in V \setminus s$, and came up with a solution with the Bellman-Ford algorithm. However, I don't see how could I use this result for the original problem. Maybe with a dynamic programming approach?

# Answer
For each node $u$, let $p(u)$ be the maximum energy the particle can have when it reaches node $u$ from the starting node $s$, or $\infty$ if it cannot reach $u$.

Hint, there is an orderly way to determine $p(u)$ for all $u$, node by node, thanks to the fact that the graph is acyclic.

Here is a more-revealing hint.

> A topological sort will be useful.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, dynamic-programming, dag
---


# Question
Title: Could I apply Rice theorem for both TM's property and language property?
I read that Rice theorem applicable only for language property not for machine property. But today I have read from stack exchange and one site they are applying Rice theorem on machine also. My question is could we for both or language only?

# Answer
Let's start by formulating Rice's theorem.

> Fix an alphabet $\Sigma$. We consider Turing machines that recognize languages over $\Sigma$ (the language recognized by a Turing machine consists of all inputs on which the Turing machine halts).
>
> A collection $p$ of languages over $\Sigma$ is *nontrivial* if
>
> 1. $L(M\_1) \in p$ for some Turing machine $M\_1$.
> 2. $L(M\_2) \notin p$ for some Turing machine $M\_2$.
>
> **Theorem.** If $p$ is non-trivial then $\\{ M : L(M) \in p \\}$ is undecidable.

The question you link to mentions two different languages. The first language $L\_1$ is described extremely vaguely. One possible interpretation, inspired by the OP's vague comments, is that $L\_1$ consists of all Turing machines $M$ for which there exists an input $x$ such that when running $M$ on $x$, the symbol $\sigma$ gets printed on the tape.

The second language $L\_2$ is described more concretely, even though some vagueness still remains. It consists of all Turing machines $M$ such that for all integers $x,y$, if we run $M$ on input $\langle x,y \rangle$ then $M$ halts and outputs $\langle xy \rangle$; here $\langle xy \rangle$ is the encoding of the integer $xy$ according to some fixed encoding scheme, and $\langle x,y \rangle$ is similarly the encoding of the pair of integers $x,y$.

As you can see, none of the two languages are of the form considered by Rice's theorem. One of the answers mentions an extension of Rice's theorem which captures $L\_2$, but doesn't provide any more details.

We can show that $L\_1$ is undecidable by reduction from the halting problem. Given a Turing machine $M$, construct a Turing machine $M'$ which erases its input, simulates $M$, and prints $\sigma$ once $M$ halts (we arrange that $M$ never uses the symbol $\sigma$). Then $M$ halts iff $M' \in L\_1$.

We can also show that $L\_2$ is undecidable by reduction from the halting problem. Given a Turing machine $M$, construct a Turing machine $M'$ which runs $M$ on a parallel empty tape, and once it halts, checks whether the input to $M'$ is of the form $\langle x,y \rangle$, and if so, computes $\langle xy \rangle$ (otherwise we don't care what $M'$ does; it can just immediately halt). Then $M$ halts iff $M' \in L\_2$.
> 1 votes

---
Tags: formal-languages, turing-machines, rice-theorem
---


# Question
Title: Currently best approximation for graph coloring
As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation for coloring a general graph?

More formally, I am looking at a graph $G=(V,E)$ for which I do not know the chromatic number. I am trying to find a good coloring of such a graph. What is considered good?

For example, if $d=d(G)$ is the degeneracy of the graph, I can color $G$ in $d+1$ colors in linear time. The degeneracy can be computed in polynomial (linear) time.

I'd like to ask for other (polynomial) coloring algorithms that do not know the chromatic number of the graph (Yet, they are may attempt to approximate it in polynomial time), which (obviously) won't lead to $\chi(G)$ colors, but might lead me to either:

* $f(\chi(G))$-coloring, better if $f$ is linear, but also if not.
* $g(G)$-coloring, where $g$ is a parameter of the graph $G$. Such as: degeneracy, maximal degree, etc. Prefferably better than $d+1$-coloring.

Basically, I have a graph that I only know $V$ and $E$. I don't know $\chi(G)$ or anything else. So anything I want to know must be computed (or approximatex) polynomially.

Now, I want to color this graph in the best possible way that will require polynomial time. Or, in one of the best ways if there are several.

I tried looking online, but could not find such results. There are many negative results, showing some approximations are $NPH$, but I am looking for the positive results.

# Answer
> 1 votes
Dinur, Mossel and Regev showed in their paper Conditional hardness for approximate coloring that assuming some variant of the 2-to-1 conjecture (a reduction of the same family as the more famous unique games conjecture), for every $C\>4$ it is NP-hard to distinguish between 4-colorable graphs and $C$-colorable graphs. (The recently proved variant of the 2-to-1 conjecture doesn't suffice for their result, since it lacks perfect completeness.) In particular, assuming P≠NP, this implies that there is no polynomial time algorithm that colors a 4-colorable graph with any constant number of colors.

There are various extensions of this result. For example, under a stronger assumption, the same paper shows that you can consider 3-colorable graphs instead of 4-colorable graphs. Follow-up works give similar results in which $C$ is a growing function of the number of vertices, as well as similar results for hypergraphs without assuming any known conjectures (other than the implicit P≠NP), and unconditional results for graphs in which the coloring needs to be legal only for almost all vertices. Another genre of related results shows that it is NP-hard to distinguish $a$-colorable graphs from $b$-colorable graphs, where $b$ is a fast growing function of $a$ (see for example Wrochna and Živný, which get $b$ exponential in $a$).

The best known positive result in this direction is due to Kawarabayshi and Thorup, who give an efficient algorithm that colors a 3-colorable graph using $O(n^{0.19996})$ colors.

---
Tags: complexity-theory, graphs, approximation, colorings
---


# Question
Title: Attempting to verify the colorability using Wigderson's Algorithm
The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time.

For those who are not familiar with the algorithm, I'll give a brief description of it (it can be used for any $k$-colorable graph, but lets assume $k=3$).

We loop on $V$ until a $v\in V$ is found such that $\deg v \geq \sqrt {|V|}$. If no such $v\in V$ exists, then the graph has a bounded degree of $\sqrt{|V|}$, and can be easily colored using $\sqrt{|V|}$ colors in linear time (by simply iterating over all vertices and selecting an unoccupied color among the ones of its neighbours).

Once such a $v\in V$ is found, we denote by $G\_v$ the induced subgraph of $v$'s neighbours. As $G$ is $3$-colorable, $G\_v$ is $2$-colorable. That means, $G\_v$ can be colored using $2$ colors in linear time, by a simple "red"-"blue" algorithm. By selecting a third color, $v$ can be colored as well. Once we move to the next $v\in V$, we use a different color class (each color class contains $3$ colors).

We know that $\left|V\_{G\_v}\right| \geq \sqrt{|V|}$. Meaning, this procedure occurs for at most $\frac{\left| V\right|}{\sqrt{\left| V\right|}} = \left| V \right|$ iterations. The running time is linear each time, meaning the entire running time is still linear (in the original $G$).

So far is the algorithm. I would like to use in the following way:

Given a graph $G=(V,E)$, try coloring it using Wigderson's algorithm. If the graph is actually $3$-colorable, this will succeed. You will receive a $O\left( \sqrt{\left| V \right|}\right)$-coloring. If $G$ is not $3$-colorable, I believe this will fail because there should be at least one vertex $v \in V$ whose color, under any coloring function, cannot be among $\left\\{ 0,1,2 \right\\}$ (up to a permutation of the colors...). Meaning, under any coloring, its neighbours use all the colors $\left\\{ 0,1,2 \right\\}$ and the induced subgraph of its neighbours is not $2$-colorable. This means that when we try to $2$-color it by a simple "red"-"blue" algorithm, we will fail. So by checking whether or not we fail in Wigderson's Algorithm, can we not verify in reality whether $G=(V,E)$ is $3$-colorable or not?

I assume the answer is no, yet I'm looking for my mistake, and if possible, to elaborate on where exactly I am wrong in here.

# Answer
> 2 votes
Consider a star on $n-4$ vertices together with a clique on $4$ vertices.

---
Tags: complexity-theory, graphs, colorings
---


# Question
Title: Rice theorem could apply except RE language?
You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages.

$Q\_1:$ So my question is that could I apply Rice theorem to check decidability of for example emptiness, membership etc of CFL languages.

$Q\_2:$ $$L\_1= \\{\langle M \rangle \mid \text{L(M) } = \phi\\}$$ is undecidable for RE languages but $$L\_2= \\{\langle G \rangle \mid \text{L(G) } = \phi\\}$$ is decidable for CFG. CFL is RE also. But why $L\_1$ is undecidable but $L\_2$ not, What's reason behind that?

# Answer
> 0 votes
When domain is Unrestricted grammars i.e. $G$ can be any $Type-0$ grammar and then if it is asked "whether $L(G)$ is CFL or not" ....is Undecidable (Because of Rice's theorem) otherwise decidable. That's why $Q\_1$ is undecidable and $Q\_2$ is decidable.

---
Tags: context-free, undecidability, rice-theorem, decidability
---


# Question
Title: Find the segments set with the lowest number of 2D collisions
I am given 2 sets of n 2D Points. I need to find the segment set S where each of the n segments has its start and end in the first and second set respectively. The requirement is that each point must be used only once and that the set S must be the one with the lowest number of collisions between each pair of segments.

Do you know if there is an algorithm specific for this purpose or a particular paradigm that should be followed? Thanks

# Answer
> 3 votes
The related questions in the side panel led me to Joseph O'Rourke's answer to "Constructing non intersecting segments from distinct sets of points", which says that there is a solution with *zero* crossings (assuming points in "general position" — more on that later).

This introduced me to the idea of "ham-sandwich cuts": given a set of red points and blue points in the plane, there is a line that splits both the set of red points and the set of blue points in half, and it can be found in linear time.

Searching for "optimal ham-sandwich cut plane" then turned up this article, which appears to solve a more generalized version of your problem: "An optimal algorithm for plane matchings in multipartite geometric graphs"

(In their version there can be more than two colours / sets of points, as long as no one set contains more than half the total number of points, and allowable segments are ones that join two points of different colours / sets)

If I'm understanding it correctly, they use a divide and conquer approach that runs in n log n time, loosely:

* Find a ham sandwich cut for the input point sets.
* Look at the half of each point set on one side of the cut. Segments drawn between points in this half won't cross those drawn between points in the other half, so we can consider each half as an isolated sub-problem.
* Recurse on each half, finding a ham sandwich cut for each, repeatedly, until the satisfying segments are trivial.

There are nuances about how you handle more than two sets (which you don't need) and how to handle points on the cut line, which I'll confess I don't yet understand in depth, so I'll have to refer you to the paper for the full treatment.

References I've found to this problem generally assume that no three points lie on a line. If I understand correctly that's not required for the zero-crossing solution to *exist*, outside of pathological cases where say all points are on a line with all red points at one end and blue points at the other. But it might be required for the algorithm to be guaranteed to find it or execute within the given time bounds. I am new to this topic though so I may be missing something obvious.

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


# Question
Title: How is ‘x + ½ = 2 and x ∈ ℤ’ an open statement?
I was watching this video on statements. There is an example:

> $x + \frac12 = 2$

It's an **open statement** as the truth value could be `T` or `F` depending on the value of $x$.

> $∃x: x + \frac12 = 2$ and $x ∈ ℤ$

Now the statement is **closed statement ~~(proposition)~~** as the truth value is `F`.

But later the professor said:

> $x + \frac12 = 2$ and $x ∈ ℤ$

is an **open statement**. But it's not clear to me how it's an **open statement** as for any value of $x$ the statement is `F`?

**Update from the author of the video:**

> $x$ is a free (unquantified) variable here, so by definition this is an open statement. But you've identified something that's a source of confusion. Many online sites say that a statement is open if its truth value depends on what values the variable(s) take on. That usually coincides with the definition I indicated above. But this example points out that the two definitions are not the same. While it's easy to slip into the "is the truth value known" definition (as I seemed briefly to do at around 19:40), the definition of an open statement that works best is that it's a statement with one or more free variables, as I point out in several places in this video.

# Answer
> 16 votes
$$x=1$$ $$∃x: x=1$$ The first is an open statement, since no value for $x$ is given. $x$ is called a free variable here.
The second is a closed statement, because it talks about all possible values of $x$. $x$ is not a free variable here.

An open statement can be true or false depending on what the values of its free variables are.
A closed statement is either always true or always false. (But we might not know which) $$x=x+1$$ This is an open statement since there is no $∃x$ there. It just so happens that it is always false, but that is not relevant to openness.

# Answer
> 8 votes
Whether it's an open statement or not depends on the structure of the statement, no on whether you can prove the truth value.

Look at the second statement. There are three things you could substitute: You could substitute any number for the "1/2", you could substitute any number for the "2", and you could substitute any set of numbers for the "Z".

All these changes don't change the structure of the statement, so it remains an open statement with any of those changes. Of course, depending on the values you substitute, there might be a solution for x, or there might be none, or multiple solutions, but that doesn't change the structure of the statement which remains open.

# Answer
> 1 votes
Generally in first order logic open statement simply means a formula with free variable(s) and thus is not a (closed) sentence. How can you be sure that its closed statement is false if it turns out that the actual statement reads $\lnot \exists x: x + 1/2 = 2$ AND $x ∈ Z$?

# Answer
> 0 votes
The derivative of $3x+5$ is a function, even though it's always equal to $3$. (The statement "the derivative of $3x+5$ is $3$" is really shorthand for "The derivative of $f:x\rightarrow 3x+5$ is $f':x\rightarrow3$".) The derivative of $3x+5$ at $x=2$ is not a function, it's a real number.

An open statement can be viewed as being a function of the free variables. Whether that function has different values for different inputs is irrelevant to whether it's a function/open statement. If an expression has no free variables, then it's called a closed statement (technically, it can be considered to be a nullary function, so one could argue that the analogy between functions and open statements should be between *non-nullary* functions and open statements).

---
Tags: first-order-logic
---