Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$

Okay I can't draw and the only tools for visualizing Turing machines aren't the most practical so I'll give you a list of states and how they behave. Note that next refers to the next state and that if next and write aren't assigned the machine doesn't move to another state / doesn't write something.
A brief verbal description since the machine is somewhat big (9 states). There are states for count 0/ count 1 and count 2. Which count zeros...; Now when the machine reaches a third zero it is replaced with X and we are back to "count 0". Every of those three states has a "back" state responsible for moving back to start if we encounter an "empty". Notice that if we do not encounter a zero on our way back we are done and have to report accept or reject. If however we encounter a zero on our way back "count i back" switches to state "count i not finished" which if it encounters a "empty" (while moving left) will switch back to "count i" ($i \in \{0,1,2\}$.
"count 0" (initial state)
    read 0: {move: right, next: "count 1"}
    read X: {move: right}
    read empty: {move: left, next: "count 0 back"}
"count 1"
    read 0: {move:  right, next: "count 2"}
    read X: {move: right}
    read empty: {move: left, next: "count 1 back"}
"count 2":
    read 0: {move: right, write: X, next: "count 0"}
    read X: {move: right}
    read empty: {move: left, next: "count 2 back"}
"count 0 back"
    read X: {move: left}
    read 0: {move: left, next: "count 0 not finished"}
    read empty: reject
"count 1 back"
    read X: {move: left}
    read 0: {move: left, next: "count 1 not finished"}
    read empty: accept
"count 2 back"
    read X: {move: left}
    read 0: {move: left, next: "count 2 not finished"}
    read empty: reject
"count 0 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 0"}
"count 1 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 1"}
"count 2 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 2"}

Hope you get the idea!


Set $\delta' = \frac{\delta}{2(n-1)}$.
You can nudge each $x_i$ except for the last one by a random value in $\left[-\delta', +\delta'\right]$, and then adjust the last value to get the sum to be $1$.

Pseudocode:

  $x \leftarrow (x_1,...,x_n)$
  $\delta' \leftarrow \frac{\delta}{2(n-1)}$
  $y  \leftarrow  (y_1, \ldots, y_n)$
  for each $i$ until $n$ do
  $\quad y_i \ \leftarrow \ (\,x_i + \mathsf{randomBetween(-\delta',+\delta')}\,)$
  endfor
  $y_{n+1} \leftarrow (1-\sum y_i)$

Using $y$ instead of $x^*$, the last line guarantees tha $\sum y_i = 1$.

We need to check that $|| x - y || < \delta$:

For $i=1,2,\ldots, n-1$ we have $|x_i - y_i| = \delta_i'$. Since the original $x$ vector sums to $1$, we also have $$|x_n-y_n| = \left|x_n - 1+\sum_{i=1}^{n-1} (x_i + \delta_i')\right| = \left|\sum_{i=1}^{n-1}\delta_i'\right|$$.

So $$|| x- y|| = \sum_{i=1}^{n-1} | \delta_i'| + \left| \sum_{i=1}^{n-1} \delta_i'\right| \le 2\sum_{i=1}^{n-1} | \delta_i'| \le \delta$$ using the triangle inequality.


An infinite decidable language that is a subset of $\overline { A_{TM}}$

Fix a special TM $M_d$ which infinitely loops on any input $x$. In other words, $M_d$ does not care about input $x$ and always infinitely loops on any input. Such a TM could consist of a single state and instructions such as $\delta(q_0, a) = (q_0,a)$ for all input symbols $a \in \Sigma$,  which tells $M$ to stay in the same state and never move the head. So, given its description $\langle M \rangle$ it is easy to recognize this machine by inspecting its states and instructions.

Since $M_d$ never halts on any input $x$ the following language must be infinite

$$L = \{\langle M_d,x \rangle \mid x \in \Sigma^*, M_d \text{ is the fixed TM} \}$$. This language is also a subset of $\overline{A_{TM}}$ since $M_d$ never halts on any input $x$. Thus, if we are given $\langle M_i,x \rangle$ we simply decide by checking whether $i=d$, i.e., whether $M_i$ is the same as $M_d$ by inspecting $M_i$'s states and instructions meaning $L$ is decidable.


Proving that non-regular languages are closed under concatenation

You can't prove it because it isn't true: the class of non-regular languages isn't closed under concatenation.

Let $X\subseteq \mathbb{N}$ be any undecidable set containing $1$ and every even number.  For example, take your favourite undecidable set $S$ and let $$X = \{0, 2, 4, \dots\} \cup \{1\} \cup \{2i+1\mid i\in S\}\,.$$ The language $\mathcal{L} = \{a^i\mid i\in X\}$ is undecidable, so it certainly isn't regular.  But $$\mathcal{L}\cdot\mathcal{L} = \{a^{i+j}\mid i,j\in X\} = \{a^i\mid i\in\mathbb{N}\}\,,$$
is regular.


Regular expression - every b preceded and followed by an even number of a's

The answer you already have covers almost all the cases: any time there's a $b$, there need to be an even number of $a$'s, so that covers all words containing a $b$.

However, there's an edge case where there are no $b$'s in your word, so you need to union your language with the case where the word has no $b$'s.

$((aa)^*b(aa)^*)^* \cup a^*$ should fit your final answer.


Algorithm for units allotment to the customers based on preferences

This is not an answer.

This post is used to show that the problem in the question is not the same as the stable marriage problem. There are three differences.

The number of customers might not be the same as the number of units. However, there is an asymmetrical version of stable marriage problem as described here. So this is not a critical difference.
Each customer may not have ranked all units. However, it can be understood each customer ranks all units not explicitly ranked lower than all units ranked. So this is not a critical difference.
None of the unit ranks the customers at all. In stable marriage problem, each man ranks all women while each woman ranks all men. This is an important difference that makes every algorithm for stable marriage problem not applicable directly for the current situation.

We could assign a random (strict) ranking (and possibly different) of customers to each unit. Now we can apply any algorithm for stable marriage problem to our customers and units.
We could assume that all units rank all customers indifferently. We can then find super-stable or strongly-stable "marriage" between customers and units.

Although we could assign rankings of the customers to the units so as to apply the algorithms for stable marriage problem, it adds an extra dimension of condition as well as probably extra steps in the solution algorithms. It might/should be better that the problem and its solution is kept as it is, agnostic to any rankings of the customers by the units.

(This post could be changed to an answer should the question be updated with the addition of a priority table by units.)


Here's a simple $O(n \log n)$ solution if multiplication and the modulus operator is always assumed to be $O(1)$ (which is a big assumption -- see the note at the end).

Create a new array, $B$, in which the first element is $A[1]$ and every future element at index $i \in 2..n$ is $A[i] * B[i-1]$. This gives you an array of all "partial products".

This array is nondecreasing, and $B[j]$'s factors are a superset or $B[i]$'s factors whenever $i < j$. Therefore, for any $A[i]$ (or even for every integer $k$), you can use binary search to find the smallest index $i$ for which $k$ divides $A[1] * A[2] ... * A[i]$. This takes $O(\log n)$ time per lookup, or $O(n \ log n)$ in total for all of $A$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?


When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

The answer depends.

For every CFG we can construct an equivalent PDA with empty stack acceptance that has just a single state.

The construction is mentioned in wikipedia. We have single state $1$. For every grammar production $(A\to \alpha)$ add an pda instruction "expand" $(1,\epsilon,A,1,\alpha)$ which means "pop $A$ and push $\alpha$ without reading input". Additionally we have "match" instructions $(1,a,a,1,\epsilon)$ which means "when symbol $a$ is on top of the stack, we must read it from the input, while popping it from the stack".
The initial stack symbol is $S$, the axiom of the grammar.

If we instead want final state acceptance then we need to distinguish a final state, so it is necessary to use two states.

Use a new initial stack symbol $Z$ to mark the bottom of the stack.
Just add two instructions, one to push $S$ on the stack $(1,\epsilon,Z,1,SZ)$, the other to move to the accepting state $f$ when the empty stack is reached $(1,\epsilon,Z,f,\epsilon)$.

This however assumes the automaton model that I was brought up with. Certain books do not agree, and consider PDA that start with an empty stack (brrr). In that case an additional state is used to start and push $Z$ onto the stack, so we need three states.


How about the Collatz Conjecture:

def f(n):
   if (n % 2 == 0):
      return n/2
   else:
     return 3*n + 1
n = read_input()
while (n != 1):
  n = f(n)

Will this program always halt? Nobody knows! It's an open problem in mathematics. You can run it for specific instances, and if it halts, you know that it halts. But if it doesn't halt, you never know when to quit. You could run it for 1000000 steps, but maybe it halts after 1000001 steps?

We may be able to intuitively determine which programs halt. This is because we write programs in ways that make their halting obvious: we write loops over finite numbers, we try to have recursion over strictly smaller arguments.

It turns out there is a large class of programs which are guaranteed to halt, and almost everything you can think of falls into this class. So most of the time, things you're running across on a daily basis will halt. But not every program is in this class.

The Halting problem says that there is no algorithm which can take any program which halts and return whether it halts or not. It doesn't mean that, given a specific program, we can never know if it halts.


Problem easy for humans and hard for general purpose machine learning, not needing external context?

This answer is an ongoing catalogue of instances I find.

"A Deep Belief Net Learning Problem" explains why shallow networks cannot learn XOR problems, stating that deep networks can.  However, empirically deep networks are not good at learning XOR problems, suggesting the XOR problem is one that is easy for humans but hard for neural networks.


What is happening in this part of the LC3?

This would appear to be a picture of the LC-3 data path from the book Patt, Yale N; Patel, Sanjay J: Introduction to Computing Systems.

The IR is the instruction register, the register where the actual bits of the instruction are fetched in the beginning cycles of processing the instruction.  The SEXT unit takes the immediate field out of the instruction.  The SR2MUX is used by the control unit to control whether the second operand of the instruction comes from a register operand or the immediate operand.


Number Partitioning targeting a Ratio of subset sums?

Yes.  Suppose the numbers are $x_1,\dots,x_n$ and the target ratio is $r$.  Define

$$y=\left\lfloor {1-r \over 1+r} \times (x_1 + \dots + x_n) \right\rceil,$$

and then look for the partition of $x_1,\dots,x_n,y$ that has minimum difference.  I suspect this might be either the solution to your original problem, or very close to it.

Why?  A partition of $x_1,\dots,x_n$ with exactly the ratio $r$ will have one group whose total is $c (x_1+ \dots + x_n)$ and another whose total is $cr(x_1+\dots+x_n)$.  These two must sum to $x_1+\dots+x_n$, so we find that $c+cr=1$, i.e., $c=1/(1+r)$, so their difference is

$$c(x_1+\dots+x_n) - cr(x_1+\dots+x_n) = {1-r \over 1+r} (x_1+\dots+x_n).$$

We have defined $y$ to be this difference, rounded to the nearest integer.  So, if you add $y$ to the smaller group, you get a perfect partition of $x_1,\dots,x_n,y$ with difference zero.  And the converse is true as well.


Well, apparently my answer was wrong. The algorithm, at least. The theorem seems to be okay, if a little unreadable.

More in line with that proof, the algorithm should be

if n is root,   # as before
    n.color = black
    n.black-quota = n.height / 2, rounded up.
    # black-quota could start at any value between n.height/2 and n.min-height

else if n.parent is red,   # as before
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    n.black-quota = n.parent.black-quota - 1

    # check that the subtree isn't totally uncolorable
    if n.min-height < n.black-quota then
        error "shortest path was too short"

    # use red only if the subtree is not colorable (as a tree), with given quota
    if n.height <= n.black-quota*2  then
        n.color = black

    else
        n.color = red

What I meant by the last condition is that 17 is red for the sole reason that you can't color it black i.e. $b(17) \notin [\frac{1}{2}h(17), m(17)]$.

Hopefully that works. Thanks for pointing out the error!


Reduction between $\Sigma^*$ and $\emptyset$

Let $f : \Sigma^* \to \Sigma^*$ any total function. Then, the statement $x \in L_2$ is always false since $L_2 = \emptyset$, and conversely $f(x) \in L_1$ is always true since $L_1 = \Sigma^*$. So, clearly, the equivalence

$\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

is false for $f$ and all $x \in \Sigma^*$ (it would have been sufficient to find one example-$x$); in fact,

$\qquad\displaystyle x \in L_2 \iff f(x) \notin L_1$

holds for all $x$. So $f$ is not a reduction function.

Since we picked $f$ arbitrarily, there can be no reduction from $L_2$ to $L_1$. A similar argument works for the other direction.


Let $X$ denote the fraction of remaining edges. We know that $0 \leq X \leq 1$ and $\mathbb{E}[X] = 1/2$. Let us define $Y = 1 - X$, which is the fraction of edges inside $A$ and $B$. This is a non-negative random variable whose expectation is $\mathbb{E}[Y] = 1/2$. According to Markov's inequality,
$$
\Pr[X < 1/4] = \Pr[Y > 3/4] = \Pr[Y > \tfrac{3}{2} \mathbb{E}[Y]] < \frac{2}{3}.
$$
Therefore $\Pr[X \geq 1/4] > 1/3$.

Let us show that the similar inequality $\Pr[X > 1/4] \geq 1/3$ is tight, that is, there exists a random variable satisfying $0 \leq X \leq 1$, $\mathbb{E}[X] = 1/2$, and $\Pr[X > 1/4] = 1/3$. Indeed, take $\Pr[X = 1/4] = 2/3$ and $\Pr[X = 1] = 1/3$, and notice that
$$
\mathbb{E}[X] = \frac{2}{3} \cdot \frac{1}{4} + \frac{1}{3} \cdot 1 = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}.
$$
In a similar way, one can show that $\Pr[X \geq 1/4]$ can be arbitrarily close to $1/3$.


Combine the following two facts:

$\mathsf{NTIME}(n) \subseteq \mathsf{TIME}(2^{O(n)})$, by deterministic simulation of nondeterminism.
$\mathsf{TIME}(2^{O(n)}) \subsetneq \mathsf{TIME}(2^{n^2})$, by the time hierarchy theorem.


You mentioned
$$
\log(n!) = \log(n(n-1)\cdots1) = \log(n)+\log(n-1)+ \cdots +\log(1)
$$
From this, we can write (assuming $\log$ is base 2)
$$
\begin{array}{l}
\log(n!) \\
= \log(n)+\log(n-1)+....+\log(1) \\
\geq \log(n)+ \cdots + \log(n/2) \\
\geq \log(n/2)+ \cdots + \log(n/2) \\
= n/2 \cdot \log(n/2) \\
= n/2 \cdot (\log(n) - 1) \\
= n/2 \cdot \log(n) - n/2 \\
\end{array}
$$
since $\lim_{n\rightarrow +\infty} \dfrac{n/2}{n/2 \cdot \log(n)} = 0$, the last expression above is $\Theta(n \log(n))$, hence $\log(n!)$ is $\Omega(n \log(n))$.


How can I tell if a bit pattern can represent offset gray-code?

Yes. Any bit pattern can represent an offset gray-code number. Gray code is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).To fully understand it you need and example and compare with default binary.
In binary:
1-> 0001
2-> 0010
3-> 0011

You can see that in binary when incrementing from 1 to 2, there are happening two bit operations. One is that the first bit turns off and second the 2'nd bit lights up. So this violates the rule of gray-code - "two successive values differ in only one bit".
In gray code it would look like this:
1-> 0001
2-> 0011
3-> 0010

Can you see the difference?
When we incremented from 1 to 2, the first bit didn't turned off anymore and the second lighted up. So only one bit operation happened.
You can also check out this article which has a C program that generates gray-codes between 1-32 bits.
Using-Gray-Codes


Recurrences and Generating Functions in Algorithms

Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik. The examples below are from these books (the mistakes and lack of clarity are mine).

Suppose that you're looking for the ways to make change with a given set of coins. For example, with common US denominations¹, the possible coins are $[1], [5], [10], [25], [100]$. To give ¢42 in change, one possibility is $[25][10][5][1][1]$; another possibility is $[10][10][10][10][1][1]$. We'll write $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$. More generally, we can write a generating function for all the ways to give change:
$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$
In more technical terms, $H$ is a term in the space of power series over the five variables $[100], [25], [10], [5], [1]$. Define the valuation of a monomial in this space by
$$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$
Then the ways to give $v$ cents in change are the number of monomials whose valuation is $v$. We can express $H$ in an incremental fashion, by first writing down the ways $P$ to give change in pennies only, then the ways $N$ to give
change in pennies and nickels, and so on. ($I$ means no coin.)
$$\begin{gather*}
  P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\
  N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\
  D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\
  Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\
  H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\
\end{gather*}$$
If you want to count and not just enumerate the ways to give change, then there is a simple way to use the formal series we've obtained. Apply the homomorphism
$$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100} $$
The coefficient of $X^v$ in $S(C)$ is the number of ways to give $v$ cents in change.

A harder example: suppose that you want to study all the ways to tile rectangles with 2×1 dominoes. For example, there are two ways to tile a 2×2 rectangle, either with two horizontal dominoes or with two vertical dominoes. Counting the number of ways to tile a $2 \times n$ rectangle is fairly easy, but the $3 \times n$ case quickly becomes nonobvious. We can enumerate all the possible tilings of a horizontal band of height 3 by sticking dominoes together, which quickly yields repetitive patterns:
$$\begin{cases}
  U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\
  V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\
  \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\
\end{cases}$$
where the funny shapes represent elementary domino arrangements: $\mathsf{o}$ is no domino, $\mathsf{L}$ is a vertical domino on top of the left part of a horizontal domino, $\substack{\strut\\\mathsf{I}}$ is a vertical domino aligned with the bottom of the band of height 3, $\substack{\:-\\=}$ is a horizontal domino aligned with the top of the band plus two horizontal dominoes below it and one step to the right, etc. Here, multiplication represents horizontal concatenation and is not commutative, but there are equations between the elementary patterns that form variables in this power series. As before with the coins, we can substitute $X$ for every domino and get a generating series for the number of tilings of a $3 \times (2n/3)$ rectangle (i.e. the coefficient of $X^{3k}$ is the number of ways to tile a rectangle of area $6k$, which contains $3k$ dominoes and has the width $2k$). The series can also be used in more versatile ways; for example, by distinguishing vertical and horizontal dominoes, we can count the tilings with a given number of vertical and horizontal dominoes.

Again, read Concrete Mathematics for a less rushed³ presentation.

¹  I know my list is incomplete; assume a simplified US suitable for mathematical examples.²
²  Also, if it comes up, assume spherical coins.
³  And better typeset.


Prove that given a number we can find whether there're 2 elements in a red/black tree that their sum equals that number in $\Theta(n)$ time

So we are given a binary search tree $T$ (we, however, do not require it to be balanced). Also we are given an integer; let's call it target_number. We wish to query whether there are two distinct nodes in $T$ such that the sum of their values equals target_number. In order to do that, we need two functions: get_successor(x) and get_predecessor(x). Given a node x get_successor(x) returns the tree node whose value is larger than that of x and is the smallest such value. The definition of get_predecessor(x) is symmetric.

The algorithm is now (as in your question): point to the minimum node, and point to the maximum node. Compute the sum $S$ of the nodes pointed by the two pointers. If $S$ is less than the target number, move left pointer to its successor node. If $S$ is greater than the target number, move right pointer to its predecessor node. Otherwise, we have a match and return true.

query(root, target_number)
    left_finger  = the minimum node of the entire tree rooted at root
    right_finger = the maximum node of the entire tree rooted at root

    while left_finger != nil and right_finger != nil and left_finger != right_finger
        tentative_sum = left_finger.value + right_finger.value
        if tentative_sum < target_number
            left_finger = get_successor(left_finger)
        else if tentative_sum > target_number
            right_finger = get_predecessor(right_finger)
        else
            return true
    return false

Next, we need to give a strong argument that it runs, in fact, in $\Theta(n)$. Take a look at operation get_successor: If you start from the minimum node and visit the entire tree in successor order, you do $\Theta(n)$ work regardless the fact that get_successor runs in worst case $\mathcal{O}(\log n)$, and that is why: you visit each node at most three times: from the parent, returning from the left child and returning from the right child; we spend constant time at each node.

As you can see from the below diagram, each node x has at most 3 incoming arcs and has at most 3 outgoing arcs. Traversing each arc is $\Theta(1)$. So basically, if we start from a minimum node, and keep advancing to the successor nodes, we do essentially in-order traversal that is, however, iterative instead of recursive. Same argument for starting from the maximum node via get_predecessor.

Now, we do the same traversal but in "both directions" (the left_finger proceeds towards successor nodes and right_finger proceeds towards predecessor nodes, and we terminate (at latest) when the two fingers meet. Thus, running time is linear in tree size and space complexity constant since no recursion is involved.


see also eg

Wikipedia evolutionary music
A genetic algorithm for producing music Matic
A fitness function for computer-generated music using genetic algorithms Alfonseca
Computer Models of Musical Creativity Cope / "asks whether computer programs can effectively model creativity -- and whether computer programs themselves can create"
Virtual Music: Computer Synthesis of Musical Style Cope / "the author and a distinguished group of experts discuss many of the issues surrounding the program, including artificial intelligence, music cognition, and aesthetics."
Machine Musicianship "This book explores the technology of implementing musical processes such as segmentation, pattern processing, and interactive improvisation in computer programs."


Because, in general, hashing is not injective.

Being injective is a property of a function which states that each distinct element of the domain is mapped to distinct element of codomain. It means that given a value of a function, you will (if it is a valid value) know from what it came from. For more on this, see injective function.

Therefore, if hashing function $h$ is not injective, it can happen that two elements $A,B$ could be mapped to $H =: h(A) = h(B)$ and from knowing only $H$ you cannot determine whether it is the result of hashing $A$ or $B$.

But, there is a concept of perfect hashing which is injective.

If your question is about cryptographic nature of hashing, then the reason is the same as why any good cipher is "unbreakable". It is not that it is impossible to decrypt it (it surely cannot be the case, because then the reciever of cipher could not do it), but is just very very time consuming without knowing the key. You can find out more on that at Cryptography Stack Exchange.


Why do DFAs with a single final state have less power?

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts

There are, equivalent or nonequivalent, definitions of "power" and "has power" in computation theory. Here is one definition of power that is suitable for the current situation.

A (descriptive) power means a set of languages over an alphabet. Given a set of automata $S$, the (descriptive) power of $S$ is $P(S)=\{L(A)\mid A\in S\}$, where $L(A)$ is the language accepted by $A$. Given two sets of automata $S_1$ and $S_2$, if $P(S_1)=P(S_2)$, we say $S_1$ and $S_2$ has the same power or $S_1$ is as powerful as $S_2$ or $S_1$ is equivalent to $S_2$ in power. If $L(S_1)\subsetneq L_{S_2}$, we say $S_1$ is less powerful than $S_2$.

For a more rigorous definition, we should define the meaning of "$L$ is the language accepted by $A$". However, since that meaning is clear in the context of DFA and NFA, we will skip it here. Note that we only talk about "power" for a set of automata. When we compare powers, the same alphabet is usually implied.

  Since it is a DFA, regardless of the number of accept states, the power should be the same.

Take a moment to reflect. Are you sure you have seen or proved that claim? I would bet you have not, although there are many popular cases of different automata having the same power, such as NFA and DFA have the same power.

On the other hand, there are many cases where if you restrict some aspect of automata, you will decrease its power, which is of course reasonable. For example, if you restrict the stacks of PDAs to be finite, they become equivalent in power to finite automata. If you restrict (deterministic) PDAs to only have one or two states, you will get various powers depending on how PDAs are defined to accept (here are some result).  If you restrict Turing machines to be read-only, they can be considered as two-way finite automata, which have the same power of the usual DFAs.

For an extreme example, if you change DFAs to DFAs with only one state, you will only have two DFAs, one DFA whose start state is not an accept state and one DFA whose start state is also an accept state, whose power is two languages, the empty language and the language of all words over the alphabet.

  DFA with single final state has the same power as DFA with more than one final state.

Final states are also commonly called accept states in the context of DFA or NFA. Fix our alphabet. Let $S_n$ be the set of all DFA that have $n$ accept states, where $n\ge1$. We will show a more general proposition.

(Less accept states, less power). $S_n$ is less powerful than $S_{n+1}$ for all $n$.

Proof. Suppose we have $A\in S_n$. Let $A'\in S_{n+1}$ be the same as $A$ except that $A'$ has one extra accept state that is not used by any transition. Since $L(A)=L(A')$, $S_n$ is at most as powerful as $S_{n+1}$.

Let $a$ be a symbol in the alphabet. Here is the beautiful example by Hendrik Jan. Let $K=\{\lambda, a, a^2, \dots, a^n\}$.

Suppose $K=L(B)$ for some DFA $B$. For the sake of contradiction, suppose both $a^i$ and $a^j$, where $i<j$, are accepted by state $q$ in $B$. That means, given $j-i$ $a$'s, $q$ is transitioned to itself. So given another $j-i$ $a$'s, $q$ will be transitioned to itself again. And so on. That means, all strings $a^i, a^j, a^{i+2(j-i)}, a^{i+3(j-i)}, \cdots$ are accepted. That contradicts the fact that $B$ only accepts the $n+1$ strings in $K$. So all states of $B$ in which these words are accepted must be different. That is, $B$ must have at least $n+1$ accept states.

I will leave it as an exercise for you to construct a DFA with $n+1$ accept states that accepts $K$. Since $K\not\in P(S_n)$ but $K\in P(S_{n+1})$, we have proved "less accept states, less power".

Exercise 1. Show that DFAs with $n$ reject states have less power than DFAs with $n+1$ reject states for all $n\ge1$.

Exercise 2. Let $S_{m,n}$ be the set of DFAs with $m$ accept states and $n$ reject states, $m+n\ge1$. Compare their powers.

Exercise 3. (Provided by Mr. Sigma) Show that NFAs with a single accept state have the same power as all NFAs.

Exercise 4. Show that NFAs with a single accept state and without $\epsilon$-transition have the same power as all NFAs.


Let $v$ be an arbitrary vertex in your graph, of degree $d$. In any solution $D$, either $v \in D$, or at least $d-1$ of its neighbors are in $D$. In this case, we have one branch with parameter $k-1$, and $d$ branches with parameter $k-(d-1)$ (which is progress as long as $d \geq 2$).
If $d = 1$, then we can say more. Let $u$ be the unique neighbor of $v$. If $D$ is any feasible solution, then so is $D \setminus \{v\} \cup \{u\}$. In other words, we can assume without loss of generality that any solution does not contain $v$. Any such solution either contains $u$ or all neighbors of $u$ apart from $v$. If $u$ also has degree $1$ then there is clearly a solution not containing either $u$ or $v$, so we can assume that in this case $u$ has degree at least $2$. In this case, we have one branch with parameter $k-1$, and one branch with parameter $k-(d-1)$.
Denoting by $T(k)$ the worst-case size of the search tree when the parameter in $k$, our ideas so far show that
$$
T(k) = T(k-1) + \max_{d \geq 2} (dT(k-(d-1)).
$$
Unfortunately, if we choose $d = 2$ then we get $T(k) \geq 3T(k-1)$, whose solution is $T(k) = \Omega(3^k)$.
We can improve on this algorithm by noting that if all vertices have degree $2$ then the problem is easy to solve, since the graph is a union of disjoint cycles, and a cycle of length $\ell$ requires spending $\lceil \ell/2 \rceil$ vertices of $D$. Hence either $v$ has degree at least $3$, or $v$ has degree $1$ (and $u$ has degree at least $2$). This leads to the improved recurrence
$$
T(k) = T(k-1) + \max(T(k-1),\max_{d \geq 3} dT(k-(d-1))).
$$
Unfortunately, if we choose $d = 3$ then we get $T(k) \geq T(k-1) + 3T(k-2)$, whose solution is $T(k) = \Omega(\bigl(\frac{\sqrt{13}+1}{2}\bigr)^k)$, with a base of roughly $2.3$.
We can improve on this as follows. We can assume that the minimum degree is $2$. Let $v$ be a vertex of degree $d \geq 3$. Any solution either contains $v$, or all of its neighbors, or it contains all but a single neighbor $w$, and all the remaining neighbors of $w$. This leads to one branch with parameter $k-1$, one branch with parameter $k-d$, and $d$ branches with parameters at most $k-d$. Thus
$$
T(k) = T(k-1) + \max(\max_{d \geq 1} T(k-d), \max_{d \geq 3}(T(k-d) + \max_{e_1,\ldots,e_d \geq 2} T(k-(d-1)+(e_1-1)) + \cdots + T(k-(d-1)+(e_d-1)))).
$$
Using monotonicity, this reduces to
$$
T(k) = T(k-1) + \max(T(k-1), \max_{d \geq 3} (d+1)T(k-d)).
$$
Using base case of $T(0) = 1$, we can prove by induction that $T(k) = 2^k$. The lower bound is clear. For the upper bound, we need to prove that $(d+1) 2^{k-d} \leq 2^{k-1}$ for all $d \geq 3$, which reduces to $d+1 \leq 2^{d-1}$, an inequality which can be checked directly.


Reducing lambda expression to normal form

$\lambda$-calculus is a rewriting system, but it's power to express all partial recursive functions makes it equivalent to Turing machines, in the sense that it is a universal model of computation. Means of computation in $\lambda$-calculus are conversions and reductions, of which the main ones are $\beta$-reduction and $\alpha$-conversion. You can learn a lot about $\lambda$-calculus on Wikipedia alone.

$\alpha$-conversion
Take for example $\lambda$-expressions $(\lambda x. x)$ and $(\lambda y. y)$. We say they are $\alpha$-equivalent because they clearly represent the same function. In short, we can rename variables (and sometimes have to).

$\beta$-reduction
This relation is the one that "gives life" to $\lambda$-expressions and reduces them to normal forms. We use $\beta$-reduction on terms of the form $(\lambda x. M)\ N$, i.e. when applying abstraction to some term $N$, and we call that construction a redex. What this expression becomes after $\beta$-reduction is written $M[x:=N]$ and it means that we replaced all free occurrences of $x$ in $M$ with $N$. For example:
$$ (\lambda x. x\ x)\ N \rightarrow_\beta N\ N$$

We will be reducing leftmost outermost redex in each step. This strategy garantees that we will get to normal form if it exists.

Now let us dive into this...
Let's find a leftmost outermost redex (underlined) in your expression:
  $$\underline{\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)\ \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)}\ (\lambda f. \lambda x. f\ x)$$

We have $\Bigl(\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x\Bigr)$, which is an abstraction (it is of the form $\lambda n. M$), that is applied to $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$, so ($\beta$-reduction) we have to replace all free occurences of $n$ in $M$ with $\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)$. We get $\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$, so entire expression is now (where I already underlined next outermost redex):
  $$\underline{\biggl(\lambda m.\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)\ (\lambda f. \lambda x. f\ x)}$$
We now have to substitute $(\lambda f. \lambda x. f\ x)$ for $m$ in $\biggl(\lambda f.\lambda x. \Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ (m\ f)\ x\biggr)$ and get
  $$\lambda f.\lambda x. \underline{\Bigl(\lambda f. \lambda x. f\ (f\ x)\Bigr)\ \Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)}\ x$$
Now just keep reducing
  $$\lambda f.\lambda x. \underline{\Bigl(\lambda x. ((\lambda f. \lambda x. f\ x)\ f)\ (((\lambda f. \lambda x. f\ x)\ f)\ x)\Bigr)\ x}$$
  $$\lambda f.\lambda x. \Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)$$
  $$\lambda f.\lambda x. \underline{(\lambda x. f\ x)\ \biggl(\Bigl((\lambda f. \lambda x. f\ x)\ f\Bigr)\ x\biggr)}$$
  $$\lambda f.\lambda x. f\ \biggl(\Bigl(\underline{(\lambda f. \lambda x. f\ x)\ f}\Bigr)\ x\biggr)$$
  $$\lambda f.\lambda x. f\ \Bigr(\underline{(\lambda x. f\ x)\ x}\Bigr)$$
  $$\lambda f.\lambda x. f\ (f\ x)$$
And now, if you are still alive, remember $\alpha$-equivalence. We can change the names of variables, say $f$ to $y$ and $x$ to $z$, and obtain your wanted solution.

What have we computed?
We computed that $2 \cdot 1 = 2$, in $\lambda$-calculus using Church numerals:

$c_0 = \lambda f. \lambda x. x$
$c_1 = \lambda f. \lambda x. f\ x$
$c_2 = \lambda f. \lambda x. f\ (f\ x)$
$\vdots$

Expression $\lambda n.\lambda m.\lambda f.\lambda x. n\ (m\ f)\ x$ is the multiplication operator, and other two expressions (on which this operator was applied) are Church numerals for $2$ and $1$.


The basic idea is to make $n$ trips, returning to the start and refueling on all but the last trip. On each trip but the last, you'll leave some fuel at a new dump. You want to know how far you can go on the last trip. To make calculations easy, we'll say that a full tank contains 1 (unit) of fuel and that amount will take you a distance of 1 (other unit) of distance.

Example 1 ($n = 1$ trip). Trivial: drive until you run out of fuel. Distance covered $D(1)=1$.

Example 2 ($n=2$). On the first trip, travel $x$ distance, so you'll have $1-x$ fuel remaining. Leave just enough fuel at dump 1 to allow you to return to the start. Leaving $1-2x$ at dump 1 will do the trick. On the second trip, starting with a full tank, go to the first dump (using $x$ of your fuel), top off your tank (taking $x$ from the dump, leaving $1-3x$) and drive until you run out of fuel. To maximize the distance we'll need the dump to be empty so $1-3x=0$, so $x=1/3$. The total distance you'll cover will be $D(2)=1+1/3$.

The general case. With $n$ trips, you'll hit dump 1 $2n-1$ times, dump 2 $2n-3$ times, dump 3 $2n-5$ times, and so on. To empty the dumps on the last trip, we'll place dump 1 at a distance $1/(2n-1)$, dump 2 at a further distance $1/(2n-3)$, and so on. Then the last trip will cover
$$
D(n) = 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}
$$
If we define the $m$-th harmonic number,
$$
H_m=1 + \frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5} + \dotsm + \frac{1}{m}
$$
then it's well known that $H_m\approx\ln m$ and we can write our distance
$$\begin{align}
D(n) &= 1 + \frac{1}{3}+\frac{1}{5} + \dotsm + \frac{1}{2n-1}\\
 & = \left(1 + \frac{1}{2}+\frac{1}{3}+ \dotsm + \frac{1}{2n-1}\right)-\left(\frac{1}{2}+\frac{1}{4}+ \dotsm + \frac{1}{2n-2}\right)\\
 &=H_{2n-1}-\frac{1}{2}H_{n-1}
\end{align}$$
This will take an amount of trips (and fuel) that are exponential in the desired distance. For example, to go a distance of $2$, it will take $n=8$ trips and to go a distance of $5$ will take $3093$ trips.

This (and a variant) is known as the jeep problem and is covered in more detail here.


Polynomial-time algorithm with exponential space is eligible?

Regarding your first question, what you're missing is where your "exponential table" comes from. Your algorithm has a finite description and should work for every $n$. So it cannot explicitly contain the $n$-table for all $n$. It could contain instructions for computing the table, but then it would have to first execute them, and constructing an exponential size table takes exponential time.

On the other hand, your program could use a (supposedly) exponential amount of uninitialized space. Since its running time is polynomial, it only accesses polynomially many cells. You can implement memory access in such a way that if $T$ cells are ever accessed then $\tilde{O}(T)$ memory is used (exercise). The corresponding running time might become much worse, but still polynomial.

A third possibility are non-uniform computation models, which are popular in cryptography. Here the idea is that the algorithm is allowed to use a certain hard-coded amount of data which depends only on $n$. However, this data has to be polynomial size. This restriction comes from the interpretation of the model in terms of circuits. A machine running in polynomial time corresponds to circuits for every $n$ of polynomial size. If we now relax the constraint that all these circuits come from some single algorithm, then we get non-uniform polynomial time, which is the same computation with advice depending on $n$ of polynomial size (exercise).

The answer to the first question should obviate the second one. I would just mention that sometimes, instead of probabilistic polynomial-time algorithms, one considers (deterministic) polynomial size circuits.


Can a recursive language be uncountable?

Languages are collections of words. Words are finite strings.

As Shaull stated in his comment, every language over a finite alphabet is countable. (In fact, every language over a countable alphabet is also countable.)

Languages of infinite words, sometimes called $\omega$-languages, are considered in computer science. For example, they are the subject of $\omega$-automata theory. But the Turing machine formalism is about the usual notion of language.


Looking for books on creating and understanding theorems targeted at Computer Science

Algorithm Design, by John Kleinberg and Eva Tardos looks like it may be what you want. Here's the description on Amazon:

  Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

However, since the fields of computer science and mathematics are so closely related, you really should take the time to understand the math side of things. This looks like it could be a good starting point though


Rollback and Timestamp Ordering in Database

Timestamp Ordering ensures serializability by serializing transactions in order of their timestamps.

The transaction that starts earlier is assigned smaller timestamp than a transaction started later. Assuming the given schedule shows each transaction's start. $T_{5}$ will have smallest timestamp.

So to ensure serializability the given schedule must be conflict serializable. In other words it must be conflict equivalent to a serial schedule(It is a schedule in which transactions are aligned in such a way that one transaction is executed first. When the first transaction completes its cycle, then the next transaction is executed) whose first transaction is $T_{5}$ because of smallest timestamp.

Because $Write(y)$ of $T_{5}$ conflicts with $Write(y)$ of $T_{3}$,  $T_{5}$ is rolled back. Now considering $T_{1}$ , $T_{2}$, $T_{3}$ , $T_{4}$, their execution is already serial with respect to each other , the order being $T_{2}$ followed by $T_{1}$, followed by $T_{3}$, followed by $T_{4}$.

Hence only transaction $T_{5}$ is rolled back.


If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is also still an open problem.

It is suspected that $\text{BQP} \not\subset \text{NP}$. In fact it's suspected that $\text{BQP} \not\subset \text{PH}$ via the "Recursive Fourier Sampling" problem. But proving separations between complexity classes is surprisingly hard. I don't think anyone's even managed to show that $\text{BQP} \not\subset$ $\text{LSPACE}$.


A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively

The $s$'s tell you which way each segment of the arm is pointing: $s_i=+1$ if the $i$th segment points up and $s_i=-1$ if the $i$th segment points down.

This means that $S_j := \sum_{i=0}^j s_i\ell_i$ is the distance of the end of the $i$th segment from the pivot. So $\min_j S_j$ and $\max_j S_j$ are the height of the lowest and highest points of the arm when it's folded in the way that $s_0, \dots, s_n$ describe.


Constructing non intersecting segments from distinct sets of points

Here is a quote from

  Kaneko, Atsushi, and Mikio Kano. "Discrete Geometry on Red and Blue Points in the Plane—A Survey." Discrete and Computational Geometry. Springer Berlin Heidelberg, 2003. 551-570.


For a fixed root, there are two kinds of path: the ones which pass the root and the ones which don't. The first kind is special since we can seperate a path $(a,b)$ into $(a,r)$ and $(r,b)$, which might be easier to deal with via proper preprocessing. Consider following divide and conquer procedure:

Solve(T):
  Fix a root r
  for each a
    for each b s.t. (a,b) pass r
      AR[a]+=calc(a,b)
  for each branch T_i of r (which is also a tree)
    Solve(T_i)

Note that we neither miss a pair nor count a pair twice since $(a,b)$ don't pass $r$ if and only if they are in the same branch. In addition, it's not hard to prove that trees in depth-$d$ recursive call don't overlap. Therefore, if we can do the non-recursive part in $O(\text{size of tree})$, the complexity would be $O(\text{recursive depth}\times n)$. If we always choose $r$ as the centroid, recursive depth is bounded by $O(\log n)$ and hence the complexity would be $O(n \log n)$. Now let's see how to solve the non-recursive part.

For a pair of node $(a,b)$, let $\text{path}(a,b)$ denote the set of distinct values on the path from $a$ to $b$, and $I_{ab}(v)$ denote the indicator function which is $1$ when $v\in \text{path}(a,b)$ and $0$ otherwise. It's not hard to see $\text{calc}(a,b)=|\text{path}(a,b)|=\sum_vI_v$.

Recall that in each phase, we choose the centroid $r$ as the root and consider only the paths passing the root. Let $B_a=\{b\in T:(a,b)\text{ pass }r\}$. Using the indicator function above, we have $\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\sum_v I_{ab}(v)=\sum_v\sum_{b\in B_a} I_{ab}(v)$. Therefore, computing $\sum_{b\in B_a} I_{ab}(v)$ for each $a$ and $v$ also gives us the answer. (You can interpret this as the number of $b$ such that $v\in \text{path}(a,b)$.) To do this, consider the set $S$ for each value $v$ such that $S_T(v)=\{u\in T: v\in\text{path}(r,u)\}$. We need to maintain $|S(v)|$ for the whole tree and similarly $|S_i(v)|$ for the $i$-th branch of $r$. We will see how to implement this later.

Since $B_r=T$, $\sum_{b\in B_r}\text{calc}(r,b)$ is exactly $\sum_v|S(v)|$. Next, consider node $a$ in the $i$-th branch. Let $r_i$ denote the $i$-th child of $r$. For each node $b$ which is not in the $i$-th branch, we can split path $(a,b)$ into $(r,b)$ and $(r_i,a)$. Therefore, $$\sum_{b\in B_a}\text{calc}(a,b)=\sum_{b\in B_a}\text{calc}(r,b)+\sum_{b\in B_a}|\text{path}(r_i,a)\backslash\text{path}(r,b)|$$
It's not hard to see that the first term equals to $\sum_v(|S_T(v)|-|S_i(v)|)$, so let's focus on the second term. Now consider each node $u$ on the path from $r_i$ to $a$ and count $\text{value}[u]$ one by one. There are two possible cases:

$\text{value}[u]=\text{value}[u']$ for some $u'\neq u$ on the path from $r_i$ to $u$. In this case, we have already counted $\text{value}[u]$ before so just ignore it.
If not, we should count the number of $b$ such that $\text{value}[u]$ doesn't appear in $\text{path}(r,b)$ and add it to $AR[a]$. This is exactly $(n-n_i)-(|S(\text{value}[u])|-|S_i(\text{value}[u])|)$ where $n_i$ is the number of nodes in the $i$-th branch.

Note that the number we count for each $u$ is independent from $a$. Therefore we can do this for every $a$ in a single DFS which takes $O(n)$. (Tell me if you need more details.)

Now the only remaining part is the preprocessing which computes $|S(v)|$, and it's actually similar to previous steps:

Consider each node $u$.

If $\text{value}[u]=\text{value}[u']$ for some $u'\neq u$ on the path from $r$ to $u$, we have already counted $\text{value}[u]$ before so just ignore it.
If not, add $n_u$ to $|S(\text{value}[u])|$. Here $n_u$ means the size of subtree rooted at $u$.

$|S_i(v)|$ can be computed similarly. The preprocessing also takes $O(n)$.

The complete flow seems like

Solve(T):
  Choose a centroid r as the root
  Preprocess() //Compute |S(v)| and |S_i(v)| via a tree traversal

  AR[r]+=Sum{|S(v)|}
  for each node u
    AR[u]+=Sum{|S(v)|-|S_i(v)|}

  Update AR with the second term via another tree traversal

  for each branch T_i of r (which is also a tree)
    Solve(T_i)


What Makes an Algorthim Greedy [Graph Coloring Algorithm]

"A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage." (from Wikipedia)  In other words, it does not backtrack.  It builds up the solution incrementally, and when it adds something to the solution-so-far, it never later removes it (or, when it makes a decision, it never later undoes that decision).
Does that describe the algorithm you are looking at?
If you want to justify that it satisfies the greedy choice property, it might help to precisely state what is the "subproblem" that is solved at each step.


The comments are right. In a topological sort, we start with nodes that have no incoming arrows and remove them from the graph, so to speak. In this case, if there are multiple possible nodes to remove, then we want to remove them in lexicographical order. Hence, the order should be $B, A, C, D, E , F, G, H$.

Your suggest topological sort does not work. This is because you propose to put $G$ before $F$.


Calculating a jackpot winner based on probabilities

For each user, sample the exponential distribution with rate equal to the size of that user's bet. The user with the smallest random variate wins the pot. Generation is something like $-\log(1 - \text{random}()) / \text{bet}$ where $\text{random}()$ returns a random number in $[0, 1)$.


Non recursively enumerable language proof by reduction to non-HP

From a programming perspective, a reduction argument is often like this: "If you have a subroutine that can effectively solve problem A, here's how you can use it to solve problem B. But problem B is unsolvable, therefore no such effective subroutine exists."

In your case, the non-halting problem (Is my input $\langle M, w\rangle$ a Turing machine and a word that makes it loop forever?) is not recursively enumerable. If we can make it recursively enumerable by adding an effective subroutine for problem B, then no such subroutine for problem B exists.

The language $L_2$ of Turing machines that accept three or fewer strings is not r.e. If it were, then there's a subroutine B which recognizes whether a TM accepts three or fewer strings.  So: imagine a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$ which ignores its input and simulates $M$ on $w$. If the simulation finishes, $M^\prime$ accepts; otherwise it loops forever.  So, $M^\prime$ accepts all inputs if $M$ halts on input $w$. $M^\prime$ doesn't accept any strings if $M$ loops forever on input $w$.

Our program makes $M^\prime$, then asks B whether $M^\prime$ accepts 3 or fewer strings. If it does, $M$ must loop forever on input $w$. We should accept ("LOOPS FOREVER"). Otherwise, we don't ("DOESN'T LOOP FOREVER").

Because our program solves an unsolvable problem with help from B, such a subroutine B cannot exist.

The language $L_4$ of Turing machines that accept all even numbers is not r.e. If it were, then there's a subroutine C which recognizes whether a TM accepts all even numbers.  So, imagine we have a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$. On input $x$, the machine simulates $M$ on $w$ for $|x|$ steps, then rejects if $M$ has finished by then; otherwise it accepts. So, $M^\prime$ uses its input as a timer: it rejects all strings that are longer than the number of steps $M$ takes to halt on $w$. (If $M$ never halts, $M^\prime$ accepts all strings. If $M$ halts, $M^\prime$ accepts all short strings and rejects all long strings.)  So if $M$ never halts, $M^\prime$ accepts all strings, specifically including all even numbers. If $M$ halts, $M^\prime$ rejects all long strings, specifically including all large even numbers.

So, our program constructs $M^\prime$ and asks C whether it accepts all even numbers. If C says yes, it means that $M^\prime$ accepts all strings because $M$ loops forever on $w$. We accept ("LOOPS FOREVER").  If C says no, it means that $M$ eventually halts on input $w$. We reject ("DOESN'T LOOP FOREVER").

In both cases, $M^\prime$ uses "accept" to mean "LOOPS FOREVER", and "reject" to mean "DOESN'T LOOP FOREVER". In the first case, we made $M^\prime$ accept all strings when $M$ doesn't loop forever. In the second case, we made $M^\prime$ accept all strings when $M$ does loop forever. Those differences contributed to the discrepancy.


Convert $1.75\times10^{15}$ to IEEE-32 format?

You need to understand how the IEEE-754 standard for floating point numbers works. It is not simply converting the number to binary.

Instead, the 32 bits that compose the representation of the floating-point number are split into 3 fields: sign, exponent, mantissa. Their sizes are 1bit, 8bit, and 23bit, respectively.
Each field is written in binary basis (unsigned).

If the value of the exponent field is $e$, and the value of the mantissa field is $m$ then, the these 32bits represent the number
$$ 2^{e-127} \times (1 + m\cdot 2^{-23})$$
the $s$ bit determines if the number is positive or negative.

So, to represent the number $1.5\cdot 10^{15}$ you will need to set:
$s=0$ (positive), $e=177$, and $m=2787263$. Calculate
$2^{e-127} \times (1 + m\cdot 2^{-23}) = 2^{50} + 2787263\cdot 2^{27} = 1500000014041088$, which is the closest you can get to $1.5\cdot 10^{15}$ with 32bit representation.

Use https://www.h-schmidt.net/FloatConverter/IEEE754.html as a simple converter and a way to learn how this representation works.

(Oops, I demonstrated the above for 1.5e15, while the question was about 1.75e15. Nevermind, replace with $m=4649908$ to get 1.74999999e15).


Why don't hard drives actually delete data?

There are two possible criticisms here, which should actually be leveled at the operating system, more accurately the file system:

Why does the OS not superficially erase data when a file is erased?
Why does the OS not thoroughly erase data when a file is erased?

Regarding point 1, historically speaking, you don't want to do this, since you might change your mind later on, and this way the data is still there. Of course, modern operating systems which have a recycle bin (some of them, say Linux and OS X, only implement this on their GUI) don't really benefit from this advantage. Rather, one reason you don't want to erase data superficially is that it is still possible to recover the data, say using lab analysis. Perhaps this is even feasible by reading the location many times and measuring the amount of errors. However, there is still something to gain here: malicious software would have a much harder time reading your data even if it is just erased superficially.

Regarding point 2, if you rigorously erased the data each time a file is erased, then you will probably shorten your hard drive's life. In addition, deletion would become a slow operation, which may hurt performance when many temporary files are created, a technique which had been common in the past.

If you really care about erasing your data before reselling older hardware, you can obtain software that will thoroughly erase the data and thus make it much harder to recover. If you're afraid that your hard drive, containing sensitive information, could be stolen at any point, then you should erase your sensitive data using the same kind of software.

It remains to consider the casual user who is worried about malicious software reading erased files. Such a user could benefit from superficial erasure of files. I am not aware of any file system providing this service.

If you're not using an actual hard drive but some other storage device, you might encounter other difficulties, check out this question on askubuntu.

As a workaround, and as suggested by the answers to the aforementioned question, you can encrypt your hard drive instead.


Given a PRAM may use arbitrarily many processors, why is Hamiltonian Cycle not in NC?

If I give all of the permutations of the vertices of a graph as input

That's not the input for Hamiltonian Cycle; you only get the graph.

  then I can assign a processor to each permutation

Since there are $n! \in \omega(c^k)$ many permutations, you don't have that many processors.

Here's the twist: if you were allowed to use all permutations as input, you'd of course have polynomially many processors in $n!$ at your disposal. But since your input is the graph you only get polynomially many in $n$.


Find an algorithm that sorts the nodes of a given graph acc. to distance from source node + value of the node's key

Hint:

Use BFS to calculate the distances.
Calculate the scores (sums of distance to source and serial number).
Use counting sort to sort the scores.
Go over the list again and output the vertices in sorted order.


Relation between best case and average case complexity

I think your definitions of $T_{\text{best}}$, $T_{\text{worst}}$, and $T_{\text{avg}}$ could use some clarification. I'll proceed assuming the correspond to best-, worst-, and average-case runtimes [1].

The first claim is false. The problem is that $f$ could dominate $T_{\text{best}}$ at an arbitrary rate. So we cannot make any claims about $f$'s status as an asymptotic lower bound of $T_{\text{avg}}$.

The second claim is true. Hint: prove $T_{\text{best}} = O(T_{\text{avg}})$, then use transitivity of $O$ to conclude the result.

[1] https://en.wikipedia.org/wiki/Best,_worst_and_average_case


What does an input string of epsilon mean?

In the context of NFAs, $\epsilon$ marks state transitions that do not consume input. These transitions thus express the non-determinism of the automaton.

When discussing the acceptance of $\epsilon$, the symbol marks the empty string (this is equivalent to the condition that an accepting state is reachable by a sequence of $\epsilon$-transitions from the start state). to avoid confusion, some authors use a different symbol for the empty string (often $\lambda$).


Which kind of branch prediction is more important?

I don't know which case is prevalent, but I would like to offer some thoughts on your proposal of double pipelines.

First of all, you would need double the wire which would consume double the energy and produce double the heat while active. While not needed, on the other hand, it would be completely useless. So one could argue that it is not a good use of resources that are rare on modern processors.

More fundamentally, unless you prefer one branch based on probability, how do you know which version to write through? If none, you might not save anything because other processors might have to wait on your decision, anyways. If you stick with one of them, you have essentially the same rollback probability and cost as you have now.

Let us do a rough calculation. For sake of simplicity, let us assume that handling two pipelines instead of one does not cause additional management overhead. The expected cost (e.g. energy, heat) is $C = c + p(c_r + c)$ with one pipeline ($c$ the cost of executing either alternative, $p$ the probability for rollback and $c_r$ the cost for rollback without the cost for executing the other alternative) but either $2c$ or even $2c + pc_r$ -- either is a lot larger than $C$ if $p$ and $c_r$ are relatively small, and $p$ certainly is (as far as I know, modern branch predictions have accuracies over 90%). And we don't get much for this cost! Expected execution times are $t + p(t_r + t)$ with one pipeline and $t$ resp. $t + pt_r$ with two; as $p$ is small, time savings are negligible.


Time complexity of printing prime numbers within a range?

Both "the time complexity is $O( end \cdot \sqrt{end} )$" and  "the time complexity is $O( (start-end) \cdot \sqrt{end} )$" are correct statements (assuming that arithmetic operations on the involved integers can be performed in constant time).
The second upper bound is tighter in some cases. For example, setting $start=end-10$ the first upper remains unchanged while the second one simplifies to $O(\sqrt{end})$.
Also notice that "In  notation  represents the problem size, which is the range between start and end in your case." is false.
The size of (any reasonable encoding of) the instance is $O(\log end)$.


Print maximum frequency number in an array(with slight modification)

Start by sorting the array. Now go over the array using four pointers, left, center left, center right, and right. The two central pointers bracket all the occurrences of some value $x$. The left pointer points at the leftmost value which is at least $x-M$, and the right pointer points at the rightmost value which is at most $x+M$. Using the positions of these pointers you can calculate the maximum frequency of $x$.

Traversing the array should take linear time, so the entire algorithm takes time $O(n\log n)$.

For a possibly simpler solution, you can sort the array and then use a single pointer to traverse it. Treat this pointer as one of the central pointers from the previous algorithm, and find the locations of all other pointers in logarithmic time using binary search. Traversal now takes time $O(n\log n)$, but this doesn't increase the asymptotic running time of the algorithm.


Algorithm for finding two smallest numbers in an array

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.


Does a greedy strategy exist for this instance of the Bin Packing Problem?

No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a solution for your problem in polynomial time using a greedy approach. Then, you could use your algorithm to solve in polynomial time the decision version of the Bin packing problem, which is known to be NP-complete (and, therefore, unlikely to be solvable in polynomial time).

How does this reduction work?

The decision version of the Bin packing problem involves deciding whether a certain number of bins (for example, 9) is optimal. If your hypothetical polynomial-time greedy algorithm finded a solution for 9 bins and failed to find a solution for 8 bins, then the answer for the decision problem would definitely be yes, and no otherwise.

Greedy is actually good.

All that being said, to obtain an approximate solution, a greedy approach is, probably, the best heuristic: sort the items in decreasing order of size and insert them one by one into the first bin that has room for it. This heuristic is called first-fit decreasing. The main appeal of this heuristic is that we pack the big items first and hope that the little ones fill up the spaces.


Error estimates of piecewise-linear curve approximations

It is impossible to achieve a guaranteed small error for general functions. If the function is given to you as a black box, for all you know it could be the constant zero other than some specific point in $[0,1]$ in which it is very large. If you have bounds on the first two derivatives, however, then you should be able to use Taylor's formula to accomplish your guaranteed approximation.

Matlab's function probably uses some heuristic, which works for reasonable functions. The idea of this heuristic is to empirically estimate the derivative of a function at a point by computing $[f(x+\epsilon)-f(x-\epsilon)]/(2\epsilon)$ for some small $\epsilon > 0$. When the derivative is large, the step size is small, and vice versa. Your worries are justified: in order to get a bound on the distance from the function, you need to have a global bound on the derivative in the entire interval being plotted, and then you can choose the tolerance accordingly. FPLOT is therefore just an optimization, choosing a larger step size when tolerable. From the description you gave it is not clear whether the step size is doubled once or keeps getting doubled — in the first case this optimization saves you at most half the time, and in the second case you could get large errors. (The first interpretation seems more reasonable.)


Can a subset of an NP-complete problem be in P?

Your question doesn't make sense:

  The problem is NP-complete (proven) for all input data (without exception).

This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, any problem is $O(1)$ on that input: you just output yes or no, depending which is correct for your input. When you do this, all of algorithm analysis breaks down and everything ends up useless. So, we don't do this.

$P$, $NP$, $NP$-completeness, polynomial time, etc. are all related to asymptotic complexity: as the size of input grows, how does the run-time grow? This only makes sense when you look across different input, the same way the derivative of a point in calculus is a property that takes into account the curve surrounding the point.

  We assume that P != NP.

Again, this doesn't affect your answer. If $P = NP$, then every $P$ set is $NP$-complete,* so there are a bunch of subsets in $P$. And if $P=NP$, the examples that people have given are all valid.

  Is it possible that there is a subset of the problem (infinitely large), that this problem is in P?

Yes, and the other answers have given great examples of this. But for posterity, here's yet another counter example.

$k$-coloring is $NP$-complete if you take $k$ as input, but $2$-coloring is an infinite subset of this that is in $P$.

* Except for $\emptyset$ and $\Sigma^*$, which aren't $NP$-complete for technical reasons relating to the form of reductions we use to define completeness.


Linear algorithm to measure how sorted an array is

Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A good way to avoid this problem is to shuffle the whole input randomly before we start sorting.

Now to gain more information about how "sorted" the array is, we have to define this quantity formally. We need a formal mathematical definition of "sortedness" before we can design an algorithm to measure it. Here are two different quantities that show in some way the "sortedness" of the array. Let us call the input array $A := a_1, \dots a_n$ where $n$ is the length of the array.

The first of which is the number of "inversions". So what are inversions? - you might ask. Inversions are pairs $(i, j)$ such that $i < j$ and $a_i > a_j$. Of course in a sorted array we have no inversions. Counting inversions can be done in running time $O(n\log n)$ using different methods among which are divide and conquer and using balanced search trees. However since counting inversions is not faster than sorting, I would not recommend it to find how sorted an array is as a pre-sorting routine.

Another measure is the minimum number of elements to be removed to turn the array sorted. This problem is equivalent to finding the longest increasing subsequence and it has an $O(n \log n)$ algorithm using dynamic programming. However, there is an simple linear time two approximation algorithm for this problem. Intuitively, the algorithm removes pairs of adjacent inversions until the array contains no more inversions. In pseudo-code the algorithm goes as follows:

- Let L be an empty linked list
- For each a := a[1] .. a[n] do
 - Append a to L.
- Set i := 1
- While a[i] is not the last element in L
 - while  a[i] no the first element in L
     and a[i] < a[i-1] do
  - remove a[i] and a[i-1] from L
  - Set i to the next element.
 - Set i to the next element.

Each time we remove two elements from $L$, they form an inversion an at least one of them should be removed. Hence we remove at most twice as many as the total number of elements that must be removed. Note that the running time can be bounded in $O(n)$ since the outer while iterate over all elements once and each call of the inner loop removes two elements and hence it can not be called more than $O(n)$ times in total.

One way to use this measure to sort arrays more efficiently is to use the previous algorithm to find all such pairs. Let $L_1$ be the list above after removing the elements from it and $L_2$ the list of all removed elements. Now since we know that $L_1$ is sorted, all we need to do is to sort $L_2$ in $O(h\log h)$ assuming $h$ is the number of elements has to be removed to turn the array sorted. Using some kind of sliding window (the conquer part of merge sort), we can build a sorted version of $A$ combining $A_1$ and the sorted version of $A_2$ in linear time. In total we get an adaptive sorting algorithm running in $O(n + h \log h)$.


Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

An example of a such problem in $\mathrm{DTIME}(n)$ is DNF satisfiability [1]. Its counting version is #P-complete [2], but its decision version can be solved by simply checking if there is a conjunction that is satisfiable.
For $\mathrm{DTIME}(1)$ I think the answer is that there are no such problems because we can iterate over all computation paths in $O(1)$ so counting is easy.
Note that in general, disallowing instances with answer 0 does not change the #P-completeness of any problem whose decision version is in P because we can check this case in polynomial time.
[1] https://en.m.wikipedia.org/wiki/Disjunctive_normal_form
[2] https://en.m.wikipedia.org/wiki/%E2%99%AFP-complete


Books to prepare before reading Knuth's The Art Of Computer Programming (TAOCP)

Don Knuth is a teacher, and is always very thorough when he writes.  So one should
expect that he states all prerequisites in his books.

To ascertain that, I went to look in my own issue of the first volume.

Indeed the preface states some prerequisites on page v, which he sums
up into "the single requirement that the reader should have already
written and tested at least, say, four programs for at least one
computer".

Starting page viii, he gives a few words regarding mathematical
content.
"the material has been organized so that persons with no more than a
knowledge of high school algebra may read it, skimming briefly over
the more mathematical portions; yet a reader who is mathematically
inclined will learn interesting mathematical techniques [...]". He
calls his organization a dual level of presentation.

Later he confirms that "a knowledge of elementary calculus will
suffice for most of the mathematics in these books, since most of the
other theory that is needed is developed herein ..."

Hence my best advice is to find out what you need by first reading the
prefaces of the various volumes of TAOCP in the library.  I suggest
adding some lighter reading, such as comics.  You may need it.

A word of warning though. Knuth tends to be too optimistic regarding the brains of other people.


It’s trying to give an intuition and nothing more so, if the passage is not helpful to you, just skip it. Look at the actual definition instead.

Honestly, I think it’s a very bad and unhelpful attempt at giving intuition. In some ways, $\lim$ gives more information; in some ways, it gives less. In some senses, $\lim$ is more specific in that it gives a single value that the function asymptotically approaches, and the notion of limit makes sense approaching points other than $\pm\infty$.  If the limit is a real number, then saying $\lim_{n\to\infty}f(n)=c$ gives more information than $f(n)=O(1)$, which suppresses $c$.

On the other hand, for many functions we're interested in, $\lim_{n\to\infty}f(n)=\infty$ so $\lim$ gives almost no information.  In those cases, big-$O$ allows you to give more information.

I wouldn’t worry about the “suppressing a number” stuff. Saying $3x=O(x)$ suppresses the number three but $3x+1=O(x)$ suppresses two numbers, $3x=O(3x)$ suppresses nothing and $x=O(3x+1)$, er, un-suppresses stuff. Somethingl ike $x=O(x^2)$ is even less clear. It's hard to tell what de Bruijn really intended.


The list takes $2*N*k$ bytes in total. A circular linked list is just a simple linked list with its last node's next pointer pointing back towards head. So, no extra pointer is required to make it circular. Hence, the total space is $2*N*k$.


Force-directed graph optimization with step-wise costs and constraints

This is a discrete optimization problem.  I think one possible approach would be to approximate the discrete elements with continuous, differentiable functions and then optimize the resulting substitute problem.
Consider the function $f(x)=1$ if $x\ge 0$, or $f(x)=0$ if $x<0$.  This is a discrete function, which can be approximated by the sigmoid function $S_\alpha(x) = 1/(1+e^{-\alpha x})$.  The sigmoid is effectively a "softened" version of $f$.  The larger that $\alpha$ is, the better the approximation.  And notice that the sigmoid function is continuous and differentiable and monotonic.  Similarly, the function $f(x)=c$ if $x \ge t$, or $f(x)=0$ if $x<t$, can be approximated by $c/(1+e^{-\alpha (x-t)})$.
So, take your problem, and replace each of the discrete decisions with a softened version.  For instance, you have a rule that says "if a pair of nodes is at distance $\le$ 25m, then multiply a factor of 1.04".  I suggest you replace this with the rule "multiply a factor of $1.04/(1+e^{-\alpha(25-d)})$ where $d$ is the distance between those two nodes".  In this way, each rule can be replaced with a "softened" version, where the parameter $\alpha$ determines how soft it is: the smaller $\alpha$ is, the smoother the function; the larger $\alpha$ is, the better an approximation it is to the discrete rule.  Your requirement that the product be between 0.67 to 1.5 can be replaced with a version that applies a penalty if the product is below 0.67 or above 1.5, and then you compute a softened version of this penalty for each node.  Finally, the objective function can be the sum of these penalties.
Once you've done that, you have a continuous, differentiable objective function, so you can minimize it using gradient descent.  I suggest that you initially set $\alpha$ to be a fairly small value, and during gradient descent you gradually increase $\alpha$ until finally it is a very large value (i.e., slightly increasing $\alpha$ after each iteration of gradient descent).
As a side note, instead of working with the product of factors, I recommend you take the log of everything, so that work with the sum of log factors.  Usually summations behave more nicely with gradient descent than products.
I suggest that you use gradient descent with random restarts.  For instance, you might do 1000 trials, where in each trial you start with randomly chosen initial positions, and then do gradient descent from there until convergence; and you take the best result across all of these 1000 trials.
You could also try replacing gradient descent with any other iterative method, such as Newton's method.
I don't know whether this will work well for your particular problem, but it is one thing you could try that might work.


Graph partitioning with parts of equal size

Your problem is a special case of graph partitioning. When $k=2$, the problem is known as minimum bisection, and is NP-complete.


Add a road to a network (Graph problem with Dijkstra)

Who knows. You'd have to ask them; that doesn't provide enough details to narrow it down.

If I had to guess, I imagine that perhaps they had in mind that they would do Dijkstra's algorithm once to measure the distance from $s$ to each vertex; then for each candidate edge $(u,v) \in E'$, they would use Dijkstra's algorithm to find the distance from $u$ to $t$ assuming $(u,v)$ has been added to the graph; and use this to find the best edge to add.

In any case, their alternative solution is considerably slower, so it's a poor choice and should not be used.  It's far faster to use the first solution you listed.


Minimize edges of a directed unweighted graph

There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ obtained by replacing each undirected edge {u,v} of $H$ with the pair of directed edges $(u,v)$ and $(v,u)$.

If there is a Hamiltonian path traversing the vertices $\langle u_0, \dots, u_{n-1}, u_n = u_0 \rangle$ of $H$, in order, then the set of $n$ edges $\{ (u_i, u_{(i+1) \bmod n}) \mid i=0,\dots,n-1\}$ of $G$ induces a subgraph $G'$ with your property.

If there is a subgraph $G'$ of $G$ with at most $n$ edges that satisfies your property, then it must have exactly $n$ edges. Moreover the in-degree and the out-degree of each vertex must be exactly $1$, and the undirected version $H'$ of $G'$ must be connected. In other words $G'$ is a cycle that that traverses each vertex of $G$ exactly once, showing that $H'$ is a Hamiltonian path of $H$.


Rounding logarithm to next integer — Potential function

The analysis there is slightly wrong, though the conclusions are correct. Here is the correct calculation:

$i$ is not a power of 2. In that case $\lfloor \log_2 i \rfloor = \lfloor \log_2 (i-1) \rfloor$ and so $\Phi(i) - \Phi(i-1) = (2i+1) - (2(i-1)+1) = 2$.
$i$ is a power of 2. In that case $2^{\lfloor \log_2 i \rfloor} = i$ and $2^{\lfloor \log_2 (i-1) \rfloor} = i/2$, and so $\Phi(i) - \Phi(i-1) = (2i - 2i + 1) - (2(i-1) - i + 1) = 2-i$.


Does there exist a language which is PSPACE-complete and regular?

There exists a PSPACE-complete regular language if and only if P=PSPACE, which is unknown.

In fact, we can say even more: the language $\{1\}$ is PSPACE-complete if and only if P=PSPACE.


Exactly what is the difference between Finite Automata and Transition Graphs?

Your nomenclature is highly nonstandard. It seems that "finite automata" are what are usually known as DFAs, whereas "transition graphs" are a special case of GNFAs in which the only regular expressions allowed are words; alternatively, they are like $\epsilon$-NFAs, only transitions can be marked by arbitrary words (rather than just words of length at most 1).

There are two differences between your FAs and your TGs:

FAs are deterministic: at each point in time, there is exactly one choice of which state to go to next. There is no such restriction on TGs. Moreover, whereas FAs have a unique initial state, TGs have an arbitrary number of initial states.
Transitions in FAs are labeled by symbols. In contrast, transitions in TGs are labeled by words.

These are exactly the differences that you listed.


Yes, you could try applying the LSTM iteratively 20 times.  In other words: use the first 200 datapoints to predict the 201th; then use datapoints 2..201 to predict the 202th; and so on, until you predict the 220th.  You'll have to evaluate how well this works on a test set; it might work, or it might not.

This could still fail badly.  It could even be that there is just no way to predict 20 timesteps out.  For instance, it's possible that the short-term correlation is high but the long-term correlation is low.  Think of the weather: it's possible to predict tomorrow's weather with relatively high accuracy, but seems to be extremely hard to predict the weather 3 weeks out.  So there might just be fundamental barriers to making predictions that far into the future.


If a sparse language is NP-complete then are all NP languages sparse?

If we only consider the latter half of the question: "are all NP languages sparse", the answer is no. A counterexample is $\{0,1\}^*$. It belongs to NP but is not sparse.

However, you added a precondition: "a sparse language is NP-complete", and $A\rightarrow B$ is true if $A$ is false, so the answer depends on whether there exists a NP-complete sparse language. Since it remains open whether there exists a NP-complete sparse language, your question also remains open.


What is the difference between control flow and control logic?

Control flow is oriented around the idea of imperative statements. What is the computer doing at this given time? What will it do next? What actions should it perform?

Declarative programming abstracts this away (or at least tries to). You're program is now not a set of instructions for the computer to follow, but a sort of specification for the problem. In order to be powerful enough to be Turing complete, these specifications are usually recursive.

The main difference is that a declarative program makes no promises about how it will be run. You state the logic, and the compiler/interpreter makes a program that fulfills that logic.

One of the most important aspects of a declarative description is that it's (relatively) standalone. A procedure in an imperative language says "do this thing to the current state". A declarative program says often will not depend on its context, or will make its context more explicit.

In practice, you can usually infer the control flow of a declarative program pretty easily, especially in strict languages like ML, F# or Elm. There's a pretty close correspondence between recursive declarations and loops, and between declarative functions and imperative procedures.

Things get fuzzier in a language like Haskell, where evaluation is lazy (you don't decide what gets run when). Or in Prolog, where there's an implicit backtracking search that the runtime does for you. You're not coding these things manually, you're simply specifying what the result should look like, not how you will get that result.


If $n$ is a power of two, then you can simply determine the value $i$ by determine bit per bit in the binary representation. So if $n=8$ then you ask your source 3 times. Suppose you get as result $1,1,0$ then you would map this event to the event that you have selected $i\leftarrow\text{bin}(110)=6$. Clearly you need $\log n$ bits.

If $n$ is not a power of two, then things a are more tricky You can definitely can get an approximate uniform distribution, if you follow the method above. Say you sample $k$ bits, and you get the $k$-digit binary number $b$, then you can pick
$$i\leftarrow \frac{b}{2^k}n.$$

The more bits you sample, the closer you approach the uniform distribution. I am sure there are more involved methods for case wehere $n\neq 2^k$


Why are the two farthest points vertices of the Convex Hull?

Let $p,q$ be two points in your set of points. The point $p$ can be represented as some convex combination $\sum_i \alpha_i p_i$ of points on the convex hull. The triangle inequality gives
$$
\|p - q\| = \left\| \sum_i \alpha_i (p_i - q) \right\| \leq \sum_i \alpha_i \|p_i - q\| \leq \max_i \|p_i - q\|,
$$
where both inequalities used $\alpha_i \geq 0$ and the second also $\sum_i \alpha_i = 1$. We conclude that $p$ can be replaced by some point on the convex hull. Similarly, having replaced $p$ by a point on the convex hull, we can replace $q$ by a point on the convex hull.


Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths

Your question is quite open-ended, in that you have not specified how accurate the upper bound should be, nor how efficient the algorithm should be. There is certainly a trade-off between the run-time and the accuracy.

Ways to get an exact answer:

Naive brute force - I guess you know what this means (very slow)
Observe that it is easy to calculate the number of ways of the graph is a tree (start from the leaves, and when they join up, just count number of ways of joining the two branches

ie. #ways = #ways(branch A) * #ways(branch B) * {#nodes(branch A) + #nodes(branch B)} Choose #nodes(branch A)

Thus iterate over all possible trees, and sum up the number of ways of assembling the tree.

This method is faster than a naive brute force, but it is still brute forcing on all the trees

For an upper bound:

$n!$ - very quick but not accurate
Using the same observation as before (easy to calculate number of ways for a tree), you can use the quick method for all subtrees/leaves off the main component. Then join it all up.

For example, suppose the main component connected to the root has $a_0$ nodes, then you have two subtrees hanging off that main component with $a_1$ and $a_2$ nodes, each with $b_1$ and $b_2$ ways of assembling them respectively.

Then, letting $b_0$ = $a_0!$ (an upper bound on the main component), an upper bound on the whole graph is $b_0b_1b_2\frac{(a_0a_1a_2)!}{a_0!a_1!a_2!}$.

This method is very quick, but although it is a much better upper bound than $n!$, it can still be very far off the exact answer.
A refinement to either of the above methods can be made, by considering the earliest that a particular node can appear in the sequence. Basically, it is a way of counting such that, for example, since you know $B$ can never be the 1st in the sequence, and $C$ is 3rd or later, etc., you can count in such a way to avoid that possibility.

For example, in the above example, first consider that there are 2 ways of ordering $E$, $F$, in places 4-6, call this sequence $s_1$. Then there are 2 ways of ordering $C$, $D$ in places 3-6 (sequence $s_2$). So you can now merge the two sequences. Because the intersection of their possible places is 4-6, you know that in place 4-6, there is one element from $s_2$ and two elements from $s_1$. Thus, the number of ways of merging them is $\frac{3!}{2!1!}=3$, thus the merger of the two sequences results in a sequence with $2\times 2 \times 3=12$ ways, in a possible range of places ranked 3-6. After merging with a subsequence consisting of $B$ and a subsequence consisting of just $A$, you have an upper bound of $12$ ways of assembling it.
Further refinement may also be made by considering the latest a node can appear (eg. $C$ and $D$ cannot be in place 6. Thus, when merging sequences $s_1$ and $s_2$, an even better upper bound is $2\times 2 \times \frac{2!}{1!1!}=8$ ways.

There may be other ways I cannot think of. But each refinement will add complexity, and running time to your algorithm.

I am unsure if there exists an efficient algorithm for finding the exact answer (in $P$ time).


Why the language of unary primes isn't regular

This is one of the more difficult common applications of the pumping lemma, so I'll give you an outline to get you started.

Suppose $L$ is regular and let $k$ be the pumping length.  Let $p$ be a big enough prime* so $1^p\in L$, and write $a=1^r1^s1^t$, with $r+s\leq k$ and $s\geq 1$, so $t=p-r-s$.  You need to find some $n$ such that $1^r(1^s)^n1^t\notin L$, i.e., such that $r+ns+t$ is not prime, which you can show by writing it as a product of two factors, both strictly bigger than $1$.

* You'll certainly need $p>k$ to apply the pumping lemma, but you might need it to be bigger still, to guarantee that the factors are bigger than $1$.


Show that run time complexity of operations on 2-4 tree is $O(\lg n)$

The tree is height-balanced, therefore the height of the tree is $O(\log n)$. So any insertion has to travel at most $O(\log n)$ steps deep into the tree to find the proper insertion place. Then it also takes another $O(\log n)$ steps the rebalance the tree. The same idea can be applied to searching and deleting in the tree.

The $O(\log n)$ height bound may be difficult to see in a 2-3-4 tree, so I will offer an alternative way to come to this realization. Any 2-3-4 tree is isometric to a proper Red-Black tree. That is to say, "they are equivalent data structures. In other words, for every 2–3–4 tree, there exists at least one red–black tree with data elements in the same order." A Red-Black tree is a balanced binary search tree whose height is more clearly bounded by $O(\log n)$ and so are all of its operations.


Combinatorics approach to staircase problem

Let $W(n)$ be the number of ways you can reach step $n$ by 1- or 2-step moves. Then $W(1)=1, W(2)=2$ (by two 1-step moves or one 2-step move). Then to reach $n$ height, your last move is either a 1-step move from height $n-1$ or a 2-step move from height $n-2$, giving us the recurrence $W(n) = W(n-1) + W(n-2)$. I'll leave the solution of this recurrence to you. (Hint: it should be familiar.)


Filling a matrix with the sum of conditional values

Let $V$ be the $N\times P$ matrix whose columns are the vectors $v$, and let $D$ be the $P\times P$ diagonal matrix with elements $D_{vv} = \alpha_v$. Then you want to compute $VDV^T$. Computing $U = DV^T$ takes time $NP$, and it remains to compute $VU$. When $P < N^{0.3029}$, for every $\epsilon > 0$ there is an (impractical) algorithm to compute this product in time $O_\epsilon(N^{2+\epsilon})$. See Le Gall, who improved on an earlier result of Coppersmith.


Today's CPUs are incredibly complex beasts. Sure, you can go rummage in computer architecture books and get a rough idea how a very simple CPU works. Understanding in detail how the CPU in your PC  (or even your smartphone) works will require a lifetime, if not more. I suspect noone at Intel/AMD really undestands their latest CPU fully.

For example, today's processors take instructions from RAM, translate them into microinstructions internally, reorder and schedule those working even on several copies of the programmer-visible registers in parallel where possible (doing more or less the job of an optimizing compiler), and finally executing the resulting stream(s) of microinstructions.

Today's CPUs are much, much faster than RAM (in the time required to fetch a word from memory they can execute hundreds of instructions). Cache memory, and it's efficient use, predicting what will be read next, is crucial. Another area of significant complexity.

Add circuitry to compute the various operations, including floating point and assorted functions, like square roots and trigonometric functions. A box marked "floating point unit" right there.

And this doesn't yet consider the GPU that is integrated in some models...


What advantage does Tangaroa offer over PBFT?

The notion of perfection in consensus:

Tangaroa is a BFT flavored Raft usually consisting of 3 - 5 systems in a cluster and can tolerate failure of up to 1/2 of the node count with a concept of "randomization in election of leadership".

PBFT is the "practical" BFT system designed for more deterministic behavior with a concept of "eventual leadership".
However, I came across this research (https://www.zurich.ibm.com/~cca/papers/sieve.pdf) mentioning "Fault-tolerant execution on multi-core servers poses a new challenge, even for deterministic applications,
because thread-level parallelism may introduce unpredictable differences between processes." in Related Work.

Choosing which one?
I'd leave that to you once you'll be able to determine the nature of the state machine you'd like to see operational.

Hope this helps :)
Comments and corrections,(if any) are most welcome!


The Absolute Minimum Every Software Developer Absolutely, Positively Must Know about Computer Science (No Excuses!)

> What's the absolute minimum every software developer absolutely,
> positively must know about computer science (no excuses!)?

IMO every software developer should absolutely know (no excuses!) the quote attributed to E. W. Dijkstra:

"Computer science is no more about computers than astronomy is about telescopes"

:-D :-D


Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time

If you believe in the exponential time hypothesis, then you can construct such an example by padding SAT. The ETH states that solving SAT on $n$ variables takes time $2^{\Omega(n)}$; let's say the time is $T(n)$. We can assume that SAT instances consist of at most $O(n^3)$ clauses, and so have length at most $\tilde{O}(n^3)$. Pad such an instance by adding $N = T(n)^{1/c}$ (where $c > 1$ need not be an integer) spaces. According to the ETH, the resulting languages requires time $\Omega(n^c)$ to solve in the worst case (the "best case" time complexity of a problem is almost always $\tilde{O}(n)$, depending on your model of computation and how devious the problem is), but witnesses can be verified in time $\tilde{O}(n)$ and $O(\log n)$ space; most of these resources are spent on checking that the input is well-formed.

The same idea would work even with much weaker hypothesis, such as P$\neq$NP; I'll leave you the details.


Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra

For part (a), there are (at least) two approaches:

Outline a LOOP program which simulates a given IF program. Seems pretty messy.
IF programs can be simulated by a WHILE program, i.e. they are recursive. Moreover, the running time of such a simulator is very manageable. A recursive function with a primitive recursive bound on the running time is primitive recursive, and so implementable as a LOOP program.

For part (b), there are again two approaches (leading to the same result):

Suppose that you had a universal LOOP program. Try running the argument used to prove that the halting problem is undecidable, and see what you get.
The running time of every LOOP program is on some level of the primitive recursive hierarchy, and the latter is strict and has infinitely many levels. Consider the running time of a universal LOOP program and see what happens.

Part (c) is about universal Turing machines.


$\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?

Consider what happens when you feed into a majority gate the the inputs $x_1,\ldots,x_k$ and $k-1$ zeroes. You get an $\mathsf{AND}$ gate. If you feed into it $k-3$ zeroes, you get a gate corresponding to $x_1+\cdots+x_k \geq k-1$. Using similar ideas, you can construct a constant-depth circuit over the basis $\{\lnot,\mathsf{MAJ}\}$ that computes $x_1+\cdots+x_k = \ell$ and so $\mathsf{MOD}_{2017}$.

If you're not allowed to use constants but there is a tie-breaking rule for $\mathsf{MAJ}$, then you can implement constants using $\mathsf{MAJ}(x_1,\lnot x_1)$, whose constant value will depend on the tie-breaking rule.

If you're not allowed to use constants and every majority gate needs to have an odd number of inputs, then it is generally not possible to construct such a circuit. Indeed, suppose that you plug $x_i = x_1$ for all $i>1$, and that $k$ is chosen so that the output is constant whatever the value of $x_1$ is (this depends on your definition of $\mathsf{MOD}$, which you haven't supplied). On the other hand, you can prove by induction that every gate computes either $x_1$ or $\lnot x_1$, and in particular not a constant function