Consider a linear program of the following form: maximize $c^Tx$ over $Ax \leq b$, where $x \in \mathbb{R}^n$ and $b$ has integer entries.
The simplex algorithm finds a solution of the form $x = A_S^{-1} b_S$, where $A_S$ is a submatrix consisting of $n$ rows, and $b_S$ are the corresponding entries of $b$. Each entry of $A_S^{-1}$ is a ratio of two determinants: the determinant of some $(n-1)\times(n-1)$ submatrix of $A$ (namely, minors of $A_S$), and the determinant of some $n \times n$ submatrix of $A$ (namely, $A_S$). If the entries of $A$ are integers and every $n \times n$ submatrix has determinant $0,\pm 1$, then $A_S^{-1}b$ is integral.
The condition that any square submatrix has determinant $0,\pm 1$ is known as total unimodularity. If the constraint matrix $A$ is totally unimodular, then the simplex algorithm will always find an integral solution.
A more general condition is total dual integrality, which just states that for every integral $c$, the linear program has an integer optimal solution. If the system satisfies TDI then the simplex algorithm is also guaranteed to find an integral solution.


Is it legal to use non-terminal twice in Backus-Naur grammar

Yes, you are allowed to use the same non-terminal more than once in a rule.

Note that the two grammars you give do not express the same set of strings.
The first grammar gives any sequence of 6 or 7 following the +, as  can be applied recursively. The second defines exactly four strings +66, +67. +76, +77.


I agree that it's a misnomer. Consensus from the comments seems to be that "circular function" is not a commonly used term for a recursive function. I think the person you saw using the term was using the wrong word, perhaps because of translation issues.


Set Basis Problem Variant reference for NP-Completeness?

The problem is in fact solvable in polynomial time.

Let
$$C_0=\Bigl\{c\in C:c\supsetneq\bigcup_{\substack{c'\in C\\c'\subsetneq c}}c'\Bigr\}.$$

On the one hand, if $B\subseteq C$ has the property in the question, then $C_0\subseteq B$: since $c\in C_0$ cannot be written as the union of its proper subsets from $C$, a fortiori it cannot be written as a union of its proper subsets in $B$, hence the only possibility is $c\in B$.

On the other hand, $B=C_0$ does have the required property. We prove by induction on $|c|$ that any $c\in C$ is a union of a subcollection of $C_0$: if $c\in C_0$, this holds trivially; otherwise $c$ is the union of its proper subsets in $C$, which in turn can be written as unions of subcollections of $C_0$ by the induction hypothesis.

Thus, the problem is equivalent to $|C_0|\le K$, which can be checked in polynomial time.


How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation.

[1] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test


Pumping lemma for regular languages. Proof

I assume that you want to show that the language $L$ does satisfy the Pumping Lemma, as it indeed is regular. In words your language consists of all strings that have length at least 4 and contain two consecutive symbols that are the same. The position of a pair of equal letters letters is indicated here with $i$. (Note $i$ in general is not unique.)
So we need to explain that all strings in the language (above a certain length) can be pumped within the language.
You must realize that your division into $uxw$ can actually depend on the string $a$ itself.
So if $a$ starts with a repeated letter, e.g., $a = 00\dots$, we can pump the third letter. Otherwise if the repeated pair is assumed to be not in the first position, we can then pump the first symbol and we keep the repetition in the string while pumping.


An algorithm to compute a set of states that satisfy a specific CTL formula

The set of states satisfying $\exists a U b$ is the smallest set $S$ such that

$S$ contains all states satisfying $b$, and
$S$ contains all states satisfying $a$ which have a successor in $S$

Note that we specify the "smallest" such set because otherwise you could  pick the set of all states, or include arbitrary cycles of $a$-states, etc. Do you see how to get an algorithm from this?


Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$

Your recurrence can be solved using the Akra–Bazzi theorem, a vast generalization of the master theorem. The result is $\Theta(n\log n)$.
You can also see this using a recursion tree. The root is labeled $n$. An internal vertex $m$ has children labeled $m/5$ and $4m/5$. Vertices are leaves if their labels is at most some arbitrary positive constant $C$, say $C=1$. The running time is proportional to the sum of all labels.
We can partition the vertices in the tree to levels according to their distance from the root. The first $\log_5 n$ levels of so are "complete", that is, their labels sum to $n$, and there are $\log_{5/4} n$ levels in total, so the sum of labels is between $n\log_5 n$ and $n\log_{5/4} n$ levels. In particular, the complexity is $\Theta(n\log n)$.


Algorithm for efficiently sorting large lists based on user preference

"Being more interesting" is not a transitive property. I can simultaneously find book A more interesting than B, book B more interesting than C, and book C more interesting than A. (On top of that, whether A is more interesting than B might also depend on when you ask me).

I wouldn't use a yes/no decision but let's say a range from -10 to +10, which allows the user to say that a book is much more interesting or just a tiny little bit more interesting than another boo.

I wouldn't modify ranks after each user comparison of two books, but remember all the rankings, and then each time give all the books a ranking, and find one that minimises the difference between the ranking and the user comparisons.

There's probably a good algorithm to do so. A not very good algorithm: Start ranking all books with an "interestingness" of zero. For each set of rankings we can calculate the error: For each user comparison between books A and B, calculate rating (A vs. B) minus (ranking A - ranking B), sum the squares of these.

Pick a book at random and change its ranking to minimise the error while leaving all other rankings unchanged. Repeat until you can't manage to improve it anymore.


C(++) library for DFAs - free for academic use

I don't know of a full blown library, but based on [1] there is a really fast practical C++ implementation available from the author's homepage here.

[1] Valmari, Antti. "Fast brief practical DFA minimization." Information Processing Letters 112.6 (2012): 213-217.


Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

This is actually not very complicated.  I'll assume that epsilon productions have already been eliminated from the language, because that will only obscure the key concept of "left corner".

Form a graph G where the vertices are all the non-terminals of the grammar.  Now draw a directed edge from A to B if there is any production rule that looks like "A -> B[...]".  The paper calls B a "direct left corner" of A.  More generally, some other non-terminal C is called a "left corner" of A if there is some path from A to C along the edges of this graph.  This can be done by computing the transitive closure of G, call it H.

The paper suggests ordering the vertices by counting the number of left corners each vertex A has (i.e. how many other non-terminals you can reach from A, or the out-degree of A in the graph H), then sorting them in decreasing order by this number.

One handwavy motivation for this policy is that if there is an important non-terminal (say the starting symbol S) with connections to many other symbols), then it makes sense to purge left-recursion from S early on, because if you leave it till later there will be more copies of S that you need to expand out.  I think the explanation in the paper is more convincing, but perhaps less obvious.


How to find the number of Binary Search Trees with given number of nodes and leaves?

You can compute the numbers with dynamic programming.

Let $c(n,l)$ be the number of BSTs with $n$ nodes and $l$ leaves, where the nodes are selected from a set of $n$ distinct nodes. Then we have the following recurrence relation in general cases,

$$c(n,l) = \sum_{i=0}^{n-1}\sum_{j=0}^l c(i,j)\cdot c(n-i-1, l-j)$$

The outer summation is over $i$, the number of nodes in the left sub-BST of a BST with $n$ nodes and $l$ leaves.
The inner summation is over $j$, the number of leaves in the the left sub-BST of $i$ nodes.
The product $c(i,j)\cdot c(n-i-1, l-j)$ is the number of BSTs whose left sub-BST has $i$ nodes and $j$ leaves and whose right sub-BST has $n-i-1$ nodes and $l-j$ leaves. Please note that the root of such BST has only one choice, namely, the $(i+1)^{th}$ smallest node.

I will let you figure out the boundary values of $c(n,l)$ such as when $n=0$ or $n=1$ or $l=0$. There might be a few different cases. However, this should be enough to point you to the right direction.


How can an LBA check legality of TM transitions without extra memory?

B is given the complete computation history as input. All it does on that input, according to the description, is moving around, reading, marking, and unmarking things. Moving around and reading obviously don't need extra space, and marking/unmarking can be done in-place as well. (For each letter of M's alphabet B's alphabet can contain a marked copy, so that marking just means replacing the unmarked symbol with the marked one.) Thus, all is well.


Yes, undecidable also applies to problems that cannot be represented by TM at all. The ones where a YES can always be found are a subclass of these called (recursively) enumerable. Unsolvable is a less common term which I know mostly to be used synonymous to undecidable.

So  decidable - undecidable but enumerable - non-enumerable  is a partition of the class of all problems into three classes, where the middle one is intuitively somthing like the easiest undecidable problems.


Transforming a byte with a subset of a small, fixed set of values and xor into any other value

You have recalled the correct category, "linear-algebra".

Let us see how we can interpret xor in the terms of linear-algebra. Here is the computation rules for xor.
$$0\oplus0=0$$
$$0\oplus1=1$$
$$1\oplus0=1$$
$$1\oplus1=0$$
If we consider 0 and 1 as the zero element and the unit element of the binary field $\Bbb F_2$, the simplest finite field, then we can see $\oplus$ is none other than the addition in $\Bbb F_2$.
$$0+0=0$$
$$0+1=1$$
$$1+0=1$$
$$1+1=0$$

That means, if we xor a string of 3 bits to another string of 3 bits, we are actually adding two vectors $\vec a$ and $\vec b$ in the three-dimensional linear space $\Bbb F_2^3,$
$$\vec a+\vec b=\vec c$$
For example, $(0,1,0) + (1,1,0)=(1,0,0)$.

If we fix the second vector, the addition by the second vector is a linear transformation from $\Bbb F_2^3$ to $\Bbb F_2^3$. All these transformations form a 3-dimensional linear space over $\Bbb F_2$ with basis
$$\{\text{addition by (1,0,0)}, \text{ addition by } (0,1,0), \text{ addition by (0,0,1)}\}.$$
Given a set of vector in $\Bbb F_2^3$, all combinations of the additions by those vectors can transform any vector to another vector if and only those vectors are linearly independent.

For example, "three bits 0b101, 0b110 and 0b011" "do not have this property" because, $(1,0,1)+(1,1,0)+(0,1,1)=(0,0,0)$ in $\Bbb F_2^3$, i.e, those three vectors are not linearly independent.

Here is a counting exercise.

(Exercise) Show the number of sets of such strings of 3 bits is $(2^3-1)*(2^3-2)*(2^3-2^2) = 168.$ In general the number of set of such string of n bits is $(2^n-1)(2^n-2)\cdots(2^n-2^{n-1}).$


What is normally meant in cases like this is

  there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,

with an implicit

  but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.

Whether it really is trivial is a trickier thing (but often it really is).

Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:

A problem is in $\mathcal{NP}$ if, given the input and a solution, we can check that the solution is correct in deterministic polynomial time, or
given the input, we can compute the solution in non-deterministic polynomial time.

So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:

Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or
Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ if we can make some really good guesses.

Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.

The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.

Footnotes.

As A. Schulz notes in the comments, there is an additional issue of ensuring that the witness (the solution handed to us) has an encoded length bounded by a polynomial in the size of the original input. This may be easy to see, but as A. Schulz also notes, if we're talking about the Geometric Steiner Tree problem, then we might have to make an additional argument about how we encode the geometry of the tree - not necessarily too complicated, but still important. If we're talking about the Steiner Tree Problem in Graphs, then it's more straightforward (as we don't have to worry about the geometry), and perhaps something you can gloss over. Nonetheless it is important to be careful :).


Why can't you write the 2-paths problem as a max-flow problem?

The proposed construction does find two vertex disjoint paths from s to t (if they exist). HOWEVER, the paths might be $P_1=(s_1,…,t_2)$ and $P_2=(s_2,…,t_1)$, which is not what we want.


How does 0 have two values in one's complement?

In 1's complement you just invert all the bits.

Consider these 2 examples (assuming 8 bits):

$4 = 00000100$,  so $-4= 11111011$
$0 = 00000000$, so $-0=11111111$.

So you have 2 ways to represent the number 0

In 2's complement you add 1 to the 1's complement representation of the negative number

$-4$ that in 1's complement was $11111011$ becomes $11111100$
$-0$ that in 1's complement was $11111111$ becomes $00000000$ same as 0

So you have just one way to represent the 0 in this case

As you can see from the examples the difference is that:

in 1's complement, with 8 bits you can just express numbers from $-2^{7}+1$ to $2^7-1$ (from -127 to 127)
in 2's complement with 8 bits you can express numbers from $-2^{7}$ to $2^{7}-1$ (from -128 to 127), so one more number


$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$

Yes, I can.

First of all, $\mathrm{poly}(\mathrm{subexp}) = \mathrm{subexp}$. So, we can simulate a subexp TM in subexp time. (This is in stark contrast to standard $\mathrm{SUBEXP}$ where we do not have any particular subexp machine)

Using this, we are able to put $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$. The poly space TM would try every possible poly-size circuit and for each circuit make $2^n \times 2^n$ local checking of the tableaux using the current circuit. Note that the subexp TM never touches the $2^n$th cell and would cease to run long before $2^n$ time but that does not affect the poly space bound.

After putting $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$, we use the result of interactive proving protocol with the power of the prover at most $\mathrm{P}^\mathrm{L}$ (where $\mathrm{L}$ is the language at hand) to push it down to $\mathrm{MA}$.


$A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$

If $0 \in A$ then clearly $0 \in A^* = B^*$. Conversely, if $0 \in B^*$ then $0 \in B$: indeed, if $0 = w_1 \ldots w_n \in B$, then exactly one of the $w_i$ can be non-empty, and it must equal $0$. Therefore $\{0,1\} \subseteq A$ and $A^* = B^*$ implies $\{0,1\} \subseteq B$. In other words, there are no two languages $A,B$ satisfying your constraints.


Counting the nodes in a network in a distributed way

For constant node degrees, the following simple algorithm seems to work:
The source node $s$ can initiate a BFS tree construction and then we simply accumulate the count upwards along the tree edges starting from the leafs and ending at $s$. Each node locally keeps track of its parent/children in the tree; note that we can do this using $O(\log n)$ space as the degree is constant and therefore each node knows if it is a leaf.

For arbitrary degree, there's also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds. (In each round, every node can reliably exchange $O(\log n)$ bits with each of its neighbors.)

Suppose that I have a network $G$ with diameter $Diam(G)$.

Each node $u$ generates a random value $x_u$ according to the exponential distribution with rate 1; we round $x_u$ to $\Theta(\log n)$ bits.
Node $u$ also has a local variable $minval_u$ where it keeps track of the minimum value encountered so far. Initially, $minval_u = x_u$.
For the next $Diam(G)$ many rounds, node $u$ sends $minval_u$ to its neighbors. Also, upon receiving $minval_v$ from some neighbor $v$, node $u$ sets $minval_u = \min(minval_u,minval_v)$.
After round $Diam(G)$, node $u$ computes its estimate of the number of nodes as $1/minval_u$.

Why does this algorithm work?

Our algorithm exploits the following nice property of the exponential distribution (see here):
If we have $n$ exponential random variables $X_1,\dots,X_n$ each of rate $1$, then the random variable $X = \min(X_1,\dots,X_n)$ is also exponentially distributed of rate $n$ and therefore has expected value $1/n$. At the end of the algorithm, the $minval_u$ variable corresponds to a sample of this random variable $X$. Therefore, to get the sought value $n$ (i.e. the number of nodes), we simply compute $1/minval_u$. To get a high probability bound, we can repeat the above $\Theta(\log n)$ many times and take the average of the produced estimates.


Recognizing vs Deciding in defining class BPP

Complexity theory makes no distinction between "deciding" and "recognizing". The two words are used interchangeably. Turing machines considered in complexity theory are usually assumed to always halt. Indeed, usually only time-bounded machines are considered (such as polytime Turing machines), and these halt by definition.

In your particular case, you can interpret accept as halting in an accepting state, and reject as halting in a rejecting state. The Turing machine is thus allowed not to halt. However, the class BPP also requires the machine to run in polynomial time, that is, to halt in polynomial time. In particular, the machine must always halt.


Path in digraph passing through given set of vertices

Decompose the graph into strongly connected components. You get a DAG, each vertex of which represents a strongly connected component. Let $S,F$ be the strongly connected components containing $s,f$. There is a path from $s$ to $f$ if there is a path from $S$ to $F$ in the decomposition (this includes the case $S=F$). Any such path can only pass through (genuine) vertices in the connected components that appear on the path from $S$ to $F$ in the decomposition, and conversely we can arrange it to pass through all of them (since you allow the paths not to be simple). This leads to a simple criterion for your problem – can you state it?


Is my proof for a context free language correct? Same number of a's as b's

First of all, you've never said what exactly you are trying to prove. From the title, one might guess that you're trying to prove that the given grammar generates the language $L = \{ w \in (a+b)^* : \#_a(w) = \#_b(w) \}$. However, it seems that you are only trying to prove that every word generated by the grammar is in $L$. (The other direction is even harder.)

In order to prove your claim, you strengthen the claim, trying to prove the following:

If $S$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = \#_b(w) = m$.
If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = m + 1$ and $\#_b(w) = m$.
If $A$ generates $w$ then for some $m \in \mathbb{N}$, $\#_a(w) = m$ and $\#_b(w) = m + 1$.

In order to prove the strengthened claim, you need to prove by induction some claim $P(m)$. However, you never state what $P(m)$ is. Your "inductive hypothesis" is actually the statement that you're trying to prove by induction. One way to interpret your inductive hypothesis is the following: $P(m)$ states that

If $S$ generates $w$ then $\#_a(w) = \#_b(w) = m$.
If $A$ generates $w$ then $\#_a(w) = m + 1$ and $\#_b(w) = m$.
If $A$ generates $w$ then $\#_a(w) = m$ and $\#_b(w) = m + 1$.

However, this is simply false. You need to come up with a predicate $P(m)$ that you could prove by induction. Once you've done that, you can check whether your proof works.

The rest of your proof contains several other problems, but let's start with the more major problems mentioned above.


Basically from what I understood, it would be something like this....
In the quantization graph, we usually see a wave and the corresponding amplitudes marked at the axes and all those amplitude values are equally spaced from each other.
But according to tapered quantization, the constantly repeating values of the amplitudes will follow a finely spaced pattern in the plotter but with the values that appear rarely, those amplitude points/ values would face an non-equal pattern in between them(they would be marked or placed far away from each other).


If the CPU (Central Processing Unit) does any processing, it will do either Arithmetic or Logic operations... in a sense, some form of ALU is the core of the CPU.


How can computer memory remember after the computer runs out of battery?

There’s permanent storage that doesn’t need any power and lasts forever.
Your computer likely has a tiny battery for important things like clock time which should last for a very long time.
Your computer probably has code that dumps all memory contents to permanent storage just before the battery runs out and reads it back when there is enough battery life.


Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $

$RE$ and $co-RE$ are sets of sets of strings. $H_{TM}$ and $\overline{A_{TM}}$ are sets of strings. You correctly have that $H_{TM}\in RE$ and $\overline{A_{TM}}\in co-RE$. However, you cannot then conclude that
$$
H_{TM}\cap\overline{A_{TM}}\in RE\cap co-RE
$$
For a simple example, let
$$
A=\{\{1\},\{2\}, \{1, 3\}, \{2, 3\}\}\text{ and }B=\{\{1\},\{3\}, \{1, 2\}, \{2, 3\}\}
$$
So $A$ will serve as $RE$ and $B$ will serve as $co-RE$. Then we have $A\cap B=\{\{1\},\{2,3\}\}$. Now let $x=\{1,3\}\in A$ and $y=\{2,3\}\in B$ (here $x$ serves as $H_{TM}$ and $y$ serves as $\overline{A_{TM}}$). Then $x\cap y=\{3\}\notin A\cap B$.


I don't see any optimisation problem, no need for any greedy algorithm, nothing.

You described the behaviour of the elevator. All you need to do is to simulate that behaviour and count the number of movements.


Does the space complexity of a recursive algorithm depend on the total no of recursive calls?

Yes, that's right.

The statement "space complexity is $f(n)$" means that, if we had only $f(n)$ memory and no more, it would still be possible to run the algorithm.

As an example, say we are generating all permutations of length $n$ recursively.
Then we make $c_1 \cdot n!$ recursive calls but, at every moment, use at most $c_2 \cdot n$ memory.
A hypothetical machine with $c_2 \cdot n$ memory, and no more, would still run the algorithm correctly.

The space complexity depends on the structure of recursive calls, not simply on their number.


Negative Numbers in 32 bit Floating Point IEEE Numbers

Contrary to two's complement representation of negative integers, the negative numbers in IEEE floating-point are represented with only a sign bit change, as shown in there.
For example, $0\cdot01111100\cdot01000000000000000000000$ is the representation of $0.15625$, and $1\cdot01111100\cdot01000000000000000000000$ is the representation of $-0.15625$.
In particular, there are two representations of zero (the positive one and the negative one).


Do not get confused by the word "predicate". It is actually quite common to show that a function is primitive recursive by using another function for which we already know that it is primitive recursive in its definition.

For example, in the proof that multiplication is primitive recursive one usually defines multiplication using addition, which is not a basic primitive recursive function.

If "predicate" confuses you check out its definition, e.g., wikipedia. It is just a function $f: \mathbb{N} \rightarrow \{0,1\}$. So you can use a primitive recursive predicate just as a primitive recursive function of that kind.

All you need to show is, as mentioned in the comments, that the bounded quantification is primitive recursive.


quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$?

No, $\log_4 n$ is not the same as $\log_2 n$. $\log_4$ is exactly $\frac{\log_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log_4 n) = O(\log_2 n)$. But at this point they aren't computing the complexity (yet). They are doing "exact" math. If you have an array with $n$ elements and you always divide it by $4$, it will take exactly $\lceil\log_4 n \rceil$ iterations until you reach the size $1$, and not $\lceil \log_2 n \rceil$.

One more thing. They don't proof, that the average runtime is $\Theta(n \lg n)$. Because the array will obviously not always split with a ratio of 1:3. They only give you some intuition, why the complexity makes sence. Like they mention in the article:

  Showing that the average-case running time is also $\Theta(n \lg n)$
  takes some pretty involved mathematics, and so we won't
  go there.


Interval Scheduling Problem with Three Resources

The greedy scheduling with a first fit resource selection is actually not correct.
Consider the case where the intervals are:

${ (1, 3) , (2, 5) , (6, 7) , (4, 8) }$,

for simplicity assume we only have 2 resources. The greedy algorithm will assign intervals 1, 2, 3 to resources 1, 2, 1 respectively and will fail to assign a resource for the last interval. Although, a more optimal assignment would have been assigning all 4 of them 1, 2, 2, 1 in the following order.

So another greedy choice has to be made which is the selection of the resource to host the interval. The greedy choice would be selecting the compatible resource with the latest finish time. That way resources which are good (i.e. support more intervals) are kept free.

Intuition to the correctness of the algorithm:

There are 2 claims:
1) Intervals with early finishing time are always better to schedule first.

This is proven by an exchange argument, assume we would leave an interval with early finish time unscheduled to take a later interval, future intervals will definitely have a harder job finding a free room.

2) When an interval is compatible, it is always better to select the worst compatible room.

Since by claim 1, the interval will be taken anyway, the state of the rooms will have a room with $nextFreeTime = endTime_{cur}$ leaving 2 rooms with their previous $nextFreeTime$. Selecting the room with a larger $nextFreeTime$ will leave the better rooms for worse intervals.

Note: The problem can be solved with a less efficient but more obviously correct algorithm using a 3D dynamic programming approach. The state of the dp would indicate the last taken resource in each of the rooms, and the transitions are for each current interval, try selecting all of the compatible rooms updating their states. The intervals are still taken in order of finish time (Claim 1 still holds). The complexity becomes $O(n^3)$, however this is not scalable for k resources unlike the greedy algorithm.


Every single-exponential (i.e. known to be solvable in $O(c^n)$ for some constant $c$) EXPTIME-complete problem will answer your requirements.

For example, see checking thorough rerefinement on finite modal transition systems.


An instance of (the decision version of) vertex cover is a pair $\langle G, k \rangle$ where $G = (V,E)$ is a graph and $k$ is an integer. The problem is that of deciding whether $\exists S \subseteq V$ such that $|S| \le k$ and $\forall (u,v) \in E, \; \{u,v\} \cap S \neq \emptyset$.

Let $v_1, \dots, v_n$, be the vertices of $V$, in an arbitrary order.

You can see that vertex cover is a special case of set-cover. Indeed, it suffices to define $U=E$, $S_i = \{u \in V  : (v_i, u) \in E \}$ for $i=1,\dots,n$, and $K = k$.

If there is a set-cover $C$ of size at most $K$, then for each element $e = (v_i, v_j) \in U = E$ at least one of $V_i$ and $V_j$ is in $C$ (since these are the only two sets that contain $e$). This means that $S = \{v_h : V_h \in C \}$ is a vertex-cover for $G$ of size $|S| = |C| \le K = k$.

If there is a vertex cover $S$ of size at most $k$ for $G$, then for each edge $e = (v_i, v_j) \in E = U$,  $\exists v_k \in \{v_i, v_j\} \cap S$. This means that $V_k \ni e$ is in the set $C = \{ V_h : v_h \in S \}$ and hence $C$ is a set-cover of size $|C|=|S| \le k=K$.


Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$

The logic behind $(11+\epsilon)$ is to either allow a $11$, or allow no such pairs. The question states "[...] containing at most one pair [...]", and therefore we need to allow either one or zero pairs, and this is achieved by $(11+\epsilon)$.


Reducing 3-colouring to planar 3-colouring

The idea is simple. Given an arbitrary graph embedded in the plane, what might make it non-planar is that edges could cross. By slightly perturbing the planar embedding (where we put the vertices), we can ensure that no more than two edges meet at a point.

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x_1,x_2$ and a vertical pair $v_1,v_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$, and vice versa, for each choice of $c(x_1) = c(x_2)$ and $c(v_1) = c(v_2)$ there is such a coloring.

How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x_1 = a$ and $v_1 = r$. The gadget ensures that $c(x_2) = c(a)$ and $c(v_2) = c(r)$, so if we connect $x_2$ to $b$ and $v_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.

The general case is more complicated but of the same spirit, and you can read about it in the proof. The idea is to replace each crossing with a copy of the gadget; two adjacent crossings on the same edge share vertices, as illustrated on page 124 of the lecture notes.

The difficult part in coming up with this reduction is constructing the gadget. The idea itself is pretty natural, and it is somewhat surprising that it can be made to work.


Differences between the OS and DB buffer pool?

Yes, absolutely, that could happen, and it makes it harder for databases to optimize their own performance.

Some databases bypass the operating system's virtual memory management and manage memory themselves.  They might request that the operating system pin a range of the address space into memory (and never page it out).  Or, they might be designed to be the only application that runs on the machine, and take care of their own memory management so they never use too much memory -- hoping that this will make it unlikely that the OS ever pages out any of their data.


Well you have a little problem between your hands. The problem is that creating a DFA that generates some language $L$ have more than one solution. In fact if $L$ is regular then it have infinite solutions. If you are searching a book with answers it may not be usefull because your answer can be correct even though it is different from the one in the book.

There is some methods to prove the correctness of a DFA using proof by induction but it is fairly difficult. If you are having problems generating DFA I wouldn't reccommend to try proving the correctness until you are more experienced into this topic.

My teacher told me that the best you can do to be sure that your DFA is correct(when you skipping the proof of correctness) is do it in a sistematic way and understandable for anyone that reads it.


Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

We will use Burnside's lemma, plus some additional optimizations.

Note that row swaps and column swaps commute, so the group of allowable transformations to the grid is exactly $G = S_w \times S_h$, where $S_n$ is the symmetric group on $n$ symbols.  Note that $G$ embeds in $S_{wh}$ via a canonical embedding $\varphi : G \to S_{wh}$, given by $\varphi(\pi,\sigma) = \tau$ where $\tau$ is defined by $\tau(i,j) = (\pi(i), \sigma(j))$.  Therefore, we will think of $G$ simultaneously as the direct product $S_w \times S_h$ and also as a subgroup of $S_{wh}$.

Now let's count the number of grids that are fixed by a group element $g=(\pi,\sigma) \in G$.  Define the cycle type of a permutation $\pi$ to be the multiset of lengths of the cycles in the cycle decomposition of $\pi$.  If $\pi \in S_n$, the cycle type of $\pi$ is a partition of $n$.  With this in mind, we will let $\ell(\pi)$ denote the cycle type of $\pi \in S_w$ and $\ell(\sigma)$ the cycle type of $\sigma \in S_h$.  Finally, let $\ell((\pi,\sigma))$ denote the cycle type of $(\pi,\sigma)$, thinking of $(\pi,\sigma)$ as an element of $S_{wh}$.  We can express $\ell((\pi,\sigma))$ in terms of $\ell(\pi)$ and $\ell(\sigma)$: let $x,y$ range over $x \in \ell(\pi), y \in \ell(\sigma)$, and for each $x,y$, $\ell((\pi,\sigma))$ has $\gcd(x,y)$ copies of $\operatorname{lcm}(x,y)$.

Now the number of grids that are fixed by $(\pi,\sigma)$ is

$$f(\pi,\sigma) = k^{|\ell(\pi,\sigma)|},$$

where $|\ell(\pi,\sigma)|$ counts the number of cycles in $(\pi,\sigma) \in G$ (multiplicities are counted).  By the above characterization of $\ell(\pi,\sigma)$, we see that

$$f(\pi,\sigma) = k^{\sum_{x \in \ell(\pi)} \sum_{y \in \ell(\sigma)} \gcd(x,y)}.$$

To apply Burnside's lemma, it remains to sum $f(g)$ over all elements $g \in G$, as Burnside's lemma tells us that the total number of non-equivalent grids is

$$N = {1 \over |G|} \sum_{g \in G} f(g) = {1 \over w! h!} \sum_{g \in G} f(g).$$

In principle, we could compute this sum by enumerating all $w! h!$ elements in $G$, then evaluating $f$ on each, and summing the result.

It turns out this can be optimized further, as $f((\pi,\sigma))$ depends only on $\ell(\pi)$ and $\ell(\sigma)$, but not on any other aspect of $\pi$ or $\sigma$.  Thus, we can more efficiently evaluate the sum using the formula

$$\sum_{g \in G} f(g) = \sum_{P,Q} n(P,Q) \times k^{\sum_{x \in P} \sum_{y \in Q} \gcd(x,y)},$$

where the inner sum ranges over all partitions $P$ of $w$ and all partitions $Q$ of $h$, and where we define

$$n(P,Q) = |\{(\pi,\sigma) \in G : \ell(\pi)=P, \ell(\sigma)=Q\}|$$

to count the number of group elements of $G$ whose cycle types are $P,Q$.  Now we have

$$n(P,Q) = n_w(P) \times n_h(Q),$$

where $n_w(P) = |\{\pi \in S_w : \ell(\pi)=P\}|$ is the number of permutations in $S_w$ with cycle type $P$, and similarly $n_h(Q)$ is the number of permutations in $S_h$ with cycle type $Q$.  Finally, it is easy to compute $n_w(P)$ for any desired partition $P$; it is

$$n_w(P) = {w! \over \prod_{x \in P} x}.$$

Plugging in, we find that the total number of non-equivalent grids is given by

$$N = \sum_{P,Q} {k^{\sum_{x \in P} \sum_{y \in Q} \gcd(x,y)} \over \prod_{x \in P} x \prod_{y \in Q} y}.$$

This can be computed by two nested for-loops that iterate over all partitions $P$ of $w$ and all partitions $Q$ of $h$.

What is the running time of this algorithm?  The  asymptotic running time is approximately $O(p(w) p(h))$, where $p(n)$ is the number of partitions of the integer $n$.  It is known that asymptotically $p(n) = O(\exp\{\pi \sqrt{2n/3} \})$, so it follows that the asymptotic running time of this algorithm is approximately $O(\exp\{\pi \sqrt{2/3} (\sqrt{w}+\sqrt{h})\})$, or equivalently, approximately $O(2^{3.7(\sqrt{w}+\sqrt{h})})$.  This should allow you to handle the full range of values $1 \le w,h \le 12$, as for that range we have $\sqrt{w}+\sqrt{h} < 7$ and $2^{3.7 \times 7} \approx 2^{26}$ is not too large.


Single-tape Turing Machines with write-protected input recognize only Regular Languages

Introduction

I thought there might be an error in the original statement of the question,
and the OP was no longer around to ask. So I assumed that the tape was
read-only everywhere, and wrote a first proof based on that
assumption, motivated by the fact that the TM has full Turing power
outside the input part of the tape if it can write it, which induces the false belief
that it can recognize any RE language.

However, that is not the case: the restriction on writing on the input
part of the tape implies that only finite information can be extracted
from the input, limited by the number of states on entry and exit of
that part of the tape (combined with side of entry and exit). InstructedA is to be credited for remarking in a comment that there is a problem with recognizing any RE language, since it is not possible to make a copy of the input without EVER writing to the original input area,

Hence I wrote a second proof that assumes that only the input section
of the tape is read-only, the rest being read-write allowed.

I am keeping both proofs here, as the first did help me find the
solution, even though it is not necessary to understand the second
proof, is more complex, and is subsumed by the second proof. It can be
skipped. However, the weaker proof has the advantage of being constructive
(to obtain a FSA equivalent to the Turing Machine), while the more general result is not constructive.

However I am giving first the last and more powerful result. I am a bit surprised that I was not able to find this result, even without proof, elsewhere on the net, or by asking some competent users, and any reference to published work would be welcome.

Contents:

Turing machines that do not overwrite input accept only regular languages.
This proof is not constructive.
Turing machines with read-only tapes accept only regular languages.
It may be skipped as subsumed by previous proof, but it uses a different approach, which has the advantage of being constructive.

Turing machines that do not overwrite input accept only regular languages

We recall that, while the TM does not overwrite its input, and is thus
read only on its input, the TM can read and write on the rest of the
tape. The proof relies on the fact that the observational behavior of
the TM over an unlnown input can produce only a finite number of
different cases. Hence, though the TM has full Turing power just by
relying on the rest of its tape, its information on the input, which
can be any string in $\Sigma^*$, is finite, so it can compute only on a
finite number of different cases. This gives a different view of the
finite character of regular languages, behavioral rather than
structural.

We assume that the TM accepts when it enters an accept state.

Proof.

We define an input restricted computations (IRC) as a (read-only)
computation of the TM such that the TM head stays on the input part of
the tape, except possibly for the last transition that may move it to
a cell immediately at the left or the right of the input area.

A left input restricted computations is an IRC that starts on the
leftmost symbol of the input. A right input restricted
computations is an IRC that starts on the rightmost symbol of the
input.

We first prove that, for left input
restricted computations that start in state $p$, the following
languages are regular:

the language $K_{Lp\to Lq}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that ends on the first cell left of the
leftmost input symbol in state $q$;
the language $K_{Lp\to Rq}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that ends on the first cell right of the
rightmost input symbol in state $q$;
the language $A_{Lp}$ of input strings such that there is a left input
restricted computation, starting in state $p$, that reaches an accept
state.

And similarly, for right input restricted computations starting in
state $p$, the following similarly defined languages are regular:
$K_{Rp\to Lq}$, $K_{Rp\to Rq}$, and $A_{Rp}$.

The 6 proofs rely on the fact that two-ways non-deterministic finite
state automata (2NFA) recognize regular sets (see Hopcroft+Ullman
1979, pp 36-41, and execise 2.18 page 51). A 2NFA works like a
read-only TM on a tape limited to its input, starting initially from
the leftmost symbol, and accepting by moving beyond the right end in
an accepting state.

In each of the 6 cases, the proof is done by building a 2NFA that
mimics the input restricted computations, but with some extra
transitions to make sure it can start from the leftmost cell and
accept the language by exiting from the rightmost end in an accepting
state. For the $K_{??\to ??}$ languages, the original accepting state
of the TM are changed into states leading to a halting non-accepting
computation. In two cases, it may be necessary to add an extra cell
with a new guard symbol on the left to detect TM computations that
would terminate on the left end, so as to make them terminate on the
right end.

These languages are defined for all combinations of states $p$
and $q$ of the original Turing machine. They represent all that can be
observed (hence known and computed on) of the input by the TM.

If $k$ is the number of states, we thus define $4k^2$ languages
$K_{??\to ??}$ and $2k$ languages $A_{??}$, hence a total of $4k^2+2k$
languages. Actually, some of these languages can be equal.

These are the only possible input restricted computations of the TM
starting on one end of the input. Hence the computations induced by each input string (outside the input section of the tape) are
characterised by the set of such languages the input belongs or does not belong to, hence by an
intersection of each of these $4k^2+2k$ languages or its complement in $\Sigma^*$. All these intersections are finite intersections of r$4k^2+2k$ regular languages, or their complement which are also regular, and are therefore regular.

As a consequence, the set of these intersections defines a partition
$\mathcal P$ of $\Sigma^*$ into at most $2^{4k^2+2k}$ regular languages
(at most because some initial languages may be equal, and some
intersections may be too). All strings belonging to the same
equivalence class can produce exactly the same behavior, as seen from
the ends of the input. This implies that they cannot be distinguished
for computation of the Turing Machine, if you abstract away what
happens in the read-only input area.

If we take two strings $u$ and $v$ in the same equivalence class of
$\mathcal P$ , we can prove, by induction on the number of times the
input area is entered, that for any accepting computation of the TM on $u$,
there is an accepting TM computation on $v$ that is identical everywhere outside
the input area. Hence, either all strings of an equivalence class are
accepted, or none is. As a consequence, the language accepted by the
TM is a union of equivalence classes of $\mathcal P$. Hence it is a
finite union of regular languages, and thus it is a regular language.

To be very complete, we skipped the case of the empty input
string. In this case, we just have a normal TM, that can read or write
anywhere. If it reaches an accepting state, the empty string is in
the language, else it is not.  But that has little effect on the fact
that the language recognized is regular.

Of course, it is not decidable whether an equivalence class is or is
not in the language (the same holds for the empty string). This is a
non constructive proof.

QED

Turing machines with read-only tapes accept only regular languages

This is subsumed by the previous result. It is kept as it uses a different approach, probably less elegant, and helped me in finding the previous proof by understanding what matters. But it can well be skipped by readers. However, one advantage of this proof is that it is a constructive proof producing a FSA accepting the language. A sketch of a similar proof is given by Hendrik Jan in his answer to a previous similar question, which assumes the whole tape was read-only.

I assume that the blank symbol that is on the unused part of the tape
is never part of the input. This symbol is noted here $\Box$. The TM
is supposed to accept when it reaches an accepting state.

The first step of the proof is to show that the head need not ever
leave the input area of the tape. We thus analyze what happen when the
head moves off the rightmost input symbol. The analysis when moving
off the leftmost one is identical.

If we consider that the head has moved on the first blank cell on the
right of the input, the TM being in state $q$, we have to understand
what can happen. There are actually three cases, that may be
simultaneously possible when the TM is non-deterministic:

the TM keeps computing for ever, without the head ever coming coming
back on the input part of the tape;
the TM reaches an (a) accepting or (b) stops in a non-accepting state;
the TM head ultimately comes back on the rightmost cell of the
input,  the finite control being in state $r$.

So we have to analyze the behavior of the TM finite control, when
computing on a blank half-tape, starting in state $q$ on the leftmost
cell of a blank half-tape, infinite towards the right.

Since the TM does not write, and reads only the blank symbol $\Box$,
all the finite control can do is move left or right, and
configurations are differentiated only by the position of the head,
i.e. by an integer. The tape can be replaced by a counter, starting at
$1$, that is incremented when the head moves right and decremented
when it moves left, provided we consider only transitions that require
the blank symbol on the tape. If the counter goes down to $0$, that
correspond to a case of the head coming back on the rightmost input
symbol.

A first remark is that we can ignore computations that do not
terminate (case 1) or that terminate with rejection (case 2.b) since
termination with acceptance is the only relevant case for accepting a
string. So we only want to know whether the counter can go down to
$0$, and in what state, or whether the computation can reach an
accepting state.

We represent the relevant part of the finite state control by a
directed graph where the vertices are the states of the TM, and where
the edges are the blank transitions, with a weight +1 or -1 depending
on whether the head is supposed to move right or left.

We define $A_R$ the set of state $q$ from which an accepting state
can be reached with a positive weighted path.

We also compute the set $E_R$ of all pairs $(q,r)$ of states such that
there is a path of weight $-1$ from $q$ to $r$, but no prefix of that
path has a negative weight.

Then we modify the finite state control of the TM as follow (ignoring now
all transitions on blank symbol $\Box$):

We create a new accepting state $q_A$ with no transitions.

For every transition  $p,a\mapsto R,q$ you add a transition
$p,a\mapsto R,q_A$ if $q\in A_R$ (i.e. an acceptance is possible if
you are on the rightmost symbol).

For every transition $p,a\mapsto R,q$, and every pair $(q,r)\in E_R$
you add a dummy-transition $p,a\mapsto S,r$, where $S$ indicates that
the head should not move. Since this is not an allowed move with most
automata formalizations, these dummy states can be eliminated by
transitive closure afterwards.

Once this is completed, we proceed to remove the dummy
transitions. For every tape symbol $a$, we build the set
$F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto
S,r\}$, and we consider the transitive closure $F_a^*$ of the relation
defined by $F_a$. Then, for every transition $r,a\mapsto L,s$ of the
original TM, and every pair $(p,r)\in F_a^*$, we add a new transition
$p,a\mapsto L,s$. Then all dummy transitions can be removed.

We proceed similarly for the moves of the head left of the input part
of the tape, thus reversing left and right, and exchanging $+1$ and
$-1$  in the graph weights.

Once this has been done, we remove completely all transitions on blank
cells, since the corresponding computation are short-circuited by the
new transitions. And we now have a new TM with a head that stays on the
input all the time, except when accepting with state $q_A$, and still
recognizes the original language.

We now have to do a few cosmetic changes, so as to make this TM behave
exactly like a two-ways NDA (acceptance is only by exiting the input
on the right into an eccpting state). Then we can rely on the on the
know equivalence between 2-NDA and FSA (see for example Hopcroft+Ullman 1979, page 40) to obtain the proof that the
language is regular.

QED


In short: no, it doesn't follow from the claims you mention that this algorithm is a verifier in a meaningful use of the term.

The paper states:

  Our attempt here is to obtain a polynomial-time algorithm for
  computing these tables that is sufficient but not necessary,
  in the following sense. Our algorithm will not be able to
  generate the scheduling tables for all TT-schedulable instances;
  however, if the algorithm does generate scheduling tables for
  an instance, then these tables are correct.

So, they claim to have a polynomial time algorithm that can provide a solution for a subset of all problem instances, but there are some cases for which this algorithm fails to provide a correct solution. Furthermore, they claim elsewhere that there is some characterization of this subset.

By contrast, a polynomial time verifier for a certain problem $X$ is an algorithm, that given an problem instance $I$ of $X$ and a certificate $C$, can prove whether the instance is a YES-instance or not in polynomial time. Usually, the certificate corresponds to some 'solution' that the verifier needs to verify correctness for.

So, the algorithm in this paper can be called a polynomial time verifier algorithm for the subset it solves in polynomial time only, as a polynomial algorithm that solves a problem is also a verifier. But, the claim that this algorithm is a verifier in this sense isn't useful, as it is a strictly weaker property (at least, if $P\neq NP$ ) than being an actual algorithm for the solution.


If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

I'm guessing you are talking about Myhill-Nerode classes.

We can view $L$ as a subset of $\mathbb N$, since only the length of the word is important on $\{a\}$. Moreover two numbers $i,j$ are equivalent iff for any $n$, $i+n\in L$ iff $j+n\in L$.
Assume there are $i<j$ equivalent, and let $k=j-i$. Then for any $n$, we have $n\in L$ iff $n \bmod k\in L$, since you can replace $j$ by $i$ as many times as you want. This means $L$ is regular, because it depends only of the congruence classes modulo $k$.

So the answer to your question is Yes: if $L$ is nonregular, all classes are singletons.


The thing you need to remember is that even if Σ has only one symbol , Σ* still has infinite strings over that one symbol , even if Σ = {a} , Σ* = {ε,a,aa,aaa,....} , (a^n , n≥ 0) , Σ* has infinite strings just like with any other alphabet , and so we can form infinite languages over an alphabet with a single symbol just like other alphabet , if now you are convinced that Σ* is infinite even if |Σ|=1  just like any other alphabet , then just as you believe that P(Σ*) for  |Σ| >1 is uncountably infinite , hopefully you can see now that P(Σ*) for |Σ| = 1 is also uncountably infinite , since in both cases it is P(some infinite language) , which in both cases is uncountably infinite


Omission of smaller variables in Big-O Complexity

Yes, you can.  Since $k \le n$, you have $n+k+m \le 2n+m = O(n+m)$.


There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file.

If you are allowed preprocessing, you can store the locations of all zeroes in a new file, and then choose a uniformly random zero in $O(1)$ by choosing a uniformly random position in the list.

Practically speaking, we expect bitmaps to contain a decent fraction of zeroes – say at least 1%. This suggests querying uniformly random locations in the file until you reach a zero. The expected runtime of this algorithm is at most 100 random queries.


Efficient Algorithm to compute radius of tree

Yes, it can be done in $O(n)$ time.

Rooted trees

First let me describe how to do it for a rooted tree.  We'll compute several quantities for each node $v$ in the tree:

Let $p(v)$ denote $v$'s parent.
Let $h(v)$ denote the height of $v$ (i.e., the distance from $v$ to its deepest descendant).  You can compute $h(v)$ for all nodes $v$ in $O(n)$ time via a simple recursive traversal.
Let $f(v)$ denote the length of the longest simple path that starts $v \to p(v) \to w \to \cdots$ such that $w$ is a sibling of $v$, i.e., $p(v)=p(w)$ and $v \ne w$.  In other words, it's the length of the longest path that starts from $v$ by going up once and then immediately going down.  Note that

$$f(v) = \max \{2+h(w) : p(w)=p(v), w \ne v\}.$$

Suppose we've computed $h(v)$ for all nodes $v$.  Also, suppose that for each node we keep track of its two children with the two largest $h(\cdot)$ values.  Then, we can compute $f(v)$ for each node $v$ easily.
Let $g(v)$ denote the length of the longest simple path that starts $v \to p(v) \to \cdots$.  In other words, it's the length of the longest path that starts by going up from $v$ (possibly several times).  Note that $g(v) = \max \{ f(p^i(v))+i : i \ge 0\}$ and moreover

$$g(v) = \max(f(v), g(p(v))+1).$$

Therefore, if you've computed $f(v)$ for all nodes $v$, you can easily compute $g(v)$ for all nodes via a simple recursive traversal.
Let $e(v)$ denote the eccentricity of node $v$, i.e., $e(v) = \max\{d(v,w) : w \in V\}$.  The eccentricity of a node $v$ is given by $e(v) = \max(h(v),g(v))$.

This gives us a way to label all the nodes with their eccentricity, in $O(n)$ time.  Then we simply find the node whose eccentricity is the smallest.  The algorithm runs in $O(n)$ time in all.

Unrooted trees

If we have an unrooted tree (as in the question), we can first turn it into a rooted tree (do a DFS; then the DFS tree will be a rooted version of the tree), then apply the previous algorithm.


On certificates in BPP (avoiding majority vote)

A randomized algorithm $A$ does not produce any sort of "certificate" in any useful sense. Even if $A$ is a correct BPP algorithm, all that you know by running $A$ once is that it gives this particular outcome on this particular set of coin tosses. How would you use this fact as a witness that the input is or is not in the language? A correct BPP algorithm may give the right or wrong answer on this particular run.

In contrast, a correct deterministic algorithm does give a certificate from only running it once because it will give the same (correct) answer every time. Whereas you would need to run $A$ on all possible coin tosses and concatenate these answers to get any sort of "proof" about the input.

Another approach to your question: you could also start from the fact that a problem is in NP and try to design a randomized algorithm that both solves it and produces witnesses when it does. Here, however, as Yuval says, the issue is that witnesses may be very unlikely to guess so we do not know how to do this in general. If we could show that a randomized polynomial-time algorithm can reliably guess witnesses when they exist, we will essentially have shown $NP \subseteq BPP$.


How does the double rotation in AVL tree work?

At the drawing is correct the brown variant. The purple isn't binary search tree (thanks, Hendrik Jan for this clarification) at all.
Why? Because it is not in the right order (for all nodes in a BST must be true, that all nodes in its right subtree have bigger value and all nodes in the left subtree have a smaller value than the node).

About the double rotation itself:
The problem was that I didn't know how to choose the correct vertex, the right answer is that you have to take the middle one as the root of the new subtree (11 from the set 10, 11, 14 on my drawing) and the rest must fit the rules for the binary search AVL trees.


Find maximum non contiguous subarray that respect a specific rule

I will move my comment to an answer, since you seemed to indicate that the comment solved your problem.

Your problem is normally called the Longest Common Subsequence problem. It does not require the common subsequence to be contiguous. It can be solved efficiently with dynamic programming, and it is an early example of dynamic programming in many textbooks.

There are many implementations of LCS available online. The wiki article on LCS I linked to in the above comment is a good place to start.


Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent?

The answer is no: this is not possible. I assume a horn formula is a CNF formula with at most one positive literal (=nonnegated variable) in each clause. Now, for the sake of contradiction, suppose we have a horn formula $\phi$ that is equisatisfiable to $p\vee q$. Since $\phi$ is a horn formula, each clause in it contains a negative literal OR there is a clause consisting of only one (positive) variable. If the latter is the case, that positive variable must be a helper variable, since if it were p, it would mean that p must be necessarily true for satisfaction, which is not the case in "$p\vee q$" (same argument for q). So in this case, we derive an equisatisfiable formula by replacing that variable with true. In this new formula, we have one less clause that contains only a positive variable. We repeat this process until this is no longer the case, until we have a formula that has a negative literal in each clause. But such a formula is satisfiable by setting every variable to false. However, that's not the case in $p\vee q$, hence the contradiction.


Another technique that may be suitable for your problem is backtracking. It is often used for solving puzzles such as 8 queens problem, sudoku, etc.


What is the difference between a function and a procedure

This is rather old distincion (from pascal - which is the most recognisable for this - see vonbrand's answer).
Function returns value, procedure does not.
This is only naming convention, the more common is just calling the both function, and if needed say that one does not return value.
Some programming languages always return value (like the last statement is sent) or get returning cell on stack and does not use it.
Other languages explicitly return empty value, so still you can assign it to variable, so there is no point of this distinction.


Given max-flow determine if edge is in a min-cut

Will not find A-E, B-C min-cut. Will find A-B, A-E and C-D. Graph does not show flow direction, but assume left to right (i.e. A->B, B->C, A->E, E->C and C->D)

    B
   / \
1 /   \ 1
 /     \   2
A       C --- D
 \     /
1 \   / 4
   \ /
    E


Multiple post-fix expressions for an in-fix expression

(A+b)-c and a+(b-c) are not the same. Not with integers (one expression might overflow while the other one doesn’t), not with floating-point numbers ( different rounding errors).

Only the second postfix expression is correct.


Is it always possible to have one part of the reduction?

If you define "reduction" using a single implication as in $x\in A \implies f(x) \in B$, then $A$ indeed always "reduces" to any nonempty $B$. Take any $b\in B$, and define $f(x)=b$ the be a constant function. This is computable in O(1), hence in polytime.

It does not matter if $B$ is decidable, or in P, or anything else -- as long as it is not empty, that's enough.

1) No, it does not prove anything. If you have that $A$ reduces to a PTIME $B$ with your proposed reduction, you can't conclude $A$ is PTIME. $HALT$ would reduce to checking if a number is $12$ (which is PTIME), but $HALT$ is surely not PTIME.

2) $f$ above is constant, hence always decidable. (There is no such a thing as a semicomputable function)

3) Similarly, the converse implication is satisfied, for any $A$ and non-full $B$, if we take the constant function $f(x)=b \notin B$.

Below, I consider the more standard definition of reduction with the double implication.

The halting problem is not reducible (polytime or not) to its complement, nor its complement is reducible to the halting problem.

This is because $A\leq B$ holds iff $\bar A \leq \bar B$, hence in either case the complement of $HALT$ would reduce to $HALT$, but the first is not recursively enumerable, and the second is, so we get a contradiction.

For the others:

1) Yes. The reverse direction is trivial, since if $B\in P$ then $B\in NP$ hence it reduces to 3SAT.

2) The $HALT$ counterexample above holds for any computable $f$. There is no such a thing as a semicomputable function -- semidecidability only applies to problems.


Showing a partition-like problem is NP-complete

I'm going to make a few guesses as to what you precisely mean, and if they're correct, we can edit the question so everything is clearer. First I'll define what I think you mean with your problem:

  Input: A set of positive integers $A=\{a_{1}, \ldots, a_{n}\}$.
  Question: Is there a set of integers $P = \{p_{1}, \ldots, p_{n}\}$ such that for each $i$  the absolute value of $p_{i}$ equals $a_{i}$ (i.e. $|p_{i}| = a_{i}$) and the sum of the elements of $P$ is zero (i.e. $\sum_{i=1}^{n}p_{i} = 0$)?

Clearly what we want to do is flip the sign on some of the $a_{i}$s and make them negative (or rather $p_{i} = -a_{i}$). Then the question is whether this problem is NP-complete.

Of course the answer is yes, we just need to identify a suitable problem for the reduction. In this case, there's a very simple reduction from the Partition problem:

  Partition
  Input: A set of positive integers $S=\{s_{1},\ldots,s_{n}\}$.
  Question: Is there a partition of $S$ into two disjoint subsets $S_{1}$ and $S_{2}$ such that $S = S_{1} \cup S_{2}$ and $\sum S_{1} = \sum S_{2}$?

The reduction should be pretty clear from here.

Let $S$ be the input to the Partition instance, then we construct an input set $A$ for the new problem by simply setting $A := S$.

Now we just have to show that $S$ is a Yes-instance for Partition if and only if $A$ is a Yes-instance for the new problem.

Assume $S$ is a Yes-instance for Partition, then there are two sets $S_{1}$ and $S_{2}$ that partition $S$ as described, and importantly have the same sum, then in $P$ we can set the elements corresponding to elements of $S_{2}$ to be negative, and we have a solution for the new problem ($P$ is really just $S$ in disguise, now with some signs flipped to negative).

Now assume $A$ is a Yes-instance for the new problem, then there exists a $P$ which is $A$, but with some elements now negative. Then there is some set $P' \subset P$ whose elements are negative and with a little thought we can see that as $\sum P = 0$ hence $\sum (P\setminus P') + \sum P' = 0$. Therefore, more precisely, $\sum_{p \in P\setminus P'} p = \sum_{q \in P'}|q|$. Obviously if then go back to looking at $A$ (which is just $S$ recall), we have a partition suitable for a solution to the Partition instance.

So we have that Partition $\leq_{m}$ "the new problem", which tells us that the new problem is NP-hard. The very last bit is to show that the new problem is in NP, and hence NP-complete. This is of course simple, as all we have to do is observe that we can check a solution in polynomial-time just by:

Adding up $P$ and checking the sum is zero, and
Checking that each element $p_{i}$ is $\pm a_{i}$.

So, now that I've gone a bit overboard, did I guess the details correctly?


Looking for memory-efficient way to detect hash collisions

Assume you have a good hash function producing an n bit hash code, that is $2^n$ possible values. Assume you are hashing k values, so there are about $k^2/2$ pairs of hash codes that might collide. The probability of a collision is about $k^2 / 2^{n+1}$.
By picking a large n, you can make that probability arbitrarily small. Ask a physicist to calculate the probability that your computer will be hit by a meteor and completely destroyed, together with all hash values. Pick n large enough that the probability of a collission is say 1,000 times smaller than the probability of a total destruction of the computer involved.
You might also consider what is the amount of damage if you have a collission. For example, the damage could be that as a result, there will be one person in the world who can enter your country with the passport of one specific other person. Make n large enough so that the expect damage through a collision is negligible.
(That's the principle behind the use of GUIDs. There is no guarantee that there are no collisions, but with a proper implementation the probability can be neglected. )


What is the Code2 and other concepts of variable encoding in Coding Redundancy?

In the first column, $r_k$ is the gray level. It ranges from 0 to 1, where 0 is 0% white (i.e., black) and 1 is 100% white. There are 8 gray levels arranged in regular intervals of 1/7.

Code 1 and Code 2 are two different ways of encoding the gray level. Code 1 is a fixed-length code (all codewords have the same length) whereas Code 2 is a variable-length code, specifically a prefix code, presumably a Huffman code for the distribution in the second column. Code 2 is better because the expected codeword length is 2.7 bits, which is smaller than the 3 bits that you get with Code 1.

Since Code 2 is a prefix code, decoding it is actually very simple, and requires no lookahead. (That's why prefix codes are sometimes called instantaneous codes.)


Algorithm for checking if a list of integers is pairwise coprime

First, two facts about coprime integers:

Iff $a$ and $b$ are coprime, then $ab = \mathrm{lcm}(a,b)$
Iff $a$ is coprime to both $b$ and $c$, then $a$ is coprime to $bc$

It follows from this that a set of distinct integers $\{a, b, \cdots z\}$ is pairwise coprime if its product is equal to its least common multiple.

You can compute the least common multiple by using the following identity:

$$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$$

Assuming you have $n$ numbers with $k$ digits each, and multiplying/dividing/modding two numbers is $O(1)$ (which may or may not be a good assumption depending on your model), then:

Calculating the product of your set takes $O(n)$
Calculating the gcd of two numbers takes $O(k)$
Calculating the lcm of two numbers thus also takes $O(k)$, by reduction to gcd
So calculating the lcm of your entire set takes $O(nk)$

Thus, the time complexity of the entire algorithm is $O(nk)$.


Crafting a dataset to train a NN that recognizes image styles

You have to know how to read these papers, and set your expectations low.  The prior ability to do anything of this sort was so low that any advance, even a highly imperfect one, is exciting and unexpected.

It's like one of those animal trick shows, where the cute dog sits in front of the piano and plays Happy Birthday on it.  You're not expecting Beethoven's Moonlight Sonata or mastery-level playing.  It would be churlish to complain that the piece was overly simplistic, the playing lacked expression, and halfway through, the dog got distracted and started chasing his tail and never finished playing.  Come on, it's a piano-playing puppy!  How often do you see that?

Same deal here.  It's probably not really fully capturing "style" as a human would consider it.

Don't think of this as transforming an image to make it look like it was painted by some specific painter or artist.  It's not going to take my cellphone-snap of a tree in my backyard and make it look like an Ansel Adams composition.  Don't think of this as learning the style and idiosyncracies of a particular painter.  Don't even think of this as learning "style" as humans would consider it.

Rather, what they do is propose a technical transformation to an image, and then they look at its effect on some examples and -- woah -- the effect is pretty cool!  In some cases it comes surprisingly close to mimicking some aspects of human style.  It's not wonderful, but hey, it's more than one would otherwise expect.

At a technical level, they identify some particular attribute or property of an image that they can compute: if $I$ is an image, let $f(I)$ denote the value of this attribute.  Then, given an image $I_1$ and an image $I_2$, they show how to modify $I_2$ to get a new image $I'_2$ such that $f(I'_2)$ is similar to $f(I_1)$.  They look at some examples and empirically find that (a) $I'_2$ often seems to have "similar visual content" to $I_2$, and (b) $I'_2$ often seems to have captured some of the aspects of "artistic style" of $I_1$ (it seems to have a similar "style" as $I_1$), in some vague sense.

Based on this, they decide to call $f(I)$ the "style" of $I$.  That's probably playing a bit fast and loose with naming, as I suspect $f(I)$ falls far short of always capturing all of the elements of artistic style as a human would judge it.

At a technical level, $f(I)$ is computed by computing some kind of correlation matrix on the responses of internal layers of a particular neural network when applied to image $I$... or something like that.  The details don't matter so much, as the fact that empirically their transformation provides results that are interesting and unexpected.

And that's why they don't require a large training set per artist: they don't try to capture anything specific to a single artist.  They're not doing what you seemed to expect them to be doing.  Also, the neural network was obtained by pre-training it on a dataset of millions of images, so it probably captures some kind of information about typical patterns that are seen in images.


Linear programing, objective function. variable depending on the sign of another variable

I think it's cleaner to define two variables that represent the positive and negative parts of Si. Call them Si1 (= positive part) and Si2 (= negative part).

Si1 - Si2 = Si
Si1, Si2 >= 0

Probably you will also need constraints that say that if Si < 0 then Si1 must equal 0, and if Si > 0 then Si2 must equal 0. Introduce an additional binary variable y that equals 1 if Si > 0, equals 0 if Si < 0, and could equal either if Si = 0:

-M * (1 - y) <= Si
 M * y >= Si

where M is a large constant.
Then require Si1 = 0 if y = 0 and Si2 = 0 if y = 1:

Si1 <= M * y
Si2 <= M * (1 - y)

Then set your objective function to minimize 100 * Si1 + 200 * Si2.

Note: If both Si1 and Si2 have positive coefficients in the objective function, and the objective is a minimization, then you do not need the stuff after the divider line. The two constraints before the line are sufficient, because we will always want to set Si1 and Si2 as small as possible, which means setting one of them to 0.


How can i prove this asymptotic comparison?

When it comes to instances like this, I prefer to think about conceptually "promoting" and "demoting" lower order terms.

For instance, if we wanted to upper bound:

$$f(n) = 32 + 11 \log_2 n + 5 n + 2 n^2$$

We know (by intuition or limits) that $n^2$ is the fastest growing term here. Thus, we should be able to bound $f(n)$ by $n^2$. By this, I mean we can find some constant $c$ such that $f(n) \leq c n^2$ for all $n \geq n_0$ (where $n_0$ is some initial starting value for $n$ where this inequality holds true). Note, that this is preciesly the definition of Big O.

  Promoting lower order terms of $f(n)$ - Consider we can represent each lower order term by a constant $c_0$ times some function $h_0$ of $n$ (e.g. $c_0 \cdot h_0(n) = 11 \cdot \log_2 n$). For each lower order term, we will promote $h_0(n)$ to the highest order function of $n$, call it $h^*(n)$ and leave the constant the same.

Consider the lower order terms of our example: $\{32,\ 11 \log_2 n,\ 5n\}$ and the highest order term $2 n^2$. The promotions will go as follows:

$$\begin{align*}
32 & \mapsto 32 \cdot n^2\\
11 \cdot \log_2 n & \mapsto 11 \cdot n^2\\
5 \cdot n & \mapsto 5 \cdot n^2
\end{align*}$$

Let's assume $n_0$ is the first value of $n$ for which all lower order functions of $n$ are less than or equal to the highest order function of $n$. In our example we have:

$$\begin{align*}
1 & \leq n^2 & \forall n \geq 1\\
\log_2 n & \leq n^2 & \forall n \geq 1\\
n & \leq n^2 & \forall n \geq 1
\end{align*}$$

Thus we have found our $n_0 = 1$. Now we can replace the lower order terms in $f(n)$ with their promoted counterparts to get:

$$\begin{align*}
f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\
& \leq 32 n^2 + 11 n^2 + 5 n^2 + 2n^2
& = 50 n^2
\end{align*}$$

With this he have found our $c = 50$. Thus we can conclude:

$$f(n) \leq 50 n^2 \quad \forall n \geq 1 \quad \implies f(n) = O(n^2)$$

  For demoting lower order terms we simply remove them from the equation to get:

$$\begin{align*}
f(n) & = 32 + 11 \log_2 n + 5 n + 2 n^2\\
& \geq 2n^2\\
&  = 2n^2
\end{align*}$$

Thus we can conclude:

$$f(n) \geq 2 n^2 \quad \forall n \geq 1 \quad \implies f(n) = \Omega(n^2)$$

Then we clearly get:

$$f(n) = O(n^2) \land f(n) = \Omega(n^2) \implies f(n) = \Theta(n^2)$$

Typically, most of these operations are simple enough to just conclude $f(n) = \Theta(n^2)$ in one fatal sweep, though it does always help to determine $c$ and $n_0$ explicitly when you need to. Clearly, the $c$ we find here is a loose upper bound and you could usually restrict it further if you needed to.

At this point I am assuming you have a summation of functions that are monotone non-decreasing. You must be a bit more careful when you have decreasing lower order terms, but these are usually not a big problem.


How to approach Dynamic graph related problems

It's hard to give you concrete techniques because "dynamic" could mean a wide variety of things, and the algorithms/results depend on your model. Below is an overview of the concerns. Here is a paper that gives an overview of some different concerns and models (related to what Peter cited in another answer).

For dynamic problems in general, the key issues are:

do you want an exact solution in all cases, or is approximation allowed?
do you know anything about what changes will occur (e.g. a probability distribution), or are they all equally likely?
how does the algorithm learn about the changes?

A typical dynamic model is something like the following:

Given a graph, you want to compute some property. You are allowed to compute a solution for the initial graph.
You are then told one modification: edge $(e,f)$ is deleted. Compute the property on the new graph using limited resources.
Repeat 2 for $n$ times.

And here are 3 possible modifications:

You aren't allowed to compute the complete solution at the beginning because of information / time / space limitations (one example of which is online algorithms)
In step 2, the algorithm is not "told" the modification, but has to find the modification in the graph by querying a data structure or something.
A distributed model (like Peter discusses in another answer), where the information is discovered locally and the computation/changes are made locally.

Dynamic models are typically interesting because of resource (e.g. time/space) limitations. In step 2, if I was allowed to compute a complete answer (like I did in step 1) then the problem is easy, since it's just a repeated static graph problem. We're more interested in the smallest amount of resources necessary to compute the change.


Calculating Binet's formula for Fibonacci numbers with arbitrary precision

As the comments show, roundig is a respected method for Fibonacci computations. See also "Computation by rounding" in the wiki-lemma.

You avoid roundoff by computing exactly, but using numbers of the form $a+b\sqrt5$: $(a+b\sqrt5)(c+d\sqrt5) = (ac+5bd)+(ad+bc)\sqrt5$. Technically that is $Z[\sqrt5]$ I believe. But I now realise that you also have to take into account that $a,b$ are fractions.

But the recursion is so nice, why not use it? Based on the matrix form you can get the $n$-th Fibo number in a logarithmic number of steps.


Why are ADT packages opened immediately after they are built, while existential objects opened as late as possible?

You can see an instance of the claimed property in the two definitions of add3.

In the ADT style, add3 is defined as:

let { Counter, counter } = counterADT in
let add3 = λ (c : Counter). counter.inc (counter.inc (counter.inc c)) in
counter.get (add3 counter.new);

As you see, in order to call about inc, one must already have opened the existential package. You cannot write the inc3 function in the "ambient scope", as Counter is not an ambient type, but a type encapsulated in the counterADT package.

You could repackage everything after the first call to inc, and re-open the package before the next call, but that would be somewhat pointless.

In the object style, add3 is defined as:

add3 = λ (c : Counter). sendinc (sendinc (sendinc c)))

Here, the client code does not open the existential package themselves.  Instead, each call to sendinc will open the package when it needs to run inc, and will repackage the output.  The client could just do the same, but that is not the intent of this style (they would be breaking the abstraction).

So, the confusion might be that you understood the sentence as "the packages are open at a given time", as opposed to "a programmer would be expected to open the package at a given time".

The difference in timing comes from the way we want to use these two mechanisms.

The ADT mechanism is one where we have a single representation, that we wish to hide, while giving some actions to perform on that representation.  Because there is a single representation, it is perfectly acceptable to unpackage it once and for all.

The object mechanism is one where we want to potentially allow multiple representations that all share some actions to perform on them.  Because we want to allow multiple representations, each package should be responsible for knowing how to perform the abstract action on its concrete representation.  If we were to unpackage the existential type early, we would locally be restricted to a given representation.

This becomes very interesting when thinking about binary operations over the packaged type: in the ADT style, the two operands are guaranteed to share the same representation, whereas in the object style, each operand could have its own concrete representation and its own way of implementing the binary operation.

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

^ This paper, "On Understanding Data Abstraction, Revisited", by William R. Cook gives a lengthy explanation of the difference in power between these two approaches, and is, in my opinion, an excellent read.


Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.
Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr[A(x) = 1] \geq 2/3$, and if $x \notin L$ then $\Pr[A(x) = 0] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$.
Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?
Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In total, $$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$
Similarly, if $x \notin L$ then $\Pr[B(x) = 0] \geq 11/18$. This is almost what we want – we want $11/18$ to be replaced by $2/3$.
In order to enhance the success probability ("error reduction"), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.


Viterbi Algorithm: initial state with ONE probability

Wikipedia is wrong.  That's not what $T_1$ stores.  Rather, $T_1$ stores the likelihood of a path... namely, the likelihood of the path that has the highest likelihood.  What's the likelihood of a path $\hat{X}$?  It is the probability of generating the output sequence $Y$ given that you followed the path $\hat{X}$, i.e., the probability $P(Y | \hat{X})$.  Note that this is not the same as $P(\hat{X} | Y)$.

The probability $P(Y | \hat{X})$ might be less than 1, even if we're certain that $\hat{X}$ was the path that was followed.  In particular, you can have $P(Y | \hat{X}) < 1$ even if $P(\hat{X}) = 1$.  This can happen, for example, if there are multiple possible output sequences that could arise when following the path $\hat{X}$.

As usual, Wikipedia is not a primary source.  Don't use Wikipedia as your only source for learning new material.  It is helpful as a summary, but when you find something in Wikipedia that is confusing or that doesn't make sense, go to a primary source -- e.g., a highly reputed textbook.  Wikipedia does have errors, poor writing, gaps in its explanation, and so on, so it is not a substitute for a high-quality primary source.


Notations for dealing with generators in algorithms

There is no standard way of writing pseudocode. Your main goal when writing pseudocode is that the reader understands it. If you are unsure that the reader will understand yield or yield from, explain what these keywords mean for you, and mention that they are borrowed from Python, to give due credit.


What is a conventional format for presenting algorithms?

There is no such thing as  the "format" for algorithms. A general agreement¹ is to use pseudocode, i.e. code that abstracts from the particulars of specific programming languages, machines and/or libraries.

The most important thing is to be consistent.
If you want to follow a specific style, I recommend you pick up some textbooks on algorithms and/or data structures and follow the style you like best.

Some kinds of pseudocode have specific package support in LaTeX, e.g. clrscode, algorithms or pseudocode. For help with these go to tex.SE.

As long as you publish about algorithms as scientist. Articles featuring concrete technology frequently use real code, for better or worse.


Can somebody explain Horner's method of evaluating polynomials and how does it reduce the time complexity to 2n operations?

Let's compute the polynomial $2+3x+x^2+15x^3$ using Horner's method:
$$ 2 + x(3 + x(1 + 15x)). $$
The complete set of steps is
$$
\begin{align*}
&t_1 \to 15 \times x \\
&t_2 \to t_1 + 1 \\
&t_3 \to t_2 \times x \\
&t_4 \to t_3 + 3 \\
&t_5 \to t_4 \times x \\
&t_6 \to t_5 + 2
\end{align*}
$$
Compare this to the "trivial" method:
$$
\begin{align*}
&t_1 \to x \times x \\
&t_2 \to t_1 \times x \\
&t_3 \to 15 \times t_2 \\
&t_4 \to 3 \times x \\
&t_5 \to 2 + t_4 \\
&t_6 \to t_5 + t_1 \\
&t_7 \to t_6 + t_3
\end{align*}
$$
Here the idea is to compute the powers $1,x,x^2,x^3$ and then take the linear combination corresponding to the polynomial. Since one of the coefficients is $1$ (coefficient of $x^2$), we only need $7$ rather than $8$ operations.


Computational complexity of calculating mean vs median?

You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.


The following simpler adaptation of von Neumann's trick is more efficient than the one described in HdM's answer. Throw your die twice. If the two answers $x,y$ are different, write $0$ if $x<y$ and $1$ if $x>y$. This way, you get an unbiased bit source. If you are so inclined, you can use this bit source to simulate fair die throws.


Problems that become far easier when restricted to only integer values

There's no single answer.

Some algorithms are faster when dealing with small integers, because you can use small integers as the index into an array.
Some algorithms are faster when dealing with positive integers, because the set of positive integers has the property that it does not contain any infinite decreasing chains: any set of positive integers has a minimum.
Some algorithms are faster when dealing with integers because they assume a computational model where you can add or multiply integers in $O(1)$ time.  It is dubious whether these algorithms are truly faster in practice, as that assumption isn't literally true, but they might be.
Some algorithms are faster (or simpler) when dealing with integers because integers can be not only compared, but also hashed, and the ability to hash items increases the range of options available to the algorithm designer.  See the nuts-and-bolts problem for an example vaguely of this form (there are probably better examples).

There are probably many other principles I'm not thinking of right now.

Most of the cases I know of involve only a $O(\lg n)$ speedup.   However, be warned that asymptotic $O(\lg n)$ speedups are not very robust, for several reasons.  Just because algorithm A is asymptotically faster than algorithm B by a factor of $\Theta(\lg n)$ doesn't mean it'll be faster in practice; it might be slower in practice, because of constant factors or because of considerations ignored in the theoretical analysis (e.g., caching  effects, the memory hierarchy, and so on).  Also, often the $O(\lg n)$ speedup results you see in this area will be dependent on a particular computational model and might not carry over to other computational models.

So, it's not clear how much weight you should put on this, if you are motivated by practical concerns.

See also:

Is there a meaningful difference between O(1) and O(\log n)?
Logarithmic vs double logarithmic time complexity
Why is quicksort better than other sorting algorithms in practice?
Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
How can a quadratic algorithm be faster than a linearithmic one?
Shouldn't complexity theory consider the time taken for different operations?
How can we assume that basic operations on numbers take constant time?


Is randomly building a BST different from random sampling whole trees?

You want to distinguish

  randomly built binary search tree

from

  choosing a binary search tree from a random distribution.

Let me first tell you why this is not a well-posed query. Neither version is
completely specified; the first misses the process by which the tree is built
as well as the used random source, the second lacks a specification of the
distribution to be used. In particular, the "randomly built" trees are
"chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate
the models.

Starting with the empty tree, we insert keys $s_1, \dots, s_n \in [1..n]$
successively (with BST insertion). The sequence is chosen uniformly at random
from all permutations of $[1..n]$.

This is the famous random permutation model.
Pick a tree uniformly at random from all BSTs with keys $[1..n]$.

There are several ways to see that the two models define different random distributions.

There are $n!$ different permutations but only
$C_n = \frac{1}{n+1} \cdot \binom{2n}{n}$
BSTs. Show that it is not possible to distribute the permutations evenly,
i.e. $C_n$ does not (always) divide $n!$.

In particular, for $n=3$ we have six permutations but five BSTs.
For $n=3$, enumerate all trees and notice that four trees result from one
permutation each while the fifth results from two. Ergo, the random
permutation model is not uniform.
Know (from earlier studies) that BSTs have average height $\Theta(\log n)$
in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko [1]; the method of analysis has broader relevance and the result generalises to many families of trees.

The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)


An LL parse produces a leftmost derivation, which means that at each point in the derivation, the leftmost non-terminal must be replaced by one of its productions. The issue is to decide which production to use.

A grammar is LL(k) if the production to be used in the leftmost derivation can always be determined by examining only the terminals prior to the first non-terminal and the $k$ following terminals in the input. (These will be the next $k$ symbols in the input if we're doing a left-to-right parse; the terminals prior to the non-terminal will already have been input.)

In your grammar, neither $S$ nor $A$ present any problems at all. $S$ only has one production, so there is no need to examine any terminal at all to make a decision. $A$ has two productions, but their first terminal differs so it is trivial to predict which one to select: if the next input symbol is $a$, select the first alternative; if it is $b$, select the second one.

$B$ also has two productions, but both of them start with a $b$. So we need to look at least one symbol further in the input. Now, what is the second symbol in a derivation starting with each production for $B$? For $B \to b c$, the second symbol is clearly $c$. In $B \to b B c$, the second symbol must be the first symbol in some derivation of $B$. But, as we've just observed, every derivation of $B$ starts with $b$. So the second symbol in $B \to b B c$ must be a $b$.

With that, we have a complete decision procedure:

If the non-terminal to expand is $S$:

choose the production $S \to a a A$

If the non-terminal to expand is $A$:

If the next input is $a$:

choose the production $A \to a A c$

If the next input is $b$:

choose the production $A \to b B c$

If the non-terminal to expand is $B$:

If the next two input symbols are $bb$

choose the production $B \to b B c$

If the next two input symbols are $bc$

choose the production $B \to b c$

If there is no non-terminal left

Report success

If none of the above rules apply

Report failure

The longest sequence of terminals we need to examine in any of those rules is 2. So the grammar is LL(2).


Converting a function with single parameter to a function with multiple parameters

You could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$.

$$f(n, i) = \begin{cases}
    1 & \text{if } n =0\\
    f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\
    0 & \text{otherwise}\\
\end{cases}$$

Then $f(n, 0)$ gives you the answer you want.


This is of course a consequence of $coNP \subset PH \subset PSPACE = IP$. But it can also be proven directly for UNSAT.

The basic idea is reducing the problem to zero-testing a sum over a polynomial in a suitable finite field. It's a bit too technical to repeat neatly here, but I can give you an informal idea of how it is done.

Let's consider a formula $\phi$, define $p_\phi$ to be the polynomial where you think of $x_i$s as variables, replacing $\neg x_i$ by $(1 - x_i)$, each $\wedge$ by $\times$ and each $\vee$ by $+$. Notice that the formula is unsatisfiable iff $p_\phi(x_1, \dots, x_n) = 0$ for all $x \in \{0, 1\}^n$ or equiavalently if

$$
\sum_{x_1 \in \{0, 1\}}\sum_{x_2 \in \{0, 1\}} \dots \sum_{x_n \in \{0, 1\}} p(x_1, x_2, \dots, x_n) = 0
$$

This follows from the fact that $p_\phi \geq 0$ for any $0/1$ assignement.

The interaction is essentially the prover trying to convince the verifier that the sum is indeed zero. The interaction is done on the sum above modulo a suitable prime to keep computations manageable for the verifier.  The full details are explained here. The main proof that you need to follow and convince yourself of, is that the prover cannot fool the verifier with large probability.


Sorting when there are only O(log n) many different numbers

Because you asked for minimum number of comparisons, so I assume the algorithm can only compare the numbers.

The idea is to extend the sorting lower bound argument.
Assume you want to sort $n$ elements knowing there exist at most $k$ distinct values. There are $n!$ ways to permute the elements, but many of them are equivalent. If there are $n_i$ element of the $i$th values. Each permutation is equivalent to $\prod_{i=1}^k n_i!$ other permutations. So the total number of distinct permutations is

$$\frac{n!}{\prod_{i=1}^k n_i!}$$

The number of required comparisons is bounded below by $$ \log_2 \left( n!/\min \{ \prod_{i=1}^k n_i! \big| \sum_{i=1}^k n_i = n, n_i\geq 0\text{ for all } i\} \right)$$

Good thing that minimization part can be easily shown by extend factorial to the continuous domain. $\min \{ \prod_{i=1}^k n_i! \big| \sum_{i=1}^k n_i = n, n_i\geq 0\text{ for all } i\}$ is attained when $n_i=n/k$. (note the $\log$ in the next computation is base $e$ for convenience)

$$ \log \left( n!/{(n/k)!^k} \right) = \log (n!) - k \log ((n/k)!) = n\log(n) - n\log(n/k) + O(\log n)=  n(\log(n)-\log(n)+\log(k)) + O(\log n) = \Omega(n\log k) $$

$\log(n!) = n\log n - n + O(\log n)$ is Ramanujan's approximation.

To get an upper bound. Just consider storing the unique values in a binary search tree, and each insert we either increase the number of occurrence of an element in the BST, or insert a new element into the BST. Finally, print the output from the BST. This would take $O(n\log k)$ time.

Since both the lower bound and upper bound works for all $k$, the algorithm would take $O(n\log \log n)$ time for your problem.

Addendum:

I just figured out from @Pseudonym's comment that this proof also proves that we need at least $nH$ comparisons where $H$ is the entropy of the alphabet, so I might as well add this to the answer.

Let $c = \log 2$ and $p_i = n_i/n$. The entropy of the alphabet where the $i$th letter appears $n_i$ time is $H=-\sum p_i \log_2 p_i$. $nH = -\sum n_i (\log_2(n_i)-\log_2(n)) = \sum n_i (\log_2(n) - \log_2(n_i)) = c \sum n_i (\log(n) - \log(n_i))$.

\begin{align*}
\log_2 \left( n!/\prod_{i=1}^k n_i! \right) &= \log_2(n!)-\sum_{i=1}^k \log_2(n_i!)  \\
&= \log_2(n!)-\sum_{i=1}^k \log_2(n_i!)  \\
&= c (\log(n!)-\sum_{i=1}^k \log(n_i!))  \\
&= c (n \log n-n + O(\log n) - \sum_{i=1}^k n_i \log(n_i)-n_i+O(\log n_i))  \\
&\geq c (n \log n-n -  \sum_{i=1}^k n_i \log(n_i)-n_i)  \\
&= c (-n + \sum_{i=1}^k n_i(\log(n) - \log(n_i))+n_i)  \\
&= c (\sum_{i=1}^k n_i(\log(n) - \log(n_i)))  \\
&= nH
\end{align*}


How to calculate the size of a page in a two level paging CPU?

The thorough solution:

The virtual address looks like this:

+-------------+------------+--------+
+ table index + page index + offset +
+-------------+------------+--------+

where:

table index is the index length of an entry in the page table directory. I'll call it $i_t$.
page index is the index length of an entry in the page table. I'll call it $i_p$.

So we have such an equation now:
$$
i_t+i_p+o=32
$$
where $o$ represents bits that we need for offset.

From the decoded addresses we know that offset cannot be greater than $14$, so:
$$
o \leq 14
$$
We know that an entry in both page tables and page tables directories needs $i_t + b_d$ of bits where $b_d$ is the number of bits for accounting information (such as dirty bits, protection bits and so on). So, $b_d$ are accounting bits in the page table directory and $b_t$ are are accounting bits in page table.

So, if $\text{page size} = 2^\text{offset}$ then $\text{page table size} = 2^\text{offset}$ and $\text{page table directory size} = 2^\text{offset}$:
$$
\begin{cases}
i_t+b_d = o\\
i_s+b_t = o\\
\end{cases}
$$
We can say thatSince $\text{page table size} = \text{page table directory size}$ then $i:= i_t = i_s$ and $b :=b_d=b_t$, so we end up with a system of equations like this:
$$
\begin{cases}
i_t+b_d = o\\
i_s+b_t = o\\
i_t+i_p+o=32
\end{cases}
$$
$$
o-b_d+o-b_t+o=32\\
$$
and finally because of $b :=b_d=b_t$:
$$
3o-2b=32\\
$$
Now we will test different values of $o$ (I'll not test odd $o$'s because $o$ must be dividable by $2$):

when $o=14$:
$$
42-32=2b=10\\
\implies b=5\\
\implies i = 14-5=11\\
\implies i_t+i_s+o=11+11+14=36 \neq 32
$$
when $o=12$:
$$
36-32=2b=4\\
\implies b=2\\
\implies i = 12-2=10\\
\implies i_t+i_s+o=10+10+12=32 = 32
$$
which seems to be the answer. Let's just make sure there are no other possibilities.
when $o=10$:
$$
30-32=2b=-2\\
\implies b=-1\\
$$
which cannot be true - you obviously cannot have a negative number of bits.

Therefore, the size of a page is equal $2^o=2^{12}$.