You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).

You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' > \sum_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.
(1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \{ S' + S-B \}$ and $L\setminus M \cup \{ S'+B \}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.
(2) If $L'$ can be partitioned into two equal parts $P_1,P_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| < S'$, so it is not possible that $\{S'+S-B\} \cup \{ S'+B \} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P_1$. The rest of the elements in $P_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.


Deciding whether complement of context-free language is context-free

Your problem can be formalized in several equivalent ways:

Given a context-free grammar $G$ over $\Sigma$, is $\overline{L(G)} := \Sigma^* \setminus L(G)$ context-free?

Given a PDA $M$ over $\Sigma$, is $\overline{L(M)}$ context-free?

Since we can effectively (and efficiently) translate between the two representations, both problems are equivalent. We stick to the first one.
It is well-known that given a context-free grammar $H$ over $\Sigma$, deciding whether $L(H) = \Sigma^*$ is undecidable. We will reduce this problem to Problem 1.
Let us be given a context-free grammar $H$ over $\Sigma$. If $\Sigma$ is a singleton, then $L(H)$ is regular, and so $\Sigma^* \setminus L(H)$ is also regular and context-free. Otherwise, let $a,b \in \Sigma$ be two distinct symbols. Construct a grammar $G$ over $\Sigma \cup \{\#\}$ (where $\#$ is a fresh symbol) for the language
$$
L = (\Sigma^* \setminus \{ww : w \in \Sigma^*\}) \# \Sigma^* \cup \Sigma^* \# L(H).
$$
If $L(H) = \Sigma^*$ then $L = \Sigma^* \# \Sigma^*$ is regular, and so its complement is regular and context-free. Otherwise, let $x \notin L(H)$. If $\overline{L}$ were context-free, then so would the following language be:
$$
\overline{L} \cap \Sigma^* \# x = \{ww : w \in \Sigma^*\} \# x.
$$
This would imply, however, that $\{ww : w \in \Sigma^*\}$ is context-free, which is known to be false.
Summarizing, $\overline{L(G)}$ is context-free iff $L(H) = \Sigma^*$.
Compare Theorems 11–12 in Hendrik Jan's notes.


Why is the processor's pipeline delay calculated as N*max(Delay) ? why not N*(D1 + D2 + D3 ... )?

Each stage of the pipeline is only as fast as the slowest stage. The calculation for the latency expresses this by taking the maximum delay (max(D1, D2, D3, D4)) and multiplying it by N, which is the number of stages. Thus: N*max(D1, D2, D3, D4).

Keep in mind, N is the number of stages, not instructions. The formula measures the latency, not the total run time.

Your chart demonstrates this, as you can see that there is more and more delay building up in the first and second stages as they finish faster than the next stage. But there is a problem: where does the data from each stage go before it enters the next stage? The simple answer is nowhere: it is stuck in the current stage until the next stage is free. Your third stage is creating a traffic jam!

Consider this chart, in which each stage has been slowed down to take 4 time units (the n represents that processing is done but the data must wait for the next stage to clear):

    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
    S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                            S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                                        S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!

Here we can see that it takes each individual instruction 16 time units to make it through the pipeline (4 stages * max delay of 4). The total run time is only 28 time units. It takes 16 units for the first instruction to run, and 4 more time units for each additional instruction. So the run time formula is something like: N*max(D1, D2, D3, D4) + (IC - 1) * max(D1, D2, D3, D4) where N is the number of stages and IC is the number of instructions.


Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$

Given parameters $n$ and $g$, you want to find the connected components of the graph on $[n] := \{1,\ldots,n\}$ whose edges are $\{(i,j) \in [n] : (i,j) > g\}$. Let us write these edges in a different way:
$$
\bigcup_{d=g+1}^n \{(i,j) \in [n]: d \mid (i,j) \} =
\bigcup_{d=g+1}^n \{(dI,dJ) : 1 \leq I,J \leq n/d \}.
$$
For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path:
$$
\bigcup_{d=g+1}^n \{(dI,d(I+1)) : 1 \leq I < \lfloor n/d \rfloor \}.
$$
The number of edges in the new graph is
$$
\sum_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum_{d=g+1}^n \frac{1}{d} = O(n\log n).
$$
You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.


Check if there is only one simple path in graph between nodes x and y`

Raphael's suggestion to use 2-shortest path is correct but more complex than necessary.

Your approach is unfeasible, the number of cycles is factorial in the size of input.

Here's a sketch of a solution in time $O(|V|+|E|)$.

Find a path $p_1, \dots p_n$ from $x$ to $y$ in $O(|V|+|E|)$. If  no such path exists, answer $\textsf{NO}$. Otherwise, mark all the nodes in the path. That path is indeed unique if and only if no node in that path reaches a node that comes after it. Starting from the first node of the path $p_1$, pick a random edge going out from $p_1$ other than the one that connects it to $p_2$ and start a DFS from there. If you reach a marked node, answer $\textsf{NO}$, if you never reach a marked node, cut that branch from the graph and pick another random outgoing edge. Continue in a similar fashion until all outgoing edges are exhausted, then start again with the following node until you reach $p_n$.
If you finish the procedure without ever answering $\textsf{NO}$, answer $\textsf{YES}$. The entire procedure has the cost of a DFS, $O(|V|+|E|)$, therefore the overall time is $O(|V|+|E|)$.


These problems usually appear under the name "X edge deletion" and "X vertex deletion", where X is the graph class of interest, e.g., X could be "planar". There are also different variants where you allow for say edge addition and deletion (these are "editing problems"), or the operation could be edge contraction and so on.

In other words, you seem to be interested in both planar vertex deletion and planar edge deletion. For starters, you can see [1] and [2] (the problems seem FPT parameterized by the number of operations $k$).

[1] Marx, Dániel, and Ildikó Schlotter. "Obtaining a planar graph by vertex deletion." Algorithmica 62.3-4 (2012): 807-822. -- Non-paywalled version here.

[2] Golovach, Petr A., Pim van’t Hof, and Daniël Paulusma. "Obtaining planarity by contracting few edges." Theoretical Computer Science 476 (2013): 38-46.


Find largest and second largest elements of the array

Here I present an optimal solution minimizing the number of comparisons.
The thing to take advantage of is the first step of the original algorithm:
if A[1] < A[2],
    largest = A[2], second = A[1]
else
    largest = A[1], second = A[2]

We can get the largest and second largest of sets of two in one comparison!
So the first thing we should do is divide our array into $n/2$ pairs of two. Namely:
$$p_1 = (a_1, a_2), p_2 = (a_3, a_4), \ldots, p_i = (a_{2i - 1}, a_{2i}), \ldots, p_{n/2} = (a_{n-1}, a_n)$$
For every pair $p_i$, we can determine it's largest and second largest value in one comparison. We'll call these $p_i.L$ and $p_i.S$ respectively. So it takes $n/2$ comparisons to determine all of thee values for every pair.
Let's call the overall largest and second largest elements $\mathbb{L}$ and $\mathbb{S}$ respectively. We know that $\mathbb{L}$ will be among the $\{p_i.L\}$'s because it will be the largest of these. We also know $\mathbb{S}$ will be among $\{p_i.L\} \setminus \mathbb{L}$ or it could be the second largest value in the pair that $\mathbb{L}$ came from.
An example: Let our original array be:
$$A = [1,4,5,2,7,9,10,19]$$
We then break it up into pairs:
$$P = [(1,4)(5,2)(7,9)(10,19)]$$
We then know $\mathbb{L}$ will be in:
$$W = \forall i.\; \{p_i.L\} = \{4, 5, 9, 19\}$$
So now we just need to find three values: $W.\mathbb{L}$ (this will be $A.\mathbb{L}$), $W.\mathbb{S}$ (this could potentially be $A.\mathbb{S}$) and $p_i.S$ where $p_i$ is the pair that $W.\mathbb{L}$ came from (this could also potentially be $A.\mathbb{S}$).
From our example we see $A.\mathbb{L} = W.\mathbb{L} = 19$. We then see $A.\mathbb{S}$ is either $W.\mathbb{S} = 9$ or $10$ (from the pair containing $W.\mathbb{L}$), and it is $10$.
So this turns our problem of $A$ into a subproblem of size $n/2$, $W$. Then we can run the original algorithm on this subproblem and do some extra comparisons to get $A.\mathbb{S}$ and this totals about $\approx 1.5n$ comparisons. But we can do better!
We use recursion on this subproblem instead of just using the original algorithm. So the algorithm looks like this, and will return the indices of the $A.\mathbb{L}$ and $A.\mathbb{S}$. (assume $n = 2^k$ and this is 1-indexed). The algorithm will modify the input array so we will assume $A$ to be a copy of the input.
L_and_S (array of length n):
  Let A = copy of input
  // base case
  if n == 2:
    if A[1] > A[2]:
      return (1, 2)
    else:
      return (2, 1)

  // recursive case
  Let W be new array length n/2 (keeps track of largest elements)
  Let M be new array length n/2 (keeps track of swaps)
  for i in 1 ... n/2:
    // swap larger element into first position of pair
    // set M[i] to 1 if pair was swapped, else 0
    // move larger element into W
    if A[2*i - 1] < A[2*i]:
      temp = A[2*i - 1]
      A[2*i - 1] = A[2*i]
      A[2*i] = temp
      M[i] = 1
    else:
      M[i] = 0
    W[i] = A[2*i - 1]

  // now recurse on W
  (j, k) = L_and_S(W)
  // map back from W to A
  j_swap = M[j]
  k_swap = M[k]
  j = 2*j - 1
  k = 2*k - 1
  if A[j + 1] > A[k]:
    k = j + 1
    k_swap = 0 - j_swap
  return (j + j_swap, k + k_swap) // account for the swap

We can run through the example above:
L_and_S([1,4,5,2,7,9,10,19]):
  // do n/2 comparisons
  A = [4,1,5,2,9,7,19,10]
  W = [4,5,9,19]
  M = [1,0,1,1]
  (j, k) = L_and_S([4,5,9,19]):
             // do n/4 comparisons
             A = [5,4,19,9]
             W = [5,19]
             M = [1,1]
             (j, k) = L_and_S([5,19]):
                        // do 1 comparison (5 > 19)
                        return (2,1)
             (j_swap, k_swap) = (1, 1)
             (j, k) = (3, 1)
             // do 1 comparison (9 > 5)
             k = 4
             k_swap = -1
             return (3 + 1, 4 - 1) = (4, 3)
  (j_swap, k_swap) = (1, 1)
  (j, k) = (7, 5)
  // do 1 comparison (10 > 9)
  k = 8
  k_swap = -1
  return (7 + 1, 8 - 1) = (8, 7)

We see overall this takes $n/2 + n/4 + 1 + 1 + 1 = 9 = n + 1$ comparisons! These are comparisons of the array elements, ignoring the base case comparison in the beginning.
The exact recurrence relation for number of comparisons is the following (assume $n = 2^k$):
$$\begin{align}
  T(2) & = 1\\
  T(n) & = T(\frac{n}{2}) + \frac{n}{2} + 1\\
  & = 1 + \sum_{1}^{\log_2 n - 1} \frac{n}{2^i} + 1\\
  & = \log_2 n + \sum_{1}^{\log_2 n - 1} \frac{n}{2^i}\\
  & = \log_2 n + n - 2\\
  & = n + \log_2 n - 2
\end{align}$$
So we get the total number of comparisons in the worst case is $n + \log_2 n - 2$, which is pretty good. In fact, this is a lower bound! (see here) If you include the base case comparison it adds another $\log_2 n$ to the comparisons. Here's a table for the first few $n$:
$$\begin{array}{|c|c|}
\hline n & n + \log_2 n - 2 & 2n - 3 \\
\hline 2 & 1 & 1 \\
\hline 4 & 4 & 5 \\
\hline 8 & 9 & 13 \\
\hline 16 & 18 & 29 \\
\hline 32 & 35 & 61 \\
\hline 64 & 68 & 125 \\
\hline 128 & 133 & 253 \\
\hline 256 & 262 & 509 \\
\hline 512 & 519 & 1021 \\
\hline 1024 & 1032 & 2045 \\
\hline
\end{array}$$

Implementation of the code in python can be found here, with test cases at the bottom.


Comparison between IDA* and Recursive best first search

Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. Artificial Intelligence, 62 (41--78), 1993. In fact, RBFS is much more than "just updating the $F(n)$ value for the parent for which the current execution was stopped". RBFS stores the so-called stored $f$-value of each node $n$ as $F(n)$. An invariant of the algorithm is that the stored $f$-value is the minimum static $f$-value (ie., the usual $f(n)=g(n)+h(n)$) among all leave nodes generated in a tree rooted at $n$. From here, $F(n)\geq f(n)$ for all nodes $n$ given that costs are monotonic. Initially, when a node is expanded for the first time $F(n)=f(n)$. Later on, when backtracking after examining its descendants, its $F$-value (ie., the stored $f$-value) is accordingly updated.

So, if nodes beneath node $n$ are examined, up to what point are they developed? Another parameter used in RBFS is an upper bound $B$ which is initially set to $+\infty$. Do not read $B$ as a global upper bound! Indeed, every time a node is selected for expansion, $B$ is updated to the minimum between the current value of $B$ and the second-best $F$-value. So here you are a second invariant of RBFS: every time a node is selected for expansion, it has an $f$-value which is less or equal than the second best $f$-value in the whole search tree. This is true: first, because $B$ is updated using the second-best $F$-value which amounts to compare it with all the descendants of its siblings; second, the other component used is $B$ itself which was, in turn, computed in the same way by its ancestors. Finally, remember that after every expansion, nodes are sorted in increasing order of their $F$-value.

As a result, RBFS expands nodes in the same order of A*! So far, I do not see it as a successor of IDA*, but instead, as a new member of the large family of best-first search algorithms. Note that in the preceding statement I solely refer to the new expansions. There will be often in between an arbitrarily large number of re-expansions.

For a more didactical explanation of the algorithm refer to the paper Ariel Felner. The Collapse Macro in Best-First Search Algorithms and and Iterative Variant of RBFS. Symposium on Combinatorial Search (SoCS 2015), 28--34. Israel, 2015. During his dissertation Ariel openly said that this is an algorithm poorly understood in general and there was agreement. Conclusion: read this paper also if you are interested in understanding RBFS (I do sincerely doubt that my review suffices for a good understanding of the algorithm).

Regarding your questions:

Note that in the first paragraph I expliclty refered to backtracking ie, RBFS is implemented as a depth-first search algorithm. So far, its memory requirements are $O(bd)$ where $b$ is the branching factor and $d$ is the depth where the solution lies.
Assuming that the expansion of every node is the dominant operation and that it takes the same amount of time in spite of the node been expanded, then the number of expansions directly relates to the time complexity. Korf proved that, in the general case, the time complexity is (as one would expect) $O(bˆd)$ where $b$ is the asymptotic branching factor. Also, the best and worst case analysis are analyzed by Korf in the original paper.

As you mentioned the relationship with IDA* let me also remark that Korf proved that RBFS expands less nodes (in total, considering also re-expansions) than IDA* in the average-case in case of monotonic costs. If costs do not grow monotonically then these algorithms cannot be compared as they traverse entirely different search trees. Since IDA* is known to be asymptotically optimal, then RBFS is asymptotically optimal as well.

Hope this helps,


This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right?

Yes.

Let $T$ be the threshold of the process you describe. In a uniform (i.e. non-biased) distribution, the sequence $\mathtt{0}^{T+1}$ would have the probability $2^{-(T+1)}$, like any other sequence of length $T+1$. But the process you describe will flip the last bit, since the threshold of excess $\mathtt{0}$ bits was exceeded, and thus this sequence has the probability $0$. That's a bias. Note that this bias exists regardless of the distribution of the original generator, i.e. the process always makes the generator somewhat worse.

It's pretty apparent if you take this to an extreme. With $T=1$, the output of the process would be an alternating sequence, either $\mathtt{01010101\ldots}$ or $\mathtt{10101010\ldots}$, which is obviously hardly random at all.

This process looks like it was devised by someone who doesn't understand probability. They have a vague intuition that (9,9,9,9,9,9) doesn't look random and so they go out of their way to avoid too many repetitions. But (9,9,9,9,9,9) is not impossible, so any random generator will generate this sequence of length 6 one day, and again, and again… And it will generate (9,9,9,9,9,9,9) if you wait long enough, and (9,9,9,9,9,9,9,9), etc.

The proportion of $\mathtt{1}$ bits in the first $n$ bits should tend towards a bell curve as $n$ tends to infinity. A biased initial source deforms the curve towards one side. The process moves the summit towards the center, but cuts off the sides.

  Is this a valid concern?

Yes. Bad random generators sink ships (or save them, as the case may be). One of the ways the Allies broke messages encrypted with the German Enigma during WWII was to rely on lack of randomness because the operators' intuition of randomness led them to introducing biases.

  If yes, what are proper ways to deal with bias in RNG?

If you have a random source where each bit has a probability $p$ of being $\mathtt{0}$ and $1-p$ of being $\mathtt{1}$, then there's a rather well-known trick to turn it into a uniform source, which is due to Von Neumann. Read two bits; if they're different then output the first bit and discard the second one; if they're the same then discard both bits and try again. This works well enough with a biased coin because the bias is overwhelmingly due to the design of the coin which doesn't change between tosses. But it assumes that the bits are all independent from one another. This is not a safe assumption for a physical random generator. Even if the underlying physical process is “perfectly” random, imperfections in the construction of the apparatus often have more complex biases, e.g. due to resonance phenomena. The general name for this sort of process is whitening. Von Neumann whitening is typical good enough for physical simulations, but other usage such as cryptography needs more reliable methods.

In computer security, the practical way to construct a random generator is to use a hybrid design.

A random source (ultimately derived from some physical process) provides entropy. It doesn't matter that this source is biased. All that matters is that it has some minimal level of unpredictability, i.e. there is some threshold $p \gt 0$ such that the probability of any given bit being $\mathtt{0}$ is between $p$ and $1-p$.
The entropy is used as a seed to a cryptographically secure pseudorandom number generator (CSPRNG). A CSPRNG is deterministic, but it is infeasible for an adversary to guess any part of its output unless they know the seed. (“Infeasible” means that the adversary trying to guess an output bit gains a negligible advantage from any knowledge that doesn't imply knowledge of the key.)

The resulting distribution is not uniform (since the CSPRNG is deterministic, it can only output a finite subset of all possible sequences, limited by its state size), but it is indistinguishable from a uniform distribution by an adversary with finite processing power.


There is an instruction already in the branch delay slot - it's just not displayed. So unless that instruction that isn't displayed is a NOP instruction, it will not be executed anymore if the branch is performed, so the meaning of the program has changed. Unless the question is "here is the code for a processor without branch delay slots, modify it for a processor with branch delay slots". In which case the obvious solution is to just move the last instruction before the conditional branch to the branch delay slot.

Independent of branch delay slot, you cannot just move the SW instruction which uses R2 past an instruction that modifies R2. In this case, you can move it if you modify it: R2 is increased by 4, so you can use the address -4(R2) instead of 0(R2).

In general, you initially don't care about branch delay slots and write code as if there were no branch delay slots, and add a NOP after each conditional branch, so you have correct code.

Then you move instructions into the branch delay slots, but carefully: You mustn't move an instruction if there is a branch to the conditional branch (because that instruction would be wrongly executed when branching to the conditional branch). You can't move certain instructions, like branches, returns, calls. And you can't move an instruction that was already moved. Say x = 0, branch if zero, not, branch if not zero, not. You can move the x = 0 into the first branch delay slot, but you mustn't move it into the second one.


Proving NP hardness in Puzzle with SAT reduction

As far as I can tell, no, you have not proved NP-hardness of your puzzle. NP-hardness is precisely defined. If you want to prove a mathematical statement, you must do mathematical work and can't get there by only hope and intuition.

If you want to show that problem X is hard by a polynomial-time reduction from 3-SAT, you should proceed as follows. Take any arbitrary instance $I$ of 3-SAT and construct, in polynomial-time, an instance $I'$ of X. Once you've done this, prove that $I$ has a solution if and only if $I'$ has a solution. This is the "mathematical part", where you use the properties of $I$ and $I'$ to argue for both implications; you need some insight and practice in writing mathematical proofs, where in the argument the next step follows from the previous.

For example, contrary to what you seem to say, you can't show hardness by reducing one fixed instance of 3-SAT to your problem X.

If all this feels confusing but you are still excited, I recommend that you:

Read the relevant definitions of NP, NP-hardness and polynomial-time reductions. Think about what they mean intuitively as well.
Look at examples of reductions and NP-completeness proofs. Don't expect to get it straight away, but be willing to do some work. There are plenty of exercises out there and many questions on this site too.
Come back to your original problem later, perhaps after getting a little bit more familiar with writing proofs in general.


How can I prove the following problem is NP complete?

I think there is an easy reduction from Knapsack.

Knapsack:

Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$
Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$

Now given an input of knapsack, let's construct an input of your problem: add a $n+1$-th element, and consider:

$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $c\{i, j\} = \infty$  and $c\{i, n+1\} = w_i$
$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $g\{i, j\} = 0$  and $g\{i, n+1\} = v_i$
set $b = W$ and $p = V$

Then this instance has a solution of your problem if and only if the input of knapsack has a solution. Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem.


Is word size, the size of a memory location? the size of the data bus? or the cpu register size?

This is one of those terms that can mean different things depending upon who you ask and the context in which it is asked.

Usually a processor's word size is defined as the largest size integer which it can operate on with a single arithmetic instruction.  For example, 64 bit computer can add or subtract 64 bits with a single instruction.  But that same computer may be able to operate on bytes, 16 bit words, and 32 bit longwords.

Don't equate the memory path with the computer's word size.  Often data is moved into and out of cache in a fixed size block that is a multiple of the computer's word size.  A 64 bit CPU has 8, 8 bit bytes per word but might use a 64 byte cache line and move data into and out of memory in cache block chunks, even if the CPU is only accessing 1 byte of the cache block.  OR conversely, the data path to memory could be smaller, as the case with the old 8088 CPU.   It used 16 bit CPU registers and did 16 bit arithmetic, but had an 8 bit data bus.  It had to do 2 memory transfers to load or store a register.

And then there are fixed definitions for a word size, for example...

DEC had a problem with just saying WORD especially on VAX architecture, mostly because the company had built so many different computers with different natural word sizes (9, 18, 36, 12, 16, 32 and 64 that I can think of) and the VAX was capable of working with a large variety of data sizes.  So they decided to define terms like WORD to have more definite meanings.
Byte = 8 bits,
Word = 16 bits,
Longword = 32 bits,
Quadword = 64 bits,
Octaword = 128 bits

This took much of the confusion out of discussions when a processor was capable of handling multiple different data sizes.

edit - I didn't really address this part of the question:
"And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3 And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4"

Not usually.
IF a 64 bit computer is capable of addressing Longwords on a byte boundary, normally the system would load the cache block containing the address 0 from memory into cache.  Often that will be on a multiple word cache size.   So in the example I gave with a 64 byte cache line, the hardware would move the first 64 bytes into cache as a chunk.  The CPU would then access the bytes from cache as you describe (well sort of, it may have to shift bytes to get them loaded correctly).  If the longword you attempted to load spanned 2 cache blocks, the hardware would have to load 2 cache blocks (128 bytes) to access the 4 you were interested in. Or in the example you gave with a 32 bit data bus, it would have to load 64 bits (2 lines) to get the 32 that you want.   If possible, it's best to align data on its natural boundary to avoid this and other data manipulations required to deal with unaligned data.


Practical importance of Turing machines?

The importance of Turing machines is twofold. First, Turing machines were one of the first (if not the first) theoretical models for computers, dating from 1936. Second, a lot of theoretical computer science has been developed with Turing machines in mind, and so a lot of the basic results are in the language of Turing machines. One reason for this is that Turing machines are simple, and so amenable to analysis.

That said, Turing machines are not a practical model for computing. As an engineer and a Mathematica user, they shouldn't concern you at all. Even in the theoretical computer science community, the more realistic RAM machines are used in the areas of algorithms and data structures.

In fact, from the point of view of complexity theory, Turing machines are polynomially equivalent to many other machine models, and so complexity classes like P and NP can equivalently be defined in terms of these models. (Other complexity classes are more delicate.)


First, $A_{PTM}$ as you defined it is not even decidable (so it isn't in BPP), since your simulation might not halt.

The naive attempt at a BPP complete language is:

$A_{PTM}=\left\{\left(\langle M\rangle,x, 1^t\right) \big| M \text{ accepts $x$ in $\le t$ steps with probability $\ge \frac{2}{3}$} \right\}$.

Note that there is no notion of "error" in the definition of $A_{PTM}$, as there are no right answers, you decide whether or not to include some triplet in your language.

You can show that $A_{PTM}$ is indeed BPP-hard (I leave the reduction details for you). The problem is that we do not know if $A_{PTM}\in \mathsf{BPP}$. Simply simulating $M$ on $x$ for $t$ steps and outputing its answer won't work. Imagine $M$ accepts $x$ after $t$ steps with probability $\frac{1}{2}$, then although $(M,x,t)\notin A_{PTM}$, you accept it with probability $\frac{1}{2}$, while you should be accepting with probability $\le \frac{1}{3}$.

In fact, $A_{PTM}$ is $\mathsf{PP}$ complete, so it is unlikely to lie in $\mathsf{BPP}$. The existence of complete problems for BPP is currently an open question in complexity. You can check this question from cs-theory, which talks about why it is harder to find complete problems for classes like BPP.


What does Stroustrup mean by 7/8ths of MIPS being in the vector units?

Imagine you have a 256 bit vector floating point unit which can perform eight 32 bit operations in parallel. How many operations per second can you perform with or without using the vector FPU?

Imagine you have eight cores.  How many operations can you perform in one second using one core or all eight cores?


Understanding a proof for the existance of a non-computable function

The contradiction reached is that $0 = 1$ which violates one of Peano's axioms. Assume $G$ is computed by the $j$-th Turing machine. Observe that $G$ is everywhere defined. Then
$$f_j(j) = G(j) = f_j(j) + 1$$
and by canceling $f_j(j)$ on both sides we get
$$0 = 1.$$


The chronological order constraint actually makes this problem much easier to solve than D.W. thought. It means that we can orient edges in the graph from earlier to later tournaments (reflecting the fact that we cannot travel back in time), and wind up with a DAG (cycle-free directed graph). The problem can be solved optimally in $O(pn^2)$ time and $O(pn)$ space (so, at most a few milliseconds and KB for your problem size) using dynamic programming.
Let $f(v, i)$ be the length of the shortest $i$-vertex path that ends at vertex $v$. The goal is to compute $f(v, p)$ across all vertices, and pick the $v$ that minimises the function among all of them.
The shortest $i$-vertex path ending at vertex $v$ must be the result of extending (by one edge, to $v$) the shortest length-$(i-1)$ path to one of $v$'s predecessors:
$f(v, i) = \min_{u:uv\in E} f(u,i-1)+d_{uv}$
where $E$ is the set of all edges in the graph and $d_{uv}$ is the distance between $u$ and $v$.
Naturally we also have $f(v, 1) = 0$ for all $v$. So, we can compute all these function values and store them in a 2D array as follows:

Initialise $f[1][v] = 0$ for all $v$.
For $i$ from 2 to $p$:

For each $v$ in $V$:

Set $x = \infty$.
For each predecessor (in-neighbour) $u$ of $v$:

Set $x = \min(x, f[i-1][u] + d_{uv})$.

Set $f[i][v] = x$.

Set $z=v_1$.
For each $v$ in $V\setminus \{v_1\}$:

If $f[p][v] < f[p][z]$ then set $z=v$.

After running this, we know the lengths of all shortest paths of $i$ vertices or less ending at each vertex, and that the shortest overall path of $p$ vertices ends at vertex $z$. To find an actual shortest path ending at vertex $z$, we can trace backwards through the matrix looking for predecessor entries that satisfied the $\min$ condition:

Set $i=p$.
While $i>0$:

Output the current vertex, $z$.
Set $x = \infty$.
For each predecessor (in-neighbour) $u$ of $z$:

If $f[i-1][u] + d_{uz} = f[i][z]$:

$u$ is the previous tournament on some optimal path ending at $z$, so set $z=u$, decrease $i$ by 1 and jump to the top of the while loop.

This will output the tournaments in reverse order, but that can be easily fixed.


Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).
Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this assumption later). We concentrate on your sample recurrence
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n). $$
This recurrence needs two base cases, $T(0)$ and $T(1)$. We make the assumption that $T(0) \leq T(1)$, which we also relax later on.
I claim that $T(n)$ is monotone non-decreasing. We prove by complete induction that $T(n+1) \geq T(n)$. This is given for $n = 0$, so let $n \geq 1$. We have
$$
\begin{align*}
T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\
&\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n).
\end{align*}
$$
This implies that
$$ T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rceil}). $$
So if $T(2^m) = \Theta(T(2^{m+1}))$, we're done. This is always the case if the solution for powers of two is of the form $T(n) = \Theta(n^a \log^b n)$.
Now let's relax the assumption that $T(0) \leq T(1)$. Consider a new recurrence $T'$ defined in exactly the same way, only $T'(0) = T'(1) = \min(T(0),T(1))$. We can prove by induction that $T'(n) \leq T(n)$. Similarly, we can define a new recurrence $T''$ satisfying $T''(0) = T''(1) = \max(T(0),T(1))$, and then $T(n) \leq T''(n)$. Invoking the Master theorem, we see that $T'=\Theta(h)$ and $T''=\Theta(h)$ for the same function $h$, and so $T = \Theta(h)$ as well.
Now let's relax the assumption that $f$ is monotone. Suppose that $f = \Theta(g)$ for some monotone function $g$. Thus $cg(n) \leq f(n) \leq Cg(n)$ for some $c,C>0$ and $n$ large enough. We assume for simplicity that $n=0$; the general case can be handled as in the previous paragraph. Again we define two recurrences $T',T''$ by replacing $f$ with $cg,Cg$ (respectively). Once again the Master theorem will give the same result (up to constant multiples), which is also identical (up to constant multiples) to what we would get by solving the original recurrence only on powers of two.


Proving that $A=\{w_{2i}|w_{2i}\not\in L(M_i)\}$ is not Turing-recognizable

Lets reformat your language $A_D$ to say $A_D=\{ \langle M \rangle| \; \text{M is a Turing machine ( TM ) and does not accept }\langle M \rangle\}$. Here $\langle M \rangle$ means encoding of Turing machine $M$, and I assume the inputs are always valid encodings TM's ( as you can always check if a string is a valid encoding or not ). Now say there was a decider for $A_D$, let it be $D$. Now if you give input $\langle D \rangle $ to $D$ it has to halt ( we assumed it is a decider ) and either reject or accept. If it accepts it, it means $\langle D \rangle  \in A_D$ and thus $D$ does not accept $\langle D \rangle $, which is a contradiction. If $D$ reject $\langle D \rangle $ it means $D$ accepts $\langle D \rangle $ acccording to definition of $A_D$ which again is a contradiction. Either ways it is a contradiction, thus our assumption that $D$ exists is not correct and $A_D$ is undecidable ( this proof is related to Cantor's diagonal method ) .

This logic cannot be applied to prove $A_D$ is not  Turing recognizable. I leave the reason for you to figure out ( hint: no assumption about halting on all inputs is made ).

I will prove non recognizability  of a general language ( which implies undecidability  ) instead of $A_D$ and the one you specify in your question.
$L=\{  w | \; f(w) \;\text{ is a valid encoding of some Turing machine where } f \; \text{is some computable function and the Turing machine given by } \; f(w) \; \text{does not accept} \; w\}$
( $f$ is such that  for every TM encoding $\langle M \rangle \exists w $ s.t. $ f(w)=\langle M \rangle$ )
Now suppose $L$ was Turing recognizable, let the TM  be $R$. We construct another Turing machine $H$ which given an input $w$ first finds $f(w)$ ( again assuming it is a valid encoding of a TM, if not $H$ can directly reject ). Then $H$ gives $w$ to $R$ and simulates $w$ on $f(w)$ in parallel. If $f(w)$ accepts $w$ $H$ rejects, if $R$ accepts $w$, H accepts. This way you are able to decide language $L$ which is undecidable. You can prove $L$ is undecidable yourself ( see when $f$ is the identity function, $L$ reduces to $A_D$ which is undecidable ).
I leave it for you to figure out how non recognizability of $L$ can be used for proving that of your languages.


How to find the Big-O for finding combinations of balanced parentheses?

Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses.

Bertrand's formula states that for each $a$, the number of such arrangements is
$$
\frac{(a+1)-(k-a)}{k+1} \binom{k+1}{a+1} = \binom{k}{a} - \binom{k}{a+1}.
$$
Hence the number of nodes at level $k$ is
$$
\sum_{\lceil k/2 \rceil \leq a \leq \min(k,n)} \left[\binom{k}{a} - \binom{k}{a+1}\right] = \binom{k}{\lceil k/2 \rceil} - \binom{k}{\min(k,n)+1}.
$$
Summing this for $k$ from $0$ to $2n$, we obtain
$$
\sum_{k=0}^n \binom{k}{\lceil k/2 \rceil} + \sum_{k=n+1}^{2n} \left[\binom{k}{\lceil k/2 \rceil} - \binom{k}{n+1}\right].
$$
It follows from Stirling's approximation that this is $O(4^n/\sqrt{n})$, and conversely, just considering $k = 2n$ (corresponding to Catalan numbers), this is $\Omega(4^n/n^{1.5})$.

We are however not done, since the numbers involves are quite large — on the order of $n$ bits. Therefore arithmetic takes super-constant time. We still get a running time of $\tilde{O}(4^n)$.

Now for space complexity. The recursion tree is $n$ levels deep, and at each level we might be storing up to $n$ bits of information, giving an upper bound of $O(n^2)$ bits. This should be quite tight.


Take all $2n$ starting and ending times and sort them, then walk through the list in sorted order, increasing a counter at each "starting" time, and decreasing the counter at each "ending" time.  On every counter increase, check whether this is the highest the counter has gone so far, and if so update the best-so-far event.


Given a binary matrix, how to find the starting coordinates of a sub matrix?

Here is one approach.  It won't survive JPEG compression, though, so probably you can do better.

Let $m$ be an integer large enough that $2^m$ is significantly larger than both the width and height of the matrix.  Choose a maximum-period $m$-bit LFSR; this generates a sequence of bits of length $2^m-1$, say $s_1,s_2,s_3,\dots,s_{2^m-1}$, where each $s_i \in \{0,1\}$.

Now, construct the original matrix as follows: at coordinate $(i,j)$, the value will be $s_i \oplus s_j$.

Given a submatrix, we can find coordinates as follows.  First note that given a consecutive range of the sequence $s$ of length at least $$, we can find where in the sequence it was taken from.  In other words, given $s_i,s_{i+1},\dots,s_{i+m-1}$, we can recover the value of $i$.  (How?  Simply trying all possible values of $i$ will work; one property of LFSR sequences is that the map $i \mapsto (s_i,s_{i+1},\dots,s_{i+m-1})$ is bijective, so $i$ will be uniquely determined.)

Now given the submatrix, we'll try to find the coordinates of its upper-left corner, say $(i,j)$.  We'll start by looking at the first row of the submatrix, and examine the sequence of values that appear in its grid.  This either takes the form $s_i,s_{i+1},s_{i+2},\dots$ or $s_i \oplus 1, s_{i+1} \oplus 1, \dots$ according to whether $s_j=0$ or $s_j=1$.  We can try both possibilities for $s_j$, and get two candidates for $i$.  Then we look at the first column of the submatrix, and obtain two candidates for $j$ in the same way.  This gives us two candidates for $(i,j)$, we can check which one is correct by looking at a few other positions in the submatrix.

Then, you can recover the coordinates of its lower-right corner in the same way.

All in all, this will enable you to recover the coordinates of the submatrix, as long as the submatrix is at least $m$ pixels wide and $m$ pixels high.

There are other ways as well.  For instance, one very simple approach is to fill in the original matrix randomly, and remember how you filled it in.  Then given a submatrix it is straightforward to find where it came from (e.g., by checking all possibilities; this can be sped up by precomputing a hash table).

In practice, if you plan to print out the original matrix and then take a scan or photo of it, then you might want a different approach that is more robust to the kind of transformations that will typically occur during printing and scanning.  That will lead to a very different kind of problem.  So if you want to know about how to do that, you should probably ask a separate question focused on those considerations.


It is a strange grammar that while is combined with else in your pseudocode. There is such grammar in Python but it is obviously not the case. I guess you mean

s = n
while (s > 4)
  if (s is even)
      s = s / 2
  else
      s = s - 1

Anyway, let's start with your recursion formula.

Consider $n>4$. Note if $n$ is even, $S(n)=1+S(n/2)=1+S(\lfloor n/2\rfloor)$, and if $n$ is odd, $S(n)=1+S(n-1)=2+S((n-1)/2)=2+S(\lfloor n/2\rfloor)$. So anyway, for $n>4$ we have

$$1+S(\lfloor n/2\rfloor)\le S(n)\le 2+S(\lfloor n/2\rfloor).\quad (1)$$

Suppose $2^{k-1}\le n < 2^k$, you can prove

$$ k-2\le S(n)\le 2(k-2).$$

using mathematical induction (the formal proof is  left to you as an exercise). So $S(n)=\Theta(k)=\Theta(\log_2 n)$.

From (1) we can write $S(n)=S(\lfloor n/2\rfloor)+f(n)$ where $1\le f(n)\le 2$, i.e. $f(n)=O(1)$. Then Master Theorem applies.


Algorithm to convert decimal number to binary

Just converting the comment into a short answer:

$7 = \text{int}(\log_{2} 236)$. Generally, $p = \text{int}(\log_{B}V)$.

As other people pointed out, this algorithm is needlessly complicated and not practical; it is not easy to calculate $\log_B V$ for large $V$ by pencil and paper. Instead, use the other algorithm which is also mentioned in the article you are reading:

From decimal to binary

Step 1: Check if your number is odd or even.
Step 2: If it's even, write 0 (proceeding backwards, adding binary digits to the left of the result).
Step 3: Otherwise, if it's odd, write 1 (in the same way).
Step 4: Divide your number by 2 (dropping any fraction) and go back to step 1. Repeat until your original number is 0.


How does (non)deterministic time relate to verifiability?

Here's some intuition for the equivalence proof

$(\implies)$: Suppose we have a non-deterministic Turing Machine $M$ that solves a problem $P$ in polynomial time. When we run $M$ on some accepted input $x$, we make a bunch of decisions non-deterministically, essentially choosing an execution path. If we record each of those choices, this gives is a string with is polynomial in the size of $x$ (since we know $M$ runs in non-deterministic polynomial time). Then the trace of running $M$ on $x$, with each decision point, is a certificate for $x$. We can follow the steps again and check that any string represents a valid run on $M$, and see whether it ends in a YES or NO state.

$(\impliedby)$: Suppose we have a verifier which takes a string $c$ and input $x$ and checks if $c$ is a valid certificate that $x$ is accepted by problem $P$, where  $|c| \leq |x|^k$ for some fixed $k$. Then we can make an NTM which looks at any $x$ and determines whether it is in $P$ by "guessing" non-deterministically guessing a certifier $c$ of length less than $|x|^k$ and running the verifier on that.

EDIT: to apply this to $EXP$ and $NEXP$, just replace the word polynomial with exponential and change the bound on $c$, and the rest should still work. It doesn't really apply to classes like $PSPACE$, since it's not defined in terms of non-deterministic machines. Not being able to make these kinds of guesses are what makes PSPACE harder (as far as we know) than NP.


Random uniform sampling of position restricted permutations

I'll answer both the question as it currently stands, and the original version of the question.

The current question

Your question is basically asking for a way to sample uniformly at random from the set of perfect matchings of a given bipartite graph.  In particular, we have $N$ nodes on the left side corresponding to the $N$ rows of $R$, and $N$ nodes on the right side corresponding to the $N$ columns of $R$.  Draw an edge between node $i$ (on the left) and node $j$ (on the right) when $R_{i,j}=1$.  This gives a bipartite graph $G$.  Now there's a bijection between the perfect matchings of $G$ and the permutations in $\Pi_R$, so we want to sample uniformly at random from the perfect matchings of $G$.

The following question refers to algorithm for exactly that problem: Sampling perfect matching uniformly at random.  In particular, there are existing algorithms that approximate sampling from the uniform distribution (i.e., their distribution is almost uniform).

The original question

Originally, the question imposed the stronger restriction that $\pi(i)=j \Longleftrightarrow R_{i,j}=1$.  Here's the solution to that version of the problem.

Theorem. If $R$ is a permutation matrix, there is a single permutation $\pi$ that is compatible with $R$.  If $R$ is not a permutation matrix, there is no permutation $\pi$ that is compatible with $R$.

Recall that a permutation matrix is a matrix that has exactly one 1 in every row and every column.

Proof of theorem. Consider any row, say row $i$.  If it is all zeros (has no $1$), then there's no matching permutation ($\pi(i)$ has to equal something).  If it has two or more $1$'s, there is no matching permutation (you can't have $\pi(i)=j$ and $\pi(i)=k$ where $j\ne k$).  So for there to be a matching permutation, the row must have exactly one $1$.  Since the row $i$ was arbitrary, this must be true of all rows.  By symmetric, the same is true for all columns.  QED.

You can easily recognize whether a matrix is a permutation matrix or not.  Given a permutation matrix you can easily recover the corresponding permutation.  Therefore, an algorithm to do what you want is trivial.  The algorithm either outputs nothing (if $R$ is not a permutation matrix) or always deterministically outputs a single permutation (if $R$ is a permutation matrix).

For the example $3 \times 3$ matrix you gave in your question, there is no permutation that is consistent with that matrix.  Your matrix has $R_{2,1}=1$ and $R_{2,2}=1$.  By your conditions, this implies the requirements that $\pi(2)=1$ and $\pi(2)=2$.  However, $1\ne 2$, so it is impossible to have a permutation $\pi$ that satisfies both of these requirements.


Understanding proof for Busy Beaver being uncomputable

Just for the completeness, I will present my proof that shows uncomputability of BB function.
The structure of a correct proof would look something like the following.

Construct a universal Turing machine U that simulates any other Turing machines but writes ‘1’ on the output tape for every step of the simulation.
For any Turing machine M, there is an encoding 〈M〉for U. We create a new Turing machine by adding new states in U which first writes〈M〉on its input tape and runs it on U. Call this new Turing machine UM.
Let n be the number of states in UM, and m be the number of states in M. We can see that BB(n) upper-bounds the number of 1’s outputted by UM and also upper-bounds the maximal number of steps run by the halting Turing machine with m states. Hence, S(m) <= BB(n), where S(m) is the maximal number of steps run by a halting Turing machine with m states.
Given a Turing machine of size m, we can always determine corresponding value for n.
If there is any function that always upper bounds S, it is uncomputable as it will contradict with the result from the halting problem. (Run a Turing machine that many steps to determine whether it halts or not)


Union of halting-like problem and non-halting-like problem

Let's write formally what $L$ and $\overline{L}$ are:

$$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$
The latter is confusing, so let's rearrange it:

$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \wedge M(w) \mbox{ halts}) \vee (b=0 \wedge M(w) \mbox{ does not halt}) \}$$

(Note that we ignore malformed inputs, but that can be easily circumvented and does not effect the answer).

From this, you can easily see that $L$ and $\overline{L}$ are basically the same idea -- the bit at the end determines whether you're looking at the halting problem or at its complement. In either case, neither $L$ nor its complement are recursively enumerable.

One thing that can trigger you to suspect this is the answer, even without formally writing $\overline{L}$, is the fact that both the halting problem and its complement easily reduce to $L$. Thus, $L$ is not recongnizable nor co-recognizable, and so neither is its complement.


Ok I think I have found it.

Let $A$, $B$ and $C$ such that $A \leq_Q B$ and $B \leq_Q C$, respectively by the recursive functions $f$ and $g$. Let
    \begin{align*} h : x,y \mapsto & \text{ find } b \in W_{f(x)} \text{ and } c \in W_{g(b)} \text{ such that } y = c \\
  & \text{ return } 0
\end{align*}
By $s$-$m$-$n$ we have a recursive function $s$ such that $\varphi_{s(x)}(y) = h(x,y)$.

Assume $x \in A$. If $y \in W_{s(x)}$, then $\exists b \in W_{f(x)}$ and $\exists c \in W_{g(b)}$ such that $y = c$ so $b \in B$ and $c \in C$ by the assumed reductions, so $y \in C$ and $W_{s(x)} \subseteq C$.

Now if $x \in \overline{A}$, then $\exists b \in W_{f(x)} \cap \overline{B}$ and $\exists c \in W_{g(b)} \cap \overline{C}$, so $h(x,c)\downarrow$ and $c \in W_{s(x)} \cap \overline{C}$.

So we can conclude $A \leq_Q C$.

Let me know if you think there's a problem with this.


Appreciation of the 5 state process model

a) A process does not necessarily have to terminate, it only reaches the terminated state if it exits voluntarily. If a process has no exit statement (e.g. a server), it would never reach the terminated state unless killed by the OS. Other ways for a process to never reach termination include not being scheduled when ready because some other process with higher priority is always scheduled before it (starvation), or being stuck in the blocked state waiting for some resource but never getting it, for example, trying to obtain a lock (deadlock/livelock).

b) If we cannot check wether the process has reached the terminated state or not, we can never free up its resources (stack, data, process table entry). It is important for the OS to be able to tell what state a process is in for the scheduler to work properly. If a child process terminates and reaches the 'Z' state, the operating system needs to have this information when it tries to pick a process to schedule. This prevents processes that no longer need CPU time from being scheduled. If the OS did not have this state information available at all times, the implications would be wasting memory space and CPU time.

I suggest reading up on the wiki for the
exit,
wait and
fork syscalls for better understanding :)


How can $A \cup B$ be decidable if $B$ is undecidable?

If $A=\{0,1\}^*$ then $A\cup B=\{0,1\}^*$, regardless of what $B$ is. $\{0,1\}^*$ is decidable, and choosing to express it as something involving undecidable things doesn't change that fact.

The question "Is $w$ in $A\cup B$?" is equivalent to "Is at least one of the following statements true? $w$ is in $A$; $w$ is in $B$; $w$ is in both $A$ and $B$?" In the case $A=\{0,1\}^*$, we can answer "Yes, $w$ is in $A$" and the rest of the questions are irrelevant.  It doesn't even matter if we can't answer "Is $w$ in $B$?", because we don't need to.

Here's a more practical example that might help. Suppose I give you a number $x$ and ask you "Is $x\in\text{Integers}\cup\text{Primes}$?" Figuring out if a large number is prime is quite difficult, but you can easily answer my question by checking if $x$ is an integer. You can ignore the "prime" part completely.


Both CDCL and DPLL need exponential time in the worst case. I am not sure if it can be proved that CDCL is always faster than DPLL on every instance, but there is major empirical data suggesting it dominates. For a nice, short overview see the presentation Boolean Satisfiability Solving: Past, Present & Future by Joao Marques-Silva. He also has quite a few related talks online, see here.

CDCL is the dominating solver among all modern solvers. I would claim CDCL does indeed always dominate, and that is because it's basically a DPLL-based procedure, but with additional enhancements. It uses information gained during the search, restart strategies, special data structures, and so on.

There are instances that make all the known DPLL-like algorithms run in exponential time. For example, Alekhnovich et al. [1] exhibit such a family of 3-SAT instances. For more information on satisfiability, both theoretical and practical, I think one of the best sources are the Handbook of Satisfiability [2] and the regular International Conferences on Theory and Applications of Satisfiability Testing, known as SAT.

[1] Alekhnovich, M., Hirsch, E., and Itykson, D. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. JAR, 35(1-3), 51-72, 2005.

[2] Biere, A., Heule, M., van Maaren, H. and Walsh, T. (Eds.). Handbook of Satisfiability. IOS Press, 2009.


Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Hint: Use some data structure that allows insertion, deletion, and search in logarithmic time to maintain a snapshot of the $k$ preceding elements, and use it to determine whether the next element is a $k$-maximum in time $O(\log k)$.


Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?

Some mathematicians find it natural to substitute for the variable in the denominator of a derivative, writing things like $\frac{d \log V}{d\log p}$. This suggests that the $x$ in the denominator $\frac{dy}{dx}$ is neither bound nor binding nor a symbol.

Rather $\frac{dy}{dx}$ seems to be an operation on "variable quantities" $y,x$ requiring some side conditions, similar to how the usual division $a/b$ requires $b\neq 0$, or how the operation $\frac{v}{v_1^0\ldots v_i^1\ldots v_n^0}$ in my comment requires $v_1,\ldots,v_n$ to be linearly independent and $v$ to lie in their span.

I suspect that the side condition for $\frac{dy}{dx}$ should be analogous: $dx$ needs to be linearly independent and $dy$ has to be a multiple of $dx$.

With these side conditions we are not allowed to substitute a constant for $x$ in $\frac{dy}{dx}$ since then $dx=0$ and so $dx$ is not linearly independent. That would explain why we are not allowed to write $\frac{d x^2}{d3}$ or to take the derivative of equation $x=0$ w.r.t. to $x$ to conclude $1=0$.

I'd be interested in hearing if someone sees an immediate problem with this interpretation.

(I see some subtlety in the fact that $d(x|_{x=3})$ cannot mean the same as $(dx)|_{x=3}$, since otherwise I'd expect $\frac{dy}{dx}|_{x=3}$ to be the same as $\frac{d(y|_{x=3})}{d(x|_{x=3})}$ which would not be allowed by the side condition. On the other hand, that is not so strange from a differential geometric point of view if we read $|_{x=a}$ as restriction: there is a difference between restricting a differential form and pulling it back. But I need to think more about this.)


Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

If you use the pumping lemma on the word $w=0^{p^2} 1^{p^3}$, consider the partition $w=xyzuv$, where $|yzu|\le n$ and $|yu|>0$ ($n$ being the length of $w$).
It is easy to prove that from all the cases (that is, from all the possibilities for $y$ and $u$), the only non-trivial case is when $y=0^i$ and $u=1^j$, in which case the hint you mentioned finishes the job.


How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$?

You cannot directly prove $f(n)^d$ is $O(b^n)$ from the fact that $f(n)$ is $O(2^n)$. For example, $2^n$ is $O(2^n)$, but $(2^n)^d$ is not necessarily $O(b^n)$.

So forget the fact that $n$ is $O(2^n)$. You should prove $n^d$ is $O(b^n)$ directly.

You may find a correct proof here.


Quickly determine if insertion sort or quick sort is better

Quicksort is better unless the number of items in the wrong place is O(log n) only. There is a simple sorting algorithm that runs in O (n) if the number of items in the wrong place is a bit less than O (n / log n): Scan the array, and whenever two items are out of order put them into a separate array. Sort the separate array with Quicksort, then merge both arrays.
This will be not O(n), but faster than Quicksort, if the number of items in the wrong place is much lower than n, say O (n / sqrt(log(n)). The scanning + merging is obviously O(n). If t items are in the wrong order, then sorting them using Quicksort takes O (t log t), so it's O(n) in total if (t log t) = O(n), and asymptotically faster than Quicksort if t = o(n).


A buffer is usually used only as temporary storage while something is being transmitted or read. For instance, you might be reading data from a slow-response external storage medium (e.g., a CD) and processing it continuously. In this setting, the first process reads chunks of data from the medium and writes it to the buffer on demand, while the latter reads from the buffer as if it were reading from storage directly. This avoids deadlocks in that the latter process does not need exclusive access to the medium.

In contrast, RAM is simply what is used as main memory for the processes in a general-purpose computer. There might be several buffers not only in RAM but also in other memory units. Saying that RAM is used for "temporary storage" can be rather misleading since "temporary" here actually means "until the process using it is inactive or extinct" (and not "until the data is not needed anymore").

In summary, a buffer is an abstracted concept (and only really exists at the software level); RAM is a concrete type of storage technology.


Similarly as $O$ notation which "ignores constant factor", $O^*$ notation "ignores polynomial factor" that is: $f(n) = O^*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ for $n$ large enough. This is mainly used to compare functions which are growing exponentially, in which case polynomial factors are less important.

This notation is not as standard as $O,o,\Omega, \omega$. Sometimes, this notation or $\tilde{O}$, as observed by @Raphael, is used to ignore polylogarithmic factor when people focus on ptime algorithms.


Complexity to insert subset of array to minimize order inversions

Since this problem is basically about merging the element not in $B$ with element in $B$ to minimize order inversions, this answer will be focused on the following problem. The algorithm and analysis hereof can be extended to the problem in the question easily.

$A$ is a sorted array of $n$ integers. $B$ is an array of $m$ integers. $n\gt0, m\gt0$.
How can we merge them into one array efficiently without changing the order of elements in $B$ so that the result array has minimum number of inversions?

As OP indicated, the problem above can be done trivially in $O(nm)$. "For each element in $A$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it."  The OP also noted that in the result array, we should keep elements that come from $A$ sorted.
The observations above given by OP lead to the following recursive helper algorithm that gives the indices where elements of $A$ should be inserted into $B$. The simple idea is "binary insertion". That is, insert the middle element into $B$, then recurse.
Pythonic notations will be used.
Input: $A$ is an array with $A[sa\colon ea]$ sorted. $B$ is another array with subarray $B[sb\colon eb]$ specified. $I$ is an array of the same length as $A$.
Output: updated $I$, such that if for each element $A[i]$ in $A[sa\colon ea]$, we insert $A[i]$ right before $B[I[i]]$, keeping the original order of $A$ among themself, the inversion number of $A[sa\colon ea]$ merged with $B[sb\colon eb]$ is minimized.
Procedure:

If $sa\ge ea$, return.
Let $ma = (sa + ea)//2$
Scan through $B[sb\colon eb]$ to find the indice $mb$ in range($sb\colon eb+1$) such that if we put $A[ma]$ right before $B[mb]$, we will have minimum number of inversions that consist of $A[ma]$ and an element in $B[sb\colon eb]$.  (Or, any one of those optimal indices).
Let $I[ma] = mb$.
Call this procedure with $A[sa\colon ma-1]$, $B[sb\colon mb]$ and $I$.
Call this procedure with $A[ma+1\colon sb]$, $B[mb\colon eb]$ and $I$.

To solve the initial problem, we will do the following.

Initialize $I$, an array of $n$.
Run the algorithm above with $A[0\colon n]$, $B[0\colon m]$ and $I$
Merge $A$ with $B$ according to $I$.
Return the merged array.

If implemented properly, the algorithm above runs in $O(m\log n + n\log m)$ time. It can be proved that $O(m\log n + n\log m)$ time is optimal. It uses $O(n)$ auxiliary space.
The algorithm here is, basically, doing the same thing to find the same arrangement as in OP's pesudocode. Only more efficiently.
It is a nice exercise to prove the correctness of either algorithm.

If the given array $A$ is not sorted, then sort it at the start of the algorithm. That will add $O(n\log n)$ to its time-complexity.


Get indexes of unique elements in two different arrays in linear time

Given the following assumptions:

Since the meaning of the $=$ operator was not defined, we assume

  $i≠j⇒x_i≠x_j$

  ...

  The $x_i$ values are not necessarily integers or string, but any type of elements.

are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each element is a single word, perhaps a distinct pointer to some arbitrary object.

We assume that, given an arbitrary address, reading/writing at that address takes constant time.
We assume that adding 2 addresses takes constant time.
We assume that a pointer to unbounded memory is available in n time.

Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space.

Then:

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine,
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result

...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of every non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.


Height of epsilon-balanced binary search tree

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has length $\ell$ (edges), then the last node contains at most $\epsilon^\ell n$ nodes, and so $\epsilon^\ell n \geq 1$, or equivalently, $\ell \leq \log_{1/\epsilon} n$.


Normally in speech-to-text we don't already have a perfect segmentation into words, which is why we often use the HMM to match the entire speech sentence.  Also, this way the HMM can take into account probabilistic information on the distribution of word bigrams (and even trigrams).  If you already have a segmentation and you are sure it is correct, then you can use the HMM to match just the word, if you like.  But getting a reliably correct segmentation is tricky, given how people speak in practice, so you might want to check how accurate your segmentation is before relying upon it.

Either GMM + HMM or DTW would be a reasonable approach.

A very simple approach would be to download an existing speech-to-text tool and use it on those sentences, instead of trying to build something yourself.


is it possible to have a mapping reduction between 2 NP complete languages?

You certainly can! This is how NP-completeness works: every NP-complete problem can be mapping-reduced to every other NP problem, by definition.

For example, consider the Boolean Satisfiability Problem: given some assortment of variables joined together by AND, OR, and NOT, is there any assignment of True and False to those variables that will make the whole thing evaluate to True? This problem is NP-complete.

Consider also the 3Sat problem, a convenient one to use in all sorts of NP-completeness proofs. This is the same as the Boolean Satisfiability Problem, except that the input is a series of clauses joined by AND, where every clause consists of exactly three terms joined by OR, and a term is either a variable or the negation of a variable.

Since every 3Sat input is a Boolean formula, 3Sat can be trivially reduced to Boolean Satisfiability. And there's a method of converting any Boolean Satisfiability problem into an equivalent 3Sat input in polynomial time.

Therefore, $\mathrm{3Sat} \leq_M \mathrm{BooleanSatisfiability}$, and $\mathrm{BooleanSatisfiability} \leq_M \mathrm{3Sat}$.

(It's easier to understand this with general problems, but this can be trivially rephrased to work with languages, as in your question: let the language $\mathrm{BooleanSatisfiability}$ consist of the binary encodings of inputs for which the Boolean Satisfiability Problem should return true, for example.)


How to represent a 0-valid boolean formula?

The constraints of a $0$-valid formula can be more general. All we know about them is that they are satisfied if all variables are $0$. For example, a constraint could be $x = y$ (i.e. $(x \land y) \lor (\lnot x \land \lnot y)$). Your form is not general enough, since it only considers constraints of the form $\lnot x_1 \lor \dots \lor \lnot x_\ell$.

While your formulation doesn't capture the problem of determining the most positive solution for a $0$-valid CSP, it is equivalent to an even more classical problem, set cover. In particular, your problem is NP-complete.


Feedback polynomial of 7-bit Linear Feedback Shift Register

The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.


Deterministic finite automata that accepts the only the string "aabb"

Your purpose is to detect a substring $aabb$. When the FA is in state $D$ it already has read $aab$ (pay attention that in order to get to $D$ from the start state the FA must read $aab$ or $a\dots aab$). While in state $D$ there are two possible inputs: $a$ or $b$. If it reads $a$ it enters the state $B$ because it already has $a$ (it remains to read $abb$). On $b$ it enters the accept state. If on $a$ it stays on $D$ then it would accept a wrong string, for example, $aabab$ which does not contain $aabb$ as a substring. In other words, on $a$ you should send it back to the state $B$ as if FA switches from state $A$ into state $B$.


How can I calculate optimal batch sizes for calls to an external server?

Here's the simplest model I can think of.  Assume that each command takes $\beta$ seconds to complete, and it takes $\alpha$ seconds to create a connection.  Then I would expect that it would take $\alpha+\beta k$ seconds to complete a batch of size $k$.  If there are $N$ commands in total, then we'll need $N/k$ batches.  With 6 concurrent TCP connections to the server at a time, this means it'll take $N/(6k) \times (\alpha + \beta k)$ seconds to complete all of the batches.  As a function of the batch size, this is

$$f(k) = {\alpha + \beta k \over 6k} N.$$

You can find the optimal batch size by finding $k$ that minimizes $f(k)$, which can in turn be done using calculus by taking the derivative and setting it to zero: $f'(k)=0$.  Note that

$$f'(k) = {6\beta k - 6(\alpha + \beta k) \over 36k^2} N
= {\alpha \over 6k^2} N.$$

Setting this to zero, we find that $f(k)$ is minimized by taking $k$ as large as possible; in the limit we have $\lim_{k \to \infty} f(k) = \beta/6 N$.

Obviously, this is not what you observe empirically, which suggests that this model is not accurate.  I suggest as a next step you start to brainstorm why the model might be inaccurate or what factors it might be overlooking.  You might also want to measure and plot some additional metrics, e.g., the average time it takes for each batch to complete (as a function of batch size, i.e., the time between starting execution of command 0 from batch $i$ to starting execution of command 0 from batch $i+1$).


Algorithm to enclose a 2D-gridbased-room efficient

This is a graph cut problem.

Build a graph with one vertex per square.  Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step).  Add an extra "source" vertex $s$, and an edge from $s$ to each starting point (yellow/green block).  Add an extra "sink" vertex $t$, and an edge from each exit to $t$.

Now your mission is to find a minimum vertex cut that separates $s$ from $t$, i.e., a subset $S$ of vertices such that every path from $s$ to $t$ traverses at least one vertex of $S$.  There are standard algorithms for the minimum vertex cut problem, which you can find by searching the literature.

See also https://en.wikipedia.org/wiki/Vertex_separator and https://cstheory.stackexchange.com/q/2877/5038 and https://cstheory.stackexchange.com/q/29464/5038.

You'll need to add the extra constraint that the subset $S$ cannot include $s$ nor $t$, but I expect it should be easy to incorporate this constraint into standard algorithms for vertex cut.


The most efficient algorithm for finding the highest valid number for an API

Assuming $1$ is always a valid ID, you can solve your problem in about $2 \log v$ queries where $v$ is the maximum value by using exponential search and binary search.
Query the API using powers of two ($2,4,8,\dots$) until you find the smallest power of two $x$ such that $x > v$. Clearly $x \le 2v$.
This requires up to $1+\lceil \log_2(v) \rceil$ queries.
Then use binary search in the range $[v-1, 2v)$ to find the exact value for $v$. This requires at most $\lceil \log_2(1+v) \rceil$ queries.


Resource Reservation: No Greedy Approach?

Your algorithm is correct when all resources are interchangeable. For example, the resources are 100 memory units.

However, it may not return the right result when the resources are not of the same kind. One way to find a counterexample is to search for counterexample of the greedy algorithm on the maximum independent set is to, uh, search online. One counterexample I found is the following, where vertex $C$ is selected first.

.

User j_random_walker proposed the following strategy to figure out a counterexample, where the tip in the last statement is added by me.

  Figure out how to force your algorithm make the "wrong" choice in the first step: Since your algorithm always chooses the process with the fewest resource requests first, that means you have to design the problem instance so that this choice can only lead to suboptimal solutions. Work backwards to discover constraints: Clearly if the optimal solution has all 2 processes, then they can't have any conflicts, so any order of choosing them will give the same answer. So the smallest counterexample must have at least 3 processes. We will not consider processes that only request one resource; it cannot be wrong to included those processes.

Here is the smallest counterexample on which the greedy algorithm might fail, which has 3 processes and 4 resources. Process $P$ requests resources $a$ and $b$. Process $Q$ request $a$ and $c$. Process $R$ request $b$ and $d$. When the greedy algorithm select $P$ first, it cannot select any more process.

Exercise. Find a counterexample on which the greedy algorithm will always fail.


Computability of Kolmogorov Complexity of Turing-Incomplete language

The important thing to notice is that your programs always halt. This makes computing the Kolmogorov complexity an easy task, since given a string $w$, you can go over all possible programs of length $\le|w|+2$ to find the shortest program whose output is $w$. The upper bound $|w|+2$ follows from the fact that for any string $w$, "w" is a program whose output is $w$.
In fact, you could probably compute the complexity of a string in polynomial time, since compression is only possible in the case of repetitions (you can not take advantage of a more general structure). Something along the following lines should work $KC(w_1...w_n)=\min\limits_i \big(KC\left(w_{i+1}...w_n|w_i\right) +KC(w_1...w_i)\big)$, where $KC\left(w|w'\right)$ is just $KC(w)$ if $w'$ is not a prefix of $w$, and $KC(w'')+O(\log j)$ otherwise where $w=w'^jw''$ and $j$ is the maximal number satisfying this. The point is that you only need to compute the complexity of substrings of $w$, of which there are $O(|w|^2)$.


What problem cannot be solved by a short program?

For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose.

There are some interesting results, however. Encoding of randomly generated strings will always require a cost proportional to the size of the string. Pigeonhole principle tells us there will always be some functions, in any fixed language L, that cannot be expressed in a space smaller than a complete enumeration of all the cases. And Blum's size theorem tells us that, for a total language, there are always functions you can encode larger than an arbitrarily chosen blowup factor compared encoding the same function in a Turing complete language.


Do Higher Order Functions provide more power to Functional Programming?

In a functional programming language that is powerful enough (for example, with data types to implement closures) you can eliminate all uses of higher order by the transformation of defunctionalization. Since this method is used to compile this kind of language, you can reasonably assume that this does not affect performances and that in this setting higher order does not make the language any less powerful. However it does affect how to write code.

However if the language is not powerful enough, then yes, higher order does provide expressive power. Consider the lambda-calculus: without any higher-order function, it really can't do anything, mostly because the most basic data types (integers, booleans) are implemented using functions.

In conclusion, it really depends on the language.

Above is my answer. Below, a comment about a usual assumption on imperative languages.

  about an algorithm that on a non-lazy functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

I would like to see this reference. The usual assumption is that an access to a array of length $n$ in a RAM is in time $O(1)$ and the equivalent in pure FP is in in time $O(\log n)$. That is not entirely true: the access time in a RAM is in $O(\log m)$ where $m$ is the size of the memory. Of course, $m≥n$. In practice accessing an element of an array is much faster. A reason would be that $m$ is bounded but... so is $n$!

EDIT: thank you for the link (the link for the paper about laziness is not available, here is another one). As posted in the comments and above in my answer, the model of RAM is a little unfair to pure FP by providing $O(1)$-time look-ups even when the size of one address is not bounded. I am yet to understand how the lazy trick works but I think it is important to note that this is only for this particular problem.


What is an array of arrays called when all arrays have the same size?

In C# world there are 2 kinds of array declarations, and 2 names for it:

Jagged:

[
  [ 1, 2, 3 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2 ]
]

Rectangular:

[
  [ 1, 2, 3, 4 ]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 4, 4 ]
]


Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas?

Yes.  The quantifiers can be ignored for the sake of the test since a quantified Horn formula is syntactically identical to an unquantified one except for the quantifiers.  That is, a quantified Horn formula still consists of only of clauses with zero or one positive literals.  The test only determines whether any combination of polarity flips could produce a Horn formula.

In order for the test to be useful for quantified formulas, it only remains to show that a quantified formula can be renamed and remain equisatisfiable with the original formula.

For unquantified formulas renaming a variable leaves satisfiability unchanged because a solution to the renamed formula is the same as a solution to the original formula except that the renamed variable has its value negated in compensation for the polarity change.  The same is true for existentially quantified variables in a quantified formula, and for the same reason.  For universally quantified variables, observe that the universal quantifier already requires satisfiability to survive a polarity flip because any solution has to encompass both true and false values for any universally quantified variable.  That is, $\forall x(x)$ and $\forall x(\lnot x)$ offer the same solution constraint; the clause must be satisfied with $x$ taking both the true and false values.


By the very same reason you have mentioned there cannot be such a (many-one) reduction.

Note that if you have two problems, say $A$ and $B$, and $A\le_m B$ then also $\bar A \le_m \bar B$. In fact the same reduction can be used for both statements. So a reduction from ATM to ATM-complement, would also be a reduction from ATM-complement to ATM. And you already know that such a thing does not exist.

If you are however ask for Turing reduction, then the answer is yes. We can ask an ATM oracle and invert the answer to get a Turing machine that decides ATM-complement.


How to calculate whether a parenthesis string is valid using a 2-tape Turing machine?

As others have pointed out, you can use a stack to check for matching parentheses. Such manipulation is the base idea of the shunting yard algorithm by Dijkstra.


Can every two languages in $RE$ be reduced?

Consider the case $L_2 = \emptyset$. This language is clearly recursively enumerable, but the only language which can be reduced to it is itself.

What is true, and follows directly from the definition, that two RE-complete languages reduce to one another.


Your tree is correct. However, it's not the only possible one. Your tree came from the derivation
$$
S\Rightarrow Sa\Rightarrow aSaa\Rightarrow aaaa
$$
a different one would be from
$$
S\Rightarrow aSa\Rightarrow aSaa\Rightarrow aaaa
$$


Are there sorting algorithms that take advantage of a metric space?

For the searching problem (rather than sorting), your idea sounds like interpolation search.  Binary search uses only the binary result of the comparison (less than or not), and runs in $O(\lg n)$ time.  Interpolation search also uses information about how close the values were, and heuristically runs in $O(\lg \lg n)$ time in the average case.  Thus, that's an example where using the extra information can speed up search (at least heuristically).


The graph you describe is called the condensation of the original graph.


Add lines to star with fixed coordinates maximizing smallest angle

I'll describe an efficient algorithm for this problem.

Suppose we have an angle $\theta$, and we want to find out how many new edges we can add, with the constraint that the minimum angle between all pairs of edges must be at least $\theta$.  Then it's not too hard to compute this.  Pick any adjacent pair of existing edges; suppose they are at angle $\gamma$ from each other.  Then you can add $\lfloor \gamma/\theta \rfloor - 1$ new edges between them, while ensuring the minimum angle remains at least $\theta$.  So, sort all of the existing edges by angle, iterate through each pair of adjacent existing angles, count how many new edges you can add between them (using the formula in the previous sentence), and add them up.  That tells you how many new edges you can add, if you want the minimum angle between edges to be at least $\theta$.

Great.  But in your situation, we don't know $\theta$; we just know that we want to add at least $n$ new edges.  So, use binary search on $\theta$ to find the largest $\theta$ such that you can add at least $n$ new edges while preserving a minimum angle of at least $\theta$.  You can do this by choosing a value of $\theta$, computing how many new edges you can add (using the algorithm of the previous paragraph), then increasing or decreasing $\theta$ according to the rules of binary search based on whether the number of new edges you could add was above or below $n$.


Maximum chromatic number of sparse graphs

A graph with $O(n)$ edges has chromatic number $O(\sqrt{n})$, and this is tight.

Suppose first that a graph has $m = O(n)$ edges and chromatic number $\chi$. Take a $\chi$-coloring of the graph. Any two color classes must be connected by an edge, since otherwise we can identify them. Therefore $m \geq \binom{\chi}{2} = \Omega(\chi^2)$, and so $\chi = O(\sqrt{n})$.

To show that this is tight, consider the union of a clique on $\sqrt{n}$ vertices and an independent set on $n-\sqrt{n}$ vertices. This is a graph with $n$ vertices and $\binom{\sqrt{n}}{2} = O(n)$ edges, and chromatic number $\sqrt{n}$.


Does Amdahl's law apply to modern multi-code processors?

Yes, it's still true. The speedup can't be less than zero (if parallelizing your code makes it slower, just run the serial version) or more than 100% (because saving more than 100% of the runtime would make the runtime negative).

Multicore processors are essentially just a matter of terminology changing over time. If you think you have one processor with four cores, Amdahl thinks you have four processors.


What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$

After calculating a few values, you can guess the solution and then easily prove it by induction. Another way to find it is to use "creative cancellation":
$$1 + 7 (T_1 + \cdots + T_{n-1}) = T_n = (T_n + \cdots + T_1) - (T_{n-1} + \cdots + T_1).$$
Hence if you put $S_n = T_1 + \cdots + T_{n-1}$, you deduce
$$
S_n = 8S_{n-1} + 1.
$$
In order to make this homogeneous, take $R_n = S_n + c$:
$$
R_n = S_n + c = 8S_{n-1} + 1 + c = 8(R_{n-1} - c) + 1 + c = 8R_{n-1} + 1 - 7c.
$$
Choosing $c = 1/7$, this gives $R_n = 8R_{n-1}$, and so $R_n = 8^{n-1} R_1$. Now $R_1 = S_1 + 1/7 = T_1 + 1/7 = 8/7$, and so $R_n = 8^n/7$.

It follows that $S_n = (8^n-1)/7$ and $T_n = S_n - S_{n-1} = (8^n - 8^{n-1})/7 = 8^{n-1}$.

Let me conclude by giving a combinatorial interpretation for the recurrence. I will show that $T_n$ is the number of base-8 numbers of length $n-1$. Indeed, any such number is either 0, or starts with a non-zero digit followed by a number $i < n-1$ digits long.


What is meant by $\operatorname{poly}(|F|, n, e)$?

$F=\mathrm{poly}(n)$ means that $F$ is polynomial in $n$, i.e., that there exists a constants $c$ such that $F=\Theta(n^c)$. (sometimes it might mean upper-bounded by polynomial, that is $F=O(n^c)$)

For multiple variable, the same applies, $\mathrm{poly}(n,m)$ means polynomial both in $n$ and $m$, that is, there are constants $c_1,c_2$ and the quantity is $\Theta(n^{c_1}m^{c_2})$. (again, the more common use is for $O(n^{c_1}m^{c_2})$)


After the training phase, is it better to run neural networks on a GPU or CPU?

Running trained artificial neural network is repeated performing of a matrix with vector multiplication and performing the same nonlinear function for each element of a vector. If both operations could be parallelised and vectorised, it is what is GPU well suited for. But it strongly depends on the size of given vectors and matrixes which depend on the size of the neural network. For small nets, CPU could be faster than GPU but it would not matter anyway. For huge nets, GPU would be probably much better suited if algorithm is written right.


Your language is regular, since it is identical to $a\Sigma^*a$.

Indeed, by definition of $L$, every word of the form $a\Sigma^*a$ is in $L$ (take $n = 1$). Conversely, every word in $L$ starts and ends with $a$ (and is of length at least 2), and so is of the form $a\Sigma^*a$.


What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?

To my knowledge, it is an open problem whether the inclusion (c) above
is strict. Some (baby) steps toward solving this problem can be found in

"Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars", IJFCS 2011, http://dx.doi.org/10.1142/S0129054111008118

"On Erasing Productions in Random Context Grammars", ICALP 2010, http://dx.doi.org/10.1007/978-3-642-14162-1_15

"A Sufficient Condition for Erasing Productions to Be Avoidable", DLT 2011.
http://link.springer.com/chapter/10.1007%2F978-3-642-22321-1_39


Algorithm for generate all solutions to a linear Diophantine equation

Your current recursive solution is pretty solid. It is, I believe, about the most efficient recursive approaches we can have for the general situation.

Somehow I prefer the code in you first solution since it is easier to read. All we need to make it correct is to change return [None] to return [] and if None not in res: to if res:

Implementation-wise, we could change it to use an iterative method which should run faster. Also, we could sort $a_i$ in descending order which may improve the listing speed. For example, solutions for $100x_1+100x_2+x_3=1000$ will be found much faster than $x_1+100x_2+100x_3=1000$.

In some special cases, we might be able to speed up the performance. For example, for $15x_1+10x_2+6x_3=100000$, $x_1$ must be a multiple of 2, $x_2$ must be a multiple of 3, $x_3$ must be a multiple of 5. These restriction could help us to improve the speed if they are given or they can be found by factorization easily.


Reduction examples from the strongly NPC problem 3-PARTITION

Prof. Erik Demaine has contributed the wonderful (video) lecture of "Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall'14)". In particular, lectures 2 and 3 are devoted to the reductions (directly or indirectly) from $\textsf{3-Partition}$.

For example, Lecture 2 is concerned with several variants of Jigsaw puzzles. The results are collected in the paper "Jigsaw Puzzles, Edge Matching, and Polyomino
Packing: Connections and Complexity". Its abstract says

  We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles
  are all NP-complete. Furthermore, we show direct equivalences between these three types of
  puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.

Most probably you have known these results and this video lecture. However the wonderful lecture may be also useful for other people.


Converting a digraph to an undirected graph in a reversible way

David Richerby's answer (which was accepted) is good.

I followed his instructions on a simple example digraph, and hope it helps someone.

(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)


For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication

I would assume that a very large product is at least say up to 128 bits (product of two 64 bit integers). In that case there are simple algorithms that calculate the higher and the lower 64 bits of the result, and then you count individually how many bits are set in the higher 64 bits, and how many in the lower 64 bits, and add the two numbers.
If your very large product is the product of say two numbers of $10^6$ bits each, these numbers could each be split into say 15,625 64 bit integers, and the product can be calculated easily with O(n^2) operations for n = 15,625. Or it can be calculated faster but with much more difficulty with a more complicated algorithm. This gives a result of 31,250 64 bit integers, and you can easily count the number of bits set in each integer, and add those numbers.


Why are there two different `until` ($\cup$) semantics in Timed Computation Tree Logic?

The two definitions are equivalent:

As you point out, the second one implies the first, as if $\phi$ holds, then clearly $\phi\vee \psi$ holds.

Conversely, consider a computation that satisfies the first definition, and assume by way of contradiction that it does not satisfy the second definition.
Thus, there exists some time in which $\psi$ holds, and in all previous times, $\psi\vee \phi$ holds. However, there also exists a previous time $d$ where $\psi\wedge \neg \phi$ holds, otherwise the second definition would hols.

Consider the minimal (or infimum) time $d$ for which this happens. Then in that time, $\psi$ holds, and in all previous times, $\psi\wedge \phi$ holds, so the second definition also holds for time $d$, which implies it for any later time.

Another way of looking on it: assume that the second definition doesn't hold, so either $\psi$ never holds, in which case clearly the first definition fails, or there is some minimal time $d$ where $\phi$ doesn't hold, and $\psi$ doesn't hold before $d$. In the latter case, $\phi\vee \psi$ also doesn't hold at time $d$, so the first definition doesn't hold.


Time efficient way to implement Multi-Armed-Bandits?

Store the values in a priority queue.  Typically, in each iteration you will update the value for only a single arm, so you need to change the key of a single value in the priority queue, which can be done in $O(\log n)$ time, where $n$ is the number of arms.  You can also find the argmax in $O(\log n)$ time.


Why does this Pumping Lemma example show irregularity?

$s$ consists of $p$ zeroes followed by, well, it doesn't matter what. $xy$ is the start of $s$ and consists of at most the first $p$ characters of $s$. All of those $p$ characters are zeroes so, in particular, $y$ is all zeros.

Step 4 of your proof is invalid because you can't choose what $x$ and $z$ are. The pumping lemma tells you that, if $C$ is regular, there is some way of writing every appropriate $s\in C$ as $s=xyz$ such that blah, blah, blah. It doesn't tell you that writing $s=\varepsilon y\varepsilon$ will work.


Find minimum time path between two nodes

This can be done in polynomial time.

I'm assuming:

All our your nodes are charging stations.  If not, you can create a new graph that consists of only charging-stations (including start/finish) by finding the all-pairs shortest paths (or just running Dijkstra's multiple times)
The time spent charging is proportional to the distance driven.  If there are eg. paths that are shorter but require larger charges, the problem becomes much more difficult.

The optimal method will be to drive as far as you can on one charge, then fill up your battery only barely enough to make it to the next charging station.  You can do this by adding weight to each edge $\overline{AB}$ equal to the time needed to wait at $A$ while charging, taking into account the battery's initial charge.

We'll do this by altering Djikstra's algorithm.  We need to make two changes to the algorithm

In addition to giving each node a TentativeDistance, also assign it a CurrentBatteryLevel.  This will be the battery level when reaching the node, before doing any charging.  Set it to full for the initial node.
When expanding the current node and calculating the tentative distance to a neighbor-node, add to the edge-weight the amount of time that will need to be spent charging.  If there is enough charge to make it there, this will be 0, and the potential CurrentBatteryLevel for the neighbor-node will be >= 0.  If there is not, it will be the time required to charge the battery enough so that, when you make it there, CurrentBatteryLevel will be 0.

This works because we're still guaranteed to have found the shortest path to a node when expanding it.  This is true because there are no longer paths with shorter charging times, and we're only altering outgoing edges when expanding nodes (never incoming edges), so the assumptions of Dijkstra's algorithm still hold.

Also, since we only increase edge-weights, never decrease, if you have a heuristic you can still use A*.  It must consistent, since our algorithm breaks if we need to expand nodes multiple times.


What's the difference between Computer Science and Informatics?

I deliberately use very common, not necessarily professional resource.

Computer Science

  Computer science is the study of the theory, experimentation, and engineering that form the basis for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale. A computer scientist specializes in the theory of computation and the design of computational systems.

source: Computer Science @ Wikipedia

Informatics

  Informatics is a branch of information engineering. It involves the practice of information processing and the engineering of information systems, and as an academic field it is an applied form of information science. The field considers the interaction between humans and information alongside the construction of interfaces, organisations, technologies and systems. As such, the field of informatics has great breadth and encompasses many subspecialties, including disciplines of computer science, information systems, information technology and statistics. Since the advent of computers, individuals and organizations increasingly process information digitally. This has led to the study of informatics with computational, mathematical, biological, cognitive and social aspects, including study of the social impact of information technologies.

source: Informatics @ Wikipedia

It is for sure time and place dependent, after further research it seems that the German term Informatik was a synonym of the Computer Science at first, was adapted virtually everywhere, but evolved since 1956, and diverged with meaning, but it is still overlapping. Tt seems that currently Informatics is used more as applied Computer Science (ref: search engine coin toss).

The IT (Information Technology) in some languages has broader meaning, and simply merges telecommunication with computer sciene and informatics. Unfortunately this is not well-defined term, it is part of the language so it may vary in time up to the moment when people think it is too broad and start some finer classification.

Please see also Informatics vs. Computer Science