# Question
Title: Solving T(n) = 2T(n/2) + log n with the recurrence tree method
I was solving recurrence relations. The first recurrence relation was

> $T(n)=2T(n/2)+n$

The solution of this one can be found by Master Theorem or the recurrence tree method. The recurrence tree would be something like this:

The solution would be:

$T(n)=\underbrace{n+n+n+...+n}\_{\log\_2{n}=k \text{ times}}=\Theta(n \log{n})$

Next I faced following problem:

> $T(n)=2T(n/2)+\log{n}$

My book shows that by the master theorem or even by some substitution approach, this recurrence has the solution $\Theta(n)$. It has same structure as above tree with the only difference that at each call it performs $\log{n}$ work. However I am not able to use same above approach to this problem.

# Answer
> 6 votes
The non-recursive term of the recurrence relation is the *work* to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, so you need at first to find the total work on the level $k$ and then to summarize this work over all the tree levels.

For example, if the work is constant $C$, then the total work on the level $k$ will be $2^k \cdot C$, and the total time $T(n)$ will be given by the following sum:

$$T(n) = \sum\_{k=1}^{\log\_2{n}}2^k C = C(2^{\log\_2{n}+1}-2) = \Theta(n)$$

However, if the work logarithmically grows with the problem size you'll need to accurately compute the solution. The series would be like the following:

$$T(n)=\log\_2{n}+\underbrace{2\log\_2(\frac {n} {2})+4\log\_2(\frac {n} {4})+8\log\_2(\frac {n} {8}) + ....}\_{\log\_2{n} \text{ times}}$$

It'll be a quite complex sum:

$$T(n)=\log\_2{n}+\sum\_{k=1}^{\log\_2{n}}2^k \log\_2(\frac {n} {2^k})$$

I'll temporarily denote $m=\log\_2{n}$ and simplify the summation above:

$$\sum\_{k=1}^{m}2^k \log\_2(\frac {n} {2^k})=\\\=\sum\_{k=1}^{m}2^k(\log\_2{n}-k)=\\\=\log\_2{n}\sum\_{k=1}^{m}2^k-\sum\_{k=1}^{m}k2^k=\\\=\log\_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Here I used a formula for the $\sum\_{k=1}^{m}k2^k$ sum from the Wolfram|Alpha online symbolic algebra calculator. Then we need to replace $m$ back by $\log\_2{n}$:

$$T(n)=\log\_2{n}+2n\log\_2{n}-2\log\_2{n}-2n\log\_2{n}+2n-2$$ $$=2n-\log\_2{n}-2=\Theta(n)$$

Q.E.D.

---
Tags: recurrence-relation
---


# Question
Title: Want to know the time complexity inner for loop which is partially iterating the array
**Question:** Find out next increasing value of each element in this below array.

```
int[] array = { 5, 2, 7, 10, 4, 12}

```

e.g)
5's nextIncreasingValue: 7
2's nextIncreasingValue: 7
7's nextIncreasingValue: 10
...
12's nextIncreasingValue: -1

**Implementation:**

```
for(int i = 0; i < array.length; i++) {
        int nextIncreasingValue = -1;
    for (int j = i + 1; j < array.length; j++) {
        if(array[j] > array[i]) {
            nextIncreasingValue  = array[j];
            break;
        }
    }
    PRINT("For " + i + "th next increasing value is: " + j)
}

```

Now I want to know the time complexity of this program, since each time inner for loop is skipping some of the elements on iteration. So it cannot be O(n^2) even in the worst case.

Kindly explain me what will be the time complexity?

**O(n) Solution using stack:**

```
Stack s = new Stack();
for(int i = 0; i < array.length; i++) {
   while(!s.isEmpty() && array[i] > s.peek()) {
         PRINT  s.pop() NIV is array[i];
   }
   s.push(array[i]);
}
while(!s.isEmpty())
   PRINT  s.pop() NIV is -1;

```

# Answer
It **is** $O(n^2)$. Consider `array = [n, n-1, n-2, ..., 1]`.

---

BTW, you could implement this in $O(n)$ by scanning from the end of the array:

* Suppose the next-increasing-value (NIV) of `a[i+1]` is `x`.
* We want to find the NIV of `a[i]`, which we observe that:
    1. If `a[i+1] > a[i]`, then the NIV is `a[i+1]`
    2. If `x > a[i]`, then the NIV is `x`
    3. Otherwise, `a[i]` is already the maximum value, so the NIV = -1.

Using this we could work backward from `a[n-1]` to `a[0]` to find the NIV of each entry in $O(n)$ time.
> 9 votes

# Answer
This should be a comment, but I don't have that rep yet on this stackexchange.

kennytm's answer is right, I just want to add my rule of thumb:

whenever you are iterating over an array/list/other linear data structure, regardless of how many elements you skip or how early you break out, the big-O notation is always O(n). Whenever you call that iteration from another loop, regardless of how far into the array you start, or how quickly you break out, it becomes O(n^2). Maybe you can see the pattern now.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Can threads use resources from other processes?
This is how I see threads. Please do correct me if I'm wrong:

A thread is a part of a process that runs a sequence of program code. There can be many threads within a process that run different parts of a program (one thread manages keyboard input, one manages auto-saving, one manages printing etc.). The process allocates resources while the thread(s) are responsible for getting tasks executed by being scheduled for CPU time.

My question is:

> Are threads always bound to their own process or can they exchange resources with other threads outside of their process?

# Answer
> 1 votes
Threads are used to handle tasks simultaneously. For example, you keep your computation running in a thread, while another thread is waiting for keyboard input.

Threads inherit the privileges of the process they run in.
If the parent process is authorized to access another process's resources than the thread can do this.
The operating system assigns the process privileges when starting that process.

Whether your threads can obtain resources or not depends on the implementation of threads in your operating systems. In Linux, with some languages such as C, your threads are able to share memory with other processes, and even threads can create other threads. Basically, threads' access to memory is the same as your process. So, **threads can create a shared memory with another process and keep communicating with other processes via shared memory space**.

---
Tags: operating-systems, threads
---


title: Proof for TM accepting any PDA-language

text:
# Question
Title: Proof for TM accepting any PDA-language
How do you suggest I go about proving this:

Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine.

The best I can come up with is that since TMs are equivalent to computers, where as PDAs are not. A TM accepting any PDA-accepted language is understandable. (Church-Turing thesis)

BTW, I know PDAs accept CFLs, but is that all they accept?

# Answer
Simple, I don't know if you want the full answer but here is my proof:

We know that "A language is CF iff a PDA recognized it", and you know that this proof has two directions, I won't prove it here either. We can answer your question if we proof: "Any PDA has an equivalent TM".

**IDEA:**

Let state a TM M and a PDA P.

We know that any operation in P has the following format: a, b -\> c, where a is the item you have at the input, b is at the top of the stack and c the symbol I want to put at the top of the stack. We can simulate all the possible operations of P on M and the stack on the tape.

How? P will be simulated on two tapes: one for reading the input and the other for simulating the stack ( we still can simulate on a single-tape TM, since any k-tape TM can be turned on a single one tape TM.) by adding elements to the tape and erasing them as we need. The blank symbol will now be allowed as part of the input symbols $\Sigma$ (so that we can "use" the pop instruction of a PDA).

(I won't go through this but if you want me to, I can rewrite it later).

**PROOF:**

We know by definition that P has the formal description:

"P is a 6-tuple(Q, $\Sigma ,\Gamma,\delta, qo, F$) where:

Q is a set of states,

$\Sigma$ is a finite set called the input set,

$\Gamma$ is a finite set called the stack set,

$\delta$ is a finite subset of $Q \times (\Sigma \cup\\{\varepsilon\\}) \times \Gamma \times Q \times \Gamma^\* $, the transition relation.

q0 E Q is the start state,

F $\subseteq$ Q is the set of accepting states.

"

Great, now we'll make a transition algorithm that **any** TM can be turned into an AP, simply put:

Given an TM M, we'll create the formal transition to make an equivalent PDA:

1st step: We add the state "idle" on M, which is simply move to the left, do nothing, move to the right, do something.

2nd step: For every transition of P (a, b -\> c), we'll create an equivalent in M $\delta$.

3rd step: The accept state will only happen if we erase the initial symbol of $\Sigma$ and the reject state if the input ends.

I think you'll get the idea, sorry for my english mistakes, if you want to make improvements, you are free to do so.
> 1 votes

# Answer
Explain simply that you can simulate a push-down automaton using a TM. Thus, you have to "implement" a stack, which should not be that hard. State of the PDA can be stored in the internal state of the TM.
> 0 votes

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


# Question
Title: Converting a algorithm to a runtime function
I need to find an upper limit for the runtime of $f(n)$.

```
f(n):
{
 g(n,1)
}

g(n,k):
{
 if n<=0 return;
 for(i=1; i<=n; i++)
 {
  print "I love data structures!";
  k++;
  g(n-1, k);
 }
 return;
}

```

I tried to think of it this way:

`for(i=1; i<=n; i++)` $\rightarrow (n+1)c\_2$

`g(n-1, k)` $\rightarrow ng(n-1)$

$$f(n) = g(n,1) + c\_f = c\_1 + (n+1)c\_2 + nc\_3 + nc\_4 + ng(n-1) + c\_f$$

I am not sure about the recursion runtime analysis:

`g(n-1,k)` $\rightarrow ng(n-1)$

Thank you!

# Answer
> 0 votes
The recursion for $g$'s running time is $$T(n)=n(T(n-1)+1)$$ where $1$ is the (constant) work done from the print statement and incrementing $k$. $g(n-1,k)$ and the constant work are called $n$ times from the for loop. The recursion stops at $g(0,k)$ which has running time $T(0)=1$.

Solving this recursion on Mathematica (I suspect doing it by hand would involve induction or inspection) gave the result: $$T(n)=\Gamma(n+1)+en\Gamma(n,1)$$ The complexity of this is $$T(n)=O(\Gamma(n+1)+en\Gamma(n,1))$$ $$T(n)=O(n\Gamma(n,1))$$ Since $n$ is an integer, then we can reduce this to $$T(n)=O(n!)$$

---
Tags: runtime-analysis, recursion
---


title: Connected Component in Graph

text:
# Question
Title: Connected Component in Graph
I am a bit confused about the notion of connected component of a graph. I understand what is a subgraph and what means for a graph to be connected. But the definition we got in class is this: "A connected component of a graph is a maximal connected subgraph.". My question is, if the subgraph is connected but it is not maximal connected, it isn't considered anymore a connected component? For example if we have 4 nodes and 4 edges forming a square, and we pick 4 nodes and only 3 of the edges, this is still connected, but it is not maximal connected. So this isn't anymore a connected component?

# Answer
Usually when defining components one considers "induced subgraphs", that is, all edges between the selected nodes are present in the subgraph. This contary to what you suggest, taking all nodes, but only a subset of the edges.
> 0 votes

---
Tags: graphs
---


# Question
Title: Checking whether a number divides any of a set of other numbers
Consider a static set $S$ of positive numbers from range $\[1..10^9\]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | x$".

1. Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.
2. Storing all the divisors for every element of $S$ makes query time $O(1)$ but uses too much memory and precomputation time $O(|S| \times \sqrt{|\max(S)|})$.

I'm interested in an algorithm that uses less memory than second solution (because $|S| \sim 10^6$) and still somewhat faster queries than first solution (number of queries is also $\sim 10^6$).

# Answer
With the following techniques, I have been able to achieve a speedup of 100,000x over the brute force method of storing the dividend in an array and checking each dividend each time a divisor needs to be checked.

To do this, I use 10-20x as much working space as the brute force method when I am pre-processing the set of dividends. In the end, I use roughly 2-3x as much storage as the brute force method. I believe the working space requirement can be reduced substantially (see below) by the use of more complex algorithms.

To be specific about timing, with $\sim10^6$ dividends and divisors, the brute force method takes $0.02 \mu s$ for each dividend (that's the build) and $16{,}000{,}000 \mu s$ per divisor (that's the query) while my method takes $55 \mu s$ per dividend and the same time per divisor.

To create the structure, first make a trie of the dividends. Treat them as strings of prime factors, biggest factor first. Thus, 650 would be inserted into the trie as the string $\langle 13,5,5,2 \rangle$. Insert not only that string, but also all subsequences. In this case, that means to also insert:

* $\langle \rangle$
* $\langle 13 \rangle$
* $\langle 13,5 \rangle$
* $\langle 13,5,5 \rangle$
* $\langle 13,5,5,2 \rangle$ (the first sequence)
* $\langle 13,5,2 \rangle$
* $\langle 13,2 \rangle$
* $\langle 5 \rangle$
* $\langle 5,5 \rangle$
* $\langle 5,5,2 \rangle$
* $\langle 5,2 \rangle$
* $\langle 2 \rangle$

This represents all divisors of the dividend 650. Since all divisors are in the trie, queries can now proceed by just factoring the divisor in the same way (as a list of prime factors, largest first) and then traversing the trie. If the traversal hits a dead end before the divisor's prime sequence is exhausted, it divides no dividend in the trie.

Space-wise, for $\sim10^6$ random 31-bit dividends, this takes up 7-10x as much space as just storing the dividends themselves.

Sidebar: This is roughly the same amount of space as storing every divisor of every dividend in a hash table. I find this interesting on its own, as this is much less than the $n \sqrt{n}$ or $n \sqrt\[3\]{n}$ space upper bounds posted in the question and comments, I suspect because of overlap - 2 divides many numbers, but it only needs to be stored once. This method uses $60\mu s$ per dividend and $0.3\mu s$ per divisor on my computer, making about twice as fast as this trie/DAG method, while using the same amount of working space but larger storage space during queries.

To decrease the space usage of the tree, make a compressed acyclic graph of it, using the algorithm from "Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings", by Jan Daciuk. The big ideas, as I see them, are to:

1. Make an equivalence relation on DAG/Trie nodes in which two nodes are equivalent if they have the same set of children pointing to the same literal nodes. This makes deciding trie equality take time proportional to the number of children of a node, not the number of descendants. This is very important.
2. Use a postorder traversal to dedupe the nodes, so that the children of a node are already deduped before the parent, ensuring the equivalence relation doesn't miss anything.

This reduces the number of notes in the Trie/DAG by a factor of 6ish in my testing. Note that this does not do nearly as well if the prime factor strings are inserted smallest-prime first. I think that's due to the nature of the minimum automaton, in which nodes with the same label nearer to the root have many outgoing edges. Putting larger primes nearer the root reduces the amount of duplication near the root. I suspect this is related to the problem of picking a variable ordering in Binary Decision Diagrams.

In my testing, 80-90% of the work of the algorithm is actually the problem of factoring the numbers. I used trial division; if you use a better algorithm, I think your algorithm will be faster.

The working space required can be reduced using "Incremental construction of minimal acyclic finite state automata", by Daciuk et al.

In the below table, the space bounds are the amount of memory used divided by the number of items, and time bounds are the number of microseconds divided by the number of items.

$$ \begin{array}{|c|c|c|c|c|} \hline \textbf{Method} & \textbf{Construction time ($\mu s$)} & \textbf{Query time ($\mu s$)} & \textbf{Working space} & \textbf{Storage space}\\ \hline \text{Query every dividend} & 0.02 & 16{,}000{,}000 & 1 & 1\\ \hline \text{Store every divisor} & 60 & 0.3 & 7-10 & 7-10\\ \hline \text{This method} & 55 & 55 & 7-10 & 2-3\\ \hline \text{Incremental minimization} & ? & 55 & 2-3 & 2-3\\ \hline \end{array} $$
> 2 votes

# Answer
A silly answer:

Precompute the union of the sets of the factors of all elements in the set.

Then checking if the number is a divisor of any elements in the set is just a single set lookup ($O(1)$). This, however, requires an absurd amount of precomputation (and space to store the resulting set).

The precomputation time can probably be improved - sort the input set, then for each number from 1 to the square root of the largest number in the set, check if any of the numbers from the number squared to the largest number in the set are divisible by the number (add it to the cache if so). It's still absurd, however.
> 2 votes

# Answer
Sure, there are efficient algorithms. There's a straightforward algorithm, and it is already efficient. Let $S$ be your set, and $d$ be the number.

* For each $x \in S$:

+ Check whether $d$ is a divisor of $x$, using integer division or modular arithmetic (reduce $x$ modulo $d$ and check whether you get 0). If it is, output "Yes".
* If you made it through the entire loop and no $x$ was a multiple of $d$, output "No".

There are efficient algorithms for division; they take at most quadratic time (in the bit-length of the integers), but even faster ones are known. Multiply this by the number of elements of the set $S$, and you have the running time of this algorithm.

---

You can't expect to find a solution that uses less memory. Any solution will have to store the entire set $S$, or at least something that's information-theoretically equivalent to the set of prime divisors of $S$; in the worst case, the latter is of the same size as $S$.
> 1 votes

# Answer
```
Create an Array of size 10^9 (initialized to 0).

For each x in S: Set Array[x] = 1

currentNumber = 1

while True:
    if d*currentNumber > 10^9 then output NO and exit
    if Array[d*currentNumber] == 1 then output YES and exit
    else currentNumber=currentNumber+1;
output NO;

```
> 0 votes

---
Tags: algorithms, data-structures, number-theory
---


# Question
Title: Data normalization when control has multiple values in CS/CE
(This question was originally posted at https://academia.stackexchange.com/questions/68675 but was considered too specific for Academia.)

In computer science/engineering research papers relating to performance improvement wherein execution time is normalized to control benchmarks (i.e. speedup plots), how is that normalization generally implemented when the control(s) is/are executed multiple times in order to avoid the possibility of other processes/interrupts/etc. taking processor time and skewing the results? My first thought would be to just use the minimum time achieved for each benchmark, but as that would probably not be the minimum possible execution time in most cases and, depending on the situation, overall execution time rather than best-case execution time may be more important, is it better to just accept the skewing and go off the means? Or is it better to use the median for each set of results?

# Answer
> 0 votes
One simple approach is to use the median. It is less sensitive to outliers than the mean, but still serves as a good summary of typical running time. Alternatively, you could use the mean but in that case you should inspect all the results yourself to check for the possibility of outliers. I personally would recommend the median.

Papers often show confidence intervals as well, so that you can assess the effect of statistical noise.

Normally, benchmarks are run on an isolated system to minimize interference from other tasks.

Note that there are many challenges with benchmarking. Even simple irrelevant changes can cause significant changes to performance, e.g., because they happened to change cache alignment to something that is randomly better or worse. Therefore, it can be difficult to separate out whether your optimization led to a 3% performance improvement because your optimization is an improvement, or if that's just randomness (e.g., just recompiling with slightly different settings can change the running time by +/- 3%, and you happened to get unlucky once and lucky the other time).

---
Tags: empirical-research, benchmarking
---


title: Is $\log(n!)$ in $\Theta(n \log(n))$?

text:
# Question
Title: Is $\log(n!)$ in $\Theta(n \log(n))$?
I had two questions on my automated test which I don't understand the answer for.

$\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(n))$. But is it also in $\Omega(n \log(n))$? I don't think so, but my automated interview test thought so!

$\log(n)+\log(n^2) = \log(n)+2\log(n) = 3\log(n)$. So, it is in $O(\log(n))$, $\Omega(\log(n))$ and $\Theta(\log(n))$. But for some reason my automated interview test thought otherwise.

Is my understanding correct or is the automated test correct?

# Answer
> 7 votes
You mentioned $$ \log(n!) = \log(n(n-1)\cdots1) = \log(n)+\log(n-1)+ \cdots +\log(1) $$ From this, we can write (assuming $\log$ is base 2) $$ \begin{array}{l} \log(n!) \\ = \log(n)+\log(n-1)+....+\log(1) \\ \geq \log(n)+ \cdots + \log(n/2) \\ \geq \log(n/2)+ \cdots + \log(n/2) \\ = n/2 \cdot \log(n/2) \\ = n/2 \cdot (\log(n) - 1) \\ = n/2 \cdot \log(n) - n/2 \\ \end{array} $$ since $\lim\_{n\rightarrow +\infty} \dfrac{n/2}{n/2 \cdot \log(n)} = 0$, the last expression above is $\Theta(n \log(n))$, hence $\log(n!)$ is $\Omega(n \log(n))$.

# Answer
> 6 votes
Yes. This follows from Stirling's approximation: $\sqrt{2\pi}\\,n^{n+1/2}\\,e^{-n}\leq n!\leq e\\,n^{n+1/2}\\,e^{-n}$.

---
Tags: asymptotics, landau-notation
---


title: Running programs backwards

text:
# Question
Title: Running programs backwards
I never used a debugger that can run a program backwards but I would like to. Now I wonder if there is much evidence and theory about backwards runnable programming, when and why a program can be run backwards or when and why not?

Intuitively I find that the computer should be able to run the program backwards, if it once has run the program forward knowing that the program will run backwards hence saving states of the program that otherwise might get lost and deallocated.

Debugging is just a practical example. I'm also interested in it for the sake of the theory of reversibility, if the program can be run backwards, then what the program does is reversible, isn't it?

# Answer
In theory, to actually run program backwards would require you to undo any effects of program execution. Doing that should be relatively simple, if inefficient, for memory changes, harder for changes on disk and impossible for networking. And if the code depends on any external state (time of day, file on disk that could be modified by another process), rewinding and running it again won't produce the same result.

In practice, what is possible is to allow you to *look* at the state of the program at some point in its execution, but without allowing you to restart from that point. This way, there are no problems with external state, because this form of rewinding doesn't need to undo any state changes (except for memory) and stepping forwards will always produce the same result (because the code is not actually executed again). This form of rewinding is implemented in Visual Studio, under the name Historical Debugging, though it doesn't record program state at every instruction or line of code, only at every method call.
> 4 votes

# Answer
There's lots of research on this subject. I've sometimes seen it called "time-travel debugging" in the literature, sometimes "reverse debugging". A few minutes on Google Scholar should turn up a bunch of research publications on the subject.

See also https://softwareengineering.stackexchange.com/q/181527/34181 and https://stackoverflow.com/q/1470434/781723.
> 4 votes

---
Tags: automata, programming-languages
---


# Question
Title: What does the "Lambda" in "Lambda calculus" stand for?
I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from.

Can anyone explain the origins of the term?

# Answer
> 85 votes
An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006):

> By the way, why did Church choose the notation “$\lambda$”? In \[Church, 1964, §2\] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to distinguish function abstraction from class-abstraction, and then changing “$\wedge$” to “$\lambda$” for ease of printing. This origin was also reported in \[Rosser, 1984, p.338\]. On the other hand, in his later years Church told two enquirers that the choice was more accidental: a symbol was needed and “$\lambda$” just happened to be chosen.

# Answer
> 10 votes
here is some other near-firsthand info/ angle on this by Church student Dana Scott as just reported by Ghica and documented in a youtube video.\[1\]

> He says that when Church was asked what the meaning of the λ was, he just replied “Eeny, meeny, miny, moe.“, which can only mean one thing. It was a random, meaningless choice. Prof. Scott claimed that the typographical origin myth was mainly propagated by Henk Barendregt and is just pure whimsy. He asked us to stop perpetrating this silly story.

\[1\] Dana Scott on lambda notation / youtube

\[2\] why is lambda calculus named that / math.SE

---
Tags: terminology, computation-models, lambda-calculus, history
---


# Question
Title: Who was the first to define Flow Shop / Job Shop problem?
I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my master thesis.

I'm guessing that there may be no author of this problems but this information also would help me a lot.

# Answer
Coffman and Demming's famous *Operating Systems Theory*, 1973, section on Job Shop and Flow Shop problems (pp. 123-128) cites Conway, Maxwell, and Miller, 1967 as "a comprehensive treatment" of Job Shop scheduling. In the next paragraph, they introduce Flow Shop scheduling as a specialization of Job Shop, and cite

> Johnson, S.M.; "Optimal two- and three-stage production schedules with set-up times included." *Naval Research Logistics Quarterly*, 1(1):61-68, 1954.

*Naval Research Logistics Quarterly* seems to be a Wiley pay-walled journal, but my library has a subscription to it. Johnson's paper begins:

> Let us consider a typical multistage problem formulated in the following terms by R. Bellman:
>
> "There are n items which must go through one production stage or machine and then a second one. There is only one machine for each stage. At most one item can be on a machine at a given time.
>
> "Consider $2n$ constants $A\_i, B\_i, i = 1, 2, \cdots, n$. These are positive but otherwise arbitrary. Let $A\_i$ be the setup time plus work time of the $i$th item on the first machine, and $B\_i$ the corresponding time on the second machine. We seek the optimal schedule of items in order to minimize the total elapsed time."

He doesn't give the full reference to Bellman. Johnson's paper extends the definition in the obvious way to 3 machines.
> 2 votes

---
Tags: scheduling
---


title: Complexity of division

text:
# Question
Title: Complexity of division
The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".

But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?

If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$

# Answer
> 5 votes
The paper

> Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", *Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation* (PLDI):61-72, 1994.

gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount. The division is then done by multiplying the dividend by the reciprocal and shifting.

The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments. Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations. Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.

As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision. Newton's iteration doubles the number of useful digits each iteration. So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc. Since that's a geometric sum it sums to a constant and you get $O(M(n))$.

---
Tags: algorithms, complexity-theory, asymptotics, arithmetic
---


# Question
Title: Transition and configuration of Turing machine
In my lecture I have examples about 0 -\> R (which means if it's 0, move Right) or 0 -\> x, R (replace 0 with x and move Right) but I don't quite understand about the 0, 0 -\> R expression. What is the configuration of Turing machine btw

# Answer
Notations vary, but "$0, 1 \rightarrow R$" can be short for "$0 \rightarrow R$ and $1 \rightarrow R$."

A configuration is a way of writing the current state of the TM, the symbols on the tape and the current position of the tape. Here's a common way to write a configuration: if the state is $q\_0$, the tape has $101$, and the head is pointing at $0$, write $1q\_001$.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Subsets and Proper subsets of regular language
Let L ⊆ {0, 1}\* . Then

1) If all proper subsets of L are regular,is L regular?

2) If all finite subsets of L are regular,is L regular?

3) If a proper subset of L is not regular,is L non regular?

I am not sure if one or more of the above are true.I think 2) is true because any finite subset can be accepted by a DFA.Are 1) and 3) always true?If not,I am not able to provide counter examples.

# Answer
1) Consider $L-\\{w\\}$ where $w$ is an arbitrary element of $L$. What can you conclude?

2) Remember: every finite set is regular.

3) Start with an easy example $L=\\{a,b\\}^\*$ is regular, and contains various types of subsets.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Equivalent definition of minimal spanning tree
> Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$.

It's my attempt to prove $\Rightarrow$: Consider the cycle $path(v, u) \in T \cup E(v, u)$. If $(v, u)$ is not maximal, replace the maximal edge on the path by $(v, u)$. T is still connected, and we got spanning tree which weight is less than $w(T)$.

But I am stuck with the direction of "$\Leftarrow$".

# Answer
*Note:* The original answer has a flaw in "without loss of generality". The following one is based on Section 8.2.3 of the book "Computer Algorithms" (3rd edition) by Sara Baase and Allen Van Gelder.

---

The right part of the theorem is called the MST property.

> *MST Property:* Let $T$ be any spanning tree. For any edge $e \notin T$, $e$ has the maximal weight on the cycle created by adding it to $T$.

In terms of the MST property, the theorem to prove can be restated as:

> A spanning tree $T$ is an MST $\iff$ $T$ has the MST property.

---

We first prove the following lemma:

> *Lemma:* If $T$ and $T'$ are spanning trees that have the MST property, then $w(T) = w(T')$.

*Proof:* Let $\Delta E = (E(T) \setminus E(T')) \cup (E(T') \setminus E(T))$. That is, $\Delta E$ is the set of edges that are in one of $T$ or $T'$ but not in both. $\Delta E \neq \emptyset$. Let $|\Delta E| = k$.

If $k = 0$, we are done.

Let $k \> 0$ and $e$ be a minimum edge in $\Delta E$. Assume that $e \in T \setminus T'$ (the case of $e \in T' \setminus T$ is symmetrical).

$T' + e$ create a cycle $C\_{T'}$. There must be an edge $e'$ on the cycle $C\_{T}$ that $e' \neq e$ and $e' \in T' \setminus T$ (otherwise $T$ contains the cycle $C\_{T'}$).

* Since $T'$ has the MST property, $e$ has the maximum weight on the cycle $C\_{T'}$. Thus, $w(e') \le w(e)$.
* On the other hand, $e$ by definition is a minimum edge in $\Delta E$. Thus, $w(e) \le w(e')$.

Therefore, $w(e) = w(e')$.

Add $e$ to $T'$, creating a cycle, then remove $e'$, leaving a spanning tree $T''$. Since $w(T'') = w(T')$, $T''$ is an MST. However, $T$ and $T''$ differ by $k-1$ edges.

Repeating the procedure above, we will end with an MST, say $T^{k+1}$, such that $T$ and $T^{k+1}$ differ by $0$ edges.

Therefore, we have $w(T) = w(T^{k+1}) = \cdots = w(T'') = w(T')$.

---

Given the lemma above, we proceed to prove the "$\Leftarrow$" direction as follows:

Assume $T$ has the MST property. Let $T\_m$ be any MST. By the "$\Rightarrow$" direction, $T\_m$ has the MST property. By the lemma above, $w(T) = w(T\_m)$. Thus, $T$ is an MST.
> 1 votes

# Answer
Assume that there is a minimum spanning tree $T'$ with smaller weight than $T$. Since $T\neq T'$ there has to be an edge $uv$ in $T'$ but not in $T$. Now remove $uv$ from $T'$. This splits $T'$ into two trees $T'\_u$ and $T'\_v$. We denote the vertices spanned by $T'\_u$ by $U$ and the vertices spanned by $T'\_V$ by $V$. Let $\pi$ be the path that connects $u$ with $v$ in $T$. When traveling along $\pi$ we will leave at some point the set $U$ and enter the vertex set $V$. Assume that this "jump" happens at edge $ab$. Since $uv$ has a larger weight than $ab$ we get that $T'\setminus \\{uv\\} \cup \\{ab\\}$ has a smaller weight than $T'$ (and is of course a spanning tree). Hence $T'$ cannot be a MST and we have a contradiction to our assumption that there is a spanning tree with smaller weight than $T$.
> 0 votes

---
Tags: graphs, weighted-graphs, spanning-trees, minimum-spanning-tree
---


title: Big-O and not little-o implies theta?

text:
# Question
Title: Big-O and not little-o implies theta?
If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$?

Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$?

If not, can you provide an explanation/counter-example, please?

# Answer
Let's start with the simple case $g = 1$, and $f$ having positive values only (that's all we care about with functions that represent complexity).

* $f \in O(1)$ means that $f$ is bounded: there exists $B$ such that $f(n) \le B$ (for sufficiently large values of $n$).
* $f \in o(1)$ means that $\lim\_{n\to\infty} f(n) = 0$.
* $f \in \Theta(1)$ means that $f$ is bounded above and below: there exists $A \gt 0$ and $B$ such that $A \le f(n) \le B$ (for sufficiently large values of $n$).

Note that $f \in \Theta(1)$ requires a positive (nonzero) lower bound for $f$: for sufficiently large $n$, $f(n) \ge A$. If $f \in o(1)$ then for sufficiently large $n$, $f(n) \lt A$. It is possible for neither of these to hold if $f$ oscillates between “large” (bounded below) and “small” (converging to zero) values, for example $$f(n) = \begin{cases} 1 & \text{if \\(n\\) is even} \\ 1/n & \text{if \\(n\\) is odd} \\ \end{cases}$$ Informally speaking, half of $f$ is $\Theta(1)$ (the even values) and half is $o(1)$ (the odd values), so $f$ is neither $\Theta(1)$ nor $o(1)$, despite being $O(1)$.

With $g = 1$, there are regularity conditions on $f$ that's sufficient to make $O$ and not $o$ imply $\Theta$: this does hold if $f$ is monotonic; more generally, it holds if $f$ has a limit at $\infty$. With arbitrary positive $g$, these sufficient conditions translate to conditions on the quotient $f/g$ being monotonic (because $f \in O(g)$ iff $f/g \in O(1)$, etc.). It isn't enough for $f$ and $g$ to be both increasing or any such condition from real analysis. You can take any $g$ and multiply it by the $f$ above to get a counterexample to your conjecture.

With algebraic conditions on $f$ and $g$, if they are taken from sufficiently restricted sets of functions, the conjecture may hold. For example, it holds if they're both polynomials (for polynomials, $f \in O(g)$ if $\deg(f) \le \deg(g)$, $f \in o(g)$ if $\deg(f) \lt \deg(g)$ and $f \in \Theta(g)$ if $\deg(f) = \deg(g)$). But as soon as you add “perturbations” to $f$ and $g$, all bets are off.
> 11 votes

# Answer
No, it isn't true. Just consider $f(n) = n \bmod 2$ and $g(n) = 1$.

We have $\forall n ~ f(n) \leq 1 \cdot g(n)$, so $f(n) \in O(g(n))$.

$\lim\_{n \to \infty} f(n)/g(n)$ is undefined and therefore not $0$, so $f(n) \not\in o(g(n))$.

There is no positive number $a$ such that $f(n) \geq a \cdot g(n)$ for all $n$ starting with some $n\_0$, so $f(n) \not\in \Omega(g(n))$ and therefore $f(n) \not\in \Theta(g(n))$.
> 9 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: What happens under the hood when the process requests operating system to open a file?
Suppose a process wish to open a file named test.txt. So it issues a system call requesting Operating system to find the file on disk,and to grab the handle of file to operate on it. My question is how does the operating system actually locates file on disk(Particularly sequence of actions the operating system performs to do this)? How partitions,file systems,directory structures used to accomplish this? (If possible kindly explain with an example)

# Answer
> 1 votes
I'll outline a fictional simplified filesystem for you. There are a few more details, but they are not needed to understand what's going on.

The operating system uses a module called a filesystem.
The filesystem is software that knows how the disk is organized.
It talks to the disk-driver which is software that tells the disk to read of write a particular sector on the disk.

The top down structure goes like this:

```
string s = ReadTextFileIntoString('c:\documents\test.txt');

//Translates to the following calls.
  Disk = GotoDisk('c:');
  //The root directory is always at sector 512.
  Dir = Disk.ReadDirectoryFromDisk(512);
  Sector = Dir.SearchForFileName('documents');
  if (Sector = -1) then StopWithError;
  Dir2 = Disk.ReadDirectoryFromDisk(Sector);
  Sector = Dir2.SearchForFileName('test.txt');
  if Sector = -1 then StopWithError;
  File = Disk.GetFile(Sector);
  s = File.ReadToString;  /see above.

```

A disk is made up of sectors, The first sector is 0 and the last is sector how ever many sectors there are on the disk. Say 1.999.999.999 for a 1 terabyte disk. Every sector is 512 bytes large. There are no missing numbers or gaps.
The very first sector, sector 0 holds the master boot record. Which is a small program in 512 bytes that starts up the operating system.
This tiny program knows how to read a sector from the disk and little else.

The disk driver is software that knows how to read and write a sector. That's it.
It has two methods.

```
ReadSector(sectornumber: integer, Buffer: 512bytes);
WriteSector(sectornumber: integer, Buffer: 512bytes);

```

Above the disk driver sits the filesystem,

It knows about:

* Directories
* File Allocation Table - FAT

A directory is a text file with the following structure:

```
filename1.1024.characters filesize starting-sector DirectoryYN
filename2....

```

As you can see we know where a file starts. The directory tells us.
But a sector is only 512 bytes. How do we know where the rest of the file is?
Files on disks are **not** continuous so if the first sector is 5 the rest of the file need not be on sectors 6,7,8 etc. In fact they can be anywhere at all.
To solve this problem there is the FAT The File allocation table.
This is structure to tell which sectors belong to a file.

It looks like this:

```
0 2 3 3 8 10 -1 -1 -1 -1

```

Every entry corresponds to a sector. The 1 first entry is sector 0 (we start counting at 0 in computing).
The second entry is sector 1 etc.
Inside the entry is a reference to the next sector.
If a file has no next sector the entry references itself.
The first entry (in our fictional example) is the boot sector, which is a file 512 bytes long. It has no next sector, so the next sector is itself: 0. The second entry is the FAT itself. It is a little larger, so it starts at sector 1-\>2-\>3-\>3 the entry for sector 3 points to itself, so there the file ends.
This is how the filesystem knows how to locate a file.
It knows where the file starts and it uses a little table to see where the different sectors after the first are located.

For those sectors that are empty it works the same way, but negative numbers are used. All the writer has to do is locate negative numbers in the file allocation table and write data into those sectors, then update the relevant entries in the FAT and the file is stored.
Note that there are two pieces of information stored a single entry in the table.
The first the the number of the entry, this corresponds with the sector, second it the data inside that entry, this corresponds with where the next sector in the chain is, or whether that sector is free.

An entry in the directory can be another directory (which is really a text file) or a normal file.
The filesystem will load one directory at a time, until it finds the entry for the file, then it will do whatever is requested (read, write, delete).

---
Tags: operating-systems, filesystems
---


# Question
Title: Regular expression for language of strings having odd length but even number of $b$'s
I have to draw a finite automaton of a language over $\\{a,b\\}$ of all strings having odd length and has an even number of $b$s.

I already came up with following regular expression $(a+b)((a+b)(a+b))^\*$ which satisfies the condition that a string must have odd length.

What should it look like so that a string has even number of $b$s as well?

# Answer
**Hint**: Use four states, depending on what the input so far has been: (odd length, even b's), (odd length, odd b's), (even length, even b's), (even length, odd b's).

Then answer these questions:

1. Which of the states should be the start state?
2. Which of the states should be final states?
3. What should the transitions be between the states? For example, from (odd length, even b's), on seeing an $a$ you should then be in (even length, even b's).
> 1 votes

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


# Question
Title: What is the difference between AM and IP
**Intro**

I am trying to understand how those two models of interactive proof are different. I understand that

* $\text{AM}$ relies on public coins (the prover knows the random bits used by the verifier)
* $\text{IP}$ relies on private coins (the prover does not)

And here are some common results in those classes

* Goldwasser and Sipser showed that if we allow a polynomial number of rounds $Q$, we have that $\text{IP}\[Q\] \subseteq \text{AM}\[Q+2\]$.
* It has also been shown that if we allow a constant number of rounds $k$ in $\text{AM}$, we have that $\text{AM}\[k\] \subseteq \text{AM}\[2\]$

This seems to imply that if we limit $\text{IP}$ to a constant number of round $k$, we also have that $\text{IP}\[k\] \subseteq \text{AM}\[k+2\] \subseteq \text{AM}\[2\]$, and that these classes are very similar.

---

**The thing that bugs me**

But then, why do we have the huge difference that $\text{IP} = \text{PSPACE}$, while $\text{AM} \subseteq \prod\_2^{\text{P}}$?

(see the Complexity Zoo on AM and IP)

---

**Question(s)**

1. Why the difference? My assumption is that there is a convention to use $\text{AM}$ to speak about $\text{AM}\[k\]$, private coin, constant $k$ rounds protocols, and $\text{IP}$ to speak about $\text{IP}\[\text{poly}\]$ public coin, polynomial rounds protocols. Is it correct?
2. Do the results holds if we swap the classes? $\text{IP}\[k\] \subseteq \prod\_2^{\text{P}}$ does, but what about $\text{AM}\[\text{poly}\] = \text{PSPACE}$?
3. As an additional question, we do know that a constant number of messages $k$ can be condensed into only two messages. Is there a similar result for a polynomial number of messages?

# Answer
$AM$ is defined to be $AM\[2\]$, i.e. languages with 2-rounds Arthur-Merlin protocol, which is equal to $AM\[k\]$ for any constant $k$.

Two extra rounds are required to overcome the fact that the coins are public, i.e.

$IP\[k\]\subseteq AM\[k+2\]$ for any $k$ , constant or not, as stated in complexity zoo.

This means that $IP\[poly\]=AM\[poly\]=PSPACE$ (which answers your second question).

If $IP$ can be limited to a constant number of rounds (rather than polynomial), then we would have $PSPACE\subseteq IP\[k\]\subseteq \Pi^p\_2$, and the hierarchy collapses to the second level, since $PH\subseteq PSPACE$.
> 3 votes

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Proof of 0/1 knapsack optimal substructure
I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property.

Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions defined over $E$.

Now, suppose that, among all solutions weighing at most $W$, $S \subseteq E$ is the best solution. How can I prove that $S - \\{x\\}$ is the best solution weighing at most $W - w(x)$, considering the set of possible items as $E - \\{x\\}$? I tried to suppose that $S' \subseteq E - \\{x\\}$ is a better solution (that is, $v(S') \> v(S - \\{x\\})$ and $w(S') \leq W - w(x)$), but I get stuck when I try to find a contradiction.

Any help?

Thanks in advance!

# Answer
> 2 votes
Suppose that some $S'\subseteq E-\\{x\\}$ is a better admissible solution than $S-\\{x\\}$. Then $S'\not= S$, the value is more, $v(S') \> v(S-\\{x\\})$, and $x\not \in S'$, and $w(S')\leq W-w(x)$, as you indicated. Now add $x$ to $S'$ to obtain $S''=S'\cup \\{x\\}$. What will be the value and weight of this new subset? And how does it compare to the value and weight of $S$? Let's write it out:

$w(S'') = w(S')+w(x) \leq (W-w(x))+w(x) = W$ so $S''$ weighs less than $W$, so $S''$ is an admissible solution, so it makes sense to compare their values.

$v(S'') = v(S') + v(x)$. By assumption, $v(S')\>v(S-\\{x\\})$, so, adding $v(x)$ to both sides of this last equation, $v(S')+v(x)\>v(S-\\{x\\})+v(x) = v(S)$. Hence $v(S'')\>v(S)$. But this is a contradiction, because $S''$ is supposedly a better admissible solution while you had presumed that $S$ was the best admissible solution. $\square$

By admissible I mean that the knapsack weighs less than the maximum weight.

---
Tags: correctness-proof, knapsack-problems
---


# Question
Title: How to use Parikh's Theorem to show language is not context free
Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, language isn't important, but for definiteness:

$$ L=\\{0^m1^n:m\>n\text{ or }(m\text{ is prime and }m\leq n)\\}$$

# Answer
> 4 votes
If $L$ were context free, then the set $$ H = \\{(m,n) : m \> n\\} \cup \\{(m,n) : m \leq n \text{ and } m \text{ is prime}\\} $$ would be semilinear. The set $\\{(m,n) : m \leq n\\} = \mathbb{N} (1,1) + \mathbb{N} (0,1)$ is also semilinear. The intersection of semilinear sets is also semilinear, so the set $$ H' = \\{(m,n) : m \leq n \text{ and } m \text{ is prime}\\} $$ is also semilinear. The projection of a semilinear set is semilinear, and so the set of primes is semilinear. But one-dimensional semilinear sets with asymptotic density zero are finite, whereas the set of primes is an infinite set with asymptotic density zero.

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


# Question
Title: How do IR researchers evaluate the ranks of documents?
I am developing a new IR system in a specialized context. I understand that a traditional IR system (like a search engine) should rank documents in terms of their relevance for a query. The most relevant documents should come first and the least relevant (perhaps: least relevant above some threshold) should come last.

I want to evaluate my new IR system. How do researchers evaluate document rank? How do they say that this document is more relevant than that document for some query? The most obvious thing to do would be to manually assign such labels and then check the machine against the hand labels. This seems highly subjective. Maybe there is a better way?

I've read section 15.1 Manning's *Foundations of Natural Language Processing* but it only talks about evaluating precision and recall -- not evaluating rank. Any suggestions on where to look on evaluating rank?

# Answer
> 1 votes
If I understand what you're trying to achieve correctly, you can use this technique **discounted cumulative gain**.

$$DCG\_p=\sum\_{i=1}^{p}{\frac{2^{rel\_i}-1}{\log\_2{(i+1)}}}$$

$i$ is the rank, and $p$ is the number of results that you want to evaluate. For example, if you evaluate DCG for the first 10 results, then $p=10$.

NDCG is a form of DCG that involves normalizing the result. This is useful if p differs when you compare DCG scores. $$NDCG=\frac{DCG}{IDCG}$$ where IDCG is the ideal DCG. This is found by calculating the DCG up to $p$ under ideal conditions (all documents have a relevance of 1).

Note that neither recall nor precision are used here. Relevance and rank are the factors to compare. You still need to give the documents a relevance factor, that's unavoidable, but you don't need to establish a threshold as you would with other evaluation metrics.

---
Tags: natural-language-processing, information-retrieval
---


# Question
Title: How do we generate a depth-first forest from the Depth First Search?
I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the Depth-First Search Forest as mentioned in CLRS:

```
STRONGLY-CONNECTED-COMPONENTS (G)

 1. Call DFS(G) to compute finishing times f[u] for all u.
 2. Compute G^T
 3. Call DFS(G^T), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
 4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.

```

However, I did not understand how to generate the DFS Forests from the Depth First Search. Please explain me how is it possible, and preferably use Cormen's DFS Psuedocode as I am a beginner and am quite familiar with CLRS.

Below is Cormen's DFS psuedocode:

```
DFS (V, E)

1.     for each vertex u in V[G]
2.        do color[u] ← WHITE
3.                π[u] ← NIL
4.     time ← 0
5.     for each vertex u in V[G]
6.        do if color[u] ← WHITE
7.                then DFS-Visit(u)              ▷ build a new DFS-tree from u

DFS-Visit(u)

1.     color[u] ← GRAY                         ▷ discover u
2.     time ← time + 1
3.     d[u] ← time
4.     for each vertex v adjacent to u     ▷ explore (u, v)
5.        do if color[v] ← WHITE
6.                then π[v] ← u
7.                        DFS-Visit(v)
8.     color[u] ← BLACK
9.     time ← time + 1
10.   f[u] ← time                                 ▷ we are done with u

```

PS: Rest assured, this is **not** homework.

# Answer
Algorithm `DFS-Visit(u)` finds a tree that consists of vertices that are in the same connected component as vertex `u`. Basically, when you run `DFS-Visit(u)`, you visit every vertex in the same connected component as `u` and you change their color to `black`.

In algorithm `DFS(V, E)`, in steps 5-7, you find a vertex `u` with color `white` (which means that it is not in any of the previous trees/visited connected components) and run `DFS-Visit(u)` in order to find the next tree.
> 1 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Deadlock avoidance: How does the system know in advance about the number of resources required by a process?
While studying about `Deadlock Avoidance` I came across a paragraph which states as given below:

> When the system needs to issue any resource to any process, then in making this decision the system must consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process.

So my question is that how can the system know in advance about the number of resources that a particular process will require/request in future?

# Answer
> 1 votes
For many systems, it's impossible to know (for instance, your home computer). In a very controlled system, you could know in advance about the number of resources that a process requires and when these requests occur (for example, an embedded system).

You could probably create some sort of heuristic for what resources might be requested in the future based on previous knowledge (such as past program execution or code analysis) for the impossible cases. I'm not sure how much this is done in practice though.

---
Tags: operating-systems, deadlocks
---


# Question
Title: Reccurrence for the game of pile of stones
I am trying to solve this question from Project Euler for past few days: Divisor game. The problem is as follows:

> Two players are playing a game. There are $k$ piles of stones. When it is his turn a player has to choose a pile and replace it by two piles of stones under the following two conditions:
> **1**.Both new piles must have a number of stones more than $1$ and less than the number of stones of the original pile.
> **2**.The number of stones of each of the new piles must be a *divisor* of the number of stones of the original pile.
> The first player unable to make a valid move loses.
> Let $f(n,k)$ be the number of winning positions/configurations for the first player, assuming **perfect/optimal** play, when the game is played with $k$ piles each having between $2$ and $n$ stones (inclusively). Then find $f(10^7,10^{12}).$

**What I tried**

* The first thought upon seeing the number of piles to be $10^{12}$, is that somehow matrix exponentiation is involved, with a linear recurrence being obtained on the number of piles $k$ for some fixed $n$.
* The second thing which can be observed is that if I have $k-1$ piles of stones with each pile having stones between $2$ and $n$. And this configuration is denoted by $S\_{k-1}$, then if I have two numbers $a=q\_1^{r\_1}q\_2^{r\_2}...p\_x^{r\_x}$ and $b=s\_1^{t\_1}s\_2^{t\_2}...s\_y^{t\_y}$ ( where I have written the prime factorization of $a$ and $b$ ) such that $r\_1+r\_2..+r\_x=t\_1+t\_2..+t\_y$ then either both the configurations $S\_{k-1}a$ and $S\_{k-1}b$ are loosing configurations or both are winning configurations ( where $S\_{k-1}a$ means I have added a pile with $a$ stones to the configuration $S\_{k-1}$ ).
* Based on the the above two points I tried the following approach. Let $L\_{k-1}$ and $W\_{k-1}$ be the number of loosing and winning configurations respectively, where each configuration has $k$ piles, with each pile having between $2$ and $n$ stones ( inclusive ). Also let $P$ and $C$ represent a prime and a composite number respectively, between $2$ and $n$ ( inclusive ). Then it is easy to note the following:
* $L\_{k-1}P$ is a losing configuration with $k$ piles, last pile having $P$ stones.
* $W\_{k-1}P$ is a winning configuration with $k$ piles, last pile having $P$ stones.
* $L\_{k-1}C$ is a winning configuration . The reason is: as $C$ is a composite number it has a prime divisor $p$. The first player chooses the last pile ( $k$th pile ) having $C$ stones and replaces it with two piles each having $p$ stones. Now its the second players chance and he is left with configuration $L\_{k-1}$ which is loosing configuration ( the second player can't choose the two newly form piles as they cannot be broken down further as they have prime number of stones ).
* The problem comes here as $W\_{k-1}C$ can be a winning or a loosing configuration. For example let $k=2$ and $n=10$ then it can be seen that a single pile having $4$ stones is a winning configuration. And also it is easy to see that $\\{4,4\\}$ is a loosing configuration whereas $\\{4,8\\}$ is a winning configuration ( where $\\{4,8\\}$ means two piles, first having $4$ stones and second having $8$ stones). So I am unable to move forward in this case.

I still suspect it is a matrix exponentiation question. But I guess it cannot be done just keeping variables $W\_{k-1}$ and $L\_{k-1}$. How do I proceed ?

PS: As this problem is from project Euler I would appreciate only hints.

# Answer
AS I asked for hints only, apart from the hints I have provided one can solve the question with grundy numbers.
> 2 votes

---
Tags: time-complexity, recurrence-relation, dynamic-programming, number-theory, game-theory
---


title: Are all languages in P?

text:
# Question
Title: Are all languages in P?
Are all languages in $\mathbf{P}$?

Note: The definitions of all the symbols and functions here follow the document \[1\].

The following is my attempt to answer the question. Assume that we design a special Turing machine $M\_1$, no matter what the input is, $M\_1$ will jump to the state $q\_{\rm accept}$ (the accepting state). Because no matter what the input $w$ is, $M\_1$ only needs one step to finish the calculation, $T\_{M\_1}(n) = 1\ \forall n \in \mathbb{N}$. Let $k=1$, then $T\_{M\_1}(n) \leq n^1 + 1 = n + 1$. Therefore, $M\_1$ runs in polynomial time. Then, all languages $L$ are in $\mathbf{P}$.

## Reference

\[1\] S. Cook, *The P versus NP problem*, \[Online\] http://www.claymath.org/sites/default/files/pvsnp.pdf.

# Answer
You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding means that it return a positive answer iff $w \in L$ **and** a negative otherwise.

Your approach will return a positive answer in every case. Thus your TM will accept the language $\Sigma^\*$ where $\Sigma$ is the input alphabet of your TM.
> 20 votes

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


# Question
Title: Proof for This Greedy Strategy for Equalizing An Array
Recently the following problem was posed in a private coding competition at my workplace:

> An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\\{2,2,3,7\\}$ and $D=\\{1,2,5\\}$ we can equalize $A$ in two steps, first adding $A=\\{5,5,5,0\\}$ to get $A=\\{7,7,8,7\\}$ and then adding $\\{1,1,0,1\\}$ to get $A=\\{8,8,8,8\\}$.

In discussion forums it was suggested to repeatedly find the difference of the smallest and largest elements and then greedily increment all but the largest element by this amount. An implementation using this strategy passed all test cases. However I'm unable to see how this strategy will indeed result in the smallest number of steps.

# Answer
> 3 votes
Actually I am not sure the greedy solution will always give the best solution?

Recall that the change making problem does not work for certain denominations in a greedy way. For example with denominations $1,3,4$ and a goal of $6$ the greedy solution will give $4,1,1$ whereas the optimal solution is $3,3$.

This can be translated into your problem. Start with array $A=\[0,6\]$ and steps $D=\\{1,3,4\\}$. Now your greedy solution seems to behave like change making. I am not certain about this, however, as your description does not precisely say by which amount the numbers are incremented. Perhaps your algorithm chooses $\[0,6\] \to \[4,6\] \to \[7,6\] \to \[7,7\]$ (which is also wrong, anyway).

---
Tags: greedy-algorithms
---


# Question
Title: Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)
I am currently learning landau notations and am stuck on the following True/False question.

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough. But i am not sure if my reasoning is correct and if i get the big picture here.

# Answer
> 2 votes
Θ(n log n) means the algorithm is O(n log n) and Ω(n log n), and is slower than Θ(n) so your reasoning is correct.

But there's another layer: Landau notation denotes asymptotic bounds on functions. Saying "worst case" restricts it to those functions which result in the highest run time. For example take binary search: we get a best-case runtime asymptotic of Θ(1) and a worst-case asymptotic of Θ(log n).

To answer your question about the difference between "worst-case Θ(n log n)" and "run-time O(n log n)"\*, the first one gives us more information: it tells us it runs about as fast as n log n, where the second tells us it runs at most n log n.

<sub>\*Technically the second one doesn't tell us for what 'run-time' configuration it is asymptotically approaching, but in that case generally most people mean 'in the worst case this algorithm runs in O(n log n)' when they don't say anything.</sub>

---
Tags: terminology, asymptotics, runtime-analysis, landau-notation
---


title: Runtime analysis with recursion factor

text:
# Question
Title: Runtime analysis with recursion factor
I have this code:

```
if n is even
{
for i=1....n
   for j=1...i
      print j
return 8*foo(n/2)
}

```

Asking to calculate the running time $T (n)$. I thought at first that I can write the function like this:

$$T(n)= 8T(n / 2)+n^2$$ But according to the answers of the quiz, they are saying that the function looks like this:

$$T (n)= T(n / 2)+n^2$$ Why we can delete 8? Thank you very much!

# Answer
You're asked to calculate the *running time* of the segment, not the *value* returned. In terms of running time, multiplication by 8 is a single operation, so the running time is (roughly) $T(n)=T(n/2)+n^2$.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: If my computer is a 32 bit system,it has a 32 bit address right?But when i print any memory address in C why do i get a short value?
For example

```
printf("%u",&a);

```

*gives me output* **65524**

# Answer
> If my computer is a 32 bit system, it has a 32 bit address right?

You should not take it for granted.

Many older processors had external (or internal) buses narrower than 32 bits (thus limiting memory size or demanding more cycles for instruction fetch) but were labeled 32-bit based on the fact that they had 32-bit registers and instructions able to manipulate 32-bit quantities.

Some examples are Motorola 68000 and IBM System/370.

Also a 32 bit system, for backward compatibility, may use a non linear address space (e.g. Intel 80386 fully support the 16-bit segmented address space of its predecessors).

Conversely processors with 32-bit registers and instructions that manipulate 32-bit quantities may have bigger external address bus (e.g. Pentium Pro with 36 bits and a larger address space than 4 GB).

Anyway the correct explanation (educated guess) is in the comments (further details in https://stackoverflow.com/q/5208641/3235496).
> 0 votes

---
Tags: computer-architecture, c
---


# Question
Title: Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?
I was reading a paper and I came to the following :

"Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see \[19\]) for any fixed $\epsilon\> 0$, the ..." where \[19\] is the following article : D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC, pages 681–690, 2006.

My question: is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? Because I cannot find this result in the cited article. However, I can find the results about max clique and chromatic number. What I am missing?

# Answer
Yes, this is true.

To see this, notice that cliques and independent sets are complementary. That is, a set of vertices $S$ is independent precisely when $S$ forms a clique in the complement of the graph. Intuitively, this means that if you had an approximation algorithm for finding a maximum clique, you could use it to find a maximum independent set by executing it on the complement graph.
> 5 votes

---
Tags: reductions
---


# Question
Title: How to recursively infer a word/string from a context-free grammar?
> Give the recursive inference of the word $abcddd$ from the Context-free Grammar:
>
> $A\rightarrow aAd\mid B$
> $B\rightarrow bBd\mid C$
> $C\rightarrow cC\mid cD$
> $D\rightarrow Dd\mid ϵ$

This is a follow up question to this one here. Much like that question I haven't found any good information on the subject. I understand the inductive proof of an inferred word belonging to a language, but I don't know how to put it to practical use. I have found an example in our course literature, "*Introduction to Automata Theory, Languages, and Computation*" by Hopcroft, Motwani and Ullman, but they only have a filled out table of the inference of several words without any detailed explanation on how they got there.

I tried to mimic that table for this excersice and think I have solved it, but I don't understand what I'm doing or if I'm even doing it right. What I need is someone to explain the thinking behind this algorithm or whatever it is they are using. Here is the table I have created for the word $abcddd$:

$$ \begin{array}{ r | c | c | c | c } & \textit{String Inferred} & \textit{For language of} & \textit{Production used} & \textit{String(s) used} \\ \hline (i) & ϵ & D & D \rightarrow ϵ & - \\ (ii) & d & D & D \rightarrow Dd & (i) \\ (iii) & cd & C & C \rightarrow cD & (ii) \\ (iv) & cd & B & B \rightarrow C & (iii) \\ (v) & bcdd & B & B \rightarrow bBd & (iv) \\ (vi) & bcdd & A & A \rightarrow B & (v) \\ (vii) & abcddd & A & A \rightarrow aAd & (vi) \\ \hline \end{array} $$

To me this is just like deriving words, but backwards, if you know what I mean? So, I am doing this correctly? Why am I doing this, instead of just deriving words "as usual"?

# Answer
> 1 votes
You are correct to realize that this is just like deriving words, but backwards. The authors admit this when they say "However, it is often more natural to think of grammars as used in derivations, . . ."

Labeling the productions as $A\rightarrow aAd$ (1), $A\rightarrow B$ (2), $B\rightarrow bBd$ (3), $B\rightarrow C$ (4)m $C\rightarrow cC$ (5), $C\rightarrow cD$ (6), $D\rightarrow Dd$ (6), and $D\rightarrow\epsilon$ (8) we can produce this derivation $$ A\stackrel{(1)}{\Longrightarrow}aAd\stackrel{(2)}{\Longrightarrow}aBd\stackrel{(3)}{\Longrightarrow}abBdd\stackrel{(4)}{\Longrightarrow}abCdd\stackrel{(6)}{\Longrightarrow}abcDdd\stackrel{(7)}{\Longrightarrow}abcDddd\stackrel{(8)}{\Longrightarrow}abcddd $$ and reading this from right to left gives exactly the table you had.

Frankly, it's not a topic I cover when I'm teaching this material.

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


# Question
Title: Find pth percentile of a stream of numbers
I want to find the pth percentile of a stream of integers, exactly (not approximately).

If we know the number of integers which will be coming in the stream and the numbers can fit into the memory then we can simply sort the integers and find the pth percentile.

But, what if all the numbers can't be fit in memory? How can we do that?

We can assume all integers are 64-bit integers.

# Answer
> 3 votes
I'm afraid that it is not possible to solve this problem with above conditions. Sooner or later, while reading next element from stream, you will run out of memory and will have to throw away one of buffered elements. But without having any constraints on further elements in stream, it is always possible to construct such sequence of further elements in stream, so that thrown out element is the searched one.

A practical commercial-grade solution exists, though it produces approximate result:

1. Allocate memory for as many numbers as you can afford
2. Use reservoir sampling atop of allocated memory to sample numbers from stream
3. When end of stream is reached, search for percentile among samples

To get exact solution, you need to either know number of elements in advance, or to have enough memory, or to have knowledge of stream properties (e.g. stream is monotonic). Keywords are "running median" and "n-th order statistics".

---
Tags: streaming-algorithm
---


title: Understanding DPA

text:
# Question
Title: Understanding DPA
DPA denotes “Deterministic Pushdown Automata”.

Is the following (\*) true regarding DPA:

> After all symbols of the input sequence are *consumed*, the input sequence is accepted either (1) if the stack is empty or (2) if the current state of the DPA is an accepting one, or both.

My book is fairly vague on the subject (it doesn't mention it) and Wikipedia, in my opinion, doesn't offer a better explanation either:

> There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are the languages that are accepted by final state, as well as have no word in the language that is the prefix of another word in the language.

(What I don't understand is the *equivalence* they mention, and how does that influence the acceptance of a word.)

If my statement (\*) doesn't hold, how would I determine, given the definition of a DPA, which condition are input sequences supposed to fulfill? Would I assume one or the other as the *preferred* one?

# Answer
You can define the language of a PDA in two different ways:

1. For a PDA $M$, $L\_1(M)$ is the set of all words which can be processed by $M$ in such a way that at the end, the stack is empty.
2. For a PDA $M$, $L\_2(M)$ is the set of all words which can be processed by $M$ in such a way that at the end, $M$ is at an accepting state.

A basic theorem shows that both acceptance criteria are equivalent:

> For each language $L$ the following holds: there exists a PDA $M\_1$ such that $L\_1(M\_1) = L$ iff there exists a PDA $M\_2$ such that $L\_2(M\_2) = L$.

A language $L$ is *context-free* if there exists a PDA $M$ such that $L\_1(M) = L$. Equivalently, a language $L$ is context-free if there exists a PDA $M$ such that $L\_2(M) = L$. The two definitions are equivalent due to the theorem.

Some PDAs are deterministic – call those DPAs. The basic theorem doesn't hold for DPAs. According to Wikipedia, there exists a DPA $M\_1$ such that $L\_1(M\_1) = L$ iff $L$ is prefix-free (no word is a prefix of another word) and there exists a DPA $M\_2$ such that $L\_2(M\_2) = L$.

A language $L$ is *deterministic context-free* if there exists a DPA $M$ such that $L\_2(M) = L$.

If $L\_1(M) = L$ for some DPA $M$ then $L$ is deterministic context-free, but $L$ could be deterministic context-free without there existing a DPA $M$ such that $L\_1(M) = L$.
> 4 votes

---
Tags: automata
---


# Question
Title: Evolutionary algorithm in stochastic environment
Consider the following model problem:

I want to use an **evolutionary algorithm** to optimize the starting point of particles for which it is apriori clear where they would start in state space, but not **when**. Once a particle is placed, it is part of the dynamics, which is **stochastic**, i.e. whether certain particles interact is modeled by a random variable. A *mutation* of the evolutionary algorithm corresponds to slightly changing the time when the particle is introduced in the system.

I have now two choices:

1) I let the stochastic dynamics evolve *while* the evolutionary algorithm is optimizing, i.e. after every mutation I *draw* a new interaction environment from the distribution. That means, the algorithm is evaluating every situation with a different environment (drawn from one fixed distribution).

2) I draw an interaction pattern for every particle *apriori* to have one fixed environment (we assume they can be drawn independently). Then I let the algorithm optimize my problem in that deterministic environment. I do that for *several* environments and take some statistic over the solution.

Does someone have experience with those two approaches and can tell me their advantages and disadvantages from a practical point of view?

# Answer
> 2 votes
I'd go with option 1.

A dynamic training environment is a good way to produce a robust solution (after all natural evolution, which is the inspiration for EA, is always dynamic).

Moreover *"take some statistics over the solutions"* can be a very hard problem (you shouldn't take for granted that there is a meaningful way to combine / extract information from multiple solutions).

Indeed there are some important aspects to consider:

* **population diversity have to be carefully monitored**. Often EAs are designed for a static optimization problem and the quick loss of diversity can be a problem in a dynamic environment;
* it seems that you have a system in which environmental change occurs rapidly. **Try to slow down the environment**: do not draw a new interaction environment after every mutation but wait for a sequence of mutations (in Genetic Programming this is the approach taken in Dynamic Training Subset Selection{1}). I'm not sure this will work, but it's worth a try;
* **supply the EA with an explicit memory** (sometimes called *Valhalla*) so that the EA can recall useful information from past generations (e.g {5}).

---

This is small compendium of interesting papers.

Looking for further resources, consider that there are many kinds of dynamic environments: e.g. noisy fitness functions, environments with optimum changing over time... they are somewhat different problems but share many interesting techniques.

Also it seems to me that you're describing a so called *co-adaptive environment* (each individual's evolution drives other individuals evolution and individuals change their fitness landscape evermore). You may find interesting techniques in papers about *co-evolution*.

1. Dynamic Training Subset Selection for Supervised Learning in Genetic Programming by Chris Gathercole, Peter Ross (1994).
2. Genetic Algorithm for Adaptation to Dynamic Environments - A survey by Naoki Mori, Hajime Kita (2000).
3. Evolutionary Dynamic Optimization - A survey of the state of the art by Juergen Branke, Trung Thanh Nguyen, Shengxiang Yang (2012).
4. An evolutionary approach for time dependant optimization by Philippe Collard, Cathy Escazut, Alessio Gaspar (1997).
5. "Memory enhanced evolutionary algorithms for changing optimization problems" by Juergen Branke (1999).
6. Evolutionary Algorithms and Dynamic Optimization Problems by Karsten Weicker (2003).

---
Tags: optimization, heuristics, evolutionary-computing
---


title: Relation between MAX CUT and MIN CUT

text:
# Question
Title: Relation between MAX CUT and MIN CUT
I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)?

Barahona, in 1982, showed (Lemma 1) finding a cut of at least k on a unit-weight graph is equivalent to finding a cut of at most -k on a graph in which each edge is replaced with a chain of edges, each of weight +1 except for one with weight -1. http://yaroslavvb.com/papers/barahona-on.pdf

Is this not technically MIN CUT on that extended graph? Wouldn't this show that MAX CUT can be reduced to MIN CUT, and therefore belong in P or is there something about MIN CUT I don't understand properly?

# Answer
Both problems you mention have the stated complexity only when edge weights are non-negative. With these constraints, the reduction you describe no longer works.
> 1 votes

---
Tags: complexity-theory, graphs, max-cut
---


# Question
Title: 2D random walk. Should both dimensions be independent?
My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive.

What is the correct approach in selecting consecutive positions of the particle? Do I choose both coordinates independently or the step length?

# Answer
The usual 2D random walk goes one step in one of the cardinal directions (up, down, left, or right). If you rotate the plane by 45 degrees, you get a random walk which moves up or down **and** left or right on each step. So both these distributions are the same (up to scaling), at least for a fixed step size.
> 1 votes

---
Tags: randomized-algorithms, randomness, random-walks
---


# Question
Title: Understanding hashtable performance in the worst-case
Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. `java.util.HashMap`) hashtable $O(\log n)$. Why? I cannot really understand this. If we have a uniformly-distributed hash values it should be the case that each hash bucket contains approximately the same number of elements.

Therefore, if we have load-factor (`buckets_number/elements_number`) say $0.5$, we guarantee the constant-time performance for search operations $O(2)$.

# Answer
The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations.

In the worst case however, all your elements hash to the same location and are part of one long chain of size `n`. Then, it depends on the data structure used to implement the chaining. If you choose a sorted array, you can do binary search and the worst case complexity for search is `O(log n)`. If you choose an unsorted list, you have a worst case of `O(n)` for search. Depending on your choice of data structure, the performance (worst and average case) of insert, delete and search changes.

According to Coding-Geek.com, Java 7's HashMap implementation uses a linked list (unsorted), but Java 8 uses a balanced binary tree instead. Of course, insert/delete/search in a balanced tree of size `n` has complexity `O(log n)`.
> 6 votes

---
Tags: time-complexity, hash-tables, hashing
---


# Question
Title: Pseudocode algorithm to check encoding of Turing machine
My question goes like this:

> Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is correct, that $\delta(q\_a,a)$ is undefined for every symbol $a$, etc.

Unfortunately, I got no idea how to tackle it. I have a clue that induction might be needed, but it didn't help me. Any help will be appreciated. Thank you!

# Answer
The encoding $\langle M \rangle$ of a TM, has a specific *structure*. All you need your algorithm to do, is to verify that the input string $w$ possesses the "correct" structure of a valid encoding.

Note, that there are many possible ways to define the encoding $\langle M \rangle$. For instance *one* possible such encoding, for $M=(Q,q\_0,F,\Gamma,\Sigma, \sqcup, \delta)$ is $$ 1^{|Q|}01^{|\Gamma|}01^{|\Sigma|}0\delta\_100\delta\_200 \ldots \delta\_{last}000$$ where each $\delta\_i$ is one line of the transition function, such that if, for instance $\delta(q,a) = \\{ p, b, d\\}$ we encode it as $1^q01^a01^p01^b01^d$ with $d$ being the direction where the head moves, say Left=1, Right=2, Stay=3.

Remember that other encodings are possible, it depends on your definition!

However, assuming the above definition, I think you should be able to come up with an algorithm to verify if the encoding is valid or not.

For instance, is the input $w=0000000$ valid ?

> no, because it contains no states $Q$, etc.

What will you need to check for validity? Basically, only the following

> 0. that the formatting looks correct (no extra characters, ends with 000, etc,)
> 1. that all the sets exist (and behave correctly, e.g., $|\Gamma|\>|\Sigma|$)
> 2. that $\delta$ is well defined (think, what does this mean)...
> 1 votes

---
Tags: algorithms, turing-machines
---


# Question
Title: Linear-time algorithm to find an odd-length cycle in a directed graph
> ***Problem:*** Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. *(Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.)*

---

The related post@cs.stackexchange asks for the *existence* of an odd-length directed cycle in a digraph, which is solved by the following theorem@algs4.cs.princeton.edu.

> *Theorem:* A directed graph has an odd-length directed cycle if and only if one (or more) of its strong components is non-bipartite (when treated as an undirected graph).

Thus, we can assume that the digraph is strongly connected.

# Answer
Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to. Note that since every vertex is reachable from $s$, BFS will explore all the edges, so all of the edges would be going between the two blocks of the partition. Otherwise, you find an edge $(u,v)$ that goes between levels of the same parity. Suppose level of $u$ is even and level of $v$ is even. Then run DFS (or BFS) from $v$ to get a path to $s$. If this path is of even length then you get an odd directed cycle $s \rightsquigarrow u \rightarrow v \rightsquigarrow s$. If this path is of odd length then you get an odd directed cycle $s \rightsquigarrow v \rightsquigarrow s$. Analogous thing holds when level of $u$ is odd and level of $v$ is odd. Since this algorithm simply does 2 runs of BFS/DFS, it runs in linear time.
> 12 votes

# Answer
There actually is the answer to your question on a page you have linked: algs4.cs.princeton.edu: Directed Graphs. It's under Creative Problems (41.) and the trick is that you can construct a directed odd-length cycle from an undirected odd-length cycle in a strongly connected component.

> 41. Odd-length directed cycle. Design a linear-time algorithm to determine whether a digraph has an odd-length directed cycle.
>
> Solution. We claim that a digraph G has an odd-length directed cycle if and only if one (or more) of its strong components is nonbipartite (when treated as an undirected graph).
>
> If the digraph G has an odd-length directed cycle, then this cycle will be entirely contained in one of the strong components. When the strong component is treated as an undirected graph, the odd-length directed cycle becomes an odd-length cycle. Recall that an undirected graph is bipartite if and only if it has no odd-length cycle.
>
> Suppose a strong component of G is nonbipartite (when treated as an undirected graph). This means that there is an odd-length cycle C in the strong component, ignoring direction. If C is a directed cycle, then we are done. Otherwise, if an edge v-\>w is pointing in the "wrong" direction, we can replace it with an odd-length path that is pointing in the opposite direction (which preserves the parity of the number of edges in the cycle). To see how, note that there exists a directed path P from w to v because v and w are in the same strong component. If P has odd length, then we replace edge v-\>w by P; if P has even length, then this path P combined with v-\>w is an odd-length cycle.
> 0 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Basic questions about network flow calculations
Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to each edge $e$ of the graph a capacity $c\_e$ is assigned (which can be defined as a function vertex properties of the endpoints of an edge), and in analogy to flow of water through pipes for example, a net flow is assumed to take place from the source towards the sink. That is the net flow out of the source, is equal to the net flow entering the sink: $$ \sum\_{u\in O(s)} f(s,u)-\sum\_{u\in I(s)}f(u,s)=\sum\_{u\in I(t)} f(u,t)-\sum\_{u\in O(t)}f(t,u) $$ where $O(s)$ denotes the set of vertices, that $s$ is incident on, and $I(s)$ denotes the set of vertices that are incident to $s.$ Now often, one is interested in computing the maximum possible flow in the graph, which leads to using Menger's theorem, which relates maximum number of distinct paths (between $s$ and $t$) to the minimal cut-set, or in a general setting, it relates the maximum flow to minimum cut capacity (summing the capacities of the minimum cut, that disconnects source from sink).

There are many algorithms that allow computing the maximum flow rather efficiently, for a given digraph. But my questions are (sadly) rather basic, but are solely related to **computing maximum flow**:

* Assuming the capacities of all the edges are known, why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities? or am I wrong?
* How are then the individual flows $f$, through each edge $e$ (where $f\_e\le c\_e $), calculated when we are estimating the *maximum flow*? Do we set all flows equal to respective capacities (i.e. $f\_e=c\_e$)? Or is the individual flow, a function of the minimum capacity ($\text{min}(c\_e)$ for all edges $e$) of the graph?
* Of course it is possible that I'm completely wrong here, in which case, the question becomes: how is the flow decided for each edge (knowing at least that $0\le f\_e \le c\_e$ for all edges), when we are interested in estimating the maximum flow through the graph?

# Answer
> 3 votes
I think all your questions are answered by examining the actual algorithm to compute the max flow.

With regards to your Q1: in the max flow problem your input is a graph and capacities on edges, your output is the max flow. Thus, max flow is a function of the graph and capacities.

The basic algorithm for computing max flow is as follows. Your capacities are $c: E \rightarrow \mathbb{R}$. We shall incrementally compute the flow $f: E \rightarrow \mathbb{R}$. Let $f^i$ be the flow in iteration $i$. To begin with set $f^0 = 0$. In iteration $i$ construct the residual capacities $c^i(e) = c(e) - f^i(e)$ - this is how much capacity is left on edge $e$ given that we are already sending $f^i(e)$ flow through it. Find an augmenting path from $s$ to $t$, i.e., any path $p$ from $s$ to $t$ such that all edges on that path have positive residual capacity. How much flow can you push on this path? Clearly it's the minimum capacity along an edge of that path $f\_{add} = \min\_{e \in p} c^i(e)$. Update your flow by pushing $f\_{add}$ flow along path $p$. This process naturally stops when your residual graph does not have an augmenting path from $s$ to $t$. It's a fact that at that point the flow you constructed is, indeed, the maximum flow. This fact requires a proof. This is a meta-algorithm (called Ford-Fulkerson), because I have not specified how to choose augmenting paths. Certain choices are better than others. Using BFS (in which case, this max flow algorithm has a name of Edmonds-Karp) to choose the augmenting path results in a polynomial time algorithm, but it again requires proof.

# Answer
> 3 votes
> why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities?

This is a bit like asking, "Why does the top speed of my car not depend on the speed I'm doing at the moment, and instead it is only a function of the power of its engine?"

The amount of water leaving the source is a property of a specific flow: different flows will have different amounts of water leaving the source. The maximum possible flow depends on the capacities of the edges in the graph, but it doesn't depend on whatever other flow you happen to be thinking about at the moment.

> How are then the individual flows $f$, through each edge $e$ (where $f\_e\leq c\_e$), calculated when we are estimating the maximum flow?

By using one of the algorithms that does that. I suggest you look at a description of one of these algorithms.

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


# Question
Title: Undecidability of REGULAR_TM (Detail within Proof)
I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book.

The example shows how $REGULAR\_{TM}$, defined as the problem of determining if a Turing machine recognizes a regular language, is undecidable. The way they do it is by showing a reduction from $A\_{TM}$, which is the acceptance problem for Turing Machines (the acceptance problem for some computational model is the task of determining whether or not it accepts a given input string).

From what I understand, all that needs to be done is show that if $REGULAR\_{TM}$ was decidable by some TM $R$, then another TM could use $R$ to decide $A\_{TM}$, which would be a contradiction, since $A\_{TM}$ is undecidable.

They construct a TM $S$ that can be used to decide $A\_{TM}$. Where I'm lost is through their use of an intermediate TM, $M\_2$. Here is the full description:

* $S$ = "On input $\langle M, w\rangle$, where $M$ is a TM and $w$ is a string:
    1. Construct the following TM $M\_2$.
        + $M\_2$ = "On input $x$:
            1. If $x$ has the form $0^{n}1^{n}$, *accept*.
            2. If $x$ does not have this form, run $M$ on input $w$ and *accept* if $M$ accepts $w$."
    2. Run $R$ on input $\langle M\_2 \rangle$.
    3. If $R$ accepts, *accept*; if $R$ rejects, *reject*."

My two main questions are:

1. Why are we allowed to do step 2 in the construction of $M\_2$? If we could just say "run $M$ on $w$ and *accept* if $M$ accepts", then wouldn't that be a way to show that $A\_{TM}$ is decidable?
2. What exactly is the role of step 1 in the construction of $M\_2$? The book says that the purpose of this TM is not to be run, but just to feed its description into $R$. The TM recognizes $\\{0^n1^n\mid n \ge 0\\}$ if $M$ does not accept $w$, and $\Sigma^\*$ if it does, but I don't see how it does that from the description. Also, I don't see how $A\_{TM}$ can be decided by using this (I'm thinking it's that the TM $M\_2$ only outputs a regular language if the TM $M$ accepts $w$, but I don't understand how it can do that).

Any help is greatly appreciated, thanks!

# Answer
> 6 votes
This proof assumes, for the purpose of contradiction, that there exists a Turing machine $R$ deciding $R\_{TM}=\left\\{\langle M\rangle | \hspace{1mm} L(M) \text{ is regular}\right\\}$, and uses the existence of $R$ to construct a Turing machine deciding $A\_{TM}=\left\\{\langle M,w\rangle | \hspace{1mm} M \text{ accepts $w$}\right\\}$.

$R$ halts on every input (since it decides $R\_{TM}$), so there is no problem running it (it will finally halt and either accept or reject the input). This avoids the problem of running $M$, some arbitrary Turing machine, on some input $w$, since we do not know that $M$ will finally halt.

Now, Sipser constructs a new Turing machine, $M\_2$, such that:

$L(M\_2) \text{ is regular} \iff M \text{ accepts $w$}$

If the above holds, then you would have $\langle M\_2\rangle\in L(R) \iff M \text{ accepts $w$}$, so you could find out if $M$ accepts $w$ simply by running $R$ (which always halts) on $M\_2$.

To see why this property holds, note that $M\_2$ always accepts strings of the form $0^n1^n$, and it accepts any string not of this form iff $M$ accepts $w$. This means that $L(M\_2)=\left\\{0^n1^n | n\ge 0\right\\}$ if $M$ does not accept $w$, and $\Sigma^\*$ (which is regular) otherwise.

---
Tags: computability, turing-machines, reductions, undecidability
---


title: Difference between SNN RL and DNN RL?

text:
# Question
Title: Difference between SNN RL and DNN RL?
In Reinfrocement Learning (RL) in Neural Networks (NNs), I've seen two approaches to Q-learning.

The first is to tile the state space with basis functions using Spiking Neural Networks (SNN) to represent reward. This approach is used in "A neural reinforcement learning model for tasks with unknown time delays" by Daniel Rasmussen and is expanded upon in "A neural model of hierarchical reinforcement learning" by the same author.

The second is to use Deep Neural Networks (DNN) to map the state space to the reward space, such as the various publications used by Deep Mind.

From what I've read so far, I believe the differences between these two approaches are as follows:

* SNNs take less long to train
* SNNs can be deployed on existing neuromorphic hardware
* SNNs are more easily extended into continuous cases
* SNNs do more inference between states
* DNNs can map larger and higher dimensional state spaces
* DNNs require less knowledge of the task for the programmer

Is this analysis accurate? Are there other differences that I've missed?

# Answer
Daniel Rasmussen replied via email:

> * SNNs take less long to train
>
> This really depends on the training method, and the implementation. If you just implemented an abstract DNN approach to solve the same task as is being solved in those NEF RL papers, it would be a pretty simple network and would train quite fast (almost certainly faster than with the simple PES rule). On the other hand, if you recreated the internal structure of the SNN model, and trained it using a DNN approach (e.g., using something like nengo\_deeplearning), I suspect that that would never converge to something useful. So overall it's hard to say something useful to compare them in this sense, but I think if you had to commit to something, the DNN training methods are probably more efficient than SNNs.
>
> * SNNs can be deployed on existing neuromorphic hardware
>
> Yep
>
> * SNNs are more easily extended into continuous cases
>
> I'm not sure if this is true. It is true that there aren't a lot of examples of people doing continuous state processing with DNNs, but that's also true of SNNs. I'm not sure it's any easier or harder for DNNs than SNNs (it's just harder than the discrete case in both paradigms).
>
> * SNNs do more inference between states
>
> Again, don't think this is true in general, it'll all depend on how things are implemented.
>
> * DNNs can map larger and higher dimensional state spaces
>
> Also depends on the implementation, but it is true that DNNs tend to be more computationally efficient than SNNs (because they're not incorporating all those biological features).
>
> * DNNs require less knowledge of the task for the programmer
>
> Not categorically true, but probably true in most cases.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, reinforcement-learning
---


# Question
Title: Minimum Weight Directed Subgraph ensuring all pairs reachability?
After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an algorithm for it. I couldn't find anything in Google or Google Scholar.

Given a directed graph $G=(V,E)$ with a weight for each edge given by $w(e)$, find a subset $S \subseteq E$ of minimum cost (sum of weights) such that for every pair $u,v \in V$ of nodes, there is a path from $u$ to $v$ that traverses only edges in $S$.

For instance:

```
A--2->B
^     |
|2    |2
|     v
C--1->D
 <-3--

```

In the example, there is an edge from C to D of cost 1 and the opposite direction of cost 3. The solution here would be the edges CA, AB, BD and DC. This solution has cost 9.

Any variation of Prim or Kruskal fails on this problem, and I can't see any other algorithm that I could modify to work here. Also, I can't come up with any algorithm (I'm starting to suspect its NP-complete, but I am still looking for a reduction).

Can anyone tell me if this is indeed proven NP-complete or if there is a polynomial-time algorithm for this?

# Answer
> 2 votes
This problem is a generalized version of the famous Minimum Spanning Strong Subdigraph or MSSS \[1\]. This problem is NP-hard and there are several heuristic algorithms for it. You may look at the reference given in this solution and the related papers to find out more about this problem.

Note that this problem itself is a simplified version of Minimum Equivalent Graph of a Digraph \[2\]. Therefore, there are some algorithms that you can use as a heuristic for this problem.

**\[1\]** Bang-Jensen, Jorgen, Jing Huang, and Anders Yeo. "*Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs.*" SIAM Journal on Discrete Mathematics 16.2 (2003): 335-343.

**\[2\]** Martello, Silvano, and Paolo Toth. "*Finding a minimum equivalent graph of a digraph.*" Networks 12.2 (1982): 89-100.

---
Tags: algorithms, graphs
---


# Question
Title: What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)?
I am looking for the time complexity of the following nested loops, where the inner loop is shrinking.

```
function(int n){
  c=0;
  for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
      c++;
}

```

# Answer
It's not hard to see how many times `c` gets incremented. Each $+$ in the table below represents one `c++` operation.

$$\begin{array}{r|ccccccc} &i=1&2&3&4&5&6&\cdots&n \\ \hline \\ j=1& +&+&+&+&+&+&\cdots&+& \\ 2& &+&+&+&+&+&\cdots&+& \\ 3& & &+&+&+&+&\cdots&+& \\ 4& & & &+&+&+&\cdots&+& \\ 5& & & & &+&+&\cdots&+& \\ 6& & & & & &+&\cdots&+& \\ \vdots& & & & & & &\ddots&+& \\ n& & & & & & & &+& \\ \end{array}$$

The total number of $+$ operations is

$$\begin{align} 1 + 2 + 3 + \cdots + n =&\ \frac{n (n + 1)}{2} \\ =&\ \frac{n^2}{2} + \frac{n}{2} \end{align}$$

… which is roughly $\dfrac{n^2}{2}$, which is usually just characterized as $O(n^2)$. You can also see that roughly half of the $n \times n$ square is filled in.
> 3 votes

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