There is no asymptotically better deterministic algorithm than the one that just checks, for each position $i=1,\dots,n$ whether $A[i]=B[i]=C[i]=0$.

This is easy to see since any correct algorithm must read at least one entry per value of $i$. To see this, suppose that there is an instance
$I = \langle A,B,C \rangle$ for which a correct algorithm $\mathcal{A}$ accesses neither of $A[i]$, $B[i]$, and $C[i]$, for some $i$.

Consider two instances  $I' = \langle A',B',C' \rangle$  and  $I'' = \langle A'',B'',C'' \rangle$ that are identical to $I$ except (possibly) for the fact that $A'[i]=B'[i]=C'[i]=0$ and $A'[i]=B'[i]=C'[i]\neq 0$. Clearly $\mathcal{A}$  must return the same set $S$ of indices on all of $I$, $I'$, and $I''$. If $i \in S$, then $\mathcal{A}$ fails on $I''$, otherwise $\mathcal{A}$ fails on $I'$.


Hendrik Jan is correct about the Knuth-Morris-Pratt algorithm (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition table for the DFA can be constructed. If $W$ is the pattern string you want to match, the time to build the table (and hence construct the DFA) is $O(|W|)$.

The central idea is that the failure table $T$ (I'll try to use the same names as wikipedia, just to get a ready-made example) tells you where you could be up to in the string if the current match doesn't work out, i.e. if you don't see the next character you're expecting, perhaps the beginning of the match you want has already been seen, you're just mistakenly further ahead, so you only want to "back-track" a little (note, there's no real backtracking in the usual algorithmic sense).

So, shamelessly stealing the example from wikipedia, say we have the failure table $T$:

$$\begin{array}{c|cccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
W[i] & A & B & C & D & A & B & D \\
T[i] & -1 & 0 & 0 & 0 & 0 & 1 & 2
\end{array}
$$

We can construct the DFA as follows; we have $|W|+1$ states, with a backbone of transitions that match the entire pattern. To match the table we'll call the start state $q_{-1}$ and the final state $q_{|W|}$ (so in the example $q_{6}$). The backbone is then the transitions $\delta(q_{i-1},W[i]) = q_{i}$, so in the example, we go from the start state $q_{-1}$ to state $q_{0}$ on an $A$ and from $q_{2}$ to $q_{3}$ on a $D$.

Now the trick is to add the correct "backwards" transitions so that we don't go too far back along the backbone when we get something wrong. This is where we us the failure function. If we're in state $q_{i-1}$ and we don't see $W[i]$ as the next symbol, then we can alternatively transition to $q_{T[i]}$ if we see $W[T[i]]$. From the example, if we're in state $q_{5}$, and we don't see a $D$, but we do see a $C$, we can go to $q_{2}$. Every other symbol returns us to the start state.

Reiterating; there are three types of transitions, the backbone transition if everything's going fine, the transition given by the failure table so we might be able to recover a bit, and $|\Sigma| - 2$ other transitions that take us back to the start state.

The start and final states are a little special of course, the start state can't go back further, so the failure recovery transition appears with the other transitions, and once we reach the final state, it doesn't matter what else we see, so it's a sink state too.

There's one final wrinkle, the case where the failure symbol is the same as the expected (e.g. $W[1]$ and $W[5]$) in this case we can just defer the decision until they're different, or we can create an NFA.

The example then results in a DFA that looks (barring mistakes) like:

The dashed transitions represent the "everything left over" transitions.

It should be easy enough to see that given the table, we can construct the DFA in $O(|W|)$ time (in one pass really). The table can also be constructed in $O(|W|)$ time - the source code on wikipedia is sufficient. If we get clever, of course we can skip the intermediate table step and use the table building algorithm to just create the DFA immediately. This running time is also the best we can hope for, as a DFA that matches only this string has to have at least $|W|$ transitions (and $|W|+1$ states), so we need to read the entire string $W$, which takes $\Omega(|W|)$ steps.


Difference between reductions in algebraic problems versus reductions in computational intractability

Reductions in computational complexity are similar to the reduction you described, but are usually given with bounds on the time or space. To be useful, these bounds are usually inconsequential (ie. the same or smaller) to the bounds of solving the problem.

Reductions in computational complexity are about converting one problem to another equivalent one. Usually one would also give bounds on how hard (how much time/space) a reduction takes as well. For example, all NP-complete problems have reductions to each-other, and their reductions are polynomially bounded. Since algorithms solving NP-complete problems are suspected to take exponential time on a deterministic Turing machine, the polynomial time reductions are inconsequential (compared with the time of actually solving the reduced problem), and thus these reductions make all of the NP-complete problems essentially equivalent. There can reductions between problems in other classes of complexity as well, and to be useful they would likely be bounded by something considered inconsequential to solving them.


Do all greedy algorithm produce just the first solution, no matter how bad it is?

Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of priority algorithms formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms cannot do.

Sometimes greedy algorithms give good results, sometimes they don't. When they do, the corresponding algorithm is very simple and fast. When they don't, we have to use more complicated algorithms. Here good results doesn't necessarily mean optimal results. The greedy algorithm for maximum coverage doesn't produce optimal results, only a $1-1/e$ approxmation – but this is also the best one can do in polynomial time (in the worst case), so the greedy algorithm is optimal with respect to the worst case approximation ratio.


If $f(n)=n^a$ for a given $a>0$, find $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$

For given $a>0$ and $f(n)=n^a$ we consider
$$g(n)= \begin{cases}{}
n^{a+1}, & n=2k\\
0, & n=2k-1
\end{cases}$$
for $k\in \mathbb{N}$


Proving that picking odd-numbered symbols can create the universal set from a non-regular language

You want to show that $\operatorname{odd}(L_1) = \{a,b\}^*$. This is a set equality claim, and you show it the way you can approach any such claim:

Show $\operatorname{odd}(L_1) \subseteq \{a,b\}^*$.

That's trivial.
Show $\operatorname{odd}(L_1) \supseteq \{a,b\}^*$.

Let $w \in \{a,b\}^*$. Can you construct $w' \in L_1$ so that $w = \operatorname{odd}(w')$?

   You only need to fix symbol counts, so brute force works:
 $w' = w_1 \overline{w_1}  \cdots w_n \overline{w_n}$ with
 $\overline{x}$ the "inverse", i.e. it maps $a$ to $b$ and vice versa.

Thus, $w \in \operatorname{odd}(L_1)$. Since $w$ was chosen arbitrarily,
the claim follows.

A similar proof works for $\operatorname{even}(L_1)$.


Efficiently remove nodes from a connected graph

Let $G$ be your graph. Compute any spanning tree $T$ of $G$. Perform a postorder visit of $T$, and keep track of the set $D$ of the first $k$ vertices visited ($T$ and $D$ can be computed by the same DFS visit).

The graph $G'$ obtained by deleting the vertices in $D$ from $G$ is still connected (and $T-D$ is a spanning tree of $G'$).
To prove this notice that if $v \in D$, then all descendants of $v$ in $T$ must belong to $D$ as well.


As far as I know, the main models of computability are λ-calculus, Turing machines and recursive functions. I am not aware of the situation regarding complexity in recursive functions, they may or may not be useless for complexity.

It may be seen as a fortunate coincidence that Turing machines, which are not so arguably very inefficient machines, are also a very good model of complexity. What made things natural is that there are a lot of transformations involving TMs that are polynomial. (Universal machine, simulation of a $n$-taped machine with a 1-taped machine, from an arbitrary alphabet to a binary one, simulating a PRAM, ...) and that polynomials are a class of functions stable by arithmetic operations and composition – which makes them a good candidate for complexity theory.

Pure λ-calculus was in itself useless for complexity. However a simple type system came into play and allowed guarantees of termination for some λ-terms in a very easy way. Then some other systems (systems T, F, ..) allowed a great expressiveness while keeping termination.

Efficiency or complexity being a refinement of termination and types being closely related to logic, later came light linear logics which characterizes several classes of complexity. (Elementary, P, and some variations for PSPACE and others). The research in this domain is very active and is not restricted to these complexity classes, and is not even restricted to the λ-calculus.

tl;dr: λ-calculus was useful for computability, termination and complexity theory.

However to give credit where credit is due Turing machines are a good and unanimous way to define what is complexity, but that's true only for loose bounds like "polynomial", not for tight bounds for which PRAM-like models are more suitable.


What actually is the concept of transparency? Why not call it Abstraction?

I agree with you.  The distinction is pretty weak.

I think the rationale is that transparent is supposed to mean "invisible", or "you don't even know it's there."  Abstraction means that you don't see the implementation of something, but you know that it's there.

Example: Consider Linux.  There's one command,  cp <srcfile> <destfile> for copying files on the mounted file system.  There's a completely different command, usually scp <user>@<machine-name>:<srcfile> <destfile> for copying a file from a remote filesystem that is mounted on a remote machine.  scp is an abstraction in that it hides all the implementation details about contacting the remote machine using the ip protocol, the encryption of the channel, and the mechanics of accessing the disks on the local and remote sides of the transfer.  But in no way is the distinction between a local file and a remote file transparent.  You have to use a different command depending on where the file is.

Worse, you can't edit the remote file in-place.  With a local file you just open the file in your text editor.  With a remote file you have to scp it to your local file system, edit the copy, and then scp the modified file back to the original location.


Retrieving data from hash table ordered by insertion time

Once you've put an element in any kind of container data structure like map or set, ordered or unordered, the data structure no longer remembers the order in which you called insert().  (The "ordered/unordered" distinction is whether the data structure keeps the elements in order by their key with respect to the less-than operator.)

If you want to know the order in which some events happened you will need to keep another container data structure, or some auxiliary information in the objects you are storing.  For example if you want to be able to iterate through in the order in which you inserted: keep both an unordered_map and a vector of references to the objects you inserted.  Every time you do an insertion you also push_back a reference to what you just inserted.  (But be careful, if you are doing this in C++, that you aren't also removing objects from the unordered map, because then the references in the vector will become invalid.)

If you want a number associated with each element stored in the map ("this was the 42nd inserted"), then you should augment your map datatype with, (a) a global counter and (b) a way to store both an object and a number (e.g., store struct {T the_object; int insert_order;} instead of objects of type T), and (c) wrap the insert operators so that they increment the counter and insert the new number along with the new object.


What's the error in the following proof of the halting problem decidability?

A Turing machine may run forever without ever entering any kind of cycle. (Consider the machine which always just moves its head to the right.)


Finding closest edge to a point in a planar graph

Use a Voronoi diagram of the line segments
As @D.W. noted, a Voronoi diagram of line segments1 is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of Computational Geometry by de Berg et al. But I don't think you should do this.
Don't use a sweepline algorithm
However, while sweep-line algorithms are nice in theory, implementing them in a robust and efficient manner turns out to be quite difficult in practice. I think this goes doubly so for the Bentley-Ottman algorithm. Therefore, in the field of algorithm engineering, which concerns itself with implementing algorithmic ideas on a computer, (randomized) incremental construction methods are usually preferred. These methods are much easier to make robust and are dynamic (support modifications efficiently) by default2. The (expected) running time is also often not so bad in theory, and can beat the theoretically superior algorithm in practice. (if someone managed to implement the other algorithm effectively, that is).
Use random incremental construction
I recommend the algorithm by Karavelas (described in this conference paper ). It computes a line segment Voronoi diagram in $O((n+m)\log^2 n)$ expected time, together with a hierarchical structure that supports nearest neighbor queries in $O(\log^2 n)$ expected time. (Here, $n$ is number of segments, and $m$ the number of points)
This algorithm is implemented in the CGAL library, see this manual page for the details.

1: Formally, this is only a proper generalisation of a Voronoi diagram if the line segments are disjoint, because if the nearest point is point shared by two segments, we cannot uniquely determine its cell. If these line segments form the embedding of a planar graph, they only intersect at the end-points. In this case, we can often get away with shrinking the segments a tiny bit s.t. the endpoints are now disjoint. Another option is to consider the open segments and their endpoints as 3 separate objects, and make a Voronoi diagram of those.
2: More precisely, insertion is already implemented, and deletion is usually not too hard to add.


The loop invariant probably involves the loop control variable.  If so, it only makes sense to ask if the invariant is true, when the loop control variable is initialized. When the loop control variable is uninitialized, expressions that involve it are undefined.

Consider a simple example, a loop whose purpose is to determine whether all the elements of a (0-based) array $a$ are equal:

   all_equal = true
   for (i = 1; i < a.size; i++)
      if a[i-1] ≠ a[i]
         all_equal = false

Here the loop invariant is that $all\_equal$ is true if and only if the $a[k]$ are all equal for each $k$ with $0 \le k \le i$.

This is makes no sense at all unless the loop control variable $i$ has a well-defined value.  Before the initialization, it doesn't. After the initialization, we have $i=1$, and the loop invariant is true.


According to ISGCI this graph is known as "A".

Looking at some references, it also seems that there is really no common well-known name.


You are asking the question for Euclidean Steiner Trees. For Euclidean Steiner Tree problem one can show that "points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles". That's why you need two steiner vertices instead of just one for 4 point solution. If you take just one extra point the degree will be 4 and angles also will not remain 120 degree.

To prove the property of Euclidean Steiner Trees take help of your favorite search engine. A good reference. See section 3.


here is a half-baked answer:
I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular:

Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi.

I am saying it's a half-baked answer, because I haven't had chance to read any of his works.


Ackerman hierarchy for higher order primitive recursion in System T

(This is a very partial answer, only addressing the first point, and not the main question about the hierarchy.)

I don't have a proof to point out to you, but the idea is that a single first-order recursor on naturals such as
$$
\begin{array}{l}
rec: (nat \to nat) \to nat \to nat \to nat
\\
rec\ f\; z\; n = f(f(\ldots f(z))) \qquad \mbox{($n$ times $f$)}
\end{array}
$$

would be much less powerful than having the full (primitive) recursion scheme

$$
rec_U: (U \to U) \to U \to nat \to U
$$

since the latter roughly resembles a polymorphic term in System F, which can be used at many types $U$.

Indeed, the basic $rec$ only gives us access to the first order primitive recursion scheme, as we can find in a computability / recursion theory book.
With only that, we know functions like Ackermann's are not definable. (Well, this is not that obvious since here we also have higher-order lambdas, it's only recursion which is constrained. But the point should stand anyway, I think.)

With the $rec_U$ scheme, instead, we can choose $U = nat \to nat$, which allows us to define Ackermann's function, as Girard shows in the book mentioned by the OP. Hence, the scheme is strictly more powerful.


Sorting algorithm that moves element to a 2-dimensional array

What you have come up with is a sligthly less memory efficient version of counting sort.

This algorithm works in $\mathcal{O}(n + range)$ time where $n$ is the number of elements in the vector $unsorted$ and $max$ and $min$ are as defined in your program.

Your implementation uses $\mathcal{O}(n + range)$ memory. You can make it more memory efficient by just keeping track of how many times the same number in the vector 'unsorted' occurs rather than maintaining a vector with repeated instances of the same element i.e.

vector<int> presorted(range+1);
for(int i = 0; i < unsorted.size(); i++)
     presorted[unsorted[i] - min]++

It will now use only $\mathcal{O}(range)$ memory.

Yes you are correct, this method might potentially use up a lot of memory if the difference between the smallest and largest elements of the vector is too great.

For those who are not fluent in C++:

OP is finding the smallest and largest elements of the unsorted array $max$ and $min$ respectively.
He is initializing an array of size $max - min$ and creating an empty linked list in each position of the array (in this code it is the vector of vector of integers $presorted$).
Then each element of $unsorted$ is added as a new node in the linked list at $presorted[unsorted[i] - min]$. In a random access computational model this operation will take $\mathcal{O}(1)$ time and hence each element of $unsorted$ is added to its appropriate bucket in constant time.
Then he is just iterating in the array of linked lists and compressing it to the final array $sorted$ which is the final output.


Is there a relationship between visitor pattern and DeMorgan's Law?

The best way to explain it is
$$\mathsf{Bool} \to C \cong C \times C,$$
which is a special case of
$$(A + B) \to C \cong (A \to C) \times (B \to C).$$
Read the above as follows: as sum is equivalent to a pair of visitors.
(By the way, this is not the de Morgan law. It does not have a name, as far as I know. It's a general consequence of the definition of the concepts involved.)


Presumably you don't really get a manifold.

For one thing, there's probably a nonzero chance of any particular coordinate being perturbed arbitrarily -- an impurity in a crystal, a grey hair on a head of brown ones, etc. -- so you'd really get something more like a probability distribution concentrated near a lower dimensional platonic ideal.

Second, there are probably all sorts of behaviors going on that aren't allowed in a manifold, like self-intersections, edges, and components of different dimensions.

That said, simple statements like "the left side of someone's face usually looks about like the mirror image of the right" cut the dimensionality of the space nearly in half.  Add enough such independent conditions and you whittle things down quite a bit.


Proving $(a+b)^* = b^*(ab^*)^*$ equationally

A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free):
$$
\begin{align*}
(a+b)^* &= (b+a)^* && C2 \\
&= (b^*a)^*b^* && C11 \\
&= (\epsilon+b^*(ab^*)^*a)b^* && C12 \\
&= b^* + b^*(ab^*)^*ab^* && C9 \\
&= b^*(\epsilon + (ab^*)^*ab^*) && C8 \\
&= b^*(\epsilon + \epsilon(ab^*\epsilon)^*ab^*) && C6,C7 \\
&= b^*(\epsilon ab^*)^* && C12 \\
&= b^* (ab^*)^* && C7
\end{align*}
$$


Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone NP-complete) becomes a finite language when restricted to instances of constant size. All finite languages can be decided in constant time.

If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that P$\,=\,$NP. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of P and NP don't depend on that short-hand.


in function declarations, what advantages are there to having the type of the parameter specified after the parameter name?

It's completely arbitrary.

In a given programming language, one would hope that the same convention is used throughout, so either int f(int x) or f(x: int): int but not int f(x: int) or f(int x): int; but even that is arbitrary.


AI Search - State in the toy vacuum problem

"State" is the sum of all information that describes the current situation of the robot, and everything about that past that might be relevant.  I don't understand your diagram so I can't tell you what it is specifically in your particular example, but it appears that the state includes the current location of the vacuum and which locations currently have dirt.  So, you might have one variable that defines where the robot is located, one variable that indicates whether there is dirt in the left room, and one variable that indicates whether there is dirt in the right room.
In AI search, we often assume that we know the set of all possible states and all ways to transition between them.  We give that information as input to the search algorithm, and it finds a way to reach a desired state from where we currently are.


Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?

The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing machine using space $s(n)$ to a deterministic one using space $O(s(n)^2)$, and this is suspected to be tight in general; see for example this question on cstheory.
Linear-bounded automata correspond to a class of grammars, context-sensitive grammars, in the following strong sense: a language can be described by a context-sensitive grammar iff it is accepted by some linear-bounded automaton. We only know how to prove this result if the linear-bounded automata are allowed to be nondeterministic. Indeed, assuming that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ (a conjecture which is much weaker than the tightness of Savitch's theorem), there exists a context-sensitive language which cannot be decided by a deterministic linear-bounded automaton.


$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable?

A $k$-ary relation $R \subseteq \mathbb{N}^k$ is recursively enumerable if its indicator function $f_R$ defined by

$$f_R(n_1,\ldots,n_k) = \begin{cases} 1 & \text{if } R(n_1,\ldots,n_k) \\
0 & \text{otherwise} \end{cases}$$

is a partial recursive function.

So if $f: \mathbb{N} \rightarrow \mathbb{N}$ is a partial recursive function, it is easy to see that the graph

$$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set. We have $f_{R_f}(m,n) = 1 - \mathrm{sg}(f(m) - n)$, where $\mathrm{sg}(n)$ is the primitive recursive function that is $0$ for $n=0$ and $1$ otherwise. Since we can express the indicator function $I_{R_f}$ of the graph as the composition of partial recursive functions, we therefore conclude that it is also a partical recursive function.

Conversely, if $$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set with indicator function $I_{R_f}$, then

$$f(m) = \mu n. [ (1 - I_{R_f}(m,n)) = 0 ] $$

Here $\mu n.P(n)$ denotes unbounded mineralization over the unary predicate $P(n)$.


What is the significance of the vector dimension in semidefinite programming relaxations?

Vector programs are solved by solving semidefinite programs. The basic idea is that if $v_1,\ldots,v_n$ are vectors, then the matrix $V_{ij} = \langle v_i,v_j \rangle$ is positive semidefinite:
$$ \alpha' V \alpha = \sum_{i,j} \alpha_i \alpha_j \langle v_i, v_j \rangle = \left\|\sum_i \alpha_i v_i\right\|^2. $$
The converse is also true: a positive semidefinite $n \times n$ matrix $V$ of rank $r$ can be written as $V = LL'$, where $L$ is $n \times r$ (this is known as the Cholesky decomposition). Furthermore, $L$ can be found effectively given $V$. If $\ell_1,\ldots,\ell_n$ are the $r$-dimensional rows of $L$, then $V_{ij} = \ell_i \ell'_j = \langle \ell_i, \ell_j \rangle$. We can therefore optimize a vector program involving inner products of vectors $v_i$ by solving a semidefinite program. Rank constraints are not convex, and so we cannot really control the dimension of the vectors other than the trivial bound $n$.

As you mention, the analysis in the particular case of MAX-CUT only uses the two-dimensional projections. This shows that even if you could somehow guarantee that $\operatorname{rank} V = 2$ (recall that the rank corresponds to the dimension), the analysis wouldn't get better. On the other hand, if you could guarantee than $\operatorname{rank} V = 1$, you will have solved MAX-CUT exactly. This shows that the latter constraint is NP-hard to realize. It is probably the case that any non-trivial rank constraint cannot be enforced in polynomial time, and any constant rank constraint is NP-hard.


Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free?

A word like $a^nb^nc^n$ should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments.

Also, each splitting $z=uvxyz$ can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different $i$ for each splitting. That is very natural here as $a$ has the minimal number of occurrences, and contradiction is reached by adding occurrences, whereas for $c$ deletion (choosing $i=0$) will get you into trouble.


MST: Is there such an example of a graph with unique mst and not unique light edge?

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is:

Grow the tree, adding nodes one by one.
On each step, select the minimum weight
edge leading to a new node.

You realise that whatever is the starting node, you have at least 2 choices. If the MST was unique, there would be leaf nodes having only one possible edge. Therefore there are several possible MST.


lambda calculus beta reductions: ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

$$
(\lambda f. \lambda x .f x f)
(\lambda y.\lambda g. g (* y y))
2
(\lambda a. a)
$$

The leftmost redex $(\lambda a.b)c$ is

$$(\lambda f. \lambda x .f x f)(\lambda y.\lambda g. g (* y y))$$

with

$a = f$
$b = \lambda x .f x f$
$c = (\lambda y.\lambda g. g (* y y))$

Don't forget to make sure that $x$ doesn't exist in $c$, because if so then doing an immediate beta reduction would change the meaning of the expression.  So the redex reduces to:

$$(\lambda x .(\lambda y.\lambda g. g (* y y)) x (\lambda y.\lambda g. g (* y y)))$$

Overall giving

$$
(\lambda x . (\lambda y.\lambda g. g (* y y)) x (\lambda y.\lambda g. g (* y y)))
2
(\lambda a. a)
$$

The next redex is $(\lambda y. \cdots)x$


Algorithm for finding "mean center" of unweighted graph

Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.

Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.

If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.

Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)


Algorithm to find repeated patterns in a large string

To improve your brute force, you would only need to look at the substrings of minimum length, as longer substrings will occur at most as many times as their own substrings. This should take linear time to create the dictionary, and O(nlog(n)) to sort.

If this is too memory intensive, you could do pruning by first brute-forcing this for say, substrings of length 2, and then only consider min-length substrings that contain at least k of the most common 2-length substrings for some threshold k.


Are algorithms (and efficiency in general) getting less important?

On the contrary. At the same time that hardware is getting cheaper, several other developments take place.

First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large amounts of data, and do it quickly. Algorithms are more important than ever.

Second, the area of machine learning is growing strong, and full of algorithms (albeit of a different kind than what you learn in your BA). The area is thriving, and every so often a truly new algorithm is invented, and improves performance significantly.

Third, distributed algorithms have become more important, since we are hitting a roadblock in increasing CPU processing speed. Nowadays computing power is being increased by parallelizing, and that involves dedicated algorithms.

Fourth, to counterbalance the increasing power of CPUs, modern programming paradigms employ virtual machine methods to combat security loopholes. That slows these programs down by an appreciable factor. Adding to the conundrum, your operating system is investing more CPU time on bells and whistles, leaving less CPU time for your actual programs, which could include CPU-intensive algorithms such as video compression and decompression. So while hardware is faster, it's not used as efficiently.

Summarizing, efficient algorithms are necessary to handle large amounts of data; new kinds of algorithms are popping up in the area of artificial intelligence; distributed algorithms are coming into focus; and CPU power is harnessed less efficiently for various reasons (but mainly, because computers are getting more powerful). Algorithms are not dead yet.


How can I get index of combination from element indices

(BTW, I think the code in the first edition of the question was the issue -- not the background info with respect to the sexagenary cycle, which is actually good to include to understand the motivation for the problem).
To put the problem a bit differently, you have the sets $\mathbb{Z}/m\mathbb{Z}$ =  $\{0,1,...,m-1\}$ and $\mathbb{Z}/n\mathbb{Z} = \{0,1,...,n-1\}$, and you start with the pair (0,0), then (1,1), etc., basically applying the mapping $(x,y)\mapsto(x+1 \mod m,y+1 \mod n)$, until you wrap back around to $(0,0)$. In the easy case where $m=n$ then, you can see that $(i,i)$ was the $i$-th term in the sequence  (0-based). In general, if you are asking about the index of $(i,j)$, then you are effectively trying to solve the system of congruences
\begin{align*}
x &\equiv i \mod m \\
x &\equiv j \mod n
\end{align*}
for $x$. Here $x$ represents how many times you did the $(+1,+1)$ operation starting with $(0,0)$.
When $m$ and $n$ are coprime, the Chinese remainder theorem gives you an algorithm to compute the solution.  When they are not coprime, then that system in general may not have a solution, but in the case where the system was created by the above construction, it does. This math.stackexchange answer shows you how to find the (unique) solution in the range $[0,LCM(m,n))$.


Why Can't Reverse Hashing Prove $P \neq NP$?

Give a polynomial time hash function that takes exponential time to compute the inverse of.

That’s an open problem. It can’t currently be used to resolve $P$ vs $NP$ because no one knows if there is an example of such a function. In CS, we often assume that $P\neq NP$ and that there are cryptographically secure hashes, but that’s an (experienced based) assumption, not a probable fact.


Choose minimum subset of edges in tree that connects all important nodes

Note this is equivalently finding edges with minimum sum of weights such that their removal leaves each important node in a separate component, which is called minimum multiway cut problem.

This problem is NP-hard in general graph, while Chopra, Sunil, and Mendu R. Rao developed a polynomial time algorithm for tree in 1991 [1].

[1] Chopra, Sunil, and Mendu R. Rao. "On the multiway cut polyhedron." Networks 21.1 (1991): 51-89.


Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?

Yes, well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE, at least for the two notations (grammars) given in the question!

The normal notation is indeed a visibly pushdown language, with $\Sigma_c=\{(\}$, $\Sigma_r=\{)\}$. When we encounter the symbol $($, then we push the number of still expected occurrences of of terms or proposition (and whether we expect terms or propositions) on the stack. When we encounter the symbol $)$, then we first check that exactly the expected number of terms or proposition occurred, then overwrite the counter by the value on the stack, and decrease it by one. The counter is finite, because its maximum value is the maximum arity of the signature, and zero is its minimal value, because we reject when the counter would become negative.

The given RPN grammar is also a visibly pushdown language, because the maximum arity of the given signature doesn't exceed two. You push on the stack the variables, pop from the stack for the binary function, the quantifier and the equality relation, and do nothing for the rest. What we actually push on the stack is the type (empty, term, or proposition) of the top element of the "real RPN" stack, before the new element is pushed. Convince yourself that we can always know this type (variable is not a type here).

Also RNP formulas for signatures with higher arity can be recognized in LOGSPACE, because they can be converted in constant time and space to an equivalent signature that whose arity doesn't exceed two, by using a pair constructor.


How does Paxos maintain the promise that future proposal will not break the current chosen value without knowing the future?

The bold section is saying that before proposing a value know if a value is accepted or if there is a higher proposal number that is chosen by one of the majority. If there is a higher proposal number, the proposer needs to propose a higher number than that is already proposed. If a value is already accepted then majority should know if a value is accepted. The proposer accepts the value. The majority is because two majorities always overlap.


Similarity between Min-Conflicts and Coordinate Descent in CSPs?

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent?

In the same sense that A* and BFS are essentially equivalent except for the choice of which node to visit next, yes.

  If so why are classified differently?

There are some problems for which Min-Conflicts performs asymptotically faster (in the expected-time sense) than Coordinate Descent, and vice versa. Ditto, there are some problems where one (generally) converges and the other (generally) doesn't.


Using reduction to prove that a given language is not recursively enumerable

Assume that $L$ is recursively enumerable. We can reduce the Halting problem to $L$ as following. Given $\langle M, w \rangle$, create a TM $M'$ which halts only on the input $w$, and infinitely loops if the input is different from $w$. Clearly $L(M') = \{w\}$ and $L(M) \cap L(M') = \emptyset \iff \langle M,M' \rangle \in L \iff \langle M, w \rangle \notin HALT$. This shows that $\overline{HALT}$ is recursively enumerable. Since $HALT$ is also r.e. it follows that $HALT$ is decidable which is impossible. Thus $L$ is not recursively enumerable.

$HALT = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w \}$.


Given an instance $G = (V,E)$ for Max-Cut, we create an instance of Max-2Sat with one variable $x_v$ per vertex $v \in V$, and two clauses per edge $(v,w) \in E$:
$$ x_v \lor x_w, \qquad\overline{x_v} \lor \overline{x_w}. $$
Every subset of $V$ corresponds to a truth assignment for the $x_v$ in a natural way. Furthermore, the number of clauses satisfied is exactly
$$ |E| + |E(V,\overline{V})|. $$
Intuitively, the edge $(v,w)$ is cut iff $(x_v \lor x_w) \land (\overline{x_v} \lor \overline{x_w})$, and this is why this reduction works.


If $X$ is any non-constant source, then any codeword in any prefix code for $X$ has length at least $1$, and so $R \geq 1$. Therefore if $X$ is a source with very low entropy then there's a large discrepancy between $H(X) \approx 0$ and $R \approx 1$.

As a concrete example, consider a binary source in which the probability of one of the options is $\epsilon$. Then $H(X) = \epsilon \log (1/\epsilon) + O(\epsilon)$ whereas $R = 1$.


In this particular case, you can just go over all possibilities.

The dynamic programming approach is to compute recursively the maximal profit that can be obtained from using $x$ refrigerators in the first $y$ stores (and not using any in the other stores). I'll let you fill in the missing details.


Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case).

Consider all intervals $(I_n=[\![s_n,e_n]\!])_{0\leq n<p}$, and sort them by increasing start time $s_n$, breaking ties arbitrarily  [time $\mathcal{O}(p\cdot \log p)$]
Build a stack containing only the first interval (i.e. the one with the smallest start). For each subsequent interval: if [the interval doesn't overlap with the head of the stack] then [push it] else [merge it with the head of the stack] [time $\mathcal{O}(p)$]

What we've done here is merge the intervals $(I_n)_n$ so as to rewrite $\bigcup I_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}_n=[\![\tilde{s}_n,\tilde{b}_n]\!])_n$

Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $[\![0,\tilde{s}_0[\![$ and $]\!]\tilde{s}_{-1},L]\!]$) [time $\mathcal{O}(p)$]

Overall the runtime is $\mathcal{O}(p\cdot \log p)$.


$\newcommand{\stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}$Your comment is correct in that there are $4^5=1024$ functions from $A$ to $B$.

Letting $|A| =n, |B| = m$ this can be seen by the identity:

$$\sum_{k=0}^n \stirling{n}{k} m(m - 1) \dotsb (m - k + 1) = m^n$$

This describes all the ordered partitions of $A$ over $B$ where each partition is an assignment to the same item in $B$.

A less heady explanation (and perhaps easier to visualize) is the following:

We have a vector of length $n$. Each position in this vector can choose $m$ possible values. That is, the $i$th value in the vector represents what $f(a_i)$ maps to. How many $n$-length vectors over $m$ values can we have? Exactly $m^n$.


What makes data flow analysis higher level than control flow analysis?

Look at Wikipedia article "Control Flow". It contains typical flow chart. Arcs are the ways where control token moves from one node to another.

Now imagine you want to employ parallelism and launch several control tokens. Immediately a problem arise: how to isolate pieces of data from simultaneous modification by different control tokens. To tackle with this problem, we divide our data in parts - one parts belong to dedicated control token, and others are  for exchanging information between control tokens. The result is a dataflow diagram (or chart). That is, to manage data in parallel environment, we have to split data into pieces and explicitly manipulate them. Data flow is no more than parallel control flow.

Functional programming is another story. While there exist both control flow (von Neumann) and data flow processors, there is no functional processor. Functional programs can be compiled both to data and control flow processors. But since ordinary imperative programs cannot be directly compiled to dataflow processors (they first have to be converted to dataflow programs, which is hard), and converting functional programs to dataflow representation is easy, we can consider functional programming as a variant of dataflow programming.

And finally, consider distributed computing. Since it involves multiple computers with no shared memory, it is best described as dataflow computing and not as imperative computing. What happens inside computer nodes, is it functional programming or imperative, does not matter. But the way how data are exchanged matters. And using functional data structures to exchange data between nodes is very appropriate.


How to evaluate the clock cycle for MIPS single cycle CPU

Now that you have (dramatically) modified your question:

The author of the book is correct.  RD1 can not be on the critical path because the time to read RD1 is the same as the time to read RD2, but then RD2 needs to go through the mux in front of the ALU.  If the time to read RD2 > T(Sext) then RD2 is on the critical path, if T(Sext) > T(RFread) then Sext is on the critical path.  That's what the Max() operator does.  Either way T(mux) needs to be in the expression.

Your last expression with T(Sext) +T(mux) is the same as what the author's expression gives in the case that T(Sext) > T(RFread).  But your middle expression is wrong: if T(RFread (the read of RD1)) > T(Sext) + T(mux) then T(RFread (the read of RD2)) + T(mux) > T(Sext) + T(mux) + T(mux) > T(Sext) + T(mux).  So you need to have T(mux) in the expression no matter which T(RFread) or T(Sext) is larger.

The basic rule (which you are mostly correctly following) is: use Max() for things that proceed in parallel, + for things that follow in sequence.  The mux comes after both the Sign extend and after the read of RD2.


Program synthesis, decidability and the halting problem

I think there may be a problem with the formulation of the problem.

Consider the set $S=\{M: M $ is a decider of its language $\}$.
The halting problem is decidable for this set (that is, if we are promised that the input is in this set). In fact, it is trivial (the machines in $S$ always halt).

Also, clearly every decidable language is in $S$.

EDIT: Based on the changes in the question - indeed, membership in $S$ would be undecidable: if $S$ contains a machine for each decidable language, then $S\neq \emptyset$. Thus, by Rice's theorem, if $S$ is decidable then $S$ contains every machine, but then the halting problem is undecidable on $S$.


Like transitive reduction, but removing vertices rather than edges?

There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex.  Here $O(n^\omega)$ is the running time for matrix multiplication.  See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038.  This may or may not be faster in practice.

To enumerate a list of all such triangles can take $\Theta(n^3)$ time in the worst case, for instance, in the case where you have a complete graph on $n$ vertices, as then you have $\Theta(n^3)$ triangles in the graph, so just outputting them takes $\Theta(n^3)$ time.


Longest path among subset of given points

This can be solved exactly with dynamic programming. The running time will be $O(n^2m)$.  It finds the exact optimal sequence, not just an approximation.

Let $A[t,u]$ denote the longest path $p_{s_1},\dots,p_{s_t}$ such that $s_t=u$.  In other words, it is the maximum possible value of $\|p_{s_1} - p_{s_2}\|_2 + \dots + \|p_{s_{t-1}} - p_{s_t}\|_2$ such that $1 \le s_1 < \cdots < s_t = u$.

Notice that we have a recursive equation that defines $A[\cdot,\cdot]$.  In particular,

$$A[t,u] = \max \{ A[t-1,v] + \|p_v - p_u\|_2 : 1 \le v < u\}.$$

Thus, we can fill in the values of $A[t,u]$ incrementally, in order of increasing value of $t$.  Each step requires $O(n)$ time, and there are $nm$ entries to fill in, so the total running time is $O(n^2m)$.

In practice the running time might often be something closer to $O(nm)$ if you terminate the search for $v$ early.  In the recurrence above you might often be able to prove that  if $v$ is much smaller than $u$ the maximum can't be achieved, so you could examine at values of $v$ in decreasing order and stop the iteration early once you know there is no improvement possible with a smaller value of $v$.


Can the Bell-LaPadula model emulate the Chinese Wall model?

first the Bell-LaPadula Model cannot capture changes over time. second, more serious problem arises when one considers that subjects in the Chinese Wall model may choose which CDs(company dataset) to access; in other words, initially a subject is free to access all objects. the Bell-LaPadula Model cannot emulate the Chinese Wall model.


Can we have a general function of any function this way?

The function you are describing is known as a universal Turing machine. A universal Turing machine is given a Turing machine $T$ and an input $x$, and outputs $T(x)$ (if $T$ doesn't halt, the universal Turing machine also doesn't halt).

If you want your function to have restricted complexity, you can just stop the computation once it has gone on for too long, and output zero, say. For any Turing machine with the correct complexity, the restricted universal Turing machine will still be correct. A variant is to accept a clocked Turing machine, which provides its own bound on the running time (which you can choose to ignore at your discretion).


How to convert pixel relative focal lengths to mm.

There is only one focal length, $F$. It is the distance between the focal point and the image plane.

The numbers you have, are actually not lengths. They are calculated by $f_x=F\cdot s_x $ and $f_y=F\cdot s_y $  where $s_x$ and $s_y$  are the size of your image in pixels. To get the focal length in mm as you want, simply divide $f_x$ with the width (in pixels) of your image.


It is possible to formalize Coq's logic within Coq but only subsets of the logic have been formalized yet. Relevant contributions are CoqInCoq, PTS, PTSATR, and PTSF.


The article Applying Sorting Networks to Synthesize Optimized Sorting Libraries by  Codish et al. experiments in this area, trying to take advantage of "instruction  level  parallelism  and  non-branching  conditional assignment instructions, both of which are common in modern CPU architectures", and create a quicksort implementation that falls back on sorting networks instead of falling back on insertion sort. In their tests, the result was faster than with the insertion sort fallback. That said, the paper only analyses how it performs with int, and has a dedicated "copy-and-swap" algorithm for int to order two integers without branches.

The hybrid sorting algorithm RADULS2 described in Even faster sorting of (not only) integers by Kokot et al. seems to use sorting networks too. The following note is rather interesting:

  Yet it is worth mentioning, that our implementation of sorting network for 16B records uses SSE to allow elements swapping by branchless code. Without such optimization [sorting networks] performed much worse as compilers tend to produce the code with branching instructions. The cost of swapping the elements is easy observable in case of 32B records—in such a situation [enumeration sort] clearly outperforms [sorting networks].

Access Aligned Sort uses bitonic sorting networks to improve a bottom-up mergesort and ends up with an algorithm that is faster that standard implementations of std::sort when sorting properly aligned float arrays. The algorithm uses [Boost.SIMD] to take advantage of SIMD instructions.

Finally, I've also experimented with sorting networks in a library of mine: I managed to obtain sorting algorithms which were faster than the usual insertion sort for small arrays of int, but I had to use the "copy-and-swap" trick described in Applying Sorting Networks to Synthesize Optimized Sorting Libraries to make them efficient, and I realized that it didn't really improve things for long or long long integers. The number of comparison tends to make the algorithm too slow compared to a simple insertion sort, which is adaptive. I tried to use them as a fallback algorithm for quicksort instead of insertion sort, but it didn't make an observable difference.

GPU sorting networks and hardware sorting networks would probably outperform most sorting algorithms, but I don't know much about those. Some guy implemented a few sorting networks with CUDA, you might want to take a look.

Conclusion: if you only need to sort small arrays, sorting networks are worth it, but they generally require implementers to carefully implement them if they want decent speed, and most of the time, unless you're sorting something else than raw collections of integers or floating point numbers, they aren't faster than usual sorting algorithms. When you use them as a fallback, it doesn't even always make a speed difference, so unless you really need that speed, they're not worth the implementation cost.


The major hypothesis of Rice theorem is that you are dealing with a set which is "extensional", or "semantically closed". Formally this requires that when the encoding of a TM $M$ belongs to the set, and $N$ is a TM equivalent to $M$, then the encoding of $N$ must also belong to the set.

Equivalence here means that the TMs $M,N$ terminate on the same inputs, with the same output (including acceptance).

Conditions like "halts in 50 steps" break equivalence, in general. I.e. it is possible that $M$ halts in 10 steps with output zero on every input, yet $N$ does the same after "wasting" 100 steps. So, Rice can not be applied to these.

  Questions like:- Turing machine makes at least five moves,It accepts a string input of length at least five ,TM halts for every input on length <50 are all decidable.

No. The property "at least five moves" is decidable. The properties "accepts a string of at least five" and "halts for every input of length <50" are NOT decidable. Indeed, these properties only care about the input/output behavior of the TM, hence if $M$ satisfies one of those, and $N$ is equivalent, then $N$ also satisfies the same property. So, Rice applies to those.


Regarding Turing Machine Halting Problem

The halting problem is the question of whether a program $B$ halts on and some given input $x$. It is impossible to create a program that decides the halting problem, so the effect is that, whatever program $A$ you create, there will exist some program $B$ and input $x$ such that $A$ will not tell correctly whether $B$ halts on input $x$.


Are there any problems in complexity class EXP that are not in NP?

First of all, we don't know whether $NP=EXP$ or not. So the initial answer is "it is an open question".

However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$).

Since you are looking into problems that cannot (to our knowlendge) be verified in polynomial time, you can start with any PSPACE complete problem. For example, TQBF, or $ALL_{NFA}$. If you want EXP-complete problems, there are examples here.


Checking if there is a single path that visits all nodes in a directed graph

The problem is how to deal with visited vertex.

If you keep following, the time complexity is not linear because of repeated visiting. Otherwise, your algorithm will fail in the following simple example:

1 --> 2 -----------> 3 --> 4
        \         /
         --> 5 -->

The first search find 1-2-3-4, then it goes back to 2 and find 1-2-5-3. Now because 3 is visited, the search stops, and thus finally fails.

A hint (or answer) to solve the problem: performing a topological ordering firstly.


If P is solvable in $O(n^7)$, that means that P is solvable in $C \cdot n^7$ time, for some constant $C>0$ and large enough $n$. Since $C \cdot n^7 < C \cdot n^9$ for large enough $n$, that implies that P is solvable in $O(n^9)$.

P is bounded by O($n^7$) in the worst case, but it does not imply that in the best case cannot run in constant time, for instance. Thus, P is not greater than $C \cdot n^7$ for large enough $n$, so it is not $\Omega(n^7)$.


Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results

I would say that luck and intuition are improved by experience :)

The trick is also to use inverse morphisms! They can perform nondeterministic letter substitutions.

A related example.
Consider the morphism $h: \{a,b\}^*\to \{0\}^*$  with $h(a) = h(b) = 0$, then $h^{-1}$ maps a word $0^n$ to any string $w\in\{a,b\}^*$ with length $n$.

Background. It is easy to write a FSA with output that maps strings $0^i10^j$ to strings $a^ib^j$, and regular languages are closed under finite state transductions (input-output transformation by two-tape finite state automaton). If you are not familiar with this result, by Nivat's Theorem: any finite state transduction can be written as a composition of an inverse morphism, intersection with regular language, and a morphism.


How to solve a Simple Linear Equation using a binary tree data structure

You don't really want to solve the equation using this representation. You want to convert it into a normal form such as $ax+b = 0$, from which you can read the solution. The first step would be to replace $P = Q$ with $P - Q = 0$. The second step would be to normalize $P - Q$ to some standard form, say a polynomial (or in you case, perhaps $ax+b$). One way to do this is to convert each subexpression into normal form recursively, using rules for handling leaves such as numerical constants and $x$, and mathematical operations such as $+,-,\times$.


generate possible inputs valid for automata

Just do a BFS from the start state, and at every node keep track of what transitions you took to get there. Obviously this will only generate a finite number of words, as it doesn't follow cycles.


For a given pair of points, suppose you know which sides of the square they touch, and they are not touching the same side (of course, there are only 12 possibilities for this); fix this information about what side each is on.  For example, with your example of points at $(0,0)$ and $(10,7)$, say that we've decided that $(0,0)$ will be on the left (west) side of the square and $(10,7)$ will be on the right (east) side of the square.

It is true that there there can be infinitely many possible squares that touch those points at the given sides, as you explain in the question.  However, you can always reduce this to looking at finitely many possibilities.  In particular, I think it suffices to consider at most $2n$ candidate squares, out of this infinite set: the $n$ candidates whose bottom (south) side is at $y$-value $y_1$, $y_2$, ..., or $y_n$, and the $n$ candidates whose top (north) side is at $y$-value $y_1$, $y_2$, ..., or $y_n$.  In other words, you can consider only cases where the lower-left corner is at one of the points

$$\{(0,y_i) : i \in \{1,\dots,n\} \wedge -3 \le y \le 0\} \cup \{(0,y_i-10) : i \in \{1,\dots,n\} \wedge -3 \le y \le 0\}.$$

Of course, any square that contains some other point in its interior can be immediately ruled out.

(I don't have a proof of this statement; this is just what my intuition suggests.)

I'm not quite sure what to do if both points are on the same side (e.g., they have the same $x$-value or the same $y$-value).  Perhaps we can use a similar argument to argue that there are at most $(2n)^2$ candidate squares that must be considered, but I'm not sure.

This immediately suggests an exponential-time algorithm.  At each step, you non-deterministically select a pair of points that aren't already covered by the existing set of rectangles.  Now you're going to enumerate all candidate squares that touch those two points and non-deterministically select one such square.  To help with this, enumerate all 12 or 16 possibilities for which side of the square each point is on, and non-deterministically select one.  Next consider the $\le 2n$ candidates suggested by these possibilities, and non-deterministically select one.  This gives you a square; add it to your collection, and go on to the next step.  You can resolve the non-determinism using backtracking.  This algorithm might work well enough to experiment with many collections of points and see if you can find a counterexample for your conjecture that it is always possible to find such a set of $n-1$ squares.


You are thinking in the right direction, and you almost got it right. What we need is a partial computable map $r : \mathbb{N} \to \mathbb{N}$ such that, for all $n \in \mathbb{N}$,
$$n \in \mathrm{HALTEMPTY}_{\mathrm{TM}} \iff r(n) \in \mathrm{HALT}_{\mathrm{TM}}.$$
Your instinct about having to do something with empty tapes is right, but you should follow the definitions. An element of $\mathrm{HALT}_{\mathrm{TM}}$ is a code $\langle M, w\rangle$, which means that rather than "deleteing the tape", you should provide a tape $w$. In this case, it should be the empty tape $w_\mathrm{empty}$. So we may define
$$r(M) = \langle M, w_\mathrm{empty} \rangle.$$
Reduction in the other direction is more complicated, you should try to do it yourself.


Are runtime bounds decidable for anything nontrivial?

Here are a few remarks which could be relevant:

Kobayashi proved that a TM running in time $o(n\log n)$ accepts a regular language (and so runs in time $O(n)$); recently this has been extended to non-deterministic TMs (Tadaki, Yamakami and Lin).
Machines running in time $o(n)$ actually run in constant time (consider any $n$ for which the running time is less than $n$; adding characters to the end doesn't affect the TM).


Your strategy is close, but probably needs some clarification. This is essentially equivalent to finding the longest path in DAGs, which can be done easily in a few ways easiest of which, similar to what you describe:

Negating edge weights and running a DAG-Shortest-Path algorithm.

In your case we could implement it similar to the following (transcribed mostly from CLRS 24.2) assuming input is an adjacency list:

0.  Max-Weight-Paths(Graph G(E, V)):
1.    add Super-Source S, and Super-Sink T // takes O(V + E)
2.    negate all edge weights              // takes O(V + E)
3.    topological sort G.V                 // takes O(V + E)
4.    for each vertex u in sorted order:
5.      for each vertex v in G.adj[u]:
6.        Relax(u, v)                      // 4-6 takes O(V + E)

Now for returning all max weight paths we can simply modify the relaxation step (6) a little bit. Instead of only containing a back pointer to one parent, we can maintain a linked list of back pointers to all parents of equal total distance like so:

0.  Relax(Vertex u, Vertex v):
1.    if distance(v) > distance(u) + w(u, v):
2.      distance(v) = distance(u) + w(u, v)
3.      parents(v) = {u}
4.    elif distance(v) == distance(u) + w(u, v):
5.      add u to parents(v)

Assuming parents(v) is maintained as a list, the Relax step still takes $O(1)$.

Then in the end you can return all max weight paths by starting at the sink T and traversing back up through parents(T) an so on. This traversal will return a DAG itself if multiple max weight paths exist. So just be smart about the traversal and the whole thing should take $O(V + E)$.

Edit, when I say be smart about the returning traversal, keep in mind a bad case scenario, something like this where all edge weights are equal:

There would technically be $6^2$ max weight paths, you could expand this example to get graphs with very large amounts of max weight paths due to combinatorics. So it might be more useful to return the DAG of max-weight paths rather than each individual. Although if you must return individual paths then you might be out of luck, because there are a lot of possibilities.


It just means "a system whose complexity is high enough to allow it to do [whatever thing we're talking about]."


Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there.


Predicting next action to take to reach a final state

You can represent the problem as a directed graph where the nodes are the states and the edges are the action that signifies the transition from one state to another if the action is performed. Once this is done you can use various graph path finding algorithms to find the sequence of actions to reach a specific state from a starting state.


Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

The first step is finding a simpler description of the language generated by the grammar $S \to aSbS \mid \epsilon$.
The second step is deducing a description of the complement, which is the language you're actually interested in.
Finally, in order to show that the language is context-free, you can consult our reference question on this topic.


How to prove that this defined language is regular?

Try proving it for $\alpha = 1/2$ first.  Construct a non-deterministic automaton that recognizes $L_\alpha$.  Before you start reading in the string $w$, guess something about where you will be in the future.  What would you like to guess?  What would help you?


How does "δ:Q×Σ→Q" read in the definition of a DFA (deterministic finite acceptor)?

$\delta$ is a function which takes a current state and a letter from the alphabet as arguments and produces next state.

It might be easier to understand when you realize that it is just a function that takes a pair, for instance $(q_0, a)$ where $q_0 \in Q$ is a state and $a \in \Sigma$ is a letter in the alphabet, and $\delta(q_0, a) = q_1$ means that if in state $q_0$ you read an 'a', proceed to state $q_1$.

It is the definition of a transition function which is used for example in Turing machines.

$\times$ means Cartesian product and $\to$ means "produces" or "maps to".


Why would you use a monitor instead of a semaphore?

They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" keyword). However the semaphore is considered a "lower level" entity than the monitor for the following reasons & differences:

Both Monitors and Semaphores are used for the same purpose – thread synchronization. But, monitors are simpler to use than semaphores because they handle all of the details of lock acquisition and release. An application using semaphores has to release any locks a thread has acquired when the application terminates – this must be done by the application itself. If the application does not do this, then any other thread that needs the shared resource will not be able to proceed.
Another difference when using semaphores is that every routine accessing a shared resource has to explicitly acquire a a lock before using the resource. This can be easily forgotten when coding the routines dealing with multithreading . Monitors, unlike semaphores, automatically acquire the necessary locks.[1]

See also the highly voted Stack Overflow answer Semaphore vs. Monitors - what's the difference? with a great/ memorable analogy to public toilets & bike stands.


There are many hash functions for hashing a string; a web search should turn up a bunch.  You can use any one you like.  The fact that you are using double hashing doesn't impose any additional requirements on the hash function.  Yes, that would be a reasonable hash (and you could use two different int arrays for the two different hash functions); there are many other choices that would be reasonable as well.


Here's another, elementary proof technique that does not use Rice's theorem which is way overkill for this simple problem.

We have Turing machine family $F(A)$ that goes into an infinite loop for any input except 2, in which case it will run program $A$, which can be arbitrary.

Now if we could decide your original problem we could decide for arbitrary inputless Turing machines whether they halt using $F$. But this is obviously undecidable and therefore your original problem is as well.


Testing whether the language of one automaton is a subset of another

Recall some closure properties of regular languages, namely that they are closed under complementation and intersection. Now, $L(A)\subseteq L(B)$ whenever $L(A)\cap\overline{L(B)}$ is empty. So you need to construct the automaton that accepts the intersection of $A$ and the complement of $B$ – these are standard constructions – and test whether the resulting automaton accepts the empty language. This can be checked by inspecting the automaton to see whether any accepting states are reachable from the initial state. If not, then the language accepted is empty.


PSPACE languages reducible to other PSPACE languages in polynomial space

The same way that you show that any problem in P is polytime reducible to any other, or that any decidable language is Turing reducible to any other: solve the problem in the reduction.

Note that the claims (yours in the question and mine above) aren't quite true for many-one reductions, since you can't reduce any other language to $\Sigma^*$ or $\emptyset$ using many-one reductions.


How to verify Hamilton-Path in log-space?

You can check all vertices in order.

Suppose we are given vertices $v_1, v_2, \cdots, v_n$ and a path $p=(p_1,p_2, \cdots,p_m)$.Check if $m==n$. If not, reject. Otherwise, check if $v_1$ appears in $p$. If not, reject.  Otherwise, check if $v_2$ appears in $p$. If not reject. And so on. Finally check if $v_m$ appears in $p$. If not, reject. Otherwise, accept.


The inefficiency in compiler would make the next compiler work slower, but the result of work will be the same.
So in next compiler you wouldn't even know about that inefficiency.


If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm?

A language $A$ is polynomial time reducible to a language $B$ if there is a polynomial time function $f$ such that $x \in A$ iff $f(x) \in B$. In particular, if $B$ can be solvable in polynomial time, then so can $A$.

There are other notions of reducibility in complexity theory, some stronger than this and some weaker. A weaker notion is polynomial time oracle reducibility: $A$ is polynomial time oracle-reducible to $B$ if $A$ can be solved in polynomial time given oracle access to $B$ (this can be defined formally). Stronger notions put more constraints on $f$, such as being computable in logarithmic space.

Weaker notions of reducibility could seem more natural: if $A$ is polynomial time oracle-reducible to $B$ and $B$ can be solved in polynomial time, then so can $A$. Why would we want to put more constraints on our reduction? For example, assuming $\mathsf {NP} \neq \mathsf {coNP}$ (which is a common assumption), an NP-complete cannot be polynomially reduced to its complement. For example, SAT, the language consisting of all satisfiable CNFs, isn't reducible to coSAT, the language consisting of all unsatisfiable CNFs. Intuitively, this seems ludicrous, since if you could find out whether a CNF is unsatisfiable, surely you could find out whether a CNF is satisfiable!

Indeed, Cook first defined NP-hard problems using oracle reduciblity rather than the modern many-one reducibility (described in the first paragraph of this answer). The problem with oracle reducibility is that it is hard to reason about, whereas many-one reducibility leads to a richer complexity theory. Also, the polynomial hieerarchy, which mirrors the classical arithmetical hierarchy from recursion theory, only makes sense using many-one reducibility. Perhaps in the future you will be able to formulate your own opinion on this matter.

When studying the internal structure of $\mathsf P$, we must use stronger notions, since all non-trivial problems in $\mathsf P$ are polynomially reducible to each other (the only exceptions are $\emptyset$ and $\Sigma^*$). The most common notions are logspace reducibility, in which $f$ has to be computable in logarithmic space, and the even stronger AC0 reducibility (also known as first-order reducibility), in which $f$ has to be computable by uniform polynomial size circuits having constant depth.


Operating System code suffers more cache misses than user code

There's cache misses when you access a page for the first time, then you get hits. Since the kernel initialises the page, it gets all the cache misses. Then it passes the page to the user code, which gets cache hits.

The same misses would happen in user code if the kernel didn't initialise the page.


A set such as $\{1,2,3\}$ is valid input to the problem you defined, so yes, it is "allowed". When setting such constraints, you typically want to know "does the problem still remain NP-complete?". In this sense, notice there is a difference between "can my input take form such as this" and "if my input always takes this form, is the problem still NP-complete?"

I believe you are after the latter; if you impose some constraints on the input, does the problem remain NP-complete? For example, if your input is the set $\{1,\ldots,n\}$ for some positive integer $n$, the answer is no, the problem can easily be decided in polynomial time (can you see why?)


Published or widely known failures of Page Rank algorithm

yes this "problem" is quite well studied and google itself is researching ways to improve it. its called the word sense disambiguation problem and is under active/ongoing research, as its becoming a competitive feature between different search engines. quite simply, the same word has different meanings depending on context.

as for your more general question about "widely known failures of page rank", it is long known that it cannot necessarily distinguish spam web pages designed to fool it, and a related technique called a link farm with many external pages pointing to one site. in this sense google search is employing somewhat similar aims/techniques to spam-detecting algorithms employed largely/widely by mail providers.

google has proprietary/closely guarded techniques to detect/filter spam and these are a large part of the continually refining versions released. then advertisers attempt to respond with new techniques. this back-and-forth evolutionary dance/ "arms race" is also known as search engine optimization from the advertisers pov, but the term also somewhat applies to googles process of improvement! (SEO is a very large field with strong overlap with marketing and probably worldwide worth in the billions of dollars.)

somewhat similar, so-called "google bombing" where people create a mass movement to use words together to affect search engine results. it is somewhat subjective whether to call this a "failure" of the search engine or actually a "feature" (as from the perspective of those exploiting it, because in a way search engines actually by design measure meme prevalence in cyberspace!).

one method of dealing with word disambiguation is actually looking at trends in users personal search engine behaviors. in this way person A typing in a query will get different results than person B depending on their search histories.[1]

a related field called Latent semantic analysis helps with this somewhat by representing documents as sets-of-words with weights associated with each word, and the same word may have different weights in different documents or depending on document similarity measured by the vector cosine similarity technique.

an example paper from this field is K&M ref below. it actually uses & builds on results of existing google searches for word disambiguation.

yet another known issue is called "topic drift" where basically, if you search on two terms $x$ and $y$, if $y$ is more common it will tend to dominate and more results will be related to $y$ and "drown out" results with both $x$ and $y$. see eg [2]

Google, Bing Battle for Better Disambiguation, AI eweek
Google & WordNet based Word Sense Disambiguation Klapaftis, Manandhar
[1] Google Now Personalizes Everyone’s Search Results searchengineland
[2] hits/pagerank & topic drift tcs.se


What are applications of Coin Change problem?

This is going to sound very silly but, I once had to implement the coin change solution for the purpose of... distributing change!

The application was a soda pop vending machine that could accept bills and coins and dispense coins.

The spec required the use of a least coin pay, plus an alternative algorithm should one of the coin tubes be empty and thus unable to dispense coins of that denomination.

The classic example was buying a 60 cent soda pop with a dollar (I know, pop was cheap back then ;-). This leaves 40 cents change, or in the US, 1 quarter, 1 dime, and 1 nickel for least coin pay. If the nickel tube were empty though, the machine would dispense 4 dimes.

I know to is not quite the lofty heights of academia, but it was an actual application of the problem's solution. On a further note, more modern coin changer mechanisms implement their own coin management so for those more capable peripherals, we would just let the coin mech figure out if change could be made.

If not, the customer would get the dreaded NO CHANGE error message and the money would be returned.


How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$?

A simple solution is to use a $n$-bit bitvector.  This is basically an array with $n$ entries, where each entry is either 0 or 1.  If the $i$th entry is 1, that means that $i$ was stored in the data structure; 0 means that $i$ was not stored in the data structure.  This takes $O(n)$ bits of space.  The insert and access operations can be done in $O(1)$ time.

The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once.  If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.


A nonterminal $X$ is nullable if there is some derivation $X \to^* \epsilon$. It is clear that all non-terminals found by your algorithm are nullable (you can prove this by induction). On the other hand, if $X$ is nullable then take a derivation tree for the derivation, and prove by induction on the depth that all non-terminals on the way are recognized as nullable by this algorithm. This is why the algorithm is correct.

In your first example, $B$ is not nullable. In fact, you can't generate any string from $B$. The same is the case for your second example $S\to S$, where again the grammar generates no strings.


What's the meaning of the $\top$ symbol in a Hoare triple?

The symbol $\top$, known as top, stands for "True". There is also a symbol $\bot$, known as bottom, which stands for "False". Top is always true, and bottom is always false. In your case, having a precondition that always holds is the same as having no precondition.


Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing.  For instance, it has been used for image segmentation, image stitching, seam carving, image denoising, stereo image correspondence, and more.

See, e.g., https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision, What's the relationship of max-flow-min-cut and Markov Random Fields?, https://cs.stackexchange.com/a/37423/755, https://en.wikipedia.org/wiki/Image_segmentation#Graph_partitioning_methods


Clarification on NP-hardness and hardness of approximation results for set cover?

When you have a result like "It is NP-hard to approximate X within ..." or say "X is NP-complete", it means that there is an infinite family of instances of X that are hard. This is what worst case intractability means.

In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.

At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.


Are the sets of all finite automata and pushdown automata countable?

The set of all finite automata is indeed countable, but that has nothing to do with the set of all TMs being countable. The two models are only related by the set of languages they accept, but both have infinitely many machines per language so we can't immediately conclude anything about the sets of machines.

You can prove countability with the usual means: working from the formal definition of FAs (something like $A = (Q, \Sigma, \delta, Q_F)$), construct an injection into $\mathbb{N}$. That's tedious, but elementary. For PDAs, it works just in the same way.


Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$


A way to convert a binary tree into a grid

A vertex in the grid has $O(d)$ vertices at distance $d$ from it. In contrast, the complete binary tree of height $h$ as $2^h$ vertices at distance $h$ from the root. Therefore there is no isometric embedding of arbitrary binary trees in the grid. Similar considerations show that there is also no embedding of bounded distortion (in which distances increase by at most a constant factor).


Is it possible to prove EQTM is undecidable by the Rice theorem?

You can reduce it to a problem about single Turing machines by fixing one of the inputs. For example, you can take $M_2$ to be some Turing machine which accepts nothing. This shows that $EQ_{TM}$ is at least as hard as deciding emptiness.

Another approach is to encapsulate the pair of Turing machines $M_1,M_2$ in one Turing machine $M$, which upon input $0x$ will simulate $M_1$ on $x$, and upon input $1x$ will simulate $M_2$ on $x$ (on the empty input it can arbitrarily halt). There is a simple reduction showing that $EQ_{TM}$ is equivalent to the corresponding problem for $M$, and then you can apply Rice's theorem.


A "half adder" only does half the job: It adds two inputs x and y.

A "full adder" does the full job: Most of the time, you need to process two inputs, plus a carry from another (half or full adder). A "full adder" adds three inputs x, y and z.


Can two minimum spanning trees for a same graph has different number edges?

The answer is no. When running an algorithm for finding MST, It is first of all a tree, it has |v| - 1 edges $exactly$.

If there are more than |v| - 1 edges, than there're two vertices that their path isn't simple, which is simply shown with induction. Meaning if there's a path from s to t with more than |v| - 1 edges, one of the vertices will be repeated.


Interpreting probabilistic time turning machines

As the notation implies, the probability is taken over the choice of $r$. So it's the fraction of $r$s which the machine $A$ "accepts" (answer Yes). You're right that the random variable $A(r)$ has two possible values, Yes and No, and so for example the probability to get Yes and the probability to get No add up to $1$.

We usually think of $A$ as a statistical test. For example, $A$ might test the the number of $1$s in $r$ is roughly $\ell/2$, say between $\ell/2-\sqrt{\ell\log \ell}$ and $\ell/2+\sqrt{\ell\log \ell}$, and then it accepts with probability $1-2/\ell^2$ or higher (using Chernoff's inequality).

Something you are confused about is the branching. The machine $A$ can read its input bits many times. There is always one computation branch. After $\ell$ steps, there is still only one computation branch. On the other hand, at the outset there are $2^\ell$ different computations to consider.


Given a Turing Machine M, are there infinitely many Turing machines that recognize L(M)?

Your attempt is fine. Yes, a Turing machine can only have a finite number of states, but you can add $i$ unreachable states for any natural number $i$ and there are infinitely many natural numbers, even though each one of them is finite.


Practical Applications of regular grammars

Regular grammars are more-or-less the same as NFAs, so you might as well ask what applications these have. Finite automata are used in compilers, for performing lexical analysis. Any course on compilation will contain ample information on this.

As for the weaknesses of regular grammars, they only describe regular languages. In particular, they're not enough to parse programming languages, even superficially. We use context-free grammars for that. Any course on formal languages and automata will explain all of that very clearly.


Why decision tree method for lower bound on finding a minimum doesn't work

In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which then implies the bound that you got on the height of the tree. This is Lemma 2 in the linked document. They call this an information theoretic argument.
The reason why it gives such a conservative lower bound for the height of the trees, is that the bound on the number of leaves is too conservative. So, Lemma 1's fault of not being strong enough.

I was curious to see if this method could give a better lower bound if one manages to bound better the number of leaves. For this what we need to do is to have some control on the number of times an outcome of the algorithm is repeated across the leaves.
Suppose a comparison-based algorithm for minimum has decision tree with a maximum of $K$ leaves corresponding to the same outcome.
Then the tree has at most $Kn$ leaves and at most height $\log(n)+\log(K)$. If $n>2(\log(n)+\log(K))$, then none of the paths from root to leaf compares all elements of the array. Since the height of the path is bounded by $\log(n)+\log(K)$, then there are at most that many comparisons in the path. Each comparison looks at $2$ elements, so at most $2(\log(n)+\log(K))$ are inspected. Then we can keep the elements compared in one of the paths fixed and make the other elements smaller than the element that that path chooses as minimum. This input would result on the same output from the algorithm but have a different minimum. So, the algorithm must be incorrect. So, the inequality above must be false. This argument has the flavor of the adversary argument, which applied directly gives the best lower bound for this problem.
Hence $n\leq 2(\log(n)+\log(K))$. From this we get that $\log(K)\geq n/2-\log(n)$, or in other words
$$K\geq 2^{n/2-\log(n)}$$
Now, this tells us that the decision trees for these algorithms will always have at least $K+(n-1)\geq 2^{n/2-\log(n)}+(n-1)$ leaves. So, their height is at least
$$\log\left(2^{n/2-\log(n)}+(n-1)\right)\geq n/2-\log(n)$$


Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?

For every Turing machine over some language L, there is a set of words that it will halt and accept on and a set of words it will halt and reject on, if it does halt.

If $|L| = 1 $ then the Turing machine will accept on exactly one input.

Given an arbitrary M and some input, we cannot decide whether the program will halt; halting problem. However, since M is not arbitrary, it’s fixed,this is not the Halting problem. I believe an algorithm would only need to check if the input is equal to the first element in L.


As others have said, this is very opinion based. What's the difference between "cool" and "beautiful"? I find the Curry-Howard isomorphism beautiful, you don't. Neither of us is wrong.
Ultimately, Computer Science is a science of compromise. Mathematics is concerned with what "is": logical facts, pure truth and knowledge. Computer Science is concerned with what can be computed, and thanks to undecidability, that's really not that much.
There are uncountably many undecidable sets, but only countably many decidable ones.
So the mathematicians get to write beautiful pictures and draw beautiful diagrams about what is, in the abstract. And the computer scientists get to find the heuristics, the edge cases, the conservative approximations, and the impossibility results. In some sense, ours is a science of ugliness.
That said, everyone will find something beautiful in their field. In mine (Programming Languages), there's a whole category of paper called "Pearl" papers, where the design of something complex is made particularly simple or elegant by the programming language or technique used to create it. If you google "ICFP Functional Pearl" or "JFP Functional Pearl" you'll find a ton.


Does PDA epsilon transition only transition when there's no more input?

A PDA is always allowed to take $\epsilon$ transitions, just like an NFA. More generally, the PDA is not allowed to peek at anything beyond the current letter. It cannot tell whether it has finished reading the word or not. Whether it can take a transition or not depends only on the contents of the stack and, in the case of a transition "swallowing" an input symbol, on the next symbol in the input (if any).


How can a Turing Machine recognize a regular language?

Hint: A DFA consists of 5 parts: state-set, alphabet, initial-state, final-state-set and transition-function. What does a Turing Machine consist of, and which would correspond to each part of a DFA?


Find X contiguous segments in a range of integers

Here's a quick piece of pseudo-code off the top of my head.

Given maximum value m and number of non-empty segments n, do so:

  Call Helper(Empty List [passed by reference], Empty List [copied before passing or passed by copy], 0, m, n)

The helper function takes as input:

a reference to the output list of lists,
a list of segments to append more segments to
the lower bound or starting value
the upper bound or stopping value
the number of segments

function Helper(L, S, l, u, n):
  If n = 1 then append to L the list S.append(l, u)
  Else:
    For each t from l+1 up to u-n *inclusive*:
      Make a copy of S into S'
      Append to S' the pair (s, t)
      Call Helper(L, S', t+1, u, n-1)

As you can see, the only "trick" was perhaps just figuring that out you should use a helper function with more arguments to aid the recursion. Of course, different solutions may be possible.

A note here. It should be possible to change the implementation above slightly (e.g., using return values as opposed to passing L by reference) that one can memoize the result of each call for a given triple (l, u, n). Such a DP approach seems to me like it may make the program be significantly faster on large input. I assume this sort of problem has much sharing to be exploited using a DP approach.


Does there exist any unrelativized separation between a quantum complexity class and a classical one?

Separations are known for constant-depth circuits. One recent result in this area is due to Bravyi, Gosset, and Koenig (see also the journal version in Science). Recent independent works by Bene Watts, Kothari, Schaeffer, and Tal, Coudron, Stark and Vidick, and Le Gall strengthened the hardness result for classical circuits from worst-case hardness to average-case hardness.


Can one count the number of n points in m triangles in less than O(nm)?

Pragmatic solution that's easy to implement

If you care more about a pragmatic solution that will likely work well enough in practice in most cases, and is easy to code, I would suggest storing each point in a quadtree.  Then, for each triangle $T$, recursively search the quadtree to find all points within the triangle $T$.  (This recursive search is pretty easy; at a node that represents a split of the space, check whether the triangle intersects the rectangular regions corresponding to the node's two children, and recurse on whichever node(s) it intersects.)

I don't know of any reason to think that the worst-case asymptotic running time will be better $O(nm)$ (e.g., it might perform poorly if you have many long, skinny, diagonal triangles), but it might work well in practice in many cases.

Sweepline algorithm

Alternatively, you could use a sweepline algorithm, similar to the Bentley-Ottman algorithm for detecting intersections among line segments.  Unfortunately, it seems it might take quadratic time in the worst case.

Each triangle is defined by three line segments, so build the Bentley-Ottman data structures from these line segments.  Also, you'll have an interval tree; for each triangle, it stores the interval of $y$-values that are obtained by intersecting that triangle with the current sweepline.  Each point and each vertex of any triangle triggers an event when the sweepline hits that point or vertex.  When you hit a point $p$, you can quickly count the number of triangles it is contained in: check the interval tree to see how many intervals in the tree contain it.

Each operation can be done in $O(\log(n+m))$ time.  Unfortunately, there could be as many as $O(n+m^2)$ events (since there can be $O(m^2)$ intersections among the line segments), so in the worst case the total running time could be as bad as $O((n+m^2)\log(n+m))$.  If you care only about typical running time, this might often do a lot better than that, as the number of intersections among the triangles might often be as little as $O(m)$, which would lead to a $O((n+m)\log(n+m))$ running time; but that's not guaranteed, and there exist inputs where it is much slower.


Calculate Miss rate of L2 cache given global and L1 miss rates

You would only access the next level cache, only if its misses on the current one. Therefore the global miss rate is equal to multiplication of all the local miss rates.

0.0541    = L2 misses * 0.0913
L2 misses = 0.0541/0.0913 = 0.5926
L2 miss rate = 59.26%

In your answer you got the % in the wrong place.


Given any language $L$ there is a special Turing machine $T$ that decides $L$ in polynomial time.

The Turing machine has 3 states: the initial states $q_0$, the accepting state $q_A$ and the rejecting state $q_R$.
Let $\Gamma$ be the tape alphabet (including the blank symbol $\varepsilon$), and let $\alpha x$ denote the contents of the tape starting from the left edge to the head position in tape, where $\alpha \in \Gamma^*$ and $x \in \Gamma$. As usual, I am going to assume that the input is written starting from the beginning of the tape and that the head is initially positioned at the beginning of the tape.
The transition function $\delta$ is defined as follows:

$\delta(q_0, \alpha x) = (q_0, x, R)$ if $x \neq \varepsilon$
$\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \in L$
$\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \not\in L$

Since there are undecidable languages for regular Turing Machines, this immediately implies that A and B are false.

Answers D and C are unclear. They talk about "both answers" but you are given $4$ possible answers.


Why doesn't A* give the optimal path for navigating from A to R in this state space?

For A* to be optimal, the heuristic needs to be admissible (and this example shows why). This heuristic is not admissible because the heuristic value at M is 40, while the shortest path from M to R has length 30.


Can this DFA be converted to a regular expression?

Every DFA can be converted to a regular expression, so you must have made a mistake when you converted. The conversion is quite fiddly, so making a mistake with a nine-state automaton is easy to do, unfortunately.

It might help if you split the automaton in two: if the automaton accepts, it either reads an $a$ and then accepts using only states $2,4,6,\omega$ or it reads a $b$ and then accepts using only states $3,5,7,\omega$. So the regular expression must be something of the form $aR_{\{2,4,6,\omega\}}+bR_{\{3,5,7,\omega\}}$, where $R_S$ is the regular expression for the automaton that just has the states in $S$. Now, you just have to convert two nearly identical four-state automata, which should be easier to do correctly.


Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$

In the following grammar the first block of productions ensures that the right amount of $a,b,c$, and $d$ is generated, in some order. The terminal  $a$ is represented by the nonterminal $A$, $b$ by $B$, etc.
They also ensure that $X$, which represents a $a$, is at the end of the sentential form.

The next block ensures that $A,B,C,D$ can be reordered.

The last block ensures that terminals are generated from right to left in the correct order (first $d$, then $c$, then $b$, and finally $a$).

$$
\begin{align*}
S  &\to ABBCCCDS'X \\
S' &\to AABBCCCDS' \mid BDDD\\
\\
BA & \to AB \\
CA & \to AC \\
CB & \to BC \\
DA & \to AD \\
DB & \to BD \\
DC & \to CD \\
\\
DX &\to Xd \\
X &\to Y \\
CY &\to Yc \\
Y &\to W \\
BW &\to Wb \\
W &\to Z \\
AZ &\to Za \\
Z & \to a
\end{align*}
$$


Finding a subarray of time series data in which all values are less than X for specified time Y?

You don't need a clever or sophisticated algorithm.  It suffices to linearly scan through the time series, in chronological order, and keep track of the length of window of values less than $X$.

At time $t$, remember the length of the longest window ending at time $t$ such that all values in the window are less than $X$.  At time $t+1$, when you see the next value, update this length (it either increases by 1, if the new value is less than $X$, or resets to 0, if the new value is at least $X$).  Keep track of the longest such window that you saw during the entire scan.  If it is longer than $Y$, output it.

This requires very little memory (only an integer to keep track of the length of the window of consecutive values $< X$, and an integer to keep track of the current position in the array).  The algorithm should be extremely fast.


Either find a perfect matching, or return a witness that none exist

I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:

either X has at least |X| neighboors in V => then you move your assignements to add properly x.
either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).

For your problem, there is no weight. So if you are in the second case, just break off and you have your X subset. Else you will reach the last x of U and have a perfect assignement.


Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?

Your problem is the same as interval graph coloring.

There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.


You haven’t specified the order of entries in your vector. In general, the $i$’th entry is obtained with probability $|x_i|^2$.

Let’s consider two examples. In the first, the order of entries is $|00\rangle, |01\rangle, |10\rangle, |11\rangle$. The two final entries will be obtained with probability $1/2$ each, and so the first qubit will be measured as $|1\rangle$. If you measure only the first qubit, then you will still always get $|1\rangle$, and the other qubit will remain in the superposition $\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)$.

If the order of entries is instead $|00\rangle, |10\rangle, |01\rangle, |11\rangle$, then once again the two final entries will be obtained with probability $1/2$ each. This means that the first qubit will be measured as $|0\rangle$ or $|1\rangle$ with equal probability.