What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

Linearity for boolean functions means exactly linearity over a vector space.

Consider the field $\mathbb{F}_2$, i.e., the field with two elements $\{0,1\}$.  Here the "addition" is addition modulo 2, i.e., exclusive xor (xor).

A vector space $V$ over this field is basically a vector of $n$ elements of $\mathbb{F}_2$.  The "sum" of two vectors $v+w$ is obtained by taking the component-wise "sum", i.e., the xor of these two vectors.  In this way you can think of the space $\{0,1\}^n$ as a vector space over $\mathbb{F}_2$: just identify $\{0,1\}^n$ as the set of $n$-vectors over $\mathbb{F}_2$, so it becomes a $n$-dimensional vector space.

Now a boolean function $f:\{0,1\}^n\to \{0,1\}$ is considered linear iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$.  This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n.$$

Here $\oplus$ represents the xor operation.

Why is this equivalent to the usual definition over vector spaces?  Recall from linear algebra that if $f:V \to W$ from vector space $V$ to vector space $W$, then it can be represented as multiplication by a $k \times \ell$ matrix, where $k = \dim V$ and $\ell = \dim W$.  Here we have a map $f: \{0,1\}^n \to \{0,1\}$, and $\dim \{0,1\}^n = n$, so $f$ can be represented as multiplication by a $n \times 1$ matrix.  Here everything is over the field $\mathbb{F}_2$, so you have to replace the usual addition and multiplication with addition and multiplication modulo 2.  Multiplication by the matrix $[c_1 c_2 \cdots c_n]$ is equivalent to the definition above, so we obtain the equivalence.

Caveat: linear vs affine. If we have $f:V \to W$, a linear function is one that can be represented as

$$f(x) = Mx$$

where $M$ is some matrix.  An affine function is one that can be represented as

$$f(x) = Mx+c$$

where $M$ is some matrix and $c$ is some vector.  A linear function has the property that $f(x)+f(y)=f(x+y)$.  An affine function does not; but it does satisfy the property that $f(x-y+z)=f(x)-f(y)+f(z)$.

Wikipedia's definition claims to be a definition of a linear function, but it's really a definition of an affine function.  Sometimes people don't distinguish between linear vs affine (they consider both of them to be linear functions).  That can be a bit confusing, especially if you're just learning these concepts. Unfortunately, Wikipedia seems to be one of those places that has lumped both concepts under the name "affine".

In your context, a boolean function $f:\{0,1\}^n\to \{0,1\}$ is affine iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$.  This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n \oplus c_0.$$

The difference between linear vs affine is the extra constant term ($\oplus c_0$) that can appear in an affine function.  When Wikipedia provides its definition of a linear function, it is really providing a definition of an affine function.  I guess that implicitly Wikipedia is using the word "linear" to include both concepts.  Anyway, as long as you understand this little detail, all of the standard machinery of linear algebra applies.

See also https://en.wikipedia.org/wiki/Affine_transformation#Over_a_finite_field.


algorithm complexity calculation T(n) = 2T(n/2) + n*log(n)

Let's start at the beginning.

Basically, there are 3 very popular notations to express time complexity of algorithms:

$\Theta(g(n))$,
$\mathcal{O}(g(n))$ (this is the well-known Big O notation),
$\Omega(g(n))$.

The first thing that is in most cases a little bit confusing (and misused), that these notations denote sets - sets of functions. For example, the interpretation of $\Theta(g(n))$ is as follows:

$$\Theta(g(n)) = \{ f(n) \; | \; \text{There exist } n_0, c_1 \text{ and } c_2 \text{ constants so that } 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n > n_0. \}$$

So, $\Theta(g(n))$ is a set of $f(n)$ functions for that $g(n)$ can be used as both an upper and a lower bound (with the use of the given $c_1$ and $c_2$ constants). In other words, if you plot these 3 functions, $f(n)$ is going to be between $c_1 \cdot g(n)$ and $c_2 \cdot g(n)$ - at least, for all inputs larger than or equal to $n_0$. (It's worth taking a look at figures about these in Google so that you can get a better understanding of it.)

Note: because of the use of $n_0$ and all larger inputs than it, these notations are also called asymptotic notations.

The interpretation of $\mathcal{O}(g(n))$ and $\Omega(g(n))$ are very similar to the one above, but they only refer to either the upper bound or the lower bound, respectively. (Of course, the existence of only one $c$ constant is enough for these 2 definitions.)

Just in case, see the definition of $\mathcal{O}(g(n))$ below:

$$\mathcal{O}(g(n)) = \{ f(n) \; | \; \text{There exist } n_0 \text{ and } c \text{ constants so that } 0 \leq f(n) \leq c \cdot g(n) \text{ for all } n > n_0. \}$$

In other words, $g(n)$ is an upper bound for all the functions in the set $\mathcal{O}(g(n))$. For example, let's denote the time complexity of the insertion sort with $T(n) = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2}$ (you can derive this easily if you think through the algorithm). Now, here $T(n) \in \mathcal{O}(n^2)$ means that the time complexity of the algorithm is quadratic - so if the size of the input is $n$ (we have an array to be sorted consisting of  $n$ elements), the algorithm must perform the most expensive operation at most $c \cdot n^2$ times (where $c$ might be 1). Three notes here:

Typically, we don't care about the "weaker" members of the equations, like $\frac{n}{2}$ in the example above, because of the asymptotic property I mentioned earlier (that wants to say something like "for large enough inputs always the strongest members will only count").
Typically, we only consider the most expensive operations of an algorithm, i.e., in the case of sorting algorithms, the number of comparisons.
Many times, people use the notations of $T(n) \in \mathcal{O}(g(n))$ and $T(n) = \mathcal{O}(g(n))$ like they were equivalent (basically, they aren't, but it's a common thing since the use of the latter can be advantageous as well).

So now, that hopefully we are done with the basics, you can see, that if a function $f(n) \in \Theta(g(n))$, it is also true that: $f(n) \in \mathcal{O}(g(n))$ and $f(n) \in \Omega(g(n))$ (in most textbooks, this is presented as a theorem with its proof, as well). In most cases, people don't care about the lower bounds of an algorithm's time complexity - so, it shouldn't really matter whether you see $\mathcal{O}$ or $\Theta$ (this would be the answer to your second question). I think that $\Omega$ is much less frequent than the other two.

I haven't ever seen the $ld$ notation you mentioned. However, I would prefer to use $\log_2$, it will be clear for anyone. Of course, you can use the one you would like to, but make sure to put them into either $\mathcal{O}$ or $\Theta$ (I can't recall a case when only the function was indicated).

Truly hope that I managed to provide a detailed answer you find useful enough. If you have any further question, please feel free to ask.


Where can I find a study on the amount of different word frequencies in a corpus?

What you're asking directly refers to Information Retrieval. Information Retrieval directly creates models for such things as frequency of words in a corpus and so on.

In a corpus, different indicators are estimated in order to create a score. Two indicators are predominant in those models :

Inverse document frequency (idf)

This model aims at attenuating words that appear too often and considered irrelevant to judge the score of a word.

$ idf_{t} = log\frac{N}{df_{t}}$ where $N$ stands for the total of document in a collection and $df_{t}$  the number of documents in a collector that contain the term $t$

Term frequency (tf)

This is the most basic way to modelize word frequency in a corpus. It can be computed by saying that:

$tf_{t,d} = \frac{t_{occ}}{N}$ where $t_{occ}$ is the occurence of the term divided by the number of words in the document.

More information on this subject can be found here :

Scoring, term weighting and the
vector space model


Does a DFA accept an empty string if $q_0$ is the accept state?

Yes.  This is immediate from the definitions.

A DFA accepts if it's in an accepting state after it's read its input. If the input is the empty string, the DFA makes no transitions so, after reading it's input, it's still in its initial state, $q_0$.  If $q_0$ is an accepting state, the automaton accepts the empty string.

Note that you write "the accepting state" but an automaton may have multiple accepting states.


Query: Given a graph, is edge x in an optimal TSP tour?

The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that
$$
x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|).
$$
This is the natural location for your problem:

$x$ is a pair $(G,e)$, where $G$ is a graph and $e$ is an edge of $G$.
$y$ is a TSP tour.
$z$ is a TSP tour.
$f(x,y,z)$ holds if (i) $y,z$ are TSP tours of $G$; (ii) $e \in y$; and (iii) $w(y) \leq w(z)$.

More generally, $\Sigma_k^P$ is defined similarly with $k$ quantifier alternations, and $\Pi_k^P$ is defined the same but starting with a universal rather than an existential quantifier. For example, $\Sigma_1^P$ is NP and $\Pi_1^P$ is coNP. We also define $\Delta_k^P = \Sigma_k^p \cap \Pi_k^P$, generalizing the class NP∩coNP.

We define $\Sigma_k^P$-hard and $\Sigma_k^P$-complete in analog to NP-hard and NP-complete, using polynomial time reductions. The obvious question to ask in your case is whether your language is $\Sigma_2^P$-complete.


Why is bipartite perfect matching a special case of clique problem?

Let $G=(V,E)$ be the bipartite graph.  Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common).  Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$.  In particular, there's a perfect bipartite matching for $G$ if and only if there is a clique of size $|V|/2$ in $G'$.


Will a node with no incoming arc or no out coming arc affect the maximum flow?

Yes, you can. If it has, say, no outcoming edge, there can be no flow routed over this node. Otherwise the flow conservation constraint for this node ($v$)
$$\sum_{(u,v) \in E} f_{uv} - \underbrace{\sum_{(v,w) \in E} f_{vw}}_{= 0} = 0$$
is violated if you have incoming flow.


Figuring out the language of a non-linear CFG

It's no wonder that you're having trouble with this; it's nasty. So as not to spoil the suspense, $L(G)$ is

  The set of all $w\in\{a, b\}^*$ such that $w = a^{i_1}b\,a^{i_2}b\dotsm a^{i_n}b$ with $i_k\ge 1$ for all $1\le k\le n$ and
  $$
\sum_{k=1}^n i_k=2n-2
$$

The proof is basically int two parts. First it's clear that any word generated by the grammar must end in $b$ and that no two $b$'s can be adjacent, so any word in $L(G)$ must have the form noted above.

To show the sum part, let's count the number of $S$'s, $a$'s and $b$'s in any sentential form that results from starting with $S$ and using either of the two productions of the grammar. Let $(s,a,b)$ represent these counts. We have

The production $S\rightarrow aSaS$ will change $(s,a,b)$ to $(s+1, a+2, b)$, since we're adding two new $a$'s and one more $S$.
The production $S\rightarrow b$ will change $(s,a,b)$ to $(s-1, a, b+1)$.
We start with the count $(1,0,0)$.
Note that production (1) followed by production (2) yields the same counts as we would have by using the productions in the opposite order, (2), (1). This observation isn't critical, but it means that we have a particularly pretty form when we apply the productions to the count tuples.
A count $(s,a,b)$ corresponds to a word in $L(G)$ only if $s=0$.

Starting with $(1,0,0)$ we now take D.W.'s tack and look at some small examples. Considering the counts with $s=0$, we find $(0,0,1), (0,2,2), (0,4,3), (0,6,4), (0, 8, 5)$ and so we guess that all the words in the language must have counts of the form $(0, 2n-2, n)$. We're done, right? Well, not quite. We need to show that (1) our guess about the counts was correct, and (2) that we actually can get any sequence of $i_k$'s satisfying these conditions. Fortunately, both pieces are more or less easy to show by induction, though the second one is somewhat messy.

By the way, we can also show that any string in $L(G)$ must have length $3n-2$ and that there are $\binom{n}{2}$ such strings.


In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific advantages of cosine distance over Euclidean distance are:

it is fast and simple - particularly, since vectors are sparse, only dimensions present in both vectors need be considered (if the vectors are pre-normalized);
it works well for vectors with moderate overlap in support, whereas in Euclidean distance coordinates outside of the support of one vector dominate;
it tends to work well with a wide variety of techniques - for example, in your question, LSH for cosine distance is simpler than LSH for Euclidean distance;
the magnitude of a vector, which usually corresponds to the length of the document, is not useful - note that cosine distance ignores length but Euclidean distance doesn't;
it is well-studied so it has momentum.


Suggest structure for query $sumRange(low,high)$ which returns sum of elements whose key $k$ satisfies $low \le k \le high$ in $\Theta(\log n)$ time

Prefix sums or a 1-D summed area table suffice to answer those queries in $O(1)$ time.  (Alternatively, you can augment a balanced binary search tree -- I will let you discover how.)


Pumping lemma to show a language is not context free

First language: $0^{p}1^{p}2^{p^2}$ - If we make $0$ or $1$ longer, $2$ must get longer too to satisfy the condition of the language. Because of $|vwx|\le p$ $v$ cannot contain $0$ when $x$ contains $2$. Also if either $v$ or $x$ contained two different symbols, we know that it would break the language (there would be a sequence of e.g. $0^{i}1^{k}2^{l}1^{m}2^{n}$ with $l,m > 0$).
The last possibility is when $v$ is of form $1^k$ and $x$ of form $2^{l}$. We will prove by contradiction that this is impossible too. We would need such $k, l>0$ that the next equation holds for all $i \ge 0$
$$p(p+i\cdot k) = p^{2}\cdot i \cdot l \\
p^{2} + p\cdot i \cdot k = p^2 \cdot i \cdot l \\
l = \frac { p^2 + p \cdot i \cdot k }{p^2 \cdot i} \\
l = \frac {1}{i} + \frac {k}{p} $$
From $|vwx|\le p$ and $k,l>0$ we know that $k<p$. Similary $\frac{k}{p}<1$ and $\frac{1}{i} < 1$ for $i > 1$. From those and the fact that $l$ is natural number, the only possible value of $l$ is $1$. That would mean
$$p^{2} + p\cdot i \cdot k = p^2 \cdot i \\
k = \frac{p \cdot i - p}{i} \\
k = p - \frac{p}{i}$$

There are two problems with this: first it would hold only when $i$ divides $p$ and $k$ would be dependant on $i$ but has to be a constant. Thus we have proved this is impossible too and the lemma is complete.

For the second language, I believe it is pretty difficult example I and I would advise you to first try some easier languages, if you have just started using the lemma.

You can chose for any $p$ a string $0^{0}10^{1}10^{2}1...10^{p-1}10^{p}$ and then you have to enumerate all the possibilities and prove they don't hold for some $i$.

Either $x$ or $v$ contains two (or more) $1$'s - then it also contains $10^m1$ so with $i>1$ the pumped string will contain two $x_m$'s so it will not be from $L$.
Both $x$ and $v$ contain no $1$'s - with $i=0$ the substrings $x_m$ and $x_n$ containing $x$ and $v$ respectively will get shorter. Since the original string $s$ contained all shorter strings $x_k$ at least one of them will colide with some shorter string.
Either $x$ or $v$ contain only $1$. - If that substring is pumped, the new string will contain $...11... = ...1x_{0}1...$, but the original string started with $1... = x_{0}1...$, thus we have a collision.
Either $x$ or $v$ are of form $0^{n}10^{m}$ with either $n$ or $m$ greater than $0$. With $i=3$ we get $...0^{n}10^{n+m}10^{n+m}10^{m}...$ where we immediately see a collision.

I hope I did not forget some special case.


Mapping reduction to show NeverHalt is undecidable

You will not prove that $NeverHalt_{TM}$ is undecidable by "finding a TM whose language will "help" us solve" it. This would actually prove the opposite, if $M$ is a TM deciding some language.

You have to suppose $NeverHalt_{TM}$ to be decidable by a turing machine $D$, and show that with its help you can decide other non-recursive language. In other words, you have to pick a suitable undecidable language and reduce it to $NeverHalt_{TM}$. There is a reduction from the emptiness problem for turing machines : $E_{TM} = \{\left < M \right >\ :\ \mathcal L(M) = \varnothing \}$.


Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

As long as decision problems (or optimization problems) are concerned, probabilistic Turing machines are equivalent to non-probabilistic Turing machines, since you can just simulate all the possible coin tosses (there are some subtleties here since the probabilistic Turing machine could halt only with probability 1, but let's ignore them).

However, there could be a difference in efficiency. Using truly random coin tosses could allow you to solve a specific problem faster. However, it is conjectured that truly random coin tosses can't bring down the level of difficulty from non-polynomial to polynomial, that is, if you have a probabilistic polynomial time algorithm for a problem, then there exists a deterministic polynomial time algorithm for the problem. This conjecture is known as the P=BPP conjecture. The idea is that you can simulate the truly random coin tosses with a sufficiently sophisticated PRNG. The simulation might be costly in running time, but it incurs only a polynomial overhead, and from this point of view that's a cost we're willing to pay.

Practically speaking, PRNGs are good enough, although in some rare cases you need to be slightly careful and use something beyond the fastest known PRNG. Only in cryptography does it sometimes make sense to use truly random coin tosses, since you can get absolute security guarantees this way (one-time pads), though in practice cryptographic PRNGs are used and they seem secure enough.


Which sort algorithm can I use as a metaphor for this learning philosophy?

Bubble Sort

After each iteration the amount of elements to be compared reduces by one. Will serve a good analogy to working in passes and the amount of work decreases on each pass.

If there is no constraint for analogy the analogy to be from sorting only, then you can use memoization .


This model seems a little confusing due to the role of $G$ and I didn't find their definition of $P(Y|G)$ very sound.

You can consider it the following way:

$$P(Y|\textbf{X},G) \propto P(\textbf{X}|Y) \cdot P(G|Y) \cdot P(Y) = P(\textbf{X}|Y) \cdot [P(G|Y) \cdot P(Y)] \propto P(\textbf{X}|Y) \cdot P(Y|G)$$


Your first step is to characterize what effect you expect an event to have on your signals.  Does it change the mean?  Increase the mean?  Change the variability?  The more you can say about the type of effect it will have, the more specific a test you'll be able to build, and thus the more effective any analysis is likely to be.

Then, your second step is to apply appropriate techniques from the statistics literature on time series analysis.  There are many techniques that look applicable here:

You could look for change points, where the mean value changes.  For instance, the CUSUM procedure might be useful.  Look into the theory on change point detection; there's lots of work on it.  See also https://stats.stackexchange.com/questions/tagged/change-point.
You might also find literature that describes this as looking for a level shift in time series data.  It's basically the same thing.
You might be looking for a "structural change" in the signal, which is a bit more broad/general than change point analysis.  See, e.g., https://stats.stackexchange.com/questions/tagged/structural-change.

I recommend you start with some exploratory analysis.  Based on the underlying physics/mechanics of how your system works, try to identify some ways that an event might affect the resulting signals.  Also, do some exploratory data analysis: find some examples of known events, visualize the signals during those time periods, and hypothesize some feature values that seem to be affected during the signal (e.g., the mean got larger; the standard deviation got larger; the mean of the absolute value of the first derivative got larger; something like that).  Finally, look for appropriate techniques in the statistical literature.  If you can characterize the effect of an event well, you might be able to use change point detection techniques that will work well.  If you can't characterize the effect of an event, you might need to fall back to some kind of machine learning, trained using a large training set... but you should still do each of the steps I listed, to help you identify what features might be useful to use in your machine learning model.


There is no formal definition of "safe programming language"; it's an informal notion.  Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety is being claimed/guaranteed/provided.  For instance, the language might provide type safety, memory safety, or some other similar guarantee.


What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so
$$
g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}.
$$
To obtain an upper bound, notice that as long as $f^{(t)}(n) \geq \sqrt{n}$, we have $\log f^{(t)}(n) \geq (\log n)/2$, and so it takes at most $\log_{(\log n)/2} n = O(\log n/\log\log n)$ iterations to reduce $n$ to $\sqrt{n}$. The same argument applies for reducing $\sqrt{n}$ to $\sqrt[4]{n}$ and so on, and therefore
$$
g(n) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log\log \sqrt[4]{n}} + \cdots.
$$
(Here $\cdot \ll \cdot$ is the same as $\cdot = O(\cdot)$.) Notice that
$\log \sqrt{n} = \frac{1}{2} \log n$. For large $n$, we will have $\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$ (say), and so
$$
\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}.
$$
Therefore the sum is majorized by a convergent geometric series, and we conclude that
$$
g(n) = O\left(\frac{\log n}{\log\log n}\right).
$$
In total, we get that
$$
g(n) = \Theta\left(\frac{\log n}{\log \log n}\right).
$$
With more work, we can probably prove a more refined estimate such as
$$
g(n) \sim \frac{\log n}{\log \log n}.
$$


Complexity of variation of partition problem

Is it in NP? Yes - any restricted version of an NP problem is also in NP.

Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let's call your form of the problem "equal cardinalty 2-partition". To reduce from regular 2-partition to equal cardinalty 2-partition, we can pad the 2-partition problem by adding lots of extra 0's to the set, so that the 0's can be used to balance out any valid 2-partition solution to a solution that is an equal cardinality 2-partition.

You might object to the use of 0's in the input, and define "positive balanced cardinality 2-partition" where the input must be positive (so 0's are not allowed). But I can reduce any balanced cardinalty 2-partition problem to positive balanced cardinalty 2-partition by incrementing all numbers in the input by 1. This does not change the solution because of the equal cardinality constraint (each part of the partition gets increased by equally much).

Now you might still object that this reduction requires that you allow duplicate numbers in the input set. Even if you disallow duplicates in the input it remains NP-hard, and you can show so by a reduction from Positive 1-IN-3 SAT.

Is it in P? Answering this question would settle the P vs. NP problem so you're not very likely to get an answer any time soon.


Making groups out of a list of things based on some similarity

Suppose you represent your items as vertices in a graph and two vertices are connected by an edge if they have a similarity greater than $0.5$.
Then, a possible group corresponds to a clique in this graph (i.e all vertices in the group are connected). You probably only care about the "largest" groups (for example, if $\{x,y,z\}$ is a group then you don't care about the group $\{x,y\}$), which correspond to maximal cliques in the graph.

Thus, your problem amounts to listing all maximal cliques in this graph. Unfortunately, there can be exponentially many such maximal cliques so you won't be able to do this in polynomial time. The Wikipedia article I link to mentions a few sources and ways to do this either in asymptotically optimal time for the worst case or in time polynomial per maximal clique, which might be of interest if the graph happens to have relatively few maximal cliques.


Minimizing total distance traveled by points in points cloud transformation

If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two disjoint intervals with integer endpoints have distance at least $\frac{1}{4H}$ from each other. Hence if $\epsilon$ is less than this value, it might as well be 0.

Take any four points $A, B, C, D$ and assume that there exists a line segment connecting $A$ and $B$, one connecting $C$ and $D$, and that these line segments intersect at point $X$. Then $|A - B| + |C - D| = |A - X| + |B - X| + |C - X| + |D - X|$. Triangle inequality is strict when the three points do not lie on the same line, so if not all of $A,B,C,D$ are colinear, we can exchange the startpoints of the segments to decrease their total length. Thus, if no four points lie on a line, the minimum total length solution doesn't have intersecting line segments.

To find the minimum total length solution, we use min-cost matching, with cost $|A - B|$ to match points $A$ and $B$ (assuming one of $A$ and $B$ is a starting point, and the other is an endpoint).

To handle the case where some four points lie on a line, we just disallow matching $A$ and $B$ if some other point lies between them. Matching in this case is not always possible, for example if we have two startpoints, then two endpoints on a line.


Machine Learning to predict the Halting Problem

After some digging around, I finally came across the original paper.

Regarding applications of a (necessarily fallible) predictor of halting - one possibility is to use it as a heuristic in some wider heuristic process, for example in the generation of Turing-complete programs for Genetic Programming.


Finding the middle point of the "most populated" area in a set of points?

What you are looking for is called cluster analysis or a clustering algorithm. It's a topic studied in unsupervised machine learning, so there's not necessarily a single "best" algorithm that exists (rather, there are different methods which are meant to optimize for different metrics). For example, do you want your clusters to all be similar size? Do you want a fixed number of clusters, or a variable number of clusters? Different answers to these questions result in different algorithms, so you will have to do some research (or try out directly) the different clustering algorithms available. For example, one of the classic algorithms is called k-means clustering.
Once you find the clusters, you can take the average of the points in the biggest cluster to solve your problem.
You don't have to implement the algorithm yourself -- many machine learning libraries (scikit-learn, Pytorch, ...) have out-of-the-box clustering procedures that you can try out and see what they look like for your dataset.


First of all, let me strongly recommend avoiding outdated textbooks such as Aho, Hopcroft and Ullman.
Let me also replace Aho, Hopcroft and Ullman's use of "position" with the more common notion of pointer. In a linked list, each cell consists of a value and pointer to the following cell (if any). The linked list itself is represented as a pointer to its first cell (if any). Therefore, if we consider the list $a,b,c$, then a pointer which is pointing at the third element will be pointing at the cell containing $c$.
(This is also a good place to mention that unless you're programming in Fortran or in Excel, then your arrays are zero-based; that is, the first element is element number 0.)
Now suppose that $p$ is a pointer which currently points at the cell containing $c$. If you insert $x$ between $a$ and $b$, then $p$ will still be pointing at $c$. However, $c$ is now the fourth element rather than the third element.
In contrast, if the list were implemented as an array, then $p$ will be a pointer to the third element of the array. Therefore, after inserting $x$ between $a$ and $b$, the pointer $p$ will be pointing at $b$.


Grouping/Clustering results based on shared values

You could use the Jaccard distance to compare two jobs: i.e., the distance between two jobs is

$$d(A,B) = {|A \cap B| \over |A \cup B|},$$

where $A$ is the set of applicants for the first job and $B$ is the set of applicants for the second job.  Then, use any standard clustering algorithm with this distance measure.


Bipartite Graph to solve the wolf river crossing problem

I have never really imagined solving this problem with a graph, but it is an interesting point of view.
My guess is that the graph you have to create is a bipartite graph with 16 vertices, each vertex representing the state of the situation, that is representing where is each of the different actors of the problem: the wolf, the goat, the cabbage and the boat. Each actor have two positions possibles (each side of the river), so $2^4 = 16$ different configurations. You might then delete forbidden configurations, representing a case where the wolf is alone with the goat or the goat alone with the cabbage.
Now, you can add an edge between two vertices $v$ and $w$ if and only if you can go from $v$ to $w$ by crossing the river with the boat, with one actor from wolf/goat/cabbage on board.
The graph is indeed bipartite, because there are no edges between two vertices where the boat is on the same side.
Solving the problem now results in finding a path between the two vertices where the four actors are on each side of the river.


Generative power and classification of matrix grammars

Isn't the difference because matrix grammars exist with and without appearance checking? In the usual notation $\mathrm{MAT} \subset \mathrm{MAT}_\mathrm{ac} = \mathrm{RE}$.

A matrix grammar basically is a grammar with so-called matrices, lists of context-free type of productions $(A_1\to x_1, \dots, A_k\to x_k)$. There are two main variants of how to apply productions in matrix grammars. Either a matrix is applicable if all its productions can be applied in the given order. This is the less powerful variant, although we can generate $\{ a^nb^n c^n \mid n\ge 1\}$ that way.

Alternatively in a more powerful version some of the productions in a matrix may be marked as skipping productions. If the left-hand nonterminal in such production is present in the string it must be applied, when it is not present the production can be skipped. It is called appearance checking, and turns out to be a very powerful feature.

(added) In your new explicit definition of matrix grammars the set $F$ of occurrences of productions in the matrices are in fact the productions that can be skipped whenever the left side is not present (normally they would block the application of the matrix).
So, when $F\neq\varnothing $ your model has appearance checking. Your first reference indeed has this feature, but does not mention it explicitly by name.


Just a hint:

If the requirement was to count the length $3n$, the NFA was simple, and could be done with 3 states. Similarly, if you only needed the $5m$ part, an easy 5-state NFA could do this.

Now think how to "combine" these two NFAs, one on top of the other. Use $\epsilon$-moves to go from the end of one, to the start of the another. Because you need $|Q|=5$, you will have to overload the meaning of 3 states so they serve both the $3n$ and the $5m$ machines.

Another hint that may be helpful: make $q_0$ accepting (and the only accepting state).

Good Luck.


Selection Sort vs Insertion Sort For Reversed Array

This is an awful question for a test.

Selection sort always has about n^2/2 comparisons and n swaps. Insertion sort has between n and n^2/2 comparisons and the same number of swaps. But as you said absolutely correctly, the actual time depends on the exact implementation.

For example if you look for the smallest element in selection sort like this:

smallest = a[k]
smallestIndex = k
for k+1 ≤ j ≤ n
    if a[j] < smallest
        smallest = a[j]
        smallestIndex = j

you see that that the code in the if-statement will be executed with every execution of the loop.

On the other hand, in the insertion code the moving can be done with some highly optimised code.

So I wouldn't be at all surprised if insertion sort were faster on some particular implementation even in this situation, even though it is the worst case for insertion sort. (I would also not be surprised if selection sort were faster).


Finding the half with greatest elements in a set

Proceed in two phases.

Determine the median of the input.
Partition the input with the median as the pivot (cf. Quicksort).

Both steps take worst-case linear time. Note, though, that in practice you'd not use a linear-time selection algorithm but rather Quickselect, which is faster in expectation.


Why is the PageRank vector also the eigenvector of the web adjacency matrix?

PageRank is the stationary probability (i.e. dominant eigenvector) of the following random walk: with probability 0.85, choose a random outgoing link; with probability 0.15, choose a random web page. The "modified adjacency matrix" that Wikipedia talks about is obtained from the actual adjacency matrix $A$ by computing $0.85 A + 0.15 J$, where $J$ is the all-ones matrix. See this talk (page 13).


Define a finite automaton accepting the language below

It helps to think of finite automata in terms of their states. That is, think of what should each state represent for designing a finite automaton. In fact, it helps to "be the automaton". For this problem, you could start like, Initially, we are at the "start" state, say S1. Now we see an "a", what do we do? We have matched part of the ab substring, so we now need to check if we get a "b" next in line. So this state "waiting for a "b"" is a new state, say S2. Now at S1, we get a "b". This doesn't change anything, we still haven't got an "a" so we continue to remain in S1, waiting for an "a" to match and move to S2. At S2 if we get a "b", we have an "ab" now, so I move to a new "matched ab" state, say S3. At S2, if we get an "a", then we are still in the "matched a" state, and continue to wait for B. Try to think this way, and you shall probably find it easier to design automata, I found this intuition helpful.


What is the impact of synchronisation overhead on parallel speedup?

For current multicore CPUs with support for SMT (Simultaneous Multi Threading), coarse-grained parallelism is strictly required, independently of the parallel technology used (pthreads, OpenMP, MPI). You need to feed each thread or process with enough work, otherwise the cost of thread creation/management and synchronization (for Pthreads and OpenMP) or the cost of communication and synchronization (for MPI processes) will be much higher than the work done per thread/process.

For GPUs, since these are actually SIMD units, i.e., data parallel machines, you need to feed them with data according to a fine-grained data decomposition (again, this is independent from the actual technology used, such as CUDA or OpenCL). In this case, thread management is lower (because it is done in hardware, not in software), but in general synchronization must be avoided, as much as possible. If you can not restructure your code so as to avoid synchronization you are going to experience bad performances on GPUS. Both NVIDIA and AMD recommend to avoid synchronization and to use GPUs for very simple data parallel tasks.
Moreover, you need to copy the data to be processed from the host to the GPU and back once results are computed, and this will also incur a performance penalty, depending on the size of your data processed by the GPU device.


Solving recursion $T(n)=2T(n/2) +2/\log(n)$


Find the shortest path from every vertex to every other vertex. To find the shortest cycle from $s$ to $v$, just concatenate the shortest path from $s$ to $v$ and then $v$ to $s$ which was found earlier


Can converting NFA to DFA change the language?

By definition, two automata are equivalent if they accept the same language.
In your case, the DFA you construct is indeed equivalent to the NFA you start with. Both of them accept all strings starting with $01$. In particular your NFA does not accept $101$.


Dynamic length of union of segments (1d Klee's measure problem)

The online version can be solved in $O(n\log n)$ amortised time, possibly using the technique you already came up with. The key is to maintain just the nonoverlapping intervals that result from merging intervals wherever necessary.

Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, type)$, where $type$ is either $start$ or $stop$. New intervals will be merged with these so that the segments in the tree are nonoverlapping at all times. When a new segment $[a, b]$ arrives, add $b-a$ to the total length, and search the tree to find all contained endpoints. For each such endpoint:

If it is $(x, start)$, add $x$ to the total length.
If it is $(x, stop)$, subtract $x$ from the total length.
Delete it.

If the leftmost such endpoint is a $start$, or if there are no endpoints, then insert $a$ as a $start$ endpoint; otherwise, if there was at least one endpoint (the leftmost of which must be a $stop$), add $a$ to the total length. If the rightmost such endpoint is a $stop$, or if there are no endpoints, then add $b$ as a $stop$ endpoint; otherwise, if there was at least one endpoint (the rightmost of which must be a $start$), subtract $b$ from the total length.

To understand why the time complexity is not quadratic even though an individual operation can take $O(n)$ time, notice that a preexisting interval never needs to be merged with other intervals more than twice (once to its left, once to its right), so we can conservatively pay the cost of these potential merges at the time we create the interval; since merging amounts to removing an endpoint, the cost of performing a merge is constant, so the overall time complexity doesn't change. Basically, any time we have to merge a bunch of intervals, we remove the possibility of having to merge them in the future.


How does the forget layer of an LSTM work?

Think of it like this: The cell state $h_t$ is a vector.  The forget vector $f_t$ is used to choose which parts of the cell state to "forget".  We update the hidden state with something like $c_t = f_t \circ c_{t-1}$ (it's actually more complicated, but let's start with that, to gain intuition).  Suppose $f_t$ were a vector of 0's and 1's.  In the coordinates where $f_t$ is 1, the value of $c_{t-1}$ would be copied over to $c_t$ (it's not forgotten).  In the coordinates where $f_t$ is 1, $c_t$ is reset to zero and the value of $c_{t-1}$ is ignored  (it's forgotten).  So, the forget vector can be used to control in which positions we forget values from the previous cell state vector.

Now what remains is to figure out a way to choose a forget vector $f_t$.  In general we might want to choose which positions to forget based on both the current input $x_t$ and the previous hidden state $h_{t-1}$.  So, we should compute $f_t$ as some function of $x_t$ and $h_{t-1}$.  Many choices of how to represent that function might be possible, but a LSTM chooses a specific function for this.  In a LSTM, this is done by a single-layer fully-connected neural network.  A single-layer fully-connected neural network concatenates all of the inputs, then multiplies them by a matrix, adds a bias, and feeds the result to an activation layer (in this case, sigmoid activation).  So that's why the formula for $f_t$ looks the way it does: that formula is capturing what a single-layer fully-connected neural network does.


Union of a language in P and a language in NP\P

From an Hint (by Yuval Filmus), the statement is FALSE because if $L_1=Σ^∗$ then $L_1 \cup L_2=Σ^∗$. I know $Σ^∗$ is in P (i.e., a TM which accepts all strings), and the statement is FALSE.


Finding the element that occurs more often than the other

I am guessing that the solution you are meant to give is to check the middle entry in the array.
Below is a spoiler as to why this works. Hover with mouse to see, but I suggest you try to figure it out alone first.

   If the middle number is $a$, then since the array is sorted, $a$ appears more than $b$, and otherwise $b$ does.

However, it is not really true that this is a constant time algorithm, as it assumes you can compute the length of the array in constant time.

This is impossible in a standard TM, and even in a RAM model. It requires at least $O(\log n)$ operations in the latter, where $n$ is the length of the array.


Sound and complete algorithms for boolean satifiability

Resolution is sound and complete. In recursive learning, you recursively evaluate the clause satisfiability requirements for identifying common assignments. Look at say page 29 and onwards in these slides.


Rici is correct.  The statement could be reasonably interpreted, as you first assumed:

if E then ( if E then x ) else x

It may also be interpreted:

if E then ( if E then x else x )

In a context-free grammar, the allowable set of expressions are determined through substitution.  In the first interpretation I took your third statement and substituted the first S for the second statement, and then replaced all remain S with x.  In the second interpretation, I took your second statement and replaced it with the third statement, and replaced the remaining S with x using the first statement.


Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

What he wants to show here is that for any sentence of some given length, there is a (very large but finite) number $m$ which is the maximum number of steps in a derivation of the sentence.
If that is true (which it is), then we can figure out whether or not a sentence is generated by the grammar by enumerating all possible derivations with at most $m$ steps. If we encounter the sentence in one of these derivations, then we have derived it. Otherwise no derivation exists.
There are a finite number of such derivations, so this process will eventually finish. That makes it recursive, since it eventually finishes both on success and on failure). (It won't finish during the lifetime of the universe but mathematicians are allowed to ignore inconvenient aspects of reality).
Type 0 grammars (not context-sensitive) are not non-contracting, so we can't limit the number of possible derivation steps. We can still enumerate all possible derivations in order by derivation length (in steps), but we have no guarantee that the process will ever terminate on failure. (More accurately, there is no point on the enumeration at which we can say that a derivation for the sentence will never appear.) So Type 0 grammars are recursively enumerable, but not recursive.


How can one simulate a PDA with a FIFO queue PDA?

The answer is: "rotate".

Consider the stack like (bottom) ABCD (top). stack-pop is from top, queue-pop is from bottom (this is directed to myself, I am easily confused). Pushes are from top.

Now, if we want to stack-pop, we push a marker # (to top) then repeatedly queue-pop and push, essentially moving everything from bottom to top. If we delay the pushes by one, we are able to stack-pop, just not pushing the last symbol before the #.

By the way, almost the same trick shows that we can even simulate the Turing machine by a single queue. Which was asked in our sister math department.


Yes, it is true.

Let $w: E(G) \to \mathbb{R}$ be a weight function on the edges of $G$, $s \in V(G)$ be the start vertex. Let $p(v) = \min\{\max\{w(e_1), \ldots, w(e_k)\} \mid e_1, \ldots, e_k \text{ is edges of a path from } s \text{ to } v \}$ i.e. the shortest path between $s$ and $v$.

Let's prove by induction on the step of Dijkstra's algorithm that it does indeed find the shortest paths. Let $S \subseteq V(G)$ be the set of vertices that have been already processed by the algorithm. Then Dijkstra's algorithm finds $p'(v) = \min\{\max\{p(u),w(uv)\} \mid u \in S\}$ for every $v \in V(G) \setminus S$. Then it is sufficient to prove that there exists $v_0$ such that $p(v_0) = \min p'(v)$ the equality $p(v_0) = p'(v_0)$ holds. Let $e_1, \ldots, e_k$ be the edges of the shortest path from $s$ to $v_0$. $e_k = u v_0$ then $p(u) \le p(v_0)$. If $u \in S$ the statement is proved. Otherwise pick $v_0 := u$ instead (this reduction is finite since we can choose a vertex closer to $s$ in terms of the smallest number of edges in a path between them).

So essentially nothing changes comparing to the algorithm and the proof.

But there is another solution that uses Disjoint Set Union (DSU) data structure. Initialize DSU with sets $\{v_1\}, \{v_2\}, \ldots, \{v_n\}$. Then add edges in the increasing order of $w$ and when an edge $uv$ is added unite the sets containing $u$ and $v$ in the DSU. If at some step an edge with a weight $x$ has been added last then all the vertices in the set containing $s$ have distance to it at most $x$. So if you unite sets $A \ni s$ and $B$ put $p(v) = x$ for $v \in B$.


Inclusion of points in rectangles using a sweepline algorithm

I think storing in the AVL-tree only bottom $y$ coordinate is not enough. I think you should store at least both bottom and top coordinates of the active rectangle. Since your rectangles are not overlapping storing only the bottom and top coordinates is enough to solve the problem.

Basically, storing active rectangle in the AVL tree needs to decide whether a point is in a rectangle. Consider the following scenario

  y1 ----------------------------
     |                          |
     |                          |
  y2 ----------------------------
         o y6
  y3 ----------------------------
     |                          |
     |           o y7           |
  y4 ----------------------------

  y5 ----------------------------
     |                          |
     |                          |
  y6 ----------------------------

Initially your $p$ points in the AVL tree. As you sweep you add both $y$ coordinates of the active rectangles in the tree (and remove them as you rich the end of the rectangle).

If at the same time you have more than one active rectangles then by brute force method you would need to go over all rectangles and check whether $p_y \in [b,u]$. However, using AVL tree you could find the point $p_y$ in the tree and check the number of points smaller than $p_y$. If that number is even, say $2k$, then you have exactly $k$ active rectangles below $p$ meaning that $p$ is not in one of them, otherwise (if odd) it is in a rectangle. Look at the above figure, there are 4 points smaller than $y_6$ and so $y_6$ is outside, but there are 3 points smaller than $y_7$ and so $y_7$ is in a rectangle.


How does size of list in merge-sort, quick-sort, insertion-sort, matter?

It's unclear to me why you put the algorithms in that order. Also, "best work" is quite informal. There are many ways to compare sorting algorithm (worst-case time, expected-time, space complexity, etc). Some considerations that might help you are below.
I can see how InsertionSort could be faster than MergeSort of QuickSort in practice for small lists.
The worst-case complexity of InsertionSort can be upper bounded by $c n^2$ for some constant $c$, while the worst-case (resp. expected) complexity of quicksort can be lower bounded by $c' n \log n$ for some $c'$. It might very well be that the multiplicative constant $c'$ is large enough to satisfy $c n^2 < c' n\log n$ for small $n$.
For huge lists, a "standard" implementation of merge sort requires $O(n)$ auxiliary space, while quick-sort can be run in place. They both have the same asymptotic expected running time, so if that's how you are comparing your algorithms, QuickSort might be preferred.
If you're comparing the algorithms by their worst case running time then it might be the case (I didn't estimate the actual constant, which depends on the specific implementation anyway) that QuickSort runs in time $\approx c_q n^2$ while MergeSort runs in time $\approx  c_m n \log n$. In this case MergeSort is clearly preferred for large enough list but, if  $c_q \ll c_m$, QuickSort would be preferred for moderately-sized lists.
Notice that, in practice, you can just use QuickSort (since the extra overhead spent for small lists in negligible, in the absolute sense). Fancy implementations (such as the ones often found in standard libraries) use hybrid algorithms: they run QuickSort and if they realize that the size of the subproblems is somehow not shrinking fast enough, they revert to MergeSort. Whenever the number of elements left to sort is small, they switch to a quadratic-time sorting algorithm like InsertionSort.


Does adding S->SS in a context-free grammar change the language to its Kleene star?

As chi pointed out in the comment, since $\varepsilon\in L^*$ and $\varepsilon$ may not belong to the new grammar, so adding $S\rightarrow SS$ does not always generate $L^*$. It makes more sense to ask whether it generates $L^+$, so the following answer focuses on $L^+$.

General Form

Consider the following grammar:

\begin{align}
S&\rightarrow aSb\\
S&\rightarrow \varepsilon
\end{align}

It generates the language $L=\{a^nb^n\mid n\in\mathbb{N}\}$.

Now after adding $S\rightarrow SS$ in this grammar, the string $aababb$ can be generated by the grammar but it does not belong to $L^+$.

Chomsky Normal Form

Easy to see $L^+$ can be generated by the new grammar. Now for any string $s$ generated by the new grammar, we can prove $s\in L^+$ by mathematical induction on the depth of its parse tree. Consider the derivation process of $s$.

If the first derivation does not use the rule $S\rightarrow SS$, we can conclude $S$ does not show up in the following derivation since $S$ does not show up in the right hand side of a CFG of Chomsky normal form. As a result, $s\in L$.

If the first derivation uses the rule $S\rightarrow SS$, the strings generated respectively by the two $S$'s in the right hand side must belong to $L^+$ due to inductive assumption, thus $s$, which is formed by concatenating the two strings, also belongs to $L^+$.


Maximum-coverage minimum-overlap intersection of sets

Without knowing anything about the restrictions to your problem, the general version is Set cover, one of Karp's 21 NP-complete problems.
However, if you know more about the structure of the data, you might be able to get better algorithms, see for example the Art gallery problem, where you are given a polygon, and want to find the minimum number of guards/cameras you should place that cover the entire polygon.


Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm?

There are 2 major reasons:

For most algorithms the number of other operations can be bounded by a multiple of the number of comparisons (i.e. runtime in $\mathcal{O}(\#comparisons)$). This is because e.g. a swap does not occur without a prior comparison requiring this swap (depends on algorithm).
Using comparisons you can prove an $\mathcal{O}(n \log n)$ lower bound for any comparison based sorting algorithm on $n$ elements.


General Number Field Sieve Big O Clarification

There is a small difference between these two:

$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$. Here $n$ is a number of bits needed to represent given number $N$.
$O\left( \exp\left((64/9)^{1/3}\,(\log N)^{1/3}\,(\log\log N)^{2/3}\right) \right)$. Here the number $N$ itself is used in notation.

This is true since length of number grows logarithmically of the number itself. Just put $n$ instead of $\log N$ or vice versa and you see that they are equal.

In terms of big O notation constants are uninteresing, so, base of logarithm also is uninteresting. That's why it doesn't make sense whether you interpret number in decimal or binary or any other (except unary) system.

$n=k\,\ln(10)$: here  $\ln(10)$ is constant and we can get rid of it. Also, $k$ depends linearly on $n$, so $k = O(n)$.

$n = \lfloor k\, \log_2(10)\rfloor + 1$: and here both $\log_2(10)$ and $+1$ are removed when written as big O: it still equals $O(n)$.


Modulo hash function and multiples of three

Observe that $2^{2n} = 4^n \equiv 1^n\equiv 1 \mod 3$ and $10^n \equiv 1^n\equiv 1  \mod 3$.  The relevance of $2^{2n}$ is that exchanging two characters (stored in bytes with even numbers of bits) amounts to multiplying one part of a key by $2^{2n}$ for some $n$, and dividing another part by a like amount.  (Also note, powers of 3  ($3^k$ for some $k$) are multiples of 3 ($3\cdot m$ for some $m$ if $k>0$) but multiples of 3 are much more common than its powers.)


Using a 2nd neural network to predict 1st neural network prediction error

It's not an unreasonable approach, but I suspect you'd need to define a custom loss function to make it work well.

I can also suggest two different, more sophisticated approaches: the bootstrap, or a variational neural network.

In the bootstrap, you train many classifiers (say, 100 of them); each is trained on a different random sample of the training set, and then you look at the distribution of outputs from these classifiers when you feed in the input $x$ to each of them.

In a variational network, instead of outputting a single number $y$ for the prediction in response to the input $x$, the network outputs two parameters $(\mu,\sigma)$, with the idea that the network is predicting a Gaussian distribution $\mathcal{N}(\mu,\sigma^2)$ as an approximation for $p(y|x)$.  Then you can use this to get a sort of confidence interval for the prediction, e.g., $[\mu-2\sigma,\mu+\sigma]$.  I'm not an expert on this, but I think a variational network is actually very close to what you suggested; we can think of it as two networks, one that outputs $\mu$ (your first network) and one that outputs $\sigma$ (your second network).  However, variational networks are trained with a special loss function.  In particular, if we have an instance $(x_i,y_i)$ in the training set, the loss for the network is the log likelihood $-\log p(y_i)$ where here $p(y_i)$ represents the probability of getting the output $y_i$ from a Gaussian distribution with parameters $\mathcal{N}(\mu,\sigma^2)$, where $\mu,\sigma$ are the two outputs from the network.  Since the Gaussian distribution has probability density function

$$p(y_i) = c e^{-(y_i-\mu)/2\sigma}$$

where $c$ is a constant.  Therefore, the loss function is

$$-\log p(y_i) = (y_i-\mu)/2\sigma + c'$$

where $c'$ is a constant that can be ignored.  Thus, I think you can think of the variational approach as being equivalent to your approach, but with a custom loss function chosen to be appropriate for what you're trying to achieve.


Is L closed under linear-time reductions?

L is closed under linear-time reductions if and only if L = P.

Proof:

If L is closed under linear-time many-one reductions then:

Since L has non-trivial problems, all problems that are solvable linear time are in L.

Let (x) be the modification of the most basic P-complete problem to ask about "the first sqrt(T) steps" rather than "the first T steps". Since unary-to-binary conversion can be done in linear time and [square-roots can be computed and TMs can be simulated in quasi-linear time], (x) can be solved in linear time. Since L has non-trivial problems, there is a linear-time many-one reduction from (x) to a problem in L. By this paragraph's assumption, that means (x) is in L.  Since L can square unary inputs, there is a logspace reduction from the most basic P-complete problem to (x). Thus (x) is P-complete. Since (x) is in L, that means  P ⊆ L .

If L is closed under linear-time many-one reductions then then P ⊆ L. With no assumptions, L ⊆ P.  Therefore, if L is closed under linear-time many-one reductions then then L = P. Since P can perform linear-time Turing reductions, P is closed under linear-time Turing reductions. Therefore, if L = P  then L is closed under linear-time Turing reductions.  QED


Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

You can use the Akra–Bazzi theorem, a generalization of the master theorem.

Using the notations in the Wikipedia page:

$g(x) = x$
$k = 1$
$a_i = 2$
$b_i = 1/3$
$h_1(x) = 1$ (in fact, probably $h_1(x)$ is a bit different, since $n/3+1$ isn't always an integer)
$x_0$ is a constant which is missing from your recurrence relation

You can easily check that all conditions of the theorem hold. To get the asymptotics, we first compute the value of $p$, which is the solution to $2(1/3)^p = 1$, that is, $p = \log_3 2$. Next, we calculate the integral appearing in the answer formula:
$$
\int_1^x \frac{u}{u^{p+1}} \, du = \int_1^x u^{-p} \, du = \frac{x^{1-p}-1}{1-p}.
$$
We conclude that
$$
T(x) = \Theta\left(x^p\left(1 + \frac{x^{1-p}-1}{1-p}\right)\right) =
\Theta(x^p + x) = \Theta(x^{\max(p,1)}).
$$
Since $p < 1$, the answer is $T(x) = \Theta(x)$.

More generally, the Akra–Bazzi theorem shows that the master theorem applies even when the applications of $T$ on the right-hand side of the recurrence are off by a small amount (at most $O(x/\log^2 x)$).


This language is regular. Since you're looking for equivalences mod 2 we need only consider the evenness or oddness of the count of the two kinds of symbols in the input. Consider a finite automaton with four states: EE, EO, OE, OO, where state EE records that the number of $a$'s seen so far is even and the number of $b$'s is also even. Similarly, being in state EO means you've seen an even number of $a$'s and an odd number of $b$s. States OE and OO are defined similarly.

Now consider the transitions between states. For example, in state EO with input a, the number of $a$'s changes from even to odd, while the number of $b$'s doesn't change, so we have the transition $\delta(\text{EO}, a) = \text{OO}$. The other seven transitions are defined similarly.

The start state is EE, since you've seen 0 $a$'s and 0 $b$'s and obviously 0 is an even number. The final states are EE and OO, for obvious reasons.


R-Tree multipath search - remember the path?

Sure, you can cache the results of lookups into a R-tree (or any other data structure).  Simply build a cache (e.g., a hashtable) where after each lookup into the R-tree, you update the cache; and before doing a lookup into the R-tree, check the cache first.  You don't need to store the entire path in the cache: it's enough to just store the results of the search.

Whether this will improve performance or not will depend on your particular workload.


The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes.
For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and reject).


primitive recursion on untyped lambda calculus

Famously, the fixed-point operator $Y$ of the untyped $\lambda$-calculus, which has the property that
$$ Y\ F=_{\beta}F\ (Y\ F)$$
for every term $F$, is enough to implement primitive (and indeed, non-primitive!) recursion.

Given any encoding of the natural numbers which allows decrementing, if you have an expression
$$ e(n)=C[e(n-1)]$$
where $C$ is some programatic context, you can create a term, $P_e$, defined by:
$$ P_e\equiv\lambda F\ n.C[F\ (n-1)] $$

Now it's easy to show that
$$(Y\ P_e)\ n = P_e\ (Y\ P_e)\ n= C[(Y\ P_e)\ (n-1)]$$
and so it makes sense to define the function $e$ as $Y\ P_e$.


What are the differences between NP-Complete and NP-Hard?

A problem $\Pi$ is $\textrm{NP}$-hard if every problem in $\Pi' \in \textrm{NP}$ can be reduced to $\Pi$ via a Karp reduction $\le_p$, i.e., if $\Pi' \le_p \Pi$.

A problem $\Pi$ is $\textrm{NP}$-complete if it is $\textrm{NP}$-hard and belongs to $NP$.

Intuitively, a $\textrm{NP}$-complete problem is as hard as the hardest problem in $\textrm{NP}$ while a $\textrm{NP}$-hard problem might be even harder.

Finding a polynomial-time algorithm $A$ for any $\textrm{NP}$-hard problem $\Pi$ (therefore also for any $\textrm{NP}$-complete problem) would immediately yield a polynomial-time algorithm for all problems in $\textrm{NP}$: reduce (in polynomial-time) an instance $x$ your problem $\Pi' \in \textrm{NP}$ of choice to an instance $y$ of $\Pi$ and then solve $y$ it using $A$.


You can solve this optimally in $O(kn^3)$ time by solving a sequence of $k$ Assignment problems.

Let $f(i)$ be the lowest sum of costs of any set of $n$ paths beginning at step $i$ and continuing to step $k$ (i.e., the end). We would therefore like to compute $f(0)$, as well as a set of paths realising it.

Assume we have already computed $f(i+1)$. (Clearly $f(k) = 0$, so we have a starting point.) Let $A_{i,i+1}$ be the solution to the Assignment problem (minimum-weight bipartite matching) in which one set of vertices are the points in $S_i$ and the other is the points in $S_{i+1}$. I claim that we can compute $f(i)$ as $A_{i,i+1} + f(i+1)$.

Suppose this claim is not correct: then for some $i$, there is a better solution with cost $B_i < f(i)$, which can likewise be decomposed as $B_i = B_{i,i+1} + B_{i+1,k}$. In particular, let $i$ be the maximum possible $i$ for which $B_i < f(i)$. Then at least one of $B_{i,i+1} < A_{i,i+1}$ or $B_{i+1,k} < f(i+1)$ must be true for our assumption $B_i < f(i)$ to be true.

It cannot be that $B_{i,i+1} < A_{i,i+1}$, since $A_{i,i+1}$ is the minimum possible cost by definition of the Assignment problem. So it must be that $B_{i+1,k} < f(i+1)$. But this cannot be true either, since if it were then it would violate our assumption that $i$ is maximum possible. Thus supposing the existence of a solution with a better cost $B_i$ leads to a contradiction, so it cannot be true, meaning that $f(i)$ gives the optimal cost after all.

$f(0)$ gives you the cost of the optimal solution. To extract such a solution, just record the matchings produced by the Assignments problems you solved along the way.


Validity of Algorithm for Testing Two Floating Point Numbers

There is one method to compare floating point numbers for equality, which is both very simple and correct: You use the equality (==) operator.
There is another method to compare whether floating point numbers are identical, which unlike the equality operator would find that -0 and +0 are not the same, and that NaNs with the same bit pattern are the same: Use memcmp. (Don't do this if your compiler stores 80 bit long double into 128 bits).
What you are talking about is the question: "Are these two numbers so close together that their difference could be due to rounding errors alone", and another question would be "Are these two numbers so close together that we don't care that they are different".
Swift has decided to put an operator for the latter into its standard library. This considers floating numbers with an n bit mantissa "as good as equal" if the difference is at most the last n/2 bits.
So first don't call your function "equals", because that is a lie. Call it "almostEqual" or something like that. Then make sure that it returns true without failure whenever x == y, that almostEqual (x, y) == almostEqual (y, x) for all pairs x, y, and that it returns the same result if you scale x, y both by the same power of two (unless this produces overflow or underflow).
Be aware that you cannot guarantee that almostEqual(x,y) and almostEqual(y,z) implies almostEqual(x,z). This also implies that you cannot make it compatible with any hash function.


Are there grammar classes between Chomsky level 1 and 2?

I know I'm pretty late, but oh well.

There's a class of grammars known as indexed grammars (describing indexed languages, which are a proper subset of CS languages and a superset of CF languages). The rules look very much like the ones in a CF grammar, but every LHS nonterminal has an associated stack of index symbols, and when rewriting that nonterminal, the stack can be manipulated by other nonterminals in the RHS. For example:

$A[\sigma] \rightarrow B[\sigma x] C[\sigma y]$

which means "rewrite nonterminal A to nonterminals B and C, copy the stack and push x to B's stack and y to C's stack" or

$A[\sigma x] \rightarrow B[\sigma]$

meaning "if there's an A with x on top of its stack, rewrite it to B and pop that x off the B's stack".

Some examples of indexed languages are $\left\{ a^n b^n c^n d^n | n \geq 1 \right\}$ or $\left\{ www | w \in \left\{ a, b \right\}^+ \right\}$.

As for the automaton, indexed languages are exactly the class of formal languages recognizable by a nondeterministic nested-stack automaton, which is basically a NPDA in which some elements of the stack may be other stacks.

Concerning practical use, wikipedia says that indexed grammars sometimes find use as affordably processable descriptors of natural languages.

Edit: As Raphael mentioned, indexed languages | grammars are closely related to mildly context-sensitive languages.

There's a class of grammars similar to indexed grammars called linear indexed grammars. While in an IG, every nonterminal in the RHS recieves a copy of the LHS's stack, LIGs require that at most one nonterminal in the RHS recieves the stack. Given that any LIG can be transformed into an equivalent IG, they're strictly less powerful and it has been shown that the set of languages they generate is equivalent to the set of mildly context-sensitive languages.


If your heuristic is essentially the original problem, but with some constraints removed, it is monotonic.
Otherwise, you must prove that there is no transition which does not uphold the formula in Caesar's answer.


$L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular

You can write this language as the intersection of two languages:
$$
\{ x \# y \mid  xy \in L \} \cap \{ y \# x \mid xy \notin L \}
$$
I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows:

Start with a DFA for $L$.
Guess which state the DFA will be on after reading $x$.
Based on this guess, verify that after reading $xy$, the DFA reaches a rejecting state.
Now read $x$ and verify your guess.

You take it from here.


If you repeat an Algorithm $A$ with negligible probability  $\epsilon(n)$ of success for an input of length $n$ the number of times until the first success happens is a geometrically distributed random variable $S$. The expected value of $S$ is

$$\mathbb{E}(S) = \frac{1}{\epsilon(n)} = n^{\omega(1)} \quad .$$

So an attacker using $A$ polynomial many times  (say $p(n)$) can't have non negligible probability of success, which we'll see by comparing expected values. Let $A'$ be the algorithm which repeats $A$ $p(n)$ times and the random variable which represents the number of times $A'$ has to be repeated until the first success shall be named $S'$. Then:

$$\mathbb{E}(S) \leq p(n) \mathbb{E}(S')\quad,$$

so a non negligible success probability for $A'$ would mean a non negligible probability for $A$, since the product of two polynomials is again polynomial. So allowing negligible probabilities does no harm (at least for polynomial bounded adversaries).

This is essentially contains an indirect proof that $p(n)\epsilon(n)$ is still negligible for any polynomial $p$, which can also be proven directly: $p$ is dominated by its largest exponent, so $p(n)\in \mathcal O(n^c)$ for some $c \in\mathbb{N}$. On the other hand $\epsilon(n)\in o(n^{-d})$ for all $d\in\mathbb{N}$. Define $d'=d-c$ and you'll get $\epsilon(n)\in o(n^{-(d'+c)})$ for all $d'\in\mathbb{N}$. So $p(n)\epsilon(n)\in o(n^{-(d'+c)})\mathcal O(n^c)=o(n^{-d'})$ for all $d'\in\mathbb{N}$, which is again negligible.

If you insist on a probability of $0$ (or $\frac{1}{2}$ in the case of distinguishers) many applications become (nearly) impossible. Consider a cryptographic hash function $h$ and an unknown argument $x$. The probability of finding a preimage $x'$ s.t. $h(x')=h(x)$ taken over all $x$ can't be $0$, because testing all possible inputs will lead to success eventually. You could however choose to limit the probability with $2^{-n^{\Omega(1)}}$ or similar and call only those functions negligible. But most of the time only unbounded adversaries or efficient (i.e. polynomially bounded) adversaries are considered, so the different notions wouldn't matter, as an efficient adversary can break none and and unbounded can break both.


In short, a reduction need not preserve approximations. For more details, see my answer on cstheory to a similar question.


Confusion over the complexity of parameter passing in merge sort

The $N$ is incurred once for every recursive call, since this is the cost of passing a parameter. Since there are two recursive calls, it's $2N$. As for the $4N$, this seems like a mistake. Don't expect solutions you find on the internet to be correct. Finally, $N$ is not a subset of $n$. It is the size of the original array. A less confusing way to write the conclusion would be $\Theta(nN) = \Theta(N^2)$. Note that it is always the case that $n \leq N$ (and not the other way around).


A byte of data is eight bits, there may be more bits per byte of data that are used at the OS or even the hardware level for error checking (parity bit, or even a more advanced error detection scheme), but the data is eight bits and any parity bit is usually invisible to the software. A byte has been standardized to mean 'eight bits of data'. The text isn't wrong in saying there may be more bits dedicated to storing a byte of data of than the eight bits of data, but those aren't typically considered part of the byte per se, the text itself points to this fact.

You can see this in the following section of the tutorial:

Doubleword: a 4-byte (32 bit) data item

4*8=32, it might actually take up 36 bits on the system but for your intents and purposes it's only 32 bits.


What ML methods exist to categorize signal from noise? Red noise? Spatially correlated noise?

The basic approach is to model the noise as an appropriate stochastic process (aka random process).  There's an entire subfield of statistics that has studied different kinds of stochastic processes, and they each have different properties.  It would be too much to try to summarize that entire subfield in a single answer here.


Space complexity of directed and undirected graph

It's hard to know for sure from what you've written, but I suspect what you're doing wrong is that you're considering what the space requirement would be for a complete graph.  For a complete graph, the space requirement for the adjacency list representation is indeed $\Theta(V^2)$ -- this is consistent with what is written in the book, as for a complete graph, we have $E=V(V-1)/2 =\Theta(V^2)$, so $\Theta(V+E)=\Theta(V^2)$.

However, you shouldn't limit yourself to just complete graphs. There are other graphs that aren't complete, and have fewer edges than the complete graph.  In general, the space for the adjacency list representation is $\Theta(V+E)$; this fact holds for all graphs, regardless of how many edges they have.

Why is this true?  It's because for each vertex you have a pointer to the head of a linked list.  That's $\Theta(V)$ space for all of those pointers.  Also, the total number of nodes across all the linked lists is equal to $2E$, as each edge $(u,v)$ appears twice: once in the list for $u$, and once in the list for $v$.  Therefore the space needed for all of the linked lists is $\Theta(E)$.  Adding the space for the pointers and the space for the lists gives $\Theta(V+E)$.

You could say that the space requirement for the adjacency list is $O(V^2)$.  It's true that it will never be more than that.  However, for some graphs it will be much less.  For instance, in a graph that is a simple path ($v_1 \to v_2 \to \dots \to v_n$), there are $V$ vertices and $E=V-1$ edges in total.  For that graph, the adjacency list representation will need $\Theta(V+E)=\Theta(V)$ space.  Thus the $O(V^2)$ upper bound is very loose and too pessimistic.


Does the Paxos algorithm use failure detectors?

In short, the "plain" Paxos algorithm does not use failure detectors, but it can be augmented with failure detectors. Furthermore, the "plain" Paxos algorithm does not fully solve the problem of consensus.

To answer this question more in detail, we first define "the consensus problem". An algorithm "solves" the problem of consensus if it guarantees that the following properties are satisfied:

Termination (or liveness, or progress): all non-faulty processes eventually decide on a value
Agreement (or consistency, or safety): all processes that decide do so on the same value
Validity (or non-triviality): the value that has been decided must have proposed by some process

The "plain" Paxos guarantees that agreement and validity are always satisfied, that is, if you use Paxos to solve consensus, then you will never get as a result processes that decide on different values or that decide on values that have never been proposed.

However, "plain" Paxos does not guarantee termination, that is, if you use "plain" Paxos, then it is possible that processes will never decide on a value. This problem can be (partially) circumvented by using using "leader election", that is, you elect a leader (which must be a proposer in the "plain" Paxos algorithm) which coordinates the proposals. However, the leader can also fail. This failure of the leader can e.g. be detected using failure detectors (which, in practice, may be implemented as "timeouts"). Therefore, Paxos can use failure detectors. But I won't dwell more on this topic.

In conclusion, "plain" Paxos does not fully solve the problem of consensus, because it does not guarantee "progress".


Canonically, we convert from infix to postfix form only expressions. However, you can enhance this by introducing the assignment operator = in addition to the standard four binary operators +, -, *, and /. Just define the conversion as: a = b  becomes  ab=. So for example, a = x + 5 becomes ax5+=.

As for the negative numbers, you can parenthesize them (as you suggest). For example,  a = -b + 2 becomes a(-b)2+= or just separate each operand or operator by a single space, for example the previous postfix expression can be written as a -b 2 + =. This is another example: derv = -dy/dx + 5*(-x) becomes derv(-dy)dx/5(-x)*+= or derv -dy dx / 5 -x * + =.


Miss penalty for Write request in a Write-Back style system

Depends on what you mean by "penalty". In theory (and in practice in high performance processors), a store does not need to stall subsequent instructions, so there's essentially no penalty at all from a store miss.

If you're talking about issue-to-commit time (i.e. when the store can be considered permanent) then the latency would indeed be when the cache line read occurs.

NOTE:

Most if not all architectures (ARM for example) allow non-temporal store hints. In practice most processors treat these as non-cacheable stores. So they go directly to memory without the need to grab the data into cache.

Some microarchitectures detect store streams to a temporal block. They support a type of RdNoData command that simply grabs store permissions without transferring data.


Finding the best poker hand in a connected grid structure where order matters

I recommend you use breadth-first search (BFS) through the state space.

Start by trying to find (partial) straights that are ascending.  For each possible starting position (there are 12 possibilities), use BFS to search for a path that starts at that position and makes an ascending straight (i.e., the numbers increment by one each time you move forward).  This will find you the longest ascending straight.

Next search for descending (partial) straights in the same way.  This will find you the longest descending straight.

You can also search for straight flushes in this way, too.

Next for x-of-a-kinds in the same way.  This will find you the longest sequence that are all of the same rank (e.g., two-of-a-kind, three-of-a-kind, four-of-a-kind, five-of-a-kind).

Next search for flushes in the same way.  This will find you the longest sequence that are all of the same suit.

You can look for two-pair and full-house separately, with a different method tailored to that problem.  Enumerate all pairs (i.e., all pairs of adjacent positions where the two cards have the same rank).  Now check whether any two of those pairs are adjacent; if so, you have found a two-pair.  Similarly, enumerate all three-of-a-kinds (i.e., paths of length 3 where the three cards have the same rank).  Now check whether any pair is adjacent to any three-of-a-kind; if so, you have found a full-house.

In this way you can find the best poker hand in the grid.  I expect that this will be very efficient.


Linear congruential generator with uniform distribution

One issue with your generator is that when computing tmp = (a*state)%p, you are actually taking modulo twice: first modulo $2^{32}$ (with sign), then modulo $2^{31}-1$. So you aren't really computing $a^t \pmod{p}$ like you might have expected. To test this hypothesis, you can ask Java to use long for the multiplication a*state – the results should improve. There is also a difference between using signed and unsigned arithmetic, though you can't test this in Java.

The other generator is more careful - it's only multiplying small numbers (the result is below $2^{31}$), which is why the truncation issue doesn't effect it.

The other generator computes the function
$$ y\lfloor \tfrac{p}{a} \rfloor + z \mapsto az - (p\pmod{a}) y. $$
(The comparison to $0$ just ensures that the result is in $[0,p)$ without affecting the value modulo $p$.)

The idea is that
$$ a(y\lfloor \tfrac{p}{a} \rfloor + z) \equiv az + y(a\lfloor \tfrac{p}{a}\rfloor-p) \pmod{p}. $$
Now $a\lfloor\frac{p}{a}\rfloor-p = -(p\pmod{a})$, and so the other generator really computes $x \mapsto ax \pmod{p}$.


Loading a word from a byte addressed cache

For nearly all major architectures, a cache line is 64 bytes wide. All memory transactions from your L1 cache all the way out to DRAM will use 64 byte lines. The only place where the byte address-ability comes into play is between the processor core and the L1 cache. It is common for L1 RAMs to be built with byte enables or some from of specification to a subset of the bytes from a 64 byte cache line.

Let's assume the interface from the processor to the L1 cache yields an address and a width (number of bytes). Suppose you want address 0xF002 and you want 4 bytes. The cache line is address 0xF000 (0xF002 & ~0x003f), the offset within the cache line is 0x0002 (0xF002 & 0x003f), and because you specified a 4 byte width you'd receive bytes 0xF002, 0xF003, 0xF004, and 0xF005.

Most processor/cache interfaces will only support common widths (1, 2, 4, 8 bytes), and basic architectures will force the addresses to be aligned (i.e., a 2 byte read can't start at an odd address). More advanced architectures will handle the misalignment in hardware (see MIPS unaligned load/store for a bad implementation). x86 allows unaligned loads and stores. Here is a short list of reasons unaligned memory accesses are bad:

  Why unaligned access is bad

  The effects of performing an unaligned memory access vary from
  architecture to architecture. It would be easy to write a whole
  document on the differences here; a summary of the common scenarios is
  presented below:

  Some architectures are able to perform unaligned memory accesses    transparently, but there is usually a significant performance cost.
  Some architectures raise processor exceptions when unaligned accesses    happen. The exception handler is able to correct the
  unaligned access,    at significant cost to performance.
  Some architectures raise processor exceptions when unaligned accesses    happen, but the exceptions do not contain enough
  information for the    unaligned access to be corrected.
  Some architectures are not capable of unaligned memory access, but will    silently perform a different memory access to the one that was
  requested,    resulting in a subtle code bug that is hard to detect!

  It should be obvious from the above that if your code causes unaligned
  memory accesses to happen, your code will not work correctly on
  certain platforms and will cause performance problems on others.
  from: https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt


Yes, this problem is decidable.  It can be answered in polynomial time.  We can check whether there exists any input $x$ that causes it to enter an infinite loop, by characterizing the states from which it could enter an infinite loop.

First, let me establish some terminology.  Let $Q$ denote the set of states of the DPDA, and $\Gamma$ the stack alphabet.  A configuration is a pair $(q,t)$ with $q \in Q$, $t \in \Gamma^*$, where $q$ represents the state of the automaton and $t$ the contents of its stack.  Define the status of the automaton at any point to be a pair $(q,\gamma)$ where $q \in Q$ represents the state of the automaton and $\gamma \in \Gamma$ the symbol at the top of the stack.  Thus, the status gives only partial information about the configuration of the automaton.

Now, the strategy is going to be twofold:

We will determine, for each possible status $(q,\gamma)$, whether that status is reachable (i.e., whether there is some input $x$ that takes the automaton to a point where it is in that status).
We will also determine, for each possible status $(q,\gamma)$, whether the automaton enters a particular kind of infinite loop if the automaton starts in the configuration $(q,\gamma)$ and then reads the input $\epsilon$ (the empty word).  In particular, if it starts in configuration $(q,\gamma)$ and reads the input $\epsilon$, we'll test whether it transitions to any configuration $(q,t)$ where $t$ has the form $\cdots \gamma$ (i.e., $\gamma$ at the top of the stack, with some other stuff below it in the stack) in the process of reading the empty word.

Putting these two together, if there is a status $(q,\gamma)$ for which the answer to both questions is yes, then we will learn that the input $x$ causes the automaton to enter an infinite loop.  We will show a polynomial-time algorithm for each.  Since there are only finitely (in fact, polynomially) many possibilities for the status, this gives a polynomial-time algorithm for the original problem.  So, on to the details of how to check each of these things.

First, reachability is easy and can be tested using standard methods.  (For instance, construct a new automaton that halts when it enters the status $(q,\gamma)$ and otherwise doesn't halt, then check whether that automaton accepts the empty language or not; there is a standard algorithm for that.)

Second, it's easy to find all statuses $(q,\gamma)$ where an automaton that starts in configuration $(q,\gamma)$ and reads the empty word will enter an infinite loop of the particular kind mentioned above.  (One way is to reduce this to reachability; construct a new automaton that starts in configuration $(q,\gamma)$ and halt if it reaches any configuration of the form $(q,\dots \gamma)$ apart from the initial state, discarding all non-$\epsilon$ transitions from the original automaton and keeping only the $\epsilon$ transitions.  Then, check whether this new automaton accepts a non-empty language.)

This yields an algorithm for the original problem.  Why is it correct?

Well, if this algorithm outputs "yes", then it is correct -- there exists an input $x$ that causes the automaton to halt.  In particular, we know there exists an input $x$ that causes the automaton to transition to status $(q,\gamma)$, i.e., to some configuration of the form $(q,t_0 \gamma)$.  Suppose reading the empty word causes the automaton to transition from configuration $(q,\gamma)$ to $(q,t_1 \gamma)$; then it follows it will subsequently transition to $(q,t_1 t_1 \gamma)$ and even later to $(q,t_1 t_1 t_1 \gamma)$ and so on, entering an infinite loop.  Thus, reading the empty word will cause the automaton to transition from the configuration $(q,t_0 \gamma)$ to the configurations $(q, t_0 t_1 \gamma)$ and $(q, t_0 t_1 t_1 \gamma)$ and so on, thus entering an infinite loop.  Since the input $x$ takes us to that configuration $(q,t_0 \gamma)$, we have found an input $x$ that causes the DPDA to enter an infinite loop.  So if the algorithm says "yes", it is correct.

What about the converse?  Let's suppose there exists some input $x$ that causes the DPDA to enter an infinite loop.  It follows that the infinite loop must happen during the $\epsilon$-transitions that follow some finite prefix of $x$, say $x'$.  Let $(q',t')$ denote the configuration of the automaton immediately after reading the last letter of $x'$ (but before following any of the subsequent $\epsilon$-transitions).  Let's consider the sequence of configurations that the DPDA visits after that point, by following the $\epsilon$-transitions.  By assumption, this is an infinite sequence.  Consider the corresponding sequence of statuses.  Since that is infinite sequence, and there are only finitely many statuses, there must be at least one status that appears infinitely many times.  Discard a large enough prefix of the sequence so that you remove all the statuses that occur only finitely many times, so that now we have a sequence where all statuses recur infinitely many times; such a prefix must exist.   Among all configurations in the resulting sequence, pick the configuration where the height of the stack is minimal.  Call this configuration $(q,t)$ where $t=t_0 \gamma$.  By the choice of $(q,t)$, it follows that in all subsequent configurations the stack is at least as tall, so the original symbols $t_0$ are never popped, i.e., all subsequent configurations are of the form $(q',t_0 u)$ for some $q' \in Q$, $u \in \Gamma^+$.  Also since the status $(q,\gamma)$ recurs infinitely often in the sequence and since $(q,t_0 \gamma)$ was the one of minimal height, there must be some subsequent configuration of the form $(q, t_0 t_1 \gamma)$ (i.e., some subsequent configuration with the same status, but stack at least as high).  And since we got from $(q, t_0 \gamma)$ to $(q, t_0 t_1 \gamma)$ by $\epsilon$-transitions, without ever popping off the $t_0$ part, this means we'll enter an infinite sequence $(q, t_0 \gamma) \leadsto (q, t_0  t_1 \gamma) \leadsto (q, t_0  t_1  t_1 \gamma) \leadsto (q, t_0  t_1 t_1  t_1 \gamma) \leadsto \cdots$.  Since the $t_0 \gamma$ was never popped off, that also means that if we had started in the configuration $(q, \gamma)$, we would also have entered an infinite sequence $(q, \gamma) \leadsto (q,  t_1 \gamma) \leadsto (q, t_1 t_1 \gamma) \leadsto \cdots$, and this would have been detected in step 2 of the  algorithm.  Also, by assumption, since the configuration $(q, t_0 \gamma)$ is reachable on input $x'$, the status $(q,\gamma)$ is reachable and this would be detected in step 1 of the algorithm.  In summary, if there exists an input $x$ that causes the DPDA to enter an infinite loop, there exists a status $(q,\gamma)$ that is reachable and that triggers an infinite loop of the specific kind detected in step 2 of the algorithm, so the algorithm will output "yes".


Communication allowed in the NC^i model?

The model of parallel computing used in the definition of Nick's class is PRAM (see this wiki page, note: particular policy for handling read/write conflicts is irrelevant for Nick's class). In this model, the processors share memory and a common clock, but are otherwise independent. Therefore, any communication that happens between processors uses memory as the channel. The result of the computation can be announced in some pre specified register.

Edit:

Note there are a couple ambiguities in your statements: to show that a problem belongs to $\mathrm{NC}^i$ you can choose $k$ (the power in your polynomial number of processors) depending on the particular problem, while $i$ is fixed. Also, all the quantities should only be specified up to a constant, e.g. $O(\log^i n)$ time and $O(n^k)$ processors.


Is this benchmark sufficient to consider my algorithm as an efficient matrix multiplication algorithm?

one thing I want to mention is that the strassen's matrix multiplication algorithm isn't often used in the real world and your algo is probably faster if the $n$ stays below a few thousands (explained here: https://stackoverflow.com/questions/13559928/why-is-my-strassens-matrix-multiplication-slow).
Now if you still want to compare your algorithm to the strassens algorithm I would recommend you to copy past a function from somewhere and run it on your computer.
The algorithm would get the same input as your algo and would run on the same hardware.
Here are some implementation of strassens algo:
vectors:
https://github.com/dmonaldo/strassen-matrix-multiplication/blob/master/main.cpp
arrays:
https://www.geeksforgeeks.org/strassens-matrix-multiplication-algorithm-implementation/
When I benchmark an algorithm I always want to plot the results to visualize the complexity. I think more is better; so you should probably use more n not only 256, 512, 1024. Also it would be good to know if your algo is made for a special case like sparse matrices etc. if that's the case you need to pay close attention to the input data, otherwise one algo might have a disadvantage.


Can't wrap my head around on building a suffix table for Boyer Moore

The shift rules of Boyer–Moore algorithm come from the bad character rule and the good suffix rule.
While the bad character rule exploits a single character that is in the text but not in the pattern, the good suffix rule exploits multiple contiguous characters that appear in both the text and the pattern.
"In the first table, for k = 5, we have d2 = 4." This is because "AB" is both a prefix of "ABCBAB" and a suffix of "BCBAB". So if some text contains "BCBAB", it is possible that text extends to right to contain "BCBABCBAB", thus containing the pattern "ABCBAB". It is not simply because 'we match the A with the suffix "BCBAB"'. That B after A should be matched as well.
In the second table for k = 4, although we can match the D at the beginning with the D inside "RIDI", a shift of 3 cannot possibly match the whole pattern, since it will lead to the mismatch between the I after D and the R after D. So there is no need to consider a shift of 3.
          T:    ***RIDI̲***
  current P:      DRIDI̲
P shifted 3:         DR̲IDI


Is it possible to wear-level a FAT32 file system?

The OS references blocks using a "logical block address".  The SD card then maps this to a physical page of flash memory.  With wear leveling, each time data in that block is changed, it will get mapped to a new physical page of flash memory.  So, even though the OS is changing the same "logical block address" every time, this is causing different physical pages in flash to be erased and rewritten.  This spreads out the "wear" across the entire flash device, lengthening its lifetime and avoiding the problem you mentioned.  In other words, although the FAT32 is stored at the same "logical block address", it isn't stored on the same physical page of flash memory every time it is modified.
I'd expect that any commercial flash storage device you buy today will be using wear leveling, because of exactly the problem you mention if wear leveling isn't used.  This problem is not specific to FAT32; it occurs with essentially all conventional filesystems.


Isn't Functional Programming just Imperative Programming in disguise?

If we peel off the syntactic sugar on the front and the code generation on the back and compare what happens in between when converting source to running code for imperative languages, such as C or Java with functional languages such as ML or OCaml we will generally find the following differences in what, why, and how.

Mutable vs. immutable

With functional programming one tends to use immutable values which means that we don't have to worry if a value changes by a means external to our current function. When used correctly this removes any problems related to side effects.

Focus: Data versus function.

When one thinks of coding in imperative one first thinks of data structures and then what methods they need, when working with functional programming one first thinks of what functions are needed and then makes the data types needed. Most of the data types are either lazy list, (think stream or infinite list) or discriminated unions. When the discriminated union is recursive you instantly have created a tree or graph without having to write all of walking code.

Generics/Parametric polymorphism

This one is interesting, and if I have my facts correct, was invented with functional programming and then transplanted to imperative programming. So if you like generics thank the functional language designers.

Referential transparency/Parallelization

Because of referential transparency functional code can be more easily ported to parallel computing.

Higher order function/compositionality

Since functions can create new functions and return functions, creating new functions is based on other functions is as easy as creating new expressions instead of writing entire new methods. This leads to morphisms which are very useful if the problem you are solving can be expessed with math. Doing set transformations, think SQL and updates, is so much easier with functional programming. As Wandering Logic noted this is where functional programming languages excel.

Typing: Static versus inference.

Since the types are inferred as opposed being set by the programmer during writing, more checks can be to ensure the correctness of the code and often the functions will be made generic as opposed to being of a set type.

Pattern Matching vs switch statement

When combining matching with discriminated unions, your matching is checked to ensure you have covered every outcome. How many times have you had a run time error because you missed a case with a switch statement.


"In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state." wiki quote.
Its output depends on state and polynomial, not two states.

The name come (afair) from Fibonacci work on recurence relation, his sequence, and further interest in characteristic polynomials of generating sequences, but the one who gave closed form solution to Fibonacci numbers and researched characteristic equation (the one used in generator with possibly minimal monic to make longest period), was Lucas. I cannot find any reference why it is called Fibonacci LFSR, but it is inventors will to name it.

The same stands for LFG - lagged Fibonacci generator was (in multiplicative form) introduced by Marsaglia to overcome deffects of additive one.

The real interest in random generation was started by Galton (if it matters Romans did toss coins and stored bits), random numbers by Pearson, first PRNG is attributed to von Neuman, first working one to Lehmer, as for Fibonacci his insights are nice, but he started his sequences to count rabbits with no connection to PRNG whatsoever.

Of you are interested in history of PRNG, History of uniform random number generation
 is nice.


How would it be possible that primality testing is in P, but not factorization?

First of all, it doesn't make sense to talk about solving any particular formula in polynomial time--every specific formula can be solved in constant time (the answer is either yes or no, we just don't know which). So talking about whether any particular formula is "evil", probably does not make sense.
Also, just because we can solve problem A, by reducing to the problem B, doesn't mean we can solve everything near problem B. In fact, we may not even be able to solve problem B, in some cases!
Can you remove some clauses and make a family of SAT problems harder? Definitely. Take any family, and add the clause $A \& \bar{A} $. Now the answer is definitely "no". Remove that clause, and the problem is hard.
This makes sense--removing constraints often feels like intuitively makes things harder. Think about sudoku--less filled in boxes, doesn't always make the problem easier.


Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach.

You are correct. While the master theorem can yield asymptotically tight bounds, the question asks you to prove an exact inequality, $T(n) \leq 8n^2$ for all for $n\in\mathbb{N}_0$.

Since this is a proposition on natural numbers, we should use mathematical induction. Because $T(n)$ is related to $T(\lfloor n/2\rfloor)$, we will use strong induction.

Base case. $n=0$:   $T(0)=0\le 8\cdot0^2$.

Inductive step. Assume for all $k < n$, prove for $n >0$:

$$T(n)=3T(\lfloor{n/2}\rfloor) + 2n^2\le3\cdot8(\lfloor{n/2}\rfloor)^2 + 2n^2\le24(n/2)^2+2n^2=8n^2$$

Note that since $\lfloor{n/2}\rfloor\lt n$, we can apply the induction hypothesis to obtain $T(\lfloor{n/2}\rfloor)) \leq 8(\lfloor{n/2}\rfloor)^2$.

Exercise 1. Show that $T(n) \lt 8n^2$ for all $n >0$.

Exercise 2. What is the largest $n$ such that $T(n) \le 7n^2$?

Exercise 3. Show that $\dfrac{T(n)}{n^2}\to8$ when $n\to\infty$.