title: What counts as an operation?

text:
# Question
Title: What counts as an operation?
Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all operations to be equal?

Surely, dividing two very large numbers is more time-consuming than adding one to a number (as in each iteration of a for loop). Multiplication, for example, can consist of any number of small additions. So, instead of just adding them up shouldn't we be applying some kind of weight to each operation depending on the type of operation (addition, multiplication, etc) and the size of the numbers involved?

My problem is that I am being asked to *prove* that the complexity of my algorithm is $O(f)$ (for some function $f$) and I am not sure how to do this in a mathematically rigorous fashion because of the inherent vagueness in the definition of a "simple operation". So how would I go about this?

# Answer
> 1 votes
Simple operations are anything that takes constant time to achieve. The confusion is that division does not seem to take constant time, and in fact, in general, it does not. BUT!

Division and addition both take constant time if, say, you are adding two 32-bit integers together, which is usually how it goes. However, if you are adding arbitrarily large numbers, they won't really be constant-time, though sometimes I think people will treat it as if it is because the numbers are kind of assumed to not get super big.

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


# Question
Title: Can't Understand this Subset Construction Proof
This proof is from Introduction to Automata Theory Languages and Computation by Hopcroft & Ullman and is regarding a 'bad case' for subset construction.

The NFA which is being converted is as follows:

The argument for this then goes as follows:

> Consider the NFA N of Fig. 2.15. $L(N)$ is the set of all strings of $0's$ and $1's$ such that the nth symbol from the end is $1$.
>
> Intuitively, a DFA D that accepts this language must remember the last $n$ symbols it has read. Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, if D has fewer than $2^n$ states, then there would be some state $q$ such that D can be in state $q$ after reading two different sequences of $n$ bits, say $a\_1a\_2…a\_n$ and $b\_1b\_2…b\_n$.
>
> Since the sequences are different, they must differ in some position, say $a\_i \neq b\_i$. Suppose (by symmetry) that $a\_i = 1$ and $b\_i = 0$. If $i = 1$, then q must be both an accepting state and a nonaccepting state, since $a\_1a\_2…a\_n$ is accepted (the $n^{th}$ symbol from the end is 1) and $b\_1b\_2…b\_n$ is not.
>
> If $i \> 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a\_ia\_{i+1}…a\_n00…0$ is accepted and $b\_ib\_{i+1}…b\_n00…0$ is not.

What's confusing me are these two lines,

> Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...

and

> If $i \> 1$, then consider the state $p$ that D enters after reading $i - 1$ $0$'s. Then p must be both accepting and nonaccepting, since $a\_ia\_{i+1}…a\_n00…0$ is accepted and $b\_ib\_{i+1}…b\_n00…0$ is not.

I understand the case where $i = 1$, but I don't understand how the $i \gt 1$ works, and what they mean by any of the $2^n$ subsets being $1$. How can the subsets be $1$?

# Answer
> Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...

This is just referring to the fact that there are $2^n$ possible sequences of length $n$ made up of $0$'s and $1$'s. That is, if you have $n$ symbols, you can think of "a subset of those symbols being $1$" as taking a subset of the indices from 1 to $n$ and making the symbols at those indices be $1$.

> If $i\>1$, then consider the state $p$ that D enters after reading $(i−1)$ $0$'s. Then $p$ must be both accepting and nonaccepting, since $a\_ia\_{i+1}\ldots a\_n00 \ldots 0$ is accepted and $b\_ib\_{i+1}\ldots b\_n00 \ldots 0$ is not.

So you have two sequences of characters $a\_1a\_2\ldots a\_n$ and $b\_1b\_2\ldots b\_n$ which end up in the same state. You know that $a\_i=1$ and $b\_i=0$. Now take both of those strings and append $(i-1)$ $0$'s to each one. This gives you the following two strings $x$ and $y$:

$x= a\_1a\_2\ldots a\_i\underbrace{a\_{i+1}\ldots a\_n}\_{n-i\text{ symbols}}\underbrace{00 \ldots 0}\_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $1$ ($a\_i = 1$ and it is the $n$th symbol from the end).

$y= b\_1b\_2\ldots b\_i\underbrace{b\_{i+1}\ldots b\_n}\_{n-i\text{ symbols}}\underbrace{00 \ldots 0}\_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $0$ ($b\_i = 0$ and it is the $n$th symbol from the end).

Now think about what happens when you run these two strings through D. It's actually quite similar to the $i=1$ case: since the two strings ended up in the same state $q$ after reading $a\_1a\_2\ldots a\_n$ and $b\_1b\_2\ldots b\_n$, they also have to end up in the same state $p$ after reading $(i-1)$ more $0$'s. Thus this state $p$ has to be both accepting and nonaccepting since our string $x$ should be accepted but $y$ should not be accepted.
> 4 votes

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


# Question
Title: Reversing topo-order of the original graph instead of the topo-order of the transposed graph?
(Note that my question is different from this one, I understand why we have to do a dfs on a reversed graph, I want to understand why we can't reverse the topological order instead of transposing the graph.)

In Kosaraju's algorithm, it is stated to compute the transposed graph and apply topological sort on it. I understand why this is necessary.

What I don't understand is the necessity to actually compute the transposed graph. Can't we just apply the topological sort algorithm on the original graph and use the resulting list in reverse order?

In Dasgupta,Papadimitriou, Vazirani, one can read

> There is not an easy, direct way to pick out a node that is guaranteed to lie in a sink strongly connected component.

I am having trouble to see why. If I apply a `explore` on any node of the following graph, the first finished node will be one of inside a sink strongly connected component.

Wikipedia's description of the algorithm seems to confirm this. The first DFS prepends instead of appending.

Can someone show an example (if any) where using the reversed topological order of the original graph instead of the topological order of the transposed graph is wrong?

# Answer
> 3 votes
It may work for the graph you give, but not for all graphs. Consider a graph with 3 vertices, A, B, and C.

$A \rightarrow B, C$

$B \rightarrow A$

Search on A, exploring B before C, B finishes first but is not in a sink.

Also, note that for the Wikipedia article, the search is on incoming edges, not outgoing, which is why it doesn't need to explicitly transpose the graph.

# Answer
> 3 votes
My intuition for why the reverse topological order is necessary is that given a node $v$ in a strongly connected component $C$, if $v$'s finishing time (denoted in CLRS as $f(v)$) is maximal, than so is $C$'s. However, if $f(v)$ is minimal, $f(C)$ might not be minimal. In order for the algorithm to work without the transpose, at each stage you must be able to choose a node belonging to the SCC with the lowest remaining $f(C)$, which is generally not possible without already knowing what the SCCs of the graph are.

By the way, your question is identical to exercise 22.5-3 in CLRS version 3, and you can also find other answers to it online.

---
Tags: graphs
---


# Question
Title: How does matrix chain multiplication problem has an optimal substructure?
We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure?

For eg. consider if these are optimal solutions for matrices A1.A2.A3.A4.A5.An:

> (((((A1.A2)A3)A4)A5)A6)An)
> (((((A1.A2)A3)A4)A5)(A6.An))

If any of above is optimal solution then we won't be able to consider any optimal substructre.No?

# Answer
> 5 votes
First of all, it is correct and important to know that optimal solutions need not necessarily be *unique*! However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such decisions repeatedly (usually via *divide and rule*)

Note that *again*, the 'optimal' decision need not be unique! So, by making different locally optimal decisions, it is possible to end up with multiple globally optimal results. So, the seeming contradiction of multiple optima and optimal substructure doesn't exist.

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


title: Time complexity of Prim's algorithm

text:
# Question
Title: Time complexity of Prim's algorithm
There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix).

As far as I have understood,that is because we have to ckeck all the nodes per every node, that is, when checking the first node's best edge, we have to check edges from the current node to all other nodes. That makes $(n-1)$ edges at most. We check this for all nodes, so it would be n\*(n-1) edges to check at most.

So why is the time complexity $O(n^2)$?

In addition, why don't we consider the edges which create a loop and why don't we ommit them in the algorithm? Does that make any difference in the time complexity?

# Answer
The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$

The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity

For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$
> 2 votes

# Answer
In prim's algorithm for every vertex you have to search for all the adjacent vertices which can be O(n) in worst case and search for minimum among them takes O(n) time. So TC for one vertex will be O(n)+O(n)=O(n). For n vertices TC will be n\*O(n)=O(n^2)
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, adjacency-matrix, prims-algorithm
---


# Question
Title: Is every algorithm on bounded resources O(1)
Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, therefore the function describing running time is bounded and hence is $\mathcal O (1)$.

Therefore, when analyzing any algorithm that has been tuned to support some machine requirement (ex. input is 32 bit integer), if it halts, we may say it's $\mathcal O (1)$.

What am I missing here? What are arguments supporting/opposing this point of view?

# Answer
> 2 votes
By *definition*, every algorithm (that always halts) on a finite domain has $O(1)$ running-time: pick $n\_0 \> \max \\{ |x| \mid x \in D\\}$ with $D$ the input domain of the algorithm.

However, that fact is utterly uninteresting. Asymptotics are designed to help make statements for "large n", expressed through a limit process; they are simply meaningless if the domain is bounded, or the inputs you see in practise are "small".

As a consequence, if you are concerned with finite domains you'll have to use different mathematical notions, and potentially different machine models.

# Answer
> 1 votes
Let $s$ be the number of states that the Turing machine can be in, including the value of the machine's internal register, the contents of writable tapes, and the locations of the heads. As the machine is deterministic, if it were to enter the same state twice in one run, its sequence of instructions following each step entering that state would have to be the same; therefore it would run forever. Thus the machine can never enter the same state twice so the machine runs in time $O(s)$.

If the machine has $r$ possible values of its internal register, a total of $c$ writable cells each containing a value from an alphabet of size $a$, and tapes of length $l\_1, \ldots, l\_t$ then it's easy to see that $s \le S \equiv r \cdot a^c \cdot l\_1 \cdot \ldots \cdot l\_t$. Then the machine runs in time $O(s)$ so it runs in time $O(S)$.

If you treat $r$, $c$, $a$, and $l\_1 \ldots l\_t$ as constants then $O(S) = O(1)$. However, if you treat them as variables then you can use the formula incorporating them.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Smallest possible DFA for a language over {0,1}* with third to last symbol 1 should have 4 states not 8. Where am I going wrong in my DFA?
So I was reading Micheal Sipser's Introduction to TOC and when I stumbled upon this aforementioned question , he'd the following dfa :

Now, I came up with a much better DFA with only 4 states :

I read in another thread that the minimum number of states for a DFA for this language is 8. But , I came up with 4.

Where am I going wrong ? (I tried testing this DFA with a plethora of input strings , seems ok to me)

# Answer
> 1 votes
Try inputting 1100 to your DFA. You get to $q\_1$, a non-accepting state.

We can show that 8 states are needed using the Myhill–Nerode theorem. The following table gives words separating any two of $000,001,010,011,100,101,110,111$: $$ \begin{array}{c|cccccccc} & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\\hline 000 & & 00 & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\ 001 & 00 & & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\ 010 & 0 & 0 & & 00 & \epsilon & \epsilon & \epsilon & \epsilon \\ 011 & 0 & 0 & 00 & & \epsilon & \epsilon & \epsilon & \epsilon \\ 100 & \epsilon & \epsilon & \epsilon & \epsilon & & 00 & 0 & 0 \\ 101 & \epsilon & \epsilon & \epsilon & \epsilon & 00 & & 0 & 0 \\ 110 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & & 00 \\ 111 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & 00 & \end{array} $$

---
Tags: finite-automata
---


# Question
Title: Local search (Hill Climbing) scope and definition
I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-queens puzzle to illustrate the algorithm working, he stated that in it a queen can only move one row up or down, so for example in a column with the following configuration:

In the first iteration the queen can only move to either rows 4 or 6 (8 rows, 0-based index), then in the next iteration it would be stuck in a local maxima because neither row 3 nor 7 have values lower than 14, so the algorithm would then proceed to the next column or terminate. He argued that even tough a queen can legally move directly through all the rows of its column doing so would make the algorithm fall of the concept of "Local search", because a local search move is limited to only one of its closest neighboors per time/iteration.

I found this weird because it appears to me that such a limitation greatly reduces the usefulness of hill climbing (in the 8-queen problem it makes the success rate abysmal). So I would like to know what's the correct/formal definition of local search and hill climbing, should it always be constrained to the closest neighboor? what constitute a closest neighboor? I would especially appreciate some book references.

# Answer
Local search and hill climbing assume that you have defined a notion of "neighbor" and have defined an objective function. It's up to you to define those for your particular application. As you have noticed, some choices of the "neighbor" relation might make local search more effective or less effective.

In the 8-queen problem, there are multiple ways you could define the notion of "neighbor". One option is to treat two configurations as neighbors if you can get from one to the other by moving one queen one step; then the example in the question shows that local search with this notion of neighbor might get stuck. That is a consequence of defining "neighbor" in a particular way as much as a consequence of using local search, and is not fundamental to the notion of local search. Nothing prevents you from defining "neighbor" differently. For instance, one alternative is that you could consider two configuration neighbors if you can get from one configuration to the other by moving one queen any number of steps in a single direction. That might have different properties.

What *is* fundamental is that local search and hill climbing can risk getting stuck in a local minimum (where all neighbors are worse than your current location, but you're not in a global minimum). The likelihood of this may depend on the particular problem you are working with, the specific notion of neighbor you choose, and which local search method you use. Hill climbing is particularly susceptible to local minima; other methods are designed to try to reduce the risk of local minima.
> 3 votes

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


# Question
Title: Length of distinguishing string for a DFA
Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?

# Answer
> 4 votes
It is a classical fact that if two states are distinguishable, then they are distinguished by a string of length at most $n-1$. This follows from an analysis of Hopcroft's algorithm. See also lecture notes of Luca Trevisan.

Let us say that $q\_i \equiv\_k q\_j$ if $\delta(q\_i,w) \in F \Leftrightarrow \delta(q\_j,w) \in F$ for all $|w| \leq k$. We can compute $\equiv\_k$ inductively as follows:

* $q\_i \equiv\_0 q\_j$ iff $q\_i,q\_j \in F$ or $q\_i,q\_j \notin F$.
* $q\_i \equiv\_{k+1} q\_j$ iff $q\_i \equiv\_k q\_j$ and for all symbols $\sigma$, $\delta(q\_i,\sigma) \equiv\_k \delta(q\_j,\sigma)$.

If $\equiv\_k = \equiv\_{k+1}$ then $\equiv\_k$ is the Myhill–Nerode relation $\equiv$, since the formula above shows that $\equiv\_k = \equiv\_m$ for all $m \> k$. Conversely, if $\equiv\_k \neq \equiv\_{k+1}$ then $\equiv\_{k+1}$ has more equivalence classes than $\equiv\_k$ (since $\equiv\_{k+1}$ refines $\equiv\_k$). If $\equiv\_0 \neq \equiv\_1 \neq \cdots \neq \equiv\_m$ then $\equiv\_m$ must have at least $m$ more equivalence classes than $\equiv\_0$, which has at two equivalence classes (in the non-trivial case). Since $\equiv\_m$ contains at most $n$ equivalence classes, we deduce that $m \leq n-2$. Hence $\equiv = \equiv\_{n-2}$.

# Answer
> 2 votes
Distinguishing strings can, in general principle, be of any length, though the specifics will depend on the automaton and states that you're looking at.

For example, consider the usual automaton that accepts even-length strings over the alphabet $\\{1\\}$. We have states $q\_\mathrm{e}$ (which is the start state and is accepting) and $q\_\mathrm{o}$ (which is not accepting), and the transition function just swaps state every time a character is read. For this automaton, every string over $\\{1\\}^\*$, including the empty string, distinguishes the two states. Strings of even length (including $\epsilon$) distinguish because they're accepted by $q\_\mathrm{e}$ and rejected by $q\_\mathrm{o}$; odd-length strings are the other way around.

# Answer
> 0 votes
Hint: what happens if you remove a loop in the path corresponding to the word?

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


# Question
Title: How do these alternative definitions of one-way functions compare?
I've seen competing requirements in the definitions for one-way functions. Namely

$$ \underset{x,r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big) = o(n^{-c}) $$ and $$ \underset{x}{\mathbb{E}}\left\[\underset{r}{\mathbb{P}}\big(f(B(f(x),r)) = f(x)\big)\right\] = o(n^{-c}) $$

where $x\in\\{0,1\\}^n$ and $r = \text{poly}(n)$. $B$ is thought of as a randomized algorithm and $r$ are the random bits it's using.
Now I know that for the construction of pseudo-random generators from one-way permutations either of these definitions will do, but is the same true for the construction from general one-way functions? Are there cases that I should be aware of where these definitions aren't interchangeable?

Edit: Okay, here's my own explanation for why these expressions are equal. If we replace the entire mess $f(B(f(x),r)) = f(x)$ with the indicator random variable $p(x,r)$ then we can write: $$ \begin{split} \underset{x}{\mathbb{E}}\left\[\underset{r}{\mathbb{P}}\big(p(x,r)=1\big)\right\] & = \underset{x}{\mathbb{E}}\left\[\underset{r}{\mathbb{E}}\left\[p(x,r)\right\]\right\]\\ & = \underset{x,r}{\mathbb{E}}\left\[p(x,r)\right\]\\ & = \underset{x,r}{\mathbb{P}}\big(p(x,r) = 1\big)\\,. \end{split} $$

# Answer
The expressions are equivalent. To see why, unfold the expectation and use the fact that $x,r$ are independent.

$$ \mathop{\mathbb{E}}\limits\_{x}\left\[\Pr\limits\_{r}\big(f(B(f(x),r))=f(x)\big)\right\]= \sum\limits\_{x}\Pr(x)\Pr\limits\_{r}\big(f(B(f(x),r))=f(x)\big)= \sum\limits\_{x}\Pr(x)\sum\limits\_{r}\Pr(r)\mathbb{1}\_{f(B(f(x),r))=f(x)}= \sum\limits\_{x,r}\Pr(x,r)\mathbb{1}\_{f(B(f(x),r))=f(x)}= \Pr\limits\_{x,r}\big(f(B(f(x),r))=f(x)\big). $$

Note that both the second and the last equalities follow from the definition of the probability of an event over a discrete sample space (sum of the probabilities of elements in the event, or summing over the entire space while multiplying by the associated indicator function).
> 3 votes

# Answer
They're equivalent. In general, if $X$ is a 0-or-1 random variable, then $\mathbb{E}\[X\] = \mathbb{P}\[X=1\]$ holds. Also, if $E\_{X,Y}$ is an event that depends on two independent random variables $X,Y$, then $\mathbb{P}\_{X,Y}\[E\_{X,Y}\] = \mathbb{E}\_X\[\mathbb{P}\_Y\[E\_{X,Y}\]\]$. To see way, just expand the definitions, as Ariel suggests.

(Comment on the original version of the question, before it was edited: The former expression makes no sense. It doesn't type-check. When you write $\mathbb{P}\[\cdots\]$, the $\cdots$ has to be an event. $\mathbb{P}\big(f(B(f(x))) = f(x)\big)$ is not an event; it is a random variable. Check your sources -- I suspect you must have copied something down wrong.)
> 3 votes

---
Tags: pseudo-random-generators, one-way-functions
---


# Question
Title: Problem with the pseudo random number generator One-Time-Pad
I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $XOR$ and get the cipher text. This encrypts the message and to decrypt the message you'd do $XOR$ with the cipher and key bits.

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator, where the original key is $n$-bits long (and doesn't have to be as long as the message). Then you'd put the key in the generator and get a pseudo random number. But since it's pseudo random, wouldn't the sender and receiver get different keys? Then how can the receiver decrypt the message if they don't have the same key?

# Answer
> 17 votes
You seem to have misunderstood what the key is.

In the context of symmetric encryption, the key is a *shared* secret: something that is known to both the sender and receiver. For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that.

For your proposed "efficient" OTP, the key is the PRNG seed: both parties must ensure beforehand that they know it. Then, they both initialize the PRNG with the same seed and it is guaranteed to produce the same sequence of "random" numbers for each of them.

However, note that this is a massive, massive weakening of OTP. An actual OTP gives perfect security, as long as the pad is kept secret. If you intercept the 17-character message

```
nsmklmfmwnfmngner

```

you have zero knowledge of whether it is

```
maketrumpthepotus

```

encoded with one pad, or

```
ensureclintonwins

```

encoded with a different pad. Or

```
kittensarethebest

```

or literally anything else. However, using a pseudorandom pad means that only certain pads are possible (maybe there's no key at all that encrypts the kitten message to "nsmklmfmwnfmngner", so you can rule that out). Anybody who knows the PRNG algorithm can start guessing keys to try to decrypt messages. Anyone who captures some pad material can start trying to reverse engineer the PRNG. Anyone who captures encrypted messages can start trying the same.

You really shouldn't call it OTP unless the key material is as long as the message. Your proposal for using a PRNG is just a generic stream cypher.

# Answer
> 11 votes
> Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator

No, no and once again no. I'm concerned that this is what you're being taught. **The absolutely fundamental concept of a one time pad and the notion of mathematically provable perfect secrecy is that the pad material is truly random. And it must never ever be reused, even once.** It cannot be generated by any form of algorithm. The random numbers must come from a physical process such as dice throws, electrical noise or photon interference in a split laser beam. If you make them with any sort of algorithm /code then that's just a stream cipher like RC4 or an AES construct.

Browse through the one time pad tagged questions over at crypto.se. That will tell you everything. More importantly, you'll read many attempts at *improving* or making the one time pad *more efficient*. All of them are snake oil, no matter how enticing they might appear.

# Answer
> 7 votes
A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish the generator's output from a truly random string). Note that allowing the generator to toss coins makes the whole thing uninteresting, as you could simply return a truly random output.

In that case, the key can be the seed $s$, and the receiver can compute $G(s)$ to decipher the message (since $G$ is deterministic, this computation yields the same result for both parties).

---
Tags: randomized-algorithms, randomness, cryptography, encryption
---


# Question
Title: Why is it better to do the data flow analysis in the basic blocks
I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal.

Sadly, quoting the exact source, would be slightly hard as it is not in English, but a quote from wikipedia can also be used:

*Data-flow analysis is the process of collecting information about the way the variables are used, defined in the program. It attempts to obtain particular information at each point in a procedure. **Usually, it is enough to obtain this information at the boundaries of basic blocks**, since from that it is easy to compute the information at points in the basic block.*

Even though, in Wikipedia it is slightly explained, why the basic blocks are the preferred way, I still do not understand the benefits and if it is not obtained from the basic blocks, then from where?

# Answer
It isn't "better" in the sense that the analysis is more precise. It's just more compact and cheaper to compute.

There's no reason why you can't compute an old-school iterative bit-vector-based dataflow analysis at every point between two intermediate-representation instructions. It will give you the same answer as doing it on basic blocks.

The main issue is that doing it this way, you need to store and manipulate the data at every point between two IR instructions. And remember, the only variable lifetimes that change across an instruction are the variables that participate in that instruction, so the sets on each side of an instruction are mostly the same. This is wasteful, especially on older machines.

Having said all that, we generally don't do dataflow analysis this way any more. Almost all modern compilers use some variant of static single assignment form. SSA form is cheap enough on modern machines, and gives you a more precise analysis: not only does SSA form give you the definitions that reach a program point, for example, it also gives you the paths along which those definitions reach.
> 3 votes

---
Tags: compilers, data-flow-analysis
---


# Question
Title: Prove that the language $L_1 = \{a^ib^{2i}c^j \;|\; i,j ≥ 0\}$ is context-free
Prove that the language $L\_1 = \\{a^ib^{2i}c^j \\;|\\; i,j ≥ 0\\}$ is context-free.

I have a grammar like this but there are some strings that are not be able to be generated

$$\begin{align} S &\to aSbb \\;|\\; C \\ C &\to cC \\;|\\; \epsilon \end{align}$$

One example is the string $abbc$ cannot be generated.

# Answer
> 2 votes
You've almost got it. Consider that $L\_1$ is simply the concatenation of $L\_a$ and $L\_c$, where $L\_a = \\{a^ib^{2i} \\;|\\; i ≥ 0\\}$ and $L\_c = \\{c^j \\;|\\; j ≥ 0\\}$, since the two parts of each sentence are independent of each other.

That should suggest a grammar which starts with the production $L\to AC$, and which then proceeds to define $A$ and $C$ in the obvious way.

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


# Question
Title: Find the loop invariant of the given while loop
I don't know how to find a loop invariant. I'm not sure where to start. Can anyone find the loop invariant of the given program and explain your method please.

```
{n ≥ 0 ∧ i = 0}
while i < n − 1 loop
b[i] := a[i + 1];
i:=i + 1
end loop
{∀j.(0 ≤ j < n − 1 → b[j] = a[j + 1])}

```

# Answer
> 5 votes
At the end of each iteration you have $$ \forall j: 0 \leq j \< i \implies b\[j\] = a\[j+1\] $$ which you can prove by induction. Thus, when the algorithm terminates, $i$ has reached $n-1$ and you have $$ \forall j: 0 \leq j \< n-1 \implies b\[j\] = a\[j+1\]\\,. $$

I figured this out by just asking myself what kind of statement I can make at the end of each iteration. In this case it's that the first $i$ elements have been copied. Then I just turned that into a formal statement.

---
Tags: proof-techniques, loop-invariants, hoare-logic, proof-assistants
---


# Question
Title: Under what circumstances are one-way functions reducible to their hard-core bits?
I've seen competing claims about hard-core predicates. On the one hand, there's the basic definition

> Let $f : \\{0,1\\}^n \rightarrow \\{0,1\\}^k$ and $b : \\{0,1\\}^n \rightarrow \\{0,1\\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$, $$ \mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\\,. $$

But I've also read the statement

> We want the problem of finding $x$ to be reducible, in polynomial time, to the problem of finding $b(x)$, so that finding $b(x)$ is just as hard as finding all of $x$. In that case $b$ is called a hard-core bit for $f$.

How are these requirements related? Is one stronger than the other? Or do they imply each other?

# Answer
Inverting a one way function is not always reducible to evaluating a hardcore bit. As an example, consider trivial hardcore predicates. Let $f$ be one way and define $g(x,b)=f(x)$ where $b\in\\{0,1\\}$. Obviously $b$ (the rightmost bit of a string) is a hardcore predicate for $g$, however knowing it does not bring you any closer to finding the rest of the string. The problem is that such predicates are probably of no use. Usually, we cant afford to lose information (e.g. while constructing pseudorandom generators), so we won't be able to base hardcore predicates on a part of the input that we're not using.

To overcome the above problem (i.e. ignoring trivial hardcore predicates), we can demand that evaluating the predicate will help us reverse the function (if this is the case, then $f(x)$ and $h(x)$ cannot be independent). The generic construction in Goldreich-Levin's theorem indeed yields such a predicate. If $f$ is one way and $g(x,r)=(f(x),r)$, then an algorithm computing $h(x,r)=\langle x,r\rangle$ can be used to find $x$ (just feed it $f(x)$ along with different values of $r$).
> 3 votes

# Answer
An intuitive, informal interpretation of the first definition is that it is hard to find $b(x)$ (given $f(x)$). If you can predict $b(x)$ from $f(x)$, then you have an adversary $B$ such that $\mathbb{P}\[B(f(x))=b(x)\]$ is significantly larger than $1/2$; the assumption that no such adversary exists means that you cannot predict $b(x)$ from $f(x)$. Conversely, any such adversary gives a way to predict $b(x)$ from $f(x)$.

One way to show that it is hard to find $b(x)$ is to show that finding $x$ (from $f(x)$) reduces to finding $b(x)$ (from $f(x)$). The assumption that $f$ is one-way implies that finding $x$ (from $f(x)$) is hard. Such a reduction would then imply that finding $b(x)$ (from $f(x)$) is hard as well.

The Goldreich-Levin theorem shows one example of a specific predicate $b(x)$ where we can demonstrate the existence of such a reduction. That then implies that this predicate $b(x)$ is hardcore.

See https://en.wikipedia.org/wiki/Hard-core\_predicate and a good textbook on one-way functions, hardcore predicates, and the Goldreich-Levin theorem.
> 0 votes

---
Tags: one-way-functions
---


# Question
Title: Length of shortest word accepted by exactly one of two DFAs
Let $M\_1$ and $M\_2$ be two deterministic finite automata with $M\_1$ having $n$ states, and $M\_2$ having $m$ states, over the same alphabet $\Sigma$. Show that if $M\_1$ and $M\_2$ are not equivalent, then there is some string $\omega \in \Sigma^\*$ of length at most $n \times m$ that is in exclusively $M\_1$ or $M\_2$.

It is clear to me that since they are not equivalent, there is some string that is in exclusively $M\_1$ or $M\_2$. But how can we show that there is some string that does not exceed the required length?

# Answer
Construct the product automaton $M = M\_1 \times M\_2$, which contains $nm$ states. Since $L(M\_1) \neq L(M\_2)$, the automaton $M$ contains a state $(q\_1,q\_2)$ reachable from its initial state such that $q\_1$ is an accepting state of $M\_1$ and $q\_2$ is not an accepting state of $M\_2$, or vice versa. Since $M$ contains $nm$ states, this state is reachable from the initial state of $M$ by a path of length at most $nm-1$. This corresponds to a word of length $nm-1$ which is in $L(M\_1)$ but not in $L(M\_2)$, or vice versa.

Using the method of this answer, we can improve the bound to $n+m-2$. This is tight for $m=1$, as the example of $L(M\_1) = \sum\_{k=0}^{n-2} \Sigma^k$ and $L(M\_2) = \Sigma^\*$ shows.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Generate a dataset for binarization of text in images
I want to generate a dataset of binarized masks of scene-text images to use them to train a model. I have no previous experience in dataset synthesization especially related to font-rendering.

Can anyone provide me some links to articles/blogs/related-github-projects?

# Answer
> 1 votes
Start with the following paper, and use it to seed a literature search using the usual methods.

Detecting Text in Natural Scenes with Stroke Width Transform. Boris Epshtein, Eyal Ofek, Yonatan Wexler. CVPR 2010.

---
Tags: computer-vision
---


# Question
Title: Can Floyd-Warshall algorithm be used in an undirected graph with negative edges?
So i know that it cannot be used if the directed graph has negative cycle, but what about the undirected graphs with negative edges?

is it going to always work, or sometimes or never?

# Answer
> 2 votes
Floyd–Warshall can be used to detect the presence of negative cycles in directed graphs. This aspect has been widely used in the scheduling community in the form of detecting consistency of a simple temporal network. To answer your question, the values output by Floyd–Warshall will be correct even in the presence of negative edges as long as there are no negative cycles.

---
Tags: algorithms, graphs
---


# Question
Title: Pseudo-number generation compared to Blum-Micali
A few years ago I made a pseudo-random number generator to use in a monte carlo simulation for a lecture in my University.

My instructor ask me why I did that generator instead of using C equivalent rand.

The algorithm is $x\_{n+1} = e^{x\_n + k} \mod 1$ using float point values with $K$ big enough to contain a complete cycle inside $\epsilon$ (a very small value).

Yesterday I find another PRNG using a similar formula: Blum-Micali algorithm

$x\_{n+1} = g^{x\_n} \mod p$

The answers are... ***could my algorithm be based on the Blum-Micali one?***

***Could my algorithm contain the Blum-Micali properties?***

Thanks in advance.

# Answer
> 2 votes
No, your algorithm is fundamentally different. The resemblance is purely superficial. The Blum-Micali generator is based on integers modulo a large prime number, and leverages deep number theoretic ideas. Yours is based on the fractional part of real numbers (hence the "mod 1"), and is not based on number theory and not related to Blum-Micali. Blum-Micali is cryptographically secure. Your scheme seems unlikely to be.

---
Tags: pseudo-random-generators
---


# Question
Title: Adding the requirement of linear time on infinitely many inputs into the class $P$
Is the following problem computable in polynomial time?

**Input:** $\<M\_1\>$, encoding of a determinstic TM that runs in polynomial time ($L(M\_1)\in P$)

**Output:** $\<M\_2\>$, encoding of a determinstic TM that runs in polynomial time ($L(M\_2)\in P$), and satisfies:

* $L(M\_1)=L(M\_2)$ (they decide the same language)
* $\forall n\exists w\in\\{0,1\\}^n : \text {Time} (M\_2,w)=n$ (there exists an input of any length on which the TM runs in linear time)

# Answer
> 3 votes
\[EDIT 2\]

No, and in particular $M\_2$ does not exist in general.

Consider only TM's (and languages) that do not distinguish between the letters $0$ and $1$. Let's call them monochrome. Thus, membership of a word $w$ in a monochrome language depends only on $|w|$. Now let $L$ be a non-regular monochrome language in P. For example, $L$ can be the set of all words whose length is a square number.

Next, we exploit the fact that we use Turing machines (and not RAMs or whatever) and that the time bound is exactly $n$ (and not $O(n)$). In that time bound, all the TM $M\_2$ can do on the witness word $w$ (by which I mean the special input of a given length $n$ for which $M\_2$ runs in time $n$) is to read the input once from left to right. If at any step it does not go right, it cannot discern the length of $w$. As $L$ is by nature neither finite nor co-finite, $M\_2$ must measure the length exactly.

So, at least on the witness words, $M\_2$ acts like a DFA. Then, construct an NFA $A\_1$ which simulates $M\_2$ as long as $M\_2$ only goes right. The NFA $A\_2$ is obtained from $A\_1$ by replacing all edge labels by $\\{0,1\\}$. Then $A\_2$ recognizes $L$: For any input, $A\_2$ behaves just like $A\_1$ does for the respective witness word, including acceptance or rejection.

Thus, $L$ is regular, contradicting the choice of $L$.

---
Tags: complexity-theory, turing-machines, computability, time-complexity, polynomial-time
---


# Question
Title: Is it possible to transfer a point from one camera to another, given n corresponding points?
I have 2 images of a scene taken at one moment by two identical cameras (similar cameras intrinsic parameters) by to arbitrary locations and at two arbitrary orientations (different cameras poses). On the images n points correspondence p\_i1={x\_i1, y\_i1, z\_i1}↔p\_i2={x\_i2, y\_i2, z\_i2}, i=1,2,...,n are given. Let for simplicity z\_i1=z\_i2=f for all the points.

Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p\_01 known only at one image to be able to locate it on the second image p\_02?

My guess is (due to the fact that projection on a camera sensor plane is 3d-to-2d) it is not possible! And at most one may find a line on the 2nd image on which the additional point could be positioned.

I know that the task is solved with a homography matrix for two cameras having one center. I know it must be solvable for the case of all the points being coplanar.

But is it possible for arbitrary positioned cameras and arbitrary situated (non-coplanar in world frame) corresponding points?

# Answer
> Is it possible at any number of corresponding points n to derive a transformation relation from one camera view to another so that for an additional point p\_01 known only at one image to be able to locate it on the second image p\_02?

The answer is no - it is impossible. Each point on the image1 may in general correspond to an entire line on the image2 (see https://en.wikipedia.org/wiki/Epipolar\_geometry). The homography matrix is a projection matrix of one plane on another and, therefore, is useful when you have a plane object ( chessboard, book, painting etc.) pictured on both images.
> 2 votes

---
Tags: computational-geometry, computer-vision, image-processing, linear-algebra
---


# Question
Title: Finding a (Small-Big-Medium) subsequence
> Given a list of $n$ non repeating integer numbers $L:=(x\_1,\dots,x\_n)$ develop an algorithm that decides if there are $x\_{i\_1},x\_{i\_2},x\_{i\_3}\in L$ such that $i\_1\<i\_2\<i\_3$ and $x\_{i\_1}\<x\_{i\_3}\<x\_{i\_2}$. Only a yes-no answer is required.

The statement also suggest to use the "divide & conquer" strategy.

**My try** was the following:

I read the vector left to right

* If the list changes from increasing to decreasing, then it is clear that the last read number is lower than the maximum of the currently read list. So if it is greater than the minimum of the current list we can stop. This comparation can be done in $\mathcal{O}(1)$ if we keep track of the minimum of the currently read list.
* If the list changes from decreasing to increasing, then I look for the first number $m$ in the list which is a local minimum and it is lower than the last read number $c$. And then I look for a local maximum appearing after $m$ which is greater than $c$. If both searches are successful we can end. This searches can be done in $\mathcal{O}(\log n)$ time if we keep track of the local maximums and local minimums currently found (binary search).
* If the list keeps increasing we do the same as in the previous step.
* If the list keeps decreasing do nothing.

So the complexity is $\mathcal{O}(n\log n)$. I think the strategy is good, but an online judge rejected it. I don't know if it is due to a silly bug or because the strategy is indeed wrong.

Anyway, seeing the stats of the people who solved the problem, my solution is so memory consumming, so I really think it can be done better.

**Any idea?**

# Answer
> 1 votes
Your algorithm is wrong in the detail of finding a local maximum after $m$ as pointed out in the comments.

Divide-and-conquer can be used to solve this problem. If such $i\_1,i\_2,i\_3$ exist, there are four cases:

1. $i\_1,i\_2,i\_3\le n/2$, or
2. $i\_1,i\_2\le n/2$ and $i\_3\>n/2$, or
3. $i\_1\le n/2$ and $i\_2,i\_3\>n/2$, or
4. $i\_1,i\_2,i\_3\> n/2$.

Cases 1 and 4 can be checked by solving the sub-problems on $(x\_1,\ldots,x\_{n/2})$ and $(x\_{n/2+1},\ldots,x\_n)$. For other cases, numbers less than $\min\_{i\le n/2} x\_i$ are useless, so we can filter them in $O(n)$ time first. In the following analysis, we assume all numbers are no less than $\min\_{i\le n/2} x\_i$.

For case 3, $i\_1$ can be adjusted to $\arg\min\_{i\le n/2} x\_i$, then $i\_2$ and $i\_3$ exist if and only if $x\_{n/2+1}\<\cdots\<x\_{n/2}$ does not hold. Therefore we can also check this case in $O(n)$ time.

For case 2, since we have passed case 3, we can assume $x\_{n/2+1}\<\cdots\<x\_{n/2}$. Let $r\_1=n/2$, and $r\_{i+1}$ be the largest index smaller than $r\_i$ such that $x\_{r\_{i+1}}\>x\_{r\_i}$. Similarly let $l\_1=1$, and $l\_{i+1}$ be the smallest index larger than $l\_i$ such that $x\_{l\_{i+1}}\<x\_{l\_i}$. We mark each element with which sequence its index belongs to. This can be done in $O(n)$ time and space. Easy to see $i\_1$ and $i\_2$ can be adjusted to $l\_s$ and $r\_t$ respectively for some $s$ and $t$. Furthermore, we can adjust them such that no $l\_j$ or $r\_j$ lies between $l\_s$ and $r\_t$. So we can scan from $x\_1$ to $x\_{n/2}$ once to get all possible $(i\_1,i\_2)$ pairs in $O(n)$ time.

For example, suppose $(x\_1,\ldots,x\_{n/2})=(40,60,30,10,50,20)$, then $\\{r\_i\\}$: $6,5,2$, and $\\{l\_i\\}$: $1,3,4$. We mark these elements as $40\_l,60\_r,30\_l,10\_l,50\_r,20\_r$. Possible $(i\_1,i\_2)$ pairs are $(40,60)$ and $(10,50)$.

Every possible $(i\_1,i\_2)$ pair is an open interval. We need to determine whether any of $x\_{n/2+1},\ldots,x\_n$ falls into these intervals. Note $x\_{n/2+1},\ldots,x\_n$ are sorted and so are these intervals, we can determine it in $O(n)$ time.

Now checking for case 2 and 3 costs $O(n)$ time and space, so this algorithm costs $O(n\log n)$ time and space in total.

---
Tags: algorithms, divide-and-conquer, subsequences
---


# Question
Title: NL Completeness Log space reduction $PATH$ to $EQ_{DFA}$
Let $$PATH = \\{(G, s, t) | \exists \text{ a directed path from $s$ to $t$ in $G$}\\},$$ $$EQ\_{DFA} = \\{(M\_1, M\_2) | \text{DFA $M\_1$ and $M\_2$ over the same alphabet are equivalent}\\}.$$ Is there a log space reduction from $PATH$ to $EQ\_{DFA}$?

My attempt was to first show that there exists a DFA that accepts a string iff $M\_1$ and $M\_2$ do. At this point, I am unsure how to reduce the first problem to the second.

# Answer
> 1 votes
It is easier to think about a reduction from $\overline{PATH}$ (since it is NL-complete, this answers your question in the positive). You can treat the graph as a DFA, with initial state $s$ and a single accepting state $t$, and ask whether this automata is equivalent to some DFA for the empty language. Note that the alphabet here is not really important, and you could simply use fresh letters for each vertex.

---
Tags: complexity-theory, finite-automata
---


# Question
Title: Should we eliminate left recursion before using NPDA to simulate CFG?
I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser".

It says:

> If a language is context free, then some pushdown automaton recognizes it.
>
> Let A be a CFL. From the definition we know that A has a CFG, G, generating it. We show how to **convert G into an equivalent PDA**, which we call P.

But what if G has left recursion?

Does the NPDA construction in this book can halt when it simulate a CFG which has left recursion?

What's the different between NPDA and Recursive-Descent Parsing (full backtracking) in Compilers Principles, Techniques, & Tools ?

Thanks.

# Answer
As stated in the second paragraph following the one you quote, the PDA being constructed is *non-deterministic*, which greatly simplifies the construction.

A non-deterministic machine is allowed to have points at which more than one action is possible, without any procedure for determining which one is correct. It is only necessary to prove that one possible action leads to correct termination.

Such machines are easy to construct in formal theory but building them in the real world is trickier. A back-tracking parser must explore alternatives in some order; if it chooses an alternative which fails to terminate, then it will never get around to trying another possibility.

In contrast, the non-deterministic machine terminates acts as if it took all possible branches at the same time. If any branch terminates in an accepting state, the machine can can terminate and accept the input. This can be simulated by making copies of the machine at every branch, and simulating the progress of all currently active copies by repeatedly advancing each one by one step. (More copies might be made at each step of each copy, so it can get a little closer unwieldy.)

Consequently, it does not matter to the PDA if there is left-recursion in the grammar. To be sure, the left-recursion means that some of the possible execution paths will never terminate, but as long as there is a path which terminates, the PDA will choose it.

---

There is a subtle but important point which I left out of the first version of this answer, which is that the definition of the language recognised by the PDA is the set of inputs for which the PDA terminates in an accepting state. Nothing guarantees that the PDA will eventually terminate on other inputs, and it is quite possible that the PDA will never halt if it is given a input which is not in the language it recognises. (This is another reason why non-deterministic PDAs aren't much use in practical parsers.)

This should not be surprising. If the machine were guaranteed to halt, then there would exist a machine which recognised the complement of the language. But if that were the case, the complement of every context-free language would be context-free, and we know that not to be true.
> 3 votes

---
Tags: context-free, formal-grammars, pushdown-automata, parsers
---


# Question
Title: how does rotation works in AVL trees and what is a good way to understand it?
If we consider this tree with T1 and T2 as subtrees, and we want to rotate on x (rotating the edge between T1 and x), what is the result? how does it work then? Does the x stay in its place and T1 switch with T2? I saw multiple examples online but they had too many nodes and i couldn't really understand the concept of rotating and that's why i chose this simple example so that i (hopefully) can apply it in all other situations.

# Answer
> 4 votes
One needs *three* subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other.

The operation can be seen as a associative property: $T\_1\\;p\\; (T\_2\\; q\\; T\_3) = (T\_1\\; p\\; T\_2)\\; q\\; T\_3$ of the inorder traversal of the nodes in a binary tree.

Both the left and right diagram have the inorder $\mathrm{in}(T\_1)\\; p\\; \mathrm{in}(T\_2) \\; q\\; \mathrm{in}(T\_3)$, where $\mathrm{in}(T)$ is the inorder of subtree $T$.

It is pretty well explained at wikipedia Tree rotation, even with animated pictures.

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


title: Reduce ATM to CFTM

text:
# Question
Title: Reduce ATM to CFTM
How would I reduce $A\_{TM}$ to $CF\_{TM}$ when: $A\_{TM}=\\{\<M,w\>|M$ is a Turing Machine description and $w\in L(M)\\} $

$CF\_{TM} =\\{\<M\> | M$ is a Turing Machine description $L(M)$ is a context-free language.$\\}$

My problem is this: $A\_{TM}$ deals with all $TM$s how would knowing if some $TM$'s language is $CF$ help us know if $w \in L(M)$ ?

# Answer
If I read you correctly, you have the reduction wrong. Essentially, you need to use a transformation $f$ *from* an instance of $A\_{TM}$ *to* an instance of $CF\_{TM}$ such that $$ \langle{M, w}\rangle\in A\_{TM} \Longleftrightarrow L(f(\langle{M, w}\rangle)) \text{ is a CFL} $$ To this end, let's define $f(\langle{M, w}\rangle)$ to be the description of a TM $N$ where

```
N(x) =
   if x = a^(2^n) for some n
      return accept
   else if M(w) = accept and x = a^k for some k
      return accept

```

Now if $\langle{M, w}\rangle\in A\_{TM}$, it's clear that $L(N)=a^\*$, the language of all strings of *a*s which, being regular, is certainly a CFL. On the other hand, if $\langle{M, w}\rangle\notin A\_{TM}$ then we skip the **else** part of the code of $N$ and so $$ L(N) = \\{a^{2^n}\mid n\ge 0\\} $$ which is well-known to be not a CFL.

This, by the way is a very handy idiom: have both parts accept a non-"whatever" language and the last part activate to add enough strings to get what you need to make a "whatever" language.
> 2 votes

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


title: Finding the maximum of a random forest

text:
# Question
Title: Finding the maximum of a random forest
If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is it possible to efficiently find the subspace on which this function achieves its maximum? Enumerating all intersections could take exponential time in e.g. the case where each tree is a stump which bisects a different dimension.

It is possible to do better by computing bounds and doing some pruning, but I wonder whether a polynomial-time solution is possible.

If the leaf values are taken from $\\{0, 1\\}$ then this is a restricted max-clique problem, but I suspect it should be possible to exploit the decision-tree structure to create a faster algorithm.

Any thoughts?

# Answer
> 2 votes
Apparently, it's NP-hard. See the following paper:

Evasion and Hardening of Tree Ensemble Classifiers. Alex Kantchelian, J.D. Tygar, Anthony D. Joseph. ICML 2016.

Section 4.2 says that solving the problem exactly is NP-hard. However, the paper then goes on to develop techniques that, in practice, might often find an approximate maximum, using integer linear programming.

For a proof of NP-hardness, see Section 5.2 of Kantchelian's PhD dissertation.

---
Tags: algorithms, optimization, machine-learning, combinatorics
---


# Question
Title: Can pseudo random number generator generate all possible sequences?
Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the sequence Q, for any Q with any length? This is an existence question; does it exist or not, the process of finding a random number generator is irrelevant. The code for G is finite as is the seed s.

My intuition is that no, moreover, it's impossible to construct such a G with these properties. Unfortunately I can't justify my intuition.

# Answer
> 2 votes
If you are considering a pseudorandom generator that can work with seeds of any length, then the answer is "It depends". It depends on the pseudorandom generator. There are pseudorandom generators for which the answer is yes (e.g., $G(x)=x$, or any bijective $G$), and pseudorandom generators for which the answer is no (e.g., $G(x) = G'(\text{SHA256}(x))$, where $G'$ is a pseudorandom generator that accepts fixed-length seeds, is almost certainly such an example).

In practice, pseudorandom generators usually have a fixed-length seed. In that case, if the length of the output is longer than the length of the seed, then there exists an output that isn't produced by any seed (of that length). This follows from the pigeonhole principle.

In practice this almost certainly doesn't matter. Usually what matters is whether the output of the pseudorandom generator passes statistical tests, or whether it is indistinguishable from true-random bits.

---
Tags: pseudo-random-generators
---


# Question
Title: Perfect random number generation using normal numbers
This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the number of 1-bits and 0-bits before the $n^{th}$ bit are about the same). Doesn't this mean that the algorithm that computes bits of this normal number is a perfect random number generator? I thought deterministic random number generation is inherently pseudo-random, by information-theoretic limits or whatever. (Also: can anyone figure out the complexity of computing the $i^{th}$ bit using their method? The math in that paper is beyond me).

Finally: many easily-computable irrationals, like $\sqrt{2}$ and $\pi$, are very strongly conjectured to be normal. If that were proven, wouldn't that provide a poly-time perfect random number generator? Which is definitely impossible? What am I missing here?

# Answer
> 3 votes
> many easily-computable irrationals, like $ \sqrt{2} $ and $ \pi $

Therein lies your missing bit. They are in no way easy to compute if you want many of them, as you would for a real world application. A nuclear detonation simulation or Monte Carlo model of stock market behaviour requires millions /billions of pseudo random numbers. It's just that the formulae are simple to write down. They are not simple to use for digits far away from the decimal point.

12 trillion digits of $ \pi $ required the following not simple kit and about a week to compute using a BPP variant:-

Even more impressively (or uselessly depending on your point of view), the quadrillionth bit of $ \pi $ (which is a zero) took 1.2 million cpu hours to compute using \>1000 computers. I suppose computers have gotten faster since then, but it'll still be a while before you can do it on an iPhone.

Secondly, you'd be using the same sequence of numbers over and over, which isn't very random. So a smart chap might then decide to pick random sub sequences of say irrational number $ \frac{1}{ \sqrt{2} } $ to use. You'd then have to choose which digits /sequences to use, and how would you actually decide those? Use a random number generator?

In short, it's unfeasible to use this technique for general pseudo random number generation. Which is why no one does.

Smallish caveat. Very short sequences from irrationals like these are used as nothing up my sleeve numbers in cryptography for variable initialisation.

---
Tags: randomness, pseudo-random-generators
---


title: Measuring one way network latency

text:
# Question
Title: Measuring one way network latency
This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is posed as a puzzle I think it fits on this web site because of its applicability to the design and experience of communication protocols such as in online games, not to mention NTP.)

Suppose two robots are in two rooms, connected by a network with differing one-way latencies as shown in the graphic below. When robot A sends a message to robot B it takes 3 seconds for it to arrive, but when robot B sends a message to robot A it takes 1 second to arrive. The latencies never vary.

The robots are identical and do not have a shared clock, though they can measure the passage of time (e.g. they have stop watches). They do not know which of them is robot A (whose messages are delayed 3s) and which is robot B (whose messages are delayed by 1s).

A protocol to discover the round trip time is:

```
whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

```

Is there a protocol to determine the one way trip delays? Can the robots discover which of them has the longer message sending delay?

# Answer
The following diagram, from a blog post I wrote, is a visual proof that it's impossible:

Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). The first packet always reaches the server at 1.5s on the server's clock, the second always reaches the client at 2s on the client's clock, etc. The packet contents and local arrival times are the *only things* a protocol could be based on, but the contents and arrival times can be held constant as the asymmetry varies by also varying the initial clock skew.

Basically, asymmetry in the one-way latencies looks *exactly* like clock skew. Since the problem states we don't start off knowing the initial clock skew or the one-way latency asymmetry, and varying one looks like varying the other so their effects are indistinguishable, we can't separate their contributions in order to solve for the one-way latency asymmetry. It's impossible.

More formally, you can't solve for edge lengths when given only the lengths of the cycles. The cycle basis has $n-1$ degrees of freedom, corresponding to $n-1$ unknown clock skews relative to one of the participants. You can always hide the one-way latencies, even when there are many participants:

If you're not so visually inclined, I have another intuitive argument. Imagine a time portal to a hundred years in the future. As you chat across it to someone on the other side, you realize the conversation is totally normal despite the hundred year asymmetry in one-way delays. Any observable effect would have been obvious on that scale!
> 14 votes

# Answer
I think it is impossible to figure out one-way latency just by comparing stopwatches.

$A$ sends $B$ his clock $C\_{A1}$, let's say its value is 5.
$B$ acknowledges the message at time $C\_{B1}=1$
$A$ sends his clock again, $C\_{A2}=9$ (initial + round-trip latency).
$B$ receives at time $C\_{B2}=5$.
And so on. Neither $A$ or $B$ can figure out when the other robot received a message with respect to their watches.

Maybe if you make it a bounty question someone will crack it. Until then, kudos.
> 1 votes

# Answer
I have found a way to BOTH discover which node is who (i.e. who has the longer message delay) AND estimate the one way trip delay. While the other answers are correct they are ONLY considering direct clock measurement approached which of course cannot work. However as I am proving here this is only part of the story as here is my working algorithm for the above:

Assume as in real life:

* Links of finite bandwidth b
* Each node has unique address (e.g. A and B)
* Packet size p much smaller than the bandwidth\*latency product
* Nodes A and B are able to fill the channel
* Nodes have a *random()* function

Each node fills the channel with its own packets (marked A or B respectively) OR forwards the packets it received from other nodes as follows:

```
Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to
          either forward that packet from the other node
          or discard that packet and forward my own packet

```

**Intuitive Explanation** Since A's bandwidth\*latency product is higher (because latency is higher) A will manage to have more packets received than B, therefore *each Node can know who they are in the diagram*.

Furthermore, *with enough convergence time* of running above algorithm the ratio of packets of A to B will denote the *actual ratio of RTT delay of A to B and therefore the desired OTT*.

**SIMULATION RESULT TRACE** Here is a simulation that proves the above and shows how A successfully converging toward 3 second delay and B converging around 1 second delay:

*Explanation of Figures:* Each line represents 1 second of time (packet size is chosen to have 1 second transmission time for clarity). Note that each node can start the algo at any time not in any particular sequence or time. The columns are as follows:

* NODE A receives : What node A sees in its receiving side (this is also P4 below)
* NODE A injects : What node A sends out (note this is A, or randomly A or B)
* P1, P2, P3 : The three packets that are in transit (in order) between A and B (1 second transmission means 3 packets are in transit for a latency of 3)
* NODE B receives : What B sees in its receiving side (this is P3)
* NODE B injects : What B sends out (note this is B, or randomly A or B per algo)
* P4 : The packet in transit from B to A (see also P1, P2, P3)
* A counts A : What A counts for the A packets it has seen
* A counts B : What A counts for the B packets it has seen
* B counts A : What B counts for the A packets it has seen
* B counts B : What B counts for the B packets it has seen
* A-\>B : The latency that A estimates towards B (ratio of RTT of 4 seconds based on packets seen)
* B-\>A : The latency that B estimates towards A (ratio of RTT of 4 seconds based on packets seen)

As we can see both nodes converge and stay around their true latency (actually we do not see that for A because more seconds are needed to converge but it does converge same behavior as B)

Better filters could converge faster but we can clearly see how they both converge around the correct values for their delays, therefore they can *exactly* know know their delay (even though I am showing their estimation only for illustration).

Also, even if bandwidths between the links are different the above method could still hold (although one will have to think about it more to be more certain) by using packet pairs to figure out bandwidth estimates and then just apply to the proportion equation above.

**Conclusion** We provided an algorithm for both A and B to know their position in the network and know their latency to the other node for the above diagram. We used a network measurement estimation method rather than clock-based approaches which indeed cannot lead to a solution due to recursive clock sync issue.

**Note** I now edited this answer providing all the simulations because no one would believe me I solved it so far as you can see in the first comments. Hopefully with these results someone can be more convinced and approve to help everyone at least find one error or correctness in this network measurement puzzle!
> 0 votes

# Answer
This is an answer to @user3134164 but is too big for a comment.

Here's my attempt at showing why this can't work (mathematical approach). Let's call $P\_x$ the probability that robot $x$ chooses its own packets when it receives one of the other robot's packets, and $R\_x$ the probability that a packet robot $x$ received is its own. After stationary regime has been achieved (that is, after an "infinite" amount of time, ie all convergence is done), we have the following :

* $R\_1 = (1 - R\_2) \times (1 - P\_2)$, and similarly $R\_2 = (1 - R\_1) \times (1 - P\_1)$. The idea is that if a robot receives one of its own packets, it means the other robot received it instead of one of its own (hence the $1 - R\_2$) and that it still chose to send it instead of one of its own (hence the product by $1 - P\_2$).
* This gives a system of two equations with two unknowns, $R\_1$ and $R\_2$. You might want to solve it, but it doesn't really matter. In fact, the ratios you're looking for are respectively $\frac{R\_1}{1 - R\_1}$ and $\frac{R\_2}{1 - R\_2}$. As you can notice, the only terms that appear in those expressions are the probabilities at which each robot chooses their own packet over the other's. The latencies don't even appear in the formula simply because both robots are pumping out packets constantly, so both are constantly receiving packets. They will indeed receive different ratios of packets, but it will only depend on the aforementionned probabilities.

This is why I believe this will lead you nowhere. Please do point out any mistake I could have made during this reasoning.
> 0 votes

---
Tags: computer-networks, protocols, distributed-systems
---


# Question
Title: Regex for divisibility by 123 in binary strings
Is there a regex that checks for divisibility by 123 in binary strings?

This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative Exercises section).

Creating a regex to check if a binary string is divisible by 3 is simple: (0|1(01\*0)\*1) *

A regex to check if a binary string is divisible by 2 is also simple: (0|1)\*0

And there are many questions on the Internet asking for a regex for divisibility by 7.

However, I could not find any resources related to a regex for checking if a binary string is divisible by 123.

These are the representations of some multiples of 123 in binary:

> 0 = 0
>
> 123 = 1111011
>
> 246 = 11110110
>
> 369 = 101110001
>
> 492 = 111101100
>
> 615 = 1001100111
>
> 738 = 1011100010
>
> 861 = 1101011101
>
> 984 = 1111011000
>
> 1107 = 10001010011
>
> 1230 = 10011001110

There doesn’t seem to be a pattern that stands out (even though there is probably one, since the question to check 123-divisibility with a regex exists).

There are, however, some similarities in some strings:

123, 246, 492 and 984 in binary are basically the same, but 246 has an extra 0 in the end, 492 has two extra 0s in the end and 984 has three extra 0s in the end.

369 and 738 in binary are basically the same, but 738 has an extra 0 in the end.

615 and 1230 in binary are basically the same, but 1230 has an extra 0 in the end.

Any ideas for a regular expression for such strings? Thanks!

# Answer
Here is a way that succeeds, albeit with a lot of work.

First, construct a DFA for the language. That is actually quite simple: It has states $0$ through $122$ (for the remainders), start state and only accepting state is $0$, the transitions from state $n$ go to $(2n \mod 123)$ for label $0$ and to $(2n+1 \mod 123)$ for label $1$.

Now, convert that DFA to a regular expression. The result is not likely to be simple, small or nice.

If you use an extension to regular expressions that allows intersection, you can also do the above with $41$ instead of $123$ and then intersect with the expression you have for divisibility by $3$.
> 5 votes

---
Tags: regular-expressions
---


# Question
Title: Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?
Until just now I thought that I have fully understood Rice's theorem but this example irritates me:

$L^\* = \\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H\_{all} \mbox{ } \\}$ where $H\_{all}$ denotes the totality problem. Correct me if I'm wrong but in my opinion this is not the same as $L' = \\{ \langle M \rangle \mid M \mbox{ is a Turing machine that halts on every input} \mbox{ } \\}$. Here, I could apply Rice's theorem and conclude that L' is not decidable but in the other case, L\* is actually empty so the theorem is not helpful.

# Answer
Well, Rice's theorem doesn't apply but we don't need it—$L^\*$ is empty and therefore decidable.

To figure this out, we just need to be meticulous about what these languages are.

* $L^\*$ is the set of all Turing machines that recognize the totality problem. It is the set of all Turing machines that can take in a Turing machine $\langle N\rangle$ and accept just if $N$ halts on all inputs.
* $L^\prime$ is the set of all Turing machines that halt on all inputs.
* They're different languages: $L^\*$ is the set of all machines whose language is $L^\prime$.

The totality (all-halt) problem is unrecognizable: there is no Turing machine that takes in a TM $\langle N\rangle$ and accepts just if $N$ halts on all inputs. (Consider a reduction to the halting problem.) Therefore, $L^\*$ is empty and $L^\prime$ is unrecognizable.

$L^\*$ is empty, therefore decideable (when given a machine $\langle N\rangle$ and asked if it recognizes the totality problem, always say no.) $L^\prime$ is unrecognizable, which is stronger than merely undecidable.

But, if we didn't already know that $L^\prime$ was unrecognizable, we could use Rice's theorem to show that $L^\prime$ is undecidable. There's a string in $L^\prime$, for example the Turing machine that ignores its input and always accepts. There's a string not in $L^\prime$, for example the Turing machine that ignores its input and loops forever.

---

Also, a side note: Rice's theorem says that non-trivial language properties of TMs are undecideable. As you point out, there are two trivial languages which the theorem doesn't cover: the empty language $\varnothing$ and the language of all strings $\Sigma^\*$. Note that we don't need Rice's theorem for these languages to determine decidability— we already know they're decideable. In fact, they're *regular*: there's a DFA that accepts all strings, and a DFA that accepts no strings.
> 2 votes

# Answer
Rice's theorem states that the problem of determining, given a Turing machine $M$, whether $L(M)$ belongs to some set of languages $S$ is decidable if and only if $S$ is trivial, that is, either $L(M) \in S$ for every Turing machine $M$, or $L(M) \notin S$ for every Turing machine $M$.

Hence all you need to do in order to determine whether $L^\*,L'$ are decidable, is to determine whether the corresponding sets $S^\*,S'$ are trivial or not.
> 1 votes

---
Tags: turing-machines, computability, undecidability, rice-theorem
---


# Question
Title: Chord protocol - How should I go about mapping nodes to placeholders on the ring?
In the real world, how is a node mapped to the position on the ring, Each nodes's IP address is hashed using SHA-1 hashing algorithm which will produce this hash - 73.128.154.69 hashed into 60CBFB98C9052A425D684A2C3D8D8D38424129A3. This should have been in the range of 0 to (2^m) - 1 where m is the number of bits. I have the following questions -

1. How should I convert this hashed value into a number?
2. Will the IP address after leaving and re-joining the ring get the same placeholder position?
3. Are placeholders or node positions ordered numbers at all?

# Answer
> 1 votes
Take the last m bits of the hash. View it as a number in binary. That's how you convert the hashed value into a number. The position is a number. That should answer your questions 1 & 3.

Now that you know how it works, you should be able to answer question 2 yourself. If not, go back and read the original paper (especially Section IV.B), which should make this clear.

---
Tags: distributed-systems, communication-protocols, protocols, peer-to-peer
---


# Question
Title: How do I create a pushdown automata for a language where some characters occur in times in multiples of 2 or 3
I have an assignment to create a pushdown automata for $L=\\{a^{3n} c^m b^{2n} \mid n,m\geq 0, m\\!\mod\\! 2=0\\}$ and I am confused how to handle $2n$ and $3n$.

# Answer
Informally, you are going to use the stack of the automaton to keep track of $n$ and make sure that there really are $2/3$ as many $b$s as $a$s. So every time you see three $a$s in the initial stage you push a token onto the stack, and every time you see two $b$s in the final stage you pop a token from the stack, and then you only accept a word if the stack ends up empty. The states of the automaton can deal with making sure that there are exactly $3n$ $a$s with none left over and likewise $2n$ $b$s and that the $a$s, $b$s and $c$s appear in the right order.
> 1 votes

# Answer
Although the general question is poorly asked, I shall provide some general advice nevertheless, as I think it is educational in general (feel free to comment with "Please consider not to encourage undesirable posting behaviour.", I'm thinking I can contribute. Some bad questions have good answers)

The advice given by Raphael is good and can be generalised: whenever you have a difficult language to construct, try to tackle its separate parts first. (try to *divide and rule*!) If you don't know how to create a PDA for the language $L\_1=\\{a^{3n} \mid n\geq 0\\}$ or $L\_2 = \\{b^{m} \mid m\\!\mod\\! 2 = 0\\}$, how do you think to create a PDA for $L$?

Remember the general advice (this one applies even for high level research!) (this is a quote, I someone knows from whom please tell me)

> When you're trying to solve a *hard* problem and can't do it, try to find an easier problem you *can't solve* either. Try to solve that one and re-apply this rule in case of failure.

At the very least, this should get you to the essential part that you fail to understand, which means you can ask the right question!

---

Now, a bit more specific: I will not tell you the answer, for this will not help you. As Andrej Bauer has said on this site

> What makes you think that the point of a homework problem is its solution?

But I can provide a way to start. Let's try to solve $L\_1$. How can we *count* in a PDA? How can we ensure, that after we can seen an $a$ trice in a row, we remain on a path to an accepting state? Think about this. If you still have doubts, edit you question with your specific problems. This, I think, is the best way to solve such questions. At the very least, what is important here is that *you* solve the question, because I'm not going to make your exam.
> 0 votes

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


# Question
Title: Non recursively enumerable language proof by reduction to non-HP
I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the language to the non halting problem which is not r.e.

For example, if I have

$$L\_2 = \\{\langle M\rangle\mid M \text{ is a TM and }|L(M)|\leq 3\\}\\,.$$

I construct $\tau(\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it erases its input, copies $M$ and $x$ to its tape, and runs $M$ on $x$; it accepts if $M$ halts on $x$. Then I prove the reduction is valid (see website)

But then if I have the language

$$L\_4 = \\{\langle M\rangle\mid M\text{ is a TM that accepts all even numbers}\\}\\,,$$

I construct $\tau (\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it runs $M$ on $x$ for $|w|$ steps; it rejects if $M$ halts on $x$ within $|w|$ steps, and accepts otherwise.

I know this may sound like a stupid question but beginnings are always hard until you understand the main logic behind it but why does $M'$ need to reject when $M$ halts? Why not accept when $M$ halts like in the first case?

# Answer
From a programming perspective, a reduction argument is often like this: "If you have a subroutine that can effectively solve problem A, here's how you can use it to solve problem B. But problem B is unsolvable, therefore no such effective subroutine exists."

In your case, the non-halting problem (Is my input $\langle M, w\rangle$ a Turing machine and a word that makes it loop forever?) is not recursively enumerable. If we can make it recursively enumerable by adding an effective subroutine for problem B, then no such subroutine for problem B exists.

---

The language $L\_2$ of Turing machines that accept three or fewer strings is not r.e. If it were, then there's a subroutine B which recognizes whether a TM accepts three or fewer strings. So: imagine a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$ which ignores its input and simulates $M$ on $w$. If the simulation finishes, $M^\prime$ accepts; otherwise it loops forever. So, $M^\prime$ accepts all inputs if $M$ halts on input $w$. $M^\prime$ doesn't accept any strings if $M$ loops forever on input $w$.

Our program makes $M^\prime$, then asks B whether $M^\prime$ accepts 3 or fewer strings. If it does, $M$ must loop forever on input $w$. We should accept ("LOOPS FOREVER"). Otherwise, we don't ("DOESN'T LOOP FOREVER").

Because our program solves an unsolvable problem with help from B, such a subroutine B cannot exist.

---

The language $L\_4$ of Turing machines that accept all even numbers is not r.e. If it were, then there's a subroutine C which recognizes whether a TM accepts all even numbers. So, imagine we have a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$. On input $x$, the machine simulates $M$ on $w$ for $|x|$ steps, then rejects if $M$ has finished by then; otherwise it accepts. So, $M^\prime$ uses its input as a timer: it rejects all strings that are longer than the number of steps $M$ takes to halt on $w$. (If $M$ never halts, $M^\prime$ accepts all strings. If $M$ halts, $M^\prime$ accepts all short strings and rejects all long strings.) So if $M$ never halts, $M^\prime$ accepts all strings, specifically including all even numbers. If $M$ halts, $M^\prime$ rejects all long strings, specifically including all large even numbers.

So, our program constructs $M^\prime$ and asks C whether it accepts all even numbers. If C says yes, it means that $M^\prime$ accepts all strings because $M$ loops forever on $w$. We accept ("LOOPS FOREVER"). If C says no, it means that $M$ eventually halts on input $w$. We reject ("DOESN'T LOOP FOREVER").

---

In both cases, $M^\prime$ uses "accept" to mean "LOOPS FOREVER", and "reject" to mean "DOESN'T LOOP FOREVER". In the first case, we made $M^\prime$ accept all strings when $M$ *doesn't* loop forever. In the second case, we made $M^\prime$ accept all strings when $M$ *does* loop forever. Those differences contributed to the discrepancy.
> 1 votes

---
Tags: turing-machines, reductions, halting-problem
---


title: Calculating unbalanced binary trees

text:
# Question
Title: Calculating unbalanced binary trees
Two-part question:

1. Is there any more specific name than "unbalanced binary tree" to describe the tree below? The distinguishing characteristics are:

i. The root node and left children must have either 0 or 2 children.

ii. Right children must have 0 children.

iii. All nodes must be positive non-zero integers.

iv. Any node with children must equal the sum of its children.
2. Given the value of the root node (in this case, 77), is there a standard algorithm to efficiently calculate all possible trees of this type?

* i.e. `(77, 76, 1)`, ..., `(77, 1, 76)`, `(77, (76, 75, 1), 1)`, etc.

---

```
         77
        /  \
       68   9
      /  \
     48   20
    /   \
   47    1
  /  \
 42   5

```

# Answer
Here is an algorithm to enumerate all possible trees meeting your conditions. These trees are in bijection with their sequence of leaves. Given a root value $n$, iterate sequence lengths from 1 to $n$. For a length $l$ you wish to enumerate all sequences of positive numbers of length $l$ adding to $n$. If $l=1$ choose the sequence consisting of $n$. If $l\>1$ enumerate possibilities 1 to $n-l+1$ for the first number $a$ and generate remaining numbers as a sequence of length $l-1$ adding to $n-a$.

In Haskell this could be implemented as:

```
seqsTo n = concatMap (seqsToOfLength n) [1..n]
seqsToOfLength n 1 = [[n]]
seqsToOfLength n l = concatMap (\a -> map (a:) (seqsToOfLength (n-a) (l-1))) [1..n-l+1]

```
> 1 votes

# Answer
It is a special caterpillar. Let $d(i)$ be the number of such trees with root $i$. We have $d(1)=1$; and $d(n)=\sum\_{i=1}^{n-1}d(i)+1$, where "plus 1" is for the case of no children and $d(i)$ in sigma for the case that the left child is $i$. One can easily compute $d(n)$ in $O(n)$ time using a simple loop. Or it is not hard to solve the recurrence relation and get $d(i)=2^{i-1}$ for $i\geq 1$.
> 1 votes

---
Tags: algorithms, binary-trees
---


# Question
Title: Understanding context free grammars in conjunction with PDA
I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really interested in many of the topics and I hope you can help me realign my knowledge about the CFG and PDA.

**So my question is:** could you tell me if what im writing here is correct? If not could you tell me what is wrong in my interpretation?

**What I think I understood**:

A state of a pushdown automata is equivalent to a set of production rules (or is it a production rule?) and these production rules contain replacement rules.

Depending on what character we read from our input we add an appropiate stack character or replace a character in the stack which is defined by one of the replacement rules.

So lets say we have defined the following production rule: a^n b^m : m != n

the replacement rules looks like:

```
production rule {
    input ; Stack Symbol -> To Do On Stack

    a ; nothing -> A
    a ; A -> AA
    b ; A -> nothing
    emtpy -> #
}

```

for every "a" we read we add an A and for every "b" we remove an A. The stuff what happens in my PDA stack is therefore defined in the replacement rule of my production rule?

Now if I wanted to parse a nested input like: "{hello world {fooBar is cool + 5}}"

I assume I need two production rules each with different replacement rules for our stack:

```
RULE 1:

{ ; nothing -> O
[a-zA-Z] ; O -> L

```

ok seriously I have to stop here because I have no idea what im doing. I would appreciate it if you could tell if my interpretation is wrong and how to handle the last example.

I am sorry if I couldnt be more concise. Im currently a bit confused with this.

# Answer
A PDA is a machine with a certain set of states and an infinite, initially empty, stack. It also has an input tape with the input word written on it. As long as there's input remaining, the machine reads the next character of input, checks its current state, and pops off the top character of the stack to read it. Based on what it finds, the PDA then switches into some new state and pushes a new character onto the stack.

The set of all languages PDAs can recognize is called the context-free languages. They are context-free roughly because what happens next depends only on the character at the top of the stack, rather than all the context beneath it in the stack. A PDA is finished when it goes into a special state for accepting or rejecting the input word. (Some people instead say that a PDA is finished when the stack is empty.) The language of a PDA is the set of all words that it accepts.

---

A context free grammar is a set of production rules. For simplicity, a production rule looks like $A \mapsto B$ or $A\mapsto BC$ or $A \mapsto \mathtt{a}$ or $A \mapsto \epsilon$. These respectively mean "If you have the symbol $A$, you may replace it with $B$ / $BC$ / the character $\mathtt{a}$ / the empty string." A production rule is a rule that allows you to transform a symbol. The capital letter symbols are called nonterminals; they are sort of like variables. The symbols like $\mathtt{a}$ are terminals; they are sort of like constants. There is a special nonterminal symbol called the start symbol, usually denoted $S$. The language of a context-free grammar (set of rules) is the set of all strings of terminals (like $\mathtt{abcde}$) you can make starting from the start symbol $S$ and applying any of the rules until only terminal symbols remain.

---

It turns out that context-free grammars (CFGs) are equivalent to pushdown automata (PDAs) because they can recognize the same languages. In particular, for every CFG there's a corresponding PDA, and vice versa.

Here's the CFG-\>PDA recipe. If you have a CFG, make a PDA with one start state and one reject state. Push the start symbol onto the stack. Then, loop: pop off the top symbol of the stack. Nondeterministically pick a production rule with that symbol on the left hand side. Push all the symbols on the right hand side of that rule onto the stack (make sure the leftmost symbol ends upon top). If the symbol at the top of the stack is a terminal character, make sure it matches the next character of input, otherwise reject. If the stack becomes empty, accept.
> 2 votes

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


title: Determine if a language is decidable

text:
# Question
Title: Determine if a language is decidable
$$ L=\\{\<M\>|M\ is\ a\ TM\ ;\ ∃x,|x|\<5 ;\ M\ rejects\ x\\} $$

How can i prove that $L \notin R$? I can't see how Rice's theorem be used here since the conditions are not met (The constrain $M\ rejects\ x$ is about the machine architecture and cannot be expreseed by a non-trivial language)

# Answer
> 1 votes
Actually "M rejects $x$" just means that $x \notin L(M)$, which is a statement about languages so Rice's theorem applies.

---

Use the decider for $L$ to solve the halting problem: On input $M$ and $w$, construct the machine $M\_w$ that ignores its input and simulates $M$ on $w$. If the simulation halts, $M\_w$ accepts. Otherwise, it doesn't.

So $M\_w$ either accepts all strings (if $M$ halts on $w$) or no strings (if $M$ doesn't halt on $w$). You apply your decider to $M\_w$. If $M\_w$ accepts all strings, the decider will REJECT: the machine doesn't reject any short strings. If $M\_w$ accepts no strings, the decider will ACCEPT: the machine rejects some short strings (in fact, all of them). We return the opposite answer, solving the halting problem.

It follows that a decider for $L$ can effectively solve the halting problem; therefore, such a decider does not exist.

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


# Question
Title: TM to detect repeats of any other TM and input value
I read a previous question, Is a secondary TM sufficient to detect all loops?, which asks if there is a TM1 that takes the description and input of any other TM2 to detect if TM2 will loop for the input.

One answer was to run two copies of TM2, the second at 1/2 the speed.If the second machine ever reaches the same configuration as the first, a loop was detected. Seems to me that the process requires a third entity to do the comparison at every step. Since neither copy output their complete configuration, it is not obvious this third entity and the complete system of all three entity can be a TM. Another easy way is for a second TM2 to keep a list of all configuration of TM1 and check to if there any repeats. This can surely work. But again, what is not obvious is if this complete system of the checking process on TM2, the running of TM1 and outputting TM1's complete state configurations to TM2 can be realized as a TM. TM1 can't output its own states to TM2, so TM2 somehow has to grab these from TM1, not just its output but TM1's complete state information or there has to be a third entity that does the communication.

My question: Can this process be implemented as a Turing machine?

# Answer
I think you're wondering how one Turing machine can keep track of what another Turing machine is doing, including checking that machine's state and knowing what's on its tape. After all, Turing machines don't have a method for "outputting" a description of what they're doing—they merely run.

But a Turing machine that takes in a description of another Turing machine can simulate that second machine on its tape, the same way that you can simulate running a TM using pencil and paper. The TM writes down the current configuration of the simulation, including what the simulated current state is, what the second machine's tape says, and where the machine's tape head is. It follows rules for moving the tape head, writing to the simulated tape, and changing the simulated current state.

That's how one machine can simulate another. Another helpful trick is that a TM can have any finite number of tapes without affecting its capabilities—a three-tape TM is no more powerful than a one-tape TM. So if it's conceptually helpful, you can give the TM a separate tape for each concurrent simulation.
> 1 votes

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


# Question
Title: Can a Turing machine determine if a set is accepted by a another Turing machine?
Can a Turing machine $M\_A$ determine if the Turing machine $M\_B$ accepts the set $W\_k$?

I am curious about the answer to this as I am thinking about using the truth value of it on using it for a recursive enumerability proof.

# Answer
Is the language of all machines that accept $W$ recognizable?

$$L\_W = \\{\langle M\rangle : L(M) = W\\}$$

The answer is unfortunately no, except in trivial cases. If $W$ is unrecognizable, then $L\_W$ is empty (no machine recognizes $W$) and hence decidable (The machine that rejects all inputs decides $L\_W$). In all other cases, **$L\_W$ is unrecognizable**. We can show this using reductions from the unrecognizable rejection problem— the problem of determining whether a machine rejects a word.

* If $W=\Sigma^\*$, the set of all strings, then $L\_W$ is unrecognizable (a standard result: "$M\_x(w)$ simulates $M$ on $x$ for $|w|$ steps and accepts if the simulation doesn't accept by then." provides a reduction from the problem of deciding whether $M$ rejects $x$).
* If $W\neq \Sigma^\*$ is decidable, then $L\_W$ is unrecognizable. Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N\_x(w)$. The new machine decides whether $w\in W$ and accepts if so. Otherwise, it simulates $N$ on $x$ and does what it does. The machine $N\_x$ therefore accepts $W$ (if $N$ rejects $x$) or all strings (if $N$ accepts $x$).

If we could recognize whether $N\_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.
* If $W$ is recognizable but undecidable, then $L\_W$ is unrecognizable: Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N\_x(w)$. The new machine simulates $N$ on $x$ for $|w|$ steps. If the simulation accepts in that time, the machine accepts. Otherwise, the machine tests whether $w\in W$ and does what it does.

Hence $N\_x$ accepts the union of $W$ and the set of all strings longer than the number of steps it takes for $N$ to accept $x$. If $N$ rejects $x$, $N\_x$ recognizes $W$. If $N$ accepts $x$, $N\_x$ recognizes additional words. (Note that because $W$ is undecidable, there must be arbitrarily long strings not in $W$. Otherwise, a DFA could decide $W$ by memorizing the short strings and using a length requirement for the long ones. Hence $N\_x$ recognizes a strict superset of $W$ if $N$ accepts $x$.)

If we could recognize whether $N\_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.
> 2 votes

# Answer
While user326210's answer analyzes the language $\\{\langle M\rangle\mid L(M)=W\\}$, my answer analyzes the language $L\_W=\\{\langle M\rangle\mid L(M)\supseteq W\\}$.

# $W$ is an empty set

$L\_W$ is the set of encodings of all TMs, thus decidable.

# $W$ is a finite but not empty set

$L\_W$ is undecidable but recognizable.

Suppose $L\_W$ is decidable by $D\_{L\_W}$, we can build a decider $D\_H$ using $D\_{L\_W}$ to solve halting problem. The decider $D\_H$ works as follows:

On input $\langle \langle M\rangle, w\rangle$:

1. Construct a TM $M'$ working on input $w'$ as follows:

1. Run $M$ on $w$.
    2. If $w'\in W$ (recall that $W$ is finite), *accept*. Otherwise *reject*.
2. Run $D\_{L\_W}$ on $\langle M'\rangle$.
3. If $D\_{L\_W}$ accepts, *accept*. Otherwise *reject*.

We can see if $M$ halts on $w$, $M'$ accepts $w'$ if and only if $w'\in W$, which means $L(M')=W$. Otherwise, $M'$ accepts nothing. Therefore $D\_{L\_W}$ accepts $\langle M'\rangle$ if and only if $M$ halts on $w$, so $D\_H$ is indeed a decider for halting problem. Hence $L\_W$ is undecidable by contradiction.

To recognize $W$, a TM can run $M$ on all strings in $W$ (recall again that $W$ is finite) and accepts if $M$ accepts all these strings. This TM recognizes $L\_W$.

# $W$ is an infinite set

$L\_W$ is unrecognizable.

Suppose $L\_W$ is recognizable by $M\_{L\_W}$, we can build a recognizer $M\_R$ using $M\_{L\_W}$ to recognize $\overline{A\_{\mathrm{TM}}}=\\{\langle\langle M\rangle,w\rangle\mid M\text{ does not accept }w\\}$, which is unrecognizable. $M\_R$ works as follows.

On input $\langle \langle M\rangle, w\rangle$:

1. Construct a TM $M'$ working on input $w'$ as follows:

1. Run $M$ on $w$ with at most $|w'|$ steps.
    2. If $M$ accepts, *reject*. Otherwise *accept*.
2. Run $M\_{L\_W}$ on $\langle M'\rangle$.
3. If $M\_{L\_W}$ accepts, *accept*. If $M\_{L\_W}$ rejects, *reject*.

We can see if $M$ accepts $w$, say with $n$ steps, then $M'$ accepts $w'$ if and only if $|w'|\<n$, which means $L(M')$ cannot be a superset of $L\_W$ (recall that $L\_W$ is infinite). Otherwise $M$ accepts every string, which means $L(M')$ is certainly a superset of $L\_W$. Therefore $M\_{L\_W}$ accepts $\langle M'\rangle$ if and only if $M$ does not accept $w$, so $M\_R$ is indeed a recognizer of $\overline{A\_{\mathrm{TM}}}$. Hence $L\_W$ is unrecognizable by contradiction.
> 1 votes

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


# Question
Title: Finding $d$ in RSA Encryption mathematically and by hand
I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.

Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively prime to $(p-1)(q-1)$, $e=23$ So the public key is $(23,143)$

Now I want to find out $d$ and for that I've come across $2$ different methods. First is using this formula $$23 \cdot d \equiv1 \mod120$$ where I can't seem to work out what $d$ is. I tried to solve it like a quadratic equation $$23x=1 \mod 120$$ $$x=\frac {1}{23}$$ which doesn't make sense. Then I came across this other method to find the value of $d$.

$$∃k : e \cdot d +k(p-1)(q-1) \equiv1$$ $$23 \cdot (47) + (-9)\cdot120=1$$ So the private key would be $(47,143)$ but there is no mention of how they figured out the value of $d$ and $k$. That's why I need some help to work out the value of $d$ in a way so that I can find it given any problem.

# Answer
> 1 votes
Suppose that you know $e$ and $n$, and want to find out $d$ such that $ed \equiv 1 \pmod{n}$ (this is possible if $(n,e) = 1$). An efficient way to do this is to use the extended Euclidean algorithm, which finds two integers $a,b$ such that $an + be = (n,e) = 1$. You can use $d = b \bmod{n}$, since $de \equiv be \equiv 1-an \equiv 1 \pmod{n}$.

---
Tags: algorithms, complexity-theory, algorithm-analysis, cryptography, encryption
---


# Question
Title: Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free
Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language $L = \\{a^ib^jc^k \mid i ≠j ≠ k ≠ i \\}$ is not context free.

From my understanding, we want to prove that all 3 conditions of the pumping lemma hold. This will not guarantee that the language is context-free. However, I have found a case where it breaks

Let the string be $abbccc$

If $u = \lambda$, $v = a$, $x = aa$, $y = a$, $z = bbccc$.

Therefore, when we pump the string for $i = 2$, we get $aaaaaabbcccccc$, which is NOT in the language because we have the same number of $a$'s and $c$'s. How is this possible?

# Answer
The Pumping Lemma states: "... there exists a constant $p$ such that for each word $w\in L$ with $|w|\ge p$ there exists a decomposition $w = uvxyz$ such that ...", where $p$ is the pumping constant.

You have chosen your own decomposition, and shown it not fit the pumping property. Perhaps there is another decomposition that will work?

And even in the case your example would work, I can claim that the pumping is larger than 6.
> 2 votes

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