Using random projections for locally sensitive hashing

$r \cdot v$ can be negative even if all elements of $v$ are positive: consider, e.g., $r = (2,-3)$ and $v=(1,1)$.  Then $r \cdot v = -1$.

Also, using random projections is not the same as defining a hash to be 1 if the dot-product is $\ge 0$ and 0 if it is $<0$.  You can still use a random projection without using that particular hash function.  I haven't looked at the sparselsh code, but it's also possible that it could be using a random projection but without using that specific hash function.


Quadratic equations using 2 different approaches

You can understand which, if either, solution is correct by substituting it back into the quadratic and seeing which one works.

As to why you get different answers, it's to do with the accuracy of floating point representations.  Roughly speaking, numbers are represented to some number of significant figures and this can cause problems when you add numbers with different orders of magnitude or subtract numbers that are approximately equal.  For example, evaluated left-to-right to one significant figure, $0.3+0.3+1 = 0.6+1 = 2$, whereas $1+0.3+0.3=1+0.3=1$.

This is a particular issue in the calculation of $b^2-4ac$ in your example, where $b=1000$ and $a=c=0.001$: the correct answer is $999\,999.999\,996$, which is very susceptible to even slight rounding errors. You then have to calculate the square-root of that, which gives a number very close to $1\,000$, and compute $1\,000$ minus that number.  All of these steps cause problems.

The concepts you need to read up on are loss of significance and numerical stability.


Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges

It's called Johnson's algorithm.

Instead of trying to keep track of the number of edges, it searches for a function $\delta:V\to \mathbb R$ so that for all edge $(v,v')$, $w(v,v')+\delta(v)-\delta(v')\ge 0$ and set that as the new weight $w'(e,e')$ of the edge $(e,e')$.

Then, for any path $p=v_1\cdot \dots\cdot v_n$ the $\delta$ values of all intermediate vertices cancel so that $w'(p)=w(p)+\delta(v_1)-\delta(v_n)$. And the shortest paths for $w$ and $w'$ therefore coincide.

Then remains the problem of finding such a $\delta$. The magic is that you can just add a new vertex $v_*$ and edges $(v_*,v)$ of weight $0$ for every vertex $v$, and then set $\delta (v)$ to be the weight of a shortest path $p_v$ from $v_*$ to $v$. Then the positiveness condition simply becomes $w(v,v')+w(p_v)-w(p_{v'})\ge 0$ which can be rewritten as $w(p_v)+w(v,v')\ge w(p_{v'})$ which is true because $p_v\cdot v'$ is a path from $v_*$ to $v'$ and $p_{v'}$ is a path from $v_*$ to $v'$ of minimal weight.


Prove that a model of infinite tapes is stronger then turing machine model

It is a standard proof that Turing machines with any finite number of tapes are equivalent to single-tape Turing machines, since you can code any fixed number of tapes on a single tape.

If you allow a Turing machine to have an infinite number of tapes, then you can decide any language $L$. To do this, first copy the input $x_1\dots x_\ell$ so that the $i$th tape contains the symbol $x_i$ in its first cell. Now move all the tape heads back to position $1$ and enter some special state $q_\mathrm{decide}$. Recall that the transition function decides what to do based on the state the machine is in at the moment, and what is under each of the infinitely many heads. So just define it to accept from state $q_{\mathrm{decide}}$ if there is some $k$ such that it sees $w_1, \dots, w_k$ under the first $k$ heads and $w_1\dots w_k\in L$, and every other head sees the blank character; otherwise, it rejects.

Note that there is a philosophical problems with write down the transition function if $L$ is undecidable, but the function certainly exists.


I've been doing competitive programming for several years at a very high level and haven't ever heard of a Chairman tree. Though I still can tell you how to make any data structure persistent. In case of BSTs and segment trees it even doesn't increase the running time (asymptotically, of course; you can notice some slowdown in practice).

First, let's consider a basic segment tree. I'll write C++-ish code because such trees, when made persistent, are most conveniently interpreted with pointers. For sake of simplicity I'll describe a (rather stupid) tree with two simple operations: assign a number to a position $i$ and get a number on a position $i$.

struct node {
    int l, r;
    node *L, *R;
    int value;

    void put(int i, int x) {
        if (l == r) value = x;
        else if (i <= L->r) L->put(i, value);
        else R->put(i, value);
    }

    void get(int i) {
        if (l == r) return x;
        else if (i <= L->r) return L->get(i);
        else return R->get(i);
    }
}

For those who are not familiar with notation (though it should be clear from the code): a node represents a segment $[l, r]$ of an array. When $l = r$ the node is a single element, else it has two children, $L$ and $R$, having ranges, respectively, $[l, (l+r)/2]$ and $[(l+r)/2+1, r]$.

When you put a value to a tree, you modify it. But we may notice that each modification touches only $O(\log n)$ nodes of a tree, so instead of modifying existing nodes we may copy them and apply updates only to the new vertex.

Here is the outline: whenever the function wants to modify a node, it makes a copy, modifies a copy and returns the copy back to the caller (because the caller wants to update himself too). In this example only put must be modified, and here we go:

node* put(int i, int x) {
    node *t = this->makeCopy();

    if (l == r) t->value = x;
    else if (i <= L->r) t->L = t->L->put(i, value);
    else t->R = t->R->put(i, value);

    return t;
}

Voi-la! Now we have got a fully-functional persistent array which takes $O(\log n)$ time and space per operation. You only have to store pointers to the roots of versions you need, and as long as the pointer is saved, it will stay untouched. Forever.

The very same technique may be applied to any kind of a segment tree, giving no overhead in time (because segment tree queries are already $O(\log n)$. More, you can use this approach with BST's. The most reasonable choice of a structure to make persistent is a Treap, mostly because it does not require storing pointers to parents. It might be hard to understand which values exactly one should clone while splitting and merging, but it is done in several minutes with pencil and paper.

Now a bonus and a tiny warning. First, you can make any data structure persistent: just implement it using persistent arrays :) If the structure itself is not tree-ish, this will cost you a logarithmic increase in time, of course. Second, this technique cannot be applied to any DS which running time is amortized, so be careful with persistent splay tree.

Hope this helps, and don't hesitate to ask something in comments!


semaphore implementation with test and set

The purpose of the spinlock is to prevent other cores from entering the critical section. The purpose of disabling interrupts is to prevent this core from re-entering the critical section.

The only way this core could try to re-acquire the semaphore is if an interrupt occurs and the interrupt handler needs the semaphore for some reason. Disabling interrupts prevents this from occurring.

As for the reason why sleep() is called after releasing the spinlock but before interrupts are enabled... well, that depends too much on the specifics of the operating system design to give a general answer.

The whole of the "waiting on the semaphore" operation should be atomic. That includes waiting on its queue and transitioning the thread from its "running" state to its "waiting" state. Presumably, that's what the call to sleep() is supposed to do.

You wonder if there's a possible race condition where this CPU releases the spinlock on the semaphore, then some other CPU signals the semaphore, then this cpu calls sleep(). That isn't necessarily a problem. If sleep() is written such that if it finds that the current thread is runnable it handles that case correctly, it won't cause a problem.

So why are interrupts disabled when you call sleep()? Some kernels are just designed that way, in that interrupts need to be disabled when you call into the scheduler. The call to sleep() may not actually "sleep"; it might just be whatever the scheduler has to do to make a thread sleep.

Alternatively, if there is a thread context switch hidden deep inside that call to sleep(), that may be where interrupts are re-enabled.

Ultimately, this code is designed to get the general idea across. How you would implement it in a real kernel would be like this, but this isn't necessarily drop-in code.

(Consider that load-linked/store-conditional instructions are spelled out in the example but there's no memory barrier operation on the spinlock release. That's a very specific ISA!)


Are their problems that we can not even approximate efficiently?

Are there any natural problems for which this is not the case?

Consider the scheduling jobs with deadlines on a single machine problem. I cannot say anything about its average time but this problem has no $\rho$-approximation unless $P=NP$.

Suppose that there are $n$ jobs to be scheduled on a single machine, where the machine
processes at most one job at a time. Suppose also each job $J_i$ has

release time $r_i  \geq 0$
deadline (due time) $d_i$

Define the delay by $D_i = t_i - d_i$ if the job $J_i$ finishes at $t_i$. So, we are interested in the minimization of the maximum delay, i.e.,

$$\text{minimize: } \max\{D_i\}, i=1,\dots,n$$

Now assume we have $\rho$-approximation algorithm for this problem. This means that our algorithm would find a solution which is not more than $\rho OPT$ (where $OPT$ is the optimal value). If for any problem instance with the optimal value equal to $0$ our approximation algorithm would find the solution at most $\rho 0 = 0$ in (polynomial time) and this would imply $P=NP$.


Find nth number which does not contain the digit c

Let's do it in base 3.
Here are the first 8 numbers without 2 (left column) and the first 8 numbers without 1 (right column), with zero padding:
000    000
001    002
010    020
011    022
100    200
101    202
110    220
111    222

Hopefully you can take it from here.


Calculating the average waiting time of tasks

From the two options, the first is the (only) reasonable approach. The second one is absolutely useless; details follow:

If you are trying to minimize the waiting time of the tasks that were shifted, then the best algorithm simply reschedules no tasks at all. The total time of transferred tasks is zero and, thus, optimal. Even if you require at least one task to be transferred, the best algorithm then simply picks the one with the least running time and transfers it to the least loaded queue. In both cases it could hardly be said the algorithm does something useful.
If you are trying to maximize the waiting time of the tasks which were rescheduled, then consider the algorithm which permutates all tasks between the devices. This naturally maximizes said measure and, again, hardly qualifies as a sensible load balancing algorithm.


Having a verifier for a language in general is known as semidecidability, which is actually weaker than decidability. So in general, the answer is no, we can't build a decider for $L$.
But if the verifier is efficient (i.e., $L \in $ NP), then indeed $L$ is decidable, and your argument is pretty close for why that is.
Let's say we have an efficient verifier $V(x,c)$.
Given an $x \in \Sigma^*$, the "certificate space" is $C=\{c \in \Sigma^* \mid |c| \leq p_L(|x|)\}$, where $p_L$ is a polynomial. That means the certificate space is actually finite. $x \in L$ if and only if there exists a $c \in C$ such that $V(x,c)$ accepts. So indeed we can just check every possible certificate for a given input $x$ to construct a decider for $L$.
In fact with a bit more work you can show that $L \in$ EXP, meaning $L$ is decidable in exponential time.


Are all computational complexity results oracle results?

The issue you are highlighting is that of computation model, which is how we measure the resource consumption of an algorithm. The computation model specifies how to assign time complexity, space complexity, and so on to a given program (whose syntax it also specifies). There are three popular computation models:

Turing machines, of various sorts.
Boolean circuits.
RAM machines, of various variants.

A variant of the RAM machine can be specified in terms of the allowable basic operations, which is the issue that you encountered. For Boolean circuits, the analog is the set of allowable gates, and for Turing machines there seems to be no such analog.

In contrast, here is an actual example of how oracles are used in theoretical computer science.

A submodular function is a set function $f\colon 2^U \to \mathbb{R}$ (i.e., a function that accepts a subset of $U$ as input, and returns a real output) that satisfies a technical constraint known as submodularity.

Submodular optimization is the field which studies how to optimize submodular functions relative to various constraints (including no constraints).

A typical problem is:

  Given a submodular function, find its minimum.

How is the submodular function "given" to us? It could be given to us as a truth table (i.e., the value of $f(A)$ for any $A \subseteq U$), but this is not a realtistic assumption. Rather, there is often an efficient algorithm that computes $f$. In most cases we are interested in an algorithm which is oblivious to the exact algorithm used to compute $f$. In these cases, we are looking for an algorithm which has oracle access to $f$, that is, the function $f$ is provided as an input oracle.

(In other cases we would like to use the code for $f$. This happens usually when $f$ has a particular structure, for example if it is a coverage function. In cryptography we sometimes want to "open the black box" even when $f$ has no particular structure.)


Determine page number and offsets for address references

I think Page numbers will be given by first 5 bits and last 10 bits will give the offset. With the first 5 bit first you locate which page no. you want to go and then remaining 10 bits will tell you the offset at that page taking you at the exact location


The reference bit stays at 1, it is set to 0 only in two circumstances, when the page is read from disk, or when the algorithm gives a page a second chance.


Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers

Assuming f(0) and f(1) are integers, find which powers of two and of five are factors of f(0) and f(1). The powers in f(n) can be calculated like a Fibonacci sequence and the number of trailing zeroes is the smaller of both sequences.

The Fibonacci series is defined by $fib(0)=0$, $fib(1)=1$, and for $n≥2$ we have $fib(n) = fib(n-2)+fib(n-1)$, so the series starts (0, 1, 1, 2, 3, 5, 8, 13 ...). If we start with different values and use the same recursion formula, we get for example the sequence (1, 0, 1, 1, 2, 3, 5, 8, 13...). If we define $fib(-1)=1$, then the n-th element of this sequence equals $fib(n-1)$.

The sequence starting with (x, y) and the same recursion formula (x, y, x+y, x+2y, 2x + 3y ...) equals $x \cdot fib(n-1) + y \cdot fib (n)$.

Let $f(0)$ have the factor $2^x$ and $f(1)$ the factor $2^y$ and no higher power of two, then $f(n)$ has the factor $2^z$, where $z = x \cdot fib(n-1) + y \cdot fib (n)$.

Likewise, let $f(0)$ have the factor $5^a$ and $f(1)$ the factor $5^b$ and no higher power of five, then $f(n)$ has the factor $5^c$, where $c = a \cdot fib(n-1) + b \cdot fib (n)$.

The number of trailing zeroes in $f(n)$ is

    $min(z_n, c_n)$ where

    $z_n = x \cdot fib(n-1) + y \cdot fib (n)$
    $c_n = a \cdot fib(n-1) + b \cdot fib (n)$


Relationship between Coloring a graph and its complement

Sorry, this is false:

For example, take $G$ as a size-$10$ independent set. It has a $1$-coloring, or even a $3$-coloring... its complement is a clique, which admits neither a $9$- nor $7$-coloring.


Label groups of vertices in a graph in an efficient manner without BFS/DFS

As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).


Are turing machines and formal languages the same mathematical object?

No, they are not the same thing. A language is a set of words over some finite alphabet. A Turing machine is a 7-tuple as defined in the Wikipedia.

For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.

This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.


Finding minimum spanning tree with O(|V|)

Use DFS to find a cycle in the graph (in linear time). Save the maximum-weight edge while performing DFS, Delete it from the outputted cycle.
Repeat 11 times.
Done.


Sub-exponential for Subset Sum on the total bit length of the input

This doesn't violate the exponential time hypothesis.  The exponential time hypothesis says that k-SAT takes exponential time, i.e., $\Omega(2^{cn})$ for some constant $c>0$.  So if you found a $O(2^{\sqrt{n}})$ time algorithm for k-SAT, that would violate the exponential time hypothesis -- but a a $O(2^{\sqrt{n}})$ time algorithm for subset sum does not violate the hypothesis.


Modal logic axiom S4, transitive and reflexive frame, tableaux solver

To find a descriptive answer to this post, please see my thesis which presents background information of various modal logics including S4. It also contains detailed implementations of the algorithms used along with implementations in python.

I have also proved that NPSpace problems such as S4 or K4 are terminating in finite time without infinite looping. Here is the link to full report -> Link to the pdf file located on my website. I would recommend reading it fully and following the research papers which were used to make sure full knowledge is transferred onto you :).

Please note that this was a research project which I have now finished. Nevertheless, if anyone wants to expand on my work or would like me to get involved on similiar topic, please get in touch in any way possible.


Using induction to prove transition states are the same

We use induction on the length of $w$. Let this length be denoted by $|w|$

Base case: $|w|$ = 1

Immediate by the assumption that $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$

Induction hypothesis: $δ^*(s_0,w)=δ^*(s_f,w)$ for $|w| = k$ where $k \geq 1$

Inductive step: Assuming the induction hypothesis, prove that it works for $k+1$:

Let $w$ be a word s.t $|w| = k+1$. Clearly $w$ can be seen as two strings $w = w^{-1} \circ v$ where $\circ$ is concatenation of strings.

As $|w^{-1}| = k$ we, by induction, get that $δ^*(s_0,w^{-1})=δ^*(s_f,w^{-1})$. As $x$ is a string of length $1$ we get by $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$ that $δ^*(s_0,w)=δ^*(s_f,w)$

The proof could be a bit more formal, but atleast the intuition should be clear.


Huffman encoding: why is there no need for a separator?

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword.  For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10.

This means that you can decode greedily by reading the encoded string from left to right and outputting a character as soon as you've seen a codeword.  For example, 0, 00 and 000 don't code anything so you keep reading bits.  When you read 0000, that encodes "E" and, because the code is prefix-free, you know there's no other codeword 0000x, so you can now output "E" and start to read the next codeword. Again, 1 doesn't encode anything but 10 encodes "e".  No other codewords begins with "10", so you can output "e".  And so on.


Why does a suffix tree have a linear number of nodes (relative to input string size)?

For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).

I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less interior nodes than leaves an therefore the tree has size $O(n)$.

Notice that in the uncompressed version (edge labels a characters) with a large alphabet, you can have super-linear suffix trees. For example, consider the text abcdefghijk....


Proof that POSITIVE-3-SAT is in the complexity class P

It looks like you misunderstood a bit what you should prove since you missed the much easier way to prove although your (trivial) proof looks correct.

An easier proof

Let us call a boolean formula in conjunctive normal form in which all clauses consist of exactly 3 literals and in which no variable appears negative a positive‑3 formula. So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable positive-3 formula}\}.$$

Note that any positive‑3 formula is satisfiable since it becomes TRUE if a truth value of TRUE is assigned to all variables.  So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a positive-3 formula}\}.$$

Here is an algorithm $\mathcal A$. Given an input string $s$, $\mathcal A$ just verifies whether $s$ is the encoded form of a positive-3 formula. If $s$ is, $\mathcal A$ returns yes; otherwise, $\mathcal A$ returns no. That verification step can be done in linear time in terms of the number of clauses in $s$. So $\text{POSITIVE-3-SAT}$ is in P.

The moral of the above proof is that you can use whatever known to you to construct the algorithm. All you need is to specify an algorithm and show that it works as wanted.

It depends on the requirement/convention/stage of your course or the intention of your course instructor whether you needs to explain in detail why that verification can be done in linear time or polynomial time. It looks like that verification step is totally ignored by the proof in the question, which is, in fact, a general accepted practice in the field.


Is potential causality relation equals to set of consistent happens before relations?

The book says "A potential causality diagram is equivalent to the set of happened before diagrams that are consistent with it."  (emphasis added)

You seem to have interpreted that as "A potential causality diagram is equal to the union of happened before diagrams that are consistent with it."  But that's not the same statement.  I would suspect that this might be the cause of your confusion.  Go back to the original statement and disregard the idea of taking the union, and see if you can make sense of the original statement.

Perhaps there is additional explanation or context after that sentence.

If not, perhaps the book is claiming there is a bijection between (a causality diagram C) and (the set of happens-before relations that are consistent with C).  That claim sounds accurate.  To construct the inverse map: given such a set of happens-before relations, take the smallest element in the set, and that's C.


Which goes first stl or data structures and algorithms?

I think STL (assuming you mean C++ standard template library) is something you sort of learn as you use it. Exposure to DSA (data structures and algorithms) is essential for solving new problems or progressing in CS. Since you are just starting out and partial to C++, any DSA textbook in C++ will be a good reference. Just try to Google search “Data Structures and Algorithms C++,” maybe with your preferred file type.


Find an undecidable language that is mapping-reducible to its complement

Try the following construction. Given a language $L$, use
$$ \{0x : x \notin L\} \cup \{1x : x \in L\}. $$


Prove that every maximal flow yields the same minimal cut

Here are some hints.  Instead of trying to prove the contrapositive, try proving the statement directly.  If $f_1 \ne f_2$, then that means that there is some edge $e$ where $f_1$ sends a different amount of flow down than $f_2$ does.  What does that imply about the residual graph for $f_1$, vs the residual graph for $f_2$?  Those two residual graphs must differ in some specific way: how?  What does that difference imply for $S_1$ vs $S_2$?  Try writing out some small examples, with small graphs, where you draw the flows, residual graphs, and cuts explicitly.  What do you find?

I suggest you spend a bit more quality time on your own, trying a bit harder to solve it yourself.  This is your exercise; you need to solve it yourself.  And you need to put in a bit more effort to explore this problem.  Don't give up easily -- you can do it!


Is it possible to write a program that calculates an algorithm's time complexity?

Yes, you are right. There is no program that can calculate all algorithms' time complexity.

More formally speaking, there is no Turing machine which, given any Turing machine $T$ and an input of length $n$, it can calculate a finite upper bound for the computation time that will be used by $T$ and that input in case that computation does halt, or infinity in case that computation does not halt. The reason is simple, as you have mentioned, there is no Turing machine that can decide whether an arbitrarily computation will run forever or not in the first place. In fact, we cannot algorithmically tell even whether a given Turing machine halts on the empty input.

Notice that a trivial time complexity of all algorithms is an upper bound of running forever for any input. There are also trivial lower bounds such as whether the computation will run for less than for 7 steps. Those trivial time complexities have to be excluded from our discussion so as to keep our discussion interesting.

We can ask refined questions. For example, does an arbitrary Turing machine run in time $O(1)$? It turns out this question is undecidable as well.

For more information, you may want to read Verifying Time Complexity of
Turing Machines by David Gajser.


This may be a question that's too broad to cover here.
The WAM covers a lot of Prolog-specific capabilities (e.g. unification, nondeterminism, the cut) that other abstract machines do not, and its design is also quite subtle in its details (e.g. garbage collection on backtracking is designed into the machine). There is a reason why the WAM Book is 130 pages long: it is complicated and hard to understand!
Still, the WAM Book is the best explanation that I'm aware of, and there may be no substitute for going through that, working through the exercises, hand-compiling small examples of your own, and possibly even implementing parts of the WAM in a suitable language.
I'm going to suggest that you try with it again, and ask specific questions here if you get stuck on something.
But if that doesn't sound like something that you want to do right now, you may want to go through a less complicated abstract machine first, such as the SECD machine. The WAM was, after all, influenced by abstract machines that came before it, and that is assumed knowledge.


The approach is to build a fully persistent version of the rope data structure.  This then lets you keep a pointer to each version of the data structure: you have a pointer to version 1 ("hello world") and version 2 ("hello").  To undo the last operation, you just start working from version 1 rather than version 2.  In particular, yes, you can store these pointers in a stack data structure. The point is that each modification creates what is effectively a new copy of the data structure, without modifying the old version.  Of course, actually making an entire copy would be inefficient, so what the data structure does is share the parts of the tree that are unchanged.

For details on how to make a persistent version of the data structure, see What classes of data structures can be made persistent?.  See also Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration.


Clarifying "operation" in the definition of data type

It sounds like you might be asking about an abstract data type.  If so, the answer is the third option: "an identifier with signature and established behaviour".

If you are asking about a data type, then I'm not sure there's a clear answer that applies to all type systems and all programming languages.  Syntactically, I think it falls closest to your second option: "an identifier with signature" -- the type checker doesn't know anything about the intended behavior.  However, in practice programmers might associate other things with a type: for instance, the type might indicate the intended meaning of the data, it might indicate the intended behavior of the operations, it might indicate how the data is represented or stored, and it might even encode other distinctions -- though many of these might not be checked by the compiler's type checking or might not be visible to the compiler.


What does actually reasonable mean when we say "reasonable model of computation"?

It doesn't have a precise meaning. What an author considers "reasonable" largely depends on the context. It is usually meant to exclude certain pathological cases.


You can prove by induction that it always holds that $z \leq 0$, and so $z \neq 1$ and $z < y$. This allows the following simplification:

Input: $i$
$x,y,z,w \gets 1,1,0,0$
Repeat:

$z \gets z-1$

If $x = y$ then $w \gets w+1$ and $y \gets 1$; Else $y \gets y+1$

$x \gets 8w$

Until $w = i$
Return $z$

The running time is proportional to the number of iterations of the loop (which also happens to be the negation of the output).

In the first iteration we have $x=y$ and so set $w\gets 1$, $x\gets 8$, $y\gets 1$. Eight iterations later, we have $x=y=8$ (at the beginning of the iteration), and so we set $w\gets 2$, $x\gets 16$, $y\gets 1$. Sixteen iterations later, we have $x=y=16$, and so we set $w\gets 3$, $x\gets 24$, $y\gets 1$.

In total, we see that the number of iterations is
$$
1 + 8(1 + \cdots + (i-1)) = 1 + 8\frac{i(i-1)}{2} = 4i(i-1)+1 = (2i-1)^2.
$$
This shows that the output is $-(2i-1)^2$, and that the running time is $\Theta(i^2)$.


How do I find running time for the following divide and conquer problem?

You cannot use the Master Theorem to solve this recurrence, since $n!$ doesn't grow like $n^c$ for any $c$. Instead, Stirling's approximation shows that $n! \sim \sqrt{2\pi n} (n/e)^n$. Rather, expand the recurrence to get
$$
T(n) = n! + 16 (n/4)! + 16^2 (n/16)! + \cdots.
$$
Stirling's approximation shows that the latter terms are tiny compared to the first one. Therefore
$$
T(n) \sim n!.
$$
This is just shorthand for
$$
\lim_{n \to \infty} \frac{T(n)}{n!} = 1.
$$

If you want to prove this formally, one way is as follows. Start with the observation that $n/16 \geq 4$,
$$
16 (n/4)! \leq (n/4+1)(n/4)! = (n/4+1)! \leq \frac{1}{n} n!.
$$
The first inequality uses $n \geq 60$, and the second $n \geq 4$. Continuing in this vain, for $n/16^2 \geq 4$,
$$
16^2 (n/16)! \leq \frac{1}{n/4} (n/4)! \leq \frac{1}{n/4} \frac{1}{n} n! \leq \frac{1}{n} n!.
$$
In the same way we show that $16^k (n/4^k) \leq n!/n$ for $n/4^k \geq 4$. Therefore
$$
T(n) = n! + 16(n/4)! + 16^2(n/4^2)! + \cdots \leq n! + n!/n + n!/n + \cdots + 16^r T(4),
$$
where $n/4^r = 4$, and so $r = \log_4 n - 1$, which implies $16^r = n^2/16$. Since there are $r-1 = \log_4 n - 2$ summands of the form $n!/n$, we certainly have
$$
T(n) \leq n! + \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2.
$$
This shows that $T(n) = n! + f(n)$, where
$$
f(n) = \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2
$$
is a function satisfying
$$
\lim_{n \to \infty} \frac{f(n)}{n!} = 0.
$$
On the other hand, clearly $T(n) \geq n!$. This implies what we claimed above, $T(n) \sim n!$.


general question amortized cost and worst case

The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition.

Consider a data structure supporting operations $O_1,\ldots,O_m$. These operations have amortized cost $T_i$ (where $T_i$ could depend on parameters) if the total cost of a sequence of operations run immediately after initializing the data structure consisting of $c_i$ many operations of type $O_i$ is at most
$$ c_1 O_1 + \cdots + c_m O_m. $$
This bound only works if we consider all operations done on the data structure since initialization.

In your case, you are only considering one part of the operations performed on the data structure, and so amortized cost doesn't apply.


Perturbing a Markov chain to be closer to a target stationary distribution

You could use gradient descent.  It is possible to compute the gradient of the objective function $\varphi(A)$ in terms of $A$, i.e., the derivative of the objective function with respect to each entry of the matrix $A$. Then you could apply gradient descent.

In particular, let $\varphi(A) = \|A-A_0\|_F + \|\pi(A) - \pi_0\|_2$ denote your objective function.  Applying gradient descent to this objective function requires us to be able to compute $\nabla \varphi(A)$, i.e., the derivative ${\partial \over \partial A_{ij}} \varphi(A)$ of the objective function with respect to each individual entry $A_{ij}$ of the matrix $A$.  Let me explain how to do that.

One approach is to approximate the gradient numerically, i.e., to compute the gradient $\nabla \varphi(A)$, perturb each element of $A$ by a small amount of measure how much $\varphi(A)$ changes.  This might be fast enough if the matrix dimensions are sufficiently small, and it has the benefit of being easy to code.  However, it will scale poorly in practice for large matrices, as we need to compute $n^2$ perturbations for each gradient, and each perturbation requires computing the stationary distribution of a perturbed matrix, which naively takes $O(n^3)$ time, for a total of $O(n^5)$ time per gradient.  Thus each iteration of gradient descent will take $O(n^5)$ time, and you need to do many iterations of gradient descent, so this might take a while.  (You can speed this up by computing the stationary distribution of the perturbed matrix  using a few iterations of the power method, initialized with the stationary distribution of $A$; this takes $O(n^2)$ time; but it's still $O(n^4)$ time per iteration of gradient descent.)

A better way is to find an explicit, symbolic formula for the gradient $\nabla \varphi(A)$, and then use that with gradient descent.  That is possible but it gets messy, so I'll explain the details below.

It remains to handle the constraint that $A$ must be stochastic.  There are multiple ways to do that:

One way is to use projected gradient descent: in each iteration you update $A$ in the direction indicated by the gradient, then project the resulting matrix to the nearest stochastic matrix ($A' = A - \gamma \nabla \varphi(A)$, then let $A''$ be the stochastic matrix nearest to $A'$ and replace $A$ with $A''$).
Another way is to adjust the objective function, letting $\varphi'(A) = \varphi(A) + c \cdot p(A)$ where $p(A)$ is a penalty term that measures how badly $A$ fails to be stochastic (a simple choice might be $p(A) = \sum_i |(\sum_j A_{ij}) - 1|^2 + \sum_{i,j} \min(a,0)^2$), then choose $c$ sufficiently large and apply gradient descent to minimize $\varphi'(A)$.  For instance, you could perform several rounds of gradient descent, where the solution from the previous round is the initial value for next round, and where you double $c$ after each round.

There may be other ways as well.

OK.   That's an overview of the approach that I am proposing.  On to explaining how to compute the gradient symbolically, as promised.

An explicit formula for the gradient

We can write the objective function in the form $\varphi(A) = \varphi_1(A) + \varphi_2(A)$ where $\varphi_1(A) = \|A-A_0\|_F$ and $\varphi_2(A) = \|\pi(A) - \pi_0\|_2$.  It's easy to compute $\nabla \varphi_1(A)$; it is simply

$$\nabla \varphi_1(A) = {1 \over \|A-A_0\|_F} (A - A_0).$$

Computing $\nabla \varphi_2(A)$ is more difficult, as this requires us to compute the gradient of the stationary distribution $\pi(A)$ as a function of $A$.  Since the stationary distribution $\pi(A)$ is the principal eigenvector of $A$ (when it is unique), this reduces to computing the gradient of the principal eigenvector of $A$ as a function of $A$, for which there are techniques available.  In particular, we have

$$\nabla \varphi_2(A) = {1 \over \|\pi(A) - \pi_0|_2} \sum_k (\pi_k(A) - {\pi_0}_k) \; \nabla \pi_k(A),$$

and we need to find an expression for $\nabla \pi_k(A)$, where $\pi_k(A) = \pi(A)_k$ is the $k$th element of $\pi(A)$, and $\nabla \pi_k(A)$ is the gradient of that with respect to the entries of $A$.

Fortunately, there are nice formulas for how to compute the gradient of the eigenvector of a matrix.  In particular,

$$\nabla \pi_k(A) = (\text{Id} - A^\top)^\dagger b_k \pi(A)^\top,$$

where $b_k$ is the $k$th basis vector (1 in the $k$th entry and 0 elsewhere), and $\dagger$ indicates the Moore-Penrose pseudo inverse.  (Here I have used that the stationary distribution $\pi(A)$ is the eigenvector that corresponds to eigenvalue 1.)  Plugging in, we find that

$$\nabla \varphi_2(A) = {1 \over \|\pi(A) - \pi_0|_2} (\pi(A) - \pi_0)^\top (\text{Id} - A^\top)^\dagger \pi(A)^\top.$$

This then gives a symbolic expression for $\nabla \varphi(A) = \nabla \varphi_1(A) + \nabla \varphi_2(A)$.


Cook-Levin theorem proof's requirement of $\phi_{cell}$

We are building a reduction from problem Q (some problem in NP) to SAT.  To do that, we construct a function $f$ that maps an instance of Q to an instance of SAT.  In other words, if $w$ is an instance of Q, then $f(w)$ is a formula in CNF form.  (Recall that SAT is a decision problem whose instances are CNF formulas.)  Let's call that formula $\varphi$.  We'll remember that $\varphi$ depends on $w$.

What is the formula $\varphi$?  A formula is something that takes any assignment $x$ and assigns a truth value to it, namely $\varphi(x)$.  The way the reduction works, we interpret $x$ as a tableau, and $\varphi$ is defined so that $\varphi(x)$ will be true if $x$ is a valid tableau for the input $w$ (a valid computation of a non-deterministic Turing machine for problem $Q$ when run on input $w$).

So, $f(w)$ is not the tableau itself.  $f(w)$ is a formula that accepts valid tableaus.

Then, once we have defined $f$ (i.e., $\varphi$), we prove the following property: $\varphi$ will have a satisfying assignment if and only if $w$ is a yes-instance for problem Q.

For this to work out, the formula needs to include terms that ensure that any satisfying assignment to $\varphi$ is a valid tableau.  If you left that part out, you wouldn't be able to prove the property mentioned above, so $f$ wouldn't be a correct reduction.


What is the period of N xored identical random number generators, with differing seeds?

I will assume the N random generators have independent seeds and states.  Suppose their periods are $t_1,\dots,t_N$.  Then the period of their xor is a divisor of $\operatorname{lcm}(t_1,\dots,t_N)$.  Typically, it will be exactly $\operatorname{lcm}(t_1,\dots,t_N)$, but I don't know whether that is guaranteed in all cases.

If all $N$ generators have the same period $t$, then the period of their xor is a divisor of $t$ (and thus cannot be any larger than $t$).


Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

Hint: find a recurrence $f(n, k)$ that tells you in how many different ways you can sum to $k$ using the first $n$ integers (ignoring order and using numbers at most once). Then the answer to your problem is $\frac 1 2 f(n, n(n+1)/4)$.

The trick is to realize that the sum of $P$, is $S= \displaystyle \sum_{k=1}^n = \frac{1}{2}n(n+1)$, and that if you partition a set in two with equal sums, both halves must sum to $\frac{1}{2}P$. After counting the number of ways to sum to $\frac{1}{2}P$ we must still divide by two due to order, as for example the partition $(\{3\}, \{1, 2\})$ is the same as $(\{1, 2\}, \{3\})$.


An algorithm to maximize the number of parallel tasks

From your initial DAG $G(E, V)$ You start reversing all edges to build a new DAG $G'(E, V')$. Then do a BFS from $i$ in $G'$ to remove any unneeded tasks (unreached nodes in the BFS). This step is $O(N)$ with $N = |V'|$, the number of edges.

From $G$, build the number of requirements of each task ($R(V)$) and at the same time the list $L$ of the tasks with no requirements. this takes $O(N)$.

Then you iterate on this pseudo-algorithm:

while(root is not executed)
    L' = empty list
    for v in L
        for each node v' with an edge in G' from v to v'
             R(v') -= 1
             if R(v') == O then add v' to L'
    execute all L in a parrallel step
    L = L'

this is $O(N)$.


You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic.

Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$.

You take it from here.


In RegExr, why is regex OR in JavaScript sometimes not commutative?

It is not a bug; it is rather the JavaScript RegEx engine tries to match as much of the first of the two expressions combined by the "|" operator as it can. Thus, instead of matching a word like "bbb" with as many "b"s as possible, it matches the pattern a* against the empty word (implicitly) at the beginning of "bbb". Granted, the RegExr interface does not highlight this properly, but that is more of a missing feature than a bug.

As mentioned in the comments, you should also be aware the engine tries to find (possibly) strings in the input text which match the pattern specified by the regex; the matches are what are highlighted by the RegExr interface. This is a different use of regexes than in formal language theory, in which regexes are used to specify formal languages, and in which an input (word) as a whole either matches the regex or not.

Caveat: If you are trying regexes verbatim from a formal languages class, you may run into trouble when trying to specify the empty word; the character ε is not interpreted as the empty word but as the Greek lowercase epsilon character instead. This question on SE contains some ways of correctly specifying (only) the empty word.

Warning number 2: If you write L(a*|b*) verbatim for your expression there, it is interpreted as a capital $L$ followed by the pattern (a*|b*), not as the language corresponding to the pattern (a*|b*)!


You understood it correctly, but have interpreted it differently than the book wanted it to be interpreted. You are right that $9n$ grows faster than $n$ so the main problem in your book may be trying to express a mathematical definition of $O$ with too few words.

The definition
The function $f(n)$ is in $O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and a positive real number $c$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$.

Now it is clearer how $9n$ is in $O(n)$. Because there exist, say $c=10$ and $n_0=0$ such that $9n \leq c \cdot n$ for all $n \geq n_0$.

Why compare so loosely?
The problem is, if we would compare growth rates by exact function values, then two very similar functions may not end up in the same class. For example, with your "strict-O notation"; for any function $d > 0$, $f+d$ would not be in the same class as $f$, and that is not very useful. So, we have to draw the line somewhere (pun intended). Also, we use asymptotic analysis for describing algorithm complexity dependant on the input size $n$, and it is often not possible to calculate computation steps that precise.

Other notations
But, there are other asymptotic notations except big-O so you might want to look at those. You will find that $\Theta$ is, for example, more restrictive than $O$.


What's a good algorithm for deleting multiple elements in a heap?

I think you're optimizing for the wrong metrics.  The total running time will be $\Theta(n)$ no matter what you do.  Scanning the entire array to identify which elements to remove will take $\Theta(n)$ time, so your total running time can't be any better than $\Theta(n)$.  Conversely, there is a simple algorithm that achieves $\Theta(n)$ time.  MakeHeap can be done in $\Theta(n)$ time, so it gives you a simple $\Theta(n)$ running time algorithm: scan the entire array, delete whatever you want to delete, then run MakeHeap.

However, if you're trying to optimize the amount of work per deletion and for some reason the time taken to scan the array "doesn't count" (I don't understand why it wouldn't count, but let's just run with it):

In this case there is an alternative algorithm.  Deleting a single element from a heap can be done in $O(\lg n)$ time.  So, if you want to delete $k$ items, delete each one-by-one.  Total running time: $\Theta(n)$ to scan the array, $\Theta(k \lg n)$ to delete them.


Are there problem instances which we know to be unsolvable?

Every problem with a finite number of inputs is computable.

Proof: Suppose that the inputs are $i_1,\ldots,i_n$ and that the desired outputs are $o_1,\ldots,o_n$. Then the following program solves the problem:

If the input is $i_1$, output $o_1$.
If the input is $i_2$, output $o_2$.
...
If the input is $i_{n-1}$, output $o_{n-1}$.
Output $o_n$.


Why discriminate the base case allows me to complete the induction proof?

You want to prove that if the result of of filter test l is a non-empty list, then its first element passes test. You're using induction on l.
The base case for the induction is the empty list []. For the base case, you need to prove that if filter test [] = x :: lf then test x = true. In order to prove this, you assume that filter test [] = x :: lf, and prove that this hypothesis is a contradiction. Indeed it is: there is no value of x and lf that makes filter test [] = x :: lf true, because filter test [] is the empty list. So, for the base case, for any x and any lf, the proposition filter test l = x :: lf -> test x = true is true.
Using the notation you've used to state the principle of induction, P(n) has the form “Q(n) implies R(n)” (where Q(n) is “the result of filter is a non-empty list” and R(n) is “the first element passes the test”). It would be strange if P(0) was vacuously true, but that's not what's going on here: what's going on is that R(0) is vacuously true, because Q(0) is impossible. The base case P(0) is possible. It happens to have the form of an implication where the premise is impossible, but that's just happenstance.


Graph partition that maximize the number of triangles within its parts

I don't know whether there are any good heuristics, but I can suggest one approach: you could try to use an ILP solver on this task.  Introduce zero-or-one variables $x_{i,v}$, $y_{i,u,v,w}$, where $x_{i,v}=1$ means that vertex $v$ is contained in partition $P_i$, and $y_{i,u,v,w}=1$ means that $u,v,w$ are a 3-clique in $P_i$.  (Only introduce variables $y_{i,u,v,w}$ for triples of vertices $u,v,w$ that are a 3-clique in the original graph $G$; all others are effectively hardcoded at 0.)  You can add constraints
$$y_{i,u,v,w} \ge x_{i,u} + x_{i,v} + x_{i,w} - 2,$$
$$y_{i,u,v,w} \le x_{i,u}, y_{i,u,v,w} \le x_{i,v}, y_{i,u,v,w} \le x_{i,w},$$
$$\sum_v x_{i,v} \le M, \sum_i x_{i,v}=1.$$
Then, maximize the objective function $\sum_{i,u,v,w} y_{i,u,v,w}$ subject to these constraints, using an off-the-shelf ILP solver.


Difference between IO threads and worker threads

I don't know NodeJs or .NET, and they would be off-topic here anyway, but the underlying concepts are common among programming frameworks and programming models, so I'll answer in general terms.

The word thread can mean several things.

There is the conceptual meaning: one thing happening after another.
There is the way this conceptual meaning is represented in a programming language. In almost all programming languages, most ways to combine program fragments lead to those fragments being executed one after the other, thus in a single thread, e.g. a; b is a very common syntax for “execute a then b”. A few keywords, operators or library functions allow code to be executed in a way other than in sequence, e.g. fork in Unix or Async in .NET. These create conceptual threads.
There are ways to implement this concept at the operating system level. These fall mainly in two categories (refinements are possible but I won't get into those):

Kernel threads are managed by the OS kernel. The threads live independently. If one thread in a program is blocked on an IO call, that doesn't affect the other threads.
User threads (also called green threads) are managed by the program. From the perspective of the kernel, there is a single thread, so if the program blocks on an IO call, none of its threads can run. To allow non-blocked threads to keep running, the programming library must ensure that it makes only non-blocking system calls (it may expose blocking functions in the programming interface, however).

There isn't always a direct match between programming language threads and operating system threads. There are several potential reasons for such a mismatch:

The language was designed with a certain model in mind, but it's implemented on an operating system which doesn't have primitives that map directly to that model.
The language induces programmers to use threads a lot, but kernel threads are somewhat expensive. So many programming language threads are executed in the same kernel thread. Instead of using blocking IO, the library functions uses non-blocking IO exclusively, and calls a function such as select or poll which returns as soon as one pending I/O is unblocked.
I don't know NodeJS, but “able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete” sounds to me like this is what's happening.
The language discourages programmers from explicitly using threads, possibly because threads with shared memory is extremely hard to get right (the potential for race conditions is huge). Instead, it favors higher-level abstractions where parallel threads are mostly independent. Under the hood, those abstractions may be implemented with operating system threads.
I don't know .NET, but async/await sounds to me like it's implementing a rendezvous abstraction. The async keyword creates a thread which lives its own life until await joins it with its parent.


Let's fix the following definition for $L(M)$: it's the set of strings $x$ such that $M$ halts on input $x$.

Given machines $M_1,M_2$, consider a machine $M$ which accepts two inputs $x$ and $t$ and runs the following algorithm:

Run $M_1$ on input $x$ for $t$ steps.
If $M_1$ halted: run $M_2$ on $x$.
Otherwise:

Run $M_2$ on input $x$ for $t$ steps.
If $M_2$ halted: run $M_1$ on $x$.
Otherwise: halt.

The machine $M$ rejects an input $x,t$ iff one of the machines $M_1,M_2$ accepts $x$ within $t$ steps and the other one rejects $x$. So $M$ accepts all inputs iff $L(M_1) = L(M_2)$.


ACTL is the universal fragment of CTL.
Thus, existential path quantification is not allowed.
So a path formula is of the form $AF\psi$,  $AG\psi$, or $AX\psi$ (or a conjunction or disjunction of path formulas).

Moreover, you are not allowed a general NOT operator, but rather negations have to be on the atomic propositions (otherwise this fragment would be equal to CTL).


If you normalize your histograms you then have an empirical pmf. There are numerous methods to calculate distances of pmfs, such as Kullback-Leibler and Jensen-Shannon divergences. If the base-set of the histograms are exactly the same then KL divergence will work fine. If they intersect, but are not exactly the same, then JS divergence will work instead.

Be careful as KL divergence is non-symmetric. That is, given two pmfs $P$ and $Q$, $\text{D}_{\text{KL}}(P||Q)$ may not be equal to $\text{D}_{\text{KL}}(Q||P)$. On the other hand $\text{D}_{\text{JS}}$ is symmetric, but still not a metric.


A framework to capture common variation of sequence alignments

Despite the different uses of the algoritms, and the various names, I personally would say this is a single algorithm, with different variations. To make this answer more readable, I will add some details.

The basic algoritm global alignment (aka Needleman-Wunsch, below left) compares two strings $x=x_1\dots x_m$ and $y = y_1 \dots y_n$ (with match/mismatch score $\sigma$ between letters and negative gap cost $g$ between letter and missing letter). It is computed using an array $A$ and the recursion $$A[i,j] = \max \left\{\begin{array}{lll}A[i,j-1]&+&g\\A[i-1,j-1]&+&\sigma(x_i,y_j)\\A[i-1,j]&+&g\end{array}\right.$$
The starting values along the borders of the matrix are $A[i,0]=i\cdot g$ and $A[0,j]=j\cdot g$.

The value of the alignment is found in the last cell of the computation, and the alignment itself can be found by tracing back how this maximum value is obtained.

For local alignment (aka Smith-Waterman, below right) we need not a complete match but only the optimal value of matches between substrings of $x$ and $y$. That can be obtained by considering only part of the 'full' computation, ignoring any prefix or suffix with a negative value. This requires two changes. First any negative value obtained by the basic recursion is set to $0$, and also we look for a maximum inside the matrix (not the last cell). As any negative values are set to $0$ this effects the boundary values in the same way: they are set to $0$.

The three variants of semi-global alignment you mention (including overlap and fitting alignment) are somewhat in the middle of these two, as they carefully select which prefixes and suffixes do not count towards cost. They each follow the basic recursion (allowing negative values). Such alignments follow a path from one border of the matrix to another one. Starting at a left or top border means ignoring prefixes, and setting the corresponding border to $0$. Ending at a right or bottom border (i.e. choosing the maximum value at that side) corresponds to ignoring that suffix.

The two pictures below represent overlap and containment/fitting.


Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$

Since Master theorem is in terms of fractions of $n$ in the recurrence, and you have a fractional power of $n$ in the recurrence, try to convert between powers and multiplications. Taking $\log$ or $\exp$ of something usually helps with that.

Let $x=\log n$, $F(x)=T(\exp x)$. Then you have this recurrence:

$F(x)=T(\exp(\log n))=T(n)=2T(\sqrt n)+O(1)=2T(\exp (\frac{1}{2}\log(n)))+O(1)=2F(\frac{x}{2})+O(1)$

Then apply Master theorem to $F(x)$ and get $F(x)=O(x)$.

Therefore $T(n)=F(\log n)=O(\log n)$.


O(m+n) Algorithm for Linear Interpolation

You only need to perform binary search for the first element and then iterate simultaneously through the data points and query points.

Pseudocode

interpolated = []
find x[i] such that x[i] <= q[0] <= x[i+1] with binary search

for q in qs:
    while not x[i] <= q <= x[i+1]:
        i++
    t = (q - x[i]) / (x[i+1] - x[i])
    interpolated.append(y[i] * (1-t) + y[i+1] * t)


Constructing languages in NPI other than through Ladner's Theorem

It is perfectly possible that the intersection of an infinite decidable sparse set and an NP-complete set lies in P. Take your favorite NP-complete set $L$, and consider $L' = 0L \cup 1^*$, which is still NP-complete. The intersection of $L'$ with the infinite decidable sparse set $1^*$ is $1^*$, which is certainly in P.

Mahaney's theorem shows that sparse sets cannot be NP-complete, but to construct an NPI language you will need to show that your sparse set is not in P, which will probably require diagonalization. Your diagonalization will somehow have to ensure that the resulting language is sparse, while still being in NP and outside of P. Perhaps this can be done, but I'm not aware of any such proof. (That said, my knowledge of the relevant literature is sparse.)


Yes, anything that has constant input could be done in $O(1)$. Howether if the coordinates have size more than $O(1)$ than you will not be able to even read them in time.
That depends on your representation of the graph and what operations do you count. If you assume that you read the whole graph in some way and then find the needed degree, the complexity will be $O(|V| + |E|)$ if your representation is an edge list, $O(|V|^2)$ if it is an adjacency matrix. If you assume that you already have some representation of the graph in memory you can find the degree in $O(|V|)$ if you have the adjacency matrix.
You can do it in $O(|V| + |E|)$, start with an empty graph (all the degrees are zero) and add the edges one by one. When you add an edge to the graph only two vertices change their degrees.
No, consider the graph $K_4$ (complete graph on $4$ vertices). All the degrees in it are odd so it does not have even en Euler path.
If you want to read the coordinates it takes $O(n)$ operations, so no.


How to determine valid handle for given bottom up parser?

A handle is a production whose right-hand side can be reduced at a specific moment during a parse. (Or, as it is usually presented, it is the production which has been expanded at a specific point in a derivation for a sentence.) Although a handle is almost always defined as a production, it's common to talk about them as though they were just the right-hand side. That's clearly not correct because you cannot reduce a handle without knowing what it will reduce to, but in many contexts (including multiple-choice exams) it's possible to get away with this informality.

So I'd disagree that $B∗(id)$ is a handle, because it is not the right-hand side of any production. That doesn't really alter your question about whether $id$ is a handle.

A production (or its right-hand side) could be a handle for a grammar if there exists a derivation which involves that production. That is not necessarily the case for every production in a grammar, since grammars can include unreachable and useless productions. However, the grammar you present does not include any such productions. There exist derivations which use each of the productions, including $B\to id$ and $C\to (id)$. On that basis, I agree that both (A) and (C) are correct answers.


I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ensure that each variable and its negation get different values. The edge from each variable to R ensures that there are only two possible colors that can be assigned to x, one of which means true and one of which meand false.

Hope this helps!


Polynomial-time reduction of Primality and 3-SAT

For the first question: This is an open problem. If $\mathsf{P} \neq \mathsf{NP}$ then the answer is no: the decision version of 3-SAT is $\mathsf{NP}$-Complete, while Primality is in $\mathsf{P}$, the means that a Karp reduction from 3-SAT to Primality would imply $\mathsf{P}=\mathsf{NP}$.

For the second question:
Primality is in $\mathsf{P} \subseteq \mathsf{NP}$, therefore there is a Karp reduction from Primality to any $\mathsf{NP}$-Complete problem, such as 3-SAT.


Quicksort $T(n)_{best}=\Omega(n\log n) $ proof

You mentioned the quicksort recursion:
$$
T_{best}(n) = \min_i [T_{best}(i-1) + T_{best}(n-i) + n].
$$
Note how in this recursion $(i-1) + (n-i) = n-1$. This is because the two subproblems don't involve the pivot. This is the case for any node in the recursion tree: if a node corresponds to an array of length $m$, then its two children correspond to arrays of lengths $m_1,m_2$ where $m_1 + m_2 = m-1$. In particular, if a certain level has $x$ nodes then the sum of lengths at that level $S$ and the sum of lengths at the next level $T$ satisfies $S = T + x$; the $x$ pivots disappear from the recursion.

Denote by $N_i$ the number of nodes at depth $i$, and by $S_i$ the sum of lengths at depth $i$. Assuming we start counting at level 0, we have $S_0 = n$, $S_{i+1} = S_i - N_i$, and $N_i \leq 2^i$. You can prove by induction that
$$
 S_i \geq n - (2^i-1).
$$
In particular, $S_{\log_2 n} \geq 1$ (assuming $n$ is a power of 2), so there are at least $\log_2 n$ levels of recursion. Furthermore,
$$
\sum_{i=0}^{\log_2 n} S_i \geq \sum_{i=0}^{\log_2 n} (n+1-2^i) = (n+1)\log_2 n - (2n-1) = \Omega(n\log n).
$$
Since $\sum_{i=0}^\infty S_i$ is exactly the running time of quicksort (up to constants), we see that quicksort always takes at least $\Omega(n\log n)$.


A pumping lemma for deterministic context-free languages?

There is a Pumping Lemma specifically for DCFL, under the title "A Pumping Lemma for Deterministic Context-Free Languages", by Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016/0020-0190(89)90108-7. With this explicit title I must apologize that I missed it!
The online copy unfortunately has a blank spot in one of the formula, so I hope I reconstructed the result properly. Below ${}^{(1)}y$ is the first symbol of $y$ (when it exists) or $\varepsilon$ (if $y=\varepsilon$).
Lemma 1 (Pumping Lemma). Let $L$ be a DCFL. Then there exists a constant $C$ for $L$ such that for any pair of words $w,w'\in $ if
(1) $w=xy$ [?] and $w'=xz$, $|x|>C$ and
(2) ${}^{(1)}y = {}^{(1)}z $, [?]
then either (3) or (4) is true:
(3) there is a factorization $x=x_1x_2x_3x_4x_5$, $|x_2x_4|\ge 1$ and $|x_2x_3x_4|\le C$, such that for all $i\ge 0$ $x_1x^i_2x_3x^i_4x_5y$ and $x_1x^i_2x_3x^i_4x_5z$  are in $L$;
(4) there exist factorizations $x=x_1x_2x_3$, $y=y_1y_2y_3$ and $z=z_1z_2z_3$,  $|x_2|\ge 1$ and $|x_2x_3|\le C$, such that for all $i\ge 0$ $x_1x^i_2x_3y_1y^i_2y_3$ and $x_1x^i_2x_3z_1z^i_2z_3$ are in $L$.
Two applications of the Lemma are given: $\{ a^ib^i \mid i\ge 0 \} \cup \{ a^ib^{2i}  \mid i\ge 0 \}$ as well as $\{ w\in\{a,b\}^* \mid w=uv, |u|=|v|, \mbox{ and } v \mbox{ contains an } a \}$ are not DCFL.
The proof uses the fact that each DCFL has an LR(1) grammar in Greibach normal form.


How to simulate a bidirectional TM on a regular one with time factor four?

In the book you mentioned above you simulate a infinitely long bidirectional TM increasing the number of symbols and by "“folding” it in an arbitrary location". Thus each cell in the unidirectional TM will represent 2 symbols or a pair. So this can be x/(symbol or blank), x/y or (symbol or blank)/x. Now T(n) is the worst case scenario. Let us assume that the current state of the TM is as follows

^ symbol for blank.

e/h|l/^|l/^|o/^|!/^|?/^  (this is equivalent to h|e|l|l|o|!|? in a bidirectional TM, basically bend on the first position itself). with head pointing to ?/^, now if I want to write to the position I have to write as a pair. But I cannot read the second symbol in the pair without iterating to the left most position and then to the right again. So from the head position ?/^ we have to iterate 6 times to the left and 5 times to the right to read "^". Once we read "^" we have to return, so iterate back so 6 times to the left and then 5 times to the right. Now that we know the second symbol in the pair, we can write the new symbol for ex . "u/^". In a more generalized sense to write something in a Tape in the above state we have iterate the length of the tape(n) 4 times. So it will take 4 times more time to halt on a regular TM in the worst case, so t(n) = 4t'(n).


An example is the word $aabbab$.

We can either create it like this
$$S \rightarrow aT \rightarrow aaTT \rightarrow
 aabST \rightarrow aabbRT \rightarrow aabbaT \rightarrow aabbab.$$
Or like this
$$S \rightarrow aT \rightarrow aaTT \rightarrow
aabT \rightarrow aabbS \rightarrow aabbaT \rightarrow aabbab.$$


What is meant by Category theory doesn't yet know how to deal with higher-order functions?

The issue with higher-order functions is simple enough to state.

A type-constructor like $T(X) = [X \to X]$ is not a functor.  It should have been.
A polymorphic function like ${\it twice}_X : T(X) \to T(X) = \lambda f.\, f \circ f$ is not a natural transformation.  It should have been.

If you read Eilenberg and MacLane's original category theory paper, (PDF) the intuitions they present cover those cases.  But their theory doesn't.  Theirs was a great paper for 1945!  But, today, we need more.

The reaction of category theorists to these issues is a bit perplexing.  They act as if higher-order operations form a Computer Science idea; they are of no consequence to mathematics.  If that is so, then a foundation of mathematics would not be good enough for a foundation of computer science.

But I don't seriously believe that.  I believe that higher-order functions would be quite important for mathematics as well.  But they have not been seriously explored.  I am hopeful that, some day, they will be explored and the limitations of category theory will be realized.


You don't need to put all numbers encountered in the heap. Never let your heap grow in size more than $k$. Keep a min heap. Now, if at some point of time heap has size $ < k$, then push the number encountered ( say $i$ ) into the heap. If heap is full and the number $i$ is greater than top element of heap ( say $top$ ) , pop the $top$ and insert $i$ into heap. At the end all the numbers in the heap are your desired $k$ numbers. Each operation takes $O(logk)$ steps ( as heap size is always $ \le k$ ). And there are $n$ steps so $O(nlogk)$.


A state in a DFA always needs to have exactly one transition per symbol in the alphabet. I have understood from a few of my classmates that some teachers omit the error-state. I however prefer to show the error-state in graphs, since it simplifies verification of determinism in a graph.

In a NFA there can be no such rule. Therefore it should work to not present a transition for the symbol (0) in this case. If the NFA would be determinized, this non existing transition, along with all other non-looping transitions would point to a error state.


What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.


What is a proper way of solving a multibody nonlinear problem?

OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty efficiently.

Thanks for everyone who gave me suggestions and guidance to the right path!

Have fun (mixed with a lot of frustrations) with modeling!


Using Generalized Rice's Theorem to Prove Decidability

I'm going to ignore the second half of your post, and answer the question that appears at the first half. If this is not what you meant - post another question or edit as necessary.

Given a machine $M$ we define $L(M)$ to be the language recognized by that machine. In other words, $L(M)$ is the set of all the words $w\in \Sigma^*$ such that $M$ accepts $w$.

Thus, by its definition $L(M)$ is at least semi-decidable (because $M$ is accepting it!!)

To clarify whether $L(M)$ is decidable or semi-decidable(but not fully decidable), we need more information on $M$.

For instance, it can be that $M$ is the trivial machine that immediately go to the accepting state. In that case $L(M)=\Sigma^*$ (all the possible words), and $L(M)$ is decidable.

On the other hand it can be that $M$ does the following:

1. it ignores the first symbol of the input
2. it runs HP on the rest of the input

where HP is the machine that accepts the Halting Problem language. It is not too difficult to see that in this case $L(M)$ cannot be fully decidable (or otherwise the halting problem will be decidable), but, as said above, it is semi-decidable by definition (that is, it is in $RE\setminus R$).

Now, if you don't care about a specific machine $M$, but instead about all the machines that accept infinitely many words that begin with 1 and infinitely many words that begin with 2, the language that contain all such machines cannot be decidable due to Rice's theorem.

Just to be clear on the statement: let $S \subset RE$ be all the languages that contain infinitely many words that start with 1 as well as infinitely words that start with 2, then

$$L_S = \{ \langle M \rangle \mid L(M) \in S \}$$ cannot be decidable, $L_S\notin R$. Note that $L_S$ contains all the (encodings of) machines that satisfy the property $S$  defined in your question.


Time/Space Optimal k-Subset Operator Application - Is this a named problem?

For $K \ll 2N/3$, a good solution goes as follows, for $K$ even (the case $K$ odd is very similar):

Generate all XORs of length 2.
Generate all XORs of length 3.
...
Generate all XORs of length $K/2$.
Generate all XORs of length $K$.

This requires $\binom{N}{K/2} + \binom{N}{K/2-1} \approx \binom{N}{K/2}$ memory and $\binom{N}{2} + \cdots + \binom{N}{K/2} + \binom{N}{K} \approx \binom{N}{K}$ operations. This is close to optimal in terms of number of operations, since clearly at least $\binom{N}{K}$ are needed.

You can optimize this a bit as follows:

Generate all XORs of length 2 of $X_1,\ldots,X_{N-K/2+2}$.
Generate all XORs of length 3 of $X_1,\ldots,X_{N-K/2+3}$.
...
Generate all XORs of length $K/2$ of $X_1,\ldots,X_N$.
Generate all XORs of length $K$.

The savings are not significant.


Adding a vertex in graph in adjacent matrix repersentation

It more or less depends on the implementation. If you have implemented the matrix using linked lists (which isn't what we usually do), then adding a new vertex in $G$ will be linear in the number of vertices of $G$. But we don't usually use linked lists because then reading/checking an edge will take $V(G)^2$ time.

To allow random/constant time access of the adjacency matrix, we need to use fixed-size arrays of arrays (or matrix). Now, when you add new vertex, we are required to copy the whole matrix into a bigger size matrix: hence the quadratic time.

Generally, we use $vectors$ instead of $arrays$ which hold extra hidden memory, and hence it will indeed be linear time to add a vertex on average. https://www.geeksforgeeks.org/vector-in-cpp-stl/


You can prove this by full induction, which gives you an algorithm, too. The claim is $$I_n = \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} = (1 + a^{c_1})(1 + a^{c_2}) \ldots (1 + a^{c_n}) $$
The product of the right side can be computed in $O(n)$ steps if the exponentiation requires constant time.

Proof:

For $n=1$ the claim is obviously true: $I_1 = 1 + a^{\epsilon_1}$.
$n \rightarrow n+1$: Let the claim be true for $n$:
\begin{eqnarray}
(1 + a^{c_{n+1}})I_n & = & (1 + a^{\epsilon_{n+1}})\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} + a^{c_{n+1}}\sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=0}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} + \sum_{(\epsilon_1,...,\epsilon_n) \in \{0,1\}^n,\\ \epsilon_{n+1}=1}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 & = & \sum_{(\epsilon_1,...,\epsilon_n,\epsilon_{n+1}) \in \{0,1\}^{n+1}}a^{c_1 \epsilon_1 + ... + c_n \epsilon_n + c_{n+1} \epsilon_{n+1}} \\
 & = & I_{n+1}
\end{eqnarray}


A $\mathsf{BPP}$ machine $A$ has randomness complexity $r(n)$ which is polynomial in $n$. Hence, an $\mathsf{EXP}$ machine $B$ can loop over all $2^{r(n)}$ values of the random tape of $A$, simulating $A$ with each random input (each simulation taking polynomial time), and count how many times $A$ accepts or rejects. The overall decision of $A$, then, is whichever of the two counters contains a larger value at the end of this process.

Interestingly, the same reasoning also explains why $\mathsf{PP}$ is contained in $\mathsf{EXP}$.


TM with double-infinity tape semi-decides the same languages as classical TM

The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for any unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left" on the unbounded-tape TM, because our proof has to be applicable to all unbounded-tape TMs, not just ones that conveniently do this.
Understanding the equivalence of these two definitions of TM is important because both definitions are widely used in the academia, and many proofs using TMs are easier on one of these models over the other. Knowing that they are equivalent allows one to pick the easier model for a given situation.
For a basic idea of how to prove these two models of computation equivalent, consider that shifting the entire contents of the tape to the right can be done by a classical TM, allowing it to dynamically claim more space on the left of existing tape contents as needed. You can utilize this behavior to simulate an unbounded-tape TM in a classical TM.


Algorithm to convert rendered number back into symbolic form

RIES is another method for finding closed-form expressions; its web page describes the algorithm it uses.

If you do a Google search for algorithm for inverse symbolic calculator, you will find Wikipedia's page on algorithms for finding integer relations between multiple real numbers (as the page describes, you look for an integer relation between $x$, the number you care about, and a list of other standard mathematical constants).


A pathfinding algorithm for graphs in which arc weights can change over time

Look at pathfinding algorithms in the context of robotic navigation. In many such applications, the observed world is modeled as a graph. Naturally, the environment changes meaning the graph evolves as well.

For a start, have a look at D* Lite in the work of Koenig & Likhachev. This is a rather standard work in the area, and you'll find plenty of more work regarding replanning by looking at papers that reference it.

[1] Koenig, Sven, and Maxim Likhachev. "Fast replanning for navigation in unknown terrain." IEEE Transactions on Robotics 21.3 (2005): 354-363.


Connecting an unconnected forest of subtrees in a graph?

Your problem is known as the group Steiner tree problem, and it is NP-hard. More specifically, in this problem we are given a weighted graph $G=(V,E)$, and $k$ (vertex-disjoint) sets $S_1,S_2,\ldots,S_k \subseteq V$, and asked to find the minimum cost tree that uses at least one vertex from each $S_i$, where $i \in [k]$.

But don't fall into despair yet. Luckily for you, you have a very small number of "terminal trees", specifically three. The good news is that the problem is solvable in polynomial-time for fixed $k$. Moreover, it can be solved in something called FPT time, in fact there is an algorithm solving it running in $2^k n^{O(1)}$ time. When $k = 3$ is fixed, this is polynomial time. Let me shortly describe the idea, or at least give the pointers for a possible algorithm.

Misra et al. [1] observe that group Steiner tree reduces to the so-called directed Steiner out-tree problem. This, in turn, is solvable in a certain time bound using the idea of branching walks (of Nederlof) and inclusion-exclusion. The added nice thing is that the algorithm (as usual with such an inclusion-exclusion approach) needs only polynomial space. Moreover, there is evidence such algorithms are practical too. The Misra et al. [1] paper gives the necessary references.

[1] Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2012). FPT algorithms for connected feedback vertex set. Journal of combinatorial optimization, 24(2), 131-146.


Is there an algorithm to achieve optimal compression in a "streamed" manner, assuming equal probability of each possibility?

However, this requires having access to all of the data at once in order to decompress it.

Not true. The trick is to compress backwards, from the last symbol, to the first. You do need all the data at once to compress though.

However, what you are looking for can be done with arithmetic coding, without even needing access to all of the data at once during compression.


Measuring entropy for a table (e.g., SQL results)

Information-theoretic approach to database dependency theory has long history; here is couple of references:

An information-theoretic approach to normal forms for relational and XML data by  M. Arenas and L. Libkin (2005)
Information dependencies by M. M. Dalkilic and E. L. Roberston (2000)


Are there data structures that mix a tree structure with lists?

Yes.  Build a tree (with any branching factor you want).

Then, augment the data structure by maintaining one doubly linked list per level that contains all of the nodes at that level.  In particular, in each node you have a "left" and "right" field which goes to the next and previous elements in that doubly linked list (i.e., the next sibling to the right of it and the previous sibling to the left of it).

All of the standard tree operations can be augmented to update/maintain these doubly linked lists as well.  This adds only $O(1)$ extra time to each operation to update the doubly linked lists, so the asymptotic running time for each tree operation remains the same.

This construction can be applied to any tree with any structure you want (binary tree, $k$-ary tree, b-tree, AVL tree, red-black tree, etc.)

I don't know of any particular name for this specific case.  It is an instance of augmenting a data structure.  Many data structures/algorithms textbooks will have a chapter on augmenting data structures.


Can a runtime environment detect an infinite loop?

It might be theoretically possible for a runtime environment to check for such loops using the following procedure:

After ever instruction executed, the runtime environment would make a complete image of the state of a running process (i.e. all memory associated with it, including registers, P.C., stack, heap, and globals), save that image somewhere, and then check to see whether it matches any of its previously saved images for that process. If there is a match, then the process is stuck in an infinite loop. Otherwise, the next instruction is executed and the process is repeated.

In fact, rather than performing this check after every single instruction, the runtime environment could simply pause the process periodically and make a save-state. If the process is stuck in an infinite loop involving n states, then after at most n checks, a duplicate state will be observed.

Note, of course, that this is not a solution to the halting problem; the distinction is discussed here.

But such a feature would be an enormous waste of resources; continually pausing a process to save all memory associated with it would slow it down tremendously and consume an enormous amount of memory very quickly. (Although old images could be deleted after a while, it would be risky to limit the total number of images that could be saved because a large infinite loop--i.e., one with many states--might not get caught if there are too few states kept in memory.) Moreover, this feature wouldn't actually provide that much benefit, since its ability to catch errors would be extremely limited and because it's relatively simple to find infinite loops with other debugging methods (such as simply stepping through the code and recognizing the logic error).

Therefore, I doubt that such a runtime environment exists or that it will ever exist, unless someone programs it just for kicks. (Which I am somewhat tempted to do now.)


I found other answers here confusing, so let me explain it clearly here-
Definitions:

A sentential form is any string derivable from the start symbol. Note that this includes the forms with non-terminals at intermediate steps as well.
A right-sentential form is a sentential form that occurs in a step of rightmost derivation (RMD).
A sentence is a sentential form consisting only of terminals

The examples in your question are all sentences. And since any way of derivation (including RMD) ultimately leads to a sentence, technically all sentences are right-sentential as well as left-sentential forms. So there isn't any counter example which you asked for.
Clarifying Examples : Page 2 of this link


The Turing machine uses the tape alphabet $\Gamma = \{0,1,x,\epsilon\}$.
Writing down all the transitions explicitly is tedious, so I'll just summarize the main steps:

Move right until you find a 1 or $\epsilon$.
If a 1 is found proceed as follows:

Replace the $1$ with $x$.
Move the head back to the initial position (move left until you find $\epsilon$, then move right once).
Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
Replace the 0 with $x$.
Move right until you find a $0$ or $\epsilon$. If no $0$ is found reject.
Replace the 0 with $x$.
Move the head back to the initial position.
Repeat everything from the very first step.

Otherwise, if no 1 is found:

Move left until you find a $0$ or $\epsilon$. If no 0 is found, accept.
Reject.


Show that this algorithm does not work for determining convex polygons

A simple counterexample is a pentagram (http://en.wikipedia.org/wiki/Pentagram). It contains right turns (if you go in clockwise direction) only, but it is not convex. The above algorithm will incorrectly say pentagram is a convex polygon. It's actually a complex polygon.

In other words, algorithm might fail if the input polygon is complex.


RAM is cleared after each power cycle.
The power-up value of cells depends on the technology.

Static RAM content is usually random (there is no preference between 0 and 1, but the same chip may present similar patterns after each power-up).
Dynamic RAM has the value corresponding to empty capacitors in the RAM array, which usually corresponds to ones, but there is no guarantee.
Dynamic RAM can retain data for several seconds when unpowered (very dependant on temperature) : One cannot assume a known state at power-up and recent DRAM (DDR3, DDR4...) need complex initialization sequences where the RAM controller stores and checks some values like FFFF/0000/AAAA/5555, ...)


What's the least signifcant bit of a mantissa system?


Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

Counterexample: $f(n)=n!$ As $f(n)$ is $n$ times bigger  than $f(n-1)$, it is clear that $f(n-1) \neq \Theta(f(n))$.


Are there any proofs that BQP is not in P?

This is a famous open problem, so you won't find a proof anywhere at this time. We don't even know how to prove that $\mathsf{P\neq PSPACE}$, so finer separation of complexity classes such as $\mathsf{P\neq BQP}$ is also not known. Note that $\mathsf{BQP\subseteq PSPACE}$ is not trivial, you can find a proof in Quantum complexity theory, by Bernstein & Vazirani.

It is suspected that they are different, with the ability of quantum computers to factor integers in polynomial time being a strong witness.


Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$

In his famous paper, Håstad shows that it is NP-hard to approximate MAX2SAT better than $21/22$. This likely means that is is NP-hard to distinguish instances which are $\leq \alpha$ satisfiable and instances which are $\geq (22/21) \alpha$ satisfiable, for some $\alpha \geq 1/2$. Now imagine padding an instance so that it becomes a $p$-fraction of a new instance, the rest of which is exactly $1/2$-satisfiable (say it consists of groups of clauses of the form $a \land \lnot a$). The numbers now become $1/2 + p (\alpha - 1/2)$ and $1/2 + p((22/21)\alpha - 1/2)$. The latter number can be made as close to $1/2$ as we want.


How to convert this DFA with multiple final states to a regular expression? (State elimination method)

When I eliminate say $q_1$, ..., now since $q_1$ has 2 outgoing transitions, '$a$' to $q_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q_1$, which are $q_0, q_2$ and $f$ when $q_1$ is eliminated.

$\delta(q_0, ab)=q_0$
$\delta(q_0, aa)=q_2$
$\delta(q_0, a)=f$
$\delta(q_2, a+bb)=q_0$
$\delta(q_2, ba)=q_2$
$\delta(q_2, \epsilon+b)=f$

  $a(ba)^* + a(ba)^*a(ba)^*(aa(ba)^*a(ba)^*)^* + b(ab)^* + b(ab)^*b(ab)^*(bb(ab)^*b(ab)^*)*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$


It depends on the notion of equivalence you are using.

Suppose we compare these terms according to their denotational semantics,
on $\omega$-CPO domains. Denote with $F,G$ the semantics of the terms $f,g$. Thus, $F,G$ are Scott-continuous functions. Then, we have that the semantics of $Y(f \circ g)$ is, according to the Kleene's fixed point theorem

$$
(1) = [\![ Y(f\circ g) ]\!] = \bigsqcup\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\}
$$
where $\bigsqcup$ denotes the supremum / least upper bound.

Similarly, we get

$$
(2) = [\![ f(Y(g\circ f) ]\!] = F(\bigsqcup\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\})
$$

By continuity, we get
$$
(2) = \bigsqcup\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\}
$$

One can then prove that $(1)=(2)$ by observing that any element of any one chain is bounded above by some element of the other chain. Indeed, we have
$$
\bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots
$$
estabilishing that $(1)\sqsubseteq(2)$. Further,
$$
F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots
$$
estabilishing that $(2)\sqsubseteq(1)$, concluding the proof.

Much less formally, the term $Y(f \circ g)$ expresses the infinite application
$$
f(g(f(g(\ldots))))
$$
and, similarly, $Y(g \circ f)$ expresses
$$
g(f(g(f(\ldots))))
$$
It is fairly natural, then, that applying a single $f$ on top of the second one results in the first one. The above domain-theoretic proof provides a formal justification of that.


predication execution, branch prediction

The quote from the book doesn't describe how predicated instructions work today. It says that predicated instructions are "executed but only committed if the condition is true". But that would be exactly what branch prediction does, and would lead to exactly the same problems.

Instead, a predicated instruction is implemented as an ordinary instruction which just has one more input. It is always executed and always committed, just the effect of the instruction depends on a condition flag. That means all the mechanism to accelerate execution, out of order execution etc. can be used.


Here is an example of a decider:

  On input $w$, accept if $|w|$ is even, and reject if $|w|$ is odd.

Does it solve the halting problem?


Are two states equivalent in a DFA if on the same input the states transition to each other?

"We say that states $p$ and $q$ are equivalent if:

  For all input strings $w$, $\hat{\delta}(p,w)$ is an accepting state if and only if $\hat{\delta}(q,w)$ is an accepting state."

  (John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to automata theory, languages, and computation, 2nd edition.)

So if the automaton doesn't accept any strings, there cannot be a string that distinguishes the two states, and therefore there cannot be an equivalence between two states.


looking for counterexample for my algorithm for maximum independent set in Bipartite Graph

Consider the following graph:

None of the vertices has degree 1, so we go straight to step 5. Your algorithm would return 5 as the maximum independent set size, as both $L$ and $R$ have 5 vertices. However, the actual maximum independent set is $\{1, 2, 3, 6, 7, 8\}$, which has 6 vertices.


Addition errors in IEEE754 floating point representation

Printing out the IEEE754 format of the two numbers, I get:

  $\space\space\space0[11100010]10111100010010010101011=+1.10111100010010010101011\times2^{99}$
  $+0[11100001]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

Compare the exact values:

$$
1.1011110001001001010101011000111111010110011111001110000010110110100111 \times 2^{99} \\
1.0100001100011110000011111010111001101101011100100001011111001010101 \times 2^{98}
$$

Observe that both of the numbers are already rounded to represent them in IEEE 754, and it happens that both of them have rounded up.

Also note that since the values have different exponents, they've been rounded at different places.

Now add the rounded values:

  1.10111100010010010101011 ×299
+ 0.101000011000111100001000×299
 -------------------------------
 10.01011101110110000101111 x299
 11  1         1111

There's overflow, so the answer will have exponent $2^{100}$ and we have to round. Again, we're rounding up, to $1.00101110111011000011000\times2^{100}$.

  So, I suppose when you add these, you end up loosing precision, but exactly how?

You will nearly always lose precision when adding two floating point numbers. If they're both positive and have the same exponent, the output will have a larger exponent and you lose some bits from the end. If they have different exponents, the smaller one will lose bits from the end. And if they have opposite signs and the same exponent, the output has a smaller exponent and you lose precision because you need bits beyond the end which were lost earlier. Essentially the only cases where you don't lose precision are when you add a number to itself, or when the input numbers and the result can all be represented exactly in the width of the type.


On different characterizations of $\mathsf P$

I will consider the following simpler version of your question: is there a function $g(n,\epsilon)$ such that the following are equivalent, for a function $f(n)$:

$f$ is bounded.
For every $\epsilon > 0$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,\epsilon)$.

Consider first the case in which $g(n,\epsilon_1)$ eventually exceeds $g(n,\epsilon_2)$ whenever $\epsilon_1 > \epsilon_2$ (like your example $g(n,\epsilon) = n^\epsilon$). Then the second condition can be rewritten equivalently as

For every integer $M$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,1/M)$.

Define the function
$$ f(n) = \max_{M \leq n} g(n,1/M). $$

This function satisfies condition (3), and so is bounded, say $f \leq C$. This implies $g(n,1) \leq C$. But then the bounded function $C+1$ doesn't satisfy condition (3) for $M=1$. This contradiction shows that under the stated constraint, no function $g$ fits the bill.

On the other hand, as you mention, $f$ is bounded iff it is eventually dominated by every $\omega(1)$ integer function. Indeed, suppose that $f$ is unbounded. Then for every integer $M$ there exist infinitely many $n$ such that $f(n) \geq M$. In particular, we can find an increasing sequence $n_1,n_2,\ldots$ such that $f(n_M) \geq M$. Define a function $g$ by $g(n) = M-1$ for $n_{M-1} < n \leq n_M$. Then $g = \omega(1)$ but $f$ is not eventually dominated by $g$.

The functions from $\mathbb{N}$ to $\mathbb{N}$ have the cardinality of the continuum, and so they can be put (constructively!) in one-to-one correspondence with the real interval $(0,\infty)$. This immediately gives a function $g(n,\epsilon)$ which does fit your bill, though is not particularly natural.


No, in general you can't assume that an exponential search space requires exponential time to search. Linear programming generally has an exponential search space but can be done in (weakly) polynomial time.


Is emulation and/or virtualization faster when the host and guest systems are more similar?

Yes, virtualization on the same architecture will be a lot faster, if the architecture has built-in support for virtualization (as modern x86 processors do).  With hardware support for virtualization, most code will run at full speed.

If you want to "virtualize" onto a different architecture, then under the hood the VM will probably end up doing emulation.  Emulation is much slower.

To understand why, I suggest you do some more background reading about how virtualization and emulation work.  You could start with Wikipedia: https://en.wikipedia.org/wiki/Virtual_machine and https://en.wikipedia.org/wiki/Hardware-assisted_virtualization and https://en.wikipedia.org/wiki/Hardware_virtualization and https://en.wikipedia.org/wiki/Emulator.  If you'd like more details, you could check out an appropriate textbook (e.g., a good operating systems textbook).

The operating system most likely won't matter -- at least, there's no fundamental reason why it needs to make a difference.  (It might make a difference for engineering reasons rather than scientific reasons, e.g., due to a 32-bit vs 64-bit OS, or due to lack of support for features used by the VM software.)  The only way to know for sure is to do some experiments: measure performance on workloads you care about.


Is the complement of a semidecidable (r.e.) language always a semidecidable (r.e.) language?

No. A language $L$ and its complement $\bar L$ are semi-decidable if and only if $L$ is decidable (see here).

For example, the language containing all programs that terminate is semi-decidable, as you can run any program to see if it halts.
Its complement on the other hand is not semi decidable, as you cannot have a routine that determines, if a program will run forever or not.


Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci

Suppose that you test the edges in order. The expected cost is thus
$$
\sum_{i=1}^n c_i \prod_{j=1}^{i-1} p_j.
$$
Now suppose that we switch the order of $k$ and $k+1$. The two relevant terms are
$$
c_k \prod_{j=1}^{k-1} p_j + c_{k+1} \prod_{j=1}^k p_j.
$$
After switching $k$ and $k+1$, these two terms become
$$
c_{k+1} \prod_{j=1}^{k-1} p_j + c_k p_{k+1} \prod_{j=1}^{k-1} p_j.
$$
Dividing by $\prod_{j=1}^{k-1} p_j$, these two expressions become
$$
c_k + p_k c_{k+1} \\
c_{k+1} + p_{k+1} c_k
$$
The switch leads to an improvement if
$$
c_k + p_k c_{k+1} > c_{k+1} + p_{k+1} c_k \\ \Longleftrightarrow \\
c_k (1-p_{k+1}) > (1-p_k) c_{k+1} \\ \Longleftrightarrow \\
\frac{c_k}{1-p_k} > \frac{c_{k+1}}{1-p_{k+1}}.
$$
This suggests testing the edges in increasing order of
$$
\frac{c_i}{1-p_i}.
$$


Each vertex in a decision tree is associated with a question of the form "$x_i < c$?" (or "$x_i \leq c$?"), where $x_i$ is one of the input and $c$ is a constant. The decision whether to go left or right then depends on which side of the hyperplane $x_i = c$ the input is located.

The possible hyperplanes which come up this way are not arbitrary – they are orthogonal to one of the axes; the hyperplane $x_i = c$ is orthogonal to the $x_i$ axis. An example of a different hyperplane, which cannot occur, is $x_1 - x_2 = 0$.


Partition points in a plane with a straigth line

There is a brute $O(n^3)$ algorithm.

There are $\binom n 2 = \frac {n(n-1)} 2$ lines over pairs of points. If a line goes over $k$ points, there are $2(k+1)$ ways to rotate the line by a negligible angle, so that no points go over it and each rotation partitions the $k$ points differently.

For each pair of vertices (v1, v2),
  rotate the space so that v1.y = v2.y = 0
  let UP be the sum of values of vertices with positive y
  let DOWN be the same for negative y
  let L be a list of vertices with y = 0, sorted by x

  For each of L.length+1 ways to cut L in two,
    let LEFT be the sum of values of vertices in L to the left of the cut
    let RIGHT be the same for vertices to the right

    check whether one of UP + LEFT, DOWN + RIGHT or UP + RIGHT, DOWN + LEFT
     is a better partition than your previous best.


Can I simplify the recurrence T(n) = 2T((n+1)/2) + c by ignoring the "+1" part?

This probably does not change the asymptotic order.

From $T'(n) = 2 T'(n/2) + c$, you can obtain $T'(n) = \Theta(n)$.

Then you can try to prove that your original $T(n) = \Theta(n)$ by mathematical induction.


PAC learning vs. learning on uniform distribution

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

This has been asked on TCS.SE.
It looks like the short answer is yes -- Aaron Roth gives the example of width-$k$ conjunctions for $k \gg \log n$. And in the comments, Avrim Blum is quoted as giving the answer of $2$-term DNF.

I don't totally understand the examples there -- it must take a bit more work to really derive the result (I will update this answer if I find a self-contained proof). But the general problem here with the uniform distribution is that if the target function $f$ is "sparse", meaning it labels at most a $\delta$ fraction of the input distribution with $1$, then it is easy to learn by simply guessing $0$.

Beyond just efficient (polynomial) PAC learning, there are other examples where the uniform distribution seems to help. For example, a classic hard problem for PAC learning is DNF, a problem which is conjectured to be not PAC learnable, and quite hard. On the other hand DNF over the uniform distribution is almost PAC learnable: we have a qausipolynomial time algorithm for it. See these notes and these notes.

In summary, there appears to be a lot of work on learning under the uniform distribution (search "PAC learning under uniform distribution" for additional references). And it seems that this problem is easier than studying PAC learning, where we aren't able to prove much. Quoting Ryan O'Donnell's notes above:

  General PAC-learning insists that one algorithm works simultaneously for all distributions. In fact, the machine learning community interested in real-world applications finds the uniform setting questionable: "They’ll punch you in the nose if you try to tell them about algorithms in this
  framework." --Ryan. But, in a more general framework, no one can really prove anything.


Subset of nodes such that all nodes of a graph are adjacent

In the literature, such a subset is called a perfect code.
As it is NP-complete to determine if a given graph has a perfect code, even on some very restricted inputs, your exponential-time algorithm is probably about as good as it gets.