# Question
Title: Can someone show me step-by-step how to calculate the primitive operations of this algorithm?
See the example algorithm below from my course notes, I don't follow the operation counting in the inner loop. Can someone walk me through this step-by-step?

Here's the algorithm:

```
Algorithm PrefixAverages1(A, n):
    Input: An integer array A of size n.
    Output: An array X of size n such that X[j] is the average of A[0] to A[j]

    Let X be an integer array of size n         1
    for j=1 to n-1 do                           2
        a <- 0                                  3
        for k=1 to j do                         4
            a <- a + A[k]                       5
        X[j] <- a/(j+1)                         6
    return X                                    7

```

The solution provided to this sample question uses the following steps to calculate the total cost (in primitive operations\*) of the running time of the algorithm:

Operation counting for main body and outer loop:

* $1 + op(outerLoop) + 1$
* $2 + op(outerLoop)$
* $2 + (1 + (B-A + 2)op(j\>n-1) + (B-A + 1) * 2 + op(innerLoop))$ where $B = (n-1)$ and $A = 1$
* $2 + 1 + 2n + (n-1) * 2 + op(innerLoop)$
* $1 + 4n + op(innerLoop)$

Operation counting for inner loop:

1. $innerLoop = \sum\_{j=1}^{n-1} 5j + 7$
2. $innerLoop = \left(\sum\_{j=0}^{n-1} 5j + 7 \right) - 7$
3. $innerLoop = \left(5\sum\_{j=0}^{n-1} j + \sum\_{j=0}^{n-1}7 \right) - 7$
4. $innerLoop = \left(5\sum\_{j=0}^{n-1} j + 7n \right) - 7$
5. $innerLoop = \frac{5n^2}{2} + 7n - 7$

Then putting the cost of the inner loop and the main body together, the total cost is shown as:

* $\frac{5n^2}{2} + 11n -6$

Specifically I don't follow the operation counting for the inner loop, I understand why there's a $- 7$ added when the sum is changed from $j=1$ to $j=0$. But I don't quite understand the subsequent steps that manipulate the equation.

---

**Source:** This is a previous exam paper from my University course.

* **List of primitive operations:**

* Indexing into an array
* Assignment
* Arithmetic
* Method call
* Following an object reference
* Comparison
* Returning a value

# Answer
> 3 votes
I'll list the arithmetic rules used in each step. In the following $f$ and $g$ are terms that possibly depend on $i$, while $a$ doesn't depend on $i$.

1. has no operations.
2. you explained in the question.
3. $$\sum\_{i=x}^y f+g = \sum\_{i=x}^y f + \sum\_{i=x}^y g$$ and $$\sum\_{i=x}^y af = a\sum\_{i=x}^y f.$$
4. $$\sum\_{i=x}^y a = (y-x+1)a.$$
5. is wrong. The correct formula to apply would be $$\sum\_{i=0}^y i = \frac{y(y+1)}2,$$ making the result from the question $$x = \frac{5n(n-1)}2 + 7n - 7 = \frac 52 n^2 + \frac 92 n -7.$$

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Why addition algorithm is not pseudo- polynomial?
There is something I don't understand.

In the Subset Sum problem, in the Dynamic Programming solution, because of binary representation of the sum T, we say it is pseudo-polynomial in run time; we must sum in the worst case from 1 to T.

So I don't understand why the Addition algorithm is not pseudo-polynomial, when we can add great numbers too.

# Answer
The reason is that the runtime of addition is proportional to the number of digits, not the value of the numbers, as it is for subset sum. Remember that the number of digits is the size of the input.
> 8 votes

# Answer
The subset sum algorithm runs in time $\tilde{O}(S)$, where $S$ is the sum we're looking for. The input length is $n = \log S$, since it takes this many bits to encode $S$ in binary. Overall, the algorithm takes time $\tilde{O}(2^n)$, which is exponential.

In contrast, you can add two $n$-bit numbers in $\tilde{O}(n)$, which is polynomial time.

(The notation $\tilde{O}(f(n))$ usually means "up to logarithmic factors", but here I use it to mean "roughly".)
> 5 votes

---
Tags: algorithm-analysis, arithmetic, pseudo-polynomial
---


# Question
Title: How can a problem be undecidable yet enumerable?
How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers and can be computed by a program with an output. But if thats the case it should be decidable. Or is decidability separated from computability?

Am I misunderstanding the intuition of the halting set?

# Answer
For me, the easiest way to think of it is this:

You're asking yourself "out of a bunch of candidates in a set $X$, do any of them fulfill the property $P$"?

Decidable/recursive means that you only need to look at a finite number of elements of $X$ before you hit some point where you know nothing that's left has the property.

A problem that's recursively enumerable, but not recursive, is one where you can look at each $x$ in $X$ one at a time. If you find one, then you're done, you know there exists on that fulfills your property. But there's no way of knowing when you're done, and $X$ is infinite, so if one doesn't exist, you will end up searching forever.

This contains some simplifications over the theoretical definitions, so be careful.

As an example: The halting problem is, you're looking at all $x\_1, x\_2, \ldots$ where each $x\_i$ is a configuration of the turing machine $M$ after $i$ steps. The property is, is $x\_i$ in a halting state. If you find one, you're done, but if you don't find one, there's no way to know when you're done.

Compare this to the SAT problem. You've got a Boolean formula, and you want to give each variable a True or False value to make the whole thing true. Even though it's really slow, you can try all true/false combinations. There's an exponential number of them, but it's finite. When you're done, you're done, and if none of them satisfied, you can halt, confident that there's no answer.
> 0 votes

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Best algorithm for correlation between time series?
I have some biological data (ECG), which are quite chaotic in nature, and and some other data; that are not chaotic but related in some way, like fatigue. I want to find out how the time series, chaotic, data are related to each of these other time series.

My undergrad thesis was on string "emotion" classification and time series is a whole other animal. My goal is to understand how the "other data" trend and at what percentage in correlation the biological data, not just classes \[A, B, C\].

I want to be able to distinct what is happening throughout the biological's phases in retrospect to the other time series. Like in this phase of the ECG there was 20% increase in fatigue, 7% in attention etc. I have all those data I just don't know how to make the connection.

I tried to find on time series ML but all of them jump from pretty basic algorithms and vague narratives to hardcore mathematical implementations.

If you know of a site, blog, docs, anything that ease into such examples and, very important, have code (python would be nice).

Would Random Forest work for such a task or should I be looking more into KNN (K-Means Nearest Neighbour), DTW (Dynamic Time Wrapping), STMF (Shape-based Template Matching Framework)?

Thank you very match for your time. Would be happy to provide and clarification I can, if anything doesn't make sense.

# Answer
You haven't given us much information about your problem, so let me give you some hints about how to approach this.

First, **look for a model**. Ask yourself: Do you have a plausible biological/physical model for how the dependent variables might depend on the independent variables? Why do you think it's plausible that the independent variables might help in predicting the dependent variables? This may help you select an appropriate machine learning tool.

If you don't have a model and don't have any physical/biological reason to expect a causal relationship, then you're doing data mining (and maybe you should reconsider why you are doing this project, or maybe you need to study the underlying application domain better to try to investigate candidate explanations why there might be a causal connection between the two).

Second, **classify the data you have**. The right algorithm will depend on what data is in the time series. Ask yourself: What is the value at each point in time, for the dependent variables and the independent variables? For each, decide whether you have ordinal data, categorical data, or interval data -- that will play a huge role in narrowing down which machine learning algorithm might be applicable. Also, ask yourself whether you know anything about their distributions.

Third, **visualize your data**. Before you start diving into complex machine learning algorithms, do some data visualization. Try to find as many ways as you can think of to look at your data. Sometimes when you stare at data in the right way, that suggests hypotheses or relationships that might be relevant.

So, do all of that. That will help you think more clearly about the problem, and may help you narrow down the scope of machine learning problems. Once you've done all of that and can answer all of those questions, you might be in a position to ask a better-crafted, more narrowly scoped question.

---

Last, don't forget to consider some variety of linear regression: for interval data where you hypothesize some kind of linear relationship, it's a natural first thing to try.
> 1 votes

---
Tags: reference-request, machine-learning, data-mining, classification, statistics
---


# Question
Title: Complexity of bitwise AND operation on bit string regular expressions
Given two regular expressions of bit strings $B\_1$ and $B\_2$ of the same length (stated mathematically, $B\_1,B\_2 \in \\{0,1\\}^m$) that use only grouping and repetition, what is the optimal running time of performing a bitwise AND operation on $B\_1$ and $B\_2$?

For example, given two regular expressions, $B\_1 = ((10)^2(01)^2)^2$ and $B\_2 = (01)^8$, the resulting pattern $R$ of the AND operation would be $R = ((0^4(01)^2)^2$.

Does there exist an algorithm that will run in polynomial time (with respect to the lengths of the regular expressions)? Note, you can pair every possible combination of groups in $O(n^2)$ time, where $n$ = $\max(|B\_1|,|B\_2|)$, and $|B\_i|$ is the length of regex $B\_i$. However, that still does not give you the resulting bit string regular expression $R$.

The exponent $k$ of a given substring can be stored in binary form, so it only adds $\log(k)$ bits to the representation. Furthermore, note that given any two groups of size $m$ and $n$, there are at most $\max(m,n)$ bit patterns of length $\min(m,n)$ that can result. In addition, if there are $g\_1$ groups in $B\_1$ and $g\_2$ groups in $B\_2$, then there can only be $g\_1 g\_2$ unique pairs of groups. Therefore, I think it can be concluded that the space required is at most $O(g\_1 g\_2 \max(|group\_{i,B\_1}|,|group\_{j,B\_2}|)^2)$, which is polynomial in $n$. However, I am still missing the proof that the resulting regular expression can be found in polynomial time.

For slightly easier problem, you can assume that every repetition is a power of two. However, that does not necessarily mean that groups are power of two in size. For an even further simplification you, could assume the groups are also a power of two in size.

Now that I think of it, I will include this idea which I just came up with. You can represent the offsets of the 1s every group as set of linear integer equations. Then you may be able to find solutions to pairs of integer equations with constraints somehow? Or am I over complicating it?

Another possibility is, as Yuval Filmus suggests, convert to NFA. However, I am not clear why an NFA would be needed since these are fixed sequences (that is, the number of repetitions is fixed). Furthermore, I am not sure how one would apply the AND operation after they are in NFA form.

# Answer
> 1 votes
## Formalism

Let me formalize your problem as follow. Define a *gegular expression* as an expression that follows the following grammar:

$$E ::= 0 | 1 | E\_1 E\_2 | E^k,$$

where $k$ ranges over positive integers and $E\_1,E\_2$ range over gegular expressions. Note that these are not regular expressions, as Yuval Filmus explains, even though they are related.

Obviously, each gegular expression codes for a single binary string. If $E$ is a gegular expression, let $\[E\]$ be the binary string is codes for. Also let $\text{len}(E)=\text{len}(\[E\])$ denote the length of the binary string $\[E\]$. Of course, these can be easily computed recursively: e.g., $\text{len}(E\_1 E\_2) = \text{len}(E\_1) + \text{len}(E\_2)$ and $\text{len}(E^k) = k \times \text{len}(E)$.

Given two gegular expressions $E\_1,E\_2$, the ultimate goal is to find a third gegular expression $E\_3$ such that

$$\[E\_3\] = \[E\_1\] \land \[E\_2\],$$

i.e., that represents the bitwise-AND of the bit strings that $E\_1,E\_2$ code for. If this holds, we will write $E\_3 = E\_1 \land E\_2$. ($E\_3$ may not be unique -- there may be multiple acceptable $E\_3$ -- but we won't let this bother us.)

## Helpful tools

Here are some little lemmas that are helpful.

First, if $E$ is a gegular expression and $\ell$ is a positive integer, we can compute a new gegular expression that codes for the first $\ell$ bits of $\[E\]$. Define $\text{prefix}\_\ell(E)$ to be this gegular expression. We can compute $\text{prefix}\_\ell(E)$ recursively using the following relations:

$$\text{prefix}\_\ell(E\_1 E\_2) = \begin{cases} \text{prefix}\_\ell(E\_1) &\text{if $\ell \< \text{len}(E\_1)$}\\ E\_1 &\text{if $\ell = \text{len}(E\_1)$}\\ E\_1 \\; \text{prefix}\_{\ell-\text{len}(E\_1)}(E\_2) &\text{otherwise.} \end{cases}$$

$$\text{prefix}\_\ell(E^k) = E^{\lfloor \ell / \text{len}(E) \rfloor} \\; \text{prefix}\_{\ell \bmod \text{len}(E)}(E).$$

You might notice that this does not increase the size of the gegular expression too much (at most a quadratic blowup, and usually much less).

Also, there are some special cases where your problem is easy. For instance.

$$E\_1^k \land E\_2^k = (E\_1 \land E\_2)^k$$

if $\text{len}(E\_1)=\text{len}(E\_2)$.

If the exponents are not identical, we can reduce to the above case. Let $E\_1,E\_2$ be two gegular expressions of lengths $\ell\_1,\ell\_2$, respectively (i.e., $\ell\_i = \text{len}(E\_i)$). Let $m = \text{lcm}(\ell\_1,\ell\_2)$ be the least common multiple of their lengths. Then

$$E^k = (E E \cdots E)^{\lfloor k/m \rfloor} E E \cdots E$$

holds for all $E,k,m$, where the first $E E \cdots E$ represents $m$ concatenations of $E$ and the second $E E \cdots E$ represents $k \bmod m$ concatenations. Thus we have

$$E\_1^{k\_1} \land E\_2^{k\_2} = (E\_1 E\_1 \cdots E\_1 \land E\_2 E\_2 \cdots E\_2)^{k\_3} \\; \big( \text{prefix}\_{\ell'\_1}(E\_1^{k\_1}) \land \text{prefix}\_{\ell'\_2}(E\_2^{k\_2}) \big),$$

Also, if $\text{len}(E\_1) = \text{len}(E'\_1)$, then

$$(E\_1 E\_2) \land (E'\_1 E'\_2) = (E\_1 \land E'\_1) (E\_2 \land E'\_2).$$

If they are not of the same length, say $E\_1,E'\_1$ have lengths $\ell\_1,\ell\_2$ where $\ell\_1\<\ell\_2$, then we can express their bitwise-AND as

$$(E\_1 E\_2) \land (E'\_1 E'\_2) = (E\_1 \land \text{prefix}\_{\ell\_1}(E'\_1)) (\text{prefix}\_{\ell\_2-\ell\_1}(E\_2) \land \text{tail}\_{\ell\_2-\ell\_1}(E'\_1)) (\text{tail}\_{\text{len}(E'\_2)}(E\_2) \land E'\_2).$$

(Here $\text{tail}()$ is defined analogously to $\text{prefix}()$, except it relates to the end of a string rather than the beginning.)

I think from these special cases, you should be able to build a recursive algorithm that computes the bitwise-AND of any two gegular expressions.

---
Tags: complexity-theory, time-complexity, regular-expressions
---


# Question
Title: Can a Markov Algorithm Replace the Empty String?
Suppose I have a Markov Algorithm, and I have some rules, such that after execution of these rules, the remaining string is either "a", "b", or the empty string, "". Then I have three terminal rules to cover these cases:

1. "a" -\>. "100"
2. "b" -\>. "99"
3. "" -\>. "0"

Is the last rule a valid terminal rule? Can a Markov Algorithm replace the empty string, or does it halt as soon as the string it is computing is empty?

# Answer
> 2 votes
Rules of the form $\epsilon \to w$ are allowed for Markov Algorithms. Be aware, however, that they will not only match, when the string is empty. Instead they will match every string, since every string contanins $\epsilon$ as a substring.

Since a rule that matches at multiple positions will be applied to the leftmost of them by definition, Rule 3 from your question will prepend a 0 to the string and terminate, whenever no rule before it is applicable. So, unless your previous processing relies on the fact that the algorithm will terminate when no rule is applicable (or already contains a rule for a or b), adding the three rules from the question as the last rules will give you the desired result.

---
Tags: algorithms, strings
---


# Question
Title: Leftist heap - determining time complexity
The time complexity of merge (union) operation is said to be $O(\lg (n\_1 + n\_2))$, where $n\_1$ and $n\_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the algorithm has to go through all the elements of both rightmost paths of the original heaps - lengths of these paths are bound by $O(\lg n\_1)$ and $O(\lg n\_2)$. That makes $O(\lg n\_1 + \lg n\_2)$ in total, which is $O(\lg (n\_1 n\_2))$. Where am I making a mistake in my assumptions?

Arbitrary delete operation - the complexity should be $O(\lg n)$, where $n$ is the size of the heap. But after the deletion, the algorithm has to go through all the nodes from the parent of the deleted node to the root and correct the Leftist property, and the lenght of this path is bound by $O(n)$. Again, where am I wrong?

# Answer
> 3 votes
For the time complexity of merging, JeffE already pointed out in the comments that $O(\log(n\_1n\_2)) \in O(\log(n\_1+n\_2))$.

For arbitrary deletions note the following:

* When we merge the two subtrees of the deleted node, the root of the resulting tree will have an s-value that is at least the s-value of the deleted node -1.
* Thus, the s-value of any updated node will not be decreased by more than 1. (There is no constant bound for how much it can increase.)
* Thus, if we update the s-value of a left child in and that value was strictly larger than the s-value of the right child, the s-values of the parent and all nodes above the parent will not change.
* If the s-value of the left child and right child are equal, exchanging them still gives a valid leftist heap.
* Thus, the number of updated nodes is bound by the length of a right flank in a leftist tree, which in turn is bound by $O(\log n)$.

---
Tags: data-structures, runtime-analysis, heaps
---


# Question
Title: What is a suitable data structure in this scenario?
I need an efficient data structure for maintaining a set of values. Here, $n\_1$ is the number of insertions per unit time; $n\_2$ is the number of deletions per unit time; $k$ is the number of searches per unit time.

I have 4 possible use cases:

1. $k \gg n\_1,n\_2$ with limited memory
2. $n\_1 \gg k,n\_2$ with limited memory
3. $k, n\_1, n\_2$ are comparable with limited memory
4. $k, n\_1, n\_2$ are comparable with unlimited memory

I have decided to use a doubly linked list for the second case and a direct address table for the fourth case.

My question is about the first and the third cases. Both Hash Table and Tree (AVL or Red-Black) look promising. Should I choose the Hash Table with an amortised constant time or the Tree with a $\log n$ worst case time?

# Answer
> 1 votes
Depending on how limited the memory is, the best choice for 1 could be a sorted array: Binary search is fast, insertions and deletions are rare and memory overhead is negligible.

For number 2 a (unsorted) singly linked list is better than a doubly linked one, since we (presumably) don't perform any operations that benefit from the backlinks and thus can save the memory (and maintenance time) required for them.

For number 3, unless the hash function and data don't play nicely with each other, the hash table will likely be faster than a tree. If the load factor does not get too low, it will also be more space efficient, since a binary tree with $n$ keys needs $\sim 2n$ pointers.

---
Tags: data-structures, efficiency, dictionaries
---


# Question
Title: Finding minimum/maximum value in a Binary Indexed Tree
I know how a BIT works. But I was wondering if a BIT can be used to find the minimum/maximum element in the complete range, or more specifically, to find the minimum (or maximum) value after all the update processes have been completed. Now, I know that this can very well be achieved using Segment Trees, but is it possible to do the same using a BIT?

I know the obvious way of traversing the complete BIT and calculating the value at each index. I am looking for a more efficient/optimized way.

# Answer
> 2 votes
You cannot do better than $O(n)$.

Consider a set, where all values are $k$, except $2i$ and $2i-1$, which are $k-l$ and $k+l$ respectively. Any entry in the tree that contains a sum of $m$ values will be $mk$, with the single exception of the entry $2i-1$.

Thus, even if we knew we had a set of the form described, we had to look at $\frac n2$ entries in the worst case, in order to determine the minimum and maximum value.

---
Tags: data-structures, binary-trees
---


# Question
Title: Does an associative array represent a mapping?
An associative array is a set of pairs (key, value).

Does it represent a mapping, or a relation (i.e. does it allow the same key to be associated to different values)?

Does it represent an injective mapping only, or does it allow different keys to be associated to the same value?

Can a hash table implement any associative array, or just some special types of associative array?

# Answer
> 2 votes
If the sentence you give is the whole definition, then an associative array is a relation and not necessarily injective.

A hash table can implement only mappings, but it does not require them to be injective.

---
Tags: terminology, data-structures, hash-tables
---


# Question
Title: Power of nondeterministic type-1 min-heap automaton with both a heap and a stack
I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

Two of my last questions seem to have been quickly dispatched; one completely, and the other mostly (I have edited it to make it more viable). In either event, I actually had one other question I meant to ask, and would be interested to lay this subject to rest for good and all. So here it is:

> A two-stack PDA can simulate a Turing machine. A $k$-heap nondeterministic type-1 min-heap automaton cannot (it seems; see the linked question). What about a $k$-tape nondeterministic type-1 min-heap automaton augmented with a stack (similar to that of a PDA)? Can it simulate a Turing machine? If not, does an augmented $(k+1)$-heap nondeterministic type-1 min-heap automaton accept a class of languages which is a proper superset of languages accepted by augmented automata with only $k$ heaps?

Thanks, and I promise this is the last of these questions.

# Answer
A heap and a stack can both be used to implement a counter. 2 counters suffice to recognize $RE$. (See also)
> 3 votes

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


# Question
Title: Is the language of words with as many a's in the first as b's in the second part context-free?
Is $L = \\{ W\_1W\_2 \mid W\_1,W\_2 \in (a+b)^\* , N\_a(W\_1) = N\_b(W\_2)\\}$ context free? Can we construct an NPDA for the language?

There is a book here that claims $L$ is not CF (without any elaboration), but I think we can construct a NPDA that accepts the language. My guess is we can construct the language with an NPDA where after reading some $a$ and $b$ and pushing $A$ for each $a$ into the stack, makes a guess to jump to a new state and consumes the pushed $A$ with each $b$.

# Answer
> 4 votes
Yes, the language is context-free.

Let $w$ be a word in $\\{a,b\\}^\*$. Decompose it as $w = u v$ where $|u| = N\_b(w)$. $$ \begin{align} N\_a(u) &= N\_a(w) - N\_a(v) && \text{because \\(w = u v\\)} \\ &= N\_a(w) - (|v| - N\_b(v)) && \text{because \\(v \in \\{a,b\\}^\*\\)} \\ &= N\_a(w) - |w| + |u| + N\_b(v) && \text{because \\(|v| = |w| - |u|\\)} \\ &= |u| - N\_b(w) + N\_b(v) = N\_b(v) \\ \end{align} $$ Thus we can decompose any word in the desired form: $L = \\{a,b\\}^\*$. Constructing a PDA is left as an exercise to the reader.

This still works if the language contains other letters, by the way, but you have to take a prefix of $w$ that contains $N\_b(w)$ letters in $\\{a,b\\}$ and arbitrarily many other letters.

Another way to see this is to notice that if there is an $a$ in $u$ and a $b$ in $v$, then you can swap the two letters, which results in a word that has the same balance $N\_a(u) - N\_b(v)$. $L$ is the set of words whose balance is zero for some split position. Iterate this decomposition until it becomes impossible: either $u$ contains no $a$ or $v$ contains no $b$. If we choose the split position so that $|u| = N\_b(w)$ and $|v| = N\_a(w)$, then now $u$ contains all the $b$'s and $v$ contains all the $a$'s: $N\_a(u) = 0$ and $N\_b(v) = 0$, and in particular the balance is 0.

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


# Question
Title: Turing-unrecognizable language - what TM does?
I have a problem giving "intuitive" explanation to turing-unrecognizable languages.

We can prove that, say, ${\overline{A\_{TM}}}$ is not turing-recognizable, because that would make ${{A\_{TM}}}$ decidable, but what would the $TM$ do if it doesn't accept, reject of loop?

# Answer
You might be a little confused by a definition somewhere. A TM $M$ is a recognizer for a language $L$ if it

* Accepts every string in $L$
* Either rejects or loops on every string not in $L$

Now let's think about the language ${\overline{A\_{TM}}}$. An input $\langle N,x\rangle$ is in ${\overline{A\_{TM}}}$ if either:

* $N$ rejects on $x$.
* $N$ loops on $x$

So any recognizer will need to figure out (in finite time) that $N$ is going to loop on some input, which is just the halting problem.
> 6 votes

---
Tags: computability, turing-machines
---


# Question
Title: What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?
1. In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the likelihood that a random pattern is a GoE as n increases?

Also, by the Garden of Eden-theorem, only cellular automata which are non-injective, that is, for which a given pattern may have more than one predecessor, contain Gardens of Eden.
2. Is it then in general impossible to see whether a given cellular automaton pattern at some time-step is derived from a GoE (since there could also have been a non-GoE ancestor leading to the same state)? That is, does the evolution of the CA 'wash out' the information that it is derived from a GoE? (I hope it's sufficiently clear what I mean.)
3. Furthermore, is there a relation between GoE-patterns and uncomputability/undecidability? It seems to me that if you consider the CA to be implementing some computation, then the GoEs are 'outputs that could never be produced', at least heuristically, but a brief Google search led nowhere. Perhaps asked another way, is there a relation between the existence of GoEs and the universality of a CA? I know Life is both universal and has GoEs, but I don't know about the general case. Any pointers would be much appreciated.

Having done some additional reading, I think I can strike out the third question: since reversible cellular automata that are computationally universal exist (according to wiki), there doesn't seem to be any connection between computational universality and GoEs. Now, what about universal constructors? Are there reversible universal constructors? Von Neumann's original rule happens not to be reversible, and in fact, has GoEs, but again, this need not say much.

The wikipedia page above mentions a way to emulate d dimensional irreversible CAs within d + 1 dimensional reversible ones, which readily establishes the computational universality of the latter, but I'm not sure if this holds as well for universal construction: the emulated constructor would only construct patterns on a d-dimensional sub-grid of the automaton (?).

# Answer
1. as said by vzn, any pattern containing a Garden of Eden pattern is itself a Garden of Eden Pattern, the probability that a random nxn pattern is actually GoE goes to 1 as n goes to infinity (in the case of a non-surjective CA of course, otherwise it's 0). More precisely, it is lower bounded by $1 - \alpha^{n²}$ for some $0\<\alpha\<1$. Indeed, consider a fixed GoE pattern P of size $k\times k$, then the probability for a random pattern of size $n\times n$ to be a GoE is at least $1 - (\frac{1}{q^{k^2}})^{(\frac{n}{k})^2}$, where $q$ is the number of states of the CA.
2. you can generate all the possible pre-image of a given pattern in finite time and you can also test whether a pattern is a GoE so your problem is clearly decidable. It's polynomial-time decidable in 1D and NP-hard in 2D.

* in the 1D case, a CA can be seen as a finite state transducer. So the language $L\_{GoE}$ of all GoE patterns is a regular language because it is the complement of $T(Q^\ast)$ (where $T$ is the transducer and $Q$ the set of states of the CA) which is itself a regular language as the image of a regular language by a transducer. Then $T(L\_{GoE})$ is also regular and its the set you asked.
    * in the 2D case, I think we can show that it is NP-hard using the classical simulation of Turing machines by Wang tiles. The rough idea is the following. Consider any NP-complete problem $L$ and take a Turing machine $T$ which is a polynomial time verifier for the problem. Then construct a CA that basically checks that the input, if written in some special alphabet $A$, encodes a successful computation $T(x,y)$ of $T$ working on input $x$ and witness $y$. If so erases everything with a special state $a\not\in A$, but keep the input x. If some error is detected produce some special state $b\not\in A$. Finally, the CA does nothing on states which are not in $A$. Now consider a pattern formed by an input $x$ surrounded by many $a$. The pattern as always itself as a preimage, but it as a GoE preimage if and only if there is some $y$ such that $T(x,y)$ says "yes", *i.e.* iff $x\in L$. **CQFD**
    *At the time of writing I don't see how to prove that the problem is NP*
3. as pointed-out Turing-universality is still possible without GoE patterns (in reversible CA for instance). But intrinsic universality requires GoE patterns. This comes from the fact that, first, a surjective CA only admits surjective CA as subautomata, and, second, grouping and iterating a CA doesn't change its surjectivity.
> 2 votes

# Answer
have not seen a strict technical definition of GOE, and one would seem to need to take into account the concept of what exactly constitutes "space" around the figure. in Life it is well determined, but for CAs in general which CA state denotes "space" needs to be defined.

1. the concept of "orphans" is relevant as cited on the wikipedia GOE page. basically there exist finite patterns called orphans that are GOEs and such that any addition around the finite pattern is also a GOE. this allows a lower bound on total GOEs, roughly, there are at least as many GOEs of a given size as there are orphans of a smaller size plus arbitrary bits surrouding the orphan. of course this is a very rough measure. on brief search did not see a paper that studied this specific question of incidence of GOEs at different sizes.
2. if you have a pattern and want to know if it has an ancestor thats a GOE, thats decidable to ask if the GOE is bounded by some size around the initial pattern because thats a finite search space (with some assumptions about how rules behave wrt "space" around the pattern). otherwise (conjecture) its undecidable (circumstantial evidence next).
3. indeed GOE testing is basically undecidable in general, in fact to any "undecidability degree" see thm 4.1 in this paper Cellular Automata and Intermediate Reachability Problems Sutner p 1006:

> Theorem 4.1. For any recursively enumerable degree $d$ there is a two-dimensional cellular automaton whose Garden-of-Eden Problem for ﬁnite conﬁgurations is of degree $d$.
> 1 votes

# Answer
Question 1:

I'd say that it's a function $F(k,r)$ where $k$ is the width of the neighbourhood the rules take into account (say $k=3$ in Conway) and $r$ a measure of the 'injectivity' of the rules (the probability 2 distinct configurations produce 2 distinct new states). In particular, as a first approximation, I would expect $F \propto k^2, F \propto r$.
> -2 votes

---
Tags: automata, cellular-automata
---


# Question
Title: Find $k$ subsets containing a particular element quickly
Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (\< n)$ subsets that contain $e \in U$ (call this *Extraction(e)*). Elements are integers.

To that effect, I want to preprocess/encode the $n$ subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is (assume that this item is uniformly selected over queries).

I don't have a good intuition for various methods to do this and after how much prerocessing space/time diminishing returns kick in. I'm certainly looking for something that takes polynomial time/space.

I was thinking about encoding the subsets as hashsets and then hashing together $q$ of these subsets together at a time, so that I end up with $\lceil\frac{n}{q}\rceil$ packaged hashsets. $q$ would be inferred in some fashion from the frequency distribution of all elements in U. Then I could iterate over these packaged hashsets and check for containment of $e$ in constant time (average-case).

Is this problem well-studied?

# Answer
> 2 votes
Use a hash table, keyed on elements of $U$. For each subset $S$ of $U$, say $S=\\{x\_1,\dots,x\_\ell\\}$, you'll add $S$ to the hash table $\ell$ times, once for key $x\_1$, once for key $x\_2$, and so on. Now to find all subsets containing some element $e$, just look into the corresponding bucket in the hash table and you can iterate over sets containing $e$ very rapidly.

This is basically just applying the idea of "indexes" from databases to your problem. It is straightforward and provides excellent time complexity, at the cost of modest space complexity (approximately doubling the space needed to store all of the subsets).

---
Tags: reference-request, data-structures, sets, hash, average-case
---


# Question
Title: What is the reason that is FFT multiplication slower than other methods for small N?
I've seen plenty of statements in papers and on websites that Fast Fourier Transform-based multiplication algorithms are slower than other multiplication algorithms for relatively small input size N, and I've seen plenty of data in papers and on websites demonstrating that this is the case, but nothing I've come across has bothered to explain what causes FFT to be slower for small N.

I would guess that the overhead is due to getting the input into a form that FFT can swallow, but I'd like to know what the actual cause of the overhead is and whether it can be reduced. Note that I'm not talking about switching from some FFT implementation to another method when N is below a certain size as many implementations do, but the source of overhead in the FFT itself and what can be done to reduce it.

# Answer
> 3 votes
The Wikipedia FFT article says that the split-radix FFT algorithm requires $4N\log\_2N-6N+8$ real multiplications and additions. Multiplying 2 degree $M$ polynomials results in a polynomial of degree $2M$, so the "FFT multiplication of two polynomials" goes like this:

```
FFT (size 2M) of polynomial f(x) (evaluate f(x) at the 2M primitive roots of unity)
FFT (size 2M) of polynomial g(x) (evaluate g(x) at the 2M primitive roots of unity)
multiply each of the 2M fourier coefficients together
inverse FFT (size 2M) of the fourier coefficients to get the resulting polynomial

```

Perhaps there is a way to make the first two `FFT`s faster based on the fact that the $M+1$th through $2M$th coefficients of `f(x)` and `g(x)` are all zeros, but I don't know it offhand.

So we are doing 3 FFTs of size $2M$ plus an additional $2M$ complex multiplies (each of which is 4 real multiplies and 2 real additions so: $$3 (4(2M)\lg2M - 6(2M)+8)+4M = 24M\lg M -8M+24$$ additions and $24M\lg M - 4M + 24$ multiplications.

Meanwhile the naive polynomial multiplication algorithm (convolution) takes $M^2$ real multiplications and $(M-1)^2$ real additions. (Proof left as exercise for the reader.)

Thus the naive algorithm will be faster for $M \leq 128$, while the FFT based algorithm will probably be faster at $M \geq 256$, and the crossover will be somewhere between 128 and 256. (Proof left as exercise for the reader.)

I did this quickly and sloppily, so I'm probably off somewhere (e.g., the forward FFTs are real -\> complex, (but is there a DCT version that would be cheaper?) while the reverse is complex -\> real (which may have slightly different constants than the ones I used,) and I only did the evaluation at $M$ power of 2 (FFT of non-power of 2s is more expensive.)) Nonetheless, the point stands: the constant multiplier for the FFT is approximately 24, while the constant multiplier for the naive convolution is 1, so you need to compare (something like) $24M\lg M$ to $M^2$.

---
Tags: algorithms, algorithm-analysis, fourier-transform
---


title: How to filter a very, very large file

text:
# Question
Title: How to filter a very, very large file
I have a very large unsorted file, 1000GB, of ID pairs

1. ID:ABC123 ID:ABC124
2. ID:ABC123 ID:ABC124
3. ID:ABC123 ID:ABA122
4. ID:ABC124 ID:ABC123
5. ID:ABC124 ID:ABC126

I would like to filter the file for

1) duplicates

```
example
ABC123 ABC124
ABC123 ABC124

```

2) reverse pairs (discard the second occurrence)

```
example
ABC123 ABC124
ABC124 ABC123

```

After filtering, the example file above would look like

1. ID:ABC123 ID:ABC124
2. ID:ABC123 ID:ABA122
3. ID:ABC124 ID:ABC126

Currently, my solution is this

```
var hash;

foreach line in file
      get ID1
      get ID2

      if exists in hash ID1ID2 or exists in hash ID2ID1
        //next line, as we have already have this in our collection
      else
         add to hash ID1 ID2
         print the line

```

which gives me the desired results for smaller lists, but takes up too much memory for larger lists, as I am storing the hash in memory.

I am looking for a solution that will take less memory to implement. Some thoughts I have are

1) save the hash to a file, instead of memory

2) multiple passes over the file

3) sorting and uniquing the file with unix `sort -u -k1,2` , but that takes many hours and it also doesn't reduce the file that much. So even if I run that sort, Most of the filesize is retained. when the hash is searched for ID2ID1 , I still have to load a huge file into memory

# Answer
> 2 votes
You have a dataset with at least billions of entries, whose size is that of a medium-sized hard disk. This is large. If something takes only “many hours” and not many months, that's as good as you can expect.

Sorting the file is a viable strategy to get rid of the duplicates. You'll also need to canonicalize the pairs. If you stick with a flat file, the most likely strategy is to do a pass of canonicalization where you define an order relation on the IDs and swap the pairs if the larger ID comes first. For the canonicalization step, you can use `awk` or a custom C program. For the sorting step, use `sort`, which is (at least on Linux) capable of doing external sorts and is likely to be faster what you'd come up with. Do this in a C locale to make processing faster (based on bytes rather than multibyte characters).

If you want to do lookups, a terabyte-sized flat file is not the right format. This is large even for a database. On the topic of databases with billions of records, read Can MySQL reasonably perform queries on billions of rows? and Which database could handle storage of billions/trillions of records?. A database may or may not be adequate for your task — this depends if the pairs are all you have or if there's other data to consider, and on whether there's structure to the IDs. I think a database would be the right tool if you want to support queries like “list the pairs that contain this ID value”. You should ask database professionals, rather than computer science professionals, whether and which database would be suitable; be sure to explain the structure of your data and what kind of queries you'll want to make. If you decide to use a database, there's no need to remove duplicates or canonicalize entries before importing them, that will happen on the fly.

If you determine that you aren't going to benefit from a database, then you should organize your data in a structured way. The best structure depends on the density of the data, i.e. how many of the potential pairs are present, how many of the potential IDs are present, the distribution of IDs, etc. Here's an example of the kind of structure that might work:

* A toplevel directory determined by the first two characters of the first pair.
* A second-level directory determined by the next two characters of the first pair.
* In these directories, a file per first ID, named with the first ID and containing the list of second IDs.

This is just an example — you need to find a repartition that works. With typical Linux filesystems, aim for about 100–1000 entries per directory (i.e. 100–1000 toplevel directories, 100–1000 subdirectories in each directory, 100–1000 file in the deepest directories).

There's no need to remove duplicates before moving the data into a structured file set like this. You may want to do a pass of canonicalization first (or do it on the fly).

If you're going to make a lot of queries and you expect many of them do come up negative, build a Bloom filter. Define a fast hash function on pairs whose output is $N$ bits, and write an array of $2^N$ bits to a file where the nth bit indicates whether there exists a pair whose hash is $n$.

# Answer
> 0 votes
Use GNU/Unix `sort`. It is designed exactly for this sort of thing, and is perfect for removing duplicates. (See, e.g., `sort -u` or `sort ... | uniq ...`.)

You might want to tune the initial buffer size, with parameter `-S`.

GNU sort already implements algorithms to sort files that are larger than can be fit into main memory, and thus it can handle very large files. The algorithmic technique you are looking for is called "external sorting". There's *lots* written on the subject. You can do your own research for more on that.

---
Tags: algorithms, efficiency, memory-management, data-sets, information-retrieval
---


title: Solution of complex recurrence relation

text:
# Question
Title: Solution of complex recurrence relation
Do anyone have any idea how to solve this recurrence?$$T(k) = \sum\_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$

I am working with this kind of recurrence for the first time and don't have much idea of how to proceed. But, for beginning I was trying to guess the solution and use substitution method. But, in the guessing part itself I am stuck. It seems like the solution should be exponential to $k$.

# Answer
Everything becomes much simpler if when $n$ is odd we stop the sum at $\lfloor n/2 \rfloor$, and when $k$ is even we discount the term corresponding to $k/2$ by a half. In that case you can write $$ 2T(k) = \sum\_{i=1}^{k-1} \binom{k}{i} T(i) T(k-i) $$ and so, putting $T(0) = 0$, we get that for $k \geq 2$, $$ 2T(k) = \sum\_{i=0}^k \binom{k}{i} T(i) T(k-i). \tag{1}$$ (When $k = 1$ this reads $2T(1) = 0$.)

Now define the exponential generating function $$ P = \sum\_{n \geq 0} T(n) \frac{x^n}{n!}. $$ Put $T(1) = c$. The identity (1) implies the equation $$ 2(P-cx) = P^2. $$ Solving the quadratic, we obtain $$ P = 1 - \sqrt{1 - 2cx} = 1 - \sum\_{n \geq 0} \frac{(2n)!}{(1-2n)(n!)^24^n} (2cx)^n = \sum\_{n \geq 1} \frac{(2n)!(c/2)^n}{(2n-1)n!} \frac{x^n}{n!}. $$ We conclude that for $n \geq 1$, $$ T(n) = \frac{(2n)!(c/2)^n}{(2n-1)n!} \sim \frac{1}{\sqrt{2} n} \left( \frac{2c}{e} n \right)^n. $$ The first few terms (starting with $T(1)$) are $$ c,c^2,3c^3,15c^4,105c^5,\ldots $$
> 7 votes

---
Tags: combinatorics, recurrence-relation
---


# Question
Title: What is the regular expression to the given language?
I can't really find out, how can the following given Language be written down with regular expressions

$ L = \\{ a^{3k-1} b^n a^{2t} \mid n \> 0; k, t\ge1 \\} $

I had some guesses, but I don't know how to express the part $a^{3k-1}$ of the Language. Probably it should look something like this:

$(aaa)^+$ `[something]` $b^\*(aa^+)$

# Answer
> 3 votes
Look at the three parts of your language:

1. For the $a^{3k-1}$ part, we have possibilities $a^2, a^5, a^8, \dots$. For this part we'll have any 2 $a$s plus a multiple of 3 $a$s. That's expressible as $aa(aaa)^\*$.
2. The $b^n$ part is easy, it's just $b^+$, since you need $n\>0$.
3. The $a^{2t}$ part is likewise easy. Since $t\ge 1$ we can express this as $(aa)^+$.

Now concatenate these three regular expressions.

# Answer
> 1 votes
Hint: How would you represent the language $L\_{odd} = \\{ a^n \mid n \\,\text{is odd}\\}$? First, you'd find an equation that always yields an odd number. The least odd number is $1$. So $a$ is in the language. Now, think of getting new odd numbers from this initial $1$ by adding a number to $1$. You do this by repeatedly adding $2$'s to $1$: $1 + 2k, k \geq 0$, or equivalently $2k -1, k \> 0$. In terms of regular expressions, you recognize odd sequences of $a$ by a regular expression that recognizes $a$ and zero or more sequences of $aa$ concatenated to that initial $a$ ($2k, k \geq 0$): $L\_{odd} = a(aa)^\*$.

It should be possible to generalize to any equation $c\_1k - c\_2$, $c\_1$ and $c\_2$ being constants and $c\_1k \> c\_2$, such as the equations $3k-1, n, 2t$, in your case.

Solution:

> $aa(aaa)^\*b^+(aa)^+$

# Answer
> 0 votes
You need an extra two a's in the beginning to get the right pattern. $(aa)(aaa)^\*b^+(aa)^+$

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


# Question
Title: Divide an integer into the sum of consecutive positive numbers
Today I am trying to solve an classical problem:

> For any $n\in \Bbb{N}^+$, If it can be represent as the sum of consecutive positive numbers, find out them.

For example:

$$15 = 1+2+3+4+5$$ $$15=4+5+6$$ $$15=7+8$$

And I have an ugly method, its time complexity is: $O(n^2)$. I use two for loop to exhaustion all possibilities.

```
for(int i=1;i<n;i++)
{
    for(int j=i;j<n;j++)
    {
        sum+=j;
        if(sum==n)
        {   //print out the answer
            for(int l=i;l<=j;l++)
            {
                cout << l << "+ ";
            }
            cout << endl;
            break;
        }
    }
    sum = 0;
}

```

I think there may be exist a more effective solution, But I am failed until now. Please help me.

```
for i from 1 to n
{
   for j from i to n
   {
       sum <- sum + j
       if sum equal n
       {
          print the result
       }
   }
   sum <- 0
}

```

# Answer
> 8 votes
Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum\_{i=1}^m i = \frac{(m+1)m}{2}$, $$ \sum\_{i=a+1}^b i = \sum\_{i=1}^b i - \sum\_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \frac{(b-a)(b+a+1)}{2}. $$ Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we want $x,y$ to have different parities (this is only a restriction if $n$ is even) and $y \geq x+1$. Also, $b \neq a+1$ corresponds to $x \neq 1$.

For example, for $n = 15$ we have $2n = 30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$. These correspond to the following pairs $(a,b)$: $$ (6,8),(3,6),(0,5). $$ These, in turn, correspond to the representations $$ 15 = 7+8 = 4+5+6 = 1+2+3+4+5. $$

This leads to an $O(n)$ algorithm (in the appropriate computation model). I'll let you work out the remaining details.

# Answer
> 7 votes
Here's a hint: if $n$ can be represented as the sum of $2k+1$ consecutive integers, and if the middle of those consecutive integers is $m$, then what can you say about the relationship between $n$, $k$, and $m$? Now, given $n$, can you determine whether it is expressible as the sum of an odd number of consecutive integers?

# Answer
> 4 votes
Here's a $O(\sqrt n)$ algorithm. We want to find all length-$k$ expressions for which $$ n=a+(a+1)+(a+2)+\cdots+(a+(k-1)) $$ Rearranging terms, we require $$ n=\sum\_{i=0}^{k-1}(a+i) = \sum\_{i=0}^{k-1}a+\sum\_{i=0}^{k-1}i=ka+\frac{k(k-1)}{2} $$ and so we must have $$ n=k\left(\frac{2a+k-1}{2}\right) $$ for some $a$ and $k$. If $k$ is even we require $$ n=\left(\frac{k}{2}\right)(2a+k-1) $$ and so $n$ must be divisible by $k/2$. If $k$ is odd, we'll have $2a+k-1$ even, so $n$ must be divisible by $k$.

That means that the possible solutions will only be those for which $k$ is odd and $k\mid n$ or $k$ is even and $(k/2)\mid n$. Now that we know that we're looking only for divisors of $n$, we'll have candidate pairs $k$ and $n/k$ for those $k\le \sqrt{n}$ if $k$ is odd and $k\le 2\sqrt{n}$ if $n$ is even. That means we can find all solutions by checking at most only the $k\le2\sqrt{n}$. Since each check involves nothing more than a constant number of steps, we can find all the solutions in time $O(\sqrt{n})$.

Let's look at your example, with $n=15$:

1. ($k=1$). We have $15 = 1\cdot(2a+1-1)/2$ so $a=15$, giving the sum `15=15`. The other solution will be when $k=15$, giving an impossible solution.
2. ($k=2$). We have $15=(2/2)(2a+1)$ and so $a=7$, giving the solution `15=7+8`. The companion solution, where $k=15/1$ is impossible, again.
3. ($k=3$). We have $15=3\cdot(2a+2)/2$, so $a=4$, giving another solution `15=4+5+6`. The companion solution, when $k=15/3=5$ gives $a=1$, which yields the solution `15=1+2+3+4+5`.
4. ($k=4$). Since $4/2=2$ doesn't divide 15, there is no possible solution.
5. ($k=5$). Since $5\>\sqrt{15}$ we can stop looking at odd candidates.
6. ($k=6$). $6/2$ divides 15, but we've already considered that solution. There are no further even numbers to consider, and so we stop trying, having found all the possible solutions.

# Answer
> 2 votes
You can replace your second "for" loop with binary search, since you can calculate sum of arithmetical progression by formula. I mean traverse all possible values of lengths and try to find starting value by binary search, it replaces second $N$ with $log(N)$

I found my old $O(NlogN)$ code where $N$ is the maximal length of representation $1+2+...+N$. It searches the lenght of this representation.

```
int ans = 1, n; cin >> n;
    for(int len = 2; len <= 32000; len++)
    {
        int l = 1, r = n/2;
        while (l <= r)
        {
            int mid = (l+r)/2;
            __int64 cur_sum = (2*mid + len - 1) * 1LL * len / 2;
            if (cur_sum == n) { ans = len; break; }
            if (cur_sum < n) l = mid+1;
            else r = mid-1;
        }
    }
    cout << ans;

```

I'm not sure it works ok on all cases, currently I'm writing binserach differently, but the idea is clear I think.

---
Tags: algorithms, search-problem, integer-partitions
---


# Question
Title: Is my grammar correct for this context-free language?
$\\{a^nb^2a^n \mid n \ge0\\}$

I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between.

I came up with the following grammar, but I think it accepts strings that it should not such as: $abb, bba$, etc.

$$\begin{align} S&\rightarrow X\\ X&\rightarrow XbbX \mid \epsilon\\ A&\rightarrow aA \mid \epsilon \end{align}$$

# Answer
In dealing with CFGs, it's often useful to work from the inside out. Clearly $$ S\rightarrow aSa $$ will generate all strings of the form $a^nSa^n$, for $n\ge 0$. Then all you have to do is allow the possibility that $S$ will also eventually generate $bb$, which we can do by the production $S\rightarrow bb$, giving the grammar $$ S\rightarrow aSa\mid bb $$ or, if you wanted to be explicit about the $bb$ central part, you could write $$\begin{align} S&\rightarrow aSa \mid T\\ T&\rightarrow bb \end{align}$$ The problem with your grammar is that it can't guarantee that there will be the same number of $a$s on each end of a generated string.
> 3 votes

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


# Question
Title: What is the maximum achievable throughput in this communication using sliding window protocol?
Station A is sending data to station B over a full duplex error free channel. A sliding window protocol is being used for flow control. The send and receive window sizes are 6 frames each. Each frame is 1200 bytes long and the transmission time for such a frame is 70 μS. Acknowledgment frames sent by B to A are very small and require negligible transmission time. The propagation delay over the link is 300 μS. What is the maximum achievable throughput in this communication?

# Answer
To compute the throughput we need to check the performance of the system in long term, not just at the starting. Thus we need to find a regular pattern of the transmission that will be repeated for infinitely many times.

Here you didn't mention the details of sliding window protocol, thus I'll assume the worst case scenario. I assume that the receiver don't send the ACK until it gets all of the 6 frames.

The first bit will be reached to the receiver after 300 $\mu$S. After 70 $\mu$S the first packet will be reached. And the other five packets would take 350 $\mu$S more. Then the receiver will send the ACK that will take 300 $\mu$S to reach to the sender. Sender can start transmission only after getting this ACK and a new cycle starts. This pattern is repeated for ever.

Now, you can see only productive time in this 300+420+300 $\mu$S interval is 420 $\mu$S. Hence the throughput is 420/1020 = .41
> 1 votes

---
Tags: computer-networks
---


# Question
Title: What is the difference between turing reductions and many-one reductions?
To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is $C$-complete and the complexity of the reduction is asymptotically less than the upper bound of the complexity class (I just made this up, but it seems to be the case for the reduction to be at all useful; can someone verify?). Restrictions with respect to resource usage make sense to me: Why would anyone need to reduce a problem $B$ to some other problem $A$ if the computation of the reduction is greater than or equal to the computation of $B$?

However, I am taught that such reductions (showing that something is $C$-complete) *must* be of the **many-one** kind. Assume we are only talking about decision problems. Why does it matter how the reduction is done, as long as it proves whatever we are trying to prove (i.e. $A$ is $C$-Complete)?

Below are some statements I've established from my studies. Some are incomplete (I have not proven all of them), but my intuition tells me that all of these statements ought to be true. Can someone please confirm/correct my statements below?

* **Show A is decidable**
    + Construct a decider $M'$ of $A$ using a machine $M$ for decidable language $B$. This reduction does not turn instances of $A$ into instances of $B$, but it still decides $A$, so we say this is a Turing reduction from $A$ to $B$.
    + Give a many-one reduction from $A$ to $B$. This will show that $A$ is decidable, albeit overkill.
* **Show A is undecidable**
    + For some known undecidable language $B$, Give a Turing reduction from $A$ to $B$.
    + For some known undecidable language $B$, Give a many-one reduction from $A$ to $B$ (**is this impossible?**).
* **Show A is recognizable**
    + For some recongizable language $B$, give a reduction from $A$ to $B$.
    + Give a T.M. $M$ that accepts strings in the language of $A$; $M$ is not required to reject strings not in $A$ (it may never halt).
    + Show its complement $\overline{A}$ is decidable.
    + Show that $A$ is decidable.
* **Show $A$ is unrecognizable**
    + Show that $A$ and $\overline{A}$ are both undecidable.
    + Are there any other ways to show a language is unrecognizable?.
* **Show $A$ is $C$-complete**
    + Show $A \in C$, and for some known $C$-complete language $B$, give a reduction $B \leq\_m A$.
        - The reduction $R$ must meet the following restriction: If the complexity class $C$ has upper bound $f(x)$ on resource $S$ for some positive quantity $x$ of abstract machines that decide languages in $C$, then $g(x)$ measures the $S$-complexity of $R$ such that $g(x) \in o(f(x))$.
        - I'm not entirely comfortable with this definition, because, well, $PSPACE$-complete reductions are only required to have polynomial running time. In this case, I think any polynomial-time algorithm has space-complexity asymptotically less than $PSPACE$.
        - This line of reasoning doesn't add up either, because it is not known that $P \subset PSPACE$ (help?).

In general, it seems anywhere a many-one reductions is used, a Turing reduction may be used, but I'm not sure if the opposite is true. This is where my question about undecidability comes in: Can a many-one reduction be used to show that a language is undecidable? If this were possible, what would it imply?

# Answer
> 7 votes
You got it backwards. Turing reductions are *more general* than many-one reduction. A many-one reduction is also a Turing reduction, but some Turing reductions are not many-one reductions. This is provably the case for (arbitrary) computable reductions. For example, there is a Turing reduction from the halting problem to its complement, but no such many-one reduction.

Completeness is defined with respect to many-one reductions since it allows making finer distinctions. Turing reductions, for example, don't allow us to distinguish the halting problem from its complement, or NP from coNP, but many-one reductions do.

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


# Question
Title: A binomial random number generating algorithm that works when $Np$ is very small
I need to generate binomial random numbers:

> A binomial random number is the number of heads in $N$ tosses of a coin with probability $p$ of a heads on any single toss. If you generate $N$ uniform random numbers on the interval $(0,1)$ and count the number less than $p$, then the count is a binomial random number with parameters $N$ and $p$.

In my case, my $N$ could range from $10^3$ to $10^{10}$ and my $p$ is around $10^{-7}$. Often my $Np$ is around $10^{-3}$.

There is a trivial implementation to generate such binomial random number through loops:

```
getBinomial(int N, double p):
  x = 0
  repeat N times:
    if getUniformRandom() < p: # getUniformRandom() returns a real number in (0,1)
      x = x+1
  return x

```

This naïve implementation is very slow, $O(N)$. I tried the Acceptance Rejection/Inversion method \[1\] implemented in the Colt (http://acs.lbl.gov/software/colt/) lib. It is very fast, but the distribution of its generated number only agrees with the naïve implementation when $Np$ is not very small. In my case when $Np = 10^{-3}$, the naïve implementation can still generate the number 1 after many runs, but the Acceptance Rejection/Inversion method can never generate the number 1 (always returns 0).

Does anyone know what is the problem here? Or can you suggest a better binomial random number generating algorithm that can solve my case?

\[1\] V. Kachitvichyanukul, B.W. Schmeiser (1988): Binomial random variate generation, *Communications of the ACM* 31, 216-222.

# Answer
If $Np$ is small then the distribution is very close to Poisson, which is easier to generate, especially when the expectation is small.

In your specific case, most of the time the result is zero, and the probability that this happens can be calculated exactly. This optimization will probably result in a speed-up of $10^3$.
> 1 votes

---
Tags: algorithms, pseudo-random-generators
---


# Question
Title: Number of Final States Subset Construction for NFA to DFA
**"Suppose we use the subset construction to convert a $7$-state NFA $M = (Q,\Sigma, \delta, q\_0, F)$ into a DFA $M' = (Q', \Sigma, \delta', q\_0, F')$ for the same language. Then $M'$ will have $|Q'| = 128$ states. If $|F| = 2$, then $M'$ will have $|F'| = 96$ final states."**

From the subset construction, I know there are $\mathcal{P}(Q)$ new states in the machine, which means there are $2^7 = 128$ new states in $M'$. I am not sure mathematically why there are $96$ final states.

**Observations:**

I see that if I have an initial NFA with $3$-states $\\{1,2,3\\}$ and a $|F| = \\{1\\}$, then $P(\\{1,2,3\\}) = \left\\{ \emptyset, \\{1\\}, \\{2\\}, \\{3\\}, \\{1,2\\}, \\{1,3\\}, \\{2,3\\}, \\{1,2,3\\} \right\\}$. I can also note that there are now $4$ final states and can conjecture $|F| = 2^{n} - 2^{n-k} = 2^{3} - 2^{3-1} = 4$, where $k$ is the number of final states. I also notice that each particular state occurs $2^{n} - 2^{n-k}$ times in the construction.

However, if I let there be $2$ final states (say $\\{1,2\\}$) in the initial machine, the new machine will have $5$ final states, not $2^3 - 2^{3-2} = 6$. I can see this is because $\\{1,2\\}$ is a state that contains both elements, and is being double counted.

I would prefer simple well-written intuitive answer rather than an overly mathematical one.

# Answer
> 4 votes
Think about which states in the new NFA *don't* contain a state that was in $F$. These are $\emptyset$ and every combination of states from $\mathcal{Q}-F$, i.e. $\mathcal{P}(\mathcal{Q}-F)$.

In your 3-state example, the only elements of $\mathcal{P}(\\{1,2,3\\})$ that don't contain 1 or 2 are $\emptyset$ and $\\{3\\}$, which constitute $\mathcal{P}(\\{3\\})$, with cardinality 2, so we have $\mid F'\mid=8-2=6$.

For your 7-state example with $\mid F\mid=2$, the size of $\mathcal{P}(\mathcal{Q}-F)$ is 32, which means there are $\mid F'\mid=128-32=96$ states that *also* contain at least one state that was in $F$.

So your conjecture of $2^{\mid F\mid}-2^{\mid\mathcal{Q}-F\mid}$ is correct.

---
Tags: finite-automata
---


# Question
Title: Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation
I'm trying to proof/refute the following equation:

$$n^n = \Omega(n!)$$

Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem.

$$\lim\_{n\to \inf}{{f(n)}\over{g(n)}} = K$$

However, in this case $n!$ is somewhat of a party-stopper. I found Stirling's approximation which states that:

$$n! \approx \left(\frac{n}{e}\right)^n\sqrt{2πn} $$

My idea was therefore:

$${n^n}\over{(\frac{n}{e})^n\sqrt{2πn}}$$ $${n^n}\over{\frac{n^n}{e^n}\sqrt{2πn}}$$ $${e^n}\over{\sqrt{2πn}}$$ $$\lim\_{x\to \infty}{{e^2n}\over{2πn}} = \infty$$

$$ 0 \< K \leq \infty $$

therefore the original equation is true.

Is that approach "ok", did I understand Stirling's approximation correctly?

# Answer
> 4 votes
Stirling's approximation states that $$ n! \sim \sqrt{2\pi n} (n/e)^n. $$ This notation means that the ratio between the two sides tends to 1 as $n$ tends to infinity. For your purposes, we can simply write $$ n! = \Theta(\sqrt{n} (n/e)^n). $$ Since $\sqrt{n} = o(e^n)$, $$ n! = o(n^n). $$

If all you want to show $n! = O(n^n)$, then as Jukka mentions you can use the simple bound $n! \leq n^n$.

---
Tags: asymptotics, check-my-answer
---


# Question
Title: Hash tables - probing for collisions run time
The question is a true or false question:

**Hash tables using probing for collisions run in constant time with respect to how many items are in the hash but are at least linearly dependent on how full the hash is.**

I think it's true but I don't fully understand why and I don't understand the term linearly dependent.

Any help would be great, thanks.

# Answer
> 0 votes
The average number of positions addressed is $$ \frac{1}{2} \left(1 + \frac{1}{1-\alpha}\right) $$ for linear probing and $1 + \alpha/2$ for chained hashing. Here $\alpha$ is the load factor. For each constant $\alpha$, this average is constant, but it depends on $\alpha$. The expression $1/(1-\alpha)$ blows up as the table gets full ($\alpha \to 1$), which is probably what is meant by *the dependence is at least linear*. The dependence is on the load factor rather than on the absolute number of elements in the table, which is not the deciding factor.

Usually, a *linear* dependence (not to be confused with the same terminology from linear algebra!) would be $\Theta(\alpha)$, at least linear would be $\Omega(\alpha)$, and more than linear $\omega(\alpha)$; but here $\alpha \to 1$ rather than $\alpha \to \infty$ so terminology is not standard. Perhaps the correct variable, which does go to $\infty$, is $1/(1-\alpha)$. In this case, we do have linear dependence for linear probing.

---
Tags: algorithms, algorithm-analysis, hash-tables
---


# Question
Title: Practical importance of interval / circular-arc graphs in resource allocation
A graph is called a circular-arc graph if each of its vertices can be assigned to a circular arc such that two vertices are adjacent iff their respective arcs have a non-empty intersection. Analogously, a graph is an interval graph if we can assign each of its vertices to intervals on a line in the above fashion. Note that interval graphs are a subclass of circular-arc graphs.

Wikipedia states that interval/circular-arc graphs are important in the modeling of (periodic) resource allocations problems in operations research. Can you provide a concrete example of such a problem and how it is modeled to CA/interval graphs? The problem should conceivably occur in practice.

# Answer
Making Louis' comment into an answer:

Given a set of intervals (interval system) $\mathcal{I} = \\{ \[x\_1, x\_2\] ,\dots, \[x\_{2n-1}, x\_{2n}\] \\}$. Each of the $n$ intervals corresponds to the time period a certain job is being worked on. Now, we want to find all time periods in which the number of concurrently active jobs is maximal. These time periods happen to correspond to the maxcliques of maximal size of the intersection graph $G(\mathcal{I}) = (\mathcal{I} , E)$ with $E$ being defined as $$ (\[a,b\] , \[c,d\]) \in E \iff \[a,b\] \cap \[c,d\] \neq \emptyset $$ The closed neighborhood of a vertice $v$ in a graph $G$ is defined as $$ N\[v\] := \\{ u \in V(G) : \\{v,u\\} \in E \\} \cup \\{v\\}$$ It is known that for any interval graph every maxclique can be characterized as the intersection of two neighborhoods, i.e. for each maxclique $C$ of $G$ there exist some $u,v \in V(G)$ s.t. $C = N\[u\] \cap N\[v\]$.

With this we can easily devise an efficient algorithm to find the wanted time periods.

If you have any other answers along these lines I'd be happy to hear them.
> 2 votes

---
Tags: graphs
---


# Question
Title: Logic applications and security protocols references request
I'm a student of logic and I'm interested in looking at logic applications, of which I am told there are many, in computer science and allied areas. I've seen some applications. More specifically, I keep seeing little things about security protocols which use logical methods. I'd like to learn some more about this material, although I suspect it may require I obtain a knowledge of networks and cryptography which I currently lack (although hopefully not for long!). I have recently obtained Ryan and Schneider's textbook on Security Protocols.

Are there any other suggestions for reading and self-teaching in this and / or other areas in computer science which use logical techniques / formal methods? (I expect there are many; just looking to be pointed in a couple of amenable directions which are reasonable for someone who knows some pure logic.)

# Answer
I really like the phrase, as well as the book, that logic is calculus of computation. It is kind of hard to find an area in computer science where logic is not used. I will just mention few areas where knowing logic *comes in handy*.

1. **Verification**. Techniques of logic are heavily used in verification area. Specification of hardware and software systems is usually given as logical formulas. Depending on what properties are being checked, such systems are also modeled by appropriate logic (propositional, FOL, modal logics, linear logic, etc.). Methods like satisfiability and model checking are usually used to check whether a system meets its specification. Moreover, there is an area of decision procedures that tries to come up with efficient procedures for checking satisfiability of formulas in various logics (by most first order theories). In general, you might want to take a look at automated theorem proving.
2. **Programming languages**. As pointed earlier, there is a deep connection between programming languages and logic. By Curry-Howard isomorphism, every functional program is isomorphic to some proof in constructive logic. Logic is also used for defining axiomatic semantics of programming languages; see Hoare logic. Prolog is a programming language based on a paradigm where computation is specified by logical formulas. Lambda calculus was first intended as a formal logical system aimed to laying foundations of mathematics, but turn out to be more useful as a programming language. It is now at the core of every functional programming language.
3. **Misc**. You might also be interested in the way logic and computability interplay. What might be specially interesting to you is descriptive complexity. Logic is also getting more attention in computational biology. It is also used in AI for knowledge representation.

Hope this gives you some kind of a starting point.
> 2 votes

---
Tags: logic, formal-methods, security, applied-theory
---


# Question
Title: Studying Skiena. War Story: What’s Past is Prolog
I am reading The Algorithm Design Manual, 2nd Edition. The book gives an example task and then explains how to solve it step by step. (The task and solution is detailed here)

*But I don't follow one step from the solution. That step doesn't contain enough details for me so I don't understand it. I'm asking if someone can explain it.*

**Below I rewrote the task in a shorter form than in the book:**

Given n ordered strings (lets call them rules) of m characters. The strings are indexed starting from 1 (not 0)

The goal is to construct the trie with the minimum possible number of edges. The leaves of the resulting trie (each leaf represents a string) have to be in the same exact order as the given collection of strings.

We are free to pick an arbitrary character position on each step of constructing the trie (e. g., we are free to start constructing the trie from character position 2 as opposed to starting from 1). Thanks to this ability we can minimize the built trie. Lets call picking a character - probing.

Example:

From the four rules below it's possible to build different tries depending on the order of picking characters from the strings.

`S1: (a,a,a)
S2: (b,a,a)
S3: (c,b,b)
S4: (d,b,b)`

The book says that

> Probing at the p-th position, 1 \<= p \<= m, partitioned the rules into runs R1,...,Rr, where each rule in a given run Rx = Si,...,Sj had the same character value of Si\[p\].
>
> Since the rules were ordered, each node in the subtree must represent the root of a run of consecutive rules, so there were only ${{n}\choose{2}}$ possible nodes to choose from for this tree...
>
> ...
>
> The rules in each run must be consecutive, so there are only ${{n}\choose{2}}$ possible runs to worry about.

**My question: How does the fact the rules are consecutive lead to the inference that there are ${{n}\choose{2}}$ possible nodes/runs after probing at the p-th position?**

# Answer
Each (non-trivial) run is given by two (different) indices, marking the beginning and end of the run, so if the sequence is of length $n$, there are $\binom{n}{2}$ possible runs. If we only consider *maximal* runs, there are at most $n$ (or even less, if we don't consider trivial runs).
> 1 votes

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


# Question
Title: Sorted array with odd indexed elements swapped randomly
> A sorted array $\mathcal{A}$ with **even** number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}\_1, \mathcal{A}\_2$) contain equal number of elements. We choose some arbitary **odd indexed** (index with $1,5,9$ etc.) elements from $\mathcal{A}\_1$ and swap them with some other random **odd indexed** elements of $\mathcal{A}\_2$. **Even indexed** elements of $\mathcal{A}$ remain untouched.

We need to device an algorithm to check whether an element $\mathcal{x}$ exists in $\mathcal{A}$ in $O(\log n)$ time.

# Answer
> 2 votes
Hint:

1. Use binary search to find the possible locations of $x$ in the original array.
2. If you find two even elements $y,z$ with $y\<x\<z$ and the element between them $w$ is does not belong there, then $w$ might have been switched with $x$. Find the proper position of $w$ using binary search and look if $x$ is there.

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


title: Decision Tree and rank?

text:
# Question
Title: Decision Tree and rank?
Consider all strictly decreasing functions from {1,2,3,4} to {1,2,3,4,5,6}, or in other words, all functions defined on {1,2,3,4} such that f(1)\>f(2)\>f(3)\>f(4). Draw a decision tree so that the leaves are in lexicographical order when read from left to right. Then answer the following questions:

(a) What is the rank of 5431?

(b) What function has rank 0?

I have been looking all over the internet but I could not find a good resource for decision tree. I would be very appreciate it if anyone could show me how to approach this problem. Thanks

# Answer
The decision tree implements the following algorithm for finding $f$:

1. What is $f(1)$?
2. What is $f(2)$?
3. What is $f(3)$?
4. What is $f(4)$?

There are six possible answers to the first question, but only three of them lead to a valid function. You split according to these answers in the correct order (you want the result to be in lexicographic order), and then continue to the second question. And so on. If you did everything correct, you'll find $\binom{6}{2} = 15$ different leaves, the *last* of which is $6543$.
> 2 votes

---
Tags: decision-problem
---


# Question
Title: Is there a largest class of halting programs?
The halting problem says that a Turing machine cannot decide if another Turing machine halts.

However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO statements are simple to formally verify. FORTRAN is however not Turing complete.

What is the largest subset or class of halting programs that can be decided? Is there a class of such languages?

This blog entry seems to hint at the fact that since the compiler optimized the code by eleminating the while(1) loop, Fermat's last theorem is disproved by a compiler.

# Answer
There is no largest class of programs which have a decidable halting problem. If $L$ is such a class and $P \notin L$, then the class $L \cup \\{P\\}$ also has a decidable halting problem (why?). (This works since the class of *all* programs does not have a decidable halting problem.)

Responding to Raphael's comment, there is also no largest class of programs, *up to finitely many exceptions*, with a decidable halting problem. For each program $P$, let $L(P)$ be some infinite decidable set of programs equivalent to $P$ (for Turing machines, we can add dummy unreachable states, for example). Let $L$ be a class with decidable halting problem. I claim that there must be some $P$ such that $L(P) \cap L = \emptyset$. Otherwise, we could decide the halting problem for an arbitrary program $P$ by enumerating $L(P)$. Given a program $P$ such that $L(P) \cap L = \emptyset$, we can obtain a decider for $L \cup L(P)$, so that $L$ has infinitely many exceptions.
> 6 votes

---
Tags: computability, complexity-classes, halting-problem
---


title: Dynamic programming rectangular grid

text:
# Question
Title: Dynamic programming rectangular grid
You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs.

How to find out the minimum number of slabs required to cover all the points which have a value 1?

NOTE: The 1x40 slabs can overlap with each other.

# Answer
> 1 votes
I'm assuming you're only allowed to use the 1x40 slabs horizontally or vertically. They thus cover entire rows or columns. We can rephrase your problem as *minimum vertex cover* in a bipartite graph. The bipartite graph consists of 40 *row* vertices and 40 *column* vertices. Connect two vertices if the corresponding point in the grid is 1. The minimum number of slabs needed to cover all 1s is exactly the minimum vertex cover in this bipartite graph. In bipartite graphs, minimum vertex cover equals maximum matching, so the problem is algorithmically feasible. In order to find a concrete algorithm, just look for algorithms for solving minimum vertex cover on bipartite graphs.

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


# Question
Title: Reduction from partition to multiprocessor scheduling
I am kind of unsure about a reduction between two problems. Here are the two problems:

**PARTITION:** Instance: A finite set of n positive integers $S= \\{a\_1,a\_2,...a\_n\\}$. Question: Can the set $S$ be partitioned into two subsets $S\_1$,$S\_2$, s.t. the sum of the numbers in $S\_1$ equals the sum of the numbers in $S\_2$?

**MULTIPROCESSOR SCHEDULING:** Instance: A set $J$ of $k$ jobs where job $j\_i$ has length $l\_i$, and $m$ processors. Question: Can we schedule all jobs in $J$ on $m$ processors s.t.: **(a)** on each processor the next job in the sequence is started immediately after the preceding job is finished and **(b)** the total time to execute all jobs on each processor takes the minimum possible time $T\_{min}=\big(\sum\limits\_{i=1}^k l\_i\big)/m$

I am a little bit unsure about my try to reduce Partition to multiprocessor scheduling. My attempt is posted as an answer.

# Answer
(This is the answer that the OP wanted to have checked.)

Let $S=\\{a\_1,...,a\_n\\}$ be an arbitrary instance of Partition. In our reduction we set $J=S$. if $\sum\limits\_{a \in S} a$ is even, we set $m=2$. Note: If the sum of elements in $S$ is odd, there cannot be a Partitioning. Further, we set the length $l\_i$ of job $j\_i$ to the value of $a\_i$.

So this is my reduction. But I am very unsure if this is just too easy? Note that I do not have to provide the correctness proof but just the reduction. Is this somehow a right reduction? I am very unsure if I have to distinguish between the two cases where the sum of elements of $S$ is odd or even. What if the sum is odd?

Can someone give me some hints on that?
> 0 votes

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


# Question
Title: Computing FOLLOW sets for a LL(1) grammar
I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word.

Given the grammar:

```
S-> ABC
A-> Aa|b
B-> Bc|d
C-> Ce|f

```

I've come up with the following first and follow sets:

```
1 S->ABC   First(1)-{b}
2 A->bA'   First(2)-{b}
3 A'->aA'  First(3)-{a}
4 A'->E    Follow(4)- ??
5 B->dB'   First(5)-{d}
6 B'->cB'  First(6)-{c}
7 B'->E    Follow(7)- ??
8 C->fC'   First(8)-{f}
9 C'->eC'  First(9)-{e}
10 C'->E   Follow(10)- ??

```

Please help me determine the follow sets I've indicated with `??`. Is there a formula I can use to determine the follow sets?

# Answer
The follow set of something translates to asking: what symbol can come next in the string we are trying to read with the grammar rules the machine has?

Let's say we take a string `"abba"`. The input tape symbol will end the string with `$` as the delimiter. So we can say that `'a'`, `'b'`, `'b'`, `'a'` and `'$'` are the symbols that the read/write head of the parser will see while evaluating this string. I am taking the below production rules for this grammar.

```
S->AB
A->ab|a
B->baB|E

```

The string `"abba"` can be evaluated in the following manner:

```
S->AB
 ->abB
 ->abbaB
 ->abbaE

```

In the above case, `Follow(A) = {b,$}`.

`'b'` is part of the set because `B`'s production follows `A`'s production, `S->AB`, and whatever is the first letter that `B` produces will follow the last letter `A` produces.

Similarly, `$` is part of the set because of `B`'s epsilon production. When `B` is evaluated using rule `B->E`, then for `Follow(A)` there is no first letter produced by `B`.

In such a case where the `Follow(A)` is an epsilon production,

```
S->AE | using B->E

```

Then `Follow(A)` becomes `Follow(S)` which is `$`.

If you look at the string `"abba"`, once the last a is read the only symbol that can come after the string is `$`.

As a generalization, if `X->ABC` and `C->E`, then `Follow(B) = Follow(X)`.

In your question's example, evaluating `Follow(A')` results in only two possibilities where `A'` is on the RHS and can have a following symbol. Below are the two productions that can result:

```
A->bA'
A'->aA'

```

Unfortunately, out of the two one is `Follow(A') = Follow(A')` as per the rule I have mentioned in last line of the answer.

Hence we can only consider the other follow which is

```
Follow(A') = Follow(A)

```

i.e.

```
Follow(A) = First(B)

```

In a practical sense, if we have

```
S->ABC

```

and

```
A-> bA'
A'->aA'|E

```

Then whenever we have an A production, it will further lead to either `A -> baA'` or `A->b` (if we take `A'->E`).

In both cases the only thing that can follow `A'` is whatever is the first of `B`.

In a similar manner we can compute the same for `Follow(B')` and `Follow(C')`.
> 1 votes

---
Tags: formal-grammars, compilers, parsers
---


title: Denumerably many isomorphism types

text:
# Question
Title: Denumerably many isomorphism types
Computability and Logic by Boolos and Burgess says that formula $\Gamma\_d$ in example 12.12

```
∀x∀y(∃u(u ≠ x ∧ u ≡ x) ∧ ∃v(v ≠ y ∧ v ≡ y)) → x ≡ y)

```

supports models, whose domain is partitioned into equivalence classes of any size, e.g.

is possible. Yet, I do not understand how this is possible. Suppose my x is the first dot. Then, I can find u, which is the second dot. Similarly, let y be the first dot in the second equivalence class and another dot v is in its companion in the eqivalence class. The formula says that x and y must be in the same equivalence class. But they are obviously not!

Are they trying to cheat me?

# Answer
They are not trying to cheat you. You need to read the text of Example 12.12, following the formula. It says:

> A denumerable model of $\Gamma\_d$ will consist of a denumerable set $X$ with an equivalence relation in which any two elements $a$ and $b$ that are not isolated, that is, that are such that each is equivalent to something other than itself, are equivalent to each other.

Thus $x$ and $y$ in your example must be equivalent in the model, and the picture is not an accurate representation of what $\Gamma\_d$ captures.
> 3 votes

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


title: Find MST based upon new definition

text:
# Question
Title: Find MST based upon new definition
Redefine the weight of a spanning tree to be the weight of the maximum weight edge in the tree (i.e. the weight of the tree is no longer the sum of the weights of all the edges in the tree, only the weight of the edge with the maximum weight). How would you derive an efficient algorithm to compute the minimum weight spanning tree under this new definition? Do not assume the edge weights are distinct.

A brute force approach would obviously be to compute all possible MSTs, then sort them based on their maximum weighted edge, and choose the smallest one. This is not efficient however, but I am having trouble seeing how to do this. Any ideas?

# Answer
Every MST according to the original definition is also optimal according to your new definition. (The proof of this statement is left as an exercise; it is not that hard.) So any MST algorithm will do the job.
> 2 votes

---
Tags: algorithms, graphs, trees, spanning-trees
---


title: Zigzag subsequence

text:
# Question
Title: Zigzag subsequence
As part of a homework assignment I'm asked to describe an O(mn) algorithm to find the length of the longest zig-zag sub sequence. The overall topic for this assignment is dynamic programming. As described in chapter 15 of CLRS.

A zigzag pattern is for example (2, 4, 1, 4) or (1, 2, 1) or (6, 1, 3, 2). While (1, 2, 3) and (4, 3, 2) are not. But the input could be (1, 2, 1, 1, 4, 1) which should result in (1, 2, 1, 4, 1). But for now the number of elements denoting the longest zig-zag sub sequence is simply stored at the end of the subl array.

Below is my attempt at an algorithm. I'm trying to use a bottom up approach.

```
zigzag(A)
    signs[] ={0}
    subl[] = {1}
    for i= 1 to n
        for j = i - 1 downto 0
            sign = signs[j]
            if sign = 0 OR (sign<0 AND A[i] - A[j]>0) OR (sign>0 AND A[i] - A[j]<0)
                subl[i] =subl[j] + 1
                signs[i] =A[i] - A[j]
                break

```

As far as I can analyse the outer for loop runs n times and the inner loop also runs at most n times. Which means that my algorithm actually is mn = nn = n^2. However I'm somewhat worried because my algorithm looks a lot like bubble sort.

# Answer
You haven't defined your notation, but if $m\<n$, then an $O(n^2)$-time algorithm (like yours) isn't necessarily a $O(mn)$-time algorithm. So, depending upon the definition of $m$, your algorithm might be too slow.

(Think about the case where $m=7$ or where $m=\sqrt{n}$, for instance.)
> 1 votes

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


# Question
Title: Predicting target location given cursor speed and direction
Do you guys know of any method or algorithm you are able to predict where a user is moving their cursor given its speed and bearing?

I'm trying to predict if and when users are moving their mouse to a certain part of the screen (address bar location).

Could I exploit Fitts's Law in this regard?

# Answer
> 1 votes
Fitts's law gives you a guess for the length of the movement (in terms of screen distance), and so gives you a rough spot where the user is aiming. Make a list of "points of interest" where the user is likely to click (a priori), and then put together a score which takes into account both the probability that the movement ends at the point, and its prominence. Pick the point with maximal score.

Machine learning has been used to derive the parameters for Fitts's law, and I'm not sure anything more is needed here apart from some UI experiments.

---
Tags: algorithms, hci
---


# Question
Title: Red black tree partition to $\sqrt{n}$ trees
This is a question I have stumbled upon in an old Algorithms test I found online:

> A) Plan an algorithm that does the following: Input: Red-Black tree Output: $\sqrt{n}$ seperate trees, so that every tree has $\sqrt{n}$ nodes. What is the complexity of the Algorithm you planned? must show analysis.
>
> B) Assume that you have started from an empty Red Black tree, and that the input is a set of nodes and not a Red Black tree. Show how can you make a more efficient algorithm of partitioning the nodes to $\sqrt{n}$ Red Black trees so that every tree has $\sqrt{n}$ nodes. What is the complexity of the new Algorithm you planned and how does it affect existing Red Black tree functions? must show analysis.

Now I have answered A and I am pretty sure that's the best answer there is, but I need your help in telling me if I can do better. This is without analysis:

> Algorithm: 1. Scan the Red Black tree using In-Order traversal to build a sorted array out of it. \< \> O(n). 2. Divide the array to $\sqrt{n}$ sub-arrays and build a Red Black tree out of every sub \> array - O(n) total.

Now what I don't really understand is how do I solve B. I'm not exactly sure if the input in B is a Red Black tree or just a set of nodes, so both will be acceptable if you want to share your answer to B with me. I have asked a student and he told me that the complexity that I should get in B is $O(\sqrt{n}\*log(n))$.

I need help reaching that, or maybe something better (hints and stuff).

# Answer
For question B) you need to make $O(\sqrt{n})$ RB trees from $n$ nodes (there is no tree to start with just bunch of nodes). Thus you need to process each node at least once. Thus time complexity of this building should be $\Omega(n)$. Thus I think there is no hope of getting the $O(\sqrt{n}\log n)$ bound.
> 3 votes

---
Tags: algorithms, trees
---


# Question
Title: Are there algorithms or circuits that can implement addition without the need for carry flags
Let two numbers $x,y$ be represented in some digit form (binary, octal, ...): $(x\_1 x\_2 x\_3 \ldots)$ and $(y\_1 y\_2 y\_3 \ldots)$.

Can we add those numbers such that we do not need to carry over: $x\_i = x\_i+y\_i + c(x\_{i-1},y\_{i-1})$ where $c(x\_{i-1},y\_{i-1})$ is the carry value of $x\_{i-1}$ and $y\_{i-1}$.

Are there $O(1)$ step circuit implementations of addition that exist? Are they practical?

In other words, is addition inherently recursive over the number of digits?

# Answer
For non-redundant representations like $(x\_n, x\_{n-1}, ..., {x\_1})$ the recursion is fundamental (although the operator is associative so you can apply the prefix sum optimization to parallelize the operation down to $O(\lg n)$ steps.)

But there are redundant representations where addition can be performed more efficiently, in some cases. The carry-save adder is used in most hardware multiplier implementations, where you need to sum together a large list of numbers.

The redundant representation is just to represent every number by two subsums:

```
c3 c2 c1
x3 x2 x1 x0

```

so, for example, the number "5" can be stored either as:

```
 0  0  0
 0  1  0  1

```

or

```
 0  0  1
 0  0  1  1

```

The "addition" operation adds three subsums and produces two subsums:

```
 0  0  1
+0  0  1  1
+0  0  0  1
-----------
 0  1  1  0
 0  0  0  0

```

So, not very useful if you are just adding two numbers, but when you need to sum a whole list of numbers, each individual addition is fast, and then only at the end do you have to convert back to a non-redundant representation.

There are other redundant representations used in hardware multiplication algorithms, like Booth encoding where the digits can be positive, zero or negative.
> 5 votes

# Answer
For every length of x you can create an adder that will calculate the addition in "one step", actually two (and+or) in BNF, but if you have larger numbers combined of several x you will need to carry over the result for each step.

Interesting are maybe analogous adders, where you convert your number to voltages, add those and convert the result back and also those (don't remember the name) where every digit of the number counts as 1 and you adding two numbers, e.g. 3+4 = 111+1111 gives you 1111111 = 7,
> 0 votes

---
Tags: arithmetic, binary-arithmetic
---


# Question
Title: Maximum amount of memory that can be allocated to a process
DISCLAIMER: The following scenario was taken from an assignment I got in a OS course I'm taking, and it arose a lot of question marks in my head. However non of the questions asked by myself here reflects a question that I'm supposed to answer (alone) as part of the assignment. What I mean is: I'm not asking you to do my HW I'm just asking for help to better understand the concepts.

Given the following scenario:

- A system using paging for memory management.
- Physical memory size is 128MB
- There are 4K frames in physical memory and each frame has 8K words.
- Page table of a single process has at most 1024 entries
- Virtual memory is not used.
I know from the above that a WORD in such a system must be 4 Bytes long.

Since virtual memory is not being used, I think it is possible that a process can get all the 4K frames if it requests them (assuming obviously that they're available for it when it's loaded) thus it can be allocated all of the available physical memory (128MB). However if Virtual Memory is used then the maximum amount it can get is 32MB because of the structure of the page table (1K entries, each entry has 8K words and each word = 4 Bytes). Is my conclusion correct or not? I reached it while reading Silberschatz, Galvin & Gane book (Operating System Concepts).

# Answer
> -2 votes
The main point I think is here the usage of paging without implementation of virtual memory(VM) techniques.

Nowadays it's rare, but once upon a time when the concept of VM was a dream paging was used for a different purpose. At that time the memory allocated to a process needed to be contiguous which usually lead to fragmentation (external) and hence bad utilization of memory. Then the concept of paging brought a revolution. Memory can be allocated to a process non-contiguously. The process memory space is divided into pages of same size. The Main Memory is also divided into same size frames and page size is equal to frame size. Page table of a process keeps track of the addresses of the frames. To be precise if the page table has $k$ entries it can have at most $k$ frames. For each frame, page table stores the starting memory address of that frame. Unlike the concept of VM all the frames need to be stored in main memory. Note that this might lead to another type of fragmentation (internal) as a process memory space size might not be multiplicative of page size. But, this is not that severe like the external one.

So, here in your question I think they try to mean this kind of scenario, paging without VM. Thus here also it is possible to limit the size of a process by using the page table in the similar manner you mentioned in your question for the case where we use VM.

But, my main concern is to convey the idea that we can indeed use paging without VM.

---
Tags: memory-management, paging, virtual-memory
---


# Question
Title: Proving a language is not decideable using a reduction from Busy Beaver?
I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural number). I was asked to prove that this function is uncomputable using a reduction from the Busy Beaver. I'm still new to reductions and after sitting on this problem for a while I've gotten nowhere. I'd appreciate any help/guidance.

# Answer
> 1 votes
Hint: Why is the busy beaver function difficult (rather, impossible) to compute? Consider the following algorithm: given $n$, run all $n$-state Turing machines, and whenever one of them halts, update your estimate on the maximum number of steps. Eventually you will have found $BB(n)$, but you wouldn't know, since some of your machines are still running. Will any of them terminate, or have you discovered $BB(n)$? The function $F(n)$ given to you in the question could help in that respect.

# Answer
> 1 votes
Note that $F(n)$ is **non-decreasing** function, and that

$F(BB(n))\leq n$

and

$F(BB(n)+1)\>n$.

That was my big hint. For the complete solution, keep reading:

Build a $TM$, $S$, such that on a given $n$:

Run on $k$ from $1$ until $FF(k)\leq n$ and $FF(k+1)\>n$. Then return that $k$.

-- S computes $BB(n)$.

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


# Question
Title: NP-completeness: Reduce to or reduce from?
Very simple question, but a mistake I make often enough that I'd love to have a standard reference.

I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $P$, then showing that this solves another NP-Hard problem $Q$ in polynomial time.

Have I reduced $P$ to $Q$ or have I reduced $Q$ to $P$?

Since $Q$ is the problem of known hardness I've chosen, have I reduced from $Q$ or reduced to $Q$?

# Answer
To show a new problem $X$ is hard, you reduce from a problem of *known hardness* to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$.

The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-SAT instance to an instance of $X$. Given an instance of 3-SAT, you transform it into an instance of $X$, apply the efficient algorithm for $X$, and thus have solved the 3-SAT instance.
> 10 votes

# Answer
Suppose you already know that a problem $Q$ is NP-hard. Now you need to show that problem $P$ is NP-hard.

Note that it's very informal and intuitive idea.

We'll show $P$ is as hard as $Q$, which proves that $P$ is also Np-hard. We know that $Q$ is very hard problem. Now the idea is like proof by contradiction. Assume $P$ is not that hard like $Q$ and I could have an easy algorithm. Now, I need to get some contradiction. So what can I do? I can **reduce** $Q$ **to** $P$, i.e, we have an easy black box algorithm for $P$ and we can use that to change an input of $Q$ to input of $P$ and use that black box to get a solution for $Q$. Oh! I have easily solved $Q$. But, this contradicts the fact that $Q$ was hard. Thus our assumption was wrong and $P$ must be also as hard as $Q$.

The following image will not let you forgot the direction ever.

**$Q$ known to be NP-hard, $P$ claimed to have a polytime algorithm.**
> 5 votes

# Answer
Short answer: You have to reduce a known $\mathtt{NP}$-hard problem $Q$ to your problem $P$.

Let me give an informal argument why this is the case. Note that if you reduce $Q$ to $P$, then you can reduce *any* problem from $\mathtt{NP}$ to $P$. Thus $P$ is $\mathtt{NP}$-hard, by defintion of $\mathtt{NP}$-hardness. (A problem $Q$ is $\mathtt{NP}$-hard if every problem from $\mathtt{NP}$ is reducible to it. Equivalently, a problem is $\mathtt{NP}$-hard if there exists an $\mathtt{NP}$-complete problem that is reducible to it.)

I highly recommend Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak.

Also, $\mathtt{NP}$-hardness is not the same as $\mathtt{NP}$-completeness. The title of the question asks for $\mathtt{NP}$-completeness, while the question itself is about $\mathtt{NP}$-hardness. The problem $Q$ is $\mathtt{NP}$-complete if it is $\mathtt{NP}$-hard and if it is in $\mathtt{NP}$. Note that $\mathtt{NP}$-hard problem need not be in $\mathtt{NP}$.
> 3 votes

---
Tags: complexity-theory, terminology, np-complete, reductions, polynomial-time
---