Can reversing the final and non-final states of a DFA produce the complement of the original language?

In DFAs, the path taken in the automaton are deterministic and reach one specific state, so all the strings in the language reach one accepted state and all the other strings on this alphabet reach non-accepting states. Switching the accepting and non-accepting path is equivalent to saying "accept every string that doesn't reach an accepting state in the original automaton, don't accept any string that reach an accepting state in the original automaton", in short, "Not in the language L of the original automaton", which is the complement of L.

In NFAs, it is quite easy to find contradiction to show that this statement is incorrect.

Consider the following 2-state NFA with the alphabet {a, b}:

state 1 (starting state, accepting state):
  input a -> go to state 1
  input b -> go to state 2

state 2:
  input a -> go to state 1 and 2
  input b -> go to state 2

The string "aaba" is accepted by this automaton. If we switch the accepting states, this string is still accepted by the automaton, and thus the two languages can't be the complement of each other.


What is the exact meaning of a Predicate, decidability and computability?

There is an unfortunate clash of terminology here. Before exposing it, let me just mention that decidable and computable are synonyms. You mention several concepts, including:

Partially computable: A partial function which is computed by some program that doesn't necessarily always halt.
Partially decidable (terminology I personally have never heard): A language (i.e. set of words) that is enumerated by some program.

These are different concepts. Partial computability is a property of (partial) functions. Since languages can also be viewed as predicates, partial computability can also apply to languages, though this is somewhat misleading, since a partially computable predicate is always computable.

Partial decidability, usually known by some of the other names you mention, is a property of languages. Partial decidability can also apply to predicates by considering the language of all input tuples satisfying the predicate.

The halting problem itself has many variants, of which you mention two:

The halting predicate $HALT(x,y)$, true if the program encoded by $x$ halts on input $y$.
The halting problem, which is the language of all pairs $(x,y)$ such that the program encoded by $x$ halts on input $y$.

The halting problem is a language whose corresponding predicate is the halting predicate. Both are partially decidable but not partially computable or computable.


You have the right idea but I think you are overthinking it a bit.

For a), your teacher had a good hint.   I think there is a simpler solution than the way you are going. As a further hint, notice that if $k=2$, the problem is solved after 1 round of quicksort (with linear median-finding).  You have two equal-sized subarrays, where the left is smaller than the right.  Can you extend this to $k=4$?  Then, can you extend it to arbitary $k$?

b) I think you have the right intuition, but this argument is not formal yet.  Recall the original proof of the sorting lower bound, where you argue that you need $n\log n$ comparisons to get  $n!$ permutations.  Can you extend that to this case?  How many permutations are required when we don't need to fully sort?


Depth-first search or Breadth-first search. Note that Dijkstra's algorithm, essentially reduces to breadth-first-search with equal-cost-paths.

You can also do a sort of meet-in-the-middle (known as a bidirectional search), starting a search from both ends.

Any algorithm for detecting connected-components will work here as well (again, these essentially using one of the search algorithms and adding connected nodes to some collection). However, you can perhaps use the some sort of disjoint-set-data-structure to keep track of different components as you add "lines" into the graph, and thus quickly test if the component of $A$ is the same as $B$. See also: connected-component labeling, and partition refinement.

If your nodes have a special structure, you might be able to take advantage of it. For example, if you are thinking of nodes in euclidean space, you can use a spatial-index, such as a quad-tree, to speed the traversal/search by traversing whole globs of nodes in one shot when it is far from a line/obstacle. Another example would be to use A*, even if you don't care about shortest-path, it might be better than simple breadth-first/depth-first, because of the structure and heuristic you can provide (see best-first search and beam-search).

EDIT:

I thought of another formulation of the problem (which likely would use one or a combination of the above approaches): Is there an online-algorithm to keep track of components in a changing undirected graph:

  Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
  for Connectivity, Minimum Spanning Tree, 2-Edge,
  and Biconnectivit (PDF).
  Near-optimal fully-dynamic graph connectivity (PDF)


Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

The comment of @Yuval tells the intuition behind the answer (the shortcoming of a PDA is that you can iterate only once over the word and you cannot read the second letter in the stack before popping the first one, note that you can keep only constant amount of data in the state).

However, a very concise formal proof why we can not simulate all Turing machines with PDAs is that you can build to each PDA a corresponding context free grammar such that a given word  is accepted by a given PDA if and only if it can be constructed with the corresponding grammar source.

Now since CFL is a proper subset of CSL which is again a proper subset of recursive languages which all can be decided by Turing machines, Turing machines can simulate all PDAs but not vise versa. To see why, for a given recursive but not context-free language, say the standard example $a^nb^nc^n$, there is no PDA to compute this language since else there would be a context free grammar to compute it which would make it CFL. On the other hand it is not hard to build a Turing machine that decides this language.


Derandomize MAX-CUT problem using $\log n$ bits

Consider a graph with $n$ vertices and $m$ edges.

Let $\mathcal{D}$ be a pairwise independent distribution over $\{0,1\}^n$, and suppose that $x = (x_1,\ldots,x_n) \sim \mathcal{D}$. For every edge $(i,j)$, the probability that it is cut in the cut corresponding to $x$ is
$$
\Pr[x_i \neq x_j] = \frac{1}{2},
$$
due to pairwise independence. Therefore the expected number of edges cut is exactly $\frac{m}{2}$, by linearity of expectation. In particular, there is at least one realization of $x$ (that is, one point in the support of $\mathcal{D}$) which cuts at least $m/2$ edges.


Distributive property with sum types and product types

Polynomial types (those obtained through $+,\times,0,1$ and type variables) form a commutative semiring.

Basically, all the elementary arithmetic laws for $+$ and $\times$ hold as expected, up to (natural) isomorphism. These include commutativity, associativity, and distributivity of $\times$ over $+$.

More concretely, the distributive law is
$$ (A\times C)+(B\times C) \simeq (A+B)\times C$$
and I think this was the law that Philip Wadler meant to show.


You need to prove by induction the following claim:

  Let $T$ be a tree rooted at $r$ with at least two vertices. You can list the vertices of $T$ in a sequence such that the distance (in $T$) between two adjacent vertices (including the first and the last) is at most $3$, and furthermore the vertex following $r$ is adjacent to $r$ (in $T$).

(The induction is on the number of vertices.)

Given this, you argue as follows. Suppose that there is a Hamiltonian cycle with heaviest edge having weight $w$. Then there is a spanning tree whose heaviest edge has weight $w$. So the heaviest edge in the bottleneck spanning tree has weight at most $w$. Apply the claim to that tree, and consider the corresponding Hamiltonian cycle. Since the tree distance between adjacent vertices is at most $3$ and thanks to the triangle inequality, the heaviest edge in the resulting cycles weighs at most $3w$.


complexity of outputting the union of a collection of subsets of a set

That's not possible.  Any correct algorithm will have to read all of the input.  The input size is $\Theta(mk)$, so that means any correct algorithm will have to have running time at least $\Omega(mk)$.  $O(m+k)$ and $O(m+k) p(\log(m+k)))$ are not achievable.


An associative dictionary is any data structure which maps keys to values. Binary search trees, hash tables, and B-trees are all examples of associative dictionaries. It is incorrect to say that an associative dictionary must be a binary search tree.
Similarly, a priority queue is any data structure which allows insertion in any order and removal in priority order. A binary heap is an example of a priority queue, but it is incorrect to say that a priority queue must be a binary heap.
There are lots of other data structures which implement priority queues, including n-ary heaps (for n greater than 2), binomial heaps, Fibonacci heaps, Brodal queues, van Emde Boas trees, and many more besides.
And that's leaving aside the issue that a binary heap doesn't strictly need to be stored in contiguous memory. Any storage scheme can be used as long as it can be indexed like an array and supports $O(1)$ access time.


Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

Unfortunately your grammar generates mixed $1$s and $2$s.
You can try something like this:
$S\rightarrow 0SB | S'$
$S' \rightarrow 0S'A | \varepsilon$
$A\rightarrow 1$
$B\rightarrow 2$
Notice that I don't know if in your problem $n$ can be $0$ or not (and similarly for $a$ and $b$), so maybe you have to fix something.
Anyway, here the idea is starting generating first some $0$s an all the $2$s, and then add the remaining $0$s and the $1$s: it is similar to the "standard" grammar used to generate $0^n 1^n$.


Analogy between Gödel's incompleteness proof and Richard's argument

Both examples are instances of diagonalization, a technique also used to prove Cantor's theorem ($\kappa < 2^\kappa$ for all cardinals $\kappa$) and Turing's theorem that the halting problem is undecidable.

An analogy is by nature informal. It is not supposed to be rigorous.


The same hardness assumption that implies P=BPP also implies NP=MA (at least according to the complexity zoo).

Even if the hardness assumption is wrong, separating NP from MA would be a huge achievement, since it would imply that P is different from NP (as MA is in the polynomial hierarchy).


Time complexity of DFS and recurrence relation

For an implicit graph  the recurrence can be written as follows:

Let $b$ be the number of branches of every node (assumed to be constant)

let $d$ the depth of the graph

For depth 1 there are $b$ branches:

$T(b,1) = b$

For the next levels it can be written as

$T(b,d) = b + b*T(b,d-1)$

where $b$ are the nodes at this level, and are the $b*T(b,d-1)$ nodes at next level.

If you substitute the definition for $T(b,d-1)$ you get

$b * (1 + b*(1+T(b,d-2)) = b + b^2(1+T(b,d-2))$

If you further substitute the definition of $T(b,d-2)$ you get

$b + b^2(1+b+b*T(b,d-3)) = b + b^2 + b^3 + b^3*T(b,d-3)$

If you continue to expand you get

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*T(b,1)$

Since we know that $T(b,1) = b$, we can substitute

$T(b,d) =  b + b^2 +b^3 +... + b^{d-1}*b$

Thus

$T(b,d) =  b + b^2 +b^3 +... + b^d$

Using Big-O Notation. $O(b^d)$

For explicit graphs with $V$ vertex and $E$ edges

We assume you have an adjacent list. That is for every $V$ you have a list of adjacent edges. You can think of a Table of $E$ edges (columns) x $V$ vertex (rows).

We can write our recurrent relation based on the navigation of that table.

$T(V,E) = 1 + e_0 + T(V-e_0,E-e_0)$

We count $1$ for visiting the first row, and $e_0$ for the number of edges adjacent to that first vertex.  For the next rows we use the recurrent relation except this time we have $V-e_0$ vertex and $E-e_0$ edges to visit.

If we substitute our definition for the 3rd. element in our relation we get:

$T(V,E) =  1 + e_0 + 1 + e_1 + T(V-e_1,E-e_1)$

if you keep expanding you get

$T(V,E) =  1 + 1 + .. + 1 + e_0 +e_1 + .. + e_V$

1 for every row visited and a certain number of edges for a given vertex.  In total the number of edges is $E =e_0 + e_1 + .. e_V$.

$T(V,E) =  V + E$

in Big-O Notation $O(V+E)$.


CRC computation speed vs polynomials features

The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 for X86 processors (pclmulqdq using xmm registers) the multiply time is fixed. For a typical hardware implementation, since the multiply is carryless, there's no propagation delay related to carry operations and all the XOR operations occur in parallel.

For standard multiplies (with carry), old processor multiply times were affected by the weight of the multiplier, but multiply times on processors since around 2010 or a bit before have fixed multiply times (for X86, it's 3 clocks). I'm not aware of a carryless multiply that isn't fixed in time, but it could exist on some processor I'm not aware of.


Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$

Since $10$ is relatively prime to $M$, it has an inverse modulo $M$, which can be found efficiently using the extended GCD algorithm. So you can simply calculate $X = -10^{-L}D$ (all computations modulo $M$).


Transition systems that satisfy LTL but not CTL, and vice versa

Technically, LTL and CTL are incomparable in their differentiating power over Kripke structures. So intuitively, it shouldn't be easier to design one or the other.

However, most people tend to find it easier to think in linear time. Making sure a certain property holds for all paths is easier than studying a branching-time property. In particular, this is because a counter-example for the satisfaction of an LTL formula is a path, whereas a counterexample for a CTL formula may be a tree.

To demonstrate how to approach the questions at hand, let's consider the first one. First, consider what the formulas mean:

$FGp$ means "in every path, after a finite prefix, $p$ always holds".

$AFEGp$ means "in every path, after a finite prefix, a state is reached from which there exists a path in which $p$ is always true."

Now, if $FGp$ holds, then $AFEGp$ must also hold, because in every path, eventually a state is reached from which $Gp$ holds. Thus, our search should restrict to finding a system which satisfies $AFEGp$, but not $FGp$.

To achieve this, we need to at least have a state that satisfies $Gp$, so let's start with that. Take the state $A$ to have the transition $A\to A$, and $A$ is labeled with $p$. Let's also have $A$ as the initial state (this is arbitrary). So far, this system also satisfies $FGp$, so now we fix that by adding a "bad path": we add a state $B$, labeled by $\neg p$ with the transitions $A\to B$ and $B\to A$.

The path $A,B,A,B,...$ does not satisfy $FGp$, so this is good. However, every path eventually reaches $A$, in which $EGp$ is true, so $AFEGp$ holds, and we are done.


What are the concequences of the unit type and the unit value being the same?

You have been confused by Haskell's notation. The unit type and unit value are of course different, and it just happens that Haskell uses the same notation for both.

As for the consequences: there are none. Notation is irrelevant here. You can call the unit type Dog or BauwnNuYwvb (i.e., nonsense), and it won't change the type system.


What's the difference between subtyping and inheritance?

See the following discussions in other stack exchange groups.

See discussion in https://stackoverflow.com/questions/23592131/what-is-the-difference-between-subtyping-and-inheritance-in-oo-programming

Also see https://cstheory.stackexchange.com/questions/10620/how-does-inheritance-differ-from-subtyping

However there is some differences of opinion. See Inheritance Is Subtyping as well as Inheritance Is Not Subtyping


When and what must be present on the left-hand side of the turnstile in metalogics?

Perhaps what you're missing (although you seem to suspect) is that the left hand side of the $⊢$ is not just for specifying what types variables have. In fact, as you've noted, it doesn't necessarily have all (or only) the variables on the right hand side (although in this situation it does only have variables, not things like $λy.x : α→β$).

What it's doing is keeping track of what are sometimes called the "free variables" on the right hand side, along with their specified types. The idea is essentially that there are actually no free variables in this formalism; variables are either bound by a $λ$ or in the context $Γ$. The lambda introduction rule:

$$\begin{array}{c}Γ(x:τ) ⊢ e : ρ \\ \hline Γ ⊢ λx.e : τ → ρ\end{array}$$

moves a variable from being bound in the context to being bound by a lambda. In some presentations this might even be written $λx:τ.e$ to still be explicit about what type $x$ has, but this is not really necessary when working with a derivation where the type is already recorded in the judgment (and there are other situations as well).

Of course, variables can go in the context even if they don't occur on the right hand side, like $y$ in your example. This allowed writing a constant function that doesn't actually use its argument.

One way to think about this is to read the tree bottom to top. We want to verify that $λx.λy.x$ has type $α→β→α$. The way we do this is to start in the empty context, and move upward. We use the lambda introduction rule to push lambda-bound variables into the context with an appropriate type, and eventually verify that $$x:α,y:β⊢x:α$$ holds. This is maybe more obvious if the variable rule has a line above it, allowing you to create a completed tree:

$$\begin{array}{c}\\
  \hline x:α,y:β⊢x:α \\
  \hline x:α ⊢ λy.x : β→α \\
  \hline ⊢ λx.λy.x : α→β→α
  \end{array}
$$

The root of the tree is our goal at the bottom, and the leaves at the top are all empty lines. $Γ$ is the local context in which we are verifying the inner parts of the lambda term, and its content is actually motivated by wanting to move under the lambda and verify the type of its body; it contains the variables and their types that have been brought into scope in that process.


What should be the way to design code for such a situation?

Off the top of my head...

Given a Packet, encode both the slot and count into the number
with known limits.... a code can be computed ...
and both the Sender and Receiver know what the limits are.

For example: 5 slots, and 7 possible counts (max count from 0..6 is 7 )

A CODE to determine what slot and count in that slot when it arrives

Code = Count_in_slot + (slot_number * (Max_Counts ) )

   Table of example CODES that could be sent or received

Slot            n counts
       0   1   2   3   4   5   6
      --- --- --- --- --- --- ---
 0     0   1   2   3   4   5   6
 1     7   8   9  10  11  12  13
 2    14  15  16  17  18  19  20
 3    21  22  23  24  25  25  27
 4    28  29  30  31  32  33  34

Decode a Slot  and count from the number :

 Sequence Initialize all ZERO's

 for each Code received
   temp  = Code
   Count = temp mod max_count  (NOTE: Remainder of a division (Modular math )
   temp  = temp \ max_count    (NOTE: integer divide)
   Slot  = temp mod Number_of_slots
   Sequence(Slot) = Count

And when either all slots are received, or max time wait occurs the reconstructed sequence is completed.

ALSO NOTE:
 If time delay is used to close the sequence, then slots with ZERO do not need to be sent.


Decidability of halting problem for DPDAs with $\epsilon$-transitions?

Let $L_1$ be the language of all $(M, p, y)$ such that if we start $M$ (a DPDA with $\epsilon$ transitions) in state $p$ with a stack consisting of only $y$ (which is either a single symbol or nothing), then reading an empty string as input would cause $M$ to eventually return to state $p$, with a $y$ on top of its stack if $y$ was a symbol rather than nothing (if $y$ was originally nothing, we don't care about what's on the top of stack after $M$ returns to $p$; anything is fine).
claim: $L_1$ is decidable.
proof: modify $M$ as follows: make a copy $p_0$ of $p$ with the same outgoing transitions but no incoming transitions, and start the DPDA in $p_0$ with a symbol $y$ (or empty) in its stack. If $y$ is empty, then make $p$ the only accept state. Otherwise if $y$ is a symbol, then after creating $p_0$, modify the outgoing transition of $p$ with $y$ on the top of its stack to instantly go to a state $w$ that is now the only accept state (see note 1). Now use the standard CFL emptiness decider on this modified DPDA and we are done.
Note 1: If there is no such transition to modify due to determinism of $M$, i.e. $p$ only has one outgoing $\epsilon$ transition that either does nothing or pushes some symbol onto the stack, then do the following instead: delete the transition, add one that pops $y$ and goes to $w$ and also add trivial no-op transition that pops then immediately pushes back all other symbols that are not $y$.
Next, let $L_2$ be the language of all $(N, q, x)$ such that if we start the DPDA $N$ in state $q$ with a stack having only a single symbol $x$ (or empty), then with an empty input string, it will run forever without ever attempting to pop an empty stack. Note Sipser calls $(q, x)$ a "looping situation".
claim: $L_2$ is decidable (Sipser third edition problem 4.32 asks to prove this)
proof: take $N$ and delete all its input-reading transitions (leaving only $\epsilon$ transitions). Then, start $N$ in state $q$ with an $x$ on its stack, and for every state $p$ it enters, take its stack top $y$ and run the decider for $L_1$ on $(N, p, y)$. This procedure is guaranteed to terminate in either an accept for $L_1$ for some $p$ and $y$, or $N$ itself will terminate (either by attempting to pop an empty stack or by running out of $\epsilon$ transitions to follow). (Why?  Suppose $N$ runs forever.  Consider all of the pairs $(p,y)$ that it encounters at each step during execution.  Since there are only finitely many states and symbols, by the pigeonhole principle, there must be some pair $(p,y)$ that is encountered infinitely often during execution; consider all the time points where we encounter $(p,y)$.  Since the size of the stack cannot decrease forever, there must be some adjacent pair of such time points where the stack is larger at the second than at the first.  Now consider the execution between between those two times, and find the time in that range when the stack is smallest.  Let $p'$ be the state of the DPDA and $y'$ the value on the top of its stack.  Then starting the DPDA at state $p'$  and just $y'$ on the stack and running forward will eventually return to state $p'$ with $y'$ on the top of the stack.  Why?  Well, we start $(p',y')$, then reach a point with state $p$ and $y$ on the top of the stack, then continues on to a point with state $p'$ and $y'$ on the top of the stack, and we never pop off the initial $y'$.  Basically, we've decomposed the trajectory $(p,y) \leadsto (p',y') \leadsto (p,y)$ into its second part $(p',y') \leadsto (p,y)$ followed by its first part $(p,y) \leadsto (p',y')$, but with things chosen so that we can start with just the symbol $y'$ on the stack and nothing more, and it will never get popped off.  It follows that $(N,p',y')$ is accepted by $L_1$, i.e., if $N$ runs forever, it will visit a pair that is accepted by $L_1$.)
Finally, we get to the problem in the main question: define $L_3$ as the language of $(M, x)$ where $x$ is some input string such that the DPDA $M$ halts on input $x$.
claim: $L_3$ is decidable.
proof: run $M$ on input $x$, and after every input symbol read, run the decider for $L_2$ on the current state and stack top: either $M$ itself will halt or the $L_2$ decider will return an acceptance. (Why?  Suppose $M$ never halts normally. Then consider the configuration $(q,s)$ where $s$ is the shortest stack among all configurations, resolving ties arbitrarily. Since $s$ is among the shortest stacks, it will never pop below the element on top of $s$.  Consequently, $(q,y)$ is accepted by the decider for $L_2$, where $y$ is the top of $s$.)
Note 2: it's probably not necessary to run $L_2$ decider to prove decidability of $L_3$: we can just run the $L_1$ decider instead.


Is Terra the only system programming language able to compile code at runtime?

No. So far the only ones I've found are pretty obscure/old, both variations of C:

`C
E-Code


Why is Graph Isomorphism downward self reducible?

This answer shows how to prove an easier variation, the case of (undirected loopless) multigraph isomorphism.
The problem of multigraph isomorphism is downward self-reducible
The simple idea is to merge two vertices in a way that distinguish those two vertices and edges involving them.

Let $G$ be a multigraph. If the sum of degrees of two vertices reaches the maximum, we will call an ordered pair of those two vertices a degree-maximum pair. For a degree-maximum pair $(u,v)$, construct $G_{u,v}$ as follows.

Its vertices are  all vertices of $G$ except $u$ and $v$, together with a new vertex $u_v$ which is understood as $u$ merged by $v$. Note that $G_{u,v}$ has one less vertice than $G$.

Its edges consists of two parts.

the edges of $G$ whose endpoints are neither $u$ nor $v$ with the same multiplicity. Let $m$ be the maximum multiplicity of these edges.
for all vertex $w$ of $G$ that is neither $u$ nor $v$, edge $\{w, u_v\}$ with multiplicity that is the sum of the multiplicity of $\{w,u\}$ in $G$ and the product of $m+1$ and the multiplicity of $\{w,v\}$ in $G$.

It is easy to see that if we are given a multigraph $G'$ that is isomorphic to $G_{u,v}$ for some multigraph $G$, we can reconstruct $G$ from $G'$ up to isomorphism.

Suppose we are given two graphs of $n$ vertices, $G$ and $H$. Use the oracle to compare $G_{u,v}$ with $H_{x,y}$ for all tuples $(u,v,x,y)$, where $(u,v)$ is a degree-maximum pair in $G$ and $(x,y)$ is a degree-maximum pair in $H$. Once the oracle return yes, we conclude $G$ and $H$ are isomorphic; otherwise the oracle always return no, in which case we conclude $G$ and $H$ are not isomorphic. It take polynomial time to construct $G_{u,v}$ from $G$ or $H_{x,y}$ from $H$. There are less than $n^2$ tuples. So the whole algorithm takes polynomial time. QED.

I am yet to find a proof that shows the problem of (non-multi)graph isomorphism is downward self-reducible.


Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$.
You can estimate the sum as follows:
$$
\sum_{i=0}^n \sqrt{i} \log_2^2 i \geq
\sum_{i=n/2}^n \sqrt{i} \log_2^2 i \geq
\sum_{i=n/2}^n \sqrt{n/2} \log_2^2 (n/2) \geq
\frac{n}{2} \cdot \sqrt{n/2} \log_2^2 (n/2).
$$
The latter expression is $\Omega(n^{3/2} \log^2 n)$, which is better than what you claim.
You can also estimate the sum by an integral. According to Wolfram alpha,
$$
\int \sqrt{x} \log^2 x \, dx = \frac{2}{27} x^{3/2} (9\log^2 x - 12 \log x + 8) + C.
$$
Since $\sqrt{i} \log_2^2 i$ is increasing, we have
$$
\int_0^n \sqrt{x} \log^2 x \, dx \leq \sum_{i=1}^n \sqrt{i} \log^2 i \leq \int_1^{n+1} \sqrt{x} \log^2 x \, dx,
$$
from which we see that your sum is $\Theta(n^{3/2} \log^2 n)$.


How can I quickly guess if L is context-free or det. context-free?

This answer was first written before the OP edited the question to specify
that he wanted "a quick test I can apply by inspection, without use of
a computer, that will often be correct."

Of course, I do not think anyone has such a test. To begin with, we
should first define a meta-language defining sets of strings to which
such a test could be applied. How general should this language be, as
we can even define metalanguages that can describe only context-free sets.
But that is no help, since the difficulty remains in the translation
between metalanguages.  In other words, this is simply an ill defined
question as asked.

And even if we were to agree on the language, as something that looks
more or less like the examples, we just do not have such
tests. Actually the question was raised before, as a suggestion for
research, but I do not recall there was any follow-up.

This discussion is mostly intended for the determination of
CF-ness. Raphael rightly commented that if the language is known to be
CF, even assuming that a CF grammar is known for it, it remains
undecidable to determine whether it is deterministic CF. However, the
OP is not asking for a decision procedure, but only a test which works
most of the time. So assuming there is a proper definition of what
most of the time means, such a test could still exist, though I do not
know of any. To take an example in a somewhat different family of
problems, there are primality tests that are fast and known to work
most of the time, with a probability of error that can be chosen
arbitrarily low (with increased cost).

Before I knew the OP wanted "a quick test", I thought he was only
asking for the heuristics we use to get a feeling that some language
is more likely to be this or that. I tried to give some hints on how I
do it. There is nothing more to my answer. It is based on a few
patterns that we see often enough, though the devil in the details may
sometimes change the answer.

Here is what I first answered

Since your question is whether we can see things at a glance, the
answer is that for many exercises, we can ... though we may
occasionally make mistakes.

Very often the stack is used simply as a counter, which is only a
small part of the CF power.

This is typically the case of the following example: $\{a^l b^m \mid l, m
\in \mathbb{N}, l=4m\}$, you have to check that 2 subparts of the
string have the same length $m$, up to a multiplicative rational
constant (4 in this case). That is easily done with a pushdown stack,
by pushing $m$ times in the stack the first time, and then popping $m$
times, checking that there is enough and not too much to pop. When you
push, or pop, you can do it for several symbols to account for the
constant.

However, this allows you to synchronize the sizes of two parts of the
input string, but not more. Once the information is popped, it is lost
and there is no way you can check a third part for the same size.
This is the case of your first example, where you would have to check
for $2n$ and twice for $n$, which makes three times, one too many.

The second example can be discounted as non CF for another reason. The
pumping lemma, without going into details, does tell you that an
infinite CF language has strings that can increase in size by constant
increments. That is, there is some number $n$ such that you can find an
infinite sequence of strings that increase in length by exactly $n$.

For a language of the form $\{a^l b^m \mid l, m \in \mathbb{N},
l=4^m\}$, when you increase $m$ by 1, the number of $a$ increases by
$4^{m+1}-4^m=3\times 4^m$.  That is incompatible with the presence of a linearly
increasing sequence. Exponentials usually do that.

This is an example of using the pumping lemma without even bothering
to try pumping anything. Geological considerations tell you the well will be dry.

Hence I conclude that none of your examples is CF,

But that is not always a full proof (though the pumping lemma use could be considered one). Mostly first evaluation at a glance, heuristics. One might combine exponentials so that things work.

As for deterministic, it is another kind of game. Basically, you try
to see whether you have to guess sometning in order to do your
counting right, so that it succeeds.

In the first example I gave, you obviously do not need any guess. It is
deterministic CF.

But if you consider the language
 $\{a^n b^{2n}c \mid n\in \mathbb{N}\} \cup\{a^n b^{4n}d \mid n\in
 \mathbb{N}\}$
it is non deterministic because you have to guess the last symbol of
the string before you decide to count with the constant 2 or with the
constant 4.

Thanks to  Hendrik Jan for pointing out my misreading of one example.


how to prove correctness of this BFS algorithm?

Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle.

Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible distance to $s$. Any two vertices in $S$ can not belong to the same cycle, since then they will form a cycle with a vertex with a smaller depth in the BFS-tree, which contradicts the assumption that they are closest possible to $s$. All these vertices belong to the same level of the BFS-tree since they have the same distance to $s$. The BFS-tree branches at each of them to at least two branches. Sice they all belong to cycles in the graph, there must exist an edge between two branches from the subtree rooted at one of them. This edge has its endpoints between two nodes on the same level in the tree, since else, one of them could have been visited by the other and get a smaller depth. When visiting this edge, our algorithm detects a cycle. The Cycle is hence this edge along with both paths in the BFS-tree from a vertex $v \in S$, to the endpoints of this edge. We output exactly these edges, where we start by printing this edge and backtrack on both branches until we reach back the vertex $v$ .


Here is an application of FIFOs in multiprocessor computers. A multiprocessor computer can be regarded as a distributed system.

To make a multiprocessor computer that correctly executes multiprocess programs, two requirements are given by Leslie Lamport [1]. The second one reads,

  Requirement R2: Memory requests from all processors issued to an individual memory module are serviced from a single FIFO queue. Issuing a memory request consists of entering the request on this queue.

For what it concerns applications of non-FIFO queues, I am confused about your requirement: Why do you use a queue if you don't need its features?

Anyway, is the priority queue an application in which we need to investigate elements of the queue which are not at its extreme sides?

[1] How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. By Leslie Lamport. IEEE Transactions on Computers, 1979.


Write a regular expression - Contains an equal number of 01 and 10 subtrings

Part of your confusion stems from the fact that there are two different formulations of Arden's Lemma, which I'll call LR and RL. To illustrate them, let's take a simple FA with three states, $P,Q,R$, where $P$ is the start state and $R$ is the only final state. The transitions are
$$\begin{array}{c|cc}
 & 0 & 1\\ \hline
P & Q & \varnothing\\
Q & R & Q\\
R & R & R
\end{array}$$
It's clear with a moment's thought that the language accepted by this FA is denoted by the regular expression $01^*0(0+1)^*$, so let's see what the two versions of Arden's Lemma produce.

LR: In this version we generate the regular expression from left to right. If we have a state $X$ with a transition on $a$ to state $Y$ we will include the equation $X=aY$, along with any other terms that arise from transitions from $X$ to other states. Along with this, we add a "$+\epsilon$" to the expression for $X$ if $X$ happens to be a final state. Having made the collection of equations, we may apply the simplification rule that says that whenever we have $X=rX + s$ for regular expressions $r, s$ we can replace the equation by its solution $X=r^*s$. Note that here the goal is to product a regular expression for the start state.

In the example above, we'll have the equations
$$\begin{align}
P&=0Q\\
Q&=0R+1Q\\
R&=(0+1)R+\epsilon & \text{since R is final}
\end{align}$$
Substituting, we see that $R=(0+1)^*\epsilon = (0+1)*$ and $Q=1^*(0R)=1^*0(0+1)^*$, and finally $P=0Q=01^*0(0+1)^*$, as we expected.

RL: In this version we construct the regular expression from right to left. The difference is that if we have a state $X$ with transition on $a$ to state $Y$ we include the equation $Y=Xa$, along with any similar terms. In this case, we add the "$+\epsilon$" only to the start state's equation and the substitution in this case says that if we have $X=Xr+s$ we have the solution $X=sr^*$.

Returning to our example, we'll have
$$\begin{align}
P&=\epsilon & \text{since $P$ is the start state and has no incoming transitions}\\
Q&=P0+Q1\\
R&=Q0+R(0+1)
\end{align}$$
Now our goal is just opposite of what we had in the LR version: we want an expression for the final state, $R$. Working from the top down we have $Q=Q1+P0=Q1+0$ so $Q=01^*$ and $R=Q0(0+1)^*=01^*0(0+1)^*$: the same result generated in a different order.

Assuming you want to use the LR version, your equations should be
$$\begin{align}
a_1&=0a_2\\
a_2&=0a_3+1a_5+\epsilon\\
a_3&=0a_3+1a_4+\epsilon\\
a_4&=0a_3+1a_4\\
a_5&=0a_6+1a_5\\
a_6&=0a_6+1a_5+\epsilon
\end{align}$$
As for your problem with $a_5, a_6$, for example, we could do this:
$$\begin{align}
a_5 &= 1^*(0a_6)=1^*0a_6 & \text{Arden}\\
a_6 &= 0^*(1a_5+\epsilon) &\text{Arden again, now substitute $a_6$}\\
a_5 &= 1^*0[0^*(1a_5+\epsilon)]\\
    &= (1^*00^*1)a_5+1^*00^* &\text{so we have}\\
a_5 &= (1^*00^*1)^*1^*00^*
\end{align}$$


Turing Machine where branches are resolved via arbitrary operator

Using any/all (a.k.a. or/and) gives rise to alternating Turing machines. Goldschlager and Parberry (On the construction of parallel computers from various bases of boolean functions, Theoretical Computer Science 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines extended Turing machines.

To me, it would make sense to use the same term for what you're proposing. I suggest following the references in Goldschlager and Parberry and looking up who's cited them, to see if the term "extended Turing machine" stuck and if it's been applied to your scenario.


Keep k+ties largest elements in a stream

Keep a binary heap, where each element in the heap is a unique key value together with a pointer to a list of all the items with that key value.

For instance, with the input list $[10,5,7,5,7,9,10]$, the unique key values are $5,7,9,10$, so you'd have a heap containing the following 4 elements: $5$ (with a pointer to the list $[5]$), $7$ (with a pointer to the list $[7,7]$), $9$ (with a pointer to the list $[9]$), and $10$ (with a pointer to the list $[10,10]$).  Now you can find the top-$k$ elements (with ties) straightforwardly using this heap data structure.


Approaches to the size constrained weighted set cover problem

The problem is in P and can be solved in $O(m^k)$ time, where $m$ is the number of sets to select from.  For this reason, it is fundamentally different from standard set cover (which is NP-hard) and might not have been studied as much in the complexity theory literature.


Can someone help me understand the time and space complexity?

Assuming that sorted() really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches.
You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is not creating a list that contains pairs of elements from a and b but just returning an iterator to these pairs. Going through the list implicitly returned by this iterator takes $O(n)$ time, even just to construct it (e.g., list(zip(a,b))). In your particular case this doesn't really matter since the time complexity will be $\Omega(n)$ anyway.
You say that sorted() takes $O(n)$ time. This is not impossible, but it's at least suspicious (have you checked in the python documentation/implementation?). There is no algorithm that can sort a list of $n$ elements in time $O(n)$ by only performing comparisons. The implementation of sorted() would need to be particularly clever and recognize that you are sorting small integers.
Probably sorted() just takes $O(n \log n)$ time and $O(n)$ space, which would result in the same overall time and space complexities for your algorithm.


Decidable properties of computable reals

Yes, Rice's theorem for reals holds in every reasonable version of computable reals.

I will first prove a certain theorem and a corollary, and explain what it has to do with computability later.

Theorem: Suppose $p : \mathbb{R} \to \{0,1\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence $(x_i)_i$ such that $p(\lim_i x_i) \neq p(x_j)$ for all $j \in \mathbb{N}$.

Proof. We construct a sequence of pairs of reals $(y_i, z_i)_i$ as follows:
\begin{align*}
(y_0, z_0) &= (a, b) \\
(y_{i+1}, z_{i+1}) &=
\begin{cases}
(y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\
((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\
\end{cases}
\end{align*}
Observe that for all $i \in \mathbb{N}$:

$p(y_i) = 0$ and $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Thus the sequences $(y_i)_i$ and $(z_i)_i$ are Cauchy and they converge to a common point $c = \lim_i y_i = \lim_i z_i$. If $p(c) = 0$ then we take $(x_i)_i = (z_i)_i$, and if $p(c) = 1$ then we take $(x_i)_i = (y_i)_i$. $\square$

Corollary: Suppose $p : \mathbb{R} \to \{0,1\}$ and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then every Turing machine either runs forever or it does not run forever.

Proof.
By the theorem, there is a Cauchy sequence $(x_i)_i$ such that $p(x_j) \neq p(\lim_i x_i)$ for all $j \in \mathbb{B}$. Without loss of generality we may assume that $p(x_j) = 1$ and $p(\lim_i x_i) = 0$.

Let $T$ be a Turing machine. Define a sequence $y_i$ by
$$y_i =
\begin{cases}
x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\
x_i & \text{if $T$ does not halt within $i$ steps}
\end{cases}
$$
The sequence is well-defined because we may simulate $T$ up to $i$ steps and decide whether it has stopped or not within that many steps. Next, observe that $(y_i)_i$ is a Cauchy sequence because $(x_i)_i$ is a Cauchy sequence (we leave this as an exercise). Let $z = \lim_i y_i$. Either $p(z) = 0$ or $p(z) = 1$:

if $p(z) = 0$ then $T$ runs forever. Indeed, if it stopped after $j$ steps, then we would have $z = x_j$, and so $p(z) = p(x_j) = 1$ would contradict $p(z) = 0$.
if $p(z) = 1$ then $T$ does not run forever. Indeed, if it did, then we would have $z = \lim_i x_i$, and so $p(z) = p(\lim_i x_i) = 0$, contradicting $p(z) = 0$.
$\square$

Now we can explain why this gives us Rice's theorem for real numbers. The proofs are constructive, therefore they yield computable procedures. This is true of any model of computability and any compute structure of reals that deserve to be so called. In fact, you can go back and read the proof as instructions for building a program -- all the steps are computable.

Thus, if we had a computable map $p : \mathbb{R} \to \{0,1\}$ and computable $a, b \in \mathbb{R}$ such that $p(a) = 0$ and $p(1) = 1$, then we could apply the computable procedures arising from the constructive proofs of the theorem and the corollary to create the Halting oracle. But the Halting oracle does not exist, therefore, every computable map $p : \mathbb{R} \to \{0,1\}$ is constant.

Supplemental: There was also a question about whether Rice's theorem is related to connectedness of the reals. Yes, it is essentially the statement that the reals are connected.

Let us first observe that a continuous map $p : X \to \{0,1\}$ (we take the discrete topology on $\{0,1\}$) corresponds to a pair of disjoint clopen (closed and open) sets $U, V \subseteq X$ such that $U \cup V = X$. Indeed, take $U = p^{-1}(\{0\})$ and $V = p^{-1}(\{1\})$. Because $p$ is continuous and $\{0\}$ and $\{1\}$ are open, $U$ and $V$ will be open, disjoint, and they obviously cover all of $X$. Conversely, any pair $(U,V)$ of disjoint clopens that cover $X$ determines a continuous map $p : X \to \{0,1\}$ that maps elements of $U$ to $0$ and elements of $V$ to $1$.

From this we learn that a space $X$ is disconnected if, and only if, there exists a continuous map $p : X \to \{0,1\}$ and $a, b \in X$ such that $p(a) = 0$ and $p(1) = b$ (we need $a$ and $b$ so that we get a non-trivial decomposition of $X$). There is another way to say the same thing: a space $X$ is connected if, and only if, all continuous maps $X \to \{0,1\}$ are constant.

In computable mathematics we have a basic theorem: every computable map is continuous. So, as long as we are within the realm of computable objects, Rice's theorem does in fact state that a certain space is connected. In the case of the classic Rice's theorem the space in question is the space of partial computable functions $\mathbb{N} \to \mathbb{N}$.


How do you determine the inputs to a neural network?

How do you determine what inputs you should use for a neural network?

Experimentation.  Initially you use a priori knowledge and intuition to guess the features will be useful for classification or prediction or whatever it is your network is doing.  Then you test the network and observe its error rate.  Based on the results you make adjustments; add/discard features, regularize, add/discard layers, adjust the learning rate, and so on.

  Are more inputs necessarily better?

No.  You're trying to find the features that matter to what you're trying classify/predict and discard unrelated features.  Processing input/features that don't matter to the computation just wastes CPU time.

  Does it matter if inputs are linearly independent?

If inputs are linearly dependent then you are in effect introducing the same variable as multiple inputs.  By doing so you've introduced a new problem for the network, finding the dependency so that the duplicated inputs are treated as a single input and a single new dimension in the data.  For some dependencies, finding appropriate weights for the duplicate inputs is not possible.

  Could one build a neural network that could determine its own inputs for an arbitrary problem and raw data set?

This is essentially what neural networks that deal with raw data only must do.  The hidden layers tease features out of the raw data and those features are gradually refined by the feedback that occurs during training.  This is an approach you might use if you have no idea how to proceed given some classification problem.  But usually you have some idea what features are both useful and difficult for the network to compute for itself, and you provide those features as additional input.


PDA accepting all words not of the form $b^na^n$

The PDA has two main states:

No $a$ has been encountered.
Some $a$ has been encountered.

While in the first state, it pushes $B$ onto the stack for any $b$ it encounters. It moves to the second state when encountering an $a$, at which point it removes $B$ from the stack for any $a$ it encounters (including the first $a$). If it ever realizes that it has seen more $a$s than $b$s, or if it encounters $b$ again, it can immediately accept (depending on your model, you might have to read the remainder of the input). After finishing reading the entire input, if the stack contains at least one $B$ then it accepts, and otherwise it rejects. You can implement this by requiring the PDA to pop at least one $B$ before accepting.
Formally describing this PDA depends on the exact definition of PDAs in your class, and in any case, it is an exercise which is best for you to do on your own.


General approach to randomized algorithm for equality problem

Suppose that the inputs are $x,y \in \{0,1\}^n$.

Consider the following protocol:

The parties decide on a random string $z \in \{1,2\}^n$.
Alice sends Bob $\alpha = \sum_{i=1}^n x_i z_i \pmod{3}$, and Bob sends Alice $\beta = \sum_{i=1}^n y_i z_i \pmod{3}$.
The parties compute $\gamma = \alpha - \beta \pmod{3}$.

Suppose that the Hamming distance between $x$ and $y$ is $d$. Then $\gamma$ is the sum of $d$ random values in $\{1,2\}$. Using linear algebra, we can calculate
$$ \Pr[\gamma = 0] = \frac{1}{3} + \frac{2}{3} \left(-\frac{1}{2}\right)^d.$$
(You can also prove this formula by induction.)

In particular, when $d=0$ the probability is $1$, when $d=1$ the probability is $0$, and otherwise the probability is in the range $[1/4,1/2]$ (corresponding to $n=3$ and $n=2$, respectively).

The suggests a protocol of the following form:

The parties decide on $N$ random strings $z_1,\ldots,z_N \in \{1,2\}^n$.
Alice sends Bob $\alpha_j = \sum_{i=1}^n x_i z_{j,i} \pmod{3}$ and Bob sends Alice $\beta_j = \sum_{i=1}^n y_i z_{j,i} \pmod{3}$, for $1 \leq j \leq N$.
The parties compute $\gamma_j = \alpha_j - \beta_j \pmod{3}$ for $1 \leq j \leq N$.
If all $\gamma_j$ are zero or all are non-zero, output "Hamming distance is probably at most 1", otherwise output "Hamming distance is definitely more than 1".

As in the case of equality, this protocol has only one-sided error: whenever the algorithm outputs "Hamming distance is more than 1", it is always correct. It remains to determine the connection between $N$ and the error probability $\epsilon$. Let $p = \Pr[\gamma = 0]$. If $p \neq 0,1$, the probability that the algorithm outputs the incorrect answer is
$$
p^N + (1-p)^N \leq (1/2)^N + (3/4)^N.
$$
This shows that $\epsilon$ is exponentially small in $N$, and so in order to guarantee an error probability of $\epsilon > 0$, it suffices to take $N = O(\log(1/\epsilon))$.


How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

First of all, we have to distinguish between two different questions. The first is about analyzing the specific (generalized) merging algorithm used in merge sort. The second is about analyzing the problem.

Merge sort merging

The paragraph you quote attempts to analyze the merge sort merging algorithm. It only gives a lower bound on the number of comparisons, though presumably it is easy to show that it is also an upper bound. In order to give a lower bound of $C$ on the number of comparisons, it is enough to describe a situation in which the algorithm uses $C$ comparisons. Such a situation is the "worst case [instance]" that the paragraph is talking about.

The merging algorithm starts with three lists of length $n/3$, and constructs a "big list" of length $3$. The algorithm works by comparing the smallest elements in all remaining lists, and moving the smallest one to the top of the big list. As the algorithm progresses, eventually lists will empty — all their elements have been moved to the big list.

The paragraph suggests to consider the situation in which the first list empties when the other two have exactly one element remaining, which it claims is a "bad case", indeed the "worst case"; for the sake of the lower bound, we don't care whether this is actually true. You have to argue that the situation can actually happen, and carefully count all comparisons done by the merging algorithm. The merging algorithm the paragraph considers always compares the bottom elements of all remaining lists, requiring $\ell-1$ comparisons if $\ell$ non-empty lists remain. In this case, as long as all lists are non-empty, we need two comparisons per element.

At the situation considered there are only two elements left, so $n-2$ elements have been processed with two comparisons per element, leading to $2(n-2)$ comparisons. The final two elements require one more comparison. It is not too hard to check that this is indeed the worst case: this situation maximized the number of times that an element requires two comparisons to process.

The more general case with $c$ lists is very similar. Again the worst case is when the first list empties when all other lists have exactly one element. Up to now there have been $(c-1)(n-c+1)$ comparisons. The next element will require $c-2$ comparisons only (since there are only $c-1$ non-empty lists), the element after that $c-3$, and so on. This gives the formula you state.

General question

A different question one can ask is: given $c$ sorted lists of length $n/c$, how many comparisons are needed to determine the sorted order of all of them merged. There are two variants of this question:

What is the minimal $C$ such that there is an algorithm which outputs the correct order and never uses more than $C$ comparisons; the algorithm is only allowed to access the lists by comparing two elements. This is the so-called decision-tree model.
What is the minimal running time of an algorithm merging the lists.

These questions are rather different. The first question is much easier to answer, and I will only comment on it. However, the minimal $C$ doesn't necessarily correspond to an efficient algorithm, since determining which comparison to do next could be difficult.

The classical lower bound on sorting extends to this situation. Given $c$ sorted lists of length $n/c$, the number of possible ways they fit together to one big list is $\frac{n!}{(n/c)!^c} = \Theta\big(\frac{c^n}{n^{(c-1)/2}}\big)$, and we obtain a lower bound of $(\log_2 c)n - O_c(\log n)$. Fredman's classical result shows that there is a corresponding algorithm in the decision-tree model using at most $(2+\log_2 c)n$ comparisons (for large enough $n$, depending on $c$), which is better than the merge sort merging procedure for $c \geq 5$. The correct answer is probably $(\log_2 c)n \pm o_c(n)$. Indeed, using heaps you can merge $c$ lists with $O((\log c)n)$ comparisons efficiently, as described for example in answers to the following question.


what does the redundancy of a code means?

A linear error-correcting code encodes $m$ message bits using $w$ encoded bits. The redundancy is $r = w-m$. In other words, it is a collection of $M = 2^m$ codewords out of the possible $W = 2^w$ words of length $w$. We can extract the redundancy using the formula
$$ r = \log_2 \frac{W}{M}. $$
This formula makes sense for arbitrary error-correcting codes.

In your case, codewords are of length $n$, and there are at least $2^n/(6n-3)$ of them. Therefore the redundancy is at most
$$ \log_2 \frac{2^n}{2^n/(6n-3)} = \log_2 (6n-3). $$


Calculating cache memory based on LRU algorithm

Least recently used cache do the following things:
we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent.

If the cache is not full,
1 a). add to the cache if the entry is not in the cache.
1 b). If the entry is in cache we make that most recent and continue.
If the cache is full,
2 a) If the value is already in the cache we just move it up(front) so that it represent most recent after this.
2 b) If the value is not in the cache we remove the least recent one and add the current value to the top(front)to represent that as the most recent.

Now let me explain you the sample which you have provided.

**Input**                     **cache**(front represent most recent and end represent least recent

1   2   3   4   5   2   5   4   1   5   2   3  --> inputs

1   2   3   4   5   2   5   4   1   5   2   3  --->(this is our cache) **top represent most recent**
-   1   2   3   4   5   2   5   4   1   5   2
-   -   1   2   3   4   4   2   5   4   1   5
-   -   -   1   2   3   3   3   2   2   4   1  ----> **end represent the least recent**

So we have our answer as,(from most recent to least recent) = 3,2,5,1

hope this helps you.Sorry for my bad editing.


Communication Complexity for Product Distributions

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $(X,Y)$ for inner product? We want each of $X,Y$ separately to be quite random, and we want $X\cdot Y$ to be mostly zero, say $X \cdot Y$ contains at most a single $1$. This cannot be accomplished by a product distribution. While you can get the $X \cdot Y$ property, this implies that each of the two inputs will be very biased. Conversely, if the inputs $X,Y$ are quite random, then $X \cdot Y$ will have many $1$s.

The inner product function doesn't suffer from the same issue. Indeed, it seems that the hardest distribution is the uniform distribution. You can prove a linear lower bound using the discrepancy method – this is standard, and uses a bound on the discrepancy known as Lindsey's lemma.

Sherstov came up with an optimal gap example in his paper Communication complexity under product and nonproduct distributions. His function is a random function, chosen so that there are no large monochromatic $1$-rectangles. The end result is a function whose randomized communication complexity is $\Omega(n)$, but for any product distribution, the randomized communication complexity is $O(1)$.


Can I use machine learning to predict someone will buy something in a specific time?

Short answer:
Yes it can be done using machine learning if you have  features with sufficient information.
Long answer:
You can model this either as a multilabel problem (i.e Beer, chicken, pizza are multiple labels [non mutually exclusive] for the same data point) or as a multiclass problem (by creating a combination like "Beer, chicken, pizza". In the multiclass case the labels would be mutually exclusive). You can use day of the week, name of person and some other attributes as features (aka predictors) for the model.
For a more detailed answer you'd need to tell us what you have already tried out so that the community can help you.
Also, see this   related question.


Complexity of finding factors of a number

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.


Lower bound on running time for solving 3-SAT if P = NP

These are some of the best time and space bounds known. In this area the research has gone to the direction of giving bounds in both time and space. My understanding is that superlinear time bounds without a space constraint are not known.

Time-Space Lower Bounds for Satisﬁability Lance Fortnow, Richard Lipton, Dieter van Melkebeek

  We establish the ﬁrst polynomial time-space lower bounds for satisﬁability on general models of computation. We show that for any constant $c$ less than the golden ratio there exists a positive constant $d$ such that no deterministic random-access Turing machine can solve satisﬁability in time $n^c$ and space $n^d$, where $d$ approaches 1 when $c$ does.


What does the intersection symbol (∩) mean when applied to two non-set elements?

Eh.  $\cap$ doesn't mean anything on non-set variables.  Looking at the paper, that part of the paper doesn't make any sense to me either.  The paper says $x_1,x_2$ are Boolean variables, but the notation $x_1 \cap x_2$ is not well-defined on two Boolean variables; you can't take the set-intersection of two Boolean variables.  If $x_1,x_2$ were sets somehow (which the paper says they aren't), then the meaning of $x_1 \cap x_2 \in \{x_1,x_2,v\}$ is that either $x_1 \subseteq x_2$ or $x_2 \subseteq x_1$ or $x_1 \cap x_2 = v$.

So it's anyone's guess what that formula was supposed to represent.  If you absolutely must understand the paper, you'll probably have to read the surrounding context to guess what the intention was.  Better yet, find a better paper to read, if you can.  In any case, the reason you are confused is because what's written is confusing and seems like mathematical gibberish to me.  It happens; no one is perfect.  Don't assume that just because a paper is published in a journal, that what's written there will necessarily be correct or useful or meaningful.


What is an asymptotically tight upper bound?

Saying that a big-O bound is "asymptotically tight" basically means that the author should have written $\Theta(-)$.  For example, $O(x^2)$ means that it's no more than some constant times $x^2$ for all large enough $x$; "asymptotically tight" means it really is some constant times $x^2$ for large enough $x$ and not, say, some constant times $x^{1.999}$.


What is complement of Context-free languages?

One can understand your question in two ways, according to the definition of "the complement of CFL".

case A: Complement of CFL is the class of all the languages that are not in CFL.  Formally, $$\overline{CFL} = \{ L \mid L\notin CFL\}.$$
In that case, $\overline{CFL}$ is way bigger than $P$, it even has languages that are not in $R$, etc.
But maybe that's not what you meant.

case B: Define the complement-CFL class as $$co{CFL} = \{ \bar{L} \mid L \in CFL\},$$
in words, the set of all languages $L$, such that $L$'s complement is context free.

In that case, what you wrote makes sense:
$CFL \subsetneq P$  (by the CYK algorithm), and also $co{CFL} \subseteq P$ (run the same algorithm, output the opposite answer), and since $CFL \neq co{CFL}$,
then it should be immediate that $co{CFL}\subsetneq P$, right?


Problem with storing an existing triangulation in a DCEL

The point of a half-edge data structure is that each half-edge is incident to exactly one face, and each face is represented by a list of half-edges given in order around the face. This is different from a normal planar map in which edges are incident to two faces. This can make certain coding tasks easier to deal with. So an (undirected) edge $\{u, v\}$ gets split into two half-edges $uv$ and $vu$ which are directed and twins of each other.

To list all half-edges (in order) incident to a face just requires following next pointers from each edge. Something like:

HalfEdge startEdge = ...some half-edge...
HalfEdge walk = startEdge;
do {
  //... do something here ...
  walk = walk.next;
} while (walk != startEdge);

In a DCEL the code above will walk around all edges in ccw order incident to the face startEdge.

Here is a concrete example:

Suppose we want to represent a triangulation with a single triangle $ABC$ where $A$, $B$, and $C$ are given in ccw order. We create six half edges: $AB$, $BC$, $CA$, $BA$, $CB$, and $AC$.

set the twins: $AB.twin$ = $BA$, $BA.twin = AB$. $AC.twin = CA$, $CA.twin = AC$, $BC.twin = CB$ $CB.twin = BC$.

set the next pointers: $AB.next = BC$, $BC.next = CA$, $CA.next = AB$ $AC.next = CB$ $CB.next = BA$, $BA.next = AC$.

and prev pointers $AB.prev = CA$, $BC.prev = AB$, $CA.prev = BC$, $BA.prev = CB$ $AC.prev = BA$ $CB.prev = AC$.

Now we already have implicitly faces: if we start with $AB$ and chase the next pointers around until we get back to $AB$, we get $AB$, $BC$, $CA$ which represents the interior of the triangle. If we start with $BA$ we get a different list: $BA$, $AC$, $CB$. This list represents the so-called "unbounded" face which is the exterior of our triangle. These are the "cycles" you mentioned. The first cycle is the (cyclic) list $AB\leftrightarrow BC\leftrightarrow CA$ and the second is $BA \leftrightarrow AC\leftrightarrow CB$.

For some applications this is all you need, but for others you may want a structure for storing extra information about the face. Keep in mind that the face is already represented by the double linked list $AB\leftrightarrow BC\leftrightarrow CA$. However we can make two data structures $f_0$ and $f_1$ for storing extra information for the unbounded face $f_0$ and the interior of the triangle $f_1$. We then set pointers again:

$AB.face = f_1$, $BC.face = f_1$, $CA.face = f_1$,
$BA.face = f_0$, $CB.face = f_0$, $AC.face = f_0$.

So now each half-edge points to the face incident to it. But we may also want to start with a face structure and then get a list of its incident half-edges. We already have the half-edges stored as lists, so we just need to point to any arbitrary start of the list, something like:

$f_0.halfEdgeList = BA$

$f_1.halfEdgeList = AB$

So now given a face $f$, we can loop over all its incident half-edges as before:

HalfEdge startEdge = f.halfEdgeList;
HalfEdge walk = startEdge;
do { // ... same as above
  walk = walk.next;
} while (walk != startEdge);

Finally, assuming you already have correctly set the previous, next, and twin pointers for your half-edges, then you could do something like this: when you create a half-edge, initialize its face pointer to 0. Then add all half-edges to a queue.

Note I'm writing pseudo-code, not C++ code here:

while (!queue.Empty()) {
  HalfEdge startWalk = queue.dequeue();
  if (startWalk.face = 0) {
    //This half-edge doesn't have a face yet
    Face f = create_new_face(); //Some function to create a new face and add it to any appropriate lists

    //Now walk around all edges from startWalk setting the face:
    HalfEdge current = startWalk;
    do {
      current.face = f;
      current = current.next;
    } while (current != startWalk);
  }
}

UPDATE: I looked at the link you provided and want to give a bit of terminology. Above I used the terms source and target to refer to the the start and end vertices of the half-edge. In the C++ code you linked to source is called tail, and target is the tail of the twin. So if you have a half edge called halfEdge:

vertex *source = halfEdge->tail;
vertex *target = halfEdge->twin->tail;


A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.

This also assumes that the "do something"-bit doesn't change the label (and that the order of the "do something"s doesn't matter).


How to find the most unique vectors in a set?

I suspect your problem might be NP-hard (by reduction from Clique), so it might be hard to find an efficient algorithm for it.

One heuristic is to use the farthest-point first method, where at each stage you pick the point whose angle to the others already picked is as large as possible.  In other words, suppose we have already picked a set $S$ of vectors.  Now we find the vector $x$ that maximizes $\min \{\text{angle}(x,s) : s \in S\}$, add it to $S$, and repeat.  This most likely won't give the optimal set of vectors, but it might give something that is somewhat close to optimal.

Another possible approach is to use binary search and some kind of clique-finding algorithm.  Let $t$ be a threshold.  Form an undirected graph $G$ where each vector is a vertex in the graph; and you have an edge $(u,v)$ if the angle between the two vectors $u,v$ is at least $t$.  Then if you can find a clique of size $k$ (where $k$ is the desired size of your subset), then you've found a subset of vectors that are all at angle $\ge t$ from each other.  Now repeat this, using binary search on $t$ to find the largest $t$ for which you can find a $k$-clique.  In this way you might be able to take advantage of methods in the literature for finding $k$-cliques.  (For instance, one simple preprocessing step you can do to reduce the size of the graph is:  delete any vertex whose degree is less than $k$, and repeat until convergence.)


Updating a mst after increasing the weight of an edge in the mst

Let $S$ be a spanning tree of an  edge-weighted graph. We call $S$ a local-minimum spanning tree (local-MST) of the graph if every edge not in $S$ weighs the heaviest in the cycle created when that edge is added to $S$.

Here is a very useful characterization of MST.

A spanning tree is an MST if and only if it is a local-MST.

Proofs of the above theorem can be found here or here.

Once we are armed with above theorem, it is easy to prove the algorithm in the question does produce an MST.

Proof of the algorithm: $G$ and $G_2$ will be referred as $(G, w_1)$ and $(G, w_2)$ respectively, where $w_1$ is the the original weight function and and $w_2$ is the updated weight function. $w_1$ and $w_2$ are the same except on $e$.

Let $G_a$ be the subgraph spanned by $T_a$ and $G_b$ be the subgraph spanned by $T_b$. Every vertex of $G$ is either in $G_a$ or in $G_b$.

Consider an arbitrary edge $f$ of $G$. Let $\mathcal C$ be the cycle created when we add $f$ to $T_2$.

If $f$ is in $G_a$ or $G_b$, then $e$ is not part of $\mathcal C$. So $\mathcal C$ is also the cycle created when we add $f$ to $T$. Since $T$ is an MST of $(G, w_1)$, $f$ weighs the heaviest in that cycle with respect to $w_1$ and, hence, with respect to $w_2$ as well.
Otherwise, $f$ connects one vertex in $G_a$ and one vertex in $G_b$. $\mathcal C$, as a cycle, must include $e_2$ since $e_2$ is the only edge in $T_2$ that connect $G_a$ and $G_b$.

In the above illustration, all green edges together with $e$ is the cycle created when $e_2$ is added to $T$.  All blue edges together with $e$ is the cycle created when $f$ is added to $T$. All green and blue edges together is $\mathcal C$.

Since $T$ is a local-MST w.r.t $w_1$, $e_2$ weighs the heaviest on the green cycle w.r.t. $w_1$. Since $w_2$ and $w_1$ agrees except on $e$,
$$w_2(e_2)\ge w_2(\text{every green edge}).$$

Similarlyly we have
$$w_2(f)\ge w_2(\text{every blue edge}).$$

Since $w_2(f)\ge w_2(e_2)$ by the specification of the algorithm, $f$ weighs the heaviest among all green edges and all green edges. That is, $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

There are configurations other than the illustration. For example, $e_2$ or $f$ might be the same as $e$. The green cycle and the blue cycle might have multiple overlapping segments. In every case, similar argument  with the same inequalities shows that $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

So we have shown that $T_2$ is a local-MST of $(G, w_2)$. By the above theorem, $T_2$ is an MST of $(G, w_2)$.


Is it possible to compute -12 (decimal) in 4 bits binary

No, it's not possible, at least using the standard representations. An unsigned $n$-bit number can represent any integer in the interval $[0, 2^{n} - 1]$. A signed $n$-bit number using two's complement can represent integers in the interval $[-2^{n - 1}, 2^{n - 1} - 1]$. With $n = 4$, that gives an interval of $[-8, 7]$, which obviously doesn't include $12$. One's complement can use $n$ bits to represent the interval $[-(2^{n - 1} - 1), 2^{n - 1} - 1]$, giving the interval $[-7, 7]$ for four bits, which also doesn't work. You'd have to contrive a nonstandard representation to represent $-12$ in four bits.


How can the Operating System run on the same chip it is supposed to be managing?

In their most primitive form, operating systems rely on processes being well-behaved and handing control back to the operating system from time-to-time. If a process is not well-behaved, then indeed it can happen that the operating system freezes.

Most CPU's however, have interrupts: an interrupt pauses the current process (preemption) and hands control back to the operating system. You can schedule interrupts to happen at specific intervals, or be triggered externally (for instance pushing the reset button).

Basically, the CPU switches back and forth between running the OS and running processes at a blazingly fast speed. Furthermore, CPU's have "user mode" and "kernel mode". Processes run in user mode and the OS runs in kernel mode. Running in user mode prevents a process from executing restricted commands (such as IO). If a process wants to write to the disk, it has to ask the OS to do so. The OS switches to kernel mode and does the write on behalf of the process (after making sure the process has the required permissions).


Logspace algorithm for balanced parentheses problem

Initialize a counter at zero. Whenever you see "(", increase it by one, and whenever you see ")", decrease it by one. Accept if the counter was always nonnegative and ended up at zero. The counter only takes logarithmic space to store.


Deterministic linear time algorithm to check if one array is a sorted version of the other

You haven't specified your computation model, so I will assume the comparison model.

Consider the special case in which the array $B$ is taken from the list
$$
\{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}.
$$
In words, the $i$th element is either $2i-1$ or $2i$.

I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, that the algorithm has compared each element in $B$ to its counterpart in $A$. Indeed, suppose that the algorithm concludes that $A$ and $B$ contain the same elements, but never compares the first element of $B$ to its counterpart in $A$. If we switch the first element then the algorithm would proceed in exactly the same way, even though the answer is different. This shows that the algorithm must compare the first element (and any other element) to its counterpart in $A$.

This means that if $A$ and $B$ contain the same elements, then after verifying this the algorithm knows the sorted order of $A$. Hence it must have at least $n!$ different leaves, and so it takes time $\Omega(n\log n)$.


Your second step isn't sound.

Take any unsatisfiable $3$-SAT formula (without restriction on the number of variable appearances) and perform the standard reduction to a formula where each variable occurs at most three times.  That is, for each variable $X$ that occurs $k>3$ times, replaces the occurrences respectively with $X_1, \dots, X_k$ and add the new clauses

$$(\overline{X_1}\lor X_2) \land(\overline{X_2}\lor X_3) \land \dots \land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_1)$$

to ensure that $X_1, \dots, X_k$ have the same value in any satisfying assignment.

Now, we have the clause $\overline{X_1}\lor X_2$ but not $X_1\lor\overline{X_2}$ so we can use your second step, taking $A=\overline{X_1}$ and $B=X_2$. So we must delete the first clause and replace any instance of $X_1$ with $X_2$ and any instance of $\overline{X_2}$ with $\overline{X_1}$.  This replaces the clauses above with

$$(\overline{X_1}\lor X_3) \land (\overline{X_3}\lor X_4) \land \dots \land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_2)\,,$$
i.e.,
$$(X_1\rightarrow X_3)\land (X_3\rightarrow X_4) \land \dots \land (X_{k-1}\rightarrow X_k)\land (X_k\rightarrow X_2)\,.$$

This no longer requires all the the $X_i$ variables to have the same value. There are formulas that will become satisfiable when you make this transformation.

But, further, we can now apply the transformation again to the clause $\overline{X_1}\lor X_3$, resulting in
$$(\overline{X_1}\lor X_4) \land (\overline{X_4}\lor X_5)\land\dots\land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_2)\,.$$
Note that the variable $X_3$ has completely disappeared and can take any value. Iterating, we see that all the clauses relating $X_1, \dots, X_k$ disappear!

What have we done? We've taken a formula that mentioned $X$ more than three times and replaced these occurrences with successive new variables $X_1, \dots, X_k$, plus the constraint that all these new variables must take the same value.  We then deleted all the constraints, so $X_1, \dots, X_k$ can take any value at all, independently of each other and, by the way, each of the variables $X_1, \dots, X_k$ now only occurs once.  So, if we started with an unsatisfiable formula in which every variable occurred more than three times, we end up with a formula where every variable occurs exactly once.  That formula is always satisfiable.


What is the actual scope of the Halting Problem impossibility result?

Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and:

If $H$ terminates and outputs "yes" then $M(x)$ halts.
If $H$ terminates and outputs "no" then $M(x)$ does not halt.

In particular, $H$ is allowed to run forever and not give an answer.
Given two partial Halting oracles $H_1$ and $H_2$ we may combine their powers by running them in parallel, and if either one ever halts and gives an answer, we output that answer. Let us write $H_1 \oplus H_2$ for such a combined partial Halting oracle.
Consider the partial Halting oracle $L$ which works as follows on input $(M,x)$: it simulates the working of $M$ on input $x$, and if the simulation ever terminates, it terminates with output "yes". Then $L$ correctly predicts all cases that halt, and no others.
Given any partial Halting oracle $H$, we can always combine it with $L$ to get a partial Halting oracle $H \oplus L$ that correctly predicts all the halting cases. The only question then is, how good a predictor of non-halting can be implemented.
Define the non-halting set
$$\overline{K} = \{(M,x) \mid \text{$M(x)$ does not halt}\}$$
and for any partial Hlating oracle the set
$$S_H = \{(M,x) \mid H(M,x) = \text{"no"}\}.$$
We then have $S_H \subset \overline{K}$, $S_H$ is computably enumerable, and $\overline{K}$ is productive. Computability theory teaches us that $\overline{K} \setminus S_H$ is infinite, i.e., every partial Halting oracle fails infinitely often.
You may try to measure the ratio of $S_H$ to $\overline{K}$ in some fashion, such as the measure you suggest in the question. However, the problem with all such measures is that they heavily rely on how machines are coded. By passing to a different coding we can maipulate the measure to be whatever number we like, so that is not very helpful. For instance, to get a 99% success rate, use the following coding: a number of the form $100 n$ encodes the machine encoded by $n$ in some standard encoding, while a number of the form $100 n + r$ with $0 < r < 100$ encodes a machine that obviously never halts (always the same machine).


What constant in the latest fast matrix multiplication is hidden by Big-O notation?

All improvements since Strassen's original algorithm only achieve their exponent in the limit. That is, if they are stated as $O(n^c)$ algorithms, what they really show is that for every $\epsilon>0$ you can multiply two $n\times n$ matrices using at most $C_\epsilon n^{c-\epsilon}$ multiplications, where the constant $C_\epsilon$ blows up badly (exponentially in $1/\epsilon$?) as $\epsilon\to0$. (Coppersmith and Winograd showed that this kind of behavior is actually necessary.)

The papers don't explicitly compute $C_\epsilon$. One reason is that if you are serious about the constant, then you will probably need to apply low-level optimizations that will improve $C_\epsilon$ at the expense of the simplicity of the algorithm. Another reason is that due to the exponential dependence on $1/\epsilon$, you don't expect the result to be practically meaningful, so it's not really worth it. A third reason is that fast matrix multiplication algorithms are developed in a more abstract framework, which makes it awkward to come up with an actual explicit algorithm.

Fast matrix multiplication algorithms are recursive, that is, they iterate a smart $m\times m$ multiplication algorithm. Whereas for Strassen's original algorithm $m = 2$, for the improvements $m$ depends on $\epsilon$ (exponentially?), and so you will only be able to apply the base case for very large matrices; and for such large matrices, you would actually do much worse than the high school algorithm. The benefits of these algorithms only show up once they have been iterated many times, which would correspond to astronomically high (or worse) dimensions.

If you do feel like working out a constant, there are several expositions of the theory of fast matrix multiplication. You could take the first improvement over Strassen's original algorithm, and try to work out what the parameters are like.


How to find 5 repeated values in O(n) time?

The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:

Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\sigma_d = \sum_{i=1}^n A[i]^d$.
Compute $\tau_d = \sigma_d - \sum_{i=1}^{n-5} i^d$ (you can use the well-known formulas to compute the latter sum in $O(1)$). Note that $\tau_d = m_1^d + \cdots + m_5^d$, where $m_1,\ldots,m_5$ are the repeated numbers.
Compute the polynomial $P(t) = (t-m_1)\cdots(t-m_5)$. The coefficients of this polynomial are symmetric functions of $m_1,\ldots,m_5$ which can be computed from $\tau_1,\ldots,\tau_5$ in $O(1)$.
Find all roots of the polynomial $P(t)$ by trying all $n-5$ possibilities.

This algorithm assumes the RAM machine model, in which basic arithmetic operations on $O(\log n)$-bit words take $O(1)$ time.

Another way to formulate this solution is along the following lines:

Calculate $x_1 = \sum_{i=1}^n A[i]$, and deduce $y_1 = m_1 + \cdots + m_5$ using the formula $y_1 = x_1 - \sum_{i=1}^{n-5} i$.
Calculate $x_2 = \sum_{1 \leq i < j \leq} A[i] A[j]$ in $O(n)$ using the formula
$$
x_2 = (A[1]) A[2] + (A[1] + A[2]) A[3] + (A[1] + A[2] + A[3]) A[4] + \cdots + (A[1] + \cdots + A[n-1]) A[n].
$$
Deduce $y_2 = \sum_{1 \leq i < j \leq 5} m_i m_j$ using the formula
$$
y_2 = x_2 - \sum_{1 \leq i < j \leq n-5} ij - \left(\sum_{i=1}^{n-5} i\right) y_1.
$$
Calculate $x_3,x_4,x_5$ and deduce $y_3,y_4,y_5$ along similar lines.
The values of $y_1,\ldots,y_5$ are (up to sign) the coefficients of the polynomial $P(t)$ from the preceding solution.

This solution shows that if we replace 5 by $d$, then we get (I believe) a $O(d^2n)$ algorithm using $O(d^2)$ space, which performs $O(dn)$ arithmetic operations on integers of bit-length $O(d\log n)$, keeping at most $O(d)$ of these at any given time. (This requires careful analysis of the multiplications we perform, most of which involve one operand of length only $O(\log n)$.) It is conceivable that this can be improved to $O(dn)$ time and $O(d)$ space using modular arithmetic.


A hash function with predicted collisions

Generally the collisions in a hash function are, in a way, what winds up improving the running time.

This is because running time (or size, or insertion time) is generally defined in terms of worst-case input.  If you use an algorithm without any randomness or hash, you need to deal with the worst case.  For example, finding duplicate elements in an array has an $\Omega(n\log n)$ in the comparison model, same as sorting.  But if you just hash the values, you can determine whether or not there's a duplicate in $O(n)$ time and space with a small probability of error.    Determining a hash function that wouldn't collide, eliminating the possibility of error, has to take $\Omega(n\log n)$ time.  (You may notice that these are, in a way, the same problem--though of course hashed values generally belong to a smaller universe and the comparison model may not be appropriate).

That said, there are some ways to take advantage of the ways hash functions collide.  One is locally sensitive hash functions, in which elements with small differences (i.e. normal distance functions for points) hash to the same value.  Recently I've been reading this paper(1), which I found really easy to read, and shows some good, intuitive applications for how a locally sensitive hash function can be used to solve seemingly difficult problems--in this case the nearest neighbor problem with small probability of error.

Incidentally, the space advantage of possible collisions is how bloom filters work, a data structure that allows you to store elements of a set, each in space smaller than their actual size.  They are a constant factor away from optimal, and the upper and lower bounds demonstrate the tradeoff between error and space.

(1) Neylon, T.  A locally sensitive hash for real vectors.  SODA2010.


Subset sum into a consecutive range vs. standard subset sum

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$.

Given an instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$, construct an instance of subset sum with elements $x_0,\ldots,x_{n-1},1$ and target $X+1$. You take it from here.


As mentioned in the comments, DP is a perfectly valid solution to the problem. If the numbers are too large to calculate directly the number of solutions, then you can take things mod 10^9 + 7 during intermediate steps, too. This will work out because $(a \% b + c \% b) \% b = (a + c) \% b$ (for positive numbers or programming languages that implement negative mod correctly such as Python.

For a more elegant approach, you can calculate directly using more combinatorics. You know the total number of paths in the rectangle before part of it was removed, so it suffices to count the number of paths that went through the removed portion. To do this, take a diagonal from the bottom left of each removed rectangle up and to the right until you reach the border, Any path that goes in the removed portion must hit this diagonal, so if you sum the number of paths there are through each spot on the diagonal, you know how many paths to remove from your total. To count the number of paths that go through a square, count the number of paths to that square and multiply by the number of paths from there to the finish.

A fancier version of this approach is to count directly the paths that avoid the removed portion. To do this, take a diagonal from the corner of the removed rectangle (but not including it) down and to the left until you reach the border. A path avoids the removed rectangle if and only if it goes through this diagonal, so you can sum the number of paths through each location on this diagonal. Again, multiply the number of paths to a point by the number of paths from that point.


Finding the Largest "Ordered" Difference in Elements of an Array

The first observation is that the strategy of buying at the lowest price or selling at the highest price does not always maximize the profit. As you also note, the simple brute-force method works by trying every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $n \choose 2$ dates and $n \choose 2$ is $\Theta(n^2)$.

To achieve $o(n^2)$ running time, a simple transformation is applied to the input array. Instead of looking at the daily prices given, we will instead work with the daily change in price, where change on day $i$ is the difference between the prices after day $i-1$ and after day $i$. With a transformed input array like this, we now want to find the nonempty, contiguous subarray whose values have the largest sum. This contiguous subarray is called the maximum subarray.

For a detailed divide-and-conquer algorithm running in $\Theta(n \log n)$ time, see for example Chapter 4 of the Cormen et al. book, 3rd edition, page 68-74. The Wikipedia page also mentions Kadane's linear time algorithm and gives pseudocode.


In general it is impossible to tell. When people say that a graph has maximum degree 3, they could mean two different things:

The maximal degree of a vertex in the graph is 3.
All vertices in the graph have degree at most 3.

Similarly, a function of degree $d$ sometimes means a function of degree exactly $d$, and sometimes a function of degree at most $d$. In many contexts, the difference is immaterial. For example, a graph of maximum degree 3 on $n$ vertices has at most $1.5n$ edges – and this holds for both meanings.

If the difference is pertinent, then one would hope that you could tell which meaning is intended from context. For example, if we are trying to understand how large the maximum degree can be under some constraints, then probably we refer to the first meaning; and if we have an inductive argument which removes edges, then we might refer to the second meaning.


Is there a random shuffle algorithm using only true /false?

No, there is no algorithm that shuffles an array of length $n > 2$ using a bounded number of random Booleans. This is because given an algorithm that uses $m$ random bits (at most), each outcome has a probability of the form $A/2^m$, whereas we need each possible permutation to have probability $1/n!$.

When you're using Fisher–Yates shuffle in the form you describe you aren't getting a uniformly random permutation, though you are getting something very close. If you want to get a truly uniform random permutation then you need to use some form of rejection sampling.

Using bubble sort in the way you describe would likely be a disaster – it would likely result in a random permutation which is easy to distinguish from uniform. Don't do that. There are no tricks and shortcuts. If you want your random permutations to be faster at the cost of being slightly less uniform, you can reduce the precision involved in approximating random integers inside the Fisher–Yates shuffle. This will probably be much better than inventing your own algorithm.


Complexity of an algorithm for bounding a region in 2D

This question is not well-posed.  You haven't told us what form you want the answer in, nor what you know about the region.  In the fully general case, this problem is not solvable in any finite amount of time: there are uncountably many possible regions, so you can't even describe all of them in finite space.

Perhaps what you want is an approximation to the region (or to its perimeter).  If so, you need to figure out how you want it to be described, and what approximation metric you are using.

A plausible approach is to find a bounding box, then sweep a vertical line from left to right.  If your region is convex, then given the vertical line $x=1$ (say), you can find all points on that line that lie within your region by using binary search (twice): the result will be that all points $(x,y)$ satisfying $x=1$, $f(1)\le y \le g(1)$ are in the region, for some values $f(1),g(1)$.  Now if you know that all of the points in your region lies satisfy $1 \le x \le 5$, you can iterate over values of $x$, from $1$ to $5$ by steps $\epsilon$, and find the values of $f(x)$ and $g(x)$ for each such $x$.  This gives you about $8/\epsilon$ points on the perimeter of the region.  Now, you could interpolate along these points somehow to get a plausible approximation to the shape of the region.

Whether this is good enough will depend upon your particular application and what you are trying to accomplish.  Since you haven't told us that, we can't evaluate whether this is an adequate solution for your needs.  (That, incidentally, is why the question is not well-posed.)


Check whether it is possible to turn one BST into another using only right-rotations

If $T_1$ and $T_2$ don't encode the same sequence, they are not right-convertible into each other (obviously). This can be tested in linear time by inorder traversal of both trees.

The following procedure tests, if $T_1$ can be right-converted into $T_2$:

If both trees are empty, $T_1$ is right-convertible into $T_2$.
Right rotations move the root of the left subtree to the root of the complete tree. Thus, only nodes on the left flank of the tree can be rotated to the root. If the root node of $T_2$ is not on the left flank of $T_1$, $T_1$ is not right-convertible into $T_2$.
If the root $r_2$ of $T_2$ is on the left flank of $T_1$, obtain $T_1'$, by rotating $r_2$ up one level repeatedly, until $r_2$ is the root. Now $T_1$ is right-convertible into $T_2$, if and only if the left and right subtree of $T_1'$ are right-convertible into the left and right subtree of $T_2$, respectively.

Runtime:

Since each node will be rotaded up only once and by at most as many steps as the height of the tree, we need at most $O(n^2)$ rotations. If in $T_1$ all nodes are on the left flank and in $T_2$ all nodes are on the right flank, we will need $\frac {n(n-1)}2$ rotations, so the worst case runtime is in $\Theta(n^2)$.

Correctness:

If the algorithm finds a sequence of rotations, there obviously is one. To see the other direction, note the following:

If we rotate $r_2$ off the left flank, we immediately destroy right-convertability. So such rotations can never be necessary.
Any rotation not involving $r_2$ will affect a subtree, that is not changed by moving $r_2$ to the root. (It may be moved around as a whole, but this is independent of rotations within the subtree.) So if this rotation is necessary, we can still do it at a later time.

From these points correctness follows by structural induction.


Your problem appears to be:

Given strings $S,T$, determines whether $S$ appears as a subsequence of $T$.

There are several ways you could approach this.

One way is to use dynamic programming and apply a straightforward modification to computing the Levenshtein edit distance, where you set the cost of an insertion to be 1 and the cost of a deletion or replacement to be $\infty$.

Another solution to use a string-matching algorithm.  Build the regexp $.\star S_1 .\star S_2 . \star \cdots . \star S_n . \star$ and check whether $T$ matches this regexp, using any standard method (e.g., convert the regexp to a NFA or DFA).  For instance, if $S$ is the string HOT and $T$ is the string HELLO THERE, then you will check whether HELLO THERE matches the regexp .*H.*O.*T.*.  I suspect this might be faster, but the best way to find out is to try it and see.


Is the problem of deciding whether a Context free grammar generates exactly K strings is decidable?

As you said, if there is a cycle of variables (non-terminals), the language generated is infinite. If you can also show the converse, that is, if the language is infinite, then there exists a cycle of variables, then you can construct a machine to do the following given a finite $K$:

Given a context-free grammar $G$, check if it has any cycles of non-terminals.
If yes, then $L(G)$ is infinite, so output no; otherwise, $L(G)$ is necessarily finite (using the converse property above, which you need to prove).
Since the grammar generates a finite number of strings, it is safe to try all possible paths of productions starting from the starting variable. Each such path corresponds to a string in $L(G)$. Eventually, all possible paths will be exhausted (as otherwise $L(G)$ would be infinite), at which point you will have generated $L(G)$. If $|L(G)| = K$, output yes, otherwise output no.


Has the graph isomorphism problem been solved?

No.  That paper appears to be flawed.  The flaw was explained in a comment by Tracy Hall on MathOverflow.  A follow-up comment claims that the author later realized there is a flaw in his algorithm.

As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed.  When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.


How do Context Sensitive Grammar systems work?

Your understanding of Linear Bounded Automata is incorrect.  These automata are NOT derived from Pushdown Automata - there is no 'stack' in them.  A closer understanding would be that LBA are a special, 'truncated' form of Turing Machine, in which the size of the tape is restricted to being linearly-proportional to the size of the input string (actually, with a large enough alphabet, the tape space can be limited to -just- the space taken by the input string).
Also, the grammar-expansion behavior described in (1) is more closely analogous to a Lindenmyer System, which is not quite the same as a CSG (in which only one substitution takes place at any one step, so (3) isn't a concern).


Linear-bounded automata accept the class of context-sensitive languages. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of recursive languages. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is not context-sensitive by the nondeterministic space hierarchy theorem.


Enumerating pairs of disconnected cliques in a graph

I figured out this solution while discussing with a Professor.

The above problem could be formulated into a clique search problem. Let the input graph be $G_1 = (V_1,E_1)$. Create a duplicate $G_2 = (V_2,E_2)$ of $G_1$. Let vertices in $V_1$ be denoted by $\{v_{11},v_{12},...,v_{1k}\}$ and their duplicates in $V_2$ be represented by $\{v_{21},v_{22},...,v_{2k}\}$. Now, for each pair of vertices $(v_{1i},v_{1j})$ in $G_1$ without an edge with $(i<j)$, connect $(v_{1i},v_{2j})$. Then, all the desired pairs of disconnected cliques of $G_1$ can be obtained as cliques of $G_1 \cup G_2$ that have vertices in both $G_1$ and $G_2$.


How to teach abstraction needed for programming?

To the extent that this question is on topic here (that is, without reference to literature on mathematical education), I would propose that experimenting with concrete instances is not antithetical to the development of abstract concepts.

In an educational setting in computer science, it should be clearly stated and agreed upon that formal reasoning is the goal, and aquiring an intuitive grasp on things is not enough. After this is established (not trivial, literally counterintuitive), abstractions and concrete examples can help each other, not get in the way of each other.

The thing is, formal reasoning is not something that we do, it is what we are as a field - which is why studying the history of computing is so important. It can be tedious though, unnerving sometimes. It must be gradually developed as a habit. Intuitions are naturally captivating, and that is why we tend to rely on them to motivate our students, but there is something captivating about formalization too. Our challenge is to bring it to the center of the stage.