Can a new company make a processor compatible with Windows and current software?

In theory a new microprocessor manufacturer could enter the market. In practice this is very unlikely, but not for any reason to do with the x86 architecture - the barrier is economics.

Manufacturing modern microprocessors is a highly complex engineering challenge which requires a lot of very expensive equipment. Getting the design right in the first place requires a massive upfront investment. And the profit margin on each unit is tiny, so in order to turn a profit you also have the additional overhead of investing in automation - you cannot just employ an army of production line staff.

A saturated market place with established players, high fixed costs and low profit margins is not going to be attractive to start-ups or new entrants, or to their investors.

The one thing that might change this is a breakthrough in technology. If you invent a way to manufacture a portable quantum computer from household waste in your garage using a few DIY tools, then you are home and dry.


Round robin tournament scheduling using divide and conquer

The recursive approach is not necessarily the simplest one here. There is a simple direct construction I am quoting from here. Suppose first that you are trying to schedule $n$ teams, where $n$ is odd. In total there are $n(n-1)/2$ matches to schedule, and in each round at most $(n-1)/2$ matches can take place, so there should be $n$ rounds in total. All computations below are modulo $n$. In round $r$, team $x$ plays against team $r-x$, except for team $r/2$, which stays out. Here is an example for $n=5$:

Round 0: 1–4, 2–3, 0 sits out
Round 1: 0–1, 2–4, 3 sits out
Round 2: 0–2, 3–4, 1 sits out
Round 3: 0–3, 1–2, 4 sits out
Round 4: 0–4, 1–3, 2 sits out

It's easy to prove the correctness of this schedule. Indeed, teams $x$ and $y$ meet in round $x+y$ and in no other round.

If $n$ is even then there are $n(n-1)/2$ matches to schedule, and each round at most $n/2$ can take place, so there should be $n-1$ rounds. Indeed, we take the schedule for $n-1$, and pair up the team sitting out with the extra team. For example, for $n=6$:

Round 0: 1–4, 2–3, 0–5
Round 1: 0–1, 2–4, 3–5
Round 2: 0–2, 3–4, 1–5
Round 3: 0–3, 1–2, 4–5
Round 4: 0–4, 1–3, 2–5

It's again not hard to prove the correctness of the schedule. If $x,y \neq n-1$ then they meet in round $x+y$, while $x$ and $n-1$ meet in round $2x$ (where all computations are modulo $n-1$).


Perceptrons: Functions not learnable without bias

If you don't have a bias, your perceptron learns the function

$$y = w_1 \cdot x$$

This means the decision boundary is a line through (0, 0).

AND

$y, x, w_1 \in \mathbb{R}^2$

Function table:

x_1 x_2 y
---------
0   0   0
0   1   0
1   0   0
1   1   1

This is not learnable.

  I am using a sigmoid activate function.

Without a hidden layer, a Perceptron is still a linear classifier.


Difference between heuristic and approximation algorithm?

A heuristic is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a proof it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a plausible idea, that should not give a too bad solution. In this case, it can be shown that it won't always give a good solution.

An approximation algorithm is usually understood to give an approximate solution, with some kind of guarantee of performance (i.e., it solves TSP, and the total cost is never off by more than a factor of 2; or even better, it solves TSP and, depending on <some parameters that can be varied> the solution is never worse than optimal by more than a factor $1 + \epsilon$, where $\epsilon$ depends on <parameters>).


Binary symmetric sources and information theory

You want to generate $n$-bit random variables $X_1,\dots,X_m$ such that the Hamming  distance between $X_i,X_j$ is about $pn$.  Let me start by showing you how to do this for the special case where $n=1$; then I'll generalize.

Set $q = (1 - \sqrt{1-2p})/2$.  Pick a set $S \subseteq \{0,1\}^m$ of $m$-bit values, such that every element $s \in S$ has Hamming weight $qk$.  Now pick a random $s$ from $S$, randomly permute the bit positions of $s$, and assign this to $X_1,\dots,X_m$ (i.e., $X_i$  is the $i$th bit  of $s$).  I claim this will have your desired property.  Why?  Well,

$$\Pr[X_i \ne X_j] = \Pr[X_i=0,X_j=1] + \Pr[X_i=1,X_j=0] = 2q(1-q) = p,$$

so the expected value of the Hamming distance between $X_i,X_j$ will be about $p$, as desired.  The joint  entropy is easy to calculate: it is simply $\log_2 |S|$.

What if we want $n>1$?  Then we can just sample the first bit of $X_1,\dots,X_m$ as above; then sample the second bit of $X_1,\dots,X_m$ in the same way (iid; i.e., pick another  $s$ from $S$, and randomly permute its bit-positions); and so on.  This gives us a source where the expected value of the Hamming distance between any  two $X_i,X_j$ is about $pn$, and where the joint entropy is $n \log_2 |S|$.


Basic complexity theory (in Oracle Separation of BQP and PH)

Let me answer your questions one by one.

Black-box separations versus oracle separations

Black-box algorithms are given access to a black box. For example, an algorithm might get black box access to a function $f\colon \{0,1\}^n \to \{0,1\}$. This means that the algorithm can obtain the value of $f(x)$ for any given $x \in \{0,1\}^n$, but is not otherwise given any explicit description of $f$.

As an example, consider the following promise black box problem: given a function $f$ which is either the constant $0$ or balanced (that is, half its values are $0$ and half are $1$), determine which of these two cases $f$ belongs to. There is a very simple randomized algorithm which makes a constant number of queries and outputs the correct answer with constant probability; but every deterministic algorithm must make exponentially many queries in the worst case. This is an example of a black-box separation between promise versions of $\mathsf{P}$ and $\mathsf{BPP}$.

Oracle separations also pertain to black-box algorithms, but now we want to fix the black box. In order to separate two relativizable complexity classes $A$ and $B$, we need to find a specific oracle $O$ such that $A^O \neq B^O$ (or prove that one exists). For every oracle $O$, the classes $A^O$ and $B^O$ consist of languages decided by algorithms with no auxiliary input. Rather, these algorithms have access to an $O$-oracle. But in contrast to the situation in the preceding paragraph, here the oracle is not part of the input. Rather, it is fixed.

The standard example is Turing machines with access to an oracle to the halting problem. In contrast to the example given above for black-box algorithms, here the oracle is not an input but rather an additional mechanism that the machine can make use of.

On randomness

A language $L$ is in $\mathsf{BPP}$ if there is a randomized polytime machine $T$ such that:

If $x \in L$ then $\Pr[T(x) = 1] \geq 2/3$.
If $x \notin L$ then $\Pr[T(x) = 1] \leq 2/3$.

When considering the black box version of $\mathsf{BPP}$, the definition remains exactly the same. The black box is not randomized; only the algorithm is randomized. As an example, consider the promise problem of determining whether an input black box is the constant zero function or is balanced. This problem can be solved in $\mathsf{BPP}$ by sampling a few points, or in $\mathsf{E}$ by querying the first $2^{n-1}+1$ values of the black box.

Randomization is part of the algorithm, not the decision problem.

Oracle circuits

The paper you are reading doesn't actually use these — the oracles are only applied to $\mathsf{BQP}$ and $\mathsf{PH}$. But for completeness sake, let me mention that the most common model uses oracle gates, which are gates that provide access to the oracle.

An advice

Let me close with an advice. The paper you are trying to read is at the forefront of research. It would be extremely hard to appreciate it without having some background. This paper is probably not a good entry point into complexity theory. I suggest familiarizing yourself with complexity theory first, for example by reading parts of the textbook by Arora and Barak.


Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?

Consider the worst case analysis: when the array is completely sorted, but from largest to smallest. In this case, bubble sort will make $n-i$ swaps in iteration $i$ (and in particular, there will be a swap in every iteration), and repeat that for $n-1$ times. This gives a total runtime of $(n-1)^2=\Theta(n^2)$.

Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$.


What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem.

In your example you would construct this graph:

The arcs with no label have weight zero.

Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores according to your definition. There are many efficient algorithms for obtaining the $k$-th shortest paths, including a variation on Dijkstra's algorithm which is probably the easiest to implement.

PS. Some of these algorithms require that the weights of the arcs be non-negative. That can be easily achieved in your case, by adding a large enough constant to every weight, e.g., shifting every weight by +13 in your example. The result is equivalent, since all the paths from $s$ to $t$ contain the same number of arcs.


Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?

The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.

A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.


Can you have three consecutive black nodes in red-black search tree?

In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.


Cartesian product of regular expressions?

Gelade and Neven prove the following theorem in their paper Succinctness of the Complement and Intersection of
Regular Expressions:

  For every $n$ there exist two regular expressions $r_1,r_2$ of size $O(n^2)$ such that the smallest regular expression representing $L[r_1] \cap L[r_2]$ has size $\Omega(2^n)$.

This suggests that there is no analog of the product construction for regular expressions.


Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$

The language $$L= (0+1)^*$$ (the set of all strings over $0$ and $1$) is countable. Furthermore, any subset of $L$ is also countable. However, the set of all sublanguages of $L$
$$S = P(L) = \{M \mid M \subseteq L\}$$ (a set of sets in fact) is not countable. This video proves this using the diagonalization argument.

$S$ and $L$ are two different sets. In fact, $L$ is a member of $S$.


Every string in $SAT_H$ has length $m+1+m^{H(m)}$ for some $m$. In particular, there will be strings of length at most $\log n$ whenever $m+1+m^{H(m)} \leq \log n$. For some reason you insist that $m$ equal $n$. Perhaps you should consider the following equivalent definition of $SAT_H$:
$$SAT_H = \{\psi01^{|\psi|^{H(|\psi|)}} : \psi \in SAT\}. $$
There is, however, a subtle point: the definition of $H(n)$ relies on the set $SAT_H$, whose definition in turn relies on the definition of $H(n)$ in what seems to be a circular fashion! However, if you work out the details you see that $H(n)$ relies on those parts of $SAT_H$ which depend on $H(m)$ for much smaller $m$. Indeed, we need to know the members of $SAT_H$ of size at most $\log n$. Each such member comes from a $\psi$ of size $m+1+m^{H(m)} \leq \log n$, and in particular $m \leq \log n$. So we only need to know the value of $H$ on the much smaller values up to $\log n$.


How can a 32bit CPU have an addressable memory size of 16TB?

The $32$ bit page frame address acts as a base address and will be typically stored in an index register.

An individual machine code instruction (e.g. a branch instruction) will then contain a $12$ byte bit offset. The offset is added to the base address to create the complete $44$ byte bit address.


Why does space(n) <= time(n) imply that TIME(f(n)) is a subset of SPACE(f(n))?

A machine which runs in time $f(n)$ also runs in space $f(n)$, that is, the space used by a machine is always at most the time it uses. In symbols, $\mathrm{space}_M(n) \leq \mathrm{time}_M(n)$.

A machine is in $\mathsf{TIME}(f(n))$ is it runs in time $O(f(n))$. Any such machine also uses space $O(f(n))$ (since the space used by a machine is at most the time it uses), and so it is in $\mathsf{SPACE}(f(n))$. In other words, $\mathsf{TIME}(f(n)) \subseteq \mathsf{SPACE}(f(n))$. This implies that
$$
\mathsf{P} = \bigcup_{k=0}^\infty \mathsf{TIME}(n^k) \subseteq \bigcup_{k=0}^\infty \mathsf{SPACE}(n^k) = \mathsf{PSPACE}.
$$
A similar calculation shows that $\mathsf{EXPTIME} \subseteq \mathsf{EXPSPACE}$.

For the remaining relation, we have to use a different fact about time and space: a machine which uses space $f(n)$ runs in time $O(2^{O(f(n))})$. This is because the number of configurations in a (one-tape) machine which uses space $f(n)$ is $|Q| f(n) |\Sigma|^{f(n)}$, where $|Q|$ is the number of states and $|\Sigma|$ is the size of the tape alphabet. You can check that this implies the remaining containment $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.


Does Second chance Page replacement algorithm suffer with Belady's anomaly?

This is not true.  This is only a special case in once instance of 2nd chance algorithm.  All reference bits set to one does not persist for each page that tested for a page replacement.  Since LRU does not suffer from Belady's anomaly, and since 2nd chance is an approximation to LRU, then it follows that 2nd chance does not suffer from Belady's anomaly.


Is there any way to distinguish between LL(k) and LR(k) grammar?

$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in the classes, because this is so if and only if the tables contain no errors. Also, yes, there are classes of grammars which we can parse efficiently if we have a parse table, but for which we cannot generate the table if it exists.

Any textbook on parsing methods will teach you how to generate the tables for $LL(1)$ methods and possibly also for $LR(1)$ (though $SLR(1)$ is more common). Textbooks such as Parsing Theory by Sippu and Soisalon-Soininen also treat the parse table generation for $LL(k)$ and $LR(k)$ grammars.

Unfortunately, for really weird grammars, the parse tables for $LL(k)$ and $LR(k)$ (though not for $LL(1)$) can blow up and become huge; they will do this even for normal grammars if $k$ is high enough. There are tests available that can check whether a grammar is $LL(k)$ or $LR(k)$ or not that run in polynomial time (table generation is exponential). For details, read the textbook above. Note that in a lot of cases, the table is reasonably sized, so the test is not needed.

If you don't want to try values of $k$ to see if your program works, but instead want to have your computer figure out whether there exists a value of $k$ such that your grammar is $LL(k)$ or $LR(k)$, you are unfortunately out of luck, as this is undecidable. If your grammar is $LR(k)$ for some $k$ though, you can decide whether your grammar is $LL(c)$ for some $c$, possibly different from $k$ (see here for details).


Yes. A deterministic Turing machine can simulate another deterministic Turing machine (possibly only up to some point), and an Enumerator is a particular kind of deterministic Turing machine.


Falsifying the "Circular Wait" Condition - Deadlock Prevention

It's fixed.  Your example violates the protocol.  If the process needs mutually exclusive access to both the tape drive and the disk drive, then it needs to take locks in increasing order, i.e. first the tape drive then the disk drive.  If it wants to use the disk drive before the tape drive, that's fine, it will just be holding the tape drive lock in the mean time.

The ordering and protocol is a global invariant.  All code everywhere at all times needs to follow the protocol to avoid deadlock.  In practice, this is pretty difficult to enforce in realistic code unless there's a manager that handles resource access.


It's impossible to tell if all you have is the pictorial representation, since these look the same for both types of automata. Even if you're given a formal specification you won't necessarily be able to tell the difference (it depends on how these automata are encoded).

This kind of ambiguity is similar to linguistic ambiguity that can occur in real life. For example, suppose you see the word "impossible" written on the wall. Can you tell whether it's English or French?

Sometimes this kind of ambiguity is purposeful. For example, the pictorial representation of a DFA doubles as the pictorial representation of an equivalent NFA. The only difference in your case is that the two interpretations are inequivalent.


Is there any meaning behind the classification of "λ-terms" in classes such as "church number" and "church list"?

Several observations can be made based on your remarks:

In System F, every data type can be given an encoding using polymorphic types, e.g. $\mathrm{Bool}$ can be defined as the type
$$\forall A.A\rightarrow A\rightarrow A$$
On the other hand, certain terms (not all of course) can be given a principal type in system F, e.g.
$$\lambda ab.a $$
can be given the type $\forall AB.A\rightarrow B \rightarrow A$. But you can now notice that this is a generalization of the type $\forall A.A \rightarrow A \rightarrow A$, and this happens to be the most general type it shares with $\lambda a b.b$, which is of course the polymorphic encoding of $\mathrm{Bool}$. In this way, one can always attempt to assign the most general type to a term, and then check to see if this happens to be (a generalization of) the polymorphic encoding of a datatype.
Intersection type systems are usually undecidable type systems assigning types to pure $\lambda$-terms that have the remarkable property of classifying their behavior: in particular the most simple such system is complete for strong normalization: a term has a type iff it is SN.

In intersection type systems, it is always possible to interpret the set of all types of a term (ordered by the sub-typing relation) as a representation of the behavior of that term. In particular, there is a close correspondence between the various domain theory models of the pure $\lambda$-calculus and various intersection typing systems. See for example Intersection Types and Lambda Theories for an overview.


Understanding $\text{handle}$ in parsing problem

I'll assume you talk about the 'handle' as often defined in the context of LR-parsing. I'm not entirely sure if the definition you use is the proper definition: $A$ and $B$ seem to stand for nonterminals, but $B$ should really stand for some string of terminals and nonterminals (as the right hand side of a production of $A$, to be precise) to have a proper meaning.

Let's parse your example using LR machinery, and illustrate what happens. In particular, we'll find multiple handles during the parse. The dot '$\bullet$' will show where in the parse we are at the moment. We're looking for suffixes of the part to the left of the bullet that exactly match productions of our grammar.

$\bullet aaAbBb$ - we're starting at the beginning.
$a \bullet aAbBb$ - moving on, '$a$' is not a handle as it is not a production.
$aa \bullet AbBb$ - moving on, '$aa$' or '$a$' is not a handle as it is not a production.
$aaA \bullet bBb$ - '$A$', '$aA$' and '$aaA$' are not productions.
$aaAb \bullet Bb$ - '$b$' and '$aAb$' are candidate handles (they are right-hand sides of productions), but your parse tree shows that neither gets reduced, so we ignore them.
$aaAbB \bullet b$ - '$bB$' is a handle! We reduce it to $B$.
$aaAB \bullet b$ - '$aAB$' is a handle! We reduce it to $A$.
$aA \bullet b$ - '$A$' and '$aA$' are not productions.
$aAb \bullet$ - '$aAb$' is a handle! We reduce it to $S$.
$S \bullet$ - Oh hey, we're done: the input was part of the grammar.


The claim is not true (unless you add some "nice" conditions on the functions).

Take, for example, the functions $g(n)=n$, and consider the following function $f$: on the even numbers, we'll take $f(n)=n^2$, and on the odd numbers, take $f(n)=n$.

Since $n\notin \omega(n)$, then the assumption holds (that is, $f(n)\notin \omega(g(n))$), but since since $n^2\notin O(n)$, we also have that $f(n)\notin O(g(n))$.


Greedy approach suggestions for assigning objects

This problem reduces to finding a maximum matching in a bipartite graph, which can be done easily by e.g. the Ford-Fulkerson algorithm. You construct the graph as follows:
Take all elements of type $a$ on one side and all elements of type $b$ on the other. Then, for any two elements $a_i,b_j$, draw an edge between them if they do not belong to the same category.
If there is a matching in the set with only, say, $k$ pairs belonging to the same category, then we can find a matching in our graph on $m-k$ edges, where $m$ is the number of a's (or b's).


Least Significant Bit (LSB) vs Little Endian - Are they equivalent in anyway!

LSB (least significant bit) and MSB (most significant bit) apply purely to the values of an integer. The least significant bit is the bit with value 1, the second least significant bit is the bit with value 2, and so on.

"Little endian" and "Big endian" are just artefacts from the fact that the bytes of a number can be accessed individually as they are stored in memory. But if an integer is stored in 4 bytes, there are actually 24 different ways in which order these bytes could be stored in memory; big endian and little endian are just two of those 24.

With all this said, if you have been understanding your professor correctly, and reported accurately what he said, then he is absolutely wrong. Actually the multiple choice answer "lower bit" is already nonsense (maybe not nonsense, but we really like precision in CS). If you have 32 bits, 31 of them are "lower" than some other bit, but ONE of them is the lowest bit. The Least Signficant Bit.

When "Little Endian" and "Big Endian" are abbreviated, they are abbreviated as LE and BE (for example UTF-16 LE and UTF-16 BE).


Prove the probability of which a hash function is collision-free

For every $i < j$, the probability that $h(x_i) = h(x_j)$ is at most $2^{-n/2}$. The number of pairs of indices $1 \leq i < j \leq M$ is $M(M-1)/2 < M^2/2 = 2^{n/2}/200$, hence a union bound implies that the probability that $h(x_i) = h(x_j)$ for some pair $i < j$ is at most
$$
2^{n/2}/200 \cdot 2^{-n/2} = 1/200.
$$
It follows that the probability that $h(x_1),\ldots,h(x_M)$ are all distinct is at least $199/200$.


Not satisfiable 3SAT instance implications

You are describing the Resolution refutation system, which is complete in the sense that if a CNF is unsatisfiable, then it can be proven using Resolution. Resolution is also implicitly used in most SAT solvers.
The width of a Resolution refutation is the maximal number of literals in a clause encountered during the refutation. There are 3CNFs on $n$ variables which require width $\Omega(n)$, for example Tseitin contradictions on 3-regular expanders; see for example Massimo Lauria's lecture notes. This means that every Resolution refutation of these 3CNFs must contain a clause having $\Omega(n)$ literals.


Can the plus operator in regex be replaced by the star operator?

True. For any regular expression $R$, (the meaning of) $R^+$ equals $R \cdot R^*$, and conversely, $R^*$ equals $R^+\mid\varepsilon$ (where $\mid$ here is the choice operator 'or', and $\varepsilon$ the expression matching the empty string).

Thus in any regular expression dialect it suffices to include only one of star and plus without loosing expressibility. Translation of plus into star can be done recursively (inside-out).


I personally, do not see why this is left as unanswered.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just negate every query output.


Comparison of two line segments along a ray

The best way to see this is to describe the algorithm more carefully:

Pick one of the segments, say $s_1$. First, we test the orientation of the points $a_2,b_2$ w.r.t. $s_1$. If both lie on the same side of $s_1$, we test the orientation of $q$ w.r.t. $s_1$. Then, we have two cases:

$q$ lies on the same side as $a_2,b_2$. This means $s_1$ is further away, as your figure shows.
$q$ lies on the other side as $a_2,b_2$. This means $s_2$ is further away, which can also be seen from the figure, with a little imagination.

If $a_2$ and $b_2$ do not lie on the same side w.r.t. $s_1$, note that, since $s_1$ doesn't intersect $s_2$, it follows that $a_1,b_1$ are on the same side w.r.t. $s_2$!

So, we now only need to test whether $q$ lies on the same side as $a_1$, w.r.t. $s_2$: If it does, $s_2$ is further. If it doesn't, $s_1$ is further.

So, we have exhausted all possibilities and determined which segment is further using only four orientation tests! (In the first case, we test $a_2,b_2,q$ w.r.t. $s_1$ and in the second $a_2,b_2$ w.r.t. $s_1$ and $q,a_1$ w.r.t. $s_2$)
So, we were able to improve upon the given $5$ in the description, by postponing the testing of $q$, such that $q$ only has to be compared to one segment and not $2$.

(Note that in the given configuration, if we assume $q$ isn't collinear with any of the segments, no points are on the linear extension of the segment, which means they are always on exactly one side.)


Nim Games: Is it possible to reduce following using Grundy Number?

Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the sum as well as the current set of allowed addends. You can compute the Grundy function, which gives the equivalence to Nim, using dynamic programming.


Maximizing the rank of a binary matrix by zeroing matrix entries

The largest rank equals the size of a maximum matching of the corresponding bipartite graph, for which there are known efficient algorithms; see for example Wikipedia.

On the one hand, if the graph contains a matching of size $m$, then we can delete all other entries, thus obtaining a matrix in which an $m\times m$ minor is a permutation of the identity, and so of rank $m$. Thus the maximum achievable rank is at least the size of any matching.

On the other hand, suppose that by deleting entries of the original matrix $A$, we can obtain a matrix $B$ whose rank is $m$. The matrix $B$ must contain an $m\times m$ minor $C$ whose rank is $m$ (find a set of $m$ rows which form a basis for the row space, then a set of $m$ columns which form a basis for the column space). In particular, $\det C \neq 0$ and so there must be a "generalized diagonal" in $C$ which consists only of $1$s (since $\det C$ is the sum of the products of all generalized diagonals). This generalized diagonal appears already in $A$, and constitutes a matching of size $m$ in the corresponding graph.


Best improvements to do to the DPLL SAT algorithm

The most improvement with the least effort will come from adding rapid random restarts to your solver.  DPLL is known to exhibit heavy-tailed behavior, producing both short and long search times for instances depending on initial search conditions.  Random restarts allow the solver to bail out of exponentially long searches of unfruitful assignments and give the solver more chances to find one of those short searches sooner.

Implementing two-watched-literals will produce the next big improvement because it eliminates a major backtracking cost.  Backtracking is done exponentially often in the worst case, so any improvements there offer unequivocal improvements in search speed.  Implementing two-watched-literals will require a significant overhaul of your solver, but it will teach you a lot about how real-world SAT solvers work.


Vertices reachable from negative-weight cycles in Bellman-Ford

You don't need to perform DFS separately from each such vertex.  Instead, add a new fake vertex $s_0$, with an edge from $s_0$ to each vertex in a negative cycle; use DFS to find all vertices reachable from $s_0$; and set their distances to $-\infty$.  This needs only a single DFS, rather than many DFS's.  It is simple and fast; there is no hope for something that is asymptotically faster, as it takes linear time, and in the worst case, you might need to visit all vertices, taking linear time in the worst case.


motivation and idea of defining non-deterministic Turing machine

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.

I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".

An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.

Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.

A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.

This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible.
For example, if we input $9$ to the NTM we just described,
then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.

  It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.

  Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?

No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.

  If no, why do we need to allow multiple choices for a Turing machine?

We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.

  In this sense, an NTM looks like a multi-threading parallelization to save time?

Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.

In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.

Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.


Stacking things of different thickness to approximate desired thickness

This is as hard as the subset sum problem.  The subset problem asks "is there a way to get exactly the desired thickness?".  Obviously, if we could solve your problem, we could also solve the subset sum problem.  Unfortunately, the subset sum problem is NP-hard, so your problem will be too.

In practice you can try using an approximation algorithm for the subset sum problem, e.g., by rounding to the nearest integer (or to the nearest multiple of $1/k$ for some $k$) and then applying the dynamic programming algorithm for subset sum.  See, e.g., https://en.wikipedia.org/wiki/Subset_sum_problem


Determining how similar a given string is to a collection of strings

Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined.

Given the heuristics, you can use likelihood to get a score which would (hopefully) be higher for your sample data than for other text. In order to determine a reasonable threshold, you can perform cross-validation. Pick a set of sample phrases which are not city names. Divide the city names into two parts, a large (say 80%) part and a small (say 20%) part. Train your model on the large part (that is, collect statistics on the large part), and then evaluate your model on the small part and on the sample of bad phrases. Determine if there is a reasonable threshold that passes most city names, but only a small amount of bad phrases.


Yes. Suppose that $L \in P$, then $x \in rot(L)$ if and only if there exist $u,v$ such that $x = uv$ and $vu \in L$.

A simple polynomial time algorithm for deciding membership in $rot(L)$ is: given the input $x =x_1 x_2 ... x_n$ generate the $n$ rotated strings $x_1 x_2 .. x_n,\, x_2 x_3 .. x_n x_1,\ldots, x_n x_1 .. x_{n-1}$ and check
in polynomial time whether at least one of them belongs to $L$; in that case accept ($x \in rot(L)$) otherwise reject ($x \notin rot(L)$).


Is Equality problem decidable in DCFL and CFL?

We can't. Infinitely many different PDAs for the same DCFL exist.

In 1997, Géraud Sénizergues proved that equivalence of DCFLs is decidable, and he was awarded the Gödel Prize for it.

For general context-free languages, it is undecidable.
As a matter of fact, it is already undecidable for linear context-free languages.


Reference introductory books or articles to Game Semantics

I know three introductions that may satisfy your criteria. All of them will use some Category Theory, but the first one (by Jürjens)  is actually quite light on that side -- he actually defines what categories and morphisms are in the context of game semantics, on page 111 (11th page of the article). You may want to read this one first, and then the others.

Games in the Semantics of Programming Languages -- an elementary introduction by Jan Jürjens.
Game Semantics by Abramsky and McCusker.
Semantics of Interaction (arXiv:1312.0121v1 [cs.LO]) by Abramsky.


Finding the longest overlapping interval pair

Hint: Try divide-and-conquer.  I can only see about two plausible ways to do the "divide" step; try both of them, and one of them should work to yield a useful algorithm.


The Turing test and Searle's Chinese Room argument represent two alternative definitions of intelligence.

The Turing test is based on the assumption that intelligence is difficult to formally define but can be easily recognised by behavior. So if a computer program behaves and interacts in a way that is practically indistinguishable from the behavior of human being (who we assume is "intelligent") then, based on this assumption, we should say that the computer program is also intelligent. In the Turing test, the particular behavior that is tested is holding a conversation in natural language.

Searle's Chinese Room argument is a challenge to the validity of the Turing test. It posits a complex system that behaves as if it were intelligent (in this case, holding a conversation in Chinese), but in which each component of the system follows an algorithm, and so no part of the system can be said to "understand" Chinese. The Chinese Room argument is based on the assumption that the system as a whole cannot be said to be intelligent unless some of its individual components are intelligent - it is essentially a reductionist argument.

In summary, the Chinese Room argument says that its is possible for a system to simulate intelligence without actually being intelligent. Whereas the Turing test is says that if a system can simulate intelligence then it actually is intelligent.

We can illustrate the difference between the two points of view with an analogy as follows. The Turing test would say that an aeroplane flies because it travels through the air from one place to another - it exhibits "flying" behavior. The Chinese room argument would say that an aeroplane only simulates flight because it does not flap its wings.


Reduction from $L_{nonuniversal}$ to $L_{finite}$

For brevity, denote $L_{finite}, L_{nonuniversal}$, respectively, as $L_f, L_n$. To establish a mapping from $L_n$ to $L_f$ we map $\langle\,M\rangle\rightarrow\langle\,N\,\rangle$, where $\langle\,N\,\rangle$ is defined by

N(x) =
   for s = epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... //i.e., the standard order
      run M on s
      if M(s) = accept and s = x
         return accept

Now look at the behavior of this mapping:

If $\langle\,M\,\rangle\in L_n$ there will be some string in $\{0,1\}^*$ which is not accepted by $M$. Let $z$ be the first such string in standard order. Then $N$ will accept all and only those strings $y$ which are earlier in order than $z$ so $L(N)$ will consist of only those $y$s and so will be finite, i.e., $\langle\,N\,\rangle\in L_f$.
Similarly, if $\langle\,M\,\rangle\notin L_n$, then $L(M)=\{0,1\}^*$ so $M$ will accept every string and consequently $L(N)=\{0,1\}^*$, an infinite language, so $\langle\,N\,\rangle\notin L_f$.

These two observations establish the reduction we need.


You can do much better. Consider for example the tree in which the root has $N$ children, and each one has one child. The maximum matching has size $N$, but the longest path is only four edges long.

Here is a better algorithm. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the subtree, as well the maximum matching within the subtree that doesn't touch the root of the subtree. You can think of it as a form of dynamic programming.

Many problems on trees can be solved efficiently using this kind of dynamic programming.


How to predict the length and offset of the sequence in and array?

Let $n$ be the length of the string, and $k$ be the maximum length of the substring. Thus the first $n-k+1$ positions correspond to length $k$, the next $n-k+2$ to length $k-1$, and so on. Denote by $i_\ell$ the index at which substrings of length $k-\ell$ begin. We have
$$
i_\ell = \sum_{t=k-\ell+1}^k (n-t+1) = \frac{[(n-k+1)+(n-k+\ell)]\ell}{2} = \frac{\ell^2}{2} + \ell\left(n-k+\frac{1}{2}\right).
$$
Given $i_\ell$, we can solve for $\ell$:
$$
\ell = \sqrt{(n-k+1/2)^2+2i_\ell}-(n-k+1/2).
$$
Monotonicity shows that for arbitrary $i$, the floor of this expression still gives the correct value of $\ell$. This suggests the following algorithm:

Let $i$ be the input index.
Calculate $\ell = \lfloor \sqrt{(n-k+1/2)^2+2i}-(n-k+1/2) \rfloor$.
Calculate $i_\ell = \ell^2/2 + \ell(n-k+1/2)$.
Output length=$k-\ell$ and offset=$i-i_\ell$.

For example, let's take $i = 10$ in your case (where $n = 11$ and $k = 4$). Then $\ell = \lfloor \sqrt{7.5^2+20}-7.5 \rfloor = \lfloor 1.23\ldots \rfloor = 1$ and $i_\ell = 1^2/2 + 1\cdot 7.5 = 8$. Hence the length is $4-1=3$ and the offset is $10-8=2$.


What does ⊢ mean in operational semantics?

This is something that I think is not explicitly pointed out or not pointed out with enough emphasis in many, even introductory, CS/type theory/logic texts.

$\vdash$ doesn't mean anything.

Instead, in this example, the three place relation $- \vdash - \Rightarrow -$ is what has meaning.

Except that was a lie. It doesn't a priori have meaning either.  That relation is what is being defined.  $- \vdash - \Rightarrow -$ is just a (mixfix) name.  It does, of course, have some informal meaning we are hoping to capture with this definition, and after it is defined it does have meaning.

In most cases, such relationships are being inductively defined which makes them identical to inductive families in a dependently typed language.  For example, here are the rules for the arithmetic language fragment from figure 3.2 in section 3.1:
$$
\frac{}{\langle n,s \rangle \Downarrow n} \qquad
\frac{\langle e_1, s\rangle \Downarrow n_1 \qquad \langle e_2, s\rangle \Downarrow n_2}{\langle e_1 + e_2, s \rangle \Downarrow n_1+n_2} \qquad
\frac{}{\langle \mathtt{L}, s \rangle \Downarrow s(\mathtt{L})}
$$

and here's Agda code for this fragment:

data Expr : Set where
    Num : Nat -> Expr
    Add : Expr -> Expr -> Expr
    Lookup : Label -> Expr

data Eval : (e : Expr) (s : Label -> Nat) (n : Nat) -> Set where
    EvalNat : {n : Nat}{s : Label -> Nat}
        -> Eval (Num n) s n
    EvalAdd : {e1 e2 : Expr}{n1 n2 : Nat}{s : Label -> Nat}
        -> Eval e1 s n1
        -> Eval e2 s n2
        -> Eval (Add e1 e2) s (n1+n2)
    EvalLookup : {l : Label}{s : Label -> Nat}
        -> Eval (Lookup l) s (s l)

A proof of a statement like $\langle 3+4,s \rangle \Downarrow 7$ looks like:

threePlusFourIsSeven : {s : Label -> Nat} -> Eval (Add (Num 3) (Num 4)) s 7
threePlusFourIsSeven = EvalAdd EvalNum EvalNum

Rule induction, which is the topic of section 2.3, is induction over data types like this.

I hope at this point that you can see that the answer to:

  Are the two notations that I have shown (using a pair/tuple and using ⊢) interchangeable in operational semantics?

is "yes, but only because whenever you see such notation it is being or has been defined, and we can use whatever notation we want to mean whatever we want if we define it."  In other words, nothing is stopping us from having used the syntax $s \vdash e \Rightarrow n$ instead of $\langle e, s\rangle \Rightarrow n$. We'd just be defining a relation named $- \vdash - \Rightarrow -$ instead of being named $\langle -,- \rangle \Rightarrow -$.

That said, there are (unwritten) conventions – naming conventions no less – that are commonly abided by.  So $\vdash$ is normally used to separate some "context" or "environment" from "terms".  The tuple notation is often used for state components because we (denotationally) model state as a function from the old state to the output plus the new state.  If we also have input, this results in a function (Input, State) -> (Output, State).  This intuition gets reflected in the naming of the operational semantics, as in, for example, figure 3.6 which includes rules like $\langle \mathtt{skip};C_2, s\rangle \rightarrow \langle C_2, s\rangle$.  Nothing stops us from writing that $s \vdash \mathtt{skip};C_2 \rightarrow s \vdash C_2$, but I think you can agree that that is harder to read.

I got around to posting a blog article that goes into this notation in more detail.


For given set of integers, find and count the pairs with maximum value of bitwise or

If the numbers have width $c\log n$ then there is a randomized $O(n^{2-1/O(\log c)})$ algorithm that finds the maximum OR correctly with high probability. The idea is to find the maximum OR bit by bit, MSB to LSB. We can do this using $c\log n$ queries of the following form: "Is there an OR whose $k$ most significant bits are $b_1\ldots b_k$?". Each such query is equivalent (up to bitwise operations) to the query (applied to a different list): "Is there an OR in which all bits are 1?". Abboud, Williams, and Yu gave a randomized $O(n^{2-1/O(\log c)})$ time algorithm for this problem (which they call Boolean orthogonal detection, flipping 0s and 1s).

If the numbers have unbounded width then (depending on the exact model of computation), there is no $O(n^{2-\epsilon})$ time algorithm (assuming SETH). Indeed, deciding whether the maximum OR is all 1s is the same as Boolean orthogonal detection, for which the aforementioned hardness is known (see for example these lecture notes of Russel Impagliazzo).

Finally, if the numbers have bounded width then there is a simple $O(n)$ algorithm. The algorithm computes the set of numbers appearing in the input, and looks up the answer at a (rather large) table.


In practice, in about 95% of cases, the correct answer is probably going to be: forget about those files, use /dev/urandom or CryptGenRandom() (or equivalent).  They provide very high quality random numbers -- That's what they're designed for.  So this is the most pragmatic answer, and it will provide excellent quality randomness.

Let's say you can't do that, maybe because it's a headless embedded device with no access to entropy, or you want your random numbers to be a repeatable deterministic function of the files.  Then in that case the best answer is likely to be -- guess what? -- hashing.  In particular: concatenate all the files, take the SHA256 hash of the concatenation, and then use that as a key for AES-256-CTR; then use AES-256-CTR to generate as much output as you want.  This is basically using a cryptographic hash to generate a seed for a cryptographic-quality pseudorandom generator, and it satisfies all your requirements.  This is a solid answer, from the perspective of robust engineering and high quality random numbers.

OK, let's say you are a theorist.  If you are a theorist, you won't like the last answer, because it relies upon cryptographic assumptions that have not been mathematically proven to hold.  Pragmatically, you probably shouldn't worry about that -- you rely upon those assumptions every day (e.g., when doing e-commerce or entering your password into a website), and other issues are far more likely to affect you in practice -- but let's say you are a theorist.

From a theoretical perspective, the cryptographic solution is potentially unsatisfying, because it relies upon an unproven assumption, and that is... inelegant.  So, it's interesting to ask what can be achieved that will provably work.  If that's what you're interested in, you'll want to read about randomness extractors.

If you care about pragmatics, randomness extractors are probably not the best possible solution: extractors need stronger assumptions about the distribution of the data in your files, they are more limited in how much random output they can produce, and they are more fragile.  But they do come with provably good properties, and they are mathematically elegant and beautiful.


The complexity of $A^{k \cdot log_{x} (n)}$ is exponential?

This is polynomial complexity, because

$$A^{k \log_x n} = A^{k \lg n / \lg x} = (2^{\lg A})^{k \lg n / \lg x} = (2^{\lg n})^{k \lg A / \lg x} = n^{k \lg A / \lg x}$$

and $k \lg A / \lg x$ is a fixed constant.


Analyzing the time complexity of nested loops

Translating for-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:

$\qquad\displaystyle\begin{align*}
\#\mathrm{Task} \quad&= &&\sum_{i=1}^n \sum_{j=1}^{n^2} \sum_{k=1}^j 1 \\
                     &= && \sum_{i=1}^n \sum_{j=1}^{n^2} j \\
                     &= && \sum_{i=1}^n \frac{n^2(n^2 + 1)}{2} \\
                     &= && \frac{n^3(n^2 + 1)}{2}.
\end{align*}$

We use the closed form of the triangular numbers (which you find on any formulary if you have not memorized it). Finally, obtain a $\Theta$-class using standard tools.


How often can a linear speed sort succeed?

David Eppstein gave away the answer: an $O(n)$ comparison-based algorithm will succeed on a negligible fraction of permutations. One way to see that is that an $O(n)$ algorithm can only take care of $2^{O(n)}$ different input permutations, compared to the $n! = 2^{\Omega(n\log n)}$ possible ones.


Applications of the splittance of a graph/ Turning graphs into splitgraphs

There is nothing deeper to it than what you describe: if the graph is split or it has "small" distance to being split (e.g., you can make it split by removing a small number of edges/vertices), you might be able to devise a polynomial-time algorithm for some otherwise NP-hard problem.
However, it is quite rare such procedures are applied in practice. It can take too much time to decide if the input graph has the desired properties compared to just using a state-of-the-art solver (e.g., integer programming) for the problem you care about. In fact, it is possible these solvers implicitly detect such useful structure and there is no need for this "additional" theoretical analysis.
To summarize, algorithms for split graphs and the kind of situations you describe are mostly theoretical and rarely implemented or used in practice.


Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

The language is actually decidable, but the proof is quite involved, and uses crossing-sequence arguments. See this paper for details.

If you change $200|x|$ to a faster growing function, such as $|x|\log |x|$ (plus some constant), then the language becomes undecidable by standard reduction arguments.


Flajolet-Martin Algorithm : question about use of certain hash functions

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ?

You have the right idea. I believe what the question is trying to suggest is that this hash function has a problem with certain values of $a$ and $b$. Consider, in particular, $a = 16$. What will happen to the hash function in that case? How many possible values are there?

So, to pick a good value of $a$, we should probably make sure that $a = 16$ is not allowed. $a = 8$ is not good either. What do you suggest is a good choice for $a$?


Composition of functions computable in logspace

The idea is quite simple. We are going to simulate running $M_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M_f$ attempts to read from the input tape, we invoke the machine computing $\mathrm{BIT}_g$, which also uses up $O(\log n)$ steps; we know which input $i$ to give, since this is just the location of the head.


Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?

You can do this in $O(n^2)$ time using an advanced version of Earley. See this answer for this advanced version.

This algorithm can parse any $LR(k)$ grammar in linear time. While doing so, it also parses all prefixes of the string (if no lookahead is used - for lookahead you would need to also perform actions that would be performed at end-of-string tokens) and puts 'I am finished' items in item sets whose index corresponds to an index in the string at which a prefix was recognized to be in the language.

We can therefore start this algorithm at every position in the string, parsing the remainder of the string, for a total running time of $O(n^2)$. As we can have $O(n^2)$ matches, this is in a sense optimal.

You could also change the algorithm and run it once: you can insert an 'I've started here' item at every index, and then parse the string running the Early version only once. This may be faster in practice, but I'm not sure what its running time would be.

Note that recovering a parse forest from an Earley parse is not the simplest thing in parsing. The above algorithm probably needs augmenting if you also want all the parses of the substrings (rather than just what substrings match). Note that on grammars that are not $LR(\pi)$ for some regular partition $\pi$ (which includes all $LR(k)$ languages), the above algorithm may not run in quadratic time.


Approximating all independent sets of size k in a graph

In general, the maximum independent set problem cannot be approximated to within a constant factor in polynomial time unless $P = NP$. You can do better, however, if you restrict yourself to special graph classes. For example, in interval graphs, the maximum independent set problem can be solved in polynomial time. As another example, in planar graphs, the maximum independent set problem can be approximated to within any ratio $r < 1$ in polynomial time.

There is a lot more information provided here: https://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-tim
http://www.graphclasses.org/classes/problem_Independent_set.html

If you're interested in actual implementations, the Wikipedia page has a few references: https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Software_for_searching_maximum_independent_set


Your goal is to “prove”  --I'm using bullets “•” for syntactic separators--
$$ ∀x \;•\;\; ∃y \;•\;\; y² ≤ x < (y+1)²$$

Proof Methods

In the natural deduction style, one proves “∀ x : ℕ • P x” by proving
two statements:

Base case      :: P 0
Inductive step :: P a ⇒ P (S a) , for a : ℕ and S successor function

Where, in this case,
$$P x \;\;≡\;\; ∃y \;•\; y² ≤ x < (y+1)²$$

In the constructive fashion, one proves “∃ y • Q x” by
actually finding such a $y$ using whatever data is available.

Base case

For the [base] case the input x is 0, and we need to find
some $y$ with $y² ≤ x < (y+1)²$. Clearly $y = 0$ works as shown
in the proof your posted.

Inductive step

For the [inductive] case where the input x is of the shape S a,
we need to find a $y$ with $y² ≤ S a < (y+1)²$, (*).

However, we have the assumption $P a$ which gives us a $b$ with
$b² ≤ a < (b+1)²$ --which looks really close to the goal (*).
To reach our goal (*), let's do the simplest thing possible:
replace $a$ with $S a$ in (1) thereby obtaining
$b² ≤ S a < (b + 1)²$. Because of (1), and the transitivity of ≤,
the left part is true and the whole thing reduces to:
$$S a < (b + 1)²$$
So if this is true, then we are done and the answer is $b$.
If it is not true, then we must have it complement:
$$(b + 1)² ≤ S a$$

But from (1) we also have $a < (b + 1)² = b² + 2b + 1$
thus we obtain $S a = a + 1 < (b² + 2b + 1) + 1 ≤ b² + 4b + 2 = ((b + 1) + 1)²$
Hence, we have found that $(b + 1)² ≤ S a < ((b + 1) + 1)²$
and so we may take the output $y$ to be $b + 1$ for our goal (*).

Curry-Howard: Proving ≅ Programming

The above was a proof [sketch] which corresponds to the a program.

A proof of $$∀ x : ℕ • ∃ y : ℕ • R(x, y)$$
corresponds to the program

-- Output y = prog x satisfies relationship R(x, y), for all input x.
prog :: Int → Int
prog 0  = “the y found in the base case of the proof”
prog n  = “the y found in the inductive step,
             along with any conditionals and recursive calls”

Applying this to our above proof yields,

prog :: Int → Int
prog 0 = 0
prog n = let a = n - 1 ; b = prog a
         in
           if   a + 1 <= (b + 1) * (b + 1)
           then b
           else b + 1

Hope that helps :-)


Which languages do Perl-compatible regular expressions recognize?

I've also found this blog post extremely interesting http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html. It provides the very same proof I gave before about the fact that regexps recognizes the CFLs (by rewriting the grammar through DEFINE blocks), and even some CSLs (like the language of repeated strings); it builds on that and goes on, giving a proof that regexps with backreferences are NP-hard (by reducing 3-SAT to a regexp).


regular expression: sum of positive fixed point decimal numbers

The idea is to identify the different kind of subexpression you have, and the regular expression should write itself.

Here you have a non-empty sum of decimal numbers, so the "outside shape" is $E=N(+N)^*$, where N is an expression for decimal numbers, and "+" is the symbol for addition.
Now we just have to detail N: it is a non-empty sequence of digits, with possibly one dot, which does not start with $0$ and does not end with $0$ if there is a dot.
For short let write D=0+1+2+...+9 the expression for 1 digit. here the "+" is the one from regular expression, meaning Union, not the addition symbol.
Also, the first digit should not be 0, and if there is a point, the last one should not be 0. So let's P=1+2+...+9 the expression for nonzero digits

We are now ready to write N:
N=PD*+PD*.D*P+0.D*P
It means that either we don't have a dot, and then we can end with 0, or we have a dot, and then we cannot ened with 0. There is also a special case for numbers like $0.345$.

By substituting the letters with their explicit expressions, you get the full explicit one for E.


How to remember NFA's choice on a certain computation?

Hint: Let the input be $x_1,\ldots,x_n$. As you mention, it is easy to compute the left-associative product $L_n$ "as you go": $L_{m+1} = L_m x_{m+1}$. The right-associative product recurrence has the wrong direction: $R_m = x_{m+1} R_{m+1}$. To cope with that, at each step you have to guess the value of $R_{m+1}$; it needs to be a value which conforms to your earlier guess of $R_m$ and to the value of $x_{m+1}$. At the end, compare your initial guess of $R_1$ to the value of $L_n$. Arrange things so that you only need to keep track of finitely many values of products.


Genetic Algorithms - Tournament Selection

A simple version of tournament selection is as follows.

  Select $k$ random Individuals from the population.
  Select the best Individual from the $k$ Individuals.
  Repeat from 1 until you have selected the desired amount of Individuals.

As an example. Consider your data, $k=3$ and that we wish to select 3 Individuals.

$[12,2,3,99,73,32,53,8]$ (your data).

$[12,2,99]$ (3 random Individuals).
$99$ is the best Individual.

$[2,73,53]$ (3 random Individuals).
$73$ is the best Individual.

$[99,8,53]$ (3 random Individuals).
$99$ is the best Individual.

We have selected the Individuals $73,99$ and $99$.

Note that we have selected $99$ twice.
If this is not desired, you can delete an Individual from the population if it has been selected.

It is also possible, instead of always selecting the best Individual, to select an Individual according to some stochastic scheme. For example, assign the best Individual from the tournament pool (the $k$ randomly selected individuals)  $i=0$, the second best $i=1$, ... (etc), and the worst Individual $i=k-1$. Then Individual $i$ is selected with chance $\frac{2(k-i)}{k(k+1)}$.

I just made this stochastic scheme up. You can use your fantasy on how to extend/alter tournament selection or any other genetic operator :)


Lower bound on competitive ratio of $m$-machine scheduling

Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the maximum is at least 2 instead of the optimum 1). This case gives an average competitive ratio of at least $p \cdot 1 + (1-p) \cdot 2 = 2-p$.

Consider next the sequence $m \times 1, 2$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 3/2, since the maximum is 3 while the optimum is 2. If it doesn't schedule the 1's in different machines, we use the trivial bound on the competitive ratio. This case gives an average competitive ratio of at least $p \cdot (3/2) + (1-p) \cdot 1 = 1 + p/2$.

We conclude that the competitive ratio is at least $\max(2-p,1+p/2)$. If $p \leq 2/3$ then $2-p \geq 4/3$, whereas if $p \geq 2/3$ then $1+p/2 \geq 4/3$, and so whatever the value of $p$, we get that the competitive ratio must be at least $4/3$.


Regarding programming languages, what is meant by "hook"?

Typically, a hook is an non-abstract method defined in an abstract class, that can be optionally implemented and overridden in subclasses to modify behaviour. I think this is best exemplified in the template method pattern, where the (abstract) superclass defines the overall semantics for a process, but leaves primitive operations to be implemented by sublasses:

A template method is defined inside an abstract class:

public abstract class AbstractLogger {

    /*
     * Template method, made final to make
     * sure the flow is not modified by subclasses
     */
    public final void logMessage(String msg) {
        msg = preProcess(msg);
        writeToLog(msg);
    }

    /*
     * Abstract primitive operation that must be
     * implemented by subclasses
     */
    protected abstract void writeToLog(String str);

    /*
     * Hook method that can be optionally overriden to
     * modify the template method's behaviour
     */
    protected String preProcess(String str) {
        return str; // default behaviour: do nothing
    }

}

Concrete subclasses make use of the hook-method to augment behaviour:

public abstract class TerminalLogger extends AbstractLogger {

    /*
     * This primitive operation must be implemented
     */
    protected void writeToLog(String str) {
        System.out.println(str);
    }

    /*
     * Override super.preProcess() to modify behaviour
     * of the template method
     */
    protected String preProcess(String str) {
        return str.toLowerCase();
    }
}

Pardon the contrived example - I hope it illustrates the point clearly enough.
For more info on hook methods and template methods see:

http://en.wikipedia.org/wiki/Hook_method#Hook_methods

http://en.wikipedia.org/wiki/Template_method_pattern

The template method pattern wiki presents a fuller example than mine - you might want to check it out.


GPUs are bad at doing one thing at a time.  A modern high-end GPU may have several thousand cores, but these are organized into SIMD blocks of 16 or 32.  If you want to compute 2+2, you might have 32 cores each compute an addition operation, and then discard 31 of the results.

GPUs are bad at doing individual things fast.  GPUs only recently topped the one-gigahertz mark, something that CPUs did more than twenty years ago.  If your task involves doing many things to one piece of data, rather than one thing to many pieces of data, a CPU is far better.

GPUs are bad at dealing with data non-locality.  The hardware is optimized for working on contiguous blocks of data.  If your task involves picking up individual pieces of data scattered around your data set, the GPU's incredible memory bandwidth is mostly wasted.


How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more

A* isn't based on the GRAPH-SEARCH algorithm but on the UNIFORM-COST-SEARCH one:

function UNIFORM-COST-SEARCH(problem) returns a solution or failure
   node ← a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
   frontier ← a priority queue ordered by PATH-COST,
              with node as the only element
   explored ← an empty set

   loop do
     if EMPTY?(frontier) then return failure

     node ← POP(frontier)  /* chooses the lowest-cost node in frontier */
     if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)

     add node.STATE to explored
     for each action in problem.ACTIONS(node.STATE) do
         child ← CHILD-NODE(problem, node, action)
         if child.STATE is not in explored or frontier then
             frontier ← insert(child, frontier)
         else if child.STATE is in frontier with higher PATH-COST then
             replace that frontier node with child

Uniform cost search algorithm is identical to the general graph search algorithm (in your question) except:

for the use of a priority queue and
the addition of en extra check in case a shorter path to a frontier state is discovered.

A* is identical to UNIFORM-COST-SEARCH except that uses $g + h$ instead of $g$.

So assuming the following distances (straight-line distance to Bucharest) for the h heuristic function:

Sibiu          253     Fagaras 176
Rimnicu Vilcea 193     Pitesti 100
Bucharest        0

the second path will NOT be omitted. Stages in an A* search for Bucharest  are (numbers show $f = g + h$):

(a) Sibiu 0 + 253 = 253
(b) Fagaras = 99 + 176 = 275, Rimnicu Vilcea = 80 + 193 = 273
(c) Pitesti = 177 + 100 = 277
(d) Bucharest (via Fagaras) = 310 + 0 = 310

A* search keeps going, choosing Pitesti for expansion:

(e) Bucharest (via Pitesti) = 278 + 0 = 278


Find position in array where element-wise multiplication with string of 1 and 0s results in max value

Let the array consist of the numbers $a_0,\ldots,a_{n-1}$, and let the mask be $b_0,\ldots,b_{k-1}$. Define
$$
A = \sum_i a_i x^i, \quad
B = \sum_j b_j x^{k-1-j}.
$$
Notice that
$$
AB = \sum_{i,j} a_i b_j x^{i+k-1-j},
$$
and so the coefficient of $x^{i+k-1}$ in $AB$ is
$$
\sum_{j=i}^{i+k-1} a_j b_{j-i}.
$$
Therefore if you can calculate $AB$, you can solve your problem.
You can calculate $AB$ in $O(n\log n)$ using FFT.


How to argue about semi-decidability of a problem?

We know that $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ have the same cardinality, so there exists a bijection $f:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$. Let $s_n$ be the $n$-th string in some enumeration, like $s_1=\epsilon, s_2=0, s_3=1, s_4=00, s_5=01,\dotsc$ then consider the following semi-decider, where I leave it to you to fill in the missing parts:
$$\begin{align}
&\Pi'(\Pi_1, \Pi_2)=\\
&\quad\text{for }n=1,2,3,\dotsc\\
&\quad\quad\text{compute }f(n)=(i,j)\\
&\quad\quad\text{run }\Pi_1(s_i)\\
&\quad\quad\text{run }\Pi_2(j)\\
&\quad\quad\text{... }\\
&\quad\quad\text{... }\\
&\quad\quad\quad\text{return accept}
\end{align}$$

There are lots of bijections between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, here are a few to get you started.


How to determine if an automata (DFA) accepts an infinite or finite language?

This is well enough known that you should be able to find it in most intro theory texts:

Theorem. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of length $k$, where $n\le k < 2n$.

This makes the decision problem simple: just try all strings of length at least $n$ and less than $2n$ and answer "yes" if $M$ accepts one of them and "no" if there's no string in that range that's accepted.


Reduction: Vertex Cover to Binary Integer Program (Decision Problem)

Vertex Cover (Decision Version):

Given a graph $G=(V,E)$ and a positive integer $K$. The decision vertex cover problem asks: Does $G$ contains a vertex cover of size $K$ or less?

Binary Program (Decision Version):

Given a matrix $\mathbf{A}$ of size $m\times n$, a vector $\mathbf{b}$ of size $m$ and a positive integer $L$. Define the decision version of Binary Program as: Is there a vector $\mathbf{x}\in\{0,1\}^n$ of $L$ nonzeros or less such that $\mathbf{A}\mathbf{x}\geqslant\mathbf{b}.$

You could write the optimization version of vertex cover as a Binary Program as follows: Let $x_v$ be a binary variable that is equal $1$ if vertex $v$ is selected, and, $0$, otherwise.

\begin{align}
    & \text{minimize}
    & & \sum_{v \in V} x_v\\
    & \text{subject to}
    & & x_u+x_v\geq 1 \text{ for all } \{u,v\} \in E\\
    & & & x_{ v }\in\{0, 1\}, \forall v\in V.
\end{align}

You can easily check that this Binary Program indeed finds a vertex cover of minimum size.

Now, just set $L=K$, $m=|E|$, $n=|V|$, the vector $\mathbf{b}=[1,1,\ldots,1]^\top$ and the matrix $\mathbf{A}=[a_{ev}]_{\forall\,e\in E,v\in V}$ as

$$a_{ev}=\begin{cases}1,\text{ if } v\in e\\0, \text{ otherwise}\end{cases}$$

This is, cearly, a polynomial-reduction from Vertex Cover to Binary Program.


Your confusion appears to arise from a misunderstanding: $O(\log n)$ means "proportional to $\log n$ or better". So being able to get the closest pair in constant time is not a problem.

While you seem to already have found a solution to the original problem, I'll still give hints towards a solution, in order to make this answer helpful for other people stuck with that problem.

Hint 1: Basic data structure to start from: (Contrary to the claim in the current version of the question, a sorted array does not work, since you can not insert or delete in an array in $O(\log n)$.)

   A height balanced binary search tree (e.g. AVL tree) works.

Hint 2: What additional information should be stored:

   Each node stores: the smallest and largest value in the subtree below this node and the  closest pair in that subtree.

Hint 3: How to update the information in a single node:

    The smallest value is the smallest value in the left subtree (or the value of the node itself, if no left subtree is present).
 The largest value is the largest value in the right subtree (or the value of the node itself, if no right subtree is present).
 There is no closest pair in a leaf.
 In an inner node there are at most 4 candidates for the closest pair:
 The closest pair in the left subtree,
 the closest pair in the right subtree,
 the pair (largest value in the left subtree, value of the node) and
 the pair (value of the node, smallest value in the right subtree).
 Simply compute minimum of these.

Finally: How to do the operations:

    $\text{search}$ just ignores the additional information.
  $\text{closest_pair}$ reads the required information from the root node.
  $\text{insert}$:
  1. perform a normal AVL-insert
  2. update all nodes on the path from the inserted leaf to the root and all nodes affected by rotations (starting at the leaf)
  $\text{delete}$:
  1. perform a normal AVL-delete
  2. update all nodes on the path from the deleted leaf to the root and all nodes affected by rotations (starting at the leaf)

 If the descent into the tree in insert and delete is done via recursion, the updates can --just as the rotations -- be done when returning from the recursive calls.
 Of course, once a node is unchanged, the nodes above it will remain unchanged as well (unless affected by a rotation).


Since programs are swapped from backing store to main memory why don't they get lost when the computer is suddenly turned off?


Can all permutations of a set or string be generated in O(n log n) time?

You have misinterpreted the SO question itself (or we have misinterpreted yours, which seems more likely). That SO quesiton is talking about generating a 'next' permutation from a previous given one, so that all permutations can be generated by calling 'next' multiple times.

The answer to that is talking about the (amortized) time complexity of the C++ implementation std::next_permutation which I believe uses Narayana Pandita's algorithm, and generates them in lexicographic order.

(Also, as an aside: permutations are different from combinations. There are $n!$ permutations, but $2^n$ combinations (subsets). You seem to be under the impression that permutation is same as a combination (based on your claim of $O(2^n)$)).

To get back to the original question, another way to look at the question: would using next_permutation to generate all the $n!$ permutations in lexicographic order be $\Theta(n!)$ or $\Theta(n\times n!)$?

While there are some wrong statements in the answer you linked, it does state the right answer: It is $\Theta(n!)$, i.e. the amortized time complexity of next_permutation is indeed $O(1)$.

This can be proven as follows:

If $T(n)$ is the time taken to generate all the $n!$ permutations using next_permutation then we have that

$$T(n) = n T(n-1) + O(n^2)$$

(You fix the first number $n$ times and generate the permutations for the rest, and pay $O(n)$ cost when the first number is switched.)

Let $G(n) = \dfrac{T(n)}{n!}$. Note that we are looking the the asymptotics of $G(n)$. We get

$$G(n) \le G(n-1) + \frac{cn^2}{n!}$$

This is a simple telescoping sum, and since $\sum_{n=1}^{\infty} \frac{n^2}{n!}$ is convergent, we get that

$$G(n) = O(1)$$

Note that you could have changed the recursion to

$$T(n) = nT(n-1) + O(n^k)$$

and still have gotten $O(1)$ amortized per permutation.


What is the name of this type of function composition?

You composition is of type $\operatorname{comp}:(A \to X \to C)\to (B \to X) \to (A\to B \to C)$. Up to Currying, it can be seen as being of type $(A  \times X \to C)\to (B \to X) \to (A\times B \to C)$. So it's just a composition of a two arguments functions with a one argument function. You take $f$ and $g$ and return $(a,b)\mapsto f(a,g(b))$.

From a general abstract nonsense point of view, you can define the functor $$A\times -:\begin{array}{lll}
O & \mapsto &A\times O\\
g : B \to X&\mapsto &<\operatorname{id}_A;g>:A\times B \to A\times X
\end{array}$$
and then your composition is just $\operatorname{comp}=f\mapsto g \mapsto f\circ (A\times  g)$.


What is the relation between the formal definition of strictness and its intuitive notion

The intuition: if executing f(x) causes x to be evaluated, and evaluating x doesn't terminate, then this will cause f(x) to fail to terminate (because evaluating x doesn't terminate, so the execution of f(x) never completes).

So, if executing f(x) always causes x to be executed, then f will be strict by the formal definition above.  That's why "f(x) completely evaluates x" implies "f(x) evaluates to bottom for all x that evaluate to bottom".

In contrast, with a lazy function, evaluating f(x) doesn't necessarily trigger evaluation of x, so it doesn't necessarily terminate (even if evaluating x wouldn't terminate).  Thus, for a function that is intuitively lazy, it won't meet the formal definition of strict.


It's not, since there can be exponentially many such walks.

The $((2 \cdot n)+1)$ by $((2 \cdot n)+1)$ grid graph will have at least $2^n$  such paths for $k = (2\cdot n \cdot n)+(4 \cdot n)+1$, since paths can go along two sides of the grid, in from both ends of that, then connect both ends of that in a way which encloses exactly two squares of each of the $n$ non-overlapping 2-by-2 blocks on the diagonal between those ends.

However, there are at least 8 weaker versions of what you're asking about.

Enumerating them in poly(input_size, number_of_such_paths) time.
Enumerating them in poly(input_size) $\cdot$ number_of_such_paths time.
Enumerating them with polynomial delay.
Doing one of the previous three while using only poly(input_size) space.
Computing number_of_such_paths and a bijection from {0,1,2,3,...,number_of_such_paths-1} to the set of such paths.
Doing the previous thing and computing the inverse of the bijection.

I don't know anything about whether or not any of those are doable in polynomial time.


Crossover operator in genetic algorithms in Neural Networks

I don't think you should.

But, supposing the structure is the same in all individuals, you could take a random set of nodes from one, and the rest from the other, and just keep all out edges from nodes you selected.

Another alternative is taking a random set of edges from one, and the rest from the other.

A third alternative is to take the first $\ell$ layers from the first individual and the last $L-\ell$ layers from the second individual.

As you can see, there are very many approaches, and I don't think any of them will be satisfactory, but I hope you try and see for yourself.


Concise way to say "increases with n or some term of n"

"Presumably the complexity of each new connection is an increasing function of the number of rules."

But you don't mean complexity. Problems have complexity, algorithms have running time (or, more generally, resource usage), functions have growth rate.


Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)

To generalize your approach to $k$-subsets of an $n$-set, you would need to build a hypergraph. Ordinary graph edges are relations between pairs of vertices. Hypergraphs allow relations between arbitrary sets of vertices. They are extremely general objects, essentially representing families of sets.
This question provides two good answers for how to (reasonably) efficiently enumerate these subsets. The first uses bit magic and is a special case when $n$ is small enough. The second takes a recursive approach which saves having to compute the first $k-1$ elements of a $k$ subset multiple times, but only really helps if enumerating over several consecutive values of $k$.


You enforce the property of having an equal number of characters to the left and the right by only having rules that add an equal number of characters.

At the moment, your approach is essentially, "Start with $kyyk$ and add stuff to the left and the right." In this  case, "stuff" is the non-terminal symbols $K$ and $Q$, each of which can expand to any string in $\Sigma^*$. Whenever you're expanding two non-terminals in a context-free language, they're expanded completely independently, so there's no way to control their interaction, e.g., to require that both strings have the same length.  This means that the approach of generating the left-stuff and right-stuff from two  non-terminal symbols can't work.

Instead, you need to take the opposite approach. Start with nothing and simultaneously expand the stuff on the left and right.


Consequences of factoring and discrete log in $P/Poly$

There appear to be pretty much no interesting consequences, from a complexity-theoretic perspective.  See Consequences of Factoring being in P? on CSTheory.  (Any consequence of factoring being in P/poly would also be a consequence of factoring being in P; but as the answers to that question state, there are basically no known complexity-theoretic consequences to factoring being in P.)

A Google search for "consequences of factoring in P/poly" also turns up Factoring Could be Easy.


Identification and the definition of data type

Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?

Yes. You can have a strongly typed language that completely infers types, where the program at no point refers to the types, at all, ever.

For example, you could write programs in Hindley Milner (without the gamut of extensions you see in something like Haskell) without ever referring to a type. You shouldn't, but you could.

Types and values are usually separate in non-dependently typed programs, and if your system allows for full type reconstruction, you don't need to refer to them in your code.

  Are there any programming languages that don't use named types?

Doubtful. When you use an integer but the program expects a boolean, the compiler has to tell you something. So it's going to want to give a name to those types.

Without primitive types, you can't do much useful in a programming language, so you're going to want to at least give your primitive types names.

Also, having all sum-types be anonymous would be extremely tedious. You could refer to the List type as T . T = Nil + Cons T, and occasionally you will see something like this on paper, but this is going to get hard to use very fast. As you can see, recursive types are particularly awkward in this scheme, and you usually end up needing the type-level equivalent of the $Y$-combinator.

Now, if you use things like Church encoding, you can get away without having primitive types, where everything is probably going to be higher-rank polymorphic types. For example, you can encode natural numbers as  forall a . (a -> a) -> a -> a. But again, this is something more useful on paper than in the hands of a programmer.

  And, if so, what implications, if any, are there of this?

None that I can think of, other than the lack of nominal typing, and you could even fake nominal typing by attaching some singleton type to your values.

For example, ((), forall a . (a -> a) -> a -> a) is isomorphic to forall a . (a -> a) -> a -> a, but now you have two isomorphic types the system considers distinct.


First let $\Sigma = \{a,b\}$.

Assuming that you're taking a strict approach, there has to be a transition from every state for every symbol in the alphabet, then you have only two possible DFAs (that accept $\emptyset$ and $\Sigma^{\ast}$ respectively).

If you allow a partial transition function, where missing transitions imply rejection (note that this can still be interpreted deterministically), then there are five different languages that can be accepted (strictly there's seven automata): $\emptyset$, $\{\varepsilon\}$, $a^{\ast}$, $b^{\ast}$ and $\Sigma^{\ast}$.

With a larger alphabet, in the partial function case, you get more of course. With $|\Sigma| = n$ there are $2^{n} + 1$ possible languages, from $2^{n+1}$ different automata (half produce the same language). You get $2^{n}$ from each possible choice of which symbols will have a transition in the case where the state is accepting, and the $+ 1$ from the case where the state is non-accepting (it doesn't matter what transitions you have then, the languages are all $\emptyset$).


Time-space tradeoff for missing element problem

This can be done in $O(n \log n)$ word operations and $O(1)$ words of memory (respectively $O(n \log^2 n)$ time and $O(\log n)$ memory in bit-level RAM model). Indeed, the solution will be based on the following observation.

Say there are $n_0$ even and $n_1$ odd numbers in range $[1, n + 1]$ (so $n_0 \approx n_1$ and $n_0 + n_1 = n + 1$). Then there is $b \in \{0, 1\}$ such that there are at most $n_b - 1$ values with parity $b$ in the input. Indeed, otherwise there are at least $n_0$ even and at least $n_1$ odd values in the input, meaning that there are at least $n_0 + n_1 = n + 1$ values in the input, contradiction (there are only $n$ of them). It means that we can continue searching for missing number only among the odd or even numbers only. The same algorithm can be applied to higher bits of binary notation as well.

So our algorithm will look like that:

Suppose that we already now that there are only $x$ values in the input with remainder modulo $2^b$ being equal to $r \in [0, 2^b)$ but there are at least $x + 1$ numbers in range $[1, n + 1]$ that have remainder $r$ modulo $2^b$ (at the start we know
that for sure for $b = 0, r = 0$).
Say there are $x_0$ values in the input with remainder $r$ modulo $2^{b + 1}$ and $x_1$ values in the input with remainder $r + 2^b$ modulo $2^{b + 1}$ (we can find these numbers in a single pass through the input). Clearly, $x_0 + x_1 = x$. Moreover, because there are at least $x + 1$ numbers in the input with remainder $r$ modulo $2^b$, at least one of the pairs $(r, b + 1), (r + 2^b, b + 1)$ satisfies the requirements of the step $1$.
We have found the missing number when $2^b \geqslant n + 1$: there is only one number in range $[1, n + 1]$ that may have remainder $r$ modulo $2^b$ ($r$ itself if it is in range), so there are at most zero values in the input that have such remainder. So $r$ is indeed missing.

Clearly, the algorithm halts in $O(\log n)$ steps, each of them needs $O(n)$ time (single pass over the input array). Moreover, only $O(1)$ words of memory are required.


Are you allowed to have empty states on Turing machine?

The output and transition functions have to be defined for all state and character combinations. But if you say you can't get into the state, it means that if you do get there, the input was invalid. Therefore simply append a definition like "and all transitions not mentioned so far are to a rejecting state" (which is an endless loop if you are doing a stop/don't stop machine).


Conway's Game Of Life Problem Parallel (OpenMP)

There is a simple solution.  Instead of storing a hashmap of all positions, store the set of only the positions that are currently alive.  Live cells are included in the set; dead cells are not.  When you want to know whether a particular cell is alive or not, look up that position in the set; if it is found, then the cell is alive, otherwise the cell is dead.  You can store the set as a hashtable.

You said that you expect only about O(size^2) cells to be alive.  My proposal reduces the space complexity to O(size^2), instead of O(size^3).  Also, the running time to check whether a particular cell is alive will be O(1).  The running time to enumerate all live cells will be O(size^2).

It follows that the running time to compute the next state of the world will be O(size^2).  Since each cell has only 4 neighbors, you only need to enumerate O(5 * size^2) = O(size^2) many cells (all of the live cells and their neighbors) to see which will be alive in the next iteration.  To tell whether a cell will be alive in the next iteration can be done by examining its state and the state of its 4 neighbors, which can be done in O(1) time.

This approach should also generalize nicely to a parallel/distributed implementation.

This all assumes that the number of live cells is limited to O(size^2) for all iterations.  That might be a dubious assumption in practice: the number of live cells can quickly grow to O(size^3), for some initial configurations (in particular, it might take only O(lg size) iterations to go from O(size^2) to O(size^3) live cells).


Finite representations and programming languages Countably inifite

Here is a simpler situation highlighting the difference. The set of finite binary strings is countable. The set of infinite binary strings is uncountable.

Another example: the set of numbers with finite decimal expansion is countable. The set of numbers with infinite decimal expansion is uncountable.

The reason that the number of languages is uncountable is that you have infinitely many choices: for each word, you can decide whether it's in the language or not. That's why it's like that infinite binary string considered above.


Converting sets into regular expressions

We don't quite convert a set to a regular expression. Rather, we give a regular expression for a language (i.e., a regular expression which defines the same language). For example, a regular expression for the language $\{01,10\}$ is $01+10$, and a regular expression for the language $\{abb,a,b,bba\}$ is $a+b+abb+bba$. There can be other regular expressions. For example, another regular expression for the second language is $a(\epsilon+bb) + b(\epsilon+ba)$.

Regarding the syntax of regular expressions, this should be explained in your book.


Greedy proof: Correctness versus optimality

You can use whatever proof method you want. Proofs aren't even limited to existing patterns such as "greedy stay ahead" and "swapping". Indeed, in some cases, such as the greedy algorithm for maximizing a submodular function over a uniform matroid, the proof consists of adding together a bunch of inequalities expressing the fact that the random choice was (greedily) optimal.

Usually the proof that a greedy algorithm works compares itself against an optimal solution, though when proving approximation guarantees, it could be enough to compare the greedy solution to the theoretical maximum (a case in point is the derandomized version of the random 3SAT algorithm).

Also, I suspect that "correctness" and "optimality" mean the same thing.


Is this a misleading or undesirable implementation of a hash map?

As others have indicated, this code example doesn't do resizing, and this is an important part of a "real" dynamic hash table. Whether or not it's "bad" depends on what it's trying to achieve as an example, but it's certainly not code that you should deploy.

Linear probing isn't necessarily a bad idea. After all, it has excellent locality. But since you asked about a specific scenario, let's explore that. The scenario is where you have two keys, k1 and k2, which have the same hash value h, and a third, k3, with the hash value h+1.

Most hash table designs rely on the premise that the hash function is "good". If you have a "good" hash function, this should be a difficult scenario to engineer on purpose, but it's still possible that it happens with high enough probability just by virtue of storing a lot of entries in the hash table.

Consider an open addressing hash table with $m$ slots and $n$ elements in it. Denote the load factor by $\lambda = \frac{n}{m}$. Then if the hash function is "good", and $m$ and $n$ are large enough, the probability that a given slot has $k$ elements that would "naturally" hash to that slot is given by the Poisson distribution:

$$P(k; \lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$$

So the probability that a given slot has at least 2 elements is:

$$P_1 = 1 - P(0; \lambda) - P(1; \lambda)$$

And the probability that the very next slot has at least 1 element is:

$$P_2 = 1 - P(0; \lambda)$$

The probability of this scenario occurring to a given hash slot is:

$$P_1 P_2 = 1 - e^{-\lambda} (\lambda + 2) + e^{-2\lambda} (\lambda + 1)$$

...and so on. Multiply this by $m$ to give the expected number of times this scenario happens for any $m$ and $n$.

(Exercise: Suppose that you have $m$ pigeonholes and $n$ pigeons, and you assign pigeons to pigeonholes randomly and $m$ is large enough. Then the proportion of pigeonholes with $k$ pigeons assigned follows a Poisson distribution. Show that the expected number of "pigeon collisions" is $\frac{1}{2}$ when $n = \sqrt{m}$.)

Remember, though, that short probes aren't necessarily a problem. What you're trying to avoid is long probes. Specifically, you're trying to ensure that the maximum probe length, that is, the largest distance that an entry is from its "home", is small. This number gives the maximum "work" that you may have to do to look for an entry.

In open addressing, it is common practice to keep track of this maximum probe length, and update it when a new element is inserted. This number is used for (at least!) two purposes: to decide when to stop searching, and to decide when to resize the table.


What are the meanings of metalanguage and metasyntax and EBNF?

In general, informally, a metalanguage is a language used to talk
about a language, possibly to specify it or to study its properties.

For example, linguists use English to describe the English
language. As a consequence English is used as its own metalanguage.
To avoid confusion, various quoting system are used to distinguish the
two level. For example, when talking about a small animal that barks,
we use the word "dog". Here, "dog" represent a word of a language
being talked about, not any of the possible meanings of that word in
the language it belongs to. It cannot bite.

When a language A is used as metalanguage to talk about a language B,
B is called the object language. But, though sometimes used in a
formal way, this is very similar to saying that wheather is the object
of many conversations.

In computer science, a well known example is the programming language
ML. The name ML actually stand for metalanguage. ML was initially
conceived by Robin Milner as a metalanguage to develop proofs about a small language
called pplambda in the LCF theorem prover. Hence, both syntactic and
semantic properties of pplambda can be expressed in ML.

Another well known example is Lisp, a language that is its own meta
language, and has been the first programming language to have that property. Lisp programs can be syntactically represented as a Lisp
data structure. The semantics of Lisp is also expressed in Lisp, since
the first Lisp interpreter was written in Lisp.

This works so well that the feat has since be often repeated for many other
programming languages, and it is very customary to write the first
compiler of a language in the
language itself, as part of a language bootstrapping process. Hence
the language is self compiling. This requires defining both the syntax
and the semantics of the language in itself.

So, in effect, most programming languages are, or can be, a
metalanguage for themselves, and for other programming languages.
That is actually the least one can expect from languages that often
claim to have Turing power.

The concept of metalanguage often concerns a conplete object language,
whether natural language or programming language, with syntax and semantics. But it can also
concern languages in the formal language sense, which are only syntax.  A mathematical
formalism used to describe (a family of) formal languages (regular
sets, context-free, recursively enumerable, ...) is a metalanguage for
this formal language.

This is more interesting when the syntax of the metalanguage belongs to the same language
family as the formal languages it describes.  The best known example is the
BNF language (Backus-Naur Form), and its later EBNF variant. It is a
language used to write context-free (CF) grammars, thus to define
purely syntactic languages. Its own syntax is context-free, hence
describable in BNF.  Hence BNF can be syntactically its own metalanguage,
but not semantically.  But then, BNF describes only CF languages and
has no claim for Turing power.

It is to be noted that BNF has a CF syntax, but it also has
semantics. The semantics of a BNF program is precisely a CF grammar and the formal language it defines,
to which the BNF program associates no semantics. A context-free
grammar just defines a formal language, and no semantics is
associated. Hence it is wrong to consider that BNF is a CF
grammar.  BNF has a CF grammar which defines its syntax.

Answering your questions

Regarding the two preliminary quotes. They are expressed in the
context of formal systems, and "formal" means mathematically defined,
which may include both syntax and semantics for the language. It does
not contradict the above discussion, but rather confirms it.

A formal grammar of a formal language is not a metalanguage of
the formal language. The mathematical formalism used to write the
grammar is in this case the metalanguage.

The quote goes into an issue that I did not address here, that of the
structure that a syntax definition can attach to the strings of a
formal language. It is, as far as I see, quite unrelated to the
concept of metalanguage, when we talk of formal languages in the
formal language theory sense. Two different syntactic definitions can
produce the same language, when considering only the string it
defines for the language. But these definitions implicitly associate
diffrerent structures with the string (such as parse-trees in the context-free
case) and that can be important.

When the formal language is actually the syntax of a complete
language that also has semantics, the structure is important as it is
usually organizing the definition of the semantics, which is the
purpose of many metalanguages.
As written above, a context-free grammar cannot be a metalanguage
since it has no semantics. The formalism used to write the CF grammar
is a metalanguage for the purely syntactic formal language defined by
this CF grammar. EBNF is a language with both syntax and semantics.
A program  (or whatever you want to call it: text, description,
grammar, ...) written in EBNF is a text using the syntax of
EBNF. This text has a meaning, defined by the semantics of EBNF,
which is the CF grammar it describes. EBNF is not a metasyntax, but a
meta language for syntax.

This calls for more precision. I consider that the word metasyntax is
just shorthand for the expression "syntax of [a/the] metalanguage". I
do not ses what other meaning it could have.

The first quote is just nonsense to me. The second quote is poorly
phrased and should rather be (if I understand the intent):

  Extended Backus-Naur Form (EBNF) is a family of metalanguages for
  defining syntax, any of which can be used to express a context-free
  grammar.

The quote (out of its context) is in agreement with what I said so
far. The expression "formal metalanguage" is not to be understood as
formal language in the formal language theory sense, but as a
language with a formally, i.e., mathematically, defined syntax and
semantics.

This quote alone just say that EBNF is a widely used metalanguage for
computer languages, but without being more precise about it.
Actually, according to me, EBNF is a metalanguage for (more than one)
formal languages in the formal language theory sense, since it can
only talk about the syntax, and pure syntax without semantics may be
seen as such a formal language. But these formal languages are those
described by the grammars expressed in EBNF. A grammar itself is not
a language, but it may be part of a language seen as a global object of study, since it can describe its syntax.

I hope this clarifies things.