# Question
Title: Hash table versus binary search lookup for unchanging data
Let's say I have some static, unchanging data (no adds, modifies or deletes) which is looked up by a string value, and that I'm looking to minimize size in memory while also trying to minimize lookup time.

It seems to me that keeping the strings sorted in a list and then doing a binary search is always going to be better than a hash table since the hash table has memory overhead to store info about the buckets, and lookups ought to be slower unless I have a lot of buckets.

Is my reasoning correct? Are there any better data structures or algorithms for this situation?

---

**Implementation details**

My specific goal is to have a data structure which associates data entries with strings.

The data structure is meant to be friendly for disk serialization - where i can read the whole file into memory with one allocation and one disk read, and then do "pointer fixup" to make the data structure valid and usable.

This data structure is static (constant) and does not change. It's read only data, so the search for data entry by string function is the only operation that matters for execution time.

The size in memory of the data structure is also important, but is not as important as search time.

Below are the two options I described above, as I see them implemented, but let me know if you see anything that could be improved, or if there is something better I could do that is completely different!

---

**Binary Search**

This one is pretty simple. I'm leaving out details like fourcc in header, file versioning and proper syntax for avoiding padding in structs since they are out of scope of the algorithmic questions.

In the file, i would have a uint32 specifying how many entries there were.

Then, I would have the entries $0...n$, which might look like:

```
struct SEntry
{
  char *string;
  uint32 data; // or whatever data was associated with the string
}

```

Immediately after the last data entry, the file would then contain the (null terminated) string for the first entry, then the string for the second string, etc, all the way up to the last string for data entry $n$.

On disk, the char * would store the offset in the file to the string that it pointed to. This way, after i read the file into memory, i just add the address of the memory buffer to each char * to make it point at the (null terminated) string associated with that object.

To make data lookup by string fast, i'd sort the entries in the file by the string alphabetically, so that a lookup is $O(log\_2{N})$.

---

**Hash Table**

This one is only slightly more complicated.

The file would once again first contain a uint32 specifying how many entries there were.

A hash function would be used on the strings to output a $M$ bit hash. For more easy understanding let's assume it gives a 4 bit hash. The data entries would be sorted by what hash their strings gave, effectively grouping the data entries into 16 different groups, that were ideally evenly sized on average.

After the number of entries in the file, there would then be 16 SEntry pointers, which stored offsets to where each of those groups began in the file. On load, we would fix these up to point at the actual places in memory, just like the strings.

The strings would come after the last data entry, just like in the last file description.

Now, for searching this structure once it's in memory and fixed up, you hash your string with the same 4 bit hash, find where the bucket begins, and search all items in the bucket linearly until you find the item you are looking for, or until you reach the end of the bucket. You can find the end of the bucket by seeing where the next bucket starts. In the case of the last bucket, it ends where the first data entry's string begins. In the case of empty buckets, they have the same starting address as where the next bucket starts, so have a size of zero.

Searching this data structure is $O(N/16)$, more generally $O(N/2^M)$, which makes it get better lookup time as $M$ gets bigger, but there is also the memory overhead of $2^M$ uint32's in the file to store the information about the hash tables.

---

**Hybrid**

I also had the idea of doing a hybrid solution, where the hash table solution is used, but each hash bucket is sorted so that it can be binary searched.

---

**Analysis**

Let's say that a typical file (but neither best nor worst case) contains 20,000 items. That may not be very much in some circles, but these lookups are done in performance critical situations where microseconds matter, so needs to be as fast as possible, and also be as small as possible, because RAM is also precious, second to performance.

Going with the binary search, $log\_2{20000} = ~14$, so that means worst case is 14 string compares looking for a string that isn't there.

Going with the 4 bit hash function and 16 hash buckets, instead it is $20000/16 = 1250$, so that is a worst case of 1250 string compares, which is quite a bit. It only has 128 bytes of overhead for the hash table information though (16\* 64 bit pointers)

Going with an 8 bit hash table and 256 hash buckets, that is $20000/16=~78$, so worst case of about 78 string compares, and has 2048 (2KB) overhead for the hash table information (256\*64 bit pointers).

Going with the hybrid solution for the 4 bit hash, the 1250 worst case lookup becomes ~10 lookups worst case.

Going with the hybrid solution for the 8 bit hash, the 78 worst case becomes ~6 lookups.

That 8 bit hash hybrid setup only brings the count down to 6, from the binary searches 14.

It seems like binary search brings way more to the table than hash tables do in this situation, but that maybe a small bit count hybrid could possibly be helpful?

With these details, do you guys have any other recommendations?

Thanks!

# Answer
Have you considered "perfect hashing"? Basically you chose the hashfunction such that not collisions occur (every bucket has at most one entry). This is usually quite memory efficient, because you simply have a an array of values, no whole memory pages or linked list of objects to manage buckets (if you would do that). The plain array structure also makes it quite fast.

If you are concerned about memory efficiency you may also want to look into critbit-trees / binary tries. They store only the bits of the key that differ from other keys (more or less). This is reasonably fast and also quite memory efficient, especially with long keys, such as uint256 or arbitrary length. An example implementation is here (my code).

I'm not sure whether these structures fit your requirements, but I think they are worth mentioning.
> 3 votes

# Answer
Let me quote "Algorithms" by R. Sedgewick and K. Wayne:

> As a rule of thumb, most programmers will use hashing except when one or more of these factors is important, when red-black BSTs are called for. In Chapter 5, we will study one exception to this rule of thumb: when keys are long strings, we can build data structures that are even more flexible than red-black BSTs and even faster than hashing.

I am yet to read `Chapter 5` (though I suspect they hint at suffix tree, suffix array or similar) but in addition to Raphael's comment I would like to say that without a deeper understanding of your problem it is entirely possible that neither hashing nor BSTs might be the optimal datastructure.
> 2 votes

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


# Question
Title: Figuring out the language of a non-linear CFG
I have the CFG G with the following production rules: $$ S \to aSaS \mid b $$ Is it possible to find $L(G)$? I have no idea how describe it by any pattern. I use grammophone to check example words, but it's not very helpful tho.

# Answer
It's no wonder that you're having trouble with this; it's nasty. So as not to spoil the suspense, $L(G)$ is

> The set of all $w\in\\{a, b\\}^\*$ such that $w = a^{i\_1}b\\,a^{i\_2}b\dotsm a^{i\_n}b$ with $i\_k\ge 1$ for all $1\le k\le n$ and $$ \sum\_{k=1}^n i\_k=2n-2 $$

The proof is basically int two parts. First it's clear that any word generated by the grammar must end in $b$ and that no two $b$'s can be adjacent, so any word in $L(G)$ must have the form noted above.

To show the sum part, let's count the number of $S$'s, $a$'s and $b$'s in any sentential form that results from starting with $S$ and using either of the two productions of the grammar. Let $(s,a,b)$ represent these counts. We have

1. The production $S\rightarrow aSaS$ will change $(s,a,b)$ to $(s+1, a+2, b)$, since we're adding two new $a$'s and one more $S$.
2. The production $S\rightarrow b$ will change $(s,a,b)$ to $(s-1, a, b+1)$.
3. We start with the count $(1,0,0)$.
4. Note that production (1) followed by production (2) yields the same counts as we would have by using the productions in the opposite order, (2), (1). This observation isn't critical, but it means that we have a particularly pretty form when we apply the productions to the count tuples.
5. A count $(s,a,b)$ corresponds to a word in $L(G)$ only if $s=0$.

Starting with $(1,0,0)$ we now take D.W.'s tack and look at some small examples. Considering the counts with $s=0$, we find $(0,0,1), (0,2,2), (0,4,3), (0,6,4), (0, 8, 5)$ and so we guess that all the words in the language must have counts of the form $(0, 2n-2, n)$. We're done, right? Well, not quite. We need to show that (1) our guess about the counts was correct, and (2) that we actually can get any sequence of $i\_k$'s satisfying these conditions. Fortunately, both pieces are more or less easy to show by induction, though the second one is somewhat messy.

By the way, we can also show that any string in $L(G)$ must have length $3n-2$ and that there are $\binom{n}{2}$ such strings.
> 6 votes

# Answer
One standard way to find $L(G)$ is via "guess-and-check". In other words:

1. Generate many example words using the grammar. You might generate all words of length $\le k$, for some small $k$ (e.g., $k=5$ or $k=10$). Write down all of those words so you can stare at them.
2. Look for a pattern in this list of words. Make a guess at what $L(G)$ might be, based on the pattern.
3. Finally, prove your guess correct using the techniques described at How to show that L = L(G)?.

This can unfortunately get pretty tedious, and requires you to make a guess at the pattern.

In your case, the first few words are `abab`, `aababab`, `abaabab`, etc. Keep going: generate a longer list. Then, see if you can find any pattern.
> 2 votes

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


# Question
Title: How to express taking the next bit of an infinite string in small-step semantics?
I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational\_semantics).

Whenever this rule is applied, the next bit belonging to an infinite bit string must be taken. Therefore, in the premise of the rule, I have to express that the next bit of a (previously) fixed bit string is taken.

To represent the set of infinite (bit) strings, it is usually used the notation $\\{0,1\\}^{\omega}$.

So, the first idea is to write the premise of the rule in the following way: $ b= nextBit(str) \quad str \in \\{0,1\\}^{\omega}$.

What do you think about that? In my opinion, it doesn't make explicit that the infinite string $str$ is chosen once and then fixed. Is it something like

$ b = nextBit(str \rvert\_{str \in \\{0,1\\}^{\omega}})$

reasonable or it is too fuzzy/ non standard?

How would you express it explicitly that $str$ is fixed and it doesn't change during the run?

# Answer
In general, the only *persistent* pieces information in a deduction rule (like the ones in the wikipedia article) are the variables which are shared between one of the *premises* and the *conclusion* of the rule.

So in effect, a `findOne` function that operates on a given (fixed) string and returns the position of the first bit which is one would have to pass the string to the conclusion of the rule. Thus one possible formulation would be

$$ \frac{\mathrm{findOne}(str)}{\mathrm{findAux}(str,0)}$$

where `findAux` is defined by

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=0}{\mathrm{findAux}(\mathrm{getTail}(str),n+1)}$$

$$ \frac{\mathrm{findAux}(str, n)\quad \mathrm{nextBit}(str)=1}{n}$$

And `nextBit` is defined by other rules. One often uses pattern notation instead, so if strings of bits are represented $1.0.0.1.1.0.0.1\ldots$ (so concatenation is "$.$"), the first rule would be

$$ \frac{\mathrm{findAux}(0.str, n)}{\mathrm{findAux}(str,n+1)}$$

Note that the free variables $str$ and $n$ are implicitly *universally quantified*, so the first rule reads

> For *any* value of $str$, the value of $\mathrm{findOne}(str)$ is the value of $\mathrm{findAux}(str, 0)$.

Having "side conditions" such as $str\in\\{0,1\\}^\omega$ can clarify, but is usually clear from the context. Note that the $str$ in the premisse and the conclusion are the same, by definition of what a deduction rule is.
> 2 votes

---
Tags: semantics, notation, small-step-semantics
---


title: Construct SLR Parse table problems

text:
# Question
Title: Construct SLR Parse table problems
Consider the augmented grammar G is:

```
S` -> S
S -> a
S -> (T)
T -> T,S
T -> S

```

I have tried to construct parse table. But, when I read '(' nonterminal Symbol (item 3), there is no action table elements either 'shift' or 'reduce'.

```
I3:
S -> (.T)
T -> .T,S
T -> .S

```

so I can't construe '(a,(a,a))' in this Parse table. then is it ambiguous grammar? or I wrong the answer?

# Answer
> -2 votes
I3 productions are: S-\>(.T) T-\>.T,S T-\>.S here you need to add closure of S S-\>.a S-\>.(T)

---
Tags: compilers, parsers
---


# Question
Title: How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?
In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which are productions annotated with a position and a lookahead character.

It's known that given a state in an LR(1) automaton, the configurating set formed by dropping the lookahead tokens from each LR(1) item yields a configurating set corresponding to some state in the LR(0) automaton. In that sense, the main difference between an LR(1) automaton and an LR(0) automaton is that the LR(1) automaton has more copies of the states in the LR(0) automaton, each of which is annotated with lookahead information. For this reason, LR(1) automata for a given CFG are typically larger than the corresponding LR(0) parser for that CFG.

My question is *how much larger the LR(1) automaton can be.* If there are $n$ distinct terminal symbols in the alphabet of the grammar, then in principle we might need to replicate each state in the LR(0) automaton at least once per subset of those $n$ distinct terminal symbols, potentially leading to an LR(1) automaton that's $2^n$ times larger than the original LR(0) automaton. Given that each individual item in the LR(0) automaton consists of a set of different LR(0) items, we may get an even larger blowup.

That said, I can't seem to find a way to construct a family of grammars for which the LR(1) automaton is significantly larger than the corresponding LR(0) automaton. Everything I've tried has led to a modest increase in size (usually around 2-4x), but I can't seem to find a pattern that leads to a large blowup.

Are there known families of context-free grammars whose LR(1) automata are exponentially larger than the corresponding LR(0) automata? Or is it known that in the worst case, you can't actually get an exponential blowup?

Thanks!

# Answer
> 4 votes
The grammar

$$\begin{array}{l} S \rightarrow T\_0 \\ T\_n \rightarrow a \\; T\_{n+1} \\ T\_n \rightarrow b \\; T\_{n+1} \\ T\_n \rightarrow b \\; T\_{n+1} \\; t\_n \\ T\_N \rightarrow t\_N \end{array} $$

has the LR(0) state $$T\_N \rightarrow t\_N \dot \\\$$ expanded to $2^N$ variants in the LR(1) automata as all the partitions of $\\{t\_0 \dots t\_{N-1}\\}$ are possible look-head which appear in different contexts. The number of states in the LR(0) automaton on the other hand is linear in term of $N$. Thus an expansion factor of the order of $2^N/N$ is possible.

Edit: I'll have to check later when I've more time, I think adding $T\_N \rightarrow T\_0$ would give the exponential factor on nearly all the LR(0) states. That result in a shift-reduce conflict.

# Answer
> 0 votes
Such lower bounds are sometimes tricky to construct and may evoke deeper CS theory (eg in cases, complexity class separations). This paper seems to give a theoretical construction/ lower bounds you seek eg in Theorem 5 which puts a lower bound on total symbols and therefore also states. The references also include other similar constructions/ lower bounds.

> Theorem 5. Let $f(n,k) = 2^{\frac{1}{4}(n - k)} / n^2$. For any LR(k)-grammar with $k = 0,1;...,n−1$ generating $L\_n$; where $n \geq 3$; the number of nonterminal symbols must be at least $f(n,k)$ or there exists a nonterminal symbol A such that the number of different productions with A on the left hand side must be at least $f(n,k)$.

On the size of parsers and LR(k)-grammars / Leunga, Wotschkeb

---
Tags: context-free, parsers, lr-k
---


# Question
Title: Number of solutions to linear system of equations over GF(2)
Linear systems of equations over the reals have either 0, 1 or infinitely many solutions. However, when applied to finite fields (specifically GF(2)), infinitely many is not an option.

Is there a fast general method to calculate the *number* of distinct solutions to a linear system of equations over GF(2)?

You can assume that Gaussian elimination has already been performed, so an example augmented matrix would be:

$$ \left\[ \begin{array}{ccccccccc|c}1&0&0&0&1&1&1&0&0&1\\ 0&1&0&0&1&0&1&0&1&1\\ 0&0&1&0&0&1&1&1&0&0\\ 0&0&0&1&1&1&1&1&1&1\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&0\\ \end{array} \right\] $$

# Answer
> 2 votes
You can take any subset of the free variables, and then correct any resulting sum using the fixed variables.

Thus, after Gaussian elimination the total number of solutions is $2^f$ where $f$ is the number of free variables.

---
Tags: algorithms, linear-algebra, boolean-algebra
---


# Question
Title: Generative Machine Learning algorithms on tree structure
I'm looking into PCFG sentence grammar dependency structure parsing using StanfordNLP PCFG parser. It generates tree structures represented as a string like this:

```
 Happy new year => (ROOT (VP (VBN Happy) (NP (JJ new) (NN year))))

```

Or in a more visual way, the tree structure looks like this:

```
(ROOT
  (VBN (JJ Happy)
    (NP (JJ new) (NN year))))

```

Since some machine learning algorithms are generative, and I'm wondering if I group tree structures into two sets: one set contains sentences with negative emotions, one set on positive emotions. Can I use the machine learning algorithm to get the most commonly occurred subtree structure within each set?

I'm very sorry if I caused any confusion. First of all, I want to know if this problem is solvable in the realm of machine learning.

Remember topic modeling? Where the algorithm reads large chunks of text and generate similar topics and return keyword strings grouped together as a topic? One topic could be: `Gun, ship, sailer, ocean, fish, war, Gulf, oil`

It provides an insight into what computer understands what this document might be talking about, so we can compare it with what humans think.

However, what I want to do, is ask the question if I can find common syntactical subtree structures in a sentence that might indicate the attribute of this sentence: negative or positive.

No, I am not asking for a sentiment analysis classifier, and that is not my interest at all.

For example, (this is an unpublished study right now), as us humans, we can say certain things about the future, and it will appear in a special structure, like "I will go to the mall" or "I'm going to jogging." You can see that "will" or "going to" might appear in many sentences, and serve as a common grammatical/syntactical structure. Those structures can be spotted by us human beings (namely linguists), however, is it possible to let machine find such common pattern?

I know in data science, or in realm of machine learning, people use algorithms to find/generate common patterns. I can group my parsed sentences (as tree structures represented above) into two groups: negative group and positive group (NOT emotions, just names for two groups), and then I want to use this algorithm to see if one or multiple subtree structures are very common among the group so I can extract them out.

As I stated before, I only need two things:

1. Is this solvable in Machine Learning realm?
2. If it is, which algorithm should I use?

# Answer
> 1 votes
It sounds like what you want is a machine learning algorithm that works on trees, in the supervised learning context. I'd imagine there are probably many machine learning algorithms that could be adapted to this setting, but a natural one to try first is naive Bayes. So, let me sketch how to use naive Bayes in this setting.

First, we need a feature set. A simple feature set would be: each possible subtree that appears anywhere in the training set is a feature. So, in the example in the question, your feature set would include the subtree `(NP (JJ new) (NN year))` and `(JJ new)` and every subtree of every parse tree that appears in the training set. Let $S\_1,\dots,S\_n$ denote these $n$ subtrees. This gives you a bunch of features. Now you can label each sentence with its label (positive or negative); and for each, you know whether it contains that feature or not.

Now remember how Naive bayes works. We have a boolean random variable $Y$ that indicates the class of an item, and $n$ boolean random variables $X\_1,\dots,X\_n$ that indicate which features it has. In particular, $X\_i=+$ means that the $i$th feature is positive, i.e., that the $i$th subtree $S\_i$ is a subtree of the current item. We want to calculate

$$\Pr\[Y=+ | X\_1=x\_1,\dots,X\_n=x\_n\].$$

We do this using Bayes theorem. In particular, we use our training set to calculate

$$\Pr\[X\_i=x\_i | Y=y\],$$

for each of the 4 possibilities of $x\_i,y$. Then, we use Bayes theorem to compute $\Pr\[Y=+ | X\_1=x\_1,\dots,X\_n=x\_n\]$.

Now everything works as usual for naive Bayes. We've converted this into a situation where there's a set of $n$ features that can be present or absent for each item, and we want to label all the items; there's no more need to reason about the tree structure, we can just use a standard classifier like naive Bayes. You could also plug in some other classifier as well, too; hopefully you can see how this might work, from here.

# Answer
> 0 votes
You could use the techniques of syntactic pattern recognition. More specifically, you could use the UpWrite predictor, a method for inducting language grammars:

"Introducing the UpWrite Predictor", Jason L. Hutchens. International Colloquium on Grammatical Inference, 1999.

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


title: Issues in RSA setup

text:
# Question
Title: Issues in RSA setup
Suppose we have public key: $$n= 1015, e= 3$$ and private key: $$d= 635, p= 35, q= 29, \phi(n)= 952$$ For $m = 100$, we have $$c = m^e ~mod~n = 100^3 mod~1015 = 225.$$ To decipher this, let us take $$c^d~mod~n$$ which is $$225^{635}~mod~1015$$ which equals $$680$$ But $680 \neq 100$ so this means that RSA incorrectly decrypted it right? Why does this happen?

# Answer
Your public key is not a legal RSA public key. In RSA, $n$ must be a product of two primes, but 35 is not a prime. Therefore, things don't work right: for instance, you got the wrong value of $\phi(n)$.
> 1 votes

---
Tags: cryptography, encryption, modular-arithmetic
---


title: Relation between hardware and software

text:
# Question
Title: Relation between hardware and software
I'm very interested in computing and programming. I have done a lot of programming with different languages although I have a question nobody was able to answer until now.

I question myself how is software related to hardware. to be more specific what are the basic mechanisme which make it possible for hardware to understand software code?

**for example** : when you put on the computer it starts at a certain point in the register and feeds it into the apu. afther that I'm stuck ....

edited the question

# Answer
This is quite a difficult question to answer. I would comment if I could. The first problem is that you have not defined what you mean by a computer? Are you talking about the electrical based computers we know today or are you also including mechanical computers in your question? Here's a wiki link about the Difference Engine. The difference engine is completely mechanical but you can still technically 'program' it although it does not directly follow the paradigms of today.

Most parts of your question relate to one specific problem: How does the processing unit of a computational device work in a general way in accordance to the modern idea of software? I will give a general overview of what processor do.

A computer has three general operations: input (The input the user puts in, which includes data and what operation is wanted to be done), processing (the processor taking the input and operating on it) and output (what information is returned to the user). So what is inputted into a computer at the lowest level is some data and what is called an op-code or instruction. This is instruction is part of a collection stored in the processor (either electronically or via some other physical means) which has a defined algorithm associated with it. These instructions are considered 'basic' or low level. When something much more complicated is required to be processed, it is broken down into small parts which use these instructions to produce the desired computation in the end. Mechanical processors, specifically gearing based systems work in a similar way but accept input differently. The gears shift according to an algorithm to produce a result from a specific sequence of gear shifts initially (which is the input).

Here's a link to a Intel Lesson Series on Microprocessors

Another explanation of the CPU

From what I can gather the software you are talking about are the programs you see running on a computer. These are considered to be high level software, which are very complex when looking at this software from the perspective of a processor. Essentially the tools used to make this software and the software itself is broken down into a set of instructions for the processor to process at some point in the execution chain. With modern software there are many layers of abstraction to get from the processor to what the user sees. See this Wikipedia article about abstraction (It's the most comprehensive I could find): https://en.wikipedia.org/wiki/Abstraction\_(computer\_science)

Modern compilers such as gcc take human readable code and turn that into executable code which the operating system then executes. During execution the operating system will call processor instructions (which is a few abstraction levels down) in accordance to the executable code which the compiler produced.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: How do set partitions get mapped by restricted growth functions
I am reading Skiena but do not have a formal background in Computer Science. On page 457 he discusses generating set partitions via restricted growth functions. Here's specifically what he says:

> > Set partitions can be generated using techniques akin to integer partitions. Each set partition is encoded as a restricted growth function a1,...,an where a1 = 0 and ai \<= 1 + max(a1, ..., ai). Each distinct digit identifies a subset, or block, of the partition, while the growth condition ensures that the blocks are sorted into canonical order based on the smallest element in each block. For example, the restricted growth function 0, 1, 1, 2, 0, 3, 1 defines the set partition {{1, 5}, {2, 3, 7}, {4}, {6}}.

Can someone walk me through how this mapping works? It seems to me that a2 should be less than 1 + max(0, a2). But how does that determine a2? How do I get from 0, 1, 1, 2, 0, 3, 1 to that set of partitions? I don't see it at all and would appreciate any explanation or hints.

# Answer
> 3 votes
We want to define a sequence of nonnegative integers $\[a\_1, a\_2,\dotsc, a\_n\]$ with $a\_1=0$ such that for each $1\le i\le n$ we'll have $a\_i\le 1+\max\\{a\_1,\dotsc, a\_{i-1}\\}$ (Note the last index; the definition you gave would allow $a\_i$ to be anything). This condition doesn't uniquely determine $a\_i$, rather it gives several possibilities in general.

Let's generate some of these sequences.

* The shortest is just $\[0\]$
* To set $a\_2$ we must have $a\_2\le1+\max\\{0\\}=1$ so $a\_2$ could be either $0$ or $1$, giving us the length-2 sequences $\[0,0\]$ and $\[0,1\]$
* To set $a\_3$ we either start from $\[0,0\]$ or $\[0,1\]$. From $\[0,0\]$ we see that $a\_3$ could be either $0$ or $1$, giving us $\[0,0,0\]$ and $\[0,0,1\]$. From $\[0,1\]$ we could have $a\_3=0,1,2$, giving us $\[0,1,0\], \[0,1,1\],\[0,1,2\]$.

Let's look at the length-3 sequences, $\[0,0,0\],\[0,0,1\],\[0,1,0\],\[0,1,1\],\[0,1,2\]$, and see how they give rise to partitions of the 3-element set $\\{a,b,c\\}$.

1. $\[0,0,0\]$ tells us that each element lives in set 0, giving us the partition $\\{a,b,c\\}$.
2. $\[0,0,1\]$ tells us that elements $a,b$ live in set 0 and $c$ lives in set 1, giving us the partition $\\{a,b\\},\\{c\\}$.
3. Similarly, $\[0,1,0\]$ gives rise to the partition $\\{a,c\\},\\{b\\}$.
4. Similarly, $\[0,1,1\]$ gives us $\\{a\\},\\{b,c\\}$.
5. Finally, $\[0,1,2\]$ gives us $\\{a\\},\\{b\\},\\{c\\}$.

By inspection, these five growth functions give rise to all the five possible partitions of the set $\\{a,b,c\\}$.

# Answer
> 2 votes
The restricted growth function encodes which part a given integer belongs to: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline 1&2&3&4&5&6&7\\\hline 0&1&1&2&0&3&1\\\hline \end{array} $$

Part 0 contains $\\{1,5\\}$. Part 1 contains $\\{2,3,7\\}$. Part 2 contains $\\{4\\}$. Part 3 contains $\\{6\\}$.

---
Tags: algorithms, sets
---


# Question
Title: Can you take classical code and compile it to quantum code?
Is there anyway for example, to take a trivial program from C such as:

`int main() {
 int i = 1 + 1;
 return 0;
}`

And compile this down to some form of Quantum Abstract High-level language, i.e. Quantum C?

From what I understand, quantum arithmetic is quite tricky business that uses QFTs. My first thought was to do the following for the example above:

Initialise two qubits and set the amplitudes like following: $$ 0|1|0|0$$

Where 0100 = 2 in decimal.

Somehow return this quantum register.

Using the amplitudes, you could perform 32-bit arithmetic with 32 qubits?

I haven't answered the notion of creating a function or returning either.

Essentially what I'm asking is the following, can we take known quantum methods (using Unitary functions to perform calculation) and apply this to classical code and if so, how?

EDIT: I've looked further and seen a few papers on Quantum Full Adders, I assume this is the way to go for addition? Is this too much? In quantum computation books that describe quantum assembly, there is not much mention of addition.

# Answer
Doubly-controlled NOT gates are universal with respect to classical functions. Quantum computers can perform doubly-controlled NOTs. So even a quantum computer not allowed to perform fancy operations involving superposition, and not allowed to perform irreversible operations such as measuring or clearing a bit, can perform any classical computation.

For example, a quantum computer can basically directly run the gates making up a VanRentergem addition circuit:

Quantum computers are actually slightly *better* at reversible computation than classical computers. Classically you sometimes need an extra scratch bit to compute a function, because of permutation parity issues, but quantum shenanigans get that down to zero. Though of course emulating irreversible functions still requires introducing new scratch bits each time.
> 6 votes

---
Tags: compilers, quantum-computing
---


# Question
Title: How do I verify that a DFA is equivalent to a NFA?
I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is equivalent to a NFA?

# Answer
This is a problematic question. There is a way to check equivalence of automata, which I'll now explain, but I'm afraid it won't help you, as you will see at the end.

Recall that two sets $A$ and $B$ are equal iff $A\subseteq B$ and $B\subseteq A$ (this is the definition of set equality). Thus, it is enough for you to verify that $L(D)\subseteq L(N)$ and $L(N)\subseteq L(D)$, where $D$ and $N$ are your DFA and NFA, respectively.

But how do you check containment of languages, you might ask. Well, now observe that $A\subseteq B$ iff $A\cap \overline{B}=\emptyset$ (where $\overline{B}$ is the complement of $B$).

Let's consider first checking whether $L(N)\subseteq L(D)$. To do this, you need to complement $D$ (very easy - swap the accepting an rejecting states), then construct the intersection automaton (e.g. with the product construction) with $N$, and check for emptiness, by finding a path to an accepting state.

The converse direction, however, will show why this doesn't help you. In order to check whether $L(D)\subseteq L(N)$, you need to complement $N$. But in order to complement an NFA, you first need to convert it to a DFA, rendering the whole idea pointless.

Essentially, the problem with your question is much deeper: you want to verify that *you* (an undefined computational model) executed a well-defined algorithm properly. So this is not really a computer-science problem.

I will say this: following the constructions I suggested, it is not hard to conclude that $L(D)\neq L(N)$ iff there is a word of length at most $2^{2n}$ ($n$ being the number of states of $N$) that is accepted by one and not by the other. So you can try all words up to this length.
> 7 votes

# Answer
One way to proceed is to convert the NFA to a DFA and then check the equivalence of the two DFAs, for which there is a linear algorithm \[1\].

The following paper treats the more general case of the equivalence of two NFAs (which of course also applies to your case).

Filippo Bonchi, Damien Pous, Checking NFA equivalence with bisimulations up to congruence Principle of Programming Languages (POPL), Jan 2013, Roma, Italy. ACM, pp.457-468, 2013.

**Abstract**. We introduce bisimulation up to congruence as a technique for proving language equivalence of non-deterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp \[1\]. We compare our approach to the recently introduced antichain algorithms, by analysing and relating the two underlying coinductive proof methods. We give concrete examples where we exponentially improve over antichains; experimental results moreover show non negligible improvements.

\[1\] J. E. Hopcroft and R. M. Karp. A linear algorithm for testing equivalence of finite automata. TR 114, Cornell Univ., December 1971.

See also the web appendix to this paper, which contains Coq proof scripts of the results, a link to an implementation and an interactive applet.
> 5 votes

# Answer
this question is more about applied software testing and verifying correctness in practice rather than a theoretical question.

* if you have other code to compute intersections and complements (and empty DFA languages), you can use the idea that $D\_1 \cap \bar{D\_2}$ and $D\_2 \cap \bar{D\_1}$ are both empty where $\bar{D}$ is the complement.
* you can rely on prior tested software that has been tested to validate your results. eg AT&T FSM library
* another idea: randomized testing. pick random strings within your language. determine if the strings are accepted or unaccepted by the DFA/ NFA. if the two are not equal, with high probability you will find strings that mismatch.
* another idea: you can write code to traverse all branches of the DFA and NFA to some particular depth and look for mismatches. this is equivalent to enumerating all potential accepted strings of given lengths.
> 0 votes

---
Tags: automata, finite-automata, proof-techniques, nondeterminism
---


# Question
Title: What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?
I am looking for the most efficient algorithm for finding shortest path between two Vertices.

The graph is:

* undirected
* edge-weighted
* Non-negative
* less then 300 nodes

I understand that most of the algorithms based on Dijkstra's shortest path algorithm. But which one is the most efficient for the case a specified above. Thank you.

# Answer
> 3 votes
Use Dijkstra's algorithm. It is quite efficient, and on a graph with only 300 nodes, it will run *extremely* fast, so fast that it's not worth worry about.

You mentioned in a comment that your main concern is that the algorithms are described for directed graphs, but you have an undirected graph. No worries. You can apply Dijkstra's algorithm to an undirected graph, too. Whenever your graph has an undirected edge between vertices $u$ and $v$, think of that as equivalent to the two directed edges $u \to v$ and $v \to u$. In this way, you can convert your undirected graph to a directed graph -- and then you can apply Dijkstra's algorithm to the result. The same goes for any other algorithm for directed graphs; it can be applied to an undirected graph in the same way.

---
Tags: algorithms, graphs, shortest-path, efficiency
---


# Question
Title: Check whether loop invariants are correct?
I'm trying to prove some code is correct, using Hoare logic. How do I check whether my loop invariants are correct?

I'm asked to prove (using Hoare Logic) that the following program is valid:

```
x=1;
i=N;
while (i!=0){
    i--;
    x*=A;
}

```

with the pre-condition that `N>=0` and post-condition that `x=A^N`.

This is my attempt:

```
{ N>=0 }
x=1;
i=N;
{i >= 0}
while (i!=0){
    {i>=0}
    {x = product(i in (0:N-i); A)}    (loop invariant)
    i--;
    x*=A;
}
{x = A^N}

```

The curly brackets represent invariants that are supposed to hold at that point in the code. The 2 loop invariants seem to hold for every instance of the loop.

Is my attempt correct? Are my loop invariants sufficient? Do I have too many?

I know that `{i>=0}` is given by the definition of the loop. Should I remove that loop invariant then, since it is the case by default?

**EDIT: My new attempt**

```
{N>=0}
x=1;
{x = A^(N-N)=A^0=1}
i=N;
{x = A^(N-i)}
while (i!=0){
    {i>=0}
    i--;
    {x = product(i in (0:N-i-1);A)}
    x*=A;
    {x = product(i in (0:N-i);A)}
}
{x=A^N}

```

# Answer
> 3 votes
Rather than telling you whether your specific invariants are correct, let me teach you the procedure for how you can check whether your invariants are correct on your own.

Basically, you break it down by looking at each chunk of code separately. For each chunk of code, you look at the invariant before it and after it and see whether they're consistent with that chunk of code. If this check passes for all of the chunks, you're done: you're entitled to conclude that your program is "correct". The beauty of this is that this helps you break down the task into small manageable pieces. You never have to think about the entire program as a whole -- you only look at one chunk, in isolation, at any given time.

The way you verify a chunk of code depends on what kind of statement it contains. There are only a few cases you need to worry about:

1. **Straight-line code.** Suppose you have a statement with no branching, e.g.,

```
{P}
stuff;
{Q}

```

What you need to do is check that if `P` is true before the statement, then after executing the statement, `Q` will surely be true. In other words, if all we know about the state of the program is that `P` is true, and then we execute `stuff`, then afterwards it is guaranteed that `Q` will be true.

Notice that you check this by looking only at `P`, `Q`, and `stuff`: you shouldn't need look at any code in the rest of the program. If you find yourself trying to think about what the rest of the program is doing or ways you might be able to reach this chunk of code, you're doing something wrong, and probably you need to strengthen `P` (add some additional clauses that record more information about what states of the program are possible at that point).
2. **Loops.** Suppose you have a while-loop, e.g.,

```
{P}
while (e) {
    {Q}
    stuff
    {R}
}
{S}

```

Then you need to check four things. First, you need to check that the path that skips the loop entirely is valid, i.e., check that `P && !e` implies `S`. Second, you need to check that, on the first iteration of the loop, the loop invariant will hold: i.e., check that `P && e` implies `Q`. Third, you need to check that on any iteration of the loop, the following is valid:

```
{Q}
stuff
{R}

```

Fourth, you need to check that `R && e` implies `Q`. Fifth, you need to check that on the last iteration, `S` is enforced, i.e., that `R && !e` implies `S`. If all of these checks pass, then your invariants for the while-loop are OK.

Here's a different way to think about it that might feel more intuitive. You can try to find an invariant `T` that lets you annotate the loop with

```
{T}
while (e) {
    {T && e}
    stuff
    {T}
}
{T && !e}

```

All you need to check is that the following code block is valid:

```
{T && e}
stuff
{T}

```

If that code block is valid, then the entire while-loop construct is acceptable.
3. **Conditional statements.** If statements can be handled similarly, but are a bit easier than while-loops. For instance, if you have

```
{P}
if (e) {
    {Q}
    stuff
    {R}
}
{S}

```

then you need to check both the false-path and the true-path through the conditional. To check the false-path, check that `P && !e` implies `S`. To check the true-path, check that `P && e` implies `Q`, that `R` implies `S`, and that the following is valid:

```
{Q}
stuff
{R}

```

In this way, you should be able to check all of your invariants step-by-step. The only two things you need to know how to do are: (1) check whether one logical formula implies another, and (2) verify invariants for straight-line code. Everything else reduces to those operations.

With practice, you'll find that this becomes pretty mechanical. And with practice, you'll find that many of these invariants can be omitted (if it's straightforward for a reader to re-derive them), but when you start out, it's best to be verbose and include them all, without trying to omit stuff.

---
Tags: correctness-proof, loop-invariants, hoare-logic, software-verification
---


# Question
Title: Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?
Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ bit reads and writes in the worst case, though only $2 - 2^{1-n}$ bit reads on average (i.e $2$ bit reads on average asymptotically). On the other hand, there are codes like the Binary Reflected Gray Code that only require $1$ bit write in the worst case (since all integers in the sequence have hamming distance one). However, the BRGC requires $n$ bit reads in the worst and average case. In addition, there are other codes, such as the Recursive Partition Gray Code, which improve the average number of reads down to $O(\log n)$.

I would like the know if there is a code that can outperform the standard binary code with regards to the average number of reads. I have, however, no restrictions on the number of bit writes or the number of reads in the worst case. I feel like there should be a lower bound that says you cannot do better on average than $2 - 2^{1-n}$, but haven't been able to find a reference.

Edit: I know there is a lower bound of $\log n + 1$ reads in the worst case due to Fredman in 1978, but I am not aware of a lower bound for average case.

# Answer
There's a trivial lower bound showing that the average number of bits read needs to be strictly greater than $1$. This shows that it's not possible to improve on the standard binary code by more than a factor of 2. Probably not what you were hoping for, but it's something.

---

Proof:

In particular, what would it mean to perform an increment operation using 1 bit read on average? That would mean there is a deterministic "increment" function $f:\\{0,1\\}^m \to \\{0,1\\}^m$ and an injective function $\varphi : \\{0,1\\}^n \to \\{0,1\\}^m$ such that:

1. The average number of bits read by $f$ is 1. In other words, if we let $X$ be a random variable distributed uniformly on $\\{0,1\\}^n$ and $Y$ be the number of bits that $f$ reads, on input $\varphi(X)$, then we require $\mathbb{E}\[Y\]=1$.
2. Let $R$ denote the range of $\varphi$, i.e., $R = \\{\varphi(x) : x \in \\{0,1\\}^n\\}$. Then when projecting to $R$, $f:R \to R$ is bijective and its permutation structure consists of a single cycle.

Let's prove that no such pair $(f,\varphi)$ can exist, if $n\>1$. In condition 1, note that if $n\>1$, $f$ must always read at least one bit of its input, so we always have $Y \ge 1$. From the fact that $Y \ge 1$ always and $\mathbb{E}\[Y\]=1$, we conclude that $Y=1$ always holds. In other words, it follows that $f$ always reads exactly one bit of its input. Since $f$ is deterministic, the first bit it reads must be independent of the input, so say the first bit $f$ reads is bit position $i$. But since $Y=1$, this is the only bit of its input that $f$ reads. Thus, $f$ only depends on a single bit of the input (bit position $i$). It is easy to see that no such function can meet condition 2, i.e., can be a valid increment function, if $n\>1$.
> 2 votes

# Answer
We can prove a tight lower bound of $2 - 2^{1-n}$ as follows. Informally speaking, we will argue inductively that whenever a bit is read during the increment procedure, that one of the two possible outcomes (a $0$ or a $1$ can be read) will cause the algorithm to stop reading additional bits. This will show that if we require the average number of reads to be strictly smaller than $2$, then we required a code isomorphic to the standard binary code.

Suppose that the first bit read by the increment algorithm is bit $i\_1 \in \[n\]$. Now we have three cases to consider. In the first case (A), the algorithm will stop reading additional bits regardless of the value of $i\_1$. This means that after reading $i\_1$, the algorithm must decide which bits must be flipped right away, and clearly this will not yield a valid increment algorithm for $n \> 1$. In the second case (B), the algorithm will adaptively read another bit, regardless of the value of $i\_1$. We note that the algorithm may choose to read a different bit depending on the value of $i\_1$. In this case, however, we are already reading at least $2$ bits no matter what, so the average number of bits read will exceed $2-2^{1-n}$. Finally, in the third case (C), the algorithm will only read another bit for a single value of $i\_1$ (say $1$ for convenience). That is, when $i\_1$ is $0$, the algorithm will determine which bits need to be flipped, and when $i\_1$ is $1$, the algorithm will probe a second bit. In such a case, the expected number of bit reads is at least $1/2 \cdot 1 + 1/2 \cdot 2 = 3/2$. This is the only case where we can hope to beat the standard binary code.

Now we can apply this argument inductively. Suppose now that the algorithm is adaptively reading bit $i\_k$, with $k \leq n-1$. Then in case (A), at most $n-1$ of the bits are ever read by the algorithm. This means that there is a bit that is never read and thus never written to, so the increment algorithm cannot be correct. Here we assume that the only bits that can be flipped are the ones read during that particular increment operation. In case (B), we can verify that the expected number of reads is at least $$\sum\_{j=1}^{k-1} j/2^j + 2^{1-k}\cdot(k+1) = 2$$ which is again too many. In case (C), however, the expected number of reads can be verified to be at least $$\sum\_{j=1}^{k-1} j/2^j + 2^{-k}\cdot k + 2^{-k} \cdot (k+1) = 2 - 2^{-k}\cdot(2k+3)$$ which is again the only case which might lead us to a better performance than the standard binary code.

When performing the $n$-th bit read, there are no other bits that the algorithm can read (since the other $n-1$ bits have already been read), so only case (A) becomes valid. Computing the expected number of reads then gives exactly $2 - 2^{1-n}$, as required.

---

I find that it helps to view this as a binary decision tree, where the internal nodes are labelled by the bit read, and the leaves are labelled by the bits that are flipped. So you begin by reading the bit labelled at the root of the tree (in our case $i\_1$), then you go left if you've read a $0$ and right if you've read a $1$. With this picture in mind, it becomes clear that there are only three cases to consider at each step of the proof.
> 3 votes

---
Tags: lower-bounds, integers
---


title: NP-complete promise problems?

text:
# Question
Title: NP-complete promise problems?
Are there any good examples of promise problems that are NP complete?

# Answer
> 5 votes
There's two trivial answers:

1. No. For a problem to be NP-complete it must be in NP. To be in NP it must be a decision problem and promise problems aren't decision problems (they don't have to answer Yes or No on inputs outside the promise).
2. Yes. If you want to say informally that something is NP-complete (usually meaning "there's an obvious equivalent decision problem that is NP-complete"), then you can reformulate any decision problem as a promise problem just by taking the promise to be the set of sensible inputs. For example we can make a promise version of Dominating Set by taking the promise $L\_{YES} \cup L\_{NO}$ to be the set of all simple, undirected, unweighted graphs (so if you give it an input that's not a graph, it doesn't have to do anything in particular).

So there's no list of NP-complete promise problems because either none of them are (the strict answer), or you can just take any NP-complete problem and make a promise version.

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


title: Big-O proof for a recurrence relation?

text:
# Question
Title: Big-O proof for a recurrence relation?
This question is fairly specific in the manner of steps taken to solve the problem.

Given $T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$.

So the steps were as follows. We want to prove that $T(n) \le cn^2$.

$$\begin{align\*} T(n)&=2T(2n/3)+O(n) \\ &\leq 2c(2n/3)^2+an\\ &\leq (8/9)(cn^2)+an \end{align\*}$$ and then my prof went on to do:

$$T(n) \leq cn^2+(an-(1/9)cn^2)\\,,$$ which comes out to:

$$T(n)\leq cn^2 \text{ for any }c \>= 9a\\,.$$

My question is, how were they able to switch from 8/9 to 1/9 while introducing a new term? Is this allowed? She never explained, this was just in her solutions.

# Answer
> 12 votes
As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an \leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c \geq 9a$, which then gives you the desired result since $an - (1/9)cn^2 \leq 0$ for such values of $c$.

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


# Question
Title: How does one find a non-quadratic residue modulo $p$?
I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be.

I thought that one can use the Legendre Symbol

$$ \left( \frac{a}{p} \right) = a^{ \frac{(p-1)}{2} } \pmod p $$

if the Legendre Symbol returns -1 then its a non quadratic residue and if its a quadratic residue it would return 1. To do this it's easy find a randomized algorithm, since only half the elements are quadratic residues, then one guesses any element at random, say $a \in Z^\*\_p$ and if the Legendre Symbol returns -1 the return success. Since half the elements are not quadratic residues, it would take about 2 iterations in expectation to find one.

I was wondering, is this algorithm correct? It seems that its completely symmetrical for finding quadratic residues. I am not sure that is strange, but it seems weird to me. Is it correct that the two algorithms are basically the same?

# Answer
You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue *deterministically* in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is also equivalent to extracting square roots modulo a prime. This is all explained in notes by Booher.
> 5 votes

---
Tags: algorithms, algorithm-analysis, number-theory
---


# Question
Title: NP-complete reduction for a k-dumbbell graph
A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete?

Proof it is in NP: Given the cliques of size k, I can verify if it they are the cliques of size k.

Proof of NP-hardness: If there is only one edge between them, how can I be sure that this is the edge I need for the reduction?

I'm trying to reduce from the k-clique problem as it seems to be the easiest choice.

I'm new to this so, if I'm wrong somewhere, please help me out !

# Answer
Hint: Following your idea, you want to reduce the clique problem to the dumbbell problem, to show that the latter is NP-hard. Given an instance $(G,k)$ of the clique problem, it is natural to consider two copies $G',G''$ of your original graph, connected in some way, so that if the original graphs contains a $k$-clique, then the new one contains a $k$-dumbbell.

If the new graph contains a $k$-dumbbell restricted to one of the copies, then the original graph certainly contains a $k$-clique. You want to arrange matters so that if the $k$-dumbbell straddles both copies, then it is composed of a $k$-clique in each one.

This is just a hint, so I'm not giving a full solution. Indeed, there might be several ways of using this idea to get an NP-hardness reduction. Some of them require you to slightly change the value of $k$ from the clique instance to the dumbbell instance.
> 0 votes

---
Tags: np-complete, reductions, np-hard, clique
---


# Question
Title: Variation to edit distance depending on position still a metric?
The edit distance between two strings $d(w\_1, w\_2)$ sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric.

In particular, the cost of an edit operation may depend on the character inserted or deleted, meaning we have costs $w\_\text{insert}(a)$ and $w\_\text{delete}(a)$ for all characters $a$.

Question: If the cost also depends on the position in the input string where it is applied, will the result still be a metric?

As an example, consider a spell checker that assumes mistakes in the first character of a word are rather seldom as compared to other positions, so when searching for corrected words, a change in the first position would have high cost.

# Answer
> 4 votes
Here is why the usual edit distance is a metric:

1. $d(w,w) = 0$ since no operations need to be performed to get from $w$ to $w$.
2. $d(x,y) = d(y,x)$ since given a sequence of operations for transforming $x$ to $y$, we can perform it in reverse to transform $y$ to $x$ at the same cost. This shows that $d(y,x) \leq d(x,y)$, and similarly $d(x,y) \leq d(y,x)$.
3. $d(x,y) \leq d(x,z) + d(z,y)$ since if $\alpha$ transforms $x$ to $z$ and $\beta$ transforms $z$ to $y$ then $\alpha\beta$ transforms $x$ to $y$, and moreover the cost of $\alpha\beta$ is the sum of the costs of $\alpha$ and $\beta$.

Now you're in a position to answer your question yourself.

---
Tags: strings, string-metrics, edit-distance
---


# Question
Title: Shortest path problem where edge weight depends on path taken
I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between stops.

The weights of the edges represents how long it takes to complete a particular journey between stops. For example, if the next bus for a particular route is 10 minutes away, and the journey takes 5 minutes, then the edge weight for that route would be 15.

However, in order to know the amount of time until a particular bus arrives at a stop, it is necessary to know the current time—defined as the sum of the weights of the edges previously taken, plus the time at which the journey started.

What algorithm would allow me to know what vertices have been previously visited, so I can compute the sum of the edge weights? Obviously I could compute every single possible path in the graph, but that seems terribly inefficient.

# Answer
> 2 votes
Don't do that. Instead, change the way you model the problem as a graph problem.

One crude approach: Rather than having a vertex for each bus stop, introduce one vertex for each *pair* of a bus stop and a time. For instance, if $s$ is a bus stop and $t$ is a time, then $(s,t)$ is a vertex. If we have a bus that goes from $s$ to $s'$, takes 5 minutes, and departs every 20 minutes, then we'd have edges $(s,0) \to (s',5)$, $(s,20) \to (s',25)$, $(s,40) \to (s',45)$, etc. You can take it from here. (Test for understanding: see if you can work out what the running time of finding the shortest path to some destination is.)

A smarter approach: Fix an original vertex $v\_0$ (the starting point of all trips). For each vertex $v$, compute $d(v)$, which is the time it takes to get from $v\_0$ to $v$. How do you compute $d(v)$? Use dynamic programming. If you know $d(u)$ for all predecessors $u$ of $v$, then you should be able to work out an easy way to compute $d(v)$. Also, if you've studied shortest-paths algorithms, you should be able to find an ordering for assigning $d(\cdot)$ values. This will provide an efficient algorithm.

---
Tags: algorithms, graphs, shortest-path, routing
---


# Question
Title: Is there anything lower than the bit level of 1s and 0s?
When learning about the architecture of computers and how it works, we are thought that the lowest language that we can find that the machine understands is binary as 1&0. And anything that we input will have to be transformed/converted to binary, but being binary **numbers** wouldn't that mean that we would need another interpreter/compiler to transform binary into actual machine language? We all know from electronics that a computer is mainly composed of cpu which is an IC that is therefore made out of transistors etc, and the only thing that those tools understand is electricity, therefore electricity will be the lowest understandable language for a computer. So my concern is, is binary really 1s&0s or the 1s&0s are just used to represent the absence and or presence of electricity? Supposing that it's just a representation for absence or presence of electricity, wouldn't there be another intermediate or even lower language between the commands that we input and binary, so that the circuits would know where to send the current to and where not to?

# Answer
Digital computers work so that (almost) at any given point in time, any wire carries (roughly) one of two possible voltages, one signifying $0$ and the other signifying $1$. The voltages depend on the convention being used. In this sense, digital computing does work with $0$s and $1$s. However, even digital computers interface with analog devices, such as physical storage and networks. The way that data is encoded in networks can be somewhat different, since several bits can be encoded at once, depending on the encoding.

Let me explain my qualifications in the first sentence above. "Almost" refers to the fact that when wires switch from $0$ to $1$ or vice versa, there will be intermediate voltages. These switches are synchronized across all the wires so that whenever wires are "read", the switch (if any) has already occurred. "Roughly" refers to the fact that the voltages are not exact. There are two small ranges of voltages which correspond to $0$ and $1$. The devices should be able to "read" bits throughout these ranges, but usually "write" them more restrictively.
> 8 votes

# Answer
the question is not exactly clear & has some misconceptions or misapplication of terminology (eg "lower language") but interpreting it in a more general/ metaphorical/ analogical/ loose way, *yes*:

* one interesting case study here is the logical flip flop (see also How to understand the SR Latch) which because it has a feedback loop, cannot really be analyzed logically in terms of 0's & 1's and has to be analyzed more as an analog device
* the *timing* of the circuit is crucial in understanding the dynamic nature of the flip flop. an esp useful way of understanding it is a voltage/time plot.
* "beneath" 0's and 1's of logical circuits are continuous/nondiscrete analog voltages, and binary electronics can be said to tightly "control" the analog signals into highly constrained boundaries.
* there are cases where this "breaks down" eg for example on an IC chip, the electronics of defective gates or marginal designs can cause the chip to fail and fall out of the binary "envelope".
* another basic component of non-binary electronics is noise. much of the IC design can be regarded as controlling/minimizing it. in fact binary electronics can be seen as a means of eliminating noise from circuitry to achieve "noiseless" signals.
> 3 votes

# Answer
You are asking several different things into one question. Maybe it's a good idea to untangle the problem for yourself. You are talking about physics, definition of the industry and software/computer architecture.

> that the lowest language that we can find that the machine understands is binary as 1&0. And anything that we input will have to be transformed/converted to binary.

Let's do this part first. Modern-day computers are based on electrical circuits. For example most ARM processors can run at 5 volts. Because of the way the ARM processor is build in the fabric the processor understand a ~0 volt signal as a 0 bit and ~5 volt as a 1 bit. It is the definition chosen by someone.

> but being binary numbers wouldn't that mean that we would need another interpreter/compiler to transform binary into actual machine language?

I do not completely understand what you are asking here. But let's say you are looking from a software perspective. Then, the program eventually will be transformed in actual lines of bits and a line of bits which tell the CPU what to do with the bits. These are fed into the CPU (processing unit) and based on the processor architecture a action will be performed on the data.

> We all know from electronics that a computer is mainly composed of cpu which is an IC that is therefore made out of transistors etc, and the only thing that those tools understand is electricity, therefore electricity will be the lowest understandable language for a computer. So my concern is, is binary really 1s&0s or the 1s&0s are just used to represent the absence and or presence of electricity?

As I mentioned a little bit above, it is the way computers are built. You can run the processor on other voltages but it won't work (I think). Because the a particular definition is made about at what voltage a bit is 0 or 1.

> Supposing that it's just a representation for absence or presence of electricity, wouldn't there be another intermediate or even lower language between the commands that we input and binary, so that the circuits would know where to send the current to and where not to?

Yup, basically analog signals. But keep in mind most of the time these are converted by an ADC (analog digital converter) into a bit value which represents a predefined voltage on that line.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Logarithmic Randomness is Necessary for PCP Theorem
I am trying to proof the following statement:

If $ {\rm SAT} \in {\rm PCP}\[r(n),O(1)\]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$.

Here are my ideas for the proof: It can be easily worked from here that there exists an nondeterministic Turing machine $N$ solving any SAT instance in time $o(n^{q})$ for any $q \in R^{+}$. I believe it should lead to a contradiction somewhere (maybe alteration theorems). I had another approach to guess the certificate, but that takes time $2^{2^{o(\log n)}}$ which is not always polynomially bounded.

Source: PCP Course By Prahladh Harsha. This was one of the excercise questions. I am self studying this, so this does not violate any ethical arguments.

# Answer
You can actually show a slightly stronger result: if $SAT \in PCP(o(\log n), o(\log n))$ then P=NP. The idea is to apply the implied reduction repeatedly, reducing the size of the instance all the way down to $O(\log n)$, at which point you can solve it by trying all certificates.

For more details, Arora and Safra (page 76) suggest looking at Theorem 26 in the appendix of FGLSS (journal version). Unfortunately, this appendix doesn't seem to be available any more.
> 3 votes

---
Tags: complexity-theory, p-vs-np, probabilistic-algorithms
---


# Question
Title: Constrained Smallest Enclosing Ball Problem
Let $X = \\{x\_1, x\_2, ..., x\_n\\} \subset \mathbb{R}^m$ be a finite set of points. Smallest enclosing ball is a well-known problem that asks for the $m$-ball that covers all $x\_i \in X$, while having the smallest radius possible.

I am interested in solving a related, more constrained problem. Namely, in my version, the enclosing $m$-ball's center can not be chosen freely, but is constrained to be one of the points in $X$. In other words, I would like to find the point $x\_j \in X$ such that the maximum distance (i.e. the enclosing radius)

$$\max\_{x \text{ } \in \text{ } X} \\; \lVert x - x\_j \rVert$$

is minimized.

Obviously, one can simply compute all distances in $O(m n^2)$ time, and find the desired point. A less naive way to tackle the problem would be to generate a space-subdividing acceleration structure, say a kd-tree. We can do this in $O(m n \log n)$. Then, per-node maximum distances can be computed in $O(f(m, n))$ time, and we can pick the node having the minimum-maximum distance. This method would have a complexity of $O(n (f(m, n) + m \log n))$. Here, $f(m, n)$ is a function that stands for the query complexity of the kd-tree. Therefore, $f(m, n)$ "looks like" $m \log n$ for small $m$, but $m n$ for large $m$.

All in all, we would still be making many repeated (and unnecessary) distance computations. Also, because of how $f(m, n)$ behaves, the latter method degrades to the former for big $m$. Therefore, even the latter solution is not very satisfactory.

Can we do better? What is the best (in terms of time complexity and practical performance) known algorithm to tackle this problem?

# Answer
I guess one simple approach would be to use any known Smallest Ball algorithm to determine the center of the optimal ball. Then you use kNN-queries to find the closest neighbour, which is likely the required point. However, you would need to show that the closest neighbour really is necessarily the best point. Maybe you need to actually check a number of candidates within a to-be-determined distance of the virtual center point.

Also, for a practical solution, I wouldn't use a kd-tree. R-Tree (or R\*tree/R+tree/X-tree) behave better, so does the PH-Tree (a kind of quadtree).
> 1 votes

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


# Question
Title: Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?
I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that unlike $LR(1)$ items, which just have an item lookahead (the token that should appear after the completed $LR(1)$ item), the items in an $LR(2)$ parser also need a dot lookahead (the tokens that should appear after the dot in the $LR(2)$ item).

I'm having trouble understanding what this means, how this lookahead is computed, and why this isn't needed in $LR(0)$ or $LR(1)$ items. Can anyone explain what this means?

# Answer
> 4 votes
I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used.

First, let's remark that there are three kinds of items:

1. those in which the dot is just before a non-terminal. They never participate in an ambiguous situation: when a non-terminal has been produced, it is shifted.
2. those in which the dot is at the end. They have the item look-ahead and the dot look-ahead which are equal (what may follow the dot is what may follow the produced non-terminal when the production is reduced as the dot is at the end of the item).
3. those in which the dot is just before a terminal. They have the item look-ahead and the dot look-ahead which are different. The item look-ahead is what may follow the non-terminal when the production is reduced, the dot look-ahead start by the terminal which follow the dot and continue with what can be generated after that terminal.

Now, with a look-ahead of 1 or less, the dot look-ahead is trivial: either it is the item look-ahead or the terminal which is just after the dot and that's what you are using to solve a conflict (or decide that there is no way with the limited look-ahead you have). With a look-ahead of 2 or more, you have to compute the dot look-head or you may not know if you have to shift or to reduce as in the example provided by Grune and Jacobs:

$$\begin{array}{l} S \rightarrow Aa \\; | \\; Bb \\;| \\;Cec \\;|\\; Ded \\ A \rightarrow qE \\ B \rightarrow qE \\ C \rightarrow q \\ D \rightarrow q \\ E \rightarrow e \\ \end{array}$$

which has the state: $$\begin{array}{lcc} &\textrm{item look-ahead}&\textrm{dot look-ahead}\\ A \rightarrow q \cdot E & a\\# & ea\\ B \rightarrow q \cdot E & b \\# & eb\\ C \rightarrow q \cdot & ec & ec\\ D \rightarrow q \cdot & ed & ed\\ E \rightarrow \cdot e & a \\# & ea\\ E \rightarrow \cdot e & b \\# & eb\\ \end{array}$$

---
Tags: compilers, parsers, lr-k
---


title: On equivalences to promise problem

text:
# Question
Title: On equivalences to promise problem
We know that under hierarchy collapse results GI is not NP complete.

Would there be any consequences if GI is equivalent to a promise version of an NP complete problem?

# Answer
No. Simple reductions from GI to SAT are efficiently invertible, so for any such reduction, GI is equivalent to SAT-that's-promised-to-be-in-the-range-of-the-reduction.
> 2 votes

---
Tags: complexity-classes
---


# Question
Title: How can the class of tail recursive functions be compared to the classes of PR and R?
How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)?

The computation of a PR function always halts. This does not apply to TR functions. Given a tail recursive function $f$: $$f(x) = f(x)$$ The function $f$ obviously will result in an endless recursion and therefore $TR \not\subseteq PR $. Also a PR function has a finite time and space complexity, where a TR function can have a finite space and infinite time complexity. For this reason I assume: $$PR \subset TR \subset R $$

* Is this assumption correct?
* Is the Ackermann function $\in TR$?
* Is there a well known function which is in $R$, but not in $TR$?

# Answer
> 10 votes
Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls.

The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value is directly returned (such as recursion base cases) are replaced by calling the continuation in tail-position with the result as an argument.

Transformation from the lambda calculus into CPS can be done mechanically. So, $TR=R$.

---

EDIT: addressing the comments about higher-order functions:

Tail-calls are almost always discussed in the context of higher order functions and the lambda calculus. So the problem is, what precisely is our definition of $TR$?

You can certainly add a wrapper around a CPS function to give it the type $\mathbb{N}^n \to \mathbb{N}$, by giving it an initial continuation of $\lambda k \ldotp k$. If higher-order functions are allowed internally, then the result that $TR=R$ still holds.

If higher order functions aren't allowed internally, what is our definition of $TR$? If we define it in the same way as $PR$, then it is going to only contain primitive recursive problems by definition (since it's just the restruction of $PR$ to tail-recursion). If we add $\mu$ for infinite search, I think we're just going to get $R$, since we can encode higher-order functions using integers. So, I'm not sure there's a meaningful question to be asked in the non-higher-order case.

---

EDIT 2:

As for the class of first-order functions that only allow tail recursion, with Constant, Successor, Projection and Composition functions, and extension by tail recursion:

```
h(x1 ... xn) =
  if c(x1 ... xn) = 0 then
    h(g1(x1), ..., gn(xn))
  else
    f(x1, ..., xn)

```

where $c$, $g\_i$ and $f$ are all tail-recursive functions, I think we can prove that it's Turing Complete, by solving Post's Correspondence Problem, which is undecidable but semi-decidable:

Assume that we've got nice functions for dealing with strings encoded as integers, with concatenation, etc.

Let $pcpInst(k, n)$ be a function which takes an integer $k$ and returns the $k$th string over the alphabet $\\{1, \ldots, n \\}$.

Let $c(k, x\_1, \ldots, x\_n) = $ be a function, where $k$ is an integer, and each $x\_i$ is a pair containing two strings over a binary alphabet. Thus function does the following:

* Computes $k\_1 \cdots k\_p = pcpInst(k,n)$, the $k$th possible PCP solution indices.
* Constructs $s\_1=\pi\_1(x\_{k\_1}) \cdots \pi\_1(x\_{k\_p}))$. This is the string we get by concatenating the first string of the arguments indexed by our $k\_i$ sequence. We define $s\_2$ with $pi\_2$ similarly.
* Return $0$ if $s\_1 \neq s\_2$, return $1$ otherwise.

Now, we'll define our function to solve the a PCP instance with $n$ strings:

* $h(k, x\_1, \ldots, x\_n) = h(S(k), x\_1, \ldots, x\_n)$ if $c(k, x\_1, \ldots, x\_n) = 0 $
* $h(k, x\_1, \ldots, x\_n) = 0$ otherwise

Now we define $h'(x\_1, \ldots, x\_n) = h(0, x\_1, \ldots, x\_n)$.

It is clear to see that $h'(x\_1, \ldots, x\_n)$ returns 0 if and only if there is a solution to the correspondence problem defined by pairs of strings $x\_1, \ldots, x\_n$. If there is a solution, we eventually iterate to it by increasing $k$, and return $0$ when our $c$ function returns 1. If there is no solution, we never return.

The trick here is ensuring that $c$ is itself tail-recursive. I am fairly confident that it is, but that proving so would be tedious. But since it is performing simple string manipulations and equality checks, I would be very surprised if it is not tail recursive.

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


# Question
Title: Check if a string can be split into two subsequences
Given a string S of length N, a string A of length M, a string B of length O such that N \>= M + O. Check if the string S can be split into two subsequences X and Y such that A = X and B = Y.

Example: S = "abCDEfgH", A = "abfg", B = "CDEH" =\> answer is Yes S = "abcDEG", A = "acdG", B = "ED"

I found that this can be solved by dynamic programming but having a tough time finding a recursion. Can someone tell me the recursion and also an intuitive explanation of it? Thanks in advance!

# Answer
> 0 votes
We'll use indices `(i, j, k)` to keep track of how much we've seen of each string `(S, A, B)`.

* If we've seen all of `S`, then return YES if we've seen all of `A` and all of `B`,
* If `S[i] == A[j]`, then recurse on `(i+1, j+1, k)`,
* If `S[i] == B[k]`, then recurse on `(i+1, j, k+1)`.

Implement this as a memoized recursive function. This has time complexity `O(S * A * B)`.

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


# Question
Title: Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?
I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square root).

I was wondering if using the previous fact and also that we knew we had a number of the form $N = 4k+3$ (not necessarily prime), then maybe there is a different primality testing for (any?) $N$ using the square root function (i.e. $SQRT\_N(a) = a^{k+1} $).

So the algorithm that I thought was the following:

Choose a Quadratic Residue (QR) $a \in \mathbb{Z}^\*\_N$ (one can easily do this by checking if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ holds). Once we have a QR, compute $a^{k+1} = x\_a$ and check if $x\_a^2 $ is equal to $a$. If its true, then we conclude that $a$ is prime. Otherwise, we choose a different QR $a' \in \mathbb{Z}^\*\_N$ and repeat the algorithm. One can repeat this algorithm $k$ times. If after $k$ times there is no success then conclude the number is composite.

I have mainly intuitions on why its correct but not a formal proof. From the first fact that $x\_a = a^{k+1}$ is a square root when $p$ is prime, it must mean that $x\_a^2 \equiv a \pmod p$. Therefore, if $a$ is a QR then that check will pass (half the time we will choose a QR so the probably that we choose a non QR is only 1/2).

However, if $N$ is composite, it seems we have no guarantee that $x\_a^2 \equiv a \pmod N$. So if it doesn't hold we are sure its not prime. But if it does hold then if its prime we are right but if its composite we might be wrong? Basically, is it possible to use the SQRT function when $N = 4k+3$ to decide if $N$ is prime or not?

---

I also thought of an another algorithm that deserved its own question: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?

# Answer
> 5 votes
Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime. Suppose $N=91$ and $a=9$. Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR. Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes your second test, your algorithm will conclude that 91 is prime. However, 91 is not prime: $91=7 \times 13$. Thus your algorithm has drawn the wrong conclusion in this case. This demonstrates that your algorithm can output incorrect answers in at least some cases.

---

Actually, there is a more serious problem with your algorithm. There is no number $N$ where your algorithm will ever output "composite". It thinks that all numbers are primes. More precisely, for every $N$, your algorithm will either loop forever (trying to find a number that passes the QR test, in vain), or will terminate and output "prime". So, your algorithm is about as wrong as could be.

You can see this by applying some number theory. You have a test whether $a$ is a QR and a second test based on the square root insight. If $a$ passes the first test, it will pass the second one.

Here's why. Your QR test succeeds if $a^{(N-1)/2} \equiv 1 \pmod N$. Your second test succeeds if $(a^{(N+1)/4})^2 \equiv a \pmod N$. The latter is equivalent to $a^{(N+1)/2} \equiv a \pmod N$. But $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$. Therefore, if $a^{(N-1)/2} \equiv 1 \pmod N$, then (multiplying both sides by $a$) we immediately see that we must have $a^{(N+1)/2} \equiv a \pmod N$.

Each of the $k$ passes of your algorithm basically amounts to looking for an $a$ that passes the first test, and then checking whether it passes the second test -- but based on the prior insight, we see that any $a$ that passes the first test will be guaranteed to pass the second test as well. Thus, if the algorithm ever finds any value $a$ that passes the QR test, the second test will automatically pass and the algorithm will output "prime".

The lesson to learn: any time you think you have an algorithm that looks promising, it's worthwhile to code it up and try it on some test cases and see if it seems to work well. Trying it on a few test cases is not a substitute for a proof of correctness, but it can be a helpful way to weed out some incorrect algorithm quickly.

---

Finally, on to your real question: can we use something like this to build a primality test? Well, you can think of the Miller-Rabin primality test as loosely based on something like this. They are based on a characterization of what the square roots of $1$ should look like, if $N$ is prime. If you encounter a square root of $1$ that is not $1$ or $-1$, you can conclude that $N$ is not prime. However, it's not limited to numbers $N$ of the form $N=4k+3$, so in that sense it is definitely different.

# Answer
> 3 votes
The congruence is true for all primes $p$ of the correct form but it is also true for some composite numbers, which makes the congruence alone useless as a primality test.

Example: set $p$ to the number $15$, which is obviously composite and is of the form $4k + 3$ with $k = 3$. $10000$ is $100^2$, so $10000$ mod $15$ produces the quadratic residue $a$ = $10$. $10^{k+1}$ = $10^{4}$ = $10000$; applying mod $p$ to that yields $10$. Now the test: Under mod $p$ $10$ is supposed to be the square root of $a$ ($10$) only if $p$ is prime, but $10^2$ = $100$ which is $10$ mod $p$, so $p$ has passed the primailty test. Yet we know $p$ is composite.

This is demonstrating that even if your method for picking QR's is perfect, the algorithm still can err. For instance, here would be a reasonable way to pick $a$: pick a random number $r$, square it, and call $a$ the result (i.e., $a =r^2 \bmod N$). Then you know that $a$ is guaranteed to be a QR, and there's no need to test it using the test you listed. If that was how your algorithm picked $a$, then the example above shows that your algorithm can give the wrong answer in some cases (e.g., $p=15$, $r=5$).

---
Tags: algorithms, algorithm-analysis, randomized-algorithms, number-theory
---


# Question
Title: Identify balanced and full binary search tree insert order
I'm inserting numbers 1 thru 15 into a binary search tree one by one. I need to come up with an order to insert these elements for it to result in a full and balanced binary tree. I've tried to create the binary search tree myself, starting with a root of 8, however I could never get it to be full; the depth would increase from three to four or sometimes five.

How can I come up with an order to insert these numbers into a binary search tree, and get it to be balanced and full?

# Answer
> 1 votes
Keep trying. Try a recursive algorithm. You know that the root needs to be 8. You should be able to infer what numbers need to go in the left subtree of the root. What order should you insert those numbers in, to ensure that the left subtree results in a full and balanced binary tree? Hmm, does that resemble a problem you've seen before? You should be able to take it from there.

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


# Question
Title: How to identify labels in unsupervised learning?
Let's say I am working on handwritten digit recognition (0 to 9). I know for instance that if I use clustering then I need to look for 10 clusters. But once I have the 10 clusters,how do I identify automatically which cluster corresponds to which digit? In general, say I have some other classification task where I don't have the labels for the training data, but I know that there are, lets say, two classes. I want to build a model which can then tell me, for the test instances, which classes they belong to. But again the problem that even if I can group the train cases together, how do I know the actual label of the test instance in this unsupervised setting?

# Answer
> 1 votes
You can't, in a completely unsupervised setting. You need something more: e.g., a training data set where you have labels for at least some of the instances, or some other information that allows you to set a label for each cluster.

How is the computer supposed to know that a circle means zero as opposed to some other number, if you don't tell it that? Obviously, it can't. In fact, in the Eastern Arabic numbering system, there's a zero-looking character that actually means the number 5, not the number 0. Obviously, a computer can't possibly know which of those two meanings is intended, if you don't tell it somehow.

---
Tags: machine-learning, data-mining, pattern-recognition
---


# Question
Title: Why can't you see computer behind a router?
I understand the basics of networking(DNS,DHCP,IP,MAC, etc.).

I have installed a router and plugged my computer into the router. On the other end of the router the cable goes somewhere to a switch(I think). And then to internet. But on the same network my neighbour is also connected. Now my neighbour and I tried to ping his computers but I cannot seem to find it. Why is that ?

# Answer
> 2 votes
When you install a new router and plug various devices to it, all plugged in devices got totally new set of private IP address. Your router act as Network Address Translation (NAT) server. All of devices behind router, are on different private network. It also possible that your device and neighbour's device may have same private IP addresses because your neighbour would be getting IP address from different router or DHCP server.

---
Tags: computer-networks
---


# Question
Title: Why does it seem as if I can apply the Pumping lemma to a language that is regular?
We learn about the Pumping Lemma at the class and I tried to make few examples to understand it...

There I make this example:
Let's say: $L=\\{w\in L|w=(0+1)^\*1\\}$ - i.e. - L is the language of all the words that finish with $1$. (The language is regular of course).

Now, I can take the word: $w=0^{n-1} 1$. $w\in L$ and $|w|\ge n$.
I can take: $u=0^{n-1},v=1,z=\varepsilon$.
$|uv|\le n$ and $|v|\>0$, but:
$uv^0z\notin L$ because $uv^0z$ ends with $0$...

What I miss here?
I'd like to understand more where is my mistake...

# Answer
> 4 votes
The pumping lemma says that, for every regular language *there exists some* pumping length $p$\* such that blah blah blah.

You made two mistakes. First, you tried to choose $p$ based on a specific word, rather than based on the language as a whole. Second, you chose the wrong value of $p$. In particular, for the language you've given, $p=1$ has the property required of the pumping lemma: for every word $w$ in that language, you can write $w=\epsilon y z$ with $|y|=1$, and you'll find that $\epsilon y^n z$ is in the language for all $n\geq 0$.

# Answer
> 3 votes
The pumping lemma states that "... there **exist** such $u$, $v$, $z$ that $w = xvz$ ..." but it doesn't state you can divide $w$ into **arbitrary** three pieces (even provided the other conditions hold).

# Answer
> -1 votes
En tu caso esta algo mal planteado Para verificar con el lema de bombeo se sigue los siguientes pasos: k es un conjunto de estados de A Primero tiene q cumplir L=t(A)y w € A

A es un AFD con |k|=n y |w| \>= n

a) w=uvz

b)|uv|=n

c)v ≠¶ (¶ es el vacío)

d) u(v^i)z i\>=0 u(v^i )z € T(A)

con eso el AFD es A={{q0,q1,q2},{0,1},d,q1,q3} Con cadena w=0100111 u(v^i )z i \>=0 y |uv|\<=n u=0 v=1 z=00111 n=3 al incrementar i aun w € T(A)

espero entiendas :)

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


# Question
Title: Why does the concatenation of the empty set with any language give the empty set?
Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.

# Answer
> 10 votes
Let $L\_1, L\_2$ be languages, then the concatenation $L\_1\circ L\_2=\\{w\mid w=xy, x\in L\_1, y\in L\_2\\}$. If $L\_2=\varnothing$, then there is no string $y\in L\_2$ and so there is no possible $w$ such that $w=xy$. Thus for any $L\_1$, we'll have $L\_1\circ\varnothing = \varnothing$.

---
Tags: formal-languages, closure-properties
---


# Question
Title: There is any notation for a language that is empty infinite?
Assume that $L$ is a language, is there any established notation that means that $L$ is infinite or empty?

# Answer
> 1 votes
The usual way to describe these properties is by indicating the size of $L$, denoted by $|L|$.

* Empty language, the size is zero, $|L|=0$
* Finite language, $|L|=c$ or in general, the size in non-infinite, $|L|\< \infty$
* Infinite language, $|L|=\infty$.

---
Tags: formal-languages, notation
---


# Question
Title: Run-time analysis of distributed network decomposition algorithm
I'm trying to understand the run-time analysis in the article \[1\].

The authors define the following notation: $g(n) = \hat O(f(n))$ if $g(n) = O(f(n)^{O(1)})$. In the run-time analysis of their algorithm, they find that $$T(l) \leq \hat O(p\log n)10^{\log\_{p/2} l} \equiv f(l,p)$$ where $n$ is the number of nodes in the network, $l$ is the number of nodes in the input to the (recursive) algorithm and $p$ is a parameter.

Then they claim that the minimum of $f(n,p)$ is attained when $p=2^{\Theta(\sqrt{\log n})} = \hat O(n^{\epsilon(n)})$ with $\epsilon(n) = \frac 1{\sqrt{\log n}}$. This is the part that I don't understand. How do you minimize $f(n,p)$?

---

1. On the Complexity of Distributed Network Decomposition by A. Panconesi and A. Srinivasan (1996)

# Answer
> 0 votes
Calculus: any local minimum of the function $f(x)$ must be a point $x$ that satisfies $f'(x)=0$, where $f'(x)$ is the first derivative of $f(x)$. So, take the derivative, set it to zero, and find all solutions. Each solution is a candidate for the minimum. You then need to check each candidate to see which makes $f(x)$ smallest. You'll also need to check the "endpoints", e.g., the smallest and largest possible value for $x$ need to be added as candidates.

You can do the same for functions of two variables, and for asymptotics.

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


# Question
Title: What is the difference between ∀ and Π in the Calculus of Constructions?
As I've learned, the Calculus of Constructions has only two binders - $\lambda$ and $\Pi$. Morte, for example, has $\forall$ as a mere alias of $\Pi$. Yet, on the paper Self Types for Dependently Typed Lambda Encodings, there are types such as:

$$\begin{gather} \mathrm{Nat} := \forall X. (X \rightarrow X) \rightarrow X \rightarrow X \\ \mathrm{It} : \forall X. \Pi x : \mathrm{Nat}. (X \rightarrow X) \rightarrow X \rightarrow X \\ \mathrm{Ind} : \forall P : \mathrm{Nat} \rightarrow \mathord{\ast}. \\; \Pi x:\mathrm{Nat}. \\; (\Pi y:\mathrm{Nat}. (P \\, y \rightarrow P (S \\, y))) \rightarrow P \\, \bar 0 \rightarrow P \\, x \end{gather}$$

Notice that the paper uses both $\forall$ and $\Pi$. Moreover, $\forall$ is used both with the syntax $\forall a : b \rightarrow c$ and $\forall a . b$. I can't parse those expressions. What is the difference between $\forall$ and $\Pi$, and how would you express those types on Morte?

# Answer
> 6 votes
I had only a quick and cursory look at the paper — so take this with great care.

It appears that $\Pi X$ is used to express dependent products as in the calculus of constructions. Instead, $\forall X$ looks more like polymorphic types in ML.

The main difference is that, if $t : \Pi x. P(x)$ then $t T : P(T)$, while if $t : \forall x. P(x)$ then $t : P(T)$. Note that the former requires an additional argument, the second does not: the polytype gets instantiated automatically. Rules $\mathit{App}$ and $\mathit{Inst}$ at page 7 cause this difference.

Of course, this also means that introducing $\Pi$ requires a lambda, while introducing $\forall$ does not.

There also is some type / kind distinction related to this, but I can't comment on that precisely.

---
Tags: type-theory, dependent-types, calculus-of-constructions
---


# Question
Title: Is the language $a^i b^j c^k$ with $i+j > k$ context-free?
I am learning about Context Free Grammars and currently stuck on the following question.

> Is the following language context-free? If not, then how can we prove it using Pumping Lemma?
>
> $\qquad L = \\{a^i b^j c^k \mid i,j,k \geq 0 \land i+j \> k\\}$.

After spending some time I have been able to generate the production rules for the following language, but unable to understand and conclude the above.

Important Condition **($i+j = k$)**

> $\qquad M = \\{a^i b^j c^k \mid i,j,k \geq 0 \land i+j = k\\}$.

$\qquad\begin{align\*} S &\to aSc \mid X \\ X &\to bXc \mid ε \end{align\*}$

Any assistance in solving the condition **($i+j \> k$)** would be a great help.

# Answer
There is a simple way to obtain a grammar for the language $L\_{\geq} = \\{a^ib^jc^k : i+j \geq k\\}$ given a grammar for the language $L\_= = \\{a^ib^jc^k : i+j = k\\}$. Starting with a grammar for $L\_=$, change all rules mentioning $c$ to rules mentioning a new non-terminal $C$, and add the two productions $C\to c \mid \epsilon$.

Concretely, if we start with the following grammar for $L\_=$: $$ \begin{align\*} &S\to aSc \mid T \\ &T\to bTc \mid \epsilon \end{align\*} $$ then the corresponding grammar for $L\_{\geq}$ is $$ \begin{align\*} &S\to aSC \mid T \\ &T\to bTC \mid \epsilon \\ &C\to c \mid \epsilon \end{align\*} $$

Of course, this is not quite the restriction we were after. It is possible to modify the grammar for $L\_{\geq}$ to a grammar for $L\_{\>} = \\{a^ib^jc^k : i+j \> k\\}$ by "signalling" within the grammar that at least one $c$ was actually dropped. This requires duplicating some of the non-terminals and rules. Details left to you.

Another modification which will produce $L\_{\geq}$ from $L\_=$ replaces each $a$ by a non-terminal that generates $a^+$, and each $b$ by a non-terminal that generates $b^+$: $$ \begin{align\*} &S\to ASc \mid T \\ &T\to BTc \mid \epsilon \\ &A \to Aa \mid a \\ &B \to Bb \mid b \end{align\*} $$ Again we can use signalling to get $L\_\>$ rather than $L\_{\geq}$. Details left to you.
> 3 votes

# Answer
I think self-learning along with the assistance of you all has really helped. Thank you for all your help.

**Please input** or comment, if the below production rules can be edited or modified into something more succinct. **I think it can be improved**

The following Language is Context-Free

> $\qquad L = \\{a^i b^j c^k \mid i,j,k \geq 0 \land i+j \> k\\}$.
>
> ***Production Rules***

$$ \begin{align\*} &S\to aAE \mid AU \\ &A\to aA \mid \epsilon \\ &B\to bB \mid \epsilon \\ &E\to aEc \mid F \\ &F\to bFc \mid \epsilon \\ &U\to aUc \mid V \\ &V\to bVc \mid bB \\ \end{align\*} $$

> ***Strings Generated***

$$ \begin{align\*} &a \mid b \\ &bb \mid ab \mid aa \\ &aac \mid bbb \mid abb \mid abc \mid abc \mid aaa \mid bbc \\ &abbc \mid aaac \mid abbc \mid bbbc \mid aabc \mid aabc \\ &abbcc \mid bbbcc \mid aaacc \mid abacc \mid abacc \mid abbcc \\ &abbbccc \mid aabbccc \mid aaaaccc \mid aaabccc \\ &aabbbbbbbccccccc \mid aabbbbbbbcccccccc \end{align\*} $$
> 2 votes

# Answer
Yes, above language is context free. You can design Pushdown automata for above language easily.

I'll describe pushdown automata function intuitively -\> Start pushing all a's if there are any. Once all a's are finished, then start pushing b's if any. Then starting popping one symbol off stack for each c. At then end of you see end of input & stack is non empty you accept. (I'm not describing the process of rejecting input if it is not in format of a^ib^jc^k, format , as I think it is intuitive).

As far as grammar is involved you have to write grammar similar to what you have written , you just need to do few modifications.

i+j \> k, Due to think condition minimum strings of above Context Free Language are a or b. Now S corresponds to state which can generate any no of a's. Y can generate any no of b's. aS and bY help in generating more no of a's/b's than c's. Just a or just b are terminating condition, see that you can generate any string from this grammar.

S -\> aSc | aS | a | Y

Y -\> bYc | bY | b
> 0 votes

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


# Question
Title: Why it is nearly impossible to have an approximation algorithm for Maximum Clique problem?
I read a theorem which states that: If there exists a polynomial time approximation algorithm for solving the Maximum Clique problem (or the Maximum Independent Set problem) for any constant performance ratio r, then NP = P.

But I never understood the reasoning behind this!!

# Answer
In fact, something stronger is true: if you can approximate maximum clique within $n^{1-\epsilon}$ for some $\epsilon \> 0$ then P=NP. This is because for every $\epsilon \> 0$ there is a polytime reduction $f\_\epsilon$ that takes an instance $\varphi$ of SAT and returns an instance $(G,cn)$ of maximum clique such that:

1. If $\varphi$ is satisfiable then $G$ has a $cn$-clique.
2. If $\varphi$ is not satisfiable then $G$ has no $cn^{1-\epsilon}$-clique.

If you could approximate maximum clique within $n^{1-\epsilon}$ you would be able to distinguish the two cases (exercise), and so to decide whether $\varphi$ is satisfiable or not.

The reduction uses the PCP theorem as a first ingredient. Given the PCP theorem it is not hard to give a similar reduction with a constant gap, and with some effort to give a reduction with a gap of $n^\epsilon$ for some $\epsilon \> 0$. The reduction claimed above, which has a gap of $n^{1-\epsilon}$ for every $\epsilon\>0$, is much harder. See lecture notes of Guruswami and O'Donnell for the constant gap, and lecture notes of Scheideler for the $n^\epsilon$ gap.
> 9 votes

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