Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped.

  Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(X)$ gate (for $n > 3$), using no work qubits.

I've figured out that this can't be done classically.

I've figured out how to do it with $O(2^n)$ exponentially precise gates (nest the double-control-from-single-controls-and-square-root-of-operation construction inside itself $n-2$ times).

I've tried generalizing the above construction into accumulating a linear combination of controlled operations. For example, if I have 3 controls called A and B and C and make a vector of the various cases [0, A, B, C, AB, BC, AC, ABC] then:

Applying an operation unconditionally adds [1, 1, 1, 1, 1, 1, 1, 1]
Controlling an operation on A adds [0, 1, 0, 0, 1, 1, 0, 1]
Xoring A into C then controlling an operation on C (then undoing the xor) would add [0, 1, 0, 1, 1, 1, 0, 0]
Xoring (A and B) into C via a toffoli gate then controlling an operation on C would add [0, 0, 0, 1, 1, 1, 1, 0]

Then I would try to add (apply a root of X) and subtract (apply inverse square root) the various vectors I can make until the result comes out as [0, 0, 0, 0, 0, 0, 0, N].

But I keep hitting various walls, such as solutions ending up with large multiples (i.e. the gates I'm using become exponentially precise, which I think is a no-no) or just not being able to solve the system due to the interplay between generating elements with AND/XOR then solving with +/* being non-standard or creating exponential numbers of gates.

What are some other approaches to try?

Eventually I ended up solving this for $O(n)$ gates. I wrote up a trilogy of blog posts on it.

Constructing Large Controlled Nots (classically, with an ancilla)
Constructing Large Increments (classically, with an ancilla)
Using Quantum Gates instead of Ancilla Bits

Of course it would suck if you found this twenty years from now and my website was long gone, so the basic steps follow in quickly-described image form.

1. Bootstrap a Borrowable Ancilla Bit

Use a square root and its inverse to reduce the maximum number of controls  by one, creating an uninvolved wire for each operation. Then iteratively move controls off of non-Not operations, and re-arrange the cruft that results into large increment gates and single-qubit phase gates.

2. Use Single Ancilla Bit to Cut Operations in Half

For each large operation, use the uninvolved wire as a borrowed ancilla bit. Use it to transform the huge increment and controlled-not gates into smaller operations that each have approximately half of the wires uninvolved. Repeat twice, if required for the next step to have enough working space.

3. Use Many Ancilla Bits to Finish

For each still-too-large operation, borrow the many uninvolved wires as ancilla bits. Use them to get all the way down to Toffoli-or-smaller gates.

Those three steps will get you all the way from a fully-controlled-not to linearly many Toffoli, CNOT, and single-qubit gates. There's a few implied pieces, like how to merge a control into an increment gate, but they're pretty simple.

(Sorry for the inconsistent style of the diagrams.)


weighted subset exchange question Assume there is a set {1,...,n} of person. For each person i, a set $A_i$ of items are available for exchange. A is the set of all items. The value of item j to person i is $v_{ij}$ and assume all values are positive integers. The question is, does there exist a pair of person who can both make profit by exchanging some of their items in $A_i$.Formally:$\exists$ i and i' and $S_i\subseteq A_i$ and $S_{i'}\subseteq A_{i'}$ such that $\sum_{j\in S_i} v_{i'j}>\sum_{j\in S_{i'}} v_{i'j}$ and $\sum_{j\in S_{i'}} v_{ij}>\sum_{j\in S_{i}} v_{ij}$ I'm not sure whether this question is NP-Complete or there exists a polynomial-time algorithm?

It looks like your question can be written formally

  $\exists i,j\in\{1,..,n\}\:\exists S\subseteq A_i\:\exists T\subseteq A_j :
(\sum_{y\in T}v_{i,y}>\sum_{x\in S}v_{i,x})\land (\sum_{x\in S}v_{j,x}>\sum_{y\in T}v_{j,y})$

If the above is true, then persons $i$ and $j$ benefit from swapping items from $S$ and $T$.

This is hard to decide. Here is an idea for a reduction. We simplify things by assuming there are only two persons $P_1$ and $P_2$, that $P_1$ has just coins and banknotes in $A_1$, that $P_2$ has just $A_2=\{x\}$ and that they would both profit if $P_1$ can buy item $x$ at price $V$ from $P_2$. This is because $v_{1,x}-1=V=v_{2,x}+1$, i.e., $P_1$ thinks that
by paying $V$ for $x$ he wins $1$, while $P_2$ thinks he wins $1$ by selling $x$. They will trade iff $P_1$ can find some coins and notes in his $A_1$ that add up to $V$ exactly (we assumes that $P_2$ only has $A_2=\{x\}$ so he cannot make any change). NB: the coins and notes are items $c\in A$ with $v_{1,c}=v_{2,c}$, their face value is the same for both persons.


What does the posterior probability of a variable mean in the Bayes' rule? I have been studying Artificial Intelligence and I have noticed that the Bayes' rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, 'posterior' mean in this context with regard to the Bayes' rule?

The word posterior stems from the latin word posterior (base form posterus), which means later, after, behind.

In the context of probability and Bayes' theorem it denotes a probability, often written as a symbol $P(A|B)$, where $A$ and $B$ are random variables. This symbol $P(A|B)$ means the probability of $A$ after you have observed $B$. Hence the naming posterior probability, or short posterior.

In this context the probability of observing a certain value of the random variable $B$ is denoted by $P(B)$ and is called prior probability, or just prior for short sometimes. The word prior also stems from a Latin word, pri, which means before. The name hints that you will gather observations of $B$ before you calculate $P(A|B)$.

In this way you use prior information to improve your model of $A$, expressed by the posterior probability $P(A|B)$. By this your probability of $A$ is based on the observed outcome of $B$. Like it has been said by John Maynard Keynes "When the facts change, I change my mind. What do you do, sir?".


RNG: removing bias by counting bits I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias:
two counters are used, which count amounts of 1's and 0's in the stream and when the difference is above the threshold, the next bit out ot the rng is forced to either 0 or 1.
I have concerns about this. This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right? Is this a valid concern? If yes, what are proper ways to deal with bias in RNG?

This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right?

Yes.

Let $T$ be the threshold of the process you describe. In a uniform (i.e. non-biased) distribution, the sequence $\mathtt{0}^{T+1}$ would have the probability $2^{-(T+1)}$, like any other sequence of length $T+1$. But the process you describe will flip the last bit, since the threshold of excess $\mathtt{0}$ bits was exceeded, and thus this sequence has the probability $0$. That's a bias. Note that this bias exists regardless of the distribution of the original generator, i.e. the process always makes the generator somewhat worse.

It's pretty apparent if you take this to an extreme. With $T=1$, the output of the process would be an alternating sequence, either $\mathtt{01010101\ldots}$ or $\mathtt{10101010\ldots}$, which is obviously hardly random at all.

This process looks like it was devised by someone who doesn't understand probability. They have a vague intuition that (9,9,9,9,9,9) doesn't look random and so they go out of their way to avoid too many repetitions. But (9,9,9,9,9,9) is not impossible, so any random generator will generate this sequence of length 6 one day, and again, and again… And it will generate (9,9,9,9,9,9,9) if you wait long enough, and (9,9,9,9,9,9,9,9), etc.

The proportion of $\mathtt{1}$ bits in the first $n$ bits should tend towards a bell curve as $n$ tends to infinity. A biased initial source deforms the curve towards one side. The process moves the summit towards the center, but cuts off the sides.

  Is this a valid concern?

Yes. Bad random generators sink ships (or save them, as the case may be). One of the ways the Allies broke messages encrypted with the German Enigma during WWII was to rely on lack of randomness because the operators' intuition of randomness led them to introducing biases.

  If yes, what are proper ways to deal with bias in RNG?

If you have a random source where each bit has a probability $p$ of being $\mathtt{0}$ and $1-p$ of being $\mathtt{1}$, then there's a rather well-known trick to turn it into a uniform source, which is due to Von Neumann. Read two bits; if they're different then output the first bit and discard the second one; if they're the same then discard both bits and try again. This works well enough with a biased coin because the bias is overwhelmingly due to the design of the coin which doesn't change between tosses. But it assumes that the bits are all independent from one another. This is not a safe assumption for a physical random generator. Even if the underlying physical process is “perfectly” random, imperfections in the construction of the apparatus often have more complex biases, e.g. due to resonance phenomena. The general name for this sort of process is whitening. Von Neumann whitening is typical good enough for physical simulations, but other usage such as cryptography needs more reliable methods.

In computer security, the practical way to construct a random generator is to use a hybrid design.

A random source (ultimately derived from some physical process) provides entropy. It doesn't matter that this source is biased. All that matters is that it has some minimal level of unpredictability, i.e. there is some threshold $p \gt 0$ such that the probability of any given bit being $\mathtt{0}$ is between $p$ and $1-p$.
The entropy is used as a seed to a cryptographically secure pseudorandom number generator (CSPRNG). A CSPRNG is deterministic, but it is infeasible for an adversary to guess any part of its output unless they know the seed. (“Infeasible” means that the adversary trying to guess an output bit gains a negligible advantage from any knowledge that doesn't imply knowledge of the key.)

The resulting distribution is not uniform (since the CSPRNG is deterministic, it can only output a finite subset of all possible sequences, limited by its state size), but it is indistinguishable from a uniform distribution by an adversary with finite processing power.


Lower bound of a summation with an exponential For the following (related to a binary tree complexity question):

$$f(n) = \sum_{h=0}^{\lg{}n} h2^h$$

Is there any way to express this only in terms of $n$? Or approximate it?

Put in another way, I figure at worst for an upper bound, we could guess at it in the following way:

$f(n) = 0 + (1 \cdot 2) + (2 \cdot 2^2) + (3 \cdot 2^3) + ... + (\lg{}n \cdot 2^{\lg{}n})$

This means since we go from $0$ to $\lg{}n$, and the largest above when reduced is $n\lg{}n$, I could write $\mathcal{O}(n\lg^2{}n)$.

Supposedly $f(n)$ reduces to $\Theta(n\lg{}n)$ or better (by better I mean closer to $\Theta(1)$) and I'm struggling to show that... and I don't know if it's possible even. I can't prove it though so I can't claim it's not, reducing the summation if possible would hopefully lead to a quick answer.


What is the time complexity of memory allocation assumed to be? It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more room in the buffer, so the dynamic array allocates a new buffer and copies over $n$ items.

My question is, what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

This depends on what you mean by "allocate a buffer with size $O(n)$" and how much time that takes. Unfortunately, there isn't a standard answer for that. It boils down to how you model "allocating a buffer", and your assumption about the time complexity of that operation.

You could assume that allocating such a buffer could be done in $O(1)$, or you could assume that this takes $\Theta(n)$ time. It depends on the system you're trying to model:

The operating system will generally overwrite memory that has previously been used by another process with all zeros to avoid leaking information from one process to another. Thus, allocating a size-$n$ buffer will take at least $\Omega(n)$ time due to this initialization procedure.
If you are working in a very low-level setting (for instance assembly programming), "allocating a buffer" might you mean grabbing a pointer to the top of the heap and then incrementing that pointer by the number of elements you want to allocate. You could reasonably model this as an $O(1)$ operation.
If you are, for instance, working in C and initialize a buffer by calling malloc, then there is generally no guarantee about the complexity of this operation. It might take $O(1)$ time, $O(n)$, $O(n^2)$, exponential time or even fail to allocate the buffer at all (out of memory). On the other hand, specialized implementations of malloc (such as TLSF) might come with guarantees.

Thus, depending on the implementation, the operation "allocating a buffer" should be modeled as having a different time complexity. If you are working in a purely theoretical setting (without any underlying implementation), then you have to make an assumption. Assuming it takes $O(n)$ time is more reasonable than assuming it would take $O(1)$ time (since more real-world systems will be able to meet the former assumption than the latter), however, any assumption, if clearly stated is valid. It is even possible to reason about totally unreasonable assumptions (for instance, you could assume that you could copy over $n$ items in $O(1)$ time) for the sake of argument.


Metrics for measuring the tradeoff between efficiency and effectiveness in Information Retrieval I'm comparing several methods for building inverted indexes (n-grams, hash boundaries, etc.).
Given a set of queries, these indexes perform differently.
On one hand, I get performances metrics (efficiency) such as the time needed to execute the query.
On the other hand, I get metrics such as precision and recall (effectiveness) by checking the relevance of the results.
Depending on the method I use, there is a tradeoff between efficiency and effectiveness.
For example, some methods loose a little in term of effectiveness for a huge gain in term of efficiency.

Are there some metrics which puts the effectiveness (precision, recall, etc.) in perspective with the efficiency (throughput, memory, etc.)?

I assume that your question is being put in the context of boolean retrieval. It seems that there is not a single metric that takes into account both efficiency and effectiveness and provide a theoretical framework for IR evaluation.

This is mainly because these two issues can sometimes be quite independent between each other. We use certain methods to build inverted indexes in order to mitigate memory issues that arise when we try to index large collections of documents. Some of these methods (such as hash tables) provide fast access to the dictionary (in $O(1)$ time) but fail to accomodate proximity queries (the sort of "find documents that have the word "Beatles" near the word "Animals"). Moreover there are implications arising if we are to index a collection that might change in size and content. Usage of B-trees can overcome these issues as these structures permit an ordering of their contents.

On the other hand some other methods (such as k-gram auxiliary indexes) charge us with additional processing time but offer a more broad range of queries that can be computed (complex wildcard queries such "co*ter*ed"). In general this results in a more powerful IR system in the sense of a wider capability in answering queries.

There is of course the "user happines" measure that takes into account the extent to which the user's information need is satisfied by the system but this is not always the case as users tend to take into consideration several other factors like the user interface which is independent of the system's performance.

In my humble opinion the issue of the relation between effectiveness and efficiency is something that can be examined more thoroughly in the "real" context of an implemented IR system. It is in this setting that more concrete conclusions can be extracted about the effect that different indexing methods have on the performance of the IR system.

An excellent resource in these topics is the following book by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze
http://nlp.stanford.edu/IR-book/information-retrieval-book.html


Regular expressions and 'capturing parentheses' with 'backreferences' We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences':

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_Expressions#special-capturing-parentheses

(x)
Matches 'x' and remembers the match, as the following example shows. The parentheses are called capturing parentheses.
The '(foo)' and '(bar)' in the pattern /(foo) (bar) \1 \2/ match and remember the first two words in the string "foo bar foo bar". The \1 and \2 in the pattern match the string's last two words.

I want to know if this pattern /(foo) (bar) \1 \2/ is in fact a RE according the definition of RE that we have in theoretical formal language or it is something more powerful. And if it is so I would like to know if this kind of feature is implemented also with FA or in another way (in particualr how it is implemented).

These extended notions of regular expressions capture more than just the regular languages.  For example, ([ab]*)\1 matches the language $\{ww\mid w\in\{a,b\}^*\}$, which isn't regular and isn't even context-free (Example 2.38 of Sipser, Introduction to the Theory of Computation, 3rd edition).

"Regular" expressions that don't match regular langauges can't be translated to finite automata, since finite automata match only the regular languages. A side-effect of this is that many libraries don't even try to compile to automata, which can lead to extremely slow matching, even when a "regular" expression is a true regular expression. Russ Cox wrote an excellent article about this, which goes into a lot of the history, too.


Does the language defined in the details in NP-C or P? It's known that:
$$
\textrm{CLIQUE} = \{(G,k): \mbox{G has a clique of size } k\}
$$
is $\textrm{NP-C}$, but what if every vertex has 2 neighbours (as defined in $\textrm{2d-CLIQUE}$)?
$$
\textrm{2d-CLIQUE} = \{(G,k): \mbox{every vertex in G has exactly $2$ neighbours and $G$ has a clique of size } k\}.
$$

Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete.

Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:

$k=0$, or
$k \in \{1,2\}$ and $G$ is not empty, or
$k = 3$ and $G$ has a triangle, which can be checked in $O(n)$ time.


Relation Between Priority Queue, Heap, Tree There are $2$ "basic"/"fundamental" data structures due to the way memory works:

array
linked list

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

array
tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $\subset$ tree $\subset$ priority queue?

Arrays and linked lists are indeed simple data structures, but they are not more "fundamental" than other data structures. Everything in software is built out of contiguous memory to which the CPU has random access by address. All data structures are just abstractions built on top of that foundation.

A tree data structure is not composed of arrays and linked lists in any meaningful sense. You can implement a tree data structure using contiguous memory and pointers, just as you can implement a linked list using contiguous memory and pointers. If anything, a linked list is a special case of a tree in which each node has at most one child.

Saying that a tree is built from linked lists is like saying that a dinosaur is built from birds.

It is confusing a special case as a composition. A dinosaur is not composed of birds; a bird is a special case of dinosaur. A tree is not composed of linked lists; a linked list is a special case of tree.
However, the special case is itself only in a technical sense. If someone casually mentions the word dinosaur, they probably aren't thinking of birds. If someone casually mentions the word tree, they probably aren't thinking of linked lists.

You are also confusing the definition of abstract data type. An abstract data type is one where the operations are specified but the implementation is unspecified. A priority queue is an abstract data type, for which many concrete implementations are possible. Possible implementations of a priority queue include ones based on heaps stored in tree data structures; heaps stored in implicit trees in resizable array data structures; binary search trees; and many others. A linked list is an example of a concrete data structure which can be used to implement (among other things) a list abstract data type with operations for insertion, removal, indexing, etc.


Average number of comparisons for a successful search of a prime number in a binary search tree A binary search tree is constructed by inserting the following value sequentially:
$$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$
Let $p_v$ be the probability to search for the value $v$ in the binary search tree (for $1\leq v\leq10)$.
$p_v = \frac{1}{25}$ if $v$ is an even number and $p_v = \frac{1}{10}$ if $v$ is an odd number. Determine the average number of comparisons for a successful search of a prime number in a binary search tree.

I know that I have to calculate the expected value, but I don't know where to start. Any help to solve this problem is greatly appreciated.
This is what I have tried:

To search for number 3, it takes 1 comparison.
To search for number 7, it takes 5 comparisons.
To search for number 2, it takes 3 comparisons.
To search for number 5, it takes 5 comparisons.

So the average number of comparison to search for a prime number is:
$$\frac{1+5+3+5}{33} = \frac{14}{33}$$

This is a very simple question, I will explain steps-by-steps:
First, you need to count total elements and total comparisons in your tree
Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree.
Third, if the problem gives you a probability to search for an element, you need to multiply it by each element.
Now back to your question:

Total elements = $10$, total comparisons = $1 \cdot 1 + 2 \cdot 2 + 3\cdot 3 + 2 \cdot 4 + 2\cdot 5 = 33$ (this is calculated by taking the total nodes at each level and multiply it by the level, you need to draw the tree to understand).
The tree has $5$ odd elements and $5$ even elements, you need to do now is to take the probability and multiply it by each element, which in your case is $\frac{1}{10} \cdot 5 + \frac{1}{25} \cdot 5 = \frac{1}{2} + \frac{1}{5} = \frac{7}{10}$.
Now your expected value is: $E(x) = \frac{33}{\frac{7}{10} \cdot 10} = \frac{33}{7}$, which is also the solution for your problem.


Multi-variate complexity semplification I developed an algorithm with the following multi-variate complexity:
$$O((k^n+kn)l^{kn}),$$
where $n,k,l$ are variables.

I have very little knowledge of complexity theory, and I'm not sure whether this expression can be simplified. Since $k^n$ dominates $kn$ it seems reasonable to $O(k^nl^{kn})$. Is this correct?
Assuming $l\ge 2$, can the expression be simplified even further?

Yes. you're right (for $k,n \geq 1$). Also you can right the final answer as $O((kl^k)^n)$.


Graph Coloring Problem Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?

It's unclear exactly what level you're asking the question at.

In principle, you could set up a graph where the vertices are prisoners, there's an edge between any two prisoners who need to be kept separate, and each prison corresponds to a colour. In practice, there are probably too many prisoners in any reasonably sized country for this to be a computationally tractable approach (though the conflict graph would probably be rather sparse), there are more constraints on the system that would be hard to model in this graph-colouring approach, and two prisoners getting into a fight could cause a re-colouring that might cause a large proportion of the prison population to be moved, which is neither feasible nor desirable.


determine if a machine prints a certain string in less time than it takes to run the machine itself? Does there exist a procedure that determines if a polytime machine prints a certain string, and does so in less time than the machine itself takes to run?

Define a machine $a$ that analyzes another machine $b$, input $i$, and string $r$:

$a(b,i,r) = b(i) \text{ prints } r$           $[T_b = O(n^k), k >= 2]$

Is there an $a$ with run-time $T_a \in o(T_b)$ on all $b,i,r$?

Your question is somewhat unclear, but here is something you can prove using the time hierarchy theorem. We will use the convention that a Turing machine computing some function prints the result at the end, and prints nothing except that. Suppose $T$ is a machine that accepts the code of a machine $P$ running in time $O(n^\alpha)$ and an input $x$, and returns the output of $P(x)$ in time $O(n^\beta)$ for $1 \leq \beta < \alpha$. Using $T$, we can evaluate the function computed by $P$ in time $O(n^\beta)$, so $\mathrm{Time}(n^\alpha) \subseteq \mathrm{Time}(n^\beta)$, which contradicts the time hierarchy theorem.


Sorting an array of boolean values im looking for some guidance on how to get started with sorting an array of booleans so that the falses would be in front of the trues.

so if given this:
a = {true, true, false, true, false}

it would return:
a = {false, false, true, true, true}

here is the exact question:
     Suppose you have an array of booleans of size n. Give an algorithm that sorts the array so that all false elements come before all true elements.

Thanks for any help you can give me!

With only 2 possible values, you want to use an algorithm such as Counting Sort.

Since you only have 2 possible values, true and false, it's easy to just count how many true/false values you have. But to be more efficient, you can just count how many trues you have (or falses) instead. Because size - numTrue = numFalse.


Why do we should not to use simple count instead of cumulative count in Counting Sort? I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn't use cumulative sum. I want to ask why it is bad to not to use cumulative sum in counting sort algorithm? (BTW it has O(n) runtime complexity)
def my_counting_sort(lst):
    counts = (max(lst)+1) * [0] # n
    output = []
    for item in lst: # n
        counts[item] += 1
    for index in range(len(counts)): # n
        item = counts[index]
        while item > 0:
            output.append(index)
            item -= 1
    return output

It is related to the stability of output this algorithm:

Stable sort: For same number appearing more than once in the input array, ties are broken by the rule that whichever number appears first in the input array appears first in the output array.

•The property of stability is important only when satellite data are carried around with the element being sorted.

•Counting sort is often used as a subroutine in radix sort. Counting sort’s stability is crucial to radix sort’s correctness.

Having a cumulative sum helps it in making it a stable sort.


Searching for the biggest area inside 2D matrix I have an algorithmic problem where I need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions:

Each pixel needs to be connected either diagonally or adjacently.
The area is considered coherent only if it is surrounded by the other type of pixel( x-es on the edge are not)

A pixel is considered an object with 3 fields:

int x,y;          //Cordinates of a pixel
String type;      //Type of a pixel
boolean visited;  //Was the pixel visited

The input file is something like this:

oooooooooo
oXXooXXXoo
oooXoooooo
xooooXXXXo
xxooXooooo
xxxooooooo

The output in this example should be an int of value 5.

Is someone able to tell me if the BFS algorithm is a viable solution or should I try a different approach?

A BFS combined with floodfill should be enough.

Basically, you do the following:

Iterate until you find the first X
Run a BFS on it and change all pixels to visisted = True. Also keep track if you happen to reach the boundary or fulfill any other criterion s.t. it is disqualified
If it is not disqualified, save its size as the current max-size
Iterate further until you find the next unvisited pixel and redo steps 2-4. Keep track of the largest size found.
If you need the original array, change back the visisted state of each pixel in a final iteration.

Overall runtime: Linear, because you change each element at most twice (once to visisted and once back), and also consider only a constant number of neighbors for each element (8).


If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index? If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are from $\color{Blue}1$ to $\color{Blue}n$)

Let $D(i)$ denote the number of descendants of the $i$th node.  In a min-heap, all $D(i)$ nodes below node $i$ must have a larger value than node $i$.  Hence, the $n-D(i)$ largest values $n-D(i)+1,\ldots,n$ cannot be put in node $i$.  It turns out that $n-D(i)$ can be put in node $i$, and so the maximum possible value for node $i$ is $n-D(i)$.  To see how this can be achieved, fill in the descendants of node $i$ by $n-D(i)+1,\ldots,n$, and fill in the remaining nodes in any way so that the min-heap property is satisfied.  The integers available for the parents of node $i$ are all less than $n-D(i)$ and so the min-heap property can be satisfied.  The sibling  of node $i$, the siblings of the ancestors of node $i$, and the descendants of these siblings, all necessarily contain values smaller than node $i$ because the values larger than $n-D(i)$ have been used up, and this is fine because we want node $i$ to have the largest possible value. There is no violation of the min-heap property, which only concerns relations between a node and its parent (and therefore all its ancestors) or its children.

To obtain the smallest possible value for node $i$, let $A(i)$ denote the number of ancestors of node $i$.  This value is the number of nodes in the unique path from the root to node $i$ (including the root node but not including node $i$).  These $A(i)$ nodes must have values less than node $i$, and so the smallest possible value for node is at least $A(i)+1$.  Is this bound achievable?  Yes, put values $1,2,\ldots,A(i)+1$ as the values on the path from the root node to node $i$ (where node $i$ takes value $A(i)+1$).  Observe that the remaining nodes can be filled in with the remaining values in such a way that the min-heap property is satisfied.  The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of all these siblings, as well as the descendants of node $i$, will all have a larger value than $A(i)+1$, and this doesn't violate the min-heap property.


Solving a problem related to convolution I have this confusion related to solving this problem

  You’ve been working with some physicists who need to study, as part of their experimental design, the interactions among large numbers of very small charged particles. Basically, their setup works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points $ \{1, 2, 3, \cdots , n\}$ on the real line; and at each of these points $j$, they have a particle with charge $q_j$. (Each charge can be either positive or negative.)

  They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle $j$, by Coulomb’s Law, is equal to

  $F_j = \sum_{i<j}\frac{Cq_iq_j}{(j-i)^2} - \sum_{i>j}\frac{Cq_iq_j}{(j-i)^2}$

  They’ve written the following simple program to compute $F_j$ for all $j$:

For j = 1, 2,...,n
   Initialize Fj to 0
   For i = 1, 2, ..., n
￼     If i < j then
       Add Cqiqj/(j-i)^2 to Fj
     Elseif i > j then
       ￼Add −Cqiqj/(j−i)^2 to Fj
     Endif
   Endfor
   Output Fj
Endfor

  It’s not hard to analyze the running time of this program: each invocation of the inner loop, over i, takes $O(n)$ time, and this inner loop is invoked $O(n)$ times total, so the overall running time is $O(n^2)$.

  The trouble is, for the large values of $n$ they’re working with, the program takes several minutes to run. On the other hand, their experimental setup is optimized so that they can throw down $n$ particles, perform the measurements, and be ready to handle n more particles within a few seconds. So they’d really like it if there were a way to compute all the forces $F_j$ much more quickly, so as to keep up with the rate of the experiment.

  Help them out by designing an algorithm that computes all the forces $F_j$ in $O(n \log n)$ time.

I am sure that this problem is solved by convolution which takes time $O(n \log n)$. However, I am not being able to proceed and see how it's converted to a problem related to convolution. Any suggestions?

Hint: Consider the two sequences $q_1,\ldots,q_n$ and $\ldots,-1/9,-1/4,-1,0,1,1/4,1/9,\ldots$.


Disjoint paths of length at most L and the number of nodes to remove to vanish this property - Inequality Given an graph $G$ and two, randomly chosen, non-adjacent nodes, let's call them $s$ and $t$,
we make the following two notations:

$P_L(s,t;G)$ = the maximum number of internally disjoint paths (paths that don't have any node in common, except s and t) with a length at most $L$ (L ranges from 1 to |G|).

$K_L(s,t;G)$ = the minimum size of a set of nodes (s and t not included in the sets) with this property - if we remove  the set of nodes, the result is that there are no more paths of length at most $L$, from $s$ to $t$.

I have to prove the inequality
$$ P_L(s,t;G) \le K_L(s,t;G) $$
and specify the values of $L$ (L ranging from 2 to |G|) for which the relation satisfies the equality too, for any chosen graph G and nodes s,t.

The first idea that comes to my mind is to start a discussion based on the values of $L$ and try to prove the relation by induction. Any ideas how?

Hint: Suppose that $P_1,\ldots,P_t$ are internally disjoint $(s,t)$-paths of length at most $L$. Show that you have to remove at least one vertex from each path to make the distance from $s$ to $t$ larger than $L$.

When $L = |G|$, the classical Menger's theorem states that equality holds.


How many edges can a unipathic graph have? A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.

Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of length 2, for a total of $2(n-1)$.

What is the maximum number of edges in a unipathic graph with $n$ vertices? An asymptotic bound would do (e.g. $O(n)$ or $\Theta(n^2)$).

Inspired by Find shortest paths in a weighed unipathic graph; in my proof, I initially wanted to claim that the number of edges was $O(n)$ but then realized that bounding the number of cycles was sufficient.

A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges.

   Consider a complete bipartite graph, with oriented edges $\forall (i,j) \in [1,m]^2, a_i \rightarrow b_j$. This graph is unipathic and has no cycle: all its paths have length $1$. It has $2m$ vertices and $m^2$ edges.

 (Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)


How do I manage flow control with no ELSE statement? (on Turing machine) I have been given the problem of writing a turing machine with the commands:

if, while, whileNot, read X, write X, goLeft, goRight, HALT

The problem was simply "calculate a two's complement number, from number with \$ on the left and # on the right, ex: $10110100#"

I started by writing this pseudocode to flip the bits:

whileNot read #
    if read 1
        write 0
    if read 0
        write 1
    goRight

But then I realized once 'write 0' executes, 'if read 0' will immediately be true and undo my work. I need a statement that is effectively 'else if read 0', is there any turing trickery that I can employ to do something like this?

The following code should work:

whileNot read #
    while read 1
        write 0
        goRight
    while read 0
        write 1
        goRight

As for implementing IF-THEN-ELSE in general, it depends on the exact semantics of your programming language, which you haven't specified.


Loop invariant: decreasing a variable and swapping it As an example exercise, we were asked to find the loop invariant for this bit of code.

def mystery(a,b):
    # Precondition: a >= 0 and b >= 0
    while a >= 0 and b >= 0:
        if a < b:
            a, b = b, a
        else:
            a = a - 1
    return a

From what I can see, it first ensures that a >= b.
After that, each loop iteration decreases the value of a by 1.

This will continue until a and b are 0.

Then one final iteration terminates the loop with a == -1.

However from what I can tell, if the loop invariant is something like a >= b, it fails upon termination as a = -1 and b = 0.

Could anyone tell me the actual loop invariant of this function as I'm a bit confused.

There isn't a single loop invariant: any property that remains true during the execution of the loop is a loop invariant. For example, “I am not the Pope” is an invariant of this loop, but it is not a useful one. A useful loop invariant is one that helps in proving some property of the program.

Here, presumably, the ultimate point of the exercise is to determine the return value of the function (as a function of the arguments a and b). The only way this function can return is on normal exit of the while loop, returning a in a state of the program where the condition a >= 0 and b >= 0 is false.

The property a >= b isn't likely to be relevant because it's neither true at the start of the function nor when the function returns.

Given the objective to figure out the value of a when the loop exits, it is useful to look at what happens in the last iteration of the loop. We know that a >= 0 and b >= 0 is true on entry to the function, so there will be at least one loop iteration. Let $a'$ and $b'$ be the values of a and b at the start of the last iteration, and $a''$ and $b''$ the values at the end. We know from the loop condition that $a' \ge 0$, $b' \ge 0$, and $a'' \lt 0 \vee b'' \lt 0$. This can only happen when the else branch is taken. Therefore $a'' = a' - 1$ and $b'' = b'$. Plugging these equalities into the inequalities we had, we get that $b'' \ge 0$ so $a'' \lt 0$ and also $a'' \ge -1$.

It appears that b >= 0 and a >= -1 are two invariants of the loop — they're true on entry and they're true on return. Furthermore, if the initial values of a and b are integers, the property “a and b are integers” are also loop invariants. If a and b are integers, then the only possible value for $a''$ given the inequalities above is $-1$, so this function can only return the value $-1$.

Follow-up exercices:

If a and b aren't constrained to be integers, what does the function return? You'll need to find another invariant to determine the value of $a''$.
If a and b are nonnegative integers, I've proved that this function can only return the value -1. I haven't proved that this function is equivalent to return -1, however: it might also loop infinitely. Prove that (given the precondition that the arguments are non-negative) the function always terminates.


Multiple Knapsack Problem with Set of Admissible Balls We have $m$ bins and $n$ balls.

Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3.
Each ball $j=1,2,\ldots,n$ can be put into bin $i=1,2,\ldots,m$.
For each bin $i=1,2,\ldots,m$, there is a collection of sets $S_i=\{X_1,X_2,\ldots,X_{k_i}\}$ for given $k_i$ ($k_i\geq0$ and $k_i\leq\binom{n}{2}$). Each $X_j\in S_i$ is a 2-cardinality set and it represents the set of two balls that can be put into bin $i$. We can only choose at most one set from $S_i$.

For example, for $m=2$ and $n=3$. Say we have $k_1=0$ and $k_2=2$ and $S_1=\emptyset$. $S_2=\{\{1,2\},\{2,3\}\}$. This means that:

Ball $1$, $2$ or $3$ can be each put into bin $1$ or bin $2$. This is always true (for all instances of the problem).
In bin $1$, we cannot put any set of two balls.
In bin $2$, we can put balls $1$ and $2$ or balls $2$ and $3$.

We want to assign the maximum number of balls into the bins. Is this easy or hard?

Since, we have the assumption that $|X_j|=2$, I was thinking that maybe we can solve it in polynomial-time. I am trying to prove that it is easy by reducing it to maximum flow.

A problem similar to this one but more general was posted here Assigning Balls to Bins with Constraints on Which Ball to Go to Which Bin?.

This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\{a, b, c\}$ into a valid pair $\{a, b\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-k$ bins with 1 ball each), where $k$ is the largest size of any 3DM for the original input.


What is the definition of Infinitely Often class in complexity I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?

$L\in DTIME\left(2^{n^c}/n^c\right)$ if there exists a machine $M$ running in time $O\left(2^{n^c}/n^c\right)$ which correctly decides membership to $L$ for an infinite number of input lengths, i.e. for every $k\in\mathbb{N}$ there exists $n\ge k$ such that $\forall x\in\{0,1\}^n : M(x)=\mathbb{1}_{x\in L}$. You can think of it as having a non trivial special case where we can decide membership to $L$ (where by non trivial I mean an infinite set of inputs, not just very short ones).


SAT to knapsack vs. ETH Theorem states that every problem in $\mathsf{NP}$ can be reduced to another $\mathsf{NP}$-complete problem in polynomial time. Also you can only make a problem polynomially longer using polynomial time.

Thus SAT of length $n$ can be reduced to knapsack with length $n^k$ for some fixed $k\in\mathbb{R}^+$. We don't need to show that reduction, we only need to know that it exists.

Knapsack has quasipolynomial algorithm, in other words running time is $O(\alpha^{\log^p q})$ where $\{p,\alpha\}\in\mathbb{R}^+$ are some fixed numbers and $q$ is length of knapsack problem.

Now assuming we have converted SAT to knapsack we get runtime $O(\alpha^{\log^p n^k})=O(\alpha^{k^p\log^p n})=O(\beta^{\log^p n})$ where $\beta\in\mathbb{R}^+$ is some fixed number. So, the runtime is quasipolynomial.

Why doesn't this simply negate ETH?

Knapsack does not have any known quasipolynomial time algorithm (one which runs in
$n^{poly(\log n)}$ time, with $n$ being the inputs length).

What it does have is a pseudo-polynomial time algorithm, i.e. an algorithm which requires polynomial time in the numeric value of the input, but exponential in the length of its description. The dynamic programming algorithm for knapsack runs in time $O(nW)$, however the input $W$ when given in binary representation requires $\log W$ bits, so the algorithm is actually exponential (and not quasipolynomial).


2-D peak finding complexity (MIT OCW 6.006) In a recitation video for MIT OCW 6.006 at 43:30,
Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to it's adjacent neighbors, was described as:
Note: If there is confusion in describing columns via $n$, I apologize, but this is how the recitation video describes it and I tried to be consistent with the video.  It confused me very much.

Pick the middle column $n/2$ // Has complexity $\Theta(1)$

Find the max value of column $n/2$ //Has complexity  $\Theta(m)$ because there are $m$ rows in a column

Check horiz. row neighbors of max value, if it is greater then a peak has been found, otherwise recurse with $T(n/2, m)$ //Has complexity $T(n/2,m)$

Then to evaluate the recursion, the recitation instructor says

$T(1,m) =  \Theta(m)$ because it finds the max value
$$ T(n,m) =  \Theta(1) +  \Theta(m) + T(n/2, m) \tag{E1}$$

I understand the next part, at 52:09 in the video, where he says to treat $m$ like a constant, since the number of rows never changes.  But I don't understand how that leads to the following product:
$$ T(n,m) = \Theta(m) \cdot \Theta(\log n) \tag{E2}$$
I think that, since $m$ is treated like a constant, it is thus treated like $\Theta(1)$ and eliminated in $(E1)$ above.  But I'm having a hard time making the jump to $(E2)$.  Is this because we are now considering the case of $T(n/2)$ with a constant $m$?
I think can "see" the overall idea is that a $\Theta(\log n)$ operation is performed, at worst, for m number of rows.  What I'm trying to figure out is how to describe the jump from $(E1)$ to $(E2)$ to someone else, i.e. gain real understanding.

the analysis you outline appears to be incorrect. the correct complexity is $O(m)$ where $m$ is the larger dimension of the matrix (either rows or columns). see this other correct analysis for more/better detail. part of the mistake is not defining the recurrence relation $T(n,m)$ in terms of $T(n,m)$ only (which is handled correctly in the paper). the paper shows/uses an infinite series:

$
\begin{eqnarray*}
T(n) & = & T \left({n \over 2}\right) + cn \\
 T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\
&= & O(n)
\end{eqnarray*}
$


How to solve cubing, batching, and routing problem together? I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing.

The input data has some orders with items. Items have locations, 3 dimensions. Each tote has the same size. One trolley can fit 4 totes.

The cubing part could just use approximate volume.

The goal is to create batches with planned picking route.

The size of the problem: about 50-80 items per order. 5-10 orders during
the picking window.

The problem is intertwined if we want to minimize the distance. Should the cubing part solved separately without considering the batching and routing? If so, is this a VRP?

I assumed the cubing is a bin backing/multiple knapsack problem, and is first fit algorithm good enough? Which heuristic performs better?

First, you need to understand how you are going to pick. That means, in one tote, do you want only one order or multiple items of different orders can end up into one tote. If it is latter, is there any sorting or consolidation area to separate out?
Is it like one order must go into one carton?
After we have those answers, I would always prefer first cubing and then, according to our strategy, pick them, and for the optimal path, obviously use VRP.
Prefer using https://or.stackexchange.com/


Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\dots, i_k}$ has distribution $U_k$ (uniform distribution on $\{0,1\}^k$).
Problem: Consider probabilistic algorithm $A$ that has oracle access to the input of length $n$. It means that algorithm $A$ can adaptively request $k$ bits of input (in more detail, $A$ can request one bit, then based on the oracle answer request another bit and repeat it not more than $k$ times).
Prove that if $D$ is $k$-independent distribution than $Pr_{x \sim D} [A(x) = 1] = Pr_{x \sim U_n}[A(x) = 1] $
First of all, I don't understand how adaptivity can potentially help the algorithm to distinguish the uniform distribution from a $k$-independent one. The second question is as in the problem.

$$
\Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]
$$
Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.
$$
\Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot
\Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1].
$$
Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.


Dividing EX stage of a pipeline into EX1 and EX2 stages There is this problem about pipelining that does not have an answer, and I'm wondering what the answer could be:

 In the five stage pipeline with forwarding support to EX, the first operand of ALU comes from 3-to-1 input multiplexer. As the memory latency increases, MEM stage now takes 2 cycles (from 1
cycle) To adjust the pipeline for the latency increase, the MEM stage becomes MEM1 and MEM2.

How should the input mux for the ALU be changed, if forwarding to EX needs to be fully supported?
Even with the full forwarding to EX, show an example where the number of stall cycles increase in the new pipeline compared to the old one.

I don't get what it means to divide MEM stage with MEM1 and MEM2. Why would any additional input be necessary?

This is multi-cycle processor, where each stage takes a single clock cycle. The text suggest that the new MEM stage should take 2 clock cycles. Then, it can be seen as splitting this 2-cycle stage into 2 separate 1-cycle stages which we can call MEM1 and MEM2 respectively.
There is no new input. You only need to make sure that the "right" input travels along the pipeline and reaches the right stage at every time.


Prove Recursive formula (Dynamic programming) N(C,i) I've been asked to prove the correctness of the following recursive formula. The formula is trying to define, how many ways you can spend your money C on the i amount of beers. I did the following recursive formula where you either bought a beer and losing $P-i$ money, or passed the beer and went for the next in the array $i-1$. You cannot buy the same type of beer twice.

$$N(C,i)=\begin{cases}
    0       & \quad \text{if } C<0\;||\; i<0 \\
    1       & \quad \text{if }  C=0\\
    N(C,i-1)+N(C-P_i,i-1)  & \quad otherwise
  \end{cases}
$$

I'm not certain how to prove the correctness of the algorithm. Especially because the assignment is about dynamic programming, and I can't find any repeated subproblems. The amount of money you will have will differ unless some of the different beers cost the same. I asked a fellow student who said the problem will always give overlapping subproblems.

The problem has also been talked about here (Making a recursive formula for finding amount of ways to spend money on beer), but I think my recursive formula is correct.

Sorry, if the question is unclear, or if I've done something wrong. It's the first time on stackexchange, and I think, this is the place to ask the question and not the mathmatics site.

I figured it out.

Overlapping-subproblems:

$P_i == P_{i_1}$: If two beers has the same price it will give overlapping subproblems. The assignment thinks this is okay.
$P_i == P_{i-1}+P_{i-2}$: If a collection of beer has the same price as another collection of beers they will end up with the same parameter $C$. Because every left call doesn't change the value of $C$ it will give overlapping subproblems.

Proof of Correctness

I thought I had to prove the algorithm through induction with a mathematical equation. This wasn't the case. I had to prove that simple base-cases would give the correct value, and that the recursive calls would get closer to the 1st and 2nd statement and prove that the algorithm would eventually terminate.

Case 1: If $C = 0$, then $N(C,i)=1$
Case 2: If $i = 0$ and $C!=0$, then $N(C,i)=0$ (Had to edit my formula. The assignment specified that you had to use all your money)
and more...


Is there any official terminology about something like double quotes "" grammar? In many programming language string is a token.
For example:
 token               ::= '"' string
                       | digit nat

 string              ::= char string
                       | '"'

 nat                 ::= digit nat
                       | ϵ

This is a LL(1) grammar for some programming language's toke grammar.
When parsing a string, there is no need to check follow set, because there is a " at the end of each string.
Comparing with nat, string is more easy to parse.
My question is
Is there any official terminology about this kind of grammar?
Thanks.

Editing:
There was some mistake in the original grammar, thanks @rici for pointing out my mistakes.

FOLLLOW sets are not used in the parsing of either string or nat. In both cases, the parser merely needs to determine if the input is in a set of valid symbols. In the case of nat, the valid symbols are digits; in the case of string, they are characters other than ". (In real languages, the parser would also be checking for \). But in both cases, a check is necessary, and there's no good criterion for saying one test is "simpler" than another. (In practice, both checks are likely to be a simple table lookup. So they're O(1).)
FOLLOW sets are only needed when the grammar contains ε productions. Even then, the parser's actions are not complicated. What is more complicated is building the parser, something which only happens once. It's not really that big of a deal, but it's sufficiently notable that "ε-free grammars" are a thing. I don't think there's any common vocabulary to describe the difference between explicitly and implicitly-terminated repetition, and any way the distinction will be very hard to define strictly. Your string would be parsed by a parser which used a different rule to collect the trailing ", and it's quite possible that the two parsers end up with the same implementation.


The crux of Savitch's Theorem In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going to quote the text verbatim, because quite frankly I don't fully understand it (which is why I was unable to really ask my question in enough detail):

  We need to simulate an $f(n)$ space NTM deterministically. A naive
  approach is to proceed by trying all the branches of the NTM’s
  computation, one by one. The simulation needs to keep track of which
  branch it is currently trying so that it is able to go on to the next
  one. But a branch that uses $f(n)$ space may run for $2^{O(f(n))}$
  steps and each step may be a nondeterministic choice. Exploring the
  branches sequentially would require recording all the choices used on
  a particular branch in order to be able to find the next branch.
  Therefore, this approach may use $2^{O(f(n))}$ space, exceeding our
  goal of $O(f^2(n))$ space. (Sipser, "Introduction to the Theory of Computation" 334)

He goes on to describe Savitch's use of a subroutine called $CANYIELD$, a TM that decides whether some configuration $c_2$ is reachable from some other configuration $c_1$ in $t$ steps. It is recursively defined, so that $CANYIELD(c_1, c_n, t)$ results in two recursive calls $CANYIELD(c_1, c_m, t/2)$ and $CANYIELD(c_m, c_n, t/2)$, and so on until the "distance" between configurations is $0$ or $1$, or it is deemed unreachable. I think this can also be described as $STCON$ on a configuration graph of the TM in question.

So, there are two questions I have.

I understand how the size of each level and the depth of $CANYIELD$ results in no more than $O(f^2(n))$ use of space, but I don't understand how the intermediate configuration $c_m$ is found. Is this just not important given that all we care about is space? How do we know that the space used to obtain $c_m$ is negligible?
I don't understand why we need $2^{O(f(n))}$ space in the naive approach. Why can't we "forget" about branches we've executed, so that we are still using at most the space required to go all the way down one branch?

A program running in space $f(n)$ can take up to $2^{O(f(n))}$ time (the constant depends on the alphabet size). Hence, it could potentially make up to $2^{O(f(n))}$ non-deterministic choices. Naively, going over all of them requires that many steps. Savitch's theorem shows how this can be accomplished using only $O(f(n)^2)$ space. The idea is to use a recursive "meet in the middle" approach. Let an upper bound on the running time of the machine be $T$. The initial tape is the the state of the tape when the machine is started up. The final tape is the state of the tape at the end of the execution. We "guess" (i.e., go over all possibilities) the final tape, and try to verify that this final tape can be reached from the initial tape. At the first level of the recursion, we "guess" the contents $X$ of the tape at time $T/2$. We then recurse into two similar tasks:

Verify that $X$ can be reached in $T/2$ steps from the initial tape.
Verify that the final tape can be reached from $X$ in $T/2$ steps.

Each of these is solved by recursion. We can reuse the space of the first task when we execute the second task. The base of the recursion is when the number of steps is one, in which case we can verify the claim directly. If it checks out, great. Otherwise, we signal failure, and this signal prompts us to make the next guess (at the appropriate level of recursion).

Each level of the recursion requires storage space of size $f(n)$, and there are $\log T = O(f(n))$ levels, so the total space consumption is $O(f(n)^2)$.


Finding the Shortest Path that connects k nodes in a graph I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass through all the $k$ nodes, but can contain other nodes from the graph and can visit those $k$  nodes in any order. In addition, any node can be traversed more than once. Also, the path has to start and end with two distinct nodes from the given set of $k$ nodes. For example, if $k=2$, we have two nodes, $u_1$ and $u_2$, and are looking for the shortest path from $u_1$ to $u_2$. We can use UCS or $A^*$ to solve this. If $k=3$, there will be three nodes: $u_1$, $u_2$, and $u_3$. The path can start in $u_1$, pass through $u_2$, and finish in $u_3$, or start in $u_2$, pass through $u_1$, and end in $u_3$, etc. $k$ can take any value from $2$ to $n$, $n$ being the total number of nodes in the graph.

To me, this somewhat looks like a problem of finding the minimal tree whose leaves are those $k$ nodes. A path passing through the leaves could then be obtained by traversing the tree in an appropriate order.

The state of a traversal at any point will be (a) the node you're currently at, and (b) the subset of the $k$ selected nodes you've already passed through.  Thus, you can solve this problem by constructing a new graph $G'$ that is $2^k$ times as large as the original graph $G$, and then finding the shortest path in $G'$.

In particular, each vertex of $G'$ has the form $(v,S)$ where $v \in V$ and $S$ is a subset of the $k$ selected nodes; for each edge $v \to w$ in the original graph, $G$' has the edge $(v,S) \to (w,S)$ (if $w$ is not one of the selected $k$) or $(v,S) \to (w,S\cup \{w\})$ (if $w$ is one of the selected $k$).

Unfortunately the running time of this algorithm is exponential in $k$.  I don't expect there to be a polynomial-time solution; David Richerby explains why not.


Derivation from grammar Given the grammar $G=(\{S, L_x, R_x, W_x\}, \{a,b\}, P, S)$ derive the words $abaaba$ and $aabbaabb$.
$$
P=\left\{
\begin{align}S\phantom{{}_x R_y}    &\to  \epsilon \mid L_x R_x,\\
    L_x \phantom{R_y}      &\to  x \mid L_x y W_y,\\
    W_x y\phantom{{}_y}    &\to  y W_x,\\
    W_x R_y                &\to  R_y x,\\
    R_x \phantom{R_y}      &\to  x \\
\end{align}\right\}$$
with $x,y$ element of $\{a,b\}$. ($x$ and $y$ may or may not be equal)
Following the rules I always end up with words of the form $xx, xyxy, xyyxyy, \ldots$.
Am I allowed to replace each $y$ differently? Otherwise I don't see any way to get words like $abaaba$.

The grammar as given in your assignment is an abbreviation for the following expanded grammar:
$$P=\left \{
\begin{align}
\begin{aligned}
S &\to \epsilon, \\
S &\to L_a R_a, \\
S &\to L_b R_b, \\ \\
L_a &\to a, \\
L_a &\to L_a a W_a, \\
L_a &\to L_a b W_b, \\ \\
L_b &\to b, \\
L_b &\to L_b a W_a, \\
L_b &\to L_b b W_b, \\
\end{aligned}\qquad\begin{aligned}
W_a a &\to a W_a, \\
W_a b &\to b W_a, \\
W_b a &\to a W_b, \\
W_b b &\to b W_b, \\[8pt]
W_a R_a &\to R_a a, \\
W_a R_b &\to R_b a, \\
W_b R_a &\to R_a b, \\
W_b R_b &\to R_b b, \\[8pt]
R_a &\to  a\\
R_b &\to  b\\
\end{aligned}\end{align}\right \}$$
So, yes, $x$ and $y$ need to be replaced consistently when you expand the shorthand notation. (And it's probably clear why the shorthand was used.)
Intuitively, what's happening here is that $S$ creates a left marker ($L_x$) and a right marker ($R_x$) which will eventually resolve to the same character. The left marker then expands to a sequence of $xW_x$ pairs, where $W_x$ is a "walker". The $W_x$s all walk to the right; when they finally hit the right marker, they deposit their payload after the right marker. This has the effect of creating two copies of the same string.
In an abbreviated form (combining derivation steps) you get something like this:
$$S\to L_aR_a\Rightarrow L_a b W_b a W_a R_a \Rightarrow L_a b a R_a b a \Rightarrow a b a a b a$$
Filling in the complete derivation would be a useful exercise. (Indeed, it's the exercise you've been asked to do.)


Several simple propositions about regular languages (Originally posted on Math-Stackexchange)
https://math.stackexchange.com/questions/2982949/regular-languages-and-regular-expressions

Notation:
$\Sigma:=\{a_1,\cdots ,a_\Delta\}$ finite alphabet
$\Sigma^n= \underbrace{\Sigma \times \Sigma \times \cdots \times \Sigma}_{n}$ Words of length $=n$
$\Sigma^*= \bigcup \limits_{n\geq0} \Sigma^n$ Set of all finite words
$L \subseteq \Sigma^*$ Language

I'm trying to prove, that the following statements are either true or false. Unfortunately, I'm having a hard time finding formal proofs for my answers. I hope you can help me out a bit.

Let $A,B$ be two subsets of $\{0,1\}^*$

If $A$ is regular pumpable and $B \subseteq A$, then B is regular pumpable too.
If $A$ not regular pumpable and $A ⊆ B$, then $B$ is not regular pumpable too.
If $A$ is regular and $B \subseteq A$, then B is regular too.
If $A \cap B$ is regular, then $A$ and $B$ are regular too.
There is at least one finite language on the alphabet $\{0,1\}$,
that doesn't meet the pumping lemma.

In all following counterexamples, $A$ and $B$ are subset of the full language $F=\{0,1\}^*$. Note that $F$ is a regular language.

  If $A$ is regular pumpable $B\subseteq A$, then $B$ is regular pumpable too.

Counterexample: $A=F$ while $B$ is any non-regular-pumpable language.

(It is taken for granted that a language being regular-pumpable means it is able to be pumped like a regular language. There are different ways to define being able to be pumped like a regular language; however it is defined, $\{0^n1^n\mid n\ge 0\}$ will not be regular pumpable. I made this note since some non-regular languages can be pumped like a regular language. For example, $\{ 01^{n^2} \mid n \ge 1 \} \cup \{ 0^kw \mid k\neq 1, w\in \{1\}^* \}$ is non-regular but can be pumped by the most common version of the pumping lemma for regular languages.)

(In case "regular pumpable" for a language is defined simply as "regular", just let $A=F$ and B be any non-regular language for a counterexample.)

  If $A$ not regular pumpable and $A\subseteq B$, then $B$ is not regular pumpable too.

Counterexample: $B=F$.

  If $A$ is regular and $B\subseteq A$, then $B$ is regular too.

Counterexample: $A=F$ while $B$ is non-regular.

  If $A\cap B$ is regular, then $A$ and $B$ are regular too.

Counterexample: $A$ is not regular while $B=F\setminus A$. $A\cap B=\emptyset$ is regular.

  There is at least one finite language on the alphabet $\{0,1\}$, that doesn't meet the pumping lemma rules.

That is not true. All finite languages are regular and, thus, meeting the pumping lemma rules.

  How do you come to that conclusion?

Mostly experience and knowledge plus a bit of luck. Before proving any proposition, you would like to do some sanity check with some simple and/or extreme cases. For example, you might have noticed that I have used the simple and extreme language $F$ several times.


Computing the longest common substring of two strings using suffix arrays After I learned how to build a suffix array in $O(N)$ complexity, I am interested in discovering the applications of the suffix arrays. One of these is finding the longest common substring between two strings, in $O(N)$ time. I found on the internet the following algorithm:

merge the two strings $A$ and $B$ into one string $AB$
compute the suffix array of $AB$
compute the $LCP$(longest common prefix) array
the answer is the largest value $LCP[i]$

I tried to implement it, but as many implementation details were not said(i.e. when concatenating the strings, should I put a special character between them($AcB$)?), my code failed on many test cases. Could someone elaborate more on this algorithm?

Thanks in advance.

Note: I do not guarantee the correctness of this algorithm; I found it on a blog, and I'm not sure it is working. If you think it is incorrect, please suggest another algorithm.

Your algorithm is incorrect. I assume you know how to compute the suffix array and the LCP array of a string, that is, their efficient implementation. As has been pointed out in the comments, you should try to understand what each component is, and why it works.

First of all, is the suffix array ($SA$) of a string. A suffix array is basically all the suffixes of the string $S$ arranged in ascending lexicographic order. More specifically, the value $SA[i]$ indicates that the suffix of $S$ starting from position $SA[i]$ is ranked $i$ in the lexicographic ordering of all suffixes of $S$.

Next is the $LCP$ array. $LCP[i]$ indicates the length of the longest common prefix between the suffixes starting from $SA[i-1]$ and $SA[i]$. That is, it keeps track of the length of the longest common prefix among two consecutive suffixes of $S$ when arranged in lexicographic order.

As an example, consider the string $S = abbabca$. The suffixes in lexicographic order would be $\{a, abbabca, abca, babca, bbabca, bca, ca\}$, so $SA = [7, 1, 4, 3, 2, 5, 6]$ for a 1-indexed array. The $LCP$ array would be $LCP = [-, 1, 2, 0, 1, 1, 0]$.

Now, given two strings $A$ and $B$, we concatenate them as $S = A\#B$, where $\#$ is a character not present in both $A$ and $B$. The reason for choosing such a character is so that when computing the LCP of two suffixes, say $ab\#dabd$ and $abd$, the comparison will break off at the end of the first string (since it only occurs once, two different suffixes will never have it in the same position), and won't "overflow" into the other string.

Now, it can be seen that you should be able to see why you only need to see consecutive values in the $LCP$ array (the argument is based on contradiction and the fact that the suffixes in $SA$ are in lexicographic order). Keep checking the $LCP$ array for the maximum value such that the two suffixes being compared do not belong to the same original string. If they don't belong to the same original string (one begins in $A$ and the other in $B$), then the largest such value is the length of the largest common substring.

As an example, consider $A = abcabc$ and $B = bc$. Then, $S = abcabc\#bc$. Sorted suffixes are $\{abc\#bc, abcabc\#bc, bc, bc\#bc, bcabc\#bc, c, c\#bc, cabc\#bc\}$.
$\begin{align*}
SA &= [4, 1, 8, 5, 2, 9, 6, 3, 7] \\
LCP &= [-, 3, 0, 2, 2, 0, 1, 1, 0]
\end{align*}$

Now, the greatest value is $LCP[2] = 3$, but it is for $SA[1]$ and $SA[2]$, both of which start in the string $A$. So, we ignore that. On the other hand, $LCP[4] = 2$ is for $SA[3]$ (corresponds to the suffix $bc$ of $B$) and $SA[4]$ (corresponding to suffix $bcabc\#bc$ of $A$). So, this is the longest common substring between the two strings. For getting the actual substring, you take a length $2$ (value of the greatest feasible $LCP$) substring starting from either $SA[3]$ or $SA[4]$, which is $bc$.


Algorithm for listing all binary trees of a given height I've been trying to find an algorithm to list all binary trees of a given height $h$.

Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699).

All the algorithms that I have been able to see list all binary trees for a given number of nodes. A very inefficient way of solving the problem would proceed by checking all the trees with a number of nodes between $h+1$ and $2^{h+1}-1$, but this is not great at all.

Any pointers or references would be much appreciated.

As hinted at in comments, just follow the recursive structure of binary trees.

We create a function listbt(h) that lists all binary trees of exactly height h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

Correctness follows with an elementary inductive proof over h.

If you memoize the results of listbt this is going to be as efficient as it gets; the sheer number of trees and thereby the number of checks t != T dominate.

Note that if you employ term sharing (i.e. only link t and T in Node(t, T) but do not copy them) you can reduce the size of the output significantly. That only makes sense if your BTree implementation is immutable, though.


Is this FA really equivalent to the given regular expression? From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$.

So the Automata in the picture is not equivalent to the RE?

They aren't equivalent. For example, the string "L__L" is described by the expression, but not accepted by the automaton (no way to have two '_' in a row).


When to free physical registers When we do register renaming to avoid WAR and WAW hazards while executing instructions, how can we know that there is no need for a physical register anymore and we can put it back in the free list?

I find the simplest way to think about this problem is to consider a machine that has two Register Alias Tables (RAT).  These tables simply store the physical register identifier associated with each architectural register.

The two tables sit in the retirement stage (the Retirement Register Alias Table or RRAT), and the renaming stage. Retirement and renaming both happen in-order, no matter how the execution stages work.  The Retirement-RAT represents the architectural/non-speculative state of the machine.  The renaming RAT represents the speculative state of the machine (the state the machine will have if all of the speculative decisions made before the current instruction were to be found to have been correctly predicted).

Think about the state of the Retirement Register Alias Table just before the retirement of an instruction that writes to (architectural) register $R$.  At this point the Retirement Register Alias Table contains a mapping from $R$ to $P_0$, the previous physical register that was assigned to architectural register $R$, and the next instruction to retire will have a different assignment from $R$ to $P_1$.  Since retirement happens in-order, we know that all instructions that could have referenced physical register $P_0$ have already retired, and thus physical register $P_0$ can be returned to the free list.

Many (most) actual out-of-order designs do something more complicated than what I've described here (instead of Register Alias Tables mapping from architectural to physical registers, there are CAMs mapping from physical to architectural registers which allows quicker recovery from mis-speculations), but the reasoning techniques are the same: renaming and retirement both happen in-order, and you can use that fact to reason about which registers can be returned to the free list.


Peaking finding when equals is taken out of the equation I am going through the online course MIT OCW 6.006, lecture 1. It introduces a binary search algorithm that finds a peak in O(lgN) time.

A peak A[i] is defined as A[i]>=A[i-1] and A[i]>=A[i+1]. But I wonder what if the definition takes the equal sign out A[i]>A[i-1] and A[i]>A[i+1], a peak is defined as an element that is strictly larger than its neighbour.

Obviously, the binary search algorithm will not work without changes, because for a case that A[i]=A[i-1] and A[i]=A[i+1], it cannot decide to go left or right.

So, is there any algorithm that stills take O(lgN) time? (I personally think no, because for an array of equal numbers, aka the case that a peak does not even exists, you need to examine all elements)

I can further improve your approach - let's consider an array that has peak, but all but two elements in the array are equal. O(log n) comparisons can check only O(log n) elements, so it's not enough even to decide whether peak is in first or second half of the array.


Can big-step semantics express evaluation order? Can you express evaluation order using big-step semantics?

For example, in a simple language consisting of only if t then t else t and true and false, we can decide to only step a if then else to one of its branches if its branches are already values.

Can big-step semantics express the same thing?

No, you cannot express evaluation order using big-step semantics.

Borrowing from Benjamin Pierce: big-step semantics is a multi-step evaluation relation that directly formulates the notion of "this term evaluates to that final value". So it cannot impose the kind of evaluation order you describe.

Also keep in mind what the horizontal bar represents. Again borrowing from Pierce: If we have established the statements in the premise(s) listed above the line, then we may derive the conclusion below the line. It would not make sense to impose an ordering on the premises to draw the conclusion.


n closest points in a set of lat/long coordinates Here's my problem:

I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long coordinates. I also have a function to calculate the distance between two points based on their coordinates.

Now I'm looking for a way to find one of these things:

The n nearest products to the user's location.
All the products within a radius of x kilometers from the user's location.

Both solutions would be fine for my application.

Currently I just iterate over all the database entries, find their distance, and sort them. This obviously gets way too slow with a lot of entries.

Are there any algorithms/data structures I can apply here to make it faster?

Thanks in advance!

Your problem (at least the second variant) is known as 2D range searching. Commonly used data structures are range trees and k-d trees. Searching for range searching on the web will open you a window into the area. These lecture notes come up, for example.


k-path problem - P, NP or NPC? I need to determine which complexity class this problem belongs to:

  Given a graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of length $k$ exist between thesee two vertices?

How can I approach this problem to solve it?

If the path has to be simple reduce the HamiltonPath problem to this to show that's NP-complete, otherwise (not necessarily simple paths) take the $k$-th power of the adjacency matrix, whose entry corresponding to $u$ and $v$ not only contains whether there is such a path, but also the number of such paths.


What is "memory coalescing"? I came to know that the graphic processing unit have something called memory coalescing. On reading on it I was not clear on the topic. Is this any way related to Memory Level Parallelism.

I have searched in Google but was not able to obtain a satisfactory answer.

It would be helpful if someone gives a more comprehensive, easy-to-understand explanation.

"Coalescing" can also refer to coalescing memory access patterns. In this usage, coalescing is used to mean making sure that threads run simultaneously, try to access memory that is nearby. This is usually because:

Memory is usually retrieved in large blocks from RAM.
Some processing units will try to predict future memory accesses and cache ahead, while yet processing older parts of memory.
Memory is cached in a hierarchy of successively larger-but-slower caches.

Therefore, making programs that can use predictable memory patterns is important. It is even more important with a threaded program, so that the memory requests do not jump all over; otherwise the processing unit will be waiting for memory requests to be fulfilled.
Diagrams inspired by Introduction to Parallel Programming: Lesson 2 GPU Hardware and Parallel Communication Patterns:
Below: Four threads, with uniform memory access. The black dashed rectangle represents a single 4-word memory request.

The memory accesses are close, and can be retrieved in one go/block (or the least number of requests).
However, if we increase the "stride" of the access between the threads, it will require many more memory accesses. Below: four more threads, with a stride of two.

Here you can see that these 4 threads require 2 memory block requests. The smaller the stride the better. The wider the stride, the more requests are potentially required.
Of course, worse than a large memory stride is a random memory access pattern. These will be nearly impossible to pipeline, cache or predict.
TikZ sources:

Memory.Access.Coalescing.tex (writelatex)


What guarantees do "soft" real-time operating systems actually provide I think I know what a "hard" real-time operating system is.  It is an operating system with a scheduler that provides a contract with the application programmer.  An application provides a deadline with each resource allocation request.  If the deadline requests are feasible, the scheduler guarantees that each resource will be allocated to the requesting application before the deadline.  The guarantee is sufficient to enable an application programmer to reason about the maximum latencies and minimum throughputs of specific requests.

All the definitions I find of "soft" real-time systems seem vacuous to me.  Wikipedia says

  the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.

Uhhhh.  Okay.  By that criteria Windows 95 was a soft real time system and so was 3BSD and so is Linux.  Wikipedia is not a great source, but the next couple of Google hits aren't much better.  For example http://users.ece.cmu.edu/~koopman/des_s99/real_time/ says

  In a soft real-time system, a degraded operation in a rarely occurring peak load can be tolerated.

That's not a contract, that's a fancy way of saying nothing.

What are examples of real soft real-time guarantees/contracts offered by real operating systems?

I'm looking for answers of the form:

  In (OS-name) if programmer does (what-programmer-needs-to-do) then the operating system guarantees (what-the-system-guarantees).

You've got it right, and Wikipedia is as informative as can be — soft real-time is not a formal characterization, it's a value judgement. Another way to say “soft real-time” is “I wish it was real-time”, or perhaps more accurately “it should be real-time but that's too hard”.
If you really want to word in the form of a guarantee, it's a guarantee of best effort rather than a guarantee of specific performance.
Or, to quote the Erlang FAQ (Erlang is a programming language originally designed for use in telephony):

What does soft realtime mean?
Cynics will say "basically nothing".
(…) Many telecomms systems have less strict requirements [than hard realtime], for instance they might require a statistical guarantee along the lines of "a database lookup takes less than 20ms in 97% of cases". Soft realtime systems, such as Erlang, let you make that sort of guarantee.

And this does provide a useful definition. Soft real-time indicates a design which is optimized towards each individual task taking no more than a certain amount of time, rather than towards optimizing the total time spent to perform all tasks. For example, a soft real-time system would aim to complete 99.9% of the requests in 10ms and process 100 requests per second, where a non-real-time might aim to proceed 200 requests per second but allow the occasional request to block for 50ms or more. A hard real-time would guarantee one request every 15ms no matter what.
Soft real-time is used for applications where a missed deadline means a degradation of service, but is not performance-critical. Multimedia and telephony are some typical use cases. Each audio or video frame must be rendered it time, or else it has to be skipped; but skipping a frame is not the end of the world. The designers of Erlang had similar objectives on reliability in other matters: they observed that it was better for a telephone exchange to very occasionally drop a call, but to be absolutely sure that the exchange as a whole would keep working come what may, than to ever risk catastrophic failure in trying to maintain connections at all cost.
In contrast, something like controlling a motor requires that the software never misses a deadline. This has costs: the overall performance is typically slower, and only relatively simple behaviors can be achieved. On the other side of the spectrum, a number crunching application typically cares only about overall performance — what matters is how fast the 1000x1000 matrices are multiplied, not how fast each column is calculated.


How is it possible to compare $P$ class with $BQP$? BQP : (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Question : We know that $\mathsf{P}$ and $\mathsf{NP}$ classes are defined on Turing model of computation where as $\mathsf{BQP}$ is defined over quantum model of computation. When there model of computation are different how we can say that $\mathsf{P} \subseteq \mathsf{BQP} $?

BQP is simply a set of languages, i.e. $\mathsf{BQP}\subseteq 2^{\Sigma^*}$, and in that sense it can be compared with any other set of languages, such as $\mathsf{P, NP}$. It doesn't matter how those sets are defined, as we can always ask whether they are comparable under the inclusion relation.

You can ask why does it make sense to compare classes obtained from different models of computation (e.g. uniform polynomial size quantum circuits vs polynomial time Turing machines). The idea is to try and capture the notion of "efficiently computable" relative to each model. If you agree that efficiency in quantum/classic computation is captured by BQP and P, then the question "can quantum computers solve more problems efficiently" translates to whether or not $\mathsf{P\subsetneq BQP}$.


Proving that the continuation of a non-regular language is not ω-regular I want to prove that a language is not $\omega$-regular.

The language I'm working with can be defined as:

$$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$

where $L^\prime$ is a specific non regular language (I omit the definition $L^\prime$ because I think it is of no help for my problem), $a_i$ are symbols in $L^\prime$ alphabet and $x$ is any symbol not in $L^\prime$ alphabet.

I'm aware of several proof techniques for proving a language is not regular (see e.g. How to prove that a language is not regular? ).

Are there similar proof techniques for proving that a language is not $\omega$-regular?

If $L'$ is regular then it is easy to extend a DFA for $L'$ to a deterministic Büchi automaton for $L$. For the other direction, start with a (general) Büchi automaton for $L$. Call a state winning if the automaton accepts starting at the state upon reading $x^\omega$. Remove all $x$ transitions and make winning states accepting to obtain an NFA for $L'$.


Arden's lemma applicability on context free grammars The Arden's lemma states that there exists a solution to the equation between regular expressions
r = sr + t, with r unknown, and it is s*t.

I went through some other topics on the forum and I always saw it being applied, for example, on grammars that have productions like

S->AS|b

so that L(S) = L(A)L(S) + b and the solution is L(A)*b.

However, on some student notes from a classmate I found this example:

S->ASA|A

A->aAa|Ab|e

and the Arden's rule is applied in this way without any further manipulation of the grammar:

L(S) = L(A)L(S)L(A) + L(A) and it concludes by saying that L(S) = L(A)*

This seems wrong to me, but I want to check first whether there is some further hypothesis that can be applied here to make the statement valid.
For example, I wonder if it is decidable (and of course valid) whether the productions S->ASA|A generate the same language of the productions S->AAS|A.

Can somebody please help me?

First of all, let me mention that Arden's lemma applies not only to regular expressions but to any equation among languages of the form $r = sr+t$, where $r,s,t$ are arbitrary languages. The smallest solution to this equation (also known as the least fixed point) is always $r = s^*t$. If $\epsilon \notin s$, then this is in fact the only solution. (Otherwise, $\Sigma^*$ is also a solution.)

The language generated by the rule $S\to aSa|a$ is not $a^*$ but rather $a(aa)^*$: only odd powers are allowed. So it seems that the student notes contain a mistake, though in this particular case the calculation yields the correct conclusion since $\epsilon \in L(A)$.

On the other hand, $S\to aSa|a$ and $S\to aaS|a$ do generate the same language.
More generally, if the only rules involving $S$ are $S \to ASA|A$, then replacing these rules by $S \to AAS|A$ or $S \to A|SAA$ result in the same language, $L(A)(L(A)^2)^*$; and if $\epsilon \in L(A)$, we can further simplify this to $L(S) = L(A)^*$.


Can we use the same reduction L1 -> L2 for coL1 -> coL2 does L1

    ≤
    p

 L2
yield that coL1

    ≤
    p

coL2 for the same reduction?

Yes. If $f$ is a polynomial-time computable function such that $x \in L_1 \iff f(x) \in L_2$ then

$x \in \text{co}L_1 \iff x \not\in L_1 \iff f(x) \not\in L_2 \iff f(x) \in \text{co}L_2.
$


Meaning of ⟨_⟩ in the context of verifiers A verifier for a language A is an algorithm V, where $$A = \{w \mid V
\text{ accepts $\langle w,c \rangle$ for some string $c$}\}$$ ($c$ is called a certificate or
  proof)

What's the definition of $\langle , \rangle$ here?

Any reasonable definition would do (I'll provide a formal definition later on). One simple definition, when $w,c$ are strings over some alphabet $\Sigma$ which doesn't contain the space character, is that $\langle w,c \rangle$ consists of $w$, a space, and $c$.

More generally, suppose that $\langle w,c \rangle_1$ and $\langle w,c \rangle_2$ are two definitions of the pairing function such that:

There exists a polytime function $f$ such that $f(\langle w,c \rangle_1) = \langle w,c \rangle_2$.
There exists a polytime function $g$ such that $g(\langle w,c \rangle_2) = \langle w,c \rangle_1$.

Then if we define NP using $\langle,\rangle_1$ and $\langle,\rangle_2$ we obtain the same class. A reasonable definition is one that satisfies (1) and (2) for the pairing function I described above.

This sort of situation happens often in complexity theory. When the details of the input representation don't make a difference, we don't bother specifying them exactly. That's because we never actually refer to these details, so they are "too much information". You only need to worry about such details when you're actually programming, or when you're dealing with very weak complexity classes, for which converting between different input representations can be difficult.


How can primitive recursion in two variables be made to be of only one variable? Problem 7.16 in The Nature of Computation reads as follows:

  [...] show that when defining primitive recursive functions, we really only need to think about functions of a single variable. In particular, show that a function $f(x)$ is primitive recursive if and only if it can be generated from $0$, $S$, $pair$, $left$, and $right$, using composition and iteration, where iteration is defined as follows: if $f(x)$ and $g(x)$ are already defined, we can define a new function $h(y)=g^y(f(0))$. In fact, we can simplify this further and just take $h(y)=g^y(0)$.

($S$ is the successor function. $pair$, $left$, and $right$ create a tuple and take it apart again.)

It's easy to see that one can use $pair$, $left$, and $right$ to put multiple arguments into a tuple, pass that to a function and have that function extract the arguments back out. Similarly a recursive function of the form $f(x) = g(x,f(x-1))$ can be replaced by $f(x) = h^x(0)$. ($h$ will have to return a tuple $(x, f(x-1))$).
However I'm unable to deal with the case where multiple parameters and recursion occur simultaneously, i.e. $f(x,y)=g(x,f(x,y-1))$. The trouble occurs before trying to replace the recursion by iteration, at the stage where multiple arguments have to be combined. The problem is that, the way I see it, primitive recursion is only allowed to call the immediately next smaller case. For instance, $f(64)$ can call $f(63)$, but not $f(32)$. But $pair(x,y-1)\neq pair(x,y)-1$. So when calling a recursive function with a tuple, it can't access the corresponding smaller case that it would've had access to in the multi-parameter setting.

For reference: $pair$ is defined similar to how the rationals are put in a one-to-one correspondence to the natural numbers by Cantor's argument. Though instead of snaking back and forth along the diagonals, it always moves along a diagonal in the same direction, starting over when reaching the end of one.

A few facts that should help:

1 - You can encode lists with primitive recursive functions

I can expand if needed.

I'll write lists as $[x_1, \dots, x_n]$, write $x::[x_1,\dots ,x_n]$ for $[x,x_1,\dots,x_n]$ and $\operatorname{hd}([x_1,\dots ,x_n])$ for $x_1$.

2 - You can use any order you want when defining a function by primitive recursion

Let $b$ be a primitive recursive bijection whose inverse is also primitive recursive. Then you can use recursion with respect to the order $x<_by$ defined as $b(x)<b(y)$ and it will still define primitive recursive functions. Suppose that you have $g(x,b(0))=g_0(x)$ and $g(x,b(k+1))=h(x,b(k),g(x,b(k)))$. Then you can define $g'(x,0):= g_0(x)$ and $g'(x,k+1)=h(x,b(k),g'(x,k))$ and you will get $g'(x,k)=g(x,b(k))$ so that you can now define $g(x,y):=g'(x,b^{-1}(y))$.

3 - Your function can know its value on all smaller inputs when defining a function by primitive recursion

Let $X$ be the domain of your function $g$ defined by $g(x,0)=g_0(x)$ and $g(x,k+1)=h(x,k,[g(x,k),g(x,k-1),\dots,g(x,0)])$. Then you can define $g'(x,0):=[g_0(x)]$ and $g(x,k+1):=h(x,k,g'(x,k))::g'(x,k)$ and you will have $g'(x,k)=[g(x,k),g(x,k-1),\dots,g(x,0)]$. You can therefore define $g(x,k):=\operatorname{hd}(g'(x,k))$.


Maximum matching on a tree How should I compute efficiently a matching of maximum size in a tree?

My thoughts so far: since from a path we can get a matching, then just finding the longest path in the tree should be enough to answer the question.

Am I wrong? another approach?

You can do much better. Consider for example the tree in which the root has $N$ children, and each one has one child. The maximum matching has size $N$, but the longest path is only four edges long.

Here is a better algorithm. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the subtree, as well the maximum matching within the subtree that doesn't touch the root of the subtree. You can think of it as a form of dynamic programming.

Many problems on trees can be solved efficiently using this kind of dynamic programming.


Heap comparison based sorting question I need some help with this question from my problem set. I do not want a solution but some $\textbf{hints}$ on how to proceed.

  Given $n$ records in a file that are so numerous, that just storing
  the $n$ keys alone would require more RAM than is available on your
  computer. Let $m$ be the maximum number of
  records that you can store in RAM at once. Assuming that $m >$
  $\sqrt{n}$, produce a $\mathcal{O}(n \log n)$ time algorithm for sorting
  the $n$ records. The sorted records would then be written to a file, since
  it will not be possible for them to all fit in memory at once.

$\textbf{My approach:}$ I figure I should use a heap based approach. Try to create a type of online algorithm to read $m$ records at a time, and then use heapsort or a type of comparison based algorithm to solve it?

$\textbf{Related Questions:}$

1) I don't understand the underlying assumption of letting $m>\sqrt{n}$?

Hint: Convert the input into $n/m < m$ chunks of length $m$ and sort the chunks. Then use your heap idea. Note that you're using the assumption $m > \sqrt{n}$ so that the heap fits in memory.