Complexity of union-find with path-compression, without rank

Seidel and Sharir proved in 2005 [1] that using path compression with arbitrary linking roughly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$.

See [1], Section 3 (Arbitrary Linking):
Let $f(m,n)$ denote the runtime of union-find with $m$ operations and $n$ elements. They proved the following:

  Claim 3.1. For any integer $k>1$ we have $f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$.

According to [1], setting $k = \lceil m/n \rceil + 1$ gives
$$f(m, n)\leq (2m+n) \log_{\lceil m/n\rceil +1}n$$.

A similar bound was given using a more complex method by Tarjan and van Leeuwen in [2], Section 3:

  Lemma 7 of [2]. Suppose $m \geq n$. In any sequence of set operations implemented using any form of compaction and naive linking, the total number of nodes on find paths is at most $(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$ With halving and naive linking, the total number of nodes on find paths is at most $ (8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil $.

  Lemma 9 of [2]. Suppose $m < n$. In any sequence of set operations implemented using compression and naive linking, the total number of nodes on find paths is at most $ n + 2m \lceil \log n\rceil + m$.

[1]: R. Seidel and M. Sharir. Top-Down Analysis of Path Compression. Siam J. Computing, 2005, Vol. 34, No. 3, pp. 515-525.

[2]: R. Tarjan and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, Vol. 31, No. 2, April 1984, pp. 245-281.


Two labelled transition systems feeding each other

Transducers, or finite automata with output, are very powerful when they can be iterated. After all a step of a Turing machine on a tape (or better a instantaneous description, with the state assumed to be marked on the tape) is just a simple local rewrite, and iterating that is a computation.

With two transducers $T_M$ and $T_e$ we can mimick that iteration. Assume $T_e$ just echos what it reads. $T_M$ starts on empty input by writing the initial configuration and marker $\#w_0$, which it then gets as input via $T_e$. Then $T_M$ computes the next configuration of TM $M$ and writes $\#w_2$, etcetera. In that way $T_M$ writes a complete computation of $M$ in the form $\#w_1\#w_2\#w_3\dots$. If TM $M$ cleans its tape before halting, and if $T_M$ stops (and accepts) when it reads empty tape with halting state of $M$, the system has a halting computation iff the TM has one. Quite powerful.

In a simpler example $T$ gets a string $a^n\#$ as input. If $n$ is even it halves $n$ and outputs $a^{n/2}\#$, if $n$ is odd $T$ blocks (halts in a negative state, or runs off in a never halting sequence of epsilon moves), except when $n$ equals $1$, then it will accept and halt. Observe that when the output if $T$ is fed back as input, the system will only halt when the initial value of $n$ was a power of two.

In fact, what is obtained is a so-called fixed point language of the transducer $T$: strings $w$ such that $T$ writes $T$ on input $w$.
If I recall well, the fixed point languages of `rational functions' (finite state transducers that are not necessarily deterministic, but have only one output on a given string) are co-context-free, complements of context-free languages.
Prefix and equality languages of rational functions are co-context-free, Information Processing Letters, 1988,
doi:10.1016/0020-0190(88)90167-6,


What's the difference between a rule based system and an artificial neural network?

The difference is vast, although as Dave wrote, the resulting black box might look the same from outside. Rule-based systems are examples of "old style" AI, which uses rules prepared by humans. Neural networks are examples of "new style" AI, whose mechanism is "learned" by the computer using sophisticated algorithms, and as a result, we humans don't really understand why it works. While in some cases rule-based systems could be effective, the general trend in AI has been to switch to machine-learning algorithms such as neural networks, due to their much better performance.


A polynomial reduction from any NP-complete problem to bounded PCP

As is often the case with NP-reductions, it makes sense to look for similar problems. In particular, it is hard to encode global conditions such has "have seen some nodes" into PCP (with polynomially many tiles) which contraindicates graph problems, packing problems would require us to encode unary numbers in PCP (creating exponentially large instance), and so on. Therefore, a string problem with only local restrictions can be expected to work best.

Consider the decision version of the shortest common supersequence problem:

  Given two strings $a,b \in \Sigma^+$ with $|a|=n$ and $|b|=m$ and $k \in \mathbb{N}$, decide whether there is a string $c \in \Sigma^+$ with $|c| \leq k$ such that $a$ and $b$ are subsequences of $c$.

The idea is to let PCP build supersequences of $a$ and $b$ from left to right, encoding in the tiles' overlaps at which position we are in $a$ and $b$, respectively. It will use one tile per symbol in $c$, so $k$ corresponds to the BPCP's bound: if we can solve this PCP with $\leq k$ tiles, you can read off the common supersequence of equal length, and vice versa.

The construction of the tiles is a bit tedious, but quite clear. Note that we will not create tiles that do not forward $a$ or $b$; such can never be part of a shortest common supersequence, so they are superfluous. They can easily be added without breaking the properties of the reduction.

The numbers in the overlaps are encoded in binary, but using symbols outside of $\Sigma$ and padding them to a common length $\log \max(m,n)$. Thus we ensure that the tiles are used as the graphics suggest (tetris), that is characters and index-encoding overlaps do not mix (PCP does not prevent this per se). We need:

Starting tiles: $c$ can start with $a_1$, $b_1$ or both if they are equal.
Intermediate tiles: $c$ can proceed with the next symbol in $a$, in $b$ or both if they are equal.
Terminating tiles: $c$ ends with the last symbol of $a$ (if the last one of $b$ has been seen already), similar for $b$, or with the last symbol of both.

These are the tile schematics. Note that the intermediate tiles have to be instantiated for all pairs $(i,j) \in [n]\times [m]$. As mentioned above, create the tiles without $*$ only if the respective characters in $a$ and $b$ match.

[source]

The $*$ are symbolic for "don't care"; in the actual tiles, the other symbol will have to be copied there. Note that the number of tiles is in $\Theta(mn)$ and each tile has length $4\log \max(m,n) + 1$, so the constructed BPCP instance (over alphabet $\Sigma \cup \{0,1\}$ plus separation symbols) has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time. Therefore, the proposed reduction is indeed a valid polynomial transformation which reduces the NP-complete shortest common supersequence problem to BPCP.


Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same thing for $M'$).
Now consider $\overline{M'}$. Since we added a rejecting transition which is possible for every entry in $M'$, that means that there is an accepting transition for every entry in $\overline{M'}$, so it means that $L(\overline{M'}) = \Sigma^* \in P$.
That does not necessarily imply that $P = NP$, the reason being that $L(\overline{M'}) \neq \overline{L(M')}$.
Generaly speaking, $L \in NPC \Leftrightarrow \overline{L} \in \text{co-}NPC$, but that is not the case if you consider a Turing Machine and its switched version.


My solution uses 2 arrays (R and C) to store the zero-counts and a 1D array (Grid) to represent the grid of zeros and ones as a sequence of numbers. All 3 arrays are of size $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likewise for the i'th row). Here is a Python implementation and a test case (yours):

N = 3
R = []
C = []
Grid = []

for k in range(N):
    R.append(N)
    C.append(N)
    Grid.append(0)

def qr(k):
    print R[k - 1]

def qc(k):
    print C[k - 1]

def r(i, k):
    R[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[i - 1] & (1 << l) >> l)
        if bit != k:
            if k == 0:
                C[l] = C[l] + 1
            else:
                C[l] = C[l] - 1
        Grid[i - 1] = Grid[i - 1] | (k << l)

def c(i, k):
    C[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[l] & (1 << (i - 1))) >> (i - 1))
        if bit != k:
            if k == 0:
                R[l] = R[l] + 1
            else:
                R[l] = R[l] - 1
        Grid[l] = Grid[l] | (k << (i - 1))

qr(1)
c(1, 1)
qr(1)
qc(1)
r(1, 0)
qc(1)

You have to complete this with code that parses the input file and interprets the commands.


composite number Pumping Lemma for L = {$0^p$∣$p$ is a composite number}

The Pumping Lemma will give you a way to generate strings in the language whose lengths are in an arithmetic progression.  If you pick the initial string right, you should be able to apply Dirichlet's (?) Theorem that arithmetic progressions having certain properties necessarily include infinitely many primes.


How does sorting come into play with convex hull?

It is easier to catch the connection with sorting if you first sort the points by their polar angle. This is the basic idea for the Graham scan. Though, the idea with sorting points by the x-coordinates also works: you need then to apply just a slight modification of the same Graham's algorithm.


In CAD systems this is done

On user side

find intersection of two curves
split curves by their intersection
make closed path to form a polygon
fill polygon
you can still group separated line into one line and operate with it as previously, change in internal logic (math core side) will be hidden from you

On math core side

choose appropriate method of intersection of curves based on the type of the curves
do intersection either by exact intersection if lines types support this (eg straight lines) or by numerical method (usually iterative) in other cases (eg when you have splines underlying)
create new curves based on existent edges of lines and on the found intersection point
an so on


Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing?

All it's saying is that the messages between two processes need to be received in the order they are sent. If I'm going to send only differences between the previous message, we both better agree on what "the previous message" is.

For example, if I send "increment the first and second component" and then "increment the first and third component" but you receive them in the opposite order, you are likely to make form incorrect assumptions about how these messages relate to messages you're receiving from other processes. The correct intermediate state will have a vector clock that looks like $(1,1,0)$ but the one you'd reconstruct from the out of order messages is $(1,0,1)$. A message from another process with vector clock $(2,0,1)$ might then look like its strictly after the out-of-order message when, in fact, it is concurrent with it.


Non Turing-Recognizable from symmetric difference

(Converting the comment hints and guidance into an answer)

If you take $A$ to consist of all strings, $A=\Sigma^*$, then $A$ is decidable and recognizable.
Then, we will take the second language, $B$, to be recognizable but not decidable.

Their symmetric difference will give us (by definition) $\overline B \triangleq \Sigma^* \setminus B$.

Now, let's get concrete. The halting problem, $HP$, is a recognizable non-decidable language. If we take $A=\Sigma^*$ and $B=HP$, then their symmetric difference is $\overline {HP}$. The last step is to show that $\overline {HP}$ is not-recognizable (but this is a very well known fact that $\overline{HP}\in coRE$ and not-recognizable, since if it was recognizable, then $HP$ would have become decidable, since for any input we would have a machine that says "yes" if it is the language, and another machine that says "no" if it is not).


Edit Distance Algorithm (variant of longest common sub-sequence)

the additional cost of adding a swap function should be:

T(j-2,k-2) + Cs  , if A[j-1]=B[k],and A[j]=B[k-1]

I found the answer by studying the Damerau–Levenshtein distance modification of the classic edit distance problem.

Source: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance


Under which operations is the class of non-recursive languages a closure?

Non-recursive languages are closed under complement, but not under union or intersection.

Indeed, a decider for $A$ exists iff there is a decider for $A^c$. Hence the closure under complement.

However, let $B$ be any non-recursive language. $B^c$ is also non-recursive. But $B \cap B^c = \emptyset$ and $B \cup B^c = \Sigma^*$ are both recursive. Hence, non-recursive languages are not closed under union or intersection.

In the example you mention, you can not conclude anything about $L$ from $A,B$ being non recursive.

I will provide a hint for $L$, only. When you have a language of the form $L=\{f(x,y) | x,y\mbox{ s.t. } p(x,y)\}$, it is sometimes convenient to choose a particular value $a$ and study the related language $L_a = \{ y | y\mbox{ s.t. } p(a,y) \}$ first. Maybe one can choose $a$ to make $p(a,y)$ simple enough so that other proof techniques apply.


Finding the greatest $k$ numbers with a certainty of $p$

I propose the following algorithm. You take some random element $p$ of your input as pivot element for $k=n/10$. Next, you scan through all your data and split it  into a list of elements $\le p$ and a list with elements $>p$.

Case 1: The list with the larger elements contains more then $k$ elements. Then take this list and repeat.
Case 2: The list with the larger elements contains less than $k$ elements, say $m$. The repeat with the other list, but set $k=k-m$.
Case 3: Otherwise you are done.

This is very easy to implement and should find the solution quickly. (You said you want to do the math by yourself ;) )

Remark: There is a classic $O(n)$ algorithm for this. You can determine the $k$-th biggest element in $O(n)$ by the algorithm of Blum et al. and then use this element as pivot. However, I think the the constant in the $O(n)$ makes this variant slower then the above solution. Especially if you are fine with an imprecise solution.


Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?

Here is how to solve this for your particular $n$ and $k$. Your system has $k^n = 81$ possible states. You can describe the evolution of the system as a directed graph: there is an edge $s_1 \to s_2$ if state $s_1$ evolves in one step to state $s_2$. Some states are legal, some are illegal. You want to find an illegal state $s$ from which no legal state is reachable. This is a question that can be solved using a graph traversal algorithm such as DFS.

Once you find such a state, you can try to generalize the construction to other values of $n$ and $k$. Other simulations (with other values of $n$ and $k$) could be helpful here.


The $^*$ is an operator that takes a language (not only regular languages) $L$ and produces a new language $L^*$ called the Kleene closure of $L$. A language is a set of strings over a finite alphabet (alphabets are commonly denoted by $\Sigma$).

Definition of $L^*$

$$L^*=\bigcup_{i\in \mathbb{N}_0}L^i=L^0\cup L^1\cup L^2\dots$$

Where, $L^0=\{\epsilon\}$ and $L^n=LL^{n-1}$ for $n\gt0$

Example

Let $\Sigma=\{0,1\}$.

$\Sigma^0=\{\epsilon\}$

$\Sigma^1=\Sigma\Sigma^0=\{0,1\}$

$\Sigma^2=\Sigma\Sigma^1=\{00,01,10,11\}$

$\dots$

$\Sigma^*=\{\epsilon,0,1,00,01,10,11,\dots\}$

In other words, $\Sigma^*$ is the set of all finite-length binary strings.


Your problem is known as majority dynamics. It is known that under rather general conditions, the behavior converges to a fixed point or to a cycle of length 2. Presumably in your case the rules are such that cycles of length 2 cannot happen. Try adapting the proof method in Goles and Olivos.


Role of weak entities in avoiding inconsistencies

Definition and example of weak entity

The diagram shows a strong entity (Order, key Order number) linked to multiple weak entities (Order Line, key Order number+Order linenumnber). There's a foreign key from the weak entity to the strong (Order number).

So the Order number is duplicated in the sense a given Order number appears in many entities: one strong (Order number is the whole key); many weak (Order number is part of the key).


monotone min 3-sat polynomial algorithm?

The problem MIN-3SAT is usually know as "minimum vertex cover for 3-uniform hypergraphs". Any reasonable algorithm that you will suggest will give a 3-approximation (or worse), and indeed, it is conjectured (and follows from the unique games conjecture) that no polynomial time algorithm can improve on this approximation ratio.

This means that if you try hard enough, it is extremely likely that you will find an instance in which your greedy approach gives a solution which is roughly 3 times as worse as the optimal solution. I'll let you find it on your own.


You're right, there is a missing assumption that f(n) is at least O(n).
Indeed, the last line of the proof state that the operand are of size O(f(n)), while what has been proven before is O(f(n)+l(I)+l(B)). Since l(I) is O(n), the hypothesis is needed for this simplification.


If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?

There is a big difference between $\{ xy ∣ |x|  =  |y|, x = y \}$ and $\{ xy ∣ |x|  =  |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.

Checking that the first symbol is the same is not difficult. That can easily be achieved with a context-free grammar; we just need a word consisting of some symbol followed by a word with that same symbol in the centre:

$$\begin{align}S&\to a A\mid b B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b \\ \end{align}$$

That doesn't help us with checking that all symbols in the first half are the same as the corresponding symbols in the second half. But it does give us a way to check if some symbol in the first half is the same as the corresponding symbol in the second half:

$$\begin{align}S&\to A A\mid B B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\  \end{align}$$

And clearly it can easily be modified to check whether the corresponding symbols differ, giving the grammar in @Raphael's answer, linked in your question:

$$\begin{align}S&\to A B\mid B A\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\  \end{align}$$


Why is the Boolean hierarchy contained in the class $P^{NP}$?

Every language in the Boolean hierarchy can be written as a "Boolean formula" whose "variables" are languages in NP, e.g.
$$ \overline{(L_1 \cap L_2) \cup L_3}. $$
Given an oracle to NP (i.e., an oracle to some NP-complete problem) and an input $x$, we can decide in polytime whether $x \in L_1$, $x \in L_2$, $x \in L_3$. We need polytime since NP-completeness is defined with respect to polynomial time reductions. Given the values of the "variables", it is easy to compute the "formula".


Your statement is incorrect for two reasons.

First, there are in general several final states in the DFA corresponding to an NFA and not a single one. Next a set in the DFA is final if and only if it contains at least one final state of the DNA (and not all of them as you wrote). Furthermore, the initial state of the DFA is the set of all initial states of the DFA.

You can find the formal proof in any textbook on automata, but here is the intuition.

Let $\mathcal{A} = (Q, A, E, I, F)$ be a NFA. Let us call successful a path in $\mathcal{A}$ starting in $I$ and ending in $F$.
By definition, a word $u$ is accepted by $\mathcal{A}$ if and only if there exists a
successful path with label $u$.

Now, what happens when you use the subset construction to compute a DFA $\mathcal{B}$ equivalent to $\mathcal{A}$? You know that the states of $\mathcal{B}$ are subsets of $Q$. Furthermore, there is a path from $P$ to $R$ with label $u$ (where $P$ and $R$ are subsets of $Q$) if and only if
$$
\text{for each $r \in R$, there is a state $p \in P$ and a path in $\mathcal{A}$ from $p$ to $r$ with label $u$.}
$$
Thus intuitively, this path $P \xrightarrow{u}_{*} R$ in the DFA encodes all the possible paths in the DNA from a state of $P$ to a state of $R$.

Suppose now that $P = I$ and that $R$ contains a final state of $\mathcal{A}$, say $f$.
Then there is a state $p \in I$ and a path in $\mathcal{A}$ from $p$ to $f$ with label $u$. Thus this path is successful and $u$ is accepted by $\mathcal{A}$.

In the opposite direction, suppose that $u$ is accepted by $\mathcal{A}$. Then $u$ is the label of a successful path in $\mathcal{A}$, say from $p \in I$ to $f \in F$. Let $R = I \cdot u$ (in the DFA $\mathcal{B}$). Then $f \in R$ by construction and thus $R$ contains a final state.


Representing integers that are larger than the machine integer size by an array of digits is the standard way to do it, and it's usually called bignum, or more formally arbitrary-precision arithmetic.

Division on bignums is not simple. There's no shortcut: it isn't like with addition and subtraction where you can make a single loop that goes over both arrays. You can use the long division method you learned in primary school. There are more complex methods that have better performance in general; the Wikipedia article has a good overview.

There is no useful relationship between $n \bmod (a+b)$ and $n \bmod a$ and $n \bmod b$. I don't see where this would come up anyway. (On the other hand, $(a+b) \bmod p$ is either $(a \bmod p) + (b \bmod p)$ or $(a \bmod p) + (b \bmod p) - p$ depending on whether the sum overflows $p$).

When computing with numbers modulo $n$, always reduce modulo $n$ after each operation, to avoid having numbers grow too large. During one operation, it's usually useful to allow one more digit, to accumulate carries on partial results.

Note that primality testing is rarely done on large numbers, because it gets extremely slow. In cryptography, approximate algorithms are used, that have a small probability of accepting a composite number as prime (but if the algorithm says “prime”, then the number may not be prime, but it's “difficult” to factor).


Do these answers work even when we change the values?

The value of any $st$-flow is at most the value of any $st$-cut, and they are equal if and only if the flow value is maximized and the cut value is minimized. Thus, statement (A) is false since $f$ isn't necessarily a maximum flow (since you claim (A) is true, maybe you forgot to mention that $f$ is a maximum flow, or you meant to say that the value of the cut is at least 50?).
Statement (B) is true, since if there is a flow and cut of equal value, then the flow is a maximum flow and the residual graph has no path from $s$ to $t$.

Of course, the actual values don't matter. Only the relationship between the flow value and cut value is relevant.


Cliques in an alternate graph representation

You haven't specified exactly what your output is, but if it is the standard "output all maximal cliques", then the size of your output is exponential in the worst case, and therefore regardless of what algorithm you use, or what your representation* is, the algorithm may have to spend exponential time, just to output the answer.

*This is assuming the number of cliques you can represent in a single machine word is at most polynomial (which it clearly is, for any reasonable model).


What is the transitive and reflective closure of the derivation relationship?

If $R\subseteq A\times A$ is a binary relation, it can be imagined as a directed graph: the elements in $R$ are the edges. The graph however might be infinite. The elements in $R^*$ represent (finite) paths, following zero, one or more of the consecutive edges. Zero edges because of reflexivity, two or more because of transitivity.

In case of a grammatical derivations the relation $\Rightarrow$ considered is a binary relation in $\Sigma^*\times\Sigma^*$ for some alphabet $\Sigma$, defining a single step as defined by the grammar. Then  $\Rightarrow^*$ consists of all pairs of strings the first one of which can be rewritten into the second, using zero, one or more steps.

In other words, $x \Rightarrow^* y$ iff there exist steps $x= w_0 \Rightarrow w_1 \Rightarrow \dots \Rightarrow  w_n=y$.
Again, this includes the case of zero steps $x= w_0 = w_n=y$.

This notation can then be used to define the language of the grammar. Usually [but not always] this looks like $L(G) = \{ x\in\Delta^* \mid S \Rightarrow^* x \}$; the set consisting of all terminal words ($x\in\Delta^*$) that can be derived from the axiom ($S \Rightarrow^* x$).


Doubt in derivation of a proof in Information Theory

For fixed $p$, the central limit theorem shows that
$$
\begin{align*}
\lim_{n\to\infty} \Pr[\mathrm{Bin}(n,p) \leq np] &= \lim_{n\to\infty} \Pr[\tfrac{1}{n}\mathrm{Bin}(n,p) \leq p] \\ &=
\Pr[N(p,\tfrac{p(1-p)}{n}) \leq p] \\ &= \frac{1}{2}.
\end{align*}
$$
In this particular case you can get quantitative bounds in several ways, for example using the Berry–Esseen theorem or large deviation theorems such as the Chernoff bound.


Algorithm for determining if a statement is a paradox

So, there are a few problems with this.

First, what is your formal definition of a paradox? Is it just a statement that can be found to be both true and false in some system? Paradox tends to be a bit of an informal term, so in CS we usually just refer to this as a contradiction, or an unsound logical system.

For example, Russel's paradox isn't actually a paradox, it's a proof by contradiction. We assume a premise i.e. "any set characterized by a logical proposition exists.", and show that we can prove falsehood from it, thus concluding that the premise must be false. (In intuitionist logic, this is actually how falsehood is defined).
How are you encoding your logic statements? Traditional propositional logic doesn't give much in the way for describing self reference, so you probably need something higher order. Starting with natural language statements and converting them into logic is a whole separate problem.
Your problem seems undecidable, since you could use it to determine if one can prove false from an arbitrary proposition, which means you can use it to determine if an arbitrary statement is true, which means you can use it to determine if a Turing Machine halts on given input.


Understanding basic operation of TM and FA

Turing machines (and RAM machines) and (most) finite automata operate in two different input models. Finite automata usually accept their input in a streaming fashion: they read one input symbol, do something, read another input symbol, do something, and so on. When the input is exhausted, they report their output. Turing machines, in contrast, get all their input on the input tape, and then do whatever processing they wish. They don't have to stop after they have scanned the entire input.

This difference in the input model explains the different semantics you have indicated. There are, however, finite automata which have input semantics similar to a Turing machine, namely two-way finite automata. Although behaving superficially like Turing machines, they are equivalent in power to deterministic finite automata (DFAs).


Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?

Your model of what you do mentally is incorrect. In fact, you operate in two steps:

Eliminate all points that are too far, in $O(1)$ time.
Measure the $m$ points that are about as close, in $\Theta(m)$ time.

If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the target, but you may need to measure the closest contenders.

To illustrate this point, which green dot is closest to the red dot? (Only by a little over 1 pixel, but there is one that's closest.) To make things easier, the dots have even been color-coded by distance.

This picture contains $m=10$ points which are nearly on a circle, and $n \gg 10$ green points in total. Step 1 lets you eliminate all but about $m$ points, but step 2 requires checking each of the $m$ points. There is no a priori bound for $m$.

A physical observation lets you shrink the problem size from the whole set of $n$ points to a restricted candidate set of $m$ points. This step is not a computation step as commonly understood, because it is based on a continuous process. Continuous processes are not subject to the usual intuitions about computational complexity and in particular to asymptotic analysis.

Now, you may ask, why can't a continuous process completely solve the problem? How does it come to these $m$ points, why can't we refine the process to get $m=1$?

The answer is that I cheated a bit: I presented a set of points which is generated to consists of $m$ almost-closest points and $n-m$ points which are further. In general, determining which points lie within a precise boundary requires a precise observation which has to be performed point by point. A coarse process of elimination lets you exclude many obvious non-candidates, but merely deciding which candidates are left requires enumerating them.

You can model this system in a discrete, computational world. Assume that the points are represented in a data structure that sorts them into cells on a grid, i.e. the point $(x,y)$ is stored in a list for the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$. If you're looking for the points that are closest to $(x_0, y_0)$ and the cell that contains this point contains at most one other point, then it is sufficient to check the containing cell and the 8 neighboring cells. The total number of points in these 9 cells is $m$. This model respects some key properties of the human model:

$m$ is potentially unbounded — a degenerate worse case of e.g. points lying almost on a circle is always possible.
The practical efficiency depends on having selected a scale that matches the data (e.g. you'll save nothing if your dots are on a piece of paper and your cells are 1 km wide).


A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements

Following the conventions of Peczarski, Towards Optimal Sorting of 16 Elements, let us denote by $S(n)$ the optimal number of comparisons needed, and by $C(n)$ the information-theoretic lower bound $\lceil \log_2 n! \rceil$. It is known that $S(n) = C(n)$ for all $n \leq 11$, but $S(n) = C(n)+1$ for $12 \leq n \leq 15$. See Peczarski's paper for references. See also A036604.


Using AI / Machine learning to find the most time and space efficient solutions to an algorithm

No.

With all the hype about AI/Machine learning, sometimes people forget that there are known limitations to computers, which can be proven, so it doesn't matter how fast your computer is, how sophisticated is your neural net, you just cant do it.

I'll try to address your specific question. First, you have to define exactly what is the task that you expect your AI algorithm to solve. Suppose your input is a description of the problem, given in the form of an encoding of a Turing machine $\langle M\rangle$ which solves it, or as a valid code in your favorite programming language. Now, say we want to output an equivalent program, with optimal (asymptotic) time complexity.

The decision version corresponding to your problem is, given a program in your language, decide if there exists an equivalent program with better (asymptotic) time complexity.

This is not possible for any computer, or in more technical terms, this language is undecidable. We can reduce the halting problem to the above in the following way:

Given a pair $(\langle M \rangle,w)$, Let $M_w$ be the machine which, given input $x$, runs $M$ on $w$ for $|x|$ steps. If $M$ halted then $M_w$ accepts iff $x$ is a palindrome. If $M$ didn't halt within $|x|$ steps, $M_w$ rejects. We can build $M_w$ such that $M_w$ runs in $O(n^2)$ time.

If $M$ halts on $w$ after $n$ steps, then $L(M_w)=\left\{x \big| |x|\ge n \land \text{x is a palindrome}\right\}$, otherwise $L(M_w)=\emptyset$. Since we know that checking whether a string is a palindrome requires $\Omega(n^2)$ time on a single tape Turing machine, then if $M$ halts on $w$, $M_w$ decides $L(M_w)$ with optimal time complexity. Otherwise it doesn't (the empty language can be decided in constant time, just output "no" without even reading the input). This means that $M$ halts on $w$ iff $M_w$ has optimal time complexity.

This shows that for general programs, this task is hopeless. Perhaps, for a specific subset of programs, you can decide optimality, and this doesn't necessarily mean using some fancy AI algorithm,  see Program optimization.


How to show that a turtle graphic language is not regular?

The program $g^nr^9gr^9g^mr^9gr^9g$ crosses a line iff $n \geq m$.


How to Specify the Behavior of Automata for Verification

It feels to me like this has already been explained before (1, 2).  To prove that an automaton is correct, you first must define what correctness means to you.  Usually that is done by writing a specification of what it means to be correct.  Then, you prove that an automaton meets the specification.

If you're interested in knowing how to do that, that's a broad subject that people have written entire books about.  I suggest reading a textbook on model checking (particularly of finite-state systems).

How do you know what the specification should be?  Well, you have to figure out what correctness means, or the requirements are.  That's not really a question about computer science but rather a question about your application or your business domain and what problem you are trying to solve or what you're trying to do with the automaton.

If you're asking "what to verify", we can't answer that, because that's something you have to decide: you have to decide what properties you want to prove.  It's like asking 'how do I prove the natural numbers?'  You can't.  You have to decide what theorem you want to prove, before you can ask how to prove it.  If you ask a mathematician how to know what theorems to prove, the answer will probably be something like "well, you have to figure out what you want to know or what is interesting to know".


Konig's Theorem for Min Weight Vertex Cover?

So I found the answer.

The equivalence is that the min weight vertex cover of a bipartite graph can be computed as the maximum flow in a related bipartite graph. In the unweighted case, this maximum flow corresponds to the maximum carnality matching in a bipartite which is exactly the version of Konig's theorem that we all know and love.

For the sake of completeness here is the reduction of bipartite min weight vertex cover to max flow.

Let $G = (A,B)$ be the given bipartite graph. Construct a flow network $N$  by connecting the a source $S$ to all nodes in $A$ and all nodes in $B$ to a sink $T$.

Let the capacity of all original edges in $G$ be $\infty$. The capacity of all edges of the form $(S,a)$ where $a \in A$ will be $w_a$ and the similarly the capacity of all edges $(b, T)$ where $b \in B$ will be $w_b$. Every $S-T$ cut in this network corresponds to exactly one vertex cover and every vertex cover corresponds to an $S-T$ cut. Thus the min-cut a.k.a. the maximum flow will give us the minimum weight vertex cover.

For a more detailed proof refer this.


Büchi automaton with modified acceptance condition

Let $S$ and $F$ be the set of all states and all accepting states of $\mathcal{A}$, respectively. For $t \in S \setminus F$, let $\mathcal{A}$ be the automaton obtained by making $t$ the only accepting state. For $t \in S \setminus F$, let $\mathcal{B}_t$ be the automaton obtained by removing all states in $F$, and making $t$ the starting state. We think of $\mathcal{A}_t$ as an NFA, and of $\mathcal{B}_t$ as a Büchi automaton. The following language is $\omega$-regular:
$$ L = \overline{\sum_{t \in S \setminus F} L(\mathcal{A}_t) L(\mathcal{B}_t)}. $$
An $\omega$-word $w$ is not in $L$ if and only if on some run of $\mathcal{A}$, no accepting state appears infinitely often. Therefore an $\omega$-word $w$ is in $L$ if and only if on all runs of $\mathcal{A}$, some accepting state appears infinitely often.


Are there any more complex problems than the Totality Problem that appear in the practical world?

Let $\{W_e\}_{e\in\mathbb N}$ be a canonical list of the recursively enumerable, i.e., computably enumerable, i.e., Turing recognizable, languages (or sets).

The property that $W_e$ is actually recursive, i.e., computable, is $\Sigma^0_3$:
$$\exists d\forall n(n\in W_e\leftrightarrow n\not\in W_d).$$

It is at the 3rd level of the hierarchy: it is not of lower complexity than $\Sigma^0_3$. See e.g. Soare: Recursively enumerable sets and degrees, Theorem 3.4, for the proof.


Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$?

The property that, for all $x$, $x\in A$ iff $f(x)\in B$ means that $f(A)\subseteq B$ and $f(\overline{A})\subseteq \overline{B}$. Your proof attempt uses the condition $f(A)=B$, which is neither necessary nor sufficient.


Build all valid parenthesis in polynomial time

"We assume that there are no more than polynomially bounded amount of setting the parenthesis"

Your assumption is wrong.  There are exponentially many such expressions.  In particular, each such expression corresponds to a full binary tree with $n$ leaves (i.e., a binary tree where each non-leaf node has exactly 2 children).  There are exponentially many such trees.  Consequently, there are exponentially many such expressions.

It follows that you can't generate the list of all such expressions in polynomial time, since it takes exponential time even just to write down the answer (let alone to find it in the first place).


Restricting capabilities of admin role in database schema

Generally, you cannot prevent administrators from making any change they want to the database.  Many administrator actions require privileges that give them a lot of control over the database.  For instance, if they can restore from backups (something that administrators often need to do), they can overwrite everything in the database.

Designing systems that will remain secure even when the system administrator is not trusted is very challenging, and for a learning management system, is probably more expensive than is worth it.

Therefore, there's probably no point in trying to restrict admin.  Don't forbid what you can't prevent.


Data Searching from a large data set without reading each element

Say you have $n$ entries, $m$ distinct letters, and the $i$-th letter occurs $k_i$ times. You can find the last occurrence of the $i$-th letter using a variant of binary search: Double your step size until you find a different letter (or run out of the array), do binary search between your last and second-to-last step. This takes about $2\log k_i$ many steps. So in total you need about

$$\sum_{i=1}^m \log k_i = \log \prod_{i=1}^{m} k_i$$

many steps. That product is biggest when all terms are equal, so you have something like $m\log (n/m)$ many steps.

Naively implemented, this is not always better than looking at all elements though. If you work out all the details, you'll see that for example when $m=n$ you have to be a bit careful.


A question about decidable and undecidable problems

When the author talks about "number of programs", they mean numbers that represent programs. Normally, we think about programs of being strings of characters (e.g., Java programs) but we can also represent programs as numbers. The easiest way to see this is to think how they're represented inside your computer. That string of characters is just a big list of zeros and ones inside the computer, and a "big list of zeros and ones" is just a number written out in binary. Formally speaking, "programs" here are probably Turing machines but it won't hurt you to think of computer programs in whatever language you're familiar with.

The technique of using natural numbers to represent arbitrary objects like this is sometimes called "Gödel numbering", as it was first used by Kurt Gödel to prove things about logic. He encoded logical formulas as numbers, which allowed him to write formulas about formulas, in much the same way as a compiler is a computer program that operates on computer programs, and a universal Turing machine is a Turing machine that operates on Turing machines.

  "... [T]here are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." What are "they"? Is the writer talking about inputs/arbitrary whole numbers or certain sets of whole numbers?

That's not a very well-written sentence. The interpretation that makes most sense to me (the only one I can think of that makes the statement true) is, "There are certain sets of whole numbers for which no computer program can be written that decides whether its input is in that set."


How to expand 2D graphic and functions to 3D?

In most 3D graphics pipelines (e.g., OpenGL) points and direction vectors are represented with 4D homogeneous points (x, y, z, w) and their respective transformations are stored as 4x4 matrices. We can use the same representations for 2D and treat the z-value as the "stacking order" of our 2D shapes.

For example, for a 2D CW rotation about the origin we can use a 3D rotation about the z-axis:

       _                               _
      | cos(angle)  -sin(angle)  0   0  |
  M = | sin(angle)   cos(angle)  0   0  |
      |    0             0       1   0  |
      |    0             0       0   1  |
       -                               -

So to rotate a 2D point (x,y) about the origin we simply compute

  M * [x, y, 0, 1]^T

With 2D geometry we simply perform a orthographic projection into the rectangular region we wish to view. The pipeline is already designed to sort objects by their z-value for hidden-surface removal so defining a stacking order of 2D objects is trivial with the machinery in place.

Making the jump to 3D is a matter of generalizing the geometry and transformations with the added dimension. All of the usual affine transformations (rotation, scale, translation, shear, ...) generalize in a very simple way.

The biggest new concepts in 3D  is setting up a virtual camera (defined by a simple affine view matrix)  and you now have to project your 3D geometry down to 2D to create an image -- this can be done using parallel or perspective projections. Perspective projections require perspective foreshortening based on distance from the camera -- we can make very clever use of the homogeneous representation and a division by z to pull this off. This is standard material for most introductory graphics textbooks / courses.

Anyway, there's a start....


From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence,

$$
f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1
$$

Therefore, you can't find any constant $c$, such that $f(n) = O(n^c)$, as it is $\Theta(2^n)$.


Which class of neural network problem is this?

If I understand the question correctly,
you want to find the optimum of the function $F(G) := \min_{v\in V} f(G,v)$*, where $V$ is your vector space, over all valid graphs $G$. Additionally, you can compute $F(G)$ for any given graph.

First of all, I doubt only neural networks are going to be very helpful. The main strength of neural networks is to classify given training data. Judging from your question, I doubt training data is abundant.

The general problem of heuristically** optimizing an arbitrary function (here: $F$) over a discrete solution space (here: all valid graphs $G$) is usually solved by applying metaheuristics, such as local search methods (e.g. Hill climbing, simulated annealing, tabu search) or evolutionary algorithms.

These methods require you specify some structure of your solution space.

For local search, you need to define a neighbour relation between solutions to provide structure, such that

The neighbour relation is symmetric
Any two solutions are 'reachable' from another by
The difference in $F$ between neighbours is usually (hopefully?) low.

For this problem, we could consider two graphs neigbours if we can reach the other by removing or adding an edge. This is clearly symmetric and all solutions are reachable if we assume all graphs have the same vertices. Then, all that's left is to hope that the network performance $F(G)$ usually doesn't change much if we remove/swap two edges.

Most likely, this neighbour relation does not suffice, as this is very problem-specific. If you have such a neighbour relation, you can apply some local search method and get a hopefully good answer.

*: (You may want the maximum instead, but that doesn't really change anything, of course)

**: In other words, we 'attempt' to find a good answer without any optimality guarantees. Note that this is even 'weaker' than approximation. These methods are often justified, as many optimisation problems over discrete domains cannot even be approximated efficiently. I think this is acceptable, as neural networks usually cannot guarantee any optimality either.


Match dictionary to misspelled word, corner cases

Are we talking about a dictionary containing words of some language? Then there are many, many tricks you can use.

Your dictionary may contain 500,000 words, but people don't use that many. And they don't make arbitrary spelling mistakes, but typically only a small number. So you could have a second dictionary containing previous results. If I enter "wierd" you find "weird" after a lengthy search, but then you add "wierd" to a second dictionary.

You can look at the word and decide what is most likely the correct spelling. Like "messsage" is probably "message", without consulting your dictionary. You could map "messsege" to "m, vowel, s, vowel, g, optional vowel", and have a second dictionary for mapped words, which would tell you that your word is likely either "message" or "massage". This will work best for complicated words that nobody knows how to spell correctly.

If you know that your word was typed on a keyboard, there are errors that are more likely than others. If you know that your word was scanned by a scanner, there's a completely different set of errors, like "wam" might really be "warn" (nobody would make that mistake typing on their keyboard). For keyboard entry, the user's fingers might have moved to a different position on the keyboard. Like "leubpard" is "keyboard" with the right hand moved one position to the right. That's a case where simple algorithms fail completely.

Split your dictionary into the 5,000 most common and the 495,000 less common words. Most likely you find a good match within the first 5,000 and can remove most items in the large list that cannot be better.


Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

We can encode satisfiability of a SAT instance as the feasibility of a 0-1 integer linear program. For feasibility, the objective function doesn't matter, so you can impose whatever constraint you wish on it.

For an example of how to express boolean or, boolean and, and boolean negation in a 0-1 integer linear program, see Express boolean logic operations in zero-one integer linear programming (ILP).  This is all that's needed to express a SAT instance as a 0-1 integer linear program.


Edges in and out of cycles and their relation to connectivity of the graph

Yes.  Let $G$ be a graph, and suppose that the edge $ij\in E(G)$ is not on any cycle.  This implies that every path $P$ from $i$ to $j$ in $G$ uses the edge $ij$, since, otherwise, $P\cup \{ij\}$ is a cycle in $G$.  In particular, removing $ij$ from $G$ disconnects $i$ from $j$.

These kinds of edges are called bridges.


How would I design an NFA that recognises the language of all strings that don't end in a certain sequence?

Any DFA is also already a NFA, so you've already answered your question.


Is is possible to determine if a given number is xor combination of some numbers?

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.


Does a graph always have a minimum spanning tree that is binary?

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.

In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.


Is the union of 2 non context free languages always non context free?

As you suspected, the union of two non context-free languages may be context-free.

For example, $\{a^nb^nc^n\mid n\ge0\}\cup\{a^nb^nc^m \mid  m,n\ge 0,m\ne n\,\} = \{a^nb^nc^m\mid m,n\ge0\}$.

For a simpler example, $\{a^{n^2}\mid n\ge 0\}\cup\{a^{m}\mid m \text { is not a square}\} = \{a^{n}\mid n\ge 0\}$.

In fact, by a counting argument on countably infinity, for almost all languages $L$, both $L$ and its complement $\overline L=\Sigma^*\setminus L$ are non context-free (and even non context-sensitive), where $\Sigma$ is the (nonempty) alphabet. Their union, $\Sigma^*$ is context-free (and, actually, regular).

Your example is not correct since $L_3\setminus L_1 = \{a^nb^mc^k\mid n,m,k\ge0, n\ne m\}\cup \{a^nb^mc^k\mid n,m,k\ge0, m\ne k\}$ is a union of two context-free languages, hence also context-free.


Confused between the terms Process and Process Control Block

The point of swapping is to make room in RAM. What is moved to disk is what the book calls “process in memory”, not the process control block. The PCB block is a small amount of memory, so moving it to disk wouldn't help much. Additionally, some of the PCB is necessary even if the process is never scheduled, for example to know whether a file is open or not (which matters if the file is deleted or when taking a lock on the file), to know what events (such as I/O becoming available) might cause the process to become runnable (this information would be in the “process state”), and the knowledge of where the process data is in the swap space (that would be the process's “memory limits” while it's swapped out). In contrast, none of the process's own memory is necessary while the process is not scheduled.
Note that most operating systems don't swap out a whole process, but parts of its memory. Some books make a distinction between “swapping” a whole process and “paging” parts of memory, but in modern usage, the words “swapping” and “paging” are usually synonymous and refer to any mechanism that temporarily moves process memory to swap, whether it moves a whole process at a time (uncommon) or parts of process memory (common).


Algorithm to find a path connecting given nodes in a graph

Your problem is known as the Steiner tree problem. While this problem is NP-complete, it has efficient constant-factor approximation algorithms.


Is it NP-complete to test if a graph contains $t$ $k$-cliques?

This problem is clearly NP-hard since it is a generalization of many NP-hard problems. The most obvious one is the maximum clique problem, i.e. finding a clique of the maximum size in a graph. The decision version of this problem is a special case of your problem where you set $t$ equal to one. (See below for the hardness-proof).

Further reading.

Other example is the triangle packing problem, assuming you are looking for pairwise vertex-disjoint cliques (note that for the maximum clique it does not matter if the cliques have to be vertex disjoint since we chose $t=1$). In the triangle packing problem we are looking for a set of $k'$ vertex-disjoint triangles ($K_3$) in a graph, which is a special case of your problem where we set $k = 3$ and $t = k'$.

Note that the maximum clique problem is one of the Karp's 21 hard problem, which are probably some of the most important/original proven hard problems. In his paper "Reducibility Among Combinatorial Problems" [Karp, 1972], he provides some of the very first hardness reductions using Cook's theorem. Here is a link to the wiki page of the paper where you can find more information and a link to the original paper.


All of the keys you want to delete in this particular example belong to the case when we are deleting keys from a leaf node, without need to rebalance a tree after deletion.

Algorithm for deleting a key from a leaf node consists of three steps:

1) Search for the value to delete.

2) If the value is in a leaf node, simply delete it from the node, because there are no subtrees to worry about.

3) If underflow happens (i.e., if we break one of the defining rules/properties of a B-tree - every non-root node has to have at least (M-1)/2 keys), rebalance the tree.

Also, if you are interested in implementation of rebalancing algorithm, beyond the scope of the given example, I suggest these sources:

https://www.youtube.com/watch?v=vqIxJaNrPI4

https://webdocs.cs.ualberta.ca/~holte/T26/del-b-tree.html


Minimal spanning tree with degree constraint

As D.W. suggested, you can start as follows:

Temporarily delete vertex $1$.
For each of the resulting connected components $C_1, \dotsc, C_m$ find a MST, using e.g. Kruskal's or Prim's algorithm.
Re-add vertex $1$ and for each $C_i$ add the cheapest edge between $1$ and $C_i$.
If $m=k$, you are done.

If $m<k$, you can now do the following:

For each edge $\{1,v_j\}$ not yet added, determine the most expensive edge on the path from $1$ to $v_j$ in the current tree. Call this edge $e_j$ and compute $d_j = \operatorname{cost}(e_j) - \operatorname{cost}(\{1,v_j\})$, the cost savings of replacing $e_j$ by $\{1,v_j\}$ in the spanning tree.
Create a priority queue of the tuples $(v_j, e_j, d_j)$, ordered by decreasing value of $d_j$.
As long as $\operatorname{deg}(1) < k$ and the first value $d_j > 0$, consider the first tuple from the proority queue:

If $e_j$ has already been removed, find the edge $e_j$ and the value $d_j$ corresponding to the current tree. Update the tuple and its position in the priority queue.
Otherwise replace $e_j$ by $\{1,v_j\}$ in the spanning tree and remove the tuple from the queue.

Finding $e_j$ can be done in ${\cal O}(n)$, using e.g. a modified DFS. This makes the second phase ${\cal O}(n^2)$. Since Prim's algorithm is ${\cal O}(n^2)$ as well, this is also the running time for the complete algorithm.


Avoiding correlated values and reduced collision resistance in multiple hash states

MurmurHash2_x86_64 (aka MurmurHash64B) works as follows: it computes a 32-bit value $h_1$ based on bytes 0-3, 8-11, 16-19, 24-27, etc. of the input; it computes a 32-bit value $h_2$ based on bytes 4-7, 12-15, 20-23, etc. of the input; and then it mixes and combines these two values to obtain a 64-bit hashcode, computed as a function of $h_1,h_2$.  (Here by $h_1$ I mean the value of the variable h1 at line 180 in the source code you linked to.)

There is a sense in which this has only 32-bits of collision resistance.  In particular, if we consider two inputs that are the same in bytes 0-3, 8-11, 16-19, etc., and differ only in the other bytes, then there will be a $1/2^{32}$ chance that they collide.  Why?  Because there is a $1/2^{32}$ chance that they end up with the same $h_1$ value just by chance; and they will certainly end up with the same $h_2$ value (since it depends only on bytes that are the same for both outputs); so there is a $1/2^{32}$ chance they collide.  This is the same chance of collision as for a 32-bit hash.  For a 64-bit hash, you might expect a collision probability of $1/2^{64}$.

So this is a sense in which MurmurHash2_x86_64 is less than ideal, i.e., a sense in which one might say it has only 32 bits of collision resistance.  Whether it is relevant in your practical situation is unknown.

The latest version of MurmurHash is MurmurHash3.  MurmurHash3 supports a 128-bit output.  A reasonable approach would be to compute a 128-bit hash using MurmurHash3, then discard all but the first 64 bits.


Subset on boolean cube with largest sum of biases

It will be slightly cleaner to replace $\{0,1\}^n$ with $\{-1,1\}^n$, and to normalize your function $\tilde{p}_i$ so that we get the $i$'th Fourier coefficient
$$
\hat{p}(\{i\}) = \mathbb{E}[x_i p].
$$
Let $\sigma_1,\ldots,\sigma_n \in \{ \pm 1 \}$. Then
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n \sigma_i x_i\right)p\right].
$$
If we define a function
$$ q(x_1,\ldots,x_n) = p(\sigma_1 x_1, \ldots, \sigma_n x_n) $$
then $q \in [0,1]$ and
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n x_i\right) q\right].
$$
Under the constraint $q \in [0,1]$, the right-hand side is clearly maximized when
$$
q = \begin{cases} 1 & \text{if } \sum_i x_i > 0, \\
0 & \text{if } \sum_i x_i < 0, \\
\ast & \text{if } \sum_i x_i = 0, \end{cases}
$$
where $\ast$ means that the value doesn't matter. In other words, $q$ is the majority function, and so
$$
\begin{align}
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) &\leq 2^{-n} \sum_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &=
2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k-1} - 2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k} \\ &=
2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &=
2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
\end{align}
$$
Therefore
$$
\sum_{i=1}^n |\hat{p}(\{i\})| \leq \max_\sigma \sum_{i=1}^n \sigma_i \hat{p}(\{i\}) \leq 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
$$
Furthermore, this is achieved for the majority function.


You are probably looking for a barrier synchronization primitive.  Each thread calls into the barrier when it is done creating its set.  Only when all the threads have called into the barrier are any threads permitted to proceed.

If your programming language doesn't include a barrier primitive, then you can fake it, in your example, simply by having the main thread sit in a loop and join with all the children thread as the children finish and return from their computation.  The loop should only exit when it sees every child thread finish.


Divide and Conquer a problem into a sub-problem to solve it efficiently

The given information tells you absolutely nothing about the runtime of B.

As an example, let’s say the solution is a vector of N numbers which can be found in O(n^2 log n) but not in O(n^2), and let B be the problem “What was your input”. Solve the problem in O(n^2 log n), pass the solution to B, get it back in O(n), all consistent with the information you have.


Turing machine for $a^i b^j$ with $i \geq j$

I concur with the Patrick87's suggestion, so here's my version of it.

For the notation in the state diagram, I've used a slightly lazy version, to hopefully reduce some the normal clutter a little.

The start state is marked with the $>$ (left side, in the middle), and I've included an explicit accept state (marked with the usual double circle and "Acc"), and an explicit reject state (marked "Rej").
The transitions are labelled $\alpha \rightarrow \beta,X$, where $\alpha$ is the symbol read from the current tape cell, $\beta$ is the (optional) symbol to write to the tape, and $X \in \{L,R,S\}$ is the direction to move the tape head - note that I've included $S$ as a "stay put" option, because it's a pain in the [expletive] if you have to move the head each time, but it doesn't really change anything.
I've also added some blue, numbered arrows to assist in the explanation below.
$\sqcup$ is the blank symbol.

Now, behold in all its glory, a Turing Machine (diagram):

Now, a couple of notes by way of explanation. Of course this is essentially Patrick87's suggestion as mentioned, so if you already get that, you don't need to read further. These correspond to the blue numbers in the image:

At each iteration of the basic loop (and in particular at the start) if the tape is blank, we move to the accept state, this corresponds to $i=j$ with the trivial case of $i=j=0$ if the tape is blank to start with.
If we see a $b$, then there must be too few $a$s, not that this also takes care of the situation where the $a$s and $b$s are out of order. This transition may make more conceptual sense after going through the main loop once, but it still applies at the start.
We read an $a$, and replace it with a blank - now we are on the hunt for either a matching $b$, or, if we've already used up all the $b$s, a blank at the end of the string of $a$s.
We also have constraints on the format of the string - all the $a$s must come before the $b$s, so to ensure this, we explicitly move past all the $a$s.
Once we've done that, if we see a blank, then there aren't any more $b$s, so we can accept (this is the $i > j$ case).
If we do see a $b$, then we'll match it with the $a$ we matched at step 3, but we want to take the last one (otherwise we would need to shuffle the string around, or use extra symbols to denote deletions that aren't blanks or something).
Once we hit the end of the string, we move back one, and take off the last $b$ (note that we had to have seen at least one $b$ to get here, so there's definitely one to remove).
Now we've matched an $a$ and a $b$, we can return to the start of the unprocessed string - just keep going until we hit a blank. Then we're in the same situation as when we started, just with two less characters in the string.


I haven't read that book, so I may be off the mark.

Usually the transmission delay on a direct link is negligible compared with the processing delay at the endpoints and at each hop. In concrete scenarios, going via a geosynchronous satellite is the only way you have significant transmission delays on a link (about 0.2s to go up and down).

So when you have a network link that consists of a chain of direct links with a router at each hop, the total transmission delay is the sum of the store-and-forward delays on the routers. Strictly speaking, it's that plus the total length of the link divided by the speed of light (if the signal propagates at light speed), but that second part is usually negligible.


part of this question already has an answer in  multiple sequence alignment using HMM and simulated annealing
and about the number of states in HMM it is a challenge yet.


Do functional algorithms require more memory than imperative algorithms?

Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in words and behind the scenes set(words) is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses imperative features dressed up as functional programming. Have a look at Ocaml or Haskell.

As for your question, people have thought about just how efficiently one can implement functional programs on standard hardware (which I think is what you're asking). At LICS 2015 the following paper has been accepted:

  B. Accattoli, C. Sacerdoti Coen. On the Relative Usefulness of Fireballs. LICS 2015.

In it the authors show that a RAM machine (standard hardware) can simulate $\lambda$-calculus (functional programming) with a linear-time overhead with respect to the number of computation steps ($\beta$-reductions) of the functional program. This shows that functional programs can be efficiently implemented on existing hardware and will not in general consume a lot more resources.

Let me also point out that you cannot make the comparison you're trying to make in a sensible way. You are comparing two different algorithms that compute the same function. Instead, you should be comparing two implementations of the same algorithm in an imperative and a functional style. For instance sorting algorithms would do. And you should use a language that supports both imperative and functional programming. For instance, we could take merge sort and use the rosettacode.org functional implementation of merge srot in OCaml. Perhaps someone has the time to play with this and post some comparisons.


Is there any difference between extensible records and dependent maps

Simple records correspond to maps of dependent type (and we don't have a merge operation yet). More precisely, the record type

{ lbl1 : A1, lbl2 : A2, ..., lblN : AN }

corresponds to the product type

∏ (ℓ : label), A ℓ

where label is the sum type

lbl1 + lbl2 + ... + lblN

and A : label → Type is the type family defined by

A lbl1 ≡ A1
A lbl2 ≡ A2
       ⋮
A lblN ≡ AN

The record type above is also equivalent to the simple product

A1 × A2 × ⋯ × AN.

You asked about extensible records. There are at least two ways to do this. Without any additional technology we can model an extension of

{ foo : A, bar : B } ≤ { foo : A, bar : B, baz C }

with a couple of function that map between them (projection in one direction and extension by an extra field in the other). This is all very mundane.

We could also ask for the type of all possible record types. Suppose we have a type label of all possible labels (in practice it could be string or some such). The type of all record types is

record ≡ label → option Type

An element R : record is a mapping from labels to optional types, where
R lbl takes value None if label lbl does not appear in R and value Some A if it appears and have type A.

If R : record then the type decribed by R is the product type

∏ (ℓ : label),
  match R ℓ with
  | Some A ⇒ A
  | None ⇒ unit
  end

This means that a record r of type R is a dependent function which takes a label ℓ to an element of A if ℓ appears in R and to the unit otherwise.

However, a merge operation is problematic, as well as a subtyping relation R ≤ Q. This is so because we cannot express the fact that a label lbl has the same type in record R and record Q. At best you can say that the types are isomorphic, or propositionally equal, but that's not what you want.

We can define an extend operation

extend : record → record → record

in which the first argument overrides the second one so that extend R Q has the fields of R additionally those fields of Q that do not appear in R:

extend R Q ≡
   λ (ℓ : label),
     match Q ℓ with
     | Some A ⇒ Some A
     | None ⇒ Q ℓ
     end


Curry Howard correspondence to Predicate Logic?

To explain why I'm uncomfortable with Newsham's and (especially) Piponi's data wrappers ... (This is going to be more question than answer, but perhaps it'll work towards explaining what's wrong with my IsNat even though it seems very similar to Newsham.)
Piponi page 17 on has:
data Proposition = Proposition :-> Proposition
                  | Symbol String
                  | False deriving Eq

data Proof = MP Proof Proof
     | Axiom String Proposition deriving Eq

I see no types here. Spelling a data constructor :-> does not make it function arrow; and spelling a data constructor MP (for Modus Ponens) does not make it function application. There's a 'smart constructor' operator (@@) for MP, but that doesn't apply no function: it merely does pattern matching on the :-> constructor.
Newsham has (I'll start with the Implication section/Modus Ponens):
data Prop p = Prop p

data p :=> q = Imp (Prop p -> Prop q)

impInj :: (Prop p -> Prop q) -> Prop (p :=> q)
impInj p2q = Prop (Imp p2q)

impElim :: Prop p -> Prop (p :=> q) -> Prop q
impElim p (Prop (Imp p2q)) = p2q p

This looks more like it: we have types, function arrows, function application in impElim. The type constructor Imp with its injection and elimination rules mirror the proof tree structures in the Lectures on Curry-Howard isomorphism. But I'm nervous: why does Imp need a type constructor and data constructor? Again, spelling as :=> doesn't make that a function arrow. Why all this wrapping and unwrapping Prop constructors? Why not plain Prop (p -> q)?
So when I look at the 'Conjunction' section (which actually comes first):
data p :/\ q = And (Prop p) (Prop q)

andInj :: Prop p -> Prop q -> Prop (p :/\ q)
andInj p q = Prop (And p q)

andElimL :: Prop (p :/\ q) -> Prop p
andElimL (Prop (And p q)) = p

andElimR :: Prop (p :/\ q) -> Prop q
andElimR (Prop (And p q)) = q

Those Elim functions don't use function application. They merely pattern match on the constructors. There's no implicational structure for conjunction: we rely entirely that the 'programmer' has used only the andInj rule to build a type (p :/\ q).
So when Newsham gets to the commutativity of conjunction:
commuteAnd :: Prop (p :/\ q) -> Prop (q :/\ p)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

And claims

Notice that our Haskell proof did not contain any reference to the internal structure of the (:/\) data type. Having defined and proven our rules "andInj", "andElimR" and "andElimL" we shouldn't ever have to peek into the implementation of the (:/\) data type again.

I plain disagree:

The signature for commuteAnd does rely on the internal structure of the :/\ type constructor.
Although the function definition looks like merely function application, in fact the andElims do "peek" into the structure.

I'd expect we could prove the commutativity of conjunction from its definition, without needing an axiom to say so(?)
OK if I'm being so purist, what do I expect? This for conjunction is based on the Church encoding for pair:
type Conj p q r = Prop ((p -> q -> r) -> r)     -- not right, see later

andInj :: Prop p -> Prop q -> Conj p q r
andInj (Prop p) (Prop q) = Prop (\elim -> elim p q)

andElimL :: Conj p q p -> Prop p
andElimL (Prop conj) = Prop (conj axK)    -- axK is `const`

Now I can write commuteAnd using 'proper' function application:
--  commuteAnd :: (Conj p q r) -> (Conj q p r)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

That function definition is the same as Newsham's. But I've commented out the signature because GHC's inferred type is not general enough. It wants Prop ((p -> p -> p) -> p) -> ((p -> p -> p) -> p). Which is only a fancy variation on the Identity law.
Edit: (After @DerekElkins first comment here.) Scrap all this:

I've ended up in deep (and murky) water. I think my type for Conj needs to be more polymorphic, possiby Impredicative. I've mucked about trying to give a higher rank type:
type Conj p q = Prop (forall r.((p -> q -> r) -> r))

But GHC isn't playing. (And support for Impredicative polymorphism is "flaky".) And a forall-quantified thing like that looks suspiciously like the definition for False/uninhabited that I was expecting to use.

I do need a higher-rank type, but not Impredicative. And not on the type for Conj but for commuteAnd
commuteAnd :: (forall r. Conj p q r) -> (Conj q p r')
-- (same function for `commuteAnd` as above)

OK. I can happily swap arguments ad infinitum.
[End of Edit]
So my question: if it's legit what Newsham is doing with nesting constructors and pattern matching everywhere, then what's not legit about my IsNat and pattern matching?


Proving regularity via equivalence classes

If you are allowed to use closure properties (as the formulation in the question suggests) then $xw_1\in L_1$ so $w_1$ is a suffix of $L_1$, similarly $w_2$ is a prefix of $L_2$. Taking suffixes and prefixes is a closure property of regular languages, and so is concatenation. That solves the regularity.

At what level do you want/need equivalence classes for your answer?

(added) For language $K$ its set of prefixes is defined as
$$\mbox{pref}(K) = \{ w \mid \mbox{there exists string $y$ such that } wy\in K  \}$$
precisely as used for $L_2$ in the operation in the question.

Given a finite state automaton for $K$ we get a FSA for $\mbox{pref}(K)$ by making all states final that have a path leading to a final state.

Also $\mbox{suff}(K) = \{ w \mid \mbox{there exists string $x$ such that } xw\in K  \}$.
Similarly one proves closure under suffix by making all states initial. As that is not commonly allowed for FSA that is solved by adding $\varepsilon$-transitions to all other states.

Your language $L$ based on $L_1,L_2$ equals $\mbox{suff}(L_1)\mbox{pref}(L_2)$, the concatenation of a suffix and a prefix language.

I could not find a reference to a question in this forum that dealt with the prefix/suffix operations, perhaps someone can help. Closure under prefix is a special case of closure under quotient.


How to Generate Münchhausen Numbers in High Radices?

Meet-in-the-middle

One approach is to use a meet-in-the-middle algorithm.  This will reduce the running time from  $2b^b$ to something in the ballpark of $\sqrt{2b^b}$.

In particular, let your candidate number be
$$A = a_b b^b + \dots + a_1 b + a_0.$$
We'll write this in the form $A=A^* + A^\dagger$ where
$$\begin{align*}
A^* &= a_b b^b + \dots + a_{\lfloor b/2 \rfloor+1} b^{\lfloor b/2 \rfloor+1}\\
A^\dagger &=a_{\lfloor b/2 \rfloor} b^{\lfloor b/2 \rfloor} + \dots + a_0.
\end{align*}$$
Finally, let $s(a_i b^i + \dots + a_0) = a_i^{a_i} + \dots + a_0^{a_0}$.  We'll look for all solutions to the equation
$$A^* + A^\dagger = s(A^*) + s(A^\dagger).$$
This is equivalent to
$$A^* - s(A^*) = s(A^\dagger) - A^\dagger.$$
We'll compute a table of all possible values for $s(A^\dagger)-A^\dagger$, where $A^\dagger$ varies over all possibilities of the form above.  Then, we'll compute $A^*-s(A^*)$, for each $A^*$ of the form above, and look it up in the table to check for a match.  Each match yields a solution to the equation above, and thus a valid Münchhausen number.  This can be used to enumerate all Münchhausens.

For $b=10$, the running time becomes something like $10^5$ steps of computation, which should be no problem.  However, this is entirely infeasible for $b=35$.  The algorithm is still exponential-time.

Linear programming

Another possible idea is to use integer linear programming.

Let $x_{i,d}$ be a 0-or-1 variable, with the intended meaning that $x_{i,d}=1$ means that $a_i = d$.  Then we can obtain a bunch of linear inequalities that characterize a correct solution.  In particular, we have
$$\sum_{i,d} x_{i,d} d b^i = \sum_{i,d} x_{i,d} d^d.$$
We also have $\sum_d x_{i,d} = 1$ for each $i$.

Next, given a lower and upper bound $L,U$, we could use integer linear programming to search for a valid solution in the range $[L,U]$, by adding the inequality
$L \le \sum_{i,d} x_{i,d} d b^i \le U$ and looking for a valid solution.  To enumerate all solutions, start with a broad range $[0,2b^b]$, then when you find a valid solution, split the current range in two and recurse.  Then, use an off-the-shelf ILP solver to find solutions.

I don't expect this to be very effective, but you could augment it with additional inequalities that might help the ILP solver run faster.  In particular, for each prime number $p$ less than $2b^b$, we have
$$\sum_{i,d} x_{i,d} d b^i \equiv \sum_{i,d} x_{i,d} d^d \pmod p$$
This can be encoded via the linear equality
$$\sum_{i,d} x_{i,d} d b^i = \sum_{i,d} x_{i,d} x_{i,d} d^d + y_p p$$
where $y_p$ is an integer variable.  Note that $d b^i$ and $d^d$ are integer constants, so you can reduce them modulo $p$. Thus we get the linear equality
$$\sum_{i,d} \alpha_{i,d,p} x_{i,d} = \sum_{i,d} \beta_{d,p} x_{i,d} + y_p p$$
where $\alpha_{i,d,p} = d b^i \bmod p$ and $\beta_{d,p} = d^d \bmod p$ are constants you can precompute.  You can do the same if $p$ is a power of a prime.

So, you might add linear inequalities of this form for several well-chosen prime powers (say, all of the prime powers below some bound; or all small prime numbers, plus the prime power factors of $b$, $b-1$, $b+1$, $b^2$, $b^2-1$, $b^2+1$).  One could hope that these help the linear solver find solutions faster.

I don't know whether this will be effective, but it is something you could try.  It would not be too hard to implement and see how well it works.


How to reduce language is finite to language is regular?

First note, that for a regular language, however encoded, it is decidable wether it is finite or not. So you can use the language $REGU$ as an oracle for $FIN$ in the following way: To check if $\langle M \rangle \in FIN$ you ask the oracle $\langle M \rangle \in REGU$? If the answer is no, you can be sure that $\langle M \rangle \notin FIN$ as every non-regular language is infinite. If the answer is yes there is a proof (e.g. an NFA $\mathcal{A}$) that shows that $M$'s language is regular. Then you run your procedure to check whether $\mathcal{A}$ is finite (this is, as mentioned above decidable).


How is the run time calculated in this insertion sort algorithm?

Let me answer step by step:

$c_1, c_2, c_4$ etc. are costs of the operation in the corresponding line. For example $c_1$ is the cost of for: one pass of this line costs $c_1$.
$key=A[j]$ happens $n-1$ times, because we start from $2$ and $n=A.\text{length}$.
As it is commented, its cost is $0$.


Rules regarding Chomsky Normal Form (CNF) grammars

The production

$$S_0 \to S$$

is not in CNF. CNF requires that nonterminals produce either two nonterminals or one terminal. Since the above line shows a nonterminal producing a single nonterminal, it does not fit. The CFG in CNF would be just:

$$S_0 \to XX$$
$$S_0 \to XZ$$
$$\vdots$$

To answer your original questions, though, yes, you can do the above in CNF. There are no stipulations about how many times a nonterminal may appear on the left or whether it can be duplicated on the right.


Is what the all-zeroes instruction does considered in machine instruction design?

In general ease of decoding and code density seem to be given more emphasis when designing an instruction encoding than catching the accidental execution of data (though the danger of nop slides is well known).

Catching the all-zeroes case is rather inexpensive and a number of ISAs specify that such will always be an illegal instruction; e.g., RISC-V (The RISC-V Instruction Set Manual, Volume I: User-Level ISA, Version 2.1: "We reserve all-zero instructions to be illegal instructions to help trap attempts to execute zero-ed or non-existent portions of the memory space. The all-zero value should not be redefined in any non-standard extension. Similarly, we reserve instructions with all bits set to 1 (corresponding to very long instructions in the RISC-V variable-length encoding scheme) as illegal to capture another common value seen in non-existent memory regions.") and Power (Power ISA, Version 2.07: "An instruction consisting entirely of binary 0s is guaranteed always to be an illegal instruction. This increases the probability that an attempt to execute data or uninitialized storage will result in the invocation of the system illegal instruction error handler.")

One might expect memory access protection mechanisms to prevent accidental execution of data, but special casing the all-zero instruction is an inexpensive means of providing a slightly deeper defense. (In addition, some embedded processors do not provide any memory protection.)

Mitch Alsup (a semi-retired computer architect) has designed a RISC-inspired ISA that has a somewhat broad range of illegal instructions meant to catch executing data. From a comp.arch post: "And in particular, opcodes near integer zero are decoded as unimplemented, and Opcodes near FP one (~10**-5 to ~10**5) are also decoded as unimplemented; in both positive and negative senses." "Thus jumping into data is highly likely to result in attempting to execute an unimplemented instruction."


In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?

The answer is yes. But the departure point is slightly different.
Here it is:

\begin{array}{|c|c|c|}
\hline
\neg A \vee B, \neg B \vee C \models \neg A \vee C &
A \implies B, B \implies C \models A \implies C \\
\hline
\end{array}

The former statement is just the fact that if you start with $A\vee B$
and turn it into an implication you find $\neg A\implies B$.


Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

For the sake of avoiding dealing with rounding in the analysis, assume for simplicity that $k$ is a power of $2$ (if it is not, you can add $d \le k-1$ dummy arrays with one $+\infty$ element each, and ignore the last $d$ elements in the final sorted vector).

You can merge your arrays two by two in a binary-tree fashion: the algorithm works in $\log k$ phases. In phase $i=0, \dots , \log k - 1$ there are $k/2^i$ sorted arrays, where the arrays of phase $0$ are the $k$ input arrays. These arrays are arbitrarily grouped into $k/2^{i+1}$ pairs and each pair is merged. The resulting arrays are moved to the next phase.
At the end of the $(\log k - 1)$-th phase there is only one sorted array $A$ remaining. Return $A$.

The total amount of work on each phase (a level of the tree) is $O(n)$, and the number of phases (i.e., levels) is $O(\log k)$.


Finding the most frequent element assuming $\Theta(n)$ frequency

Here is an algorithm for all $0<\alpha\leq 1$. I'm assuming your data can be ordered and that comparing two elements is done in constant time.
Run a few levels of the quick-sort recursion (choosing the pivot optimally in linear time with the Median of Medians algorithm) until you have partitioned the elements into "buckets" $B_1,\ldots, B_m$ each of size $\frac{\alpha n}{4} \leq |B_i| \leq \frac{\alpha n}{2}$, where all elements in $B_i$ are smaller or equal to all elements in $B_{i+1}$.
This will take $O(n\log(1/\alpha))$ time.
Now notice that because the relative majority element $e$ is present at least $\alpha n$ times and each bucket has at most $\frac{\alpha n}{2}$ elements, the majority element needs to fill at least one of the buckets completely. Thus $e$ is also  the first element in some bucket.
Notice also that there are at most $4/\alpha$ buckets as each bucket contains at least $\frac{\alpha n}{4}$ elements. Thus you can pick the first element in each bucket, and choose the element with maximum frequency among those in $O(n/\alpha)$ time.
Thus, you can find that relative majority element $e$ in $O(n\log(1/\alpha) + n/\alpha) = O(n/\alpha)$ time.


Finding two languages satisfying conditions

A slight improvement:

$L_2 = E_{TM} \backslash L_1 $ (since we require that $L_1 \cap L_2 = \emptyset$).

$L_1$ must be a language of turing machines, i.e. $L_1 = \{\langle M\rangle \mid \dots\} $, so that $L_1 \cup L_2 = E_{TM}$.

So let's set $L_1 =$ $\{\langle M\rangle\mid  C_0\text{ is a reject state}\}$.

The following holds:

$L_1 $ is infinite and decidable (easy to decide given $M$, what the configuration of the first state is).
$L_2 $ is infinite and unrecognizable.


One way to grasp it would be with concrete examples.

So an expression like:

"is a man" OR "is a man with a sister" (i.e. A = is a man and B = has a sister)

In this expression, if you're a man, it doesn't really matter whether you have a sister or not, you are to be counted.

or perhaps closer to a program, in an answer to "which words should we select?":

"words that start with W" OR "words that start with W and end with S"

You can see that the second condition identifies at most a subset of the first and is therefore redundant (and can safely be lopped off).

In code, you would simplify an expression like:

if s.startswith("W") or (s.startswith("W") and s.endswith("S"))

to

if s.startswith("W")

This might be why it's handy to know as a computer scientist. Conditional expressions have a tendency to become complex (and therefore difficult to reason about). Being able to simplify them safely is often a good refactoring move.

Another way to grasp it would be visually, with a Venn diagram with A and B overlapping circles. In that case, A AND B would be their intersection (the overlapping part) and the expression A OR (A AND B) would mean all points inside A or inside the intersection. Since the intersection is by definition all within A, specifying the (A AND B) intersection as an alternative is redundant.


"Scripting" languages are typically interpreted, not compiled.  That means that there will be a program called the "interpreter" for that language, which reads the programs written in the language, and executes them. You can start reading about interpreters from the Wikepedia entry:

http://en.wikipedia.org/wiki/Interpreter_(computing)

A compiler, on the other hand, translates a program in the programming language into machine language, and lets the CPU execute the machine language program.  The only reason for compiling instead of interpreting is for speed.  The CPU can typically execute the translated machine language program about 10-100 times faster than any interpreter.  The reason is that the CPU is implemented in hardware.  Otherwise, there is nothing that a CPU can do that a program can't.

Interpreted programs runs slow as compared to compiled ones due to the difference in execution process.

Scripting languages are usually used for expressing high-level operations.  For such things, the speed advantage of the CPU becomes much less significant.  So, interpreting them can be competitive to compiling them.


(Your question seems to be about concepts and terminology. The meaning of termini depends on context - the quote is from a compiler writers' book. Not only are the authors entitled to a "compiler centric" view of things: that perspective is to be expected.)

There are at least two "CS" interpretations to runtime environment.
 One is the process/OS level - some lump of hardware turned into a MINIX machine, an OS/400, QNX, z/OS, Multics one, defined in an applicable application binary interface (ABI).
At this level, memory usually gets allocated in segments or pages (taking care no information leaks). (In a conventional OS,) Requirements like amount and initialisation are taken from an "executable file" in an appropriate format.
It is a matter of definition whether "the compiler" is responsible for the generation of such a file from source code or just some intermediate code which may be executed by an interpreter, or statically analysed&improved, turned into assembly language, assembled into an object file/module, linked with other modules.

To me, the existence of a virtual machine is a philosophical question (as opposed to the existence of the computing hardware heating up my environment) - I take the pragmatic stance of accepting help, from a mere concept when that is what it is. Proponents of something like the Java virtual machine (JVM) (a popular target for compilers, btw.) are entitled to making the case for VM existence.

Regarding exactly when the compiler does something, anything going on during execution of the compiler should be beyond doubt. A compiler-centric view may include anything from decisions made during the specification of the compiler (like row-major or column-major layout of two-dimensional arrays) up to and during the execution of the compiled program - anything not due explicitly to a specific part of the source code, but the language specification implemented by the compiler.

 This is the programming language level - what gets your main() running (and possibly constructors&co. of statically allocated objects before that), that Begin…End;-block implicitly prefixed with Simula - you name it. It takes care of memory(/address) allocation (and possibly initialisation) for a subroutine call stack (per coroutine/thread), "statically allocated" program data (those objects named in the source program - on behalf of the program source code/the coder/the one who started the program), "automatically allocated" space (e.g., for "local" variables in potentially recursive subroutine calls), "dynamically allocated" space (e.g. objects for linked data structures. "dynamically": as need arises during program execution, a "program request" for (memory for) another object may lead to the language runtime environment requesting more memory from the OS - often, the RTE manages a memory pool for smallish requests and makes largish ones to the OS).
"The compiler" decides about memory layout for multi-dimensional arrays.
It arranges access to machine code for the "runtime library" - with OS support more often than not.
In all, a Forth machine, a Java, Fortran, Beta one.

Note that

the paragraph quoted does not say the compiler [executes] the code
creates and manages needs interpretation/leaves room for it
one resource managed by one authority doesn't preclude the same resource being managed by another one - expect conflicting responsibilities handled usefully.


What is the best complexity of finding a minimum in a matrix?

You can't find the minimum without reading all values, due to an adversary argument. The adversary pretends that the matrix is the zero matrix, that is, whenever you ask for some value in the matrix, it answers zero. If you haven't queried some entry, then the algorithm cannot distinguish between two possibilities: that the matrix is entirely zero, or that it is zero apart from the entry, which has value –1. The minimum in both cases is different, so the algorithm can't be correct.


Definition of efficiency versus complexity of algorithm

An algorithm is often called "efficient" if its runtime is short, compared to the inherent difficulty of the problem.

For example, you cannot sort arbitrary arrays by comparing keys in less than O (n log n). Once sorted you can lookup values in O (log n). Looking up a value in the sorted array by doing a linear search has lower complexity then sorting the array, but it is inefficient because linear search takes time O (n) and could be done in O (n log n).


Finding a value in a sorted array in log R time, R is the number of distinct elements

There is no such algorithm.  Here's an information-theoretic proof that it can't be done, inspired by gnasher79's answer.

Let's focus on the special case where $R=3$.  Suppose there is a constant $c$ and an algorithm that examines at most $c$ elements of the array, regardless of $n$.  Then this algorithm can't possibly solve your problem.

In particular, consider all arrays of the form $[0,\dots,0,1,2,\dots,2]$, i.e., containing some number of 0's, followed by a single 1, followed by 2's.  Let's imagine what the algorithm does when you ask it to find a $1$.  There are $n-1$ different possible positions for the $1$.  However, after doing $c$ probes, the algorithm learns only $c \lg 3$ bits of information about the position of the $1$.  Thus, if $n-1 > 2^{c \lg 3}$, the algorithm can't possibly work correctly for all such arrays: there exists some pair of arrays where the algorithm outputs the same thing in both cases, but the correct answers differs, so the algorithm must be wrong for at least one of those two cases.  In other words, if we take $n$ to be sufficiently large (namely, $n> 3^c + 1$), the algorithm will be incorrect.

This implies there is no algorithm for the case $R=3$ whose running time is upper-bounded by a constant.

It follows that there is no algorithm whose running time is $O(\lg R)$ (and whose running time doesn't depend on $n$): if there was, plugging in $R=3$ would give us a $O(1)$-time algorithm for the special case where $R=3$... but I just proved that no such algorithm can exist.

However, the special case $R=2$ can be solved in $O(1)$ time: simply look at the first and last element of the array, and pick whichever one matches the value you're looking for.


What are the effects of the alphabet size on construct algorithms for suffix trees?

A larger alphabet is usually a drawback. However there are algorithms that can deal with this as long as the alphabet size is $n^{O(1)}$.

Ukkonen's algorithm runs only in $O(n)$ if the alphabet size is a constant but it is $O(n \log n)$ without this assumption. However, there are alternatives. You can compute the suffix-array of a text in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can get the suffix tree out of the suffix array in $O(n)$ time, when you have the LCP-array. Basically, you compute the Cartesian tree of the LCP-array and use the suffix-array to label the nodes. The LCP-array can be also computed with the DC3-algorithm.


Both algorithms are DIT, but the main difference is in memory access patern.
Cooley-Tukey - the most popular form of transformation from DFT to FFT comes from cache awareness, which is optimal for CPU pipeline.
Cooley-Tukey in first phase reverses bit order while Stockham changes order at each stage.
This is observable if you take look at edges - once you have half of the data it stays in place for Cooley-Tukey but moves for Stockham.

For CPU Stockham makes cache mispredictions while Cooley-Tukey makes thread serialization for GPU.

FFT - look at BFS vs DFS strategy.

FFT stage decomposition - very nice pdf showing butterfly explicitly for different FFT implementations.


The remark is about one specific usage of Coq, namely formalization of programming language theory.

Let us first make clear the distinction between synthetic and analytic:

In a synthetic approach to a subject we say that there are things whose basic properties and structure are postulated in one way or another. We then study these things by relying only on the postulated properties and structure.
In an analytic approach to a subject we discover that there are certain things. To learn more about them, we take them apart, we study how they are made and we analze them. This way we discover their properties and structure.

How would one study a programming language in these two ways?

Synthetically, we would postulate the constituent parts of the language (there are terms, there are types), their basic structure (these are the ways of building terms) and basic properties. We do not ask what the terms and type are made of, or whether the terms are trees or strings, or whether the collection of types is built in a particular way.

Analytically, we would start with a mathematical setup that allows us to do many things, such as use inductive definitions to construct mathematical objects. We woudl build terms and types as particular inductively defined sets or types. Then we would study their structure, how we can transform them, etc.

It should be clear that Coq is of the analytic kind. When you implement a programming language in Coq, you define inductive types of terms and types. Then you analyze them using induction, define operational semantics as a recursive function on the syntax of terms, etc.

On the other hand, Twelf is of the synthetic kind. We postulate that there is a type of terms and a type of types, but we do not tell Twelf that these are inductive types (there's no way to say that in Twelf). We define operational semantics by providing basic transition rules. There is no mention of recursively defined functions (there's no way to define functions in Twelf), we just rely on the postulates that we wrote down.

You should compare the above situation to planar geometry. Hilbert's approach to geometry is synthetic (but his ideas are rooted in Euclid), Descartes' are analytic. The analytic geometry is so called because a line is not a primitive concepts: it has an inner structure, namely it is a set of points.


Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths

This is a classic problem known as "reachability querying". There are various algorithms possible, with different complexities.
Unless you are working with some huge graphs and can not afford to store the index, the simplest is storing the $O(|V|^2)$ transitive closure of your graph. This can be computed quite simply with Floyd-Warshall in $O(|V|^3)$, and with a lot more effort in $O(|V||E|)$ using the methods found in Nuutila's thesis.
Now if your graphs are truly large and you can not afford to spend $O(|V|^2)$ memory you enter an academic world of dozens upon dozens of papers, each with slightly varying performance characteristics (very often incomparable, yet almost always claiming to beat the competition), and varying difficulty of implementation. I guarantee you that almost all of them will be hard to implement however.
Allow me to reproduce Table 1 from Reachability querying: an independent permutation labeling approach, a recent paper by Hao Wei et. al. Here we have as main parameters $n = |V|$, $m = |E|$, $k$ is the width of the graph, $t$ is the number of non-tree edges of the graph after a spanning tree is formed.


Chandy/Misra dining philosophers solution

Yes. Whenever a philosopher asks for a fork that is dirty, the philosopher who currently has that fork cleans it and gives it to the person who asked for it.

So, in the initial position, 1 has two dirty forks and can eat, 2, 3 and 4 have one dirty fork each and 5 has no forks at all. If 3 requests a fork from 4, 4 cleans it and gives it to him. This leads to the state where 1 has two dirty forks and can eat, 2 has one dirty fork, 3 has one clean fork and one dirty fork and can eat, and 4 and 5 have no fork.