title: Asymptotically Optimal Algorithms

text:
# Question
Title: Asymptotically Optimal Algorithms
I am confused how to check if an algorithm I made is asymptotically optimal.

At the very least, the running time is constant at O(4). This is because you will need to check at least 4 names.

At the very most, the running time is linear at O(n). This is from n + n + n/2 + n/2 + n/4 + n/4 + .... = 2n * (1 + 1/2 +...) \< 2n. As we ignore constants its just O(n).

I checked on Wiki and it said that the algorithm should perform at worst a constant factor of the best algorithm. But if you invented an algorithm then how do I figure this out?

# Answer
> 1 votes
We usually only care about the *worst-case complexity* of algorithms. An $O(n)$ algorithm is usually asymptotically optimal (assuming $n$ is the input size), since most functions require you to read the entire input in some cases.

Another example in which you can prove asymptotic optimality is comparison-based sorting algorithms. A comparison-based sorting algorithm is a sorting algorithm whose only access to the data is a comparison oracle, which compares to data items. Any such algorithm must make $\Omega(n\log n)$ oracle queries in the worst case. Therefore a comparison-based sorting algorithm running in time $O(n\log n)$ is asymptotically optimal.

In most cases, however, we cannot prove that a given algorithm running in superlinear time is optimal, since we don't know how to prove running time lower bounds on general computation models. However, in some cases we can prove such lower bounds conditionally, that is, assuming some widely believed hypothesis. This is known as *fine-grained complexity theory*, and it indicates (conditionally) that the best algorithms for many problems are indeed asymptotically optimal.

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


# Question
Title: Why isn't it simple to count the number of words in a regular language?
Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the expression - the language is infinite. Else: Go through and count all the combinations of words that are possible to make using the expression (basically if there is a + operator on the expression, multiply the amount of legal words by the amount of strings connected by the +..)

Is this wrong? Thanks in advance

# Answer
Yep, this is wrong, because of ambiguity.

Consider the following language: $(a + aa) + a(a + \epsilon)$.

With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.

A better method is to use dynamic programming on an minimal DFA for your language, with no "dead" states. If the minimal DFA is cyclic, the language is infinte, so we can assume there's no cycles. Using a DFA is key, because the determinism means there's exactly one path through the DFA for each word.

What you do is build up a recurrence for the number of words that end at a given state:

* 1 words ends at the start state: $\epsilon$
* For each state $q$, the number of words ending there is the sum of the number of words ending at each state with a transition into $q$.

The total number of words is then the sum of the number of words ending at each final state.
> 12 votes

# Answer
Complementing jmite's answer, it is not too difficult to compute the number of words in a regular language, using the "transfer matrix" method. This is the same as jmite's dynamic programming, but the technique has further applications such as asymptotic enumeration.

Given a DFA, construct a $Q\times Q$ matrix $M$ (where $Q$ is the set of states) in which $M(i,j)$ is the number of letters that cause the DFA to move from state $j$ to state $i$. Let $1\_{q\_0}$ and $1\_F$ be the indicators for the initial state and for the accepting states, respectively. Finally, let $n = |Q|$.

The number of words of length $m$ is $c\_m := 1\_F M^m 1\_{q\_0}$. Compute $c\_m$ for $0 \leq m \< 2n$. If $c\_n + \cdots + c\_{2n-1} \> 0$ then the language accepted by the DFA is infinite. Otherwise, the number of words in the language is $c\_0 + \cdots + c\_{n-1}$.

(When computing powers of $M$, care must be taken regarding the magnitude of the entries, which is exponential in $m$. Since their size is only polynomial, the resulting algorithm runs in polynomial time.)
> 10 votes

# Answer
Actually, you can still derive counting formulas for **unambiguous** regular expressions with Kleene stars within.

Given the inductive definition of a regular expression as: $$ \begin{equation\*} e \in \mathrm{Re} := x \in \Sigma \mid e\_0 ~ e\_1 \mid e\_0 + e\_1 \mid e^\* \end{equation\*} $$

Consider the following translation $\[\\!\[\cdot\]\\!\] : \mathrm{Re} \to \mathbb{C}(z)$ that takes a regular expression and translates it into a complex-valued rational function:

$$ \begin{align\*} \[\\!\[x \in \Sigma\]\\!\] &= z \\ \[\\!\[e\_0 ~ e\_1\]\\!\] &= \[\\!\[e\_0\]\\!\] \times \[\\!\[e\_1\]\\!\]\\ \[\\!\[e\_0 + e\_1\]\\!\] &= \[\\!\[e\_0\]\\!\] + \[\\!\[e\_1\]\\!\]\\ \[\\!\[e^\*\]\\!\] &= \frac{1}{1 - \[\\!\[e\]\\!\]} \end{align\*} $$

We can show that this translation returns a rational expression by doing structural induction on $e$, and noting that all of the operations used on the right-hand side preserves rational-ness.

Suppose that the regular expression $e$ that we put in is unambiguous, then we would find that the rational function denoted by $\[\\!\[e\]\\!\] \in \mathbb{C}(z)$ is actually the generating function for the family of words that are accepted by the language underlying $e$, ranked by their length.

For example, consider the language $(a^\*b)^\*$, which defines the language of runs of $a$ delimited by $b$. Now, this regular expression is unambiguous, so we can run our translation trick:

$$ \begin{align\*} \[\\!\[(a^\*b)^\*\]\\!\] &= \frac{1}{1 - \[\\!\[a^\*b\]\\!\]} \\ &= \frac{1}{1 - (\[\\!\[a^\*\]\\!\] \times \[\\!\[b\]\\!\])} \\ &= \frac{1}{1 - \left(\frac{1}{1 - \[\[a\]\]} \times z\right)} \\ &= \frac{1}{1 - \frac{z}{1 - z}} \\ &= \frac{1}{2} + \frac{1}{2 - 4 z} \end{align\*} $$

As it turns out, given the above generating function, its coefficient extraction will be $$ \[z^n\]\[\\!\[(a^\*b)^\*\]\\!\] = 2^{n - 1} + \frac{\delta\left(n\right)}{2} $$ where $$ \delta(n) = \begin{cases} 1 & \text{if } n = 0 \\ 0 & \text{otherwise} \end{cases} $$

In fact, since our translation $\[\\!\[\cdot\]\\!\]$ generates rational functions, we can use a partial fraction decomposition to create an enumeration formula for any unambiguous regular expression.

Suppose you have a irreducible rational function $$ r(z) + \frac{p(z)}{q(z)} $$ where $r, p, q$ are polynomials, then you can decompose this into $$ r(z) + \frac{C\_0}{z - q^\*\_0} + \dots + \frac{C\_n}{z - q^\*\_n} $$ where $q^\*\_k$ are the roots of $q(z)$. There's a bit of technical corner-cases (like multiplicity of roots, etc), but it's relatively easy to do coefficient extraction on the expression above: $$ \[z^n\] \frac{C}{z - q^\*} = C \times {q^\*}^{-n} $$

In fact, the partial fraction decomposition generalize to multivariate rational functions, so you can actually construct counting formulas for queries such as "How many words are there where there are $n$ `a`s and $m$ `b`s?"

Unfortunately, the extent to which this method will be useful ends when you have an ambiguous expression.
> 9 votes

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


title: Finding if a CFG is ambiguous

text:
# Question
Title: Finding if a CFG is ambiguous
I'm trying to find if the following CFG is ambiguous.

\begin{align\*} M &\to 0R \mid 1R\\ R &\to 1RR \mid 0 \mid 0M\\ P &\to 0PP \mid 1 \mid 1M\\,. \end{align\*}

When doing the parse tree, do I treat $0R$ as two separate things or as one? If I treat all those things as separate, when I get to $0M$, do I go back to the loop of $M\to 0R \mid 1R$ again?

# Answer
> 1 votes
In a parse tree, each vertex is annotated by a terminal, non-terminal, or $\epsilon$. In particular, you have to treat $0R$ as two separated things, a leaf labeled $0$ and a vertex labeled $R$. You can have several vertices with the same label, corresponding to your "loop".

I suggest looking at some examples of parse trees on the web or in your textbook.

# Answer
> 1 votes
Finding whether an arbitrary context free grammar is ambiguous is undecidable. That's meant, in general. But on a case by case basis, there are techniques you can use to show how a grammar is ambiguous, when it is so. As others have suggested, textbooks will give you the basics about those. But even textbooks vary in pedagogical quality or completeness of explanations. You can also back up to other resources, such as Wikipedia articles, of varying quality, just the same, granted. In your case, the grammar is simple (read: small) enough to use a common, simple technique: find a string in the language which admits more than one leftmost derivation, aka parse tree. And you're done once you find it: because, then, yes, the grammar is ambiguous.

And from only the phrasing of your question, I suspect you have already found its answer, actually. :)

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


# Question
Title: How can I get all representations of an n-ary tree that completely "cover" the tree?
I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover:

Suppose we have the following tree

```
        1
     /    \
    2      3
   / \    /|\
  4   6  5 7 8
      |
      9

```

I want to somehow obtain the following:

* 1
* 2, 3
* 2, 5, 7, 8
* 4, 6, 3
* 4, 6, 5, 7, 8
* 4, 9, 3
* 4, 9, 5, 7, 8

As you can see `1` completely covers the tree because all leaves are underneath it. Similarly `2, 3` covers the entire tree because all leaves are underneath them. This goes for all of them until finally we get to `4, 9, 5, 7, 8` which covers the entire tree because all leaves are underneath (or are them).

Is there an algorithm to do this or a modification of a classic search algorithm that will produce this?

# Answer
Let $T$ be a tree with root $r$, and let the children of $r$ be $r\_1,\ldots,r\_d$. Then every minimal cover of $T$ either consists of $r$, or is a union of minimal covers of $r\_1,\ldots,r\_d$; if $r$ is a leaf then the second option doesn't exist. You can easily convert this to a recursive algorithm that lists all minimal covers.
> 2 votes

# Answer
Yuval was moving in the right direction.

Here's the pseduo code:

```
def get_tree_covers(node):
    node_covers = []
    if node is NULL:
        return node_covers
    node_covers.append(node.value)
    if node.children is NULL:
        return node_covers
    child_covers = [] // Used to store the covers of each child
    for child in node.children:
        child_covers.append(get_tree_covers(child))
    if child_covers.length == 1:
        tree_covers = join_lists(tree_covers, child_covers[0])
        return tree_covers
    joined_covers = child_covers[0]
    for i in range(1 to child_covers.length):
        new_tree_covers = []
        for j in range(0 to joined_covers.length):
            for k in range(0 to child_covers[i]):
                new_cover = joined_covers[j] + child_covers[i][k]
                new_tree_covers.append(new_cover)
        joined_covers = new_tree_covers
    tree_covers = join_lists(tree_covers, joined_covers)
    return tree_covers

```

The runtime is abysmal and I would love to know if anyone can come up with anything quicker. Worst case this thing runs in `O(max_branch_lengh^number_of_branches)` which is **really** bad. For my use case it works out all right because I'm using it on very small trees so we're talking at most a few hundred operations. But on a larger tree this would really kill your runtime.
> 0 votes

---
Tags: graphs, trees, graph-traversal
---


title: SVM with different length features

text:
# Question
Title: SVM with different length features
I need to train SVM with 2 different features..the problem is one feature is the HOG with length 144 and other an RGB value with length 3.. Can i combine these two features to train SVM and test using the same? the code iam using is

`X1=xlsread('train1.xlsx');
Y1=xlsread('CLASS1.xlsx');
svmStruct1=svmtrain(X1,Y1);
 classes=svmclassify(svmStruct1,test);`

the test data contains both RGB and HOG values..

# Answer
Yes, you can do it. Concatenate the two feature vectors to get a single feature vector of length 147; the first 144 components are from the HOG, and the last 3 components are from the RGB. Then apply the SVM on the feature vector of length 147. SVM doesn't care where the individual numbers came from.

Code is off-topic on this site.
> 0 votes

---
Tags: svm
---


# Question
Title: Is the Rice Theorem applicable for these problems?
**I have 1 problem :--\>**

```
L = { < M > | TM halts on no inputs }

```

I have solved the above problems by reductions given in the book and even there are many links in stackexchange site. I have no problems in the reduction method.

But, just trying to be more curious, I tried to solved these problems by using rice theorem. I know that rice theorem is applied on the property of languages and here it is property of TM's but i tried some conversion here .

**Though, I am getting the right answer but i want to confirm is what i have tried is legal or Can It be solved like this ?**

As the TM halts on no inputs, which means it is not halting on the inputs in the language as well as inputs not in the language.

```
So, I wrote it as

L = { < M > | L(M) = PHI }

```

which is surely a non trivial property and as well as non monotonic property, hence the language is Undecidable and as well as Non RE.

**Well, I am new to this topic. So, i don't know whether I am right in the conversions or Can I assume something like this. Please correct me if i am being stupid .**

# Answer
> 5 votes
Rice's theorem cannot be used to show the undecidability of these two languages.

Most of the incorrect attempts that I have come across, are based on the misunderstanding that the notion of property is a vague notion from everyday life. However, a property means something very precise in the context of computability theory: *A property is a class of Turing-recognizable languages.*

Rice's theorem can be applied whenever we are faced with a non-trivial class of Turing-recognizable languages $\mathcal{S}$, that is, a class of Turing-recognizable languages that is neither the empty class or the class of all Turing-recognizable languages. Rice's theorem tells us that if $\mathcal{S}$ is a non-trivial class of Turing-recognizable languages, then

$$L\_{\mathcal{S}} = \\{ \langle M \rangle \mid M \text{ is a Turing machine such that } L(M) \in \mathcal{S} \\}$$

is undecidable.

But there is no class of recognizable languages that corresponds to

$$A = \\{ \langle M \rangle \mid M \text{ halts on no input} \\}$$

For consider the Turing machines $M\_1$:

"On input $x$, loop forever"

and $M\_2$:

"On input $x$, *reject*"

We have that $\langle M\_1 \rangle \in A$ but $\langle M\_2 \rangle \notin A$, while we also have $L(M\_1) = L(M\_2)$.

Similarly, there is no class of languages that corresponds to

$$B = \\{ \langle M \rangle \mid M \text{ halts on at least one input} \\}$$

Here, we can choose $M\_1$ as

$M\_1:$ "On input $x$, if $x = aa$ then *reject*, else loop forever"

and $M\_2$ as

$M\_1:$ "On input $x$, *reject*"

Again we have that $\langle M\_1 \rangle \in A$ but $\langle M\_2 \rangle \notin A$, while we also have $L(M\_1) = L(M\_2)$.

A *correct* application of Rice's theorem to a decision problem about Turing machines must identify a *non-trivial class of Turing-recognizable languages* that the decision problem corresponds to.

See my note http://people.cs.aau.dk/~hans/ANoteOnRicesTheorem.pdf for more about correct applications of Rice's theorem as well as a discussion of incorrect applications of the theorem.

# Answer
> 1 votes
Yes, your application of Rice's theorem is correct.

Let me present Rice's Theorem in a different way (in fact, closer to the original presentation). Suppose to have an acceptable enumeration of partial computable function $\varphi: N \to PC$. We say that a set $A \subseteq N$ is extensional with respect to $\varphi$ if it is the counter image of some subset $F \subseteq PC$ of computable functions, i.e.

$$A = \varphi^{-1}(F)$$

This is equivalent to require that $A$ is closed w.r.t. $\varphi$:

$$i \in A \wedge \varphi\_i = \varphi\_j \Rightarrow j \in A$$

Stated in another way, this means that a program is or not in $A$ independently from the way it written, but only according to the function it computes (its behaviour).

Rice's theorem states that an extensional set is recursive if and only if it is trivial. This of course applies to your case.

The theorem can also be stated for r.e. sets. Consider an effective enumeration of r.e. set, $W: N \to RE$ (for instance, you can take $W\_i = dom(\varphi\_i)$.

In this case the notion of "extensionality" is relative to $W$. Again, an extensional set $A \subseteq N$ is recursive if and only if $A$ is trivial.

In the context of languages, it would be better to consider acceptance on termination only.

---
Tags: turing-machines, undecidability, semi-decidability, rice-theorem
---


# Question
Title: How is a grammatical rule applied if the variable is not part of the source word
I'm currently working with this grammar:

1. $S \to aSBC$
2. $S \to aBC$
3. $CB \to BC$
4. $aB \to ab$
5. $bB \to bb$
6. $bC \to bc$
7. $cC \to cc$

It is supposed to define the language $$ L = \\{a^nb^nc^n : n \geq 1\\}. $$

I need to know how to get through the grammar rules to end up with $L$. So I started with the first two rules which end up to be $a^n(BC)^n$.

$$ S \Rightarrow^\* a^{n-1}S(BC)^{n-1} \Rightarrow a^{n-1} aBC (BC)^{n-1} = a^n (BC)^n.$$

It's quite obvious until there. My lecture than adds the third rule to $a^n(BC)^n$:

$$ a^n(BC)^n \Rightarrow^\* a^nB^nC^n. $$

And that's where I'm completely lost. How is the third rule applied if its left-hand side ($CB$) isn't even part of the initial word ($a^n(BC)^n$)?

# Answer
When we write $a^n(BC)^n$, we mean the word composed of $n$ copies of $a$ followed by $n$ copies of $BC$; using $^n$ is just a shortcut. For example, $a^2(BC)^2$ is shortcut for the word $aaBCBC$. Indeed, $^n$ just doesn't belong to the syntax of words, which states that a word is a sequence of terminals and non-terminals.
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: Why does the neural network logistic regression cost function sum for all layers only for lambda?
I'm taking Andrew Ng's machine learning course and week 5 covers the training of neural networks. The modified cost function for neural network training is derived from the logistic regression cost function, and is described as follows:

$$\begin{gather\*} J(\Theta) = - \frac{1}{m} \sum\_{i=1}^m \sum\_{k=1}^K \left\[y^{(i)}\_k \log ((h\_\Theta (x^{(i)}))\_k) + (1 - y^{(i)}\_k)\log (1 - (h\_\Theta(x^{(i)}))\_k)\right\] + \frac{\lambda}{2m}\sum\_{l=1}^{L-1} \sum\_{i=1}^{s\_l} \sum\_{j=1}^{s\_{l+1}} ( \Theta\_{j,i}^{(l)})^2\end{gather\*}$$

Here, *K* is the number of output units, *L* is the total number of layers in the network, and ${s\_l}$ is the number of units in layer *l*.

I don't understand why the second half of the cost function, intended to prevent over-fitting by minimizing the values of the theta parameters, is summed across the *entire* network while the first half of the equation which actually determines theta is only for a specific layer. If each layer's cost function already includes a minimization parameter for that layer's theta values, why is it necessary to perform this minimization globally for every layer in the cost function J?

As I understand it, in training a neural network you mainly treat each layer as completely separate from the next (and in fact, that is one of the major selling points of the NN approach, wherein solving *L* layers independently of one-another lets you use a simple approach to obtain powerful results) - so why are we summing the second half of the equation over all layers?

# Answer
> 2 votes
The first term depends on the output of the entire network, i.e., on all the parameters for all layers, not just a single layer's parameters.

This is an application of the empirical risk minimization framework for training a classifier, with regularization. The cost function $J(\Theta)$ has the form

$$J(\Theta) = \text{empirical risk} + \text{regularization penalty}.$$

Denote the empirical risk by $R(\Theta)$; it depends on the parameters $\Theta$ (for all layers). Denote the regularization penalty by $P(\Theta)$; it depends on the parameters $\Theta$ (for all layers).

The empirical risk $R(\Theta)$ is the sum of the loss for each instance in the training set, i.e., it has the form

$$R(\Theta) = {1 \over m} \sum\_{i=1}^m \ell(h\_\Theta(x^{(i)}), y^{(i)}),$$

where $\ell$ is a loss function, $x^{(i)},y^{(i)}$ is the $i$th instance in the training set, and $h\_\Theta(x)$ denotes the output of the classifier on input $x$ when the parameters are $\Theta$. Note that the output of the classifier depends on all the parameters for all the layers, so $R(\Theta)$ depends on all the parameters for all layers (not just a single layer).

A comment on notation: We use $\Theta$ to denote all of the parameters, i.e., a single vector that concatenates the parameters for each layer. Here it appears $\Theta^{(l)}$ has been used to denote the parameters for the $l$th layer, so $\Theta = (\Theta^{(1)}, \dots, \Theta^{(L)})$.

In your specific example, we use the cross-entropy loss for $\ell$ (this is also known as the logistic loss function, where there are only two classes). That's how we get the first term.

Also the regularization penalty $P(\Theta)$ depends on all of the parameters, for all layers; it is a sum of penalties for each layer.

If you work through the math, you'll see how we get something of the form you've shown in the question. As this answer hopefully makes clear, each term depends on the parameters for *all* the layers, not just a single layer.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Need help optimizing the loading of passengers on small airplanes
I work for a small non-profit that provides transportation for people who need medical treatment. We connect volunteer private pilots who fly people in their own (small) aircraft, typically 3-5 seats.

Several times each year, we provide flights for kids to go to special needs camps. In this scenario, we have a number of kids (say 20-30) going from multiple origins to one destination, and several pilots who have expressed an interest in flying one of the routes. We'd like to create an algorithm to optimize the loading and travel of each aircraft. The number of seats is a constraint, in other words, we can't have more passengers than there are seats. Optimizing loading would mean (I think) minimizing the difference between the airplane's load capability and the total weight of the passengers. A second factor would be how far the pilot would need to go out of their way to complete the trip, based on where the plane is based. For that, we can look at a multiple of the trip distance. So, if the plane is based at either the origin or the destination of the route, the multiple would be 1 (total distance divided by trip distance), whereas the multiple will grow the more they have to go out of their way.

I'm a programmer and not a mathematician, and I would love to have any guidance anyone is willing to provide as to an approach.

# Answer
This is an optimization problem.

The first step is to work out more precisely what your objective function is. In other words, given a candidate assignment of pilots, you need a well-specified way to compute a single "goodness value" for that assignment. That's your objective function: an objective function maps a candidate solution to a number indicating how good the candidate solution is. Once you have defined an objective function, you then have a well-defined optimization problem.

Right now, it sounds like you haven't yet settled on a specific objective function. You mention some possible factors, but the question isn't completely precise about how exactly those factors should be measured or how to weight the individual factors and combine them to get a single number. Generally you can't solve the optimization problem until you formulate an objective function that gives you a single number (otherwise the notion of a "best" solution isn't well-defined).

Once you can do that, you could look at expressing this as an integer linear programming problem. See, e.g., .

The kind of problem you mention generally falls into the field known as "operations research".

Alternatively, with only 15-20 kids, you might even be able to write a program that exhaustively enumerates all candidate solutions and scores each one. There will be exponentially many candidate solutions but if the number of kids is small enough it might be feasible to enumerate them all. 15-20 kids is probably on the edge of what could be computed in a reasonable amount of time, so this might fail badly, and you might need to resort to combinatorial optimization methods, such as integer linear programming.
> 2 votes

# Answer
This is a combinatorial optimization problem which is in NP. The standard generic solution is simulated annealing: come up with ways to manipulate one solution to generate others (say by flipping two children from one plane to another, or swapping a plane for another) and a measure of optimality $\phi$. Then start with a solution, and try the ways to manipulate it. If they work better, keep them. If they don't, keep them with a probability proportional to $e^{-\phi/T}$ where $T$ is the temperature. Then slowly drop the temperature.
> 0 votes

# Answer
It sounds like you have several objective criteria and system constraints to consider and they may change over time. A wide range of problems can be formulated and solved as Mixed Integer Programming (MIP) problems. One way to solve a MIP problem would be use to use the revised simplex method to solve linear programming problems and the branch-and-bound algorithm to find integer solutions (Bazaara; Jarvis and Sherali, 1990). If it turns out that the performance of this tandem algorithm is unacceptable using real information then at least you can use this as a basis for testing your newly designed and implemented special algorithm.

With this in mind you should gather and formulate all your criteria and constraints. Formulating MIP problems can be challenging. I found it very helpful to see and to practice on a few examples. Check out “Model Building in Mathematical Programming” (Williams, 1999).

Consider the possibility that several solutions (not necessarily optimal) are acceptable and the final solutions will be decided by a person or group of people rather than the computer. This is probably more desirable especially if stakeholders change their mind or events occur that affect the inputs to the model, thus affecting the solutions. In this case you should include in your design an interactive decision support system.

Are you considering other things such as user interfaces for entering input data and running scenarios, reports for system status, etc. If you have not decided on a platform or framework to code your software system then you should also consider your situation as a document workflow problem. Look at PDF forms using JavaScript and the Acrobat/JavaScript API as one way to satisfy your document workflow requirements (Adobe, 2012; 2007; Flanagan, 2006).

## References

1. Adobe Systems Incorporated. (2012). Adobe Acrobat XI \[software\]. San Jose, California: Adobe Systems Incorporated.
2. Adobe Systems Incorporated. (2007). Adobe Acrobat SDK 8.1 JavaScript for Acrobat API Reference for Microsoft Windows and Mac OS. Edition 2.0, April 2007. San Jose, California: Adobe Systems Incorporated. Retrieved Aug. 3, 2010 from http://wwwimages.adobe.com/www.adobe.com/content/dam/Adobe/en/devnet/acrobat/pdfs/js\_api\_reference.pdf.
3. Bazaara, M. S., Jarvis, J. J. and Sherali, H. D. (1990). Linear Programming and Network Flows. New York: Wiley.
4. Flanagan, D. (2006). JavaScript: The Definitive Guide, Fifth Edition. Sebastopol, CA: O’Reilly Media Inc.
5. Williams, H.P. (1999). Model building in mathematical programming (4th ed.). New York (NY): John Wiley & Sons, Inc.
> 0 votes

---
Tags: linear-programming
---


# Question
Title: Can such an algorithm be written using recursion
I'm writing an algorithm that, given a limit `N`, and given a list of elements of value `V`, find all the possible combinations so that the sum of the elements is equal to `N`. **Note that several elements can have the same value.**

A simple example to demonstrate this, if `N=16`, and that we have 3 elements, `a`, with a value of `3`, `b` with a value of `3` and `c` with a value of `4`, we have:

```
a+a+a+a+c = 12
a+b+a+b+c = 12
c+c+c+c = 12
b+b+a+b+c = 12
etc...

```

The algorithm I wrote is pretty straightforward, yet I have a huge trouble making it generic. Indeed, my algorithm depends on the numbers of elements given as input. Here is what I came up with, in pseudo-code:

```
Input: a list of element (input)
Output: A list of elements so that the sum of their value == N (output)

FOR element_1 IN input
    sum := element_1.value

    IF sum EQUALS N
        output.push([element_1])

    FOR element_2 IN input
        sum := element_2.value

        IF sum EQUALS N
            output.push([element_1, element_2])

        FOR element_3 IN input
            // etc, there will be as much inner for loops are there are elements in input

RETURN output

```

Note that the algorithm is working, and the results are correct.

The problem here is that my algorithm depends on how many numbers there are in the input list. To be precise, the algorithm will work if there are less elements in the input list than there are inner for loops, and fail otherwise. Thus, I wondered, **is this possible to write this algorithm using recursion ?** So that I can write a generic code, that will adapt to the length of the input list.

I tried, yet didn't succeed, I don't know much about algorithmic, and I wondered if there are cases where recursion cannot be applied, and if this case is one of them.

# Answer
> 1 votes
Off the top of my head i would perform a recursion this way:

```
Solve(N,V,target_value):
    if target_value == 0:
        return {}
    if target_value<0 or |V|==0:
        return false
    for 0<=i<N:
        sol = Solve(N-1,V\V[i],target_value-V[i]
        if sol is feasible:
            add [V[i]+sol] to the list of feasible solutions
    if there are any feasible solutions, return them. else return false.

```

This is obviously pseudo-code that needs to be tweaked a bit. But the general idea is to reduce the problem instance by thinking "If I take element `i`, what other elements do I have to take?". So assuming you take element `i`, you reduce the target value and exclude `i` from the available other elements and perform a recursive call.

The recursion base is reached when:

1. The target value becomes negative (= we put too many elements into the sack already!)
2. We used up all elements and still didn't reach the target value! The problem is therefore unsolvable
3. We reached the target value and can return the current chain of elements. This is done by returning an empty list, which is then filled when the stack is being unwinded (line 9).

---
Tags: algorithms, recursion, knapsack-problems
---


# Question
Title: Markov chain probability in a complete graph
I'm having a hard time understanding the following. Assuming we have a complete graph with $n$ vertices, where initially, one of those has an information. At this point, all we care about is that in each time $t$ a node that has the information chooses randomly one of it's neighboors and sends it the info, only if the receiver does not have it. We don't care how the sending is done. Let $x\_t$ be a random variable representing the number of nodes that have the info at the time $t$. It is indicated that $x\_t$ can be modeled by a homogeneous increasing Markov chain. So, if at $t$, if $k$ vertices have he info, then the probability of another vertex receiving the information (using population protocols), that is, to have $k+1$ vertices know it is $\frac{2k(n-k)}{n(n-1)}$. Can someone explain why this stands?

The link to the paper I got this from is this: https://drive.google.com/open?id=0B0RiUAwpE4vnTlFqWmRHdlRYSFp4aDlYcWE5dWxUdWg2ZDA4 and the transition graph of the chain is shown in Figure 2.

# Answer
The probability that you state is the probability that a random edge of the complete graph connects one of the $k$ nodes to one of the other $n-k$ nodes. This means that in your process, a random edge is chosen, and if exactly one vertex already knows the information, then the other vertex is made aware of it. Information spreads exactly when the chosen edge is of this form, which in your case happens with the probability you mention.
> 2 votes

# Answer
So after putting a lot of thought into this and with the help of the previous comment, I managed to figure it out like this:

First of all, the graph has $\frac{n(n-1)}{2}$ edges, so the probability of a node knowning the info choosing one edge is $p=\frac{2}{n(n-1)}$. Now, we have $k$ such nodes so p is multiplied by $k$ and $n-k$ edges connecting that node to the remaining $n-k$ nodes who don't have the info and thus the probability is also multiplied by $n-k$, which gives the result.

Please correct me if I'm wrong
> 2 votes

---
Tags: probabilistic-algorithms
---


title: Solve parity game in polynomial time?

text:
# Question
Title: Solve parity game in polynomial time?
Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?

# Answer
> 6 votes
Parity games are famously known to be in $NP\cap coNP$, and in fact, in $UP\cap coUP$. However, there are no polynomial algorithms known for them.

To be more specific, the best algorithms run in time that is polynomial in the number of states $n$, but exponential in the parity index $d$.

The state of the art, as far as I know, is Jurdzinsky's work here.

Parity games is one of the rare problems we know to be in $NP\cap coNP$, but don't know to be in $P$. Since most other candidates for such languages were eventually shown to be in $P$, it is not unreasonable to believe that a polynomial time algorithm will be found.

# Answer
> 8 votes
The state of the art for solving parity games is now quasipolynomial time. Here are references:

> Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
>
> A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.
>
> Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić, LICS 2017.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak

---
Tags: algorithms, complexity-theory, graphs, polynomial-time, game-theory
---


# Question
Title: Sampling from a set of numbers with a fixed sum
Let $s = \\{x\_1, x\_2, \ldots, x\_n\\}$ be a set of $n$ random non-negative integers where $\sum\_i x\_i = n$. And let $\\{y\_1, y\_2, \ldots, y\_{\sqrt{n}}\\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen uniformly at random. Defining $y$ to be $\sum\_i y\_i$ I am interested in calculating the value of $y$.

By linearity of expectation, I know $E\[y\] = \sum\_i E\[y\_i\] = \sqrt{n}$. But can I prove with high probability that $y$ is close to its mean?

I tried using Chernoff bound but unfortunately since $x\_i$'s and therefore $y\_i$'s are not independent, I can't apply it here.

I also tried using Chebyshev's inequality since $y\_i$'s seem to be negatively correlated but I can't calculate the variance of $y\_i$ and the proof would be messy even if I do.

Does anyone have any idea for a simpler proof?

# Answer
> 4 votes
You can bound the variance as follows. Let $b\_i$ be an indicator variable signaling that $x\_i$ was chosen. You are interested in $y = \sum\_i b\_i x\_i$. We have $$ \mathbb{E}\[(b\_ix\_i)^2\] = \frac{x\_i^2}{\sqrt{n}}, \quad \mathbb{E}\[b\_ix\_i\cdot b\_jx\_j\] = \frac{\sqrt{n}(\sqrt{n}-1)}{n(n-1)}x\_ix\_j = (1-O(1/\sqrt{n}))\frac{x\_ix\_j}{n}. $$ Therefore $$ \mathbb{E}\[y^2\]=\sum\_i \frac{x\_i^2}{\sqrt{n}}+\frac{1-O(1/\sqrt{n})}{n}\sum\_{i \neq j} x\_ix\_j \leq \frac{(x\_1+\cdots+x\_n)^2}{n} + \frac{\sum\_i x\_i^2}{\sqrt{n}}. $$ This shows that $$ \mathbb{V}\[y\] \leq n + \frac{\sum\_i x\_i^2}{\sqrt{n}} - (\sqrt{n})^2 = \frac{\sum\_i x\_i^2}{\sqrt{n}}. $$ The error in this estimate is quite small. The quantity $\sum\_i x\_i^2$ is maximized when $x\_i = n$ for some $i$, and we conclude that $\mathbb{V}\[y\] \leq n^{3/2}$. This is of course not very helpful, if you are trying to use Chebyshev's inequality!

A cheap way out is to "filter out" all elements which are at least, say, $n^{1/2+\epsilon}$. There are at most $n^{1/2-\epsilon}$ of these, and so it is very likely that the sample contains none of them. This allows us to essentially assume that all $x\_i$ are at most $n^{1/2+\epsilon}$, and so $$\sum\_i x\_i^2 \leq \left(\sum\_i x\_i\right) \max\_i x\_i \leq n^{3/2+\epsilon}.$$ This shows that the "effective" variance is at most $n^{1+\epsilon}$, and so with high probability the deviation from the mean is at most, say, $n^{1/2+2\epsilon}$.

You can probably get better bounds with improved technology, but this bound is already pretty reasonable. When $x\_1 = n$, you are always within distance at least $\sqrt{n}$ from the mean.

---
Tags: probability-theory, randomized-algorithms, sampling, chernoff-bounds
---


# Question
Title: Context free grammar for $L=\{a^n b c^n | n \ge0\}$
I'm having trouble with this problem. Can't find a CFG. Someone an idea?

$$L=\\{a^n b c^n | n \ge0\\}$$

# Answer
$$\begin{align}X&\to aXc\\ X&\to b\end{align}$$
> 7 votes

---
Tags: context-free
---


# Question
Title: Why are decision problems easier than the equivallent optimization problems?
Suppose that we have an optimization problem defined as follows:

$OPT$ = *Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$*

and the equivallent decision problem

$L\_{OPT}$ = *Given an input string defining $F$ and $f$ and a target value $u\in Q$, decide if there is a solution $x \in F$ so that $f(x) \geq u$*

Assuming that an efficient solution here is defined as an algorithm that runs in polynomial time in the length of the input, then if we have an efficient solution for $OPT$ it is trivial to see that we can get an efficient solution for $L\_{OPT}$. However, my teacher said that we could have that $L\_{OPT}$ has an efficient solution without $OPT$ having an efficient solution.

How is the latter possible? If we can efficiently solve $L\_{OPT}$, wouldn't we be able to run a binary search algorithm to find the solution for $OPT$?

# Answer
> 1 votes
If the objective function $f$ is easy to compute, you can use a solution to $OPT$ to solve $L\_{OPT}$: find some $x$ which maximises the objective function; compute $f(x)$ and output "yes" if it meets or exceeds the threshold $u$ (output "no" otherwise).

That is, $L\_{OPT}$ reduces to $OPT$ (for some suitable definition of the reduction type), and is in this sense easier.

If we let $OPTVAL$ be the function problem of computing the optimal value, but not the solution which has this value, $OPTVAL$ reduces to $L\_{OPT}$ via binary search. (Also $OPTVAL$ reduces to $OPT$: compute the optimal solution, then compute its value.)

Note that the reduction in one direction is a member of a smaller class of reductions than in the other: when solving $L\_{OPT}$ via $OPT$ you have the reduction $r$ and some post-processing $p$ such that for every instance $i$, the answer to $L\_{OPT}$ equals the output of $p(OPT(r(i))$. That is, it's a one-call reduction (but not tail call, which it can't be due to a type mismatch). The reduction from $L\_{OPT}$ to $OPTVAL$ is a multi-call reduction (with binary search it will make a logarithmic number of queries).

It's not clear to me that you can reduce $OPT$ to $OPTVAL$, not even with multiple calls: given an oracle which tells you what the optimal value is, how to you compute a solution with that value, generically?

However, most "natural" problems will probably let you do this. For instance, if we represent a graph $G$ as the number of vertices followed by an enumeration of the *complement* of the edge set and want to compute the chromatic number (smallest $k$ such that the graph is $k$-colourable), we can let $G'$ be $G$ with an edge added and ask our $OPTVAL$-oracle what the optimal value is. Whenever such a change doesn't increase the number of colours required, we learn of an additional constraint we can impose. Do so until it's no longer possible (at most polynomially often); now each vertex is adjacent to every vertex of any different colour, i.e. $u$ and $v$ have the same colour for every $(u, v) \in (V \times V) \setminus E$. Assign a colour to an uncoloured vertex, apply this rule and repeat until the graph is $k$-coloured.

One could generalise this: let solution-extractable optimisation problems be those such that with oracle access to the optimal value on smaller instances and the given instance, you can compute the optimal solution. Then you can multi-call reduce $OPT$ to $OPTVAL$ on solution-extractable problems (by construction). Of course, you can also compute optimal *solutions* to the smaller instances, since they are instances of a solution-extractable problem by assumption; maybe that helps to extract the optimal solution to the bigger instance.

It would be nice to have some generic constructions that enable this. Here's one idea:

Given some optimisation problem $P$ with a bound $k$ on the solution length, let instances of $Q$ be triples $(x, 1^{2k-l}, p)$ where $x$ are $P$-instances and $p$ has length $l$ be the problem of finding optimal solutions to $P$ which have $p$ as a prefix. If you can solve $OPTVAL\_Q$ then $P$ is solution-extractable: whenever $OPTVAL$ of $Q$ goes down both when you extend $p$ with a $0$ and when you extend it with a $1$, $p$ is a longest optimal solution; otherwise, extend $p$ with any value which doesn't decrease the objective function. Note that padding the problem with a number of ones equal to two times the bound on the solution length, we make the self-reductions downward when extending $p$.

Probably bit-by-bit solution extraction can be extended to chunk-by-chunk extraction if chunks have length at most $O(\log n)$ (since there's only polynomially many values to try out).

# Answer
> 0 votes
There is some degree of truth in it: For the decision problem, you need to *either* prove that a solution exists (often by finding one), or prove that none exists. If the target value is far away from the optimal value, then it may be easy to either find a solution or prove that non exists; the closer you choose a target value to the optimal value, the harder you can expect it to be.

You may have situations where you are never asked to solve an instance of the decision problem that is hard. For the optimisation problem, you *must* solve all problems, including the hard ones. For example, it will be trival to find a tour connecting all 48 continental capitols of the USA with a tour of less than 20,000 miles, and trivial to prove that a tour of 1,000 miles is not possible. But finding the shortest possible tour will be hard.

---
Tags: complexity-theory, optimization, reductions, decision-problem
---


# Question
Title: How to generate (Java) source code in academically acceptable way - using abstract syntax tree?
I am trying to do automated programming research: business software generation from the knowledge base that is implemented as Scheme (Lisp dialect) code (in the framework of http://opencog.org/ Atomspace). My question is - **how to generate Java source code in academically acceptable way?**

I know or I can imagine several ways:

* Raw code generation: I can predict what classes and what members can be and create one large literal constant that is the source code.
* Find or implement templating engine like Visual Studio's T4 templates
* Find something about code generation from the UML models. I don't know yet how MDD tools implement such generation
* I can genereate Java Abstract Syntax Tree in my Scheme code and then find tools generate Java source code from Java AST. Actually this could be - in my opinion - the most academically correct way that is also the best integrated in my workflow and that is the most extendable. My OpenCog Scheme Atomspace in effect is large hypergraph and Java AST is (hyper)graph to, so - AST generation reduces to the graph transformation. This seems the path to follow, isn't it?

There are some technical questions as well - are there tools that accept Java AST (in some form) and that generate Java source code? Can such AST-2-code tools be generated from the formal grammar of the programming language (https://docs.oracle.com/javase/specs/jls/se7/html/jls-3.html is example of the specification in the free, readable form)?

So - the question is - what is the best practice of code generation in the computer science academic project?

# Answer
It highly depends on what is the domain you are working on, i.e. why do you need to generate Java Source code anyway?.

Can you explain better what knowledge do you have stored in your knowledge base?.

The most "formal" method I can think of is by using the Java grammar and generate and abstract syntax tree as you mentioned. But it may or may not be appropriate, it depends on what are the task you want to solve.

If you want to use the grammar approach you may want to check antlr, I've used it to compare AST in plagiarism detection. Here is a repository with the grammars of many languages, including Java: https://github.com/antlr/grammars-v4
> 1 votes

# Answer
There is no such thing as "academically acceptable" or "academically correct". That's not a thing.

Rather, what matters is whether you make a significant, novel contribution, and whether you adequately demonstrate evidence that your work does represent a significant, novel contribution.

Instead, I suggest that you focus on the requirements for your application domain, and use good engineering principles to choose a solution that has technical merit and that meets those requirements, without worrying about whether it is "academic" enough.
> 0 votes

---
Tags: software-engineering, knowledge-representation, code-generation, syntax-trees
---


# Question
Title: Why is big omega of peak finding Omega(lg n)?
Why is big omega of finding a peak in an unsorted array Omega(lg n), not Omega(1)?

I understand that peak finding is O(lg n), because in the worst case, we find a peak in the last possible step, so when drawing a decision tree, the height of the tree (lg n) would be the worst case situation. However, in the best case, can't we get "lucky" and find a peak in the first try?

# Answer
I think you got a bit confused with the definition of Big-Omega ($\Omega$). The $\Omega(f(n))$ is a lower bound for an algorithm. It means that your algorithm's running time can not be less than $kf(n)$ where $k$ is a constant. And it applies to worst case not the best case.

**edit** If you calculate your algorithm running time as $c\log{n}$, it's asymptotic analysis says that it is $\Omega(\log{n})$.

big omega notation
> 1 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: n-state DFA that requires n-2 steps to check equivalence
We have a DFA $A = (Q,\Sigma, \delta, q\_0, F)$. States $p, q$ $\in Q$ are equivalent, $p \sim q$ if $ \forall w \in \Sigma ^ \ast$ $ \delta^\*(p,w) \in F \iff \delta^\*(q,w) \in F$

States $p,q$ are equivalent after $i$ steps, $p \sim ^i q$, if $ \forall w \in \Sigma ^ \ast$ such that $|w|\le i$ $ \delta^\*(p,w) \in F \iff \delta^\*(q,w) \in F$

$p \sim q$, if $ \forall i$ $p \sim ^i q$

State equivalence $\sim$ creates a partition $Q/\sim$ of states to equivalence classes.

I am trying to find a $n$-state DFA for all $n \ge 2$ where the state equivalence relation $\sim$ is equal to the state equivalence relation after $n - 2$ steps, $\sim^{n-2}$, but is not equal to the state equivalence relation after $n - 3$ steps, $\sim^{n-3}$.

So I'm searching for DFAs which require exactly $n - 2$ transitions to check the equivalence. I don't know how to approach this problem.

# Answer
Consider the following DFA on the alphabet $\\{0\\}$:

* The states are $q\_1,\ldots,q\_n$, with $q\_1$ initial and $q\_n$ final.
* $\delta(q\_i,0) = q\_{i+1}$ for $i \< n$, and $\delta(q\_n,0) = q\_n$.

Consider the pair of states $q\_1,q\_2$. For $i \< n-2$, $\delta^\*(q\_1,0^i),\delta^\*(q\_2,0^i) \notin F$, whereas $\delta^\*(q\_1,0^{n-2}) = q\_{n-1} \notin F$, $\delta^\*(q\_2,0^{n-2}) = q\_n \in F$.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Creating a temp array vs passing one in Mergesort
In my CS class, we've discussed two ways of dealing with the temporary array required for the merging phase of mergesort. One of them is to pass a full-size temporary array as a parameter, e.g. merge(array, tempArray, first, last), and another is to create a temporary array of appropriate size (or two half-sized arrays) in the function call, e.g.

```
merge(array, first, last):

...
leftArray = items from first to middle
rightArray = items from middle+1 to last
...

```

My CS professor is of the opinion that the first option will somehow have a performance (speed/memory) improvement over the second, but I don't understand why. Merging the arrays is a "tail" operation in mergesort, and so the second option doesn't seem like it will actually require more memory overall. Is the only reason why because memory allocation takes time?

Thanks!

# Answer
Most programming languages pass arrays as function arguments by reference: that is, the function is told where in memory the array is located, rather than being given all the elements directly. This means that, when you call something like

```
sort (int array A, int left, int right)

```

only three words of data are passed to the function, regardless of how big the array is – the address of `A` and the integer values describing the portion of the array to be sorted.

In contrast, the approach of creating two new arrays for the two halves requires allocating memory for the new arrays and copying the data across. Each of these takes a number of operations that is proportional to the size of the array. This is much less efficient, especially when you consider that the algorithm is recursive and will copy the array multiple times.
> 2 votes

# Answer
Memory management would be the only reason. In the second approach, you need to create $2n$ arrays total size of about $2n\log{n}$. If it is happening with a large $n$ or very small computing unit, you will face serious performance issues. Finally, you have to be careful with memory when you work with recursive functions. It easily cause memory overflow.
> 2 votes

---
Tags: sorting, mergesort
---


title: Definition of an immune set

text:
# Question
Title: Definition of an immune set
I'm reading a theorem about existence of a simple set.
The definition of an immune set can be found from here

A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ is infinite, but for every index ${\displaystyle e}$, we have ${\displaystyle W\_{e}{\text{ infinite}}\implies W\_{e}\not \subseteq I}$. Or equivalently: there is no infinite subset of ${\displaystyle I}$ that is recursively enumerable.

I am not able to understand this definition, because I couldn't come up with example.

# Answer
### Standard construction of a (co-c.e.) immune set

Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory.

The standard example of an immune set is as follows. Consider the set $$P = \\{\langle m, n\rangle \mid n \> 2 m \land n \in W\_m \\},$$ where $\langle {-}, {-}\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is an acceptable pairing function. There is a computable *selection* function $f$ for $P$, i.e., a partial function $f$ such that: for every $m \in \mathbb{N}$, if there is $n \in \mathbb{N}$ such that $\langle m, n \rangle \in P$ then $f(m)$ is defined and $\langle m, f (m) \rangle \in P$. (Why does such an $f$ exist? Exercise!)

Observe that $f$ is defined at infinitely many values. Indeed, there are infinitely many $m \in \mathbb{N}$ such that $W\_m$ is infinite, and at least at all of those $f(m)$ is defined.

Now let $S$ be the image of $f$, i.e., $$S = \\{n \mid \exists m \in \mathbb{N} . f(m) = n\\}.$$ We claim that the complement $I = \mathbb{N} \setminus S$ is immune:

1. Because $f(m) \> 2 m$ for every $m$ at which $f$ is defined, the set $I$ is infinite. Indeed, among the numbers $0, 1, \ldots, k$, at most $k/2$ can be enumerated by $f$, so at least all the rest will be in $I$.
2. Suppose we had an infinite c.e. set $U \subseteq I$. There is $m$ such that $U = W\_m$. Because $U$ is infinite, $f(m)$ is defined, hence $f(m) \in W\_m = U \subseteq I$. On the other hand, by the definition of $I$ we also have $f(m) \in S \not\in I$, a contradiction. Therefore $U$ cannot be infinite.

### The intuition behind the construction

Here is an informal explanation of $I$. The set $I$ has to satisfy two opposing conditions:

1. $I$ must be large enough (infinite).
2. $I$ must not be too large (for every infinite $W\_m$, it has to avoid an element of $W\_m$).

If we only cared about the first condition, we would take $I = \mathbb{N}$. If we only cared about the second condition, we would take $I = \emptyset$. But the two conditions work against each other.

Our first atempt could be this: for each infinite c.e. set $W\_m$, pick an element $f(m) \in W\_m$, let $S = \\{f(m) \mid \text{$W\_m$ is infinite}\\}$ and let $I = \mathbb{N} \setminus S$. Then we satisfied the second condition, since $f$ enumerated one element of each infinite $W\_m$, and we avoided all of those. However, there is no guarantee that $I$ is large enough – what if $S = \mathbb{N}$?. We can do better by making sure that

* $f$ is computable so that $I$ will end up being co-c.e.
* force $f$ to pick ever larger elements, so that we can be sure that it skips lots of numbers, which then end up being in $I$.

We achieve both of these with our constuction.

Let me finish with an interesting observation. In the *effective topos*, an immune set is an example of a subset of $\mathbb{N}$ which is neiter finite nor infinite.
> 8 votes

# Answer
An interesting example of immune set is the set of random numbers in Kolmogorov complexity.

The Kolmogorov complexity $k(n)$ of a number $n$ is the smallest $i$ such that $\varphi\_i(0) = n$. The idea is that we are comparing a number with alternative, effective descriptions of it.

A number is called random if $n \le k(n)$, that is, when it is its own shorter description.

Let $\mathcal{R}$ be the set of random numbers. It is easy to see that $R$ is not empty, and $\overline{R}$ is r.e.

Let us prove that $R$ is immune.

Let $A$ be an infinite subset of $R$. Let us suppose that it is r.e. and let $f$ be an effective enumeration for it, that is $A = cod(f)$.

By the $s\_{mn}$ theorem, there exists a total computable function $h$ such that $$\varphi\_{h(i)}(x) = f(\mu n. f(n) \> i)$$ Note that $h(i)$ "describes" a random number in $A$ larger than $i$ (that appears in the enumeration $f$ the earliest), and hence (being random) not describable with a program smaller or equal to $i$.

Now, take a fixed point $m$ for $h$. Then, the program $m$ describes a number that cannot be described by a program smaller or equal to $m$, which is clearly an absurdity. Hence, A cannot be r.e.

I could have been a bit more formal, but the idea of the proof is much more interesting than the details. Note the obvious analogy with Berry's paradox (the smallest number that cannot be defined with less than $m$ characters, where $m$ is the length of this definition).
> 5 votes

---
Tags: computability, semi-decidability
---


# Question
Title: How are partial measurements performed on a N qubit quantum circuit?
I am trying to understand quantum computing concepts and have gone through alot of websites and books such as: Quantum Computing by Mikio and https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lecture1.pdf So I do understand conceptually how to make measurements but I have enclosed images of a circuit i devised for an example and I am not able to attain the result of stage 5 (which is the output of the 1st two qubits only) when represented as matrices?. No paper/text explains this concept with proper examples. Any help is deeply appreciated. I have posted a similar question on the physics forum but they denied to respond as they assumed it some homework problem and had other issues. I am stuck and unable to move forward from here. Also it is not an assignment or anything. Thank you for your help.

# Answer
To measure a single qubit you:

1. Split the amplitude vector into "target qubit is Off" and "target qubit is On" parts.
2. Weigh up the parts. Add up the squared magnitudes of the amplitudes within each part. This gives you the probability of each.
3. Randomly pick one of the parts. (Or keep tracking both. Just make sure you never interfere parts from one with the other anymore.)
4. Renormalize the part(s). Divide by the squared-magnitude-sum, so the result totals to 100% again.

You'll probably find the calculations a lot easier if you do one operation at a time instead of a whole column at a time.

Also, you'll probably find my quantum circuit simulator Quirk helpful. It lets you drop state displays into the middle of circuits. Useful for checking your work. Here's your circuit in Quirk, with various displays sprinkled in:

The vector entries are not in quite the same order, but they agree with your results.

As you can see, the top measurement results are 50/50 random and the third qubit ends up pointing right (i.e. in the state $|0\rangle - |1\rangle$ regardless of the measurement outcome). (Trying to factor out a qubit often makes states easier to understand.)

Basically what has happened is easier to explain if you think in terms of the X gate as an X-axis control. Given the state of the third qubit during the CCNot, that "control" is satisfied. So really it's like the controls on the top two wires are a controlled-Z. This entangles the top two qubits.
> 3 votes

---
Tags: quantum-computing
---


# Question
Title: What characterises vertices at fixed indices in all topological orderings?
Let $G$ be a DAG with $v \in V$. Suppose that there exists some $i$ such that for all topological orderings $v\_1, \ldots, v\_n$ we have $v\_i = v$.

What's a set of necessary and sufficient conditions about $v$ for this to occur?

# Answer
**Theorem**: A given vertex $v$ always comes first, $i = 1$, iff it has no incoming edges and every other vertex has at least one incoming edge.

**Right-to-left implication**: no vertex other than $v$ can come first, since they all have incoming edges.

**Left-to-right**: for $v$ to come first it has to have in-degree 0. If some vertex $w$ has in-degree 0 with $w \neq v$ and there's a topological ordering where $w$ has a left neighbour $u$, then swapping $w$ and $u$ yields another topological ordering: the only vertices which have new relative positions are $u$ and $w$, and since $w$ has in-degree 0 no constraint is violated by putting it before $u$.

Repeatedly move the leftmost such $w$ one step to the left; this will end when one such $w$ comes first, contradicting the assumption that $v$ always comes first. Hence no $w$ exists.

**QED**

By a symmetric argument, a vertex always comes last if it alone has out-degree 0.

**Theorem**: $v$ is fixed-index iff it is comparable to every other vertex (i.e. for all $w$, either $w = v$ or there is a path from $v$ to $w$ or there is a path from $w$ to $v$).

**Right-to-left**: compare $v$ to all other vertices. All $w$ with a path to $v$ must come before $v$ and all $u$ with a path from $v$ to $u$ must come after $v$. That leaves only one index at which $v$ can occur.

**Left-to-right**: assume for the sake of contradiction that there exists some $w$ to the left of $v = v\_j$ in some topological ordering, where $w$ is incomparable to $v$, i.e. there is neither a path from $v$ to $w$ nor from $w$ to $v$. Let $u = v\_i$ be the rightmost among those, $i \< j$.

Consider $t = v\_{i+1}$. By $u$ being the rightmost incomparable vertex left of $v$, either $t = v$ or $t \< v$. If $u$ were comparable to $t$ then $u$ would also be comparable to $v$ (by transitivity through $t$) so it isn't. Hence we can swap $u$ and $t$ and remain topologically ordered. Continue doing this until $u$ and $v$ get swapped, contradicting $v$ being fixed-index.

Similarly derive a contradiction from the existence of an incomparable vertex to the right of $v$. Hence there is no incomparable vertex.

**QED**

*Some consequences*:

Let a digraph $G$ be Weakly Connected if the undirected counterpart is connected; define Weakly Connected Components analogously.

Any interleaving of the topological orderings of two weakly connected components is a topological ordering of their union. In particular, one can put the entire ordering of one component immediately before or after a given vertex in the other component, so no vertex can be fixed-index (so long as both components are non-empty).

**Corollary**: a DAG with a fixed-index vertex is weakly connected.

A more direct and constructive proof: $path(s, v) + path(v, t) = path(s, t)$ where the precise definition of $path$ and $+$ is left as an exercise ;-)

There is no implication in the other direction: consider the complete bipartite graph on 2+2 vertices, edges left-to right, with $a, b$ on the left and $c, d$ on the right; then $a$ and $b$ come before $c$ and $d$, but $a$ and $b$ can always be swapped, and so can $c$ and $d$. This graph is weakly connected but has no fixed-index vertex.

It is also not the case that all paths from $v\_i$ to $v\_k$ go through $v = v\_j$ when $i \< j \< k$. For (counter)example, $V = \\{a, b, c\\}$ and $E = \\{(a, b), (a, c), (b, c)\\}$ which has only one topological ordering. Let $(v\_i, v, v\_k) = (a, b, c)$; then there is a path of length 1 from $a$ to $c$ which doesn't go through $b$.
> 2 votes

---
Tags: graphs
---


title: Numbering of computable functions

text:
# Question
Title: Numbering of computable functions
Is there a numbering (not Gödel numbering) of all computable functions $U(p, x)$, such that the set of numbers of functions defined in zero is exactly the set of even numbers. More formally: $I = \\{p,\ |\ U(p, 0)\ \mathrm{defined}\\} = 2\mathbb{N}$.

My guess that it's true. But I'm not sure how to prove it.

## Ideas:

We can construct a numbering of all computable functions, defined in zero using the function $F(p, x, t)$ which is equal to $0$ if $U(p, x)$ hasn't finished work in $t$ steps and $1$ in other case. We can do it because set of pairs $(p, t)$ is enumerable.

Then, having this function $V(p, x)$ and some other numbering $U(p, x)$ we can construct numbering

$$ U'(p, x) = \begin{cases} V(\frac{p}{2}, x)\ \ if\ p \vdots 2\\ U(\frac{p + 1}{2}, x)\ \ if\ p \not\vdots 2 \end{cases} $$

# Answer
Hint:

* There are countably many computable functions defined at zero, and countably many computable functions undefined at zero.
* There are countably many natural numbers divisible by 2, and countably many natural numbers not divisible by 2.

Put the two facts together.
> 0 votes

---
Tags: computability, discrete-mathematics
---


# Question
Title: Sum of all distances in connected DAG in $O(n\log n)$
I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows: For every node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are given as input.

I need to compute the sum of all of the distances between all pairs of different vertices, i.e., to compute $\sum\_{u\<v} d(u,v)$, which is the sum of the distances for each pair $u,v$ such that $u\<v$.

For example, suppose $n=4$, and the edge lengths are $1,1,1,1$. Then the pairs along with their distance would be $(1,2):1,(1,3):2,(1,4):3,(2,3):1,(2,4):2,(3,4):1$, so the total sum of distances would be $1+2+3+1+2+1=10$.

I tried Dijkstra's Algorithm (time complexity $O(n\log n)$) on every node but the time complexity is $O(n^2 \log n)$ which is inefficient. Is there a way to reduce it to $O(n \log n)$ or less?

# Answer
I think the question is not clear enough, but what I understood is that we want to find the sum of all the shortest path from $u$ to $v$ such that $u \< v$. The trick is that the graph is actually a directed chain, so we can represent the edges in an array $A$ of length $n - 1$.

The brute force formula is $\sum\_{i=1}^{n -1} \sum\_{j=i + 1}^{n} \delta(i,j)$. Where $\delta(i,j)$ is the shortest path from $i$ to $j$, because our graph is a chain, we can simply express this as $\delta(i,j) = \sum\_{k=i}^{j - 1} A\_{k}$. In the example you provided with 4 nodes $A =\[1,1,1\]$. The above formulas have a complexity of $\Theta(n^3)$, which can be improved to $\Theta(n^2)$ by doing a prefix sum on $A$. But a pattern can easily detected by looking carefully where the items of $A$ repeat.

For example, if $A = \[1,2,3\]$ the above formulas would provide the following operations:

$(1 + (1+2) + (1+2+3)) + (2 + (2+3)) + (3)$, here each "big parenthesis" is the computation from each node. The last node is obviously ignored.

We can rewrite this as:

$3 \*(3 * 1) + 2 \*(2 * 2) + 1 * (1 * 3)$

For example $3 \*(3 * 1)$ means that $3$ was repeated once ($1$) on $3$ parenthesis. Likewise, $ 2 \*(2 * 2)$ means that $2$ is repeated two times on $2$ parenthesis and so on.

The repetitions have a pattern: the number of times it appears on a "big parenthesis" is actually the index of the element, but the number of times is repeated inside the parenthesis decreases as the index increases because less paths starts from nodes that are closer to the end of the chain. Work through the example and you will find the pattern, make sure you understand this paragraph.

As you mentioned that you have not found the pattern, the above discussion can be summarized in this formula: $\sum\_{i=1}^{n - 1} A\_{i} * i * (n - i)$. Remember that $n$ is equal to the number of nodes and $A$ contains the edges, which are $n - 1$.

The proof of the above intuition is left as an exercise for the reader :-).

EDIT: Just in case, the complexity is $\Theta(n)$ because we only do a loop to compute the summation and the inner operations are $\Theta(1)$. Depending on how you represent the graph in the input, the memory complexity can be either $\Theta(1)$ or $\Theta(n)$.
> 1 votes

# Answer
From the comments it seems you're interested in the *sum* of the distances between all pairs.

As in your comment, let $a\_i$ be the weight of the edge between node $i$ and node $i+1$. The weight of the path between node $i$ and node $j$ is $a\_i+\cdots+a\_j$. Using this, it is easy to calculate the answer for small $n$:

* $n=2$: $a\_1$
* $n=3$: $a\_1+(a\_1+a\_2)+a\_2 = 2a\_1+2a\_2$
* $n=4$: $a\_1+(a\_1+a\_2)+(a\_1+a\_2+a\_3)+a\_2+(a\_2+a\_3)+a\_3 = 3a\_1+4a\_2+3a\_3$
* $n=5$: $4a\_1+6a\_2+6a\_3+4a\_4$
* $n=6$: $5a\_1+8a\_2+9a\_3+8a\_4+5a\_1$

And so on. Let's put these numbers in a table (we'll stop at the middle of each coefficient vector): $$ \begin{array}{ccccc} 1 \\ 2 \\ 3 & 4 \\ 4 & 6 \\ 5 & 8 & 9 \\ 6 & 10 & 12 \\ 7 & 12 & 15 & 16 \\ 8 & 14 & 18 & 20 \\ 9 & 16 & 21 & 24 & 25 \\ 10 & 18 & 24 & 28 & 30 \end{array} $$ The pattern is reasonably obvious to spot.

For the proof, you have to calculate in how many shortest paths does the edge between node $i$ and node $i+1$ participates — this is the coefficient of $a\_i$.

All details left to you.
> 0 votes

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


# Question
Title: Method for finding Hyperrectangle that a coordinate is within
I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to efficiently figure out which hyperrectangle a given coordinate is within.

I do not always have too many hyperrectangles, so just iterating through the set of partitioned hyperrectangles is often fine to see which one a given coordinate is in. However, I sometimes have larger quantities of hyperrectangles and I want to write something that scales better than simply iterating through the set.

My first thought is to consider some hashing approach analogous to spatial hashing but am not sure the best way to go about formulating this since the hyperrectangles could be any dimension. Any thoughts?

# Answer
> 2 votes
The best algorithm will depend on the proportion of hyperrectangles to dimensions. If I understand correctly, what you want is to do a first-pass computation where you build a data structure in order to get a sublinear algorithm (in terms of the number of hyperrectangles) that will tell you which hyperrectangle a point is in.

I think a binary search tree would work well. At each branch of the tree you can split the set of hyperrectangles in half by performing a check to see if coordinate X\_i is greater than or less than some value. You want to include in each set every rectangle that is at least partially inside the split region. For example, if you have a rectangle from (0,0) to (2,2) and you split on the first coordinate at 1, you would want to include this rectangle in both sets. Continue until you have only single hyperrectangles - these will be the leaves of the tree.

How and when you split is up to you. Each time the number of hyperrectangles on both sides should be roughly equal. An approach where you just cycle through the dimensions would probably work well. For example, first you split halfway along X\_1, then halfway along X\_2, ... eventually you split halfway along X\_d, then you start over if necessary.

If n is the number of hyperrectangles, then the construction step should take about O(n\*log(n)), and the lookup step should take about O(log(n)) each time.

# Answer
> 0 votes
Have you considered spatial indexes (other than spatial hashing)? It sounds like you could use a simple quadtree (up to 10 dimensions) or R-Tree (an R\*Tree/RStarTree works well up to 50 dimensions or even more). In the case of R-Tree, an STR-Tree may be faster if you have can insert everything at once (bulk loading) rather than loading hyperrectangles one by one.

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


# Question
Title: Every LEFT-RESET Turing machine has an equivalent conventional Turing machine
I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, RESET}, and the transitions for the conventional Turing machine are {Left, Right}. Here is the general outline of my proof:

Given a LEFT-RESET Turing machine $T\_1$ and a conventional, I will prove that $T\_1$ has an equivalent conventional Turing machine $T\_2$. There are two possible transitions for $T\_1$: right and reset. The right transition of $T\_1$ is identical to the right transition of $T\_2$. When $T\_1$ performs a reset, $T\_1$ moves its read-write head left until it reaches the leftmost cell on the tape. Therefore, a LEFT-RESET Turing machine is equivalent to a conventional Turing machine. Q.E.D.

Do I have to prove that there is a series of transitions on $T\_1$ that are equivalent to a single left transition on $T\_2$? Other write-ups I have seen include this, but if the LEFT-RESET Turing machine cannot perform a traditional left transition as an operation, I do not understand why it is part of the proof.

# Answer
The other write-ups you mention show that the two models are *equivalent*. That is, they also show that a normal Turing machine can be simulated by a left-reset Turing machine.
> 1 votes

---
Tags: turing-machines, proof-techniques
---


# Question
Title: Why are mapping reductions from incomputable Languages OK?
For example, many reductions from $A\_{TM}$ will often have the lines:

```
Simulate M on w:
    if M accepts
       ...
    else

```

But: a reduction is a computable function, right? So why are we allowed to say "if M accepts"? Also, I can take the same logic and reduce $A\_{TM}$ to a deciable language: Let L be the empty language. Clearly L is decidable.

Given $(M,w)$:

```
 Output output:
      If M accepts w
            output = '0'
      else
            output = $\emptyset$

```

Obviously I'm wrong here. But why? Thanks in advance.

# Answer
> 0 votes
There are two options:

* Either the pseudocode means "run $A\_{TM}$ on the pair $M,w$" when it says "Simulate $M$ on $w$";
* or it really means to simulate $M$ on $w$, and if it ever stops then do something; there is no "else" clause in that case.

---
Tags: automata, reductions
---


# Question
Title: Showing two Turing machines decide different languages
I want to figure out how two languages are different. If we have TM M and TM N, how would I figure out if the languages are different? My intuition is that if a M accepts an input a and N does not then that would prove the languages are different, right?

I'm not too sure if I'm thinking of this correctly.

# Answer
> 2 votes
Languages are just sets (of strings). As with any pair of sets, you show that they're different by showing that one set contains an element that's not in the other. Note that, in general, the problem of determining whether two Turing machines decide the same language is undecidable, so there's no algorithm you can use to generate such a string, in general. But, for any two given Turing machines, you can still try to figure it out.

---
Tags: formal-languages, turing-machines
---


# Question
Title: Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$
So, I'm refreshing my undecidablility knowledge, and I came across this statement reading about Post's Correspondence Problem on Wikipedia:

> A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.

I'm a little confused about how to parse this sentence formally.

Let $POST(n) = \\ \\{((a\_1, b\_1),\ldots, (a\_n, b\_n) \mid a\_i, b\_i \in \\{0,1\\}^\*, \\ \exists j\_1 \ldots j\_m \ldotp a\_{j\_1} \cdots a\_{j\_m} = b\_{j\_1} \cdots b\_{j\_m} \\}$

Which of the following is true?

* $\forall n \ldotp n \geq 5 \implies POST(n)$ is undecidable
* $\bigcup\_{n \geq 5} POST(n)$ is undecidable

i.e. if I'm showing that a problem is undecidable, can I show that that problem can be used to solve any 5-tile PCP instance? Or am I not allowed to make such assumptions on the number of tiles?

# Answer
It is the first version: $\forall n,\\,n\geq 5\Rightarrow\\,POST(n)$ is undecidable. The reason for the number $5$ is explained in the article of Turlough Neary cited in wikipedia page. The case $n=2$ is proven in

A. EHXENFEUCHT, J. KARHUMAKI, G. ROZENBERG, *"THE (GENERALIZED) POST CORRESPONDENCE PROBLEM WITH LISTS CONSISTING OF TWO WORDS IS DECIDABLE"*, Theoretical Computer Science 21 (1982) 119-144.
> 4 votes

---
Tags: formal-languages, computability, reductions, undecidability
---


title: Residual Graph in Maximum Flow

text:
# Question
Title: Residual Graph in Maximum Flow
I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow?

Can anyone help me understand the concept of Residual Graph?

How does the Algorithm change in Undirected Graphs?

# Answer
The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows.

Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f\_e/c\_e$ denotes both the flow $f\_e$ pushed through an edge $e$ and the capacity $c\_e$ of this edge):

One possible greedy approach is the following:

1. Pick an arbitrary augmenting path $P$ that goes from the source vertex $s$ to the sink vertex $t$ such that $\forall e \\: (e \in P \rightarrow f\_e \lt c\_e $); that is, all of the edges in $P$ have available capacity.
2. Push the maximum possible flow $\Delta$ through this path. The value of $\Delta$ is determined by the *bottleneck* of $P$; that is, the edge with minimum available capacity. Formally, $\Delta=\min\_{e \in P} (c\_e-f\_e)$.
3. Go to step 1 until no augmenting paths exist.

That is, find a path with available capacity, send flow along that path, and repeat.

In $G$, one possible execution of the above heuristic finds three augmenting paths $P\_1$, $P\_2$, and $P\_3$, in this order. These paths push 2, 2, and 1 units of flow, respectively, for a total flow of 5:

Choosing paths in this order leads to an optimal solution; however, what happens if we select $P\_3$ first (i.e., before $P\_1$ and $P\_2$)?

We get what is called a *blocking flow*: no more augmenting paths exist. In this case, the total flow is 3, which is not optimal. This issue can be resolved by allowing *undo* operations (i.e., by allowing flow to be sent in reverse, undoing work of previous iterations): simply push 2 units of flow backwards from vertex $w$ to vertex $v$ like this:

Encoding these allowed undo operations is the main goal of the **residual graph**.

A residual graph $R$ of a network $G$ has the same set of vertices as $G$ and includes, for each edge $e=(u,v) \in G$:

* A forward edge $e'=(u,v)$ with capacity $c\_e-f\_e$, if $c\_e-f\_e \gt 0$.
* A backward edge $e''=(v,u)$ with capacity $f\_e$, if $f\_e \gt 0$.

For example, consider the residual graph $R$ that is obtained after the first iteration of the greedy heuristic when the heuristic selects $P\_3$ first (that is, when it gets the blocking flow):

Note that the *undo* operation that pushes 2 units of flow from $w$ to $v$ is encoded as a forward (augmenting) path from $s$ to $t$ in $R$:

In general:

> When an augmenting path $P'$ is selected in the residual graph $R$:
>
> * Every edge in $P'$ that corresponds to a forward edge in $G$ increases the flow by using an edge with available capacity.
> * Every edge in $P'$ that corresponds to an edge going backwards in $G$ undoes flow that was pushed in the forward direction in the past.

This is the main idea behind the Ford–Fulkerson method.

The Ford–Fulkerson method proceeds in exactly the same way as the greedy approach described above, but it only stops when there are no more augmenting paths in the residual graph (not in the original network). The method is correct (i.e., it always computes a maximum flow) because the residual graph establishes the following **optimality condition**:

> Given a network $G$, a flow $f$ is maximum in $G$ if there is no $s-t$ path in the residual graph.
> 43 votes

# Answer
The intuition behind the residual network is that it allows us to "cancel" an already assigned flow i.e. if we have already assigned 2 units of flow from $A$ to $B$, then passing 1 unit of flow from $B$ to $A$ is interpreted as cancelling one unit of the original flow from $A$ to $B$.
> 4 votes

---
Tags: algorithms, graphs, network-flow
---


title: Pumping Lemma CFL

text:
# Question
Title: Pumping Lemma CFL
For proving a language is not CF, I was wondering when we split up the string to 5 pieces are we allowed to proportion it anyway as long as we satisfy the following conditions :

\begin{align} |vwx| &\le p \text{ (pumping length)}\\ |vx| &\> 0 \end{align}

Could I possibly make the $u$ value take on a majority of the string?

# Answer
From the pumping lemma for context free languages from Wikipedia, $$(\forall L\subseteq \Sigma^\*)(\text{context free}(L)\implies\\ ((\exists p\ge1)((\forall s\in L)((|s| \ge p)\implies\\\((\exists u,v,w,x,y\in\Sigma^\*)\\\(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))) $$

Let $i$ be the statement $$\text{context free}(L)$$ and $j$ be the statement $$((\exists p\ge1)((\forall s\in L)((|s| \ge p)\implies\\\((\exists u,v,w,x,y\in\Sigma^\*)\\\(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))$$

The pumping lemma states that $i\implies j$ is true for all context free languages. Its contrapositive is $\neg j\implies \neg i$. To show that a given language is not context free using the pumping lemma, you assume that $i$ is true, then show that $\neg j$ is true, which implies that $\neg i$ is true, leading to a contradiction.

So, $\neg j$ is, $$((\forall p\ge1)((\exists s\in L)((|s| \ge p)\implies\\\((\forall u,v,w,x,y\in\Sigma^\*)\\\neg(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))$$

which gives $$((\forall p\ge1)((\exists s\in L)((|s| \ge p)\implies\\\((\forall u,v,w,x,y\in\Sigma^\*)\\\(\neg(s=uvwxy) \lor \neg(|vwx|\le p) \lor \neg(|vx|\ge1) \lor \neg((\forall n\ge0)(uv^nwx^ny\in L)))))))$$

Note that the contrapositive of $j$ needs that at least one of the statements of the lemma be false for *all* ways to split strings $s$ in $uvwxy$. So, you need to consider all possible ways in which they can be split.

---

If the statements are not clear, the following is an alternative:

$i$:

The language $L$ is context free.

$j$:

There exists $p\ge1$ such that for all strings $|s|\in L$ and $s\ge p$, there exists a way to split $s$ as $uvwxy$ such that

1. $|vwx|\le p$
2. $|vx|\ge1$
3. $uv^nwx^ny\in L$ for all $n\ge 0$

which gives $\neg j$ to be

For all $p\ge1$, there exists string $s\in L$ and $|s|\ge p$, such that *for all ways* to split $s$ as $uvwxy$, at least one of the following is false

1. $|vwx|\le p$
2. $|vx|\ge1$
3. $uv^nwx^ny\in L$ for all $n\ge 0$

Note that the statement uses "for all ways to split $s$ as $uvwxy$", and hence, you cannot make assumptions on the length of $u$.
> 1 votes

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


title: How to generate an LL(2) parse table?

text:
# Question
Title: How to generate an LL(2) parse table?
The algorithms I've seen for building an LL(1) parse table involve calculating `first` and `follow` sets such that:

```
predict(nonterminal, production) ==
     if epsilon in FIRST(production):
         first(production) union follow(nonterminal)
     else:
         first(production)

```

where production is a sequence of symbols which can include nonterminals, terminals, and epsilon.

what's the algorithm for an LL(2) parse table?

# Answer
There is a pretty reasonable discussion in this essay from the SLK parser generator.

Basically, you just need to extend $FIRST$ and $FOLLOW$ to be $FIRST\_k$ and $FOLLOW\_k$, meaning the first / following $k$ symbols. The basic principle is the same, but when $k \> 1$ there is a complication, leading to the distinction between "strong" and regular grammars.

The naming is a bit counterintuitive; the parsing table for a strong grammar can be generated by an easier but less powerful algorithm, so the strong grammars are in a sense weaker; they make a stronger guarantee about predictability.
> 2 votes

---
Tags: compilers, parsers, ll-k
---


# Question
Title: Why cannot we reduce the Emptiness problem of LBA to the Acceptance problem of LBA?
I am a little bit confused about the emptiness problem of the linear bounded automaton (LBA). I know that this problem is undecidable. However if we ***assume*** that is decidable, what could be wrong if we reduce it to the acceptance problem of LBA?

# Answer
Since the acceptance problem for LBAs is decidable, if you could reduce th emptiness problem to the acceptance problem, then the emptiness problem for LBAs would be decidable. However, the emptiness problem for LBAs is not decidable. This shows that we cannot reduce the emptiness problem to the acceptance problem.

It seems that you are confused about the direction of the reduction. When reducing problem A to B, we show how to solve problem A using problem B, not the other way around.
> 1 votes

---
Tags: formal-languages, undecidability, linear-bounded-automata
---


title: what is routine induction?

text:
# Question
Title: what is routine induction?
I read a paper which mentioned routine induction many times. But when I google it, there are nothing showed up.

I think routine induction means the induction on the structure, analyzing possible cases in proofs. am I right?

Just to make sure, I am asking it here.

# Answer
> 4 votes
I'm going to give a bit more nuanced answer.

To begin, if you are going to read many programming language theory and related research papers, get used to the phrase "by structural induction". It's not uncommon that these three words are the entirety of a proof sketch in a paper. The majority of proofs in this area are *very* boring but also tedious. So boring and tedious that we've written programs to write these proofs for us. If a computer can quickly find these proofs fully formally with a one-line proof script, this elliptical style is moderately justified.

Sometimes an author will say that you can find a proof by "following your nose". This means that the structure of the theorem strongly suggests one (or at most a few) next steps. This (combined with some searching) is what's behind Coq's `auto` tactic, Agda's Agsy tool, and the Djinn tool. Structural induction is the "follow your nose" step you get when faced with the problem of proving something about all members of an inductively defined type like an abstract syntax tree. So an elliptical "by structural induction" is really the statement of "do the obvious thing; there are no surprises".

# Answer
> 4 votes
The word *routine* is used here in its non-technical sense: normal, usual, plain. It just means a proof by induction where nothing special happens.

---
Tags: proof-techniques
---


# Question
Title: Why L is defined as L = SPACE$( \log n)$ instead of L = SPACE$(\log^2 n)$ or L = SPACE$(\sqrt n)$?
$L$ is the class of languages that are decideable in logarithmic space on a deterministic Turing machine. In other words,

> L = SPACE$( \log n)$

But why $\log n$, instead of $\log^2 n$ or $\sqrt n$. This is what, I find out in the Theory of computation book by Michael Sipser Theory of computation book by Michael Sipser, Chapter 8

> Logarithmic space is just large enough to solve a number of interesting computational problems, and it has attractive mathematical properties such as robustness even when mathematical model and input encoding method change.

I am not able to understand completely, how mathematical properties and input encoding are related to defining L complexity class.

# Answer
> 5 votes
The complexity class $\mathsf{L}$ satisfies many desirable properties:

* It is closed under concatenation and iteration.
* The corresponding function class is closed under composition.
* The same complexity class is obtained for any number of work tapes.
* It is resilient under "reasonable" input transformations with polynomial blowup (see below).
* It can accommodate most known NP-hardness reductions.
* It is a subset of $\mathsf{P}$.
* It supports pointers indexing the input.

What is an input transformation? Consider the case of graphs. We can encode a graph either as an adjacency matrix of as adjacency lists. We can convert between the two in logspace, and so a graph problem which is in $\mathsf{L}$ under one of them is also in $\mathsf{L}$ under the other.

Logspace is the natural space analog of $\mathsf{P}$, considering the containment $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{f(n)})$.

It also shows up in the refined Schaefer's dichotomy theorem, as the lowest non-trivial complexity class.

# Answer
> 0 votes
Why? Because that's the definition. Why is $\pi$ defined to be the ratio between the circumference and diameter of a circle, rather than the base of natural logarithms or the golden ratio? Because it is.

You seem to be looking at it backwards. It's not that somebody said, "Hmm. My name's Logan and I want to have a complexity class called **L**. What class should I choose?" Rather, the class of problems that can be solved in $O(\log n)$ steps for inputs of length $n$ is a useful and important class of problems. People talked about it a lot, so they needed to give it a name. The name they chose was **L**, which is a logical and mnemonic name for that class of problems. Just like people said, "Hey, we seem to be using this circumference-to-diameter ratio a lot. What name should we give it?" rather than, "Hey, $\pi$'s a pretty shape. We should use it for a constant!"

---
Tags: complexity-theory, space-complexity
---


title: Interrupts and polling

text:
# Question
Title: Interrupts and polling
Are Interrupts really just an abstracted form of polling?

I saw a system-file-watcher library that stated it used polling, as opposed to listening for events. Is the .NET framework SystemFileWatcher class just an abstraction of polling?

In a computer, interrupts are stacked, and the CPU checks the interrupt stack after every cycle, so this is pretty much polling, right? - Albeit more efficient than checking every individual device.

# Answer
> 1 votes
Not really.

Polling requires CPU cycles to poll a device and respond if needed. Detecting interrupts takes up no extra CPU cycles and is almost always done in parallel with instructions being executed. CPU cycles are only used up in servicing the interrupt.

Also, with polling, you have a control over how and when you poll devices whereas interrupts are generally out of sync with the program (or at least, you cannot exert too much control over when they arrive).

The mindset behind polling driven and interrupt driven code/architecture is entirely different.

---
Tags: software-engineering, cpu, intervals
---


# Question
Title: What's the difference between Memory Byte (Mb) and Mega Byte (mb)
I am currently running my head around to understand if i am actually getting it correct or not?

A memory chip with 1 byte cell size has 12 address lines. How many data lines does the chip have? What is the memory size of the chip in Mbytes?

12 address lines means it has 2^12 cells in the memory, right?

Then what is MBytes size?

So confusing.

# Answer
Ok - there's a lot of muddle here!

"Memory Byte" isn't a term at all. Nor is "mb" - that would mean "milli-bit", which isn't really a thing!

MB means Megabyte - which means either 1,000,000 bytes, or 1,048,576 bytes (1024x1024), depending on context. To avoid confusion, the term "Mebi" (implying binary form) is often used to mean the 1024 version, abbreviated MiB.

As a rule of thumb, memory sizes are usually quoted in mebibytes or similar - so a 16GB RAM is really 1,073,741,824 x 16. Disks are usually measured in decimal millions, because it makes them sound larger for marketing purposes.

Uppercase 'B' usually means bytes, and lowercase 'b' means bits. So "Mb" denotes megabits. As a rule, storage capacities are measured in bytes, and communication speeds are measured in bits/s, so you usually see 20Mbs meaning 20 megabits per second.

With respect to memory addressing: the number of address lines will relate to the number of memory "words" that can be individually addressed - and as you say, 12 address lines means 2^12 words can be addressed, which is 4096. How big is a "word"? That depends on the specific memory device.

For a small byte-addressable memory, the word unit is a byte, and each byte is accessed one at a time, so *there will be 8 data lines*. If it has 12 address lines, *then it is a 4KB memory, and would be called a "4k x 8" memory* \- that's the specific answer to your question. But some devices are accessed 16 bits at a time (eg a 32k x 16), or even just 1 bit at a time.

In short, the number of address lines is independent of the memory's word size. But if you know the capacity of the device in bytes and you know the word size, you can calculate the size of the address bus.

Note that you can take two byte-addressable memory devices, wire their address buses together, and put them next to each other to create a 16-bit data bus: one device produces the bottom 8 bits and the other produces the top ones. That's how computer DIMMs work: lots of 4- or 8-bit wide memories ganged together to produce an effective 64-bit wide memory bus.
> 4 votes

# Answer
To answer the questions you actually asked:

*A memory chip with 1 byte cell size has 12 address lines. How many data lines does the chip have? What is the memory size of the chip in Mbytes?*

Assuming the standard 8-bit byte *(note: historically there HAVE been other choices!)*, then this chip has 8 data lines. Its total capacity is 4096 bytes, i.e (1/256)Mbyte. If you wanted to use such chips to build a useful main memory, you would need a whole lot of them (my advice: choose chips with a greater capacity).

*12 address lines means it has 2^12 cells in the memory, right?*

That is correct. But be aware: different chips could have different cell sizes. For example, one could have a chip with word-sized cells, where a word has 32 bits. With 12 address lines, such a chip would hava a capacity of 16384 bytes, but would only be able to access them in 4-byte chunks. If you wanted to address individual bytes on such a chip, you would have to 'set aside' the two low-order address bits in order to access the word containing that byte, then use those two address bits to pick the byte out of the word.
> 1 votes

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