# Question
Title: How fast can all nth roots of an integer be computed?
I mean that for every $i$ from 2 to $\lceil \log\_2n\rceil$ I want to know $\lfloor \sqrt\[i\]{n}\rfloor$. Could this be done faster than computing the roots one by one?

# Answer
Let's say n is very large, say around $2^{1000}$. In theory, you can calculate the k-th root of n by calculating $2^{(\log n) / k}$. Doing this for multiple k means you calculate $\log n$ only once, so you save some time here.

You will spend a large amount of time calculating say the first 50 roots because you need very high precision to calculate the root rounded down to the nearest integer. I can't see you saving any time by calculating multiple roots together.

The next roots are much easier to calculate. Then if k gets large, say 200, you will find that many roots rounded down are the same. Here you can make some savings by calculating for which range of integers k the k-th root of n will be between some integer r and r+1, and therefore the k-th root rounded down equals r. In this example there will be a few hundred k where the k-th root rounded down equals 2, for example.

But I think the first few roots (2nd, 3rd, 4th root) will take so much more time due to the high precision required, that the effort for the remaining roots will be much smaller. So I would say that you can save a little bit of time, but likely just a constant factor.

(Also, the effort may be bigger if the k-th root of n is very, very close to an integer, but that doesn't change the analysis. )
> 2 votes

---
Tags: algorithms
---


# Question
Title: I don't understand the case 4 of red-black tree deletion
I don't know why case 4 will resolve the issue of the double black of $x$ described in Introduction to algorithm p.329. I know case 1 is transformed into one of {2,3,4} case, and case 2 re-point $x$ to its parent node so it's approaching the root, and case 3 will be transformed into case 4, but both case {3,4} will not change the pointer $x$, anyway so how case 4 work?

Is it because for paths include $C,E$ there is no difference about the number of blacks while for that about $\alpha,\beta$ an extra black node $B$ is passed?

# Answer
> but both case {3,4} will not change the pointer , anyway so how case 4 work?

Let us check case 4. Although the parent pointer of node $x$ is not changed, i.e., the parent node of $x$ is still $B$, the color of $B$ is set to black and node $D$ is lifted to become $B$'s parent with $B$'s original color.

So, going from the graph on the left hand side of case 4 on the image in the question to the graph on the right hand side, we have added that "extra" black node that was supposed to attached to $x$, which is, in your words, an extra black node $B$ is passed for the paths going through $\alpha,\beta$.

Furthermore, for that graph on the right hand side, we can check that all simple paths from the node to descendant leaves that do not pass through $A$ contain the same number of black nodes as before. Since all properties of black-red tree have been restored, case 4 ends the while loop, which ends RB-DELETE-FIXUP$(T, x)$, which ends RB-DELETE$(T, z)$.
> 2 votes

---
Tags: balanced-search-trees, red-black-trees
---


# Question
Title: List of algorithm problems in term of ideals
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem we have a solution then it means the problem has a question. For example we can transform the problem of MAx-Clique to the following set of polynomials

$P=\\{x\_i^2-x\_i, x\in \[n\]\\}\cup \\{x\_ix\_j, (i,j)\notin E\\}$

I want to know there is any list of problems like this? If you know any paper or book such that there lots of problems like the above one which can transform it to set of polynomials please let me know and have it.

# Answer
We all know that 3SAT is NP-complete. Here is how to reduce 3SAT to your problem.

Suppose that the 3SAT instance has variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$. The new instance will have variables $x\_1,\ldots,x\_n,y\_1,\ldots,y\_m,z\_1,\ldots,z\_m$, and the following polynomials:

* $x\_i^2 - x\_i$ for each $i \in \[n\]$ and $y\_j^2 - y\_j, z\_j^2 - z\_j$ for each $j \in \[m\]$.
* For a clause $C\_\ell$ of the form $x\_i \lor x\_j \lor x\_k$: $x\_i + x\_j + x\_k - y\_\ell - z\_\ell - 1$.
* If a clause has negated variables, say $x\_i$ appears as $\overline{x\_i}$, then replace $x\_i$ with $1-x\_i$ in the polynomial stated above.

Why does this work, the first type of polynomials constrain all variables to be $0,1$. The polynomial $x\_i + x\_j + x\_k - y\_\ell - z\_\ell - 1$ states that $x\_i + x\_j + x\_k = 1 + y\_\ell + z\_\ell$, and since $y\_\ell,z\_\ell$ occur only in this polynomial, this is the same as $1 \leq x\_i + x\_j + x\_k \leq 3$, that is, $x\_i + x\_j + x\_k \geq 1$, or equivalently, $x\_i \lor x\_j \lor x\_k$.
> 2 votes

---
Tags: algorithms, graphs, optimization, integer-programming
---


# Question
Title: How to create a cellular automata rule to achieve a desired pattern?
Normally, to find the rule that is suitable to our need, we have to generate all possible rules and apply each rule on a seed and check whether a rule produces a desired pattern. This method is exhaustive and computationaly intensive.

Is there a way to derive the rule that would generate the desired pattern?

# Answer
One way to achieve what you describe would be to encode your problem as a SAT instance, with clauses decribing the desired initial and final pattern and the state transitions under the (fully or partly unknown) evolution rule, and then let a generic SAT solver look for a solution.

In fact, at least for certain classes of rules (specifically, two-state isotropic rules on the Moore neighborhood, a class that includes e.g. Conway's Game of Life), you won't even need to implement this yourself, since there is an existing program called LLS that can do exactly that. While a full tutorial on how to use LLS is beyond the scope of this answer, one of the things it can do is take a partial rule string (i.e. a description of the state transition rule, with some transitions left unspecified) and a list of grids fully or partially describing the evolution of a pattern over several generations, and search for a solution that fills in the unspecified bits of the transition rule and/or the pattern.
> 2 votes

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


# Question
Title: Finding the maximum of a bitonic sequence
Given to us is an array $B\[1\],\ldots,B\[n\]$ as input, which satisfies the following property: there exists a special index $i^\* ∈ \\{1, \dots , n\\}$ such that $$B\[1\] \< B\[2\] \< \dots \< B\[i^\*− 1\] \< B\[i^\*\] \> B\[i^\* + 1\] \> B\[i^\* + 2\] \> \dots \> B\[n\].$$

It is noted that the index $i^\*$ is not given as part of the input.

The question asks me to design an algorithm for computing the index $i^\*$, whilst trying to ensure it has the smallest running time possible.

I just wondered if anyone could produce this algorithm and explain your thought process on how you came up with it if possible? Stuck on these type of questions

# Answer
> 3 votes
The first thing that comes to my mind after reading your question is as follow. Draw the sequence as a graph given below. Each $B\[i\]$ you can think of a point in the graph given below.

The idea to do binary search should be clear from the question as input sequence is almost sorted. Now if you guess the peak point then you are in a good position, but during the binary search if you choose a number which will give you two cases.

The above two cases are the cases in which you need to think, but if you have tried few problems on binary search then now the problem will be easy to solve. More formally you can see the yuval's answer. You ask for the thought process, I have tried to give you my thought process. For any two persons thought process is different, there may be many other way to visualise the problem you have described.

# Answer
> 1 votes
A sequence satisfying your constraint is known as *bitonic*. (Strictly speaking, a bitonic sequence is one which is either monotone increasing then decreasing *or* monotone decreasing then increasing). You can find the index $i^\*$ using binary search. The idea is that given an index $i$, you can compare $i$ to $i^\*$ as follows:

* If $B\[i-1\] \< B\[i\] \> B\[i+1\]$, then $i = i^\*$.
* If $B\[i-1\] \< B\[i\] \< B\[i+1\]$, then $i \< i^\*$.
* If $B\[i-1\] \> B\[i\] \> B\[i+1\]$, then $i \> i^\*$.

I'll leave you to handle the corner cases $i = 1$ and $i = n$.

---
Tags: algorithms, arrays, discrete-mathematics
---


title: 2-opt vs 3-opt comparison

text:
# Question
Title: 2-opt vs 3-opt comparison
I have a question regarding performance of 2-opt and 3-opt algorithms.

I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%.

Surprisingly, in few cases my 2-opt algorithm outperforms the 3-opt algorithm. I am wondering, is it some kind of error or it may happen that the 2-opt algorithms sometimes end in the better local optimum?

(I know that if solution is 3-opt, then it is also 2-opt. But we can find multiple 2-opt or 3-opt solutions in the same route, don't we?)

# Answer
> 2 votes
Your experiments show that 2-opt could outperform 3-opt. The reason is that there are many local optima, and some of the are better than others. Local search guarantees reaching a local optimum with respect to the moves being considered, but it doesn't provide any guarantee beyond that. It could be that one point which is locally optimal with respect to 2-opt is better than another point which is locally optimal with respect to 3-opt.

You can modify your algorithm to first try local search with respect to 2-opt and then with respect to 3-opt, and take the better solution. You could improve this by running a 3-opt local search starting at the 2-opt local minimum.

There are other degrees of freedom in the local search algorithm: for example, when there are several possible local improvements, which do you choose? A uniformly random one? The first one you found? The one which results in the best improvement? A random one chosen in proportion to the improvement? And so on. Each of these could result in a different solution. If you use a randomized strategy, each single run using the same heuristic could result in a different solution, so it makes sense to run local search many times.

An even more drastic option would be to replace local search with *simulated annealing*, which sometimes allows taking a local change which worsens the situation a bit. This might fare better on some instances.

---
Tags: algorithms, traveling-salesman
---


# Question
Title: How "add" could be implemented in only bitshift operations
Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift operators. I'm interested to know what sequence of bitshift operations can reproduce the addition operation.

# Answer
This is impossible, a shift does not combine two operands.
> 3 votes

# Answer
You can partly perform an addition, but the practical interest is definitely null.

A logic circuit can be described as a thruth table.

Consider for instance the truth table of a full adder (sum)

```
a b c | sum=a xor b xor c
0 0 0 | 0
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 0
1 1 1 | 1

```

Shifting can somehow be considered as a way to perform a table lookup.

If we build `v=4*a+2*b+c` and `T=0b10010110`, we can see that the LSB of `T>>v` equals the corresponding entry. So, to get only the corresponding bit, we can do

```
unsigned fulladd_sum(unsigned a,b,c) {
  // note a,b,c must only have their LSB eventually set
  unsigned int as, bs, cs;
  unsigned int T=0b10010110;
  unsigned int sum;
  as=a<<2; bs=b<<1; cs=c<<0;
  sum = ((T >> as) >> bs) >> cs ;
  return (sum <<31) >> 31 ; // to get rid of useless bits
}

```

And we have the sum bit. We can do the same for the carry and process this way successive bits.

The only problem, as already spotted, is that we have no way to combine bits and the result will be spread over several variables representing the successive logic weights of the result.

Concerning the operands, we can have normal operands and extract individual bits by shifting and cleaning (with `((op >> i) <<31) >>31` to get the ith bit).
> 0 votes

---
Tags: computer-architecture, logic, circuits, bit-manipulation
---


# Question
Title: Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:

> For $Σ = \\{a, b\\}$, let us consider the regular language: $$L = \\{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k}, k \geq 0\\}$$ Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$?
>
> (A) 3$\quad$(B) 5$\quad$(C) 9$\quad$(D) 24

---

### My Attempt

I tired to solve like this. I divide the minimum string possible into $x(y^i)z$ that is $a^2$ so getting i value $2$ but option not available.

Then I take second minimum $a^5$ i.e., taking $x=\epsilon$ and $y=a^5$ and $z=\epsilon$.

I am getting $i=5$. So is it correct answer??

# Answer
> I am getting i=5. So is it correct answer?

I am afraid I could not understand your argument and conclusion clearly.

Anyway, can you check if you are able to pump $a^2, a^5, b^{10}, b^{22}$ using the pumping length of your choice?

---

Here are a few results stated in the form of exercises that you can prove and use to solve the problem in the question and beyond.

Assume $L$ is an arbitrary regular language.
**Exercise 1**. Show that there exists $p\_0=p\_0(L)\in \Bbb N^+$ such that $p\in\Bbb N$ is a pumping length for $L$ iff $p\ge p\_0$.
We call $p\_0$ the minimum pumping length of $L$.

**Exercise 2**. Let $L\_{m,n}=\\{a^m, a^{m+n}, a^{m+2n}, \cdots\\}$ for $m,n\in\Bbb N$, $0\<n$. Show that $p\_0(L\_{m,n})=m+1$.

**Exercise 3**. Let $L\_1, L\_2$ are two regular languages. Show that $p\_0(L\_1\cup L\_2)\le\max(p\_0(L\_1), p\_0(L\_2))$

**Exercise 4**. Let $L\_1, L\_2$ are two regular languages over disjoint alphabets that do not contain the empty word. Show that $p\_0(L\_1\cup L\_2)=\max(p\_0(L\_1), p\_0(L\_2))$

**Exercise 5**. Show that 11 is the minimum pumping length of $\\{x\mid x=a^{2+3k} \text{ or } x=b^{10+12k},\ k\ge0\\}$.
> 2 votes

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


# Question
Title: Kosaraju's Algorithm-Strongly connected components
In Kosaraju's Algorithm, using first dfs (traversing on reverse graph) we calculate finishing time of nodes, and then traverse (actual graph) in reverse order of finishing times. why not without reversing graph, using first dfs (traversing on actual graph) we calculate finishing time of nodes, and then traverse (actual graph) in actual order of finishing times. In case my proposed method is wrong please provide me with a counter example.

# Answer
> 2 votes
Consider a graph on $V= \\{a,b,c,d,e,f,g,h\\}$ with edges $ E=\\{ab,ba,cd,dc,ef,fe,gh,hg,be,fh,ad,dg\\}$ wherew $uv$ means an edges from u to v.
Applying your algo:

a valid dfs traversal : a,b,e,f,h,g,h,f,e,b,a,d,c,d,(g already done),a

vertex according to finish time : g,h,f,e,b,c,d,a

scc according to your algo : $\\{g,h\\},\\{f,e\\},\\{b,a,d,c\\}$

correct answer : $\\{g,h\\},\\{e,f\\},\\{a,b\\},\\{c,d\\}$.

# Answer
> 4 votes
What separates theoretical computer science from more applied areas within computer science is the notion of *proof*. If an algorithm claims to do something, we want *proof* that it does so, preferably a mathematical proof. (In rare occasions, experiments are also accepted.) We work under the maxim *an algorithm doesn't work unless it is proved to work*, whereas you seem to be working under the maxim *an algorithm works unless we can find a counterexample*.

For these reasons, I don't find it a good use of my time to find a counterexample. If you did want to find a counterexample yourself, there are several things to try. First, you can try a few random graphs; often this works. Second, you can try to concoct a parametric situation and determine parameters that defat your algorithm; this seems harder to apply in your case since your edges are not weighted, and so the parameters are too discrete. Third, you can try to prove that your algorithm works, fail at some step, and produce a counterexample as part of the process. Fourth, you can play with your algorithm on several graphs until you get an intuitive understanding of what it does, and given this understanding try to construct a counterexample. Fifth, if you really believe that the algorithm doesn't work but can't use any of the preceding method, treat it as a research project and use your research skills to construct a counterexample.

Kosaraju's algorithm is that way that it is for a reason. If a simpler or more intuitive algorithm worked, probably by now people would have discovered it, and it would be known. The fact that we still teach Kosaraju's algorithm suggests that similar but simpler algorithms don't work. That's why I'm pretty sure that your algorithm doesn't work, even without reading it. Of course, I can be wrong. To prove me wrong, all you have to do is to prove that your algorithm works.

# Answer
> 1 votes
For Kosaraju's algorithm to work you need to pick the components in the correct order starting from the sink SCC and work your way backward until you reach the source SCC. so basically you need to start with a node in the sink SCC.

Now let's define two claims

claim1: DFS guarantees that the node with the biggest finishing time will be in the source SCC.

claim2: DFS guarantees that the node with the smallest finishing time will be in the sink SCC.

Kosaraju's algorithm depends on the correctness of claim1. Because when you transpose a graph, the source SCC becomes the sink and vice versa so the node with the biggest finishing time, which is guaranteed by claim1 to be in the source of the transposed graph, must be in the sink SCC of the original graph.

For your modification to work, claim2 (not claim1) needs to be true. A counterexample to claim2 would be any graph where you start the DFS from the node that lies on the edge the connects two SCCs, like any of the examples by emmy.

---
Tags: algorithms, graphs
---


title: VC Dimension of Origin-Centered Circle

text:
# Question
Title: VC Dimension of Origin-Centered Circle
Is the VC dimension of an origin-centered circle 1 or 2?

It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 \<= r2, r2 will never be able to be labeled 1 without r1 also being labeled 1, so the r1 = 0, r2 = 1 labeling could never be possible.

However, this and this both say that an origin-centered circle has VC dimension of 2.

# Answer
> 5 votes
What you are missing is a *definition* of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first link) makes it clear that you can choose whether it is the *inside* or the *outside* of the circle which gets the value +1, and this shows that any two points whose distance from the origin is not the same can be shattered, and so the VC dimension is at least 2.

# Answer
> 1 votes
Assume that the points on the circle are considered inside. With that if you have 2 points at an equal distance from the origin, you cannot label one + and the other -. Either both are in or both are out. On the contrary for 3 points with varying distance from the origin, you can label them +, -, +. This arrangement cannot be shattered. Hence the VC dimension is 2.

Consider the distance as an attribute and +/- as a label. For the same set of attributes, you cannot have a different label.

# Answer
> 0 votes
Why are you excluding the case where the distance is the same? Take any two points with equal distanced from the origin and they cannot be shatters -\> VC is 1

---
Tags: machine-learning, vc-dimension
---


# Question
Title: How to efficiently specify a MILP constraint with nested AND and ORs
Let's say I want to set `x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0`

All of the `x`s are binary variables.

My first thought is I have to add 3 additional variables, let's say `y1, y2, y3` and 12 constraints like this

```
3*y1-x2-x3-x4<=0
y1-x2>=0
y1-x3>=0
y1-x4>=0
2*y2-x5-x6<=0
y2-x5>=0
y2-x6>=0
y3-x7=0
3*x1-y1-y2-y3>=0
x1-y1<=0
x1-y2<=0
x1-y3<=0

```

Is there a more efficient way to tackle this?

# Answer
It can be done with two auxiliary variables, `y1,y2`:

```
x1 >= y1
x1 >= y2
x1 <= y1 + y2

x2 + x3 + x4 >= 3*(y2 - y1)
x2 + x3 + x4 <= 2 + y1 + y2

x5 + x6 >= 2*(y1 - y2)
x5 + x6 <= 1 + y1 + y2

x7 >= y1 + y2 - 1
x7 <= y1 + y2

```

The idea here is that if `(y1,y2) = (0,1)`, then the first and-clause is forced to be true; if `(y1,y2) = (1,0)`, then the second and-clause is forced to be true; if `(y1,y2) = (1,1)`, then the third and-clause is forced to be true; and if `(y1,y2) = 0`, then all three and-clauses are forced to be false.

In other words, `(y1,y2)` represents the index (in binary) of which of the three and-clauses is true; or `(0,0)` if none of them are true.

I would be surprised if it is possible to encode your constraint using only a single auxiliary variable.

This trick can be generalized: if you have an OR of $2^k-1$ AND-clauses, then you can find an encoding that uses $k$ auxiliary variables.
> 2 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: IF A is reduced to B and B belongs to NPC then where does A belongs to?
i came across a question with no proper explnation. IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P. i know why it is as harder as NHP but i am not able to figure out about P class.

according to me if A \> B(A polynomial time reducible to B) and B belongs to NPH then A is as easier as NPC and as harder as NPH. A cannot belong to P since if A belongs to P then then in polynomial time i can solve P and in additional polynomial time i can reduce the results of A to suffice results of B.but as given B belongs to NPH and thus no polynomial time algorithm exists to solve B. which is contradiction to the assumption of A belongs to P. can someone explain what mistake am i making?

# Answer
If A reduce to B and B belongs to NPC, then surely A is in NP, but may or may not be NPC. A belongs to P is another question. If there given P = NP, then A would be belongs in P also.
> 4 votes

# Answer
As G. Bach explained the reduction is just to show the upper bound. If A reduces to B then A can not be harder then B. For example if we had a Hamiltonian cycle and set it up in such a way that if we start from a certain node and follow the cycle we will be able to also sort a group of numbers. then that would mean that sorting can't be harder then finding a Hamiltonian cycle and in fact we can solve it in $O(N\log N)$ but that isn't the point here. we have shown a sorting problem can be reduced to a Hamiltonian cycle and that would mean if we converted a sorting problem to this Hamiltonian cycle we can use a Hamiltonian cycle algorithm to solve it.
> 1 votes

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


# Question
Title: Showing party invitation problem is np-complete
Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P\_i$ of people she would like to have invited to the party. Depending on how much you like housemate $i$, you pick an integer $m\_i$ indicating the minimum number of people on $i$'s list that you'll invite. Having selected these values $m\_i$ already, you'd like to know whether it is possible to invite at most $n$ people to your party such that for each housemate~$i$, at least $m\_i$ of the people in $P\_i$ are invited. We call this the Party Invitation problem. Prove that Party Invitation is NP-Complete.

I am not really sure which problem to reduce from and how to construct the reduction. Thank you

# Answer
> 1 votes
**Simple party invitation problem**. Suppose there are $m$ housemates decide to throw a party. Each housemate $i$ specifies a group of people $P\_i$ who could be invited, $1\le i\le m$. Is it possible to invite at most $k$ people to the party such that at least one person in $P\_i$ for each $i$ is invited?

It is enough to show the simple party invitation problem is still NP-Complete, which is, in fact, true.

Let's try to do some pattern matching between the simple party invitation problem and the set cover decision problem.

In set cover, we are given many sets, and we want to find some sets that satisfy some constraints. In simple party invitation, we are given many persons, and we want to find some persons that satisfy some constraints. Hence it seems that a set among the given sets should correspond to a person that could be invited. (Yes, a set corresponds to a person, which might be counterintuitive and which might be why this problem is not immediate to solve.)

What about the constraints? In set cover, we want to find some sets the union of which will cover all elements. In simple party invitation, we want to find some persons to invite so that every lists of people will be covered, that is, there is at least one person invited in each list. It looks like an element in set cover corresponds to a list of persons in simple party invitation. (Again, an element corresponds to a list, which might not be straightforward and which might be why this problem is not immediate to solve.) The fact that an element is a member of a given set in set cover corresponds to the fact a list of persons contains a given person.

You take it from here.

You could also reduce the hitting set problem to the simple party invitation problem, which might be clearer intuitively if you are familiar with the former.

---

For the pattern matching part, I am following the great teaching style in this answer of Yuval.

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


# Question
Title: How to prove the equivalence of two CFG for balanced parentheses?
Given two CFGs for balanced parentheses.

1. $S \rightarrow SS \mid (S) \mid \epsilon$
2. $S \rightarrow S(S)S \mid \epsilon$

How do I show that they are equivalent?

I have been able to show $ L(2) \subset L(1) $ as follows

$$ S \Rightarrow SS \Rightarrow SSSS \leadsto S(S)S $$

Thus, $ S \leadsto S(S)S $. Keeping production rule $ S \rightarrow \epsilon $, we get $ L(2) \subset L(1) $.

But I can't prove the reverse i.e. $ L(1) \subset L(2) $. Any help would be appreciated.

# Answer
> 4 votes
> But I can't prove the reverse i.e. $(1)\subseteq (2)$.

Indeed, that direction of inclusion is somewhat harder to prove.

---

Let us prove all following 3 context-free grammars are equivalent

* $G\_1$: $S \rightarrow SS \mid (S) \mid \epsilon$
* $G\_2$: $S \rightarrow S(S)S \mid \epsilon$
* $G\_3$: $S \rightarrow (S)S \mid \epsilon$

Proof.

* $L(G\_1)\supseteq L(G\_2)$: $S\Rightarrow\_{G\_1}SS\Rightarrow\_{G\_1}SSS\Rightarrow\_{G\_1}S(S)S\\,.$
* $L(G\_2)\supseteq L(G\_3)$: $S\Rightarrow\_{G\_2}S(S)S\Rightarrow\_{G\_2}(S)S\\,.$
* $L(G\_3)\supseteq L(G\_1)$:

Let $B$ be the language of balanced parentheses, i.e., $$\\{x\in\\{(,)\\}^\*\\}:|x||\_(= ||x||\_) \text { and, }\text{if } f\text{ is a prefix of } x,\\,|f||\_(\ge ||f||\_)\\}\\,.$$ It is immediate to see that $L(G\_1)\subseteq B$ by structural induction.

Let $P(n)$ be the proposition that all words in $B$ not longer than $2n$ are in $L(G\_3)$.

+ $P(0)$ is true since the only word not longer than 0 is $\epsilon$.
    + Assume $P(k)$ is true. Let $w\in B$ with length $2(k+1)$. $w$ must start with left parenthesis, "(". If we count the number of "("s and the number of ")" in $w$ starting from the beginning "(", there will be a time the number of ")"s catches up with the number of "("s. Consider the first time that happens, which must at a ")" in $w$. So $$w=(w\_1)w\_2$$ for some $w\_1,w\_2\in B$. By IH, $S\leadsto\_{G\_3}w\_1$ and $S\leadsto\_{G\_3}w\_2$. Hence $$S\Rightarrow\_{G\_3}(S)S\leadsto\_{G\_3}(w\_1)w\_2=w$$ which shows $P(k+1)$ is true, completing mathematical induction.

All $P(n)$ tell that $L(G\_3)\supseteq B$.

---

**Exercise**. Let $G\_4$ be the grammar $S \rightarrow S(S)\mid \epsilon$. Show that $G\_4$ also generates the language of balanced parentheses.

# Answer
> 2 votes
Let $T = \\{ (, ) \\}$ be the alphabet of terminals and $N = \\{ S \\}$ that of nonterminals. Additionally, let $\Rightarrow\_i$ denote a derivation using the grammar for $L\_i$, $i \in \\{ 1, 2 \\}$.

Let $w \in L\_1 \setminus \\{ \varepsilon \\}$. Then $S \Rightarrow\_1^\ast w$ and $w$ contains at least one pair of parentheses; in order to produce it, the rule $S \to (S)$ must be used somewhere (since it is the only rule which contains parentheses at all). Thus, there is $w\_1, w\_2 \in (N \cup T)^\ast$ and $w\_3 \in L\_1$ with $$S \Rightarrow\_1^\ast w\_1 S w\_2 \Rightarrow\_1 w\_1 (S) w\_2 \Rightarrow\_1^\ast w\_1 ( w\_3 ) w\_2 \Rightarrow\_1^\ast w$$ and such that this is the *first use* of the rule $S \to (S)$. Now, since this is first derivation in which the rule $S \to (S)$ is used, $w\_1, w\_2 \in \\{ S \\}^\ast$ and both were produced by using (only) the other two rules of the $L\_1$ grammar. As a result, $S \Rightarrow\_1^\ast w\_1$ and $S \Rightarrow\_1^\ast w\_2$.

Using induction on the number of pairs of parentheses in $w$ (since $w\_1$, $w\_2$ and $w\_3$ all have at least one pair less than $w$) yields $S(S)S \Rightarrow\_2^\ast w\_1 (w\_3) w\_2 \Rightarrow\_2^\ast w$, as desired.

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


title: SLR parse table and unambiguity

text:
# Question
Title: SLR parse table and unambiguity
If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous?

I think that since we have constructed the parse table which means for every sentence we would be able to decide whether the string will be accepted or not. But I am a little bit confused on whether it is really true or not. Actually, I am trying to prove that a grammar is unambiguous and I constructed parse table with no conflicts.

# Answer
As said in the comment by Yuval, an SLR parse table with no conflicts (or parsing deterministic finite automaton) for a particular grammar implies that the grammar is unambiguous.

In fact, that is true for most if not all popular parsing methods.

* LL(k)
* LR(k)
* SLR(k)
* LALR(k)

Here is the sketch of a proof for all parsing methods. A parse table or a parsing finite automaton specifies an algorithm to produce all leftmost derivations (or rightmost derivations) of the input sentence. If there is no conflict in the parse table or the finite automaton is deterministic, only one derivation can be generated. That means the grammar is unambiguous.

Note for a given sentence, there is only one leftmost derivation is equivalent to there is only one rightmost derivation.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Proving that Every Full Prefix-Free Language is Maximal
I'm practicing a problem where I need to prove that every full prefix-free language is maximal.

I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, where a prefix-free language is full if,

$$\sum\_{x\in A} 2^{-|x|} = 1$$

Furthermore, I know that a language A ⊆ {0, 1}\* is prefix-free if no element of A is a prefix of any other element of A and that the Kraft inequality says that for every prefix-free language A,

$$\sum\_{x\in A} 2^{-|x|} \leqslant 1$$

I'm pretty sure that a full prefix free language is maximal, since it belongs to the maximal prefix-free set. I don't know, however, how to formally prove this. Should I be doing induction with Kraft's Inequality and with what I know about the relationship between maximal and prefix-free sets?

Any help would be appreciated!

# Answer
> 1 votes
Suppose that $A$ is a full prefix-free language, that is, $$ \sum\_{x \in A} 2^{-|x|} = 1. $$ Assume, for the sake of contradiction, that $A$ is not maximal. Then there is a word $y$ such that $A \cup \\{y\\}$ is also prefix-free. According to Kraft's inequality, $$ \sum\_{x \in A \cup \\{y\\}} 2^{-|x|} \leq 1. $$ However, this implies that $$ 1 \geq \sum\_{x \in A} 2^{-|x|} + 2^{-|y|} = 1 + 2^{-|y|} \> 1, $$ and so we reach a contradiction. This shows that $A$ is maximal.

---

The more interesting direction is the converse: if $A$ is maximal then $A$ is full. Let me give two proofs of this fact.

The first proof is by induction on the length of the maximal word in $A$ (note that if $A$ is maximal then it cannot be empty). If $A = \\{\epsilon\\}$ then $A$ is indeed full. Now suppose that $A$ contains some word of positive length. Since $A$ is prefix-free, $\epsilon \notin A$. Hence we can write $$ A = \\{ 0x : x \in A\_0 \\} \cup \\{ 1x : x \in A\_1 \\}, $$ where $A\_0,A\_1$ are prefix-free, and have shorter maximal words. It is easy to check that $A\_0,A\_1$ are maximal: for example, if $A\_0 \cup \\{y\\}$ were prefix-free, then $A \cup \\{0y\\}$ would be prefix-free. Applying the induction hypothesis, we see that $$ \sum\_{x \in A} 2^{-|x|} = \sum\_{x \in A\_0} 2^{-|0x|} + \sum\_{x \in A\_1} 2^{-|1x|} = \frac{1}{2} \sum\_{x \in A\_0} 2^{-|x|} + \frac{1}{2} \sum\_{x \in A\_1} 2^{-|x|} = \frac{1}{2} + \frac{1}{2} = 1. $$

The second proof uses a probabilistic argument, though for the sake of presentation I will present it as a counting argument. Let $A$ be a prefix-free code which is not maximal, and let $n$ be the length of the maximal word in $A$. For a word $x$ of length at most $n$, let $B\_n(x)$ denote all words of length $n$ of which $x$ is a prefix, and note that $|B\_n(x)| = 2^{n-|x|}$. Since $A$ is prefix-free, the sets $B\_n(x)$ for $x \in A$ are all disjoint. Therefore $$ \left| \bigcup\_{x \in A} B\_n(x) \right| = \sum\_{x \in A} |B\_n(x)| = \sum\_{x \in A} 2^{n-|x|} = 2^n \sum\_{x \in A} 2^{-|x|} \< 2^n. $$ Therefore there is some word $w$ of length $n$ which has no word in $A$ as a prefix. So $A \cup \\{w\\}$ is also prefix-free, and we conclude that $A$ is not maximal.

---

Both proofs we presented above actually show the following stronger fact: every prefix-free code is a subset of a maximal prefix-free code. Let me quickly outline how to obtain this result using both proofs.

In the first proof, we prove the claim by induction. If $A = \emptyset$ then we can extend it to $A = \\{\epsilon\\}$, and if $A = \\{\epsilon\\}$ then $A$ is already maximal. So suppose that $A = 0A\_0 \cup 1A\_1$. The induction hypothesis shows how to extend $A\_0,A\_1$ to maximal prefix-free codes $B\_0,B\_1$ (respectively), and then $B = 0B\_0 \cup 1B\_1$ is maximal.

In the second proof, we obtain a maximal prefix-free code by adding to $A$ all words in $$ \overline{\bigcup\_{x \in A} B\_n(x)}. $$

In both proofs, one way to check that the extended code is maximal is by verifying that it is full.

---

For extra credit, the reader can try extending the ideas above to infinite prefix-free codes, that is, prefix-free codes containing countably many words.

# Answer
> 1 votes
It looks like, I am afraid, you have done little useful thinking after a lot of typing. Well, that does happen a lot to me as well when it is about a new field.

---

Let $A$ be a full prefix-free language over alphabet $\\{0,1\\}$, i.e., $$\sum\_{x\in A} 2^{-|x|} = 1\\,.$$

For the sake of contradiction, assume $A$ is not maximal. That is, there exists a word $y\not\in A$ such that $B=A\cup\\{y\\}$ is a prefix-free language. Then

$$\sum\_{x\in B} 2^{-|x|} = 2^{-|y|} + \sum\_{x\in A} 2^{-|x|} = 2^{-|y|} + 1 \>1\\,,$$ which contradicts the Kraft inequality.

Done.

---

Here are several related exercises. Note the alphabet is assumed to be finite.

**Exercise 1**. Show that a full prefix-free language over any alphabet must be maximal.

**Exercise 2**. Show that a maximal prefix-free finite language over any alphabet must be full.

**Exercise 3**. Show that a maximal prefix-free infinite language over any alphabet must be full.

---
Tags: proof-techniques, sets
---


title: Proving existence results

text:
# Question
Title: Proving existence results
I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}\* with both of the following properties:

(i) For all x ∈ A, |x| ≤ 5.

(ii) Every DFA that decides A has more than 8 states.

To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}\* that holds both of these properties?

# Answer
You can prove the existence of an object satisfying properties in many ways. The simplest is to exhibit such an object explicitly, which is what you can do in your case. But there are also other possibilities:

1. Use a probabilistic argument. If you choose a uniformly random graph on $n$ vertices, then it will have no large clique or independent set. We don't know how to construct such graphs explicitly.
Sometimes it is not enough to just choose a random graph. The well-known construction of graphs with high girth and high chromatic numbers modify a random graph so that it satisfies the requirements. A more sophisticated version is the recent interlacing polynomials method, used to construct Ramanujan graphs.
2. Use a non-constructive argument. The is an algorithm that given $n$, determines whether the decimal expansion of $\pi$ contains a block of $n$ zeroes. Indeed, such a program either always returns YES, or it returns whether $n \leq N$, where $N$ is the longest such stretch of zeroes. While we do not at the moment know which of the two options is correct, one of them must be correct, and so the algorithm exists.
3. Use a proof by compactness. Consider the problem of determining whether a graph can be embedded into a torus (without edge crossings). This is a minor-closed family of graphs, and we can consider the set of forbidden minors, i.e., minimal graphs (with respect to the minor relation) not embeddable into a torus. This is an antichain of graphs (with respect to the minor relation), so according to the graph minor theorem, it must be finite. Since we can test whether a graph on $n$ vertices has a given graph as a minor in time $O(n^2)$, it follows that we can determine whether a graph is embeddable in a torus in time $O(n^2)$. But we can't actually construct the algorithm, so we don't know the complete list of forbidden minors.
> 1 votes

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


title: Uniformly random iteration of subtrees

text:
# Question
Title: Uniformly random iteration of subtrees
I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $T$ that is also a tree". For example, a tree $A(B(D, E, F), C(G, H))$ should have 62 subtrees if my math is correct.

The amount of subtrees can be calculated as follows. Let us denote by $R(T)$ the number of subtrees of $T$ rooted at $T$. If $T$ is a leaf then $R(T) = 1$, and if tree has children $T\_1,\ldots,T\_\ell$ then $$ R(T) = \prod\_{i=1}^\ell (R(T\_i) + 1). $$ Finally, the number of subtrees of $T$ is $\sum\_{x \in T} R(T\_x)$, where $x$ goes over all vertices of $T$, and $T\_x$ is the subtree induced by $x$ (consisting of $x$ and all of its progeny).

By shuffling the order of these trees and listing the first 5, the result might be $C(G), A(B(F)), B(D, E), A(B, C), C$.

I can already generate a full list of subtrees. For larger trees, this quickly becomes impossibly large. I am looking for a way of generating these subtrees without having to generate all of them.

One possible method I've thought of is to keep a count of how many unseen rooted subtrees each of the nodes has left, and decrementing each time a subtree is generated from that node. The probability that a node is selected would be weighted by this counter. I would also have to prevent the generation of duplicates. I was wondering if there is a better way.

# Answer
If $k \leq (1-\epsilon) N$, where $N$ is the total number of subtrees, then the following approach would work:

1. Start with the empty list $L$.
2. Repeat $k$ times:

* Pick a random subtree $T'$.
    * If $T' \notin L$, add it to $L$; otherwise, go back to the previous step.

Since $k \leq (1-\epsilon) N$, the expected number of times it takes to find $T' \notin L$ is at most $1/\epsilon$ throughout the process; it will be much smaller in the beginning. In particular, if $k \ll \sqrt{N}$, then it is highly likely that you will never generate the same subtree twice.

In more detail, the average expected number of repetitions is $$ \frac{1}{k} \sum\_{\ell=0}^{k-1} \frac{N}{N-\ell} \approx \frac{N}{k} \int\_0^k \frac{dx}{N-x} = \frac{N}{k} \ln \frac{N}{N-k} \approx \frac{N}{N-k} = 1 + \frac{k}{N-k}. $$

You can implement the check $T' \notin L$ quickly using a hashtable. In this way, we have reduced your problem to that of generating a uniformly random subtree, which you can do as follows, essentially by reducing the problem of uniform generation to that of counting.

In order to pick the root of the subtree, first compute $R(T\_x)$ for every vertex $x \in T$ (you can do this in $O(n)$ for all vertices together if you're careful, where $n$ is the number of vertices). The root is $x$ with probability $R(T\_x)/N$ (you can choose $x$ quickly using binary search, for example).

If $x$ is a leaf, then we're done. Otherwise, suppose that $x$ has children $x\_1,\ldots,x\_\ell$. Your random subtree skips $x\_i$ with probability $1/(1+R(T\_{x\_i}))$ (independently). If it doesn't skip $x\_i$, then you generate a random subtree of $T\_{x\_i}$ recursively.

---

Here are two other related approaches. The first is to generate all subtrees, permute them randomly in $O(N)$, and then output the prefix of length $k$.

A variant of the first approach uses *unranking*. By modifying the approach above, you can take an integer in the range $0,\ldots,N-1$ and convert it to a subtree. This goes as follows. Let $x\_1,\ldots,x\_n$ be an enumeration of the vertices of $T$. The first $R(T\_{x\_1})$ integers correspond to subtrees rooted at $x\_1$. The following $R(T\_{x\_2})$ integers correspond to subtrees rooted at $x\_2$. And so on.

Now suppose we're given an integer $i$ in the range $0,\ldots,R(T\_x)-1$, and need to convert it to a subtree rooted at $x$. If $x$ is a leaf, then there is nothing to do. Otherwise, let $x\_1,\ldots,x\_\ell$ be the children of $x$. We first convert $i$ into $\ell$ numbers $i\_1,\ldots,i\_\ell$, where $i\_j$ is in the range $0,\ldots,R(T\_{x\_{i\_j}})$. If $i\_j = R(T\_{x\_{i\_j}})$, then the subtree won't contain $x\_{i\_j}$. Otherwise, we can generate a subtree of $x\_{i\_j}$ recursively.

Given the unranking procedure, you can generate a permutation of $0,\ldots,N-1$, take the prefix of length $k$, and convert it to a list of $k$ subtrees. If you have any other way of generating a random sequence of $k$ elements of $0,\ldots,N-1$ without repetition, then you can use it in the same way.
> 1 votes

---
Tags: trees, randomness, subtree
---


title: Recursion to DP Solution

text:
# Question
Title: Recursion to DP Solution
There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll incur an operating cost of $N(i)$ if you run the business out of NY; you'll incur an operating cost of $S(i)$ if you run the business out of SF. There is a moving cost $M$ if you decide to switch offices. The goal is to minimize total cost. According to the solutions, a DP solution would look like this:

$$ OPT(i, N) = N(i) + \min(OPT(i-1, N), OPT(i-1, S) + M), \\ OPT(i, S) = S(i) + \min(OPT(i-1, S), OPT(i-1, N) + M). $$

I'm trying to figure out how one can use recursion as opposed to DP to solve this solution. My understanding is that recursion works from top to bottom and DP works bottom up. I'm just having trouble actually figuring out a viable top to bottom recursive algorithm would look like in this case.

# Answer
The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

```
Function OPT(i, site):
    If i = 0, return 0
    If i > 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
    If i > 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)

```

If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

```
Function OPTm(i, site):
    If i = 0, return 0
    If (i, site) in Database, return Database(i, site)
    If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
    If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)
    Database(i, site) = answer
    return answer

```
> 1 votes

# Answer
Yuval's answer shows you how to write a recursive solution.

Here I would like to correct a misunderstanding about dynamic programming in the question that is pretty common.

Although the majority code in programming language that applies dynamic programming uses bottom-up table-filling method, dynamic programming is not bottom up only.

In fact, the thinking phase of dynamic programming is done overwhelming in recursive way. That is, figuring out what are the smaller problems that could contribute and determine the given final or larger problems as well as finding the recurrence relations.

In fact, even if the programming code is written as a recursive solution, that code is still called dynamic programming.

More information can be found in the Wikipedia entry.
> 1 votes

---
Tags: optimization, dynamic-programming, recursion
---


# Question
Title: Maximum product of contiguous subsequence over $\mathbb{R}$
For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).

Let us first show how to solve the problem when the array contains no zeroes:

* If there is a single entry, return the entry.
* If the number of negative entries is even, return the product of all elements.
* Otherwise, let the array be $A\_1,\ldots,A\_n$, let the index of the first negative element be $i$, and let the index of the last negative element be $j$. Return $$ \max \left( \prod\_{k=i+1}^n A\_k, \prod\_{k=1}^{j-1} A\_k \right). $$ (Since $n \> 1$, both sums are non-empty.)

For a general array which is not all zeroes, we partition in into maximal subarrays with no zeroes, apply the preceding procedure to each subarray, and return the maximum over all outputs.

Besides this solution, I also have a dynamic programming solution inspired largely from the problem of maximum sum subsequence that works for positive real numbers but not for negative numbers.

Given an array $A\_1,\ldots,A\_n \> 0$, we compute an array $S\_1,\ldots,S\_n$ such that $S\_i$ is the maximum product of a subsequence of $A\_1,\ldots,A\_i$ containing $A\_i$: $$ S\_1 = A\_1, S\_{i+1} = \max(A\_{i+1}, S\_i A\_{i+1}). $$ The answer is then $\max(S\_1,\ldots,S\_n)$.

I would like to know how to change the first solution to handle general numbers rather than only integers, and to understand how these changes work.

I tried to find a data structure for the problem with floating-point numbers, I thought of using $P\_{\min}$ and $P\_{\max}$ matrices where $P\_{\min\ i, j}/P\_{\max\ i,j}$ is the minimum/maximum product that can be computed from a subsequence in the $A\_i,\ldots,A\_j$ subsequence, but I could not find a recursive relation between the elements of the matrices. I think I found some sort of heuristic method using $P\_{\min}$ and $P\_{\max}$ as vectors that are updated in a single iteration of $A$, each value of $P\_{\min}$ depending on $A$ and $P\_{\max}$, and each value of $P\_{\max}$ depending on $A$ and $P\_{\min}$, but I did not test how adequate it is.

An example of why the first algorithm in my question is not working for floating-point numbers is the input $2, 2, 0.1, 2, 2$.

# Answer
> 4 votes
You can adopt the dynamic programming solution; the other solution looks harder to adapt.

Given an array $A\_1,\ldots,A\_n$, we let $P\_i$ be the maximum positive product of a subsequence of $A\_1,\ldots,A\_i$ containing $A\_i$, and we let $N\_i$ be the minimum negative product of such a subsequence. If no such subsequences exist, we let $P\_i = 0$ or $N\_i = 0$.

Initialization:

* If $A\_1 = 0$ then $P\_1 = N\_1 = 0$.
* If $A\_1 \> 0$ then $P\_1 = A\_1$ and $N\_1 = 0$.
* If $A\_1 \< 0$ then $P\_1 = 0$ and $N\_1 = A\_1$.

Iteration:

* If $A\_i = 0$ then $P\_i = N\_i = 0$.
* If $A\_i \> 0$ then $P\_i = \max(A\_i, A\_i P\_{i-1})$ and $N\_i = A\_i N\_{i-1}$.
* If $A\_i \< 0$ then $P\_i = A\_i N\_{i-1}$ and $N\_i = \min(A\_i, A\_i P\_{i-1})$.

If $\max(P\_1,\ldots,P\_n) \> 0$, then this is the answer. The only way in which this fails to happen is if there is no subsequence whose product is positive. This can only happen if the array contains only negative numbers and zeroes, and every two negative numbers are separated by at least one zero. If there is at least one zero, then the answer is zero. If there are no zeroes, then $n = 1$, and the answer is $A\_1$.

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


# Question
Title: How to evaluate dynamical conditioning/pseudo code
I am having a hard time even to formulate my question, so here it is:

I have an application that the user can go in and define on a webpage the logic one wants to evaluate for the student to comply with:

> Student must take classes (MATH111 OR (MATH101 AND MATH103))

I have an array of all its enrolled classes like:

> \[MATH101,MATH102,MATH123,MATH444\]

How do I evaluate my array on that expression to check if the students satisfies the AND/OR clause?

# Answer
> 1 votes
First, your terminology is unusual. I wouldn't speak about "evaluating an array on an expression", but rather about "evaluating an expression using a variable assignment". Your array is, essentially, a variable assignment stating which boolean variables are true and which are false.

You can represent the expression as a syntax tree, having `AND`/`OR` internal nodes, and variable names `MATH101` as leaves.

Then, you can evaluate the expression simply visiting the tree. In pseudocode:

```
boolean function eval(tree, array):

    if tree is a leaf X:
       return the boolean answering (X in array?)
    else if tree is OR(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 || b2)
    else tree must be AND(t1,t2):
       b1 = eval(t1, array)     # recursive calls
       b2 = eval(t2, array)
       return (b1 && b2)

```

If you want, you can even implement short-circuit evaluation to save some time. If your expressions are short it won't make any difference w.r.t. performance, though.

---
Tags: logic
---


# Question
Title: Trouble understanding theory for error detection and correction in repetition code
## Question 1

Consider a repetition code to **detect** $m$ errors. What is the smallest repetition parameter $k$ (i.e., the number of repetitions per bit) it should be used so that the code can always detect $m$ errors?

To be clear I know that you need $k=2m+1$ to **correct** errors, I am asking what is $k$ if you only want to detect errors. I know the answer is $m+1$.

I read some articles about Hamming codes but I didn't understand the explanation. I also read this post but it wasn't helpful enough: Hamming distance required for error detection and correction

## Question 2

Let a code make 3 repetitions and add a parity bit to the message. For example, $1010$ is encoded as $111 \\; 000 \\; 111 \\; 000 \\; 0$. How many (maximum) errors can this code identify? How many can it fix?

(The answer is fix one and identify three but I don't understand why.)

# Answer
> 1 votes
* **Question 1:** Suppose $k$ is fixed. Then, if any group of repeated $k$ bits is flipped, the error is not detected, so we need $k \ge m + 1$. On the other hand, if $k = m + 1$, then any combination of $m$ errors will be detected because at least $k$ bits must be flipped (i.e, the whole group of $k$ repetitions) in order to arrive at a valid code word.
* **Question 2:** The reasoning is similar. One bit errors can be fixed because of the parity bit. Two bit errors cannot because flipping the parity bit and any other repetition bit yields a word $w'$ with Hamming distance $2$ from the original code word $w$; from it, flipping the other two repetition bits yields a valid code word $w''$ which also has Hamming distance $2$ to $w'$, so the error cannot be corrected. The argument for identifying up to three errors is similar: at least four bits must be flipped to arrive at $w''$ from $w$ (as before), and anything less than that will not yield a valid code word.

---
Tags: coding-theory, hamming-code
---


# Question
Title: Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$
The base scenario is this: We're given a weighted, directed graph $G= (V,E)$, and are tasked to find an approximating algorithm which returns a digraph $G' = (V,E')$ (i.e. which only deletes edges) so that $G'$ is acyclic, and so that the sum of the weights of the remaining edges $\sum\_{e\in E'} weight(e)$ is as big as possible.

Furthermore, the approximation shall be at worst half as good as the optimal solution (i.e. the sum of weights the approximation algorithm returns is at least half as big as the sum of weights of the optimal solution)

This is a homework problem, and I'm looking for hints how to solve it, as I can't seem to figure out any tactic to somehow compare the approximation algorithm ideas to any bound on the optimum solution.

I've come up with 4 ideas of choosing nodes/edges, from which 2 could go arbitrarily bad, and from which I believe 4) has the best chance of succeeding.

So far I have the following results:

1)
Using an algorithm to identify the strongly connected components, I can partition $G$ into a set of subgraphs (one for every strongly connected component), and solve for each subgraph individually (all edges between these subgraphs never create a cycle, and can always be taken into the solution).

2)
Using the tactic to iteratively identify a cycle and remove the one edge of it which has the lowest weight can go arbitrarily bad .

The optimal subgraph $\hat G = (\hat V, \hat E)$ has a topological sorting.
Therefore, there exists a numbering $v\_1,..,v\_{|V|}$ of the nodes so that with $T:= \[v\_1,..,v\_{|V|}\]$, the sum $$\sum\_{j=1}^n \sum\_{ k=2}^j weight(v\_j\to v\_k) $$ is minimal. (The sum represents for each node $v$ in $T$ the weight of all edges $(v,v')$ that is lost because $v'$ appears before $v$ in the list, and thus there mustn't exist an edge $v\to v'$

Therefore, an approximation algorithm might guess the topological sorting of the optimal graph.

3)
Going from left to right, and always picking the node that brings with it the highest weight (as sum of its outgoing edges that are eligible) can go arbitrarily bad.

4)
However, so far I haven't found any counter-example for going from right to left, and always picking the node which loses the least weight.

For the last approach, we can show the following inequality:
Let $T:= \[v\_1,..,v\_{n}\]$ be the result of the approximation algorithm, then holds: $$ \sum\_{k=1}^{j-1} weight(v\_j\to v\_{k}) \le \sum\_{j=2}^n\sum\_{k=2}^j weight(v\_1\to v\_k) = \sum\_{j=1}^{n-1} (n-j)weight(v\_1\to v\_j) $$

# Answer
> 2 votes
First: The upper bound is as stupid as they come: Namely, that at most, the optimal solution contains all edges.

With this upper bound, our approximating algorithm now asserts the following statement:
In every weighted, directed graph $G =(V,E)$ there exists a subgraph $G' = (V,E'), E'\subseteq E$ so that $G'$ is acyclic, and $\sum\_{e\in E'} weight(e) \ge \frac 1 2 \sum\_{e\in E} weight(e)$,
i.e. we can choose the edges in $E'$ so that they accumulate at least half of the weight of all edges in $E$.

To find such a graph $G'$, we enumerate the vertices in $V$ as $x\_1,...,x\_n$, and now create two edge sets using it: $$ E\_1 = \\{(x\_i,x\_j)\in E\mid x\_i\<x\_j \\} \\ E\_2 = \\{(x\_i,x\_j)\in E\mid x\_i\>x\_j \\} $$ Differently put, imagine the graph $G$. Now move the vertices, so that they form the line $x\_1,...,x\_n$ from left to right (while keeping the edges intact).
Now, for $E\_1$, you remove all edges going left.
For $E\_2$, you remove all edges going right.

Each of the corresponding graphs $G\_1 := (V,E\_1), G\_2:=(V,E\_2)$ is acyclic, and $E\_1\dot\cup E\_2=E$, i.e. $E\_1, E\_2$ contain all edges in $E$ exactly once.

Therefore, either $G\_1$ or $G\_2$ has to contain at least half of the edge weight, and thus one of them is the wanted subgraph.

---
Tags: graphs, approximation, dag
---


title: Pseudo Code optimization

text:
# Question
Title: Pseudo Code optimization
**Summary:**

I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip.

**Detail**

So far I have written following:

What I do not like here is:

1. In while loop I am removing one by one elements of $R$ (which is a row vector with $m$ elements). This means the complexity of $m^2$, however I could have sorted $R$ outside the loop and then just removed the head every time that would reduce the complexity to $m\log m + m$ for this part. But in that case the index $j$ will get jumbled up and not usable in the rest of the part. **Is there an elegant Pseudo-code way of saying "store the indices before sorting for later use"?**
2. Any other stylistic suggestions that make it easier to read while still reducing the "implementation complexity" ?

In general, I know its a trade-off between readability vs complexity. Generally, the main purpose of presenting an algorithm is to make it readable and leave the implementation details to the implementer. But just to be pedantic ..

Thanks.

# Answer
> 0 votes
Good questions.

## On algorithm

* "Is there an elegant Pseudo-code way of saying 'store the indices before sorting for later use'?"

Yes. you can write "let $Q$ be the array that includes $(r\_{j}, j)$ for all $1\le j\le m$ sorted by their first entries". Note that $Q$ keeps track of the indices in the second entries of its elements.

What you will code actually is to create an array that has all elements like $(r\_j,j)$ and sort it, where $(a, b)\prec (c, d)$ if $a \< c$. In term of Java, your sort the array of those ordered pairs with a customized comparator. In Python, it is automatic as you can try `a = [(5,1),(7,2),(4,3)]; a.sort(); print(a)`.
* You cannot pull out $t$ from the array $S$ since each element in $S$ is $d\_t$, a primitive value.

What you want is to store the key-value pair $(t, d\_t)$ in $S$. That is, $S$ should be an **associative array**, which is a dict in Python or a Map in Java or std::map in terms of C++.
* "For all $d\_t\in S$, set $d\_t= d\_t+r\_j$".

Since $d\_t$ appears in $S$, "set $d\_t$" could be probably understood as "set the $d\_t$ in $S$" by anyone who has not understood the algorithm before seeing the pseudocode. What you want is to update, I believe the $d\_t$ in $D$ instead of $d\_t$ in $S$.

## On variables

* The name of variables does not make much sense. It is prefered to use the first letter of one related word.
* There is no need to introduce both $R$ and $\[r\_{j}\]\_{1\times m}$. Only one or two labels/variables are used in actual programming code, such as `double[] r = new double r[m];` in Java or `double[m] r;` in C/C++.
* Why considering $\[r\_j\]$ as a $1\times m$ matrix? It is a simple array.

For example, you could write the following naming choices.

* Per Core peak power consumption: $p=\[p\_1,\cdots, p\_m\]$
* Per Core Utilizations: $u=\[u\_1, \cdots, u\_m\]$
* Total time slots in a period: $s$

## How to write pseudocode?

It occurs to me that the pseudocode in the question might be even harder to understand than the actual code had it been implemented in most programming languages that I use.

Whenever you are writing pseudocode, imagine that you are telling the target audience how the algorithm works. Have you made it easier for them to understand the algorithm fully and correctly?

# Answer
> 1 votes
I think it would be perfectly reasonable and normal to present the pseudocode as is, and to mention in the accompanying text that if you sort $R$ in advance, you can implement this algorithm in $O(m \log m)$ time. I think it's pretty clear how to implement the selection step, and you don't need to write out all the indices to explain.

---
Tags: algorithms, time-complexity
---


# Question
Title: If you can represent/model a Conditional IF statement with AND + NOT or OR + NOT
I am still trying to wrap my head around this, which shows how to simulate control-flow without using an `if`-statement.

I've been looking at basic logic today and learned that you can represent all logic with 1 (like NAND), 2 (AND + NOT, OR + NOT, etc.), or 3 logical primitives.

This makes me wonder if you can represent the `if`-statement using just AND + NOT or OR + NOT (and what it might look like), such that a program loop would be able to evaluate an expression such as `if (a) b()`, or something more complex like in the first link above.

# Answer
This is partly possible.

Assume your code is

```
if (a==b)
  x = y;
else
  z = w;

```

where all vars are `int`s

This can be rewritten as

```
c = (a==b) -1 // true 1-1=0; false 0-1=0xfffffffff

x = (~c &  y) | (c & x); // or ~(~(~c&y)&~(c&x)) to only use & and ~
z = (c &  w) | (~c & z);

```

This can be applied to arbitrarily complex expressions, even nested, but **you cannot have function calls**, which seriously limits application area.

Note that this is routinely used to program SIMD extensions like SSE or AVX. In SIMD, you do several operations simultaneously and the only way to perform if-then-else if by mean of masking and anding/oring.

Similarly, there is the same problem on a GPU where hundred of processing elements work simultaneoulsy. It is hidden from the user, but internally the controller transforms if-then-else to logic ops. It even keeps track of it across function calls.
> 3 votes

# Answer
**What you need is a multiplexer.**

In a CPU "If" is evaluated using the ALU (To determine if the argument of "If" is 0), the result of which feeds the select line of a multiplexer. The inputs of the multiplexer are the two possible positions in the code you want to jump to. The output will be the position you do jump to.

You can build a multiplexer from a functionally complete set.

Note: Alain Merigot's solution uses 2 multiplexers.
> 0 votes

---
Tags: computer-architecture, logic
---


# Question
Title: State-elimination on FSA, after epsilon-removal construction
I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.

But there are already some epsilon transitions in this FSA.

My question is:

Should I first follow the epsilon-removal construction, and then do state elimination?

Or can I use state-elimination directly on this FSA?

# Answer
> 0 votes
> Should I first follow the epsilon-removal construction, and then do state elimination? Or can I use state-elimination directly on this FSA?

If you would like to do more work to kill time, or if you would like to check the effect of epsilon-removal construction, or if someone higher on the command chain forces you to (for reasons I have no informed guess about), you should do the epsilon-removal construction before state elimination.

Otherwise, it is perfectly fine to start state-elimination directly and immediately.

By the way, the regular express I got is $$\left(0+(0+02)(2+42)^\*(4+\epsilon)\right)^\*(0+02)(42+2)^\*\\,.$$

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


# Question
Title: Time complexity to find Median of Medians
I recently wrote my Grad school Admission test few days back and the following question appeared in the test.
There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ..., An contains 'n' distinct elements. There are no common elements between any two arrays. The worst case time complexity of computing the median of medians of A1, A2, ..., An is:

1. O(n)
2. O(n log(n))
3. O(n^2)
4. Ω(n^2 log(n))

Approach 1: Compute the median using Counting Sort for all arrays and then store the median values in a separate array. Once again apply Counting Sort on the newly created array having median values and compute the median. Time Complexity = O(n^2) Space Complexity = O(n)

Approach 2: Instead of Counting sort, use any other algorithm with constant space complexity, thereby yielding a total Time complexity of O(n^2 log(n)).

> According to space-time trade-off, a problem or calculation can either be solved in less time by using more storage space (or memory), or by in very little space by spending a long time.

Approach 1 favours time and Approach 2 favours space. I believe that space should be favoured as the size of Array will be very high on performing Counting sort when the range of values is high. Thus I marked Ω(n^2 log(n)) in test. However, my mentor and one my acquaintances say time should be favoured and O(n^2) is the correct answer. So, my question is whether to favour time or space?

# Answer
> 2 votes
The running time of counting sort isn't $O(n)$, in general. If you are guaranteed that every element of the array is an integer in the range $1..n$, then the running time of counting sort is $O(n)$; but if you aren't guaranteed that, in general the running time could be much worse.

Since the question doesn't make any guarantees that the elements of the array will be in a specified range, you can't claim that counting sort will have $O(n)$ running time, and your analysis of Approach #1 is not correct.

Approach #2 does indeed provide an algorithm with running time $O(n^2 \log n)$. However, that's not the best algorithm. There are better algorithms, which can find the median in $O(n)$ time. So, the correct answer is $O(n^2)$ ... but not for any of the reasons listed in your question. See https://en.wikipedia.org/wiki/Selection\_algorithm and Find median of unsorted array in $O(n)$ time.

---
Tags: data-structures, time-complexity, arrays, space-complexity
---


# Question
Title: Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free?
$ L = \\{ww^{R} \in \\{a,b,c\\}^{\*} : |w|\_{a} \not\equiv |w|\_{b} $ and $ |w|\_{b} \not\equiv |w|\_{c} \\} $

I would use the Ogden pumping lemma. Assumption $n \< m$ where $n$ is a number from lemma. My selected word : $ a ^ {m! + m} c ^ {m! + m} b ^ {m} b ^ {m} c ^ {m! + m} a ^ {m! + m} $ where the first $ b ^ {m} $ are the distinguished characters.

It seems to me that it isn't possible to pump this word in any way possible so it isn't contex-free langauge. Have I right?

# Answer
> 2 votes
Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

Intuitively we cannot recognize $L$ using a pushdown automaton as the number of $b$'s has to be used twice, once in comparing against the number of $a$'s and once in comparing against the number of $c$'s. However, that is far from a proper proof.

We can just use the standard pumping lemma for context-free language for a rigorous proof.

For the sake of contradiction, let $p\>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

* $vwx$ contains at least one letter other than $b$.
Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.
* $vwx$ contains only $b$s.
Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}+1$. Then let $s=uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L\\,.$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

---

Here are two related exercises.

**Exercise 1**. Show the following language is not context-free. $$ L = \\{w \in \\{a,b,c\\}^{\*} : |w|\_{a} \> |w|\_{b}\text{ and } |w|\_{a} \> |w|\_{c} \\}\\,. $$

**Exercise 2**. Show the following language is not context-free. (Hint, Ogden's lemma.) $$ L = \\{w \in \\{a,b,c\\}^{\*} : |w|\_{a} \not=|w|\_{b}\text{ and } |w|\_{a} \not= |w|\_{c} \\}\\,. $$

---
Tags: complexity-theory, formal-languages, regular-languages, context-free, pumping-lemma
---


title: Is $T(n^2) = Ω(n)$?

text:
# Question
Title: Is $T(n^2) = Ω(n)$?
According to this link:

> We need the notation for the **lower bound**. A capital omega $\Omega$ notation is used in this case.
>
> We say that $f(n) = \Omega(g(n))$ when there exist constant $c$ that $f(n) \geq c \cdot g(n)$ for for all sufficiently large $n$. Examples:
>
> 1. $n = \Omega(1)$
> 2. $n^2 = \Omega(n)$
> 3. $n^2 = \Omega(n \cdot \log n)$
> 4. $2n + 1 = O(n)$

I need to verify whether $T(n^2) = Ω(n)$. Because I can't seem to think that a quadratic run-time can have a linear lower bound run-time.

I am confused so I might be wrong though.

# Answer
> 2 votes
You haven't said what the function $T$ is, so let me guess that what you need to verify is that $n^2 = \Omega(n)$. Note that this statement has nothing to do with the running time of any algorithm. It is purely a statement about two functions, $n^2$ and $n$.

When trying to prove something, it's always a good idea to use the definition. In order to show that $n^2 = \Omega(n)$, we need to find $c \> 0$ so that $n^2 \geq c \cdot n$ holds for all large enough $n$. I'm sure you can think of such a $c$ that works for all $n \geq 1$.

If you have an algorithm running in time $\Theta(n^2)$, then its running time is also $\Omega(n)$. This just means that the running time is linear *or worse*. In particular, a quadratic running time *always* has a linear time lower bound, just as $2 \geq 1$ holds although $2 \neq 1$.

For more information, check our reference questions on asymptotic notation and on running times and asymptotic notation.

---
Tags: algorithm-analysis
---


# Question
Title: How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?
The theorem states that

$$ H(P)\leq\mathrm{MinACL}(P)\<H(P)+1 $$

where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word length of any Huffman coding and $H$ means the entropy of the probability distribution $P$.

Now, the problem is how to show that for any $\epsilon\>0$, there is a probability distribution $P$ s.t. $\mathrm{MinACL}(P) - H(P)\geq1-\epsilon$?

(I was given a hint that I can start with a source s.t. $H(P)=\mathrm{MinACL}(P)$ and try to change the probabilities in order to skew the code.}

# Answer
You can take the distribution $P(0) = 1-\epsilon$, $P(1) = \epsilon$. This distribution has entropy $h(\epsilon) = O(\epsilon \log 1/\epsilon)$, but $\mathrm{MinACL}(P) = 1$. As $\epsilon$ tends to $0$, the gap tends to $1$, since $\lim\_{\epsilon\to 0} h(\epsilon) = 0$.
> 2 votes

# Answer
Em…… I seem to have figured out how to construct a probability distribution to achieve $\mathrm{MinACL}$ as close to $H(P)+1$ as possible. Suppose, for the information source $(S,P)$ with $|S| = 2^l + 1$, $p\_0 = 1 - \epsilon$, $p\_i = \epsilon/2^l,1\leq i\leq2^l$, a valid Huffman tree could be constructed as follows: First build a full binary tree with $s\_i,1\leq i\leq2^l$, as leaves and then make $s\_0$ sibling of the root of this binary tree, and child of the Huffman tree root node. This scheme can be justified easily given $\epsilon\in(0,0.5)$. Then, $H(P) = -(1-\epsilon)\log(1-\epsilon)-(\epsilon/2^l)\log(\epsilon/2^l)$ and $\mathrm{MinACL}(P) = (l+1)\cdot\epsilon+1\cdot(1-\epsilon)$.

$$ \lim\_{\epsilon\to0}\mathrm{MinACL}(P)-H(P) = 1 $$

(I haven't calculated the limit, but the graph below if of much evidence: )
> 2 votes

---
Tags: information-theory, coding-theory, encoding-scheme
---


# Question
Title: Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$?
I am reading Introduction to Algorithm CLRS (3rd ed.), Chapter 4 (Divide and Conquer), page 78, and am not sure why the explanation of why SQUARE-MATRIX-RECURSIVE algorithm takes $Θ(n^3)$.

> Combining equations (4.15) and (4.16) gives us the recurrence for the running time of SQUARE-MATRIX-MULTIPLY-RECURSIVE: $$ T(n) = \begin{cases} Θ(1) &\text{if } n=1 \\ 8T(n/2) + Θ(n^2) &\text{if } n\>1 \end{cases} $$ As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution $T(n) = Θ(n^3)$.

The part that I don't understand is that why $8T(n/2) + Θ(n^2)$ becomes $Θ(n^3)$. I only see $n^2$ in the term but why would it become $n^3$?

# Answer
> 3 votes
What you are asking is indeed answered in section 4.5 of CLRS using a methodology described later in the book. I will post here an alternative answer you should be able to understand with your current knowledge.

Think of the recursive relationship $$T(n) = 8T(\dfrac{n}{2}) + cn^2.$$

Let us first see what happens if we substitute $T(\dfrac{n}{2})$

$$T(n) = 8 (8T(\dfrac{n}{4}) + c (\dfrac{n}{2})^2) + cn^2 = 8^2 T(\dfrac{n}{4}) + 8c(\dfrac{n}{2})^2 + cn^2.$$

By substituting $T(\dfrac{n}{4})$ we get:

$$T(n) = 8^2 (8T(\dfrac{n}{8}) + c (\dfrac{n}{4})^2) + 8c(\dfrac{n}{2})^2 + cn^2 = 8^3 T(\dfrac{n}{8}) + 4cn^2 + 2cn^2 + cn^2.$$

It becomes obvious that in the general case after $k$ iterations we have:

$$T(n) = 8^k T(\dfrac{n}{2^k}) + cn^2(2^{k-1} + 2^{k-2} + \dots + 2 + 1).$$

Let $n = 2^k$.

Notice that $k = \log\_2n \Rightarrow8^k = 8^{\log\_2n} = 2^{3\log\_2n} = 2^{\log\_2n^3} = n^3$. By substituting $k = \log\_2n$ in the previous relationship we get:

$$T(n) = n^3T(1) + cn^2 (\dfrac{1}{2} + \dfrac{1}{4} + \dots + \dfrac{1}{n})n.$$

$T(n) = n^3 T(1) + cn^3$, therefore you have $\Theta (n^3)$.

# Answer
> 2 votes
Here is a simpler example that could be useful. Consider the recurrence

$$ T(n) = \begin{cases} 1 & \text{if }n = 1, \\ T(n-1)+1 & \text{if } n \> 1. \end{cases} $$

The solution to this recurrence is $T(n) = n$, although the additive term in the recurrence is only $1$.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Find a minimum-weight perfect b-matching, where b is even
How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?

A minimum-weight perfect b-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly b edges from M.

# Answer
A subgraph in which each vertex has degree exactly $b$ is known as a *$b$-factor*. You are asking for something similar (but not identical) to the minimum weight $b$-factor.

Tutte showed how to reduce minimum weight $b$-factor to minimum weight perfect matching in his paper A short proof of the factor theorem for finite graphs.

We will split each vertex $v$ of degree $d(v)$ into $2d(v) - b$ vertices: $v\_1,\ldots,v\_{d(v)},v'\_1,\ldots,v'\_{d(v)-b}$ (we can assume that $d(v) \geq b$, since otherwise the graph has no $b$-factor). We lift each edge $(x,y)$ to an edge $(x\_i,y\_j)$ of the same weight in such a way that each $x\_i$ and $y\_j$ participates in exactly one such edge. We furthermore connect each $v\_i$ to each $v'\_j$ with a zero-weight edge, for all $i \in \[d(v)\]$ and $j \in \[d(v)-b\]$.

Each $b$-factor of the original graph corresponds to a matching in the new graph of the same weight. Indeed, lift the $b$-factor to the new graph, and for each vertex $v$, add an arbitrary matching between $v'\_1,\ldots,v'\_{d(v)-b}$ and the $d(v)-b$ new vertices corresponding to "unused ports".

Conversely, we can convert every matching in the new graph to a $b$-factor of the same weight in the original graph by undoing this construction.
> 2 votes

---
Tags: matching
---


# Question
Title: The number of balanced trees with N node and L leaves
An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the heights of the left and right subtrees is at most 1, and the subtrees are themselves balanced.

I tried to use dynamic programming to calculate the number for the subtrees created from any subsequence of $1..N$. However, without building each possible subtree and calculating its height and differentiating the height of the subtrees from each other, it can't distinguish the balanced subtrees. Moreover, the sum of their leaves must be exactly $L$. There are many constraints, and I couldn't come up an algorithm, either a working nor an optimum one.

Could you please guide me?

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University

# Answer
Suppose $BTC\[H\]\[N\]\[L\]$ shows the number of balanced trees with the height $H$, with $N$ nodes and $L$ leaves. Using the following formula, a dynamic programming algorithm can be developed for the problem:

The recursive part: $\begin{align\*} BTC\[H\]\[N\]\[L\] = \sum\_{h=0}^H\sum\_{n=0}^N\sum\_{l=0}^L \qquad&(BTC\[h-1\]\[n\]\[l\]\times BTC\[h-1\]\[N-n\]\[L-l\])\\ +&(BTC\[h-1\]\[n\]\[l\]\times BTC\[h-2\]\[N-n\]\[L-l\])\\ +&(BTC\[h-2\]\[n\]\[l\]\times BTC\[h-1\]\[N-n\]\[L-l\]) \end{align\*}$

The base cases: $BTC\[h\]\[n\]\[l\]=\begin{cases}0 & \text{if $h\>\log\_2n$ or $l\>\frac{n}{2}$ or $n=0$ or $l=0$}\\ 1 & \text{if $h=0$}\end{cases}$
> 2 votes

---
Tags: algorithms, dynamic-programming, binary-trees
---


# Question
Title: PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of the b's and higher than the amount of c's, so for example the word "abcacba" would be accepted.

# Answer
Note the language where the number of $a$'s is larger than both the number of $b$'s and the number of $c$'s is not context-free, and cannot be accepted by a PDA.

Formally the language can be written as $L = \\{ x\in\\{a,b,c\\}^\*\mid \\#\_a(x) \> \\#\_b(x) \text{ and }\\#\_a(x) \> \\#\_c(x) \\}$.

Intuitively we cannot recognize $L$ using a single pushdown as the count of $a$'s has to be used twice, but in comparing with the number of $b$'s and the number of $c$'s. That is no formal argument, there might be clever tricks avoiding the direct comparison of numbers. Yet there is a possible water tight proof, it uses the pumping lemma for context-free languages.
> 1 votes

# Answer
Let $L$ be the language of words with more $a$'s than $b$'s and $c$'s. No PDA can accept $L$ since $L$ is not context-free.

This answer is a proof for the non-context-free-ness using pumping lemma that is mentioned in Hendrik Jan's answer.

Assume $L$ is context-free for the sake of contradiction. Then there is a $p\ge1$, the pumping length such that every word in $L$ of length no less than $p$ can be written as $uvxyz$ such that $|vxy| \le p$, $|vy| \ge 1$ and $uv^kxy^kz$ is also a word in $L$ for all nonnegative number $k$.

Consider the word $a^{p+1}b^pc^p$ that is in $L$ but "almost not in $L$". Write it as $uvxyz$ as said above. Call $v$ and $y$ together the pumpable part of the word. Since $vxy$ is too short to contain both $a$ and $c$, there are three cases for the pumpable part.

* the pumpable part contains at least one $a$. Then it cannot contain $c$. Pumping down by letting $k=0$ will decrease $a$'s without decreasing the $c$'s.
* the pumpable part contains at least one $c$. Then it cannot contain $a$. Pumping up by letting $k=2$ will increase $c$'s without increasing the $a$'s.
* the pumpable part contains $b$ only. Pumping up by letting $k=1$ will increase $b$'s without increasing the $a$'s.

In all cases, $a^{p+1}b^pc^p=uvxyz$ can be pumped into a word not in $L$. So $L$ does not behave as described by the pumping lemma, which invalidate our assumption that $L$ is context free.
> 1 votes

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


# Question
Title: Find a minimum-weight perfect 2-matching
How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V?

A minimum-weight perfect 2-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly 2 edges from M.

# Answer
From an answer to my other question it turns out that one can convert this problem to standard matching.

Find a minimum-weight perfect b-matching, where b is even

I still wonder whether this would give the most efficient approach?
> 1 votes

---
Tags: matching
---


# Question
Title: Sorting lower bounds for almost sorted array
Can't find a good way to tackle the problem. Would appreciate any help.

$A$ is an $n$ items array from an ordered set, in which every item is at most $\log n $ indices away from its position in the sorted array.

Show that:

1. The array can be sorted in $O(n\log\log n)$.
2. There is a lower bound of $\Omega(n\log\log n)$ for sorting $A$ using comparisons.

The general idea is more important than details for both assertions.

# Answer
> 5 votes
Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A\_i$ to the heap, and pop the minimum element as $A\_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$, this runs in time $O(n\log k)$.

To see that this works, note that the first element in the sorted array must be one of the first $k+1$ elements, and in particular it must be the minimum of these elements. The second element could be any of the remaining elements or the $(k+2)$'th element, and in particular it must be the minimum of these elements. And so on.

For the lower bound, partition $n$ into blocks of length $k$, and consider the set of all permutation which fix each block. The number of such permutations is $$ k!^{n/k} = \[\Omega(k)^k\]^{n/k} = \Omega(k)^n. $$ Hence the number of comparisons is at least $\log \[\Omega(k)^n\] = \Omega(n\log k)$.

---
Tags: data-structures, time-complexity, sorting, comparison
---


# Question
Title: How to find the definition of Computer Architecture terms in Compter Science?
To find the meaning of computer architecture terms in Computer Science do I need to use a Computer Science book? Do I need to find the computer architecture terms in a Computer Science Dictionary or is there a another way of finding the computer architecture terms? If there is another way to find the terms please can you tell me? One example of a computer Architecture term is Memory cell. Another example of a Computer architecture term is Arithmetic Logic Unit.

# Answer
Just use Google. For the specific examples you give, Wikipedia has detailed information: memory cell, arithmetic logic unit. Any computer architecture textbook will also explain these terms.

The internet is full of resources about computer architecture. If Google doesn't give you a good answer, that means the term you were looking for doesn't exist and you used the wrong words.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Alternatives to directly connected networks for representing frequently-updated graphs
What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated, split, joined to other graphs?

Business Context: I am writing a molecule editor in C# and have currently used a directly connected network. By this, I mean each edge maintains direct object references to each node, and each node supports a collection of edges, although this has proven to present problems when updating. I am looking for a better way of doing this.

The model should support

* Adding and removal of nodes
* Adding and removal of edges
* Splitting connected graphs into two separate graphs
* Joining graphs together

**EDIT**: by a 'directly connected network' I imply the following. Vertices are **Atom** objects. Edges are **Bond** objects. Each Atom has a collection of Bonds, and each Bond has a StartAtom and EndAtom. The collections hold object references, so it is possible to directly retrieve the Atoms by calling Bond.StartAtom and Bond.EndAtom. Setting the StarAtom or EndAtom requires that both Bond collections on each atom be update in synchrony.

Also, Atoms and Bonds reside within a Molecule, each being stored in one of two dedicated collections, and each Atom and Bond holds a direct reference to its parent Molecule. Also, Molecules may contain an arbitrary number of child Molecules, and each of these has a reference to its parent.

The major difficulty with this approach is book-keeping. Molecular graphs, when being edited are constantly being updated. A typical operation is to remove a linking bond between to portions of a Molecule, which would split it into two separate Molecules. Or to perform the revers operation, joining the Molecules into one combined Molecules, simply by drawing a bond between two disconnected Atoms.

The current approach is challenging to maintain easily and reliably. When you add the requirement that you must support Undo and Redo then it becomes near impossible. So I am looking for any approaches or design patterns that would simply this task though abstracting the representation. I am currently experimenting with an edge-list approach. I want to know if there are any better ways of doing it.

# Answer
You might be interested to know after all that I settled on an edge-list representation. This allows easy cloning and has loosely coupled nodes and edges, which makes it idea for frequent editing operations.

Thanks for all the help and constructive comments.
> 0 votes

---
Tags: graphs
---


title: Algorithm comparison

text:
# Question
Title: Algorithm comparison
I am learning Big O and Big theta notation and confused the certain case.
I have two functions,
function 1(f1) $$ n * n^{1/2} $$ function 2(f2) $$ 1.001^n $$

in smaller cases (10,000) f1 is much faster than f2, however, it is vice versa for bigger case (10,000,000). For the smaller case, I can say $$ f2 = O(f1) $$ In the bigger case, I can say $$ f1 = O(f2) $$ and I think this case is, $$ f1 = \theta(f2) $$ (If ^ this is wrong, please let me know)
At this case, can I say ?? $$ f1 \equiv f2 $$

# Answer
No, you can't say that, because $O$ doesn't mean "For small inputs, \[something\] happens" and $\Theta$ doesn't mean "For some inputs, one of the functions is bigger and, for other inputs, the other one is." In mathematics, it is essential to use the actual definition of the concepts that you're working with, and to prove that the definition applies in your situation.
> 2 votes

---
Tags: asymptotics
---


title: Polynomial multiplication coefficients

text:
# Question
Title: Polynomial multiplication coefficients
I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific coefficient (or even deciding whether it is 0 or not) of some degree $k$ of the multiplication of an input? It is trivial to see that linear time in k is a must and sufficient as stated by D.W. If one can preprocess the polynomial and query some specific coefficient is there an interesting $o(polynomial-multiplication)$ preprocessing and $o(k)$ per query ?

# Answer
> 1 votes
Yes, there are more efficient ways. If you have two polynomials $p(x)=\sum p\_i x^i$ and $q(x) = \sum q\_i x^i$, then the coefficient of $x^k$ in $p(x) q(x)$ is given by

$$\sum\_{i=0}^k p\_i q\_{k-i}.$$

This can be computed in $O(k)$ time, which is more efficient than multiplying the polynomials and extracting the coefficient of $x^k$.

With preprocessing, you can just multiply the polynomials during the preprocessing phase and store all of the coefficients. Then looking up any desired coefficient can be done in $O(1)$ time.

---
Tags: algorithms, complexity-theory, time-complexity, polynomials
---


# Question
Title: Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither
$ L = \\{ww^{R} \in \\{a, b\\}^{\*} : |w|\_{a} \equiv |w|\_{b} \equiv 0$ $ (mod$ $13) \\} $

Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-free (build a grammar or PDA) else if the language L is not context-free (Prove)

so

We know that $ww ^ {R}$ without any restrictions isn't regular, but it is context-free. but with additional above restrictions $ L = \\{ww^{R} \in \\{a, b\\}^{\*} : |w|\_{a} \equiv |w|\_{b} \equiv 0$ $ (mod$ $13) \\} $ I have no idea how to prove this. I think this language still isn't regular :

Let's take $n, m \> p$ where $p$ is from pumping lemma and $n mod 13 = 0$ and $m mod 13 = 0$ and chose word $s = a^{m}b^{n}b^{n}a^{m}$ and use the pumping lemma that is not regular. Well?

Any idea?

# Answer
Let $$ P = \\{ww^{R} : w\in \\{a, b\\}^{\*} \\} $$ $$R\_a=\\{u\in \\{a, b\\}^{\*} : |u|\_{a}\equiv 0\ (\text{mod}13) \\} $$ $$R\_b=\\{u\in \\{a, b\\}^{\*} : |u|\_{b}\equiv 0\ (\text{mod}13) \\} $$

We know $P$ is context-free.

We know $R\_a$ is regular and $R\_b$ is regular. So $R\_a\cap R\_b$ is regular.

So, $L=P\cap (R\_a\cap R\_b)$ is context-free.

---

**Exercise 1.** (One minute or less) Verify that $L=P\cap (R\_a\cap R\_b)$.

**Exercise 2.** Show that $R\_a$ is regular.
> 0 votes

---
Tags: regular-languages, context-free, finite-automata, pushdown-automata, pumping-lemma
---


# Question
Title: Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1?
I am wondering if there is a log time WBT (weight balanced binary search tree) data structure in which for any node, the sizes of its left and right subtrees diff at most by 1.

PS: I have read through Balancing weight-balanced trees but the weights of subtrees can differ up to a factor of $\Delta$.

# Answer
> -1 votes
Refer the following paper; https://www.researchgate.net/publication/2241064\_A\_New\_Weight\_Balanced\_Binary\_Search\_Tree. It has both bottom-up and top-down restructuring.

---
Tags: binary-trees
---


# Question
Title: Is it possible for a network to have a negative cycle that is not found by the Bellman–Ford algorithm?
I'm struggling to think of such a network. According to the definition I'm working with:

> Given a network $(V, A, w)$.
>
> For all arcs $(u, v) \in A$ :
>
> $\quad$ If $d\[u, |V| - 1\] + w(u, v) \< d\[v, |V| - 1\]$:
>
> $\quad\quad$ Print “Negative cycle!” and stop immediately

To me this implies the only way a negative cycle isn't detected is if all arcs from any $u$ to my $v$ must have a positive weight. How, then, could there be a negative cycle?

# Answer
No, it is not possible. If there is a negative cycle in a network, it will be found by the step 3 of Bellman–Ford algorithm as described by Wikipedia.

Here is the reason given by Wikipedia.

> Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration $i$ that the edges are scanned, the algorithm finds all shortest paths of at most length $i$ edges (and possibly some paths longer than $i$ edges). Since the longest possible path without a cycle can be $|V|-1$ edges, the edges must be scanned $|V|-1$ times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length $|V|$ edges has been found which can only occur if at least one negative cycle exists in the graph.

For more detailed understanding, please read the proof of the correctness of Bellman-Ford as well as finding negative cycles by Bellman-Ford.

---

Here is one easy related exercise.

**Exercise**. Let $e\_0, e\_1, e\_2, \cdots, e\_{m-1}, e\_m=e\_0$ be a negative cycle whose number of vertices, $m$ is the smallest among all negative cycles. Show that it is a chordless cycle.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Type system with subtyping on abstract data types?
Consider this example on binary trees in some ML-like language:

```
type tree =
  | Null
  | Node of tree * tree

let rotate_left p =
  match p with
  | Null -> p
  | Node (a, q) ->
    match q with
    | Null -> p
    | Node (b, c) ->
      Node (Node (a, b), c)

```

In the definition of *rotate\_left* above I only want to consider rotation on trees where the right subtree is also a node:

```
let rotate_left (Node (a, Node (b, c))) =
  Node (Node (a, b), c)

```

In relation to a ML-like type system, this second version of *rotate\_left* is partial where as the first version is total.

Is there a type system expressive enough that such functions would be considered total?

**Note;** I use the term "subtyping" in the title of this question, since I think of the values of the type of the second version of *rotate\_left*, to be a subset of the values of the type of the first version of *rotate\_left*.

# Answer
> 6 votes
You want to write some executable code (`is_left_restartable`) and use it inside a type annotation. This is, by definition, a dependent type.

The problem when you have dependent types is that it's hard to keep type checking usable for a programming language. It's generally desirable to keep the type system decidable, because programmers tend to be annoyed when a programming error causes the compiler to loop forever. So at the very least the type constraints need to stick to a subset of the language that guarantees termination. And of course since type constraints are evaluated at compile time, they can't contain any side effects.

It isn't too difficult to define a subset of the language without arbitrary recursion. For example, just forbid recursive functions. And, to keep things simple, forbid the use of library functions or functions defined in a different module — if you don't do this then library functions need to be annotated, not only so that the type checker knows that they're allowed in types, but also so that the compiler knows what to make of them.

Even if type constraints are in a subset of the language that always terminates, that doesn't make them decidable. For example, if the type constraints can include enough arithmetic to encode addition and multiplication of variables — a context in which this comes up naturally is array lengths — then the type system encodes Diophantine equations and is therefore undecidable. It's possible to keep the system decidable if it only allows additions and not multiplications of variables, as in Dependent ML.

Even when type checking remains decidable, it's a lot harder to keep type inference decidable. That's not a big problem in itself, because programmers who want to benefit from the finer-grained types can just write type annotations. But it can be difficult to precisely define when type annotations are needed and when they aren't. It's still a difficult problem to find a good balance between requiring a lot of annotations, and making it easy for programmers to know when annotations are needed.

When the type constraints are purely defined in terms of pattern matching, as in your example, they can be expressed using generalized algebraic datatypes (GADT). GADT have matured enough to be supported in mainstream languages, notably OCaml. To avoid extensive analysis of which functions are allowed in types, most implementations of GADT including OCaml's use the type system to express constraints, not the term syntax. You would need to define `is_left_rotatable` as a type, and to write a transformation function from matching trees to `is_left_rotatable`.

---
Tags: reference-request, programming-languages, type-checking
---


# Question
Title: Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free
$L = \\{ w : |w|\_{a} \equiv |w|\_{b} \vee |w|\_{c} \equiv |w|\_{d} \\}$

In my opinion complement of the L language is

$L^{C} = \\{ w : |w|\_{a} \neq |w|\_{b} \wedge |w|\_{c} \neq |w|\_{d} \\}$

I choose to Ogden pummping lemma word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p \> n$

I would like to distinguish $c ^ {p}$. And then I have to have at least one distinguished symbol and the rest not distinguished and in my opinion it can't be pumped in any case because i can $c^{p}$ pumped to $c^{p + p!}$ so it isn't context-free

Do I think right?

# Answer
> 1 votes
> I choose to Ogden pumping word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p \> n$.

I am afraid you could not show that Ogden's pumping lemma cannot be applied to $s$ since $s$ belongs to the context-free language, $P\_1=\\{a^{k}b^lc^md^n\mid k\not=l\wedge m\not=n\\}$, which is a subset of $L^C$.

Although your approach does not work, your conclusion that $L^C$ isn't context-free is correct.

---

Well, you are quite near the right approach.

Let $P\_2=L^C\cap L(a^\*c^\*b^\*d^\*)=\\{a^{k}c^mb^ld^n\mid k\not=l\wedge m\not=n\\}$. We can show word $a^{p}c^{p}b^{p+p!}d^{p + p!}$ cannot be pumped as described in Ogden's lemma for $P\_2$ when all of its $a$'s are distinguished. Hence $P\_2$ is not context-free. Since $L(a^\*c^\*b^\*d^\*)$ is regular, $L^C$ cannot be context-free.

---

**Exercise 1.** Show $P\_1$ is context-free. Show $P\_3$ is context-free, too where $P\_3=\\{a^{k}c^md^nb^l\mid k\not=l\wedge m\not=n\\}$.

**Exercise 2.** Show $P\_2$ is not context-free following the approach given above.

**Exercise 3.** Show the complement of the following language is not context-free, $\\{ w : |w|\_{a} = |w|\_{b} \vee |w|\_{c} \not= |w|\_{d} \\}$.

---
Tags: regular-languages, context-free, formal-grammars, pumping-lemma, check-my-answer
---