little-oh proof

An equivalent but more straightforward question would be why $\lg n$ is dominated by $\lg^2 n$, that is why $\lg n \in o(\lg^2 n)$.

Then based on the definition of little-oh we need to show that for any choice of constant $ c > 0 $, we can find a constant $ n_0 $ such that the inequality $ \lg n < c \lg^2n $ holds for all $ n > n_0 $.

We prove that if we pick $ n_0 = \sqrt[c]{b} $ where $ b $ is the base of $ \lg $, then the definition above holds.

If $ n_0 = \sqrt[c]{b} $ then we have $ n > \sqrt[c]{b} $ or $ n > b^{\frac{1}{c}} $.  Now since $\lg n$ with a base $ b > 1 $ is an increasing function, then $ \lg n > \lg b^\frac{1}{c} $ or $ \lg n > \frac{1}{c} $.  If we multiply both sides by $ c > 0 $, we have $ c \lg n > 1 $.  Now we can multiply both sides by $ \lg n > 0$ (Note that for $ \lg n > 0 $ to be true, we must have $ n_0 \geqslant 1 $ which leads to $ \sqrt[c]{b} \geqslant 1 $ or $ b^\frac{1}{c} \geqslant 1$ which results in $ \lg b^{\frac{1}{c}} \geqslant \lg 1 $ or $ \frac{1}{c} \geqslant 0 $ or $ c > 0 $; which is already guaranteed.) to have
$$
 c \lg^2 n > \lg n .
$$
This is what we needed to show.

Big-Oh proof sketch

A slightly different but related question could be why $\lg n$ is bounded above by $\lg^2 n$, that is why $\lg n \in O(\lg^2 n)$.

The answer is that since $\lg n > 1$ for $n$ larger than the base of $\lg$, then if we raise $\lg n$ to any power greater than $1$ (including power of $2$), it will be larger than $\lg n$ itself.

(We could rather argue that since we proved that $ \lg n \in o( \lg^2 n) $, it follows from $ o(f) \subset O(f) $ that $ \lg n \in O( \lg^2 n) $.)

Note

So yes, the rule of $n^a > n^b$ if $a > b $ and $ n > 1 $ does apply here.  Note that this rule is equivalent to the statement that any exponential function with a base greater than $1$ is an increasing function.


rebalance red-black tree with many violations

In general, I would say that the algorithm you want is a tree union (also called a merge), which takes two trees and combines them so that the new tree contains the union of the keys of both inputs. You can read a brief description on Wikipedia, or a more in-depth description (which generalizes to other balancing schemes such as AVL, BB[α], Treap) in a recent paper.

However, it seems that your use-case is slightly more specific than a tree union. In particular, I'm guessing that the subtrees you are grafting onto the existing tree don't violate the ordering property of the BST. In this case the algorithm you want is even simpler than a tree union, and is much closer to a simple insertion:

// graft B onto T
function graft(T, B):
  let (L, R) = split T at B.root.key
  return join(L, join(B, R))

This algorithm is inspired by the union algorithm but does not need to recurse, because of the nice properties of the input. It uses two functions which I've summarized below; you can find them described in more detail in the links I provided above.

split cuts a tree at a specific key k, producing two trees L and R where all keys in L are less than k, and all keys in R are greater than k.
join takes two trees (L, R) where all keys in L are smaller than all keys in R and combines them into a single tree.

Both split and join have logarithmic time complexity. Because of this, graft only takes logarithmic time. If you have a small number of branches to graft, then simply iteratively applying graft should be fastest. However if you have a large number of branches to graft, it may be faster to first combine them into a single tree and then merge this tree with the original.


High-level requirements for a Proof of "Saving to the Database"

The SoftwareEngineering.SE link gives the wrong answer for the right reasons. You can only ever prove anything with respect to a formal model. Verifying that that formal model accurately captures reality (or at least accurately captures the parts you care about for your purposes) is an informal process. In many applications of formal methods, one of the most time consuming and difficult parts is creating and validating the formal model. For example, for the CompCert project they had to make both a formal model for the behavior of C and a formal model for the behavior of the target processor (at least for the instructions they use). Both of these are massive undertakings on their own.

It makes no sense to "add more detail to the proof". Either a statement has a proof or it doesn't. It's proven if it has a proof. All proofs are equivalent for this purpose. What you can add more detail to is the formal model. Except "add more detail to" has the wrong connotations. You generally want the least detailed model that is accurate and for which you can prove your desired properties, e.g. correctness. The only reasons to change to a more detailed model is 1) you can't actually prove what you want with the original model, 2) the original model is wrong in which case your new model is not compatible with it, or 3) which is really a variant of (1), there is a different program that you could write that exploits those details to achieve the same functional behavior but different non-functional properties such as performance or implementation simplicity. In all these cases we need a new proof because we've changed the statement we're proving: either by changing the program or by changing the assumptions.

There are two aspects to the use of a formal model. First, as far as your program is concerned, it doesn't care if the database saves the data or even if the database exists. It only cares that the operations it uses behave as specified with respect to a given formal model. That formal model can be very high-level and abstract with no reference to any notion of "database" or "network" or "HTTP". However, it will likely be quite complicated to soundly capture the realities of the actual underlying systems. Second, at the systems level, you certainly do care whether the data was committed to the database as opposed to just being stored in some local cache. At the level of the program, there is absolutely no way for you to guarantee this. Your program could always be running in a sandbox that mimics any observable behavior. All you can prove at the program level is that your program will invoke some sequence of operations that putatively will lead to data being committed to the database. At some point you just have to accept based on empirical evidence that the chosen real world implementation faithfully implements the formal model. You can provide an implementation of the primitives of a high-level model with respect to a lower-level formal model that has been proven correct if you want to reduce how much you need to accept without (mathematical) proof.

The current state of play is that most programming languages lack publically available, normative (mechanized!) formal models let alone the underlying hardware. Ipso facto, most standard libraries, applications, operating systems, drivers, etc. are not proven correct since they have nothing with respect to prove their correctness. This is both in the sense that there isn't a formal model of what "correct" even means, nor is there a formal model of the implementation language so that you know what the implementations even do. In other words, in most cases we neither know what an implementation does nor what we even want it to do. This is why the artifacts (and tooling) produced by the CompCert projects and its related projects and by the $\mathbb K$ framework folks and several other groups are so important. Without these artifacts, you either use some massively over-simplified and weakly verified formal model that implicitly assumes millions of lines of codes are "correct" (spoiler: they aren't)1, or you invest man-centuries building a chain of trust. With luck, in the near-ish future some critical mass of formalization will be reached and proving the correctness of your program will become proportional to the complexity of your program and not the entire ecosystem.

1 While using an oversimplified formal model doesn't provide most of the benefits of "provable correctness", it does, in practice, do an excellent job of improving code quality by revealing mistaken assumptions in the code. Of course, the mistaken assumptions in your formal model have to be detected the old-fashioned way for the most part.


Is there another type of list than arraylist and linked-list?

Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example:

Binary Tree or d-ary tree is a hierarchical structure that stores nodes in the form of parent and child nodes.

Directed or Undirected Graph can be represented using adjacency list data structure which represents all possible connections between a set of objects. In other words, it is an array of lists.

Doubly Connected Edge List is used for performing fast operations on planar graphs and 3-dimensional polytopes.

Skip List is a randomized data structure that provides $O(\log n)$ insertion in a linked list

Likewise, you can even design your own data-structure based on different requirements. It is all about how you arrange and connect the objects.


How to avoid permutations in the n-Queens problem?

Note that your solution is not optimized - if you really want a speed boost, you should handle rotations / mirroring instead of looping through every possible combination. With a large board, this will be much more significant than looping through the solutions one extra time.

There are a few ways you could handle the permutations. I would handle them as a secondary check under if (n_queens_are_on_the_board), resulting in the following algorithm:

solve(queens){
    if (n_queens_are_on_the_board){
        if (solution_is_sorted) {
            remember_solution();
        }
        return;
    }
    for(x: 0 to n){
        for(y: 0 to n){
            if(current_position_not_attacked){
                add_queen_to_current_potision();
                solve(board);
                remove_prevously_added_queen();
            }
        }
    }
}

All that you have to do now is define a function to tell if the solution is sorted - again, there are a few ways you could do this. The simplest is probably to define the hash of a point to be point[0] * length(points) + point[1] and discard the solution if the hash of position n + 1 is less than the hash of position n. With this algorithm, you will end up with the solution (0,1) (1,3) (2,0) (3,2) from the sample provided.


Computing the minimum distance between each pain of points

Suppose the points are $[4,1,10,11]$.  The distance from the starting point (whether you interpret that as $4$ or $1$) to each other point does not give you the nearest pair of points.

In this problem, the input is an array containing numbers, not in sorted order.


Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array

You are almost there. In the first merge pass we do $\frac{k}{2}$ merges each taking time proportional to $2n$. In the second merge pass $\frac{k}{4}$ merges each taking $4n$ (note how nicely the factors 2 and 4 cancel and each merge pass runs in $\Theta(nk)$ time). Finally, since we need only $p = \log_2k$ merge passes, we obtain the running time of $\Theta(nk \log k)$.


Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $

You can write your language as a union of simpler languages:
$$
\{ a^{i+2} b^i : i \geq 0 \} \cup
\{ a^{i+1} b^i : i \geq 0 \} \cup
\{ a^i b^i : i \geq 0 \} \cup
\{ a^i b^{i+1} : i \geq 0 \} \cup
\{ a^i b^{i+2} : i \geq 0 \}
$$


Please skip that article at tutorialspoint. Instead, read this article at GeekforGeeks, which is much better. You may want to check my answer to another question.

The common abbreviations for Left rotation, Right rotation, Left-Right rotation, Right-Left rotation are L, R, LR and RL respectively, as expected. These rotations can be applied to all kinds of binary search trees. For example, they are applicable to red-black trees, too.

Please note that there is minor confusion about the terminologies. However, I would say that more than 9 out of 10 times, you will encounter the mainstream terminologies as explained in that GeekForGeeks article.

A common reference to rebalance AVL trees is the Wikipedia entry on AVL trees.


Recurrence with a function of n times T()

You can use the more elementary method in which you expand the recurrence:
\begin{align}
T(n) &= n^2 + n^{1/3} T(n^{2/3}) \\ &= n^2 + n^{5/3} + n^{5/9} T(n^{4/9}) \\ &= n^2 + n^{5/3} + n^{10/9} + n^{19/27} T(n^{8/27}) \\ &= \cdots
\end{align}
This suggests that $T(n) = O(n^2)$. Indeed, let us try to prove by induction that $T(n) \leq Cn^2$:
$$
T(n) \leq n^2 + n^{1/3} \cdot Cn^{4/3} = n^2 \left(1 + \frac{C}{n^{1/3}}\right),
$$
which will be at most $Cn^2$ for any $C>1$ and large enough $n$ (depending on $C$).
Indeed, defining $S(n) = T(n) - n^2$, we have
$$
S(n) = n^{5/3} + n^{1/3}S(n^{2/3}),
$$
and so the same argument shows that $S(n) = O(n^{5/3})$ and so $T(n) = n^2 + O(n^{5/3})$. In the same way, we can get $T(n) = n^2 + n^{5/3} + O(n^{10/9})$, and so on.


The MBR refers to the format used by (many but not all, and slowly being replaced by GPT) disk to identity partitions. A partition is simply a contiguous range of blocks on the disk. A partition is often used to store data, in the form of files and directories. But of course a disk knows nothing about files and directories. A file system is a system that controls how your data is stored on the disk. A file system is really two things:

it specifies how the data is organized and accessed (directories, files, links, permissions, encryption, ...): this is the logical aspect
it specifies how this data is encoded on the disk: this is physical aspect

There exists many file systems: FAT, exFAT, NTFS, ext, btrfs, HFS, XFS,  ISO 9660 and others. FAT is a file system invented by Microsoft. What this means is that they designed the logical and physical aspects of it, and they applied and were granted a few patents on it. They also wrote the Windows driver for FAT, but note that anyone can do that (assuming the file system is properly documented and ignoring royalties issues) and indeed linux and MacOS have their own driver which follows Windows's specification.

Now as I explained a file system specifies how the data is encoded on the disk and FAT is not exception. The first sector of a FAT partition (also known as the boot sector, or super block) is what is described in the link you gave: is starts with 3 bytes for a jump instruction and is followed by the BIOS/OEM Parameter Block (which has a different format on FAT12, FAT16 and FAT32). This OEM block is specific to FAT and does not exist on other file systems. Other file systems use a different format. I might add that calling this the OEM/BIOS block was very unfortunate because it really has little to do with BIOS or OEM, but that was the name Microsoft came up with. It should really be called the FAT Parameter Block.

To finish, designing a good file system is hard because they are many trade-offs to make. FAT is simple and relatively robust, but sucks at about everything else if I may say. Sadly it is also the only file system that all OSes support and so is the de facto standard for interoperability.


Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?

$DTIME(n^2) \subseteq \mathcal{P} \subseteq \mathcal{NP}$ and by the Time Hierarchy Theorem  $DTIME(n^2) \nsubseteq DTIME(n)$
Therefore $\mathcal{NP} \neq DTIME(n)$


How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?

Exponential time is not required for finding the requested probability.  In fact, only linear time is needed, as we will see below.

First let's define some additional notation.  Let $X = (x_1, x_2, \ldots, x_n)$ and $Y = (y_1, y_2, \ldots, y_n)$ -- that is, two $n$-tuples of our variables.  Let $\mathbf{1}$ denote an $n$-tuple of 1s, $ (1, 1, \ldots, 1)$.  And let $S_n$ denote the set of all possible $n$-tuples of $0$ and $1$.  In CS literature, the elements of $S_n$ are sometimes called "strings".  If $\sigma$ is one such element, we write $\sigma(k)$ for its $k$th component.

In this new notation, the task is to compute $\Pr(Y = \mathbf{1})$.  We can marginalize out the configuration of 0s and 1s on $X$ as follows:
$$\Pr(Y = \mathbf{1}) = \sum_{\sigma \in S_n} \Pr(Y = \mathbf{1} | X = \sigma) \Pr (X = \sigma).$$

From the prompt we know that each $x_k$ is 0 or 1 with equal probability, so $\Pr (X = \sigma) = 2^{-n}$ for every $\sigma \in S_n$.  Additionally, for any given $\sigma \in S_n$, we know that $\Pr(Y = \mathbf{1} | X = \sigma) = \prod_{k=1}^n p_{k,\sigma(k)}$, since the probabilities $p_{k,\sigma(k)}$ are independent.  Combining these observations, we obtain
$$\Pr(Y = \mathbf{1}) = 2^{-n} \sum_{\sigma \in S_n}  \prod_{k=1}^n p_{k,\sigma(k)}.$$

Our next step is to show that we can factor the left-hand side of this equation as follows:
$$\sum_{\sigma \in S_n}  \prod_{k=1}^n p_{k,\sigma(k)} = \prod_{k=1}^n (p_{k,0}+p_{k,1}).$$
We prove this inductively.  When $n = 1$, both sides are $p_{1,0}+p_{1,1}$, so the base case holds.  For the inductive case, we assume the $(n-1)$th case and write the $n$th case as
$$(p_{n,0}+p_{n,1}) \sum_{\sigma \in S_{n-1}}  \prod_{k=1}^{n-1} p_{k,\sigma(k)} = (p_{n,0}+p_{n,1}) \prod_{k=1}^{n-1} (p_{k,0}+p_{k,1}).$$
Both sides simplify to those of the above identity, respectively, so the identity is proved.

This leaves us with the result that $\Pr(Y = \mathbf{1}) = 2^{-n} \prod_{k=1}^n (p_{k,0}+p_{k,1}).$  For a hash table representation, look-up times are $O(1)$ for each $p_{k,0}$ and $p_{k,1}$, so we can compute this product with a simple for-loop in a runtime of $O(n)$.


If you mean result in terms of state, then you can compute this by applying the matrix $I \otimes H$ to the Bell state.

If you mean what happens operationally, then observe that applying a hadamard gate on each qubit of the Bell state results in no change -- the resulting state is again the Bell state. So, if you apply two hadamard gates in parallel or none at all and then you measure both qubits, you will get perfect correlations between the measurement outcomes (measurement outcomes on the qubits are guaranteed to be equal). However, if you apply a hadamard gate to either the second qubit or the first qubit and then measure both qubits, then the measurement outcomes  will be completely independent of each other, that is, the measurement result of the first qubit can be $0$ or $1$ with $50\%$ probability and the measurement result of the second qubit can be $0$ or $1$ with $50\%$ probability, regardless of what was seen in the other measurement.

Algebra:

Given the state $|00\rangle + |11\rangle$, you can not compute the Hadamard gate by factoring the state and applying a Hadamard to only one qubit, as the state is entangled and cannot be factored into two independent qubits. You can, however, apply the result of $I \otimes H$, which is the operation of applying Identity gate on the first qubit and the Hadamard gate on the second. The resulting operation is, with scaling factor $s$,

$$ I \otimes H = \left[\begin{matrix}
1 & 0 \\
0 & 1
\end{matrix}\right]
\otimes
\frac{1}{\sqrt{2}}
\left[\begin{matrix}
1 & 1 \\
1 & -1
\end{matrix}\right]
= s\left[\begin{matrix}
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
\end{matrix}\right]$$

For more details on this, see the question How to apply a 1-qubit gate to a single qubit from an entangled pair?.

Now, you can pass your entangled state, $
\left[\begin{matrix}
\frac{1}{\sqrt{2}} & 0 & 0 & \frac{1}{\sqrt{2}}\\
\end{matrix}\right]^{T}
$ for $\frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$, through the gate and get
$$
s\left[\begin{matrix}
1 & 1 & 0 & 0 \\
1 & -1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & -1 \\
\end{matrix}\right]
\left[\begin{matrix}
\frac{1}{\sqrt{2}} \\ 0 \\ 0 \\ \frac{1}{\sqrt{2}}\\
\end{matrix}\right]
=
\frac{1}{2}\left[\begin{matrix}
1 \\ 1 \\ 1 \\ -1\\
\end{matrix}\right]
$$
Which is the state
$$|00\rangle + |01\rangle + |10\rangle - |11\rangle.$$
And measurement of the first qubit or the second qubit would be 0 or 1 with equal probability, and give no information on the state of the other qubit.


Proof of the undecidability of compiler code optimization

Optimized program must have the same behavior as the original program. Consider the following program:
int main() {
    f();
    g();
}

, where it's guaranteed that $f$ is pure function. The only question is: does it finish its execution? If it does, then we can replace main()'s body with g(). Otherwise, we should replace it with an infinite loop. Unfortunately, verifying whether f() finishes its execution is undecidable.
Another example is the program with body print(f(42)), where f is pure. The optimal program would just replace f(42) with its value. However, there is no algorithm that does this. We may try to compute it in compile-time, but it may never finish.
Another example (now without infinite loops). Assume that your program defines a context-free grammar and $f(x)$ checks whether string $x$ belongs to the language defined by this grammar (for any CFG we can build such $f$ automatically). Then if $f$ is a constant "true", then
if (f(x)) {
    g()
}

can be optimized to g(). Unfortunately, checking that grammar accepts all strings is called a universality problem and is known to be undecidable.


Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

Polynomial time means that the running time is bounded by a polynomial in the length of the input.  The running time here is bounded by $nW$.  $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a number up to $2^\ell$ so $W$ is potentially exponential in the length of the input, not polynomial.


What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is
$$
\sum_{k=0}^n n(n-1)\cdots(n-k+1) = \sum_{k=0}^n \frac{n!}{(n-k)!} = n! \sum_{k=0}^n \frac{1}{k!} \approx e \cdot n!.
$$
When the maximum clique has size $k$, the number of recursive calls is at most
$$
1 + n + n(n-1) + \cdots + n(n-1)\cdots(n-k+1) \leq 2n^k.
$$
Conversely, if you run the algorithm on a complete $k$-partite graph, then the number of recursive calls will be $\Omega(n^k)$.


Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?

At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to overcome this difficulty by letting the algorithm sometimes make moves that temporarily deteriorate the value of the current solution.


Is the sieve an improvement for prime finding over an optimized algorithm?

Sorry, but you can’t just count loops, the number of loops is totally irrelevant.

If you count nested loops, that is slightly significant but can be very misleading.

You need to count how many iterations a loop performs. In the first example, the number of iterations is up to primes.length, which is around n / log n. In the second example, the number of iterations in the inner loop is less than n / 2i, and i grows quickly.

Add a counter to each function and see how often the inner loop gets executed.

PS. Let n = 1 billion, and print say every 100th prime added to primeVals. Then check how long it takes. The sieve will take a good time. But I can promise you, the “optimised” algorithm will be a lot more than ten times slower.


What can be concluded from a full application of resolution?

By definition if a proof system is refutation-complete then once you've applied it to the maximum extent and not found a contradiction, you have proven that there are no refutations, i.e. the formula is satisfiable.  To find a satisfying assignment, add a unit clause that asserts a value for one of the variables, e.g. $(a)$, and use resolution on the resulting formula.  If you find a refutation (produce an empty clause), then replace the asserting clause with its negation e.g. $(\lnot{a})$, otherwise leave the original assertion in the formula.  Repeat the procedure with a different variable.  Eventually you'll have successfully asserted values for all the variables and found a satisfying assignment.


Efficient Algorithm for determining who wins a game of Chess

When talking about standard chess with an $8\times 8$ board, there is no asymptotics, so you can solve the problem in $O(1)$ time.

Your idea works fine, since for each position the size of the tree is bounded by some constant independent of the input (the tree size is bounded by the number of possible positions). You can now ask whether this solution is feasible or has any practical implications? The answer is obviously no, but when analyzing the asymptotic complexity of the algorithm, this doesn't matter.


Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-decreasing subsequence of length $N-M$; this can be reduced to strictly increasing subsequences by adding appropriate $\epsilon$s.)


Assume $H$ does not halt on $w$. To prove $L(A) = \Sigma^∗$ we need to show that $A$ accepts every $x$. Indeed, whatever $x$ is, we simulate the execution of $H$ on $w$ for only $|x|$ steps (a finite, known amount of steps). I.e., we do not simply run that program on its own, we keep an "alarm clock" counting the steps $H$ as it is running, and as soon as it reaches $|x|$ the alarm rings and we stop the simulation. In this way, no matter what $H$ does on $w$, the simulation will always terminate: either because $H$ halts before $|x|$ steps, or because the alarm rings and we abort the simulation.

Now, since $H$ does not halt on $w$ by hypothesis, $H$ will always make the alarm ring. In such case, $A$ accepts $x$ by construction, hence $A$ indeed accepts all inputs $x$.

For the other direction, assume that instead $H$ does halt on $w$. Let's write $k$ for the number of steps that make $H$ halt on $w$. We now need to prove that $L(A) \neq \Sigma^∗$. Take $x = 1^k$: we prove that $A$ rejects it. By definition, $A$ simulates $H$ on $w$ for $|x|=k$ steps, and that's just enough time to make $H$ halt. So, by construction $A$ rejects.


algorithm to delete nodes that completely removes connectivity

Your problem is: given a graph, find a minimum-sized set of vertices whose removal disconnects the graph.

This is the "minimum vertex cut" problem.  There are standard algorithms for this, based on network flow and the max-flow-min-cut theorem.  You need to modify the graph slightly to make two copies of nodes, then apply network flow (network flow on the original graph finds a minimum edge cut; you want a minimum vertex cut).  See https://en.wikipedia.org/wiki/Vertex_separator, https://en.wikipedia.org/wiki/Cut_(graph_theory), https://cstheory.stackexchange.com/q/2877/5038.


Can counting problems have optimal substructure?

I think you understand what's going on well.  It's just two different ways of looking at things.  I agree with you that I think PEG is being a bit pedantic.  Personally, I never particularly liked "optimal substructure + overlapping subproblems" as the definition of dynamic programming; those are characteristics that dynamic programming algorithms tend to have, and tend to help us separate dynamic programming from (say) divide-and-conquer or greedy algorithms.  I like to think of dynamic programming as recursion plus memoization (and possibly, plus table-driven bottom-up memoization).  But to each their own.


Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, to allow unspecified results when the invariant is broken.

This is not just a "C++ vs Java" difference, but a general difference in programming languages between the philosophies "undefined behavior can happen if you're not careful" and "undefined behavior can't happen, ever, and I'll try hard to report errors at runtime".

  Existing iterators, being pointers to nodes, are not invalidated by moving, adding, or removing nodes, as long as the iterators don't point to nodes that are later deleted.

The last part is crucial. C++ can say "iterators are invalidated", while Java wants to detect if those are used after they are invalidated (and raise an exception).

Detection can be expensive, and require each list to be aware of the iterators that are currently scanning the list, so that they can be checked and possibly flagged as invalid. Each list object should have a list of (weak references to) all the active iterators, and check whether they refer to deleted list cells.

Since this would impact performance, a simpler approach is to invalidate all the iterators every time the list is modified. This can be done by storing a single number in both list and its iterators. When the iterator is created, the number is copied from the list. When the list is modified, the number is incremented. When the iterator is used, we quickly compare the two numbers, and throw if they differ.

This is reasonably cheap, even if it's suboptimal because it invalidates all iterators, when that is not really necessary.

There is some middle ground between these two approaches. A Java library could avoid  undefined behavior, and allow the list to be in an invalid state when the invariant is broken, but allow iterators to remain valid in more cases (without trying to check this).
This means that all list methods can potentially throw, or produce invalid results, including failing to terminate. Debugging can be quite hard in such conditions, but that's the price to pay when invariants are not checked early at runtime.


Explanation of the Gelfond Lifschitz reduct

Due to b(j)., c(j):- a(j), not b(j). is not applicable and needs to be removed.
As all negated literals are deleted, c(i):- a(i), not b(i). is converted to c(i):- a(i).
Therefore, as I = {a(i), b(j), c(i), d(i, j, i)} is minimal representation of the remaining P, it is also stable.


Calculating gradient in a neural net using batches

This is known as stochastic gradient descent.  I suggest you read some background material on stochastic gradient descent; then I think you will understand.  There is lots written on that subject in many standard places.

Compare:

In standard gradient descent, we let $E(w)$ denote the total error across all training samples (as a function of the weights $w$), compute the gradient of $E(w)$ (with respect to $w$), and use that gradient to update the weights.
In stochastic gradient descent (in its simplest form), we pick a single training sample at random, let $E_1(w)$ compute the error on just that training sample (as a function of the weights $w$), compute the gradient of $E_1$ (with respect to $w$), and use that to update the weights.  We repeat this many times.  In each iteration, we pick a different randomly chosen training sample.

$E_1(w)$ can be thought of as a noisy approximation to $E(w) $, so the gradient of $E_1(w)$ can be thought of as an approximation to the gradient of $E(w)$.  Thus, in each iteration of stochastic gradient descent, we are moving in a direction that is roughly correlated with the direction standard gradient descent will take, but with some noise; over enough iterations, hopefully this noise will average out.  A crude intuition might be that $kn$ iterations of stochastic gradient descent are roughly comparable to $k$ iterations of standard gradient descent, if $n$ is the number of samples in the training set.
Stochastic gradient descent with batches is a more sophisticated form of stochastic gradient descent, where we randomly choose a batch of training samples (more than one sample, but less than all of them), sum the total error across the batch, compute the gradient, and use that to update the weights.


Is bounded waiting satisfied in this 2 process solution?

Bounded waiting is satisfied, the process $p_i$ will never be bypassed by $p_{1-i}$ after changing the value of $w_i$ (wants $i$) to $1$.

If $p_i$ set the value of $w_i$ to $1$, then in order to enter the critical section, $p_{1-i}$ must pass the while loop. This cannot happen until the value of $w_i$ is set to 0. The only place where $w_i$ is set to $0$, is after $p_i$ has finished, which means he will never be bypassed by $p_{1-i}$.

When in doubt, try to prove it yourself. If you agree that the number of times a process may be bypassed is at most $0$, then yes, bounded waiting holds.


Can algorithms of arbitrarily worse complexity be systematically created?

Yes, of course.  $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times.

The answer to your other questions are also yes, by the time hierarchy theorem.


$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?

The flaw is in the claim $\bigcup_{k=1}^\infty L_k  \in\bigcup_{k=1}^\infty a_k$.  That is not a valid conclusion.  It doesn't follow from the fact that $L_k \in a_k$ for each $k$.
(Consider: just because $3 \in S_1$ and $5 \in S_1$, it doesn't follow that $3+5 \in S_1 \cup S_2$.  Just because $L_1 \in S_1$ and $L_2 \in S_2$, it doesn't follow that $L_1 \cup L_2 \in S_1 \cup S_2$.  Just because $L_k \in a_k$ for each $k$, it doesn't follow that $\bigcup L_k \in \bigcup a_k$.  In fact, it is correct that $L_k \in \bigcup a_k$ holds for each $k$, but $\bigcup L_k \in \bigcup a_k$ doesn't hold; the regular languages are not closed under infinite unions.)
You won't always have us to check every dubious proof, so let me teach you two techniques you can use if you run across a proof that you are suspicious/skeptical of:

If you're not sure whether to be convinced of a proof, try taking each individual step and writing out a detailed proof of it.  If you started with a 4-line proof sketch, this might turn into a 40-line proof, so it's tedious, but it's often a good way to discover whether the proof is valid (sometimes when it comes time to write down the justification, you discover that that step that looks obvious in writing isn't actually so obvious).

Pick a specific example and work through what the logic of the proof is saying about that example.  Check whether the logic is valid for that particular example.
For instance, pick $L= \{0^n 1^n : n \in \mathbb{N}\}$; this is perhaps the canonical CFL that isn't regular.  Work through what your proof claims about that $L$, and check each statement to see if it is valid.  Well, $L_k = \{0^n 1^n : n \le k\}$, and sure enough, it is correct that $L_k \in a_k$ for each $k$.  It is also correct that $L = \cup_{k=1}^\infty L_k$.  However, when you check the claim that $\bigcup_{k=1}^\infty L_k  \in\bigcup_{k=1}^k a_k$, you discover that the claim is not correct, as the left-hand side is $L$ and the right-hand side is the set of all regular languages and $L$ is not regular.  So, that's the step you should be suspicious of.


Mapping intuitionistic logic to the modal logic S4

That is the right paper, but there are actually several equivalent embeddings.

The book Basic Proof Theory by Troelstra and Schwichtenberg gives two such embeddings. Here's one. If $P$ is atomic but not $\bot$:

$$P^\circ := P$$
$$\bot^\circ := \bot$$
$$(A \wedge B)^\circ := A^\circ \wedge B^\circ$$
$$(A \vee B)^\circ := \square A^\circ \vee \square B^\circ$$
$$(A \rightarrow B)^\circ := \square A^\circ \rightarrow B^\circ$$
$$(\exists x A)^\circ := \exists x \square A^\circ$$
$$(\forall x A)^\circ := \forall x A^\circ$$

Here's the other:

$$P^\square := \square P$$
$$\bot^\square := \bot$$
$$(A \wedge B)^\square := A^\square \wedge B^\square$$
$$(A \vee B)^\square := A^\square \vee B^\square$$
$$(A \rightarrow B)^\square := \square (A^\square \rightarrow B^\square)$$
$$(\exists x A)^\square := \exists x A^\square$$
$$(\forall x A)^\square := \square \forall x A^\square$$

They are equivalent in the sense that $S4 \vdash \square A^\circ \leftrightarrow A^\square$, and the embeddings are sound and faithful. The proofs are left as an exercise, or you can dig out the book.


The following paper answers a close variant of this question: The Efficient Construction of an Unbiased Random Sequence, Elias 1972.

The question there seems to be this: Given access to this biased independent source, output a sequence of random numbers in $[1,N]$ (note the difference from your question in which only one output symbol is requested). As the length of the desired output goes to infinity, the "efficiency" of the scheme in the paper (which seems like a natural generalization of von Neumann) goes to $1$, meaning, I believe, that an input with entropy $h$ is converted to an output of entropy approaching $h$.

The question seems much better behaved when phrased this way, rather than requesting a single output digit, because, for instance, if we draw $N$ samples and end up with an output with lots of information (for instance, all $N$ input symbols are distinct), then we can use all of that information to produce many output symbols, whereas with the question as phrased here, any information beyond that used to produce one output symbol goes to waste.

I believe that the scheme repeatedly takes $N$ draws, looks at the sequence, and maps it some outputs or the empty string. Perhaps there is a way to improve the scheme for your question by looking at prefixes and stopping if we have "enough" information to output a symbol? I don't know.


Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

Your PDA isn't deterministic, as it has moves for $q_0, \epsilon, a$ and $q_0, b, a$.


Find n-th number in a number system with only 3 and 4

You're on the right track, it is similar to binary in a way.

The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can treat $3$'s like a $1$ in binary, they have a value equivalent to $2^n$ where $n$ is the position of the digit, starting from the right $n$ starting at $0$.  Thus $3 \equiv 1$, $33 \equiv 3$, $333\equiv 7$, etc.

A $4$ has a value equivalent to $2^{n+1}$ starting from the right $n$ starting at $0$, so $4\equiv2$, $44 \equiv 6$, etc.

Because of the similarity to binary, we can convert our input (the decimal number) to binary, and then convert that to $3,4$.  To do so, we can use the following algorithm.

Given a binary number, iterate through the digits from right to left.

If the digit encountered is a $1$, place a $3$ for that digit in the result.
If the digit encountered is a $0$, and there are more digits following, place a $4$ for this digit in the result, and for any consecutive $0$'s, place a $3$ for those digits until a $1$ is encountered.  When a $1$ is encountered following a $0$ or series of $0$'s, if there are more digits following, change this $1$ to a $0$, and repeat step $2$ as if this were the first $0$ you've encountered.  When a $1$ is encountered and no more digits are following it, do nothing and return the result.

This reason this works is the following

Step $1$ uses the fact that $3$ has the same value in $3,4$ as $1$ does in binary.
Step $2$ is necessary because in $3,4$ there is no $0$ value for any digit.  Using the fact that $2^n = 2^{n-1} \times 2 = 2^{n-1} + 2^{n-1}$ we convert a $1$ followed by $n$ $0$'s to its equivalent form in $3,4$ of $n-2$ $3$'s followed by a $4$. The first $3$ has a value of $2^{n-1}$ and the remaining $3$'s and $4$ sum up to $2^{n-1}$.

This algorithm is roughly $O(\log n)$.


Conditions under which the 3-partition problem is not strongly NP-complete?

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete.

On the other hand, exhaustive search is not always the best approach for hard problems. Parameterized algorithm introduce methods usually to restrict the area where the exhaustive search must happen. Randomized algorithm offer methods where a greedy algorithm or a heuristic looking among bounded number of solutions gives an optimal answer with some probability. repeating the method enough number of times yield an answer with high probability. So no it does not mean that an exponential exhaustive method on the whole input is the best we can do. It only means unless $P = NP$, no polynomial time deterministic non-randomized algorithm can be designed for this problem.


Is this special case of a scheduling problem solvable in linear time?

A few things I found out so far.

We can reduce ourselves to solving the following related problem:

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

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

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

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

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

feasible schedule = head (leftOverItems schedule) == 0

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

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

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

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

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

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

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

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

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

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

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

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


Given a moving ball in a grid, which squares does the ball reach?

Exhaustively tracing the movement of the ball is the easiest to program, and also not too bad on efficiency grounds.  You should keep a hash table of all states of the ball that have been seen before (where the state of a ball is the grid square it is in, and which direction it is heading); if you see it repeat a past state, then you know it will loop forever and you can stop tracing the movement any further.  With this way, tracing the ball's movement will take at most $O(mn)$ time in the worst case.

This can be sped up by using a little bit of simple algebra to calculate "given the current state, what's the next wall the ball will hit?" in $O(1)$ time -- that will be faster, but not easier.

There is a more elegant and efficient solution, based upon number theory and on Tom Van der Zanden's technique of extending the grid infinitely.

Imagine a parallel universe where ball travels in a straight line in an infinite grid; as Tom says, bouncing off the walls in our universe is equivalent to continuing in a straight line in the parallel universe.  This is the first insight we will use.

Let's work out the implications of this insight.  In our universe the ball starts at some initial coordinate $(x_0,y_0)$, moving NE, and we want to know if will ever reach coordinate $(x',y')$.  What does this mean in the infinite universe?  Well, imagine placing mines at coordinates $(x',y')$, $(x',2n-y')$, $(x',y'+2n)$, $(x',4n-y')$, ..., $(2m-x',y')$, $(2m-x',2n-y')$, ... -- in particular, at coordinates $(2im \pm x',2jn \pm y')$ where $i,j$ range over all integers.  Then I claim that the ball will eventually reach coordinate $(x',y')$ in our universe if and only if the ball will eventually hit a mine in the parallel universe.  So our problem reduces to asking: in the parallel universe, will the ball ever hit a mine?

The second insight is that we can use number theory to answer that question.  In particular, after $t$ units of time, the ball will be at position $(x_0+t,y_0+t)$ in the parallel universe.  We want to know whether there exists any integers $t,i,j$ such that $x_0+t = 2im \pm x'$ and $y_0+t = 2jn \pm y'$.  Re-arranging these equations and using the language of modular arithmetic, we are asking whether there exists an integer $t$ such that both of the following equations hold:

$$\begin{align*}t &\equiv \pm x' - x_0 \pmod{2m},\\
t &\equiv \pm y' - y_0 \pmod{2n}.\end{align*}$$

Now we're all set to apply number theory.  In particular, this is set up perfectly to apply the Chinese remainder theorem.  Define $g = 2 \gcd(m,n)$.  Then the above system of equations has a solution in the integers if and only if

$$\pm x' - x_0 \equiv \pm y' - y_0 \pmod{g}.$$

In other words, we should check the following four conditions:

$x'-x_0 \equiv y' - y_0 \pmod{g}$
$-x'-x_0 \equiv y' - y_0 \pmod{g}$
$x'-x_0 \equiv -y' - y_0 \pmod{g}$
$-x'-x_0 \equiv -y' - y_0 \pmod{g}$

If any of those four conditions holds, then there is a solution to the above system of equations and thus in the parallel universe the ball will hit some mine; if none of those four conditions holds, then the ball will never hit any mine.  (These 4 conditions are the relevant conditions if the ball is initially travelling NE.  The other directions can be handled symmetrically with a similar set of 4 conditions.)

Rephrasing in terms of the original problem, we get a solution to the original problem that is easy to implement and runs in $O(1)$ time.  We compute $g=2 \gcd(m,n)$ and check the four conditions in the bullet list above.  If any of the four conditions holds, then the answer is yes: the ball will eventually reach the point $(x',y')$.  If none of the four conditions holds, then the answer is no: the ball will never reach the point $(x',y')$.


How balanced is a binary tree in the average case?

Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

To be a bit stereotypical: yes. There are reasonable ways to approach the problem, but it's so dependent on use case that you will need to take a look at how your particular algorithm builds binary trees to get information about your algorithm.
More specifically: you ask about the 'average' balance of a binary tree, but you can't have an average without a probability distribution on the set of binary trees. There are (infinitely) many different probability distributions, and different algorithms for generating trees will lead to different distributions on the set of trees generated.
For example, since the number of binary trees on $n$ nodes is finite, we can talk about the uniform distribution where we consider every binary tree equally probable, and ask what the average balance is there. For concreteness, I'm going to use height as a measure of the balance of a tree, because it's easy and well-studied, but note that there are plenty of other metrics you could measure by: maximal ratio between subtree sizes, for instance, would be another reasonable one. Looked at over the uniform distribution of $n$-node binary trees, the average height is proportional to $\sqrt{n}$, (almost) 'right between' the two extremes.
But very few algorithms would lead to a uniform distribution on binary trees. As an example of a more reasonable distribution, we could choose a permutation uniformly at random from the $n!$ permutations on $\{1\ldots n\}$ and then build a binary tree by inserting nodes labeled $1$ through $n$ into a tree in the given order. It can be shown that this process yields a tree with average height proportional to $\log n$, so trees generated in natural fashion from random data are generally 'pretty good'.


How can I compare two different neural networks, from a theorical point of view?

Essentially, no.  The only way to know which neural network is going to give you better accuracy is to try them on a realistic data set.  The theory we have is not well-enough developed to allow us to reliably predict which will do better on a particular data set.

A secondary remark.  When you remark "other programs might interfere", that's not correct.  Even if other programs are running (on a multi-tasking machine), they won't affect the accuracy.  They might take the process of running or training the neural network on your data set take longer, but they won't affect the results.


Does assembly language get translated to binary code? If so, is assembly language portable across machines?

Assembler code describes instructions for one particular architecture. It is slightly helpful by allowing you to use human-readable names for instructions, names for memory addresses, doing some simple calculations etc. but it is totally useless to produce instructions for any other processor.

With heroic effort you could create a translator that produces code for a different architecture but nobody would thank you for it. The advantage of assembler code is that it lets you write code for things high level software isn’t designed for - like writing the code to boot a computer, handle interrupts, doing a process switch - and that kind of code is often very machine specific; it might not even be usable on a different computer with the same processor.

So yes, for any portability you need a high level language.


What are the challenges of using gradient descent on hyper parameters λ and η to find out their optimum values?

The cost function $C(w,\lambda)$ is not a function of learning rate $\eta$. You can't compute the gradient of $\eta$.

$\lambda$ is part of the cost function. You can indeed compute its gradient and apply SGD on $\lambda$. However, when you do that, $\lambda$ will keep decreasing because its optimal value is obviously $-\infty$.

Note that it is possible to optimize hyperparameters like $\eta$ and $\lambda$ with another neural net, but that is a different story.


Why postfix is used more often than prefix expression?

The evaluation is easier for postfix-notation expressions.
The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time:

operand -> put it on the stack;
operator -> get from the stack the number of values it needs (two for +, three for ?:, one for unary - and so on), combine the values using the operator and put the result on the stack.
when the entire expression is processed, the stack contains only one value; it is the value of the entire expression.

The prefix-notation expressions can be evaluated using a similar algorithm that uses the operands (instead of the operators) to trigger computations. However, it is not that straight-forward; it involves lookups on the top of the stack to find the operator and to decide if enough operands were read for it.
The prefix-notation expressions can also be evaluated from right to left using the same algorithm as for postfix-notation expressions.


How are faces of a DCEL updated when triangulating a polygon?

For the algorithm that triangulates a monotone polygon: every time you add a diagonal, you actually find a triangle. So, you can indeed explicitly relabel the face-value associated with all edges of that triangle. That does not affect the asymptotic running time.

For the algorithm that splits a simple polygon in to monotone polygons you cannot really afford that, as you may have to relabel an (half)edge multiple times. Hence, a solution there is just to be lazy: i.e. use the sweep just to update the vertex/edge fields in the DCEL, and ignore the face values. When you are done with the sweep: use the vertex/edge fields, in particular the next-fields on the half-edges, to walk around every face, and set the face values appropriately.


What is memory model in computer organization?

um I'm not sure if it is what you are looking for or not. I assume by memory model you mean the part in which we place input and do some calculation (like paper which we write something to remember and calculate).

The memory model depends on the definition of the model itself. In CS we have different kinds of computing model with different power.
One of the simplest one is Deterministic Finite Automata and informally its memory just contains an input string and nothing more.
One of the most powerful one is Turing machine that its memory is a infinite tape.
There are other models between these two such as PushDown Automata and Linear Bounded Automata where loosely speaking their memories contains stack of symbols and finite tape.

Also there are other models with same power as Turing machine, like two stack PDA, cellular automata and etc.

So by how to define your computing model and program, your memory model details will be different.


Calculating Size of parts of tree cut by an edge in a tree

You can use dynamic programming in its version for trees. Choose a root arbitrarily, and calculate recursively the number of vertices in the subtree rooted at each node. This should give you enough information to calculate $k_e$ for each edge $e$. The total running time should be $O(n)$.

I'm leaving the rest of the details for you to ponder.


How to pick w for the Pumping lemma if the language has no clear pattern?

I think your confusion lies in the fact that the language is not given in more "structured" form. Even if the language is not given as such, you are free to choose any string from the language which is more "structured" and allows you to disprove that language is regular.

Take $w=C^{2N}A^{3N}$ (or $A^{3N}C^{2N}$) where $N$ is the pumping length and $w$ is a string in your language, and then follow the proof in similar lines as in  How to prove that a language is not regular?.

You should prove by yourself that above string $w$ can not be pumped.


Is every PSPACE-complete problem complete with respect to logspace reductions?

If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.

To see why, suppose for the purpose of contradiction that the definition of completeness remains unchanged when replacing polynomial time with logspace reductions, and simultaneously $\mathsf{P=PSPACE}$. Since $\mathsf{P=PSPACE}$, every nontrivial language in PSPACE is complete under polynomial time reductions, e.g. undirected connectivity which lies is $\mathsf{L}$. Seeing that we assumed that polynomial time completeneess is equivalent to logspace completeness, undirected conectivity is also PSPACE complete under logspace reductions, which implies $\mathsf{L=PSPACE}$, contradicting the space hierarchy theorem.

This question is probably still open (though I am unaware of any important/strange implications of the negation of your statement). You can find similar discussions about NP-completeness, where it appears the same question is also open.


Is there a path of length $k$ between given vertex to a subset of vertices in a connected directed graph

From the algorithm you describe and the comment you made on your question I understand that you are interested in walks and not in simple paths and that the graph is unweighted.

The algorithm you describe has at least exponential complexity since you examine each possible subset of $A$ (it has $2^{|A|} = O(2^N)$ subsets). We can use a much faster polynomial time algorithm.

One such algorithm has $O(k(N + M))$ computational complexity. You will need $k + 1$ boolean matrices, $B_0, B_1, \dots, B_k$, of size $N$. $B_0$ will be initialized to false, excluding its $s$-th position which will be initiallized to true. That is:

$B_0[u] = 1$, iff $u = s$

You will execute $k$ steps. In the $i$-th step you will calculate $B_i$ using the following formula:

$B_i[u] = 1$, iff $\exists v: (v, u) \in E \wedge B_{i - 1}[v] = 1$

This way $B_i[u]$ will be true iff there is a walk of length $i$ from $s$ to $u$. When you have calculated $B_k$ you can find the answer by checking $B_k$'s positions that match to $A$'s nodes' ids. Iff at least one of these array positions make $B_k$ true, then the answer is positive. The computational complexity of this algorithm is $O(k(N + M))$ and its space complexity is $O(kN)$. You can drop the space complexity to $O(N + M)$ if you observe that only the previous and the current boolean matrix $B_{i - 1}, B_i, \forall i \in \{1, 2, \dots, k\}$ are needed during each step. Bellow you can see a C++ implementation of this algorithm.

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Equal to maximum possible N + 5

vector<int> E[MAXN];  // Adjacency lists
vector<int> A;  // Nodes that belong in set A

bool PB[MAXN];  // boolean array of the previous step
bool B[MAXN];  // current boolean array

int main()
{
    int N, M, S_A, s, k;
    // N: number of nodes
    // M: number of directed edges
    // S_A: size of set A
    // s: starting node
    // k: length of walk to be done
    cin >> N >> M >> S_A >> s >> k;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);  // there is an edge from u to v
    }
    for (int i = 0; i < S_A; i++)
    {
        int a;
        cin >> a;
        A.push_back(a);  // a belongs to A
    }

    // Create B_0
    for (int i = 0; i < N; i++) B[i] = false;
    B[s] = true;

    // Perform the k repetitions
    for (int i = 1; i <= k; i++)
    {
        // Copy B (B_i) to PB (B_{i-1}) and initialize B
        for (int j = 0; j < N; j++)
        {
            PB[j] = B[j];
            B[j] = false;
        }
        for (int j = 0; j < N; j++) if (PB[j])
        {
            // There is a walk from s to j of length i-1...
            for (int l = 0; l < E[j].size(); l++)
            {
                // ...and an edge from j to E[j][l]...
                B[E[j][l]] = true;
                // ...so there is a walk of length i from s to E[j][l]
            }
        }
    }
    // Now B = B_k

    for (int i = 0; i < S_A; i++)
    {
        int a = A[i];
        if (B[a])
        {
            // There is a walk of length k from s to a
            cout << "YES\n";
            return(0);
        }
    }
    // There is no walk of length k from k to any node of A
    cout << "NO\n";
    return(0);
}

This algorithm is fast if $k$ is small but when $k$ becomes larger its computational complexity increases significantly. We will now describe an algorithm which is faster for large values of $k$.

You can use the fact that the $(i, j)$ cell of $Adj^p$ (where $Adj$ is the adjacency matrix of the graph) is equal to the number of walks from $i$ to $j$ in the graph with length equal to $p$ (easy to prove using mathematical induction). In your case you are interested in walks of length equal to $k$ so you have to calculate $Adj^k$. You can efficiently calculate $Adj^k$ in $\lceil log_2k \rceil$ steps using exponentiation by squaring. Each step of the above calculation requires squaring an $N \times N$ matrix. This can be done in $O(N^3)$ using the naive algorithm or in $O(N^{2.373})$ using the fastest known algorithm. The fact that you want to know if a path between two nodes exists and not the number of different paths allows you to avoid large numbers by making the integer matrix boolean after each multiplication. When you have $Adj^k$ (in boolean format) you can check if there is a path of length $k$ from $s$ to a vertex in $A$ by checking the $s$-th row of $Adj^k$ and specifically the columns regarding nodes of $A$. Formally the result is positive iff
$$\exists u \in A: Adj^k(s, u) = 1$$
The algorithm is the following:

Read input and calculate adjacency matrix of the graph: $O(N^2)$
Calculate $Adj^k$ using exponentiation by squaring, fast matrix multiplication and making matrix boolean after each multiplication: $O(N^{2.373}logk)$
Check if there exists a cell $Adj^k(s, u) = 1$ where $u \in A$: $O(N)$
Output the reslt: $O(1)$

The total computational complexity of this algorithm is $O(N^{2.373}logk)$ and it is better than the first algorithm for large values of $k$. Both of them also include possibility of self edges as you mention in your comment on your question.

You are able to combine the two algorithms and run the fastest one based on the values of the parameters and achive $O(\min \{k(N + M), N^{2.373}logk\})$ computational complexity.


This is answered on  Math.SE; see also  MathWorld .

Briefly,the $(i,j)$-th entry in $A^n$ gives the number of directed walks from vertex $i$ to $j$ that have length $n$. Also, given another adjacency matrix $B$, this entry in the product $(AB)$ gives the number of directed walks from vertex $i$ to $j$ , that walk first along an edge of the first graph and then along an edge of the second.Putting these two together would give you an interpretation to the product of 7th powers in your question.


EXPSPACE is not the most inclusive computational complexity class.  There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).

The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$.  If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE.  So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE.  And so on.  There is an infinite hierarchy of complexity classes, each bigger than the previous.

This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).


Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?

All variables are understood to be positive integers. Let $n\mid m$ mean $n$ is a factor of $m$, a.k.a. $m$ is divisible by $n$ or $m=0\pmod n$.

  Is it correct that if $\gcd(n, k)=1$, then $n\mid\binom nk$?

Yes.

Since $k\binom nk=n\binom{n-1}{k-1}$, we know $k\binom nk$ is divisible by $n$. Since $\gcd(n,k)=1$,  we must have $\binom nk$ is divisible by $n$.

  Is it correct that if $\gcd(n, k)>1$, then $\binom nk>0\pmod n$?

The relation of "greater than" or "less than" modulo $n$ does not make sense since, for example, $-1=1=2019\pmod 2$.

What you have in mind should be the following question.

  Is it correct that if $\gcd(n, k)>1$, then $n\not\mid\binom nk$?

Not necessarily.

The smallest counterexample is $\gcd(10,4)=2\neq1$ but $10\mid\binom{10}4=210$. In fact, if $n=2\pmod8$, then $n\mid\binom n4$.

Kummer's theorem provides a way to compute the exponent of the highest power of a given prime number dividing a binomial coefficient. Peter Taylor points out that it can be used to determine whether $n\mid\binom nk$ in polynomial time if we know the prime factorisation of $k$ or $n$. However, no algorithm is known to be able to obtain the prime factorisation of an integer in polynomial-time.

Here is a related interesting article, divisibility properties of binomial coefficients by K. R. Mclean.

Exercise 1. Show that if $m\mid n$ and $\gcd(m,k)=1$, then  $m\mid\binom nk$.

Exercise 2. Show that $2i\mid\binom{2i}4$ iff $i=1\pmod4$.

Exercise 3. Find infinitely many pairs of $n$ and $k$ such that $1\lt k \mid n$ and $n\mid\binom nk$. (Hint, one such family can be found by setting $k=6$.)


What is a compact way to represent a partition of a set?

You can use the way that the recurrence formula below is derived to find your encoding:
$$ B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k. $$
This is proved by considering how many other elements are in the part containing the element $n+1$. If there are $n-k$ of these, then we have $\binom{n}{n-k} = \binom{n}{k}$ choices for them, and $B_k$ choices for partitioning the rest.

Using this, we can give a recursive algorithm to convert any partition of $n+1$ to a number in the range $0,\ldots,B_{n+1}-1$. I assume you already have a way of converting a subset of size $k$ of $\{1,\ldots,n\}$ to a number in the range $0,\ldots,\binom{n}{k}-1$ (such an algorithm can be devised in the same way using Pascal's recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$).

Suppose that the part containing $n+1$ contains $k$ other elements. Find their code $C_1$. Compute a partition of $\{1,\ldots,n-k\}$ by "compressing" all the remaining elements to that range. Recursively compute its code $C_2$. The new code is $$C = \sum_{l=0}^{n-k-1} \binom{n}{l} B_l + C_1 B_{n-k} + C_2. $$

In the other direction, given a code $C$, find the unique $k$ such that
$$ \sum_{l=0}^{n-k-1} \binom{n}{l} B_l \leq C < \sum_{l=0}^{n-k} \binom{n}{l} B_l, $$
and define
$$ C' = C - \sum_{l=0}^{n-k-1} \binom{n}{l} B_l. $$
Since $0 \leq C' < \binom{n}{k} B_{n-k}$, it can be written as $C_1 B_{n-k} + C_2$, where $0 \leq C_2 < B_{n-k}$. Now $C_1$ codes the elements in the part containing $n+1$, and $C_2$ codes a partition of $\{1,\ldots,n-k\}$, which can be decoded recursively. To complete the decoding, you have to "uncompress" the latter partition so that it contains all the element not appearing in the part containing $n+1$.

Here is how to use the same technique to encode a subset $S$ of $\{1,\ldots,n\}$ of size $k$, recursively. If $k=0$ then the code is $0$, so suppose $k>0$. If $n \in S$ then let $C_1$ be a code of $S \setminus \{n\}$, as a subset of size $k-1$ of $\{1,\ldots,n-1\}$; the code of $S$ is $C_1$. If $n \notin S$ then let $C_1$ be a code of $S$, as a subset of size $k$ of $\{1,\ldots,n-1\}$; the code of $S$ is $C_1 + \binom{n-1}{k-1}$.

To decode a code $C$, there are two cases. If $C < \binom{n-1}{k-1}$ then decode a subset $S'$ of $\{1,\ldots,n-1\}$ of size $k-1$ whose code is $C$, and output $S' \cup \{n\}$. Otherwise, decode a subset $S'$ of $\{1,\ldots,n-1\}$ of size $k$ whose code is $C - \binom{n-1}{k-1}$, and output $S'$.


PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

You are asking two questions: how to construct a PDA for the language, and why this language is context-free while the same language with the condition $x \neq y$ replaced by the condition $x = y$, is not. I will only answer the second, since for the first question there are known algorithms.

The reason that your language is context-free is that we can rewrite it as follows:
$$
\{ \Sigma^i a \Sigma^i \Sigma^j b \Sigma^j : i,j \neq 0 \} \cup
\{ \Sigma^i b \Sigma^i \Sigma^j a \Sigma^j : i,j \neq 0 \}.
$$
This gives a different description of the language as the union of concatenations of context-free languages. A similar trick just doesn't work for the language $\{ xy : x=y \}$.

Here is a different example. Consider the following two collections of natural numbers (without zero):

$A = \{ x \cdot y : x \neq y \}$.
$B = \{ x \cdot y : x = y \}$.

The set $A$ consists of all natural numbers other than $1$, whereas the set $B$ consists of all squares. Even though we defined them in a similar way, the set $A$ has a much simpler description, while $B$ doesn't.


I use an ILP. I hope there are better solutions available.

Let H be your $n\times n$ happiness matrix. I use $n^2$ 0-1-variables $uv_{ij}$ per edge $uv$ in the seating graph. $uv_{ij}$ is 1 if person $i$ sits at place $u$ and person $j$ sits at place $v$.

maximize $\sum_{uv\in E} h_{ij} \cdot uv_{ij}$
s.t.
$\sum_{i,j} uv_{ij}=1$ for all $uv$, each edge gets exactly one neighbor configuration
$\sum_{j} ux_{ij} = \sum_{j} uy_{ij}$ for all edges $ux$ $uy$ that share an endpoint and all i, if $i$ sits at $u$ according to $ux$, they must also sit at $u$ according to $uy$


In the paper "Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances" by Farhan Ahammed and Pablo Moscato, the authors show how to build instances which causes Concorde to run in its worst-case time.

So, you may compare your solver with Concorde on instances generated that way, besides comparing on randomly generated instances and/or specific test-case instances.

Here is the paper's abstract:

  The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde [2], the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.


Matching two lists of different sizes with exceptions?

This is an instance of bipartite matching.  Build a graph where each left vertex represents one item from the larger list.  Duplicate each element in the smaller list the minimum number (e.g., if you want no item from the smaller list to appear more than twice, duplicate each item in the smaller list twice), then use one right vertex for each such (duplicated) item.  Draw an edge between items if they are not a forbidden pairing.  Then, use any standard algorithm (e.g., the Hungarian algorithm) to search for a perfect matching in this bipartite graph.


Check-digit algorithm that includes characters?

Check digit

If the check digit needs to be a digit (0-9), here is one solution:

You could take the SHA256 hash of the character string, modulo 10, and use that as your check digit.  The advantage is that this has good properties on average, and takes into account all characters.

Arguably, a possible disadvantage is that it is not guaranteed to detect all single-digit errors and all transpositions; those are only detected with probability 9/10.  (Some other checksum algorithms for digits achieve the latter guarantee, but they don't work with alphabet characters.  Moreover, there is no hope or possibility of achieving both of those guarantees when you have to deal with alphabetic characters: it's not possible to guarantee detection of either kind of error when you have alphabetic characters and a check digit that is restricted to 0-9.)   Therefore, I'm not sure it is possible to do much better than this.

Check character

If the check digit can be anything from the character set, here is an alternative solution:

Suppose there are $n$ characters, so each character can be thought of as a number in the range $0,1,2,\dots,n-1$.  Let the characters in the string be $x_1,x_2,\dots,x_k$.  Then you can use the following as the check sum:

$$x_1 + 2x_2 + 3x_3 + \dots + kx_k \bmod n.$$

If $n$ is prime, this has the following nice guarantee: any one-character error will be detected (e.g., cooking -> cooling), and any transposition of two characters will be detected (e.g., weird -> wierd) (unless the transposed characters are a multiple of $n$ positions apart).

If $n$ is not prime, you get weaker properties, but it's still a reasonable checksum.

Alternatively, you can use the SHA256 hash of the character string, modulo $n$, as the check sum.  That has no guarantees but is good on average.


Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?

Actually this language is not a CFL.

And here is a proof:

Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs.

Then $a^{m+k_1}b^{2^m+k_2} \in L$ where $1\le k_1,k_2<m$

(cases invloving either $k_1 = 0$ or $k_2=0$ are easier.)

Now, that suggests that,

$2^{m+k_1} = 2^m + k_2$ (by defination of $L$)

$\therefore 2^m2^{k_1} = 2^m + k_2$   ....................................(1)

now, $k_1 \ge 1\implies 2^m2^{k_1} \ge 2^m + 2^m > 2^m + k_2.$

(because we have $k_1 \ge 1$ this means left side of equation $1$ will always have value $\ge 2.2^m$ but right side of equation can have maximum value of $2^m + m - 1$)

Hence this language can't be CFL.


Complexity of finding a spanning tree that minimizes the maximum interference

This problem already is known, and is NP-Hard, but if you like to know more about the interference related problems I'd offer you to read this book.

The Problem 1, in the Buchin work is as follow:

  Problem 1 (Locher, von Rickenbach, Wattenhofer[5]). Given n nodes in
  the plane. Connect the nodes by a spanning tree. For each node v we
  construct a disk centering at v with radius equal to the distance to
  v's furthest neighbor in the spanning tree. The interference of a node
  v is then defined as the number of disks that include node v (not
  counting the disk of v itself ). Find a spanning tree that minimizes
  the maximum interference.


The notation is as follows: FROM[left bit : right bit], so in your example PC[15:9] means take bitfield (number) from PC from fifteenth bit to ninth bit, inclusive, so 15 - 9 + 1 = 7 bits.
The same applies for IR[8:0] meaning take bitfield from IR from eight to zeroth bit inclusive.
For example PC[14:14] would be exactly one bit long and in such case by convention one would write PC[14].


Why is the video game Braid Turing-complete?

Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard.

Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing machine, and thus determining if any general Braid level is solvable is similar to solving the halting problem, which is undecidable.


Data Compression: Which one is Better "Compress before Encrypt" or "Encrypt before Compression"

Compressing encrypted data doesn't work.  Encrypted data looks pseudorandom, therefore if you try to compress it, you'll find that the compression is ineffective.

Try it.  You'll see.  It's a very simple experiment -- give it a try.


Proof of correctness for a triangulation-algorithm

I am here again :)
I prove it by induction as you already did. But instead of assuming that the new point is in the lower/upper hull, I assume that the point is the rightmost one (a stronger condition), so it will belong to both, lower and upper hull.
Applying euler formula we know that the total amount of triangles in a valid triangulation is $2\cdot n − h − 2$. Where $n$ is the amount of points and $h$ is the amount of points in the convex hull.
I change a bit the algorithm I proposed you before. Instead of making one sweep from left to right to build the upper hull and one from right to left to build the lower hull, lets build the lower hull with a sweep from left to right too, but this time changing the counter-clockwise condition for clockwise.
Applying the above algorithm to build the triangulation with this slightly new approach will lead you to the same solution. Let's work again on the induction, but this time assuming the new point is the rightmost one and prove the euler condition holds.

Assertion: The said algorithm always returns a triangulation for a given point set.
The assertion is clear for a set of three points, so we got our induction start.
Now lets suppose the assertion holds for all sets with at most n points.
The total number of triangles is $2n - h - 2$
When you add a point in the rightmost position the amount of points will be $n_1=n+1$ and the amount of points in the convex hull will be $h_1 = h + 2 - t$ where $t$ is the total number of added triangles. The total number of triangles we are expecting is:
$$2 \cdot n_1 - h_1 - 2 = 2 \cdot (n + 1) - (h + 2 - t) - 2$$
$$ =(2 \cdot n - h - 2) + t $$
Then the number of triangles that we have built in this last step is $t$ which implies that we have all triangles we need in the solution. Check the picture to get an intuitive idea about what is happening.

I have coded this solution in Codeforces problem, but I can't find it right now :(


Regular Expressions with at least 2 0's and at most 1

Your answer is correct. You can obtain a slightly shorter expression by deleting two of the $\epsilon$ in your expression. Indeed
\begin{align}
(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon) &= (1+ \epsilon)000^* + 0^*0100^* + 000^*1 \\
&= 1000^* + 0^*0(1+\epsilon)00^* + 000^*1\\
&=1000^* + 0^*0100^* + 000^*(1+\epsilon)
\end{align}
Finally, if you want to avoid $\epsilon$, you could use one of the expressions
$$
000^* + 1000^* + 0^*0100^* + 000^*1 \quad \text{or} \quad 0^*(00 + 100 + 010 + 001)0^*
$$
which might be easier to read.


In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity?

The "multiplicative constant" is quite a bit more complex, the real average time for e.g. quicksort is $a n \log n + b \log n + c n + d$ for some constants that depend on the exact cost of comparisons (and thus the layout of the elements), memory access (again, data layout related), machine architecture, how smart the compiler is, ...

To get real average time, you need to know the distribution of possible inputs. Most analysis is done assuming all possible inputs are equally likely, but some experiments have shown that sorted (or almost sorted) data is very likely. In that case, it turns out lowly insertion sort beats all, at $O(n)$.

Do you worry about worst time? Sorry, you can't grab the on average fastest quicksort, and have to fall back on much, much slower heapsort or mergesort variants.

If you want a complete answer to your question, go check Knuth's "The Art of Computer Programming", volume 3 (Sorting and Searching). Some 800 pages of heavy going math for your enjoyment.


Given a sorted dictionary of words, find order of precedence of letters

Let's denote the words by $w[1],\ldots,w[n]$. Suppose that $i < j$ and that $w[i],w[j]$ first differ on the $t$th coordinate. In symbols, $w[i]_{<t} = w[j]_{<t}$ but $w[i]_t < w[j]_t$ (I hope the notation is obvious).

I first claim that $w[k]_{<t} = w[k+1]_{<t}$ for all $k \in \{i,\ldots,j-1\}$. Indeed, suppose that $w[k]_{<t} < w[k+1]_{<t}$ for some $k \in \{i,\ldots,j-1\}$. Then $w[i]_{<t} \leq w[k]_{<t} < w[k+1]_{<t} \leq w[j]_{<t}$, contradicting the assumption $w[i]_{<t} = w[j]_{<t}$.

Call an index $k \in \{i,\ldots,j-1\}$ special if $w[k]_t < w[k+1]_t$. Let the special indices be $k_1,\ldots,k_m$. Then
$$
w[i]_t = w[k_1]_t < w[k_1+1]_t = w[k_2]_t < w[k_2+1]_t \cdots w[k_m]_t < w[k_m+1]_t = w[j]_t.
$$
This shows that $w[i]_t < w[j]_t$ follows from $w[k_1]_t < w[k_1+1]_t,\ldots,w[k_m]_t < w[k_m+1]_t$ by transitivity. (Here we are using the fact, proved earlier, that $w[k_r]_{<t} = w[k_r+1]_{<t}$ for $r \in \{1,\ldots,t\}$.)


efficient algorithms for factoring polynomials

Do you know of Berlekamp's algorithm and the  Cantor–Zassenhaus algorithm?

http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm

http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm

Unless I'm misunderstanding your question, there is no field of integers- they form a ring but don't have multiplicative inverses


Understanding an example of coin toss expectation maximization

From mcdowella's answer to IcySnow's question Expectation Maximization coin toss examples, Michael Collins' EM Algorithm (pdf) paper presets the "Three Coins Example" in section 3.1 (pdf page 8-9) and explains the steps for recalculating the parameters $\lambda, p_1, p_2$ in accordance with the EM Algorithm.

The derivation is too lengthy to type up here, but to summarize, you'll formulate the conditional expectation in terms of the previous iteration of parameter values and then differentiate the expectation with respect to each parameter from the previous iteration then perform algebra to obtain the maximum after setting the derivative to zero.


Theoretical computer science means different things to different people. However, here are some areas which are commonly taught in undergraduate theoretical computer science classes:

Combinatorics and elementary set theory. This serves as prerequisite to all that follows.
Data structures and algorithms. One standard textbook is Introduction to algorithms, but it might be too advanced if you're just starting out.
Computability and automata theory. One standard textbook is Introduction to the theory of computation by Michael Sipser.

In some places, another core subject is functional programming and labmda calculus.

An undergraduate degree in computer science typically deals with several other topics, such as operating systems, networking, and sometimes compilation.


In other words, you are given a directed graph, and you want to know:

Whether there are any directed cycles, i.e., whether your graph is a DAG.
Assuming there are no directed cycles, whether the corresponding partial order is a linear order.

As KWillets comments, this is just topological ordering. In your case, to find whether your digraph is a DAG supporting a unique topological ordering, try the following algorithm:

Verify that there is a unique source (a node with no incoming edges).
Remove the unique source, and repeat.

This succeeds iff your digraph is a DAG which has a unique topological ordering.


A data structure that makes finding close objects easy

Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees.

It might also be possible to apply ideas from sweep-line algorithms, sweeping outwards radially from the current position of the robot.


The trick in converting from hexadecimal (base 16) to octal (base 8) is using a (perhaps imaginary) binary (base 2) intermediate. To demonstrate this, let's convert from base 10000 to base 1000, where the intermediate would be decimal (base 10). Consider this number, whose digits are separated by a space:

  3 1415 9265 3589 7932 3846

The corresponding number in base 1000 is

  314 159 265 358 979 323 846

This example is not completely academic. In some situations one converts between base 1000, used in many European languages, and base 10000, used in Chinese.


Time Complexity of the Kruskal Algorithm after sorting

Almost linear in term of the number of edges of the graph.

More specifically, here is the quote from Wikipedia entry on Kruskal's algorithm.

  Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in $O(E \,\alpha(V))$ time, where α is the extremely slowly growing inverse of the single-valued Ackermann function.

Here $E$ stands for the number of edges in the graph and $V$ stands for the number of vertices in the graph. In fact, $\alpha(n)$ is less than 5 for any practical input size $n$, since  $\alpha$ is the inverse of the growing function $f$ and $f(1)=3$, $f(2)=7$,$f(3)=61$, $f(4)=2^{2^{2^{2^{16}}}}-3$, a number whose number of digits is a number whose number of digits is 19727 (all fractional parts ignored). In other words, even if $n$ has trillions of trillions of digits, $\alpha(n)$ is still 4.

Please note in computer science, this factor $a(V)$, however slowly grows, represents a real barrier to achieve a linear algorithm even after the edges have been sorted by weight.


The idea is to build a graph with only the edges that are candidates for the shortest path from $v$ to $u$ assuming that $f$ is the required solution.

If during the process we find an edge that lead to a shorter path then we return false.

Otherwise, at the end, we check that all the nodes are still connected (with a DFS) hence that there exists a path with the required weight.

  if $f(v)\neq 0$ then return false

  $\forall e=(v_1,v_2)\in E $ do

  if $f(v_2) > f(v_1)+w(e)$ then return false

  if $f(v_2) < f(v_1)+w(e)$ then remove $e$ from $E$

  done

  build $cV$ the set of reachable vertices in the new graph (with a DFS)

  return $V=cV$

Correction:
- if there exists $u\in V$ such that $f(u)>\delta(v,u)$ then there exists $e=(v_1,v_2)\in E$ such that $f(v_2) > f(v_1)+w(e)$. Let $e_1,...,e_n$ be the shortest path from $v$ to $u$ if $f(v_{i+1}) \leq f(v_i)+w(e_i)$ then $f(u)\leq \delta(v,u)$ contradiction.

Hence the algorithm return false.

otherwise if there exists $u\in V$ such that $f(u)<\delta(v,u)$ then $u$ is disconnected from $v$ in the resulting graph.
Hence the algorithm return false. $u$ is connected, hence there exist a path $e_1,...,e_n$ from $v$ to $u$ such that $f(v_{i+1}) = f(v_i)+w(e_i)$ hence $f(u)\geq \delta(v,u)$ contradiction.
otherwise if for all $u\in V$ $f(u)=\delta(v,u)$ then all the edges belonging to the shortest path verify $f(v_{i+1}) = f(v_i)+w(e_i)$ hence are still in the graph at the end hence all the vertices are still connected. Also there are no edges such that $f(v_2) > f(v_1)+w(e)$ otherwise $f(v_2)>\delta(v,v_2)$.

Complexity:

$O(|E|)$ to build the new graph plus $O(|E|)$ for the DFS plus $O(|V|)$ for set equality hence $O(|V|+|E|)$.


Can you define what it means to solve a problem "only" with recursion?

Would your definition allow an algorithm like this:

int foo(int n) {
    if (n==1) return 1;
    while(someCondition) {
        do something
        foo(n-1);
    }
}

If your definition would wllow this, then it would be easy to transform every algorithm in such a recursive form (you could do all your calculations in the outermost function call and do nothing in the recursive calls).


Dijkstra's algorithm - Finding additional paths with same weight but different edges

One way to proceed may be to store for each node a list of parents so $parents[v_i]$ becomes an array of lists. There is also the same array of distance from $s$, $d[v_i]$ initially infinite for all $v_i$ but $s$ ($d[s] = 0$).

So like standard version of Dijkstra's algorithm, you maintaint a priority queue $q$ (sorted by $d$). When $v_i$ is depiled from the queue you explored all the nodes $v_j$ reached from $v_i$, in the standard version of the algorithm, there was 2 cases:

a smallest path to $v_j$ has been found: $d[v_j]$ and $parents[v_j]$ are updated and $v_j$ is added to the queue.
the new path is not better, do nothing.

So now, if the path is smallest, $parents[v_j]$ is replaced by the list with one element $[v_i]$.

And there is an additional case: if path to $v_j$ is exactly the same in distance, append $v_i$ to $parents[v_j]$. Note that there is no need to put $v_j$ again in the queue.

Once you reach $t$ and you backtrack path using $parents[v_i]$, if there are several elements in the list, any may be picked and lead to a different shortest path.

Note that $parents[v_i]$ is $O(N^2)$ in space. The worst cases are very dense graphs,  and this would mean that there is a large number of shortest paths. In this case, other method to store $parents[v_i]$ may be more adapted.


How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Let $M(m, n)$ and $D(m, n)$, respectively, be the costs of multiplying and dividing an $m$-digit number by an $n$-digit number (with $m \ge n$). Brent and Zimmermann give the following bounds:

$$ (1) \qquad M(m,n) \le \left\lceil \frac{m}{n} \right\rceil  M(n) $$
  $$ (2) \qquad M(m,n) \le M \left( \frac{m+n}{2} \right) (1+ o(1)) $$
  $$ (3) \qquad D(m+n,n) \le O(M(m,n)) $$
where $M(n)$ is the complexity of balanced $n$-digit multiplication.

I am not an expert in this area but I can try to summarize their explanations:

(1) is based on the idea that if $m = kn$, you can cut the larger operand into $k$ pieces, giving $M(kn, n) = k M(n) + O(kn)$.

(2) is based on using an evaluation-interpolation scheme and reducing the unbalanced multiplication to a balanced multiplication of two $(m+n)/2$-digit numbers (I realize this is a bit vague, but they don't give much details in this case).

(3) they also don't give a reference in this case; judging from the bound, it may be based on using Newton to compute the reciprocal of the $n$-digit number and then multiplication. One unbalanced division algorithm they do discuss explicitly is based on computing $n$ digits of the quotient at a time, reducing the division to several $2n$ by $n$ divisions, each of which is implemented with the recursive division algorithm. However, the latter does not seem to fit the bound (3).

For the details, have a look at Sections 1.3.5, 1.4.3, and the table at the end of their monograph.


Consider the problem
$$A^f =
A_{TM}^f =
\{\langle M,x,t \rangle \mid
M\in DTM \text{ and }
M(x) \text{ halts and accepts in } f(|t|) \text{ steps}\}.$$

Now
$L^{\exp}$ is complete for $\mathsf{EXP} = \mathsf{DTime}(\exp (n^{O(1)}))$ and
$L^{\exp\exp}$ is complete for $\mathsf{2EXP} =\mathsf{DTime}(\exp\exp(n^{O(1)}))$.

We show that $L^{\exp \exp}$ is in $\mathsf{EXP}^\mathsf{EXP}$.

Given $\langle M,x,t \rangle$,
we simply write $\langle M,x,1^{\exp(|t|)} \rangle$ on the query tape and
ask it from $L^{\exp}$ and return its answer as output.

This algorithm is in $\mathsf{EXP}^\mathsf{EXP}$, therefore $\mathsf{2EXP} \subseteq \mathsf{EXP}^\mathsf{EXP}$.


Combinatorial optimization problem - What would you call this?

It's called four-dimensional matching and it's NP-complete.


Hardness

Your problem might be called "maximum minimal set cover".  In particular, your problem feels like it might be related to minimum maximal matching, which is NP-hard.  If you wanted to try to prove NP-hardness, you might try to see if you can find a reduction from minimum maximal matching.

Algorithms

Your problem can be expressed as an instance of SAT, and then you could apply an off-the-shelf SAT solver.  In particular, we formulate the decision problem variant, where we are given $F$ and an integer $k$, and we ask whether there exists a maximal cover $E$ such that $|E|=k$.   To express this decision problem in SAT, we introduce constraints to capture two different aspects of the problem:

The requirement that $E$ be a cover of size $k$:  We introduce boolean variables $x_f$ (one for each $f \in F$), with the intent that $E=\{f \in F : x_f = \text{true}\}$.  It is easy to write down boolean constraints on the $x_f$'s to express the requirement that $E$ be a cover (i.e., for each $u \in U$, you have a clause $\lor_{u \in f} \; x_f$) and that $|E|=k$ (see this answer for several ways to express the latter in SAT).
The requirement that no subset of $E$ be a cover: We introduce the boolean variables $y_g$ (one for each $g \in F$), with the intent that $y_g$ is true if and only $E\setminus\{g\}$ is a cover.    It is straightforward to write down boolean constraints to ensure that each $y_g$ has the appropriate value (i.e., $y_g = \land_{u \in U} \lor_{u \in f, f \ne g} \; x_f$; now apply the Tseitin transform).  Then, we can add the clause $\neg x_g \lor \neg y_g$ for each $g \in F$.

Now there exists a maximal cover $E$ of size $k$ if and only if there is some satisfying assignment for this SAT instance.  So, run an off-the-shelf SAT solver on this, and do binary search over $k$ to find the largest such cover, and you are done.

Alternatively, you can express your problem as an instance of integer linear programming, and then apply an off-the-shelf ILP solver.  This might provide reasonable approximations to the optimum in practice, as many ILP solvers have heuristics to try to find an approximate optimum (i.e., a valuation to the variables that makes the objective function as large as they're able to).

One approach to formulate this as an ILP instance is similar to that for SAT:

The requirement that $E$ be a cover of size $k$: We introduce an integer variable $k$.  Also, we introduce integer variables $x_f$ (one for each $f \in F$) that are constrained to be zero or one.  Zero plays the role of false, one the role of true.  Thus, the intent is that $E=\{f \in F : x_f=1\}$.  It is easy to write down linear constraints to express the requirement that $E$ be a cover (i.e., for each $u \in U$, we have the inequality $\sum_{u \in f} x_f \ge 1$) and that $E$ have size $k$ (i.e., $\sum_f x_f = k$).
The requirement that no subset of $E$ be a cover: We introduce linear constraints to express the requirement that if $x_f=1$, then $E\setminus \{g\}$ is not a cover, for all $g \in F$.  This can be done using the methods described here: Express boolean logic operations in zero-one integer linear programming (ILP).

In particular, here's what it looks like.  Introduce zero-or-one integer variables $y_{g,u}$ for each $g \in F$ and each $u \in U$, where $y_{g,u}=1$ is intended to represent that $E \setminus \{g\}$ does not cover $u$.  In particular, for each $u \in U$ and each $g \in F$, add the inequality

$$\sum_{u \in f,f \ne g} x_f \le K - K y_{g,u},$$

where $K$ is a sufficiently large constant ($K=|U|$ will suffice).

Also, for each $g \in F$, add the inequality

$$\sum_{u \in U} y_{g,u} \ge 1.$$

This ensures that, for each $g \in F$, $E\setminus\{g\}$ is not a cover (since there exists $u \in U$ such that $E\setminus\{g\}$ does not cover $u$).
Maximize $k$: You want to maximize $k$.  So, your integer linear program is: maximize $k$, subject to the linear inequalities mentioned above.

Now you can apply an off-the-shelf ILP solver to this ILP instance.


Given a minimum vertex cover can we find all the others in polynomial time?

Just complementing on D.W.'s already correct answer.

Take a collection of disjoint copies of triangles.  This has $2^{n/3}$ many vertex covers.  If you add a universal vertex (a vertex connected to every other vertex), the graph obviously becomes connected.

Now, this universal vertex is always going to be in any minimum vertex cover.  However, for the rest of the graph (the original triangles), you still need to cover all the edges.  There are of course $2^{n/3}$ ways of choosing vertices to the vertex cover.

However, there is a well-known algorithm which enumerates every minimal vertex cover with polynomial delay, meaning that it takes polynomial time between every output.  This means that in graphs with few vertex covers, you can do this relatively quickly.

For your second question, the simplest is probably the $2^k n^2$ algorithm where $k$ is the size of the optimal vertex cover.  You branch on edges, deleting the vertex you chose to the vertex cover, and when you have an edgeless graph, you output the set of vertices you deleted.


How can you define the notion of "state" using only a type theory language?

I am not sure what your question exactly covers. But to have a more formal definition of "State" it could be useful to look at the State Monad in Haskell. Haskell is a functional programming language which operates different compared to a imperative programming language (like Java or C).


Is undecidable(complement of R) a subset of NP-hard?

If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ is a set and $f_i$ reduces SAT to $A$ in polytime, then $f_i$ must have infinite range. Otherwise, we can hardcode the relevant values of $f_i$ to get a polytime algorithm for SAT.

We can construct an undecidable problem which is not NP-hard using diagonalization. Let $f_i$ be an enumeration of all polytime reductions whose range is infinite. We construct an undecidable problem $A$ such that no $f_i$ reduces SAT to $A$. We will use $K$ to denote the undecidable set corresponding to the halting problem.

The set $A$ will be defined in stages, starting with a completely undefined set. In stage $i$, we find a string $s$ such that $f_i(s)$ is longer than any string on which $A$ is defined (here we use the fact that the range of $f_i$ is infinite). We define $A$ on $f_i(s)$ so that $s \in SAT$ iff $f_i(s) \notin A$. After all finite stages, we complete the definition of $A$ for each undefined string $s$ by letting $s \in A$ iff $|s| \in K$.

By construction, no polytime $f_i$ reduces SAT to $A$, and so $A$ is not NP-hard. On the other hand, $A$ is not decidable since $K$ reduces to $A$: we can decide whether $n \in K$ (for $n \geq 2$) by taking a majority of three strings of length $n$.