title: Generating random words by grammar

text:
# Question
Title: Generating random words by grammar
## A bit of context

I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this question I presented "minimal working example" for simplicity. And of course, I am able to avoid the issue I faced using a bunch of trivial heuristics, but the question really makes me wonder.

## The problem

Suppose we have a typical context-free grammar for arithmetic expressions of $+,\*$, brackets, and integer literals:

$$E \longrightarrow F(“+”F)^\*$$ $$F \longrightarrow T(“\*”T)^\*$$ $$T \longrightarrow int|“(”E“)”$$

It is easy to implement a staighforward algorithm for generating random words by this grammar: we implement a separate procedure for each nonterminal. If a nonterminal has multiple production rules (as $T$ does), we choose a production rule by tossing a coin. If rule contains kleene star (e.g. $(“+”F)^\*$), we also toss a coin and generate zero or one repetition (sure we could pick any random integer $k\geq0$ and generate $k$ repetitions, but for simplicity we will focus on the simplest version of this procedure). Here is what we get:

```
generate_E():
    if coin_toss():
        return generate_F() + "+" + generate_F()
    else:
        return generate_F()

generate_F():
    if coin_toss():
        return generate_T() + "*" + generate_T()
    else:
        return generate_F()

def generate_T():
    if coin_toss():
        return "(" + generate_E() + ")"
    else:
        return random_integer()

```

An invocation of generate\_E() yields a random expression.

What could go wrong? It turns out that execution of this procedure on the real machine terminates with stack overflow quite often. Of course, technically here we have a possibility of endless recursion, but my intuition was telling me that probability of reaching recursion depth $k$ decays exponentially with increasing $k$, therefore getting deep levels (let's say, 1000) is almost impossible. Apparently, a few consecutive runs reveals that procedure can easily reach depth of many thousands (by depth I mean maximum number of procedure calls the stack contains simultaneously).

I am curios how to formalize this empirical fact. I want either a formula for $P(depth = k)$, or an asymptotic approximation of it, or an inequality bounding right tail of CDF below (something like $P(depth \> 1000) \> 0.05$)

## My attempt

I tried to come up with a formula for $P(depth = k)$:

Let's denote $P(depth = k)$ as $P\_E(k)$. Also, we define similar values for *generate\_F()* and *generate\_T()* \- $P\_F(k)$ and $P\_T(k)$ respectivetely.

Clearly (*else* branch of *generate\_T*), $$P\_T(1) = \frac{1}{2}$$ and for $k \> 1$ (*then* branch)$$P\_T(k) = \frac{1}{2}P\_E(k - 1)$$

Regarding $P\_F(k)$, we can either execute *else* branch, and it gives term $$\frac{1}{2}P\_T(k - 1)$$, or *then* branch, what gives a bit more complicated one $$\frac{1}{2}\sum\_{(x, y) | max(x, y) = k - 1}{P\_T(x)P\_T(y)}$$ i.e. $$P\_F(k)= \frac{1}{2}(P\_F(k - 1) + \sum\_{(x, y) | max(x, y) = k - 1}{P\_T(x)P\_T(y)})$$

Finally, the formula for $P\_E(k)$ is almost the same as for $P\_F(f)$, we only have to replace $P\_T(x)$ with $P\_F(x)$.

Now, we can calculate some values of $P\_e(k)$

\begin{array} {|r|r|}\hline k & P\_E(k) & P\_E(k)\text{ in decimal}& P\_E(k)\text{ by Monte-Carlo} \\ \hline 3 & \frac{33}{128} & \approx0.257812 & \approx0.2527 \\ \hline 6 & \frac{4448787585}{34359738368} & \approx0.129477 & \approx0.1282 \\ \hline 9 & \frac{14080391757747154038821618051813151497122305}{178405961588244985132285746181186892047843328} & \approx0.078923 & \approx0.0761 \\ \hline 12 & \text{ the fraction is too long} & \approx0.053213 & \approx0.0530 \\ \hline \end{array}

As we can see, the recurrent formulas seem to be true, but neither they give me an insight on asymptotical behaviour of $P\_E(k)$, nor the first values give a clue on formula in closed form.

Any help would be appreciated.

# Answer
> 11 votes
Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 \> 1$, it is not surprising that your process often failed to terminate.

To gain more information, we need to know the exact distribution of the number of $E$-offsprings, which is given by the following generating function (see the Wikipedia article linked to above): $$ h(z) = \frac{33}{128} + \frac{7}{16}z+ \frac{15}{64}z^2 + \frac{1}{16}z^3 + \frac{1}{128}z^4. $$ This implies that the extinction probability is $d \approx 0.717778143742483$ (by solving $h(z) = z$). This is an upper bound on the probability that your procedure terminates.

We can easily recover your numbers by considering iterates of $h$. The probability that the process terminates in $3k$ steps is $h^{(k)}(0)$. So computing $h(0),h(h(0))-h(0),h(h(h(0)))-h(h(0))$ and so on, we recover the figures in your table.

When $k$ is large, $h^{(k)}(0) \approx d$. We can compute $h'(d) \approx 0.882115879977412$. We have $$ \frac{d - h^{(k)}(0)}{d - h^{(k-1)}(0)} = \frac{h(d) - h(h^{(k-1)}(0))}{d - h^{(k-1)}(0)} \approx h'(d). $$ It follows that $$ d - h^{(k)}(0) \propto h'(d)^k. $$ Therefore the probability that the process terminates in exactly $3k$ steps is $$ h^{(k)}(0) - h^{(k-1)}(0) = \[d - h^{(k-1)}(0)\] - \[d - h^{(k)}(0)\] \propto h'(d)^{k-1} - h'(d)^k \propto h'(d)^k. $$ Empirically, we can check that the constant of proportionality is roughly $0.0248011196615094$.

# Answer
> 7 votes
As Yuval has noted, this way of randomly generating recursive data structures is known to (usually) end up with an infinite expected size.

There is, however, a solution to the problem, that allows one to weigh the recursive choices in such a way that expected size lies within a certain finite interval: Boltzmann samplers. They are based on the combinatorial generating function of the structure and come from combinatorial species theory. For practical implementations, you don't need the theoretical parts, though. A good programmatic introduction in Haskell can be found in Brent Yorgey's blog. If you can read (or decipher) Haskell, porting the approach to your own data structure isn't too difficult.

As an example for how a derivation like yours looks within that framework, read Counting and generating terms in the binary lambda calculus by Grygiel & Lescanne (spoiler: it's a surprising amount of complex analysis).

---
Tags: algorithm-analysis, formal-grammars, probability-theory, randomized-algorithms
---


# Question
Title: Generating regular expressions not containing abc
Let sigma = {a,b,c}. How do I generate a language L that does not containg abc? Any guidance is appreciated!

# Answer
Design a DFA that recognizes "abc" (make sure to include all transitions). Complement it (make accepting states non-accepting, and make non-accepting states accepting) in order to get a DFA for $L = \Sigma^\* \setminus \\{ abc \\}$. Finally, write down the regular expression of the complemented DFA.

---

As a brute force solution that does not use DFAs: write a regular expression for all words of lengths 0, 1, 2, and more than 3. This should be easy. Then write, a regular expression for all words of length 3 except abc. For example: $(b+c)(a+b+c)^2 + ab(a+b) + a(a+c)(a+b+c)$

Take the union of all the above REs.
> 1 votes

# Answer
The language of all words not containing $abc$ as a subword can be handled by focussing on the letter $b$. Whenever it occurs in the string we should check that one of the following conditions hold:

* it is the first letter of the string
* it is directly after another $b$ or after a $c$, or symmetrically
* it is directly before ...
* it is the last letter of the string

If that is true, I think it can be handled efficiently with a regular expression.

Be safe, all!
> 1 votes

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


title: When is a problem strongly NP-complete

text:
# Question
Title: When is a problem strongly NP-complete
Let the problem of the diophantic equation 0/1 be as follows.

Input : A polynomial equation on n variables whose coefficients are integers (ex : $2x^3\_1 x\_2 + x\_1x^3\_3 - 3x\_4 = 8$)

Question: Does this equation have a solution in space {0,1}$^n$ ? (can we satisfy the equation by choosing for each variable the value 0 or 1?)

1 - How to prove that this diophantine equation 0/1 is NP-complete?

2 - How to prove that this diophantine equation 0/1 is Strongly NP-complete (ie its restriction to the case where all the coefficients are bounded by a polynomial of the number of variables is already NP-complete)

# Answer
> 0 votes
This problem is strongly NP-complete; it is straightforward to reduce 3SAT to this problem.

The clause $C = (x\_1 \lor \neg x\_2 \lor x\_3)$ can be encoded as the polynomial $p(x\_1,x\_2,x\_3,\dots) = \[(1-x\_1)x\_2(1-x\_3)\]^2$. The conjunction of clauses $\varphi = C\_1 \land \dots \land C\_m$ can be encoded as $q(x\_1,\dots,x\_n) = p\_1(x\_1,\dots,x\_n) \cdots p\_m(x\_1,\dots,x\_n)$, where $p\_i(x\_1,\dots,x\_n)$ is the encoding of clause $C\_i$. Then, the polynomial $q(x\_1,\dots,x\_n)$ has a solution in $\\{0,1\\}^n$ if and only if the original formula $\varphi$ is satisfiable.

---
Tags: np-complete
---


# Question
Title: Help with finding a flaw in argument simulating large Turing machines with smaller ones
I have an argument which, if it goes through, just about proves that either:

* Programming languages are more powerful than Turing machines
* The busy beaver function ($BB()$) on Turing machines is computable

Now, I understand that it's vastly more likely that my argument has some flaw that I can't find. But it's more interesting to me *how* I'm wrong, rather than *whether* I'm wrong.

# Argument

Construct a Turing machine $M\_1$ as which takes as arguments (on the tape) $n, k$, simulates all Turing machines with $n$ states until $k$ of them halt, and then halts itself. This is easy to write in a programming language, as demonstrated by the following Python snippet:

```
def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1

```

Now, let $m\_1$ be the number of states required by $M\_1$. Fix $n$ much greater than $m\_1$. Let $k\_1$ be the largest number such that $M\_1(n, k\_1)$ halts and $k\_0$ be the smallest number such that when $M\_1(n, k\_0)$ halts, $k\_1$ simulated Turing machines have halted (as all equivalent machines will halt on the same step). Choose $k$ with $k\_0\leq k\leq k\_1$. This means that $M\_1(n,k)$ halts in about $BB(n)$ steps.

Construct $M\_2$ which is the same as $M\_1$ except the first thing it does is write $n$ and $k$ to the tape. Let $m\_2$ be the number of states required by $M\_2$. Then $m\_1+K(n)+K(k)+C=m\_2$ for some small $C$ (which is probably constant and likely $0$), with $K(n)$ being the Kolmogorov complexity of $n$ in Turing machine states.

Now, $K(n)$ is at most $O(\log(n))$. There are about $n^n$ machines with $n$ states, so $k$ is about $n^n$, and thus $K(k)$ is at most $O(\log(n^n))=O(n \cdot \log(n))$. That means that $m\_2\>n$. But here we have a problem: if $k$ is easier to write to the tape (so that $K(k)\<n-\log(n)$), then $m\_2$ would be slightly smaller than $n$. That would mean $BB(m\_2)\>BB(n)$ and $m\_2\<n$, a clear contradiction.

In my mind, these are the possible resolutions:

* $M\_1$ is impossible to create as a Turing machine, meaning that Python is more powerful than Turing machines are.
* There is some transfinite extension to Turing machines which is not much more powerful than Turing machines in general, and $M\_1$ can be written in this extension. In other words, $M\_1$ is the limit of a set of machines $M\_{1,N}$, each of which can handle any $n\<N$. This would probably entail the busy beaver function being computable.
* There is a large set of numbers which cannot be written by a Turing machine in much fewer than $\log(k)=n$ states (we need $K(k)\<n-\log(n)$). It seems impossible to me that no candidate for $(n, k)$ could be sufficiently compressed.

Where is the error in this logic?

---

I had previously said that $K(k)\leq O(n)$, but @6005 pointed out that was suspect. With that fixed (to $O(n \cdot \log(n))$), it still seems very surprising to me that we can't achieve a reduction from $K(k)\approx n \cdot \log(n)$ to $K(k)\<n-\log(n)$ for any potential value of $(n,k)$, but no longer inconceivable.

# Answer
Your flaw seems to be here:

> Now, $K(n)$ is at most $O(\log(n))$. $k$ is about $n^n$, so $K(k)$ is at most $O(n)$. That puts $m\_2$ just slightly larger than $n$.

It's true that $k$ is about $n^n$ (more precisely, $k = n^{\Theta(n)}$ or $k = 2^{\Theta(n \log n)}$, and this can be shown by upper bounding $k$ by the number of Turing machines, and lower bounding by finding a family of simple halting Turing machines). However, that doesn't imply that $K(k)$ is at most $O(n)$. Rather, we only know that $K(k)$ is at most $$ O(\log(n^n)) = O(n \log n). $$

Your contradiction relies on picking $k$ so that $K(k)$ is $o(n)$ (a bit smaller than $n$). Your reasoning shows that this is impossible.

But this is not too surprising: most $k$ we expect to be about $O(n \log n)$, and $k$ is a number that holds a lot of information about Turing machines with $n$ states, so we don't expect to be able to compress such a number to smaller than $O(n)$ states itself.

---

**P.S.** Putting aside the question of whether Python is really equivalent to Turing machines (probably no one knows, as it hasn't been formally shown), your program `M1` is in fact clearly expressible as a Turing machine. From this, you should be able to see that the resolutions based on `M1` not being expressible as a Turing machine are not correct.
> 3 votes

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


# Question
Title: Longest path in an undirected tree with only one traversal
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:

* Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
* Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.

The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?

(This can be equivalently described as the problem of computing the diameter of an undirected tree.)

# Answer
> 25 votes
We perform a depth-first search in post order and aggregate results on the way, that is we solve the problem recursively.

For every node $v$ with children $u\_1,\dots,u\_k$ (in the search tree) there are two cases:

* The longest path in $T\_v$ lies in one of the subtrees $T\_{u\_1},\dots,T\_{u\_k}$.
* The longest path in $T\_v$ contains $v$.

In the second case, we have to combine the one or two longest paths from $v$ into one of the subtrees; these are certainly those to the deepest leaves. The length of the path is then $H\_{(k)} + H\_{(k-1)} + 2$ if $k\>1$, or $H\_{(k)}+1$ if $k=1$, with $H = \\{ h(T\_{u\_i}) \mid i=1,\dots,k\\}$ the multi set of subtree heights¹.

In pseudo code, the algorithm looks like this:

```
procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

```

---

1. $A\_{(k)}$ is the $k$-smallest value in $A$ (order statistic).

# Answer
> 11 votes
This can be solved in a better way. Also, we can reduce the time complexity to O(n) with a slight modification in the data structure and using an iterative approach. For a detailed analysis and multiple ways of solving this problem with various data structures.

Here's a summary of what I want to explain in a blog post of mine:

**Recursive Approach – Tree Diameter** Another way of approaching this problem is as follows. As we mentioned above that the diameter can

1. completely lie in the left sub tree or
2. completely lie in the right sub tree or
3. may span across the root

Which means that the diameter can be ideally derived by

1. the diameter of left tree or
2. the diameter of right tree or
3. the height of left sub tree + the height of right sub tree + 1 ( 1 to add the root node when the diameter spans across the root node)

And we know that the diameter is the lengthiest path, so we take the maximum of 1 and 2 in case it lies in either of the side or wee take 3 if it spans through the root.

**Iterative Approach – Tree Diameter**

We have a tree, we need a meta information with each of the node so that each node knows following:

1. The height of its left child,
2. The height of its right child and
3. The farthest distance between its leaf nodes.

Once each node has this information, we need a temporary variable to keep track of the maximum path. By the time the algorithm finishes, we have the value of diameter in the temp variable.

Now, we need to solve this problem in a bottom up approach, because we have no idea about the three values for the root. But we know these values for the leaves.

**Steps to solve**

1. Initialize all the leaves with leftHeight and rightHeight as 1.
2. Initialize all the leaves with maxDistance as 0, we make it a point that if either of the leftHeight or rightHeight is 1 we make the maxDistance = 0
3. Move upward one at a time and calculate the values for the immediate parent. It would be easy because now we know these values for the children.
4. At a given node,

* assign leftHeight as maximum of (leftHeight or rightHeight of its left child).
    * assign the rightHeight as maximum of (leftHeight or rightHeight of its right child).
    * if any of these values (leftHeight or rightHeight) is 1 make the maxDistance as zero.
    * if both the values are greater than zero make the maxDistance as leftHeight + rightHeight – 1
5. Maintain the maxDistance in a temp variable and if in step 4 the maxDistance is more than the current value of the variable, replace it with the new maxDistance value.
6. At the end of the algorithm the value in maxDistance is the diameter.

# Answer
> 0 votes
Iteratively remove the leaves. That is

N = number of nodes
while N\>2
identify the leaves
remove the leaves
subtract the number of leaves removed from N
if N is 1
the one node in the tree is the centre
else
the two nodes in the tree are the bicentres

I have in mind to generate all the different trees by iterative expansion of trees and testing for isomorphism. Who has done this before. Let me know to keith.paton@skynet.be

# Answer
> -2 votes
Below is code that returns a diameter path using only a single DFS traversal. It requires extra space to keep track of the best diameter seen so far as well as the longest path beginning at a particular node in the tree. This is a dynamic programming approach based on the fact that a longest diameter path either doesn't include root, or is combination of the two longest paths of root's neighbours. Thus we need two vectors to keep track of this information.

```
 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }

    return max(m1 + m2 + 2, max_diam);
}

```

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


# Question
Title: EVEN-CFL Decidable / Undecidable - Rice-Theorem
Let EVEN-CFL $=\left\\{w | M\_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M\_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\\}$

Question : Is EVEN-CFL decidable?

Am trying to learn this type of proofs

Now the Rice-Theorem states, that semantic properties that are non-trivial are undecidable.

For this, EVEN-CFL is not a syntactic property of a TM, it's a property of the language and it's non-trivial because there exists languages that are context free and others that are not, like recursive languages or they have the length or not.

Is this right so far? How do I proceed now is this it? The use of the RICE-THEOREM

Thanks

# Answer
The property of being EVEN-CFL of c.e. languages is not trivial, by Rice's theorem this is not decidable.
> 1 votes

---
Tags: formal-languages, turing-machines, undecidability, rice-theorem
---


# Question
Title: Algorithm to find what points are the nearest to other points
I have two lists:

* Location list, it contains point of interest
* People list, it contains coordinates of every person. One single person could be in the list multiple times, depending from the log time. Someone who is out for a walk will result in two different locations in two different hours.

I would find out what people where near every point of interest.

I could approach the problem with brute force: external loop check for every point of interest the entire people list finding out who was there.

I would obviously avoid brute force. I thought about Nearest Neighbour, for sure multiple people will be in the same spot so I could look for a point of interest in the cluster.

Solutions?

# Answer
> 1 votes
Use a data structure designed for nearest neighbor search.

---
Tags: algorithms, nearest-neighbour
---


# Question
Title: Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm
I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to reach the last element of the array in the minimum number of steps. At each step, I can move to any element with the same value, move forward one, or move backward one. The greedy criterion is to move furthest to the right as much as possible. For example, if we have array {1,2,3,4,1,5}, the algorithm will start at 1 move to 1 before the 5 then moves to 5 with number of steps of 2.

An an example of input instance that proves the given greedy algorithm wrong might be {1,2,1,3,2} where the given algorithm crosses the array in 3 steps whereas there is an optimal solution of moving from 1 to the second 2 right to last 2 in two steps. Now, what is a correct algorithm for solving this problem ?

# Answer
> 1 votes
The fact that you have **several** potential ways you can move in this problem should be an indicator of how to come up with a counterexample such that using the "greedy" strategy of simply going as far right as possible doesn't yield an optimal solution.

Consider the array, $A = \\{1, 2, 1, 3, 2\\}$

By the greedy strategy you would end up making the moves in this series:

$1 \xrightarrow{} 1 \xrightarrow{} 3 \xrightarrow{} 2$ $(3$ total moves$)$

However, the optimal strategy would be to make the moves:

$1 \xrightarrow{} 2 \xrightarrow{} 2$ $(2$ total moves$)$

**Edit:** I guess the question was edited as I was answering the question/after I answered it and we ended up with the same example..? Anyway here's another below:

Consider another counterexample (where backtracking produces a better solution):

$A = \\{2, 1, 4, 6, 1, 5, 0, 10, 9, 8, 6\\}$

The greedy strategy would yield the path: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xrightarrow{} 5 \xrightarrow{} 0 \xrightarrow{} 10 \xrightarrow{} 9 \xrightarrow{} 8 \xrightarrow{} 6$
$(8$ total moves$)$

Whereas the series of moves: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xleftarrow{} 6 \xrightarrow{} 6$ $(4$ total moves$)$

There's another series of moves resulting in a length $4$ path as well.

Since making the "locally optimal" decision for this problem at each step doesn't yield the optimal solution for the overall problem, this looks like a problem that could be solved using dynamic programming.

Look at it in a top-down fashion. What is the **last** move we'd want to make to get to the final element of the array, i.e., $a\_n$. Recurse on that subproblem. Find a way to develop a solution using memoization (to avoid solving the same subproblem multiple times) or solve it iteratively, in a bottom-up manner. DP can be a bit difficult.

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Why do we need value-returning functions?
I'm just a beginner at C++ programming. I am currently having hard time grasping the usage of value returning function and non-value returning function. Void functions are called non-value returning function but they can return value if we assign certain parameters, compute the parameters and call them in the main function. So, doesn't this defeat the purpose? I feel like I am getting this wrong, so some explanation here would be great!

Also, I see that void functions are easier to use, since I don't need to use " cout\<\< 'the void function' \<\< endl; " It seems easier and the value-returning function seems useless. I need explanation here as well as to why we need value-returning function.

Please bear with my questions and I am always ready to learn!

# Answer
> 4 votes
"Need" as such, no. There you are right, all the work can be done using `void` functions, by passing pointers to variables to modify instead, or changing global variables. In fact, everything is compiled down to assembly language, and no such language I know of has "functions" that return values.

On the other hand, we are accustomed (by mathematics, and by lots of it's applications in everyday life) to think in terms of functions that are applied to arguments and return a value. Think of `sin x`, square root, and a long list of others, like lowly `strlen()` in C. It is a nice simplification to be able to say:

```
y = abs(x) - 42 * sqrt(b);

```

instead of something like:

```
pabs(x, &xa);
psrqrt(b, &ba);
y = xa - 42 * ba;

```

Come to think about it, multiplication and subtractions are functions returning values too (`X& operator*(const X&, const X&)` and `X& operator-(const X&, const X&)` in C++), and the handling of results and intermediate values soon gets unmanageable. One of the points of a programming language is to handle such bureaucratic details for you, transparently.

# Answer
> 1 votes
Consider that Prolog gets by without functions most of the time. (It does have functions, but they are mostly used for mathematical notation like `sin(X)`.)

Rather than return a value, like `f(X1,X2)`, you define a predicate `p(X1,X2,Y)` which is true if `Y` would be the return value from that function.

In Haskell, which is a functional language, you would typically sum a list with a function. Here, `sum_list xs` returns the sum of the elements of the list `xs`:

```
sum_list [] = 0
sum_list (x : xs) = x + sum xs

```

(In Haskell, you use the notation `x : xs` to denote a list with `x` as the first, or head, element and `xs` as everything but the first element, also know as its "tail".)

In Prolog, which is a logic language, you would typically define a predicate `sum_list(Xs,S)` which is true if and only if `S` is the sum of the elements of the list `Xs`.

```
sum_list([], 0).
sum_list([X | Xs], S) :- sum_list(Xs, S1), S is X + S1.

```

(In Prolog, `[X | Xs]` means a list with `X` as its head and `Xs` as its tail. Variables in Prolog start with an upper-case letter. Also note that the `+` operator is behaving like a function.)

A function is just a special kind of predicate, so you don't need functions to program if you have predicates. But it is very convenient notation for many circumstances.

# Answer
> 1 votes
What you describe is possible, but is considered bad programming practice for some good reasons. It does not scale to large, complex programs because it lets bugs slip easily. Using too many global variables makes it hard to control your program's behavior, because you need to be able to track which components of your program are interacting with which variables and in what order.

So, if you want to analyze a specific function somewhere in the depths of your code, and if that function uses a variable that has been declared outside the function, then you also need to know which other functions have interacted (and in what way) with that variable.

Let's call a function pure if it does not interact with its environment, i.e. *it does not use variables declared outside its body*, it does not use user input, it does not print output, and in general it does not do many things, but it only computes some value. Pure functions give you the safety that their result depends purely on their input. No matter in what environment you run a pure function, it will always give you the same result for the same arguments. So, with pure functions you can be sure that to analyze/understand them, you do *not* need to look outside their body. Pure functions correspond really well to the mathematical notion of a function, by the way.

A good programming practice is to separate the pure parts of your program from the parts that need to interact with some environment. Then use pure functions for the pure part and make organized code for the impure. In general, this gives you better control over your program and fewer bugs. Some languages take advantage of the distinction between pure and impure computations to allow for code optimizations and better performance.

---
Tags: c++
---


title: Sum of sequence complexity

text:
# Question
Title: Sum of sequence complexity
I try to find out what is the time complexity of this program:

```
for (int i =0; i < n; i++)
{
    for (int j = i+1; j < n; j++)
    {
         //Do something O(1)
    }
}

```

I tried to find any explanation, As I see, it something like Arithmetic progression sum `(n(n-1)/2)`.

Is it? or it's just `O(n^2)`

# Answer
The inner loop will iterate once with $j=i+1$, once again with $j=i+2$, and so on, up to the last iteration with $j=n-1$, so there will be, for each $i$ in the outer loop, $(i+1)-(n-1)-1=n+i-1$ time contributions from the inner loop. Add these to get your answer.
> 1 votes

---
Tags: time-complexity
---


title: Existence of graph spanners

text:
# Question
Title: Existence of graph spanners
An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. The goal is to find a small set $S$ that satisfies this constraint.

Recently, I've looked at some algorithms for this problem such as A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Interestingly, all of them seem to compute a $(2k-1)$-spanner that have at most $O(k n^{1+1/k})$ edges, for integers $k\ge 1$.

This made me wonder about the following:

> Is it impossible to construct a $k$-spanner for **even** $k$, e.g., $k=2,4$, in general graphs?

# Answer
> 4 votes
Strictly speaking it is possible to construct $2k$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $2k-1$ spanner.

Indeed, assuming Erdős Girth Conjecture, there are graphs $G=(V,E)$ with girth (length of the shortest cycle) $2k+2$ and $\Omega(n^{1+\frac{1}{k}})$ edges.

A $2k$ spanner $S$ of $G$ cannot exclude any edge $(u,v) \in E$. Indeed, if $(u,v) \in E \setminus S$, either $u$ and $v$ are disconnected in $(V, S)$, or their distance in $(V, S)$ is at least $2k+1$. This is a contradiction.

This means that any $2k$ spanner of $G$ must have at least $\Omega(n^{1+\frac{1}{k}})$ edges. However, $O(n^{1+\frac{1}{k}})$ edges are already enough to guarantee the existence of $2k-1$ spanners in any graph, as you point out.

---
Tags: graphs, combinatorics
---


# Question
Title: Definition of 2-CNF (a.k.a Krom) formula
In my lecturer's notes, the following definition for a 2-CNF wff is given:

> A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has at most two literals.

However, there is no mention in the notes of how one might represent clauses containing a single literal L in the wff's corresponding implication graph (although I suppose one could add an edge from every other literal to L). Looking at Krom's original paper, the definition he seems to use is:

> A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has exactly two literals.

This definition would seem to make a lot more sense. Which definition is correct? Am I missing something?

# Answer
A unit clause of the form $p$ is the same as the clause $p \lor p$, and so corresponds to the arrow $\lnot p \to p$.

As an example, consider the unsatisfiable CNF $$ p \land (\lnot p \lor q) \land \lnot q. $$ The implication graph contains the following edges: $$ \lnot p \to p \\ p \to q, \lnot q \to \lnot p \\ q \to \lnot q $$ These can be arranged in a cycle: $$ \lnot p \to p \to q \to \lnot q \to \lnot p $$ This cycle contains both $p$ and $\lnot p$ (and also both $q$ and $\lnot q$), showing that the formula is unsatisfiable.
> 3 votes

---
Tags: graphs, logic, satisfiability, propositional-logic
---


# Question
Title: Perfect Matching in Bipartite Graph with mutually exclusive edges
**Problem**

I would to solve *Perfect Matching in Bipartite Graph Problem* **where some edges are mutually exclusive**.

**Example**

Left vertices: $a,b,c$

Right vertices: $x,y,z$

Edges: $(a,x),(a,y),(b,z),(c,y)$

Exlusive pairs: $(b,z)$ and $(c,y)$

Answer: *no perfect matching*

**Question**

Is the problem in *P* or *NP*?

**Solution Attempts**

I know that *Perfect Matching in Bipartite Graph Problem* is in *P*. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is *NP*, but without any luck.

# Answer
> 1 votes
It is $NP$ as $SAT$ can be polynomially reduced to this problem.

Let clauses be the left part vertexes, and literals be the right part vertexes. Draw an edge $(x,y)$ iff clause $x$ contains literal $y$. Finally, a pair of edges $(x\_1, y\_1)$ and $(x\_2, y\_2)$ will be exclusive iff $y\_1$ corresponds to literal $a$ and $y\_2$ corresponds to literal $\overline{a}$.

---
Tags: graphs, time-complexity, bipartite-matching
---


title: Are these REs equivalent?

text:
# Question
Title: Are these REs equivalent?
I have to implement a compiler for a given language as part of an assignment. The language is kept simple enough such that it can be fully expressed through REs.

My question lies with two of the REs provided:

> DIGIT := \[0-9\]?
>
> INTEGER\_LITERAL := DIGIT DIGIT\*

When I saw the RE for `INTEGER_LITERAL` I sort of thought to myself:

> "Well that's just DIGIT+"

Am I right to think so?

# Answer
Any regular expression satisfies $r^+ = rr^\* = r^\*r$. In fact, one often *defines* $r^+$ using one of these formulas, usually $r^+ := rr^\*$.
> 2 votes

---
Tags: regular-languages, regular-expressions, compilers
---


# Question
Title: Prove the following language is regular?
> Assume $L\_1$ is a regular language, and define:
>
> $$L = \\{wcv ∈ \\{a, b, c\\}^\* \mid |w|\_a + 2|v|\_b ≡ 3 \bmod 5, w, v ∈ L\_1\\}.$$
>
> Show that $L$ is regular.

I first tried to prove by showing that the pumping lemma holds true, then learned that it was not a double implication and can only be used to prove languages are not regular.

Then I tried to draw an NFA, but didn't make any progress.

What's a good way to prove that a language like this is regular?

# Answer
The answer depends on whether $L\_1$ is a language over $\\{a,b\\}$ or over $\\{a,b,c\\}$.

**$L\_1$ is a language over $\\{a,b\\}$**

In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular: $$ L\_2 = \\{wcv \mid |w|\_a+2|v|\_b \equiv 3 \bmod 5 , w,v \in \\{a,b\\}^\*\\}. $$ Your language is $L = L\_1cL\_1 \cap L\_2$.

**$L\_1$ is a language over $\\{a,b,c\\}$**

In this case we have to be more careful. Given a DFA (or an NFA) for $L\_1$, we construct one for $L$ which in three stages:

1. Simulate $L\_1$ and keep track of the number of $a$s modulo 5. Whenever at an accepting state of $L\_1$, add a nondeterministic move to stage 2.
2. Read $c$.
3. Simulate $L\_1$ (starting from its initial state again) and keep track of the number of $b$s modulo 5. A state is accepting if it is accepting for $L\_1$ and the constraint $|w|\_a+2|v|\_b$ is satisfied, where $w$ is the word read at the first stage, and $v$ is the word read at the third stage.

I'll let you fill in the details.
> 3 votes

# Answer
For every $i=0,\dots,4$, there exists a regular expression $W\_i$ for the language of all words $w$ such that $|w|\_a \bmod 5 = i$.

For example: $$ ((b+c)^\*a)^i ( ((b+c)^\*a)^5)^\*(b+c)^\* $$

Similarly, for every $j=0,\dots,4$, there exists a regular expression $Z\_j$ for the language of all words $z$ such that $2|z|\_b \bmod 5 = j$.

Then a regular expression for your language is $\sum\_{i=0}^4 W\_i c Z\_{(3-i) \bmod 5}$
> 1 votes

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


title: Select minimal rate of growth

text:
# Question
Title: Select minimal rate of growth
Suppose we have algorithm that is $\Theta(n(t+n^{1/t}))$, where $t\>0$ is some parameter. How to select $t$ such that the running time has a minimum rate of growth?

Source: *Combinatorial Optimization* by Korte and Vygen (I am going through this book by myself but sadly there are no available solutions anywhere online, it seems).

I am not very proficient with math, but my assumption is that I need to look for $t$ s.t. the second derivative of $n(t+n^{1/t})$ would be 0 (since we are looking for minimal RATE of growth, not for the minimal value of the function itself, so $n^{1+1/t}ln^2(n) = 0$.

Is that a correct approach, or I completely misunderstood the question/concept of the rate of growth?

# Answer
> 3 votes
Here is the original exercise.

> Suppose we have an algorithm whose running time is $\Theta(n(t + n^{1/t} ))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen (depending on $n$) such that the running time (as a function of $n$) has a minimum rate of growth?

As others have pointed out, you misunderstood the exercise. The phrase "rate of growth" is indeed somewhat misleading.

The rate of growth of the running time of an algorithm refers to the growing behavior of the running time when the input length goes bigger and bigger. It is almost universal trend that the running time of an algorithm becomes longer when the input length becomes bigger. In particular, it is true asymptotically for the current case if we assume $t$ is a constant.

In order for the running time to have a minimum rate of growth everywhere or in average, we need the running time be the minimum when the input length is sufficiently large, since the running time for input length $n$ is the sum of all differences between the running time for input length $i-1$ and $i$, where $i$ ranges through $n\_0$, $n\_0+1$, $\cdots$, $n$ for some small constant $n\_0$ and the running time for input length $n\_0$. So, the requirement "the running time (as a function of $n$) has a minimum rate of growth" in general is just "the running time (as a function of $n$) is the minimum", as we ignore the contribution of the usually rather short running time for the small input length $n\_0$. The exercise would have been clearer had it said "... such that the running time is the minimum as a function of $n$".

"How to select $t$ such that the running time has a minimum rate of growth?" The definition of $\Theta$ tells us that the running time is proportional to $n(t+n^{\frac 1t})$ within a constant factor. This question requests you to select $t$ as a function of $n$ such that, $n(t+n^{\frac 1t})$ as a function of $n$ is as small as possible. Or, once we have pulled out the factor $n$, such that, $(t+n^{\frac 1t})$ as a function of $n$ is as small as possible

---

Now that we have understood the exercise, the real task is how to answer that question.

Note that $t$ increases as $t$ increases. On the other hand, $n^{1/t}$ decreases as $t$ increases, assuming $n\>1$.

If we let $t=1$, then $t+n^{\frac 1t} = 1 + n$. If $t=n$, then $t+n^{\frac 1t}=n+n^{\frac 1n}= n+o(1)$. In either case, either $t$ or $n^{\frac 1t}$ is rather substantial. If we select $t$ to be some value between $1$ and $n$, we could possibly make both $t$ and $n^{\frac 1t}$ much less substantial, thus making their sum much smaller. The relevation is that we could choose $t$ such that $t=n^{\frac 1t}$ so that none of the two is particularly large.

Suppose $t\_0$ as a function of $n$ satisfies $t\_0=n^{\frac1{t\_0}}$. Then we have $$t\_0\le\min\_{t\>0}t+n^{\frac 1t}\le 2t\_0$$

It is an easy exercise for the interested readers to prove the above formula.

The above formula indicates that we can use binary search to find or approximate the wanted value of $t$. Fixing $n$, we will start with interval $\[1,n\]$. Check the middle value $t =(1+n)/2$. If $t\<n^{\frac1{t}}$, replace the left endpoint 1 with $(1+n)/2$ so that we will continue with interval $\[(1+n)/2,n\]$. Otherwise, replace the right endpoint n with $(1+n)/2$ so that we will continue with interval $\[1, (1+n)/2\]$. Repeating this binary search until the interval becomes small enough. We will use either of its endpoints as the wanted value of $t$.

---

The above gives a simple algorithmic way to chose $t$ to make $t+n^{\frac1n}$ reach the minimum within a factor of 2. We can do better following the steps given by D.W.

> You want to find $t$ that minimizes $f(t)=t+n^{1/t}$. This can be done by setting the first derivative to zero. In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $$(\log n)/t + \log \log n = 2 \log t.$$

Now the problem is how to solve the above equation for $t$. Note the left-hand side is a decreasing function in $t$ and the right-hand side is an increasing function in $t$. If $t=1$, the left-hand side is greater than the right-hand side. If $t=n$, the right-hand side is greater than the left-hand side. So there is a unique solution for $t$, which is between 1 and $n$. We can use binary search to find that solution.

---

A couple of related results are listed here just for fun.

**The selected $t$ is equal to $\frac{\log n}{\log\log n}$ asymptotically.**.

**The minimum running time is $\Theta(\frac{n\log n}{\log\log n}).$**

# Answer
> 2 votes
You want to find $t$ that minimizes $f(t)=t+n^{1/t}$. This can be done by setting the first derivative to zero. In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $(\log n)/t + \log \log n = 2 \log t$. Solving that analytically for $t$ looks tedious but perhaps you can obtain an approximation.

---
Tags: asymptotics
---


# Question
Title: generate all unlabelled trees up to size n
Who has published an answer to these problems?

An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define such a signature.

Many thanks Keith Paton Independent researcher

# Answer
> 1 votes
If you just want to *define* such a function, then you can just consider the equivalence relation $\rho$ where $T\_1 \rho T\_2$ iff $T\_1$ and $T\_2$ are isomorphic. Partition the set of all trees w.r.t. $\rho$. Let $C(T)$ be the equivalence class in which $T$ belongs and select one representative $T^C$ for each equivalence class $C$. Define $s(T) = T^{C(T)}$.

If you want a signature that can be easily/quickly computed, you can define one recursively. For simplicity I am going to define it over binary strings, but you can interpret this string as an integer. I am also going to assume that you are interested in rooted trees (see below if this is not the case). If $T$ is a singleton let $s(T)=\epsilon$, where $\epsilon$ is the empty string. Otherwise let $r$ be the root of $T$ and $u\_1, u\_2, \dots, u\_\ell$ be the children of $u$ sorted in nondecreasing order of $s(u\_i$). Define: $s(T) = \bigcirc\_{i=1}^\ell (1 \circ s(u\_i) \circ 0)$, where $\circ$ denotes concatenation.

Algorithmically, this amounts to starting with $s(T)=\epsilon$ and performing a DFS visit of $T$: every time that an edge $e$ is traversed append a $0$ (resp. $1$) to $s(T)$ iff $e$ is traversed away (resp. towards) the root. The order in which the children $u\_1, \dots, u\_\ell$ of a vertex are visited is determined by the values of $s(u\_i)$ themselves.

If you are interested in unrooted trees, then you can use the same approach by first rooting $T$ in one of its centers. If $T$ has only one center, then $s(T)$ is unique. If $T$ has two centers, you can select the one that results in the smallest value of $s(T)$ (w.r.t. the lexicographical order).

This has been used, e.g., here in Section 3.1.

---
Tags: graphs
---


# Question
Title: Iterative Depth First Search for cycle detection on directed graphs
I found this pseudocode on Wikipedia, and looks very elegant and intuitive:

```
L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

```

I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.

How should I approach this?

# Answer
> 2 votes
Using the same logic as the recursive algorithm, I added on the stack a `pos` value which keeps track of the position of the last descendant currently processing.

This was necessary for the "backtrack" steps of the algorithm.

```
from typing import List

UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1

def is_acyclic(graph: List[list], vertex_count: int) -> bool:
    state = [UNDISCOVERED] * vertex_count
    for vertex in range(vertex_count):
        if not dfs(graph, vertex, state):
            return False

    return True

def dfs(graph: List[list], v: int, state: list) -> bool:
    stack = [(v, 0)]
    while stack:
        curr, pos = stack[-1]
        if state[curr] == PROCESSED:
            stack.pop()
            continue
        if state[curr] == DISCOVERED and pos == 0:
            return False
        if pos == 0:
            state[curr] = DISCOVERED

        for i in range(pos, len(graph[curr])):
            stack[-1] = curr, pos + 1
            descendant = graph[curr][i]
            stack.append((descendant, 0))
            break
        else:
            state[curr] = PROCESSED

    return True

```

# Answer
> 2 votes
You could add "colors" to the nodes similar to the method done for recursive DFS found in CLRS, for example. When you instantiate each node (assuming they are objects) put a **color** field such that every node initially has `node.color` $\xleftarrow{}$ **white**.

The following is your pseudocode ***modified*** that I believe would help:

```
    L ← Empty list of all nodes, where node.color ← black (once placed here)
    while exists nodes such that node.color is white do
    select a node n such that n.color is white
    visit(n)

function visit(node n)
    if n.color is black then:
        return
    if n.color is gray then:
        stop   (back edge is found indicates cycle exists)

    mark n.color as gray

    for each node m with an edge from n to m do
        visit(m)

    mark n.color as black
    add n to head of L

```

The idea is that all "unvisited" nodes begin colored "white". Then, when we encounter a node, we visit it and color it "grey" while exploring it. When we are done exploring this node, we color it "black". We only call DFS on nodes with "white" color.

Also regarding implementation, in addition to the stack, you could make `L` a set and just do a check on the size (since you know only distinct nodes will get added to this set) and once the size is equal to the number of nodes you know you've visited all the nodes of the graph, but as is if you use the coloring eventually it'll be the case that there is no node, `n` such that `n.color == white`.

---
Tags: algorithms, graphs, graph-traversal, dag, depth-first-search
---


# Question
Title: Is it possible to find a supersequence of a single array?
In Jeff Erickson's *Algorithms* textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary array A of integers".

A supersequence contains all of the elements from the original array X\[1...n\], and oscillating is defined as X \[i\] \< X \[i + 1\] for all even i, and X \[i\] \> X \[i + 1\] for all odd i.

However, I am not asking about the answer to this problem. I am just wondering if this question even is sound. How can you find a supersequence of a single array? Wouldn't the answer just be the length of the original array if all elements are oscillating? Else, 0. Usually, a supersequence is found between multiple arrays.

# Answer
> 1 votes
What about the array $\[1, 3, 5\]$? The supersequence $\[0,1,0,3,0,5\]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.

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


# Question
Title: How does the hardware of a while loop work?
I know get how logical operators for if logic gates work, but I am trying to understand how while loops fit into that picture. I realize that this question is a bit vague. It all started because I was wondering if one could write a while-loop with a series of if statements. Then I realized there had to be something deeper in our programming languages.

# Answer
Vladislav is right, but there is more that can be said.

A loop means running some code, and then running it again. An `if` just conditionally branches to two different bits of code. If one of those bits of code can jump back to the earlier code, or to the `if` itself, then you can get a loop. So you need something that can jump somewhere else. A `goto` is one command that does that in some languages. You have to have a way to naming or identifying where the jump is to, though, even if it's just by a line number.

Another way to implement a loop is with recursion. To do that, you need to be able to name procedures or functions or targets, and then embed the call to the named code in one of the branches of the `if`. (In tail-recursive languages such as Common Lisp and Scheme, this can be as efficient as a loop in some circumstances.)

In both cases, it's crucial that there be a way of referencing earlier code, and jumping into it. If you don't have that, an `if` won't be enough. (But see below.)

You could do without the named code if you knew that your while "loop" didn't need to perform more than $n$ iterations. Then you just expand the loop explicitly:

```
run my code
if something is true then stop
else run my code
     if something is true then stop
     else run my code
     if something is ....

```

However, naming isn't actually required in order to loop without just writing the same code repeatedly. You can do it with recursion, as noted above, but it's possible to define a recursive function using a Y combinator. This is probably not very efficient, and if your language evaluates eagerly, as most do, it's kind of a mind-twister at first (it's simpler in with certain kinds of delayed evaluation), but it works, and it's cool. (My favorite source for the complicated version that most languages need is *The Little Schemer* by Friedman and Felleisen; you can probably find the simple version in any book on lambda calculus. That's the version described in the Wikepedia page, so maybe that's enough.)

In answer to the title of the question, in hardware there has to be some jump to a location--probably the same location--that causes the same code to be executed repeatedly--or *some* way of getting the same code to start running in the CPU, such as rewriting the stack. Others will be able to say more about this.

(It would be appropriate if the Y combinator function was named after Paul Graham's Y combinator company, since the company is named after the function. Graham's book on lisp *On Lisp* discusses recursion without naming, but very briefly, in an endnote on pages 387-388.)
> 1 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Is decimal number 8 represented as 3 bits or 4 bits in computer?
I was told by my professor that

"It takes c * ln(n) bits to store a number n, where ln() is base 2 and c is a constant."

Thus, to store a number 8, we need ln(8) = 3 bits(I think const c can be ignored here.), but isn't 8 stored as "1000" in a computer, which is 4 bits?

Thanks.

# Answer
> 2 votes
The exact number of bits for a number $n \gt 0$ is: $$\lfloor log\_2(n) \rfloor + 1$$ If to use natural logarithms, then this number will be: $$\lfloor log\_2(n) \rfloor + 1 = \lfloor log\_2(e) \cdot ln(n) \rfloor + 1 = \mathcal{O}(log(n))$$ We usually ignore the logarithm base in this kind of $\mathcal{O}$ notation, because logarithms with all constant bases are asymptotically equivalent.

# Answer
> 5 votes
$b$ bits have a total of $2^b$ distinct bit-patterns. To store 8 *distinct values*, you need at least 3 bits.

This does *not* tell you on its own how many bits are required to store the number 8, because that depends on the way that you assign numbers to bit patterns.

A typical "unsigned integer" uses $b$ bits to represent the numbers `0`, `1`, ... `2^b-1`. In that format, you would need 4 bits to represent 8, because $2^3-1\<8\<2^4-1$.

A typical "two's complement integer" uses $b$ bits to represent the numbers $-2^{b-1}$ to $2^{b-1}-1$. In this format, you would need 5 bits to represent 8, since $2^{4-1}-1\<8\<2^{5-1}-1$.

If you're only interested in representing powers of two (perhaps because you doing something hardware or memory related, where divisions such as alignment are only ever powers of two), you use fewer bits; for example, if `00` is 1, `01` is 2, `10` is 4, and `11` is 8, you only need 2 bits to represent 8.

# Answer
> 2 votes
Simple answer is $4$-bits. Why $4$? Because $0$ is included. You need to count zero as one unit. So we have $9$ units in total. The number $8$ is the $9$th number in the sequence: $\\{0,1,2,3,4,5,6,7,8\\}$. Hope this made it clearer.

We can make a table of all the binary numbers that the computer use:

```
1: 0 0000
2: 1 0001
3: 2 0010
4: 3 0011
5: 4 0100
6: 5 0101
7: 6 0110
8: 7 0111
9: 8 1000 *

```

The first colum represents the unit (or quantifier), the second column represent the decimal number, the final colum represent the binary number containing four bits.

The $\log\_2$ of $x$ is the power to which the number $2$ must be raised. Hence $\log\_2(x) = y$ such that $2^y = x$.

$\log\_2(8) = 3$.

$2^3 = 8$.

But, since the number $8$ is in the actual $9$th position, we have to add $+1$ when we compute the logarithm:

$\log\_2(8+1) = \log\_2(9) = 3.1699250014423126$

The computer cannot represent its value using $3.$something-bits, so we have to take the ceiling to be able to compress all numbers (including zero):

$\lceil\log\_2(9)\rceil=\lceil3.1699250014423126\rceil=4$.

This should be enough. We can see however that $2^4=16$. So we can conclude that with four bits we can compress/pack $16$-numbers in total:

$\\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\\}$. That is from $0$ to $15$. And number $8$ is in the $9$th position again.

Zero can be mistaken for not being treated as a quantity, so caution must be taken when computing with the base $2$ logarithm. Just add $1$ to fix it. Computer-registers are often restricted to $8$, $16$ or $32$ bits (which are power of twos). That is their numbers range from $0$ to $2^x-1$. As you can see their maximum value is $2^x-1$. The $-1$ shows some kind of symmetry to the notion that we have to add $+1$ to that log.

**Edit:** Also what Curtis F just stated, it depends on how you represent the numbers. You could indeed represent the number $8$ with just one bit, i.e. the mapping $\\{0,1\\}\rightarrow\\{0,8\\}$. But I don't think you want that.

# Answer
> 1 votes
Your professor is unclear here. If you know the number is eight, you don’t need to store it - zero bits. The question should be “how many bits do I need to store one of k different values”. For example , to be able to store a value from 0 to 8, 3 bits are not enough, you need four bits.

But if you store large amounts of numbers of different sizes, and you only need sequential access to them, you’d use something like Huffman coding or Arithmetic coding. In the first case the number of bits for the number eight depends on what percentage of your gazillions of numbers are eight, if one in 100 numbers on average are equal to eight, then most likely 7 bits would be used. With Arithmetic coding, it’s not even a fixed number of bits.

---
Tags: number-formats, binary
---


title: Dynamic Programming vs Memoization

text:
# Question
Title: Dynamic Programming vs Memoization
I am having trouble to understand *dynamic programming*. Mainly because of its name. As far as I understand, it's just another name of *memoization* or any tricks utilizing memoization.

Am I understanding correctly? Or is DP something else?

# Answer
From Wikipedia:

> There are two key attributes that a problem must have in order for dynamic programming to be applicable: *optimal substructure* and *overlapping sub-problems*. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead\[1\]. This is why merge sort and quick sort are not classified as dynamic programming problems.

Therefore, it seems the point is **overlapping of subproblems**. And if some subproblems are overlapped, you can reduce amount of processing by eliminating duplicated processing. There can be many techniques, but usually it's good enough to re-use operation result, and this reusing technique is *memoization*. I can imagine that in some cases of well designed processing paths, memoization won't be required.
> 1 votes

# Answer
*Summary: the memoization technique is a routine trick applied in dynamic programming (DP). In contrast, DP is mostly about finding the optimal substructure in overlapping subproblems and establishing recurrence relations.*

*Warning: a little dose of personal experience is included in this answer.*

*Reading suggestion: If this answer looks too long to you, just read the text in boldface*.

## Background and Definitions

**Memoization** means the optimization technique where you memorize previously computed results, which will be used whenever the same result will be needed.

Memoization comes from the word "memoize" or "memorize".

**Dynamic programming (DP)** means solving problems recursively by combining the solutions to similar smaller overlapping subproblems, usually using some kind of recurrence relations. (Some people may object to the usage of "overlapping" here. My definition is roughly taken from Wikipedia and *Introduction to Algorithm* by CLRS.) I will only talk about its usage in writing computer algorithms. Note that an actual implementation of DP might use iterative procedure.

Why is DP called DP? The word "dynamic" was chosen by its creator, Richard Bellman to capture the time-varying aspect of the problems, and because it sounded impressive. For the full story, check how Bellman named dynamic programming?.

Nowadays I would interpret "dynamic" as meaning "moving from smaller subproblems to bigger subproblems". (The word "programming" refers to the use of the method to find an optimal program, as in "linear programming". People like me treat it as in software programming sometimes.)

## Explanations

**Why do some people consider they are the same?**

It is understandable that Dynamic Programming (DP) is seen as "just another name of memoization or any tricks utilizing memoization". When the examples and the problems presented initially have rather obvious subproblems and recurrence relations, the most advantage and important part of DP seems to be the impressive speedup by the memoization technique.

In fact, for some time, I had been inclined to equating DP to mostly memoization technique applied to recursive algorithms such as computation of Fibonacci sequence or the computation of how many ways one can go from the left bottom corner to the top right corner of a rectangle grid.

**How are DP and memoization different?**

**The memoization technique is an auxiliary routine trick that improves the performance of DP (when it appears in DP)**. It appears so often and so effective that some people even claim that DP is memoization

Let me use a classic simple example of DP, the maximum subarray problem solved by Kadane's algorithm, to make the distinction between DP and memoization clear.

Since I was a kid, I had been wondering how I could find the maximum sum of a contiguous subarray of a given array. First thought was grouping adjacent positive numbers together and adjacent negative numbers together, which could simplify the input. Then I tried combine neighbouring numbers together if their sum is positive or, hm, negative. Then the uncertainty seemed attacking my approach from everywhere. Many years later, when I stumbled upon the Kadane's algorithm, I was awe-struck. It is such a beautiful simple algorithm, thanks to **the simple but critical observation** made by Kadane: any solution (i.e., any member of the set of solutions) will always have a last element. Trust me, only if you can appreciate the power of such a simple observation in the construction of DP can you fully appreciate the crux of DP.

Please note there is not any (significant) usage of memoization in Kadane's algorithm.

Just in case you might brush off Kadane's algorithm as being trivial, let me present two similar problems.

* Can you find efficiently the maximum sum of two disjoint contiguous subarray of a given array of numbers?
* Can you find efficiently two disjoint increasing subsequence of a given sequence of numbers the sum of whose lengths is the maximum?

If you can find the solution to these two problems, you will, I believe, be able to appreciate the importance of recognizing the subproblems and recurrence relations more. That might just be the start of a long journey, if you are like me.

By Wikepedia entry on Dynamic programming, the two key attributes that a problem must have in order for DP to be applicable are the optimal substructure and overlapping sub-problems. In other words, the crux of dynamic programming is **to find the optimal substructure in overlapping subproblems, where it is relatively easier to solve a larger subproblem given the solutions of smaller subproblem**.

In summary, here are the difference between DP and memoization.

* **DP is a solution strategy which asks you to find similar smaller subproblems so as to solve big subproblems. It usually includes recurrence relations and memoization**.
* **Memoization is a technique to avoid repeated computation on the same problems. It is special form of caching that caches the values of a function based on its parameters.**

## More advanced dynamic programming

Here I would like to single out "more advanced" dynamic programming. More advanced is a pure subjective term. What I would like to emphasize is that the harder the problems become, the more difference you will appreciate between dynamic programming and memoization.

Even as the problem becomes harder and varied to solve, there is not much variation to the memoization. The memoization technique are present and helpful most of the time. However, it becomes routine. After all, all you need to do is just to record all result of subproblems that will be used to reach the result of final problem.

However, as I have been solving more and harder problems using DP, the task of identifying the subproblems and construction of the recurrence relations becoming more and more challenging and interesting. There are many variations and techniques in how you can recognize or define the subproblems and how to deduce or apply the recurrence relations. Many of the harder problems look like having a distinct personality to me. Here are some classical ones that I have used.

* the More-Subproblems Principle (named by me for the lack of a name): when the recurrence relations cannot be established because the solutions to bigger subproblems need to use some condition that is not tracked by the solutions to smaller subproblems, extend the subproblems by another parameter (a.k.a. dimension) to keep track of that condition. The more refined subproblems have been solved, the easier to solve the bigger subproblems, even with the extra condition.

The following is a nice article.
> 19 votes

# Answer
Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations.

Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation results. In other words, it is the research of how to use memoization to the greatest effect.

---

The name "dynamic programming" is an unfortunately misleading name necessitated by politics. The "programming" in "dynamic programming" is not the act of writing computer code, as many (including myself) had misunderstood it, but the act of making an optimized plan or decision.

---

The earlier answers are wrong to state that dynamic programming *usually* uses memoization. Dynamic programming *always* uses memoization. They make this mistake because they understand memoization in the narrow sense of "caching the results of function calls", not the broad sense of "caching the results of computations".

For example, let's examine Kadane's algorithm for finding the maximum of the sums of sub-arrays. The listing in Wikipedia is written in Python, reproduced below:

```
def max_subarray(numbers):
    """Find a contiguous subarray with the largest sum."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

```

On first sight, this looks like it does not use memoization. That's only because memoization is implicit in the `current_sum` variable. If this variable is not used to memoize the intermediate results, then every previous `current_sum` needs to be computed again, and the algorithm does not save any time.

This point is more clear if we rewrite the code in a pure functional style:

```
max_subarray numbers = go 0 0 numbers
  where
    go best_sum _           []     = best_sum
    go best_sum current_sum (n:ns) =
         let current_sum' = max 0 (current_sum + n)
             best_sum' = max best_sum current_sum'
         in go best_sum' current_sum' ns

```

Now, what if instead of `current_sum` being a parameter, it is a function that finds the maximum sum of all sub-arrays ending at that element?

```
max_subarray numbers = go 0 [] numbers
  where
    current_sum_f []          = 0
    current_sum_f (n:prev_ns) = max 0 (current_sum_f prev_ns + n)
    go best_sum prev_ns []     = best_sum
    go best_sum prev_ns (n:ns) =
         let best_sum' = max best_sum (current_sum_f (n:prev_ns))
         in go best_sum' (n:prev_ns) ns

```

In the rewrite above, `current_sum_f` is the computation actually representative of the sub-problem "finding the maximum sum of all sub-arrays ending at that element".

Without memoization, the algorithm is $O((1 + N) * N / 2)$ in time and $O(1)$ in space. Exactly the same as a naive algorithm searching through every sub-array.

With naive memoization, that is, we cache all intermediate computations, the algorithm is $O(N)$ in time and $O(N + 1)$ in space. Typical exchange of space for time.

But that's not Kadane's algorithm. Kadane's algorithm only memoizes the most recent computation. It is $O(N)$ in time and $O(2)$ in space. Why is that correct?

Because for `current_sum_f`, recurrence is only one step deep. If it is like generating Fibonacci sequence, which is two steps deep, then we need to memoize the two most recent computation.

---

References:

---

Read More:
> 5 votes

# Answer
In Memoization, you store the expensive function calls in a cache and call back from there if exist when needed again. This is a top-down approach, and it has extensive recursive calls.

In Dynamic Programming (Dynamic Tables), you break the complex problem into smaller problems and solve each of the problems once. In Dynamic Programming, you maintain a table from bottom up for the subproblems solution.

Both are applicable to problems with Overlapping sub-problems; as in Fibonacci sequence. If there is no overlapping sub-problems you will not get a benefit; as in the calculation of $n!$

The result can be solved in same $\mathcal(O)$-time in each. DP, however, can outperform the memoization due to recursive function calls. If the sub-problem space need not be solved completely, Memoization can be a better choice.
> 1 votes

---
Tags: terminology, dynamic-programming, memoization
---


# Question
Title: Thoughts on definition for disadvantage of concurrent processing?
I'm a Computer Science student currently learning about concurrent processing. I found the benefits and disadvantages in my book vague, did some online research and put together a more detailed way of defining the disadvantage of concurrent processing; thoughts and corrections are appreciated.

Book version: "The drawback is that if a large number of users are all trying to run programs, and some of these involve a lot of computation, these programs will take longer to complete."

My version: Using concurrent processing on multiple users running the same program, means no one can finish until everyone has nearly finished. This is inefficient compared to consecutive processing where the last user would finish at the same time as the last user in concurrent processing, but some users would finish significantly earlier. However the scaling of this inefficiency is limited by the amount of threads, because concurrent processing only switches between the first process of each thread queue. The process at the beginning of each thread can change with the use of interrupts though.

Do you think I elaborated on the book properly, or misunderstood it?

# Answer
I'm studying for the same A Level and have found that **deadlock**, **starvation**, **race conditions** and the **overhead** affiliated with coordinating simultaneous threads are reasonable, in-depth disadvantages of concurrent processing

**Deadlock** occurs when each process/thread is waiting for another to finish (meaning that no process is ever able to complete). For example, this happens with cyclic dependencies *(e.g. when process A needs B which needs C which needs A)*.

**Starvation** is when a process is always denied a resource that it needs, resulting in the process never completing.

**Race conditions** are when two processes are sharing the same storage location (i.e. variable) and the result of operations depends on the order in which they are ran.

**Overhead** \- there is additional processing overhead to coordinate the individual threads (and combine their results). This can mean, for some problems, a single thread is more efficient than multiple.

Hope I've helped clarify things for anyone who was also confused with this topic,

Josh

*Sources:*

Cambridge Elevate OCR A Level Textbook

Rensselaer Polytechnic Institute Lecture Notes
> 1 votes

---
Tags: concurrency
---


title: Bus and System Clocks

text:
# Question
Title: Bus and System Clocks
What is the difference between a Bus clock and a System Clock? Do they function the same way? I have been reading about System clocks but I can't really find anything about bus clocks in my book to compare the two.

# Answer
In a simple computer architecture with a single active CPU connected to RAM and other passive peripherals by a bus, then there is a timing signal (typically produced by a quartz oscillator) that synchronises the internal operation of the CPU. This clock signal is the system clock.

There may also be a separate timing signal that synchronises the activities of writing to and reading from the bus. This is the bus clock. Because the speed at which data can be reliably transmitted across the bus may be lower than the internal speed at which the CPU runs, the bus clock signal is usually at a lower frequency than the system clock. The bus clock signal may be produced by passing the higher frequency system clock signal through a frequency divider.

In more complex architectures, where there are multiple active components (CPUs, FPUs, graphics cards, memory controllers, I/O controllers) running at different speeds, then the bus clock is often the fundamental synchronising signal, and each component then multiplies the frequency of the bus clock signal by a specific ratio to obtain its internal system clock signal.

For more details see https://anydifferencebetween.com/difference-between-system-clock-and-bus-clock/ and https://en.wikipedia.org/wiki/CPU\_multiplier.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Converting context-free grammar to chomsky normal form
I'm trying to prove that the following CFG can be converted to a CNF:

```
S -> aAB
A -> aAa
A -> bb
B -> a

```

Here below is how I've managed so far:

### Step 1: add a new start state

```
S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a

```

### Step 2: remove epsilon rules

There are no such rules in this CFG.

### Step 3: remove non-terminal to non-terminal rules

```
S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a

```
Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:
```
S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB

```

So this is where I got confused. I have now both `C` and `F` that go to `AB`. If I've done this correctly that would mean that either `C` or `F` can simply be removed. Or, of course, I've done something wrong in this procedure.

# Answer
You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

```
A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.

```

Consider the grammar

```
S → TU
S → UT
T → a
U → a

```

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is. Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form! A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it. Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form. But nobody asked it to. Except you.

Just let the poor algorithm go about its ways. You know what to do once it's finished :-)
> 6 votes

# Answer
Here is Swaira Shabbir's image answer, converted into mathjax:

$$ \begin{align} S&\rightarrow aAB\\ A&\rightarrow aAa\\ A&\rightarrow bb\\ B&\rightarrow a\\ \end{align} $$ CFG-to-CNF
$\underline{Step\text{ }1}$: Not hold, as there is no 'S' on right side of any production.
$\underline{Step\text{ }2}$: No Epsilon rules here i.e. No Useless, Null & Unit Productions.
$\underline{Step\text{ }3}$: Non terminal -\> 2 Non terminals
Non Terminal -\> one terminal
Production that does not follow these rules, convert their right side to uppercase & add new productions. $$ \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ S&\rightarrow XAB\\ A&\rightarrow XAX\mid YY\\ B&\rightarrow a\\ \end{align} $$ $\underline{Step\text{ }4}$: Reduce length of right side of productions to '2' terminals by introducing new productions. $$ \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ R&\rightarrow XA\\ S&\rightarrow RB\\ A&\rightarrow RX\mid YY\\ B&\rightarrow a\\ \end{align} $$ So required CNF Form is:
> 0 votes

# Answer
1) no empty production 2) no unit production 3) convert all mix term and terminal greater than one into capital

S-\>AAB A-\>AAB/BB B-\>a A-\>a

4) Reduce the length of each non terminal upto 2 and add new rule S-\>TB A-\>TB/BB B-\>a A-\>a T-\>AA (new rule)
> -2 votes

# Answer
Rules for conversion of CFG to CNF https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/

Here is the solution of question:
> -3 votes

---
Tags: context-free, formal-grammars, proof-techniques, chomsky-hierarchy
---


title: regex of three repeating number

text:
# Question
Title: regex of three repeating number
I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but never has the occurrence of 123.

```
((1 or 3)*(211 or 231 or 233 or 2211 or 2231 or 2233))* 222

```

is as far as I could get, I can't see how to prevent 123 from happening while still allowing a string like 1223221222 to occur. Any thoughts?

# Answer
First, "has no occurence of 123".

So the string can start with any number of 2s and 3s. Then it has 0, 1 or more components that start with 1, and followed by any number of 2s and 3s other than 23. So the 1 is followed by nothing, a single 2, 22 and any number of 2s and 3s, or 3 and any number of 2s and 3s.

Each of these components could contain three or four consecutive 2s. Four consecutive 2s are not allowed, three consecutive 2s may only happen once. So for each of those components add things to not allow three 2s in a row, or to allow three but not four 2s in a row. And then the language is any number of components with no three 2s, optionally followed by a component with three 2s and any number of components with no three 2s.

It's a bit complicated, but not too bad.

So make regular expressions for "lead\_2" = "any number of 2s and 3s, but no three 2s in a row", "lead\_3" = "any number of 2s and 3s, with 222 once but not twice, and no 2222", "follow\_2" = "1, followed by lead\_2 not starting with 23", "follow\_3" = "1, followed by lead\_3 not starting with 23", and the whole language is

```
lead_2 (follow_2)* or
lead_2 (follow_2)* follow_3 (follow_2)* or
lead_3 (follow_2)*

```
> 1 votes

# Answer
Assuming that we consider 2222 to contain 222 twice (from character 1 to 3, and from character 2 to 4): We define some building blocks: A = "no 1's, no 222". B = "no 1's, exactly one 222", C = "1 followed by A, but not followed by 23", and D = "1 followed by B, but not followed by 23". Then the regular expression is

```
A C* | A C* D C* | B C* = (A | A C* D | B) C*

```

We take another building block X = ((2 | 22)? 3)\* which is any number of 3s, each preceeded by one, two or no 2's.

A consists of any number of 3s preceeded by no, one or two 2s, followed by no, one or two 2s. A = X (2 | 22)?

B is quite similar, but it ends either in 222, or in 2223 followed by A: B = X 222 (3 A)?

C starts with 1. If there are any 3's, then the first one is not preceded by exactly one 2, otherwise it is very similar to A: C = 1 ((22)? 3 X)? (2 | 22)?.

D starts with 1, followed by B, but again if there are any 3's then the first one is not preceded by exactly one 2. D = 1 ((22)? 3 X)? 222 (3 A)?.

To get the usual regular expression, substitute everything, which will make the expression rather large and unreadable.

```
(((2 | 22)? 3)* (2 | 22)? | ((2 | 22)? 3)* (2 | 22)? (1 ((22)? 3 ((2 | 22)? 3)*)? (2 | 22)?)* 1 ((22)? 3 ((2 | 22)? 3)*)? 222 (3 ((2 | 22)? 3)* (2 | 22)?)? | ((2 | 22)? 3)* 222 (3 ((2 | 22)? 3)* (2 | 22)?)?) (1 ((22)? 3 ((2 | 22)? 3)*)? (2 | 22)?)*

```

Same thing can be achieved with a state machine with 10 accepting states and one non-accepting state.
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?
I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one I get when calculating the same speedup using Gustafson's law. I don't understand why is that.

# Answer
> 6 votes
The reason is that Amdahl's law and Gustafson's law refer to two very different situations.

In particular, Amdahl's law applies to those cases in which the problem size is fixed, e.g. you need to process a static dataset or an image of given dimensions. The law treats the problem size as being a constant (size constrained model), and clearly shows how the execution time decreases as the number of processors increases. This law can be applied to any system, not just to parallel systems; it is a very general statement about any improvement in a system, i.e., no matter how much one improves one part of a system, the improvement in the overall performance is bounded by $1/f$, where $f$ is the fraction of the original time spent in parts of the system one does not improve. This model, fixing the amount of data per processor, usually provides the highest efficiency possible (this is commonly referred to as strong scaling).

On the other hand, rather than assuming that the problem size is fixed, it is just as valid to assume that the parallel execution time is fixed. This is exactly what the Gustafson's law does: as the parallel system size is increased (i.e. the number of processors $p$ is increased), the problem size is increased to maintain constant parallel execution time (weak scaling). Therefore, this is a time constrained model. So, the important difference is that the scaled speedup of Gustafson starts with a big problem on a big ($p$ processors) machine and looks back toward the one-processor case and asks how long it would have taken to execute, whilst Amdahl's law starts with a problem on the one-processor machine, and asks how long it might take on a many-processor parallel machine. Gustafson simply noted that there were lots of problems that seemed to run well on lots of processors: they computed for a great deal of time $(1-s)$ using all the processors, and not all that long $(s)$ in a serial fashion. So he derived the scaled speedup formula to help explain that.

Does this contradict Amdahl's law? No, of course. Amdahl works when you are given a fixed size input and you want to understand how fast you can process in parallel that input. Gustafson works when you can increase the problem size and you want to solve larger problems in the same amount of time. For instance scientist are actually interested to solving larger instances of problems, or want to increase the complexity of a model to gain better accuracy.

# Answer
> 0 votes
It seems that the "50%" in Gustafson's law means that 50% of the time, tasks are being run in parallel. For example with 100 tasks and four processors, running 20 tasks on a single processor in 20 time units, then 80 tasks running on four processors also in 20 time units, gets called "50%" but it means "the processors are running parallelizable tasks 50% of the time". Amdahl's law would call the exact same situation "80% of tasks are parallelizable".

So it seems that someone really messed up what they are calling things.

---
Tags: parallel-computing
---


# Question
Title: Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?
If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).

Intuitively, it may feel it is, because it is like the reverse of build it up.

(Building a heap can be O(n) -- in Wikipedia).

If building a heap is O(n) in the worst case, including the numbers are all adding by ascending order, then taking the heap down is exactly the "reverse in time" operation, and it is O(n), but this may not be the "worst case" of taking it down.

If taking down a heap is really O(n), can't the selection problem be solved by building a heap, and then taking it down (k - 1) time, to find the kth max number?

# Answer
Delete-max is $O(\log n)$, so you have $O(n) + k O(\log n)$ which is $O(n)$ for fixed $k$. But if $k$ is not fixed, it can be up to $\frac{n}{2}$ (if it's greater, just use a min-heap instead of a max-heap), and $O(n) + \frac{n}{2} O(\log n) = O(n \log n)$.

In fact, if there was some tricky way to do what you want, you would solve sorting in $O(n)$, not just selection, which is known to be impossible.
> 2 votes

# Answer
Building a heap is O(n).

Taking the first item from a heap and then re-arranging things so it is a heap again is O (log n), and since you need to do this n time is O (n log n).

Of course you can just take one element of the heap after the other in O(n), but they won't be in sorted order. And building a heap can be done in O(n) because you add n/2 items to the lowest level of the heap when it has height 1, n/4 to the second lowest level of the heap when it has height 2, n/8 when it has height 3, and so on. And n/2 * 1 + n/4 * 2 + n/8 * 3 ... \< n.
> 1 votes

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: generalizing ball-bin problem to k-universal family
I am trying to solve a question in the book on *Probability and Computing* by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal hashing.

In the standard bin-ball problem setup there are $n$ bins and $n$ balls. These $n$ balls are randomly thrown (independently) in $n$ boxes and we try to find maximum occupancy in any bin. This can be done by considering a hash function $h: \[n\] \to \[n\]$. We say that ball $i$ goes in bin $h(i)$. In this case hash function comes from a 2-universal family. It is shown that for 2-universal hash family, max occupancy is $l\_{\max}=1+2\sqrt n$ with probability greater than $\frac{1}{2}$. It follows with usual application of Markov's inequality. Now we try to generalize this to hash $h$ coming from a $k$-universal family and find $l\_{\max}$ so that max occupancy is less than that with probability $\frac{1}{2}$.

I tried to do following: First set up indicator variable as in previous case for 2-universal problem

$X\_{ij}=1$ if ball i goes in bin $j$. Now load for bin $i$ is $X=\sum\_{j=1}^{n}X\_{ij}$.

Since hash is now $k$-universal we try to go for Markov on $k^{\text{th}}$ moment instead of Markov (which comes from 1-st moment) to get probability bound of $\frac{1}{2n}$. In the end we apply union bound. But I am unable to simplify expression for $k$-th moment in this context to get an answer.

Definition of $k$-universal hash function

$\mathrm{Pr}(h({i\_{1}})=h({i\_{2}})=\cdots=h({i\_{k}}))= \frac{1}{n^{k-1}}$ for any $k$ distinct elements $i\_1,\ldots,i\_k$.

# Answer
Let $B\_j$ be the number of balls in the $j$'th bin. Then $$ \mathbb{E}\left\[\sum\_{j=1}^n \binom{B\_j}{k}\right\] = \sum\_{i\_1 \< \cdots \< i\_k} \Pr\[h(i\_1) = \cdots = h(i\_k)\] = \frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}. $$ Let $C\_j = B\_j - (k-1)$. Then $$ \mathbb{E}\left\[\sum\_{j=1}^n C\_j^k\right\] \leq k! \mathbb{E}\left\[\sum\_{j=1}^n \binom{B\_j}{k}\right\] \leq n, $$ and so with probability at least $1/2$, $$ \max\_j C\_j^k \leq \sum\_{j=1}^n C\_j^k \leq 2n, $$ hence $C\_j \leq (2n)^{1/k}$, implying that $l\_{\max} \leq (2n)^{1/k} + k-1$.
> 1 votes

---
Tags: probability-theory, hash, randomness
---


# Question
Title: Table-Driven Lexer and the Classification Table
I'm trying to implement a compiler for a custom language as part of an assignment.

I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 tables:

1. Classification Table
2. Transition Table
3. Token Type Table

**My problem is mainly coming from the fact that the only example I've seen of the concept of a table-driven lexer is the "famous" (because I see it in every University's online notes) Cooper & Torczon DFA for reading digits.** *Page 25*

From what I gather, the purpose of each of these is as follows:

> 1: To classify the atomic parts of the language, such as digits (0,1,2,3....) and letters (a,b,c,...)
>
> 2: To define what should happen next according to what's just been classified (If digit, go to state X, if letter, go to state Y)
>
> 3: Apparently this is used to check whether or not the string is accepted. Honestly I don't even know what the point of this is.

The grammar I'm trying to build a compiler for is much more complicated than the examples I've seen online. It contains more "atomic" symbols, such as operators (\*,+,-,/,\>, etc..) and reserved keywords (if, for, while, etc...)

By atomic, I mean symbols that stand on their own. (I.e. *if* is a symbol in its own right, not *i* and *f*) This poses a problem for me, since I won't be able to know if I'm reading *if* or a string of the form a**if**b

**Here's what I'm currently trying to do:**

1. First, I'm building a CAT (classifier table) for all the atomic symbols of the language. I don't know if this is the right thing to do, especially when I have 52 letters (English alphabet), 10 digits and reserved words.
2. I will then merge all the CATs together. So I will have one big CAT that covers letters, digits, and reserved words.
3. Then, I will build a (*big*) transition table, so that when I read a character and determine its classification (**problem: What about reserved words that take more than 1 character?**) I will know where to transition to next.
4. These tables are used by a simple DFA class which, once the lexeme is read, will spit out a token.

The assignment specifies that I have to use a table-driven lexer.

# Answer
A table-driven lexer is just a way of simulating a DFA. Lexer generators build DFAs from a lexical description, and then compile the DFA into the tables necessary to produce a lexical scanner.

Note that the goal is to not just identify lexemes, but to *classify* them by lexical type. Some lexemes have a unique spelling (like `if` and `<=`); others represent classes of symbols which have the same syntactic significance but different semantics. (That would be, for example, *IDENTIFIER* and *NUMBER*, which are two lexical types, each with a potentially unlimited number of different associated tokens.)

Lexical analysis with a state machine is slightly different from using a DFA to recognise strings, because the point of lexical analysis is to divide the input into a sequence of substrings, each of which is a token. It's important that this sequence is a partitioning of the string; every character is part of some token. That means that each successive token starts *exactly* where the previous token finished. In particular, that means that you don't have to worry about the `if` in the middle of `different`, but you do have to think about the `for` in `fortunate`. (All the same, it doesn't present a huge problem.)

As the Dragon book notes (and so do Cooper&Torczon IIRC), the vast majority of lexers use the "maximal munch" procedure (sometimes with a few exceptions), in which the lexeme produced at some point in the input is the longest one matchable with some lexical pattern.

In some cases, it is possible that the lexical analyser will overreach. As an example, consider lexing C, where `.` and `...` are both possible lexemes, but `..` is not. If the input contains `..`, the lexical analyser needs to try to match the pattern `...`. If that fails, if the input contains `..` followed by something other than another `.` (for example, `..345`), the lexical analyser will have to backtrack. It will accept the first `.` as a token, and then restart the scan with the second `.` (which will turn out to lead to recognizing the number token `.345` in this case).

So the precise algorithm used by the analyser when it is asked to produce the next token is:

1. Run the DFA until it reaches a state in which the next character has no valid transitions.
2. While running the DFA, always remember the last accepting state encountered.
3. When the DFA cannot be advanced any further, if it is not in an accepting state, back up to the last accepting state and return the corresponding token.

It's always a good idea to try to avoid this backtracking, but it is not always possible as the above C example indicates.

We said earlier that the goal of the analyser is to identify the lexical type of the token. How does it do that? Simple. The various patterns are combined into a single DFA, using the standard NFA-\>DFA transformation. (That's in the Dragon Book.) In the DFA which results from that transformation each state is a set of states from the original NFA, and is an accepting state if any of the associated NFA states is accepting. We map that onto a token type by noting which of the NFAs contains the associated accepting state. If there is more than one NFA which has contributed an accepting state, then we choose one of them arbitrarily. (Usually, we've arranged the patterns in priority order so that we can simply say that the first pattern wins.)

That gives us a mapping from DFA state to pattern number, and that is the role of the Token Type table.

In case that explanation was too theoretic, I've created two graphs. The first one shows DFAs for four patterns: the token `<`, the token `<=`, the token `if` and the token `ID` (any identifier). In the transitions, please interpret "letter" as meaning "any letter other than `i` or `f`", which was just too long to put on the graph. And see the paragraph below about character classification.

In the second graph, I show the DFA which results from combining these. I leave it as an exercise to construct the Token Type table.

The Transition table is simple: it just represents the DFA. It maps a pair `<state, character>` to a new state. Unfortunately, there are a lot of different possible characters -- 256, if we use 8-bit characters -- and usually quite a few states, and that would make for quite a large table, since it is essentially a two-dimensional array. To make the table smaller, we note that many characters have precisely the same transitions *in every state*. As a simple example, most of the 256 possible input characters are only valid inside character string literals or comments, and in those contexts all of them are effectively identical.

That's what the character classification table is. We gather the possible input characters into a set of equivalence classes, where each equivalence class has exactly the same transitions in every state. Any character with a specific transition -- including the `i` and the `f` in `if`, for example -- will be in an equivalence class by itself. But even then, we'll find that many alphabetic characters are not present in any keyword (upper-case characters, for example). And while some digits may have specific transitions -- `0` is a common case -- there are very few lexicons in which `2` and `3` have specific transitions. So we can probably reduce the number of possible transition characters from 256 to maybe 40 or 50, which is an 80% reduction in size of the transition table. In any case, if you don't want to do that, it's just an optimisation. The analyser will work fine either way.
> 7 votes

---
Tags: formal-grammars, compilers, lexical-analysis
---