For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?

It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.

By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression.  This is more powerful than a classical regular expression from a formal languages / automata theory textbook, as classical regular expressions don't allow backreferences, lookahead, lookbehind, and so on.

For a classical regular expression, if you have a good implementation for the matcher, then no regular expression is too evil.  In particular, a standard algorithm for matching is to convert the regular expression to a NFA and then executing the NFA on an input string.  For this algorithm, the worst-case running time to test a $n$-character string is $O(n)$, when the regular expression is fixed.  This means that the running time can't explode too rapidly.  There is no string that will cause an exponential increase in running time.  Thus, if you're using a matcher that uses this algorithm, no classical regular expression will be evil.

This does depend on the implementation of the regular expression matcher.  If you have a naive or poor implementation of the matcher, then matching could take exponential time; there are certainly algorithms with that property.  But the best answer to that is probably not to change the regular expression; it's probably better to pick a better matcher, if you are concerned about denial-of-service attacks.

In comparison, some modern regexps are unavoidably evil.  If you have a modern regexp, then matching can require exponential time.  In particular, regexps with backreferences can recognize NP-hard languages.  Consequently, under plausible assumptions, there exists a class of evil regexps where testing for a match takes exponential time.  Thus, some modern regexps are unavoidably evil: there is no feasible way to find an equivalent regexp that won't cause exponential blowup in running time to match.

(Such an equivalent might exist and might even be findable in theory, but under plausible assumptions, finding the equivalent regexp will take exponential time, which isn't feasible in practice.  If you had a systematic procedure to find the equivalent regexp in polynomial time, then you could solve the NP-hard problem in polynomial time, proving that P = NP.  It doesn't do much good for there to exist an equivalent regexp if there's no way actually find it within your lifetime.)

Background and sources:

Which languages do Perl-compatible regular expressions recognize? and Expressiveness of modern regular expressions provide references to justify that modern regexps can recognize NP-hard languages.
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata? and When a regexp is not a Regular Expression? can be helpful to understand the difference between regular expressions and regexps.
This article from Russ Cox has a nice explanation of two different ways of building a regular expression matcher, and explains why the running time if you use the proper algorithm is linear in the length of the input string (when the regular expression is held fixed and its length is treated as a constant).  In particular, the NFA-based algorithm -- also known as the Thompson algorithm -- has linear worst-case running time.  It also shows how some popular languages have regexp implementations that can go exponential on some regexps, and it discusses which aspects of modern regexps can introduce exponential running times.
In this post I assume P != NP.  More to the point, when I refer to "plausible assumptions", I am referring to the exponential time hypothesis.


What's the runtime complexity of this algorithm for breaking up string into words?

The running time is polynomial with memoization.  If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is polynomial.


"Print 'em all game" for Turing machines

If you use a Gray code then you can get $O(2^n)$. The Gray code described in the Wikipedia article modifies at time $t$ the position $p_t$ which is the index of the right-most 1 bit in $t$. The resulting position sequence is
$$ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, \ldots $$
You are interested in $\sum_t |p_{t+1}-p_t|$:
$$ 1,1,2,2,1,1,3,3,1,1,2,2,1,1,4,4,\ldots. $$
We can see that half the time this is $1$, a quarter of the time it's $2$, one eighth of the time it's $3$, and so on. The total average value is roughly
$$ \sum_{n = 1}^\infty \frac{n}{2^n} = 2. $$
So the head moves roughly $2^{n+1}$ times compared to your lower bound of roughly $2^n$.


How much time would be needed to compute an algorithm with time complexity $O(n^k)$?

An algorithm has time complexity $O(n^k)$ if there exists a constant $C>0$ such that the number of operations that the algorithm performs in the RAM model on an input of length $n$ is at most $Cn^k$.

There are several reasons why this doesn't allow you to determine how much time the algorithm will take on a given machine for a given value of $n$:

$Cn^k$ is only an upper bound.
We don't know the value of $C$.
Your machine differs from the abstract model of computation used to analyze the algorithm.

Therefore the only way to really know how much time a certain algorithm would take is to code it and empirically measure its running time.

What good is asymptotic analysis, then? The abstract machine is a reasonable model of real computers, so it is likely that the running time will scale like $n^k$ (assuming $O(n^k)$ is a tight upper bound). If $k$ is large, then likely the algorithm isn't practical. So asymptotic analysis allows you to compare different algorithms on paper rather than in practice. Of course, sometimes this comparison will result in the wrong conclusion. This is the case for fast matrix multiplication, for instance.


What is the exact difference between a latch & a flipflop?

As far as I understand, the difference is indeed the clock/enable.

A flip-flop samples the inputs only at a clock event (rising edge, etc.)

A Latch samples the inputs continuously whenever it is enabled, that is, only when the enable signal is on. (or otherwise, it would be a wire, not a latch).


To get the CPL by this definition you first take the average distance from a certain vertex to any other vertex:
$$d_v = {{\sum_{v \ne w} d(v,w)} \over {|V(G)| - 1}}$$
 After doing so for every vertex $v \in V(G)$, calculate the median of all previously calculated $d_v$.


$g(n)$ is in $O(f(n))$ means that there exists a positive number $c$ such that $g(n) \leq c \cdot f(n)$ for all $n$ (or at least all large $n$s). In other words, $g(n)$ does not grow faster than $cf(n)$.

We say "is in" because $O(f(n))$ is a class of all functions that satisfy above condition. It is also sometimes said just "is" and written $g(n) = O(f(n))$ but in my opinion this is too misleading because equality here is not symmetric.

That an algorithm is in a complexity class $O(f(n))$ means that a function $g$ that measures the number of basic calculation steps (dependant of the input size $n$) of this algorithm is in $O(f(n))$.

Useful links:

Big O notation
Time complexity


FLP Impossiblity Result assumption of $C_1 = e'(C_0)$

At least in this part of the article, the character C is used for bivalent configurations. The index $0$ for the bivalent $C_0$ was chosen simply because $e(C_0)$ is 0-valent and the index $1$ in $C_1$ was chosen because $e(C_1)$ is 1-valent, even though $C_0$ and $C_1$ are bivalent neighbors (when applying $e'$).


Finding largest sum of $k$ elements below threshold

You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.

For simplicity, let me assume that $k$ is even.

The idea is as follows:

Partition $A$ into two parts.
For each part, compute a sorted list of sums of $k/2$ elements from the part.
For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in the second part which conforms to the constraints.

As stated, there are several problems with the idea:

It assumes that the optimal solution contains exactly $k/2$ summands out of each part.
It runs in time $O(n^{k/2} \log n)$.
It uses $O(n^{k/2})$ memory.

To handle the first difficulty, there are several options. We could just repeat the entire algorithm $\sqrt{k}$ times. Alternatively, there might be deterministic ways to achieve the same goal. Here is a hybrid solution:

Randomly partition $A$ into $k^3$ parts $P_1,\ldots,P_{k^3}$ (anything substantially larger than $k^2$ would work). With high probability, each element of the optimal solution is in its own part.
Consider all possible partitions of $A$ into two parts of the form $P_1,\ldots,P_i$ and $P_{i+1},\ldots,P_{k^3}$. One of these will contain exactly $k/2$ elements of the optimal solution.

To handle the second difficulty, we need to be slightly more careful in implementation. Using merging (the familiar subroutine from mergesort), it should be possible to compute the $k/2$-sums of each part in $O(n^{k/2})$. The final step can be implemented in $O(n^{k/2})$ using a classic two-pointer technique (the first pointer goes up on the first half, the second one goes down on the second half).

There are tricks to reduce the memory required from $O(n^{k/2})$ to $O(n^{k/4})$: further divide each part into two sub-parts. You can easily go over all $k/2$-sums in the first part by considering all pairs of $k/4$-sums in its subparts. Binary search on the second part can then be implemented using the two-pointer technique.


Regular Expressions. Reversal of concatenated strings verification

For the first part,
$$L=\{aw|w\in\{a,b\}^*\}$$
and
$$L_R=\{wa|w\in\{a,b\}^*\}$$

It is true that $L_R$ is the reverse of $L$. $L$ represents the set of strings starting with the symbol $a$, and $L_R$ represents the set of strings ending with the symbol $a$. Note that for some $w$ such that $aw\in L$, you only need to find some $w'$ such that the reverse of $aw$ is $w'a$. You do not need $w=w'$, so your example does not counter the statement.

For every string $w\in\Sigma^*$, where $\Sigma=\{a,b\}$, reversing the characters of $w$ must also belong to$\Sigma^*$. Thus, every string $aw$ in $L$, there is a string which is its reverse in $L_R$ and vice-versa.

For the second part, there is no significance in reversing $v$. It might be intentionally a part of the problem statement.


How do global variables and automatic variables with the same name interact?

In most programming languages, especially imperative languages, a “variable” is actually two things: a name and a storage location. The storage location is a block of memory where a value can be stored and retrieved. The variable's name is often called an identifier. An identifier is a way to refer to some object in the program, in this case a storage location. A variable has a scope, which is the part of the program where the variable's name refers to the variable.

For example, consider the following C snippet.

int foo;
void myfunction(void) {
    float foo;
    … /* Here the identifier foo refers to the variable that's of type float. */
}
/* Here the identifier foo refers to the variable that's of type int. */

This snippets declares two variables. The two variables happen to have the same name: both are called foo. They're distinct variables, refering to distinct storage location, same as if they'd been called by different names. The scope of the foo variable that's of type float is the function myfunction: inside the code of myfunction, the identifier foo refers to this variable; outside the code of myfunction, the identifier foo refers to some other variable, or none at all. The scope of the foo variable that's of type int is the file where it's declared; the identifier foo refers to this variable everywhere is the whole file, except for the functions (or more generally blocks¹) which declare another variable that's also called foo. The local variable foo is said to shadow the global variable foo.

A variable whose scope is a whole file is usually said to be global. A variable whose scope is a function, method, block, etc. is usually said to be local. In the example above, the int-typed foo is a global variable and the float-typed foo is a local variable, local to the function myfunction.

The scope of a variable is the part of a program where its name refers to that variable. This is not always the same thing as the part of the program where the storage location exists. There is some correlation between the two, because it's usually undesirable to have a name for a storage location that doesn't exist, and it's often desirable to have a name for storage locations that do exist.

In C, the time during which a storage location exists is called its duration. The duration of a global variable is the whole program execution (“static duration” in C jargon, but that jargon doesn't extend to other languages, unlike most of the terms I used in this answer). (That's in C and some other langauges; in many other languages the duration of a global variable starts when the variable is defined.) The duration of a local automatic variable is the time during which the block containing it is executing. Note that “automatic” refers to the duration, not to the scope; “automatic” is not the opposite of “global”, “local” is. In C, you can't have automatic duration at a global scope, but you can have static duration at a local scope, with a variable that's declared static or extern.

void myfunction(void) {
    static int s;
    extern int e;
}
/* Here s and e are not defined */

The duration of both s and e is the whole program execution, but their scope is only the function myfunction: the names e and s are not valid outside that function. The difference between static and extern is that the variable s cannot be accessed from another scope, whereas e is the same variable as any other extern e in any scope.

Coming back to the foo example above, since two variables in different scopes have no relation, altering foo in myfunction has no impact on the global foo. They're unrelated variables, they just happen to have the same name.

It would be possible to rename the local variable foo to avoid having a name conflict. If you change all occurrences of foo in the code of myfunction to a different name that isn't used elsewhere in the program, you get an equivalent function.² This renaming process is known as alpha conversion in programming language theory.

The main reason programming languages allow programmers to pick the same name for different variables is that doing otherwise makes it difficult to write large programs and especially to write programs in pieces. If adding a library to your program meant that you had to rename some of your local variables in unrelated parts of your program to avoid conflicts, it would be a nightmare. (As it is, C only has global names for functions, which can be troublesome.)

Basically all languages allow variables in unrelated scopes to have the same name. C also allows shadowing: defining a variable in a scope hides any variable by the same name in a surrounding scope. This is common, but not univeral. For example, in Java, if you define a variable in a block, you can't define another variable by the same name in a nested block. The advantage of this restriction is that it prevents a source of confusion: a programmer might inadvertently use the name to refer to the variable from the outer scope, and not realize it instead refers to the variable in the inner scope. The downside of this restriction is that it makes some program transformations impossible without renaming the variable.

void myfunction(void) {
    int x = 1;
    if (…) {
        int x = 2;  // allowed in C, forbidden in Java
        printf("%d\n", x); // prints 2
    }
    printf("%d\n", x); // prints 1
}

Some languages have a way to refer to a variable that's shadowed, but it's uncommon. C has no such way, but you can refer to the storage location of the outer variable if you have a pointer to it.

¹  More precisely, the scope of a variable defined in a block runs from the variable definition to the end of the block. If there is an outer scope with a variable of the same name, it's that same part which is excluded from that outer scope.
²  This only works in languages where variable names are not significant. Actually, I lied here, because C can make variable names significant via the preprocessor. C is quite a complex language… If that preprocessor feature isn't used, variable names are not significant.


Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays

If you don't have access to atomic primitives like CAS, you're going to have to depend on voluntary synchronization between the two halves.  This means side A cannot proceed until side B has acknowledged that side A took the mutex.

Since we know nothing about the shared memory, we cannot assume that write to two seperate regions will be seen in order (some caches will change the order that writes present).  We will have to assume that there is some atomic thing, like an int32.  We're also going to have to assume that when you say atomic read and write, you never see tearing on the integer, and it's monotonic (if I numbered A's writes, and I've observed #13, I will never again see the  #12 value that had been written).

If you do this, then just take one bit (say, the MSB) and use that as an ownership token over the communication used to handle locks.  If it's a 1, it means A gets to write.  If it's a 0, B gets to write.  Whenever A sets it to a new value, the MSB is always 0, and when B sets it to a new value, the MSB is always 1.  Now, with nothing but normal reads and writes, we can tell who has the "rights" to the communication channel.

Now the communication channel consists of the lower 31 bits.  You can send anything you please across this, including requests to acquire or release a "mutex."  If you want to acquire it, you simply have to wait for it to be your turn to read, send a "request mutex" message, and wait for the reply to say "mutex OK"

EDIT: From our chat discussion, it appears what is really needed is a lottery process to select a master thread, who then takes over the job of being the "kernel" that manages the mutual exclusions.  All it needs is a way to detect when the master thread died, and elect a new master.  This lets us split the problem up into a slow part, which is very robust, and a fast part that works as long as a master is present.


Here is a recursive version of insertion sort:

Input: array $A_1,\ldots,A_n$

If $n = 1$, output $A_1$. Otherwise, continue.
Recursively sort $A_1,\ldots,A_{n-1}$ into $B_1,\ldots,B_{n-1}$.
Insert $A_n$ into $B$.
Output $B$.

If we denote by $T(n)$ the running time for arrays of length $n$,
then step 2 takes time $T(n-1)$, whereas step 3 takes time $O(n)$. Combined, we get the recurrence $T(n) = T(n-1) + O(n)$, with base case $T(1) = O(1)$, corresponding to step 1.


Proving a LL(1) equivalent grammar doesn't exist

The language for the grammar in the question is the set of all words with equal number of $a$'s and $b$'s.

I am afraid your intuition is incorrect. Here is an $LL(1)$ grammar for it.

$S \to aAbS \mid bBaS \mid \epsilon$
$A \to aAb \mid \epsilon$
$B \to bBa \mid\epsilon$

Here is some statistics about the above $LL(1)$ grammar.
$$\begin{array} {|c|c|c|c|}
\hline
\text{nonterminal} &\text{first set} &\text{follow set} &\text{nullable} &\text{endable}\\\hline
S &a\ b &\emptyset &\text{yes} &\text{yes}\\\hline
A  &a &b &\text{yes} &\text{no}\\\hline
B &b &a &\text{yes} &\text{no}\\\hline
\end{array}$$

Here is the parsing table.
$$\begin{array} {|c|c|c|c|}\hline
 &a & b &\$ \\\hline
S  &S\to aAbS &S\to bBaS &S\to \epsilon\\\hline
A  &A\to aAb &A\to \epsilon\quad\ & \\\hline
B &B\to \epsilon\quad\ &B\to bBa & \\\hline
\end{array}$$

Exercise. Show that both the grammar in the question and the grammar in this answer generate the language of words with equal number of $a$'s and $b$'s.


There are n numbers. Find the maximal set of pairwise NON coprime numbers

Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge $uv$ of $G'$ with a prime number $p_{uv}$ such that for each pair of edges $uv, wx \in E$ it holds that $p_{uv} \neq p_{wx}$
Now, label each $v \in V$ with $$ \prod_{u \in Adj(v)} p_{uv}\,.$$

Now, take the set of the labels. A subset of it is the maximum set of non-parwise coprime numbers if and only if it is a maximum clique in $G'$, if and only if it is the maximum independent set of $G$.


Recurrence relations when function call is made inside loop

First, those two summation are not equivalet, the reason that the $1$ is outside is because this line in your code:

 int x=1,k;

Try to run this "by hand" and you will understand why you are addidng $1$ only once.

$\text{fun}(1)=1\\
\text{fun}(2)=2\\
\text{fun}(3)=5\\
\text{fun}(4)=15$

$$\Longrightarrow \text{fun}(n)=\begin{cases}
1;&&&&&&&&n=1\\
\color{red}1+\displaystyle\sum\limits_{k=1}^{n-1}\text{fun}(k)\times \text{fun}(n-k)&&&&&&&&n>1
\end{cases}$$

EDIT:

Step by step for n=3:

int fun (int 3)
{
  int x=1, k;
  if (3==1) return x;
  for (k=1; k<3; ++k)
     x = x + fun(k) * fun(3 – k);
  return x;
}

First loop $k=1:$

$x=\color{green}1+\underbrace{\text{fun(1)}}_{=1}\times \underbrace{\text{fun(3-1)}}_{=2}=\color{red}3$

Second loop $k=2:$

$x=\color{red}3+\underbrace{\text{fun(2)}}_{=2}\times \underbrace{\text{fun(3-2)}}_{=1}=\color{blue}5$


Is there a way to make chess an absolutely fair game?

We can run a pair of games, sequentially, where player one first plays white, then black.

Let's write W for win, L for lose and D for draw, from the point of view of player one. In the cases WW,WD,DW, player one wins the match. In the cases LL,LD,DL, player one loses the match. In the cases WL,LW,DD, the match is a draw.
(If a draw match is undesired, play another match.)


How can I formalize key value stores with set theory?

One simple way to model a key-value store is as a map $f:K \to V$ where $K$ is the set of possible keys and $V$ is the set of possible values.

Often, each value $v \in V$ will itself be a tuple or record.  You can represent a tuple as a Cartesian cross-product, e.g., $V = V_1 \times V_2 \times \dots \times V_k$.  You can represent a record as either a tuple (if the set of attributes is finite and known in advance), or as a function from attribute names to values.

Modelling languages like Alloy can represent such maps natively.  Some modeling languages will use the notation $k.f$ instead of $f(k)$ (i.e., object field access notation instead of function evaluation), but the two are equivalent.

If you don't want to use functions, but want to stick to just sets, that is also feasible.  You can model any function $f: K \to V$ as a binary relation, i.e., a set $S \subseteq K \times V$ with the additional property that if $(k_1,v_1) \in S$ and $(k_2,v_2) \in S$ and $k_1=k_2$, then $v_1=v_2$.  However this may be less natural.

This gives you a way to model the state of the store.  You will then need to model the effect of each operation that can be performed on the store, in these mathematical terms.


Determine the smallest $3$ numbers in a set using comparisons

I can show you how to get the two smallest elements in $n + O(
\log n)$ comparisons, the extension to the three smallest elements should not be difficult.

Build the following tree. Start with your array, then for each pair of neighboring elements (non-overlapping), promote the smaller one level up. Do the same for the new level, until the tree has a root.

This tree is built using less than $n$ comparisons ($n / 2 + n / 4 + \dots$). The smallest element is obviously the root. The second smallest element must be one of of the siblings of all the nodes that are equal to the root along the path down the tree to the array level. There are at most $\log n$ such nodes.

You should also convince yourself of the bound when the number of nodes on a level is not even.


Closure properties of the class of inherently ambiguous CFLs

Reversal

The class of inherently ambiguous context-free languages is closed under reversal (exercise).

Intersection

The class of inherently ambiguous context-free languages is not closed under intersection. Indeed, take some inherently ambiguous context-free language $L$. Now take $L'$ to be a copy of $L$ which uses a different alphabet. Then $L \cap L' = \emptyset$.

Complementation

The class of inherently ambiguous context-free languages is not closed under complementation. Indeed, consider the Goldstine language
$$ G = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i \text{ for some } i \}. $$
This language is context-free and inherently ambiguous (see slides of Cyril Nicaud). Also,
$$
\overline{G} \cap \Sigma^* b = \{ aba^2\cdots a^p b : p \geq 1 \},
$$
which isn't even context-free.

Union

The class of inherently ambiguous context-free languages is not closed under union. Indeed, the following variant of the Goldstine language is probably also context-free and inherently ambiguous:
$$ G' = \{ a^{n_1} b \cdots a^{n_p} b : p \geq 1 \text{ and } n_i \neq i+1 \text{ for some } i \}. $$
However, $G \cup G' = (a^*b)^+$.

Iteration (Kleene star)

The class of inherently ambiguous context-free languages is not closed under Kleene star. Indeed, consider the following language:
$$
\Omega_3 = \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \}.
$$
Here $|u|_a$ is the number of $a$s in $u$. This language is context-free and inherently ambiguous (see the slides of Cyril Nicaud). However, $\Omega_3^* = \{a,b,c\}^*$.

Concatenation

The class of inherently ambiguous context-free languages is not closed under concatenation. Indeed, the following variants of $\Omega_3$ are probably also context-free and inherently ambiguous:
$$
\begin{align*}
\Omega'_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b \text{ or } |u|_a \neq |u|_c \text{ or } u = \epsilon \}, \\
\Omega''_3 &= \{ u \in \{a,b,c\}^* : |u|_a \neq |u|_b+1 \text{ or } |u|_a \neq |u|_c+1 \text{ or } u = \epsilon \}.
\end{align*}
$$
However, $\Omega'_3 \Omega''_3 = \{a,b,c\}^*$.


From the givens you can only deduce that the Shannon capacity is at least $\sqrt{5}$. For example, it could be that $\alpha(C_5^8)^{1/8} > \sqrt{5}$, which doesn't contradict your data.

As an aside, the Shannon capacity is usually denoted by $\Theta$, whereas $\theta$ is the Lovász function, which is an upper bound on the Shannon capacity. From the givens you can only deduce that $\theta(C_5) \geq \sqrt{5}$.


NEAT algorithm and dynamic topology neural networks

Not an expert in neural net. But I recently read and answer a question on NEAT. From there, I would assume that direction of edges are already determined in each gene. Because of the way operations on genome was designed, I could see that you can ensure the genome is always in `topological order'.

Alternatively, looking at heuristic algorithms that iteratively update graph's weight as it learns (e.g. pagerank and ACO), it should be fine to assume initial weight and just let the iteration stabilise. One could imagine this as every edge being directed both ways --- every link is both input and output.


Top-down typing strategy - is there a name for this?

There is no top-down or bottom-up typing strategy when defining a language. It is an implementation issue. A type system will
only define operator operand constraints on your AST. The kind
constraints is fixed by the type system and is part of the design of
the language. It can be very simple as in older languages, or be a
sophisticated logical system. Even when simple, it can be seen as a
logical system. Your AST may be seen as a proof tree in that logical
system, where the nodes are to be decorated by types, that may be seen as logical
propositions proved by by the sub-tree dominated by that node . For example, the type int found for an expression is
a predicate satisfied by the expression.

So you can associate type inference rules to the operators of your
AST. For example if you have an AST operator +  with two operands,
you can associate (among others) the inference rule:
$X::int \,\wedge\, Y::int \;\Rightarrow\; X+Y::int$

Defining the type system of a language amount to defining such rules
for all AST operators where that make sense, i.e. involved with the
type system.

Type checking your program consists in finding a type for each
(relevant) AST node, such that that there is an inference
rule (associated to the operator of that node) that is satisfied by
the node type and the types of its operands.

This can be done with top-down or bottom-up algorithms, or any
mix. That is only a matter of finding efficient algorithms. But the
checking strategy is an implementation issue, not a language
definition issue. However, it is advisable to choose a type system
that allows for a tractable type checking strategy.

Note that the types may not be all completely defined by the type system,
and the checking strategy may actually infer the "details" of these
types, in particular by means of unification techniques.

The above description may not seem too complex (I hope). One hidden
aspect, that makes the whole thing a lot more interesting, is that
in static typing (particularly) all occurences of the same variable
must have the same type, which introduces additional constraints.
But getting into the details is too much for a normally sized answer.

For more about this, you should look for type inference.


NFA or DFA for strings the contain exactly twice substring ab?

To answer these kind of questions try to break down your problem into smaller parts.

Can you find a NFA that accepts all words that contain the substring $ab$ exactly once?
If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\circ L_2 =\{uv\mid u\in L_1 \text{ and } v\in L_2\}$?
Can you find a NFA that accepts all words that contain a $c$?
If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\cap L_2 =\{u \mid u\in L_1 \text{ and } u\in L_2\}$?

Steps 2. and 4. are well known closure constructions for regular languages. Its not hard to come up with these constructions by yourself, but there are also part in most of the textbooks.

As pointed out in the comments, the concatenation is in your case more subtle, since the first string might end with $a$ and the second one might start with  $b$. This can be fixed by setting $L_1:=\{w \mid \text{$w$ contains $ab$ once in the end}\}$. In particular, you can always split the words of your language exactly after the first occurrence of $ab$.


Surprisingly high collision rates when hashing a short list with few buckets

Depending on how you count collisions, we can expect either about 2000 collisions, or about 1472 collisions.  The latter is in close agreement with what you observe, so yes, 1500 collisions looks about right to me.

Counting collisions pairwise

I think the most natural way to count collisions is "pairwise".  For instance, if A, B, and C all hash into the same bucket, let's count that as 3 collisions.   If A, B, C, and D hash to the same bucket, let's count that as 6 collisions (not 4, but 6: the 6 collisions are AB, AC, AD, BC, BD, and CD).  And so on.  In general if there are $k$ items in a bucket, that causes ${k \choose 2}$ collisions, with this method of counting collisions.

Then, you can use linearity of expectation to estimate the number of collisions, assuming the hash function is good.  Let $X_{i,j}$ be an indicator random variable that is $1$ if objects $i,j$ hash to the same bucket, or $0$ otherwise.  Let $Y=\sum_{i<j} X_{i,j}$ be the sum of these random variables.  Then $Y$ counts the number of collisions.

Can we estimate a typical value for $Y$?  Well, we can compute the expected value of $Y$ in a straightforward way:

$$\mathbb{E}[Y] = \sum_{i<j} \mathbb{E}[X_{i,j}] = \sum_{i<j} {1 \over 4000} = {4000 \choose 2} {1 \over 4000} = {3999 \over 2} \approx 2000,$$

using the fact that $\mathbb{E}[X_{i,j}] = \Pr[X_{i,j}=1] = {1 \over 4000}$ since there is a 1 in 4000 chance that object $j$ hashes to the same bucket as object $i$ (assuming a good hash function).  Typically, the observed value of $Y$ will be near its expected value.  So, that'd predict that you see about 1500 collisions.  That's a consequence of the number of buckets and the number of items hashed.

In general, if you hash $n$ items into $m$ buckets using a good hash function, you should expect to see about ${n^2 \over 2m}$  collisions, on average, using this method for counting collisions.

Counting collisions by bucket size

On reading your comment, it sounds like you are counting collisions differently.  If there are $k \ge 1$ items in a bucket, it sounds like you are counting that as $k-1$ collisions.  How does that affect things?  Well, it makes the calculation more complicated.  I'll share a much terser analysis for this case, without showing all the details.

Let $N_i$ denote the number of items in bucket $i$.  If the hash function is good, the number of items in a bucket should follow approximately the Poisson distribution with parameter $\lambda = n/m$.  In your case, we have $\lambda=1$.  The total number of collisions (the way you are counting it) is

$$N = \sum_i \max(N_i-1,0).$$

Now,

$$\begin{align*}
\mathbb{E}[\max(N_i-1,0)]
&=
 1 \cdot {\lambda^2 e^{-\lambda} \over 2!} +
 2 \cdot {\lambda^3 e^{-\lambda} \over 3!} +
 3 \cdot {\lambda^4 e^{-\lambda} \over 4!} + \cdots\\
&=
 \lambda e^{-\lambda} + \lambda^2 - \lambda.
\end{align*}$$

(Don't ask me how I summed the series; black magic.)  It follows that

$$\mathbb{E}[N] = \sum_i \mathbb{E}[\max(N_i-1,0)] = (\lambda e^{-\lambda} + \lambda^2 - \lambda) n.$$

In your case $\lambda=1$ and $n=4000$, so we predict $1/e \times 4000 \approx 1472$ collisions.  That has very close agreement with what you are observing empirically, so practice and theory seem to be in close agreement.


How best to allocate stock buys and sells when using specific id to maximize long term capital gains

There's a natural greedy algorithm.  Scan through the buy/sell orders in chronological order.  At each sell order:

Sell as many shares that would be classified as long-term as possible, until you've sold the number required by the sell order.

If you still need to sell more shares, and there are no more shares that would be classified long-term sales, sell the youngest (newest / most recently bought) shares first.

I suggest trying to verify whether that leads to a correct algorithm or not.  See How to prove greedy algorithm is correct.


Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

You are on the right track.

It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)

Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths.

Let the index of the first minimum strength be $m$. Then the maximum number of kicks is $n = R/S[m]$. So $O=[m, m, \cdots, m]$, where the number of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n*S[m]$.

How can we get a lexicographically smaller order with the same number of kicks? If we can find an index $i$ smaller than $m$ such that we can replace a kick of strength $S[m]$ by a kick of strength $S[i]$ without overpassing the resistance capacity $R$, then we can replace the first element in $O$ by $i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $i$ as small as possible and, then, we would like to use it as many times as possible.

For example, $R = 11, S = [6, 8, 5, 4, 7, 4]$. Then the first minimum strength is the first 4 whose index is 3. So $n=11/4=2$ and $O=[3,3]$ with total strength $4*2=8$. To make it smaller, we will check the strengths before 4 in order. The first one is $6$. Since $8-4+6=10<11$, we find a smaller order $[0,3]$. If we apply 6 again, we would get $10-4+6=12 > 11$. So we go ahead to check the next strength 8, which is too large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find a smaller order $[0,2]$. Since the room left for replacement, $11-11 =0$, we stop our effort. The final answer is [0,2].

I have verified that my program wrote along the above approach works. Hopefully, I have written enough to encourage you to go ahead. Hopefully, I have not written too much to spoil the fun for you.

This problem is a variation of the unbounded knapsack problem.


How to prove that context sensitive languages are closed under intersection and complement?

The first closure property, closure under intersection, is a DIY proof if you choose the right model for the context-sensitive languages. By defining them with the help of linear-bounded automata you can run two of these automata successively to test (nondeterministically) for acceptance of the intersection.

Second, closure under complement, is hard! It used to be a famous open problem until solved independently by Immerman and Szelepcsényi. It is quite a surprising proof, how to prove complement for a nondeterministic automaton. The technique is called inductive counting and works for larger families of complexity classes: NSPACE($s(n)$)=co-NSPACE($s(n)$), where context-sensitive equals linear nondeterministic space.


Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$

If you let T(0) = T(1) = 0, then prove by complete induction for every k >= 1 that T(n) = k for all n such that $2^{k-1} < n <= 2^k$.
k = 1: True because T(2) = 1.
k -> k + 1: Let $2^k < n <= 2^{k+1}$. Then $2^{k-1} < n/2 <= 2^k$, therefore $2^{k-1} < \lceil n/2 \rceil<= 2^k$, therefore $T(\lceil n/2 \rceil) = k$, therefore T(n) = k+1.
So instead of O(log n) you get the much stronger $T(1) + \lceil \log_2 n \rceil$ for all n >= 1.


Can the following conditions hold all together?

Conditions $2,3,4$ imply $L_1 \in RE$, contradicting $1$.

Here's how to semi-decide $L_1$. Take a candidate $x$.
If $x \in L_1 \cap L_2$ (decidable by $2$), accept.
If $x \notin L_1 \cup L_2$ (decidable by $3$), diverge (we know $x \notin L_1$ for sure).

We now know that
$$x \in (L_1\setminus L_2) \cup (L_2\setminus L_1) \qquad (*)$$

Exploiting $4$, we run semi-deciders for $\overline{L_1}, \overline{L_2}$ on $x$ in parallel. By $(*)$, (exactly) one of these must eventually halt.

If the former halts, we infer $x \notin L_1$, so we diverge.
If the second one halts, we infer $x \notin L_2$, and by $(*)$ we obtain $x\in L_1$, so we accept.


Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency.  For instance, you can enumerate all programs (in order of increasing size) and test each one to see which is the first that produces a valid perfect hash.  This is a valid deterministic algorithm that is guaranteed to always find a valid perfect hash (and even to find the minimal such program).  However, this will be extremely slow for all but the smallest values of $M$, so it's not likely to be useful in practice.

I expect that finding the smallest such program will be NP-hard, and probably $\Pi_2$-hard (loosely, "even harder than NP-hard").  I don't have a proof of this -- just a suspicion.  For example, the problem of circuit minimization is known to be $\Pi_2$-hard.  In other words, given a circuit $C$, it's $\Pi_2$-hard to find the smallest circuit $C'$ that computes the same function as $C$.  Your probably isn't quite the same, but it has a "similar feel", so I would expect your problem (finding the smallest deterministic program that yields a valid hash for the $M$ items) will also be hard.

If you are willing to make unproven assumptions, it is possible to come up with a deterministic algorithm that is also efficient: about as efficient as the randomized/probabilistic algorithms you know of it and want to avoid.  In particular, you can take a randomized algorithm and derandomize it as follows: fix a cryptographic-strength pseudorandom number generator (e.g., AES-CTR mode); fix a seed for it (e.g., the all-zeros AES key; or pick a random 128-bit value, and fix it as the AES key); feed this seed the prng algorithm and use it to generate an unending stream of pseudorandom numbers; now run the randomized algorithm, except that whenever it calls for a random number, give it the next pseudorandom number from the output of the crypto prng.  Note that this is a completely deterministic algorithm: the seed is hardcoded into the code of the algorithm and fixed for all time.  Here's what we know: if the pseudorandom number generation algorithm is cryptographically secure, and if the randomized algorithm outputs the correct answer, then (with high probability over the choice of seed) the deterministic algorithm also outputs the correct answer.

This means that if you know how to build a cryptographically-secure pseudorandom number generator, you can convert any randomized algorithm into a deterministic algorithm.  It may be surprising that cryptography has anything to do with this subject, since we don't require kind of security properties from the hash, but it turns out that this construction gives a generic way to derandomize any randomized algorithm.  Here's how to see the connection: the definition of what it means for a prng to be cryptographically-security is that no polynomial-time algorithm should be able to tell that it is receiving pseudorandomness rather than real randomness; thus, we can run the randomized algorithm, and swapping out the true-random bits for pseudorandom bits won't mess up the algorithm.

Thus, this will let you build a deterministic algorithm that is correct and efficient, if AES is secure (or one that works if factoring is hard, or based on any other cryptographic assumption).   It's widely believed that AES is secure (and factoring is hard, etc.), even though we have no proof, so this provides a reasonable practical solution to your problem, even though we have no proof that it works.


Finding integer square root for large integers [find asymptotic time complexity]

Normally, you don't measure the complexity of a problem before designing an algorithm; instead, you measure the complexity of a particular algorithm.  So, before you get to measuring complexity, the first step is to come up with a specific algorithm.

When you have a specific algorithm in mind, one technique that's useful for analyzing the running time of divide-and-conquer algorithms is to write down a recurrence relation characterizing its running time, and then solve the recurrence.  You can often use the Master theorem to solve the recurrence.

To learn these techniques, see your favorite algorithms textbook, or read the following resources:

How to come up with the runtime of algorithms?
What is the difference between an algorithm, a language and a problem?
Solving or approximating recurrence relations for sequences of numbers
Is there a system behind the magic of algorithm analysis?


Selection type generated by nested loops where initial value is current value of parent loop

The sequences your program generates are non-decreasing sequences.


Are all databases reducible to this ultimate abstract database design?

This insight was made at least as far back as 1886, by Alfred Kempe.  In fact, he observed that any set of relationships (not just those that are already relations) can be captured as a binary relation.  At the time this seems to have come as a shock to Charles Sanders Peirce, who had built his relation algebra on the idea that any relation can be captured by means of ternary relations, and who up to this time apparently believed this to be the best possible.  Kempe used graphs to illustrate his notion, while Peirce used edge-labelled graphs.  In a long and admiring review Peirce revised his theories to accommodate binary relations as a possible foundation, and distinguished the two approaches:

  Mr. Kempe's conception depends upon considering the diagram purely in its self-contained relations, the idea of its representing anything being altogether left out of view; while my doctrine depends upon considering how the diagram is to be connected with nature.

In terms of modern database representations, RDF corresponds to Peirce's ternary relations, while key-value stores correspond to Kempe's graphs.  As Raphael pointed out in a comment, these are essentially the ideas behind graph databases.

As an aside, the arguments about binary/ternary/quaternary/quinternary/... tuples being the "best" foundation for data representation still rage on in the W3C semantic web working groups.  I believe that the original insight of the relational model was that for efficiency, one should use relations of the right arity; relationships that are naturally represented as tuples should not be transmogrified into more complicated data structures just for reasons of purity.  However, this argument also goes the other way: relationships where different instances naturally have different arities should not be shoehorned into a rigid relational schema just to preserve the purity of the data model.

A. B. Kempe, A Memoir on the Theory of Mathematical Form, Philosophical Transactions of the Royal Society of London 177, 1886, 1–70.
C. S. Peirce, The Critic of Arguments (1892 essay), in Collected Papers of Charles Sanders Peirce, Vol. III, Harvard University Press, 1933, 250–265.


What is the quickest way to allocate a set of points to a fixed number groups based on Euclidean distances from a point in each group?

This looks very much like the Nearest neighbor problem. The asymptotically most efficient approach is probably computing a k-d-tree on the points in B. Constructing the tree takes $O(|B| \log |B|)$ and lookup is logarithmic, so an additional $O(|A| \log |A|)$ to find all nearest neighbours.

Please not that the constant factors for the naive approach where you just compute the distance to each point in B and take the minimum are really good. CPUs are very good at just summing squared differences. In practice it will be hard to beat that unless B is really huge.


Undecidable Problem for Regular Languages

Yes, there are undecidable problems like the Post Correspondence Problem that can be coded into the language of a finite state automaton, as explained in my earlier answer to a (slightly broader) question: https://cs.stackexchange.com/a/6198

The result can be traced to a paper by Engelfriet and Rozenberg dealing with the so called twin shuffle operation.
Fixed Point Languages, Equality Languages, and Representation of
Recursively Enumerable Languages (J. ACM)
doi:10.1145/322203.322211

Recently Endrullis, Shallit and Smith presented the paper Undecidability and Finite Automata at the conference DLT2017 (doi:10.1007/978-3-319-62809-7_11, arxiv:1702.01394) which deals with your question:

  Abstract. Using a novel rewriting problem, we show that several natural decision
  problems about finite automata are undecidable (i.e., recursively
  unsolvable). In contrast, we also prove three related problems are
  decidable. We apply one result to prove the undecidability of a
  related problem about k-automatic sets of rational numbers.

I am very proud that one of the references in this paper is to my earlier SE answer!


Are every problems in EXP karp reducible to any EXP-Complete?

Yes. That's the definition of $\mathrm{EXP}$-completeness.

  My question is: where is my mistake?

Your mistake is in believing that $L''\notin\mathrm{EXP}$. You've demonstrated a Turing machine that decides $L$ in time $O(n^{\log n}) = O(2^{(\log n)^2})\subset O(2^n)$. I'm not sure what you mean by "$M$ prevents the reductions" – you're trying to reduce from $L(M)$ to $L$, not from $L$ to $L(M)$.

On the other hand, $L''$ is not $\mathrm{EXP}$-complete, by the time hierarchy theorem. Any language reducible to $L''$ must be in time $O(2^{(\log (n^c))^2})$ for some $c$, but this is just time $O(2^{(c\log n)^2})=O(2^{(\log n)^2})$.


Curiosity on system device nomenclature - Gaussian Mixture Models

These are accelerators for Gaussian Mixture Modelling used for speech recognition and video processing applications.  They can be typically accessed via openCL libraries.

GMMs are used for efficient classification of partial or noisy data e.g. speaker voices or people object in videos.


Algorithm to compute a recursive function on a given set

You haven't told us what the function is, so we can't give you an algorithm.

However, here's what I can say.  There are two general techniques that are often applicable to this setting:

Use dynamic programming (or memoization).  This will avoid you having to evaluate fun(k,S) more than once for any pair (k,S).
Look for mathematical identities that give you different ways to express your function.  Sometimes you can find different ways to express your function (e.g., by factoring out common terms or somesuch); if so, look for these, and see if any of them leads to a more efficient algorithm than the others.


The exact response is hardware implementation specific. Typically the memory access will timeout and a hardware exception will be generated. DEC called these Machine Checks, other manufacturers may use different terms.  The CPU will follow some interrupt path that will handle the timeout.  In normal operation the most common result will be a system crash (again different terms are used, but "Bugcheck" was favored by DEC, "ABEND" is used by others.).

There are some system implementations that don't have a timeout mechanism, in these cases the typical response would be a hang waiting for a response from memory or in a less desirable case, random noise would be read from the data lines.

During boot sequences, the exception handling is sometimes changed so that the system configuration can be discovered.  The configuration code may "probe" addresses until it gets an exception in order to find the end of physical memory. Again, this is architecture dependent and not always necessary if the hardware provides some other means of determining the installed memory.

Since you mention ARM specifically, you can read a white paper for ARM memory implementation here:
Principles of ARM® Memory Maps
This paper has the following recommendation regarding memory accesses:
"Unpopulated DRAM partitions must not alias any other addresses, accesses
should return bus errors."


Database books are good example. However, have a look at the field I/O efficient data structures (and algorithms). To my knowledge, there are some  courses about this topic, but very few books.

Check this book: U. Meyer, P. Sanders, and J. Sibeyn (eds.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Check these courses:
http://www.win.tue.nl/~hermanh/teaching/2IL35/
http://www.daimi.au.dk/~large/ioS12/

and these slides:
algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf


How are artificial intelligence and Natural intelligence compared?

You are probably referring to ConceptNet (created by the Massachusetts Institute of Technology under its Artificial Intelligence program).

It's a software system / semantic network containing lots of things computers should know about the world, especially when understanding text written by people.

Researchers from the University of Illinois (research team led by Stellan Ohlsson) did a study on the ConceptNet 4 version of the AI and they discovered that its IQ level is the same as that of a 4-year-old child (somewhat... see below).

The chosen IQ test is known as the Wechsler Preschool and Primary Scale of Intelligence (third edition, WPPSI-III). It's commonly used in schools across the United States and is designed to measure the level of intelligence in five key categories and consists of 14 subtests (picture memory, similarities, object assembly, picture naming...).

  The  test  questions  (e.g. "Why do we shake  hands?")  were  translated into ConceptNet 4 inputs using a combination of the simple natural language processing tools that come with ConceptNet together with short Python programs that we wrote. The question answering used a version of ConceptNet based on spectral methods.

  The  ConceptNet system  scored  a  WPPSI-III  VIQ  that is  average  for a four-year-old child, but below average for 5 to 7 year-olds

  [CUT]

  The large variations among subtests and ordinary common sense strongly suggest that the WPPSI-III VIQ results do not show that "ConceptNet  has  the  verbal  abilities  a  four-year-old."

  Rather, children's IQ tests offer one objective metric for the evaluation and comparison of AI systems

(From Measuring an Artificial Intelligence System's Performance on a Verbal IQ Te st For Young Children - Stellan Ohlsson, Robert H. Sloan, György Turán, Aaron Urasky)


If $k \leq (1-\epsilon) N$, where $N$ is the total number of subtrees, then the following approach would work:

Start with the empty list $L$.
Repeat $k$ times:

Pick a random subtree $T'$.
If $T' \notin L$, add it to $L$; otherwise, go back to the previous step.

Since $k \leq (1-\epsilon) N$, the expected number of times it takes to find $T' \notin L$ is at most $1/\epsilon$ throughout the process; it will be much smaller in the beginning. In particular, if $k \ll \sqrt{N}$, then it is highly likely that you will never generate the same subtree twice.

In more detail, the average expected number of repetitions is
$$
\frac{1}{k} \sum_{\ell=0}^{k-1} \frac{N}{N-\ell} \approx \frac{N}{k} \int_0^k \frac{dx}{N-x} = \frac{N}{k} \ln \frac{N}{N-k} \approx \frac{N}{N-k} = 1 + \frac{k}{N-k}.
$$

You can implement the check $T' \notin L$ quickly using a hashtable. In this way, we have reduced your problem to that of generating a uniformly random subtree, which you can do as follows, essentially by reducing the problem of uniform generation to that of counting.

In order to pick the root of the subtree, first compute $R(T_x)$ for every vertex $x \in T$ (you can do this in $O(n)$ for all vertices together if you're careful, where $n$ is the number of vertices). The root is $x$ with probability $R(T_x)/N$ (you can choose $x$ quickly using binary search, for example).

If $x$ is a leaf, then we're done. Otherwise, suppose that $x$ has children $x_1,\ldots,x_\ell$. Your random subtree skips $x_i$ with probability $1/(1+R(T_{x_i}))$ (independently). If it doesn't skip $x_i$, then you generate a random subtree of $T_{x_i}$ recursively.

Here are two other related approaches. The first is to generate all subtrees, permute them randomly in $O(N)$, and then output the prefix of length $k$.

A variant of the first approach uses unranking. By modifying the approach above, you can take an integer in the range $0,\ldots,N-1$ and convert it to a subtree. This goes as follows. Let $x_1,\ldots,x_n$ be an enumeration of the vertices of $T$. The first $R(T_{x_1})$ integers correspond to subtrees rooted at $x_1$. The following $R(T_{x_2})$ integers correspond to subtrees rooted at $x_2$. And so on.

Now suppose we're given an integer $i$ in the range $0,\ldots,R(T_x)-1$, and need to convert it to a subtree rooted at $x$. If $x$ is a leaf, then there is nothing to do. Otherwise, let $x_1,\ldots,x_\ell$ be the children of $x$. We first convert $i$ into $\ell$ numbers $i_1,\ldots,i_\ell$, where $i_j$ is in the range $0,\ldots,R(T_{x_{i_j}})$. If $i_j = R(T_{x_{i_j}})$, then the subtree won't contain $x_{i_j}$. Otherwise, we can generate a subtree of $x_{i_j}$ recursively.

Given the unranking procedure, you can generate a permutation of $0,\ldots,N-1$, take the prefix of length $k$, and convert it to a list of $k$ subtrees. If you have any other way of generating a random sequence of $k$ elements of $0,\ldots,N-1$ without repetition, then you can use it in the same way.


What does it mean that numbers are "totally ordered", in the Paxos Made Simple paper?

Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\{0\}$ and $\{1\}$ are incomparable.

Intuitively, a total order is one where you can lay all the elements on a line, where moving along the line always increases the value. (This is not mathematically true because some orders are too “dense” to fit.)

Suppose that two proposals numbered $n_1$ and $n_2$ are chosen, with values $v_1$ and $v_2$ respectively. The desired safety property is that the values are in fact the same: $v_1 = v_2$. By condition P2, if $n_1 \le n_2$, then proposal $n_2$ is higher-numbered than proposal $n_1$, so its value $v_2$ is equal to $v_1$. Similarly, if $n_2 \le n_1$ then $v_1 = v_2$. The fact that the integers are totally ordered implies that at least one of the propositions $n_1 \le n_2$ and $n_2 \le n_1$ is true, and therefore either way $v_1 = v_2$.

What condition P2 means in some idealized way is that if a choice is made, all subsequent choices will be for the same value. However, “subsequent” doesn't quite work out, because the numbering of the proposals doesn't necessarily correspond with the order in which they are made in real time: different nodes in the network can make proposals before they are aware of each other, so numbers can't be assigned to proposals in chronological order. Solving this problem is a large part of working out a consensus algorithm.


How to define a similarity between two graphs?

One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost of a transformation from one to the other (the costs need to be symmetrical for this to be a distance, e.g. the cost of deleting is equal to the cost of adding, and are usually taken to be unitary).
There are applications outside of pure graph theory such as pattern recognition or in bioinformatics (generalisations of string edit distance useful for DNA analysis).
Note that usually we don't consider "edit distance up to isomorphism" as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.


This problem is call "$X$-satuated bipartite matching" or Hall's marriage problem, which is discussed at here on Wikipedia.

Consider each item as a woman. Each bag is a man. If item $a$ is allowed to be placed in bag $x$, it means woman $a$ and man $x$ can be married happily. Only one item can go in each bag corresponds to the assumption of monogamy, a man with one wife and a woman with one husband. So the problem is asking whether it is possible that all women can be married happily.

Please check the link for details and much more interesting result around. You can find various efficient algorithms to solve the problem and related problems.

Since we are here, we should mention the following celebrated theorem.

  Hall's Marriage Theorem — A family $S$ of finite sets has a transversal if and only if $S$ satisfies the marriage condition.


vmlinux is the executable file that is generated when building the Linux kernel. This isn't a normal executable file that would be generated as a result of compiling a program using, say, gcc.
As Wikipedia suggests, this executable needs to be further processed to be made bootable, but this is the essentially the executable image of the kernel.

Does that mean vmlinux is a virtual machine that runs Linux?

No, the 'vm' here stands for 'virtual memory'. From Wikipedia,

With the development of virtual memory, kernels that supported this feature were given the vm- prefix to differentiate them. The name vmlinux is a mutation of vmunix.

What is this vmlinux executable good for? Well, for starters, it can be made bootable and then booted on a physical computer.
You can also use this executable to run a virtual machine using qemu. Then, you can debug the kernel that is running in the virtual machine using gdb.


How to find contour lines for Appel's Hidden Line Removal Algorithm

For the "-facing" rule to hold, you must make sure that all faces are properly oriented. Use the right-hand rule for instance, that means that the vertices of a face should be numbered in such a way that a positive rotation in the plane of the face corresponds to a normal pointing outside of the polyhedron. (Got it ?) Or more simply, every face must come with its outward-pointing normal.

Dangling faces, i.e. not belonging to a closed polyhedron can be seen as having an undeterminate orientation.

Now computing the parts of an edge which are hidden by a contour polygon is the main course. This problem is very close to that of clipping a line segment by a polygonal window in 2D. First consider the line of support of the line segment and find intersections with the polygon. By using a parity rule, you can easily determine the parts inside and outside the polygon.


Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?

The average-case running time of an algorithm with respect to some distribution $D$ is, by definition, the expected running time of the algorithm when run on an input sampled according to $D$.
This should be contrasted with worst-case running time, which is the maximum running time on any input of a given length, and best-case running time, which is the minimum running time on any input of given length.
Since worst-case and best-case running time are defined as maximum and minimum, there are inputs attaining them. Average-case running time is an expectation, and so it is meaningless to talk about an input attaining them.
If you throw a die, the expected number you get is 3.5. This is not attained by any particular throw. If the die had 5 sides, the expected number is 3, which does correspond to some throw, but that doesn't mean that the throw is "average case".

What sometimes happens is that you can isolate a class of inputs $X$ such that when run on an input from $X$, the running time of the algorithm is within a constant factor of the average-case running time (for this to make sense, $X$ should actually corresponds to a sequence $X_n$ of inputs of every length, or at least infinitely many length). You can say that $X$  "achieves" the expected running time of the algorithm.


how to approximate a very complex optimal policy when the distance function is unknown

Let me start with some basic material that covers the case where you know how to compute $D(P)$; then speculate on some methods that might be applicable to your particular situation, where we only know how to compute $D(P)-D(Q)$.

Gradient descent. One reasonable approach is to use gradient descent to optimize the parameters.  If we have an objective function $\Phi(P)$ that tells us the penalty or loss associated with policy $P$, we use gradient descent to try to find parameters $P$ that minimize $\Phi(P)$.  This requires that $\Phi(\cdot)$ be continuous and differentiable.  Ideally, we'd have a way to compute the partial derivatives (the gradient) of $\Phi$ at any point; but if we don't, one possibility is to use standard methods to approximate the partial derivative, e.g.,

$${\partial \over \partial x} \Phi(P) = {\Phi(P+\epsilon x) - \Phi(P-\epsilon x) \over 2 \epsilon}.$$

Stochastic gradient descent. In your situation, stochastic gradient descent is an important optimization that provides significant speedups.  The basic idea is that, if we can decompose the objective function as a sum

$$\Phi(P) = \sum_i \Phi_i(P),$$

then we can speed up gradient descent.  In each step, we evaluate the gradient of $\Phi_i$ (rather than of $\Phi$, as ordinary gradient descent would do) and take a small step in the direction given by that gradient.  This can be a lot more efficient, if computing the gradient of $\Phi_i$ is more efficient than computing the gradient of $\Phi$.

In your situation, $\Phi(P)$ is defined to be

$$\Phi(P) = \sum_{i=1}^n {w_i(P) \over n},$$

where $w_i(P)$ is 1 if $P$ wins in the $i$th game and 0 otherwise.  Therefore, $\Phi$ has the required form to allow you to apply stochastic gradient descent, and you can expect this method to give significant speedups.  Effectively, you do only one game simulation per step of (stochastic) gradient descent rather than $n$ game simulations per step.

As a practical matter, there are many further improvements on stochastic gradient descent that are well-studied, including momentum, rmsprop, and many others.  Personally, I'd recommend trying the Adam solver; it seems to be state of the art.

So if you knew how to compute $D(P)$, the above would give you a reasonable method for optimizing $P$: simply define $\Phi(P)=D(P)$ and then apply stochastic gradient descent.  But you don't... so now we need a way to adjust.

Your situation.  Your specific situation is more challenging, but there are still some avenues you could explore.  For instance, here is one approach you could consider.  Fix a reasonable policy $Q_0$, and define

$$\Phi(P) = D(P) - D(Q_0).$$

Apply stochastic gradient descent to try to minimize $\Phi(P)$, i.e., to find $P$ that makes $\Phi(P)$ small.  Do that for a little while.  Then, pick a new policy, call it $Q_1$, and define

$$\Phi(P) = D(P) - D(Q_1)$$

and continue iterating.  Every so often, you replace $Q_i$ with a new (better) policy $Q_{i+1}$ that hopefully is closer to $O$.  This might work.

How do you choose $Q_{i+1}$?  One way would be to let $Q_{i+1}$ be the best policy seen so far.  So, effectively, you are constantly trying to find a policy that beats the best policy seen so far.  You'd need to tune how often you change $Q$ and play with some parameters.

Caveats.  However, I suspect that if you're actually dealing with a two-player game, things won't be this simple.  In particular, I suspect that your model of the situation is not accurate: that, for several reasons, the fraction of times that $P$ wins against $Q$ is not actually an estimator of $D(P)-D(Q)$.

The relationship between "fraction of wins" vs $D(P)-D(Q)$ is probably not linear.  For example, Magnus Carlsen (world chess champion; rated about 2800) will beat me 100% of the time in chess.  He will presumably also beat Arnold Schwarzenegger (rated about 1500) 100% of the time.  But Arnold will probably beat me 100% of the time, too, because I suck at chess.  Letting $P_M = $ Magnus Carlsen, $P_A = $ Arnold Schwarzenegger, and $P_D = $ me, it can't be simultaneously true that $D(P_M)-D(P_D)=1$, $D(P_M)-D(P_A)=1$, and $D(P_A)-D(P_D)=1$, yet that is what your assumption implies.
Strategies usually aren't totally ordered.  Sometimes we have situations where one strategy is especially effective against another strategy (more than you'd expect based on their overall strength).  For instance, we can have situations where Alice usually beats Bob, Bob usually beats Charles, and Charles usually beats Alice.  Your framework doesn't take this into account.

You'll probably need more sophisticated methods to deal with these challenges.  For instance, one possibility is to build a small collection of different baseline strategies $Q_1,Q_2,\dots,Q_k$.  Then, evaluate $P$ according to how well it does against all of these: e.g., have $P$ play $n/k$ games against each $Q_i$, count the total number of wins for $P$, and divide by $n$.

This leaves open the question of how you select the baseline strategies $Q_1,\dots,Q_k$.  You might want each $Q_i$ to be as strong as possible, but also want to have some diversity in the pool, so $Q_i,Q_j$ are as different as possible for all $i,j$.  That requires a way to measure how similar two strategies $Q_i,Q_j$ are.  One way might be to play a game between $P$ vs $Q_i$; at each board position reached, compare how often $Q_i$ would select the same move as $Q_j$.  To select a collection of baseline strategies, you could try to solve an optimization problem where you select among the s policies you've explored so far, while maximizing some objective function that rewards selecting strong strategies but penalizes similarity between selected strategies.

There are probably many challenges here, but hopefully this gives you some ideas you can try out.


Binary strings such that the sum of 0's is not equal to twice the sum of 1's

Distinguish $n_0(w) < 2n_1(w)$ and $n_0(w) > 2n_1(w)$. That is, in your grammar for $n_0(w) = 2n_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.


Solved it, my question was badly formulated, I had only coordinates of points not the vertices themselves, I have calculated the perimeter using the euclidean distance formula.


Can the perceptron classifier achieve perfect accuracy, on any data set?

The use of a nonlinear kernel never gives any guarantees to make any data set linearly separable in the higher dimensional feature space. Kernels are used to map the data from input space onto a higher dimensional space, in which a hyperplane will be better at separating the data (but no guarantee for linear separable higher dimensional mapped data). That is why we can not be sure that perceptron algorithm will work correctly on higher dimensional mapped dataset or not.


Yes they are equivalent and it is always possible. Informally: you can exchange any $S$ move state with pair of states that goes $L$ then $R$ (or in the other direction).

Formally:
Prove that standard Turing Machine is equivalent to class of Turing Machines with $S$ (no move).
Let $M$ denote standard TM, there exists a TM $M'$ with no move option such that $L(M) = L(M')$. This way is trivial, simply do not use $S$ move in the extended version.
In the other direction:
Given TM $M'$ with no move option, construct equivalent TM $M$ such that $L(M') = L(M)$.
Construct new transition function $\delta'$ for $M$ such that for each state with move $\in \{L, R\}$ in $\delta$ there is equivalent state in $\delta'$.
For each $S$ move in $\delta$ put two states in $\delta'$.
So for $\delta(q_x, a, b, S, q_y)$ put two states to $\delta'$, $\delta(q_x, a, b, L, q_n)$ and $\delta(q_n, *, *, R, q_y)$. The $q_n$ matches the acceptance with $q_x$.  If the $S$ move was accepting state, make the second state accepting. This gives the equivalence in the accepting states and the head (heads) position.
$L(M') = L(M)$, so these classes are equivalent.


How to prove that sequences of stack operations are not context-free

The language is context-free. If we replace $\mathrm{push}(k)$ by $[_k$ and $\mathrm{pop}(k)$ by $]_k$ and delete the dots, then we get exactly all prefixes of a Dyck language with $N$ different types of brackets.


Egg dropping puzzle - clarification of problem statement

Imagine this as a game of two players: the experimenter vs. nature.

The egg breaking limit is not chosen in advance.
Instead, the players together form statements about its possible values, all the way until only one value remains.

On each turn, the experimenter chooses the floor from which to drop the egg.
After that, the nature chooses whether the egg actually breaks or not.

Of course, with some moves of the experimenter, nature can't choose because the previous statements already determine the outcome.
However, note that a good strategy for the experimenter does not make such redundant moves.

With such formulation, the "worst case" here is equivalent to the game-theoretic "if nature plays optimally", and "minimizing the number of moves in the worst case" to "if both play optimally".


The reason that $(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$ and not to $\lambda x. \lambda y.\lambda x.\lambda y.y$ is that the $y$ in the body of $\lambda y.\lambda x.\lambda y.y$ refers to the argument of the third lambda, not the first.

If you rename the arguments to have distinct names, $\lambda y.\lambda x.\lambda y.y$ would be written as $\lambda y_1.\lambda x.\lambda y_2.y_2$. So if you apply that function to the argument, that means that every occurrence of $y_1$ in $\lambda x.\lambda y_2.y_2$ should be replaced with the argument. However $y_1$ does not appear at all in that expression, so the argument is simply ignored and the result is just $\lambda x.\lambda y_2.y_2$.


Relation of deterministic push down automata and lower elementary recursion

No, that doesn't follow at all.  There are problems that can be solved in polynomial time, but that don't correspond to any deterministic context-free language.


Can only information(data) be stored in ram?

RAM is just a really fast hard disk (except the contents are usually lost if powered down). It can store anything you could store on a hard disk (programs, documents, pictures, temporary data,...).


Edit: This is a proof for the non-quantum version.

Suppose we want to compute $x \land y$ from $x,y,0,1$ using the operations NOT and CNOT (=XOR). Prove by induction that any such expression is equal to one of the following forms:
$$ 0,1,x,y,\lnot x, \lnot y, x\oplus y, \lnot(x\oplus y). $$
It is more helpful to write it in the form $ \alpha \oplus (\beta \land x) \oplus (\gamma \land y)$, where $\alpha,\beta,\gamma \in \{0,1\}$. Yet more helpful is to switch notation so that this expression is written $\alpha + \beta x + \gamma y$; this should be suggestive enough.


Repeated substitution

Repeatedly substitute in, and look for a pattern:

$$\begin{align*}
T(m,n) &= T(m/2,n/2) + T(m, n/2) + 1\\
&= T(m/4,n/4) + 2 T(m/2,n/4) + T(m, n/4) + 3\\
&= T(m/8,n/8) + 3 T(m/4,n/8) + 3 T(m/2,n/8) + T(m, n/8) + 7\\
&\vdots\\
\end{align*}$$

Do you see the pattern?  The coefficients $1,3,3,1$ should remind you of binomial coefficients.  The pattern is

$$T(m,n) = 2^k-1 + \sum_{i=0}^k {k \choose i} T(m/2^i, n/2^k).$$

You can prove that this holds for all $k$ (by induction on $k$).  Then, setting $k=\lg n$, we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} T(m/2^i, 1).$$

So it suffices to know how to evaluate $T(m,1)$ for all $m$.  That information cannot be deduced from the recurrence you gave us -- it needs to be supplied as additional base cases.

For instance, suppose we are given the base cases $T(m,1) = 1$ for all $m$.  Then we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} = 2n-1 = \Theta(n).$$

However, if we were given different base cases, the solution might be different.

Guess-and-check

Another approach is to somehow guess the solution (for instance, by playing with a bunch of examples and looking for patterns), and then check that it holds.  For your example, if we assume $T(m,n) = T(m/2,n/2) + T(m,n/2) + 1$ and we assume $T(m,1)=1$ for all $m$, then rubbing our rabbit's foot for luck, we might get lucky and guess

$$T(m,n) = 2n-1.$$

It is then easy to plug in and confirm that this is a valid solution to the recurrence you gave.

However, in general, guess-and-check is often very hard -- you can try many guesses, but sometimes it can be very difficult to find a guess that turns out to be correct.


What is the difference between "for infinitely many n" and "for all n"?

"for infinitely many input sizes $n$, $P(n)$ holds" means there are input sizes $n_1$, $n_2$, $\ldots$, (infinitely many) such that $P(n_i)$ holds for all $i$. In other words, for every integer $k$, there is an input length $n \geq k$ such that $P(n)$ holds.

In contrast, "for all input sizes, $P(n)$ holds" means that for every input size $n$, $P(n)$ holds.

Typically, "for all input sizes, $P$ holds" and "for almost every input size, $P$ holds" are used interchangeably, although the latter technically means that there is a $k$ such that for all input sizes $n \geq k$, $P$ holds. (Note that the negation of "for infinitely many input sizes, $P$ holds" is "for almost every input size, $\neg P$ holds.") This is generally because in the models of computation being considered, constant factors don't matter, so from an "almost every input size" statement you can generally hardcode the solutions for all inputs of length less than $k$ in your model, and get a "for all input sizes" statement.


Fundamental and essential matrices, value of intrinsic parameters

What are the intrinsic parameters good for?  They potentially allow mapping objects in the images to locations in the real world (in 3D).  For some applications, that can be very useful.  For instance, consider pedestrian detection, where we want to detect pedestrians.  Usually, it's not enough to detect the presence of a pedestrian: we also want to know exactly where the person is, and how far away they are.

Calculating alignment from a set of corresponding points is not an unreasonable approach to aligning two images.  The primary disadvantage is that you need a way to identify a set of corresponding points.  This typically requires either (a) explicit calibration or (b) heuristic methods.

Explicit calibration is a perfectly fine approach, if it is feasible for your application.  However, for some applications we only have images post-facto and we don't have any way to do an explicit calibration, so it's not always an option.

Heuristic methods are another possibility.  They try to find corresponding points, e.g., using Lucas-Kanade, optical flow, or other methods.  As heuristics, they are not guaranteed to work.  Sometimes they might fail to detect corresponding points, or output false detections.  Another issue is that their effectiveness depends upon characteristics of the scene that you're capturing: they're more effective for some kinds of scenes than others.  But this also could be a valid approach.

To be clear: 3D reconstruction requires two cameras (as mentioned in the question) or depth information; just one 2D camera plus its intrinsics are not enough to reconstruct where each object is in the real world, in 3D space.


A polygon is degenerate if some of its vertices lie on each other. e.g the triangle (0,0),(0,1),(0,0) is degenerate. It has 3 sides, and 3 vertices, but two of vertices repeat. It's possible to repeat a vertex multiple times (for example (0,0),(0,0),(0,0) is another degenerate triangle). By definition, checking whether a polygon is degenerate or not is easy.

But what are the uses of degenerate polygons? One application from graphic acceleration (3D drawing) is as follows:

In 3D drawing GPUs normally use triangulation to render images. The (simple) reason for using triangles is because they are simplest possible 2D objects so don't need much hardware.

If we want to draw a complex 3D image, by this GPU limitation, we have to decompose it into multiple triangles. But if we call the GPU to render each triangle separately, it would be very slow (because of the number of calls). So the triangle strip is used to reduce the number of calls to the GPU.  A good explanation of triangle strips can be found on Microsoft Documentation: Triangle Strips, also you can see the wiki for: Triangle Strip.

But the problem arises when we want to draw two separate objects in one strip. In this case degenerate triangles help. The GPU can detect the degenerate triangles and skip their drawing. So we can connect two separate strips with one degenerate triangle.

In general if we have $n$ different components, such that we already have their corresponding triangle strips, we can draw them all by just one call to the GPU. This causes to extra memory usage, but it is a trade off between the number of calls to the GPU for rendering and the overhead of using an extra, degenerate triangle.


The point is that we are not trying to find the global maximum element of the array, only a peak (that is, a local maximum).

Let's say that you look at the middle column and find its global maximum, and this maximum is not a peak, because the value to its left is larger. Then you know that the left half of the matrix contains a value that is larger than all of the elements of the middle column. Hence there is always a peak in the left half (for example, the global maximum of the left half, but we do not necessarily search for that).

The values in the right half are irrelevant; they could be larger or smaller, but we don't care. We only want to be sure that we do not recurse into a half that contains 0 peaks.


There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC).

Shannon's original formulation of GPAC could not compute certain functions, including the Gamma function. However, a 2007 paper cited in that Wikipedia article provides a reasonable reinterpretation of GPAC which turns out to be more powerful, enough so that the authors claim that "the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals."

Claude Shannon is well-known as a pioneer in digital computer design and particularly for his foundational work on information theory, but his genius and sense of whimsy led him to extraordinary achievements in other areas, and analog computation remained an interest throughout his life. One example is his mathematical analysis of juggling, including the construction of a prototype juggling robot. (See here for more information and a brief video including the robot.)


Are neural networks a type of reinforcement learning or are they different?

What is a neural network?

Neural networks are algorithms for function approximation. I like to call them a construction kit for functions. Their basic building block is a neuron, commonly visualized like this:

You can see the $n$ inputs $x_1, \dots, x_n$ ($x_0$ is typically constant 1), each multiplied with a weight $w_i \in \mathbb{R}$. This gets summed up and an activation function $\varphi$ (e.g. sigmoid $\varphi(x) = \frac{1}{1+e^{-x}}$) gets applied. So a neuron is a function

$$f(x_0, \dots, x_n) = \varphi(\sum_{i=0}^n x_i w_i)$$

The learning is just adjusting the weights $w_i$ automatically to something that makes sense in your context.

Now we can have arbitrary numbers of inputs $x_i$, but to have an arbitrary number of outputs we need more than one neuron. To get our model much more flexible, we stack them to a so called multilayer Perceptron (MLP):

So you can see, the output of one neuron (perceptron) can be the input of another! With backpropagation (a good implementation of gradient descent for this type of model) you can automatically adjust the weights.

What is reinforcement learning?

In machine learning you can distinguish 5 types of problems:

Regression: Predicting a continuous variable

You have a photo of a person and you want to tell how old the person is (e.g. howhot.io)

Classification: Predicting a variable with finite possible values

MNIST: You get a 28px x 28px image. You know it is either 0, or 1, or 2, ..., or 9. So a digit. You have to say which one.
ImageNet: You get a bigger image. You have to decide which one of a 1000 classes it is (dog, cat, car, house, ...). You can be sure it is one (and exactly one) of those.
http://write-math.com: Classify a handwritten symbol into about 380 classes
https://howhot.io/: Classify gender

Clustering: Grouping data

You have a lot of portrait images (or crops of images). You know there is exactly one persons face on it. You don't know how many people there are in total. Now you would like to group it so that each group is one person.
Species: You properties of animals and you want to group them. So you want a hierarchical clustering which puts closely related animals (dogs, cats; fly, moscito) closer together than not related ones (dogs, flys)

Collaborative Filtering: Filling gaps

Netflix: You have a lot of movies, a lot of ratings. However, not every person rated every movie. In fact, probably no person did. But you want to fill the gaps so that you can tell the users which movies they should watch because they will probably like it.
Amazon: pretty much the same as with Netflix, but for all kinds of products

Reinforcement learning (RL): Learning with environment

Self-driving cars
Playing games (e.g. Backgammon, Go, Atari (video))

What makes RL very different from the others is that you typically don't have a lot of data to start with, but you can generate a lot of data by playing. You have to deal with the problem that you have to make decisions, but it is not clear what is good (delayed reward). For example, it might take several moves until you know in Go if a move was smart.

What is different between neural networks and RL?

Neural networks are algorithms, RL is a problem type. You can approach RL with neural networks.

What is the relationship between neural networks and genetic algorithms?

Search for "the five tribes of machine learning", e.g. the image on http://www.welchlabs.com/blog/2016/2/16/whats-next-for-welch-labs


What is the system's mean time to failure?

For part 1, its simple. You need to find the $x$ (as defined below) for which MTTF(system) = 1.20M.

So $1.20 * 10^6 = \frac{1}{[(\frac{1}{6*10^6})*x]} \implies x = 5$.

We can have 5 disks (50 TB) if we want an MTTF(System) = 1.2M.

Part 2 is homework for you.


First-order logic arity defines decidability?

Logic with unary predicates (not operators), is called monadic. The thing that is called propositional logic only has nullary predicates, i.e., constants true and false, and no quantifiers.

The undecidability of predicate logic follows because predicate logic (with at least one binary predicate) is powerful enough to describe how a Turing machine works, and so we can express in the logic sufficiently complicated statements about Turing machines to get undecidability. In contrast, in monadic logic, where we only have unary predicates, we cannot describe the working of a Turing machine. I am being deliberately vague here to give an idea without getting bogged down in technicalities.


By definition, the dual code $C^\perp$ consists of all words $x$ such that $\langle x,y \rangle = 0$ for all $y \in C$. If $C = C^\perp$ then in particular $\langle x,x \rangle = 0$ for all $x \in C$, which implies that $x$ has even weight.


Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

Let $A'(L)= \{ w_1 \sharp w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ where $\sharp$ is a new symbol.

$A'(L)$ is the intersection of context-free language $\{ w_1 \sharp w_2: |w_1|=|w_2|\}$ and regular $L\sharp L^R$, therefore it is context-free. $A(L)$ is a homomorphic image of $A'(L)$, so it is context-free as well.

I prefer this proof to others as it is "higher-level".


How can Computer Science theories and inquiries be resolved?

Theoretical computer science, to which the questions you state belong, is part of mathematics, and the methods used to resolve questions are the same ones used elsewhere in math, namely the method of proofs. The questions you list are notoriously difficult, and seem to be out of reach for current methods.

In the past, the methods used to attack questions of the sort you describe were purely combinatorial. Recently, Ketan Mulmuley and his students have come up with a different method which employs representation theory (via some algebraic geometry), and is conjectured by them to be one day strong enough to resolve the P versus NP question. Currently, though, the only questions within reach of their methods are algebraic ones like permanent versus determinant rather than Boolean ones like P versus NP.

Since it is widely (though not universally) believed that P is different from NP, many results are proved conditional on this assumption. That is, they hold only if P is indeed different from NP. The area of hardness of approximation, which studies how well different combinatorial problems can be approximated in the worst case (in polynomial time), is a good example: all results in this area are conditional on P versus NP or on some even stronger assumptions.


FA for |w| divisible by 3 or number of zeros divisible by 2

Only six states are required. Indeed, you can accept the language of all words of even length using two states, and the language of all words whose number of 0s is a multiple of three using three states. Using the product construction, you obtain a DFA for your language using only six states.

We can easily show that six states are required using Myhill–Nerode theory, by considering the following six words:
$$
\epsilon,0,00,1,10,100
$$
Details left to reader.


What is the difference between directed graph and bidirectional graph?

As stated in the Wikipedia article, a bidirected graph is a graph where all edges have an orientation at both edges of the edge. The orientation is an arrow head. So in your example, it is not a bidirected graph because the edges only have orientation on one end.
The following would be an example of a bidirected graph. Notice there is an arrow head on both sides of each edge of the graph.

There are three types of edges of a bidirected graph.

Extroverted edge: arrow heads oriented outwards or towards vertices (e.g. $\{a,b\}$)
Introvert edge: arrow heads oriented inwards or away from vertices (e.g. $\{b,c\}$)
Directed edge: arrow heads oriented in one direction or away from one vertex and towards the other (e.g. $\{a,c\}$)

There are also loose edges (which have no orientation on either end) and half edges (which have orientation on one end).
Another use of bidirected graph is a directed graph where each edge has a matching edge going the opposite direction. Your example would not be a bidirected graph in this context either since there are edges that do not have the reverse direction (e.g. $(1,3)$ exists but $(3,1)$ does not). The following is an example of bidirected graph in this context.

Bidirected graphs are not common in my experience. This is just from a quick read of the Wiki article.

Bidirected graphs: https://en.wikipedia.org/wiki/Bidirected_graph
Directed graphs: https://en.wikipedia.org/wiki/Directed_graph


Optimize stacking time series by offsetting start times (feels like a backpack problem?)

I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it.
Let $c_1, \dots, c_n$ be the series data. For each valid start time $i$, create a variable $x_i$ to hold the number of copies to start at this time and add the constraint $x_i \ge 0$. For each minute of time $i$ (now also including the 8 hours' worth after all valid starting times), add the constraint $\sum_j c_{i-j+1}x_j \le 780$. Objective: Maximise $\sum_i x_i$.
Although this will make for a fairly large ILP instance, my feeling is that will be a "nice" one that can be solved to optimality quickly by a commercial solver like CPLEX or Gurobi. But in case it's not: Even a free LP solver will solve the LP relaxation of this without difficulty; rounding down the $x_i$ gives a feasible solution. If there are few variables $\ge 1$, so that rounding gives an unhelpful answer, you can always just remove some of the variables (I suggest removing the ones with the lowest values) and re-solve.


If you suspect that your solution is right, then try to prove it (since we are not dealing with foundations, e.g. how exactly is time represented in our system, the proof will be somewhat informal, but it is still a good way to convince yourself).

Claim 1: No more than one pair of follower and dancer can be at the dance floor concurrently.

This is obvious, since if we have one dancer and one follower dancing then both locks are acquired, and thus no more dancers are able to continue.

Claim 2: If a pair $(f,l)$ is dancing ($f,l$ are follower and leader correspondingly), no other dancers will be able to dance until both $f,l$ are done.

Obviously at least one of the dancers $f,l$ has to finish for others to be able to join (we need to release at least one lock). Suppose $l$ finishes first. More followers cant join unless $f$ is done (lock), so the next dancer has to be a leader. However, the next leader will be stuck waiting for follower_rendezvous, which will only be signaled when a new follower comes, and for that $f$ must finish dancing as well (to release the lock).

Claims 1,2, together with the observation that a pair of follower and dancer are able to dance concurrently, concludes the proof.


Given an non-deterministic finite automaton, will its determinization always have unreachable states?

No, there aren't always unreachable states.  Consider the NFA with one state, $q$, and no transitions.  (It accepts the language $\{\epsilon\}$ if $q$ is accepting, and accepts $\emptyset$, otherwise.)

If you determinize this automaton, you end up with a two-state DFA with a transition from the start state $\{q\}$ to the other state, $\emptyset$, so both states are reachable.


Quadratic Diophantine equation - Polynomial Time Cases

You shouldn't expect a complete characterization of all parameters that can be solved in polynomial time, but here are two cases where it can be solved in polynomial time:

If $b$ is prime, you can solve this in polynomial time by letting $x = \sqrt{c/a} \pmod{b}$ and then $y=(c-ax^2)/b$.  You can compute modular square roots in polynomial time by standard methods.

If $b$ has known factorization, similar methods can be used (use the Chinese remainder theorem).

Dealing with the requirements $x\ge 0,y \ge 0$ (which were added to the question after I wrote this answer) is more challenging.  When $b$ is prime, you can enumerate both modular square roots and see if either of them leads to a valid solution.  When $b$ is not prime but has known factorization, in the worst case this might require enumerating exponentially many modular square roots (though you might be able to randomly sample a few square roots and hope that at least one will lead to a positive solution).


Minimum path - robot motion problem combined with freeze tag problem

Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot to move from one position to the other.  The edge lengths can be computed using the A* algorithm or any other pathfinding algorithm.

Now I think you want a rooted spanning tree $T$ for the graph $G$, with the following properties:

The root of the tree is the vertex that corresponds to the initial position of the awake robot.
Every node of the tree has two children, except for the root, which has one child.
The tree is a spanning tree, i.e., every vertex in $G$ appears somewhere in the three.
The "duration" of the tree is minimal among all such trees.

Here we define the duration of a tree to be the maximum of the lengths of all path from the root to some leaf.

I don't know whether there is an efficient algorithm to find such a tree.


What does distinct mean in terms of an array?

Yes you are right..
An array is distinct if it contains unique elements i.e. no duplicates


Converting Mathematical Statements to SAT Formulas

If you want to know whether there exists a general method/algorithm which can convert any given mathematical statement (by which you mean statements written in logic (say first-order logic, second-order logic ... etc)) to a SAT formula which is True iff that statement is True, then the answer is No.

The reason being that evaluating whether an SAT formula  is true or false is decidable (in exponential time if not faster), whereas these logics are usually undecidable. So, no such algorithm can exist.

Of course, there are logics which are decidable, and the statement of those logic can be converted to SAT formula (maybe trivial ones like True or False as mentioned by @D.W) by a specific algorithm. See: http://www.lsv.fr/~haase/documents/h18.pdf


Amortized time cost of insertion into an Array list

For the estimate,
$$
n + \frac{n}{2} + \frac{n}{4} + \cdots +1 <n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n,
$$
since $1 + 1/2 + 1/4 + \cdots = 2$.

If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the definition of amortized time. (More accurately, the amortized time is at most $K$ if $n$ insertions take at most $Kn$ time, for every $n$.)


Generate integer from 0 to 1 with equal probability

Yes, this is exactly rejection sampling and it works in the way you think it works, assuming that your initial procedure gr_04() generates the numbers $0$–$4$ with equal probability (you say it's random but you don't say it's uniform).

If $X$ is distributed uniformly on $\{0, \dots, 4\}$, then $\Pr(x\in\{0,1\}) = \Pr(x\in\{2,3\}) = 2/5$. With probability $1/5$, you'll have to try again but, on your second attempt, the probability of getting $0$ or $1$ is still equal to the probability of getting $2$ or $3$.  The number of attempts you have to make before you get something in $\{0, \dots, 3\}$ is just a geometric random variable with parameter $p=4/5$ and this has expectation $(1-p)/p = 1/4$ so, on average, you'll have to make $5/4$ calls to gr_04(), including the one that succeeds.

The analysis of your second example is similar: your procedure generates each possible answer with the same probability and each attempt succeeds with probability $7/8$, so you'll need an average of $8/7$ calls to gr_01(), which means an average of $(8/7)(5/4)=10/7$ calls to gr_04().