Is cubical type theory still consistent with univalent excluded middle and univalent choice?

I decided to rewrite my answer, because I thought I could explain the details
better. I'd still defer to someone more knowledgeable should they happen to come
along.

I think it is relatively safe to say that cubical type theory as an approach on
the whole is compatible with the classical axioms you want. The reasons for
this are:

The differences people usually point out, like the $\mathsf{Glue}$ type,
are just a way of making univalence hold for all types, independent of
their belonging to a universe. This is (in my view) merely fixing a
limitation of the HoTT approach of minimally extending Martin-löf type
theory, where it's impossible to state the univalence axiom except by
reference to a universe. However, if you have enough universes with
univalence axioms, every type is in a universe, and so univalence holds for
all types. In fact, this is how Agda actually works directly; the universes
are primary, and all types are declared as part of a universe, similar to a
pure type system.
There is (I've heard) a cubical set model (discovered by Emily Riehl) that is
completely compatible with the standard simplicial set model, and I believe
it has been shown to be adequate for doing cubical type theory. I think what
this means is that if you add EM (and maybe choice), you get the same
homotopy theory as the classical simplicial set model. I've also heard that
there are constructive analogues of the simplicial set model, so it is not
inherently classical.

Now, what you have to worry about are other details. For instance, cubical Agda
uses the sort of cubes with inversions and connections. So, if i and j are
dimension variables, then ~ i is a dimension, and so is i ∨ j. There are
also Cartesian cubes that don't have ∨ but have other similar constructions.
These affect the details of how you are able to construct paths. Having more of
them is convenient for easily constructing compositions of paths and whatnot,
but my understanding is that the model that matches the classical simplicial
model lacks most of these things.

Now, more specifically, I've also heard that most of these other cubical set
models are anti-classical (I'd forgotten that earlier). I've not been able to
work out the details of how you demonstrate this inside implemented cubical
type theories, but my understanding is that, using ~ as an example, you try to
construct some contradictory scenario using a point i on the interval such
that i = ~i. There's no way given in the type theory to construct such a
point, and somehow it's inconsistent to presume that you can tell whether any
abstract point is or is not like that.

So, I guess the answer to your specific question is that there is probably a
way to refute excluded middle in cubical Agda (although I don't know how), and
every other computer implemented cubical type theory. But it's also likely that
a cubical type theory could be implemented that is consistent with classical
axioms (and homotopy theory) and supports all the reasoning desired (although
maybe it's more difficult to construct certain things). Unfortunately, you'll probably have to wait until the details are fleshed out more and some implementation decides to pick up the compatible version of the theory.

Another option, I suppose, is to not worry about the anti-classical part too much. If you use the cubical primitives to implement something similar to reasoning in the HoTT book, and avoid working directly with the cubical operations, you can probably be reasonably confident (I think) that you haven't relied on any paradoxes. I think there are efforts to provide a HoTT interface on top of cubical type theory in some of the libraries available. You could also dabble in learning the direct cubical parts, even though you don't use them directly, although I don't know exactly which parts are still part of the 'proper' model.

Edit: by the way, here is a presentation about cubical set models of homotopy type theory that mentions the anti-classical properties of many cubical set models. It describes, vaguely, what you have to do to refute excluded middle, but it's all in terms of looking at the models from the outside, hence some of the difficulty of translating that to a refutation within cubical type theory (for me).

Edit 2: here's a potential more positive answer. It's been pointed out to me that the constructions in the above video may not be possible to carry out inside cubical type theory. They are constructions that can be carried out in the 'intended' cubical set models, but just like Martin-löf type theory has other models than the intended one (which is how you get to HoTT), the cubical set models aren't necessarily the only model of the corresponding cubical type theory. So it's possible that cubical type theories are compatible with excluded middle and choice, even though their most obvious models are not.


Algorithm for fastest division below threshold

The optimal strategy is the greedy one: repeatedly split chunks of size $j$. This strategy results in $\lceil \frac{i}{j} \rceil - 1$ splits. We can prove that this strategy is optimal by induction on $i$. The strategy is clearly optimal for $i \leq j$. Now suppose that we split $i > j$ as $i = i_1 + i_2$. In total, this choice will use up at least this many splits:
$$
1 + \lceil \tfrac{i_1}{j} \rceil - 1 + \lceil \tfrac{i_2}{j} \rceil - 1 = \lceil \tfrac{i_1}{j} \rceil + \lceil \tfrac{i_2}{j} \rceil - 1.
$$
Let $\alpha = i/j$, $\alpha_1 = i_1/j$, $\alpha_2 = i_2/j$, so that $\alpha = \alpha_1 + \alpha_2$. To complete the proof, notice that $\lceil \alpha_1 \rceil + \lceil \alpha_2 \rceil \geq \lceil \alpha \rceil$, and so the quantity above is always at least $\lceil \tfrac{i}{j} \rceil - 1$, as claimed.

I have described one optimal strategy. Using the proof above, we can actually describe all optimal strategies. Splitting $i$ to $i_1+i_2$ is optimal iff $\lceil \frac{i_1}{j} \rceil + \lceil \frac{i_2}{j} \rceil = \lceil \frac{i}{j} \rceil$. When does that happen? Define
$$
i = aj-b, \quad i_1 = a_1j-b_1, \quad i_2 = a_2j-b_2,
$$
where $0 \leq b,b_1,b_2 < j$. A splitting is optimal iff $a_1 + a_2 = a$. Notice that
$$
i_2 + i_2 = (a_1+a_2)j - b_1 - b_2.
$$
This shows that the splitting is optimal iff $b_1 + b_2 = b$ (rather than $b + j$).


When does a Monte Carlo algorithm solve a problem?

In general Monte Carlo is used to solve a wide variety of different types of problems. In this particular case you want to learn if a random variable is the constant 1, or not. The idea is straightforward, sample the random variable multiple times, (each sample independently from previous sample to avoid bias) and check if all results were 1. If at least some of the result was 0, we know for sure the random variable is not constant 1 (in Solovay-Strassen Test context, the number is composite).

It is important to emphasize, since Monte Carlo is a randomized algorithm, that it is said to solve the problem if the probability of returning the wrong answer is below some threshold (a small number we will call $\epsilon$).

What happens if all outcome were 1? There is a chance that it is the constant 1, but also there is a chance we were not lucky and all outcome were 1 when they can also be 0. If the probability of sampling a 1 is $p < 1$, then after $n$ samples the probability of getting all 1 is $P_n = p^n$. Note that while $n$ increase $P_n \rightarrow 0$. We can specify a threshold, let's say $\epsilon = 10^{-10}$, such that if $P_n < \epsilon$ (i.e. the probability of having a false positive is less than $\epsilon$) we are ok with that result.

Now the answer to your question. $\forall p < 1, \epsilon > 0 \space \exists n \space p^n < \epsilon$. What is this telling you exactly?

Whatever the success probability is, as far as it is less than $1$ (for example $p = 0.99$ or $p=0.01$ or $p=0.5$) and threshold $\epsilon$ there exist an $n$ such that if we run the experiment $n$ times (sample $n$ times the random variable independently) we are going to fail with probability at most $\epsilon$. So Monte Carlo can be applied for non-degenerated values of $p$, just the number $n$ of sample must be adjusted to satisfy the $\epsilon$ threshold requirement.


How generate n equidistant points in a n-1 dimensional space

I assume we are working in $\mathbb{R}^n$.

First of all, observe that one regular $n-$simplex effectively determines all the others. In fact, if $S_1, S_2$ are two sets of points in $\mathbb{R}^n$ that satisfy the regularity condition, then they can be obtained from each other by composing at most an isometry and an homothetic transformation of the affine space (the converse is also true).

Therefore, it is sufficient to construct an unitary $n-$simplex centered in the origin. We visualize each vertex of the simplex $v_1, v_2, \dots v_{n+1}$ as an element of the real $n$-dimensional vector space.

Consider two vertices $v_1, v_2$ of the simplex, let $O$ be the origin and $\pi$ be the plane passing through $v_1, v_2, O$. The angle $\vartheta =\angle v_1 O v_2$ is exactly $\arccos (-1/n)$. To prove that, we observe that:

$$
0 = \left \| \sum_{i} v_i \right \|^2 = (n+1) + 2 \cos\vartheta \binom{n+1}{2}
$$

We deduce that the following hold:

$\forall i \quad \| v_i \| = 1$
$\forall i \neq j \quad \left \langle v_i, v_j\right \rangle = -1/n$

We may assume without loss of generality that $v_1, v_2$ lie on the same line, that $v_3$ lies on the same plane as the others and so on (in general, that for each $k$, $v_1, v_2, \dots v_k$ lie on the same subspace of $\mathbb{R}^n$ with dimension $k$). Therefore, we may write the vectors by coordinates as follows:

$$
\begin{array}{r c l}
\begin{array}{r}
v_1 \\ v_2 \\ \cdots \\ v_{n+1}
\end{array} &
\begin{array}{r}
= \\ = \\ \\ =
\end{array} &
\begin{array}{c c c c c c}
(x_{1,1} & 0 & 0 & 0 & \dots & 0)^T \\
(x_{2,1} & x_{2,2} & 0 & 0 & \dots & 0)^T \\
\\
(x_{n+1, 1} & x_{n+1, 2} & x_{n+1, 3} & x_{n+1, 4} & \dots & x_{n+1, n+1})^T \\
\end{array}
\end{array}
$$

The first equation uniquely determines $x_{1,1}$ and the second all the $x_{m,1}$. Now we use again the first to compute $x_{2,2}$ and with the second we determine all the remaining $x_{2, m}$.

Continuing the procedure in a similar fashion computes the coordinate values of all the vertices.


Why " every non-prime attribute of R is non-transitively dependent on every key of R" in the original def of 3NF?

In K→A, the K and A stand for sets of attributes. Let's suppose K is {j, k} and A is {x, y, z}. Then we have

{j, k} → {x, y, z}

Then x is dependent on the key, and that dependency is non-transitive.

A (i.e. {x, y, z}) is not a key for R (we're supposing), so the fact that {x, y, z} trivially Functionally Determines {x} (search for 'trivial' here) does not fall under the 2nd bullet that you quote from wikipedia on 3NF.

You might prefer to work with the Zaniolo 1982 definition that wikipedia gives. Because this is self-contained/doesn't need cross-referring to 2NF. (It'll also help you see the difference to BCNF, sometimes called "twothree-and-a-half Normal Form".)

Be careful to observe that given some set of FDs for a relation, you can derive further FDs, including the trivial FDs. (See Armstrong's Axioms and 'Closure' on the FD's article.) Then the fact that you can derive some dependency transitively which is the same as a non-transitive dependency already given, is just a tautology.

Addit: in response to comments "transitive dependent ... I still need some authoritative expression"

Ok. Looking at the wikipedia definition of 'Transitive Dependency' you have linked to in the q:

  A transitive dependency can occur only in a relation that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation.

Your formula mentioning K, A, x is not "three ... distinct collections of attributes": specifically x is not distinct from A; x is an element of A. Therefore your K → A ∧ A /→ K ∧ A → x does not represent a transitive dependency. But we do have that K→x. Therefore x's dependency on K must be non-transitive.

So in wikipedia's definition of 3NF, its definition of transitive dependency is sloppy.

To put it in sharp focus: imagine your K contains only a single attribute k; imagine your A contains only a single attribute x. Now you can't apply the definition of transitive dependency: R contains less than 3 attributes.


For a set of points P, connected by weighted edges (distances) I need a path through all points while minimizing the travel on any edge longer than X

Create a graph from the airport coordinates where edges have the haversine distance as weights.  Since the graph is a metric graph, you can apply Christofides algorithm.  This algorithm is a $\frac 3 2$-appoximation, which means that it gives a solution which is not worse than 50% longer than the optimal.
However, since you want to also minimize the number of long edges, you can remove all edges that are longer than you would like, but you now have a non-metric graph (it does no longer satisfy the triangle inequality).
One related problem is the Bottleneck traveling salesman problem, in which you want to find a Hamiltonian path that minimizes the longest edge.  Since your original graph is a metric graph, you can apply the 2-approximation to get an algorithm in which the longest edge is not more than twice possible.

Since you seem to be set on using genetic algorithm, you can consider using both of these algorithms for seeding the initial pool for the GA.  Run both algorithms many times to get many different solutions (introduce some randomness), and you might have a very good starting pool.


Find the minimal tank capacity to be able to travel from any city to any other

We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.

Sorting costs $O(n^2\log n)$ time. To find the minimal $i$, we can use the bisection method. We first test whether the graph is strongly connected with the edges $e_1,\ldots,e_{n(n-1)/2}$. If yes, we then test the connectivity with the edges $e_1,\ldots,e_{\lceil n(n-1)/4\rceil}$, otherwise we test the connectivity with the edges $e_1,\ldots,e_{\lceil3n(n-1)/4\rceil}$, and so on. The running time to find the minimal $i$ is also $O(n^2\log n)$. So the total running time of this algorithm is $O(n^2\log n)$.


Encoding two 6-bit positive integers compactly

Suppose that $H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$ is such that $a,b \in \{0,1\}^6$ can be recovered from $H(a,b)$. In particular, $H(a,b) \neq H(c,d)$ whenever $(a,b) \neq (c,d)$. Since there are $2^{12}$ possible inputs, and the value of $H$ on each of them is different, it follows that the range of $H$ must consist of at least $2^{12}$ different points. Since $\{0,1\}^n$ has $2^n$ points, we conclude that $n \geq 12$.


Genetic Algorithm - Fit max circles inside box

In genetic algorithms, each individual should be a candidate solution to the problem.  You're trying to find a packing of circles into the box, so each individual should be a complete packing that specifies the location of all the circles.


Let us denote by $X_n$ the value of $X$ after reading $n$ elements, and let $Y_n = 2^{X_n}$. We have $Y_0 = 1$ and $Y_{n+1}$ equals $2Y_n$ with probability $1/Y_n$, and $Y_n$ otherwise. Therefore
$$
\mathbb{E}[Y_{n+1}|Y_n] = Y_n + \frac{Y_n}{Y_n} = Y_n + 1,
$$
which together with $Y_0 = 1$ implies that $\mathbb{E}[Y_n] = n + 1$.

More generally, we can estimate all moments of $Y_n$ in this way. We have
$$
\mathbb{E}[Y_{n+1}^k|Y_n^k] = Y_n^k + \frac{(2^k-1)Y_n^k}{Y_n} = Y_n^k + (2^k-1) Y_n^{k-1},
$$
and so $Y_0^k = 1$ implies that
$$
\mathbb{E}[Y_n^k] = 1 + (2^k-1) \sum_{m=0}^{n-1} \mathbb{E}[Y_n^{k-1}].
$$
As an example,
$$
\mathbb{E}[Y_n^2] = 1 + 3 \sum_{m=0}^{n-1} (m+1) = 1 + 3 \frac{n(n+1)}{2}.
$$
Therefore the variance of the estimator $Y_n-1$ is
$$
\mathbb{V}[Y_n-1] = \mathbb{V}[Y_n] = \mathbb{E}[Y_n^2] - \mathbb{E}[Y_n]^2 = 1 + 3 \frac{n(n+1)}{2} - (n+1)^2 = \frac{n(n-1)}{2}.
$$
More generally, induction shows that $\mathbb{E}[Y_n^k] = \Theta(n^k)$, and with some effort we can even calculate the leading constant:
$$
\mathbb{E}[Y_n^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell} n^k + O(n^{k-1}).
$$
In particular, if we denote $Z_n = (Y_n-1)/n$ then $Z_n \to Z$, where
$$
\mathbb{E}[Z^k] = \prod_{\ell=1}^k \frac{2^\ell-1}{\ell}.
$$
For more on $Z$, see Theorem 7 in Ph. Robert, On the asymptotic behavior of some algorithms.


How can the class of tail recursive functions be compared to the classes of PR and R?

Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls.

The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value is directly returned (such as recursion base cases) are replaced by calling the continuation in tail-position with the result as an argument.

Transformation from the lambda calculus into CPS can be done mechanically. So, $TR=R$.

EDIT: addressing the comments about higher-order functions:

Tail-calls are almost always discussed in the context of higher order functions and the lambda calculus. So the problem is, what precisely is our definition of $TR$?

You can certainly add a wrapper around a CPS function to give it the type $\mathbb{N}^n \to \mathbb{N}$, by giving it an initial continuation of $\lambda k \ldotp k$. If higher-order functions are allowed internally, then the result that $TR=R$ still holds.

If higher order functions aren't allowed internally, what is our definition of $TR$? If we define it in the same way as $PR$, then it is going to only contain primitive recursive problems by definition (since it's just the restruction of $PR$ to tail-recursion). If we add $\mu$ for infinite search, I think we're just going to get $R$, since we can encode higher-order functions using integers. So, I'm not sure there's a meaningful question to be asked in the non-higher-order case.

EDIT 2:

As for the class of first-order functions that only allow tail recursion, with Constant, Successor, Projection and Composition functions, and extension by tail recursion:

h(x1 ... xn) =
  if c(x1 ... xn) = 0 then
    h(g1(x1), ..., gn(xn))
  else
    f(x1, ..., xn)

where $c$, $g_i$ and $f$ are all tail-recursive functions, I think we can prove that it's Turing Complete, by solving Post's Correspondence Problem, which is undecidable but semi-decidable:

Assume that we've got nice functions for dealing with strings encoded as integers, with concatenation, etc.

Let $pcpInst(k, n)$ be a function which takes an integer $k$ and returns the $k$th string over the alphabet $\{1, \ldots, n \}$.

Let $c(k, x_1, \ldots, x_n) = $ be a function, where $k$ is an integer, and each $x_i$ is a pair containing two strings over a binary alphabet. Thus function does the following:

Computes $k_1 \cdots k_p = pcpInst(k,n)$, the $k$th possible PCP solution indices.
Constructs $s_1=\pi_1(x_{k_1}) \cdots \pi_1(x_{k_p}))$. This is the string we get by concatenating the first string of the arguments indexed by our $k_i$ sequence. We define $s_2$ with $pi_2$ similarly.
Return $0$ if $s_1 \neq s_2$, return $1$ otherwise.

Now, we'll define our function to solve the a PCP instance with $n$ strings:

$h(k, x_1, \ldots, x_n) = h(S(k), x_1, \ldots, x_n)$ if $c(k, x_1, \ldots, x_n) = 0 $
$h(k, x_1, \ldots, x_n) = 0$ otherwise

Now we define $h'(x_1, \ldots, x_n) = h(0, x_1, \ldots, x_n)$.

It is clear to see that $h'(x_1, \ldots, x_n)$ returns 0 if and only if there is a solution to the correspondence problem defined by pairs of strings $x_1, \ldots, x_n$. If there is a solution, we eventually iterate to it by increasing $k$, and return $0$ when our $c$ function returns 1. If there is no solution, we never return.

The trick here is ensuring that $c$ is itself tail-recursive. I am fairly confident that it is, but that proving so would be tedious. But since it is performing simple string manipulations and equality checks, I would be very surprised if it is not tail recursive.


Reverse An Array whats wrong with this type of code?

Notice that you increment $p$, whilst also decrementing $n$. Since your condition in the while loop is that p < n, then the while loop will only work for half the elements.
Also, note that you delete the last $n/2$ values, since you modify them without first reading them.


Finding regular expression for a language with more substring of one type than from another

Hint: Suppose that as you read a word, you keep a counter which increases by 1 whenever you encounter 011, and decreases by 1 whenever you encounter 110. Show that the counter only gets the values 0,1,-1. In other words, between two occurrences of 011 there is an occurrence of 110, and vice versa. Use this to design your regular expression (you could also start with a DFA).


Is the halting problem decidable by an "infinite Turing machine"?

It is true that infinite Turing Machines as you have defined them can solve the halting problem for regular Turing Machines. That is, there exists an infinite TM, $I(t,x)$, that returns $1$ iff $t(x)$ halts. To see this, just have your first step be “run t(x) for infinitely many steps” and the rest is easy after that. Yes, there are some issues formalizing this idea, but it can be done. This is called a “Hyper Turing machine”

There’s an interesting question lurking here though... is there an infinite TM that solves the halting problem for infinite Turing Machines? The answer to that is no, and if you know the diagonalization proof of the incomputability of the halting problem that applies here too.


How to decode multiple-digit gamma codes and get the gap sequence?

The above sequence it read as a concatination of 5 numbers:

You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way.

First, read the first unary code, it is 1110 - so the first number
is "1110:001", which is 9
The next unary code is right after this, and is: "110" - so the 2nd number is "110:10" which is 6
The next unary code is "10", and the 3rd number is "10:1", which is 3
The next unary code is "111110", and the 4th number is "111110:11011", which is 32+16+8+2+1=59
Next unary number is "110", which gives you the 5th and last number, which is "110:11", which is 7.

So, the decoding of the given gamma code is actually 9,6,3,59,7


Just looking at the plot we can easily see, that these two complexities are completely different.

To prove it, we have to show that there doesn't exist a $c \in \mathbb{R}$ such that

$$(\log n)^n \le c \cdot n^2$$

We can take the $\log$
$$n\cdot \log\log n \le \log c + 2\log n$$
Because $3 \le \log\log n$ and $\log n \le n$ for big $n$, also the following inequalities have to hold:

$$3n \le n\cdot \log\log n \le \log c + 2\log n \le \log c + 2n$$

And therefore also the following inequaltiy has to hold:

$$3n \le \log c + 2n$$

This implies $n \le \log c$ or $e^n \le c$. And there is no $c \in \mathbb{R}^+$ with $c \ge e^n$ for all $n$

The proof is probably way too complicated, but it was the first thing that came to my mind.


Decidable language: set of context-free langauges containing 1 string

Hint: The point of this exercise is that it is decidable whether a context-free grammar generates the empty language. Using this as a black box, you can proceed as follows. On input $G$:

Check if $L(G)$ is empty, and if so, reject.
Find a word $w \in L(G)$.
Check whether $L(G) \cap (\Sigma^* \setminus w)$ is empty.

I'll let you figure out how to implement the latter two steps; step 2 uses the fact that it is decidable whether a grammar $G$ generates a given word $x$, and step 3 uses the fact that the intersection of a context-free language and a regular language is context-free (constructively).

The same idea can be used to calculate $L(G)$ given that we know that $L(G)$ is finite.


Let $\tau_1: x_1, x_2, \dots, x_n$ and $\tau_2: y_1, y_2, \dots, y_n$ be two topological orderings of the vertices of graph $G$. Our aim is to show that $\tau_1$ can be transformed into $\tau_2$ by a sequence of swaps, each changing the position of two vertices in the sequence, not connected to each other by an edge of $G$.

Starting from the beginning compare the vertices $x_i$ and $y_i$ and select the first pair that differs. For notational convenience we assume $x_1 \neq y_1$. As $y_1$ must occurs in $\tau_1$ we can find $x_j=y_1$, $j>1$. Thus vertices $x_1, \dots, x_{j-1}$ are all before $x_j=y_1$ in ordering $\tau_1$, but all after $y_1=x_j$ in ordering $\tau_2$. This implies there is no edge in $G$ (in either direction) from $x_j$ to each of $x_1, \dots, x_{j-1}$. Thus we can "legally" swap $x_j$ with each of $x_1, \dots, x_{j-1}$ to get it to the first position. We obtain $\tau'_1: x_j, x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n$ which has the same first element as $\tau_2$.

Iterate, or invoke induction.

(Thanks for your suggestions and support.)


How to solve if we have $3^{(n-2)/2}$ in recurrence relation?


The best approach to search for closest object in hash map holding arraylist without changing data structure

If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree indexes, such as quadtrees, R-Trees or kd-trees.


You don't mention that visiting a vertex multiple times is not allowed so I will assume that there isn't such a restriction. In your comment on your question you state that:

  The question is on the lines of If I were to start driving from X, no matter how I drive, I can always reach x

So the question is if $x$ is reachable from all nodes which are reachable by $x$. This is an easy to solve problem in linear time. First do a dfs from $x$ using the right direction of the edges to find which nodes are reachable by $x$. Let's name this set of nodes $A$. Then do a second dfs from $x$ to find from which nodes you can reach $x$. Let's name this set of nodes $B$. The answer of the problem is positive iff
$$A \subseteq B$$
You can check if this condition holds in linear time. The algorithm consists of the following steps:

Read input and initialize two adjacency lists (right and reverse edge directions): $O(N + M)$
Execute dfs from $x$ using right edge directions and mark visited nodes ($A$): $O(N + M)$
Execute dfs from $x$ using reverse edge directions and mark visited nodes ($B$): $O(N + M)$
Check whether $A \subseteq B$ or equivalently if $u \in A \Rightarrow u \in B$: $O(N)$

The total computational and space complexity of the above algorithm is $O(N + M)$ (linear), where $N = |V| \wedge M = |E|$. You may check the following C++ code if you want.

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Maximum number of nodes + 5 (change according to your requirements)

vector<int> E[MAXN];  // Adjacency lists with right edge directions
vector<int> RE[MAXN];  // Adjacency lists with reverse edge directions

bool A[MAXN];  // A[i] will become true iff i-th node is reachable from x
bool B[MAXN];  // B[i] will become true iff x is reachable from i-th node

void dfs(int u)
{
    A[u] = true;  // u was reached from x
    for (int i = 0; i < E[u].size(); i++)  //  for every out-neighbour of u...
    {
        int v = E[u][i];  // We name this node v
        if (!A[v]) dfs(v);  // If you haven't visited v yet, visit it now
    }
}

void dfsr(int u)
{
    B[u] = true;  // x can be reached from u
    for (int i = 0; i < RE[u].size(); i++)  //  for every in-neighbour of u...
    {
        int v = RE[u][i];  // We name this node v
        if (!B[v]) dfsr(v);  // If you haven't visited v yet, visit it now
    }
}

int main()
{
    // Read input and make initializations...
    // I assume that nodes are numbered from 0 to N-1
    int N, M, x;
    cin >> N >> M >> x;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;  // There is an edge from u to v
        E[u].push_back(v);  // Right direction from u to v
        RE[v].push_back(u);  // Reverse direction from v to u
    }

    dfs(x);  // DFS from x using the right direction of edges
    dfsr(x);  // DFS from x using the revers direction of edges

    // Check if A is a subset of B (A[x] => B[x])
    for (int i = 0; i < N; i++) if (A[i] && !B[i])
    {
        cout << "NO\n";
        return(0);
    }
    cout << "YES\n";
    return(0);
}

I would like to note two facts:

In your comment you say that the problem statement is equivalent with wether $x$ is reachable by every node. This is not true based on your previous statement. It asks if $x$ is reachable by every node reachable by $x$, which is different. If that was the case only one dfs from $x$ using the reverse edges would be required.
On your question you proposed an idea about finding the strongly connected components. It is true that you can answer the question using this technique, but you don't have to find if there is only one strongly connected component (that solves the wrong problem - see 1.). Instead you have to verify that there is no edge from $x$'s strongly connected component to any other strongly connected component (in which case there would be nodes where you could go starting from $x$ but then you could not return to $x$ from them). This is a correct solution for your problem which also has linear time complexity. Although its implementation is a little bit harder and there is no reason to make things more complex than they are.


Can finding a witness be NP-hard even if we already know there is one?

TFNP is the class of multivalued functions with values that are polynomially verified and guaranteed to exist.

There exists a problem in TFNP that is FNP-complete if and only if NP = co-NP, see Theorem 2.1 in:

Nimrod Megiddo and Christos H. Papadimitriou. 1991. On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 2 (April 1991), 317-324. DOI: 10.1016/0304-3975(91)90200-L

and the references [6] and [11] within. PDF available here.


This is another classical example in which the pumping lemma is the wrong way to go. Here are two cheap alternatives.

Use the Myhill–Nerode theorem. For any $i \neq j$, the words $1^i$ and $1^j$ are inequivalent, since $1^i\#1^i \notin D$ while $1^i\#1^j \in D$. Since there is an infinite pairwise inequivalent collection of words, the language is not regular.
Use closure operators. If $D$ were regular, then so would $\overline{D} \cap 1^*\#1^* = \{1^i \# 1^i\}$ be. Now it's easy to use the pumping lemma.

It's also possible to use the pumping lemma directly. Suppose that the pumping length is $p$. Take $w = 1^p\#1^{p!+p} \in D$. According to the pumping lemma, we can write $w = xyz$ so that $0 < |xy| \leq p$ and $xy^iz \in D$ for all $i$. Let $y = 1^q$, so that $1 \leq q \leq p$. Choose $i = p!/q + 1$. Then $xy^iz = 1^{p!+p} \# 1^{p!+p} \notin D$, contradiction.

The trick of using factorials here is standard. Now that you've seen it, you can use it whenever it's needed.


A recursive solution to the all-pairs shortest-paths problem

(1) tells you how to compute the shortest path.

Note that given that the graph has no negative-weight edge, the shortest path between two nodes is a simple path (with no cycles) which has at most $n-1$ edges. More than $n-1$ edges means a cycle which increases the path length. But we are interested in the shortest path.

(2) claims that after $n-1$ edges the shortest path length remains same:
$L_{i,j}^{n-1}=L_{i,j}^{n}$ is read as "the shortest path from $i$ to $j$ passing through $n-1$ edges is the same as the shortest path through $n$ edges".

In fact it means that there is no need to compute $L_{i,j}^{n},L_{i,j}^{n+1},\dots$ since it will not lower the path between $i$ and $j$.


Hyperplane through origin which goes through most number of points

I suspect your problem might be hard, for the following reason:  The corresponding problem when working over a finite field is NP-hard.

Your problem is equivalent to the following:

Inputs: a $M \times N$ matrix $A$, with real-valued entries
Goal: Find $x \in \mathbb{R}^N$ that maximizes the number of 0 entries in $Ax$

The corresponding problem for a finite field (e.g., working with integers modulo a prime $p$, rather than real numbers) is known as the minimum-weight codeword problem for linear codes, and it is known to be NP-hard.  See, e.g.,
https://cs.stackexchange.com/a/59922/755,
Solving/Optimizing a linear system in a finite field (Z/2Z),
https://cstheory.stackexchange.com/q/27460/5038,
https://cstheory.stackexchange.com/q/21678/5038.
It's always possible that the problem is dramatically easier for real numbers than over a finite field, but that seems like it might be a lot to hope for.

Anyway, I don't know if there are algorithms with running time better than $O(M^N)$, but I suspect it's hard (not likely to have a polynomial-time solution).

See also https://cstheory.stackexchange.com/q/3719/5038 for a related but different problem.


How to reduce UNSAT problems so that less than $7/8+\epsilon$ of clauses are unsatisfied?

The reference is Håstad's classic paper, Some optimal inapproximability results. It relies on the PCP theorem and on Raz's parallel repetition theorem. The proof is not particularly easy, and even the reduction itself is not so simple to state (if you take into account the PCP component).


Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

Let's assume for simplicity that $C = \emptyset$; I'll let you work out the general case. Note that there are at most $|U|$ sets in OPT. Let $OPT = \{O_1,\ldots,O_m\}$, where $m \leq |U|$. We have
$$
\sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i \setminus (O_1 \cup \cdots \cup O_{i-1})|}{|U|} \leq \sum_{i=1}^m \frac{c(O_i)}{|O_i|} \frac{|O_i|}{|U|} = \frac{OPT}{|U|}.
$$
On the left-hand side we have a weighted average of the quantities $c(O_i)/|O_i|$, so one of them must be at most $OPT/|U|$. The greedy algorithm selects a set $S$ with $c(S)/|S|$ minimal, so in particular
$$
\frac{c(S)}{|S|} \leq \min\left(\frac{c(O_1)}{|O_1|},\ldots,\frac{c(O_m)}{|O_m|}\right) \leq \frac{OPT}{|U|}.
$$


Algorithm to maximize dot product between two sets of vectors

As a completely different approach, assuming that $d < \log n$, one can generate $O(\log n)$ random vectors $w_i$ with unit norm. For each $w_i$ we look at $\langle l_i, w_i \rangle$ and $\langle r_i, w_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d < \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d << \log n$.


Its hard to tell what the "complexity" of a loop without knowing what each iteration performs, but what we can do is count how many times each loop iterates:

  for (int i = 1; i < n; i++)

You correctly stated this loop iterates $n$ times.

  for (int i = 0; i < n; i+= 2)

The above loop iterates until $i \geq n$, or in other words, $k$ times, when $i+2k = n \rightarrow 0+2k = n$ (since you initiate $i=0$ and increment it by $2$). Solve the trivial equation, and you get $k=\frac{n}{2}$, which is $O(n)$ iterations.

  for (int j = 1; j < n; j*= 2)

Same as the second time, we must solve $2^k = n$, since you multiply $j=1$ by $2$ each iteration. Solve and get $k=\log(n)$


Is there a way to find a simple regular expression for this language?

Forget about the $0$, they are boring. Like you said, you can add $0^*$ basically everywhere and you are done.

Now for the $1,2$. Just try to order them in batches that total 5. Then you realised that this might be problematic in case at the count of 4 we read $2$ and overshoot by one. No problem, we remember this, and continue until we reach a proper multiple of five. Note however, that the overshoot just might repeat when we have $212$, or similar.

So here is how the regular expression is constructed: any multiple of five, or when we reach an overshoot, wait until we are back. Repeat.

First some abbreviations:

$E_5= \{11111,1112,1121,1211,2111,221,212,122\}$.

$E_4 = \{1111,112,121,211,22 \}$.

$E_{\mathrm{shoot}}= \{1112,212,122\}$.

Finally here is your expression:

$\Big ( E_5 \cup E_4\cdot 2 \cdot (E_{\mathrm{shoot}})^*\cdot E_4\Big )^* $.

Ah. Add $0^*$, lots of them.


Understanding LEADING and TRAILING operations of an operator precedence grammar

@Raphael : Definition of trailing : Any terminal which is present at the last of a right sentential form (and not the sentence) which is derived from a non-terminal is the trailing of that non-terminal.

Trailing($E$) :

$E \rightarrow E + T$  --In this the trailing is '$+$'

$ \rightarrow E + T * F$ [using $T \rightarrow T*F$] -- Here trailing is '$*$'

$\rightarrow E + T * ( E )$ [using $F \rightarrow ( E )$] -- Here trailing is '$)$'

(from $E + T * F$) $\rightarrow E + T * id$ [using $F \rightarrow id$] -- Here trailing is '$id$'

Hence trailing($E$) = $\{+,*,),id\}$

So the lesson here is that you must use the right sentential forms also and not just the sentence to find out the trailing.

Note : $E \rightarrow E + T \rightarrow E + T * F \rightarrow E + F * id \rightarrow T + id * id \rightarrow F + id * id$ are all right sentential forms of $E$ as they have at least one non-terminal.

However $id + id * id$ is a sentence because it has no non-terminals and you must not use just the sentence to find out the trailing.


A PDA (or an NFA) doesn't split. At any given point in time, it non-deterministically chooses a valid next step, if any. If there are several options, you can say that the PDA "splits" if you wish, trying all of them in parallel.

A PDA (or an NFA) could have more than one possible move even if it has no $\epsilon$ moves, and conversely, there might be situations in which an $\epsilon$ move is the only possible move of the automaton (can you think of such a situation?). So your identifying $\epsilon$ transitions with "splitting" is wrong.


Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people

Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a < 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b < D, or b < (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person.

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result < 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is > w/3 first, or you might waste a lot of time.


Let's try to solve a simpler problem first:

Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left.

Now this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each element with the distance.

A simple code:

dist = INF
for(i=0;i<a.length;i++){
    if(a[i] == 0)
       dist = 0;
    else
       dist++;
    b[i] = dist;
}

Now once you have solved the simpler problem for closest 0 to the left, you can similarly solve the problem for closest 0 to the right. With these two solutions, you should be able to easily get a solution for the original problem (by taking a min of the two solutions).

The solution evidently has O(n) time complexity, and can be easily coded to use only O(1) space by carefully manipulating the updates in the original array only.


When is a first-order formula is existential and when is it universal?

The key to the usage is to transform the formula to an equivalent formula that is in prenex form.

A formula $F$ is in prenex form if $F \equiv Q_1 x_1 ...Q_m x_m\; G$ where $G$ is a quantifier free formula and $Q_1,...,Q_m$ are quantifiers.

A formula $F$ is universal if it is equivalent to a formula in prenex form that has only universal quantifiers.

There is an important model theoretic property of universal formulas: a universal formula that is satisfiable in some structure $S$ is also satisfiable in any substructure $P$ of $S$.

  Why is $\forall x \exists y(X[xy]∨X[yx])$ universal and $\exists x \forall y(X[xy]∨X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?

Either sentence is neither universal nor existential. One can easily come up with an example structure where $F\equiv\forall x \exists y(X[xy]∨X[yx])$ is true but is not true for a substructure.

   Let $S=\{0,1\}$ and $X[xy]\equiv x\not=y$, then F is true in $S$ but is not true for any one-element substructure of $S$.

Now for the second question

  And if you have a formula like this: $H\equiv(\exists x X[xy])⊙X[yx]$, where ⊙ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

In order to find the prenex form we rename the variable $x$ in the scope of the existential quantifier to get $H'\equiv(\exists z X[zy])⊙X[yx]$.

Now suppose $⊙$ is disjunction or conjunction then we can consider an equivalent formula $H''\equiv\exists z X[zy]⊙X[yx]$ that is in prenex form and is an existential formula.

However if $⊙$ were an implication then the formula $H$ would be equivalent to $H'''\equiv\forall z X[zy] \Rightarrow X[yx]$. The formula $H'''$ is clearly a universal formula.


Ignoring the even semester constraints, you can model this as a scheduling problem where classes are jobs of processing time $1$ which have to satisfy precedence constraints and must be processed on a parallel machine that can process at most a fixed number $m$ of jobs at the same time. In standard notation, this problem would be called $Pm\mid\text{prec},p_j=1|C_\text{max}$ and is NP-complete (Ullman, NP-complete scheduling problems, J. Comp. Sys. Sci., 10, 1975).

That said, for the size of problems you may be interested in, an integer programming model can likely be solved to optimality. If you let the semesters be $S=\{1,2,\ldots,s\}$, where $s$ is some upper bound on the number of semesters, $m$ the maximum number of classes you can do every semester, and $\prec$ the predecence relation (i.e. $c\prec c'$ if class $c$ must precede class $c'$) a formulation would be
\begin{align}
\text{minimize } & C_\text{max},\\
\text{subject to } & C_\text{max} \geq s\,x_{cs}, & \forall c,s,\\
& \sum_c  x_{cs} \leq m, & \forall s,\\
& \sum_s x_{cs} = 1, & \forall c,\\
& 1+\sum_s s\,x_{cs} \leq \sum_s s\,x_{c's}, & \forall c\prec c'\\
& x_{cs}\in\{0,1\}, & \forall c,s,
\end{align}
where $x_{cs}=1$ indicates that class $c$ is done in semester $s$. It would be also easy to add even semester restrictions to this model.


Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time

You can modify the CYK parsing algorithm so that it counts the number of parse trees for each word.
Given a word $w = w_1 \ldots w_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w_i \ldots w_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w_i$ is a rule. Otherwise, all parse trees are of the form $$A \to BC \to^* (w_i \ldots w_k) (w_{k+1} \ldots w_j)$$
and so if we know, for each $i \leq k < j$ and for each $B,C$ such that a rule $A \to BC$ exists, how many parse trees there are for $w_i \ldots w_k$ rooted at $B$ and for $w_{k+1} \ldots w_j$ rooted at $C$, then we can count the number of parse trees of $w_i \ldots w_j$ rooted at $A$.
You are interested in whether the number of parse trees of $w_1 \ldots w_n$ rooted at $S$ is larger than one or not. Therefore you can cap the numbers at two, thus avoiding large numbers and so reducing the running time.


Regular expression notation clarification

Usually, $\Sigma^*$ denotes the set of all strings of length zero or more over the alphabet $\Sigma$. Thus, $\Sigma^* = \{\epsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ldots\}$, where $\epsilon$ denotes the empty string.

$\Sigma^+$ is the set of all strings of length $1$ or more over the alphabet $\Sigma$.  Thus, $\Sigma^+ := \Sigma^* - \{\epsilon\} = \{a,b,c,aa,\ldots\}$.


That's not $\in$ but $\epsilon$: that is, a lowercase Greek letter epsilon. It's normally written $\varepsilon$ instead for clarity, but this author chose to use the "lunate" form for unknown reasons.

In this case, epsilon is being used as a shorthand for "an arbitrarily small but positive real number". This should probably be explained in the proof, but it's a fairly common shorthand in mathematics (for example, delta-epsilon proofs, floating-point epsilon…).

In other words, it's saying that the log of $n$ is always asymptotically smaller than $n$ raised to any positive power. In the next line it substitutes in a definite value, 0.01, for epsilon.


Is longest-path with a specific source and destination impossible in polynomial time?

The longest-path problem is $\mathsf{NP}$-hard even when a source vertex $s$ and a target vertex $t$ are specified. To see this, you can reduce an instance of (the decision version of) longest path on a graph $G =(V,E)$ with no source/destination specified to (the decision version of) this variant by:

Adding to $G$ a new path $\langle u_0, \dots, u_n \rangle$ of length $n = |V|$, and connecting $u_n$ to each of the vertices $v \in V$ via the edge $(u_n, v)$; and
Adding to $G$ a new path $\langle z_0, \dots, z_n \rangle$ length $n$, and connecting each of the vertices $v \in V$ to $z_0$ via the edge $(v, z_0)$.

Call the resulting graph $G'$. It is easy to see that there is path of length $k$ in $G$ if and only if there is path from $u_0$ to $z_n$ of length $2n + k$ in $G'$.

This shows that, if $\mathsf{P} \neq \mathsf{NP}$ your variant does not admit any polynomial-time algorithm.

If $\mathsf{P} = \mathsf{NP}$, then there is a polynomial time algorithm for the decision version of longest path (given a graph $G$,  two vertices $s$ and $t$, and an integer $k$, decide whether there is a path from $s$ to $t$ in $G$ of length at least $k$), which is $\mathsf{NP}$-Complete.

Your version of longest path can then solved in polynomial time by first finding the length $k$ of a longest path $P$ and then recursively guessing the next vertex of $P$: delete $s$ from $G$ and check, for every neighbor $u$ of $s$, whether there exists a path $P'$ from $u$ to $t$ in $G-s$. When you find a $u$ for which the answer is affirmative, solve the problem recursively on $G-s$ to find $P'$ and construct $P$ as $s \circ P'$, where $\circ$ denotes concatenation.


Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \{ |w : w \in L \}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.

Since $L \neq \emptyset$, $S \Rightarrow^* |w$ for some word $w$. Therefore:

Every rule contains at most one $S$ on the right-hand side. Indeed, otherwise you could generate a word with more than one $|$.
Every rule containing exactly one $S$ must be of the form $S \to Sw$, where $w \in \Sigma^*$. Indeed, the rule cannot contain $|$, since otherwise $S$ would generate a word with more than one $|$; and the rule cannot contain anything to the left of $S$ since then $S$ would generate a word not beginning in $|$.
Every rule not containing any $S$ must be of the form $S \to |w$, where $w \in \Sigma^*$ (in fact, $w \in L$).

Let $A$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to |w$, and let $B$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to Sw$. Thus
$$ L = |AB^*. $$
Conversely, it is easy to check that every language of this form (with $A,B$ finite) has a context-free grammar with a single nonterminal. Considering also the empty language, we have shown:

  The language $|L$ can be generated using a context-free grammar with a single nonterminal iff $L = AB^*$ for some finite (possibly empty) $A,B$.

The collection of languages of the form $AB^*$ is closed under quotient from the left, which is the following operation: $\sigma^{-1}S = \{ w : \sigma w \in S \}$. Indeed, if $\epsilon \notin A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^*$, and if $\epsilon \in A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^* \cup (\sigma^{-1}B)B^*$. Therefore, Greibach's theorem shows that determining whether a context-free grammar generates a language of the form $AB^*$ is undecidable.

Given a context-free grammar $G$, we easily construct a context-free grammar for $|L(G)$. The language of this context-free grammar can be generated by a single nonterminal iff $L(G)$ is of the form $AB^*$, and so the following problem is undecidable: Given a context-free grammar, determine whether its language can be generated by a context-free grammar with a single nonterminal.


Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158)

This algorithm appears and is analyzed in Curtis, Darts and hoopla board design. Curtis actually considers two problems:

Dartboard design: Given a sequence of numbers, find a circular arrangement $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^n |a_i-a_{i+1}|^q$ for some $q \geq 1$ (where $a_{n+1} = a_1$).
Hoopla board design: Given a sequence of numbers, find a permutation $a_1,\ldots,a_n$ maximizing $\sum_{i=1}^{n-1} |a_i-a_{i+1}|^q$ for some $q \geq 1$.

Your problem is the hoopla board design with $q = 1$. You can find a complete proof of the greedy algorithm in Curtis' paper. It's not trivial, though also not too complicated.


Undecidable problem intersection of two DCFL languages is DCFL?

Problem statement

We have two deterministic pushdown automatas (DPDA) $D_1$ and $D_2$. The problem is to decide whether there exists a DPDA $D$ such that $L(D) = L(D_1) \cap L(D_2)$.

Post correspondence problem

The proof is based on the fact that Post correspondence problem (PCP) is undecidable. Suppose we have a PCP problem with two input lists $\alpha = (\alpha_1, ..., \alpha_n)$ and $\beta = (\beta_1, ..., \beta_n)$

Define languages

Let $$L = \{i_1...i_k\#j_m...j_1\$\beta_{j_1}...\beta_{j_m}\$\alpha_{i_k}^R...\alpha_{i_1}^R | \;1 \leq i_l \leq n, 1 \leq j_l \leq n \}$$
One can constructively show that there exists a DPDA $D_1$ that accepts $L$.
From the other hand, the language with words $u\$u^R\#v\$v^R$ also has DPDA $D_2$. Let's call this language $L_{rev}$.

Let intersection language be $L_{\cap} = L \cap L_{rev} $

Emptiness of $L_{\cap}$ is equivalent to PCP decidability

Consider a word from $L_{\cap}$. It is like $i_1...i_k\#j_m...j_1\$\beta_{j_1}...\beta_{j_m}\$\alpha_{i_k}^R...\alpha_{i_1}^R$ and like $u\$u^R\#v\$v^R$. So $\alpha_{i_1} = \beta_{i_1},..., \alpha_{i_k} = \beta_{i_k}.$

Since then, if $L_{\cap} \neq \varnothing$ then there is a solution for PCP. Otherwise, there is no solution.

Emptiness of $L_{\cap}$ is equivalent to existing of $D$

Furthermore if $L_{\cap} = \varnothing$ then $L_{\cap}$ has DPDA because it is empty.
Using pumping lemma, one can show that if $L_{\cap}$ is not empty then this language is not context-free. Since languages of DPDAs are subset of context-free languages then $D$ does not exist.

Conclusion

Assume we can decide if $D$ exists. Let's take our PCP, construct our languages and answer if $D$ exists. If it does exist, then the intersection language is empty and the PCP doesn't have a solution. Otherwise, it has. This way, we decide whether a solution for PCP exists. But this problem is known to be undecidable. We have come to a contradiction. Consequently, the assumption is wrong and the problem of deciding whether $D$ exists is undecidable.


Relation between problems and algorithms

I think the question is more philosophical than scientific, and indeed, as @raphael mentioned, the problem is in the definition of a "Problem".

Algorithm, in the simplest way, is a function (a mapping).
It gets an input (instance) $in \in I$ and gives an output $out \in O$.
For any instance $in$ there is only a single output $out=\mathsf{ALG}(in)$.
Therefore, the algorithm solves only a single problem — that is, it defines only a single mapping from $I$ to $O$.

True, if you have two problems (mappings), $P_1 : I_1 \to O_1$ and $P_2: I_2 \to O_2$ we can construct a "single" algorithm that solves "both". It gets as an input the pair $(in,type)$. If $type=1$ it returns $P_1(in)$ and otherwise it returns $P_2(in)$.

But again, this fancy algorithm can be seen as solving a single problem from the domain $(I_1\cup I_2) \times \{1,2\}$ into $O_1 \cup O_2$.


Solving " Tricolor Arrangement " Efficiently

Here is an algorithm with $O(n)$ time-complexity.

First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.

Second, we can solve the following equations for nonnegative integer variables $a_k$, $1\le k\le6$ in $O(1)$ time.

$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$

Third, we arrange the three rows into the following configuration.
$$
\begin{array}{|l|l|l|l|l|l|} \hline
    a_1\text{ red} & a_2\text{ red} & a_3\text{ white} & a_4\text{ white} & a_5\text{ blue} & a_6\text{ blue}  \\\hline
    a_1\text{ white} & a_2\text{ blue} & a_3\text{ blue} & a_4\text{ red} & a_5\text{ red} & a_6\text{ white}  \\\hline
    a_1\text{ blue} & a_2\text{ white} & a_3\text{ red} & a_4\text{ blue} & a_5\text{ white} & a_6\text{ red}  \\\hline
\end{array}
$$

We are done.

Here are a couple of exercises that fill the gap in the above specification of the algorithm.

Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1\le k\le6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $\sum_{i=1}^3r_i=\sum_{i=1}^3w_i=\sum_{i=1}^3b_i=n$. Show that there is always a solution.

Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.

Here is a problem that may not be easy to do.

Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant.  (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)


Definition and example of search problem

Here is an example of a search problem:

  Given a CNF $\varphi$, find a satisfying assignment $x$.

Every satisfying assignment would do. A machine solves this problem if on input $\varphi$:

If $\varphi$ is satisfiable, then the machine outputs a satisfying assignment.
If $\varphi$ is unsatisfiable, then the machine outputs "unsatisfiable".

An important class of search problems are those that always have solutions. Here is a canonical example:

  Given an unsatisfiable CNF $\varphi$ and an assignment $x$, find a clause not satisfied by $x$.

Note that since $\varphi$ is unsatisfiable, for every assignment there is a clause which $x$ doesn't satisfy. A machine solves this problem if given $\varphi$ and $x$, it outputs a clause of $\varphi$ unsatisfied by $x$.


What guarantees do "soft" real-time operating systems actually provide

You've got it right, and Wikipedia is as informative as can be — soft real-time is not a formal characterization, it's a value judgement. Another way to say “soft real-time” is “I wish it was real-time”, or perhaps more accurately “it should be real-time but that's too hard”.
If you really want to word in the form of a guarantee, it's a guarantee of best effort rather than a guarantee of specific performance.
Or, to quote the Erlang FAQ (Erlang is a programming language originally designed for use in telephony):

What does soft realtime mean?
Cynics will say "basically nothing".
(…) Many telecomms systems have less strict requirements [than hard realtime], for instance they might require a statistical guarantee along the lines of "a database lookup takes less than 20ms in 97% of cases". Soft realtime systems, such as Erlang, let you make that sort of guarantee.

And this does provide a useful definition. Soft real-time indicates a design which is optimized towards each individual task taking no more than a certain amount of time, rather than towards optimizing the total time spent to perform all tasks. For example, a soft real-time system would aim to complete 99.9% of the requests in 10ms and process 100 requests per second, where a non-real-time might aim to proceed 200 requests per second but allow the occasional request to block for 50ms or more. A hard real-time would guarantee one request every 15ms no matter what.
Soft real-time is used for applications where a missed deadline means a degradation of service, but is not performance-critical. Multimedia and telephony are some typical use cases. Each audio or video frame must be rendered it time, or else it has to be skipped; but skipping a frame is not the end of the world. The designers of Erlang had similar objectives on reliability in other matters: they observed that it was better for a telephone exchange to very occasionally drop a call, but to be absolutely sure that the exchange as a whole would keep working come what may, than to ever risk catastrophic failure in trying to maintain connections at all cost.
In contrast, something like controlling a motor requires that the software never misses a deadline. This has costs: the overall performance is typically slower, and only relatively simple behaviors can be achieved. On the other side of the spectrum, a number crunching application typically cares only about overall performance — what matters is how fast the 1000x1000 matrices are multiplied, not how fast each column is calculated.


Finding largest farthest increasing pairs in array?

I'm going to assume that in your question, $i > j$ holds as well (if there is no such pair of values, then you have a nonincreasing array and the problem is trivial).

The two alternatives you've pointed out in your post are

$O(n)$ additional memory and $O(n)$ time
$O(1)$ additional memory and $O(n^2)$ time

An "intermediate" solution, for example, is to pick $O(\frac{n}{B} + B)$ additional memory and $O(n \cdot \left(\frac{n}{B} + B)\right)$ time. To do this, divide the array into continguous blocks of size $O(B)$, and so the number of blocks is $O(\frac{n}{B})$. For each block, store only the minimum value of the block in an array block_minimum.

Say you're at the $i$-th index. The goal is to find the first index in the array where the value of the corresponding element is greater than A[i].

First, for all preceding blocks, find the first block $j$ for which block_minimum[j] < A[i]. If such a block exists, scan that block and find the first index $k$ belonging to the block for which A[k] < A[i]. The index $k$ is the first index of the array for which A. There are $O(\frac{n}{B})$ preceding blocks.

However, if such a block doesn't exist, then second, iterate on preceding elements in the current block (there are $O(B)$ of them).

The combination of the two steps consumes $O(\frac{n}{B} + B)$ time for an index $i$. So the overall time usage is $O\left(n \cdot \left(\frac{n}{B} + B\right)\right)$ and the extra memory usage is $O\left(\frac{n}{B}\right)$ (the number of blocks).

If we choose $B = O(\sqrt n)$, we obtain a solution that uses $O(\sqrt n)$ memory and $O(n \sqrt n)$ time. This technique is commonly known as square-root decomposition.


Let's start with the simple case $g = 1$, and $f$ having positive values only (that's all we care about with functions that represent complexity).

$f \in O(1)$ means that $f$ is bounded: there exists $B$ such that $f(n) \le B$ (for sufficiently large values of $n$).
$f \in o(1)$ means that $\lim_{n\to\infty} f(n) = 0$.
$f \in \Theta(1)$ means that $f$ is bounded above and below: there exists $A \gt 0$ and $B$ such that $A \le f(n) \le B$ (for sufficiently large values of $n$).

Note that $f \in \Theta(1)$ requires a positive (nonzero) lower bound for $f$: for sufficiently large $n$, $f(n) \ge A$. If $f \in o(1)$ then for sufficiently large $n$, $f(n) \lt A$. It is possible for neither of these to hold if $f$ oscillates between “large” (bounded below) and “small” (converging to zero) values, for example
$$f(n) = \begin{cases}
  1 & \text{if \(n\) is even} \\
  1/n & \text{if \(n\) is odd} \\
\end{cases}$$
Informally speaking, half of $f$ is $\Theta(1)$ (the even values) and half is $o(1)$ (the odd values), so $f$ is neither $\Theta(1)$ nor $o(1)$, despite being $O(1)$.

With $g = 1$, there are regularity conditions on $f$ that's sufficient to make $O$ and not $o$ imply $\Theta$: this does hold if $f$ is monotonic; more generally, it holds if $f$ has a limit at $\infty$. With arbitrary positive $g$, these sufficient conditions translate to conditions on the quotient $f/g$ being monotonic (because $f \in O(g)$ iff $f/g \in O(1)$, etc.). It isn't enough for $f$ and $g$ to be both increasing or any such condition from real analysis. You can take any $g$ and multiply it by the $f$ above to get a counterexample to your conjecture.

With algebraic conditions on $f$ and $g$, if they are taken from sufficiently restricted sets of functions, the conjecture may hold. For example, it holds if they're both polynomials (for polynomials, $f \in O(g)$ if $\deg(f) \le \deg(g)$, $f \in o(g)$ if $\deg(f) \lt \deg(g)$ and $f \in \Theta(g)$ if $\deg(f) = \deg(g)$). But as soon as you add “perturbations” to $f$ and $g$, all bets are off.


The master theorem is a very thorough answer to this question.

Let us consider the three cases of the theorem, as applied to the recurrence $T(n) = aT(n/b) + f(n)$:

$f(n) \ll n^{\log_b a}$: in that case most of the work is done at the leaves.
$f(n) \asymp n^{\log_b a}$: in that case the work done at all levels is similar.
$f(n) \gg n^{\log_b a}$: in that case most of the work is done at the root.

Other recurrence relations behave differently. As an extreme example, there is no natural Case 1 for the recurrence $T(n) = T(n-1) + f(n)$.


Is every linear-time algorithm a streaming algorithm?

For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself.  For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a “single-pass streaming algorithm” which first copies the input to the work space in single pass and then only use the work space.

I think that it is typical to restrict the work space to at most polylogarithmic in the input size when talking about streaming algorithms.  Under this assumption, median selection does not have an O(1)-pass streaming algorithm by the result of Munro and Paterson [MP80]: any P-pass streaming algorithm for median selection on N elements has to store Ω(N1/P) elements.  On the other hand, median selection has a well-known deterministic linear-time algorithm [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan.  Time bounds for selection.  Journal of Computer and System Sciences, 7(4):448–461, Aug. 1973.  DOI: 10.1016/S0022-0000(73)80033-9

[MP80] J. Ian Munro and Mike S. Paterson.  Selection and sorting with limited storage.  Theoretical Computer Science, 12(3):315–323, Nov. 1980.  DOI: 10.1016/0304-3975(80)90061-4


Finding which value I will be on after a certain number of steps

A simple observation is that, with 0-based indices:
final_index = (elements_traversed - 1) mod array_length

For example, for array_length = 3 and elements_traversed = 7, final_index = (7 - 1) mod 3 = 0 (corresponding to the first element).


Communication complexity: fooling set bound for inner product function

Let $(x_i,y_i)$ be a fooling set for inner product, of size $m$. Construct an $m \times n$ matrix $X$ whose rows are $x_i$ and an $n \times m$ matrix $Y$ whose columns are $y_i$, and consider the matrix $M = XY$ (arithmetic is over the field $\mathbb{F}_2$). The decomposition $M=XY$ shows that $M$ has rank at most $n$.

Suppose first that $\mathrm{IP}(x_i,y_i) = 1$ for all $i$, and so for each $i \neq j$, either $\mathrm{IP}(x_i,y_j) = 0$ or $\mathrm{IP}(x_j,y_i) = 0$.
Consider the Hadamard (entrywise) product of $M$ and $M^T$. It is known that rank is submultiplicative with respect to entrywise product, and so the rank of $M \circ M^T$ is at most $n^2$. On the other hand, $M \circ M^T$ is the identity matrix, and so has rank $m$. We conclude that $m \leq n^2$.

When $\mathrm{IP}(x_i,y_i) = 0$ for all $i$, we consider the matrix $M' = M+J$, where $J$ is the all ones matrix. Since $J$ has rank 1, the rank of $M'$ is at most $n+1$, and so the argument in the preceding paragraph shows that $m \leq (n+1)^2$.


Is $DSPACE(f) \subseteq DTIME(f)$ always?

We don't know that $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$ is ever true and we suspect that it's never true.

A Turing machine that uses space $f(n)$ can run for $2^{O(f(n))}$ steps without getting stuck in an infinite loop, so it should be able to do much more than a Turing machine that can only run for $f(n)$ steps.  As you've observed, if $\mathrm{DSPACE}[f(n)]\subseteq\mathrm{DTIME}[f(n)]$, then $\mathrm{DSPACE}[f(n)]=\mathrm{DTIME}[f(n)]$ and we have no reason to think that would ever be true for reasonable functions.


Do static and dynamic scoping matter to the closure of a function?

I'd view it this way:

In dynamic scoping, functions only ever access the local environment
In lexical scoping, functions access the environment in which they are created. Because this is non-local to their calling environment, it must be stored in a closure.

Closures really aren't a thing in dynamic scoping: instead of looking for variables in the closure, you look for variables in the environment in which the function was called.

The process of closing over (storing) the environment is what makes static scoping static scoping.


What is the order of this traversal method?

This is a depth first recursive binary tree traversal.

Such a traversal may be qualifed as pre-order, in-order, or post-order
if you do some specific action on each node, before the first
recursive call, between the two recursive calls, or after the second
recursive call.

Actually, you can have several actions to perform, some in pre-order,
some in in-order, and some in post-order.

In your case, you have to collect and combine the information from the
two subtrees, and that is necessarily in post-order. But it is just
using terminology, which I see as moderately meaningful in this context.

These concept often suppose an order of the daughters of a node, but this is largely irrelevant here. You can process your subtrees in any order, left first or right first. I guess that is also why I am a bit reluctant to make this postorder distinction. The pre-order, in-order, post-order distinction assumes you are exploring depth first from left to right.

They also correspond to distinct linear notations for representing binary trees, where nodes are labeled differently from leaves: prefix, infix and postfix.


Computation is effectively computable in theory and in practice

The only definitions of the term "effectively computable" that I can find online are that the phrase just means "computable" (which is usually taken to mean "Turing-computable"). As such, computability is an absolute concept: either a function is computable or it is not. Are you asking about whether a function that is computable can actually be computed in practice? If so, the answer is clearly no: it's easy to construct families of problem instances that would require more time than the expected lifetime of the sun, for example. For example, take large instances of EXP-complete problems: $2^{100}$ exceeds the age of the universe in nanoseconds.  (That is, a 1GHz computer that had been running since the beginning of time wouldn't have executed $2^{100}$ instructions yet.)


Is there an FPRAS for the number of min st cuts in general graphs?

The Provan and Ball paper actually shows a 1-1 reduction from bipartite independent sets (BIS) to min st cuts. So an FPRAS for min cuts would imply an FPRAS for #BIS. However, #BIS is not known (and thought unlikely) to have an FPRAS [1][2].

[1] Dyer, Martin, et al. "On the relative complexity of approximate counting problems." International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer, Berlin, Heidelberg, 2000.

[2] Dyer, Martin, Leslie Ann Goldberg, and Mark Jerrum. "An approximation trichotomy for Boolean# CSP." Journal of Computer and System Sciences 76.3-4 (2010): 267-277.


"The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value." If that were true, your scheme would be able to compress every input by at least one bit. This is provably impossible by a simple counting argument (there are $2^n$ $n$-bit strings but only $2^n-1$ strings of length less than $n$), so your claim cannot be true.


A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}

There can be multiple grammars for one language, all equally valid.

We generally don't check solutions to exercises here.  The way to tell for yourself whether your answer is correct is to prove it correct: see How to show that L = L(G)? for techniques on how to do that.


1) Yes, for OSes that support memory-mapped files. The OS simply allocates a region of the virtual address space for the file, and sets up its paging algorithms so that,

when a page is accessed but is not in RAM, it is loaded in RAM
when there's little RAM left, some memory-mapped pages can be saved to disk and freed (they can be reloaded later on, if needed, from disk)

This is very similar to what happens with swapping.

2) On 64 bit systems, I'd say that virtual address space is a non-issue. Even with files as ridiculously large as 1PB=1024TB each, you'd have to map 16000+ of them to exhaust the space. Even if some address space is reserved by the OS, this limitation is irrelevant until we can store petabytes very easily.

On 32-bit systems, yes, that can be an issue.

For a possible reason: read-only memory-mapped segments are cheap. The OS can unload their pages when memory becomes too tight, without accessing the disk. If the process used regular memory the access would be less efficient, unless the process implements some memory-management itself. The process is simpler to design since it can exploit the OS for making access efficient, and pretend a large file was fully loaded in RAM, roughly.

Read-write memory-mapped segments are less useful, in my opinion, but those are also simple to use by the process.

3) the file is read from (and written to, if the mapped segment isn't read-only) disk. But this is done by the OS, in its paging routines, not by the process.


Hard disk scheduling - N-set-SCAN vs FSCAN

If you take a peek at how real operating systems do it, the answer is that they use algorithms that are orders of magnitude more complex than either.

If I told you the dirty secret behind operating systems (and compiler, and...) text books, I'd have to kill you afterwards.

  Text books only show you the parts where there is some hints of order (some theory behind the algorithms). Most of an operating system's code is battling unruly hardware, work around device bugs, get some half-decent answer out of woefully inadequate data, and do all that fast. Many algorithms are heuristics, derived by trying many ideas, keeping and refining those that worked best. For compilers, the authors of the book describing lcc say that the contents of most compiler books was around 5% of the code of the compiler, and the bug rate in that negligible. I'd say operating systems aren't much different.


Consider a standard coding of Turing machine $T_0$, $T_1$, $T_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a non-computable bijection. Define a new coding of Turing machines $T'_n = T_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but it is not equivalent to $T$ by a computable bijection (or else $b$ would be computable).


I can't understand this example of PDA Automata

The idea of this PDA is very simple. Start with a PDA for $L' = \{ w \in \{a,b\}^* : |w|_a = |w|_b \}$, and now modify it as follows:

Whenever you read $a$, simulate the original PDA reading $aa$.
Whenever you read $b$, simulate the original PDA reading $bbb$.

Hopefully you can see why the new PDA accepts $L$ given that the original one accepted $L'$.

The PDA for $L'$ maintains a stack which can be of three different types, depending on the word $x$ seen so far:

If $|x|_a = |x|_b$ then the stack contents is $Z_0$. In particular, this is also the initial stack.
If $|x|_a > |x|_b$ then the stack contents is $B^{|x|_a - |x|_b} Z_0$.
If $|x|_a < |x|_b$ then the stack contents is $A^{|x|_b - |x|_a} Z_0$.

When the top-of-stack is $Z_0$ we know that $|x|_a = |x|_b$, and so we optionally move to the final state; the PDA will accept only if $x = w$, since otherwise it will get stuck.

When converting this PDA to the one for $L$, we use epsilon transitions to simulate reading the second $a$ and the second and third $b$s.


is advice function and an oracle the same thing?

No, they are not the same.  An oracle is something that an algorithm can send inputs to, and get back outputs, possibly many times.  Advice is a single value that is provided to the algorithm, and depends only on the length of the input to the algorithm.


You have a small (but crucial) misunderstanding of what the VC dimension of a class is.

The VC dimension is the maximal number $d$ such that there exists a set of $d$ points that is shattered by the class.
It doesn't mean that every set is shattered.

In this case, indeed 4 co-planar points cannot be shattered, but if they are placed in a tetraeder then they can be.

This is similar to the case of 2D: 3 points that are co-linear cannot be shattered by a line, but there exists a set of 3 points that can be shattered.


Selecting random points at general position

Here's an approach that I think achieves $O(n^2)$ running time, as long as the points are not too dense (as long as $n$ is not too large compared to the size of the region).

Store the set of all slopes of lines between any pair of points.  There are $O(n^2)$ pairs of points, and each pair of points determines line; add that line to the set.  I suggest you store this as a hash table that maps the slope $s$ to the set of pairs $(P,Q)$ of points which are at slope $s$ from each other.

Now to add a new point, pick a point $R$ uniformly at random.  Pair $R$ up with each other point, say $P$.  Compute the slope of the line from $P$ to $R$.  Look up that slope in the hash table, and see whether the corresponding set contains the point $P$.  The latter can be done in $O(1)$ expected time if you use suitable data structures for the hash table and for storing the set (in particular, the entry corresponding to slope $s$ can be a hash-set of all of the points that participate in a pair whose slope is $s$).  Since $R$ can be paired up with $n$ other points, this check will take $O(n)$ expected time.

Now as long as the number of points is not too dense (so that you don't reject a point more than a constant fraction of the time), the expected running time will be $O(n^2)$.


Simpler proof of Rabin's Compression Theorem?

It is hard to answer this question since it is hard to find a formal statement of Rabin's compression theorem. Here is one from the book Complexity Theory and Cryptology: An Introduction to Cryptocomplexity by Jörg Rothe, page 63:

  For each time constructible function $t(n)$ there exists a decidable set $D_t$ such that each deterministic Turing machine $M$ deciding $D_t$ must run in time larger than $t(n)$ for all large enough $n$.

Granted, this is not exactly your statement (it might be a different theorem proven in the same technical report of Rabin from 1960, or perhaps a different publication of Rabin from the same year), and it also differs from the rather unclear statement in Levin's lecture notes, which is closer to your statement but also seems to mention a predicate (though Levin's proof doesn't result in a predicate).

Both statements are somewhat different than your informal statement that every complexity class has a problem that can be solved optimally in it. They also seem to mention that the problem can be chosen to be a predicate.

In order to make progress, I suggest that you update your question with a complete formal statement of Rabin's compression theorem as you understand it, explaining no longer standard notions such as volume. Then try to formally prove the theorem along the lines you mention. If you succeed, include the proof. If you fail, you have answered your own question.

It is likely that there is some easy version of the theorem that does follow from your argument, but the actual theorem is harder, requiring either a delicate priority argument (like in the book) or a Kolmogorov complexity argument (like in Levin's notes). This may be due to one of two features of Rabin's theorem:

It gives a predicate rather than an arbitrary function.
The actual guarantee is a bit different. For example, in Levin's version you should be able to compute the function in all volumes which are asymptotically larger than the optimal complexity.

Also, depending on your computation model, your own function might not be computable in your own time bound (though multitape machines seem fine here).

Why am I so sure that there is something wrong with your argument? Your argument is very simple, and I find it hard that it was missed by both Rabin and Levin. It is much more probable that it just doesn't work, or that it proves a weaker version of the theorem.


Is there any limit to what we can define as a language?

No. Any set of strings over some alphabet is a language. Typically, in computer science, we're only interested in the case where the alphabet is finite and usually, though not always, we only consider finite strings, too.

  Is any set of symbols a language?

A set of symbols is an alphabet. A language is a set of strings whose characters are in some alphabet, though you could also consider an alphabet to be a language of words of length 1..

  For example, given the alphabet $\Sigma$, do we say that the language $L=\Sigma$ has alphabet $\Sigma$?

As above, yes.

  Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)?

A language is a language; the definition hasn't changed over time so I'm not sure what you mean by a "modern equivalent". A complexity class $C$ is a class of languages, classified by the amount of some resource (typically time or space) required to determine whether, for some $L\in C$, an input word is a member of $L$.

  I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

Languages and decision problems are essentially the same thing. Given a language $L$, the corresponding decision problem is "Given a word $w$, is $w\in L$?" More formally, a problem is a collection of objects of some kind (e.g., graphs or formlas) such as the 3-colourable graphs or satisfiable 3CNF formulas. A language then, is an encoding of the elements of a problem as strings, e.g., strings representing the adjacency matrices of 3-colourable graphs.


The self-information is a measure of deviation from expectation of random variable in shannons (bits, the unit may vary when used in different context) when sampling a random variable.

Straight from definition it is reciprocal of probability of occurence for some event, so a little example would help.

Imagine that somewhere it rains only in one month every year (for some random number of days). From the event it is a sunny day we know almost nothing and it could be any month, so it meets the common (the most probable) outcome and we learned almost nothing, so it is not very important piece of information. But the event it rains gives us the exact month, so it is worth more in the sense that we have learned more, hence the higher self-information.

Some people call it a surprisal, which means "not the expected outcome". You need more memory to store rare event, (sorry for circular ref, but it is one of consequences, for the compression) think about the entropy encoding, it takes the most amount of bits to store the least expected events. Huffman codes and self-information.


It's just that the logistic function reaches its saturated regime around +-4.6, as in the image. So, any absolute values of x much lower than this will give you results around 0.5. Increasing the absolute value of the weights (all of them) you'll get nearer the saturated region, resulting in outputs closer to 0 and 1. Nevertheless, if you use the step function at the output layer instead of the logistic, you'll get the correct values exactly for both sets of weights: 0 0 0 1.


Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not?

Using Ran G.'s comment which links to a very similar question:

Suppose $L$ is regular. $M=a^*b^*$ is regular, too, so since regularity is closed by set difference, $M\backslash L=\{a^nb^n\}$ would be, too, which is the usual counterexample.


Is the set of strings with equal number of 010’s and 101’s regular?

Try writing a few words that are contained (and not) in your language. See if you can discern some structure that helps answering your question.

Hint: CS teachers are a devious, sadistic bunch. This might be a trick question...


Implementing Gauss–Legendre algorithm using arbitrary-length rationals

It sounds like you are using arbitrary-precision arithmetic, i.e., you represent each rational number as a ratio $a/b$ where $a,b$ are stored as arbitrary size integers (bignums).  If that's the case, that's probably the source of your problem.

Don't do that.  That's highly inefficient, because you'll end up with very large integers $a,b$, that may be far larger than needed for the desired precision level; and it'll be imprecise, because of the ⌊√a⌋/⌊√b⌋ problem you mention.

Instead, use fixed-precision arithmetic: each number is represented directly as a number (not a ratio) using a fixed-precision representation.  That will be much more efficient and more accurate.  It won't have the problem of ⌊√a⌋/⌊√b⌋, since you're not limited to a ratio of integers.  You might need to find a library that implements fixed-precision arithmetic, or to implement that part yourself, and you'll probably need to estimate the appropriate precision level based on the number of iterations and the amount of precision achievable with that given precision level.


Assuming you mean simple cycles (otherwise the number is infinite) - yes, of course the number can be exponential: consider the complete graph on $n$ vertices, then every sequence of distinct vertices can be completed to a simple cycle. So you get at least $n!$ cycles.

Even if you ignore cyclic permutations of a cycle, this is still exponential: you can take only cycles of length $n/2$, and you have more than ${n\choose n/2}$ such cycles.


If they can only move the head right, they are equivalent to finite automata.


How to give an approximation algorithm for this unusual bin packing problem?

Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the case of $d$ constraints (in your case, $d = n$) many natural algorithms give a $d+1$-approximation.


You haven't fully specified the greedy algorithm, so let's assume that at each step you select a vertex covering the most new edges. In that case, this is the greedy algorithm for the more general problem of Maximum Coverage, whose approximation ratio is known to be roughly $1-1/e$, which is even larger than $1/2$. For a proof, see for example here. There is also a less classical proof that doesn't use elements at all, but only the monotonicity and submodularity properties of the coverage function (the function getting ass input a set of vertices and outputting the number of edges covered).

There are somewhat better algorithms that use the fact that each edge is covered by only two vertices. Examples are the LP-based algorithm and the non-oblivious local search algorithm. It is also possible that the greedy algorithm performs better in this case.


Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?

This is called the Dominating Set problem, and it is indeed NP-hard. In fact, it's in some sense harder than Vertex Cover, since it's not fixed parameter tractable (FPT) with respect to the solution size $k$.


Are event and mode well defined terms in CS literature?

I'm not sure whether they have accepted meanings, but to the extent that they do, an "event" happens at an instantaneous point in time, as opposed to something ongoing.  If I was reading something that used the word "mode", I probably wouldn't be sure what is meant by "mode" without looking at the context.

I'm not sure whether you should expect precise, widely-accepted definitions for terms that are used informally.


How to perform local search to find maximal induced subgraphs?

All three problems are easy to formalize as local search problems.  Let $f$ be a function that measures the quality of a solution $s$, in your cases

$f(s)$ is

the number of edges (or vertices) in the tree $s$
the number of edges (or vertices) in the forest $s$
the number of vertices (?) in the bipartite graph $s$

and your goal is to maximize $f$.

Lastly, you need to define a neighborhood function $N(s)$ that gives all possible ways of modifying a current solution $s$ to a new solution $s'$.

To illustrate $N(s)$ in the simplest case, the tree:
$$ N(s) = \{ X \subseteq V(G) \mid \text{is_tree}(V(s) \setminus X \cup (X \setminus V(s)) \}, $$

and my apologies for the terse syntax.  It is simply all the ways you can delete a certain set of vertices from the solution $s$, simultaneously adding a different set of vertices, at the same time keeping the property that the new $s'$ is a tree.

Now, the search algorithm simply starts with a random solution (tree) $s$ (which might be the empty tree), and just randomly walk $N(\cdot)$.


What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups?

Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree.  Now for each rectangle $R$, you can determine whether there exist any other rectangles within the prescribed distance, and if so, list them all.  Then you can merge all such rectangles into the same group by using a union-find data structure to keep track of which rectangles are in which group.  Each rectangle starts out in its own group, and when you find two rectangles that are close to each other (within the prescribed distance), you use the Union operation to merge their two groups.

A number of optimizations are possible.  Here is one simple optimization.  For each internal node in the quadtree, keep track of a single bit that indicates whether all points (rectangles) in the subtree under that node are known to be in the same group.  When enumerating neighbors to $R$, if that bit is set, then you don't need to enumerate all points under  that node; it's enough to find any one point (rectangle) under that node, and merge it into the same group as $R$.


What is the name of the other vertex of an undirected edge?

There's no set phrase; any clear description will do. "The other vertex in $e$", "the other endpoint of $e$", "$b$".

I've never heard of "co-vertex" and "neighbouring vertex" is vague, since $a$ might have multiple neighbours.


Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Let's denote the sets of states in $A_1$ and $A_2$ by $Q_1$ and $Q_2$, respectively. Furthermore, let's denote by $F_1$ and $F_2$ the accepting states of these machines, $q_0'$ and $q_0''$ the start states of these machines, and $\delta_1$ and $\delta_2$ the transition functions of these machines.

We can use the Cartesian-product-machine construction to define an automaton $A_3$ which accepts $L(A_1) \cup L(A_2)$ as follows. First, let $Q_3 = Q_1 \times Q_2$ be the set of states. Now, define $F_3 = \{(q_1, q_2) \in Q_3 \mid q_1 \in F_1 \vee q_2 \in F_2\}$. Let $q_0'''$ be the start state and define $\delta_3((q_1, q_2), \sigma) = (\delta_1(q_1, \sigma), \delta_2(q_2, \sigma))$.

Consider the functioning of such a machine. By virtue of its being in some state $(q_1, q_2) \in Q_3$, we know by construction that $A_1$ would have be in state $q_1$ after seeing the same input, and we know $A_2$ would be in stare $q_2$ after seeing the same input. $A_3$ will accept if either $q_1$ was accepting in $A_1$ or $q_2$ was accepting in $A_2$, because of how we defined $F_3$.

Intuitively, this works by demonstrating that we can model two DFAs executing in lockstep using the DFA formalism itself; two DFAs executing in lockstep is equivalent to the DFA constructed above. We have chosen to accept a string if either of the machines accepts, but as you can see, we could define a DFA for any of the standard binary set operations: union, intersection, difference, symmetric difference, etc.


Search for specific element in sorted array

Define $B[i] = (A[i]-2)/3$. Now you want to find an index $i$ such that $B[i] = i$.


Is a Turing Machine "by definition" the most powerful machine?

I agree that a Turing Machine can do "all the possible mathematical problems".

Well, you shouldn't, because it's not true. For example, Turing machines cannot determine if polynomials with integer coefficients have integer solutions (Hilbert's tenth problem).

Is Turing Machine “by definition” the most powerful machine?

No. We can dream up an infinite hierarchy of more powerful machines. However, the Turing machine is the most powerful machine that we know, at least in principle, how to build.  That's not a definition, though: it is just that we do not have any clue how to build anything more powerful, or if it is even possible.

What's the new thing Alan Turing gave us?

A formal definition of algorithm. Without such a definition (e.g., the Turing machine), we have only informal definitions of algorithm, along the lines of "A finitely specified procedure for solving something." OK, great. But what individual steps are these procedures allowed to take?
Are basic arithmetic operations steps? Is finding the gradient of a curve a step? Is finding roots of polynomials a step? Is finding integer roots of polynomials a step? Each of those seems about as natural. However, if you allow all of them, your "finitely specified procedures" are more powerful than Turing machines, which means that they can solve things that can't be solved by algorithms. If you allow all but the last one, you're still within the realms of Turing computation.
If we didn't have a formal definition of algorithm, we wouldn't even be able to ask these questions. We wouldn't be able to discuss what algorithms can do, because we wouldn't know what an algorithm is.


Why are palindrome and not-palindrome both context-free?

You make the mistake of assuming that

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \forall\, x \in X. \lnot P(x)$

while in truth

$\qquad \lnot \forall\, x \in X. P(x) \quad \equiv \quad \exists\, x \in X. \lnot P(x)$.

In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.

As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,

$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.

The complement is a nice exercise and can be found elsewhere on the site.


What is the minimum pumping length of the union of two languages?

Consider the following two languages:
$$
L_0 = 1(0+1)^* + 0^{n_0}, \\
L_1 = 0(0+1)^* + 1^{n_1}.
$$
The minimum pumping length of $L_0$ is $n_0 + 1$, and that of $L_1$ is $n_1 + 1$. Yet $L_0 \cup L_1 = (0+1)^+$ has a minimum pumping length of 1.

What does hold is that the pumping length of $L_0 \cup L_1$ is at most the maximum of the pumping lengths of $L_0,L_1$. In fact, it can be any number between 1 and that maximum. Indeed, suppose that $1 \leq a,b \leq c$, and consider the languages
$$
\begin{align*}
L_0 &= 1(0+1)^* + 0^{a-1}, \\
L_1 &= 0(0+1)^* + 1^{c-1} + 2^{b-1}.
\end{align*}
$$
The maximum pumping length of $L_0$ is $a$, that of $L_1$ is $c$, and that of $L_0 \cup L_1 = (0+1)^+ + 2^{b-1}$ is $b$.


What algorithm to use for this kind of routing optimization?

The answer depends on what you mean by "safest".

According to one interpretation, each short stretch of the route has a "danger" rating, and the overall danger of a route is the sum of the dangers of the individual stretches. In this case your problem is just shortest path in disguise – given each edge a weight according to its danger. If you want to consider both the danger level and the length, assign the weights as some linear combination of the two.

According to another interpretation, the danger of a route is the maximum of the dangers of the individual stretches. In this case you can use binary search to reduce your problem to shortest path. Given a danger level $D$, you can compute the shortest distance that only goes through edges of danger at most $D$. In this way you can find the minimal $D$ for which it is possible to get from A to B, as well as (for example) the minimal $D$ for which it is possible to get from A to B using a path at most twice the distance from A to B.


Given two vertices $u$ and $v$, I want to find the length of the shortest path between them. I think that the shortest path should pass through $\gcd(u, v)$ or $lcm(u, v)$ (lowest common multiple), but I can't prove it. Can someone tell if my theorem is correct?

I think the claim is not strictly true as written, and I will provide a counter-example.

First a claim: For any two vertices in this graph, there is a shortest path between them which uses only edges whose weight is a prime.

Pf: If the weight is not a prime, it can be factored, and this yields a different path between the same two vertices. The sum of any sequence of positive numbers all at least 2 is less than or equal to their product (trivial, by induction), so that is a shorter path, which can be substituted into the original in place of the non-prime edge.

(Note that a slightly stronger thing we could say is "shortest paths can only contain edges whose weight is a prime or is 4", proof left to reader.)

Now take two arbitrary non-prime coprime numbers, say, 6 = 2 * 3, and 35 = 5 * 7.

Clearly, a shortest path using only prime edges has at least 4 steps.

Also, we can ignore the possibility of a shortest path using edges corresponding to primes which are not {2, 3, 5, 7} -- by commutativity of multiplication, any such edges can be reordered until the end, without changing the weights of any of the edges, and the total effect of any such edges for primes which were not originally involved must be a loop, so in fact they could be skipped.

It follows (from this argument) that the shortest paths from 6 to 35 are in bijection with orderings of {2, 3, 5, 7}. They all have the same cost, which is 2 + 3 + 5 + 7.

Some of them pass through the lcm or gcd, but some do not. For instance, 6 -> 2 -> 10 -> 70 -> 35.

I think you can prove that there is a shortest path passing through the gcd? And there is a shortest path passing through the lcm?

I think the idea to prove that would be, look at the edges in the path, and look at which ones make the number larger, and which ones make the number smaller. Then rearrange the edges using commutativity of multiplication as before. If you sort it so that those that make the number larger come first, and then are followed by those that make the number smaller, then in the middle I think you pass through the lcm. If you sort it so that those that make the number smaller come first, then I think you pass through the gcd.


How does the processing happen in a CPU when it uses Virtual Memory?

Virtual memory is handled just in the part of the CPU that handles reading and writing memory.

At some point, the CPU has calculated a memory address and has decided to read or write memory at that location. If there is no virtual memory used, then the memory address is the actual address in the physical memory connected to the CPU. With virtual memory, the memory access part of the CPU will first translate the virtual memory address to a real memory address.