Transformation from one feature space to another

This is just the explicit form of the feature map for a homogenous, degree 2 polynomial kernel.  Here your input space is $\mathbb{R}^2$ and the feature space can be identified with $\mathbb{R}^3$.  The point the author is making is that instead of computing the feature map explicitly, and then taking the Euclidean inner product $\langle \Phi(p),\Phi(q)\rangle$, you can just compute $\langle p,q\rangle^2$.


How does the automatic complexity analysis of Codility work?

Probably only Codility knows for sure how they do it.  But here is how I bet they do it.

First, they devise a set of test cases of varying sizes.  They run your program on each test case and time how long it takes.  This gives them a set of observations $(n_i,t_i)$, where $n_i$ is the size of the $i$th test case and $t_i$ is the time your program takes given that input.  These can be viewed as a set of points in the 2D plane.

Second, they try to fit a curve to these points.  For instance, they check whether a line appears to fit the points, or a quadratic, or a cubic.  They probably have a library of a set of families of curves (e.g., $cn, $cn^2$, $c n \lg n$, $c \lg n$, and so on), and they check each to which ones are consistent with the observation.  Then they output that one as the running time of your algorithm.

I would imagine some adjustments might be necessary.  Rather than checking whether the points fit the curve, it might be necessary to check whether the points all fall below the curve.  For instance, rather than checking whether there exists a constant $c$ such that $t_i \approx c n_i^2$ for all $i$, they might check whether there is a constant $c$ such that $t_i \le c n_i^2$ for all $i$ (with some constraints on $c$, e.g., $c \le 1000$).  Out of all asymptotic running times that seem to be consistent with the observations, they select the asymptotically smallest one and output that one.

This approach has the advantage that it does not require analysis of source code.  All they need is the ability to run your program and time its running time.

At the same time, this heuristic is definitely not foolproof: it can give the wrong answers in some cases.  See How to fool the plot inspection heuristic?


Can Turing Machines decide on computability?

A real number cannot be input into a Turing machine, since it is an infinite object. There are various models for providing a Turing machine with oracle access to real numbers, but these are by definition computable.

You could imagine a Turing machine given a ZFC definition of a real number, and in that case it's undecidable. For example, given a Turing machine $T$, you could define a number $x$ as follows: if $T$ doesn't halt in $n$ steps then the $n$th bit of $x$ is zero. Otherwise, it is the $n$th bit of Chaitin's constant. So $x$ is computable if and only if $T$ never halts.


Is this problem NP-Complete (Bin packing with seperable items and penalty)?

We can reduce from 3-Partition. In 3-Partition instance we have:

A set, $S = \{ s_1, s_2, ..., s_n \}, n = 3m$, where $m$ in a
positive integer
$B = \sum_{ i = 1 }^{ n } \frac { s_i } { 3 }$
$\frac { B } { 4 } < s_k < \frac { B } { 2 }$, $\forall k
   \in \{ 1, ..., n \}$

Where the problem is whether $S$ be partitioned into m triples such that they all have the same sum, $B$.

To reduce from my problem, let:

$N = m$
$F$ may be set to anything
$V = B + 3F$
$S_1 = S$, ie. the values from the 3-Partition instance become the item sizes in the new problem

In the reduced problem the total space available is:

size of each bin $\times$ number of bins

$ = (B + 3F) m $

$ = Bm + 3mF $ (1)

And the total space that the items will occupy is at least:

Sum of item sizes from $S_1 +$ number of pieces, $p$, from items $S_1 \times$ size of items in $S_2$

$ = Bm + pF $ (2)

We know that:

$ p \geq n = 3m $ (3)

and

total space occupied $\leq$ total space available:

(1),(2) $\Rightarrow Bm + pF \leq Bm + 3mF $

$\Rightarrow p \leq 3m $

(3) $\Rightarrow p = 3m $

Implies that for the reduced problem to be satisfiable then all the available bin space is occupied by the items, and that it's not possible to separate any of the items from $S_1$ into smaller pieces. (4)

It's clear now that this is equivalent to the 3-partition problem, but I've shown it below:

If a 3-partition problem is satisfiable then there exists corresponding triplets in the reduced problem that can be placed into each of the separate bins with exactly $3F$ remaining in each to allow for the required items from $S_2$. Hence 3-partition $\Rightarrow$ reduced problem. (5)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition), we know that if we place more than 3 items in a bin that we exceed the capacity of the bin:

$s_{1,k} > \frac {B}{4}$

If we place $x$ items into a bin, where $s_{min}$ is the size of the smallest item:

total size of bin used for $x$ items $ = x ( s_{min} + F )$ (6)

Because $\frac {B}{4} < s_k$ from the original 3-particiation problem, and item sizes in $S_1$ correspond to the values in $S$ (from 3-partition):

$ s_{min} > \frac {B}{4} $ (7)

(5), (6) $ \Rightarrow$ total size of bin used for $x$ items $ > x ( \frac {B}{4} + F )$

$\Rightarrow$ total size of bin used for $x$ items $>$ total capacity of bins $ = B + 3F $, $ \forall x > 3 $

$\Rightarrow$ A satisfiable solution to the reduced problem has no more than 3 items in any bin. (8)

Likewise, because $s_k < \frac {B}{2}$ from the original 3-particiation problem:

$ s_{max} < \frac {B}{2} $

$ \Rightarrow$ total size of bin used for $x$ items $ < x ( \frac {B}{2} + F )$

$\Rightarrow$ total size of bin used for $x$ items $<$ total capacity of bins $ = B + 3F $, $ \forall x < 3 $

(4) $\Rightarrow$ A satisfiable solution to the reduced problem has no fewer than 3 items in any bin. (9)

(8), (9) $\Rightarrow$ A satisfiable solution to the reduced problem has exactly 3 items in each bin. (10)

If any reduced problem is satisfiable: We know from (4) that the items cannot be separated; we know from (10) that each bin contains exactly 3 items.

$\Rightarrow$ The triples from each bin (items from $S_1$) have sizes that sum to $B$, and that the sizes for each item in $S_1$ have a one-to-one correspondence to the values in the set $S$. Therefore there is a partition of the $S$ set into triples, where each of the triples sums to $B$. Hence reduced problem $\Rightarrow$ corresponding 3-partition problem. (11)

So long as we accept that the problem from the question is in NP (I'm not going to prove this!) (5), (11) $\Rightarrow$ the problem from the question is in NP-Complete.


How to remove cycles from a directed graph

There is a paper "breaking cycles in noisy hierarchies" which talks about leveraging graph hierarchy to delete cycle edges to reduce a directed graph to a DAG.

The reduced DAG will maintain the graph hierarchy of the original graph as much as possible.

The corresponding code is available on Github: https://github.com/zhenv5/breaking_cycles_in_noisy_hierarchies


If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (stored for example in 8MB text files). Of course, addition can be done very quickly compared to the value of the numbers; it runs in $\mathcal{O}(\log(N))$ time, if $N$ is the value of the sum.

This does not mean you can speed things up a little; if your processor handles 32 bits each operation, then you use $\frac{n}{32}$ time, but that is still $\mathcal{O}(n)$ and not $o(n)$.


Efficient algorithm to filter off points from a point cloud

You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time.

Your function, as python-like pseudocode:

def FilterPoints(master, subset):
    # take the list and convert it to a set ( O(|subset|)
    subset_set = set(subset)
    # iterate through master and and the points that are not in subset O(|master|)
    filtered_list = [p for p in master if p not in subset_set]
    return filtered_list

Some points:

If master is larger than subset, the algorithm will be $\mathcal O(|master|)$
The equivalent of set in C# should be HashSet


Verifying if a greedy solution is optimal for a specific instance (Set cover)

Let me formalize your problem, in two different ways:

GREEDY-SET-COVER: Given a Set Cover instance, does the greedy algorithm always produce a set cover of minimal size?
GREEDY-SET-COVER2: Given a Set Cover instance, does the greedy algorithm always produce a set cover of non-minimal size?

The two problems might seem complementary, but in fact it is not the case: if at some step of the algorithm there are several sets covering the same number of uncovered elements, the greedy algorithm must make a choice. In GREEDY-SET-COVER, we are asking whether all such choices lead to an optimal solution. The complement of GREEDY-SET-COVER2 asks whether some such choice leads to an optimal solution.
I will show that GREEDY-SET-COVER is $\mathsf{coNP}$-complete, and that GREEDY-SET-COVER2 is $\mathsf{NP}$-hard (but not necessarily in $\mathsf{NP}$). In fact, the same reduction will work for both.
Let me start by showing that GREEDY-SET-COVER is in $\mathsf{coNP}$. Given an instance of GREEDY-SET-COVER, all we need to do in order to show that it is a No instance is to give a transcript of the greedy algorithm together with a set cover which is smaller than what the greedy algorithm output. Unfortunately the same kind of witness doesn't work for GREEDY-SET-COVER2, since we would have to list all possible runs of the greedy algorithm.
In order to show that GREEDY-SET-COVER is $\mathsf{coNP}$-hard, we reduce from SAT. Let $\varphi$ be an instance of SAT with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. We first check whether there is an assignment to some variable which satisfies at least $m-1$ clauses. If it satisfies all clauses, the instance is satisfiable. Otherwise, the instance is satisfiable unless the remaining clause consists of this variable with opposite polarity. In both cases, we output an appropriate fixed instance of GREEDY-SET-COVER.
Suppose now that every assignment to a variable satisfies at most $m-2$ clauses. We will construct a Set Cover instance over the universe $\{x_1,\ldots,x_n,C_1,\ldots,C_m\}$ having the following sets:

For each variable $x_i$ and each truth value $\tau$, there is a set $X_{i,\tau}$ which contains all clauses satisfied by this assignment to $\tau$, as well as the element $x_i$.
The set $Y = \{C_1,\ldots,C_m\}$.

If the SAT instance is satisfiable, there is a set cover of size $n$, consisting of the sets $X_{1,\tau(1)},\ldots,X_{n,\tau(n)}$, where $\tau$ is a satisfying assignment. Otherwise, the optimal set covers have size $n+1$. The greedy algorithm first takes the set $Y$ (since all other sets contain at most $(m-2)+1 = m-1$ elements), and then takes one set each from every pair $X_{i,T},X_{i,F}$, in total producing a set cover of size $n+1$. This set cover has minimal size if and only if the SAT instance is unsatisfiable.
The exact same reduction works for GREEDY-SET-COVER2, since every run of the greedy algorithm must start with the set $Y$, and eventually produces a set cover of size $n+1$.


Explanation of an explanation of Turing's proof to the halting problem?

P should take two arguments: a TM M and a string x. P accepts if M halts on input x, otherwise rejects. Definition of P:

P(M, x): execute M on x and if it halts, go to the accepting state. If M doesn't halt on x, go to the reject state.

The language of the words accepted by P is Turing recognizable but not decidable. So you can define P, but the machine won't stop for all the inputs, and this is what you're trying to demonstrate.

You don't need to know the code source of P to produce P'. P' can be seen as:

P'(Q):
execute P(Q, 'Q'), where 'Q' is the encoding of the TM Q, and if P accepts then don't halt, else halt.

The point is: if you suppose that a machine P that decides the Halting Problem exists, you're going to get a contraddiction. In fact you can produce a machine P' for the complement (you can do this because we are presuming the Halting Problem is decidable), so that it stops if the machine given in input doesn't and viceversa. If you try to use P' on P', then you get an antinomy.

I'm not sure this answer to your questions..


Example Turing Machine for a time-constructible function

I think you're right, we should use asymptotic notation, for the reason you mention, but maybe somebody more knowledeable than me can weigh in if that's wrong. Here are my thoughts: A function $T$ works as a function of the number of bits on the tape, with $|x|=\lfloor\log(x)\rfloor$. Consider the function $T(n)=n$. This function maps $x\mapsto T(|x|) = T(\lfloor\log(x)\rfloor)=\lfloor\log(x)\rfloor$. This means is must count the number of bits on the tape, erase the input, and write the number, but it has only exactly enough time to read the input, and then it must halt. But since $\log(x)<x$ for some $x$, this means the machine must, on most inputs, also move back on the tape, at least to the beginning. With a multitape Turing Machine, I can think of a $(3n+\log(n))$-time machine which computes $T(n)=n$, so I think it makes more sense to use asymptotic notation.

Note that in order to make a Turing Machine, if you have trouble when $n$ is small because $T$ doesn't grow fast enough for you, you can just hardcode the first billion values into your TM, and run an honest algorithm on the remaining numbers. This is how you overcome the problem of computing, for example, $n\cdot \log(\log(\sqrt{n}))$, which requires a lot of computation but grows very slowly.

A machine which computes $x\mapsto 2^{|x|}$: read the first $1$ on the tape, then replace all subsequent numbers by $0$ and add one $0$ to the end. And you did it in $n+1$ steps exactly! That is exponentially faster than the available time.

According to this question (link), there is an alternative source of Arora and Barak which does use asymptotic notation and one by Sipser, although it doesn't provide any explicit references. As far as I know, all other definitions (like $\text{TIME}(n)$ and $\text{SPACE}(n)$) are built around asymptotic notation anyway, so it should be perfectly legal to use asymptotic notation here.


Proof that "local" minimum spanning tree is "global" minimum spanning tree

If we remove $e = (x,y)$ from $T_2$, then it breaks into two connected components, say $T_{2,x},T_{2,y}$. There is a unique path in $T_1$ from $x$ to $y$, which together with $e$ forms a fundamental cycle of $T_1$. The path starts at $T_{2,x}$ and ends at $T_{2,y}$, hence at some point it crosses between the two. Adding the corresponding edge to $T_2$ would result in a fundamental cycle containing $e$.


Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not guaranteed to be non-regular. For example, take $L_1=\Sigma^*$, $L_2=\{a^nb^n\mid n\geq 0\}$. $L_2$ is not regular but $L_1L_2=\Sigma^*$ is regular.

To prove that $S$ is non-regular using the pumping lemma, pump a string that contains more $b$s than $c$s.


If you meant what $\mathcal{O}((\log (n+7))^{\log (n)})$ is (so the power applies to the logarithm itself, not its argument), then we simplify that to $\mathcal{O}((\log (n))^{\log (n)})$; as per a suggestion by Saeed Amiri, here a proof for this equality:

Since $(\log (n))^{\log (n)}) \leq (\log (n+7))^{\log (n)})$ for all $n$, we have $\mathcal{O}((\log (n))^{\log (n)}) \subseteq \mathcal{O}((\log (n+7))^{\log (n)})$.

For the other direction, consider

$\qquad
\begin{align}
(\log (2n))^{\log (n)} &\leq c(\log (n))^{\log(n)} &\iff \\
\frac{\log(2n)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\
1+\frac{\log(2)}{\log(n)} &\leq \sqrt[\log(n)]{c} &\iff \\
\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} &\leq c
\end{align}
$

What we now notice is that $\log n$ is a non-integer bound, so we can't directly expand to a polynomial here. We could if we knew that

$\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil}$

Therefore, a small proof of the monotonicity of that function:

$\frac{d}{dx}\left(1+\frac{\log(2)}{\log(x)}\right)^{\log(x)} = \frac{\left(\frac{\log (2x)}{\log (x)}\right)^{\log (x)}\left(\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)\right)}{x \log (2x)} \geq \frac{\log (2x)\log\left(\frac{\log (2x)}{\log (x)}\right) - \log (2)}{x (\log (x))^{\log (x)}} > 0$

for all $x > x_0$ for some $x_0$ [specifically, for $x_0 = 2$; check the link to math in the comment section].

Since we now know that the function is monotonically nondecreasing for all $n > 2$, we can choose our $c$ slightly differently:

\begin{align}
\left(1+\frac{\log(2)}{\log(n)}\right)^{\log(n)} \leq \left(1+\frac{\log(2)}{\lceil\log(n)\rceil}\right)^{\lceil\log(n)\rceil} &\leq c &\overset{\text{rewriting the polynomial}}{\iff} \\
\sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq c
\end{align}

Now we use the inequality $\binom{n}{k} \leq \frac{n^k}{k!}$ and see that
\begin{align}
\sum_{i=0}^{\lceil\log(n)\rceil}\binom{\lceil\log(n)\rceil}{i}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i &\leq \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\lceil\log(n)\rceil)^i}{i!}\left(\frac{\log(2)}{\lceil\log(n)\rceil}\right)^i \\
&= \sum_{i=0}^{\lceil\log(n)\rceil}\frac{(\log(2))^i}{i!} \\
&\leq \sum_{i=0}^{\infty}\frac{(\log(2))^i}{i!} \\
&= e^{\log(2)}
\end{align}

So we know that $\mathcal{O}((\log (n+7))^{\log (n)}) \subseteq \mathcal{O}((\log (n))^{\log (n)})$ since we can choose a finite $c$ in the above inequation.

If we try to express $(\log (n))^{\log (n)}$ as a power of $n$ now, we get

\begin{align}
n^{f(n)} &= (\log (n))^{\log(n)} &\iff \\
\log(n^{f(n)}) &= \log ((\log (n))^{\log(n)}) &\iff \\
f(n) \cdot \log(n) &= \log(n) \cdot \log (\log (n)) &\iff \\
f(n) &= \log (\log (n))
\end{align}

, and so we get $\mathcal{O}((\log (n))^{\log (n)}) = \mathcal{O}(n^{\log(\log(n))})$, if that is any improvement.

(Credit where it's due: I copied this way of expressing our function as a power of $n$ from here, so google can help with this stuff, sometimes.)

Now where does this place $\mathcal{O}((\log n)^{\log n})$ in terms of complexity? We know that $\forall c \in \mathbb{R}: \lim_{n \to \infty} \frac{c}{\log \log n} = 0$, which means that $n^c \in \mathcal{o}((\log n)^{\log n}) = \mathcal{o}(n^{\log \log n})$; the small $\mathcal{o}$ is intended here, it means that $n^c$ grows strictly slower than $n^{\log \log n}$. [A small remark about that at the end of all this; if this is not relevant to your needs or confuses you, you can - apart from those in the remark at the end itself - replace every $\mathcal{o}$ with $\mathcal{O}$, all statements will still be true.]

On the other hand, we have for any constant base $b > 1$:

\begin{align}
n^{\log \log n} &\leq b^n &\iff \\
(\log \log n) * (\log n) &\leq n * \log b
\end{align}

This tells us that instead of $n^{\log \log n}$ and $b^n$, we can equivalently compare $(\log \log n) * (\log n)$ and $n$ by just ignoring the constant (!) factor $\log b$. Using the limit rules for asymptotic notation as well as l'Hôpital's rule, we get

\begin{align}
\lim_{n \to \infty} \frac{(\log \log n) * (\log n)}{n} &\leq \lim_{n \to \infty} \frac{(\log n) * (\log n)}{n} \\
&\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2*\log n}{n} \\
&\overset{\text{l'Hôpital}}{=} \lim_{n \to \infty} \frac{2}{n} = 0
\end{align}

Therefore we know $(\log n)^{\log n} = n^{\log \log n} \in \mathcal{o}(b^n)$ for any base $b>1$ of the exponential, meaning it grows strictly slower than any exponential function with constant base that we would be interested in. (What I mean by this is that in the analysis of the complexity of algorithms, we don't care about exponentials with negative bases because those aren't even real functions, much less functions over the naturals, or exponentials with bases between $0$ and $1$ because those all converge to $0$.)

In summary, we now know that in terms of complexity:

\begin{align}
\mathcal{O}(n^c) \subsetneq \mathcal{O}((\log n)^{\log n}) = \mathcal{O}(n^{\log \log n}) \subsetneq \mathcal{O}(b^n)
\end{align}

for any constants $c > 0$ and $b > 1$. What you have is a function strictly between polynomial and exponential growth.

Now the remark about Big-Oh and small-oh: $\mathcal{o}$ is a stronger statement than $\mathcal{O}$, because if $f(n) \in \mathcal{o}(g(n))$ then we know $g(n)$ grows strictly (meaning by a non-constant factor) faster than $f(n)$, but if $f(n) \in \mathcal{O}(g(n))$ we only know that $g(n)$ grows at least as fast as $f(n)$, so there may only be a constant factor. For example, $n \in \mathcal{o}(n \log n)$ and $n \in \mathcal{O}(n)$, but $n \not \in \mathcal{o}(n)$.


Relation between "undecidability of arithmetic" and "godel's incompleteness theorem"?

Yes, if we know that $Th(\mathcal{N})$ is undecidable then we know that it is not computably axiomatizable, and in particular we know that no computably axiomatizable theory consisting only of true sentences of arithmetic is complete.

Here I'm adopting a Platonist view with regards to $\mathcal{N}$: I assume that "the" set of natural numbers exists, and "true" means "true in that structure.

However, there are a couple points here:

How do we know that $Th(\mathcal{N})$ is undecidable?
What about strengthenings of Godel's theorem, like "No consistent computably axiomatizable theory of arithmetic extending PA (or even Q) is complete"? (This is an extension due to Rosser of the theorem as originally proved by Godel, but is basically just one clever idea on top of the usual proof.)

Ultimately, (1) really already uses the key idea/argument of Godel's theorem, while (2) points out the limitations of measuring the complexity of a single structure.

So this shouldn't be construed as trivializing Godel's theorem in any way; in particular, I object to the word "simply" in the last line.


Let's assume for simplicity that $f(n),g(n)$ both take positive integer values. Then $f(n) = O(g(n))$ iff there exists $C>0$ such that $f(n) \leq Cg(n)$ for all $n$. This implies that for any $h\colon \mathbb{N} \to \mathbb{N}$, $f(h(n)) \leq Cg(h(n))$ holds for all $n$, and so $f(h(n)) = O(g(h(n)))$.
In the general case, a quick perusal of the definitions shows that if $f(n) = O(g(n))$ and $\lim_{n\to\infty} h(n) = \infty$ then $f(h(n)) = O(g(h(n)))$. Indeed, $f(n) = O(g(n))$ means that there exist $N,C>0$ such that $f(n) \leq Cg(n)$ for all $n \geq N$. Now suppose that $\lim_{n\to\infty} h(n) = \infty$. In particular, there exists $M>0$ such that $h(n) \geq N$ whenever $n \geq M$. Hence $f(h(n)) \leq Cg(h(n))$ for all $n \geq M$.


Algorthm: Given a set of points, width around line, find line to capture maximum points

If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.

Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns.  Suppose we are given a list of points $(x_i,y_i)$.  The vertical distance from $(x_i,v_i)$ to the line $y=ax+b$ is

$$|ax_i+b-y_i|.$$

Suppose we want this distance to be at most $d$, where $d$ is given.  In other words, we want

$$|ax_i+b-y_i| \le d.$$

This is equivalent to

$$y_i-d \le ax_i+b \le y_i+d,$$

which gives two linear inequalities.  (Recall that $x_i,y_i,d$ are known, and $a,b$ are unknown.)  Given $k$ points, you get $2k$ linear inequalities.  Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.

You can even find the minimal value of $d$ such that such a line exists.  Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.


Proving whether $\bf{K}$(Happy $\lor$Sad) $\implies$ $\neg \bf{K}($Happy) is satisfiable, valid or unsatisfiable

The formula is either satisfiable or unsatisfiable. Only when it is satisfiable, it may also be valid.

To rule out that the implication is valid, show that its negation is satisfiable, that is, construct a model that satisfies the LHS but not the RHS. (Hint: a model with just one possible world suffices.)

Next, rule out that the implication is unsatisfiable by providing a model that satisfies the RHS. (Hint: again, a model with just one possible world will do.)

After these two steps, you're left with the answer.


Computing FOLLOW sets of left recursive grammar

The cited algorithm for FIRST and FOLLOW  is a least fixed-point algorithm; recursive inclusion of the same set is a no-op.
That's clearly stated in the Dragon Book's description of this algorithm, which involves repeatedly evaluating  the equations until no additional elements are added to any set during an iteration.
The algorithm works without the necessity to remove left recursion (and recursive equations in the FOLLOW set are possible without left recursion in the grammar). Left recursion elimination is not isomorphic, by the way; it's not a reversible procedure and the original grammar can not be recovered.


There has been a lot of work on formalizing mathematics, and in all of this work one needs to express definitions, theorems and proofs within the logic that one is using for formalization.

This is always quite involved.

To describe the statement that 3SAT is NP-complete, we will need a version of first-order logic with a term language that will allow us to express notions of languages, time complexity, Turing machines, polynomial-time reducibility, propositional logic and conjunctive normal forms.

Once we have an appropriate term language, we will need to describe 3SAT and NP-completeness in it. This requires us to be able to express the definitions of these notions, and this in turn involves the definition of first-order predicates that correspond to these notions and the notions that were used to define them.

Let us take a brief look at a part of this construction - this should convince you that this is indeed fairly involved. A language $L$ is NP-complete if

$L \in \mathrm{NP}$
For every $L' \in \mathrm{NP}$ we have that $L'$ polynomial-time reduces to $L$

We define a predicate $NPC(x)$ which holds if the following conjunction holds for $x$

$x$ is a language in $\mathrm{NP}$
for every $y$, if $y$ is a language in $\mathrm{NP}$, then $y$ polynomial-time reduces to $x$

We therefore need a predicate $NP(x)$ that captures that $x$ is a language in $\mathrm{NP}$, and we need a predicate $PTR(x,y)$ that captures that $y$ polynomial-time reduces to $x$. If we have these, then we can define

$$ NPC(x) = NP(x) \wedge \forall y. NP(y) \Rightarrow PTR(x,y) $$

The definition $NP(x)$ must capture the following

$x$ is a language.
There exists a nondeterministic Turing machine $M$ with polynomial-time complexity such that for all $w$, $M$ will accept $w$ if and only if $w$ is an element of $x$.

And this in turn requires us to define predicates $L(x)$, which must describe that $x$ is a language, $TM(y)$ which must describe that $y$ is a nondeterministic Turing machine, $ACC(m,w)$ which must describe that $m$ is a Turing machine that accepts string $w$, $TC(x,c)$ which describes that $x$ is a Turing machine within $c$ steps and $POL(c,p,n)$ which describes that $c$ is bounded by the polynomial $p(n)$.

Once we have defined these, we may have needed to introduce and define further predicates. And once this has been done, we need to define $PTR(x,y)$. Here, we can make use of some of the predicates that we already have, but we also need to introduce some new ones as well.

I hope that this outlines that this process of formalization is a involved and not entirely trivial task, and I hope this also explains why I do not present the entire construction of the first-order formula here.


Multiple matching in Maximum Flow problem?

Your approach works.  The situation you're worried about can't happen.  It appears you haven't quite fully grasped how the Ford-Fulkerson algorithms yet, so focus on getting more familiar with it.  It always finds the max-flow, and the max-flow always solves your problem.

The key misunderstanding is where you wrote:

  Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could

This is false.  That actually can't happen.  Work through the proof of correctness for the Ford-Fulkerson algorithm to understand why not: if there's a larger flow, then there will always be an augmenting path you can find to increase the size of the flow.

This was presumably an exercise to help you get acquainted with network flow algorithms, and it worked: it uncovered a gap in your understanding.  This is great -- it means you have something yet to learn about how the algorithms work.  What a great opportunity!  Now you get to spend some time communing with a textbook learning this lovely subject.  Have fun!


What kind of formal semantics can describe HTML and CSS?

I think the paper "Automated Reasoning for Web Page Layout" might be interesting to you. This paper defines CSS semantics in order to verify the layout formally. Look at section 3 of the paper for details. This would be one of the ways to express the CSS semantics, although this is a bit different from other semantics for programming languages.


Practical applications of the palindromic substring problem?

Lots of string-related algorithms have applications in the field of bioinformatics. Motivations for finding palindromic substrings in bioinformatics include

Finding secondary structures in RNA folding 1
Predicting DNA breakage during gene conversion 2
Finding/analyzing clustered regularly interspaced short palindromic repeats (CRISPRs) 3

These three motivations are presented in an article here and there are most likely many more.


Reduction of SUBSET-SUM to SET-PARTITION

What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X.

The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of whose elements was 't'. If we include the extra element (s-2t) in this subset Y, the sum of its elements would now become ( t + s - 2*t ) = (s-t). This is also the sum of the elements which are remaining in the set (X - Y). Hence, X' can be divided into two subsets each of whose sum is (s-t).


How to prove $\{a^nb^na^n \mid n\geq1\}$ is not regular using pumping Lemma

Let's recall the Pumping Lemma statement:

For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:

$ |y| \geq 1 $
$ |xy| \leq p $
$ xy^iz \in L, \: \forall i \geq 0 $

So yes, $ p $ is an arbitrary value and a fixed costant, called "pumping length". The proof for your language may be the following:
Let's assume that $ L $ is a regular language, so for all strings $ w \in L $ it must satisfy conditions of PL.
Now choose a string $ w $ that is in $ L $, let choose $ w = a^pb^pa^p $ and we can split $ w $ in $ xyz $, so let's say that:

$ x = a^k $
$ y = a^h $
$ z = a^{p-h-k}b^pa^p $

with $ h \geq 1 $ and $ h + k \leq p $.
Now note that the first two conditions of the PL are satisfied, but for the third, if we take $ i = 0 $ then $ w = xy^0z = a^ka^{p-h-k}b^pa^p = a^{p-h}b^pa^p $ and this string clearly doesn't belongs to $ L $ and this contraddict the initial assumption of $ L $ regular, so this meanings that $ L $ isn't a regular language because it doesn't satisfy the PL.


A stochastic policy can perfectly represent a deterministic policy by assigning probability 1 to a unique action.

Depending on how you are adjusting the policy it might take time to converge into a deterministic one, however it can get there in the limit.


How to prove an polynomial run time is faster than exponential using definition of big O

In order to prove that $f(n) = o(g(n))$ (and so $f(n) = O(g(n))$) for two positive functions $f(n),g(n)$, it is enough to prove that
$$
\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0.
$$
In your case, you can use L'Hôpital's rule, together with induction on $k$. We will show that for all integer $k \geq 0$ and all $c > 1$,
$$
\lim_{n\to\infty} \frac{n^k}{c^n} = 0.
$$
This is clear for $k = 0$. Given that it holds for $k-1$, it holds for $k$ since
$$
\lim_{n\to\infty} \frac{n^k}{c^n} =
\lim_{n\to\infty} \frac{k}{\ln c} \frac{n^{k-1}}{c^n} = 0,
$$
by the induction hypothesis.

If $k$ is not integral, the result still holds, since $n^k \leq n^{\lceil k \rceil}$.


Reduction from set cover problem to vertex cover problem

Edit: Wherever it says "vertex cover", read "dominating set".

Suppose that the sets are $S_1,\ldots,S_n$ and the elements are $x_1,\ldots,x_m$. For each set $S_i$ there will correspond a vertex $S_i$. For each element $x_j$ there will correspond $n$ vertices $x_j^{(1)},\ldots,x_j^{(n)}$. There is also an additional vertex $t$. Finally, assume wlog that the optimal solution for set cover is not $S_1,\ldots,S_n$ (this can be checked in polynomial time).

The instance of vertex cover is as follows. The vertex $t$ is connected to all of $S_1,\ldots,S_n$. Whenever $x_j \in S_i$, the vertex $S_i$ is connected to all of $x_j^{(1)},\ldots,x_j^{(n)}$. If there's a set cover of size $M$, then there is a vertex cover of size $M+1$ (we need to take the extra vertex $t$ so that all set vertices are covered). I believe that the converse should hold as well.

Try to work it out yourself, and if it doesn't work out, try to fix it and let us all know how.


When does a type generalise another type?

A pretty easy way to see if $t$ generalizes $u$ if $u$ matches $t$:

replace all variables in $u$ by (fresh) constants, written $u_c$, and check if $u_c$ unifies with $t$.

If so, then there is a substitution $\sigma$ such that $t\sigma\equiv u$ which means by definition that $t$ is more general than $u$.

As mentioned in the comments, if $\mathrm{mgu}(t,u)$ succeeds and returns a substitution $\tau$, then $u$ matches $t$ iff $u\tau\equiv u$ up to variable renaming.

Note: Pattern matching is usually best implemented independently from unification, as it is simpler in general. In particular it isn't necessary to actually replace variables with constants in $u$. Beware of non-linearities in $t$ though: $\alpha\rightarrow \alpha$ does not match $\mathrm{int}\rightarrow\mathrm{bool}$!


Set cover problem and the existence of such cover

There are two approaches for this:

The "hands on" way: first, find the minimal $k$ for which there is a set cover, by repeatedly calling an oracle for the decision problem (you can even do a binary search, but it isn't necessary).
Once you have the minimal $k$, choose a set $s_1\in S$, and check if there is a set cover of size $k$ in $S\setminus\{s_1\}$. If there is, you don't need $s_1$, so throw it away. If there isn't, remove $s_1$ from $U$, and repeat the process with $k-1$, until you have the set cover, which will be minimal.

The more theoretical approach is as follows. Since SET-COVER is NP-complete, there is a reduction from it to SAT, and a reduction from SAT to SET-COVER. If you examine the standard reductions (i.e. the Cook-Levin theorem, and a textbook reduction for $SAT\le_p SET-COVER$), you will see that both reductions are Levin reductions, which means that not only they are reductions, but they also preserve witnesses. That is, given a solution to the output of the reduction, you can generate from it a solution to the input.

Now you can proceed as follows. Given an instance for SET-COVER, find the minimal $k$ as before, and then reduce the problem with this $k$ to SAT. Now, if you have an oracle for the decision problem, you can reduce SAT to the SET-COVER, so you can also solve SAT using this oracle. For SAT we know how to find a solution using an oracle (just try bit-by-bit), so you can find a witness, and from this generate a witness for SET-COVER.

The latter works with any NP-complete problem.


Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G')

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately.
How does the $\epsilon$-removal work? Suppose that we want to remove the production $A \to \epsilon$. How can this production be used in a derivation? Whenever $A$ appears on the right-hand side of a production, we can remove it by applying $A\to\epsilon$. Hence, in order to get rid of the production $A\to\epsilon$, we simply replace each production $X \to \alpha$ by all possible productions obtained by removing occurrences of $A$ in $\alpha$. (This may result in productions of the form $X \to \epsilon$, which we need to handle separately.)
In your case, this means that we need to augment the production $A \to 0A1$ with the production $A \to 01$ obtained by erasing $A$ on the right-hand side.
What is a good way of finding such bugs? You describe three grammars: the original one, the one obtained after removing $\epsilon$ productions, and the final one obtained by removing redundant symbols. The first one generates $010$, the last one doesn't. The first step is to check which of the two transformations introduced the mistake, and you can do that by checking whether the second grammar generates $010$.
It turns out that the second grammar doesn't generate $010$. In order to understand what went wrong, you can take a derivation of $010$ in the first grammar, and see why it cannot be reproduced in the second grammar. One such derivation is $S \to AB \to 0A1B \to 0A10 \to 010$. In the second grammar, all but the last steps are still available, so the problem lies with the production $A \to \epsilon$, which the second grammar isn't able to simulate.


Facts about internal and external path lengths of binary tree

I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m>1$, if the current (ordered) contents of the tree at the previous step are $x_1<\ldots<x_{m-1}$, we choose an interval uniformly at random among the $m$ intervals
$$(-\infty,x_1),(x_1,x_2),\ldots,(x_{m-2},x_{m-1}),(x_{m-1},\infty),$$
choose an arbitrary element from the interval, and insert it to the binary tree. A random binary search tree of size $n$ is obtained by stopping this process at step $n$, and erasing the values at the vertices.

You can show that the arbitrary choices do not affect the distribution. Also, the relative order of the elements of the tree at step $n$ (in order of insertion) is a random permutation on $n$ elements.

You haven't explained what you mean by $S_n$ and $U_n$ exactly, so I assume you are using the following definitions:

Let $T_n$ be a random binary search tree of size $n$ before erasing the values. Choose one of the $n$ elements at random, and run binary search on $T_n$ and this element. The average number of comparisons in this process is $S_n$.
Let $T_n$  be a random binary search tree of size $n$ before erasing the values, and let $x$ be the random element inserted by the process at the following step. Run binary search on $T_n$ and $x$. The average number of comparisons in this process is $U_n$.

First fact

Given these definitions, the first fact is easy to prove. Suppose that the element we search for was inserted at step $i$. Note that the distribution of $i$ is uniform over $\{1,\ldots,n\}$. Inserting $i$ at step $i$ requires $U_i$ comparisons in expectation. It takes us the same number of steps to reach this element at the current experiment, and one more comparison to verify that we have indeed found the element. The formula follows.

Second fact

Here we need a non-trivial argument, outlined in the Wikipedia article. Let the sorted elements in the tree be $x_1<\cdots<x_n$. Suppose that the element we look for is $x_i$. The search goes through an element $x_j$ if $x_j$ is an ancestor of $x_i$. Thus, given $i$, the average number of comparisons is $$\sum_{j=1}^n \Pr[\text{$x_j$ is an ancestor of $x_i$}].$$ Now $x_j$ is an ancestor of $x_i$ if among all elements in $\{x_i,\ldots,x_j\}$ (or $\{x_j,\ldots,x_i\}$), $x_j$ was the first inserted. Since the true order of insertion is a random permutation of $x_1,\ldots,x_n$, we conclude that $$\Pr[\text{$x_j$ is an ancestor of $x_i$}] = \frac{1}{|i-j|+1}.$$ Choosing a random $i$, this shows that
$$
\begin{align*}
S_n &= \frac{1}{n} \sum_{i=1}^n \sum_{j=1}^n \frac{1}{|i-j|+1} \\ &=
\frac{1}{n} \sum_{i=1}^n \frac{1}{|i-i|+1} + \frac{2}{n}\sum_{i=1}^n\sum_{j=1}^{i-1} \frac{1}{i-j+1} \\ &=
1 + \frac{2}{n}\sum_{i=1}^n \sum_{j=2}^i \frac{1}{j} \\ &=
1 + \frac{2}{n}\sum_{i=1}^n (H_i - 1) \\ &=
\frac{2}{n} \sum_{i=1}^n H_i - 1 \\ &=
\frac{2(n+1)}{n} (H_{n+1} - 1) - 1.
\end{align*}
$$
Here $H_i$ is the $i$th harmonic number, and we used the identity $\sum_{i=1}^n H_i = (n+1)(H_{n+1}-1)$. It is well-known that $H_i = \ln i + \gamma + O(1/i)$ and that $\ln (n+1) = \ln n + O(1/n)$, and so
$$
\begin{align*}
S_n &= 2\left(1+\frac{1}{n}\right) (\ln n + \gamma - 1 + O(1/n)) - 1 \\ &=
2\ln n + 2\gamma - 3 + \frac{2\ln n}{n} + O\left(\frac{1}{n}\right).
\end{align*}
$$

Third fact

The upper bound is given by a path, in which case $I_n = 0 + 1 + \cdots + (n-1) = n(n-1)/2$. For the lower bound, it is easier to consider first the special case $n = 2^m-1$. In that case, the lower bound is given by a balanced binary tree. Such a tree has $2^k$ nodes at depth $k$, and so
$$
I_n = \sum_{d=0}^{m-1} 2^k k = 2^m (m-2) + 2 = (n+1)\log_2 \tfrac{n+1}{4} + 2.
$$
More generally, if $n = 2^m-1+x$ for $x < 2^m$, it is best to put the $x$ extra nodes at depth $m$, and so
$$
\begin{align*}
I_n &= 2^m(m-2) + 2 + mx \\ &= (m-2)(2^m+x) + 2(x+1) \\ &= (m-2)n + m-2 + 2(x+1).
\end{align*}
$$
Notice that $m \leq \log_2 (n+1) < m+1$, that is, $m = \lfloor \log_2 (n+1) \rfloor$. Therefore
$$
I_n = n\lfloor \log_2 (n+1) \rfloor + O(n) = n \log_2 n + O(n).
$$
To get an actual lower bound, notice that
$$
I_n \geq (m-2)n + m > n \log_2 \frac{n+1}{4} \geq n\log_2 \frac{n}{4}.
$$


The sum of all integers less than n with a zero

Here are some hints. First, as András suggests, it is easier to sum instead all integers without a zero, and then use the well-known formula $1+\cdots+n = n(n+1)/2$.

Let $S_n$ be the sum of zero-less numbers up to and excluding $n$, and let $T_k$ be the sum of zero-less numbers of width exactly $k$. We start by calculating $S_{10^k} = T_1 + \cdots + T_k$. We have
$$ \begin{align*}
T_1 &= 1 + \cdots + 9 = 45, \\
T_2 &= 11 + \cdots + 99 = (1 + \cdots + 9 + 10 + \cdots + 90)\cdot 9 = 45 \cdot 11 \cdot 9, \\
T_3 &= 111 + \cdots + 999 = (1 + \cdots + 9 + 10 + \cdots + 90 + 100 + \cdots + 900)\cdot 81 \\ &= 45 \cdot 111 \cdot 81.
\end{align*} $$
In general we get the formula
$$ T_k = 45 \cdot (1+10+\cdots+10^{k-1}) \cdot 9^{k-1} = 5 \cdot (10^k-1) \cdot 9^{k-1}, $$
from which it is easy to compute $S_{10^k}$:
$$ S_{10^k} = \frac{5}{9} \sum_{\ell=1}^k 90^k - \frac{5}{9} \sum_{\ell=1}^k 9^k = 50 \frac{90^k-1}{89} - 5 \frac{9^k-1}{8}. $$
For the general case, let's take as an example $n = 1234$. Zero-less numbers less than $1234$ come in the following forms:

Numbers less than $1000$: there are $1 \cdot S_{1000}$ of these.
Numbers of the form $1XYZ$ where $X<2$: there are $1 \cdot S_{100}$ of these.
Numbers of the form $12YZ$ where $Y<3$: there are $2 \cdot S_{10}$ of these.
Numbers of the form $123Z$ where $Z<4$: there are $3 \cdot 1$ of these.

The general case is similar. Suppose $n = d_k \cdots d_0$, where none of the digits is zero. Then
$$ S_n = d_k S_{10^k} + (d_{k-1}-1) S_{10^{k-1}} + \cdots + (d_1-1) S_{10} + (d_0-1). $$
If one of the digits is zero, say $n = 1230456$, then we can replace $n$ with $1230000$, and use the same recipe as before, stopping at the first zero digit.


Finding the regular expression equivalent for the given finite automaton

Your DFA accepts the language of all words over $\{a,b\}$ in which the number of $b$s is of the form $3n+1$ (i.e., it is equivalent to 1 modulo 3). More generally, upon reading a word $w$, the DFA will be in state $q_1$ if it read a number of $b$s which is a multiple of 3; in state $q_3$ if it read a number of $b$s which is equivalent to 1 modulo 3; and in state $q_2$ if it read a number of $b$s which is equivalent to 2 modulo 3.

Using this description, it is easy to come up with a regular expression equivalent to your DFA. Rather than do that, let me give regular expressions for the language $L_{even}$ of words over $\{a,b\}$ containing an even number of $a$s, and for the language $L_{odd}$ of words over $\{a,b\}$ containing an odd number of $a$s:

$L_{even}$: $b^*(ab^*ab^*)^*$.
$L_{odd}$: $b^*ab^*(ab^*ab^*)^*$.

These examples should enable you to solve your specific problem.


Complexity of simplifying two-variable algebraic expression

Minimizing the number of characters is a tough one.

The field of symbolic computation might be relevant, but I don't know of any algorithms that find a simplified form with the fewest characters.

Here's one approach you can use, that won't be optimal.  Express the expression as a polynomial over variables $x,y$.  Then, factor the polynomial.  Computer algebra systems will include algorithms to do that for you.  For the size problems you are talking about, this should be very efficient.

This won't necessarily find the optimal expression.  For instance, $x^2 + y^2 + 2xy + 1$ is irreducible (can't be factored), but there is a shorter equivalent expression, namely $(x+y)^2 + 1$.  However, in many cases it will find a way to simplify the expression to some extent.

Another approach, which also isn't optimal, is to use a template-based method.  Suppose you have a "template" for what you expect the simplified expression might look like: e.g., you are interested in expressions of the form

$$T(x,y) = \sum_{j,k} a_{j,k} (b_{j,k} x + c_{j,k} y)^k + \sum_{j,k} d_{j,k} x^j y^k.$$

Then given an expression $f(x,y)$, it is possible to determine whether there is an equivalent expression of the form above.  In particular, pick many random values $(x_i,y_i)$, evaluate the expression $f$ at each of those values, and set up one equation per value

$$f(x_i,y_i) = T(x_i,y_i).$$

Here since we can evaluate $f(x_i,y_i)$, the left-hand side of each such equation is a constant.  Expanding out the definition of $T(x_i,y_i)$, the right-hand side is an expression in the unknowns $a_{j,k},b_{j,k},c_{j,k},d_{j,k}$.  Thus, each value $(x_i,y_i) we pick gives us one equation on those unknowns.  After sufficiently many equations, it should be possible to solve that system of (nonlinear) equations for the unknowns.  (Computer algebra packages typically also include methods to solve a system of nonlinear equations for you.)  There may be many solutions, in which case you could enumerate all solutions, or consider simpler templates and find one solution per template.

This might give you multiple candidates for simplified expressions, and you can keep the one that has the fewest characters.  Again, there will be cases where it is not the optimal solution, but it might be useful for small expressions.

Finally, if you care about optimality more than efficiency, you could enumerate all expressions in order of increasing length, and test each one to see if it is equivalent to the original expression.  A simple way to test whether two expressions are equivalent are to evaluate them at some randomly selected points; this is fast, but might occasionally err on the side of failing to realize that two inequivalent expressions are inequivalent.  A more comprehensive test is to convert both expressions to polynomials, then check that their coefficients are equal.  This should give the optimal solution, but I expect it will be inefficient: the running time is exponential in the length of the solution.


Computational Complexity of Promise Monotone 1 in 3 SAT

The trivial answer is no, as promise problems cannot be (by definition) in NP, and thus cannot be NP complete. The basic complexity classes e.g. $P, NP$ refer only to decision problems.

However, if you want to relate your promise problem to the standard classes, you can say it is NP-hard in the sense that if it can be solved in polynomial time for inputs in the promise, then $P=NP$.

To see why the above holds, let us introduce some notations. Let $C$ be the set of all monotone clause 3CNF, for which all satisfying assignments are 1 in 3. We shall call this set "the promise". Now your problem is, given an input in $C$, to determine whether it lies in $L_{yes}=C\cap SAT$, or in $L_{no}=C\setminus L_{yes}=C\cap\overline{SAT}$.
Given an instance $\varphi$ to monotone clause 1 in 3 SAT, transform it to a monotone clause 3CNF $\psi$ such that $\psi\in C$, and in addition every 1 in 3 satisfying assignment for $\varphi$ also satisfies $\psi$. You can construct $\psi$ by adding clauses which negate conjunctions of pairs of literals in the same clause. Since $\psi\in C$ for every possible $\varphi$, and in addition $\varphi$ has a one in three satisfying assignment iff $\psi\in L_{yes}$, then solving the promise problem in polynomial time allows you to determine whether $\varphi$ has a one in three satisfying assignment, and thus $P=NP$.

The above basically shows that you can reduce an NP complete problem to your promise problem, but when talking about promise problems the definition of reduction should be slightly adjusted. Let us say that $f$ is a reduction from $L$ to the promise problem $L_{yes}\cup L_{no}$ if $Im(f)\subseteq L_{yes}\cup L_{no}$ and for every $x$ it holds that $x\in L\iff f(x)\in L_{yes}$. This is equivalent to saying that  $x\in L\Rightarrow f(x)\in L_{yes}$ and $x\notin L\Rightarrow f(x)\in L_{no}$ (note that not being in $L_{yes}$ does not imply being in $L_{no}$).


What is the role of Numerical Gradient Computation in Backpropagation algorithm?

The purpose is pure educational. Students that jump straight to mid- or high-level libraries like tensorflow, keras, theano, etc don't have to compute the gradients themselves. On the one hand, it saves a lot of time, but on the other hand, it is makes it very easy to abstract away the learning process.

Here's how Andrej Karpathy puts it (the lecturer of the previous cs231n classes at Stanford):

  When we offered CS231n (Deep Learning class) at Stanford, we intentionally designed the programming assignments to include explicit calculations involved in backpropagation on the lowest level. The students had to implement the forward and the backward pass of each layer in raw numpy. Inevitably, some students complained on the class message boards:

  “Why do we have to write the backward pass when frameworks in the real
  world, such as TensorFlow, compute them for you automatically?”

  ...

  The problem with Backpropagation is that it is a leaky abstraction.

  In other words, it is easy to fall into the trap of abstracting away the learning process — believing that you can simply stack arbitrary layers together and backprop will “magically make them work” on your data.

I recommend to read the whole post, it's very interesting.

So, you try to compute gradients manually. And when you do that you find that it's pretty hard to assess if the code is right: it's just a raw formula that takes a bunch of floating numbers and returns another bunch of floating numbers. And here you find the alternative numerical method that you can compare to very useful.

Of course, analytical formulas are faster and more precise and they are used in practice whenever possible. But while studying neural networks and back-propagation, it's very useful to get through manual computation at least once. Besides, it sometimes helps to find the bugs.


Is there a concept of information that distinguishes between "computed" and "non-computed" information?

The distinction between information theoretic and computational knowledge is an issue which is fairly common in cryptography.

Consider for example the one-time-pad encryption, that given a message $m\in\{0,1\}^l$, encrypts it using a secret key $k$ (chosen uniformly at random) by $m\oplus k$. Clearly, one learns no information from seeing the encryption of one message (it is a uniformly distributed string), so you could say that you have information theoretic security, which should make you very happy. However, if you insist on such a strict notion of security, it turns out you cant encrypt messages who are longer than the key, and if you want to do that, you should settle for a weaker notion, which is security against bounded resources adversaries (see semantic security).

One example which seems to fit your question well is one way permutations. A function $f:\{0,1\}^*\rightarrow \{0,1\}^*$ is called a one-way permutation if for every $n\in\mathbb{N}$, $f|_{\{0,1\}^n}$ is a permutation of $\{0,1\}^n$, and for some bounded resources adversaries, almost no knowledge of $x$ is exposed from $f(x)$. Since $f$ is a permutation, $f(x)$ completely determines $x$, but it is extremely hard to recover.

That said, I will strengthen Raphel's comment and say that there isn't a general definition for information (or what you call computational information), this is an issue which strongly depends on the context.


Applying a 1x1 convolution on an existing layer

A $1 \times 1$ convolution is a modern technique for dimensionality reduction, originally proposed in the Inception paper by Google team.

Suppose the layer outputs a $(N,H,W,F)$ tensor, where $F$ is the number of feature maps. Then the number of floating-point operations that the subsequent convolutional layer is going to compute is $O(N \cdot H \cdot W
 \cdot F)$, most importantly it's proportional to $F$. Likewise the number of parameters is also proportional to $F$ and the filter size.

The problem is that deep convolutional networks tend to increase the number filters exponentially, so $F$ can be really large, which makes training deep networks pretty expensive.

The idea is to reduce the size of the tensor via clever application of the convolution to $(N,H,W,F')$, where $F'$ is much smaller than $F$. If the network learns to compress the information of $F$ feature maps into $F'$ feature maps, the whole network will become much lighter both in terms of memory and computational complexity, yet potentially deeper. As it turns out, this trick works magically, so that it's used all over the place before expensive convolutional layers:

  One big problem with the above modules, at least in this naive form, is that even a modest number of 5x5 convolutions can be prohibitively expensive on top of a convolutional layer with a large number of filters.

  This leads to the second idea of the proposed architecture: judiciously applying dimension reductions and projections wherever the computational requirements would increase too much otherwise. This is based on the success of embeddings: even low dimensional embeddings might contain a lot of information about a relatively large image patch...1x1 convolutions are used to compute reductions before the expensive 3x3 and 5x5 convolutions. Besides being used as reductions, they also include the use of rectified linear activation which makes them dual-purpose.

The trick itself is pretty simple: apply $F'$ convolutions with $1 \times 1$ kernel size. This doesn't change spatial dimensions of the image, but only reduces the depth.

This is exactly what happened in your case: the depth was reduced from 256 to 2, which is a 128x boost for the subsequent layer.


So let me clarify a few things, you are interested in the big-O notation - this means upper bound. In other words, it is okay to count more steps than you actually do. In particular, you can modify the algorithm to

 ...
    for (j = 0; j < n; j++)
 ...

So you have two nested loops, each loop runs $n$ times, which gives you an upper bound of $O(n^2)$

Of course, you would like to have a good estimate for the upper bound. So for completion, we want to determine a lower bound. This means its okay to count less steps. So consider the modification

for (i = n/2; i < n; i++)
    for (j = 0; j < n/2; j++)
        sum++;

Here, we perform only a some of the loop-iterations. Again we have two nested loops, but this time we have $n/2$ iterations per loop, which shows that we have at least $n^2/4$ additions. In this case we denote this asymptotic lower bound by $\Omega(n^2)$. Since the lower and upper bound coincide, we can even say that $n^2$ is a tight asymptotic bound, and we write $\Theta(n^2)$.

If you want to know more, read here.


Can all decision problems reduce to undecidable?

a machine that for any input will never accept, but always loop forever

isn't a decision problem, and so it doesn't make sense to say it's undecidable.

However, given an undecidable problem $A$, there are always "more undecidable" problems $B$, i.e. those which would be undecidable even given an oracle for $A$. For example, the halting problem for Turing machines extended with an oracle for $A$.


Optimized algorithm to compare templates of two websites

Reading between the lines, here is what I propose. I assume that you are interested in the structure of websites, so the first step is to expose this structure.

Throw away all non-structure tags as well as attributes (maybe keep class) and text.
 I imagine we would be left with <div>, <table>, <ul>/<ol>¹, HTML5 structure tags and little else, depending on coding style.
 For the sake of efficiency, use a SAX-style parser for this step.
Create a tree of the remaining tags, either directly or in a second run.
 The structure of this tree should hold the information you want.
 You may want to cut everything that is nested deeper than some level;
 the overall structure of some website is likely to be clear from the first
 five to ten levels.
Compare the trees. What is useful here depends heavily on the kind of
 similarity you want and on the degree of sophistication the used websites
 display.

Equality of trees would be simplest measure but also coarse. There
 has been work on tree similarity measures, see e.g. here. Some research may unearth a measure that suits your purpose.

Finetuning the steps will require experiments and will most likely depend on the class of websites you compare.

You say you remove lists and tables because the may contain different numbers of elements. While that is true, the action is overcompensating since the occurrence of a list or table can be significant. Instead, remove all contained tags but keep the main ones. But then again, maybe the templates differ in the amount of columns in some table?


Unsplittable flow in capacitated networks

The easiest algorithm to implement will probably be to use integer linear programming, and then use an off-the-shelf ILP solver.  I would suggest starting with that and seeing if it is efficient enough, and only dive into the literature if ILP does not meet your needs.

One formulation as ILP could go something like this.  For each edge $e$ and each source $s$ you have a variable $f_{e,s}$ that indicates how much flow from source $s$ goes through edge $e$.  You'll have a constraint saying that $\sum_s f_{e,s}$ has to be at least the demand and at most the capacity, for each edge $e$.  Also, you'll have a constraint representing conservation of flow.

Finally, to encode the unsplittable flow condition, for each edge $(v,w) \in E$ and each source $s$, add a variable $x_{v,w,s}$ that is $1$ if the flow from $s$ enters $v$ and goes next to $w$, or 0 otherwise.  To ensure that no flow splits, you'll have a constraint $\sum_w x_{v,w,s} \le 1$ for each $v,s$ and a constraint $f_{(v,w),s} \le K \cdot x_{v,w,s}$, where $K$ is a huge constant.

This should be relatively easy to implement.  You can formulate some code to produce the right ILP system in an hour or two, and then use an off-the-shelf ILP solver.  Therefore, you should be able to very quickly experiment with this approach and see whether it meets your needs or not, before diving into the research literature on multi-terminal unsplittable flow problems.


Basic question on intermediate code generation

The intermediate language is a relatively normal programming language and as such you can write an optimizer for it. Optimization passes like common subexpression elimination, constant propagation, or strength reductions are fairly independent of the programming language.

As long as the intermediate language can express all concepts from the source language reasonably well, there is little loss in just optimizing the intermediate representation. For example LLVM's intermediate language is well suited for representing C-like imperative languages. It also comes with a type system, so not much information is lost when translating from C, or Ada, or Java to LLVM.

There is of course a problem if the source language contains information that can't be encoded in the intermediate language. For example you could think about just optimizing x86 assembly instead of first translating to something like LLVMs IR. However assembly lacks many high level constructs that make it easier for the compiler to optimize things. For example it lacks a type system. If your Ada code restricted the value of a variable to be less than five, the compiler could use that information to optimize some conditionals. Such information would be lost when translating to Assembly.

Because of this mismatch it is not uncommon to first do some high level optimizations in the target language and then translate to the intermediate language to leverage all the work that went into the optimization passes that are suitable for many languages. This article about Rust's Mid-Level IR provides an example of this. But this step is not strictly necessary (For example Rust didn't do this at first), you just lose some optimization opportunities if you skip it.

In the end it's probably an engineering tradeoff. You lose a few opportunities for optimization by using an intermediate language. But you save enormous amounts of developer time by reusing existing optimization passes.


representing set of non-overlaping string in formal notation

Idea: represent substrings by their resp. start and end index.

Let $w = w_1 \dots w_n \in \Sigma^*$ a string for some alphabet $\Sigma$. Denote (indexed) substrings of $w$ by pairs $(i,j)$ with $1 \leq i \leq j \leq n$. The actual sequence of symbols represented by $(i,j)$ would be $w_{i,j} = w_i \dots w_j \in \Sigma^*$.

Denote the set of all indexed substrings of $w$ by

$\qquad\displaystyle S_w = \{ (wi, j) \mid 1 \leq i \leq j \leq n \} \subseteq [1..n]^2$.

Note how $\{ w_{i,j}  \mid  (i,j) \in S_w\}$ is can have fewer elements due to duplicate substrings.

Non-overlapping substrings

Two indexed substrings $(i,j), (k,l) \in S_w$ with $i \leq k$ overlap if and only if $k \leq j$. Otherwise, we call them non-overlapping.

Sets of non-overlapping substrings

A set $A \subseteq S_w$ of substrings of $w$ is non-overlapping if and only if

$\qquad \forall\, u, c \in A.\ u$ and $v$ do not overlap¹.

The set of all non-overlapping sets of substrings

The set of all non-overlapping sets of substrings is

$\qquad \mathcal{N}_w = \{ A \subseteq S_w \mid A \text{ non-overlapping²} \}$.

If you so desire, input the formal definition of "do not overlap" here, i.e. $u = w_{i,j}$ and $v = w_{k,l}$ with $i \leq k$ and $k > j$. Or invent notation for the predicate "do overlap", e.g. $\operatorname{overlap}(u,v)$ or $\eta(u,v)$ or ...
Again, you can replace "non-overlapping" with the definition. I don't think that makes things more clear. The whole reason for defining shorthand is to express more complicated things easily and succinctly, after all.


How to prove a LTL formula correct in a specific model?

Your intuition is correct.

Consider an arbitrary path starting from $q_3$: let it be $q_3\, q\, q'\, q'' \ldots$. We need to prove it satisfies $\varphi = (X\lnot a)\rightarrow (FG \lnot a)$.

We proceed by cases on the second state $q$ in the path. It can be  one of $q_1,q_2,q_4$.

If $q=q_4$ then $X\lnot a$ is false in the path, hence $\varphi$ is true in the path.

If $q=q_1$ or $q_2$ then we must have $q'=q''=\cdots=q_2$. The whole path is of the form
$q_3\, q\, q_2\, q_2\, q_2 \ldots$. This path makes $FG\lnot a$ true, since there exists a suffix (namely, $q_2\, q_2\, q_2 \ldots$) where $G\lnot a$ is true ($a$ is false in each state of the suffix). Hence, $\varphi$ is true in the path.

You could make this even more formal by explicitly referring to the definition of validity.


Rows and columns in quantum-gate matrices read the same - why?

A counter-example to your observation is the Pauli Y gate:

$$Y = \begin{bmatrix} 0&-i\\i&0\end{bmatrix}$$

The first row is 0 then -i, but the first column is 0 then +i.

Another example is the X->Y->Z->X gate (a 120 degree rotation around the X+Y+Z axis of the bloch sphere):

$$\frac{1-i}{2} \begin{bmatrix} 1&-i\\1&i\end{bmatrix}$$

The reason the rows often look so much like the columns, particularly for self-inverse operations, is because quantum gates are unitary and the inverse of a unitary matrix is its conjugate transpose. But you can easily break the symmetry by multiplying an individual row (or column) by a phase factor, which produces a different but valid quantum operation.


Can we use Convolutional Neural Network for dataset containing numeric data?

Convolutional neural networks are just one of many models for classifing data. All models can be used for any data and they differ only in performance.

When you feed an image to the CNN (or any other model), the model does not “see” the image as you see it. It “sees” numbers that describe each pixel of an image and does all calculation using those numbers.
As was pointed in the comments; at the end, everything is effectively a number in the computer.

Your task asks you to use CNN because it will most likely perform best (in comparisson to other models) at this specific task. CNNs are very good at classifying objects that are not too similar, but have some shared features presented in a not too obvious way.

You can read about classification models here and I found a paper about detecting fraud with CNNs that might help you.


Actually "M rejects $x$" just means that $x \notin L(M)$, which is a statement about languages so Rice's theorem applies.

Use the decider for $L$ to solve the halting problem: On input $M$ and $w$, construct the machine $M_w$ that ignores its input and simulates $M$ on $w$. If the simulation halts, $M_w$ accepts. Otherwise, it doesn't.

So $M_w$ either accepts all strings (if $M$ halts on $w$) or no strings (if $M$ doesn't halt on $w$). You apply your decider to $M_w$. If $M_w$ accepts all strings, the decider will REJECT: the machine doesn't reject any short strings. If $M_w$ accepts no strings, the decider will ACCEPT: the machine rejects some short strings (in fact, all of them). We return the opposite answer, solving the halting problem.

It follows that a decider for $L$ can effectively solve the halting problem; therefore, such a decider does not exist.


Constructing an optimal solution to bin packing using a "magical function" $\phi$

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.


What is a Black Box attack against Machine Learning algorithms?

This is known as a "model extraction attack", and there's a line of research in the computer security literature on this problem.  For instance, you might look at the seminal paper by Papernot et al on the subject.  A little time on Google Scholar should rapidly turn up dozens of papers on the subject.


Can a 2-way set associative mapping have just one set?

Set index will be 0 or no set index.
Set associative mapping has set identification algorithm the same as direct  mapping which is j mod m, where j is the main memory line and m is the total set count. Here in this case, main memory has 4 main memory lines ( 0, 1, 2 and 3 with each having 4 bytes). Now set count is 1, hence 0 mod 1, 2 mod 1, 3 mod 1 and 4 mod 1 are all 0 which means all blocks will get mapped to Set 0 and within the set 0, the mapping is fully associative. The behaviour and mapping is more like fully associative mapping. hence for a set-associative mapping, a 2-way set associative mapping with 2 cache lines or a 4-way set associative mapping with 4 cache lines etc., behaves like fully associative and set index width is 0.
Generalizing, a K-way set associative mapping with K cache lines only will behave like a fully associative mapping.


Why is my regular grammar for palindromes wrong?

Your grammar is correct, in the sense that it does generate all palindromes over the alphabet $\{a, \dots, z\}$. But it's a context-free grammar and not a regular grammar. In a regular grammar, you're only allowed rules of the form $A\to\epsilon$, $A\to a$ and $A\to aB$, i.e., there is at most one non-terminal on the right and any terminals must come before it.

(Alternatively, you get the same class of languages by insisting that any terminals on the right must come after the nonterminal but you can't mix the two in a single grammar.)


In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

You can look up the small graphs that ISGCI uses to define classes. Specifically, $S_3$ is the following "sun" graph:

ISGCI defines sun graphs as

  a chordal graph on $2n$ nodes ($n\geq3$) whose vertex set can be partitioned into $W = \{w_1,\dots,w_n\}$ and $U = \{u_1, \dots,u_n\}$ such that $W$ is independent and $u_i$ is adjacent to $w_j$ iff $i=j$ or $i=j+1\pmod{n}$.

Implicitly, the subgraph induced by $U$ can be anything. Wolfram Mathworld also talks about "complete sun graphs", which is the special case where $U$ is a clique.


First let's look at the special condition.
For each edge $p_i p_{i+1}$ in the path $P$ the has to exists an additional path that connects $p_i$ with $p_{i+1}$. This criterion is equivalent to: no edge of the path is a bridge edge.

This means that we can determine already before the actual shortest path search, which edges we are allowed to use, and which edges we are not allowed to use.

Therefore you can construct an efficient algorithms as follows:

compute all bridge edges (e.g. with Tarjan's bridge-finding algorithm)
remove all bridge edges from the graph
execute any shortest path algorithm, e.g. BFS, on the remaining graph

Some additional notes, since you wrote that you want to use multiple algorithms. However these approaches will perform a lot worse than the one described above.

of course you can also determine if an edge $p_i p_{i+1}$ is a bridge edge in other ways. E.g. remove the edge from the graph, and check if you can find a path from $p_i$ to $p_{i+1}$ with a DFS (backtracking), or with another BFS.
Also you can use Backtracking itself to find the shortest path at the end.


Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular?

$(n-m)\bmod 5$ can only be $0,1,2,3,4$. So intuitively, the language in the question is a regular language. We can show that conclusion rigorously in the following two ways.
Regular expression
The simplest way is to verify that the language is described by the following regular expression.
$$(00000)^*(\epsilon+01+0011+000111+00001111)(11111)^*.$$
Intuitively, the language consists of words each of which is zero or more five 0s, followed by some number of 0s, followed by the same number of 1s, followed by zero of more five 1s.

Minimal DFA
Here are the states of the minimal DFA for this language.

$Z_{0}$, which represents words each of which is zero or more five 0s.
$Z_{1}$, which represents words each of which is zero or more five 0s, followed by 0.
$Z_{2}$, which represents words each of which is zero or more five 0s, followed by 00.
$Z_{3}$, which represents words each of which is zero or more five 0s, followed by 000.
$Z_{4}$, which represents words each of which is zero or more five 0s, followed by 0000.
$S_{0}$, which represents words each of which is zero or more five 0s, followed by nothing or 01 or 0011 or 000111 or 00001111, followed by zero or more five 1s, ending with 1.
$S_{1}$, which represents words each of which is zero or more five 0s, followed by 0 or 001, or 00011 or 0000111 or 1111, followed by zero or more five 1s, ending with 1.
$S_{2}$, which represents words each of which is zero or more five 0s, followed by 00 or 0001 or 000011 or 111 or 01111, followed by zero or more five 1s, ending with 1.
$S_{3}$, which represents words each of which is zero or more five 0s, followed by 000 or 00001 or 11 or 0111 or 0001111, followed by zero or more five 1s, ending with 1.
$S_{4}$, which represents words each of which is zero or more five 0s, followed by 0000 or 1 or 011 or 00111 or 0001111, followed by zero or more five 1s, ending with 1.
$R$, which represents all other words, which are words that are not of the form $0^*1^*$.

In other words, besides the "rejecting" state $R$ that behaves as a black hole, we have, for $i=0,1,2,3,4$,

a state $Z_i$ which represents words of the form $0^*$ whose number of 0s is the same as $i$ modulo 5.
a state $S_i$ which represents words of the form $0^*1^*1$ whose number of 0s is the same as $i$ plus its number of 1s modulo 5.

It should be not be difficult for you to figure out the initial state, the accepting states and the transitions between the states.

Is it reasonable to get a DFA with at least 30 states for this language?

It is totally fine if you can construct a DFA with 30 states or 2019 states for this language. That will show the language is regular.
On the other hand, it is sometimes interesting or helpful or challenging to find the DFA with the minimal number of states. For this language, 11 states is the minimum.

Here are two related exercises.
Exercise 1. Show $\left \{ 0^m1^n \mid (n-m) \bmod 5=2 \right \}$ is a regular language. How many states are there in the minimal DFA for it?

Exercise 2. Show $\left \{ 0^k1^m2^n \mid (k+m-n) \bmod 2=0 \right \}$ is a regular language. How many states are there in the minimal DFA for it?


Are there some good algorithm to select m by three matrices which satisfies certain conditions?

A simple way to deal with this problem—which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements—is to treat it as a constraint satisfaction / combinatorial search problem and apply backtracking. Each matrix entry branches the search tree 9 ways, but many of these subtrees can be trivially eliminated because they immediately violate one of the conditions.

Take the $m = 5$ case that you got stuck on as an example. For condition 1, note that already there are only $\binom{9}{3}^5 = 4,182,119,424$ matrices of size 5x3 with elements in [1..9] which have elements strictly increasing from left to right in each row. It's $\binom{9}{3}^5$ because condition 1 is equivalent to, for each row, choosing 3 distinct elements from [1..9]. You can of course iterate over such rows with

for i in 1 to 7, for j in i + 1 to 8, for k in j + 1 to 9

Moreover, conditions 2 and 4 can be checked as you are generating the rows, rather than only checking these conditions once you have the entire matrix. This should drastically prune the search tree.

Tassle adds (and provides this sample code):

  You can also prune on condition (5) by first computing all possible profiles $x(M)$ which lead to $q(M)=2$, and then trying to find all satisfying matrices with a specific profile. Out of all 490314 ways to choose 15 numbers in {1...9}, only 84 lead to $q(M)=2$. In fact, using this, even python on my quite slow machine can manage m = 5 in a reasonable time.

This sort of brute forcing is also embarrassingly parallel and requires hardly any memory, so consider dividing the space of matrices among however many CPU cores you have.


Eligibility trace and the role of gamma and lambda

At least for gamma I can answer it generally without looking in the book:

Gamma is commonly used as the discount factor. That is a number in (0, 1) which defines how much of the reward you got in step i will be also given to step (i - n). Commonly, the reward is discounted exponentially (like gamma^n)


How to create disjoint sets out of an adjacency list

In the disjoint-set approach you start from a collection of single vertices and repeatedly join the incident vertices of the edges. This will give you the connected components in $O(n+m\times(\text{find}+\text{union}))$.

The BFS approach takes only $O(n+m)$ and thus is faster, since the disjoint set operations take more than O(1).


Is a stack machine with a forward read iterator Turing complete?

Your model is Turing-complete, unfortunately.

You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$.

Enqueue(val) is just Push(val).

For Dequeue():

ReadBegin().
Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $x$ for every $d$, and push $x$ or pop $y$ for anything else. Always prefer pop to push. Finally there won't be any $y$ in the stack and the result will be the number of $x$ on the top of the stack.
ReadBegin().
While pTop is a $x$:

Repeat ReadNext() until it returned something other than $x$ and $d$.
Pop().

Push a $d$.
The last result of ReadNext() is returned as the result of Dequeue.

The proof is straightforward. Check the revision history for a more complicated version firstly reducing it to a two-way version.


Number of distinct substrings in a string

Instead of a formal proof, I want to give some intuition behind the formula. The suffix array contains all the suffixes of the string $w$. A substring is nothing else than a prefix of a suffix. So if you count $\sum_i |S[i]|$, you will get all the substrings, but of course you overcount the number of different substrings.

Let's have a closer look. Assume the $S[i-1]=xyz$ and $S[i]=xyxyz$. By the above counting method the entry $S[i-1]$ counted the substrings $x,xy$ and $xyz$ and the entry $S[i]$ counted $x,xy,xyx,xyxy,xyxyz$. You will notice that since the prefixes of length 2 of both entries are the same we have double counted $x,xy$. But the length of the longest common prefix is stored in $L[i]$ so we subtract it to compensate for the overcounting.


find all paths from source to destinations and then calculate the path with minimum cost

One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist[i][j]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\{i, j\}$ with cost $c$ we update as following:(for all values of k)
$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$
$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$
The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.


Karnaugh map with don't care: increasing the number of groups instead of simplifying

Your answer is correct. It is also more reduced. The reason your book and the solver give you a bigger equation is because they use a greedy algorithm that attempts to match bigger groups (groups with less variable in them). This will have an optimal behavior if the map has no "don't cares" [reference needed].

To have optimal behavior with "don't care", you have to consider that an X can be either a 1 or a 0. That means that for each X, you have two versions of you map. So, if you have $N$ "don't cares", you will have to reduce the $2^N$ versions of the map and choose the smallest reduced operation from the results.

Extra

If you have lots of those maps to reduce, i suggest you use Logic Friday or a similar equation reducer.


Linear and almost-linear perfect hashing

I think there is a constraint that the domain of the hashing function must be {0...n-1}, where n means the number of elements to hash. Only defining in this way , the reduction from 3SUM to Conv3SUM works.

The is an almost-linearity function in wiki. And it is easy to figure out a counter example for the existence of perfect linear hashing function.

Consider the following questions:

Let A = {1,2,3,4}, B={0,1,2,3}

how many triples (x,y,z) satisfy x+y=z, where x,y,z are in A and distinct！
what if x,y,z are in B

The answer of the first question is

1+1=2
1+2=3
1+3=4
2+2=4

But there are only two triples in the second question. You can find out a bijective function, satisfying that linearity property, mapping A onto B .


How do you go from $\log P = \log N$ to the next step?

Two positive real numbers are equal if and only if their logarithms are equal. This is because $\log$ is a strictly increasing function that grows without bound and is defined for all positive reals: it is, therefore, a bijection from $\mathbb{R}_{>0}$ to $\mathbb{R}$.

Clearly, if $x=y$ then $\log x=\log y$. If $x\neq y$ then suppose $x>y$ (the case $x<y$ is identical). Because $\log$ is strictly increasing, $x>y$ implies that $\log x>\log y$ so, in particular, $\log x\neq \log y$.  Therefore, $x=y$ if, and only if, $\log x=\log y$.


How to prove by contradiction that every nonempty hereditary language contains the empty string?

Let L be a nonempty hereditary language. Let x be one of the shortest strings in L. x exists because L is not empty.

Removing any character from x would produce a string not in L, since x is one of the shortest strings. Because L is hereditary, we can remove a character from x giving another string in L, unless x is the empty string. Therefore x is the empty string. Therefore L contains the empty string.

If you insist on proof by contradiction: Let L be a nonempty hereditary language not containing the empty string, and let x be one of the shortest strings in L. x is not the empty string since L doesn't contain the empty string. Therefore there is a character in x which can be removed, giving a string y in L.

But y is shorter than x, therefore x is not the shortest string in L.


How to test image segmentation algorithms?

Google "image segmentation benchmark".  You will find various data sets with ground truth, such as this one.


Using Clique decision to solve Clique optimization

You would use binary search.  Start with the lower bound being 3 and the upper bound $n$, where $n$ is the number of vertices.  Call your clique decision oracle with a $k$ value halfway between the two bounds.  If it answers "yes", move your lower bound to $k + 1$.  If it answers "no", move your upper bound down to $k - 1$.  Repeat until you have found the largest $k$ value the oracle answers "yes" to.  It should take $O(\log n)$ calls to the oracle.


Example of a false proposition when assuming Type : Type

The relevant literature is the following:

Thierry Coquand A new paradox in type theory (link). He describes his paradox in a system that is somewhat weaker than

Type : Type

But that can be easily transported to the above. The main idea is taking Reynolds proof that there are no models of system F in set theory. That proceeds by building an initial algebra of the form:

$$ A\simeq (A \rightarrow \mathrm{2}) \rightarrow \mathrm{2}$$

Where $\mathrm{2}$ is a set with 2 elements, and deriving a contradiction by a cardinality argument. Coquand shows

You can carry out this reasoning in the above type theory
There is a model of system F in that theory. This yields a contradiction.

The second article is from Antonius Hurkens, and is titled A simplification of Girard's paradox (link). The proof involves a construction of the "type of all well-founded types". I must admit that the general idea seems clear, but the details are quite devilish.

I'm afraid there is no simple, easy to understand contradiction in $\mathrm{Type} : \mathrm{Type}$. However the proof-terms obtained from the contradiction are relatively tractable: only a few lines are sufficient to define them.

Alexandre Miquel, in his thesis dissertation, showed that one could construct a model of naive set theory in these inconsistent type systems by using a pointed graph interpretation of sets. He can then simply apply Russel's paradox directly. Unfortunately the model construction takes a bit of work, and the dissertation is in French.


Decide if a string is in a language without simulating the automata accepting the languge

You ask two questions.

For your first question, about whether a TM can do this without fully simulating the DFA:

The problem statement is not well-defined.  Given a TM, you can't tell whether it "fully simulates the DFA on a string" or not.  (That's undecidable.)  There are all sorts of ways that a TM might effectively "simulate", but in an obfuscated way that makes it hard for you to realize that's what it is effectively doing.

Your language $L$ is certainly decidable.  It has the form $L=L_1 \cap L_2$ where $L_1$ and $L_2$ are both decidable, hence $L$ is decidable too.

For the second question, about whether a TM can do this using at most a constant number of steps after reading the last bit:

Sure.  That's always possible, for any decidable language.  After reading all but the last bit, the TM can decide what it will do if the last bit is 0 and what it will do if the last bit is 1 (doing as much computation as necessary to handle both cases).  Then, when it reads the last bit, it will immediately be able to produce the correct output, using only a constant number of steps.  This doesn't really have anything to do with whether the TM is or isn't simulating the DFA, though.


Think about what happens when you manage to find the first interval, say it is $[v_1,...,v_k]$ for some $k$. Then what would you be able to say about the minimal division of $v_{k+1},...,v_n?$
Think also about how you could find the first interval. Starting from an empty interval and expanding it (how?) should do the trick.


Calculating the runtime for a recursive algorithm

1) $f(n) \in O(n)$, since $k$ is a constant.

2) If $a=b=k$, then $\log_b a = \log_k k$. Your specific case of $\log_1 1$ only appears for $k=1$. And if we insert $k=1$ into the original recurrence we get $T(n) = T(n) + n + 1$, which does not make much sense as a description of a runtime. So it is sensible to simply exclude this case.


Is this variation of the traveling salesman problem NP-hard

I think if you choose all $d$'s to be exactly $1$ and choose $L$ to be exactly $n$ (number of cities), any solution must visit all cities, so the reduction will work out.


Most efficient known priority queue for inserts

Worst-case complexity
Insert: $\mathcal{O}(1)$
Find-min: $\mathcal{O}(1)$
Decrease-key: $\mathcal{O}(1)$
Delete: $\mathcal{O}(\log \log n)$
Space: $\mathcal{O}(n)$
Proof

THEOREM 1. We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$ time.

Which is established with a combination of:

LEMMA 3. Let $\tau(n, N)$ be the delete time for a priority queue for up to $n$ integers in the range $[0 , N)$ supporting insert and dec-key in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.

and:

THEOREM 6. Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $[0 , N)$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.

Reference
Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC  ’03. New York, NY, USA: ACM, 2003.


What is the difference between "backhaul" and "core" network in cellular networks?

Let's have a little bit of a glimpse from the diagram below;

What you can analyse in that diagram,is a convention point to point (PTP) and line of sight (LOS), a microwave link uses atail node and aggregation node,which allows remote base station to  access the core network through the backhaul link.

Therefore,backhaul network is a side network which communicates with the core network,i.e. it links packets to and from  the core network.

That said, cellphones also communicates with a single cell tower which constitutes a local network (subnetwork);whereby the link between the celltower and rest of the world(to the core network) begins with the backhaul link. The rest of the world is termed as autonomous network system,which is administered by global internet providers.

A high-level summary is that cellular backhaul refers to transport from remote cell towers to mobile telephone switching offices (MTSO). This backhaul is frequently provided by a third-party internet service provider via layer 2 circuits. The ISP's edge device (optical switch or router) with a customer handoff point (UNI) is located at the cell tower and the network demarcation between the ISP and the cell provider's core network (ENNI) is located at the MTSO. An EVPL (point-to-multi-point) configuration is commonly implemented with both circuits traveling from the tower to the MTSO over divergent paths to provide redundancy.

Hope this can give you some insights.


Hitting probability of random walk within given number of steps

For every point $(a,b)$ and number of steps $t \leq k$, compute inductively (i.e., using dynamic programming) the probability of reaching $(a,b) \neq (x,y)$ in $t$ steps without hitting $(x,y)$. Given this information, you can easily compute the probability of hitting $(x,y)$ in at most $k$ steps.


Well, the set $\left \{w_1**w_2**..**w_k \right \}$ contains only one single element, but is nevertheless a set. And TM can accept only languages, which are sets of words.

Why is it slightly easier? Hmm, I would say, it is easier since you can simplify the algorithm slightly. You have one counter for $k$, and then you check, whether in the string $\cdots *x*y*\cdots$, you have $\text{bin}(y)=\text{bin}(x)+1$ on every position. You do not have to care about detecting the right $k$. Other than this, the suoer-string is longer, which gives you more space. But this effect vanishes in the big-O.


Find number of triples that sum up to zero in query-intervals

Let us call the input array $A$. We build the solution in three steps:

First, for each value $v$ between $-10^6$ and $10^6$, build a list with all the indices in $i \in \{1, \dots N\}$, where $A_i = v$ and keep all these lists sorted. One way to achieve this is to iterate over $A$ and append the index of each element to its corresponding list. Let $L_v$ be the list corresponding to a value $v \in \{-10^6, \dots 10^6\}$.

In the second step, we will build a two-dimensional array $C[N][N]$, where
\begin{equation}
C[i][j] = \begin{cases}
|\{k: i+j+k = 0, k \in \{i, \dots j\}\}| &;i\leq j,\\
0 &;\text{Otherwise}.
\end{cases}
\end{equation}
We can compute $C$ by iterating over all pairs $i, j \in \{1, \dots N\}$, $j\geq i$, and for each such pair, let $u = A_i$ and $v = A_j$. Let $w = -(u + v)$. Note that $u + v + w = 0$, Using binary-search twice, find in $L_w$ the lowest index not less than $i$ and the highest index not greater than $j$. The difference of the indices of these two values plus 1 is the number of elements $w$ between $A_i$ and $A_j$, such that $A_i + A_j + w = 0$, which is exactly $C[i][j]$.

Now as a last pre-processing step, Let us compute the two-dimensional array $S$, the prefix-sums over $C$, that means:
$$
S[i][j] = C[i][j] - C[i-1][j] - C[i][j-1] + C[i-1][j-1],
$$
where we consider $C[i][j] = 0$ for $i = 0$ or $j = 0$ (since we considered 1-indexed arrays).

Now for each query $i, j$, output
$$S[j][j] - S[i-1][j] - S[j][i-1] + S[i-1][i-1],$$
where again, we consider $S[i][j] = 0$ for $i = 0$ or $j=0$.

Based on the previous definitions, try to see why this yields the answer you are looking for.

The running time is $O(N^2\log N)$ pre-processing and $O(1)$ per query. The space complexity is $O(N^2 + M)$, where $M$ is the largest value (equal to $10^6$ in your case), which is needed to keep track of the start of each list $L_i$ for each $i \in [-M, M]$.


Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(.

NP-Hardness

Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or above some $k$?

This problem is NP-Complete.

First, clearly this decision problem is in NP, as if one can provide you with such an assignment then you can compute the total score and verify that their solution works.

Next, note that this problem is essentially equivalent to finding two distinct highest-cost paths that go through the same amount of nodes, and together go through every node. Using this idea, we will solve the hamiltonian path problem.

Given two hamiltonian path instances $G_1=(V_1, E_1)$ $G_2=(V_2, E_2)$ of the same size $n$, consider the combined graph $G=(V_1\cup V_2, E_1 \cup E_2)$, and then create an instance of our seating arrangement problem where every edge is a $1$ if it occurs in our combined graph, and a $0$ otherwise. Because these graphs are undirected, the preferences will be the same in both directions.

The question "is there some way to assign seating positions to professors such that the total score obtained is greater than or equal to $\vert V_1 \vert + \vert V_2 \vert$" is NP-Complete, as it is only possible to do this if a hamiltonian path exists in both graphs.

Approximation algorithm ideas

NP-Hardness just guarantees that a problem can't always be solved exactly unless $P=NP$, however, it doesn't tell us anything about how difficult it is to approximate. Here is one idea I had, it's incomplete, but is at least something to get you started.

For simplicity, I will now consider the problem where there is a single circle of chairs, and we are trying to place professors in the same way you require. We will also restrict all preferences to be greater than or equal to 0. This can most likely be extended to your problem but I haven't got around to that yet, so I will update this problem once that is accomplished, or you can do this yourself.

With this "roundtable" problem, it turns out there is an algorithm I found that is guaranteed to find a solution that is no less than 8 times the optimal solution.

This algorithm does the following:

Place each person randomly around the table.
Consider a pair of people (any will do), and see if swapping them will increase the total score. If so, swap them.
Repeat until no swap will increase your total score.

This is guaranteed to halt in polynomial time because each swap strictly increases the total score (I think? Still a little fuzzy about this part but I'm fairly sure that is true and will formalize it in a bit).

How good does this algorithm do? Well, call $Opt$ the optimal ordering of professors, and $Val$ the ordering of professors that this algorithm gives when it is done.

Now, consider any set of edges $(a, x)$, $(x, b)$, $(c, y)$, $(y, d)$ in your graph, where $a, x, b, c, y, d$ are professors. We will denote these edges $(a,x,b)$ and $(c, y, d)$ since by definition given any arrangement of professors they are next to each other.

We know that, if $y$ and $x$ could be swapped our algorithm would have done so. Call $\mid (a, x, b)\mid$ the score of edge $(a, x)$ plus the score of edge $(x, b)$. Then, if $(a, y, b)$ and $(c, x, d)$ are in val, we know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)|$$

Because either our algorithm swapped $x$ with $y$, or there was equal score regardless of the swap, in which case we have

$$|(a, y, b)| + |(c, x, d)| = |(a, x, b)| + |(c, y, d)|$$

Note that we technically also know

$$|(a, y, b)| + |(c, x, d)| \geq |(a, x, b)| + |(c, y, d)| \geq |(c, y)|$$

Which is true because $|(a, x, b)| + |(c, y, d)|$ contains $|(c, y)|$ in it. Now we can look at the terms on both ends, and this gives us

$$|(a, y, b)| + |(c, x, d)| \geq |(c, y)|$$

Which holds for all edges $(c, y)$. Note that given any $(c, y)$, there is only one such pair of $(a, y, b)$ and $(c, x, d)$, because the positions $c$ and $y$ are fixed.

We know that the value of $Opt$ is equal to the sum of all it's edges $(v_1, v_2)$, $(v_2, v_3)$, ..., $(v_{n-1}, v_n)$, $v_n, v_1)$ (where $v_i$ is some professor), so for each of these, we get a single inequality. Consider the edge $(a, y)$. $|(a, y)|$ will only appear in an inequality if $a$, $y$, or the professor before $a$ is contained in the edge in Opt. Thus, worst case $(a, y)$ is counted 8 times, because each variable can be in at most two edges, by definition.

If we sum all of the edges on both sides, we get

$$8*Val\geq Opt$$

Thus

$$(8 \geq \frac{Opt}{Val})$$

which is a factor 8 approximation, as desired.


Use two indices: the first index allows you to map a key value to the corresponding tuples that contain that key value; the second index allows you to map a data value to the tuples that contain that data value.  Each index can be implemented as a hash table, binary tree, or any other data structure you like that provides fast lookups.

For instance, databases implement ideas like this to enable fast lookups and searches.