If the universe were predetermined, would non-deterministic automata still make sense?

It makes perfect sense. Non-deterministic automata and non-deterministic algorithms in general are useful in many situations. The best known situation is when one designs algorithms (or strategies or recipes or ..) and analyzes them.

For example, an algorithm for computing the maximum element of a set of numbers will have a loop of the form "as long as the set is not empty, take out an element and compare it with the current max value". This algorithm is non-deterministic because I did not explain how one chooses what element to pick. I did not explain it because it is not important for the correctness of the method (and because deciding in advance how to pick an element would blur the issues and limit the scope of my algorithm).

Note that, in all likelihood, all actual implementations of the algorithm will run deterministic code. But it is useful for me to think in term of the more abstract, more generic, non-deterministic algorithms. You may give it a different name but non-determinism is an essential concept.

Here is another way to see that non-determinism in mathematical models is not related to non-determinism in the actual world : your question is similar to me asking if the universe is governed by predeterminism, does the $P\not=NP$ question make sense?


Are all prefix codes uniquely decodable?

You can prove by induction on the length of the encoding that any string is uniquely decodable.

Let $s=s_1...s_n$ be some string encoded with a prefix free code. Since our code is prefix free, there exists a unique prefix of $s$, $s_1...s_j$ which is a code word. $s_{j+1}...s_n$ is also a valid encoding (we removed a single codeword from a concatenation of codewords), so by our inductive hypothesis, $s_{j+1}...s_n$ is uniquely decodable, which completes the proof.


Assume $\Sigma = \{a,b\}$. We want to generate a word $w_1\#w_2$ is such that $w_1 \ne w_2^R$. There are two obvious possibilities:

$|w_1| = |w_2|$: In these words, there has to be at least one pair of positions equidistance from $\#$ such that the letters in these positions are different. Using the non-terminal $S_1$, we will generate the part of $w$ till we reach the first such pair; then we transition to non-terminal $S_2$ which will generate the opposite letters at that pair of position and move to the non-terminal $S_3$. From $S_3$, we are free to generate whatever we want. This will make sure that we have at least such pair of opposite letters, and hence $w_1 \ne w_2^R$.
We can generate such words using following grammar:
\begin{align}
S_1   &\rightarrow aS_1a|bS_1b|S_2\\
S_2  &\rightarrow aS_3b|bS_3a\\
S_3 &\rightarrow aS_3a| bS_3b| aS_3b | bS_3a|\#
\end{align}
$|w_1| \ne |w_2|$: In this case, with the non-terminal $P_1$ we will generate any word with equal number of letters on both side of $P_1$, and then we will move to either the non-terminal $P_2$ or $P_3$. With $P_2$ (or $P_3$) we will generate more letters either on the left side (or the right side) of $\#$. In the end, this will make sure that $|w_1| \ne |w_2|$.
We can generate such words using the following grammar:

\begin{align}
P_1   &\rightarrow aP_1a| bP_1b| aP_1b | bP_1a| P_2 |P_3 \\
P_2  &\rightarrow aP_2|bP_2|a\# | b\#\\
P_3 &\rightarrow  P_3a|P_3b|\#a | \#b\\
\end{align}

For the given language, the grammar would be: $S \rightarrow S_1|P_1$.


Prove that the depth of every vertex in a cycle is $\le \lfloor \frac{n}{2} \rfloor$ in a breadth first search?

There may be other ways to prove your claim, the simplest seems to me is by induction on $n$.

Base case : $n=3$, that means input graph is a triangle and it is easy to see that in this case maximum depth is $\le \lfloor \frac{n}{2}\rfloor$

Inductive case:  Suppose that depth of every vertex is $\le  \lfloor \frac{k}{2}\rfloor$ in $k$ cycle graph want to prove that depth of every vertex is $\le  \lfloor \frac{k+1}{2}\rfloor$  for $k+1$ cycle graph.

Hint for Inductive case: Going from $k$ cycle to $k+1$ cycle means we have added one vertex to any one of the edge ( as we know its both endpoints have depth  $\le  \lfloor \frac{k}{2}\rfloor$ (due to induction ) ) of the $k$ cycle graph it means depth of both endpoints in $k+1$ cycle will be    $\le  \lfloor \frac{k+1}{2}\rfloor$.


Dynamic Programming, Counting Independent Sets

Let $OPT_N[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that neither of the leftmost two vertices can be selected into an independent set.

Let $OPT_T[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the top of the leftmost two vertices must be selected in the independent set.

Let $OPT_B[i]$ be the number of independent sets in the graph with $2i$ vertices with the additional constraint that the bottom-most of the leftmost two vertices must be selected in the independent set.

According to the above definitions $OPT_N[1] = OPT_T[1] = OPT_B[1] = 1$ while, for $i>1$:
$$
\begin{align*}
OPT_N[i] &= OPT_N[i-1] + OPT_T[i-1] + OPT_B[i-1]\\
OPT_T[i] &= OPT_N[i-1] + OPT_B[i-1]\\
OPT_B[i] &= OPT_N[i-1] + OPT_T[i-1]
\end{align*}
$$

The number of independent sets on a graph with $2i$ vertices is then $OPT_N[n] + OPT_T[n] + OPT_B[n] = OPT_N[n+1]$.

You can simplify the above formulas by noticing that you must have $ OPT_T[i] = OPT_B[i]$.


Here's an efficient method that doesn't involve constructing a graph of the states and searching for a path to each target value. Let the capacities of the bottles be integers $K_1<K_2$, respectively, and denote by $(a_1, a_2)$ the current amounts in the bottles. You have six basic operations you can perform, for $i=1, 2$:

$f_i$: fill bottle $i$.
$e_i$: empty bottle $i$.
$p_i$: pour as much of bottle $i$ as will fit into bottle $3-i$.

We'll show this

  Theorem. If $\gcd(K_1, K_2) = 1$ (i.e., $K_1$ and $K_2$ have no factors in common), then you can start in state $(0,0)$ and end in state $(0, t)$ for any target integer $0\le t\le K_2$.

Consider these two sequences of basic moves, starting in state $(0, b)$:

Sequence $S$: if $b>K_2-K_1$, perform $f_1, p_1, e_2, p_1$.
Sequence $T$: if $b\le K_2-K_1$, perform $f_1, p_1$.

The result of $S$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(K_1-(K_2-b),K_2)\stackrel{e_2}{\rightarrow}(K_1-K_2+b,0)\stackrel{p_1}{\rightarrow}(0,K_1-K_2+b)
$$
and the result of $T$ will be
$$
(0, b)\stackrel{f_1}{\rightarrow}(K_1,b)\stackrel{p_1}{\rightarrow}(0, K_1+b)
$$
It's not difficult to establish that if $b>K_2-K_1$, the $S$ sequence will satisfy that the first component of each state will be less than or equal to $K_1$ and the second will be less than or equal to $K_2$ at each step and we can show similarly that the basic moves in the $T$ sequence are likewise always legal at each step.

For example, with $K_1=3, K_2=5$ we will have the following sequence of states:
$$
(0,0)\stackrel{T}{\rightarrow}(0,3)\stackrel{S}{\rightarrow}(0,1)\stackrel{T}{\rightarrow}(0,4)\stackrel{S}{\rightarrow}(0,2)
$$
so the sequence $T,S,T,S$ will generate the target values $0, 3, 1, 4, 2$, and of course we can always generate $K_2$ by a single $f_2$ move. Notice that we have generated all the target values $0\le t\le K_2=5$, as the theorem above indicated we should.

To show that this behavior happens for all integer capacities $K_1<K_2$ where $\gcd(K_1, K_2) = 1$, consider the second component values at each stage modulo $K_2$: an $S$ sequence takes $(0,b)\rightarrow(0, K_1-K_2+b)$ and $K_1-K_2+b\equiv K_1+b\pmod{K_2}$. Similarly, a $T$ sequence takes $(0, b)\rightarrow(0, K_1+b)$, so any sequence of $S$-$T$ moves starting at $(0,0)$ will produce the target values $nK_1\pmod{K_2}$, for $n=0, 1, 2, \dotsc,K_2-1$.

For our example, with $K_1=3,K_2=5$, we'll have the sequence of target values
$$
\langle\,0, 3, 6, 9, 12\,\rangle \equiv\langle\,0, 3, 1, 4, 2\,\rangle\pmod{5}
$$
All that remains to establish our theorem is to show that the $K_2$ elements of the target sequence are distinct. Suppose that they weren't, namely that there exist $n, m$ with $0\le n < m < K_2$ such that $mK_1\equiv nK_1\pmod{K_2}$. Then we would have $(m-n)K_1\equiv0\pmod{K_2}$ which would mean that $K_2$ would have to divide $(m-n)K_1$. However, $K_1$ has no factors in common with $K_2$ since $\gcd(K_1, K_2)=1$, so $K_2$ would have to divide $m-n$. However, $m-n<K_2$ and so the only possibility would be that $m-n=0$, i.e., $m=n$, contrary to our assumption. Thus, all the $K_2$ values in our target sequence are distinct, establishing our theorem.

Notes

For completeness, we note that if $\gcd(K_1,K_2)=g>1$ then you can make all and only those target amounts $ng$ where $0\le n\le K_2/g$, since we can reduce this case to one with capacities $K_1'=K_1/g,K_2'=K_2/g$ and observe that $\gcd(K_1',K_2')=1$.
Instead of the $S$-$T$ sequences, these can also be used:
$$\begin{align}
Q: &\text{if }b < K_1, \text{ perform }p_2,f_2,p_2,e_1\\
R: &\text{if }b \ge K_1, \text{ perform }p_2,e_1
\end{align}$$
The $S$-$T$ sequences might not produce a given target in the fewest number of moves. It may be the case that the $Q$-$R$ sequences will get to a given target value faster and vice-versa. It's possible, using the extended Euclidean algorithm, to determine which sequence choice will reach a particular target value quicker.
To generate all the possible target values by this method will take $O(K_2)$ time.
If you only want an answer to the interviewer's question, "is there a sequence of operations that leaves an amount $k_3$ in the larger bottle?" here's an algorithm that runs in time $O(\log K_2)$: if $k_3 > K_2$ answer "no", otherwise compute $g=\gcd(K_1, K_2)$ (which you can do in time $O(\log K_2)$) and if $g$ divides $k_3$, answer "yes", else answer "no".


Minimum number of givens for General Sudoku of size $n^2 \times n^2$

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is known for $n = 2$ (4 x 4 Sudoku), of which the minimum clues is 4 (25% of cells filled). There are 13 such non-equivalent puzzles. (based on info at "enjoysudoku.com").

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is also known for $n = 3$ (9 x 9 Sudoku), of which the minimum clues is 17 (about 21.0% of cells filled). About 49,000 such non-equivalent Sudokus have been discovered.

For $n = 4$ (16 x 16), the fewest clues known in any puzzle is 55 (about 21.5% of cells filled), but it is not known if this is the fewest possible. (based on info at "enjoysudoku.com").

For $n = 5$ (25 x 25), little work has also been done to find the fewest clues possible, and comparatively few Sudokus of this size have been constructed. One 25 x 25 Sudoku is known to have 328 clues. So from a cursory study, the fewest clues for (n=5) is 328 or fewer (about 52% or fewer cells filled). Note: this Sudoku was not an attempt to be an example with few clues. I listed it only to provide an initial upper bound.


Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$

When $n$ is large, $T(n-\sqrt{n})$ is much larger than $T(\sqrt{n})$. Therefore, roughly speaking,
$$ T(n) \approx T(n-\sqrt{n}) + \Theta(n). $$
Now let us imagine extending $T$ to all inputs, and suppose that it was differentiable. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and consequently
$$ T'(n) \approx \Theta(\sqrt{n}) \Longrightarrow T(n) = \Theta(n^{3/2}). $$
Armed with this guess, let us now attempt to show that it indeed describes the order of growth of your recursion. On the one hand, unrolling $T(n) \geq \Theta(n) + T(n - \sqrt{n})$, we get
$$
T(n) \geq \Theta(n + (n-\sqrt{n}) + \cdots + (n-\lfloor \sqrt{n}/2 \rfloor \sqrt{n})).
$$
Here there are $\Omega(\sqrt{n})$ summands, each of which is at least $n/2$, and so $T(n) = \Omega(n^{3/2})$.
In the other direction, let us assume that $\Theta(n) \leq Cn$, and let us try to prove inductively that $T(n) \leq Kn^{3/2}$. For the inductive step to go through, we would need
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2}.
$$
The mean value theorem shows that for some $\theta_n \in [0,1]$,
$$
n^{3/2} - (n - \sqrt{n})^{3/2} = \sqrt{n} \cdot \frac{3}{2} \sqrt{n-\theta_n \sqrt{n}} \geq \sqrt{n} \cdot \frac{3}{2} \sqrt{n - \sqrt{n}},
$$
which is at least $n$ for $n \geq 4$. Therefore for $n \geq 4$, we have
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} - Kn + Kn^{3/4} + Cn.
$$
For $n \geq 16$, we have $n^{3/4} = n \cdot n^{-1/4} \leq 16^{-1/4} n = n/2$, and so
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} + (C-K/2)n,
$$
which is at most $Kn^{3/2}$ if $K \geq 2C$.

More generally, similar arguments should show that if $k(n) = o(n)$ then the recurrence $$T(n) = T(k(n)) + T(n-k(n)) + \Theta(n)$$ should have the solution $$T(n) = \Theta\left(\int \frac{n\,dn}{k(n)}\right). $$


Longest subarray with at most two different values - Runtime complexity for a DP solution

Here is how the sliding window algorithm works (unfortunately, I don't understand your code, so can't say whether this is the same algorithm).

We keep track of two pointers $i,j$, with the following properties: the subarray $A[j],\ldots,A[i]$ contains exactly two values, and it is maximal with respect to $j$ (that is, either $j = 0$ or $A[j-1],\ldots,A[i]$ contains three values). We also keep track of the two values in question $a,b$, and of their last appearance $k_a,k_b$. Finally, we keep track of the longest valid subarray seen so far.

In the initialization phase, we scan the array until we see two different values; if the array is constant, then the answer is the length of the array.

At steady state, we take a peek at $A[i+1]$. If $A[i+1] \in \{a,b\}$, we update $k_a$ or $k_b$, and simply increase $i$. If $A[i+1] \notin \{a,b\}$, then we do two things. First, we update the value of the longest valid subarray seen so far (comparing it to $j-i+1$). Second, suppose that $A[i] = a$; then we set $j = k_b+1$, set $b = A[i+1]$, set $k_b = i+1$, and increment $i$.

Finally, when reaching $i = n$, we update the value of the longest valid subarray (comparing it to $j-i+1$), and output the result.

As you can see, this algorithm performs $O(1)$ operations per iteration, so runs in $O(n)$ time.


Is there a complexity metric for finite state machines?

Yes, there is a canonical complexity metric for finite state machines: the number of states.  It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric).  We don't use a normalized metric based on the combination of such values.  We just count the number of states.


Prove that this solution to the Closest 3-Sum problem always works

The core of the problem is to solve the 2 sum closest problem for a particular i:

Given a target value, find a pair of numbers who's sum is closer to the target value.

The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right)

Your question is why can we decrease r or increase l.

The answer is as the array is sorted, and suppose nums[r] + nums[l] < target, we would not gain any better result comparing nums[l] with any of the values of nums between l and r. Because for any other value in nums[l to r] the sum is even smaller.
 As we wouldn't get any better result, why not forget about the value nums[l] all together? Right?
And that is what we do by increasing l.

This reasoning happens since the beginning of the 2 sum closest search. When l=0 and r=len(nums). We discard values one by one until we are left with l=r-1.


Show that regular languages are closed under Mix operations

Take any string over the alphabet $\Sigma$. Colour some of the letters red and the remaining letters green. Accept the original string if the red letters form a string in $L_1$ and the green ones are in $L_2$.

More technically, regular languages are closed onder intersection and under (inverse) homomorpisms.

Let $\Gamma = \Sigma \times \{1,2\}$ be an alphabet with colours.

Define the homomorphisms $h_i:\Gamma^* \to\Sigma^*$, $i=1,2$ by $h_i(a,i) = a$ and $h_i(a,j) = \varepsilon$ for $i\neq j$. These keep only letters of their assigned colour, whereas their inverses colour the letters into that asigned colour while inserting arbitrary letters of the other colour.

Finally let $g:\Gamma^* \to\Sigma^*$ be the morphism $g(a,i) = a$ (which removes the colour).

Then $Mix_2(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \;)$.

PS. Let $R_{12}$ be the regular language $[(\Sigma\times \{1\})(\Sigma\times \{2\})]^*$.
Then $Mix_1(L_1,L_2) = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap R_{12} \;)$.

Just for fun,  $L_1 \cdot L_2 = g(\; h_1^{-1}(L_1) \cap h_2^{-1}(L_2) \cap (\Sigma\times \{1\})^*(\Sigma\times \{2\})^* \;)$. Regular languages are closed under concatenation :)


Impossibility condition in the Byzantine Generals problem

all the papers [...] state that $3m+1$ with only $m$ traitors will definitely give
  you the correct solution

They should actually state that when $3m+1$ then correct algorithms exist, but not all algorithms are correct.

Algorithms are like cooking recipes (in fact recipes are algorithms): Consider the problem of baking bread. There are books that tell you that you require flour, water and yeast (or similar). But not every recipe of the three will at the end resemble bread.
Consider this one: Mix a spoon yeast, a spoon of flour and 5 litres of water, fill in glasses and refrigerate overnight, serve cold... Definitely not bread ;-)

What your example shows is that the algorithm given in 1),2),3) is not one that solves
the Byzantine Generals problem. (Note that it is well known that a correct algorithm will (in the worst case) need at least m+1 rounds.)

Answer to original question on CSTheory:

I think your miss-conception lies in the assumption

  m+1 loyal generals should vote the same way

Why should this hold?

Assuming you are talking about the problem as defined in LSP82:
For simplicity let's set $m=1$. Then with just $2m+1=3$ generals
you have one commanding general and two lieutenant generals.
When the commanding general is correct, he and the correct general
will vote the same way. So in this case your assumption holds.
But what if the commanding general himself is Byzantine? Then he can
give different instructions to the two correct (lieutenant) generals,
and they are no longer guaranteed to vote the same way.

In general, if the proposer/commanding general is faulty then
there is no way to guarantee that all correct processes will vote in the same way.


Seeking nontrivial small SAT/UNSAT instances

To build a satisfiable instance, start by picking an assignment to the variables that will be a solution.  Then, randomly generate clauses that are satisfied by this assignment.  Add as many clauses as desired.  If you add enough clauses, then with high probability your chosen solution will be the only one, and the problem will be non-trivial.

For instance, suppose your assignment is $x_1=\text{True}$, $x_2=\text{False}$.  Then you could add any subset of the clauses $x_1 \lor x_2$, $x_1 \lor \neg x_2$, or $\neg x_1 \lor \neg x_2$.  For example, one random formula you could generate might be $(x_1 \lor x_2) \land (\neg x_1 \lor \neg x_2)$.

To build an unsatisfiable instance, proceed as above; then add one more clause that is violated by the solution you chose in advance.  If you added enough clauses, it is likely that there will be no other solution, so the problem will be unsatisfiable.  Check with a SAT solver just to be sure.


Karp reduction from PARTITION to SUBSET SUM

Let's say we have a canditate set $A=\{a_1,...,a_n\}$ to feed as input to PARTITION. There is a transformation in polynomial time $f$, with $f(A)=(A,B)$, where $B=$${\sum_{i=1}^n a_i }\over 2$.
Then $A$ is a solution to $PART$ if and only if $(A,B)$ is a solution to $SSUM$.
So we have $PART \le_m^p SSUM$


Specifically speaking, 3-SAT is an example of NP-Complete problem. But your problem is only considered with NP problems.

We have the decision problem:

  Is a SAT problem in NP?

Obviously, it is. Because you could always verify a "certificate" in time linear to your input size (values of your literals, that is a sequences of 0s and 1s).

For your question:

  Is a un-SAT problem in co-NP? (complement to SAT problem)

We could find the following definition:

  A decision problem X is a member of co-NP if and only if its
  complement X is in the complexity class NP [1].

Therefore, un-SAT is co-NP by definition.


What is the difference between exhaustive search & combinatorial search?

My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, in general exhaustive search is in the worst case linear in the size of the search space to be explored.

On the other hand, combinatorial search instead is a smarter kind of search, which usually exploits one or more pruning strategies to avoid testing all of the possible candidate solutions. In this case, you can safely discard some candidates (depending on the particular algorithm of course) and therefore you can save precious time. An example of combinatorial search is, for instance, branch and bound. Here, you may safely skip some subtrees since, depending on your particular optimization problem, you know in advance that no node within a certain subtree can yeld a better solution than the current one during the execution of your algorithm.


The idea is that the process is not terminated: only the current operation is cancelled. The process reacts to the cancellation by trying again. In this model, it is assumed that each process runs something like the following pseudocode:

begin_transaction:
    try:
        acquire(lock_1);
        acquire(lock_2);
        …
        release(lock_2);
        release(lock_1);
    with Cancelled:
        goto begin_transaction

Without any form of deadlock prevention, the processes would get stuck forever. Cancelling one of the processes (in a way that releases its locks) prevents that.

This form of deadlock prevention only works if processes are written in the expected way and can cope with cancellation. It does not generalize to arbitrary programs.


How to go from a recurrence relation to a final complexity

From what you wrote it seems that for all $k$ you have $T(k)=k-1+T(k-1)$ and $T(1)=0$. Therefore you can get it directly:

$$T(n)=(n-1)+(n-2)+\dots+1+0 = \sum_{k=1}^{n}{(k-1)}=\frac{n(n-1)}{2}$$

So $T(n)$ is in $Θ(n^2)$.


What are the differences between approximation of AIXI and deep reinforcement learning

It's a bit of an apples and oranges comparison. AIXI is a proposal for how generalized learning should be structured, while neural networks are a specific learning implementation.

That being said, you probably wouldn't want to use an AIXI implementation for a known task such as game AI. Game AI is a specific learning task, so it's better and easier to use an AI specifically tailored to that task. The AlphaGo AI, for example, combined a deep learning neural network for finding interesting looking moves with a positional analysis engine for figuring out the strength of those moves. That sort of architecture works great for learning to play Go, but it's not general.


Finite Automata -- Determine if a set is regular

Hint: Show that a word belongs to $A$ iff it starts at $0$ and contains at least one more $0$. That is, $A$ is accepted by the regular expression $01^*0(0+1)^*$.


Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit

I have proved that my algorithm works, so here's the algorithm, just to remind:

  Iterate over all the tasks ordered by increasing $e(i)$ and for each of them try performing it the earliest possible. If cannot, return false. If all tasks are added, return true.

And the proof follows:

Suppose the algorithm is not correct and there exist such data, that it returns false, while it is possible to perform a plan (mapping: task -> time) in which each task is performed.

Now let's find the first task (chronologically), which is performed at different time in plan created by my algorithm (further called my plan) and the optimal plan.

Then, this task is performed earlier in my plan (because of how the algorithm works) and this is the task we must most hurry with (compared to the rest of tasks performed later in my plan) (because of the order of tasks list processed by the algorithm).

So, we can safely reschedule this task (call it $t$) (in optimal plan) to the time when it is performed in my plan.

If this rescheduling bears any conflict with another task (call it $t'$) in the optimal plan, we can also safely move $t'$ to the time of, when $t$ was performed originally in the optimal plan (because $e(t) < e(t')$).

So we see that we can safely rearrange the optimal plan, so it becomes my plan. Hence my plan is optimal and the algorithm works.


Does my solution converge to O(N) for worst-case time complexity?

$ \sum_{i=1}^n \frac{i}{n} $ is the harmonic sequence, which goes to $\log(n)$

since in your question you claim the $T =\frac{n}{2} \sum_{i=1}^n \frac{i}{n}$

$T = \frac{n}{2} \log(n) = O(n\log(n))$


How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?

First, separate the set of variables $I = \{1,\dots,n\}$ according to their values:

$\qquad\begin{align}
  I_+ &= \{ i \mid X_i = 1\} \text{ and} \\
  I_- &= \{ i \mid X_i = 0\} \;.
\end{align}$

Let $n_+ = |I_+|$ and $n_- = |I_-|$.

Given $X_1, \dots, X_n$ and $k$, it is clear that we have to choose $k$ indices from $I_+$ and arbitrarily many from $I_-$. That means we will have to output

$\qquad \binom{n_+}{k} \cdot 2^{n_-}$

solutions. Note that if we assume $\binom{a}{b} = 0$ for $b<0$ and $b>a$, this extends nicely to inputs that allow no solution.

Generating all valid solutions in a list can be done by two nested recursions: the outer creates all $k$-subsets of $I_+$, the inner all subsets of $I_-$. This way, no illegal solutions are investigated, which is as efficient as you can expect (up to list operations).

  outer(I+, 0, I-) = inner(I-)
| outer(I+, k, I-) =
    result = []
    foreach ( i in I+ ) {
      suffices = outer(I+ - i, k-1, I-)
      result ++= (suffices map { [i] ++ _ })
    }
    return result

  inner([])      = []
  inner(x::rest) =
    smaller = inner(rest);
    return smaller ++ (smaller map { [x] ++ _ })

If you want an iterator, note that you can replace recursion with stacks (which allows you to compute it step by step) and emit solutions in the innermost call of inner. Of course, you'll have to reverse the way solutions are constructed (while descending, as opposed to during ascension as I did above).


How to check rapidly if an element is present in a large set of data

If you knew that every article had a DOI, you could just store a hashtable of the DOIs of the papers that you've already harvested.  Of course, in practice, many papers don't have a DOI or don't list their DOI.

If you knew that the paper would be listed with the correct title and authors, you could use a hash of the titles and authors and store that in a hashtable.  Of course, in practice it is common for titles to be mis-spelled, or for there to be variations in how they are listed (e.g., changes in capitalization; do you list the full first name of each author or just their first initial; and so on and so on).

If you knew the list of all variations, you could try to canonicalize the title and authors (e.g., lowercase the title, use only the last names of the authors, and so on).  Of course, in practice we probably can't know all the variations.

If you figured that all variations would be at small edit distance, you could use fuzzy matching and some kind of database that allows approximate match lookups.  (e.g., Efficient map data structure supporting approximate lookup, How fast can we identifiy almost-duplicates in a list of strings?, How to compare/cluster millions of strings?)  However, I suspect that in practice edit distance might not be enough to find all matches.  Also, there is a risk that you might end up conflating two different papers (for instance, I have seen a series of papers with titles like "Catching the Bugblatter, Part I" and "Catching the Bugblatter, Part II" with the same authors).

Hopefully all of this is conveying that in practice I suspect the problem is messy and there is no single clean answer.  Perhaps a pragmatic solution is to use some of the above techniques to find obvious matches, with the idea that this will take care of most cases of matches.  For the remainder, just accept that you might store the article multiple times, but hopefully this won't be too common.  Ultimately, storage space is extremely cheap, so storing the same article a few times probably isn't so bad.


Machine Learning vs System Identification?

System identification is the science of constructing dynamical models from observed data. There are two main approaches: Prediction Error Identification (PEI) and Subspace Identification (SID). Both of them are delivering a so called parametric model, that is to say, a model of a fixed structure. Usually it is the case that the user selects the structure of the underlying system (especially in the PEI methods) or at least the order of the system (in both methods). Even though it is not necessary, a low order system is sought (that is to say, the number of the basis coefficients is relatively small) because it is often used for control purposes, so we have to keep it as simple as possible to avoid computational issues etc. This model can be used to make predictions about the future behaviour of the system given some inputs.

On the other hand, machine learning (ML) has two main branches, classification  and regression algorithms. The latter ones are also used for prediction purposes. Two of the most famous approaches in machine learning are Support Vector Machines (SVM) and Gaussian processes (GP). The main difference with the system identification techniques is that the ML techniques are delivering a non-parametric model. The latter means that the prediction for a new input is given as a function of the data points used for the "training" (learning, identification) of the model. Therefore, if we used N=1000 data points for the training, then the prediction would be expressed as a function of these data points. ML methods are more flexible since they don't require any structure selection from the user, but they face other limitations (e.g. computational effort).

Until recently the ML and the system identification techniques were developing independently. But in the latter years there is a great effort to establish a common ground (e.g. see the paper "Four encounters with system identification" from Ljung)


As Lukas points out, having multiple initial states is something of a red herring. You've defined your automaton to accept a subset of the strings that match the regular expression $Q\Sigma^*$ and that regular expression matches the language accepted by some ordinary DFA using the usual techniques. (Lukas gives an explicit construction in terms of the original automaton.)

For equivalence, there is a standard polynomial-time technique used for state minimization for DFAs. Luca Trevisan has a good set of notes (PDF) on this, which I'll briefly summarize.  Let the automaton have state set $Q$, alphabet $\Sigma$ and transition function $\delta$.

For a state $q$ and string $w$, write $\delta^*(q,w)$ for the state that you reach by starting at $q$ and reading $w$.  For states $p$ and $q$, write $p\equiv q$ to mean that $\delta^*(p,w)$ and $\delta^*(q,w)$ are either both accepting or both rejecting. This gives the same relation $\equiv$ that you give in the question.  We'll show how to compute $\equiv$.

To do this, for any $n\geq 0$, define $p\equiv_n q$ in the same way as $p\equiv q$, except restricting $w$ to be of length at most $n$.  We'll compute the relations $\equiv_n$ inductively, and show that knowing a finite number of them is the same as knowing $\equiv$.

First, note that $p\equiv_0 q$ if, and only if, $p$ and $q$ are both accepting or both rejecting so we can compute $\equiv_0$ easily.  Now, suppose we've already computed $\equiv_n$.  We claim that $p\equiv_{n+1}q$ if, and only if, $p\equiv_n q$ and $\delta(p,u)\equiv_n\delta(q,u)$ for all $u\in\Sigma$. Obviously, if $p$ and $q$ "agree" on all strings of length at most $n+1$, they must also agree on all strings of length at most $n$. For the second part, consider a string $uw$ where $|u|=1$ and $|w|=n$. We're saying that, for $p$ and $q$ to agree on $uw$, it must be that, after reading $u$, they move to states that agree on $w$.

This allows us to construct the relations $\equiv_n$ for all $n$.  Finally, we claim that $\equiv_{|Q|}$ is actually the same relation as $\equiv$.  To see this, observe that every $\equiv_n$ is an equivalence relation and, furthermore, the procedure from moving from $\equiv_n$ to $\equiv_{n+1}$ can only split equivalence classes into smaller ones: it can never merge them. Also, if $\equiv_n$ and $\equiv_{n+1}$ are the same relation, then $\equiv_{n+i}$ is the same relation for all $i\geq 0$.  $\equiv_0$ has at most two equivalence classes.  Every step of the process either splits at least one equivalence class or is the end of the game: it doesn't split any class and nor does any future step. We can't split classes more than $|Q|$ times because, if we did, we'd have more equivalence classes than states, which is impossible. So it must be that $\equiv_{|Q|}$ is the same thing as $\equiv$ and we're done.


How can I show context free grammars are strictly more expressive than regular expressions with an example?

The canonical example is the language $L=\{a^nb^n\mid n\ge 0\}$. It's easy to produce a CFG for this and it's nearly as easy to show that it's not a regular language. For your first question, note that any regular language can be generated by a left-linear grammar and these are CFGs, so any regular language is also context-free.


Was multiple inheritance ever implemented by adding redundant data members?

It does not matter how you implement multiple inheritance, the inherent issues coming from that still apply.

If $C$ is a class, and $D$ a derived class (subclass), and $d:D$ we can write d.foo() to call a method that can be defined in $D$ (possibly ovverriding $C$'s own method) or the method which is inherited from $C$ (and not overridden). In any case, there a clear choice on which one should be called.

If instead $D$ derives from $C_1,C_2$ then that method might be inherited from both and we need to disambiguate somehow. For instance, d.foo() could be an error now, and we could require something like d.C1::foo() instead. Or we could give priority to the "first" superclass. Or we could require that the definition of $D$ must resolve the ambiguity (e.g. an overridden method is now mandatory). None of this is an ideal solution. Liskov substitution principle for $C_2$ is likely broken by any of these options.

Using composition instead of inheritance, things hardly change. We still need to disambiguate. We can use d.field_c1.foo() instead. We can make $D$ to define a foo() method that chooses according to the wanted priority. We also have the additional option of making $D$ not expose the foo() method at all, but this means that $D$ can no longer be considered a subtype of $C_1,C_2$, not even in some lax sense.

More pragmatically, after decades of being almost dogmatic about OOP, the software engineering community is now coming to a more honest evaluation of it, trying to highlight the advantages without hiding the issues. Inheritance is now still found interesting and useful, but much less so.


As I understand the process, altering a perceptron without retraining is impossible. The weight adjustments are not only relative to that specific example but also relative to the other training examples that have gone before.  Identifying the incorrectly classified instance and removing it from the test set before retraining the model would seem to be the most effective way of correcting the weights.

I think it's worth pointing out that in comparison to other machine learning algorithms, perceptrons are relatively resistent to noise and incorrectly classified instances in the training set.  If you're encountering a large number of misclassified instances, it would seem more prudent to have better validation at the point you ingest the data prior to training than to come up with some way to correct for misclassified instances after the perceptron has been trained.  If that's not possible and you're able to identify the incorrectly classified instances as such, then removing them and retraining would seem the only way to effectively remove the impact of the misclassified instances.


You might start from an initial solution computed using one of your two models, and then apply local search: consider any movement of one set from a group to another, and apply it if it does not violate the group constraints and it improves $\Phi$.

Local search is a common approach in graph partitioning, thus it is probably already a part of what KaHIP is doing, but even if it is, you would now do it with the correct measure, $\Phi$, not its surrogate, so the outcome is likely to be improved.


What do you call a data structure containing multiple lists?

If you don't care about the order of elements (e.g. you can deal with sets instead of lists) then the union-find structure gives an (amortized) constant time union operation.
There's also the unrolled linked list but the idea is to unroll a list for better cache performance rather than better performance when concatenating lists. For this reason, the number of elements at each node is generally bounded.
I don't think the data structure you describe has a name. It will act like a linked list in the worst case e.g. O(1) to add at the front/back and O(n) to search but you get the added bonus of O(1) concatenation that would be O(k) (for k new elements) with linked lists.
If that's all you're doing with your list then there doesn't seem to be any need to rearrange your list at any point e.g. by coalescing or splitting up nodes.
Update: An example of a specific data structure that seems to behave in the way you want is the Quicklist in Redis. It is described as a 'linked list of ziplists' where a ziplist is a contiguous bit of memory.


Blockchain cipher suitable for preschoolers

I'd suggest you don't try to create or use a cipher.  Rather, I think maybe a more interesting way to view blockchain systems is as a log that is created through a distributed lottery.

So, in lesson one, you could describe how to keep track of something (account balances?  something more relevant?) via a sequence of log entries written on the board.  This would be a centralized scheme.

In lesson two, you can make it distributed.  In each stage, have a lottery where you randomly pick one of the students to win the lottery.  The winner of the lottery gets to write down the next log entry on the board.  Everyone else watching can see whether that student did it correctly and fairly.  If not, the next winner ignores the bogus stuff written on the board.

No cryptography is needed.  You just need a way to randomly pick one student in the room, in a fair way.  This could be done with numbered balls in a box, or any number of other ways.


Does "$\forall x\in L, \sigma(\neg x)=\neg \sigma(x)$" hold given that $\sigma(F)\equiv F$ for a CNF formula $F$ built on a set $L$ of literals?

No.  Suppose $F$ is the formula

$$(x_1 \lor x_2) \land (\neg x_1 \lor x_2) \land (x_1 \lor \neg x_2) \land (\neg x_1 \lor \neg x_2) \land (x_1 \lor \neg x_1) \land (x_2 \lor \neg x_2),$$

and consider the permutation $\sigma$ such that $\sigma(x_1)=x_2$, $\sigma(x_2)=\neg x_1$, $\sigma(\neg x_1)=x_1$, and $\sigma(\neg x_2)=\neg x_2$.

Then $\sigma(F) \equiv F$, but $\sigma(\neg x_1) \ne \neg \sigma(x_1)$.


Floating point format: why must `1−emax ≤ q+p−1 ≤ emax`?

The reason we get a larger range is denormalized numbers. Generally speaking, floating point numbers have three physical parts: sign (1 bit), mantissa $M$ and exponent $e$. Most of the time we think of the number as $\operatorname{sgn} \times 1.M \times 2^{e-e_0}$, where $e_0 = 2^{|e|}-1$ (e.g. for single precision, it's 127, since the exponent is allotted seven bits). Here "$1.M$" means the number you obtain by writing $M$ as a binary string and prefixing $1.$.

For reasons having to do with underflow (non-zero numbers turning to zero), it is important to be able to store numbers very close to zero. These numbers, named denormalized numbers or subnormalized numbers, have $e = 0$ and represent $\operatorname{sgn} \times 0.M \times 2^{1-e_0}$. (This means that normal numbers cannot have $e = 0$.) This explains the extended range mentioned in the Wikipedia page.

Other numbers having special encodings are $\pm \infty$ and NaN (not a number), which represent some illegal operation (division by zero, taking the logarithm of a non-positive number, taking the square root of a negative number, and so on). For more details, consult the Wikipedia page regarding the original standard.


What is a continuous environment for an agent?

Continuous has its usual definition: a variable that "looks like the real numbers" in the sense that, for any value $x$ that the variable could take and any positive constant $\delta$, there's another value $y$ that the variable could take that's within distance $\delta$ of $x$.  So, for example, the environment of your physician expert system will include things like the patient's temperature and blood pressure, which are both continuous, but it will also include discrete things such as what medicines they're currently taking and substances they're allergic to.  There are also awkward cases such as how much pain they feel, which you might imagine to be continuous but is typically expressed on a discrete scale of 0 to 10.  (I guess it's on a discrete scale partly because it's completely subjective and partly because nobody could distinguish between 3.298364 and 3.298365.)

However, note that your agent is most likely running on a digital computer. Because of this, any inputs it receives will have been rounded to some level of precision, making everything discrete in the end.


Disjoint Set Connected Components With Weighted Graph

Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.

Here's a resource to start off with:- Disjoint Set Union

for edge in edges:
    if find_set(edge[0], node_map) != find_set(edge[1], node_map):
        unioned_set = union(edge[0], edge[1], node_map, sets_map)
        cost_map[edge[2]] = unioned_set.count - 1

cost_map[edge[2]] will not be equal to the size of resultant set after union - 1.

It will be equal to the product of size of two individual sets.

Over here,

for i in xrange(1, largest_cost+1):
    val = cost_map.get(i, 0)
    prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

largest_cost can be >10^9. Neither can you store an array of that size, nor can you execute a loop with 10^9 operations with a time limit of 1sec.

Try using binary search on the L R query.

If you implement disjoint union set with arrays and make the above corrections , then I believe the code should work.


Is it possible to convert all logical formulae into a form such that each variable ends up in exactly 1 "factor" of the and operation? ($\land$)

In general, it is impossible to separate variables in that way. Consider the formula $a \leftrightarrow b$, and assume it can be written in the form $f(a) \land g(b)$.

Up to logical equivalence, $f(a)$ must be either $a$ or $\lnot a$. Ditto for $g(b)$. We therefore have that $f(a) \land g(b)$ must be one of these formulas:

$$
a\land b \qquad
a\land \lnot b \qquad
\lnot a\land b \qquad
\lnot a\land \lnot b \qquad
$$

However, none of the above ones is equivalent to $a \leftrightarrow b$.

(Well, to be pedantic, $f(a)$ and $g(b)$ could also be the constantly true or constantly false function. Those choices won't work either, obviously.)


If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

In this particular example, the following works:
Let $A$ be the algorithm for deciding whether some graph $G$ has a TSP-route has a cost of at most $b$.
We start by finding the optimal $b^\ast$ using $A$ and binary search on an appropriate range (say $[0, \sum_{e \in E(G)} w(e)]$) in polynomial time.
Following this, we start modifying the instance graph $G$ by setting edge weights to some large value so they will never be picked (e.g. $1 + b^\ast$) in a route of optimal cost $b^\ast$ and using $A$, we check whether the resulting graph still has a route of cost $b^\ast$.
If that is the case, we keep the modification and otherwise we undo it.
However, we now know that any such route (in the modified graph) must include the edge we messed with, so we store that.
Successively applying this to all edges we will find at least one such edge per pass over $E(G)$ and after at most $|V(G)|$ passes, we will have found a TSP-route of cost $b^\ast$ consisting of the edges we stored.
Hence we call $A$ an polynomial ($O(|V(G)| \cdot |E(G)|)$, or if you want $O(|V(G)|^3$) amount of times (in the second step, the first one also takes polynomially many) and all of our other operations can also be easily done in polynomial time.
Therefore, we can solve the optimization problem in polynomial time if we have a polynomial-time algorithm for the decision variant.
This approach also works for other problems (with slight variations for the second part); in fact I am not aware of a problem where this general strategy fails. I am actually pretty sure that one can use it to recover an accepting path of a polynomially-bounded NTM which can then be used to solve optimization variants of all $\mathsf{NP}$-complete problems.


This is not "enough proof". The main problem of your proof is that it just lacks words. A proof should explain what you have in your head. So the first thing is to clearly states what you want to prove.

  We want to prove that $n^2$ is not $O(\log n)$.

Then you have to explain how you will do it:

  Assume toward a contradiction that $n^2=O(\log(n))$.

So you are going to do derive a contradiction from this assumption. We just apply definitions.

  By definition, it means that there exists $c, n_0$ such that for every $n \geq n_0$, $n^2 < c \log n$, that is, ${n^2 \over \log n} < c$.

Now you need to explain why this is absurd. There are many ways of doing it depending on what you assume the reader to be familiar with. One way to go is the following:

  It is well known that $\lim_{n \rightarrow \infty}{n^2 \over \log n} = \infty$. Thus, there exists $n_1 \geq n_0$ such that ${n_1^2 \over \log n_1} \geq c$, contradicting the initial assumption.

Now, you conclude:

  Thus, $n^2$ is not $O(\log n)$.

If you think your reader is not familiar enough with limits you can then go more into details:

  We know that for every $n \in \mathbb{N}$, $\log(n) \leq n$. Tus, $n = {n^2 \over n} \leq {n^2 \over \log n}$. Thus, $n_1 = \max(n_0,c)$ verifies both $n_1 \geq n_0$ and $c \leq n_1 \leq {n_1^2 \over \log n_1}$ which contradicts the intial hypothesis.


Why is particular token missing in LALR lookahead set?

In state 0, R ::= ⋅L can only be generated by S ::= ⋅R. In L ::= ⋅* R, the dot precedes *, not R, so no further items are generated by it.

The dragon book uses this grammar as an example of the inadequacy of SLR, and the correct computation of the lookahead in this case is an instance; the SLR algorithm bases lookahead decisions on the FOLLOW set rather than actual lookahead possibilities in the state, which will eventually lead to a shift/reduce conflict on lookahead symbol =.


Parsing arbitrary context-free grammars, mostly short snippets

Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.

The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not LL(1): it just tries out all possible LL(1) parses. It uses a directed graph for every point in the parse, which means that if a parse state is encountered that has been dealt with before, it simply merges these two vertices. This makes it suitable for even left-recursive grammars, unlike LL. For exact details on its inner workings, read the paper (it's quite a readable paper, though the label soup requires some perseverance).

The algorithm has a number of clear advantages relevant to your needs over the other general parsing algorithms (that I know of). Firstly, implementation is very easy: I think only Earley is easier to implement. Secondly, performance is quite good: in fact, it becomes just as fast as LL(1) on grammars that are LL(1). Thirdly, recovering the parse is quite easy, and checking whether there is more than one possible parse is as well.

The main advantage GLL has is that it is based on LL(1) and is therefore very easy to understand and debug, when implementing, when designing grammars as well as when parsing inputs. Furthermore, it also makes error handling easier: you know exactly where possible parses stranded and how they might have continued. You can easily give the possible parses at the point of the error and, say, the last 3 points where parses stranded. You might instead opt to try to recover from the error, and mark the production that the parse that got the furthest was working on as 'complete' for that parse, and see if parsing can continue after that (say someone forgot a parenthesis). You could even do that for, say, the 5 parses that got the furthest.

The only downside to the algorithm is that it's new, which means there are no well-established implementations readily available. This may not be a problem to you - I've implemented the algorithm myself, and it was quite easy to do.


It depends on the problems. Just knowing that $A$ and $B$ are in $NP$ doesn't tell you whether $A$ is reducible to $B$.

If $B$ is in $P$ and $A$ is $NP$-complete, then $A$ cannot be reduced to $B$ (unless $P=NP$).

If $A$ is in $P$ then it can be reduced to any problem $B$ except $\emptyset$ and $\Sigma^*$.

If $B$ is $NP$-complete then any problem (in $NP$) can be reduced to it.


Can a processor without stack pointer registers, have a subroutine calls and interrupts?

The Control Data Cyber series had no stack pointer, but it had a Pascal compiler. Seymour Cray says your book is wrong. (The Subroutine Call instruction that this computer isn’t supposed to have would store the return address into the location after the instruction it branched to, forming an instruction that could be used to jump back to the caller). If your instructor doesn’t know who Seymour Cray is then they shouldn’t be teaching.

And there were microprocessors that handled interrupts by switching to a second set of registers. So the answer would be 4.


How is the R-Tree's MBR size determined? Changes to MBR?

First of all, let us have some background. There are variants of Guttman's r-tree that have different splitting heuristics (e.g. Sellis' r+-tree, which involves inserting an item multiple times into a tree; and Beckmann's r*-tree, which takes into account area, margin, overlap). Also, there are variants that are more suitable for higher dimensions (e.g. Berchtold's x-tree, which uses split history and supernodes). You can improve any of the above structures using bulk loading, which can guarantee zero overlap between rectangles at the same level.

Rectangles used typically are minimum bounding rectangles (MBR's) that may fit your data well (if you are using orthonormal rectangles as with data mining), or may have to be used as approximations (if you are trying to detect intersections between polytopes).

You can find MBR's, which are possibly described using upper-left point and lower-right point, by taking extreme value pairs for each dimension.

Note also that points are degenerate rectangles and that we can form MBR's for collections of MBR's.

For example, if we had $P$ = $\{(1, 0), (2, 1), (3, 2), (4, 3)\}$, and right is large $x$ and up is large $y$, an MBR for these points could be $(p_\text{upper-left}, p_\text{lower-right})$ = $((1, 3), (4, 0))$.

There have been attempts to quantify how much time a query on an r-tree takes, but intuitively what is happening is that we may spend more than $O(k \cdot \log(n))$ time for $k$ matches, even though depth is $O(\log(n))$, because we could go down many branches without reaching a match. If you are interested, there are certain operations one could perform on an r-tree that take more time but have clean running time asymptotic values if you include a "look-ahead" query at each node we visit. In the end, however, with a regular r-tree and with regular queries, loosening the MBR's leads to diminished performance.


How can I prove that a cryptography algorithm is a pseudo-random number generator?

We don't know how to prove that a cryptographic PRNG exists. There are some candidate constructions, but they have not been proved to work. There are some results of the form "if X exists then so does a cryptographic PRNG", where X is some other cryptographic primitive, and the PRNG can be constructed explicitly from X. However, none of these other cryptographic primitives are known to exist. A particularly intriguing open question is to construct such a primitive which works merely under the assumption that P differs from NP.

On the other hand, proving that a generator is not a PRNG is much easier.  You just need to give a distinguisher which has a non-negligible advantage in comparing the output of the generator to truly random output (as in the definition of a cryptographic PRNG).


Decidable language that has no finite description?

Unless you want to be more rigid in what you allow as a "description", every decidable language has a finite description - precisely the Turing machine that decides it. This Turing machine must exist (otherwise the language would not be decidable).
Although we often thing of automata as machines that do work, mathematically they're just a way of, in a certain sense, compressing the table that says "yes" or "no" for every string (over the given alphabet).


How powerful are DFA with recursive calls?

Recursion is implemented on a computer using a stack, and your case is no different. You can use a stack to emulate the "call-and-return" semantics of your DFA with recursive calls, and the results will be a DPDA.


On computing the factor-free basis of a regular language

A language $L$ is infix-free if
$$ L \cap (\Sigma^+L\Sigma^* \cup \Sigma^*L\Sigma^+) = \emptyset. $$
(This deep observation, which I made independently, appears in reference [1] to the paper you cite.) This gives a simple algorithm for deciding whether a regular language $L$ (given as a DFA, NFA, or regular expression) is infix-free.

Similarly, the basis of $L$ is
$$ L \setminus (\Sigma^+L\Sigma^* \cup \Sigma^*L\Sigma^+). $$
This gives a simple algorithm for computing the basis of a regular language (as a DFA, NFA, or regular expression).


Why do caches fetch data to the right if the offset bit is 0 and to the left if it is 1 in a 2-word block

The two-word blocks are always aligned, and you can find where they start by zeroing the LSB. So the two blocks are always of the form $x0,x1$. So if you fetch $x1$ you also fetch $x0$, and vice versa. This makes indexing the block easy, since to find what block a word belongs to, you just need to drop the LSB.


$(\log n)^{\log n}$ lower-bound and upper-bound

Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.


Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?

Yes, there's a nice algorithm for this.  Compute the transitive reduction, then check whether the result is planar.

Why does this work?  The transitive reduction is the graph with the smallest number of edges, that has the same reachability relationships as the original graph.  It is also unique.  Moreover, any other graph with the same reachability relationships must include all the edges in the transitive reduction (plus possibly some others).  Thus, if the transitive reduction isn't planar, no other graph with the same reachability relationship will be planar (as adding more edges to a non-planar graph can never make it planar).


How many words of memory map to the same cache entry?

The correct answer is M/C. This question is on the Computer science Major Field Assessment Test. https://www.ets.org/Media/Tests/MFT/pdf/mft_samp_questions_compsci.pdf


Are functions in O(n) that are nor in o(n) all in Θ(n)?

Tell the lecturer they're wrong. Take the function
$$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$
This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.

Here is a monotone example, which might be more convincing:
$$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$


Class of the language of Turing machines that loop on at least one input

The language $L$ consists of (descriptions of) Turing machines $M$ such that $M$ does not halt on all inputs. In other words, $\langle M \rangle \notin L$ if $M$ halts on all inputs. Can you think of any connection to the halting problem?


How would you identify the size of a circular turing tape?

This answer was inspired by YuvalFilums's comment.

I will denote values in the cells with $t$ and $f$ and locations on the tape with $0, 1, 2, \dots$ to avoid confusion.

First, check that the length $\neq 1$. To do this, set the cell under the counter to $f$. Then, move right $1$ cell and set that cell to $t$, and return to $0$, checking if that is $t$. If so you have your answer, otherwise move to $2$ and set that to $f$, and return to $0$.

Second, check that the length $\neq 2$ similarly.

Then repeat the following procedure indefinitely:

Move right until encountering an $f$. Set this to $t$.
Move right one cell and set it to $f$.
Return to $0$. If it is $t$, find the first $f$ after $1$, and move left one cell. This is your answer. Otherwise, repeat.


Is there any good way to judge whether the rectangle is inside the point cloud?

The point cloud can define a polygon.
After you define a polygon you can use the point inside polygon test on the four corners of the rectangle and see if all the points are inside the polygon.

The point in polygon test.


Two grammars $G_1 = \langle \Sigma, V_1, S_1, P_1 \rangle$ and $G_2 = \langle \Sigma, V_2, S_2, P_2 \rangle$ are

weakly equivalent if $L(G_1) = L_(G_2)$
strongly equivalent if $L(G_1) = L_(G_2)$ and for every string $w$ in the language, the minimal left-most derivations of $w$ in $G_1$ and the minimal left-most derivations of $w$ in $G_2$ are exactly the same in number, and can be put in one-to-one corresponce (note that the number of derivation trees must be the same in number if the grammars are ambiguous, i.e. they must be ambiguous "in the same way")

Example:

$G_1 = S \to A; A \to 1B; A\to 1; B\to 0A$; we have $L(G_1) = \{ (10)^*1 \}$

$G_2 = S \to B; B \to A1; B\to 1; A\to B0$; we have $L(G_2) = \{ 1(01)^* \}$

isomorphic if there is a bijection $\phi : V_1 \to V_2$ such that $\phi(S_1) = S_2$ and $\phi(P_1) = P_2$ (after extending $\phi$ to productions and set of productions in the natural way).

Note that weakly equivalence is undecidable, while strongly equivalence (and ismorphism) are decidable.

As a final remark I think that - in most formal language contexts - it would be fine to say that the grammars in your question are the same grammar :-)


Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

Assuming $T(1)=1$, you can show by induction that $T(n) = \frac{n(n-1)}{2} + 1$.

The base case is trivial since $T(1) = 1 = \frac{1 \cdot 0}{2} + 1$.

As for the inductive step, suppose that the claim holds up to $T(n)$.
$\begin{align*}
T(n+1) &= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n  \\
 &= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\
&= \frac{(n+1)((n+1) - 1)}{2} + 1.
\end{align*}
$


what will be space complexity for snippet for(i=1 to n) int x=10;?

You are right. Are they saying if we run that loop n times then n different variables having name x will be created? This doesn't happen. Moreover, it is good practice to avoid unnecessary global variables. To check this yourself, you can try printing the logical address of x using this:-
for(i=0;i<10;i++)
   {
       int x=1;
       printf("%d\n",&x);
   }

The same logical address gets printed every time. So yes, the total space used by this is not dependent on n. It is O(1).
By the way, You could have thought that x gets destroyed only once at the end of last iteration and meanwhile all the values a[i] would be getting overwritten on the same x in each iteration. Even this is not what happens. x gets destroyed after each iteration and the space is made available for use by other parts.


There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.

  Let r,s-SAT denote the class of instances with exactly r variables per
  clause and at most s occurrences per variable.

  [...]

  Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable.

  [...]

  Theorem 2.4. Every instance of r,r-SAT is satisfiable.

The reason there's no conflict is that you need to allow 2 or 3 literals per clause to make 3-SAT $NP$-complete when restricted to at most 3 occurrences per variable. The trivially satisfiable bit only kicks in when you have exactly 3 literals per clause and at most 3 occurrences per variable.


Leftist heap - determining time complexity

For the time complexity of merging, JeffE already pointed out in the comments that $O(\log(n_1n_2)) \in O(\log(n_1+n_2))$.

For arbitrary deletions note the following:

When we merge the two subtrees of the deleted node, the root of the resulting tree will have an s-value that is at least the s-value of the deleted node -1.
Thus, the s-value of any updated node will not be decreased by more than 1. (There is no constant bound for how much it can increase.)
Thus, if we update the s-value of a left child in and that value was strictly larger than the s-value of the right child, the s-values of the parent and all nodes above the parent will not change.
If the s-value of the left child and right child are equal, exchanging them still gives a valid leftist heap.
Thus, the number of updated nodes is bound by the length of a right flank in a leftist tree, which in turn is bound by $O(\log n)$.


How to find First in a left recursive grammar?

Here is how to apply the production rule $ A\to AX$ to compute $\text{first}(A)$.

  When $\epsilon\in\text{first}(A)$, add all (non-$\epsilon$) members of $\text{first}(X)$ to $A$.

More generally, if there is a rule $A\to AX_1X_2\cdots X_n$,

  When $\epsilon\in\text{first}(A)$, add all non-$\epsilon$ members of $\text{first}(X_1)$ to $A$. When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X_1)$, add all non-$\epsilon$ members of $\text{first}(X_2)$ to $A$.
  When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X_1), \text{first}(X_2)$, add all non-$\epsilon$ members of $\text{first}(X_3)$ to $A$, and so on.

The rules above are just specializations of the general rules. What is particular in this situation is that there is no effect when you add all members of $\text{first}(A)$ to $\text{first}(A)$. There is no concern about infinite recursion.

Here is a left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x$
$\quad Y \to y$
We compute as the following.

$\text{first}(X)=\{x\}$ by the rule $X\to x$.
$\text{first}(Y)=\{y\}$ by the rule $Y\to y$.
$\text{first}(S)=\{y\}$ by the rule $S\to Y$.
Since $\epsilon\not\in\text{first}(S)$, ignore rule $S\to SX$.

Here is another left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x \mid \epsilon$
$\quad Y \to y \mid \epsilon$
We compute as the following.

$\text{first}(X)=\{\epsilon, x\}$ by the rules $X\to x \mid \epsilon$.
$\text{first}(Y)=\{\epsilon, y\}$ by the rules $Y\to y\mid\epsilon$.
add $\epsilon, y$ to $\text{first}(S)$ by the rule $S\to Y$.
Since $\epsilon\in\text{first}(S)$, add $x$ to $\text{first}(S)$ by the rule $S\to SX$. So $\text{first}(S)=\{\epsilon, x, y\}$

Exercise. Compute the first set of the following grammar.
$\quad E\to E - T \mid T$
$\quad T\to T * F \mid F$
$\quad F\to (\ E\ ) \mid I$


Is the language $\{a^n b^m : 1000|nm \}$ regular?

Notice that $1000 = 2^3 5^3$. Then $1000 | nm$ iff for some $0 \le i,j \le 3$,
$n$ is multiple of $2^i 5^j$ and $m$ is a multiple of $2^{3-i} 5^{3-j}$ (notice that there are only finitely many choices for $i$ and $j$).
Then $L$ can be obtained as the union of the languages $L_{i,j} = \{a^n b^m : 2^i 5^j|n \;\mbox{ and }\; 2^{3-i} 5^{3-j}|m\}$.
Each of these languages  $L_{i,j}$ is the concatenation of $L'_{i,j} = \{ a^n : 2^i 5^j|n\}$ with $L''_{i,j} = \{b^m : 2^{3-i}5^{3-j}|m\}$.
It is easy to see that each $L'_{i,j}$ and each $L''_{i,j}$ is regular. By the closure properties of regular languages $L$ is regular.


Meyniel's theorem + finding a Hamiltonian path for a specific graph family

It is enough to prove your claim for the case of a tournament, in which for every pair of vertices $v\neq w$, exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.


Algorithm for approximation with sum or difference of 2 unit fractions

Here's a method that gets close. Do a continued fraction expansion of $\frac{m}{n}$:

$$\frac{m}{n} = \frac{1}{a + \frac{1}{b + \epsilon}} \approx \frac{1}{a + \frac{1}{b}} = \frac{1}{a} - \frac{1}{a(1 + ba)}$$

If $\epsilon$ is small, then this is probably very close to optimal if not optimal in most cases.

The method fails when the truncated continued fraction approximation isn't very good. Take $\frac{15403}{26685}$ (a rational approximation to the Euler-Mascheroni constant) as an example. The continued fraction approximation is:

$$\frac{15403}{26685} = \frac{1}{1 + \frac{1}{1 + \epsilon}}$$

Which suggests:

$$\frac{15403}{26685} \approx \frac{1}{1} - \frac{1}{2}$$

But clearly $\frac{1}{2} + \frac{1}{14}$ is closer.

I would wager that the worst case for any method is the conjugate golden ratio $\phi' = \frac{\sqrt{5} - 1}{2}$. This isn't rational (in fact it's the "most" irrational number in a technical sense; find its continued fraction expansion if you're curious), but you can get arbitrarily close by choosing $m$ and $n$ to be consecutive Fibonacci numbers, e.g. $\frac{4181}{6765}$. The best approximation I could find is $\frac{1}{2} + \frac{1}{9}$.


What algorithm to use for this subset sum problem

You can implement the dynamic programming algorithm using a much smaller amount of memory. You don't need the entire table in memory all the time.

The point is that to answer the question "Is there a set of items $1,\ldots,i$ that sums to $s$?", you only need the answers for $i-1$ (the previous "row" in the DP table), but you don't care about the (previously computed) answers for $i-2,i-3,\ldots$. Thus, at any given time, you'd only need an two arrays of around 120MB each in memory (and in fact, you can do it using only one array!).

However, reconstructing the solution becomes more difficult, since traditionally you'd reconstruct the solution by backtracking through all of the stored values. There's a nice workaround: with each (feasible) subproblem, store how much of the weight is taken up by the first $n/2$ elements.

We can do this computation in time $O(ns)$ (where $s$ is the sum of all elements). From the final row of the dynamic programming table, we can now find not only whether the problem has a solution at all, but also (if a solution exists), what portion of the target sum is achieved by the first $n/2$ elements (and consequently, we also know what portion of the sum the remaining elements make up). We can now solve the two subproblems recursively, each of half size. The total time taken is only $O(ns \log n)$, i.e., we only take a factor $O(\log n)$ hit in the running time for a linear reduction in memory usage.

You should also consider the possibility that perhaps not all possible values can be attained as sum of items in your set. So, depending on the input, perhaps not using a contiguous array of bits, but using instead for example a hash table will use less memory.

Finally (as an alternative solution), if you only need an approximation, consider rounding the values (e.g. to the nearest thousand) to reduce the size of the tables further.


Finding any path between nodes of implicit, finite, regular, undirected graph

The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.


Has the notion of "non-cheating" quines been formalised?

Most formal semantics for programing languages tend to keep things simple, in particular, it's pretty rare to have the ability to express "grabbing your own source code" in a formal semantics.

This has the somewhat dubious advantage of disallowing some kinds of "cheating" by construction: the "cheat" is simply not part of the language semantics. In particular, a simple lambda calculus with simple string concatenation and printing primitives cannot implement many (any?) of the "cheats" you have in mind. In such a language, a quine might be a program which prints the exact string representation of it's own code. You can even avoid the print primitive if you allow returning the string rather than printing it. In that case, you only need string literals and concatenation.

It's a useful exercise to figure out various properties of quines in such a language. It's pretty easy to see that some variable will need to be repeated twice: there are no "linear" quines. However the statement

  This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part.

is a bit vague, and I'm not sure it's true in general, depending on the precise meaning of "copied verbatim".


Relation with the perfect partition problem and the single machine task schedule problem

Just let $d_i=x_i$, $a_1=\frac{\sum_{i=1}^n x_i}{2}-d_1$ and $b_1=\frac{\sum_{i=1}^n x_i}{2}$, and $a_i=0$ and $b_i=\sum_{i=1}x_i$ for other $i$'s. Then easy to see there is a solution for the original PPP instance iff there is a solution for this SMP instance.


Suppose that the path consists of edges $e_1,\ldots,e_\ell$. The following answer assumes that by "subpath" you mean a partition of $e_1,\ldots,e_\ell$ into intervals. Go over all possible values of $b_1,\ldots,b_{\ell-1} \in \{T,F\}$. If $b_i = T$ then the edge $e_i$ ends an interval. Otherwise it doesn't. Here is how this looks in your case, $\ell=4$:
$$
\begin{array}{ccc|c}
b_1 & b_2 & b_3 & \text{subpath} \\\hline
F & F & F & e_1e_2e_3e_4 \\
F & F & T & e_1e_2e_3;e_4 \\
F & T & F & e_1e_2;e_3e_4 \\
F & T & T & e_1e_2;e_3;e_4 \\
T & F & F & e_1;e_2e_3e_4 \\
T & F & T & e_1;e_2e_3;e_4 \\
T & T & F & e_1;e_2;e_3e_4 \\
T & T & T & e_1;e_2;e_3;e_4 \\
\end{array}
$$


What's the meaning of this service specification

That means:

For all natural numbers x and y,

if the value of variable x is greater than zero
then after the assignment statement "y := x*x" is executed
the predicate "y > x" will be true.


Standard problem sets for metaheuristics

are these any good to you?

Binary Welded Tree (BWT). To ﬁnd a labeled node in a
graph

BooleanFormula(BF). To evaluate a NAND formula

ClassNumber (CL). To approximate the class group of a real
quadratic numberﬁeld

GroundStateEstimation(GSE). To compute the ground state
energy level of a particular molecule

QuantumLinear Systems(QLS). To solve a linear system of
equations

UniqueShortest Vector (USV). To choose the shortest vector
among a given set

Triangle Finding(TF). To exhibit a triangle inside a dense
graph


Solve Recurrence for $T(n) = 7T(n/7) + n$

Here is what I get:
\begin{align}
T(n) &= n + 7T(n/7) \\ &= n + 7(n/7) + 7^2 T(n/7^2) \\ &= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3)
\end{align}
and so on. Each of the summands equals $n$, and there are $O(\log n)$ of them.


Push Down Automatons "guess" - what does that mean?

Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them.

Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a theoretical device, which can be used to simplify the presentation of certain concepts.

For the palindrome, you can think about it in two ways. Either there's a magical power that lets your machine say "this is the middle of the word, time to switch from pushing to popping", or after reading each letter, it says "I'm going to fork a new process which that this letter is the middle of the word, and see if it finds it's a palindrome. Then in this other thread, I'll keep trying, assuming this isn't the middle of the word".

Another way to think of it is as infinite parallelism. So an equivalent model would be that, instead of choosing a new path, it simultaneously tries both paths, branching off new "processes," succeeding if any are in a final state after reading the whole word. Again, this can't be built using real hardware, but can be modelled with non-determinism.

The interesting thing about nondeterminism is that for finite-automata and Turing machines, it doesn't increase their computational power at all, just their efficiency.


Is the union of a non-regular and a regular language regular?

There is no simple rule.

Consider the languages

$L_1 = \{ a^n b^n \mid n \geq 0\}$,
$L_2 = \{ b^n \mid n \geq 0 \}$, and
$L_3 = \{ a^n b^m \mid n,m \geq 0 \}$.

Clearly, $L_2$ and $L_3$ are regular while $L_1$ is not. Furthermore,

$L_1 \cup L_2$ is not regular but
$L_1 \cup L_3$ is.

Therefore, you will have to look more closely at the language at hand and maybe try to proof both claims. Our reference material can help you get started; feel free to post any specific questions about your attempts as new questions.


Yes.  To reduce the ordinary partition problem to this variant, just multiply each element by 3.  Now, the case where the weights of the two partitions differ by two cannot arise so, if the instance is a yes instance, it must be because there's an equal-weight partition.


Greedy algorithm for subset sum on powers of 2

You can prove the algorithm using induction. In order to prove by induction, your main statement would be: Let $s_n$ be the (correct) sign of $a_n$ (if it exists), then the algorithm trying to find $s^*_1,\dots,s^*_{n-1}$ such $\sum_{i=1}^{n-1} s^*_ia_i=num-s_na_n$ is correct (by induction assumption). Then, we only need to show that the algorithm chooses $s^*_n=s_n$ and then we would get $\sum_{i=1}^n s^*_ia_i=num-s_na_n+s^*_na_n=num$ as required.
Now the tricky part comes: how can we prove that the $s^*_n$ the algorithm chooses is indeed correct? We want to split this part into two cases:

$num\ge0$, and assume towards contradiction $s_n\neq 1$, i.e only $s_n=-1$ gives a valid solution (there may be multiple solutions, so beware of saying there is only one such $s_n$). Then we need to have $\sum_{i=1}^{n-1}s_ia_i = num+a_n$. Since we are dealing with only powers of $2$, and $a_n$ is the highest value, then there must be some values whose sum (when summed with the appropriate sign) is precisely $a_n$ (and this is because $a_n$ is also a power of 2, if you want a complete proof to this statement, think about the numbers as binary numbers with only one "1" in them and the rest are "0"s), now we can "flip" the sign of those values, and we would get $\sum_{i=1}^{n-1}=num-a_n$ (since their sum is $a_n$, the effect of flipping their sign is like subtructing $2a_n$) and then by choosing $s_n=+1$ we get $\sum_{i=1}^n s_ia_i=num$, in contradiction to our assumption.
$num < 0$, we get that $s^*_n=-1$, and by flipping all of the signs as well as the sign of $num$ we get $s^*_n=1$ for $num>0$, and notice this is the same as the first case.


Algorithm to find a line that divides the number of points equally

One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that direction. However, if you choose a "generic" direction then this won't happen (assuming that the points are distinct). Since there are linear time median algorithms, this is an $O(n)$ algorithm. Using the randomized quickselect algorithm, you get a practical linear time algorithm.


NP problems with exponentially complex average time solution?

We don't know.  It's possible that $P \ne NP$ but still all problems can be solved in subexponential time, as Yuval states.  The Exponential Time Hypothesis is a conjecture that a certain problem requires exponential time to solve, but it's a conjecture -- there's debate among researchers about whether we should expect it to hold or not.

Assuming the ETH, you can find problems that meet your requirements, at least for worst-case hardness: there is asymptotically almost surely a solution, and any deterministic algorithm must have worst-case running time that's exponential in the length of the input.  In particular, ETH implies that every problem in the class SNP takes exponential time to solve.  For instance, 3SAT would qualify.

It sounds like you really want average-case hardness.  There are some natural candidate problems: 3SAT with an appropriate clause density would be one reasonable one.

You could also use cryptographic hardness assumptions from the crypto community, e.g., inverting $f(k) = AES_k(0)$ probably takes exponential time yet is known to have a solution, as far as we can tell given our current state of knowledge.  This gives you a problem with a concrete parameter size, but with standard techniques you can build something asymptotic if you prefer an asymptotic family of problems.


$ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

The definitions are (as used commonly in Computer Science, all functions positive):

$f(n) = O(g(n))$ if there is $c_1 > 0$ such that for some $N_1$ whenever $n \ge N_1$ it is $f(n) \le c_1 g(n)$

$f(n) = \Omega(g(n))$ if there is $c_2 > 0$ such that for some $N_2$ whenever $n \ge N_2$ it is $f(n) \ge c_2 g(n)$

$f(n) = \Theta(g(n))$ if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

Note that the values of $N_i$ might be huge, and nothing is said about the values of $c_i$. This is a rather crude comparisons for very large $n$. Useful because they are (comparatively) easy to get, and we are mostly interested in our algorithm's performance for large inputs (small ones are dispatched with not too much work).

Informally, $f(n) = O(g(n))$ means $g$ is an upper bound to $f$, $f(n) = \Omega(g(n))$ means $g$ is a lower bound, $f(n) = \Theta(g(n))$ that they grow roughly at the same rate. Note that for example $n = O(n^3)$ and $n = \Omega(\ln n)$. The notation does not mean $g(n)$ is "best possible" in any sense. Often it is understood from the context that the bounds are tight, but you have to check the context/derivation.


Making a CFG for a^i b^j c^k such that i+j = 3k

I am not sure whether it is a good idea to actually provide the grammar here in an answer but since the grammar is actually fairly easy I cannot see which details I could hide in a hint, so here it is:

$G = (\{S, A\}, \{a, b, c\}, P, S)$ with
$$
P = \{S \to aaaSc \mid aabAc \mid abbAc \mid bbbAc \mid \varepsilon, A \to bbbAc \mid \varepsilon\}.$$
You start by adding three $a$s for each $c$, after finitely many (possibly 0) applications of the first rule, you start creating three $b$s for each $c$ but one time you may actually add 2 $a$s, 1 $b$ for one $c$ or 1 $a$, 2 $b$s for one $c$ (2nd and 3rd rule, respectively).


Approximate a float using a minimal fraction

The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A best rational approximation of $x$ is a rational number $p/q$ such that $\left|x-\frac{p}{q}\right| \leq \left|x-\frac{p'}{q'}\right|$ for all $q' \leq q$. Your $p/q$ is in particular a best rational approximation, so it would be one of the convergents.


Louvain algorithm: self-loop weight is double?

Every edge has the same weight, which it contributes to each endpoint. When both endpoints are in the same cluster, the edge counts twice towards that cluster. Then they are in different clusters, the edge counts once towards each of the two clusters. So each edge has the same overall contribution.


You're misunderstanding what Vertex Cover is: the task is to find a set of vertices which "cover" or "touch" all edges. Each of the vertices $4,5$ covers the unique edge $(4,5)$ in the complement of your graph.

The theorem states that the size of the maximum clique in a graph equals the size of a minimum vertex cover in its complement. This is because a set $A$ of vertices is a clique in a graph $G$ if and only if its complement $\overline{A}$ is a vertex cover in the complement graph $\overline{G}$.

Indeed, $A$ is a clique in $G$ if any two $x,y \in A$ are connected in $G$; $\overline{A}$ is a vertex cover in $\overline{G}$ if for every edge $(x,y) \in \overline{G}$, one of $x,y$ is in $\overline{A}$. So $\overline{A}$ is not a vertex cover in $\overline{G}$ if there exists an edge $(x,y) \in \overline{G}$ such that $x,y \notin \overline{A}$, i.e. if for some $x,y \in A$, $(x,y) \notin G$; this is exactly the condition that $A$ is not a clique in $G$.


One approach is to use linear regression.

The matrix $A$ has $n^2$ entries; treat each of those entries as an unknown, so you have $n^2$ unknowns.  Now when $x$ is known, $f(x)$ is a linear function of those unknowns.  If you have a set of equations $f(x_i)=y_i$ that are all known to be exactly correct, then you can solve for the unknowns by using linear algebra.  If they are known to be approximately correct (e.g., $||f(x_i)-y_i||_2$ is small), you can use least squares to find the solution for the unknowns that minimizes the sum of the squared errors (that minimizes $\sum_i ||f(x_i)-y_i||_2$).  If a $1-\epsilon$ fraction of them are approximately correct, where $\epsilon \ll 1/n$, then you can pick a random subset of $n$ of them, guess that all of the ones in the subset are correct, use least squares to solve for the unknowns, and check whether that solution seems valid given the remaining equations, and repeat until you find a good solution.


According to Wikipedia, a closed-form formula for the number of unlabelled trees is not known, so a numbering in the form of a bijection between the set of unlabelled trees on $n$ vertices and $\{1,\ldots,T_n\}$ (for an appropriate $T_n$) is probably hopeless. Tree isomorphism is in P, so if you want an "effectively unique" identifier for trees, you can get it by using the Prüfer numbering and applying the algorithm to test equality. It is also possible that you can canonicalize trees (using the same ideas as in the algorithm), thereby creating a coding scheme in which two isomorphic trees get the same (Prüfer) number.


In general, there is a trade-off in programming language design between ease of use and expressiveness (power).  Writing a simple "Hello, world" program in a beginner language, such as Scratch or App Inventor, is generally easier than writing it in a general-purpose programming language such as Java or C++, where you might have a choice of several streams to output to, different character sets, the opportunity to change the syntax, dynamic types, etc.

During the creation of App Inventor (which I was part of), our design philosophy was to make programming simple for the beginner.  A trivial example was basing our array indices at 1, rather than 0, even though that makes calculations likely to be performed by advanced programmers slightly more complex.

The main way, however, that visual programming languages tend to be designed for beginners is by eliminating the possibility of syntax errors by making it impossible to create syntactically invalid programs.  For example, the block languages don't let you make an rvalue the destination of an assignment statement.  This philosophy tends to yield simpler grammars and languages.

When users start building more complex programs in a blocks language, they find that dragging and dropping blocks is slower than typing would be.  Would you rather type "a*x^2+b*x+c" or create it with blocks?

Justice can't be given to this topic (at least by me) in a few paragraphs, but some of the main reasons are:

Block languages tend to be designed for beginners so are not as powerful by design.
There is no nice visual way of expressing some complex concepts, such as type systems, that you find in general-purpose programming languages.
Using blocks is unwieldy for complex programs.


Would any continuous model of the universe have/be based on hypercomputational laws?

If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals.  A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum.  Wikipedia states that the set of functions that are computable in this model are incomparable with the set of functions that are computable in the usual model, and gives a citation where you can read more.  It's not clear to me exactly how that result should be interpreted, though.


Vehicle Routing Problem Using Simulated Annealing

To solve a combinatorial optimisation problem such as this by a method such as Simulated Annealing, you need 3 basic ingredients:

A representation for a 'Candidate Solution'. For vehicle routing, this is typically a permutation of the depots, i.e. a list of depots in the order to be visited.
A measure of the quality of a candidate solution. Various methods exist for penalising solutions with deliveries outside their time windows or fail to meet other constraints.
One or more 'perturbation operators' for transforming a candidate solution into another (hopefully better) one. For example, swapping two randomly-chosen depots in the permutation is one of the simplest approaches, but of course more informed operators as possible.

Given these three, it's then possible to plug your problem into a range of metaheuristics, such as iterated local search, Tabu search, various Evolutionary Algorithms or Tabu search.

As regards annealing schedule, there's a range of literate on choosing parameters, but one simple option is to obtain initial and final temperatures from the statistics of a sequence of random perturbations, then experiment with the choice of cooling rate in a geometric annealing schedule.

The excellent (and freely-available) book "Essentials of Metaheuristics" offers a more detailed background on the above and some guidelines for what techniques to apply in what circumstances.


Running Dijkstra on particular graph with negative weight

The shortest path tree of Dijkstra will set root as $S$ then it first selects the $Y$ with weight 8. Then it will look at the shortest distance of all the neighbor's of the tree. There will be two candidates $X$ and $Z$. It will choose $X$ since the distance is 10. Then finally, it will choose $Z$ with distance 11.

The Dijkstra's, as stated, cannot work correctly on graphs with negative weights.

The problem is that it is a greedy algorithm and once it finds the shortest path for a node it is not re-evaluating for any other possibilities may occur in the future. This is not possible if the graph has not negative weights.


Efficient algorithm to compare arrays problem

You can write $x$ and $y$ in binary as
\begin{align}
x&=x_{M-1} \ldots x_0 \\
y&=y_{M-1} \ldots y_0
\end{align}
(This is exactly the contents of your arrays.)
Since $x \neq y$, there must be a first bit (from the left) at which they differ. Say that this bit is $x_i \neq y_i$. Since $y > x$, we know that $y_i = 1$ and $x_i = 0$. Thus
\begin{align}
x &= x_{M-1} \ldots x_{i+1} 0 x_{i-1} \ldots x_0 \\
y &= x_{M-1} \ldots x_{i+1} 1 y_{i-1} \ldots y_0
\end{align}
The following two integers are in the range $x,\ldots,y$:
\begin{align}
&x_{M-1} \ldots x_{i+1} 0 1 \ldots 1 \\
&x_{M-1} \ldots x_{i+1} 1 0 \ldots 0
\end{align}
This shows that if you take the AND of all integers from $x$ to $y$, you get
$$
x_{M-1} \ldots x_{i+1} 0 0 \ldots 0
$$


LinkedList: Remove the kth node form the end

head = head.next

would accomplish nothing. It would only change the local variable head.
Read the question again:

Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed.

Since you cannot change what node is the head, you change the contents of that node.


Is quadratic nonresiduosity in $\textbf{NP}$?

When the modulus is a prime $p$, you can compute quadratic residuosity in polynomial time using the Legendre symbol: $x$ is a quadratic residue mod $p$ iff $(x|p)=1$ or $0$.
When the modulus is a prime power $p^\alpha$, then you can do the same: I believe $x$ is a quadratic residue mod $p^\alpha$ iff $(x|p)=1$ or $0$.  I believe this can be proven using Hensel lifting.
When the modulus is a number $n$ with known prime factorization $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$, you can use the Chinese remainder theorem: $x$ is a quadratic residue mod $n$ iff it is a quadratic residue mod $p_i$ for all prime factors $p_i$ of $n$.
This means that quadratic nonresiduosity mod $n$ can be computed in polynomial time when the factorization of $n$ is known or given.  This also means that, as far as I can see, the language QNR should be in NP: a natural certificate is a prime $p$ that divides $n$, and such that $(a|p)=-1$.  The verifier can verify that $p$ is prime in polynomial time and compute the Legendre symbol $(a|p)$ in polynomial time.  At least, that's how it seems to me.
I don't know why Arora-Barak say that QNR is not known to be NP.  This makes me suspect that I may have misunderstood something, as they know way more about computational complexity than I do.


why quicksort can have a best big o notation of (n log n)

The "standard" version of quicksort does not have a worst case time complexity of $O(n \log n)$. In fact, it can even require $\Theta(n^2)$ time. However, quicksort does have an average time complexity of $O(n \log n)$.
You can get quicksort to run in $O(n \log n)$ worst-case time if you use a suitable pivot-selection strategy. In particular you want a pivot-selection algorithm that requires at most linear time to find a pivot ensuring that the two recursive calls of quicksort are  performed on at least a constant fraction of the input elements. See Median of medians.
The base of the $\log$ doesn't really matter as long as it is a constant greater than $1$. This is because the big-oh notation hides constant multiplicative factors and if you consider two possible bases $a$ and $b$, you have $\log_a n = \frac{\log_b n}{\log_b a}$, where $\log_b a = \Theta(1)$. That said, $\log$ usually refers to the binary logarithm in computer science.


consider a base 16 adder how to modify the adder so that it can perform a base 8 addition?

Assumptions/Statements:
A base 16 adder: an adder that adds two 4-bit binary numbers I1 and I2 and outputs the 4-bit result R and a carry bit C

To use as a base 8 adder (as above) discard the Most Significant Bit from both I1 and I2 (i.e. ground/zero them). Now your inputs are base-8. From the output discard the Carry bit C it will always be zero. Your new Carry bit will be the Most Significant Bit from result R. Your new result will be the 3 least significant bits from R.

Please check Assumptions/Statements are in accordance to your book!


I/O cost to traverse a tree stored in preorder form

It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

Read $B$ nodes into a buffer.
For each node in the buffer:

Push $(node.id, num\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
While $S.peek().num = 0$:

$d = S.peek().d$
Output $(S.peek().id, d)$.
$S.pop()$
$S.peek().num = S.peek().num - 1$
$S.peek().d = max(S.peek().d, d + 1)$.

If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.


You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.


Get the nth lexicographic string of "all" possible combinations of an alphabet

It is better if you include the empty string as the $0$th string in lexicographic order. Here is how you convert an index into a word.

First, we are going to find the first letter of the word, and an internal index among all words starting with this letter. We do this by counting how many words start with each letter, including the "empty letter". I'll let you figure out how to do that. In your case, we get $1,5,5,5$. This means that $[0,1)$ corresponds to the empty sword, $[1,6)$ to words starting with $a$, $[6,11)$ to words starting with $b$, $[11,16)$ to words starting with $c$.

Given an index, you locate which interval it belongs to, and record the starting character and the internal index inside the interval. In your example, $12$ belongs to $[11,16)$ (and so starts with $c$), and its internal index is $1$.

If the index is $0$, then we are done. Otherwise, we recurse. In your example, we are left with the alphabet $\{a,b\}$ for which the intervals are $[0,1),[1,3),[3,5)$. The current index is $1$, so the word at this level of recursion starts with $a$, and the new index is $0$. That means that the recursion ends here. The outputs is thus $ca$.


Given two heuristic values how do I tell which one is admissible?

A heuristic function $h$ is admissible, if it never overestimates the cost for any given node. Formally speaking, let $h^{*}$ map each node to its true cost of reaching the goal. The heuristic function $h$ is admissible, if for all nodes $n$ in the search tree the following inequality holds:
\begin{align}
  h(n) \leq h^*(n). \tag{$\star$}
\end{align}

That means for checking whether a given heuristic function $h$ is admissible, we have to verify that the inequality $(\star)$ holds by either
  (a) calculating the real cost $h^{*}$ for each node and comparing the values, or
  (b) proving it by using additional information available of the heuristic.

For example, we know that the eucledian distance is admissible for searching the shortest path (in terms of actual distance, not path cost). Note also that any consistent heuristic is admissible (but not always vice-versa).

For your example, there is no additional information available regarding the two heuristics. Thus you have to calculate the real cost $h^*$ for each node, and then check whether the inequality $(\star)$ holds (I leave this task to you).

By checking the total cost you can neither prove that a heuristic is admissible nor that a heuristic is not admissible. The problem with this idea is that on the one hand you sum up the costs of the edges, but on the other hand you sum up the path cost (the heuristic values). For example, consider the following search tree with start node $A$ and goal node $C$

and the following heuristic functions $h_1$ and $h_2$:

\begin{align}
  h_1(A) = 20; &\quad h_2(A) = 8 \\
  h_1(B) = 10; &\quad h_2(B) = 11 \\
  h_1(C) = 0; &\quad h_2(B) = 0 \\
\end{align}

The sum of the total cost of the search graph is $10 + 10 = 20$. The sum of the heuristic values of $h_1$ is equal to $20 + 10 + 0 = 30$, which is larger than $20$ although $h_1$ is admissible. The sum of the heuristic values of $h_2$ is equal to $8 + 11 + 0 = 19$, which is smaller than $20$, but $h_2$ is not admissible, since $h_2(B) = 11 \nleq h^{*}(B) = 10$.