# Question
Title: How does hardware interrupt work on a physical layer
I'm a newbie in computer science and would to understand how hardware interrupts work at the physical layer. I ask my question considering a specific example. When packet arrives at the network adapter, a hardware interrupt is raised. Wikipedia says that

> an interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention.

I know that the OS will invoke a corresponding interrupt handler when the interrupt's type is detected. But I don't understand how the CPU detects and distinguishes incoming interrupts.

First, why CPU does know that the interrupt is coming from the network adapter and not from some other device?

Second, where are interrupt handlers registered in the CPU? Are there specific areas of the CPU that contain addresses for handlers registered by the OS?

# Answer
> 4 votes
The CPU has specific pins on the outside to detect hardware interrupts.

Take for instance the 6502 used in the Apple II and c64 it has two interrupt pins:
IRQ on pin 4 and (can be ignored)
NMI on pin 6 (cannot be ignored)

If the signal on pin 6 falls from high voltage to low voltage the CPU will perform a call to the non-maskable-interrupt handler.
It will read the contents of address $FFFE and jump to the 16-bit location contained in that address.
After it's done it will return to where execution was before and resume operation as if nothing happened.

In the interrupt handler the CPU will query its peripherals to find out which one generated the interrupt.
Usually a specific chip is connected to the interrupt pin and that chip can be queried using an INput/OUTput instruction to get the relevant info quickly. On the c64 the CIA 6526 was used.

> Are there specific areas of the CPU that contain addresses for handlers registered by the OS?

You set up the CPU so that it calls a predetermined address when it receives an interrupt.
In early CPU's this address has hardcoded in the chip. In newer chips the system kernel can change the interrupt address using a privileged instruction.

On modern processors this works the same but things are complicated because everything is virtualised.

---
Tags: memory-hardware
---


title: Petri net, how to stop it after 5 times

text:
# Question
Title: Petri net, how to stop it after 5 times
I have a task to reimplement this net (library system) into a 'finite' net, which ends after 5 'readings'. I have totally no clue how to achieve this, it was our first lesson.

Is there someone that could help me?

# Answer
In order to prevent a loop from running forever you need to either

* keep track of how many times you've performed the loop using a loop counter
* change the conditions of your state machine inside the loop so that you ensure it will stop at some point.
> 1 votes

---
Tags: petri-nets
---


# Question
Title: Finding top k which are the most different from each other
Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$. Also, each two items $a\_1,a\_2 \in A$ have variety score $var(a\_1,a\_2)$ which tells how different they are.

I want to optimize over these two values (say with equal weights) to find $k$ items that have both high scores and large variety (to avoid almost-repetitive items). That is, to solve the following optimization problem:

$$\arg\max\_{a\_1,...,a\_k\in A}{(\sum\_{i=1}^{k} s(a\_i) + \sum\_{1 \le i\<j\le k} var(a\_i, a\_j)})$$

1. Is this problem NP-hard?
2. If not, can you provide a polynomial time algorithm that solves it?
3. If yes, can you provide a polynomial time approximation algorithm that approximately solves it?

# Answer
Your problem is NP-hard, when $k$ is part of the input. Let $G=(V,E)$ be an undirected graph. If we set all the scores to zero and $\text{var}(u,v)$ to 1 if $(u,v) \in E$ and 0 otherwise, your problem is equivalent to asking whether $G$ contains a clique of size $k$. This is a NP-hard problem.

If we set all the scores to zero and allow the variety values to be arbitrary, your problem is equivalent to the maximum edge-weighted clique problem (MEWCP), which has been studied in the literature. For instance, you can use quadratic programming or ILP to look for solutions; these can take exponential time in the worst case, but might be useful in practice if the number of items is not too large.

Obviously, when we take into account that scores can be non-zero, the problem only gets harder. You might be able to adapt methods for MEWCP to your problem, or express your problem directly as an ILP or QP.
> 1 votes

---
Tags: algorithms, optimization, np-complete, approximation, sets
---


# Question
Title: Understanding pipeline stalls (bubbles) based on stage
I'm currently reading through *x86 Assembly Language and C Fundamentals* and came across this statement in the second chapter of the book:

> If the instruction required is not available in the cache, then a cache miss occurs, necessitating a fetch from main memory. This is referred to as a pipeline stall and delays processing the next instruction. Information is passed from one stage to the next by means of a storage buffer.

Having read the Wikipedia article associated to this, and the book covering one paragraph of this subject that I can find, I have a few glaring questions regarding this.

* Would a pipeline stall occur if there were no further instructions to fetch from main memory, and if so, would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?
* Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?
* If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle for both/all of the stages that's trying to use the resource, or is there specificity involved based on stage that would allow for one of the stages to complete its instruction given that the cycle was the cycle in which the pipeline stall occurred?

**Note:** I'm not formally educated in Computer Science so I apologize if these are CS101 questions.

# Answer
A CPU pipeline has a number of stages.

The exact stages vary between CPUs and some CPUs have very many stages, but obviously the first stage must be Instruction Fetch (IF) and the second stage must be Instruction decode (ID).
If an instruction is not in the cache it cannot be fetched and delays occur.
Let's call our missing instruction $A$.

The only way for the next instruction $B$ to **not** be delayed is if $B$ is in the cache and the CPU supports out of order instruction and $B$ does not depend on the outcome of instruction $A$ and the CPU allows fetching from memory and the cache at the same time and the CPU knows where $B$ is located.

Phew that's a lot of if's.
Let's unpack the various issues.

**Cache**
Because barring jumps instructions are fetched sequentially it's moderately unlikely that $A$ is not cached, whilst $B$ is. But it does happen.

**Out of order support**
Most CPU's support OoO execution, so there are no problems there.

**Independent instruction**
Some instructions have no dependencies. e.g. `xor rax,rax` will zero out rax no matter what.
However we don't know what instruction $A$ does. If it's an unconditional jump it may just jump over $B$.
Still the CPU might elect to execute B speculatively, if the gamble pays off valuable time is gained.

**Fetching from memory and cache at the same time**
Current x86/x64 CPU's do not support this.
The reason why will become clear in the next paragraph.

**Where is $B$ located?**
The x86 architecture has a variable length instruction.
A x86/x64 instruction can be anywhere between 1 and 15 instructions long.
Only when the pipeline gets to the Instruction Decode (ID) stage does the CPU know how long the instruction is.
***So there is no way for the CPU to know where $B$ starts until $A$ has been decoded.***
*In normal execution the CPU solves this by either (a) pre-decode instructions and store the instruction lengths in the cache (as meta data), or (b) fetch large chunks of data in one go and parallel decode this or both.<br>Intel uses strategy b, AMD uses a+b.*

However it is impossible to know where $B$ starts without knowing the instruction length of $A$. There are 15 possible lengths and the CPU will not start 15 possible speculative executions, that's would just be a waste of silicon :-).

If the x86 architecture had fixed instruction length then speculative execution would have been an option. The fetch and decode stages pose no problem and perhaps even more stages could be performed.
However CISC and variable instruction length throws a big spanner in the works.

> Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?

The details are very complex, but, yes, a stall can and does occur at every stage.
Common stall reasons are:

* mispredicted jumps. This causes a stall because the pipeline needs to be emptied and reread from some as yet unknown address.
* instruction $B$ depends on the outcome of instruction $A$. This is called a dependency chain. These chains can be arbitrary long.
* both instructions $A$ and $B$ require some piece of expensive hardware. The CPU has only one of these available and thus $B$ must wait for $A$ to finish.

> If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle

That depends if the resource allows pipelining.
In modern CPU's the answer is yes. Expensive hardware is capable of pipelined operation.
E.g. two multiplication instructions will execute in 4 cycles given that a `MUL reg,reg` has a 3 cycle latency and a third unrelated instruction can execute in parallel.

> would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?

Yes, e.g. if the memory has been swapped out to disk and the disk takes indefinitely long the CPU will just wait.
*Well the hardware will generate a page fault exception, but that's beside the point*
> 5 votes

---
Tags: cpu-cache, cpu-pipelines
---


# Question
Title: Longest path of a DAG containing a single node?
I'm interested in implementing an algorithm detailed on this Wiki page for finding the longest path of a DAG.

The second part of the algorithm says the length of the longest path of a node with no outgoing edges should be zero, but my programming professor says this node should return 1 as its longest path length. (Perhaps he says this assuming each node's length is set to 0 and a recursive function that visits each node will add 1 to whichever child has the longest path.)

I think that if someone can answer the question: what is the length of the longest path of a DAG containing a single node, then I will have an answer to my question. Though, I'm not sure if a single-node graph constitutes a DAG.

As you can probably tell, I'm new to graphs, so any guidance is appreciated.

# Answer
You have not misunderstood anything, there is simply a discrepancy of notation: sometimes the length of a path is measured as its number of edges, sometimes as its number of nodes, depending on context. In your implementation, it doesn't matter which convention you use, as long as you are consistent throughout your algorithm. Then if you use the second convention and your algorithm returns $3$ for a particular vertex, it means the longest path to that vertex has three nodes: $abv$. If you use the first convention (which is what this Wikipedia article uses, but not your professor), the algorithm should return $2$, because the longest path has two edges.

If this is an assignment, and your professor uses the convention that paths are measured by their vertices, and says that you should too, then you should too.
> 1 votes

---
Tags: graphs
---


title: Computation of busy beaver function

text:
# Question
Title: Computation of busy beaver function
The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n\>4$? What is so different about $n=4$ than $n=5$? Or $n=6$? Somewhere along the way there must be some fundamental difference, otherwise $S(n)$ would be, in principle, computable for all $n$, so what exactly *is* this difference?

# Answer
The reason that no program can compute $S(n)$ is that if you knew what $S(n)$ is you could decide the halting problem - you'd know when to stop waiting. On the other hand, for each $m$ there is a program that computes $S(n)$ for all $n \leq m$ - it just uses a table.

If it were possible to prove the value of $S(n)$ for all $n$ (that is, for all $n$ we could prove $S(n) = \alpha$ for some $\alpha$) then we could compute $S(n)$ by searching through all proofs (this assumes that our proof system is valid). So for each proof system there is a minimal value of $n$ for which you cannot prove that $S(n) = \alpha$ for any $\alpha$.

Finally, the reason that we know $S(4)$ is probably because $4$ is a really small number. The number $5$ is slightly bigger, and so things get more complicated. There's no deep reason why we know $S(4)$ but not $S(5)$, just like there is no deep reason why we know the Ramsey number $R(4)$ but not $R(5)$ (though Ramsey numbers are of course computable).
> 6 votes

# Answer
Scott Aaronson discusses this here. He and his co-author find an explicit upper bound on $n$ for which $S(n)$ can be computed.
> 4 votes

# Answer
another angle, with an informal sketch of an answer, which would take a long time to technically flesh out with further research (ie it is basically a research program): there is some preliminary evidence that the limit of what is computable about the Busy Beaver function is a measure of algorithm complexity, with two refs below that hint at this direction.\[1\]\[2\] roughly, small TMs with very few states cannot accomplish "as much" or "as sophisticated behavior" as more complex algorithms with more states. therefore calculation of it appears also to have a deep link with Kolmogorov complexity.\[3\] another way of looking at this is that what is known/computable about the Busy Beaver function also closely coincides with state-of-the-art in automated theorem proving, which (similar to technological advance) is a continually advancing frontier based on mathematical & computer science research.

\[1\] Busy beaver problem, a new millenium attack, van Heuveln et al

\[2\] Small Turing machines and generalized busy beaver competition, Michel

\[3\] On running time of the shortest problems, Batfai
> 2 votes

---
Tags: computability, busy-beaver
---


# Question
Title: Showing a language is a subset of another language?
I'm actually trying to give an example of a language being context-free and its superset that isn't context-free. I came up with this, but I'm not sure if this particular language is a superset of the other.

Let A be a context-free language. A = {a^n b^n | n \>= 0}.

Let B be a non context-free language. B = {a^n b^n c^n | n \>= 0}.

What I'm not sure of is if A is a subset of B. I saw something regarding proving if a regular language is a subset of another regular language, but I don't know if it applies to this situation.

Can someone provide some clarity on this, please?

# Answer
A language $B$ is a superset of another language $A$ if it contains all the strings of $A$ and some more. In your example, $A$ contains $ab$, but $B$ only contains string with $c$'s in them, so $ab\not\in B$, so $B$ is not a superset of $A$, i.e. $A \not\subseteq B$.

What you are looking for is a language $B$ which is not context-free but which does contain all of $A$. For example, you could let $C$ be some very difficult language, for example, the language of TMs that halt on the empty tape, or the language of prime numbers, and let $B=A\cup C$. Then whatever the complexity it $B$, you can be sure that it's not context-free. This trick won't always work. For example, if $A=\Sigma^{\*}$, then no superset of $A$ *exists*, and certainly not one that isn't context-free.

What you read about one language a subset of another language is probably succinctly captured in the Wikipediag page on context-free languages (link) and that of regular languages (link) under the section of *closure properties*. A closure property is a theorem states that, for example, if $L\_1$ and $L\_2$ are both context-free, then $L\_1 \cup L\_2$ is also a context-free language. In this case you can say *context-free languages are closed under union*.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: In Data Mining, what does it mean to be greedy?
I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory.

For example, with Hierarchical Clustering *the decision to merge clusters* is described as greedy. However, a filter attribute selection method where we select a subset of the attributes which possess the highest Information Gain is also described as greedy because *it does not cope well with the interaction of attributes*.

What does the term *greedy* mean in terms of Data Mining?

# Answer
> 3 votes
I'm not a Data Mining expert, but from what I understand, it means the same thing as it does outside of data mining: to improving the solution in a locally optimal way, rather than one that is guaranteed globally optimal. (And, as Raphael comments, to not backtrack on that decision).

For example, if you are training a graphical model, the process of repeatedly adding the edge that improves your model's fit the most, until no changes improve the model, is a greedy process. at each stage, you've taken the action which has the most incremental improvement over your current model, but the result may not be globally optimal.

Likewise, in the clustering example, to say that the clusters are merged greedily means that they are merged in the way that provides the best incremental improvement over other merges, but may not lead to the optimal clustering at the end.

---
Tags: algorithms, terminology, greedy-algorithms, data-mining
---


# Question
Title: How can I show context free grammars are strictly more expressive than regular expressions with an example?
I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot..

I have no idea what example is traditionally used for this.

# Answer
The canonical example is the language $L=\\{a^nb^n\mid n\ge 0\\}$. It's easy to produce a CFG for this and it's nearly as easy to show that it's not a regular language. For your first question, note that any regular language can be generated by a left-linear grammar and these are CFGs, so any regular language is also context-free.
> 3 votes

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


# Question
Title: Turing NP complete but not Karp NP complete?
Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction?

Conversely is there some examples of candidate problems that have Turing reduction to SAT but no known Karp reduction?

# Answer
The complement of any **NP**-complete problem (including SAT itself) is polynomial-time Turing-interreducible with SAT but, there's a Karp reduction if, and only if, **NP$\\,=\\,$co-NP**.
> 5 votes

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


# Question
Title: Solving recurrence relation when cost of all combining steps is constrained
I have a recurrence relation $T(n) = \left( \sum\_{i=1}^{k} T(d\_i n) \right) + f(n)$, where each $ 0 \< d\_i \< 1$, $f(x) \> 0$ for all $\\, x \> 0$ and $f(xy)=f(x) \cdot f(y)$ for $x,y\geq 0$.

I am asked to give an asymptotically tight bound on $T(n)$ if $\sum\_{i=1}^{k} f(d\_i) \< 1$ and if $\sum\_{i=1}^k f(d\_i) = 1$ using the substitution method, and I am told not to worry about the base case. I am following the substitution method from CLRS section 4.3 and basically means guess an upper bound, and then prove by induction.

I tried several guesses when $\sum f(d\_i n) \< 1$, but I get stuck regardless of my choice. If $T(n) = O(f(n))$, it must be true that \begin{align\*} T(n)&\leq c f(d\_1n) + c f(d\_2 n) + \dots + cf(d\_k n) + f(n)\\ &= c(f(d\_1 n) + f(d\_2 n) + \dots f(d\_k n)) + f(n) \\ &\< c + f(n) & \text{Since} \sum f(d\_i n) \< 1 \end{align\*} Which is false, unless $c \< 0$, which can't be the case.

If $T(n) = \lg f(n) $ then it must be true that

\begin{align\*} T(n) &\leq c \lg (f(d\_1 n)) + c \lg(f(d\_2 n)) + \dots + c \lg(f(d\_k n)) + f(n) \\ &=c \[\lg f(d\_1) + \lg f(n) + \lg f(d\_2) + \lg f(n) + \dots + \lg f(d\_k) + \lg f(n)\] + f(n) \\ &=c \left( \left(\sum\_{i=1}^{k} \lg f(d\_i)\right) + k \lg f(n) \right) + f(n). \end{align\*} Not sure how to proceed here. When I tried $T(n) = O\left(f(n)^2\right)$, I got

\begin{align\*} T(n) &\leq c \left( \sum\_{i=1}^n f(d\_i n)^2 \right) + f(n) \\ &\< c + f(n) & \text{ since } \sum f(d\_i n ) \< 1 \implies \sum f(d\_i n)^2 \< 1 \\ &\leq c f(n)^2 \end{align\*} which doesn't seem too tight, but I'm not sure. Any comments or pointers on how to proceed? I presume it involves incorporating the constraints on $\sum f(d\_i)$ in some other way, but right now I am not seeing how to do so.

# Answer
> 1 votes
Form a recursion tree. The root represents $T(n)$, and has weight $f(n)$. It has $k$ children, the edges are labelled $f(d\_1),\ldots,f(d\_k)$, and the children itself have weights $f(d\_1)f(n),\ldots,f(d\_k)f(n)$; they correspond to $T(d\_1n),\ldots,T(d\_kn)$. Each child has its own $k$ children, and so on, only we delete nodes corresponding to $T(m)$ for $m \< 1$. Note that the weight of each node is $f(n)$ times the weights of all edges from the node to the root. The total running time, assuming a base case around $1$, is the sum of all weights in the tree.

When $\sum\_{i=1}^k f(d\_i) \< 1$, we can compute the total weight of the infinite tree (without the pruning described above) as $$ f(n) \sum\_{t=0}^\infty (f(d\_1) + \cdots + f(d\_k))^t = \Theta(f(n)); $$ here $(f(d\_1) + \cdots + f(d\_k))^t f(n)$ is the total weight at level $t$. Thus in this case we have $T(n) = \Theta(f(n))$.

When $\sum\_{i=1}^k f(d\_i) = 1$, each full level contributes $f(n)$, and each partial level (where some nodes were pruned) contributes at most $f(n)$. There are $\Omega(\log n)$ full levels and $O(f(n))$ full or partial levels, and we conclude that $T(n) = \Theta(f(n)\log n)$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Is it possible that $\mathsf{L} = \mathsf{NP}$?
When I studied computer science 10 years ago, it was still an open question whether $\mathsf{L}$ and $\mathsf{NP}$ are truly different classes. Is that still the case or has the inequality been proven in the meantime?

(I know this is a somewhat stupid question, but there's nothing about it in the complexity zoo, and googling L and NP is surprisingly ineffective ;-))

# Answer
> 5 votes
$L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP$

From space hierarchy and time hierarchy theorems we can prove that

$L \subsetneq PSPACE$

$NL \subsetneq NPSPACE$

Note that we know $PSPACE = NPSPACE$.

$P \subsetneq EXP$

$NP \subsetneq NEXP$

Note that we don't know if $EXP \subsetneq NEXP$.

Whether the other inclusions are strict, are still open problems. Even though there are no proofs, many, but not all, believe most of the inclusions to be strict.

---
Tags: complexity-theory
---


# Question
Title: How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?
I did some quick math on how much data is contained on a screen at any given instant and I ended up with a number well beyond what I thought was possible. 256 colors for Red, Green, and Blue each define a pixel and there are currently 1920x1080 pixels on my screen so..

256 x 256 x 256 x 1920 x 1080 bits = 4.35 Terabytes of data

Obviously that would require more space than is on my desktop, let alone some Raspberry pi. So how do they do it? Any other resources anyone has for learning how displays work in general I'd love to have a look.

# Answer
You're confusing the number of possible values that a pixel can display with the amount of data being shown at any given instance. The number you give is the number of possible pixel states that your display can be in, multiplied by the number of pixels, which isn't really a meaningful number.

(EDIT: As Mehrdad and phihag point out, I'd incorrectly assumed you'd given the number of possible images. That number is actually $(256 \times 256 \times 256) ^ {1920 \times 1080}$, which is much larger than your number.)

The important detail is, at any time, a pixel is only in one state.

There are 256 possible values for each pixel, but we only are in one of them at any given time.

Any number between 0 and 255 can be encoded using 8-bits, just the same way you can write any number between 0 and 999999 using only 6 decimal digits. So there are 24 bits per pixel, or 3 bytes per pixel.

So 3\*1920\*1080=6220800 bytes, or just over 6MB.

Think of it like this, you as a person can verbally list all the digits in some 20-digit number, but you can't possibly list every 20-digit number. Your monitor could never in its lifetime display all possible images, but it certainly display one of those images.
> 7 votes

# Answer
By doing the math correctly. :-) Try keeping track of the units:

1 byte/color × 3 colors/pixel × 1920 pixels/row × 1080 rows/frame = **6,220,800 bytes/frame**

The more impressive part, I might note, is that at *60 frames per second*, this is **0.35 GiB/second**, which is pretty fast.
> 1 votes

---
Tags: computer-architecture, combinatorics, graphics
---


# Question
Title: What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?
The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book *Elements of Automata Theory* ascribes the algorithm to McNaughton and Yamada, who have indeed described it in their paper.

It might appear like a standard situation when one algorithm is ascribed to different authors. However, things seem to be more complicated. In fact, McNaughton and Yamada dealt with a converse problem (constructing a finite automaton to a rational expression) as well and Wikipedia's article on Thompson's construction refers to *this* algorithm as to the McNaughton-Yamada algorithm.

For this reason, I would like to ask what is the most correct name one can use for the Kleene/McNaughton-Yamada algorithm? In fact, I would also be interested in a correct name for a generalized algorithm, which works over arbitrary, say, complete (or closed, Conway, etc.) semirings. Thank you in advance.

P.S. Sorry for not providing a link to the McNaughton-Yamada paper, but I was not allowed to post more than 2 links.

# Answer
There is no such thing as a "correct" name. There is the name that is commonly used, which might depend on the community. This is what you would use unless you want to make a point. If you think that the common name doesn't give credit to the right people, you can use a different name, though you should also mention the common name so that others know what theorem you refer to.

Mathematical theorems and concepts are often named not after the first people who proved or defined them (if you're interested, you should be able to find several lists of such theorems and concepts online). Yet once a name has stuck, it is different to change it. That is because the most important goal of a name is not to give credit but rather to give a short name for a common concept. Indeed, sometimes results are not named after anybody, even though many of them were first proved by somebody.
> 1 votes

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


# Question
Title: Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$
$P^{\\#P}\subseteq P^{PP}$ and $\\#P\subseteq FP^{PP}$ are known and usually handwaived as exercises. I could not find proofs of these two results.

What is a rigorous proof for $P^{\\#P}\subseteq P^{PP}$ and $\\#P\subseteq FP^{PP}$?

How is having an oracle to $\\#P$ at most as powerful as having an oracle to $PP$?

# Answer
> 6 votes
This is not the full proof but the complete idea:

Let Turing machine $M$, define $L\_M$ be the language defined as $L\_M = \\{ ((x, y) \in \Sigma^\*\times \mathbb{N} ~|~ \\#\text{accepting path of } {M}(x) \> y \\} $

Then prove that $L\_M\in PP$.

Now use the binary search technique to compute the function g(x) in $\\#P$ using $L\_M$.

And other way around its easy by using $\\#P$ function TM you can always answer whether no. of accepting paths are more $\frac{1}{2}$ or not.

Let $L\in P^{\\#p}$, then there is a deterministic oracle Turing machine $M'$ that runs polynomial time, and a function $g\in \\#p$ such that $L= M'^{g}$. Let $M$ be a poly time Turing machine that uses at most $poly(n)$ non-deterministic steps such that $g(x)=\\# acceptig pathof M"(x)$. Use the standard binary search technique to show that $g(x)$ can be computed using $O(n)$ many queries to the language $L\_M$.

$x$, oracle access to $L\_M$ and output $g(x)$.

1. Initialize $p=|x|$, $y=2^p$.
2. Repeat steps 3 & 4 until $p\ge 0$
3. Query $(x,y)$ to the oracle; If YES, then set $y=y+2^{p+1}$;

Else

break .
4. Set $p=p-1$

Now we know the range for g which is $2^{p-1}\<g\<2^{p}$ $use binary search technique in this range and since there can be exponential terms hence binary search technique will take O(|x|) time.

Clearly, the algorithm above runs in time ${\sf poly}(n)$, and hence computing $g$ can be done in $poly$ with oracle access to $L\_M\in PP$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: The language of Turing machines that accept exactly $k$ inputs
For a fixed $k\geq 0$, let $X\_k = \\{\langle M\rangle\mid |L(M)|=k\\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X\_k$ recursive, recursively enumerable or neither?

I think $X\_k$ is NOT recursively enumerable because even if you generate every possible string, and test each one, if you find $k$ strings that M accepts, you still have to check every other string (in case $M$ accepts more than $k$ strings), which means your machine will loop indefinitely, and never find a yes-instance. However I'm not sure how you would show this, initially I thought I could reduce the NHP (Not Halting Problem) to L but that didn't go too well. Any ideas?

# Answer
> 1 votes
Hint: to decide whether $M$ halts on input $w$, consider a new machine $M'$ that rejects every input except $w$ and simulates $M$, otherwise. That's not quite the answer but it should get you close enough.

# Answer
> 0 votes
Please see a related question. Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

Though the question talks about $|L(M)| = 1$ the solution is general enough for any $|L(M)|$.

We can show $L\_u \leq X\_k$ as following. We reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows: $M'$ rejects all inputs other than $w$ and some other $k-1$ distinct strings. $M'$ accepts the other $k-1$ distinct strings as mentioned before. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L\_u$ iff $M' = f(\langle M,w\rangle) \in L$.

In fact we can prove that $X\_k$ is neither RE nor co-RE. This can be done by taking $k$ other distinct strings than $w$ in the above reduction.

---
Tags: computability, undecidability, decision-problem
---


# Question
Title: What are examples of $\mathsf{NL}$-complete problems?
Wikipedia lists exactly two problems as $\mathsf{NL}$-complete - 2-satisfiability and St-connectivity (although stating that there are "several"):

https://en.wikipedia.org/wiki/Category:NL-complete\_problems

My old literature on complexity (from study) also has no additional examples. And the complexity zoo also lists the graph reachability problem as sole example:

https://complexityzoo.uwaterloo.ca/Complexity\_Zoo:N

So, are there any other problems known to be $\mathsf{NL}$-complete?

# Answer
> 4 votes
Here are three more examples, taken from an assignment by Trevisan:

1. Given an NFA and a word, determining whether the NFA accepts the word.
2. Reachability in DAGs.
3. Determining whether a digraph is strongly connected.

Planken shows that the Simple Temporal Problem with bounded weights is NL-complete (see the link for definitions).

There are likely many others. Schaefer's dichotomy theorem, in particular, gives many examples.

---
Tags: complexity-theory
---


# Question
Title: Practical Applications of regular grammars
A regular grammar is a mathematical object, $G$, with four components, $G = (N, Σ, P, S)$, where. $N$ is a nonempty, finite set of nonterminal symbols, $Σ$ is a finite set of terminal symbols , or alphabet, symbols, $P$ is a set of grammar rules, each of one having one of the forms. $A → aB$.

I want to know what's Practical Application of these grammars. I mean where and how do we use these in real world?

Also it may be helpful if someone tells me about the weaknesses of regular grammars.

Thanks in advance.

# Answer
Regular grammars are more-or-less the same as NFAs, so you might as well ask what applications these have. Finite automata are used in compilers, for performing lexical analysis. Any course on compilation will contain ample information on this.

As for the weaknesses of regular grammars, they only describe regular languages. In particular, they're not enough to parse programming languages, even superficially. We use context-free grammars for that. Any course on formal languages and automata will explain all of that very clearly.
> 4 votes

---
Tags: regular-languages
---


# Question
Title: Convert integer of mixed radix to standard positional numeral system and vice versa
I have multiple numbers (e.g. `[1, 4, 2]`) where each number can be one of a specified range of numbers (e.g. `[0-1, 0-5, 0-3]`). I think one can represent my so chosen numbers by seeing them as digits of a number in the mixed radix numeral system with different bases for each position. In the above example, the bases would be `[2, 6, 4]` and the number would be `1 4 2`.

With the bases given in this example one could specify `48` different numbers (`2 * 6 * 4`). If I know the bases, how can I construct an algorithm that converts such a number to another number in a standard positional numeral system (like e.g. decimal, binary or hexadecimal) without just building a big generated lookup table? The conversion has to be bijective and there should not be any gaps - so for this example the mixed radix numbers should be represented by the integers from `0` to (inclusive) `47` in the decimal system.

Actually I want to encode these mixed radix numbers in binary data, so a gapless and bijective conversion to the binary system would be sufficient.

# Answer
If you have numbers $x\_1,\ldots,x\_n$ in the ranges $x\_1 \in \\{0,\ldots,b\_1-1\\},\ldots,x\_n \in \\{0,\ldots,b\_n-1\\}$, you can get a number in the range $\\{0,\ldots,b\_1\ldots b\_n-1\\}$ using the formula $$ x\_n + b\_n x\_{n-1} + b\_n b\_{n-1} x\_{n-2} + \cdots + b\_n b\_{n-1} \cdots b\_2 x\_1 = \\ x\_n + b\_n (x\_{n-1} + b\_{n-1} (x\_{n-2} + \cdots )). $$ The second formula gives an efficient way of calculating the transformation (from inside out), and also hints at calculating the inverse transformation efficiently.
> 3 votes

---
Tags: combinatorics, number-theory, integers, number-formats, numeral-representations
---


# Question
Title: Busy Beaver problem - Proof by contradiction
I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable:

> Find $\sum(n) = max \\{\sum(M) | M \in M(n) \\}$

Where

> $n$ : Number of states
>
> $M(n)$: Set of Turing Machines with $n$ states and binary alphabet (0s and 1s)
>
> $\[k\]$: Configuration of having a block of $k$ consecutive 1s on an otherwise blank (All 0) tape, and with the head at the leftmost 1.
>
> $e$: Empty tape (All 0s)
>
> $\sum(M): \sum(M) = k$ if machine $M$ when started on $e$ halts with $\[k\]$. Otherwise $\sum(M) = 0$

The proof:

> Suppose there is some Turing machine $\sum$ that computes $\sum(n)$. Then consider the following Turing machine $Q$ where $k$ is the number of states of the last 3 components:

I cannot understand from here, what exactly is the contradiction here?

# Answer
> 4 votes
I know it took me a few reads before a grasped what it was saying, so maybe if we build $Q$ in a different and (much) more verbose way, it'll help.

So let's start by assuming a Turing machine $\Sigma$ exist which, given a line of n 1's on an otherwise blank tape, can compute the busy beaver of n ($\Sigma(n)$) and write's out that many 1's on the tape. Now, this Turing machine has some number of states, which we will say is a.

Next, let's assume that another Turing machine, $+1$ which runs to the end of a line of 1's and adds one more 1 to that line. This Turing machine has some number of states, which we will say is b.

Next, let's assume that even another Turing machine exists, called $D$, short for Double. Given a tape with some number of 1's on it, it doubles the number of 1's on the tape. And let's say that it has some number of states c.

We now have three Turing machines, each with a, b, and c states respectively. So now let us define a number k, such that k = a + b + c.

Now let us build another Turing machine, $K$, short of Write K. $K$ will print out k 1's on a blank state, and have k states. A simple machine, where each state writes 1, moves to the next position on the tape, and then goes to the next state.

So now let's combine all our machines into one big machine.

We start with $K$, then go to $D$, then $\Sigma$, and finally $+1$. Let's call it $Q$. Now, to find the number of states $Q$ has, you have to add up the members. In order, that is k + c + a + b. And given that a + b + c = k, this mean that $Q$ has 2k states.

Now, let's run $Q$ and see what happens.

We start with a blank tape. Then $K$ runs and puts k 1's on the tape. Next, $D$ doubles this tape in size, so it now has 2k 1's on the tape. Next, $\Sigma$ runs and computes $\Sigma(2k)$ and prints that many 1's on the tape (replacing the 2k 1's). Finally, $+1$ runs and adds one extra 1 on the end of the line. So there are now $\Sigma(2k) + 1$ 1's on the tape.

Now, this means that $Q$, a Turing machine with 2k states, just wrote $\Sigma(2k) + 1$ 1's on a tape, which is impossible because the maximum number of 1's possible to write on a tape, given 2k states (and not counting cases that never halt), is $\Sigma(2k)$. Contradiction (and thus $Q$ cannot exist, and namely $\Sigma$ inside of $Q$ cannot exist).

In short, $Q$ has 2k states because we purposefully built it to have exactly 2k states to aid in creating the contradiction.

---
Tags: computability, undecidability, busy-beaver
---


# Question
Title: Program interpretation for static analysis
Are there any implementations, or even academic work, regarding an application capable of looking at code and inferring what the code actually intends to do? For example, we give it a program that calculates the SQRT(x); it should go and annotate that particular piece of code with SQRT(X), regardless of implementation technique. Say you use recursion instead of a for loop; it should still be able to infer what the code intends to do. Pattern matching is not really an option here.

Another example: Say you have a program that computes the sum of inverse squares, starting at 0. It should print out the mathematical equivalent of that expression as result. Something like SIGMA 1/x^i

# Answer
It's been hinted at in the comments, but in general, the task of giving *non trivial* explanations of an arbitrary piece of code by some automated analysis is impossible.

The first issue is giving a well-defined meaning to the term "program intent". The field of operational semantics can give us a precise definition of what a piece of code *actually does* when run on a concrete computer, under the hypothesis that the compiler or interpreter is free of programing errors, but the *intent* of the person who wrote the code can obviously not be divined from the code itself, e.g. a piece of code may be intended to say, crash if given a negative number as input, or that outcome may be the result of programmer oversight.

However it might be desirable to, say, infer various mathematical properties of an arbitrary piece of code, in your example you might want to infer

```
forall x, if x > 0 then SQRT(x)*SQRT(x) == x

```

This also is impossible to do in general. This somewhat surprising fact can be demonstrated using Rice's theorem, which essentially says that *any* property like the above statement can not be proven or refuted automatically for arbitrary programs.

That being said, there *has* been a substantial body of work which aims at identifying and proving properties such as the above for concrete program implementations. Because of Rice's theorem, such attempts must be incomplete, but in practice much can be done for "real world" programs. This field is usually designated under the term formal methods, and even a short summary would be significantly more effort than I'm ready to put forward right now. A good overview can be found here.
> 2 votes

# Answer
This is essentially impossible. Not only for programming languages, but for natural languages like English, even. For example, Google Translate can't actually determine the essence of what you are trying to say. All Google Translate does in reality is match a pattern (syntax recognition) with a few bells a whistles in the form of allowing for synonymous terms and phrases etc, to allow for more flexibility.

The extent to which semantic analysis is effective is actually very limited. Your question implied compiler implementation as the means to achieve some sort of semantic (meaning) derivation from any given program. The compiler can analyze tokens (words, symbols), then match a specific pattern of those tokens and label it as 'Expression' or 'Class' or 'VarDecl' or whatever, then it will analyze whether those recognized patterns are in the correct order, make sense in consideration of the particular context, whether it could be substituted for an equivalent expression of that same structure.

But as you can imagine, there is only a finite amount of rules you can instruct the compiler to recognize. But to attempt to build a compiler that can extract the ultimate meaning of your program is expecting it to do something that sometimes even *humans can't do* perfectly.

Sometimes we really underestimate the power of the human mind to extract meaning. To try and implement that functionality in a program is much like trying to implement a program which can really understand abstract things like a movie's meaning. Or a song. We just aren't at that level yet.

Again, you can implement a small, finite set of rules which allow your program to express one thing in many forms, but this *is* pattern matching. And essentially all semantic analysis is still pattern matching.

There is currently no algorithm computers can understand which can work with *real* abstractions. All of them are pattern-matching type algorithms which, ultimately can't recognize anything they aren't written to. *Real* abstraction would be necessary for truly determining the meaning of a program. That said, there is a *LOT* a compiler does to recognize structures and replace them, optimize them, completely remove them etc. - to the point where there isn't much need for them to understand what is being done as a whole. In fact, I don't think there are many programmers good enough to know how to replace a program *as a whole* and write it better, most of the time. So, it follows that the programmer responsible for writing a program capable of such would have to be good enough to do that himself, and even then, this would be hard to write down.
> 0 votes

---
Tags: artificial-intelligence, compilers, type-theory, type-inference
---


title: Arithmetic of asymptotic functions

text:
# Question
Title: Arithmetic of asymptotic functions
I faced some problem that involves arithmetic over asymptotic functions. These are as follows:

> 1. Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then \[f(n). g(n)\] + h(n) is:
>
> (a) $Ω(n)$
> (b) $O(n)$
> (c) $\Theta(n)$ (d) None of these

Solution to this was discussed as follows:

Let

* $n = 5$
* $f = 6$ so that $f = Ω(n)$ and
* $g = -6$ so that $g = O(n)$ and
* $h = 5$ so that $h = Ѳ(n)$
* $f.g + h = -36 + 5 = -31 \< n → f.g + h = O(n)$

Now let,

* $g = 4$ so that $g = O(n)$ and
* $f.g + h = 24 + 5 = 29 \> n → f.g + h = Ω(n)$

Hence option 4 is correct, None of these.

Then I came across another problem

> 2. Let $f(n)=Θ(n),g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)= ?$
>
> (a) $Ω(n)$ (b) $Ω(n^2)$ (c) $Θ(n)$ (d) $Θ(n^2)$

This problem was solved in completely different approach:

Using the definitions of notations:

$f(n)= θ(n)→ c\_1.n\<=f(n)\<=c\_2.n$ ... for $n\>n\_0$

$g(n)= θ(n)→ c\_3.n\<=g(n)\<=c\_4.n$ ... for $n\>n\_0$

$h(n)= Ω(n)→ h(n)\>=c\_5.n$ ... for $n\>n\_0$

Using the extended notations forms:

$c\_1.c\_3.n^2\<=f(n)g(n)\<=c\_2.c\_4.n^2$ ... for $n\>n\_0$

Taking $c\_1,c\_3=k\_1$ and $c\_2.c\_4=k\_3$

$k\_1.n^2\<=f(n)g(n)\<=k\_2.n^2$

Adding h(n)

$k\_1.n^2+c\_5.n\<=h(n)+f(n).g(n)\<=k\_2.n^2$ ... for $n\>n\_0$

As $n^2\>n$ for all $

$k\_3.n^2\<=h(n)+f(n).g(n)\<=k\_2.n^2$

Which simplifies to :

$f(n).g(n) + h(n) =Ω(n^2)$

Though I am able to appreciate both approaches, this leaves me a lot of confusion. I am not able to confidently apply these methods to each other, nor to other similar problems and reach the correct solution. Are these methods correct? In fact are these questions themselves correct? Is there more straightforward approach to solve such kind of problems?

# Answer
One way to help understand what's going on conceptually would be to draw a linear graph of what each of these functions mean.

So for example, say we're given a problem that tells us:

$g\_1(n)=\Theta(lg(n))$

$g\_2(n)=O(n^2)$

$g\_3(n)=\Omega(n)$

we can make a quick sketch of *where* they could be in relation to each other.

With this visual, we can get an idea of possible candidates for these functions.

So let's bring it back to one of the questions you had trouble understanding:

> Let $f(n)=Θ(n), g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)=?$

We know that $f(n)$ and $g(n)$ are both tightly bounded at $n$, so if you multiply them together, you'll clearly get $\Theta(n^2)$.

Now if we also add some function $h(n)$ that we know has a lower bound of $n$, the result must be $\Theta(n^2)+\Omega(n)$ which we can reduce to $\Omega(n^2)$, since an additional $...+\Omega(n)$ factor will be at its lowest value $n$ but there is no bound on how *high* this function can be (it could be anywhere from $n$ to $n^{1000}$ since there's no telling what an upper bound is), so we can conclude that it's $\Theta(n^2)+n=\Omega(n^2)$
> 2 votes

# Answer
The first question is somewhat ambiguous, since the answer depends on whether you're assuming all functions are non-negative or not; we usually make this assumption in complexity theory. In that case, $f(n)g(n) + h(n) \geq h(n)$, and so $f(n) g(n) + h(n) = \Omega(n)$. On the other hand, it's not always the case that $f(n)g(n) + h(n) = O(n)$: for example, if $f(n) = g(n) = h(n) = n$ then $f(n)g(n) + h(n) = \Theta(n^2)$.

For the second question, again we get $f(n) g(n) + h(n) \geq f(n) g(n) = \Omega(n^2)$. On the other hand, if $f(n) = g(n) = n$ and $h(n) = n^3$ then $f(n) g(n) + h(n) = \Theta(n^3)$, showing that it's not necessarily the case that $f(n) g(n) + h(n) = O(n^2)$.

I skipped some steps; the details are as in the answer to the second question, though that answer is only partial (it doesn't show that you can't conclude that $f(n) g(n) + h(n) = O(n^2)$).

On the other hand, the answer to first question is completely wrong: asymptotic notation doesn't say much about any specific $n$ (other than the usual assumption that all functions are non-negative). In particular, if $f(5) \> 5$ then we can't conclude that $f(n) = \Omega(n)$; perhaps $f(n) = 5$ for all $n$, for example.

You would do well ignoring whoever answered the first question. Unfortunately they have no idea what they're talking about.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Why does Karger's algorithm work "with high probability"
I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).

It states that a single round of contractions yields a min-cut with probability $\Omega(n^{-2})$ and concludes that $O(n^2 \log n)$ independent contractions are sufficient to find a min-cut with high probability.

It makes sense to me that $O(n^2)$ independent contractions yields a min-cut with a probability of approximately 1. Anything above this increases the probability, but why has $\log n$ being chosen?

# Answer
Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2})$, i.e. with probability $\ge \frac{c}{n^2}$ for some $c\>0$.

This is, of course, very bad. For large $n$ our success probability converges to zero. However, if we run it independently $k$ times, then our failure probability is now $\left(1-\frac{c}{n^2}\right)^k$ (we choose the minimal cut obtained from the $k$ runs, in order to fail finding the cut in this manner we must fail every time). Finally, we have:

$\Pr\left\[\text{failure}\right\]\le \left(1-\frac{c}{n^2}\right)^k\le e^{-\frac{kc}{n^2}}$, taking $k=n^2\log n$ we get:

$\Pr\left\[\text{failure}\right\]\le e^{-c\log n} = \frac{1}{n^c}$, which converges to zero, as apposed to our failure probability after a single run of the algorithm.
> 6 votes

# Answer
Approximately, if a chance NOT to find a cut in independent contraction is $1-\frac{a}{n^2}$, then a chance to find it in $n^2\log n$ contractions is $$ 1-\left(1-\frac{a}{n^2}\right)^{n^2\log n}=1-\left(\left(1-\frac{a}{n^2}\right)^{n^2}\right)^{\log n}\approx 1-\exp(-a\log n)=1-\frac{a}{n}. $$
> 4 votes

---
Tags: graphs, probabilistic-algorithms
---


# Question
Title: Difference between centralized computing and distributed computing using Client-Server
I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes from a type of distributed computing, where one type is the client server model. From what I know, the client server model has multiple clients using a network to access a server. How does this differentiate from calling it centralized computing?

# Answer
As a contrast to "distributed", "centralized" means one computer. Sometimes (not so much nowadays) this may be a mainframe with multiple "dumb" terminals in which all the work happens on the mainframe and the terminals just take in inputs and display outputs. If the terminals aren't "dumb", meaning they can do non-trivial computation of their own (and, in particular, maintain state), then this is essentially an example of a distributed, client-server system. Your description of "distributed" corresponds to a peer-to-peer system which is but one form of a distributed system.

Admittedly, there has been a level shift in the terms, and/or they are applied at a logical level. For example, Facebook would be considered a "centralized" system insofar as it's controlled by a single entity, as opposed to Diaspora which is decentralized. I think it has become popular to use the term "distributed" when "decentralized" may be a better term. Of course, Facebook has many servers spread across the world, and so it's infrastructure is very much distributed. Similarly, a single data center for Facebook may logically be a single "server" but internally is a distributed system as well consisting of hundreds of physical servers.

Wikipedia does a pretty good job of outlining the key characteristics of a distributed system from a theoretical perspective:

> Three significant characteristics of distributed systems are: concurrency of components, lack of a global clock, and independent failure of components.

Though I would add to that list that the communication medium is unreliable. The focus of distributed computing, in both theory and practice, is dealing with various forms of failure. Wikipedia's use of the more generic term "component" suggest that this notion can be applied at different levels. For example, you can fruitfully think of the various sub-systems of a single computer (on the motherboard) as forming a distributed system if your focus is on timing and failure issues. Even single multi-core CPUs are becoming more and more like distributed systems with the cores as the "components".
> 2 votes

---
Tags: distributed-systems, computer-networks
---


# Question
Title: Is this special case of a scheduling problem solvable in linear time?
> Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number, bonus points for only assuming comparability), if she misses the deadline.
>
> Write a function that given a list of (deadline, grade impact) figures out a schedule for which homework to do on which day that minimizes the sum of bad impact on her grades.
>
> All homework has to be done eventually, but if she misses a deadline for an item, it doesn't matter how late she turns it in.

In an alternative formulation:

> ACME corp wants to supply water to customers. They all live along one uphill street. ACME has several wells distributed along the street. Each well bears enough water for one customer. Customers bid different amounts of money to be supplied. The water only flows downhill. Maximize the revenue by choosing which customers to supply.

We can sort the deadlines using bucket sort (or just assume we have already sorted by deadline).

We can solve the problem easily with a greedy algorithm, if we sort by descending grade impact first. That solution will be no better than O(n log n).

Inspired by the Median of Medians and randomized linear minimum spanning tree algorithms, I suspect that we can solve my simple scheduling / flow problem in (randomized?) linear time as well.

I am looking for:

* a (potentially randomized) linear time algorithm
* or alternatively an argument that linear time is not possible

As a stepping stone:

* I have already proven that just knowing which items can be done before their deadline, is enough to reconstruct the complete schedule in linear time. (That insight is underlying the second formulation where I am only asking about certificate.)
* A simple (integral!) linear program can model this problem.
* Using duality of this program, one can check a candidate proposed solution in linear time for optimality, if one is also given the solution to the dual program. (Both solutions can be represented in a linear number of bits.)

Ideally, I want to solve this problem in a model that only uses comparison between grade impacts, and does not assume numbers there.

I have two approaches to this problem---one based on treaps using deadline and impact, the other QuickSelect-like based on choosing random pivot elements and partitioning the items by impact. Both have worst cases that force O(n log n) or worse performance, but I haven't been able to construct a simple special case that degrades the performance of both.

# Answer
A few things I found out so far.

We can reduce ourselves to solving the following related problem:

```
newtype Slot = Slot Int
newtype Schedule a = Schedule [(Slot, [a])]

findSchedule :: Ord a => Schedule a -> Schedule (a, Bool)

```

I.e. give the input data already sorted by deadline, but allow an arbitrary non-negative number of tasks to be done on each day. Give the output by just marking the elements on whether they can be scheduled in time, or not.

The following function can check whether a schedule given in this format is feasible, ie whether all items still in the schedule can be scheduled before their deadlines:

```
leftOverItems :: Schedule a -> [Int]
leftOverItems (Schedule sch) = scanr op 0 sch where
  op (Slot s, items) itemsCarried = max 0 (length items - s + itemsCarried)

feasible schedule = head (leftOverItems schedule) == 0

```

If we have a proposed candidate solution, and all items left out, we can check in linear time whether the candidate is optimal, or whether there are any items in the left-out set that would improve the solution. We call these *light* items, in analogy to the terminology in Minimum Spanning Tree algorithm

```
carry1 :: Ord a => Schedule a -> [Bound a]
carry1 (Schedule sch) = map (maybe Top Val . listToMaybe) . scanr op [] $ sch where
  op (Slot s, items) acc = remNonMinN s (foldr insertMin acc items)

-- We only care about the number of items, and the minimum item.
-- insertMin inserts an item into a list, keeping the smallest item at the front.
insertMin :: Ord a => a -> [a] -> [a]
insertMin a [] = [a]
insertMin a (b:bs) = min a b : max a b : bs

-- remNonMin removes an item from the list,
-- only picking the minimum at the front, if it's the only element.
remNonMin :: [a] -> [a]
remNonMin [] = []
remNonMin [x] = []
remNonMin (x:y:xs) = x : xs

remNonMinN :: Int -> [a] -> [a]
remNonMinN n l = iterate remNonMin l !! n

data Bound a = Bot | Val a | Top
  deriving (Eq, Ord, Show, Functor)

-- The curve of minimum reward needed for each deadline to make the cut:
curve :: Ord a => Schedule a -> [Bound a]
curve = zipWith min <$> runMin <*> carry1

-- Same curve extended to infinity (in case the Schedules have a different length)
curve' :: Ord a => Schedule a -> [Bound a]
curve' = ((++) <*> repeat . last) . curve

-- running minimum of items on left:
runMin :: Ord a => Schedule a -> [Bound a]
runMin = scanl1 min . map minWithBound . items . fmap Val

minWithBound :: Ord a => [Bound a] -> Bound a
minWithBound = minimum . (Top:)

-- The pay-off for our efforts, this function uses
-- the candidate solution to classify the left-out items
-- into whether they are definitely _not_ in
-- the optimal schedule (heavy items), or might be in it (light items).
heavyLight :: Ord a => Schedule a -> Schedule a -> ([[a]],[[a]])
heavyLight candidate leftOut =
    unzip . zipWith light1 (curve' candidate) . items $ leftOut
  where
    light1 pivot = partition (\item -> pivot < Val item)

```

`heavyLight` not only checks a proposed schedules for optimality, it also gives you a list of items that can improve a non-optimal schedule.
> 1 votes

# Answer
No. This is not a special case of a flow problem solvable in linear time. Because complexity is given by $O(n^2)$ and while sorting itself we get complexity as $O(n\log n)$ and in order to execute all the other n processes complexity definitely wouldnt remain linear.
> -5 votes

---
Tags: algorithms, optimization, randomized-algorithms, network-flow, scheduling
---


# Question
Title: Genetic Algorithms - Tournament Selection
I know this should be a fairly simple concept but I have been Googling a lot and can't seem to find a definitive definition.

If we had the following random population:

```
[12,2,3,99,73,32,53,8]

```

And a tournament size of 3. What could be a possible outcome?

Is there lots of variations of Tournament Selection?

# Answer
> 4 votes
A simple version of tournament selection is as follows.

> 1. Select $k$ random Individuals from the population.
> 2. Select the best Individual from the $k$ Individuals.
> 3. Repeat from 1 until you have selected the desired amount of Individuals.

---

As an example. Consider your data, $k=3$ and that we wish to select 3 Individuals.

$\[12,2,3,99,73,32,53,8\]$ (your data).

$\[12,2,99\]$ (3 random Individuals).
$99$ is the best Individual.

$\[2,73,53\]$ (3 random Individuals).
$73$ is the best Individual.

$\[99,8,53\]$ (3 random Individuals).
$99$ is the best Individual.

We have selected the Individuals $73,99$ and $99$.

Note that we have selected $99$ twice. If this is not desired, you can delete an Individual from the population if it has been selected.

It is also possible, instead of always selecting the best Individual, to select an Individual according to some stochastic scheme. For example, assign the best Individual from the tournament pool (the $k$ randomly selected individuals) $i=0$, the second best $i=1$, ... (etc), and the worst Individual $i=k-1$. Then Individual $i$ is selected with chance $\frac{2(k-i)}{k(k+1)}$.

I just made this stochastic scheme up. You can use your fantasy on how to extend/alter tournament selection or any other genetic operator :)

---
Tags: genetic-algorithms
---


# Question
Title: Order Notation - Why can't $c$ be in terms of $n$?
For $f(n)$ to be in $O(g(n))$, there must exist a $c \> 0$ and $n\_0 \> 0$ such that

$$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n\_0\\,.$$

I found a solution to a question where my $c$ is in terms of $n$, but my friend says you can't have that. I'd like to understand why. My thought process is: if I am given an $n$, I can pick a distinct $c$ that will satisfy the requirements above by using the $c$ in terms of $n$ relationship.

Thank you.

# Answer
> 4 votes
Suppose we define $f(x) = O'(g(x))$ to mean that there is a function $c(x)$ such that $f(x)\leq c(x)g(x)$ for all sufficiently large $x$. Then $f(x) = O'(g(x))$ for almost every pair of functions $f$ and $g$, just by taking $c(x)=f(x)$. So, this definition just isn't a useful way to compare functions.

(I say "almost every pair" because there are issues if we have infinitely many values of $x$ for which $g(x)=0$ and $f(x)\neq 0$ but I don't think it's worth pinning down exactly what functions work and what don't.)

---
Tags: landau-notation
---


# Question
Title: What is the fastest addition algorithm on a turing machine?
What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a\_1+a\_2$ where $a\_1$ and $a\_2$ are written out in the usual decimal expansion, and the output on the tape is just the result, $a\_1+a\_2$ (there is no need to keep the inputs). The best I can do so far is $O(n^2)$ time using this program I made: http://morphett.info/turing/turing.html?185f35a035e386d2a927c15b869b422a

The way this algorithm works is by finding the rightmost "non-added" digit of the number to the right of the addition sign (henceforth No. 2), marks this with an "o", and moving left until it finds a "non-added" digit of the number to the left of the addition sign (henceforth No. 1) and marking the result with a letter so that the machine will know how many decimal places to go to the left when adding next time. If there are any carries, these places are marked with numbers rather than letters because they haven't been 'reached' yet other than by the carry. The machine ends when all the digits on the right-hand number have been turned into "o"s and the machine encounters the plus sign instead of a number. Then, it cleans up all the "o"s and transforms all the letters into numbers and deletes any 0's at the beginning of the number.

I won't provide a rigorous proof, but this algorithm can be seen to be $O((n\_2)^2)$ time complexity intuitively by the fact that for each digit in No. 2, the turing machine has to move about $n\_2$ (which I use to denote the length of $a\_2$) steps to the left, and since there are $n\_2$ digits in No. 2, this algorithm takes about $n\_2\times n\_2=(n\_2)^2$ steps. (Thus it runs in $O(n^2)$ time, assuming both numbers are of the same length, $n\_1=n\_2=n$). This improves on the naïve exponential time implementation of just subtracting one from No. 2 and adding one to No. 1 until No. 2 is exhausted, but is there any faster algorithm?

EDIT: Just to clarify I want the fastest algorithm for adding two decimal numbers of *equal length*, $n$. I use $n\_1$ and $n\_2$ as the lengths of $a\_1$ and $a\_2$ respectively only to emphasize that the algorithm is technically only quadratic in $n\_2$, which is where it gets the $O(n^2)$ runtime from. I tried calculating the exact number of steps the algorithm takes, which is $n\_1+2(n\_2)^2+5n\_2+max(n\_1,n\_2)+5+2c+d$, where c is the number of carries (bounded by $n\_1$) and d is the number of digits in the result. Thus, a more precise runtime would be $O((n\_2)^2+n\_1)$, but left this out for conciseness and because in the end I only cared about the case $n\_1=n\_2=n$.

# Answer
> 1 votes
(This should be a comment but I can't comment yet)

Just to clarify, when you have an integer $n$, it's represented on $\operatorname{size}(n)=\log\_2 n$ bits.

So here, you are given $n\_1$ and $n\_2$ and you want to compute $n\_1+n\_2$. Let $f(n\_1, n\_2)$ be the number of steps needed to compute that. You seem to be claiming that $f(n\_1, n\_2)=O\left((n\_2)^2\right)=O\left(\left(2^{\operatorname{size}(n\_2)}\right)^2\right)$, which is obviously false. Now if you change it to $f(n\_1, n\_2)=O\left((\operatorname{size}(n\_2))^2\right)=O\left((\log\_2 n\_2)^2\right)$, it becomes a little bit more plausible.

But that still can't be the complexity because if you have $n\_1=2^{k}-1$ and $n\_2=2^0$, your algorithm will at least read $n\_1$, which takes $O\left(\operatorname{size}(n\_1)\right)=O\left(\log\_2 n\_1\right)=O(k)$ while $O\left((\log\_2 n\_2)^2\right)=O(1)$ in these cases. The complexity should depend on the size of $n\_1$ one way or another.

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


title: Questions about SIMD instructions

text:
# Question
Title: Questions about SIMD instructions
What is the trend over time for the size of registers of x86 CPUs? I know that we have today 512-bit registers, but is there a kind of Moore's Law to predict the size of registers in the future?

Thank you very much.

# Answer
> 5 votes
Moore's law is only indirectly involved here. NVidia's SIMD registers are 1024 bits wide, have been that wide since at least 2006, and haven't grown. Intel's slowly grew from 64-bit MMX in 1996, to 128-bit SSE in 1999, to 256-bit AVX in 2008, to the 512-bit AVX-512 in 2015.

My prediction is that neither Intel nor NVidia will grow their SIMD registers any wider from here on out. The cost would be large, and the benefits decrease with each doubling.

The reason the cost would be large for Intel is that Intel has a whole bunch of inter-related design decisions that would need to be revisited. Intel processors have used a cache-line width of 512 bits since the Pentium-4. The cache ports to the cpu pipeline are 512-bits wide. The BTB designs probably assume 64-byte cache lines. I assume the coherence busses for multi-socket systems are 512-bits wide. (I'm in the software division, not the hardware division.) There is probably quite a bit of legacy code that has now been optimized for 512-bit cache lines. For example: to avoid false-sharing overhead on cache lines, data structures may be aligned on 64-byte boundaries. Customers would get annoyed if they spent thousands of dollars for a new server only to discover that their legacy code now runs *slower*. I would guess that NVidia faces similar constraints.

The benefits decrease with each doubling because of something similar to Amdahl's law. The benefit of SIMD is supposed to be that you double your ALU bandwidth, while keeping the area (and power) of the rest of your pipeline constant. Suppose your processor is 16mm2, of which 1mm2 is your 32-bit ALU and register file, and you are getting 1 GFlOPS. That's 1/16 GFlOPS/mm2. Move to 64-bit SIMD, and your performance doubles, but so does the size of your ALUs and register file. So now you are getting (at best) 2 GFloPS/17mm2, which is almost twice as good. But when you get up to 512-bit SIMD you have 16 GFlOPS/31mm2. Now doubling to 1024-bit SIMD gets you to 32 GFlOPS/47mm2, which is only 32% better.

---
Tags: computer-architecture
---


title: Implications of Pessiland

text:
# Question
Title: Implications of Pessiland
Consider 3COL (three colourability), Travelling Salesman, 3SAT and 2SAT. Which of these problems can be solved in polynomial time if we happen to live in world 3 (Pessiland).

My Thinking - We know that 2SAT is a P problem and so we can solve it in polynomial time even though we are in Pessiland however I am unsure on what the implications are for 3COL, travelling salesman and 3sat!

5 Worlds I refer to - http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html

# Answer
The only world in which NP-complete problems (e.g. 3sat, 3colorability, traveling salesman) are solvable in polynomial time is Algorithmica, i.e. $P=NP$.

The rest of them refer to various conjectures that might hold within $P\neq NP$, for example $NP$ problems are hard/easy on average, or one way functions do/don't exist.
> 3 votes

---
Tags: np-hard, decision-problem
---


# Question
Title: What exactly (and precisely) is "offset"?
Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?"

Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the computing world. Of course, I have come across it while mounting a disk image; but does it have any other usage than that. I ask this because I have come across the word at other places. Does it have to do anything with memory registers?

# Answer
An offset is a difference between two indices, usually memory locations or array indices.

For example, suppose that you have an array $A$ in which each element occupies $x$ bytes. Suppose also that the address of $A$ is $M$. Then the address of the $i$th element (counting from zero) is $M + i \cdot x$. Here $i \cdot x$ is the offset. It's the difference between the address of the $i$th element and the address of the array (which is the address of the zeroth element).
> 4 votes

---
Tags: data-structures, computer-architecture, partitions
---


title: Bidirectional Dijkstra vs Dijkstra

text:
# Question
Title: Bidirectional Dijkstra vs Dijkstra
Are there any kind of graphs where Bidirectional Dijkstra would expand more than Dijkstra?

I tried to come up with an argument like this:

Let node $n$ be expanded by Bidirectional Dijkstra. Now there are two possibilites:

1. Node $n$ was expanded in the forward search
2. Node $n$ was expanded in the backward search

If $n$ was expanded in the forward search, then it would have been expanded in Dijkstra's algorithm also because forward search of Bidirectional Dijkstra is essentially just Dijkstra stopped earlier.

If $n$ was expanded in the backward search, there are two cases possible:

1. $n$ is on the actual shortest path between start and goal.
2. $n$ is not on the shortest path between start and goal.

If $n$ is on the actual shortest path between start and goal, then $n$ will also be expanded by Dijkstra. If $n$ is not on the shortest path between start and goal, then $n$ might not be expanded by the Dijkstra.(I am not sure how to use this case. Does this suggest that Bidirectional Dijkstra can expand more nodes than Dijkstra?)

# Answer
Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following your reasoning.

Consider a graph $G(V, E)$ where $V$ is the set of vertices, $E$ is the set of edges and you want to find the shortest path between two vertices $s, t\in V$ (from source and target respectively). Say there is a single path of length $\ell$ from $s$ to $t$, $\pi\langle s, u\_1, u\_2, \ldots, u\_{\ell-1}, t\rangle$. Let us assume further:

1. $s$ has only one descendant, $u\_1$
2. And, in general, $u\_i$ has only one descendant, $u\_{i+1}$, $1\leq i\<\ell - 1$

However, $t$ has many different descendants: $\\{v\_1, v\_2, \ldots, v\_k\\}$. For the sake of clarity, let us assume without loss of generality that the cost of all edges is 1 and that the path $\pi\langle s, u\_1, u\_2, \ldots, u\_{\ell-1}, t\rangle$ is the only optimal path.

Now, Bidirectional Dijkstra would expand first $s$ in the forward search and then $t$ in the backwards search. The forward OPEN list contains only $u\_1$, whereas the backward OPEN list contains $\\{v\_1, v\_2, \ldots, v\_k\\}$ and $u\_{\ell-1}$. Next, $u\_1$ is expanded in the forward search and the forward OPEN list only contains $u\_2$. However, the backward search might choose $v\_1$ for expansion. This is your case! $v\_1$ does not belong to the optimal path, yet it is expanded by Bidirectional Dijkstra (admittedly, this depends on the tie breaking strategy but assume $k$ is too large and ties are broken randomly). In the end, the forward search would go all over $\pi$ whereas the backwards search might be entertained expanding descendants of nodes $v\_i$.

However, the Unidirectional search algorithm would have gone all the way through $\pi$, as it is its only choice, finding the goal node in precisely $\ell$ expansions.

To prevent this, *Ira Pohl's principle of cardinality* is applied often. It dictates to expand nodes from the OPEN list with less nodes. In this case, it would suggest expanding only nodes from the forward search, making Bidirectional Dijkstra to behave like Unidirectional Dijkstra. However, it should not be very difficult to make some maths to find a little bit more involved case where *Ira Pohl's principle of cardinality* does not help and Bidirectional Dijkstra still expands more nodes than Unidirectional Dijkstra.

In general, we say that Bidirectional Dijkstra expands only $O(b^{d/2})$ nodes whereas Unidirectional Dijkstra has to expand $O(b^d)$ nodes, but this assumes that the branching factor is the same for the forward and backward search.

For a much broader discussion on the topic which also includes the intricacies of applying bidirectional search to heuristic search I do strongly recommend you reading: Robert C. Holte, Ariel Felner, Guni Sharon, Nathan R. Sturtevant. Bidirectional Search that is guaranteed to meet in the middle. AAAI 2016.

Hope this helps,
> 7 votes

---
Tags: search-algorithms, artificial-intelligence
---


title: In Minimax, how should we handle draws?

text:
# Question
Title: In Minimax, how should we handle draws?
A player playing the Minimax strategy should choose moves which minimise their maximum loss.

What should happen when draws can happen? Should we class the draw as a win because we aren't losing? Or should be class it as a loss because we are trying to win the game and a draw isn't a win? Or should we just class a draw as its own end point?

# Answer
Minimax strategies apply to games with *scores*. A minimax strategy maximized the guaranteed score. Assuming that you prefer a win to a draw and a draw to a loss, you can choose three scores $a \> b \> c$ arbitrarily and assign them as your value in the case of a win, a draw, and a loss, respectively.
> 5 votes

---
Tags: game-theory
---


# Question
Title: Why descriptive power of context-free grammar is greater than regular expression?
Below is a saying from this article.

> Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the strings matched by the expression. But, the reverse is not true: not every grammar can be converted into an equivalent regular expression.

Can anyone tell me if the saying is correct and why? Per my understanding, they should have same power and the differernce is a context-free grammar has recursive definition.

# Answer
Let the set of languages that can be represented by regular languages be $R$. And set of languages that can be generated by a context free grammar be $G$. Then surely $ R \subset G$. For the proof that every regular language has a context free grammar that generates it, I encourage you to look up Michael Sipser's book on complexity. And for the second part, there are many languages which have a context free grammar generating them but are not regular. For example $L=\\{ww^{reverse}\\}$, where $w^{reverse}$ is reverse of the string $w$. How do we know $L$ has a context free grammar ( you can easily come up with a push down automaton for it ), look up Sipsers. And look up pumping lemma in the book to prove $L$ is not regular.
To get an intuition, any regular language can be represented by a finite state automaton ($FSA$) and vice versa. And any context free grammar can be represented by a pushdown automaton ($PDA$) and vice versa (again, read the proof from Sipser). And in a $PDA$, in addition to the states (like in $FSA$), you also have an infinite stack. Thus intuitively context free grammars have "power" greater than that of $FSA$.
> 1 votes

---
Tags: context-free, formal-grammars, regular-expressions
---


title: Multi-threading vs. Interrupt Handlers

text:
# Question
Title: Multi-threading vs. Interrupt Handlers
In Arduino's architecture, multi-threading is not supported. However, interrupt handlers are being used as "placebo/replacement" if you may. However, I am not quite sure how these interrupt handlers work. For instance:

```
void functionA()
{    //x is a global boolean
    x = true; //as soon as this is set to true, before the next line executes, it jumps to functionB
    int y = 10;
}
void functionB()
{
    while(x) executeSomeOperation;
}

```

Something of that sort takes place(forgive my crude code, it is just to get my point across). More specific examples can be found in the VirtualWire library of Arduino. How is that possible without multi-threading? Because as function A is taking place, the program must surely be waiting to see if `x` is being set to true. Which sounds like "multi-threading" to me. **Thus, can someone clarify the differences between how multi-threading and interrupt handlers work?**

# Answer
**Threads**
On a platform that supports multi-threading the threads run in parallel.
That means that multiple threads can run at the same time.
This depends on the numbers of cores the CPU makes available.
If the programmer insists on running more threads than the CPU has cores then the threads will be time-sliced.
How much time each thread gets depends on the priority of that thread.
A thread can also choose to yield, which means that it will transfer execution time to another thread before its time slice is up.
If a thread does not yield the scheduler (which is part of the operating system) will pause the thread and force another thread to run.

**Interrupt handler**
An interrupt handler interrupts the main program. That means that the state of the thread is saved and execution is paused.
The interrupt handler is executed and when the interrupt handler yields the state of the main program is restored and execution of the main program resumes.

In many systems the interrupt handler is assigned a standard interruption schedule, e.g. 50 times a second.
The interrupt is always given preference over the main program, so if the interrupt takes up a lot of time the main program will get very little or no time to run. The interrupt gets scheduled no matter what. The main program gets whatever time is left over.
An interrupt handler is not subject to a scheduler, although possibly the interrupt can be interrupted by another interrupt.

**Time slicing**
In contrast, threads (insofar as threads outnumber CPU cores) are time sliced. Every thread gets the same amount of time. If there is a high priority thread it may get more time or get scheduled more often, but the scheduler makes sure every thread does get a time slot now and then.

**Interrupts don't play nice**
Because an interrupt handler will get prioritized over the main execution it is unwise to treat it like a thread. If you do heavy calculation in an interrupt handler your main program will never run!
This is made worse by the fact that interrupts are usually scheduled to run many times a second.

**Alternatives**
There is an alternative to abusing the interrupt handler for multi-threading.
You can use fibers on Arduino.
Fibers are cooperative threads, that means that a single thread will run until it yields.
After a yield the next fiber in line will run.
As long as all fibers yield in a cooperative manner this works very much like real pre-emptive threads.
If one fiber does not yield, none of the other fibers will get any running time.
This is the multi-tasking mechanism that was used in Windows 3.x

Just to make things confusing libraries that support this behavior talk about threading, not fibers.
Note that threading is impossible on Arduino, so these misnamed 'threads' are really fibers.
> 3 votes

---
Tags: multi-tasking
---


# Question
Title: How come Google search never gets slower? Doesn't it have to go through the ever increasing amount of data on the internet and then rank?
I heard Google creates indexes of pages. Even then, the number of indexes goes with time. Why wouldn't this slow down the search?

# Answer
The google indexing and search is run in parallel using a map-reduce algorithm.
As the number of pages to index expands, so does the number of computers that google uses for the task.

Currently Google handles about 3.5 billion searches per day.
A single search uses 1 000 computers in parallel (each computer holds $\frac{1}{1000}$ of the total Google index) and takes on average 0.2 seconds.

Servers available for search are always in read-only mode. When the search index gets updated those servers are temporary unavailable for search.

Given the current amount of floor-space in its data centres Google has a maximum of about 1.7 million servers.
Obviously most of these are devoted to something other than search.
> 3 votes

---
Tags: search
---


# Question
Title: Showing a language is context free. Use PDA or CFG?
I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it.

Show language $L$ is context free, where $L = \\{\text{all strings where middle two symbols are the same}\\}$

# Answer
For this problem, it's easier to come up with a CFG than it is to invent a PDA. First, notice that the strings should all be of even length, otherwise it's not clear what "middle two symbols" should mean. Here are some hints to get you going.

**Hint 1**. Could you have grammar rules $T\rightarrow (something)$ which would generate all strings $xx$, where $x$ is a symbol from your alphabet?

**Hint 2**. If you had a start variable $S$, could you make productions of the form $S\rightarrow (symbol\_1)\\; S\\; (symbol\_2)$ that would generate all sentential forms $\alpha\\;S\\;\beta$ where $\alpha$ and $\beta$ can be any strings over your alphabet and have the same length?

If you can do these two tasks, the CFG is easy.
> 1 votes

---
Tags: computability, context-free, automata, formal-grammars, pushdown-automata
---


# Question
Title: How to calculate the time complexity of a Catalan-like recurrence by substitution?
I was given the following problem:

> Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum\_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \geq 2 \end{cases}$$ *using the substitution method.* **Answer:** $\Omega(2^n)$.

I have seen there is a *closed-form* for this recurrence but I am unsure whether it can be used out of the blue or not. I don't know if I have to prove it by deriving it from the recurrence or if there are simpler ways of solving such a problem by mere substitution.

On the other hand, I think substitution is not the right tool to use here. I have tried with both reverse and forward substitution, but in neither approach I could determine the function as with other problems (e.g. QuickSort).

*Is it possible to solve this problem with only substitution at all? If so, how can I devise it?*

# Answer
You can use induction. First, check directly that $P(n) \geq 2^{n-2}$ for all $n \leq 4$ (the relevant values are $1,1,2,5$). Now suppose that $P(n) \geq 2^{n-2}$ holds for all $n \leq m$, where $m \geq 4$. Then $$ P(m+1) = \sum\_{k=1}^m P(k) P(m+1-k) \geq \sum\_{k=1}^m 2^{k-2} 2^{m+1-k-2} \geq m 2^{m+1-4} \geq 2^{m+1-2}, $$ since $m \geq 4$.
> 4 votes

# Answer
For the record, I'll describe here the procedure that I was looking for (after being oriented by my instructor).

1. A *closed form* was indeed needed to solve the problem. From here, I took this recurrence:

$$P(0) = 1, P(n+1) = \frac{2(2n+1)}{n+2} \cdot P(n)$$

2. Using reverse substitution, and then letting $j = (n-k)+2$, I ended up with

$$P(n) = 2^n \prod\_{k=1}^{n} \frac{2(n-k)+1}{(n-k)+2} = 2^n \prod\_{j=2}^{n+1} \frac{2j-3}{j} = 2^n \prod\_{j=2}^{n+1} \left( 2 - \frac{3}{j} \right)$$

3. I proved by induction that $P(n) \geq 2^n\ \forall\ n \geq 5$, in order to use $n\_0 = 5$ in the formal definition of $\Omega\[f(n)\]$, which for completeness, is

$$\Omega\[f(n)\] = \\{g(n) \mid \exists\ c \> 0, n\_0 \> 0 : 0 \leq cg(n) \leq f(n)\ \forall\ n \geq n\_0\\}$$

4. Finally, using $n\_0 = 5$ and the formal definition, it is shown $P(n) \in \Omega(2^n)$.

If my reasoning is flawed, please leave a comment and I'll edit accordingly.
> 2 votes

---
Tags: recurrence-relation
---


title: When the heapsort worst case occurs?

text:
# Question
Title: When the heapsort worst case occurs?
The best-, average-, and worst case time complexity of Heapsort for $n$ *distinct keys* are all $\Theta(n \lg n)$.

> What are the worst-case inputs for heapsort?

# Answer
Please check the paper@arXiv2015: A Complete Worst-Case Analysis of Heapsort by M. A. Suchenek.

This paper gives a rather involved lower bound; see Abstract and Theorem 12.2 on page 94.

To the specific question,

> Example of a 500-node worst-case array for Heapsort, created by my Java program, is included in Appendix A.3 page 110.
> 6 votes

---
Tags: time-complexity, heap-sort
---


title: Complexity of the Dijkstra algorithm

text:
# Question
Title: Complexity of the Dijkstra algorithm
I'm little confused by computing a time complexity for `Dijkstra` algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I understand. It's because for each node, we could theoretically relax edges going to each vertex so it is $n * n$ times, respectively $n(n-1)$.

On the other hand, I can't figure out why this complexity isn't $O(|E|+|V|)$. For each $v \in V$, we relax only those edges $e$, which weren't computed yet. If vertex $v$ is already computed (red on gif above), we don't need to work with it anymore.

So can I say that in one way, it is true that `Dijkstra` is in $O(|V|)$, but if we can put into the computation number of edges, I can say that it is in $O(|V|+|E|)$?

# Answer
> For each v from V, we relax only those edges e, which werent computed yet. If vertex v is already computed (red on gif above), we don't need to work with it anymore.

Your are assuming that each edge is visited only once, but this assumption is not quite right. Let's say we have two sets $S$ and $S'$, such that $V=S \cup S'$ and $S$ is the set of vertices, for which we have found the shortest path from source $s$. Each time, we need to find an edge $e=(u,v)$ ($u \in S$ and $v \in S'$) that sits on a shortest path, but how do you find this edge? You need to either

(1) use a brute-force algorithm and spend $O(|V|)$ to look at all edges $e=(u,v)$ ($u \in S$ and $v \in S'$) for finding the minimum one, which takes $O(|V|^2)$ (because each time you are looking at the same edge that are not in the shortest path).

or

(2) use a min-heap and spend $O( \log |V| ) $ for finding that edge, and achieve $O( (|V| + |E|)\cdot \log |V| )$ overall running time.

However, if the graph is **unweighted**, your assumption is right and you can achieve the running time $O(|V|+|E|)$.
> 2 votes

---
Tags: graphs, time-complexity, shortest-path
---


# Question
Title: Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?
Given a DAG (directed acyclic graph) $G=(V,E)$ without *multiple edges*, i.e., edges with the same source and target vertices, we define:

A vertex $v\_j \in V$ is a diamond-join ($\Diamond\_J$) vertex if there exists some other vertex $v\_f \in V$ *such that* there are at least two *vertex-disjoint* paths (except $v\_f$ and $v\_j$) from $v\_f$ to $v\_j$.

Furthermore, we call such a corresponding vertex $v\_f$ above a diamond-fork ($\Diamond\_F$) vertex. And, we call such a pair $(v\_f, v\_j)$ above a diamond ($\Diamond$) pair.

---

***An Example:*** In the figure below,

* $E$ and $F$ are $\Diamond\_J$ vertices.
* $A$ and $C$ are $\Diamond\_F$ vertices.
* $(A,E), (A,F)$ and $(C,F)$ are $\Diamond$ pairs.

---

***The problems are:***

> 1. How to identify all the $\Diamond\_J$ vertices?
> 2. How to identify all the $\Diamond\_F$ vertices?
> 3. How to identify all the $\Diamond$ pairs?

The algorithms should be as efficient as possible. For example, are there linear algorithms, i.e., in $\Theta(n + m)$, for them, where $|V| = n, |E| = m$?

---

***My Thoughts:***

The first problem is easy: Run DFS on $G$ and the vertices pointed to by ***cross edges*** are the $\Diamond\_J$ vertices.

I do not know how to solve 2&3 efficiently.

---

***Edit (2016-05-11):*** I accept the answer by @Chao Xu which solves the third problem in $O(nm)$ (I think it is correct; please peer review it). I am still open to possibly more efficient algorithm for the third problem, like $O(n+m)$.

# Answer
$G=(V,E)$ is the graph we work on.

Problem 2: $\Diamond\_F(reverse(G))=\Diamond\_J(G)$, where $reverse(G)$ reverses all the edges of G.

Problem 3: This can be solved in $O(nm)$ time. For each vertex $s$, find all the pairs $(s,v)\in \Diamond$ in $O(m)$ time. To do this and split every outgoing edge $(s,v)$ with a new vertex $v'$. Namely, delete edge $(s,v)$, and replace it with $(s,v')$ and $(v',v)$. Find the dominator tree with source $s$ in the new graph, which can be done in linear time for dags.

$(s,v)\in \Diamond$ iff $v$ is the children of $s$ in the dominator tree and $v\in V$.
> 3 votes

---
Tags: algorithms, graphs, graph-algorithms, dag
---


# Question
Title: Language of TMs such that one state is visited most often
To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q\_0, \delta, q\_F)$, where $Q$ is the finite state set, $\Sigma \subset \Gamma$ are the input and working alphabet, $q\_0, q\_F$ are the initial and final states, and $\delta : Q \times \Gamma \times Q \times \Gamma \times \\{L,N,R\\}$ is the transition function. I am talking about single-tape TMs without input or output tape, so the initial configuration of input $w$ is just $B^{-\omega} q\_0 w B^\omega$, where $B$ is the blank symbol.

The language I am considering is $L$ of all Turing machines $M$ which satisfy the following: There is a state $q$ of $M$ such that on the run of $M$ on the empty word $\varepsilon$, $q$ is visited more often than any other state.

"More often" talks about the cardinality, i.e. $q$ is visited more often than $p$ if $p$ is visited $n$ times (finitely often) and ($q$ is visited infinitely often or $q$ is visited finitely often but $\>n$ times).

I came up with this language as an exercise for students, when I found that neither I nor any colleague I asked could come up with precise decidability results.

It is clear that $L$ is not coRE and therefore undecidable. We can, for example, reduce the epsilon halting problem $H\_\varepsilon$ to $L$ by inserting a new state and have the TM visit that state once after each step of computation.

Unsolved so far is the question whether $L$ is RE. When allowing multiple tapes, it is not, as we can reduce $\overline{H\_\varepsilon}$ to $L$. However, for single-tape TMs, our last guess was that it is enumerable by using the fact that a positive input which does not halt has to stay in a single state forever and can only expand the tape into one direction from that point on. We could not come up with an exact solution so far though.

# Answer
> 1 votes
After a deleted (wrong) answer I thought about the following to prove that $L$ is RE for single tape Turing machines.

As you said in the question, the problem is "recognizing" $M \in L$ that doesn't halt.

Note that a non-halting TM $M \in L$ not necessarily must expand the tape; for example:

```
q,[ -> q,[,R
q,a -> q,b,R
q,] -> q,],L
q,b -> q,a,L
causes an endless ping-pong in the same state q
...[aaaaa]....
   ^head

```

Also note that a non-halting TM $M \in L$ can expand the tape without changing its state; for example:

```
q,[ -> q,[,R
q,a -> q,b,R
q,B -> q,b,L
q,b -> q,a,L
causes an endless expanding loop:
...[aaaaaBB...

```

But for both expanding and non-expanding cases, we must have that the Turing machine $M$ must continue forever in the same state otherwise it doesn't belong to $L$ (cardinality constraint).

But the halting problem for one-state one-tape Turing machine, on a blank tape except for a finite number of cells, is decidable. See for example Gabor T. Herman: The uniform halting problem for generalized one-state turing machines. Information and Control; Volume 15, Issue 4, October 1969, Pages 353-367):

-----
**Introduction**: The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given TM will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor.
... we assume that in an ID the tape must be blank except for some finite number of squares ...
In this paper we show the solvability of the UH for one-state TM's ...
-----

So, to enumerate the $M\_i \in L$ start a dovetailed simulation of $M\_1,M\_2,M\_3,....$.

* if $M\_i$ halts at steps $n$ then just count the states visited and outputs $M\_i$ if there is a most visited state;
* otherwise, if $M\_i$ doesn't halt at step $n$, and it is in state $q$; decide if the corresponding one-state TM halts or not. If it doesn't halt then $M$ belongs to $L$;...
* ... otherwise continue the dovetailed simulation (if it halts it will be detected at a later step)

# Answer
> 1 votes
This does not completely qualify, but I'll share it anyway.

We "cheat", by redefining TMs so that, instead of performing "read cell - write cell - move head", they instead perform "read cell - move head - write cell". The variant is still Turing powerful.

Given a TM $M$ using alphabet $\\{0,1,-\\}$ and with states $Q$, we can craft a TM $N(M)$ using alphabet $\\{0,1,-\\}\times Q \times S$ ($S$ defined below) and with states $q\_1,q\_2$ as follows:

* $N$ starts from state $q\_1$, and writes on its first cell $(-,q\_i,s\_0)$ where $q\_i$ is the starting state of $M$
* $N$ never leaves state $q\_1$, while simulating $M$ on the current tape. The current cell $(x,q,s)$ contains the symbol under the head of $M$, the state $q$ of the simulated $M$, and the auxiliary state $s\in S$ of the simulator. Doing this heavily relies on the ability of writing the cell *after* the move, so that the $s$ in the current cell can be updated and written in the adjacent cell.
* If $M$ halts, then $N(M)$ starts alternating $q\_1,q\_2$ infinitely often.

TM with multiple tapes could also perform this trick, I guess.

This is a reduction because:

* $N(M)$ can be computed from $M$
* If $M$ halts on the empty tape, then $N(M)$ has no most visited state ($q\_1,q\_2$ are visited infinitely often).
* If $M$ does not halt on the empty tape, then $N(M)$ has a most visited state ($q\_1$ is visited infinitely often, $q\_2$ is never visited).

---
Tags: computability, turing-machines, undecidability, semi-decidability
---


# Question
Title: Key differences between interactive and time sharing operating systems?
Couldn't find much online on how an interactive system is different from a time-sharing system, or the different traits of both.

My understanding of a time-sharing system is many people at terminals being able to use the system at the same time, and the CPU's aim is to maximise response time not CPU time (unlike a multiprogrammed batch system). The switches between jobs are very frequent, and users get immediate responses, when for example submitting interrupts via keyboard inputs. There is very little CPU idle time, duplication of software etc, but it is less reliable, there might be lower security and integrity, and potentially bad data communication. An example would be a chat messaging client or system.

# Answer
> 1 votes
Time sharing is a system of multi-tasking designed to allow multiple users to use a single machine at the same time.
A time sharing operating system is one that supports multi-tasking and multi-user.
In a time-sharing system the user typically interacts with the operating system through a secondary machine called a `terminal`.

In an interactive operating system there is typically only one user on the system that has full control over the system.

Because of the environment in which time-sharing machines are used (large cooperations and banks) security and separation between users is a prime concern.

Interactive computing originates from the hobby and personal computing revolution. Because there is only a single user security was initially not a concern.

From these starting points the lines have blurred.
First single user systems gained multi-tasking and then multi-user concepts were copied over from time-sharing systems into the interactive OS'es.

Meanwhile the security and performance of time sharing systems have also improved.

# Answer
> -1 votes
Your understanding is quite accurate. The main concern on time sharing systems is that the system appear responsive to interactive users.

I am not aware of any difference between the meaning of two terms in the context of operating systems. 'Interactive' just connotes to a property of an OS.

---
Tags: operating-systems
---