NOT satisfiable 3SAT instance certificate

A CNF which is not satisfiable is usually called unsatisfiable. A CNF which is unsatisfiable but becomes satisfiable if we drop any clause is minimally unsatisfiable.
Papadimitrious and Wolfe constructed, in their paper The complexity of facets resolved (Lemma 1), a polynomial time reduction $f$ from CNFs to CNFs such that:

If $\varphi$ is satisfiable then $f(\varphi)$ is satisfiable.
If $\varphi$ is unsatisfiable then $f(\varphi)$ is minimally unsatisfiable.

It is likely that this can be extended to a reduction from 3CNFs to 3CNFs.
This reduction shows that the minimally unsatisfiable case is the "hardest". In particular, if there is an efficient way to check that a minimally unsatisfiable CNF is unsatisfiable, then P=NP.


Proving Little-Oh notation by definition

Either you do what David suggested, or you do something like this:

Let $c > 0$. Then

\begin{align}
5n^2 +3n &\le c(n^3-4n) &\iff \\
5n+3 &\le cn^2-4c &\iff \\
0 &\le cn^2-5n-(3+4c)
\end{align}

Now solve for $n$ and let $n_0$ be the bigger root of that term.


An algorithm to detect if the conversion rate growth acceleration rate is still rising or stopped

You are seeking to predict future values of the time series based on past values.  There's lots in the area of time series analysis and prediction; I suggest reading about those topics.  The right approach will depend on domain knowledge and how currency rates tend to change and what statistical model is appropriate in your setting.


Simplifying $b(abb + abbbb + aba^*bbb)^*$

Note that $abbbb+aba^*bbb = aba^*bbb$. Also, note that you can "factorize" common expressions in the parentheses.
Your regular expression is equivalent to $b(a(\varepsilon + ba^*b)bb)^*$ (I don't know if it can be simplified again).


Mapping several memories to one address space

Each RAM chip (e.g., DIMM module) has its own range of physical addresses.  The memory controller connects the CPU to the RAM chips via a memory bus.

In its simplest form, each read or write operation sent on the memory bus contains some bits that select which RAM chip it applies to, and some bits that indicate the address to be selected within that RAM chip.  So, physical memory is partitioned among the RAM chips.  The memory controller is responsible for managing this partition and determining, based on the physical address, which RAM chip to select (what to write on the chip select bits of the memory bus).  The specific architectural details have evolved over time and may differ from platform to platform.

Physical addresses are normally not visible to user-level applications.  Instead, a virtual memory subsystem (page tables) are used to translate from virtual addresses to physical addresses.  The user-level application seems virtual addresses.  There need not be any simple way that ranges of virtual memory addresses correspond to RAM chips.


Algorithm for difference of two semi-decidable languages

You are confusing languages with algorithms.

An algorithms is not "computable" or "non-computable". It can halt or not halt, but the latter doesn't mean that the language it defines is non-computable.

In this case, if conditions 1 and 2 are fully-computable (assuming by that you mean decidable, or recursive), then you can write algorithm 3 as follows:

Given x, check both condition 1 and condition 2. Print the input iff condition 1 holds and 2 doesn't.

The fact that algorithms 1 and 2 are "silly" in that they get stuck for no "good reason" doesn't affect the decidability of their languages.


On $NP=\Sigma_2^P$ from non-deterministic time?

Here is a simpler "proof" using the same ideas. I will show that NP=coNP. Indeed, suppose that $L \in \mathsf{coNP}$, and consider the machine which on input $x$, invokes the NP-oracle $\overline{L}$, and outputs the opposite value.

What goes wrong in this argument? Let us use the "witness" definition of NP: a language $L$ is in NP if there exist a polynomial $p$ and a polytime predicate $P$ such that $$ x \in L \Longleftrightarrow \exists |y| \leq p(|x|) \, P(x,y). $$
Now suppose that $L$ is in coNP, that is,
$$ x \in L \Longleftrightarrow \forall |y| \leq p(|x|) \, \lnot P(x,y). $$
(We get this by applying the previous definition to $\overline{L}$.)

Our machine deciding $L$ nondeterministically accepts as input $x,y$ and outputs $\lnot P(x,y)$. However, this accepts a different language $L'$ given by
$$ x \in L' \Longleftrightarrow \exists |y| \leq p(|x|) \, \lnot P(x,y). $$
The difference is the quantification — existential instead of universal.

Informally, this shows that nondeterministic machines cannot simulate nondeterministic oracles. However, they can simulate deterministic oracles: $\mathsf{NP}^L = \mathsf{NP}$ for all polytime $L$. This is because an NP-machine can simulate the computation of $L$ on any given input directly. The same cannot be said about nondeterministic oracles.


proving $E_{TM}$ is undecidable using the halting language

Suppose that there is a Turing machine $T$ that decides $E_{TM}$.

Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^*$ that decides whether $(M,w) \in H_{halt}$. $M^*$ operates as follows:

It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is complete, accepts.
It simulates $T$ with input $M'$ to decide whether $M' \in E_{TM}$.
If $M' \in E_{TM}$ then $M'$ does not accept any input, which implies that $M$ cannot halt on input $w$. In this case $M^*$ rejects.
If $M' \in E_{TM}$ then $M'$ accepts at least one input (and hence all inputs), meaning that $M$ must halt on input $w$. In this case $M^*$ accepts.


Curry–Howard correspondence and functional programming "reliability"

The dependent types allow you to specify what properties your function should have, not just what its domain and codomain are. This way it becomes impossible to accidentally use the wrong function.
For example, suppose we want a function that sorts lists (of integers). In ordinary programming we would ask for a value of type List → List, and then we would write documentation in English that says "and it is supposed to sort lists".
With dependent types, we would write down a fancier type:
Σ (f : List → List) Π (lst : List) isSorted(f lst) × isPermutation(lst, f lst)

(See below how one defines isSorted and isPermutation.)
An element of this type is a pair (f, p) such that f :  List → List and p is a function which takes as input any list lst and outputs a pair (q, r), such that: q is the proof that isSorted f lst and r is the proof that lst is a permutation of f lst. In other words, p proves that the output of f lst is precisely the sorted list lst.
If you think about it, it is impossible to accidentally use a non-sorting function. If you do, then you will not be able to also write down the proof that it really sorts lists.
In ordinary programming we are used to write down data and functions into the source code, but keep their properties in our heads. In dependent programming the properties are part of the source code, and so are the proof that those properties are satisfied.
P.S. We define isSorted : List → Type as
isSorted nil = True
isSorted (x :: lst) = (Π (y : int) . elementOf y lst → x ≤ y) × isSorted lst

It is a bit more annoying to define isPermutation, so I will not do it here.


Algorithm to calculate numbers of 10^x smaller than given one

$Num \geq 10^{x} $

$\implies x \leq log_{10}(Num)$

Then $x = \lfloor log_{10}(Num) \rfloor $.

$10^{x}$ would be your number.


Functions with small support have small circuits

Consider the AND function:
$$
x_1 \land \cdots \land x_n.
$$
Its support size is $1$, and its circuit complexity is $O(n)$. By negating inputs, you can get a circuit for any function whose support size is $1$. By ORing together $k$ such functions, you can get a circuit of size $O(kn)$ for any function whose support size is $k$.


Number of permutation cycles in matrix transposition

Let's take a simple example:
$$ \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}' = \begin{pmatrix} a & d & g \\ b & e & h \\ c & f & i \end{pmatrix}.$$
So we need to exchange $(b,d),(f,h),(c,g)$, i.e. the answer is 3. Now try to generalize this to $A \times B$ matrices. Obtain a formula, substitute $A = 2^a$ and $B = 2^b$, and find a way to efficiently compute the result modulo a small prime $p$.

When $A = 2^a$ and $B = 2^b$, things look nicer. The permutation taking a position in the original matrix to the corresponding position in the transposed matrix corresponds to left shift by an amount $a$. Suppose $g = \mathrm{gcd}(a,b)$ and $a' = a/g,b' = b/g$. We can now think of the operation as a left shift by the amount $a'$ of a string of length $a'+b'$ over an alphabet of size $G = 2^g$. The number of orbits is then the number of necklaces of length $a'+b'$, which has an explicit formula. (The shift amount doesn't matter since $a'$ is invertible modulo $a' + b'$ due to $(a',b')=1$.)


Computing the rank of a multiset after inserting another element

I'll consider the easy $|S|=2$ case. There are $n+1$ multisets of size $n$, and so the rank of the multiset $0^{n-k} 1^k$ is
$$ r(n,k) = \sum_{m=0}^{n-1} (m+1) + k = \frac{n(n+1)}{2} + k. $$
What happens when adding an element? Adding $0$ and $1$, respectively, correspond to $r(n+1,k)$ and $r(n+1,k+1)$. We have
$$
\begin{align*}
r(n+1,k) &= \frac{(n+1)(n+2)}{2} + k = n + 1 + \frac{n(n+1)}{2} + k = n+1 + r(n,k), \\
r(n+1,k+1) &= r(n+1,k)+1 = n+1 + r(n,k) + 1.
\end{align*}
$$
Therefore the function you want is
$$ f(r,x,n) = r + n+1 + x. $$
Here $n$ is the size of the old multiset, rather than the number of elements. For example, the rank of $(1,1)$ is $5$, and $f(5,0,2) = 5 + 3 + 0 = 8$, $f(5,1,2) = 5 + 3 + 1 = 9$.


Relating memory complexity and decidablity

Any language accepted by a non-deterministic Turing machine is decidable, since non-deterministic Turing machines can be simulated by deterministic Turing machines. See for example the Wikipedia article.

There is some subtlety you might be worried about: the non-deterministic Turing machine might always halt (on a given input), but its running time could be unbounded, and then the trivial simulation which just tries all possible guesses wouldn't halt. Fortunately, König's infinity lemma shows that if the running time is unbounded, then there is some infinite computation, so the running time must be bounded.


Is (a+b)* and (ab)* same in finite automata?

The regular expressions $(a+b)^*$ and $(ab)^*$ represent languages according to the semantics of regular expressions. Formally, the language $L[r]$ corresponding to a regular expression $r$ is defined as follows:

$L[\emptyset] = \emptyset$.
$L[\epsilon] = \epsilon$.
$L[\sigma] = \sigma$ for $\sigma \in \Sigma$.
$L[r_1+r_2] = L[r_1] \cup L[r_2]$.
$L[r_1r_2] = L[r_1] L[r_2]$, where $L_1 L_2 = \{ w_1w_2 : w_1 \in L_1, w_2 \in L_2 \}$.
$L[r^*] = L[r]^*$, where $L^* = \bigcup_{n \geq 0} L^n$, and $L^n$ is defined recursively by $L^0 = \{\epsilon\}$ and $L^{n+1} = L^n L$.

Two languages over the same alphabet are equal if they are equal as sets, that is, if they contain the same words. In your case, you haven't specified the underlying alphabet $\Sigma$, so I'm assuming that $\Sigma = \{a,b\}$.
Now that you have all the definitions, you can check for yourself whether $L[(a+b)^*]$ equals $L[(ab)^*]$.


How can I show that the Cook-Levin theorem does not relativize?

Please refer Does Cook Levin Theorem relativize?.

Also refer to Arora, Implagiazo and Vazirani's paper: Relativizing versus Nonrelativizing Techniques: The Role of local checkability.

In the paper by Baker, Gill and Solovay (BGS) on Relativizations of the P =? N P
question (SIAM Journal on Computing, 4(4):431–442, December 1975) they give a language $B$ and $U_B$ such that $U_B \in NP^B$ and $U_B \not\in P^B$, thus proving that there are oracles $B$ for which $P^B \neq NP^B$.

We shall modify the $U_B$ and $B$ to $U_{B'}$ and $B'$ such that we get a new language that cannot be reduced to 3SAT even if there is availability of $B'$ as an oracle.

First assume that we can pad every $3SAT$ boolean instance $\phi$ to $\phi'$ with some additional dummy 3CNF expressions such that $|\phi'|$ is odd and they are equivalent, i.e., $\phi$ is satisfiable iff $\phi'$ is satisfiable. We can do it in $n+O(1)$ time and with $O(1)$ padding, but even if it takes polynomial time and extra polynomial padding it does not matter.

Now we need to combine the $B$ and $3SAT$ to $B'$ somehow so that BGS theorem still holds but additionally $3SAT \in P^{B'}$. So we do something like the following.

$U_{B'} = \{1^n \ \ |\ \ \exists x \in B, $ such that $|x| = 1^{2n}\}$ and

$B' = B'_{constructed} \ \cup \{\phi \ \ |\ \ \phi \in 3SAT $ and $ |\phi| $ is odd $\}$.

Now we shall construct $B'_{constructed}$ according to the theorem such that if the deterministic machine $M_i^{B'}$ for input $1^n$ ($n$ is determined as in theorem) asks the oracle $B'$ a query of odd length we check if it is in $3SAT$ and answer correctly but if it asks a query of even length we proceed according to the construction, that is, answering correctly if it is already in the table, otherwise answer no every time. Then since we are running for $1^n$ we flip the answers at $2n$ length so that $M_i^{B'}$ does not decide $U_{B'}$.

We can prove similarly as in the BGS theorem that for this $B'$ and $U_{B'}$ too, we have $U_{B'} \in NP^{B'}$ and $U_{B'} \not\in P^{B'}$.

$U_{B'} \in NP^{B'}$ is easy to prove. We construct a non-deterministic Turing Machine which for input $1^n$ creates non-deterministic branches that runs for $2n$ steps to generate a different $2n$-length string and then asks oracle $B'$ if the $2n$-length string is in $B'$, and if the answer is yes it accepts $1^n$ else it  rejects $1^n$. This construction shows that $U_{B'} \in NP^{B'}$.

$U_{B'} \not\in P^{B'}$ can be proved with the help of diagonalization argument. Basically it is different from every $L(M_i^{B'})$ for every oracle Turing Machine that have $B'$ as an oracle. This is because of how we construct $B'_{constructed}$.

Now we shall prove by contradiction that there does not exist a reduction from $U_{B'}$ to $3SAT$ even with the availability of oracle $B'$.

Assume there is a reduction using oracle $B'$, i.e., $U_{B'} \leq^{B'}_P 3SAT$.

That means we can reduce a string of the form $1^n$ to a 3SAT instance $\phi$ using a polynomial-time deterministic machine which uses $B'$ as oracle.

We can now describe a deterministic TM $M^{B'}$ which will decide strings $U_{B'}$ in polynomial time using $B'$ as an oracle. First this machine reduces the input $1^n$ to a 3SAT-instance $\phi$ using $B'$ as an oracle. This can be done because we have the reduction above. Then if $\phi$ is not odd length $M^{B'}$ will pad it to make $\phi'$ which is odd length. Next, it will give this $\phi'$ to oracle $B'$ and get the answer yes/no. It will accept if the answer is yes and reject if the answer is no.

This machine is deterministically polynomial and uses oracle $B'$.

Thus we have proved that $U_{B'} \in P^{B'}$, a contradiction.

Therefore $U_{B'} \not\leq^{B'}_P 3SAT$.


Why don't most websites I visit seem to use TLS with Ephemeral Diffie-Hellman?

The typical process to establish a secure channel uses asymmetric cryptography for two purposes: to allow the parties to authenticate each other, and to establish a shared symmetric key (in TLS, that's the premaster secret). At least one of the sides needs to authenticate the other, otherwise the two sides could each establish a secure channel with a man-in-the-middle. The shared symmetric key must be established in such a way that a man-in-the-middle cannot find it out. There are many different ways to do this, and I'll focus on ways that are actually used in TLS.

Most TLS connections do authentication and shared key establishment independently. This is the only way in TLS 1.3 (except with pre-shared symmetric keys), and it's the most common way in previous TLS versions.

To establish a shared key, each side creates an ephemeral Diffie-Hellman key (usually elliptic-curve DH, but it can also be finite-field DH) and sends the public key to the other side. Each sides receives the other side's public key, calculates the shared secret, and discards the ephemeral DH key. Thanks to the security properties of Diffie-Hellman, it's impossible to reconstruct the shared secret by observing wire traffic: an adversary would also need to have one of the private DH keys. Hence this method guarantees perfect forward secrecy.

For authentication, the client authenticates the server. (The server can optionally authenticate the client, but having one side do authentication is enough to prevent active man-in-the-middle attacks.) The way this works is that the server sends a digital signature (RSA, DSA or ECDSA) of the handshake, i.e. of the packets that both sides have either read or written so far, and the client verifies this signature. The client either already knows the server's public key (public key pinning or raw public keys, both rare settings), or far more commonly verifies a certificate chain from a root certificate authority trusted by the client to the server's public key.

The authentication process has no impact on the shared key establishment. That's why you don't find anything about Diffie-Hellman in the certificate information: it isn't involved in that part of the protocol. The algorithms mentioned in the server certificate are the one used to sign the handshake (subject public key algorithm) and the one used by the CA to sign the certificate (certificate signature algorithm).

By the way, “PKCS#1 v1.5 RSA Encryption” in X.509 certificates is called this for historical reasons, but it's actually a PKCS#1 v1.5 RSA signature.

TLS ≤1.2 also has cipher suites that use static Diffie-Hellman (also called non-ephemeral Diffie-Hellman). With these cipher suites, DH also provides the authentication part of the process. The server always uses the same DH key. The client verifies that the DH public key that it receives from the server is the one that it expects. If an adversary tries to impersonate the server and sends the legitimate server's public key, they won't be able to calculate the shared secret because they don't have the private key. If an adversary tries to impersonate the server and sends their own public key, the client will abort the connection because it sees a public key that is not the expected one. Static Diffie-Hellman does not provide forward secrecy, since obtaining the server's static private key is enough to decrypt all past recorded traffic.

Just like with signature-based cipher suites, the client doesn't actually need to know the server's public key in advance. The client can use a public key infrastructure to validate the server's public key: it checks that the server's public key comes in a certificate that has been signed by a (chain of) CA that the client trusts. An X.509 certificate can contain a signature of an (EC)DH public key. It's rarely done in practice, because it only has a marginal performance benefit, it's less secure (no forward secrecy), and there's a self-reinforcing loop that almost nobody does it (because there's no reason to) so almost nobody implements support for it (because there's no demand) so almost nobody does it (because there's no software support).


Size of the language accepted by a Turing Machine

... what does $|L(M)| \leq 10$ mean?

This means that the size of the language accepted by the TM $M$ is less than or equal to $10$. In other words, TM $M$ accepts no more than $10$ strings (inputs), while the length of any accepted input may be greater than $10$.


What's the dual problem of stable matching?

From http://kuznets.fas.harvard.edu/~aroth/papers/1993_MOR_StableMatchingsOptimal.pdf :

  Shapley and Shubik (1972) observed that [the dual] formulates the problem of finding payoff vectors in the core of the above assignment game.

The assignment game described is that two agents who choose to match get a total "value" equal to the edge weight between them, and they can split this value between them in some way; these are the "payoffs".

It might be nice for future readers if you put the LP and dual in your question....


Recover a matrix with minimum number of queries

Let me consider the case $n = m$ for concreteness. Since the entropy of $A$ is $n\log n$ and each question results in at most one bit of information, at least $n\log n$ queries are needed.

Suppose that a question is selected uniformly at random. The probability that the answer is zero is $(1-1/n)^n \approx 1/e$, and in that case, we can mark all the queried entries as zero. Imagine making such queries until $N$ are successful. This is the same as making $N$ queries, each of which involves $n$ zero positions at random. The probability that a particular zero position is never queried is
$$
\left(1 - \frac{n}{n(n-1)}\right)^N \approx e^{-N/n}.
$$
Therefore after $(2+\epsilon) n\log n$ queries, the probability that a particular zero position is never queried is at most roughly $n^{-2-\epsilon}$, and so the probability that not all zero positions are revealed is at most $n^{-\epsilon}$. We conclude that $(2e+\epsilon) n\log n$ queries suffice to reveal the matrix with probability $1-o(1)$.

We can repeat the calculation for general $m$, but the bounds no longer match. For example, when $m$ is very large, the answer to most questions will be zero, and so bounding the amount of information obtained from a single query by one bit is too generous.


In my answer I will assume that all numbers are at most $M$ big, i.e. $A[i] \le M$.
First some comments about your both approaches.
Computing the GCD takes $O(\log M)$ time. So your first approach is actually $O(N^2 \log M)$.
I also don't think that your second approach is actually better than $O(N^2)$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $\Theta(N)$ effort for each divisor of $N$. Which means that the complexity for such a test case is something like $O(N^2 \sqrt M)$.

Let's first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.
Let's define the function $f$ as $f(i)$ is the smallest number of subarrays in which you can split the prefix of size $i$ of the array (the first $i$ numbers). Also let $f(i) := \infty$ if it is not possible to split the array, and $f(0) := 0$.
It's easy to see, that you can compute $f(i)$ using the recursion:
$$f(i) = \min_{\substack{1 \le j \le i\\ \gcd(A[i], A[j]) > 1}} f(j-1) + 1$$
This formula is very trivially to implement together with dynamic programming, and will have the complexity $O(N^2 \log M)$.
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for j = 1 to i:
        if gcd(A[i], A[j]) > 1:
            f(i) = min(f(i), f(j-1)) + 1
print f(N)

Now to a better approach. We need two mathematical facts that will help us:

If two numbers have a common divisor greater than one, then they have a common prime factor.
A number $\le M$ has at most $\log M$ prime factors.

Let the set of prime factors of $x$ be $P(x)$.
Then we can also rewrite the recursion for $f$ as:
$$f(i) = \min_{p \in P(A[i])} \left( \min_{\substack{1 \le j \le i\\ p ~|~ A[j]}} f(j-1) \right) + 1$$
In other word, if $A[i] = 20 = 2^2 \cdot 5$, then we look for all previous numbers who are divisible by 2, and take the minimum of $f(j-1)$, and for all previous numbers who are divisible by $5$ and take the minimum of $f(j-1)$. The actual optimal value $f(i)$ will one more than the minimum of both.
If we define $g(p, i)$ as the minimum of $f(j-1)$ with $p ~|~ A[j]$ and $1 \le j \le i$, then the formula simplifies to:
$$f(i) = \min_{p \in P(A[i])} g(p, i) + 1$$
We can actually apply some sort of dynamic programming also to the function $g$.
We store the values in a hash table.
First we initialize the function for every possible prime factor with $g(p) = \infty$, and whenever a $f(j-1)$ changes, we update $g(p)$ for every $p \in P(A[j])$.
This means, after we update $f(i)$, we only need to update $O(\log M)$ different values of $g$.
This gives us the following algorithm:
# initialize g
for all p:
    g(p) = infinity

# set the first value f(0)
f(0) = 0
# update g
for p in P(A[1]):
    g(p) = min(g(p), f(0))

for i = 1 to N:
    # first compute f(i)
    f(i) = infinity
    for p in P(A[i]):
        f(i) = min(f(i), g(p)) + 1

    # and then update g
    if i < N:
        for p in P(A[i+1]):
            g(p) = min(g(p), f(i))
print f(N)

It's easy to see that this algorithm runs in $O(N \log M)$ time.
A shorter variation, but with the exact same approach and complexity, would also be:
for all p:
    g(p) = infinity
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for p in P(A[i]):
        g(p) = min(g(p), f(i-1))
        f(i) = min(f(i), g(p)) + 1
print f(N)

The only thing to discuss is, how we get the prime factorization of each number.
There are loads of different approaches.
For instance if $M$ is not too big, you can compute the Sieve of Eratosthenes in $O(M \log M)$ and during the computation store a prime factor for each number $\le M$. This allows to compute the prime factorization of each number in $O(\log M)$.
Another option would be just to compute the prime factors on the fly, which would give take additionally $O(N \sqrt{M}$) time if you use the typical trial division until square root algorithm.


The terms forward, back and cross edges classify edges in the original graph with respect to the depth-first search, so they don't appear in the DFS tree itself. Different DFS runs may yield different classifications. They are useful in some algorithmic contexts.

You can read more on Wikipedia.


Solving cycle in undirected graph in log space?

The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the edge counter by half the degree of $u$. After going over all vertices, we have counted the number of vertices $V$ and edges $E$ in the connected component containing $v$. This component contains a cycle if and only if $E \geq V$.


How about "message strings are associated with keys"?


Optimal way to pack items with multidimensional weight such that the number of items is minimized?

This problem is NP-hard, so you can't expect a general algorithm that is efficient and always correct.  In particular, in the special case where the goal vector has only 1's and 0's in it, it becomes an instance of the exact cover problem.
Your problem can be viewed as an instance of the multidimensional subset sum problem.
If you have to solve it in practice, I would suggest formulating it as an instance of integer linear programming and using an off-the-shelf ILP solver.


What are the implications of Lean not having the type `Set`?

In Coq Set behaves basically like the smallest possible Type. Unlike Coq however, Lean lets you select the "level" of the type manually, such as Type 9 (or Sort 10), something which is not allowed in Coq - meaning that you do not need Set in Lean, you can just use Type 0 (or just Type, or Sort 1) instead as it is basically the same thing.
I should also note that in Lean Prop is the same as Sort 0 (or Sort) (which does not have large elimination) and Type n (for n : nat) is the same as Sort (n + 1) (which has large elimination).

TL;DR: Type (with no "arguments") is the Set of Lean


You've left out part of the statement.  It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow."  If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$.  The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated.  The $s$ to $c$ link is saturated.


Removing lambda-productions when it's at the start symbol

You cannot, in general, remove all $\lambda$ productions. Indeed, if you grammar produces the empty string, then somewhere in the grammar there must be a $\lambda$ production.

There are two ways to handle this problem:

Consider only grammars not producing the empty string. Such a grammar won't contain the product $S \to \lambda$.
Allow arbitrary context-free grammars, and also allow the production $S \to \lambda$ (but not $A \to \lambda$ for $A \neq S$). If the grammar does contain the rule $S \to \lambda$, then we also ask $S$ not to be on the right-hand side of any production. Such grammars behave very similarly to grammars without $\lambda$ productions, since the production $S \to \lambda$ can only be used in the derivation $S \Rightarrow \lambda$.


Here is a slight modification of Kruskal's algorithm which can solve this.

Sort all edges by non-decreasing weight.
Maintain a disjoint set union to track which vertices are connected, as usual.
Consider the edges one by one in the resulting order.
If an edge connects two vertices which are already connected, we drop it, as usual.

The difference is as follows: if an edge connects two components such that each already contains a factory, such edge would contribute nothing to our network, so we also drop it.

If an edge connects two components, and at least one of them does not contain a factory, we take the edge and update the disjoint set union, as usual.

Another view with the same result is as follows.
Make an auxiliary vertex, the super-factory.
Add an edge of weight 0 from the super-factory to each of the real factories.
Run Kruskal algorithm on this new graph.

First thing, it will take all our added edges with weight 0.
If the original graph also had such edges, let the algorithm start with our newly added edges. We can do it since the total cost does not depend on the ordering of same-weight edges.

Now, the original condition “each shop must be connected to a factory” got translated to “each shop must be connected to the super-factory”, which is equivalent to just “all vertices must be connected”, which in turn is exactly what Kruskal algorithm will do for us.


How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?

We have
$$
T(n) = \sum_{m=3}^n \frac{1}{m\log m} + T(2).
$$
We can bound
$$
\int_3^{n+1} \frac{dx}{x\log x} \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \int_2^n \frac{dx}{x\log x}.
$$
Since $(\log\log x)' = \frac{1}{x\log x}$, this shows that
$$
\log\log(n+1) - \log\log 3 \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \log\log n - \log\log 2,
$$
and so $T(n) = \log\log n + \Theta(1)$.


Hint: We have $F_n = [\varphi^n-(-\varphi)^{-n}]/\sqrt{5} = \varphi^n/\sqrt{5} \pm o(1)$, since $|1/\varphi| < 1$. Hence
$$ 2^{F_n} = 2^{\varphi^n/\sqrt{5}} 2^{\pm o(1)} = 2^{\varphi^n/\sqrt{5}} (1\pm o(1)). $$
In particular, $2^{F_n} = \Theta(2^{\varphi^n/\sqrt{5}})$. I'll let you compare $2^{\varphi^n/\sqrt{5}}$ and $2^{\varphi^n}$ yourself.


LL(1) CFG for triple amount of b's compared to a's?

I believe that any string able to be represented by a CFG can also be parsed in LL or LR. That is just one of the features of CFG's. The grammar you have originally written can be parsed using LL as the upper-case $A$ will act always as your left-most variable to be expanded and simplified.

I think your problem with constructing the grammar can be solved by also including rules in which the lower-case and upper-case $a$'s are switched, though, that is a rather clunky solution.

$S \rightarrow A$

$A \rightarrow \epsilon | baAbb | bAabb | bbbaA | bbbAa | bbaAb | bbAab | aAbbb| Aabbb$


Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

I choose to Ogden pumping word $s = a^{p}b^{p + p!}c^{p}d^{p + p!}$ and $ p > n$.

I am afraid you could not show that Ogden's pumping lemma cannot be applied to $s$ since $s$ belongs to the context-free language, $P_1=\{a^{k}b^lc^md^n\mid k\not=l\wedge m\not=n\}$, which is a subset of $L^C$.

Although your approach does not work, your conclusion that $L^C$ isn't context-free is correct.

Well, you are quite near the right approach.

Let $P_2=L^C\cap L(a^*c^*b^*d^*)=\{a^{k}c^mb^ld^n\mid k\not=l\wedge m\not=n\}$. We can show word $a^{p}c^{p}b^{p+p!}d^{p + p!}$ cannot be pumped as described in Ogden's lemma for $P_2$ when all of its $a$'s are distinguished. Hence $P_2$ is not context-free. Since $L(a^*c^*b^*d^*)$ is regular, $L^C$ cannot be context-free.

Exercise 1. Show $P_1$ is context-free. Show $P_3$ is context-free, too where $P_3=\{a^{k}c^md^nb^l\mid k\not=l\wedge m\not=n\}$.

Exercise 2. Show $P_2$ is not context-free following the approach given above.

Exercise 3. Show the complement of the following language is not context-free, $\{ w : |w|_{a} = |w|_{b} \vee |w|_{c} \not= |w|_{d} \}$.


Can I Use Machine Learning to Predict the Likelihood of an Order Being Shipped?

Here's the thing to know: machine learning assumes that there is some sort of statistical distribution, and you "learn" that distribution, in order to get the probability of some event.

The common saying in machine learning is "garbage in, garbage out." You have a bunch of random variables, but if those variables are all statistically independent, then you won't get anything useful from machine learning.

Say, for example, that there was a strong correlation between the amount of money paid for the carrier, and whether the item is shipped. Machine learning would likely be able to discover this relationship.

Or, if there were certain periods of the year where an item was more or less likely to be shipped. Machine learning could find this out.

But, if there's no underlying pattern in the data you give to your training algorithm, then you will get no useful information out of it.

For your question of finding the best data points: don't. That's what the machine learning algorithm is for. You give it your data, and it looks at which ones are statistically relevant, given some threshold. The whole point of machine learning is letting the algorithm do that for you, and more importantly, that's all the algorithm can really do for you.

Generally, these algorithms will work better when they have more data, so don't go out of your way to remove what data you're giving it.

And, remember, that ALL these algorithms are doing is statistics. If it says that the item is shipped with probability 0.6, don't be surprised when it isn't shipped. And, it's possible that it will say the item is shipped with probability 0.99, but it won't ship, because there's some variable which is hugely important in real life, which you didn't have recorded for your data set. If that variable isn't correlated with your data, then your model will be no good.


Why a language specified by a regular expression is not a complement of a given language?

The complement of a language $L$ should contain all strings not in $L$. Your language $L$ doesn't contain the word $0$, which the language $(10)^*$ also doesn't contain – so $(10)^*$ can't be the complement of $L$.


Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence
$$ C_{n+1} = \sum_{i+j = n} C_i C_j, $$
which follows directly from the interpretation as counting binary trees. You can use this formula to decode a number in $[0,C_{n-1}) = \{0,\ldots,C_{n-1}-1\}$ to a binary tree. If the index is chosen randomly, you obtain a random binary tree.

The decoding procedure is recursive. First, we partition $[0,C_{n-1})$ into intervals of lengths $C_0 C_{n-2}, C_1 C_{n-3}, \ldots, C_{n-2} C_0$. If the number falls in the interval of length $C_i C_j$, then the left subtree will have $i+1$ leaves, and the right subtree will have $j+1$ leaves. Within the interval, we have an index in the range $[0,C_i C_j)$, which we decode to a pair of indices $x \in [0,C_i)$ and $y \in [0,C_j)$. We recursively compute which tree with $i+1$ leaves is encoded by $x$ and which tree with $j+1$ leaves is encoded by $y$. The recursion stops when $n = 1$, in which case the tree consists of just the root.


Algorithm for designing a binary code with predefined distance

This is known as an embedding into $\{0,1\}^n$.  Your matrix $A$ defines a weighted graph, and you want an embedding into the hypercube.

I suggest you examine the literature on low-distortion graph embeddings, which have been studied in great depth in the computer science literature.  You might find some existing constructions on this topic.  I'm not deeply familiar with that literature myself and I don't know whether you will find anything directly applicable.


When talking about the length of a path in a graph, what exactly is a skip?

The second definition that you quote is informal, and open to interpretation. Fortunately, the same paper On $k$-skip shortest paths by Tao, Sheng and Pei contains a formal definition, Definition 2 on page 4.

That said, $k$-skip is not a common term, and doesn't really have a universally accepted definition (or indeed, any universally known definition), except perhaps in work following up on the Tao et al. paper mentioned above.


Big Oh rules - How to argue in case of negative base

If $C_n = -2^n + 2^n$, then this just simplifies to $C_n = 0$, so I assume that you mean $C_n = (-2)^n + 2^n$. Then:
$$
C_n \le |-2|^n + 2^n = 2^{n+1} = O(2^n).
$$


Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)

Every hash function is stateless; that's part of the definition of what it means to be a hash function.

A simple approach is to take a representation of the input in binary, using any standard encoding for the integers and for $n$-vectors of integers, and then hash the result using your favorite hash function.  The output will be a binary string.  Treat it as the binary representation of a number in the range $[0,1)$ (put a decimal point before the start of it, and interpret it in base 2).  That's your output.

Then, choose a suitable hash function for hashing binary strings.  If you need it for cryptographic purposes, you could use SHA256.  If you need it for non-cryptographic purposes, there are many standard, fast hash functions; choose one that meets your requirements.  Since you didn't state any precise requirements in the question, we have no basis to select among any of the standard solutions.


I don't know exactly where you're trying to get to with this, but I think you probably want to Taylor expand the division:

$$\frac{1}{1 - \delta_2} = 1 + \delta_2 + \delta_2^2 + \delta_2^3 + \cdots$$

Then, for example, if $\epsilon$ is the machine epsilon and $\delta_2 > 0$:

$$1 + \delta_2 \le \frac{1}{1 - \delta_2} \le 1 + \delta_2 + \epsilon$$

That is quite a tight bound, when you think about it. (Exercise: Prove that this is true if $\delta_2 \le 0$, too.)


Proof that total computable functions are not enumerable

$g$ is total computable by definition.

By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
$1$ certainly is.
$+$ certainly is.
The concatenation of $+$ and $f$ is computable by construction, and that's $g$.

The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here.

So under the assumption that such $f$ existed, $g$ is computable; therefore, it must have an index in $f$, which is impossible (as you note); therefore, the assumption must be false.


Intuitive meaning of modal $\mu$-calculus formula

Let's break it down.

First, let's look at $[-a]\phi$. This means every non-$a$ transition leads to a state where $\phi$ holds. It follows then that $[-a]\mathrm{ff}$ holds for states that have no non-$a$ transitions, which we will use when looking at the least fixed point semantics.

$\langle-\rangle\mathrm{tt}$ is pretty simple. It holds in any state that has any transition, i.e. is not deadlocked.

So together $\langle-\rangle\mathrm{tt} \land [-a]\phi$ means the state can take a transition and $\phi$ holds after every non-$a$ transition.

One way to view the meaning of $\mu Z.\phi(Z)$ is by the approximants referenced in your linked tutorial. If the formula is satisfied in state $s$ then there is some $\beta$ such that $\bigvee_{\alpha<\beta} \phi^{(\alpha)}(\mathrm{ff})$ is satisfied in $s$. The notation $\phi^{(n)}(x)$ means $\phi$ iterated on $x$, $n$ times, i.e. $\underbrace{\phi(\phi(\dots\phi(x)))}_{\text{$n$ times}}$. Let's look at some of these.

\begin{align}
\phi^{(0)}(\mathrm{ff}) &= \mathrm{ff} \\
\phi^{(1)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(0)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff} \\
\phi^{(2)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(1)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff}) \\
\phi^{(3)}(\mathrm{ff}) &= \langle-\rangle\mathrm{tt} \land [-a]\phi^{(2)}(\mathrm{ff}) \\
                        &= \langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a](\langle-\rangle\mathrm{tt} \land [-a]\mathrm{ff}))
\end{align}

Hopefully it is clear that these have the meanings

$\phi^{(1)}(\mathrm{ff})$: States that can take only $a$ transitions
$\phi^{(2)}(\mathrm{ff})$: Live states that

have only $a$ transitions; or
all length 1 non-$a$ paths lead to a live state with only $a$ transitions

$\phi^{(3)}(\mathrm{ff})$: Live states that

have only $a$ transitions; or
all length 1 non-$a$ paths lead to a live state with only $a$ transitions; or
all length 2 non-$a$ paths lead to a live state with only $a$ transitions

If that is unclear, remember that $[-a]\phi$ is trivially satisfied for states with no non-$a$ transitions.

Now you should see that $\phi^{(n)}(\mathrm{ff})$ is true if and only if the state can take at most $n-1$ non-$a$ transitions before reaching a live state with only $a$ transitions. It turns out that $\phi^{(n)}(\mathrm{ff}) \implies \phi^{(n+1)}(\mathrm{ff})$ so we don't need to take the disjunction with lesser approximants and can simply say $\mu Z. \langle-\rangle\mathrm{tt} \land [-a]Z \iff \exists \beta \in \mathbb{N}. \phi^{(\beta)}(\mathrm{ff})$, or in english, after a finite number of non-$a$ transitions we reach a live state with only $a$ transitions.


Runtime analysis of a "find the secret number" algorithm

You're almost there. It takes $O(\log S)$ time for your while loop to finish (by the way, how would you go about proving that? You can try induction on $\lceil \log_2 S \rceil$ or on $\lfloor \log_2 S \rfloor$, one of them should work). Then $\mathrm{low} \leq S < \mathrm{high}$. Furthermore $\mathrm{low}$ and $\mathrm{high}$ are certain powers of two, and so you can relate $\mathrm{high}-\mathrm{low}$ to $S$. More concretely, you want to bound $\mathrm{high}-\mathrm{low}$ from above in terms of $S$. This is the part you're missing. Perhaps you should try a few concrete examples and then generalize.


Is this phrase structure grammar from my textbook correct?

You are correct, in a sense. Speaking in formal notation, you have

$\qquad \displaystyle \mathtt{Sentence} \Rightarrow \mathtt{List}\ \mathtt{End} \Rightarrow \mathtt{Name}\ \mathtt{End}$

and we can not get rid of $\mathtt{End}$. We have not generated a wrong word, but a sentence that can not be derived further to any word. That is not a mistake in the grammar itself (with respect to the generated language), but certainly nasty if you think of parsing.

Your modification is valid. In particular, we do not need to generate lists of length one using rule 2 (which you make impossible by your modification) because we can just alternative 1 of rule 1.

Note that the grammar given is not the greatest (for parsing). For example, it is not context-free (rule 3). A better way to implement detection of the end is to generate the list the other way round ($\_$ denotes a space):

$\qquad \displaystyle \begin{align}
  \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\
  \mathsf{List} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{,\_}\ \mathsf{Name} \\
  \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry}
\end{align}$

Of course, this grammar is now left-recursive which is problematic for some parsing strategies (e.g. LL). So it may be useful to create the list from left to right after all, but keep generating the $\mathtt{and}$ at the start:

$\qquad \displaystyle \begin{align}
  \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\
  \mathsf{List} &\to \mathsf{Name} \mid \mathsf{Name}\ \mathtt{,\_}\ \mathsf{List} \\
  \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry}
\end{align}$

Now a parser working from left to right can always identify the next rule (with a lookahead of two to catch whether there is a comma behind a name).


Is $Ω(n\log n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

O($n$ $log$ $n$) lower bound complexity assumes the length of each key bit is constant.  If not, then in the worst case you must compare nearly all bits, and multiply the complexity by that length and get O($kn$ $log$ $n$)

In contrast, some non comparison sorts with arbitrary key lengths can be done in worst case O($kn$).

EDIT: To add more detail:

For Counting Sort, the worst case and average case are O($n+r$) where $r$ is the range of keys (max - min).

For LSD Radix sort the worst case and average case are O($n+k/d$) where $k$ is the key length and $d$ is the digit size.

You mention that there is no limit on key bit length.  It would seem that LDS Radix has better worst case performance:  $O(k(n+ln\ n))$ > $O(n+k/d$), putting aside other factors such as space.


Nothing is free.  GPGPUs are SIMD.  The SIMD instructions on GPGPUs tend to be wider than the SIMD instructions on CPUs.  GPGPUs tend to be fine-grained multi-threaded (and have many more hardware contexts than CPUs).  GPGPUs are optimized for streaming.  They tend to devote a greater percentage of area to floating point units, a lower percentage of area to cache, and a lower percentage of area to integer performance.

Let's do a comparison.  Intel's core i7-5960x has 8 cores, each with 4-wide (double precision) SIMD, running at 3 GHz (3.5GHz turbo), a 20M L3 cache, consumes 356mm^2 and 140W and costs \$1000.  So 8*4*3*4 = 384 double precision GFlops.  (The extra 4x is because you can do two fused-multiply-adds per vector lane per cycle.)  It can do 768 single precision GFlops.  That's about 1.08 DP GFlops/mm^2 and  2.75 DP GFlops/Watt.  There's also about 57.5 KB/mm^2 of on-chip cache.

NVidia's GeForce GTX Titan Black has 15 SMXs, each with 32-wide double precision SIMD, running at 890MHz (980MHz turbo), 3.5M of L1+L2 cache, consumes 561mm^2, 250W and costs \$1000.  So 15*32*.89*4 = 1709 double precision GFlops.  (Same 4x from two fused-multiply-adds per vector lane per cycle.)  It can do 5126 single precision GFlops.  That's about 3.05 DP GFlops/mm^2 and 6.8 DP GFlops/Watt.  So 3x the DP floating point density per unit area and 3x the DP floating point power efficiency.  And the tradeoff? 6.4 KB/mm^2 of on-chip cache. About 9x less dense than the CPU.

So the main difference is that the GPU has chosen an area balance that strongly favors floating point (and especially single-precision floating point) over cache.  Even ignoring the fact that you need to copy stuff back and forth between the CPU and GPU to do I/O, how well the GPU is going to do compared to the CPU depends on the program you are running.

If you have a data parallel floating point program with very little control divergence (all the vector lanes are doing the same thing at the same time) and your program is streaming (can not benefit from caching), then the GPU is going to be about 3x more efficient per unit area or per Watt.  But if you have any significant amount of divergent control, non-data-parallel work to do, or could benefit from large read-many-times data structures, the CPU will probably do better.


Converting a number from N to 0 in binary

I think you can just do a simple breadth-first-search on this. First note that:

There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop.
It doesn't make sense to do move #2 twice in a row.

The important thing to do while searching is to note whether the number we've arrived at was by doing move #2 (otherwise we'd get stuck in a loop). So here's a pseudocode:

Put the current number into a queue with flag 0
While the dequeued number is not zero:

If you can do move #1 on the dequeued number then do move #1 and put that in a queue with flag 0
If the dequeued number's flag is 0, then do move #2, and put that in the queue with flag 1


The birthday attack applies to any hash-function, regardless of its structure, and also to $h_i$.

For your first question, here is a possible hint. Note that

if we can find a collision in $h_i$ then we can find a collision in $h_0$ (by considering the top-most $h_0$, for instance).
if we can find a collision in $h_0$ then, we can find a collision for $h_i$ (by replacing one of the inner-most $h_0$ with it's collision).


Prove (p → ¬q) is equivalent to ¬(p ∧ q)

Can we use that $a \to b$ is same as $\neg a \lor b$? If yes then:
$$\neg (p \wedge q) \rightarrow (p\rightarrow\neg q) $$
is same as
$$(\neg p \lor \neg p) \rightarrow (\neg p \lor \neg q)
$$


Is the union between a regular language and a random language also a regular language?

The empty language is certainly regular. Take its union with any non-regular language $N$. What's the result?


Trustless exchange without a third party

This is known as the fair exchange problem.  There's lots of research on the topic; see the link for an overview and starting point.


Check for solution. Grouping should be done using 2 quads


Why Church-encoded types aren't sufficient to express inductive proofs?

How would you prove inside the pure CoC that the induction principle holds of the Church numerals? See Thomas Streicher's, Independence of the induction
principle and the axiom of
choice in the pure calculus
of constructions.


Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

What is a Segment Tree?

It is a data structure which is used to operate over a range of input.

  How does it work?

The original elements of the array form the leaves of the tree. Each internal node represents some merging of the sub trees. For example consider the array $A = [1,5,7,8,9,15]$.

If we were to construct a segment tree out of the array with the sum operation in mind, we would have the following tree.

  What about the run time complexity?

If we try to implement the $Sum(i,j)$ and $Change(i,x)$ operations via a segment tree, the time complexity would be the following:

 Construction of the Segment Tree: This would take $O(n)$ time.
 $Sum(i,j)$ : This would take $O(\log(n))$ time.
 $Change(i,x)$ : This would take $O(\log(n))$ time.

  What about the space complexity?

Being an almost complete binary tree, a Segment tree with $n$ leaf nodes will have $2n — 1$ total nodes. Hence the space complexity will be $O(n)$.


Which fingerprinting/hashing algorithms support compounding?

This falls into a general class of hash functions known as homomorphic hash functions.

Your question is not entirely clear about what definition you are using for $+$.  If you want the hash function to satisfy $h(x+y)=h(x)+h(y)$ where both instances of the $+$ operator refers to addition in a suitable group (e.g., addition of integers, xor), then such a hash is called linear.  A CRC hash is an example of a linear hash function.

It's important to distinguish concatenation from addition.  If you are looking for a hash that satisfies

$h(x||y) = h(x)+ h(y)$,

where $||$ denotes concatenation and $+$ denotes addition, then that's a different beast.  I don't know of any standard name for it.  This is a very restrictive property.  Such hash function will always necessarily have the form

$h(x) = \sum_i h(x_i),$

where $x_i$ is the $i$th character of the string $x$.  Consequently, the only way to achieve such a property is as follows: you choose some lookup table that maps from a single character to an integer; then you apply this to all the characters in the string and sum them up.  Unfortunately, such a hash is less than ideal, as a hash function, as any two strings that have the same characters in a different will yield the same hash value.  Thus if you use this as a hash function for a hash table, you might find an increased rate of collisions.  However, it would be easy to construct such a hash function.

There are other generalizations.  For instance, maybe you want a hash function with the property that

$h(x||y) = F(h(x), h(y))$

where $F$ is some associative function.  There are standard constructions of such a hash.  For instance, CRCs achieve this (though here $F$ depends on the length of $x$).

I suggest you also look at rolling hashes, the Rabin-karp rolling hash, Buzhash, AdHash, and MulHash.  See also the following resources:

https://crypto.stackexchange.com/q/17935/351
https://crypto.stackexchange.com/q/11420/351
the answers to https://crypto.stackexchange.com/q/1558/351


Does every data type just boil down to nodes with pointers?

Well, that is basically what all data structures boil down to. Data with connections.  The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in.  You should create a few data structures in C++ and check out where your objects land in memory.  It can be very interesting to learn about how the data is laid out in memory.

The main reason for so many different structures is that they all specialize in one thing or another. For example, it is typically faster to iterate through a vector instead of a linked list, due to how pages are pulled from memory.  A linked list is better to store larger sized types because vectors must allocate extra space for unused slots (this is required in the design of a vector).

As a side note, an interesting data structure you may want to look at is a Hash Table.  It does not quite follow the Nodes and Pointers system you are describing.

TL;DR: Containers basically all Nodes and Pointers but have very specific uses and are better for something and worse for others.


Finding a Hoare logic correctness proof for a Repeat-Until loop

Note that the loop is not the outermost construct in your program; that is a sequential composition. In order to apply this rule, you first need to take care of the initial assignments. In this case that is straightforward: you get that the formula $x>0\wedge y>0\wedge z=0\wedge u=x$ holds after $z:=0; \ u:=x$.

For the loop rule, you need three formulas: a precondition $P$, a postcondition $Q$, and an invariant $R$, satisfying the premises of the rule. The precondition $P$ also needs to follow from the formula we obtained above. The postcondition $Q\equiv z=x*y$ is already given in your initial triple. What is left to do is therefore to find $P$ and $R$ such that

$(x>0\wedge y>0\wedge z=0\wedge u=x)\to P$,
$\{P\}\ z:=z+y;\ x:=x-1\ \{R\}$,
$(R\wedge u\neq 0)\to P$,
$(R\wedge u=0)\to z=x*y$.

A special case which may be worth trying here is to assume that the third condition holds with equality, i.e. $P\equiv (R\wedge u\neq 0)$. This reduces the problem to finding $R$ such that

$(x>0\wedge y>0\wedge z=0\wedge u=x)\to (R\wedge u\neq 0)$,
$\{R\wedge u\neq 0\}\ z:=z+y;\ x:=x-1\ \{R\}$,
$(R\wedge u=0)\to z=x*y$,

which is essentially an application of the usual while rule. As for how to find $R$, that is in general a very tricky problem. You seem to be looking in the right direction, but you invariant still needs some work (checking which of the conditions it fails, and how, may help with that).


Notation for asymptotic bounds on both sides

I'm also not aware of any specific notation for the concept you want. In the example theorem statement in the question, there's nothing wrong with what you already have ("$\epsilon$ such that $\epsilon=o(\cdots)$ and $\epsilon=\omega(\cdots)$"). In other situations, it might be more convenient to say something like, "For any $\epsilon\in o(\cdots)\cap\omega(\cdots)$".


Why do we try to maximize Lagrangian in SVMs?

I think the answer to this deals with convex functions and duality.

$$L(w, b, \alpha) = \frac{1}{2}\|w\|^2 + \sum_i α_i(y_i(w \bullet x+b)-1).$$

When you minimize this, you are minimizing it over $w,b$. As you stated, this will produce the Lagrangian dual function:

$\Theta (\alpha) = inf L(w, b, \alpha) = \sum_iα_i-\frac{1}{2}\sum_{i,j}y_iy_jα_iα_j(x_i\bullet x_j)$

The maximization must be done here, but of the function $\Theta (\alpha)$ (the Lagrangian dual function).

Here is some background on why we are maximizing:

1) Let $p*$ be the optimal value of the problem of minimizing $\frac{1}{2}\|w\|^2$ (the primal). The Lagrangian dual function has the property that $L(w, b, \alpha) \leq p*$. It is a lower bound on the primal function. Instead of solving the primal problem, we are want to get the maximum lower bound on $p*$ by maximizing the Lagrangian dual function (the dual problem).

2) The primal problem is a convex function. The Lagrangian dual function is a concave function(can be verified). Maximizing a concave function is equivalent to minimizing a convex function. Therefore it is easy.

3) Why maximizing $\Theta (\alpha)$ is as good as minimizing $\frac{1}{2}\|w\|^2$: Let $d*$ be the value of $max \Theta (\alpha)$. This primal convex optimization problem satisfies Slater's constraint qualification which gives us strong duality ($d*=p*$). Therefore, $max \Theta (\alpha)$ is the same as $min \frac{1}{2}\|w\|^2$.


Why do we need to take the derivative of the activation function in backwards propagation?

As a disclaimer, I didn't read that page, but I can certainly explain where the derivatives come from. The backpropagation algorithm is actually a variant of the gradient descent algorithm.

Think about a single function for the moment. Suppose you have a function which responds to a single input and a single weight: $f(w, x)$. We want to adjust $w$ so that it gives expected answers for various known values of $x$.

Then by Taylor's theorem:

$$f(w + \delta w, x) \approx f(w, x) + \delta w \frac{\partial f}{\partial w}(w, x)$$

Or to put it another way:

$$f(w + \delta w, x) - f(w, x) \approx \delta w \frac{\partial f}{\partial w}(w, x)$$

So if you find a value for $x$ which gives the wrong output, this gives you an estimate of how "wrong" $w$ is, and it's related to the derivative of $f$.

This idea extends to multi-variate calculus. If you have a vector of weights and inputs $\mathbf{w}$ and $\mathbf{x}$, then Taylor's theorem says:

$$f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) \approx f(\mathbf{w}, \mathbf{x}) + \nabla_{\mathbf{w}}f \cdot \delta \mathbf{w}$$

Where $\nabla_{\mathbf{w}}f$ is the gradient of $f$ with respect to the weights only.

Now let's think about your case, where the function $f$ has a specific form: it's a function applied to the dot product of $\mathbf{w}$ and $\mathbf{x}$:

$$f(\mathbf{w},\mathbf{x}) = h(\mathbf{w} \cdot \mathbf{x})$$

Then:

$$\begin{align*}
f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) - f(\mathbf{w}, \mathbf{x}) & = h((\mathbf{w} + \delta \mathbf{w}) \cdot \mathbf{x}) - h(\mathbf{w} \cdot \mathbf{x}) \\
& \approx (\mathbf{x} \cdot \delta \mathbf{w})\, h'(\mathbf{w} \cdot \mathbf{x})
\end{align*}$$

Again, this gives you an approximation to how "wrong" the weights are given a "wrong" observation.

The backpropagation algorithm works by combining all of the training data into a single loss function which measures how "bad" the current set of weights is in training the data, and then does more or less exactly the above procedure, estimating the gradient of the loss function with respect to the weights, and then moving all of the weights in that direction.


Operating System: Busy waiting is not eliminated with semaphore?

So even if the process is in waiting state we still call it "busy
waiting"?

In the book, they are calling the mechanism as Busy Wait not because of the processes waiting in queue but rather for the fact that when multiple processes are trying to execute Wait() or signal() operation concurrently, they will have to busy wait.
Note that the variable "value" in the code of Wait() and signal() is a shared variable and hence critical section. Two processes should not be allowed to modify this variable concurrently. For synchronisation, we prefer the busy wait(spin lock) over non busy wait synchronisation mechanism because the code of Wait() or Signal() is pretty small and so processes which are waiting to execute "Wait()" will not have to spend much time waiting. Moreover, if you choose non busy waiting synchronisation mechanism in situation when the length of critical section is small(as it is here) then context switch overhead will waste more CPU time compared to the CPU time wasted in busy wait.
So what we have done is that we limited the busy waiting only to the critical section of Wait() and signal() operation. Earlier busy waiting was present in critical section of our application program.


Undirected graph with exponential number of simple cycles

The graph below contains $3m+1$ vertices and at least $2^m$ simple cycles (illustration has $m=3$):


Floating point Euclidean norm optimization

Roughly right.

You can first calculate the sum of squares. If it overflows, then you find a large power of two M, divide all numbers by M, calculate the norm, and multiply by M. If overflow happens at $2^{1023}$, then you have numbers greater than $2^{500}$. Dividing by M=$2^{700}$ means you get neither overflow nor underflow.

You may have underflow in some of the squares. Check how much error an underflow can produce. Then you check how large a sum wouldn’t be influenced by these errors. If the sum of squares is larger than say $2^{-900}$ then there may be products with underflow but they don’t affect the sum. In that case you are fine.

Otherwise, multiply all numbers by M, calculate the norm, and divide by M.


Is the P vs NP problem, an NP or co-NP problem?

It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing.

In a certain overly pedantic sense, the correct answer to your question is that the problem you care about is in P, since there's an algorithm which will answer every question of your form in polynomial (in fact constant time). But we don't know if that algorithm is just "Return  TRUE" or is "Return False."

The idea that the video may be touching on is the idea that if P != NP, then in general, finding proofs is hard. In fact, "Is statement S provable in formal system A with a proof of length at most x" is an NP-hard problem" (Questions in this are things like "Is there a proof of Fermat's Last Theorem that's shorter than 5 pages.") . And we also expect that if P != NP, for most "natural" NP-complete problems, random instances will often not be easy. So if P != NP, then searching for proofs should often be difficult, and thus we shouldn't be surprised that the proof that P != NP would itself be one of those. This may be what they were trying to say.


About the connection of pipelined execution and latency

In a processor that would nowadays be considered simple, you need two numbers for an instruction: what is the total execution time (for example 4 for load) and how long you need to wait before another independent operation can be issued - it seems that someone assumed 1 cycle between instructions for load. A different processor might only allow a load every two cycles, and your numbers would be totally different.
The PowerPC 603 was interesting in that a multiplication took 4 cycles, but it couldn’t start four multiplications in a row, so your multiplications would have started at cycles 4, 5, 6, 8, 9, 10, 12 etc.
Things get more interesting when you have multiple independent execution units; like you assume at least three units capable of load, store, and multiplication. And more interesting if you have limits decoding instructions, dispatching to execution units etc.


"Functional dependencies" with cardinality constraints

After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called numerical dependencies. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which is also referred to as a $k$-dependency.

Unfortunately, they are not finitely axiomatizable:

John Grant and Jack Minker (1985). Normalization and axiomatization for numerical dependencies. In: Inf. Control 65(1), pp. 1-17. https://doi.org/10.1016/S0019-9958(85)80017-6

The entailment problem is in EXPSPACE. However, there is a sound branch-and-bound algorithm that may be used:

Paolo Ciaccia, Matteo Golfarelli and Stefano Rizzi (2013). Efficient derivation of numerical dependencies. In: Inf. Syst. 38(3) pp. 410-429. https://doi.org/10.1016/j.is.2012.07.007

A general survey of the generalization of functional dependencies is

Loredana Caruccio, Vincenzo Deufemia and Giuseppe Polese (2016). Relaxed Functional Dependencies—A Survey of Approaches. In: IEEE Tran. Knowl. Data Eng. 28(1) pp. 147-165. https://doi.org/10.1109/TKDE.2015.2472010

An extension of numerical dependencies is $\mathit{CFD}^c$, conditional functional dependencies with cardinality constraints. This paper defines them, and gives some algorithms for satisfiability and entailment:

Wenguang Chen, Wenfei Fan and Shuai Ma (2009). Incorporating cardinality constraints and synonym rules into conditional functional dependencies. In: Inf. Process. Lett. 109(14) pp. 783-789. https://doi.org/10.1016/j.ipl.2009.03.021


Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?

Use two integers to represent one integer. Assume you are using c/c++. You can use a struct that has two long long unsigned integers to represent $x$, $y$ and $z$. So you can express $x = 2^{32}x_1+x_2$ with $x_1$ being a nonnegative integer smaller than $2^{32}$ and $x_2$ being a nonnegative integer not greater than $2^{32}$. I would assume you will know the rest.

Or you can choose to use some libraries or built-in classes. For example, you can use BigInteger class in Java.

(It goes without saying that you will not have these problems if you were using Python, Ruby, etc.)


Yves Caseau gave a method for efficiently encoding type hierarchies as bit vectors. See Efficient handling of multiple inheritance hierarchies.


VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points

Here are some ideas. Denote by $\{x\}$ the fractional value of $x$, and consider the function $f_n(x) = \operatorname{sgn} (\sin 2\pi n x)$. Then:

$f_n(x) = +1$ iff $\{nx\} \in (0,1/2)$.
$f_n(x) = -1$ iff $\{nx\} \in (1/2,1)$.

Suppose first that the set of points is independent over the rationals. Weyl's equidistribution theorem shows that $\{nx_1\},\ldots,\{nx_N\}$ is equidistributed over $[0,1)^N$, and in particular we can find $n$ for which $\{nx_i\}$ matches the label of $i$.

Another case is $x_i = 2^{-i}$. This case is often used to show that the collection $\{ f_n : n \in \mathbb{N} \}$ has infinite VC dimension. In this case we choose $n$ so that its binary expansion corresponds to the labels of the set (details left to the reader, or see Example 3 on page 4 of these lecture notes). Using Weyl's equidistribution theorem, we can generalize this to the case $x_i = 2^{-i} x_0$ for arbitrary $x_0$.

I see two possible arguments for the general case:

Perturb the $x_i$s slightly to new values $y_i$ that they are rationally independent, and apply the argument above. Intuitively, if the perturbation is small enough then $\{nx_i\} \approx \{ny_i\}$ and by asking that $\{nx_i\}$ be in (say) $(1/6,1/3)$ or $(2/3,5/6)$, we can guarantee that $f_n(x_i) = f_n(y_i)$. The difficulty with this argument is that the perturbation needs to be small as a function of $n$, and we don't know $n$ in advance, barring some uniform version of the equidistribution theorem.
Choose a basis $r_1,\ldots,r_m$ for $x_1,\ldots,x_N$ over the rationals such that each $x_i$ is an integer combination of the $r_j$, and then try to apply an argument similar to that of the second case. If $m=1$ then this argument seems convincing (though details need to be checked), but the general case seems a bit more difficult.

For an interesting strengthening of the rationally independent case, see this nice paper.


Understanding lemma found in proof of quotient construction for DFAs

Let us start with explaining the notation:

$F$ is the set of accepting states of some DFA.
We define an equivalence relation $\approx$ on the states of the DFA as follows: $p \approx q$ if for all words $x$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x)$, where $\hat\delta$ is the transition function of the DFA (extended from symbols to words).
We denote the equivalence class of a state $p$ by $[p]$.
$F' = \{ [p] : p \in F \}$.

Now suppose that $[p] \in F'$. According to the definition of $F'$, $[p] = [q]$ for some $q \in F$. Standard properties of equivalence relations imply that $[p] = [q]$ iff $p \approx q$. By definition of $\approx$, $\hat\delta(p,x) \in F$ iff $\hat\delta(q,x) \in F$ for all words $x$. Taking $x = \epsilon$, we see that $p = \hat\delta(p,\epsilon) \in F$ iff $q = \hat\delta(q,\epsilon) \in F$. Since $q \in F$, this shows that indeed $p \in F$.


The resulting precedence graph for your example will contain a cycle due to $R1(A) W2(A) R1(A)$. Hence its not conflict serializable. Since one example is sufficient to disprove the statement, therefore I agree with you. The answer might be wrong.


Proof for Minimum number of insertions to convert a string to a palindrome

As D.W. indicates, you use proof by induction. I'll explain this with some hints on the case $S[i] = S[j]$. The intuition is that if $S[i] = S[j]$ then the best way of converting $S[i],\ldots,S[j]$ into a palindrome is converting $S[i+1],\ldots,S[j-1]$ into one, and then converting this to a solution for $S[i],\ldots,S[j]$ at no further cost (how?).

Formally, we need to prove two things:

$c[i,j] \leq c[i+1,j-1]$.
$c[i,j] \geq c[i+1,j-1]$.

For the first inequality, you need to show that if you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting $m$ characters, then you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting at most $m$ characters. You get the first inequality by taking $m = c[i+1,j-1]$. The proof is not difficult and left to you.

The second inequality is more delicate. Now you need to show that if you can convert $S[i],\ldots,S[j]$ into a palindrome by inserting $m$ characters then you can convert $S[i+1],\ldots,S[j-1]$ into a palindrome by inserting at most $m$ characters. To show this, consider the insertions converting $S[i],\ldots,S[j]$ into a palindrome:
$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j],w_j.
$$
Here the $w_t$'s are words which may be empty.

  Claim: We can modify this solution to a solution with possibly less insertions in which at least one of $w_{i-1},w_j$ is empty.

(Proof left to you.)
If both $w_{i-1},w_j$ are empty then it is easy to complete the proof (details left to you). Otherwise, suppose without loss generality that $w_j$ is empty, that is, the insertions are

$$
w_{i-1},S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

Since $w_{i-1}$ is non-empty and the word is a palindrome, it must start with $S[j]=S[i]$. Writing $w_{i-1} = S[j] x$, we can rewrite this solution as

$$
S[i],x,S[i],w_i,S[i+1],w_{i+1},\ldots,w_{j-1},S[j].
$$

I'll let you finish the proof of this case from here, and to mimic this proof for the case $S[i] \neq S[j]$.


how to prove original intervals and canonical form of intervals have the same interval graph

You haven't described how a system of intervals are converted to canonical form, but here is one way to do it. We find an order-preserving mapping (satisfies $f(x) < f(y)$ iff $x < y$) from the coordinates in the original system to the integers $\{1,\ldots,2n\}$ (we do this by sorting all of the original coordinates). We get the same interval graph since the mapping is order-preserving – that's a nice exercise.


Maximum Expected Fishing Day (Recurrence Relation)

Although the subproblems are defined correctly in the approach quoted in the question, there are some typos and glitches when it comes to the base cases and recurrence relations.

Please see the corrected base cases and recurrence relations below.

Base case: for any $(m,d,v)$ such that $m$, $d$ or $v$ equals to 0,
$$\text{MEFD}(m,d,v) =0\tag{R0}$$

Recurrence Relations:
$$\begin{align*}
\text{MEFD}(m,d,v) &= \max(\text{MEFD}_{1}(m,d,v),  \text{MEFD}_{2}(m,d,v))\tag{R1}\\
\text{MEFD}_{1}(m,d,v)&=\frac{1}{d}(1+\text{MEFD}(m-1,30,v-1))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v-1)\tag{R2}\\
\text{MEFD}_{2}(m,d,v)&=\frac{1}{d}\text{MEFD}(m-1,30,v))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v)\tag{R3}
\end{align*}$$

Equation (R1) says that the maximum expected fishing days is the larger of the expected fishing days yielded by two strategies, John selects the next day and John does not select the next day. John will proceed with the best strategy in the remaining days.

Equation (R2) compute the maximum expected finishing days when John has selected the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v-1$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v-1$ vacation days.

Equation (R3) compute the maximum expected finishing days when John has decided to work for the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v$ vacation days.

Note "John needs to inform his boss in order to get time off from work at least a day in advance" is interpreted as something like if John wants to take tomorrow off, he can just inform his boss tonight, at which time he must have known whether today is a fishing day. If it is, he will not, of course, select any remaining day in the current month as a vacation day. That is why whenever the next day will be a fishing day, we will only consider the remaining $m-1$ months in the above recurrence relations.


Why do neural networks seem to perform better with restrictions placed on their topology?

Fewer nodes/edges (or edges with fixed weights) means that there are fewer parameters whose values need to be found, and this typically reduces the time to learn. Also, when there are fewer parameters, the space that can be expressed by the neural network has fewer dimensions, so the neural network can only express more general models. It is thus is less capable of over-fitting the data, and hence the models will seem more general.


What is the lower bound for the following equation

This is a quadratic function; therefore $f$ is big-Theta of $n^2$. Therefore, it is both Big-O and Big-Omega of $n^2$.

However, when a function $f$ is big-Omega of another function $g$, then $f$'s growth is of greater or equal order than $g$. However, since a quadratic grows strictly faster than a linear in the long run, $n^2$ is big-Omega of $n$. Think of as if big-Omega means "greater or equal than".

Also note when $f$ is big-Omega of $g$, then $g$ is big-O of $f$. Obviously, $n$ is big-O of both $n$ and $n^2$.


You can estimate your sum from below by
$$
1^k + \cdots + n^k \geq \sum_{m=\lceil n/2 \rceil}^n n^k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^k = \Omega(n^{k+1}).
$$
It is even easier to see that $1^k + \cdots + n^k \leq n^{k+1}$, and so $1^k + \cdots + n^k = \Theta(n^{k+1})$.

You can get better bounds by approximating the sum with an integral:
$$
\frac{n^{k+1}}{k+1} = \int_0^n x^k \, dx \leq 1^k + \cdots + n^k \leq\int_1^{n+1} x^k \, dx = \frac{(n+1)^{k+1}-1}{k+1}.
$$
This shows that
$$
1^k + \cdots + n^k = \frac{n^{k+1}}{k+1} + O(n^k).
$$

There is also an exact formula, known as Faulhaber's formula.


Assuming a 32-bit architecture (with alignment), then instructions are words; that is, every instruction is composed of 4 bytes.

That implies that the bottom two bits of the address are byte offsets within the word; that is, the address 10001111 denotes 4th byte of the word at 10001100. When we're talking about instructions, however, we'll never need to fetch individual bytes -- we want whole words.

Different textbooks handle the program counter differently, but given that whichever paradigm you're using has the program counter incremented by 1 (rather than 4), that leads me to believe that the PC stores word address, rather than byte address.

Then, if the program counter is at 10001111 and we increment by 1, we do in fact get 10010000. To turn this word address into a byte address (so we can fetch the instruction from memory), we can simply left-shift by 4.

In short, if the program counter is at 10001111 (the word address), then the byte address of the instruction we'll actually be fetching is 1000111100. To fetch the next instruction, we can just increment the program counter by 1.


What defines negative and non-negative type operators?

I can explain the mathematical background. Suppose we have a type operator $F$ that takes a type $A$ to a type $F(A)$, and we want to extend it so that it also maps functions. It should take a function $f : A \to B$ to a function $F(f) : F(A) \to F(B)$. This can often be done, for example if
$$F(X) = X + (C \to X)$$
for a fixed $C$, then we may define
$$F(f) : A + (C \to A) \to B + (C \to B)$$
in a natural way as
\begin{align*}
F(f)(\mathtt{inl}(a)) &= \mathtt{inl}(f(a)) \\
F(f)(\mathtt{inr}(g)) &= \mathtt{inr}(f \circ g)
\end{align*}
We say that $F$ acts covariantly on functions.

But sometimes the direction gets reversed! Consider
$$F(X) = X \to C$$
for a fixed type $C$. Then $f : A \to B$ can be mapped to
$$F(f) : (B \to C) \to (B \to A)$$
by
$$F(f) = \lambda g . g \circ f.$$
This time the direction was reversed. We say that $F$ acts contravariantly on functions.

In some cases we are stuck, for instance if $F$ mixes things up. An example would be $F(X) = X + (X \to C)$.

If $F$ takes several arguments it may act covariantly on some of them and contravariantly on others.

Covariance and contravariance are important mathematical concepts which show up in many places: category theory, physics, analysis, you name it.

The positive and negative occurrences of a type variable in a type expression tell you whether the corresponding type constructor acts covariantly (positive) or contravariantly (negative) in that position.

For example, in $F(X) = (X \to C) \to C$ we have a positive occurrence of $X$, and indeed $F$ acts on $f : A \to B$ covariantly to give $F(f) : F(A) \to F(B)$ defined by
$$F(f) = \lambda \phi : (A \to C) \to C . \lambda g : B \to C . \phi(g \circ f).$$


Is Turing machine a programmable machine or Is it like a fixed program computer?

Your regular stored program computer could be compared to the Universal Turing Machine (UTM) in that it can be seen as a multipurpose device. Any concrete UTM, nevertheless, still accepts only one base level language, as does the computer that you are using right now. "On top" of that language, other languages can be encoded, and the fact that programs/machines can be processed as data is what gives computers an enormous range of applications, or even "incarnations", which we have just begun exploring.

To answer your question directly: a TM that is programmable is also "fixed", depending on how you see it. Conversely, a machine doesn't have to be as powerful as the UTM to be considered programmable, in some way. In fact, many (very) useful languages are not Turing equivalent.

Regarding computational languages/machines, the notion that there would be something like a "proto-language", or "proto-machine" is misleading. The mythology that has been built around the general-purpose computer obscures its candid nature. The Universal in "Universal Turing Machine" should not be equated to absolute. It is a proposed definition of universality, mathematical in nature, which has been ever since reinstated, repeatedly, in so many ways that it is impossible to describe exhaustively.


Why can we assume an algorithm can be represented as a bit string?

You already have a representation of that function as text.  Convert each character to a one-byte value using the ASCII encoding.  Then the result is a sequence of bytes, i.e., a sequence of bits, i.e., a string over the alphabet $\{0,1\}^*$. That's one example encoding.


Why are there two not operators in lambda calculus?

The lambda-calculus is confluent. All the terms involved are strongly normalizing (these boolean encodings only work on booleans; they could do anything if applied to a lambda-term that doesn't reduce to $\mathrm{true}$ or $\mathrm{false}$). So the choice of reduction strategy is not relevant.

When something looks weird or incomprehensible on Wikipedia, check the history. Sometimes things get deformed over successive edits, and sometimes an edit is just wrong. WikiBlame can be very useful for that.

The edit that introduced the distinction between two evaluation strategy is from September 2012. It has no edit description, its content doesn't make sense (it implies that call-by-value is not an applicative-order strategy), and even the author was clearly not sure what they wrote (they left a comment with an interrogation).

The bit about normal order was added in December 2013 which was part of a series of edits mainly to improve the formatting and the wording. It doesn't look to me like the editor meant to change the meaning of the article, but they were mislead by the previous edit.

Hopefully someone will soon edit this article to rectify it, ideally with references for both of the not functions.

Incidentally, the choice of reduction strategy does matter if you want to extend these functions outside the booleans. For example, if you want to have $\mathrm{if}\,b\,M\,N$ where $b$ is a boolean (a term that reduces to $\mathrm{true}$ or $\mathrm{false}$) and $M$ and $N$ are arbitrary terms, then this behaves differently depending on the evaluation strategy. With call-by-value, this only terminates if $M$ and $N$ terminates. With call-by-name, this terminates if whichever of $M$ or $N$ is selected terminates, and the one that isn't selected doesn't matter. This is the reason why if can be defined as a function in languages that use call-by-name or lazy evaluation such as Haskell, but it needs to be a special form in languages that use eager evaluation such as Lisp and ML.

Another case where the evaluation strategy matters is if you want to work on partial booleans, that is, terms that either reduce to one of $\mathrm{true}$ or $\mathrm{false}$ or don't terminate ($\bot$). For $\mathrm{not}$, the choice of evalation strategy doesn't matter: $\mathrm{not}\,\bot = \bot$ anyway. For an operator like $\mathrm{or}$, the evaluation order does matter: $\mathrm{or} \, \mathrm{true} \, \bot$ could be either $\mathrm{true}$ or $\bot$, and likewise for $\mathrm{or} \, \bot \, \mathrm{true}$. With eager evaluation, they're both $\bot$, but with left-to-right normal order $\mathrm{or} \, \mathrm{true} \, \bot \to \mathrm{true}$ while $\mathrm{or} \, \bot \, \mathrm{true}$ does not terminate. It's natural to wonder if there could be a more clever implementation of $\mathrm{or}$ that always picks its terminating argument regardless of the evaluation strategy. This problem is known as Plotkin's parallel or, and it's an important result in the theory of the lambda calculus that there is no such term. There is no way for a lambda calculus function to take two arguments and evaluate them “in parallel”, reducing them and stopping as soon as one of them terminates. The function can be weakly normalizing (it terminates in some evaluation strategies) but not strongly normalizing (there are evaluation strategies where it doesn't terminate). Thus the lambda calculus is said to be inherently sequential. It's a very nice model of sequential computation, but if you want to model parallelism or concurrency, you need other tools.


Resolution and what it means to derive the empty set

To complete the Kyle's answer:

A CNF (in Conjunctive normal form) formula, $F$, can be considered as a set of clauses, eg : $F=\{C_1,C_2 \ldots C_m\}$ and each clause can be regarded as a set of literals, eg : $C_1=\{x,y\}, C_2=\{\lnot x, \lnot y\}$.

If $F=\varnothing$ i.e. $F$ is the empty set and does not contain any clause then $F$ is satisfiable (=tautology).

If $F=\{\varnothing, C_1 \ldots\}$ i.e. $F$ contains the empty clause then $F$ is not satisfiable. The empty clause can be obtained by the resolution rule eg : the resolvent of $C_3=\{x\}$ and $C_4=\{\lnot x\}$ is the empty clause $\varnothing=\{\}$.


Note: I am the user who gave the comment cited in the OP on the CSTheory thread. Also, I am writing this as an answer rather than a comment to JohEker's post as I do not have enough reputation here to comment.

The idea is to exploit that we have a finite, local bound on the difference between zeroes and ones in the input word, i.e. we accept every word where this difference does not exceed 1 at any point. Note that if we drop the requirement that this holds for all prefixes, then the language is not regular (and thus not recognized by a DFA) by the Myhill-Nerode theorem as pointed out by JohEker.

So let $\#0(w)$ and $\#1(w)$ denote the number of ones and zeroes in the word $w$ respectively. To build a DFA from the idea above, we see that a word $w$ should be accepted if every prefix $v$ of $w$ satisfies $|\#1(v) - \#0(v)| \leq 1$, or equivalently $-1 \leq \#1(v) - \#0(v) \leq 1$.
We can keep track of the value $\#1(v) - \#0(v)$ by creating a state for every value of it that we care about and specifying transitions between these states to model how the counter changes when we read a $0$ or a $1$.
Combining this with our previous idea that we only need to know if the value of the counter is between $-1$ and $1$, we create three states $q_{-1}, q_0$ and $q_1$.

Clearly we want the initial value of the counter to be $0$, so we use $q_0$ as the initial state of our automaton and we transition from $q_k$ to $q_{k+1}$ if we read a $1$ (for $k \in \{-1, 0\}$ -- else we leave the space of values that we are interested in; more on this later) and similarly we transition from $q_k$ to $q_{k-1}$ (for $k \in \{0, 1\}$). As we want to accept the words for which the counter ends up at 0, we also define $q_0$ as the only accepting state.

Now, what happens if the counter does not stay within $\{-1, 0, 1\}$? We want to reject the input.

In our automaton, this corresponds either to reading a $0$ while we are in the state $q_{-1}$ (i.e. we have $\#1(v) - \#0(v) = -1$ that for the input $v$ before reading the $0$ and thus $\#1(v0) - \#0(v0) = -2$) or reading a $1$ while we are in the state $q_1$. So we introduce a new, "rejecting" state $q_s$ (also called a sink-state as the DFA cannot escape from this state once it is reached) which we transition to in case we detect one of the above-described scenarios. This now completes the description of our DFA, which looks like this:


Find a diffrent minimal spanning tree for a graph

You cannot find such a MST. Every two minimal spanning trees must have the same multiset of edge-weights.
Actually you can find the proof in the link that Raphael added:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?


Which is more computationally efficient: multiplication or 0 padding?

I'm assuming that your numbers are in binary. In this case, 0 padding is shift left: x << 3 is the same as x * 0x08, where 0x08 (hex) is 1000 (binary).

Shifting is much simpler to implement in hardware and is generally more efficient. You could check by writing a short C program.

Note that there is one significant difference between shift left and multiplication. The former does not signal if there is an overflow error, whereas the latter will.


If you could solve this problem, then you would be able to solve the NP-complete PARTITION problem. The partition problem asks whether a given set of positive integers $X$ can be partitioned into two equal parts. Given a set $X$ whose sum is $M$, choose an arbitrary ordering of its elements $X = \{x_1,\ldots,x_n\}$, and let $A=B=X$. Your problem asks to maximize
$$
f(S) = \left(\sum_{i \in S} x_i \right) \left(M - \sum_{i \in S} x_i\right).
$$
As a quadratic in $\sigma = \sum_{i \in S} x_i$, $f(S)$ is maximized at $\sigma = M/2$, at which we have $f = (M/2)^2$. This is achievable for some set $S$ iff $X$ can be partitioned into two equal halves.


The inner loop will iterate once with $j=i+1$, once again with $j=i+2$, and so on, up to the last iteration with $j=n-1$, so there will be, for each $i$ in the outer loop, $(i+1)-(n-1)-1=n+i-1$ time contributions from the inner loop. Add these to get your answer.


Technically it is a linear grammar, where every production is of the form $A\to uBv$ where $A,B$ are variables, and $u,v$ are terminal strings. The linear languages are in between the regular and context-free languages.

The power of these grammars is reduced because in every string (sentential from) derived there is (at most) one variable. They are more powerful than right-linear grammars because the terminal strings that are generated during the derivation can appear both left end right from the variable. An example of a linear language that is not regular is $\{a^nb^n \mid n\ge 1\}$.
An example of a language that is context-free, but not linear, is $\{ w\in\{a,b\}^* \mid w \text{ contains the same number of $a$ and $b$}\}$.


DFA for w|w has a length multiple of 2 or 3

Creating a state machine for each and combining the two is not a bad idea. To create a state machine accepting words having length N you can have each state represent the current length mod N.

After creating the two machines you can add a state having two epsilon transitions to the starting states of both machines. This gives a NFA accepting your language.

In a final stage you use the subset construction algorithm to convert the NFA you got into a DFA.


Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand?

Back to the definition. According to Wikipedia, a context-free grammar $G$ is a 4-tuple $(V, \Sigma, R, S)$. In this case, $G = (V, \Sigma, R, S)$ can be defined as

$V$, nonterminals, is $\{S\}$,
$\Sigma$, terminals, is $\{a\}$,
$R$, production rules, is $\{ S \mapsto Sa \}$, and
$S$ is the start symbol and an element of $V$.

So this is a context-free grammar although the language recognized by $G$ is empty as you noticed.

You can also verify whether this is a regular CFG by going back to the definition.


generation-compare-and-swap, or GCAS, in CTries

Nice observation.

To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying the root. Any modification of the root is only successful if the value below the main I-node did not change.

All reads of the root location are in the actual code calls to RDCSS_READ_ROOT:

https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/concurrent/TrieMap.scala#L694

And all CASes to the root are similarly replaced with an RDCSS. More details about this instruction in this paper:

https://timharris.uk/papers/2002-disc.pdf

I guess this important detail that you noticed (and in fact, you are maybe even the first person to notice so far, besides myself) was left out of the paper to keep the text clear.


What complexity class does is this set of grammars? NL-complete?

Yes, you can build a reduction to show that the following problem is NL-complete:

  Given a grammar where every rule has the form $X \to Y$ or $X \to a$ where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

This problem is equivalent to testing whether $a$ is reachable from $S$ in the corresponding directed graph, which is exactly the ST-connectivity problem.

I didn't understand what you meant by a|b.


How complete directed graph with n-vertices is connected to the n-dimensional simplex and its triangulation?

Here is what it boils down to. There are $n$ vertices $v_1,\ldots,v_{n-1},v$. For each $i$, there is an edge either from $v$ to $v_i$ or from $v_i$ to $v$. We need to show that one of the following holds:

There is an edge from $v$ to $v_1$.
There is $i < n-1$ such that there are edges from $v_i$ to $v$ and from $v$ to $v_{i+1}$.
There is an edge from $v_{n-1}$ to $v$.

Let $x_i$ be a Boolean variable denoting that there is an edge from $v$ to $v_i$. Then we need to show that the following DNF is a tautology:
$$
x_1 \lor (\lnot x_1 \land x_2) \lor \cdots \lor (\lnot x_{n-2} \land x_{n-1}) \lor \lnot x_{n-1}.
$$
Hopefully you can manage to prove this yourself. It just states that if we have a string of 0s and 1s, then one of the following must happen:

The string starts with 1.
The string contains 01.
The string ends with 0.

The easiest way to see this is to prove the following:

  If a binary string starts with 0 and ends with 1, it must contain 01.

This is just the trivial one-dimensional case of Sperner's lemma.


Maximum size of Huffman codes for an alphabet containing 256 letters

I don't see how to approach the problem.

OK, here is how you can approach the problem.  Can you solve this problem if you replace the number 256 with the number 3?  How about 4?  5?  Try solving those special cases, then see if you spot a pattern...

This is a useful, general pattern.  When a problem is too hard, try to find a simpler version of it and think about that.  When you see a constant in the problem, try solving simpler versions where the constant is smaller (so the problem becomes easier to think about), then look for a pattern, try to generalize, form a hypothesis, and see if you can prove your hypothesis.


Is the "modular subset product" problem NP-complete?

The claim that you linked to (that subset product is strongly $NP$-complete), is incorrect: it is only weakly so. The numbers $s\in S$ are small and can be represented in unary, but $t$ has to be represented in binary for the reduction to work.

If you consider it over $\mathbb{Z}_n$ it remains weakly $NP$-complete, since we can just take $n$ to be $\Pi_{s\in S} s$. In this case, the fact that we're doing modular arithmetic becomes irrelevant. $n$ will be exponential in $\Sigma_{s\in S} s$ so that $\log n$ (the size of a binary representation of $n$) will be polynomial in the size of the original instance (in which all $s\in S$ were represented in unary).


Finding triples that satisfy given constraints in $O (n \log n) $ time

Let us shift all of your indices by $1$. The condition on the indices then becomes $j^2 = ik$. The number of factorizations of $j^2$ into $i \cdot k$ is at most $d(j)^2$, where $d(j)$ is the number of divisors of $j$.  Therefore the total number of potential triples $(i,j,k)$ is at most
$$
\sum_{j=1}^n d(j)^2 = O(n\log^3 n).
$$
(For the estimate, see this question on Mathoverflow.) Note that the actual number of triples can also be bounded by $\sum_{j=1}^n d(j^2)$, which could be smaller (and it could be yet smaller even than this sum).

This means, at the very least, that if you know $n$ in advance, then you can make a list of $\tilde{O}(n)$ triples, and solve the problem in time $\tilde{O}(n)$. Using a sieve of Eratosthenes, you can likely also calculate the triples in $\tilde{O}(n)$; it might be worthwhile to store all primes at most $500,000$ ahead of time.


Number of edges in a graph with N vertices and K components

Think of the extreme case when all the components of the graph except one have just one vertex. This is the case which will have the most no. of edges. We can prove it by contradiction as follows:Suppose there were two strongly connected components having $m$ and $n$ vertices where $m < n$. Now if you remove a vertex from the one having $m$ vertices and add it to the other component, then effectively you have removed $m-1$ edges from the first graph and added $n $ edges to the second graph. So, there is a net gain in the number of edges. So the maximum edges in this case will be $\dfrac{(n-k)(n-k+1)}{2}$.As for the minimum case, since we have seen that distributing the edges with uniformity among the graphs leads to an overall minimization in their number, therefore first divide all the $n$ vertices into $k$ components to get the number of vertices in each component as $n/k$. We will still be left with  $n\mod k = f'$  vertices. Let's call $\Biggl\lfloor{\dfrac{n}{k}}\Biggr\rfloor$ = $f$. Then, the $k$ components each already have $f$ vertices with them. Now , give away $1$ vertex each to first $f'$ components. This completes our vertex distribution. So, total edges$ = (f + 1 - 1)*f' + (f-1)*(f - f')$ (because we have minimum of $x-1$ edges for $x$ available vertices) where the first term counts minimum edges for first $f'$ components which have 1 vertex extra and the second term is for the remaining components.


Here is how you can implement indirect addressing without an atomic operation that does so.

We assume that we can label memory cells (either tape cells or registers, or whatever) in some way. This can be implemented by marked copies of the tape alphabet, or a special encoding of the content.

Idea: Addresses are offsets. If you want the $n$th cell, move a marker $n$ steps from the beginning. For that, you maintain a counter at a fixed location (determined by the programmer/compiler). After that, perform your operation on the first marked cell. Remove the marking when you are done.