How many number of different binary trees are possible for a given postorder (or preorder) traversal

Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan number $C_n = \frac 1{n+1}{2n \choose n}$. Sequence A000108 in Sloane's OIES.

It has a nice recurrence, based on the fact that a tree with $n+1$ nodes has a root and the remaining nodes are distributed into two subtrees with $i$ and $n-i$ nodes respectively: $C_{n+1}=\sum_{i=0}^n C_i\,C_{n-i} $. Such a type of recurrence is called a convolution.

In fact, you have discovered this recurrence yourself! Here are your own numbers, in a slightly changed order:

$1:4:0=14 = 14 \cdot 1$

$1:3:1=5 = 5 \cdot 1$

$1:2:2=4 = 2 \cdot 2$

$1:1:3=5 = 1 \cdot 5$

$1:0:4=14 = 1 \cdot 14$


Informally speaking the two x's are indeed different variables (technically speaking, they are the same variables but bound by different abstractors).

As for your two inquiries regarding equivalences: in the strictest sense possible, they are not syntactically equivalent ($M \not\equiv N$). However, they are what is called equivalent modulo alpha ($M \equiv_\alpha N$). This basically means that one can be transformed into the other through $\alpha$-conversion (which leaves the behaviour of the term unchanged). The result is that the names of bound variables become arbitrary - as they should be.

Note that most equivalences in lambda calculus are stated modulo $\alpha$, and most lambda logicians seem to regard the formulation and application of the rule as a tedious formality. Once they have specified the $\alpha$-rule (if they even care to do so in the first place), they tend to adopt the following convention: 'from now on, when we say $M$ and $N$ are equivalent ($M \equiv N$), we just mean that they are equivalent modulo alpha ($M \equiv_\alpha N$), unless stated otherwise'. So in most contexts, you can simply say they are 'the same', but I think you should be aware of the details behind it.
Yes. If $y$ were to be substituted for some $z$ in that term, then all occurrences of $y$ will be replaced by $z$.

This is perhaps a useful free resource that covers some of the basics a little more rigorously: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf.


The class $E^E$ contains 2E, which is the class of problems solvable in iterated exponential time. The reason is that the E oracle can be applied on a padded input of exponential size. The time hierarchy theorem separates 2E from EXP.


Isn't software needed from programs to run?

Languages like C and C++ can be compiled to include all libraries they use statically (as part of the executable). This means that the executable will be able to run by itself. Of course, even in this case the executable is supported by the operating system, but this is "for free".

You are right that practical applications normally use dynamically linked libraries and even external data files, but programs arising in programming competitions are usually more low-key and can stand on their own.

The judges have a very practical reason in requiring that the executable be self-sufficient, namely it makes it much easier for them to run it. Java environments are not standard, take up a lot of space, and are time-consuming to install. In principle (and perhaps in practice) you could compile your Java code to Java bytecode and thence to an actual executable, and if you link the appropriate runtime libraries statically, you would get a standalone executable.


Approximation ratio when optimal solution is $0$

That's right.  Such a problem is not approximable to within any constant factor large than 1 (unless P=NP).

Is there a way around this?  Yes, there are several possibilities:

Use a different measure of approximation, rather than multiplicative factor.  For instance, you could consider its additive approximability.
Re-define the problem so it cannot have output of 0.  For instance, let $Pc(G)=Pb(G)+1$, i.e., $Pc$ is the problem of computing the minimum number of edges to remove from a graph so it becomes 3-colorable, plus one.  Then there is no such barrier to achieving some constant approximation factor. (There might still be other barriers, of course.)  Suppose you found that $Pc$ has a 2-approximation.  Then you could unfold what that implies for $Pb$.


Find the number of topological sorts in a tree

A clue then.

It seems you have to multiply with a multinomial coefficient in each step. Here the size of the subtree comes in handy.

Explanation: if children have certain topsorts, then these sequences may be shuffled in the topsort for the parent. We 'color' the positions where the various topsorts for the respective children are placed, and at each color we write one of the possible topsorts for that child.

Since the formula is used now in another problem, here it is explicitly.
Assume the tree  $t$ has $n+1$ nodes, and the subtrees $t_1, \dots, t_r$ of the children have $k_1, \dots, k_r$ nodes respectively (so $n=k_1+\dots+k_r$). Let $\operatorname{NoS}(t)$ be the number of topsorts of tree $t$. Then

$$\operatorname{NoS}(t) = {n \choose k_1, k_2, \dots, k_r}\prod_{i=1}^n \operatorname{NoS}(t_i) $$


Algorithm for minimizing the number of "inversions" in a graph

You can reduce MAX-2-SAT to your problem. Therefore, your problem is NP-complete.

In MAX-2-SAT we have $n$ boolean variables $x_1, \dots, x_n$ and $m$ clauses of the form $a\vee b$ where $a$ and $b$ are $x_i$ or $\bar{x_i}$ (its complement). The goal is to assign $0$, and $1$ values to $x_i$'s such that the number of true clauses is maximized. This problem is NP-complete. For an arbitrary instance of MAX-2-SAT, we build an instance of your problems as follows. Hence, your problem is also NP-complete, i.e., kind of no chance for a polynomial-time algorithm for all cases.

We put $n+m$ pair of nodes ($x_i$ and $\bar{x_i}$ for $1\leq i\leq n$, and $y_k$ and $\bar{y_k}$ for $1\leq k\leq m$) on the right side and $3m$ node on the left (three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ for $k$'th clause where $1\leq k\leq m$).
Let $(x_i\vee x_j)$ be the $k$'th clause in our instance (other cases are similar). We put three nodes $v_{k,1}, v_{k,2}, v_{k,3}$ in the left side of our graph. We then connect

$v_{k,1}$ to $x_i$ and $x_j$,
$v_{k,2}$ to $x_i$, $\bar{x_j}$, and $y_k$,
$v_{k,3}$ to $\bar{x_i}$, $x_j$, and $y_k$.

At most one of the $v_{k,1}, v_{k,2}, v_{k,3}$ can gets a green color. Moreover, this happens if and only if the clause gets a true value. Therefore, the maximum number of green nodes in the instance of your problem is equal to the solution to MAX-2-SAT.

Your bonus problem is harder than the original version and is also NP-complete.


One powerful and general approach is to write a probabilistic model that describes how colors are chosen, then apply maximum-likelihood estimation.  The probabilistic model provides an expression for $p(x)$, where $x=(x_1,\dots,x_n)$ and $x_i$ is a random variable that describes the color of the $i$th object.  You are given an observation for some of the $x_i$'s, namely, the color of the pre-classified objects, and want to infer the color of the rest.  This can be done by finding a vector $x$ that maximizes the value of $p(x)$, subject to the requirement that it be consistent with the observed colors.  You then apply some mathematical optimization routine to find $x$ that maximizes $p(x)$, subject to the constraint that $x$ is consistent with the observations.

This requires that you supply a model for how colors are generated.  Only you can provide that, since that depends on the specifics of your application domain and the random process underlying your observations.

One possible approach is to model this as a Markov random field.   Build an undirected graph where the vertices are the objects; add an edge $(u,v)$ between two objects $u$ and $v$ if $u,v$ are in the same cluster.  Then the Markov random field assumption says that $p(x)$ is proportional to

$$\prod_{(u,v) \in E} q(x_u,x_v),$$

where $q(\cdot,\cdot)$ is some function $q:\{\text{red},\text{green}\}^2 \to [0,1]$.  For instance, you might take $q(c,d) = 0.99$ if $c=d$ and $q(c,d)=0.01$ if $c\ne d$.  That defines a Markov random field.  There are algorithms for maximum-likelihood inference for Markov random fields.  (In particular, as a starting optimization, you can decompose the graph into connected components and solve the problem separately for each connected component.)

Another possible model would be a hierarchical model, where we first pick a color at random for each cluster, then randomly pick a color for each object based on the color(s) of the cluster(s) it is contained in.  Suppose there are $m$ clusters, and let $w=(w_1,\dots,w_n)$ where $w_i$ is a random variable describing the color of the $i$th cluster.  We might imagine that the $w_i$ are independently uniformly distributed.  Then, we might imagine that we pick a color $x_j$ for object $j$ based on the values of $w_i$ for each cluster $i$ that contains object $j$.  In particular, we might imagine that the conditional probability distribution $p(x|w)$ is proportional to

$$\prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i),$$

where we define $p(x_j|w_i) = 0.99$ for $x_j=w_i$ and $p(x_j|w_i)=0.01$ if $x_j \ne w_i$ (say).  Using the fact that $p(x,w)=p(x|w) \cdot p(w)$ and that $w$ is iid uniform, we obtain that $p(x,w)$ is proportional to

$$2^{-m} \prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i).$$

We can then try to find $x,w$ that maximizes $p(x,w)$, subject to the constraint that $x$ be compatible with the observations (the pre-classified objects).  This could be done by mathematical optimization.  Again, as an optimization, you can decompose the problem into independent subproblems through a connected component decomposition (consider two objects in the same component if they are members of the same cluster).

It is also possible to obtain confidence scores through "marginalization": if you can compute $p(x_i|y)$ where $y$ denotes the observed colors of the pre-classified objects, then this serves as a confidence score for the inferred color of object $i$.

There are other models that might be appropriate.  We can't tell you which one is most suitable for your application domain, but once you choose one, you can work out how to apply the maximum-likelihood maximization principle to it.


Does the intersection of VC and CLIQUE belong to NPC?

The graphs with clique size at least $k$ and VC at most $k$ have a particular
structure: They can be partitioned into three sets, $C$, $I$ and a singleton
$\{s\}$; $G[C]$ is a clique, $G[I]$ is an independent set and $s$ is just a
vertex.  $G[C \cup I]$ is what's called a split
graph.

Proof: If a graph $G$ contains a clique of size $k$, then that clique uses up
(at least) $k-1$ of your vertex cover budget.  Let $G,k$ be a yes instance and
$C$ any $k$-clique.  Observe that $G - C$ is a star with possibly isolated
vertices.

There are two cases: $G-C$ has edges, and $G-C$ does not have edges.  The latter
case is trivial, since we can let $C$ be the solution.  In the former case,
$G-C$ is the star graph with isolates.  Let $s$ be the vertex with non-zero
degree.

Both these cases lead to polynomial recognition algorithm.  The one in which
$G-C$ is an independent set, is the case where $G$ is a split graph.  The other
case has one vertex $s$ for which $G-s$ is a split graph.  Guess $s$, and you're
back at case 1.

As xskxzr pointed out, there is not necessarily a unique "split partition", that is, a partitioning of a split graph into the vertex sets $C$ and $I$, however, there are at most $n$ such partitions, and you can try all.  This leads in the end to an $O(n^3m)$ algorithm for VC∩C, which I'm sure can be improved.


The generalization of comparison sorting you're looking for is algebraic decision trees.  In this model, element distinctness is the standard problem with an $\Omega(n\log n)$ lower bound.  The reduction to convex hull is straightforward: $n$ input numbers $x_1,\ldots, x_n$ are distinct if and only if the convex hull of $(x_1,x^2_1), \ldots, (x_n,x^2_n)$.

These lower bounds depend crucially on the decision tree model.  For the word RAM, it is a famous result of Chan and Pătraşcu that $o(n\log n)$ is possible.


I think that the fastest approach with modern CPUs is

i = num & 255
j = num >> 8
*x = x1[i] + x2[j]
*y = y1[i] + y2[j]

That is 4 arithmetic ops plus 4 loads


Can we move quantifiers to the left in predicate logic?

You are looking for prenex normal form in which all quantifiers "come first".

It exists for every first-order formula but you have to take care when transforming; multiple quantifiers may use the same variable (name) in the original formula, but they may not in the normal form.


Can a Turing Machine have infinite accept states?

In the standard Turing machine, the set of states $Q$ is finite $|Q| < \infty$. Therefore, it cannot have infinite final states. However, it may, or may not have multiple final states. This will not change the power of the machine (i.e., one final state is equivalent to $k$ final states).


How do I derive a regular grammars from this regular expression?

Use Thompson's algorithm to convert the regular expression to a NFA.  Then, you can directly read a regular grammar off, given the NFA: each non-terminal represents one state of the NFA.


Determining if a digraph has any vertex-disjoint cycle cover

Your problem is answered in the Wikipedia article on vertex-disjoint cycle covers. According to the article, you can reduce this problem to that of finding whether a related graph contains a perfect matching. Details can be found in a paper of Tutte or in recitation notes of a course given by Avrim Blum.

As a comment, in the graph-theoretic literature a vertex-disjoint cycle cover is known as a 2-factor.


What is the importance of disjoint edges in k-opt algorithms?

I have a partial answer to my own question. I believe there is a benefit to considering adjacent edges. The full power of the heuristic is not achieved when only disjoint edges are considered.

To arrive at this conclusion, I implemented two versions of the 4-opt algorithm in C#. One version considers only disjoint edges and the other considers both disjoint and adjacent edges. Then, I used both algorithms to solve the Travelling Salesman problem for 1000 scenarios of 25 nodes each.

The two algorithms found the same solution 52.7% of the time.
The disjoint+adjacent algorithm found a better solution than the disjoint-only algorithm 45.7% of the time.
The disjoint-only algorithm found a better solution than the disjoint+adjacent algorithm 1.6% of the time.

The disjoint+adjacent algorithm found tours that were, on average, 99.1% of the length of the tours found by the disjoint-only algorithm.

Based on these results, I'm fairly confident that there is a benefit to exploring adjacent edges in the k-opt algorithm.

I call this a partial answer because I'm not yet clear on whether it is efficient to explore adjacent edges. Yes, exploring adjacent edges in my experiment improved the tour length by an average of 0.9%, but perhaps I could have improved the tour length more than that by using the same computing effort exploring some 5-opt steps instead.

My experimentation suggests that it is optimal to first explore 2-opt steps, then to explore 3-opt steps that include adjacent edges, then to explore 3-opt steps that include no adjacent edges, then to explore 4-opt steps that include adjacent edges, then to explore 4-opt steps that include no adjacent edges, etc. However, that is preliminary speculation. If anyone knows of k-opt documentation that covers this level of detail, please let me know about it.


The  answer is no. A counterexample is given by the following two graphs both having $(-1,
 -1,
 -1,
 -1,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 0,
 1)
$ as the multiset that you describe.

If you want to play further, you can use the following Sage program that found them

def tupleDet(G):
    A = G.am()
    L =  []
    for sub in subsets(range(G.order())):
        D = A.matrix_from_rows_and_columns(sub,sub)
        L.append(D.det())

    return tuple(sorted(L))

def search(n):
    d= {}
    for G in graphs.nauty_geng(str(n)):
        des = tupleDet(G)
        if des in d:
            print G.graph6_string(), d[des]
            return
        else:
            d[des] = G.graph6_string()


Prove that Big-O is transitive by relation. What does it mean by 'by relation'?

f(n)=O(g(n)) implies f(n) <= c1*g(n)
g(n)=O(h(n)) implies g(n) <= c2*h(n)
therefore,
f(n) <= c1*c2*h(n) = c3*h(n)

f(n) <= c3*h(n) implies f(n)=O(h(n))


I don't get where the 0.375 came from ?

If the CPU utilization is 75%, and it's shared equally between two process, each of them gets 37.5%.

  What are CPU minutes?

A CPU-minute is the amount of work done by one CPU in one minute.


Wikipedia says:

  An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.

$\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.


Easy infinite subclass of cubic graphs for Hamiltonian cycle problem

Yes, there is an infinite class of 2-connected cubic graphs on which Hamilton Cycle has a polynomial-time algorithm. Further, there is a such a class that contains infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs, which I think is a decent definition of "non-trivial".

First, let $H_n$ be the union of a $2n$-cycle on vertices $\{1, \dots, 2n\}$ and the edges $\{(i, i+n)\mid 1\leq i\leq n\}$. $H_n$ is 3-regular, 2-connected and has an obvious Hamiltonian cycle.

Now, let $G$ be a 2-connected cubic graph that has no Hamiltonian cycle. Such a graph must exist, since the Hamiltonian Cycle problem is NP-complete on 2-connected cubic graphs, so must have both "yes" and "no" instances. Fix an edge $xx'\in G$. For any graph $H_n$ pick any edge $yy'\in H_n$ and let $H'_n$ be the graph made by taking $G\cup H_n$, deleting the edges $xx'$ and $yy'$ and adding edges $xy$ and $x'y'\!$.

$H'_n$ is 3-regular and 2-connected but I claim that it has no Hamiltonian cycle. Any Hamiltonian cycle $C$ in $H'_n$ must enter the copy of $G-xx'$ at $x$ and leave at $x'$ (or vice-versa). But then $C$ must contain a Hamiltonian path $P$ of $G-xx'$ that begins at $x$ and ends at $x'\!$. However, no such Hamiltonian path can exist, since $P\cup\{xx'\}$ would be a Hamiltonian cycle of $G$, but $G$ was chosen to have no Hamiltonian cycles.

So the desired class of graphs is $\mathcal{H} = \{H_n\mid n>1\}\cup\{H'_n\mid n>1\}$. It remains to show that the Hamiltonian Cycle problem can be solved in polynomial time for graphs in $\mathcal{H}$. Observe that, for every $n$, every edge of $H_n$ is on a 4-cycle (there are 4-cycles of the form $i$, $i+1$, $i+n+1$, $i+n$, $i$). However, the edges $xy$ and $x'y'$ are not on any 4-cycle of $H'_n$. We can test that every edge of a graph is in a 4-cycle in time $\mathcal{O}(n^4)$.

I edited to changed the construction slightly, with two benefits. First, the algorithm runs in time $\mathcal{O}(n^4)$ instead of $\mathcal{O}(n^{|V(G)|})$. Second, there's an actual correctness proof; the old algorithm relied on the assumption that $G-xx'$ is not a subgraph of any $H_n$, which was probably true but really needed to be proven.


Are if statements unnecessary if a program is represented as an explicit state machine?

Literal if statements are not fundamental. As you've shown, it's possible to remove them by writing your program as a state machine, though at the gigantic cost of having to have a different version of the widthdraw() function for every possible starting balance and withdrawal amount. You can also avoid literal if statements by replacing

if (condition) {
    foo
} else {
    bar
}

with

b1 := condition
b2 := not(b1)
while (b1) {
    foo
    b1 := false
}
while (b2) {
    bar
    b2 := false
}

On the other hand, doing so has no clear advantages and many disadvantages. The gigantic-table-of-functions approach leads to huge redundancy, is very hard to maintain and is very hard for compilers and CPUs to optimize.  If you're lucky, the while loop hack might compile to the same code as the simple code with if statements but it's much harder to read and much more prone to programmers mistakenly thinking they can optimize it.

At a fundamental level, some form of conditional execution is necessary. If you have no kind of conditional statement at all, then you can only perform a class of very limited programs called "straight-line programs". These are, perhaps surprisingly, useful as a model of computation because they have a fairly simple correspondence with circuits: they correspond to the simplest notion of algorithm, i.e., take your input data and perform a fixed sequence of operations on it. For example, when you compute the length of a 2D vector, you're using a straight-line program: square the $x$-coordinate, square the $y$-coordinate, add the two squares, take the square root (at least, assuming that all those arithmetic operations, including square root, are taken as being built in to your langauge).


do we know for which $n_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($< 200$), such that every algorithm requires $\sim2^{200}$ operations?

$3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^n)$ run time. SETH does not hold for $k-SAT$ for any bounded $k$; it is only expected to hold for general Satsifiability (with no limit on clause size). We don't really know what asymptotic runtime to expect for $k$-SAT for any $k$ (other than something exponential).

Also, for any $SAT$ formula, there is an algorithm solving it in $O(n)$ time. You could never hope to find a single example hard for all algorithms.

One way to generate hard SAT instances is to reduce from Integer Factorization.


What are their execution time and  possible start time and finish times? For each process time, its execution time is $\text{TAT}-\text{WT}$. Its start time should be WT plus one of 0, 12 and 24. Its finish time should be TAT plus one of 0, 12, 24.

$$
\begin{array}{|c|c|c|c|c|}
\hline
\text{Process} & \text{WT} & \text{TAT}&\text{Execution Time} & \text{Start Time} & \text{Finish Time} \\\hline
P1 & 6 & 15 &9 & 6, 18, 30 & 15, 27, 39  \\\hline
P2 & 3 & 6 &3 & 3, 15, 27 & 6, 18, 30 \\\hline
P3 & 63 & 84 & 21 & 63, 75, 87&84, 96, 108  \\\hline
P4 & 0 & 6 & 6 & 0& 6\\\hline
P5 & 24 & 36 & 12 & 24, 36, 48& 36, 48, 60\\\hline
P6 & 7 & 15 & 8 & 7, 19, 31 & 15, 27, 39\\\hline
P7 & 24 & 39 & 13 & 24, 36, 48 & 39, 51, 63\\\hline
P8 & 6 & 12 & 6 & 6, 18, 30 & 12, 24, 36\\\hline
P9 & 3 & 7 & 4 & 3, 15, 27 &7, 19, 31\\\hline
\end{array}
$$

What can we say about start times and finish times?

The start time of any process except the first process must be the finish time of another process.
The finish time of any process except the last process must be the start time of another process.

What does it mean by SJF? It means among all jobs that have been queued/submitted, the shortest job will be executed first.

So our task is to select 10 numbers $0, 6, \cdots$ from the column "Start time" and "Finish Time" so that

each number must appear in column "Start Time" and column "Finish Time", except the first number 0, which only appears in column "Start Time" and the last number, which only appears in column "Finish time".
The sequence starts with 0, 6 since, as you have observed, the first process started at 0 and ended with at 6.
For the initial numbers that are not greater than 12, their successive differences should become bigger and bigger. For the next segment of numbers that are not greater than 24, their successive differences should become bigger and bigger. For the last four numbers, their successive differences should become bigger and bigger.

There should be enough hint to set you moving again.

Just in case you are still stuck, move your mouse over the following to reveal the spoiler.

   Check the column "Finish Time". Which process must finish last? Then which process' finish time could be the last process' start time? Then which process' finish time could be that process' start time? And so on.

 It turns out the condition SJF is not needed at all. This problem can be solved as long as the processes are executed one after another.

 On the other hand, SJF can be helpful. The three processes with longest execution time, P3, P5 and P7 must be the last three jobs since all of them started later than 24. Since SJF, $P5\prec P7\prec P3$.


Markov Chain Mixing Time of the Complete Graph

Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The variation distance between $\pi$ and $p_x^t$, which is a measure of the similarity between the distributions, is given by the formula
$$
\|\pi - p_x^t\| = \frac{1}{2} \sum_{\sigma \in M} |\pi(\sigma) - p_x^t(\sigma)|.
$$
The sum goes over all states in $M$. The mixing time of a Markov chain $M$ is the smallest $t$ such that for every state $x$, $\|\pi - p_x^t\| \leq 1/(2e)$ (your account may use a different constant).

Given a graph $G$ without disconnected nodes, we can define a Markov chain as follows. The state space is the vertex set of $G$. When at state $x$, the next state is chosen uniformly at random from the neighbors of $x$.

In the particular case of the complete graph $K_n$, the random walk simply chooses a random vertex different from the current vertex. As you mention, $\pi$ is the uniform distribution. Let us compute some variation distances, for some vertex $x$ (the results are the same for all vertices):
$$
\begin{align*}
&\|\pi - p_x^0\| = \frac{1}{2} \left[|\tfrac{1}{n} - 1| + (n-1) |\tfrac{1}{n}-0|\right] = 1 - \frac{1}{n}. \\
&\|\pi - p_x^1\| = \frac{1}{2} \left[|\tfrac{1}{n} - 0| + (n-1)|\tfrac{1}{n} - \tfrac{1}{n-1}|\right] = \frac{1}{2} \left[\frac{1}{n} + \frac{n-1}{n(n-1)}\right] = \frac{1}{n}.
\end{align*}
$$
In both cases we have split the sum into two parts: $\sigma = x$ and $\sigma \neq x$. For all $n$ we have $\|\pi - p_x^0\| > 1/(2e)$. For $n > 2e$ (i.e., $n \geq 6$), we see that $\|\pi - p_x^1\| < 1/(2e)$. Therefore for $n \geq 6$, the mixing time is $1$.

With some effort, we can compute explicitly the variation distances for larger $t$. The transition matrix of the Markov chain is $(J-I)/(n-1)$ (where $J$ is the all ones matrix and $I$ is the identity matrix). Denoting by $e_x$ the basis vector corresponding to $x$, we have $p_x^t = (J-I)^t/(n-1)^t e_x$. Next, notice that $(J-I)/(n-1) \cdot \mathbf{1} = \mathbf{1}$ (where $\mathbf{1}$ is the constant 1 vector), and all other eigenvectors have the eigenvalue $-1/(n-1)$ (the corresponding eigenspaces being all vectors with zero sum). In particular, we can write $e_x = \frac{1}{n} \mathbf{1} + (e_x - \frac{1}{n} \mathbf{1})$, and so
$$
p_x^t = \left(\frac{J-I}{n-1}\right)^t e_x = \frac{1}{n} \mathbf{1} + \left(-\frac{1}{n-1}\right)^t (e_x - \tfrac{1}{n} \mathbf{1}).
$$
Explicitly, we have
$$
p_x^t(y) = \begin{cases}
\frac{1}{n} + \left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right) & \text{if } y = x, \\
\frac{1}{n} - \left(-\frac{1}{n-1}\right)^t \frac{1}{n} & \text{otherwise}. \end{cases}
$$
Therefore
$$
\begin{align*}
\|p_x^t - \pi\| &= \frac{1}{2}\left|\left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right)\right| + \frac{1}{2} \left|\left(-\frac{1}{n-1}\right)^t \frac{1}{n}\right| \\ &=
\frac{1}{2(n-1)^t} \left[1 - \frac{1}{n} + \frac{n-1}{n} \right] \\ &=
\frac{1}{(n-1)^{t-1}n}.
\end{align*}
$$
Using this explicit formula, we find that the mixing time of $K_2$ is infinity (indeed, the chain is periodic), and the mixing time of all of $K_3,K_4,K_5$ is $2$. For $n \geq 6$, as commented above, the mixing time of $K_n$ is $1$.


Proof that languages are Turing-recognizable iff computably-enumerable

If you run $M$ on the $i$-th string then it might never halt, so your algorithm will be stuck. The idea is that if $M$ does halt on the $i$-th string, say after $j$ steps, then we will see it once we get to the $\max(i,j)$-th string.


Can high-order unification be applied to programming by example?

It's incredibly unlikely that a complete sorting algorithm that works for ANY input would be deduced from just 3 inputs.

In particular, there's a problem: sorting is a problem that matches an infinite set of inputs to an infinite set of outputs. You've only given a finite set of inputs, so there's an infinite number of problems which could be described by those input/output pairs.

For example, what if we want to sort numbers lexographically (i.e. dictionary order) instead of numerically? So 1, 11, 112, 1123, all come before 2. But, your example also describes lexographically sorting the given inputs. How does the algorithm know which one?

In short, it can't figure out that you want a sorting algorithm, because you haven't told it you want a sorting algorithm.

For that, you need a specification of some sort. The problem of "Given an arbitrary specification, find an algorithm that meets that specification" is undecidable.

So, there will never be a computer program which, 100% of the time, generates a correct algorithm solving any problem you give it.

It's possible that with machine learning, we can automatically derive some algorithms, but there will always either be a risk that those algorithms are incorrect, or there will be a risk that our procedure will say "I couldn't find a solution."

This is an unavoidable fact of mathematics.


No (unless $P=NP$).  Consider a language $L$ that is in $P$, say, $L$ is the language of prime numbers.

Suppose $V_1$ works as follows: $V_1(x,y_1)$ ignores $y_1$ and checks directly whether $x$ is prime, and if so, outputs 1; otherwise it outputs 0.

Suppose $V_2$ works as follows: $V_2(x,y_2)$ interprets $x$ as a 3CNF formula and checks whether $y_2$ is a satisfying assignment for it; then it checks whether $x$ is prime; and if both are true, it outputs 1, otherwise it outputs 0.

Both verifiers define the same language, namely, $L$.

However, given $x$, the problem of finding $y_1$ that's accepted by $V_1$ can be solved in polynomial time; but the problem of finding $y_2$ that's accepted by $V_2$ is NP-hard.  So, assuming $P \ne NP$, those two function problems have different hardness.


Keeping a String Secret in (Open) Source Code

You have at least two options, depending on what problem you want to solve.

If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit difficult so that users are not tempted, you can encrypt the solutions and store the key as part of your code, perhaps a result of some computation (to make it even more difficult).

If you want to prevent users from retrieving the answer, you can use a one-way function, or in computer jargon, a hash function. Store a hash of the answer, and they you can test whether the answer is correct without it being possible to deduce the answer at all without finding it first. This has the disadvantage that it is harder to check for an answer that is close to the correct answer, though there are some solutions even to this problem.


How to demonstrate that a language is regular for k?

Generalizing the other answer, here is a complete classification of regular language of this sort.

  The language $\{ x \in \Sigma^* : |x| \in S \}$ is regular iff there exist $n \geq 0$ and $k \geq 1$ and sets $A \subseteq \{0,\ldots,n-1\}$, $B \subseteq \{0,\ldots,k-1\}$ such that
  $$ S = A \cup \{ n+ mk + r : m \geq 0, r \in B\}.$$

One direction follows from a direct construction (either a DFA or a regular expression), and the other from the pumping lemma (exercise) or Parikh's theorem.


How to show that this algorithm for evaluating polynomials works?

I suggest you use proof by induction, on the number of iterations of the loop.

In particular, find a loop invariant: an equation that relates the value of y, i, and $a_0,a_1,\dots,a_n$, and that always holds each time you reach the head of the loop.

Then, prove that your loop invariant is indeed an invariant, using proof by induction.


Segmented address / normal virtual address

A virtual address is not normal. It is used with paging. "Normal addresses" are direct physical addresses which access main memory directly. Intel's terminology says that virtual address will be translated by the segmentation unit to a linear address. The linear address will then be translated to physical address by the MMU.
With that said the answer to your question is quite complex since it involves understanding operating-system development concepts.
Real mode
x86 CPUs start with the 8086. Today, the 8086 is emulated at startup of every x86 processor for backward compatibility with older software. This is called real mode. In real mode physical addresses are calculated using the address you specify in the assembly code by implicitly adding ds as the segment selector. They are calculated by the formula ds * 16 + offset. For example,
mov ax, 0
mov ds, ax
mov word [0x1234], 0x1234

will move 0x1234 to the physical address 0x0 * 16 + 0x1234 = 0x1234. With ds set as 0, real mode segmentation is ignored because the address you specify is translated to itself.
Protected mode
After real mode the OS will jump to protected mode. In protected mode there is segmentation and paging available for more recent CPUs. Before paging, there was only segmentation. Paging is more modern than segmentation. For an example on how to set up protected mode in NASM assembly look at the following code:
cli

lgdt[gdtr]

mov eax, cr0
or al, 1
mov cr0, eax

jmp 0x08:protectedMode       ;0x08 = 0b1000, 1 for segment selector
                             ;0 for gdt not ldt and 00 for privilege
bits 32
protectedMode:

gdt_start:
        dq 0x0      ;null descriptor
gdt_code:
        dw 0xFFFF   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 11001111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0xFFFF
        dw 0x0
        db 0x0
        db 10010010b
        db 11001111b
        db 0x0
gdtr:
        dw 24
        dd gdt_start

The code disables interrupts, loads a GDT, enables protected mode by setting a bit in the CR0 control register then jumps to protected mode in segment 0x08. Segment 0x08 is the code segment. Segment 0 being the null descriptor. Here segmentation is enabled with a flat memory model.
The flat memory model is where you specify a base of 0x0 and a limit of 0xFFFFF with a granularity (gr) of 1. The granularity specify if the limit will be in blocks of 1 byte (0) or 4KB (1). If the limit is in blocks of 4KB and the base is 0 then the segment will span the whole 4GB available address space in protected mode (with a limit of 0xFFFFF). The flat memory model is often used in modern operating systems because it simplifies operations in transition modes before long mode is enabled.
Long mode
To enable long mode, you must enable paging and set certain bits in some registers. The following code enables long mode in NASM assembly:

mov eax, cr4            ;enable PAE-paging
or eax, 1 << 5
mov cr4, eax

mov ecx, 0xC0000080     ;set long mode bit in EFER MSR
rdmsr
or eax, 1 << 8
wrmsr

mov eax, cr0            ;enable paging
or eax, 1 << 31
mov cr0, eax

lgdt[gdtr]          ;load a 64 bit gdt (will be ignored afterwards)

jmp 0x08:longMode

bits 64

longMode:

gdt_start:
        dw 0xFFFF
        dw 0
        db 0
        db 0
        db 1
        db 0
gdt_code:
        dw 0x1111   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 10101111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0x0000
        dw 0x0
        db 0x0
        db 10010010b
        db 00000000b
        db 0x0
gdtr:
        dw $ - gdt_start - 1
        dq gdt_start

The 64  bits GDT is necessary because as stated on osdev.org

Notice that we set a 4gb limit for code. This is needed because the processor will make a last limit check before the jump, and having a limit of 0 will cause a #GP (tested in bochs). After that, the limit will be ignored.

So basically, before we jump in the 64 bits code selector to enter long mode, the processor makes a last limit check. After that, the limit is ignored. This is evident since the limit is only 20 bits and, with a granularity of 4KB, this limits the segments to 4GB. In long mode you have access to much more RAM than that.
Once in long mode, you have paging enabled and everything but the CR3 register is translated by the MMU to a physical address. Everything is a virtual address. Segmentation is ignored.


Minimum number of people required to invite everyone to a reunion

One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends.

Now, assuming that you're asking people to invite their friends, and have those people invite their friends, and so on, then your problem basically boils down to finding the connected components of the graph you just made. (Two vertices are in the same connected component iff there exists a path between them)

Actually finding them isn't that bad; it's basically a slightly modified DFS.


What is difference between nondeterministic polynomial time and exponential time?

Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.


How do I approach inductive design problems with no information or context given?

Most questions in AI textbooks of this style are intended to be open ended so that the student can experiment on its own with the problem. So the golden rule is do as you see fit to provide the best learning!

In particular for this problem, your approach seems appropriate.

Since most sorting algorithms fall into a divide and conquer schema, you won't have problem fitting it into an inductive schema.

For example, you could take quicksort, which is usually implemented recursively. And then prove that it indeed sorts an array of size $n$ assuming that it sorts an array of size less than $n$.


Modifies Dijkstra’s Algorithm to find the maximum cost path

This will not work. Consider

(a)-4->(b)
(a)-1->(c)
(b)-2->(d)
(c)-6->(d)

Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.

See here for an alternative based on a topological sort.


Why is string concatenation not distributive over intersection?

When we say that concatenation doesn't distribute over intersection, we don't mean that $L(L_1\cap L_2) \neq LL_1 \cap LL_2$ for all languages $L,L_1,L_2$, but rather that this inequality holds for some $L,L_1,L_2$. Here is one example:
$$
L = \{a,aa\}, L_1 = \{a\}, L_2 = \{aa\}.
$$
In this case $L(L_1 \cap L_2) = \emptyset$ but $LL_1 \cap LL_2 = \{aaa\}$.


Random-access machines support the following operation in constant time:
$$
x \gets M[y],
$$
where $M$ is the memory array, and $y$ is an index whose allowable size depends on the exact model. Whether $M$ is an array of bits or an array of words depends on your exact model.

If you had several different memory arrays, say $M_1[y],\ldots,M_r[y]$, then you could simulate the command
$$
x \gets M_i[y]
$$
with the command
$$
x \gets M[ry + i]
$$
which also takes constant time.

Therefore there is nothing to be gained by allowing several "memories".


Greedy strategy for computing the minimum number of rays that hit all balloons

Principle: You need to shoot the rays in some order and choose carefully the proper direction/angle for the first ray.

  $Q_1:$ I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

See the figure in the problem. Suppose there are only 4 balloons: the two green ones and the two blue ones. If you shoot your first ray along the x-axis (this is allowed by your greedy strategy. note that I suppose that the three bigger balloons cannot be hit by a single ray; otherwise, move them around slightly), you will leave the two other balloons far apart. As a result, it costs you 3 rays, but the optimal is 2.

  $Q_2:$ What is the point of the fact that there is a ray that does not intersect any balloons?

So the key point is to shoot the first ray along the right direction. Here comes the fact that "there is a ray that does not intersect any balloons".

The basic idea is as follows:

first find the direction/angle $\alpha$ along which a ray does not intersect any balloons;
then identify the first balloon (say, clockwise) $b$ with respect to this direction/angle $\alpha$; Here $b$ is defined to be the first balloon you leave when you sweep a line starting from the direction/angle $\alpha$ clockwise.
shoot a ray which is $b$'s rightmost (clockwise) tangent line $l$， remote all balloons hit by $l$,
and then recurse.

  $Q_3:$ Am I supposed to prove that some optimal solution uses this fact?

It is not easy to prove a greedy strategy is correct. You can try to prove the idea above by applying mathematical induction and exchange argument (or maybe show it is wrong!). A hint is to consider the set of rays shot by an arbitrary algorithm, sort them by angles with respect to $\alpha$ (clockwise), then compare it to the optimal solution one by one.

Implementation: In the comments, OP asks for an $n \log n$ algorithm. Well, $n \lg n$ often means that you can sort some things first. Maybe sort all the balloons by the angles of their right (clockwise again) tangle lines. Then it is easy to apply the greedy strategy above.
This is a rough idea. How to implement it efficiently by choosing/designing good data structures is left as an exercise.


Since the graph is acyclic, we know that it is a forest - which means that, there is at most $1$ simple path between two nodes. Now, simply root the graph at one vertex of the edge, remove the edge, and run a dynamic programming algorithm to find the number of vertices in the subgraph, call it $v_a$. Similarly, do the same for the other vertex of the edge, call it $v_b$. The answer is $v_a*v_b$, since the simple path between every $2$ nodes is a different simple path.

Proof: Clearly every simple path we consider passses through the chosen edge. The only other simple paths are the ones where both the nodes are chosen in the same subgraph, which clearly does not pass through this edge.


The Wikipedia article on hash functions is very good,
but I will here give my take.

What is a hash?
"Hash" is really a broad term
with different formal meanings in different contexts.
There is not a single perfect answer to your question.
I will explain the general underlying concept and
mention some of the most common usages of the term.
A "hash" is a function $h$ referred to as hash function
that takes as input objects and outputs a string or number.
The input objects are usually members of basic data types like
strings, integers, or
bigger ones composed of other objects like user defined structures.
The output is a typically a number or a string.
The noun "hash" often refers to this output.
The verb "hash" often means "apply a hash function".
The main properties that a hash function should have are:

It should be easy to compute and
The outputs should be relatively small.

Example:
Say we want to hash numbers in the range from 0 to 999,999,999 to
number between 0 and 99.
One simple hash function can be $h(x) = x \mod 100$.
Common additional properties:
Depending on use case we might want the hash function to
satisfy additional properties.
Here are some common additional properties:

Uniformity:
Often we want the hashes of objects to be distinct.
Moreover we may want the hashes to be "spreading-out".
If I want to hash some objects down into 100 buckets
(so the output of my hash function is a number from 0-99),
then I am usually hoping that about 1/100 objects land in bucket 0,
about 1/100 land in bucket 1, and so on.

Cryptographic collision resistance:
Sometimes this is taken even farther,
for instance, in cryptography
I may want a hash function such that
it is computationally difficult for an adversary
to find two different inputs that map to the same output.

Compression:
I often want to hash arbitrarily-large inputs down into
a constant-size output or fixed number of buckets.

Determinism:
I may want a hash function whose output doesn't change between runs,
i.e. the output of the hash function on the same object will always remain the same.
This may seem to conflict with uniformity above, but
one solution is to choose the hash function randomly once,
and not change it between runs.

Some applications
One common application is in data structures such as a hash table,
which are a way to implement dictionaries.
Here, you allocate some memory, say, 100 "buckets";
then, when asked to store an (key, value) pair in the dictionary,
you hash the key into a number 0-99, and
store the pair in the corresponding bucket in memory.
Then, when you are asked to look up a key,
you hash the key into a number 0-99 with the same hash function and
check that bucket to see if that key is in there.
If so, you return its value.
Note that you could also implement dictionaries in other ways,
such as with a binary search tree (if your objects are comparable).
Another practical application is checksums,
which are ways to check that two files are the same
(for example, the file was not corrupted from its previous version).
Because hash functions are very unlikely to map two inputs to the same output, you compute and store a hash of the first file,
usually represented as a string.
This hash is very small, maybe only a few dozen ASCII characters.
Then, when you get the second file,
you hash that and check that the output is the same.
If so, almost certainly it is the exact same file byte-for-byte.
Another application is in cryptography,
where these hashes should be hard to "invert" --
that is, given the output and the hash function,
it should be computationally hard to figure out the input(s)
that led to that output.
One use of this is for passwords:
Instead of storing the password itself,
you store a cryptographic hash of the password
(maybe with some other ingredients).
Then, when a user enters a password,
you compute its hash and check that it matches the correct hash;
if so, you say the password is correct.
(Now even someone who can look and find out the hash saved on
the server does not have such an easy time pretending to be the user.)
This application can be a case where
the output is just as long or longer than the input,
since the input is so short.


Algorithm to check two binary expression trees for equivalence

The answer depends heavily on what operations you allow to appear in the trees.
If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm.  Basically, you pick random values for $a,b$ and check whether both trees return the same value; and repeat a few hundred times.  See https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and Is there an efficient algorithm for expression equivalence?.
Division can also be handled by expressing the tree as a rational polynomial (ratio of two polynomials), then again using polynomial identity testing.
If you can have addition, subtraction, multiplication, division, and exponentiation, then I don't know whether there are efficient algorithms.  I think that problem, or some variant of it, is addressed here: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials.

(Possibly loosely related: Decidability of Equality of Radical Expressions)
Let me also highlight that expressions like $a^b$ "smell fishy" and don't typecheck when $a,b \in \mathbb{F}$ are elements of a finite field.  For instance, if $\mathbb{F}=GF(p)$, then exponentiation $a^b$ is well-defined if $a$ is taken modulo $p$ and $b$ is taken modulo $p-1$ (not modulo $p$).  In particular, $(a+p)^b=a^b$ modulo $p$, but $a^{b+p} \ne a^b$ modulo $p$.  So, to make an expression like $a^b$ make sense, $a^b$ has to be interpreted as $a^{f(b)}$ where $f$ maps from elements of $GF(p)$ to numbers $\{0,1,\dots,p-2\}$.  There is a natural way to do that, e.g., $f(0)=0$, $f(1)=1$, ..., $f(p-2)=p-2$, $f(p-1)=0$.  But then when you do that, exponentiation doesn't have the properties you might expect.  In particular, $a^{b+c}$ is no longer equal to $a^b \times a^c$.  For instance, if $b=1$ and $c=p-1$, then $a^{b+c}=a^{p-1+1}=a^0=1$, but $a^b = a^1 = a$ and $a^c = a^{p-1} = 1$, so $a^{b+c}=1$ but $a^b \times a^c = a$.  So I would be pretty suspicious of any expression that contains exponentiation where the expression in the exponent is an element of $\mathbb{F}$.


How can I determine the start non-terminal of a CFG?

By definition a grammar is a tuple $(N,T,P,S)$ where $N$ is the set of non-terminals, $T$ is the set of terminals, $P$ is the set of productions, and $S \in N$ is the start symbol.

Therefore if you have a grammar you already have $S$ (and if you don't know $S$ then you don't have a grammar).


Time complexity of proximity search in distance matrix

There are a number of candidate techniques you could use.

The simplest is just naive search.  Given a locus $L$, just scan over all $n$ loci and see how close each one is to $L$.  You might measure "close" as Euclidean distance in the 3D coordinate system.  Naive search takes $O(n)$ time, since you have to examine each locus and you do $O(1)$ work for each locus you examine.  In your example, it appears that $n=40,000$, so this might be perfectly efficient, given your miraculous mapping to 3D space.

If you want to do this task many times, you can preprocess the data you have to make subsequent queries faster.  For instance, one candidate is to use the techniques described in the following question: Find all neighbors at a certain distance, in 3 dimensions  Basically, you have the 3D coordinates for each locus, so you store those 3D points in a k-d tree or octree.  Now given the 3D coordinates of a locus $L$, you can quickly scan the tree to find all neighbors that are near $L$ in 3D space.  The asymptotic running time of these algorithms is hard to analyze, but it might be something like $O(\lg n)$ times the number of loci that are close to $L$.

If you didn't have the miraculous map to 3D coordinates, there are alternative approaches that use just the $n \times n$ matrix of edit distances, but they will be slower.  For instance, if you have precomputed the $n\times n$ matrix, then you can use naive search: given a locus $L$, scan over all $n$ loci and see how close each one is to $L$ using the edit distance matrix.  This will take $O(n)$ time, since you have to consider all $n$ loci and it takes $O(1)$ work for each look-up in the matrix.

Unfortunately, precomputing the $n \times n$ matrix of edit distances will probably take $O(n^2)$ time, or maybe even slower.  (Therefore, unless you're going to do many queries, it is not clear that precomputing the matrix of edit distances is worthwhile.)

Anyway, even if you have the precomputed distance matrix, I don't know of any way to use nearest-neighbor search techniques to get the running time below $O(n)$ time.  This is a significant difference from the case where you have the miraculous 3D map: if you have the miraculous map to 3D coordinates, it looks like you can make search much faster.


Are the frequencies of the Huffman encoding of 3 characters unique?

You want frequencies $f_1,f_2,f_3$ for three characters, so that their Huffman encodings are $(0,10,11)$.
The Huffman algorithm repeatedly "merges" the two least frequencies. So any choice that assigns the two least frequencies to the last two characters will work. That means $f_2,f_3 \le f_1$. Since these are frequencies you probably also want the values to add to $1$, but that is of no consequence for the algorithm.
In general the Huffman algorithm does not specify which branches go left and which go right (unless we add that to the implementation) so it is hard to guarantee codes $(0,10,11)$ instead of $(1,00,01)$ for instance.


Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

This question describes a nice situation to introduce a partial version of the generalized Rice's theorem.
A partial version of the generalized Rice's Theorem
For $S$ be a subset of Turing-recognizable languages, let $L_S$ be the set of TMs that recognize a language in $S$, that is,
$$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$
Suppose $L_1 \in S$, $L_1 \subset L_2$ and $L_2 \not\in S$. Then $L_S$ is not Turing-recognizable.
$CF_{\text{TM}}$ is not Turing-recognizable.
$CF_{\text{TM}}=L_{\text{CFL}}$, where $\text{CFL}$ is the set of all context-free languages. Let $L_1=\emptyset$ and $L_2=\{a^{n^2}\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \text{CFL}$, $L_2\not\in \text{CFL}$. So, $L_{\text{CFL}}$ is not Turing-recognizable.
$\overline{CF_{TM}}$ is not Turing-recognizable
$\overline{CF_{\text{TM}}}=\{ s : s\text{ is a string that does not encode a TM}\}\sqcup L_{\overline{\text{CFL}}}$, where $\overline{\text{CFL}}$ is the set of all non-context-free formal languages. Let $L_1=\{a^{n^2}\mid n\in \Bbb N\}$ and $L_2=\{a^n\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \overline{\text{CFL}}$, $L_2\not\in \overline{\text{CFL}}$. So, $L_{\overline{\text{CFL}}}$ is not Turing-recognizable.
Proof of the partial version of the generalized Rice's Theorem
Suppose $L_S$ is recognized by a TM $M_S$. We will construct a TM that recognizes $\overline{HALT_{\text{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$, which is known as not Turing-recognizable, hence a contradiction. The TM  works as follows.

On input $\langle M, w\rangle$:

Construct a TM $T_{M,w}$ that works as follows:
On input $x$:

Run $M_1$ on $x$, and accept if $M_1$ accepts. Here $M_1$ is a TM that recognizes $L_1$.
At the same time, also run $M$ on $w$. If $M$ accepts, run $M_2$ on $x$, and accept if $M_2$ accepts.  Here $M_2$ is a TM that recognizes $L_2$.

Run $M_S$ on $T_{M,w}$, and accept if $M_S$ accepts.

Note this TM accepts $\langle M,w\rangle$ if and only if $M_S$ accepts $\langle T_{M,w}\rangle$, which means $L(T_{M,w})\in S$. Also note
$$L(T_{M,w})=\begin{cases}
L_1 & \text{if $M$ does not halt on $w$},\\
L_2 & \text{otherwise},
\end{cases}$$
so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{HALT_{\mathrm{TM}}}$.
The above proof is a modified version of xskxzr's nice proof of his lemma in his answer.

Exercises
Exercise 1. Show that a context-free language (that is defined by a context-free grammar) is Turing-recognizable. Show that a non-context-free formal language (that is defined by an unrestricted grammar and that cannot be defined by a context-free grammar) is Turing-recognizable.
Exercise 2. (One minutes or two) Check that both the question and this answer remain valid if we replace "context-free" by "regular".

Exercise 3. Show that $\overline{\text{CFL}}$, the set of all non-context-free formal languages given by their grammars properly encoded by some fixed scheme, is not Turing-recognizable. Hence, $L_{\overline{\text{CFL}}}$ cannot be Turing-recognizable either.
EXercise 3. Read the full version of generalized Rice's Theorem. Can you prove it? (This might not be easy.)


Merging of two convex polygon chains in O(log n)

You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation.  I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc.  They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups.  The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly.  Instead, they are implicit.  To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere.  Thus, when concatenating two trees, there is no need to renumber the keys.  You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information  stored in each node).


Multiple Constraint Knapsack Problem Dynamic Programming

Yes. More precisely, for any fixed number of constraints (for example, weight and volume) the problem has a pseudo-polynomial time algorithm based on dynamic programming.

The idea in your comment (add one more dimension to the dynamic programming table) is essentially correct. In the classic knapsack, for any $i=0,\ldots,n$ and $w=0,\ldots,W$, you compute the highest profit that you can get with items of type $\le i$ and total weight $\le w$ (so you can get an $O(nW)$ time algorithm). In the generalization, you also need to iterate on the total volume $v=0,\ldots,V$, which means an $O(n W V)$ time algorithm.


Deriving the Time Complexity of Ryser's Algorithm for Evaluating the Permanent of a Matrix

For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.


When generating a PDA from a CFG do I have a receiving state?

Assuming that you mean accept state when you say receiving state, the construction given in the wikipedia article has one accept state, being the only state in the machine. It accepts when you reach the end of the input with an empty stack. However, the construction used there requires a slight abuse of notation, as you need the starting symbol from the grammar to be pushed to begin with, and you have to be able to push more than one symbol at a time. This isn't so bad, but a more detailed construction makes the conversion more obvious.

The basic approach is to simulate the CFG using the PDA, informally it reads symbols off the stack, if it's a nonterminal, it replaces it with its production, if it's a terminal, it matches it off the input. The input alphabet for the PDA is the same as the CFG, the stack alphabet is the input alphabet plus the set of nonterminals in the CFG and the end of stack symbol.

The basic backbone of the PDA is:

Where $\$$ is the special end of stack symbol, and $S$ is the start symbol of the grammar.

The "production rules" transition represents a bunch of loops that simulate each production of the grammar. Given a production $X \rightarrow \chi_{1}\ldots\chi_{n}$ where the $\chi_{i}$'s are either terminals or nonterminals, we add a loop starting and ending at $q_{3}$ that looks like:

Note that I've opened the loop, and the first and last state are the same.

The last past is the "terminal rules" loop, which represent a bunch of loops (one for each terminal symbol), that match terminals pushed onto the stack by the productions to terminals in the input:

So hopefully you can see how the simulation works, the PDA literally walks through the steps of the CFG, sticking terminals and nonterminals on the stack, replacing nonterminals with their productions, and matching terminals off the input. Then it can only reach the accept state if you can match the entire input (and hence there must be some series of grammar rules that get you there).


Efficient algorithm for finding weakly connected components

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$.  Now use any standard algorithm for finding connected components in the resulting undirected graph.

One standard approach for finding connected components is to use DFS.  This runs in linear time, i.e., $O(|V|+|E|)$ time.

You can't hope for any algorithm that will perform asymptotically faster: any correct algorithm will have to examine every vertex and every edge at least once, so will have to take at least $\Theta(|V|+|E|)$ time.


Graph problem known to be $NP$-complete only under Cook reduction

I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.

Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.

Given a Boolean $(\wedge;\vee;\neg)$-formula $F$ and
an integer $k$, is there an equivalent $(\wedge;\vee;\neg)$-formula of size at most $k$?

On p. 143, the authors state:

  This provides a somewhat rare example of a natural problem for which a Turing reduction seems crucial (in the sense that we do not know of any simple modification or alternative methods that would give a many-one
  reduction).

They do not cite any other such examples from the literature. I suspect that "somewhat rare" is possibly an understatement.

References

David Buchfuhrer and Christopher Umans: "The complexity of Boolean formula minimization" Journal of Computer and System Sciences, Volume 77, Issue 1, January 2011, Pages 142-153


No, it is not sufficient to check that the 'Church encoding' is uninhabited.

Consider the type:

$$\mathsf{data} \;U = L\ (U → U)\;  |\; A\ U\ U$$

The idea is that $U$ is the type of untyped lambda terms. If you allow this as a data type into your language, it causes problems. At the very least, you can write loops in $U$ if you are allowed to inspect its values by case analysis.

δ : U -> U
δ (L f) = f (L f)
δ x = x

ω : U
ω = δ (L δ)

-- ω ==> δ (L δ) ==> δ (L δ) ==> ...

If you are also allowed to do recursion on the presumption that $U$ is well-founded, these loops leak into every other type.

However, the 'Church encoding' of $U$ is not uninhabited:

$$U' = ∀ R. ((R → R) → R) → (R → R → R) → R$$

In fact, this is a somewhat well-known representation of untyped lambda terms in a sort of higher-order abstract syntax. You can write down (an encoding of) any untyped lambda term you want:

$$id : U' = λ L. λA. L (λ x. x)$$
$$comp : U' = λ L. λA. L (λ g. L (λ f. L (λ x. A\ g\ (A\ f\ x))))$$
$$δ' : U' = λ L. λ A. L (λ x. A\ x \ x)$$
$$ω' : U' = λ L. λ A. A\ (L (λ x. A\ x\ x))\ (L (λ x. A\ x\ x))$$

So, this encoding is certainly inhabited. But, the reason I was using scare quotes earlier is that is clearly still not what we expect the original data type to mean, so it's rather unclear whether this should be considered the Church encoding of that data type. For instance, you will be unable to exhibit the equivalence:

$$U' \cong (U' → U') + U' × U'$$

which is expected of the data definition. Also, $U'$ is arguably a more faithful representation of the syntax of untyped lambda terms, because all we can do is abstract and apply, as those are the only things we know about the abstract $R$ type. $U$, at least presuming the usual semantics of data, allows us to write, "exotic terms," which is what δ and ω actually are (note that they're not the same as $δ'$ and $ω'$). And this makes sense, because these exotic terms are what allow us to write loops using the data type, whereas $U'$ is a perfectly acceptable System F type, and System F is strongly normalizing.

So, clearly, some more thorough check is necessary than mere habitation. You must check that the 'encoding' actually models the properties you're going to allow your data type to have.


Check if a lambda constructor is well-typed

A term $M$ is well-typed if and only if there is a type derivation that leads to a judgement of the form $\Gamma \vdash M : \tau$ for some context $\Gamma$ and some type $\tau$. (I use the word “type” in its general sense which can include quantified variables; in the terminology commonly used with Hindler-Milner, that's a type scheme.) So, to prove that you cannot give a type to a lambda term from first principles, you prove that there is no type derivation that leads to such a judgement.

Hindley-Milner has a nice property in this respect: it's syntax-directed, i.e. it's presented as a set of deduction rules such that for any term, there is a single rule that can be used to end a deduction of this term. (Being syntax-directed is actually a property of a presentation of the type system, not a property of the type system. In this post, I use the classical syntax-directed presentation which builds generalization into the let rule, rather than having a separate rule for generalization.)

Another nice property (shared by almost every type system) is that unused variables can always be removed from the context. So for example, if $(\lambda x y.y (x y)) (\lambda z.z)$ is well-typed, it must have a type derivation ending with the App rule and, since the term has no free variable, an empty context:
$$
\dfrac{\vdash (\lambda x y.y (x y)) : \tau_1 \to \tau_0 \qquad
       \vdash (\lambda z. z) : \tau_1}
      {\vdash (\lambda x y.y (x y)) (\lambda z.z) : \tau_0}
$$

You can of course make use of any theorem that you already know. In particular, the principal typing theorem can be useful: if a term is well-typed then all of its types are instances of a particular one. For example, the identity function $(\lambda z.z)$'s possible types are all instances of $\forall \alpha. \alpha \to \alpha$. Similarly, it's easy to see that the function $(\lambda x y.y (x y))$ has the most general type $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$.

In order to find a type for $(\lambda x y.y (x y)) (\lambda z.z)$, we saw above that we need to find types $\tau_0$ and $\tau_1$ such that $\tau_1 \to \tau_0$ is an instance of $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$ and $\tau_1$ is an instance of $\forall \alpha. \alpha \to \alpha$. This means that there must exist base types $T_1$, $T_2$ and $T_3$ which satisfy the equations
$$ \begin{align}
\tau_1 &= \forall \alpha \beta \gamma. (T_2 \to T_3) \to T_2 \\
\tau_0 &= \forall \alpha \beta \gamma. (T_2 \to T_3) \to T_3 \\
\tau_0 &= \forall \alpha \beta \gamma. T_1 \to T_1 \\
\end{align} $$
Hence $T_3 = T_1 = (T_2 \to T_3)$. But this is impossible due to the structure of types: a type can't be a strict subterm of itself. Therefore the premise of was wrong: the term $(\lambda x y.y (x y)) (\lambda z.z)$ is not well-typed.

chi's answer shows how to use another theorem about Hindley-Milner to shorten the proof: subject reduction, i.e. the property that if a term is well-typed and it reduces to another term then that other term also has the same type. Since $(\lambda x y.y (x y)) (\lambda z.z) \to_\beta^* \lambda y. y y$, if the original term has a type then so does $\lambda y. y y$. By contraposition, if $\lambda y. y y$ is not well-typed then neither is the original term. You can show that $\lambda y. y y$ is not well-typed by a shorter application of the methodology above: note that if it is well-typed, it must be an application of the lambda typing rule, which leads to a type equation of the form $T_1 \to T_1 = T_1$, which has no solution for the same reason as before.

There are, of course, other type systems where the term in question is well-typed. These type systems must have some additional ways of typing terms that Hindley-Milner doesn't have. I'll give two examples:

If you extend the syntax of types to allow them to be recursive (as with ocaml -rectypes), then the reasoning about the type equation having no solution because a type can't contain itself breaks down, and indeed both $\lambda y. y y$ and the original term are well-typed in this system. For example, the most general type of $\lambda y. y y$ is $\forall \alpha \beta [\alpha = \alpha \to \beta]. \alpha$.
If you add a rule that allows intersection types:
$$
  \dfrac{\Gamma \vdash M : \tau_1 \qquad \Gamma \vdash M : \tau_2}
        {\Gamma \vdash M : \tau_1 \wedge \tau_2}
  $$
then the reasoning above breaks down because the presentation of the type system is not type-directed. The intersection rule can be used with any language construct. With this type system, $y : \alpha \wedge (\alpha \to \beta) \vdash_{\wedge} y : \alpha$ and $y : \alpha \wedge (\alpha \to \beta) \vdash_{\wedge} y : \alpha \to \beta$ and so $\lambda y. y y$ has the type $\forall \alpha \beta. (\alpha \wedge (\alpha \to \beta)) \to \beta$. The original term is also well-typed. With a rule that departs so radically from being syntax-directed, you might think that it's difficult to prove that a term is not typable, and you'd be right: the intersection rule is so strong that it causes all strongly normalizing terms to be well-typed. Conversely, intersection types with base types (but without quantifiers or a top type) only allow strong normalizing terms, so to prove that a term is not typable in that system, it's sufficient to prove that a term is not strongly normalizing.
See Does there exist a Turing complete typed lambda calculus?) for more information about intersection types.


Why store self and parent links (. and ..) in a directory entry?

You get fewer special cases.  In many situations, VFS may handle ".." as it handles any other directory name.


Hoare logic - partial/total correctnes and strength invariant

You're misunderstanding.  It's not that when you try to prove total correctness, Hoare logic somehow magically finds a stronger invariant for you.  Hoare logic doesn't find the invariant for you -- either way, you have to find the invariant yourself and then prove it.

Rather, it's that you need to prove a stronger invariant if you want to prove total correctness.  A weaker invariant can suffice to show partial correctness.  Therefore, total correctness can often be harder to prove than partial correctness (proving total correctness requires more work, because you have to prove a stronger, more detailed invariant).


Maximimal Independent Set on Ring and Path

if a node terminates the algorithm after an iteration with probability $1/c$, then after $k$ iterations this probability is $c^{-k}$. and the number of iterations required is $\ln _c n$. This is done by arguing that the expected number of nodes after $k$ iterations is $n c ^{-k}$, and we want to make this value less or equal to 1. We achieve this by setting $k$ to $\ln _c n$.

Therefore, replacing $k = \ln _c n$ leads to $c^{- \ln _c n} = 1/n$, and whence the probability of correctness is $1 - 1/n$.

How to find $c$ ? As I said in my comment, I truly dont know the exact value. Here is a solution. Someone else may correct me.

We should calculate the probability that a node $v$ terminates the algorithm in any given iteration. This happens if $v$ is greater than its two neighbors OR if the left neighbor of $v$ is greater than all its neighbors OR if the right neighbor of $v$ is greater than all its neighbors. The probability of any of these events is 1/2*1/2 = 1/4. The probability of any of these events is 1/4 + 1/4 + 1/4 = 3/4. Therefore $c = 3/4$.


The fundamental difference in these two problems lies in the verification of a proposed solution.

The solution of a search problem is only as hard to verify correct as the predicate itself.

The solution of an optimization problem needs special arguments or proofs to avoid having to search the entire domain to verify a solution correct, which often may not exist or are not known.

This means that simply finding a solution is enough for a search problem, but without a proof or exhaustive search an instance for an optimization problem is uncertain.


If you can convert them to Horn clauses, you can convert them to Prolog.

If you can't convert them to Horn clauses, I don't think you can convert them to Prolog.

So, convert them to Horn clauses first, and then see the answer to this question:

Horn clause to Prolog


Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar

First replace ever terminal $a$ with a non-terminal $X_a$ and add a production $X_a \to a$, because context sensitive grammars only work on non-terminals. Then, for every production $A_1\dots A_n \to B_1\dots B_n$ create new non-terminal $D$ and replace the production with a sequence of productions $$\begin{align} A_1A_2\dots A_n &\to DA_2\dots A_n \\ DA_2A_3\dots A_n &\to DB_2 A_3 \dots A_n \\DB_2A_3A_4\dots A_n &\to DB_2 B_3A_4 \dots A_n \\ &\vdots \\ DB_2\dots B_{n-1}A_n &\to DB_2\dots B_{n-1}B_n \\ DB_2 \dots B_n &\to B_1B_2 \dots B_n \end{align}$$which are all context sensitive. Also, replace every production $A_1 \dots A_n \to B_1 \dots B_m$ where $n < m$ with $$\begin{align} A_1\dots A_n &\to B_1\dots B_{n-1}C \\ C &\to B_nB_{n+1} \dots B_m\end{align}$$where the first production can be made context sensitive as previously shown and the second one is context free. Of course, this construction may introduce problems (if $B_1A_2 \to \dots$ is already in the grammar, for instance). This is easily solved by adding new non-terminals.


What does "number of gates" mean in circuit complexity?

The number of inputs to a gate is an independent restriction or allowance on the circuit. The number of gates in a circuit is simply the number of gates.

Of course you can always measure the two separately. For example the $W$-hierarchy in Parameterized Complexity can be defined in terms of the large-gate depth (called in this context the weft) of families of circuits (i.e. the maximum number of gates with unbounded fan-in on any path from the inputs to the output).

Of course we can also take an unbounded fan-in gate (if we're sticking to AND/OR at least) and replace it with a circuit consisting of a several bounded fan-in gates, but the size may increase significantly.


Broadly, I can see two possible approaches: machine learning, or data mining

Machine learning

You could look into using machine learning to learn a transducer that transforms the input sequence (the letters in the word) to the output sequence (the pronunciation).  This approach doesn't try to find an explicit set of rules; it just tries to find a method that is effective in practice at producing the right pronunciation.

You could try training a recurrent neural network (RNN), and/or a LSTM network.  LSTM's have been effective at related tasks, and since you have a large training set, they might possibly be effective here.  Bi-directional RNN's/LSTM's might be worth exploring.

Data mining

Alternatively, you could use data mining techniques to try to find an explicit set of rules that seem to have good support among your dictionary.

This problem fits into the general area of sequence mining (also known as sequential pattern mining) and association rule learning.  I think it might be fruitful to try applying one of the algorithms from that field, to your problem.

In your case, you could consider each possible substring of the word or pronunciation to be a possible item, and your goal is to find rules of the form $x \Rightarrow y$, where $x$ is a substring of the word and $y$ is a substring of the pronunciation.  This is a special case of itemset mining, where your itemsets are restricted to have size 1.  You could then adapt any standard itemset algorithm (e.g., Apriori, FP-growth) to this problem.

For instance, here is an adaptation of Apriori.  You consider all possible rules of the form $x \Rightarrow y$, where $x$ and $y$ are length 1.  For each, you compute their support or some probabilistic measure of the strength of the association (e.g., out of all words that contain $x$, what fraction contain $y$?).  Discard all candidate rules for which this metric is below some threshold.  Then, try all extensions of this rule by extending either $x$ or $y$ by one character to the left or right side of it; this gives you a bunch more candidates.  For each such candidate, compute the metric and discard those that are below the threshold.  Keep expanding your set of candidates until no new candidates can be identified.  This is basically a form of "breadth-first search".  Finally, at the end, prune your rules by eliminating rules with a containment relationship (e.g., if you have a rule $x \Rightarrow y$, then you might want to remove all other rules of the form $x' \Rightarrow y'$ where $x'$ is a substring of $x$ and $y'$ is a substring of $y$).

You could also consider similar tweaks to FP-growth.

However, it's not clear to me how well a data mining-based approach will work: while it does consider order to some extent, it doesn't take into account the position within the word, and it doesn't consider whether a set of rules fully covers all of the characters in the word, and it doesn't take into account rule overlap (e.g., $x_1 \Rightarrow y_1$ and $x_2 \Rightarrow y_2$ where $x_1,x_2$ overlap partially).


How to measure processing power of a quantum computer?

this is a very difficult/subtle/controversial question at the heart of current research that even topnotch scientists are having a lot of trouble answering precisely. there are two main lines of QM computer development:

adiabatic QM computing, this is the Dwave computer that is up to 512 qubits, but it doesnt operate using "qbit transport" which is the main line of scientific research
"standard" QM computing transports qbits so their spins can interact as laid out in "quantum circuits". there is a lot of theoretical research on this topic but physics researchers are apparently still far from actually implementing (physically building/realizing) this type of computing.

unfortunately in both cases there are other further issues:

theoretically, can one get a speedup based on the mathematics/physics of quantum computing? see eg proof of speedup with [adiabatic] qm computing tcs.se
in practice, after one builds the computer, and one applies various systems, eg error correction being one of the main ones, and decoherence being one of the main challenges to overcome, how efficient will it be? will there be any speedup over conventional computing?
QM algorithms run completely differently, they are not based on binary logic! so therefore there is not yet any way to determine what the "equivalent" or "corresponding" qm algorithm is to a "classical" algorithm that is under consideration. the best we can do is try to optimize the performance of both & see what happens but that is obviously not satisfactory and somewhat dependent on human factors.

so the best answer right now is "nobody can really say right now". or, the best quantum computer in the world, Dwave, (apparently costing in \$ millions per unit, and over $100M research so far) is now shown in scientific papers to be slower than desktop computers when algorithms are optimized on those computers. or, "its an open question subject to cutting edge international research". there are many posts in Aaronsons blog on the subject. see also

Dwaves dream machine
Will Bourne, Inc magazine 1/9/2014
Dwave & the inception of the QM computing dream collection of lots of refs, papers, se questions etc


You are probably looking for a solution to the following optimization problem.

Weighted maximum biparite matching. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \rightarrow \mathbb{N}$, find a set of edges $A\subseteq U\times V$ such that all edges in $A$ are disjoint (that is, no two edges are adjacent, that is, no group has two admins and no admin has two groups) and the sum $\sum_{a\in A}w(a)$ is minimized, and it is not possible to add another pair $(u,v)\in U\times V$ to $A$ without violating the non-adjacency constraint.

The sets $U$ and $V$ are the users and the groups, respectively. The set of edges $E$ is the set of applications (user-group pairs) and the set of weights is the salary of a given assignment. The Blossom algorithm (link) is a optimization algorithm that finds a maximum matching, and it can be adapted to solve the weighted case.

A final note: you seem to be optimizing two objectives at once: both the minimum salary, and the maximum number of covered groups. Obviously these objectives conflict: covering less groups gives a lower salary. Fortunately, the Bloom algorithm will find a maximum matching, so it will cover as many groups as is possible, and within the set of matchings that cover the maximum number of groups, it finds the one with the lowest sum salary.


What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?

This can be solved with a prefix function in linear time.

Prefix function of a string $S$ is an array $p$ of length $s$, where $p_i$ is the length of the longest border of a string $s_1 \dots s_i$. The $border$ of a string is its longest proper prefix which is also a suffix. E.g. the border of $abacaba$ is $aba$, the border of $ababa$ is $aba$, the border of $banana$ is empty. The prefix function can be computed in linear time (see this Coursera lecture, for example).

For simplicity I reverse the string and now look for a recurring prefix, not suffix. Let $p_i$ be the prefix function of the string. Then the length of the shortest recurring substring of the $i$-th prefix of the string is $i - p_i$:

s: a b a c a b a c a b a
p: 0 0 1 0 1 2 3 4 5 6 7
   -------------
           -------------
   + + + +

With hyphens I denote the matching prefix-suffix pair found by prefix function, and with pluses the generating prefix itself. It is easy to see that it ends exactly where the matching suffix begins, that is, at the position $i - p_i$.

Having the length, the answer is trivially computed as $i - (i - p_i) = p_i$. Isn't it the nice observation? ;) So what you actually want to do is to take the maximum value of the prefix function of the reversed string.


Deamortizing a Las-Vegas randomized algorithm

If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which you let the algorithm loose, then the number of operations will be at most $Ac'$ with probability $1-1/A$.

In some cases you know more about the distribution of the running time of the algorithm – say its variance. In that case you can get better bounds using (for example) Chebyshev's inequality.

Another trick to try is to run several instances of the algorithm in parallel with fresh coins. For example, suppose that we run $B$ independent instances of the algorithm, each for $(A/B)c'$ operations at each step. The probability that none of them finishes is at most $(B/A)^B$, compared to $1/A$ we had before. Choosing $B \approx A/e$, this improves the failure probability from $1/A$ to roughly $e^{-A/e}$.


Is there a way to measure the maximum random bits of the outputs of a generator?

You might be looking for computational min-entropy.


I think it would be perfectly reasonable and normal to present the pseudocode as is, and to mention in the accompanying text that if you sort $R$ in advance, you can implement this algorithm in $O(m \log m)$ time.  I think it's pretty clear how to implement the selection step, and you don't need to write out all the indices to explain.


Graph search or shortest path algorithm for graph with multiple “goals”?

If you have multiple goal nodes and a consistent (or admissible) heuristic to each of them, taking the minimum of them will be still be a consistent (or admissible) heuristic.
Aside from that, there is nothing in A* that prevents you from having multiple goal nodes.  The algorithm works fine unchanged.

[Edit] Another heuristic for your problem specifically: for each tile, compute the distance to the nearest valid goal-space, then take the sum over all tiles as the heuristic.
With $n$ spaces, $n-1$ tiles, and $g$ goals, this can be done in $O(n)$ time during the pathfinding by pre-computing the distance to the nearest goal, for each tile, using eg. BFS. This will require $O(n^2)$ space and $O(gn^2)$ time (by searching backwards from each goal).


Convert C language code to problem specification by computing the invariant of a program

You can not reconstruct the specification from just the code.

For one thing, you don't know whether the code is correct or not. For another, there are multiple possible specifications that are all compatible with the code.

For instance, consider the following function:

unsigned int f(unsigned int x) {
    return x+1;
}

Was the intended specification that retval == x+1?  Or that retval > x?  Or that retval > 0?  We can't tell.  There just isn't enough information to know.  (Ignore integer overflow for the moment.)


Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

Yes, with such a powerful oracle, the halting problem can be solved.
To be clearer, given an arbitrary Turing machine, the oracle will tell the set of words accepted by that Turing machine is finite or not.
Suppose we are given a Turing machine $M$ and an input $x$. Let us construct Turing machine $M'$ such that on all inputs, $M'$ will simulate $M$ running with input $x$. Furthermore, when the simulation of $M$ halts (because $M$ halts on $x$), $M'$ will accept, regardless of whether $M$ accepts or rejects.
Note that $M'$ either always accepts or always runs forever. Now let us apply the oracle to $M'$.

If the oracle says $L(M')$ is not finite, it implies $M'$ always accepts. That means $M$ halts on $x$.

If the oracle says $L(M')$ is finite, it implies $M'$ always runs forever. That means $M$ on $x$ runs forever.

So, we have solved the halting problem on $(M,x)$, thanks to the oracle.

Here is a similar question, which might be the question intended by the OP as well.
Suppose (without any oracle) we are given an arbitrary Turing machine $M$ that accepts only finitely many words and an arbitrary word $x$, can we decide whether $M$ will halt on $x$?
The answer is no.
Otherwise, we can solve the original halting problem in the following way, which is known to be impossible.
For a pair of Turing machine and input $(M,x)$, we construct Turing machine $M'$, which checks if its input is $x$. If yes, it will run as $M$; otherwise, it will loop forever. Since $M'$ accepts at most 1 word, our assumption says that we can decide whether $M'$ on $x$ will halt or not. But that is exactly the same as whether $M$ halts on $x$ or not.


If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover?

Given a cover for $\mathcal{X}$, you seek to "cover" $\mathcal{X}\times\{-1,1\}$.
To do so, you take any set $A$ from the cover of $\mathcal{X}$, and consider the sets $A\times\{1\}$, $A\times\{-1\}$. If your original cover was of size $K$, then this process results in $2K$ sets (the reason you don't end up with $2^K$ sets is that fixing the label for one set does not affect the labeling of another, so there is no multiplication going on).

In a more straightforward approach, let $\mathcal{C}$ be your original $\frac{\gamma}{2}$-cover for $\mathcal{X}$, then a partition $\mathcal{P}$ of $\mathcal{X}\times\{-1,1\}$ such that for all $ p\in\mathcal{P}$ and $(x_1,y_1),(x_2,y_2)\in p$ it holds that $y_1=y_2$ and $||x_1-x_2||\le\gamma$, is given by $\mathcal{C}\times\{-1,1\}$, which is of size $2|\mathcal{C}|$.


Complexity of closest set of points in plane problem

There seems to be some confusion regarding parameters. There is $n$, which is the number of points we wish to return; and there is another parameter, let's say $N$, which is the number of points in the input. Assuming that $N \geq n$, the output would consist of $n$ points, so we can dispense with your $k$.

Since the heap contains at most $n$ points, all operations take $O(\log n)$ time. Therefore the running time can be upper-bounded by $O(N\log n)$. It should be easy to construct matching hard instances which show that the worst-case time complexity is indeed $\Theta(N\log n)$.

Regarding space consumption, the usual convention is to measure only the "work tape", that is, only the auxiliary space taken by the procedure, without the input and output. In this case, this is only the heap, which uses up $\Theta(n)$ space.


You should also have a look at External Sorting algorithms. This is another book on the subject Algorithms and Data Structures for External Memory


Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the other hand, accept an input of a fixed size. Hence Boolean functions don't even qualify as potentially Turing-complete.

The relevant notion of completeness here is a complete basis of connectives. A set of connectives ($k$-ary functions on Boolean values for arbitrary $k$) is complete if every Boolean function on $x_1,\ldots,x_n$ (for arbitrary $n \geq 1$) can be represented using the connectives. The following sets are complete: the de Morgan basis $\{\lnot,\lor,\land\}$ and the basis $\{\lnot,\Rightarrow\}$. In contrast, $\{\lnot,\oplus\}$ is not complete: it can only express linear functions.


What is the difference between shortest distance and shortest path?

As @randomA already indicated in a comment, a shortest path from $v$ to $w$ is a sequence of vertices (that describes a path from $v$ to $w$, which is shortest among such sequences).
The shortest distance on the other hand is the length of a shortest path, i.e. a number.

As a sidenote, be aware that there can be multiple shortest paths (but only one shortest distance). Thus, you might want to check, if the the question requires you to find one or all of them.


reduction from 3-SAT to Subset Sum problem

The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable.  The reduction below is lifted directly from the lecture notes found at https://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf .

  We reduce 3SAT to SUBSET-SUM. Consider a 3CNF formula with variables $x_1, . . . , x_n$ and clauses $c_1, . . . , c_r$.  For each variable $x_i$, we will have two numbers $y_i$ and $z_i$ in the list.  For each clause $c_j$, we will also have two numbers $s_j$ and $t_j$.  We define all of these numbers by specifying their base 10 representations.  The construction is best explained by an example and a picture.

  If the formula is $(x_1∨x_2∨\overline{x_3})∧(\overline{x_1}∨x_2∨\overline{x_3})$, then the base 10 representations of the numbers will look like this:

  \begin{array}{c|ccc|cc}
 & x_1 & x_2 & x_3 & c_1 & c_2 \\
\hline
y_1 & 1 & 0 & 0 & 1 & 0  \\
z_1 & 1 & 0 & 0 & 0 & 1  \\
y_2 & 0 & 1 & 0 & 1 & 1  \\
z_2 & 0 & 1 & 0 & 0 & 0  \\
y_3 & 0 & 0 & 1 & 0 & 0  \\
z_3 & 0 & 0 & 1 & 1 & 1  \\
\hline
s_1 & 0 & 0 & 0 & 1 & 0  \\
t_1 & 0 & 0 & 0 & 1 & 0  \\
s_2 & 0 & 0 & 0 & 0 & 1  \\
t_2 & 0 & 0 & 0 & 0 & 1  \\
\hline
k & 1 & 1 & 1 & 3 & 3 \\
\end{array}

  The number $y_i$ corresponds to the positive occurrences of $x_i$ in the formula while the number $z_i$ corresponds to its negative occurrences.  It should be clear how to generalize this construction to an arbitrary 3CNF formula.  And the list of numbers can clearly be constructed in polynomial time.  We claim  that  a  subset  of  these  numbers  adds  to  exactly $k$ if  and  only  if  the  formula is satisfiable.  A key point is that the sum of the numbers can be done column by column,  independently,  because  carries  will  never  occur.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else.  The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula.  Note that the required sum $k$ has a one in each digit position corresponding to the variables.  This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both.  Note also that sum $k$ has a three in the digit position corresponding to each clause.  The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values.  All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.


How to compare an experimental study with amortized times

If you want to compare theory and experiment, you have to perform both analyses under the same assumptions.

Note that this includes what you measure. Since you did not analyse time in theory, there is little sense in measuring running times in the experiments. Use combinatoric measures you can count reliably and independently of the system and its load.


"Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)

Natural reductions are a special case of Karp reductions, with an extra condition stating that the output's length depends only on the input's length (and not structure). This concept can be applied to many forms of many to one reductions, so I guess you could talk about natural logspace reductions.

Obviously a karp reduction can be non-natural (otherwise the definition would be of no use). Think about a reduction from clique to SAT, I can make it non natural by first checking whether the graph is planar, and in case the answer is yes output some fixed non satisfiable formula (suppose the parameter $k$ is greater than $4$). This breaks naturality, since now the output formula's length depends on the planarity of the input graph.

Finding an example of a "natural" non-natural reduction (even if a natural one is known) is harder, but I guess that if you go over enough reductions you will find one.


Is it really possible to prove lower bounds?

We can absolutely prove such things.

Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the algorithm on some input, we could observe that it never examined a particular element of the input. Changing that element to the minimum, we can get the algorithm to fail.

A less trivial lower bound is the $\Omega(n \log n)$ lower bound for sorting in the comparison-based model. The proof for that goes along the following lines: given an input of $n$ numbers, there are $n!$ possible outputs (the input could be any permutation of the sorted list, so the output can also be any permutation of the input). If we are limited to only doing comparisons, then our algorithm (on average) needs to perform at least $\log_2(n!)=\Omega(n \log n)$ comparisons in order to be able to give $n!$ different outputs.

Lower bounds can be even stronger. There are several problems (notably the $EXPTIME$-hard problems) for which there is an exponential lower bound. Problems in this class include computing optimal strategies for games such as (generalized) chess, checkers and go. The proof of this is via the Time Hierarchy Theorem, which states (subject to some restrictions on $f$):

  Given a function $f$, there exists a computational problem that can be solved in time $O(f(n))$ but can not be solved in time $o(\frac{f(n)}{\log n})$.

So basically, if you can think of a function $f$ there exists a problem that requires that much time to solve.

Finally, another avenue of not necessarily proving a time lower bound but something even stronger is showing the undecidability of a problem (e.g. halting, post correspondence).


Sorting array with at most two inversions

To show that the optimal number of comparisons is $m$, you have to prove that any algorithm that uses $m-1$ comparisons must make a mistake on some arrays. The usual way to accomplish that is through an adversary argument – you "react" to the queries of the algorithm in a specific way, and ensure that after $m-1$ steps, there are two different linear orders that are consistent with your answers to the queries (as well as comply with the constraints – in this case at most two inversions).


When reading the row then bits are amplified and sent back on the line as part of the feedback circuit. The bits are also stored in a small chunk of SRAM where they are cached for reads and writes.

writes to the rows don't happen immediately, only when unloading the data from the cache.

When unloading the cache the feedback circuit normally used to refresh the data is overridden with the new values in the row. All bits of the row are written.


NFA to accept strings where the third AND the third-last element are b

Hint. If $A$ is the alphabet, a regular expression for your language is $AAbA^*bAA \cup AAbAA \cup AbbA \cup bAb$.


Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning

With the help from a fellow friend I came to the following conclusion:

We know that we have to make $$n-1,n-2, \dots, 2,1 \text{ comparisons}$$

So when looking at the arithmetic series $$\sum_{i=1}^n k = \Theta(n^2)$$

We can conclude that $T(n) = \Theta(n^2)$.

Please comment if I can improve my answer in any way.