title: How do hand-written lexers work?

text:
# Question
Title: How do hand-written lexers work?
Im studying a book called "Engineering a compiler" by Linda Torczon and Margaret Cooper. In the second chapter which discusses lexical analysis they mention three aproaches to writing a lexical analyser: 1. Table-driven, 2. Direct coded and 3. Hand coded.

My question is: how do hand coded lexers generally work ? Are they similar to either table-driven or direct-coded ones ? Where can i find simple examples of hand coded lexers ?

# Answer
> 3 votes
> How do hand coded lexers generally work?

That depends on whose hand coded them :-). But:

> Are they similar to either table-driven or direct-coded ones?

Table-driven hand-coded lexers are rare in my experience (if you were going to use a table anyway, why not use a tool to generate the table). Torczon & Cooper use "direct-coded scanner" to mean a scanner which effectively embodies the state machine (DFA) in code, so that the program counter is the state.

Most hand-coded lexers implement a state machine of some kind, although they are often not very rigid in their model. For example, a common approach is to use a switch on the first character of the token, and then, depending on the token type, use some standard library function to parse the rest of the token. While some hand-coded parsers implement a direct-coded trie for keywords, others just recognize identifiers and then check the token in a hashtable. And a large variety of other variations on the theme.

\[Note 1\]

> Where can I find simple examples of hand coded lexers?

Check out the Bison manual, which has a number of simple examples which do not depend on lex.

---

### Notes:

1. Some machine-generated lexers -- see Ragel or re2c, for example -- are direct-coded state machines. This was once believed to improve scanner speed, a theory also endorsed by the textbook. However, I'm not convinced that it is still the case with modern pipelined processors. In any event, it is very rare for scanner speed to be a noticeable part of compilation time.

---
Tags: lexical-analysis
---


# Question
Title: How to predict the next word in a sentence using N-grams
How would I go about predicting the next word in a sentence if I have a n-gram model available? A intuitive solution would be to just ask the probability of all the words that can come next and see which has the highest. But this would be dreadfully slow if I have a very large set of n-grams wouldn't it?

If anyone could point me in the right direction that would be great!

Here is what I have so far. We have a data structure and this data structure will allow lookup of context(so the previous words) via hashing. This can be done in O(m) with m the length of the context but since this is always very short it is safe to say lookup can be done in O(1). Now let's say the previous words are "I want to" I would look this up in my ngram model in O(1) time and then check all the possible words that could follow and check which has the highest chance to come next. But with something as generic as "I want to" I can imagine this would be quite a few words. Our application must run on mobile devices so I would like to know if there is a more efficient way to get the word with the highest chance. I was thinking about maybe sorting the ngrams but since we are using some sort of hashtable this isn't really an option.

The more I think about this however the more I realize that even if it would be lets say 500 words that can come next, that this is still a fairly small number and even a slow processor could easily go over those very quickly so maybe I am over thinking things.

# Answer
> 2 votes
Store the n-grams in a tree or trie, with one level per word, starting from the leftmost word. Then given some context, e.g., "I want to", you traverse the tree/trie (follow the edge out of the root that is labelled "I", then the edge labelled "want", then the edge labelled "to") and find all children of the resulting node.

# Answer
> 2 votes
With N-Grams, N represents the number of words you want to use to predict the next word.

You take a `corpus` or dictionary of words and use, if `N` was 5, the last 5 words to predict the next. I will use letters (characters, to predict the next letter in the sequence, as this it will be less typing :D) as an example.

Say you have a corpus or input stream such as `wwwaasssssdddaawww` ? Let us use bi-grams (`n=2`) and we want to predict the next character in the sequence: ?

To do this, we first get all the distinct letters: `w,a,s,d` Next, we define a `prefix` as being the past (most recent) 2 letters: `prefix = ww`.

We then want to know, given the last two letters were `ww`, what is the probability of seeing another `w`? an `a`? a `s`? a `d`?

The first thing to do is work out how many times the prefix appears: 4 times.

So, we build our frequency distribution and we see that within the corpus, a `w` appears after the sequence `ww` twice. An `a` appears 1 time after `ww`, `s` appears 0 and `d` appears 0 times.

From this, we can conclude that the probability of seeing a `w` next, is `4/2 = 2/4 = 50%. An a: 25%, s: 0, d: 0`.

Obviously, having zero probability is not correct. If the words are unknown, you can assign them some dummy character/word like `???`. If the words are not unknown, but just not seen given the prefix, you should use some sort of smoothing algorithm (like Laplace).

That is the 'just' of it. I learned about N-Grams from the following resource: https://lagunita.stanford.edu/c4x/Engineering/CS-224N/asset/slp4.pdf

As for your data issue... You can create a data structure where each unique possible prefix is the key in, for example, a dictionary.

Your dictionary keys would look something like this (based on the above corpus):

```
'ww', 'wa', 'aa', 'as', 'ss', 'sd', 'dd', 'da', 'aw'

```

Every time you encounter a new unique prefix, you add a new entry to your dictionary.

Each key in the dictionary could have an object as a value with n-properties, where `n` is the number of distinct possible words/characters and each stores the count of observations (initialised to 0). EG:

```
'ww': w = 0,a = 0,s = 0,d = 0

```

Then every time you see a word/letter come in, you grab the prefix (in our case `ww`) and increment the count for the observed character/word:

```
'ww': w = 2, a = 1, s = 0, d = 0

```

Now when you see another `ww` and then get a `w`, just increment...

```
'ww': w = 3, a = 1, s = 0, d = 0

```

To get the probability, just grab the KVP for the given prefix, choose the property with the greatest count and divide it by the number of unique properties.

This means that instead of storing aaaaaall the data, you are just storing counts! Much more data efficient. Further, information is the far past may not be a very good indicator of what is likely to be seen in the near future, so you could limit your corpus to say, 1000 wrods... as they come in, you remove the oldest and add the new incoming one (a stack...), but you will have to play a bit to find out what works best.

Hope this helps!

---
Tags: algorithms
---


# Question
Title: N-Grams - how to predict further into the future and how far can we predict?
I am using N-Grams to predict future character input. For n+1, it performs really well.

I've been looking, but I have not been able to find any information on what the feasible maximum distance into the future N-Grams are capable of.

One way I could do this is to predict the next character (n+1) and then use that result to predict n+2, use n+2 to predict n+3... etc... but obviously an incorrect prediction will cascade and impact the future predictions as there is a dependency.

Is there a better (more accurate, reliable) way to do this? Also, I can easily use N-Grams to predict the next (n+1) character in an incoming stream, but what about n+2? How about n+3? When does it become unrealistic to predict further?

I'm sure there is some research on this, so I'd love it if you could link me to a paper or give me a brief overview to get me going.

# Answer
> 0 votes
There's no simple answer to "how far into the future can you predict?". Obviously, the further you go, the less your ability to predict. For English text, I would expect that ability to predict would decrease rapidly.

You asked if there's a better wya to do this. You can of course consider a generalization of $n$-grams where you use the characters at positions $i-n+1,i-n+2,\dots,i-1,i$ to predict the character at position $i+k$ (instead of predicting the character at position $i+1$), for any fixed $k$. This will probably perform worse the larger $k$ is.

You might also be interested in skipgrams.

---
Tags: computational-linguistics
---


# Question
Title: All nearest neighbor in a changing 2d euclidean space
I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:

Given a 2D space with $N$ random points $p\_1...p\_n$, calculate the nearest neighbor of each of the points, where the distance is at most $C$.

Note that our list of points is unsorted, and that each point is an actual object so I could give it any property I want.

Now this can easily be done in $O(n^2)$ time, it is also the easiest and not really an issue. However, the time it takes when a new point is added or a point is removed is also $O(n^2)$, and I would like to get that down, because this is done during gameplay (while the initial step is only done at start).

Does anyone know a possible improvement over the simple 'bruteforce'? I tried sorting, twice, and keeping it up to date (using a 4x linked list (up, down, left, right)) but that did not seem to work.

# Answer
> 1 votes
You want a data structure that supports nearest neighbor search in 2D. There are many options, but a simple one that is widely used for practical situations is a quadtree data structure. It supports both efficient lookup and efficient insert operations.

# Answer
> 0 votes
After I linked this to a friend, he found this solution:

Store for every point all other points that are in distance $C$ in a hashmap with the key as the node. (This is $O(n^2)$ with amortized $O(1)$ for hash put) When adding a node $x$, search all nodes and add every node with distance less than $C$ to the list of $x$. Add $x$ to all nodes in the list of $x$ ($O(n + some)$) When removing a node $y$, remove $y$ from the lists of the nodes in the list of $y$. $O(some)$

I tried this quickly in Processing (java-ish) to see if it works, and it seems to have a bit slower initial step, but removing and adding a node is almost no-time.

---
Tags: algorithms, nearest-neighbour, euclidean-distance
---


# Question
Title: How do I prove that SAT in coNP implies NP=coNP?
Is it true that if SAT is in coNP then its also coNP-complete (because it is NP-complete)?

# Answer
> 4 votes
If SAT is in coNP then since coSAT is coNP-complete, SAT can be reduced to coSAT in polytime. The same reduction also reduces coSAT to SAT. Since coSAT is coNP-complete, every problem in coNP can be reduced in polytime to coSAT, and so to SAT. This shows that SAT is coNP-complete.

---
Tags: np-complete, satisfiability, np, co-np
---


title: How to negate this one?

text:
# Question
Title: How to negate this one?
How can I negate the following sentence: For all words x from L with |x|\>= n , exists decomposition x = uvw with |uv| \<= n and |v| \>= 1, so for all i \>= 0 , is valid that u(v)^iw in L is.

# Answer
> 0 votes
The negation is: There exists a word $x \in L$ satisfying $|x| \geq n$ such that for all decompositions $x = uvw$ with $|uv| \leq n$ and $|v| \geq 1$ there exists $i \geq 0$ such that $uv^iw \notin L$.

---
Tags: logic, notation
---


title: nerode equivalence classes q - prefix?

text:
# Question
Title: nerode equivalence classes q - prefix?
Lets consider the following language : $L = \\{1w |w \in \Sigma^\*\\}$ (Alphabet is 0 and 1).

I know this language is regular, I just have to prove it now, the Problem here is the number of equivalence classes, I thought it would be: $\[1\] = \\{x|x $ starts with 1$\\}$ and $\[\epsilon\] = \\{x| x$ doesn't start 1$\\}$. But now I am dubious, isn't it possible for L to have 3 equivalence classes one containing words that start with 1 and one class that has epsilon as its only element?

Thanks in advance

# Answer
There are three equivalence classes, and this can be seen from the minimal DFA, which has three states. The equivalence classes are $\epsilon,0\Sigma^\*,1\Sigma^\*$. Indeed:

* $\epsilon$ and $0$ are in different classes since $\epsilon 1 \in L$ whereas $01 \notin L$.
* $\epsilon$ and $1$ are in different classes since $\epsilon \epsilon \notin L$ and $1\epsilon \in L$.
* $0$ and $1$ are in different classes since $0\epsilon \notin L$ whereas $1\epsilon \in L$.
* All words in $\\{\epsilon\\}$ are clearly equivalent.
* All words in $0\Sigma^\*$ are equivalent since $wz \notin L$ for all words $w \in 0\Sigma^\*$ and all words $z$.
* All words in $1\Sigma^\*$ are equivalent since $wz \in L$ for all words $w \in 1\Sigma^\*$ and all words $z$.
> 0 votes

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


# Question
Title: Operation on a regular language and context free language
Given $L\_1$ and $L\_2$ over some alphabet:

$L\_1@L\_2 = \\{uv \mid u \in L\_1 \land v \in L\_2 \land |u|=|v|\\}$

The question is: if $L\_1$ is regular and $L\_2$ is context-free, is $L\_1@L\_2$ context free?

I've been trying to disprove this but to no avail. So I've been thinking to prove this by buiding a PDA but I can't seem to figure this out.

# Answer
There is no guarantee that your resulting language will be context free.

Here is a hint for creating a more formal proof. Try the languages $L\_1 = c^\*$ and $L\_2 = a^nb^n$. The resulting language, given your additional requirement of $|u| = |v|$ would be $c^{2n}a^nb^n$.

Using the pumping lemma for context free languages, are there two substrings that you can pump indefinitely that will match this language?
> 3 votes

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


# Question
Title: Reducing randomness needed by turing machine
I am reading an article related to streaming algorithms named "Turnstile streaming algorithms might as well be linear sketched" by Yi Li, Huy Nguyen and David Woodruff,

At some point they have a random algorithm (uses a tape of random bits) that solved a problem over $\mathbb Z\_{|m|}^{n} = \\{-m,..,m\\}^n$ that succeeds with probability $1-\delta$

They want to reduce the number of bits needed for randomness used by that algorithm using via the following statement:

> Theorem 9: Let A be a randomized automaton solving problem P on $\mathbb Z\_{|m|}^{n}$ with failure probability at most $\delta$. There is a ranomized automaton B that only needs to pick uniformly at random one of $O(\delta ^{-2}nlogm)$ deterministic instances of A and solves P on $\mathbb Z\_{|m|}^{n}$ with failure probability at most $2\delta$
>
> Proof: Let $A\_1 ,A\_2 ,.., A\_{O(n\delta ^{-2}logm)}$ be independent draws of deterministic automata picked by B.
>
> Fix an input $x\in \mathbb Z\_{|m|}^{n}$.
>
> Let $p\_A(x)$ be the fraction of automata among $A\_1 ,A\_2 ,.., \> A\_{O(n\delta ^{-2}logm)}$ that solve problem P correctly on x and $p\_B(x)$ be the probability that B solves P on x correctly.
>
> By a Chernoff bound, we have that $Pr\\{|p\_A(x)-p\_B(x)|\geq \delta\\} \leq exp(-O(nlogm)) \< (2m+1)^{-2n}$.
>
> Taking a union bound over all choices of $x\in \mathbb Z\_{|m|}^{n}$, we have $Pr\\{|p\_A(x)-p\_B(x)|\geq \delta \ for\ all\ x\\} \> 0$.
>
> Therefore, there exists a set of $A\_1 ,A\_2 ,.., A\_{O(n\delta \> ^{-2}logm)}$ such that $|p\_A(x)-p\_B(x)|\leq \delta$ for all $x\in \> \mathbb Z\_{|m|}^{n}$. The automaton B simply samples uniformly at random from this set of deterministic automata

I am having trouble understanding some parts of the proof:

the random variable $p\_A(x)$ should be the amount of $A\_i$'s that succeeds divided by the amount of them that B has sampled?

if so than by the low of total probability its easy to see that:

> $p\_B(x) = \sum\_{i}P\[B\ choose\ A\_i\] P\[B\ succeeds\ on\ x\ |\ B\ choose' A\_i\] = \sum\_{i}\frac{1}{O(\delta^{-2}nlogm)} P\[A\_i\ succeeds\ on\ x\] = p\_A(x)$

where the last move comes from the fact the each instance $A\_i$ is deterministic so its either 1 for success or 0 for failure.

So the whole $|p\_A(x)-p\_B(x)|$ they use is actually 0

I understand from the end of the proof that $|p\_A(x)-p\_B(x)|$ should some how represent the distance between A's success to B's success but could not see how this happen.

Also I did not understand the use of Chernoff the way they did.

# Answer
Here is another way of looking at $p\_A$ and $p\_B$. We can think of $B$ as a deterministic algorithm which accepts an additional input $r$ representing the randomness. This input is drawn from some distribution $R$. Also, denote by $P(x)$ the correct answer. Then $$ p\_B(x) = \Pr\_{r \sim R} \[B(x,r) = P(x)\]. $$ Let $M = O(n\delta^{-2}\log m)$, and sample $r\_1,\ldots,r\_M \sim R$. The algorithm $A\_i$ simply runs $B$ with randomness $r\_i$, that is $A\_i(x) = B(x,r\_i)$. We can define another algorithm $A$ which first choose $i \in \\{1,\ldots,M\\}$ uniformly at random, and then runs $A\_i$. The success probability of $A$ is $$ \begin{align\*} p\_A(x) &= \Pr\_{i \in \\{1,\ldots,M\\}} \[B(x,r\_i) = P(x)\] \\ &= \Pr\_{r \in \\{r\_1,\ldots,r\_M\\}} \[B(x,r) = P(x)\]. \end{align\*} $$ Thus in $B$, the randomness is chosen according to $R$, whereas in $A$, the randomness is chosen uniformly from a set $\\{r\_1,\ldots,r\_M\\}$. If we choose $r\_1,\ldots,r\_M \sim R$, then we expect the performance of $A$ to be very similar to that of $B$, and this can be quantified using Chernoff's inequality.

The probability $p\_A(x)$ itself depends on the choice of $r\_1,\ldots,r\_M$. What may confuse you is how we conceive of this two-step random process. We *first* choose $r\_1,\ldots,r\_M$, and this gives us the function $p\_A(x)$, which is a random function depending on the choice of $r\_1,\ldots,r\_M$. Note that we *don't* take probability over the choice of $r\_1,\ldots,r\_M$ – if we did, we would just get $p\_B(x)$.
> 3 votes

---
Tags: turing-machines, randomized-algorithms, streaming-algorithm, chernoff-bounds
---


# Question
Title: Irregularity of language of words whose length is of power of 2
How to show that the language containing the words whose length is a power of $2$, $L=\\{w\mid|w|=2^i\\}$, isn't regular using the pumping lemma?

The pumping lemma says that

> Let be M a regular language. Then it exists a number $p\>0$ such that for each word $w\in L$, such that $|w|\ge p$, it exists $x,y,z$ such that :
>
> 1. $w=xyz$
> 2. $|y|\>0$
> 3. $|xy|\<p$
> 4. For each $i\ge 0$ we have $xy^iz\in L$.

(I don't perfectly understand this lemma...). I have great difficulties to understand the examples which I can provide you in French here.

*My question is different from How to prove that a language is not regular? as far as all answers are based on $L=\\{w\mid|w|=a^pb^q\\}$ scheme, mine only have one element and is playing on the size rather than the scheme.*

### My attempt

We take $w=a^{2^n}$. Therefore we have $w\in L$ and $|w|\ge p$. We need a partition $w=xyz$ (to fill in condition 1.) such that $|xy|\<p$ (condition 3) and $|y|\>0$ (condition 2).

* Let's assume $L$ is regular.
* I thought about taking $|w|\>n$
* $x = aaaa....$ , $y = aaaa...$, $|x|=s$, $|y|=k$. We need to consider ALL the options, that is all the possible $s,k$ such that $s≥0$,$k≥1$ and $s+k≤n$.

Let's take $i=0$, then $xy^iz=xz=a^{n-k}a^n\not\in L$ whatever may $s,k$ be and since $k\ge 1$, $L$ isn't regular at all (but why) and we reach a contradiction.

I have some difficulties understanding the conclusion.

# Answer
The strategy for proving a language non-regular is a proof by contradiction:

We assume that $L$ is regular. This then means that there exists a $p \> 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3. But now it is enough to find *some* $w$ where $|w| \geq p$ such that *no* partition can satisfy all three conditions simultaneously.

In the concrete case, you have not told us what alphabet $\Sigma$ we are considering. I assume that $\Sigma = \\{ a,b\\}$, but this is not important.

So we assume that $L$ is regular, and therefore there must exist a $p \> 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3.

But now consider $w = a^{2^p}$. Clearly, $w \in L$. Moreover, we have that $|w| \geq p$, so there should be some partition of $w = xyz$ that satisfies conditions 1, 2 and 3.

If the partition must satisfy condition $3$ then the first two parts of the partition, that is, $xy$, must have total length less than $p$. Therefore, $|y| \leq p$. If the partition must also satisfy condition $2$, then $y$ cannot be the empty string, so $y = a^k$ for some $k$ where $0 \< k \< p$.

But can such a partition then also satisfy condition $1$? No. It is enough to find an $i \geq 0$ such that $xy^iz \notin L$ to see this. Take $xy^2z$. This string has length $2^p + k$, and since $k \< p$, we know that $2^p + k$ cannot be a power of $2$. So $xy^2z \notin L$.

In other words: The appropriate strategy is to try to satisfy the conditions one by one. Usually, we first try to satisfy condition $3$. This will tell us where $y$ can appear (among the first $p$ symbols) and how long it can be. Given that, we then try to also satisfy condition $2$, and this usually just provides with the useful information that the string $y$ that can be repeated, is non-empty. Finally, we show that we can "pump our way out" of the language with this partition, thereby violating condition $1$.
> 2 votes

# Answer
Consider any $DFA$ which represents a regular language $L$. Now, the $DFA$ may have loops in it.

Pumping Lemma is about identifying strings $w$ such that $x$ and $z$ are the non-loop parts and $y$ is the string parsed in the loop part. Now, if such a $w$ is accepted by the $DFA$, $xy^iz$ is also a string of the language.

Now, to prove that the given language is not regular, try to find such a $y$ and pump it. For arbitrary values of $xy^iz$, we can see that length of $w$ is not a power of $2$ as follows using proof by contradiction:

Assume that the given language is regular. Hence, by pumping lemma we have a $p \> 0$

such that for strings $|w| \>=p$ the lemma holds.

Now, consider the closest power of $2$ greater than $p$.
It can be written as $2^{\lfloor{lgp}\rfloor+1}$.
Let's call the exponent $a$. Hence \begin{equation} a = \lfloor{lgp}\rfloor+1 \tag{1} \end{equation} Clearly $2^a \> p $ hence, pumping lemma holds true for strings $w$ of length $=2^a$.

Consider any such $w$. Let's write it as $xyz$ such that $|xy| \< p$.
Clearly $|y| \< p $.
Hence \begin{equation} |y| \< 2^a . \tag{2} \label{eq:2} \end{equation} Now, consider the new string $xy^2z$.

$|xy^2z| = |xyz|+|y|$
=\> $|xy^2z| = 2^a + |y|$
=\>$|xy^2z| \< 2^a + 2^a $ from \eqref{eq:2} above
=\> $|xy^2z| \< 2\*2^a = 2^{a+1}$

Hence, the new string constructed from pumping lemma has a length between two consecutive powers of $2$, so it cannot be a string of the original language.

As this holds for all values of $x, y, z$ satisfying the constraints of the lemma for the given string, we can say that the original language is not regular.

Hence proved that the language is not regular.
> 0 votes

# Answer
Your language is a unary language (a subset of $\sigma^\*$ for some letter $\sigma$). You can prove in various ways the following theorem:

> The language $ \\{ \sigma^n : n \in A \\} $ is regular if and only if the set $A$ is *eventually periodic*, that is, if there exist $n\_0,m \geq 1$ such that $n \in A \leftrightarrow n+m \in A$ whenever $n \geq n\_0$.

In particular, if the language is regular and the asymptotic density of $A$ is zero, then $A$ is finite. In your case the asymptotic density of $A$ is zero yet $A$ is infinite, and so the language is not regular.
> 0 votes

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


# Question
Title: Genetic algorithm neural networks converges, but suddenly stops
I'm trying to create a genetic algorithm to train neural networks (because I'm to bad at back-propagation), and it works well until generation 18, where the loss stops to decrease and gets constant. The loss gets from 112 to about 90 in 18 generations and almost doesn't change:

Here is the genetic algorithm (I think the problem doesn't come from the neural network algorithm as it's very basic) in python :

```
# This is my reproduce function :
def reproduce(first,other,mutate=0):
    child = Entity() # Creates a new Neural Network (class Entity is the class of the Neural Networks)
    # Only two synapse matrices, each get the mean of its two parents
    child.syn0 = (first.syn0 + other.syn0)/2
    child.syn1 = (first.syn1 + other.syn1)/2
    if mutate:
        # Add some mutation if it's enabled, but it didn't work without it
        child.syn0 += child.syn0*(np.random.random()*mutate-mutate/2)
        child.syn1 += child.syn1*(np.random.random()*mutate-mutate/2)
    return child

ent = [Entity() for _ in range(20)] # Creates 20 new Neural Networks with random weigths on their synapses

nb_dna = 1
gen = 0
scores = []
max_gen = 100

while gen < max_gen:
    np.random.seed(int(time.time()))
    # The Neural Networks goes forward.
    for i,e in enumerate(ent):
        e.set_input(int(np.floor(np.random.random()*nb_dna)))
        e.forward()
        # In the forward function, the score is calculated as the result of a squared error cost function

    if gen < (max_gen-1):
        # Do natural selection
        ent.sort(key=lambda x: x.score) # Sort my ascending score (the lowest the score is, the closest the NN is to the expected result
        ent = ent[:4] # Kill all entities except the five 1st

        # Reproduce the winners
        for i in range(4):
            for j in range(4-i):
                # 1st reproduces with 2nd, 3rd, 4th and 5th,
                # 2nd with 3rd, 4th and 5th,
                # 3rd with 4th and 5th,
                # and then 4th with 5th
                    new = reproduce(ent[i],ent[j],mutate=0.2) # Changing the mutation rate "mutate" will only change the convergence speed
                    ent.append(new)
    gen += 1

```

Can you tell me if I'm doing something wrong, or if I'm going the wrong way ? Else, is that the best I can get ? It's actually the first "real" genetic algorithm I create (previous ones were easy JS algorithm to try to find a target word, starting with random letters)

# Answer
Well, I'm not an expert at genetic algorithms, but here's what I would check, coming from a neural networks perspective:

1) Learning rate (in your case, I think this is your mutation rate? Please correct me if I'm wrong). When a neural network exhibits this type of 'convergence', often you need to decay the learning rate either as a step function after a fixed number of iterations, or smoothly through exponential decay. Is that an option for you?

2) Initialization. Have you tried initializing your algorithm from different points and seeing if the convergence behaviour changes?

3) Adding noise. Sometimes you can get stuck in a poor local minimum, or at a saddle point. Small neural networks are more likely to get stuck in local minima. Saddle points proliferate in high-dimensional space. When learning stalls like this, adding some jitter to your parameter values and trying to learn from that new location can sometimes move you from a saddle point or local min to a better location in error space, and learning can continue from there.

4) Hyperparameter selection. How do you know your network is the correct size? Have you done some cross-validation to determine the number of hidden units you need, for example? Have you tried any kind of regularization?

Hopefully that provides some inspiration, or at least a starting point. Best of luck!
> 2 votes

---
Tags: neural-networks, genetic-algorithms
---


# Question
Title: GOTO vs. including line in loop - will it affect efficiency?
Let's say I have an algorithm something like as follows:

```
1 eliminate stuff from a list called reactions
2 for each element in reactions:
3    if one thing is computable:
4        compute it
5    else:
6        eliminate element from reactions, GOTO 1

```

Can I change it too

```
1 eliminate stuff from a list called reactions
2 while length of reactions is > 0:
3    while thing is computable:
4        for each element in reactions
5            compute it and append it to list called relevant_reactions
6            eliminate element from reactions
7    eliminate element from reactions

```

without any changes in efficiency? If there are any ways to improve the efficiency please let me know.

For reference, this algorithm is from page 8 of the paper Reachability Problems for Continuous Chemical Reaction Networks. The reason this question is important is because the main result of this paper is showing that the algorithm runs in polynomial time.

The reason the 6th and 7th lines are the same is to eliminate both those elements where the thing is not computable and those where it is computable (those are moved to a new list). I feel like there's a better way to do that part, however, so any advice there would be appreciated.

---

I should point out that the main reason I am rewriting the algorithm is to remove the `GOTO 1`. It's hard to implement in Python 3 (my language of choice) and it seems to be generally considered bad practice.

I should also point out what exactly the "thing is computable" is for sake of context/completeness. Basically, that line is computing a vector (that must be $\in \mathbb{Q}^R\_{\geq 0}$) that is multiplied by a matrix and when added to another vector should equal another vector. The vector elements are concentrations of chemicals. The matrix contains the net change of various reactions. It would look something like this: (vector that represents current state of the system) + (matrix of net change of every reaction in the list reactions)\*(vector we are solving for) = (vector representing current state) and the element in reactions (the one in the iteration of the for loop, also in the vector we are solving for) must be greater than 0. If you found that confusing, no wonder, I did too (especially the last part). The relevant part in the paper is line 3 of Algorithm 1 in section 3. The exact line is

> Compute a vector $F\_{\rho}\in\mathbb{Q}^R\_{\geq 0}$ such that $\mathbf{c}+\mathbf{M}F\_{\rho} = \mathbf{d}$ and $F\_{\rho}(\rho) \> 0$, if one exists

# Answer
> 3 votes
With the question as it is written right now, I have no idea what "one thing" and "thing" are, the second version modifies a list named "relevant\_reactions" that isn't present in the first version, so all in all I would say that your question is impossible to answer.

You say that "goto" is considered bad practice, but instead of removing the "goto", you complete rewrote everything from scratch. If you don't like the "goto" here's a way that doesn't change your algorithm at all:

```
1 eliminate stuff from a list called reactions
2 all_done = false
3 while all_done is false
4     all_computable = true
5     for each element in reactions:
6         if all_computable is false:
7             do nothing
8         else if one thing is computable:
9             compute it
10        else:
11            eliminate element from reactions, all_computable = false
12     if all_computable is true:
13         all_done = true

```

# Answer
> 2 votes
Modern languages are *heavily* optimized, so much so that it is hard to predict if minor code changes will make an algorithm run faster. In particular with matrix math, whether the language implementation replaces loops with vector instructions or offloads parallelizable operations to a GPU is going to matter much more than pretty much anything you can adjust by hand.

What you should always do is code for completeness and correctness and only then use a profiler on the executable if it's not running fast enough. Optimize the parts that the profiler tells you consume the most CPU time.

---
Tags: algorithms, algorithm-analysis, efficiency, polynomial-time
---


title: Matching points between 2 polygons

text:
# Question
Title: Matching points between 2 polygons
Given 2 polygons in a plane:

$A : ( (xa\_1,ya\_1), (xa\_2,ya\_2), ... (xa\_n,ya\_n) )$

$B : ( (xb\_1,yb\_1), (xb\_2,yb\_2), ... (xb\_m,yb\_m) )$

Is there a polynomial algorithm to compute a matching $M$ between the points in A and B, such that:

1. If $(xa\_i,ya\_i)$ is matched to $(xb\_p,yb\_p)$ and $(xa\_k,ya\_k)$ is matched to $(xb\_r,yb\_r)$, then for $i\<j\<k$ and $p\<q\<r$, $(xa\_j,ya\_j)$ is matched to $(xb\_q,yb\_q)$.
2. For $M:\\{(i\_1,j\_1),(i\_2,j\_2)...\\}$ and $|M|=min(n,m)$, $\Sigma\_{k=1}^{|M|} distance((xa\_{i\_k},ya\_{i\_k}),(xb\_{j\_k},yb\_{j\_k}))$ is minimized.

# Answer
> 3 votes
This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms:

> H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, *Handbook of Computational Geometry*, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. doi:10.1016/B978-044482537-7/50004-8

If you have difficulty accessing that chapter, an earlier draft of the survey is here: PDF download.

---
Tags: algorithms, graphs, computational-geometry, matching
---


# Question
Title: Forming red-black tree from binary tree conserving in-order traversal
What is the optimal algorithm (in terms of time complexity) that can transform any binary tree to a red-black tree, with the requirement that in-order traversal must yield the same values for the new tree?

Is iterative insertion of the original nodes sufficient, or can it be done with better complexity?

# Answer
Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time.

The input tree gives you the in-order traversal, so you can begin by traversing the input tree and storing the keys in an array. Now, notice that if $n = 2^m - 1$ for some $m$, it's actually trivial to create a new binary tree which is *perfectly balanced*: split the array in half, choose the middle element as the root, and recursively build the left and right children from the two halves of the array. To make it a red-black tree, you have to assign colors. For a perfectly balanced tree, this is simple: you can actually make every node black.

But how do you handle the general case, when $n$ is not one less than a power of 2? You won't be able to make a perfectly balanced tree, but you can get pretty darn close!

This smells like a homework assignment, so I'll leave the specifics of assigning colors to you, but here's something to get started. Notice that, when you split the array of keys in half, the two halves have either exactly the same number of keys, or they differ by one. When they have exactly the same number of keys, assigning colors is easy. When they don't, you might need to use some red nodes...
> 1 votes

---
Tags: algorithms, data-structures, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: The most appropriate way to implement a heap is with an array rather than a linked list, why is this?
The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

I don't completely comprehend why this is? is it because it is easier to traverse?

# Answer
It doesn't make any sense at all to implement a heap as a linked list. (The most common kinds of) heaps are inherently binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at index K live at indices 2K+1 and 2K+2 if indices start at 0 (or at indices 2K and 2K+1 if indices start at 1). It's massively more efficient to find the Kth element of an array than the Kth element of a linked list.

Advantages of storing a heap as an array rather than a pointer-based binary tree include the following.

* Lower memory usage (no need to store three pointers for every element of the heap).
* Easier memory management (just one object allocated, rather than N).
* Better locality of reference (the items in the heap are relatively close together in memory rather than scattered wherever the allocator put them).
> 13 votes

# Answer
array based implementations are much easier to work with, as they can be iterated through internally making element updates and destruction much simpler. However they only work on heaps with a defined number of children on each node (like binary heaps). If you are doing something like a pairing heap you will need pointers.
> 5 votes

---
Tags: data-structures
---


# Question
Title: Is knowing ALL factors of a large number an NP?
Say I have a number 45

What are the factors of 45?

1, 3, 5, 9, 15, 45

Is there any other factors?

I know that if I want to find some non trivial factor of some number, say 45, I know it's in NP.

I can non deterministically choose some 2 numbers and verify that those 2 numbers are factors of my large number. Verifying is easy. Just multiply the 2 numbers and see if it match.

What about if I want to find ALL factors of a large number? Is it still in NP?

How do we verify, in polynomial time, that 1, 3, 15, 45 are all the factors of 45? It turns out it isn't because we still have 5 and 9. But say someone says

Okay, 1, 3, 15, 45 are all factors of 45. How do we verify it in polynomial time?

Is it in NP?

Is it NP complete?

Does it has P verifier?

Basically, I wonder if the following problems are in NP

Say n is a number

Say S is a set of numbers between 1 and n

Is S the set of ALL factors of n or not.

A program should say it's false when

1. One element of S, say s, is not a factor of n. We can verify this by dividing n by s and see if there are some reminders.
2. There exist a number, say f, not in S, but is actually a factor of n.

Now is that problem NP?

# Answer
> 3 votes
NP is a class of decision problems. Only decision problems can belong to NP. The problem "factor a number" is not a decision problem.

You can make up many decision problems that attempt to capture factoring. Here is one: the language of all quartets $(n,i,j,b)$ such that the $j$th bit of the $i$th prime factor of $n$ is equal to $b$. This language is in NP, since the factorization of $n$ functions as a witness (this uses the fact that primality can be tested in polynomial time; in fact, it is enough to know that primality is in NP, which is an easier fact). It is strongly suspected that this language is *not* NP-complete.

---
Tags: np
---


# Question
Title: Context-Free Languages where every rule produces at most one non-terminal
Consider a context-free grammar where all rules produce at most one non-terminal (i.e., there is at most one non-terminal on the right-hand side of a rule). What is the class of languages which are accepted by such a grammar?

If you like, we may assume that all rules are one of the following forms, where $V, V'$ denote non-terminals and $a$ denotes a terminal:

(i) $V \to aV'$

(ii) $V \to V' a$

(iii) $V \to \epsilon$

If all rules are of the form (i) or (iii) we get the class of regular languages. On the other hand, we can also recognize more languages, such as the language of palindromes.

Therefore, it is somewhere between regular languages and context-free. Does it perhaps coincide with unambiguous context-free or deterministic context-free?

# Answer
A grammar where every production has at most a single non-terminal is called a linear grammar. If the non-terminal is rightmost in all productions, it is a right linear grammar; if the non-terminal is leftmost in all productions, it is a left linear grammar. Left and right linear grammars produce regular languages (and every regular language can be described by a right and a left linear grammar), but unrestricted linear grammars produce a proper superset of regular languages ($a^nb^n$ is linear), are not necessarily deterministic (the set of palindromes is linear), and are a proper subset of context free languages (the Dyck language \[Note 1\] has no linear grammar. The Dyck language has a deterministic grammar, so linear languages are not a superset of deterministic languages, either.)

It is not decidable whether a CFG has a linear grammar, a result proven by Sheila Greibach in 1966 (http://dl.acm.org/citation.cfm?doid=321356.321365)

---

### Notes

1. The Dyck language is the set of all strings of square brackets where the brackets are balanced, given by the deterministic CFG:

$$S \to \epsilon \mid \mathbb{\[}\\; S\\; \mathbb{\]} \\; S$$
> 6 votes

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


# Question
Title: Evasiveness of acyclicity of undirected graph
The lecture note by Jeff Erickson discusses "Evasive Graph Properties":

> We call a graph property *evasive* if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether an (undirected) graph has that property.

As an example, it shows that connectivity is evasive.

I want to know: Is acyclicity evasive? How to prove/disprove it?

---

*My attempt:* A rather straightforward adaptation I made from the proof for connectivity does not work for acyclicity.

# Answer
Consider any algorithm for acyclicity. We will use the following adversary:

> Whenever the algorithm asks for an edge, say that the edge exists if it connects two different connected components. (That is, if it doesn't close a cycle.)

You can show that the graph constructed by this dialog is always a forest, and moreover the constructed graph has the same connected components as the query graph (which contains all queried edges). In particular, when the last edge is asked, the graph is a tree (assuming $n \geq 3$; otherwise every graph is acyclic), and the graph is acyclic if and only if this edge does not belong to the graph.
> 3 votes

---
Tags: algorithms, graphs, lower-bounds
---


# Question
Title: Subset of numbers whose XOR has least Hamming weight
I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$ complexity? I was thinking of some trie based implementation but don't think that will work at all. Would a dynamic programming approach work by any chance? If possible, a hint would be nice!

# Answer
Your problem is known as *calculating the minimal distance of a (binary) linear code*, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.
> 6 votes

---
Tags: sets, arithmetic, coding-theory, xor
---


# Question
Title: What fragment of Martin-Löf dependent type theory can be expressed using generic types in Java?
I have recently come to realize that  number of problems I had a few years ago trying to implement various mathematical theories in Java came down to the fact that the typing system in Java is not sufficiently strong to model all of Martin-Löf dependent type theory.

Prior to Java 5 and generics, the only type theory you could do was through classes and interfaces, which give you arbitrary types built out of the ground types `int`,`double`,`char` and so on using product and function types. You can also build recursive types such as `List`s, though not in a uniform way.

Using generics, you can do a bit more. You can now define `List<T>` as a function $$ \DeclareMathOperator{\Type}{Type}\Type\to\Type $$ and so we get higher order types.

This is not the end of the story, though. Using a generics trick, we can model *some* dependent product types. For example, we can define types of the form $$ \prod\_{T\colon\Type}f(T) $$ using the syntax

```
public interface f<T extends f<T>>
{
  // We can now refer to T as much as we like
  // inside the class.  T has type f<T>.
}

```

As an example, we can model the basic underlying structure of a monoid (but not the associativity and unitality conditions) using a term of type $$ \prod\_{T\colon\Type}T\times (T\to T\to T) $$ (i.e., a set $T$ with a designated unit element and a binary operation on $T$). Using Java generics, we can model this type:

```
public interface MonoidElement<T extends MonoidElement<T>>
{
  public T unit();

  public T mul(T op1, T op2);
}

```

However, when we try to model more complicated concepts, the type theory breaks down.

Is there a simple description of the fragment of MLTT corresponding to the types that can be built in the Java typing system?

# Answer
> 13 votes
There are a lot of misconceptions here. To begin, MLTT doesn't have subtypes, so Java is not going to simply be a fragment of it. It does not require dependent types to make either of the types you gave. A dependent type system doesn't need to have a "type" of types (a universe) in general (MLTT does have universes though), nor do you need dependent types to express those types. In a system like the polymorphic lambda calculus/System F, you can say $\forall T.T\times(T\to T\to T)$. Java doesn't have any equivalent to Type. A dependent type without an analog as a polymorphic type would be something like e.g. $\prod\_{n:\mathsf{Nat}}\mathsf{Matrix}(n,n+1)$ or $\prod\_{b:\mathsf{Bool}}\mathsf{if}\ b\ \mathsf{then}\ \mathsf{Nat}\ \mathsf{else}\ \mathsf{Bool}$.

It makes more sense to consider Java a fragment of System $\text{F}\_{\<:}$ which is not a dependent type system at all. Even then it is a rather weak fragment of it. There's a variant of System F called System F$\omega$ which supports full type level functions, essentially lambda at the type level (not to be confused with type-lambdas which relate the value and type levels and System F already has). Neither Java nor Haskell can do this. The only type level "functions" either (standard) Haskell or Java can make are compositions of uninterpreted functions. There is no computational behavior at the type level. Java is further restricted because it doesn't have (nor need) a kind system because it lacks higher-kinded types. That is, you can't have a type level "function" with "type" (i.e kind) $(\mathsf{Type}\to\mathsf{Type})\to\mathsf{Type}$ for example. This is why you can't make methods that operate over arbitrary monads in Java. Returning to just System F, System F has arbitrary rank types. This means you can nest $\forall$ as deeply as you like — you can use it freely. Neither Java nor Haskell (without extensions) supports this. I believe both of them can indirectly capture some higher rank types, but neither can express the type of Haskell's $\mathsf{runST}$ which requires extensions and is $\forall a.(\forall s.\mathsf{ST}\ s\ a) \to a$.

So Java is more expressive than the rank-1 types as captured by the Hindley-Milner type system but far less expressive than System $\text{F}\_{\<:}$. It doesn't support any form of dependent typing. Featherweight Java as introduced in Featherweight Java: A Minimal Core Calculus for Java and GJ by Igarashi, Pierce, and Wadler provides a simplified, idealized calculus specifically geared toward Java. There is almost certainly a paper that directly compares/reduces Featherweight Java to System $\text{F}\_{\<:}$. The upshot is Java's type system is not even remotely close to the power of MLTT. In terms of the lambda cube, ignoring subtyping, Java would be somewhere on the edge between $\lambda\\!\\!\to$, the simply typed lambda calculus, and $\lambda2$, System F. MLTT (or specifically the Calculus of Constructions) is $\lambda\text{P}\omega$, the corner opposite of $\lambda\\!\\!\to$. So describing Java in terms of MLTT would first require ignoring everything that made MLTT different from System F$\omega$ and then ignoring nearly everything that made System F$\omega$ different from System F.

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


# Question
Title: Solving Unary Constraint Satisfaction Problem other than branch and bound
I am solving a problem of planning a meal, where I need to fulfill requests such as *"create a two-dish meal that MUST have at most 2g of fat, the first dish MUST have 400kcal and SHOULD have at least 10g of protein, and the second dish MUST have 100kcal"* by returning a list of dishes from a predefined list. In other words, it takes soft/hard constraints on a meal as a whole and sets of soft/hard constraint on each dish slot as an input, and outputs an assigment of dishes to dish slots.

I modelled it as a Constraint Satisfaction Problem with all dish constraints being unary constraints and meal constraints being used for accepting/rejecting a solution as well as ranking. I wrote Depth-First Branch and Bound roughly following \[1\] (shortly, it constructs depth-first a tree of all possible assignments and prunes branches with a dish violating its constraints) and it works pretty well.(\*)

The problem is, I need another algorithm for solving that problem and - for reasons I can't change - it needs to be fully deterministic. Which is problematic, since:

* the whole meal planning research focuses on using various flavours of artificial intelligence,
* the few research papers that don't use AI, use onthologies and rule-based reasoning, but offer no details and constructing such is outside of my time budget and capabilites,
* all other algorithms I could find for solving Constraint Satisfaction Problem focus on the ones with binary constraints.

I have tried to find such algorithm for about two weeks, but found nothing. I feel like I'm missing an obvious solution, but I can't quite put my finger on it.

---

(\*) Of course, I plan to improve it by appriopriately integrating meal constraints into the search.

---

\[1\] Sundmark, Niclas. "Design and implementation of a constraint satisfaction algorithm for meal planning." (2005).

# Answer
> 2 votes
A pragmatic approach will be to formulate this as an instance of integer linear programming, and feed the system to an off-the-shelf ILP solver. The details of exactly how to do that will depend on the specific kinds of constraints you have. There are many tutorials on integer linear programming, so you might start there.

If you need the solution to be deterministic (so solving the same problem multiple times is guaranteed to give the answer), and if you're not sure whether your ILP solver is deterministic, you can define an ordering on solutions (e.g., lexicographic search) and then use binary search to find the "first" valid solution out of all optimal solutions.

---
Tags: algorithms, branch-and-bound, planning
---


title: Constrained optimization topics

text:
# Question
Title: Constrained optimization topics
Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$.

I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X\_{ij}$ is 0 or 1). So, $p\cdot q$ variables. The function $f(X)$ is given by $$ f(X) = \sum\_j \sum\_i C\_{ij} X\_{ij} - \sum\_j p(X,j), $$ where $C$ is a matrix of constants and $p$ is a penalty function (basically could be rewritten as a loose constraint as far as I can tell): $$p(X,j) = \max(0, \sum\_i X\_{ij} - D\_j)^2,$$ where $D$ is a vector of constants.

As hard constraints we got that $X\_{ij}$ is binary, and $$c\_i(X) = \sum\_j X\_{ij} \leq E\_i,$$ where $E$ is a vector of constants

I found linear programming is a topic that solves problems like this, and then found constrained optimization which would be more or less what I want, although I don't know how to write max() into inequalities. I suppose I could try to split the solution if the conditional branch was enforced on a single variable, but there are several conditionals at the same time anyway. Out of my searches the penalty method looks extremely similar to my equations, but there's the hard constraints that haven't been merged into the main function.

I request the exact topic I can research, I'm a bit confused as all of this is new to me and I'm not sure I'm studying the right topics.

# Answer
> 1 votes
This can be formulated as a mixed-integer quadratically constrained quadratic programming (MIQCQP) problem, integer programming with quadratic constraints and a quadratic objective function. You can find off-the-shelf solvers out there, and I think some of them support MIQCQP. Unfortunately MIQCQP is a pretty hard problem, so it's hard to know whether this will be effective, for the size of problem you have. But it could be worth a try.

You can encode the max by the two constraints $p\_j \ge 0$, $p\_j \ge (\sum\_i X\_ij - D\_j)^2$, where $p\_j$ is a variable representing $p(X,j)$. Since you're going to minimize a sum of $p\_j$'s, this suffices (the minimization objective will chose the smallest $p\_j$ that satisfies both inequalities, which is the max).

---

Alternatively, if you're willing to remove the "squaring" in the definition of $p(X,j)$, this could be formulate as an instance of integer linear programming.

---
Tags: terminology, optimization, reference-request
---


# Question
Title: Should one limit the maximum level of a skip list node?
In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called *fix the dice*, limits the level to our previous highest level plus one if a higher level was randomly chosen.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p \< 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.

# Answer
Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance.

The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a *demoted item*.

Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)

The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log\_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log\_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.

Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:

$$\mathscr{E}'(l) \in \[\mathscr{E}(l)-l-1, \mathscr{E}(l)+1\]$$

Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate

$$\mathscr{P}'(l) \in \[\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}\]$$

But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.

In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.
> 4 votes

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: Would it ever be possible for computer viruses to evolve new "genes" to allow them to perform their job?
As an A-level Biology student, I have thought a lot about the links with Biology and Computer Science, and something that often comes to mind are the links between Immunology and Computer Security/Viruses. For example, I (through reading about how the anti-virus programs work) decided that the way the immune system handles viruses is very similar to anti-virus programs (both contain a database of virus definitions (be it, $\beta$ memory cells or virus signatures) and both contain a method of extrapolation). The natural progression for me was then thinking about natural evolution of viruses compared to computer viruses. So on to my question:

Would it ever be possible for computer viruses to evolve into new strains which possess new "genes" to allow them to perform their job?

It seems like this sort of thinking could only really apply to viruses, I mean your regular old calculator is never going to be subject to "natural selection". But as far as I know viruses *do* mutate themselves, in order to avoid anti-virus programs, but presumably these are rather controlled, so that the virus wouldn't gain non-beneficial mutations that might otherwise render it useless. If the true random nature of nature could be applied to viruses, would they ever be able to evolve new functionality, like for example becoming a retro-virus that takes over an anti-virus program, or mutating to include new code that allows it to bring down a firewall? Would they be involved in some sort of computational natural selection, where the strongest viruses survive and pass on their beneficial genes?

# Answer
> 8 votes
I suppose it would be possible in theory, but computer malware (viruses, worms, etc.) typically don't work this way today, and there are good reasons why they're written the way they are.

You might be interested in polymorphic code, which changes itself to evade detection. It changes the sequence of instructions to some other sequence of instructions that will have the same effect, but will have a different binary. This helps evade detection by anti-virus tools that are looking for a specific "signature" of bytes. However, this is not the form of mutation you are asking about, because it will never cause the malware to "evolve" some new behavior it didn't already have.

Really, there is not much reason why malware authors would want or need their malware to evolve new functionality. They can either build the desired behavior into the malware. Or, they can have the malware contact a central "command & control" server to download new code ("software updates" for the malware) periodically, to let them control the behavior of the malware. Usually the bad guys work out offline what attacks they want to mount, and then implement this in the malware or command the malware to perform those attacks.

By working out the attacks offline, in advance, the attackers can test those attacks on their own systems and make sure they'll work properly and won't be detected. From the attacker's perspective, this is a lot better than writing malware that randomly tries stuff in hopes it'll evolve to a useful attack; malware that tries random stuff will be a lot more likely to set off alarms and be detected.

So, there's not really any need or motivation for using "natural selection" in malware, and it's not typically seen in practice.

# Answer
> 5 votes
TL;DR: computers are not autonomous entities like organisms, with any survival instinct. They just run instructions, and sometimes they run instructions we don't like, so we run other instructions to find the bad ones.

---

I started to say this in the comments, but I think there's a lot more to be said.

The virus metaphor is outdated and too widely used by people who don't understand how computers actually work. They try to liken them to living things, because they understand living things. Here's a better metaphor.

You are an office worker. You work for a giant mega-corporation, where you don't see your boss. You aren't ever told why you do your job, you don't even know what your company does. All you know is that you show up to work every day, and you follow your instructions.

There's a little window by your desk, which is the only way you ever interact with anyone else. You don't see anyone, but sometimes pieces of paper come through the window.

Your instructions are always the same at the start, but you have a huge pile papers at your desk. Some of these contain instructions, some of them contain things you've written. Sometimes your instructions will tell you to find a different piece of paper, and start using it as your instructions. Sometimes they tell you to change the pieces of paper, ripping them up, or erasing parts of them. (This is what running a program is. Sometimes programs edit files, sometimes they run other programs, etc.)

Sometimes your instructions tell you to wait by the window for more paper to come. The paper might have a picture on it, it might have text, or it might have more instructions. (This is what happens when a computer waits for mouse input or keyboard input, or something from a network (i.e. files)).

You do nothing but follow these instructions. You never know why, you never know for whom, but you just do it.

Sometimes, your instructions tell you to multitask. You have a pile of papers. You set a timer, and you work on the instructions from the top paper for 5 minutes. When the timer goes, you put that paper on the bottom of the pile, and do whatever is on the new top paper. (This is how computers run more than one program at once).

Now one day you're waiting for a piece of paper by the window, and you know when you get it, you're going to do whatever it says, because that's what the last piece of instructions told you to do. You get it, and it says to find some of your main pieces of paper, with your core instructions, and erase them. It tells you new instructions to put there. These are doing some strange things, like sending your files out the window to strange places, or collecting backup copies of all the things that come through the window. But what's important is, you don't think anything of it. They are just more instructions. You just do them.

This is what a virus is. It's just a set of instructions that you trick the computer into running.

Now, say you're a multitasking worker. You get one of these erasing instructions in the window. But, you're busy, so you put it onto the bottom of the pile. You look at the top of your pile of stuff to do, and there's a set of instructions marked "antivirus". It says to read through all your papers, and see if any of them look like their sample paper. You do, and you see that the erasing instructions is on your list.

Note that if you start running the virus instructions, you don't think anything of it. Without an antivirus, there is no attack, there is no immune response. It's not attacking you, it's just a set of instructions. The antivirus is just a TODO list that involves looking at your other instructions and finding ones that match a pattern. It's not trying to preserve the system as a whole, it's just a sheet of paper that someone gave you from the window, because it prevents other people from tricking you into doing stuff by putting stuff through the window.

Now, what about your "evolving" viruses? This is certainly possible, but let's look at what this entails. An evolving virus is basically a sheet of instructions that tells you how to make more instructions. It's a piece of paper that tells you to erase a bunch of your old instructions, and then put new ones in its place, but those new instructions also tell you to erase old instructions, and put new ones, and so on. So the original instructions aren't changing. The virus isn't mutating. Instead, it's just doing whatever it does, while also leaving behind instructions to create its next generation.

So, is it possible to do this? Yes. But it's extremely complicated. To have a program that changes itself, but having that sequence of changing not eventually converge to a program that does nothing useful, is incredibly complex.

# Answer
> 4 votes
the general question is about evolution in malware. the specific question is about genes. there is indeed a genetic algorithm mechanism that uses digital "genes" for optimization & could certainly conceivably be used in viruses/malware, although there do not seem to be any reports of this so far "in the wild". on the other hand, malware has indeed been evolving over many years from more of a theoretical curiosity to one involving organized cybercrime etcetera, with increasing sophistication in the threats. so far this is fueled largely (but not entirely!) by human-developer-driven "evolution". computer viruses can in some sense be said to be generally evolving increased "intelligence" or "attack sophistication" over time.

here are some references that study the "evolution of/in malware".

# Answer
> 1 votes
The main thing is getting it up and running. Naive versions, i.e. Taking an existing somewhat-successful piece of malware, and making every reproduction attempt have mutations, would likely be lethal to the malware in most cases.

This does not, however, mean, that it could not evolve, just that its original purpose, replication, might be hindered. With a low enough mutation rate and enough patience, beneficial and benign mutations would eventually be selected for.

One problem, however, is that they WOULD evolve. Specifically, they would evolve on pure Darwinian principles. If I write a piece of code that executes, and then, only on successful execution, copies its binary file 1000 times to 1000 locations with a random error or several in each and executes them all, it might seem like I have made replication contingent upon completing whatever task is being done successfully, but in reality, replication is only contingent upon the program THINKING it has completed that task successfully.

So there is a fair chance that if this were a piece of malware, its two basic aims, specifically, replication and screwing up people's computers, would be at odds with each other. Over a sufficiently long time, a mutation would probably arise to either make it not screw up their computers as badly, making it less important for anti-virus to deal with, thus, replicating with minimal symptoms, as is the most effective early strategy in pandemic or plague inc, or make it lie to itself that it even succeeded in screwing up their computers at all, turning the primary function into an intron fairly quickly upon it failing to execute but the replication function continuing to work.

Many people marvel at the effectiveness of the immune system in defeating all manner of threats, but in a lot of ways, computers are much, much more secure than cells. Your computer can actually just not download a virus in the first place. A perfect anti-virus system with a perfect user doesn't need to scan the hard-drive ever. Computer code cannot just be inserted physically into the hard-drive.

Contrast cells, where viruses have evolved some rather unique PHYSICAL mechanisms of slipping past cell's defenses. For example, some viruses are totally inert until they encounter a cell, but then their physical structure grabs onto and violently punctures the cell membrane to inject their genetic material. This is like a computer virus that physically cuts open your machine and adds new hardware while your OS and antivirus think "this is fine," and execute code found on that hardware.

So it is actually fairly likely that the more benign the code, the better reproduction it can do. In some cases, it might be easier for evolution to convince the user to help it than to evolve new anti-virus. I.E. appending itself to files that are likely to be shared with other users.

So ultimately, it seems more likely to me that the chance of replication is higher when it is useless as a piece of malware as such, and probably higher still if it can convince the user or anti-virus code that it is in fact something benign, important, or beneficial.

Another thing is that most machines have invalid operations, so random edits to code are likely not only to prevent functionality, but also simply cause the code to crash, even with unprotected memory.

# Answer
> 0 votes
Imagine non-malicious computer programs as the microbes in your gut. Imagine a computer virus as a infectious bacteria.

The computer can't tell the difference between the good bacteria and the bad bacteria, unlike the immune system.

It would be simple to make a self-modifying program, but 99% of mutations would result in an error. A program is like a list of instructions - and computers are very strict about how those instructions are written. Say we have this program:

1. Add one tablespoon of peanut butter.
2. Add one tablespoon jelly.
3. Put bread on top.

A mutation might result in this program:

1. Add one tablespoon of peahut butter.
2. Add one tablespoon jelly.
3. Put bread on top.

Although it's clear to the human it was meant "peanut", that's not clear to the computer. I could write a simple script that mutates itself in Python - but most of the time mutations will make it fail.

It would be very interested in a virus that mutated itself and could remain alive - we might even classify it as life.

---

*Yes, I'm late to the party - but this is an interesting topic worth writing about.*

---
Tags: security, evolutionary-computing
---


title: Is this unambiguous grammar equivalent?

text:
# Question
Title: Is this unambiguous grammar equivalent?
I have a simple context free grammar $(\\{A\\}, \\{(,)\\}, R, A)$, which consists of this one production rule:

$A \rightarrow AA\\, \vert\\, (A)\\, \vert\\, \epsilon$

I believe this is ambiguous! For example, I can represent "()" like this:

I'm sure there are an infinite number of these. I've attempted to make the grammar unambiguous whilst ensuring that the same language is accepted:

* $A \rightarrow AA\\, \vert\\, B$
* $B \rightarrow (C)$
* $C \rightarrow \epsilon$

How can I be sure that this captures the same language and is no longer ambiguous?

# Answer
> 2 votes
1. Although determining whether grammars are ambiguous is undecidable, in the case where the grammar has a rule of the form

$$T\to T\\;T$$

then either the grammar is ambiguous or the rule is useless. (Because $T\\;T\\;T$ can be reduced in two ways.)
2. Determining the equivalence of two CFGs is also undecidable so there is no general solution to the equivalence question. But you could try to prove that both grammars generate the Dyck language.
3. A simple deterministic grammar for that language is

$$S\to \epsilon\mid(\\;S\\;)\\;S$$

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


# Question
Title: Why does a Turing machine recognise exactly one language?
I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?

# Answer
> 30 votes
The language recognized by a Turing machine is, by definition, the set of strings it accepts. When an input is given to the machine, it is either accepted or not. Any particular input to that machine is either always accepted (in the language) or always not accepted (not in the language). So there's no mechanism by which a single Turing machine even could accept more than one langauge.

# Answer
> 10 votes
Think of it this way: a TM is like a computer with a loaded software. Each software does one thing, right? E.g., think of your computer and assume it has only 1 program loaded in it. Then PC+"photoshop" only does photoshop, while PC+"mine sweeper" only sweeps mines.

So a Turing machine is a very simple creature, that on each run gets a single input and outputs either a *yes* or a *no*. On which inputs it says yes, and on which it says no -- this is set by the "program" of the TM as determined by its states and transition function. Once these are fixed, the "program" is fixed, and for any given input there is only one answer: *Yes* or *No* (accept/reject). This defines exactly a single language = all the inputs that yield a *Yes* when given to the TM.

On the other hand, the **set** of **all** TMs is equivalent to the set of computer+"software" with all possible programs. Now more languages can be decided - but still, each specific TM decides (or recognizes) only one language.

# Answer
> 4 votes
**Turing Machine work as they do because we choose to define them so.** We could have more sophisticated definitions, but the question is whether it would serve a purpose, whether it would allows us to do more things. And, as far as we know, the answer is no.

It is very easy to make models of Turing Machines that recognize two languages. Given languages $L\_1$ and $L\_2$, we could define a TM with 2 kinds of accepting state: one for $L\_1$ and one for $L\_2$. A TM would be said to accept $L\_i$ if it enters at some point a corresponding accepting state. But it would resume computation to see whether it can also enter the other kind of accepting state. And we could require that it later halts, or possibly not. You could then build the entire theory on such machines. It would works and be a lot more complicated than what we usually do.

To answer David Richerby statement that "*there's no mechanism by which a single Turing machine even could accept more than one language*", it is only because we choose not to consider such mechanisms. Even if you restrict TM to the very standard model, you could say that the input is recognized to be in language $L\_1$ when the TM halts in an accepting state with an odd number of steps, and it is in $L\_2$ when the TM accepts with an even number of steps. Thanks to non-determinism, this would not prevent the TM from recognizing both of two intersecting languages.

The point is that all kinds of variants can be used to do the theory. Also very different approaches have been tried to model what is computation, such as lambda-calculus, compinatory logic, recursive functions theory, and more.

It has always been shown that none of them does anything that cannot be done by our simple model where TM recognize only one language. To such an extent that it has been conjectured that it does anything that can be done. That is called the **Church-Turing thesis**. It is the cornerstone of computability theory, that, as far as we know, determines what languages are recognizable, or not.

So we might as well use a simple model, since a complex one will make our life harder, without any real benefit.

Of course, we sometimes use other models because they allow us to better understand some issues.

# Answer
> 3 votes
A Turing machine recognizes one language because that's the definition of the word *recognize*: The language a Turing machine *recognizes* is the set of all strings/inputs for which the Turing machine accepts.

# Answer
> 3 votes
I'd like to expand on one point in Richerby's answer:

> When an input is given to the machine, it is either accepted or not.

The reason for this is that the Turing machine is deterministic: given the same input and starting state, it will always do the same thing every time you run it (either terminate in the same accept state or in the same reject state, or loop forever).

Additionally, we can easily prove that every Turing machine recognizes exactly one language:

Suppose, by contradiction, that a Turing machine M recognizes two distinct languages L1 and L2. Since L1 and L2 are distinct, there must exist a string S that is in L1 but not in L2 (without loss of generality - it could be the other way around but the proof would proceed in the same way from here with L1 and L2 exchanged). Now run M on S. If it accepts, then a contradiction is reached because then S would be in L2. If it doesn't accept (rejects or loops), then a contradiction is reached because S would not be in L1.

# Answer
> 2 votes
The answer to this depends on what exactly you understand when you mean "Turing machine". There is three components to any computational model (restricting to deciders/acceptors here):

* syntax,
* semantics,
* acceptance criteria.

For Turing machines, *syntax* would be the tuple of state set, alphabets, transition function, and so on. The *semantics* would the definition of a *computation*, that is to describe how to apply the transition function in order to derive the tape content after some steps. The *acceptance criterion* is to say, "when this happens, we stop and the result is that".

Now, are Turing machines only syntax and semantics to you, or do you include the acceptance criterion as well? If you do the former, any TM can accept multiple languages by using different acceptance criteria; you can even conceive acceptance critera that allow for multiple accepted languages (think about two-parameter TMs, for instance). If you do the latter, however, there is no wiggle room and the usual acceptance criterion does indeed allow for exactly one language per TM (of this type).

The *usual* definition and usage of the term in TCS includes all three components. That makes sense because, in particular, changing the acceptance criterion can change the class of objects the automaton represents *drastically*, so we *need* to fix the criterion in order to know what we talk about.

As an example, compare finite automata and Büchi automata. Syntax and semantics are exactly the same, but one accepts finite words while the other accepts infinite words!
Try to figure out what happens if you plug the acceptance criterion of Büchi automata into the TM definition.

Now, why is the usual acceptance criterion a meaningful one? As long as you restrict yourself to language of finite strings, not much will change by having multiple languages per TM, on the conceptual level: we will still be able to accept the same set of languages. So we stick to the simpler model. That is not to say, however, that a more involved model can not be useful for modelling in applications -- but that's beyond the scope of TCS (which holds definitorial authority).

# Answer
> 0 votes
Suppose we have a TM $M\_{1}$ that recognizes $L\_{1}$ and $L\_{2}$ where $L\_{1} \neq L\_{2}$. Suppose there is a string $s\_{1}$ where $s\_{1} \in L\_{1}$ and $s\_{1} \notin L\_{2}$. Then $M\_{1}$ accepts $s\_{1}$, but $s\_{1} \notin L\_{2}$ so $M\_{1}$ cannot accept $s\_{1}$, thus we have reached a contradiction. The other case plays the exact same, eg $s \in L\_{2}$ and $s \notin L\_{1}$. Therefore, a TM accepts only one language.

To say a TM $M$ recognizes a language $L$ means that for every string $s \in L$, $M$ accepts $s$, and for every string $s$ that $M$ accepts, $s \in L$.

$s \in L \iff M$ accepts $s$

To understand the existence of non-recognisable languages, consider the definition of decidable languages. To say a language is decidable means that the language is recognizable and co-Turing recognizable. If there were no non-recognizable languages, then every language would be decidable. This is false, see $A\_{TM}$.

# Answer
> -3 votes
no other answers point out the existence of the Universal Turing Machine(s) as first described/ discovered by Turing in his halting proof. yes a TM accepts a single recursively enumerable language, but the UTM can recognize any recursively enumerable language if it is encoded on the input along with the input string. so the question has some zenlike quality. TMs both accept only a single language and all possible encodable languages.

# Answer
> -3 votes
A language is a set of strings. Isn't the union of two languages L1, and L2 a set of strings (let's call it L3), and so would be another language? Then, if the Turing machine recognizes both languages, it recognizes L3, a single language.

---
Tags: turing-machines, computation-models
---


# Question
Title: Is there a strong argument to use shell sort over insertion sort on an array of 10 elements
I'm trying to come up with an argument of why shell sort should be used over insertion sort for an array of 10 elements. And I'm wondering if there is one at all. I know that insertion sort is more efficient for the mostly sorted array, but in all other cases the shell sort should be faster. Or there will no significant performance difference for the array of 10 elements?

I have no knowledge about the data of an array.

# Answer
> 1 votes
It's an empirical question. First you need to come up with a probability distribution on arrays, for example the uniform distribution on all permutations of $1,\ldots,n$. For each $n$, you can measure the running time of both algorithms, and see which performs faster. The threshold 10 in reality depends on the implementation and the CPU, and is quoted only because it's a "nice" number, functioning as a rule of thumb.

So far I have assumed you're interested in minimizing the *average case* running time. If you're interested in the *worst case* running time, you'll have to run the algorithms on *all* permutations, which will quickly become infeasible.

---
Tags: algorithms, sorting
---


title: Loop invariant for a while loop

text:
# Question
Title: Loop invariant for a while loop
I need help understanding why the two statements I have underlined with red are correct. I am confused as to how we can get $n + 1$.

And how $i \le n$ is true when it says $i \< n$ in the while.

# Answer
> 1 votes
The loop invariant should hold before and after each iteration of the loop. In particular, it should hold before the loop starts and after it ends.

# Answer
> 1 votes
1. Why $i \leqslant n$: because this program checks $i$ first and **only then** adds $+1$ to it.
2. When $s := s + i + x$ is applied, $x = n - i + 1$. Substituting $x$ to original formula we get $s := s + n + 1$. It is equal to $(n + 1) i$.

---
Tags: algorithms, loop-invariants
---


# Question
Title: Smaller approximation ratio for larger input size?
Is it possible for an approximation algorithm (for minimization optimization problem) to obtain smaller approximation ratios for inputs of larger size? For example, is $1/n$- or $1/\log n$-APX reasonable? If it is, do you know any natural problems?

# Answer
In most cases it is possible to artificially enlarge an instance. For example, if you want to solve MAX-CLIQUE, you can add an independent set. In these circumstances, the approximation ratio cannot improve as the size of the instance gets larger. However, it is possible that there are some natural problems in which the phenomenon you describe does occur.
> 1 votes

---
Tags: terminology, optimization, approximation
---


# Question
Title: Generating function of non-regular language
Let's say $\sum\_{n \ge 1} a\_{n}x^n$ is generating function for regular language $L$. $a\_{n}$ is number of words with length $n$.

Find an example of generating function which isn't correspond for any regular language.

My attempt : I use the fact for any regular language there is exists $n\_{0}$ $\lambda\_{i}$ and $p\_{i}$ : $a\_{n} = \sum\_{i} \lambda\_{i}^{n} p\_{i}$ and as example get language with $a\_{n} = C\_{n}$ , where $C\_{n}$ is Catalan number. My teacher said that's not obvious and told me to get easier example. But I don't know useful criteria to find an example with contradiction about regularity. Any ideas?

# Answer
> 1 votes
If we apply a substitution that maps all letters of the alphabet to the same letter, we obtain a unary language. This shows that if $L$ is regular, then the set $\\{n : L \cap \Sigma^n \neq \emptyset\\}$ is eventually periodic. This shows that $\sum\_{n=0}^\infty x^{n^2}$ corresponds to no regular language, for example.

# Answer
> 1 votes
Here is a convoluted way:

* There are inherently ambiguous CFLs (context-free languages), see e.g. (1).
* Every regular language corresponds to a DFA.
* Every DFA can be expressed by an unambiguous CFG.
* Hence the inherently ambiguous CFLs cannot be regular.
* Now the generating function for the inherently ambiguous CFLs do what you are looking for.

In particular (1) states: "if the counting generating function is transcendental over $\mathbb{Q}$, then the language is ambiguous", hence not regular.

---

<sub> 1. F. Bassino, C. Nicaud: *Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages*.

</sub>

---
Tags: regular-languages
---


# Question
Title: Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori
A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n\_{min}\le n \< n\ast\\1, &n\ast\le n\le n\_{max} \end{cases} ; n \in \mathcal Z $$

The goal is to search for $n\ast$. The bounds $n\_{min}$ and $n\_{max}$ are known apriori.

**A salient property of $n\ast$ is that it has a higher probability of lying in a region around $\hat{n}$ (known apriori).** The exact probability distribution, although unknown, (probably doesn't matter) can be considered as continuous CDF having a higher weighting factor around $\hat{n}$

I have already implemented a simple binary search, but I am looking for more efficient solutions that somehow account for the given probability information (i.e. $n\ast$ is concentrated around $\hat{n}$), I am looking for an efficient algorithm to find $n\ast$. without losing accuracy.

I know that Binary search is worst-case $\mathcal{O}(log\ n)$, but $f(n)$ is so computationally expensive that I can't afford even this.

# Answer
If you knew the distribution of $n^\*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of *expected number of queries* (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^\*$ given queries of the form "$n^\* \leq x$", which you can easily implement by checking $f(x)$. We assume that the probability that $n^\* = i$ is $p\_i$.

Gilbert–Moore algorithm: Partition the unit interval $\[0,1\]$ into intervals of length $p\_i$, and let $x\_i$ be the midpoint of the $i$th interval. We locate $n^\*$ by doing binary search on $\[0,1\]$. For an interval $I \subseteq \[0,1\]$, denote by $X(I)$ the midpoints $x\_i$ which are found in $I$. We first ask whether $n^\* \in X(\[0,1/2\])$. Depending on the answer, we ask whether $n^\* \in X(\[0,1/4\])$ or whether $n^\* \in X(\[1/2,3/4\])$; and so on. Eventually we reach an interval $I$ such that $X(I)$ is a singleton, and we have found $n^\*$.

Horibe's algorithm: Find $x$ that minimizes $|\Pr\[n^\* \leq x\] - 1/2|$, and ask whether $n^\* \leq x$. Denote by $I$ the values of $n^\*$ conforming to the answer. Find $x$ that minimizes $|\Pr\[n^\* \leq x \mid n^\* \in I\] - 1/2|$, and ask whether $n^\* \leq x$. Update $I$, and repeat until $I$ becomes a singleton.

Both algorithms find $n^\*$ using at most $H(n^\*)+2$ queries on average (where $H(n^\*)$ is the entropy of $n^\*$), compared to the trivial lower bound $H(n^\*)$, so they're pretty good.

In your case, you don't know the distribution of $n^\*$, but you can make a guess, use one of these algorithms, and hope for the best. If you have several distributions in mind, you can choose one of them to construct an algorithm, and then check their performance on the other distributions, comparing the expected number of queries to the trivial lower bound.

You could also want to optimize some other quantity – for example, the 99th percentile of the number of queries. In that case the algorithms described above will probably still be pretty reasonable.
> 2 votes

---
Tags: search-algorithms, search-trees, balanced-search-trees, binary-search, binary-search-trees
---


# Question
Title: Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree
From Wolfram:

> A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks 1982; Skiena 1990, p. 181).

What are the running times of such algorithms, in terms of size of the graphs? What algorithms are used in practice for graph isomorphism?

# Answer
> 2 votes
Algorithms used in practice differ a lot from theoretical algorithms. One popular software package is nauty. The link should also explain the algorithms used, which probably rely on combinatorial methods.

As for the running times for specific algorithms, they are likely stated in the papers. I suggest checking the references.

---
Tags: graphs, graph-isomorphism
---


# Question
Title: Is the language $L=\{a^nb^mc^k | k \ge max (m,n) \}$ CF
I'm trying to prove that the language $L=\\{a^nb^mc^k | k ≥ max (m,n) \\}$ is not CF. I consider the word $\alpha = a^pb^pc^p = uvxyz$ and i break the proof to the following cases :

1) if $vxy = a^l, b^l$ or $a^kb^l$ for some $k,l \le p$ i pump the word up, so $a^l+s, b^l+s, s \> 0 : l+s\<p =\> \alpha \notin L$

2) if $vxy$ consists any $c$ then it can't consist any $a$s so if we pump down then $c^u, u = p - l, l \> 0 =\> N\_{c} \< N\_{a} =\> \alpha \notin L$.

But i keep thinking relying on my intuition that L is CF, because L build on the rule : if we print a then we print c, if we print b we print c, or we just print c. Looks like CF. My question is is my proof wrong or my intuition?

# Answer
Your intuitive argument is wrong. If you print a $c$ for every $a$ or $b$ you see, then the language will have $k\ge m+n$ rather than $k\ge \max\\{m,n\\}$.
> 1 votes

---
Tags: context-free
---


# Question
Title: Unrestricted grammar to generate $a^{n(n+1)/2}$
I have been asked to find a grammar that will generate the language $a^{n(n+1)/2}$, where $n\ge1$ as an exercise. Any idea on how to set up such grammar? Any help would be appreciated.

# Answer
*Hint:*

$\sum\limits\_{n=1}^{m}n=\frac{m(m+1)}{2}$
> 3 votes

# Answer
I came up with an idea while trying to solve my question. The length of the input string should be n(n+1)/2 =\> (n^2 + n)/2. We know how to generate a unrestricted grammar for the language a^(n^2)b^n.In this problem, each b will be replaced by an a. Thus, the string's length will be (n^2 + n) . However we need half of this string. In order to Decrease the number of a , I changed the rules such as that a new symbol,D, would be created and it would be responsible for the deletion of an a. Basically the grammar looks like this:

* S -\> LS'R
* S'-\> XS'YB
* S'-\> e
* BY-\> YDB
* XY-\> YaX
* aY-\> Ya
* Xa-\> aX
* LY-\> DL
* DR-\> RD
* XR-\> R
* La-\> aL
* BR-\> Ra
* LR-\> e
* Da-\> e
* DY-\> YD
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: SQL, optimizing a select statement in relational algebra
is it possible to rewrite the following sql statement $\pi\_{R.a,S.d} (\sigma\_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}((R\times S)\times T))$ ?

My problem is, i dont know if it is possible to split $\sigma\_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}$ to $\sigma\_{R.b = "d"} \land \sigma\_{S.d \geq 100 \lor T.d \geq 200}$,because the rules say i can split $\sigma\_{x \land y}$ to $\sigma\_{x} \land \sigma\_{y}$ but i am not allowed to split $\sigma\_{x \lor y}$.

Relations R(a,b,c), S(b,d) with a,d are integers, b,c,d are strings.

Edit: It is important to use brackets to specify which bool statements are compared, also if you have a statement that uses $ \land and \lor $ you are not allowed to not write the brackets, that was my major mistake. correct formular $\pi\_{R.a,S.d} (\sigma\_{(R.b = "d" \land S.d \geq 100) \lor T.d \geq 200}((R\times S)\times T))$

In this case we are not allowed to split the $\sigma$ statement because we are bound to the $\lor$.

We could split the $\sigma$ if the statement would be:

$\pi\_{R.a,S.d} (\sigma\_{R.b = "d" \land (S.d \geq 100 \lor T.d \geq 200)}((R\times S)\times T))$ to $\pi\_{R.a,S.d} (\sigma\_{S.d \geq 100 \lor T.d \geq 200}((\sigma\_{R.b = "d"}(R)\times S)\times T))$ Which would lead to a smaller kartesian product. At the end: What we are seeking is to bring the $\sigma$ as close to the leafs as possible to reduce our kartesian produkt

# Answer
> 1 votes
I suspect this is a homework question.

**Edit:** OK, you're trying to invent your own homework. Well done for trying. You might have bitten off too much.

We need first to sort out the headings of your relations. As per my comment above, Cartesian product must have no attributes in common between operands. I'll assume headings: `R(a,b), S(c,d), T(e,f)` -- that is, no `b` in common between `R`, `S`; no `d` in common between `S`, `T`. Then I don't need to put the dot-prefix on attribute names. Your question becomes:

$\pi\_{a,d} (\sigma\_{(b = "d" \land d \geq 100) \lor f \geq 200}((R\times S)\times T))$

(If you do want attributes in common, then instead of $\times$, use Natural Join $\bowtie$. And the whole point about *Natural* Join (a beautiful operation, at the heart of the Relational Model) is that it 'commons up' the attribute names. So you still don't need the dot-prefix.

And what it's trying to teach you is that the Boolean operators (AND `/\`, OR `\/`) within a Select expression (`sigma`) are equivalent to certain set operators over the relations.

**Edit:** OK you've shown one equivalent for $\land$, which is to push the $\sigma$ inside the $\times$. More usually, you'd use set intersection $\cap$.

Yes you are allowed to 'split' a selection that is a disjunction (your `sigma x\/y`). Think about what is the set-theoretic operator that's equivalent to disjunction.

**Edit:** The set-theoretic operator is union $\cup$. For both intersection and union, we need the headings of the operands to be the same -- that is, the full Cartesian product.

Also beware: what's the relative precedence of the disjunction vs the conjunction in that sigma expression?

**Edit:** OK, you've answered that. So the outermost operator is $\lor$. Let's rewrite that to $\cup$ between relation values:

$\pi\_{a,d} (\sigma\_{(b = "d" \land d \geq 100)}((R\times S)\times T) \cup \sigma\_{(f \geq 200)}((R\times S)\times T))$

Now in the left operand of $\cup$ we have a $\sigma$ with a $\land$. We can push that inside, as you've already shown. Similarly in the right operand we can push the $\sigma$ inside:

$\pi\_{a,d} ( ((\sigma\_{(b = "d")}R\times \sigma\_{(d \geq 100)}S)\times T) \cup ((R\times S)\times \sigma\_{(f \geq 200)}T))$

But notice in the right operand of $\cup$, we still have bare $(R \times S)$. So the union is going to include every `(a,b)` pair from `S`, and every `(c,d)` pair from `R`. (I suggest you try that out with a few sample sets of attribute values for those relations.) Your outermost projection, just takes `a` from `R` and `d` from `S`. So all the business with the $\sigma$s and $\land$, $\lor$ is rather pointless. And relation `T` is superfluous.

The most reduced form of your formula is:

$\pi\_{a,d}(R \times S)$

Or even:

$(\pi\_{a}(R)) \times (\pi\_{d}(S))$

---
Tags: database-theory, relational-algebra
---


# Question
Title: Finding solution of given recursive equation?
$T(n) = 1+ \sum\_{j=0}^{n-1} T(j)$
I've proved $2^n$ be the solution of this equation using induction. But is there any other way to find the solution? I just proved not solved.

# Answer
> 3 votes
The trick in this case is to consider differences: $$ T(n)-T(n-1) = \left(1 + \sum\_{j=0}^{n-1} T(j)\right) - \left(1 + \sum\_{j=0}^{n-2} T(j)\right) = T(n-1). $$ Hence $T(n) = 2T(n-1)$, and so $T(n) = 2^n T(0)$.

---
Tags: recurrence-relation
---


# Question
Title: Deciding whether the head of a TM remains in K slots?
I am trying to find the following:$$ \text{For a given TM M with initial empty tape is it possible to decide whether there} $$ $$\text{exists a constant K such that the head of M remains within the first K slots?} $$

I thought this was possible if you know $K$, since you could add the current configuration to a separate tape and understand whether the machine is looping or not as there exists finitely many configurations with length $K$. But what if you don't know this number? Is it still possible to find a TM that decides this language or is there a reduction from another undecidable language?

Any help will be appreciated.

# Answer
Hint: Given a Turing machine $M$, you can construct another Turing machine $M'$ with the following properties:

1. If $M$ halts then $M'$ halts.
2. If $M$ doesn't halt then the head of $M'$ eventually reaches the $K$th square from the right for every $K$.

This construction can be used to show that the halting problem reduces to your problem.

As you mention, given $K$, your property is decidable. This shows that your problem is $\Sigma\_1$-complete.
> 1 votes

---
Tags: turing-machines, undecidability
---