Algorithms - Solving recurrence-relations/Bounds?

First of all, a recurrence is not necessarily about the running time of anything. So you don't figure out "the running time", you solve the recurrence.

Second, your recurrence only possibly makes sense for powers of 2, and even then, it needs a base case. I'll assume that $T(1) = C$.

You can use the master theorem to solve your recurrence, but you can also do it directly. First you expand it (for simplicity, I'm assuming the base of the logarithm is 2):
$$
\begin{align*}
T(2^k) &= k + 2T(2^{k-1}) \\ &=
k + 2(k-1) + 4T(2^{k-2}) \\ &=
k + 2(k-1) + 4(k-2) + \cdots + 2^{k-1}(k-(k-1)) + 2^k T(1) \\ &=
(1+2+\cdots+2^{k-1})+(1+2+\cdots+2^{k-2})+\cdots+(1) + 2^k C \\ &=
(2^k-1)+(2^{k-1}-1)+\cdots+(2-1)+(1-1) + 2^kC \\ &=
(2^k+\cdots+1)-(k+1) + 2^kC \\ &=
2^{k+1}-k-2 + 2^kC.
\end{align*}
$$
If you want to be very pedantic, you can prove this by induction. In terms of $n=2^k$, this reads
$$
T(n) = (2+C)n-\log n - 2 \sim (2+C) n.
$$
In particular, $T(n) = \Theta(n)$. You could also get this conclusion from case 1 of the master theorem.


Hamming distance required for error detection and correction

The Hamming distance being 3 means that any two code words must differ in at least three bits. Suppose that 10111 and 10000 are codewords and you receive 10110. If you assume that only one bit has been corrupted, you conclude that the word you received must have been a corruption of 10111: hence, you can correct a one-bit error. However, if you assume that one or two bits could have been corrupted, you don't know if 10110 should be 10111 (one 1 got turned into a 0) or 10000 (two 0s got turned into 1s). You can correct one-bit errors (if you assume that those are the only kind that occur) but you can't tell the difference between a one-bit error from one codeword and a two-bit error from another, so you can't deal with two-bit errors at all. If a two-bit error occurs, you'll detect that some error occurred, but you'll assume it was a one-bit error from a different codeword and "correct" it wrongly.

In contrast, with the distance-4 code illustrated in the fourth diagram, you can detect two-bit errors.  If you receive the word in the middle, you can tell that (at least) two bits got corrupted but you can't tell whether you were supposed to see the blue codeword on the left or the one on the right.


Datastructure for insertion and scored extraction

You can use left threaded AVL trees with score as key and hash (expected $\mathcal O(1)$ insert/delete or simple AVL, logarithmic but with value much smaller than $n$) as values to keep id's, and all the time keep the data sorted with $\mathcal O(1)$ inorder traversal and $\mathcal O(\log n)$ insert (which in case of your increment operation is one delete, one insert). Also you might want to keep the last result (which is sorted) to check whether some new id appeared and use binary search if it did.

Overall this gives $\mathcal O(m)$ extract (which cannot be better) and two $\mathcal O(\log n)$ operations per increment.


I can't comment about the programming language aspect, but here is the logical aspect. A sequent is an expression of the form
$$ A_1,\ldots,A_n \vdash B_1,\ldots,B_m $$
whose meaning is "if $A_1,\ldots,A_n$ hold then one of $B_1,\ldots,B_m$ holds", that is
$$ (A_1 \land \cdots \land A_n) \to (B_1 \lor \cdots \lor B_m). $$
Sequent calculus is nice since its laws enjoy a certain symmetry between the two sides that reflects the de Morgan symmetry between AND and OR.

Weakening is the law that states that you can a formula to either side of a sequent. That is, if a sequent $\Gamma \vdash \Delta$ is true (where $\Gamma,\Delta$ are sequences of propositions), then for every formula $X$, both sequents $\Gamma,X \vdash \Delta$ and $\Gamma \vdash \Delta,X$ also hold.

Contraction states that if a formula appears twice one of the sides, then an equivalent sequent is obtained by removing the duplicate. That is, if $\Gamma,X,X \vdash \Delta$ then also $\Gamma,X \vdash \Delta$, and similarly for duplicates on the other side.

One more structural rule, permutation, allows us to reorder formulas: if $\Gamma,X,Y,\Delta \vdash E$ then also $\Gamma,Y,X,\Delta \vdash E$, and the same for the other side.


Why is deep learning hyped despite bad VC dimension?

"If the map and the terrain disagree, trust the terrain."
It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC dimensions appear not to be very helpful.
The matter is hotly debated, see e.g.:

H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well?
C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning Requires Rethinking Generalization.
D. Krueger, B. Ballas, S. Jastrzebski, D. Arpit, M. S. Kanwal, T. Maharaj, E. Bengio, A. Fischer, A. Courville, Deep Nets Dont Learn Via Memorization.

Regarding the issue of adversarial examples, the problem was discovered in:

C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Going deeper with convolutions.

It is further developed in:

I. Goodfellow, J. Shlens, C. Szegedy, Explaining And Harnessing Adversarial Examples.

There is a lot of follow-on work.
Update March 2020. A new hypothesis that appears to explain some of the mismatch between clear over-parameterisation of modern (feed-forward) NNs and good recognition performance is Frankle and Carbin's Lottery Ticket Hypothesis from 2018:

J. Frankle, M. Carbin, The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.

The claim is that a "randomly-initialised, dense [feed-forward] neural
network contains a subnetwork that is initialised such that when
trained in isolation it can match the test accuracy of the original
network after training for at most the same number of iterations." Regarding the original question, the Lottery Ticket Hypothesis might be understood as saying that:

Training by stochastic gradient descent searches for small subnetworks that work well and deemphasises the rest of the overparameterised network's learning capacity.

The bigger the original network, the more likely it is to contain a small subnetwork with good performance on the task at hand.

This has found empirical support, e.g. in

H. Zhou, J. Lan, R. Liu, J. Yosinski, Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask.

and theoretical support in:

E. Malach, G. Yehudai, S. Shalev-Shwartz, O. Shamir, Proving the Lottery Ticket Hypothesis: Pruning is All You Need.

As far as I'm aware, it has not yet been possible to generalise the Lottery Ticket Hypothesis to recurrent NNs.
Update March 2021. The original 2016 paper Understanding Deep Learning Requires Rethinking Generalization has been updated. Here is the new version:
C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning (Still) Requires Rethinking Generalization.


What is an example of a decidable language?

No.

As an example of a language that is decidable but does not have a context-free grammar is the language over the decimal digits that only contains the prime numbers.


Is there a difference between the name scheduler and scheduling?

This is more a question of English than computer science. For almost any regular verb (and "schedule" is a perfect example), the [verb]er is the thing that does the [verb]ing. The scheduler is the software that schedules.


Show that a Language can be Generated by a regular grammar

The only thing that prevents your grammar from being a regular grammar is that $x$ is a string rather than a single terminal. That means that you have to deal with two kinds of problems:

$x$ is a string containing more than one terminal.
$x$ is the empty string.

To deal with the first problem, replace each problematic rule by a chain of equivalent rules of the proper form. For example, $A \to \alpha \beta$ is the same as $A \to \alpha X$ and $X \to \beta$.

To deal with the second problem, you have to get rid of rules of the form $A\to B$ and of rules of the form $A \to \epsilon$. Hopefully this is something you already know how to do. If not, notice that $A \to B$ means that whenever you have $A$, you can replace it with $B$, and $A \to \epsilon$ means that whenever you have $A$, you can remove it. Doing so recursively will allow you to get rid of these rules.


If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

B being NP-hard does not say anything about A. The problem says that there is a way to reduce A to B in polynomial time.
But on the other hand, it is also not given that A getting reduced to B is the only pathway for solving A. So, there can be other ways of solving A in polynomial time.
Hence, the implication that A is NP-hard is false.


Mapping graph to another graph's sub-graph

This is the induced subgraph isomorphism problem, which was one of the problems proven NP-complete in Cook's original paper on NP-completeness.  For a quick way to see that it's NP-complete, you can let $G$ be a complete graph on $k$ vertices to solve CLIQUE on $G'$. Unless you can restrict the form of $G$ and/or $G'$, you're probably out of luck in your quest for a good algorithm.

The problem seems to be easier if you insist that $G$ and $G'$ have the same number of vertices. In this case, you have the graph isomorphism problem. This is generally thought not to be NP-complete and, in December 2015, Babai announced an subexponential-time algorithm, which runs in time $\exp\exp(\tilde{O}(\sqrt{\log n}))$, where $\tilde{O}$ denotes hidden factors of $O(\log\log n)$.
This is faster than $O(\mathrm{e}^{n^\epsilon})$ for all $\epsilon>0$. (The algorithm was originally announced as having quasipolynomial running time but an error in the analysis came to light in January 2017.)


Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)?

We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG simulation for short).

The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2).
Therefore, the BG simulation transforms an algorithm A solving consensus among 2 processors using (3,2) into an algorithm B solving consensus among 3 processors using registers only.
Since the latter is impossible, there is no such algorithm A.

Note that by solving I mean solving wait-free.

This proof first appeared in Borowsky and Gafni, "Generalized FLP impossibility result for t-resilient asynchronous computations." Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993. (In particular see the end of section 3.3).


Why is the run time with a loop of this structure considered O(log n)

Assuming the model of computation is RAM(Random Access Machine). Which means the cost of addition, multiplication,division etc is constant. Now your program is

int j = 0;
for (int i = 1; i <= n; i *= 2) {
    j = j + n * 2;
}

Inside the loop, you are doing addition, multiplication, comparison etc which takes constant time. Let $k$ denotes the number of iterations of the loop. Let $c_i$ denotes the cost at $i$th iteration of loop.
The total cost is

$$ = c_1+c_2+\ldots + c_{k}$$
$$ = \sum_{ j =1 \text{ to } k}c_i$$

It is easy to see that above summation gives $\mathcal{O}(\log n)$.


Common method for solving satisfiability problems which lie in P

Schaefer's dichotomy theorem is proved by dividing CSPs into two types: those that can be reduced to one of a few specific problems in P, and the other to which SAT can be reduced (and so are NP-complete). Specifically, every CSP of the former type is either trivial (always satisfied by the constant 0 or the constant 1 assignment), can be reduced to 2SAT, can be reduced to HORN-SAT, or can be reduced to XOR-SAT. These are the only algorithms you need to solve these CSPs. There is no one single algorithm – there is a finite list of algorithms.


What does it mean for a function to be decidable? (homework)

They are not asking to prove that the function $g$ is decidable, but the image $g(\mathbb{N})$ is decidable. The image is a subset of $\mathbb{N}$, namely
$$g(\mathbb{N}) = \{ k \in \mathbb{N} \mid \exists n \in \mathbb{N} . g(n) = k \}.$$
The question reduces to showing decidability of "given $k$, does there exist $n \in \mathbb{N}$ such that $g(n) = k$?".


When computing the oracle in Grover's algorithm, you prepare a qubit entangled with the search register such that the qubit is ON in the parts of the superposition where the search register contains a satisfying solution and OFF in the other parts of the superposition. This is not hard to do: you just use any old circuit that would determine if a given input was a solution, and apply that to the search register.

By preparing the solution qubit, applying a Z gate to it, then uncomputing the solution qubit, you negate the parts of the superposition corresponding to solutions. Having that qubit available is not the same thing as finding a solution. For example, if you measured it you'd almost always get an OFF result and find that your search register contained a non-solution. But, by using the prepared qubit as a tool to negate the phase of the solution space, Grover's algorithm can set up a gradual rotation towards the solution space.

More information: http://algassert.com/post/1719


Incentive for block creation in a private blockchain

The blockchain would no longer be completely decentralized.  You would have a dictator, or a central authority that decides which transactions get processed and which do not.

At this point you could just as well skip the blockchain part of the transaction system as well.


How to derive dependently typed eliminators?

The canonical reference for this is Peter Dybjer, Inductive Families, which gives a pretty comprehensive treatment of inductive families based on eliminators.


Average Case Running Time of Quicksort Algorithm

The average case running time of quicksort satisfies the recurrence
$$
T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n),
$$
with base case $T(0) = \Theta(1)$.

In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order of summation, we get
$$
T(n) = \frac{2}{n} \sum_{i=0}^{n-1} T(i) + n + 1,
$$
and so
$$
nT(n) = 2\sum_{i=0}^{n-1} T(i) + n(n+1).
$$
This implies that
$$
(n+1)T(n+1) - nT(n) = 2T(n) + 2(n+1),
$$
and so
$$
T(n+1) = \frac{n+2}{n+1} T(n) + 2.
$$
Unrolling this gives
$$
\begin{align*}
T(n) &= 2 + \frac{n+1}{n} T(n-1) = 2 + \frac{n+1}{n} 2 + \frac{n+1}{n-1} T(n-2) = \cdots \\ &=
2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2}\right] + \frac{n+1}{1} T(0) \\ &=
2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2} + \frac{n+1}{1} \right] \\ &=
2(n+1) \left[\frac{1}{n+1} + \cdots + \frac{1}{1} \right] \\ &=
2(n+1) H_{n+1} \\ &= \Theta(n\log n).
\end{align*}
$$

A different way of analyzing the running time of quicksort in the average case computes the average number of comparisons. Due to linearity of expectation, it suffices to calculate the probability that two elements are compared. You can see both methods worked out in Section 3.4 of lecture notes from CMU.


Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?

No, there isn't (not unless P=NP).  Take an unweighted directed graph on $n$ vertices, and set all of the edge weights to $-1$.  Now there is a simple cycle of weight $-n$ if and only if there is a Hamiltonian circuit in the original graph.  But detecting the existence of Hamiltonian circuits is NP-hard.  Therefore your problem is NP-hard, too.


Find minimum distance match in sub-linear time in a data base

This problem is exactly solved by the k-d tree, which organizes points in $k$ dimensions with logarithmic lookup time.


In your case that the sizes are only 1, 2 or 4, the answer is quite easy:

If the knapsack has an odd size, then you pick the most valuable item of size 1 and add it to the last slot.

If the remaining knapsack has a size that is an odd multiple of two, then you pick the most valuable item of size 2, or the two most valuable items of size 1, whichever is more valuable, and put them to the last slot of size 2.

Now the remaining knapsack has a size that is a multiple of 4. You pick the most valuable item of size 4, or the two most valuable items of size 2, or the four most valuable items of size 1, or the most valuable item of size 2 plus the two most valuable items of size 1.

With other sizes, say sizes 2, 3 and 5, things will be more difficult. However, you can sort the items of each size in descending order, and can solve this using dynamic programming.

I suppose the time will be polynomial for every fixed size of weights, with the polynomial depending on the weights. But you can sort the items of each weight in descending order in O (n log n), and if there are m different weights and the size of the knapsack is K, you find the best solution easily in mW steps.

If the weights and K are large, the number of possible sums of weights may be a lot smaller than K. For example if K = 1 billion and three weights >= 100 million, there will be less than 167 possible sums of weights < K.


Is the symmetric difference of a non regular language L and a finite language f non regular?

Denoting symmetric difference by $\Delta$, note that $(L \Delta f) \Delta f = L$. This suggests the following strategy: show that the symmetric difference of a regular language and a finite language is regular. This implies your claim via proof by contradiction.

The product construction shows the stronger fact that the symmetric difference of two regular languages is regular. Hence you can strengthen your claim by replacing "finite" with "regular".


How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages?

After $n$ is fixed, you could choose $x = b^na^nb^n$. This string is clearly in $L$. By the Pumping lemma $x$ can be written as $uvw$, where $|uv| \leq n$ and $|v| \geq 1$. So for any choice of $u$ and $v$, $uv$ is a string consisting of only $b$s, and so is $v$. Thus $uv^iw = b...b(b...b)^ib...ba^nb^n$ which is not in $L$.

On @DavidRicherby comment:

The Pumping Lemma:

Let $L$ be a regular set. Then there is a constant $n$ such that if $z$ is any word in $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and for all $i \geq 0$, $uv^iw \in L$.

How to use

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$  in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = b^na^nb^n$.

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

In my proof the prefix of $z$ consists of $n$ $b$'s, so any choice of $u$, $v$, and $w$ implies that $v$ consists solely of $b$s.

5) You achieve a contradiction to the pumping lemma by showing that there exists $i$ such that $uv^iw \notin L$.

Just choose $i=2n$ and we have unequal number of $b$s on the left and right sides of the substring $a^n$: $b^{2n + d}a^nb^n \notin L$.

This is how we prove.


Bellman-Ford parent pointer (?) negative cycle

In the notation here, a vertex $v$ is called a parent pointer of a vertex $u$, if a shortest path to $u$, found so far in the algorithm, has $v$ preceding $u$. So in the graph above, starting at $a$ and moving to $b,c,d$ in that order, the parent pointers are $a,b,c$ respectively for $b,c,d$.

We say there is a loop in parent pointers if we have vertices $v_1,v_2, \ldots ,v_n$ such that $v_i$ is a parent of $v_{i+1}$ and $v_n$ is a parent of $v_1$. Notice that this is not happening in the earlier example. But if we change the weight of edge $(c,a)$ to $-3$, then we have $a$ as parent of $b$, $b$ parent of $c$ and $c$ as parent of $a$, forming a loop in parent pointers, indicating a negative cycle.

Proof for why this finds negative cycles is given in the document referred in that earlier post

Edit:

Suppose we have found a cycle $v_1,v_2,\ldots , v_n$ in parent pointers ($v_i$ is parent of $v_{i+1}$ and $v_n$ is parent of $v_1$). Let $P(v)$ denote the shortest path length obtained to vertex $v$ so far. Then, as $v_i$ is parent of $v_{i+1}$, we get $P(v_{i+1}) = P(v_i) + w(v_i,v_{i+1})$, where $w(u,v)$ is weight of the edge from $u$ to $v$. So $P(v_n) = P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}$. We have reached $v_n$ so far and now looking at its neighbour $v_1$. And $v_n$ is made parent of $v_1$. Which means the shortest path length to $v_1$ ($P(v_1)$) found so far is bigger than the path coming from $v_n$. That is, $P(v_1) > P(v_n) + w(v_n,v_1)$. Hence,

$$
P(v_1) > P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}
$$
$$
0 > \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}
$$

So any cycle in parent pointers corresponds to a negative cycle in the graph.

Note that this is only one half of the proof. We still need to show the converse (whenever there is a negative cycle in the graph, we will get a cycle in parent pointers).


No this means, that the language $L$ that contains all possible words ($L=\Sigma^*$) is in $P$. In other words, no matter what your input is, the algorithm accepts. And the corresponding language is of course (trivially) decidable in polynomial time.

To clarify things: A language is a set of words (the words are considered as encodings of the yes-instances of a problem). A complexity class is a set of languages - so it is a set of sets. When a language $L$ contains all possible words, it doesn't mean that a complexity class that contains $L$, contains all languages.


single algorithm to work on both directed and undirected graph to detect cycles?

Take a look at the answers for finding all cycles in graph.

You can transform undirected graph into a directed graph quite easily: for every edge (u,v) in your original graph G, put two edges (u --> v) and (v --> u) into your new directed graph T. Apply any of the algorithms that find cycles in a directed graph on T. However, notice that any undirected edge transforms into a directed cycle (u - v - u), so if your original graph was initially undirected, you can ignore cycles of length 2 at the end.


Distribute objects in a cube so that they have maximum distance between each other

All colors will be on the surface of the RGB cube, unless I'm mistaken, for the same reason that all electrical charge appears on the surface of electrical conductors. This suggests the following method to determine colors:

interpret the RGB color space as an XYZ Cartesian space;
interpret candidate colors as charged particles, e.g., electrons;
find the low-energy state of the system through e.g. simulated annealing;

For $n \sim 15$, a highly accurate simulation should be fairly quick; you could use a Runge Kutta technique, or even Euler's method with a small time step could probably do it (much easier to implement/understand). I might suggest the series "Numerical Recipes" for numerical integration/quadrature techniques of interest.

Once particles converge, you have the arrangement of colors by interpreting points as colors. Initially, particles can be arranged randomly on the cube's surface, with a little spacing (helps convergence and stability issues). Putting small groups on faces of the cube should work.

To avoid getting stuck in a local (rather than global) minimum, you can "pulse" some small random electric field after convergence and see whether the system goes back to the same configuration, or a different one. It's somewhat unlikely that randomly placed particles will do that in this scenario, but possible.

EDIT:

As pointed out in the comments, the assumption that optimal solutions should lie only on the surface probably doesn't hold for all geometries in the discrete case.

Fortunately, this has little bearing on the rest of the technique described above. Particles can be initially placed anywhere; just leave some room between pairs of particles for stability and covergence, and then iterate the system to convergence, then pulse a few times (possibly with increasing intensity) to see if you can get the system to converge to some different (possibly better) configuration.

Also note that I believe this method will maximize something like "(harmonic?) average distance between pairs of particles". If you want to maximize the minimum distance between pairs of particles, or some other average (geometric?) between pairs of particles, this may not give you the best solution.

In any event, I feel like this technique will give you an easy way to come up with good approximately-optimal sets of colors... getting actual "optimal" solutions is probably not required for your use-case. Naturally, if an exact and provably optimal solution is desired, numerical simulation is probably not the best way to go.


checking time for a circuit of size in polynomial k

You've misunderstood.  They are saying that the running time to check all $2^k$ assignments (not the time to check one assignment) is $\Omega(2^k)$.  It's a reasonable misunderstanding, as their wording is unclear, but that's what they mean.


How to find the spot which is furthest away?

As you get further from Germany, you will get points which are farther and farther away. So unless you are taking into account the spherical nature of Earth, we need to change the problem, and look for a location in Germany which is farthest away from all villages in Germany. This is known as the largest empty circle problem, and can be solved essentially by computing the Voronoi diagram of the set of villages in Germany.


Encoding algorithms better than or equivalent to Run Length Encoding

There are many general-purpose compression algorithms, for example Lempel-Ziv and its many variants (used for example by gzip), and Burrows-Wheeler (used for example by bzip2). You can just try them on your input and see how well they perform. If your data has particular structure, then it is possible that a dedicated compression algorithm would perform significantly better, but it's hard to tell without knowing more about the structure.


First, $|V|$ is the number of vertices and $|E|$ is the number of edges.

The point is that if a graph is connected it must have at least $|V|-1$ edges.  Therefore, $|V|\leq |E|+1$, so
$$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$

Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about what happens as some variable becomes large, over some infinite family of instances.  So, here, we're supposed to imagine that the infinite family of instances is the set of all connected finite graphs. It would have been clearer to just write $|V|\leq |E|+1$.


Asymptotic complexity of $-\log(c^{1/n} - 1)$

For $c \gt 1$ we have $c^{1/n} - 1 \sim \frac{1}{n}\ln c$, which gives
$$\lim\limits_{n\to\infty}\frac{\log(c^{1/n} - 1)}{-\log(n)} = \lim\limits_{n\to\infty}\frac{\log\ln c - \log(n)}{-\log(n)}=1$$
For proof brought approximation we can consider limit
$$\lim\limits_{x \to 0}\frac{e^x-1}{x} = \lim\limits_{x \to 0}e^x=1$$
based on   L'Hôpital, Taylor expansion etc. De facto it's derivative of exponent in point $0$.


Searching through all program of a stack-based language with little memory

I can give you a answer about the principles.

Find a computable bijection between your programs and the natural numbers. In essence, you would construct an admissible numbering. Then, you can just iterate over the naturals, compute the program corresponding to each number and perform your checks. You do not need to store any programs but the one under consideration.

The challenge is, of course, to find this bijection; it will depend on your language. If that helps you can relax injectivity; it is not necessary but duplicates will have performance impacts, obviously.

One concrete idea is: represent your language by a context-free grammar. Enumerate left-derivations along rule precedences, going from one program to the next using backtracking. It may even be possible to encode the derivation process in numbers, yielding a mapping as mentioned above.


Most Efficient Way to Map Generic Input To Generic Output

From an asymptotic perspective: No, there's no more efficient mapping than just using a table.  Lookup in a table is $O(1)$, and you can't beat $O(1)$.

From a practical perspective: The answer will depend upon the exact application domain.  For instance, sometimes using a cache will speed up things (by only a constant factor, but in practice constant factors can help), if the access pattern exhibits some locality.  It's impossible to give a general answer without knowing the specifics of the particular way you plan to use the lookup table.

However, no, you shouldn't expect there to be some clever number theory trick to build a faster lookup table.  Roughly speaking, a lookup table is as fast as you can get; all that remains is some practical optimizations.

Memory efficiency is a different matter, and depends upon the function f.  Sometimes it can be faster to compute f(x) from scratch than to look up x in the table.  Sometimes, if you've previously computed f(x') and if x' is "close" to x, then you can efficiently compute f(x).  It all depends on the function.


Good book on the history of programming languages?

There is an infrequently held conference series called History Of Programming Languages (HOPL). It was held in 1979, 1993, and 2007, the fourth installment is scheduled for middle of June, 2020.

The Proceedings for HOPL-I and HOPL-II were also published as books, for HOPL-III, both the papers and video recordings of the presentations are available. (Including the highly entertaining, though not necessarily highly scientific 50 in 50 by Guy Steele and Dick Gabriel, presenting 50 language-related ideas from 50 years in 50 words each within (a little bit more than) 50 minutes.)

There is also a website called Online Historical Encyclopaedia of Programming Languages, which collects about 9000 languages and presents them in the form of a hypergraph with several kinds of relationships (evolution-of, influence, dialect, …, also people involved, regions where it was developed, institutions, etc.) between them.


Which algorithm for game matchmaking in tournament

One plausible approach is to use local search.  In its simplest form, you could start by randomly assigning people to teams, then repeatedly picking a random pair of people and swapping them gives a better assignment, and iterating.  This kind of approach should be easy to implement and flexible.  But there's a lot more to say, so let me explain in more depth.

First, you need an objective function: a way to measure, quantitatively, how good a candidate assignment is.  In your case, you might define a way of computing a penalty score for any proposed team grouping (say, 2 point penalty for each extra or missing DPS, 2 point penalty for each extra or missing tank, 2 point penalty for each extra or missing healer, 3 point penalty for each extra person on the team over 6 or each missing person under 6; or whatever, you pick the penalty scheme).  Then you could plausibly define the objective function to be the sum of the penalty scores of all of the teams, and your goal is to find an assignment that minimizes this total penalty.

Next, you use some local search procedure to find an assignment that makes the total penalty as small as possible.  The simplest is hillclimbing, which works as follows.  Pick an arbitrary initial assignment (e.g., randomly assign each person to a team; or use any other heuristic method of computing an assignment -- it doesn't have to be optimal).  Then, in each iteration you randomly pick a modification to the assignment, check whether the proposed modification reduces the total penalty, and if so, you apply the proposed modification.  Repeat this over and over, until you go a long time with no improvement.

You need a way to generate a random modification.  A simple one would be to randomly pick two people, and swap which team they are on.  You can also consider more complex modifications.  For instance, randomly pick three  or fourpeople, and randomly permute them among their teams.  Or, randomly pick two people on two different teams, then randomly assign the first person to one of the two teams, then randomly assign the second person to one of the two teams (so this might put both people onto the same team; this modification is useful if you want to consider solutions where some teams have more than 6 people or fewer than 6 people).

This should be easy to program, and I suspect it'll give a reasonable solution.  I suggest trying it and see if you're happy with the solutions it generates.

There are a number of ways to make this more sophisticated, to try to generate solutions that are even better (lower total penalty).  You can use a more sophisticated form of local search.  For instance, you could try hill-climbing with random restarts, where you do the above process 100 times from 100 different random initial assignments, and keep the best solution found.  You could also try simulated annealing, where if the modification makes things worse we still have a (small) probability of applying the proposed modification, and we reduce this probability over time  in a specific way.

You'll have to modify this to deal with people who pre-register as a group.  Fortunately, it should be easy to generate modifications that respect this constraint.  For instance, suppose you randomly pick two people to swap, say Alice and John.  If you Alice is part of a pre-registered group with one other, then you might randomly pick someone on John's team so you can swap Alice + her partner with John + that additional person.    There are many possibilities; you should be able to select something that makes sense for your particular situation.


Hint: Try $L=0L_1\cup1L_2$. Can you see how to map $L_1$ to $L$ and $L_2$ to $L$? You have to be slightly clever; you might want to use prefixes other than 0 and 1.


What does route aggregation is an automatic process means?

Firstly, I assume you know the purpose of route aggregation (if you need more clarification on that, feel free to post another question, as it is another topic by itself).
Secondly, in this context, what Tanenbaum is saying is that aggregation can be done manually, but it is done normally done automatically by the routing processes. Manual aggregation is when a human looks at the various network destinations and decides which ones can be aggregated, and then enters the aggregated network destination info into the router configuration (during the process where we have, as Tanenbaum writes it, "an administrator assigning addresses to networks"). The alternative is, for the routing processes to handle it automatically.
Yes, it can be turned on or off through the router configuration. In fact, it can be turned on or off separately for each routing protocol being run on the router (if more than one routing protocol is operating).  It is perfectly fine to turn aggregation off for edge routers that are not connected to many networks. Then, their routing table will have individual entries for more networks (not aggregated), but would still not be too big. However, for routers in the Internet core, normally aggregation must be turned on so the routing tables don't become too big (200,000 prefixes is the size Tanenbaum mentions; without aggregation, they could be much bigger with many more prefixes).
It is an "automatic process" in the sense that the routers will exchange information as part of the routing protocol(s), and they can figure out the aggregation automatically, as part of their logic. "I mean isn't process especially on network is always automatic?" -> some things can also be configured manually. Hence, Tanenbaum tries to make the point that most aggregation is handled through the processes automatically.


No.  You can leave the month as is.  It shouldn't matter.  For a random forest, there's no value in normalizing it; it won't make the classifier any more or less accurate.

(The same is actually true for temperature, wind, and humidity data, too: there's no harm in normalizing them, but also no benefit, if you're using a random forest classifier.)


How to tell if a grammar is LALR(1) formally?

The answer to your first question is: Not that we know of.
A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton.
The good news is that the key complication is empty derivations. So, for example, if a $\hbox{LL}(1)$ grammar has no nonterminals that have only empty derivations (i.e. if every nonterminal has at least one non-empty derivation), it is $\hbox{LALR}(1)$.
See Beatty, On The Relationship Between LL(1) And LR(1) Grammars for further results. You may find something in there that's useful to you.


Is "Find a Steiner Tree of cost < K" NP-hard?

In fact, the optimization version of minimum Steiner tree isn't NP-hard, since only decision problems can be NP-hard. When we say that a minimization problem like minimum Steiner tree is NP-hard, what we mean is that the corresponding decision version is NP-hard. The decision version is just what you wrote: given an instance of minimum Steiner tree and a number $K$, to decide whether the minimum Steiner tree has cost at most $K$.


Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?

No, a quantum computer can't sum $n$ outputs from a black box function in $O(\lg n)$ queries.

For example, you could use magic summing power to easily do asymptotically better than Grover's algorithm at searching for solutions to a predicate. Except Grover's algorithm is proven to be asymptotically optimal. Contradiction.

Also, magic summing would trivially prove that $NP \subseteq BQP$. To determine if problem X has a solution or not, you'd simply sum up the outputs of the black box "if input is a solution for problem X then output 1 else output 0".


Is a unary language regular iff its exponent is a linear function?

Linear is close, but the technical term you're looking for is semilinear:, that is, a finite union of linear sets.

Half of the proof of this is a corollary of Parikh's Theorem, which says that any context-free language has a semi-linear Parikh map (that is, the set of vectors containing the occurrences of each letter in the alphabet).

For a unary language, the parikh map of the language is the language itself (i.e. each word is uniquely identified by how many letters it has), so every unary regular language is semi-linear.

The other half of the proof is showing that you can construct a regular language containing every unary semi-linear set. This takes a bit of work, but it's not too hard if you use regular expressions:

$a^k$ recognizes the language $\{ k \}$
$(a^k)^*$ recognizes $\{xk \mid x \in \mathbb{N}_0 \}$
$R_1 R_2$ recognizes $S_1 + S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $+$ here is element-wise addition
$R_1 | R_2$ recognizes $S_1 \cup S_2$ if $R_1$ recognizes $S_1$ and $R_2$ recognizes $S_2$, where $|$ here is regular-expression union.


This is only a sketch of solution (there might be some off-by-ones)

Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and the number of inversions of the permutation is exactly the sum of all $a_i$ corresponding to it (see for example Knuth TAOCP volume 3 for a nice development).

So the problem is equivalent to computing the cardinal of:

$$\{(a_1, \ldots, a_n) \in \prod_{i=1}^{n}\{0,\ldots,i-1\}, \sum_{i=1}^n a_i=k\}$$

This way, we find a DP algorithm with $n\times k$ states:

$$\text{dp}(n,k)=\sum_{i=0}^{\min(k,n-1)}\text{dp}(n-1,k-i)$$

Thus:

When $n$ is small ($n\le k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{n-1}\text{dp}(n-1,k-i)=\text{dp}(n,k-1)+\text{dp}(n-1,k)$$

So you can compute these in $O(k^2)$. In particular, we will need the following vector of size $k$:

$$\begin{bmatrix}
\text{dp}(k+1,0)\\
\vdots\\
\text{dp}(k+1,k)
\end{bmatrix}$$

When $n$ is large ($n>k+1$):

$$\text{dp}(n,k)=\sum_{i=0}^{k}\text{dp}(n-1,k-i)=\sum_{i=0}^k \text{dp}(n-1,i)$$

In this case $\text{dp}(n,\cdot)$ depends linearly on $\text{dp}(n-1,\cdot)$, the matrix being a $k\times k$ lower triangular matrix with nonzero coefficients being all 1-s. More formally, you can rewrite the previous equality as:

$$\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}=
\begin{bmatrix}
1&0&\ldots&\ldots&0\\
1&1&0&\ldots&0\\
\vdots&\vdots&\ddots&\ddots&\vdots\\
1&1&\ldots&1&0\\
1&1&\ldots&1&1
\end{bmatrix}
\begin{bmatrix}
\text{dp}(n-1,0)\\
\vdots\\
\text{dp}(n-1,k)
\end{bmatrix}$$

Just let me note:

$$A=\begin{bmatrix}
1&0&\ldots&\ldots&0\\
1&1&0&\ldots&0\\
\vdots&\vdots&\ddots&\ddots&\vdots\\
1&1&\ldots&1&0\\
1&1&\ldots&1&1
\end{bmatrix}$$

Now if you iterate the relation, you will get for any $i$:

$$\begin{bmatrix}
\text{dp}(n+i,0)\\
\vdots\\
\text{dp}(n+i,k)
\end{bmatrix}=
A^i
\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}$$

In particular:

$$\begin{bmatrix}
\text{dp}(n,0)\\
\vdots\\
\text{dp}(n,k)
\end{bmatrix}=
A^{n-k-1}
\begin{bmatrix}
\text{dp}(k+1,0)\\
\vdots\\
\text{dp}(k+1,k)
\end{bmatrix}$$

The vector on the left hand side is what we want ($\text{dp}(n,k)$), the vector on the right hand side is what we computed in the first step (when $n$ is small). So if we can compute the $k\times k$ matrix $A^{n-k-1}$, computing the answer can be done in $O(k^2)$.

Now let's see how fast we can compute $A^{n-k-1}$. I suggest three different ideas (I assume that you want the answer modulo some prime $p$):

1) Matrix exponentiation: if we can multiply $k\times k$ matrices with coefficients in $\mathbb{Z}_p$ in time $O(k^\omega)$), you can use fast exponentiation to have a $O(k^\omega \log n)$ algorithm ($\omega =2.38$ nowadays). Actually, if you are fine with a $O(k^3 \log n)$ algorithm, this should be easy to code (with the naive matrix multiplication algorithm)

2) Polynomial interpolation: if you look at the coefficients of $(A^T)^n$, it looks like:

$$(A^T)^n=\begin{bmatrix}
P_1(n)&P_2(n)&\ldots&P_k(n)\\
0&P_!(n)&\ldots&P_{k-1}(n)\\
\vdots&\ddots&\ddots&\vdots\\
0&\ldots&0&P_1(n)
\end{bmatrix}$$

where $P_1, \ldots, P_k$ are polynomials with integer coefficients and $P_i$ is of degre $i-1$. They satisfy some kind of "generalized Pascal triangle relationship":

$$P_i(n)=1+\sum_{j=0}^{n-1}P_{i-1}(j)$$

So it's possible to compute $P_i(j)$ for $1\le i \le k$ and $0\le j\le k-1$ in $O(k^2)$. We can find coefficients of $P_i$ by doing a Newton interpolation in $O(k \log k)$, so this should give a $O(k^2 \log k)$ algorithm.

3) Find a closed form for $A^i$ with the help of some well-known combinatorial objects. As I said in the comments, the polynomials $P_1, \ldots, P_k$ are close to Faulhaber's polynomials which can be computed in linear time. This might require some heavy handmade computation. I think it should lead to a  $O(k^2)$ algorithm.


I don't know whether there is a polynomial-time solution.  Since $L$ is fairly small ($L\le 10$), one possible approach is to use a SAT solver.
Suppose $L=10$.  For each vertex $v_5$ at distance 5 from $s$, we'll enforce that all paths $s \leadsto v_5$ have a different color sequence.  Then, we'll do the same for all paths $v_5 \leadsto e$.  This suffices to ensure your property holds.  (In general, replace 5 with $L/2$.)
Here is a plausible way to encode this in SAT.  For each edge $e$ and each color $c$, add a boolean variable $x_{e,c}$, which captures whether edge $e$ is assigned color $c$.  Also, for each pair of edges $e,e'$ at the "same level" (i.e., their start nodes are at the same distance from $s$), and for each pair of edges $e,e'$ that are part of the same path from $s$ to some vertex at distance 5 or some path from a vertex at distance 5 to $e$, add a boolean variable $y_{e,e'}$, which captures whether $e,e'$ receive the same color.  Then add constraints:

Enforce that $y$ are transitive by adding $y_{e,e'} \land y_{e',e''}  \implies y_{e,e''}$.

Enforce that $x,y$ are consistent by adding $y_{e,e'} \land x_{e,c} \implies x_{e',c}$ and $x_{e,c} \land x_{e',c} \implies y_{e,e'}$.

Enforce that the $x$'s are a one-hot encoding by adding the constraints $\bigvee_c x_{e,c}$ and $\neg x_{e,c} \lor \neg x_{e,c'}$ for all $e,c,c'$.

Enforce that each path uses all colors, by requiring $\neg y_{e,e'}$ for all pairs of edges $e,e'$ in the same path.

Enforce that each path uses different colors: for each pair of paths of the form $s \to v_1 \to v_2 \to v_3 \to v_4 \to v_5$, $s \to v'_1 \to v'_2 \to v'_3 \to v'_4 \to v_5$, add the constraint
$$y_{s\to v_1,s\to v'_1} \lor y_{v_1\to v_2,v'_1\to v'_2} \lor \dots \lor y_{v_4 \to v_5,v'_4 \to v_5}.$$
Do the same for each pair of paths of the form $v_5 \leadsto e$.

Then use an off-the-shelf SAT solver to solve this SAT instance.
I think the number of variables and clauses won't grow too large, so maybe there is a hope this instance of SAT might be solvable in a reasonable amount of time.  In particular, for any particular vertex $v_5$, the number of paths of the form $s \leadsto v_5$ will be at most $5!=120$; if there are more, then the graph cannot be colored.  Why?  Well, as j_random_hacker points out, all such paths must use the same set of 5 colors.  So, each such path's color sequence is of the $5!$ permutations of that set.  Also, each such path must have a different color sequence (otherwise we can pick any one path $v_5 \leadsto e$, append it to both, and obtain two paths $s \leadsto e$ with the same color sequence), so there can be at most $5!$ such paths.  This means that the SAT instance will have something like ${120 \choose 2} M + {M \choose 2}$ boolean variables and clauses, where $M$ is the max number of vertices per layer.


Calculate Shortest Path (Shortest Time) Through a Store in a Graph

You can do this with two instances of shortest paths.

You need to know the shortest distance $d(A,S)$ for each store $S$. This is just Dijkstra from source $A$.
You also need to know all the shortest paths from each store to B; i.e. $d(S,B)$ for each store $S$. This can be done by reversing the edges in the graph and running Dijkstra from source $B$.

Once you have these two, all you need to do is compute the min over paths that stop at a store, including the weight $w$ of the store.

$\min_S \left(d(A,S) + w(S) + d(S,B)\right)$

Asymptotically, in total, this is no more expensive than just running Dijkstra's algorithm. In practice you can stop early in each instance of Dijkstra once you've seen all of the stores.


Fibonacci Series with Dynamic Programming

$n$ is the index of the Fibonacci number you're computing. For example, the sixth Fibonacci number, $f(6)$, is equal to 8.

If we assume that function calls take constant time and we are using your model, then it's clear that the number of calls, $C(n)$, to compute the $n$-th Fib will be given by
$$C(n)=C(n-1)+C(n-2)$$
with $C(0)$ and $C(1)$ both being 1.

Hmm. That recurrence is almost exactly the recurrence for the Fibs, just shifted by a place, so we have $C(n)=f(n+1)$. In other words, the asymptotic growth of $C(n)$ is the same as the Fibs themselves.


Graph ordering with smallest max vertex "discrepancy"

Your problem is known as BANDWIDTH. Another way to describe it is: we are given a matrix, and we want to rearrange the rows and columns (in the same way!) so that the only non-zero entries lie across a narrow band around the diagonal.

BANDWIDTH is known to be NP-complete. Unger showed that it is NP-hard to approximate to within any constant factor.
Feige gave an $\tilde{O}(\log^3 n)$-approximation algorithm which uses metric embeddings.

Among the many variants of BANDWIDTH, let me mention the MINIMAL LINEAR ARRANGEMENT problem (known by various other names), in which the goal is to minimize $\displaystyle\sum_{(u,v) \in E} |f(u)-f(v)|$ rather than $\displaystyle\max_{(u,v) \in E} |f(u)-f(v)|$.


Is the language of DFAs which do not accept themselves recognizable?

DFAs always terminate, so if you want to check whether a given DFA accepts or rejects a given word (say its representation), just run it on the word. You can even do this in polynomial time.


How to find the optimum solution of Weighted set cover in O(2^n)

Use dynamic programming. For every $i \in [m]$ and every $V \subseteq U$, compute the minimal weight of sets among $S_1,\ldots,S_i$ needed to cover $V$.

Here is pseudocode, which uses $w_i$ for the weight of $S_i$:

Set $T[V][0] \gets \infty$ for all $\emptyset \neq V \subseteq U$, and $T[\emptyset][0] = 0$.
For $i = 1,\ldots,m$:

Set $T[V][i] \gets T[V][i-1]$ for all $V \subseteq U$.
Set $T[V \cup S_i][i] \gets \min(T[V \cup S_i][i], T[V][i-1] + w_i)$ for all $V \subseteq U$.

Return $T[U][m]$.


Prove the red blue separation problem is NP-complete

A separating polygon separating a set of points $S$ from a set of points $T$ is a simple polygonal circuit $P$ for which every point of $S$ is interior or on the boundary of $P$, and every points of $T$ is exterior or on the boundary of $P$. Let $D(P)$ denote the perimeter of a polygon $P$, that is, the sum of the Euclidean lengths of the edges of $P$. If $P$ is a separating polygon for $S$ and $T$ with minimum value of $D(P)$, then $P$ is called a minimum separating polygon.
The problem you describe is known as the minimum separating polygon problem (MSP), formally:

Instance: Two finite point sets $S$ and $T$, and an integer $k$.
Question: Is there a separating polygon $P$ for the sets $S$ and $T$ such that $D(P) \leq k$?

MSP is NP-hard. The hardness was first shown by Eades and Rappaport by a reduction from TSP, see [1], Section 2 for the reduction.

[1] Eades, Peter, and David Rappaport. "The complexity of computing minimum separating polygons." Pattern Recognition Letters 14.9 (1993): 715-718.


Can a computable function converge to an uncomputable number?

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where  $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $< n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_{2^n-1}}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.


Don't forget that the final content of the tape can be treated like the output of the algorithm that the TM computes; in other words, a TM is able to compute a function: there is no "reject state" but only an "accept state" and the function result is the content of the tape at the end of the computation.

But if you want to learn more on the relation between decision problems and function problems , (quickly) read the Decision Problem - Equivalence with functions problems entry on Wikipedia, and then search some lectures online on the subject.


The notation $A^T$ stands for the transpose of a matrix. It is not specific to machine learning, but rather standard notation in linear algebra. Other notations are sometimes used, for example $A'$.
A related operation is the adjoint $A^*$. The transpose and adjoint are equal for real matrices.


Can BPP be bounded around any constant other than 1/2?

If $c < 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin.

What went wrong? For BPP amplification to work, we need a gap between the promise for a Yes instance and the promise for a No instance. In your definition of "weak BPP" (not a standard term), you are given an algorithm such that:

On a Yes instance, accepts with probability at least $s(n) + 1/p(n)$.
On a No instance, accepts with probability at most $s(n)$.

In contrast, in your suggested definition, we have the following promise:

On a Yes instance, accepts with probability at least $c + 1/p(n)$.
On a No instance, accepts with probability at most $1 - c - 1/p(n)$.

If $c < 1/2$ then for large enough $n$, the two acceptance intervals overlap (at acceptance probability $1/2$), and so the definition is meaningless. When $c = 1/2$, there is an inverse polynomial gap, which can be amplified to a constant gap, to match the standard definition of BPP.


Since the strings must be of the form $ababab\dotsm$, and also there must be 0, 2, 4, 6, ... $b$s, begin with four states, each of which "remembers" the input so far:

$q_0$: just saw an $a$ and have seen an even number of $b$s so far,
$r_0$: just saw a $b$ and have seen an odd number of $b$s so far,
$q_1$: just saw an $a$ and have seen an odd number of $b$s so far,
$r_1$: just saw a $b$ and have seen an even number of $b$s so far.

Then, it's clear that these states will have transitions in a cycle, with transitions:

$\delta(q_0, b) = r_0$
$\delta(r_0, a) = q_1$
$\delta(q_1, b) = r_1$
$\delta(r_1, a) = q_0$

and the other possibilities will either be undefined or lead to a trap state, depending on what model of a DFA you're accustomed to using. Now make a new start state $s$, with $\delta(s, a) = q_0$ (since you've just seen an $a$ and have no $b$s yet), and, for similar reasons, define $\delta(s, b) = r_0$. I'll leave it to you to decide which (two) of the states in the cycle of four states should be final.

There are systematic ways to do this kind of product DFA, but in this case, it's no simpler than this ad hoc construction.


Okay so I managed to solve it.

It was simply: PHY rate * (DATA time / Access cycle time, where backoff = 30us)


What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

This problem is known as dynamic connectivity and it is an active area of research in the theoretical computer science community. Still some important problems are still open here.

To get the terminology clear, you ask for fully-dynamic connectivity  since you want to add and delete edges. There is a result of Holm, de Lichtenberg and Thorup (J.ACM 2001) that achieves $O(\log^2 n)$ update time and $O(\log n / \log\log n)$ query time. From my understanding it seems to be implementable. Simply speaking the data structure maintains a hierarchy of spanning trees - and dynamic connectivity in trees is easier to cover. I can recommend Erik D. Demaine's notes for a good explanation see here for a video. Erik's note also contain pointers to other relevant results. As a note: all these results are theoretical results.

These data structures might not provide ConnectedNodes queries per se, but its easy to achieve this. Just maintain as an additional data structure the graph (say as doubly connected edge list) and the do the depth-first-search to get the nodes that can be reached from a certain node.


Why is the commit phase in PBFT necessary?

PBFT is a master piece, for its technical breakthrough and exquisitely precise language. Many descriptions on the protocol details worth reading multiple times to grasp all the nuances.
I will:

quote the original paper (some math notation expressed in Latex, I will use pseudo code instead)
add on my understanding/interpretation.
Q&A myself important questions
Answer your question directly by giving out an example

Pre-Prepare and Prepare phases

We define the predicate prepared(m,v,n,i) ....
The pre-prepare and prepare phases of the algorithm
guarantee that non-faulty replicas agree on a total order
for the requests within a view. More precisely, they
ensure the following invariant: if prepared(m,v,n,i) is
true then prepared(m',v,n,j) is false for any non-faulty
replica j (including i = j) and any m' such that D(m') !=D(m)
.

This means, once reached "prepared" stage (i.e. one replica has received more than 2f+1 PREPARE), this replica, if non-faulty, could be certain that, this message m in this view v is associated with this sequence number n.
Commit phase

The commit phase ensures the following invariant: if
committed-local(m,v,n,i)
is true for some non-faulty i
then committed(m,v,n)
is true. This invariant and
the view-change protocol described in Section 4.4 ensure
that non-faulty replicas agree on the sequence numbers
of requests that commit locally even if they commit in
different views at each replica.

^^^ This is the clue for me to go back and carefully read the definition of "commit-local" over and over:

and committed-local(m,v,n,i)
is true if and only if prepared(m,v,n,i)
is true and has
accepted 2f+1 commits (possibly including its own)
from different replicas that match the pre-prepare for m;
a commit matches a pre-prepare if they have the same
view, sequence number, and digest.

^^^ notice that? match the pre-prepare, not match the prepare, why? remember "PREPARE" gives certainty on ordering within a view, "PRE-PREPARE for m" emphasize on certainty of sequence number regardless of which view, as long as commit matches the pre-prepare.
Maybe you know why by not, but if it is still not clear, please read on.
Q:Why COMMIT phase necessary?

There are replicas (non-faulty or otherwise) that didn't receive enough (i.e. 2f+1) PREPARE messages, either due to lossy network or being offline for a while. For them, they can't reach PREPARED stage. But! But when they heard from 2f+1 replicas broadcasting COMMIT message, they could be certain to commit on (m,v,n,i)
Apparently, a obvious benefit for COMMIT stage is that it accelerate the agreement/consensus process. Intuitively, you could understand it as : I'm on my way to school, Bob told me school is closed today. I couldn't take one man's word as truth. But as I march on, I see many more classmates (who have already checked whether school is closed or not) returning back from school telling me school is closed. Up until majority told me so, I will take their word for it before reaching school myself.

Example of cross view COMMIT
There are 4 replicas in total. For a message m, I, the replica, received a COMMIT: (COMMIT, m, v, n, i=2), meaning in view v, node #2 told me he committed. But since I didn't receive any other commits, I couldn't reach "commit-local" stage.
Now, "NEW-VIEW" message has been passed around. During protocol redo: other replicas multicast PREPARE messages for each message between min-s and max-s, then later I receive another COMMIT (COMMIT, m, v+1, n, i=3)
Now, could I reach "commit-local"? since I have one commit in view v and another in view v+1.
Answer is yes. Because new primary issued a new PREPARE for m, and I had two matching commits -- 2 commits in a 4 replicas system. Good enough.
Hope it helps!
Any further comment is welcomed.
Cheers!


Assuming you're talking about polynomial-time reductions, since PRIME is in $P$, you can reduce it to any non-trivial decision problem (for which there is at least one instance with answer YES and at least one instance with answer NO). Moreover, any problem in $P$ can be reduced to PRIME.

To reduce an instance $I$ of PRIME to an instance $I_Q$ of non trivial decision problem $Q$, let $Y_Q$ and $N_Q$ be a YES and a NO instance for $Q$, respectively. The reduction is as follows: solve $I$ using a polynomial-time algorithm for PRIME. Then, let

$$I_Q = \begin{cases}Y_Q & \mbox{if $I$ is a YES instance}, \\ N_Q & \mbox{if $I$ is a NO instance}.\end{cases}$$

To reduce an instance $I_Q$ of a problem $Q \in P$ to an instance $I$ of PRIME, solve $I_Q$ using a polynomial-time algorithm for $Q$ and define

$$I = \begin{cases}2 & \mbox{if $I_Q$ is a YES instance}, \\ 1 & \mbox{if $I_Q$ is a NO instance.}\end{cases}$$


Conventions on NP regarding certificates with length exponential in a variable $k$

No, you don't say it is NP for any fixed k, since that's not right; NP means something specific, and that's not it.  Instead, I would suggest that you describe the situation, as you did, in a self-contained way, since your definition is different from the ones where we have existing terminology.


Recurrence formula for optimal binary search tree

Quoting Introduction to Algorithms:

The easy case occurs when $j = i-1$. Then we have just the dummy key $d_{i-1}$.
The expected search cost is $e[i,i-1] = q_{i-1}$.

In slightly more detail, $e[i,j]$ is supposed to be the cost of the optimal binary search tree for $k_i,\ldots,k_j$. It is important to understand what cost means here. The cost is with respect to the following distribution on the input:

With probability $p_i$, key $k_i$ is being searched.
With probability $q_i$, a dummy key $d_i$ between $k_i$ and $k_{i+1}$. (When $i = 0$, it is a key smaller than $k_1$, and when $i = n$, it is a key larger than $k_n$.)

Unfortunately, the textbook is being extremely sloppy, and never bothers to explain what they mean by "the cost of the optimal binary search tree for $k_i,\ldots,k_j$". It seems that they are measuring the expected cost with respect to the stated keys as well as with respect to the dummy keys $d_{i-1},\ldots,d_j$. That is, they want to minimize
$$
q_{i-1} \mathit{cost}(d_{i-1}) + p_i \mathit{cost}(k_i) + q_{i+1} \mathit{cost}(d_{i+1}) + \cdots + q_{j-1} \mathit{cost}(d_{j-1}) + p_j \mathit{cost}(k_j) + q_j \mathit{cost}(d_j).
$$
When $j = i-1$, there are no real keys, but there is a dummy key $d_{i-1} = d_j$, and so the cost is $q_{i-1} \mathit{cost}(d_{i-1})$. The optimal cost here is clearly $1$, and that's how they get $q_{i-1}$.


Complexity of Linear Diophantine equations

Yes, this class of equations can be solved in polynomial time.  In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$.  That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd.  In addition, if a solution exists, one can be found using the extended Euclidean algorithm.


Finding if the given language is regular or not

$L$ is regular.

Here is a proof as hinted by your second method, which points out that we may take advantage of the fact that regular languages are closed under complement. Another useful fact is regular languages is closed under intersection. Let $F=\{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}, m+n+o\le 5\}$. As a finite language, $F$ is regular. Let $H = \{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}\}$. As expressed by the regular expression $a*b*c*$, $H$ is regular. Since $L= H\cap\overline F$, $L$ is regular.

We can also see that $L$ is regular by the following one-line regular expression that expresses $L$. It is wrapped into multiple lines for easier reading.

$
((a\{6,\}|a\{5,\}b+|a\{4,\}b\{2,\}|a\{3,\}b\{3,\}|a\{2,\}b\{4,\}|a+b\{5,\})c*)|\\
((a\{5,\}|a\{4,\}b+|a\{3,\}b\{2,\}|a\{2,\}b\{3,\}|a+b\{4,\}|b\{5,\})c+)|\\
((a\{4,\}|a\{3,\}b+|a\{2,\}b\{2,\}|a+b\{3,\}|b\{4,\})c\{2,\})|\\
((a\{3,\}|a\{2,\}b+|a+b\{2,\}|b\{3,\})c\{3,\})|\\
((a\{2,\}|a+b+|b\{2,\})c\{4,\})|\\
(a+|b+)c\{5,\}|\\
c\{6,\}
$

Now that we have shown $L$ is a regular, the first method must be incorrect. In fact, we do not have to keep track of how many a′s, b′s and c′s we have seen. All we need is to make sure that the total number of them is greater than 5. There is a difference between these two requirements.

By the same argument, we can see easily that for any integer $k$, $L_k = \{a^mb^nc^o|m,n,o\in\Bbb Z_{\ge0},\,m + n + o > k\}$ is a regular language.

Here is another similar fact. For any integer $s$ and $t$, $L_{s,t}=\{a^mb^nc^od^p|m,n,o,p\in\Bbb Z_{\ge0},\,m + o > s, n+p >t\}$  is a regular language.


Hint: we have $A(x^2) = \sum_{n=0}^\infty a_nx^{2n} = a_0 + a_1x^2 + a_2x^4+ \cdots$. What can we say about the coefficients of odd powers ($x, x^3, \dots$)?
Now do the same for $xB(x^2)$, what can we say about  the its even power coefficients?
What does this mean for their sum?


How many possible assignments does  a CNF sentence have?

There are 5 (Boolean) variables in the formula. Each of these could be either true or false. This means that there are $2^5=32$ ways of assigning values to these variables.

Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).


This is a textbook application of radix sort.

Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$.

The same approach works for numbers up to $n^k$, and takes time $O(kn)$.


Finding largest disjoint subtrees spanning nodes

Here's an algorithm.  Let $D(l)$ denote the department of the product category of a leaf $l$.
To find the subtree for leaf $l$ do the following.  For every leaf $l'$ such taht $D(l') \neq D(l)$, mark the node $\text{lca}(l, l')$.  Now, your largest subtree is the subtree rooted in the highest unmarked node.  Call this node $\text{root}(l)$.
To compute for all leaves, clear the marks and output $\bigcup_{l \in L} \text{root}(l)$, where $L$ is the set of leaves.

A different (faster) algorithm: For each leaf $l$, move upwards and mark each node with $D(l)$.  If you hit a node already marked $D(l)$, you move on to the next leaf.  If you hit a node marked with a different color, delete the node.  Then your connected components should be your largest disjoint subtrees.

You ask if it's a known problem, I think that the closest you get to a known problem is the lowest common ancestor problem.


What is the state of the art for k nearest neighbour search?

It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions.  It sounds like you are claiming that your data structures works in an arbitrary number of dimensions ($n$), but the running time does not depend on the dimension ($n$). That seems unlikely; nearest neighbor search is known to be hard to solve in high dimensions (the so-called curse of dimensionality).

Alternatively, if you meant that your scheme works only in 3 dimensions, then that is an important caveat that needs to be mentioned.  Being able to find the nearest neighbor in 3D in $O(1)$ time would be an impressive result; I'm not aware of any data structure that is known to have this worst-case running time.

Yes, a k-d tree is a standard data structure for this task, when you are working in 3 dimensions.  There are also generalizations and related data structures; see metric trees, binary space partitioning trees and octrees.  R-trees and R*-trees can be used if the set of points are changing.

Without knowing how your algorithms works, it's hard to give a definitive answer whether it is worth publishing.  To figure out, a good starting point would be to familiarize yourself with the published and known algorithms and see if your idea still seems to be better than all known schemes.  If you're still not sure, make ask a new question here with the specifics of your algorithm and what your specific uncertainty is.


Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

Yes, deterministic context-free languages are closed under union with regular languages.

It is easy to show they are closed under intersection with regular languages. We can apply a product construction. When reading a symbol we also do a step of a FSA that is running in parallel. Accepting a computation means accepting both the DPDA part and the FSA part.

This doesn't work for union. Why? Because a DPDA may end up in an infinite loop of $\varepsilon$-transitions, so it will never read all of its input. In that way we cannot test acceptance by the FSA.

In order to make this work we also need a normal form for DPDA, that they will never do such infinite loops, and always read all input. That normal form is usually proved when showing DCFL are closed under complement (and is non-trivial).

By he way, once we know that DCFL is closed under complement and closed under intersection with regular languages, closure under union with regular languages follows by De Morgan: $L\cup R = (L^c \cap R^c)^c$.


Is relational algebra a procedural, imperative, and/or declarative language?

The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of steps to find the result: simply execute the operations in the correct order to produce the result.

In contrast, in an expression of a calculus based language, the result is described through a property that holds on it, without specifying which operations should be applied to find it, neither the order in which they should be applied. So it “declares” the properties of the result, not a “procedure” to obtain it.

This terminology has no particular relations with other terminologies in the field of programming languages (like imperative, functional, applicative, etc.)


Assign m agents to N points by minimizing the total distance

My understanding of this question is that you have a two lists of $n$ two-dimensional coordinates. The first list represents the position of a bunch of agents (robots, maybe, or police cars). The second list represents where those agents need to go (which places need to have police cars dispatched to them), and may be longer than the first list.

It is always possible to minimize the sum distance traveled by all agents, if that's what you're worried about: there are $!n$ ways we could dispatch the robots to new positions, we can enumerate all of them, calculate the distance the agents have to travel, and pick the one that has the least distance. As written, "enumerate all the possibilities" I think counts as an answer to your question, though it's probably not the one you wanted.

There are a couple of more precise questions, all or none of which might be interesting and/or research-level. (I'm not a Theory A person...)

Is a solution possible if each agent (robot/police officer) has to make a decision independently, or has a limited ability to coordinate with other agents?
How quickly could the central dispatcher come up with a plan to dispatch everyone most efficiently? Aaron Roth observes in the comments that this can be solved as a min-cost flow problem. I think that solution looks like this (hopefully I won't make a total fool of myself here): each agent is a source vertex and each dispatch target is an intermediate vertex. There is a capacity-1 edge from each source to a vertex representing the dispatch target, and the cost along that edge is proportional to the distance between the agent's initial position and the dispatch target. There is also a capacity-1, cost-0 edge from each dispatch target vertex to the sink.
How quickly could the central dispatcher come up with a plan to dispatch everyone that is some multiple of the most efficient solution?


What is the definition of$\mathcal{Mod} P$ counting complexity class?

The class ModP is defined in Definition 3.1 on page 3 of your reference.

The abstract of the paper clearly states that the paper studies the computational power of the new counting class ModP. This suggests that this class is introduced in the paper, and in particular, is defined in the paper.


Trading States for Symbols with a Turing Machine

Here is one idea. Let $|w| = n$. We will have a tape symbol for each number in $\{0,1,\ldots,n\}$, which we will denote by $\langle i \rangle$. The machine starts by writing $\langle n \rangle$ on the tape. Then it repeatedly performs the following steps:

Read $\langle i \rangle$.
Depending on the value of $i$ and on $w$, switch to a write-0 or a write-1 state.
In write-$b$ step, move right until reaching the first blank, write $b$, then move left until reaching a cell of the form $\langle j \rangle$.
Replace $\langle j \rangle$ with $\langle j-1 \rangle$, or terminate if $j = 0$.

The exact implementation of this algorithm depends on your exact model. In your model, you might be able to do it using 5 states. But in any reasonable model, $O(1)$ states are needed, regardless of $w$.


monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies

I misunderstood the phrase "monotonically increasing". It actually means the same thing as "non-decreasing", as explained on p 53 of the book. The phrase is different from "strictly increasing", also defined there, which is what I had thought it meant.

With "monotonically increasing" meaning "non-decreasing", the exercise makes a lot more sense.


Asymptotic bounds of the following operations

If you could do all three operations faster than $O(\log n)$ time, then you would obtain a sorting algorithm whose running time is faster than $O(n \log n)$ time.  That's known to be impossible for comparison-based algorithms.
So, you probably can't do better than $O(\log n)$ time for all three operations.  In particular, you definitely can't do better using a comparison-based algorithm (one that only compares items but has no other knowledge about the values of items).
The reduction works as follows.  First, scan through the list of $n$ numbers and insert each into your data structure.  Second, scan through the list again; for each number $x$, look up its index, and then write it into an output array at that index.  This does $2n$ operations on your data structure, so if your data structure can support insert and lookup in $O(\log n)$ time, the total running time will be $O(n \log n)$.


Turing Machine Encoding and Complement of the Diagonal Language

The following hint repeats my comments and assumes that the question asks for the first encoding of a Turing machine which is in $\overline{L_d}$.

Hint: Make a list of the first few encodings of Turing machines, in lexicographic order. For each one, check whether it's in $\overline{L_d}$. The first one which is in $\overline{L_d}$ is the answer.

By the way, how does your encoding handle termination? Does it mark accepting/rejecting states in some way, or does it use another convention?


Number of submatrices, of a base matrix derived from an array, with a particular sum

Try writing a small example (e.g., where $N=3$), then pick a submatrix (say, $2 \times 2$) and write an expression for the sum of the elements of that submatrix in terms of the entries of $A$.  By doing some algebraic manipulations, you should be able to get a nice expression for this sum.

This will then let you characterize which submatrices sum to $K$, in terms of the entries of $A$.  Working on this a bit, you should be able to get a $O(N^2)$ time algorithm [assuming a submatrix is defined by a consecutive range of rows and a consecutive range of columns].

Since this is your exercise/programming contest problem, I'll let you work out the details.


are NP Complete languages closed under any regular operations?

For all of the examples in this answer, I'm taking the alphabet to be $\{0,1\}$. Note that the languages $\emptyset$ and $\{0,1\}^*$ are definitely not NP-complete.

The class of NP-complete languages is not closed under intersection.  For any NP-complete language $L$, let $L_0 = \{0w\mid w\in L\}$ and $L_1 = \{1w\mid w\in L\}$.  $L_0$ and $L_1$ are both NP-complete but $L_0\cap L_1 = \emptyset$.
The class of NP-complete languages is not closed under union. Given the NP-complete languages $L_0$ and $L_1$ from the previous part, let $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ and $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$.  $L'_0$ and $L'_1$ are both NP-complete but $L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under concatenation. Consider the NP-complete languages $L'_0$ and $L'_1$ from the previous part.  Since both languages contain $\varepsilon$, we have $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under Kleene star.  For any NP-complete language $L$, $L\cup \{0,1\}$ is NP-complete but $\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.
If the  class of NP-complete problems is closed under complementation, then NP = coNP. Whether this is true or not is one of the major open problems in complexity theory.


Algorithm to schedule employees into days

This looks a lot like the stable marriage problem, itself related to the problem of matching in biparftite graphs. There are very efficient algorithms to solve both problems.


Main idea: For each variable $x_i$ introduce a new variable $y_i$ and add a new clause $(\lnot x_i, \lnot y_i)$. Replace each occurence of $\lnot x_i$ in the original clauses by $y_i$.

The new clauses ensure that $y_i$ can be set to true if and only if $x_i$ is false. Thus we neither add nor remove satisfying assignments for the original clauses, while the new clauses can always be satisfied.


Find the cheapest combination of raw foods that fulfill nutritional requirements

Use integer linear programming.  Suppose you have $n$ foods.  Let $x_1,\dots,x_n$ be zero-or-one variables, with the intention that $x_i=1$ means you include food $i$ in the combination.  Then the price is a linear function of these $x$'s, so that's your objective function you are minimizing.  If you want the total carbs to be within a range, you can express that as a linear inequality (e.g., $\ell \le c_1 x_1 + \dots + c_n x_n \le u$, where $\ell,u$ are the lower and upper bounds of the range and $c_i$ is the amount of carbs in food $i$).  Feed this to an off-the-shelf ILP solver, and it should give you the optimal answer.


(Un)computability of a restricted Halting Problem

Fix a value of $n$. For $b \in \{0,1\}^n$, consider the following algorithm $A_b$:

If $x \leq n$ then output $b_x$, otherwise output $0$.

Clearly one of the $2^n$ algorithms of the form $A_b$ computes your function $h$, hence $h$ is computable.


It depends on what you plan to do with your CS degree. If you plan to continue to graduate school, a math minor would certainly be helpful. If your interests turn out to be in hardware, and the courses are available, some courses in electrical engineering would be appropriate, as a minor or not.

On the other hand, if you plan to go straight to Real Life$^{\text{TM}}$, then the possible enhancements widen considerably. Math is still a strong contender, of course, but if, for example, you see yourself in, say, the IT department in banking or finance, a strong background in economics would also serve you well. If you are of an artistic bent and see yourself working for Pixar, a CS major and an art minor wouldn't hurt. These days, so many businesses are in some way or another computational in part, you should really be asking yourself "What do I like to do?" and then tailor your non-CS courses accordingly.

If you go the RL$^{\text{TM}}$ route, my experience with recruiters is that I've stopped asking "what courses should we offer our students to best prepare our graduates for work in your company?" because the answers are almost always "You're doing fine with your courses, but what we really want is people with an adequate technical background who can express their ideas orally and in writing and who have some idea about how the world works". Unless you're a really good writer and speaker, take some courses in writing and oral communication---it will be time well spent. If you go that way, get as broad an education as possible, since you'll eventually be making policy decisions for your company, rather than writing programs.

Finally, be open to all possibilities, since you can't know what opportunities that might open. A number of years ago, I heard from a CS major I had taught who had become a successful rodeo clown. Did he use his major? Nope. Was he happy with his life? It certainly appeared so. The single most important lesson I teach my students is, get a job you love, then you'll never have to "work" a day in your life. Best of luck.


N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

Can you see why $\max((-2)+5, 3+4) \lt \max(-2+3, 4+5)$?

The reason is simple. Because on the right hand side, the maximum number 5 is not  paired with the minimum number.

Let the numbers are $a_1\le a_2\le \cdots\le a_n$. Let the numbers be paired in some way.

If $a_n$ is paired with $a_1$, we are done at this round.
Suppose $a_n$ is paired with $a_j$, $j\not= 1$. Then $a_1$ is paired with $a_k$ for some $k\not= n$. So we have two pairs, $\{a_n, a_j\}$ and $\{a_1, a_k\}$. The sums of these two pairs are $a_n + a_j$ and $a_1 + a_k$, the large one of which is $a_n+a_j$.

Let us switch $a_j$ and $a_1$ so that $a_n$ will pair with $a_1$, and $a_j$ will pair with $a_k$. The sums of the two new pairs are $a_n + a_1$ and $a_j + a_k$, both of which is at most $a_n+a_j$, i.e., the large one of them is at most $a_n+a_j$. So after the switch, the maximum sum of the pairs involving $a_n, a_j, a_k, a_1$ does not increase. Since other pairs stays the same, So after the switch, the maximum sum of all pairs does not increase.

Continuing this process, we will make sure the largest number remaining be paired with the smallest number remaining at each round. The maximum sum of the pairs will never increase at each round. After $n/2$ rounds, we will reach the pairing where $a_k$ is paired with $a_{n+1-k}$.

You can see the above approach is indeed the "greedy stays ahead" approach.


Using few tricks the equation can be transformed into classic Quadratic Programming problem:

$ E = \arg \max_{E} \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2 $

Defining $ \mathbf{e} = vec \left ( E \right ) $, Namely vectorizing the matrix, and defining a matrix $ A $ defined the proper usage of the weights $ {w}_{\mathbf{rs}} $, Namely put them in the correct entry at each row per pixel the above could be rewritten as:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left ( \mathbf{e} - A\mathbf{e} \right ) }^{T} \left ( \mathbf{e} - A\mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) $$

Defining $ B = I - A $ yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} {B}^{T} B \mathbf{e} $$

Defining $ L = {B}^{T} B $ , namely $ L , is a Symmetric Positive Definite Matrix yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}  $$

Adding the equality constraints using $ C \mathbf{e} = \mathbf{t} $ where $ \mathbf{t} $ is vectorization of all "Reference Pixels"

All in all this yields a Classic Quadratic Programming problem given by:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}, \; s.t. \; C \mathbf{e} = \mathbf{t} $$

Few notes:

The matrix $ L $ is Symmetric and Positive Definite matrix and usually sparse (Assuming "Small Neighborhood").
The matrix $ L $ wast built by the Matrix $ I - A $ which each row of it was normalized to be zero (Each row of $ A $ is normalized to 1 ).

Now two things are needed:

Optimized fast algorithm to solve this problem utilizing its properties.
Assuming the image is large, are the methods to solve this problem by blocks to avoid memory limits?


What's the most time efficient way to find the number of nodes reachable from each root and no other root?

A rough sketch, you can fill in the details:

Using Strongly Connected Components (SCCs), you can reduce the graph to a DAG. If you run topological sort on this DAG, all incoming edges to a node will be processed before any outgoing edges. Then just store at each node which root has reached it, or if none/more than one roots have reached it.


Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible?

If you prepare a superposition containing the various input problems, a quantum computer will allow you to compute a superposition containing the various outputs.

That being said, I'm not sure why you would want to do this. You only get to sample one of the outputs, and you don't get to pick which one. You'll get one of them at random. Presumably you would instead do some quantum computation on the output superposition, perhaps use a QFT to sample from their frequency space... but just remember that this means you must erase the input! Otherwise you won't be able to interfere the various output cases.


Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

Dijkstra's algorithm is used only when you have a single source and
  you want to know the smallest path from one node to another, but fails
  [in graphs with negative edges]

Dijkstra's algorithm is one example of a single-source shortest path or SSSP algorithm.  Every SSSP algorithm computes the shortest-path distances from a chosen source node $s$ to every other node in the graph.  Moreover, it computes a compact representation of all the shortest paths from $s$ to every other node, in the form of a rooted tree.  In the Wikipedia code, previous[v] is the parent of $v$ in this tree.

The behavior of Dijkstra's algorithm in graphs with negative edges depends on the precise variant under discussion.  Some variants of the algorithm, like the one in Wikipedia, always runs quickly but do not correctly compute shortest paths when there are negative edges.  Other variants, like the one in Jeff Erickson's lecture notes always compute shortest paths correctly (unless there is a negative cycle reachable from the source) but may require exponential time in the worst case if there are negative edges.

  Floyd-Warshall's algorithm is used when any of all the nodes can be a
  source, so you want the shortest distance to reach any destination
  node from any source node. This only fails when there are negative
  cycles.

That's correct.  Floyd-Warshall is one example of an all-pairs shortest path algorithm, meaning it computes the shortest paths between every pair of nodes.  Another example is "for each node v, run Dijkstra with v as the source node".  There are several others.

  Bellman-Ford is used like Dijkstra's, when there is only one source.
  This can handle negative weights and its working is the same as
  Floyd-Warshall's except for one source, right?

Bellman-Ford is another example of a single-source shortest-path algorithm, like Dijkstra.  Bellman-Ford and Floyd-Warshall are similar—for example, they're both dynamic programming algorithms—but Floyd-Warshall is not the same algorithm as "for each node v, run Bellman-Ford with v as the source node".  In particular, Floyd-Warshall runs in $O(V^3)$ time, while repeated-Bellman-Ford runs in $O(V^2E)$ time ($O(VE)$ time for each source vertex).

For further details, consult your favorite algorithms textbook.  (You do have a favorite algorithms textbook, don't you?)


Number of parenthesizations and Catalan numbers

Define function $Q:\mathbb N\to\mathbb N$  such that $Q(n)=P(n+1)$ for all $n\ge 0$. Or, what is equivalent, $P(n)=Q(n-1)$ for all $n\ge 1$.

We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\quad\quad\quad$$

Also, for $n\ge0$,
$$\begin{aligned}
  Q(n+1)&=P(n+2)\\
   &=\sum^{(n+2)-1}_{k=1} P(k)P((n+2)-k)\\
   &=\sum^{n+1}_{k=1} Q(k-1)Q(n+1-k)\\
   &\stackrel{k=i+1}{=\!=\!=\!=}\sum^{n}_{i=0} Q((i+1)-1)Q(n+1-(i+1))\\
   &=\sum^{n}_{i=0} Q(i)Q(n-i).\\
\end{aligned}$$

We see that $Q(\cdot)$ and the Catalan numbers $C(\cdot)$ share the same initial condition and the same recurrence relation. So, we have, for all $n\ge0$,
$$ Q(n) = C(n).$$
So, for all $n\ge 1,$
$$P(n)=Q(n-1)=C(n-1)={\tfrac {1}{n}}{\tbinom {2(n-1)}{n-1}}$$

Exercise. Define function $D$ such that $D(n)=C(n-1)$ for $n\ge1$. Show that $D(n)=P(n)$ for $n\ge1$, assuming that you have not seen the deduction above.


Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

A concise answer would be: To have enough time (resp. space) to do the diagonalization jobs.

Remember that both of these separation results are just using diagonalization techniques. In particular, to separate bigger time/space bound apart smaller time/space bound, one use the bigger bound (by just ONE machine) to diagonalize over all the possible smaller time/space-bounded machines.

And to do that, one needs to know when to finish (on each input) in case of time hierarchy, or where to prohibit the crossing (on each input) in case of space hirachy. This is possible only when the bigger bound is constructible. For time, constructibility at least requires $\geq n$. For space, constructibility at least requires $\geq log(n)$.

For full constructibility, it is not necessary to require any thing. But note that while constant functions are fully constructible (in time and space), functions in between like $log log(n)$, $log log log(n)$ (for space), $\sqrt{(n)}$, $n^{2/3}$ (for time) are not so. Informally, the spectrum of full constructibility is not continuous.

Lastly, one can even separate the notions of time constructibility by reasonable conjectures.


How to simulate online matching algorithms (implementation)

Just to clarify your doubt. An online algorithm is an algorithm that does not have the whole input (otherwise it would be offline), but it gets the input in a sequential manner. Looking at your paper, for example, they define an online algorithm as (1 Introduction):

An on-line algorithm receives a sequence of requests and must respond
to each request as soon as it is received

I would use a simpler example than a graph of boys and girls. Think about a list of numbers that you want to sort.
Then an offline algorithm would take the whole input and sort it: quicksort.
An online algorithm sorts after every single number, or better, it ensures that a certain property is maintained over a sequential input. An clear example of it is
Insertion Sort, since it ensures that the output list is always sorted.
Now looking at your questions:

In this paper, they refer to U (boys) as "on-line" which means data arrive sequentially (in real-time?) not all at once. ~> Exactly. The girls in the example arrive one by one. You might know how many they are in total, (since |V| seems to be given), but you do not know which one is the next one until you "matched" the current one. As in the "insertion sort" example, you do not know the next number until you sorted the current one.
In the online version do we assume a predefined limited number for both U and V(boys and girls)? or just for girls? ~> The paper says "Let G(U,V,E) be a bipartite graph", therefore my take on it is that you know how many boys (|U|) and how many girls you have (|V|).


Is something more than Turing complete Turing complete?

Yes. The "complete" in NP-complete and in Turing-complete are two different notions.

For Turing-complete it means (as per the definition in the question) that the system can compute the complete (in the basic English sense) set of Turing computable functions (i.e. it can do at least everything a Turing Machine can).

For NP-complete, it's not obvious that the word has anything to do with its basic English meaning except perhaps in the tenuous sense that the problem has all the complexity inherent in the class, whatever that means.

Another way to express the difference is that NP-complete can be rephrased as "complete for the class NP", whereas Turing-complete does not mean "complete for the class R" (or RE).


Distributed algorithms are sub-type of parallel algorithm. Different parts of algorithm executes simultaneously on different processors with minimum information sharing and minimum dependency among them. Although the difference between parallel algorithm and distributed algorithm is not very clear but in general parallel algorithm is used for speed-up and increase data handling capacity while distributed algorithm is mainly implemented for fault tolerance, scalability. But in your case, may be you are just storing data in different places (distributed) but the algorithm you are using is not a distributed algorithm.


Why isn't there a universal separator character for data files?

We could have a field separator, but we don't, because of historical reasons. Most of the characters are brought from the era of typewriters. So we have line-separator ^M and page-separator ^L, and we actually have record separator \037 and unit separator \038 which can be used as field separator. But in reality no one uses that. First if you have a text file like csv, you want to use separators which are visible like , : TAB or SPACE. If your file is binary you are free to do almost anything with it.

Now it is too late to have a universal field separator. You can have your own private field separator of your choice. Just don't use it in your fields too.


This problem is new to me.  It has similar hardness to weighted MaxSAT; there is a polynomial-time Turing reduction in both directions.  Here is a key fact:

Let $\varphi,(w_1,\dots,w_n)$ denote a weighted CNF formula, where $w_1,\dots,w_n$ are the weights on the clauses.  Then the following two conditions are equivalent:

There is an assignment to $\varphi,(w_1,\dots,w_n)$ so that the average of the weights of the satisfied clauses is at least $a$.
There is an assignment to $\varphi,(w_1-a,\dots,w_n-a)$ so that the sum of the weights of the satisfied clauses is at least $0$.

This lemma yields an equivalence between weighted MaxSAT and weighted MaxAverageSAT.
For instance, if you have an instance of weighted MaxAverageSAT that you want to solve, here is how you can solve it using an off-the-shelf solver for weighted MaxSAT.  Basically, use binary search on the average $a$.  Given $a$, you can test whether it is possible to achieve an average at least $a$, by using the solver on $\varphi,(w_1-a,\dots,w_n-a)$ and checking whether it gives you an assignment where the sum of the weights is at least $0$; you can then use this to determine whether to increase $a$ or decrease $a$ in the binary search.  After polynomially many iterations of binary search, you'll narrow it down to a small enough range that you can uniquely determine the maximum achievable average.


The question under what circumstances we need to jump from a universe to one higher in the hierarchy is a good one. Having the hierarchy and the ability to climb it is important. You need to jump levels when you want to treat a universe as a type or as part of a type. For example to define functions of (non-dependent) type
$$
   A \rightarrow \mathcal{U}_i
$$
you must show that $A \rightarrow \mathcal{U}_i$ is in a universe.
But that cannot be  $\mathcal{U}_i$ or some smaller universe. So what do we do? To deal with the problem (without using the unsound $\mathcal{U}_i : \mathcal{U}_i$), we need to jump up a universe. The rule that
enables us to make this jump is $\mathcal{U}$-Intro
$$
   \frac{\vdash \Gamma : ctx}{\Gamma \vdash \mathcal{U}_i : \mathcal{U}_{i+1}},
$$
given in Appendix A.2.3. The very point of the hierarchy of universes is that we can do this. This can be seen as a safe approximation of having universes contain themselves.


How can one byte hold 256 possibilities?

I just did a quick animation to convince you. Yellow is one, blue is zero.


Using Little's law to find the average N of customers

Your intuition was right.  As you hinted, Little's law only applies to a stable system.  This is not a stable system.  The arrival rate exceeds the rate at which customers can be serviced.  Therefore, the number of customers waiting in line will grow without bound, getting increasingly larger as time increases.  That means this is not a stable system.

You can only apply Little's law to stable systems.  Since this isn't a stable system, Little's law doesn't apply.


Suppose that $X$ is a random variable over the set $\{1,\ldots,n\}$ satisfying $\Pr[X=1] = a$. Let $Y$ be the indicator of the event $X=1$. Then
$$
\begin{align*}
H(X) &\stackrel{(1)} = H(Y) + H(X|Y) \\ &\stackrel{(2)}=
h(a) + aH(X|Y=1) + (1-a)H(X|Y=0) \\ &\stackrel{(3)}\leq h(a) + (1-a) \log (n-1).
\end{align*}
$$
Here (1) is the chain rule (using $H(X) = H(X,Y)$, since $Y$ is determined by $X$), (2) follows from $\Pr[Y=1]=a$ and the definition of $H(X|Y)$, and (3) follows from $H(X|Y=1) = 0$ (since when $Y=1$ we have $X=1$) and $H(X|Y=0) \leq \log (n-1)$ (since when $Y=0$, the r.v. $X$ only attains the values $2,\ldots,n$).

Furthermore, assuming $a \neq 1$, equality holds only if $X|Y=0$ is uniform, that is, if $\Pr[X=i|Y=0] = 1/(n-1)$ for $2 \leq i \leq n$, or in other words, if $\Pr[X=i] = (1-a)/(n-1)$ for $2 \leq i \leq n$.


Are Time-sharing and multi-tasking operating systems same or different

Just as multiprogramming allows the processor to handle multiple batch jobs at a time, multiprogramming can also be used to handle multiple interactive jobs. In this latter case, the technique is reffered to as time sharing, because processor time is shared among multiple users. In a time-sharing system, multiple users simultaneously access the system through terminals, with the OS interleaving the execution of each user program in a short burst or quantum of computation.

William Stallings, Operating Systems Internals and Design Principles, 7th Edition

You should keep in mind that the principal objective of a time sharing system is not to maximize processor use, but to minimize response time.

I think it would be correct however to assert that on a single processor system, multi-tasking is achieved through time sharing. Remember that a processor can execute only one task at a time at any given time.


how to prove that log(n!) >= c n log(n) for some c >0?

$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$

so

$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$