Improve minimum spanning tree with new edge, with better running time than O(|V|)?

Using Heavy path decomposition.

The key idea is to partition all edges into heavy edges and light edges.
Consider tree edge from parent node X to child node Y:

heavy edge: size of sub tree Y is at least half of the size of sub tree X;
light edge: size of sub tree Y is smaller than half of the size of sub tree X;

There are at most $O(\log |V|)$ heavy paths (path with only heavy edges) from any leaf to root. Maintaining each heavy path using segment tree or balanced BST, and converting MST into tree of heavy paths, one can query the heaviest edge $e_{max}$ between any two vertices $u$,$v$ in $O(\log |V|)$.

Another method is using Link cut tree which handles each query in $O(\log |V|)$ amortized time complexity. This can also handle the case that each query is applied to the result of previous implement.


Can I find all the common subsequences between 2 sequences by using dynamic programming?

Denote the two strings by $s = s_1,\ldots, s_n$ and $t = t_1,\ldots, t_m$. Let $\mathcal{U}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$ which contain $s_i$ and $t_j$. Let $\mathcal{U}(\leq i,j)$ be the union of $\mathcal{U}(I,j)$ over all $i \leq I$, and define $\mathcal{U}(i,\leq j),\mathcal{U}(\leq i, \leq j)$ similarly. These multisets obey the recurrences:
$$
\mathcal{U}(i,j) =
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ w s_i : w \in \mathcal{U}(\leq i-1,\leq j-1) \} & \text{if } s_i = t_j.
\end{cases} \\
\mathcal{U}(\leq i,j) = \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j) \\
\mathcal{U}(i,\leq j) = \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(i,j) \\
\mathcal{U}(\leq i,\leq j) = \mathcal{U}(\leq i-1,\leq j-1) \cup \mathcal{U}(i,\leq j-1) \cup \mathcal{U}(\leq i-1,j) \cup \mathcal{U}(i,j)
$$
with the base cases $\mathcal{U}(0,0) = \{\epsilon\}$ and $\mathcal{U}(k,0) = \mathcal{U}(0,k)$ for $k > 0$.

If you want you can even keep track of the indices from which the subsequences are taken. The recurrences above ensure that each pair of matching subsequences is counted exactly once.

If you want instead to count the number of common subsequences, all you need to do is to keep track of the size of the multisets involved. Similarly, if you want instead to determine the longest common subsequence, all you need to do is keep track of that. In the latter case, double counting of subsequences is allowed (since we are only interested in the maximum length anyhow), and this simplifies the recurrence.

Indeed, if you are interested just in the set of common subsequences, then you can use a simpler recurrence. Let $\mathcal{V}(i,j)$ denote the set of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$. The sets $\mathcal{V}(i,j)$ obey the recurrence:
$$
\mathcal{V}(i,j) = \mathcal{V}(i,j-1) \cup \mathcal{V}(i-1,j) \cup
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ws_i : w \in \mathcal{V}(i-1,j-1)\} & \text{if } s_i = t_j,
\end{cases}
$$
with base cases $\mathcal{V}(i,0) = \mathcal{V}(0,j) = \{\epsilon\}$. This is the form of the standard recurrence for longest common subsequence.

If you're interested in multisets but prefer a simpler recurrence, you can use the geekstogeeks idea, which requires multiset subtraction to avoid double counting. Let $\mathcal{W}(i,j)$ denote the multiset of common subsequences of $s_1,\ldots,s_i$ and $t_1,\ldots,t_j$, which obeys the following recursion:
$$
\mathcal{W}(i,j) = \mathcal{W}(i,j-1) \cup (\mathcal{W}(i-1,j) \setminus \mathcal{W}(i-1,j-1)) \cup
\begin{cases}
\emptyset & \text{if } s_i \neq t_j, \\
\{ws_i : w \in \mathcal{W}(i-1,j-1)\} & \text{if } s_i = t_j,
\end{cases}
$$
with base cases $\mathcal{W}(i,0) = \mathcal{W}(0,j) = \{\epsilon\}$. Depending on the application, the operation of multiset subtraction could be unavailable, and in this case you can use the idea outlined at the beginning of the answer.


Yes it is, by exactly the argument you give. Looping over all possible strings of length $n$ requires only $n$ tape cells – you can do it by treating the length-$n$ strings as numbers in base $|\Sigma|$, so looping through those is essentially a counter, too. You can reuse the space since you don't care about strings that you've already tested. Testing if the string you just made is in $L'$ takes space $n$ on your oracle tape. Implementing the counter requires only $O(n)$ bits, since you only need to store a number in the range $0, \dots, |\Sigma|^n$. So the total amount of space required is linear in $n$.

In fact, you can do slightly better, though the total will still be $O(n)$ because of the need to loop through the length-$n$ strings.  You don't need to count how many strings in $L'$ you've seen so far; you just need to know if that number is odd or even.


Dijkstra's Algorithm with different color nodes

Expanding on hengxin's idea, in order to find whether such a path exists, go over all choices of two nodes $x,y$, one red and the other blue, and see if there are paths $s \leadsto x \leadsto y \leadsto t$. In order to find the one containing the minimum number of white nodes, assign weight 1 to edges entering white nodes, and weight 0 to all other edges. The weight of a path is now the number of white nodes. Go over all possible choices of $x,y$, and calculate the minimum-weight path $s\leadsto x\leadsto y\leadsto t$; choose $x,y$ that minimize that weight.


Are there (highly) restricted process calculi? Perhaps similar to formal grammar?

I wondered if there were much more restrictive formalisms for describing concurrent processes?

Petri nets are IMO more restrictive than the process calculus and such. They are state-transition systems, which are pretty much like formal grammars (like parsing expression grammars). They all boil down to states and rules / transitions. Petri nets include parallel composition.


A question about parallel algorithm complexity

You are probably in the realm of asynchronous parallel computations where units of work are performed by processors at their pace and communication is performed explicitly. This model is a good approximation to many real life parallel computers such as PC clusters or multicore CPUs.

You have an algorithm that can be represented as $O(n \log n)$ units of work each taking constant time or as $O(n)$ units of work each taking $O(\log n)$ time.
Here $n$ is a parameter that characterizes the size of the problem.

The units of work can be executed on a parallel computer with a fixed number of sequential processing elements (e.g. processor cores). It depends on the algorithm whether the work units can complete while other work units have not started, or whether the computations will have to interleave.

In a practical computer interleaving can be achieved through pre-emption and context switches.


Is this language depending on P = NP recursive?

If P=NP, then $L = (0+1)^*$ which is regular grammar. Hence, it is recursive.

If P!=NP, then $L = \phi $   which is also a regular grammar. Hence, recursive.

In both the cases, $L$ will be a recursive language.

PS I see a lotta GATE problems these days :D


What is the probability of friendship conditioned on the number of mutual friends

Okay, this is my approach to this problem. I think the key concept here is the clustering coefficient $c$. The value of $c$ is denotes how likely it is that two nodes are connected by an edge, if the have a common neighbor. In SN-friendship graphs the clustering coefficient is usually high compared to classical random graph models, such as Erdös-Rényi.

What is known about the clustering coefficient of the facebook-graph? If you follow the presentation of this paper, for a node of degree 100, we have $c=0.14$. Assuming that you have 100 friends is a reasonable assumption than it is close to the median degree (about 99, see here) and the average degree (might be around 95, see here).

Lets make the bold assumption, that the events that a tie between two nodes $A$ and $B$ is present if they have friend $X$ in common, are independent. Then we get

$$\begin{align}
P[\text{$A$ and $B$ are friends}] & = 1 - P[\text{$A$ and $B$ are not friends}] \\
&=1-(1-c)^k.
\end{align}$$

A plot of this function looks like this:

So if $A$ and $B$ have 5 friends in common it is slightly more likely they are friends, than they are not.

This is just a rough calculations that ignores several effects.


Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution

Use an adjacency list representation, together with a Union-Find data structure on the vertices.  Augment the Union-Find data structure so you can quickly enumerate the list of all edges incident on any vertex within a particular partition (you can keep track of them with a doubly linked list, and splice the lists together whenever you do a Union operation).  Now edge contraction can be done in $O(\alpha(n))$ time, by simply doing a Union operation on the two vertices.  Edge removal can be done in $O(1)$ time, due to the adjacency list representation.  You can also find an arbitrary edge in $O(1)$ time, thanks to the augmentation of the Union-Find data structure.

This avoids the factor of $n$.  You still pay a factor of $O(\alpha(n))$ instead of $O(1)$, but $O(\alpha(n))$ is so small that it might as well be $O(1)$ for all practical purposes, and in any case it is far smaller than $n$.

Actually, I think you pay more than that, because you'll need to undo the Union operations after returning from the recursive call.  To deal with that, you can use a persistent Union-Find data structure.  I'm not familiar with the asymptotic running time for those data structures, but I think given how it is used here it will be pretty close to as efficient as the plain Union-Find.

Usually we don't worry too much about polynomial factors when analyzing exponential-time algorithms, because the polynomial factor is tiny compared to the exponential factor, so a polynomial speedup won't change much in practice.  But here is a case where the polynomial speedup you desired can be achieved.


Check if a linear function or an affine function can be a pseudo random function

Intuitively, pseudorandom functions are functions that look random. A linear function $f$ satisfies
$$ f(x+y) = f(x)+f(y) $$
for all $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies
$$ f(x+y) - f(x+z) = f(y) - f(z) $$
for all $x,y,z$, which is highly unlikely for a random function.


It depends on how the language is defined.

Language might be statically typed (like e.g. C, Java, Haskell, ...) or dynamically typed (like e.g. Python, Common Lisp, ...). In a statically typed language every expression has associated value and the semantic analyser checks whether the types match just after when the expressions are parsed.

In a statically typed language if you have variable a defined to contain integer and variable b defined to contain integer between 0 and 10, assignment b = a is not valid at compile. Of course such language needs a way of saying "please check whether the value will fit and set it if it does and do that if it does not". Usually via some kind of type cast that throws an exception, but might be anything.

In a dynamically typed language expressions don't have any type specified and whether the value can be assigned is always checked at runtime when specific type is needed.

Combination is possible where expressions may have associated type and if they don't, they are considered to be of universal "any" type and runtime check is omitted if it is possible to statically ensure the value will fit.

Then there are strongly typed languages (e.g. Java, Python, Haskell, ...) and weakly typed languages (C, C++, Pascal). In a strongly typed language each value has associated type and this type may be checked at runtime if needed. On the other hand in weakly typed languages the value is just a bit pattern and gets interpreted according to the static type of the expression. Note that dynamically typed languages are strongly typed as their values carry their type around with them.

Since your language has variable types, it is at least partially statically typed. So you can do some static type checking. If you have assignment of variable that can hold positive numbers to variable that can only hold negative numbers, you can reject such statement straight away without waiting for the actual values, because the ranges are disjoint (the types are incompatible).

If the type on the right hand is a subtype of the one on left hand (the range is smaller), you know the statement will always be ok. You don't need to do a check at runtime.

If the types have some overlap, but the type on right hand is not a subtype, i.e. may have values that don't fit in the variable on the left side, you may either require explicit check or you may automatically inject a check that will yield error or exception if at runtime the actual value does not fit. Which you do depends on the specification of the language.

Last for constants you handle them as special case of the subtype rule. A constant 42 is an integer in range [42, 42]. This is a subtype of all ranges that can contain 42 and you can do the check at compile-time.


Growing multiples of variable combinations

You can think of these combinations as 3-digit numbers in base $l+1$. For example, if $l=9$ then the solutions to your problem are in one-to-one correspondence with 3-digit decimal numbers, from 000 to 999. There are in total $(l+1)^3$ of them.

As an aside, it is not clear why you omitted 0a0b0c.


Does "in-place" for $n$ items imply space dominated by $n$?

There are two common ways to analyze computation, corresponding to two different machine models. One model is the one taught in classes on computability and complexity theory: it is the Turing machine model. In this model, the machine has a read-only input tape, a write-only output tape, and several work tapes, and we only measure space on the work tapes.

A different (and more realistic) model is used in classes on algorithms and data structures: it is the word RAM model. There are several ways to define space usage in this model - one obvious way is the number of memory cells accessed beyond the input cells. In this model, one could define an in-place algorithm as one which uses $O(1)$ space (in this model we measure space in machine words of length $O(\log n)$, where $n$ is the length of the input), though this ignores stack usage (which will be simulated in the RAM model using a stack whose memory usage counts).

You haven't defined what in-place means for you, and you haven't defined how you measure space. Without such definitions, it is impossible to answer your question. However, I have outlined above definitions of both concepts for which in-place implies sub-linear (even constant) space.


The case where $\Pr(X=1)=\Pr(X=2)=\tfrac12$ is the subset sum problem, which is NP-complete so you won't find an efficient algorithm in general. Dynamic programming is probably the way to go.


(1) NP-complete only contains problems that can be answered by Yes or No, which are called decision problems. So FACTOR is not an NP-complete problem even your reduction is correct. In fact, if your reduction were correct, it proves that FACTOR is NP-hard.

(2) If you want to prove the NP-hardness of FACTOR by reducing UKP (unbounded knapsack problem) to it, you should find an integer $M$ (in polynomial time) for each instance $I$ of UKP and show that the answer of $I$ can be gotten (in polynomial time) using the factorization of $M$.

In your proof, you can only solve a specific subset of UKP instances by FACTOR, so it is not a correct reduction.


Help me understand the logic behind x - y in binary by boolean?


What are the rudimentary types of information connectivity i.e. model types?

Model theory, branch of mathematical logic, is based on three things: atoms, functions, and relations. With these you can define pretty much anything. In fact, functions are subsumed by relations, so you only need two.

What is a list but a next relation? What is a hierarchy but a parent-child relation?

Of course these satisfy axioms, and these can readily be expressed in first order logic.


Trouble with Big-O notation proof by definition

As $a$ is fixed, then you can omit it from requirements because for $a \gt 0$ inequality $(\log n)^a \leqslant C n^b$ is equivalent $\log n \leqslant C^{\frac{1}{a}}n^{\frac{b}{a}}$. Denoting $0 \lt \frac{b}{a}=\alpha $ we obtain, that it's enough to proof $\log n \in O(n^\alpha)$ for $\alpha \gt 0$.
To simplify, we can consider $\log n$ with base $e$, because  the difference with the other base will be constant factor.
So, last step will be
$$\lim\limits_{n \to \infty}\frac{\ln n}{n^\alpha} = \lim\limits_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$
We see, that a more strong result with $o$-little is fair: $\forall \alpha \gt 0$  we have $\log n \in o(n^\alpha) \subset O(n^\alpha)$.


Algorithm for creating a directed graph using flat data input

It looks like you're making a tree based on elements after the first. Some quick pseudocode for this might look like:

 1. Start with a tree containing only the root.
 2. Set the current node to the root.
 3. Read a line of input = (ID, tail)
 4. For each object in tail, do
 5.     if the current node has a child equal to the current object, then
 6.         move to that child node
 7.         add the current ID to the list of IDs associated with that node
 8.     else,
 9.         add a new child node corresponding to the current object
10.         start a list of associated IDs using the current ID as the first entry
11. Repeat from step 2. until there is no more input

Showing this on your example:

Initial:
Root

Pass 1: (ID, tail) = (01001, (Butter, salted))
Root
- Butter (01001)
  - salted (01001)

Pass 2: (ID, tail) = (01002, (Butter, whipped, with salt))
Root
- Butter (01001, 01002)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)

Pass 3: (ID, tail) = (01145, (Butter, without salt))
Root
- Butter (01001, 01002, 01145)
  - salted (01001)
  - whipped (01002)
    - with salt (01002)
  - without salt (01145)

...

Basically, you're constructing a tree, one branch at a time.


How to find the minimum number of states required by a DFA

You can prove that your set is maximal in (at least) two different ways:

Show that every string is equivalent to one of the strings in your set.
Construct a DFA for the language having the same number of states as are strings in your set.

In your case both approaches are not too difficult.

Note, however, that the question only asks you to show that every DFA for the language must contain at least $k+2$ states. For this there is no need to show that your collection is maximal. If you find $k+2$ pairwise inequivalent strings, then it follows that every DFA for the language must contain at least $k+2$ states. If the collection is not maximal, all it means is that your bound isn't tight.


Is there such a notion as "effectively computable reductions" or would this be not useful

Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating:

Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; only from a family of languages to another.

In particular, you seem to be mixed up when you write this:

  Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way.

A reduction from, say, VertexCover to 3SAT is a Turing machine $f$ that transforms instances of VertexCover into instances of 3SAT. Since it is a Turing machine, it is effectively computable by definition. So it is not surprising that all reductions you have seen of this form are effectively computable.

In other words, if we just look at reductions from one language to another, then every reduction is effectively computable!

This is different from the case of the Cook-Levin theorem, where we have to show a reduction $f$ from an arbitrary NP language to SAT. Then it might make sense to consider whether this reduction -- parameterized by the language in NP -- is effective or not. But that brings us to my second point:

Observation 2: What counts as an effectively computable reduction depends on the representation of languages.

This is important because standard reductions (either many-to-one reductions or Turing reductions) do not depend on the way the language is represented. For a reduction from $L$ to $L'$, I consider $L$ and $L'$ to be subsets of $\{0, 1\}^*$. But for your notion of effectively computable to make sense, we need to have access to a representation of $L$ (we probably don't need a representation of $L'$).

To make this point clearer, consider the reduction in the proof of the Cook-Levin theorem, which you brought up. The proof considers a language $L$, represented by a polynomial-time nondeterministic Turing machine $N$. Then it shows that $L$ is reducible to SAT. You say that this reduction is not effectively computable, but that depends on how $N$ is represented, i.e., the definition of a polynomial-time nondeterminstic Turing machine $N$:

Definition 1: A polynomial-time NTM is a nondeterministic Turing machine such that there exists a polynomial $p(n)$, such that the TM always halts in time at most $p(n)$.
Definition 2: A polynomial-time NTM consists of a nondeterministic Turing machine, together with a polynomial $p(n)$. The way it runs is that, on any branch, it is only executed for $p(n)$ steps; if it does not halt in this time, then that branch is ignored.

It may seem that I am making Definition 2 up and that the definition is not natural, but actually both of these are perfectly valid definitions of a polynomial-time NTM that both have their merits. And for the classical theory of P, NP, and NP-completeness, both of these definitions are equivalent. The nice thing about Definition 2 is that an NTM is allowed to diverge on certain branches; you don't worry about that because the execution semantics says that we just forget about it once the running time goes above $p(n)$.

However, the definitions become inequivalent when it comes to effectively computable reductions. Note that, according to Definition 1, when we are given a language defined by an NTM $N$, we have no idea what its running time is, so we may not be able to reduce it to SAT (more on this below). But according to Definition 2, part of the NTM $N$ is that it comes with a polynomial, and so we know its running time. Therefore, we can effectively reduce all NP languages to SAT if we are using Definition 2.

Also, we have only considered nondeterministic Turing machines; we could equivalently define NP using verifier Turing machines. Then the definition of an effectively computable reduction could be something else!

TL;DR: Depending on how a language in NP is represented, and in particular depending on the definition of a polynomial-time NTM, it may be either true or false that every language in NP is effectively reducible to SAT. In other words, The set of effectively computable reductions changes depending on the model of computation used to represent languages in NP.

Now at this point, given points (1) and (2), a question still remains: can the reduction in the Cook-Levin theorem be made to be effective? In particular, suppose we fix the following definitions:

Languages in NP are represented by nondeterministic Turing machines whose runtime is bounded by an unknown polynomial $p$ (i.e. Definition 1).
Given a language $L$, we say that the class of languages NP is effectively poly-time reducible to $L$ if the following holds: there is a TM $f$ that takes as input $\langle N, w \rangle$, where $N$ is a polynomial-time NTM and $w$ is any input to $N$, such that $w \in L(N)$ if and only if $f(\langle N, w \rangle) \in L$. Also, $f$ must run in polynomial time (in its input $\langle N, w \rangle$).

In other words, to address point (1), we are assuming that languages in NP are represented by nondeterministic Turing machines without an explicit polynomial bound. And to address point (2), in our definition of effectively reducible, we are talking about a reduction from a class of languages, in this case NP, to a single language.
Now we have the following observation:

Observation 3: (Cook-Levin is not effective) The class NP is NOT effectively reducible to SAT.

Let us see why this is true. Assume towards a contradiction that an effective reduction $f$ exists. The idea is that we will try to solve a difficult (say, doubly-exponential-time) problem by taking its instance, turning it into a polynomial-time NTM, and asking $f$ to reduce it to SAT. So, let $L_{hard}$ be some problem that requires doubly-exponential time to solve (this exists by the Time Hierarchy theorem), and let $M_{hard}$ be a (deterministic) TM that solves it. Given any instance $w$ of the problem, define the following NTM $N_w$:
\begin{align*}
N_w :=
&\text{"On any input $a$, first run } M_{hard} \\
&\text{on input } w \text{. When it halts, accept if} \\
&\text{it accepts and reject if it rejects."}
\end{align*}

Now we can use this to solve $L_{hard}$ in exponential time (not double exponential), as follows. On input $w$, we first construct $N_w$, which has size only a constant more than $w$. Then we pass $\langle N_w, \epsilon \rangle$ (the second argument, $\epsilon$, is just a placeholder here) to $f$ to reduce it to SAT. $f$ gives us back an instance of SAT that is at most polynomial size in $N_w$, and $f$ takes only polynomial time to run. So we end up with an instance of SAT of polynomial size in $w$; now we solve it in exponential time in $w$ using brute-force search.

This point (3) seems to suggest that most of the time, no interesting class of languages will be reducible in this effectively computable sense to a single language. It will just be too hard, because you can exploit this computability to then solve hard problems by encoding them as part of a TM input to the effective reduction. However, something is a bit fishy here, because if we feed the TMs $N_w$ into the Cook-Levin theorem reduction, we would end up with very large SAT formulas, exponential in $w$. So perhaps our definition needs to be tweaked so that $f$ runs in time polynomial in the running time of $N_w$, not just polynomial in the input $\langle N_w, \epsilon \rangle$.

Observation 4: If we allow Turing (many to many) reductions, then Cook-Levin can be made effective.

As D.W. says in a comment:

  I think one can construct an effective Cook reduction, by iterative doubling. Does that help?

I also believe this is true. In particular, we can change our definition of an "effective reduction" from NP to a language $L$ by saying that the reduction does not just return an instance of $L$, but returns many instances of $L$ in sequence, and uses an oracle for $L$ to solve the original problem. Then to solve a general problem in NP, you could try larger and larger polynomials $p$ until you get the right one which bounds the running time. You can detect whether a particular polynomial bounds the running time on all branches of the NTM by a separate reduction to SAT.

Disclaimer

I am not an expert in this topic. These are just some preliminary notes on the idea, and I am not sure if someone has studied this in the literature.

P.S. Although it may not be directly related, your question about considering effective reductions reminds me of an idea I had, about considering not just whether languages are in P or in NP, but whether they are provably so. This is related to the idea of developing a complexity theory that is effective or constructive. I asked and later answered question about defining provably P and provably NP languages here.


Suppose for simplicity that $|l(x)| = |r(x)| = |x|-1$. If $L(n),R(n)$ are the time complexities for computing $l,r$ on inputs of length $n$, then the time complexity for computing membership in $S$ satisfies the recurrence
$$ T(n) \geq L(n) + R(n) + 2T(n-1). $$
Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.

If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c < 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).

So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.


Which of $2^{\log_*n}$ and $\log\log n$ grows faster?

Consider $n_k=2^{2^{2^{\cdots}}}$, $k$ levels. Then $\log\log n_k = 2^{2^{2^{\cdots}}}$, $k-2$ levels, while $2^{\log^* n_k} = 2^k$. Does this help?


Extending ordered tree edit distance to DAGs

So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. The informal reasoning follows:

Edit distance between RNA structures with pseudoknots is Max-SNP hard and the reduction to Max-Cut works even if we ignore the RNA sequence (Ma, Wang & Zhang, 2002: Computing similarity between RNA structures)
One can represent an RNA structure with pseudoknots as a DAG with ordered children and labelled edges by extending the tree representation from Zhang & Shasha 1989: Nodes still represent base pairs and unpaired nucleotides, "normal" edges represent the "is contained in" relationship and new type of  edges to represent a "contains only first nucleotide of a base-pair" relationship let us represent crossing base pairs.
An algorithm for edit distance on labelled DAGs would therefore likely give an algorithm for Max-Cut which is Max-SNP hard. This obviously depends on what edit operations are allowed, but it seems to work for any sensible set of edit operations I came up with.


Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

You are on the right track.

Now that we have the recurrence relation $$S(n) = 2S(\frac{n}{2}) + \Theta(n\sqrt{n}),$$ Applying the case three of the master theorem, where $a=2$, $b=2$, $\epsilon=\frac12$, we will have $S(n)= \Theta( n\sqrt n)$.

I was stretching a bit when we were applying the master theorem since the regularity condition, the existence of such $c>0$ required for case three is not necessarily satisfied. What I really meant is that we can find two constant $0<c_1<c_2$ such that $c_1n\sqrt n\le S(n)-2S(\frac n2) \le c_2n\sqrt n$ for all $n$. Define $S_1$ by $S_1(n) = 2S_1(\frac{n}{2}) + c_1n\sqrt{n}$ and $S_2$ by $S_2(n) = 2S_2(\frac{n}{2}) + c_2 n\sqrt{n}$ with the same initial condition as $S$. Now we can apply case three of the master theorem to $S_1$ and $S_2$ to get the same $\Theta$ bound, since the regularity condition is satisfied with $1>c=0.8>\sqrt2/2$. Since $S_1(n)\le S(n)\le S_2(n)$, S(n) has the same $\Theta$ bound.

In case you have not learned/are not allowed to use the master theorem, you may have to more or less prove case three of the master theorem by yourself. You could find a proof, for example, in CLRS.


You have to show two things:

Every word in the language of your regular expression contains 101 as a substring.
Every word containing 101 as a substring belongs to the language of your regular expression.

You can prove both of these using the definition of the language of a regular expression. It is a bit tiring but otherwise requires little creativity.


How to find longest possible identical sequence in Array A and B?

Assuming all characters of $B$ are wholly contained in $A$, then this method should give you an optimal results.

Algorithm

Compute the longest substring $P_i$ in $A$ that is a prefix of the suffix of $B$ from $B_{i \ldots n}$. This is essentially equivalent to finding the longest common substrings between $A$ and $B$ starting at index $i$ of $B$. There are many methods of doing this, some listed below:

Compute a suffix tree $T$ for the array $B$. Making sure to leave in the suffix links (these are important for back tracking and essentially make the tree like an Aho-Corasick state machine). Traverse $A$ using $T$ as a state machine. Keep track of deepest non-root node reached in $T$ for each path from root to leaf. This will take $\Theta(|B|) + \Theta(|B| + |A|) = \Theta(|B| + |A|)$.
Solve this by inserting both strings $A$ and $B$ into a generalized suffix tree. Keep track of deepest common ancestor between a suffix leaf of $B$ with any other suffix leaf in $A$. This will take $\Theta(|B| + |A|)$.
Least optimal, use dynamic programming, but reverse the formula so you compute longest prefix for a suffix, rather than longest suffix for a given prefix. This will take $\Theta(|B|\cdot |A|)$. (Would not recommend)

Sort $P$ by the index of the starting character of the prefix (i.e. in the original suffix order).
Let $i = 0$
While $i < |B|$:

Let $j$ be the last index of substring $P_i$.
Add substring $P_i$ to a set $S$.
Let $i = j+1$

Return $S$ as it is the set of sequences in $A$ that minimally but completely cover $B$.

Running Time

Let $n = |B|$ and $m = |A|$:

Will take $O(n + m)$ because branching factor is constant (only 10 values) and if you keep it compressed and refer to indices instead of values.
Will take $O(n \log n)$ or $O(1)$ depending on how you structure $T$.
Will take $O(n)$.

Total time will be $O(m + n)$ which will be $O(m)$ for $m \gg n$.

Example

Let $$B = [0, 1, 3, 1, 2, 0]$$
$$A = [2, 1, 3, 0, 5, 1, 2, 4, 0, 1, 3, 0, 3, 1]$$

Step 1 would compute the following tree:

Step 2 should generate the following longest prefixes $P$ for suffix $S$:

$$\begin{array}{|c||r|r|}
\hline B \text{ indices} & S & P \\
\hline [0\ldots 5] & 0,1,3,1,2,0 & 0,1,3 \\
\hline [1\ldots 5] & 1,3,1,2,0 & 1,3 \\
\hline [2\ldots 5] & 3,1,2,0 & 3,1 \\
\hline [3\ldots 5] & 1,2,0 & 1,2 \\
\hline [4\ldots 5] & 2,0 & 2 \\
\hline [5\ldots 5] & 0 & 0 \\
\hline
\end{array}$$

We then follow steps 5, 6, and 7 to get that our set to be returned is contained of:
$$P_0 = [0, 1, 3], P_3 = [1, 2], \text{ and } P_5 = [0]$$

It's also easy to think of this as the maximum number of disjoint subsequences of $B$ contained in $A$. The maximum here is 3 because there are at most 3 subsequences that have no overlapping pieces:

Maybe this visualization will help. Then we should keep track of indices along the way in $A$ (this is relatively trivial with proper manipulation), but we see $B$ can be represented by:

$$A[6 \ldots 8] \; A[4 \ldots 5] \; A[3 \ldots 3]$$
$$0,1,3 : 1,2 : 0$$


Consider a circuit having a single NOT gate, computing some function $f(x)$. We can write $f(x) = g(x,\lnot h(x))$, where $g,h$ are monotone functions.

Consider now a sequence of inputs $x_0 < x_1 < \cdots < x_n$ (i.e., $x_0$ is the zero input, and $x_i$ is obtained from $x_{i-1}$ by changing one bit from 0 to 1). Since $h$ is monotone, it is either constant on $x_0,\ldots,x_n$, or $h(x_0) = \cdots = h(x_i) = 0$ and $h(x_{i+1}) = \cdots = h(x_n) = 1$ for some $i$. In the former case, $f(x_0) \leq \cdots \leq f(x_n)$. In the latter case, $f(x_0) \leq \cdots \leq f(x_i)$ and $f(x_{i+1}) \leq \cdots \leq f(x_n)$. This means that the sequence $f(x_0),\ldots,f(x_n)$ flips from 1 to 0 at most once.

It follows that the complement of the parity function on three bits cannot be computed using a single NOT gate. Indeed, if it could, then consider $x_0=000$, $x_1=001$, $x_2=011$, $x_3=111$. Then $f(x_0),f(x_1),f(x_2),f(x_3)=1,0,1,0$ flips twice from 1 to 0.

This shows that you cannot simulate an arbitrary number of NOT gates using a single NOT gate.


Recover an array from its insertion indices

Prelimiaries

You can augment an AVL tree to support all the usual operations plus the following:

  Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).

To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).

Search
The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.

Insert
To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).

Rotations To perform a right rotation on $u$ let $v$ be its left child.
"Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.

Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).

Solving your problem

Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations.
Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.

When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.

At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).

The total time required is $O(n \log n)$.


There are two answers: one that solves your problem, and one that answers your question. I'll start with the first. One way to make sure that previous states cannot be backtracked from generated numbers is to mask the true state. Here's how it works. You take your $b$-bit number $x_t$ to be the true state at time $t$, but the number your RNG generates is $x_t \text{ mod } m$, where $m$ is much less than $2^b$. Then you can specify $g$ to be $x_{t+1} = a \cdot x_t \text{ mod } n$, with $a$ and $n$ large numbers that are relatively coprime.

This way, if you collect the numbers generated by this RNG, you need at least a couple of data points before you can make educated guesses about $x_t$, and even then it's not easy. The period of the RNG is $n$.

The answer to your question about whether there exist easy-to-compute functions that are hard to invert is an open question, known as the existence of one-way-functions. Existence is known to imply P $\not=$ NP, so it probably won't be resolved for some time. That's for functions that are easy to compute in one iteration; functions that allow an arbitrary amount of time steps to be computed is a question on a whole other level.

Of course, if you relax the question to mean a function whose inverse requires, say, $\Omega(b^2)$ time to invert, rather than superpolynomial time, there are options. For example, you could keep the function $x_{t+1}=a\cdot x_t \text{ mod }n$. To invert that function, you need to find the the multiplicative inverse of $a \text{ mod } n$. This takes $O(b^2)$ time. Then you will be able to compute $x_{t}$ given any $x_{t+1}$ in, again $O(b^2)$ time, as $x_t = x_{t+1} \cdot a^{-1} \text{ mod }n$.

This function is easy to compute for several steps, if you are willing to do some precomputation. Note that $x_{t+1} = a \cdot x_t$ and $x_{t+2} = a\cdot x_{t+1} = a^2 x_{t}$, so $x_{t+k} = a^{k} \cdot x_t$. Now you can precompute $a, a^2, \ldots, a^k$ up to some $k$, and from then on you will be able to compute $a_{t+j}, 1 \leq j \leq k$ efficiently.


Which would be better for programming using Homotopy type theory Agda or Idris

Agda is definitely the better choice if you're doing Homotopy Type Theory.

Idris has several features that are specifically incompatible with HoTT. Specifically, you can use dependent pattern matching to prove Uniqueness of Identity Proofs (UIP), which, when combined with Univalence, allows you to prove False. There's also a type-case feature which you can use to directly prove False from univalence.
Agda has some features that are specifically designed to enable HoTT. Namely, it has a --without-K option, which ensures that you can't prove UIP or the related Axiom K. There's also a whole language extension for Cubical Type Theory, which uses a special notion of equality gives computational meaning to univalence.

Relevant reading:
Introduction to Univalent Foundations in Agda
Pattern Matching without K
Proof-relevant Unification in Agda
Cubical Agda Paper
Cubical Agda documentation
Cubical Agda tutorial


Formal notations of equivalencence between floating point expressions

One plausible notion of "nearly-equivalent" for floating-point expressions is that the relative error between the two is guaranteed small.

For example, if $x\ne 0$ and $y\ne 0$, define

$$D(x,y) = \max(\left|{x \over y} - 1\right|, \left|{y \over x} - 1\right|).$$

This measures the relative error between two real numbers.  Now, say that $x$ is nearly equivalent to $y$ if $D(x,y) \le \varepsilon$ (for some $\varepsilon$ fixed in advance; e.g., $\varepsilon = 10^{-6}$ or something).

Now, we can define two floating-point expressions e, e' to be nearly-equivalent if, for all possible assignments to the variables of these expressions, we have $D(e,e') \le \varepsilon$.

This implies that replacing e with e' will have only a small effect on the value of the expression (with "small" measured using relative error, rather than absolute error).

With these definitions, if you know that a, b, and c are positive and bounded away from zero, you should be able to prove that (a+b)+c and a+(b+c) are nearly-equivalent, for very small values of $\varepsilon$ (dependent on machine epsilon and the specific floating-point format used).  However, you can't prove them nearly-equivalent when nothing is known about a, b, c, because it is possible that (a+b)+c = 0 but a+(b+c) > 0, and then the relative error is infinite in this case.

Perhaps a more nuanced definition could allow them to be treated as nearly equivalent in the general case; I don't know.  For instance, we could alternatively imagine defining $D(x,y)$ to be the smallest value $\delta>0$ such that
$$\begin{align*}
(1-\delta) x - \delta &\le y \le (1+\delta) x + \delta\\
(1-\delta) y - \delta &\le x \le (1+\delta) y + \delta
\end{align*}$$
(This effectively captures a combination of relative error and absolute error.)  I suspect it might be possible to prove that (a+b)+c and a+(b+c) are nearly-equivalent, under this distance metric.  Is this useful?  I don't know.


How do I calculate offset from virtual address?

The page size indicates how much bits represent the offset in the physical frame. In this case you have pages of 4KB that means you need 12 bits because 2^12 = 4096. The offset in the physical frame always starts at the least significant bits. So for your example with
37064 = 0b1001 0000 1100 1000,

0000 1100 1000 = 200 in decimal is the offset in the physical frame. Since you have only one level of page tables, the rest of the bits to the left represent the actual physical page. You should not see it as a division even though it works. So the offset in the page table is 1001 = 9.


What are the elements of the modular ring mod 7?

You might be confusing the ring and the multiplicative group of invertible elements mod p.
The first one is isomorphic to the integers from 0 to p-1, 0 being the additive neutral element, and 1 being the multiplicative neutral element.

If p is prime, the intervible elements are the integers from 1 to p-1, and they form a multiplicative group.

By the way, when p is prime, such a ring (all elements except 0 are invertible) is called a field.


Given $k$ sorted lists, $O(n \log k)$ complexity, Mergesort rather than Heapsort

I would structure a formal proof of the runtime of your strategy as follows (This is, in structure, very similar to what you already wrote, but does not refer to omitted steps of an imaginary run of Mergesort.):

Arrange the $k$ lists as the leaves of an (almost) complete binary tree. Each internal node of the tree represents the merging of the two lists in its children. Clearly this tree has a height of $\lceil\log k\rceil$.

In this structure, the merges on each level of the tree combined will process each element exactly once.[1] Thus, they take a combined time in $\cal O(n)$. Adding up over all levels of the tree gives a runtime in $\cal O(n\log k)$.

Note that this argument does not require the lists to be of similar size.

Depending on the audience you may be required to elaborate some more on the $\cal O(n)$ bound. This can be done similar to the reasoning in the question:

Merging two lists with size $n_1$ and $n_2$ takes $n_1+n_2$ inserts and (in the worst case) $n_1+n_2-1$ comparisons. Thus, if we perform $i$ merges on a combined total of $n$ elements, they take $n$ inserts and (in the worst case) $n-i$ comparisons.

[1] If $k$ is not a power of $2$, the lowest level processes only a subset of the elements. Obviously the bound still holds for this case.


Deterministic context-free languages are closed under regular right-product

Here is an idea. You have to work out the details by your own.

Let $Q_R$ be the states of a DEA accepting $R$, and let $Q_L$ be the states of a deterministic PDA accepting $L$. You build now a new deterministic PDA $P$ that accepts $LR$ as follows:

The state space of $P$ is $Q'=Q_L\times \mathcal{P}(Q_R)$. If you have read $w$ and you are with $P$ in state $(s,T)$, this tells you the following: $L$ would be in state $s$ after reading $w$, and for every $t\in T$ there was a possibility that a prefix of $w$ was in $L$, and the remaining suffix of $w$ would have send the DEA for $R$ to state $t$. You accept if you are in a state $(s,T)$, that contains an accepting DEA-state in $T$. The transitions can be worked out straight-forward. Notice that it might be helpful to modify the PDA for $L$ first, such that it has a total transition function. You can achieve this easily by adding a non-accepting dummy states, that collects all missing transitions.


If P = NP, how do I prove I can find the maximum clique in polynomial time?

Assuming $P=NP$, then $CLIQUE \in P$, so you can test for a clique of size $k$ in polynomial time for all $k$. So you can just test for a clique of each size between $1$ and $n$ where $n$ is the number of nodes.

Now that you have the max clique size, you just need to find it. You can do that by removing an abitrary node, then re-running then seeing if there still exists a clique of max size. You will be left with the max size clique.


I believe this problem is NP-hard and it can be shown by a reduction from the vertex coloring problem with $k$ colors.

Assume we are given a graph $G' = (E',V')$ and we want to decide whether there exists a coloring of the vertices in $V'$ using only $k$ colors. To do so, we construct a new graph $G$ that consists of $G'$ as well as the complete graph $K_k$. Furthermore, we add edges of weight $-1$ from every vertex in $G'$ to every vertex in $K_k$. The edges inside of $G'$ as well as $K_k$ on the other hand have a very large weight.

Now, I claim that $G'$ admits a $k$-coloring, if and only if we can color $G$ and achieve a profit of $|V'|$. To see this, we first observe, that due to the large weight on the edges inside of $G'$ and $K_k$, both sub-components must be colored in such a way that no adjacent vertices inside of them share the same color. For $K_k$, this trivially implies a $k$-coloring. Next, note that all vertices with matching colors between $G'$ and $K_k$ add a profit of one to the total profit. However, there can be at most one such edge between $G'$ and $K_k$ for every vertex in $G'$. This is exactly the case if $G'$ has a $k$-coloring (using the same colors that were used in $K_k$). Thus $G'$ admits a $k$-coloring if and only if we can find a coloring of $G$ with a profit of $|V'|$. This in turn implies NP-hardness of your problem.


An example of a computable problem that is not in P

As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.


Finding longest prefix of a given string in set of strings that satisies some property

I'll answer your generic question.  Store the RULES in a trie.  Then, you can generate each prefix of the QUERY, traversing the trie as you go.  This will let you enumerate all prefixes P of QUERY that are a member of RULES.  For each such prefix P, you can then evaluate F(P,QUERY).  The running time is $O(n)$ where $n$ is the length of QUERY, plus the time to do at most $n$ invocations of F.  If you want, you can check the longest prefixes of QUERY first, in order of decreasing length, so that once you find a single prefix P where F(P,QUERY) returns true, you can stop immediately.

I don't believe it is possible to do better, without knowing something about F.  Obviously, any algorithm must take at least $\Omega(n)$ time (since you must read each character of QUERY), and must invoke F potentially on each prefix that is a member of RULES.


Find non-overlapping scheduled jobs with maximum cost

The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in "Polynomial Algorithms for Perfect Graphs", by M. Grötschel, L. Lovász, and A. Schrijver.

There are a number of special cases of perfect graphs for which people have discovered simpler and more efficient algorithms for this task. I don't know whether interval graphs fall into one of these special cases.


Does solving mathematical equations with Cellular Automata structures means it is universal?

If you can solve arbitrary equations involving an arbitrary number of unknowns, then you have shown universality, as explained below.  So there is a sense in which your broad question "solving mathematical equations means universality" is actually true -- but we have to precisely define what "mathematical equations" mean here. From your actual examples it seems you are not at the final goal of showing universality: it is not sufficient to solve ploynomial equations in a single variable.

If the equations you can solve are so-called Diophantine equations, then your system is universal.  That is, polynomials with multiple variables and integer coefficients, and solved with solutions in the natural numbers. According to the solution of Hilbert's tenth problem such equations encode recursively enumerable sets (of natural numbers). The question whether the polynomial can have value $0$ with fixed `input' value of the first variable codes membership of that value in the set we compute. Or as wikipedia states: "Every recursively enumerable set is Diophantine". This seems universal to me.

To see how complicated these polynomials can be, have a look at this Formula based on a system of Diophantine equations for the prime numbers. (This example generates prime numbers, so is slightly different, but can be tweaked.)

The right definition of universality is not always clear. We must encode input and output in a way suitable to the machine at hand (here the cellular automaton) without giving away parts of the solution. I remember some controversy concerning this.


Divide the image up into evenly sized grid cells.  Have one hash bucket per grid cell, and hash each point on the curve into the grid cell it falls in.  Sort all of the elements in each grid cell / bucket by the order of their abscissa.  Then, you can iterate over all of the non-empty grid cells, and for each, iterate over their sorted list to look for an instance of a large gap.  Each isthmus will correspond to a pair of adjacent elements in the sorted list that have a large difference in their abscissa.

You should probably do this do this four times: once with the original grid; again with that grid moved by one-half to the right; again with it moved one-half down; and again with it moved one-half to the right and one-half down.  If you use grid cells of side length $2D$, then this ensures that if the distance of the isthmus is $\le D$, it will be detected during one of these four iterations.


shortest form $s$ to $t$ stopping at $u$

What you said is true.

Using your notations:

$P$ : path from $s$ to $t$

$M$ : path from $s$ to $u$

$K$ : path from $u$ to $t$

Notice that $P,M,K$ are all shortest paths from their respective sources to their targets.

Following the logic above:

$M \cup K$ is the shortest path from $s$ to $u$ to $t$

hence if $|M \cup K|$ is a good enough result for you - accept it. If it's not, i.e $|M \cup K| > \alpha|P|$, then essentially no shorter path exists from $s$ to $t$ using $u$.

(you can try proving $|M \cup K| \geq |P|$, may help your intuition!


How to read off the set represented by a van-Emde-Boas tree?

If you haven't done so, I suggest you read chapter 20 from the beginning. They develop the final data structure bit by bit, supposedly for didactic reasons.

In 20.3.1, they write:

  min stores the minimum element in the vEB tree, and max stores the maximum element in the vEB tree. Furthermore, the element stored in min does not appear in any of the [subtrees].

What might confuse you is that the actual elements to not appear. As explained earlier in the chapter, the elements are encoded by position: the domain of the tree is $[0..15]$, and the subset is essentially encoded by a bit vector stored in the leaves of the tree. Figure 20.4 is annotated helpfully in this regard; note that the minimums are moved up to the min fields here, though.

In the full VEB tree, the encoding itself is a little tricky. Here goes:

Here is how you read the tree (ignore the dark summary nodes for this purpose):

u denotes the size of the domain of a node.
The root has domain [0..u-1].
The domain of a node cluser[i] is the the i-th chunk of size cluser[i].u in the domain of its parent.
If they are not nil, min and max are indices into the domain of the node.
If min and max are nil, the node represents no elements.

Examples:

root.cluster[1].min is 0; it represents element 0 + 1*4 * 0 = 3.
root.cluster[0].cluster[1].min/max are nil; therefore 0 + 0*4 + 1*2 + 0/1 = 2/3 are both not in the node.
But 2 is in the set anyway, since it's represented by root.min!
root.cluster[3].min is 2; therefore, 0 + 3*4 + 2 = 14 is in the set.
root.cluster[3].cluster[1].min/max are 1; therefore 0 + 3*4 + 1*2 + 1 = 15 is in the set.


Explanation of the graph coloring problem stated above:

So each vertex represents a class. Each edge represents a timing conflict between two classes. Suppose there was a graph with 4 vertices and a single edge between two. This would require only 2 colors, which translates to two time slots. Draw this graph. Write out a few scenarios of class schedules and draw their corresponding graphs to get a better idea. Answer the question on whether or not these graphs are planar. If so, what does that mean w.r.t. the four color theorem?


Strictly speaking it is possible to construct $2k$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $2k-1$ spanner.

Indeed, assuming Erdős Girth Conjecture, there are graphs $G=(V,E)$ with girth (length of the shortest cycle) $2k+2$ and $\Omega(n^{1+\frac{1}{k}})$ edges.

A $2k$ spanner $S$ of $G$ cannot exclude any edge $(u,v) \in E$. Indeed, if $(u,v)  \in E \setminus S$, either $u$ and $v$ are disconnected in $(V, S)$, or their distance in $(V, S)$ is at least $2k+1$. This is a contradiction.

This means that any $2k$ spanner of $G$ must have at least $\Omega(n^{1+\frac{1}{k}})$ edges. However, $O(n^{1+\frac{1}{k}})$ edges are already enough to guarantee the existence of $2k-1$ spanners in any graph, as you point out.


I'm not sure this is the right place for this question. Anyway, hexdump is interpreting your input as a 16-bit little-endian number, therefore the bytes 0x61 and 0x62 (which leave the pipe in the "correct" order) appear reversed. Try printf "ab" | hexdump -C .

00000000  61 62                                             |ab|
00000002


The cost at each level isn't $npk$. Let's look at the first few levels.

The cost at the top level, $l=0$, is indeed $npk$.
At the next level ($l=1$) you have three recursive calls: $T(n,p,k/2)$, $T(n,p/4,k)$, and $T(n/8,p,k)$ with costs $npk/2, npk/4, npk/8$ for a total cost at level two of
$$
\frac{npk}{2}+\frac{npk}{4}+\frac{npk}{8}=npk\cdot\frac{7}{8}
$$
At the subsequent level you have nine recursive calls and if you do a bit of arithmetic you see that the total cost at that level ($l=2$) is
$$
npk\cdot\left(\frac{7}{8}\right)^2
$$
You can show inductively that the cost at level $l$ will be
$$
npk\cdot\left(\frac{7}{8}\right)^l
$$
so the total cost up to and including level $M$ will be
$$
T(n,p,k)=\sum_{l=0}^Mnpk\cdot\left(\frac{7}{8}\right)^l=npk\cdot\frac{1-(7/8)^{M+1}}{1-7/8}<8npk
$$
since, as $M$ increases $(7/8)^{M+1}\rightarrow 0$. In other words, $T(n,p,k)=O(npk)$

It's clear that $T(n,p,k)>npk$, since that's the contribution at level zero, so we have, finally, $T(n,p,k)=\Theta(npk)$.


Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment.

For a TM $M$, let $K$ be the same as $K$ but ignoring inputs. That is, for any input, $K$ will first erase the input so that it looks like an empty input is given. Then $K$ will simulate $M$ on empty input. When the simulation halts, $K$ accepts. Now consider whether $\langle K\rangle\#\langle K\rangle$ is in the language specified in the question.

Exercise. Construction a reduction from the other halting problem, whether a given TM halts on a given input $x$.


Why is automatically labeling data in unsupervised learning hard?

The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what you can do with every-day data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question.

Some specific concerns:

"I can" != "I can build an algorithm which can".
Can you? Look at some data dumps from CERN and try to classify them.
What exactly are "features" (mathematically)?
What does "fits best" mean (mathematically)?

I recommend three things that will help you build a (better) intuition.

Study computability and complexity theory -- this will help you build intution for hardness of computational problems.
Program things -- this will help you build intution for hardness of implementing things.
Try to build an unsupervised learner and fall into all the pitfalls.


Are all instructions eventually converted to zero-operand instructions?

This will depend on the computer architecture.  zero-operand computer architectures use the stack, so to add 2+2:

PUSH 2 (into the stack),
PUSH 2 (again),
ADD (call the instruction - note that no operators are passed by).
POP ( 4 out of the stack)

but most other computer architectures e.g. use registers, memory addresses and values as the parameters to an instruction (in addition to the stack). For example the same 2+2 in a CISC computer.

MOX AX,02 (AX=0)
ADD AX,02 (AX=4)

However, if you're thinking in terms of translating a high level programming language into executable code e.g. one routine calling a subroutine the list of parameters most likely be passed by via stack and the number of parameters be reduced to 0 as in the first example.


reducing the halting problem to the blank tape problem

The reduction does not actually execute $M$, what its actually doing is the following mapping:

$\big(\langle M\rangle,w\big)\mapsto \langle M_w\rangle$

Where $M_w$ is the machine that when executed with blank tape, simulates the machine $M$ on input $w$. Preforming the reduction does not require that you execute $M$, you simply need to write down the code of $M_w$. Obviously $M$ halts on $w$ iff $M_w$ halts when executed with blank tape (we constructed $M_w$ specifically for this purpose), and the correctness of the reduction follows.


Is there a universal identity or zero value for folding?

Assume we can define

foldrUniversal :: Foldable t => (a -> b -> b) -> t a -> b

Then,

foo :: b
foo = foldrUniversal (\x y -> y) []

Is a way to form a value for any type b. If the type system is sane, this implies that foo does not terminate, as if we recursively defined foo = foo. Otherwise, all the types would be inhabited, making the logic associated to the type system to be inconsistent. A type system that allows this would be regarded as essentially "broken".

In real world languages, we do (grudgingly) allow some unwanted inhabitants. Non-terminating values ("bottom") are common ones, since they are mandatory in language with unconstrained recursion. null values are also used in many OOP based languages -- this is a so-called "billion dollar mistake", and should be avoided. Having a way to craft a "real" value of type b (say non-null, non-bottom) from nothing is too much.


Efficiently checking if two star graphs are disjoint

I assume the graph $G$ is fixed, and you are doing $M$ queries on $G$.

Your algorithm takes $O(Mn\log n+t)$ time, where $t$ is the amount of time to build the adjacency list. We can use the same time, but remove the log factor by merging the neighbor of $S_1$ and $S_2$ list in $O(n)$ time.

If $M \in \Omega(n)$, you can just compute the result for all queries in $O(n^2)$ time. Store the result in a new matrix $N$, initially all $0$s. Set $N_{i,j}=1$ for all $\{i,j\}\in \{i|M_{k,i}=1\}$. Thus $N_{i,j}=1$ iff $i$ and $j$ share a neighbor.

If you query for star $S_i,S_j$, it returns $\max(N_{i,j},M_{i,j})$, if it's $0$, then there is no common vertex for the stars.

It takes $O(M+n^2)$ time and $O(n^2)$ memory.


A Bloom filter doesn't have "buckets".

You can make a Bloom filter of any size you want.  The smaller it is, the higher the false positive rate.

This should be covered in any good introduction to Bloom filters, of which there are many.


Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances

The main idea is that if the NFA has at most 10 runs over each word, then when reading a word, at any given point the NFA can be in at most 10 states. Therefore in the powerset construction it suffices to consider sets of at most 10 states, of which there are polynomially many.

All remaining details are left to you.


On maximum independent set of line graphs

Finding a maximum independent set in $L(G)$ is equivalent to finding a maximum matching in $G$. For more, and a fast polynomial-time algorithm that work for e.g., line graphs, see [1].

[1] Lozin, V.V. and Milanič, M., 2008. On finding augmenting graphs. Discrete Applied Mathematics, 156(13), pp.2517-2529.


An $O(n^2)$ algorithm is possible.

Let $A$ be the given matrix.

You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$

Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$

as

$$S(i+1,j+1) = \min \{S(i,j), S(i+1,j), S(i,j+1)\} + 1 \quad \text{if}\quad  A[i+1,j+1] = 1$$

and

$$S(i+1,j+1) = 0 \ \text{if }\  A[i+1,j+1] = 0$$

There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.


For the first one, since $A \leq_p B$, there must exist a function $f \in \operatorname{FP}$, such that $x \in A$ if and only if $f(x) in B$ for an arbitrary word $x$. We can prove that $f$ is also a reduction from $\overline A$ to $\overline B$ as follows: Let x be an arbitrary word.
\begin{align}
x \in \overline A &\iff\\
x \notin  A &\iff\\
f(x) \notin B &\iff\\
f(x) \in \overline B&\\
&\qquad\square
\end{align}

Now for the second part, we know that 3-SAT is NP-complete. For a given language $A \in \operatorname{co-NP}$, let $B = \overline A$. Clearly $B \in \operatorname{NP}$ and hence, there is a reduction from $B$ to 3-SAT. As proven above, the same reduction is a reduction from $A$ to the complement of 3-SAT.


Number of states in DFA equivalent to given NFA

The standard powerset construction takes an NFA with $n$ states over an arbitrary alphabet and produces a DFA with $2^n$ states; this is tight for alphabets containing at least two symbols (see Chrobak's paper below for several references for this).

As for unary alphabets, Chrobak showed in his paper Finite automata and unary languages that a unary NFA with $n$ states can be converted to a unary DFA with $O(e^{\sqrt{n\log n}})$ states, and showed that this is tight (up to the hidden constant factor).


Decidability of checking whether all words accepted by a TM have an even number of 1s

First, it can be shown easily by Rice's theorem.

Alternatively, you can show a reduction from $\overline{HP}$ as follows:

$$f(\left< M \right>,x)=\left<M_x\right>$$

$M_x$ on input $w$:

run $M$ on $x$ for $|w|$ steps.
if M stopped then accept.
if the number of 1's in $w$ is even then accept, otherwise reject.

I'll let you verify the correctness.


Fractional vertex cover number may not be feasible? Very confusing!

The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that every linear program is infeasible or unbounded.

To give another example, sometimes you can’t divide by $x$. But if $x$ is a positive integer, then you can always divide by $x$. This in no way contradicts the fact that there exist $x$ that you can’t divide by - it just means that this complication doesn’t occur for positive integers.

To see that the minimum fractional vertex cover always exists, we have to show that the relaxation is feasible and bounded (from below). To see that it is feasible, notice that if you assign $w(v) = 1$ for all $v$, then you get a feasible solution. To see that it is bounded from below, notice that $w(v) \geq 0$ guarantees that the objective functions is always non-negative.


I think it is easier to prove if you first note note $$ L' = \{a^nb^mc^k|n\leq k \land n,m,k>0\} = \{a^nb^mc^k | n,m,k \geq 1 \} - \{a^nb^mc^k|n>k \land n,m,k>0\}$$ So if $\{a^nb^mc^k|n>k \land n,m,k>0 \}$ is regular then so is $\{a^nb^mc^k|n\leq k \land n,m,k>0\}$ since $\{a^nb^mc^k | n,m,k \geq 1 \}$ is regular and the difference of regular sets is a regular set.

But $L'$ is not regular, a contradiction. If you are NOT convinced that $L'$ is not regular then see the following proof using the Pumping lemma.

So, let's prove that $L' = \{a^nb^mc^k|n\leq k \land n,m,k>0\}$ is not regular using the Pumping lemma in order to obtain contradiction.

The Pumping Lemma:

Let $L$ be a regular set. Then there is a constant $n$ such that if $z$ is any word in $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and for all $i \geq 0$, $uv^iw \in L$.

How to prove

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$  in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = a^nb^nc^{n+1}$ (since $n < n+1$, $z \in L$).

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

5) You achieve a contradiction to the pumping lemma by showing that there exists $i$ such that $uv^iw \notin L$.

Since $z = a^nb^nc^{n+1} = uvw$ and $|uv| \leq n$, $uv$ is a string consisting of only $a$s, and so is $v$. If we choose $i=n+2$ then we get
$uvvw$ such that $uv^{n+2}w$ has at least $n+2$ $a$s which is greater than $n+1$ $c$s which does not belong to $L'$. But this contradicts to the Pumping lemma.

You may try to prove the second language  yourself.


How to generate the LR(0) finite state machine for a grammar

There is no loop, an item like $S\to \bullet{+}SS$ in your example might occur in several item sets of the LR automaton.  Let us continue the construction of state 2:

[State 2]
S -> * . S S
S -> . + S S
S -> . * S S
S -> . s

It has transitions to itself on "$*$", to state 1 on "$+$", to some state 3 with item set $\{S\to s\bullet\}$ on "$s$", and to yet another state on "$S$":

[State 4]                 [State 5]
S -> * S . S   --(S)-->   S -> * S S .
S -> . + S S
S -> . * S S
S -> . s

State 4 has again a transition to state 1 on "$+$", state 2 on "$*$", and state 3 on "$s$".  The construction is not complete yet, since you are missing some outgoing transitions from states 1 and 0, but hopefully you can finish it yourself.


The state of a qubit, or of a collection of qubits, is given by a state vector. However, most people would say that the output of a quantum computer is in fact the result of a measurement, which transforms the state into one which indicates a single outcome.

There are many ways to approach this, but the simplest one to describe mathematically is complete measurement in the standard basis. In this case, you transform a quantum state on $n$ qubits into an $n$-bit string.

Suppose that you have a state $|\psi\rangle \in \mathbb C^{2^n}$ on $n$ qubits, given by $$ |\psi\rangle \;=\; \sum_{x \in \{0,1\}^n} \!u_x \;|x_1 x_2 \cdots  x_n \rangle \;, \quad \text{such that } \sum\limits_{x\in\{0,1\}^n} \!|u_x|^2 = 1 .$$

In order to get a classical output from a quantum computer, one thing you can do is to perform a complete measurement in the standard basis. What this means is that we collapse the state to some single output vector $y \in \{0,1\}^n$. We get different bit-strings $y$ with different probabilities, governed by the formula
$$
 \Pr\nolimits_\psi(y) \;=\; \Bigl| \langle y | \psi \rangle \Bigr|^2
\;=\; \left|  \sum_{x \in \{0,1\}^n} \!u_x \; \langle y_1 y_2 \cdots y_n | x_1 x_2 \cdots x_n \rangle \right|^2
\;=\; \left|  u_y \right|^2 \;.
$$
The outcome is then just a random output string $y \in \{0,1\}^n$, where the probabilities are given by the non-negative real numbers $|u_y|^2$. Afterwards, you can compute with the measurement result $y \in \{0,1\}^n$ however you like, with a classical computer.

It's possible to describe performing a measurement only on a single bit, or with respect to bases other than the standard basis, but that's not really necessary to answer your question; measuring all of the qubits is certainly something you can do, and it's enough to get classical outputs from quantum computations.


If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?

From $f(n) = \Theta(g(n))$ you know that, for some positive constants $c \in \mathbb{R}^+$ and $\eta \in \mathbb{N}$, and for all $n \ge \eta$, it holds that $f(n) \ge c g(n)$, i.e., $g(n) \le \frac{1}{c} f(n)$.$^1$
Moreover, from $f(n) = o(h(n))$, you know that for any constant $c' > 0$ there is some $\eta'_{c'}$ such that $f(n) \le c' h(n)$ for any $n \ge \eta'_{c'}$.
Pick any constant $c'' > 0$ and let $\eta'' = \max\{\eta, \eta'_{c'}\}$ where $c' = c \cdot c'' > 0$.
From the previous inequalities we have that, for any $n \ge \eta''$:
$$
g(n) \le \frac{1}{c} f(n) \le \frac{1}{c} \cdot  c' h(n) =  c'' h(n),
$$
thus proving that $g(n) = o(h(n))$.

$^1$: In fact, the weaker condition $f(n) = \Omega(g(n))$ suffices.


Compute cache miss rate for the given code

As the cache is 4 doubles, for m=1, after accessing A[0], there are in the cache A[0]...A[3]. So next access A[1] is a hit and it is the same for A[2] and A[3]. Only access A[4] will be a miss. Hence miss rate is 0.25

For m=2, After accessing A[0], the cache holds the same line. Next access is A[2] which is a hit, and A[4] is a miss and so on. So miss rate is 0.5. Note that total cache size is 8 doubles. So when accessing A[8], cache line 0 is cleared and when A[1] will be accessed on later iterations, it will be again a miss.

For m=16 and n=2, one needs to look closely at the access patterns. Also do not forget that the cache is associative with two lines.

iteration 1 i=0, j=0 ->       A[0]  miss in line 0
iteration 2 i=0, j=1 16j+i -> A[16] miss in line 1
iteration 3 i=1, j=0 16j+i -> A[1]  hit in line 0 (because cache is 2 ways associative)
iteration 4 i=1, j=1 16j+i -> A[17] hit in line 1

and all access will be hits until iteration 8 (i=4, j=0). In that case, we access  A[4] that isn't in any cache and we restart a new cycle. So we have 2 misses for 8 iteations and miss rate is 0.25


Minimum sum of distance from entrance gate

I will try to give a solution. Tell me if I am mistaking anywhere.

First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill chairs from start. then next gate starts where 1st gate stopped. I leave it to you to check that this is the optimal solution.

Second observation : We can use dynamic programming here and start removing chairs. (Here I must say I am sorry as my notations might not match with general notations but I will try my best)

Let us denote the first problem as $f(10,(4,5),(6,2),(10,2))$. 10 is number of chairs, rest are ordered pairs stating number of gate and number of people. Now we will start removing chairs. There are 4 cases : chair is removed before 1st gate or between 1st and 2nd gate or 2nd and 3rd gate or after 3rd gate.

Now we can make the following observation : $f(10,(4,5),(6,2),(10,2))=\min[f(9,(3,5),(5,2),(9,2)),f(9,(4,5),(5,2),(9,2)),f(9,(4,5),(6,2),(9,2))]=\min(19,20,18)=18$ (Note that there are 3 cases here as the 4th case doesn't make sense.)

Here as there are 9 people we get the result (of $f$ using the first observation) from here. This is how you can do the problems. There might even be more gates you just have to generalize the function.

Did you understand what I tried to do?


This is indeed a concern for those building real-world applications - how does one measure "availability" - not the binary property discussed in the CAP theorem, but the experience for users of the system.

There is industry agreement around this concern, and a standardized method of measuring it applicable to all systems. (Note: as stated in the comments, this is a separate concept from the theoretical concept of availability, which is analyzed from an algorithm, or perhaps from a simulation of a system.)

The Apdex method assumes you have a definition of "satisfied service" at some response time. Let's say you consider a sub-1-second response time to satisfactory to define "available." Then, by convention, "tolerable" service is 4 times the target time: in our case, a response time from 1 to 4 seconds. Response times longer than 4 seconds are considered "frustrated."

Then, the Apdex score is the number of satisfied requests, plus half the number of tolerable requests, plus none of the frustrated requests (i.e. 0), all divided by the total number of requests.

For example, if you had 100 total requests, and 30 of them were satisfied (< 1s), 50 were tolerable (>1s but <4s) and 20 were frustrated (>4s), the apdex score for your service for the period of time those requests were serviced would be (30+25+0)/100, or 0.55. (An apdex score, by virtue of being a ratio, is always between 0 and 1)

Fun fact: a bunch of businesses then teamed up to turn this quite simple idea into a fully-fledged business. If you are a business, you can pay the Apdex Alliance money so they can produce education, webinars, and blogs, as well as certify compliant business so they may use the Apdex name and logo(!)

(I am not affiliated with the Alliance. I just like standards.)


Here is an outline of a parsing procedure. To prove that the grammar is unambiguous, you have to show that it works (parses the string), and furthermore that the parsing tree it produces is the unique one generating the string. If this question came up in the context of a course on compilers, then you should have learned the necessary tools.

The parser is a DPDA. The stack starts initialized with S, and then works according to the following rules, reading the input from left to right.

If the top-of-stack is S:

If the string starts aa, replace S with AS (S on top).
If the string starts ab, replace S with BS.
If the string starts and ends a, reject.
If the string ends, accept.
If the string starts b, delete S and process b again.

If the top-of-stack is A:

If the string starts b, delete A.
Otherwise, reject.

If the top-of-stack is B:

If the string starts b, replace B with S.
Otherwise, reject.

(Unless explicitly stated, the automaton consumes the characters it reads from the string.)
At the end of parsing, the automaton rejects unless the stack is empty.

I'll let you figure out how to construct the actual parse tree. You'll also have to figure out how to prove that this parsing tree is the unique one (if it is indeed the case).


Shuffling a list while keeping order relative to related elements

Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews described in his paper Generating a random linear extension of a partial order. This might even be implemented in some library.

Your particular case is generating a random lattice word of certain content (for the reduction, delete all letters or all numbers). This is a concept occurring in representation theory of the symmetric groups, generalizing the classical ballot sequences. If you're lucky you might find an algorithm for generating a random lattice word (in Mupad, for example, somebody implemented an algorithm for generating all lattice words).


No, in general. If $\bar{L_2}$ and $L_4$ are both the empty language, or have an empty intersection, then $L_4\cap\bar{L_2}\cap\bar{L_1}$ is regular, but that says nothing about whether $L_1$ is regular.


What do we know about covering the edges of a graph by disjoint paths?

You can cover the edges of a graph by cycles iff the graph is Eulerian (or has multiple Eulerian components). Notice that two cycles that share a vertex can always be combined into one cycle.


How do computers remember where they store things?

I'd suggest you look into the wonderful world of Compiler Construction! The answer is that it's a bit of a complicated process.

To try to give you an intuition, remember that variable names are purely there for the programmer's sake. The computer will ultimately turn everything into addresses at the end.

Local variables are (generally) stored on the stack: that is, they're part of the data structure that represents a function call. We can determine the complete list of variables that a function will (maybe) use by looking at that function, so the compiler can see how many variables it needs for this function and how much space each variable takes.

There's a little bit of magic called the stack pointer, which is a register which always stores the address of where the current stack starts.

Each variable is given a "stack offset", which is where in the stack it's stored. Then, when the program needs to access a variable x, the compiler replaces x with STACK_POINTER + x_offset, to get the actual physical place it's stored in memory.

Note that, this is why you get a pointer back when you use malloc or new in C or C++. You can't determine where exactly in memory a heap-allocated value is, so you have to keep a pointer to it. That pointer will be on the stack, but it will point to the heap.

The details of updating stacks for function calls and returns are complicated, so I'd reccomend The Dragon Book or The Tiger Book if you're interested.


Algorithm to find a shortest past under a special condition

Use a pathfinding algorithm, such as BFS, A*, or some other suitable algorithm.  Here each rectangle is treated as a vertex of the graph, and you imagine an edge from rectangle r1 to rectangle r2 if that's an allowed move (if you currently have rectangle r1, you can get to r2 in a single step).

Think of the rectangle as the "state" of the system at any point in time.  When you want to explore the statespace of a system, pathfinding algorithms are often worth a try.


Pick matrices such that each partial sum is positive

I'll represent you problem as:

  Let $S_1, \dots, S_n$ be sets of $p$ vectors of size $d$. Find a vector $v_i$ in each $S_i$ so that for every $k\le n$, $\displaystyle \sum\limits_{0\le i \le k}v_i$ has only non-negative coordinates.

Prop: This problem is in NP.

Proof: Once we have the set of indices / vectors, it's easy to check that they work in polynomial time.

Prop: For $d\ge 2$ constant and $p\ge 2$ constant, the problem (where $n$ is not bounded) is NP-hard.

Proof: We take an instance of the subset-sum problem, which is NP-hard. We have integers $i_1, \dots, i_n$. We define $M=|i_1|+\dots + |i_n|$.

We take $S_0=\{[M,M]\}$. For $1\le k\le n$, $S_k=\{[i_k, -i_k],[0, 0]\}$ and $S_{n+1}=\{[-|M|, -|M|]\}$.

All the partial sums will clearly be $\ge 0$ except maybe the last one. The last one will be $\ge 0$ iff $\sum i_k\ge 0$ and $\sum -i_k\ge 0$, i.e. iff $\sum i_k = 0$. So there is a solution iff the subset sum instance has one.

The following is a weaker result but it's written so I leave it here.

Prop: This problem with $2n$ sets of $p$ vectors of size $2d$ is at least as hard as $CNF-SAT$ on $n$ clauses with $p$ literals per clause and $d$ variables.

Proof: Take a set $C_1,\dots, C_n$ of clauses on $d$ variables, with $p$ literals per clause. $C_i=l_{i,1}\lor \dots \lor l_{i,p}$.

We write $v_k$ for the $k$th variable. To a positive literal $l_{i,j}=v_k$, we associate the vector $\phi(v_k)$ of dimension $2d$ that has a $1$ at the $k$th position and $0$s everywhere else. To a negative literal $l_{i,j}=\lnot v_j$ we associate the vector $\phi(v_k)$ of dimension $2d$ with a $1$ in $d+k$th position and zeros everywhere else.

Now, for $1\le k \le n$, we set $S_i=\{n\phi(v_k),n\phi(\lnot v_k)\}$ (and we add some useless vectors with big negative values if you really want the set to have size $p$). For $1\le i\le n$, we set $S_{n+k}=\{-\phi(l_{i,j}) / j\in\{1,\dots,n\}\}$.

The idea is the following. In the first $n$ coordinates, we store how many times we can use each of the variable, and in the next $n$ coordinates, we store how many times we can use each of the negation of variables. Then, at the beginning, in the first $n$ sets, we pick for each variable if it's true or false (by adding $n$ to the number of times we can use the variable, or to the number of times we can use its negation). The last $n$ sets then use the variables / negations to make the clause true. To make a clause true, you need to make one literal true, and the true ltterals will be exactly those for which the corresponding coordinate is $>0$ so that you can subtract $1$ while remaining $\ge 0$. If you chose $v_k$ to be false, the corresponding coordinate will remain $0$ for the whole thing so if you try to use it, it will become $<0$. And we add $n$ at the beginning because since there are $n$ clauses, we won't subtract more than $n$.

Prop: For $p\ge 3$, the problem (where $d$ and $n$ are not bounded) is $NP$-hard.

Proof: The reduction given above reduces $3-SAT$ to it in polynomial time. And $3-SAT$ is NP-hard.


Given a Turing machine M, is there a TM that computes the number of states M has?

I think you are a bit confused about TMs. A Turing machine, by canonical definition (as found in textbooks like [Sipser 1996], [Papadimitriou 1982] and [Hopcroft and Ullman 1979], as well as on Wikipedia), is a 7-tuple, one of which is $Q$, the set of states. So, the set of states of a Turing machine is not  computed; it is part of the definition of a TM.

In case of a universal TM, the input to the TM is the encoding of another TM (as well as its input). If you are familiar with functional programming, this is similar to a meta-circular evaluator (it is also similar to the eval function in some programming languages).

So, an encoding of a TM should encode all 7 elements that comprise the TM. Which means that a correct encoding of a TM must encode an enumeration of the set $Q$. Now, you can construct another TM that operates on the encoding of TMs (again, if you have done FP, it is similar to higher-order functions in FP).

If you know the encoding used, it should be trivial to retrieve the set of states of the input TM. You do need to count the number of elements in that set, but that should be Turing computable (because the set of states has to be finite). Now you have a TM that computes the number of state that another TM has.


Combining Runtime Complexity Expressions with respect to Dijkstra

Yes, you can just add them together.  If $|E|=O(|V|^2/\log|V|)$, then $O(|V|^2+|E|\log|V|)$ is the same thing as $O(|V|^2|)$, since the first term dominates.  If $|E|=\Omega(|V|^2/\log|V|)$, then it's the same thing as $O(|E|\log|V|)$, since the second term dominates.

It might help your thinking to bear in mind that $f + g = O(\max\{f,g\})$.


Use an interval tree.  It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(\log n)$ time.


Space complexity for connectivity problem with given graph diameter

The idea here is to use a reachability-based approach. Given $u, v \in V$ we ask ourselves whether $u$ reaches $v$ in $G$. By definition, there exists a path that connects $u$ and $v$ if and only if there exists a path of length at most $D$; there are at most $d^D$ such paths.

Loop over all pairs of nodes and all paths to answer the original question. The total space required by this procedure is $\left \lceil \log(n^2d^D) \right \rceil$ plus a constant amount.


Aaronson's result shows that $\Pi_2 \not\subset P^{N\!P}$ relative to a random oracle with probability 1. As he mentions, it had already been known that $N\! P != \mathrm{co}N\! P$ (and so $P \neq N\!P$ and $P \neq \mathrm{co}N\!P$) relative to a random oracle with probability 1: see the paper by Bennett and Gill. An oracle with respect to which $P \neq N\!P$ (and so $P \neq \mathrm{co}N\!P$) had been constructed earlier by Baker, Gill and Solovay. The construction is standard, and you can find many references online.


How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?

There are some things to consider here.

Conceptually, an algorithm that iterates once over the input array has runtime $\Omega(n)$ (and $O(n)$ if it does constant-time work per element), $n$ being the size of the array.

In application, if the algorithm is only ever called with arrays of length $n \leq n_0$ for some constant $n_0$, you may treat the used time as $O(n) \subseteq O(n_0) = O(1)$. Note that the $n$ here is probably not the one you use for your whole algorithm!

In practice, every algorithm runs constant time as real computers have finite memory. This is not an interesting model in the sense that it does not help to differentiate between algorithms that do behave very differently in practice, so we don't use it.

You may be interested in some of our reference questions on asymptotics, runtime analysis and the time used by arithmetic operations.


OK.  So the problem is as follows (with different notation):

Inputs: disjoint intervals $I_1,\dots,I_k$; disjoint intervals $J_1,\dots,J_m$
Output: disjoint intervals $K_1,\dots,K_n$ that are a "refinement" of the $I,J$-intervals

The $I$-intervals are not necessarily disjoint from the $J$-intervals.  We want the $K$-intervals to have the following property: if $x,y$ are in the same $K$-interval, then $x,y$ are in the same $I$-interval and $x,y$ are in the same $J$-interval.

This can be solved.  Basically, you use a 'merge' procedure vaguely akin go the merge operation from Mergesort, but adjusted to deal with intervals.    I'll assume the $I$-intervals are in sorted order, and the $J$-intervals are in sorted order (so $I_1$ is the leftmost/smallest interval of the $I$-intervals, etc.).

The algorithm considers how $I_1$ compares to $J_1$:

If $I_1$ is wholly to the left of $J_1$ (they don't overlap, and $I_1$ is smaller than $J_1$), then we output $I_1$, delete $I_1$ from the $I$-list, and continue.
If $I_1$ is wholly to the right of $J_1$ (they don't overlap, and $I_1$ is larger than $J_1$), then we output $J_1$, delete $J_1$ from the $J$-list, and continue.
If $I_1,J_1$ overlap and $I_1$ is contained in $J_1$, then do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so $c<a<b<d$), output the interval $[c,a]$, output the interval $[a,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap and $J_1$ is contained in $I_1$, do the symmetrical equivalent of the previous case.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $I_1$ is to the left of the left endpoint of $J_1$, do the following: if $I_1$ is the interval $[a,b]$ and $J_1$ is the interval $[c,d]$ (so that $a<c<b<d$), output the interval $[a,c]$, output the interval $[c,b]$, delete $I_1$ from the $I$-list, delete $J_1$ from the $J$-list, and insert $[b,d]$ to the front of the $J$-list.
If $I_1,J_1$ overlap but neither is wholly contained in the other, and the left endpoint of $J_1$ is to the left of the left endpoint of $I_1$,  do the symmetrical equivalent of the previous case.

As you can see, once you've sorted the intervals, this can be handled by a linear scan using a case analysis.  The total number of intervals in the output will be at most twice the total number of intervals in the input (i.e., $n \le 2(k+m)$).


Regular expression for a binary string containing even number of 0's

(1∗01∗01∗)∗ is actually wrong because it doesn't handle a string consisting of all 1's


Does this behavior have a formal name, and if so, what is it?

In many programming languages above statement always returns true, due to that the 3 conditions using negation are checked independently of each other.

It returns true not just due to "that the 3 conditions using negation are checked independently of each other", but because the expression (v != "x" || v != "y" || v != "z") is always necessarily true. In logic such expressions are called tautology, i.e. a formula that is true in every possible interpretation (Wikipedia).

But "this behavior or situation" does not have a special name in programming and is usually considered as a programming error.


Is Acceptance by Empty stack and Final state possible in the same PDA?

The PDA can accept $a^n$ because :

Till we don't read a $b$, we stay in start state.
The start state is a final state.

By acceptance by final state, the PDA accepts strings of the form $a^n$.

For strings $a^nb^n$, we have the following :

$X^n$ is pushed on the stack, by reading $a^n$ and looping over the start state.
For the first $b$, pop the stack, and continue to pop till we get only $Z$ in the stack.
When only $Z$ remainded, we have only one choice to do, and even if it's an epsilon transition, because it's the only possible transition at this point, the automaton is still deterministic.

We have also here an acceptance by final state.

In addition, we can define both acceptance by final state and by empty stack on the same PDA, but generally, the two don't lead to the same language. For your language, acceptance by empty stack lead to an empty language, because the stack can never be empty.


You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.


Pancake Sorting Graph Recursive Definition

From Wikipedia:

  The pancake graph $P_n$ or $n$-pancake graph is a graph whose vertices
  are the permutations of $n$ symbols from 1 to $n$ and its edges are given
  between permutations transitive by prefix reversals.

$P_n$ can be constructed from $n$ copies of $P_{n-1}$. We can construct $P_4$ from $P_3$, which looks like:

We start by making 4 copies of $P_3$ and numbering them 1 through $n$. Let's look at one particular copy and call it copy $i$. For each node in that instance of $P_{n-1}$, replace $i$ with $n$ and then append $i$ to the end of each sequence. For the $n$th copy, we don't have to do any replacing and can simply append $n$ to the end.

For example, for the 2nd copy of $P_3$ we'll first replace all the 2s with 4s and then append 2 to the end:

We now have a graph with nodes for all of the permutations of the elements from 1 to 4, and we have edges between sequences that can be transformed into one another by flipping a proper prefix. Edges from $P_{n-1}$ are still valid in $P_n$ because the only thing we've done is relabel and append a suffix.

Now go through each node and add a new edge going to the node corresponding to flipping the entire sequence. For example, (4,3,1,2) gets connected to (2,1,3,4), (1,2,3,4) gets connected to (4,3,2,1), etc.

The final graph for $P_4$ as shown in the Wikipedia article linked in the question looks like:


How does a Turing machine compute when its head is at the right-hand end of its configuration?


The informal definition of an algorithm in a popular textbook goes something like:

An algorithm is (1) a well defined computational procedure (2) that takes some input and (3) produces some output (4) for a well defined computational problem.

In your first case you have coded an algorithm where:
The problem is to find the factorial (part 4 of definition),
given int n as input (part 2 of definition),
the code describes the computation to be performed (part 1 of definition),
the output is the factorial (part 3 of definition).

In your second case:
The problem is to find the array element at position n (part 4 of definition),
given n as input (part 3 of definition),
the code describes the computation to be performed (part 2 of definition),
the output is the element at position n (part 1 of definition).

You have stored factorials there so it gives you factorials. If you had stored squares or cubes there you'd get squares or cubes, so it cannot be said that the second snippet by itself is an algorithm to compute factorials.

And if you say that an array look up along with an array having f(n) at position n is an algorithm to compute f(n) then you have gone so deep that there is no more computation below. A well defined computational procedure should be a finite piece of information. If an infinite array of factorials is a part of the computational procedure this does not hold. So that wouldn't be an algorithm to compute factorials.


Determine if an NFA accepts infinite language in polynomial time

Your algorithm is incorrect.  Think about the minimal DFA for $ab^*c$.

Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.


Original question.

  Could Any one provide a better solution for this?

I didn't see any solution provided, so that is not a valid question. Just pointing out that we expect an effort to be made by you on solving your problem before we put in an effort to help you.

Revised question.

  Which sorting method suits this kind of problem?

If I understand this correctly, it is not the choice of a sort algorithm that is important but getting the least number of moves that is important.

So first you can choose any sort method and find the correct order of the stones.

Now knowing the unsorted order and the sorted order, find the least number of moves. Since I will take it that there is a place off to the side that you can place one stone, it should take no more than a maximum of n+1 moves to sort all of the stones.

If that is not the kind of answer you expected, then you need to add more info to the question.


Is there a reversible transform that reduces the number of distinct values?

There are many reversible transformations that take a list of (let's say) non-negative integers and output a single integer. Here are two examples:
$$
2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdot 7^{a_4} \cdot 11^{a_5} \cdots \\
\langle a_1, \langle a_2, \langle a_3, \ldots, \langle a_{n-1}, a_n \rangle \cdots \rangle, \quad \langle a,b \rangle = \binom{a+b+1}{2} + a.
$$


Is function application actually a memory manipulation algorithm?

That seems reasonable to me, although I've never thought of other that way.  The critical point is that LC essentially involves variables and substitution.  So I wouldn't say it "hides" memory ops, exactly, that's just how LC substitution translates to Turing machinery.  On the other hand, substitution is not primitive - combinatory logic eliminates both variables and substitution.  So you might say LC introduces rather than hides something.


This is a classic Knapsack problem  some examples: Knapsack.java, JS example

Here is a pseudo code from Introduction to Algorithms, MIT: