How to write decoder for compressed stringified objects

Found the answer.

As described in question about encoding schema, there can be multiple objects falling to same encoded string. Hence I was facing the difficulty to write the decoder.

To solve the above problem, I've added 2 more chars to know the start of the object/array;

| : boundary indicator. To separate consecutive dynamic data fields.
^ : next field(set of fields) is/are repeated array item
$ : empty value
# : missing, null, undefined field
@ : empty object or array
! : missing, null, undefined object or array
Y : True
N : False
{ : object start
[ : array start


Implement a search procedure in terms of a set test procedure

Hint: Suppose you asked your oracle whether there is a subset of $\{x_2,\ldots,x_n\}$ whose product is $t$. What can you deduce if the answer is YES? What can you deduce if the answer is NO?

Here is the full solution:

   If the oracle answers YES, we deduce that we can remove $x_1$ from $S$. If the oracle answers NO, we deduce that every solution must contain $x_1$. We therefore remove $x_1$ from $S$ and update our target product to $t/x_1$. Continuing in this vein for $n-1$ more iterations, we find a solution. This requires at most $n$ calls to $\mathsf{Prod}$ in total.


Regular languages that can't be expressed with only 2 regex operations

With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$.  With only concatenation and the Kleene star, you can't describe a language such as $L = \{a,b\}$.


For a computational problem, can the set of instances be finite?

A finite problem can be decided in O(1) time: we can simply compare the input to a finite (bounded) list of known cases, and emit the output consequently.

Indeed, for that we do not need a Turing powerful system: a finite-state automaton suffices.

So, the problem is indeed trivial.

Co-finite (finite complement) problems are similarly trivial.


Proving that a language is not Recursive

Proving that the language is in RE is quite easy: simulate the machine on every input $w\in \Sigma^*$, in minlex order, for $|w|$ steps. If an input is accepted - accept.

Proving that the language is undecidable can be done by reduction from
$$A_{TM}=\{<M,w>: M\text{ accepts }w\}.$$
A possible reduction:

Given input $<M,w>$, construct a new TM $M'$ that works as follows: given input $x$, simulate $M$ on $w$. If $M$ accepts, accept. If $M$ rejects, reject, and of course if $M$ does not halt then so will $M'$.

Now, if $<M,w>\in A_{TM}$, then $M$ accepts $w$ within $t$ steps, for some $t\in \mathbb{N}$. Thus, for a word $x$ with $|x|>>t$ (the size of $|x|$ needed depends on the manner of simulation, but can be done with $O(t\log t)$), the simulation of $M$ on $w$ will terminate within $|x|$ steps, and $M$ will accept $w$, so $M'$ will accept $x$, and $<M'>\in L$.

Conversely, if $<M,w>\notin A_{TM}$, then $M'$ will not accept any input, so $<M'>\notin L$, and you are done.


The 3-clique problem is, given a graph, does it have a clique of size 3? This is solvable in polynomial time. Likewise, for any fixed $k$, the $k$-clique problem (given a graph, is there a clique of size $k$) is solvable in polynomial time.

But in the clique problem, we are given both the graph and $k$ and asked if there is a clique larger than size $k$. This problem is NP-Complete. For example, let's suppose someone sets $k = \frac{n}{2}$. Then the running time you give is definitely exponential.

This should make intuitive sense -- in the $k$-clique problem, if I fix $k$ to be, say 1000, ($k$ being a constant with respect to $n$.) then as graphs get really really large (like trillions of nodes), I still only have to check every set of 1000 nodes. But in the clique problem, as the graph gets really gigantic, the sets I have to check might get gigantic too.

(Edit. To finish answering the question, clique is NP-hard because for example 3SAT can be reduced to it in polynomial time, and clique is in NP. However, $k$-Clique (for any given $k$) is not NP-hard).


In the context of network routing, negative-weight edges are meaningless.

Bellman–Ford is just an algorithm for finding lowest-cost paths in a weighted graph. The algorithm itself doesn't know or care what the vertices, edges and weights mean: it just finds paths. Interpreting those paths is for the user.


Is sierpenski's triangle considered to be a computational model?

I would not call Sierpenski's triangle a computational model.  A computational model should be a system that has a way to compute something.  This means there needs to be a way to supply an input, and a way that the system does something with that input to compute something.  Sierpenski's triangle is a single thing (a single set), and it is fixed -- there is no way to supply different inputs and get a different output.

For similar reasons, I would not call Pascal's triangle a computational model.

However, I would call rule 90 a computational model.  There are standard ways of providing an input and computing stuff (e.g., the input bitstring is interpreted as a row, and then successive rows are derived using the cellular automaton rules, which is interpreted as a computation).  Similarly, I would call rule 110 a computational model.  Or, more generally, I might call cellular automata a computational model, and rule 90 and rule 110 as two instances of cellular automata.


Does checking the middle bit of an input require a log(n) space pointer?

You can do this with constant amount of memory (according to your definition of space complexity). Assume $n \ge 2$ (the complementary case is trivial).
Mark the work tape on the starting position of the input, then move right until you reach the end of the input and mark the last position of the input on the work tape.

Repeat the following:

Go back to towards the beginning of the input until you find a marked position on the work tape.
If the position immediately to the right is already marked, report the current position as the middle of the input.
Otherwise, remove the mark from the current position (i.e., write the empty symbol), move right, and mark the current position.
Advance towards the end of the input until you find a marked position on the work tape.
If the position immediately to the left is already marked, report that position as the middle of the input.
Otherwise, remove the mark from the current position, move left, and mark the current position.


The type of neural networks you have in mind (where each neuron is a threshold function taking on $0$ or $1$ values), with $n$ neurons is a dynamical system with state space $\{0,1\}^n$. After every tick of the clock, the neural network is in some new state, defined by the current values of its neurons.

Because the state space is discrete, I don't think your second question makes sense here. Linear vs. non-linear are terms applied to continuous-time dynamical systems.


Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$?

$t$ and $n$ are independent numbers. Any string in the language consists of $t$ units, where each unit consists of $n$ $1$s followed by $n$ $2$s.  In particular, then, the string generated by any choice of $t$ and $n$ contains $tn$ $1$s and $tn$ $0$s.


Looking for a good algorithm to divide the nodes of a complete graph into groups

One possible approach would be to use local search.  This probably won't find the optimal solution, and there are no guarantees, but if you're lucky, it might find a solution that is decent.

In local search, given a candidate solution, you need a way to randomly pick a neighboring solution.  In the context of your problem, one way to do that might be to pick a pair of groups and a vertex $v$ in the first group, and remove $v$ from the first group and add it to the second group.  (This will only be legal if the first group is not already at the minimum size, and the second group is not already at the maximum size.)

You could then apply a technique like simulated annealing.  You'll probably need to experiment with the tuning parameters, and experiment with the method, to see whether it produces useful solutions or not.

This will require you to be able to quickly compute the effort associated with a single group, given the list of vertices in the group.  You might want to ask separately about that problem.  It sounds related to the Traveling Salesman Problem, which is NP-hard, but there are off-the-shelf solvers that implement sophisticated algorithms for finding a solution, and for the group sizes you are talking about (8-11 vertices), this might be relatively fast.  The twist in your situation is that the TSP doesn't allow visiting a vertex more than once, but it sounds like you are willing to allow repeated visits, so we need to make adjustments to make to allow that.  The following method should suffice: use an all-pairs shortest paths algorithm to compute the distance $d(u,v)$ between each pair of vertices, then replace the edge weight on the edge $u \to v$ with $d(u,v)$, then find the TSP solution; after this adjustment, no repeated visits will be needed any longer.


Lower bound for matrix determinant algorithm

The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence
$$
T(n)=nT(n-1) + O(n^3),
$$
with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$.
In the other direction, let $S(n) = T(n)/n!$. Then
$$
S(n) = S(n-1) + O(n^3/n!),
$$
with a base case of $S(1) = O(1)$. Since $\sum_{n=0}^\infty n^3/n!$ converges, we get $S(n) = O(1)$, and so $T(n) = O(n!)$. (The same argument also proves the lower bound.)


About the relationship between non-termination and inconsistency?

Some trivial type systems

Let the set of types be $\bot,\top$ and the sets of terms be $a,b$, with typing rules

$$
\vdash a:\top \qquad \vdash b:\top
$$
and computational rules
$$
a \to b \qquad b \to a
$$

Then, the resulting system has no (weakly/strongly) normalizing terms, yet it is consistent since no term inhabits $\bot$.

We can also allow recursion on $\top$, if we want.

$$
\dfrac{
\Gamma, x:\top \vdash e:\top
}{
\Gamma \vdash {\sf rec}\ x. e\ :\top
}
$$
with the obvious computational rule
$$
{\sf rec}\ x. e \to e\{{\sf rec}\ x. e/x\}
$$

On adding full recursion

Of course, we can't allow unrestricted recursion on $\bot$, otherwise ${\sf rec}\ x.x:\bot$ leads to an inconsistency.

Adapting more serious type systems

If we take any strongly normalizing typed lambda calculus, we can modify the computational rules to add a silly reduction step
$$
t\to t
$$
for any term $t$.

The new calculus has as inhabited types the same inhabited types, so it preserves consistency. The calculus is not even weakly normalizing, though.


Generate string with large Kolmogrov complexity

No. This is basically Chaitin's incompleteness theorem.

Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you could do it for every string, then you can write a program of size $\log n + O(1)$ to search for and eventually output strings with complexity $n$, which is a contradiction for sufficiently large $n$.


sum of squared distances from mean equals all-pairs sum of square distances?

This can be easily seen by a change of coordinates that makes the average $\bar{x} = 0$. This can be done by translating the whole plane, preserving all distances. Since the equation depends only on distances, its validity does not change.

Let us denote $|S|$ by $n$. The left hand side becomes $n \sum_{i \in S} ||x_i||^2$. The right hand side can be simplified as follows:

$$
\sum_{a < b} ||x_a - x_b||^2 = \frac{1}{2} \sum_{a, b} ||x_a - x_b||^2
= \frac{1}{2} \sum_{a, b} ||x_a||^2 + ||x_b||^2 - 2 x_a \cdot x_b
$$

The first equality follows from the fact that $||x_a - x_b||^2 = ||x_b - x_a||^2$. The second is simple expansion of quadratic expression of vectors.

If you split the sum and notice that the first two terms are equal to $n \sum_{i} ||x_i||^2$. You get that $\sum_{a, b} x_a \cdot x_b = 0$. This is easy to see since:

$$
\sum_{a, b} x_a \cdot x_b = \sum_{a} x_a \cdot \sum_b{} x_b = (\sum_{i} x_i)^2 = (n \bar{x})^2
$$

which is zero since the mean vector is zero.

Of course this calculation is all well known as an identity on variance. If you have a random variable $x$ such that $Pr[x = x_i] = 1/n$. Then, your left hand side is $n^2 Var(x)$ and the right hand side is the right hand side of the last equation stated here.


Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane

Step 1. Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

Step 2. Define a mapping $M$, where the key will be a closed integer interval and the value - ordered set of integers. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $y$-coordinates into the mapping $M$ - their corresponding $x$-coordinates must be inserted into the set, corresponding to this interval:

function Insert(M, x, y0, y1)
  if mapping M contains element ([y0, y1] -> S)
    insert x into set S
  else
    insert element ([y0, y1] -> (x)) into mapping M

You can drop (or ignore in all subsequent steps) all the elements of the mapping $M$, for which their value set contains only a single number.

Step 3. The mapping M will contain elements like this:

$$([y_0, y_1] \rightarrow (x_0, x_1, ..., x_{m-1}))$$

The biggest rectangle with "vertical" side $[y_0, y_1]$ will have "horizontal" side $[x_0, x_{m-1}]$, so you can ignore all the middle elements of the ordered set. Finally, scan all the elements in the $M$ to find the element with largest rectangle area $A$:

$$A = (y_1 - y_0) \cdot (x_{m-1} - x_0) $$

Number of intervals in $M$ is $O(n^2)$, so time to insert into the mapping will be $O(n^2log(n))$.


Hints: First part: Suppose that $f$ is not one-to-one. That implies that $f(x) = f(y)$ for some $x \neq y$. Can $g \circ f$ be a bijection? Similar idea for the other half. Second part: We know that $f$ must be one-to-one and $g$ must be onto. So if $f$ and $g$ are not bijections, then $f$ must not be onto and $g$ must not be one-to-one. See how these two conditions mesh together.


Constraint violation and efficiency in search

Another example is interior-point algorithms for convex optimizations, which (if I remember correctly) start at an arbitrary point and try to simultaneously get into the feasible region and optimize the objective function. They are provable and (to some extent) practically faster than the simplex algorithm (and related algorithms like the criss-cross algorithm), which does a local search inside the feasible polytope.


Is programming an emulation of the real world?

This is a third true, a third false, and a third unknown.
Why you might think its true
As you have stated, it does intuitively makes sense that any kind of "computation" or "effect" in the real world has an equivalent computation in the computer. After all - the world we know is compromised of atoms and such, and it makes sense we can store such data in bits. If im not mistaken, the Church-Turing hypothesis that was based on this intuition hypothesizes that anything that can be done in the real world can be done in a computer
Why we might think its false
Think about our world - it has a lot of people, which independently and simultaneously do things. This kind of behaviour is not really natural for a computer - a computer can only process one thing (or at most a handful of things, if it has a few cores) at once. This leads us to think it might be impossible to think of the world as a giant computer.
Why we still don't know, and will probably never know
Physics is a branch of science that always develops. There is always more to uncover about our universe and its underlying mechanisms. Therefore, there will always be a way to create a newer and mpre sophisticated computer that can do more things. For example, the recent developments for quantum computers might change things up: In a quantum computer there are things that can be computed faster than in a normal computer. In fact, a quantum computer is capable of doing something similar to parallel computing (a common misconception is that it does compute in a parallel way, but actually it does something else that creates this effect).
This means that both statements for why it could be true and why it could be correct! It might be true that normal computers can't emulate all of the stuff that can be done in the real world, but don't know whether it will still hold for a newer computer based off of a brand new idea in physics that would be developed in a few hundred years from now.
Still, this is only my own opinion. If you want more (and probably better) answers, you might want to consider asking this to philosophers.


It would only make sense to service interrupts after a full cycle completes, not immediately, because intermediate values are only saved to the register file at the end of each cycle. Being able to service an interrupt at any point in the cycle would add a lot of complexity to a processor for very little benefit. Interrupts are time-critical, but they're typically not microseconds and nanoseconds critical.

How this happens specifically is a matter of micro-architecture, so it can vary from processor to processor, and the processor manufacturers do not share that level of implementation detail.
The interrupt hardware does not queue interrupts. Different hardware interrupts are asserted by electrifying pins on the processor. When an interrupt pin is sensed, the processor transfers control to a special piece of software called the interrupt service routine in the operating system. Thus, handling an interrupt requires many cycles at a minimum. It is possible that an interrupt could be dropped if two interrupts were to occur near-simultaneously.
However, modern OSes use a variety of techniques to handle interrupts efficiently, some of which might involve queuing. These techniques improve the behavior of the computer as well as essentially eliminating the possibility of dropping interrupts under normal conditions.

A classic approach used in Linux is the top-half/bottom-half approach. When an interrupt occurs, the physical hardware is handled by the top half, but any significant processing is deferred to the bottom half that can run at a later time. For example, suppose we're writing a driver for a network card. The top-half of the network card driver might be responsible for copying an incoming packet from the network card into the computer's memory and clearing the interrupt, while the bottom half (also called a tasklet in Linux) is responsible for processing the packet and routing it. This allows the physical interrupt to be cleared as quickly as possible by retrieving and queuing multiple packets in software, even though the processor interrupt hardware does not have any notion of queuing.

However, modern Linux has superseded all of these concepts, and now it is common to use threaded interrupt handlers, which uses a similar deferred processing approach as the top-half/bottom-half mechanism, but simplifies the instantiation of the bottom half in the kernel. Here, there might not be an actual queue of interrupts, but each interrupt can be handled concurrently by a different thread in the kernel.


Data structure for efficient searching, when insertions and removals are only one-sided

Store the elements as a sequence, sorted by increasing timestamp.  Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two neighboring elements.  Finding the two neighboring elements can be done in $O(\lg n)$ time.

You'll also need to be able to append to the end of the sequence and delete from the beginning.  Thus, basically you need a queue.

There are standard constructions for a queue.  For instance, you can store them in an array, with amortized $O(1)$-time insert and delete operations.  Basically, you have an array for the elements of the sequence, and a start index (for the beginning of the sequence) and an end index (for the end of the sequence).  To delete from the beginning, increment the start index.  To add to the end, increment the end index; if this runs past the end of the existing array, allocate a new array of double the size and copy into the new array.

Alternatively: you can store the elements in a balanced binary tree.  This will achieve worst-case $O(\lg n)$-time for all operations.


If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa

You say:

This is only possible if $A \le_m B$ exists and $B=\overline{B}$

But that condition simplifies to "false" since it can never the case that  $B=\overline{B}$.
Anyway the answer to both cases is "yes".
If $A \le_T B$ then there is a Turing machine $T$ with oracle $B$ that decides $A$.
By complementing $T$'s output we obtain a Turing machine with oracle $B$ that decides $\overline{A}$  showing that $\overline{A} \le_T B$.
Moreover, consider a Turing machine $T'$ with oracle $\overline{B}$ that simulates $T$ except for the following: whenever $T$ invokes its oracle for $B$ on some input $w$, $T'$ invokes its oracle for $\overline{B}$ on $w$ and then complements the result. Clearly $T'$ still decides $A$, thus showing that $A \le_T \overline{B}$.


Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers?

A set $S$ is enumerable (or, countable) if we can enumerate it:
$$
S = \{s_1,s_2,s_3,\ldots\}
$$
In other words, there is a mapping from $\mathbb{N}$ onto $S$.
Cantor showed that $\mathbb{R}$ isn't enumerable.
We can consider more relaxed notions of enumeration. For example, a set $S$ is well-orderable if there is a linear order $<$ on $S$ such that any non-empty subset of $S$ has a minimum. This encompasses your examples, and much more.
The axiom of choice is equivalent to the well-ordering principle, which states that every set can be well-ordered. Hence if you assume the axiom of choice, every set can be enumerated in this sense.


Connection between vertex cover and P=NP

I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time.
We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, we can scale the graph such that $(f(G,v) + 5) / f(G, v)) \leq 1.36$, which results in $f(G, v) \geq 14$.

Furthermore, vertex cover is fixed parameter tractable in the solution size. In other words, we can compute whether $G$ admits a vertex cover of a fixed size in polynomial time. Hence, we apply the fixed parameter tractable algorithm up to $k = 13$. If no solution has been found, use $g$. We now have a polynomial time algorithm that can solve any set cover instance within a factor below 1.36 times the optimal solution, which is a contradiction unless P = NP.

Corollary: it is impossible to have a computable algorithm that outputs a vertex cover of size at most $OPT + c$, where $c \geq 0$ is a constant, in polynomial time, unless P = NP.


Is it feasible to generate every possible RGB image?

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly.  For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system.  (There's something wrong with your reasoning if you've concluded it's reasonably possible to enumerate all such images.)


The definition you quote is rather meaningless. More accurately, a sequence of arrays, one of each length $n$, is partially sorted if for some constant $c$, the number of inversions of the array of length $n$ is at most $cn$. (More succinctly, a sequence of arrays is partially sorted if the number of inversions is $O(n)$.) The running time of insertion sort on such a sequence of arrays is $O(n)$, that is, linear.

It doesn't make much sense to say that a single array is partially sorted, since we can always choose $c$ to make the definition hold. If we want to talk about a single array then we need to fix $c$ in advance. Note that $c$ doesn't have to be at most $1$.


Algorithm to pack any small boxes into a big box

Your problem is called 3D Bin Packing and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem.


If I understand your question correctly, you're asking whether you can construct a reduction where the truth assignment changes the construction.

In short, no. The whole point of a reduction from problem $A$ to problem $B$ is to show that we can solve $A$ using an algorithm for $B$ - if we already know the solution to $A$, then we could trivially reduce it to virtually any other problem.

In your particular case, if you already know the truth assignment to the variables, then you've already answered whether the input formula to the 3-SAT instance is satisfiable or not, what you want is a reduction that takes the formula, turns it into an instance of your graph problem, where solving the graph problem would tell you what to set the variables in the 3-SAT instance to.


Time complexity of sum of $2^n$ values of polynomials

It takes $O(n^2)$ time.  A polynomial can be represented as the list of its coefficients.  Since it has degree $n$, it can be represented by a list of $n+1$ numbers.  Now adding polynomials can be done by adding their corresponding coefficients.  There are $n+1$ coefficients of $f(n)$, and each takes $O(n)$ time to compute (you have to add up $n$ numbers), for a total of $O(n \times (n+1)) = O(n^2)$.

There's no possibility to do anything faster, as the input contains $n(n+1)$ numbers, and any correct solution will have to read all the input.  It takes $\Theta(n^2)$ time even to read the input, let alone to do any processing, so any correct algorithm will have to take time at least $\Theta(n^2)$.

With this, you should now be able to do a similar analysis for the variant you list near the end of your question.


How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

The powerful technique you are searching for is variable substitution.

Let $S(m)=T(2^m)$. Then
$$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$
where $g(m)=f(2^m)$.

Now that we have a recurrence relation about $S(m)$, to which we might be able to apply the master's theorem. Here are some examples.

If $f(n)$ is a constant, so is $g(m)$.  If $a=1$ and $b=\frac12$, then we know that $S(m)=O(\log m)$. Hence,
$$T(n)=S(\log n)=O(\log \log n).$$
If $f(n)=\log n$, $a=1$ and $b=\frac23$, then $S(m)=S(2m/3)+m$. So $S(m)=O(m)$. Hence,
$$T(n)=S(\log n)=O(\log n).$$
If $f(n)=\log\log n$, $a=1$ and $b=\frac12$, then $S(m)=S(m/2)+\log m$. So $S(m)=O((\log m)^2)$. Hence,
$$T(n)=S(\log n)= O((\log\log n)^2).$$

Note that the above reasoning is rather loose as $\log n$ and $\sqrt n$ might not be an integer when $n$ is. A lot of careful sandwiching together with some kind of continuity or monotonicity is needed to establish the result rigorously.


QuickSelect with Median of Medians runtime

The medians of medians algorithm will return a pivot with a rank between $\frac{3}{10}n$ and $\frac{7}{10}n$ in time $O(n)$.

You can then describe the worst-case computational complexity of Quickselect on an instance of $n$ elements with the following recurrence relation:
$$
T(n) = T\left(\frac{7}{10}n\right) + O(n),
$$
where $O(n)$ accounts both for the work needed to run the median-of-medians algorithm an for the partitioning of the input.

Unrolling the recursion shows that (you can prove this formally by induction):
$$
T(n) \le c n \sum_{i=0}^{+\infty} \left( \frac{7}{10} \right)^i = cn \cdot  \frac{1}{1-\frac{7}{10}} = \frac{10cn}{3} = O(n),$$

where $c>0$ is a suitable constant (hidden in the $O(n)$ notation of the recurrence relation).


How do you prove that two languages are equivalent?

There's an algorithm for this. Construct a DFA from you NFA, construct the reverse DFA, and check whether the two DFAs accept the same language (for example, you could construct the DFA for the symmetric difference and see if it accepts anything). If you want a more serious answer, you'll need to tell us more about your $L$.


Dominating set of given size $k$ in $O(2^k |V| |E|)$

It is well-known (for a very specific group of people) that dominating set is W[2]-complete (for undirected graphs).

You are asking for a fixed-parameter tractable algorithm for solving dominating set in general graphs.  The class of algorithms admitting such running times comprises the class called FPT.

Unfortunately, most people in the aforementioned group believe that FPT is a strict subset of W[1] which again is a strict subset of W[2].

To summarize, we don't think that Dominating Set has an FPT algorithm.

Under the assumption that $\text{FPT} \neq \text{W[2]}$, there is no $O(f(k) \cdot \text{poly}(|V|, |E|)$ algorithm for any function $f$ and any polynomial function $\text{poly}$.

For the Vertex Cover problem, there is such an algorithm, that is, Vertex Cover is in FPT.  Clique and Independent Set are W[1]-complete, whereas Chromatic Number is in XP, which means that it is above the entire W-hierarchy.

Why guarantees of yes-instances won't help

Let $A$ be an algorithm that in running time $f(x)$ (where $x$ is the size of the input) returns a solution of size at most $k$. Algorithm $A$ only works on "yes"-instances.  Create an algorithm $A′$ that takes any input, runs $A$ for $f(x)$ steps, and if $A$ hasn't terminated, returns "no".  If $A$ returns, $A′$ verifies the solution (in polynomial time) and outputs either "yes" or "no" according to $A$s output.

The algorithm $A$ is an algorithm, so it's not likely to get mad at you for trying to cheat; it has to do something for any input, possibly crash and go up in smoke, but there is a nice dichotomy we can use to cheat:

If $A$ gives you any output, we can verify that the output is a correct solution in polynomial time
If $A$ fails to give you any (correct) output in its specified running time, the input has to be a no instance.

Hence, if an algorithm works on guaranteed yes-instances, we can create an algorithm that works on any instance.


Create binary numbers with a described pattern

Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

For size 2, $E = 1$, and the one string is given by $0^1 1^1 = 01$.

For size 4, $E = 2$, and the two strings are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

For size 8, $E = 3$, and the three strings are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

For size $n = 2^E$, the $E$ strings include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ strings can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Thus, the examples are:

Size 2: $E = 1$. The one string is $(0^1 1^1)^1 = (0^{2^0}1^{2^0})^{2^0}$

Size 4: $E = 2$. The two strings are $0101 = (0^1 1^1)^2 = (0^{2^0} 1^{2^0})^{2^1}$ and $0011 = (0^2 1^2)^1 = (0^{2^1} = 1^{2^1})^{2^0}$.

Size 8: $E = 3$. The three strings are $01010101 = (0^{2^0} 1^{2^0})^{2^2}$ with $k = 0$, $00110011 = (0^{2^1} 1^{2^1})^{2^1}$ with $k = 1$, $00001111 = (0^{2^2} 1^{2^2})^{2^0}$ with $k = 2$.

This is an iterative algorithm. You list each string, of length $n$ a total of $\log n$ times. It is $O(n \log n)$ to list all the strings explicity. It is $O(\log n)$ to express them regex style like $(0^x 1^x)^y$ [note $x, y$ are powers of 2, and the exponents in the power form of $x, y$ add up to $E-1$].


Is this a reduction from decision problem to non-decision problem?

It seems that the author uses the notation $A\le_p B$, where $A,B$ can be either function or decision problems, for saying that given an oracle for $B$, one can solve $A$ in polynomial time.

It is then shown that the isomorphism problem is reducible to finding the generators of a setwise stabilizer group (STAB) by showing that it is reducible to finding the generators of the automorphism group (AUT), and that $AUT\le_p STAB$. The latter is shown by viewing vertex permutations as an operation over vertex pairs, and seeking the generators of the corresponding stabilizing group relative to $E$.


Longest path in directed graph cyclic graph where each node has one children

As rus9384 & you seemed to have figured out in the comments, there exists an $O(N)$ solution to the problem.

First, apply the well known algorithm to find Strongly Connected Components in the graph in $O(N)$. Then, after collapsing all such components into single nodes, you can slightly modify the algorithm to find the Longest Path in a DAG to get your answer in $O(N)$ time.


Given a tree, find a vertex which maximizes the minimum distance to any leaf

To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.

Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.
Repeat the following until the queue is empty:

Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.
If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.

The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf.

Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.


Why can't DFS be used to find shortest paths in unweighted graphs?

The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored.

The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current node (from small to large). It is easy to construct a counterexample for this rule:

[source]

Now, that is no proof that there does not exist a strategy of choosing the next child to be investigated which will make DFS find shortest paths.

However, no matter the rule¹ you can construct graphs that have DFS commit to a long detour at the very first node, just as I did for the greedy rule. Assign edges $(s,t)$ and $(s,a)$ weights such that the rule chooses to visit $a$ first, and assign $(a,b)$ a weight greater than the one of $(s,t)$. Therefore, it is plausible that DFS can never find shortest paths (in general graphs).

Note that since you can express every (positive-integer-)weighted graph as unweighted graph -- simply replace edges with cost $c$ with a chain with $c-1$ nodes -- the same examples deal with DFS on unweighted graphs. Here, the situation is actually even more bleak: without weights, what can DFS use to determine the next child to visit?

As long as the rule is deterministic. If it is not, it can clearly not always find shortest paths.


Flipping all incoming/outgoing edges from a vertex in a DAG

This doesn't hold if we flip both outgoing and incoming edges as shown by @Yuval Filmus.

Here is my try of a proof by contradiction for only flipping outgoing of incoming edges (sorry if it's too informal):

After flipping all incoming(outgoing) edges from vertex v in a DAG G, we get another graph that is not a DAG (it has a cycle).
Since we only changed the direction of the vertices incident to v, the only way we loose the acyclic property is if there is a new cycle going through vertex v.
Since we flipped directions of all incoming(outgoing) edges from vertex v, all edges incident to vertex v are now outgoing(incoming), so it is not possible for any cycle to go through vertex v, which contradicts 2.


A tensor product of operations, $I\otimes J$ say, acts on each subsystem separately: if $\phi$ and $\psi$ are states and $I$ and $J$ are operators then
$$(I\otimes J)(\phi\otimes \psi) = (I\phi) \otimes (J\psi)$$
In bra-ket notation the state $\phi\otimes \psi$ can be denoted $|\phi\rangle|\psi\rangle$.
In your first equation, the $\langle i|0\rangle\langle 0|k\rangle$ factor and $\langle j|I|l\rangle$ factor just separate in this way.

The algebra behind the second equation is basically:
$$(1+x^{2^0})\dots(1+x^{2^{t-1}})=1+x+x^2+x^2+\dots+x^{2^t-1}$$
except that the "1" is replaced by $| 0\rangle$, and the $x$ is replaced by $\exp(2\pi i \phi |1\rangle)$ (clash of my notation: $\phi$ is now a number). The only difference is that the multiplication is really a tensor product, and with bosons $|1\rangle\otimes |1\rangle=|2\rangle$.


Minimize range of distances between two sets of points

Here is a simple algorithm to get you started.
Compute all $\binom{n}{2}$ pairwise distances, and put them in an array $A$. For each pair $a<b$ in $A$, use a bipartite matching algorithm to determine whether there is a matching that uses only distances in the range $[a,b]$. Choose the pair minimizing $b-a$. In total, there are $O(n^4)$ invocations of the matching algorithm.
It is easy to improve upon this. For example, for each $a$ we can find the best $b$ using binary search (this is essentially bottleneck matching), dropping the number of invocations down to $O(n^2\log n)$. You can improve this further (in practice) as follows:

Let $a$ be the minimal element in $A$.
Find the minimal $b$ such that an $[a,b]$-matching exists.
Decrement $b$, and find the maximal $a$ such that an $[a,b]$-matching exists.
Increment $a$, and find the minimal $b$ such that an $[a,b]$-matching exists.
And so on, until no more matchings are possible.

Here an $[a,b]$-matching is one only using weights in $[a,b]$, and "increment/decrement" are relative to $A$.
You can probably improve this even further, even in this oblivious setting where we do not use the fact that the distances originate from a planar embedding of the points.


Stable marriage problem preferential to asking side

One place to look at is the classic book The stable marriage problem. The link provides a relevant excerpt, showing that the matching produced by the standard Gale–Shapley algorithm is male optimal and female pessimal: any man gets the best possible partner (in his view) he can get in any perfect matching, and any woman gets the worst possible partner (in her view) she can get in any perfect matching. If we switch men and women, we will obtain the female optimal, male pessimal matching.

The quoted book, as well as Knuth's book on the subject, contain other material on stable marriages, including the number of different stable marriages, the lattice structure of stable marriages, sampling a random stable marriage, related problems such as the stable roommate problem, and much more.

From another angle, a distinctly different algorithm for the stable marriage problem has been developed by Subramanian and picked up by Feder; see for example Section 6 of this paper.


Intersection of two shortest paths in connected weighted graph

My idea is to find a shortest path from $u$ to $v$ ...

As noted by Pål GD, it is not enough to find just one shortest path from $u$ to $v$ as a different shortest path might contain the wanted intersection vertex. We have to take into consideration all shortest paths from $u$ to $v$. Since we are only interested in the vertices, it is enough to  find all vertices that are on some shortest path from $u$ to $v$. Denote that set of vertices as $S(u,v)$, where $S$ is the shorthand for both "shortest" and "set".

Characterization of $S(u,v)$: Let $d(x,y)$ be the distance between vertex $x$ and $y$. $$x\in S(u,v) \Longleftrightarrow d(u,x)+d(x,v)=d(u,v).$$

It is immediate to prove both "if" and "only if" part.

Here is an wanted algorithm.

Run Dijkstra's algorithm with $u$ as source and with a priority queue such as described at this wikipedia entry to obtain function $d_u$ such that $d_u(x)=d(u,x)$ for all $x\in V$ in the form of a look-up table. Similarly, obtain function $d_v(x)$ such that $d_v(x)=d(x,v)$ for all $x\in V$ by running Dijkstra's algorithm on $G$ with all edges reversed and $v$ as source. Similarly, obtain $d_s(x)$ and $d_t(x)$. For each vertex $x$ in $V$, check whether $d_u(x)+d_v(x)=d_u(v)$ and $d_s(x)+d_t(x)=d_s(t)$. If we find one such vertex, the answer is yes; otherwise, the answer is no.

Here are several related exercises.

Exercise 1. Prove the correctness of the characterization of $S(u,v)$ as well as the correctness of the algorithm.

Exercise 2. Show that the above algorithm runs in $O(|E|\log |V|)$ time when the priority queue of Dijkstra's algorithm is implemented as a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap.

Exercise 3. For each vertex $u$, let the shortest-path-index $d(u)$ be the number of ordered vertex pairs $(v_1,v_2)$ such that $u$ belongs to one of the shortest paths from $v_1$ to $v_2$. Let a path-center of $G$ be any vertex whose shortest-path-index is the maximum. Find an efficient algorithm that returns all path-centers.


Context free languages invariant by "shuffling" right hand side

Your theorem doesn't hold.
Consider the grammar
$$
\begin{align}
&S \to 1T \mid T1 \\
&T \to 23 \mid 32 \\
\end{align}
$$
Shuffling the grammar results in the same language.
Now consider instead the grammar
$$
S \to 123 \mid 132 \mid 231 \mid 321
$$
which generates the same language.
Shuffling this grammar results in a larger language.


What does $\Sigma^0_2$-hard and $\Pi^0_2$-hard for a TM's Acceptance Problem mean?

No, it's unrelated to NP-hardness.  $\Sigma_n^0$ and $\Pi_n^0$ are the levels of the arithmetical hierarchy.  $\Sigma_2^0$ is the class of problems that can be decide by Turing machines that have an oracle for the halting problem and $\Pi_2^0$ is the class of problems whose complement is in $\Sigma_2^0$.

There is the corresponding notion of the polynomial hierarchy, in which $\Sigma_1^\mathrm{P}$ is NP and $\Pi_1^\mathrm{P}$ is co-NP.


Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

marks the set of numbers P={P1,P2,P3,..,Pn}

need to find number X:

|P1-X|+|P2-X|+...+|Pn-X|=D, which minimizes D.

the fact that X is the median can be shown using induction on the number of numbers n in P.

Base: n=1: trivial to see that the median is P1 and |P1-P1|=D=0 is minimal (D>=0).

now suppose that this holds for all P of size |P|=n, we need to show that this holds for |P|=n+1.

In other words:

given that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm is the median of P={P1,..,Pn} show that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm' is the median of P={P1,..P(n+1)).
notice that there are two cases m'=m+1 (n is even) or m'=m (n is odd).

I suggest drawing a simple example using n=3 and n+1=4 on an axis. Can you see why this must hold?


Heap-like notation of a BST (BFT bit-vectors) for succinct representation

You can count it like this:

Let $n$ be the original number of nodes

Each original node has 2 children after adding the external nodes.

So 1 bit for the original node and 2 for its children. Total $3n$ bits.

But we are over counting here because original node is child of one other original node. So we subtract $n$ and get $2n$.

But we over corrected the count because root node has no parent so we add back 1 bit.

$2n + 1$.


To show that a graph-problem is in $L$ or $NL$

The problem is NL-complete.

The fact that it's in NL, as stated in the comments, follows from the fact that this problem is a restriction of the reachability problem for directed graphs.

To see that it's NL-hard, we can reduce from the reachability problem:

Consider a graph $G=(V,E)$ and vertices $s,t$. We transform $G$ to a graph $G'$ with out degree at most $2$, as follows.

For every vertex $v$ with out-neighbors $u_1,...,u_k$ ($k\ge 3$), construct vertices $v_1,...,v_{k-1}$ where there are edges from $v_i$ to $u_i$ and to $v_{i+1}$. The incoming edges to $v$ are now directed to $v_1$, and $v$ is removed.

It is not hard to see that there is a path from $s$ to $t$ in $G$ iff there is a path from $s_1$ to $t_1$ in $G'$. Also, this reduction can be implemented in log-space. Thus, your problem is NL-complete.


Prove a language $A_{PTM}$ is not BPP-Complete

To show that a language is not BPP-complete, it suffices to do one of the following:

Show that the language is not in BPP.
Show that the language is not BPP-hard.

Your language seems to be undecidable, and so in particular, not in BPP.


Is SAT is in NL?( under certain conditions)

The certificate could have linear size, and you need to remember it for the entire verification process. That is, you need to store in on the work tape and reference it as you read the clauses. You can't guess a satisfying assignment for each clause separately - under this model, every 3CNF is satisfiable. The oracle tape is consumed by each read - you can't go back and reread a previous symbol, which might be what's confusing you.


The theory probably depends on the details. In practice, if you're only interested in solving an instance, here are a some thoughts:

Most literals should be eliminated in presolve of today's solvers. They eliminate all positive-only (or negative-only) literals.
Next, your setup implies that most literals should be set to $true$. Many solvers allow you to specify which assignment should be tried first ("initial phase"). By setting this to $true$, you should get fast solves.
The potentially exponential blowup from resolution might be avoided, if there are very few negated literals. Thus, BVE and DP-based solvers could be quite effective on such formulas.
Local search solvers (WalkSAT & Co) should also do very well.

Have you tried feeding your problem to Kissat or CaDiCaL?


The definition of a priority queue is that elements will be dequeued in order of priority. The definition says nothing about the order of items of equal priority so an implementer can do anything, within reason, and still be justified in calling the resulting structure a priority queue.


How to prove the following properties of Small-step semantics?

I suggest to proceed by induction on $k$. For the inductive basis and step you'll have to look at all the possible cases that the relevant reduction step $\langle C, s \rangle$ can be derived.


Matrix chain multiplication: Greedy approach

Consider the product $ABC$, where

$A$ is $5\times 2$
$B$ is $2\times 3$
$C$ is $3\times 100$

Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products.

The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products.

Suppose that $A$ is $a\times b$, that $B$ is $b \times c$, and that $C$ is $c\times d$. There are two possibilities:

Compute $AB$ and then $(AB)C$: cost is $abc + acd = ac(b+d)$.
Compute $BC$ and then $A(BC)$: cost is $bcd + abd = bd(a+c)$.

The first option is preferable if
$$
\frac{b+d}{bd} < \frac{a+c}{ac}
$$
or equivalently
$$
\frac{1}{b} + \frac{1}{d} < \frac{1}{a} + \frac{1}{c}.
$$
For example, above we have $a = 5$, $b = 2$, $c = 3$, $d = 100$. Since
$$
\frac{1}{2} + \frac{1}{100} < \frac{1}{5} + \frac{1}{3},
$$
the order $(AB)C$ is preferable.

Your decision procedure would prefer this order if $c < b$, that is, if
$$
\frac{1}{b} < \frac{1}{c}.
$$
Your condition misses the contribution of $a,d$.


calculating the string similarity of an optimal alignment

I think you should be able to adapt the standard dynamic programming algorithm to this, with a minor modification: you simply treat deletions at the beginning and end of s2 as costing 0.


Algorithm to estimate the probability that a "0 and 1 matrix" fills up following the bootstrap percolation rules

Here is a reasonably fast approach to estimate $p_c$. We will perform $N$ different trials, count the number of successes $M$, and estimate the result as $M/N \pm 1/\sqrt{N}$ (better estimates are possible if $p_c$ is close to 0 or to 1).

For each trial, you initialize an $N \times N$ matrix with the initial filling. You then go over the array, calculating the number of active neighbors of each non-filled point in the matrix, and whenever that number reaches 2, you put it in a stack. You then repeatedly pop elements from the stack, updating the matrix of active neighbors, and whenever that number reaches 2 for some non-filled point, you add it to the stack. When the stack is empty, the process is complete, and you can check whether all points have been activated.

There are many optimizations possible: for example, you can use an $(N+2)\times(N+2)$ matrix to help deal with border cases, you can keep track of the number of active points, and so on.

Using this naive approach, I managed to perform $10^6$ trials for $n = 100$, $p = 0.0535$ in about two minutes on my PC. The answer was $M/N \approx 0.5008$, so the critical probability is pretty close to $0.0535$.


Upper bound for the union of $n$ DFAs of size at most $m$?

Yes.  There is a simple proof.

You say that $L_i$ are recognized by DFAs of size $\le m$, and that there are at most $f(m)$ possible such DFAs.  Therefore, there are at most $f(m)$ possible such languages.  If $n \ge f(m)$, then $L_1,\dots,L_n$ must contain some repetitions (some language appears multiple times).  Remove all repeated instances, so the $L_i$ are unique.  Then at that point we have $n \le f(m)$.  In other words, without loss of generality we can assume $n \le f(m)$.

Now the union of $n$ such languages can be recognized by a DFA of size at most $m^n$ (by a product construction), and $n \le f(m)$, so the union of $n$ such languages can be recognized by a DFA of size at most $m^{f(m)}$.


How to know if a code is Huffman or not without having the probability of each codeword?

If you have a Huffman code, and the codes have lengths $l_i$, then the sum over $2^{-l_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 < 1, therefore not a Huffman code. You can replace the code 110 with 11.

(I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the sum is less than 1, then there is some bit that you can remove from some code with the code remaining a prefix code, and since there is a finite number of bits to remove, the sum must become 1 eventually).


Trying to figure out the best way to approach this problem with Computer Vision

I am skeptical whether computer vision is going to be the most effective approach, but you can certainly do it.  There is lots of work on image similarity metrics using neural networks (Siamese networks, triplet loss, etc.) and you could certainly implement any of those architectures, acquire a few thousand labels, and train on it.  I would suggest pre-training on some standard similarity dataset (e.g., start with LPIPS) and then fine-tune on your data.  But be prepared that this might or might not be effective.
It might be more effective to extract features and then build a ML model that works with those features rather than with the raw images.  For instance, OCR both images and compare them; compute L1 and L2 distance; etc.


Why "reduce to", not the other way around?

There are several different types of reduction, but generally, if we say we reduce problem A to problem B, it means something like:  if we had a way to solve B, we could use that to solve A.  Some reductions may allow to use B as a black box.  Others might require that "yes" instances of A map to "yes" instances of B, and that "no" instances map as well.  Or, it may be something simpler, like "hey, I already have a great solution to problem B, and now with just a simple transform, I can use it to solve problem A."
In all forms, it implies something related to "we could solve A if we had solutions to B".

What that means has something to do with what is known.  If B is an easy problem to solve, then A reducing to B tells us that solving A is no harder than solving B, plus doing the reduction from A to B.  In that case, an easy reduction, to an easy problem, proves that A is easy.

On the other hand, especially in the context of hardness results, we would usually reduce a known difficult problem (A here) to B, and that would show that, because A is hard, but transforming an instance of A into B is easy, B must also be hard, because if B were easy, it would give a solution to the known A problem.

So basically, for an easy reduction from A to B, it proves 2 things:  A is not harder than B, and B is not easier than A.  Yes, those are the same thing, but usually, you only care about one of them, depending on whether you know A to be difficult, or B to be easy.


The key to memorizing the master theorem is to simplify it. There's an approximation to reality that is correct in 99% of the cases. A good (but not technically correct) summary of the Master Theorem is as follows:

If $T(n)=aT(n/b) + f(n)$ then compare $n^{log_b a}$ with $f(n)$

If $f(n) < n^{log_b a}$, then $T(n)=n^{log_b a}$

If they are equal, then $T(n)=f(n)\log n$

If $f(n) > n^{log_b a}$, then $T(n)=f(n)$

Basically, you compare $n^{log_b a}$ with $f(n)$ and the larger of the two is your running time; however if they are equal (for some strange definition of equal) then you get an extra $log$-factor in the running time. This sentence is all you really need to know.
Caveats
The most important one is in the meaning of "equal". For the purpose of the master theorem $f(n)$ is equal to $n^{log_b a}$ if the difference between them is less than polynomial. So, for instance, if $f(n)=n^{log_b a}\log n$ or $f(n)=n^{log_b a}\log^3 n \log \log n$ this would still count as "equal". The difference needs to be at least a factor $n^\epsilon$ for some $\epsilon>0$.
Another caveat is that for the third case ($f(n)$ exceeds $n^{log_b a}$ you also need a condition that $f(n)$ does not grow "too quickly". This is rather pathological and not likely to be an issue in practice, but something you should be aware of. The formal condition is that $af(n/b)$ should be less than $f(n)$ (for sufficiently large $n$, and where "less" is interpreted as "there is a $k<1$ such that $af(n/b)\leq kf(n)$).


Difference between pattern matching and pattern searching in terms of DFA/Regex

This is true in general, in a way.
Consider a regex $r$. You can construct a DFA (or NFA) for the matching problem. Denote this NFA by $A$.

To solve the searching problem, you can proceed in several ways.
First, you can just solve the matching problem for the regex $\Sigma^*\cdot r\cdot \Sigma^*$.

Alternatively, you can construct an equivalent NFA for the latter regex. The form of such an NFA would be an initial state that guesses when $r$ starts (at which point there is a transition to the initial states of $A$), and every accepting state of $A$ moves to an accepting sink.

This NFA can be thought of as a generalization of the situation you describe. Indeed, when you determinize it, the equivalent DFA essentially tracks $r$, and whenever it fails the DFA "resets". This is not exact, since it strongly depends on $r$.

When $A$ is a chain, then indeed determinizing the NFA yields a DFA that follows the chain, and whenever there is a "mistake" (that is, $r$ is not met), it resets to the initial state. However, it could be that resetting might not go as far as the initial state. For example, when searching for $aba$, if you see $aa$, then the second $a$ should not reset all the way back, but rather to the second state, since the second $a$ may be the start of the regex's occurrence.


Using hash tables instead of lists for buckets in hash tables

Using a hash table with $n$ buckets and a hash function $h_n : S \rightarrow \{0, 1, ..., n - 1\}$ , where each bucket is a hash table with $m$ buckets and a hash function $h_m : S \rightarrow \{0, 1, ..., m - 1\}$, is equivalent to a hash table wit $nm$ buckets and a hash function $h_{nm} : S \rightarrow \{0, 1, 2, ..., nm - 1\}$ where $h_{nm}(x) = mh_n(x) + h_m(x)$. In other words, using more than one level has no effect whatsoever on the complexity: it's the same as a for a garden-variety hash table.

Perfect hashing is a completely separate issue.


What are very short programs with unknown halting status?

Yes.  This page says there are 98 5-state Turing machines whose halting statuses are unknown.  Annoyingly, it does not give any examples of such machines, but this 26-year-old page gives 2 5-state Turing machines whose halting statuses were apparently unknown at that time.  (Searching for "simple counter" will take you right between those 2.)  I copied them here in case that link goes down:

Input Bit   Transition on State     Steps            Comment
             A   B   C   D   E

    0       B1L C1R D0R A1L H1L   > 2*(10^9)       ``chaotic''
    1       B1R E0L A0L D0R C0L

    0       B1L A0R C0R E1L B0L       ?        complex ``counter''
    1       A1R C0L D1L A0R H1L


Use of Activation Units in Facial Expression Understanding

As a preliminary answer, I can't imagine the extraction of AUs affecting their ability to detect emotions, since according to Do Deep Neural Networks Learn Facial Action Units When Doing Expression Recognition?, CNNs trained to extract emotions already correspond to AUs (called FAUs in the paper), as shown in the table below taken from their paper:

Additionally, this is a very basic CNN with only three convolutional layers and grayscaled inputs. Given a larger CNN using Inception-layers and residual connections, more specialisation would probably be seen.

However, this conclusion also makes me feel like I'm dismissing a whole area of research, so it's probably a little hasty.


Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.


What is the difference between an algorithm, a language and a problem?

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word.

Language: a language is simply a set of strings. If you have an alphabet, such as
$\Sigma$, then $\Sigma^*$ is the set of all words containing only the symbols in $\Sigma$.
For example, $\{0,1 \}^*$ is the set of all binary sequences of any length.
An alphabet doesn't need to be binary, though. It can be unary, ternary, etc.

A language over an alphabet $\Sigma$ is any subset of $\Sigma^*$.

Problem: A problem is some question about some input we'd like answered. Specifically, a decision problem is a question which asks, "Does our given input fulfill property $X$?

A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language.
For a problem $X$, the corresponding language is:

  $L = \{w \mid w$ is the encoding of an input $y$ to problem $X$,
  and the answer to input $y$ for problem $X$ is "Yes"  $ \}$

Determining if the answer for an input to a decision problem is "yes" is equivalent to determining whether an encoding of that input over an alphabet is in the corresponding language.

Algorithm: An algorithm is a step-by-step way to solve a problem. Note that there an algorithm can be expressed in many ways and many languages, and that there are many different algorithms solving any given problem.

Turing Machine: A Turing Machine is the formal analogue of an algorithm. A Turing Machine over a given alphabet, for each word, either will or won't halt in an accepting state. Thus for each Turing Machine $M$, there is a corresponding language:

  $L(M) = \{w \mid M$ halts in an accepting state on input $w\}$.

(There's a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes $\mathsf{R}$ and $\mathsf{RE}$.)

The relationship between languages and Turing Machines is as follows

Every Turing Machine accepts exactly one language
There may be more than one Turing Machine that accept a given language
There may be no Turing Machine that accepts a given language.

We can say roughly the same thing about algorithms and problems: every algorithm solves a single problem, but there may be 0, or many, algorithms solving a given problem.

Time Complexity: One of the most common sources of confusion between algorithms and problems is in regards to complexity classes. The correct allocation can be summarized as follows:

An algorithm has a time complexity
A problem belongs to a complexity class

An algorithm can have a certain time complexity. We say an algorithm has a worst-case upper-bounded complexity
$f(n)$ if the algorithm halts in at most $f(n)$ steps for any input of size $n$.

Problems don't have run-times, since a problem isn't tied to a specific algorithm which actually runs. Instead, we say that a problem belongs to a complexity class, if there exists some algorithm solving that problem with a given time complexity.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $\mathsf{P}$, but if there's a polynomial-time algorithm solving a given problem $X$, then $X$ is in $\mathsf{P}$. There could also be a bunch of exponential-time algorithms accepting $X$, but since there exists a single polynomial-time algorithm accepting $X$, it is in $\mathsf{P}$.


Binary search algorithm - worst-case complexity

That's a way to do it. Sometimes it's easier to go the other way round: What is the size of the largest array where binary search will locate an item or determine it's not there, using k comparisons? And it turns out that the largest array has size $2^k - 1$. And then you reverse this.

Understanding the master method is very useful if you have to pass a test that tests whether you understand the master method. But be prepared to have more practical problem where the only method that works is the "turn on your brain" method. A simple example is the Greatest Common Divisor algorithm.


Guessing the structure of a finger tree from the number of elements

From first principles, every 2-3 tree is a finger tree viewed from another angle, so you could solve the problem by solving the somewhat easier problem of "What shape are the valid 2-3 trees of size $n$?"

You can also look at many existing finger-tree libraries. The first one created, was, of course, the Haskell one. The function you are looking for is replicate, which takes a value $v$ and size $n$, then creates a finger tree of size $n$ containing $n$ copies of $v$. The real work of replicate is done in applicativeTree, which has individual cases for $n \leq 8$ and recurses for larger $n$.


Proving Postorder Traversal's Time Complexity

In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.

In postorder traversal each node in binary tree is visited:

a) 1 time if it is a leaf node.

b) 1 time if it is a node with only one child (either left or right)

c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.

So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:

Best case time : $O(n)$

Worst case time : $O(n)$

Hence, we can say algorithm is $Θ(n)$.


Representing FP relations using witnesses

An $A$-polynomial relation can't have two many pairs agreeing on the first coordinate. Namely for any $x$ there can be at most $2^{p(x)}$ $y$'s such that $(x,y)\in R$. This shows that the simple relation $R=\{0,1\}^*\times\{0,1\}^*$ is in FP but not A-polynomial.


No.  Ford-Fulkerson cannot be used to solve arbitrary linear programming instances.  It can only solve instances that are in the form of "max flow in this flow graph".  The dual doesn't have that form.
The dual is to find the minimum cut.  A standard way to find the minimum cut is by finding the max flow, and then using the max-flow min-cut theorem.


For bit #k to be set in the output, you need to arrange the numbers so that bit #k is either set in a[i] and cleared in c[i] or the other way round. Therefore bit #k must be set in exactly n of your 2n inputs. If that is not the case then bit #k cannot be set in the output. So first you determine all k such that bit #k is set in exactly n of the 2n inputs, and ignore all other ks.
Let k be the highest of these bit positions. Split the elements of b into those where bit #k is set and those where it is cleared, and pick c[i] from the correct one of these sets. That's always possible.
Let j be the second highest of these bit positions. Split the elements of b into four sets, where bit #k and #j are both set, bit #k is set and bit #j is cleared, etc. Depending on which bits in a[i] are set, you know from which subset of b you need to pick c[i]. This only works if the sets have the right sizes! If it doesn't work, ignore bit j and take the next highest bit. If it works you can set bit #k and #j in the result and proceed with the next higher bit.


Partial recursive function with no total recursive extension

Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function is clearly partially computable, but it has no computable extension, since you could use any such extension to solve the halting problem (why?).

Exercise for the reader: convert this construction to a Boolean function.


Clustering data for compression with PCA

(Not really an answer, more like a suggestion)
Since it's almost surely NP-hard, we need some heuristics. The idea is, for each point, to build the cluster it's contained in:
def clustering(P):  # P is the set of points
    for each p in P:
        build a somewhat-optimal cluster C containing p
        remove C from P

Now, for each point we will build a cluster, one dimension at a time. We will build vectors $(v_1, \ldots, v_k)$, until the objective doesn't improve:
def build_cluster(p, P, t):  # t is a projection distance threshold
    S = ()  # current span
    for k = 1, 2, ...:  # cluster dimension
        sample m vectors v_1, ..., v_m
        for each v_i:
            compute the number of points in P within a distance t to p + span(S, v_i)
        select the best such v_i
        if adding v_i to S is not beneficial:
            break
        S = union(S, v_i)

Now, there is a lot of engineering which can be done, except for defining stop conditions. E.g. we can sample vectors, and then iteratively improve them (minimizing the loss, I.e. the distance to the span from vertices within distance t) (and we can also decrease t in the process of improvement).
Also, maybe we should do something better than sampling random vectors since we are unlikely to hit the right one. We may try to compute some candidates based on our data.
Hope it helps.


Yes, you can use a CNN.  CNN's are not limited to just images.  Use a 1D convolution, not a 2D convolution; you have 1D data, so a 1D convolution is more appropriate.  A CNN is a reasonable thing to try, but the only way to find out if it actually works or not is to try it on some real data and evaluate its effectiveness.

You can also try simpler methods, like a fully connected network, or even logistic regression.


If you want to find periodic behaviors of your data, you should use the Fourier transform, which decomposes your data into a linear combination of cyclic waveforms. If you have a guess on the actual period, as in your case, you can try something simpler. For each hour during the day, compute the mean $\mu$ and variance $\sigma^2$ of your data, and plot the intervals $[\mu-\sigma,\mu+\sigma]$ for each hour. That should give you an idea regarding your hunch. (More generally, you can try a sophisticated method like ANOVA.)

Perhaps you should ask your question over in stats.se.


What is a problem, a task, and a solution?

philosophically, a problem isn't a problem until there is unrest, and a way to explain it as such. i.e. an understanding leads to determining if it really is a problem, or just misunderstood.  Correctly specifying the problem then leads to its identification.

A bit morbid, but for ex, people dying from arsenic poisoning seems like a problem. Arsenic is poisonous, it will cause death. Is this the problem? No, the problem is exposure. (stated generally for brevity.) The task becomes solving exposure. And of course there may be multiple solutions. Detection, protective gear, isolation, etc.


Solving Subset Sum Without the Use of Dynamic Programming

Yes.

This paper has applied polynomial arithmetic to that problem.


Show that only a few multiples of .01 decimal are powers of 2

Hint: The four values are $25/100 = 1/4$ and its multiples.

If all you want to do is store an exact amount of currency, you can use an integer which represents the amount of cents. (This is known as fixed-point arithmetic.)


What data structure would help find nearby coordinates quickly?

Yes, you could you could do better than a naive approach - you could use a k-d tree data structure.

Clever implementations, such as sklearn k-d tree do the nearest neighbour lookup in O(log(n)) which, unless you have a high dimensional and sparse dataset, will work significantly faster than a naive O(n) approach.


Machine Learning: Identify Patterns in Time-Series Data

Yes, your data is "time-series data", since it's a sequence of measurements of the same variable collected over time. Time-series data can be collected continuously or at discrete intervals.

Your sample data can be expressed as a function of time - maybe it helps to think of the "function" as the process that produces the measured output, the input to the function is the date/time stamp, and the output is the value of that parameter at that time:

$\text{INVERTER_1.VOLTAGE_DC}( \text{5/25/2016 14:30:01} ) = 249.5$

You don't necessarily need to define the (general) function(s) that produce your data to perform time-series analysis - it's enough to know the value of the function at your measurement times. The range of time-series data can be continuous & real-valued, discrete, or even non-numeric.

It's certainly possible to use machine learning techniques on time-series data, e.g. for forecasting, anomaly detection, or pattern identification.

Neural nets might be a good choice if you're interested in predictive modeling. One possible setup is to use the current parameter measurements as input to the neural net, and the output is the predicted future value or "state of the system" (e.g., whether a breaker is open or not).

WEKA is a good open-source machine-learning toolkit that contains implementations of many different ML algorithms.


What is the optimal way to cut B chocolate bars to share equally between N people?

If optimal means having less cuts, can do this:

1. Line the chocolate bar up.
   [bar 0][bar 1][bar 2]

2. Treat that as a big bar.
   [big bar            ]

3. Divide the big bar equally.

Only about N cuts needed (if B < N)

If B > N, just give everyone equal number of bars. Then divide the remaining bars with the above algorithm.

Or 1 cut:

[bar 0]
  [bar 1]
    [bar 2]

cut vertically once.

I am sure there might be easier way to line it up... if optimal means that we don't need to use a ruler to measure the chocolates in real life.


Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

Watch this video and you should get:

$$
\begin{array}{c|lcr}
i\bigg/j &  1 & 2 & 3 &  4 & 5 \\
\hline
1 & \text{C,S} & \text{B} & \text{B,S} & \text{A,B,C} & \text{B,C,$\color{red}{\text{S}}$,A} \\
2 & \quad\blacksquare & \text{A} & \text{A} & \text{B,C,A,S} & \text{A,B,C} \\
3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \text{A,S,C} \\
4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\
5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\
\end{array}
$$

Since S is in the left and higher corner so we can derivate the word $baabb$ from the context


How do I know which direction I should rotate a node in an AVL Tree?

I think, I should get 37 as the root node 25 as it's left child and 52 as it's right child but I dunno.

You plan is correct.

What you need to do is a left-right rotation as shown in the third column of the table below. That is,  a left rotation at node 25 followed by a right rotation at 52. It is symmetric to the right-left rotation as shown in the fourth column and as explained in Wikipedia.


Finding optimal set for a sum of a product function over a 2D lattice

The set $S$ must have the following form: there must exist a threshold $t$ such that:

If $xy < t$, then $(x,y)$ is in $S$.
Some or all of the points $(x,y)$ with $xy=t$ are in $S$.
If $xy > t$, then $(x,y)$ is not in $S$.

Moreover, in the second bullet, it doesn't matter which points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$.  Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.

It follows that one way to parametrize the set is as

$$S = \{(x,y) : xy < t \text{ or } (xy=t \text{ and } x<u)\},$$

for some parameters $t,u$.  It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.

So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$.  How can we do that?

One easy way is to use binary search.  Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy < t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy < t$, i.e., such that $y < t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$.  Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$.  This gives you the value of $t$.  It also gives you the number of points $(x,y)$ such that $xy<t$; call that number $k_0$.

Once you know the value of $t$, the next step is to choose a suitable value for $u$.  We'll need to choose $u$ so that there are exactly $k-k_0$ lattice points $(x,y)$ such that $xy=t$ and $x<u$.  Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k_0$ of them.

In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time.  The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.


What happens if we expand the alphabet of a given Turing Machine?

That’s a table of transitions, and it determines what the program does when it encounters a given symbol on its tape while in a given state.  This program, if I’m reading it right, accepts strings containing two consecutive 1 symbols before the first space.

If there were another symbol, it would be necessary to define what the program would do on encountering them.  For example, to ignore them, there would be a pair of transitions saying that, if the program is in state s1 and reads a 2, it should stay in state s1 and move to the right, and that if it is in state s2 and reads a 2, it should stay in state s2 and move to the right.


First, the definition is clear: support is exactly "the fraction of transactions that contain a particular subset of items." This is a data-mining term, not a statistics term.

$supp(A)$ is the fraction of transactions that contain item $A$. $supp(B)$ is the fraction of transactions that contain item $B$. $supp(A,B)$ is the fraction of transactions that contain the subset $\{A,B\}$.

Now, your question really seems to be more about how the authors expound on this, which does seem to be a little unclear. As a statistic, support can basically mean, "What is the probability that this subset of items is contained in a random transaction?" That is, you can consider that $supp(A)=\mathbf{P}(A)$.

Then you can see that
$$supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$$
comes from the definition of statistical independence,
$$\mathbf{P}(A\cap B) = \mathbf{P}(A)\mathbf{P}(B) \iff A \perp B.$$


Big-O: Why is the time complexity of these loops O(N)?

Look at how many steps the inner loop is taking. It's $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. However the geometric series tells us:

$$\sum_{k=0}^{\lceil\log n\rceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2^k} = 2n$$


According to your description:

Each node in the network can relay a certain amount of traffic per time unit.
Each link has a certain capacity.

In order to convert your problem to an instance of network flow problem, one can do the following transformation. In the underlying graph of network, $G = (V,E)$, for any vertex $u \in V$ that has an outgoing edge $(u,v) \in E$, add an auxiliary vertex $u'$. Next, add an auxiliary edge $(u,u')$ with capacity equal to the capacity of $u$ for any auxiliary vertex $u'$. Finally, replace all $(u,v) \in E$ with $(u',v)$. Below is an illustration of how the network graph looks like before and after transformation.

The transformed graph can be seen as a flow network with node $1$ as source and nodes $2$ and $5$ as sinks. More generally, nodes with no incoming edges can be treated as source(s) and those with no outgoing edges as sink(s). Introducing an additional vertex to which all other sinks are connected with infinite capacity, you can further reduce your problem to a single-source single-sink flow network.

The goal is to find the optimal path to all nodes. Therefore, aside from the value of maximum flow itself, the algorithm you use for finding such a flow is also important. Edmonds-Karp algorithm uses BFS for finding the maximum flow over the shortest path. However, you want your maximum flow to go through as many nodes as possible. Thus, you need to make sure that your flows use longest paths between source and sink.

Luckily, for Directed Acyclic Graphs (DAGs), the longest path problem can be solved in linear time using dynamic programming. Thus, by modifying Edmonds-Karp algorithm such that it uses longest paths for flow augmentation, you ensure that the maximum number of nodes will be visited by each augmenting path.

In your example, the modified algorithm will output the following flows in order:

A flow of value $40$ over path $\langle 1,1',4,4',3,3',5 \rangle$.
A flow of value $10$ over path $\langle 1,1',3,3',5 \rangle$.
A flow of value $50$ over path $\langle 1,1',2 \rangle$.


The communication complexity of the distance between two strings

Suppose that the Hamming distance between $x$ and $y$ is $n/2 - \sqrt{n}$. Suppose that you sample $m$ indices with replacement, and let $S$ be the number of indices on which $x$ and $y$ disagree. Then $S$ has expectation $mp$ and variance $mp(1-p)$, where $p = 1/2 - 1/\sqrt{n}$. According to the central limit theorem, for every fixed $t$ we have
$$
\Pr\left[ \frac{S-mp}{\sqrt{mp(1-p)}} \leq t \right] \longrightarrow \Pr[N(0,1) \leq t].
$$
We are interested in the event $S \leq m/2$, which is the same as $S - mp \leq m(1/2-p) = m/\sqrt{n}$, or equivalently
$$
\frac{S-m/p}{\sqrt{mp(1-p)}} \leq \frac{1/2-p}{\sqrt{p(1-p)}} \sqrt{m} \approx \sqrt{\frac{m}{4n}}.
$$
In particular, if $m = cn$ then (following a short argument) the probability of error tends to
$$
\Pr[N(0,1) > \sqrt{c/4}].
$$
For small enough $c$, this would be more than $1/3$, giving an $\Omega(n)$ lower bound for this version of your algorithm.

In your case, you choose indices without replacement. A similar argument works, using the central limit theorem for hypergeometric random variables, see for example Lahiri and Chatterjee, A Berry–Esseen theorem for hypergeometric random probabilities under minimal conditions, Theorem 2.1.


Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any accepting run of $M$, there is exactly one setting of $z$ which satisfies $\phi$.

By definition, if $x \in L$ then $\phi$ has at least $(2/3)2^m$ satisfying assignments, and if $x \notin L$ then $\phi$ has at most $(1/3)2^m$ satisfying assignments. You can distinguish between the two cases using a $\mathsf{\#SAT}$ oracle.


A nondeterministic Turing machine can be simulated using a deterministic Turing machine in exponential time (can be shown as a simple exercise). Furthermore, NDTM is a generalization of DTM. So, the computability powers of NDTMs and DTM are equal, in sense of decidability. So, the Halting problem is not decidable by a NDTM. However, their time complexity is different.


Trying to break the proof of undecidability of the halting problem

Let's do this step by step.

"Z(A,b) where {A,b!=Z}"
I understand this to mean "just forbid input Z for algorithm Z". You can not do that. A machine that is supposed to solve the halting problem has to work on all machines, by definition of the problem. In other words, you make the assumption "Let Z be a machine that does not solve the Halting problem" -- that does not lead anywhere.

dkuper's argument is correct: you can derive the contradiction by feeding any of the infinitely many indices of the (assumed) solver of the halting problem, arriving at the same contradiction. Since this set of indices is not recursive, you can not program your machine to detect every alias.

Then the machine does not solve the halting problem anymore (see 1). Even if we had some leeway there, just assume the function that solves the halting problem for all functions but the one which solves the halting problem, and do the same proof.
And when you try to fix this in the same way, I'll get another function. And another one. There are enough of them.

In other words, your strategy of fixing one (or finitely many) special cases won't lead you anywhere. The halting problem is far too undecidable for that -- as the proof shows.


Closed form for the recurrence T(n) = T(n-1) + n²


Reducing Graph Reachability to SAT (CNF)

Maybe the solution is to use the 2-SAT problem which does have a polynomial solution.

For a 2-SAT problem, you can indeed build an implication graph. Basically a clause $(a \vee b)$ leads to the implications $\neg a \implies b$ and $\neg b \implies a$. The problem is satisfiable if there is no variable $x$ such that $x$ and $\neg x$ are in the same SCC of the implication graph. Being in same SCC is equivalent to double reachability:

it exists a path from $x$ to $\neg x$
it exists a path from $\neg x$ to $x$

So for any skew-symmetric (required property) graph, you can build a 2-SAT problem for which it is the implication graph.


Hashing a Specific Range Of a Character Array

Use a rolling hash function, such as the Rabin-Karp hash.  This allows you to compute hashes of any subrange of $A$ very efficiently, e.g., in $O(1)$ time, assuming you use some extra memory to keep track of all of the intermediate states of the rolling hash.

If $A[0..n-1]$ is your array, a rolling hash defines the hash of the entire array using a recurrence like this:

$$x_i = f(x_{i-1}, A[i])$$

where $x_{-1}$ is some fixed constant and $f$ is some function.  Now here's what you can do.  You can store the $x$ values in an array $X[0..n-1]$ (where $X[i]=x_i$).  This will allow you to compute the hash of any prefix of $A$.

If you want to be able to compute the hash of any consecutive range of $A$, choose the function $f$ carefully to be reversible.

A simple instantiation: let $X[-1] = 0$ (for some constant $c$) and

$$X[i+1] = \alpha \cdot X[i] + A[i] \bmod 2^{32},$$

where $\alpha$ is some 32-bit constant (you'll want it to be odd).  Preprocess the array $A$ once to compute the array $X[0..n-1]$.

Now, the hash of $A[i..j-1]$ can be very efficiently computed: it is the following:

$$X[j-1] - \alpha^{j-i} X[i-1]  \bmod 2^{32}.$$

Notice that $\alpha^{j-i} \bmod 2^{32}$ can be computed efficiently using fast exponentiation algorithms, i.e., repeated squaring modulo $2^{32}$.  Thus, assuming you've stored the array $X$ alongside the array $A$, a hash of any range of $A$ can be done in $O(1)$ time.

If you want something even simpler and easier to implement, set $\alpha$ to 1.  Then the hash of $A[i..j-1]$ just becomes $A[i]+ A[i+1]+ \cdots + A[j-1]$, and $X[i]$ stores $A[0] + A[1] + \cdots + A[i]$, so the hash of $A[i..j-1]$ is just $X[j]-X[i]$.
However, the quality of this hash degrades and you might see an increase in hash collisions.


Finding shortest path involving additional restrictions

We can create a new graph consisting of $N\cdot (H + 1)$ nodes and apply the Dijkstra algorithm on that graph. We will denote the new nodes as $(u, h):$ which means that the boat is at island $u$ and has been damaged by $h$ units, where $h$ is between $0$ and $H$. For each edge $(u, v, d, t)$ that goes from island $u$ to island $v$ while taking $d$ damage and $t$ time, we will create multiple edges in the new graph $((u, h), (v, h+d), t)$ (for $0 \leq h \leq H-d$). Your starting node will be $(A, 0)$ and to find the shortest path to $B$ you need to apply the Dijkstra algorithm and take the minimum time to $(B, h)$ for some $h$ between $0$ and $H$.


Is computational power of Neural networks related to the activation function

Just a note:

rational-weighted recurrent $NN$s having boolean activation functions (simple thresholds) are equivalent to finite state automata (Minsky, "Computation: finite and infinite machines",  1967);
rational-weighted recurrent $NN$s having linear sigmoid activation functions  are equivalent to Turing Machines (Siegelmann and Sontag, "On the computational power of neural nets", 1995);
real-weighted recurrent $NN$s having linear sigmoid activation functions are more powerful than Turing Machines (Siegelmann and Sontag, "Analog computation via neural networks", 1993);

but ...

real-weighted recurrent $NN$s with Gaussian noise on the outputs cannot recognize arbitrary regular languages (Maass and Sontag, "Analog Neural Nets with Gaussian or Other Common NoiseDistributions Cannot Recognize Arbitrary Regular Languages" , 1995);


solving recurrence by substitution, calculations doesnt add up

Using the so-called substitution method, we get (for even $n$)
$$
\begin{align*}
p(n) &= 2p(n-2) + n \\ &= 4p(n-4) + 2(n-2) + n \\ &= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &= \cdots \\ &= 2^{n/2} p(0) + 2^{n/2-1} 2 + 2^{n/2-2} 4 + \cdots + 2^0 n.
\end{align*}
$$
Let's assume for simplicity that $p(0) = 0$. We can write
$$
p(n) = \sum_{k=0}^{n/2-1} 2^k (n-2k) = 2^{n/2+2} - n - 4 = \Theta(2^{n/2}).
$$
(Solution courtesy of Wolfram alpha.)


It would work, the only problem is that it will generate a lot of extra piles for the intermediate results that are difficult to track.
if the sorting algorithm sorts the $d$-digit numbers starting from their most significant digit it would create 10 piles at first (one pile for the numbers starting with 0, another one for those starting with 1 and so on) and then sort each pile recursively as explained in the book.
The problem is that to sort the pile of numbers starting with 0 the algorithm needs to create ten more piles (one for the numbers starting with 00, the second for the numbers starting with 01 and so on, the last pile is for the numbers starting with 09).
Thus we have created 19 piles until now. To sort the pile of the numbers starting with 00 we need to create 10 more piles. If this process continues until the $d$ digit are sorted you can imagine that a huge number of piles are created (how many?).
This are the extra piles that the book was referring to.
If you use LSD radix sort you don't have to split the numbers in piles at all. You can just sort the input pile by last digit, then the same pile by the penultimate digit and so on, after $d$ steps you will end up with the expected result.
The intuition is the following: let $d$ be $2$ and let $83$, $19$ and $17$ be the input.
The first step on MSD radix sort will place $17$ and $19$ before $83$. Then if you sort the same whole pile by the second digit you will end up with $83$ before $17$ which is wrong. You need to split the pile because you have to "remember" the previous sorting made by the algorithm, which is more "important".
Conversely, the first step of LSD radix sort will place $83$ before $17$, then $19$. If you take the whole pile and sort it by the first digit you get $17$, $19$, $83$ which is correct. You don't need to split the pile because the current step of the algorithm is more "important" of the previous ones and it is allowed to "mess up" the previous ordering in any way (for example by placing $83$ after $17$ and $19$). This would work as long as the sorting algorithm used for each digit is stable.


How does one generate a list of size N of all possibilities using a dictionary of size D?

The answer is elementary: recursion!

The underlying observation is that if you can create lists of size $N-1$, you can easily create lists of size $N$ by just appending any one of the $D$ values to every $N-1$ long list.

In pseudo code:

def all_possibilities(n, D) {
  if ( n == 0 ) {
    return [[]]
  }
  else {
    smaller = all_possibilities(n-1,D)
    return smaller.map { l =>
        D.map {
          d => l ++ [d]
        }
      }.flatten
  }
}

You can prove this correct by induction over $N$.


Can you determine rotation/camera calibration from series of images separated by pure rotation

If the images are related by pure rotation, then the homography would give you the rotation matrix.  If the rotation is in-plane, then you would not be able to compute the intrinsics.


What is the runtime of the following code?

Hint: First of all, since the code in the loop doesn't depend on $x$, the running time of the code is $\Theta(n)$ times the running time of the code inside the outer loop. Second, the running time of the code in the inner loop is $\Theta(\ell)$, where $\ell$ is the number of iterations of the while loop, which is the number of times you need to double $1$ until you reach or exceed $n$. Perhaps you can find a formula for $\ell$.


Converting nested absolute value into linear programming

This sounds like a homework problem, so just hints here.

We'd usually just transform $x_1$ and $x_2$ into two new variables,
$$
\begin{array}{ccccc}
x_1^{'}~{\equiv}~x_1-a_1 & & \text{and} & &
x_2^{'}~{\equiv}~x_2-a_2
\end{array}
,
$$such that the new problem is$$
\min{\left|
\begin{array}{c}
{\left|x_1^{'}\right|}-{\left|x_2^{'}\right|}
\end{array}
\right|}.
$$
Then, the absolute values imply symmetries such that we don't need to consider some parts of the domain.

We may ignore:

$x_1^{'}<0$, because it's degenerate with $x_1^{'}>0$ under $\left|x_1^{'}\right|$.
$x_2^{'}<0$, because it's degenerate with $x_2^{'}>0$ under $\left|x_2^{'}\right|$.
$\left|x_1^{'}\right|<\left|x_2^{'}\right|$, because it's degenerate with $\left|x_1^{'}\right|>\left|x_2^{'}\right|$ under $\left|\left|x_1^{'}\right|-\left|x_2^{'}\right|\right|$.

Typically you can specify these sorts of domains to ignore in terms of constraints.

Then, since the degenerate cases have been removed, the objective function's just$$
\min{
\left(
{x_1^{'}}-{x_2^{'}}
\right)
}.
$$


I doubt that “overhead” is a term. Here’s what we use in Russian papers:

оверхед — direct transliteration (for informal texts)
издержки — costs (of production)
Translations of “slowdown” (for time) and “blow-up” (for space).


Can you substitute functions in Big-$\Theta$ notation?

Bit $\Theta$ gives big possibilities. Let's write down what we have, assuming appropriate conditions on constants and infinity neighbourhood:
$$f(n)=\Theta(\log n) \Leftrightarrow a_1 \log n \leqslant f \leqslant a_2 \log n$$
$$g(n)=\Theta(n+\log n) \Leftrightarrow b_1 (n+\log n) \leqslant g \leqslant b_2 (n+\log n)$$
Now we combine from above inequalities
$$ c_1 (n+f) \leqslant b_1n+\frac{b_1}{a_2}f\leqslant g \leqslant b_2 n + \frac{b_2}{a_1}f \leqslant c_2 (n+f) $$
which gives $g(n) = \Theta(n + f(n))$.


Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$


Are there any computer science encyclopedias?

There are two that I've seen:

Encyclopedia of Computer Science and Technology by Allen Kent (Over 40 volumes)
Encyclopedia of Computer Science and Technology by Harry Henderson

Also, Wikipedia could be considered containing a CS encyclopedia.


(1) is hard to answer unless you clarify what you mean by "versions of SAT problem."  If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only nontrivial class known to be in NL is 2-SAT.

As for question (2), 2-SAT is amenable to dynamic programming, as is SAT in general.  During the DPLL process each partial assignment produces a new subformula: the previous formula with false literals removed and all satisfied clauses deleted.  As subformulas are determined to be unsatisfiable, they can be memoized in a canonical form.  If a known unsatisfiable subformula is encountered again during the DPLL search, a table lookup can identify it and the search can immediately backtrack.  For SAT instances derived from problems with many symmetries (and therefore many identical subformulas) the time savings can be substantial.


Subtracting binaries using two's complement

Your book is wrong and what you are doing is correct.

1110 is 14 in decimal and 1011 is 11 in decimal. Hence the answer should be 3 i.e. 0011


Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

This variant of 1-in-3 SAT is polynomial time solvable. I will try to show this using the fact that 2-CNF-SAT is polynomial time solvable: wikipedia 2-SAT. (There may be better ways or more efficient algorithms for this particular problem)

Given a special 1-in-3 sat formula $F$, do the following:

Keep the size-1 clauses
Replace any size-2 clause $(\ell_1, \ell_2)$ by formula $(\ell_1\vee \ell_2) \wedge (\neg \ell_1 \vee \neg \ell_2)$
For a size-3 clause $(\ell_1,\ell_2,u)$ where $u$ is unique to this clause: replace it by $(\neg \ell_1 \vee \neg \ell_2)$

It is easy to see that this results in a 2-CNF formula, let's call it $F'$. Use your favorite way to solve 2-SAT to find out whether $F'$ is satisfiable.

Verify that the original 1-in-3 SAT formula is satisfiable, if and only if $F'$ was satisfiable. (If this needs more explanation let me know)


Time complexity of min() and max() on a list of constant size?

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 elements takes much longer than finding the minimum of a list of 3 elements.


Is it possible to encode an arbitrary computation as a series of NP complete problem instances?

Each program instance can be encoded as a (possibly very long; even infinite, if the program doesn't halt) series of NP complete problem instances, e.g. as follows:

For each "wire" inside a computer, we can derive a SAT formula that describes how the value (on or off) on this wire after the following clock signal depends on the currrent values of several other wires.  Using such SAT instances along with a set of variables that describe the current state of the computer, we are able to simulate any computation through a series of SAT instances.

Of course it is possible to combine multiple of these instances (or use a different approach), in order to simulate larger chunks of the computation at once. But there are limits:

If your original problem is in NP, then of course you can encode it as a single NP complete problem instance. But you probably will not gain much from doing this.

If your original problem is not in NP then you will need a superpolynomial number of NP complete problem instances in order to solve it, since a polynomial number of NP complete problem instances can be solved in polynomial time by an NDTM, implying that the problem is in NP.

So the short answer to your question is: "Yes, but usually not in a way that is helpful in the sense of your motivation."