Is it decidable whether a given context free grammar generates an infinite number of strings?

Let $G$ be a context free grammar, and let us assume that it is in Chomsky normal form. If it's not, we'll convert it first. An important property of this normal form is that the only way to derive the empty word is with the single rule $S_0\to \epsilon$ (where $S_0$ is the initial variable, which cannot be derived from other variables).

Thus, any other derivation adds some non-trivial part to a word.

Now, let $n$ be the number of variables in the grammar, and let $k$ be the maximal length on the right-side of a derivation rule. That is, $A\to B_1\cdots B_k$ is the maximal length. We are going to show the following theorem:

  $G$ generates an infinite word iff it generates a word of length at least $k^{n+2}$.

Consider some word $w$ generated by the grammar, and a derivation tree for it. The derivation tree has branching factor of at most $k$, and thus it needs to be of height at least $\log_k |w|$ in order to derive $w$.

Take a really long word $w$. Just how long? take $w$ of length $k^{n+2}$. Then, every derivation tree of $w$ requires at least height $\log_k(k^{n+2})=n+2$. That means that there is some path in the tree of length $n+2$, and on this part there is some variable that repeats (since there are only $n$ variables). We can assume that the derivation from this variable derives other things besides itself, otherwise we can shorten the tree.

Now, you can "pump" the word $w$ to infinitely many other words that are generated, by repeating the subtree of the variable that derives itself.

If this sounds complicated, take a look at the pumping lemma, it's the same idea.

So now what? Well, take your grammar, and "remove" from it all words of length less than $k^{n+2}$ by intersecting it with a regular language of all words of length at least $k^{n+2}$, and check if the resulting grammar is non-empty. If it is, the original grammar generated an infinite language, and otherwise - a finite language.


Design Hashing function from known distribution of bits to be set

There are 224,723,513,575,448 possible 64-bit bit-strings which satisfy the constraint that there are between 3 and 15 one-bits (inclusive). That number is approximately 247.675, so it could be represented in 48 bits. This compression is not particularly difficult, but it is much slower than the Murmur3 mixing algorithm you cite, whose speed seems to be a concern.

In any event, the compression won't really help you much (if at all). A good hash function will produced unbiased distribution of hash values for any subset of possible inputs; such hash functions are theoretically possible and, with appropriate caveats, practically achievable. (Tabulation hashing is a simple and effective technique, which is provably independent provided you have an appropriate source of randomness. But unless you have special requirements, you are probably better off using an existing hash library which has been tested and found to be unbiased.)

In practice, the C++ standard does not prescribe any particular hashing algorithm nor does it prescribe any particular mapping from hash values to buckets for unordered associative containers (there is no such thing as a std::ordered_map; there are std::map, which is ordered and therefore not a hash table, and std::unordered_map, which is a hash table). The implementations of the C++ standard library I know of use the identity function for hashes of all integer types. (Hash values are of type size_t, which means that values larger than the capacity of a size_t will be reduced modulo the size of a size_t; that will be the case for a 64-bit key on most 32-bit architectures.) Since that is likely to produce biased results in your case regardless of how the hash values are mapped to buckets, you probably are well-advised to use a specialized hash function, at least if you expect the hash tables to be large.


Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial

You are correct that a term was omitted in the RHS of (2.3.10), but the final asymptotic bound $O(\phi^n)$ holds for the augmented RHS also. Perhaps it might be easier for you to see this if you just work out the solution for the nonhomogeneous recurrence relation from scratch rather than use Wilf's Theorem 1.4.1 on the epsilons, as shown below.  Essentially, we are  adding a linear term $an+b$ to the exponential $\phi^n$, which gives $\phi^n + an+b = O(\phi^n)$, where $\phi$ is the golden ratio.

More specifically, suppose that before the two recursive function calls to the chrompoly function, the edge set needs to be modified, and for the given value of $\gamma = |V|+|E|$, the cost for modifying the edge set is $\gamma$.  (You can also take this cost to be $c \gamma$ for some other $c$, if you wish.)

Then, the recurrence $h(n) = h(n-1)+h(n-2)+n$ needs to be solved.  From the theory of linear nonhomogeneous recurrence relations, the solution $h(n)$ is the sum of a generation solution and a particular solution, where (1) the general solution has the form $h_1(n) = c_1 \alpha^n + c_2 \beta^n$, where $\alpha , \beta$ are roots of the characteristic equation (one of them containing the golden ratio), and (2) the particular solution has the form $h_2(n) = an+b$ because the nonhomogeneous part is polynomial of degree $1$. (If the nonhomogeneous part was $7n^2 3^n$, then the particular solution would take the form $(an^2+bn+c)3^n$. If $3$ was a single root of the characteristic equation, then the particular solution would take the form $n(an^2+bn+c)3^n$. If $3$ appeared as a root with multiplicity $m$, then the extra factor would be $n^m$.)

Thus, $h(n) = O(c \phi^n +an+b) = O(\phi^n)$ because the linear terms grow more slowly than the exponential and can be ignored in asymptotic notation.


(OCR ) How to Recognise Handwritten fractional numbers using Neural networks

Usually one of the steps is "segmentation", where we separate the image into smaller images, one for each character/symbol.  Thus the fraction "1/13" would have four character, "1", "/", "1", and "3".  Then, you apply a neural network separately to each of those four smaller images.

See https://en.wikipedia.org/wiki/Optical_character_recognition for an introduction.  OCR is covered in many standard sources.  I suggest reading the literature on the subject to learn more about standard methods.


You can use "arithmetic decoding". Interpret your random data as a random bit stream which encodes a random number between $0$ and $1$. Then write this number in base $B$.

A much simpler method is "rejection sampling". Suppose for example that $128 < B < 256$. Given a random byte $x$, if $0 \leq x < B$ then output $x$, otherwise reject. If $x$ is close to $256$ then this is pretty efficient. (To get higher efficiency, try the same trick with some power of $B$, i.e. output several digits at once.)


Efficient lookup when key is made of multiple elements and elements can be empty

This is the problem of building a data structure for storing rectangles in $m$-dimensional space, so you can answer stabbing queries efficiently.

For instance, if your keys have 4 elements, then we are in $m=4$ dimensions.  The key $(1,5,6,3)$ corresponds to a single point in 4-dimensional space.  The key $(1,?,6,3)$ corresponds to a line in 4-dimensional space.  The key $(2,?,?,?)$ corresponds to an (infinite) box in 4-dimensional space.

So, in general, each key can be thought of as an (axis-aligned) box in $m$-dimensional space.  A query is a point in $m$-dimensional space, and you want to find all boxes that contain that point.  That is sometimes known in the literature as a "stabbing query" (particularly when we're talking about intervals, i.e., $m=1$).

There are many data structures for this problem.  Take a look at R-trees, for example.  You can also look at $m$-dimensional segment trees.  It is known that you can build a $m$-dimensional segment tree in $O(n (\lg n)^m)$ time and $O(n (\lg n)^m)$ space; each lookup can be answered in $O(k + (\lg n)^m)$ time, where $k$ is the number of entries that match the query.  Thus, segment trees will likely be a good representation if the dimension $m$ is small.  (Optimizations: The exponent can be reduced slightly from $m$ to $m-1$.  There are also special algorithms that achieve even better performance in the case of $m=2$, $m=3$, or $m=4$.)

See also Data structure to hold list of rectangles?.


This language is decidable.

Hint: If you are allowed to run for only $i$ steps, what can you do with input of size $j>i$?


How to transform a Infinite decimal of $\frac{23}{6}$ into binary?

Here is a hint by example.

$\frac{23}6 > 2$
$\frac{23}6-2 = \frac {11}6 > 1$
$\frac{11}6-1 = \frac {5}6 > \frac 12$
$\frac{5}6-\frac12 = \frac {1}3 > \frac 14$
$\frac{1}3-\frac14 = \frac {1}{12} > \frac 1{16}$
$\vdots$

So $\frac{23}6=2+1 +\frac12+\frac14+\frac1{16}+\cdots=(11.1101\cdots)_2$

Exercise. How to determine the period of the fraction part of the binary expansion of $\frac {23}6$?


It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$
CFP(n,A) =
\begin{cases}
False& \text{if }A=[\;]\\
True& \text{if } first(A) + last(A) = n\\
CFP(n,tail(A))&\text{if }first(A)+last(A)<n \\
CFP(n,init(A))&\text{otherwise}
\end{cases}
$$
where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:

|A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:

$A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
$A_j = last(A)$: Analog to the previous case.
$first(A)<A_i\leq A_j<last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.


Meaning of Free (Arbitrary Abstract Algebra Term)

Yes, and in fact there is even a general notion of an algebraic theory, and thus algebraic object. An algebraic theory consists of:

a sort
constants and function symbols
algebraic axioms, that is universally quantified sentences which may contain equality, but no other logical symbols (ie. $\exists,\vee,\to,\neg$)

It is worth noting that the theory of fields is not algebraic, thus there are no free fields.
So the theory of monoids $\mathcal M$ has a sort $M$, constant $e : M$, function symbol $\mu:G\times G\to G$, and axioms

$\forall x.\mu(x,e)=x$
$\forall x.\mu(e,x)=x$
$\forall x,y,z.\mu(\mu(x,y),z)=\mu(x,\mu(y,z))$

In general, given an algebraic theory $T$ we may consider the set of terms in this theory. Categorically, a free algebra for $T$ is the initial object in the category of algebras for $T$. The standard way to construct the free algebra is to take the term model for $T$, that is the underlying set of the free algebra is the set of terms of $T$ modulo the equivalence relation generated by the axioms of $T$.
So what we mean by a free structure in the theory $T$ generated by the set $B$, is to consider a free algebra for the theory $T_B$ containing an additional constant symbol for each element of $B$.
This description is concrete but a bit complicated. There is a much simpler but more abstract construction using the theory of monads, because an algebraic theory corresponds precisely to a monad.

An example for monoids in a functional programming language could look as follows, by interpreting the theory of monoids as a monad:
type 'a mon =
| Id
| Bin of 'a mon * 'a mon
| Var of 'a

let return (x : 'a) : 'a mon = Var x

let rec bind (x : 'a mon) (f : 'a -> 'b mon) : 'b mon =
match x with
| Id -> Id
| Bin (s,t) -> Bin (bind s f, bind t f)
| Var u -> f u

let rec eq (a_eq : 'a -> 'a -> bool) (s : 'a mon) (t : 'a mon) : bool =
match (s,t) with
| (Bin (Id,u), v) | (Bin (u,Id), v) | (u, Bin (Id,v)) | (u, Bin (v,Id)) -> eq u v
| (Bin (Bin (u1,u2),u3), v) -> eq (Bin u1, Bin (u2,u3)) v
| (u, Bin (Bin (v1,v2),v3)) -> eq u (Bin v1, Bin (v2,v3))
| (Id,Id) -> true
| (Bin (u1,v1), Bin (u2,v2)) -> (eq u1 u2) && (eq v1 v2)
| (Var x, Var y) -> a_eq x y
| _ -> false

type two = A | B

let two_eq x y : bool =
match (x,y) with
| (A,A) | (B,B) -> true
| _ -> false

Then the type two mon with relation eq two_eq gives the free monoid on two elements.
The function return : two -> two mon gives us the two generators return A and return B.
The function bind : two mon -> (two -> 'b mon) -> 'b mon tells us that a map from the free monoid on two elements to another (in this case free) monoid is uniquely determined by what the elements of two are mapped to.


What happens when the words transfered on the bus are smaller than its width?

I would say "it depends":

most likely you ask for 8 bits to be retrieved and you get 8 bits and ignore the other 24 lines;
if you know you're dealing with sequential data, that you want to consider bytewise, you could retrieve 4 bytes at a time, but you'll have to split or handle the retrieved 4 bytes in code.

On specific architectures you have alignment considerations.

Specifically addressing your question, no, it is very unlikely a system would retrieve 4 words in each cycle only to then "split" them into single words to process, without a program catering for that itself.


Non-Deterministic FSA to Deterministic FSA, Two initial states

The powerset construction converts an NFA to a DFA. You then "optimize" the result by removing states which cannot be reachable from the start state. When the NFA has multiple starting states, you do exactly the same thing. The starting state of the new DFA is the state corresponding to the set of starting states in the NFA (compare that to the usual case, in which the starting state of the DFA is the signleton consisting of the starting state of the NFA).

Given a DFA, you can compute the set of reachable states iteratively: the starting state is reachable; any state which it points to is reachable; any state which these point to is reachable; and so on. (Technically, this is known as BFS. There are also other algorithms, such as DFS.)


What algorithm should I use to find a minimal tree that include certain nodes within a graph?

This is the famous Steiner tree problem in graphs, which is known as NP-hard.


Let me answer your concrete questions:

An oracle is a language. One way to describe a language is to give a procedure for constructing it.
The construction is not a counterexample to P=NP. It shows that there exists an oracle relative to which P and NP are different. It also gives another oracle relative to which they are the same. Later, it was shown that P is different from NP relative to a random oracle (almost surely); recently this was extended to the entire polynomial hierarchy. The modern interpretation of such results is that diagonalizing techniques (techniques that would also work relative to an arbitrary oracle) cannot be used to settle the P vs NP question.
"Run query machine $P_i$ with oracle $B_i$ on input $x_i = 0^n$" has the following meaning. The machine $P_i$ is an oracle machine — it is a Turing machine that has a special mechanism allowing it to access the oracle. We run $P_i$ on the input $0^n$, i.e., the string of length $n$ consisting entirely of zeroes. Whenever $P_i$ makes an oracle access, we answer according to $B_i$.
Your final question is a bit specific. I suggest trying to read the proof again, and if you fail, check a more modern account. Note that the result can be proved in several ways, so a proof appearing in a different source might be different.


I really can't explain it better than Wikipedia does:

Suppose you want to traverse a tree. You can traverse it in a serial manner by walking the tree (either recursively or otherwise), or you can traverse it parallel by starting at $N$ leaf nodes and following the shortest path to the root.

In the serial case your running time will be $O(n\log(n))$.
$n$ is because you need to visit all $n$ nodes and $\log(n)$ because of extra time spend going up and down the tree because you can only reach sibling nodes via their parent.

In the parallel case your best running time will be $O(\log(n))$ or more accurate $O(\frac{n}{m}\log(n))$ where $m$ is the number of threads used.
You do this by assigning a leaf node to a thread and finding the shortest path to the root.
If you have more leaf nodes than threads you'll assign more than one leaf node to a thread.

Because the height of a tree is $\log(n)$ the running time per thread is obviously $O(\log(n))$.
This is not as efficient as can be, because the closer you get to the root the more nodes will get visited more than once.
You can solve this issue by having the first thread to arrive at a parent to leave a breadcrumb after which subsequent threads drop out.
If you elect to let duplicate threads drop out of the traverse, you also solve the problem of thread synchronization issues when altering data in the tree.


Construct a Circuit computing all boolean functions over n bits

Given the circuit $C_n$, you can compute $C_{n+1}$ using $O(2^{2^{n+1}})$ additional gates. Indeed, each output gate of $C_{n+1}$ is of the form
$$
(\lnot x_{n+1} \land y_i) \lor (x_{n+1} \land y_j)
$$
for some $i,j$, so can be computed from the outputs of $C_n$ using $O(1)$ additional gates.

In total, the circuit $C_n$ uses $O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$ gates.


How would I write an if-statement in continuation passing style without an if-statement?

I think you are over-attributing things to CPS.  First, CPS lets you model exceptions, generators, and functional calls, but it doesn't create them.  For example, modeling exceptions with CPS only gives me exception-like behavior in code that is itself in CPS.  I can, of course, use CPS as an implementation mechanism, an intermediate language, for exceptions or generators.  Compare this to a language with first-class continuations, e.g. Scheme's call-with-current-continuation.  With that, I could implement exceptions as a library.

Second, recursion gives you loops, not CPS.  If you had a language which couldn't express recursion nor had built-in loops, CPS transforming would clearly not change this.  You also don't need CPS to express loops as recursion, though it may be useful for things like break and continue.

To address your specific question, in some sense if is part of the definition of booleans.  If you want to do anything non-trivial with a boolean, you must at some point use if.  You could choose a different, non-abstract representation of booleans via their Church encoding, but converting the "native" booleans to this representation would require if, and at any rate this would just be word play.  While our if-cps would not require using if in this representation, this would only be because if is represented by the identity function in this representation.  Or to put it another way, we are using this representation's if.


$w$ is an input word, $r$ is a random bits used by a machine to make random decisions.

So, it is obvious that $P \subseteq BPP$, so let's try to show that: $BPP \subseteq P$.

Let $L$ in $BPP$. Then $M(w, r)$ be a machine that decides $L \in BPP$. $M$ is a polynomial probabilistic machine. Let $M'(w, r)$ be an polynomially amplifcated $M$, so:
$$w \in L \implies Pr[M'(w, r) \text{ accepts }w] \to 1$$
$$w \not \in L \implies Pr[M'(w, r) \text{ rejects }w] \to 1$$

Now, we construct machine $M_p$ that recognizes $L$ and works in polynomial time.

Let $w$ be a given word to decide. $M_p$ constructs in polynomial time a boolan circuit $C$ equivalent to $M'(w,r)$ where $w$ be hardcoded in that circuit. So, the input word is a random string, $r$.

Note, that our machine $M_p$ So, for a random input  $r$ our machine for word $w \in L$ must accept it if $M'$ accepts it with probability $\approx 1$.

But, we must show that $L \in P$ so we cannot use a random word $r$.

Instead, we would like to ask our algorithm about probability of acceptance a random word: $A(C)$. The returned value must be $\approx 0.6$ because possible error is $0.4$. So, if A(C) is $\ge 0.6$ then $M_p$ accepts, else rejects.

It works in polynomial and it accepts the same language:

$$w \in L \implies Pr[M' \text{ accepts w is }] \approx 1 $$
$$w \not \in L \implies Pr[M' \text{ rejects w is }] \approx 1 $$


Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings $S$ and $T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest.

One way to detect if a sequence forms a valid balanced parenthesis is to change ( for +1 and ) for -1 and check that the sum of every prefix is non-negative $(P_i \geq 0)$ and the sum of the entire sequence is $0$ ($P_n = 0)$. We define $P_i$ as the balance of the $i$-th prefix.
To compute the largest valid subsequence you can keep track for each prefix $i$ what is the largest valid subsequence of that prefix with a fixed balance $b$: $(Q_i^b)$. The answer to your problem is $Q_n^0$.
Fortunately $Q_i^*$  only depends on the $i$-th character and $Q_{i-1}^*$ so we can use dynamic programming to compute such values. Let's define for the sake of simplicity that for states such that no valid sequences exist the value of $Q_i^b = -\infty$.
The base case for empty prefix $i = 0$.

$Q_0^0 = 0$: The largest valid subsequence for the empty prefix is the empty string (size=$0$) which has balance $0$.
$Q_0^b = -\infty$: For all balance different than $0$ there is no such string that is subsequence of the empty prefix with balance $b$, so we use $-\infty$.

Let's define transitions to compute each value given that all previous values (with less $i$) are already computed. On each step we either append that character to the end of the subsequence, or we discard that character:
$$Q_i^b = \max(Q_{i - 1}^b, Q_{i - 1}^{b - s[i]} + 1)$$
The first term in the $\max$ expression cover the case that we don't use the last character, so the maximum subsequence with balance $b$ and prefix $i$ is at least as large as the maximum subsequence with balance $b$ and prefix $i - 1$.
The second term in the $\max$ expression cover the case that use the last character, notice that $s[i] = +1$ if there is an open parenthesis ( at position $i$, or $s[i] = -1$ otherwise. Then the new balance will be $b$ if in the previous step the balance was $b - s[i]$, so after adding the $i$-th character it becomes $b$.
We should only compute $Q_i^b$ values for $b \geq 0$, to keep the balance of the sequence always non-negative.
In practice we know the balance won't be larger than $n$ (in fact it won't be larger than $\frac{n}{2}$) so we can compute values of $Q_i^b$ for $0 \leq i \leq n; 0 \leq b \leq n$. Each transition is computed in $O(1)$ so the overall complexity of this solution is $O(n^2)$. Since states $Q_i^*$ only depend on states $Q_{i -1}^*$ we can use only $O(n)$ memory keeping at each moments two rows of the dynamic programming table.

To find a subsequence of two strings $S$ and $T$ we can instead use a dynamic programming state with $3$ dimensions: What is the maximum valid parenthesis sequence with balance $b$ which is a subsequence of prefix of length $i$ from $S$ and prefix of length $j$ from $T$ ($R_{i,j}^b$). The answer is $R_{|S|, |T|}^0$.
The solution is almost the same but transition should be modified to address the new constraint:
$$R_{i, j}^b = \max(R_{i - 1, j}^b, R_{i, j - 1}^b, R_{i - 1, j - 1}^{b- S[i]} \cdot [S[i] == T[j]])$$
The first two terms inside $\max$, handle the case where the best sequence with balance $b$ of prefixes $i$ and $j$ from $S$ and $T$ don't use the last character for both, so at least one of them is not used, and we cover both situations.
The third case is trickier, it handles the case where we do use the last character, but we can only use that character if both character are the same $S[i]$ and $T[j]$, since we most find a common subsequence.
Note about complexity: Now complexity is $O(n^3)$ since that is the number of states and each state is computed in $O(1)$. Again, we can apply a trick to use $O(n^2)$ memory, however it is very tricky to do that and also being able to recover the answer.
In practice: The problem have $n=700$ and time limit $3.5$ seconds. Notice that the number of operations you are doing are roughly $\frac{700^3}{2}=171500000$ basic operations. A modern machine should perform roughly $1e8$ basics operations per second, so this solution should fit in time.
However, to recover the answer you should store for each state, the optimal decision. Notice there are only 3 options, so it fits in 2 bits. It requires $\frac{700^3}{2} \cdot 2$ bits which is $~42MB$. However, if instead of bits, a byte is used to store each decision, the the code will use $\frac{700^3}{2}$ bytes which is $171MB$ and is greater than the limit $128MB$.


How to find out the complement of a language of turing machines?

You cant find the complement of a $TM$ for undecidable languages.
A decidable language is such that a $TM$ which recognizes language membership, always halts with a yes. In this case finding the complement of the machine is simple, just reverse the yes with the no, obtaining the complement of the original decision problem. I leave to you
the task of determining whether the language of your example is decidable or not.

HINT:
you can compare it with the Halting problem or $ATM$


Restricting possible permutations in Graph Isomorphism problem

It's GI-complete.  Here's a simple reduction.  Let $G_0,H_0$ be any two connected, undirected graphs on $n$ vertices.  Consider the vertices of $G_0$ as even-numbered vertices of $G$, and add $n$ odd-numbered vertices that aren't connected to anything. Construct $H$ from $H_0$ similarly.  Now $G$ is vertex-pair-isomorphic to $H$ if and only if $G_0$ is isomorphic to $H$, so solving vertex-pair-isomorphism is at least as hard as solving graph isomorphism.


For all three of your statements, the answer is that, generally speaking, the implications simply aren't as intuitive as, say, the associative laws. Look at the analogous problem with algebraic expressions: we have associative laws for addition and multiplication and we also have a distributive law that states that for any expressions $p,q,r$ we have
$$
p\cdot(q+r)=(p\cdot q)+(p\cdot r)
$$
Eventually, these rules should be intuitively obvious. However, one implication of these rules, that
$$
(p+q)^3=p^3+3p^2q+3pq^2+q^3
$$
is probably not as intuitively obvious as the rules used to derive that identity. The utility of the result above is that it can be used as a tool to simplify other more complicated problems.

It's the same for regular expressions: the fact that, say, $r(sr)^*=(rs)^*r$, is correct can be proven rigorously, but having done that you can use it as a tool to show that
$$
aa+(aab)^*aa=aa+aa(baa)^*=aa(\epsilon+(baa)^*)
$$
should you ever need to. For example, there is a handy technique, involving what's known as Arden's lemma that can be used to produce a regular expression describing the language accepted by a finite automaton. Depending on how it's applied, this can produce several regular expressions from the same FA, so it might fall to you to show that the expressions are indeed equivalent, in which case the "implications" you listed might be handy.

The upshot (here's the tl;dr part), is that the implications you mentioned are simply tools you can use when needed: they've beed proven to hold, but there's no reason why they should be intuitively obvious.


About independent set in triangle free graphs

The point is that the graph is triangle free, so if $j$ and $k$ are both neighbours of $i$, then the edge $\{j,k\}$ is not in the graph.  This means that $N_i = \{j : \text{$i$ is a neighbour of $j$}\}$ is an independent set for any $i$.

The other fact being used is that a graph with $n$ vertices of maximum degree $\Delta$ has an independent set of size at least $\lfloor n/(\Delta+1)\rfloor$.


What would happen if we added this rule to red-black trees?

Yes it stays $O(\log n)$. Compared to the proof of the original one, we have no three red consecutive on a path from the root to a leaf. The bound on the blacks stays the same in a path. The length of the path is now at most three times the number of blacks which is at most $3O(\log n)=O(\log n)$.

The insertion changes indeed. Now we have strictly more cases, since we are supposed to regard two levels up in the tree after inserting and rotating. However, I think a case distinction suffices as well similar to the one in the original r-b trees.


Comparing the complexity of algorithms for listing k-cliques

$O(m \cdot \frac{(2a)^{k-2}}{(k-2)!})$ is not necessarily better than $O(m \cdot a^{k-2})$, since the big-oh notation $O$ is an upper bound. To compare the two algorithms, you'd better analyze using the $\Theta$ notation. In addition, note that if you set $k$ to some fixed value, terms such as $\frac{2^{k-2}}{(k-2)!}$ are considered to be constants and thus omitted in asymptotic analysis.


Is this possible to solve 3SAT in O(n^24) time and O(1) space?

You are correct in your assumption that your algorithm correctly identifies some unsatisfiable instances, but for the general case it does not work.

For instance, you can always rewrite a clause $\{A, B, C\}$ to the equisatisfiable clause set $\{A, X, Y\}, \{\neg X, A, B\}, \{\neg Y, B, C\}$. To see this, observe that you can always recover the original clause through resolution. If applied to say, the first clause in the above example, this will already break your algorithm.

Maybe someone with more knowledge on SAT can give some more insightful information.


Efficient algorithm for assigning weights to nodes in graph to create steady state flow

I will assume, that all weights are rational (since there is a problem with representing irrational numbers on computer).

You can solve this problem by using linear programming in similar manner to finding maximal flow.

$\forall_{v \in V} w_V$ is constant.

$\forall_{e \in E} w_e$ is variable.

Firstly, for each node we want to be sure that inward flow is equal to outward flow:
$$\forall_{v \in V} \sum_{(v_{i}, v)\in E}w_{v_{i}}w_{(v_{i}, v)} = \sum_{(v, v_o)\in E}w_{v}w_{(v, v_o)}$$

Then we want to be sure, that every edge is non negative:
$$\forall_{e \in E} w_e \geq 0$$

You can notice, that if there is any non-trivial solution then there are infinitely many, arbitrary large flows (you can multiply weight of every edge by constant $c$ and it will be still valid). So if there is any non-trivial solution, then there is a solution with sum of weights of edges not smaller then 1:
$$\sum_{e \in E} w_e \geq 1$$

Now what's left is to check if there is a solution for this linear programming instance.


How to find all the contiguous subsequence of an array is less than O(N^2) time complexity?

A contiguous subsequence satisfies your conditions if either it consists only of odd elements, or it contains one number which is a multiple or 4, or it contains two numbers which are multiples of 2. This suggests computing the following quantities:

$X$: Number of contiguous subsequences consisting only of odd elements.
$Y$: Number of contiguous subsequences containing an even element.
$Z$: Number of contiguous subsequences containing no element which is a multiple of 4, and exactly one even element which is not a multiple of 4.

You are interested in $X+Y-Z$.

To determine $X,Y$, it suffices to partition the elements into odd (O) and even (E). If your sequence is of the form
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
then
$$
X = \sum_{i=1}^{r+1} \binom{\ell_i+1}{2}, \\
Y = \sum_{1 \leq i < j \leq r+1} (\ell_i+1) (\ell_j+1).
$$
In order to compute $Y$ quickly, note that
$$
2Y = \left(\sum_{i=1}^{r+1} (\ell_i+1)\right)^2 - \sum_{i=1}^{r+1} (\ell_i+1)^2.
$$

In order to compute $Z$, we first separate our sequence by breaking at every element which is a multiple of 4. If $Z_j$ is the number of $Z$-type contiguous subsequences in the $j$th subsequence, then $Z = Z_j$. We can write the $j$th subsequence as
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
just as before. We then have
$$
Z_j = \sum_{i=1}^r (\ell_i+1) (\ell_{i+1}+1).
$$
In total, the algorithm runs in linear time.

Disclaimer: Verify that the formulas work – they might be slightly off, but the general idea should work.


Recursive definition of a language given the regular expression

Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction.

$B=\{\epsilon\}$

$\mathcal{F}=\{X\to0X|10X|X1\}$

$L_1 = \langle B \rangle_{\mathcal{F}}$


Language that system calls are implemented in

System calls are usually implemented in C (or at least that used to be the case) mixed with assembly language. That said, everything gets translated eventually to machine code.


$\mathsf{co\text{-}NP}$ and Cook reductions

Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite.

This shows that Cook reductions are not sensitive to the difference between NP and co-NP. Karp reductions are, and that's why we use them in the usual definition of NP-complete. (If we were only interested in P vs. NP, Cook reductions would be fine.)


The barbers paradox first order logic formalization

You're not being asked to do any inference; just to express something.

  there exists a barber who shaves all the people that don't shave themselves

translates directly as

$$\exists b\, \forall x\,\big(\neg S(x,x) \rightarrow S(b,x)\big)\,.$$

(There exists a barber such that everyone who doesn't shave themself is shaved by the barber.)

Your version says that there exists a person who, if they don't shave themself, is shaved by the barber. That's not equivalent. For example, it's true in any world where at least one person does shave themself: just let $x$ be that person, so $\neg S(x,x)$ is false, so $\neg S(x,x)\rightarrow\text{anything}$ is true.


What is wrong with this conditional proof of P=NP?

Suppose L=P. Let A be a problem in NP. By the verifier definition of NP, each positive solution to A has a witness that can be verified in polynomial time. Since P=L, the same solution can be verified in logarithmic space. Thus NP=NL.

You haven't shown that NP$\,=\,$NL. The only method you've derived to show that $x\in A$, is to nondeterministically "guess" a witness $y$ and use the deterministic logspace algorithm to verify it. However, $y$ itself may be polynomially long, whereas your NL machine can only guess logarithmically many bits: your NL machine doesn't have enough space to store the witness, so you don't have an NL algorithm.

Also, note that we already know that witnesses to NP-complete problems can be verified in a complexity class smaller than L. Fagin's theorem says that NP is exactly the set of problems that can be defined in the existential fragment of second-order logic. This is equivalent to saying that you can verify a polynomial-length witness using first-order logic. FO is strictly weaker than L, since first-order logic can't solve simple logspace problems like telling you if your witness string contains an even number of $1$s.


Solution to a Np-hard problem and its relevance to a dual LP

Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as complementary slackness are satisfied by any pair of optimal solutions.

In this case, however, we are already looking at the dual linear program; the constraints here correspond to subsets. In detail, the constraint $\sum_{i\colon e_i \in S_j} y_i \leq w_j$ corresponds to the subset $S_j$.

What is the relation to Set Cover? There is a natural linear program which is a relaxation of a natural integer programming formulation of Set Cover. If you compute its dual, you get the linear program that you quote. (If you're not sure which primal linear program was used to generate this dual linear program, you can always compute the dual of the dual linear program to get back the primal linear program.)


Comparison of running times: Determine largest n to run in given time

That's the answer then. "It's so huge, it can't be written down at all".

If an algorithm takes ln (n) microseconds, where n is the problem size, then there is no way to represent a problem that cannot be solved within a second.

Your equation is absolutely fine, and the solution would be for example $n = e^{1,000,000}$. It's just a very, very large number.

BTW. It's a very useful thing to look at. For example, if your computer can solve a problem of size n in an hour, you would want to know "what size of problem could I solve in an hour if I bought a computer that is twice as fast, or ten times faster".


Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?

It might be easier to consider the complement of your language:
$$
\overline{K} = \{ u \in \{0,1\}^* : \exists v \in \{0,1\}^{|u|} \text{ s.t. } u+v \in \overline{L} \}.
$$

You can now easily convert an NFA for $\overline{L}$ to one for $\overline{K}$ by replacing all edges labelled $1$ with edges labelled $0,1$ and all edges labelled $2$ with edges labelled $1$.

I'll let you figure out why this works.


Compute single-source shortest paths in O(n+m) time?

There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand.

The main idea is to transform the weighted graph into an unweighted one. If the number of nodes and edges of the transformed graph remains linear to $n$ and $m$, then we can run BFS to solve it in $O(n+m)$.

The transformation is as follows: for each edge $(u,v)$ of weight $w$, create $w-1$ nodes to connect $u,v$. For example an edge $(a,b)$ of length $3$, we create two dummy nodes and transform it into

$a-d_1-d_2-b$

It is easy to check that this transformation preserves the shortest path between any pairs of nodes. The number of nodes is now $O(n+cm)=O(n+m)$ and the number of edges is $O(m+cm)=O(m)$. Since BFS is linear to the number of nodes and edges, we have a runtime of $O(n+m+m)=O(n+m)$.


How do you correctly write this sentence as a CTL formula?

You can learn a lot about CTL at Wikipedia page.

The sentence you need to write, expressed more closely in the vocabulary of CTL operators, would be
Along all paths starting from current state, it always has to hold that there exists at least one path where $p$ eventually is true.

I think you can take it from there, but comment if you have troubles.

hint: The operators you will need to use are $F$, $A$, $E$ and $G$.


Recursion Davis' Staircase understanding

Your base case seems to be wrong.
Suppose we want to climb $n$ stairs, we want to compute $F(n)$. There are three possibilities which can be defined recursively:
1) First cover 1 stair, then there are $F(n-1)$ ways to continue.
2) First cover 2 stairs, then there are $F(n-2)$ ways to continue.
3) First cover 3 stairs, then there are $F(n-3)$ ways to continue.

So we need to add these three options
$$F(n) = F(n-1) + F(n-2) + F(n-3)$$
where base case is

$$F(1) = 1, F(2)=2, F(3) = 4$$

UPDATE (on Charles, and quicksort comments):

How to derive base cases

$F(1)$ means we have only one stair and thus there is only one way to climb it. So, $F(1)=1$.

For $F(2)$ we have two stairs and there are only two ways to climb it: First stair, and then the second, or directly jump on the second stair. So, $F(2) = 2$.

Similarly for $F(3)$. We may move to the first stair, then to the second, and then to the third one. We may also jump to the second and then to the third, or alternatively step on the first and then jump to the third. And finally we could directly jump to the third stair. In total, four possibilities, $F(3) = 4$.

The following is the pseudocode:

 Count(N)
   if N == 1 return 1
   if N == 2 return 2
   if N == 3 return 4
   return Count(N-1) + Count(N-2) + Count(N-3)
 end

As for the above tree, you don't need to "unravel" for the case $N=3$ since it is the base case which is handled in a single if-statement. However, for $N=5$ the recursion tree would look like as the following:

                      ( 5 )
                     /  |  \
                    /   |   \
                   /    |    \
                  /     |     \
                (4)    (3)    (2)
               / | \    |      |
              /  |  \   4      2
            (3) (2) (1)
             |   |   |
             4   2   1

Note that the above method of counting is the most terrible way since you always solve the same subproblems (overlapping subproblems) many times which leads to the exponential time. You could rewrite the algorithm which solves iteratively without using recursion as following

Count(n)
  if n == 1 return 1
  if n == 2 return 2
  if n == 3 return 4

  x1 = 1
  x2 = 2
  x3 = 4
  i = 4

  while i <= n
    sum = x1 + x2 + x3
    x1 = x2
    x2 = x3
    x3 = sum
    i+=1
  end

  return sum
end

Finally (as quicksort noted in his/her comment), you could solve the above recurrence relation and find the closed form formula which gives you $O(1)$ solution (without need to compute the entire sequence up to $N$).


what are the key advantages of pipelining

I Googled your question and found this (and this):

  Consider the modern way of making cars - on an assembly line. Here, there is an orderly flow of parts down a conveyor belt, and the parts are processed by different stations (also called segments of the assembly line). Each segment does one thing, over and over. The segments are coordinated to exploit the sequentiality inherent in the automobile assembly process. The work gets done more smoothly (because of the orderly flow of input parts and output results), more efficiently (because each assembler at each segment of the pipeline does his or her task at what one hopes is maximum efficiency), and more reliably because there is greater consistency in one task being done repetitively (provided the assembly line is designed correctly).

To put it in a simple way: Suppose you build a car in 10 steps $(s_1, s_2, \dots, s_{10})$. Suppose also that a single person can complete these 10 steps in 2 hours and a single step in 12 minutes. Let's also say that you have only 1 workplace for each step, so 2 people can't be working on the same step for 2 different cars. You'd have two ways to produce cars:

Put a single person that builds a car every 2 hours and uses all 10 workplaces.
Put a person per workplace (10 people in total) where each person completes a single step in 12 minutes and have a car every 12 minutes. The exception in this case is the first car which would take 2 hours to be completed, but from the second car and forward you'd have a car every 12 minutes.

The second way is the equivalent of pipelining.


Valgrind: what is the difference between a store and a modify?

This sounds like a question about the terminology that Valgrind happens to use, more so than a question about fundamental aspects of computer science.  I suggest you ask on a Valgrind support forum if you want an authoritative answer.

Based on your examples, it looks like the most likely answer is that the Valgrind folks are using the word "store" to mean "an operation that writes to memory, overwriting in a previous value with a new value that does not depend upon its previous value" while they mean "modify" to mean "an operation that writes to memory, updating its value to a new value that may depend upon the value previously stored in that location".  Only Valgrind folks can confirm authoritatively whether this is actually what they mean.


Why we can't create a binomial heap in max-heap format?

Why do you say that we cannot create a binomial max-heap?
Given any min-heap implementation you can always create its max version (and vice-versa).
An easy "black-box" way to see that this is true is considering what happens when all operations involving a key $k$ are actually performed on the key $-k$ instead.
That is, instead of inserting $k$ we insert $-k$; instead of deleting $k$ we delete $-k$; when we need to return the minimum key $k$, we return $-k$; etc...


Index matching algorithm without hash-based data structures?

If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $\Theta(n\log n)$ time in worst case for any algorithm.

This can be seen from the situation when array $a$ is sorted while array $b$ is arbitrary before we apply the algorithm. Knowing the index $I(k)$ of the element in $b$ which is the same as the $k$-th element of $a$ for all $k$, we can sort $b$ in $O(n)$ time by simply putting $b_{I(k)}$ in $k$-th position (using one temporary working space or a new result array of length $n$). However, it is well-known that it takes at least $\Theta(n\log n)$ time (comparisons) to sort $b$ in worst cases for any algorithm. So obtaining that knowledge, the index $I(k)$ for all $k$ must
take at least $$\Theta(n\log n)- O(n)=\Theta(n\log n)$$ time as well in worst cases.

The following is a formal formulation of the conclusion above in the comparison computation model.

Let $\mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,f\in E$, $\mathcal O$ outputs -1 if $e\prec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from $\{0, 1,\cdots, n-1\}$ to $E$. To output $I(0), I(1), \cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0\le k\le n-1$, it will take $\Theta(n\log n)$ queries against $\mathcal O$ in the worst case.

  whether there is a linear algorithm for this task that does not use any hashsets.

A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.


I will share below my attempt to prove that you can express every regular language as a regular expression using just the $+$ and $@$ operators. Unfortunately, my attempt at a proof has a gap.  Perhaps you can repair the gap.  My attempt based upon Brzozoswki's method for generating regular expressions, so I'll assume you are already familiar with how that works.

First, some definitions and other preliminaries.

Definition. Define $A^+$ to be the language of one or more words from $A$, i.e., $A^+ = \{a_1 a_2 \cdots a_k \mid k \ge 1, a_1,\dots,a_k \in A\}$.  In other words, $A^+ = A^* \setminus \{\epsilon\}$.

Definition. $\newcommand{\rp}{\backslash\backslash}$  For sets $A,B \subseteq \Sigma^*$, define $A\rp B$ by $A\rp B = (A^*\backslash B) - (A^+ \Sigma^*)$, where $A\backslash B$ is the left quotient, and $-$ represents the difference of two sets.  In other words, $A\rp B$ is the smallest set $C \subseteq \Sigma^*$ such that $A^* B = A^* C$ and such that no word in $A^+$ is a prefix of any word in $C$.

Example: $\{01\}\rp \{0101010,101\} = \{0,101\}$.

Note that if $A,B$ are regular languages, then $A\rp B$ is also a regular language and can be computed effectively from $A,B$.  (This follows from the standard closure properties of regular languages.)

Definition. The semantics of regular expressions using the $+$ and $@$ operators are defined inductively:

$L(w) = \{w\}$ if $w \in \Sigma^*$
$L(A_1+A_2+\dots+A_k) = L(A_1) \cup L(A_2) \cup \dots \cup L(A_k)$
$L(A^@ B) = \{ab : a \in L(A^*), b \in L(B), b \notin L(A^+ \Sigma^*)\}$
$L(w B) = \{wb : b \in L(B)\}$ if $w \in \Sigma^*$
$L(A^@) = L(A^*)$
$L((A_1+A_2)B) = L(A_1B + A_2 B)$, $L(A(B_1+B_2)) = L(AB_1 + AB_2)$
$L(A_1 A_2 \cdots A_k) = L(A_1 (A_2 \cdots A_k))$

(As a consequence, every regular expression using $+,@$ can be equivalently written as a sum of terms of the form $A_1 A_2 \cdots A_k$ where each $A_i$ is either of the form $w_i$ or $C_i^@$ for some $w_i \in \Sigma^*$ and some regular expression $C_i$ using $+,@$.  Once it is rewritten in that sum-of-products form, the semantics of the resulting expression is given by the definition above.)

For instance, we have the following property: if there is no word in $L(A^+)$ that is a prefix of any word in $L(B)$, then $L(A^@ B) = L(A^* B)$.

In what follows, I won't try to distinguish between a regular expression $E$ and its corresponding language $L(E)$.

Now we can prove a generalization of Arden's lemma.

Lemma 1.  Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$ and no word in $A^+$ is a prefix of any word in $B$.  Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$).  Then the least solution to this equation is $X=A^@ B$.

Proof.  Arden's lemma says the least solution is $X=A^* B$.  Now, since no word in $A^+$ is a prefix of any word in $B$, in fact $A^* B = A^@ B$, as there can be no ambiguity about how much the $*$ operator gobbles up.

Lemma 2. Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$.  Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$).  Then the least solution to this equation is $X=A^@ C$ where $C=(A\rp B)$.

Proof.  Arden's lemma says the least solution is $X=A^* B$.  As noted above, $A^* B = A^* C$.  Moreover, no word in $A^+$ is a prefix of any word in $C$, so $A^* C = A^@ C$.

Now given any regular language $L$, we can apply Brzozoswki's method to it, but using Lemma 2 above instead of Arden's lemma.  It's tempting to hope that the result will be a regular expression for $L$ that uses only the operators $+$ and $@$, but unfortunately there's a gap: I don't know whether one can prove that $A\rp B$ can be represented as a regular expression using only the $+$ and $@$ operators.  So, this proof method has a big gaping hole in it.

But perhaps someone will see a way to build on this and prove the desired result.


Is it decidable whether a given Turing machine moves its head more than 481 cells away from the left-end marker, on input ε?

A run of a TM is a sequence of configurations, where each configuration states the contents of the tape (from the left marker, up until the point where it is blank all the way to the right), the location of the head, and the state.

An important feature of (deterministic) TMs is that you can uniquely continue a run from a given configuration. That is, a configuration has all the information you need to proceed.

In particular, if a configuration $c$ yields a runs that gets back to $c$, at some point, then the run is stuck in a loop (note that this is not a necessary condition, a run might not halt while never repeating a configuration!).

Now, consider all the possible configurations that use up to 481 cells. There is a finite amount of those, namely $m^{481} \cdot 482 \cdot k$ (where $m$ is the size of the alphabet, and $k$ is the number of states).

Thus, if you simulate the run for that many steps, then either at some point the machine goes beyond 481 cells, in which case you accept, or it doesn't, in which case you know for sure that a configuration must repeat (by the pigeonhole principle), so you can reject.


The problem with your second approach (Case 2) is that the neural network might decide to output very large numbers for keypoints near or on the edge.  If it does, the loss function won't do anything to discourage it from doing that.

For instance, suppose the keypoint is at (30,94) for one instance in the training set.  Then outputting (30,1000) has the same penalty as (30,96).  So a network might just learn to output (30,96), and then start increasing the second coordinate (it learns (30,97), then (30,98), etc.) -- there's no penalty for that.

In particular, suppose that at some point the network is outputting (30,96) on that instance, and suppose the gradients encourage increasing the 96 a little bit.  Then in the next iterations the weights will be adjusted so it outputs (30,97).  Because the output is clamped before applying the loss function, (30,97) will receive the same penalty as (30,96).  Also it will have the same gradient.  Thus the learning process will continue adjusting the weights to cause the second coordinate to keep increasing forever.

This causes learning to fail to converge, or to converge very slowly.  And if learning fails to converge, it's plausible that overall rms error (including on other instances where this issue doesn't arise) might be very bad.


In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $u$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $u$ is indeed a valid vertex cover.


Inserting $n$ items to a heap takes $\Theta(n)$.

You probably mean that "building" a heap takes $\Theta(n)$.

  Each delete-min takes $\Theta(d \lg n/ \lg d)$, I was thinking the bound is $\Theta(n d \lg n / \lg d)$.

I agree with you.

  How do I prove that it is indeed a tight bound?

How tight do you want to prove it is? Do you want to show that the worst-case running time of $d$-ary heap-sort is $\Omega(n d \lg n / \lg d)$? If so, I tend to think it is indeed tight.

For a hint, this paper: The Analysis of Heapsort mentions that (in Abstract)

  The number of keys moved during $2$-ary heap-sort when sorting a random file of $n$ distinct elements is $n \lg n + O(n)$ in the worst case.

It even further proves that (Notice that it is for the best case)

  Theorem 1 (Page 7): Heap-sort ($2$-ary) requires at least $\frac{1}{2} n \lg n- O(n)$ data moves for any heap composed of distinct keys.

Maybe you can adapt it to $d$-ary heap-sort.


Distributed predicate computation on event stream

Impossibility result #1: dropped events
The problem cannot be solved in general; there is no way to guarantee that your requirements will be met if some events are dropped (i.e., not received).  Consider first this stream:
e1 = { name: Jhon, timestamp: 1 }
e2 = { name: Jhon, timestamp: 4 }

where the algorithm sees both events.  Next, consider this stream:
e1' = { name: Jhon, timestamp: 1 }
e2' = { name: Pete, timestamp: 2 }
e3' = { name: Jhon, timestamp: 3 }
e4' = { name: Jhon, timestamp: 4 }

where the algorithm sees only the events e1',e4' (the other events are lost and never received).  You might notice that what the algorithm sees in both cases is identical, so its outputs will be identical in both cases.  However, the correct answer differs in these two cases, so there is no hope for an algorithm that always produces a correct output.  (The correct response in the first case is to produce no notifications; the correct response in the second case is to produce two notifications, one to indicate that the predicate is false after receiving e2', and one to indicate that the predicate is true after receiving e3'.)
It is not clear how to adapt the requirements to deal with this situation.  The only plausible solution I can see is to say that the notifications that are produced should depend only on the received events, not on the events that are sent.  This is equivalent to specifying that events cannot be dropped.
Impossibility result #2: re-ordered events
You state that you must be able to handle re-ordered events, without storing all events in memory, and with arbitrary re-ordering. However, these requirements are incompatible: that is impossible to achieve.  Consider a long sequence of events with timestamps 2,4,6,8,10,12,...  At the end of the long sequence of events, if an event with an odd timestamp arrives, the only way to be sure you can handle it correctly is to store the entire history of past events (or past states of the object).
So, you're going to have to relax the requirement about re-ordering as well.  Perhaps you're willing to store all events in memory forevermore.  (If so, you have a solution.)  Perhaps you are willing to impose a bound on re-ordering, e.g., no event will be delayed by more than 10 minutes.  (If so, you only have to store history for the past 10 minutes, and everything older can be deleted.)  Perhaps something else makes more sense in your particular situation.
But the one thing that is not an option is to impose all of the strong requirements stated in your question, and require an algorithm that is always correct.

I'm not aware of any literature on this and I don't particularly see any reason to expect there to be any.  It's a very specific set of requirements, and it looks to me like the resulting task is either trivial or impossible to solve.  Those usually aren't the kind of problems that tend to be studied in the literature.  Perhaps you might be interested in persistent data structures, but that's just a fancy way of storing the entire history of events, which you said you want to do; and you don't need a fancy data structure to do that in your particular situation.


Cyclic deterministic finite automata, exponential advantage over DFA

Let $\Sigma$ be an alphabet of size $n$, and consider the language $L_n$ of all words over $\Sigma$ which contain all letters of the alphabet. It is well-known that the minimal DFA for $L_n$ contains $2^n$ states. On the other hand, $L_n$ is accepted by a CDFA with $n+1$ states.


When you speak about direct access in small amount of time that could also be logarithmic, you speak about secondary devices, so hard disks, floppys, USB flash drives, etc.

When you speak about random access you mean that access time to any part of memory is constant. This is very hard to achieve with secondary devices, but easier with primary ones.


Are there practical methods for solving ILP?

Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot.  Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can find an approximate solution as well (find the best solution they can within the time constraints).  There are no hard-and-fast rules.

Of course, ILP is NP-hard, so you should not expect any ILP solver to be able to efficiently solve all ILP instances.  Rather, what seems to happen in practice is that some instances can be solved in a reasonable amount of time, but others appear to be very hard.  However, ILP solvers incorporate many sophisticated techniques for speeding up the solver, and these are sometimes effective.  There's no good way to know for sure in advance whether your specific instance will be solvable efficiently or not, but to try it.

Why is it useful to reduce some other problem to ILP? That's not always useful or interesting... but in some cases it is.  For example, it lets you take advantage of the sophisticated methods already implemented in ILP solvers, without having to re-invent them in the context of your other problem.


Find all the paths from node A to node B

Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that
$$\begin{align}
P(i, 0) &= 1\\
P(0, j) &= 1\\
P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0
\end{align}$$
Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot of redundant calls. You could improve this by memoizing the intermediate values: at step $k$, compute and save the values $P(0, k), P(1, k), \dotsc P(k,k)$ and the values $P(k, 0), P(k, 1), \dotsc P(k,k)$. Note that this last series actually doesn't need to be saved at all, since $P(a,b)=P(b,a)$.

For another way (which turns out to be conceptually the same as Yuval's answer), you could observe that a path consists of a collection of steps:

An eastward move, $E$, from node $(i,j)$ to node $(i+1, j)$.
A southward move, $S$, from node $(i,j)$ to node $(i, j+1)$.
A diagonal move, $D$, from node $(i,j)$ to node $(i+1, j+1)$.

So to get from $(0,0)$ to $(i,j)$ we will need to make $i$ moves east and $j$ moves south. Note that each diagonal move will contribute 1 to the eastward moves and 1 to the southward moves. Thus, every path from the origin to node $(i,j)$ can be uniquely described as a sequence of $E, S, D$ where the number of $E$s plus the number of $D$s equals $i$ and  the number of $S$s plus the number of $D$s equals $j$. For example, $P(2,2)$ is the number of paths

Using no $D$s: $EESS, ESES, ESSE, SEES, SESE, SSEE$.
Using one $D$: $DES, DSE, EDS, SED, ESD, SED$.
Using two $D$s: $DD$

So we see that $P(2,2)=6+6+1=13$.

Now the number of sequences of three symbols $D,E,S$, in order, with $a$ of the $D$s, $b$ of the $E$s, $c$ of the $S$s,  is given by the multinomial coefficient
$$
\binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\;b!\;c!}
$$
and from this and the observations we just made, we'll have, for $i\le j$,
$$
P(i, j)=\sum_{k=0}^i\binom{i+j-k}{k,\ i-k,\ j-k}=\sum_{k=0}^i\frac{(i+j-k)!}{k!\;(i-k)!\;\ (j-k)!}
$$
where $k$ is the number of $D$ moves, $i$ is the number of $E$ moves and $j$ is the number of $S$ moves. This sum of factorials is also somewhat computationally expensive, but by recognizing that there are some relations among the terms, you can slightly simplify the number of multiplications and divisions involved. Unfortunately, there doesn't appear to be any nice closed form for this sum, unlike the situation where we don't allow diagonal moves, in which case $P(i,j)=\binom{i+j}{i}$.


Amortized time complexity for double stack emulated queue

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$.

You can formalize the above argument in various ways. As an example, if you perform $A$ insert operations and $B$ remove operations, then the argument above shows that you push at most $2A$ elements and pop at most $A+B$ elements. Hence the total running time is $O(A+B) = A \cdot O(1) + B \cdot O(1)$.


Will hardware/implementation affect the time/space complexity of algorithms?

Sure.  Certainly.  Here's how to reconcile your discomfort.

When we analyze the running time of algorithms, we do it with respect to a particular model of computation.  The model of computation specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?).  The running time of the algorithm might depend on the model of computation.

Once you've picked a model of computation, the analysis of the algorithm is a purely abstract, conceptual, mathematical exercise that no longer depends on hardware.

However, in practice we usually want to pick a model of computation that reflects the reality of our hardware -- at least to a reasonable degree.  So, if hardware changes, we might decide to analyze our algorithms under a different model of computation that is more appropriate to the new hardware.  That is how the hardware can affect the running time.

The reason this is non-obvious is because, in introductory classes, we often don't talk about the model of computation.  We just implicitly make some assumptions, without ever making them explicit.  That's reasonable, for pedagogical purposes, but it has a cost -- it hides away this aspect of the analysis.  Now you know.


Probability bounds on size of smaller partition in randomized quicksort

Suppose for simplicity that all elements are distinct, and that after sorting, these elements are $x_1,\ldots,x_n$. A random pivot has the same distribution as $x_i$ for $i$ chosen uniformly at random from $\{1,\ldots,n\}$. The size of the smaller partition is $\min(i-1,n-i)$. If $I$ is the set of indices $i$ such that $\min(i-1,n-i) \geq an$, then the probability you are looking for is $|I|/n$ (by the definition of uniform probability). I'll let you complete the calculation.


I suggest you start by reading about standard clustering algorithms and methods for clustering.  You could start with Wikipedia: cluster analysis and hierarchical clustering, then move on to textbooks or online resources.  Especially, check out hierarchical clustering to see if any of its methods might do what you want.

It sounds like you're not quite sure what you want.  So, if you learn more about standard clustering methods, you might be in a better position to formulate a narrower, more focused question -- or if you're lucky, maybe you'll find a solution you're happy with.


Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^2/\log^2 n)$ time, beating the best known algorithm for this problem, which takes $O(n^2 (\log \log n)^{O(1)}/\log^2 n)$ time.

In 3SUM, we are asked to find 3 distinct elements that sum to zero in a list of distinct integers $x_1, \dots, x_n$.  We can reduce this problem to your problem as follows:

For each $i$ from 1 to $n$:

Call $find(-x_i)$.  If this succeeds, with return value $(x_a, x_b)$, then $x_a, x_b, x_i$ are all distinct and sum to zero: return TRUE.
Call $insert(x_i)$.

Return FALSE.


Minimum bits needed when representing a value in a set

You can encode the set $X$ using only two bits: use $00$ to encode $1$, $01$ to encode $2$, and $10$ to encode $1e10$.

More generally, the exact identity of the elements of $X$ are not important. You can encode letters of the alphabet or even words, if you want.

You haven't defined what an encoding scheme is, so let me assume that it is a uniquely decodable code. Any uniquely decodable code for $X$ must contain a codeword whose length is at least $\log_2 |X|$ (and so at least $\lceil \log_2 |X| \rceil$). This follows from McMillan's inequality.


Uniform generation of random bipartite bi-regular graphs?

The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more difficult as $d$ grows as a function of $n$. To the best of my knowledge, the problem is still open for $d = \omega\left(\sqrt{n}\right)$.
However, if one assumes that $d$ is a constant, then there is a simple and efficient algorithm called the configuration model:
https://en.wikipedia.org/wiki/Configuration_model
It can be easily adapted to the case of biregular graphs with $M$ vertices of degree $k$ on the left side, and $N$ vertices of degree $d$ on the right side. Of course, for this to be possible at all we need $Mk=Nd$.
The algorithm is as follows:

Assign each vertex on the left side $k$ ``half-edges", and each vertex on the right $d$ half-edges.

Choose a uniformly random perfect matching of size $Mk$ matching all of the half-edges on the left side to the half-edges on the right side.

This tells you which vertices to connect to which, but there may be double edges. Repeat the above procedure until there are no double edges.

It is pretty easy to see that the resulting distribution is uniform by counting the number of perfect matching that can yield a given graph. It is harder to analyze the probability that there are no double edges, which is critical if we want to bound the expected runtime. However, it turns out that for constant $k$ and $d$, the probability that there are no double edges is a constant independent of $n$, and so we only need to repeat the algorithm $O(1)$ times.


It seems like this algorithm is keeping track of parent pointers. Each node N has three fields: N.left (left child), N.right (right child), and N.p (parent). The variable y is used to keep track of the most recent parent, so when we fall off the tree (i.e. when x == NULL) we can use y as the parent of the new node z.


Why does making a seemingly insignificant edit to an executable's machine code return errors?

When you open an executable in a text editor then the editor reads the contents in some lossy way - even if you haven't changed anything then the file would be different. Binary files contain non-printable characters (those with ASCII codes from 0 to 31), and these could be deleted by the text editor (other than CR/LF), especially the 0 character. Also, Windows text editors would convert CR (the UNIX new line convention; 0D) to CR/LF (the Windows convention; 0D 0A).

If you're curious what went wrong in your case, try to compare the files byte by byte and see where the differ. You could use a "hex editor", which is what you should have used to modify your file in the first place. These editors don't mishandle your files.


Is it decidable whether one language is polytime reducible to another?

I'm going to assume that your question is whether the language $$L = \{\langle M_1\rangle; \langle M_2\rangle\mid L(M_1)\leq_\mathrm{p} L(M_2)\}$$ is decidable, where $\langle M\rangle$ is the description of Turing machine $M$ and $\leq_\mathrm{p}$ denotes polynomial-time many-one reducibility.

This language is undecidable.

The only language that is many-one reducible to $\Sigma^*$ is $\Sigma^*$ itself.  This is because a many-one reduction from $X$ to $\Sigma^*$ must, by definition, map all "no" instances of $X$ to "no" instances of $\Sigma^*$. However, $\Sigma^*$  has no "no" instances, so the reduction can only exist if $X$ also has no "no" instances, i.e., if $X=\Sigma^*$.

So, now let $Y$ be any Turing machine that accepts every input.  The language $H=\{\langle M\rangle\mid \langle M\rangle;\langle Y\rangle\in L\}$ is clearly reducible to $L$. But $H$ is the language of Turing machines that accept every input, which is undecidable.


Find and sort 2d array elements like radar

For each of your points in the field, calculate the red angle:

Then sort all the (point, angle)-tuples by the angle.


With some algebra (and changing the constant in the $O(n)$), we can actually change the bases.

$$3^n = (2^{\log_2 3})^n = 2^{n\log_2 3}$$

Since $\log_2 3$ is a constant, $n\log_2 3 = O(n)$.  So $3^n = 2^{O(n)}$.

I'm not sure what you mean by "$3^n$ grows faster than any exponential function with a base of 2."   $2^n = o(3^n)$ of course but it seems you mean something more general.  My guess is that your statement applies to something like $O(3^n)$, where you multiply the base by a constant, as opposed to $2^{O(n)}$ where you multiply the number in the exponent by a constant.


Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

It is defined to be a probability.  A probability is by definition already normalized.  In particular, we are guaranteed that

$$\sum_{j=1}^N \gamma_j(1) = 1,$$

as there are only $N$ possibilities for the state that you're in at time $1$, and these $N$ cases have no overlap.


How to model a logical indicator when two inequalities hold in Integer Programming?

Your general approach is a good one.  Use Boolean variable that captures whether an inequality holds to define $\delta_{i,j}^1$ and $\delta_{i,j}^2$.  Then, use Express boolean logic operations in zero-one integer linear programming (ILP) to define $\delta_{i,j}$ in terms of $\delta_{i,j}^1$ and $\delta_{i,j}^2$ (via a logical-AND operation).


A good-enough version of good-enough? When should I stop iterating?

I did not check the code used in Abelson and Sussman's book or wiki.
My guess is that the recursive (or iterative) procedure will somehow
organize to compute improve(guess,x) only once. In a recursive
procedure, you just compare the formal parameter which is the previous
guess with the actual value (current guess) that you would pass for a
recursive call, in order to decide whether actually do the call rather
than return it. There may be a difference of one (wasted) iteration
depending on how you do the test.

Regarding the fact that you do the test on $x$ or on $\sqrt x$, or
rather $\mathtt{guess}^2$ or $\mathtt{guess}$, that does not give you the same
precison if you look for the same difference.

One way of explaining it is that $|\mathtt{guess}^2-x|=
|\mathtt{guess}^2-{\sqrt x}^2| = |\mathtt{guess}-\sqrt
x|(\mathtt{guess}+\sqrt x)$
since the second factor has to be positive (at least when relative
imprecision gets small).

Since $\mathtt{guess}$ is supposed to be very close to $\sqrt x$, we know that
$\mathtt{guess}+\sqrt x$ is very close to $2\sqrt x$ or
$2\;\mathtt{guess}$.

Hence $|\mathtt{guess}^2-x|$ is close to $2\sqrt
x\;(\mathtt{guess}-\sqrt x)$, so that the condition
$|\mathtt{guess}^2-x| < 0.001\;x$ can be replaced by
$2\sqrt x\;|\mathtt{guess}-\sqrt x| < 0.001\;x$, i.e.
$|\mathtt{guess}-\sqrt x| < 0.0005\sqrt x$
or, still using the same approximation:
$|\mathtt{guess}-\sqrt x| < 0.0005\;\mathtt{guess}$

This can be further formalized, but the above informal reasonning
gives you the idea.

However, I did not check how fast this conputation is converging, and
what is the difference between $|\mathtt{improve(guess,
x)-\mathtt{guess}}|\;$ and $|\mathtt{guess}-\sqrt x|$, i.e. how fast one
gets closer to the exact answer with each new iteration (assuming the
precision of the arithmetics is still good). Their ratio should also be accounted for. It depends on the formula used for computing the approximation, which I did not look at.


Computers don't learn - they compute.  They are given a set of instructions and generally follow those instructions to the letter, with the occasional blue screen of death.

The computer uses an algorithm that is developed to solve a particular problem.  The algorithm will iterate on a problem using the criteria and input data it is given.  As the algorithm progresses it's internal state is modified in some way, which you could say it is "learning", based on however it is processing of the data.

So in the case of learning how to do basic math - the network would have to be given the input of the numbers and operations, it would need to be "trained" on how to use them, and then given data to operate on.

The problem with that is... computers are really, really good at doing basic math - it's pretty much what they are designed for doing, but they are not good a "learning" things, because deep down they are just build to move the ones and zeros around really fast.

What could be more useful is to train the network to try and understand if a question is a math question or not, e.g "what is one plus one" vs "is that a banana over there", and/or do natural language processing on it to determine the logic of the problem, resolved as a trivial problem for a computer "1+1=?".

i.e. the actual math itself is the easy bit for the computer - processing understanding how you are phrasing a question is what the network would need to do.

And the answer of course is 42.


How to prove formally that grammar isn't LR(1)

$$S'\Rightarrow^*\underbrace{ab}_uA\underbrace{b}_w\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{b}_w$$

$$S'\Rightarrow^*\underbrace{abbbb}_zA\underbrace{b}_x\Rightarrow \underbrace{ab}_u\underbrace{b}_v\underbrace{bbbb}_y$$

$$FIRST(w)=FIRST(y)=b$$
But:
$$abAbbbb=uAy\neq zBx=abbbbAb$$


The answer to all of those questions is no, and not for some especially deep reason, as most of these can be ruled out by forcing the intersection to be simple enough.

Suppose $B$ contains all languages with only even length words, and $C$ contains all languages with odd length words. Clearly $B\cap C =\emptyset$, so $\mathsf{P^{B\cap C}=P}$, but $P^B, P^C$ both contain undecidable problems. This example rules out $1,2$.

To rule out $3$ you can set $\mathsf{B=EXP}$ and $C=\emptyset$. Choosing $B=\emptyset$ rules out $4$. Not allowing the empty set won't change much, as we can always do the same tricks with finite languages (or simple infinite langauges), so it is probably not possible to claim anything interesting in the general case.


For your first question, the vector $b$ is necessary to make sure $\text{Pr}_{A,b}[\vec{a_1} x^{T} + b_1 = y] = 1/2$, for $k = 1$.

Otherwise, it is easy to see that $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 0] = 3/4$ and $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 1] = 1/4$, for $n=1$. By conditional probability and the law of total probability, we can get $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 0] = 5/8$ and $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 1] = 3/8$, for $n=2$. This approach can be generalized to arbitrary $n$.


Define $\gamma = 1/\beta$, $P=\textrm{precision}$, and $R=\textrm{recall}$.

Then $$F_{\beta} = (1 + 1/\gamma^2)\cdot \frac{PR}{P/\gamma^2 + R} = (\gamma^2 + 1) \cdot \frac{PR}{\gamma^2R + P}$$, which is the $F_\gamma$ measure with the roles of $P$ and $R$ switched.

So the same reasoning that shows precision is preferred for $\beta < 1$ can be used to show that recall is preferred when $\gamma = 1/\beta < 1$, i.e. when $\beta > 1$.


Is Post's correspondence problem recognizable?

We can recognize acceptable inputs of PCP by exhaustively checking all valid possibilities (preferably by non-deterministic TM). That is it!. If the input is acceptable then the TM will stop, if it is not then the TM may not stop. Thus PCP is an RE language. Recognizability should not be confused with decidability.

We can do the same with deterministic TM by essentially simulating each thread of NDTM one step at a time.


Runtime-Analysis for single loop incremented by a factor of 3

That's right. This for loop stops when:
$$
3^i < n^3 \rightarrow i<3\log(n)
$$
Which implies the complexity of this for loop is $O(\log(n))$.


Move tokens from s to t as fast as possible

Menger's theorem states that the maximum number of $s$-$t$ (internally) vertex-disjoint paths is equal to the minimum size of an $s$-$t$ vertex cut. Let the common value be $m$.  Then it can be shown that the asymptotic number of rounds required is $n/m + O(1)$.

Using the vertex disjoint paths, we can route $n$ tokens in $n/m + O(1)$ rounds, where the constant depends on the graph $G$ (but not on $n$).  This gives an upper bound.

On the other hand, every token must pass through the vertex cut, and at most $m$ can do so at any given round, so routing $n$ tokens takes at least $n/m$ rounds.  (For each token, there must be a first time at which it reaches a vertex in the cut. Each such time can repeat at most $m$ times, since at most $m$ vertices of the cut can be occupied at any given time. So the number of rounds is at least $n/m$.)  This gives a matching lower bound.

From these two bounds, we deduce that the asymptotic number of rounds required is $n/m + O(1)$.


How do multiple branches from one node occur with the Monte Carlo Tree Search?

It sounds like you're reading a summary/overview.  You might be reading too much into one sentence there.  The sentence says "MCTS will add one child node per iteration".  That doesn't mean each node will have only one child after the process finishes.  You might have one iteration that adds one child of X, and a later iteration that adds another child of X, and an even later iteration that adds yet another child of X, and so on.

Similarly, nothing says that MCTS is limited to adding only two or three children per node.


how to interpret the coefficients of binary logistic regression?

I don't have the rep to comment, but the answer to your question is "sort of." It would take me too long to answer this question completely and with the proper care, so i will point you to a good resource
http://www.appstate.edu/~whiteheadjc/service/logit/intro.htm

There is a section midway through on interpreting your regression coefficients. In your specific case (as I imagine all of your independent variables only take on positive values), your interpretation is fine. If $b_1$ is the slope coefficient of an indicator variable for some word, then a 1 unit change in $b_1$ (i.e. if the word corresponding to $b_1$ is seen) corresponds to an $\exp{(b_{1})}$ change in the log odds of your model (e.g. the probability of the person being a boy is $\exp{(b_{1})}$  more likely). Hope this helps


Is the language of Roman numerals ambiguous?

A grammar (not a language!) is ambiguous if there is a word with two "essentially different" parses. Roman numerals are unambiguous - given a roman numeral, it has an unambiguous numerical value. The fact that this correspondence is not one-to-one is beside the point.


Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata?

Let us check the definition.

For two sets of strings $S_1$ and $S_2$, the concatenation $S_1\cdot S_2$ consists of all strings of the form $vw$ where $v$ is a string from $S_1$ and $w$ is a string from $S_2$, or formally $S_1\cdot S_2 = \{ vw : v \in S_1, w \in S_2 \}$.

What about $\emptyset\cdot R$?

 Since there is no string in the empty set, we cannot find any string of that form $vw$ where $v$ is a string from the empty set. For example, you cannot form a mixed double in tennis if there is no male players. So $\emptyset\cdot R=\emptyset$.


What is the purpose of the SKI combinator calculus(or even lambda calculus)? What are some real life examples of its use?

The obvious application of the lambda calculus is any functional programming language (e.g., Lisp, ML, Haskell), and any language that supports anonymous functions.

As for combinator calculus, does there have to be a "real-world application"?  Turing machines, for example, are hardly ever used "in the real world" but they form the basis of the theory of computation.  One useful feature of combinator calculi is that they're simpler systems than, e.g., Turing machines. If you want to prove that some other system is Turing-complete, it might be easier to show how it can simulate combinators than to show it can simulate a Turing machine.


I don't know how to prove a simple theorem used with fixpoint in Coq

You are making your life difficult by defining things in convoluted ways. Here's how a better definition of the same thing makes the proof easy.

Fixpoint f_better n0 len : Prop :=
  match len with
  | 0 => True
  | S k => x n0 /\ f_better (S n0) k
end.

Theorem t1_better: forall n0 len,
    x n0 /\ f_better (S n0) len <-> f_better n0 (S len).
Proof.
  easy.
Qed.

If you really insist on using your version, we can prove that as well, but it'll be painful.


Which of these properties hold for all FO theories? (but not regarding fragments thereof)

Your answers to (a) and (c) are correct. To tell whether (b) is correct we need a precise notion of expressiveness.
The issue is that propositional logic and first-order logic have totally different semantics: their notions of "model" are valuation and structure respectively. When two logics use the same notion of "model" we can straightforwardly compare their expressive powers by looking at what sets of models their sentences can pin down respectively. For example, SOL is strictly more expressive than FOL since there is an SOL-sentence whose class of models is not the class of models of any FOL-sentence (e.g. take an SOL-sentence whose models are exactly the finite structures, and observe via compactness that no FOL-sentence can do this). But this direct comparison idea doesn't even make sense for FOL vs. propositional logic.
Now for the specific question you ask, due to the fact that you look at all FOL theories this is arguably a moot point since there is a particular FOL-theory which is extremely simple, namely it only has two formulas up to semantic equivalence and it is linear-time decidable:

 Take the theory in the empty language of a one-element pure set.

(Of course if you allow inconsistent theories this is even easier, but that seems silly. Incidentally note that $(i)$ the example above really does have to be that "small" per here and here, and $(ii)$ this also addresses (c).)
Since propositional logic isn't that simple, it's pretty clear that this is an FOL-theory which is not as expressive as propositional logic in any meaningful sense. But I think it's still worth highlighting this ambiguity, since there will be less trivial situations where we want to compare very different logics and there we will absolutely need a precise definition to say anything.


How to construct a random error-correcting code (its generator matrix) according to the code parameters?

Look at Reed–Solomon codes. They are MDS codes, and AFAIK, MDS codes are most efficient codes that operates on independent blocks of bits.

If you need to support only erasures, there is simple to describe algorithm - consider input words as values of some polynomial at points 0..n-1, and compute (using a Galois Field) values of the same polynomial at points n..n+m-1 - it will be possible to restore polynomial coefficients from any n survived values.

If you can read Russian, I wrote more about erasure-only codes at ReedSolomonFFT-ru.md.


How does $\mathsf{NP} \subset \mathsf{P}/\mathsf{poly}$ imply these two inclusions?

If $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$, then $\mathsf{SAT} \in \mathsf{SIZE}[O(n^k)]$ for some fixed constant $k$. The claimed results should follow by using this circuit to replace the $\mathsf{NP}$ oracle(s) involved in the relevant classes. For example, (2) follows by noting that $\mathsf{ZPP}^{\mathsf{NP}} = \mathsf{ZPP}^{\mathsf{SAT}}$ and then replacing every call to the $\mathsf{SAT}$ oracle with the assumed small circuit for $\mathsf{SAT}$.


Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$

This question has been answered before, but let me summarize the answer:
$$
a^*b^*c^* \setminus \{ a^n b^n c^n \} = \\
\{ a^{n+1+m} b^n c^p \} \cup \{ a^n b^{n+1+m} c^p \} \cup \\
\{ a^{n+1+m} b^p c^n \} \cup \{ a^n b^p c^{n+1+m} \} \cup \\
\{ a^p b^{n+1+m} c^n \} \cup \{ a^p b^n c^{n+1+m} \}.
$$
All parameters $n,m,p$ are assumed to be non-negative.


Can we represent all computer programs as graphs?

I don't know if it's a particularly well known equivalence, but it's fairly simple when you think about it.

Turing Machines are known to be equivalent to the (untyped) Lambda Calculus. The Church-Turing thesis proposes that this is they are the most powerful form of computation.

The Lambda Calculus is a syntactically defined term re-writing system. Essentially, it's a very simple programming language. So, it can be parsed into an abstract syntax tree (graph).

So, we have:

Every computer program is representable in the untyped lambda calculus.
Every lambda calculus program can be parsed into an abstract syntax tree

This means that every computer program can be represented as a Lambda Calculus abstract syntax tree.

These trees might not have much in the way of interesting properties. For example, they're definitely not unique i.e. two different trees can perform identical computations.


Take your example
$$ A = [1,4,2,6,3,7,5,8]. $$
An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together:
$$
1,4,2,6,3,7,5,8 \\
1,2,3,4,5,6,7,8
$$
You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.


What is the computational class of a pushdown automaton with real values?

Since none of your instructions can influence the behavior of the pushdown automaton (they can only influence the value of $x$), this does not change which languages the pushdown automaton can accept.


If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$)

If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct).

If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order to obtain $N$ as a sum of $k$ powers of two (you cannot be stuck with only terms of the form $2^0$ -which cannot be split- before reaching $k$ terms as $k\leq N$ by assumption).
If $n>k$, then it cannot be done. Indeed, assume it could be done, and consider the decomposition into $k$ powers of two. (Iteratively) merge these powers of two until you reach a binary decomposition of $N$. This decomposition has at most $k$ $1$s, which is absurd by uniqueness of the binary decomposition.


XOR of three integers where each pair's XOR is the other integer

There are infinitely many solutions: choose $a=b\in\mathbb N, c=0$ and then $a\oplus b\oplus c=0$.

To find all solutions, choose an arbitrary $c\in\mathbb N$. We want to find all $a,b$ with $a\oplus b=c$. Its equivalent to $a=b\oplus c$, so for every $b\in\mathbb N$ we would choose $a=b\oplus c$ and $a,b,c$ would be a valid solution.

All of the solutions are of this form - and therefore thats how you can iterate through every possible solution to the question


Optimal encoding scheme for semi-rewritable memory?

The lifetime capacity can be arbitrarily large.
One may change the weight of the ternary symbols from 1/3, 1/3, 1/3 to 1/2, 1/4, 1/4 (favouring the symbol with blank bits). This reduces the entropy of the ternary symbol from $log_2(3)$ to $\frac{3}{2}$.
What it also does is reducing the capacity loss between generations, to a factor of $\frac{5}{3}$
Thus, instead of a lifetime capacity of:
$$\frac{log_2(3)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2}\right)^i = log_2(3) \approx 1.58$$
The lifetime capacity is instead:
$$\frac{3}{4} \cdot \sum_{i=0}^{\infty}\left(\frac{3}{5}\right)^i = \frac{15}{8}\approx 1.88$$
This can be generalised.
By weighted as $x$, $\frac{1-x}{2}$, $\frac{1-x}{2}$, the loss of capacity for each generation is a factor that can be written as:
$$generation\ loss =\frac{1}{2} - \frac{1}{x - 1}$$
And the entropy of the symbol is:
$$S = - \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)$$
For a lifetime capacity of:
$$\frac{- \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)}{2} \cdot \sum_{i=0}^{\infty}\left(\frac{1}{2} - \frac{1}{x - 1}\right)^i$$
Which grows unbounded when $x$ approaches 1, however quite slowly (logarithmic). This makes the capacity per generation very low, but the sparseness of the set bits allows the memory to be reused many many times.


It is solvable in polynomial time.

Convert an instance of Bounded Occurrence 3DM to a cubic graph.

For each triple, create a vertex

For each element, there are exactly two triple containing it. So, there are exactly two vertices corresponding to these two triples. Connect these two vertices by an edge.

Now, a solution to your problem is an independent vertex cover.

A graph has an independent vertex cover iff. it is bipartite. Checking for bipartiteness can be done in polynomial time.


How can union-find algorithm be used with "real" data

Short answer: indirection.

For instance, each object could have a field that contains an index into the id array.

Or, you could use pointers.  Standard union-find data structures often use pointers instead of integers/indices/arrays.  Thus, each object has a pointer to another object in the same equivalence class.  See, e.g., https://en.wikipedia.org/wiki/Disjoint-set_data_structure or other standard presentations of union-find data structures.


Maximum connected cell length containing two different numbers

First you can transform the matrix to a graph, where every maximal area containing the same integer is transformed to a vertex with a weight that is the number of cells in the area, and there is an edge between two vertices iff the two corresponding areas are adjacent, that is, there is a cell in one area that is adjacent to at least one cell in the other area. Therefore, the matrix in your example is transformed to

5 - 3 - 2 - 5
|   | / |   | \
2 - 1   |   |   3
| / | \ |   |   |
6   |   5 - 2 - 5
|   | / | \ | / |
5 - 2   |   3   |
|   |   |   |   |
4 - 6 - 8 - 9 - 6

Now the problem turns out to be finding the connected subgraph with maximum sum of weights such that it contains exactly two integers. This transformation can be done in $O(mn)$ time.

Next, run the following algorithm:

maxS := empty set
While True:
    Search the next edge (u,v) that is not used
    If not found:
        return maxS
    Let x,y be the integers contained in u,v respectively
    (#) Do BFS from u where only edges between vertices containing x,y respectively are considered
    Mark all edges found during the BFS as used
    S := the set of vertices found during the BFS
    If the sum of weights in S > the sum of weights in maxS
        maxS := S

Note the (#) line, this algorithm requires us to, given a vertex containing integer x, efficiently find all its neighbors (as well as edges) containing y. You can sort all the neighbors for all vertices in advance, which takes $O(\sum_v n_v\log n_v)=O(mn\log(mn))$ time ($n_v$ is the number of neighbors of vertex $v$). Now compared to normal BFS, it takes extra $O(\log n_v)$ time for each vertex $v$.

Basically, each BFS induces a maximal connected subgraph containing exactly two integers. This algorithm checks all such subgraphs and choose the optimal one. Note each edge belongs to only one such subgraph and each vertex $v$ belongs to $t_v$ such subgraphs ($t_v$ is the number of distinct integers among all neighbors of $v$), the time complexity of this algorithm is

$$O\left(mn+\sum_vt_v\log n_v\right)=O\left(mn\log(mn)\right).$$


Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set

Let's name the vertices $v \in V \setminus U$ and $u \in U$ the vertices that are allowed to have out-neighbors anywhere.

Suppose that we know the vertex $u$ and delete all its out-edges.

Now we are looking for a vertex $v$ that "separates" the graph in two components, $V \ni v$ and $U \ni u$.

We can find $u$ in $O(n)$ time by trying all possibilities.  We can also find the strongly connected components in $O(n + m)$ time.  In this graph, we must find $v$ with the above property.  That can be done in linear time $O(n + m)$.  Hence it all runs in $O(n(n+m))$ time, which is at most $O(n^3)$.


Yes, they mean the same thing.  A n-gram is a sequence of n consecutive things (words, letters, whatever).  A k-mer is a sequence of k consecutive things (DNA basepairs).  The phrase k-mer is more common in computational genomics.

See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.


Which languages are recognized by one-counter machines?

A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.

For example a 1-counter automata can recognize the language $\{a^nb^n\}$ which is not regular, but cannot recognize the language $\{a^nb^ma^mb^n\}$ which is context free and can be recognized by a 2-counter automata, too.

If k-DCA is a deterministic k-counter automata, and k-NCA is a nondeterministic k-counter automata, then we have the following proper inclusions:

DFA (regular languages) $\subset$ 1-DCA  $\subset$  2-DCA

1-DCA $\subset$ 1-NCA

If we don't allow $\epsilon$ transitions (switch to real time) then k-DCA $\subset$ k'-DCA for k < k'.

Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\{ww^R\}$), and languages recognized by counter automatas that are not context free (for example $\{a^nb^nc^n\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).


Flow value over edges in Max flow/Min Cut Ford Fulkerson

Yes. More precisely, for every min cut $(W,\bar{W})$, there is some max flow $f$ such that $f(x,y)=0$ if edge $(x,y)$ goes from $\bar{W}$ to $W$, and $f(x,y)$ equals the capacity of $(x,y)$ if edge $(x,y)$ goes from $W$ to $\bar{W}$. This is usually proven using the linear programming formulations of min cut and max flow, and follows by the complementary slackness property.


Are there algorithms or circuits that can implement addition without the need for carry flags

For non-redundant representations like $(x_n, x_{n-1}, ..., {x_1})$ the recursion is fundamental (although the operator is associative so you can apply the prefix sum optimization to parallelize the operation down to $O(\lg n)$ steps.)

But there are redundant representations where addition can be performed more efficiently, in some cases.  The carry-save adder is used in most hardware multiplier implementations, where you need to sum together a large list of numbers.

The redundant representation is just to represent every number by two subsums:

c3 c2 c1
x3 x2 x1 x0

so, for example, the number "5" can be stored either as:

 0  0  0
 0  1  0  1

or

 0  0  1
 0  0  1  1

The "addition" operation adds three subsums and produces two subsums:

 0  0  1
+0  0  1  1
+0  0  0  1
-----------
 0  1  1  0
 0  0  0  0

So, not very useful if you are just adding two numbers, but when you need to sum a whole list of numbers, each individual addition is fast, and then only at the end do you have to convert back to a non-redundant representation.

There are other redundant representations used in hardware multiplication algorithms, like Booth encoding where the digits can be positive, zero or negative.