title: Random walks on Complete Binary Trees

text:
# Question
Title: Random walks on Complete Binary Trees
Let $T$ be a complete binary tree of height $n$ and root $r$.

A random walk starts at $r$, and at each step uniformly at random moves on a neighbor.

There are $m$ random walkers all starting at $r$ and let denote with $H\_1,\dots,H\_m$, the heights reached by the walkers after $n$ steps.

Show that, for some constant $C$ which do not have to depend on $n$ and $m$, it holds that

$\mathbb{P}\left(\underset{i \in \[m\]}\max\left|H\_i - \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 - \frac{1}{m}$

I have been trying several strategies, to appropriately define $H\_i$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

Thanks in advance!

# Answer
> 0 votes
**This answers the version of the question in which the goal is to show that with high probability, $\max |H\_i - \frac n 3| \leq C\sqrt{n\ln m}$ for some constant $C$.**

Since $|H\_{i+1}-H\_i| \le 1$, you can use Azuma's inequality (via Doob's martingale) to upper bound the probability of deviation from the mean, and so obtain your required bound, once we show that the expectation of $H\_n$ is very close to $\frac{n}{3}$.

To this end, let $X\_i$ be a random variable equal to $+1$ with probability $2/3$ and to $-1$ with probability $1/3$, and couple $H\_i - H\_{i-1}$ to the $X\_i$: if $H\_{i-1} = 0$ then $H\_i = 1$, and otherwise $H\_i = H\_{i-1} + X\_i$. Let $Y\_i$ be a random variable equal to $+2$ if $H\_{i-1} = 0$ and $X\_i = -1$, and equal to $0$ otherwise, so that $H\_i = H\_{i-1} + X\_i + Y\_i$. In total, $H\_n = \sum\_{i=1}^n (X\_i + Y\_i)$.

In order to calculate $\mathbb{E}\[H\_n\]$, notice first that $\mathbb{E}\[X\_i\] = \frac13$. For calculating $\mathbb{E}\[Y\_i\]$, let us notice that the event "$H\_{i-1}=0$" is independent of the event "$X\_i=-1$". Therefore, if we let $Z\_i$ be the indicator of $H\_i = 0$, then $\mathbb{E}\[Y\_i\] = \frac23 \mathbb{E}\[Z\_i\]$. Defining $Z = \sum\_{i=1}^\infty Z\_i$, we have $$ \frac{n}{3} \leq \mathbb{E}\[H\_n\] \leq \frac{n}{3} + \frac{2}{3} \mathbb{E}\[Z\]. $$ Let $a\_k$ be the expected number of visits to the root if starting at a node at depth $k$ (so $a\_0 = \mathbb{E}\[Z\]$), let $p = 1/3$, and let $q = 1-p = 2/3$. Then $a\_k$ satisfies the following recurrence: $$ a\_0 = 1 + a\_1, \quad a\_k = p a\_{k-1} + q a\_{k+1}. $$ Let us prove inductively that $a\_k = (p/q)^k + a\_{k+1}$. This holds for $k = 0$. Given that $a\_{k-1} = (p/q)^{k-1} + a\_k$, we have $$ a\_k = pa\_{k-1} + qa\_{k+1} = p(p/q)^{k-1} + pa\_k + qa\_{k+1}. $$ This implies that $qa\_k = p(p/q)^{k-1} + qa\_{k+1}$, and so $a\_k = (p/q)^k + a\_{k+1}$, as claimed.

When $p \< 1/2$, we know that $\mathbb{E}\[H\_n\] \longrightarrow \infty$, and so $a\_k \longrightarrow 0$ (this requires proof). Therefore $$ a\_0 = \sum\_{k=0}^\infty (p/q)^k = \frac{1}{1-p/q} = \frac{q}{q-p}. $$ (Similarly, $a\_k = (p/q)^k \frac{q}{q-p}$.) In our case, $a\_0 = 2$, and so $$ \frac{n}{3} \leq \mathbb{E}\[H\_n\] \leq \frac{n+4}{3}. $$

# Answer
> 3 votes
**This answers a previous version of the question, in which the goal was to prove that with high probability, $\max |H\_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$ for some constant $C \> 0$.**

When a particular walker is not at the root, it has a probability of 2/3 to go down a step, and a probability of 1/3 to go up a step. This is where $n/3$ comes from. However, when it is at the root, it always goes down. This suggests comparing $H\_i$ to a sum of $n$ i.i.d. variables whose distribution is $+1$ w.p. $2/3$ and $-1$ w.p. $1/3$. Indeed, if $X\_i$ is a variable with that distribution, then $H\_i$ stochastically dominates $X\_i$. Hence it suffices to show that $$ \mathbb{P}\left(\max\_{i \in \[m\]} X\_i \geq \tfrac{n}{3} + C\sqrt{n\ln m}\right) \geq 1-\frac{1}{m}. $$ (More formally, we can construct a coupling of the $H\_i$ and $X\_i$ in which $H\_i \geq X\_i$.)

Up to an affine transformation, the distribution of $X\_i$ is binomial, so it should be easy to obtain whatever bound you wish. You can take a look at Lower bounds on binomial and Poisson tails: anapproach via tail conditional expectations by Pelekis, for example.

---
Tags: binary-trees, random-walks
---


title: What is the time complexity of it?

text:
# Question
Title: What is the time complexity of it?
I can calculate the time complexity of the following loop:

`for (int i = 1; i < n; i++)`

The time complexity of it is $O(n)$.

but I can't calculate the time complexity of the next two loops.

I can't find any hints.

`for (int i = 0; i < n; i+= 2)`

`for (int j = 1; j < n; j*= 2)`

# Answer
Its hard to tell what the "complexity" of a loop without knowing what each iteration performs, but what we can do is count how many times each loop iterates:

> for (int i = 1; i \< n; i++)

You correctly stated this loop iterates $n$ times.

> for (int i = 0; i \< n; i+= 2)

The above loop iterates until $i \geq n$, or in other words, $k$ times, when $i+2k = n \rightarrow 0+2k = n$ (since you initiate $i=0$ and increment it by $2$). Solve the trivial equation, and you get $k=\frac{n}{2}$, which is $O(n)$ iterations.

> for (int j = 1; j \< n; j\*= 2)

Same as the second time, we must solve $2^k = n$, since you multiply $j=1$ by $2$ each iteration. Solve and get $k=\log(n)$
> 1 votes

# Answer
```
for (int i = 0; i < n; i += 2)

```

has the time compexity O(n) and

```
for (int i = 0; i < n; i *= 2)

```

has the time compexity O(ln n).
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?
**Note:** The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA.

I need to scan both columns (shown below) to find any number of column 1 values that when summed match the setpoint (E2) and column 2 values that when averaged match the setpoint (E3). One constraint is that the chosen values in column 1 and column 2 **must be from the same row** (or same 'index', shown in the image highlighted in blue and green).

**Explanation of the solution below:** What it should do is say 'A2 and A6 sum to 7 (match cell E2), and the corresponding B2 and B6 average to 3' (match cell E3). Therefore, these rows should be selected/highlighted in any appropriate way. (note that technically the first solution would be rows 2 and 3 as they fit the sum/average setpoints also).

**Example that does not work as a solution:** It can't be A4 and A5 because although they add to 7, B4 and B5 average to 1.5, not the setpoint of 3.

Image of the problem (with a solution highlighted):

A solution for one of the cases (below) works only for the case where there are **two** rows that will sum/average to the setpoints. It will not work for cases where more than two rows are required. The solution should work for **any number of rows required.**

**Example where three rows would be required (Solution is the first three rows):**

**Reason for this solution:** B6:B8 sums to the setpoint of 8 and C6:C8 average to the setpoint of 3
I am looking for help with an algorithm. If the solution is a large number of rows required (\>100), how can I iterate through the combinations efficienctly to find a set of rows that both sums/averages to the setpoints?
It may not be possible to find a solution to both setpoints, in this case finding a solution within an error is also ok

**Note:** If there is a more suitable stack exchange please advise.

Finding an algorithm is NP-Hard, therefore I am also looking for appropriate simplifications to avoid this. An error term may be an example of one simplification.

# Answer
> 2 votes
In general, no; this problem is NP-hard. Even matching just the sum (without getting into anything about the average) is NP-hard, as it is the subset sum problem. Thus, you should not expect any efficient algorithm for your problem that works for all possible inputs.

I notice that in your examples, the numbers are all small. For that special case, there are reasonably efficient algorithms using dynamic programming: see, e.g., https://en.wikipedia.org/wiki/Subset\_sum\_problem#Pseudo-polynomial\_time\_dynamic\_programming\_solution.

The dynamic programming algorithm in that link describes how to make the sum match, but you can adapt it to make both the sum and average match. In particular, you have an array $Q\[t\_1,t\_2,i,k\]$, which you will fill in with True if there exists a subset of $k$ out of the first $i$ rows whose first column sums to $t\_1$ and whose second column sums to $t\_2$. You can use dynamic programming to fill in this array (in order of increasing $i$) in $O(N^4M^2)$ time, where $N$ counts the number of rows in your spreadsheet and $M$ is the largest number in the spreadsheet. Then, once you've filled in this array, there will be a selection that sums to $s$ and averages to $a$ if and only if there is some $k$ such that $Q\[s,ak,N,k\]$ is True.

I recommend implementing this in a programming language (e.g., VBA, not Excel). Implementing it in Excel might be possible but it sounds painful. See https://cs.stackexchange.com/tags/dynamic-programming/info for our reference material on dynamic programming; if you're not familiar with that subject, you might want to read a textbook introduction to it.

---
Tags: algorithms, search-algorithms, approximation
---


title: What are the axioms of automata theory?

text:
# Question
Title: What are the axioms of automata theory?
Every theory has axioms and theorems derived from axioms.

How many axioms are there for automata theory? What are the axioms of automata theory?

# Answer
Automata theory is a broad field and researchers keep inventing new types of automata. There is even a conference series on non-classical models of automata. So it is impossible to encompass all of automata theory. For classical models such as context-free grammars, recently formalized proofs of the most basic theorems have been carried out. These are derived from first principles (these are definitions in terms of set theory). See this example for an accessible account: https://www.react.uni-saarland.de/people/hofmann/jhofBA.pdf
> 2 votes

# Answer
Automata theory is built on set theory, so the underlying axioms are those of the Zermelo–Fraenkel set theory (ZFC) with the axiom of choice.
> 2 votes

---
Tags: automata
---


# Question
Title: How to reduce number of move operations in an array?
Say I have an array of numbers, e.g. `[0, 1, 2, 3, 4, 5]` and I want to end up with an array, e.g. `[2, 1, 4, 0, 5, 3]`. At my disposal, I have a single method that I can use:

```
move(fromIndex, toIndex)

```

Thus, to achieve my desired array, I could call the method a number of times:

```
move(2, 0); // [2, 0, 1, 3, 4, 5]
move(1, 2); // [2, 1, 0, 3, 4, 5] (swapped 2 with 0)

move(4, 2); // [2, 1, 4, 0, 3, 5]
move(3, 4); // [2, 1, 4, 3, 0, 5] (swapped 4 with 0)

move(4, 3); // [2, 1, 4, 0, 3, 5] (swapped 0 with 3)

move(5, 4); // [2, 1, 4, 0, 5, 3] (swapped 5 with 3)

```

Thus, I also have a list of `move()` operations to achieve my desired result. The list of `move()` operations can possibly be reduced in size by changing the order and the indexes, to end up with the same result.

Is there an algorithm that I can use on my list of `move()` operations to reduce its size to a minimum?

# Answer
> 0 votes
### The example in the question

The minimum number of moves needed for the example in the question, from `[0, 1, 2, 3, 4, 5]` to `[2, 1, 4, 0, 5, 3]` is 3.

```
            // [0, 1, 2, 3, 4, 5], where 2, 4, 5 are good.
move(2, 1); // [0, 2, 1, 3, 4, 5], where 2, 1, 4, 5 are good.
move(0, 4); // [2, 1, 3, 4, 0, 5], where 2, 1, 4, 0, 5 are good.
move(2, 5); // [2, 1, 4, 0, 5, 3], where 2, 1, 4, 0, 5, 3 are good.

```

The idea is to split the target array into two subsequences, `2, 4, 5` and `1, 0, 3` where the first subsequence is the longest increasing subsequence. Keeping the order of elements in the first subsequence, we will move the remaining elements from left to right to their expected positions respectively, i.e, first moving `1` to its expected positions and so on.

### An algorithm

**Input**: Array $A = \[0, 1, 2, ..., n-1\]$ and array $B\[0\], B\[1\], ..., B\[n-1\]$ which is a permutation of $0, 1, 2, ..., n-1$.

**Output**: A list of minimum size each of whose elements is an operation of the form `move(fromIndex, toIndex)` such that after performing that list of operations on $A$, $A$ becomes $B$.

**Procedure**: $B$ is intact while $A$ will be changed move by move.

1. Let $B\[s\_1\], B\[s\_2\], \cdots, B\[s\_m\]$ be the longest increasing subsequence of $B$. This can be done as described in this Wikipedia article. It can also be done as described in this Wikipedia article since the longest increasing subsequence of $B$ is the longest common subsequence of $A$ and $B$. Let $s\_{-1}=-1$ and $s\_{m+1}=n$.
2. Let $O$ be an empty list of operations. For $i$ from -1 to $m$ inclusive do:

* For $j$ from $1$ inclusive to $s\_{i+1} - s\_i $ exclusive do:

    1. Find $x$, the index of $B\[s\_i\]$ in $A$. If $i=-1$, let $x=0$.
        2. find $y$, the index of $B\[s\_j + j\]$ in $A$.
        3. Move $A\[y\]$ to the $j$-th place after the place of $A\[x\]$.
        4. Add $\text{move}(y, x + j)$ to $O$.

    Now all numbers in $B$ up to index $s\_{i+1}$ are good, i.e., sorted in the same order in $A$ and in $B$, although the same number might be at different indices in $A$ and in $B$.

**Correctness**

It is clear that at the end of the algorithm, all numbers in $A$ are sorted in the same order in $B$ and in $B$, i.e., $A$ is $B$. The total number of moves in the algorithm is $$(s\_0-s\_{-1}-1) + (s\_1-s\_{0}-1)+\cdots + (s\_{m+1}-s\_{m}-1) = s\_{m+1}-s\_0-(m+1)=n.$$

On the other hands, each `move(fromIndex, toIndex)` in any algorithm can increase the common longest subsequence between $A$ and $B$ by at most 1. So $n-m$ moves are needed.

This is pointed out by xskxzr first.

**Complexity**

It takes $O(n\log n)$ or $O(n^2)$ to find the longest increasing subsequence. Finding the index of a number in $A$ is performed about $2n$ times, which costs $O(n^2)$ in total. It takes $O(n^2)$ to perform all $n$ moves. So the algorithm runs in $O(n^2)$ time.

The implementation of finding the index of a number can be sped up so that the algorithm can be implemented to run in $O(n\log n)$ time.

### Exercises

**Exercise 1.** (One minute or two) Array $A$ is a permutation of $0, 1, \cdots, n-1$. State an algorithm that find a list of operations of the form `move(fromIndex, toIndex)` such that will sort $A$ in minimum steps.

**Exercise 2.** The same input is given. Find an algorithm that computes the minimum number of moves needed to change $A$ so that it ends up the same as $B$ up to a cyclic shift. For example, when $B=\[2, 1, 4, 5, 0, 3\]$, $A$ should be changed to one of $\[2, 1, 4, 5, 0, 3\]$, $\[1, 4, 5, 0, 3, 2\]$, $\[4, 5, 0, 3, 2, 1\]$, $\[5, 0, 3, 2, 1, 4\]$, $\[0, 3, 2, 1, 4, 5\]$ and $\[3, 2, 1, 4, 5, 0\].$

---
Tags: sorting, arrays, ordering
---


# Question
Title: What Do These Symbols Mean in Repetitive Rule Application and How Are They Applied Practically?
Frequently in cs blogs and books I see this notation, `=>*` and `=>+` but I am not sure how it is being applied in a production rule and it's significance. What exactly does it represent, and can you show an example of it being applied.

# Answer
In most CS contexts, including this one, $X^\*$ means any number of $X$'s, including zero, and $X^+$ means one or more $X$'s.

So $A\Rightarrow^\* B$ just means that $A$ gets to $B$ by some number of steps and, if that number is zero, then $A=B$. More formally, it means that there is some number $\ell\geq 1$ and objects $C\_1, \dots, C\_\ell$ such that $A=C\_1$, $B=C\_\ell$ and $C\_i\Rightarrow C\_{i+1}$ for each $i\in\\{1, \dots, \ell-1\\}$. $A\Rightarrow^+ B$ means the same thing except with $\ell\geq 2$.

So, for example, given the grammar $$S\to aS\mid b\\,,$$ we have $$S\Rightarrow aS\Rightarrow aaS\Rightarrow aab\\,,$$ so we can write $S\Rightarrow^\*aab$. In this case, $\ell=4$, $C\_1=S$, $C\_2=aS$, $C\_3=aaS$ and $C\_4=aab$. Since $\ell\geq 2$, we can also say $S\Rightarrow^+ aab$. We can also write $S\Rightarrow^\*S$, which is $\ell=1$, $C\_1=S$; but we can't write $S\Rightarrow^+S$, because any *positive* number of productions from $S$ will give a string with at least one terminal symbol in it.
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: What is the relation between syntax and type theory?
Type theory and syntax are similar, in that they are inductive rules that determine whether a particular string of symbols is "correctly specified" in some sense.

There is a difference between syntax and type theory. Syntax in programming languages for example, concerns things that do not concern type theory, such as the fact that the statement `if import microsoft.(false ==== 5) then import` is "syntactically nonsense". This is not a type error, but a syntax error.

But I'm unsure what the relation is.

I normally think of syntax and type systems as follows: Let $L$ be the set of possible strings of some symbol set $S$. A particular syntax inductively specifies a subset $T\subseteq L$ of "terms" in $L$. e.g. a program is not well-specified if it is not in $T$. A particular type system then makes an additional restriction, by inductively specifying a subset $W\subseteq T$ of "well-typed terms".

**But given such a syntax and type system, we can always consider a *new* syntax which is simply the old syntax plus also has the inductive rules of the type system as an additional restriction.**

Therefore it is not clear to me why there is a fundamental difference between a syntax and a type system.

Is my intuition correct? Can we see type checking a particular form of syntax checking?

# Answer
> 4 votes
The division line between syntax and additional type checking can indeed be blurred, if so desired, but usually we make a distinction as follows:

* the syntax is described using a formal grammar, preferrably one that is not very complex, such as a context-free gramar, or one that is even simpler than that.
* the typing rules are described using inference rules whose complexity tyically exceeds that of a context-free formal grammar.

In general, a programming language might stratify the task of getting from the source code to the compiled code as follows:

1. *Parsing* converts the input string to an abstract syntax which represents the input as a tree.
2. *Elaboration* performs certain simple transformation of input syntax, such as getting rid of syntactic sugar.
3. *Type-checking and inference* verifies that the program is well-typed, thereby guaranteeing that later stages will not get stuck. It may also augment the input source with extra information about types.
4. Several phases of *compilation* may follow, each translating from its input to a simpler language. The final language may be machine code, or byte code, or in general some intermediate code.
5. The program is executed.

While you may consider merging some of these phases together, and sometimes that is a good idea, it is in general better to keep them separate. From a conceptual point of view parsing is very different from type checking. After all, these two phases serve different purposes: one is just a translation from strings to trees, while the other one statically analyzes the structure of the program in order to detect possible errors and to aid further compilation.

An example of merging different phases is "just in time" compilation: we run a program in an "interpreted" mode so that there is no delay because of compilation, and at the same time we perform on-the-fly compilation of those parts of the code in which the program is spending most of the time. I believe some browsers do that with Javascript.

---
Tags: type-theory, syntax
---


# Question
Title: What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \\{acbc: a,b,c \in \\{0,1\\}^+ \\}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??

# Answer
I claim that $L$ is equal to the set of all strings of the form $a\gamma b\gamma$, where $a,b \in \\{0,1\\}^+$ and $\gamma \in \\{0,1\\}$. Indeed, a string of this form clearly belongs to $L$. Conversely, if $acbc \in L$ and $c=d\gamma$, then $acbc = ad\gamma bd\gamma$ belongs to the new set. The new set is clearly described by the regular expression $$ (0+1)^+0(0+1)^+0 + (0+1)^+1(0+1)^+1. $$
> 1 votes

# Answer
The question seems a bit less detailed. Note that, you have defined, a, b and c belong to {0,1}+ . Here, there is no upper bound for the length of c. We know that, regular expressions can only express regular languages, i.e. languages which are recognized by any Finite State Machine, like DFA. Finite State Machines have finite memory. To recognize the above language, machine needs to store the contents of first 'c' to match with the second 'c'. As the length of 'c' can be infinite, a Finite State Machine can not recognize this language.
However, if we introduce an upper bound to the length of 'c', then it will be regular language and can be expressed by a RE. For |c| = 1, your RE is correct.
> 1 votes

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


# Question
Title: reduction from 3-SAT to Subset Sum problem
How to reduce 3-SAT to subset sum problem?

# Answer
The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable. The reduction below is lifted directly from the lecture notes found at https://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf .

> We reduce 3SAT to SUBSET-SUM. Consider a 3CNF formula with variables $x\_1, . . . , x\_n$ and clauses $c\_1, . . . , c\_r$. For each variable $x\_i$, we will have two numbers $y\_i$ and $z\_i$ in the list. For each clause $c\_j$, we will also have two numbers $s\_j$ and $t\_j$. We define all of these numbers by specifying their base 10 representations. The construction is best explained by an example and a picture.
>
> If the formula is $(x\_1∨x\_2∨\overline{x\_3})∧(\overline{x\_1}∨x\_2∨\overline{x\_3})$, then the base 10 representations of the numbers will look like this:
>
> \begin{array}{c|ccc|cc} & x\_1 & x\_2 & x\_3 & c\_1 & c\_2 \\ \hline y\_1 & 1 & 0 & 0 & 1 & 0 \\ z\_1 & 1 & 0 & 0 & 0 & 1 \\ y\_2 & 0 & 1 & 0 & 1 & 1 \\ z\_2 & 0 & 1 & 0 & 0 & 0 \\ y\_3 & 0 & 0 & 1 & 0 & 0 \\ z\_3 & 0 & 0 & 1 & 1 & 1 \\ \hline s\_1 & 0 & 0 & 0 & 1 & 0 \\ t\_1 & 0 & 0 & 0 & 1 & 0 \\ s\_2 & 0 & 0 & 0 & 0 & 1 \\ t\_2 & 0 & 0 & 0 & 0 & 1 \\ \hline k & 1 & 1 & 1 & 3 & 3 \\ \end{array}
>
> The number $y\_i$ corresponds to the positive occurrences of $x\_i$ in the formula while the number $z\_i$ corresponds to its negative occurrences. It should be clear how to generalize this construction to an arbitrary 3CNF formula. And the list of numbers can clearly be constructed in polynomial time. We claim that a subset of these numbers adds to exactly $k$ if and only if the formula is satisfiable. A key point is that the sum of the numbers can be done column by column, independently, because carries will never occur.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else. The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula. Note that the required sum $k$ has a one in each digit position corresponding to the variables. This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both. Note also that sum $k$ has a three in the digit position corresponding to each clause. The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values. All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.
> 11 votes

---
Tags: complexity-theory, automata, reductions
---


title: Vertex cover of bipartite graph

text:
# Question
Title: Vertex cover of bipartite graph
A vertex cover is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.

From codeforces,

> The minimum vertex cover should contain exactly one vertex for every edge in the maximum matching $M$. So let's assign a boolean variable for every edge in $M$, say, $x\_i = 0$ if the $i$-th edge adds its left end to the vertex cover. One can build all the dependencies over these variables. For example, if there exist edges $(u,v) \in M$ and $(u,w) \notin M$, while $w$ is not saturated by $M$, we have to set $x\_i$ equal to 0, because there is no other way to cover the edge $(u, w)$. All the other cases are handled trivially.
>
> As a result, we obtain a full system of restrictions for the set of variables. Finding an arbitrary valid assignment is a classical 2-SAT problem. So we have basically reduced the minimum vertex cover problem to 2-SAT without thinking too much.

I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

This is the graph I have ($2K\_2$) two edges in the maximum matching:

For the first edge I took left vertex in the cover $x\_1=0$ (according to the blog in the link) for the second edge I took right vertex in the cover $x\_2=1$.

Questions:

1. How final 2-sat will be true?
2. Can anyone explain what will be the relation between $x\_1$ and $x\_2$?

# Answer
> 3 votes
As that link explains, you have one variable per edge in the maximum matching, call it $x\_i$ for the $i$th edge. If $x\_i=0$, we'll choose the left endpoint of that edge to be in the vertex cover; if $x\_i=1$, we'll add the right endpoint of that edge to the vertex cover.

Now, we need to make sure that all of the vertices are covered. Iterate over each edge $(u,w)$ that's not in the matching:

* If $u$ is touched by the matching but $w$ is not touched by the matching, then the only way to achieve a valid vertex cover from this matching is to include $u$ in the vertex cover. So, we need to find the edge $(u,v)$ in the matching, then set the corresponding variable $x\_i$ to 0 (to ensure $u$ is selected, not $v$).
* If $u$ is not touched by the matching but $w$ is touched, then do the reverse of the above.
* If neither of $u$ nor $w$ is touched by the matching -- this can't happen in a maximum matching (because you could add the edge $(u,w)$ and get a larger matching). So, you can ignore this case.
* If both $u$ and $w$ are touched by the matching, then we need to ensure that either $u$ or $w$ is selected. This can be enforced with a 2-CNF clause. In particular, let $x\_i$ be the variable for the edge that touches $u$, and let $x\_j$ be the variable for the edge that touches $w$. If $u$ is the left endpoint for $x\_i$ and $w$ is the right endpoint for $x\_j$, we add the 2-CNF clause $\neg x\_i \lor x\_j$; this ensures that either $u$ or $w$ are selected (or possibly both).

So, combine all the 2-CNF clauses you get in this way, and you get a 2-CNF formula, i.e., a 2-SAT instance. Solving the 2-SAT instance tells you how to pick a set of vertices that will be a vertex cover. Once you have an assignment that satisfies the 2-SAT instance, that corresponds to a consistent way to choose vertices; and you can verify that this set of vertices forms a vertex cover.

# Answer
> 3 votes
> I don't understand the variables. I have an edge from maximum matching then I might have both the endpoints of that edge in the vertex cover. But this scheme does not allow this.

In bipartite graphs, the size of a maximum matching is also the size of the minimum vertex cover. Since every vertex cover must contain *at least* one vertex from each edge in the matching, it follows that it has to contain *exactly* one vertex from each edge in the matching.

---
Tags: algorithms, graphs, approximation, vertex-cover
---


title: Implications of Integral linear program

text:
# Question
Title: Implications of Integral linear program
Let $(P)$ an *Integer Linear Program*, where we aim to find $x\in \\{0,1\\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$

Let $(P^\*)$ be its relaxation, which means that the constraint $x\in \\{0,1\\}^n$ is replaced by $x\in \[0,1\]^n$.

Then, suppose that we know that $$ \max\_{x\in \\{0,1\\}^n} \left\\{f(x), Ax\le b\right\\} = \max\_{x\in \[0,1\]^n} \left\\{f(x), Ax\le b\right\\} $$

Is it possible, given an optimal solution $y^\*\in\[0,1\]^n$ of $(P^\*)$ (that we have found with simplex algorithm for instance), to find an optimal solution $y\in\\{0,1\\}^n$ of $(P)$ (*i.e.* such that $f(y)=f(y^\*)$ and $Ay\le b$), say in polynomial time ? Or is there any concrete conter-example ?

# Answer
In general, this is not possible unless P=NP. So, it is unlikely that such a method exists.

Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $C\_i$ and variables $v$. For each clause, denote the variables that appear positive by $C\_i^+$ and the variables that appear negative by $C\_i^-$. Now, consider the following integer program $P$:

$\begin{align} \max 1 \quad \text{s.t.} \quad & \sum\_{v\in C\_i^+} x\_v + \sum\_{v\in C\_i^-} (1-x\_v) \geq 1 \text{ for all } i\\ & x\_v \in \\{0,1\\} \text{ for all } v \end{align}$

Note that $P$ has a feasible solution if and only if our 3SAT instance is satisfiable. (a solution to $P$ corresponds to a satisfying assignment of the 3SAT instance) This solution is then 'optimal' as well, as all feasible solutions of $P$ have the same cost. This means that also the relaxation $P^\*$ must have the same cost if $P$ is feasible. So, we will assume that the given 3SAT instance is satisfiable, so that the costs of $P$ and $P^\*$ are equal.

Now, suppose we have some method to find a solution for $P$ from a solution $y\in \[0,1\]^d$ for $P^\*$. As $P^\*$ is a normal linear program, we can find such a solution $y$ in polynomial time, by using e.g. the ellipsoid method. Then, our method gives us a solution for $P$ in polynomial time. But this solution gives a satisfying assignment for our initial 3SAT problem, which means we can find a satisfying assignment to 3SAT problems in polynomial time. As finding a satisfying assignment for 3SAT is NP-hard (even if we know the instance has a satisfying assignment), this means that P=NP

---

I suppose that intuitively, what is going on here is that knowing the value of a solution to an integer program does not tell you a lot about the specific variable assignment. In a way, this is because the 'complexity' of a linear program lies mostly in its constraints, rather than the goal function.
> 2 votes

# Answer
Bare in mind that the simplex algorithm will always find an optimal solution that is a vertex of the polytope defined by $A x \leq b$. Hence if none of the vertices of the polytope are integral then it cannot find the integral solution.

For example, consider maximising $x + y$ subject to the constraints that $x + y \leq 4$, $y - x \leq 1$ and $x - y \leq 1$ as shown in the figure below. Then the optimal solution of this as an integral linear programming problem is $(2, 2)$ however the solution found by the simplex method for the relaxed problem will either be $(1.5, 2.5)$ or $(2.5, 1.5)$.

Note however that this situation can only occur if the relaxed version of the problem has more than one optimal solution. If the relaxed version has a unique optimum $y^\*$ then thanks the equality that you have supposed $y^\*$ will be integral and so the optimum solution to the integral problem.
> 0 votes

---
Tags: optimization, integer-programming, mathematical-programming
---


# Question
Title: design cache system using queuing theory
If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS & a cache size will have a count). How can one use queuing theory to estimate the best possible cache size ?

# Answer
> 1 votes
You first need to establish the access speed of the cache, depending on the cache size (usually larger cache -\> slower speed, because of physics). You also need to determine the energy consumption of a larger cache, which will lead to increased heat, which will lead to lower clock speed (again, because of physics). Then you need to find the cost of a larger cache - if I can gain *more* for less money using different methods than increasing the cache size, I'm not going to increase the cache size (because of economics).

Histograms of existing applications are of limited use, since there are plenty of algorithms that adapt to the cache size - with a cache four times the size you would have completely different access patterns. So you are going to use simulations.

I wonder why I didnt't mention queuing theory here.

---
Tags: algorithm-design, queueing-theory, design-patterns, cache
---


title: Complement of NP-complete can be in NP

text:
# Question
Title: Complement of NP-complete can be in NP
Here are a couple of questions I struggle with. (We use $A'$ to denote the complement of the problem $A$.)

1. A problem $A$ is NP-complete if and only if $A'$ is in NP?
2. A class problem $A$ is NP-Complete iff $A'$ is in NP? (Is there any difference between these two?)

I got this claim to be true that

> If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

And this claim also to be true:

> $A$ is NP-hard iff $A'$ is coNP−hard

Then is the upper claim also true?

# Answer
> 4 votes
> A problem $A$ is NP-complete if and only if $A'$ is in NP?

This is false. Take $A'=\emptyset$: then we have $A'\in\mathrm{NP}$ but $A=\Sigma^\*$ is not $\mathrm{NP}$-complete.

> If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

This follows from the following three facts, which you should attempt to prove yourself.

1. The complement of an $\text{NP}$-complete problem is $\text{co-NP}$-complete;
2. if any $\text{co-NP}$-complete problem is in a class $\mathcal{C}$ that is closed under polynomial-time reductions, then every $\text{co-NP}\subseteq\mathcal{C}$;
3. $\text{NP}$ is closed under polynomial-time reductions.

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


# Question
Title: How to show a language is regular through creating DFA
I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.

The alphabet is $\Sigma=\\{0, 1\\}$ and the language is: $$L = \\{x \in \Sigma^\*\mid \\#\_0(x)\>\\#\_1(x)\text{ and }\\#\_1(x)\leq3\\}\\,,$$ where $\\#\_i0(x)$ means the number of $i$s in $x$.

When I should send it to a dead/trap state and what should the DFA look like?

# Answer
As with any automaton, the states need to encode all the information you need to decide whether or not to accept the string you've read so far. In this case, that means that number of $0$s and $1$s that you've seen. Except you can't quite do that, because that would require infinitely many states. However, if you look more closely at the definition of the language, you'll see that you don't need to know the exact number of $0$s and $1$s: for example, if you've seen six $1$s, that's the same as seeing seven, or a million.

Once you've worked out what the states are, work out what the transitions between them are. You'll find that you have a trap state, without needing to figure out what it should have been. Trap states occur "naturally", whenever you've seen enough of the input to be able to say, "I don't care what else I see: I'm rejecting this string!"
> 1 votes

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


# Question
Title: Minimally extend a tree such that there are no bridges in the new graph
We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.

An edge $e$ is a bridge if the graph with that edge removed is no longer connected.

For example, here is a tree with 8 nodes

```
1 2
2 3
3 4
4 5
3 6
3 7
3 8
At least three edges should be added. For example: (1, 6), (5, 7), (8,4)

```

In very small graphs we can brute force all possible new edges. However, this is too slow for bigger trees. I tried making some observations but I couldn't find anything that could solve the problem.

This problem is the task "NET" from Baltic Olympiad in Informatics 2015.

# Answer
> 2 votes
If a tree $T$ becomes bridgeless after edges in a set $S$ have been added to $T$, we will say $S$ doubly connects $T$.

### The minimum size of $S$ that doubly connects $T$ is $\lceil n/2\rceil$, where $n$ is the number of the leaves in $T$.

The simple idea is that the edges to be added should only connect leaves of the tree. After we have selected an edge to be added, we can delete its two vertices and some related vertices and edges so that the remaining tree has two less leaves. We will make sure that solving the problem for the remaining tree is enough to solve the original problem.

### Outline of an algorithm

**Input**: A tree $T$ whose vertices are $0, \cdots, n-1$ where $n\ge2$. The set of vertices that are neighbours to vertex $v$ is $N\[v\]$.

**Output**: A list of edges whose size is minimum such that $T$ with those edges added is bridgeless.

**Helper procedure** to delete a vertex $v$ of degree 2: Suppose $x$ and $y$ are the two vertices connected to $v$. Mark $v$ as deleted. Replace $v$ in $N\[x\]$ with $y$. Replace $v$ in $N\[y\]$ with $x$. Note that $T$ remains a tree after the procedure.

**Helper procedure** to delete a leaf: Suppose $v$ is a leaf that is connected to $u$. If $u$ is a leaf, just return. Otherwise, do the following. Mark $v$ as deleted. Delete $v$ from $N\[u\]$. If the degree of $u$ is 2, apply the procedure above to delete $u$.

**Main Procedure**:

1. Delete all vertices of degree 2.

Now each vertex is either a leaf or connected to two or more other vertices.
2. Let $S$ be an empty list. Loop the following.

1. Find a pair of leaves the distance between which is at least 3. Let them be $u$ and $v$. Add edge $(u,v)$ to $S$. Apply the helper procedure to delete $u$ and $v$.
    2. If no such pair can be found, break the loop.
3. Now $T$ has no path of length 3 and each vertex of $T$ is either a leaf or connected to two or more other vertices. There are two cases.

* $T$ has only one edge. Let it be $(u,v)$. Add edge $(u,v)$ to $S$. (If we add the edge $(u,v)$ in $S$ to the tree, we will have two edges connecting $u$ and $v$. This is the only place where we introduce a parallel edge.)
    * $T$ has three or more edges. $T$ must be a star graph. Let the center vertex be $u$ and other vertices be $v\_1, \cdots, v\_m$. If $m$ is even, add edges $(v\_1, v\_2)$, $(v\_3, v\_4)$, $\cdots$, $(v\_{m-1}, v\_{m})$ to $S$. If $m$ is odd, add edges $(v\_1, v\_2)$, $(v\_3, v\_4)$, $\cdots$, $(v\_{m-2}, v\_{m-1})$ as well as edge $(v\_1, v\_m)$ to $S$.

### Implementation of the algorithm

There are a few ways to implement step 2.1.

A naive way to find a pair of such leaves is to do a depth first search from any vertex.

In order to find such pair of vertices faster, we can also select any two neighboring internal node $x$ and $y$. The edge $(x,y)$ splits $T$ into two subtress, one part that has $x$ and the other part that has $y$. We can pair any leaf of $T$ in one part with any leaf of $T$ in the other part. We can do this recursively.

### Exercises

**Exercise 1.** If an edge set $S$ doubly connects a tree $T$, then then $|S|\ge\lceil n/2\rceil$. (Hint, each leaf of $T$ must be an endpoint of some edge in $S$.)

**Exercise 2.** Use the notations in the algorithm. Show the algorithm is correct by verifying the following.

1. For an iteration in step 2, let $T\_s$ be $T$ at the start of the iteration and $T\_e$ be $T$ at the end of the iteration and $e$ be the edge added to $S$. If $B$ doubly connects $T\_e$, then $B\cup \\{e\\}$ doubly connects $T\_s$.
2. In step 3, edges added in step 3 doubly connects $T$.
3. At the end of algorithm, $|S|=\lceil n/2\rceil$.

**Exercise 3.** Modify the algorithm so that no parallel edge is needed unless $n=2$.

# Answer
> 3 votes
Start by proving the following statement:

> Let $G=(V,E)$ be an undirected graph. There are no $\mathrm{bridges}$ if and only if there are two edge disjoint spanning trees of $G$.

Proof:

1. Suppose there are two edge disjoint spanning trees, $T\_1, T\_2$ of $G$.

Now we remove an arbitrary edge. If it belongs to neither $T\_1$, or $T\_2$, we're done. If it belongs to $T\_1$, it is therefore not in $T\_2 $ (symmetrical for $T\_2$) $\Rightarrow$ $G$ is still connected $\Rightarrow$ there are no $\mathrm{bridges}$ in $G$.
2. Suppose there are no two edge disjoint spanning trees. Then there is at least one cut $C^\*$ of $G$ s.t $C^\*=\\{A, \bar{A}\\}$ and $\delta(C^\*) \leq 1$. Otherwise it is easy to constructively show there are two spanning trees.

Let $e$ denote the edge between $A$ and $\bar{A}$. Since $e$ is the only edge connecting the two subsets, by removing it, $G$ is separated into two unconnected componenets, therefore $e$ is a $\mathrm{bridge}$

---

If you can add any edge you want, simply extend $G$ s.t there are two edge disjoint spanning trees. If you start from a tree, it means you have exactly $n-1$ edges, and to create another distinct spanning tree you would have at least $n-1$ additional edges.

If you can't add any edge you want, see http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf by Tarjan on disjoint spanning trees (with algorithm)

---
Tags: graphs, trees
---


# Question
Title: Basic second-order logic example contains a mistake?
I'm reading the following course on second-order logic, by Péter Mekis : http://phil.elte.hu/mekis/sol.pdf . The course seems excellent, but I'm stuck on one of his first examples for showing the power of second-order logic w.r.t first-order logic.

In this example, he works on the following statement : "Santa Claus has all characteristic properties of a pedophile." This is translated into the second-order logic sentence : ∀X ( R(X,P)→P(a) ), where a is santa, P is the property of being a pedophile, X is a property and R tells us whether a property is characteristic of another property.
I understand this as : for all properties, if a property is characteristic of being a pedophile, then santa is a pedophile. This is obviously not what the statement says, so am I misunderstanding or should the second-order logic sentence instead be : ∀X ( R(X,P)→X(a) ), effectively meaning : for all properties, if the property is characteristic of being a pedophile, then santa has this property.

# Answer
Yes, the example contains a mistake. The statement $\forall X (\mathcal{R}(X,P)\rightarrow P(a))$ is in fact equivalent to $P(a)$, under the assumption that $\mathcal{R}(X,P)$ is true for at least one $X$.

So indeed, the example should be $\forall X (\mathcal{R}(X,P)\rightarrow X(a))$, as you state. Perhaps the author would not have made this mistake if they had chosen a class of people that would be described by another letter than $P$.
> 4 votes

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


# Question
Title: Proving that L is not regular using closure properties
I need to show that the following language is not regular.

$$L = \\{\ ab^jc^j\ |\ j \geq 0\ \\}\ \cup\ \\{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \\}$$

There is also a hint that it cannot be proven just with using the Pumping Lemma. Closure properties must also be used.

I'm having a hard time with this one. Any help would be appreciated.

# Answer
> 2 votes
Let $ L\_1 = \\{\ ab^jc^j\ |\ j \geq 0\ \\} $ and $ L\_2 = \\{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \\} $. Then

$$ L = L\_1 \cup L\_2. $$

If we take $$ \begin{align} L\ \cap\ ab^\*c^\* &= (L\_1\cup L\_2) \cap ab^\*c^\* \\ &= (L\_1\cap ab^\*c^\*)\ \cup\ (L\_2 \cap ab^\*c^\*)\\ \end{align} $$

Since $L\_1\cap ab^\*c^\* = L\_1$ and $L\_2 \cap ab^\*c^\* = \emptyset$, we have

$$ L\ \cap ab^\*c^\* = L\_1 $$

Now, $ab^\*c^\*$ is regular, and $L\_1$ is not regular (can be shown using the Pumping Lemma). If $L$ was regular, by the closure properties, $L\_1$ would be to, which is a contradiction. Hence, $L$ is not regular.

# Answer
> 1 votes
Here is a further hint. $L$ consists of two parts. One of them as a language by itself is not regular. Can you see which part?

Can you carve out that part as the intersection of $L$ with another regular language?

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


# Question
Title: Can a transcript change dependent random variables into independent variables?
Let's say $X, Y$ are *dependent* random variables. Can I find an example such that for a transcript $t$ conditioned on a communication protocol $\Pi=t$, the variables become independent?

# Answer
Yes. Consider the following protocol. Alice flips a coin, and sets $X$ and $Y$ to be equal to the outcome of the coin flip. She then sends $X,Y$ to Bob. Note that the transcript will include the value of $X,Y$.

Now unconditionally, $X,Y$ are dependent (there is probability $1/2$ that they are Heads,Heads and probability $1/2$ that they are Tails,Tails). But conditioned on the transcript, $X,Y$ are independent (e.g., if the transcript says they are Heads, then with conditional probability $1$ they are Heads,Heads and all other cases have conditional probability $0$; that meets the definition for independence).
> 1 votes

---
Tags: communication-protocols, communication-complexity
---


# Question
Title: How do I determine if this argument is valid?
I'm studying propositional logic the section on "valid arguments".

A self-assessment question reads

"Show whether or not the following argument is valid"

$\frac{P}{C}$

I don't know what function to apply to P to calculate C.

The solution in the back of the book shows the following truth table:

```
Variables   Premise Conclusion
P       C      P        C
F       F      F        F
F       T      F        T
T       F      T        F  <--
T       T      T        T

```

So the conclusion is that the argument is invalid because the premise is true and the conclusion false.

I understand that of course, but how do I calculate Conclusion? Do I just guess what it should be?

My teacher had the following to say:

> If P is True, C is True. If P is False, C is False.
>
> Swap it for 'Premise - I am thirsty' & 'Conclusion - I drink some water'
>
> The conclusion is dependant on the premises. If there is only one, they \> will never differ and a Conclusion will never be False, with a True Premise.

This answer flies in the face of the answer in the book.

I pointed this out to my teacher and got the following:

> My understanding is that P is the only variable; C is the conclusion that represents what P might be i.e True or False, once evaluated.

So... in conclusion I find myself still confused

# Answer
> 0 votes
The argument $\frac{P}{C}$ means "If we assume that $P$ is true, we can prove that $C$ is true." For example, $\frac{A}{A\lor B}$ because, if you can prove that $A$ is true, then $A\lor B$ is also true: there's no way that $A$ can be true but $A\lor B$ can be false at the same time.

In the argument you've been give, $P$ and $C$ are completely unrelated. There is a way that $P$ can be true and $C$ can be false at the same time: specifically, $P=\mathrm{true}$, $C=\mathrm{false}$. Therefore, the argument is not valid.

You don't calculate the conclusion, *per se*. rather, you look for a situation in which the premise is true but the conclusion is false. If you can find such a pair of premise and conclusion, the argument is invalid. Conversely, if you can prove that the premise being true always makes the conclusion true, the argument is valid.

I don't understand what your teacher is trying to say. It's not enough to show that the argument is valid for one particular instantiation of $P$ and one particular instantiation of $C$. "Valid" means it works for all instantiations. Also, the examples of $P$ being "I am thirsty" and $Q$ being "I drink some water" doesn't work. There are situations where you are thirsty but you don't drink water (maybe you drink nothing; maybe you drink juice), and situations where you're not thirsty but you do drink water (maybe you're Mark Zuckerberg at a Senate hearing), as well as situations where you're thirsty and drink, or not thirsty and don't drink.

---
Tags: propositional-logic
---


# Question
Title: Run Length Encoding Compression With Nested Level
I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:

ABABABCABABABC --\> 3(AB)C3AB(C) --\> 2(3(AB)C) ?

It's easily to decompress it by using some techniques like stack, but what is the most efficient way to compress it, any formal algorithms or how to evaluate that?

# Answer
Yes. The Sequitur algorithm could be viewed as doing more or less what you've asked for.

For instance, Sequitur would encode abababcabababc to the grammar

S → WW
T → ab
U → TT
V → UT
W → Vc

You can think of this as having your form. V is basically an encoding of 3(ab). W is basically an encoding of 3(ab)c. WW is basically an encoding of 2(W). So, the final grammar is equivalent to 2(3(ab)c) -- it is just a different way to write it. Sequitur writes the output as a context-free grammar, instead of using your notation, but its grammar is equivalent to the answer you were hoping for.

---

Here is the sequence of steps that Sequitur would use to reach that result.

First, we have the grammar

S → abababcabababc

The first digram encountered is ab, so it replaces that with a non-terminal:

S → TTTTcTTTc
T → ab

Then this becomes

S → UTcUTc
T → ab
U → TT

and then to

S → VcVc
T → ab
U → TT
V → UT

and then to

S → WW
T → ab
U → TT
V → UT
W → Vc
> 2 votes

---
Tags: data-compression
---


title: What is a 'Key' in computer science?

text:
# Question
Title: What is a 'Key' in computer science?
I'm a bit confused on what exactly the meaning of a 'key' is in computer science. I understand key-value pairs, primary keys, etc... But I can't find a definition of what the term 'key' means by itself.

As far as I can tell it just means a piece of data. In CLRS, data associated with tree nodes are referred to as 'keys'. Data to search a hash table is called a 'key'. Is this what a 'key' is?

# Answer
> 31 votes
In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with.

In the contexts you mention, a key is a **unique identifier** for the complete data used to retrieve it from some location in the structure. Each key is associated with only one item, so it can be used to find a particular set of data. The data structure will usually be organized in such a way that finding the key is much more efficient than a linear search through all of the data. Sometimes the key is actually part of the data and stored along with it (like primary keys in the database); other times, it is segregated from the data itself (like in a hash map). The data structure will also often perform extra processing on the key (and only the key) to support its efficient searching algorithm (such as in a hash map, the key is converted into a hash code, or a database will index the primary keys using a B-tree).

In cryptography, a key is used in a sense more akin to physical keys used on locks. They're pieces of data required to obtain the original from the encrypted data (to "unlock" the data, so to speak).

# Answer
> 13 votes
A *key* in the context of data structures (such as in the book CLRS) is a value (often an integer) that is used to identify a certain component of a data-structure. Often, keys determine how the underlying data is stored or manipulated. For example, in *binary search trees* we have that for every node, the key of that node is larger than the keys in the left sub-tree and smaller than those in the right subtree. This property makes it easier to search for a given key (or determine there is no node with such a key).

In practice, our 'actual' data is often not a key, but something larger and more relevant that a single number. This data is called *satellite data* and can be mostly ignored when dealing with manipulations on data structures, as long as the satellite data moves whenever the key gets moved (otherwise, you lose track of your data).

---

The concept of a key is similar in the context of databases, but there it is often required that a key is *unique*. A primary key has to be unique, for example. This requirement is often nessecary in the context of data-structures, but is sometimes made for simplicity.

In cryptography, a key usually refers to an (often secret, but not always!) parameter that is needed to encrypt or decrypt with a given en- or decryption algorithm. The keys used to encrypt and decrypt have to be 'related' (in symmetric cryptography, the need to be the same) for the process to encryption or decryption to be successful.

---
Tags: terminology
---


# Question
Title: What are the sufficient conditions for a grammar to be unambiguous?
There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?

For example, if I'm not mistaken, it can be algorithmically checked if a grammar contains no conflicts under LR(1), LALR(1) or LL(1); if so, is there any implication like "If the grammar has no conflicts under LL(1) then it is unambiguous" or something like that?

# Answer
If you can construct a deterministic parser corresponding to a grammar, then the grammar is clearly the unambiguous. (If it were ambiguous, there would need to be a point in some parse which admitted more than one parse action, violating the presumption of determinism.)

All of the algorithms you mention for constructing a parser either produce a deterministic parser for a grammar or report conflicts. So the absence of conflicts implies unambiguity.

Note that there might exist parsing algorithms which produce parsers which do not precisely correspond to the grammar. For example, yacc/bison use an algorithm which resolves conflicts, either using precedence declarations or through some default resolution rules. The resulting parser is then unambiguous, but it is no longer capable of producing the same set of derivations as the original grammar. Indeed, it might not even be able to recognise the same sentences.
> 3 votes

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


# Question
Title: Is this problem that's similar to integer linear programming also an NP-complete problem?
I've come across this problem while trying to work out a table-formatting algorithm.

It's very similar to standard linear programming (though it uses $\>$ instead of $\<$; I'm not extremely familiar with linear programming, but I believe this doesn't matter much).

Let $\vec v = (v\_1, \dots, v\_n)$ be a vector of positive-integer variables.

The problem is to find if there is an assignment to $\vec v$ such that

$$ v\_1 + \dots + v\_n = c $$

and

$$ A \vec v \geq \vec w $$

where $c$ is a known constant, $\vec w$ is a known constant, and $A$ is a matrix with the special property that each row of $A$ is of the form $(0, \dots, 0, 1, \dots, 1, 0, \dots, 0)$.

That is, each inequality constraint only uses coefficients 1 and 0, and only "consecutive" variables appear in each linear constraint.

---

I think that this problem is NP-complete, but I haven't been able to prove it.

I think a reduction to exactly-1-in-3-SAT or set-cover is most likely to succeed (variables would be literals/values respectively and rows in the matrix would correspond to clauses/sets), but the restriction that constraints only refer to consecutive variables doesn't seem strong enough to describe arbitrary clauses/sets.

Alternatively, I might be wrong, and this problem actually has an algorithm that I have been missing. (The problem I'm actually interested in solving is finding the smallest $c$ such that constraints remain satisfiable, but I've phrased the problem this way so that it remains a simple decision problem)

---

As an example, here's a small instance of this problem:

$$ \begin{array}{} v\_1 + v\_2 + v\_3 + v\_4&=& 10 \\ v\_1 &\geq& 1 \\ v\_2 &\geq& 1 \\ v\_2 + v\_3 &\geq & 3 \\ v\_3 + v\_4 & \geq & 4 \\ v\_3 &\geq& 1 \\ v\_4 &\geq& 1 \end{array} $$

which has a possible assignment $\vec v = (1, 1, 6, 2) $.

# Answer
> 3 votes
Your problem is solvable in polynomial time.

Your problem is equivalent to ILP with difference constraints, i.e., every linear inequality has the form $x\_j - x\_i \ge c\_{i,j}$. (Why? Set $x\_i = v\_1 + \dots + v\_i$; then $v\_{i+1} + \dots + v\_j = x\_j - x\_i$.)

Such a system of inequalities can be solved with shortest-path algorithms. In particular, if we didn't have the restriction to integer values, this becomes the standard problem of solving a system of difference constraints. You can solve this by creating a graph with one vertex per variable and one edge per constraints, and finding shortest paths using Bellman-Ford. See, e.g., Algorithms: Difference Constraints, Decide whether a set of inequalities is solvable, http://videolectures.net/mit6046jf05\_demaine\_lec18/, or a good textbook (I think this is described in CLRS).

As stated, those algorithms don't take into account the restriction to integer solutions. But if you examine how shortest path algorithms work, if all of the constants are integers, then the solution will be an integer solution as well. So, that ensures you get an integer solution.

Lastly, the requirement that $v\_1 + \dots + v\_n = c$ is equivalent to $x\_n = c$, which can be handled using the shortest paths algorithm. In particular, find a solution; then if $x\_n \ne c$, then set $c' = c - x\_n$ and add the constant $c'$ to all variables; the result will be another solution that satisfies all the inequalities, and also satisfies the equality $x\_n = c$.

Finally, once you've solved to find a solution for the $x$'s, you can recover a solution for the $v$'s by setting $v\_i = x\_i - x\_{i-1}$.

One catch is that this solution might not be all positive. To handle this, I suggest adding the inequalities $x\_i - x\_{i-1} \ge 0$ before solving. That will then meet all of your needs.

---
Tags: np-complete, integer-programming, constraint-satisfaction
---


# Question
Title: when can i detect the position of error in hamming code
I have 4-bit data with the hamming code `0010011`.
the parity parameters are: `p1=0 , p2=0 , p3=0`
and the check codes are: `c1 = 0 , c2 = 1 , c3 = 0`
so I thought that I have an error in position 2 of my data but the solution says that I can not detect the position of the error.
my question is: when I can find the position of an error in hamming code?

# Answer
> 2 votes
You can never detect the positions of errors with certainty.

You can make *the assumption* that there is at most a single bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in only one bit position; if there is exactly *one* such data then you know where the error is (under your assumption).

You can make *the assumption* that there is at most a double bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in at most two bit positions; if there is exactly *one* such data then you know where the error or errors are (under your assumption).

---
Tags: error-correcting-codes, hamming-code
---


# Question
Title: What is the intuition behind a Free-Choice Petri Net?
So I've found this definition in a paper called `Time and Petri Nets, Popova-Zeugmann, L.`, but I am unable to understand the intuition behind it.

> N is a free-choice net (FC net) if each shared place is the only pre- place of its post-transitions, i.e., $\text{if}\ t, t' ∈ p^•\ \text{then}\ ^•t\ =\ \\{p\\}\ =\ ^•t'$.

Could someone give me an example of what this allows to, or disallows to do?

# Answer
The literature on Petri nets has many papers that really aim to teach the concepts used.

In the case of *free-choice Petri net*, such an introduction can be found in the paper *Structure Theory of Petri Nets: the Free Choice Hiatus* by Eike Best, in the ACPN (Advanced Course on Petri Nets) 1986. (An online copy is here.)

If anywhere, the *intuition* behind free-choice nets should be explained there, but that doesn't really happen, and I haven't seen such an explanation elsewhere, either.

As far as there is an intuition behind free-choice nets, it is expressed by their name: whenever there is a choice, say, between step *B* or step *C* (that is to say: we have a place *A* with an arc to transition *B* and an arc to transition *C*), then that choice is *free*, that is to say, neither *B* or *C* are subject to any other additional conditions (that is to say, they cannot have additional input places).

Rather than focusing on intuition, the paper describes free-choice nets as follows, and I think this is the standard way to explain them:

1. One of the reasons Petri nets interest us is that they offer descriptions of concurrent system behaviour that can be statically analyzed. We can *prove* certain properties of the behaviour of Petri nets.
2. However, for unrestricted Petri nets, certain important properties are extremely hard to analyze; for instance, the question whether the net is live, or whether a given marking can be reached. So it is interesting to study *restricted* forms of Petri nets for which such analysis is easier.
3. One possible restriction is to say: no place may have more than one input transition, or more than one output transition. This type of Petri net is called an *S-net*. This eliminates parallelism and basically turns the net into a state machine. For instance, we can no longer write down a process in which the first thing to happen is *A*, then *B* and *C* in whatever order, and, finally, *D*. We can't put *B* and *C* in parallel.
4. Another restriction is the reverse: no transition may have more than one input place or more than one output place. This type of Petri net is called a *T-net* or marked graph. Now, we do have parallelism, but we no longer have *choice*. For instance, we can no longer write down a process in which the first thing to happen is *A*, then either *B* or *C*, and, finally, *D*. We can't have a choice between *B* and *C*.
5. Both restrictions are very severe, so it's interesting to look at compromises. Free-choice nets are just that: to quote Wikipedia, *they are the nets in which every arc from a place to a transition is either the only arc from that place or the only arc to that transition. I.e. there can be both concurrency* (parallelism) *and conflict* (choice), *but not at the same time*. So this is a proper generalization of S-nets and T-nets.
6. Certain properties of the behaviour of Petri nets that are hard or impossible to decide for arbitrary Petri nets become doable for free-choice Petri nets.

So the prime motivation for free-choice nets is not any particular intuition, but the fact that they allow certain forms of static analysis of behaviour.
> 2 votes

---
Tags: petri-nets
---


title: lambda calculus with church numerals

text:
# Question
Title: lambda calculus with church numerals
today I found this term in our exercises: ((^fx.f(f(f x)) ^gy.g(g y )) ^z.z + 1) (0)

I am quit unaware how to solve this type of question. I know this is the church numeral 3 , 2 , the identity function +1 and zero. But for my understanding it lacks an operator like +-\*/ as ex.

(λmn.m (succ n)) to connect two church numerals?

Some hints will be greatly appreciated.

# Answer
Your term is the application $3\ 2\ succ\ 0$, where $succ$ is the successor function.

If you task is to reduce this term to a beta normal form:

First we can observe that for terms $M$ and $N$, the application $MN$ beta-reduces to the $M$-fold application of $N$, which is

* in the case of $N$ an operation: the $M$-fold application of the operation $N$ to whatever term $P$ the term $MN$ is applied to; i.e., $MNP$ is $\underbrace{N(N(...N(}\_{M\text{ times}} P)))$,
* in the case of $N$ a church number: the (church number representation of the) exponentiation of $N$ with $M$; i.e, $MN$ with $M,N$ numbers is $N^M$.

as you can easily verify with simple numbers like $2$ and $3$.

So $3\ 2$ is $2^3$, which beta-reduces to $8$, and $3\ 2\ succ$ creates an 8-fold application of $succ$, which is then applied to $0$.
So your term is the $2^3$-fold = $8$-fold application of the $succ$-function to the number $0$, that is, $\underbrace{succ(succ(...succ(}\_{8 \text{ times}} 0)))$, which eventually beta-reduces to the church number $8$, $\lambda fx.f(f(f(f(f(f(f(f(x))))))))$.
> 4 votes

# Answer
Essentially your term is the application $3\ 2\ {\sf succ}\ 0$. So we start performing beta reduction steps. Since $3\ f\ x = f(f(f x))$, we get $2\ (2\ (2\ {\sf succ}))\ 0$. From here, we get $(2\ (2\ {\sf succ}))\ ((2\ (2\ {\sf succ}))\ 0)$. And so on -- I'll leave the steps to you.

If I see correctly, after a long-ish sequence of beta steps we should reach the numeral $8$ as a normal form. Try checking that $(2\ (2\ {\sf succ}))\ 0 = 4$, and after that check that $(2\ (2\ {\sf succ}))\ 4 = 8$.
> 2 votes

---
Tags: lambda-calculus, functional-programming, church-numerals
---


title: Operator name in LL(1) computation

text:
# Question
Title: Operator name in LL(1) computation
I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(1).

The definition requires the disjointness of certain sets; each set is defined as an infinite limit, but practically calculated via fixed-point iteration of an inductive, case-based equation.

Present in these equations is the definition of a new operator to simplify the notation (let $\epsilon$ be the empty sequence):

$$\forall S,T : S \oplus T = \begin{cases} S & \epsilon \not\in S \\ (S \setminus \\{\epsilon\\}) \cup T & \epsilon \in S \end{cases}$$

I know this operator in latex as `\oplus`. In an attempt to write readable-code, I want to give this operator a name (and endow scala `Set`s with a trait that expresses this name).

Is there a traditional name for this usage of $\oplus$? If so, what is it?

Bonus points: if the name is, e.g., *add*, is there an acceptable word like *addable* with the meaning that two objects—mathematical or code—are capable of being *added*?

# Answer
> 2 votes
A set of values that comes with an "add" operation that is associative is called a semigroup. If it also comes with an element that plays the role of 0 (so that 0 + x = x and x + 0 = x for all x), it is a monoid.

In your case, you have a monoid, as $\\{\epsilon\\}$ plays the role of 0 (it is an identity).

# Answer
> 2 votes
D.W.'s answer is excellent, and gave me a rabbit hole to dig through. The operator clearly establishes a magma, being a closed binary operator. I was able to construct a proof1 that $\oplus$ as defined is associative; thus, the definition gives (at least) a semigroup.

Further, I claim the following: Given any domain (call it the type $A$) and an element $a \in A$, parameterize $\oplus$ on $a$ such that

$$\forall S,T \in \mathcal{P}(A) : S \oplus\_a T = \begin{cases} S & a \not\in S \\ (S - \\{a\\}) \cup T & a \in S \end{cases}$$

The resulting object $(\mathcal{P}(A), \oplus\_a)$ is a semigroup.

I have also shown that $\oplus\_a$ is not commutative, for let $X$ be some set not containing $a$ and $Y \neq (X \cup \\{a\\})$ be a set containing $a$: then $X \oplus\_a Y = X$, but $Y \oplus\_a X = (Y - \\{a\\}) \cup X \neq X$.

So the resulting object cannot be an Abelian group.

Proofs remain to be had regarding the (non)existence of an identity or the (non)invertibility. If identity can be shown, we have a monoid. If invertibility can be shown, we have an inverse semigroup. If both, then a full group.

The identity element, as pointed out by D.W., is $\Phi = \\{a\\}$. Put simply:

$$\forall S \in \mathcal{P}(A) : \Phi \oplus\_a S = (\Phi - \Phi) \cup S = S$$ $$\forall S \in \mathcal{P}(A) : S \oplus\_a \Phi = \begin{cases} S & a \not\in S \\ (S - \Phi) \cup \Phi = S & a \in S \end{cases} \big\\}= S$$

So we have a monoid.

---

1 Proof of associativity is sketched as follows: we must show that $\forall X,Y,Z \in \mathcal{P}(A) : (X \oplus Y) \oplus Z = X \oplus (Y \oplus Z)$.

Now we consider that each of these sets has two states: it either contains or does not contain $a$. Because we need three two-bit states to represent the problem space (the set of cases), we have 7 cases, which we represent as a binary tuple $xyz$. If an element is $0$, it indicates that the corresponding set contains $a$ in the equation. If it is a $1$, it indicates that the corresponding set does not contain $a$ in the equation.

Finally, let $X^0$ be the set $X$ containing $a$ for each of our sets, and $X^1$ similarly be the set not containing $a$. Let $XY = X \cup Y$.

A few facts:

* $X^0 \oplus Y^0 = X^1Y^0$
* $X^0 \oplus Y^1 = X^1Y^1$
* $X^1 \oplus Y^0 = X^1 \oplus Y^1 = X^1$
* $X^1Y^1 \oplus Z^0 = X^1Y^1 \oplus Z^1 = X^1Y^1$

The cases are left as an exercise to the reader; they are incredibly straightforward.

*Hint:* $001$ follows from $000$. Similarly, $011$ follows from $010$. Both $101$ and $111$ follow from $100$.

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


# Question
Title: Fewest traversals to visit all vertices of DAG
I want to find the fewest traversals to visit all vertices of a DAG. To take a very simple case:

```
Boston -> New York   -> San Francisco or Las Vegas, both to -> LA
       -> Pittsburgh -> San Francisco or Las Vegas, both to -> LA

```

There are lots of ways to traverse this graph, but to visit every vertex, you only need:

```
1. Boston -> New York   -> San Francisco -> LA
2. Boston -> Pittsburgh -> Las Vegas     -> LA

```

I have no preferences in how the graph is visited, and it's fine to visit the same vertex multiple times during different traversals.

(Real application: I am generating test cases for human testers and want them to help them perform their tests at every 'vertex' with as few run-throughs as possible.)

# Answer
> 2 votes
I think you can solve this problem by reducing it to a minimum-cost circulation problem.

Let $G$ be your graph. Replace each vertex $v$ with two vertices $v\_\text{in},v\_\text{out}$; replace each edge $u \to v$ into $v$ with an edge $u \to v\_\text{in}$ and each edge $v \to w$ out of $v$ with an edge $v\_\text{out} \to w$, and add the edge $v\_\text{in} \to v\_\text{out}$. Add a new source vertex $s\_0$ and a new sink vertex $t\_0$. For each vertex $v$ in your graph, add an edge $s\_0 \to v\_\text{in}$ and an edge $v\_\text{out} \to t\_0$. Finally, add an edge $t\_0 \to s\_0$. All edges have cost 0, lower bound 0, and upper bound $\infty$, except that all $v\_\text{in} \to v\_\text{out}$ edges have lower bound 1 and the $t\_0 \to s\_0$ edge has cost 1.

Now, find the minimum cost circulation in this graph. There are polynomial-time algorithms to do this.

I claim that this minimum-cost circulation corresponds to the minimal set of paths to cover all the verticies. In particular, if the minimum cost circulation has cost $c$, then that means there will be $c$ paths that cover the vertices. This circulation will have total flow $c$, so you can trace where each of the $c$ units of flow go starting from $s\_0$ to $t\_0$, and that will trace out a path; take those $c$ paths as your collection of paths. By the way I defined the lower bounds, this ensures that each vertex will be covered by at least one of these $c$ paths.

# Answer
> 2 votes
This is the classical problem of chain decomposition of partially ordered set (poset), in the sense that they can be reduced to each other very easily.

Any directed acyclic graph (DAG) $G(V,E)$ defines a poset $P(V, \preceq)$ naturally by $u\preceq v$ for any pair of vertices $(u,v)$ such that there is a path from $u$ to $v$ in $G$. A path (which is named traversal in the question) in $G$ corresponds to a chain in $P$ naturally. A set of paths whose union covers all vertices means exactly that the corresponding set of chains is a not-necessarily-disjoint chain decomposition of $P$.

Note that it is straightforward to modify a not-necessarily-disjoint chain decomposition of $P$ to a disjoint chain decomposition of $P$. Conversely, we can insert vertices between the vertices that correspond to a chain in $P$ so that they become a path in $G$.

There are efficient algorithms to compute a chain decomposition of a poset such as On the Decomposition of Posets by Yangjun Chen and Yibin Chen, 2012. In that paper a poset is, in fact, given by a DAG in the first place.

This is the perfect time to present the very nice **Dilworth's theorem**: for any finite poset the largest antichain has the same size as the smallest chain decomposition. It says that, for the situation in the question, the minimum number of traversals needed to cover all cities is the maximum number of cities that are pairwise unreachable to one another. Note that New York and Pittsburgh are not reachable from each other.

---
Tags: algorithms, graphs, graph-traversal, dag
---


# Question
Title: ZigZag sequence without dynamic programming
I just came across the maximum zigzag sequence problem, defined as follows:

> A zigzag sequence is defined as a sequence of numbers such that the difference between two consecutive numbers alternates between positive and negative.
>
> Given a an array of N integer number, find the length of the longest zigzag subsequence. A subsequence is formed by deleting zero or more elements of the original sequence, but preserving the order in the original sequence.
>
> For example given the array {1, 2, 4, 2, 3, 5, 1} the subsequence {1, 4, 2, 5, 1} is the longest zigzag.
>
> A sequence of one element is a trivial zigzag of length 1.

I've found several references to a dynamic programming formulation of the solution which is O(N^2) and very complex. See for example this.

However, I've come with a much simpler solution with O(N) and based on finding all the local maximum and minimum of the original sequence, that is, the elements of which the sign of the difference between consecutive elements change. Here is the code in Java:

```
public static int zigZagLength_pablochacin(int[] sequence) {

    if (sequence.length == 0)
        return 0;

    int lastDiff = 0;
    int length = 1;

    for (int i = 1; i < sequence.length; i++) {
        int diff = Integer.signum(sequence[i] - sequence[i - 1]);
        if ((diff != 0) && (diff != lastDiff)) {
            lastDiff = diff;
            length++;
        }
    }

    return length;
}

```

Apparently,this approach has also been proposed elsewhere.

**My question is, am I missing something that makes this simple solution wrong?**

Note: I originally asked this question in Code review Stack, but was considered off-topic, as it doesn't relate to code style but to the solution.

# Answer
> 1 votes
Your simple algorithm is correct.

In fact, you have proved the correctness of your algorithm basically since your algorithm is, as you have written, based on finding all the local maximum and minimum of the original sequence. The simple mathematical reason is that for each zigzag, i.e., $a\[i\]\<a\[i+1\]\>a\[i+2\]$ or $a\[i\]\>a\[i+1\]\<a\[i+2\]$, there must exist a local maximum or a local minimum respectively.

A more rigorous and rather tedious proof is needed to convince all of us that there is no off-by-one error in your program. However, I will skip it since it is routine and not enlightening at all.

---
Tags: time-complexity, dynamic-programming, subsequences
---


# Question
Title: Proof that POSITIVE-3-SAT is in the complexity class P
I have the following language:

$$\text{POSITIVE-3-SAT} = \\{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of exactly 3 literals and in which no variable appears negated}\\}.$$

---

Progress so far:

My concern is that I have not understood the task. I have proposed what I think is a (near trivial) proof.

To show that the language is in **P**, my approach is to provide a deterministic algorithm which can decide the problem in polynomial time.

By definition, $\text{POSITIVE-3-SAT}$ must comprise of an arbitrarily long number of conjunctions of clauses of the form $(\lambda\_1 \lor \lambda\_2 \lor \lambda\_3)$. Each clause is trivially satisfiable in the case that a truth value of TRUE is assigned to any of the clauses $\lambda\_1, \lambda\_2, \lambda\_3$. On this basis, each clause containing 3 literals can be decided in $O(3)$ steps, $\equiv O(1)$.

If we make the assumption that the language is constrained to only contain a finite number of $n$ clauses, then we can say that the satisfiability of the language can be decided in $O(n) \equiv O(n^1)$ steps.

Thus, $\text{POSITIVE-3-SAT}$ can be decided by a deterministic algorithm in polynomial time.

Thus, $\text{POSITIVE-3-SAT} \in$ **NP**.

# Answer
> 1 votes
It looks like you misunderstood a bit what you should prove since you missed the much easier way to prove although your (trivial) proof looks correct.

### An easier proof

Let us call a boolean formula in conjunctive normal form in which all clauses consist of exactly 3 literals and in which no variable appears negative a positive‑3 formula. So

$$\text{POSITIVE-3-SAT} = \\{\langle\phi\rangle \mid \phi\text{ is a satisfiable positive-3 formula}\\}.$$

Note that any positive‑3 formula is satisfiable since it becomes TRUE if a truth value of TRUE is assigned to all variables. So

$$\text{POSITIVE-3-SAT} = \\{\langle\phi\rangle \mid \phi\text{ is a positive-3 formula}\\}.$$

Here is an algorithm $\mathcal A$. Given an input string $s$, $\mathcal A$ just verifies whether $s$ is the encoded form of a positive-3 formula. If $s$ is, $\mathcal A$ returns yes; otherwise, $\mathcal A$ returns no. That verification step can be done in linear time in terms of the number of clauses in $s$. So $\text{POSITIVE-3-SAT}$ is in **P**.

---

The moral of the above proof is that you can use whatever known to you to construct the algorithm. All you need is to specify an algorithm and show that it works as wanted.

It depends on the requirement/convention/stage of your course or the intention of your course instructor whether you needs to explain in detail why that verification can be done in linear time or polynomial time. It looks like that verification step is totally ignored by the proof in the question, which is, in fact, a general accepted practice in the field.

# Answer
> 0 votes
Yes, your proof seems to be correct. However note that a SAT instance with no negated clause is always satisfable by boolean algebra's axioms, you only need to assign the value "true" to all of them, so your Language is verifiable by definition (it is a bit like prooving that x+y+z+...\>0 or x*y*z\*....\>0 is always verifiable in Peano's Arithmetic).

---
Tags: satisfiability, 3-sat, normal-forms
---


# Question
Title: Merging and Unmerging Sets of Trees Efficiently
**Background**

Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:

Tree 1:

```
{
  a: {
    b: 1
  },
  c: [{}],
  d: 3
}

```

Tree 2:

```
{
  a: {
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

```

`merge(t1, t2)` would yield:

```
{
  a: {
    b: 1
    z: 1
  },
  c: [
    {
      x: 1
    },
    {
      x: 2
    }
  ],
  d: 4
}

```

Note the overwrite of primitives (`d`).

**Problem**

I'd like to be able to merge some order set of trees like the above (the order is important because of the overwriting of primitives) AND be able to efficiently unmerge one of the trees.

Mathematically, I want two functions $merge$ and $unmerge$ such that the following holds true:

$$ unmerge(merge(t\_1,...,t\_n,...,t\_p), t\_n) = merge(t\_1,...,t\_{n-1},t\_{n+1},...,t\_p) $$

where $p,n \in Z^+$ and $n \leq p$.

Simple solutions like "delete all of the nodes on $t\_n$ from the merged tree" obviously doesn't work in many cases.

More robust solutions like creating immutable copies of the interim trees might would has you could take the cached tree $merge(t\_1,...,t\_{n-1})$ and then merge in the subsequent trees $t\_{n+1},...,t\_p$. However, in the worst-case ($n=1$) this is equivalent to just remerging the entire set; ideally, there would be some less computationally complex solution.

Would love any advice or pointers for further research. Thanks!

# Answer
# One solution

Make trees immutable, using path copying. Give each tree a name. Whenever you create a new tree T3 by merging two trees T1,T2, remember in T3 that it was created by merger of T1,T2 (i.e., include pointers to T1,T2 as part of the auxiliary information in the root node of T3). Also keep track in the auxiliary information for each tree all of the original trees it was transitively created from.

Now, when you want to unmerge a tree, you can look at the auxiliary information to work out what you need to do. When you call unmerge(T, U), look at the auxiliary information for T to find the two trees T1,T2 it was merged from; if U was used to create T1, then

unmerge(T, U) = merge(unmerge(T1, U), T2)

so you can proceed recursively. Similarly, if U was used to create T2, then

unmerge(T, U) = merge(T1, unmerge(T2, U))

The running time of this will be proportional to the maximum "depth" of the merge operations, times the time to merge two trees.

# A more efficient solution

With more sophisticated data structures, you can speed up the unmerge operation so it performs at most $O(\log n)$ merges.

Call a tree "atomic" if it wasn't created by a merge/unmerge. The auxiliary information for each tree T will be an ordered list of the atomic trees T1,..,Tk it was created from, so that T = merge(T1,..,Tk). This list will be stored as a persistent self-balancing binary tree with k leaves, one per atomic tree in the list, ordered in the same way they are in the list. Each node in that self-balancing tree corresponds to an interval Ti,..,Tj of the list (namely, Ti,..,Tj are the set of leaves under that node); add metadata so that node points to the tree produced by merge(Ti,..,Tj). Also, as auxiliary information for tree T, we'll have a map that given the name of a tree U lets you look up where in the list T1,..,Tk that U appears; this can be done with a second persistent self-balancing binary tree with k leaves, ordered by lexicographic order on the names of the atomic trees.

The merge(T1, T2) operation merges the two trees, and constructs its auxiliary information by concatenating the associated lists. Those operations on the self-balancing binary trees can be done in $O(\log n)$ time, so this adds little overhead to the merge operation.

Finally, unmerge(T, U) can be implement as follows. First, we look up where U appears in the associated list for T; suppose U is the ith item in the list T1,..,Tk, i.e., U = Ti. Then we need to compute merge(T1,..,Ti-1,Ti+1,..,Tk). It turns out that this can be done in $O(\log n)$ merges. Why? Well, we look at the path from Ti to the root in the self-balancing tree for T; if we take all of the siblings of the nodes on that path, and merge their associated trees in the correct order, we get merge(T1,..,Ti-1,Ti+1,..,Tk). Since it is a self-balancing tree, its depth is at most $O(\log n)$, so there are at most $O(\log n)$ nodes along that path, so we need to do at most $O(\log n)$ merge operations. Thus, unmerge(T, U) is about $O(\log n)$ times as slow as a merge operation.

---

A final note: there's nothing special here about the fact that the T1,..,Tk are trees. They could have been any value, such as simple integers or anything else. So, you might find it easier to think about this with simple values first. On the other hand, this also means that my algorithm isn't taking into account the fact that the T1,..,Tk are trees; it's possible that data structures that take that into account might be able to be even more efficient.
> 2 votes

---
Tags: algorithms, trees
---


# Question
Title: 3-DNF proves the algorithm is in P class
To understand fully, please read link

After, reading the link we will take a look at how we recover our solutions to a constrained Sudoku Puzzle.

If we assume that a sudoku puzzle was generated with this procedure we can now create a "semi"-solver. I say "semi" because we need the $3 \times 3$ grid $M\_{2,2}$ already solved for us. Let's assume we have this. As an example I will assume we are provided:

$$\begin{bmatrix} 5 & 9 & 6\\ 1 & 2 & 4\\ 3 & 7 & 8 \end{bmatrix}$$

Now we will flatten it into: $\[5,9,6,1,2,4,3,7,8\]$ and permute as follows:

```
[8, 5, 9, 6, 1, 2, 4, 3, 7]-----list 1
[7, 8, 5, 9, 6, 1, 2, 4, 3]-----list 2
[3, 7, 8, 5, 9, 6, 1, 2, 4]-----list 3
[4, 3, 7, 8, 5, 9, 6, 1, 2]-----list 4
[2, 4, 3, 7, 8, 5, 9, 6, 1]-----list 5
[1, 2, 4, 3, 7, 8, 5, 9, 6]-----list 6
[6, 1, 2, 4, 3, 7, 8, 5, 9]-----list 7
[9, 6, 1, 2, 4, 3, 7, 8, 5]-----list 8
[5, 9, 6, 1, 2, 4, 3, 7, 8]-----list 9

```

Now for each list, we will turn them into a $3 \times 3$ grid using the same mapping in step 2 above. For example list 1 would get mapped to

$$\begin{bmatrix} 8 & 5 & 9 \\ 6 & 1 & 2 \\ 4 & 3 & 7 \end{bmatrix}$$

Now we position these in the game board the same way we did as step 3 above. For example our layout would be as follows:

```
**list1**  **list4**  **list7**

**list2**  **list5**  **list8**

**list3**  **list6**  **list9**

```

In the prior example this would give us the correct solution:

$$M = \begin{bmatrix} 8 & 5 & 9 & 4 & 3 & 7 & 6 & 1 & 2\\ 6 & 1 & 2 & 8 & 5 & 9 & 4 & 3 & 7\\ 4 & 3 & 7 & 6 & 1 & 2 & 8 & 5 & 9\\ 7 & 8 & 5 & 2 & 4 & 3 & 9 & 6 & 1\\ 9 & 6 & 1 & 7 & 8 & 5 & 2 & 4 & 3\\ 2 & 4 & 3 & 9 & 6 & 1 & 7 & 8 & 5\\ 3 & 7 & 8 & 1 & 2 & 4 & 5 & 9 & 6\\ 5 & 9 & 6 & 3 & 7 & 8 & 1 & 2 & 4\\ 1 & 2 & 4 & 5 & 9 & 6 & 3 & 7 & 8\\ \end{bmatrix}$$

Then we have list 9 (our input) will always give you correct solution in quadratic time.

For further illustration, I intend to prove that the algorithm aforementioned is in P class in two ways.

Here, we'll take a look at **3-DNF**.

**(L1 ∧ L2 ∧ L3) | (L4 ∧ L5 ∧ L6) | (L7 ∧ L8 ∧ L9)**

Let **L1**=list1, **L2** = list2,...

```
**list1**  **list4**  **list7**

**list2**  **list5**  **list8**

**list3**  **list6**  **list9**

```

Therefore, the algorithm generates grids and recovers correct solutions easily.

Now, lets say I want to check the satsifiability of the algorithm's circular shifts. Here, I generate 3 more grids to show that there is a 3x3 positive *3-satisfying permutes*.

**l = \[8, 5, 9, 6, 1, 2, 4, 3, 7\]**

```
[5, 9, 6, 1, 2, 4, 3, 7, 8]-l1
[9, 6, 1, 2, 4, 3, 7, 8, 5]-l2
[6, 1, 2, 4, 3, 7, 8, 5, 9]-l3
[1, 2, 4, 3, 7, 8, 5, 9, 6]-l4
[2, 4, 3, 7, 8, 5, 9, 6, 1]-l5
[4, 3, 7, 8, 5, 9, 6, 1, 2]-l6
[3, 7, 8, 5, 9, 6, 1, 2, 4]-l7
[7, 8, 5, 9, 6, 1, 2, 4, 3]-l8
[8, 5, 9, 6, 1, 2, 4, 3, 7]-l9

```

**x = \[5, 9, 6, 1, 2, 4, 3, 7, 8\]**

```
[9, 6, 1, 2, 4, 3, 7, 8, 5]-x1
[6, 1, 2, 4, 3, 7, 8, 5, 9]-x2
[1, 2, 4, 3, 7, 8, 5, 9, 6]-x3
[2, 4, 3, 7, 8, 5, 9, 6, 1]-x4
[4, 3, 7, 8, 5, 9, 6, 1, 2]-x5
[3, 7, 8, 5, 9, 6, 1, 2, 4]-x6
[7, 8, 5, 9, 6, 1, 2, 4, 3]-x7
[8, 5, 9, 6, 1, 2, 4, 3, 7]-x8
[5, 9, 6, 1, 2, 4, 3, 7, 8]-x9

```

**y = \[9, 6, 1, 2, 4, 3, 7, 8, 5\]**

```
[6, 1, 2, 4, 3, 7, 8, 5, 9]-y1
[1, 2, 4, 3, 7, 8, 5, 9, 6]-y2
[2, 4, 3, 7, 8, 5, 9, 6, 1]-y3
[4, 3, 7, 8, 5, 9, 6, 1, 2]-y4
[3, 7, 8, 5, 9, 6, 1, 2, 4]-y5
[7, 8, 5, 9, 6, 1, 2, 4, 3]-y6
[8, 5, 9, 6, 1, 2, 4, 3, 7]-y7
[5, 9, 6, 1, 2, 4, 3, 7, 8]-y8
[9, 6, 1, 2, 4, 3, 7, 8, 5]-y9

```

Here, I demonstrate that the 3x3 shift meets satisfiability for 9! Sudoku grids generated by the algorithm. At the end of the question I prove that the expression is always meets satisfiability when given the correct inputs.

*(l1 ∨ x9 ∨ y8) ∧ (l2 ∨ x1 ∨ y9)*

**l1 = \[5, 9, 6, 1, 2, 4, 3, 7, 8\]**

**x9 = \[5, 9, 6, 1, 2, 4, 3, 7, 8\]**

**y8 = \[5, 9, 6, 1, 2, 4, 3, 7, 8\]**

All the listed elements above have their defined variables within these expressions. All the expressions hold true.

> (1∨9∨8)∧(2∨1∨9)∧(3∨2∨1)∧(4∨3∨2)∧(5∨4∨3)∧(6∨5∨4)∧(7∨6∨5)∧(8∨7∨6)∧(9∨8∨7)∧(1∨9∨8)∧(2∨1∨9)

Here is a chart showing the 3-satsifiability of the algorithm. Proving that the 3x3 shift overlaps all 9! valid grids that the algorithm can generate

*Overall, are these proofs correct that constrained Sudoku is in P class?*

# Answer
> 2 votes
As I already explained earlier, any algorithm on a 9x9 input takes constant time. Thus it is in P. This is not very interesting or useful.

When people talk about Sudoku being NP-hard, they don't actually mean Sudoku, they are referring to a generalization on a grid of arbitrary size. Your question doesn't prove that this generalized problem is in P.

General comment: It looks like you're immersed in details, but haven't got a solid grasp on the fundamentals/basics yet. I encourage you to spend some more time learning about the definition of languages, decision problems, P, NP, NP-complete, NP-hard, and reductions before trying to take your Sudoku "project" any further. As it stands some of your statements appear to reflect a misunderstanding of basic concepts, and so you're spending time on things that are a dead end or reflect some basic misconceptions. (For instance, an algorithm can't be in P, and a proof can't be in; a problem can be.) I hope you'll take this as aimed to help you learn, rather than an attempt to criticize you personally or tear you down.

---
Tags: satisfiability, decision-problem
---


# Question
Title: Which would be the most purely functional equivalent to generators?
Some programming languages, apart from functions, have generators (eg. Python's yield). Although generators are introduced in this Python's tutorial on functional programming, I don't think that they can be considered functional programming, because they do have state, and in a vary implicit manner.

Generators are reminiscent of laziness in pure functional languages like Haskell. Apart from laziness, are there other purely functional alternatives for having a construct similar to generators? Do you have any examples?

# Answer
> 2 votes
Functional programming does not have to be pure or stateless. There's no strict rule. Languages that are designed to support first-class functions and higher-order functions can still be considered functional languages. For instance, Standard ML has support for mutable variables but is still considered a functional language.

Also, functional programming can be considered a style of organizing your program rather than a property of a programming language. So, it is possible to use Python in a functional way.

A Python generator can be written in a way so that it is purely functional: e.g., it produces a lazy list/stream and operates in a purely functional way. Internally, generators might be implemented in a way that involves state, but from the outside (from the perspective of code that invokes a generator), I think it is possible to write the generator so it behaves in an observationally pure way (i.e., observationally indistinguishable from pure).

I'm not sure what you mean by "purely functional alternatives for having a construct similar to generators" so I don't know how to answer that part.

---
Tags: functional-programming
---


# Question
Title: Is there a sorting algorithm of order $n + k \log{k}$?
I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example

```
[1, 4, 2, 5, 5, 3, 4, 2, 2, 5]
(n = 10, k = 5)

```

and am asked to find a sorting algorithm that averages $O(n + k\log{k})$. I've concluded that partial quicksort (or quickselsort) might achieve this, but doesn't seem to utilise that the vector contains duplicates. Am i missing some basic algorithms here?

# Answer
Here is an approach:

1. Create a hash map (dictionary in python) with keys being the elements of the vector and the corresponding values being the number of times the the element occurs in the vector, i.e. its frequency. Time complexity for this would be $O(n)$ (How? Try to find out and let me know in the comments).
2. Sort all the keys of the map. Time complexity $= O(k\log (k))$ as there are $k$ distinct elements.
3. In a new vector, push each sorted values as many times as its frequency. Look up on a map takes constant time. So this operation would take linear time.

Total complexity would be of $O(n + k\log(k))$
> 4 votes

# Answer
The short answer is no, *in the worst-case comparison based algorithms*, for reasons stated here.

Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a BST. Here I'll give a variant of quick-sort which also achieves $O(n \log k)$ With a slight modification and a more careful analysis of quick-sort. We will change the "pivot" of quick-sort to never put duplicate elements in separate sub-problem. The partition procedure is as follows:

```
partition(list A of size n):
  x = SELECT(A, n/2)

  left = list of all elements less than x
  right = list of all elements greater than x
  center = list of all elements equal to x

  return (left, center, right)

```

Then the overall quick-sort looks like this:

```
quick-sort(list A of size n):
  if all elements in A are the same:
    return A
  left, center, right = partition(A)
  quick-sort(left)
  quick-sort(right)
  return concat(left, center, right)

```

The important thing here is the base case, when we only have one unique element in the list, just return the list. This will ensure that we have exactly $k$ leaf nodes in our recursion tree. The recurrence at face-value is:

$$T(n) \leq \max\_{i,j} \\{T(n - i) + T(n - i - j)\\} + O(n)$$

Obviously with some constraints on $i$ and $j$, but that's the idea. Another thing to note is that via `SELECT` we ensure that `center` contains all the median elements, this would imply that we only recurse on two sub problems of size less than $n/2$, leading us to:

$$T(n) \leq \max\_{l,r} \\{T(\tfrac{n}{2} - l) + T(\tfrac{n}{2} - r)\\} + O(n)$$

Where $l$ would be the overlap of the median on the left side and $r$ would be overlap of median on the right side. Note that $r + l$ is the number of elements equal to the median. With this we see a clear upper bound of $O(n \log n)$. However, when we include the base cases this becomes better. If we assume that each unique element is repeated $c = n/k = n^\*/k$ times (distributed evenly) then we can get the recurrence:

$$T(n) \leq \begin{cases} 1 & n \leq n^\*/k\\ T(\tfrac{n}{2} - n^\*/2k) + T(\tfrac{n}{2} - n^\*/2k) + O(n) & \text{otherwise} \end{cases}$$

If we do recursion tree analysis on this we can see it is $O(n \log k)$.

We could also take advantage of the fact that we do not do $n$ work at each level of recurrence, but rather at level 0 we do $O(n)$, at level 1 we do $O(n - n/k)$, at level 2 we do $O(n - 3n/k)$, at level 3 we do $O(n - 7n/k)$ and so on. Without out our assumption the analysis becomes more tricky, and we would need to do average case analysis. However, I would claim that this assumption is worst case. Intuitively if this assumption did not hold, then we have fewer repetitions for some element $x\_i$, but *more* repetitions for some element $x\_j$. Thus, making $x\_j$ more likely to be in one of the `center`'s without going too deep in the recursion tree. This would reduce the amount of work on the remaining subproblem(s) more by removing more than $n/k$ elements from the list.
> 6 votes

---
Tags: algorithms, sorting, quicksort
---