# Question
Title: 3SUM problem solution on the basis of cubic function and a line?
The 3SUM problem formulation: in a given set of **n** real numbers find **3** elements that sum to specified value **S**.

I am trying to understand mathematical solution of the 3SUM problem based on a polynomial of **3** degree. I found some information about 3SUM problem as a special case of geometrical problems. It says:

> There are **m** points on a plane and it is required to check if some 3 points are located on on the same straight line. So, there is a straight line function: $y = ax + b$ and a curve: $ y = f(x) = x^3 - Sx^2 $
> Intersection of the above two equations is roots of the following equation: $x^3 - Sx^2 - ax - b = 0 $
>
> So, set of points $(a\_1 , f(a\_1)), ..., (a\_m , f(a\_m))$ contains **3** points $(a\_x , f(a\_x)), (a\_y , f(a\_y)), (a\_z , f(a\_z))$ on the samle straight line if and only if $a\_x + a\_y + a\_z = S$

I can't fully percieve the relation between 3SUM problem and the above geometrical problem. AFAIK, in the equation: $x^3 - Sx^2 - ax - b = 0 $ variable $a$ represents set of points $(a\_1 , f(a\_1)), ..., (a\_m , f(a\_m))$ and probably all real numbers in which I search for some **3** numbers that sum to **S**. So **3** numbers $a\_x + a\_y + a\_z$ sum to **S** if all of them are on the same line. But what **x**, **y**, **z** represent here? What is $a\_z$ or $a\_y$? And what is coefficient before $x^3$ equal to? How do I define **b**?

Can someone clarify relation between 3SUM problem and the above geometric problem?

# Answer
> 2 votes
Consider the problem of finding whether the list $a\_1,\ldots,a\_n$ contains $d$ points summing to $S$. We assume that these points are all distinct.

Let us suppose that the $d$ points $a\_{i\_1},\ldots,a\_{i\_d}$ do sum to $S$. All of these points are roots of the polynomial $$ (x-a\_{i\_1})(x-a\_{i\_2})\cdots(x-a\_{i\_d}) = x^d - Sx^{d-1} - P\_{d-2}(x), $$ where $P\_{d-2}$ is a polynomial of degree at most $d-2$; the point is that we know that the coefficient of $x^{d-1}$ is $-S$, since (in this case) it equals the negative sum of the roots.

In view of this, we are motivated to consider the points $p\_i = (a\_i, a\_i^d - Sa\_i^{d-1})$. If $a\_{i\_1},\ldots,a\_{i\_d}$ sum to $d$ then the points $p\_{i\_1},\ldots,p\_{i\_d}$ all lie on the polynomial $y = P\_{d-2}(x)$ of degree at most $d-2$ (we have seen that above).

Conversely, suppose that there exist $d$ points $p\_{j\_1},\ldots,p\_{j\_d}$ which all lie on a polynomial $y = Q\_{d-2}(x)$ of degree at most $d-2$. This means that these points satisfy $$ a\_{j\_t}^d - Sa\_{j\_t}^{d-1} = Q\_{d-2}(a\_j), \text{ for $j=1,\ldots,d$}. $$ Stated differently, the values $a\_{j\_1},\ldots,a\_{j\_d}$ are all roots of the polynomial $$ Q = x^d - Sx^{d-1} - Q\_{d-2}(x). $$ Since $a\_{j\_1},\ldots,a\_{j\_d}$ are all distinct (by assumption) and a polynomial of degree $d$ has at most $d$ roots, we conclude that $a\_{j\_1},\ldots,a\_{j\_d}$ are all the roots of $Q$, which means that $$ Q = (x - a\_{j\_1}) (x - a\_{j\_2}) \cdots (x - a\_{j\_d}), $$ implying that $S = a\_{j\_1} + \cdots + a\_{j\_d}$, as before.

Summarizing, the $d$ values $a\_{i\_1},\ldots,a\_{i\_d}$ sum to $S$ if and only if the points $p\_{i\_1},\ldots,p\_{i\_d}$ lie on a polynomial of degree at most $d-2$. Stated differently, there are $d$ values summing to $S$ if and only if there are $d$ points lying on a polynomial of degree at most $d-2$.

This criterion should be contrasted with the fact that *every* $d$ points lie on some polynomial of degree at most $d-1$.

---
Tags: algorithms, algorithm-analysis, combinatorics, search-algorithms
---


title: How to pick Hamming distance

text:
# Question
Title: How to pick Hamming distance
Wikipedia's article Cyclic redundancy check states that for the same n (bits) there are multiple CRCs possible with different polynomial. Then it lists this Best CRC Polynomials article that gives some variations with different polynomials. I am looking to implement a simple CRC-8. What should be my criteria for picking one polynomial over another?

I assume that it boils down to selecting the Hamming distance, but how is that related to my problem at hand? How do I pick the correct/best Hamming distance for best detecting possible errors in my case (and in what terms should I describe my case)? For example, will the choice depend on the media for storing/transmitting data or other physical factors or something else?

# Answer
> 2 votes
The author of the list that you mention has written a thorough report on the problem of selecting a CRC polynomial, which probably contains the answers to all your questions. See page C-19:

> Important to select CRC polynomial based on:
>
> * Data Word length
> * Desired HD
> * Desired CRC size
>
> Safety-critical applications commonly select HD=6 at max message length

For example, HD-6 detects between 1-6 error bits in the Data Word, so the bigger the HD the better (for the given Data Word length).

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


# Question
Title: What is an upper bound of T(n) = 2 T(3n/10) + T(4n/10) + n
```
if assume that T(n) = 2T(3n/10) + T(4n/10) + n <= cnlogn

T(n) <= 6cn/10 * log(3n/10) + 4cn/10 * log(4n/10) + n
= cn/10 * (6(log3 + logn - log10) + 4(log4 + logn - log10)) + n
= cn/10 * (10logn - 10log10 + 6log3 + 4log4) + n
= cnlogn - cn/10 * (10log10 - 6log3 - 4log4) + n <= cnlogn

because (10log10 - 6log3 - 4log4) > 0, there exists c that satisfy the equation.

```

I think it is the tight upperbound because I failed when I assumed the T(n)\<=cn so I think that upper bound of T(n) = O(nlogn)

am I doing right?

# Answer
You can prove this using induction, but it will be messy. I'll show you a better approach below (unless you explicitly want to solve it using induction).

Yes, the answer is $O(n \log n)$, which follows most easily using the Akra-Bazzi method. (This is a generalization of the better-known Master theorem, and is extremely useful for solving these types of recurrences.)

Clearly, the recursion satisfies the form from the statement of the Akra-Bazzi theorem: $g(x)=x$, and the constants $a\_i$ and $b\_i$ obviously satisfy the requirements.

In your case, $b\_1=3/10$ and $a\_1=2$; and $b\_2=4/10$ and $a\_2=1$. Thus $a\_1\cdot b\_1 + a\_2\cdot b\_2=1$, thus we take $p=1$. By the Akra-Bazzi theorem, the solution is $T(x) = O(x \cdot (1 + \int\_1^x \frac{g(u)}{u^{p+1}} du))$. Because $p=1$ we are integrating the function $x/x^2=1/x$.

Since $\int\_1^x \frac{1}{u} du = \log x$, we have that $T(x) = O(x (1 + \log x))$ which is $O(x \log x)$.

Using variable $n$ instead of $x$, we state this in more familiar notation: $T(n) = O(n \log n)$.

In fact, Akra-Bazzi gives us a stronger result that $T(n) = \Theta(n \log n)$, from which it immediately follows that $T(n) = O(n \log n)$. This is because $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.
> 3 votes

---
Tags: asymptotics, recurrence-relation
---


title: A heap based problem

text:
# Question
Title: A heap based problem
I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed.

> You are given a file of numbers which represent the values of associated with certain chemical reactions for the past year from a large scale industrial laboratory (reactions can happen on the millisecond scale, so this file is very large). Let $n$ represent the number of values in the file. For some fixed $k$, devise a $\mathcal{O}(n \log k)$ time algorithm for finding the highest $k$ reactions that occur in the file.

$\textbf{My approach:}$ I reasoned that I should build a max-heap and exploit the `get-max()` queries and save the $k$ highest values to an array. The time complexity to build a heap is $\mathcal{O}(n)$ and here mentions the `extract-max` query is $\mathcal{O}(\log n)$ so this operation would run in $\mathcal{O}(n\log n)$ time and not $\mathcal{O}(n\log k)$? Also, I'm not sure why `extract-max` runs in $\mathcal{O}(\log n)$ time?

# Answer
You don't need to put all numbers encountered in the heap. Never let your heap grow in size more than $k$. Keep a min heap. Now, if at some point of time heap has size $ \< k$, then push the number encountered ( say $i$ ) into the heap. If heap is full and the number $i$ is greater than top element of heap ( say $top$ ) , pop the $top$ and insert $i$ into heap. At the end all the numbers in the heap are your desired $k$ numbers. Each operation takes $O(logk)$ steps ( as heap size is always $ \le k$ ). And there are $n$ steps so $O(nlogk)$.
> 1 votes

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


title: What does Θ(1) memory mean?

text:
# Question
Title: What does Θ(1) memory mean?
I have the definition of an in-situ algorithm from the professor, but I don't understand it.

> In-situ algorithms refer to algorithms that operate with Θ(1) memory.

What does that mean?

# Answer
> 13 votes
First, let's unpack what $\Theta(1)$ means.

Big $O$, and big $\Theta$, are classes of functions. There's a formal definition here, but for the purposes of this question, we say that a function $f$ is in $O(1)$ if there's a constant $c$ where, for all $x$, $f(x) \leq C$. That is, $f$ grows at most as fast as a constant function.

Big-$\Theta$ doesn't mean much for constant functions, because when describing algorithm time or space usage, there isn't much below constant. But to explain what it means, $f \in \Theta(1)$ if there are some constants $c,d$ such that, for all $x$, $d \leq f(x) \leq c$. That is, $f$ grows at least as fast, and at most as fast, as a constant function.

Now what does this have to do with memory usage? Consider some algorithm $A$. There is some (mathematical) function which, given an input $n$, gives the maximum memory usage of your algorithm $A$ on any input of size $n$. Let's call this function $mem$.

So, now we combine our two concepts. If an algorithm uses $\Theta(1)$ memory, then its memory usage function is in $\Theta(1)$, meaning that there exists some $d,c$ such that, for any input, the memory used is between $d$ and $c$.

In short, this means that the memory usage of the algorithm is in some constant range, regardless of the input.

Usually, the memory function does not account for the memory used to store the input to the algorithm, since otherwise memory usage would always be at least $\Theta(n)$.

# Answer
> 8 votes
**Constant space complexity of algorithm**

> Amount of memory your algorithm uses is independent of input.

An algorithm is said to have constant space complexity if it makes use of fixed amount of space. It can be $10$ variables or an array of exactly $10$ elements.

However, In-situ algorithms perform their intended function on the input itself and thus require very little or no extra space. The input is usually overwritten by the output as the algorithm executes. (ref)

In-situ algorithms do not consider the space occupied by the input and take only the extra space into account, while calculating space complexity.

# Answer
> 0 votes
That means that additional memory amount required for algorithm is not greater than some constant amount that doesn't depend on input size for sufficiently big input.

---
Tags: algorithms, terminology, landau-notation
---


# Question
Title: What is the resulting set for {0,1}*\{0}*?
If we have a language $L = \\{0\\}^\*$ over the alphabet $\Sigma=\\{0,1\\}$, what is $\Sigma^\*\backslash L$?

That's what I think:

$\\{0,1\\}^\* = \\{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... \\}$
$\\{0\\}^\* = \\{\epsilon, 0, 00, 000, 0000, ... \\}$
$\\{0,1\\}^\*\backslash \\{0\\}^\*= \\{1,01,10,11,001,...\\}$

In other words, the resulting set should contain everything from $\Sigma^\*$ except the empty string and any string that contains 0s but not 1s.

If my thinking is correct, then how can I express $\\{1,01,10,11,001,...\\}$ more succinctly using set notation? I was thinking of something like $\\{0,1\\}^\*\\{1\\}\\{0,1\\}^\*$ but I'm not sure if it's correct or if there's a better way.

# Answer
> 5 votes
You are correct that the words not in $0^\*$ are exactly those words which contain $1$ somewhere. You are also correct that you can represent this complement using the regular expression $(0+1)^\*1(0+1)^\*$. There are other regular expressions for the same language, for example $0^\*1(0+1)^\*$ (which is a "deterministic" regular expression).

---
Tags: formal-languages
---


# Question
Title: How do I prove that all primitive recursive functions are computable?
I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?

# Answer
You prove it by structural induction over the definition of primitive recursive functions. The definition of *computable* is: a function is computable if it is computable by a Turing machine. There are many other equivalent definitions.
> 3 votes

# Answer
There are different definitions of computability.

1. A function is computable if there is a terminating Turing machine which computes the result.
2. A function is computable if there is a µ recursive function which computes the result.
3. A function is computable if there is a lambda expression in untyped lambda calculus whose beta reduction terminates and which computes the result of the function.
4. ...

All these definitions are pretty formal (i.e. "execution" can be done by a machine). The definitions have been invented at the beginning of the 20th century in order to find a precise definition for the predicate "can be computed mechanically".

It can be proved that all these definitions are equivalent. E.g. for any terminating Turing machine there exists a µ recursive function which calculates the same result. For any µ recursive function there exists a terminating Turing machine which calculates the same result. These proofs can be found in recursion theory. The proofs are general. I.e. they apply to all Turing computable functions, to all µ recursive computable functions etc.

Since the primitive recursive functions are a subset of µ-recursive functions they are clearly computable in the sense of µ recursive functions. Since all µ recursive functions are Turing computable, clearly all primitive recursive functions are Turing computable as well.
> 1 votes

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


# Question
Title: What is the most efficient constant-space sorting algorithm?
I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions:

1. SWAP: swap the next index with the current one;
2. MOVE: moves the cursor to +1 or -1 index;

That is, you can't swap non neighboring indexes, nor swap the index `100`, after you just swapped index `10`. What is the most efficient algorithm - i.e., the one that uses the less amount of total moves?

# Answer
> 15 votes
Consider cocktail shaker sort, which is a bidirectional version of bubble sort. You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done. This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes. Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.

# Answer
> 4 votes
The only algorithm with the two operators that you have mentioned which is quite efficient is the bubble sort. The complexity of the algorithm is $O(n^2)$ in the worst case.

I also assume apart from the two operations, we can also check whether we are at the rightmost (Op 3) or leftmost position (Op 4), either by use of sentinels $-\infty$ and $+\infty$ or by some operation on the list. Also we should have a comparison operation (Op 5) given separately or combined with swap operation. If the comparison operation is combined with the swap operation then it must tell us whether the swap was performed or not.

The algorithm that does not uses a boolean flag to know whether we have swapped any element or not, is given below (the trick to keep the information in the state of the machine, rather than memory):

```
Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

```

The solution of Eric Lippert, the gnome sort also works, because basically it is a two way bubble sort.

# Answer
> 4 votes
The number of swaps of adjacent elements needed to order an array is equal to the number of inversions in the array. With *n* elements in total, there are at most *n\*(n-1)/2* inversions, so bubble sort gives the asymptotically optimal number of swaps in this model.

---
Tags: algorithms, sorting, in-place
---


title: Heap comparison based sorting question

text:
# Question
Title: Heap comparison based sorting question
I need some help with this question from my problem set. I do not want a solution but some $\textbf{hints}$ on how to proceed.

> Given $n$ records in a file that are so numerous, that just storing the $n$ keys alone would require more RAM than is available on your computer. Let $m$ be the maximum number of records that you can store in RAM at once. Assuming that $m \>$ $\sqrt{n}$, produce a $\mathcal{O}(n \log n)$ time algorithm for sorting the $n$ records. The sorted records would then be written to a file, since it will not be possible for them to all fit in memory at once.

$\textbf{My approach:}$ I figure I should use a heap based approach. Try to create a type of online algorithm to read $m$ records at a time, and then use heapsort or a type of comparison based algorithm to solve it?

$\textbf{Related Questions:}$

1) I don't understand the underlying assumption of letting $m\>\sqrt{n}$?

# Answer
> 4 votes
Hint: Convert the input into $n/m \< m$ chunks of length $m$ and sort the chunks. Then use your heap idea. Note that you're using the assumption $m \> \sqrt{n}$ so that the heap fits in memory.

---
Tags: data-structures
---


# Question
Title: Is there an algorithm that will fill any shape with points a given distance away from each other?
I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is continually filled up with points until no new points can be found without exceeding the bounds of the polygon. The polygon can be given as set of vertices.

I could see an algorithm starting out with a point at the center of the polygon, and then adding a second point exactly the desired distance away. With those two points, another point equidistant to the two previous points could be found by finding the intersection of two circles with the two previous points as their centers and their radii the desired distance.

This gives two points, each of which can be added to a growing list of points. Each point keeps track of what points have been added as neighbor relative to it, and when it has M neighbors, it no longer tries to find any new neighbor. It also does not continue to look for more neighbors if no new neighbors can be found that don't leave the bounds of the polygon.

I am having some mental blocks and if anyone could suggest any leads I would greatly appreciate it. Thank you.

# Answer
> 0 votes
Are you looking for something like this?

Another way is to create equilateral triangle tiling like this, plot your polygon and check which points are inside. Of course it is not needed to actually plot it, just store it in memory.
If your resolution is e.g. one pixel big, you can check all possible starting points shifts from the starting point to find better solution.
To find optimal solution also rotation would be needed, or different approach.
If you decide that not rotated version is sufficient, the ray casting algorithm (also known as scanline test) for testing point inside polygon would be very effective, because all points in a row form line, so in one longer pass you can test whole row.

---
Tags: computational-geometry
---


title: Log reduce PATH to DISTANCE-PATH

text:
# Question
Title: Log reduce PATH to DISTANCE-PATH
An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t.

DISTANCE-PATH is similar, but with an extra requirement d and on an undirected graph. A true instance of this would be where G is an undirected graph and there exists a path of length d from s to t, and there isn't a shorter path.

Given directed , construct an undirected G' such that G' has a path from s to t of shortest length d iff G has a path from s to t.

The idea is to construct G' by making n copies of G, and each edge in G' connects one copy to the next.

I don't understand how d comes into play and how to ensure there are no shorter paths, should d be the number of copies of G made? Should G' connect the copies of G by connecting one t node to the next s node? I'm not sure how to approach this problem

# Answer
> 1 votes
The idea is to build a layer graph $G'=\left (V\_1,...,V\_n\right)$ with $n$ layers, where each layer is a copy of $V$. For each $(u,v)\in E$ we add the edges $\left\\{(u\_i,v\_{i+1}) | 1\le i \le n-1\right\\}$, where $u\_i$ is the copy of $u$ in $V\_i$. In addition we add self edges $\left\\{(u\_i,u\_{i+1}) | u\in V, 1\le i\le n-1\right\\}$. You then want to know whether there exists a path $s\_1\rightsquigarrow t\_n$. Since $G'$ is a layer graph, any path from $s\_1$ to $t\_n$ is of length $n-1$ (so you dont need to worry about shorter paths anymore). You should now be able to complete the details yourself.

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


# Question
Title: What is the chance that this code terminates?
I wrote this Python code, and wondered if it sometimes *simply doesn't* terminate (assuming we had infinite memory/time and no recursion depth limit).

Intuitively you'd think it terminates, since at some point you must get *lucky*, and if it doesn't terminate you have an infinite amount of time to get lucky. On the other hand, as the recursion depth increases you must become exponentially more lucky.

```
import random

def random_tree():
    if random.random() < 0.5:
        return 0
    return [random_tree() for _ in range(random.randint(1, 5))]

```

If `random_tree` doesn't always terminate, why, and what is the chance that it does terminate?

I've tried to calculate it using $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$, which in it's terrific uselessness either gives the answer ~$0.684124$ or... $1$.

Probably more complicated, but also intriguing to me, what is the termination chance $P(a, b)$ for:

```
def random_tree(a, b):
    if random.random() < a:
        return 0
    return [random_tree(a, b) for _ in range(random.randint(1, b))]

```

Or in pseudo-code:

```
random_tree(a, b) is a function that either:
    - returns 0 with probability a
    - returns a list containing the results of 1 to b
      (uniformly chosen from this inclusive range) recursive calls

random_tree(a, b):
    if rand() < a # rand() is a random real on [0, 1)
        return 0
    list = []
    len = randint(1, b) # uniform random integer from 1 to b inclusive
    do len times
        append random_tree(a, b) to list
    return list

```

# Answer
This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 \> 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated — you need to select the root which is smaller than 1.
> 8 votes

---
Tags: trees, probability-theory, termination
---


# Question
Title: Implementation-level description of a Turing Machine
I am new to Turing Machines!

I need to work on an implementation-level description of a Turing machine that decides the language L = an where n is a Fibonacci number.

I know Fibonacci numbers include 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

So would this be as

```
M= "On input a^n:
    Scan a^n, if a '1' is found, cross it out, and move the head
    of the tape back to the left-hand end, and then go to II
    (****could I make II my accept state? Or should I make two the recursive calculation I explain in C below?)

    If a '0' is found, cross it out, and go to the reject state
    (can I make this three?)
    II. Accept
    III. Reject

```

I want to incorporate the **recursion aspect** of this in the implementation. Because if I were in C, and n is not a 0 or 1, it is a fibonacci number if you do a sort of fib(n) where inside it 'return fib(n-1) + fib(n-2)'.

Thoughts? Thank you.

# Answer
One approach is using Fibonacci words (each word is the concatenation of the preceding two words): $$ \begin{align\*} &0 \\ &01 \\ &010 \\ &01001 \\ &01001010 \end{align\*} $$ You can generate them according to the following scheme: $$ \begin{align\*} &\color{blue}0\color{red}1 \to \color{blue}0\color{red}1\color{green}0 \to \color{blue}{01}\color{green}0 \to \\ &\color{blue}{01}\color{red}0 \to \color{blue}{01}\color{red}0\color{green}{01} \to \color{blue}{010}\color{green}{01} \to \\ &\color{blue}{010}\color{red}{01} \to \color{blue}{010}\color{red}{01}\color{green}{010} \to \color{blue}{01001}\color{green}{010} \to \\ &\color{blue}{01001}\color{red}{010} \to \cdots \end{align\*} $$ I hope the algorithm is clear. The basic operations are copying of words and changing colors.

Why is this helpful? The lengths of the Fibonacci words are exactly the Fibonacci numbers. If you can compare lengths of words, then by generating the sequence of Fibonacci words, at some point you will either reach or exceed the input, and using that information will be able to decide your language.

While I explained how to generate the Fibonacci words, you can actually just generate the words $a^{F\_n}$ directly, which is slightly easier. You can even do that on top of your input for a really slick approach.
> 1 votes

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


# Question
Title: Is the unweighted vertex cover problem equivalent to its weighted version?
Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq\_\mathrm{m} \text{WVC}$$ but $$\text{UVC} \not \equiv\_\mathrm{m} \text{WVC} \enspace ?$$

I think the first part is easy to prove, since one can construct an instance of WVC by taking an instance of UVC and letting the weight of all of its vertices be the same.

I find not that easy to prove the second part though. As WVC is a generalization of UVC, intuitively $\text{WVC} \leq\_\mathrm{m} \text{UVC}$ can't hold, but I'd appreciate some help to demonstrate it in a formal way.

# Answer
> 3 votes
If you're talking about determining whether there exists a cover of weight $\le T$, then the problem is obviously in NP and thus reduces to unweighted vc (since $VC$ is NP complete).

If however were talking about whether the minimal cover is of weight $\le T$, then the problem is $\Sigma\_2$ complete, and is therefore not reducible to vc unless the hierarchy collapses to the first level.

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


# Question
Title: what is the difference between "language" and "certificate" in complexity theory?
Seems like they both are set of strings for which the problem returns "yes" in decision problems.

**P** class is consists of problems so we can only say a problem is in **P**. But we sometimes say that a language **L** is in **P**. why?

# Answer
> 1 votes
A (formal) language $L$ is a set of words over some finite alphabet. It can be an infinite set. Generally we're interested in the problem of deciding whether a particular word is in the language or not. For example $L$ can be the set of all Turing machines (encoded as binary strings for example) that halt after at most 100 steps when started with an empty tape, or $L$ can be the set of English words that don't contain the letter 'e'.

A certificate on the other hand is one particular string. When solving the decision problem I talked about above, namely checking whether some word $w$ is in some language $L$, sometimes the problem becomes much simpler if you have some additional information $c\_w$. This is often called a certificate for $w \in L$ respectively $w\not \in L$.

For example if $L$ is the set of all graphs that can be colored with at most 3-colors, deciding whether a particular graph $G$ is in this set is NP-complete. But if I already give you a coloring $c\_G$ it is very easy to check that it's a valid coloring. The coloring is a certificate for $G\in L$. A coloring has the nice property that it's short, just a couple of bits for each node of the graph. Note that in this case it's not easy to give a (short) certificate for some $G'$ that is not colorable. A very long certificate in this case would be an enumeration of all exponentially many possible 3-colorings of $G'$. Checking that each is not valid is again easy, and since the certificate $c\_w$ is so long, the running time of the algorithm with input $G', c\_w$ is polynomial as a function of input size.

---
Tags: complexity-theory
---


# Question
Title: How to write operational semantics rule for havoc x?
If I want to extend a new language by adding a new command havoc x, which updates the variable x with a non-deterministic value, how to write operational semantics rule for havoc x? I'm confused about generate a non-deterministic value. If I write like this: $$\frac{n = \[e\]\_ {intexp}\sigma}{(\mathrm{havoc}\ x,\sigma)\rightarrow(x:=x+n,\sigma)}$$ is it make sense?

# Answer
I'm going to assume that all the allowed values for $x$ are (unbounded) integers.

In that case your proposal somewhat makes sense, insomuch as $e$ is some arbitrary well-formed expression (which evaluates to some value in the context $\sigma$). But it's just as easy to write this

$$\frac{n\in\mathbb{Z}}{(\mathrm{havoc}\ x,\sigma)\rightarrow (x:=n,\sigma)} $$

You see that in both cases the result of the evaluation by this rule can non-deterministically give any value in $\mathbb{Z}$ to $x$. In this sense, you have a *family* of rules, one for each $n\in\mathbb{Z}$.
> 3 votes

---
Tags: operational-semantics
---


# Question
Title: Is there a canonical form that uses AND and XOR?
Is there something like the sum of products form of a circuit which uses AND and XOR instead of AND and OR?

I know that you can create an OR gate from AND and XOR (but i can't remember or find the details of that at the moment), but am wondering if there is anything more straightforward, as in an actual form that uses AND and XOR?

# Answer
> 3 votes
You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms:

> An arbitrary *n*-variable function $f(x\_1,x\_2,...,x\_n)$ can be represented using the positive polarity Reed-Muller form (PPRM)
>
> $f(x\_1,x\_2,...,x\_n) = a\_0\oplus a\_1x\_1\oplus a\_2x\_2\oplus\ldots\oplus a\_{12}x\_1x\_2\oplus a\_{13}x\_1x\_3\oplus\ldots\oplus a\_{n-1,n}x\_{n-1}x\_n\oplus\ldots\oplus a\_{12\ldots n}x\_1x\_2\ldots x\_n$.
>
> For each function $f$, the coefficients $a\_i$ are determined uniquely, so PPRM is a canonical form. If we used either only the positive literal ($x\_i$) or only the negative literal ($\overline{x\_i}$) for each variable in Eq. (4)1, we get the FPRM. There are $2^n$ possible combinations of polarities and as many FPRMs for any given logical function.
>
> If we freely choose the polarity of each literal in Eq. (4), we get a GRM. In GRMs, contrary to FPRMs, the same variable can appear in both positive and negative polarities. There are $n2^{n-1}$ literals in Eq. (4), so there are $2^{n2^{n-1}}$ polarities for an $n$-variable function and as many GRMs. Each of the polarities determines a unique set of coefficients, and thus each GRM is a canonical representation of a function.

---

1 It's not clear from the text, but equation 4 is the generic PPRM equation included in the quote

# Answer
> 3 votes
Yes. You want algebraic normal form. Every formula in algebraic normal form has the form of an xor of products.

Because xor is the same as addition when working modulo 2 (i.e., when working in the finite field $\mathbb{F}\_2$), this basically comes down to expressing the function as a multivariate polynomial over $\mathbb{F}\_2\[x\_1,x\_2,\dots,x\_n\]$ -- in fact, a multilinear polynomial.

There are efficient algorithms to derive the algebraic normal form of any function. They are efficient in the sense that the running time is roughly proportional to the size of the resulting ANF expansion.

---
Tags: circuits, digital-circuits
---


# Question
Title: Why do presenttations of proof systems in logic and automated reasoning not include the algorithm that finds proofs?
Is is that a common way to present a proof system in the field of Logic and Automated Reasoning is to present a system of inference rules, without having to formally describe a particular algorithm or procedure to find proofs in this system?

I notice that phenomenon in both textbook as well as conference or journal papers of this field.

This can be seen in classic topics like: the Natural Deduction calculus, Hilbert calculus where only inference rules is presented.

In modern researches, I am studying about Separation Logic, thus, I would like to take some papers from this field to illustrate this observation:

Automated Cyclic Entailment Proofs in Separation Logic

Symbolic Execution with Separation Logic

# Answer
To simplify a bit, a system of inference rules generally defines a set of *sequents*, which are simply pairs of a list (or set) of propositions $\Gamma$ and a proposition $\phi$ written

$$ \Gamma \vdash \varphi$$

called the *derivable* sequents. The rules describe which sequents are derivable, and for any reasonable system, given $\Gamma\vdash\varphi$, and sequents $\Gamma\_1\vdash\varphi\_1,\ldots,\Gamma\_n\vdash\varphi\_n$, it is easy to tell whether

$$\frac{\Gamma\_1\vdash\varphi\_1\ldots \Gamma\_n\vdash\varphi\_n}{\Gamma\vdash\varphi} $$

is a valid derivation. This usually be done with some obvious algorithm.

Some much more difficult algorithmic questions are this:

1. Given $\Gamma\vdash\varphi$, is this sequent derivable?
2. Given $\Gamma$, how can we enumerate the set of $\varphi$ such that $\Gamma\vdash \varphi$ is derivable?

In general, there is no algorithm for answering question 1, and question 2 is quite difficult. In particular, when trying to prove $\Gamma\vdash\varphi$ a natural approach is to try to apply all possible rules until exhaustion. Several issues come up:

1. What order do we apply rules in?
2. How do we guess the $\Gamma\_i\vdash \varphi\_i$? If any variables appear on top that do not appear in the conclusion, you need to guess some instance for that variable.
3. When do we know if a derivation does *not* exist?

Because of the complexity of these issues, it's much more natural to separate the system of rules that describe the derivable sequents from the algorithms trying to find actual derivations of a given sequent.
> 8 votes

---
Tags: logic, automated-theorem-proving
---


# Question
Title: What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies?
F+ and F\* is defined as follows:

* **F+: closure of F**

+ F+ = {fd | F |= fd}
    + Set of all FDs deduced from inference rule (normally: Armstrong axioms)
* **F: cover of F**

+ {fd | F |- fd} cover of F
    + Set of all FDs entailed by F (all FDs that are true)

So my question is: What is the difference between F+ and F\*? Can you also give an example to demonstrate the difference.

# Answer
> 4 votes
Closure and cover are two completely different things.

The **closure of a set of attributes or a functional dependency** $f$ is a set of relation schemes that can be implied by $f$. In order to find the closure, we can expand the FD or the set of attributes based on the given set of FDs by replacing each relation with the ones inferred by it. For example,

$$X = \\{ f\_1:A \rightarrow BC,~~~ f\_2: C \rightarrow D,~~~ f\_3: BD \rightarrow E, ~~~~f\_4: F \rightarrow G , ~~~~f\_5: F \rightarrow H \\}$$

then the closure of $f\_1: A \rightarrow BC$ or $\\{A\\}$ is $\\{A,B,C,D,E\\}$:

$$A \rightarrow\_{f\_1} ABC \rightarrow\_{f\_2} ABCD \rightarrow\_{f\_3} ABCDE$$

while the closure of $F\rightarrow G$ is $\\{F, G, H\\}$.

The **cover of a set of functional dependencies** $X$ is a set of functional dependencies $Y$ that is *equivalent* to $X$ and the left-side of each functional dependency in $Y$ is unique. Though, not every cover is minimal, and we are usually looking for minimal cover. For example a cover of $X$ is,

$$Y=\\{f\_1:A \rightarrow BC,~~~ f\_2: C \rightarrow D,~~~ f\_3: BD \rightarrow E, ~~~~f\_4: F \rightarrow GH \\}$$

Please do some search before posting your questions, there are plenty of resources on the web, including Wikipedia and Wikipedia.

# Answer
> 1 votes
An important property of the Armstrong’s axioms, (as well as of similar set of axioms), it that they are sound and complete (for a proof see for instance this).

This amount to say that F+ = F\*. In other words, all the FD derived from those axioms are logically entailed by F, as well as all the FD dependencies logically entailed by F can be derived by repeatedly applying the axioms.

---
Tags: database-theory, databases
---


title: Variation of MAX 3-SAT

text:
# Question
Title: Variation of MAX 3-SAT
Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)?

I'm trying to think of an efficient algorithm to solve this problem. This is sort of a variation of the MAX 3-SAT, but with a fixed k. If we have m clauses, checking naively would get $\binom{m}{k}$ comparisons, but this seems factorial (if we approximate with Sterling's formula, exponential) complexity.

What could be an efficient way to check this? I must be missing something. Thanks.

# Answer
(I don't know whether "3CNF" means *exactly* 3 literals per clause, or
*at most* 3 literals per clause.  I will address the more general case.)

Empty clauses can't be satisfied, so removing them affects
neither the maximum nor which assignments achieve that.
If  2$\cdot$k ≤ #\_of\_non-empty\_clauses  then YES, since the expected number of those clauses satisfied by a random assignment is at least half of #\_of\_non-empty\_clauses,
so at least one assignment satisfies at least half of the non-empty clauses.
(One can efficiently-and-deterministically *find* such an
assignment via the method of conditional expectation.)
Thus, your problem can be kernelized in linear time into less than 2$\cdot$k clauses.
> 1 votes

# Answer
This is the decision version of MAX-3SAT, which is known to be NP-complete. In particular, if you choose $k = m$ then you get the classical NP-complete problem 3SAT.
> 2 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


# Question
Title: Characterizing a CFG equivalent to a special type of PDA
Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which starts with an empty stack and ends with an empty stack and which has the additional property that during this computation, the stack size can increase, but once the stack size decreases it cannot subsequently increase. I want to show that there is a CFG equivalent to $P$ with the property that for each production in this grammar, there is at most one variable on its right-hand side.

My initial idea to approach this problem was to convert $P$ into an equivalent PDA $P'$ which either pops or pushes on every transition, but never both, which empties the stack before accepting, and which has a single final state. Then I would convert $P'$ into a CFG $G'$ using the standard method, as seen here. Finally, I could show that for every $\sigma \in L(P') = L(P)$, there exists a derivation of $\sigma$ in $G$ such that every production applied in this derivation is of the form $A\_{pq} \rightarrow aA\_{rs}b$, where $p,q,r,s$ are states in $P'$ with the property that a transition exists from $p$ to $r$ which reads input symbol $a$ and pushes a symbol $u$ onto the stack and a transition exists from $s$ to $q$ which reads input symbol $b$ and pops $u$. However, I don't know how to show this to be the case.

# Answer
> 1 votes
In other words, you are constructing a linear grammar for a one-turn pushdown automaton.

So the standard construction from the link (which is Sipser style, afaik) gives productions $A\_{ik}\to a A\_{\ell j} b$ for each pop-push pair in the computation. That is ok, the productions are of the right form.

Now there are two problems. One is what to do with the zillions of $A\_{ij}\to A\_{ik}A\_{kj}$ productions (which are obviously not allowed!) ? The answer is in the intuitive meaning of the symbols $A\_{ij}$.

The second problem is hidden, and not clear in your question (and also not in the example you link). Is it allowed to replace to topmost stack symbol by another (this will not change the stack size) or are those considered two consecutive operations? (Here the Sipser model deviates from the standard one). Also: can we make a computational step. not changing the stack?

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


# Question
Title: I want to pursue a career in computer programming. Where do I start?
I am currently finishing up my junior year as a Biochemistry major at a 4-year university. In a year, I will graduate with a B.S. in Biochemistry and way more credit hours than anyone should ever have due to AP classes in high school. To make a long story short, I want to pursue computer programming once I graduate next year. I need to know what to do now, where I should go next. My university does not offer any CS classes, but I am willing to work extracurricularly if it means gaining relevant experience. I'm not completely at square 1, I have some experience with programming, but not nearly enough to compete with a Bachelor's.

1) **Do I need a Bachelor's in CS to pursue programming?** I have developed and published a handful of websites and iPhone/Android applications over the years, but I never took it on as a full time job. I am conversant in most relevant computer languages, but never as a result of any official classes, just through personal study.

2) **What resources are available to me regarding open positions in CS?** I have been stuck in my birth state my entire life, and thus have little exposure to the job market outside of a 200-mile radius. I am engaged and plan to move away with my fiancé when we both graduate next year, but I would like to move somewhere that will be conducive to my programming ambitions. Are there any notable cities that are iconic in the CS market?

3) **What should I be focusing on now?** I would like to finish out my degree program so the past 3 years won't be completely for naught, but what should I be doing in the meantime? Should I pursue some form of internship, should I attempt to strike further out in freelance work, or should I take some sort of online classes?

4) **What do employers look for?** If I'm looking to make the best first impression, what sort of things should I become conversant in? Is there a core set of languages I should go ahead and start learning?

Honestly I'm just extremely lost and need to know what steps I should take from here. Also, if I can avoid paying for another 4 years of college, that would be great.

# Answer
> 2 votes
You are *already* making iOS Apps, so you most likely *already* know at least 1 programming language. You **don't need a degree in computer science to be a programmer**. You (usually) need a degree in computer science to be a computer *scientist*.

You should continue programming, as **it's the only way you'll get better**. If you want to put it on your resume you need to be extremely fluent in at least 1 language and *show* that you're fluent (you're off to a great start with those iOS apps).

Employers don't look for a CS degree, although it is nice. Most jobs require a bachelors degree, but not *in* computer science per se.

Putting personal projects on your resume along with an explanation of your ability to write code should be good enough. And trust me, they will be testing your abilities as a programmer from the second you get a callback.

During the first interview, you will most likely be asked to write code on paper with a developer at the company. If you pass that, they might ask you to complete a lengthy exercise to demonstrate your proficiency.

So in my opinion: **Keep doing what you're doing**. If you want to land a job as a programmer master at least 1 language.

---
Tags: programming-languages
---


# Question
Title: How do you call this typical file name order?
```
log1.gz
log10.gz
log100.gz
log101.gz
log102.gz
log103.gz

```

# Answer
As already stated in the comment, it is called **lexicographic order** in ascending direction; description can be found in this answer.
> 1 votes

---
Tags: terminology, sorting, strings
---


# Question
Title: Why should I use Huffman enoding if it makes my data longer?
I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag.

My request / response xml looks something like below

```
<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX
   </compatible>
</products>

```

I was given a suggestion to use Huffman code to compress compatible list data.

What I am confused about is how would Huffman encoded data in the XML reduce the size of the request / response XML as the resulting stream of binary data in the compatible tag might just increase the length and size of XML.

Example: Huffman encoding first 2 product IDs generates a longer binary string Original String: 2TR,07N Encoded binary String: 11101100110100010101

So my XML will change from

```
<products>
   <id>
     2XZ
   </id>
   <compatible>
   2TR,07N
   </compatible>
</products>

```

TO:

```
<products>
   <id>
     2XZ
   </id>
   <compatible>
   11101100110100010101
   </compatible>
</products>

```

Am I missing something obvious here?

# Answer
I cannot see the benefit of Huffman coding in XML. First, the coding dictionary of each symbol has to be known on the receiving end, i.e.

```
<dictionary><code symbol=",">01</code><code symbol="2">11</code>....</dictionary>

```

Second, the Huffman coded data should be represented as 8-bit data to be space efficient. For example, your Huffman code for `2TR,07N` becomes `&xECD1;&x50;`. However, 8-bit data is incompatible to XML because a lot of symbols are reserved for tags "\<\>" or attributes ":=".

If you are free to use any compression technique, I would suggest gzipping your data and then encoding the 8-bit data as base64. In this case, the string (264 characters without comma)

```
2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX

```

will be encoded as (232 characters)

```
H4sIACSf+1YAAxXPS1ZCMRBF0b5jSeMlgmDTDyAKfuDVFZ3/QNg0zlrVqcrOmE9tWn22MZ/btB5a
mGeVol9d9Kf/NmpS19C9Fna6bvNSD1pprUc96VkvetVGW+30pn2bune7O32p2/67PnTQUXz1pW/9
6KSzOIuzOIuzOIuzOMMZznCGLf4VvrgfvvCFL3zhC1/4whe+8IUve/GEJzzhCU94whOe8IQnPOEJ
T3hyubsCdDvGCWABAAA=

```

It is worth noting that `gzip` has Huffman coding in design, and the `base64` encoding is a common practice for embedding PNG images in HTML.

References:
> 2 votes

---
Tags: data-compression, huffman-coding
---


# Question
Title: Why there is no constraint on "Prover" in definition of $IP$?
According to the definition of $IP$ given in Sanjeev Arora and Barak there is no constraint on the running time of the "Prover" ( when "verifier" sends a message to the "Prover" and expects a message in return from it ). Why is it so ? Also the book says the "Prover" might compute some undecidable function. How is that possible ? Am I missing something trivial ?

# Answer
There's nothing canonical for *what* constraint one might put on it.  Requiring complete efficiency would give BPP, since the algorithm can just simulate the whole interaction.  Requiring efficient-given-a-polynomial-length-string would give MA, since the prover could just send its string to the verifier.  It turns out that PSPACE is always enough, so letting the prover be at least that powerful yields the same class as not constraining the prover.  I suppose
things from FUP to \[CH given a polynomial-length string\] might give intermediate classes.
> 4 votes

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


# Question
Title: Why do we pop the dollar symbol when it's already present in the stack in PDA?
Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack.

I would like to know if we could replace the transition given here(p.54) of the form

A,`$` $\to$ 0`$`

with

A,$\epsilon \to$ 0.

# Answer
> 2 votes
The "end-of-stack" symbol (often $\\$$) is necessary for the automaton to know when there are no more stack symbols. Therefore, when we reach $\\$$ we have two options:

1. Remove the $\\$$ and terminate¹.
2. Put it back there for later, maybe adding additional symbols.

Ergo, as long as you do not want to terminate you have to keep putting $\\$$ back when you find it.

*Why* does it have ot be like that, you ask? In the definition I know, PDAs always "take out"² the top-most symbol. So the creator of the PDA has no choice but to deal with the $\\$$ once it is on the top of the stack.

But *why* define it like that, you ask? If PDAs were allowed to not consume the topmost stack symbol they'd be inherently nondeterministic. And since you gain nothing by this choice -- doing nothing with the stack is trivial to simulate by just putting the symbol you read back -- there is no reason to introduce this source of nondeterminism.

---

1. Depending on the definition, termination is *defined* by empty stack or you have to switch into a final state. The definitions are equivalent.
2. Remember that it's an declarative, not an algorithmic definition!

---
Tags: automata, pushdown-automata
---


title: Merkle tree collision probability

text:
# Question
Title: Merkle tree collision probability
Say I use a perfect 128-bit hash function to construct a merkle tree. By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the function, over a large enough domain of hashed entities.

Does the root have a higher collision probability than any of the leafs?

To elaborate, say that I have 1000 entities, each of which has a $p\_1=1/2^{128}$ probability of colliding. I construct the tree so that the lowest level spans the range of $2^8$ values, and upper levels span the range of two lower levels.

What is the probability of a single collision in such a tree? What is the probability of two collisions in a single tree? $n$ collisions?

# Answer
> 0 votes
I used Infer.Net to calculate the answer. For anyone interested, here's the code.

```
open MicrosoftResearch.Infer;
open MicrosoftResearch.Infer.Models
open MicrosoftResearch.Infer.Distributions
open MicrosoftResearch.Infer.Factors
open MicrosoftResearch.Infer.FSharp;
open System

let treeCollisionProb() =
    let hashSize = 128
    let entityCount = 512
    let subRangeCount = 32

    let subRangeWidth = hashSize / subRangeCount
    let upperLevelChildrenCount = 2

    let avgEntitiesPerRange = entityCount / subRangeCount

    let hashCollision() = Variable.Bernoulli(2. ** -128.)

    let nodeCollision (children:Variable<bool>[]) =
        let anyChildCollision =
            children
            |> Array.reduce (|||)

        let childHashSequenceHashCollision = hashCollision()
        let parentCollisionWithoutChildCollision = ~~~anyChildCollision &&& childHashSequenceHashCollision

        anyChildCollision ||| parentCollisionWithoutChildCollision

    let subRange() =
        [| 1..avgEntitiesPerRange |]
        |> Array.map (fun i -> hashCollision())

    let subRanges =
        [| 1..subRangeCount |]
        |> Array.map (fun i -> subRange())

    let subRangeParents = subRanges |> Array.map nodeCollision

    let rec constructTree (rangeWidth:int) (children:Variable<bool>[]) =
        if rangeWidth = 1 then children.[0]
        else
            let chunks = children |> Array.chunkBySize upperLevelChildrenCount
            let parents = chunks |> Array.map nodeCollision
            constructTree (rangeWidth / upperLevelChildrenCount) parents

    let tree = constructTree subRangeWidth subRangeParents

    let engine = InferenceEngine()

    let result = (engine.Infer<Bernoulli> tree).GetProbTrue()
    result

[<EntryPoint>]
let main argv =
    let prob = treeCollisionProb()

    printfn "tree collision probability: %g" prob

    let treesTillCollision = 1./prob
    printfn "trees till collision: %.3g" treesTillCollision

    let timeTillCollisionSec (genIntervalSec:float) = genIntervalSec * treesTillCollision

    let intervalSec = 5.
    let secsInYear = 365 * 24 * 60 * 60
    let yearsToCollision = (timeTillCollisionSec intervalSec) / (float secsInYear)
    printfn "If we generate a single tree every %.0f seconds, we'll have to wait %.4g years in average to see a collision" intervalSec yearsToCollision

    Console.ReadLine() |> ignore
    0

```

# Answer
> 4 votes
Yes, the root has a higher probability of collision.

Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.

The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the probability that $\langle h(A),h(B) \rangle = \langle h(X),h(Y)\rangle$. The probability of the second part is $p^{-2}$ and the probability of the first is $p^{-1}(1-p^{-2})$, for a total of $p^{-1} + p^{-2} - p^{-3}$, which is slightly greater than $p^{-1}$, the probability of a single collision.

That assumes all of your leaves have different values. If the leaves are all the same but one, the probability of collision at the root is proportional to the logarithm (base 2) of the number of leaves times the collision probability of the underlying hash function.

---
Tags: hashing
---


# Question
Title: Inplace sorting of variable length records
Is there an in-place algorithm for sorting variable length records?

For example a vector of arbitrary length strings.

Most provided in-place algorithms assume that you can switch two elements without affecting the rest of the structure. However this does not work if your records differs in size.

Googling leads me to this. However, they finish with:

> After writing all sorted output blocks, merge them into the final sorted file using any convenient merging algorithm. When allocating buffers or making other preparations, the merging steps can take advantage of the fact that every variable-length block written by step 7 has the same maximum size (just less than the size of buffer 1 or 2)." I do not feel that doing in-place merging of arbitrary length records is in any way trivial.

# Answer
If we're just dealing with packed variable-length records, swapping two adjacent elements is not difficult, so bubble sort will work.

There are some techniques for creating space while sorting to use for auxiliary data structures, based on the fact that (partially) sorted data has less entropy than unsorted. See Radix Sorting With No Extra Space by Franceschini, Muthukrishnan, and Patrascu for examples. They don't deal with variable length records specifically, but some of the ideas there might be useful.
> 1 votes

---
Tags: algorithms, sorting, strings, in-place
---


# Question
Title: Is it decidable whether a linear language contains a square?
A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings).

**Question:** Is it decidable whether a linear grammar generates a square?

What did I do? I know that it is undecidable whether a linear grammar contains a palindrome, and that it is undecidable that a context-free grammar contains a square. Both via reduction from PCP. Given two sequences $(u\_1,\dots, u\_n)$ and $(v\_1,\dots, v\_n)$, strings of the form $u\_{i\_1}\dots v\_{i\_k}\\#v\_{i\_k}\dots u\_{i\_k}$ are linear, whereas those of the form $i\_1\dots i\_k u\_{i\_1}\dots u\_{i\_k}\\#j\_1\dots j\_k v\_{j\_1}\dots v\_{j\_k}\\#$ are context free.

# Answer
> 4 votes
It is indeed undecidable whether a linear grammar generates a square. Same technique, reduction from PCP.

Starting with the two sequences of strings $(u\_1,\dots,u\_n)$, $(v\_1,\dots,v\_n)$ that define the PCP we can build a linear grammar with strings of the form $u\_{i\_1}\dots u\_{i\_k} j\_k \dots j\_1 \\# v\_{j\_1}\dots v\_{j\_k} i\_k \dots i\_1 \\# $.

Rules like $S\to A\\#$;

$A \to u\_i A i \mid u\_i B i$;

$B \to j A v\_j \mid j v\_j$.

Such a string is a square if both the indices and the strings match, hence iff we generate a solution of PCP.

(I really did not know the answer when I posted the question... *Sorry*. I started examining ways to show decidability.)

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


title: Equivalent formulae with different CNF

text:
# Question
Title: Equivalent formulae with different CNF
I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the following:

Give an example which shows that proving equivalence of two formulas by bringing them into conjunctive normal form is incomplete. By incompleteness, we mean that there are examples of formulas which are equivalent but their conjunctive normal form is not the same.

# Answer
It depends on the algorithm for obtaining CNF of a formula. A simple truth table-based method will always produce *syntactically* the same CNFs for equivalent formulas, since it *in a sense* just gives you the rows of the truth table for which the formula evaluates to false.

A trivial example of equivalent formulas, which are both in CNF:

$$A \wedge B$$ $$(A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee B).$$

Non-uniqueness of CNF means that one can build an algorithm, which returns essentially different CNFs for equivalent formulas. For example, as a first step the conversion algorithm can check if a formula already in CNF and return it immediately.
> 1 votes

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


# Question
Title: Language grammar correction with supervised learning
I want to work on automatic grammar correction using machine learning (possibly using recurrent or deep neural networks). The algorithm will be supplied with both corrected and initial documents for supervised learning.

I am now looking for some survey or research papers to start with. I have searched and downloaded tens of articles but none of them seems related.

* I would appreciate if someone could provide a few good starting points (papers, books).
* also I suspect that I am not using the correct keywords for my search. I'll appreciate if you could also suggest suitable search keywords.

# Answer
> 1 votes
The following paper from 2011 proposes a nice approach for using language modeling to do grammar correction, as well as an evaluation framework.

* Park and Levy, *Automated whole sentence grammar correction using a noisy channel model*. In *Proc. 49th Human Language Technologies*, volume 1, pp. 934–944. Association for Computational Linguistics, 2011. (Available from the ACM Digital Library.)

---
Tags: machine-learning, neural-networks, natural-language-processing
---


# Question
Title: Can we make a non-regular language regular via concatentation?
My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?

# Answer
If we allow $A$ to be the empty language, which is regular, then we have that $L = \\{w\_1w\_2 | w\_1 \in A, w\_2 \in B\\} = \emptyset = A$.

For the slightly more interesting problem in which A must be a non-empty regular language, then we can construct a $B$ such that no non-empty $A$ results in a regular $L$

Let $B=\\{bc^nd^n | n \> 0\\}$. Let $A$ be any regular language and consider $L=\\{w\_1w\_2 | w\_1 \in A, w\_2 \in B\\}$. Note that, contrary to the assumption in J.-E. Pin's answer, $B$ is irregular but doesn't contain the empty word.

Suppose $L$ is regular. There exists some DFA, $M=(S,\Sigma,\delta,q\_0,F)$, which accepts $L$. Regardless of how $A$ is constructed, we know that every word in $L$ must have a last occurrence of $b$. Let $Q$ be the set of states travelled to immediately after the last $b$ in all possible accepting traversals. Note that $Q$ cannot be empty, since the shortest string in $B$ is $bcd$. Let $S'$ be the set of states visited in all possible accepting traversals at some point after the last $b$. Construct $M'=(S',\Sigma,\delta',q\_0',F)$, where $\delta'$ behaves identically to $\delta$, except for the fact that $\delta'(q\_0, \varepsilon)=Q$.

I claim that this NFA accepts the language $C=\\{c^nd^n| n \> 0\\}$. For any $w' \in C$, we must have that there is some traversal from some element of $Q$ to some element of $F$, since $M$ must accept some string with this as a suffix. For any $w' \in \Sigma^{\*} \setminus C$, we can pick a $w \in A$ and form the word $wbw'$. If $M'$ accepts $w'$, then it must be the case that $M$ accepts $wbw'$, since there must have been some traversal from some state in $Q$ to $F$ which is also valid for $M$. However, because of our choice of $w'$, it cannot be the case that $wbw' \in L$, so $M'$ must reject $w'$.

So $M'$ accepts $C$, but this language is not regular, leading to a contradiction.

Hence, if $A$ is non-empty, then $L$ cannot be regular.
> 3 votes

# Answer
Yes this is possible. Consider the example given below:

Let $B = 1^p$ where $p$ is prime. This is non regular. Let $A = 1^n$ where $n \in \mathbb{N}$. This is regular.

$AB$ will simply give us $1^n$ with $n \> 2$ and this is regular since any number greater than $2$ can be reprsent as $2+x$ where $x \> 0$
> 12 votes

# Answer
Let $\Sigma$ be a nonempty alphabet. Let $B$ be *any* nonregular language on $\Sigma$ containing the empty word and let $A = \Sigma^\*$. Then $L = AB = A$ is regular.
> 12 votes

# Answer
Given a language $B$, the language $\varnothing B = \varnothing$ is regular. Apart from this trivial solution, it is not always possible to find a non-empty language $A$ such that $AB = \\{uv \mid u \in A \wedge v \in B\\}$ is regular. It is possible for many non-regular $B$ (e.g. if $B$ contains the empty word, or if $B$ is on a unary alphabet) but not for all $B$.

Take $B = \\{ca^n \mid n\in\mathbb{P}\\}$ where $\mathbb{P}$ is the set of primes. Whatever $A$ is, if $A$ is not empty then $AB$ is not regular, because to test membership in $AB$, it is necessary (due to the “stopper” symbol $c$) to use potentially unbounded memory to test the primality of the number of $a$'s at the end.

To prove this, let $u \in A$ (since we assumed that $A$ is not empty). If $AB$ is regular, then so is $L\_1 = AB \cap uca^\*$, and so is the left quotient of $L\_1$ by the singleton $\\{uc\\}$ which is $L\_2 = \\{w \mid ucw \in AB \wedge ucw \in uca^\*\\} = \\{w \in a^\* \mid ucw \in AB\\}$. This language is just $L\_3 = \\{a^n \mid n\in\mathbb{P}\\}$ (if $w \in L\_2$ then there exists $v\in A$ and $k\in\mathbb{N}$ such that $ucw = vca^k$, and since $w$ contains b^kno $c$, this implies that $w = a^k \in L\_3$; conversely, if $w \in L\_3$ then $cw \in B$ so $ucw \in AB$). $L\_3$ is a well-known non-regular language, we have a contradiction.
> 6 votes

# Answer
While your question is asking for an existential proof, it reminds me of the branch of comp. sci. called Regular Approximations.

The idea is to take a non-regular language $L$ and then find a regular language $A$ such that $L \ominus A \rightarrow 0$ under some condition / subset of $L$ (where $\ominus$ is the symmetric difference), ie find a regular language which is "arbitrarily close" to $L$ for some subset that you care about. Often you accomplish this by taking a finite subset of $L$ with large measure over your subset of interest, and then concatenating it with a carefully chosen regular language.

You can find lots of interesting reads on Google Scholar if you search something like "regular language approximation context-free".
> 0 votes

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


title: How to read 'max min' and 'min max'?

text:
# Question
Title: How to read 'max min' and 'min max'?
Here is an exercise I came across while studying MaxFlow / MinCut and I'm rather stumped:

> Designate $G = (V, E)$ as an undirected graph that has at least two vertices. Every edge $(e)$ on this graph has capacity $c\_e$. Pick two arbitrary vertices from $G$ and label them $s$ and $t$ respectively.
>
> Now, we'll let $P\*$ be the set of $s-t$ paths in the graph, and let $C\*$ be the set of $s-t$ cuts -- meaning, $C\*$ refers to the subset of edges in $G$ that constitute all possible $s-t$ cuts.
>
> Demonstrate that the following equality is true:
>
> $\max\_{P\in P\*} \min\_{e \in P}c\_e = \min\_{C \in C\*}\max\_{e \in C}c\_e$

My issue: I'm having trouble parsing the above equation. The LHS appears to be describing the longest(?) of all possible s-t paths, and the edge with the minimum capacity along that path. The RHS appears to be describing the minimum number of edges(?) possible in a subset of edges constituting an s-t cut, and the edge with the max. capacity within that subset? I'm frankly not even sure whether the above equation is meant to involve a multiplication.

Still, I figure there must be a way to parse and understand the equation correctly such that the equality would always hold, and that it can be demonstrated as such. I'd appreciate any help in this matter.

# Answer
> 2 votes
> I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have *nesting* here:

$\max\_{X \in \mathcal{X}}\ ( \min\_{x \in X} x)$

is the *largest minimum* of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \\{ \\{1,2\\}, \\{3,4\\} \\}$. Then, the following equalities hold:

1. $\min\_{X \in \mathcal{X}} \min\_{x \in X} x = 1$.
2. $\min\_{X \in \mathcal{X}} \max\_{x \in X} x = 2$.
3. $\max\_{X \in \mathcal{X}} \min\_{x \in X} x = 3$.
4. $\max\_{X \in \mathcal{X}} \max\_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

```
Xs.map { X => X.max }.min

```

---
Tags: notation, mathematical-foundations
---


# Question
Title: Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm?
I read it in not only one place. People write theorems of the form:

> *Theorem:* ALG is an O(1)-approximation algorithm

It means that ALG is a constant factor approximation algorithm but is it safe to say that? I mean it misleads. Why am I asking?

Because, many problems I know of do not have an $\alpha$-approximation algorithm where $\alpha\<\gamma$, unless P=NP. For example, the k-center problem does not have an $\alpha$-approximation algorithm where $\alpha\<2$, unless P=NP. Well, there is a simple greedy algorithm that is 2-approximation algorithm for the k-center problem. Can we say that this greedy is O(1)-approximation algorithm for the k-center problem? I mean, if it is an O(1)-approximation algorithm for the k-center problem, it is, for example, an 1.9-approximation algorithm, no?

# Answer
When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$, which is why we use the $O(1)$ notation.

You don't get to *choose* the constant – rather you are only given that such a constant *exists*.
> 6 votes

---
Tags: approximation
---


# Question
Title: Difference between Binomial and Fibonacci heap (marking)
I am confused why Binomial heaps do not utilize marking.

Concerning Fibonacci heap children:

```
Each tree in a Fibonacci heap is allowed to lose at most two children before
that tree needs to be "reprocessed" at a later step. The marking step in the
Fibonacci heap allows the data structure to count how many children have
been lost so far. An unmarked node has lost no children, and a marked node
has lost one child. Once a marked node loses another child, it has lost two
children and thus needs to be moved back to the root list for reprocessing.

```

How do Binomial heaps not need marking? It seems like in Fibonacci, this is in place so that when a marked node loses another child, it knows to move it back to the root and reprocess. I do not understand how Binomial heaps can possibly handle this without marking.

# Answer
> 1 votes
In binomial heaps the structure of the trees in the heap is very strict, they all have a number of elements that is a power of two. When a node is removed it is the root of a tree, and all the children (which are again roots trees with a power of two elements) are merged with the other original trees.

There are no nodes that have an "imperfect" number of children, and there is no marking needed to indicate that.

---
Tags: algorithms, sorting, heaps
---


# Question
Title: How can I represent state or environment in the $\lambda$-Calculus?
I have seen in different tutorials how to represent numbers and booleans in the pure $\lambda$-Calculus, and how to define some arithmetic and logic operations. But what if I want to represent other constructs, not usually encouraged in pure functional languages, like state (assignment of values to variables) and sequencing (evaluating $e\_1$ before $e\_2$)?

For example, how would I encode an assignment "$v := e$" (where $v$ is a variable and $e$ an environment)? And what about encoding "$x := 2; y := y + x$"? (The point is that there is a dependency among statements, and they should be evaluated/executed in the correct order.)

# Answer
Such a thing is, for the most part, impossible in the pure lambda calculus: all variables represent immutable values.

However, you can fake it in a number of ways.

The simplest is parameter passing. For a function which has a "state", you give it an extra parameter, which is a data structure mapping variables to their values. Any time you alter a variables value, you just create a new store with the updated value, and use it as the new parameter.

This pattern of passing the state to each computation in sequence can be abstracted using a State monad, or something similar. A state monad provides a pattern where the machinery of creating a new store, updating its values, and correctly passing it to future functions.

Monads provide a sequencing operator, which allow for the ordered evaluation that you mention.

There exists calculi which have mutation built into them, but first off, they aren't the *pure* calculus as you asked for, and in such cases, you don't encode mutation, you add it as a primitive operation.
> 4 votes

---
Tags: lambda-calculus
---


title: Equivalence of DFA' definitions

text:
# Question
Title: Equivalence of DFA' definitions
According to wikipedia DFA accepts word $w$ by one of two definitions:

1. A word $w$ is accepted by $M$ if $\hat\delta(q\_0,w)\in F$.
2. A word $w=w\_1w\_2\dots w\_n$ is accepted by $M$ if $\exists r\_0,\dots,r\_n\in Q$ such that:
    * $r\_0=q\_0$
    * $\delta(r\_i,w\_{i+1})=r\_{i+1} \ \forall 0\le i\<n$
    * $r\_n\in F$

Assuming that some word $w$ is accepted by definition 1, how can we show it is accepted by definition 2?

Thank you!

# Answer
> 1 votes
Since $\hat\delta$ is defined as the transitive closure of $\delta$, definition 1 trivially follows from definition 2 and vice versa.

---
Tags: automata, finite-automata, simulation
---


title: Variable rule in dependent type theory

text:
# Question
Title: Variable rule in dependent type theory
This is the = Type variable rule that I'm seeing through out the my course and unable to grasp it completely.

$$\dfrac{\phi \vdash \Gamma\[\mathrm{ctx}\] \qquad \Gamma(x) = \tau} {\phi; \Gamma \vdash x : \tau} \textsf{(ty-var)}$$

The first thing in antecedent looks like it's stating that $\Gamma$ is well-formed under the context $\phi$, is that right? What does the second thing in antecedent mean? I have a feeling of this but I am unable to get this simple rule.

# Answer
Essentially, $\Gamma$ is a store that maps variables to types.

This rule says that we can deduce that a variable has a type in a context if that type is stored for our variable in the context.

The rule is deliberately simple, and is a base case for the inductive process that is type derivation.

In short, to check the type of a variable, just look it up in the environment.
> 4 votes

---
Tags: type-theory, dependent-types
---


# Question
Title: How do I show that an equivalence class of a language containing an empty string is infinite
The question is as follows:

> Let $L$ be a language (not necessarily regular) over an alphabet. Show that if the equivalence class containing the empty string $\[ \epsilon \]$ is not $\\{ \epsilon \\}$, then it is infinite.

How do I go about answering this? Would I need to use Myhill-Nerode theorem? From what I've read there's a corollary from the theorem that if a language defines an infinite set of equivalence classes, it is not regular. I'm not sure if that helps answer my question though.

# Answer
Let $A$ be the alphabet. I suppose that the equivalence you are referring to is the equivalence $\sim$ defined on $A^\*$ by $u \sim v$ if and only if, for all $x \in A^\*$, $$ ux \in L \Leftrightarrow vx \in L $$ Now suppose there is a word $u \in A^+$ such that $u \sim \varepsilon$. Then by definition, $x \in L$ if and only if $ux \in L$. It follows by induction on $n$, that for all $n \> 0$, $x \in L$ if and only if $u^nx \in L$ and thus $\[\varepsilon\]$ contains $u^\*$. If the alphabet is nonempty, it follows that $\[\varepsilon\]$ is infinite.
> 2 votes

---
Tags: formal-languages, regular-languages, strings
---


title: Is this a well-known NP-hard problem?

text:
# Question
Title: Is this a well-known NP-hard problem?
Let $R = \\{1, \ldots, n\\}$ and $S = \\{S\_1, \ldots, S\_m\\}$ a collection of subsets of $R$ such that $R = \bigcup\_{i = 1}^m S\_i$ and, for $n \> 3$, $$3 \leq \vert S\_i \vert \leq 4 \\, , \enspace i \in \\{1, \ldots, m\\} \\, .$$

Then, I want to know the subset—or subsets, since there may be more than one valid solution—$T$ with **minimum cardinality** such that every $S\_i$ has at least one element in $T$. I suspect this is an NP-hard problem (or NP-complete in its decision version), but I don't know if it's one that has a name.

As an example, consider $R = \\{1, 2, 3, 4, 5\\}$ and $S = \\{S\_1, \ldots, S\_9\\}$, where

* $S\_1 = \\{1, 2, 3\\} \\, , \enspace S\_4 = \\{1, 4, 5\\} \\, , \enspace S\_7 = \\{1, 2, 3, 4\\} \\, ,$
* $S\_2 = \\{1, 2, 4\\} \\, , \enspace S\_5 = \\{2, 3, 5\\} \\, , \enspace S\_8 = \\{1, 3, 4, 5\\} \\, ,$
* $S\_3 = \\{1, 2, 5\\} \\, , \enspace S\_6 = \\{3, 4, 5\\} \\, , \enspace S\_9 = \\{2, 3, 4, 5\\} \\, .$

Here, the solutions are $T = \\{\\{1, 3\\}, \\{1, 5\\}, \\{2, 4\\}, \\{2, 5\\}\\}$. (I'd be happy even if I knew just one of them.)

Note that I'm not asking for an algorithm to solve the problem. I just want to know where this is or reduces to a well-known problem.

# Answer
3-Hitting Set problem is known in parameterized complexity theory. The requirement $\cup S\_i=R$ can always be assumed without loss of generality. See e.g. An efficient fixed-parameter algorithm for 3-Hitting Set. According to this link it is NP-hard in its usual (not parameterized) form. Proving NP-completeness of your problem we give reduction FROM 3-Hitting Set to your problem not vica versa. Therefore your problem is NP-complete (in its decision form).
> 1 votes

---
Tags: algorithms, complexity-theory, optimization, np-complete, reductions
---


# Question
Title: Why is `map insertionsort` not to equal to`map mergesort`?
In the type theory podcast ep. 3, Dan Licata claims that the fact that for every input, insertionsort and mergesort give the same result does not imply that the result would be equal when used as higher order functions as arguments to a third function, i.e. `map insertionsort` does not have to equal `map mergesort`.

He explains this by "because you don't know that, as functions, insertionsort and mergesort are equal" but I still don't get it.

Why is this the case? A counter example would be great!

# Answer
> 11 votes
It has to do with the axiom of extensionality, i.e. whether you accept it for functions or not.

The statement of this axiom with regard to functions is $$\forall f,g:A \to B,\ ((\forall x:A ,\ f\ x = g\ x) \Leftrightarrow f = g).$$ Informally it means that if two functions are equal point-wise, then we consider them equal.

*Syntactically* merge-sort and insertion-sort are *not* equal, but if we don't care about their time and memory complexities (I mean if care only about their results) we can accept the axiom of extensionality and consider them equal. That means we can substitute one for another in every expression under consideration without actually changing anything. In this case $\text{map}\ f = \text{map}\ g$.

On the contrary, if we reject the aforementioned axiom, then we can only prove a statement like this: $$(\forall x:A,\ f\ x = g\ x) \implies \forall xs:\text{list}\ A,\ \text{map}\ f\ xs = \text{map}\ g\ xs.$$ Notice that the conclusion is not the same as $\text{map}\ f = \text{map}\ g$.

---
Tags: type-theory, functional-programming, equality, homotopy-type-theory
---


# Question
Title: If a language is X-complete, is its complement is X-complete as well?
I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then its complement is X-complete? Why?

I was thinking that it has to do with accepting states in Turing Machine. You should just switch them so the complexity should be the same but I'm not sure.

# Answer
> 1 votes
> I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure.

That argument does not always work. You are probably thinking of the proofs that REG and R are closed against complement. Note how the same technique alread breaks down for CFL; it's not that easy for NPDA (or, in fact, for any non-deterministic automaton model). Also, we know that RE ≠ co-RE so the technique does not even work for all deterministic models.

This leads me to this answer: the flip-final-state technique works for *membership* in some *deterministic* classes; I'm not sure if *completeness* then works out as well, but my gut feeling is yes.

The technique is unlikely to work even for membership in *nondeterministic* classes. As a matter of fact, we do *not* know if NP = co-NP and, as a consequence, we do not know if NPC = co-NPC. And, of course, REC ≠ co-REC.

---

Another thing to keep in mind is that the notion of completeness depends on the type of reduction you consider. For instance, above mentionen open question about co-NPC and NPC applies only to Karp reductions; under Cook reductions, co-NPC = NPC (see e.g. here).

---
Tags: complexity-theory, time-complexity, np-complete, closure-properties
---


# Question
Title: Can a non-regular language be made regular via concatenation when they don't share characters?
So this is a follow-on question to my other question (Can we make a non-regular language regular via concatentation?).

Given the following,

$L = \\{0^n1^m2^m \mid n\>1, m\>1\\}$

$A = \\{0^n \mid n\>1\\}$

$B = \\{1^m2^m \mid m\>1\\}$

Is $L$ in fact just $A$ and $B$ concatenated (I believe it is, but I want to verify that)?

Further, does proving $B$ non-regular prove that $L$ is non-regular since they don't share characters?

# Answer
> 3 votes
First, the equality $L = AB$ is correct. Next, if you know that $B$ is non-regular, you can prove that $L$ is non-regular as follows.

Suppose that $L$ is regular. Then $(00)^{-1}L = \\{0^n1^m2^m \mid n \geqslant 0, m\>1\\} = 0^\*B$ is regular. It follows that $0^\*B \cap \\{1,2\\}^\* = B$ is regular. Contradiction.

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


# Question
Title: Explanation of a simple algorithm's Big O complexity
I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation:

```
Loop2(n)
    for i := 0 to n
        j := 0
        s := 0
        while s <= i
            j := j + 1
            s := s + j

```

I can see that the outer loop (alone) is run $O(n)$ times, and that the inner loop is $O(\sqrt n)$. However, the part that confuses me is that the correct answer, according to the paper, is $O(n \cdot \sqrt n)$.

I though that, since the inner loop is dependent on $i$, that it would be run $\sqrt i$ times, for $i$ going from $0..n$. Meaning that in total, the loop would run roughly $n$ times, making the whole algorithm $O(n\cdot n)=O(n^2)$. I kinda drew the logic from an analysis of insertion sort, where $$\sum\_{i=0}^{n} n-i = O(n^2)$$

I think I remember the above correctly. Can anyone fix my broken logic here?

# Answer
> 0 votes
The inner loop is $O(\sqrt{i})$, you are correct. Since $i\leq n$, then $\sqrt{i}\leq \sqrt{n}$, and we have $n\times\sqrt{i}\leq n\times\sqrt{n}$. Hence the complexity is $O(n\sqrt{n})$.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Vector clocks: Why is it necessary to increment my clock on receiving a message?
Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes.

In this scenario, Why would I need to increment my own clock if I receive an update? (I noticed in the original paper on vector clocks, they didn't mention this rule, yet followed it in the examples...) Would it be sufficient if I only incremented my clock when **I** change the data object?

# Answer
> 4 votes
Look at the definition of $\<\_H$.

We say that $e\_1\<\_H e\_2$ (event 1 happened before event 2) if:

1. $e\_1,e\_2$ took place in the same process, and $e\_1$ happened first (events within the same process are ordered).
2. $e\_1,e\_2$ are the sending and receiving of some message $m$, correspondingly.

Finally, we take the transitive closure of the above, and this yield Lamport's happened before relation.

Our objective is to assign time stamps to events, $T\_{e\_i}$ with a partial order $\<\_t$, such that $e\_1\<\_H e\_2 \iff T\_{e\_1}\<\_t T\_{e\_2}$.

The timestamps suggested here are vectors in $\mathbb{N}^n$, with the ordering $T\_{e\_p}\<\_t T\_{e\_q} \iff T\_{e\_p}\[p\]\<T\_{e\_q}\[p\]$ where $e\_p,e\_q$ are events in processes $p,q$ correspondingly (assume each time stamp contains the process id).

Back to your question, not updating your clock upon receiving a message would cause your new relation $\<\_t$ to disagree with $\<\_H$ in events within the same process. For example, you would have $c\not\rightarrow d$ (figure 3). In addition, this is mentioned in the paper (rule 2, increase the local clock at each atomic event, which is either sending or receiving a message).

---
Tags: distributed-systems, synchronization, clocks
---


# Question
Title: Is it true that P is not equal to deterministic linear space complexity class?
I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class?

Is there some proof? Or should I find some algorithm which is not in P but it is in polynomial time complexity class or opposite way?

Do you know about some?

# Answer
We do know that $\mathsf{P} \neq \mathsf{DSPACE}(n)$. This is proved in answers to a question on Mathoverflow. The idea is that $\mathsf{P}$ is closed under polynomial blowup while $\mathsf{DSPACE}(n)$ isn't (due to the space hierarchy theorem); consult the link on Mathoverflow for the details.
> 5 votes

# Answer
We know that $DSPACE(n) \neq NP$ (we only know they are unequal, we don't even know if one is a subset of other or not).

We also know that $DTIME(n) \subseteq DSPACE(n) \subseteq NSPACE(n) \subseteq DTIME(2^{O(n)})$.

As Yuval Filmus pointed out $DSPACE(n) \neq P$.
> 1 votes

---
Tags: complexity-theory, time-complexity, space-complexity, polynomial-time
---


# Question
Title: Keeping a binary search tree by splitting nodes (like a B-Tree)
A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.

Can the same technique be used to keep a regular binary search tree balanced (since a binary search tree can be viewed as a 2 child maximum B-tree)? If so, does that rebalancing method have a name, and what are its advantages/disadvantages to other ways of keeping a BST balanced, such as Red-Black trees?

# Answer
> 2 votes
1-2 Brother Trees, as in "Purely Functional 1-2 Brother Trees" by Ralf Hinze in some way allow splitting a node. Like in 2-4 trees where nodes have 2 to 4 children, in 1-2 brother trees, nodes have 1 to 2 children.

The advantages are a bit hand-wavey: it is sometimes faster, and sometimes simpler, and sometimes uses less space.

---
Tags: data-structures, binary-trees, search-trees, database-theory, balanced-search-trees
---


title: Question about simple perceptron code

text:
# Question
Title: Question about simple perceptron code
I'm reading through Sebastian Raschka's Python Machine Learning, and I see something confusing that is not explained in the text.

In the code on this page: https://github.com/rasbt/python-machine-learning-book/blob/master/code/ch02/ch02.ipynb

## Implementing a perceptron learning algorithm in Python

In the training process, in addition to updating weights, I see this happening:

```
 self.w_[0] += update

```

Then later on, during "prediction," when weights are applied to input, I see `self.w_[0]` being used:

```
def net_input(self, X):
    """Calculate net input"""
    return np.dot(X, self.w_[1:]) + self.w_[0]

```

It looks like this is a bias being added into the perceptron, but the book says that `net_input` is simply calcuating "weights transpose dot x" and mentions nothing about this `+ self.w_[0]` part...

Can anyone take a look at the linked code and make sense of what's going on with the `self.w_[0]` part? Or has anyone else got this book that might explain why that's there?

# Answer
I suspect the book's English explanation is probably a simplification (or maybe it has adopted the standard convention of adding an extra dimension to x that holds a constant value $1$). It seems like most likely you've already given the explanation; it's adding the bias value.
> 1 votes

---
Tags: machine-learning, perceptron
---


title: High Dimensional Spaces for Images

text:
# Question
Title: High Dimensional Spaces for Images
Can anyone explain why pictures are not considered 2D, but rather high dimensional? Especially with regards to CV and AI.

# Answer
From one perspective, a picture is a 2D image, because it has height and width.

But from a machine learning perspective, we can think of a picture as a point in a high-dimensional space. In particular, suppose we have a greyscale picture that is $m\times n$ pixels, i.e., $m$ pixels wide and $n$ pixels high. Then there are a total of $mn$ pixels in the image. Each pixel has a greyscale intensity, which we can think of as a real number in the interval $\[0,1\]$. Therefore, we can think of the picture as being a collection of $mn$ real numbers. In other words, the picture can be treated as a $mn$-dimensional vector -- as an element of $\mathbb{R}^{mn}$. Thus, any particular picture can be thought of as an element of a high-dimensional space.

The latter perspective arises natural for some machine learning approaches to computer vision, e.g., where we feed the pixels of the image into the machine learning algorithm, where each pixel value is treated as a separate pixel.

(A color image can be thought of as an element of $\mathbb{R}^{3mn}$: for each pixel, we have three numbers, corresponding to the intensity in the red, green, and blue channels.)
> 5 votes

---
Tags: image-processing
---


title: Packing sets to maximize overlap

text:
# Question
Title: Packing sets to maximize overlap
We are given a set of $m$ elements $\\{e\_1,...,e\_m\\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e\_j)$ with $j\in \\{1,...m\\}$. We are further given a collection $S=\\{S\_1,...S\_n\\}$ of subsets of $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).

Furthermore,

1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.

2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. an element is part of more than one set) **we pay the weight of that element only once**. Obviously, there can be no overlap between subsets when considering different configurations.

**Objective:**

we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:

$\mathcal{U}=\\{a,b,c,d,e,f,g\\}$,

$w(a)=2$

$w(b)=2$

$w(c)=3$

$w(d)=4$

$w(e)=1$

$w(f)=2$

$w(g)=2$

$S=\\{S\_1, S\_2, S\_3\\},$

$S\_1=\\{a,b,c\\}, S\_2=\\{c,d,e\\}, S\_2=\\{e,f,g\\}$

$k=2$

In this case, since $k\<|S|$, it is obvious that more than one configurations are needed. Moreover, $S\_1$ and $S\_2$ should be packed together in the same configuration because of their heavy overlap ($S\_1 \cap S\_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.

Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?

The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.

Thank you!

# Answer
> 1 votes
When $k=1$, the problem is trivial: the optimal solution is to put each set in its own configuration.

When $k=2$, the problem can be solved in polynomial time using graph matching. Build a complete undirected graph with one vertex per set. The cost of the edge $(S\_i,S\_j)$ is the cost of putting $S$ and $T$ together in the same configuration (i.e., the weight of $S\_i \cup S\_j$). Now the optimal solution to your problem is given by the minimum-cost perfect matching in this graph. That matching can be computed in polynomial time using standard algorithms.

When $k=3$, the problem is NP-hard. In fact, it is NP-hard to determine whether a graph can be covered by a disjoint union of cycles of length $\le 3$ (i.e., whether you can find a set of cycles, where each cycle has length 2 or 3, where no two cycles have any vertex in common, and where every vertex appears in one of these cycles). This implies that your problem is intractible when $k\ge 3$.

The proof of the hardness result I alluded to can be found in Section 3 of the following paper:

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. David J Abraham, Avrim Blum, Tuomas Sandholm. EC 2007.

That said, not all hope is lost. There are techniques available for finding a solution that will be close to optimal, using integer linear programming. For instance, you can express your problem as an instance of integer linear programming and then apply an off-the-shelf ILP solver. See the paper above for some more sophisticated techniques that might be applicable in your situation as well.

---
Tags: reductions, np-hard, packing
---


# Question
Title: calculate result of multiplication between two 32 bits vars into two 32 bit vars
how would I go about multiplying two 32 bit numbers (lets say unsigned) and putting the result into two 32 bit vars , one for the msbits and one for lsbits .

It should be simple but im stuck

thanks !

# Answer
> 1 votes
I'm assuming you're dealing with a circuit.
Since you are using two 32 bits, your result will be 64 bit.
In this case there are a few ways to go about this.

---

The simplest is to add, and bit-shift.
The other (much faster) way is to use Boothe's Algorithm.

Here are a few links to resources that may be helpful.

Binary Multiplier
Boothe's Algorithm

---
Tags: multiplication
---


# Question
Title: A key-value datastructure with fast (on average) member move and nearest neighbors search?
I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N neighbors in a range surrounding a given key) as fast as possible in terms of search algorithmic complexity (on average). Also I need a fast (on average) remove-insert or key update mechanism in that datastructure. I wonder what is such structure?

# Answer
> 3 votes
An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.

# Answer
> 2 votes
The Covertree is a specialized data structure for neighbour search. However I don't know it's update performance.

A better option may be the PH-Tree (my own implementation). It is similar to a quadtree, but implemented as a prefix-sharing bit-level trie.

Advantages:

* Maximum depth of the tree is 64 (assuming 64bit per dimension)
* No reordering, ever. This is important for insertion/deletion/updates, at most two nodes are modified for every insert/delete.
* It has a dedicate `update()` method for moving points. This is especially efficient for moving 'small' distances.
* Very good N-neighbour-serach performance, especially for low numbers of N, such as closest 10 neighbours or so.
* Quite space efficient in memory
* Scales very well with large number of entries (1,000,000 or more)
* Very good with clustered data (it prefers clustered data of evenly distributed data)

Disadvantages:

* Less efficient for small data sets
* Complex to implement, currently there is only a Java implementation available, see link above. (One reason: Nobody has yet managed to write a C++ implementation that is faster than the Java version...?!?!)

---
Tags: data-structures, search-algorithms, trees, nearest-neighbour, space-partitioning
---


# Question
Title: Decomposing the n-cube into vertex-disjoint paths
I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be better suited elsewhere. If so, please feel free to move my question.

Let $\mathcal{Q}\_n$ denote the $n$-cube graph. Given a set of vertices $S = \\{s\_1, \ldots s\_k \\}$ and $T = \\{t\_1, \ldots t\_k\\}$, we would like to decompose $\mathcal{Q}\_n$ into $k$ vertex disjoint paths $P\_1, \ldots P\_k$, such that each $P\_i$ begins with $s\_i$ and ends with $t\_i$. Here, two paths are vertex-disjoint if they do not share any vertices. In addition, I require that every vertex in $\mathcal{Q}\_n$ be part of some path $P\_j$. I would like to know under what conditions (particularly on $S$ and $T$) can we guarantee that such a decomposition exists?

Also, I would like to know the name of this problem so that I can better search for references.

# Answer
I found the following result due to Gregor and Dvorak. They show that if the sets $S$ and $T$ are balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e \< n$, where $e$ is the number of pairs $(s\_i, t\_i)$ that form edges in $\mathcal{Q}\_n$. The paper can be found here: http://www.sciencedirect.com/science/article/pii/S0020019008002238

I can construct an example when $k = 2$, $e=0$ and $n=3$, so this result isn't completely tight, however.
> 5 votes

---
Tags: algorithms, graphs
---