Maximizing the boolean combination of given real numbers with dependencies

It is often more natural to consider $b_i \in \{\pm 1\}$ rather than $b_i \in \{0,1\}$, and it is not difficult to convert your formulation to an equivalent one which uses $\pm 1$ variables rather than $0/1$ variables, using essentially the substitution $b'_i = 2b_i-1$. It is then possible to eliminate the linear term by adding a new variable $b_0$ and replacing $x_i$ with $x_{0i}$. The new problem can be formulated as:

  Maximize $x' M x$ over $\{\pm1\}^n$, where $M$ is a symmetric matrix with zeroes on the diagonal.

(We can assume without loss of generality that $M$ is symmetric and that its diagonal elements are zero, the latter since $(\pm 1)^2 = 1$.)

This problem is known variously as quadratic programming, binary quadratic programming, Boolean quadratic programming, unconstrained binary quadratic programming, and so on; only the first term is ambiguous, since it could also refer to the continuous version of the problem.

Binary quadratic programming generalizes MAX-CUT, and so is NP-hard. In general it is (almost) NP-hard to approximate to within any constant factor, see for example On Non-Approximability for Quadratic Programs by Arora et al. For an up-to-date survey taking a more practical perspective, see The Unconstrained Binary Quadratic Programming Problem: A Survey by Kochenberger et al.


Convert propositional logic formulas to mathematical constraints

Functions which can be described using a single constraint are known as halfspaces or linear threshold functions. They are also the functions computable using a single threshold gate.

Checking whether a function of this form exists is a linear programming problem: you look for a set of weights $w_1,\ldots,w_n,C$ such that if $f(x_1,\ldots,x_n) = 1$ then
$$ \sum_i w_i x_i \geq C + 1, $$
and if $f(x_1,\ldots,x_n) = -1$ then
$$ \sum_i w_i x_i \leq C - 1. $$

More efficient algorithms exist. For example, Maass and Turán gave a famous such algorithm in their paper "How fast can a threshold gate learn?".


Yes, you can check equivalence in polynomial time (in fact, in quadratic time).
By similar logic to my answer to your previous question, it suffices to test satisfiability of $\phi_1 \land \neg c$ where $c$ ranges over the clauses of $\phi_2$.  If any of these are satisfiable, then $\phi_1,\phi_2$ are inequivalent.  Otherwise, if they're all unsatisfiable, and the same for $\phi_2 \land \neg c'$ where $c'$ ranges over all clauses of $\phi_1$, then $\phi_1,\phi_2$ are equivalent.
So, let's investigate how to test satisfiability of $\phi_1 \land \neg c$ where $c$ is a clause of $\phi_2$.  By assumption, $c$ is a Horn clause, so it has the form $\neg x_1 \lor \dots \lor \neg x_k \lor x_{k+1}$.  So, $\phi_1 \land \neg c$ has the form
$$\phi_1 \land x_1 \land \dots \land x_k \land \neg x_{k+1}.$$
This turns out to be a Horn formula, so you can its test satisfiability with the standard algorithm for testing satisfiability of Horn formula.  This takes linear time per clause, and there are linearly many clauses, so the total running time is quadratic.


Problem with understanding proof of the Space Hierarchy Theorem

Apparently, there is a misunderstanding of the original proof from Sipser's book Introduction to the Theory of Computation that's been erroneously duplicated in a couple of sources including Wikipedia and Berkeley's CS172 lecture notes.

Namely, Sipser defines the language in terms of a TM $M$ that

takes an encoded machine description $\langle M' \rangle$
simulates $M'$ on input $\langle M' \rangle$ on a tape bounded by $f(|\langle M' \rangle|)$
inverts the answer, if the machine stops.

The resulting $L(M)$ is different from

$$ L = \{ \langle M \rangle: M\text{ rejects }\langle M \rangle\text{ using }\leq f(|\langle M \rangle|)\text{ space}\} $$

because $M$ rejects $\langle M \rangle$ due to recurrent simulation that requires infinite space and therefore $\langle M \rangle \notin L(M)$ and $\langle M \rangle \in L$ from the definition of $L$.

As a result, in the diagonalization argument we should replace references to the definition of $L$ with references to the acceptance of $M$, which breaks the argument for $M$ itself.


Prove that the Kolmogorov complexity function cannot be approached from below

We can computably approach $K(x)$ from above by trying all programs. Since $K(x)$ is not computable, we cannot computably approach it from below — otherwise it would have been computable.


SVM with a priori information about class probabilities

SVM doesn't take into account that prior knowledge about the distribution of the classes, so if you want a classifier that takes advantage of that, you'll need a different classifier.

In particular, if you know the distribution of each class and the priors (class balance), you can use Bayes rule to classify each point directly, without needing any fancy classifier.  This is the optimal (most accurate) way to classify, is not hard to implement, and doesn't require any training set.

If you know that each class has a bivariate normal distribution but you don't know its parameters (mean and covariance matrix), you can use the training set to estimate these parameters, then use Bayes rule.


Lower bounds of calculating a function of a set

You have to be specify the model of computation and properties of $f$. In the following argument I will state the assumptions that I need. It can be generalized a little bit further but I think it should be sufficient to give you the idea.

Assume that the machine $M$ never reads the value of one of the members of $A$ (a fixed set, and $A$ is given as a list). Assume further that $A$ is an input such that changing the value of its $i$th member does not change $M$'s answer. Assume further that $f$ is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

We can use an adversary argument to show that the machine cannot compute the right answer by changing the value of that member of $A$ to obtain $A'$ else s.t. the value of $f$ is different. The value of $M$ on these two sets is the same, so one of them must be false and therefore $M$ cannot compute $f$ correctly.

Therefore any machine $M$ that computes $f$ will need to read all of the input which takes $\Omega(n)$ steps.

(On the other hand, assume that we have a nondeterministic random access machine, and we want to compute OR of the bits in the input. We can nondeterministicly guess a bit and check if that is 1, if it is 1, we output 1. This machine reads only a single bit of the input in $O(\lg n)$ steps and correctly answers the problem. So without assumptions on $M$ and $f$ the result does not hold.)


Describing the Bool-And monoid in terms of categories

Monoids are one-object categories. The elements are morphisms, monoid multiplication is composition and the monoid identity is the identity morphism.

In the case of Booleans-with-AND the monoid is $M = (\{\top, \bot\}, \land, \top)$. The category therefore has a single object (we could call it $M$) with two morphisms $\top : M \to M$ and $\bot : M \to M$. Composition is given by $\land$ and the identity morphism is $\top$.

To give a little more context, there is a way to view a monoid in such a way that the objects are the elements of the monoid: as a discrete (no non-identity morphisms) monoidal category. Category Theory for Programmers covers the topic of monoidal categories in Chapter 22, "Monads Categorically".


Decidablity of Languages of Grammars and Automata

Convert G to Chomsky Normal form. This way, the only empty derivation would be the start symbol that does not appears anywhere else and thus if there is some production that may able to eventually generate itself, then the grammar is infinite. If no such production exists, each symbol will only be able to generate a finite set of strings, and then the grammar is finite. So, build a directed graph where each production is a node and each symbol inside a production is an edge targeting that symbol. If the graph has some cycle, the CFG is infinite, otherwise it is not. Hence a Turing machine for $FINITE_{CFG}$ could be construct doing exactly that, and then $FINITE_{CFG}$ is decidable.
Suppose that $FINITE_{TM}$ is decidable. Lets say that $H$ is a Turing machine that has some string as input and uses itself as an input to $FINITE_{TM}$. If $FINITE_{TM}$ returns true (i.e, $H$ accepts only a finite language), then $H$ accepts the input, which leads to a contradiction since the input set is infinite (the input's length is unbounded, so accept any possible string as input means accepting an infinite set of strings). If $FINITE_{TM}$ returns false (i.e $H$'s language is infinite), then $H$ rejects the input, meaning that $H$'s language is finite because it does not accepts any input (i.e. its language is empty), which leads to a contradiction too. This way, the supposition that $H$ exists leads to contradiction, and this supposition is based in the supposition that $FINITE_{TM}$ is decidable. So, by contradiction, we have that $FINITE_{TM}$ is not decidable.

  The same source also proves that a Context Free Grammar can be converted to a regular expression, and vice versa.

I really doubt that Sipser would state that, you probably misread or misunderstood. This would mean that context-free grammars generate exactly the same langauges as right-linear grammars. This is false; the right-linear grammars generate are a proper subset of the languages context-free grammars dp. That said, the way you tried to use regular languages to answer the questions just leads you to nowhere.

As you can see above in my proofs, the two questions are indeed two very distinct, unrelated questions. It just happens that they were worded similarly.


Help with finding a flaw in argument simulating large Turing machines with smaller ones

Your flaw seems to be here:

  Now, $K(n)$ is at most $O(\log(n))$.  $k$ is about $n^n$, so $K(k)$ is at most $O(n)$.  That puts $m_2$ just slightly larger than $n$.

It's true that $k$ is about $n^n$ (more precisely, $k = n^{\Theta(n)}$ or $k = 2^{\Theta(n \log n)}$, and this can be shown by upper bounding $k$ by the number of Turing machines, and lower bounding by finding a family of simple halting Turing machines). However, that doesn't imply that $K(k)$ is at most $O(n)$.
Rather, we only know that $K(k)$ is at most
$$
O(\log(n^n)) = O(n \log n).
$$

Your contradiction relies on picking $k$ so that $K(k)$ is $o(n)$ (a bit smaller than $n$). Your reasoning shows that this is impossible.

But this is not too surprising: most $k$ we expect to be about $O(n \log n)$, and $k$ is a number that holds a lot of information about Turing machines with $n$ states, so we don't expect to be able to compress such a number to smaller than $O(n)$ states itself.

P.S. Putting aside the question of whether Python is really equivalent to Turing machines (probably no one knows, as it hasn't been formally shown), your program M1 is in fact clearly expressible as a Turing machine. From this, you should be able to see that the resolutions based on M1 not being expressible as a Turing machine are not correct.


Computer Vision - Algorithm for reconstructing tilted image

It detects 4 markers lying on the corners of the note. One of the markers is unique to able to determine the orientation. Because the actual size and layout of the form is known, a perspective warp can be computed, bringing the scanned image to a canonical (fronto-parallel) form. Then, OCR is carried out in the region where date and time is expected. The rest of the content are taken as image and saved on the smartphone.

For OCR, character segmentation and classification might be your key words.
For Marker Detection, generally black-white polygonal regions are detected and expected to be quad-formed. The rest of the blobs are filtered out and you end up with the markers.


Applying Johnson's algorithm on undirected graph with negative edge weights

Shortest simple paths

Finding the length of the shortest simple path is NP-hard, so there is no efficient algorithm.

Shortest paths (not necessarily simple)

The original version of the question didn't include the requirement that the path be simple.  Below I include my answer to that version of the question, for posterity:

Decompose the graph into connected components.  Solve the problem separately for each connected component.

If there is an edge with negative weight in the component, then for all pairs of vertices $u,v$ in the component, the distance from $u$ to $v$ is $-\infty$.  So, you can output $d(u,v)=-\infty$ for all pairs $u,v$ in the component.  You don't even need to run Johnson's algorithm.

(Why is that answer correct?  Well, suppose the edge $(a,b)$ has negative weight.  Then consider a path $u \leadsto a \to b \to a \to \cdots \to b \leadsto v$.  Such a path can have arbitrarily small length, by traversing the cycle $a \to b \to a$ sufficiently many times.)

If there is no edge in the component with negative weight, you can use Johnson's algorithm to compute the distance between each pair of vertices in the component.  Johnson's algorithm on this component will work fine, since this component has no negative-weight edges.

Finally, the distance between any two vertices that are in different components is $+\infty$, since there is no path between them.


Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1.

You can build a directed graph with $n$ nodes and an edge from node $n_i$ to node $n_j$ if $n_i = j$, i.e. the target position of $n_i$ is $j$ (skip nodes that are already in the correct position). The resulting graph contains one or more distinct cycles.

You can arrange the cycle containing the zero following the arcs in the reverse direction, then "jump" to another cycle and arrange it; the "entry point" doesn't matter.

In the example of the figure above the swap number is zero and the target permutation is $0,1,...6$; after completing the first cycle (blue one) you must enter the second cycle (red one) in order to complete it; if $(n_i \rightarrow n_j)$ is a directed arc of the second cycle, then it must modified in $(n_i \rightarrow 0 \rightarrow n_j)$. The "entry point" is irrelevant (the number of swaps needed to arrange the second cycle doesn't change). You can also interpret the swaps on a cycle like a shift of its numbers.

The procedure always ends with the sorted array (after arranging a cycle, its numbers are never moved again). If there are $m$ cycles and the $i$-th cycle has $p_i>1$ numbers that needs to be arranged and cycle 1 contains the number used for the swaps, the total number of swaps is $(p_1-1)+(p_2+1)+...+(p_m+1)$. If the number used for the swaps is already in place the number of swaps is $(p_1+1)+(p_2+1)+...+(p_m+1)$. To prove that the number of swaps used is optimal, you can observe that every number of each cycle must be moved (requires a swap), and there is no way to move a number of a cycle without "moving" the zero on that cycle.


How to determine approximability of a problem when we don't know how good a solution is?

Definition of a well-formed optimization problem

It seems to me the core problem you have here is that the problem you have defined is not what I'd call a well-formed optimization problem.  Normally, an optimization problem looks something like this:

Input: $x$
Goal: find $y$ that maximizes $\Phi(x,y)$

where $\Phi$ is some objective function that's specified as part of the problem statement.  The key point here is that the objective function has to be computable, as a function of the input and the proposed output.

Your proposed formalization of the WSN localization problem does not have this form: the objective function is not computable as a function of the information known to us.  Therefore, it is not a well-formed optimization problem.

This explains the problem you're having.  The reason you can't compare how good different solutions are is that you don't have a computable way to measure how good a single solution is, given the information available to you.  Consequently, your problem does not fit into the standard framework of optimization problems and approximation algorithms.  This means you can't take advantage of all that theory, and strange things can happen.

So, at this point you have two options.  First, you can try to formulate your problem as a way that does qualify in this framework, i.e., where you do have a computable objective function.  The other option is to accept that you don't fit into this framework and you'll have to develop everything from scratch without being able to use the existing framework as is.

Another way to put this: if your objective function depends on values that aren't known (aren't part of the input), then what you haven't is not purely an algorithmic problem.  To make this an algorithmic task, you need a way to measure success.  One candidate way to do this would be to establish some probability distribution on the locations of the sensors, then frame this as a statistical inference problem, where you want to find the maximum likelihood estimate, or something like that.

Another approach would be to choose a different objective function, that is computable.  For instance, maybe you could evaluate the accuracy of a solution in terms of how closely it matches the givens: for what fraction of edges $\{v,v'\}$ do we have $||v_\text{est}-v'_\text{est}|| < R+\varepsilon$, and what fraction of non-edges $v,v'$ do we have $||v_\text{est}-v'_\text{est}|| > R-\varepsilon$; maybe the objective function is the sum of these two fractions, or something.  Of course, this is a different objective function, so it's maximizing something different, and the solution to that optimization problem might or might not match what you're actually looking for.

For posterity, here's some feedback on an older version of the problem, which has now been addressed by the revised question.

I see some misconceptions in this question, both about how we measure the quality of approximations, and about when approximation algorithms are applicable.  The best answer I can give is to clear up these confusions/misconceptions; that will help you think about this kind of problem more clearly.

Definition of the approximation ratio

You have a confusion about how we normally measure the quality of an approximation, in the standard theory of approximation algorithms.  This shows up in your discussion of approximation algorithms for subset sum.

With subset-sum, the objective function we are maximizing is $\text{sum}(B)$.  In the standard theory of approximability, we measure the quality of an approximation by how good the value of $\text{sum}(B)$ is, compared to the optimal value of that for the optimal choice of $B$ -- not compared to $t$.

When we ask whether there is a $2$-approximation for subset-sum, we ask whether there's an algorithm that outputs a set $B_\text{approx}$ such that

$${\text{sum}(B_\text{approx}) \over \text{sum}(B_\text{opt})} \ge 1/2,$$

where $B_\text{opt}$ is the optimal solution (the one that maximizes $\text{sum}(B)$).  The ratio on the left-hand-side is called the approximation ratio.  Notice how $t$ doesn't appear in this quantity.  The approximation ratio is defined with reference to the optimal solution, not with reference to $t$.

When approximation algorithms are applicable

Approximation algorithms are only applicable to optimization problems.

The "WSN localization problem", as you have defined it, is not an optimization problem: it is a decision problem.    Since it's not an optimization problem, the entire concept of an approximation algorithm doesn't enter into it.

Asking "is it approximable?" is a category error: it's like asking "Is 'flying' a mammal?" -- 'flying' isn't even a noun, let alone an animal.

You then talk about two metrics.  If you pick one of those metrics, you could define an optimization problem that is based upon the "WSN localization problem", where you ask to find the placement of node positions that complies with all the constraints and that maximizes (or minimizes) that metrics.  Then you would have an optimization problem.

However, when you have two metrics, we don't get a well-defined optimization problem, since it's not clear what would count as optimal.  Indeed, there might be multiple solutions that each achieve a different tradeoff between these two metrics, and is "Pareto-optimal".  (See also What is a bicriteria approximation algorithm?.)

So, to count as an optimization function, you have to be maximizing/minimizing a single objective function; the standard theory of approximation algorithms is only applicable when you have a problem that is of this form.  If your problem isn't of this form, it probably doesn't make sense to ask if it is approximable, as standard definitions of approximability don't apply.


Use machine learning algorithms data structure to store information (memory)

ML algorithms are definitely capable of storing information. Generally, any ML algorithm can be trained to remember a set of data. This is commonly referred to as overfitting and something that most ML researchers try very hard to avoid.

Also feature learning
 and compression are common themes in ML. In this case, the goals are actually to find efficient ways to represent the data. This allows to store information efficiently. Because you asked for some illustrative papers: image compression with autoencoders, image compression with PCA, ...

Methods like generative models are probably also interesting as their purpose is to discover the distribution of some data in order to generate new data. This technique can be used to generate new images that are not just random noise for example.

These are just some examples with some random papers that are top hits when searching for the terms I mentioned. Probably every machine learning algorithm can be said to store some sort of information, but for some models the stored information is more useful/meaningful than for other models.

Generating pi with machine learning has probably not been done (at least it has not been published). However, nothing keeps you from trying it out. You could try to overfit a model to learn digits of pi or you could just try what happens when you feed an LSTM with a very large sequence of pi-digits (you would have to find a reasonable objective, but might be interesting), or do some sequence to sequence learning with encoders and decoders to predict digits for pi. Probably, the methods would not perform well from a ML perspective, but some interesting things might happen.

PS: as you might have noticed, I have mentioned quite some neural networks. There are other methods out there as well: do not get too biased.


What's harder: Shuffling a sorted deck or sorting a shuffled one?

By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small.

Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.


This is a knapsack problem. In the most basic version, you have a single resource (e.g., space in your knapsack) and you're trying to choose which items to put in it so you can carry the greatest value. People have also studied multi-constraint knapsack problems, which is the variant you're directly asking about.

The bad news is that knapsack problems are, in general, NP-complete. The good news is that they can be solved in pseudopolynomial1 time using dynamic programming, which is often practical.  They can also be approximated fairly well: for any fixed $\varepsilon$, there is a polynomial time algorithm that will give you the answer to within a factor of $1\pm\varepsilon$. However, the dependence on the running time is superpolynomial, unless P$\,=\,$NP.

1 Pseudopolynomial time means that the running time is a polynomial function of the numbers represented in the input, whereas polynomial time means the running time is a polynomial function of the size of the input in bits. For example, the algorithm read n; for i=1 to n do print "hello"; end is pseudopolynomial: if its input is $n$, it performs $n$ iterations but, if the input is written as a $b$-bit binary number, then $n$ could be as big as $2^b$, so the algorithm isn't truly polynomial.


Polynomial time reductions between two problems

You can reduce from $B$ to $A$ by setting $f(F) = (F \neq F^{'})$ where $F^{'}$ is $F$ with every variable replaced with its negation. Equally, you can reduce from $A$ to $B$ by setting $f(F) = F$, because every variable assignment, and its negation, will be false.


Concrete example of an admissible A* heuristic compared to Djisktra

In other words, Djikstra is a form of A* where the heuristic always returns the actual distance.

This is wrong.  Dijkstra's is a form of A* where the heuristic is always 0.
Dijkstra's algorithm is essentially the weighted-graph version of a breadth-first search.  It simply spreads out from the start node in all directions until it researches the end node.  It could spend a lot of time searching paths that are going in the complete opposite direction of the end, because it doesn't know anything about the global properties of the graph.
That's where the heuristic comes in.  Since we know the approximate direction of the end, we can prioritize searches that move in that direction.  In a 2D graph, for example, this would mean prioritizing searches that are closer to the end from a bird's-eye view.
The heuristic is added to the total distance so far to determine which nodes to consider next.  If the heuristic is 0, then we're only using the distances known so far, meaning we don't prioritize any direction and we get Dijkstra's algorithm again.  However, if it's non-zero, we do prioritize certain directions, which hopefully leads to us reaching the end sooner.
Note that the heuristic is just an estimate, not the actual distance to the end.  In fact, it's more than an estimate - it's a lower-bound to the actual distance (that's what "admissible" means).  In our 2D example, our heuristic is the bird's-eye view straight-line, which is the shortest possible path between two points.  Adding obstacles will never decrease this path length, only increase it.


Why is Iterative-deepening A* optimal, even without monotonicity?

In a nutshell: IDA* traverses all paths of lengths iteratively larger and it stops only when expanding (as opposed to generating) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.

Now, how can we achieve that? It is simple. Get rid of the condition of monotonicity and pay attention instead to the condition of admissibility, i.e., $h(n)\leq h^*(n)$ where $h(n)$ is the heuristic estimate to reach the goal $t$ from node $n$ and $h^*(n)$ is the optimal cost of reaching the target. In other words, all that is required is that we have a function (i.e., $h(n)$) which provides a lower bound on the cost-to-go.

In the following bear in mind that IDA$^*$ is nothing more and nothing less than a depth-first search algorithm which prunes children that exceed a particular $f(n)$ value. As in the case of A$^*$, $f(n)=g(n)+h(n)$ where $g(n)$ is the cost of the path from the start state $s$ to $n$. All we have to do is to decide how to handle $f(n)$ while achieving our goal ...

Step 1: Since we have a lower bound to reach the goal, start IDA$^*$ with a threshold equal to $h(s)$, the heuristic estimate of the start state. This simply amounts to traverse all paths stemming from $s$ until a node $n$ is found such that $f(n) > h(s)$. This operation is necessarily finite in locally finite graphs (i.e., with bounded branching factor). While generating paths, note that you stop at those nodes $n$ that meet the aforementioned condition so that you can easily save the minimum excess over $h(s)$
Step 2: Once the first step is over, you know: first, no path of length $h(s)$ gets to the target; second, the next cheaper paths that can be traversed from $s$ have a cost equal to the minimum excess computed in the previous iteration. This is all you need. Proceed now as in Step 1 but using the minimum excess computed in the previous iteration as the threshold. If the iteration ended withouth success apply iteratively until getting to the solution.

Notice the remark I made in the first paragraph: from the behaviour of this algorithm, admissibility is guaranteed if you stop when expanding the goal node. This means that all paths of an inferior cost have been already traversed. If you ever stop when generating the goal, then you might incurr in suboptimal solutions since those paths might have a cost that exceeds the current threshold of that iteration.

In no place, consistency is required. From Steps 1 and 2, a proof of correctness can be easily derived by induction on the number of iterations.

Hope this helps,


Hint for 2: If $1,\ldots,i,j$ is a shortest path from $1$ to $j$ then $1,\ldots,i$ is a shortest path from $1$ to $i$.

Hint for 3: If $1,\ldots,i$ is a path from $1$ to $i$ then $1,\ldots,i,j$ is a path from $1$ to $j$.

In both cases $\ldots$ represents some list of vertices.


PAC learning: success of learning when receiving a sample from a different distribution

Let $x_1,...,x_N$ denote the elements of $\mathcal{X}$ and consider the marginal distributions $D_\mathcal{X}=(p_1,...,p_N)$ and $G_\mathcal{X}=(q_1,...,q_N)$. Recall that $p_i>0$ implies that $q_i>0$, hence the ratio $R=\max_i\frac{p_i}{q_i}$ is well defined. Also denote the output of the algorithm on a sample set $S$ by $h_S$, then:
\begin{align*}
err_G(h_S)&=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim G}[h_S(x_i)\neq y | x=x_i]=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&=R^{-1}\sum\limits_{i=1}^N q_iR\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\ge
R^{-1}\sum\limits_{i=1}^Np_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&=R^{-1}err_D(h_S)
\end{align*}
Thus, to show $err_D(h_S)$ is small with high probability when given samples from $G$, it suffices to show that $err_G(h_S)$ is small and using the bound $err_D(h_S)\le R \cdot err_G(h_S)$ where $R$ is a constant depending on the distributions. This is the standard problem of showing that the ERM is able to learn a finite hypothesis class, so I leave the details to you.


Random restarts for unsatisfiable instances

There is some research in this area.  In The Effect of Restarts on the Efficiency of Clause Learning Jinbo Huang shows empirically that restarts improve a solver's performance over suites of both satisfiable and unsatisfiable SAT instances.  The theoretical justification for the speedup is that in CDCL solvers a restart allows the search to benefit from knowledge gained about persistently troublesome conflict variables sooner than backjumping would otherwise allow the partial assignment to be similarly reset.  In effect, restarts allow the discovery of shorter proofs of unsatisfiability on average.


What does Bellantoni-Cook say about Cook-Reckov?

A polynomially bounded proof system is a function $M$ computable by an FP machine with the following properties:

For any $x$, the output $M(x)$ is a propositional tautology.
There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

Now suppose that you found a sophisticated way to describe all functions in FP, call it System R. This lets you come up with the following equivalent definition.

A polynomially bounded proof system is a function $M$ expressible in System R with the following properties:

For any $x$, the output $M(x)$ is a propositional tautology.
There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

As you can see, nothing has really been gained. We only changed "computable by an FP machine" with "expressible in System R".


Can all types of computational problems be modeled as decision problems?

Yes.  Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$.

Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1.  If you can solve that decision problem, you can solve the original computation problem.

(Strictly speaking, you also need a way to decide whether the length of $f(x)$ is $i$; that can be addressed by defining the decision problem as taking inputs $x,i,b$; if $b=0$, then the problem is to determine whether the $i$th bit of $f(x)$ is 1; if $b=1$, the problem is to determine whether the length of $f(x)$ is $i$.)


A non-regular language satisfying the pumping lemma

You are not supplying the definition of $L$, so here is one definition which works:

$$ L = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 1 \text{ and } w \in \Sigma^* \text{ doesn't start with $a$} \}. $$

Choose a pumping length of $2$. A word $ab^nc^n \in L$ can be pumped by pumping the $a$ part. A word $aaw$ can be pumped by pumping the $aa$ part. Finally, a word $bw$ or $cw$ can be pumped by pumping the $b$ part or $c$ part.

Your definition seems to be

$$ L' = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 2 \text{ and } w \in \Sigma^* \}, $$

but for this language the pumping lemma does work. Indeed, apply it to $ab^nc^n \in L'$ for large enough $n$. Then $ab^nc^n = xyz$ so that $|y| \geq 1$ and $xy^iz \in L'$ for all $i \geq 0$. Considering the case $i = 2$, we see that $y = a$ necessarily. But then, taking $i = 0$ we get $xz = b^nc^n \notin L'$.

Perhaps the exercise meant you to use the version of the pumping lemma in which $i \geq 1$ instead of $i \geq 0$.

We can show that $L$ is not regular in many ways:

Use one of the many general versions of the pumping lemma which can force the $b^nc^n$ to be pumped. For example, the general version on Wikipedia states that there exists $p$ such that any word $uwv \in L$ with $|w| \geq p$ can be partitioned as $w = xyz$ so that $|xy| \leq p$, $|y| \geq 1$ and $uxy^iz \in L$ for all $i \geq 0$. Choose $u = a$, $w = b^nc^n$ for $n \geq p$ and $v = \epsilon$, and follow the usual argument.
If $L$ were regular then $L \cap ab\Sigma^* = \{ ab^nc^n : n \geq 1 \}$ would also be regular, and you can prove that it isn't using the usual pumping lemma.
Use the Myhill–Nerode criterion. The words $ab^n$ are pairwise inequivalent, and so $L$ is not regular.


Transform regular grammar in linear grammar

A (right) regular grammar is one in which all production rules are of one of the following:

$$B \rightarrow a$$
$$B \rightarrow aC$$
$$B \rightarrow \lambda$$

Where $B$ is a non-terminal, $a$ is a terminal and $\lambda$ is the empty word. A regular grammar is a grammar which is either right-regular xor left-regular. As you have said in a linear grammar one does not require the nonterminals to appear on the far side of the right of the production rules. Therefore, every regular grammar is already a linear grammar.


How does O transform this sum like that?

Intuitively, the $O$ can swallow any constant factor. Here, we do so because the sum we get is on the cheat sheet and we can proceed more easily.

Formally, we need to apply the definition of $O$, once in either direction. I do not think the first term makes a whole lot of sense. What the authors probably mean is

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)$

with some $f \in O(h)$. Then it remains to note that

$\qquad\displaystyle \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot f(h)
  \quad\leq\quad \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} \cdot c \cdot h
  \quad=\quad \frac{c}{2} \cdot n \cdot \sum_{h=0}^{\lg n} \frac{h}{2^{h}}$

for all $n \geq n_0$, with $c,n_0$ the constants from $f \in O(h)$ (unfold the definition).
Applying the definition again concludes the proof.

Note that if we had $f \in \Theta(h)$, we would get a similar lower bound and could thus show a $\Theta$-bound for the sum.


Just, replace the constant $K = 2^3$, and you have to use this constant for your proof.

$$ 2^{n+3}  = K\times 2^n$$

So, $O(2^{n+3})  = O(2^n)$.


How to determine whether a dependent type that doesn't fit the monad instance is categorically a monad

So, there are potentially many answers to this sort of question. One is that there are many possible categories on which there can be monads. The rules for establishing that something is a monad will ultimately be the same, but the details will differ depending on the specific category chosen. So, since there is a natural number index involved, perhaps a monad on a category of natural number indexed types is in order, although your presentation is not precisely that. Or, perhaps you can also quantify over the natural number to get a monad that is the 'total space' of all the individual fibers. (It's also not clear to me why you need the index in this example, unless Idris has a feature that makes the type small because of it.)

However, another answer is that whether something 'is a monad' is kind of the wrong thing to worry about. Especially with examples like this, what is going on is that we are constructing the 'free algebra' of some embedded language we want to work with. Monads show up because they are one of the ways that algebra is dealt with in category theory. So because we're doing algebra, we can phrase it in terms of (a particular construction of certain) monads. But it can also be presented it in other ways as well.

The presentation you're using originates in Haskell (I think), and it's convenient there, because of impredicativity and no concern for logical consistency/termination. You can easily write down the, 'free monad over a type operator.' It's also convenient because Haskell has features that make things presented as Monad nicer to use than other presentations.

However, if Idris is not (as) accepting of definitions like that, it seems sensible to re-evaluate whether some other presentation that is accepted can encode all the things you want. For instance, there are ways of specifying strictly positive functors in more obvious ways, which give rise to e.g. W-types:

data W (A : Type) (B : A → Type) : Type where
  con : (a : A) → (y : B a → W A B) → W A B

and it's possible to construct free monads based on this:

data Free (A : Type) (B : A → Type) (X : Type) : Type where
  pure : X → Free A B X
  branch : (a : A) → (B a → Free A B X) → Free A B X

This is the free monad over the polynomial functor given by A and B (the A-fold sum of B a-fold products of X). But this is by no means the only option.

So, it seems to me that unless there is some syntax sugar or similar reason to prefer a particular solution (or you have other reasons), it's better to worry about whether you have built the algebraic structure you wanted in a way that is easy to use for whatever you actually wanted to use it for, and not whether it adheres to some particular way of doing it that works well in a different language.

And to loop around, if the size is just there for getting everything to termination check, maybe it also doesn't matter if it's any actual notion of monad from category theory. If you erased the sizes and it fit the definition of a normal monad, and the sizes are only there for book keeping, maybe that's good enough (as long as it doesn't obstruct you in more practical ways).


Every finite directed graph in which every vertex has outdegree at least 1 has a cycle. This is a nice exercise. Thus, even if you look only at edges labeled by a particular symbol, you will find a cycle in every DFA.


Complexity classes pertaining to listing all solutions?

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their own time and space complexities (perhaps entropy, too). In the general spirit of complexity, there are often trade offs between these to consider.

The precomputation step performs some work that is necessary before the first solution is enumerated. This might involve finding the solution itself or initializing some large data structure that will reduce the overall delay between each solution.

The delay is the resource cost associated with the computation necessary in between arbitrary enumerated solutions. In other words, the delay is a measure of the space and time needed to produce the $i+1^{th}$ solution after the $i^{th}$ one. Problems whose solutions that take $O(1)$ time for each enumeration are said to have constant delay. A requirement of $O(poly(n))$ time is said to have polynomial delay.

For the enumeration problem you specifically mentioned in your question, you should look into the class $ENUM_{NP}$ and its related siblings in section 2.1 of "Enumeration: Algorithms and Complexity" by Johannes Schmidt (Linked at the bottom).

Why do we care about precomputation time and delay?

Delay is very key to understanding the true intricacies of enumeration problems. Enumerating the elements of $\Sigma^*$ (up to size $n$) and $\{ \vec{x} : \phi(\vec{x}) \}$ where $\phi(\vec{x})$ is a Boolean formula (i.e. SAT) both take exponential time. However, enumerating through $\Sigma*$ only requires constant delay since you can just go through the elements in some order. For all we know, the delay for enumerating solutions to a 3SAT instance could be exponential. Our job as complexity theorists is to capture why the latter problem is fundamentally harder (more complex) than the former one. Delay does a pretty good job at showcasing this difference.

Likewise, we also need to know how much precomputation is done. We can reduce the delay for any enumeration problem to constant time and space by precomputing all solutions and storing them in a list to be enumerated at a later time. The challenge is to find the best balance between the two resources.

The order in which you enumerate the elements can also influence the complexity. Requiring results to be returned in a specified sorted order might require us to perform additional computation in both steps. Though situations where any order suffices (as long as each enumerated element is unique) are certainly studied, too.

As far as I know, these classes do not typically have concise labels (akin to $P$ and $NP$). We cannot feasibly expect to be able to do this since enumeration complexity classes are juggling around 3 or more resources (precomputation/total time, space, delay, and entropy). There are simply too many combinations of resource bounds to hand out special names. This does not make these classes any less interesting and also does not stop researchers from trying anyways.

Resources

This survey (really an attempt at formalization) should help you get started. It also proves some basic hierarchy theorems.

Enumeration: Algorithms and Complexity
(Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

For an enumeration of results in enumeration complexity, check out this compilation curated by Kunihiro Wasa. Since it is categorized by problem type, you can easily find a number of papers dedicated to enumerating graph cycles. It should be simple to modify the algorithms involved to only consider cycles with a given node.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html


Minimum variable size if the information are coded in non-binary system

One hexadecimal digit contains 4 binary digits. You can compute this as follows: $\log_2 16 = 4$. Alternatively, $2^4 = 16$. So the minimal memory element will contain 4 bits' worth of information.

This also works when the number of states is not a power of 2, but you have to be more flexible in your interpretation.


What is the difference between Transitive Closure and Join?

No, it is not. Transitive closure is the closure of composition on binary relations; composition can be expressed as a rename (to make join operate on the right attributes), followed by a join, followed by a project to remove the common attributes.

So composition can be expressed in terms of join, but (as Erwin Smout says) its transitive closure can not, and join (or composition) cannot be expressed in terms of transitive closure, either.


Are all integers kept in 2's complement form in all microprocessors?

If there was the keyword "almost" attached to the question then answering it could have been much more easy. As people have mentioned in the comments that nothing can be said with certainty about "all" the processors but yes majority of them do.

2s compliment is definitely preferable over the 1s compliment as it provides you a better range for instance if you have 8 bits the you can represent numbers in the range -2^7 to 2^7-1 with it (1 bit being for the signed bit). its interpretation also is easy and quick for the processors.

However for floating point numbers most processors use a different strategy to save them efficiently. This post would fall short if I needed to explain about them but matter of fact they don't use 2s compliment they rather have the concept of exponential, mantissa and signed bit. And there are 2 commonly used variant of these known as the single precision and double precision floating point representation which are technically same and vary only by the range they can represent. If you want to read further about this you can visit https://steve.hollasch.net/cgindex/coding/ieeefloat.html (not my website, but the website explains the whole thing fabulously).

Let me know if I could help you further in this regard.


Best introductory "algorithms"/"more than just coding" comp sci book?

Check out From Mathematics to General Programming by Alexander Stepanov and Daniel E. Rose.

Beginning with the basics of number theory you progress up to dealing with content that is typically covered in a 3/400 level abstract algebra course (depending on the institution).


Here's a simpler grammar:
$$
S\rightarrow XY\\
X\rightarrow aXb\mid ab\\
Y\rightarrow cYd\mid cd
$$
The key observation in cases like this is that strings in the language consist of two pieces concatenated: $a^nb^n$ and $c^md^m$, each of which can be generated by a simple grammar.


Where does LL parser belong in the top-down parsers classification

First let's make some general remarks about nomenclature.  They are not all relevant here, but they may help you in the future.

not all authors are using the same precise definition.  Sometimes the differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors.  Sometimes authors give the definition they are using, but that's not always true.  Sometimes there are well accepted definition that you can take for granted in about any context, sometimes every group tend to have its own and you have to know of which group the author is a member. (Ask a Java and a ML programmer what polymorphism is)
Nomenclature are about classification.  Classification is emphasizing some aspects while ignoring other, even if you think it should be (For instance L. Cardelli and P. Wegner do not consider the static or dynamic aspect in their analysis of polymorphism)

Now you are somewhat lucky, as some of the terms here have quasi-universal definitions  (that is not that some are not using other one, especially in blogs and QA sites, but they are trying to intuit a definition from the terms instead of looking at the definitions given by text books).

A top-down parser is a parser which start from the start symbol, guess which production to use, and then repeat the process for a non terminal symbol.  If it is able to second guess its choice, it is also a back-tracking parser.  If it never second guess its choice, it is a deterministic parser.

A LL(k) parser is a deterministic top-down parser which will always determine the production to use for the left-most non-terminal not yet determined (that's what the second L means) and will consider only the text from left to right (that's what the first L means) and will never use more than $k$ terminal symbols not predicted.

Thus

  There are four types of top-down parsers:

  recursive descent backtracking
  recursive descent predictive
  table-driven with backtracking
  table-driven predictive.

deterministic seems more common than predictive but that division seems correct.  I'll emphasize the fact that the division backtracking/predictive characterizes the algorithm, while the division recursive/table-driven characterizes the implementation.  So although the classification is correct, it is mixing different aspects something which tend to introduce confusion.

  All top down parsers are LL

That is false.  Some are not deterministic (the recursive descent backtracking one of your first list).  Some are scanning the text from right to left (AFAIK, the only interest is academic here but it would not surprise me that there is someone somewhere which found a use for it).  Some are trying to determine the production to use for another non-terminal than the next one (it's a formalization of the good old find the next matching parenthesis before trying to parse what is between them).

  LL is usually a more efficient parsing technique than recursive-descent.

LL can be implemented as recursive-descent (and is the easiest way to do so), opposing the two does not really make sense to me.  Recursive/table driven is an implementation choice.  (I've written both, I'd use the table driven approach only as part of a parser generator but I'll never say they are different algorithms).

  LL parsers are also called predictive

This could be misleading.  They are not the only class of parser which could be called predictive.


Expected number of nodes in the independent set produced by a coloring algorithm on a graph with maximal degree $k$

As you've computed the probability of a node be in the dependent set is $\frac{1}{k}(1-\frac{1}{k})^k$. Hence, the expected number of these nodes is $n\frac{1}{k}(1-\frac{1}{k})^k$. As $\frac{1}{e} \leq \frac{1}{k}(1-\frac{1}{k})^k$, so the expected would be at least $\frac{cn}{k}$ (for $\frac{1}{e} \geq c$).

Hence, the expected approximation ratio is $\frac{cn}{k}$ over $n$.


Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem?

Your problem can be mapped to problem of finding minimal set of edges $F$ such that $G\backslash F$ is a DAG (each solution for your problem is a solution for this problem and vice versa). This problem is known as minimum feedback arc set problem and is one of Karp's 21 NP-complete problems


Why doesn't subset sum solution violate Exponential Time Hypothesis?

Given a 3SAT problem of size $n$, you can convert that to a subset sum problem of size $n^2$ (roughly).  Now you can apply the algorithm for subset sum to solve the subset sum in time $2^{n^2/2}$ (roughly).  Remember, the running time depends on the size (length) of the input, and here the size of the input will be $n^2$, yielding the $2^{n^2/2}$ figure.

That will give you an algorithm for solving a 3SAT problem of size $n$ in $2^{n^2/2}$ time (roughly).  But that's much worse than the naive algorithm, which takes $2^n$ time: $2^n$ is much smaller than $2^{n^2/2}$.  So this reduction does not contradict the exponential time hypothesis: it doesn't give you a way to solve 3SAT faster than $2^n$ time.


How to find greatest set intersection of at least a given cardinality?

Here is how to reduce clique to your problem. Given a graph $G = (V,E)$ and a number $\ell$, for each vertex $x$ let
$$
S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \neq x\right\} \cup \{ \{x,y\} : \{x,y\} \in E \}.
$$
In words, $S_x$ contains all edges in the graph touching $x$, and all edges not touching $x$, whether or not they're in the graph.

One can then show that for every set of vertices $A$,
$$
\bigcap_{x \in A} S_x = \left\{\{y,z\} \in \binom{V}{2} : y,z \notin A\right\} \cup \{ \{x,y\} : x \in A \text{ and } \{x,y\} \in E \}.
$$
In words, the intersection of $S_x$ for $x \in A$ consists of all edges in the graph touching $A$, as well as all edges not touching $A$ (whether in the graph or not). The size of this intersection reaches its maximum $\binom{|V|-|A|}{2} + \binom{|A|}{2}$ if and only if $A$ is a clique in the graph.

Choosing $k = \binom{|V|-\ell}{2} + \binom{\ell}{2}$, the graph contains an $\ell$-clique if and only if there are $p=\ell$ sets whose intersection contains at least $k$ points. The value of $n$ for this instance is $n = \binom{|V|}{2}$.


Does every DAG have at most one "universal source"?

Suppose towards a contradiction that a DAG $G=(V,E)$ on $n$ vertices has more than one universal source and let $u,v \in V$ be two distinct universal sources of $G$.
Since $\mbox{out-deg}(u)=n-1$, and $G$ contains no self-loops, vertex $u$ has edges towards every other vertex in $G$. In particular $(u,v) \in E$. As a consequence $\mbox{in-deg}(v) \ge 1 > 0$ showing that $v$ cannot be a universal source.


Maximum number of nodes connected when the link has a large buffer

You can have ten of them going at once.  If they're on a third of the time and you decree that, for instance, ten operate for twenty seconds, then the next ten, then the next ten, then you can have thirty of them total.

If you just focused on the max you'd think that you could only have ten (which would be the case if you weren't able to synchronize them, and thus couldn't rule out that they might all try to talk at once.)

By averaging over the available time you can get the same result without having to speculate about how exactly to schedule them.  Over its uptime, each node transmits at an average of 3+1/3 Mbps.  Dividing 100 MBps by this number gives 30.


Is there a language for which any string (that works) can be shown to not be pumped using the Pumping Lemma?

I'd say the language $L = $ { $0^n1^n | n > 0$ } fits the bill for the Pumping Lemma for Regular Languages.  Any substring to be pumped would consist either of all the same symbol, in which case pumping up produces a string with an unequal number of $0$'s and $1$'s, or it contains instances of both symbols, in which case pumping up produces a string with a $1$ followed by a $0$; in neither case is the pumped-up string in $L$.


For $F_0 = 0, F_1 = F_2=1, \dotsc$ consider

$$
\begin{align}
T(F_n, F_{n+1}) &= 1+T(F_{n+1}\mod{F_n}, F_n) & \text{by definition}\\
 &= 1+T(F_{n-1}\mod{F_n}, F_n) & \text{since }F_{n+1} = F_n+F_{n-1}\\
 &= 1+T(F_{n-1}, F_n) & \text{since }F_{n-1} \le F_n\\
\end{align}
$$
continuing, we see
$$
\begin{align}
T(F_n, F_{n+1}) &= 1+T(F_{n-1}, F_n)\\
 & = 2 +T(F_{n-2}, F_{n-1})\\
 & = 3 +T(F_{n-3}, F_{n-2})
\end{align}
$$
and in general
$$
T(F_n, F_{n+1}) = k+T(F_{n-k}, F_{n-k+1})
$$
so when $k=n$ we have
$$
T(F_n, F_{n+1}) = n+T(F_0, F_1) = n+T(0, 1) = n+1
$$
Now to make a conjecture about the growth of $T(F_n, F_{n+1})$ we need to find how large $n+1$, the run time, will be in terms of the size of $F_{n+1}$. There is a closed form for this, namely
$$
F_k = \frac{\phi^k-\psi^k}{\sqrt{5}}
$$
where $\phi = (1+\sqrt 5)/2\approx1.618$ and $\psi = (1-\sqrt 5)/2\approx-0.618$. Since $|\psi|<1$ that term will be negligible for sufficiently large values of $k$ so we have $F_k\approx \phi^k/\sqrt5$. Taking the log (to the base $\phi$) of both sides, we have $\log{F_k}\approx k-\log{\sqrt5}$, so $k$ will be $\log {F_k}$ plus a constant which we can ignore. In terms, then, of its arguments, $p, q$, with $q \ge p$ we'll have our conjecture:
$$
T(p, q) = O(\log q)
$$
which happens to be true, even if we don't restrict ourselves to Fibonacci numbers for the arguments.

This function is just the timing function for the Euclidean algorithm, which finds the greatest common divisor of the arguments:

gcd(p, q) =
   if p = 0
      return q
   else
      return gcd(q mod p, p)

For instance,
$$
\gcd(15, 24) = \gcd(9, 15) = \gcd(6, 9) = \gcd(3, 6) = \gcd(0, 3) = 3
$$
after five recursive calls. It happens that the longest this algorithm will take to complete is when the arguments are consecutive Fibonacci numbers. The upshot is that, fortunately for us this is fast, being no worse than proportional to the number of digits in the arguments.


What is the complexity of Hamming nearest neighbor to a subspace ...?

Your problem is known as the nearest codeword problem, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the distance is at most a given distance. Regarding algorithms, I suggest taking a look at a paper of Alon, Panigrahy and Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem.


How do you call alternatives in the grammatical productions?

how do you call the individual alternatives within the RHS?

As @Rafael mentioned, they are called alternatives.

Parsing Techinques: A Practical Guide, 2nd ed. (2008) by D. Grune and  C.J.H. Jacobs, page 15:

  There is a more compact notation, in which several right-hand sides for one and the same left-hand side are grouped together and then separated by vertical bars, |. This bar belongs to the formalism, just as the arrow $\to$, and can be read “or else”. The right-hand sides separated by vertical bars are also called alternatives.

  Is it related to your syntactic forms?

From the same source (p. 13):

  Non-terminals [S, A, B, C in the example] are called (grammar) variables or syntactic categories in linguistic contexts.

It seems the terms syntactic form and syntactic category are used somewhat interchangeably.
So, if an alternative is a variable, then it represents a syntactic form, but if it has more complex structure (it can contain terminals, or several non-terminals), then we might say that from the point of view of the grammar's author the alternative does not represent a syntactic form. But someone else can always turn it into one by defining a new non-terminal with an appropriate RHS.

Since B.C. Pierce's syntactic forms include terminals (true, false, 0), I agree with the accepted answer that the term syntactic form is used somewhat informally and is not defined precisely.


An algorithm to drop low-priority items from a heap-based priority queue

Let $n$ denote the size of the min-heap.  It's easy to do this in linear time, i.e., $O(n)$ time: walk through the heap, copying over only the items that are below the threshold into an array; then call MakeHeap to turn it into a heap.

I would be surprised if you can do better than this, in asymptotic worst-case running time.  For instance, any approach that involves scanning all items at the bottom layer will necessarily take at least linear time, i.e., at least $\Omega(n)$ time.  And if there is any item in the bottom layer that you don't examine, then in at least some cases you won't be able to tell whether it needs to be included or not.  So I suspect it may be possible to construct an adversarial argument that shows that at least $\Omega(n)$ time is needed -- though I don't know for sure.

Alternatively, one could consider the running time as a function of the output size.  Let $m$ denote the size of the output, i.e., the number of elements that are above the threshold.  Then it is easy to achieve $O(m)$ running time, by doing a top-down recursive pre-order traversal of the min-heap (think of it as a binary tree), truncating the traversal at each internal node that is above the threshold.  The running time is $O(m)$ since you only visit a node if it is included in the output or if it is an immediate descendant of a node included in the output; since each node has at most 2 descendants, this means that the number of nodes visited is at most $3m$, i.e., $O(m)$.  This is clearly optimal, as a function of output size: any algorithm that produces $m$ outputs has to take at least $\Omega(m)$ time, just to write out the output.


Does coNP-completeness imply NP-hardness?

You claim that every problem in NP can be reduced to its complement, and this is true for Turing reductions, but (probably) not for many-one reductions. A many-one reduction from $L_1$ to $L_2$ is a polytime function $f$ such that for all $x$, $x \in L_1$ iff $f(x) \in L_2$.

If some problem $L$ in coNP were NP-hard, then for any language $M \in NP$ there would be a polytime function $f$ such that for all $x$, $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$, showing that NP$\subseteq$coNP, and so NP$=$coNP. Most researchers don't expect this to be the case, and so problems in coNP are probably not NP-hard.

The reason we use Karp reductions rather than Turing reductions is so that we can distinguish between NP-hard and coNP-hard problems. See this answer for more details (Turing reductions are called Cook reductions in that answer).

Finally, coNP-hard and coNP-complete are both standard terminology, and you are free to use them.


Hardness of a constrained quadratic maximization

(I have found the answer to my question, so I am sharing a sketch here).

The quadratic maximization can be shown to be NP-hard by a reduction from the following problem:

Given $k$-partite graph $G=(V_{1}, \dots, V_{k}, E)$, does $G$ contain a $k$-clique.

Note that the latter problem is a (seemingly) special case of the max-clique problem restricted to a particular family of graphs. It can however be shown that it is also NP-complete by a reduction from the general max-clique problem itself (See here).

Let $\mathbf{A}$ denote the adjacency matrix of $G$.
Let $S$ be an arbitrary set of $k$ vertices and $\mathbf{A}_{S}$ denote the principal submatrix corresponding to $S$, i.e. $\mathbf{A}_{S}$ is the $k\times k$ adjacency of the graph induced by $S$.
If the vertices in $S$ form a $k$-clique in $G$, then all off-diagonal entries of $\mathbf{A}_{S}$ are equal to $1$, and its principal eigenvalue $\lambda_{1}(\mathbf{A}_{S}) = k-1$.
In any other case, that is, if $S$ is not a $k$-clique, then $\lambda_{1}(\mathbf{A}_{S}) < k-1$.
Finally, note that since $G$ is $k$-partite, a $k$-clique (if one exists) will contain a single vertex from each of the sets $V_{i}$, $i=1,\dots,k$.

Let $\mathbf{A}^{\prime} = \mathbf{A} + |\lambda_{n}(\mathbf{A})|\cdot\mathbf{I}$, where $\lambda_{n}(\mathbf{A})$ is the smallest eigenvalue of $\mathbf{A}$;
$\mathbf{A}^{\prime}$ is a PSD matrix.
Further, consider $k$ disjoint groups of variables corresponding to the sets $V_{1}, \dots, V_{k}$ of $G$.
We solve the quadratic maximization with input $\mathbf{A}^{\prime}$ and the specified groups of variables.
The maximum objective value will be equal to $k-1 + |\lambda_{n}(\mathbf{A})|$ if and only if $G$ contains a $k$-clique.


How to improve the accuracy of automatic conflict resolution?

There are many candidate approaches you could consider.  I would suggest you be creative about what features you could use, to make predictions about which candidate is more likely to be the intended one.

One approach is to use a language model for the prevalence of different phrases.  For instance, if $w, x$ are two words, define

$$r(x | w) = {P(w \; x) \over P(w) \times P(x)}.$$

(Here $P(w \; x)$ represents the prevalence of the 2-gram $w \; x$ in some large corpus, and $P(w)$ represents the prevalence of the 1-gram $w$ in the corpus.)

Now if the previous word is $w$ and the next word is either $x$ or $y$, compare $r(x | w)$ to $r(y | w)$ to see which is larger, and use that to resolve the conflict.

For example, comparing $r(\text{Tallahassee} | \text{at})$ to $r(\text{shake} | \text{at})$ using the Google n-gram viewer, we find that the former is much larger.  In particular, the former is $1.2 \times 10^{-6}/(0.3 \times 8.5 \times 10^{-5}) \approx 0.05$, while the latter is $4.8 \times 10^{-8}/(0.3 \times 9.7 \times 10^{-4}) \approx 10^{-4}$, which is much smaller.  We conclude that "Tallahassee" is much more likely to follow "at" than "shake", so the conflict should be resolved by the former.

You can generalize this to use any number of tokens of previous history (e.g., the previous 2 words instead of the previous 1 word).

Another approach would be to use something similar, but replace words with their parts of speech.

For instance, Google's n-gram viewer supports part-of-speech queries.  You can quickly see that "ADP Tallahassee" (basically, a preposition followed by Tallahassee) is more common than "ADP shake", so "I eat at" is more likely to be followed by "Tallahassee" than "shake".  In contrast, you can see that "DET shake" is more common than "DET Tallahassee"; so "a" (an article) is more likely be to be followed by "shake".


In fact you do change the value of $n$, see $n=n/4$, and so the while-loop results in  $\sum_{i=1}^{\log_4{n}}{\sqrt{i}}$ which is equal to $\sqrt{1} + \sqrt{2} + \dots + \sqrt{\log_4{n}}$.

Upper bound
$\sqrt{1} + \sqrt{2} + \dots +\sqrt{\log{n}} \leq \log{n}\sqrt{\log{n}}$ which is less than $\sqrt{n}$ for sufficiently large $n$s (you may prove it using induction or using some other techniques).


Design a data structure with constant insertion and sublinear range maximum query

If they're timestamps, there's a good chance they are approximately randomly distributed across some range, say $[\ell,u]$.  In this case there exist reasonable solution.
You can hash each pair into $k$ equal-width buckets in this range, i.e., using the hash function $h(a,b) = \lfloor N(a-\ell)/(u-\ell) \rfloor$, where $k$ is roughly similar to the number of items seen so far.  Within a bucket, remember the largest value of $b$ of all pairs that hashed into that bucket.  Then insert can be done in $O(1)$ expected time, and lookup can be done in $O(1)$ expected time.
Of course, we won't know $[\ell,u]$ exactly, and $\ell,u,k$ will change over time.  However you can adjust on the fly, by keeping track of the smallest and largest timestamp seen and the number of pairs seen so far.  Every time the number of pairs doubles, you update the hash function and rehash.  Naively, that sounds like it takes $O(n)$ time to rehash, but you can spread that out over the next $n/4$ inserts, maintaining the $O(1)$ expected running time.

If the timestamps aren't uniformly distributed but they come iid from some distribution, and the distribution is "smooth" enough, then I think you can find a similar solution.  Keep track of the integer-percentiles of the $a$ values (i.e., the 0% percentile value, the 1% percentile value, the 2% percentile value, and so on); it is possible to estimate these values using streaming quantile estimation / streaming histogram estimation.  To hash a pair, convert its $a$ value to a percentile (a real number $p$ in the range $[0,1]$), using linear interpolation among these 101 known percentile values; then $p$ will be approximately uniformly distributed on $[0,1]$, and you can hash $p$ into equal-width buckets as before.  If the distribution is smooth enough, linear interpolation will work well and $p$ will be approximately uniformly distributed.  If the distribution is not smooth, this may work poorly.


How is heap memory allocated to a process?

Heap allocators typically call a system call to reserve a region of pages and then dole out chunks of that to new, malloc, and other higher-level calls. The system call on Unix used to be brk and sbrk, but implementations sometimes use mmap as well. I think windows uses VirtualAlloc, but it's not totally clear to me.  A good resource for this is Wikipedia's page on C dynamic memory allocation.


Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11

Well, we know our word contains a $0$, so let's start with that:

$$0$$

Now let's assume that that $0$ is the first $0$ in the word. Then there may be arbitrary $1$s and $2$s before it, but $11$ is not allowed, thus $1$ must be followed by either a $2$ or by our zero:

$$(2 + 12)^*(10 + 0)$$

Now at the end we can have arbitrary characters, except for $11$. Thus each $1$ must be followed by a $0$ or $2$, or be at the end of the word:

$$(2 + 12)^*(10 + 0)(0 + 2 + 10 + 12)^*(1 + \lambda)$$

Here $\lambda$ is the empty string. If that isn't acceptable, we can distribute over the concatenation:

$$(2 + 12)^*(10 + 0)((0 + 2 + 10 + 12)^*1 + (0 + 2 + 10 + 12)^*)$$

Or alternatively we turn our logic around:

$$(2 + 12)^*(10 + 0)(1 + \lambda)(0 + 2 + 01 + 21)^*$$

And then distribute over the earlier concatenation:

$$(2 + 12)^*(101 + 01 + 10 + 0)(0 + 2 + 01 + 21)^*$$

These are all unambiguous, by the trick of recognizing a first zero, rather than the existence of an arbitrary one.


(partial answer)

  For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?

Actually, the inclusion $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$ holds for any relation $\mathcal{R}$, and not just the one mentioned. Indeed, if we have $P \mathcal{R} Q$, then we also have $P \approx P \mathcal{R} Q \approx Q$, by reflexivity of weak bisimulation.

  According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...

You have to check that $0\xrightarrow{{\hat\tau}} 0$, which (if I remember correctly) is defined as $0\xrightarrow{{\tau}}^* 0$ which holds since the Kleene's star includes "zero steps".

I seem to remember that the "$\hat\alpha$" move definition made a special case for $\hat\tau$, specifically to allow for zero steps.


Find perfect matching whose weight is minimal, in polynomial time

Yes, there is a polynomial-time algorithm for your problem.  There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods.  In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.

Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible.  Call this the maximum-weight perfect-matching problem.  You can solve this problem as follows.  Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight).  Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching.  (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)

I claim that the resulting matching will be a perfect matching, if one exists.  Why?  Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph).  The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph).  Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph.  Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching.  It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).

So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized.  Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.


Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Hint: Use the classical dynamic programming algorithm to find all sums of subsets, and from that information deduce the sum closest to $M$.

You can actually improve this algorithm in two ways. First, you can improve the running time to $O(n\min(K,M))$, using the fact that the optimal sum is at most $2M$ (why?). Second, you can also find the optimal set $A'$ itself within the same time bound: just use the very same technique used to accomplish that for the usual SUBSET-SUM.


Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence

Proofs in Haskell?

Okay, first let's talk about the Curry-Howard correspondence. This says that one can view theorems as types and proofs as programs. However, it says nothing about which specific logic a particular programming language represents.

In particular, Haskell lacks dependent types. That means that it can't express statements with "forall x" or "exists x". So immediately there's no way to encode your axioms.
The problem is that Haskell's types only let you refer to other types, not to specific values of those types. Your axiom says "forall x and y, Property holds for x and y": it's reasoning not about $Nat$ as a class, but about specific values of that class.

There are ways to fake it in Haskell, by encoding values with a type-level representation, but I'd strongly recommend against those for a beginner.

What does the Curry-Howard Correspondence Actually Mean?

What Curry-Howard is actually saying is not that we can write a program that implements a checker for proofs. What is says is that we can view a proof as a form of a program in a purely-functional language. Specifically, a proof is like a program that takes proofs of its assumptions as input, and produces proofs of its conclusions as outputs.

The key is that propositions are like types, and proofs are like programs. So in your example, it doesn't make sense to have an implementation of your axioms, since axioms are propositions that you take as true, without proof. An implementation would correspond to a proof of them.

The real magic of Curry-Howard comes when we introduce dependent types. The key is the dependent function type: instead of just having $A \to B$, we have $(x:A) \to B$, where $x$ can occur in $B$.

There's a lot going on here. First, we've blurred the line between types and values. In the same way that the type constructor List takes an argument to become a type, like List Int, we now can have type constructors that take values as arguments.

The classic example of this is $Eq$ for representing proofs of equality. For any values $x,y$, $Eq\ x\ y$ is the type of proofs that $x = y$. So we have a type indexed on values.

Secondly, we've now given names to our arguments in the type, not just in the implementation. So the order of arguments very much matters, because the types on the right can refer to the names on the left. They depend on the names, thus the name dependent types.
What this is really saying is that the return type of the function can change, depending on the value of the argument given.

Curry-Howard then says that, if we produce a well typed function of type $(x:A) -> B$, this is the same as saying "for all $x$ that satisfy $A$, $B$ holds".

The dual of this is dependent pairs, which code "exists" proofs. Instead of having the tuple type $(A,B)$, we now have $(x:A, B)$, where $B$ can refer to $x$. This means that the type of the thing on the right can depend on the value of the thing on the left. This is a constructive form of an existential proof: the way you prove "there exists an x satisfying B" is by saying "here's the x, and here's the proof it satisfies B".

Where to learn more?

If you want to prove things in a formal setting, I'd recommend
Coq, Agda, Idris, or Isabelle, since they have the machinery
for dealing with dependent types and proving things.

Some good free resources:

Software Foundations
Certified Programming with Dependent Types
Lean You An Agda and Achieve Enlightenment

Some nice articles/papers/tutorials on the topic include:

Propositions as Types
The Power of Pi
Tutorial Implementation of Dependently Typed Lambda Calculus

The Idris book is popular, but not free:
Type Driven Development in Idris


"Last Come => More Relevant" data structures

I think of three possible options:

As mentioned before in the comments, one of my all-time favorite data structure, splay-trees. They are easy to implement and probably (assuming the Dynamic Optimality conjecture is true) roughly as good as any other dynamic search tree data structure. We already know that splay trees are as good as any static search tree. Note that there are other types of dynamic binary search trees (tango trees, zipper trees, ...), which will also perform well compared to the best dynamic search tree.
Use one or more optimal binary search tree (via dynamic programming). Since you insert/delete elements you need to rebuild the search tree form time to time. Say after a threshold value of elements that change you build the new optimal tree from scratch. This might be applicable, if you have time between the request. The rebuilding can be also be done in the background. Since building a optimal search tree is $O(n^2)$, this is not a good idea for large data sets.
Use Hashing. It might not treat the later inserted elements different, but in practice it might be as good as the other ideas.

You might think of keeping the last inserted elements in a separate data-structure (like a hash-map ) which you query first. Of course, from time to time you need to rebuilt.


By reading a 0, your DFA switches its state from right to left,
By reading a 1, it switches state from up to down.
So to reach your final state $q_3$ your DFA has to read an odd number of 1's and an even number of 0's.
Therefore your language is $L=\{w \in \{0,1\}^*|  |w|_1 mod  2 = 1, |w|_0 mod 2 = 0  \}$


Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$.
When the presenter is speaking about linear time for partition, this is a stronger statement than $O(n)$ time. All linear functions are in $O(n)$, but it also contains non-linear functions.
For example: $\sin n, \frac{1}{n}, \sqrt{n} $ are all in $O(n)$, but they are not linear. As was written in a comment, $O(n)$ is the set of functions bounded by linear functions, but not the set of only linear functions.
To be linear gives more information than to be in $O(n)$, to be in $\Omega(n)$, even to be in $\Theta(n)$.


Your graph based on a binary tree would have exponential size (it would require at least $2^k$ nodes), which is probably no good for the reduction; an exponential blow-up in the size of the problem instance isn't ok.

Yes, you could use a hexagon instead of a diamond.  I don't see any advantage, but it would also provide a valid reduction.


Computer science is a very broad field - see this Wikipedia outline. Machine learning is just one topic within the field, and there are other parts of computer science that have little or no overlap with machine learning. For example, the theory of compiler design is unlikely to be of much use to you when studying machine learning.

My suggestion is to approach this from the opposite direction. Start with a text that provides an introduction to machine learning. An introductory text should include an overview of other computer science topics that are pre-requisites. If you want to or need to dig into any these wider topics in more detail, then you have a more focussed goal than trying to understand the whole of computer science.


Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

If you want to reduce $E_{DFA}$ to $A_{DFA}$, you should use the following theorem:

  If a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

But a much more efficient algorithm would just run DFS from the initial state, and check whether some accepting state is reachable from it.


How are REGEXP implemented in programming languages?

I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata.  The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM, 11(6):419-422, June 1968.  But that paper is a little hard to read, since he was compiling to machine code.

My favorite tutorial on regular expression implementation is this series of blog posts by Russ Cox, the author of the RE2 regular expression library.  He gives lots of historical discussion.  He argues that the most efficient approach to simulating the NFA is to convert to DFA on the fly with caching of just the DFA states that you actually reach.  (In contrast to, for example, the implementation of regular expressions in Perl, which use backtracking.)  There are cases (e.g., when you get an extended regular expressions with backreferences) where you need to use backtracking, but Cox suggests that you should only use backtracking when you need to.

The other place you might look is Henry Spencer's regular expression library.  According to that web site this was described in the book: Dale Schumacher (ed), Software Solutions In C, Academic Press, 1994.


The reason that you do not find any results is thta from a scientific point of view, the well-posed questions for PTAs and MDPs are quite different:

MDPs typically have a reward function assigned, while PTAs do not necessarily have to have them.
It is a bit imprecise to state that the "objectives is to solve the non-determinism of a MDP" -- it depends on what you want to do. PTAs are foremost models that you can analyse. Resolving the non-determinism means computing a policy, which makes sense if you have some kind of optimization criterion that you want to follow. This could be a temporal logic formula.
In MDPs, the classical question is to find a policy that maximizes the limsup average payoff or the discounted payoff. In the latter case, there exist optimal memoryless policies (which is the result that you refer to). In PTAs, asking the same question is kind-of odd as the number of states in PTAs is infinite and there is (by default) nothing to optimize. A state consists of a location and a valuation to the clocks. This is already the case for timed automata, from which PTAs inherit many of their properties (and hardness results).
The questions typically asked for PTAs are whether there exist policies that raise the probability of some temporal property holding along a trace over some given limit. A paper my Norman et al. (http://www.prismmodelchecker.org/papers/fmsd-ptas.pdf) contains details. They also define reward structures for PTAs, but the do not need to be concerned with discounted payoff optimization, like it is common in the MDP research case.


Sure, this is a standard encoding exercise.

First of all, let $p : \mathbb N^2 \to \mathbb N$ any bijective computable function, called a pairing function. A standard choice is

$$
p(n,m) = \dfrac{(n+m)(n+m+1)}{2}+n
$$

One can prove that this is a bijection, so given any natural $k$, we can compute $n,m$ such that $p(n,m)=k$.

To enumerate lambda terms, fix any enumeration for variables names: $x_0,x_1,x_2,\ldots$.

Then, for each natural number $i$, print $lambda(i)$, defined recursively as follows:

if $i$ is even, let $j=i/2$ and return variable $x_j$
if $i$ is odd, let $j=(i-1)/2$

if $j$ is even, let $k=j/2$ and find $n,m$ such that $p(n,m)=k$; compute $N=lambda(n), M=lambda(m)$; return application $(NM)$
if $j$ is odd, let $k=(j-1)/2$ and find $n,m$ such that $p(n,m)=k$; compute $M=lambda(m)$; return abstraction $(\lambda x_n.\ M)$

This program is justified by the following "algebraic" bijection involving the set of all lambda terms $\Lambda$:

$$
\Lambda \simeq \mathbb N + (\Lambda^2 + \mathbb N \times \Lambda)
$$

which is read as "the lambda terms, syntactically, are the disjoint union of 1) variables (represented as a natural), 2) applications (make by two lambda terms), and 3) abstraction (a pair variable/natural + lambda term)".

Given that, we recursively apply computable bijections $\mathbb N^2 \simeq \mathbb N$ ($p$) and $\mathbb N + \mathbb N \simeq \mathbb N$ (the standard even/odd one) to obtain the algorithm above.

This procedure is general, and will work on almost any language generated through a context-free grammar, which will provide a similar isomorphism to the one above.


Algorithm to enumerate all complete schedulings of finals tests?

You're asking to enumerate all maximum matchings in a bipartite graph.  Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size graphs.

There might be algorithms that work well enough for your situation, given the small numbers you're dealing with.  For instance, a simple approach is to use a backtracking search.  First nondeterministically choose a period for final $F_1$ (out of all possibilities).  Next choose a period for final $F_2$ (out of all possibilities, excluding the periods that have already been chosen), and so on.  If at any point there are no legal choices available (e.g., you want to choose a period for $F_i$ but all options have already been filled with a final), terminate.  Now replace the nondeterministic choices with branching over all possibilities, in a breadth-first or depth-first search, and that should provide a way to enumerate all valid schedules.

See also Counting and finding all perfect/maximum matchings in general graphs and https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Counting_problems for references to the literature on the general problem.


Just like @Hendrik mention all you need to do is calculate Levenshtein distance which does exactly what you need.

Levenshtein distance can be expressed in following formulae
$$
\mbox{lev}_{a,b}(i, j) = \begin{cases}
    \max(i,j) &, \mbox{if } \min(i,j) = 0
    \\ \min \begin{cases}
           \mbox{lev}_{a,b}(i-1,j) +1 \\
           \mbox{lev}_{a,b}(i, j-1)+1 \\
           \mbox{lev}_{a,b}(i-1,j-1) +[a_i \neq b_i]
       \end{cases}
    &, \mbox{else}
\end{cases}
$$
Where $a, b$ are compared strings, $i, j$ are strings length and $[a_i \neq b_i]$ is $1$ iff $a_i \neq b_i$ and $0$ otherwise.

From this formula it can be easy translated to pseudocode.

Lev(a, b)
  len_a = len(a)
  len_b = len(b)
  cost = 0

  if(a[0] != b[0])
    cost = 1

  if (len_a == 0 or len_b == 0)
    return max(len_a, len_b)
  return min(Lev(a[1..len_a-1], b) + 1,
             Lev(a, b[1..len_b-1]) + 1,
             Lev(a[1..len_a-1], b[1..len_b-1]) + cost)

However there is small problem with this solution, its running time is $\mathcal O(nm)$ and you requested $\mathcal o(nm)$ so I hope you just made a typo.

You can also calculate this distance online using this website.


No, it doesn't mean that.

The set of NP-hard problems is upward-closed in the sense that there is no upper bound on the hardness of problems in it. You are correct to say that the class of NP-hard problems contains undecidable problems.

That does not imply, however, that every NP-hard problem has "unsolvable instances".

There is no such thing as an "unsolvable instance" in integer programming. There always is an answer, true or false (considering the decision version). Every finite set of instances is trivially computable. Only infinite sets can be undecidable.
We do know upper bounds on integer programming. For the decision version, we know that it's in NP; the optimization version is in NPO. Therefore, we know IP is decidable.


Irregularity of $\{0^x1^y : y \nmid x\}$

Assume that $L$ is regular. Suppose that the pumping constant is $q$, and let $p$ be a prime larger than $q$. Consider the word $w = 0^{p+1}1^p \in L$. According to the pumping lemma, we can write $w = xyz$, where $|xy| \leq q$, $y \neq \epsilon$, and $xy^tz \in L$ for all $t \geq 0$. Let $y = 0^i$, where $1 \leq i \leq q < p$. Then
$$
xy^{t+1}z = 0^{p+1+ti} 1^p.
$$
Since $i \in \{1,\ldots,p-1\}$ and $p$ is prime, we know that $i$ has an inverse modulo $p$, that is, a number $j \in \{1,\ldots,p-1\}$ such that $ij - 1$ is a multiple of $p$, say $ij = ap + 1$ (we prove this below). If we take $t = (p-1)j$ then
$$
p+1+ti = p+1+(p-1)ij = p+1+(p-1)(ap+1) = p(a(p-1)+2)
$$
is a multiple of $p$, and so $xy^{t+1}z \notin L$, contradicting the pumping lemma.
The existence of $j$ can be proven in many ways. Here is one. Consider the integers $i,2i,3i,\ldots,(p-1)i$. Suppose that you divide them by $p$, obtaining remainders $r_1,r_2,\ldots,r_{p-1}$. Since $p$ is prime and $i \in \{1,\ldots,p-1\}$, all these remainders are non-zero. Furthermore, they must be different: if $r_u = r_v$ for $1 \leq u < v < p-1$ then $vi-ui = (v-u)i$ would be a multiple of $p$, contradicting the primeness of $p$. Therefore one of the remainders $r_j$ must equal $1$.


It happens that compilers contain subtle errors. No blatant errors, because blatant errors would be detected and fixed.
A compiler that is itself compiled by a compiler with subtle errors will tend to have blatant errors. They will be easy to detect because they are so blatant. They will be hard to fix because these blatant errors will be produced by perfectly fine source code, so whoever wants to fix it will have a hard time finding the real problem.
The solution will be to make a compiler of sufficient quality that bugs are very rare, and extremely rare within the compiler. We also expect compiler bugs to affect very complicated code more, so the compiler writer should write code that is simple and follows common coding patterns.


Minimum bottleneck path between two vertices in an undirected graph

I will use the fact that you can check for the connectivity between two vertices $s$ and $t$ in a graph with $m>0$ edges in time $O(m)$.

Call $G$ be the input graph, and let $s$ and $t$ be endpoints of the paths you are interested in. I will denote by $G_w$ (resp. $G^<_w$) the graph induced by all the edges of weight at most (resp. less than) $w$ in $G$. You can solve the problem using the following recursive algorithm:

If $G$ has no edges, report that $s$ and $t$ are disconnected in $G$.

If $G$ has at least one edge, find the median $w$ among the edge weights of $G$, and proceed as follows:

If  $s$ and $t$ are connected in $G_w$ and disconnected in $G^<_w$, return $w$.
If $s$ and $t$ are connected in both $G_w$ and $G^<_w$, apply the algorithm recursively on $G^<_w$ (notice that $G^<_w$ has at most $\frac{m}{2}$ edges).
If $s$ and $t$ are disconnected in $G_w$, build the graph $G'$ obtained from $G$ by
identifying all vertices that belong to the same connected component of $G_w$, and apply the algorithm recursively on $G'$ (notice that $G'$ has at most $\frac{m}{2}$ edges, since it can't contain any edge with weight less than or equal to $w$).

The time complexity of the above algorithm is described by the recurrence equation:
$T(m) = T(m/2) + O(m)$, which has solution $T(m)=O(m)$.

This problem is the same as its maximization version once all edge weights are multiplied by $-1$.


How can I prove this language is not context-free?

You can force the pumping to be in some places, using Ogden's lemma, for example by marking all the 0's.

Suppose it is context free, then Ogden's lemma gives you a $p>0$, you give it $w=0^p1^p2^p$ which is in the language, and you "mark" all the 0's. Then any factorisation $w=uxyzv$ must be such that there is a $0$ in $x$ or $z$. You can also assume $x=a^k$ and $z=b^m$ since $xx$ and $zz$ must be substrings of your language.

If $z=0...0$ then $w=ux^2yz^2v$ has more 0's than 1's
If $x=0..0$ and $z=1..1$ then $w=ux^2yz^2v$ has more 1's than 2's.
If $x=0..0$ and $z=2..2$ then $w=ux^2yz^2v$ has more 0's than 1's.

So $ux^2yz^2v$ is not a word of your language. Therefore, it is not context-free.

For other techniques, see the discussion: How to prove that a language is not context-free?


Must a word be binary (and never unary)?

Machine words have fixed length. Denoting the length by $n$ and the base by $b$, each machine word has $b^n$ possible values, and so stores $\log_2 (b^n)$ bits of information.
A base can be binary or decimal and so forth; if $b=1$ then the machine word has a single possible value, and so stores no information. It would be useless.
Unary encoding is only relevant in contexts where the length is not fixed.


Expected space consumption of skip lists

In this paper it is proven that there exists a constant $\alpha$ such that the probability of the space exceeding $\alpha n$, is less than $1/2^{\Omega(\sqrt{n})}$. Thefore, the more elements there are, the less likely it is to exceed this space bound.


What is the fastest way to bytewise examine the contetnt of quadword

Yes, it can be done.  Here is one reasonable approach.  First XOR the value with 0x0A0A..0A:

t = x ^ 0x0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A;

So now the problem becomes testing whether y contains a zero byte.  First we'll replace every byte with a single bit that is 1 if the byte is non-zero, or 0 if the byte is zero:

u = t | (t>>4);
u = u | (u>>2);
u = u | (u>>1);

(Here we only care about the least significant bit of each byte; the remaining bit positions hold garbage that we don't care about.)  Now we'll flip each of those bits:

v = ~u;

At this point the LSB of each byte is 1 if the original value contained a 0x0A there, or 0 otherwise.  So, we'll test whether any of these bits are 1:

w = v | (v>>64);
w = w | (w>>32);
w = w | (w>>16);
w = w | (w>>8);
y = w & 1;

At this point, y is the result you are looking for: it will be 1 if the original value had a 0x0A byte anywhere, or 0 otherwise.


Are there any open source SAT solvers with UNSAT core extraction algorithm built in?

MUSer2 is probably the tool for extracting minimal unsatisfiable cores (MUS) currently. It treats the SAT solver as a black box, so you can plug in any solver you want.

If you want a solver with MUS extraction capability, the newest version of PicoSAT comes with a utility tool PicoMUS that does the job.


If I understood well the question, I think that you can apply a speedup trick to get faster automata on an infinite number of mazes (providing that the exit is placed on one of the border): you can simply use the internal states to store a finite number of steps and recognize dead ends like the one in the figure:

When a right-hand following automaton is in position $A$ and its state "signals" that it has just followed a closed square (with fixed size encoded, not an arbitrary large square), then it can safely turn left and avoid visiting the dead end zone.
As underlined in my comment below, the automaton will apply the shortcut on every maze that contains one (or more) "submazes" like the one in the figure, so it will perform better on infinitely many mazes. On the mazes that don't contain a submaze like the one in the figure it will perform like a standard right-hand following automaton.

In a similar manner you can encode a finite number of different  fixed size shapes to avoid dead ends and speed up your automaton. As a consequence, there is no "optimal" myopic maze solver for simply-connected mazes with the exit placed on the border.

The trick works if the entrance is placed inside the maze and the exit on the border, too; but if the exit is placed inside the maze, then it doesn't work because all locations must be visited and in this case your myopic solver is optimal.

Obviously you can't apply the same trick to solve non-simply connected mazes (but it should work if there is a fixed upper bound on the size of each unconnected component).


Decremental reachability in a grid graph

By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.

Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left.
For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.

When removing an edge call union() on the two squares (or the sqare and $A$ or $B$) separated by that edge.
To check connectivity, call find() on the faces $A$ and $B$. If the results differ, return true, else return false.


Finding longest chain in poset in subquadratic time

Well, start by observing that

when A has no comparable pairs, the height will be 0
and
when A has one or two comparable pairs, the height will be 1

.
Thus, when  $\leq$  is given with one bit for each ordered-pair of distinct elements,

even promised-to-be-at-most-1 height will have

co-nondeterministic query complexity  $(|\hspace{.02 in}A|\hspace{-0.03 in}\cdot \hspace{-0.03 in}(|\hspace{.02 in}A|\hspace{-0.04 in}-\hspace{-0.05 in}1))\hspace{.02 in}/\hspace{.02 in}2$

and probabilistic query complexity  $\Theta$$\left(\hspace{-0.02 in}|\hspace{.02 in}A|^2\right)$ .

Accordingly, we can only hope for better when  $\leq$  is given in some other way,

like as a list of the pairs for which it's true or as

an $A$-indexed array of ordered-pairs of lists, such that for each element $a$ of $A$,

$a$'s left list is the $a'$ such that  $a' < a$  and $a$'s right list is the $a'$ such that  $a < a'$

.
(I currently have no clue regarding the complexity for such representations of  $\leq$ .)

For your case of interest:

See this question and its answer.

(That answer's universe size is your n and that answer's n is your  $|\hspace{.04 in}A|$ .)

However, that negative result does not necessarily apply to

"the case where the length of the longest path is already known to be" short.


What is the difference between a prime attribute and a proper subset of the candidate key?

Prime attributes are, in your example, just A, B, and C. The subsets of the candidate key are combinations of prime attributes. The difference is subtle, but if you read your material carefully, it will become apparent.