# Question
Title: Chernoff bound when we only have upper bound of expectation
If $X$ is a sum of i.i.d. random variables taking values in $\\{0,1\\}$ and $E\[X\]=\mu$, the Chernoff bound tells us that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}$$

for all $0\<\delta\<1$.

If $E\[X\]\leq\mu$ instead, does there exist a constant $c$ such that

$$\Pr(X\geq (1+\delta)\mu)\leq e^{-c\delta^2\mu}$$

for all $0\<\delta\<1$?

(This question is related, but the answer there doesn't help.)

# Answer
Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved. A relatively standard form of this kind of tail bound would assume that $$ X = X\_1 + \cdots + X\_n $$ with all $X\_i$ independent, discrete, supported in $\[-1,1\]$, with mean $\mu\_i = 0$, variance $\sigma\_i^2$. The resulting tail bound ends up being that: $$\operatorname{Pr}\[X \> \lambda\sigma\]\le e^{-\lambda^2/4}$$ where $\sigma^2 = \sum\_{i\in \[n\]} \sigma^2\_i$ is the variance of $X$ and $\lambda\in\[0,2\sigma\]$. (Here is a proof by Van Vu.)

I'm more or less going to first reproduce the proof, so you can get an idea of why decreasing the expectation turns out to be ok.

All Chernoff bounds are based on applying Markov's inequality to $e^{tX}$ to get that $\operatorname{Pr}\[X \> \lambda\sigma\]\le \mathbb{E}\[e^{tX}\]e^{-t\lambda\sigma}$. So the general method is to work out $\mathbb{E}\[e^{tX}\]$ and then optimize $t$. We can do the MGF computation a little differently from the link, namely as $$\mathbb{E}\[e^{tX}\] = \prod\_{i\in \[n\]}\mathbb{E}\[e^{tX\_i}\] \le \prod\_{i\in \[n\]}\mathbb{E}\[(1 + tX\_i + t^2X\_i^2)\]$$ where we first used independence of the $X\_i$ and then $e^x\le 1 + x + x^2$ for $x\in \[0,1\]$. Under the hypotheses we started with and linearity of expectation, $$\mathbb{E}\[(1 + tX\_i + t^2X\_i^2)\] = 1 + t^2\sigma\_i^2\le e^{t^2\sigma\_i^2}$$ so we get that $$ \operatorname{Pr}\[X \> \lambda\sigma\] \le e^{t^2\sigma^2 - t\lambda\sigma}$$ With $t = \lambda/2\sigma$ this is what we wanted (and since $t\in\[0,1\]$, all the inequalities we used are valid).

Now let's assume that $\mu\_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses. Returning to the MGF computation, we get $$ \mathbb{E}\[(1 + tX\_i + t^2X\_i^2)\] = 1 + t\mu\_i + t^2\mathbb{E}\[X\_i^2\] = 1 + t\mu\_i + t^2\sigma\_i^2 + t^2\mu\_i^2 $$ Using that $x^2 + x \< 0$ for $x\in (-1,0)$, this implies that $$ \mathbb{E}\[(1 + tX\_i + t^2X\_i^2)\] \le 1 + t^2\sigma\_i^2 $$ and so we get the same tail bound as before.

Finally, note you always have $\sigma^2\_i\le 4$, so $\sigma^2\le 4n$.
> 5 votes

---
Tags: probability-theory, chernoff-bounds
---


# Question
Title: How exactly does a two stack pushdown automaton work?
I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \\{w\\$w\ |\ w ∈ \\{0,1\\}^n\ with\ n\>0\\}$. So far, so good.

Now I know that a 2-PDA works with two stacks and is equivalent to a Turing Machine. It reads from an input tape and can save the current digit in either the first or the second stack. How can I decide in which stack the digit is read and/or saved? Especially since it's a computer program that should deal with that step.

Since it's equivalent to a Turing Machine, I get that one stack can deal with the left side and the other with the right side of the input. However, this is not really enough information for me to write a programm that simulates it. So how does the 2-PDA read the word, for instance, `01001$01001` from language $L$. Where does it begin? How does it accept the word?

I know, so many questions, I don't want to have them answered all in much detail but the most important thing is just how it works.

# Answer
To write a program that simulates a 2-PDA (which will be able to process any transition function $\delta$, not just a particular language) what you need to do is to implement a stack class, with just the operations that it is allowed to have. The simulator is essentially a loop that keeps track of the current state of $\delta$, which has to be stored in a suitable way, and of the current input symbol. You will receive as input the encoding of a function, and the input string.

As for the specific language at hand: the $\\$$ in the middle actually makes it quite easy to design a transition function for this language. Without it, you would have a more difficult (and more interesting) problem. Just push symbols into one of the stacks and wait for the $\\$$ to come up. You can then start using the other stack for the second half of the input string. Pop them both together. If in the process all symbols match, and in the end both stacks are empty, accept.

As you can see, we won't necessarily use the two stacks as if they stood for the content of the tape at each side of the head of a Turing machine.
> 2 votes

---
Tags: turing-machines, automata, pushdown-automata
---


title: context free grammar to NFA

text:
# Question
Title: context free grammar to NFA
I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG,

$$\begin{align\*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align\*}$$

Now correct me if I'm wrong, but if this language has an NFA it means it is regular. But looking at this grammar the language described is $L=\\{a^n cb^{n+k}ca^k\mid n,k\geq 0\\}$. If so, I can use the pumping lemma by taking the promised number $n$, choose the word $a^ncb^{n+k}ca^k$, for $xyz$ we get $x=a^s$, $y=a^t$ ($t\ge1$), then I can pump for $i=2$ and get $a^{n+t}cb^{n+k}ca^k$ which is not in the language. Hence the language is not regular and that means there can't be an NFA for it.

I might have done something wrong but I cant see it. Any suggestions?

# Answer
> 1 votes
You can use the pumping lemma to show that $L$ is not regular and by definition you can't generate NFA. Maybe the question is wrong and they want you to generate a pushdown automaton (PDA).

---
Tags: context-free, regular-languages, automata, finite-automata
---


title: CFG to CNF conversion steps

text:
# Question
Title: CFG to CNF conversion steps
I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions regarding the conversion.

1. Most text books tell us about only two rules $A \rightarrow BC$ and $A \rightarrow a$. But some texts say that starting productions should not be in the right hand side. Why some stress on that rule and others not?
2. When talking about the rules some don't stress much on the condition of removing useless symbols. Is this condition mandatory or not?
3. Which is the best rule? Remove useless production, remove $\epsilon$ production, remove unit production, adjust the resulting productions so as to reflect the CNF rules.
4. Converting a grammar to Greibach normal form requires first converting the productions to Chomsky Normal Form?

# Answer
> 2 votes
1. The definition that my teacher told me about CNF: It is a context-free language whose productions are from two types:

* Type 1: $A \rightarrow a\ |\ A \in N,\ a \in \Sigma$
    * Type 2: $A \rightarrow BC\ |\ A,B,C \in N$

Nothing less and nothing more.
2. You can always simplify a CFL but that is not necessary. At least from a theoretical point of view.
3. There isn't a best rule. Removing useless production is just a way you can polish your CFL.

It is important to notice that when you have $\epsilon$ productions you don't meet the requirements for a context-free grammar so you can't make the conversion to CNF. If you eliminate those productions you are generating a CFG very similar to the original grammar but not equivalent. They denote different languages although the differences can be considered trivial.

Then you mention "remove unit productions" and "adjust resulting productions" these are the steps of the algorithm to convert a CFG into a CNF.

Polishing the grammar could be mandatory in a practical context.

4. I still don't know anything about Greibach normal form so good luck!

---
Tags: context-free, automata
---


# Question
Title: Why is automated theorem proving impossible?
As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output.

Why is it so?

# Answer
We have to be carful here. I think you mean that a program given a formula could not, in general, produce a proof of it or its negation. I can write a program that, given a theorem, will produce it's proof as long as the set of proofs is recursively enumerable. This is not possible in general because of Godel's incompleteness theorem (well that was the first case we knew of). If everything that was true could be proved then we could write a program that enumerated all the proofs until it found the proof of the formula or its negation. However this is not the case as the incompleteness theorem points out. While Godel was the first to prove this was the case the halting problem gives us a nice simple proof that some things are not provable.

The argument goes like this:

Say you have a sound and complete logic for proving the termination of computer programs. The rules of the logic make the proofs recursively enumerable as well. If the logic wasn't sound we wouldn't have to worry about proving anything because false things are already provable; everything falls apart. If it wasn't complete (generally the case) then there would be a true thing that wasn't provable and thus neither you nor the computer could ever prove it. If The proofs were not recursively enumerable then there would be a proof that the program couldn't check to be valid or even reach and thus it couldn't prove the corresponding formula. Now consider the following program:

```
Given a program called pgrm
foreach p in set of proofs //remember, proofs are recursively enumerable
  if p is a proof that pgrm halts
    output that pgrm halts
  if p is a proof that pgrm loops
    output that pgrm loops

```

This program would solve the halting program however so one of our 3 assumptions must be wrong. In practice we work with what we think are sound systems of logic and we work with recursively enumerable sets of proofs as well.
> 12 votes

---
Tags: turing-machines, logic, automated-theorem-proving
---


# Question
Title: How do i find bits in virtual and physical address?
The question is:

```
Consider a virtual address space of 256 pages with page size of 4KB, mapped onto a physical memory of 128 frames.
How many total bits are required in the virtual address?
How many total bits are required in the physical address?

```

I can't figure out how to number of frames is used with the number of pages to find the bits required.

Can someone explain the steps required to solve this problem?

# Answer
> 1 votes
You sound like you're studying for the same finals as me :).

The bits for the virtual address can be calculated as $$\log\_2( page size\ \*\ number\ of\ pages )$$

For the physical the computation is, essentially the same $$\log\_2( page size\ \*\ number\ of\ frames )$$

In this case, 20 and 19 respectively.

---
Tags: computer-architecture, virtual-memory
---


# Question
Title: Application of shortest vertex-disjoint path with time window
I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to move from one origin to its specific destination). This time window will tell us how long it will take for the object to pass a particular point on the network.

These objects should not encounter each other in any ways on the network, so it is a vertex-disjoint path problem with respect to time. For example if I have two objects A and B, and object A will pass node 1 from 10:00 a.m. to 12 p.m., during these time periods object B cannot cross this node, but any time after 12.00 and before 10 (as long as the time window of B allowed) B can pass through node 1.

I want to know if there is any application of this problem in computer science?

# Answer
> 1 votes
Your problem is not clearly defined, but it's likely it can be solved by running a standard algorithm on a longer graph.

If $G=(V,E)$ is your original graph, build $G'=(V',E')$ by making $t$ copies of each vertex in $G$, one per time slot (where there are $t$ time slots): call the copies $v\_1,\dots,v\_t$. Now for each vertex $v \in V$, add an edge $v\_i \to v\_{i+1}$ for each $i$ (this corresponds to an object staying at vertex $v$ throughout time slot $i$). Also, for each edge $(v,w) \in V$, add an edge $v\_i \to w\_{i+1}$ for each $i$ (this corresponds to an object moving from vertex $v$ to $w$).

Now you're looking for vertex-disjoint paths in $G'$. There are standard algorithms for finding vertex-disjoint paths in $G'$ (e.g., using network flow or other methods). If you want a collection of shortest vertex-disjoint paths, that might be possible, but you'll need to define precisely what objective function you want to minimize before we can suggest an algorithm.

---

This general approach can likely accommodate many additional requirements, such as that traversing a particular edge takes a certain amount of time (just use that as the length on the edge), or that we don't know the starting time when each object enters the system (add a source vertex for each object, with edges from the source to each place that the object might enter the system).

---
Tags: graphs, reference-request, shortest-path
---


# Question
Title: Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?
This problem is from Algorithms, problem 2

**The Problem** Given two sorted list of numbers $X$\[1..$n$\] and $Y$\[1..n\]. we need to come up with a O($log n$) time algorithm to find the median of the 2$n$ lists.'

My question is regarding the case where median($X$) is less than the median($Y$).

Here is the proof that the authors(gave) that any element in $X$ less than median($X$) cannot be the median of the two lists.

1. Suppose an element e is in $A$ and e $\lt$ median($X$). Then there will be less than $\frac12n$ elements less than e(in $X$)
2. Since e $\lt$ median($X$) $\lt$ median($Y$) there are less than $\frac12n$ elements less than e(in $B$)

Because of 1 and 2, the median cannot be any element in $A$ that is less than median($A$)

I agree with every step in the proof and with that statement. However, here is the diagram of possibilities where the median of the two lists can be

Based off that proof, I understand why all the elements below the median of $A$ and in $A$ cannot be the median of the two lists. But what justification did author use to eliminate median($X$) as a possibility? It wasn't included in the shaded region.

# Answer
$X\_m$ and $Y\_m$ are not shaded, because each of them *is* potentially the median of $X \cup Y$.

Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array of size $n$):

(1) $X = \\{ 2, 4, 6 \\}$ and $Y = \\{ 3, 5, 7 \\}$.

(2) $X = \\{ 2, 4, 6 , 8 \\}$ and $Y = \\{ 3, 5, 7, 9 \\}$.

I think the caption of Figure 1 is wrong: median of two sorted lists lies in the **unshaded** region.
> 4 votes

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


# Question
Title: Calculating DFT of a specific polynomial
This seems like a simple problem but I'm getting the impression I'm missing something.

**The problem**

Given the values $v\_1, v\_2, \ldots, v\_n$ such that $DFT\_n(P(x)) = (v\_1, v\_2, \ldots, v\_n) $ for $ P(x) = \sum\limits\_{i=0}^k a\_ix^i$ , $k \< n$ - find $ DFT\_{2n}(P(x^2)) $

**My attempt:**

First expand $P(x^2) $ : $$P(x^2) = a\_0 + a\_1x^2 + \ldots + a\_k^{2k}$$ Let's denote by $W^j\_n$ the j'th root of unity of order n. We have : $$ W^j\_{2n} = e^\frac{2\pi ij}{2n} = e^\frac{\pi i j}{n}$$ Using this information, let's evaluate a term p of $P(x^2)$ on some $W^j\_{2n}$ : $$a\_p(x^2) = a\_p(e^\frac{\pi ij}{n})^{2p} = a\_p(e^{2\pi i}) ^\frac{jp}{n} = a\_p$$ (since $e^{2\pi i} = 1$) So, when evaluating any term of the compound polynomial on some unity root of order 2n we get $\sum\limits\_{i=0} ^k ak$ and therefore the final answer is: $$(\sum\limits\_{i=0} ^k ak, \sum\limits\_{i=0} ^k ak,\ldots, \sum\limits\_{i=0} ^k ak)$$

This seems wrong, I don't even use the information about $(v\_1, \ldots, v\_n)$(should the answer be in terms of those?)

Any help would be appreciated.

# Answer
You haven't explained what you mean by the DFT of a polynomial, so I'm assuming you mean the polynomial evaluated at all $n$th roots of unity, that is, $$ v\_i = P(\omega^i), $$ where $\omega = e^{2\pi i/n}$ is a primitive $n$th root of unity. Let now $Q(x) = P(x^2)$, and let $\varpi = e^{\pi i/n}$ be a primitive $2n$th root of unity, $\varpi^2 = \omega$. Let us examine its DFT $w\_1,\ldots,w\_{2n}$: $$ w\_k = Q(\varpi^k) = P(\varpi^{2k}) = P(\omega^k) = v\_{k \mod{n}}. $$ We conclude that the DFT of $Q$ is $$ v\_1,\ldots,v\_n,v\_1,\ldots,v\_n. $$
> 0 votes

---
Tags: algorithms, fourier-transform
---


title: Time complexity of linear program?

text:
# Question
Title: Time complexity of linear program?
I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of nodes $N\_{k+1} \leq 0.5N\_{k}$.

I think this means that the overall complexity should be order $\log N \times T(N)$ where $T(N)$ is the complexity of the FIRST linear relaxation. since the problem size gets at least cut in half each iteration. But there's two issues.

1) The complexity of the inner problem is reduced each iteration, so we're not doing $\log N$ iterations of $T(N)$ complexity, but something like $\sum\_{i=0}^{\log N} T(N/2^i)$ or something. But is this the same as $\log N \times T(N)$ asymptotically or can I tighten my bound?

2) How do I find the complexity of my linear program? I've heard the figure $O(n^{3.5})$ where $n = $ number of variables for interior point methods and $n^3$ for average case Simplex, but I can't find a good source.

# Answer
> 4 votes
Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis is not tight, and in fact you can remove the logarithmic factor: the answer is simply $O(T(N))$.

Answering your second question, the best known time complexity for solving linear programming is given in Yin Tat Lee and Aaron Sidford's recent paper, top of page 43: $$ \tilde{O}\left(\sqrt{\operatorname{rank}(A)}(\operatorname{nnz}(A)+\operatorname{rank}(A)^\omega)L\right). $$ Here:

* $\tilde{O}$ hides logarithmic factors.
* $A$ is the constraint matrix.
* $\operatorname{rank}(A)$ is the rank of $A$.
* $\operatorname{nnz}(A)$ is the number of non-zero entries in $A$.
* $\omega$ is the matrix multiplication constant. The best known value currently, due to Le Gall, is $\omega \< 2.3728639$, but it is suspected that $\omega = 2$.
* $L$ is the bit complexity of the LP, roughly the number of bits in the encoding of the LP (see footnote 2 on page 2 for the exact definition).

The smoothed complexity of the simplex algorithm might be better, but unless your instance is random, smoothed complexity isn't going to help you.

---
Tags: time-complexity, recursion, linear-programming
---


# Question
Title: How to use frame based speech features for learning using a neural network classifier?
I am doing supervised learning on speech audio files using neural networks. For this purpose, I'll have to extract features from the audio file. But since an audio file is a time varying signal, it is generally divided into multiple frames and then features like MFCC etc are extracted from each frame. So how should I encode my feature vector for each training example(audio file) considering that it will be divided into different no of frames(depending on duration of file)?

# Answer
Simple neural network as a structure doesn't have invariance across time scale deformation that's why it is impractical to apply it to recognize time series. To recognize time series usually a generic communication model is used (HMM). NN could be used together with HMM to classify individual frames of speech. In such HMM-ANN configuration audio is split on frames, frame slices are passed into ANN in order to calculate phoneme probabilities and then the whole probability sequence is analyzed for a best match using dynamic search with HMM.

To train HMM-ANN you need a segmentation of speech on states. HMM-ANN system usually requires initialization from more robust HMM-GMM system thus there are no standalone HMM-ANN implementation, usually they are part of a whole speech recognition toolkit. Among popular toolkits Kaldi has implementation for HMM-ANN and even for HMM-DNN (deep neural networks).

There are several more complex types of neural networks that are intended to model sequence data. They fall into class of recursive neural networks where connections have cycles. Recursive neural network can process sequences of features of arbitrary length. RNN systems are state of the art systems these days and you can train very accurate recognition system using them, however, training is not simple. You can check RNN toolkits like CURRENNT.

A case of recursive neural networks are long-short term memory networks. They are state of the art system for speech recognition these days. You can learn more about them from the following publication:

http://arxiv.org/pdf/1303.5778.pdf
> 3 votes

---
Tags: machine-learning, speech-recognition, features
---


title: Is the Euclidean TSP weakly NP-hard?

text:
# Question
Title: Is the Euclidean TSP weakly NP-hard?
So the Euclidean TSP decision problem is NP-complete (see http://dx.doi.org/10.1016/0304-3975(77)90012-3 ) so the TSP optimization problem should be NP-hard.

On the other hand there is a PTAS for the Euclidean TSP (see http://dx.doi.org/10.1145/290179.290180 ).

Wikipedia says that a PTAS is not possible for strongly NP-hard Problems.

So is this a contradiction, or is the Euclidean TSP "only" weakly NP-hard? Did I miss something else?

# Answer
You're confusing a polynomial time approximation scheme (PTAS) and a **fully** polynomial time approximation scheme (FPTAS). Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial increases in degree as 1 / ε decreases. Only an FPTAS is disallowed for strongly NP-hard problems, assuming P $\neq$ NP.
> 4 votes

---
Tags: np-hard, traveling-salesman
---


# Question
Title: Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma
I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular.

My suggestion is as follows:

Assuming $L\in{}REG$, let $p$ be the number that exists for $L$ according to the pumping lemma.

Let $w=ab^{p}ba^{p}$ with $|w|=2p+2\>p$.

Since $w\in{}L$, $w$ can be written as $w=xyz=ab^{p}ba^{p}$, so that:

1. $|xy|\leq{}p$, in this case $xy=ab^{q}$ with $q\leq{}n-1\leq{}p$
2. $|y|\geq{}1$, in this case $y=b^{n}$
3. $\forall{}i\geq{}0,xy^{i}z\in{}L$

But for $i=0$ we have $xy^{0}z=xz=aba^{n}\in{}L$ which violates the definition of $L$, so that $L\notin{}REG$.

Does this constitute a sufficient proof with the pumping lemma or am I at least on the right track? I would appreciate any feedback.

# Answer
It's not sufficient proof because you only proved that if you choose the decomposition $x=ab^q$ and $z$ the rest does not meet the three points of the pumping lemma but remember that the lemma says:

If $L$ is regular then there is a constant $N\>0$ associated to $L$ such that $\forall \sigma \in L$ with $|\sigma|\geq N$ $\textbf{exist}$ a decomposition $\sigma = xyz$ ...

Summarizing. you proved that your decomposition doesn't work. Now you have to try all other possible decompositions.
> 1 votes

---
Tags: regular-languages, pumping-lemma, check-my-answer
---


# Question
Title: How to replace one symbol with two on Turing machine's tape
I want to implement following algorithm on Turing machine:

> rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars

(wikipedia)

But I don't know how to make the replacement "|0" -\> "0||" because it requires 3 cells. Basically I want to insert additional cell or shift all cell symbols from current position to the left(right). Is there a simple way of doing it?

# Answer
The way I'd do it is as follows: The syntax is from the Turing simulator I link to below. It is

```
[transition name],[symbol]
[next transition],[new symbol],[direction]

```

The actual code:

```
name: Binary to Unary
init: moveright2
accept: end

moveright2,_
moveright1,_,>

moveright2,0
moveright2,0,>

moveright2,1
moveright2,1,>

moveright1,_
moveleft,1,<

moveright1,0
moveright1,0,>

moveright1,1
moveright1,1,>

moveleft,_
sub1,_,<

moveleft,0
moveleft,0,<

moveleft,1
moveleft,1,<

sub1,0
sub1,1,<

sub1,1
moveright2,0,>

sub1,_
blankout2,_,>

blankout2,_
blankout1,_,>

blankout2,1
blankout2,_,>

blankout1,1
end,_,>

```

Basically move till you've passed two blanks(Step 1), then write a 1(Step 2), move left till you find a blank(Step 3), treat the number to the left as a binary number and subtract one from it(see below for details on how this works)(Step 4), Then repeat steps 1-4 until you can't subtract any more(in my case the subtract routine turns all 0's in the number we've been subtracting from to 1 and then hits a blank), go back turning all ones to blanks till you hit a blank, then go one farther turning that one into a blank.

It turns 101 into 11111

Subtraction routine, start at the far right of the number, if it's 0 change it to one and move left doing the same thing to each digit you come across, if it's one see step 1
> 3 votes

# Answer
Hint: $1101\_2 = 11111111\_1 * 1 + 1111\_1 * 1 + 11\_1 * 0 + 1\_1 \*1$

At each step you will erase the rightmost digit of your input. In case it's a $1$, just add (concatenate) its multiplier (already in unary) to the result. Update the multiplier, repeat.
> 1 votes

# Answer
It can be shown that allowing Turing machines the ability to insert characters in the tape doesn't increase their power. But, in this case, it's easier just to not do the replacement in-place. That is, writing `-` for the blank symbol, if your initial tape contents is

```
101------------ ...

```

then the result would be

```
---|||||------- ...

```
> 1 votes

---
Tags: turing-machines
---


title: Simulating a combinatorial network

text:
# Question
Title: Simulating a combinatorial network
I have various Boolean functions in the sum of products format. I "convert" these via combinatorial logic synthesis into a combinatorial network as an And-Inverter Graph - therefore this network only consists of 2-input, 1-output And-Gates and inverters. Every sum of products function is therefore "responsible" for a certain single output. The network is a multi-input and multi-output network, in- and outputs are Boolean (0 or 1). This network is also parsed as file, so it can be read from.

I know, that such a network can be proven to be correct, but I want to simulate this combinatorial network with certain inputs. My problem is, that I only find ways to simulate a sequential network - nothing for combinatorial networks. SAT-provers might be helpful, but because of the nature of this network and its functions, I already know the functions are satisfiable. I need to know, what output will be generated using certain inputs.

Is there any way to simulate and test a combinatorial network with certain inputs and save the outputs? I know there a SAT-provers out there, but I don't think I can really use those, as I need specific outputs and the Inputs have to be in a specific order. Logic Simulation might be the way to go, as the network is derived from Boolean functions, but I didn't find a way to simulate this network via anything.

Short Example: Network is some sort of adder, 4 inputs, 5 outputs. I then go through the inputs (0000, 0001, 0010, ...) and save the outputs of the network. I can't compare the outputs to a tables of "expected" outputs, because I don't know what the outputs will be (I only know them for certain test cases - the network probably won't be as easy as an adder).

Is there any way to simulate a network like this?

# Answer
Yes. Simulation is straightforward and doesn't require any special ideas: it can be done directly, by just executing the circuit one gate at a time.

The algorithm to simulate a combinational circuit is completely straightforward. Given a combinational circuit $C$ and an input $x$, it is easy to compute the output $y=C(x)$, simply by simulating each gate, one gate at a time. Each gate in the combinational circuit is either an AND gate or an inverter. Both can be implemented in software. So, to simulate such a circuit, you just iterate through the gates in topologically sorted order, compute the effect of each gate, and store the value of its output wire. This is a trivial, linear-time algorithm. There's no need for SAT solvers or anything fancy like that.

Of course, when you compute the output of the circuit on some input, it's straightforward to save the output anywhere you like. If you only want to test the circuit on certain inputs, just do that. If you want to compare the output of the circuit to the known-correct output, you can do that: it's just an equality test.

---

Alternatively: A combinational circuit is a special case of a sequential circuit. A sequential circuit is allowed to have both combinational logic and memory (e.g., registers). A combinational circuit is the special case where you have no memory (e.g., no registers). So, in principle any method for sequential circuit simulation already provides you a way to simulate combinational circuits.
> 1 votes

---
Tags: simulation
---


# Question
Title: Seeking Efficient Approximation Algorithm for Adaptation of TSP
Consider the following adaptation of the traveling salesman problem:

> Given a complete, undirected graph $G$ with nonnegative edge weights, color each vertex either red or blue. Find the shortest path that visits all vertices exactly once (does not need to return to starting vertex), but does not visit vertices of the same color more than 3 times in a row (i.e. the path
>
> $$red \to blue \to blue \to blue \to red$$
>
> is valid but
>
> $$red \to blue \to blue \to blue \to blue$$
>
> is not. Assume that there are the same number of red and blue vertices.

I'm trying to come up with an algorithm to at least *approximate* a shortest path given this constraint. My initial thought was the following (besides simply trying all $|V|!$ different paths):

**Greedy Approach:** Choose a starting vertex $v\_0$ and at each step, simply choose the vertex $v\_1$ that minimizes $d(v\_0, v\_1)$. However, keep a record of the colors of $v\_{i}$, $v\_{i-1}$, and $v\_{i-2}$ at each step, and if the optimal choice of the next vertex $v\_{i+1}$ violates the color constraint, choose the next best vertex.

The only problem I see with this is that you can 'run out' of vertices of a given color. That is, you could reach a point where there are more than $3$ vertices remaining, but they are all of the same color. This would make it impossible to complete the path.

**My Question**: Does anyone have any suggestions on algorithms to try? Maybe a modification to my suggested greedy approach to make it complete, or another paradigm all together?

*(I know that this problem is $NP$-complete - that's why I'm seeking an approximation algorithm.)*

# Answer
Since this is your exercise, it sounds like you are only looking for a hint or an approach. So, here is a hint/approach.

Let $M$ be a DFA (deterministic finite-state automaton) that recognizes all legal sequences of colors, where a sequence is legal if it doesn't contain the same color three times in a row.

Construct a new, bigger graph $G'$, formed by a "product construction" of $G$ and $M$. The number of vertices in $G'$ will be at most the number of vertices of $G$ times the number of states of $M$, so $G'$ will be bigger but not too much bigger.

Now think about what you can do with this $G'$. Try translating your original problem into some question about $G'$.
> 1 votes

---
Tags: algorithms, np-complete, approximation, traveling-salesman
---


# Question
Title: What is the size of a queue associated with a resource when the resource becomes a bottleneck?
In Software Performance and Scalability: A Quantitative Approach - Henry H. Liu, the author is presenting a scenario where the hardware becomes a bottleneck. In one ot the tests, he is checking the number disk (read/write) operations. In particular, the number of disk writes as the number of threads increases (see figure below).

After this, he states that: "A rule of thumb is that a resource is a bottleneck when the queue length associated with it is over 2 per unit. Since the RAID 0 configuration used for this test had four disks, the threshold would be 8. This threshold of 8 had been exceeded with a write average queue length of 20 with 4 threads. With 16 threads, the associated average write queue length even went up to 132, which was over 16 times the threshold value of 8. It is clear that the system was disk write bottlenecked."

My question is: **Why a resource is a bottleneck when its queue length is over 2?** Why is not over 1? why is not over 1000000? why 2?

# Answer
> 2 votes
He explicitly says it's a rule of thumb. That means it's not a hard-and-fast rule; it is just a guideline that is often helpful (but no guarantees). While I'm not familiar with that textbook, I suspect that justifying this rule of thumb would likely require concepts that are beyond the scope of that book.

If you want to understand where it is coming from, one approach is to try some simulations and see what happens. That will give you a rough feeling for it.

If you want to understand the mathematics behind it, your next step is to study queuing theory. There is a relationship between the average queue length and the average utilization of a resource. When queues get large, that tends to mean that the arrival rate is close to or exceeds the departure rate, and means that the resource is highly utilized. In the kind of setting talked about in the book, this in turn means that the resource is a good candidate to be a bottleneck.

---
Tags: distributed-systems, performance, queueing-theory
---


# Question
Title: Represent an octree as a binary tree of thrice the depth?
In an octree, each node has up to eight child nodes. This can be implemented with eight pointers per node that are set to null pointers if the child is not used. Another implementation uses a byte as bit-mask that stores which children are used and a pointer to the first child. The children are stored consecutively then.

I'm interested in ray-tracing of sparse voxel octrees, so finding the first intersecting leaf with a ray is the main operation on the tree.

To simplify current implementations, I wonder whether it would make sense to represent an octree as binary tree that at each node bisects the space exactly in the middle. The depth layers would alternate between the three possible orientations of the cutting plane. So three levels of the binary tree correspond to one level in an conventional octree.

1. YZ-plane (root)
2. XZ-plane
3. XY-plane
4. YZ-plane
5. ...

This is similar to the idea of k-d trees, which are binary trees for space partitioning as well. However, they store cutting planes with the nodes to allow for uneven partitioning.

Is there a difference between the octree and a binary tree of three times the depth, or are they equivalent? If there is, why is the octree used more commonly? I haven't found any reference of someone using the explained binary tree for space partitioning. Maybe I'm just missing the correct term for it though.

# Answer
> 2 votes
They're very similar, as you say. Their asymptotic running time is equivalent; the difference in running time and space usage is at most a small constant.

However, in practice, constants can matter. In practice, the octree might perform better, due to its better memory locality. If the depth of the octree is $d$, the depth of your corresponding binary tree will be $3d$. That means looking up an element requires three times as many pointer indirections in your binary tree. Pointer indirections are expensive because they typically cause a miss in the cache (they cause random access to memory, which is the worst case for memory hierarchies). Consequently, in practice, it's possible that the binary tree implementation might be up to three times slower than the octree, due to the increase in cache misses and the poorer memory locality.

Of course, the only way to know for sure is to implement and measure on some benchmarks. But this is one plausible reason why octrees might be preferable in practice.

---
Tags: data-structures, trees, space-partitioning
---


# Question
Title: Weighted interval scheduling with m-machines
I am looking for some advice and direction on solving the **weighted interval scheduling problem with $m$-machines** to plan some experimental "wet lab" procedures.

The problem is very similar to the standard weighted interval scheduling problem described but with the important difference that more than 1 'machine' can be used.

The problem has the following specifics:

* There can be a fixed number of machines (e.g. 2 machines)
* The machines can be run in parallel and are identical.
* No machine can be assigned to two overlapping intervals
* The inputs are a list of intervals with start time, stop time and a weight (score). And the number of machines available
* The output is a schedule for each machine consisting of a subset of the intervals, whose weight is maximal.

I can find some great explanations as to how weighted interval scheduling can be solved with 1 machine (python tutorial). And how interval scheduling can be solved on \>1 machine when **not** weighted (interval scheduling with \>1 resource)

## Approach attempted

As far as I can tell, the Dynamic programming approach solve the weighted interval scheduling problem is widely used.

1. For every interval j, the rightmost mutually compatible interval i, where i \< j I is a sorted list of Interval objects (sorted by finish time)
2. Use dynamic algorithm to schedule weighted intervals
3. Trace-back recursively to get the subset of intervals

These steps are explained in detail here and here.

The most simplistic way I could think of would be be to perform an algorithm for 1 machine, like the algorithm described in the python tutorial, then repeat the algorithm with the previously scheduled items removed.

## Example data

Data consists of interval id, start time, end time and weight (1, 0, 3, 3) (2, 1, 4, 2) (3, 0, 5, 4) (4, 3, 6, 1) (5, 4, 7, 2) (6, 3, 9, 5) (7 , 5, 10, 2) (8 , 8, 10, 1)

The intervals would like this if sorted by descending finishing time:

If $m$ = 2, i.e. I have 2 machines.

If I do the approach described in the python tutorial for machine 1 I get the optimum schedule of items: 3 (weight 4) and 7 (weight 2) = total weight 6. (which seems strange as it is not the maximum weight that can be obtained)

For machine 2, I then repeat this with the items 3 and 7 removed. The resulting schedule would then be: 1 (weight 3) and 6 (weight 5) = total weight 8.

See attached for Python code used (modified slightly from the python tutorial).

```
import collections
import bisect
import time
from datetime import datetime

class Interval(object):
    '''Date weighted interval'''

    def __init__(self, title, start, finish, weight):
        self.title = title
        self.start = start
        self.finish = finish
        self.weight = weight

    def __repr__(self):
        return str((self.title, self.start, self.finish, self.weight))

def compute_previous_intervals(I):
    '''For every interval j, compute the rightmost mutually compatible  interval i, where i < j
       I is a sorted list of Interval objects (sorted by finish time)
    '''
    # extract start and finish times
    start = [i.start for i in I]
    finish = [i.finish for i in I]

    p = []
    for j in xrange(len(I)):
        i = bisect.bisect_right(finish, start[j]) - 1  # rightmost interval f_i <= s_j
        p.append(i)

    return p

def schedule_weighted_intervals(I):
    '''Use dynamic algorithm to schedule weighted intervals
       sorting is O(n log n),
       finding p[1..n] is O(n log n),
       finding OPT[1..n] is O(n),
       selecting is O(n)
       whole operation is dominated by O(n log n)
    '''

    I.sort(lambda x, y: x.finish - y.finish)  # f_1 <= f_2 <= .. <= f_n

    print I
    p = compute_previous_intervals(I)

    print p

    # compute OPTs iteratively in O(n), here we use DP
    OPT = collections.defaultdict(int)
    OPT[-1] = 0
    OPT[0] = 0
    for j in xrange(1, len(I)):
        #print j
        OPT[j] = max(I[j].weight + OPT[p[j]], OPT[j - 1])
        #print OPT[j]
    print OPT
    # given OPT and p, find actual solution [intervals in O(n)
    O = []

    def compute_solution(j):
        if j >= 0:  # will halt on OPT[-1]
            print "start", j,  I[j]
            if I[j].weight + OPT[p[j]] > OPT[j - 1]:
                #print I[j].weight + OPT[p[j]], "greater than",  OPT[j - 1]
                O.append(I[j])
                #print I[j]
                compute_solution(p[j])
            else:
                #print I[j].weight + OPT[p[j]], "not greater than",  OPT[j - 1]
                compute_solution(j - 1)

    compute_solution(len(I)-1)

    # resort, as our O is in reverse order (OPTIONAL)
    O.sort(lambda x, y: x.finish - y.finish)

    return O

if __name__ == '__main__':
    I = []
    I.append(Interval(1 , 0, 3, 3))
    I.append(Interval(2 , 1, 4, 2))
    I.append(Interval(3 , 0, 5, 4))
    I.append(Interval(4 , 3, 6, 1))
    I.append(Interval(5 , 4, 7, 2))
    I.append(Interval(6 , 3, 9, 5))
    I.append(Interval(7 , 5, 10, 2))
    I.append(Interval(8 , 8, 10, 1))

    print I

    O = schedule_weighted_intervals(I)
    print "subset = ", O

```

# Answer
If the number of machines is a small constant, then the problem can be solved in polynomial time. In particular, if you have $m$ machines and intervals, the problem can be solved in $O(n^{m+1})$ time using dynamic programming.

If $m$ is part of the input, the problem might be NP-hard. In this case, I suggest you take a look at the general approaches mentioned in Dealing with intractability: NP-complete problems. If you want an exact optimum solution, I suggest trying to formulate this as an integer linear programming (ILP) problem or as a SAT instance. If you want a heuristic, a greedy algorithm might be a reasonable starting point.

For instance, here is how you can formulate this problem as an ILP instance. Introduce zero-or-one variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ means the $i$th interval is assigned to machine $j$. Now add the following constraints / linear inequalities:

* Each interval is assigned to at most one machine:

$$\sum\_j x\_{i,j} \le 1.$$
* No pair of overlapping intervals are assigned to the same machine:

$$x\_{i,j} + x\_{i',j} \le 1,$$

for all pairs $i,i'$ of overlapping intervals.

Now maximize the objective function $\sum\_{i,j} c\_i x\_{i,j}$, where $c\_i$ is the weight of the $i$th interval. Then feed this to an off-the-shelf ILP solver (e.g., lp\_solve, CPLEX, etc.).

If you want a greedy approach, here is the obvious approach. Sort the intervals by decreasing "bang-for-the-buck", where the "bang-for-the-buck" of an interval is its weight divided by its length. Consider the intervals in that order. When you consider an interval, if there is a machine that's available for that entire interval, schedule the interval on that machine; otherwise, skip that interval. Proceed until you have considered all the intervals.
> 3 votes

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Minimize Deterministic Finite Automata with no accepting states
I have a finite automaton with no final/accepting states, so F is empty. How do I minimize it?

I got this on a test and I didn't know how to approach the problem because the automaton had no accepting states. Is a single initial state with all the transitions into itself the correct answer?

# Answer
Your guess is correct and you can see it a little bit more formally as follows. Let $\mathcal{A} = (Q, A, \cdot, q\_0, F)$ be a DFA. The Nerode congruence $\sim$ on $Q$ is defined as follows: $$ p \sim q \text{ if and only if, for every word $u \in A^\*$, }\ p \cdot u \in F \iff q \cdot u \in F $$ The set of states of the minimal automaton of $\mathcal{A}$ is $Q/{\sim}$. Now if $F$ is the empty set, all the states of $Q$ are $\sim$-equivalent and thus $Q/{\sim}$ has only one element, say $Q/{\sim} = \\{1\\}$. You have no choice for the transitions and thus $1 \cdot a = 1$ for each letter $a$. Finally $1$ is the initial state, but there is no final state.
> 6 votes

# Answer
A finite automaton without end states denotes the language L = $ \emptyset $ . To minimize a DFA we minimize the number of states and the denoted language must be the same. By definition of DFA we must have an initial state $ q\_0$ so $| Q | \geq 1$ and as you say we need to include the transition function with all transition into $ q\_0 $ (because creating dead states is counterproductive).
> 7 votes

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


# Question
Title: Proving the set of finite languages is countable without using the union of countable sets
The list of finite languages over a finite alphabet is countable.

I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I can prove that the infinite union of countable set is countable.

However, I am sure that there is a simpler proof. Can someone help?

In my example $|\Sigma=\\{0,1\\}|$

# Answer
> 7 votes
Let your finite alphabet be $\Sigma = \\{a\_1, \dots, a\_\ell\\}$ and let $\\#$ be some character not in $\Sigma$. Let $L=\\{w\_1, \dots, w\_n\\}$ be a finite language over $\Sigma$. You can consider the string $\\#w\_1\\#w\_2\\#\dots\\#w\_n$ to be a number in base $|\Sigma|+1$ by associating the symbols $a\_1, \dots, a\_\ell, \\#$ with the base-$(|\Sigma|+1)$ digits $0, \dots, \ell-1, \ell$, respectively (starting the string with $\\#$ ensures that the leading digit isn't zero). This gives a map from the set of finite languages over $\Sigma$ to a subset of the integers, so that set of languages is countable.

# Answer
> 3 votes
Let $A$ be a finite alphabet and let $\<$ be a total order on $A$. For instance, if $A = \\{a,b,c\\}$, let $a \< b \< c$. Then order the elements of $A^\*$ according to the *shorlex order*: $u \leqslant v$ if either $|u| \leqslant |v|$ or $|u| = |v|$ and $u \leqslant\_{lex} v$, where $\leqslant\_{lex}$ is the usual lexicographic order. For instance, if $A = \\{a, b\\}$ and $a \< b$, you obtain the following sequence of words: $$ 1, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, \ldots $$ Let $r(u)$ be the rank of a given word $u$ in this sequence. The map $u \to r(u)$ defines a bijection from $A^\*$ to $\mathbb{N}$.

Now you want to get an injection from the set $\mathcal{P}\_f(A^\*)$ of all finite languages on $A^\*$ into $\mathbb{N}$. Denote by $p\_n$ the $n$-th prime number. Then the map $f: \mathcal{P}\_f(A^\*) \to \mathbb{N}$ defined, for each $L = \\{u\_1, ..., u\_n\\}$, by $$ f(L) = p\_{r(u\_1)}p\_{r(u\_2)} \dotsm p\_{r(u\_n)} $$ is injective.

N.B. As you can see, this construction does not use the full power of the prime numbers, and it can be modified to get a bijection from the set $\mathbb{N}\langle A\rangle$ of *polynomials over $A$* to $\mathbb{N}$. A polynomial over $A$ (with coefficients in $\mathbb{N}$) can be written as a formal sum, like $$3ab + 2bb + 5bab.$$ Now if $F = k\_1u\_1 + \dotsm k\_nu\_n$, where $k\_1, \ldots, k\_n \in \mathbb{N}$ and $u\_1, \ldots, u\_n \in A^\*$, one extends $f$ by setting $$ f(L) = p\_{r(u\_1)}^{k\_1}p\_{r(u\_2)}^{k\_2} \dotsm p\_{r(u\_n)}^{k\_n} $$ and it is now a bijection from $\mathbb{N}\langle A\rangle$ to $\mathbb{N}$.

---
Tags: turing-machines
---


# Question
Title: Where to learn about Short-circuit evaluation?
I would like to implement short circuit evaluation logic in my code. And I want to know about the full details how it works?

**Ex:**

function a() {return true;}

function b() {return false;}

function c() {return true;}

**Expression**

Case 1) a() && b() && c();

Case 2) a() || b() && c();

Case 3) a() && c() || b();

Case 1:

b() will not be executed.

Case 2:

b() and c() will not be executed

Case 3:

c() will not be executed.

Where should we learn about this `short-circuit evaluation`?

# Answer
Short-circuit evaluation is based on lazy-evaluation (call-by-need evaluation) of the arguments of some function or operator. This is all described in various wikipedia articles.

The idea is that the function call defers requesting evaluation of its arguments until they are actually needed, possibly never evaluating them if the computation may proceed independently of their value.

The expression "short-circuit evaluation" has been used mostly, at least initially, for boolean operations. For example, a conjunction (`&&`) will always return false, if one of the arguments is false. So if the first argument evalates to false, there is no need to evaluate the second.

But it is is true, and the second is false, you would think that it was not necessary to evaluate the first. This is correct, but there is not much you can do about it. You have to start with one of them, and the order is usually taken from left to right. So you may start with one that was not necessary.

Thus short-circuit evaluation also has the implicit idea that there is an order of evaluation, and that an argument is not evaluated if previously evaluated arguments show it is not needed.

Similarly, for a disjunction (`||`), if the first argument evaluates to true, there is no need to know the second argument to know the end result: true.

The `if ... then ... else ...` conditional, seen as an operator (I am skipping details) is always evaluated in short-circuit, skipping the second or third argument evaluation depending on the value of the first.

The concept can be extended to arithmetics, for example by not evaluating $b()$ in $a()\times b()$ when $a()$ evaluates to $0$.

Short-circuit evaluation does not change the end-result of a program, under the consition that evaluation of arguments has no side-effect. However, it may save on computation time, to such an extent that some programs terminate with short-circuit evaluation, that would not terminate without it. This is typically the case if an argument that is ignored would otherwise cause an infinite computation (there is also the case where it would cause a run-time error, but this may be considered a side-effect).

In your example (assuming as usual left associativity), your answers are incorrect.

For example, considering case 1: `b()` is evaluated, because `a()` returns true as first argument of a conjunction. But `c()` is not evaluated because `b()` returns false, so that `a()&&b()` returns false. The end result is false.

I am sure you can work out correct answers for the other two cases (currently wrong in the question).
> 4 votes

---
Tags: optimization, programming-languages, evaluation-strategies, termination
---


# Question
Title: What does every root is at the same level mean
My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level.

My conceptual understanding:

All this time, I was led by my textbook to believe a root is the "top-most vertex" in which all the other vertex are led away from it. So basically I am led to believe there can be only one root in a tree.

Questions:

What does "where every root is at the same level" even mean?

Isn't a root suppose to be at level 0 all the time?

# Answer
It basically is a typo, every leaf at same level may be the correct words
> 1 votes

---
Tags: graphs, binary-trees
---


# Question
Title: Is it NP complete to decide whether a graph has bigger clique or bigger independence number?
Is it $\mathsf{NP}$ complete to decide whether a graph $G$ has bigger clique $\omega(G)$ or bigger independence number $\alpha(G)$?

# Answer
Note that there is a slight technicality with regards to whether you consider the graph where the clique is larger a "yes"-instance, or a graph where the independent set is larger a "yes"-instance (i.e. the complement problem) and what you do in the event of a tie. I have picked one particular way of settling ties, but this proof can easily be adapted to the other way of settling ties (i.e. by fudging with a $\pm 1$).

If $NP\not = coNP$ then neither this problem nor its complement is in $NP$, so neither problem is likely to be $NP$-complete.

It is $NP$-complete to decide whether a graph has an independent set of size $k$. We show that, if there exist polynomial certificates for your problem then there exist polynomial certificates for the complement of the independent set problem. We note that IS remains $NP$-complete even when restricted to maximum degree $3$ graphs and $k\>4$.

Given a graph $G$ that does not have an independent set of size $k$, we create a new graph $G'$ as the union of $G$ and a clique of size $k$ (note that this increases the independence number by one).

$G'$ is a "yes"-instance of the problem "Is the Clique greater or equal to the IS?". A polynomial certificate for this fact would give a polynomial certificate testifying to the fact that $G$ does not have an IS of size $k$, which is impossible unless $NP=coNP$. (The largest clique in $G$ is of size $4$ since $G$ has maximum degree $3$, so the largest clique in $G'$ is of size $k$. The certificate for $G'$ thus has to certify that $G'$ has no IS of size $k+1$ and equivalently, that $G$ has no IS of size $k$).

If we instead consider the complement problem "Is the Clique strictly smaller than the IS?", we create $G'$ by adding a clique of size $k+1$ and then taking the complement graph $\bar{G'}$. Since a Clique becomes an IS in the complement graph and vice-versa, the largest IS in $\bar{G'}$ is of size $k+1$ while the largest Clique is of size at most $k$. $\bar{G'}$ is thus a "yes"-instance of the complement problem, but a certificate for this fact would give a certificate for $G$ not having an IS of size $k$ which is impossible unless $NP=coNP$.

However, the problem "Is the Clique strictly smaller than the IS?" is $NP$-hard. We reduce from Independent Set on a maximum degree $3$ graphs $G$ where $k\>4$. We create $G'$ by adding a clique of size $k$ to $G$. If $G$ has an IS of size $k$ then $G'$ has one of size $k+1$ (obtained by adding any of the clique's vertices to the IS). The largest clique in $G'$ has size $k$, so $G'$ is a "yes"-instance if and only if $G$ has an Independent Set of size $k$.
> 6 votes

---
Tags: np-complete
---


# Question
Title: Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$
I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \\{a^{n} b^{n} c^{n} \mid n \geq 0 \\}$$

I believe it's telling me that no string can be generated that has the same number of of $a$'s $b$'s and $c$'s. This is due to the subtraction of the second set.

A good string from a newly formed language should be something like $aaabbc$ or $abbbcc$ and so on.

So I tried breaking the problem into three parts...

* Single states:
    1. $S\_{1} \rightarrow aS\_{1} \mid a \mid \lambda$
    2. $S\_{2} \rightarrow bS\_{2} \mid b \mid \lambda$
    3. $S\_{3} \rightarrow cS\_{2} \mid b \mid \lambda$
* Two States
    5. $S\_{4} \rightarrow aS\_{4}b \mid S\_{1} \mid S\_{2}$
    6. $S\_{5} \rightarrow bS\_{5}c \mid S\_{2}$
    7. $S\_{6} \rightarrow aS\_{6}c \mid S\_{3} \mid S\_{1}$
* States w/AB states
    8. $S\_{7} \rightarrow S\_{1} \mid S\_{4}S\_{6}$
    9. $S\_{8} \rightarrow S\_{2} \mid S\_{5}S\_{6}$
    10. $S\_{9} \rightarrow S\_{3} \mid S\_{6}S\_{3}$

with an orginal start state of ...

$$ S \rightarrow S\_{7} \mid S\_{8} \mid S\_{9} $$

However I'm having problems building strings like $aaaabbbcc$ ...

Am I forming CFG's incorrectly? I felt like I was on the right track but now I'm quite lost.

# Answer
> 5 votes
This question has been answered before, but let me summarize the answer: $$ a^\*b^\*c^\* \setminus \\{ a^n b^n c^n \\} = \\ \\{ a^{n+1+m} b^n c^p \\} \cup \\{ a^n b^{n+1+m} c^p \\} \cup \\ \\{ a^{n+1+m} b^p c^n \\} \cup \\{ a^n b^p c^{n+1+m} \\} \cup \\ \\{ a^p b^{n+1+m} c^n \\} \cup \\{ a^p b^n c^{n+1+m} \\}. $$ All parameters $n,m,p$ are assumed to be non-negative.

# Answer
> 2 votes
**The quick answer** (no explanation):

The language $$L=a^\*b^\*c^\* - \\{a^n b^n c^n \mid n \geq 0 \\}$$ is equal to

$$L=\\{a^{i}b^{j} c^{k} \mid i\neq j\\}\cup \\{a^{i}b^{j}c^{k} \mid j\neq k\\}$$ which is the union of two CF languages, thus CF. And writing a grammar for each should not be too difficult, from which one gets a CF grammar for $L$.

Of course, one can prove directly that this representation of the language is indeed correct. But I wondered what is a more systematic, or at least analytic, way of finding it. That is what I am presenting below, for whoever is interested. It is actually how I found this answer, pretty trivial in retrospect.

## Understanding how I obtained that result

*Warning: this goes a bit beyond the question.*

Yuval Filmus gave previously a strong hint to answer this question, and a similar question was adressed previously. But I wondered whether this kind of problem can be adressed in a more systematic way, to prove that a language is CF, and to produce a grammar.

Thus, rather than just give a specific proof, I wish to analyze the example in details to understand what should be the strategy for a whole family of similar examples.

It is based on several facts:

1. While CF languages are not closed under complementation general, many CF languages are also co-CF, i.e. have a CF complement. This in particular the case for deterministic CF languages. Deterministic CF languages seem to show up often in exercises, though possibly a bit hidden, as is the case here.
2. CF languages are not closed under intersection, but they are closed under union.
3. Properties defining a language, that appear as conjunctions, turn into disjonction when considering complements (De Morgan's law). From a language point of view, the complement of the intersection of two languages is the union of the complement of each: $\overline{L\_1\cap L\_2}=\overline{L\_1}\cup\overline{L\_2}$
4. CF languages are closed under intersection with regular sets, and of course with union.
5. A few other set relations can be handy. For example we have $L\_1-L\_2=L\_1\cap\overline{L\_2}$.
6. Last, but not least, all the closure properties are constructive, so that one may always hope to use them to extract the grammar from the CF-ness proof. We could certainly build tools to do it for us. For example, a general CF parser (such as CYK) can be used to compute the grammar for the intersection of its language with any regular set.

We look at the example given: $$L=a^{\ast}b^{\ast}c^{\ast} - \\{a^{n} b^{n} c^{n} \mid n \geq 0 \\}$$ and we analyze it in much details, so as to understand better the techniques that can be used.
We note that: $$L=a^{\ast}b^{\ast}c^{\ast} - \\{a^{n} b^{n} c^{n} \mid n \geq 0 \\} =a^{\ast}b^{\ast}c^{\ast}\cap\overline{\\{a^{n} b^{n} c^{n} \mid n \geq 0 \\}}$$

Since $a^{\ast}b^{\ast}c^{\ast}$ is regular, $L$ is CF iff $L\_1=\overline{\\{a^{n} b^{n} c^{n} \mid n \geq 0 \\}}$ is CF.

$$\begin{align} \overline{L\_1}&=\\{a^{n}b^{n} c^{n} \mid n \geq 0 \\}\\ &=\\{a^{i}b^{j} c^{k} \mid i=j=k \geq 0 \\}\\ &=\\{a^{i}b^{j} c^{k} \mid i=j\wedge j=k \wedge i,j,k \geq 0 \\}\\ &=\\{a^{i}b^{j} c^{k} \mid i=j\wedge j=k\\}\\ &=\\{a^{i}b^{j} c^{k} \mid i=j\\}\cap\\{a^{i}b^{j} c^{k} \mid j=k\\} \end{align} $$ The last condition does not really matter here, since exponents are necessarily non-negative integers.

Thus $$\begin{align} L\_1&=\overline{\\{a^{i}b^{j} c^{k} \mid i=j\\}\cap\\{a^{i}b^{j} c^{k} \mid j=k\\}}\\ &=\overline{\\{a^{i}b^{j} c^{k} \mid i=j\\}}\cup\overline{\\{a^{i}b^{j}c^{k} \mid j=k\\}}\\ \end{align} $$

The two languages $M'=\\{a^{i}b^{j} c^{k} \mid i=j\\}$ et $M''=\\{a^{i}b^{j}c^{k} \mid j=k\\}$ are obviously CF, as it is quite easy to build a DPDA for each of them. Hence their complements are also CF, and so is their union $L1$. So **we conclude that $L$ is CF.** From this alone, we could extract a grammar for it, by mechanical means. But this is not easy by hand, and we will go a bit further.

We will try to make the complements of $M'$ and $M''$ a bit more explicit. It is not easy, since it does include for each all the string such that $a$, $b$, and $c$ are not seggregated in the right order. But we can always use the friendly help of intersection with a regular set, precisely $a^{\ast}b^{\ast}c^{\ast}$, that we discarded earlier, as not useful to prove the CF-ness of $L$. It comes back handily to simplify our work for building a grammar.

So we return to $L= a^{\ast}b^{\ast}c^{\ast}\cap L\_1$

$$\begin{align} L&= a^{\ast}b^{\ast}c^{\ast}\cap L\_1\\ &=a^{\ast}b^{\ast}c^{\ast}\cap(\overline{\\{a^{i}b^{j} c^{k} \mid i=j\\}}\cup\overline{\\{a^{i}b^{j}c^{k} \mid j=k\\}})\\ &=(a^{\ast}b^{\ast}c^{\ast}\cap\overline{\\{a^{i}b^{j} c^{k}\mid i=j\\}}) \cup (a^{\ast}b^{\ast}c^{\ast}\cap\overline{\\{a^{i}b^{j} c^{k}\mid j=k\\}})\\ &=\\{a^{i}b^{j} c^{k} \mid i\neq j\\}\cup \\{a^{i}b^{j}c^{k} \mid j\neq k\\} \end{align} $$

Building a CF grammar for these two languages id a standard, and not very hard, exercise. From that you get a grammar for the union of these two languages.

This is unlikely to be the only way to get such results, but it should give some ideas to deal with such problems.

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


# Question
Title: What advantages does Block Programming Environment have over High Level Programming Language
What advantages do block programming environments like App Inventor have over high level programming languages like Python or Java?

# Answer
Developing complex software is completely different from writing small programs.

Complex individual systems are usually elements of complex ecosystems of software and hardware platforms, interfaces, languages, and even extra-computational factors. In creating those kinds of systems the choice of languages that use visual metaphors would probably be detrimental, not beneficial, and that is why professional software developers are happy that the languages they use are "spartan".

On the other hand, if your intention is to reduce the learning curve for begginers that are not going to be professional developers of any kind, then you can begin to talk about the benefits of those "soft" languages.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Finding all paths between a set of vertices in a DAG
Given a graph `G= (V, E)` that is:

1. directed,
2. acyclic,
3. non-weighted,
4. may have more than one edge between two vertices (thus, source and destination are not enough to determine an edge).

And given a set of vertices, let's call them `vSet`; that contains a vertex `vRoot`; I need to find **ALL** paths `pSet` between `vSet` elements respecting the following:

1. any vertex that appears as a source for some path in `pSet` must be reachable from vRoot.
2. any path in `pSet` must has its source and destination from `vSet`, and must not contain any other vertex of `vSet`.

I've developed an algorithm similar to BFS, that starts from `vRoot` (according to 1 above), grow each of the current paths with one edge per an iteration until it reaches another vertex `v1` of `vSet`; then store this reaching path and start growing new set of paths staring from `v1`.

Here is a pseudo code

```
output = ∅;
maxLengthPaths = ∅;
1. add all edges that vRoot is there source to maxLengthPaths
2. while size(maxlengthpaths) != ∅ do
  (a) paths := ∅;
  (b) extendedPaths := ∅;
  (c) foreach path p in maxLengthPaths do
    i. if (destination of p in vSet)
      1. add p to output
      2. for each edge e that destination of p is its source
        A. add e to extendedPaths
    ii. else
      1. add p to paths
    iii. for path p1 in paths
      1. for each edge that destination of p1  is its source
        A. extend p1 by a edge and add it to extendedPaths
  (d) maxLengthPaths = extendedPaths

```

Here are my questions: 1. Is this the best way to achieve my task? 2. I was trying to figure out its time complexity; I found that its exponential of pow(maxNumberOfOutGoingEdgesFormAVertex, maxLengthPath). Is this really the complexity?

# Answer
> 4 votes
Any algorithm for your problem will have to take exponential time in the worst case. However, if you're willing to live with this, there is a straightforward recursive algorithm to solve your problem. Details below.

Generalizing a little bit, your problem is essentially the following:

**Input:** a dag $G=(V,E)$, three sets $S\_0,S\_1,S\_2 \subseteq V$ of vertices

**Output:** the set of all paths that start some element of $S\_0$, end at some element of $S\_1$, and all of whose intermediate vertices are from $S\_2$

To see the relationship to your problem statement, let $S\_0$ be the set of vertices that are reachable from `vRoot` and also contained in `vSet`; let $S\_1$ be `vSet`; and let $S\_2$ be the complement of `vSet`.

There is no efficient algorithm for this problem, because in the worst case there could be exponentially many such paths. Therefore, any algorithm to print all such paths will necessarily have to take exponential time, in the worst case. Of course you could build algorithms that are efficient on some inputs, but no algorithm will be efficient on all possible inputs.

However if you are willing to live with this limitation, here is an approach you could use. Basically, it's easy to come up with a recursive algorithm for this problem:

* Compute the set $S\_0$ of vertices that are reachable from `vRoot` and are contained in `vSet`. This can be found in linear time using DFS or BFS. You can also compute $S\_1$ and $S\_2$ in linear time.
* Enumerate all paths of the desired form recursively. We will build a procedure $F$ so that, for a vertex $v \in V$, $F(v)$ returns the set of all paths that start at vertex $v$ and end at some vertex in $S\_1$ and where all other nodes (the intermediate nodes) are all within $S\_2$. You can compute $F$ via a simple recursive procedure:

+ For each $w \in S\_2$ such that there is an edge $(v,w) \in E$, compute $F(w)$.
    + Now we can return $$F(v) = B(v) \cup B'(v) \cup \\{v@p : w \in S\_2, (v,w) \in E, p \in F(w)\\},$$

    where $v@p$ denotes the path that starts at $v$, goes to $w$, and then follows the path $p$; and where $B(v),B'(v)$ are defined as follows:

    - if $v \in S\_1$, then $B(v)$ is a singleton set containing the path of length 0 that starts at $v$ and stops there; if $v \notin S\_1$, then $B(v)$ is the empty set.
        - $B'(v) = \\{v \to w : w \in S\_1, (v,w) \in E\\}$.
* Finally, calculate $F(v)$ for each $v \in S\_0$ and output the union of all of those paths.
* For better performance, I recommend that you use memoization to avoid ever calculating $F(v)$ more than once for any particular vertex $v$.

This immediately gives you a recursive algorithm that solves your problem, and whose running time is linear in the size of the graph plus the size of the desired output. In other words, this algorithm is about as efficient as you could possibly hope for, given the problem statement.

---
Tags: graphs, dag
---


title: Recoloring bipartite graphs

text:
# Question
Title: Recoloring bipartite graphs
Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation:

1. Choose a vertex $v\_a$ in $A$
2. Flip the colors of $N\[v\_a\]$, meaning that $v\_a$ and every neighbor of $v\_a$ will change color.

> Is there a polynomial time algorithm to select a recoloring set $X \subseteq A$ that will minimize the number of blue vertices? The number of recolorings needed is not relevant.

Observe that the order of flipping does not matter, and for every vertex in $A$, you either flip it or you don't. We can think of the colors as a number which is incremented modulo 2. This yields a trivial $O(2^{|A|} \cdot n)$ algorithm.

# Answer
The problem is NP-complete and is thus not likely to admit a polynomial time algorithm. Below is a proof of the NP-completeness of the problem, shown by a reduction from 1-in-3-SAT.

Let $\phi$ be an instance of 1-IN-3-SAT, where we are given a 3-CNF-SAT formula asked to find a satisfying assignment where each clause is satisfied by exactly one literal. Let $V(\phi)$ be the set of $n$ variables, and $C(\phi)$ be the set of $m$ clauses.

We construct an instance $G = (A,B,E)$ with a budget of $b = n + m$ (the allowed number of blue vertices).

For each variable $x \in V(\phi)$, construct two red vertices $v\_x$ and $v\_{\overline{x}}$ in $A$ together with $b+1$ blue vertices in $B$ adjacent to both of them. This forces exactly one of $v\_x$ or $v\_{\overline{x}}$ to be flipped. We also end up with $n$ flipped "variable vertices", thus using the first part of the budget.

Remark: $\\{v\_x, v\_{\overline{x}} \mid x \in V(\phi)\\}$ are the only vertices in $A$.

For each clause, say $c = x \lor \overline{y} \lor z$, we create $b+1$ blue vertices and three extra red vertices $v\_{x \in c},v\_{\overline{y} \in c},v\_{z \in c}$, all in $B$. Let $v\_x,v\_{\overline{y}},v\_z$ all be fully adjacent to the $b+1$ blue vertices and connect $v\_x$ to $v\_{x \in c}$, $v\_y$ to $v\_{\overline{y} \in c}$, and $v\_z$ to $v\_{z \in c}$.

Now, since each clause gadget has $b+1$ blue vertices, we know that either one *or* three literals in that clause have been flipped. Suppose that three have been flipped for one of the clauses. But then we use at least budget $n + m + 2$.

Suppose that $\phi$ is a yes instance with a 1-in-3 assignment $\alpha: V(\phi) \to \\{\top,\bot\\}$. Flip every vertex which corresponds to $\alpha$. Since every clause is satisfied by exactly one variable, for each clause there is now one blue vertex, and for each variable, exactly one of them is blue, hence we have $n + m = b$ blue vertices.
> 6 votes

# Answer
Pål GD explains that the problem is NP-hard, so the next step is to try to find reasonable algorithms for your problem.

I'll note that your problem can be reduced to MINIMUM WEIGHT CODEWORD: given a linear code, find a codeword of minimum weight. Another way to state this problem is: given a boolean matrix $M$ and a boolean vector $y$, find a non-zero boolean vector $x$ such that the Hamming weight of $Mx \oplus y$ is minimized. (All arithmetic is performed modulo 2.) MINIMUM WEIGHT CODEWORD is known to be NP-hard, but there are some algorithms for it that are faster than brute-force.

Here is the connection. If there are $n$ vertices, then any $n$-bit boolean vector can be thought of as specifying which vertices will be flipped by a particular flip-operation. Thus for each vertex $v$ we get a corresponding flip-vector $m\_v$. Put these into a $n \times n$ matrix, where each row corresponds to a different flip-vector. Let $y$ be a $n$-bit boolean vector that specifies the original colors of the vertices (blue=1, red=0). Now the goal is to find a boolean vector $x$ that minimizes the Hamming weight of $Mv \oplus y$. Any such vector corresponds immediately to a set of flip-operations that minimizes the number of blue vertices in the graph.

With this background, you might be able to apply known algorithms for finding minimum-weight codewords in linear codes to your problem. The running time will still be exponential, but faster than trying all possibilities for $x$.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: What are the k characters which make the most complete words?
Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k\<M$ characters to learn, where "best" is defined as the set of $k$ with which the most *complete* words can be spelled. Ie, if I know these $k$ characters I can spell $N\_k$ words. What is the maximum $N\_k$ for every $k$ and which characters should I choose?

Checking a given set of $k$ words is equivalent to a Scrabble problem, but searching the space becomes very hard very fast. This problem is of limited interest in English where $M=26$ but is more important in Chinese or Japanese where $M \sim 10^3$.

I thought of considering the bipartite graph of characters and the words that they make but I'm not sure what the best search strategy is. I'm somewhat pessimistic that this problem is strictly solvable and therefore I am willing to try heuristic or stochastic methods.

# Answer
> 1 votes
As Lopsy states, your problem is NP-hard, so you shouldn't expect an efficient algorithm for your problem.

Your problem is an instance of the maximum coverage problem (which is also NP-hard). This may help you find algorithms that will be helpful in your setting.

There are standard algorithms for the maximum coverage algorithm. There's a natural greedy algorithm; it achieves an approximation ratio of approximately 0.63.

Perhaps a better approach is to formulate this as an instance of integer linear programming (ILP), and then throw an off-the-shelf ILP solver at it (e.g., lp\_solve, CPLEX). See Wikipedia for a description of how to do that. For your English example (alphabet size 26) it's possible this might give you an optimal solution, but for the Chinese language problem, you shouldn't expect this to terminate and give you the optimal solution within your lifetime. Instead, I suggest you let it run for a bounded time and do the best it can within that time bound. Standard ILP solvers will let you provide a time bound: e.g., run for 5 minutes and then give me the best solution you've found so for.

You will probably want to apply the following simple optimization. Replace each word with the set of letters it contains (so order doesn't matter and repetitions are ignored). Then, de-dup these sets, and include a weight for each set that counts how many times it appears. Thus, GRIN and RING map to the same set, {G,I,N,R}. This will reduce the problem size and might make the ILP solver run faster.

Depending upon your application, you might also want to weight the words by their frequency of occurrence in natural language and then solve the weighted maximum coverage problem, so that you place an extra emphasis on covering common words and a lower priority on covering rare words.

You can also search the literature for other algorithms for the maximum coverage problem, but I suspect the pragmatic answer is going to be to use ILP with a reasonable time bound.

# Answer
> 1 votes
If you take each word as a set of characters, you're looking for sets of size k that contain the most words as subsets. For a given word of j unique characters out of an alphabet of size N, you have (N-j) choose (k-j) possible supersets, ie all the sets of size k that have the original j characters plus any (k-j) others.

Some time ago I worked on an algorithm for a similar problem that might be modified for this case. I'll try to sketch how it would work in this case.

Briefly, the solution is to walk all the "words" through their candidate supersets (a factorial number) in a fixed order, identify any runs of identical values that indicate a number of words that fit in the same superset, and to save the run that's longest.

This is essentially an n-way merge, looking for runs of identical values on the output. I did this with a heap of iterators where I would pull the smallest value, count it, increment it (find the next superset in its range of possible supersets), and re-insert it into the heap. This process provably visits every possible superset and counts the words that it covers.

What makes this possibly tractable is a pruning rule that skips candidates with sub-maximal runs. What I realized while coding the above is that if my only interest is runs of length L or greater, then if I look L elements ahead I can see if the current run stops before L elements, and furthermore (with some careful reasoning) eliminate all intervening values from consideration and skip to whatever value is L elements ahead.

The problem I was solving originally was association-rule mining, which walks each set through its subsets rather than supersets, and this method worked well in that case.

---
Tags: algorithms, optimization, strings, counting
---


# Question
Title: Heap-like data structure allowing peek at largest & smallest
For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations:

* load from array
* Peek at maximum element (but don't destroy it)
* Peek at next-to-maximum element
* Peek at minimum element
* decrease the maximum element

Once initialized, the data structure always stores the same number of elements.

Currently I'm just using an unsorted array, and searching the array each time to find the max, next-to-max, and min elements, and updating the max element when necessary.

I considered using a heap / priority queue, but those don't seem ideal, as they support adding and removing elements, which I don't need to do. They also don't natively support "decrease the maximum element", just "increase an arbitrary element" so I'd have to extract-max and then re-add it.

I also considered a sorted array in a ring buffer, which seems like it would be better than just a sorted array, as I'd only have to move at most half of the list.

Wikipedia talks about some complicated data structures (Fibonacci heaps) that I vaguely remember from my sophomore algorithms class in college, but those seem like overkill (and they also support features I don't need and don't support features I need).

Well, now I search again and I find my question is sort of kind of a duplicate of Increase-key and decrease-key in a binary min-heap

# Answer
> 7 votes
One simple approach is to use a max-heap. Separately keep track of the minimum element stored in the heap. Then all operations can be done relatively efficiently:

* Load from array can be done in $O(n)$ time, building Build-Heap.
* Each of the peek operations takes $O(1)$ time.
* Decreasing the maximum element can be done in $O(\lg n)$ time. You decrease it and fix up the heap property (or extract it and re-insert it). Then, check whether it got reduced below the previous-smallest and if so update the minimum.

This seems likely to be reasonable for many workloads.

---

Alternatively, you could store the elements as a balanced binary tree with the leaves in sorted order. Keep track of a pointer to the leftmost leaf and a pointer to the rightmost heap.

* To load from array, sort the elements and then create a balanced binary tree; this can be done in $O(n \lg n)$ time.
* All of the peek operations take $O(1)$ time.
* The decrease operation can be implemented in $O(\lg n)$ time, by deleting the maximum and then inserting it in the new place, using standard data structures for balanced binary trees that support $O(\lg n)$ time insertion and deletion (e.g., AVL trees, red-black trees, etc.)

This too will likely be reasonable for many workloads.

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


# Question
Title: In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?
In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not sure what the significance of that is or even what that means. Why do the augmenting paths have to be the shortest? And why do they have to be vertex disjoint?

# Answer
Vertex-disjoint means that no vertex appears in two augmenting paths. The paths have to be disjoint so that all can be used. If we have two augmenting paths, P1 and P2, and we augment the matching using using P1, is P2 still an augmenting path for the augmented matching? Yes, if P1 and P2 are vertex disjoint.

As for minimum length, it has the practical implication that we spend the shortest time looking for augmenting paths, but there is a technical matter, too. Augmenting paths found this way are guaranteed to be vertex-disjoint. Look at this text.
> 5 votes

# Answer
Why paths must be vertex disjoint? That's easy. If they are not then symmetric difference (imagine superimposing them on existing matching) might not produce new matching (i.e. one vertex might end up with two edges instead of the requirement that one vertex must have at most one edge in the matching).

Why paths needs to be shortest? My intuition is that set of shortest paths will produce biggest possible next matching. If you choose non-shortest path then we can't use any other intersecting paths with it. For shortest paths, this is minimized as much as possible so the total number of edges in all vertex disjoint paths is maximized which gives maximum possible matching for the iteration. Again, this is just my intuition, I don't have proof for this.

This answer explains choosing shortest paths n terms of greedy solution for a packing problem: https://stackoverflow.com/a/16556223/207661
> 2 votes

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Difference between time complexity and computational complexity
For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?

I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

# Answer
> 14 votes
*Computational complexity* is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about *space* complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.

So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.

Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...). It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).

# Answer
> -2 votes
Cyclomatic complexity is often used as the measure of computational complexity a useful example is provided in https://stackoverflow.com/questions/9097987/calculation-of-cyclomatic-complexity

There may be many different (possibly nested) paths through an algorithm giving it a high cyclomatic complexity, but no loops giving it a low time complexity. A program with a single loop would have a low cyclomatic complexity but possibly a high time complexity.

Cyclomatic complexity is often used as a measure of the maintenance required for the code. A more detailed discussion is provided in http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity. This is different to time complexity that is run time measurement of the code and may be used to assess the users perception of the effectiveness of the system.

---
Tags: complexity-theory, terminology, algorithm-analysis, time-complexity
---


# Question
Title: What's the difference between a reorder buffer and an instruction window?
In an out-of-order processor, what is the difference between a reorder buffer and an instruction window?

Wikipedia says:
"In particular, in a conventional design, the instruction window consists of all instructions which are in the Reorder Buffer (ROB)."

Does this mean that the instruction window isn't a seperate hardware structure?

# Answer
Correct. The *instruction window* is not a hardware structure. It is the set of instructions that is contained in the reorder buffer at any moment in time. Looked at another way: the reorder buffer is a *container* (like a drinking cup is a container) and the instruction window is the thing the reorder buffer *contains* (like milk, juice or water is the thing contained in a drinking cup.)
> 5 votes

---
Tags: computer-architecture
---


title: this automata is NFA or DFA?

text:
# Question
Title: this automata is NFA or DFA?
That's my question, since it has two symbols but go to a single state, is DFA or NFA?

# Answer
First of all, every *deterministic* finite automaton is a fortiori a *non-deterministic* finite automaton. An finite automaton is deterministic if there are no $\epsilon$ moves, and for each state $s$ and alphabet symbol $\alpha$ there is a unique outgoing edge at $s$ labeled $\alpha$. If a finite automaton satisfies this condition, then it you can think of it both as a DFA and as an NFA. If it doesn't satisfy this condition, it is an NFA.
> 5 votes

---
Tags: automata
---


# Question
Title: Can one use the PCP theorem to prove correctness of deternimistic algorithms?
I am thinking of the equality "PCP(O(log(n)),0) = P"

Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of this algorithm say $A\_P$ such that it uses log(n) random bits. Now if I prove somekind of (exactly what ?) expectation correctness of $A\_P$ then does it imply that $A$ was correct?

If the above is not right then I would like if someone can point me to what is the closest correct thing to this!

# Answer
The statement you state is *not* the PCP theorem. The PCP theorem is a characterization of NP.

The statement you mention is much easier to prove. It says in effect that a polytime algorithm that uses $O(\log n)$ random bits can be made deterministic while keeping it polytime (given reasonable completeness and soundness properties). The proof is very simple – we can run the algorithm over the $2^{O(\log n)} = n^{O(1)}$ many choices of random bits, check how many times the algorithm accepts, and so determine whether the input belongs to the language.

At most you can think of this as a derandomization procedure – if your algorithm uses only logarithmically many random bits, then you can make it deterministic by "exhaustive search".
> 2 votes

---
Tags: complexity-theory, probability-theory, randomized-algorithms, information-theory
---


title: Understanding definition of NP

text:
# Question
Title: Understanding definition of NP
In my lecture notes, the definition of the class NP is given as:

A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that:

* For every input $x$, $M$ terminates after at most $T(|x|)$ steps
* If $x\in L$, then there is a "proof"(or certificate) $t\in\\{0,1\\}^{p(|x|)}$ such that $M$ accepts the string $\langle x,t \rangle$
* If $x\notin L$, then for any string $t\in\\{0,1\\}^{p(|x|)}$, $M$ rejects $\langle x,t \rangle$

Firstly, are we saying that $M$ here is a universal turing machine, i.e. $M(\langle x,t\rangle)=M\_x(t)$, also is it necessary to use the same $t$ for all $x$.
Also $M$ is checking whether or not $x$ lies in the $L$, so shouldn't we run just input $x$ on $M$, why is the $t$ necessary. Is there any particular reason why $t$ is called a certificate? Any help with understanding this definition would be greatly appreciated.

# Answer
> 4 votes
Here is an example that will hopefully make things clearer. Consider the problem 3COL, which is the set of all graphs that can be legally colored using 3 colors. It is conjectured that no polynomial time algorithm can determine whether a graph belongs to 3COL (i.e., can be legally colored using 3 colors). However, given a 3-coloring of the graph, it is easy to check whether it is legal (that is, you can do it in polynomial time). In this case:

* $L$ is 3COL.
* $x$ is a graph.
* $t$ is a 3-coloring of $x$.
* $M$ is a machine that checks that $t$ is a valid 3-coloring of $x$.

If a graph $x$ is 3-colorable, then some witness $t$, namely a valid 3-coloring, will convince $M$ that $x$ is in 3COL. Conversely, if a graph $x$ is not 3-colorable, then no 3-coloring $t$ would be valid, and so $M$ will always reject given inputs $x$ and $t$ (for any $t$). This shows that 3COL is in NP.

What happens if $t$ is the same for all $x$? In this case we can hard-code $t$ into the algorithm, and do away with the witness. Under such a definition we get P rather than NP.

What if $t$ is allowed to depend only on the size of $x$? The corresponding class is known as P/poly, and is important in computational complexity. It is more generally known as the class of (languages accepted by) polysize circuits. If you find this interesting, many advanced textbooks discuss this topic.

# Answer
> 1 votes
We are not "saying that $M$ here is a universal" Turing machine. It is not "necessary to use the same $t$ for all $x$." What would running "input $x$ on $M$" mean when $M$ would use its other input?

The certificate $t$ certifies $x$'s membership in the NP language that corresponds to $M$ and $T$ if and only if $M$ accepts the string $\langle x,t\rangle$ after at most $T(|x|)$ steps.

# Answer
> 1 votes
No, $M$ is not universal. The notation $\langle x,t\rangle$ just denotes the pair whose two elements are $x$ and $t$ (this is often written $(x,t)$).

We could use a machine to determine directly if $x\in L$ but doing so is computationally expensive. In particular, assuming that **P$\\,\neq\\,$NP**, it can't be done in polynomial time. Instead, we ask that more information be supplied with the problem instance: this is $t$. For example, it's hard to determine whether a Boolean formula is satisfiable but, if I give you something that I claim is a satisfying truth assignment, it's easy to test that I was telling the truth.

The alternative definition of **NP** is that it's the class of languages $L$ such that there is a *nondeterministic* Turing machine $N$ and a polynomial $T$ such that $N$ always terminates in at most $T(|x|)$ steps and $N$ accepts $x$ if, and only if, $x\in L$.

$t$ is a certificate in the sense of a certificate of authenticity. It's a "document" that proves that $x$ really is a member of the language.

---
Tags: complexity-theory, turing-machines, np
---


title: Complexity of an algorithm

text:
# Question
Title: Complexity of an algorithm
I tried to solve the following exercise :

What is the order of growth of the worst case running time of the following code fragment as a function of N?

```
int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

```

and I found that the complexity is O(n^4), however the correct answer is :

> The answer is : N^7
>
> For a given value of i, the body of the innermost loop is executed 1^2 + 2^2 + 3^2 + ... + (i^2)^2 ~ 1/3 i^6 times. Summing up over all values of i yields ~ 1/21 N^7.

I would like some help to understand this answer and the correct way to calculate complexity in this case.

# Answer
It will be easier to analyze things if we break them down into several different procedures:

```
int I(int n) { for (i = 1; i <= n; i++) J(i); }
int J(int n) { for (j = 1; j <= n*n; j++) K(j); }
int K(int n) { for (k = 1; k <= n*n; k++) sum++; }

```

Instead of measuring time complexity, let us use instead the number of times `sum` is incremented as our complexity measure. Also, let $I(n),J(n),K(n)$ double as the complexity of the functions with matching name.

It is not hard to see that $K(n) = n^2$. Therefore $$ J(n) = \sum\_{j=1}^{n^2} K(j) = \sum\_{j=1}^{n^2} j^2. $$ Now we invoke the formula $\sum\_{j=1}^m j^2 \sim m^3/3$. Substituting $m = n^2$, we get $$ J(n) \sim \frac{n^6}{3}. $$ Continuing, $$ I(n) = \sum\_{i=1}^n J(i) \sim \frac{1}{3} \sum\_{i=1}^n i^6 \sim \frac{1}{21} n^7. $$ Some of these estimates are not completely rigorous, but you can make them rigorous with a bit of work.
> 2 votes

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


# Question
Title: Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?
Consider the language below, on the alphabet $\Sigma = \\{a,b,\\$\\}$: $$L = \left\\{ x$y \mid x,y\in\\{a,b\\}^\* \land \left|x\right| \ne \left|y\right| \right\\}$$

I need to define a CFG for this language. I've tried couple of CFGs but they all failed in one way or another.

I'd be glad for help.

# Answer
Hint: $$ L = \\{ \Sigma^{m+1} \Sigma^n \\$ \Sigma^n : n,m \geq 0 \\} \cup \\{ \Sigma^n \\$ \Sigma^n \Sigma^{m+1} \\}, $$ where $\Sigma = \\{a,b\\}$.
> 4 votes

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


# Question
Title: Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular
$$L=\\{0^m1^n \enspace | \enspace m \neq n\\}$$

I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping Lemma as stated "elsewhere", but I am using the Pumping Lemma anyway. I want to present what I have so far, and for someone to tell me if I'm on the right track:

1. Assume $L$ is not regular.
2. Let $p$ be the pumping length given by the Pumping Lemma for regular languages.
3. Let the string $w = 0^p1^{p+1} \in L$
4. By the Pumping Lemma, $w = xy^iz$, where $i \geq 0$, $\color{green}{\lvert y \rvert \geq 1}$, and $\color{red}{\lvert xy \rvert \lt p}$.
5. Let:

\begin{equation} \begin{aligned} \mathcal{x} &= \mathcal{0}^{p} \\ {y} & = {1}^{p+1} \\ {z} & = \varepsilon \end{aligned} \end{equation}

It is at this point in the proof that I get confused. I feel as if I've set it up well, but just can't finish. Here's what I've got, though:

6. We see that $\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$
7. However, $\lvert xy \rvert= p+p+1 \gt p \enspace \color{red}{\textbf{X}}$

As we can see by $\textit{(7)}$, our test string $w$ violates a $\color{red}{condition}$ of the Pumping Lemma, thus is not regular.

Thumbs up, thumbs down, anyone? Did I make the appropriate inferences about my split string $w$ in order to achieve a contradiction, and did I even split the string correctly? And to boot, did I even pick a $w$ that is useful to the proof?

# Answer
> 4 votes
This is a very hard one to prove via the pumping lemma, as you have to construct a string that eventually gives you something of the form $0^{n}1^{n}$ for some $n$ when you pump it the right number of times. As Renato notes, your decomposition (at the time of writing this answer) is incorrect. We'll come back to this.

A simpler way is to use the closure properties of regular languages. In particular, regular languages are closed under complementation and intersection, so

1. If $R$ is regular, then $\overline{R} = \Sigma^{\ast}\setminus R$ is also regular.
2. If $R\_{1}$ and $R\_{2}$ are regular, then $R\_{3} = R\_{1} \cap R\_{2}$ is also regular.

So we assume that $L = \\{0^{m}1^{n} \mid m \neq n\\}$ is regular. Then by (1), $\overline{L} = \Sigma^{\ast}\setminus L$ is regular. In particular note that $\overline{L}$ includes all strings of the form $0^{n}1^{n}$.

The language $A = \\{0^{a}1^{b} \mid a,b \in \mathbb{N}\\}$ is regular (we can show this via a regular expression, DFA or regular grammar for the language, e.g. $0^{\ast}1^{\ast}$).

Then by (2) $\overline{L}\cap A$ must also be regular, but this is the language $\\{0^{n}1^{n}\\}$, which is not regular (and much easier to prove via the pumping lemma!).

As noted in the question you linked however, it is possible to do it with the pumping lemma, but you need to pick your starting string carefully. As we only have two sections to the string, the obvious approach is to have a string of the form $0^{p}1^{x}$ for some $x$, so then we know that $y = 0^{k}$ for some $k\leq p$. Now the trick is to pick $x$ such that we can pump the string some number $y$ times and get $p + (y-1)\cdot k = x$. Of course we don't know what $k$ is - it could be anything from $1$ to $p$, so $x$ needs to take this into account. Hence $x$, in part, needs to (almost) be a multiple of every number from $1$ to $p$. So if we pick $x = p + p!$, we can say that for every $k$, there exists a $y$ such that $p + (y-1)\cdot k = p + p!$. In particular $y = \frac{p!}{k}+1$.

So then our starting string is $s=0^{p}1^{p+p!}$. By the pumping lemma if $L$ is regular, we can break $s$ up in $xyz$ such that $|y| \geq 1$, $|xy| \leq p$ and $xy^{i}z \in L$ for every $i \in \mathbb{N}$, but we have just shown that for $i = \frac{p!}{k}+1$, we get the string $0^{p+p!}1^{p+p!} \notin L$. Hence $L$ violates the pumping lemma, can thus can't be regular.

# Answer
> 2 votes
Thumbs down because your decomposition is wrong. Pumping lemma complies only if you choose a valid decomposition ($|xy|\leq p$ and $|y|\geq 1$). The idea is that you prove that there are no possible(valid) decompositions such that the pumping lemma is fulfilled

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