Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?

Since $1+2+\dots+n =O(n^2)$, it is tempting to suggest that $O(1)+O(2)+\dots+O(n) = O(n^2)$ ... but this is not in fact valid.  The reason is that there might a different constant for each term in the sum.

An example

Let me give an example.  Consider the sums $S(1) = 1^2$, $S(2) = 1^2 + 2^2$, $S(3) = 1^2 + 2^2 + 3^2$, $S(4) = 1^2 + 2^2 + 3^2 + 4^2$, and so on.  Note that $1^2 \in O(1)$, $2^2 \in O(2)$, $3^2 \in O(3)$, $4^2 \in O(4)$, and so on for each term in the sum.  Therefore, it would be reasonable to write $S(j)=1^2 + \dots + j^2$ in the form $S(j) = O(1) + \dots + O(j)$.  So can we conclude that $S(j) = O(j^2)$?  Nope.  In fact, $S(n) = n(n+1)(2n+1)/6$, so $S(n) = \Theta(n^3)$.

If that doesn't help, let's try the following more precise mathematical development:

A formalization

Recall that the interpretation of, say, $O(n^2)$ is that it is a set of non-negative functions $f(n)$ (namely, the set of functions $f(n)$ such that there exists constants $c \ge 0, d\ge 0$ such that $f(n) \le c \cdot n^2$ for all $n\ge d$).

The closest we can come to an interpretation of $O(1) + O(2) + \dots + O(n)$ is that it is the set of functions of the form $f_1(n) + f_2(n) + \dots + f_n(n)$ such that $f_1(n) \in O(1)$, $f_2(n) \in O(2)$, ..., $f_n(n) \in O(n)$.

But now the constants for each $f_i$ can be different.  Thus, each $f_i$ is a non-negative function $f_i$ such that there exist constants $c_i\ge 0,d_i \ge 0$ with $f_i(n) \le c_i \cdot i$ for all $n \ge d_i$.

Now, given this, what can we say about $g(n) = f_1(n) + f_2(n) + \dots + f_n(n)$?  Not much useful.  We know that there exists a constant $d=\max(d_1,d_2,\dots,d_n)$ such that $g(n) \le c_1 \cdot 1 + c_2 \cdot 2 + \dots + c_n \cdot n$ for all $n\ge d$.  Now what can we say about this sum?  Well, the answer is that we can't say anything at all.  It could be arbitrarily large.  It is tempting to let $c=\max(c_1,c_2,\dots,c_n)$ and say that $g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$... but this is not actually correct, since we need a single constant value of $c$ that works for all $n$, and the value $\max(c_1,c_2,\dots,c_n)$ is a function of $n$, not a constant.

So there might not be any constant $c$ such that $g(n) \le c \cdot (1+2+\dots+n)$; there might not be any constant $c$ such that $g(n) \le c \cdot n^2$.  There is no guarantee that $g(n) \in O(n^2)$.

For more reading

See https://math.stackexchange.com/q/86076/14578 and Sums of Landau terms revisited for other questions that deal with this general issue.


Look for the unique integer $x$ such that $b x \le a$ and $b(x+1) > a$. With this approach, you don't need a WHILE statement.


Decidability of determining whether a context-free grammar generates all strings in 1*

You can find the solutions to the exercises of that book here. For completeness of the answer, I rewrite the solution (with some more details) here.

Let $p$ be an upper bound of the pumping length of $G$, you only need to check whether $1^0, 1^1,\ldots,1^{p+p!} \in G$. If not, we can certainly reject $\langle G\rangle$. Otherwise, applying pumping lemma on $1^k$ ($p\le k\le p + p!$), we can conclude that there exist substrings $u,v,w,x,y$ such that

$1^k=uvwxy$, which means $u,v,w,x,y$ contain only 1s,
$|vwx|\le \text{pumping length} \le p$,
$|vx|\ge1$ and
$uv^nwx^ny\in G$, i.e. $1^{|uwy|+n|vx|}=1^{k+(n-1)|vx|}\in G$, for all $n\ge 0$, which means $1^{k+n(p!)}\in G$ for all $n\ge0$.

Note $\{1^{k+n(p!)}\mid n\ge0, p\le k\le p + p!\}$ covers all $1^m$ for large $m$, so $1^0, 1^1,\ldots,1^{p+p!} \in G$ indeed implies $1^*\subseteq G$.


Given a distribution $\mu$ on a finite set, let us denote by $T(\mu)$ the average depth of a leaf in a Huffman tree of $\mu$ (depth is measured by the number of edges from root to leaf); we assume that no element has zero probability. Then
$$
H(\mu) \leq T(\mu) < H(\mu)+1,
$$
where $H(\mu) = \sum_i \mu_i \log_2 (1/\mu_i)$ is the entropy of $\mu$ (here $\mu_i$ is the probability of the $i$th element).

To prove this, let us start with Kraft's identity. In the statement below, a complete binary tree is one in which every internal node has exactly two children.

Kraft's identity. There is a complete binary tree whose leaf depths are the multiset $\{\ell_1,\ldots,\ell_n\}$ if and only if $\sum_{i=1}^n 2^{-\ell_i} = 1$.

Proof. Let us first show that the leaf depths satisfy Kraft's identity. The proof is by induction on $n$. If $n = 1$ then $\ell_1 = 0$, and indeed $2^{-\ell_1} = 1$. Otherwise, arbitrarily choose two sibling leaves, and remove them. If the original depth was $\ell$, this affects the multiset of depths by removing $\ell,\ell$ and adding $\ell-1$. The induction hypothesis shows that the new multiset satisfies Kraft's identity. Since $2^\ell + 2^\ell = 2^{\ell-1}$, the original multiset also does, completing the proof.

Let us now show that if a multiset $L$ satisfies Kraft's identity, then there is a complete tree whose leaf depths are $L$. Once again, the proof is by induction on $n = |L|$. If $n = 1$, then necessarily $L = \{0\}$, and the tree consisting of a single leaf works. Otherwise, let $\ell = \max L$. Notice that
$$
2^\ell = \sum_i 2^{\ell - \ell_i}.
$$
If $\ell_i = \ell$ then $2^{\ell - \ell_i} = 1$, and if $\ell_i < \ell$ then $2^{\ell - \ell_i}$ is even. Hence the number of copies of $\ell$ in $L$ is even, and in particular there are at least two such copies. Let us form $L'$ by removing two copies of $\ell$ and replacing them by a copy of $\ell-1$. Applying the induction hypothesis, we obtain a tree $T'$ whose leaf depths are $L'$. By construction, $T'$ has a leaf of depth $\ell-1$. Adding to it two children, we obtain a tree $T$ whose leaf depths are $L$, completing the proof. $\square$

We can now prove the inequalities on $T(\mu)$, starting with $T(\mu) \geq H(\mu)$.

Lower bound on $T(\mu)$. Consider any tree whose leaves are labeled by the support of $\mu$, and suppose that element $i$ is on a leaf at depth $\ell_i$. Let $\nu_i = 2^{-\ell_i}$. Kraft's identity shows that $\sum_i \nu_i = 1$. Since $\ell_i = \log_2(1/\nu_i)$, we have
$$
T(\mu) - H(\mu) = \sum_i \mu_i (\ell_i - \log_2 (1/\mu_i)) = \sum_i \mu_i \log_2 (\mu_i/\nu_i).
$$
The function $\log_2 (1/x)$ is convex, hence Jensen's inequality shows that
$$
\sum_i \mu_i \log_2 (\mu_i/\nu_i) =
\sum_i \mu_i \log_2 \frac{1}{\nu_i/\mu_i} \geq \log_2 \frac{1}{\sum_i \mu_i (\nu_i/\mu_i)} = 0,
$$
using $\sum_i \nu_i = 1$. We conclude that $T(\mu) \geq H(\mu)$. $\square$

The other direction uses Shannon–Fano coding.

Upper bound on $T(\mu)$. Let $\ell_i = \lceil \log_2 (1/\mu_i) \rceil$. Then
$$
\sum_i 2^{-\ell_i} \leq \sum_i 2^{-\log_2 (1/\mu_i)} = \sum_i \mu_i = 1.
$$
If $\sum_i 2^{-\ell_i} < 1$, let $\ell = \max_i \ell_i$. Notice that
$$
\sum_i 2^{\ell-\ell_i} < 2^\ell,
$$
where all summands are integral.
If we decrement one copy of $\ell$ to $\ell-1$ then we increase the left-hand side by $2^{\ell-(\ell-1)} - 2^{\ell-\ell} = 1$, so the left-hand side is still at most $2^\ell$. Hence after the update, we still have $\sum_i 2^{-\ell'_i} \leq 1$, where $\ell'_i$ are the new values. Continue doing so until the sum reaches 1; this must happen, since the decreasing process cannot continue forever (the depths keep decreasing while never dipping below zero). Denoting by $r_i$ the new values, Kraft's identity implies that there exists a tree whose leaf depths are the $r_i$. The average depth of a leaf in this tree is
$$
\sum_i \mu_i r_i \leq \sum_i \mu_i \ell_i < \sum_i \mu_i (\log_2 (1/\mu_i) + 1) = H(\mu) + 1.
$$
Huffman's algorithm will find a tree which is at least as good. $\square$

Finally, let me show that for every $\epsilon>0$ there are distributions $\mu$ for which $T(\mu) \geq H(\mu) + 1 - \epsilon$. Given $\delta>0$, consider the distribution $\mu$ on two elements with $\mu_1 = 1-\delta$ and $\mu_2 = \delta$. Clearly $T(\mu) = 1$, while $\lim_{\delta\to0} H(\mu) = 0$. Therefore we can find positive $\delta$ for which $H(\mu) \leq \epsilon$. For such $\mu$ we have $T(\mu) = 1 \geq H(\mu) + 1 - \epsilon$.

What happens if we force all probabilities to be small? Gallager, in his classic paper Variations on a theme by Huffman showed that even in this regime, there are distributions for which the gap is roughly $\log_2 [(2/e)\log_2 e] \approx 0.086$. Amazingly, this is attained by uniform distributions!


Effective AI for one player-one ghost pacman

This is an adversarial game problem where you need to find the optimal behavior from each position. There are several approaches to attack such problem.

You can do Minimax with alpha beta pruning to find the best move.
It will provide you an optimal move after exploring the entire tree up to some level (not too deep if the branching factor is too high, here your branching factor is $4*players$) using a handcrafted heuristic by you. So the quality of the results heavily depends on the quality of the heuristic. If you improve the pruning you can achieve better results, as you can explore more.

Another approach is Montecarlo Tree Search. This algorithms performs really good in several games, and doesn't depend on any previously knowledge of the game. Roughly speaking, it seeks the best option by expanding the tree from the state you are in and calculates the quality of a state by performing a random simulation of the game.

There is a novel approach, Reinforcement learning, that you can use to find the answer. The idea behind it is approximate the optimal policy that gives you the maximal reward. Here you can understand by policy the action you will make at any position an the rewards are the points you get after each action. You can read more about it here.


Which of the following words is in the language of the grammar G?

This is what we have at our hand.
Now let us see what can be get from the second production in red.

From the production in Blue we have

And the parsing can be stopped using $S\rightarrow \epsilon$
So from the above two work outs we find that the $a$'s and $b$'s are properly nested. (and can be mapped to the problem of valid parenthesization )
That being said let us work the options out:

Alternatively, during the examination, it is hard to get this detailed thought in mind, so one can try to draw the parse tree for any one of the words, trying to do so, you shall get the intuition of the semantics of the language of the grammar.


Does a graph diameter equal to DFS tree depth?

Regarding DFS the answer is no. Here there is a counter example.

The red arcs represent the DFS tree starting from the topmost node. This tree depth is 5 while the diameter is 3.

On the other hand, the maximum BFS tree depth coincides with the diameter of the graph (of course, this is valid if the graph is connected). If you run BFS from a source node S, all path found from this point to any other point will be of minimal length, i.e it contains all shortest path from point S to any other point. Though the maximum BFS tree depth is the maximum among all shortest path.


Why are computable functions also called recursive functions?

The founders of computability theory were mathematicians.
They founded what is now called computability theory
before there was any computers.
What was the way mathematicians defined functions that could be computed?
By recursive definitions!

So there were recursive function before
there were any other model of computation like Turing machines or
lambda calculus or register machines.
So people referred to these function as recursive functions.
The fact that they turned out to be exactly
what Turing machines and other models can compute is a later event
(mostly proven by Kleene).

We have the simple definition of a recursive function which is now called
primitive recursive function.
There were not general enough (e.g. Ackermann's function)
so people developed more general notions
like $\mu$-recursive functions and
Herbrand-Gödel general recursive functions that
did capture all computable functions (assuming the Church's thesis).
Church claimed that his model of lambda calculus captured
all computable functions.
Many people, and in particular Gödel, were not convinced that
these capture all functions that can be computed.
Until Turing's analysis of computation and introduction of his machine model.

The name of the field used to recursion theory.
However there has been a successful push in recent decades
to change the name to something more appealing from
recursion theory to something more computer sciency (vs. mathy).
As a result the field is now called computability theory.
However if you look at books, papers, conferences, etc. in the early decades
they are called recursion theory and not computability theory.
Even the title of Soare's own 1987 book
(who was the main person behind the push to change the name
to computability theory)
is "Recursively Enumerable Sets and Degrees".

If you want to know more about the history
a fun and good place to read about it is
the first chapter of Classical Recursion Theory by Odifreddi.


Reducing vertex cover to minimal vertex cover

Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.


Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

When you disambiguate a grammar, you usually want at least to keep the language the same. So the answer is that you want  $\mathcal L(G)=\mathcal L(D)$.

If you accepted that $\mathcal L(G)\subset \mathcal L(D)$ then you could simply choose $\mathcal L(D)=\Sigma^*$, since $\Sigma^*$ has an unambiguous grammar. Of course $\Sigma$ is the terminal alphabet.

If you accepted that $\mathcal L(D)\subset \mathcal L(G)$ then you could simply choose $\mathcal L(D)=\emptyset$ since $\emptyset$ has an unambiguous grammar.

I assume you were considering context-free (CF) languages. You should have said so.

And you should remember some facts that will not help:

Some CF languages are inherently ambiguous, so that you cannot find an unambiguous grammar for them. Furthermore, it is undecidable whether a CF language is inherently ambiguous,
It is  undecidable to know whether a grammar is ambiguous, hence it is not clear when a disambiguating transformation is needed.

See also wikipedia page on ambiguous grammars.


Finite list induction principle and the tail eliminator

I am totally lost on how to approach this problem since the eliminator seems to be able to provide just function defined on the whole family List′A(n) and not on the sub-family List′A(s(n)).

The typical trick in this situation is to pick a C such that you can pretend you are defining a function on the whole family when, in fact, you're only focusing on the sub-family you care about thanks to equality constraints.

Let me be more concrete:

If you pick C(n, xs) = (m:N) -> n = s(m) -> List'_A(m) then you can define a generalised gtail by using listrec', and derive tail as a corollary.

gtail : (A:set) (n:N) (xs : List'_A(n)) -> C(n, xs)
gtail A = listrec' A C
          contradiction -- of type: (m:N) -> 0 = s(m) -> List'_A(m)
          (\ _ _ u _ -> u)

tail : (A:set) (n:N) -> List′A (s(n)) -> List′An
tail A n xs = gtailn A (s(n)) xs n refl


Find non-regular $L$ such that $L \cup L^R$ is regular?

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

   Try to think on complements of known non-regular languages.

Solution:

   Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the strings EXCEPT for those in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now let's think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
 Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages.
 Since $\Sigma^*$ is regular, we are done.


Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

Here is what your teacher meant. Let $M=\{a^nb^n:n\geq0\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^*b^*=M$ be, reaching a contradiction. This shows that $L$ cannot be regular.


I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well.

If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you add all the A, then all the B, and then all the C. You're better off mixing smaller units. For example, do single-unit additions in the sequence [A,B,A,C,B,A]. That will prevent stratification altogether.

The way I found to do it is to treat it as a kind of merge, using a priority queue. If I create a structure to describe the additions:

MergeItem
    Item, Count, Frequency, Priority

The Frequency is expressed as "one every N". So A, which is added three out of six times, has a frequency of 2 (6/3).

And initialize a heap that initially contains:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Now, I remove the first item from the heap and output it. Then reduce its count by 1 and increase Priority by Frequency and add it back to the heap. The resulting heap is:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Next, remove B from the heap, output and update it, then add back to the heap:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

If I continue in that fashion, I get the desired mixture. I use a custom comparer to ensure that when equal Priority items are inserted into the heap, the one with the highest Frequency value (i.e. the least frequent) is ordered first.

I wrote a more complete description of the problem and its solution on my blog, and presented some working C# code that illustrates it. See Evenly distributing items in a list.

Update after comments

I do think my problem is similar to the OP's problem, and therefore that my solution is potentially useful. I apologize for not framing my answer more in the terms of the OP's question.

The first objection, that my solution is using A, B, and C rather than 0, 1, and 2, is easily remedied. It's simply a matter of nomenclature. I find it easier and less confusing to think about and say "two A's" rather than "two 1's". But for purposes of this discussion I have modified my outputs below to use the OP's nomenclature.

Of course my problem deals with the concept of distance. If you want to "spread things out evenly," distance is implied. But, again, it was my failing for not adequately showing how my problem is similar to the OP's problem.

I ran a few tests with the two examples that the OP provided. That is:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

In my nomenclature those are expressed as [2,2,2] and [4,3,2,1], respectively. That is, in the last example, "4 items of type 0, 3 items of type 1, 2 items of type 2, and 1 item of type 3."

I ran my test program (as described immediately below), and have posted my results. Absent input from the OP, I can't say if my results are similar to, worse than, or better than his. Nor can I compare my results to anybody else's results because nobody else has posted any.

I can say, however, that the algorithm provides a good solution to my problem of eliminating stratification when mixing liquids. And it looks like it provides a reasonable solution to the OP's problem.

For the results shown below, I used the algorithm that I detailed in my blog entry, with the initial priority set to Frequency/2, and the heap comparer modified to favor the more frequent item. The modified code is shown here, with the modified lines commented.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Running my test program with the OP's first example, I get:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

So my algorithm works for the trivial problem of all counts being equal.

For the second problem that the OP posted, I got:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

I don't see an obvious way to improve on that. It could be rearranged to make the distances for item 0 [2,3,2,3] or some other arrangement of 2 and 3, but that will change the deviations for items 1 and/or 2. I really don't know what "optimum" is in this situation. Is it better to have a larger deviation on the more frequent or on the less frequent items?

Lacking other problems from the OP, I used his descriptions to make up a few of my own. He said in his post:

  A typical list has ~50 items with ~15 different values in varied quantities.

So my two tests were:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

And my results:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

And for the second example:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0


Minimum number of scenarios to run to fully test a page

I would approach this a little differently.

Suppose you want to test a particular piece of functionality, e.g. logging in.

You first need to navigate to the login page, which may succeed or fail. Failure doesn't mean your test is failing; it means a precondition of your test, namely, being able to navigate to the login page, is failing. That's not what you're testing in this test.

Once you've arrived on the login page, you can attempt to log in, which may succeed or fail. This is the test you want to perform. If your test is correct, the results will correctly indicate whether logging in worked or not.

This is true in general: tests may generally have preconditions that aren't part of the test, but that can be tested themselves.

I think what you're trying to say is that many different paths may cause the precondition (in this case: the login page being reached) to be fulfilled, and testing those paths really should be separated from running the test that that precondition is a precondition for.  We want to test those paths separately, and once we think they are reliable, use any of them to fulfill the precondition for the present test.

This can be formulated differently by saying: we'll assume that using the application will put us into certain consecutive states, and what we want to do is test each transition between states. Certain sequences of actions will (if they go well) bring us into a certain state, suitable as a starting point for performing the test we want to perform. The test will then perform another action, that is supposed to bring us into a certain state (the transition), and from the test we will be able to determine whether that state has actually been reached (whether the transition happened that is supposed to happen).

We can express this by modeling the behavior of the application as a state machine that contains the states the application can be in and the state transitions we want to test.

However, we also need to take input and output into account. Sometimes, state transitions depend on user input. For instance, supplying a correct combination of username and password produces the state of being logged in; supplying an incorrect combination produces the state of not being logged in. Furthermore, the output we see (the webpage being produced) may not correspond to a specific state, it may also depend on which transition was taken to arrive into that state. For instance, when a login attempt fails, we will see an error message, but the resulting state is one of not being logged in, not one of being shown an error message.

Therefore, it's a good idea to introduce input and output into the model, which turns our model into an I/O automaton.

So the idea is to specify the application's behavior using an I/O automaton, then to write tests to test each of its transitions. Given those tests, you can automatically generate a complete test suite to test the whole system, using various strategies. I even know a piece of software designed to do this: JTorX.

We'll need to add parametrization. For instance, when logged in, we're logged in as a specific user. The user we're logged in as is a parameter to the state of being logged in. We may need to check whether we're logged in by checking whether certain attributes of that user appear in certain positions on the page. So being able to parametrize the model by user may be important.

Furthermore, I'd factor the state machine into a Petri net or similar. For instance, being logged in is not really a state; it is an attribute of a state. Typically, being logged in we can do everything we can do when not logged in (except logging in), plus a couple of things we need to be logged in for. This can be modeled using Petri nets or some derivative (some sort of colored Petri net).

This approach will provide structure and meaning to your endeavor. Your 100 test scenarios will be paths in your I/O automaton transition graph. Your 10 paths are those of the 100 that lead from the initial state to the state in which you need to be in order to start the test at hand. The whole thing will be incomparably more understandable and concise than just specifying a zillion test scenarios and trying to group them afterwards.

Too bad Selenium, TestNG, or anything else I've worked with don't support this approach directly.  If I were still working in test automation, I might have written something that does by now. The JTorX software is dead, as far as I know, but it may still be usable, or alternatives may be out there that use the same approach.


If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?

All NP-complete problems are "equally hard", in the sense that if one of them is in P, then all of them are in P. Similarly, if one NP-complete problem can be solved in quasipolynomial time (that is, time $e^{O(\log^C n)}$ for some constant $C$) then all of them can be solved in quasipolynomial time.

Some NP-hard problems are harder than others, but all of them are at least as hard as all NP-complete problem. That is, if some NP-hard problem is in P, then all NP-complete problems are in P. Similarly, if some NP-hard problem can be solved in quasipolynomial time, then the same holds for all NP-complete problems.

However, some NP-hard problems are provably harder than others. For example, the halting problem is NP-hard, but in contrast to all NP-complete problems, it cannot be solved in exponential time; in fact, it cannot be decided at all!

  My question is, it could be possible that X has a better solution like NP or P, which we could not find.

There are two problems with this statement. The first is the assumption that NP is a better complexity class than NP-hard. In fact, all NP-complete problems are both NP-hard and in NP (that's the definition of NP-completeness), so it's in fact common for problems to be both. NP-hardness is a lower bound on complexity, whereas being in NP is an upper bound. The two are not contradictory in any way.

The second problem is the assumption that it could be possible that X is in P. As explained above, that would imply that P=NP, which most people consider unlikely. An NP-hard problem cannot be "easy" – it's at least as hard as any problem in NP, and in particular at least as hard an any NP-complete problem.

  Then why should Y be NP-hard?

You can prove that Y is NP-hard if you can reduce, in polynomial time, another NP-hard problem X to it. I won't repeat the proof here, since it can be found in textbooks, lecture notes, and even here on Computer Science.

  If Y turns out to be P (assume) then X becomes P.

That's correct, but there is no contradiction here. This is actually the point of NP-hardness. We don't believe that Y is in P, since that would imply that X, as well as many other problems, are also in P.


In place sorting is sorting without using extra memory (mostly swapping elements till getting it right).

PS In many cases it's impossible to not use any extra memory, but usually in place sorting indicates to constant extra memory.


Short answer: the decoding algorithm follows the same steps as the coder: it actually builds the tree. E.g., in your example the first two 0's mean two a's have been read, This then implies the code for aa was added to the tree as number 2. This continues, but necessarily the decoder always is one step behind the coder. In most cases all information is present to make decisions in the next move. Unfortunately there is the possibility that the decoder needs the code that has been just inserted in the tree (and is not available for the decoder since it lags behind). That case is so specific that it can be reconstructed from the other information (then the unknown letter must be the first letter of the last code).

That is the global view. Wikipedia has a larger example.


Look Ahead buffer vs Translation Look aside buffer

I do not know the exact definitions of TLBs and look-ahead buffers, but here is what I understand about them.

TLBs help make translations from virtual to physical addresses quicker via caching. So, you can see how the TLB is implementing temporal locality (any kind of caching is implementing temporal locality) in some sense.

Look ahead buffers on the other hand come into play when while bringing data from disk to memory. Pages that are explicitly requested may be brought into the disk buffer along with other pages (often selected based on spatial locality to the requested page -- but there are other heuristics that the disk can use). The idea is to not have to go to disk too often. Instead the disk will try to predict what pages will be required in the RAM in the future (hence the term "look-ahead").

Note: I have heard people call the TLB the look-aside buffer and the look-ahead buffer. To me it seems like "translation look-aside buffer" is the correct expansion (because I dont see where any "looking ahead" is happening).


Can you use a Bayes classifier to determine if something is NOT in a defined class?

Create an extra class whose membership means "belongs to none of the predefined classes".


Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

The problem is that you are using $n$ to mean too many different things without really defining it. You can't say that an algorithm runs in $O(n)$ time without specifying what $n$ is, unless it is clear from context. In this case it is not clear, and that is what is tripping you up.

When we say an integer multiplication algorithm runs in $O(n^2)$ time, the tacit assumption is that $n$ is the number of bits in the two input arguments. In practice, a multiplication algorithm that runs in $O(n^2)$ is usually actually a multiplication algorithm that runs in $O(pq)$, where $p$ is the number of bits in the first argument and $q$ is the number of bits in the second argument.

When analyzing an algorithm such as the one in the question, it would be typical to define two variables: the number of elements in the list (let's call it $\ell$) and the maximum size of any element of the list (let's call it $s$). The bit size of the representation of $\ell$ is $\Theta(\log \ell)$. Given this information—and the assumption above that the multiplication algorithm runs in time $O(pq)$ for input bit sizes $p$ and $q$—then the runtime analysis is easy: the function runs in time $O(\ell s \log \ell)$.

It is possible to do runtime analysis on this procedure using only a single $n$ variable, if we define $n$ to be the total number of bits in the representation of the entire input. That is, we let $n$ be the sum of the bit lengths of all the integers in the input list. Since $\ell$ and $s$ above are obviously no greater than $n$, we can substitute $n$ for $\ell$ and $s$ in our previous bound to get a weak bound of $O(n^2 \log n)$. A more detailed analysis can actually prove $O(n \log n)$, since each bit of the input is only used in one left-hand side of a multiplication.

However, if we also drop the $O(pq)$ multiplication assumption and assume only the guarantee stated in the question of $O((\max\{p, q\})^2)$, then trying to get a bound better than $O(n^3)$ requires a lot more fiddly reasoning about tradeoffs between element size vs. list size, and probably isn't worth it. [*]

The moral of the story: when analyzing an algorithm whose runtime is affected by multiple factors, state your definitions clearly, and use as many variables as necessary for a straightforward analysis unless there is a strong reason to lump things together.

[*] This is based on me thinking about the problem for all of 5 minutes. Maybe someone else can volunteer a proof of $O(n^2)$ under these assumptions, but I couldn't think of one.


I used the following book as a resource material and it was pretty good:

  Barron's AP Computer Science A

You can see the book preview there along with the contents.


Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$.
Of course there are plenty of other algorithms that balance the tree (they are also linked in the Wiki-article).


Question about the conditions to find articulation points in a graph

Here is the proof:
Given we have A -> B as an edge where A is not the root, let's assume A is an articulation point thats not the root. Removing it results in 2 subsets - the first containing the root and the second containing B.
For the subset containing B to be disjoint from the root if A is removed, B should not have a link to any node from root ... A that is it should not be able to reach a vertex higher than itself. This is possible only if:

A -> B is a bridge meaning the highest node reachable from B is itself
A is the only node B is connected to that is above it. This way if we remove A the highest node reachable from B is itself.


$\overline{SAT}$ vs. $UNSAT$, Is it the same?

They are not precisely the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has only formulas that are not satisfiable.
In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a poly-time reduction from $\overline{SAT}$ to $UNSAT$ and vice versa.


The nodes you are highlighting are a node and its child. The promise is that the heights of siblings don't differ by more than $1$. In other words, the promise is that for every node $p$, the heights of the children of $p$ differ by at most $1$ from each other.


Distance function such that we visit every "color region" once

Summary of your problem: You have a graph and a particular path through the graph, and you want to assign weights to the edges so that running Dijkstra's algorithm on that graph will give you that path.

Solution to your problem: assign a weight of 1 to each edge in the path, and a weight of $\infty$ (or some very large number) to each edge not in the path.  (It suffices to choose a weight that is larger than the number of vertices in the graph.)  You can easily verify that the shortest path only uses edges of weight 1 (any path that includes any other edge will have a total distance that is larger than that of the desired path).


Interpret bits as a signed integer in 2s complement

To convert a 4-byte = 32-bit word to its negative you apply the two's complement operator.  The operator is, as you said, invert all the bits, then add 1 to the word.

You can tell a 4-byte = 32-bit word represents a positive value if its most significant bit (the one all the way on the left) is "0".  If the most significant bit is a "1" then the 32-bit word represents a negative value.  Thus your example big-endian register, 01001101101101101111001111010111 must represent a positive number.

I assume you know how to convert a positive binary number to its decimal or hexadecimal equivalent.  The hexadecimal equivalent of 01001101101101101111001111010111, for example, is 0x4db6f3d7.

If, on the other hand the leading bit had been a "1", as in, (just making a number up): 11001101101101101111001111010111 that represents a negative number.  The negative of what positive number?  The positive number that you will get if you apply the two's complement operator.  Flip the bits and add 1.  So the negative of
11001101101101101111001111010111
must be
00110010010010010000110000101000
+                              1 =
00110010010010010000110000101001,
which is hexadecimal 0x32490c29
so
11001101101101101111001111010111 must be -0x32490c29.


This problem is in NP, because it is "exactly as hard" as SUBSET-SUM problem. Moreover, it is, in some sense, the SUBSET-SUM problem in disguise! Let's show that.
Denote the number of buckets by $n$, their capacities by $c_1 \leqslant c_2 \leqslant \ldots \leqslant c_n$ and the original quantities of water in them by $a_1, a_2, \ldots, a_n$ (here I assume without loss of generality that the buckets are sorted by their capacities). I claim that the following statements are equivalent:

There exists a way to get exactly $m \in [0, c_n]$ water in some bucket.
There exists a subset $S$ of $\{1, 2, \ldots, n\}$, such that $\sum\limits_{i \in S} a_i \equiv m \pmod{\gcd(c_1, c_2, \ldots, c_n)}$.

To prove the $1 \Rightarrow 2$ implication, let's notice that, at every moment of time, the quantity of water in each bucket can be expressed as "sum of $a_i$ over some subset of $\{1, 2, \ldots, n\}$" $+$ "some integer linear combination of $c_i$, with negative coefficients allowed". Indeed, we can check that all three allowed operations preserve this property. The latter part is divisible by $\gcd(c_1, c_2, \ldots, c_n)$, hence $m$ being possible to obtain implies the condition $2$.
The $2 \Rightarrow 1$ implication follows from the same type of the argument as I presented in the comments. I will reproduce it here for completeness. Indeed, suppose that $m \equiv \sum\limits_{i \in S} a_i \pmod{\gcd(c_1, c_2, \ldots, c_n)}$. Because $\gcd(c_1, c_2, \ldots, c_n)$ is representable as a linear combination of $c_i$, we can represent $m$ as an integer linear combination of $c_i$ and $a_i$, with all coefficients before $a_i$ being $0$ or $1$.
Clearly, it is enough to obtain $m \bmod c_1$ water somehow (after doing that, we can just repeatedly add $c_1$ of water). But, as long as we are interested in obtaining something only modulo $c_1$, we can replace all negative coefficients before $c_i$ in this sum with nonnegative ones (by adding $c_1$ appropriate number of times). Hence, we have a representation $m \equiv \sum\limits_{i \in S} a_i + \sum\limits_{i = 2}^n k_i c_i \pmod{c_1}$, where $k_i$ are some nonnegative integers.
Now, suppose that we have $x$ water in the $i$-th bucket and $y$ water in the first bucket. Then, we can get $(x + y) \bmod c_1$ water in the first bucket and make the $i$-th bucket empty. Indeed, try to move all the water from $i$-th bucket to the first. If $x + y < c_1$, then we are done. Otherwise, the first bucket is full now and the $i$-th bucket contains $x + y - c_1$ water. Empty the first bucket and repeatedly drain $c_1$ of water from the $i$-th bucket, until there is only $(x + y) \bmod c_1$ water left. Then move all the water to the first bucket.
By doing the operation from the previous paragraph for all $i$ in $S$, we can get $\left( \sum\limits_{i \in S} a_i \right) \bmod c_1$ water in the first bucket (if $1$ is not in S, we need to empty the first bucket beforehand). Now, for each $i$ from $2$ to $n$, repeat the same operation $k_i$ times, but now fill the $i$-th bucket before the operation. In the end, the first bucket will contain exactly $\left( \sum\limits_{i \in S} a_i + \sum\limits_{i=2}^n k_i c_i \right) \bmod c_1 = m \bmod c_1$ water.
Hence, this problem is equivalent to some kind of "modular subset sum", with modulo being equal to $\gcd(c_1, c_2, \ldots, c_n)$. As for NP witness, any witness for "modular subset sum" problem will do, for example the set $S$.
A more natural witness in the context of the original problem is a "compressed sequence of operations", in the sense that we allow commands of the type "repeat a given sequence of operations a given number of times". The proof above can be translated into such a witness, and a particularly simple one (no nested block commands, we repeat only some fixed short blocks, et cetera). I am not 100% sure whether it is possible to simulate a general compressed sequence of operations in polynomial time, but I am inclined to believe that the answer is "yes, it is possible". However, it is definitely possible to simulate sequences arising from the above proof quickly, though requiring that makes the witness much less natural.
Indeed, the second part of the proof constructs a sequence of operations of polynomial length, but with a catch that the following two "mega-operations" are also allowed:

Given a bucket with $x$ water, repeatedly drain it by $c_1$, till there is only $x \bmod c_1$ water left. The first (the smallest) bucket should be empty before this operation. This operation is used repeatedly thorough the proof
If we have $m \mod c_1$ water in the first bucket, empty the largest bucket, move $m \mod c_1$ water into it and repeatedly add $c_1$ water until there is $m$ water in the largest bucket. Used only once in the end.

These "mega-operations" correspond to some simple arithmetical operations on the quantities of waters in the buckets and $c_i$'s, hence they can be carried quickly in the model of computation we are using, despite the fact that they take very large number of elementary operations with buckets.


which Pipelining architecture, should i use and how to distinguish them!

In computer architecture, there is absolutely nothing that you must do. There are always compromises, everything has advantages and disadvantages, and advantages and disadvantages change over time.

If you learned about three different architectures to achieve the same goal, you first check how each architecture fits in with the overall design, and then you invent a fourth one that works better. Your tutor can only tell you how things were done in the past; you'll have to find yourself how things will be done in the future.


A term for two algorithms which give same results but differ in complexity

What you are talking about is very narrow, there is no term† that describes it exactly.

However, a closely related concept that you might be interested in is extensional equivalence as opposed to intensional equivalence. Intuitively, two objects are extensionally equivalent if they have the same external properties, and intensionally equivalent if they have the exact same definition.

Generally, mathematics and logic define equality as (some form of) extensional equivalence; for instance, the Zermelo-Fraenkel set theory includes some form of the following axiom:

$$
\forall x \forall y [\forall z (z \in x \Leftrightarrow z \in y) \Rightarrow x = y]
$$

Since functions are really relations, and relations are really sets, two functions that are point-by-point identical are literally the same function. But still, I believe that most of us would agree that even though quicksort and bubblesort are somewhat related, they are not the same thing.

So the real question here is what is the thing you call "the algorithm quicksort"? It's certainly more than just a program: quicksort written in C is not the same program as quicksort written in Haskell, but we would still call both quicksort. But at the same time it's not really just a function, defined by its input and output: in order to deserve the name "quicksort" you also have to operate in a certain way.

It's not a question I have a good answer for, there is no† precise and universal definition of "algorithm" (yet).

In the meantime, I would say that quicksort and bubblesort are extensionally equivalent but not intensionally equivalent.

† (or, at least, none I'm aware of)


What is the formal name for this algorithmic problem?

This general form of problem is a facility location problem. The specific version you're asking about is a covering problem – you have a set of points (the houses) and you're trying to cover them with circles of some radius (the areas that get reception from each tower).


Analysis of a recursive algorithm, where running time strongly depends on input

In order to determine an upper bound on $T(x,i,y)$, consider instead the recurrence
$$ T'(x,i,y) = \begin{cases} 1 & \text{if $x = 0$ or $y = 0$ or $i > n$} \\ x + y + \max_{\substack{0 \leq a \leq x\\ 0 \leq b \leq y}} S'(x,i,y,a,b) & \text{otherwise,} \end{cases} $$
where $S'$ is given by
$$ S'(x,i,y,a,b) = T'(x-a,i+1,b) + T'(x-a,i+1,y-b) + T'(a,i+1,y-b). $$
If you have more constraints on $a,b$, you should adjust the bounds in the definition of $T'$ accordingly.


Why this greedy algorithm fails in rod cutting problem?

Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, most optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.


Whether equivalence of different types of automata is of P-type?

The short answer to your question is that 1 is in P, and for 2 and 3 we don't know, but we strongly suspect that they are not in P.

In more detail, as you point out, checking whether two DFAs are equivalent can be done in P (by observing that DFAs are closed under complementation and intersection, and that $A\subseteq B$ is equivalent to $A\cap \overline{B}=\emptyset$).

As for checking equivalence of NFAs, we know that the equivalence problem is PSPACE-complete (by a simple reduction from universality of NFAs). This means that if the problem was in P, we would get P=PSPACE, which would be a huge and unlikely surprise.

Same goes for checking equivalence of regular expressions - the problem is PSPACE-complete. This post has more details on this


Computability - Can a Turing Machine calculate the input's length?

Yes, of course it can. As a simple intuition, replace "Turing machine" with "computer program" and the answer shouldn't change, assuming that the Church–Turing thesis is true.

Just use a portion of the tape after the input as a binary counter and shuttle back and forth increasing that counter by one for every character in the input, marking the characters that you've already counted.


IS $LOGSPACE\subsetneq QMA$ an open problem?

Widely open, I can tell. $\mathrm{QMA}\subseteq\mathrm{PP}$ is known. But, $\mathrm{PP}$ has been only separated from $\mathrm{uniform}$-$\mathrm{TC}^0$ up to now. So, even the stronger claim $\mathrm{L}=\mathrm{PP}$ is still unrefutable.

From the Wikipedia article https://en.wikipedia.org/wiki/PP_(complexity)#PP_compared_to_other_complexity_classes, $\mathrm{PP}$ strictly contains $\mathrm{TC}^0$, the class of constant-depth, unbounded-fan-in uniform boolean circuits with majority gates. (Allender 1996, as cited in Burtschick 1999)

Allender, E. (1996). "A note on uniform circuit lower bounds for the counting hierarchy". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science. 1090. Springer-Verlag. pp. 127–135

Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström Quantifiers and Leaf Language Definability". ECCC TR96-005


Using Myhill Nerode to prove that a language is not regular

Let $L$ be your language and let $\equiv$ be the equivalence relation defined by $x \equiv y$ iff $x \in \Sigma^*$ and $y \in \Sigma^*$ have no distinguishing extension (a distinguishing extension is a word $z \in \Sigma^*$ such that exactly one of $xz$ and $yz$ belongs to $L$).
Given $i,j \in \mathbb{N}$ with $i < j$, $0^i$ and $0^j$ cannot belong the same equivalence class since $1^i$ is a distinguishing extension for them: $0^i 1^i \in L$ but $0^j 1^i \not\in L$.
This shows that $L/\mathbin\equiv$ is not finite, and hence $L$ is not regular.


Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

Theorem B on page no. 272 of the book states that,

  if $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, then q ∈ [ q̂ - 2 , q̂ ].

Therefore, the algorithm is valid only when $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, which makes $v_{n-1} \neq 0$ obvious. To ensure this we need to multiply both u and v by a factor ${(= (base-1) / v_{n-1})}$.


Monte Carlo Algorithms : Are there any problems where two opposite Monte Carlo algorithms could solve it?

A Las Vegas algorithm is one which is always correct, but is only efficient in expectation. Given two "opposite" Monte Carlo algorithm, you can create a Las Vegas algorithm by alternating both algorithms (or running them in parallel), halting whenever one of them produces a certain answer.

In the language of complexity theory, this corresponds to the statement $\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}$. You can find more information on $\mathsf{ZPP}$ on Wikipedia.


In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | ...$, $a_i$s terminals

If a symbol is on the top of the stack, it must have gotten there after being pushed by the code just above the test:

        for each symbol on RHS #action do
            Push(symbol)

(There is a small imprecision in that code; it doesn't mention that "for each symbol on RHS" actually means "for each symbol on RHS from right to left" but that's evident from examining the example stack sequence.)

That code snippet, in turn, was executed after the parse table is used to decide which production will apply, which it did  by examining the next input token:

    if top is a nonterminal then
        action = ParseTable[top,NextInputSymbol]

So let's read the code forwards instead of backwards. We'll suppose that $A$ is on top of the stack, and that $A$ has productions as you indicate:

$$A\to a_1\\
A\to a_2\\
...\\
A\to a_n$$

Now, we can only push one of those productions. Which one will we push? By the construction of the $ParseTable$, we can say that we will push the production whose $FIRST$ set includes the next input symbol. But in this case, that's even simpler because the $FIRST$ set of each of those productions obviously comprises the single terminal on the RHS of the production. So if the next input symbol is $a_2$, for example, the ParseTable will indicate an action corresponding to $A\to a_2$. So the $A$ will be popped from the top of the stack and then $a_2$ will be pushed.

At the next step, the top of the stack is a terminal; precisely the terminal $a_2$. And, surprise!, the next input symbol is also $a_2$. So we can just pop the stack and continue with the parse.

In short, the $ParseTable$ lookup substitutes for that long imaginary sequence of if statements. The lookup could internally be implemented with such a chain, but in real-life it would probably turn out to be a more efficient table lookup algorithm.


When using the Pumping lemma, how do I deal with different cases of y?

To review, the PL says that if a language $L$ is regular, then there is an integer $p$ such that for any string $s\in L$ of length, $|s|\ge p$  we can write $s=xyz$ with

$|y|>0$
$|xy|\le p$
$xy^iz\in L$, for all integers $i\ge 0$

Assume your language is regular and select the string $ab^pab^pab^p$ to pump. Now, where can $y$ live? Since $|xy|\le p$ you know that $xy$ lives in the first $p$ or fewer characters of $s$, namely $xy=ab^k$ for some $k<p$. We then have two possibilities for $y$: it either contains the first $a$ or it doesn't, so we have two possibilities, where I've colored the string y:
$$\begin{array}{c}
(\color{red}{ab\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)\\
(a\color{red}{b\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)
\end{array}$$

Then for each case we argue thus:

$y$ is $ab^n$ (i.e., $x=\epsilon$), with $0\le n\le p$. Then $xyz=ab^pab^pab^p=(ab^n)b^{p-n}ab^pab^p$. Then $xy^2z=(ab^n)(ab^n)b^{p-n}ab^pab^p=ab^nab^pab^pab^p$. It's not difficult to see that this cannot be in $L$, so we've reached a contradiction.
$y$ is $b^n$ (i.e., $x=ab\dotsc b$). Then $xy^2z = ab^pb^nab^pab^p$ and again, this string can't be in $L$.

In all cases, we reach a contradiction, so our initial assumption, that $L$ was regular, was false.

By the way, it's easier to use the candidate string $a^pba^pba^pb$, since for this we only have one possibility for where $y$ could live, namely among the first string of a's.


Proving regular languages are closed under a form of interleaving

Hint. Because $L_1$ and $L_2$ are both regular, you know they're accepted by NFAs (or DFAs; it doesn't matter) $M_1$ and $M_2$, respectively. To show that $\mathrm{Interleave}\,(L_1,L_2)$ is regular, show that it's accepted by some NFA $M$. For each character it receives, $M$ can decide to act either like $M_1$ or like $M_2$.


Prove $T$ is a BST iff for every node $x$ of $T$ that is not a leaf, the key of $x$ is larger or equal than the key of the left child of $x$

The second direction is not always true, in a BST all elements in the right subtree of a node should have a key bigger than its key and all elements in the left subtree of a node should have a key less than its key. for example, consider this binary tree:

     4
   /   \
  2     6
 / \   / \
1   9 3   7

it has the property that for every node x of $T$ that is not a leaf, the key of x is larger or equal than the key of the left child and less or equal than the key of the right child, but it's not a BST since 3 is in the right subtree of root but its key is less than the key of root.


Showing the language of TMs that halt on a decidable set of words is not in RE

Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $L$. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

Run $M$ on the empty input.
If $M$ halts, interpret the input as a Turing machine and run in on the empty input.

If $M$ doesn't halt on the empty input, then the set of words on which $M'$ halts is the empty set, which is decidable, and so $M' \in L$. If $M$ does halt on the empty input, then the set of inputs on which $M'$ halts is HALT, which is not decidable, and so $M' \notin L$.


Why can there be no reductions from NP-complete problems to P problems under P ≠ NP

It would contradict the assumption that P$\,\neq\,$NP. You could solve the NP-complete problem in polynomial time by reducing it to a problem in P and solving that.


Question on "Hitting the memory wall, implications of the obvious"

You have it backwards. $t_m$ is what's growing exponentially relative to $t_c$. Or rather, $t_c$ is decreasing exponentially at a rate faster than $t_m$. $t_c$ and $t_m$ are the times the accesses take which gets smaller as the speeds improve. So, as the paper states, eventually memory performance, i.e. $t_m$ comes to dominate.

The "wall" is the point where having a faster processor, i.e. reducing $t_c$, makes essentially no difference to overall performance. The situation is an example of Amdahl's law. You are correct that things would improve as $t_m$ improves but look at the extreme scenario. Choose $t_c=0$, i.e. computation takes no time at all which is to say we have "infinitely fast" processors. Even with these magical processors, our programs would still run at some multiple of the memory bandwidth. In other words, at some point, if you have a slow program, buying a faster processor will not help. Or, put a different way, at some point, the exponential improvement in processor speeds will be meaningless. It will make no actual difference in program speeds.

And by "at some point", I mean a point we seemingly reached five or ten years ago. Modern (and not so modern) high-performance software design is significantly about, in the terms of this paper, reducing $1-p$. Many of the ideas suggested at the end of that paper have been adopted in some form. Multi-level memory hierarchies make even single processors look like non-uniform memory access architectures. Prefetching and careful data layout help increase cache hits, i.e. increase $p$. We're definitely much happier using designs that waste space if they can reduce cache misses. For example, if we have an object that optionally contains another object, we might store this as a dense array of pairs of the objects with a dummy object as the second when it doesn't exist. This is likely to reduce cache misses as compared to chasing pointers. (However, filling cache and/or cache lines with dummy data also can increase cache misses which is why this kind of design needs a lot of care.) Another way to decrease the effective $t_m$ and benefit from the extra computation speed is to store data compressed. When this saga unfolded with respect to disk v. RAM, it was faster to store inverted indexes for full-text databases utilizing compression and decompress them because the time spent decompressing the indexes was more than made up in the time saved in disk traffic. I can easily imagine a near future where RAM stores a compressed representation of, say, a cache line which gets decompressed transparently by the CPU.


How to generate stereo image pair from a stationary mono camera?

You can't.  You have video of the scene from a single vantage point.  Without depth information, you can't infer what the scene would look like from another vantage point.


There is not much hope in proving $BFS(G,u) = DFS(G,u)$ directly by mathematical induction on the number of nodes in $G$ or on the degree of $u$. The problem is that as an induction hypothesis that equality does not capture the "right" kind of information or cover the "right" cases that are useful for the induction step.
Approach one: the explicit description as reachable nodes
Instead, you can try proving separately that each side is equal to the set $R$ of reachable nodes from $u$, that is, $R=\{v\in V(G)\mid \mbox{ there is a directed path from } u \mbox{ to } v \}$. More specifically,
$$R=\{u\}\cup\left\{v\in V(G)\mid \mbox{ there exist } u_0, u_1, \cdots,u_n \text{ such that }u_0=u, u_n=v, u_i\in V(G) \text{ for } 0\le i\le n \text { and }(u_i,u_{i+1})\in E(G)\text{ for } 0\le i\lt n\right\}$$
You can prove the case of $DFS$ by mathematical induction on the total number of nodes of $G$. You can prove the case of $BFS$ by mathematical induction on the distance of $v$ to $u$. Or use whatever as you see fit.
Approach two: the characterization as nodes closed under neighbourhood
A set of nodes $S$ is said to be closed under neighbourhood if for any node $n$, $S$ contains the adjacent nodes of $n$. That is, if $n\in G$ and $(n, m)\in E(G)$, then $m\in S$. Here are the critical observations on both $BFS$ and $DFS$.
Lemma 1. $DFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $DFS$ does when it discovers a new node.
Lemma 2. $BFS(G,u)$ is closed under neighbourhood.
Proof: It becomes obvious once we check what $BFS$ does when it pops out a node from the queue.
Lemma 1 and 2 suggest us to consider the minimal set of nodes that contains $u$ and closed under neighbourhood. Name it $C(G,u)$. It is enough to prove that both $BFS(G,u)$ and $DFS(G,u)$ are equal to $C(G,u)$. We have shown both contain $C(G,u)$. It is easy to verify "the set of nodes visited so far are contained in $C(G,u)$" is an invariant of $BFS$ on $G$ starting from $u$. The same hold for $DFS$.


The classical example is sorting. For any constant-size alphabet, you can sort a string of length $n$ in time $O(n)$. However, for unbounded alphabets, the best you can do (under the comparison model, as well as some of its generalizations) is $\Theta(n\log n)$.


Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways that the input can continue. If this amount of information is not sufficient to answer correctly then the language is not regular.

For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).

One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).


Developing invariants for comparing two strings

I would not simplify $(2)$ at all. Just apply the rules for if, =, and command composition. Use weakening (pre- or post- rules) when convenient to do so.

Below, I added an empty else branch for clarity.

// (2): (S1 = S2 <=> X = Y \land E = true)
//            \land \lnot(X != /\ \land Y != /\ \land E = true)
if !(X == /\ and Y == /\)
  // (3a): (2) \land (X != /\ \lor Y != /\)
  // (3b): S1 != S2 \land false = false
  E = false
  // (3): S1 != S2 \land E = false
  // (4): S1 = S2 <=> E = true
else
  // (3c): (2) \land X = /\ \land Y = /\
  // (4): S1 = S2 <=> E = true
// (4): S1 = S2 <=> E = true
return E

Above, we used weakening, so we are left with proving:

$3a\implies 3b$. By contradiction, assume $\lnot 3b:\ S_1=S_2$ and $3a$. Since $S_1=S_2$, then by $2$ (part of $3a$) we have that $X=Y \land E=true$. We also know that at least one of $X,Y$ is not empty from $3a$, hence both are not empty since they are equal. This contradicts the last part of $2$, namely $\lnot(X\neq\Lambda \land Y\neq\Lambda \land E=true)$.
$3 \implies 4$. Two truths are always equivalent.
$3c \implies 4$. Replacing both $X,Y$ in $2$ with $\Lambda$, the first part of property $2$ immediately simplifies into $4$.

The first item can also be proved more formally, but I think you get the idea.

About your attempt: you used the equivalence

$$
\begin{array}{l}
\big((S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda)\big)
\\
\equiv (S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true)
\end{array}
$$

However, this does not hold in general, e.g. for $X={\sf x}, Y={\sf y}, S_1=\Lambda, S_2={\sf h}, E=true$. Or, more in general, when $X$ is non empty, and $S_1\neq S_2$. In such case, the former is false, but the latter is true.


How to Know Whether a Topic is Publishable in Computer Science

I'm not from this field, but I believe the following advice holds in any field.

First of all, I will suggest reading related literature; always a good idea. What do people in the field say about this topic? Is there an active community working on it? If not, you may find it hard to publish this work.

In my discipline it is quite acceptable to publish workshop papers. These do not "formally" count as a publication (they don't normally publish proceedings); however, your paper will get reviewed (not very deeply) and if accepted for presentation you will get even more feedback at the workshop itself. You can of course submit it to several workshops: this is perfectly acceptable practice, and I've seen it done with papers that contain only preliminary results.

What's more, this will tell you where your paper stands. If it gets rejected from a workshop on the topic, this is probably a good indication that it's not ready for publication yet.

Important note: it is absolutely fine to submit a paper to more than one workshop; it generally -not- acceptable to make concurrent submissions. That is, submitting to one conference before the outcome of a previous submission is decided. This is highly frowned upon in most communities I'm familiar with (tantamount to self-plagiarism), and will almost certainly make you look very bad. What's more, this will help you for two reasons:

It'll give you a chance to review the feedback you got from the reviewers, and possibly improve your paper.
Communities tend to be small; if you double-submit a paper, there's a non-zero probability that it'll be reviewed by the same people repeatedly (I have had the chance to review the same paper more than once, and I'm fairly junior in my field). Not only will you piss off anyone adversarial to your work by making them read it again, it will also indicate to them that you are not serious and are just "spamming".

So, submit your paper to one workshop, wait for the outcome, then submit to another.

Of course, the tradeoff here is that it'll delay the publication of the work. That said, you may want to acquaint yourself with the field and what's going on by going to a workshop or two, even if your paper is not accepted.

Another alternative is to simply send your working paper to a number of experts in the field and ask their opinion. My experience is that even prominent researchers will seriously answer such queries if the work is comprehensive enough.

Good luck!


Mostly, show that $L$ is decidable, mostly by designing an algorithm to decide it.


For a graph to be connected, you need at least n-1 edges rigorous proof

One way to prove this is by showing that a graph on $n$ vertices with $m$ edges has at least $n-m$ connected components. The proof is by induction on $m$. If $m = 0$ the graph is empty and no vertex is connected to any other. Now suppose that the claim is true for $m$ edges, and consider some graph with $m+1$ edges. Let $C_1,\ldots,C_k$ be its connected components. Choose some arbitrary edge $e = (x,y)$, and suppose that $e \in C_i$. Let $A$ be the set of vertices $v \in C_i$ for which there is a path from $x$ to $v$ not passing through $e$. Any vertex in $C_i \setminus A$ has some simple path to $v$ which passes through $e$. This path ends at $e$, and so there is a path from $y$ to $v$ not passing through $e$. This shows that both $A$ and $C_i \setminus A$ are connected even if we remove $e$. Other connected components are not effected by the removal of $e$ (since $e$ doesn't touch any of their vertices), and so if we remove $e$, the graph has at most $k+1$ connected components. The induction hypothesis shows that $k+1 \geq n-m$, and so $k \geq n-(m+1)$, proving the inductive step.

If a graph is connected then it has one connected component, so $n-m \leq 1$, that is, $m \geq n-1$.


There's two trivial answers:

No. For a problem to be NP-complete it must be in NP. To be in NP it must be a decision problem and promise problems aren't decision problems (they don't have to answer Yes or No on inputs outside the promise).
Yes. If you want to say informally that something is NP-complete (usually meaning "there's an obvious equivalent decision problem that is NP-complete"), then you can reformulate any decision problem as a promise problem just by taking the promise to be the set of sensible inputs. For example we can make a promise version of Dominating Set by taking the promise $L_{YES} \cup L_{NO}$ to be the set of all simple, undirected, unweighted graphs (so if you give it an input that's not a graph, it doesn't have to do anything in particular).

So there's no list of NP-complete promise problems because either none of them are (the strict answer), or you can just take any NP-complete problem and make a promise version.


What uses have been proposed for overlaid skewed associativity?

The following possible uses come to mind, though I am not aware of any academic exploration of these ideas.
Way Dueling
One possible use is to extend the range of set-dueling. Presented in Moinuddin K. Qureshi et al.'s "Adaptive Insertion Policies for High Performance Caching" (2007), the "Set Dueling mechanism dedicates a few sets of the cache to each of the two competing policies and uses the policy that performs better on the dedicated sets for the remaining follower sets." By linking policies with ways in an overlaid skewed associative cache the number of entries monitored can be extended without sacrificing capacity available to a given policy (though the associativity linked to a policy would be lower).
The number of policy-bound entries in a way could also be adjusted dynamically to trade off training sensitivity with associativity of the preferred policy. It is not clear if competition for the same entries would also have benefits; the degree of sharing of monitored entries could also be adjusted dynamically.
Virtual Non-Temporal Cache
With overlaid skewed associativity, it could be practical to associate one or more ways with non-temporal access and use indexing functions for such ways which induce conflicts. For example, by simply dropping bits 6..11 of the block number (indexing by bits 0..5,12..N), a 64-block region would conflict with itself 64-times in a stream. (By XORing specific middle and least significant bits, streams with power-of-two block-strides could be allocated densely while still providing self-conflict across groups of blocks.)
Such would have the advantage over a dedicated non-temporal cache of allowing the capacity to be used more flexibly and the advantage of potentially lower semi-reserved capacity compared to LRU placement of non-temporal data in a traditionally indexed cache (where effectively an entire way worth of data would be allocated to a stream of non-temporal data).
Since different ways (and different portions thereof) could have different degrees of inducing conflicts and less conflicting ways could be selectively used, the amount of capacity allowed to a stream could be somewhat flexible and conflicts between streams might be more easily managed.
While conflict-inducing indexing could be used with isolated ways, overlaying would allow capacity to be used more flexibly and allows conflict between ways to push out data that will not be re-referenced.
Variably aligned Blocks
By associating different ways with different alignments of cache blocks, larger blocks can be more practical when there is significant spatial locality but the chunk of data that is accessed together does not start at a highly aligned address. Such could facilitate the use of larger blocks with less unused capacity. Larger blocks can reduce tag overhead and increase the accuracy of way prediction (or the utility of way memoization).
Such might be especially useful for instruction caches (benefitting more from spatial locality and being more friendly to way prediction/memoization), especially branch target instruction caches. Certain trace-oriented pre-decode optimizations might be made more practical by reducing the number of entry points within a cache block. A smaller (faster, more energy-efficient) portion of an instruction cache could be preferentially used for branch targets, avoiding redirection delay like a BTIC but allowing the capacity to be used for non-branch target blocks.
(For data caches, unaligned storage might be useful for something like a signature cache, reducing the disadvantage of non-CAM tags.???)
Similarly, a branch target instruction cache placed after the instruction cache could exploit variable alignment of function entry points without the tag overhead of using multiple smaller blocks.
Stride-based Data Mapping
Similar to using ways to map to different alignments, it would also be possible to have different ways use different subblock strides. For example, a way could map data within a block such that alternating words are excluded, not only increasing utilized capacity when stride-of-two accesses are used but also potentially facilitating fixed-stride SIMD loads and stores.
It might even be practical to support configurable power-of-two strides as long as the stride does not change often.
(A data trace cache might benefit from both supporting different alignments and different chunk compositions (e.g., 32-bit address offset/compressed address vs. 64-bit address, address only vs. address plus N bytes of data). This ties in with intra-block NUMA.)
Binding storage-type to way groups
In a unified cache, one group of ways could be dedicated to instructions and another to data. Such grouping of ways would facilitate lower associativity in at least initial look-up.
This could also be applied to metadata interpretation, different ways storing different types of metadata. For example, some ways could use ECC (requiring read-modify-write on sub-word stores) and some use parity (for lower-overhead sub-word stores, but lower reliability); such could interact with storage reliability where, e.g., ECC-using blocks in high reliability SRAM might allow greater voltage reduction and parity-protected ways might only allocate clean blocks to less reliable SRAM arrays.
Way-based block size
While conventional non-overlaid caches could associate a tag with a pair of storage blocks, using additional ways dedicated to larger blocks would tend to require fewer tag checks. Skewed indexing, especially when overlaid, would reduce conflict increase from clumping of cached data have more spatial locality. In any case, extra tags could be used for dataless inclusion or other metadata, though the increased flexibility of allocation with overlaying would tend to increase opportunities for such alternative uses.
Variable Characteristics of Storage
By overlaying ways, a portion of each way can be mapped to a section of cache which provides faster (or more energy-efficient) access or different amounts of metadata (different types of metadata was mentioned earlier).
By increasing the independence of cache properties and data address via overlaid skewed associaitity, more direct indexing could be used while still supporting differences in characteristics of specific storage locations.
While not as flexible in allocation as a traditional Non-Uniform Cache Architecture (which uses a layer of indirection), such might make NUCA techniques more applicable to L1 caches. (The problem of scheduling dependent operations given variable L1 cache latency would still need to be addressed. In addition, the aliasing issues of L1 skewed associativity would have to be handled.)
(The way indication itself can provide some metadata when ways are reserved for or biased toward specific uses or policies.)
It might also be practical to have portions of the cache (whether specific ways or sections of various ways) use subblock NUCA where a portion of blocks have faster access (e.g., to accelerate pointer-chasing code). While always using fast subblock allocation (with different subblocks being selected by way and/or address) could be implemented in a somewhat straightforward way, variable allocation of fast storage (e.g., where 64-byte blocks might be mapped to four fast 16-byte storage units, one fast storage unit and three slow ones, or four slow storage units) would seem to be difficult.
Such separation could be accomplished in non-overlaid cache by the same association of way/address with cache characteristic, but flexibility of allocation would be lower.
Further Disconnecting Associativity and Capacity
With overlaying, conflict increasing squeezing of portions of ways can be mapped to different storage sections in different ways and accesses from different ways can compete for a given entry.
Partial overlaying provides another dimension of design flexibility. For example, a two-way associative cache might map one way such that half maps to an isolated section and half to an overlaid section and map the other way with its own isolated section (and the common shared section). This kind of partial overlapping might be useful for a Knapsack-like cache ("Knapsack: A Zero-Cycle Memory Hierarchy Component", Todd M. Austin et al., 1993) where a part of the storage could be dedicated to a restricted caching while another part can be used for other accesses as well (e.g., a two-way associative section could be used traditionally while also allowing the Knapsack region to be larger and somewhat sparse in the higher addresses; the amount of contention and the replacement preferences could be somewhat flexibly designed [some similarity might be noted to Brannon Batson and T. N. Vijaykumar's "Reactive-Associative Caches"]).
Isolated ways can provide separation of associativity and capacity by having some ways be smaller than others. However, overlaying provides slightly more flexibility in allocation of capacity. With isolated ways, a given block will always be in a higher conflict section (though this can be compensated by increasing the associativity of the smaller section).
Potentially Greater Virtual Machine Isolation
By overlaying and using different indexing functions for different virtual machines, cache capacity might be more readily provided to virtual machines with less side channel information being communicated.
Traditional skewed associativity with per-VM indexing adjustment would provide most of this benefit, but overlaying provides a little more flexibility in placement and in what mappings can conflict for different pairs of virtual machines.
Multithreading Conflict Containment
Partial overlaying could be used to isolate a portion of the data associated with a thread while still providing substantial capacity sharing. Such would provide more flexible allocation than assigning a traditional way or ways to a thread-specific storage area.
Partial overlaying would facilitate having higher associativity in a subset of cache, which could be advantageous in storage shared by more threads or used for allocations more likely to induce conflict misses or for which conflict misses are more expensive.
In a clustered design, overlaying could be useful for biasing placement to reduce inter-cluster communication when threads are biased or exclusively allocated to particular clusters.
Way Prediction Implications
While skewed associativity may increase the accuracy of partial-tag-based and recency-based way prediction (because spatially local blocks are likely to be mapped to different indexes for different address regions), overlaying may provide a slight further benefit.
(Likewise, biasing allocation to improve way prediction should increase the miss rate less with skewed associativity and especially overlaid skewed associativity than with simple modulo indexing.)
Defect and Block-locking Tolerance
While not a mechanism, it might be worth noting that using overlaying would reduce the impact of excluding certain blocks from allocation choices. While traditional skewed associativity increases conflict resistance in such cases, overlaying would provide a further benefit.
Similarly, locking a chunk of cache could provide the implementation simplicity of traditional way locking with less reduction in effective associativity. (As a side note, mapping a chunk of cache to a specific address to form a scratchpad memory would free the associated tag memory for other uses. For example, half normal size blocks could be supported for part of the remaining cache; overlaid skewed associativity might facilitate flexible allocation of small blocks.)
Reduced indirection overhead for NUCA
Using overlaying would allow different addresses to map to the same block, potentially avoiding the traditional indirection of traditional NUCA while still allowing substantial flexibility in allocation of cache entries into faster storage. Lack of indirection would facilitate placing tags closer to data clusters, at least for the faster storage area (it may be desirable to co-locate all tags to provide faster miss determination, though a cache shared by multiple cores or even just multiple access paths (e.g., instruction vs. data) might have distinct fast storage with associated tags). Even if indirection is used, overlaying would reduce the costs of less general indirection, reducing metadata storage overhead and potentially access latency.
A fixed but different slice for each way would have similar benefits in terms of allowing different addresses to be placed in fast storage with quick lookup, but overlaying increases allocation flexibility.


How do I measure the reliability of a confidence value in a predictive algorithm?

Measuring probability given a single occurrence doesn't really make sense, because the only data that can fit such a sample is 100% or 0%. If you have many samples, that is, if you have some sample distribution, then you can do some measuring.

For example, you could take the KL-Divergence as a measure (although it's not symmetric).

Once you have a certain reliability measure on your algorithm, you can update this data every time you have an additional sample, in an on-line manner.

If you have more details regarding the specific algorithm, or the specific type of predictions, you can probably tailor something that suits better your scenario.


If $A \leq_P B$ then since $P \subseteq P/\mathit{poly}$, also $A \leq_{P/\mathit{poly}} B$. This means that there is a function $f \in P/\mathit{poly}$ such that $x \in A \leftrightarrow f(x) \in B$. Since $f \in P/\mathit{poly}$, for every $n$ there is a polynomial size circuit $C$ that computes $f(x)$ for $x$ of length $n$. The circuit needs to have some mechanism for indicating the output length, which might depend on $x$.
Since $C$ has polynomial size, in particular, there are only polynomially many options for the output length, and so if $B \in P/\mathit{poly}$, these circuits can be connected to the outputs of $C$ in order to compute $A$.


What is the point of this lambda expression?

The “true” lambda calculus is defined by a syntax of terms:
$$
M,N ::= x \;\mid\; \lambda x.M \;\mid\; M\,N
$$
and a reduction rule called beta reduction:
$$
(\lambda x.M)\,N \to M[x \leftarrow N] \tag{$\beta$}
$$
(Plus context rules, plus the rules for alpha equivalence, but I'll omit them in this post.)

A lambda term is an object defined by the syntax above. What makes lambda terms interesting is the way they can be evaluated using the reduction rules.

It's possible, and common, to define extensions of the lambda calculus: languages that have additional syntactic forms and reduction rules. One common, simple extension is to add constants to the syntax of terms, and to add reduction rules called delta rules that allow evaluating these constants.

For example, we can define a new calculus which is the lambda calculus plus elementary arithmetic (LCPEA). If $n$ is a non-negative integer, I'll write $(n)_a$ for a constant in the LCPEA, so the LCPEA has constants $(0)_a$, $(1)_a$, $(42)_a$, etc. Note that what's in the parentheses is an integer, not a string: the constant is the same constant regardless of how the integer is written, so $(0)_a$, $(3-3)_a$, $(1+3-2*2)_a$, etc. are all the same constant.

$$
M_a,N_a ::= x \;\mid\; \lambda x.M_a \;\mid\; M_a\,N_a
        \;\mid\; (n)_a \;\mid\; \mathord{+}_a \;\mid\; \mathord{-}_a \;\mid\; \mathord{*}_a
$$ $$ \begin{align}
(\lambda x.M_a)\,N_a &\to M_a[x \leftarrow N_a] \tag{$\beta$} \\
\mathord{+}_a (n)_a \, (n')_a &\to (n+n')_a \tag{$\delta_+$} \\
\mathord{-}_a (n)_a \, (n')_a &\to (n-n')_a \qquad \text{if \(n \ge n'\)} \tag{$\delta_-$} \\
\mathord{*}_a (n)_a \, (n')_a &\to (n*n')_a \tag{$\delta_*$} \\
\end{align} $$

The delta rules directly translate the arithmetic operators into the LCPEA. So the LCPEA effectively contains elementary arithmetic. Note that these delta rules are necessary if we want the new constants we introduced to do anything useful. It would have been possible to define a different set of delta rules that caused $+_a$ to have nothing to do with addition and so on, but it would have been confusing.

It turns out that it is possible to define pure lambda terms (i.e. terms in the true lambda calculus) that reduce in the same way as corresponding terms in the LCPEA. That is, we can define a lambda term $\langle n\rangle$ for every natural integer $n$, as well as lambda terms $\langle\mathord{+}\rangle$, $\langle\mathord{-}\rangle$ and $\langle\mathord{*}\rangle$ such that
$$ \begin{align}
\langle\mathord{+}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* \langle n+n'\rangle \\
\langle\mathord{-}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* (n-n')_a \qquad \text{if \(n \ge n'\)} \\
\langle\mathord{*}\rangle \, \langle n\rangle \, \langle n'\rangle &\leftrightarrow_\beta^* (n*n')_a \\
\end{align} $$
The Church numerals are a classical example of a set of such terms; there are others.

There are several reasons why we may want to define something like the LCPEA.

One is that it is closer to how machines behave; this is important when using the lambda calculus to model compilers, but not when doing theory of computation.
Another reason, applicable even when doing theory of computation, is that we often don't care exactly how the integers are encoded. So we might define things like $\langle 3\rangle$ and $\langle\mathord{+}\rangle$ as lambda terms, and then forget their precise definition and just remember some reduction rules for them. So they're still pure lambda terms, but we treat them as if they were part of an extended language.
In a typed lambda calculus, encoding everything as functions is problematic, because we'd like to say that something like $1$ is “inert”, not like a function, and to say that $1 \, 2$ (“1 applied to 2”) is not well-typed and does not reduce to anything. With the pure lambda calculus, $\langle 1\rangle \, \langle 2\rangle$ does beta-reduce to something, but not to something useful. When we extend the language with constants, we don't define any reduction rule that would reduce $(1)_a \, (2)_a$.
There are extensions of the language that cannot be encoded as lambda terms at all. If we're interested in studying these, we have to extend the language.


Does UDP always deliver packets inorder to the application layer

Conversely from TCP, UDP does not guarantee a reliable or ordered delivery of the packets.
As the RFC states:

  This protocol  provides  a procedure  for application  programs  to send
  messages  to other programs  with a minimum  of protocol mechanism.  The
  protocol  is transaction oriented, and delivery and duplicate protection
  are not guaranteed.  Applications requiring ordered reliable delivery of
  streams of data should use the Transmission Control Protocol (TCP)

Indeed, if you look at the UDP header there is nothing such as Sequence Number or Acknowledgment Number.

             0       7 8     15 16    23 24      31
             +--------+--------+--------+--------+
             |     Source      |   Destination   |
             |      Port       |      Port       |
             +--------+--------+--------+--------+
             |                 |                 |
             |     Length      |    Checksum     |
             +--------+--------+--------+--------+

Note also that using UDP does not mean that an ordered delivery of packets to the application layer cannot be achieved.
Indeed, UDP can be used in conjunction with an upper layer protocol that adds additional information, such as the sequence number.
See, e.g., RTP which is a Session layer protocol (OSI model) or Application layer (TCP/IP model).


What does floating point biased notation have to do with 2's complement?

IEEE 754 Floating point is a standard way of representing fractions in binary which does not use two's complement.  There's a discussion here about why that is.


Determining if an integer appears more than $n/2$ times

You are asking two questions. I will only answer the second one. Consider the following set of possible inputs: the array is contains either $n/2$ or $n/2+1$ copies of $0$, all elements preceding it are $-1$, and all elements following it are $+1$.

I claim that any algorithm which works correctly for this set of inputs must query, in the YES instances, the first and the last position of the stretch of zeroes. Indeed, if it never queries the first position for example, then the input could have been the NO instance in which the value at that position is replaced by $-1$.

Since the first and last position of zero are at distance exactly $n/2$, and are the only two positions at that distance of equal value, we see that any correct algorithm for your problem can be modified (without any additional comparisons) to give an algorithm for the following problem:

  Given an array consisting of $n/2+1$ zeroes, preceded by $-1$ entries and followed by $1$ entries, find the location of the zeroes.

Since there are $n/2$ different answers to this problem, the usual decision tree argument shows that any comparison-based algorithm must make $\log_3 n - O(1)$ three-way comparisons, or $\log_2 n - O(1)$ two-way comparisons of the form "$x=y$ or $x \neq y$?". This shows that for two-way comparisons, your algorithm is nearly optimal. (Note that $2\log_4 n = \log_2 n $.)


Algorithm To Process Purchases Efficiently and Apply Constraint

The algorithm I posted above doesn't work. It's the same as trying to load all the file upfront which blows up as the heap memory is exhausted.

Another solution would be to sort the file before processing it. The UNIX sort command is able to sort files much bigger than the RAM available on the machine. It does this using external sort I believe.

So my new solution is to sort the file first on the customerId. This ways a one pass can be done on the file and the data for each customer calculated on the fly. As each customer is encountered in order, before computing the next customer's data the memory consumed for the previous customer is freed.


An SDP relaxation is not an arbitrary optimization problem; rather, it consists of optimizing a linear function over semidefinite and linear constraints. One general formulation of SDP is
$$
\begin{align*}
&\max \sum_{ij} c_{ij} x_{ij} \\
s.t. \;\;& X \succeq 0 \\
& A \mathbf{x} = \mathbf{b}
\end{align*}
$$
Here $X$ is the matrix whose entries are $x_{ij}$, and $\mathbf{x}$ is a vector whose entries are $x_{ij}$ (in some arbitrary order).

Standard accounts on semidefinite programming should explain why the SDP relaxation that you describe can indeed be formulated in this form. In short, the idea is that $x_{ij}$ is going to represent the inner product $\langle \vec{x}_i, \vec{x}_j \rangle$. The fact that $X$ is positive semidefinite is equivalent to the existence of such vectors $\vec{x}_i$. The objective function $\sum_{(i,j) \in E} \|\vec{x}_i - \vec{x}_j\|^2$ can be written as a linear combination of the $x_{ij}$, and the constraints $\|\vec{x}_i\| = 1$ can be written as linear constraints on the $x_{ij}$.

Why do we care about semidefinite programs? Because we know that they can be solved (approximately, but arbitrarily well) in polynomial time. This is not true for an arbitrary optimization problem.

There is some evidence that the Goemans–Williamson constant $0.878$ is best-possible for polynomial time algorithms. Namely, this is the case if Khot's Unique Games Conjecture holds. Under this conjecture, Raghavendra showed that SDP relaxations are optimal for a wide class of problems (constraint satisfaction problems).


Proving specific prefixes of regular languages are regular

Basically, you do not compute these lengths $2^n$ or $n^2$, but only the from-to computations that the automaton would be able to make on input with this particular lengths.

For the first two problems the automaton computes (in its internal states) the relation $E_\ell = \{ (p,q)\in Q\times Q \mid q\in\delta^*(p,y) \text{ for some $y$ with $|y|=\ell$} \}$ for some value of $\ell$ (which depends on $|x|$).

Then $E_{2\ell}=E^2_\ell$ which helps to solve the first problem. Here $E^2$ is the composition $E\circ E$ of the binary relation $E$ with itself: $E^2 = \{ (p,r) \mid \text{ for some } q\in Q \text{ both } (p,q)\in E \text{ and } (q,r)\in E\}$

I add some details. This is still rather formal, without much intuition. I hope it helps you into the right direction.

Assume we are given a FSA $\mathcal  A= (Q,\Sigma,\delta,q_0,F) $ for language $A$. We will construct an automaton for your first problem.

The new states are of the form $(p,E)$ where $p\in Q$ and $E\subseteq Q\times Q$; i.e., the new state set equals $Q\times{\mathcal P}(Q\times Q)$.
Note that the number of possible relations $E$ is finite, hence adding such a relation to the states of the automaton will still lead to a finite state automaton.
The second component will always contain the relation $E_{2^n}$ where $n$ is the length of the input read.

The initial state equals $(q_0,E_1)$, where $E_1$ is the one-step relation on $Q$, just like defined above.

Now from every $(p,E)$ reading letter $a$ we move to state $(\delta(p,a),E^2)$. Thus, the first component copies the original move in $\mathcal A$, the second component steps from $E_{2^n}$ to $E_{2^n}\circ E_{2^n}=E_{2^{n+1}}$ following the recipe above.

When is a state $(p,E)$ final? When there is a pair $(p,q)\in E$ such that $q\in F$ is final in $\mathcal A$.

The $n^2$ problem is along similar lines, but actually slightly more involved (I think). It uses the fact that $(n+1)^2 = n^2 + 2n +1$. The automaton stores both $E_{n^2}$ and $E_{n}$ to easily update the square.


how do you prove that SAT is NP-complete?

I believe 3-SAT was originally reduced from the more general SATISFIABILITY in Karp's paper that outlined 21 NP-complete problems.

Wikipedia has a description of how to show that SATISFIABILITY is NP-complete, a result that's known as the Cook-Levin theorem. The idea of this proof is to show that any polynomial time nondeterministic Turing machine can be modeled as a boolean expression with polynomial size. The boolean expression has terms to represent the valid configuration space of the Turing machine: where the tape head is, what the current state is, what symbols are written on the tape, and what transitions are valid at every position. Because the NTM will halt in polynomial time, the configuration space is bounded and we can make a (large) polynomial expression to represent it.


How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

I do not think you can use formula (14) on page 5 of 'How to construct polar codes'. I think you want to compute Bhattacharyya parameters after channel polarization. Hence, you need to compute transition probabilities of synthesized channels firstly, and then compute Bhattacharyya parameters using formula (14) on page 5 of 'How to construct polar codes'. The formula of transition probabilities of synthesized channels is give by Arikan in his TIT paper, but it is not easy to implement it.


Regarding time complexity of multi-tape Turing machines

Multi-tape Turing Machine running in $O(f(n))$ can be simulated by a single-tape Turing machine running in $O(f^2(n))$.

Try writing a single-tape Turing machine that stores symbols from your $3$ tapes on its one tape, separated by some unique symbol not in $\Sigma$.

hint: For every step of your $k$-tape machine, a one-tape machine must first do at most $k\cdot n$ steps to find the position.