Why not to take the unary representation of numbers in numeric algorithms?

What this means is that unary knapsack is in P.  It does not mean that knapsack (with binary-encoded numbers) is in P.

Knapsack is known to be NP-complete.  If you showed that knapsack is in P, that would show that P = NP.

But you haven't shown that knapsack is in P.  You've shown that unary knapsack is in P.  However, unary knapsack is not known to be NP-complete (indeed, the standard suspicion is that it's most likely not NP-complete).  Therefore, putting unary knapsack in P does not imply that P = NP.

So which problem should we care more about, knapsack or unary knapsack?  If your motivation is based upon practical concerns, then the answer will depend on the size of the numbers you want to solve the knapsack problem for: if they're large, then you certainly care more about knapsack than unary knapsack.  If your motivation is based upon theoretical concerns, then knapsack is arguably more interesting, because it allows us to get a deeper understanding -- it allows us to make the distinction between size vs magnitude -- whereas unary knapsack prevents us from making that distinction.

To answer the follow-up question about the dynamic programming algorithm for the knapsack problem:

Yes, the same dynamic programming algorithm can be applied to both knapsacks and to the unary knapsack.  Its running time is polynomial in the magnitude of the numbers, but exponential (not polynomial) in the length of the numbers when encoded in binary.  Thus, its running time is polynomial in the length of the input when the input is encoded in unary but is not polynomial in the length of the input when the input is encoded in binary.  That's why we do consider this dynamic programming algorithm to be a polynomial-time algorithm for unary knapsack, but don't consider it to be a polynomial-time algorithm for (binary-encoded) knapsack.

Recall that we say an algorithm runs in polynomial time if its running time is at most some polynomial of the length of the input, in bits.


Find all non-isomorphic graphs with a particular degree sequence

To the best of my knowledge, nothing considerably better is known. For instance, your problem was part of the Combinatorics REGS 2012 program at Illinois.

With that being said, I can think of three possible engineering approaches that might work:

Use what you have (perhaps as a baseline for benchmarking other approaches).
Use the suggestion of Yuval: use the configuration model to generate all such graphs, and check for isomorphism between them. For instance, you can use nauty that is fast and highly optimized.
If your degree sequences are of length $n$ for some small $n$ (or you can afford to do a lot preprocessing), generate all $n$-vertex graphs. For this, you can either download them all from McKay's homepage, or use e.g., geng. If you have additional information, you might use an even more specific generator such as plantri (geng has options too). Once you have the graphs, iterate over them and check whether they have the right degree sequence.

By the way, Sage also has much of this functionality built-in, see e.g., here (for instance, search for "Generate all graphs with a specified degree sequence").


The use of modal logic in computer science

I think you can find many good examples if you search a bit online.  Some very-easy-to-find examples are in the following list:
From Stanford Encyclopedia

In computer science, labeled transition systems (LTSs) are commonly used to represent possible computation pathways during execution of a program.

Wikipedia has some examples in its article modal logic:

Versions of temporal logic can be used in computer science to model computer operations and prove theorems about them. In one version, ◇P means "at a future time in the computation it is possible that the computer state will be such that P is true"; □P means "at all future times in the computation P will be true". In another version, ◇P means "at the immediate next state of the computation, P might be true"; □P means "at the immediate next state of the computation, P will be true".

Also, if you go to Logic in Action, you will find several examples, e.g.:

[Chapter 6] introduces dynamic logic, a system that was introduced in computer science for reasoning about the behaviour of computer programs, by Vaughan Pratt and others, in the 1970s.
In [Chapter 10] it is explained how predicate logic can be used for programming. The chapter gives an introduction to concepts used in automating logical theorem proving. This leads to computational tools underlying the well known logic programming language Prolog, popular in AI an in computational linguistics. The inferential mechanism behind Prolog is called SLD-resolution. This is the reasoning engine for a natural fragment of predicate logic (the so-called Horn-fragment).


For example, the compositeness problem, "given an integer $X$, is it composite?" might have a certificate $n_1, n_2$ where $X=n_1n_2$. This certificate would be checkable in time polynomial in the length of the certificate.


Expressiveness of modern regular expressions

The word problem of regular expressions with backreferences is NP-complete;
citing Aho (1990) via Blaisorblade/Charles Stewart.

I don't know the whole set of operators some flavors of regexps have, but several are no more powerful than regular; they have probably been added as syntactic sugar.


Any algorithm polynomial time with infinite space?

If you don't allow preprocessing, then the answer is no (at least when talking about standard models of computation such as the Turing machine or a random access machine). The reason follows from the fact that (in reasonable models) writing to memory requires time, hence the amount of memory used is upper bounded by the running time.

The notion of preprocessing is captured in complexity by machines who have access to an advice, alongside with the input. For example, the class $\mathsf{P/Poly}$ consists of all problems solvable using polynomial machines, who given a length $n$ input, have access to an advice string of length $poly(n)$. Note that the advice is the same for all inputs of the same length, you can think of this advice as your preprocessing. If, as in your example, you allow too much preprocessing, then everything is solvable in a single step, which makes this situation uninteresting (and indeed, it is not realistic to imagine you have the answer ready for any possible input). In the language of Turing machines who take advice, you can say that $\mathsf{P/EXP}$ with random access to the advice is the class of all languages (your advice can include the answers for all inputs). This means that allowing the advice to be too long makes the game too easy.


Finding similar high dimensional real vectors

One approach: Quantization

One approach is to quantize the values, then apply an existing LSH that works on discrete values.  In other words, you split up the space $[0,1]$ into several ranges, map each real number to its containing range, and then apply an existing LSH that works with discrete values.  This is essentially equivalent to first truncating each coordinate of the vector, then applying some discrete LSH.

For example, suppose you split the interval $[0,1]$ up into ten ranges, $[0,0.1)$, $[0.1,0.2)$, ..., $[0.8,0.9)$, and $[0.9,1.0]$.  Now you can map any value in $[0,1]$ to its corresponding range -- this is basically just truncating to keep only the first digit in the decimal representation.  Map each interval to a digit from 0 to 9: e..g, $[0,0.1) \mapsto 0$, etc.  In this way, given any vector $v \in [0,1]^n$, you can get a new vector $w \in \{0,1,\dots,9\}^n$.  For instance, the vector $v=(0.55,0.34,0.90,0.99) \in [0,1]^4$ maps to the new vector $w=(5,3,9,9) \in \{0,\dots,9\}^n$.

The new vector $w$ is in a discrete space, rather than in a continuous space.  Now if you have a LSH that works on this discrete space, you can apply it to $w$.  For instance, suppose $h_1:\{0,\dots,9\}^n \to \mathbb{R}$ is a locality-sensitive hash (LSH) on this discrete space.  Let $f:[0,1]^n \to \{0,\dots,9\}^n$ be the mapping that sends each real number to its corresponding range, i.e., $f(v)=(g(v_1),\dots,g(v_n))$ where $g(x)= \lfloor 10x \rfloor$ is the truncation map $g:[0,1] \to \{0,\dots,9\}$.  Define $h_0 : [0,1]^n \to \mathbb{R}$ by
$$h_0(v) = h_1(f(v)).$$
Then $h_0$ is a LSH on continuous values.

If you plan to generate multiple different LSHs, it's probably slightly better to apply the following tweak.  Pick a random $n$-vector number $r \in [0,0.1)^n$.  Now the LSH for $[0,1]^n$ is defined to be $h_0(v) = h_1(f(v+r))$ as above, where $f:[0,1]^n \to \{0,1,\dots,10\}^n$ is the truncation map defined as above and $h_1:\{0,1,\dots,10\}^n\to\mathbb{R}$ is a LSH on discrete values.  This tweak lets you generate multiple independent LSH's for $[0,1]^n$.  If you are only picking a single hash function, you can skip this step.

There's nothing special about base-10.  Instead of using base-10, you can also use base-2 or any other base.  The performance will depend upon the base you use as well as the specific discrete LSH you choose, so you might need to play with the options to see which is best overall.  I suspect you will find that the optimal choice of base is base $b=2$ or $b=3$ (and, if your discrete LSH is based upon hashing a random subset of the coordinates, choosing a subset of size proportional to $\sqrt{n}/b$), but it's not possible to give a hard-and-fast rule: the optimum depends to some extent on the distribution of your data.  That's why I suggest trying a few different parameter choices to see which seems to work best on your data.

This is basically the "truncation" idea in your original post (truncate all real values, then apply a discrete LSH), but now we apply it to the entire vector, rather than trying to split the vector in half.  Of course, the discrete LSH might itself work by picking a few randomly chosen coordinates and hashing only those coordinates (e.g., using a universal hash).

Another approach: Use a LSH designed for continuous values

There are also some LSH's that are designed specifically for continuous real numbers.  I don't know if there are any for the Euclidean distance.

A totally different approach: nearest-neighbor data structures

Finally, it's worth mentioning that there are also other approaches to this problem that don't involve LSH's at all.  There are some data structures that are designed to support nearest-neighbor search (or approximate nearest-neighbor search).  You might look at metric trees, k-d trees, and nearest-neighbor search.

However, beware of the curse of dimensionality.  If the dimension $n$ is large, none of these approaches are likely to work well: high dimensions are just plain hard.  For instance, one rule of thumb I've seen is that k-d trees tend not to work well when $n \ge 30$.  I'm not sure any of these techniques will be terribly effective when $n$ is large: nearest-neighbor search in high dimensions is hard.


I have trouble to understand pattern calculus, could someone explain it in simple terms?

I can't really say that I know bondi (this is the first time I heard about it), but my experience with functional languages will allow me to give you hints.

Let's first discuss what the example given in the wikipedia page do. There are two functions called elimLeafs and elimCount. Both are accessed such as elimLeaf (Leaf 3) returns 3 and elimCount(Count 3) returns 3. "Do not focus on what these functions do !" .. There is a similarity between the two functions in that:

elimLeaf (Laef x) or elimCount (Count x) can be return as elimPattern (Pattern x) where Pattern is either Count, Leaf or any other thing you want to name.

Knowing this, you can write both functions such as "Pattern" in elimPattern (Pattern x) is a variable .. and whence you can write both elimPattern and elimLeaf such as:

 elim = | x -> | {y} x y -> y

which can be called as:

  elim Leaf (Leaf 3) returns 3 .... for example.

The function elim above is actually two functions (or I dont know what is called in Bondi). First, you got the name of the function, which is elim. The name shall be followed by =| . Then you have the definition of the function"s" which is followed by ->. So,

"elim Leaf" is matched with "elim =| x" and therefore evaluated to | {y} x y
Now, x is Leaf in "elim Leaf". Thus, "| {y} x y"  is equivalent to "| {y} Leaf y".
The function elim above can be further evaluated such that "| {y} Leaf y -> y"  (that is "| {y} Leaf y" is evaluated to y.) y in this case would be 3, given the input above.
Note here that right now you did exactly what elimLeaf did ! You can do the same for elimCount by simply replacing Leaf by Count in the input.

To clarify more:
Assume you want to do this with C++. The definition of the functions elimCount and elimLeaf are as follows:

int elimCount(int x) { return x;}
int elimLeaf(int x) { return x;}     // we are just assuming int in this example,

To write both these functions with only one, perhaps you would do something like:

int elim (const char* pattern, int x) {
    if (strcmp(pattern, "Leaf") == 0) return x
    if (strcmp(pattern, "Count") == 0), return x
 }


Two consequent parallel loops maybe joined like "product", so this code can be effectively parallelized up to $n^2$ (9 in your example) processors. Each such processor can be indexed by $i,k$ pair.

Now,

  all processors $P_{i,k}$ access simultaneously $A[i,1]$

means that all processors which have the first index equal to $i$ and second index equal to anything (to some $k$ but it does not restrict the cell), will simultaneously access $A[i,1]$. In your example, you parallelize only by $i$ (first for loop), so you have only one processor per each such cell. If you parallelize completely (by pairs $(i,k)$), you will have $n$ processors per each such cell.


About graphs whose edge set decomposes into perfect matchings

Yes: we call such graphs 1-factorable (a 1-factor is also known as a perfect matching). All such graphs are regular, but the converse is not true. In fact, a $d$-regular graph $G$ is 1-factorable if and only if it is of class one, that is, $\chi'(G) = d$, where $\chi'(G)$ is the chromatic index of $G$.

Deciding if a $d$-regular graph is of class 1 is NP-complete (see e.g. [1]), so you likely cannot test this efficiently.

[1] Leven, Daniel, and Zvi Galil. "NP completeness of finding the chromatic index of regular graphs." Journal of Algorithms 4.1 (1983): 35-44.


Counterexample that B-A can be NOT context free

Consider the languages

B = { a*b*c* } -- an obviously regular language.
A1 = { aibjc* | i > j }
A2 = { aibjc* | i < j }
A3 = { a*bicj | i > j }
A4 = { a*bicj | i < j }
A = A1 ∪ A2 ∪ A3 ∪ A4

The An langauges are all context-free, so their union is also context free, but the language B-A is the non-context free language { aibici }


You “state” a loop invariant - that’s an educated guess.

You “prove” a loop invariant - you show it’s true before the loop is first entered, and you show that if it’s true before an iteration, then it is true after the iteration.

You apply the loop invariant - you take the fact that the loop invariant is proven, and the fact that the loop stopped iterating, to prove facts that hold after the loop is finished.


Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$

$h\in [m]^U$ satisfies the simple uniform hashing assumption if when $x\in U$ is chosen uniformly at random, then $h(x)$ is uniformly distributed over $[m]$, or equivalently $\forall i\in[m]: \Pr\limits_{x\in U}[h(x)=i]=\frac{1}{m}$. In our case we have:
$\Pr[h(x)=i]=\Pr\big[\lfloor mx \rfloor=i\big]=\Pr[i\le mx < i+1]=\frac{i+1}{m}-\frac{i}{m}=\frac{1}{m}$.
We used the fact that if $x$ is uniformly distributed over $[0,1]$ then $\Pr[a\le
x\le b]=b-a$ (the equality holds with all four combinations of $\le$ and $<$).


What is Temperature in LSTM (and neural networks generally)?

Temperature is a hyperparameter of LSTMs (and neural networks generally) used to control the randomness of predictions by scaling the logits before applying softmax. For example, in TensorFlow’s Magenta implementation of LSTMs, temperature represents how much to divide the logits by before computing the softmax.

When the temperature is 1, we compute the softmax directly on the logits (the unscaled output of earlier layers), and using a temperature of 0.6 the model computes the softmax on $\frac{logits}{0.6}$, resulting in a larger value. Performing softmax on larger values makes the LSTM more confident (less input is needed to activate the output layer) but also more conservative in its samples (it is less likely to sample from unlikely candidates). Using a higher temperature produces a softer probability distribution over the classes, and makes the RNN more “easily excited” by samples, resulting in more diversity and also more mistakes.

Neural networks produce class probabilities with logit vector $\mathbf{z}$ where $\mathbf{z} =$$(z_1,\ldots,z_n)$ by performing the softmax function to produce probability vector $\mathbf{q} = (q_1,\ldots,q_n)$ by comparing $z_i$ with with the other logits.

$q_i = \frac{\exp{(z_i/T)}}{\sum_j\exp{(z_j/T)}}\tag{1}$

where $T$ is the temperature parameter, normally set to 1.

The softmax function normalizes the candidates at each iteration of the network based on their exponential values by ensuring the network outputs are all between zero and one at every timestep.

Temperature therefore increases the sensitivity to low probability candidates. In LSTMs, the candidate, or sample, can be a letter, a word, or musical note, for example:

  For high temperatures (${\displaystyle \tau \to \infty }$), all [samples] have nearly the same probability and the lower the temperature, the more expected rewards affect the probability. For a low temperature (${\displaystyle \tau \to 0^{+}}$), the probability of the [sample] with the highest expected reward tends to 1.

- from Wikipedia article on softmax function

Reference

Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network." arXiv preprint arXiv:1503.02531 (2015). arXiv


Why doesn't 2-opt return an optimal solution?

I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better.


How can a device decipher spoken English words?

You'll want to read about natural language processing.  It's an entire field of research and practice.  There are many textbooks and online resources that provide an introduction to that area.


Split array into contiguous subarrays of approximately same sums

This is a polynomial time algorithm:

Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$).

Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as:
$$
\begin{cases}
 \max_i S_i & \mbox{if } \min_i S_i \ge m^* \\
+\infty & \mbox{ otherwise.}
\end{cases}
$$

Let $OPT_{m^*}[i,k]$ the cost to split the array consisting of the first $i$ input elements into $k$  contiguous (non-empty) subarrays, and let $x_i$ be the $i$-th input element.
Then, for $i,k \ge 1$,
$$
OPT_{m^*}[i][k] = \min_{j=0, \ldots, i-1}
\begin{cases}
\displaystyle\max\, \left\{ OPT_{m^*}[j][k-1], \sum_{h=j+1}^i x_i \right\} & \mbox{if } \displaystyle\sum_{h=j+1}^i x_i \ge m^* \\[10pt]
+\infty & \mbox{otherwise}
\end{cases}.
$$

Where $OPT_{m^*}[0][0] = 0$ and $OPT_{m^*}[i][0] = OPT_{m^*}[0][k] = +\infty$ for all $i,k > 0$.

The measure of an optimal solution to the original problem will be $OPT_{m^*}[n][N] - m^*$ and you can reconstruct where to split the input array using standard techniques (e.g., by inspecting the dynamic programming table in reverse order or by storing the value of $j$ chosen for each entry $OPT_{m^*}[i][k]$).


Unique number to represent a combination of 5 numbers 1-39

This can't be encoded into 16 bits.  The number of such hands is ${39 \choose 5} = 575757$ (is that a pretty number or what?), and $\lg(575757) \approx 19.1$, so a 5-card hand be encoded into 20 bits, but it can't be encoded in 16 bits.

You can use the methods shown there (1, 2) to construct an encoding into 20 bits.  Alternatively, if you want a coding-theory-based answer, analogous to Yuval's answer there (the accepted answer), you'll need to find a linear code of appropriate parameters.  16 bits isn't enough.  Even 20 bits won't be enough; you'll need a slightly longer encoding, as the coding-theory-based solutions are fast to compute but yield an encoding that is slightly-longer-than-optimal.


What does $\{$ a set $\}^{+}$ mean in the context of languages?

This is the Kleene plus. It stands for
$$ L^+ = \bigcup_{i \geq 1} L^i. $$
Here $L^i$ is the set of concatenations of $i$ words from $L$.
In words, $L^+$ consists of all concatenations of one or more words from $L$. A related operator is the Kleene star
$$ L^* = \bigcup_{i \geq 0} L^i, $$
which also allows the empty string ($L^0$).

For example, if $L = \{a\}$ then $L^+ = \{a,aa,aaa,aaaa,\ldots\}$ while $L^* = \{\epsilon,a,aa,aaa,aaaa,\ldots\}$. If $L = \{a,b\}$ then $L^+ = \{a,b,aa,ab,ba,bb,aaa,\ldots\}$. If $L = \{aa,b\}$ then $L^+ = \{aa,b,aaaa,aab,baa,bb,aaaaaa,\ldots\}$.


How to answer multiple queries efficiently?

When the value of $t_1$ is not present you are just given weighted intervals from left to right with weight value, and you should ask questions of the form, what is the sum of the weights of intervals that contains x.

If we know all intervals/weights before hand this whole task is easy without any fancy data structure, just adding the beginning of the interval with weight +value and the end with weight -value and accumulate all such values. The answer will be constant in intervals and to find the value at $x$ you can binary search for the interval that contains $x$. Will not go deep into this solution since it will not allow us to solve the problem when $t_1$ constraint is used again.

Assume we don't know all intervals before hand and we have a mix in of, add new interval, find sum of all intervals containing $x$. You can solve this problem using segment tree with lazy propagation to add a value on intervals fast, and query sum on points (actually with segment tree you can query in intervals but it isn't required here). Both queries are done in $O(log N)$ where $N$ is the number of intervals.

Let's call all given intervals in the input updates. To solve the problem with $t_1$ back, sort all queries and updates by $t$ value. And process them in such order. When you are processing each query of type $(x, t_1)$ only intervals with lower $t$ are present in the data structure, so we have an instance of the previous problem, ask for all intervals containing $x$, whenever you get an update, add it to the data structure.

This solution is offline, since you require to know all queries beforehand. This can be solved online using persistent segment trees. The overall complexity of the solution described here is $O((N+Q) log N)$.


What does the actual parameter A[i] refer to in this example of call by value-result?

This example is to get readers to think about the consequences of how A[i] is resolved in a call by value-result setting- should it be before or after the function call to fiefoo?

The example assumes that A[i] is resolved before the call, and hence i and A[1] are assigned values 1 and 2 respectively. It has the nice property that fiefoo can only modify those variables.

On the other hand, you can imagine a programming language designer who chooses to resolve the value of A[i] after fiefoo returns, but there's two possible outcomes depending on the order in which the value-results are assigned: 1) A[old i] = y, i = x; and 2) i = x, A[updated i]. Case #2 being what you proposed.

When the designer is faced with these design decisions, she would likely opt to resolve before the call to fiefoo to avoid the possible ambiguity associated with resolving after the call to fiefoo.


Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

The set $(X \cap T) \cup (Y \cap S)$ is the same as the one given by the alternating path algorithm. Let $L_0,L_1,\ldots$ be the subsets considered in the alternating path algorithm (in the Wikipedia page they are called $S_0,S_1,\ldots$, but that will be confusing), and let $X_i = L_i \cap X$, $Y_i = L_i \cap Y$.

A vertex $x \in X_0$ is unmatched and so the edge from $s$ to $x$ is in the residual network, showing that $x \in S$. In other words, $X_0 \subseteq S$. Analogously, $Y_0 \subseteq T$.
A vertex $x \in X_1$ is connected to some $y \in Y_0$ via some edge not in the matching. Since $(x,y)$ is not in the matching, it belongs to the residual network. Since $y \in T$, also $x \in T$. In other words, $X_1 \subseteq T$. Analogously, $Y_1 \subseteq S$.
A vertex $x \in X_2$ is connected to some $y \in Y_1$ via some edge not in the matching. As before, $(x,y)$ belongs to the residual network, and so $y \in S$ implies $x \in S$. In other words, $X_2 \subseteq S$ and $Y_2 \subseteq T$.

Continuing this way, we conclude that
$$
\begin{align*}
S \cap X &= X_0 \cup X_2 \cup \cdots, & T \cap X &= X_1 \cup X_3 \cup \cdots, \\
S \cap Y &= Y_1 \cup Y_3 \cup \cdots, & T \cap Y &= Y_0 \cup Y_2 \cup \cdots. \\
\end{align*}
$$
Therefore
$$
(X \cap T) \cup (Y \cap S) = X_1 \cup X_3 \cup \cdots \cup Y_1 \cup Y_3 \cup \cdots = L_1 \cup L_3 \cup \cdots,
$$
which is the output of the alternating path algorithm.


2-D peak finding complexity (MIT OCW 6.006)

the analysis you outline appears to be incorrect. the correct complexity is $O(m)$ where $m$ is the larger dimension of the matrix (either rows or columns). see this other correct analysis for more/better detail. part of the mistake is not defining the recurrence relation $T(n,m)$ in terms of $T(n,m)$ only (which is handled correctly in the paper). the paper shows/uses an infinite series:

$
\begin{eqnarray*}
T(n) & = & T \left({n \over 2}\right) + cn \\
 T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\
&= & O(n)
\end{eqnarray*}
$


The operator $A(L)= \{w \mid ww \in L\}$

As an amplification of sdcvvc's hint:  You can find a context-free language $L$ such that $A(L) = \{a^m b^m c^m \mid m\geq 0\}$, which as you probably know is not context-free.

So we want to find $L$ such that if $ww\in L$, then $w$ has the form $a^m b^m c^m$.  We might as well have $L$ be a sublanguage of $a^*b^*c^*a^*b^*c^*$.  Now we just need to put enough restrictions on the words in $L$ so that words of the form $ww$ in $L$ will have the form we require, while ensuring $L$ is still context-free.

Partial spoiler:

  A word $a^{m_1} b^{m_2} c^{m_3} a^{m_4} b^{m_5} c^{m_6}$ has the form $ww$ if and only if $m_1 = m_4$, $m_2 = m_5$ and $m_3 = m_6$.  Now we can add some restrictions on the $m_i$ for words in $L$ to force them to all be equal in words of the form $ww$.  (Hint: we can require $m_1 = m_2$, but then we can't require $m_1 = m_3$ or $m_2 = m_3$, because then $L$ wouldn't be context-free anymore.  This isn't a problem though, because we can make use of some of the equalities we already have between the $m_i$.)


Is this decidable language a subset of this undecidable language?

No, A(DFA) is not necessarily a subset of A(TM). When you write "(M, w)" you actually refer to some encoding of M in some alphabet (usually {0,1}). These encodings of DFAs and TMs can be very different.

For a simple example: Let $A_1, A_2, \dots$ be an enumeration of all DFAs, and let $M_1, M_2, \dots$ be an enumeration of all TMs. You could say that you encode $A_i$ as the word $0 \text{bin}(i)$ and $M_i$ as $1 \text{bin}(i)$, where $\text{bin}(i)$ is the binary representation of the number $i$. Then the two langauges you presented are disjunct.

As it seems that this is part of your question: Being a subset and being computationally easier do not relate. Take the set $\Sigma^*$ of all possible words. It is easily decidable (even by a DFA) but every language, even undecidable ones, are subsets of it.


Fewest traversals to visit all vertices of DAG

I think you can solve this problem by reducing it to a minimum-cost circulation problem.

Let $G$ be your graph.  Replace each vertex $v$ with two vertices $v_\text{in},v_\text{out}$; replace each edge $u \to v$ into $v$ with an edge $u \to v_\text{in}$ and each edge $v \to w$ out of $v$ with an edge $v_\text{out} \to w$, and add the edge $v_\text{in} \to v_\text{out}$.    Add a new source vertex $s_0$ and a new sink vertex $t_0$.   For each vertex $v$ in your graph, add an edge $s_0 \to v_\text{in}$ and an edge $v_\text{out} \to t_0$.  Finally, add an edge $t_0 \to s_0$.  All edges have cost 0, lower bound 0, and upper bound $\infty$, except that all $v_\text{in} \to v_\text{out}$ edges have lower bound 1 and the $t_0 \to s_0$ edge has cost 1.

Now, find the minimum cost circulation in this graph.  There are polynomial-time algorithms to do this.

I claim that this minimum-cost circulation corresponds to the minimal set of paths to cover all the verticies.  In particular, if the minimum cost circulation has cost $c$, then that means there will be $c$ paths that cover the vertices.  This circulation will have total flow $c$, so you can trace where each of the $c$ units of flow go starting from $s_0$ to $t_0$, and that will trace out a path; take those $c$ paths as your collection of paths.  By the way I defined the lower bounds, this ensures that each vertex will be covered by at least one of these $c$ paths.


Average Case Analysis for finding max in array with duplicated element

Let us consider the following distribution: each array element is chosen independently and uniformly from $\{1,\ldots,m\}$. Let us denote by $I_i$ the indicator variable for the event that ( ** ) gets executed for the $i$th element (so $I_i = 1$ if ( ** ) gets executed, and $I_i = 0$ otherwise). Linearity of expectation shows that the expected number of times that (**) gets executed is $$ \sum_{i=2}^n \Pr[I_i]. $$
(This uses the fact that $\mathbb{E}[I_i] = \Pr[I_i]$.)

It remains to compute the probability of $I_i$. If $A[i] = j$ then (**) happens iff $A[1],\ldots,A[i-1] \in \{1,\ldots,j-1\}$, which happens with probability $\bigl(\tfrac{j-1}{m}\bigr)^{i-1}$. Therefore
$$
\Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \left(\frac{j-1}{m}\right)^{i-1}.
$$
In total, we get
$$
\sum_{i=2}^n \Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \sum_{i=2}^n \left(\frac{j-1}{m}\right)^{i-1}.
$$
You take it from here.


Solving a problem related to convolution

Hint: Consider the two sequences $q_1,\ldots,q_n$ and $\ldots,-1/9,-1/4,-1,0,1,1/4,1/9,\ldots$.


Complexity of dynamic programming algorithm for Knapsack

The first complexity measure is in terms of the target weight, the second in terms of the heaviest element. Since $W \leq nV$ (or rather, we can assume that $W \leq nV$), the first estimate $O(nW)$ implies the second $O(n^2V)$. So $O(nW)$ is a stronger estimate than $O(n^2V)$.


What is the size of a queue associated with a resource when the resource becomes a bottleneck?

He explicitly says it's a rule of thumb.  That means it's not a hard-and-fast rule; it is just a guideline that is often helpful (but no guarantees).  While I'm not familiar with that textbook, I suspect that justifying this rule of thumb would likely require concepts that are beyond the scope of that book.

If you want to understand where it is coming from, one approach is to try some simulations and see what happens.  That will give you a rough feeling for it.

If you want to understand the mathematics behind it, your next step is to study queuing theory.  There is a relationship between the average queue length and the average utilization of a resource.  When queues get large, that tends to mean that the arrival rate is close to or exceeds the departure rate, and means that the resource is highly utilized.  In the kind of setting talked about in the book, this in turn means that the resource is a good candidate to be a bottleneck.


Treating undirected graphs as a subcategory of directed graphs

You are absolutely correct; that's a perfectly valid way to view undirected graphs.

Sometimes, in undirected graphs, some things become easier and cleaner to reason about.  For instance, you don't have to worry about the difference between weakly connected vs strongly connected components in undirected graphs.  Algorithms for undirected graphs can sometimes be more efficient or simpler than if we were to apply the corresponding algorithm for directed graphs.

So: perhaps some textbooks choose to follow this treatment because it lets them introduce a problem first in the (easier) context of undirected graphs, and then generalize to the (harder) case of directed graphs.  That's just speculation.


How can I calculate the maximum sum/product of sequence?

Let's say all numbers are positive (i.e. $\geq0$). Before and after $0$s you should always use $+$. This could also solved in $O(n^2)$ by first finding all zeros and then find maximum value for each group separated by zeros. Inside each group, for positive numbers, you should always use $\times$ except in $1$ cases, if ones are in the middle of a group, still you should choose $\times$. But when ones are at the very beginning or at the very end of the group, you should choose $+$.


Your first claim is true.

As for the second consider the following counterexample.
Consider the following DAG with edges $(s,v_1),(v_1,v_2), (v_1,v_3), (v_2,t), (v_3,t)$, where $s$ is the source and $t$ is the sink

                 (v2)
                 /  \
                /    \
        (s)-->(v1)   (t)
                \    /
                 \  /
                 (v3)

There is only one mincut while according to your claim there are $\binom{5}{1} = 5$. So your second claim is false.

For the third claim consider the following DAG with edges $(s,v_1),(s,v_2), (v_2,v_3), (v_1,v_3), (v_3,t)$

                 (v2)
                 /  \
                /    \
              (s)   (v3)---->(t)
                \    /
                 \  /
                 (v1)

The Ford-Fulkerson (or any other) algorithm should find min-cut as the only edge $(v_3,t)$ which is not connected to the source. The the third claim is false.


DFA to regular expression how to deal with 'sink state'

Yes, if you have a DFA with a state $q_{rej}$  acting as a sink state, then it is there only for the formal definition of the DFA, so that our DFA will "know"  to reject any other inputs that loop in there. An NFA on the other hand, does have to have a sink state, and you can just erase it. A DFA must describe what to do on each input, whether it is an input that will be accepted or whether rejected. An NFA describes which words you will accept, it has no need to describe which you reject. A regular expression works on the same principal, it only describes which inputs you accept, it does not describe which are rejected.

Hope this clarified your question.

(note that you cannot remove those edges and the sink state in the DFA, because, as stated above, a DFA must decide an answer on each input, even if it loops in a sink state. Removing it will result in an NFA)


Longest Repeated (Scattered) Subsequence in a String

The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.

[1]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-776.


"OOD allows ADTs to be created and used."

First, if this is exactly the sentence on the exam and not your translation, it's ambiguous. It could mean that OOD is one possible way to create and use ADT, or that creating and using ADTs requires OOD.

Furthermore, ADT can mean two things: abstract data type or algebraic data type. The two concepts are completely different but are often confused. An algebraic data type is a type that is defined by its recursive structure, or equivalently by the ways to build an object of that type. An abstract data type is a type that is defined by its properties, with the way to build objects remaining hidden.

The second interpretation — that you need OOD for ADTs — is definitely false. There are programming languages which have no object orientation whatsoever but have ADTs in one sense or the other or both. Standard ML is a prime example: record and sum type definitions provide algebraic data types, while the module system provides abstract data types.

The first interpretation — that ADTs can be implemented with OOD — is contentious, because it depends on terminology that isn't standard. In typical languages that provide objects, you can build algebraic data types: define several implementations of a class to make a sum type, and put multiple fields in a class to make a product type. However this is not intrinsic to object-oriented programming. Regarding abstract data types, most object-oriented languages provide some kind of abstraction facility by hiding the implementation of a class under some interface. However, this isn't intrinsic to OOP: the key feature of objects is inheritance, and you can have inheritance without any abstraction whatsoever.

The question may be making a difference between object-oriented design and object-oriented programming construct, but OOD isn't really on the same plane as ADTs.

All in all this is a poorly-worded exam question. The connection between OOD and ADTs is an interesting subject, but the question is not phrased in a meaningful way.


You seem to have a misunderstanding of generative models v.s. "recognizing" models.

The grammar you have on the right generates words by applying rules, starting from the initial variable, and stopping after there are no more variables.

Automata, however, recognize a language as follows: you feed the automaton a word, letter by letter, and the automaton takes transitions based on the letters given to it.

If, after reading all the letters, the automaton ends up in an accepting (a.k.a final) state, then we say that the automaton accepts the word.

So it's better  to think of those as "accepting" states, rather than "final" states, although both terms are commonly used.


$Merge[A[1,...n], m]$ means merge arrays $A[1..m]$ and $A[m+1..n]$.

They are recursively sorted before merging by

MergeSort(A[1 .. m])
MergeSort(A[m + 1 .. n])


Running time of greedy scheduling algorithm

You are asking several questions. I will only answer the second one.

Suppose that $T(n) = 2T(n-1) + c$, and that $T(0) = a$. Define $S(n) = T(n) + c$. Then $S(n) = T(n)+c = 2T(n-1)+2c = 2S(n-1)$, and so $S(n) = 2^nS(0) = 2^n(a+c)$. We conclude that $T(n) = 2^n(a+c)-c = 2^na+(2^n-1)c$.


$2f$ and $2f + 1$ are just numbers. A set of $2f + 1$ nodes has a majority of non-faulty nodes, as you say; a set of $2f$ nodes can be deadlocked between the non-faulty and faulty nodes. A total of $3f + 1$ nodes are needed in the system to be able to construct a set of $2f + 1$ nodes when up to $f$ nodes are not responding (as outlined in section 3).


Language of the values of an affine function

Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with $a$ states 0, 1, ..., $a - 1$. Start state is 0, and from state $q$ on input the digit $d$ go to state $(10 q + d) \bmod a$. Accepting state is $b \bmod a$ (might need a tweak if $b > a$).


What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)

In fact, MPI and PVM are very different. However, they have the same objective, that is achieving data/message exchange between processors, thus enabling distributed/parallel computation.

MPI is the acronym for Message Passing Interface. It is a well-known message-passing standard, which defines the syntax and semantics of a core of library routines to exchange data between processors. Therefore, MPI is not a technology itself, but just the definitions of how to exchange data. However, MPI implementations exist in several programming languages (e.g., C, C++, FORTRAN, Python, and R), and those implementations are usually refereed simple as MPI. This fact may cause confusion since both the technology and the standards definition have the same name.

On the other hand, PVM is a free software (released under both the BSD License and the GNU General Public License) which enables data exchange between processors, in the same way as the MPI implementations. PVM consists of a run-time environment and library for message-passing, task and resource management, and fault notification.

You may have a look at some studies that compare both MPI and PVM. Please, see the links below.

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Papers/Comparison.pdf

https://www.researchgate.net/profile/James_Kohl2/publication/2612922_PVM_and_MPI_A_comparison_of_features/links/0c960528b9401cec40000000/PVM-and-MPI-A-comparison-of-features.pdf

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Talks/Elts.ppt


Converting a number to 16-bit Floating Point Format

First of all, the IEEE 745 16-bit format has:

1 bit for the sign.
5 bits (not 4) for the biased exponent. The bias is $15$.
10 bits for the mantissa. The leading $1$ is implicit (not explicit).

The calculation is incorrect since $(29.375)_2 = (11101.011)_2 = (1.1101011)_2 \cdot 2^4$ (and not $2^3$).

Then:

The sign bit is $1$ because the number is negative.
The unbiased exponent is $(4)_{10} = (100)_{2}$ and therefore the biased exponent is $(19)_{10} = (10011)_2$.
The mantissa, without the implicit leading $1$ and padded to 10 bits with trailing zeros, is  $(1101011000)_2$.

Then the final $16$-bit number is: $11001101011000$.


As you mention, your problem is finding a maximum matching in an unweighted bipartite graph. There are several polynomial time algorithms for solving this problem. You can read about some of them on the Wikipedia page.


Why are sensors transducers when analogue-to-digital-converters (ADC) do the actual conversion?

A sensor is a kind of transducer that converts physical quantity like temp or pressure into electrical signal (voltage, current or charge). ADC converts the electrical signal generated from sensors to an equivalent binary code,  that can be then processed by a logic processor (microcontroller, DSP, FPGA ...).


MapReduce groups everything by key, in this case the word. So the reducer gets the word, followed by a list of 1's. The length of that list is the number of times this word occurs in the text. The reducers sums up the ones to count the word.


Logical characterization of P versus NP problem (and references for least fixed point logic)

Your second question first. The context of your question is called descriptive complexity theory. In this context, I would suggest the book Finite Model Theory by Heinz-Dieter Ebbinghaus and Jörg Flum. As far as I recall it thoroughly covers both logics and their connection to P, respectively NP.

Now to your first question. Of course, as soon as both complexity classes had been characterized by logics, there were hopes to settle the P=NP question this way. Yet by now the problem has eluded this approach for several decades. One would need to pick some problem from NP and show that it is not expressible in FO(LFP) (first-order logic with least-fixed point operators). Essentially the only tool for proving non-expressibility are Ehrenfeucht–Fraïssé games. These games are notoriously hard to analyze in the presence of non-monadic second-order variables, which are needed in the case of FO(LFP). See also the paper https://eccc.weizmann.ac.il/report/2013/065/ by Yijia Chen and Jörg Flum.


Are all NP-complete languages log-space reducible to each other?

Wikipedia makes the following points:

It is unknown whether all NP-complete languages are NP-complete also with respect to logspace reductions.
However, "all known" NP-complete languages are NP-complete also with respect to logspace reductions.
There are some hints that a weaker class of reductions, AC0 reductions, may result in a different notion of NP-completeness.


Prove that the language of unary not-prime numbers satisfies the Pumping Lemma

Let $w \in \mathrm{PRIME}'$ with $|w| \geq 5$. Distinguish two cases.

$|w|$ is even -- in that case, choose $x = \varepsilon$, $y = aa$ and $z = a^{|w|-2}$. Then, for all $i\geq 0$, we have $|xy^iz|$ is even and greater than two, as $|z| \geq 3$, and therefore not prime; $xy^iz \in \mathrm{PRIME}'$.
$|w|$ is odd -- in this case, we can not verify the pumping property. This can be seen as follows.

We have

$\quad \forall m \geq 1.\, \exists n \geq m.\, \forall 1 < k \leq m.\, \gcd(k, n-k) = 1 \qquad (\star)$

that is for every assumed pumping length $m$, there is a longer word $a^n$ which you can not separate into $a^k$ and $a^{n-k}$ with $k \leq m$ (note that $k=1$ trivially violates the pumping property) so that $k$ and $n-k$ share a divisor. Therefore, we can invoke Dirichlet's theorem for every possible separation, which yields that there are (infinitely many) primes you get by $(n-k) + ik$. So we can't find a pumpable split of $a^n$, and thus the pumping property is violated for $a^n$, which is enough to "contradict" the lemma.

$(\star)$ can be shown by contradiction. Pick $n>m$ non-prime so that $n$ has no prime factor $\leq m$, e.g. $n = p^2$ for $p\geq m$ prime. Assume there was a $1<k\leq m$ so that some $1<d\leq k$ divided both $k$ and $n-k$, i.e. $k = id$ and $n-k = jd$ for some natural $i,j$. But then, $n = (i+j)d$, i.e. $d \leq m$ divides $n$, which contradicts the choice of $n$.


Difference between heuristic-based searching and optimal path searching

Uniform Cost Search (UCS) does not have a heuristic value and doesn't rely on a heuristic function.  I suspect you're getting it confused with some other algorithm (e.g., A*).  In Uniform Cost Search, there's no heuristic: we know exactly what the distance from the starting point was, and we use that to determine which nodes to expand.


Polynomial hierarchy: inclusion between spaces

Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \Pi^P_{k+1}$. Similarly $\Delta^P_{k+1} \subseteq \Sigma^P_{k+1}$.

But if the definition of polynomial hierarchy is done by alternating quantifiers than also we can prove it in the following way. The proof follows the book "Computational Complexity" by Arora and Barak, yet you have to flip a few $\exists$ and $\forall$, and do some negations. Assume equal fixed polynomial length certificates in the following proof.

We know that $P^{\Pi_k^P} = P^{\Pi_k^{SAT}} = P^{\Sigma_k^{SAT}}$.

Suppose that $L$ is decidable by a polynomial-time DTM $M$ with oracle
access to $\Sigma_k^{SAT}$.
Then, $x$ is in $L$ if and only if there exists a sequence of
oracle answers that makes $M$ accept $x$. That is, if $a_1 , . . . , a_m \in \{0, 1\}$ is a sequence of (correct)
answers  to oracle queries on input $x$, that is, the machine $M$
receives $a_i$ as the answer to its $i$ th query, then
(1) $M$ reaches the accepting state $q_{accept}$ and (2) all the answers are correct. $m$ is the maximum number of oracle queries.

We can modify DTM $M$ so that it will make exactly $m$ queries for the given input size $|x|=n$, i.e $m$ is not varying depending on the outcomes of the oracle. $m$ will be (less than) a polynomial in $n$. $m$ can also be made polynomial time computable by possibly taking a larger value. The proof is made further difficult because there are polynomial number of queries and each $i$-th query may be different depending on the answers of previous queries. Also we need to convert $\exists a_1, a_2,...$ to $\forall a_1,a_2,...$ is the proof by Arora and Barak.

Let $\phi_{i,a_1,a_2,...,a_{i-1}}$ denote the
$i$-th query that $M$ makes to its oracle when executing on $x$  receiving
answers $a_1 , . . . , a_{i-1}$ . $\phi_{i,a_1,a_2,...,a_{i-1}}$ can be generated by a turing machine (which is similar to $M$ in some ways) in polynomial time. Then, the condition (2) can be phrased as follows:

if $a_i = 1$ then  $ \exists u_1 \forall u_2 ... \phi_{i,a_1,a_2,...,a_{i-1}}(u_1,u_2,...,u_k ) = 1$
and if $a_i = 0$ then $ \forall v_1 \exists v_2 ... \phi_{i,a_1,a_2,...,a_{i-1}} (v_1,v_2,...,v_k ) = 0$.

Now we have the following:

$x \in L$
iff $\forall  a_1 , . . . , a_m \in \{0,1\}$
$\exists i \in [1..m]$ if $a_i = 1$ then $\forall U_i^1 \exists U_i^2, \forall U_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}}(U_i^1, U_i^2,U_i^3,...,U_i^k) = 0$  OR
$\exists i \in [1..m]$ if $a_i = 0$ then $\exists V_i^1\forall V_i^2, \exists V_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}} (V_i^1,V_i^2,V_i^3,...,V_i^k) = 1$
OR $M$ accepts $x$ using answers $a_1 , . . . , a_k$

This implies that $L \in \Pi_{k+1}^P$ since $\phi_{i,a_1,a_2,...,a_{i-1}} \in \Sigma_k^{SAT}$. ( You can club all quantifiers as $\forall a_1 , . . . , a_k , U^1_1 , U^1_2 . . , U^1_m \exists V^1_1 , . . . , V^1_m, U^2_1, U^2_2, ... U^2_m \forall V^2_2,..., V^2_m, U^3_1, ...U^3_m \exists ...$ , the certificates are still polynomial).

We can actually prove $NP^{\Sigma^P_k} = \Sigma^P_{k+1}$ and $CoNP^{\Pi^P_k} = \Pi^P_{k+1}$ using similar methods if I remember correctly.

The inclusion graph is given pictorially below,


Determine number of values less than mean in one pass through list

Consider an algorithm for arrays of length $n$ consisting of entries from $0$ to $n$, and using space $S$ bits.

Suppose that the first half of the array consists of pairs $a,n-a$ (where $a \leq n/2$). By choosing the second half appropriately, we can make the average of the entire array anything from $n/4$ to $3n/4$ (discretized to multiples of $1/n$). In particular, the state of the memory after reading the first half should store the number of pairs with $n/4 \leq a \leq n/2$. For every non-empty subset of $\{n/4,\ldots,n/2\}$, we can construct a first half of the array which contains exactly these values of $a$. This shows that the number of first halves that are pairwise distinguishable is at least $2^{n/4}$, hence $S = \Omega(n)$.

A very similar construction establishes an $\Omega(n)$ lower bound even when replacing the mean with the median.


if $f(n)$ is defined in the domain [0,1] then what $f(n) = O(1/n)$ actually means?

In this context it is clear that big O is taken as $n\to0$, rather than $n\to\infty$ as is more usual for us. For a function $f(x)$ defined on $(0,1)$, we say that $f(x) = O(1/x)$ if there exists a constant $C>0$ such that $f(x) < C/x$ (or, depending on the exact definition, $|f(x)| < C/x$.

This definition is by and large equivalent to the more usual definition which states that $f(x) = O(1/x)$ if there exist two constants $x_0 \in (0,1)$ and $C>0$ such that $f(x) < C/x$ for all $x \leq x_0$.

If you are confused, note that $f(x) = O(1/x)$ under these definitions iff $g(n) = O(n)$ under the usual definition, where $g(n) = f(1/n)$.

For $n$ in this range, we usually use symbols like $\epsilon$ or $\delta$ to emphasize that we are taking the asymptotics as the variable tends to 0 rather than as the variable tends to infinity.


difference between "addressable" and "address" in memory?

Address is a label that identifies a memory location. The memory is $4$ byte addressable means that you have labels that refer to memory locations of size $4$ bytes. You don't have names for smaller sizes. For example, if we have a memory of $12$ bytes and the memory is $4$ byte addressable, then we can have $3$ blocks of memory to which we can assign an address. Their addresses could be Memory block 1, The glorious block 2 and Ceres. Instead of fancy long names what is common is for the addresses to be binary numbers. Since there are $3$ addresses, then we need at least $2$ bits.
In your problem, instead of $12$ bytes, you have $16$ GB ${}=2^{34}$ bytes. The memory is $4$ byte addressable. So, we can have $2^{34}/4=2^{32}$ different addresses. So, we need $32$ bits to encode all addresses.


Is there a physical analogy to the Turing Machine?

AFAIK the Turing Machine is modeled on the idea of a human with a pen and paper. The human has a certain state in the brain, looks at the paper like the machine looks at the tape, and writes something on the paper or moves to look at a different place, just as the machine does.

TM is archaic as Peano natural number arithmetic. TM is useless for practical computation, and it is of course not intended to be used for that. It is just a simple way to axiomatize computation so we can reason about what's computable and what isn't - just as Peano arithmetic is useful for defining from first principles what natural numbers are, and what are their properties - but it would be ridiculous to try to do arithmetic by manipulating Peano numbers by hand according to the theoretical definitions.

Just think how difficult it would be to prove different theorems from complexity and computability theory (e.g. prove that the Halting Problem is undecidable), if you had to prove them using the semantics of the C++ programming language instead of the Turing Machine. Your proofs would be ridiculous or impossible - as ridiculous as proving associativity of natural number multiplication by using the grade-school method applied to decimal integers as your definition of what multiplication is.


Turing-recognizable languages closed under star operation

You're confusing the definition of $A^{\ast}$ and $A$. It is only $A$ in your example that contains strings of $a$s whose lengths are powers of two. $A^{\ast}$ does not have this restriction - it has that restriction that its strings are made up of strings from $A$.

So the individual components of each string in $A^{\ast}$ have to have lengths of powers of two (because they're from $A$), but together we only get that for every string $a^{m}$ in $A^{\ast}$ there is some set $N = \{n_{1},\ldots,n_{k}\}$ (different for each string) such that $m = \sum_{n_{i} \in N} 2^{n_{i}}$.


Can such a Turing-recognizable language exist?

If $L$ is a recognizable language that contains $f(n)$ strings of length $n$, where $f$ is computable, then $L$ is in fact computable. Given a string $x$ of length $n$, calculate $f(n)$, and then run a recognizer for $L$ on all strings of length $n$. Eventually you will find all $f(n)$ strings recognized by $L$. If $x$ is one of them, accept, and otherwise, reject.


Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

Suppose that the original graph is $G = (V,E)$. Let $V’$ be a copy of $V$, and create a new graph $G’$ with vertex set $V \cup V’$ and the following edges:

The original edges of $G$.
For every edge $(a,b) \in E$, we add a zero-weight edge $(a’,b’)$, where $a’,b’$ are the counterparts of $a,b$ in $V’$.
A matching connecting $V$ to $V’$ (i.e., each vertex in $V$ is connected to its counterpart in $V’$) with zero-weight edges.

Every matching of $G$ can be extended to a perfect matching of $G’$ with the same weight.

A useful feature of this reduction is that it preserves sparsity — that is, denoting by $n,m$ the number of vertices and edges in $G$, and by $n’,m’$ the same parameters for $G’$, we have $n’+m’ = O(n+m)$.


Is the base of natural logarithms $e$ efficiently computable?

It is not hard to check (for example using a Taylor expansion of $e^x$ at $x=0$) that for all $n \geq 0$,
$$
\sum_{k=0}^n \frac{1}{k!} < e < \sum_{k=0}^n \frac{1}{k!} + \frac{e}{(n+1)!} < \sum_{k=0}^n \frac{1}{k!} + \frac{3}{(n+1)!}.
$$
Moreover,
$$
\sum_{k=0}^n \frac{1}{k!} = \frac{\sum_{k=0}^n \prod_{i=k+1}^n i}{n!}.
$$
This formula gives an algorithm, running in time $\mathit{poly}(n)$, for computing $\sum_{k=0}^n \frac{1}{k!}$. This quantity satisfies your requirements if $\frac{3}{(n+1)!} \leq \frac{1}{C}$, that is, if $(n+1)! \geq 3C$. Since $(n+1)! \geq 2^n$, it suffices to choose $n = O(\log C)$. This gives an algorithm running in time $\mathit{poly}(\log C)$. Since the length of the encoding of $C$ is $\Theta(\log C)$, the resulting algorithm runs in polynomial time.


Why is channel capacity of AWGN infinite?

Here is a coding scheme that demonstrates the main idea:

Encoding: Let the power constraint $P$ be fixed and suppose we want to transmit one information bit a time. We set our coding scheme as $X(0) = \sqrt{P}, X(1) = -\sqrt{P}$, where $X$ is the encoding function.

Decoding: Let $Y$ denote the received signal and $Z$ the additive Gaussian noise like you defined. We set the decoder as $\hat{X} = \mathbb{1}_{\{Y > 0\}}(Y)$, where $\mathbb{1}_A(w)$ is the indicator function that yields $1$ if $w \in A$ and $0$ otherwise.

Probability of error: Let $P_e$ denote the probability of error. We assume the information bits are equally likely, since otherwise we could simply use optimal source coding to ensure they are. Then,

\begin{align}
P_e &= \frac{1}{2}P(Y>0 | X = -\sqrt{P}) + \frac{1}{2}P(Y \leq 0 | X = \sqrt{P}) \\
&= \frac{1}{2}P(Z > \sqrt{P} | X = -\sqrt{P}) + \frac{1}{2}P( Z \leq -\sqrt{P} | X = \sqrt{P}) \\
&= P(Z > \sqrt{P}) = 1 - \Phi\left(\sqrt{\frac{P}{\sigma^2}}\right),
\end{align}

where $\Phi(t) = \int_{-\infty}^t \frac{1}{\sqrt{2\pi}}e^{-\frac{-t^2}{2}}$ is the Gaussian cdf. The key observation here is that, as a cdf, this is a non-decreasing function that converges to $1$ in the limit. By increasing $P$, we can make it arbitrarily close to $1$. In other words, let $\epsilon > 0$, for large enough $P$, $P_e < \epsilon$. Without a power constraint, we can send one bit of information with arbitrarily small probability of error. This coding scheme proves a rate of $1$ is achievable.

Ok, so how do we get from an achievable rate of $1$ to $\infty$? Let's see what happens when we increase our rate from $1$ to $2$, by encoding two information bits at a time. Let
$$X(b_1, b_2)=\begin{cases} \sqrt{P}, &\text{ if } (b_1,b_2) &= (0,0) \\ \frac{\sqrt{P}}{2}, &\text{ if } (b_1,b_2) &= (0,1) \\ -\sqrt{P}, &\text{ if } (b_1,b_2) &= (1,0) \\ -\frac{\sqrt{P}}{2}, &\text{ if } (b_1,b_2) &= (1,1) \end{cases}$$

Now, if you follow the same procedure as above, you'll find out that $P_e = P\left(Z > \frac{\sqrt{P}}{2} \right) = 1 - \Phi\left(\sqrt{\frac{P}{4\sigma^2}} \right)$. Therefore, we can again find a (larger) $P$ that allows us to squeeze $2$ information bits into $1$ coded bit with an arbitrarily small probability error. As you can imagine, if $P$ is unbounded, we can simply keep doing this to encode more and more information bits to in a single coded bit without sacrificing from $P_e$.

Moral of the story: Without a bound on transmission power, we can pick a set of coded bits (codewords of length 1) that achieve arbitrarily small $P_e$ and we can do this for an arbitrarily large set of code bits to squeeze as many information bits into 1 as we want. So, the achievable rates is unbounded and since the capacity is the smallest upper bound on the set of achievable rates, it is $\infty$.


Algorithm for grouping identical neighbors in a list

You can use an adversary argument (exercise) to show that any algorithm which outputs the correct "compression" must examine all entries in the input, in every case. Such an algorithm cannot run in $o(n)$ on any input.

To answer your question, the reason that this problem requires a running time of $\Omega(n)$ is that the output depends on all entries of the input, in the sense that for every input and every entry there is a way to change the entry that affects the output. (Note, however, that not every change to the input results in a change to the output: for example $1,1,2$ and $1,2,2$ have the same output, but $1,3,2$ does not.)


Why is an accurate time so important for servers and computers?

It depends. If all atomic clocks would be turned off simultaneously, right now, that would be trouble. Because everyone relies on atomic clocks. And everything is organized in such a way that it doesn't matter much if a handful or two dozen stop working, but if they all stop working, then all the time servers in the world have no source for their time anymore.

If you announced that exactly three months from now all atomic clocks will be turned off, that would be a lot of work setting up some slightly less precise clocks, and to switch over to those less precise clocks, but cell phone service and internet would happily continue working. Even a quartz wall clock (like the one in your office) can be precise within 0.2 parts per billion. Taking 1,000 such wall clocks and carefully averaging their time would be quite accurate, and surely we can build a quartz clock for 100,000 that is a lot more precise than one that costs 100.

The problem is not the precision. The problem is that if you turn off all atomic clocks right now then we don't have anything to replace them right now. There are about 400 atomic clocks in the world. If we had 400 state of the art quartz clocks ready to be used as replacement automatically if the atomic clocks are stopped, then there would be no problem except for very few very special use cases.


Solve the equation multiplying both terms of the equation for the inverse of the hessian matrix $\vec{J} \vec{J}^T$ on the left side:

$$
 \delta \vec{x} = (\vec{J} \vec{J}^T)^{-1} \cdot \vec{J}f
$$


Managing an hotel using AVL trees - Data Structures

Maintain an AVL tree $T$ containing the indices of the unoccupied rooms. For each vertex $v$ of the tree additionally maintain the number $\eta(v)$ of vertices in the subtree of $T$ rooted at $v$.

1) Init: create an AVL tree with keys $\{1, \dots, n\}$. This requires $O(n)$ time.

2) GetUnOcc($l$, $r$): Find the vertex $u$ associated with the successor of $l$ in $T$ (possibly $l$ itself). Find the vertex $v$ associated with the predecessor of $r$ in $T$ (possibly $r$ itself). If the key of $u$ is larger than the key of $v$ return $0$. Otherwise find the least common ancestor $w$ of $l$ and $r$. Initialize the number $x$ of unoccupied rooms to $0$.
Walk from $u$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=u$ or the previous vertex in the walk was the left child of $z$, let $z'$ be the right child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$).
Walk from $v$ (inclusive) to $w$ (exclusive). Whenever you encounter a vertex $z$ such that $z=v$ or the previous vertex in the walk was the right child of $z$, let $z'$ be the left child of $z$ (if any) and add $1 + \eta(z')$ to $x$ (if $z'$ does not exist then add $1$ to $x$). Return $1+x$.

3) GetMinUnOcc($l$, $r$): Search for the vertex $u$ associated with the successor of $l$ in $T$ (where the successor of $l$ might be $l$ itself).
If the key of $u$ is at most $r$, delete $u$ from the tree subtract $1$ from the values $\eta(z)$ of all proper ancestors $z$ of $u$.
Otherwise all rooms between $l$ and $r$ are already occupied.

4) GetOut(r): Insert a new vertex $z$ with key $r$ into the tree with $\eta(z)=1$. Increment by $1$ the values $\eta(z')$ of all the proper ancestors $z'$ of $z$.


Owned state in MOESI protocol-transitions?

Owned state indicates that the data is shared between multiple caches/memory levels and is modified(by the owner) unlike modified state which indicates that only this cache has the only valid value and has modified the value. This eliminates the need for writing back to the main memory before sharing the data with anyone. Hope that helps.


Proving NP-Complete problem by reduction of subset-sum

To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard.
NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe  a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), or you can show that there is a certificate of polynomial size for each yes-instance, such that given the instance with the certificate you can in polynomial time prove that the instance is a yes instance.

Both ways are quite easy here. A polynomial certificate would be an answer of the problem. You can verify if a given set of words as a solution really uses each letter exactly once. Describing an NTM is also straightforward, where the NTM guesses all possible subsets of words and checks for each subset if it covers all letters and each letter exactly once.

To prove NP-hardness, I suggest a reduction from the Exact-Cover problem instead, since it is more related. In the exact cover problem, you are given a Universe of elements $\mathcal{U}$ and a family of sets $\mathcal{F} = \{F_1, \dots F_n\}$ over the universe (A set of subsets of the universe). The output is whether there is a subset of the sets in the family that cover the whole universe and each element is covered exactly once (included in exactly one chosen set). A reduction to your problem would be as follows. We set $\Sigma = W = \mathcal{U}$ (each element in $W$ is repeated exactly once). From each set $F \in \mathcal{F}$ we build a word $s$ that contains exactly the elements in the set (in any order).

If the instance of the exact-cover problem is a yes-instance, then there is a subset of the family $\{F_{i_1}, \dots F_{i_k}\}$ that covers each element in the universe exactly ones. The words $s_{i_1}, \dots s_{i_k}$ we built from these sets cover each element in $W$ exactly once so it is also a yes instance. On the other hand, if the instance of your problem is a yes instance, there is a ste of words $s_{i_1}, \dots s_{i_k}$ that covers each element in $W$ and hence in $\Sigma$ exactly once. The sets $F_{i_1} \dots F_{i_k}$ we build the words from cover each element in the universe exactly once.


Graphs: Dectect a sink in $\mathcal{O}(V)$

Assumption  :There is at most one row which contains all zero's.
You want to find a row of the adjacency matrix $A$ whose all entries are zero's. Simple observation if say the desired row is $k$th than in the $k$th column of adjacency matrix $A$ will contain all ones except the [k,k] index (it is easy to verify ). Let $n$ is the number of rows and columns in the matrix $A$.

Algorithm :

Start from the top right corner of the matrix $A$.
If $a_{i,j} = 0$ and $i \neq j$ then it's not your required column, skip this column mean move to $ j-1 $th column (see you have skipped one column in this step, so the number of columns for your search has been reduced).
if $a_{i,j} = 1$ and $i \neq j$ then it is your required column, but it is not required row (think why ? ) so change the row move to $ i+1 $th keep the column same.

Running time. : In each step you either reducing the number of rows or number of columns, so maximum number of steps is going to be at max $2n$ (number of rows + number of columns ).


It is very simple to understand.

The Mealy machine has 'm' outputs that means total 'm' transitions possible.
Number of states are 'n'.
Hence, there are a maximum of m*n transitions possible in total.

All these transitions should be depicted in Moore machine as well, as the power of both are same.


What is the difference between Decision Support System and Machine Learning?

Decision Support Systems (DSSs) are devoted to the management of large volumes of data. Its main goal is to simulate decision-making procedures that actually simulate (or show) some intelligence. This is why the wikipedia see DSSs well related to business processes ---as they are, indeed.

Machine Learning (ML) is used to infer or derive new knowledge from existing one usually expressed in the form of static data and optionally, as dynamic data or rules. The new knowledge is also expressed in one or both forms.

In general, DSSs and ML are different in their scope. ML is not expected to serve to take decisions though some mechanisms produce new data in such a form that a recommendation becomes apparent (e.g., when using clustering algorithms). Instead, ML can serve in the back for DSSs which I see as a more general system: it is not only in charge of taking decisions but also of managing data, the human-machine interaction (e.g., implementing Mixed-Initiative procedures), and a number of additional modules such as an explanatory module which provides additional evidence of the decisions taken.

None of these processes (necessarily) exist in ML: no need to manage data in any particular way (and indeed data is usually assumed to come either in a declarative way, e.g., PROLOG, or in a large Database conveniently designed, e.g., as in RapidMiner); no particular interface is usually required since the interesting product is the new knowledge which is writen usually in the same format than the input; no need to produce explanations of the learnt knowledge (though, admittedly, some mechanisms produce a trace that can be revisited to verify the learnt knowledge).

Other than these rather theoretical (but not really) considerations, let me emphasize that many (if not all) DSSs usually consist of Expert Systems (even nowadays) while ESs are not a form of ML.

Hope this helps,


Why $\theta/2$ in common qubit representation?

Short diagrammatic answer. Because states which are orthogonal as vectors, are represented as antipodal points on the Bloch sphere — orthogonal states of qubits are as far from each other as possible and represent a sort of 'opposite' of each other, and the Bloch sphere represents this idea.

Longer mathematical answer.
Consider the vector-valued function $\def\ket#1{|#1\rangle}$
$$ \ket{\psi_{\theta,\phi}} = \cos(\theta/2) \ket0 + \mathrm e^{i \phi} \sin(\theta/2) \ket{1}. $$
This function has a period of $4\pi$ in the argument $\theta$, as a result of that division by 2; this might be part of what you are finding strange.
However, when we consider quantum state vectors, we are not actually interested in the vector itself, as we are in the equivalence class of all vectors which are the same up to scalar factors (i.e. global phases).

Because $\ket{\psi_{\theta,\phi}} \ne \mathbf 0$, we always have $\ket{\psi_{\theta,\phi}} \ne \ket{\psi_{\theta+2\pi,\phi}} = -\ket{\psi_{\theta,\phi}}$; but we do have  $\ket{\psi_{\theta,\phi}} \propto \ket{\psi_{\theta+2\pi,\phi}}$ instead. That is, adding $2\pi$ to the angle $\theta$ gives you a vector $\ket{\psi_{\theta+2\pi,\phi}}$ which represents the same state.
Because we only care about the state-vector inasmuch as it represents a state, this vector-valued function with peridod $4\pi$ is used to stand for a state-valued function with period $2\pi$.

This becomes clearer if we use density operators to represent states, because global phases of state vectors do not affect the density operator. Define the operator
$$ \rho_{\theta,\phi} = |\psi_{\theta,\phi}\rangle\!\langle\psi_{\theta,\phi}| = \begin{bmatrix} \cos^2(\theta/2) & \mathrm e^{-i\phi}\!\cos(\theta/2)\sin(\theta/2) \\ \mathrm e^{i\phi} \!\cos(\theta/2)\sin(\theta/2) & \sin^2(\theta/2) \end{bmatrix};$$
using the double-angle formulae
$$ \begin{gather*}
\cos(\theta) = 2\cos(\theta/2)^2 - 1= 1 - 2\sin(\theta/2)^2\\
\sin(\theta) = 2\cos(\theta/2)\sin(\theta/2)
\end{gather*}
$$
we may re-write $\rho_{\theta,\phi}$ as
$$ \rho_{\theta,\phi} = \frac{1}{2}\begin{bmatrix} \cos(\theta) + 1 \;&\; \mathrm e^{-i\phi} \sin(\theta) \\ \mathrm e^{i\phi} \sin(\theta) \;&\; 1 - \cos(\theta) \end{bmatrix} ,$$
which is not the best representation for thinking about qubits, but certainly makes it very clear that the density operator corresponding to $\ket{\psi_{\theta,\phi}}$ is periodic in $\theta$ with period $2\pi$.

As icing on the cake, note that $\rho_{\theta,\phi}$ is Hermitian by construction.
So are the Pauli spin operators $\mathbf 1, X, Y, Z$, and those four are linearly independent.
That means that we can decompose $\rho_{\theta,\phi}$ as a linear combination of those four operators.
We may easily show, from the last expression for $\rho_{\theta,\phi}$, that
$$ \rho_{\theta,\phi} = \tfrac{1}{2}\Bigl(\mathbf 1 + \cos(\phi)\sin(\theta) X + \sin(\theta)\sin(\phi) Y + \cos(\theta) Z \Bigr).$$
If you take the coefficients for $X$, $Y$, and $Z$, and map them to coordinates in $\mathbb R^3$, what you obtain is the Bloch sphere representation: that is, the Bloch sphere not only represents qubit states, but it is specifically representing the decomposition of the density operator into spin matrices.


This answer shows an approach to the problem in the question.

(Threshold of isolated vertices) Let $G(n,p)$ be a random graph with $n$ vertices and each edge is present with probability $p$ independently. Suppose that $p\le c{\log n}/n$ for some constant $c$. Then the possibility of the appearance of at least one isolated vertex in $G(n, p)$ goes to 1 when $n$ goes to infinity.

Assume the above proposition on the threshold of isolated vertices holds. Applying it to the case of $G(2n, p+q)$ where $p+q\le c \log (2n)/2n$, we know the appearance of at least one isolated vertex goes to 1 when $2n$ goes to infinity.

Since the random graph in the question has less edges than the random graph above, the appearance of at least one isolated vertex in the random graph in the question also goes to 1 when $n$ goes to infinity. (This loose argument can be made rigorous.)

If you prefer not to use that proposition, you can transplant its proof to fit the current problem. It should not be hard to find a proof for that proposition since it is a classic result in the introductory theory of random graphs.


Are all subsets of NP-complete languages also NP-complete?

Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete.

You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ colors, and let $Q$ consist of all pairs $(G,2)$ such that $G$ is bipartite; note that $Q \subseteq L$. It is known that $L$ is NP-complete, whereas $Q$ is in P. Therefore $Q$ is not NP-complete unless P=NP.


What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question.

First, show that for $N>2$, $\phi(\phi(N)) < N/2$. This can be done as such:

Let $N = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $N$ ($p_i$ prime, $k_i>0$)

Suppose $N$ is even. Then $\phi(N) = N\prod_{i=1}^r(1-\frac{1}{p_i}) \leq N(1-\frac{1}{2}) \leq N/2.$ Thus $\phi(\phi(N)) < N/2$.
Suppose $N$ is odd and $N > 1$. Then $\phi(N) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $N$. By the previous result $\phi(\phi(N)) < N/2$.

So we get the desired result.

Now, let $k>2$ be some fixed integer, and suppose $N\geq k^2$. You can write:
$$T(N) = T(\phi(N)) + 2T(\sqrt{N})+\lg(\phi(N))^3 $$
$$T(N) = T(\phi(\phi(N))) + 2T(\sqrt{\phi(N)})+\lg(\phi(\phi(N)))^3 + 2T(\sqrt{N})+\lg(\phi(N))^3$$
$$T(N) \leq T(N/2) +4T(N/k)  + 2\lg(n)^3.$$
Where we used that $N\geq k^2 \implies T(\sqrt{\phi(N)}) \leq T(\sqrt{N}) \leq T(N/k)$ in the last step.

(Note that I am implicitly assuming $T(n)$ is a monotonically increasing function. One could get rid of that assumption by working on $S(n) = max(T(n),S(n-1))$, at the cost of making the argument more tedious and harder to follow)

Now we can apply the Akra-Bazzi method (a generalisation of the master theorem) with:

$k = 2$
$a_1 = 1$, $b_1 = \frac12$, $a_2 = 4$, $b_2 = \frac1k$
$g(x) = 2\lg(x)^3$

First we need to find $p$ such that $a_1b_1^p + a_2b_2^p = 1$, that is: $$(\frac12)^p+4(\frac1k)^p = 1 \;\;\; (*)$$
Let's call $p_0$ the solution to $(*)$.

Then, we need to plug $p = p_0$ into the equation:
$$T(N) \in O(N^p(1+\int_1^N\frac{g(u)}{u^p+1}du))$$
To get:

$$T(N) \in O(N^{p_0}(1+\frac{6(N^{p_0}-1)}{p_0^4N^{p_0}\ln(2)^3})) \in O(N^{p_0})$$
(I just trusted WolframAlpha and did some simplifications for the integral, I'm too clumsy/lazy to attempt it myself if I don't have to)

Notice that in $(*)$ we can make $p_0$ arbitrarily close to $0$ by picking a big enough $k$. In other words, for any $\epsilon > 0$ there exists some $k>0$ such that $p_0 < \epsilon$. So let's pick any $\epsilon > 0$ and set $k$ such that $p_0 < \epsilon$. Plugging that into the last result we get:

$$T(N) \in O(N^\epsilon)$$

And this is true for any $\epsilon>0$.

In other words, $T(N)$ grows slower than any polynomial function in $N$.

I suspect it is asymptotically not much bigger than $\lg(\phi(N))^4$, as the square root term will vanish pretty fast, but I can't prove anything better than what I showed.

Also note that you could use the master theorem by setting $k=2$ and working on the upper bound $T(N) \leq 5T(N/2) + 2\lg(N)^3$, but this would of course lead to a much weaker result.


What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?

The basic idea is simple. Just make a Turing machine behave like a DFA or PDA. There are multiple ways.

How to make Turing machines have the same power as DFAs?

Here is a straightforward way as said in the question. We will not allow them to write on the tape. We will only allow them to read the input in one direction. In that way, they literally become DFAs.
In fact, we do not have to regulate how they read the input. We can simply use read-only Turing machines, which are equivalent to DFAs in power.

How to make Turing machines have the same power as PDAs?

Let us consider Turing machines with two tapes. One read-only tape with the input, which can only be read sequentially. Another tape that will be treated as a stack. Now you can see they are literally PDAs.
Suppose we are interested in simulating each PDA individually. The existence of such a TM is proven here.

There are many type of PDAs, such as deterministic or nondeterministic, accepting by final states or empty stack, even various generalized version. It should not be too difficult to see how they can be simulated by Turing machines.

"Allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA." No, it does not. As mentioned above, read-only Turing machines are equivalent to DFAs in power. Here is the explanation from Wikipedia. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA.


Is global non-convex optimization NP-complete?

Yes, non-convex optimization is NP-hard. For a simple proof, consider the following reduction from Subset-Sum. The Subset-Sum problem asks whether there is a subset of the input integers $a_1, \dots, a_n$ which sums to zero. To reduce to non-convex programming, let $x_1, \dots, x_n$ be variables encoding the subset and consider the following non-convex program:

$$
\begin{align*}
\text{minimize }\quad&(a\cdot x)^2 + \sum_{i=1}^n x_i^2(1 - x_i)^2\\
\text{subject to}\quad& \sum_{i=1}^n x_i \ge 1.
\end{align*}
$$

Note that the optimum of this program is zero iff the Subset-Sum instance has a subset which sums to zero.


Minimizing the total variation of a sequence of discrete choices

Here is a dynamic program. Assume that $C_i = \{C_{i_1}, \ldots, C_{i_m}\}$ for all $i \in [n]$ for the sake of clarity; the following can be adapted to work if the $C_i$ have different cardinalities. Let $\operatorname{Cost}(i, j)$ be the minimum cost of a sequence over the first $i$ sets, ending with $C_{i_j}$. The following recursion describes $\operatorname{Cost}$:

$\qquad \displaystyle \begin{align}
  \operatorname{Cost}(1,j) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad, 1\leq j \leq m \\
  \operatorname{Cost}(i,j) &= \min_{k = 1}^m \left(\operatorname{Cost}(i - 1, k) + \lvert C_{(i-1)_k} - C_{i_j} \rvert\right) \ , 2 \leq i \leq n, 1 \leq j \leq m.
\end{align}$

The overall minimum cost is $\min_{j = 1}^m \text{Cost}(n, j)$; the actual sequence of choices can be determined by examining the argmins along the way. The runtime is $O(nm)$.


Max-min of a nonconvex quadratic problem

I assume that your "unit simplex" is the set of all nonnegative points whose coordinates sum to 1, $\{x: x_i\ge 0, \sum x_i = 0\}.$

Note that the max occurs when $x=y$ as $x_iy_i\le \left(\frac{x_i+y_i}2\right)^2$.  This makes your problem easy to solve, as at the optimal $x$ either $x_i^2-b_i$ is the solution, or $x_i=0$ and the solution is less than $-b_i$, so a binary search on the sorted $b_i$ should get your answer quickly.


Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I describe the best worst-case bound (to the best of my knowledge) but also an algorithm that might run in linear time in some specific cases.

But before describing the latest developments in the state of the art, I wanted to emphasize the importance of simple paths in this specific problem. As a matter of fact, many people overlooks the importance of this requirement and some do not even understand it at first glance.

When computing the shortest path from a start vertex to a goal vertex, the optimal path is necessarily simple, i.e., it does not repeat any vertices. However, when computing $k$ optimal paths, the second, third, ... best paths might not be simple. To prove it, I provide here an example that has been slightly adapted from Hershberger, Maxel & Suri, 2007:

The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $\pi_1 : \langle s, A, B, C, D, t\rangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$ and $\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $\pi_2 : \langle s, F, t\rangle$ and $\pi_3 : \langle s, G, t\rangle $ with costs 10 and 11, respectively.

Given a graph $G(V, E)$ where $V$ is the set of vertices and $\langle u, v\rangle\in E, u, v\in V$ if there is an edge between vertices $u$ and $v$,  the current state of the art for this problem to the best of my knowledge is described below:

The first significant improvement to solve the $k$ optimal paths problem is Eppstein's algorithm (Eppstein, 1998) which runs in $O(|E|+|V|\log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths.

In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|\log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen's algorithm to $O(k(|E|+|V|\log |V|))$ time. While Yen's asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice.

One of such works is due to John Hershberger et al., who introduced a replacement paths algorithm which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized.

Hope this helps,

Bibliography

Aljazzar, H. & Leue, S. (2011). $K^*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154.

Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427.

Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405.

Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716.

Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20.


Local and Global storage with multithreading pools + locking threads

I will answer Question 1.  As @DavidRicherby said, you should post the other question separately.

The space complexity is the maximum amount of space required while the algorithm is running. So it certainly would be more than the (number of elements in matrix) + (local storage of just finishing thread).  It might be the total storage of all the threads at the time the program finished but only if (a) you haven't already exited any of the threads, and (b) none of the threads freed up a bunch of memory just before the program finished.

You also need to be careful to not overcount.  As described here there are a lot of optimizations that allow you to reuse space, so you can't just sum up all the memory allocated by every thread that ever existed.  You really need to figure out the point in time during your program execution when the most memory is in use.


Big-O Notation of Anagram solution algorithm

Let's be concrete. Suppose s1 = 'abcd' and s2 = 'dcba'.

For the a in s1, it will take 4 iterations to find the a in s2.
For the b in s1, it will take 3 iterations to find the b in s2.
For the c in s1, it will take 2 iterations to find the c in s2.
For the d in s1, it will take 1 iteration to find the d in s2.

So in this case, it does take sum(i) for i = 1,...,n iterations.

Now some quiet meditation should convince you than if s2 is an anagram of s1, it will again take exactly the same number of iterations; the summands will just appear in a different order. (After all, whatever is the first character in s2 will only require 1 iteration to be found, the second character requires 2 iterations, etc.)

If s2 is not an anagram of s1, then the algorithm will short-circuit when the first character not in s2 is tested. So then the algorithm will take less than O(n^2) time. But in the worst case, the algorithm takes O(n^2) time.


If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.


Describing the asymtotic complexity of processing two-dimensional data structures

The solution is that you shouldn't just ask whether it is "linear" -- ask what variable it is "linear" in.

Your example code has running time that is linear in the total length of the input strings.  There's a long history of characterizing the running time of an algorithm as a function of the length of the input to the algorithm, and that's an entirely valid thing to do.

It's also true that its running time is $O(nk)$ where $n$ is the number of strings and $k$ is the length of the longest string.  This might be a looser bound.

Both statements are true, and don't contradict each other.  It's just a matter of identifying which upper bound on the running time is more useful.


Metagame Paradox: what is wrong with this explanation?

The flaw is that your definition of "game" is deficient and does not correspond to our intuition.  We also need a restriction on the number of moves that are possible at any position in the game.   It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite.

Usually we define a game as something where at each step there are only finitely many moves that can be played, and where the game is guaranteed to end after finitely many moves (there is no infinite sequence of moves in the game).  You forgot to specify the "at each position, there are only finitely many moves possible from that position" in your definition of a game.

If you add that to the definition, then you'll find that the metagame does not meet the definition: the metagame is not a game.  In particular, there are infinitely many possible games, so at the beginning of your metagame, there are infinitely many possible moves -- thus the metagame does not qualify as a game.  There is no paradox.

You could have an alternative definition of a game where you say that at each step the number of moves is either finite or countably infinite.  This is a bit different from what our intuition would suggest, but let's explore the consequences of defining a game this way.

In particular, the set of all games would now be uncountably infinite.

As a result, the metagame is still not a game: at the beginning of your metagame, there are uncountably infinitely many possible moves -- so does not qualify as a game.

In particular, "pick a game" is not meaningful: Player 1 has to select a game and describe it to Player 2, but there are uncountably infinitely many possible games, so Player 1 cannot describe his choice in any finite amount of time.  In particular, you cannot specify a game with a finite string (more precisely: no matter what candidate encoding of games you come up with, there will exist some games that cannot be specified by any finite string).  The description of the game is an infinite-length string.

If you like to think of it intuitively: in this case it wouldn't really be fair to think of the metagame as "finite" (even though it only lasts for a finite number of moves, if the first move takes infinitely long to complete, the metagame cannot be considered finite).

In any case, if you define a game this way, there is still no paradox.

(Why is the set of games uncountably infinite, if this is how we defined a game?  Well, I'll show an injective map $f$ that maps from a real number $x \in [0,1]$ to a game $G_x$.  In the first move of $G_x$, player 1 chooses a natural number $n \in \mathbb{N}$.  After that, there are $n$ more moves, then the game ends.  At the $i+1$th move (for $1 \le i \le n$), there are $x_i$ different moves available to the player whose turn it is to move, where $x_i$ denotes the $i$th digit after the decimal point in the decimal expansion of $x$.  Notice that $G_x$ qualifies as a game: there are two players, the players alternate, there are finitely or countably infinitely many moves at each possible position of the game, and the game is guaranteed to end after finitely many steps -- there is no infinite sequence of valid moves.  But the set $[0,1]$ of real numbers is uncountably infinite, and we have an injective map from an uncountably infinite set to a subset of the set of games.  Therefore, the set of all games is uncountably infinite, under this definition.)

Finally, the last alternative would be to define "game" so there is no restriction on the number of possible moves at each position.

However, this definition of a "game" would no longer correspond to our usual intuition for what a game should involve.  In particular, it may not be possible for a player to describe his/her move to the other player in any finite amount of time (since he/she may be choosing from among uncountably infinitely many possibilities).  That just ain't right.  In particular, such a process can't reasonably be considered finite: it would not complete in any finite amount of time.

Intuitively, why does it make sense that our definition of game ought to restrict the number of possible moves at each position to be finite, or at most countably infinite?  Because we need the player to be able to select a move and describe it to the other player.  If there is no finite encoding of the set of possible moves (at a given position), then the player whose turn it is to move has no way to describe the move he chose to his opponent.  If there is a finite encoding of the set of possible moves (at each possible position), then the number of possible moves must always be finite or countably infinite, by the definition of countability.


Complete finite automaton to never fail a match but either match original or up until the orginal

Here is what I came up with finally. I need the following operations on  finite automata, for automata a and b.

allPrefixes(a) creates an automaton that matches all non-empty prefixes of the language L(a). The implementation is quite simple on a DFA. Make sure there are no useless states (those with no path to a stop state). Then make all states except the start state into stop states.
invert(a) creates an automaton that matches the complement of L(a).
asSubstring(a) creates an automaton that matches every string in $\Sigma^*$L(a)$\Sigma^*$.
not(a) is a shortcut for invert(asSubstring(a)).
or(a,b) is the automaton that recognizes L(a)$\cup$L(b).

Given an automaton a, the automaton which comes very close to what I was after is then easy to describe as c=or(a, not(allPrefixes(a)).

Remember that I want filtering, i.e. find a match, remove the matching input, find a match again and so on until end of input. The automaton c either matches my original a or all kinds of stuff that does not end in any prefix recognized by a. Except for a suffix of the input matching only a prefix of a, there will always be a prefix of the input being matched by c.


Hint: Follow these steps:

Since $O(f) = O(g)$ then in particular $f = O(g)$ and $g = O(f)$.
Since $f = O(g)$ and $g = O(f)$ then $f = \Theta(g)$ (which is equivalent to $g = \Theta(f)$).
Since $f = \Theta(g)$, if $h = \Theta(f)$ then also $h = \Theta(g)$, and vice versa, and so $\Theta(f) = \Theta(g)$.

It is somewhat confusing that $O(f) = O(g)$ means one thing and $f = O(g)$ means another thing; if $O(f)$ is the collection of all functions $h$ such that for large enough $n$ and some $C > 0$, $h(n) \leq Cf(n)$, then $O(f) = O(g)$ is set equality while $f = O(g)$ should more properly be written $f \in O(g)$.


Estimate entropy, based upon observed frequency counts

Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \{x_1, \ldots, x_n\}$ consisting of i.i.d. realizations of $X$ then your posterior takes the form

$$
\begin{align*}
P(\theta|\mathcal{D})
&\varpropto P(\theta)P(\mathcal{D}|\theta)\\
\end{align*}
$$
Assuming $P(\theta) = B(\alpha,\beta)^{-1}\theta^{\alpha-1}(1-\theta)^{\beta-1}$, i.e., a Beta distribution and letting $n_1 = |\{x_i \in \mathcal{D} \colon x_i = 1\}|$ then we have

$$
\begin{align*}
P(\theta|\mathcal{D})
&\varpropto  \theta^{\alpha-1}(1-\theta)^{\beta-1} \theta^{n_1}(1-\theta)^{n - n_1}\\
&= \theta^{n_1 + \alpha - 1}(1- \theta)^{n - n_1 + \beta - 1}.
\end{align*}
$$
Notice the effect of the hyperparameters ($\alpha$ and $\beta$) is essentially to just add some constant to your counts of each possible outcome. So additive smoothing (at least all applications I've encountered) is really just a special case of Bayesian estimation.


Finite state automaton for the reverse of the language, and multiple starting states

FSAs come in several varieties. The most common ones are deterministic (DFA), nondeterministic (NFA), and nondeterministic with $\epsilon$-moves (also called NFAs; sometimes $\epsilon$-NFAs).

The definitions of all three are not completely standard – there are several variants in the literature (for example, some allow the transition function of a DFA to be partial). However, in most standard definitions, all FSAs have a single initial state; though it is perfectly possible to define NFAs and $\epsilon$-NFAs having several initial states.

The reason you have to add a new initial state when reversing an NFA is exactly the requirement that there be a unique initial state. If we remove this requirement, then there is no need to add a new initial state.


Termination of a composition of terminating functions

Indeed this is obvious. Now you need to "prove" it. The difficulty will depend on what definitions (and axioms) you assume when you say that "$f$ and $g$ can be implemented". Start by making these definitions explicit.


Question about Complete partially Directed Acyclic Graph

They have different v-structures: $G_1$ has the v-structures $(x_3,y,x_4),(x_4,y,x_3)$, whereas $G_3$ has the v-structures $(x_1,x_4,y),(y,x_4,x_1)$.


Difference between diameter of a graph vs longest path of the graph

The longest path of the graph is the longest path between any two vertices. There may be several with the same longest length.

Since you are comparing with the diameter, which is an integer, you probably mean the length of the longest path

The diameter is the length of the longest of the shortest path between any two
vertices. That means that you compute the shortest path for any pair
of vertices, and take the longest one of them.

The distance between two vertices being the shortest path, the diameter is the longest distance between two vertices,