Computing the closest point inside an intersection of half-spaces

This can be modeled as a convex program
$$\begin{align}
\text{min.} \qquad & ||x-p||_2^2,\\
\text{s.t.} \qquad & Ax\leq b,\\
& x\in\mathbb{R}^3.
\end{align}$$
and solved (in reasonable time) by standard solvers. Here's example code in julia

using Convex, SCS

# generate random problem data
m = 5;  n = 3
A = randn(m,n); b = randn(m,1); p=randn(3,1)

# define problem
x = Variable(n)
problem = minimize(sumsquares(x-p), [A*x<=b])

# solve
solve!(problem, SCSSolver())
println("Status $(problem.status) distance $(problem.optval)")


Does the state of a cell in cellular automata has to be from a finite set?

Although Wikipedia mentions a finite set of states (http://en.wikipedia.org/wiki/Cellular_automaton), I'm sure you could find some interesting models that use infinitely many states. As you suggested, each cell could contain an integer, a continuous value between 0 & 1 (shade of grey), etc.

The idea of basing cell contents upon cell coordinates is interesting and unfamiliar. Of course, you'd have to also include some other inputs in the transition function if you want the pattern to change from step to step. This would create patterns that vary based on their location, which sounds fun to explore.


Relation between Type Assignment system (TA) and Hindley-Milner system

System F and its subsystem HM have a type former for universal quantification:

$$
   \tau \quad::=\quad \forall x.\tau \ |\ ...
$$

which the system in Hindley/Seldin doesn't have. That is the key difference.

Now System F doesn't have decidable type-inference, and HM is a way of combining type-inference with reasonably expressive parametric polymorphism. HM achieves this by allowing only outermost universal quantification, i.e. all types are of the form

$$
   \forall x_1 \forall x_2 ... \forall x_n.\tau
$$

where $\tau$ is quantifier free (and $n \geq 0$). HM gives a rule system that ensures that only programs that can be typed in this way are admissible. This is achieved by "let-polymorphism". The system in Hindley/Seldin doesn't do any of that. Later, in Chapter 13, Hindley/Seldin introduce pure type systems (PTS), of which System F is a special case.  I'm not sure if HM can be expressed as a PTS.

The question of strong normalisation is orthogonal. System F and HM are strongly normalising, but that can easily be remedied by introducing fix-point combinators or similar. The paper  Principal type-schemes for functional programs  by L. Damas and R. Milner even states this:
"For example, recursion is omitted since it can be introduced by simply adding
    the polymorphic fixed-point operator ..." The introduction of fixpoints, making the system Turing complete, poses no issues from the point of view of type inference.


Does two system's clock synchronises to communicate with each other?

Your question is a bit vague, depending on what is communicating, so I will try to give a general answer. There are essentially two big ways of communicating:

Sending data together with a clock signal (source synchronous): this is used in I2C, RAM, SPI
Sending just data and let the other side recover the clock from it (clock recovery): this is used in USB, PCI Express, Ethernet (I think)

The bottom line is that synchronization is important, two systems will never have exactly the same clock because they drift and yet they have to agree on some clock when transferring data. Both approaches have advantages and drawbacks:

source synchronous: can achieve higher speed but needs one more wire and increases complexity of the receiver because it has to deal with two clock domains (its own and the sender's)
clock recovery: one less wire but requires the signal to toggle often enough, a process known as self-clocking which adds overhead to the signal (for example USB sends 10 bits for 8 bits of data, this is known as 8b/10b encoding)


Easy proof for context-free languages being closed under cyclic shift

You can try to use pushdown automata. Given a pushdown automaton for the original language, we construct one for the cyclic shift. The new automaton operates in two stages, corresponding to the $y$ and the $x$ part of the word $yx$ (where $xy$ is in the original language). In the first stage, whenever the automaton would like to pop a non-terminal $A$, it can instead push a non-terminal $A'$; the idea is that at the end of the first stage, the stack would contain, in reverse order, the symbols that are found in the stack after reading $x$ by the original automaton. In the second stage (the switch is non-deterministic), instead of pushing a non-terminal $A$, we are allowed to pop a non-terminal $A'$. If the original automaton can indeed generate the stack upon reading $x$, then the new one would be able to exactly pop the entire stack.

Edit: Here are some more details. Suppose we are given a PDA with alphabet $\Sigma$, set of states $Q$, set of accepting states $F$, non-terminals $\Gamma$, initial state $q_0$, and a set of allowable transitions. Each allowable transition is of the form $(q,a,A,q',\alpha)$, meaning that when in state $q$, upon reading $a \in A$ (or $a = \epsilon$, in which case it's a free transition), if the top-of-stack is $A \in \Gamma$ (or $A = \epsilon$, which means stack is empty), then the PDA can (it's a non-deterministic model) move to state $q'$, replacing $A$ with $\alpha \in \Gamma^*$.

The new PDA has a new non-terminal $A'$ for each $A \in \Gamma$. For every two states $q,q' \in Q$ and $A \in \Gamma \cup \{\epsilon\}$, there are two states $(q,q',1),(q,q',2,A)$. The starting states (the actual starting state is chosen non-deterministically among them via $\epsilon$-transitions) are $(q,q,1)$. For each transition $(q,a,A,q',\alpha)$ there are corresponding transitions $((q,q'',1),a,A,(q',q'',1),\alpha)$ and $((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$. There are other transitions as well.

For each transition $(q,a,A,q',\alpha)$, there are transitions $((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$, where $B \in \Gamma \cup \{\epsilon\}$ and $\epsilon' = \epsilon$. For every final state $q \in F$, there are transitions $((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$, where $A \in \Gamma \cup \{\epsilon\}$.

For every transition $(q,a,\epsilon,q',\alpha)$, there are transitions $((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$, where $A \in \Gamma \cup \{\epsilon\}$. For every transition $(q,a,\epsilon,q',A)$, there are transitions $((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$, where $B \in \Gamma \cup \{\epsilon\}$. For every transition $(q,a,A,q',B)$, there are "generalized transitions" $((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$; these are implemented as a sequence of two transitions through an intermediate new state. Transitions $(q,a,\epsilon,q',\alpha)$ with $|\alpha| \geq 2$ are handled similarly. For every transition $(q,a,A,q',A)$, there are transitions $((q,q'',2,A),a,B,(q',q'',2,A),B)$, where $B \in \Gamma' \cup \{\epsilon\}$. Transitions $(q,a,A,q',A\alpha)$ are handled similarly. Finally, there is a sole final state $f$, and transitions $((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$.

(There might be a few transitions that I missed, and some of the details that I'm omitting are somewhat messy.)

Recall we're trying to accept a word $yx$, where $xy$ is accepted by the original PDA. A state $(q,q',1)$ means that we're at stage 1, at state $q$, and the original PDA is at state $q'$ after reading $x$. A state $(q,q',2,A)$ is similar, where $A$ corresponds to the last $A'$ that was popped. At stage 1, we are allowed to push $A'$ instead of popping $A$. We do that for each non-terminal that is produced while processing $x$, but only popped while processing $y$. At stage 2, we are allowed to pop $A'$ instead of pushing $A$. If we do this, then we have to remember that the top-of-stock is really $A$; this only applies when there are no "temporary" things on the stack, which in the simulated PDA is the same as the top-of-stack being $\epsilon$ or of the form $B'$.

Here is a simple example. Consider an automaton for $x^n y^n$ that pushes $A$ for each $x$, and pops $A$ for each $y$. The new automaton accepts words of two forms: $y^k x^n y^{n-k}$ and $x^k y^n x^{n-k}$. For words of the first form, stage 1 consists of pushing $k$ times $A'$, stage 2 consists of popping $k$ times $A'$, pushing $n-k$ times $A$, and popping $n-k$ times $A$. For words of the second form, we first push $k$ times $A$, then pop $k$ times $A$, push $n-k$ times $A'$, transition to stage 2, and pop $n-k$ times $A'$.

Here is a more complicated example, for the language of balanced parentheses of various types ("()","[]","<>") such that the immediate descendants of each type of parentheses must belong to a different type. For example, "([]<>)" is OK but "()" is wrong. For each "(", we push $A$ if the top-of-stack isn't $A$, for each ")", we pop $A$. Similarly $B$,$C$ are associated with "[]" and "<>". Here is how we accept the word ">)([()]<". We consume ">)", pushing $C'A'$, and transition to stage 2. We consume "(", popping $A'$ and remembering the top-of-stack $A$. We consume "[()]" , pushing and popping $BA$; when pushing $B$, we are aware that the "real" top-of-stack is $A$, and so square brackets are allowed (we wouldn't be fooled by ">)(()<"); when pushing $A$, since the top-of-stack is $B$ (which is not $\epsilon$ or of the form $X'$), then we know that $B$ is also the "real" top-of-stack, and so round parentheses are allowed (even though the shadow top-of-stack is $A$). Finally, we consume "<" and pop $C'$.


kNN: how to improve Spam classification?

You could consider querying the k-nearest neighbours and weight them following some schema like this one. There are quite a few in the literature. The general idea is to give more relevance to those neighbours lying closer to your sample. It has the effect of regularizing your classifiers (smooth out your decision surfaces).

You evaluated your algorithm using 10-fold CV. What is the dispersion of your measurements?. If you see wide dispersion, you could use bagging. It is very easy to implement. It is specially meaningful when overfitting is strong.


Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

Space-constructibility is a red herring. The real problem in your argument is the step
$$
\mathsf{DTIME}(c^{S(n)}) \subseteq \mathsf{NTIME}(S(n)),
$$
which is not expected to hold in general. For example, the problem of deciding whether an input Turing machine halts in time $2^n$ can be solved in deterministic exponential time, but is conjectured not to be solvable in nondeterministic polynomial time.

Furthermore, while it's not clear whether Savitch's theorem is tight, it is expected that in general $\mathsf{DSPACE}(s(n)) \neq \mathsf{NSPACE}(s(n))$. For example, it is believed that $\mathsf{L} \neq \mathsf{NL}$.


Greater than or equal to operation (32-bit ALU)

David Richerby's comment is right, in that the typical way it's "done" is to perform a subtraction and examine the "carry out" bit.

But I think it's worth stepping back for a moment and making a general comment about modern ALU design which may help you.

Thanks to Moore's Law, the number of transistors (and hence gates) required to implement a functional unit is not a serious limitation. Moreover, integer ALUs are not even close to the most power-hungry components of a modern CPU. So the main thing that needs to be conserved in a modern integer ALU design is propagation delay.

For essentially-single-cycle operations such as logic and add/subtract arithmetic, many modern integer ALUs are designed so that all potential operations are performed in parallel, and the "correct" one is selected with a multiplexer. This has the advantage that some of the multiplexer logic can be performed in parallel with the ALU operation, which again saves on propagation delay.

The same technique is used in floating point, incidentally. When performing a IEEE-754 floating point operation, the typical final step is that the result needs to be rounded correctly, using some logic which involves testing the answer and the FPU's current rounding mode. Many "real" FPUs essentially duplicate circuitry for some of the operation, performing three versions in parallel ("round up", "round down", and "pass through") and using a final multiplexer stage to decide which one to keep.

Of course, in real CPUs, ALUs typically aren't designed at the gate level these days, they are designed at the transistor level. So, for example, the multiplexer stage is probably achieved with high-impedance outputs followed by an amplifier stage to clean up the signal.


Amdahl's law of processors (infinite processors to test limits of speedup)

Don't think of it as "you've been given infinity processors." Think of it as "you can have as many processors as you want, but of course after a certain point more professors won't help, so find out how fast you can make it run with the optimum number of processors."


How to implement polymorphism in a turing complete environment?

So, first, a question. Are you using dynamic or static dispatch? i.e. if Circle and Shape provide implementations of the same method, and you cast a Circle to a Shape, which one gets called?

If you're using static dispatch, one way to do it is, instead of making a Circle by taking a shape and adding fields, you make Circle its own type, with a special Super field that is a Circle. Any time Circle methods reference Shape fields/methods, you desugar into Super.field. Casting a Circle to a Shape then just involves looking up the shape that's stored.

If you're using Dynamic dispatch, but are using static typing, instead you can use "duck typing" internally, that is, the "type" of something is just which methods/fields are accessible. So in this system, you could construct a Circle as you've described, and when you cast it to a Shape, there's no runtime effect. Your typechecker just ensures that no Circle methods are called on a Shape, even if its runtime representation is a Circle.

Finally, if you're using dynamic dispatch and dynamic typing, then you probably don't need to ever cast a Circle to a Shape (since there's no typechecker to stop you from calling Shape methods on a Circle). The trick here is that your assert shape is a Shape should return True for anything that is a subclass of Shape. So as long as that check succeeds for a Circle, you're fine. This is why such a check is called instanceof in Python: you're not accessing the type of the value, you're checking if it is a subclass of the desired type.

I'm not sure how Turing Completeness factors into anything: Java, Python, and other subclassing languages are all Turing Complete. Java's type system is even Turing Complete!

One final pedantic note: what you call "polymorphism" is better described as "subclass polymorphism". There are, in PL theory, many other kinds of polymorphism, such as parametric (i.e. generics), and ad-hoc (i.e. overloading).


Are two-level schedulers only useful to manage swapping?

There are other forms of two-level scheduling than the type you describe.  For example, one level of scheduling could be per-user and the other could be per-process, aiming for giving a user with 20 processes the same amount of CPU time as a user with 1 process.  With a single-level scheduler, each process might get 1/21 of the CPU time.

Another form of two-level scheduling could be per-process and per-thread, aiming to give a process with 20 threads the same amount of CPU time as a process with 1 thread.


Does reduction from an NP-complete problem to some problem $X$ imply that $X\in NP$?

the reduction only shows that X is at least as hard as SAT (NP-HARD). This could mean that X is in a class suspected to be harder than NP such as PSPACE or EXPTIME. To show that X is NP-complete you must show that it is also in NP. If you try it out you will see that you can easily reduce SAT to problems in EXPTIME that are not suspected to be in NP. The idea being that your reduction shows that X is at least as hard as SAT, but there are classes of problems harder than NP problems which X could fall into.


Rooted Binary Tree - Chain Nodes Algorithm

The number of chain nodes of a rooted binary tree with two non-empty sons is the sum of the chain nodes in its sons.

Also, the number of chain nodes of a rooted binary tree with only one non-empty son is the number of chain nodes of the son plus one.

If a rooted binary tree has no non-empty sons, its number of chain nodes is zero.

And finally, the number of chain nodes of an empty rooted binary tree is zero.

So, following this properties we have

int chainNodes(tree T) {
    if (T is empty)
        return 0;
    if (T has no nonempty sons)
        return 0;
    if (T has only one nonempty son)
        return chainNodes(son)+1;
    if (T has two nonempty sons)
        return chainNoodes(leftSon)+chainNodes(rightSon);
}

which is similar to your try.


I'm looking for an algorithm to find unknown patterns in a string

Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves encode the positions.


Efficient compression of unlabeled trees

Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.

Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and $T'$ are both the null trees (having no vertices at all), they are structurally equivalent. If $T$ and $T'$ are both not null trees, then they are structurally equivalent iff their left children are structurally equivalent and their right children are structurally equivalent. 'Structural equivalence' is the minimal fixed point over these definitions.

For example, any two leaf nodes are structurally equivalent, as they both have the null trees as both their children, which are structurally equivalent.

As it is rather annoying to say 'their left children are structurally equivalent and so are their right children', we will often say 'their children are structurally equivalent' and intend the same. Also note we sometimes say 'this vertex' when we mean 'the subtree rooted at this vertex'.

The above definition immediately gives us a hint how to perform the compression: if we know the structural equivalence of all subtrees with depth at most $d$, then we can easily compute the structural equivalence of the subtrees with depth $d+1$. We do have to do this computation in a smart way to avoid a $O(n^2)$ running time.

The algorithm will assign identifiers to every vertex during its execution. An identifier is a number in the set $\{ 1, 2, 3, \dots, n \}$. Identifiers are unique and never change: we therefore assume we set some (global) variable to 1 at the start of the algorithm, and every time we assign an identifier to some vertex, we assign the current value of that variable to the vertex and increment the value of that variable.

We first transform the input tree into (at most $n$) lists containing vertices of equal depth, together with a pointer to their parent. This is easily done in $O(n)$ time.

We first compress all the leaves (we can find these leaves in the list with vertices of depth 0) into a single vertex. We assign this vertex an identifier. Compression of two vertices is done by redirecting the parent of either vertex to point to the other vertex instead.

We make two observations: firstly, any vertex has children of strictly smaller depth, and secondly, if we have performed compression on all vertices of depth smaller than $d$ (and have given them identifiers), then two vertices of depth $d$ are structurally equivalent and can be compressed iff the identifiers of their children coincide. This last observation follows from the following argument: two vertices are structurally equivalent iff their children are structurally equivalent, and after compression this means their pointers are pointing to the same children, which in turn means the identifiers of their children are equal.

We iterate through all the lists with nodes of equal depth from small depth to large depth. For every level we create a list of integer pairs, where every pair corresponds to the identifiers of the children of some vertex on that level. We have that two vertices in that level are structurally equivalent iff their corresponding integer pairs are equal. Using lexicographic ordering, we can sort these and obtain the sets of integer pairs that are equal. We compress these sets to single vertices as above and give them identifiers.

The above observations prove that this approach works and results in the compressed tree. The total running time is $O(n)$ plus the time needed to sort the lists we create. As the total number of integer pairs we create is $n$, this gives us that the total running time is $O(n \log n)$, as required. Counting how many nodes we have left at the end of the procedure is trivial (just look at how many identifiers we have handed out).


Determining an appropriate number of buckets for a hash function

The number of buckets in a hash structure will almost always be on the order of the number of items in the hash structure.

The phrase "on the order of" is intentionally imprecise. That means you could have twice as many buckets as items. Or two times as many items as buckets. But the two values (bucket count and item count) are generally correlated in a linear (not exponential) manner, within a factor of 10.

If the hash function is fairly good, and the number of buckets is prime, then anywhere up to one item per one bucket will result in a median search depth of one and an average search depth just over one. Generally, because the relative cost of a bucket is small, it makes sense to maintain a ratio of buckets to items that is greater than 1, but only minimally so.

Your description of your solution is confusing, because you have 10,000 records identified by initials, but only 676 combinations of initials (26 x 26). It is likely that you are layering complexity onto complexity in a vain attempt to save clock cycles and RAM, both of which you are likely to waste as a result of the inherent complexity of your solution. A smart guy named Donald Knuth once said: "Premature optimization is the root of all evil (or at least most of it) in programming." I'm almost certain you are well down that path already, and I suggest that you back out of that choice.


What makes a proof assistant a proof assistant?

I would expect a proof assistant to provide:

a syntax to express some mathematical statements
a syntax to express a proof of one of those statements
a computational process to "check" that a proof of a statement is indeed valid (returns success or failure, or maybe does not return at all)

Finally, for such a proof assistant to be trustworthy, it should come with a justification of the fact that when its checking process says that a proof of a statement is valid, then indeed this statement is valid in the usual mathematical sense -- there exists a mathematical proof that mathematicians will accept.


Can an algorithm be truly non-deterministic?

There are two meanings of non-deterministic.
Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the algorithm can branch into multiple execution paths, and the algorithm accepts if any of these paths accepts.  Or, equivalently, you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.  Such an algorithm can't actually be implemented in practice (except by simulating it in an inefficient way), so it is more of a thought experiment.
Meaning #2: non-deterministic means "it is not a deterministic algorithm".  For instance, such an algorithm might be randomized.
An algorithm that uses random numbers would be considered non-deterministic in the sense of Meaning #2 but not in the sense of Meaning #1.
Usually when you see the phrase "nondeterminism" in complexity theory or algorithms, it will typically mean the former meaning, but no guarantees.  You might have to infer which was meant from context.
See also Differences and relationships between randomized and nondeterministic algorithms?.


What is the importance of the condition "| xy | < p" in pumping lemma?

$p$ is the number of states in the automaton.  As you say, the pumping lemma is about the pigeonhole principle.  Suppose that $q$ is the first state that's repeated when you read input $w$.  Then $x$ is the string that you read before you reach $q$ for the first time, and $y$ is the string you read between the first and second visits to $q$. Since there are only $p$ states including the start state, you must repeat a state after doing at most $p$ transitions, i.e., reading a string of length at most $p$.  So the condition $|xy|\leq p$ comes from the proof.

In reality, when an automaton reads a particular string $w$, there might be many times when it returns to a state that has already been visited. If you take $w\in L$ any split $w=xyz$ with $|y|\geq 1$, such that the automaton is in the same state at the beginning and end of $y$ then $xy^iz$ will be in $L$ for all $i$, regardless of how long $xy$ is.


NP-Complete Problem and Polynomial Hierarchy

$\mathrm{SAT}$ and all $\mathrm{NP}$-complete problems are certainly in $\Sigma_2^P$, as $\mathrm{NP} \subseteq \Sigma_2^p$. It is true however that if $\mathrm{SAT}$ (or any $\mathrm{NP}$-complete problem) ever gets proven to be $\Sigma_2^p$-hard, then $\mathrm{NP} = \Sigma_2^p$, and consequently the polynomial hierarchy collapses to $\mathrm{NP}$.


I think you're just confused about the definition of "height".  You write that you expect $f(2)=4$, where $f(h)$ is the number of leaves when the height is $h$.  A full binary tree with four leaves looks like this:

     o
   /   \
  o     o
 / \   / \
o   o o   o

So, in this case, you're taking the height to be the number of edges between the root and a leaf, and a tree of height $h$ has $h+1$ levels of nodes.

But you also write $f(2) = 2f(2-1) = 2f(1) = 2$, implying that $f(1)=1$.  A full binary tree with only one leaf looks like this:

     o

However, that tree has one level of nodes, so it has height zero.  The height $1$ tree is

     o
    / \
   o   o

so we see that $f(2) = 2f(2-1) = 2\times 2 = 4$, as expected.
Perhaps you were thinking of the following tree, which has one leaf and height $1$, but isn't a full binary tree.

     o
     |
     o


Inputting a superposition into a cNOT gate

This is more of a question on linear algebra rather than a question about quantum computation. You should probably have a firm grip on basic linear algebra (vector spaces, linear operators, inner product, etc) before delving into quantum computation (there's no way around it).

CNOT is a linear operator in our vector space, $\mathbb{C}^4$ (were only dealing with linear transformations, specifically unitary). In order to specify how a linear transformation operates on an arbitrary vector, it is enough to specify how it operates on each member of a basis for our vector space. Suppose we apply some linear operator $T$ on an arbitrary superposition, then by linearity:

$T\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)=
\alpha T|00\rangle+\beta T|01\rangle + \gamma T|10\rangle + \delta T|11\rangle$

$T|ij\rangle$ is the application of the operator $T$ on the vector $|ij\rangle$. The application of a linear operator in a finite dimensional vector space can be described by matrix multiplication, so this means multiplying the matrix representing $T$ by the vector $|ij\rangle$. The "order" you refer to does not matter, because addition in a vector space is commutative.

Since you  know how to apply CNOT to the four basic states, the above equality shows you how to apply it on an arbitrary superposition.

When talking about matrix representation, the vector $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$ is represented by
$
\begin{pmatrix}
\alpha\\
\beta\\
\gamma\\
\delta
\end{pmatrix}
\in\mathbb{C}^4$, so applying CNOT to this state means multiplying it's matrix by this vector, i.e.

$CNOT\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)=
\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
\alpha\\
\beta\\
\gamma\\
\delta
\end{pmatrix}=
\begin{pmatrix}
\alpha\\
\beta\\
\delta\\
\gamma
\end{pmatrix}
$.

This is obviously equivalent to applying CNOT to each of the four vectors in $\mathbb{C}^4$ and adding up the results.


Is the language of palindromes context-free?

The language of palindromes is one of the standard examples of a non-regular context-free language. It is generated by the context-free grammar
$$
S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon
$$


How can I compress data that represents a number's change over time?

In the case of storage and querying from the storage i.e. if you can first get all time:value pairs, you can use curve fitting (regression) to get the polynomial function v=f(t), where v = value and t = time which will not be accurate, may even be outside 5% error margin; but would the  get the work done in a very low file size and acceptable(?) margin of error.


Prove that not all languages over unary alphabet are regular

You can show this in many ways. For example, every language can be defined using a regular expression, and the number of regular expressions over a fixed alphabet is countable, since a regular expression is just a word over some alphabet.


How does a single-track Turing machine simulate a multi-track Turing machine?

If $\Sigma = (x_1,...,x_n)$ is the alphabet of the $m$-tracks $TM$, just use an expanded alphabet $\Sigma' = \Sigma \times ... \times \Sigma$ for the single-track $TM'$  ($|\Sigma'| = n^m$).

Every vector $\bar{x}_i$ of $m$ symbols from $\Sigma$ can be mapped to a unique alphabet symbol $u_i$ in $\Sigma'$: $\bar{x}_i = (x_{i_1},x_{i_2},...,x_{i_m}) \rightarrow u_i \in \Sigma'$

Hence every transition of $TM$ $(q_h,(x_{i_1},x_{i_2},...,x_{i_m}))\rightarrow (q_k,(x_{j_1},x_{j_2},...,x_{j_m}),dir)$
can be mapped to an equivalent transition in $TM'$ where the "read vector" $\bar{x_i}$ and "write vector" $\bar{x_j}$ are replaced with the corresponding alphabet symbols in $\Sigma'$: $(q_h,u_i)\rightarrow (q_k,u_j,dir)$


Winning strategy using Dynamic Programing

For a vertex $v \in V$, let $W(v)$ be the following predicate: "a player starting at $v$ wins". If $N(v)$ is the set of outward neighbors of $v$, then
$$
W(v) = \bigvee_{u \in N(v)} \lnot W(u),
$$
where the empty disjunction is simply false.

This suggests a strategy to compute $W(v_0)$ using dynamic programming.


Suppose that $n$ is a power of $k$, say $n = k^t$. Then
$$
T(k^t) = kT(k^{t-1}) = k^2T(k^{t-2}) = \cdots = k^tT(1) = k^t,
$$
assuming a base case of $T(1) = 1$. So for powers of $k$, we have $T(n) = n$. You can also prove that by induction: if $T(n/k) = n/k$ then $T(n) = kT(n/k) = k(n/k) = n$.


Red-Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

This is case 4, because w's right child is red. the left child (of z) could have any color red/black.


$P$-complete problems and Logspace reductions

The circuit value problem: input is a Boolean formula and a truth assignment to its variables; accept if, and only if, the input is well-formed and the formula evaluates to true under the given assignment. The complement is to accept iff the input is malformed or the formula is false.

The reduction is to check that the input is well-formed.  If so, output the negation of the formula, with the same truth assignment; if not, output either $X; X=\mathrm{t}$ or $X; X=\mathrm{f}$, depending on which way you're going.


Alternative definitions of ZPP and probabilistic Turing Machines

The definition works fine if you allow $r$ to be infinite, and require that $M(x,r)$ agrees with $L$ with probability $1$ when $r$ is distributed according to the coin toss measure on $\{0,1\}^{\mathbb{N}}$ (toss a fair coin an infinite number of times). In this setting, in order to get $\mathsf{ZPP}$, you need to require that the expected running time will be polynomial in $|x|$.

However, you don't really need an infinite number of coins to get $\mathsf{ZPP}$, and could do with an exponential amount of coins. Suppose $L\in\mathsf{ZPP}$, hence there exists a probabilistic Turing machine $M(x)$, such that for all $x\in\Sigma^*$ it holds that $M(x)=L(x)$ and $\mathbb{E}[T_x]\le |x|^c$, where $T_x$ is the running time of $M$ on input $x$. You can now define an equivalent Turing machine $M'$ which is exponential in the worst case (rather than unbounded), and still satisfies the above conditions. Given input $x$, $M'$ simulates $M$ for $2^{|x|^c}$ steps, and if $M$ did not halt in this time, check "manually" if $x\in L$. This can be done by running a PSPACE machine for $L$ (which exists since $\mathsf{ZPP\subseteq PSPACE})$. You can now show that $M'$ is also polynomial in expectation (think about the appropriate choice of $c$ for this to work).


Breadth First Traversal for graph with multiple connected components

This is not a fundamental difference.  You can easily do BFS on a graph with multiple connected components by using the same loop as in lines 5-7 of the DFS procedure you show:

for each vertex $u \in G.V$:

if $u.\text{color} == \textsf{white}$:

BFS($G,u$)


What is the average search complexity of perfect hashing?

Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.


You want to find a way of creating $G'$ from $G$ such that $G'$ has a $k$-key iff $G$ has a Hamiltonian path.

If a graph $G$ has $k$ vertices and a simple path of length $k$, then what can we conclude about it having a Hamiltonian path?

I'm guessing the intention is that the vertices in the path must be different from the vertices in the cycle (otherwise every ham cycle graph would contain a $k$-key and vice versa).  So just think, suppose we knew that $G$ had a ham cycle starting from some vertex. Where would we tack on some vertices to create a $G'$ that had a $k$-key using $G$'s ham cycle?


You can write, if $b\gt 1$,
$$b^{t(n)}=2^{\log_2{b}\times t(n)}=2^{O(t(n))}$$

So,
$$O(t(n)b^{t(n)})=O(t(n)2^{O(t(n))})=O(2^{\log_2{t(n)}}2^{O(t(n))})=2^{O(t(n))}$$

To elaborate,
$$O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$$ which means it is eventually upper bounded by some $$c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$$

Note that if $b=1$, then the non deterministic Turing machine is effectively a deterministic Turing machine, so you can still write it as $O(t(n))$, which is as expected.


How does knowing the input size make the time complexity of a function constant?

First, I've noticed most of the time people omit what exactly n represents in big O notation.

Yes, that is indeed a bad habit. In general, when you analyze complexity, you must specify:

Are you talking about space complexity, step complexity, time complexity?
Are you talking about best-case, worst-case, amortized worst-case, average case, expected case?
What is your machine model? (I.e. what operations exist?)
What is your cost model? (How long do those operations take?)
What are you actually counting? (Comparisons, stores, loads, arithmetic operations, bit operations, etc.)
How do you define "length of the input"? (Number of elements, number of bits, etc.)
What is the distribution of your inputs? (In case of average or expected complexity.)

Usually it's related to the input, but it may be the value or length in bits or something else.

For data structures, it is usually the number of elements. For strings, it already gets trickier: is it the number of bytes, number of octets, number of `chars, number of code points, number of characters, number of graphemes, number of grapheme clusters?
One thing that catches many people out is that for numbers, it is usually not the magnitude, it is the length (i.e. the number of "digits" or bits), which is the logarithm of the magnitude.

Am I right that it's usually inferred from context?

Indeed. However, as mentioned above, for numbers, it is often inferred wrong.
The reason why we usually use the length of numbers is that arithmetic operations depend on the number of digits, not on the magnitude of the number: adding 1+1 take the same time as adding 4+4, but adding 10+10 takes twice as long. Adding 4999+5000 doesn't take 5000 times as long as adding 1+1, it only takes 4 times as long.

For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed.

No, it would not. O(1) means the number of comparisons (which is what we are usually counting when talking about "searching") is bounded by a constant. In your example, you will never need more than 100 comparisons, therefore the number of comparisons is bounded by 100, which is a constant.
Therefore, the time complexity is O(100), which is the same as O(1).


How does a language abstract away from underlying byte machines?

I'm assuming you are really asking

  how is it possible that the same source code can be compiled to different architectures?

In order to achieve this feat different systems use different solutions.

Interpreter
Some languages use an interpreter. In this case there is no underlying architecture. The source code gets interpreted as written.

Virtual machine using byte code
Languages like C# and java compile to intermediary code (called byte code) for a virtual machine.
A runtime then executes this code somewhat like an interpreter would.
Frequently a just-in-time compiler further compiles (critical parts of) the byte-code to actual machine code.
So Java and C# do not care about the actual machine.

Virtual machine as intermediary target
Other compilers use the LLVM architecture. LLVM presents a virtual machine to the front end and a compiler using LLVM compiles for this virtual machine.
Specific LLVM backends tuned to a specific CPU architecture further compile this intermediary code to actual machine code.
LLVM differs from Java in that LLVM always compiles all code to machine code and it does not force any specific runtime upon the compiler.

Direct compilation
Traditional compilers like gcc (gnu C) compile the code to a specific architecture in a direct manner. Every architecture requires a different compiler which follows the language rules to create assembly code.
Maintaining separate compilers for different CPU architectures whilst ensuring all those abstractions work the same on all targets is accomplished through sheer hard work and coordination between compilers.

Hence the rise of intermediary virtual machines as compilation targets.

  To what extend does a compiler abstract away the underlying CPU?

This differs per language. Older languages like C tend to less abstraction.
The trend in newer languages is towards more abstraction.
Some languages offer both abstract types (always the same irrespective of architecture) as well as implementation dependent types (different for different architectures).
An example of this is a NativeInt type that is 32 bits on X86 and 64 bits on X64.

CPU's do some of the abstraction
The other element in play is that CPU's are converging towards a single 'constellation'. More and more CPU architectures are using the X64 model of 32 bit integers and 64 bit memory.
Also many CPU's are backwards compatible with their predecessors.
As long as a compiler produces code that runs on a current or previous version of a CPU that CPU will run it.
So in that case it's the CPU that abstracts away (some of) the differences.

  ... Byte machine

A byte machine does not exist.
There is byte code, which is code for the virtual machine used by e.g. Java.
and there is machine code, which is what a CPU consumes.

Memory management
You talk about memory management.
This is a subject completely different from abstraction.
Every CPU architecture handles memory in essentially the same way.
All but the most esoteric CPU's have a stack and use pointer logic to address the heap.
The fact that e.g. Java and C# use a garbage collector is not technically abstraction, but relates to resource management.
How resource management gets done depends upon the runtime library in use by that language.

Dynamic types
Dynamic types are invented to solve the problem of buffer overflows (arguably the number one security issue facing computing today).
If the runtime library handles string and array management then the burden on the programmer decreases.

  How does a languages abstract away managed or dynamic types

By using a runtime library.
All usage of dynamic and managed types gets translated into calls to the runtime library.
E.g. when using a dynamic string, the runtime library handles the reference counting, copy-on-write and growing and shrinking the storage as needed.
None of these actions are visible in the source code.


What is the minimum square partition of an almost-square rectangle?

A similar question was asked on Mathoverflow. The commenters mentioned a paper of Kenyon, which shows that the minimum number of squares required to tile a $w \times (w-1)$ rectangle is $\Theta(\log w)$. See also a related paper of Walters.

You can tile a $(4t+7) \times (4t+6)$ rectangle using only $t+5$ squares (for $t \geq 0$).


Get the previous and next values of a string in lexicographic order

Computing the previous and next lexicographic string is the same as subtracting and adding 1 to a number, only your number is encoded in some higher base corresponding to your alphabet. I presume you already know how to add and subtract 1, but if not, there are many online resources explaining that.

You mention UTF-8, which is not quite an ordered alphabet. Yet your SQL interpreter has some specific rules for ordering strings, and is should include an ordering of the actual alphabet (UTF-8 or smaller).


Why is this argument for $P\neq NP$ wrong?

Sure, you just have to be careful thinking about what it means to have an oracle.

The problem comes from an annoying abuse of notation we use in CS: In the statement $P=NP$, $P$ refers to a set of languages. But in the statement $P^A = NP^A$, $P$ refers to a class of Turing Machines (determinstic polytime TMs). You should think of these two $P$s as of completely different types.

So even if the two sets of languages $P$ and $NP$ are the same, deterministic polytime TMs still do not work in the same way as nondeterministic ones. In particular, given an oracle, a nondeterministic TM can "ask many questions at once", which is something the regular TM cannot do. So even if they decide the same set of languages when neither type of machine is given additional help, the oracle might help one type of machine more than another.


How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?

If I understand your problem correctly, the tokens (lanterns) can be placed every $x$ blocks (starting from $0$) if and only if $x>2$ is a divisor of  $n-1$.
For example, if the array has $n=31$ elements the valid values of $x$ are $3,5,6,10,15,$ and $30$.


which of the following languages are Recursively Enumerable?

$B$ is r.e, but $A$ is not.

You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s_1, s_2,...$ are strings on $0$ and $1$ in canonical order, then starting from $n=0$ you run $M$ for $n$ steps on $s_1, s_2,..., s_n$, that is, for each $n$ run $M$ on all $s_1, s_2,..., s_n$ for $n$ steps (not just 1 step for $s_1$, 2 steps on $s_2$,... careful!). Each time just check if a string is accepted. If more than two strings are accepted then halt with accept, otherwise go on.

However we cannot use the same approach for $A$ since we cannot check infinitely many strings and say that they are not accepted except 1 or 2 certain strings IN FINITE amount of time. In other words, suppose we somehow determined that $M$ has accepted two strings, then how can we decide that the rest of infinite number of strings are not accepted by $M$ in finite amount of time?

You can also use the Rice's theorem for recursive index set.
$A$ violates the containment property in the Rice's theorem. Namely, if $L$ is in $A$ and $L \subseteq L'$ for some r.e. $L'$, then $L'$ is in $A$. Assume $L=\{00, 11\}$. Then $L$ is in $A$. Let $L'=\{00,11, 01, 10\}$. Then $L \subseteq L'$ where $L'$ is clearly r.e. But $L' \notin A$.

Update (upon comment)

Task: We want to systematically simulate each TM on every input on $\{0, 1\}$.

Solution: First note that there is a one-to-one correspondence $f$ between the set of natural numbers $N$ and $N^3$ all 3-tuples of natural numbers. So, we can effectively convert each integer $m$ into the corresponding 3-tuple $<i,j,k>$. This means that if we start to count all integers then we can enumerate all possible 3-tuples, so that each 3-tuple is eventually reachable in a finite amount of time.

Now, assume we we have fixed enumerations of all TMs and strings on $0$ and $1$, e.g., $M_i$'s and $s_j$'s.

1) Set $n =0$

2) $<i, j, k> = f(n)$  <= compute 3 tuple

3) Simulate the Turing machine $M_i$ on input $s_j$ for $k$ steps.

4) If $M_i(s_j)$ halts (after $k$ steps) then do whatever you want to do

5) increase $n$ by 1 and go to step 2)

Thus, every machine "has a chance" to run on every input for arbitrary number of steps, fair isn't it?

If some machine, say, $M_{332}$ halts on input $s_{12}$ then there is an integer, say, $461$, so that $M_{332}(s_{12})$ halts in 461 steps. So, if for example $55993$ corresponds to the 3-tuple $<332, 12, 461>$, then when $n$ reaches $55993$ (in the algorithm above) you detect that $M_{332}$ halts on input $s_{12}$.


Choosing a non-cryptographic hash function for language with no unsigned integers

The offset is unlikely to matter.  As the FNV web page says:

  almost any offset_basis will serve so long as it is non-zero

The multiplication is potentially more important.  The FNV-1 hash is defined to use unsigned multiplication modulo $2^{32}$, but if UnrealScript only has signed 32-bit integers, presumably you have no way to do that kind of unsigned multiplication.  At that point you're no longer using the official FNV-1 hash; you're using something different.  I suspect it's still fine, though.


How to prove that every regular language can be obtained by some FA?

These definitions are from Wikipedia

In theoretical computer science and formal language theory, a regular
language is a formal language that can be expressed using a regular
expression...
...
Alternatively, a regular language can be defined as a language
recognized by a finite automaton.

You can define a regular language as a set of strings accepted by some  FA. In this case you don't have to prove anything since a regular language is recognized by a finite automaton by definition.
But if you define a regular language as a formal language that can be expressed using a regular expression then you can prove that it is accepted by some FA using Thompson construction, i.e. prove the equivalence of regular expressions and finite automata.


Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace

Eventually I ended up solving this for $O(n)$ gates. I wrote up a trilogy of blog posts on it.

Constructing Large Controlled Nots (classically, with an ancilla)
Constructing Large Increments (classically, with an ancilla)
Using Quantum Gates instead of Ancilla Bits

Of course it would suck if you found this twenty years from now and my website was long gone, so the basic steps follow in quickly-described image form.

1. Bootstrap a Borrowable Ancilla Bit

Use a square root and its inverse to reduce the maximum number of controls  by one, creating an uninvolved wire for each operation. Then iteratively move controls off of non-Not operations, and re-arrange the cruft that results into large increment gates and single-qubit phase gates.

2. Use Single Ancilla Bit to Cut Operations in Half

For each large operation, use the uninvolved wire as a borrowed ancilla bit. Use it to transform the huge increment and controlled-not gates into smaller operations that each have approximately half of the wires uninvolved. Repeat twice, if required for the next step to have enough working space.

3. Use Many Ancilla Bits to Finish

For each still-too-large operation, borrow the many uninvolved wires as ancilla bits. Use them to get all the way down to Toffoli-or-smaller gates.

Those three steps will get you all the way from a fully-controlled-not to linearly many Toffoli, CNOT, and single-qubit gates. There's a few implied pieces, like how to merge a control into an increment gate, but they're pretty simple.

(Sorry for the inconsistent style of the diagrams.)


Whats is the meaning of polynomial run-time in input size ?

I think I understand the question enough to answer it. Yes polynomial time is the time the algorithm takes relative to the size of the input. So if your input has size $n$, PTIME means the running time is a polynomial in $n$. Sure if you replace $n$ with some exponential $n=e^p$ you get an exponential time relative to $p$ (assuming the algorithm was not running in constant time). But that does not invalidate the concept of polynomial time anymore than saying that $f(x)=2x$ is a linear function but you can substitute $x$ with $y^{y^y}$ on both sides, i.e $f(y^{y^y})=2y^{y^y}$; it is an intrinsic property of $f$ of being linear in its argument.

This is further discussed on an example at https://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

This issue of having to express the input size as a function of another "quantity" does occur (implicitly) in the context of reducing one problem to another in order to feed it to an existing algorithm. In that context, in order to avoid the obvious gotcha that would "prove" an EXPTIME problem is a PTIME one by using an exponential-size encoding, only polynomial-time reductions are allowed. So, if $p$ is the size of a problem, you can encode it in PTIME as another problem of size polynomial in $p$. But you can't encode it (taking only PTIME) as problem of exponential size in $p$.


Subtree with minimum sum of nodes' costs

For a node $i$ with children $j_1,\ldots,j_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence
$$
\tau(i) = \min(0,  \sigma(i) + \tau(j_1) + \cdots + \tau(j_d)).
$$
Indeed, there are two cases to consider. Either we take no vertex, in which the answer is 0. Otherwise, we must take $i$ itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of $i$.

Like all such recurrences on trees, this one can be evaluated in linear time in many ways.


What is the simplest example of a prob whose complement does not have the same complexity?

The notion of "complex" depends entirely on your model of computation. For example, if you're using DFAs, then by just about every conceivable measure every problem has the same difficulty as its complement. On the other hand, if you're using PDAs as your model of computation, many languages can be recognized by a PDA even though their complements can't. For example, the language

  { ww | w ∈ {a, b}* }

is not recognizable by any PDA, but its complement is.

In the land of NP, we don't know much about the relative difficulties of problems and their complements. It's an open problem whether the complements of any NP-complete problems are in NP.

Looking at decidability, a problem is decidable if and only if its complement is decidable. However, the same is not true of recognizability. The halting problem is recognizable, but its complement isn't.


What are the examples of the easily computable "wild" permutations?

Yes, such things exist.  They have been studied in the cryptographic literature: the key name is "format-preserving encryption".

To learn about this subject, I suggest taking a look at https://en.wikipedia.org/wiki/Format-preserving_encryption and https://crypto.stackexchange.com/q/16561/351 and https://crypto.stackexchange.com/q/504/351 and https://crypto.stackexchange.com/q/20035/351 and https://crypto.stackexchange.com/q/18988/351 and
https://crypto.stackexchange.com/questions/tagged/format-preserving.  You could also construct a suitable block cipher yourself using a Feistel construction, but it's probably better to use a standard scheme that has been analyzed in the literature.

There are many constructions.  The best one will depend on the specific value of $n$ in your application.  Take a look at the schemes in the cryptographic literature, then if you have a more specific question about how to use one of those schemes, you can ask either here or on Crypto.SE.


Can multiple tasks in an RTOS share one stack to save memory?

As long as they do not overlap in execution, the tasks can re-use the same stack space.  That is, they can not safely execute in parallel or else one task will corrupt another's stack space.

This corruption may occur due to local variables or parameters stored on the stack, or even due to the occurrence of an ISR.

Hope this helps


Interpolation on marching cubes algorithm

I worked it out on my own. I'm trying to write it down correctly so it's readable for newcomers.

Introduction

First of all, interpolation itself requires that there are float values and not binary values. This gives the ability to create different edge-crossing-vertices. How it's going I'm explaining now.

The interpolation which is needed here is linear interpolation.
For understanding purposes I'll explain it here too.

General Interpolation

After all, what is interpolation? Well good question.
Interpolation is described as name for algorithms which smooth a given input of data e.g. points (with n-dimensions). Simpler there are points searched between the points for a given interpolation value. First it's required to give the points a base so that's clear where points are searched for in between. After that a specific algorithm for the interpolation has to be chosen. There are different kinds of interpolation algorithm out there each for a specific application.
Best known is linear interpolation which results for a value one point on a line which crosses two input points.

The formula for linear interpolation (2D here) is as following (simply maths):
$$
y = y_{0} + (value - x_{0} ) * \frac{y_{1} - y_{0} }{x_{1} - x_{0}}
$$
with $$ value \in   \mathbb{R} \wedge 0 <= value <= 1 $$

After all with this formula it's possible to apply interpolation on the vertices of the marching cubes algorithm which requires following rules.

The voxels must have a floating value instead of a binary value.
The value of the voxels must be only between zero and one
There must be a boundary value be declared which describes whether a voxel is supposed to be in surface.

Looking back to the blog the boundary value is called the iso surface value.
This value describes as explained whether a voxel is being asumed to be in the surface so for acquiring the edge crossing. This is important to know because without it you wouldn't find out where even a edge-crossing computation is needed.

The interpolation is done on each coordinate of the two voxels position where and crossing-edge vertex is.
The implementation is quite easy and looks like this (extracted from here):

/*
   Linearly interpolate the position where an isosurface cuts
   an edge between two vertices, each with their own scalar value
*/
XYZ VertexInterp(isolevel,p1,p2,valp1,valp2)
double isolevel;
XYZ p1,p2;
double valp1,valp2;
{
   double mu;
   XYZ p;

   if (ABS(isolevel-valp1) < 0.00001)
      return(p1);
   if (ABS(isolevel-valp2) < 0.00001)
      return(p2);
   if (ABS(valp1-valp2) < 0.00001)
      return(p1);
   mu = (isolevel - valp1) / (valp2 - valp1);
   p.x = p1.x + mu * (p2.x - p1.x);
   p.y = p1.y + mu * (p2.y - p1.y);
   p.z = p1.z + mu * (p2.z - p1.z);

   return(p);
}

Conclusion

The interpolation of the edge-crossing vertices is a nice feature for smoothing the presentation of voxels.However the interpolation relies on that there are already floating values which means that it cannot smooth your existing binary data. For such cases different algorithms and approaches are needed.


If a grammar is SLR(1) then are the LALR and SLR tables the same?

The tables aren't the same.  The effect is not visible on correct inputs but on erroneous one.  The SLR tables may indicate that a reduce operation is in order and then detect that the input is erroneous after the reduction when the LALR one will directly indicates that the input is erroneous without doing any reduction.  That may have an influence on automatic error message generation and error recovery which are using the state of the push-down automaton to do their work.


Is my implementation of genetic algorithm correct?

No, that does not make sense.

What you have there is a toy example. In any application, the algorithm will not know the goal -- otherwise you wouldn't need it! That is, you don't have any way of known whether a mutation is benefitial before executing it.

What's more, mutating away from the optimum is an essential part of the algorithm, and can be shown to be necessary for it to work well (otherwise you get stuck in local optima more easily).


How do you rank the strings represented by a regular expression?

Suppose you want to encode an element of $\binom{[n]}{k}$, that is, a subset of $\{1,\ldots,n\}$ of size $k$. There are $\binom{n}{k}$ such subsets. FPE functions know how to handle encoding and decoding of integers in the range $\{1,\ldots,M\}$, for an $M$ of your choice. To use such an FPE function in your case you will have to translate an element of $\binom{[n]}{k}$ to an integer in $\{1,\ldots,M\}$ for $M = \binom{n}{k}$ (ranking) and back (unranking), efficiently.

How do you efficiently rank and unrank elements of a domain like $\binom{[n]}{k}$? For which domains is it possible? The video describes one scenario where this is possible, and one general algorithm for handling this scenario. If your scenario is different then you might still be able to rank and unrank efficiently, but you will have to use a different approach.

The scenario described by the video (which I haven't watched) is probably that of languages accepted by a DFA with a small number of states. Such a language can be ranked and unranked efficiently, and the algorithms use the DFA which accepts the language. This is how the DFA comes in – it is used by the ranking and unranking algorithms. Hopefully these algorithms are described in the video, but otherwise you can ask another question here.


How can i compute tag-index-displacement bits of an address if cache size is not a power of two?

One way is by having multiple cache banks, each of which is a power of two in size. For example, 3 banks of 16kB each. The first 3 (bank_num) bits can be used with one-hot encoding to decide which bank would need to be checked to access the requested data (or to write to).

The rest of the cache access would proceed as usual (look up TLB to get tag bits, index into cache in parallel, etc.)

However, usually non-powers of two caches are not used because the IPC to cache size curve is such that it you find the sweet spot very close to a number that is a power of two (or you don't lose significantly in IPC by moving to a power of two).


Encoding huge number of tape-symbols of a turing machine in the simulation of the turing-machine using real computer

You are interpreting this statement backwards - he is not calculating how many symbols can 30 gigabytes represent, he is calculating how many symbols can be represented by using 30 gigabytes to represent a single symbol!  That would be necessary to be able to approximate a calculation where each symbol is an infinitely-precise real number.


Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$?

Here is a particularly simple algorithm for the slightly simpler language $\{\alpha\alpha \mid \alpha \in \{a,b\}^*\}$; a similar approach works in your case.

The Turing machine starts by checking whether the input is empty (if so, accept) and whether it has even length (otherwise, reject). Next, we are going to find the midpoint of the input. The idea is to put a "chip" on each end of the input, and at each step, advance each chip toward the middle, until the two chips coincide. If done correctly, we can mark the middle of the input, which is the starting point of the second copy of $\alpha$. All that remains to be done is to check that the first half of the input is identical to the second half, which can be done using a simple iteration.


Insertion and deletion complexities for a linked list and array

The array may need to be reallocated if there are too many free cells, and this costs $O(n)$ (non-amortized)
For arrays, the array portion which comes after the affected element must be moved one position left or right, so that's $O(n)$. For lists, it depends. If you have the pointer to the previous cell w.r.t. the inserted/deleted one, this can be done in $O(1)$. If you don't, and you only have the pointer to the list head, then you have to scan the list -- half the list, on average, will be scanned, costing $O(n)$.


Data Compression :Compress a Compressed File

The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.


Hint: Dynamic programming on this subproblem: "Can I get a sum of $x$ if I can use only the $k$ smallest coins?"


Actually, it is pretty simple. Let $T_n$ be the running time for a given array $A[1,...,n]$. As you've mentioned, we first sort $A[1,...,n - 1]$ whose running time is $T_{n-1}$ (since it has $n-1$ elements) and then we inset $A[n]$ to the sorted list, whose running time is $O(n)$ (since we need iterate over the whole array at the worst case).

Therefore, $T_n = T_{n-1} + O(n)$. And do not forget about the base case which is $T_1 = O(1)$.


Is it compulsory that every infinite set be non regular?

You must have misunderstood the comment, since the set $\Sigma^*$ is infinite and regular. The correct notion of "infinite" is given by the Myhill–Nerode theorem. Every language is associated with a set of states, and a language is regular iff the set of states is finite.

A state in a language $L$ is a set of strings $S$ that are interchangeable with respect to $L$ in the sense that for all words $x$, either all words of the form $sx$ (where $s \in S$) are in $L$, or all are not in $L$. In the example $L = \{0^n 1^n : n \geq 0\}$, the states are $\{ 0^{m+n} 1^n : n \geq 0  \}$ for each $m \geq 0$, all other words forming another state. You can see that there are infinitely many states, and so the language is not regular.

Every regular language has a DFA whose states correspond to the states described above. This DFA is known as the minimal DFA. A "minimal DFA" for $\{ 0^n 1^n : n \geq 0 \}$ would need to have infinitely many states, since the DFA would have to remember how many zeroes it has seen so far, or more generally how many ones it expects at this point (if the next symbol is a one). No finite automaton can remember that much information, so the language isn't regular.


Let $T(n)$ denote the total number of updates to the variable when $n$ people have entered the room. For example, with $n=3$ there will be $3!=6$ possible orders where the heights are $1, 2, 3$. Notice that once the height 3 person enters, no further updates will occur, so let's group the six possible arrangements by when the height 3 person enters:
$$\begin{array}{ccc}
\mathbf{3}21 & \mathbf{3}12 \\
1\mathbf{3}2 & 2\mathbf{3}1 \\
12\mathbf{3} & 21\mathbf{3} \\
\end{array}$$
For each of these arrangements, let's count the number of updates we have to make before we see the tallest person. In the two arrangements where the height-3 person arrives first, there are 0 earlier updates. In the second row above, there will be 1 update we have to make before the tallest person arrives and in the third row there will be either 1 or two updates before the tallest person arrives: arrangement $12\mathbf{3}$ will require 2 updates (one for the height-1 person and another for the height-2 person and the arrangement $21\mathbf{3}$ will require 1 update, for the height-2 person. In this $n=3$ case, then, we'll have $0+2+3$ total prior updates (0 in row 1, 2 in row 2, and 3 in row 3). To this add the $3!=6$ updates for the tallest person, giving us a total $T(3)=5+6=11$.

Now let's look at the general case for $n$ people. As we did above, let's group the $n!$ possible arrangements by when the height-$n$ person arrived. Denote this tallest person by $X$ and the rest of the people by dots. As we did above, we'll defer counting the last update until later.

We'll have these possibilities, each of which can happen in $(n-1)!$ ways:
$$\begin{array}{cc}
\text{arrival of }X & \text{arrangement}\\
1 & X\circ\dotsc\circ \\
2 & \circ X\circ\dotsc\circ \\
3 & \circ\circ X\circ\dotsc\circ\\
\dotsm & \dotsm \\
n & \circ\dotsc\circ X
\end{array}$$

For each row above we'll count the total updates before the tallest person arrives: Obviously if the tallest person arrives first, we'll have no prior updates, so the first row above will give a total count of 0. Each of the following rows will look like this:
$$
\underbrace{\circ\dotsc\circ}_k\ X\ \underbrace{\circ\dotsc\circ}_{n-1-k}
$$
The first set of $k$ dots can be filled with the heights $\{1, 2, \dotsc, n-1\}$ and there are $\binom{n-1}{k}$ ways to choose these sets, each of which will contribute $T(k)$ updates. The last set of $n-1-k$ dots can be filled with the remaining numbers in $(n-1-k)!$ ways. Thus each row in the table will contribute
$$
\binom{n-1}{k}T(k)(n-1-k)!
$$
to the total of prior updates. Adding these and including the $n!$ updates for the tallest person we have the recurrence relation
$$\begin{align}
T(n) &= n! + \sum_{k=1}^{n-1}\binom{n-1}{k}T(k)(n-1-k)!\\
 &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!(n-1-k)!}T(k)(n-1-k)!\\
 &= n!+ \sum_{k=1}^{n-1}\frac{(n-1)!}{k!}T(k)\\
 &= n!+ (n-1)!\sum_{k=1}^{n-1}\frac{T(k)}{k!}\\
\end{align}$$
Divide both sides by $n!$ to get
$$
\frac{T(n)}{n!} = 1 + \frac{1}{n}\sum_{k=1}^{n-1}\frac{T(k)}{k!}
$$
and remember that the average number of updates, $U(n)=T(n)/n!$ which gives us.
$$
U(n) = 1 + \frac{1}{n}\sum_{k=1}^{n-1}U(k)
$$
Now we'll find a simple closed form for this:
$$\begin{align}
U(n) &= 1+\frac{1}{n}\sum_{k=1}^{n-1}U(k)\\
 &= 1+\frac{1}{n}\left(\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1) &\text{pulling out the last term}\\
 &= 1+\frac{n-1}{n}\left(\frac{1}{n-1}\sum_{k=1}^{n-2}U(k)\right)+\frac{1}{n}U(n-1)\\
 &= 1+\frac{n-1}{n}(U(n-1)-1)+\frac{1}{n}U(n-1) & \text{definition of }U(n-1)\\
 &= U(n-1)\left(\frac{n-1}{n}+\frac{1}{n}\right)+\left(1-\frac{n-1}{n}\right)\\
 &= U(n-1) + \frac{1}{n}
\end{align}$$
Whaddya know? With $U(0)=0$ we just have
$$
U(n) = 1 + \frac{1}{2}+\frac{1}{3}+\dotsm+\frac{1}{n} = H(n)
$$
the $n$-th harmonic number, as it's known and it's also known that $H(n)$ is asymptotic to $\ln n$.


Algorithm for finding strongest connection for a user on social network

Your algorithm doesn't work.  BFS doesn't explore all paths.  One of the paths you haven't explored might have much higher strength than all the ones you have explored.  There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview).  I'll let you have the fun of finding it.


How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal':

If the segment $s$ between $A,B$ is a diameter, construct the lines $k,l$ as follows: line $l$ is the unique line perpendicular to $s$ and through $A$. Line $k$ is the unique line perpendicular to $s$ and through $B$.

I claim that the lines $l,k$ are parallel lines of support. These lines are parallel, as they are perpendicular to the same segment. To see that they are lines of support, suppose to the contrary that $l$ is not a line of support. As $A$ lies on the boundary of $P$ and in $l$, $l$ intersects the boundary of $P$. So $l$ can only not be a line of support if it intersects the interior of $P$. But this means that there is a point $X$ in $P$ ('beyond' the line $l$) such that $|XB|>|AB|$, contradicting the fact that $s$ is a diameter of $P$!

So $l$ is a line of support. Analogously, $k$ is a line of support as well. So, as there is a parallel pair of lines of support through $A$ and $B$, $A$ and $B$ are anti-podal.

$\square$

The picture below sketches the situation where $A,B$ are endpoints of a diameter of $P$. A position where the hypothetical point $X$ could lie is also shown (it is clear that here there can be no point $X$ such that it lies in $P$!)  Note that while $C,D$ are not endpoints of a diameter, they are anti-podal!

Be careful though, as the converse of the statement, 'Any segment such that the endpoints $A,B$ of that segment are antipodal in $P$ is a diameter in $P$' is false. As a counterexample, take a (non-square) kite (or take the sketch above). Clearly, the two pairs of opposing corners are anti-podal, but only one of the segments between the pairs is a diameter! Your informal attempt seems to try to prove this. As what you're trying to prove is false, it isn't surprising that formalizing the proof fails!

Note that I don't use the fact that $P$ is convex. You can check that this proof also works for non-convex, but simple polygons (it might even work for non-simple polygons, but these things are awful, so I'd rather not make claims about them). Note that in the case of convexity, the diameter need not necessarily be contained within the polygon, but all definitions still apply.


Difference between fractional knapsack & greedy solution

The fractional Knapsack problem isn't solved using Dynamic Programming, but can be solved using a greedy algorithm. Item A is \$50/unit, B is \$5/unit and C is \$40/unit. The greedy method is to use as much of the highest value items as possible, which gives the solution on the image.

Dynamic Programming allows you to solve the problem when you cannot split the items.


Finding a minimum set of dependencies in a cycle-filled dependency graph

Decompose your graph into strongly connected components.  Now each strongly-connected component (SCC) of size $>1$ contains a cycle.

Let $G=(V,E)$ be the dag of SCCs obtained by this decomposition.  Sometimes $G$ is called "the metagraph".  Let $S \subseteq V$ be the set of SCCs of size $>1$.  Now our algorithmic problem is as follows:

  Given the dag $G$ and the set $S$, find a minimum-size set $T \subseteq V$ such that for every $v \in S$, there's a path from $v$ to some vertex of $T$.

The rest of the answer below is incorrect, but I'll leave the problem statement above in case it helps someone else find a clean algorithm.

This problem can be solved using a network flow algorithm.

In particular, this problem can in turn be rephrased as something akin to a minimum-cut problem: if we add a source vertex $s$ with an edge to each vertex of $S$ and a sink vertex $t$ with an edge from each vertex of $T$ to $t$, we want to find a minimum-size set of vertices that completely disconnect $s$ from $t$.  Notice that this isn't quite the normal minimum-cut problem, because here we care about minimizing the number of selected vertices rather than minimizing the cost of the edges that cross the cut, but it's close.

Here's how we can solve this problem.  For each vertex $v \in V$, we add two vertices $v_\text{in},v_\text{out}$, and we add an edge with cost 1 from $v_\text{in}$ to $v_\text{out}$.  Also, we replace each edge $(v,w) \in E$, with the edge $(v_\text{out}, w_\text{in})$, and we make this edge have cost $\infty$.  We add a source vertex $s$ and, for each $v \in S$, we add a source vertex $s$ and an edge of capacity $\infty$ from $s$ to $v_\text{in}$.  We also add a sink vertex $t$ and, for each $v \in V$, we add an edge of capacity $1$ from $v_\text{out}$ to $t$.  Let $G'=(V',E')$ be the resulting graph.

Finally, we find a minimum $(s,t)$-cut in $G'$.  This can be done by using a standard network flow algorithm to compute the maximum $(s,t)$-flow, and then using the Ford-Fulkerson min-cut/max-flow theorem to reconstruct a minimum $(s,t)$-cut.  Suppose the cut is $(U,V'\setminus U)$, where $s \in U$ and $t \notin U$.  Then for each vertex $v \in V$ such that $v_\text{in} \in U$ and $v_\text{out} \notin U$, we add $v$ to $T$.  This gives us a set $T$ of vertices that, in $G$, disconnect $s$ from $t$, and by construction, the size of $T$ is minimal.


Fastest way to solve a system of linear equations

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices.  Therefore, you can find a solution to a system of $n$ linear equations in $n$ unknowns in $O(M(n))$ time.  For instance, Strassen's algorithm achieves $M(n) = O(n^{2.8})$, which is faster than Gaussian elimination.  See https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion.

Rather than trying to implement this yourself, I would suggest using a library: e.g., a BLAS library.


If no two intervals end at the same point then you can simply sort them in increasing order of their right endpoint, and all of them will be visible.

If more than two intervals can end at the same point, then sort the intervals $[a,b]$ in increasing order of $b$ and break ties in decreasing order of $a$.

Assume w.l.o.g., that there are no identical intervals (you can discard multiple copies of the same interval, since at most one copy will ever be visible). We will show that the above algorithm is optimal with an exchange argument.
Suppose that an optimal order $S$ of the intervals places two intervals in a different order than the one computed by the algorithm. Let $[a,b]$ and $[a',b']$ be the first two consecutive intervals in $S$ that are in the "wrong" order, that is:

$b>b'$; or
$b=b'$ and $a<a'$.

we will show that $[a,b]$ and $[a',b']$ can be swapped without decreasing the number of visible intervals.

If $[a,b]$ is not visible, then swapping $[a',b']$ with $[a,b]$ cannot decrease the number of visible intervals. Therefore we assume that $[a,b]$ is visible.
Let $p \in [a,b]$ be the largest point that is not covered by any the intervals preceding $[a,b]$.

If $p \not \in [a',b']$, then swapping $[a',b']$ with $[a,b]$ yields a solution $S'$ in which (i) $[a,b]$ is visible in $S'$, and (ii) if $[a',b']$ is visible in $S$ then it is visible in $S'$. Assume then that $p \in [a',b']$.

If $[a',b']$ is not visible then swapping $[a',b']$ with $[a,b]$ yields a solution in which $[a',b'] \ni p$ is visible (therefore the number of visible intervals cannot decrease). Assume then that $[a',b']$ is visible.

If $[a,b] \supset [a',b']$ then $[a',b']$ would not be visible, therefore we are in the first case ($b>b'$). By the choice of $p$, all the points of the subinterval $(p,b]$ of $[a,b]$ are not visible. Therefore $S$ must contain an interval $[a'',b'']$ that precedes $[a,b]$ and is such that $b'' \ge b$ and $a'' > p$.
This cannot happen since $[a'', b'']$ and $[a, b]$ is a pair of intervals in the wrong order which appears before the pair $[a,b]$ and $[a', b']$ in $S$.


Superpolynomial means $n^{\omega(1)}$, that is, growing faster than any polynomial. More clearly, $n^{f(n)}$ for some function $f$ satisfying $\lim_{n\to\infty} f(n) = \infty$.


Does a subcubic algorithm exist for the following problem?

There exists a quite practical approach that works in $O(n^3 / w)$ time, where $w$ is the number
of bits in the processor word. The main idea is that you iterate over
the elements of the matrix one by one in the increasing order (break ties arbitrarily)
and "switch them on". Consider the moment when the largest element of
some triple $a_{ij}, a_{ik}, a_{jk}$ is switched on. For simplicity, let's assume
that the said element is $a_{ij}$. It is natural to add the value of the triple
to the answer now, when the last element is switched on. So we have to count
the number of possible $k$'s such that $a_{ik}$ and $a_{jk}$ are already switched on (that would be the number of triples, here $a_{ij}$ is the largest element, so they were completely switched on just now). Here we can speed up the naive $O(n)$ implementation by using bit optimisation.

For details you can refer to the following implementation in C++11 that
should work for $n \leqslant 5000$, $|a_{ij}| \leqslant 10^9$
(it is not very optimized; however,
it still beats naive summation for $n = 5000$ by large margin at least on my machine).

// code is not very elegant,
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r)
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

If you consider using bit optimisations cheating,
you can use four russians method to the same result here,
yielding a $O(n^3 / \log n)$ algorithm, which should be less practical
(because $w$ is pretty large on most modern hardware)
but is theoretically better.
Indeed, let's choose $b \approx \log_2 n$ and keep each
row of the matrix as an array of $\lceil \frac{n}{b} \rceil$ integers
from $0$ to $2^b - 1$, where the $i$-th number in the array
corresponds to the bits of
the row ranging from $ib$ inclusive to $\min(n, (i + 1)b)$ exclusive
in $0$-indexation. We can precalculate the scalar products of every two
such blocks in $O(2^{2b} b)$ time. Updating a position in the matrix
is fast because we are changing only one integer. To find the scalar product
of rows $i$ and $j$ just iterate over arrays corresponding to that rows,
look up scalar products of the corresponding blocks in the table and sum up the
obtained products.

The above paragraph assumes that operations with integers $\leqslant n$ take $O(1)$ time. It is quite common assumption, because it usually
does not actually change the comparative speed of the algorithms (for example,
if we don't use that assumption, brute force method actually works in
$O(n^3 \log n)$ time (here we measure time in bit operations) if $a_{ij}$ take integer values with absolute values at least up to $n^{\varepsilon}$ for some constant $\varepsilon > 0$
(and otherwise we can solve the problem with $O(n^{\varepsilon})$ matrix multiplications anyway); however the four russians method suggested
above uses $O(n^3 / \log n)$ operations with numbers of size $O(\log n)$ in that
case; so it makes $O(n^3)$ bit operations, which is still better than brute force despite the change of the model).

The question about existence of $O(n^{3 - \varepsilon})$ approach is still interesting, though.

Techniques (bit optimisations and four russians method) presented in this answer are by no means original and are presented here for completeness of the exposition. However, finding a way to apply them was not trivial.


What is "dynamic" about dynamic programming?

Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.


Advantages of using prime number as interval during a shell sort?

It is still an open question what the best gap sequence for shell sort would be; and what the performance of shell sort would be with an optimal sequence.

The "holy grail" for comparison based sorts is O(lg(n!)) ~= n*lg(n) -n performance.
No one has ever found a gap sequence for shell sort that achieves that.

Here's what we do know-
1= the last gap must always be 1 (insertion sort)
2= there should be no more than lg(n) -1 gaps
(thus the lg(n) -1 gap is always going to be 1)
3= the gaps should at least be relatively prime to each other.
4= the gaps should be between a factor of 2 or 3 of each other
5= the gaps can not be expressed by a closed form math formula if you want worst case performance better than O(n*lg^2(n)) or O(n^(3/2))

Thus using just primes closest to (n/2)^i for the first lg(n)-2 passes can be a very good choice, but
a= we as of yet can not prove such a gap sequence would be optimal, and
b= figuring out what the gap sequence is for any given size of data set is non trivial if all of our gaps are primes.


Is there a O(log n) algorithm for matrix exponentiation?

Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M


NP-Completeness of modified decision problems

It depends on the problem. For, say, clique or independent set, the problems become trivial if you change the direction of the inequality: $\emptyset$ is always a clique/independent set of size $\leq k$.

On the other hand, the travelling salesman problem remains NP-complete if you ask for a tour of length at least $d$ instead of at most $d$.  To see this, suppose that you want a tour of graph $G$ of length at most $d$. Let $m$ be the length of the longest edge in $G$, and let $G'$ be the graph that's identical to $G$ except that, if an edge has length $\ell$ in $G$, then it has length $m-\ell$ in $G'$.  Now, any tour of length $t$ in $G$ corresponds to a tour of length $nm-t$ in $G'$ (where $n$ is the number of vertices), so $G$ has a tour of length at most $d$ if, and only if, $G'$ has a tour of length at least $nm-d$.


When LRU is NOT the optimal replacement policy

Consider a program that plays a video in an endless loop (e.g. an electronic advertising billboard), assuming the RAM is constrained enough that the whole video can't fit at once.

The most recently used page of memory will contain the most recent section of the video, that just played. LRU would be the worst choice, because you're holding onto the parts that have already played, which are the parts that won't be needed for the longest time. They won't be needed again until all other pages are played first, and the video repeats. By definition, such a use case is hitting the least recently used pages, over and over.

The optimal page replacement policy in such a situation is one that either preempts the future pages (which is possible in this case because of the periodicity and simplicity of this usage profile) or one which permanently  holds onto some parts of the video (doesn't matter which parts, as they're all played equally) and uses the rest of the space to cycle through the rest of the pages.


Lexicographically smallest down-right path in matrix

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ matrix. (This requires a proof, but intuitively seems correct.)

To implement this algorithm efficiently, we need an efficient data structure for the two-dimensional range minimum query problem. Brodal, Davoodi and Rao give, in their paper On Space Efficient Two Dimensional Range Minimum Data Structures, a data structure that answers queries in $O(1)$ time, after $O(NM)$ preprocessing.

Actually, we need to find the minimum of a rectangle without two of its corners, but this domain can be written as the union of three rectangles, so such a query can also be answered in constant time.

Using such a data structure, we obtain an algorithm running in linear time $O(NM)$.

In fact, it suffices to use a much simpler data structure supporting one-dimensional range minimum queries; see Fischer, Optimal Succinctness for Range Minimum Queries for appropriate references. Suppose that $N \leq M$. Using a range minimum query data structure on each row, we can answer a two-dimensional range minimum query in time $O(N)$. Since the algorithm above makes only $O(N+M) = O(M)$ such queries, the overall complexity is still $O(NM)$.


The time complexity of finding the kth smallest number using buckets

Your algorithm is a variant of the radix sort.

Consider $k=n$ and the greatest two numbers differ by only the least 4 significant bits, then the two greatest numbers will be always in the last buckets in each iteration except the last. This means you have to iterate for sizeOfInt, sizeOfInt - 4, ... until 4, so the overall complexity is $O(nw)$ where $w$ is sizeOfInt.


weight balanced binary tree vs height balanced binary tree

The way to answer your question is to find the peer-reviewed papers that first described the trees (or that later chose to reference them) and read their explanations of why the authors felt the need to invent a new tree.

Generally speaking, weight-balanced trees have the property that restructuring operations on a node with $n$ descendants happen every $O(1/n)$ operations. This is good because sometimes these trees are used in an augmented way so that restructuring operations take $\omega(1)$ time. In some height-balanced trees, restructuring operations can happen every operation, while in others they happen every $2^{-O(\lg n)}$ operations, which is slightly weaker than $O(1/n)$.


Why can’t a qbit be both entangled and in a pure state?

First, let's look at the density matrix for A in the two cases. When A is in the pure state $|+\rangle$, we have
\begin{align}
\rho_+ = |+\rangle\langle+| = \frac{1}{2}\left(|0\rangle + |1\rangle\right)\left(\langle0| + \langle1|\right)
\end{align}
As a matrix, we'd write this
\begin{align}
\rho_{+} = \frac{1}{2}
\begin{pmatrix}
1 & 1\\1& 1
\end{pmatrix}.
\end{align}
When A is entangled with B, we can obtain the (reduced) density matrix for A by tracing over all B states:
\begin{align}
\rho_A &= \frac{1}{2}\text{Tr}_B\left[\left(|0\rangle\otimes|0\rangle + |1\rangle\otimes|1\rangle\right)\left(\langle0|\otimes\langle0| + \langle1|\otimes\langle1|\right)\right]\\
&= \frac{1}{2}\left(|0\rangle\langle0| + |1\rangle\langle1|\right),
\end{align}
or, as a matrix,
\begin{align}
\rho_{A} = \frac{1}{2}
\begin{pmatrix}
1 & 0\\0& 1
\end{pmatrix}.
\end{align}
Ok, you say, the density matrices are different. Who cares? Well, we don't really care about states, because we can't measure states directly. But we can measure observables, and we can find the expectation value for those measurements using our states. Specifically, we can find the expectation value of $\mathcal{O}$ by taking $\langle\mathcal{O}\rangle = \text{Tr}\,(\rho\mathcal{O})$. Let's look at the example of the $X$ operator. We have
\begin{align}
\langle X\rangle_+ &= \frac{1}{2}\text{Tr}\,(\rho_+ X)\\ &= \frac{1}{2}\text{Tr}\,\left[ \begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right]\\
&=\frac{1}{2}\text{Tr}\,\begin{pmatrix}1&1\\1&1\end{pmatrix} = 1.
\end{align}
In the state $\rho_A$, however, we have
\begin{align}
\langle X\rangle_A &= \frac{1}{2}\text{Tr}\,(\rho_A X)\\ &= \frac{1}{2}\text{Tr}\,\left[ \begin{pmatrix}1&0\\0&1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}\right]\\
&=\frac{1}{2}\text{Tr}\,\begin{pmatrix}0&1\\1&0\end{pmatrix} = 0.
\end{align}
We obtain different experimental predictions for the outcome of measurements in these two states, and so we can distinguish between them.

Edit: I didn't really answer your question beyond showing how states in the example you gave lead to different predictions. I would say the more broad lesson to draw is that when system A is entangled with system B, measurements on B can change the outcome of measurements on A. This leads to an additional, classical uncertainty in our measurements that is not present when A is in a pure, unentangled state.


Induction details for proof of closure of regular languages under unions

Given a transition function $\delta\colon Q\times\Sigma\to Q$, the standard argument proceeds by defining an extended transition function $\hat{\delta}\colon Q\times\Sigma^*\to Q$ (following the notation in Sipser)
that acts on strings (see J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages and Computations 3ed., section 2.2.4 for a reference).
This function is defined recursively by specifying
$$\hat{\delta}(q,\varepsilon)=q \qquad\hbox{and}\qquad
\hat{\delta}(q,Wa)=\delta\bigl(\hat{\delta}(q,W),a\bigr)$$ for $W \in \Sigma^*$,
$a\in\Sigma$ and $q\in Q$, and it is a simple exercise (with a proof sketched below) to show that (following the definition in Sipser)
a finite automaton $M=(Q,\Sigma, \delta, q_0, F)$ accepts a string $w\in\Sigma^*$ if and only if $\hat{\delta}(q_0,w)\in F$.

The heart of our desired inductive argument lies in the following result.

  Let $w\in\Sigma^*$. Then, with notation as in the proof of Theorem 1.25 in Sipser,
  we have
  $$\hat{\delta}\bigl((r_1, r_2), w\bigr)
= \bigl(\hat{\delta}_{\!1}(r_1, w),
\hat{\delta}_{\!2}(r_2,w)\bigr).$$

Proof. We proceed by induction on $|w|$. The result follows from the definitions when $|w|=0$
as we must have $w=\varepsilon$. Suppose inductively that the result holds for all $w$ with $|w|<n$.
Then, given $w \in \Sigma^*$ with $|w|=n$, we may write $w = w_1\dots w_n =: Ww_n$, so that
$$\begin{align}
\hat{\delta}\bigl((r_1,r_2),w\bigr)
&=\hat{\delta}\bigl((r_1,r_2),Ww_n\bigr) \\
&=\delta\Bigl(\hat{\delta}\bigl((r_1,r_2),W\bigr),w_n\Bigr) \\
&=\delta\Bigl(\bigl(\hat{\delta}_{\!1}(r_1,W),\hat{\delta}_{\!2}(r_2,W)\bigr),w_n\Bigr) \\
&=\Bigl(\delta_1\bigl(\hat{\delta}_{\!1}(r_1,W),w_n\bigr),
\delta_2\bigl(\hat{\delta}_{\!2}(r_2,W),w_n\bigr)\Bigr) \\
&=\bigl(\hat{\delta}_{\!1}(r_1, Ww_n),
\hat{\delta}_{\!2}(r_2,Ww_n)\bigr) \\
&= \bigl(\hat{\delta}_{\!1}(r_1, w),
\hat{\delta}_{\!2}(r_2,w)\bigr)
\end{align}$$
as needed.

Using the above result, it is straightforward to finish the proof of correctness.
Indeed, since $F = (F_1 \times Q_2) \cup (Q_1 \times F_2)$, it follows that
$$\hat{\delta}(q_0,w)\in F$$
if and only if
$$\hat{\delta}_{\!1}(q_1, w)\in F_1\qquad\hbox{or}\qquad\hat{\delta}_{\!2}(q_2, w)\in F_2.$$
In other words, $M$ recognizes a string $w\in\Sigma^*$ if and only if $M_1$ or $M_2$ recognizes it.

Addendum. We now sketch a proof that the two definitions of a finite automaton accepting a string are equivalent. The  first definition is given on page 40 of Sipser, we repeat it here for convenience:

  Let $M = (Q,\Sigma,\delta,q_0,F)$ be a finite automaton and let $w = w_1w_2\dots w_n \in \Sigma^*$ be a string. Then $M$ accepts $w$ if $w=\varepsilon$ and $q_0\in F$, or if $n>0$ and a sequence of states $r_0$,$r_1$, ..., $r_n$ in $Q$ exists such that $r_0 = q_0$, $\delta(r_i,w_{i+1}) = r_{i+1}$ for $0\le i\le n-1$, and $r_n \in F$.

We thus have to show the following:

  A finite automaton $M = (Q,\Sigma,\delta,q_0,F)$ accepts $w\in\Sigma^*$ if and only if $\hat{\delta}(q_0,w)\in F$.

Proof sketch. If $M$ accepts $w = w_1\dots w_n$, then $\hat{\delta}(q_0,w)=\delta\bigl(\hat{\delta}(q_0,w_1\dots w_{n-1}),w_n\bigr)=\delta(r_{n-1},w_n)=r_n$ by an inductive argument; intuitively this corresponds to showing that the recursive definition of $\hat{\delta}$ was defined 'correctly.' Conversely if $\hat\delta(q_0,w)\in F$, then we may build the sequence $r_0 = q_0$, $\;r_1 = \delta(r_0,w_1)$, ... inductively.


Intro to Algorithms: asymptotic function analysis

The values of $c_1$ and $c_2$ are pulled out of thin air. Their actual values don't matter except for the property that $$0<c_1\leq a\leq c_2$$
The value of $n_0$ also doesn't matter except for the property that $$n>n_0\implies c_1n^2\leq an^2+bn+c\leq c_2n^2$$
This implication is equivalent to saying that the interval $n\geq n_0$ is inside the set of solutions of the system of inequalities $$\begin{cases}(a-c_1)n^2+bn+c&\geq0\\(c_2-a)n^2-bn-c&\geq0\end{cases}$$
So, they solved the system of inequalities
$$\begin{cases}\frac{3a}{4}n^2+bn+c&\geq0\\\frac{3a}{4}n^2-bn-c&\geq0\end{cases}$$
You can see now that the concrete values of $c_1$ and $c_2$ were chosen such that the two inequalities in the system are nearly the same, except for the sign of the coefficients. The two are quadratic polynomials with positive leading term. They are going to be non-negative outside the interval formed by their roots. So, for the interval $n>n_0$ to be inside, we just need to take $n_0$ to be a bound from above of the absolute value of the roots.
There are many known bounds of the roots in terms of the coefficients. It looks like they took this bound by Lagranges. Although $2\max\left(\frac{|b|}{a},\sqrt{\frac{|c|}{a}}\right)$ would be the bound for the roots of the polynomial $an^2+bn+c$ and we have instead $\frac{3}{4}an^2+bn+c$. The bound would be instead $2\max\left(\frac{4|b|}{3a},\sqrt{\frac{4|c|}{3a}}\right)$, which is somewhat larger.


Is boolean validity a harder problem than satisfiability?

However to check unsatisfiability I would need to check all possible assignments, surely this makes the problem EXPTIME?

Well, $EXPTIME$ but not necessarily $EXPTIME$-complete.

Congratulations, you've found the (possible) difference between $NP$ and $Co-NP$.

The first thing to realize is that there's a duality here. Satisfiability requires only a single example to prove a YES, but (as far as we know) needs to search a possibly exponential space for a NO. Unsat is the exact dual of this: you need to search a possibly exponential set to prove a YES, but a single counter-example will prove a NO. So neither is a harder problem, it's just that one is easy for YES, and the other is easy for NO.

The second thing to realize is that every NP-complete problem has a dual like this, and that's exactly why we study $Co-NP$ complete problems. For Hamiltonian Path, one path proves it, and a full search is needed to disprove. The converse is true to for NOHAMPATH, it's complement problem. Every NP-problem has a dual by switching the "yes" and "no" cases.

Nobody knows if $NP = EXPTIME$, though it's pretty unlikely. But it seems like just having to do an exponential search isn't enough to characterize all exponential algorithms.


I found the answer consulting the book "Distributed System : Principles and Paradigms" (Andrew S. Tanenbaum - Maarten Van Steen). First of all it is possible to continue just because 3PC is non-blocking protocol by definition. A processor can reach the state “PRE-COMMIT” only if the coordinator was in state “PRE-COMMIT” (thus each processor sent a COMMIT request), so the crashed processor could not be for sure in state “INIT” nor in "ABORT", but at least in the state “READY”. Anyway, all the “alive” processors, after seeing the “PRE-COMMIT”, will go in “COMMIT” state.


If you have a Cook reduction in both directions, do you also have a Karp reduction?

The answer depends on whether you require both of $\mathcal{P}_1,\mathcal{P}_2$ to be in NP or not.

If the problems need not be in NP

Then the answer to your question is "No".  There exist problems $\mathcal{P}_1,\mathcal{P}_2$ that are Cook-reducible (in both directions) but not Karp-reducible (in either direction)

In particular, consider $\mathcal{P}_1 = $ HALT (the Halting problem) and $\mathcal{P}_2 = \overline{\mathcal{P}_1}$ (its complement).  They are Cook-reducible (you just invoke the oracle and complement its answer), but not Karp-reducible.

(Similarly, if $\textsf{NP} \ne \textsf{coNP}$, then the answer is No: take $\mathcal{P}_1 = $ SAT and $\mathcal{P}_2 = $ TAUTOLOGY, so that $\mathcal{P}_1$ is NP-complete and $\mathcal{P}_2$ is coNP-complete.  They're Cook-reducible, but a Karp reduction would prove that $\textsf{NP} = \textsf{coNP}$ via a standard argument.)

If the question is restricted to require both problems to be in NP

Then it's an open question; no one knows whether the answer is "Yes" or "No".  See https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction and

https://cstheory.stackexchange.com/q/686/5038 and
https://cstheory.stackexchange.com/q/138/5038 and
https://cstheory.stackexchange.com/q/3435/5038 and
https://cstheory.stackexchange.com/q/14379/5038 and
https://cstheory.stackexchange.com/q/16983/5038.


Facebook Hackercup 2013: Balanced Smileys

The solution is correct because the "}" and "{" symbols are considered "optional" parentheses.

(:):):(:::) → (}}{}

The left one is an example of an input string, the right is the preprocessed version of it.  If you read the algorithm, you see that they keep two values,

min_level, max_level = (0, 0).

Reading the actual solution should convince you.


Tool for generating all the consequences of the logical theory (general logic programming framework)?

You understand incorrectly. That is not how logic programming works.

The number of consequences typically grows exponentially, or is even infinite. For instance, some consequences of $\forall x \in \mathbb{N} \,.\, \phi(x)$ are $\phi(0)$, $\phi(1)$, $\phi(2)$, $\phi(3)$, $\phi(3 + 2)$, $\phi(x \cdot 2)$, and so on. Generating all consequences is infeasable and useless. It's a bit like trying to write good literature by generating all grammatically correct sentences.

The gist of logic programming is proof search. A logic program follows a particular strategy to look for the proof of a given query. So in this sense, it does things backwards.