title: Applications of Graph Automorphisms

text:
# Question
Title: Applications of Graph Automorphisms
I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me.

Is there any practical (or impractical for that matter) applications of knowing the automorphism group of a graph?

# Answer
> 11 votes
Automorphism capture a natural notion of symmetry of graphs. As a result, they can be used to speed up algorithms that would otherwise run slowly by chopping down the search space.

For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to keep checking symmetric parts of the tree. We can use graph automorphisms to compute the orbits of variables in the linear programming problem, and then treat parts with the same orbit as identical. A recent application of such techniques to MILP can be read here.

---
Tags: graphs, group-theory
---


# Question
Title: Lambda Calculus Prove Equality Excessive (Haskell-oriented)
I'm on a lambda calculus with parametric polymorphism a la Hindley-Milner Haskell-oriented course and I'm currently facing this exercise which I got stuck on.

Prove that $(\forall m\downarrow, n\downarrow :: N)\space (m+n)-m=n$

Definitions:

$(+)=\backslash m \space n \rightarrow case \space m \space of \space \\{0\rightarrow n, Sx \rightarrow S(x+n)\\}$

$pred = \backslash n \rightarrow case \space n \space of\\{0\rightarrow 0,Sx\rightarrow x\\}$

$(-)= \backslash m \space n \rightarrow case \space n \space of \space \\{0\rightarrow m,Sx\rightarrow pred(m-x)\\}$

Seems super simple but there's a part at which I got stuck. I also can only use the following already proven statements (may not need all):

$1) \space m+0=m$

$2) \space m + Sx = S(m+x)$

$3) \space m+n=n+m$

So here's what I did so far: I decided to prove this by using induction over m

$m=0, \space (0+n)-0=n-0=n$ is true (applying the given definitions for the functions)

$m=x, \space (m+n)-m=n$ is true (Hypothesis)

$m=Sx, \space (Sx+n)-Sx=n$ is true (Thesis)

Proof for $m=Sx$:

$(Sx+n)-Sx=S(x+n)-Sx=pred(S(x+n)-x)$ At which point I got stuck. I obviously have to get that $S$ out of $S(x+n)-n$ to have $(x+n)-n$ and apply the Hypothesis but I can't figure out how. Any ideas?

# Answer
You need to strengthen your induction hypothesis by generalizing it over $n$:

$$\forall n, (m' + n) − m' = n, \qquad (\text{IH})$$ where $m = S\ m'$.

After that everything is easy:

$$ \begin{array}( (\mathsf{S}\ m' + n) - \mathsf{S}\ m' &= \qquad \text{(by definition of +)} \\ \mathsf{S}\ (m' + n) - \mathsf{S}\ m' &= \qquad \text{(by 2nd statement)} \\ (m' + \mathsf{S}\ n) - \mathsf{S}\ m' &= \qquad \text{(by definition of -)} \\ \mathsf{pred}( (m' + \mathsf{S}\ n) - m') &= \qquad \text{(by IH)} \\ \mathsf{pred}(\mathsf{S}\ n) &= \qquad \text{(by definition of pred)} \\ n \end{array} $$

If you are concerned about whether we're allowed to do that generalization, then I should say that we are. You started your proof of $$\forall m\ n, (m + n) − m = n,$$ by taking some arbitrary $m$ and $n$ and then proceeding by induction on $m$ with the following proposition: $$(m + n) − m = n.$$

But in the example I showed, we assume $m$ and proceed with $$\forall n, (m + n) − m = n,$$ which immediately gives us the generalized induction hypothesis.
> 3 votes

# Answer
Another way is to continue from where you got stuck, in the inductive step. You have:
$(Sx+n)−Sx=S(x+n)−Sx$

Now you can prove the following lemma by induction on y:

> Lemma: $Sx - Sy = x - y$
>
> * **case 0**: $S(x) - S(0) = pred (S(x) - 0) = pred(S(x)) = x = x - 0$
> * given $Sx - Sy = x - y$, **case $Sy$**
>
> $Sx - S(Sy) = pred (Sx - Sy) = pred (x - y) = x - Sy$

then you continue:

$(Sx+n)−Sx=S(x+n)−Sx =^{(lemma)} (x + n) - x =^{(IH)} n $
> 4 votes

---
Tags: proof-techniques, lambda-calculus, functional-programming
---


# Question
Title: Understanding why ALL_nfa is in co-nspace
I'm trying to understand Sipser's example showing that $ALL\_{nfa} \in Co-NSPACE(n)$, where $$ALL\_{nfa} = \\{ \<A\> | A \text{ is an NFA such that } L(A) = \Sigma^\*\\}.$$

The algorithm can be seen here.

I'm confused by a few things, but mainly what is meant by "nondeterministically select an input symbol"? If I "nondeterministically" choose symbol 'a' and then mark all the vertices I can reach from the current ones by 'a', then don't I possibly miss out on the vertices reachable by 'b'? And even though we repeat this $2^q$ times, what's to stop me from choosing that 'a' transition each time?

If my instincts are correct, then what we are trying to do is convert the nfa to a dfa (which will have at most $2^q$ states). If the dfa has a single reject state, then we know the nfa has a string that will be rejected. However, we would like to do this without actually converting to a dfa, which might require too much space. So the provided algorithm tries to traverse the corresponding dfa graph, without actually building it?

# Answer
To show that $ALL\_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL\_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.

The complement is

$$\overline{ALL\_{\mathsf{NFA}}} = \\{ \langle N \rangle \mid N \text{ is an NFA where } L(N) \neq \Sigma^\* \\}$$

To show that $\overline{ALL\_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$ we therefore need to devise a Turing machine that, given an NFA description $\langle N \rangle$ can tell us if there exists an input that $N$ will not accept.

Essentially, the machine will nondeterministically guess a string $w$ and verify that this string is not accepted by $N$. Our machine may guess the wrong string, but remember that the machine is *nondeterministic* -- as long as *it is possible to* guess a string with this property, the machine will accept $\langle N \rangle$.

To guess such a string $w$ and check that the NFA does *not* accept it, we need to explore *all* the possible computations of $N$ on $w$ and show that none of them will lead to an accepting state. This does *not* require us to construct an equivalent DFA using the subset construction; doing this would require more than linear space. However, even just storing all of the computations of $N$ on $w$ on the Turing machine tape will require more than $n$ tape cells.

The trick is to guess the string symbol by symbol and keep track of the sets of states that $N$ could possibly be in after it has read a symbol. If $N$ has $q$ states, there are $2^q$ such sets of possible states. We start with the set $\\{ q\_0 \\}$ and guess a sequence of $2^q$ symbols. For each symbol that we guess, we record the subset of states that can be visited from any of the states that $N$ could be in now. We can keep track of this subset of possible current states using $q$ bits (represented as $q$ cells on the tape). This is linear in $n$ where $n$ is the length of $\langle N \rangle$. This description must at the very least list the states of $N$, so $q = O(n)$.

If the set of possible current states that we are now in does not contain an accept state, then we have found a string that cannot be accepted by $N$. We may have to guess $2^q$ symbols, since each symbol could in principle lead us to a new set of possible current states that had not been seen before. But once all sets of possible current states have been examined, we can stop. We can count to $2^q$ in binary using no more than $q$ bits. Again this requires no more than $O(n)$ bits.
> 6 votes

---
Tags: complexity-theory, space-complexity, nondeterminism
---


# Question
Title: sum of squared distances from mean equals all-pairs sum of square distances?
In this variance based k-clustering paper they claim that for a cluster with S points:

$$|S|\sum\_{i \in S}{\\|x\_i-\bar{x}\\|^2} = \sum\_{a,b \in S,\ a\<b}{\\|x\_a-x\_b\\|^2}\\,.$$

Why is that? can you please show me the derivation?

# Answer
> 2 votes
This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change.

Let us denote $|S|$ by $n$. The left hand side becomes $n \sum\_{i \in S} ||x\_i||^2$. The right hand side can be simplified as follows:

$$ \sum\_{a \< b} ||x\_a - x\_b||^2 = \frac{1}{2} \sum\_{a, b} ||x\_a - x\_b||^2 = \frac{1}{2} \sum\_{a, b} ||x\_a||^2 + ||x\_b||^2 - 2 x\_a \cdot x\_b $$

The first equality follows from the fact that $||x\_a - x\_b||^2 = ||x\_b - x\_a||^2$. The second is simple expansion of quadratic expression of vectors.

If you split the sum and notice that the first two terms are equal to $n \sum\_{i} ||x\_i||^2$. You get that $\sum\_{a, b} x\_a \cdot x\_b = 0$. This is easy to see since:

$$ \sum\_{a, b} x\_a \cdot x\_b = \sum\_{a} x\_a \cdot \sum\_b{} x\_b = (\sum\_{i} x\_i)^2 = (n \bar{x})^2 $$

which is zero since the mean vector is zero.

Of course this calculation is all well known as an identity on variance. If you have a random variable $x$ such that $Pr\[x = x\_i\] = 1/n$. Then, your left hand side is $n^2 Var(x)$ and the right hand side is the right hand side of the last equation stated here.

---
Tags: clustering
---


# Question
Title: Question about labeling in Dijkstra's Proof of Correctness
I am trying to understand the proof of correctness for Dijkstra's algorithm (shown below) and also at the following link: CS Auskland

> Proof by contradiction
>
> Suppose that $u$ is the first vertex added to $S$ for which $d\[u\] \ne \delta(s,u)$. We note:
>
> $u$ cannot be $s$, because $d\[s\] = 0$.
>
> There must be a path from $s$ to $u$. If there were not, $d\[u\]$ would be infinity.
>
> Since there is a path, there must be a shortest path.
>
> When $x$ was inserted into $S$, $d\[x\] = \delta(s,x)$ (since we hypothesise that u was the first vertex for which this was not true).
>
> Edge $(x,y)$ was relaxed at that time, so that $$d\[y\] = \delta(s,y) \le \delta(s,u) \le d\[u\]$$
>
> Now both $y$ and $u$ were in $V-S$ when u was chosen, so $d\[u\] \le d\[y\]$.

How can we say that $d\[u\] \le d\[y\]$? And why aren't we saying that $d\[u\] \ge d\[y\]$? Wouldn't the label on $u$ be larger if it is further down the path from $y$?

> Thus the two inequalities must be equalities, $$d\[y\] = \delta(s,y) = \delta(s,u) = d\[u\]$$
>
> So $d\[u\] = \delta(s,u)$ contradicting our hypothesis.
>
> Thus when each $u$ was inserted, $d\[u\] = \delta(s,u)$.

# Answer
> 2 votes
Since the algorithm at each step adds to $S$ the vertex with the lowest "d" value, and $y$ is not in $S$, $d\[u\] \leq d\[y\]$.

---
Tags: algorithms, graphs
---


# Question
Title: Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe?
In the set cover (SC) problem we are given a universe $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe. The set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe.

If I add the constraint that $m=n$ to SC, is this new problem still NP-hard?

My attempt is as follows:

To construct an instance of the new problem we do:

1. If $n=m$, then we are done.
2. If $n\>m$, then we simply add $n-m$ dummy sets to the collection $S$ and we are done.
3. If $n\<m$, then ... (I am stuck). But I think since the union of the $m$ sets is $U$ then we must have that $S$ contains redundant sets. Is this OK?

# Answer
Yes, it is still NP-complete. If you have an instance with $n \< m$, then you can pad $U$ with $m - n + 1$ new elements and add new subset containing only the new elements. The original instance has a solution of size $s$ if and only the padded instance has a solution of size $s + 1$. The reduction is obviously polynomial time.
> 6 votes

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


# Question
Title: finding a & b in an array that a+b = x, for a given integer x
I want to get an algorithm with $\theta(nlogn)$ time complexity that search for two elements in an array of integers, which their sum is equal to $x$ such that x is an integer and $n$ is array size.

# Answer
**Hint**. Sort the array. That can be done in $\Theta(n\log n)$ time. Then, for each element, $a$, in the array find out if $x-a$ is in the array. Can you do those searches quickly? If you can do each search in time $\Theta(\log n)$, for instance, then that will add on no more than $\Theta(n\log n)$ to your running time.
> 1 votes

---
Tags: algorithms, data-structures, search-algorithms, algorithm-design
---


title: Skip List randomization complexity

text:
# Question
Title: Skip List randomization complexity
I understand the basics of Skip Lists and their implementation also the basic `Search` `Insert` `Delete` functions and their run time complexity. Recently after a lecture, a professor proposed an interesting question. He asked what we suspected the total time building a skip list using randomization.

A few hints were given:

* $n \times (1/2 + 1/4 + \dots + 1/2^{k})$.
* I understand this as, For every level of the skip list their is said to be half the nodes working from bottom level to the next one above it.
* Using a geometric equation we came up with this formula: $n \times \frac{1/2^{k+1} - 1/2}{1/2 - 1}$

So ultimately what is the time complexity? $\Theta(n^2)$?

# Answer
According to the hint, the number of elements in the levels beyond the first is expected to be $$ n \cdot (1/2 + 1/4 + \cdots + 1/2^k). $$ Presumably, $k \approx \log n$, though as we will see, this doesn't really matter.

Let's plug in some numbers to see how this behaves. When $n = 100$ and $k = 10$, we get $$ 100 \cdot (1/2 + 1/4 + \cdots + 1/2^{10}) \approx 99.9. $$ When $n = 1000$ and $k = 15$, we get $$ 1000 \cdot (1/2 + 1/4 + \cdots + 1/2^{15}) \approx 999.97. $$ When $n = 10000$ and $k = 20$, we get $$ 10000 \cdot (1/2 + 1/4 + \cdots + 1/2^{20}) \approx 9999.99. $$ What is happening here? Massaging the formula for the sum of the geometric series, we get $$ n (1/2 + 1/4 + \cdots + 1/2^k) = n (1 - 1/2^k). $$ So as $k$ gets larger, the value of this formula gets closer and closer to $n$. Moreover, if $k \geq 1$ (say), then $$ \frac{n}{2} \leq n (1/2 + 1/4 + \cdots + 1/2^k) \leq n. $$ So from the point of view of asymptotic analysis, this expression is $\Theta(n)$ rather than $\Theta(n^2)$.
> 10 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, lists
---


title: Computability of Stack Cleanliness

text:
# Question
Title: Computability of Stack Cleanliness
Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language.

A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness".

The basic idea for stack cleanliness is that only certain values on the stack will be edited and all other values will remain unchanged

More formally:

Given an input arity (a tuple of positions on the active and inactive stack before the program runs), and an output arity (another tuple of the same sort after the program runs) and a function that maps between the two, a program is is considered stack clean iff it performs the function, ends on the stack it started, and the values on the stack that are not in the input remain the same regardless of the conditions of the stack.

The question is: Given a program that is known to halt for all input, a function and the two required arity tuples, is stack cleanliness computable?

# Answer
I don't know the language in detail, but my guess is: no, stack cleanliness is not computable.

For every natural $n$, consider a Brain-Flak program $P\_n$ which does the following:

* take a natural $k$ as input;
* without modifying the stack below, simulate Turing Machine number $n$ on empty input, for at most $k$ steps;
* if the machine does not halt within $k$ steps, revert the stack to the original state, and return $0$;
* otherwise, if it does halt, modify the stack below and return $0$.

$P\_n(k)$ is guaranteed to halt for any inputs $n,k$.

$P\_n$ will be stack-clean (on all inputs $k$, by definition) if and only if the TM number $n$ never terminates on empty input.

The latter is known to be undecidable (it's not even semi-decidable).

Hence stack cleanliness over input arity 1, output arity 1, and constant zero function is already undecidable.
> 7 votes

---
Tags: computability, turing-machines, programming-languages
---


# Question
Title: Number of combinations to put n items into 2 bags
I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues.

First of all: don’t worry, I don’t need you to do my homework for me, I just want to clarify an aspect of the question.

So, the original question asked us to program the computer to find all subsets of a list of items to go into a bag. It said that "The number of possible combinations to put n items into one bag is $2^n$."

So far, so good.

However, the extension of the question is to program the computer to output the amount of combinations possible to put n items into 2 bags: an item must be in either bag or neither.

Now we arrive at my question: At this point it is said that there are $3^n$ possible combinations for this, as each item has three possibilities instead of two.

This makes sense, but I actually did the problem with two items and only found seven combinations:

\[\]\[1\], 2 outside

\[1\]\[\], 2 outside

\[\]\[\], 1 and 2 outside

\[\]\[1,2\]

\[2\]\[1\]

\[1,2\]\[\]

\[1\]\[2\]

So, there are 2 items, there should be $3^2=9$ combinations, but there are only 7.

I'm sure I'm missing something....help!

# Answer
You forgot the "1 outside" case.

```
[2][] 1 outside
[][2] 1 outside

```
> 2 votes

---
Tags: combinatorics, sets
---


# Question
Title: Relation between Machine code and Von Neumann architecture
Since machine language executes instructions on ALU, CPU register and memory, is correct say that **machine code abstract the Von Neumann model**?

If exists, semantically, what is the relation between machine code and Von Neumann architecture?

# Answer
Asking whether machine code abstracts the von Neumann model is a category error – it's a statement that doesn't type-check. The von Neumann model is essentially a system architecture: it's a way of designing computers. Machine code is a sequence of instructions: a way of telling a computer what to do. Those are two completely different things.

Machine code arguably doesn't abstract anything. It's the most concrete, specific thing there is: it runs on only one specific kind of CPU (or perhaps a family of very closely related ones).
> 2 votes

---
Tags: computer-architecture, computation-models
---


title: Is $L / R$ context free?

text:
# Question
Title: Is $L / R$ context free?
I was reviewing the post If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I completely understand why $L/R$ is context free.

I just tried a different approach, which is not that rigorous according to the answers given. It is just based on the basic understanding.

**How I tried :**

Let $L = a^N b^N a^M b^M$ and $R = \left (a + b \right )^\*$.

Then $wx$ belongs to $L$. Suppose I assume $wx = aaabbbab$.

So, now $x = ab$ which belongs to $R$.

So $L/R$ contains $aaabbb$.

Like this, I will get all strings in $L/R = \left \\{ a^N b^N | N \geq 1 \right \\}$.

This language is nothing but context free.

This approach is not as rigorous as what I saw in the answers.

**I just want to confirm: is this approach right?**

# Answer
> 6 votes
You can't prove a general theorem by proving one special case. So even if your proof of the special case were correct (and it isn't), all it does is prove that the theorem holds in that specific case.

Your proof is erroneous since $L/R$ is larger than what you indicate. In fact, whenever $\epsilon \in R$, we always have $L/R \supseteq L$. In your case $$ L/R = \\{ a^{n\_1} b^{n\_2} : n\_2 \leq n\_1 \\} \cup \\{ a^n b^n a^{m\_1} b^{m\_2} : m\_2 \leq m\_1 \\}. $$

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


# Question
Title: Rearrange pixels to maximize visually distinguishable pattern
I have a dataset full of 0s and 1s, and when I visualize it with t-SNE, which does dimensionality reduction. There is clearly some structure in it as shown below. Each color corresponds to a particular category. There are 10 categories, and there are roughly 180 data points for each category. Each data point is a 64-dimension vector, i.e. there are 64 features. The category information is NOT used by t-SNE, and the coloring is applied after t-SNE run is done.

Since the dataset is all 0s and 1s, and each data point is a 64 vector, so I thought I could plot them as 8x8 dimension binary images as shown below. I have plotted 3 examples for each category

If you compare among images in a single column, there appear to be some similarity sort of. If you compare among images in a single row, they look random to me. My question is that is there such an algorithm for rearranging the pixels, which is equivalent to reordering the elements in the original 64-dimension vector, so that MAXimize the visual similarity among images in each column (i.e. make them look as similar as possible) while MINimizing the visual similarity among images in each row (i.e. make them look as different as possible)? The whole point to make it easy to spot visual patterns for different categories if possible.

**Update**:

Thank you for @aelguindy's answer. For the record, I posted what the images look like before scrambling.

This notebook shows how the scrambled version is generated. This dataset is only for experiment. I have another real dataset of 0s and 1s that have nothing to do with hand-written images, of which I was trying to find visual patterns if possible.

# Answer
**This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".**

If I understand your question correctly. You have a few separate problems:

### Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $\[0, 1\]$. I imagine that you want it to ideally satisfy the following:

* $S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
* $S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
* $S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.

Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

### Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

### Quickly computing a permutation on $\[1 \dots 64\]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

`// Obj(p) is the criterion to be maximized.
opt = null
for t trials:
 p = random permutation
 for s steps:
 p' = copy p
 randomly swap two (or three) elements of p'
 if Obj(p') > Obj(p): p = p'
 if Obj(p) > Obj(opt): opt = p`

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.
> 4 votes

---
Tags: machine-learning, image-processing
---


# Question
Title: Show that $x^3 = O(x^4)$ and $x^4 \neq O(x^3)$
Show that $x^{3}$ = $O(x^{4})$ but that $x^{4}$ $\neq$ $O(x^{3})$.

# Answer
> 2 votes
We say that a function $f$ is $O(g)$ if there exist constants $M$ and $C \> 0$ such that $$ x \> M \Longrightarrow f(x) \leq C g(x). $$

It shouldn't be too difficult to show that $x^3$ is $O(x^4)$ using the definition.

---

To show that $f$ is not $O(g)$ you need to show that for every $M$ and $C \> 0$ there exists $x \> M$ such that $f(x) \> C g(x)$. While using this to refute "$x^4$ is $O(x^3)$" is a bit awkward, I think that it's a good exercise which is not too difficult.

Later on you might learn other ways of showing that $f$ is not $O(g)$. Very briefly, the idea of the other methods is a two-pronged attack:

1. If $f$ is $O(g)$ then X.
2. X is false.
3. Therefore $f$ is not $O(g)$.

I'll let your professor give you examples of X.

# Answer
> 2 votes
$x^{3}$ $\leq$ $x^{4}$ when x $\>$ 0.

Let an integer k = 0 and a constant C=1 to show that $x^{3}$ is O($x^{4}$).

Let $x^{4}$ be O($x^{3}$).

Then there would exist some integer k and constant C such that $x^{4}$ $\leq$ C$x^{3}$ for all x $\>$ k.

Dividing through by $x^{3}$ gives x $\leq$ C. But C is a constant, while x can be arbitrarily large, so no such C and k exist, therefore $x^{4}$ $\neq$ O($x^{3}$).

---
Tags: asymptotics
---


# Question
Title: Distinction between statements, declarations, and expressions in formal grammar
I am learning basic grammar and parsing concepts and ran into this statement:

> Nonterminal symbols represent syntactic entities: statements, declarations, or expressions.

But the three terms (statements, declarations, expressions) were not really defined. I have plenty of programming experience so I have a fairly intuitive grasp of the terms, but I'm wondering, from a *language grammar* standpoint, what are the generally accepted definitions for each? When I searched online I found several language-specific discussions but nothing that gave a general definition of these terms that can apply across any language.

Are there such definitions out there? Thanks.

# Answer
These are informal terms. For example, in the C language:

1. Statements are things like `x = 3;`.
2. Declarations are things like `int x;`.
3. Expressions are things like `x * y`.

So declarations are a particular type of statements, and expressions appear in statements.

A better formulation of the statement you quoted would be:

> Nonterminal symbols represent syntactic entities such as statements, declarations, or expressions.
> 1 votes

# Answer
Purely from a *language grammar* standpoint: There is no distinction among these terms. The distinction comes from how individual fragments of the grammar are used in the translator based on the grammar. In the absence of translation, it's all just syntax.
> 1 votes

---
Tags: formal-languages, formal-grammars
---


title: Convergence of Markov model

text:
# Question
Title: Convergence of Markov model
I was learning Hidden Markov model, and encountered this theory about convergence of Markov model.

For example, consider a weather model, where on a first-day probability of weather being sunny was 0.9 while that of being rainy - 0.1. The transition distribution probabilities were - probability of sunny on current day given weather was sunny on previous day - i.e P(sun/sun) = 0.9. Similarly other probabilities were - P(sun/rain) = 0.3, P(rain/rain) = 0.7, and P(rain/sun) = 0.1.

Using bayes inference, we can find probability of distribution of weather on day Xt. It was mentioned that, after some point (i.e at state t = infinite), the probability distribution of weather on a day converges to p(sun) = 0.75 and p(rain) = 0.25.

Can someone explain this convergence mathematically? How does it converge to this distribution? It doesn't matter what's the distribution on day 1, the model always converges to the same values.

# Answer
> 1 votes
This isn't a hidden Markov model; this is an ordinary Markov model. Take a look at Wikipedia's article on Markov chains and specifically the notion of a steady-state distribution (or stationary distribution), or read about the subject in your favorite textbook -- there are many that cover Markov chains.

---
Tags: machine-learning, artificial-intelligence, markov-chains, hidden-markov-models, bayesian-statistics
---


# Question
Title: Programming Symbols : Instance/Instantiation
Is there a generally accepted symbol for indicating instantiation. That is indicating an object is an instance of a class.

My first guess is to use a left arrow with a double or triple line but this seems more like a functional programming symbol, based upon what I've seen of Haskell.

Wikipedia has no examples and a quick google for psuedocode mostly turns up simple functional or procedural algorithms. Object Orientated examples don't seem to feature or do not use any specific symbol.

# Answer
In most contexts, objects are values and classes are types, so I would simply use the colon, representing the "has type" relation:

$Object : Class$

That said, this depends on your context, and whether $:$ carries some other meaning. You could also use $\in$, since you can identify a class with the set of objects that are instances of that class.
> 3 votes

---
Tags: programming-languages, semantics, notation
---


title: Role of network layer in Routers

text:
# Question
Title: Role of network layer in Routers
I just started reading communication networks.
Now, routers contain the network layer, data link control layer and physical layer.
That being true I am confused as to why the network layer is required or to be more specific what is its function.
In "Computer Networks A top-down approach", it is written that the network layer inspects the datagram header to look at the source and host addresses and then passes the datagram to the data link layer of the next link for it to decide where to pass the data packet to.
Network layer does not seem make any changes to the headers associated with the data packet or modify the headers in any way. This begs the question, what does the network layer then do???

# Answer
There are only three high level abstractions in the network stack.

**Link Layer**: Knows how to transfer data (physically\*) across **one** hop. This layer with deals encoding and framing bits, controlling channel access, detecting and recovering from collisions in the transfer medium. Eg: Ethernet, WiFi etc.

**Network Layer**: Does forwarding and routing (note: they are different procedures). Knows how to forward a packet to the destination. Has a table of IP--\>link mapping. Let's assume your router/switch has three links, it decides (and only knows) which link to take to get closer to the "destination IP". Delegates the physical mechanism of transferring bits on that link (which may be Ethernet or WiFi or whatever) to the link layer. Once your router finds that the "destination IP" matches "your IP" it makes an up-call to the End to End layer, i.e, no more links have to be traversed. Eg: Internet Protocol IP. Just to be concrete, a router has a forwarding table which has the following form,

```
Forwarding Table
IP address   Link to take
"Your IP"    E2E layer
127.35.*.*   link 2
10.*.*.*     link 3
173.*.*.*    link 1

```

These individual links may be Ethernet or WiFi or DSL etc. Note: an intermediate gateway/switch may not have E2E layer implemented.

Packets in the network layer may get dropped due to congestion, link failures or may not reach destination due to a wrong route.

The links layer and the network layer taken together is just a "BEST EFFORT" dumb network, that doesn't guarantee: ordered delivery, delay limits, congestion control or any form of reliability that a practical application might require. It tries its best to take the packet through but it is not assured. It does not guarantee end to end delivery.

To answer your question, packet routing is in itself a hard problem which requires implementing an abstraction called the network layer for this purpose. Look for "Path vector routing", "BGP" to understand how network layer prepares these forwarding tables.

**End to End Layer**: This builds on top of the network layer, requests re-sending of lost messages, acknowledgments, arranges out of order segments, manages resources like timer etc. It works to ensure, whatever the sender sent has arrived intact. Eg, TCP, UDP

\*Link layer doesn't always mean physical transmission, for details, read about recursive network stacks like Gnutella
> 2 votes

# Answer
Network layer is required for routing purposes. The network layer at router takes the destination IP address of the packet and compares it with its routing table. **Next hop of the packet** is decided by seeing the routing table.

> The table helps to decide the router whether the packet belongs to its subnet or not. In case the it belongs to the subnet of one its interface, the packet is directly forwarded to the node. Otherwise the *next hop IP Address* is provided, which helps the router to forward the packet.

Suppose a router has four or five interfaces. Whenever a packet arrives from one of it's link, it must be able to forward it to one of its four or five outward links, in order to make sure that the packet eventually reaches destination.
I think you just skimmed over the book. Take another look to the book. The book clearly explains everything. The Network and Transport layer chapters have tonnes of information. Make sure you know most of them.
> 0 votes

---
Tags: computer-networks
---


title: From NFA to DFA

text:
# Question
Title: From NFA to DFA
Let $A = (Q,Σ,\delta,q\_0,F)$ be an NFA such that $L = L(A)$.

We define a DFA $A'=(Q',Σ,\delta,q\_0',F')$ as: $$ Q'=2^Q, \qquad q\_0'=\\{q\_0\\}\\F'=\\{q\in Q \mid q'\cap F \neq\emptyset\\} $$ My question is how we know what elements $Q'$ has? What is the formal definition to obtain these elements? Because it can contain all elements of $2^Q$, and in the DFA obtained from a NFA, the states are not all the elements of $2^Q$.

# Answer
In the DFA you defined, the states of this DFA *are* all the elements of $2^Q$.

There are other DFA's that might have fewer states, but those are different DFAs. For instance, in some variants of this construction, we only include the states that are reachable from $q'\_0$ (we remove all states that can't be reached).

You might want to read, e.g., https://en.wikipedia.org/wiki/Powerset\_construction and standard textbook explanations of the subset construction of a DFA from a NFA.
> 1 votes

# Answer
You have *defined* $Q'$ to be $2^Q$. Therefore, it *is* $2^Q$. It's possible that there are states that cannot be reached by any sequence of transitions from the start state but they're still states because they were defined to be states.
> 1 votes

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


# Question
Title: Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces
Imagine a finite $n\*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can detect a simple cycle in $H$ in linear time. However, such a search cannot efficiently find all simple cycles in $H$ as the number of cycles can grow exponentially (?) with the numer of vertices of $H$.

**Remark**: Since I'm referring to a square grid graph, we have maximum degree 4 for the vertices of $H$. Furthermore, $H$ does not have to be strongly connected. It does not have to have a "reasonable" data structure.

I wonder: What is the time complexity for finding the simple cycle, should it exist, that encloses (surrounds) the most faces? That simple cycle $C(V'',E'')$ is of course itself a subgraph of $H$.

**Edit**: I would like to add that the very same problem but with a directed graph is also of interest! :-)

# Answer
> 1 votes
1. Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time.
2. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component.
3. Pick the component with the largest number of faces and find the cycle bordering that component. This can be done with a single line sweep, which is $O(V' \log V')$.

---
Tags: graphs, time-complexity, square-grid
---


# Question
Title: Number of balanced binary trees (The Art of Computer Programming)
In the section 6.2.3 (Volume 3) Donald Knuth says:

> ... we can ask about the number $B\_{nh}$ of balanced binary trees with $n$ internal nodes and height $h$. It is not difficult to compute the generating function $B\_h(z) = \sum\_{n\ge0} B\_{nh}z^n$ for small $h$, from the relations
>
> $$B\_0(z) = 1,$$ $$B\_1(z) = z,$$ $$B\_{h+1}(z) = zB\_h(z)(B\_h(z) + 2B\_{h-1}(z)).$$

I would understand this formulas if they were like this:

$$B\_0 = 1$$ $$B\_1 = 1$$ $$B\_{h+1} = B\_hB\_h + B\_hB\_{h-1}+B\_{h-1}B\_h = B\_h(B\_h + 2B\_{h-1})$$

Which means that there is only one empty tree ($h=0$), only one tree with a single node ($h = 1$) and number of other trees (of $h+1$, where $h\ge1$) can be calculated as the number of all combinations of shorter trees - having trees shorter by one on as both sub-trees ($B\_hB\_h$), having shorter by one on the left and shorter by two on the right ($B\_hB\_{h-1}$) and the wise versa ($B\_{h-1}B\_h$).

These formulas are actually the same as the ones from the book if $z=1$. This makes me think that it is correct.

Is my reasoning correct? And if it is, can anyone explain what this $z$ actually stands for?

# Answer
> 5 votes
The way I tend to interpret these parameters is to think of them as stand-ins for some type of basic structure in your enumeration problem. This might sound a bit too abstract, so let's look at a (simpler) concrete example.

Let's consider the task of enumerating linked lists. The question I'm interested in is, given a list of unit types (those whose only element is the unit $\circ$), how many lists over unit are there such that their length is $n$? Now, this question was chosen for a very simple purpose: it's easy to see what the answer is. If each element of your list can only be a single element $\circ$, then obviously there's exactly one list of size $n$.

Now, one way to solve this is to look at the inductive definition of a list. $$ \textrm{List}\_{\circ} = \circ :: \textrm{List}\_{\circ} ~\textrm{or}~ \[\] $$

This says that a list over $\circ$ is either a $\circ$ prepended to another list, or it is an empty list. Flattening out the fancy operators into tuple form, and turning the word $\rm or$ into a $+$, we have

$$ \textrm{List}\_{\circ} = (\circ * \textrm{List}\_{\circ}) + \[\] $$

Since an empty list \[\] can be thought of as a tuple with zero $\circ$s inside, let's rewrite it as $\circ^0 = 1$. This then gives an equation

$$ L = \circ * L + 1 $$

Suppose that we're working over the complex field, then this is equivalent to (assuming that $\circ \ne 1$) $$ L = \frac{1}{1 - \circ} = \circ^0 + \circ^1 + \circ^2 + \circ^3 + \dots $$

Now, notice that the formal power series of $L$ with respect to $\circ$ exactly specifies all of the possible lists over the unit $\circ$. That's kind of cool, but is it just a coincidence?

To find out, we turn our attention to a related problem, that of counting lists over the booleans $(\bot, \top)$. Once again, we start with the inductive definition

$$ \textrm{List}\_{2} = (\bot ~\textrm{or}~ \top) :: \textrm{List}\_{2} ~\textrm{or}~ \[\] $$

Doing the same transformation as before, we find that

$$ L\_2(\bot, \top) = \frac{1}{1 - (\bot + \top)} = 1 + \bot + \top + \bot^2 + \bot\top + \top\bot + \top^2 + \bot^3 + \bot^2\top + \dots $$

Interesting, it seems like for certain enumeration problems, the inductive definition we use to specify/construct a type can be translated into this functional over the complex numbers. What's more, this functional's formal power series seems to generate a series of constructions that are isomorphic to the objects from your inductive specification. This is more or less the idea behind these generating functions: their series representation "generates" the combinatorial structures that you are studying.

Now, let's come back to the counting problem. So what if we know that $\frac{1}{1 - \top - \bot}$ represents our combinatorial class? How does this help us with the enumeration problem? Well, the counting problem asks for the number of lists that contains a certain number. This tells us that even if $\top$ and $\bot$ are distinct, they still each contribute the same number of elements (namely, 1) to the list. We can specify this "blindness" with the equality $z = \bot = \top$, so that

$$ L\_2(z) = L\_2(z, z) = \frac{1}{1 - 2z} = 1 + z + z + z^2 + z^2 + z^2 + z^2 + z^3 + z^3 + \dots $$

simplifying, this series yields

$$ L\_2(z) = 1 + 2z + 4z^2 + 8z^3 + \dots + 2^k z^k + \dots $$

Since each of the lists under $z^3$ are lists of length 3, this series then tells us that there are $2^3$ distinct boolean lists of length 3.

Herein lies the power of these generating functions. By "erasing" properties that you don't care about (like the distinctness of true and false in a counting problem), you end up with this formal series whose coefficient gives the total count of a subclass of interest. Therefore, the question du jour of these "analytic" enumeration problems is not how one interprets giving $z$ a specific value, but rather how one can show that the function is analytic/differentiable around the origin and what its coefficients are.

This glosses over a lot of the details, but the intuition should hopefully remain. For your particular problem, we can follow the same recipe to eventually derive Knuth's tower of balanced tree construction.

Now, a height-balanced tree is a binary tree such that the height of each child of a tree is always within one unit of any other child of a tree. This gives a simple case-analysis to consider.

A balanced tree of height $h$ is a root node together with children such that they are:

* Balanced, so that the height of both children are the same, aka $h - 1$.
* Unbalanced but left-skewed, so that the height of the left children is larger, aka $h - 1$ and $h - 2$.
* Unbalanced but right-skewed, so that the height of the right children is larger, aka $h - 2$ and $h - 1$.

This then yields an inductive specification

$$ BBT\_h = (BBT\_{h-1}, \circ, BBT\_{h-1}) ~\textrm{or}~ (BBT\_{h-2}, \circ, BBT\_{h-1}) ~\textrm{or}~ (BBT\_{h-1}, \circ, BBT\_{h-2}) $$

Where the tuple $(L, \circ, R)$ denotes the balanced tree rooted at $\circ$ with the left branching to $L$ and the right branching to $R$. Transferring to the complex field, this gives $$ B\_h = \circ B\_{h-1}^2 + \circ B\_{h\_2} B\_{h-1} + \circ B\_{h-1} B\_{h-2} $$ taking advantage of the newly found freedom of commutativity, and reassociating, we have $$ B\_h(\circ) = \circ B\_{h-1}(B\_{h-1} + 2 B\_{h-2}) $$ Since this is a two-step recurrence, we need to specify their initial conditions. $B\_0$ is the class of balanced trees with zero nodes, so we have $B\_0(\circ) = \circ^0 = 1$. $B\_1$ is the class of balanced trees with one node, so we have $B\_1(\circ) = \circ^1$. Finally, substituting $z = \circ$ gives Knuth's generating functions.

Of course, we've skipped over one bit: we haven't shown that there's some neighborhood around the origin such that $B\_k(z)$'s formal series actually converges. Fortunately for us, these forms of inductive constructions are all generally admissible, so we need not worry about them here.

Finally, the last step is to characterize the coefficient of $z^k$. To be fair, the full problem is to find the coefficients of $\sum\_h B\_h(z)$, but it suffices to just find the coefficient for some $B\_h(z)$, since we can then sum over the rest independently. There's two general strategies we can pursue:

1. Find an explicit characterization of $B\_h(z)$.
2. Use the implicit recurrence directly and see if we can find the coefficients directly.

Here, I imagine that Knuth's approach is probably the second approach. In particular, given two functions $A(z) = a\_0 + a\_1 z + a\_2 z^2 + \dots$ and $B(z) = b\_0 + \dots$, we have $$ A(z) * B(z) = \sum\_n \sum\_{k \le n} a\_k b\_{n-k} z^n $$ and in particular $$ zA(z) = a\_0z + a\_1z^2 + \dots $$

Letting $\[z^n\]f(z) = f\_n$ be the coefficient of $z^n$ in $f(z)$, then we have \begin{align\*} \[z^{n+1}\]B\_h(z) &= \[z^n\](B\_{h-1}(z)^2 + 2B\_{h\_1}(z)B\_{h-2}(z)) \\ &= \sum\_{k \le n} (\[z^k\]B\_{h-1}(z) + \[z^k\]B\_{h-2}(z)) \times \[z^{n-k}\]B\_{h-1}(z) \end{align\*}

This then gives a rather mundane dynamic programming algorithm to compute these coefficients. You can also probably appeal to some analytic techniques to solve for asymptotic properties, but that's for another time.

# Answer
> 3 votes
The variable $z$ is known as a *formal variable*. It doesn't really stand for anything. However, if you want, you can consider it as standing for "vertex", as in the theory of combinatorial species.

In the special case of combinatorial species mentioned here, we are interested in counting a certain type of trees by their vertices. Denote by $\langle \mathcal{L} \rangle$ the "object" corresponding to the class $\mathcal{L}$ of trees. We will have two "rules":

1. Addition rule: If a class $\mathcal{L}$ of trees can be partitioned into classes $\mathcal{L}\_1,\ldots,\mathcal{L}\_m$ then $$ \langle \mathcal{L} \rangle = \sum\_{i=1}^m \langle \mathcal{L}\_i \rangle. $$
2. Multiplication rule: Let $\mathcal{L}\_1,\ldots,\mathcal{L}\_m$ be classes of trees. The class $\mathcal{L} = \times\_{i=1}^m \mathcal{L}\_i$ of tuples $(T\_1,\ldots,T\_m )$ of trees, where $T\_i \in \mathcal{L}\_i$, satisfies $$ \langle \mathcal{L} \rangle = \prod\_{i=1}^m \langle \mathcal{L}\_i \rangle. $$

If we denote by $z$ the tree with one vertex, then $z^n$ represents a tree with $n$ vertices, and $Cz^n$ represents $C$ trees with $n$ vertices. This amounts to giving an interpretation of $\langle \mathcal{L} \rangle$ which respects the rules above: $\langle \mathcal{L} \rangle = \sum\_i c\_n z^n$, where $c\_n$ is the number of trees having $n$ vertices in $\mathcal{L}$.

We can now interpret Knuth's recurrence. Let $\mathcal{B}\_n$ denote the class of balanced trees on $n$ vertices. Then:

1. There is a single balanced tree of height $0$, so $\langle \mathcal{B}\_0 \rangle = z^0 = 1$.
2. There is a single balanced tree of height $1$, so $\langle \mathcal{B}\_1 \rangle = z^1 = z$.
3. A balanced tree of height $h+1$ consists either of (1) a root and a pair of balanced trees of height $h$ ($\langle \mathcal{B}\_1 \rangle \langle \mathcal{B}\_h \rangle^2$, given the product rule), or (2) a root and a pair of balanced trees of heights $h,h-1$ ($\langle \mathcal{B}\_1 \rangle \langle \mathcal{B}\_h \rangle \langle \mathcal{B}\_{h-1} \rangle$), or (3) a root and a pair of balanced trees of heights $h-1,h$ (same as previous case). Invoking the addition rule, we get $$ \langle \mathcal{B}\_h \rangle = z \langle \mathcal{B}\_h \rangle^2 + 2z \langle \mathcal{B}\_h \rangle \langle \mathcal{B}\_{h-1} \rangle. $$

These formulas are useful, since you can compute Knuth's $B\_h$ using polynomial multiplication (which is equivalent to dynamic programming), and then extract the number of balanced binary trees of height $h$ as the coefficient of $z^h$.

---
Tags: algorithm-analysis
---


title: What are sequences?

text:
# Question
Title: What are sequences?
What are sequences? How do we denote the numbers inside them?

I know that in terms of computer science, a sequence of items is an array.

# Answer
A sequence is a function from a subset of the set of integers to a set S. We use the notation $a\_n$ to denote the image of the integer n.

Let Z be the set of integers.

A = \[1, ..., n\] where n is an integer.

f: A $\rightarrow$ S

i $\rightarrow$ $a\_i$

1 $\rightarrow$ $a\_1$

A geometric sequence, also called a geometric progression, is a sequence of the form:

a, ar, a$r^{2}$, … , $a^{n}$

where the initial term a and the common factor r are real numbers.

The arithmetic sequence, also called on arithmetic progression, is a sequence of the form:

a, a+r, … a+mr

where the initial term a and the common difference r are real numbers.
> 2 votes

---
Tags: discrete-mathematics
---


# Question
Title: How to calculate the efficiency of an algorithm?
So I was given this algorithm to compute the efficieny in which I found sorts an array into ascending order.

```
solvethis(T[1..n])
    for i = 1 to n-1 do   //n
       minJ = i           //n-1
       minX = T[i]        //n-1
       for j = i+1 to n do  //sum_{i=1}^{n} t
          if T[j] < minX then ** //sum_{i=1}^{n} t-1
             minJ = j             //sum_{i=1}^{n} t-1
             minX = T[j]         ////sum_{i=1}^{n} t-1
      T[minJ] = T[i]      //n-1
      T[i] = minX         //n-1

```

I also listed the number of times the line of code is run. I need to find the efficiency and how many time the line at \** is calculated. Any help is appreciated thank you.

# Answer
> 0 votes
The best way (The way I was taught at least) is to look for a basic operation. That's the operation that most significantly impacts the performance of an algorithm. In your case it looks like `if T[j] < minX then` would be your basic operation as it's performed the most times, where the statements inside of the `if` check are only performed if the condition is true. The fact you have two for loops going from `1` to `n-1` tell me that you're working with quadratic time. You're going to be doing your basic operation at minimum n^2 or n operations n times. This should tell you that your algorithm performs in O(n^2) timing.

---
Tags: algorithms
---


title: Comparing 2 video files

text:
# Question
Title: Comparing 2 video files
I have a bunch of `wmv` files (~300), named the following way: `video1.wmv -> videox.wmv`. Some of these video files, are exact duplicates of one another (same format, same bitrate, same length, basically, they were copied and renamed, so the only thing that differs from them is their name). Is there any way to find out if two video files from this group are identical or not, so I would be able to filter out the duplicate ones?

Comparing their size is unfortunately out of the question, because I manually went through some of them, and because each of them is around the same length(even the non duplicate ones), some have identical sizes, but they are not identical per se.

If there is a possibility, I would prefer a method which could be implemented as a PHP script, but any other method of comparing them would be welcome.

Thanks!

# Answer
A general algorithm is to compute the SHA256 hash of each file, then sort the hashes and look for duplicates. After sorting any duplicates that may exist will be consecutive. For all practical purposes, you can assume that two files will be identical if and only if their SHA256 hash is the same.

If you're asking how to do this from the command line or looking for a product recommendation, take a look at this:
> 2 votes

---
Tags: comparison, video
---


title: Dynamic Programming Help

text:
# Question
Title: Dynamic Programming Help
Sometimes I can see the recurrence relationship and other times I cannot. This is one of those times. I've gone through a few iterations of trying to solve it but I also find a set of values where my idea fails. If I go exponenetial I can figure it out... but that's a specific no-no.

I'm good with nudges in the right direction. Please make it a little strong though.

**Problem**

Suppose it’s nearing the end of the semester and you’re taking n courses, each with a final project that still has to be done. Each project will be graded on the following scale: It will be assigned an integer number on a scale of 1 to g \> 1, higher numbers being better grades. Your goal, of course, is to maximize your average grade on the n projects. You have a total of H \> n hours in which to work on the n projects cumulatively, and you want to decide how to divide up this time. For simplicity, assume H is a positive integer, and you’ll spend an integer number of hours on each project. To figure out how best to divide up your time, you’ve come up with a set of functions{fi :i=1,2,...,n}(rough estimates, of course) for each of your n courses; if you spend h≤H hours on the project for course i, you’ll get a grade of f\_i(h). (You may assume that the functions f\_i are nondecreasing: if h' \< h, then f\_i(h')≤f\_i(h).) So the problem is: Given these functions{f\_i}, decide how many hours to spend on each project (in integer values only) so that your average grade, as computed according to the fi, is as large as possible. In order to be efficient, the running time of your algorithm should be polynomial in n, g, and H; none of these quantities should appear as an exponent in your running time.

# Answer
> 3 votes
When you encounter these types of problems, the typical thing to do is to find some "decision scheme" that can decompose your big problem into a series of smaller problems. The gist of this problem is finding a set $(h\_1, \dots, h\_n)$ that maximizes your mean grade $\frac{\sum\_{i \le n} f\_i(h\_i)}{n}$ subjected to the constraint that $\sum\limits\_{i \le n} h\_i \le H$. Notice that maximizing $\frac{\sum\_{i \le n} f\_i(h\_i)}{n}$ is equivalent to just maximizing $\sum\limits\_{i \le n} f\_i(h\_i)$ since the denominator $n$ is independent of the choices of $(h\_1, \dots, h\_n)$ that we make.

Now, there are various dynamic programming schemes that we can choose to solve this problem, each of which depends on some special interpretation of an "optimal functional" that we define. For me, the intuitive one is based on the idea of variable elimination, in which we eliminate one of the variables $h\_i$ at each turn.

Here, let $\textrm{Best}(k, h)$ denote the maximum cumulative grade you can gain for the classes $C\_k, C\_{k+1}, \dots, C\_n$ so that you spend no more than $h$ hours on all of their final projects. Given this interpretation, it is clear that our problem is to find $\textrm{Best}(n, H)$.

Now comes the fun/interesting part. First, we need to convince ourselves that this functional displays what we would call an "optimal substructure." In layman's words, this claims that if we know the best distribution of no more than 5 hours to Networking and Programming Languages' final projects, then we also know the best distribution of 8 hours to the Networking, PL, and OS' final projects **if** we *decide* to allocate 3 hours to the OS project. It's simple, we just use the same optimal budget of 5 hours for Networking and Programming languages that we already have.

In other words, this optimal substructure property guides us on the decision we have to make at each turn (because we don't have to worry about the subproblems). Here, $\textrm{Best}(k, h)$, according to the substructural property we've introduced above, must make a decision on what $h\_k$ should be assigned. In addition, it must

1. Ensure that $h\_k$ does not exceed its allocated hours of $h$, and
2. Maximize the grades contingent on the choices that it can make.

Therefore, when we consider the problem of computing $\textrm{Best}(k, h)$, there's a range of valid decisions that we can make, each corresponds with an assignment of a single value to $h\_k$. For example, say I'm considering $\textrm{Best}(\textbf{Networking}, 5)$, which corresponds to the maximum cumulative grade that I can get in classes Networking, PL, and OS with only 5 hours to distribute between them. Now, I have to make a decision about how I will budge for Networking. Say I budget exactly 0 hours to networking, then I can spend 5 hours on PL and OS; alternative, I can budget 1 hour to networking and spend 4 hours between PL and OS, 2 hours to networking and 3 between PL and OS, etc. Each choice of time budget for Networking also determines a subproblem that I have to solve between PL and OS with the remaining time. Once we consider all of these choices (and subproblems), we must then commit to the problem that will give us the best solution.

This thought process should yield a recurrence for **Best** that can be computed in some increasing order of its parameter. This computation then takes the form of a tabulation over an $n \times H$ grid, each time spending approximately $O(k)$ (where $k \le n$ is the column number) time between the $O(k)$ choices, which gives an $O(n^2 H)$ algorithm.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations
Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question.

I have never heard of a language equation. But I am just a student. Given the syntax, is this equating the derivations of a CFG grammar to equations?

In other words, is this bit from the answer $A=ABa$ meant to be considered equivalent to a BNF derivation $A \rightarrow ABa$? (where $A$ and $B$ mean the same as in the original answer -- variables that decompose to terminals containing $a$)

Or is there some other meaning being expressed here? From the second question that I found after I typed this question it seems to mean something different. Can someone "ELIStudent"?

# Answer
> 5 votes
A good way to think about these equations is to imagine them as sets over valid words. Say I have an alphabet $\Sigma = \\{a, b\\}$, then the rule $$ A \leftarrow A a \mid b $$

says that there's some set $A$ that is isomorphic to the set $(A * \\{a\\}) \cup \\{b\\}$. Here the $\*$ operation is the product/concatenation operation lifted over sets, that is $$ \\{a, b, c\\} * \\{d, e, f\\} = \\{ad, ae, af, bd, be, bf, cd, ce, cf\\} $$

Going back to our grammar rule, it is basically *declaring* the existence of a set $A$ of words that satisfies the equation $$ A = (A * \\{a\\}) \cup \\{b\\}. $$

Now, there's a huge class of sets of words that satisfies this equation. For example, the set $A\_\bot = \\{b, ba, baa, baaa, baaaa, \dots\\}$ is a valid solution since a $b$ or appending any element of $A\_\bot$ with another $a$ will result in a word that is already in $A\_\bot$. However, you should check that $$ A\_{bb} = \\{b, bb, ba, bba, baa, bbaa, baaa, bbaaa, \dots\\} $$ is also a valid solution to this equation. In particular, $b$ is already in $A\_{bb}$, and for any element $ba^k$ or $bba^k$ in $A\_{bb}$, its concatenation with $a$ results in $ba^{k+1}$ and $bba^{k+1}$, which are also already in $A\_{bb}$. Therefore, $A\_{bb}$ is also a valid fixed point.

In fact, for any given ground set of words $S = \\{w\_1, w\_2, w\_3, \dots\\}$, we can construct a closure $A\_S$ which contains every word in $S$ and similarly satisfies the above equation. In particular, the closure operator is the same isomorphism:

\begin{align\*} A\_S^{k + 1} &= (A\_S^k * \\{a\\}) \cup \\{b\\} \\ A\_S &= \bigcup\_k^\infty A\_S^k \end{align\*}

So now we get to the real question. If there are an infinite supply of solutions for this equation, then what good is it as a characterization of some grammar? Well, intuitively, we hope to just characterize those words that are generated from this rule "from scratch". In effect, we wish to treat these rules as free objects. That is, we care about the case where the underlying generator $S = \\{\\}$. Let $$ A(S) = (S * \\{a\\}) \cup \\{b\\} $$ then we want $$ A\_\* = \bigcup\_k A^{(k)}(\\{\\}) $$ to be the set generated by our grammar rule, where $A^{(k)} = A(A(\stackrel{k}{\dots} A(\cdot)))$.

This then gives some intuition of what we mean by the "least solution." $A(S)$ is monotone in the sense that $S \subseteq S' \implies A(S) \subseteq A(S')$; in fact, this holds over all grammar rules. Since the least element over the class of possible sets that $S$ can take (ordered on set inclusion) is the empty set, then effectively the "freely generated" language that we desire also turns out to be the smallest (ordered on set inclusion) fixed point, that is, $A(\\{\\}) \subseteq A(S')$ for any set $S'$.

In general, you'll see a lot of these "smallest solution" clauses all around the landscape of computer science. For example, any recursive program is the smallest solution to some program equation; any constructable inductive datatype is the smallest solution to some inductive datatype equation; any valid program semantic is the smallest solution to some logical equation; etc. It turns out that these classes of topological closures corresponds elegantly to a notion of finiteness. For example, the set of all finitary words $\Sigma^\*$ is itself a least fixed-point. Since computations themselves can be seen as some enumeration process of finite objects, the analogy holds quite naturally; least fixed-points typically gives some assurance of some form of computability.

In conclusion, if you see the phrase "least solution" or "the least fix-point," it often means that the problem concerns finite objects that are freely-generated in the sense that only things that can be derived "from scratch" are considered.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete
Let $\mathrm{SpaceTMSat} = \\{\langle M, w, 1^n\rangle\mid\text {DTM $M$ accepts $w$ in space }n\\}$.

How do I prove that this language is PSPACE-complete? NP contains NP-complete problems and so does PSPACE. Am I supposed to prove it the same way as I would prove an NP-complete problem?

# Answer
> 2 votes
For any complexity class $X$, a language is $X$-complete if it's in $X$ and every problem in $X$ can be reduced to it. There are two main ways to prove that a language is $X$-complete: literally show that it meets the definition of $X$-completeness, or show that some other $X$-complete problem reduces to it.

In cases where the language is essentially, "Here's a machine in~$X$ and an input: does it accept?", it's usually best to go for the literal approach and show that every problem in the class can be reduced to your problem. Why? Because every problem in the class is decided by a Turing machine, and your language is about whether those Turing machines accept or not.

---
Tags: complexity-theory
---


# Question
Title: proving " if $k\log(k) = \theta (n)$ then $k = \theta (\frac{n}{\log(n)})$"
First i began with the definition of $\theta$ as below: $c\_1n \leq k \log(k) \leq c\_2n \implies c\_1\frac{n}{logk} \leq k \leq c\_2\frac{n}{logk}$ and we also know if $k\log(k) = \theta (n)$ then $k = O(n)$ then $k \leq cn$ thus $c\frac{n}{logn} \leq c\_1\frac{n}{logk}\leq k $ and thus $k = \omega(\frac{n}{\log(n)})$. In in this manner, i have to prove that $ c\_2\frac{n}{logk} \leq c\frac{n}{logn}$ too to show that $k = O(\frac{n}{\log(n)})$ . But it ($ c\_2\frac{n}{logk} \leq c\frac{n}{logn}$) seems false! Is this really false and there is a better solution, or is there any proving tricks for $ c\frac{n}{logn} \leq c\_1\frac{n}{logk}$?

# Answer
> 2 votes
First, let me explain *why* your claim holds. Then we'll see how to prove it.

If $k \log k = \Theta(n)$ then $k$ has the same order of magnitude as $n$, and so we expect $\log k \approx \log n$ (or, more formally, $\log k = \Theta(\log n)$). Diving by $\log n$, we deduce $k = \Theta(n/\log n)$.

This was just intuition, so now let us see a rigorous proof. A rigorous proof rests on a rigorous definition of big $\Theta$, and this is a surprisingly delicate matter. In this case it suffices to assume that $n \geq 1$.

**Upper bound**

Suppose that $k \log k \leq Cn$ for $C\>0$.

If $k \leq \sqrt{n}$ then $$ \frac{k}{\frac{n}{\log n}} \leq \frac{\log n}{\sqrt{n}}. $$ Now $\frac{\log n}{\sqrt{n}}$ is continuous and tends to zero at infinity, so it is upper-bounded by some constant $M$. Therefore in this case $$ k \leq M \frac{n}{\log n}. $$

If $k \> \sqrt{n}$ then $$ Cn \geq k \log k \> k \log \sqrt{n} = \frac{1}{2} k \log n, $$ and so $$ k \leq 2C \frac{n}{\log n}. $$

We conclude that for all $k$, $$ k \leq \max(2C,M) \frac{n}{\log n}. $$

**Lower bound**

Left to you as an exercise.

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


# Question
Title: Is the given language decidable for turing machine?
I am going through undecidability of TM and found this question

$L=\left \\{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \\}$

I think it is decidable as number of strings in the language is prime ,i.e , 2,3,5,7,11,13,17,............. It seems to me like it is accepting all the strings.

If it has accepted 17 strings, then it must have accepted 12 strings, 14 strings, 16 strings and so on. Actually i am not getting from where to start.

**Can anyone provide legal explaination of what is actually happening here ?**

# Answer
Consider a problem 'A' which is undecidable. If 'A' is reducible to another problem 'B', then problem 'B' is undecidable.

Consider following two statements:

```
p: Turing machine halting problem is undecidable.
s: A given Turing Machine 'M' reaches a state 'q' on reading input 'w'.

```

If we can modify statement 'p' in such a way that the answer to 's' will be answer to 'p', then we can say problem 's' ( statement 's' ) is undecidable.

Also note that I will be using a term "Dead Configuration" to mean the Turing machine is in a state from which no further transitions is defined i.e, a Turing machine halts because of a dead configuration.

```
Modified version of 'p': A Turing machine halts only at state 'q'.

```

That is, whenever a Turing machine reaches a dead configuration, we will make a transition to 'q'.
Modified version pf 'p' is undecidable, which means it is undecidable that a Turing machine reaches a state 'q' on reading any input.
Hence, problem 's' is also undecidable.

On the same lines statement 's' can be modified to prove that the problem, "Turing machine will accept a string" is undecidable.

Hence, if the problem: "whether a string is accepted by a Turing machine" is undecidable then the problem of counting the number strings in a language will also be undecidable.
> 2 votes

---
Tags: turing-machines, undecidability, semi-decidability, primes
---


# Question
Title: Recognizing vs Deciding in defining class BPP
In Sipser's text, he writes:

> When a probabilistic Turning machine recognizes a language, it must accept all strings in the language and reject all strings not in the language as usual, except that now we allow the machine a small probability of error.

Why is he using "recognizes" instead of "decides"? If the machine rejects all strings that are not in the language, then it always halts, so aren't we restricted to deciders in this case?

The definition goes on:

> For $0 \< \epsilon \< 1/2$ we say that **$M$ recognizes language $A$ with error probability $\epsilon$** if
>
> 1) $w \in A$ implies $P(M \text{ accepts } w) \ge 1 - \epsilon$, and
>
> 2) $w \notin A$ implies $P(M \text{ rejects } w) \ge 1 - \epsilon$.

So it seems like the case of $M$ looping is simply not allowed for probabilistic Turning machines?

# Answer
> 2 votes
Complexity theory makes no distinction between "deciding" and "recognizing". The two words are used interchangeably. Turing machines considered in complexity theory are usually assumed to always halt. Indeed, usually only time-bounded machines are considered (such as polytime Turing machines), and these halt by definition.

In your particular case, you can interpret *accept* as halting in an accepting state, and *reject* as halting in a rejecting state. The Turing machine is thus allowed not to halt. However, the class BPP also requires the machine to run in polynomial time, that is, to *halt* in polynomial time. In particular, the machine must always halt.

---
Tags: complexity-theory, turing-machines, decision-problem, probabilistic-algorithms
---


# Question
Title: Find expression with minimal distance to target
I will start of with an informal example and give a more formal problem definition later.

Say I have a finite set of positive real values: $\\{2.3, \pi, 4.382, 0.3\\}$. Using normal addition and multiplication, we can construct expressions like $(\pi + 2.3) * 0.3 + 4.382$ and $(0.3 + \pi) * (2.3 + 4.382)$. We put the following constraints on the expressions:

1. Each value in the set must be used exactly once in the expression.
2. We can only use addition, multiplication and brackets in our expression.

The goal now is to get as close to a target value, say $9.5$. For example, the expression $2.3 * \pi * 4.382 * 0.3 = 9.49886...$ gets close. How can we find the expression whose evaluation is closest to $9.5$? Or more formally:

> Given a finite set $V$ of - not necessarily unique - elements, two binary operands $f(x, y)$ and $g(x, y)$ that operate on the elements in $V$ and a target value $t$, find the expression $E$ containing each element of $V$ exactly once, such that the evaluation of $E$ is as close to $t$ as possible. $E$ must consist only of the values in $V$, the given operands and brackets.

I understand that for small sets, an exhaustive check that checks all possible expressions is feasible. Using heuristics, quickly finding an approximate answer (with small distance to the target) is probably possible for larger sets too. My questions are; does a more efficient method exist to find exact answers for large sets? Do efficient methods exist specifically for certain operands? What fields of mathematics and computer science touch on this subject?

# Answer
This is a very difficult problem. For an already hard special case, you can look at the subset sum problem. So in general, one direction to look at is NP-hard optimization problems (and ways of coping with hardness).
> 2 votes

---
Tags: complexity-theory, optimization
---


# Question
Title: Algorithm for converting (coordinates + reach radius) data to directed graph
I am trying to find a solution better than O(n2) for the following problem:

There are N points on a 2-D plane (N $\le$ 106), with integer coordinates between -105 and 105. Each point has an associated integer "reach radius" Ri (0 \< Ri \< 105).

Build a directed graph (represented by adjacency lists) in which these points are the vertices and there is an edge from A to B if and only if point B falls in the reach of point A (i.e. euclidean\_distance(A,B) $\le$ RA).

I am thinking of dividing the plane into 4 equal regions, and solving the same problem for the regions, but don't know how to combine the partial solutions...

Thanks in advance for any ideas!

# Answer
If all pairs of points are within each other's reach, you can not optimize the construction below $O(N^2)$. However, you can optimize for sparser graphs by ordering pairs of points by distance from smallest distance to largest. Once you find a pair $(A, B)$ where $d(A, B) \> R\_{max}$, you are done. A technique you can use for this can be found here. This technique makes use of divide and conquer.

This is more a heuristic. I do not think there is a way (with or without use of divide and conquer) to reduce the worst case complexity.
> 0 votes

---
Tags: algorithms, complexity-theory, divide-and-conquer
---


# Question
Title: maximum matching in a bipartite graph for solving a chess rook maximization problem
There's an `n x n` chessboard where some cells are instead holes. I want to have as many rooks as possible in a way that the rooks won't be able to capture each other. Rooks cannot be placed on the holes but can jump over them. How can I solve this problem using the finding maximum matching principle in a bipartite graph?

# Answer
> 1 votes
This is a well known problem in competitive programming. When you put a rook in a row and a column, you can no longer have any other rooks in that row and in that column. That is, you are matching rows to column, such that each row gets at most one column and each column gets at most one row. Sounds like bipartite matching?

What do the holes represent? Positions where you cannot place rooks. These are row-column pairs that cannot be matched. I will leave it as an exercise for you to figure out what that means in the bipartite graph of rows and columns.

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Applicability of Machine Learning on Images.
I am trying to use machine learning to detect and locate an object in a greyscale image. I have about 700 images which are 360x360 pixels in size. See below for an example of the object and image:

In the first image, the object is indicated by the red arrow. In the second image, the object doesn't exist. Additionally, the object can occur anywhere along the X-axis (labelled theta) with a very slight bias towards the central pixels.

I tried to reduce the number of features by collapsing the image to a 1D array, like so:

```
array = numpy.sum(numpy.absolute(image), axis=0)

```

This ensures that I don't discard information that is crucial to my objectives (detecting and locating).

I now have a 1D array which is whiter at indices where the object is located and no noticeable brightness when the object is absent. So I created a training set of 500(samples) x 360(features) with 200 other samples reserved for cross-validation, and trained an SVM on it. The results on the cross-validation samples reported an accuracy of about 66%, and this doesn't seem to change with the number of training samples.

So I have 4 questions for the community:

1. Does the outlined problem have an acceptable solution in Machine Learning, or does it seem incredibly absurd to apply Machine Learning at all?
2. I can look for more images, or even synthesise new images from existing ones (by arbitrarily shifting the image left or right). Can I, however, expect the results to get any better?
3. With the number of features that I have, what is the number of samples that I must typically have (as a very rough guess, given that you have seen what kind of images I'm dealing with).
4. The digit recognition problem in Machine learning houses an issue which is relevant to my case -- the algorithm performs poorly when the digits are written off-centre. In my case, the pattern that I am looking for in the 1D array (a bump) is independent of the location so that any one particular group of pixels shouldn't have disproportionate weights. What is one way to work around this limitation? (I'm thinking auto-correlation)

Thank you for your time and help!

# Answer
> 3 votes
It looks plausible that this is the kind of problem machine learning will be good at. I suspect you might be able to achieve much higher accuracy, but the only way to know for sure is to try it.

For your current approach, the size of your training set is reasonable, assuming you're using a linear SVM. A linear SVM will have about 360 parameters, and your training set is larger than that, so this is not an unreasonable size of training set.

There are many things you could try, to see if they improve accuracy. Here are two.

**Translation invariance.** The properties of an object don't depend on where it is located. However, the way you're currently training the SVM doesn't take this into account, so you might be missing an opportunity to do a lot better.

One potential solution: first, take all of the positive samples in your training set (the ones that do contain a object) and shift them left or right so the object is in the same position in each (always exactly in the middle). Take each negative sample and shift it a random amount. Then, train the SVM on the modified training set. This builds a SVM model that recognizes images that contain an object at the center. Once you've got a trained SVM model, given a new image I, try all possible ways to shift it and apply the SVM classifier to each; if any of those says "yes", then you've found an object.

A different potential solution that might work better: construct features that are inherently translation-invariant, by definition. For instance, instead of using the 360 elements of the 1D array as a feature, use the average of the array, or the standard deviation. Then train a classifier on those few features.

You can probably design some other, more complex translation-invariant features. For instance, you could try computing the average or standard deviation of the first derivative of the 1D array (the average or standard deviation of $A\[i+1\]-A\[i\]$, over all $i$). Or, rather than doing this on the reduced 1D array, even better, do it on the 2D array: compute some statistics of the first derivative (in the horizontal direction) of the 2D image, and similarly for the first derivative (in the vertical direction). You could also build a histogram of the intensity distribution of the original 2D image (e.g., 10 buckets; the bucket for 0.2-0.3 counts the number of pixels whose intensity is in the range $\[0.2,0.3)$). You could grid the 2D image into 90x90 non-overlapping cells, where each cell is a 4x4 pixel square, compute the average intensity of each cell, and then compute a histogram of those values. For instance, this might capture the fact that when there is an object there will be many cells that are all-white, whereas an image with no object probably will have few or no such cells. Try different ideas along those lines, and you might find some that are effective.

**Convolutional neural networks.** By reducing to a 1D array, you've thrown away a bunch of information. You could try applying a CNN classifier directly to the 2D image. There's been a lot of work on how to do this in the computer vision community over the past 5 years, and CNN's seem to do significantly better than anything else. You could take a look at the Caffe toolset (or Theano or Tensorflow or any of a number of others). This might benefit from having more training images, but you can try it on the set you've already got.

**Regularization.** Don't forget to use regularization and to optimize hyper-parameters (often, using cross-validation and grid search).

---
Tags: machine-learning, image-processing
---


title: Why is the complement of SAT in IP?

text:
# Question
Title: Why is the complement of SAT in IP?
It is mentioned in Sipser's text that the complement of **SAT** is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the case.

Is this supposed to be seen directly? Or is it easier to show that it is in $NPSPACE$, which would prove the claim since $IP = PSPACE = NPSPACE$?

# Answer
> 4 votes
This is of course a consequence of $coNP \subset PH \subset PSPACE = IP$. But it can also be proven directly for UNSAT.

The basic idea is reducing the problem to zero-testing a sum over a polynomial in a suitable finite field. It's a bit too technical to repeat neatly here, but I can give you an informal idea of how it is done.

Let's consider a formula $\phi$, define $p\_\phi$ to be the polynomial where you think of $x\_i$s as variables, replacing $\neg x\_i$ by $(1 - x\_i)$, each $\wedge$ by $\times$ and each $\vee$ by $+$. Notice that the formula is unsatisfiable iff $p\_\phi(x\_1, \dots, x\_n) = 0$ for all $x \in \\{0, 1\\}^n$ or equiavalently if

$$ \sum\_{x\_1 \in \\{0, 1\\}}\sum\_{x\_2 \in \\{0, 1\\}} \dots \sum\_{x\_n \in \\{0, 1\\}} p(x\_1, x\_2, \dots, x\_n) = 0 $$

This follows from the fact that $p\_\phi \geq 0$ for any $0/1$ assignement.

The interaction is essentially the prover trying to convince the verifier that the sum is indeed zero. The interaction is done on the sum above modulo a suitable prime to keep computations manageable for the verifier. The full details are explained here. The main proof that you need to follow and convince yourself of, is that the prover cannot fool the verifier with large probability.

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


# Question
Title: Given a set of string patterns, find which ones match a particular string
I have an array of known patterns with optional wildcards. For example this array that has 5 patterns:

```
ab*e
hkl
abcd*
ab
sdfs?f

```

now I need to find the elements within the array that match an arbitrary string.

This can be solved with regular expression by converting the patterns to regexp and looping over the array and returning those that match my string. The problem is that this approach is too slow when my patterns array has thousands of patterns.

I'm looking for some sort of hashing to the known patterns array (could be slow as it only happens once), so that the search of matched patterns to a gives string becomes significantly faster. I checked the Rabin Karp and Aho–Corasick algorithms but they don't work for patterns with wildcards.

In the example above if I'm looking for all matched patterns for `abcde` I would get

```
ab*d
abcd*

```

or the values `0,2` which are the indexes in the patterns array matching my string.

# Answer
Rather than build 5 NFAs (one for each pattern), I suggest you build a single NFA or DFA that represents the parallel composition of all five patterns. Then you can run the string through this automaton and check what state it ends at. That state will tell you which of the 5 patterns it matches.

For best performance, build a NFA for each pattern, take the parallel composition using the product construction, and then convert to a DFA. This should be quite fast.
> 2 votes

# Answer
I suggest choosing some small $k$ (e.g., $k=3$) and breaking up each wildcard-free substring within each pattern into all overlapping $k$-mers: e.g. the pattern `abcd*ef?ghij` would give you the 3-mers `abc`, `bcd`, `ghi` and `hij`. Any string that matches `abcd*ef?ghij` *must* contain all these 3-mers, so we could pick one of them (say, `ghi`) at preprocessing time; later, when we have a string that we want to test, we know that we only need to do a "full check" for the pattern `abcd*ef?ghij` if the string contains the 3-mer `ghi`. So the idea is to build, at preprocessing time, an index $z\[\]$ that can, for any given $k$-mer $x$, quickly report all the patterns that we need to run a full check on if $x$ is present anywhere in the string. For speed, this $z\[\]$ can take the form of a large in-memory array whose index is the $k$-mer, encoded as an integer: this means that, for an alphabet of size $A$, it will have $A^k$ entries, each containing a list of pattern IDs. For speed reasons (see below) you may want to round the alphabet size up to the next power of 2 (so, e.g., if the alphabet is lowercase letters, you could round up to an alphabet size of 32, and comfortably get $k=5$).

## Preprocessing

* For each pattern $p\_i$:
    + Choose any wildcard-free $k$-mer $x$ in $p$; the "least likely" $k$-mer is the best choice.
    + Add $i$ to the list $z\[x\]$.

## Main algorithm

* For each $k$-mer $x$ in the given string $s$:
    + For each $i$ in $z\[x\]$:
        - Check whether $p\_i$ matches $s$ "the hard way".
* If there are any patterns that have no wildcard-free $k$-mer, test each of them against $s$ "the hard way".

Because each pattern appears at most once anywhere in the index $z\[\]$, this will never test a pattern twice, so the only overhead over the naive algorithm is the cost of breaking the string into $k$-mers. For alphabets with power-of-2 sizes, this can be done in linear time with bit shifts and bitwise OR operations.

Generally, a higher $k$ is better, but requires exponentially more memory -- and also means that patterns have to have longer wildcard-free substrings in order to benefit from the index. You'll need to experiment.
> 2 votes

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


# Question
Title: Calculating positions of nodes relative to a known point
If I know all the distances between a set of nodes and I also know that one of the nodes is at location (0,0), using the distances between the nodes, can I calculate the absolute positions between all of the nodes? I feel that this will involve some form of trilateration but only a single node position is known. Will I need an iterative algorithm to eventually find a unique solution?

# Answer
I wrote an algorithm that determines a configuration if one exists, given a distance matrix. It repeatedly uses circle-circle intersection to triangulate new nodes based on their distance to the first, second and third. As others have mentioned in comments, the first three points have some degree of freedom, which I've made assumptions for, in line with yours.

The code assumes all points are unique and invariant to changes smaller than a certain $\epsilon$.

```
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

const double epsilon = 0.00001;

struct Point {
    double x, y;
};

double dist(Point p, Point q) {
    return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}

vector<Point> intersections(Point p, Point q, double pr, double qr) {
    double d = dist(p, q);
    if(pr + qr < d) return vector<Point>();
    if(min(pr, qr) + d + epsilon < max(pr, qr)) return vector<Point>();
    double a = (pr * pr - qr * qr + d * d) / (2.0 * d),
        h = sqrt(pr * pr - a * a);

    Point m = { p.x + (a * (q.x - p.x)) / d,
        p.y + (a * (q.y - p.y)) / d },
        r = { m.x + (h * (q.y - p.y) / d),
            m.y - (h * (q.x - p.x)) / d },
        s = { m.x - (h * (q.y - p.y) / d),
            m.y + (h * (q.x - p.x)) / d };

    return {r, s};
}

int main() {
    int N;
    cin >> N;

    vector<vector<double> > adj(N, vector<double>(N));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }

    vector<Point> ps(N);

    for(int i = 0; i < N; i++) {
        if(i == 0) ps[i] = {0.0, 0.0};
        else if(i == 1) ps[i] = { adj[0][1], 0.0 };
        else if(i == 2) {
            vector<Point> is = intersections(ps[0], ps[1], adj[0][2], adj[1][2]);
            if(is.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            ps[i] = is[0];
        } else {
            vector<Point> first = intersections(ps[0], ps[1], adj[0][i], adj[1][i]),
                second = intersections(ps[1], ps[2], adj[1][i], adj[2][i]);
            if(first.empty() || second.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            if(min(dist(first[0], second[0]), dist(first[0], second[1])) < epsilon) ps[i] = first[0];
            else if(min(dist(first[1], second[0]), dist(first[1], second[1])) < epsilon) ps[i] = first[1];
            else {
                cout << "Invalid" << endl;
                return 0;
            }
        }
    }

    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) {
        if(abs(dist(ps[i], ps[j]) - adj[i][j]) > epsilon) {
            cout << "Invalid" << endl;
            return 0;
        }
    }

    cout << "Valid" << endl;
    for(const Point &p : ps) {
        cout << p.x << " " << p.y << endl;
    }

    return 0;
}

```

I haven't had time to comment the code. If you want me to, leave a comment. I took your drawing as a sample (which is invalid) and wrote another sample myself:

```
4
0 10 11 10
10 0 8 11
11 8 0 8
10 11 8 0

Invalid

4
0 4 5 3
4 0 3 5
5 3 0 4
3 5 4 0

Valid
0 0
4 0
4 -3
0 -3

```

As you can see, a valid configuration is printed if one exists. The complexity of the construction algorithm is $O(N)$, but we need to check if all matrix entries are valid after construction, which is $O(N^2)$.
> 1 votes

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


# Question
Title: Term for members of a class that are not inherited
Is there an explicit term for a member of a class that is not inherited from any parent class?

```
class Vehicle {
    int weight;
}

class Car extends Vehicle {
    int numDoors;
}

Car car = new Car();
car.weight = 10000; // weight is an "inherited member"
car.numDoor = 4; // what's the term for numDoor?

```

# Answer
> 2 votes
Just a member variable. If you want to specify that it is not inherited, I suppose you could call it 'noninherited member variable'. Wiktionary lists this as a term in computing.

---
Tags: terminology, object-oriented
---


# Question
Title: An imperative program is analogous to how a Turing machine works?
Since Turing machines has great influence on typical hardware architecture (Von Neumann) and both uses concept of state, is correct to say that **an imperative program is analogous to how a Turing machine works**?

> “Computability via Turing machines gave rise to imperative programming. Computability described via λ-calculus gave rise to functional programming.” — Cooper, S. B., Leeuwen, J. (2013) . Alan Turing: His Work and Impact.

And

> "Imperative programming languages such as Fortran, Pascal etcetera as well as all the assembler languages are based on the way a Turing machine is instructed: by a sequence of statements." - Barendregt, H., Barendsen, E. (2000) . Introduction to Lambda Calculus

# Answer
> 4 votes
At a high enough level and when contrasted with functional programming, sure. Turing machine models and imperative programs have in common that they start from an input and take a series of steps that change a state stored in memory, ending with some output.

This contrasts with lambda calculus and functional programming which generally and loosely do not have the above features.

I think reading any more into the comparison than this, or trying to take it any farther, is probably a mistake. As Yuval says, Turing machines are quite different from modern machines and program execution environments.

---
Tags: turing-machines, computer-architecture, imperative-programming
---


# Question
Title: $\{0,1\}^*$ vs $\{0,1\}^+$ vs $(0 \cup 1)^*$
I understand that $(0 U 1)^\*$ is the set of all binary strings. However, what do the other two expressions create?

Could someone please provide examples of what strings these languages would accept?

$L = \\{0,1\\}^\*$

$L = \\{0,1\\}^+$

# Answer
There is some abuse of notation going on. There are regular expressions and there are sets of strings.

$\\{0, 1\\}^\*$ is the set of all binary strings. This is (rarely) used to mean the regular expression matching all binary strings.

$(0 \cup 1)^\*$ is the regular expression matching all binary strings.

$(0 \cup 1)^+$ is the regular expression matching all non-empty binary strings.

$\\{0, 1\\}^+$ is (rarely used) to denote the regular expression that matches all non-empty binary strings (same as $(0 \cup 1)^+$). It might be used in some places to denote the set of all non-empty binary strings, but I never personally saw this usage.
> 2 votes

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


# Question
Title: What is it called when you classify words into categories, but not by part of speech?
I'm looking to classify words into type categories like `sushi` to `food`, `baseball` to `sports`, `happy` to `emotions`, `panda` to `animals` etc.

What is this type of classification called? I see lots of NLP-related articles discussing parts-of-speech classifiers. This isn't helpful.

I know any word has many possible categories. For example, `panda` could be classified as `animal`, `mammal`, `Ailuropoda` (it's genus), or even `algorithms` (as in, "Google Panda"). I'm open to any of the above to start. My preference would be colloquial rather than scientific (`panda` to `animal`).

Ideally it would return probability for different categories. For example, `panda` might return `0.8` for `animal` and `0.3` for `bear` and `0.1` for `algorithm`.

# Answer
> 3 votes
The name of the classification you are looking for is called *Semantic field classification* (https://en.wikipedia.org/wiki/Semantic\_field). The sort of algorithm you are looking for falls under the category of *Statistical Semantic*.

---
Tags: classification
---


# Question
Title: Help with a difficult expected runtime recurrence
I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$.

At each iteration $i$, I have a random variable $k\_i$ that is equal to the number of heads after flipping $\frac{n}{2^i}$ coins minus $\frac{n}{2^{i+1}}$ (i.e. a binomial distribution centered at 0 with width $\frac{n}{2^i}$). The runtime of my algorithm is then given by the following recurrence:

$$B(0) = 0$$ $$B(i) = \max\\{B(i-1)+k\_i, 0\\}$$

When $B(i)$ is large, the negative and positive $k\_i$ can cancel each other out, so intuitively one should be able to come up with a pretty good bound on $\mathbb{E}\[B(n)\]$, but I have no idea where to start.

# Answer
> 1 votes
Yes, you'll have $B(i) = O(\sqrt{n})$ (with very high probability).

Note that $k\_i$ is binomially distributed, so it is approximately Gaussian. It has mean $0$ and standard deviation

$$\sigma\_i = \sqrt{n} \times 2^{-i/2 - 1}.$$

The probability that $k\_i$ is more than, say, 10 standard deviations above the mean is incredibly small. We'll define the event $\textsf{BAD}\_i$ to be true if $k\_i \ge 10 \sigma\_i$, and we'll define the event $\textsf{BAD}$ to hold if there exists $i$ such that $\textsf{BAD}\_i$ holds, i.e.,

$$\textsf{BAD} = \textsf{BAD}\_1 \lor \dots \lor \textsf{BAD}\_m.$$

By a union bound, we have

$$\Pr\[\textsf{BAD}\] \le \sum\_i \Pr\[\textsf{BAD}\_i\],$$

which is still very small. Moreover, if $\textsf{BAD}$ does *not* happen, then we have

$$B(m) \le \sum\_i 10 \sigma\_i = 10 \sqrt{n}/2 \sum\_i {1 \over \sqrt{2}^i} \le 10 \sqrt{n}/2 \times 3.5 = O(\sqrt{n}).$$

In other words, there is a constant $c$ such that $B(m) \le c \times \sqrt{n}$ with overwhelmingly high probability.

(I've shamelessly handwaved and glossed over details all over the place to present the intuition in a clean way, but even correcting for them isn't going to change the bottom-line answer.)

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation, randomized-algorithms
---


# Question
Title: Hash functions and pathological data sets
So I'm watching an Algorithms course in Coursera, and we are currently discussing hash tables. He's talking about the importance of a good hash function, and about how an ideal hash function would be a "super clever hash function guaranteed to spread every data set evenly".

Then, he explains that the problem is that such a hash function does not exist (and that for every hash function there is a pathological data set), and that the reason for this is as follows:

Fix a hash function $h: U \to \\{0, 1, 2, ..., n-1\\}$. **By the Pigeonhole Principle, there exists a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$.** If a data set draws only from these, everything collides.

The bolded part is what's confusing me. Why does there exist a bucket $i$ such that at least $|U|/n$ elements of $U$ hash to $i$ under $h$? I can't really visualize what he means.

# Answer
> 6 votes
An easy way to visualize this is to imagine a hash table of size $n$ (implemented with chaining) that contains all of the elements of $U$ (even though this is unrealistic in practice because $U$ typically has massive size). Since $|U| \>\> n$, all of the elements of $U$ do not fit into the hash table; therefore, there will be collisions. Consider, for example, the universal set $U=\\{a,b,c,d,e,f,g\\}$ and a hash table with $n=3$ buckets. Since $|U|=7$, at least one bucket must necessarily contain $\lceil \\: |U| \\: / \\: n \rceil = \lceil 7/3 \rceil = 3$ or more elements. In the case of the most clever hash function (which would spread out the elements of $U$ as evenly as possible), this bucket would contain exactly $3$ elements, like this (highlighted in red):

It is important to see that no matter how clever the hash function is, there will always exist a data set (for example, the set $\\{b,g,a\\}$) whose elements hash to the same bucket (for example, bucket number $1$). Such a **pathological data set** will make your hash table degenerate to its worst-case linear-time performance.

# Answer
> 4 votes
Assume there is no such bucket. Then each bucket has at most $|U|/n - 1$ items. There are $n$ buckets, so the total number of items is at most $n\*(|U|/n - 1) = |U| - n$. This is less than $|U|$, which is the number of items we distributed to the buckets in the first place. This is a contradiction, so we proved that the statement "each bucket has at most $|U|/n - 1$ items" is false, which is equivalent to the statement "some bucket has at least $|U|/n$ items."

---
Tags: hash-tables, hashing
---