The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know.

For a permutation $\sigma$ of $\{1, \ldots, n\}$ define the permutation matrix $P_\sigma$  as the 0-1 matrix such that $P_{ij} = 1$ if $j = \sigma(i)$ and $P_{ij}=0$ otherwise. This is simply the matrix which permutes the coordinates of a vector $x$ according to $\sigma$: if $y = P_\sigma x$ then $y_i = x_{\sigma(i)}$. I'll denote $y=P_{\sigma}x$ as $\sigma(x)$ from now on.

One more definition: a non-negative $n\times n$ matrix $M$ is doubly-stochastic if each one of its rows and each one of its columns sums to 1.

And one fact which is very important in combinatorial optimization - the Birkhoff-von Neumann theorem:

  A matrix $M$ is doubly stochastic if and only if it is a convex combination of permutation matrices, i.e. if and only if there exist permutations $\sigma_1, \ldots, \sigma_k$ and positive reals $\alpha_1 , \ldots, \alpha_k$ such that $M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$ and $\sum{\alpha_i} = 1$.

Notice that a doubly stochastic matrix is defined by the inequalities

$$\forall i: \sum_{j = 1}^n{M_{ij}} = 1$$
$$\forall j: \sum_{i = 1}^n{M_{ij}} = 1$$
$$\forall i, j: M_{ij} \geq 0$$

All these inequalities taken together determine a polytope $P$, and the Birkhoff-von Neumann theorem states that the extremal points (vertices) of this polytope are all permutation matrices. From basic linear programming, we know this implies that any linear program which has the above inequalities as its constraints (and no other constraints) will have a permutation matrix as an optimal solution.

So given an input $a = (a_1, \ldots, a_n)$ to be sorted, we just need to come up with a linear objective $f_a(M)$ for which:

$f_a(P_\tau) < f_a(P_\sigma)$ if $\sigma(a)$ is sorted but $\tau(a)$ is not.

Then formulate a linear program with objective to maximize $f_a(M)$ and the inequalities above as constraints, and you are guaranteed that an optimal solution is the permutation matrix $P_\sigma$ for $\sigma$ such that $\sigma(a)$ is sorted. Of course, it's easy to "read off" $\sigma$ from $P_\sigma$.

One choice for $f_a(M)$ is $v^T M a$ where $v = (1, \ldots, n)$. Verify that

this is linear in $M$;
for $P_\sigma$, $f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$;
the above is maximized at the $\sigma$ for which $\sigma(a)$ is sorted (by contradiction: otherwise you could switch two coordinates of $\sigma(a)$ and achieve a higher value).

And voila, you have a linear program for sorting. Seems silly for sorting, but this is in fact a powerful method in optimization.


How is the problem, {⟨G⟩|G has no triangle} in Logspace?

FOR x := 1 TO n DO
    FOR y := 1 TO n DO
        FOR z := 1 TO n DO
            IF E(x,y) && E(y,z) && E(z,x) THEN REJECT
ACCEPT

Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.


Does quicksort for increasing order work faster if the input set is more decreasing sorted?

First, this is not the Quicksort that we all know and love, but some rather strange version of it, so your results cannot be applied to what is usually called Quicksort.

If the array is already in descending order, your version (unlike the original Quicksort) will not do any exchanges in the first partitioning. So the partitioning will be fast. However, it makes practically no progress; only one element is moved to its right position, and you will have about $n^2 / 2$ comparisons in total, which is about the worst case possible.

An array in ascending order is even worse, since you will do $n^2/2$ comparisons, plus $n^2/2 exchange operations.


How can I measure the usability of a catalogue?

In the past I worked on usability of interfaces in the information retrieval area, so I give you some practical ideas on how to measure the usability.

You didn't give details of what a "catalogue" is, so I will assume that a user has a problem (or need) and he is searching your catalogue (in paper or electronic format) for one or more solutions.

Then you can build a set of problems $P = \{p_1,...,p_n\}$, and for each problem a set $S^i$ of (possibly weighted) correct solutions: $S^i = \{ s^{i}_1,...,s^{i}_m\}$.

Then you can setup a test with real users.

Every user must solve all the problems in $P$ (in shuffled order) using your catalogue, in one of the two format (paper or electronic).

For each problem, you measure the time spent solving it. At the end you ask the users to give some judgements of satisfaction (using weighted values) on the two catalogues (covering different aspects of satisfaction, for example: "Do you think the catalogue helped you?", "Do you think it is easy to learn how to use it",  ....)

Then you can measure (and compare) the usability of the two catalogues in term of:

standard precision and recall of the results found for each problem $p_i$. Precision: number of correct solutions among the total number of answers; recall: number of correct solutions found among the total number of correct solutions in $S^i$
time spent for solving each problem $p_i$ (efficiency of the system);
user satisfaction

For what concerns the mapping between a paper catalogue to a system interface, you can "record" what users do during their searches on the paper catalogue, then try to "simulate" the actions of those users that performed better using an expert system (see expert system design).


Why are mapping reductions from incomputable Languages OK?

There are two options:

Either the pseudocode means "run $A_{TM}$ on the pair $M,w$" when it says "Simulate $M$ on $w$";
or it really means to simulate $M$ on $w$, and if it ever stops then do something; there is no "else" clause in that case.


I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset.

The $k=2$ case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from $k=2$.


Which part of Go(lang) is in Crystal(lang)?

I simply asked @asterite, one of the developers of Crystal, at IRC #crystal-lang (the log is here).

He said the answer is CSP, the concurrency model. For example, both Go and Crystal use channels for communications.


Is a particular string regular (e.g is '010') regular?

Being regular is a property of languages, not of words.

However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, $\{ 010 \}$. This language, just like any other finite language, is regular.

Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.

  If $L$ is a regular language then there exists a constant $n$ such that for all words $w \in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.


Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

I don't know, but I suspect it's an open question.

If the theory of the reals with exponential function is decidable, then your problem is decidable, too.  It is known that if Shanuel's Conjecture holds, then the former is decidable, so your problem is too.

If I understand correctly, the following paper tackles your problem:

The identity problem for elementary functions and constants.  Dan Richardson, John Fitch.  ISSAC '94.

It appears that they show a procedure that always terminates if Shanuel's Conjecture holds; and if it doesn't terminate for a particular expression, then we can extract from that expression a counterexample to Shanuel's Conjecture.  They then argue that it seems unlikely that we will find a counterexample any time soon, so it seems unlikely we will find inputs on which this procedure fails to terminate any time soon.

See also https://mathoverflow.net/q/118972/37212 and https://mathoverflow.net/q/129563/37212 and https://mathoverflow.net/q/145299/37212.


What was the major breakthrough between Hoare-Floyd logic and Scott–Strachey semantics?

I don't know why people didn't develop Hoare logics for lambda-calculi earlier. The first work to get this right was Honda et al's

A Compositional Program Logic for Polymorphic Higher-Order Functions

There were some earlier attempts before this, but they didn't quite nail the problem, for example: how do you denote the value of a functional program? What piece of syntax corresponds to the function space constructor? There are a couple of little things that need to be gotten right.

Let me speculate: maybe the main issue was that Hoare logic was typically concerned with stateful computation. If you combine state and higher-order functions, you immediately have to deal with aliasing, e.g. programs like

$$\lambda x^{\mathsf{Ref(Nat)}}.\lambda y^{\mathsf{Ref(Nat)}}.(x := !x+1; y := !y+1),$$ as well as local store and recursion through the store. These were only solved in the early 2000s in works like An observationally complete program logic for imperative higher-order functions (recursion through the store); A logical analysis of aliasing in imperative higher-order functions (aliasing), Logical Reasoning for Higher-Order Functions with Local State (full local store). At the same time Separation logic tackled the aliasing problem form a different angle.

This work has been implemented in Coq by A. Charguéraud in his work, and that  is also used in the Javascript semantics now.


From CFG to PDA is a simple construction. Set axiom $S$ as initial pushdown symbol. If the topmost symbol of the stack is nonterminal replace it according to a production of the grammar. If the topmost symbol is a terminal we are forced to read the same symbol from input tape (and pop the symbol). That is called expand-match. See wikipedia. The resulting PDA is single state, acceptance by empty stack.

(added) Your problem is on a special type of grammar, linear context-free. That means in every step of the derivation there is exactly one nonterminal. You can mimic this using a different construction. Basically the nonterminal is the state. All terminal symbols to the left are read, those to the right are pushed, to be read later. For $S\to aaBb$ the PDA goes from state $S$ to state $B$ while reading $aa$ (in usual models that takes two steps) and pushing $b$.

On your construction (it seems of the latter type). Concretely: the grammar generates $a$'s and $b$'s in a two-to-one / one-to-two ratio. In general: in order (for yourself) to see why it doesn't work you have to try to formulate the meaning of the states. How do they relate to things happening in the grammar?


State of variables in dynammic programming

Dynamic programming was
invented/discovered by Richard Bellman as an optimization technique.
The notion of state comes from Bellman's original presentation of
Dynamic Programming (DP) as an optimization technique. This is
presented for example in the Bellman equation entry of Wikipedia.

The technique was then extended to a variety of problems.

You might usefully read the Wikipedia presentation, I think. The
concepts you are interested in, including that of states and state variables, are described there. It may still be
some work to see how it fits the algorithm you have to explain.


Updating the distances matrix after single edge was decreased

Let me start with the setup, for the simpler case of a directed graph. We are given a weighted directed graph $G$ (with non-negative weights), and for every two vertices $s,t$, the distance $\delta(s,t)$ of a shortest directed path from $s$ to $t$. We modify $G$ to a new graph $G'$ by reducing the weight of an edge $(a,b)$, from $w(a,b)$ to $w'(a,b)$. The claim is that
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t)). $$
(In fact, the claim we want to prove is a bit stronger, since presumably we will be updating the metric sequentially rather than in parallel, but let's leave that for the future.)

In order to prove this formula, we consider two cases.

Case 1. Suppose first that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which doesn't go through the edge $(a,b)$. I claim that $p'$ is also a shortest path from $s$ to $t$ in $G$, and so $\delta'(s,t) = \delta(s,t)$. If not, let $p$ be a shorter path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) < w_G(p') = w_{G'}(p')$, contradicting the definition of $p'$.

It remains to show that $\delta(s,t) \leq \delta(s,a) + w'(a,b) + \delta(b,t)$. Suppose not, and take shortest paths $p_{sa}$ from $s$ to $a$ and $p_{bt}$ from $b$ to $t$, both in $G$. Let $p$ be the (not necessarily simple) path $p_{sa};(a,b);p_{bt}$, so that $w_{G'}(p) = \delta(s,a) + w'(a,b) + \delta(b,t)$. Since $w_{G'}(p) < \delta(s,t) = w_{G'}(p')$, this implies that $p'$ is not a shortest path in $G'$, contradicting its definition.

Case 2. Suppose next that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which goes through the edge $(a,b)$, say $p' = p'_{sa};(a,b);p'_{bt}$. Since $p'$ is a shortest path and all weights are non-negative, we can assume without loss of generality that $p'$ is simple, and so $p'_{sa},p'_{bt}$ don't go through $(a,b)$.

We claim that $p'_{sa}$ is a shortest path from $s$ to $a$ in $G$, and so has length $\delta(s,a)$. If not, let $p_{sa}$ be a shorter path from $s$ to $a$ in $G$. Without loss of generality, $p_{sa}$ doesn't go through $(a,b)$, since if it did, we would have $p_{sa} = q;(a,b);r$, and could replace $p_{sa}$ with $q$. Since $p_{sa}$ doesn't go through $(a,b)$, it has the same weight in $G$ and in $G'$, and so if we replace $p'_{sa}$ with $p_{sa}$, we would shorten $p'$ in $G'$, contradicting its definition. Similarly, $p'_{bt}$ is a shortest path from $b$ to $t$ in $G$, and so has length $\delta(b,t)$. We conclude that $\delta'(s,t) = \delta(s,a) + w'(a,b) + \delta(b,t)$.

It remains to show that $\delta(s,a) + w'(a,b) + \delta(b,t) \leq \delta(s,t)$. If not, let $p$ be a shortest path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) = \delta(s,t) < w_{G'}(p')$, contradicting the fact that $p'$ is a shortest path in $G'$.

In the undirected case, we are lowering the weights of two edges, and so the correct formula is
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t), \delta(s,b) + w'(b,a) + \delta(a,t). $$
(Note $w'(b,a) = w'(a,b)$.)


Using coloring optimization or coloring decision to solve coloring search

Given a graph $G$, we want to do two things:

Find the smallest $k$ such that $G$ is $k$-colourable,
Given such a $k$, find a colouring of $G$ with $k$ colours.

If we have an oracle for the decision version of the colouring problem, we can do both.

For the first part we can perform a search to find the optimal $k$. Even the naive approach here is okay, we can just sequentially ask if $G$ is $k$-colourable for $k=1,2,\ldots,n$. Then we make at most $n$ calls to the oracle. Of course we can perform a binary search and cut this down to $\log n$ calls. (Note that this is also how we solve the optimization version with the decision version).

Then given that we've worked out what $k$ is optimal, we can find a $k$-colouring of $G$ using the decision oracle. The only wrinkle is that the oracle doesn't take partial colourings, so we need a way of encoding in the graph that a particular vertex has been coloured a particular colour.

To do this we actually use the oracle on an auxilliary graph, which we will call $G^{+}$, that is $G$ plus a $K_{k}$ with some additional edges. Of course the $K_{k}$ needs exactly $k$ colours, so we can use its vertices to indicate which colours are available for a vertex. Let the vertices $\{k_{1},\ldots,k_{k}\}$ of the $K_{k}$ correspond to the colours $\{c_{1},\ldots,c_{k}\}$. Then we will indicate that a vertex $v$ in $G$ cannot be coloured with colour $c_{i}$ by making it adjacent to $k_{i}$. Furthermore if we colour a vertex with colour $c_{j}$ we will make it adjacent to every $k_{i}$ with $i\neq j$ (and not adjacent to $k_{j}$).

Then we repeatedly do the following:

Pick an 'uncoloured' vertex $v \in V(G)$.
For every vertex $u \in N(v)$, if $u$ has been coloured, then there is one $k_{i}$ such that $uk_{i} \notin E(G)$. Add the edge $vk_{i}$ to $E$.
For the remaining vertices $k_{j}$ such that $vk_{j}$ is not yet in $E$, we add all other edges between $v$ and the $K_{k}$ and ask the oracle if the new graph is $k$-colourable. If it is, we keep this graph and move on to the next vertex, if the answer is No, we undo step 3 and try with the next $k_{j}$.

Note that as $G$ is $k$-colourable, there is some $k_{j}$ that step three will work with. Then when we have processed every vertex, each vertex in $G$ is not adjacent to exactly one vertex in the $K_{k}$, this indicates which colour the vertex can be coloured with to obtain the colouring. From step 2, we see that this cannot be the same colour as any of its neighbours.

At step three we make at most $k$ calls to the oracle, and we do this for each vertex in $G$, so in total we make at most $(k+1)n$ calls to the oracle (including the search for $k$).


What is the best of given hashfunctions?

The question is not well-defined, since its unclear what you mean by "best".

I suspect that the intended answer is what you said and that you are using open addressing. Then, for a given $x$, $h_2$ would eventually return all possible values in $\{0, \dots, 999\}$ (since $17$ and $1000$ are coprime). $h_1$ would only return $\frac{1000}{5} = 200$ distinct values, and $h_3$ would only return $\frac{1000}{\textrm{gcd}(32,1000)} = \frac{1000}{8}=125$ distinct values.


Why using finite automata in implementing lexical analyzers

Speed and simplicity. A regular expression is a compact and declarative specification of lexemes. For most realistic regular expressions, simply writing code to mimic that specific regular expression would likely be something like an order of magnitude longer and less clear. This is especially true if you want high-performance.

A regular expression, on the other hand, can be compiled to very efficient code and is relatively simple to understand. You also get guarantees that are difficult or impossible to verify of code.  For example, a regular expression is guaranteed to be implementable using only a fixed, finite amount of memory and matching is, of course, guaranteed to terminate. This is very similar to the reasons we use primarily SQL to query relational databases rather arbitrary code.

So far this has been an answer to the question of modeling/implementing lexical analysis with regular expressions, and not to why we would implement regular expressions with DFAs. Again, the main reasons are speed and simplicity. There are however, many other options including: directly interpreting the regular expression operators, compiling regular expressions to machine code, differentiating regular expressions, NDAs clearly, converting a regular expression to a CFG and applying CFG techniques. Many of these approaches are arguably "inherently" slower than DFAs, e.g. using CFG techniques suggests that there will be overhead to support a degree of flexibility that is not used.

There are two obvious ways of implementing a DFA at least when the alphabet is reasonably small. One is to have a two dimensional table indexed by state and character. This approach is modular in that you can write the matcher once and just change the language by providing a different table (perhaps dynamically). Matching involves incrementing a pointer, one 2D table lookup, and a highly predictable jump. A second approach is to "store the state in the instruction pointer/program counter" by having each state be its own block of code. Matching in this case involves incrementing a pointer and a(n unpredictable) indirect jump. Ignoring instruction/data caching and branch prediction effects, it's hard to conceive of a more efficient approach than these. You are looking at two or three machine instructions per character of input. In the latter case, we can improve on the instruction caching and branch prediction performance by combining blocks of code together. Again, all this can be handled by a tool that takes a regular expression as input. There's no real way to beat this latter approach to implementing DFAs in performance except by improving instruction caching or branch prediction.


Independent Set Problem Variant, Induction

Hint:  Suppose you have a graph $G = (V,E)$ which is yes, and then there is a vertex $v \in V$ such that $G - v$ (the graph where you have removed $v$ from the graph) is no.  What can you say about $v$ and $G$?

Let us take an example, namely the following graph:

$G= (\{a,b,c,d\}, E=\{ab, bc, cd, ad, ac\})$

a —— d
| \  |
|  \ |
b —— c

and with $k=2$.  This is currently a yes instance.

First we ask:  If we delete $a$ from $G$, will the resulting instance still be a yes instance?

     d
     |
     |
b —— c

The answer is yes, this graph is still a yes instance.

Then we delete $b$ and ask the same question:

     d
     |
     |
     c

The answer is now no, this instance is no longer a yes instance.  Hence we cannot delete $b$.  Instead we try to delete $c$:

     d

b

The answer is still yes, and $|V(G')| = k$, so we conclude that $\{b, d\}$ is an independent set in $G$ of size $k$.


Unfeasible linear program becomes feasible if a variable is removed

There is (unless $P=NP$) no polynomial time algorithm for this problem, since the problem is $NP$-hard by reduction from Subset Sum. If you set $l_i=u_i$ then the problem is to determine if there is a subset of the $u_i$ that sums to $C$ (which is the Subset Sum problem).

If your problem did not allow $l_i=u_i$, if you were to require that $l_i<x_i<u_i$, you could get around this by setting $10000\cdot l_i<x_i<10000\cdot u_i + 1$ which for sufficiently large values of $10000$ ensures that $x_i$ will be "close enough".


Hamming code -- identical parity bits for different errors

When we say that a Hamming code detects (up to) 2 errors and can correct 1, we mean just that:

There is an error-detection algorithm that returns NO if there are no errors and returns YES if there are one or two errors. There is absolutely no guarantee when there are more errors.
There is an error-correction algorithm that gets a possibly corrupted word and outputs the original codeword, assuming that there was at most one error. There is absolutely no guarantee when there are more errors.

In real life we cannot always guarantee that there are at most X errors in every block, and this is handled by an "outer code", for example the checksum that you mention.


Minimum absolute value of subset sums of integer values

We give a Turing reduction from the $\mathrm{SubsetSum}$ problem.
Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find a set $X \subseteq A$ such that $\sum_{x \in X} x = k$ and define the set $A' = A \cup \{- k\}$.
We want to show that $f(A') = 0$ if and only if $(A, k) \in \mathrm{SubsetSum}$:

Suppose that $(A, k) \in \mathrm{SubsetSum}$. Then there exists a set $X \subseteq A$ such that $\sum_{x \in X} x = k$, i.e. the sum over the elements of $X \cup \{-k\} \subseteq A'$ is $0$, implying $f(A') = 0$.
Otherwise, we have $(A, k) \notin \mathrm{SubsetSum}$. As $A$ only contains positive integers but no subset of $A$ sums to $k$ we infer that any subset of $A'$ sums to some nonzero value.

It follows that if $f$ is computable by some polynomial time DTM then $\mathrm{SubsetSum}$ can in turn be decided in polynomial time, showing that $\mathsf P = \mathsf{NP}$.


The problem is NP-complete because it is in NP and captures the partition problem with $n = 2$ and $m = \frac12 \sum_{i = 1}^q{w(o_i)} - \frac12 \min_{i}w(o_i)$. If an equal weight partition exists, then the items can be packed in two bins each of weight $\frac12 \sum_{i = 1}^q{w(o_i)}>m$. If it doesn't, then one of the two bins would have weight at most $m$.


Neural network to detect connected parameters

That's easy.  Find all configurations where parameter 1 has value A; throw away all the rest.  Now you can easily test whether all the remaining parameters have the same value for parameter 2 (just scan through them and see if they all have the same value as the first); you can do that for parameter 3; and so on.  No fancy algorithm is needed -- it's straightforward to program with a simple linear scan.


Is the exponent in floating point numbers signed or unsigned

This is mostly a matter of interpretation. For IEEE 754 floating point numbers (one of the most common implementations), an exponent bias is used:

  In IEEE 754 floating point numbers, the exponent is biased in the engineering sense of the word – the value stored is offset from the actual value by the exponent bias. Biasing is done because exponents have to be signed values in order to be able to represent both tiny and huge values, but two's complement, the usual representation for signed values, would make comparison harder.

  To solve this problem the exponent is biased before being stored, by adjusting its value to put it within an unsigned range suitable for comparison.

For floating point numbers with single-precision, the effective exponent has 8 bits and ranges from -126 to 127. However, the internal exponent ranges from 1 to 254, meaning that 127 has been added to the effective exponent.
(This means it is valid to say that the exponents of floating point numbers are stored as unsigned integers, even though this is a matter of interpretation.)

In addition to the reasons outlined above, another good reason for this encoding is that two special exponents are required for floating point encoding according to IEEE 754: Floating point numbers can also store the values Infinity, NaN and denormalized values which would be too small to store them in the usual format.

The special constants used are the internal exponents $0$ and $2^r-1$ (where $r$ is the number of bits of the exponent), so in binary $0...0$ and $1...1$. These values are easy to recognize. Note that these exponents belong to effective exponents that are barely ever used. If we had used the internal exponent $0$ without shifting the range, it would be the same as the effective exponent $0$, making it difficult to encode common number ranges.


I hope this answer will help you to understand the mapping. Any DFA is also a PDA. The state transitions in the DFA are similar for PDA without stack. For every transition you perform in DFA, make the similar transition in PDA and do not push/pull from stack.

For a transition

In DFA : $\delta(q_x,0) \rightarrow q_y$

In stack : $\delta(q_x,0) \rightarrow (q_y,\epsilon)$

For accepting state

In DFA : $\delta(q_x,0) \rightarrow q_f$

In stack : $\delta(q_x,0) \rightarrow (q_f,\epsilon)$


Is the intersection of two context free languages recursively enumerable?

This result more easily follows from the fact that every context-free grammar is recursively enumerable, by enumerating all parse trees. The intersection of any two r.e. languages is r.e. - just enumerate them both and output every word that appears on both lists. The other direction (given by the quotation you found) is more interesting.

Edit: As Huck correctly comments, there are actually efficient algorithms for deciding membership in context-free languages. But the argument above holds for the most general grammars possible, in which case we prove that the language corresponding to any grammar is recursively enumerable. (Replace parse trees with the a sequence of rule applications.)


How to determine time complexity with a simple way?

Asymptotic notation satisfies the following two useful properties:
$$
\Theta(f(n)) + \Theta(g(n)) = \Theta(\max(f(n),g(n)) \\
\Theta(f(n)) \Theta(g(n)) = \Theta(f(n)g(n))
$$
Using these, you can determine that $f(n) = \Theta(4n^2\log^2 n)$.

Now you can check each of 1.-5. individually, using the fact that $n^a\log^bn = O(n^c\log^dn)$ iff $a < c$ or $a=c$ and $b \leq d$.


The underlying type theory of HOL/Isabelle

I don't think Isabelle's implementation manual is a good place to look at this. It may certainly contain links to the explanation but you can find instead a pedagogical introduction in section 2 of this thesis.


This can be solved in polynomial time.

Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares.

If no square has $x$-coordinate in some interval $[a, b]$, we can compress that interval into a single point. Then, the squares have coordinates in range $[0, 2m - 1]$. We will do DP in $\mathcal{O}(m^{5})$.

We calculate a DP with a state for every rectangle $(x_{0}, y_{0}), (x_{1}, y_{1})$.

We say that some snake is inside the rectangle if at least two of its squares are inside the rectangle. If at least two of some snake's squares are outside the rectangle, we say it is outside the rectangle. Notice that a snake can be both inside and outside the rectangle.

Say there are $k$ snakes inside the rectangle. The DP will represent whether we can separate the $k$ snakes with at most $k-1$ fences while obeying the trimming rules.

If any snake is both inside and outside the rectangle, we automatically fail and set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 0$. If only one snake is inside the rectangle, we set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 1$.

Otherwise, for every $x_{0} < x < x_{1}$, we will try to add a fence at this $x$-coordinate. If $DP[x_{0}, y_{0}, x, y_{1}]$ and $DP[x, y_{0}, x_{1}, y_{1}]$ and no snake inside the rectangle is outside of both of the two rectangles the fence splits our rectangle to, the fence works and we set the value of the DP to true. We similarly loop $y$-coordinates inside the rectangle. If no working fence was found, we set the DP to false.

In the end, the algorithm outputs $DP[0, 0, 2m-1, 2m-1]$

This DP can be optimised to $\mathcal{O}(n^{5} + m)$ by trimming states from the DP. We can assume that the DP-box doesn't start or end with an empty column or row, therefore there has to exist some snake with the leftmost square in the box, and we can store $x_{0}$ as the index of that snake, and whether the leftmost square in the box is the leftmost or second leftmost square of that snake (It cannot be any square after that, since then the snake would be outside the box). Storing $y_{0}, x_{1}, y_{1}$ similarly gives us $\mathcal{O}(n^{4})$ dp-states. We can further loop the $x$-coordinate of a fence over just the first and last $x$-coordinates of squares of snakes in the rectangle plus minus at most one, as every other fence either trims too much from a snake or would be equivalent to a fence placed directly to the left of it. Loop similarly over $y$. The number of such coordinates is $\mathcal{O}(n)$.


Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time.
It follows since the graph BFS traverses is guaranteed to be connected, hence $\forall v:deg(v)\ge 1$. Thus $|E_{traverse}| \ge \frac{|V_{traverse}|}{2}$ where $E_{traverse}$ and $V_{traverse}$ are the sets of edges and vertices the BFS "saw" while running.
Clearly, the BFS works in $O(|E_{traverse}|+|V_{traverse}|)$ but since $|V_{traverse}|=O(|E_{traverse}|)=O(|E|)$, we can conclude that the BFS instance runs in $O(E)$.
Note: This is only true if the BFS is ran only from one source, unlike the usual BFS algorithm description that starts the traversal from a node we didn't mark yet if we finished the last traversal instance.

Honestly, I don't know about Thorup's algorithm, so I can't answer this part of the question about it. However, I know that BFS works for both directed and undirected graphs, but doesn't work with natural weights.


Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make?

It is known.  As your final statement says, $\mbox{BPP} \subseteq \Pi_2 \cap \Sigma_2$.  It is called the Sipser–Gács–Lautemann theorem.  (All though your "so" is somewhat misleading.)

It can be strengthened to $\mbox{BPP} \subseteq \mbox{MA} \subseteq \mbox{S}^P_2 \subseteq \Pi_2 \cap \Sigma_2 \subseteq \Pi_2$ (see also Arthur-Merlin protocol).


I don't like this proof so much. Here is a different one.
We can assume without loss of generality that $A_1 \leq \cdots \leq A_N$. Consider an optimal solution $\{i_1,\ldots,i_\ell\}$, where $i_1 < \cdots < i_\ell$. In particular,
$$
A_{i_1} + \cdots + A_{i_\ell} \leq B.
$$
Intuitively, it is clear that $A_1 + \cdots + A_\ell \leq B$ (we will prove this formally in a moment), and so the greedy algorithm will also choose at least $\ell$ houses.
Now let us prove that $A_1 + \cdots + A_\ell \leq A_{i_1} + \cdots + A_{i_\ell}$.
I claim that $i_j \geq j$. Indeed,
$$
i_j \geq 1 + i_{j-1} \geq 2 + i_{j-2} \geq \cdots \geq j-1 + i_1 \geq j.
$$
This implies that $A_{i_j} \geq A_j$, and so $A_{i_1} + \cdots + A_{i_\ell} \geq A_1 + \cdots + A_\ell$.


There is no formal definition. A subproblem is just a (usually smaller!) problem that you solve on the way to solving the problem you're really interested in.


You will hardly find anything more comprehensive than the 400-page dynamic survey of Gallian [1] discussing almost 2300 references.

[1] Gallian, Joseph A. "A dynamic survey of graph labeling." The Electronic Journal of Combinatorics 16, no. 6 (2016): 1-219.


Graphs with bounded degree and small max independent set

First of all, the correct bound is $n/(\Delta + 1)$. This is tight for unions of cliques of size $\Delta+1$. If you want a connected graph, take a union of $\Delta$-cliques and connect them in a path or a cycle. This gives $n/\Delta$, so there is a small loss over the lower bound $n/(\Delta+1)$. If you want a connected regular graph, add a matching to the previous graph.


What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?

I would argue that this does not matter. Consider the case where there are multiple shortest paths from $s$ to $t$ in $G$. In the case of using $<$, we define the shortest path to be the first shortest path we come across. This is because latter paths will only be equivalent in length and thus not satisfy the invariant. However, in the case of using $\leq$ we define the shortest path to be the last shortest path we come across. This is because latter paths will be equivalent in length and thus trigger the invariant.

My point is that with $<$ or $\leq$ we could essentially flip the ordering of nodes in the adjacency list of adjacency matrix to mimic what the other comparison operator would do.


Paxos: Responding to Reordered Prepare Requests

Correct. Another way to think about Paxos is as a two step process:

Gaining permission to propose a value
Actually proposing a value

The act of successfully gaining permission from a majority of peers to propose a value explicitly precludes the possibility of any previous proposal from being accepted by a majority of peers.


Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

You have found a bug in one of the most famous textbooks on computer science!

While there are $n$ days, there are only $n-1$ changes in price of stock. So there are $\binom{n-1}{2}$ subarrays of the array of the changes in price of stock, assuming that a subarray starts and ends at different indices.
That explain away, I believe, why the books says "we still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days".

However, in fact, you are right that we still need to check $\binom n2$ subarrays.
Let $B$ be the array of the daily prices for a period of $n$, starting at index (day) 0. Let $A$, as in the book, be the corresponding array of the price changes, starting at index (day) 1. If you select to buy on day $i$ and sell on day $j$, making a profit of $B[j]-B[i]$, it corresponds to subarray $A[i+1\,..\,j]$, i.e., $(A[i+1], A[i+2], \cdots, A[j])$. Please note the change of indices from $i$ and $j$ in $B$ to indices $i+1$ and $j$ in $A$. While $i$ and $j$ must be different always as "you are allowed to buy one unit of stock only one time and then sell it at a later date", $i+1$ and $j$ are the same when $j=i+1$, i.e., when you sell the next day.
Let us verify the sum of selected numbers in $A$ is indeed $B[j]-B[i]$. $$\begin{aligned}
&\quad A[i+1]+A[i+2]+\cdot+A[j]\\
&=(B[i+1]-B[j])+(B[i+2]-B[i+1])+\cdot+(B[j]-B[j-1])\\
&=B[j]-B[i].\end{aligned}$$
Note the formula does hold when $j=i+1$.
Besides the subarrays of $A$ that start and end at different indices, we must consider the subarrays with the same starting index and ending index. There are $n-1$ of them, i.e., the subarray whose only element is $A[1]$, the subarray whose only element is $A[2]$, ... and the subarray whose only element is $A[n-1]$. Since $\binom{n-1}2+(n-1)=\binom n2$, we still need to check $\binom n2$ subarrays.
For example, if the daily prices for a period of $3$ days are $B=(85, 105, 102)$, the changes of prices are $A=(20, -3)$. If we do not check the subarray of $A$, $(20)$, which stands for buying at price $85$ on day $0$ and selling at price $105$ on day $1$, we will miss the optimal profit, $20$.

This simple and obvious bug is not listed on the errata page for Introduction to Algorithms, Third Edition. It is incredible that this bug has been living comfortably in that popular book for over ten years before you pointed out explicitly.
On the other hand, many people might have been aware of that bug, although I did not notice it. The focus of that mistaken statement is "we still need to check $\Theta(n^2)$ subarrays for a period of $n$ days". The actual number of subarrays that should be checked is not that critical, as long as its level of asymptotic growth is correct. While misleading otherwise, that bug does not harm much the development of a better algorithm.


Set which is easy to sample, but difficult to sample from its complement

We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it.

A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\frac{2}{3}$ of the elements in $S$.

However, sampling from the complement of $S$ in the general case is even harder than you require: there exist sets $S$ such that there exists no Turing machine that given $n, x = 0^{n}$ as input outputs any string in $S$ of length $n$ starting with $1$. Furthermore, we can explicitly construct such a set $S$.

This is easy to prove by a diagonalisation argument. Let $K_{w, n}$ be the set of strings of length $n$ starting with $w$. There is a countable number of Turing machines, so let $M_{i}$ be the $i$th Turing machine. For $n \geq 2$, if $M_{n-1}$ on input $n, x = 0^{n}$ doesn't halt or outputs a string in $K_{00, n}$, set $S_{n} = K_{1, n} \cup K_{00, n}$. Otherwise set $S_{n} = K_{1, n} \cup K_{01, n}$. Then $S = \{\epsilon, 1\} \cup \bigcup_{i = 2}^{\infty} S_{i}$ is one such set.


The theoretical upper bounds for duplicate detection in a set of objects?

I think you're asking about the "Element Distinctness Problem."

Assuming you're talking about time complexity (number of comparison operations) rather than space complexity, "lower bound" instead of "upper bound," and that you can't hash elements of your multiset (which gives you $O(n)$ expected time), then the best you can do is $\Theta(n \log n)$.


Let $M=\max_i|A_i|$.

Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.

Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$ elements of the array, such that the last element is in the range $\left[j,j+2^k\right)$. Then we have $f(0,j,0)=0$,
$$f(i,j,0)=|A_i-j|+ \min\left\{f\left(i-1,j-H,\hat{k}\right),f\left(i-1,j+H+1-2^{\hat{k}},\hat{k}\right)\right\}$$
where $2^{\hat{k}}>H$, and
$$f(i,j,k)= \min\left\{f(i,j,k-1),f\left(i,j+2^{k-1},k-1\right)\right\}$$
for $k>0$. Note each entry can be calculated in $O(1)$ time if we calculate them in some proper order.

Note in an optimal solution, the final $A_N$ must be in the range $[-(M+NH),M+NH]$ (otherwise the final elements are all either greater than $M$ or less than $-M$, which is not optimal), so we need to calculate $f(i,j,k)$ for all $i,j,k$ such that $0\le i\le N$, $j\ge -(M+(2N-i)H)$, $k\ge0$ and $j+2^k\le M+(2N-i)H+1$. The time complexity is $O\left(N(M+NH)\log (M+NH)\right)$, while the naive $f(i,j)$ solution takes $O(N(M+NH)H)$ time.

You can further use the range minimum query technique to reduce the time complexity to $O(N(M+NH))$.


Efficient algorithm for determining if $\pm c_1 \pm c_2 \dots \pm c_n = 0$

Hint: This is just the well-known NP-complete problem PARTITION.


If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems  (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$).

If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^n$. This problem can indeed be solved (and thus verified) in polynomial time.

If you choose to talk in terms of function problems, then the problem is given $n$, compute $2^n$. This cannot be done in polynomial time, even with non-determinism, but just because the output is exponentially big with respect to the input. Verification has nothing to do here.


Swap space management during pure demand paging

To answer this question I will visit some prerequisite understanding. Pure demand paging cannot be accomplished without hardware support. All modern computer architectures support paging, however many have different implementation details.

x86 processors use what is called a page table to keep track of virtual address spaces and page mappings, as well as bits about access privilages and, more relevant, whether or not that page is even present in physical memory. Violations trigger page faults which are trapped by the OS.

For more information on that, see this article.

In order to answer the question of page swapping, we must first visit the question of how the operating system keeps track of what pages are used by what process and how they are allocated. There are many different data structures that can be used for such. A flat bit array marking whether a frame is allocated or not is one way. Linked lists or stacks is another. With pure demand paging, allocated pages are not actually marked as present when they are allocated. This has the effect that no physical ram is set aside for a process until it actually writes to it. Once it does, the hardware throws a fault which the OS traps, and then the OS uses a swapping algorithm if there are no available physical pages to assign to the already allocated virtual page.

For more information on page frame allocation, see here. There you will see a general overview of some suitable datastructures.

Once a suitable algorithm for page allocation is implemented, another for allocating disk space for swapping must be chosen. Windows, as an example, has historically used a flat file in the filesystem for page swapping. I would imagine that for each node in the datastructure keeping track of allocated pages there is an assocated pointer to an offset in the file, indicating the position of the page in the disk. Unix-like operating systems have traditionally used separate partitions for page swapping which is arguably faster since there is no filesystem layer.

It is also possible to divorce the swapping algorithm datastructures from those of the allocation algorithm, however the two are related so this is probably not often done.

I hope that answers your question despite the relative brevity with which I have treated it. I found that the best way to learn about operating systems is to dive into the sometimes nasty architectural specific details that can be found in sites like wiki.osdev.org and  www.osdever.net which specifically deal with hobby OS making and provide excellent tutorials on such details.


Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?

There are two possible interpretations of the condition on $i,j,k$:

$(i \leq j \lor j \leq i) \land j = k$. This condition is equivalent to just $j = k$, and so the language in question is $\{ a^i b^j c^j : i,j \geq 0 \}$, which is a prototypical context-free language.
$i \leq j \lor (j \leq i \land j = k)$. A linear-bounded automaton can decide this language (exercise), so it is context-sensitive. On the other hand, using the pumping lemma you can show that it is not context-free (exercise).

I would guess that the second interpretation is the one that was intended.


Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)?

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,...  is an enumeration of all TMs" is replaced by "$M_1,M_2$,...  is an enumeration of some TMs"

Here is a formal proof.

Suppose $L$ is recognizable. Then by definition, $L$ is the language accepted by some Turing machine $M_k$ for some $k$.  Consider $a^k$.

If $a^k$ is not in the language accepted by $M_k$, then by definition of $L$, $a^k\in L$. By the definition of $M_k$, $a^k$ is accepted by $M_k$, which is a contradiction.
If $a^k$ is in the language accepted by $M_k$, then by definition of $L$, $a^k\not\in L$. By the definition of $M_k$, $a^k$ is not accepted by $M_k$, which is a contradiction.

Since we always get a contradiction, our assumption $L$ is recognizable must be wrong.

Here is an easier proof, as presented in your comment.

For all $n$, $L\not=L_n$, since $a^n\in L$ $\Leftrightarrow$ $a^n\not\in L_n$, i.e, the membership of $a^n$ in $L$ and the membership of $a^n$ in $L_n$ is different. Since $L_n$ for all $n$ enumerates over all recognizable languages, $L$ is not recognizable.

In fact, the construction of $L$ uses the classic technique to construct a non-member of a given set, the diagonal argument that was discovered/created by the great mathematician Georg Cantor. "It has been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox." The proof of the undecidability of the halting problem can be considered as an application of the diagonal argument as well.


Fuzzy string matching algorithm with allowed events?

What you want is the so-called (optimal) local alignment of two strings. You can use the standard local alignment algorithm but allow insertions/deletions at the beginning and end (of the the shorter string) for free.

In the classic dynamic programming algorithm, this corresponds to initialising the first row (resp. column) with zero, removing the penalty for steps along the last row (resp. column) and finally looking for the minimum cost in the last row (resp. column) and backtrack from there. You can find alternatives in the Wikipedia article.

Restricting the number of deletions or insertions used can be implemented by adding counters to the cell values; if adding one would take one over the respective limit (stored globally), assign cost $\infty$ to the respective operation.


How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem

Welcome to the site! Let $G = (V, E)$ be a undirected graph.
If $G$ is Hamiltonian, then there exists a simple cycle $C$ in $G$ containing every vertex, i.e. the length of $C$ is $|V|$.
Note that if you delete any edge $vw$ from $C$, you end up with a path of length $|V| - 1$ between $v$ and $w$.
Conversely, if you find a simple path $P$ of length $|V| - 1$ between two vertices $v, w$ connected by an edge, you can add the edge $vw$ to $P$ to obtain a Hamiltonian cycle (as $P$ cannot contain $vw$ due to being a simple path).
Also observe that the choice of $v$ and $w$ is arbitrary as long as they are connected by an edge.

So we can obtain the following reduction:
Starting from some graph $G = (V, E)$, pick some edge $vw \in E$ and delete it to obtain a new graph $G' = (V, E \setminus \{vw\})$.
Using the observations we made, it follows that $G'$ has a path $P$ between $v$ and $w$ of length $|V| - 1$ if and only if adding $vw$ to $P$ yields a Hamiltonian cycle in the original graph $G$.
As $G'$ can be computed from $G$ in polynomial time, we have a polynomial reduction $\mathrm{Hamiltonian Cycle} \leq_\mathsf{P} \mathrm{Long Path}$, thus showing that your problem is $\mathsf{NP}$-hard (because $\mathrm{Hamiltonian Cycle}$ is $\mathsf{NP}$-hard already).

To show that $\mathrm{Long Path}$ is in $\mathsf{NP}$ we note that a path in a graph can be efficiently encoded as a list of its edges and checking that a string actually encodes a path in the graph and then counting the number of edges to determine whether it is long enough can be done in polynomial time.

Hence we find that $\mathrm{Long Path}$ is $\mathsf{NP}$-complete.


If $L$ is NOT Turing-recognizable, does that mean that super sets with $L$ are also not?

If $L'$ were Turing-recognizable then there would be a TM $M$ which would enumerate every string in $L'$. In particular, we could construct a TM that would print on the tape every string in $L'$. Then we could easily modify this machine to enumerate the language $L$. Just do not print the first symbol on the tape (skip the initial $0$). Thus we construct a machine which enumerates $L$. But $L$ is not Turing-recognizable (not r.e.) by assumption. A contradiction.

$L'$ in your example may be expressed as a concatenation of languages $\{0\}$ and $L$, that is, $L' = \{0\}L$. However, we cannot generalize this result to arbitrary languages. For example, $\{0,1\}^*L = \{0,1\}^*$ is r.e. even if $L$ is not r.e. language on $0$ and $1$ containing empty string.

As for your claim "a not Turing-recognizable language is a subset of another language, then that language is also not Turing-recognizable", it is false too, since a not Turing-recognizable language $L$ on $0$ and $1$ is a subset of $\{0,1\}^*$ which is definitely r.e., even decidable.


What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

Use Dijkstra's algorithm.  It is quite efficient, and on a graph with only 300 nodes, it will run extremely fast, so fast that it's not worth worry about.

You mentioned in a comment that your main concern is that the algorithms are described for directed graphs, but you have an undirected graph.  No worries.  You can apply Dijkstra's algorithm to an undirected graph, too.  Whenever your graph has an undirected edge between vertices $u$ and $v$, think of that as equivalent to the two directed edges $u \to v$ and $v \to u$.  In this way, you can convert your undirected graph to a directed graph -- and then you can apply Dijkstra's algorithm to the result.  The same goes for any other algorithm for directed graphs; it can be applied to an undirected graph in the same way.


Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?

Just because that UTM itself requires $2$ tapes to do its task that efficient. Removing one tape, the magic is gone.

But assuming you have the fantasy power to do efficient $1$-tape simulation, what gains do we have then?

That should be the question rather than your question.


How strong is equivalence of lambda expressions?

In general, there is always an infinite number of "computationally different" functions that are extensionally equal: take for instance the "$3n+1$-function" $g$, and for any function $f$ define $G_f$ to be:

$$ G_f(n)=\begin{cases} f(n) & \mbox{if }g(n)\mbox{ cycles at }1 \\ 0 & \mbox{otherwise}\end{cases}$$

This function is (probably) extensionally equal to $f$ for every $f$, but this is (possibly) not provable in $\mathrm{PA}$, or indeed in the weak framework of $\beta\eta\alpha$-conversion.

More pragmatically, the identity function $\lambda x.x$ and the "stupid identity"
$$ \lambda n.n\ (\lambda x\ f.x)\ (\lambda m\ x\ f.f(m\ x \ f))$$

Denote the same function $\mathrm{id}:\mathbb{N}\rightarrow \mathbb{N}$, under the usual church encoding, but are not $\beta\eta$-equal, as can easily be seen (they are both in normal form).


It will be easier to analyze things if we break them down into several different procedures:

int I(int n) { for (i = 1; i <= n; i++) J(i); }
int J(int n) { for (j = 1; j <= n*n; j++) K(j); }
int K(int n) { for (k = 1; k <= n*n; k++) sum++; }

Instead of measuring time complexity, let us use instead the number of times sum is incremented as our complexity measure. Also, let $I(n),J(n),K(n)$ double as the complexity of the functions with matching name.

It is not hard to see that $K(n) = n^2$. Therefore
$$
J(n) = \sum_{j=1}^{n^2} K(j) = \sum_{j=1}^{n^2} j^2.
$$
Now we invoke the formula $\sum_{j=1}^m j^2 \sim m^3/3$. Substituting $m = n^2$, we get
$$
J(n) \sim \frac{n^6}{3}.
$$
Continuing,
$$
I(n) = \sum_{i=1}^n J(i) \sim \frac{1}{3} \sum_{i=1}^n i^6 \sim \frac{1}{21} n^7.
$$
Some of these estimates are not completely rigorous, but you can make them rigorous with a bit of work.


Let $w$ be the node to be deleted

1) Perform standard BST delete for $w$.

2) Starting from $w$, travel up and find the first unbalanced node. Let $z$ be the first unbalanced node, $y$ be the larger height child of $z$, and $x$ be the larger height child of $y$. Note that the definitions of $x$ and $y$ are different from insertion here.

3) Re-balance the tree by performing appropriate rotations on the subtree rooted with $z$. There can be 4 possible cases that needs to be handled as $x$, $y$ and $z$ can be arranged in 4 ways. Following are the possible 4 arrangements:

a) $y$ is left child of $z$ and $x$ is left child of $y$ (Left Left Case)

b) $y$ is left child of $z$ and $x$ is right child of $y$ (Left Right Case)

c) $y$ is right child of $z$ and $x$ is right child of $y$ (Right Right Case)

d) $y$ is right child of $z$ and $x$ is left child of $y$ (Right Left Case)

Like insertion, following are the operations to be performed in above mentioned 4 cases. Note that, unlike insertion, fixing the node $z$ won’t fix the complete AVL tree. After fixing $z$, we may have to fix ancestors of $z$ as well (See this video if you have trouble visualizing the above mentioned cases).

Courtesy of Geeksforgeeks.


In step 4 P2 tests the lock and sees the value is 0.  But testing the lock is just a read operation, so P2 has the cache line in state shared.  In step 5 P2 executes a swap operation, which is both a read and a write, so requires a coherence action (invalidate P1's shared copy) to acquire the cache line in state exclusive.  It's a "cache miss" in the sense that the required state in the cache is incorrect, not in the sense that the data is missing.


Which non-regular languages are in $AC^0$?

Languages in $AC^0$ can be more complicated than naive intuition might suggest.

Obviously, $AC^0$ contains $\{a^n b^n c^n\}$, which is non-context-free.
Every unary language is in nonuniform $AC^0$; for example, the halting problem expressed in unary.
Addition can be implemented in $AC^0$ with a carry-lookahead adder. Here the input is $2n$ bits representing two numbers, and the output contains $n+1$ wires (equivalently, each output bit can be realized in $AC^0$)
Multiplexing: $\{w x: |w|=2^n, |x|=n, w[x] = 1\}$ is in $AC^0$.

A multiplexer is a function on $2^n+n$ variables which outputs the value of one of $2^n$ variables, where the index is determined by the $n$ variables. (The same holds if the index is written in unary.)
Computation of 3SAT formulas is in $AC^0$.

The input consists of $n$ variables, followed by some clauses, each one contains three literals, where each literal is an index of the variable (unary or binary, does not matter) and a bit indicating possible negation. You can evaluate the literals with multiplexers and then add a layer of ORs and then a big AND on top.
$AC^0$ does not contain majority, but it contains approximate majority: a function that is equal to majority if the output is $\geq \frac{1}{2}+ \varepsilon$ zeroes or ones. See "Approximate Counting with Uniform Constant-Depth Circuits" by Ajtai.

$AC^0$ is closed under logical operations, concatenation and composition, so you can combine above examples. Now you should feel some respect for $Parity \notin AC^0$ and other circuit lower bounds!


Planarity conditions for Planar 1-in-3 SAT

Yes you can. Actually you can even show that something stronger is true. The problem know as Positive Planar 1-in-3-SAT is NP-complete as shown by Mulzer and Rote.

In this version of 1-in-3-SAT, you require for every input formula that

you have three variables per clause, none of them negated
the graph of the formula is planar, even if you add the "backbone" between the variable vertices

The reduction is from Planar 3-SAT.


It is possible to improve on your second algorithm by using better algorithms for integer factorization.

There are two algorithms for integer factorization that are relevant here:

GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; finding all factors will take $O(\log C / \log(n \log C))$ times as long (which is relatively small compared to the running time of ECM).

Here $L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$.

That's a pretty horrendous-looking expression for the running time, but the important fact is that this is faster than the methods you mentioned.  In particular, $L_C[0.33,1.92]$ is asymptotically much smaller than $\sqrt{C}$, i.e., GNFS is much faster than trying all possible factors $\le \sqrt{C}$.  Also $L_{n \log C}[0.5,1.41]$ is asymptotically much smaller than $n \log C$, i.e., ECM is much faster than trying all possible factors $\le n \log C$.

So, the total running time for this method is roughly $\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$, and this is asymptotically better than your first method and asymptotically better than your second method.  I don't know if it is possible to do even better.


Are there any implementations of the spineless tagless G-machine other than in GHC?

I used this Google search:

"spineless tagless g-machine" site:github.com

and found 2 repos that (try?) to implement the STG in non-Haskell languages:

PHP: lechimp-p/php-stg

RPython ("restricted" subset of Python developed for Pypy): cgswords/laurens


Polynomial time algorithm for finding two or more vertex-disjoint cycles

The structure of graphs without two vertex-disjoint cycles is well understood (see for example Bollobás, Extremal graph theory), having been researched in 1965 by Dirac and the 17-year old Lovász (separately).

Theorem 1. Suppose that $G$ has minimum degree at least $3$. Then $G$ has no two vertex-disjoint cycles if and only if one of the following holds:

$G \setminus \{v\}$ is a forest for some vertex $v$.
$G$ is a wheel (a cycle plus a vertex connected to all vertices in the cycle).
$G$ is $K_5$, the clique on 5 vertices.
$G \setminus \{v,u,w\}$ is an independent set for some three vertices $v,u,w$.

Theorem 2. A graph $G$ has no two vertex-disjoint cycles if and only if either $G \setminus \{v\}$ is a forest for some $v$, or $G$ is obtained from one of the graphs $H$ in Theorem 1 by subdividing edges, adding a forest, and possibly connecting each tree in the forest by a unique path to $H$.

Theorem 1 can clearly be implemented algorithmically in polynomial time. In order to implement Theorem 2, we need to undo the subdivision and remove the forest and its attaching paths. We can identify the forest by removing isolated trees and identifying paths leading to trees. We can then undo the subdivision by compressing paths, reducing to the case of Theorem 1. It seems that everything can be implemented in polynomial time.


There are at least three encodings of (aspects of) Category Theory in Coq. Approaches using a proof assistant guarantee correctness by design, though I don't know whether they will enhance understand. You'll then have both the proof assistant and Category Theory to learn.

If you want a reasonably introductory, computer science-oriented book, it's hard to beat Categories and Computer Science by R. F. C. Walters. His examples are mostly about data types and automata, rather than programming languages and lambdas. Conceptual Mathematics by Lawvere and Schanuel is also quite digestable.

One approach combining these two is to use this Coq formalisation with Steve Awodey’s Book. The formalisation covers closely what is in the book. There's also a blog post about it.

That said, Category Theory is tough and its relationship with  programming quickly becomes quite distant, and so one needs to rely on one's mathematical background (which is now getting on to be 20 years old).


Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call:
$$\begin{gather*}
  a_{i+1} = b_i \\
  b_{i+1} = a_i \mathbin{\mathrm{mod}} b_i \\
\end{gather*}$$

In the imperative version, let $a'_i$ and $b'_i$ be the values of the variables a and b at the beginning of the $i$th iteration of the loop.
$$\begin{gather*}
  a'_{i+1} = b'_i \\
  b'_{i+1} = a'_i \mathbin{\mathrm{mod}} b'_i \\
\end{gather*}$$

Notice a resemblance? Your imperative version and your recursive version are calculating exactly the same values. Furthermore, they both end at the same time, when $a_i=0$ (resp. $a'_i=0$), so they perform the same number of iterations. So algorithmically speaking, there is no difference between the two. Any difference will be a matter of implementation, highly dependent on the compiler, the hardware it runs on, and quite possibly the operating system and what other programs are running concurrently.

The recursive version makes only tail recursive calls. Most compilers for imperative languages do not optimize these, and so it is likely that the code they generate will waste a little time and memory constructing a stack frame at each iteration. With a compiler that optimizes tail calls (compilers for functional languages almost always do), the generated machine code may well be the same for both (assuming you harmonize those calls to abs).


Finding a small Moore machine that checks the last four bits

Since you have been given an upper limit to number of states, the best way to go about solving this problem is to get a correct solution first independent of number of states and then minimize the automata. Every moore automata has a canonical unique automata of minimum number of states (meaning all minimum state automata are equivalent).

As the solution is following and you cannot minimize the moore automata any further, you can declare that you cannot solve the problem with 7 states:

By the way, minimization of moore automata is similar to minimization of deterministic finite automata. We need to find equivalent states and merge them. Refer DFA Minimization.


Formalization of the shortest path algorithm to a linear program

This formalization takes Dijkstra's algorithm and formalizes it as a network flow problem.

In the network flow problem, $b_i$ represents the amount of flow that enters or leaves a network at vertex $i\in V$. If $b_i > 0$ we say that $i$ is a source supplying $b_i$ units of flow. If $b_i < 0$ we say that $i$ is a sink with a demand of $|b_i|$ units of flow. Here $B(v)$ are $v$'s outgoing edges and $F(v)$ are $v$'s incoming edges. So the condition $\sum_{e\in B(v)} x_e - \sum_{e \in F(v)}x_e = b_v = 1$ means that I'm allowed to supply $1$ more unit of flow coming out of $v$ than going into $v$.

Now in the network flow algorithm I'm pushing flow into the sink node, in this case the root $r$. Since each node can supply only $1$ unit of flow, the amount of flow going into $b_r$ is $n-1$. So these equations are satisfied when each node pushes it's one unit of flow down to the sink node, enforcing that we find the shortest path from every node to $r$. Now you can see that $b_r=-(n-1)$ means that it expects the $1$ unit of flow from every node.

From this it should be easy to see that $x_e$ represents the number of times you've travelled along the edge $e$ in every shortest path. The minimum cost flow problem asks for flows $x_e \in \mathbb{R}^{n\times n}$ that conserve the flow at each vertex and minimize your objective function $\sum_{e\in E} c_e x_e$. So if $x_e$ is the number of times you've used the edge $e$ in all the shortest paths and $c_e$ is the cost of pushing $1$ unit of flow across $e$ (i.e. the length of $e$), then $\sum_{e\in E} c_e x_e$ is summing the cost of every edge used across all the shortest paths.

Let's take an example with three nodes and a graph that looks like 0--1--2.

Assume that 2 is the root and each edge is unit length. So the shortest path for vertex 0  is 0--1--2 and the shortest path for vertex 1 is 1--2. So I used 0--1 once and 1--2 twice. This satisfies the equations that the units of flow going into a vertex must be one less than those going out. Additionally we have $-2$ units of flow going into vertex $2$, so that equation is satisfied as well. The objective function then sums to $3$ which is our minimum flow cost.


How to find specificity of a regex match?

There are two angles I see to define "specifity" in this context.

Specifity of a regular expression $r$ that matches input $w$ is
the (inverse of the) number of words of length $|w|$ that also match $r$.
Specifity of a regular expression $r$ that matches input $w$ is (the ratio of)
the (maximum) number of symbols of $w$ that are matched by non-wildcard symbols
in $r$ (and $|w|$).

The first option follows your idea: choose among all matches the regular expressions that
matches the fewest others. Since there are in general infinitely many matching
strings, we have to restrict ourselves to a certain length, or a finite set of lengths.

The second option follows another approach. If the input string is well described
by a given expression, long parts of it should be (more or less) explicitly described
in the regular expression. For example, $(aa|ab)+.^*bba$ is a more specific match
for $aaababaababababba$ than $.^*$.

Option 1

In this case, we have to count all words in $\mathcal{L}(r)$ that have length $n$.
Luckily, this is easy once we have an unambiguous, regular grammar¹ $G$ for $\mathcal{L}(r)$.
See here how this can be done.

Option 2

Let's assume we have an unambiguous regular expression (for instance by specifying
lazy wildcards). In that case, we can translate the regular expression into a
DFA. Run the word through it and count how many non-wildcard transitions are taken.

If the expression is ambiguous, we can do the same with the corresponding NFA
if we explore all possible paths.

Convert $r$ to an $NFA$, determinise, convert to right-regular grammar. All
conversions are standard and algorithmically feasible (if not necessarily
efficient).


Generate all permutations of 1 to n with i stacks

What is the minimum value of $i$ which can generate all permutations of 1 to $n$ at the output?
  The options are: 1) 1 $\;$ 2) 2 $\;$ 3) $n-1$ $\;$ 4) $n$

None of the given options are correct.

All permutations of 1 to 7 can be generated by 3 stacks.
The permutation 7132465 cannot be generated by 2 stacks.

The above facts can be verified by an exhaustive search by a program easily. So the minimum value of $i$ which can generate all permutations of 1 to 7 is 3. Note that $3\not=2$ and $3\not=7-1$.

Let $s_i$ be the minimum value of $i$ which can generate all permutations of 1 to $n$. Then
$s_1=0$, $s_2=s_3=1$, $s_4=s_5=s_6=2$, $s_7=s_8=3$.

It is not clear to me what are the value of $s_i$ for $i\ge 9$.


Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) =  n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{2^2})) = n\log(n) + n\log(\frac{n}{2}) + n \log(\frac{n}{2^2}) + 2^3T(\frac{n}{2^3})$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = \sum_{i=0}^{\log(n)}n\log(\frac{n}{2^i}) = n \log(\Pi_{i=0}^{\log(n)}\frac{n}{2^i}) = n \log(\frac{n^{\log{n}}}{2^{\frac{\log(n) \times (\log(n) + 1)}{2}}}) = n \log(n) \log(\frac{n}{\sqrt{2}\sqrt{n}}) = n \log(n)\log{\frac{\sqrt{n}}{\sqrt{2}}} = \Theta(n
\log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.


Check constraint under some condition in linear programming

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately.  Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases.  We'll optimize for each, separately.  The two cases are:

Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped.  So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon.  Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$.  So, this case really covers only one possible assignment to the selectors: the all-zeros assignment.  You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$.  So the value $0$ is always attainable.
Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped.  So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming.  Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function.  Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case.  This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the subset sum problem or knapsack problem.  In fact, it looks like this is a kind of reverse knapsack.  If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$.  That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack.  The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem.  The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$.  If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.


Find a CFG for palindromes with at most three c's

Call
$$
P=\{w\in\{a,b,c\}^*\mid w=w^R\}
$$
the palindrome language and
$$
Q=\{w\in\{a,b,c\}^*\mid |w|_c\le 3\}
$$
the language of strings having at most 3 $c$'s. Then your language is $L=P\cap Q$ and so is a CFL, since we know the intersection of a CFL (which $P$ is) and a regular language (which $Q$ is) is a CFL. With that out of the way, let's get a CFG for $L$.

You know that a grammar for $P$ can be given by the productions
$$
S\rightarrow aSa\mid bSb\mid cSc\mid a\mid b\mid c\mid\epsilon
$$
Now let's modify this grammar so that it generates palindromes with at most 3 $c$'s. The production $S\rightarrow cSc$ will add two $c$'s to the string being generated, so we want to limit ourself to subsequent productions that generate at most one more $c$. We can do that by changing $S\rightarrow cSc$ to $S\rightarrow cTc$ and forcing $T$ to generate palindromes with at most one $c$. This is simple enough: we can add these productions,
$$
T\rightarrow aTa\mid bTb\mid a\mid b\mid c\mid \epsilon
$$
So finally we have the grammar
$$\begin{eqnarray}
S&\rightarrow& aSa\mid bSb\mid cTc\mid a\mid b\mid c\mid\epsilon \\
T&\rightarrow& aTa\mid bTb\mid a\mid b\mid c\mid \epsilon
\end{eqnarray}$$


Just apply the given permutation on the string.

Your string is : 'HELLO WORLD AND THIS IS A SECRET MESSAGE'.

Now, to apply the given permutation, we have to shift the first 10 characters rightward by 10 units, and the next 10 characters leftwards by 10 units, while leaving the rest same. Note that you also need to count the spaces.


I've found that Blelloch writes a book about data-parallelism: Vector models for data-parallel computing. In this work, he introduces a vector memory model (V-RAM). This model extends simple RAM with additional vector memory, that available to store an unlimited amount of homogeneous simple data types. Also, there is a vector processor that is capable to perform some "simple" operations with the vectors. Blelloch has a nice definition of the simple operation: he allows to use operations, that can be implemented in $O(n)$ time on RAM and also these operations must be contained in the $NC^1$ class of the boolean circuits.

This model is a very high level, but I think that it depicts the structure of SIMD processing more deeply than PRAM. Also, this model quite interesting by itself, because it wraps almost all parallel interaction of algorithm in the primitives and description of algorithms is purely sequential.

Does anyone know about the future of this model? Does it evolve or just stuck and no progress in done in this direction?


what is approach of solving MINUS on SPOJ?

I am assuming that you have found out the sequence of $+$ and $-$ which lead to getting the final result as the required integer $m$.
One observation here is that the sequence of $+$ and $-$ of length $n$ (size of array) will always start with $+$ $-$, and remaining integers can be either $+$ or $-$. To clarify: if the array is $a_1, a_2, a_3, a_4, a_5, \ldots, a_n$ then $m= +a_1-a_2 \# a_3 \# a_4 \# \cdots \# a_n$,
where $\#$ is either $+$ or $-$.
Now to decipher the order in which operations should be carried out to get such a sequence we first look at the rightmost $-$ in the sequence.
For example, let the integers be $5,8,1,6,2,12$ and $m=6$.
One way to get this is $+5-8+1-6+2+12$.
The rightmost $-$ is near $6$.
Let's add parenthesis here to divide the problem into two smaller ones: $(5-8+1)-(6-2-12)$.
Now solve these two smaller problems individually with same idea of rightmost $-$: $(5-(8-1))-((6-2)-12)$.
We can clearly see the operation that is asked in the question.


What is the effect of having a transition in an epsilon-NFA upon "$\epsilon$,0"?

I suggest you review the definition of epsilon-NFA, especially the definition of when an epsilon-NFA accepts a word.

To answer your question, no, the $0$ is not ignored. Consider an epsilon-NFA with two states, the initial state $q_0$ and the accepting state $q_1$, connected by two edges labeled $\epsilon$ and $0$. This epsilon-NFA accepts the words $\epsilon$ and $0$. If you remove the edge labeled $0$, the epsilon-NFA will accept only $\epsilon$.


Hint: Recall what you are actually doing in ternary search - you basically partition the list into 2 parts, on of roughly $n/3$ elements, and the other of $2n/3$ elements.

So, on a bad day (worst case) you do $2n/3$ recursive calls.

Then the recurrence relation is $$T(n) = T(2n/3) + c $$

I'll cheat a bit here and use the master theorem to jump to the conclusion that $T(n) \in \Theta(log\ n)$


Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.

The number of connected spanning subgraphs of a graph $G$ equals $T_G(1,2)$, where $T_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence this paper of Björklund et al., which shows how to compute said polynomial in vertex-exponential time (i.e., $\exp O(n)$), gives us hope, since in your case $n$ is pretty small ($n \leq 15$).


White-space and comment by lexical analyzer

White-space and comments can contain valuable information.

For white-space, you can look at layout sensitive languages, like Python or Haskell. I'm not sure how their lexers work, but off the top of my head I would store an indentation level, not the actual white-space.

For comments, it can be useful to store these if you want to generate documentation from Javadoc-style comments. For Javadoc, the parameter types do not have to be specified in the docblock (unlike PHPDoc, for instance). This means that a documentation generator would have to look at both the comments and the method header (everything before {). For the latter the lexer can be used, for the former it cannot (presuming the lexer removes comments).

I'm note sure how Javadoc-based documentation generators work, so perhaps the above is inaccurate, but the general idea is correct. I'm working on the Cloogle project, a Clean function search engine similar to Haskell's Hoogle. We hook into the Clean compiler to parse function types from all standard libraries. It would be nice if we could show comments around the definition as well, but the lexer removes this information. So, if we want to display comments, we have to adapt the compiler's frontend, or write a simplistic program that finds comments around some function, without lexing everything. If the lexer and parser would store comments, we would have a much more elegant solution.


Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?

The result is proved in Ginsburg and Greibach, Deterministic context free languages, Inform. Control 9(6), 620–648, 1966, Theorem 4.1 on page 24 (643). However, the proof looks somewhat different.


Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e_{a,b}$ with shortest path from a→b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.


Using 2-opt Heuristic in a Genetic Algorithm for TSP

One optimization to your pseudo-code is to calculate the new cost of a route after performing a 2-opt move by:

cost = cost - d[b(i)][i] - d[i][a(i)] - d[b(k)][k] - d[k][a(k)] + d[b(i)][k] + d[k][a(i)] + d[b(k)][i] + d[i][a(k)]

with $b(x), a(x)$ being the node before and after node $x$ on your current route.


I don't know what sort of efficiency you are looking for, it would be good if you clarified it.
Each instruction can be described as a linear map in $\mathbb{F}_2$, so the overall
series of instructions is one linear map.
As for finding the minimal set of instructions, given a limited number of temporary variables, I believe this is analogous to the register allocation problem for compilers, which is NP-COMPLETE.


If you perform the addition, you get 1111+0111 = 0110 (ignoring the carry bit). In decimal, this reads $-1 + 7 = 6$, which is indeed correct. There is no error.

You can check that when adding a positive number and a negative number, if the result is non-negative then there will always be carry, which can be safely ignored.


Let's fix a maximal matching $M$. Let $Z\subseteq Y$ be the set of nodes that are not matched to nodes in $X$. We can see a node $x\in X$ belongs to a saturated set if and only if there does not exist an alternating path from $x$ to a node in $Z$, i.e., a path $xy_1x_1\cdots y_kx_kz$ where $(x_i,y_i)\in M$ and $z\in Z$ (the proof is similar to the correctness proof of your algorithm).

So you can add directions to all edges in $E$ such that edges in $M$ have the direction from $X$ to $Y$ while edges not in $M$ have the direction from $Y$ to $X$, then the nodes in $X$ that are not reachable from any node in $Z$ make up the maximal saturated set. You can run a simple BFS to see which nodes in $X$ is reachable from nodes in $Z$. The time complexity is $O\left(\sqrt{|V|}|E|\right)$.


Probability of k-connectedness for a random graph with given degree sequence

The answer probably mildly depends on how wild the $d_i$ are. A random $k$-regular graph is $k$-connected whp for $3 \leq k \leq n-4$ according to slides by Wormald (page 12), so I would expect that if, say, $k \leq d_i \leq \ell$ for constants $k,\ell$ (or even $\ell$ growing mildly with $n$) then the graph is still $k$-connected whp. The proof shouldn't be difficult (for constant $\ell$) using the configuration model.

A 1-regular graph is never connected (for $n > 2$), and a random 2-regular graph is, if I remember correctly, disconnected whp. If you only have a few degree 2 vertices then perhaps the graph is 2-connected whp – that would be my guess.


Are constituency grammars and dependency grammars two different types of context free grammars?

Concrete syntax trees and derivation trees exist for many types of
grammars (e.g. tree adjoining grammars, TAG). They happen to be
identical (up to labeling) in the case of CF grammars, but this is not
always the case, for example for TAG. (there are technical errors or
imprecisions in Wikipedia).

The derivation tree expresses how the rules are to be applied to
obtain the derived string. The derived tree (or concrete syntax)
associate a tree structure to the generated string, which may not be
context free.

Constituency grammars is a name often used by linguists to refer to
what we call Context-Free Grammar.  This is intended to contrast them
with Dependency Grammars based on a linguistic concept of dependency
used by linguists.

The idea of constituency is a classic idea in formal systems: terms
are formed with subterms. So the parse tree (very approximately) may
be seen as a term of an abstract algebra, and the semantics of the
whole is a composition of the semantics of the parts, the constituents
(I insist that I am simplifying a lot). While parse trees are concrete
syntax trees, the idea of abstract syntax trees (AST) was to emphasize
in programming languages the algebraic term structure to better
organize compilers and formal semantics.

Nevertheless, constituency is a syntactic concept, a very common one.

It has been extended to formalisms that consider discontinuous
constituents (or multi-parts constituents), such as TAG and Linear
Context-Free Rewriting Systems (LCFRS), which are strictly more
powerful than CF grammars.

As far as I understand, the idea of dependency is
related to lexicalized grammars (which also exists for extensions of
CF grammars).

The idea of a lexicalized grammar is that every rule instance used in
a derivation must be associated with a terminal of the generated
string (usually a single one). As is well known, every CF language has
a lexicalized CF grammar: you just put it in Greibach normal
form. Actually, the research of Sheila Greibach was probably motivated
by natural language considerations (she was working in the NL group of
Anthony Oettinger at Harvard). This concept of lexicalisation
comes from some natural language (NL) theories that consider that
construction of sentences is lexicon driven.

So far, we are still in the CF realm.

Dependency Grammar (DG), as much as I understand it as I am no specialist,
organizes the tree structure around the idea that each node of the
syntax tree is associated with a terminal (lexical element), as in
lexicalized grammar, but in such a way that it "controls" (dominates in
the tree structure) some part of the sentence, of which it is supposed
to be the central element (the exact term is "head"). So the verb will
be the head of a sentence, and the noun the head of the noun part of
the sentence, etc., according to some linguistic theory the
linguist is developing to organize language structure..

It is quite characteristic that the wikipedia article on Dependency
Grammars does not propose a formal definition of the concept. My
feeling from a quick glance at the literature is that it is mostly a
linguistic concept that can be formally dressed in different ways,
without a standard reference one. There are, however, some formal
definitions, for example in Dependency Grammars and Context-Free
Grammars, by Steven Abney (unpublished, 1994). I have also seen
contradictory statements regarding the power of DG, but it apparently
at best weakly equivalent to CFG. Specific algorithms have been
developed for dependency parsing, that seems to have interest for
linguists.

A dissertation (for sale) may contain interesting material: Dependency
Structures and Lexicalized Grammars: An Algebraic Approach*, Marco
Kuhlmann, Springer 2010. Slides about it are available.

Closely related to Dependency Grammar are Link Grammars, formally
defined, which also seem to have been designed for their parsing
properties, though advantages over CF grammars seem disputed.
Link Grammars are weakly equivalent to CF grammars, according to their
creators, Daniel Sleator and Davy Temperley.

But Dependency Grammars, or Link Grammars, though they may define the
same languages as all or part of the CF grammars, are not CF grammars,
and do not define the same structures for the strings.

It is worth noting also the Head Grammars, which are non-CF
constituency grammar, though they emphasize the concept of head more
often encountered with the dependency analysis of language. Head
grammars are LCFRS.

I believe semantics considerations enter the concept of Dependency
Grammars, but there in no clearcut limit between syntax and semantics
in Natural Language.

Constituency grammars are often just our good old, syntactic, formally
defined, context-free grammars, though it has been entended to more complex structures for constituants.


Decidability of language L = { n : ∃x∈N, n = 3x+2 }

Yes, your approach is correct.

The description of your algorithm would be clearer if it also mentions the following.

The algorithm rejects the empty word immediately.
That canonical enumerator of $\{0,1\}^∗$ enumerates all positive integers in increasing order.
If $3x+2$ is smaller than the input then the result will be ignored and the enumerator will keep going.

Another algorithm that decides the language would be subtracting 3 from the input number and checking the result repeatedly. If the result is 2, it accepts. If the result is negative, it rejects. It also rejects the the empty word immediately.


Given a set of points, find all collinear subsets

Here is a simple algorithm.  For each way to choose 2 points from $P$, find the line that goes through those two points and then find all other points from $P$ that are on the line.   If this yields at least 3 points, output it.  Continue until you've iterated over all possible ways to choose 2 different points rom $P$.

The running time will be at most cubic.  In particular, suppose there are $m$ points in the set $P$.  Then there are ${m \choose 2} = m(m-1)/2$ ways to choose two different points from $P$.  Thus, you'll do $\Theta(m^2)$ iterations.  Then you can find all other points on the line in at most $O(m)$ time, so the total running time is $O(m^3)$.

There are probably more efficient algorithms.  However, this might probably suffice for your needs.  Specifically, in your example, you'll have $m \le 5^4$.  Also, each iteration can be done faster than $O(m)$ time: given two points $p,q \in P$, you only have to check at most 3 other cells in the tic-tac-toe space.  So, in your situation, the running time is $\Theta(m^2)$, and $m^2 \approx 2^{18.6}$, so this should be pretty fast.


Are two languages regular if the union is regular?

Pick $\Sigma = \{a,b\}$, $L_1 = \{ a^n b^n : n \in \mathbb{N}\}$ and $L_2 = \Sigma^* \setminus L_1$.

The union $L_1 \cup L_2$ is $\Sigma^*$ and hence is regular, but none of $L_1$ and $L_2$ is.


Finding alternative way of combinatorial counting

The correct answer can be rewritten as $\frac{n(n-1)}{2} + n + 1$.

Let's call the two remaining attributes $A_k$and $A_l$.

You are counting each combination of $nC_{n-2}$ candidate keys four times: (1) when they are alone, (2) when they are with $A_k$, (3) when they are with $A_l$, (4) when they are with both $A_k$ and $A_l$.

Your formula then boils down to the following sum:

$nC_{n-2} + nC_{n-2} + nC_{n-2} + nC_{n-2}$

The problem is that you are counting each combination in case (2) an excessive number of times, because each $A_k$ appears in $n-2$ additional identical combinations, when it is taken as a part of the candidate key. The same is true for case (3).

There is just one singular combination in case (4), the one with all attributes.

The corrected version of you formula is then:

$nC_{n-2} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{nC_{n-2}}=\frac{n(n-1)}{2} + \frac{n}{2} + \frac{n}{2} + 1=\frac{n(n-1)}{2} + n + 1$


LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

I can't actually see an approach that would provide constant time insert and return of the mid-element in $O(1)$ (and I understand "no cost" to be some constant cost.) I have, however, some ideas that may suggest some solution.

One approach that comes to my mind are two heaps, one MIN and one MAX. The MIN heap would keep al elements greater than the current mid element (satisfying $\frac{k}{2} - \frac{k}{100} ≤ midElement ≤\frac{k}{2} + \frac{k}{100}$) and the MAX heap would store all smaller or equal ones. On INSERT(x) we'd need to keep the heaps as balanced as possible, so we would compare x with the current mid element, add it to the proper heap (MIN if x > midElement, else MAX) and if the difference between heaps' sizes would grow larger than 1, we'd take an element from the larger one and insert it to the smaller one. However, RETURN would work in $O(log(n))$, as after returning the top of one of the heaps we would need to repair that heap. INSERT would also take $O(log(n))$ and DELETE could be even linear (select the heap in $O(1)$, get to the proper level of it (elements on lower level are too too big/too small) and search the level in $O(n)$).

Another approach would be to keep a balanced tree (like RB-Tree or an AVL-Tree). The top element would always be the mid-element. However, here RETURN would also work in $O(log(n))$ because we'd need to reset the root after removing it. INSERT would also work in $O(log(n))$ for the insert itself + eventual balancing and so would DELETE.

Constant times required ("has no cost") brings Hash-tables to mind. Average INSERT would indeed take $O(1)$ and so would DELETE (if table size and hashing function would be properly designed). As for RETURN - one approach would be to track the inserted elements and keep the index of the current mid-element. If greater or smaller elements were inserted we'd consider selecting the "next mid-element", but this would probably require $O(n)$ time (or at least I can't see any other way doing it). So this would actually cause our RETURN to work in $O(1)$ (if we keep an index of the mid-element), but grow INSERT cost to $O(n)$ (and similarly for DELETE.)


cancel out parts of a formula in CNF (conjunctive normal form)

It's probably useful to note that the resolution rule can be used to figure out exactly which literals (things like $\neg A\vee D$) may be deduced from the others.

In this case, the resolution rule applied to the clauses $\neg A\vee \neg E$ and $E\vee D$ results in the clause $\neg A\vee D$, which shows that that clause is redundant.


Prove that every CFL is decidable in O(n) space

Let $G$ be a context-free grammar in Chomsky normal form. We will show how to determine whether a nonempty word $w$ of length $n$ is accepted by $G$.

Every parse tree for $w$ is first of all a full binary tree with $n$ leaves. It is known that the number of such trees is $C_{n-1}$. Moreover, there is a bijection with words containing $n-1$ pairs of balanced parentheses and full binary trees with $n$ leaves. We can go over all full binary trees with $n$ leaves in space $O(n)$ by going over all words of length $2(n-1)$ over the alphabet $\{(,)\}$, converting each of them which is balanced to a full binary tree.

For each full binary tree $T$, we consider all possible labelings of nonterminals to the vertices of the tree in which the root is labeled using the start symbol, which can be done in $O(n)$ space (here the constant depends on $G$). We check each such parse tree for validity: for each internal vertex labeled $A$ with children labeled $B,C$, we check that $A \to BC$ is a production, and for the $i$'th leaf labeled with $A_i$, we check that $A_i \to w_i$ is a production. If we find a valid parse tree in this process, then $w \in L(G)$. Otherwise, $w \notin L(G)$.


Why is it better to do the data flow analysis in the basic blocks

It isn't "better" in the sense that the analysis is more precise. It's just more compact and cheaper to compute.

There's no reason why you can't compute an old-school iterative bit-vector-based dataflow analysis at every point between two intermediate-representation instructions. It will give you the same answer as doing it on basic blocks.

The main issue is that doing it this way, you need to store and manipulate the data at every point between two IR instructions. And remember, the only variable lifetimes that change across an instruction are the variables that participate in that instruction, so the sets on each side of an instruction are mostly the same. This is wasteful, especially on older machines.

Having said all that, we generally don't do dataflow analysis this way any more. Almost all modern compilers use some variant of static single assignment form. SSA form is cheap enough on modern machines, and gives you a more precise analysis: not only does SSA form give you the definitions that reach a program point, for example, it also gives you the paths along which those definitions reach.


How does this algorithm for verifying if a string is $0^n1^n$ work?

This is a very informal answer (other users will give you a more formal and concise answer :-)

Suppose you have two numbers written in binary notation (the smaller one left-padded with zeros); for example:

14 =  1110
 6 =  0110

A simple algorithm to check if they are equal is comparing the two binary representations bit by bit; this can be done comparing the lower bit and then dividing the number by two (i.e. dropping the lower bit):

111[0] = 011[0]   OK (14 mod 2 = 6 mod 2 )
 11[1] =  01[1]   OK ( 6 mod 2 = 3 mod 2 )
  1[1] =   0[1]   OK ( 3 mod 2 = 1 mod 2 )
   [1] =    [0]   NO => 14 and 6 are different

You can easily notice that the lower bits of two numbers are the same if the numbers are both even or both odd (i.e. if their sum is even).

The algorithm above does exactly the same thing but the numbers are represented in unary:

00000000000000 111111   even 0s, even 1s, sum even OK
-0-0-0-0-0-0-0 -1-1-1   odd 0s, odd 1s, sum even OK
---0---0---0-- ---1--   odd 0s, odd 1s, sum even OK
-------0------ ------   odd 0s, even 1s, sum odd REJECT!