Can I use the following method to prove an algorithm is correct?

I am rather surprised that you raised this question since the meticulous and enlightening answers you have written to some math questions demonstrate sufficiently that you are capable of rigorous logical deduction. It seems that you became somewhat uncomfortable when you stumbled upon a new and unorthodox way to prove an algorithm is correct.

Believe in yourself. Believe in logic.

Yes, I believe you have shown your algorithm is correct. To be absolutely clear, suppose you have shown all of the following.

An optimal solution exists.
Your algorithm provides a solution and only one solution.
Every solution that is not the solution provided by your algorithm cannot be optimal.

Then your algorithm must provide an optimal solution. The implication is just simple logic.

You do not even need to show that solution provided cannot be improved in the same way as any other solution.


Computer Science is a multifaceted discipline - and Algorithms and Data Structures is important part of it. You can try free video-courses, like Algorithms, Part 1, from Princeton University - it's running right now.

Another remarkable free video-course Algorithms: Design and Analysis, Part 1, from Stanford has finished recently - hopefully it will be repeated in the future. Part 2 of this course will start this Monday.


How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well.  Focus on that before you try to tackle any of the topics in this post, or you're going to get confused.

Here is a suggested syllabus:

First, study big-O notation.  Understand what it means.  Work through the definitions.  This is well covered in standard algorithms textbooks, so work through that material patiently.  See also, e.g., How does one know which notation of time complexity analysis to use?, How to come up with the runtime of algorithms?.  Try to understand why your "shouldn't this be true no matter how large n is?" question is meaningless (hint: big-O notation relates two functions, not two numbers).
Understand bit complexity as a measure of running time for algorithms that work with large numbers.  See, e.g., Precise runtime of the algorithm to find number of digits in an integer,  Relationship between an integer N and the number of bits n required to represent the integer
Understanding the bit complexity of addition.  This will be a good test whether you understand bit complexity.  See, e.g., Time complexity of addition.
Understand the bit complexity of multiplication.  Understand why it is an open problem how fast we can multiply two integers.  See, e.g., Complexity of multiplication, https://en.wikipedia.org/wiki/Multiplication_algorithm,
Complexity of a recursive bignum multiplication algorithm, What is the fastest algorithm for multiplication of two n-digit numbers?.
Understand the bit complexity of division and modular reduction.  See, e.g., Complexity of Integer Division, Complexity of taking mod.

If there is any of these steps you are unclear on, ask a question about that specific aspect until you understand it well.  Then, go back and study the material on gcd's.  This background material will probably help you make it further through that material.

Remember that just because there is an algorithm to solve some problem in time $O(f(n))$, doesn't necessarily mean that that is the fastest algorithm to solve that problem.  It doesn't mean that is the fastest that the problem can be solved.  For instance, bubblesort can be used to sort numbers; it has a $O(n^2)$ running time.  That doesn't mean that $O(n^2)$ is the "fastest that numbers can be sorted".


Is my proof of my greedy algorithm to find subsequence correct?

A post that requests us to check if a solution to a problem is correct is off-topic in general, especially when the solution is correct. However, in the current case, there are a couple of minor conceptual misunderstandings in this question, which I would like to address.

  Would this be a way to prove the optimality as I cannot find another optimal that takes more than $O(n+m)$, hence just showing that the optimal and greedy would give the same result?

What is "the optimality"? In the original problem, there is no requirement of any kind of optimality. The requirements are

the algorithm should decide whether $'$ is a subsequence of $$.
the algorithm should run in time $(m+n)$.

Although your algorithm looks like a greedy algorithm, the quantity or the objective function that should be optimized is never defined. So, it makes little sense to "prove the optimality" of your algorithm. It does not, in fact, make much sense to say that your algorithm is a greedy algorithm without specifying the objective function! That is probably the source of your confusion. That is why your proof seems unclear and dangling at a few places, since your proof is only a proof of correctness.

On the other hand, we can list three objective functions. For one of them, your algorithm is the optimal algorithm. For the other two, your algorithm becomes a greedy and correct algorithm.

I will state the objective functions in the form of three easy exercises. Hopefully you will not be confused any more.

Exercise 1. Show that your algorithm run in $O(m)$ time. Show that any algorithm that finds $S'$ will run at least in $\Theta(m)$ time in worst cases. (Note that $O(m+n)$ cannot be used here unless we assume $m\ge n$, in which case $O(m)=O(m+n)$.)

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its finishing index $FI(sub)=i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum finishing index if there is a subsequence that is the same as $S'$.

Exercise 3. For each subsequence $sub=(S_{i_1}, S_{i_2}, \cdots, S_{i_k})$ of $S$, define its total index $TI(sub)=i_1+i_2+\cdots+i_k$. Show that your algorithm is a greedy algorithm that finds a subsequence of S that is the same as $S'$ with the minimum total index if there is a subsequence that is the same as $S'$.


Application of shortest vertex-disjoint path with time window

Your problem is not clearly defined, but it's likely it can be solved by running a standard algorithm on a longer graph.

If $G=(V,E)$ is your original graph, build $G'=(V',E')$ by making $t$ copies of each vertex in $G$, one per time slot (where there are $t$ time slots): call the copies $v_1,\dots,v_t$.  Now for each vertex $v \in V$, add an edge $v_i \to v_{i+1}$ for each $i$ (this corresponds to an object staying at vertex $v$ throughout time slot $i$).  Also, for each edge $(v,w) \in V$, add an edge $v_i \to w_{i+1}$ for each $i$ (this corresponds to an object moving from vertex $v$ to $w$).

Now you're looking for vertex-disjoint paths in $G'$.  There are standard algorithms for finding vertex-disjoint paths in $G'$ (e.g., using network flow or other methods).  If you want a collection of shortest vertex-disjoint paths, that might be possible, but you'll need to define precisely what objective function you want to minimize before we can suggest an algorithm.

This general approach can likely accommodate many additional requirements, such as that traversing a particular edge takes a certain amount of time (just use that as the length on the edge), or that we don't know the starting time when each object enters the system (add a source vertex for each object, with edges from the source to each place that the object might enter the system).


What does it mean by "not recursively enumerable"?

I'm using r.e. to mean "recursively enumerable" and co-r.e. to mean "the complement is recursively enumerable". I'm assuming by $L'$, you mean the complement of $L$.

To answer your questions directly:

This is not correct. Every language over a finite alphabet $\Sigma$ has a one-to-one correspondence to the natural numbers. To show this, you would have to construct a one-to-one function that maps the words of your language to natural numbers. This isn't difficult at all, but a bit technical, so I'm only going to sketch the construction: Pick some well-founded total order $\leq$ on $\Sigma^*$, for example the lexicographic order. For $w \in L$, define $$predecessors(w) := \{ v \in L \mid v \lneq w\}$$ to be the set of words in $L$ preceding $w$ according to your order. Define a mapping $f: L \to \mathbb N$, by $f(w) := |precedessors(w)|$, assigning to each word the number of its predecessors. You could then show that $f$ is in fact a one-to-one mapping. This construction works for any language, though it is not necessarily computable for all languages.
Correct, when $L$ is not co-r.e., by definition $L'$ is not r.e., so there cannot be an algorithm that enumerates $L'$.
Correct, your theorem says $L$ is r.e., therefore $L'$ is co-r.e. Note this follows from the first premise of your theorem, not from the latter premise. In general, $L'$ being not r.e. on its own does not imply $L'$ being co-r.e. In other words, there are languages that are neither r.e. nor co-r.e., see here.

To elaborate a bit more on what the theorem means: It says there is a language $L$ that is r.e. but not co-r.e.

The important insight is that if a language $L$ is r.e. and co-r.e., then it is decidable. Assume you have a TM $M$ for enumerating $L$ and a TM $M'$ for enumerating its complement $L'$. Then you can build a new TM $M^\star$ for deciding $L$: For a given input $w$, $M^\star$ simulates $M$ and $M'$ in parallel. Since either $w \in L$ or $w \notin L$, one of $M$ or $M'$ has to enumerate $w$ eventually. At this point, $M^\star$ stops the simulation and accepts or rejects $w$ based on which of $M$ and $M'$ enumerated it. It follows that $M^\star$ halts on all inputs and accepts $w$ iff $w \in L$. Therefore, $L$ is decidable.

Based on this insight, if you can find a language $L$ that is r.e. and undecidable, you can then conclude that it cannot be co-r.e. Since if it would be co-r.e. it could not be undecidable.

The usual example would be some variant of the halting problem, e.g. $H = \{ \langle M,w\rangle \mid M$ is a Turing Machine that halts on input $w\}$. You should know that $H$ is undecidable. To show that $H$ is r.e., you would have to construct a TM that enumerates $H$. I'm only going to sketch the proof: Your TM $M^*$ would iterate over triples of the form $\langle M, w, n \rangle$ for a TM $M$, $w \in \Sigma^*$ and $n \in \mathbb N$ in some fixed order (e.g. lexicographic order). When looking at such a triple, $M^*$ would simulate $M$ on $w$ for at most $n$ steps. If $M$ halts on $w$ within these $n$ steps, $M^*$ prints $\langle M, w \rangle$. It's not difficult to see that $M^*$ will eventually print every pair $\langle M,w \rangle$ for which $M$ halts on $w$, as for every such pair, there is some $n \in \mathbb N$, such that $M$ halts on $w$ within $n$ steps. Therefore, $M^*$ enumerates $H$, thus $H^\star$ is r.e.

Based on knowing that $H$ is r.e. and undecidable, you can conclude that $H$ cannot be co-.r.e. which proofs your theorem.


Let your vertex set be $\{v_1, \dots, v_n\}$.  If $n\leq5$, just add all possible edges.  Otherwise, create a new graph with vertices $\big\{v_{i,j}\mid i\in\{1, \dots, n\},\ j\in\{1, 2, 3, 4\}\big\}$, and edge set $\{v_{i,j}v_{k,\ell}\mid i\neq k\}$. You're looking for a minimum-weight perfect matching in that graph.  (Which is the same thing as a maximum-weight matching in the graph where you multiply all the costs by $-1$). This can be done in polynomial time, even though the graph isn't bipartite.


You are missing a fundamental detail: modern processors are pipelined. What it means in a nutshell is that instruction $I_{n+1}$ is fetched from memory and begins being processed way before instruction $I_n$ has been executed completely. But if $I_n$ is a conditional branch, we have no way to know for sure whether or not the jump will happen: we would have to stop fetching instructions until we finish evaluating $I_n$.

Branch prediction doesn't come from theory but from a strictly practical observation: it is better to be sometimes wrong, but decide quickly than to be always correct but slowly.

A classical example is the following:

for (i <-- 0 to 1,000,000) do {
    ...
}

If we just take the "loop continues" branch every time, we will be wrong once but correct the other $999,999$ times, yielding a better average running time in practice.


Finding examples of languages that are "anti-palindromic"

One example will be $L = \{ x\ \ |\ \   binary(x) < binary(x^R), x\in [0,1]^*\}$.

And yet another example $L' = \{ x\ \ |\ \   binary(x) > binary(x^R), x\in [0,1]^*\}$.

The idea is, if $x \neq x^R$ you make  a rule to choose only one of them. You need to choose the rule such that palindromes should be rejected ($f(x) < f(x^R)$, for palindromes you must have $f(x)= f(x^R)$).You can also change the alphabet, I took binary alphabet just to get a quick answer.

$L$ and $L'$ above are not regular. And every anti-palindromic language will be non-regular and can be as bad as a non-RE language. Examble of an undecidable language: $L=\{x\ \ |\ \ $such that $ binary(x)<binary(x^R)$ if both $x$ and $x^R$ $\not\in$ Halt or both $x$ and $x^R$ $\in$ Halt, otherwise if $x \in$ Halt$\}$

Klaus Draeger explained in the comment below that anti-palindromic language given at the beginning of the answer is context-free: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$


Relationship between an integer N and the number of bits n required to represent the integer

The integer $N$ takes $\log_2 N$ bits to write down.  Set $n = \log_2 N$.  Then $N = 2^n$, so $\sqrt{N} = 2^{n/2}$.

I'd guess they are using the natural logarithm (to base $e$), which is where they get $e$ instead of $2$.  That's a bit odd but I suppose it is valid.

See also Complexity of multiplication and Precise runtime of the algorithm to find number of digits in an integer.


prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $

Define a sequence by $n_0 = n$, $n_{i+1} = n_i - \sqrt{n_i}$. Let $\ell$ be the maximal index such that $n_\ell \geq n/2$. For $i \leq \ell$ we have $\sqrt{n_i} \geq \sqrt{n/2}$, and so $n/2 \leq n_\ell \leq n - \ell \sqrt{n/2}$. It follows that $\ell \leq \sqrt{n/2}$.
Let $\ell_t$ be the maximal index such that $n_{\ell_t} \geq n/2^t$; so $\ell_0 = 0$ and $\ell_1 = \ell$. The preceding paragraph shows that $\ell_{t+1} - \ell_t \leq \sqrt{n_{\ell_t}/2}$. Since $n_{\ell_t+1} < n/2^t$, it follows that $n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$. If $t \leq \log_2 n$ then $n_{\ell_t} \geq 1$, and so $(\sqrt{n_{\ell_t}}-1)^2 = n_{\ell_t} - 2\sqrt{n_{\ell_t}} + 1 \leq n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$, and so $\sqrt{n_{\ell_t}} < \sqrt{n/2^t} + 1$. Therefore if $n_{\ell_t} \geq 1$ then $\ell_{t+1} - \ell_t \leq \sqrt{n/2^{t+1}} + 1/2$. It follows that if $t \leq \log_2 n$ then
$$
\ell_{t+1} \leq \sqrt{n/2} + \cdots + \sqrt{n/2^{t+1}} + t/2 = O(\sqrt{n} + t).
$$
Choosing $t = \lfloor \log_2 n \rfloor$, we get that the maximal index $s$ such that $n_s \geq 1$ is at most $\ell_{t+1} = O(\sqrt{n} + \log n) = O(\sqrt{n})$.
This shows that assuming an initial condition of the form $T(n) = O(1)$ for $n \leq 1$, you can bound $T(n) = O(\sqrt{n})$; a matching lower bound is obvious (at each step, the value of the parameter decreases by at most $\sqrt{n}$).
Using similar ideas, you can show that if you replace $\sqrt{n}$ by its floor or ceiling, then the resulting recurrence still grows like $\Theta(\sqrt{n})$.
What is the constant factor in the asymptotics of $T(n)$? If we define $\tau(s) = n_s$ and think of $\tau$ as continuous, then $\tau' = -\sqrt{\tau}$, and so $\tau(s) = (c-s)^2/4$. Since $\tau(0) = n$, we find that $c = 2\sqrt{n}$, and so $\tau(s) = (2\sqrt{n}-s)^2/4$. Therefore $\tau(s) = 0$ for $s = 2\sqrt{n}$, and so we expect $T(n) \sim 2\sqrt{n}$. This is indeed borne out by experiments, which suggest that $T(n) = 2\sqrt{n} - \Theta(\log n)$.


Using contradiction suppose $L=\{\left< M_1,M_2 \right>|L(M_1)\subset L(M_2)\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left<M_1,M_2\right>$ if $L(M_1)\subset L(M_2)$ will halt and accept.

We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left<w,M\right>$ if $M$  doesn't accept $w$. To do so, you have to make another Turing machine $M'$ using $w$ that you are sure $w\notin L(M')$. Thus you can give $\left< M',M\right>$ as input to $T$ and look for its output. If it accept it means that $L(M')\subset L(M)$ which means $w\notin L(M)$.


Shannon proved that the capacity of the channel is a limit on its capacity. This is actually the easy part of Shannon's theorem — it is much harder to show that capacity can always be achieved. A good source for this is Shannon's paper from 1948, A mathematical theory of communication, page 24, last paragraph before Section 14. As Shannon writes, the Shannon capacity is the limit more-or-less by definition.

While Shannon already found a formula for the capacity of a channel, namely the Shannon capacity, two directions are still open (though they have partial solutions):

Zero-error encoding, also known as block codes. The best capacity in this regime is a major open problem in coding theory.
Codes with efficient coding and decoding. Shannon's theorem is non-constructive (it uses a random code), and so the codes it implies cannot be used in practice. It is more difficult to construct codes having efficient encoding and decoding. There have been lots of developments in the recent years in constructing efficiently decodable capacity-achieving codes.

Another problem is the rate of convergence in Shannon's theorem - I'm not sure what the status of that is.

In your specific case, it seems that the improvement is not be breaking the Shannon barrier (which is impossible) but by effectively changing the channels, just as telephone lines can be used to carry high-speed network traffic.


Transform values of hash functions like MD5 into numbers

The output 735b90b4568125ed6c3f678819b6e058 is just a hexadecimal representation of a 128-bit (in binary) number, which corresponds directly to an integer between $0$ and $2^{128}-1$.  Therefore, you can think of MD5 as returning a numeric value.  You should be able to make the conversion from hexadecimal  string to integer trivially using any programming language (if not, Stack Overflow is the place to go to).


Removing recursion from a function with multiple params

Here is an equivalent way to calculate $t(x,y,z)$.

We distinguish between three cases:

$x \leq z$: the answer is $y$.
$x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise.
$x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise.

You should be able to prove this characterization by induction. The second case is identical to the third case, except that the condition $y \leq x$ is replaced by the condition $y \leq x+1$.


Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

The question is not clear about the details, but assuming said resources are always locked-then-accessed sequentially, then a deadlock is not possible to occur. Since the locks are always obtained in the same order, precedence would prevent any cross-lock scenarios. Once a transaction acquires the lock for the first item in the list, other transactions will have to wait for that lock to be released.

Even if the locks are acquired-released on one-by-one basis, deadlocks would not occur. Supposing 2 transactions T1 and T2 are concurring the locks for the resources A, B, C, the sequence of events would be:

T1 acquires A
T2 waits    A
T1 releases A
T2 acquires A
T1 acquires B
T2 releases A
T2 waits    B

Then there's the scenario where T2 overtakes T1. In that case nothing would change, T2 would then be the contentious transaction (holding everyone else behind). But no deadlocks.

T1 acquires A
T2 waits    A
T1 releases A
T2 acquires A
T2 releases A
T2 acquires B
T1 waits    B
T2 releases B
T2 acquires C
T1 acquires B

The number of concurrent transactions is not important. Possibly, the great the numbers of transactions concurring, the greater the number of overtakes. It would be contentious and some transactions, even though they entered first, could possibly lag way behind other transactions that arrived later. In edge cases, some transactions could give the impression they are deadlocked when in fact they are not (they are just being thrown around by the OS scheduler).

Also, in most (all?) Systems locks are not served on the the same order they are requested.
T1, T2, T3 could request a lock for the resource A, but T3 could be the first to get it. It's very likely the locks will be given in the order they were requested, but it's not guaranteed, especially if the system running the process is already dealing with too many threads. In such cases the OS can reorder the threads, thus changing the order the locks are acquired. No deadlocks still, but some transactions could take abnormally longer than others.

The case you describe (all locks being acquired and released at once) could be even more contentious, and could become a pain in the arse as the load in the system increases - because strange (and often *un-*debuggable) things starts to happen.

Still no deadlocks though.


If P = NP, do these NP-complete problems reduce to these specific easier versions?

1. if P=NP does each of the problems on the left reduce to the easy problem (in P) in its immediate right?

If P=NP then every problem on the left is in P, and trivially polynomially equivalent to every problem on the right. There is no special formal correspondence between the pairs of problems in each row of the table. The authors probably chose informally similar problems for the left and right columns to make the point that a seemingly small change to an efficiently solvable problem can make it NP-complete, and vice versa.

2. The book mentions that "the problems on the left are all difficult for the same reason! At their core, they are all the same problem [...]" does this imply that the problems on the right are also the same problem but in different guises?

I would say no. NP-complete problems are all polynomially equivalent, meaning that given an oracle that computes the answer to one in polynomial time, you can answer any other in polynomial time. Because there is no polynomial-time algorithm known for any of them without the oracle, the amount of time you save by using the oracle dominates the total time for large enough problem sizes, so you can argue that the oracle is doing the heavy lifting. This applies to any pair of NP-complete problems, so they all contain models of important parts of each other in a nontrivial way – somewhat like different computational models can simulate each other
Problems in P are trivially polynomially equivalent: given an oracle for one, you can solve any other one in the usual way and ignore the oracle. But you can't argue from this equivalence that the oracle played any role. P contains many problems like "is the input nonempty?" that are of no use in solving any other problem and clearly don't "contain" interesting problems like MST.
If it turns out that P=NP then it becomes much harder, perhaps impossible, to formalize the relationship between the problems that were formerly considered NP-complete; the apparent similarity between them might just be an illusion.

3. Does the Rudrata/Hamiltonian path reduce to minimum spanning tree if P=NP?

In the trivial sense, yes. If P≠NP, then it doesn't (if it did, that would give you a polynomial-time algorithm for Hamiltonian path).

In my opinion, the Rudrata/Hamiltonian path could be reduced to a spanning tree and not necessarily the minimum spanning tree as the Rudrata/Hamiltonian path only needs to find a path that connects all the nodes without the constraint of minimizing total of edge weights. Is this reasoning correct?

It might be reducible to some other spanning-tree algorithm, but that algorithm would have to be flexible enough that you could encode the Hamiltonian-path constraint somehow in the input.


Identify balanced and full binary search tree insert order

Keep trying.  Try a recursive algorithm.  You know that the root needs to be 8.  You should be able to infer what numbers need to go in the left subtree of the root.  What order should you insert those numbers in, to ensure that the left subtree results in a full and balanced binary tree?  Hmm, does that resemble a problem you've seen before?  You should be able to take it from there.


In general, what you are looking for is known as dynamic connectivity: it comes with different flavors depending on whether vertices/edges can be added, deleted, or if both operations are allowed.

Many relevant papers are summarized in this answer on TCS.SE. If you are looking for a practical implementation, a possible starting point is [1]. Here, the authors perform experiments and provide some C++ code (these are for fully dynamic algorithms).

[1] Iyer, R., Karger, D., Rahul, H., & Thorup, M. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.


Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

The problem

  Do two halting Turing machines accept the same language (or compute the same "function")?

is undecidable.

Let $M$ be an arbitrary Turing machine. Let $M'$ be a Turing machine that on input $x$, simulates $M$ (on some predefined input) for $|x|$ steps and accepts if (and only if) $M$ halts within $|x|$ steps (or, if you want to go with a TM computing a function, returns $1$ if $M$ halts within $|x|$ steps and $0$ otherwise).

If $M$ doesn't halt then $M'$ accepts the empty language (or, computes the function $f(x)=0$). If $M$ does halt then the language $M'$ accepts is non-empty (or, the function is non-constant).

This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether $M'$ is equal to the machine accepting the empty language (or, the machine computing the function $f(x)=0$).

This avoids all the issues of the function not being total or being unable to construct the function explicitly.


Existence of Efficient Set Difference Algorithm

You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table.  Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable.  Then do the same, with $T$ in the hashtable and iterating through $S$.

Fine print for complexity purists: this is expected running time, making suitable assumptions about the hash function.  However, the probability that the running time takes longer than $c \cdot (n+m)$ can be made exponentially small in $c$ with a suitable choice of hash function.  For practical purposes, you typically don't need to worry about this.

You can also do it in $O(n \lg n + m \lg m)$ time, using a suitable sorting algorithm plus a standard merge algorithm.  In some special circumstances, sorting might be even faster (look up counting sort and radix sort).

Which of these is faster in practice will depend upon the platform you run it on.  You probably will need to implement and try both, to see which will be faster.  You can't trust the asymptotic complexity in this situation, as caching effects and other implementation considerations have the potential to be more important than the asymptotics.


First off, a persistent map from address to value can simulate RAM. There is a time overhead of $O(\log(s))$ and a space overhead of $O(s)$, where $s$ is the space used.* So an algorithm that runs in time $t$ and space $s$ in RAM has a purely functional algorithm in time $O(t \log(s))$ and space $O(s)$. However, simulating the RAM itself, at least conceptually, creates a purely functional computer, not version of the particular algorithm in question, so it probably isn't what you're looking for.

Fortunately this algorithm can be tweaked slightly to be purely functional. Using a persistent sorted map from list item to count, you can traverse the list, updating the count in the map for each list item encountered in $\theta(n \log(c))$ time and $\theta(c)$ space, excluding input and output lists, where $c$ is the number of distinct values. Then, you can concatMap the (list item, count) pairs to count occurrences of the list item. As the map is already sorted by list item, the resulting list will be sorted.

The original algorithm runs in $\theta(n)$ time and $\theta(c)$ mutable space, excluding input and output lists, so the functional version introduces a factor of $\log(c)$ in its run time, which is the same factor introduced by simulating the RAM.

* Specifically, as far as time is concerned, $s$ is the mutable space used, as any immutable space can be provided separately in a read-only array so it doesn't impose any time penalty.


Between every two MST's there's a series of "nearby" MST's

Here is how you make progress from $k+1$ distinct edges to $k$ distinct edges.

Suppose $T$ and $T'$ has $k+1$ distinct edges, which refer to $k+1$ edges in $T$ and another $k+1$ edges in $T'$ and they are all distinct. Among these $2k+2$ edges suppose $e\in T$ has the smallest weight.

Adding $e$ to $T'$ results in a cycle $C\subseteq T'\cup\{e\}$. If there is an edge $e'\in C$ such that $w(e')=w(e)$ and $e'\notin T$, then we are done: let $T''=(T'\cup\{e\})-\{e'\}$, and now $T''$ has $k$ distinct edges with $T$, while $T''$ and $T'$ are nearby.

The rest is to show that such an edge $e'$ always exists. Since $C$ cannot be entirely contained in $T$, there must be an edge $e'\in C$ that $e'\notin T$. I leave it to you to verify that either $w(e')<w(e)$ or $w(e')>w(e)$ cannot happen, so it must holds $w(e')=w(e)$ and that $e'$ is what we want.


It is correct.

Mathematically, $A$, $B$ and $C$ are foremostly linear mappings between vector spaces. Say, $A:W\to X$ and $B: V\to W$, then $C = A\circ B$ is a linear mapping $V\to X$. Practically speaking, and that's where the matrix representation stems from, you represent a mapping $V\to W$ as a member of the tensor space
$V^\ast\otimes W$, where $V^\ast$ is the dual space of $V$, that is, any linear mapping $V\to W$ can be written in the form
$$
B(v) = \sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)
$$
where $b_{jk}$ are the coefficients characterising the mapping, and the $w_j$ form a convention-chosen basis of $W$ and the $f_k:V\to \mathbb{R}$ (or whatever field you're working over) basis of $V^\ast$. Then, we can see what the composition comes out as:
$$\begin{align}
C(v) = A(B(v)) =& \sum_l\sum_i x_l\cdot a_{li}\cdot g_i\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr)
  \\ =& \sum_{lijk} x_l\cdot a_{li}\cdot b_{jk}\cdot g_i(w_j)\cdot f_k(v)
\end{align}$$
The basis of $W$'s dual space will be chosen so that $g_i(w_j)=\delta_{ij}$, so
$$\begin{align}
C(v) =& \sum_{ljk} x_l\cdot a_{lj}\cdot b_{jk}\cdot f_k(v)
  \\ =:& \sum_{lk} x_l\cdot c_{lk}\cdot f_k(v)
\end{align}$$
where you have your matrix multiplication
$$
c_{lk} = \sum_j a_{lj}\cdot b_{jk}.
$$
There are two alternative, equivalent ways to look at linear mappings, and one of them you found: you basically group
$$
A(w) = \sum_{li} x_l\cdot a_{li}\cdot g_i(w)
     = \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)(w)
$$
...which you can do because the dual space is also a vector space; $\Bigl(\sum_i a_{li}\cdot g_i\Bigr)$ are just the row vectors of $A$ which are not in fact vectors but co-vectors—and now
$$\begin{align}
A(B(v)) =& \sum_l x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_j\sum_k w_j\cdot b_{jk}\cdot f_k(v)\Bigr)
  \\ =& \sum_{lk} x_l\cdot \Bigl(\sum_i a_{li}\cdot g_i\Bigr)\Bigl(\sum_jw_j\cdot b_{jk}\Bigr)\cdot f_k(v)
\end{align}$$
..and there in the middle is that scalar product between a row vector of $A$ and a column vector of $B$ (or, if you will, a row vector of $B^T$).

So yeah, this can be done and is often done in algorithms.

Does it help with cache? It can certainly help, if you naturally come by $B$ in transposed form. I think e.g. the Eigen library exploits this a lot, through lazy evaluation and pre-arranging intermediate results to come out transposed in the first place if deemend useful. If all you got is $B$ in un-transposed form though, well, the cost of transposing it (which is also not readily cache-friendly) may outweigh the cache penalty of multiplying in suboptimal order.

There are many approaches to this, it's a well studied field. But there's no silver bullet for the optimal transposition policy. (An interesting approach is to store matrices in Morton order, so that always both rows and columns have some cache coherence.)


Creating a binomial heap from an array in Θ(n) time

$O(f(n))$ amortized time means that if we make $k$ consecutive operations, total time does not exceed $k \cdot cf(n)$ for a chosen positive constant $c>0$.

In your case, each insertion is worst-case $O(\log n)$. However, they're amortized $O(1)$. It means that if you make $n$ consecutive insertions (that is, build a heap from an array), total time is bounded by $c \cdot n$ for some constant $c>0$ - that is, the total time is $\Theta(n)$.

If you want to prove formally that the total time of constructing $n$-element heap is $\Theta(n)$:

Denote $k$ as the current number of items in our heap (in the beginning, $k=0$).
Write $k$ in binary; if its $i$-th bit is set, we have a binomial tree of size $2^i$.
If you insert next element when there are already $k$ of them, you create a new tree of size $2^0$; if there was already a heap of size $2^0$, you merge them into a heap of size $2^1$; if there was already a heap of size $2^1$, you merge them and so on, until you find out there was no heap of size $2^t$ in a previous state. Time needed is thus proportional to the number of ones in the end of binary representation of $k$ (plus 1).
Note that we make first heap for every $k$; we'll make the second heap for each odd $k$, third heap for each $k \equiv 3 \mod{4}$ and so on. It means that $i$-th operation inside "merge-heap" will be done roughly once in $\frac{n}{2^i}$ insertions.

Now note that number of (constant time) create-tree/merge-tree operations cannot exceed
$$ \frac{n}{2^0} + \frac{n}{2^1} + \frac{n}{2^2} + \dots = 2n. $$

Thus, the total time for the algorithm "just make $n$ consecutive insertions" is $\Theta(n)$.


Defining a graph decision problem not in NP

Problems of the type "Count the number of [object]", where "[object]" is something that can be verified in polynomial time, are essentially what defines the class $\#P$ ($\textrm{Sharp-}P$). $\#P$ is the counting variant of $NP$.

As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as counting simple paths) it would have been $\#P$-complete.

If you take a $\#P$-complete counting problem, then the decision-counting variant ("are there at least $x$ many objects [...]") can not be in $NP$, unless the polynomial hierarchy collapses. This follows by Toda's theorem, which states that $PH\subseteq P^{\#P}$. If such a decision-counting problem would be in $NP$, we could use a polynomial number of calls to an $NP$ oracle to compute the exact number (by binary search). Thus $P^{\#P}$ would be equal to $P^{NP}$ and the polynomial hierarchy collapses.


why is $\Pi_2$ smaller than $NP\cap coNP$

You seem to be using the following definition of $\mathsf{NP} \cap \mathsf{coNP}$: it consists of all languages of the form $L_1 \cap L_2$, where $L_1 \in \mathsf{NP}$ and $L_2 \in \mathsf{coNP}$. However, in reality $\mathsf{NP} \cap \mathsf{coNP}$ consists of all languages $L$ such that $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$.


Form a directed graph of dependencies, with an edge $x\to y$ if course $x$ is a prerequisite for course $y$.  Use Kahn's algorithm to topologically sort the graph.  In particular, in each semester, you take all courses with indegree 0 (i.e., all courses where you've satisfied all prerequisites), then delete those courses from the graph.

This assumes there is no limit on the number of courses you can take in each semester.  Under that condition, it will let you complete your degree in the minimum number of semesters, in an order that respects the prerequisites.

If there is a limit on the number of courses you can take in a semester, the problem is more challenging.    This algorithm will find an order you can take your courses to get your degree, in an order that respects the prerequisites, but it is not necessarily the minimal number of semesters.  If you're in that situation, the best solution may depend on the number of courses you have and whether this is a practical problem you want to solve in real life or a theoretical problem where you care about worst-case asymptotic running time.


Method for eliminating spent hashes from a large collection?

There is no lossless way to compress a set of arbitrary numbers where the size of the set is unbounded to a fixed number of bits. Cryptography won't help with that.

If you're okay with the storage requirements growing linearly with the number of elements, then use a hash table. This method has no false positives or false negatives. Queries take $O(1)$ time.

If you want a fixed size and are okay with false positives then use a bloom filter. The more elements you add the greater the probability of false positives become.

If you can force the inputs to use a timestamp then you can reject attempts to add records with a timestamp too far into the past. You can then decide to remove all records from a database that are old enough to be rejected and still prevent double spending. (But if you remove the original record you can no longer test for its membership to the set.)

Hashcash rejects headers with dates more than 2 days in the past, so hashes older than 3 days can be deleted to save storage space while still preventing reuse.


Can a graph have a cycle containing all nodes but not Hamiltonian?

Just pick a tree which - by definition - doesn't have any simple cycle, but is connected, so you can visit all the nodes and return to the starting one but you must pass on some nodes more than once.

There are also graphs which have an Eulerian cycle (a cycle that traverses every edge exactly once) but not an Hamiltonian cycle. For example pick a graph made with two triangles having one vertex in common.


Clarification reg. jump consistent hashing

I suggest this as a better version of the paragraph.

Now, for a given $i$ and $k$, we generate a pseudorandom variable, $r$, that is uniformly distributed between 0 and 1, and set $j = \lfloor(b+1) / r\rfloor$. This gives $P(j \ge i) = (b+1) / i$, as we want:
$P(j \ge i)$
$ = P(\lfloor(b+1) / r\rfloor ≥ i)\quad$ substituting the definition of j
$ = P((b+1) / r \ge i)\quad$ because $i$ is an integer
$ = P(r \le (b+1) / i)\quad$ solving the inequality for $r$
$ = (b+1) / i\quad$ because $r$ is uniformly distributed between 0 and 1


Random forests don't allow you to use strings as features.  Instead, if you want to use random forests, you'll need to select new features and do some feature extraction, so that all of your features are numbers.  The features might be some function of the strings, e.g., a histogram of the lengths of the strings, or a count of the number of times each possible word appears in your document (see e.g. bag of words model).

The features that make sense for your application will depend heavily upon your specific application, so we can't give a one-size-fits-all answer.  The right set of features will be heavily domain-specific and application-specific, so you'll need to do some brainstorming about possible features and try out your ideas to see how well they work.  That said, if you want some hints or ideas to jumpstart your brainstorming about possible features that might make sense, the NLP (natural language processing) community might be a good place to start.


Understanding non-linear dimensionality reduction algorithm (locally linear embedding)

To answer your first question:

Usually we want to reduce the dimension, because dealing with high-dimensional data is a pain: (a) algorithms for dealing with high-dimensional data tend to have higher computational complexity, and (b) high-dimensional data is hard to visualize and hard to understand.  If you can reduce the dimension without significant loss of effectiveness of the subsequent computational task, that can be useful.


Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

take $C=\emptyset$ then you want to direct the graph so all node have in degree at least 1($DA1$) and now think about directed Hamiltonian cycle($DHC$) how you can reduce $DHC$ to $DA1$ !


Minimization of idle time with two kinds of actors

Observe that it takes a PM about 75 times as long to produce a widget as it takes a TM to clear that widget and let it start producing the next widget. And we have only 5 PMs.

Intuitively, it seems like we should have only one TM. It will be idle almost all the time, waiting for one of the PMs to finish. The PMs will be busy almost all the time, except right after they finish a widget and have to wait for the output to be cleared away.

Adding more TMs would simply add more idle time for them, while reducing the PM idle time by very little at best. Removing the sole TM would leave all of the PMs idle as soon as each of them finishes the first widget.

If the times were more similar, or the number of PMs were closer to 75, finding the answer would be more complex. This problem seems to be designed for a simple, intuitive answer.


Proving that L(G) is the language defined by the CFG G

Let us denote $L'$ the language defined by the CFG $S$.

To prove $L'$ = $L$ you must do two things:

prove $w' \in L' \Rrightarrow w'\in L(G)$, meaning $L' \subseteq L(G)$
prove $w \in L(G)\Rrightarrow w\in L'$, meaning $L(G) \subseteq L'$

Combine proofs 1 and 2, and you get that $L' = L(G)$.

The proofs themselves are not hard, since $L'$ has a very specific structure.


Relativization results in class separation

Yes, check out the classes IP (interactive polynomial time) and PSPACE (polynomial space).

In 1988, Fortnow and Sipser [1] showed  that these two classes have contradictory relativizations, that is, there exist oracles $A$ and $B$ ($A$ can be chosen to be $\text{PSPACE}$ itself) such that
$$\text{IP}^A = \text{PSPACE}^A\text{, and}$$
$$\text{IP}^B \neq \text{PSPACE}^B .$$

Later, Shamir [2] showed that $\text{IP} = \text{PSPACE}$.

Chang et al. furthermore showed that for a random oracle $A$, $\text{IP}^A \neq \text{PSPACE}^A$ [3].  See ibid. for a nice introduction and overview.
This result actually disproves the Random Oracle Hypothesis which states that

  the relationships between complexity classes which hold for almost all oracles must also hold in the unrelativized case [3].

References

[1] Fortnow, L. & Sipser, M., Are there interactive protocols for co-NP languages?, Inform. Process. Lett. 28, No. 5 (1988), 249-251.

[2] Shamir, A. IP = PSPACE, in "Proceedings, IEEE Symposium on Foundations of Computer Science, 1990," pp. 11-15.

[3] Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Håstad, J., Ranjan, D., & Rohatgi, P. (1994). The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1), 24-39.


Why not use large $k$ in a $k$-ary tree?

BTrees are used in practice - file systems, database with $k$ for example equal 1024 or 4096, so it seems to be bigger than binary.

Probably you have not encountered need yet.
For example ternary tree with comparing >, =, < gives theoretical improve $O(log_3 n)$, but self balancing trees in basic form do not accept duplicates, so there is more overhead and not strictly practical.
But bigger ones, yes, they give boost and you use it right now (on the computer).


Approximating the dominating set on a certain kind of DAG

That problem is hard to approximate by reduction from set cover:

max(DTM) = 2    and    exactly one vertex has  DTM = 0

and    the vertices with  DTM = 1  are exactly the sets    and

the vertices with  DTM = 2  are exactly the set-elements

To push a solution forward, just add in the  DTM = 0  vertex.

To pull a solution back, remove that vertex if it's present, and for each

DTM = 2  vertex, replace that vertex with any one of the sets that element is in.

However, you presumably have another property:  low maximum degree .

That is useful because:

Your problem is a special case of set cover:  The elements are the vertices and the

sets are those formed as [v in V such that u=v or (u,v) in E] for elements u of V.

The size of those sets is bounded above by one plus your graph's maximum out-degree.

Theorem 3.1.6 says the greedy algorithm does significantly better on such instances.


Can a transcript change dependent random variables into independent variables?

Yes. Consider the following protocol.  Alice flips a coin, and sets $X$ and $Y$ to be equal to the outcome of the coin flip.  She then sends $X,Y$ to Bob.  Note that the transcript will include the value of $X,Y$.

Now unconditionally, $X,Y$ are dependent (there is probability $1/2$ that they are Heads,Heads and probability $1/2$ that they are Tails,Tails). But conditioned on the transcript, $X,Y$ are independent (e.g., if the transcript says they are Heads, then with conditional probability $1$ they are Heads,Heads and all other cases have conditional probability $0$; that meets the definition for independence).


Find the minimum sum of distances between sets of points to a straight line in a plane

Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is
$\left| y - b\right|$.
The sum of a distances for a set of points $S = \{(x_1, y_1), \dots,
(x_n, y_n)\}$ is then
$$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$
which is minimized for which $b$?


Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?

$O(f(n))$ means: There is a constant c > 0, and an integer $n_0$, so that for every $n > n_0$ the time is less than $c \cdot f(n)$.
Note that the integer $n_0$ could be very, very large. And the constant c could be very, very large. If $n ≤ n_0$ then we know nothing whatsoever about the time; the $O(n)$ algorithm could be slower than the $O(n^3)$ algorithm until n is really large. And the constants could be very different. You could have an algorithm that takes $n$ years, and another that takes $n^3$ nanoseconds.
Just for fun, try to figure out for which n the O(n) algorithm is faster, and how long it runs when it runs faster. For example with n = 1,000,000 the first algorithm takes a million years, the second takes $10^{18}$ nanoseconds = $10^9$ seconds < 32 years.
PS. When you look closely at the definition of $O(f(n))$, it doesn't actually say that our function must be anywhere near f(n). For example, $n^{1/2} = O(n^3)$ according to the definition. You'll often see $\Theta(f(n))$ (big-Theta) which means your function isn't just less than c * f(n) but between c1 * f(n) and c2 * f(n). And there are situations where a function doesn't behave the same for all values. Say sometimes it's close to n^3, but at other values n it's much smaller. If f(n) cannot be replaced with a smaller function then we call it "asymptotic O(f(n))".
So you could have f(n) = n if n is even, 1 otherwise. And g(n) = 1 if n is even, n^3 otherwise. For even n, f(n) is larger, for odd n, g(n) is larger.


How can one find an element in a Merkle tree?

Merkle trees are not designed to support efficient lookup.  The best you can do is search the entire tree (all the leaves) and check each node for a match.  This is $O(n)$ time.

If you want to be able to efficiently look up an item in a Merkle tree, construct a separate "index": i.e., a separate hashtable (or binary search tree) storing the mapping from hash value to position in the tree.


Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

There is plenty of precedent for problems that are NP-hard (in worst-case complexity) but can often be done in practice on many instances that arise in practice (e.g., because their average-case complexity is low, or for other reasons).

NP-hardness relates to the worst-case complexity of a problem.  However, worst-case hardness isn't always representative of typical-case hardness.  Sometimes typical instances are much easier than the worst-case instances.  Therefore, NP-hardness results aren't always an indication that the problem can't be solved acceptably well in practice.

As Yuval Filmus explained so well in a comment:

  I'm not sure there is any better answer than the fact that the algorithms work on real-world instances. NP-hardness is a worst-case concept, and sometimes the worst case is simply irrelevant. It is a challenging problem to characterize which properties of real-world instances render the problem solvable. Smooth analysis is one answer, and there might be others in the non-rigorous literature.

I recommend you take a look at Dealing with intractability: NP-complete problems for an overview of common methods for dealing with NP-hardness: i.e., for figuring out ways to solve a problem good enough for practical purposes, when we know it is NP-hard.


Fastest way to check data against an envelope

From the short description you give, I infer that you consider that fetching the envelope data from disk is a bottleneck.

Even assuming that the envelope values change with every dataset (so that there is no reuse), you figure seems to show that there are as many data points as there are envelope points. So if you completely avoided the fetching of the envelope, you could at best hope for a threefold improvement, and virtually no improvement in case there is reuse.


Rechecking contiguous characters (as in run length encoding)

If a Run only retains characters and sizes in an array, it seems as though you only need to find the indices corresponding to changedOffset and changedOffset + changedLength, and then potentially change the sizes of the characters in the indices to the right and left by simple addition. That is, if you have an array of Runs:
$$[(x,1),(y,2),(a,2),(b,1),(c,1),(z,2),(x,1)]$$
for alterArray("ac_zz",3,4), it is first determined that the $a$ and $c$ are the beginning and ending characters (the $b$ is eliminated). This is done by simply adding: $1+2=3$ (from the $1x$ and $2y$) and $2+1+1=4$ (from the $2a,1b,$ and $1c$).

Then you check whether either side has to be combined: on the left side, the $y$ is not affected; on the right side, the $z$ is affected and so we add $2+2=4z$. The $x$'s are never checked.


It seems you have almost invented the carry-save adder.

You can use independent full adders for several layer, each time reducing 3 wires of equal weight to 1 wire of that weight and 1 for the next higher weight. Of course if there are 6 wires of the same weight, you can reduce them to 2 of the same weight and 2 of the next higher weight, and so on.

But the result of doing a bunch of that is not the sum, but two partial sums, one coming from all the S outputs of the last layer and one coming from all the C outputs. They still have to be added normally. You can use a ripple-carry adder or something faster/bigger there like a Kogge-Stone adder (which you'd only need once, compared to n-1 times if you just added up everything the obvious way).


Introduction to type theory for a beginner?

Why has no one proposed Benjamin Pierce's Types and Programming Languages? That is a good introduction to type theory. Bob (Robert) Harper's Practical Foundations of Programming Languages is also a pretty good one.

Both of them introduce type theory from a computing perspective. If you like math better, try Rob Nederpelt and Herman Geuvers' Type Theory and Formal Proof: An Introduction. I have not taken a look at Basic Simple Type Theory by J. Roger Hindley yet, but I figure it should be good given the author (judging from the table of contents though, it looks hard).


If a problem Q is NP complete, is another problem reducible to Q also NP complete?

Not necessarily. Any language in $\mathbf{P}$ is poly-time many-one reducible to any non-trivial language (i.e., all except $\varnothing$ or $\Sigma^\ast$); see here, for example. The latter language (i.e., the one you are reducing to) is, in this case, the $\mathbf{NP}$-complete $\mathcal{Q}$. For all we know, your language $\mathcal{P}$ could be any language in $\mathbf{P}$ and, therefore, not necessarily $\mathbf{NP}$-complete (even under the assumption $\mathbf{P} = \mathbf{NP}$).


Inventory planning problem solved through dynamic programming

CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

recursive top-down (p363),
memoized (p365f) and
bottom-up (p366).

I suggest you try to adapt one of these.


Prove that $L^r$ is context free without alphabet

Informally, by construction $L^r$ consists of the strings in $L$ reversed. Since $L$ is context-free, it has a Grammar in Chomsky normal form. All production rules in this grammar will fall in one of three classes:

$A \rightarrow BC$
$A \rightarrow a$
$S \rightarrow ε$

Thus by reversing the order of non-terminals in the RHS of all rules of category 1., a new grammar can be derived that produces $L^r$.

This new grammar is also in Chomsky normal form, thus $L^r$ is context-free.


Need help with this runtime of algorithm with double loops that results in 0

The result you state is clearly wrong, since the second line (for example) runs $n+1$ times. The problem is in your sum, which you don't explain how you got to.
Here is the code again, with line numbers:
1: for i in 0,...,n:
2:   j = 2*i
3:   while j ≤ n:
4:     j = j + 1
5:     print "hello world"
6:   end while
7: end for

The running time heavily depends on the model. However, assuming that $n \geq 0$, the running time will be proportional to the number of times that lines 2 and 4 are executed. Line 2 is executed $n+1$ times. As for line 4, for a given value of $i$, it is executed $\max(n-2i+1,0)$ times (for example, if $2i = n$ it is executed once). In total, it is executed this many times:
$$
\sum_{i=0}^n \max(n-2i+1,0).
$$
In order to calculate this sum, it will be easier to consider separately the cases $n$ even and $n$ odd. If $n = 2m$ then the maximal $i$ for which $n-2i+1>0$ is $m$. Furthermore, the summand goes from $n+1$ down to $1$ in jumps of $2$; there are $m+1=n/2+1$ summands in total. Therefore the sum equals
$$
1 + 3 + 5 + \cdots + (n + 1) = \frac{(n/2+1)(1+(n+1))}{2} = \frac{(n+2)^2}{4} = \Theta(n^2).
$$
If $n = 2m+1$ then the maximal $i$ for which $n-2i+1>0$ is also $m$. This time, the summand goes from $n+1$ down to $2$, and there are $m+1 = (n+1)/2$ summands. Therefore the sum equals
$$
2 + 4 + 6 + \cdots + (n+1) = \frac{((n+1)/2)(2+(n+1))}{2} = \frac{(n+1)(n+3)}{4} = \Theta(n^2).
$$
In total, we get that the number of times that line 4 is executed is $\Theta(n^2)$ in both cases, and so $\Theta(n^2)$ overall (this is a subtle point, and requires a short argument).
We conclude that the total running time is $\Theta(n^2)$. (This may need the assumption $n>0$, depending on your exact definition; you can take $\Theta(n^2+1)$ if you want to be extra sure.)


Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms (MIT Press, 3rd edition, 2009) is a good book for understanding and solving time complexity and correctness of
algorithms mathematically.


Counter example

Consider the array $A=[5,2,3,4,1]$, where $n=5$.

(i) Then $A[1]=5$ is the maximum and $x=1$, $A[5]=1$ is the minimum and $y=5$.

(ii) And find minimum in $A[1 .. x] = A[1 .. 1]=A[1]$ which is $5$. So, $u=1$.

(iii) Find maximum in $A[y..n] = A[5..5]= A[5]$ which is $1$. So, $v=5$.

(iv)  Answer is $$\max(A[x]-A[u]),(A[v]-A[y]) = \max(A[1]-A[1], A[5]- A[5])= \max(0,0)=0$$

But the maximum profit is $A[4] - A[2] = 2$.

$O(n)$ solution

The idea is to start with two pointers $i=1$ and $j=2$ and at each step increase $j$ by one. At each step check if the difference $A[j] - A[j]$ is greater than the maximum profit. If it is then update the maximum profit. But if $A[i] > A[j]$ (in which case $A[j] - A[j]$ is negative and max profit is not updated) then we make $i$ point to the same location $j$ points to, since if for some $k > j$, $A[k] - A[i]$ is greater than the current maximum profit then $A[k] - A[j] > A[k] - A[i] > maxprofit$.

Set $i=1$, $j=2$, $maxprofit=0$
If $A[j] - A[i] > maxprofit$ then set $maxprofit = A[j] - A[i]$
If $A[i] > A[j]$ then set $i = j$
$j = j + 1$
If $j>n$ return $maxprofit$
Goto 2


Dual problem of a maximization primal problem $P$?

As you mention, maximization and minimization problems are equivalent. Given a recipe for dualizing a minimization problem, you can convert it into a recipe for dualizing a maximization problem as follows:

Negate the objective function and change the maximum to a minimum.
Compute the dual.
Negate the objective function and change the maximum to a minimum.

The new dual problem will have the same objective value as the primal one (under some mild conditions). This property easily follows from the same fact for duals of minimization problems.

If you're careful enough, you should also get that dualizing twice brings you back to the original program.


Finding paths with smallest maximum edge weight

You're right; it's essentially a MST problem. First build the minimum spanning tree, then use breadth-first or depth-first search to find the unique path in the tree between the two vertices.


You can print numbers 1 to $x$ and print $y-1$ spaces between them in a brute force manner. The following algorithm does that:

function enumerate(string str, int s, int t, int y):
   /* base case: there is no space left and we print the string */
   if (y==0)
      string str2 = "";
      for i=s to t:
         str2.append(i);
       print str+str2;
       return ;

   /* recursive case: add one space and recursively call the function */
   for i=s to t:
      string str2 = "";
      for j=s to i-1:
         str2.append(j);
      str2.append("~");
      if (t-i >= y-1) call enumerate(str+str2, i, t, y-1);

You can call enumerate(str="", s=1, t=5, y=2) to print all combinations of numbers 1 to 5 and 2 spaces between them, which gives you a sorted embedding of numbers 1 to 5 in 3 boxes.


No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large.

If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.

Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.


I will assume the patch is the same position and is unchanged.  Given this, you could try a two-step procedure with basic image processing methods:
Step 0 (optional): Align/register the two images.
Step 1: Compute local image similarity, on a pixel-wise basis.
Step 2: Find a large connected region in that similarity map where there is high similarity.

For Step 1, one approach is local correlation, as you used.  You could also try normalized cross correlation if you think one image might be shifted slightly (e.g., by a subpixel amount).  Another is to compute the square of the pixelwise difference of the two images.  Yet another possibility: at coordinate $(x,y)$, extract a patch 7x7 patch from each image centered at $(x,y)$, compute some measure of image similarity (e.g., L2 distance, local correlation, you name it; possibly preceded by some image registration step) between those two patches, and use that as the similarity measure at $(x,y)$; do this for every coordinate.
For Step 2, you are looking for a large connected region with a high similarity score.  One approach is to threshold followed by connected components.  Another approach is a watershed transform.  Another approach  is to use image morphological operators (e.g., opening) followed by one of these methods.  More generally, you could look at methods for blob detection.
With image processing tasks like this, you may need to experiment with a bunch of different methods and see which ones work well.  When you experiment, I recommend that you implement, measure its effectiveness, also look at a random sample of 5-10 images and the results of the analysis on those images, and look at a random sample of 5-10 images that got handled incorrectly.  This visualization can be helpful in understanding in what situations a method fails, which can sometimes suggest improvements to address those particular situations.


This is a proprietary system so we have no way of knowing.

In general, you will find a lot of work and potential solutions by searching for text similarity or document similarity. For starters, you could have a look at the work of Islam and Inkpen [1] on short sentence similarity (it mentions plenty of other references you can widen your search to) or a more general survey of Gomaa and Fahmy [2].

If you are interested in libraries, NLTK might be helpful.

[1] Islam, Aminul, and Diana Inkpen. "Semantic text similarity using corpus-based word similarity and string similarity." ACM Transactions on Knowledge Discovery from Data (TKDD) 2.2 (2008): 1-25.

[2] Gomaa, Wael H., and Aly A. Fahmy. "A survey of text similarity approaches." International Journal of Computer Applications 68.13 (2013): 13-18.


Coin flipping problem on an $n \times m$ grid

This is just linear algebra. Let $x$ be the vector over $\mathbb{Z}_2$ representing the initial state of the board, and let $y$ be the goal state of the board. Let $v_i$ be the vectors corresponding to the allowed flips (flipping corresponds to adding some $v_i$). Then we want to check whether $x+y$ is in the span of the $v_i$.


I will assume the following definition for $\mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$: it is the class of languages decided by polytime non-deterministic Turing machines with oracle access to a language in $\Sigma_k^p \cap \Pi_k^p$. Consider now some $L \in \mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$ which is decided by some NP machine $M$ with oracle access to a language $K \in \Sigma_k^p \cap \Pi_k^p$.

Since $K \in \Sigma_k^p \cap \Pi_k^p$, there are $\Sigma_k^p$-witnesses to both $x \in K$ and $x \notin K$. Including all such witnesses, the NP machine $M$ becomes an absolute $\Sigma_k^p$ machine (we fold the first $\exists$ quantifier).

In more detail, we can write $L$ as $x \in L \leftrightarrow \exists |y|<|x|^C P(x,y)$ for some predicate $P$ which is polynomial time with oracle access to $K$. Since $P$ runs in polynomial time, it makes at most polynomially many queries to $O$. We construct a new predicate $P'$ which guesses the results $b_1,\ldots,b_T$ of these queries $q_1,\ldots,q_T$. Since $K \in \Sigma_k^p \cap \Pi_k^p$, if $b_i = T$ ($b_i = F$) then for some polytime $P_+$ ($P_-$) we have
$$\exists |w_{i,1}| < |x|^{C_1} \forall |w_{i,2}| < |x|^{C_2} \cdots Q |w_{i,k}| < |x|^{C_k} P_{\pm}(q_i,w_{i,1},\ldots,w_{i,k}).$$
By combining $P$ with the machines $P_+,P_-$ we can come up with a polytime predicate $P'$ such that
$$ x \in L \leftrightarrow \exists |y| < |x|^C \exists b_1,\ldots,b_T \exists |w_{1,1}|,\ldots,|w_{T,1}| < |x|^{C_1} \cdots Q |w_{1,k}|,\ldots,|w_{T,k}| < |x|^{C_k} \\ P'(x,y,\vec{b},\vec{w}). $$
Folding the first three existential quantifiers, we see that $L \in \Sigma^p_k$.


k-center algorithm in one-dimensional space

First,

  There exist optimal solutions in which each cluster consists of a contiguous sequence of points in the real line.

Any other optimal solutions can be transformed into the cases above. In the following, we focus on the optimal solutions of the kind above.

The complexity of the following "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

The case for $k=1$ is easy. Denote the optimal solution to $k=1$ in $n$ points by $R_{n,1}$.

Let $R(n,k)$ be the optimal solution for the problem of $k$-center in the first $n$ points. For convenience, define $R(n,k) = 0$ if $k \ge n$ (This is reasonable because we can choose each point as the center of the cluster consisting of only itself).

For general $k > 1$, we consider all the cases according to the number (denoted $m$) of points that are assigned to the last cluster (that is, the last cluster contains a contiguous sequence of the rightmost $m$ points).

$$R(n,k) = \min_{0 \le m \le n} \{ R(n-m, k-1) + R_{m,1} \}$$

The complexity of the "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

Note: This paper [1] gives an $O(n \log n)$ time algorithm.

[1] Efficient Algorithms for the One-Dimensional $k$-Center Problem. arXiv, 2014.


Convert a non-deterministic Turing machine into a deterministic Turing machine

The deterministic machine simulates all possible computations of a nondeterministic machine, basically in parallel. Whenever there are two choices, the deterministic machine spawns two computations. This proces is sometimes called dovetailing. The tape of the deterministic simulator contains a list of configurations of the nondeterministic one, and performs a step on each of these in turn. This requires quite some administration, and the capability to move aroud data when one of the simulated configurations extends its allotted space.


What to do following a reduce in LR(1) parsing?

It may help to think in terms of lookahead sets, rather than lookahead symbols. So the item set in state 4 is actually:
$$\left[ C \rightarrow d \cdot, \left\{ c, d \right\} \right]$$
According to the definition of a $LR(1)$ automaton, what you should do is look at the lookahead symbol. If it's $c$ or $d$, then reduce by $C \rightarrow d$, otherwise it's a parse error.
This is correct behaviour, and you would get full marks for this answer. However, it's not how $LR$ parser generators work in practice!
A grammar which is $LR(1)$ but not $LR(0)$ has a $LR(0)$ automaton which is correct. The problem is that it's nondeterministic. And, indeed, there are variants (e.g. $GLR$) which allow for nondeterministic automata.
What that means is that in practical applications, you don't need to consult the lookahead set if you don't need to in order to make a parsing decision.
In your case, state 4 does not need lookahead to disambiguate it. If you didn't bother looking at the lookahead set, and just reduced anyway, the parse error would be caught as soon as you tried to shift the next symbol, because there isn't a transition for it. Try parsing the string d$ to see what I mean.
Real-world grammars tend to produce $LR$ automata with a lot of these states where the only possible action is to reduce by a single production. So real-world parser generators tend to optimise them by not storing their lookahead sets. We call these $LR(0)$ reduce states.
In true $LR(k)$ parsing, you will often find $LR(0)$ reduce states which differ only in their lookahead sets:
$$\begin{eqnarray*}
q_1: & \,\, & \left[ A \rightarrow \alpha \cdot, \phi \right]\\
q_2: & & \left[ A \rightarrow \alpha \cdot, \psi \right]
\end{eqnarray*}$$
(Exercise: Why can this never happen in a $LALR(k)$ automaton?)
You can merge these states and the resulting automaton will still be correct, and will still be deterministic if the original automaton was deterministic.


For an instance of 3-COLOR, try to add a complete graph of size $k-3$, and add an edge between each new vertex and each old vertex. Now you can prove the new graph is $k$-colorable iff the old graph is 3-colorable.


Your question hints at multiple misconceptions which I'm going to address.

  If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

First, let's be clear about terminology.

variable vs literal -- the formula $a \lor b \land a$ has three literals but two variables.
model vs interpretation -- every logical formula has exactly one of two possible interpretations, true and false.

It would be correct to say: the number of models grows exponentially (with base 2) in the number of variables.

  So, is the time complexity of the SAT problem of propositional logic a $O(2^x)$?

No, that does not follow.

What is $x$? In complexity theory, we usually express complexity in the input length. So if $x$ is the number of literals, that thought makes sense; if it's the number of variables, it does not. However, in the worst cases (if we consider search space alone), the number of variables and literals is the same.
The number of possible models (e.g. valuations of the variables) alone is not trivially an upper bound on the complexity. The brute-force algorithm also has to evaluate the formula for every candidate, so you have to add a linear factor at least (depends on the computational model and cost model you use).
When somebody says, "the complexity is X" that implies a lower bound in addition to an upper bound. Your observation does not provide a lower bound, even after correction.

That is because the size of the search space does not correlate with solving complexity. Take sorting, for instance: finding the correct permutation has a search space of size $n!$ and yet we can solve the problem in linearithmic time. SSSPP is another common example.


For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can determine the possible XORs resulting from partitions of the array into four subsets, and so calculate the maximum sum. The resulting algorithm runs in linear time.


Circuit satisfiability problem : SAT-C to SAT-2C

You can use a reduction from $\text{3-SAT}$.

$\text{3-SAT}$ is the language of $\text{CNF}$ formulas where each clause has at most three literals, and they are satisfiable, meaning - given a formula $\phi$ in the correct form, it is in $\text{3-SAT}$ iff there exists $x$ for which $\phi(x)=1$.

Now, you want to show that the language of two circuits that calculate two different functions is $\text{NPC}$, therefore, given a formula $\phi$ which is satisfiable, you want to create a reduction that transform this formula into two circuits, that calculate different functions.

First, transforming a $\text{3CNF}$ formula into a circuit can be done in polynomial time. So - you can construct one circuit. You now need to think of the other circuit. As Yuval Filmus mentioned, think of a circuit of constant size. What circuit will guarantee that if $\phi$ is satsfiable, than that circuit will calculate a different function than $\phi$, but if $\phi$ is not satisfiable, it will calculate the same function exactly?

Most of the answer is given, you are only left to think of that circuit. If you want, ask in the comments and I'll edit it in.


Removing max number of edges while keeping minimum distances

Your graph has no negative edges, then you can do a full exploration using Dijkstra algorithm starting from node 1. You stop when you have explored all nodes. Just record every black edges you cross.

An important point is, when you have several equal distances on a step, always give priority to red edges.


How to calculate a direct mapped chace capacity with tag and valid bits?

Unless specified otherwise, addresses are always byte adresses (and with a cache with 1B/block, any other choice would not make sense)

Ram size is relevant as it indicates addresse width.

Cache blocs are 1 byte -> offset=0b (offset indicates byte position in block and only 1 possible position).

RAM is 2kB (2^11) -> address is 11 bits

Adress width=Tag with+Index width+Offset width

Tag=7b, Address=11b, Offset=0b -> index=4b

Cache is direct Mapped -> Cache size for data=number of blocks * block size = 2^(index size)*(Block size)

-> Cache Size (data) = 2^4*1B=16B

Block associated with Tag(7b) + 1 valid bit -> 1 extra B for control per block

Total cache size = 16 block each with 1B data and 1B control -> 32B


Can one quickly update CRC codes based on small change and previous CRC code?

Yes, this is possible.  The new CRC value can be computed very efficiently.

To see how, you need to know some math and about how CRCs can be viewed as polynomials.  The CRC checksum of the bit-string $c_0,\dots,c_n$ can be viewed as the value of $c(x) \bmod p(x)$, where $p(x)$ is the CRC polynomial and $c(x) = c_n x^n + \dots + c_0$ and all arithmetic is done modulo 2.  Let $r(x)$ denote the checksum, i.e., $c(x) \bmod p(x)$.  Now if you change the $i$th bit $c_i$ to $c'_i$, then the new checksum will be given by $c'(x) \pmod p(x)$ where we define the polynomial $c'(x) = c(x) - c_i x^i + c'_i x^i$.  The checksum will be $c'(x) \bmod p(x)$, which has the form

$$c'(x) \equiv c(x) - c_i x^i + c'_i x^i \equiv r(x) + (c'_i-c_i) x^i \pmod{p(x)}$$

Since we already know $r(x)$ (it's the checksum of the original file), all we need is to compute the value of $(c'_i-c_i) x^i \bmod p(x)$.  Naively, you might think this takes $O(i)$ time -- potentially slow.  But in fact this can be done very efficiently using fast modular exponentiation, so we compute $x^i \pmod p(x)$, then multiply by $c'_i-c_i$, and we get $(c'_i-c_i) x^i \bmod p(x)$.  Then we add that to the original checksum $r(x)$.  (All arithmetic is done modulo 2, so here "addition" really means xor.)  That gives us the new checksum for the modified file.

If the modification changes multiple bits, there is a natural extension of the move to show how to compute the updated checksum as well.


Closure of regularity under the action of replacing identical pairs of letters

You can do it using homeomorphism. Define $h:\Sigma\rightarrow \Sigma^*$ by: $h(\sigma)=\sigma\sigma$.
Then, $h$ induces a homeomorphism $g$ that is defined by $g(\sigma_1,\dots,\sigma_n)=h(\sigma_1)\dots h(\sigma_n)$.
Then, its easy to see that $shrink(L)=g^{-1}(L)$ (prove this!). From closure properties of regular languages we know that $g^{-1}(L)$ is regular, hence also $shrink(L)$.


Reduction from Exact Cover to Fixed Exact Cover

Add $n$ empty sets, and choose $K = n + 1$. Every solution for the original problem is (without loss of generality) of size between $1$ to $n$, so using the empty sets you can complete it to a solution of size exactly $K$.

If you're determined to have your collection duplicate-free, add $n$ new elements $y_1,\ldots,y_n$, and the following sets:
$$
\{y_1\},\{y_2\},\ldots,\{y_n\},\{y_1,y_2\},\{y_1,y_2,y_3\},\ldots,\{y_1,\ldots,y_n\}.
$$
There are exact covers of the new elements of any size from $1$ to $n$.


Hint 1. If the conjunctive "clauses" are trivially satisfiable, then any unsatisfiability must be due to the ordinary disjunctive clauses.

Hint 2. You don't have to change any of the clauses of the original CNF.


Search for maximal value smaller than V in an array composed of K linear functions

It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.

This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.

the subarray $A[0], A[1]$ with $C=A[1]-A[0]$.
the subarray $A[1], A[2]$ with $C=A[2]-A[1]$.
$\cdots$
the subarray $A[N-2], A[N-1]$ with $C=A[N-1]-A[N-2]$.

With $o(N)$ time preprocessing and $o(K)=o(N)$ time processing, an algorithm will not be able to even read some number in $A$ when $N$ is large enough. (In fact, most of the numbers in $A$.) So, for some queried value $q$, the algorithm will fail to recognize that $q+1$ appears in $A$.

(The explanation above could be made more rigorous, for example, using the formal method of adversary and a well-defined model of computation.)

It looks like the more interesting question to ask should be whether there is an algorithm with $o(N\log N)$ preprocessing and $o(K)$ per query. Or whether there is algorithm with $o(N)$ preprocessing and $o(K)$ per query given $K=o(N)$. That sounds like another question, anyway.


How polynomial interpolation of polynomial multiplication algorithm works?


Are degree and order the same thing when referring to a B-Tree

I don't think that degree of a tree is a standard term in either graph theory nor data structures. A degree is usually a property of a node/vertex of a graph, which denotes the number of its incident edges. For trees you sometimes consider only the edges to the children.

I suppose "B-tree with minimum degree of 2" means that every node has at least two children. In other words it is a lower bound for the number of children. On the other hand the order of a B-tree denotes the maximal node degree, and is therefore an upper bound.


algorithm for number of subsequences containing at most k numbers with no element repeated in each of the subsequence

You can solve this using dynamic programming. Let me show instead the solution using generating functions, which can also be implemented using dynamic programming.

Suppose that there are $m$ distinct values in the array, appearing $n_1,\ldots,n_m$ times. The generating function
$$ \prod_{i=1}^m (1+n_ix) $$
counts the number of subsequences with distinct values of size $k$, in the sense that this is the coefficient of $x^k$. For example, in your case $m = 3$ and $n_1=n_2=2,n_3=1$. Therefore the generating function is
$$
(1+2x)^2(1+x) =
(1+4x+4x^2)(1+x) =
1+5x+8x^2+4x^3.
$$


return all strings contains given string in suffix tree

Yes, you are right. You need to consume the symbols of $T$ and all occurrences of it shall be in the sub-tree below the position you stopped.

Since the edges are stored in lexicographical order, you can perform a Depth-first to print all the substrings of $S$ starting with $T$ in lexicographical order.

Using this example from Wikipedia

and assuming $T = A$, we would arrive at an internal node. Doing a DFS, we would have: $A\$$, $ANA\$$, $ANANA\$$.


Get count of longest zigzag sub-sequences

Extending the well-known dynamic programming algorithm for Longest Common Subsesequence, we have a poly-time algorithm for Longest Zig-zag Subsequence.

When DPing, just also add another parameter: $\mathrm{A}[\mathrm{i}][\mathrm{j}]$ is the length of the longest zig-zag sequence ending at position $i$ and it is increasing when it ends at $i$ if $j = 0$ and otherwise, decreasing when it ends at $i$ if $j = 1$. So, at a position $i$, you scan from $1$ to $i-1$ and update $\mathrm{A}[\mathrm{i}][\mathrm{0}]$ and $\mathrm{A}[\mathrm{i}][\mathrm{1}]$ gradually. Note that you need to make the $\mathrm{j}$-index alternate while updating.


How can I understand if reduction is Karp reduction?

Your reduction repeatedly calls a SAT oracle. Karp reductions only make one oracle call, and furthermore they must immediately return whatever the oracle returns (so it's like a "tail call"). So your reduction isn't a Karp reduction.

How to know if a reduction is a Karp reduction? Use the definition. A Karp reduction from a language $A$ to a language $B$ is a polytime function $f$ such that for all $x$ we have $x \in A$ iff $f(x) \in B$. If your reduction cannot be put in this form, it is not a Karp reduction.


Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$

You can expand the recurrence $T(n) = 4T(n/2) + n^2 \log n$ directly:
\begin{align}
T(n) &= n^2 \log n + 4T(n/2) \\ &=
n^2 \log n + 4(n/2)^2 \log(n/2) + 16T(n/4) \\ &=
n^2 \log n + 4(n/2)^2 \log(n/2) + 16(n/4)^2 \log(n/4) + 64T(n/8)
\end{align}
and so on. We can simplify the terms: they are $n^2 \log n$, $n^2 \log(n/2) = n^2 (\log n - 1)$, $n^2\log (n/4) = n^2(\log n - 2)$, and so on. Unrolling the recurrence all the way gives
\begin{align}
T(n) &= n^2 (\log n + \log (n/2) + \cdots + \log(n/(n/2)) + 4^{\log n}T(1) \\ &=
n^2 \sum_{k=1}^{\log n} k + n^2 T(1) \\ &=
\frac{1}{2} n^2 \log n(\log n - 1) + n^2 T(1) \\ &= \Theta(n^2\log^2 n).
\end{align}
This is also what the master theorem gives (case 2 in the Wikipedia version).


If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

Here is how to implement your solution. Let $A = \langle Q, q_0, F, \delta \rangle$ be a DFA for $L$. We will construct an NFA $A' = \langle Q', q'_0, F', \delta' \rangle$ as follows:

$Q' = \{q'_0\} \cup Q^3$. The state $(q_1,q_2,q_3)$ means that we have guessed that when $A$ finishes reading the first copy of $w$, it will be in state $q_1$; the first copy of $A$, started at $q_0$, is at state $q_2$; and the second copy of $A$, started at $q_1$, is at state $q_3$.
$F' = \{(q_1,q_1,q_2) : q_1 \in Q, q_2 \in F\}$. Thus we accept if the first copy of $A$ is in the guessed state, and the second copy of $A$ is at an accepting state.
$\delta'(q'_0,\epsilon) = \{(q,q_0,q) : q \in Q\}$. This initializes the simulation of the two copies of $A$.
$\delta'((q_1,q_2,q_3),a) = \{(q_1,\delta(q_2,a),\delta(q_3,a))\}$. This simulates both copies of $A$, while keeping the guessed state.

We leave the reader the formal proof that $L(A') = \sqrt{L(A)}$.

Here is another solution, which creates a DFA. We now run $|Q|$ copies of $A$ in parallel, starting at each state of $A$:

$Q' = Q^Q$.
$q'_0 = q \mapsto q$, the identity function.
$\delta'(f,a) = q \mapsto \delta(q,a)$.
$F' = \{ f \in Q' : f(f(q_0)) \in F \}$.

What is the meaning of the condition $f(f(q_0)) \in F$? After reading a word $w$, the automaton $A'$ is in a state $f$ given by $f(q) = \delta(q,w)$. Thus $f(f(q_0)) = \delta(\delta(q_0,w),w) = \delta(q_0,w^2)$.


Can we push and pop both at a single transition in a PDA?

(Previously a comment)

Depends on how you define PDAs. The definition I consider canonical certainly does allow you to exactly this: it is assumed that each transition pops the top-most symbol, and pushes an arbitrary string. To represent not changing the stack, you'd push the same symbol you just popped; to pop one symbol, you'd push the empty string; to put $w$ on top of the stack, you'd push $wa$ (where $a$ is the top-most symbol); and to replace $a$ with $b$, you'd push $b$.


Consensus algorithm for imperfect annotators

Technically speaking, you can't.  If you flip all of the oracle outputs, then it maintains the same level of agreement but reverses the ranking.
But this is probably a trivial case that's unimportant in practice.  Suppose we can assume that every oracle has accuracy that's at least 50%.  Then one approach would be to take all questions that are rated by at least three oracles, take the majority vote among all oracles that rated it, and then measure agreement with that majority.  I think that should give a correct ordering of the oracles, given enough data (i.e., in the limit, as the number of data points goes to infinity, it should converge to the correct ordering).
In practice you could consider using a more sophisticated model that captures both differences in the accuracy of each oracle and differences in the difficulty of each question.   I'm not sure whether this will lead to a major difference in outcomes significantly, but there is tons of work in the research literature you could read about to see what methods have been studied.  Here are some example papers:

Online crowdsourcing: rating annotators and obtaining cost-effective labels, Welinder et al.

Lean crowdsourcing: Combining humans and machines in an online system, Branson et al.

Get another label? improving data quality and data mining using multiple, noisy labelers, Sheng et al.

Max-Margin Majority Voting for Learning from Crowds, Tian et al.

Active visual recognition with expertise estimation in crowdsourcing, Long et al.

and probably many more - I'm not expert on this topic, so I have no idea whether these are the most important or useful papers, so I suggest doing a literature search of your own.


Define $h(k,x)$ as the maximal $\ell \leq k$ such that program $x$ halts on inputs $1,\ldots,\ell$ after at most $k$ steps. Clearly $h(k,x)$ is computable. Define $g(k,x) = -1/h(k,x)$. Clearly $g(k,x)$ is computable and monotone.

If $x$ computes a total function then $\lim_{k\to\infty} g(k,x) = 0$. Otherwise, if $s$ is the first input on which $x$ doesn't halt then $\lim_{k\to\infty} g(x,k) = -1/(s-1) < 0$.

Suppose now that some computable function $g'(k,x)$ satisfies $\lim_{k\to\infty} g(k,x) = \lim_{k\to\infty} g'(k,x)$ for all $x$, and $g'(k,x)$ eventually stabilizes for all $x$. Thus $x$ is total iff $\exists k.g'(k,x) = 0$, putting TOT in $\Sigma_1$. However, TOT is known to be $\Pi_2$-complete, and in particular doesn't belong to $\Sigma_1$.


Transforming the sorting problem into Dijkstra

What you want is to reduce sorting (or element uniqueness) to the single source shortest path problem (rather than to Dijkstra's particular algorithm!) using an $o(n\log n)$ time reduction whose output has size $O(n)$. Then you will get a tight decision tree lower bound in the algebraic decision tree model for constant degree (Dijkstra's algorithm can be implemented using a linear algebraic decision tree).

Such a reduction is probably not known. See for example D.W.'s question on cstheory.


Compact representation of paths in a graph

A Trie might do the trick: http://en.wikipedia.org/wiki/Trie

Label each edge of your graph with a letter.  Then add the strings which represent paths through your graph to the trie.  To fulfill the requirement that "no other paths apart from the selected ones are represented" you could leave all vertices of the trie blank, and label the edges, except when the edges leading from the root to the vertex represent one of your paths, then label the vertex with something.  A bool, the number of the path under some ordering, etc.

Once you have your trie built, there are algorithms for compressing it down to an optimal (or near optimal) representation.  (see the linked Wikipedia article.)


Prove NP-completeness of deciding whether there is an edge-tour of at most a given length

It is a standard variation of the Travelling Salesman Problem.

To force an edge to be a part of the answer, break it in half and insert a new vertex.

Update A reduction in the other direction consists of "breaking all vertices in two".

More precisely, given a directed graph $G$, form another graph $G'$. For each vertex $v$ in $G$, create a pair of vertices $v_i$, $v_o$ in $G'$. For each edge $(uv)$ in $G$, create an edge $(u_ov_i)$ in $G'$. Also, for each $v_i$, $v_o$ add an edge ($v_iv_o)$, and let it belong to $F$. Now every cycle in $G'$ that contains all edges in $F$ also contains all vertices, and corresponds to a Hamiltonian cycle in $G$.


Finding out if languages involving counting and modulo operations are regular

This is essentially @Yuval's hint, expressed in a slightly different way. You've said that you can prove
$$
L_u = \{0^n1^m\mid n, m \ge 0, n - m \equiv 0\pmod{3}\}
$$
is regular. If so, then its intersection with the regular language denoted by $00^*11^*$ will be regular. Show that this intersection is equal to
$$
L_r = \{0^n1^m\mid n, m > 0, n - m \equiv 0\pmod{3}\}
$$
and you're done. Notice that a similar construction shows that
$$
\{0^n1^m\mid n > k, m > j, n - m \equiv 0\pmod{3}\}
$$
is also regular for any $k, j > 0$.

The same idea can be used on your second question.


Why is the undecidability of the Halting Problem useful?

Detecting whether a Turing machine loops can be arbitrarily difficult.
For example, pick any problem P and consider the program:

k = 0
done = False
while not done:
  if <k encodes a solution to P>:
    k = 0
  elif <k encodes a solution to ¬P>:
    break
  else:
    k += 1

This program either terminates or runs forever with repeating configurations, but in order to tell whether configurations repeat, we need to know whether P has a solution. Now just insert a very difficult (undecidable) P.

A real computer has a bazillion configurations. That number is closer to infinity than to any number we can actually comprehend. Turing machines are a better mathematical model of real computers than finite state automata. Something similar happens in physics: the Earth is made from finitely many molecules, but physicists use differential equations that assume matter to be continuous and smooth. That is because the extremely large finite number of molecules is better approximated with the continuum than a discrete system with bazillion states.


How many inputs does the Hadamard gate have?

The $n$-ary Hadamard gate acts on $n$ qubits. The state of the $n$ qubits is a unit norm vector of dimension $2^n$. You can take as basis the vectors $|x\rangle$ for $x \in \{0,1\}^n$.

As it happens, the $n$-ary Hadamard gate can be simulated by $n$ unary Hadamard gates acting on the individual qubits, which is what you see on page 6-3. The reason is that the $n$-dimensional Hadamard transform is the tensor product of $n$ one-dimensional Hadamard transforms.

The usual convention in circuit complexity is that gates have bounded fan-in. Otherwise you can compute any function using a large gate!

Consider the case $n=1$:
$$
\begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\
\frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix} 1 \\ 0 \end{bmatrix} =
\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{bmatrix} \, .
$$
This is where $|1\rangle$ comes from.

The entire circuit involves initializing $n$ qubits at the state $|0\rangle$, applying $n$ unary Hadamard gates on the $n$ qubits, applying the black box function $f$, and then applying the Hadamard gates again on the $n$ qubits. The final state of the $i$th qubit turns out to be $|s_i\rangle$.


What's the difference between Adaptive Control and Hierarchical Reinforcement Learning?

The difference between the two tasks really comes down to the level of continuity assumed in the models of the problem.

In adaptive control, continuity is assumed at all levels; the problem space and the actions to be executed are all continuous.

In hierarchical reinforcement learning, although the problem space is continuous, the actions to execute upon the space are discrete.

A good analogy for this is the robot arm trying to move to a certain goal. Adaptive control would work with Jacobian to find a continuous solution to this problem. Reinforcement learning would select actions (up, down, left, right) to learn the problem space and find a solution.

Hierarchical reinforcement learning and adaptive control are really complements of each other. When the problem gets too complex to compute with Adaptive Control, hierarchical learning steps in to make it discrete and more scalable.

For another perspective, especially since my explanation breaks down when you consider continuous HRL (which does exist), consider this explanation from my personal correspondence with Daniel Rasumussan:

  Practically, there are many differences between how they [Adaptive Control and HRL in a continuous space] are
  implemented; they use different algorithms, different learning rules,
  different representations, etc.  For example, adaptive control is not
  typically hierarchical.  You could arguably call it a hierarchy with a
  depth of 1 (with e.g. the "high level" being control in the x,y space
  and "low level" being control in the motor space).  But there's no
  temporal abstraction in that hierarchy; the high level isn't trying to
  encapsulate low level decisions, the problem is how to find a nice
  reliable one-to-one mapping between those two spaces.  Of course you
  could make adaptive control hierarchical, as you can make pretty much
  anything hierarchical, but that isn't typically what they're
  interested in.  Perhaps a more critical difference is that in motor
  control typically it is assumed that the transition and reward
  functions are known to the agent.  There may be some unknown
  variability in the case of adaptive control, but by and large the
  agent has a pretty good idea what the effects of its actions will be,
  and what the goal is that it is trying to achieve.  It's one of the
  key principle of reinforcement learning that that information is not
  known, and must be figured out by the agent by exploring the
  environment.  Now again here, you could come up with a motor control
  problem where the agent doesn't assume that information is known, but
  that just isn't the kind of problem those techniques are designed for,
  in general.  So, to sum up, there certainly is a gradient between HRL
  and adaptive control, and by tweaking various assumptions you can
  bring them closer together or farther apart.  But just implementing
  continuous actions in HRL would still leave you quite a ways from
  adaptive control.

As for an example combination this, one might imagine using hierarchical reinforcement learning to play a video game like Pong and then changing the physics of the game (Pong on slippery ice!) so that Adaptive Control might step in.


Are there any known W[3] or W[3]-hard problems?

There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for your proof.
Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find anything concrete in a quick literature search. The closest thing I could find was  Separating sets of strings by finding matching patterns is almost always hard (2017) by Lancia et al., where they conjecture that the problem they call PATTERN IDENTIFICATION is W[3]-complete for a particular parameter, but this conjecture is probably not very useful for your proof. I do note that I'm not an expert in this field, so there may be some more recent results out there I simply wasn't able to find.


how does a harddisk work? block / sector

This is something that has changed over the decades.

In the past, the blocks were laid out exactly as you see in the picture.  The bit density of the outer blocks was less than those of the inner blocks.  This made the hardware easy to build at the expense of being less efficient.

In modern times, we no longer need to make the hardware easy.  We're interested in maximum efficiency of the harddrive.  Modern harddrives do not have nice easy angular wedges like the old ones do. They, instead, try to keep the bit density as even as possible (maximized at all places).


How to perform orthogonal check on two circular binary strings?

Say we have strings $a = a_0a_1...a_{n-1}$ and $b=b_0b_1...b_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a_0a_1...a_{n-1}a_0a_1...a_{n-2}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays).

Let's reinterpret them as polynomials in the following way.

For $a=a_0a_1...a_{2n-2}$ use value at position $i$ as the coefficient associated with power $i$ in a polynomial such that $P_a(x) = a_0x^0 + a_1x^1+...+a_{2n-2}x^{2n-2}$.

Now reverse $b$ and get the new string $b=b_{n-1}...b_1b_0$ and build a polynomial similarly as we did above. You get $P_b(x)=b_{n-1}x^0+...+b_1x^{n-2}+b_0x^{n-1}$.

Now let the magic happen. Multiply both polynomials into $P(x) = P_a(x) \cdot P_b(x)$ (Remember to do this fast). Wait, what ... where is the answer to the problem.

Let's see what is the $n-1$ coefficient of the new polynomial: $$P(x) = c_0x^0+c_1x^1+...+c_{3n-3}x^{3n-3}$$

Coefficient at position $n-1$ is equal to $$c_{n-1} = a_0 \cdot b_0 + a_1 \cdot b_1 + ... a_{n-1}\cdot b_{n-1}$$

Awesome, that is the dot product of original string $b$ with original string $a$ (without rotations). Keep looking at further terms of $P$. Coefficient at position $n$ is equal to $$c_{n} = a_1 \cdot b_0 + a_2 \cdot b_1 + ... + a_{n-1} \cdot b_{n-2} + a_{n} \cdot b_{n - 1}$$

But keep in mind that $a_n=a_0$ since this is just $a$ concatenated with itself. So we have the dot product of $a$ rotated one step to the left with $b$. You can see that terms of $c_{i}$ from $n - 1 \le i \le 2n - 1$ will give you the dot product of all rotations of $a$ with array $b$. Therefore, after computing $P$, you can find whether there is at least one dot product with value equals to $0$ easily.

In general polynomial multiplication is a useful representation to model convolutions of two arrays. It turns out that a lot problems can be modeled this way in areas such as: combinatoric, dynamic programming, string matching with least mismatches.

This is indeed relevant because there is a very efficient way to multiply polynomials which is via FFT in $O(n \log n)$ (or Karatsuba in $O(n^{\frac{3}{2}})$) instead of the naive $O(n^2)$ algorithm.


What is the machine epsilon and number of mantissa bits for TI-83?

the TI-83 does not use IEEE-754 floating point, but different floating point encoding scheme with 7 bytes of binary-coded decimal for the mantissa (that's 14 decimal digits).

Yes, and in order to deal with that, the program should take into account the base of 10:
1->E
While (1+E)>1
E/10->E
End
Disp 10*E

This results in $10^{-9}$, not $10^{-14}$ - though actually 14 digits would imply that $\epsilon = 10^{-13}$. There's still something missing to explain that result, and that thing is that the TI83+ sometimes rounds to 10 digits, for example for printing, but also for the purpose of comparisons. For the purpose of subtraction, that rounding is not performed. You can see the difference with a program like this, showing that there is more internal precision than 10 digits after all:
1->E
While (1+E)>1
E/10->E
End
10E->E
For(X,1,5
Disp 1+E-1
E/10->E
End

This program shows that evaluating $1+E-1$ for $E = 10^{-12}$ still does not yield zero, while for $E = 10^{-13}$ it does yield zero. We should be careful not to conclude that therefore $\epsilon = 10^{-12}$, it's more complicated. There seems to be a special rule the zeroes out small differences. That elusive 14th digit does exist though it's well hidden, for example this demo shows it:
1+8|E~13->X
Disp X*2-2

(this is SourceCoder syntax, |E is the small E made by pressing 2nd and ,, ~ is unary negation (-)).
This program doesn't print zero, so the 14th digit has to exist internally, even though the TI83+ tries very hard to deny it. Whether this means we should say that $\epsilon = 10^{-13}$ is not clear to me. $1 + 10^{-13}$ is technically different from $1$, but they compare equal and evaluating their difference yields zero.


Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?

You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.