How to write operational semantics rule for havoc x?

I'm going to assume that all the allowed values for $x$ are (unbounded) integers.

In that case your proposal somewhat makes sense, insomuch as $e$ is some arbitrary well-formed expression (which evaluates to some value in the context $\sigma$). But it's just as easy to write this

$$\frac{n\in\mathbb{Z}}{(\mathrm{havoc}\ x,\sigma)\rightarrow (x:=n,\sigma)} $$

You see that in both cases the result of the evaluation by this rule can non-deterministically give any value in $\mathbb{Z}$ to $x$. In this sense, you have a family of rules, one for each $n\in\mathbb{Z}$.


How Does Populating Pastry's Routing Table Work?

The idea of a routing table in Pastry (and all structured P2P networks) is to minimize its size, while guaranteeing a quicker routing.

The routing algorithm of Pastry goes as follows:

Step A. A node u searches for an object A by firstly looking it up in its leaf set.
Step B. If it was not available, then the query is forwarded to a known node that shares "a number of prefixes with $A$ that is at least larger than what node u shares with A".
Step C. If such a record is not found, then the query is forwarded to a node in the leaf set that is numerically closest to $A$.

This is why a node $u$ stores addresses of nodes organizes its table as follows:

1.Each record in row $i$ of the routing table of node $u$ is a node identifier that shares $i$ prefix bits with the identifier of $u$.

2.The $(i + 1)^{th}$ bit of the records of a row $i$ is unique and is taken from the set $\{0, …, 2^{b} – 1\}$.

Example in  a typical scenario:
if u address is 1111 and object $A$ has identifier 4324: then here is what will happen: (we assume that it is of the base of 4. (i.e. addresses are from [1-4][1-4][1-4][1-4]).

Node $u$ shares 0 prefix with object $A$. Therefore, it looks in row 0.
According to rule 2 above, node $u$ stores addresses of nodes 1XXX, 2XXX, 3XXX, 4XXX, where X is a "dont-care" value. The closest among these nodes to $A$ is 4XXX. - Let's say this 4XXX is actually 4013. Then $u$ forwards to $u _1$ with address 4013. Now you are going to repeat the same thing again at node $u _1$ with address 4013.

To make it simpler, here is again an example of how it will go in 4013. $u _1$ will first look for the size common prefix between 4013 and 4324 which is 1. So it goes to row 1, which contain values such that 41XX, 42XX, 43XX, 44XX. The closes among them to $A$ is 43XX. - if this was 4331 then it will be forwards toward it.

The maximum number of hops here in is 4 hops (XXXX) ! in Pastry terms, it is $log_{2^b}$. So it is reduced as $b$ increases. But the size of the rows which are $2^b$ will increases ! -- so the authors said that $b$ = 4 is a good balance !

Practical scenarios are usually not typical as that. There may be situations in which there are not many nodes in the network. this is why we follow step C above. - However, what you need to guarantee to make this algorithm correct is that each node be connected to the closest two nodes to it (in term of identifiers). This will form a ring of ordered nodes [e.g. 1->3->4->9->10->11->1]


Here, M2 hasn't been designed to accept Regular Languages. It has been designed to be used as argument of R. As per assumption that R can decide REGULARTM, R is free to reject M2 if the case arises. Remember, decidability includes both acceptance and rejection.

Update:
As per definition, R will accept only if argument TM accepts regular language. And, it will reject if argument TM accepts non-regular language. The setup of M2 harnesses this rejection property of R. If R hasn't rejected (as it can decide, it'll accept), it means point 2 of M2 was in action (which makes M accept w creating contradiction).


Polynomial-Time reduction from Partition to MakeSpan

Given an instance of partition (i.e., a set of numbers) $\{a_1, \dots, a_n\}$ create an instance of Job Scheduling (what you call Makespan) with $2$ machines and $n$ jobs $j_1, \dots, j_n$, where the execution time of the $i$-th job is $a_i$.
Pick $b = \frac{1}{2} \sum_{i=1}^n a_i$.

If there is a solution to the partition problem, i.e., a set $A \subseteq \{a_1, \dots, a_n\}$ such that $\sum_{a \in A} a = \frac{1}{2} \sum_{i=1}^n a_i$, then there is a solution for the job scheduling problem: simply assign $j_i$ to machine $1$ if $a_i \in A$, and to machine 2 otherwise.

If there is a solution to the job scheduling problem, i.e., a partition of jobs into $M_1$ and $M_2$ such that $\max\{ \sum_{j_i \in M_1} a_i, \sum_{j_i \in M_2} a_i \} \le b$ then there is a solution $A$ to the partition problem.
The choice of $b$ implies $\sum_{j_i \in M_1} a_i = b = \frac{1}{2} \sum_{i=1}^n a_i$, therefore it suffices to select $A = \{a_i \, : \; j_i \in M_1 \}$.


Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?

Consider a Turing machine which reads its input and then immediately stops. This Turing machine always halts on every input, but the running time is unbounded: the machine runs for $n$ steps on an input of length $n$.
In fact, most halting Turing machines have unbounded running time: if the running time of a Turing machine is bounded by $T$, then the language it decides can only depend on the first $T$ symbols of the input.
If a Turing machine always halts on any input, then there is a function $f(n)$ such that the Turing machine always halts within $f(n)$ steps on an input of length $n$. You can take as $f(n)$ the maximal time it takes the Turing machine to halt on an input of length $n$. Since there are only finitely many words of length $n$ (recall that the input alphabet is fixed), this is well-defined.
Furthermore, if a Turing machine always halts on any input, the function $f(n)$ defined in the preceding paragraph is always computable. You can compute it by simulating the machine on all possible inputs of length $n$.
Space works exactly the same way.


In a Binary Search Tree what is the base of the log in this Big O notation

It doesn't matter what the base of the logarithm is.  $\log_a x = (\log_bx)/\log_b a$ so changing from one (constant) base to another just introduces a constant factor. Big-$O$ and related concepts don't care about constant factors.

The base of the log is absolutely a constant: the base used for the calculations might depend on the whim (or, more likely, convenience) of the person who did the analysis but it certainly doesn't depend on the input.


Is there no sorting algorithm with all specific desired properties?

WikiSort and GrailSort are two fairly recent algorithms that do in place, stable, worst case $O(n\ lg(n))$ key comparisons.  Unfortunately I don't understand them well enough to know if they approach $O(n)$ swaps or are adaptive so I don't know whether they violate the fourth and fifth conditions you have.

From looking at the paper "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner linked to by the WikiSort GitHub page, Kim and Kutzner claim to have a 'merge' operation that is $O( m (\frac{n}{m} + 1))$ (WikiSort is a variant of Mergesort) but I'm not sure if that translates to WikiSort having $O(n)$ swaps.  GrailSort is claimed to be faster (in the WikiSort GitHub page) so I could imagine that it's likely they both have worst case $O(n)$ swaps and are adaptive.

If anyone does manage to understand WikiSort and/or GrailSort I would appreciate them also answering my open question about it


Algorithm for display nodes of a particular node based on in-degree and out-degree

If you want to highlight the neighbors:
Use adjacency list representation, where each node has a list of all out-edges out of it, and a list of all in-edges into it.  Then given a node you can rapidly identify what to highlight.
If you want to highlight everything connected to that node (at any distance):
Use DFS to find the set of nodes that are reachable from it.


Size of address registers and data registers in relation with memory size

This question is not so simple to answer. At first sight, 32 bit address registers seem to perfectly match 2^32 byte = 4 GB of physical memory. However, with 32 Bit you can also address more than 4 GB, like Physical Address Extension (PAE) does. The opposite way round means that you can access 4 GB with less than 32 bit address register.

The data registers are not related to the memory size at all in my opinion. The data registers are mainly an indicator how much data can be transferred at one time. If you want e.g. to crack SHA-512, then you could design a CPU which benefits from transferring 512 bit of data at one time, so you have 512 data registers.

The same SHA-512 cracker CPU brings us to the accumulator: ideally the CPU would also process 512 bit numbers in one cycle, so the accumulator is also 512 bit.


Proving that a specific language is a CFL, and that another language is not a CFL

First you have to realize that the extremes of the strings are of the form $0^n10^{2n-1}$ and $0^{2n-1}10^n$. You can get a language similar to that by the grammar $S \to 1 \mid 0S00 \mid 00S0$. From this some fine-tuning is needed. First to get $1$'s at the places where now only $0$'s are. Then to get the boundary conditions exactly right.

For the non-context-free other language I would also consider an "extreme" string, similar to $0^n10^n10^n$. That is not exactly one from the language, but close enough for a start.

(Nice exercise, that problem 2.48a in Sipser)


How about $(x_1 \lor x_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_2 \lor \bar{x}_3)$?


Why if L and ¬L (Complement of L) are turing-recognized both are turing-decidable?

I will try to explain it in simpler terms.
If $L$ is Turing recognizable, there exists a TM $M_1$ that halts and accepts any input string $w \in L$. It is not guaranteed to halt on any input string $w \notin L$.
If $\bar{L}$ is Turing recognizable, there exists a TM $M_2$ that halts and accepts any input string $w \notin L$. Similarly to above, $M_2$ is not guaranteed to halt on any input string $w \in L$.
Now, for every $w$ we have two options: either $w \in L$ or $w \notin L$. Therefore for any input string $w$, exactly one of these machines will halt and accept. This allows us to construct the decider described in you proof. Create a machine $M$ that simulates $M_1$ and $M_2$. With $w$ as input, accept $w$ if $M_1$ accepts, reject if $M_2$ accepts. This machine is a decider for $L$ and therefore $L$ is decidable.
To prove $\bar{L}$ decidable as well, you could apply the same logic, but it is sufficient to point out that decidable languages are closed under complement.


Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular

The statement is false. Consider the language $L = \{a^n b : n \geq 0\}$. Then $L' = \{ a^n b a^n b : n \geq 0 \}$ is not regular (exercise).

The invalid point in your reasoning is a confusion between the following two languages: $L' = \{ ww : w \in L \}$ and $L'' = \{ w_1w_2 : w_1,w_2 \in L \}$. It is $L''$ which is the concatenation of $L$ with itself. Whereas $L'$ need not be regular, $L''$ is always regular when $L$ is.


There is a single instruction stream. Modern processors just manage to pick up multiple instructions from the instruction stream simultaneously.

For something like a POWER processor, where each instruction is always four bytes in size, that is quite easy. Instructions are loaded into cache lines, and if a cache line holds 8 or 16 instructions, it is quite easy to read four instructions at the same time.

For an x86 processor, it is more difficult because instructions have different sizes. Still, it is possible (with a lot of effort) to read several consecutive simple instructions simultaneously.


Fitness functions for low-dimensional parts of cooperative coevolution algorithms

Every sub-vector is evaluated by concatenating it with the best-fit individuals (sub-vectors) from the rest of the sub-populations to form a so called context vector.

The context vector contains all the parameters required by the benchmark function and is fed into it for fitness evaluation.

This is actually where the cooperation happens.

DECC-G is "just" a cooperative co-evolutionary (CC) scheme based on Differential Evolution (DE) and a random split/grouping of the vectors/individuals (-G).

It shares with the other co-evolutionary algorithms the general architecture:

(Coevolutionary model of three species shown from the perspective of each in turn. Image from Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents by Mitchell A. Potter, Kenneth A. De Jong)

As a side note the reference implementation of DECC-G can be found here.


Ok, so we need to get a bit mathematical here. Let's first define the following quantities

$X_n$ height of a tree composed of $n$ nodes.
$Y_n = 2^{X_n}$ is referred to as the exponential height.

One of the BST's properties is that the left subtree must contain key values less than the root. Also, the right subtree contains key values greater than the root. This property is recursive so it applies to any node. Having said that, pick any node at random, call it the $i^{th}$ node, then, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements. Therefore,
$$Y_n = 2 \max (Y_{i-1},Y_{n-i})$$
Assuming all nodes are picked with equal probability, so picking a node $i$ has the following probability $$Pr(i) = \frac{1}{n} \quad \forall i=1\ldots n$$
Now, let us find the expected value of $Y_n$
\begin{align}
 E(Y_n) &= E[2 \max (Y_{i-1},Y_{n-i})]\\
 &=
 2 \sum\limits_{i=1}^n Pr(i)E[\max (Y_{i-1},Y_{n-i})] \\
 &=
 \frac{2}{n} \sum\limits_{i=1}^n E[\max (Y_{i-1},Y_{n-i})] \\
 &\leq
\frac{2}{n} \sum\limits_{i=1}^n
E(Y_{i-1}) +
\frac{2}{n} \sum\limits_{i=1}^n E(Y_{n-i})  \\
&=
\frac{2}{n} \sum\limits_{i=0}^{n-1}
E(Y_{i}) +
\frac{2}{n} \sum\limits_{i=0}^{n-1} E(Y_i)  \\
&=
\frac{4}{n} \sum\limits_{i=0}^{n-1}
E(Y_i)
\end{align}

Now, by induction, you can actually prove
\begin{equation}
 E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
Remember that we have
\begin{equation}
 2^{X_n} = Y_n
\end{equation}
or
\begin{equation}
 E(2^{X_n}) = E(Y_n)
\end{equation}
Using Jensen's inequality, we can say that
\begin{equation}
 2^{E(X_n)}\leq  E(Y_n)
\end{equation}
But
\begin{equation}
 E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
So
\begin{equation}
 2^{E(X_n)}\leq  E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
And note that
\begin{equation}
 C_{n+3}^3
 =
 \frac{(n+3)!}{3!n!}
 =
 \frac{(n+3)(n+2)(n+1)}{6}
 \sim
 O(n^3)
\end{equation}
So
\begin{equation}
 2^{E(X_n)} \leq O(n^3)
\end{equation}
Take log on both sides,
\begin{equation}
 E(X_n) \leq O(\log n^3) = O(3 \log n) = O(\log n)
\end{equation}
Therefore, the average BST height is of order $O(\log n)$, which is what you'd expect out of Binary stuff, right ?


You can apply Davis-Putnam procedure and note that with the given restriction applying resolution rule will not be increasing formula size exponentially (in fact, it will be decreasing it). Thus, every iteration of procedure will have polynomial time complexity.
Read about Tseytin transformation and try to exploit the same idea. You can replace variable $x$ with $y$ and add $x \leftrightarrow y$ to the formula. With a proper replacement strategy you will be able to obtain an equisatisfiable formula in which every variable occurs at most three times: one in the original formula, one as the left part of equivalence, one as the right one.


Does this algorithm on a circular linked list ever terminate?

The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have 1->next = 2 and 2->next = 1. In the first iteration we'll change 1->next to 1->next->next = (1->next)->next = 2->next = 1 so 1->next will point to 1 and the loop termination condition applies, so we bail and return 1->data.

If $n>2$, every iteration of the loop will point around a node, eliminating it forever from consideration, so every iteration of the loop decreases the number of nodes in play, so we'll always get to the $n=2$ case eventually and then halt.

It might help to think of this as the nightmarish situation where a group of $n$ people have been captured by bloodthirsty pirates. The pirates arrange the group in a circle and, starting at person 1, go around the circle, shooting every other person until only one remains. Where do you want to position yourself so that you are the last surviving person?

This is a well-known problem, called the problem of Josephus, and is often assigned as an exercise in a beginning programming class. The solution is nifty: Given $n$, write it as $n=2^m+k$, where $0\le k < 2^m$, then the last survivor is the one in initial position $2k+1$ (starting at position 1). Given this, we have that with $n=729$ the survivor will be the one in position 435 and with $n=2200$ the survivor (after a heck of a lot of shooting) will be the one in initial position 305.


There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (more specific link here) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction.

While many-one reductions are generally the default notion in complexity theory, Turing reductions and the resulting degree structure are the default in computability theory. Note that if all I want to do is prove the undecidability of some set, a Turing reduction from some known-to-be-undecidable set is sufficient.

First, let's explicitly recall the definitions of the languages involved:

$A_{TM}=\{\langle M,w\rangle: M$ halts and accepts on input $w\}$.
$HALT=\{\langle M,w\rangle: M$ halts on input $w\}$.

Your proposed reduction of $HALT$ to $A_{TM}$ is correct: given $M$, we can computably build a new machine $\hat{M}$ which accepts precisely those strings on which $M$ halts. (Basically, just replace all the "reject" states in $M$ by "accept" states.)

Now let's look at the other reduction which you linked to (more specific link here).

Basically, rather than going to "all halting states accept" the linked argument considers separately:

the original machine, and
the "contrary" machine which accepts exactly when the original one rejects and vice-versa.

An affirmative answer for either case in $A_{TM}$ ensures an affirmative answer for the original machine in $HALT$.

Off the top of my head I see no reason to do this rather than follow your argument, especially because it yields a weaker result, but it is correct and is enough to prove the broader claim in the slides, namely that $A_{TM}$ is undecidable.


Find all rational roots of a polynomial equation

The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The CGAL library (in version 4.9) for example uses the method developed by Arno Eigenwillig in his PhD thesis Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs.


All $LR(1)$ grammars -- indeed, all $LR(k)$ grammars -- are unambiguous, by definition.  But the converse is not true: the fact that a grammar is unambiguous does not say anything about whether it can be parsed with an $LR(k)$ parser.

The grammar you present is not $LR(1)$, although the language itself is. (In fact, the language is regular: $(aa)^*$.) But that's not true for the language of even-length palindromes which has a rather similar unambiguous CFG:

$$\begin{align}
  S &\to \epsilon \\
  S &\to a S a \\
  S &\to b S b
\end{align}$$

Intuitively, the problem with parsing palindromes deterministically is that you have to start popping the stack at the middle of the sentence. But you can't tell where the middle of the sentence is until you reach the end, and since there is no limit on the length of a sentence, the end could be arbitrarily distant from the middle. So no finite lookahead is sufficient to make the decision.

A context-free language is $LR(k)$ precisely if it is deterministic. For the outline of a proof of the non-determinism of the language of even-length palindromes, see: prove no DPDA accepts language of even-lengthed palindromes


The number 1.19e-07 is the difference from 1.0 to the next larger representable floating point number. Single precision floating numbers have the form $x = ± 2^k m$, where k is a small integer, and 1 ≤ m < 2 is a multiple of $2^{-23}$.

If you calculate a result x, and $2^k ≤ x < 2^{k+1}$, then x will be rounded to the nearest multiple of $2^{k-23}$, with a rounding error up to $2^{k-24}$.

Don't think of floating-point arithmetic to have "uncertainty". It gives a perfectly fine well-defined result, just not the one you might have wanted.

As far as your table is concerned, it doesn't make any sense to me, but I am very confident that there is no square root involved when you try to find upper bounds for floating point errors.

To analyse floating point errors: Multiplication and division may add the relative errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example multiplying by 2.0). Addition and subtraction may add the absolute errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example subtracting x-y where x/2 ≤ y ≤ 2x.

For tightest bounds, you analyse the error depending on the input values, and you can also improve the error by arranging operations in the right order.


Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

Edit: This proof is insufficient as pointed out in comment.
I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.
Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.


First, let's unpack what $\Theta(1)$ means.

Big $O$, and big $\Theta$, are classes of functions. There's a formal definition here, but for the purposes of this question, we say that a function $f$ is in $O(1)$ if there's a constant $c$ where, for all $x$, $f(x) \leq C$. That is, $f$ grows at most as fast as a constant function.

Big-$\Theta$ doesn't mean much for constant functions, because when describing algorithm time or space usage, there isn't much below constant. But to explain what it means, $f \in \Theta(1)$ if there are some constants $c,d$ such that, for all $x$, $d \leq f(x) \leq c$. That is, $f$ grows at least as fast, and at most as fast, as a constant function.

Now what does this have to do with memory usage? Consider some algorithm $A$. There is some (mathematical) function which, given an input $n$, gives the maximum memory usage of your algorithm $A$ on any input of size $n$. Let's call this function $mem$.

So, now we combine our two concepts. If an algorithm uses $\Theta(1)$ memory, then its memory usage function is in $\Theta(1)$, meaning that there exists some $d,c$ such that, for any input, the memory used is between $d$ and $c$.

In short, this means that the memory usage of the algorithm is in some constant range, regardless of the input.

Usually, the memory function does not account for the memory used to store the input to the algorithm, since otherwise memory usage would always be at least $\Theta(n)$.


Need help understanding what co-recursively enumerable means

If you by co-CE mean co-Computably Enumerable, then they are the same.

The field called Recursion Theory is also known as Computation Theory.

You find the same analogy in the classes.  Recursive is a different way of calling Computable.  A recursively enumerable set is a different way of calling computably enumerable set.


Is there any correspondence between SUM type in type theory and arithmetical summation?

The arithmetic notation in type theory is motivated by the behaviour on sets, where the disjoint union $A + B$ has $|A| + |B|$ elements; the cartesian product has $|A| \times |B|$ elements; and the set of functions $B^A$ has $|B|^{|A|}$ elements. Sum, product and function types satisfy many of the usual identities you expect of arithmetic (although typically up to isomorphism, rather than equality).

The paper Objects of Categories as Complex Numbers by Marcelo Fiore and Tom Leinster explores this in some detail, though it helps to have a little experience with algebra or category theory.

Sometimes a natural number $n$ will denote a type with exactly $n$ terms in any context (analogous to a set with $n$ elements). In this setting, $3 + 4 \cong 7$ as types. $x + 6$ isn't well-formed without placing $x$ in some context.


Periods of an LFSR with characteristic polynomial that is a product of primitive polynomials

The states of a LFSR with characteristic polynomial $p(x)$ correspond to elements of the multiplicative group of $GF(2)[x]/(p(x))$.  The period of a LFSR state is the order of the corresponding group element.  So, we can rephrase this as a group theory question, and use facts we know from group theory to answer the question.

The LFSR state with minimal period is exactly the group element $g \in G$ with minimal order, where here $G_c$ is the multiplicative group of $GF(2)[x]/(c(x))$.

The LFSR state with minimal period (other than the all-zeros state) is the group element with minimal order (other than the identity element).

Thus, to find the minimal period you want, you need to find the order of the minimal-order group element of $G_c$ (other than the identity element $1$).

Assuming $f,g$ have no common factor (i.e., $f\ne g$), the structure of $G_c$ is $G_c \cong G_f \times G_f$, where $G_f$ is the multiplicative group of $GF(2)[x]/(f(x))$ and $G_g$ is the multiplicative group of $GF(2)[x]/(g(x))$.  This follows from an analog of the Chinese remainder theorem.

Let $g_1$ be the group element of minimal order in $G_f$, and $g_2$ the group element of minimal order in $G_g$.  From what we know about the structure of $G_c$, the group element of minimal order in $G_c$ is either $(g_1,1)$ or $(1,g_2)$.  So it suffices to find the group elements of minimal order in $G_f$ and $G_g$.

From the fact that $f$ and $g$ are primitive, we know that $G_f,G_g$ are cyclic groups of order $2^{n_f}-1$, $2^{n_g}-1$, respectively, where $n_f = \deg f$ and $n_g = \deg g$.  Per Lagrange's theorem, we know that the divisors of $2^n-1$ correspond to the orders of the group elements of $G_f,G_g$.

Let $d_f$ be the smallest divisor of $2^{n_f}-1$ (such that $d_f>1$), and similarly for $d_g$.  Then the group element of minimal order in $G_f$ will have order $d_f$, and the group element of minimal order in $G_g$ will have order $d_g$.  It follows that the group element of minimal order in $G_c$ will have order $d=\min(d_f,d_g)$, and the LFSR state of minimal period will have period $d$.

So, the answer to your question is: the minimal period (other than the all-zeros state) is exactly $\min(d_f,d_g)$ where $d_f$ is the smallest divisor of $2^{\deg f}-1$  (other than 1) and $d_g$ is the smallest divisor of $2^{\deg g}-1$ (other than 1).


Why is ww a linear indexed language while www is not?

In linear indexed languages, the intuition is that you cannot copy a big information in one step, you have to do it in aletter-by-letter way. This causes things like $ww^R$ much easier to do than $ww$. We can still do $ww$ because you can first "create" the word $w$ by pushing its letter onto the stack and writing them at the same time on the output. Then you can pop the letters to the right or to the left as you prefer, so you can always produce $ww$.
For $www$ it's not possible anymore, because after producing $w$ on the stack and writing in on the output, you need to duplicate the stack, which is not allowed. However you could produce $www^R$, by writing the letters on both sides when popping the stack.


Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma

Let $p$ be the pumping length, and consider the string $u=1^{2^{p!+p}}$, $w = 0^p$, $v = \epsilon$. Notice $uwv \in L$. According to the pumping lemma, there is a value $q \in \{1,\ldots,p\}$ such that $1^{2^{p!+p}} 0^{p-q+iq} \in L$ for every $i \geq 0$. Choosing $i = 1 + p!/q$, we obtain a contradiction.


Special Monotone SAT problem: NP complete?

The variant where $A=B$ is known as monotone not-all-equal 3-satisfiability, i.e., Monotone NAE3SAT.  According to Wikipedia, it is NP-complete.  It is not the same problem as Monotone-3-SAT.


Decision tree complexity of finding parameters of "zigzag" array

The obvious lower bound is $\Omega(\log n)$, since there are $\binom{n+1}{2}$ possible answers. It is likely that using smart binary search you can find $i,j$ in $O(\log n)$ queries. I suggest starting with the easier case in which $j = n$, that is, the array increases and then decreases, and you want to find its maximum in $O(\log n)$ queries. Such arrays are known as bitonic, and indeed you can find $i$ in $O(\log n)$ comparisons (see for example this solution).


Given computable function, what are conditions for computability of inverse function?

Let us say that a computable function $f$ is invertible if there is another computable function $g$ that on input $y$ either finds $x$ such that $f(x) = y$ or returns $\bot$ when $y$ has no preimage.

For this definition, one can show that a computable function $f$ is invertible if and only if its range is decidable, that is, we can decide whether a given input has a preimage under $f$.


$\epsilon$-approximation Sub-linear time monotonicity testing

Let $P$ denote the number of pairs of indices $i<j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $[n]$ it holds that $C^2\le 3P$.
Suppose that the claim holds for $n$ and let $f$ be a function defined on $[n+1]$. We denote by $C(n),P(n)$ the number of corrections and monotonicity violating pairs for $f|_{[n]}$ correspondingly. Finally, let $w(n)$ denote the weight of $f$, i.e. $w(n)=\big|f^{-1}(\{1\})\cap[n]\big|$. Observe that if $f(n+1)=1$ then $C(n)=C(n+1)$ and the claim clearly holds, it thus suffices to focus on the $f(n+1)=0$ case. If $f(n+1)=0$ then $P(n+1)=P(n)+w(n)$ and $C(n+1)\le C(n)+1$. Applying the inductive hypothesis $C^2(n)\le 3P(n)$ we have:
$$C^2(n+1)\le C^2(n)+2C(n)+1\le 3P(n)+2C(n)+1=\\3P(n+1)+2(C(n)-w(n))- w(n)+1$$
Since $C(n)\le w(n)$ and $w(n)\ge 1$ (the claim is trivial for the constant zero function), this concludes the proof.
The above inequality yields a simple algorithm for testing monotonicity. Sample a pair $i<j$ uniformly at random and answer "no" if $f(i)>f(j)$. Let $q$ denote the probability that $i,j$ is such a pair, then $q\ge \frac{P}{n^2}\ge \frac{C^2}{3n^2}\ge \frac{\epsilon^2}{3}$. By repeating this procedure $\approx q^{-1}$ times, you obtain an $O\left(\frac{1}{\epsilon^2}\right)$ algorithm for separating the monotone from the $\epsilon$-far from monotone case.


The order of growth analysis for simple loop

When the iterations of the inner loop depend on the outer loop, it's better to sum over the amount of iterations of the inner loop. There is no need to overcomplicate this and think of logarithms just because the outer loop has logarithmic behavior.

Iterations

In this example, we can see the number of iteration the inner loop performs is halved in each step of the outer loop:

$N$ iterations of the inner loop
$\frac{N}{2}$ iterations
$\frac{N}{4}$ iterations
$\dots$
$\frac{N}{2^i}$ iterations
$\dots$
1 iteration

as the outer loop iterates.

Formalizing

Factoring $N$, we get:
$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N})$$

Knowing that:
$$\sum_{i=0}^\infty \frac{1}{2^i} = 1 + \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+\cdots = 2$$

we can conclude that:

$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N}) < 2N$$

Which is why the algorithm's complexity is bounded by $\mathcal{O}(N)$

Since the algorithm performs at least $N$ steps (assuming $N \geq 1$), it follows that the runtime behavior is also described by $\Omega(N)$, which implies that it is in $\Theta(N)$


Can this set of propositions be represented and proved in Haskell?

Your Haskell encoding fails to capture proofs in propositional calculus (which is what the book you referred to does). The failure is not due to your using Haskell, but because of your encoding evaluation of Boolean values instead of proofs, and these are two completely different things.

When people speak about "Haskell proving things" they mean the following: given a type t which represents a proposition $T$ via the propositions as types translation, does there exists a Haskell program p of type t which corresponds to a proof of $T$?

Example: the proposition $((A \land B \Rightarrow C) \Rightarrow (A \Rightarrow B) \Rightarrow (A \Rightarrow C)$ corresponds to the (polymorphic) type ((a,b) -> c) -> (a -> b) -> (a -> c). The program \ f g x -> f (x, g x) has this type, and therefore corresponds to a proof of the proposition. The kind of logic that can be represented in this way is intuitionistic.

However, because Haskell has general recursion, not every Haskell program corresponds to a proof, and in fact Haskell cannot be considered as a proof system. It is a programming language. A better choice is Agda or Idris.

You are translating propositions into Boolean algebra which you then encode using the Haskell datatype Bool. You are therefore misusing the phrase "prove in Haskell". At best you are trying to evaluate Boolean expressions, which is not the same thing. You defined, in a somewhat convoluted way, a (partial) evaluation strategy that evaluates various Boolean propositions. It's not a very good one, for instance if you change p = True line to p = False, your program fails to evaluate a.

This has nothing whatsoever to do with Haskell because it is not specific to it. You can do the exact same thing in just about any programming language, and even in Excel. However, as was suggested already twice, prolog seems to be the most appropriate tool for the problem at hand. You are not "researching" Haskell here. I believe we already tried to explain this to you in the previous question you linked to. I hope it gets across this time.


Connection between castability and convexity

This is a proper answer but feel free to correct me I think I did not get the right definitions. This is why I begin with simple facts that should be checked first.

I suppose your are talking about $\vec v$-castability of a "open" polyhedron.

Indeed it seems that no "closed" polyhedron is $\vec v$-castable.
For every $\vec v$, a convex "closed" polyhedron can always be cut into two "open" parts among a plane of normal $\vec v$ that are $\vec v$-castable and $(-\vec v)$-castable.
The test of $\vec v$-castability is in $O(n)$ (even if is not convex)
The problem (Is there a $\vec v$ s.t. $P$ is $\vec v$-castable?) seems to be linearly reducible to the convex hull, which is in $O(n\log n)$:

First consider each outward normal $\vec{n_i}$ into a point of the unit sphere.
Compute $H$ the convex hull of these points.
If the origin $0$ is in $H$ then for all $\vec v$, $P$ is not $\vec v$-castable.
If the origin $0$ is not in $H$ then let $\vec v$ be the vector starting at the projection of $0$ on $H$ and ending at $0$. The vector $\vec v$ defines a half-space containing none of the $\vec{n_i}$ meaning that $(\vec v, \vec{n_i})>90°$.
If the origin $0$ is on the surface of $H$, just take the normal of $H$ in $0$ for $\vec v$.

not in the convex hull iff there exists $\vec v$ such that

If $P$ is convex and "open" (whatever it means), then you only need its "frontier" and the corresponding orientation. You apply the same algorithm as above on the frontier (plus the orientation vector) reducing the complexity. For a polygon it becomes in $O(1)$ if you already know the two segments on the frontier.

Hope this helps.


Algorithm to shrink a DFA by introducing nondeterminism?

For efficient heuristics I'd suggest looking into the CAD literature on the state encoding problem (assigning binary identifiers to states of a DFA to minimize the amount of logic for the state transition function.)  Devadas and Newton, "Decomposition and factorization of sequential finite state machines," IEEE TCAD, 8(11):1206-1217, 1989 points out that there is a close relationship between state encoding and state machine decomposition.

If for a DFA with $N$ states you assign a unique $M$ bit state identifier to each state ($\lg_2N < M\leq N$), then you have essentially decomposed the DFA into a network of $M$ interacting two-state machines.  Equivalently: you have defined a set $S$ with $M$ elements, and assigned a unique subset of $S$ to each state in your original DFA.  This is also what the Rabin-Scott powerset construction algorithm does.  So by doing a state encoding on the DFA we are trying to reverse engineer the set that the powerset construction algorithm started from.

In the traditional state encoding problem all encodings are legal, and there is some objective function (related to the amount of logic in the state transition function) that you are trying to minimize.  To generate an NFA you need to solve a constrained version of the enconding problem where:

  an encoding of $M$ bit identifiers to the DFA states represents an NFA iff for each symbol in the alphabet the transition function for each bit is a simple disjunction of bits.  (No conjunction or negation is allowed.)

So you could enumerate all the $M$ bit encodings for all $\lg_2N < M\leq N$, and check whether each one satisfies the constraint.  (Note that for $M=N$ the trivial "one-hot" encoding always satisfies the constraints, and gives you the DFA.)  The enumeration is ridiculously large though, (Di Micheli's textbook gives it as something like $\frac{2^M !}{(2^M - N)!M!}$.)  The reason I'm suggesting the CAD literature is that there are techniques for doing this search implicitly rather than enumerating (for example, by using BDDs, see Lin, Touati and Newton, "Don't care minimization of multi-level sequential logic networks," Int'l Conf Comp-Aided Dsgn ICCAD-90:414-417, 1990.

Example

Take the following DFA, (with a state encoding that I derived by cheating (I generated the DFA from an NFA using Rabin-Scott, and the encoding represents the subsets chosen by Rabin-Scott.))

If we call the bits in the state assignment ABCD, then when the input symbol is 1, the transition function is A=A, B=A, C=B, D=C.  When the input symbol is 0, the transition function is A=A, C=B, D=C.  This is a purely disjunctive transition function with no conjunction or negation, so this state encoding gives us an NFA.  The states in the NFA correspond one-to-one with the bits in the encoding, and the transition function is as given:

Formulation as boolean satisfiability problem

The informal description above leads directly to an encoding as a boolean satisfiability problem.  There is a set of variables that describes the transitions in the NFA, and a set of variables for the DFA state encoding that would be derived from Rabin-Scott for the chosen NFA.  The transitions of the specific DFA you are trying to decompose are used to place constraints on the NFA transitions.

Suppose we are given a DFA with $N$ states for a language with $S$ symbols, and we would like to derive an $M$ state NFA, with $\lg_2N<M\leq N$.  We will use the variables $y_{sft}$ to represent the possible transitions in the NFA.  $y_{sft}$ will be true iff there is a transition in the NFA from NFA state $f$ to NFA state $t$ on symbol $s$.  In the above example NFA, the alphabet is of size 2 and there are 4 NFA states, so there are $SM^2=32$ $y$ variables and $y_{0AA}, y_{1AA}$, and $y_{1AB}$ are all true while $y_{1DA}$ is false.

We will use the variables $x_{dn}$ to indicate whether or not the Rabin-Scott algorithm should include NFA state $n$ in the set of states labeling DFA state $d$.  In the example above we have $N=8$ DFA states and $M=4$ NFA states so there are 32 $x$ variables.  In the example above suppose the bottom-most state (the one labeled "1011") is state $k$, then $x_{kA}$, $x_{kC}$, and $x_{kD}$ are true while $x_{kB}$ is false.

Now the constraints.  First of all, Rabin-Scott must find a different encoding for each DFA state, so for the DFA states $i < j$ and all NFA states $\{A,B,\cdots, D\}$:
$$
(x_{iA} \neq x_{jA}) + (x_{iB} \neq x_{jB}) + \cdots + (x_{iD} \neq x_{jD}).
$$

Next it must be the case that if Rabin-Scott found a transition from DFA state $i$ to DFA state $j$ on symbol $s$ then for each NFA state $k$ included in the encoding of $j$ there must be an NFA state $l$ from the encoding of DFA state $j$ such that the original NFA had a transition from $l$ to $k$.  In the example above, on symbol "1" there is a DFA transition from DFA state "1000" to DFA state "1100" so there must be an NFA transition from NFA state A to NFA states A and B and no NFA transition from NFA state A to either NFA state C or D.  So for each of the $o(SN^2)$ edges in the DFA we have the constraints:
$$
\begin{eqnarray*}
x_{jA} & = & y_{sAA} x_{iA} + y_{sBA} x_{iB} + \cdots + y_{sDA} x_{iD} \\
x_{jB} & = & y_{sAB} x_{iA} + y_{sBB} x_{iB} + \cdots + y_{sDB} x_{iD} \\
       &   & \cdots                                                    \\
x_{jD} & = & y_{sAD} x_{iA} + y_{sBD} x_{iB} + \cdots + y_{sDD} x_{iD}.
\end{eqnarray*}
$$

Finally we need to deal with the start and accept states.  The DFA start state is encoded with the union of the NFA start states, so the DFA start state better not be encoded with the empty set, so $x_0A + x_0B + \cdots + x_0D$.  And finally we need a set of variables $f_n$ to indicate whether each NFA state is an NFA accept state.  It must be the case that the encoding for every DFA accept state contains at least one NFA accept state and that the encoding for every DFA non-accept state contains no NFA accept states so: $x_{iA}f_A + x_{iB}f_B + \cdots + x_{iD}f_D$ for DFA accept states $i$ and $\neg (x_{jA}f_A + x_{jB}f_B + \cdots + x_{jD}f_D)$ for DFA non-accept states $j$.


Information about on die structures are scarce for the intel CPUs. You can look at https://en.wikichip.org/wiki/amd/microarchitectures/zen#Memory_Controller for information on AMD CPUs. Especially the following images:

You have the actual die seen under a microscope for the Zen microarchitecture. You clearly see the L3 and L2 controllers. There is one L2 cache per core while there is a shared big L3 cache in the middle.


Calculate number of ways to color matrix using inclusion-exclusion principle

Not an answer, but related.

The number of colorings of a graph on $N$ vertices with $c$ colors is a polynomial of degree at most $N$ in $c$ known as the chromatic polynomial. As such, it can be calculated by evaluating it at $N+1$ points, say $c=0$ to $c=N$. Your program need $\binom{8+1}{2} = 36$ of these polynomial.

In some cases there are formulas for the chromatic polynomial, but in the case of grids it's an open question to find such a formula, see this question on math.se.


Order of storage of pointers for a linked list of length n

Let $T(n)$ be the number of middle-of-list pointers you need to store for a list of length $n$.  For a list of length $n$, you need to store one pointer to the middle, plus however many middle-of-list pointers you need for the first half, plus however many you need for the second half.  This gives
$$T(n) = 1 + 2T(n/2)\,,$$
and we can take $T(1) = 0$, since a list of length $1$ probably doesn't need a middle-of-list pointer.

We have a reference question on formally solving recurrences like this but, for a rough-and-ready approach, we see that $T(2)=1$, $T(4)=3$, $T(8)=7$ so it's pretty clear that $T(n)=O(n)$ and, more to the point, $T(n)$ is about equal to $n$.

Well, now we wonder if a linked list was really the right data structure to be using.  First off, programming a linked list with middle-of-list pointers seems to be quite difficult.  Appending an item to the list sounds like it'll be awkward because you have all those pointers to update. Actually, I'm not sure what the data structure would even look like. But, anyway, maintaining the middle-of-list pointers costs us time so we'd better hope get something back for our investment of time, such as a saving in space.  Nope. Storing the linked list needs about $n$ "next" pointers and about $n$ middle of list pointers, for a total of about $2n$. But just storing your data in a binary tree would require $n$ nodes, each with a pointer to the left child and one to the right child, again giving a total of $2n$ pointers.


Does every NP problem have a poly-sized ILP formulation?

This answer is mostly a recap of the comments on the question above.

If a problem is NP-complete, it can indeed be reduced to ILP, by using Karp's reductions (― Joe, andy). Claims of "polynomial sized formulations" from one problem to another, are likely meant as more direct formulations, as opposed to multiple reductions through SAT (― Kaveh).


The below isn't necessarily a very practical algorithm, but (if I didn't make any mistakes) it shows this problem is in fact polynomial time.

I believe you can pose your problem as a series of integral maximum flow problems. I will phrase the problem with lower bound edge demands. This is equivalent to a regular flow problem.

We construct a maximum flow problem as follows:

Make a node for each apple and construct an edge from the source $s$ with capacity $[1, 1]$.
Made two nodes for each box (one input and one output node). For each apple that can fit in that box construct an edge from that apple to that box's input node with capacity $[0, 1]$. Connect the input and output node of each box with capacity $[0, 3]$.
Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $[0, 1]$.
Connect each box's output node to the sink $t$ with capacity $[0, 1]$.
Connect  $A$ and $B$ to $t$ with respective capacities $[0, n]$ and $[0, n]$.

Now we will minimize the number of overfull boxes ($\geq 2$ apples), which is the same as maximizing the number of half full boxes.  The critical observation is that each box can lose at most one of its apples to the sink - if it is overfull it must start flowing its apples through either $A$ or $B$. In the case of 3 apples both $A$ and $B$ must be utilized to maintain the $\text{out} - \text{in} = 0$ property of the flow problem.

Now when there is a feasible solution for $n = 0$ you know that there are no overfull boxes. Vice versa, if there exists a solution where there are no overfull boxes, there will be a feasible solution for $n = 0$.

Similarly, if there exists a solution where there are $k$ overfull boxes, there will be a feasible solution for $k = n$. This means that if we try all $n$ in increasing order, the first time we find a feasible solution we know it's optimal in $k$.

By inspecting the flow graph you can then find which apple goes in which box.

Since solving this maximum flow problem is polynomial in $x, y$ and $n$ is bounded in $y$, this algorithm is polynomial in the worst case as well.


How to find the virtual pages and physical memory frames?

So 2^12 page size makes 12 bits for offset and 8 bits for page number right? and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

you are correct

  maximum number of physical memory frames the system can have.

the size of frames is the same as the size of pages

so you have 18 bit for physical memory, which 12 bit of that is needed for the offset, now you are left with 6 bit which means you can have $2^6$ frames.

  Also a last part gives me the following:

  00110110011110111100

  and says the virtual page containing the address is mapped onto
  physical frame 45, give the corresponding physical address in binary
  format. How do i find that?

00110110 011110111100

so the 12 bits from the right are for the offset which you dont need to change, the remaining 8 bit which is 00110110 needs to be replaced with 45 and instead of 8 bit we would use 6 bit to map into physical address

therefore the physical address would be 101101 011110111100

this means that in the 54th row (00110110) of our page table for that process we would find the corresponding frame for that page to be 45 (101101)


Hint: first prove a loop invariant for the nested while, i.e. you need to prove that the nested while shifts to the right the elements as required to insert the j-element indexed by the outer for loop in its correct place. Then, prove the loop invariant for the outer for loop taking into account the suggestion by @Yuval and you are done.


How is Rice's theorem applicable to this decision problem?

As you correctly mention, polynomial running time is not a semantic property.

However, the property required here is not polynomial running time (of $M$), but functional equivalence to a TM with polynomial running time (on those inputs where $M$ halts). It is of no importance, how long $M$ runs on those inputs. This is a semantic property, since every other TM $M'$, that computes the same function as $M$ will have the property as well: $M'$ halts on exactly the same inputs $x$ as $M$ and on these inputs $M'(x) = M(x) = H(x)$.


How to prove that matrix inversion is at least as hard as matrix multiplication?

If you want to multiply two matrices $A$ and $B$ then observe that
$$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}=
\begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&&I_n\end{pmatrix}$$
which gives you $AB$ in the top-right block.
It follows that inversion is at least hard as multiplication.
EDIT: I had misread the question, the original answer below shows that multiplication is at least as hard as inversion.
Based on the wikipedia article: write block inverse of the matrix as
$$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}A^{-1}+A^{-1}B(D -CA^{-1}B)^{-1}CA^{-1}&-A^{-1}B(D -CA^{-1}B )^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{bmatrix}}.$$
Note that $A$ is invertible because it is a submatrix of the original matrix (which is invertible). One can prove that $D-CA^{-1}B$ is invertible because of the following identity ($M$ is the original matrix):
$$\det(M)=\det(B)\det(D-CA^{-1}B).$$
Some clever rewriting using Woodbury identity gives
$$\displaystyle {\begin{bmatrix}A & B \\C &D \end{bmatrix}}^{-1}={\begin{bmatrix}X&-XBD^{-1}\\-D^{-1}CX&D^{-1}+D^{-1}CXBD^{-1}\end{bmatrix}}$$
where
$$X=(A-BD^{-1}C)^{-1}.$$
Let $C(n)$ denote the complexity of matrix inversion for a $n\times n$ matrix. Let $\omega$ be the exponent of the best matrix multiplication algorithm, so that we can multiply two $n\times n$ matrices in time $O(n^\omega)$. Using the formula above, we can express the inverse of an $n\times n$ matrix using:

two inverses of half-size ($\frac{n}{2}\times\frac{n}{2}$): $D$ and $X$
six multiplications of half-size: $BD^{-1}$, $(BD^{-1})C$, $X(BD^{-1})$, $D^{-1}C$ and $(D^{-1}C)(XBD^{-1})$
two additions of half-size

This gives the recurrence
$$C(n)=2C(n/2)+6O((\tfrac{n}{2})^\omega)+2O((\tfrac{n}{2})^2).$$
Since $\omega\geqslant 2$, we rewrite the above as
$$C(n)=2C(n/2)+O(n^\omega).$$
We can now apply the Master theorem. Using the notation of the wikipedia article, we have $f(n)=Kn^\omega$ for some constant $K$, $a=b=2$ thus $c_{crit}=\log_22=1<\omega$. On the other we have a regularity condition on $f$ since
$$af(n/b)=2K(\frac{n}{2})^\omega=2{1-\omega}Kn^\omega\leqslant \frac{1}{2}f(n)$$ because $\omega\geqslant 2$. Thus the theorem tells us that
$$C(n)=O(f(n))=O(n^\omega).$$
It follows from that multiplication is at least as hard as inversion.


Bias or not when finding patterns using data mining techniques?

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case

Sure. This is called hypothesis testing.

  Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with

Exploratory data analysis, see http://github.com/MartinThoma/edapy as a tool.

  how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

You have a classification problem... So, just train the classifier you want to use.

  If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?

This depends very much on the context. What I happen to do at the very beginning quite often:

Look at the general distribution of the data per single feature: min, max, mean, median, number of different values. If the number of different values is small, print a bar chart
Null values: why are they there? Can they be replaced by a reasonable other value?
Covariance

  What is the difference between ML and data mining?

Taken from
https://stats.stackexchange.com/a/29186/25741

  Data Mining is about using Statistics as well as other programming methods to find patterns hidden in the data so that you can explain some phenomenon. Data Mining builds intuition about what is really happening in some data and is still little more towards math than programming, but uses both.

  Machine Learning uses Data Mining techniques and other learning algorithms to build models of what is happening behind some data so that it can predict future outcomes. Math is the basis for many of the algorithms, but this is more towards programming.


What does the leading turnstile operator mean?

On the left of the turnstile, you can find the local context, a finite list of assumptions on the types of the variables at hand.

$$
x_1:T_1, \ldots, x_n:T_n \vdash e:T
$$

Above, $n$ can be zero, resulting in $\vdash e:T$. This means that no assumptions on variables are made. Usually, this means that $e$ is a closed term (without any free variables) having type $T$.

Often, the rule you mention is written in a more general form, where there can be more hypotheses than the one mentioned in the question.

$$
\dfrac{
  \Gamma, x:T_1 \vdash t : T_2
}{
  \Gamma\vdash (\lambda x:T_1. t) : T_1\to T_2
}
$$

Here, $\Gamma$ represents any context, and $\Gamma, x:T_1$ represents its extension obtained by appending the additional hypothesis $x:T_1$ to the list $\Gamma$. It is common to require that $x$ did not appear in $\Gamma$, so that the extension does not "conflict" with a previous assumption.


Table-Driven Lexer and the Classification Table

A table-driven lexer is just a way of simulating a DFA. Lexer generators build DFAs from a lexical description, and then compile the DFA into the tables necessary to produce a lexical scanner.

Note that the goal is to not just identify lexemes, but to classify them by lexical type. Some lexemes have a unique spelling (like if and <=); others represent classes of symbols which have the same syntactic significance but different semantics. (That would be, for example, IDENTIFIER and NUMBER, which are two lexical types, each with a potentially unlimited number of different associated tokens.)

Lexical analysis with a state machine is slightly different from using a DFA to recognise strings, because the point of lexical analysis is to divide the input into a sequence of substrings, each of which is a token. It's important that this sequence is a partitioning of the string; every character is part of some token. That means that each successive token starts exactly where the previous token finished. In particular, that means that you don't have to worry about the if in the middle of different, but you do have to think about the for in fortunate. (All the same, it doesn't present a huge problem.)

As the Dragon book notes (and so do Cooper&Torczon IIRC), the vast majority of lexers use the "maximal munch" procedure (sometimes with a few exceptions), in which the lexeme produced at some point in the input is the longest one matchable with some lexical pattern.

In some cases, it is possible that the lexical analyser will overreach. As an example, consider lexing C, where . and ... are both possible lexemes, but .. is not. If the input contains .., the lexical analyser needs to try to match the pattern .... If that fails, if the input contains .. followed by something other than another  . (for example, ..345), the lexical analyser will have to backtrack. It will accept the first . as a token, and then restart the scan with the second . (which will turn out to lead to recognizing the number token .345 in this case).

So the precise algorithm used by the analyser when it is asked to produce the next token is:

Run the DFA until it reaches a state in which the next character has no valid transitions.
While running the DFA, always remember the last accepting state encountered.
When the DFA cannot be advanced any further, if it is not in an accepting state, back up to the last accepting state and return the corresponding token.

It's always a good idea to try to avoid this backtracking, but it is not always possible as the above C example indicates.

We said earlier that the goal of the analyser is to identify the lexical type of the token. How does it do that? Simple. The various patterns are combined into a single DFA, using the standard NFA->DFA transformation. (That's in the Dragon Book.) In the DFA which results from that transformation each state is a set of states from the original NFA, and is an accepting state if any of the associated NFA states is accepting. We map that onto a token type by noting which of the NFAs contains the associated accepting state. If there is more than one NFA which has contributed an accepting state, then we choose one of them arbitrarily. (Usually, we've arranged the patterns in priority order so that we can simply say that the first pattern wins.)

That gives us a mapping from DFA state to pattern number, and that is the role of the Token Type table.

In case that explanation was too theoretic, I've created two graphs. The first one shows DFAs for four patterns: the token <, the token <=, the token if and the token ID (any identifier). In the transitions, please interpret "letter" as meaning "any letter other than i or f", which was just too long to put on the graph. And see the paragraph below about character classification.

In the second graph, I show the DFA which results from combining these. I leave it as an exercise to construct the Token Type table.

The Transition table is simple: it just represents the DFA. It maps a pair <state, character> to a new state. Unfortunately, there are a lot of different possible characters -- 256, if we use 8-bit characters -- and usually quite a few states, and that would make for quite a large table, since it is essentially a two-dimensional array. To make the table smaller, we note that many characters have precisely the same transitions in every state. As a simple example, most of the 256 possible input characters are only valid inside character string literals or comments, and in those contexts all of them are effectively identical.

That's what the character classification table is. We gather the possible input characters into a set of equivalence classes, where each equivalence class has exactly the same transitions in every state. Any character with a specific transition -- including the i and the f in if, for example -- will be in an equivalence class by itself. But even then, we'll find that many alphabetic characters are not present in any keyword (upper-case characters, for example). And while some digits may have specific transitions -- 0 is a common case -- there are very few lexicons in which 2 and 3 have specific transitions. So we can probably reduce the number of possible transition characters from 256 to maybe 40 or 50, which is an 80% reduction in size of the transition table. In any case, if you don't want to do that, it's just an optimisation. The analyser will work fine either way.


Why do we study closure properties of formal languages?

I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction of compilers. Another answer is that in the past they played an important part in artificial intelligence (nowadays statistical methods are more important).

Once we agree that regular languages and context-free languages are an interesting object of study, closure properties are basic mathematical properties of these objects. In fact, part of the beauty and appeal of the subject of regular languages is the large number of properties that they satisfy, including closure properties. Regular languages serve as a model for other families of languages, and one tries to mimic one's knowledge of regular languages on other families of languages.

Closure properties are also interesting beyond formal languages — Tychonoff's theorem in topology is one example.

Specific closure properties of regular languages have given rise to a new type of algebraic structure, Kleene algebras, which abstract some of the closure properties of regular languages and of context-free languages.


Hint: The language is not context-free. So you will need to employ a type of grammar that is more powerful. Context-sensitive grammars can do the job.

If you need guidance in how to build a context-sensitive grammar for such a language, you might want check a context-sensitive grammar for $a^nb^nc^n$.


Unfortunately, backtracking is not taught in many universities although it is a basic technique in algorithms and programming. You can backtrack using two methods: recursive or iterative. In the iterative, you use a stack. In the recursive version, you use the built-in memory stack by calling functions recursively.

A code that generates something similar to what you want is the following (it is left as an exercise to do exactly what you want.).

void backtrack(vector<int> v, int index, int max, int n) {

1)  v.push_back(index);
2)  if (v.size() == n) { print(&v); }
    else {
3)      for (int i = index + 1; i <= max; i++) {
4)          backtrack(v, i, max, n);
        }
    }

}

This is called from the main function as: backtrack(v, 1, 5, 3);  where v is a vector, and 1 is the initial element to be inserted in the vector.

You can implement your print as following:

void print(vector<int>* v) {
printf("( ");
for (int i = 0; i < v->size(); i++) {
    printf("%d ", v->at(i));
    if (i < v->size() - 1) { printf(", "); }
}
printf(") \n");
}

Note that the output of the program above is: (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5). -- Try to correct it. [Hint: use a for-loop in main]. Usually, a backtrack function has a a helper function (e.g. backtrack_helper). I haven't used a helper in here. But you can use it in your improved version.

Remark:
I added some comments in the backtrack version to show how I got this backtracking. In 1) I did the action that is supposed to be taken. In 2) I check whether I have reached a correct solution . In our case, a correct solution is when we have a vector of size n (3). If I dont reach the correct solution, I go to backtrack more. The for-loop is the most important thing in the program. I check the last element to be inserted in the vector (call it index). Then in the for-loop I call backtrack for all the neighbors of this element. These neighbors are the elements that can be inserted after index. These are called sometimes legal neighbors of index. -- It may sound weird a bet now. Let me know if you need more clarifications.


Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

Consider this example:

Every vertex has one incoming and one outgoing edge, so it is not prevented by the first two constraints. It is however prevented by the third constraint, as if you take any of the two connected components for $S$ it violates the inequality.


What's the difference between dynamic and static pipelines?

The reference I've mentioned is actually self-contained; i.e, the answer I was looking for was there all the time. But considering that others could have the same doubt, I will reproduce an snippet from that reference and answer my own question:

  Pipelines are usually divided into two classes: instruction pipelines and arithmetic pipelines. A pipeline in each of these classes can be designed in two ways: static or dynamic. A static pipeline can perform only one operation (such as addition or multiplication) at a time. The operation of a static pipeline can only be changed after the pipeline has been drained. (A pipeline is said to be drained when the last input data leave the pipeline.) For example, consider a static pipeline that is able to perform addition and multiplication. Each time that the pipeline switches from a multiplication operation to an addition operation, it must be drained and set for the new operation. The performance of static pipelines is severely degraded when the operations change often, since this requires the pipeline to be drained and refilled each time. A dynamic pipeline can perform more than one operation at a time.

So, yes, a "function" is a synonym for "operation" in this context, but nothing is said about linear and non-linear pipelines. I hope some fellow can confirm if those terms exist indeed with the same meaning used in the Wikipedia.


Any way to optimize this with subset caching?

It sounds like you are not entirely clear on the properties and structure of your function $f$, which makes things harder.  So, my first advice would be to spend a little more time trying to characterize them, as they may help you select suitable algorithms.  That said, I will suggest several methods below, which you might find helpful.  I think you might find Method 3 perfect for your needs: it should help a lot.

Method 1: Memoize $g$

Suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $+$ is some fast monoid operation (i.e., commutative and associative).

Then a very simple approach is: whenever you see a new range $r$, compute $g(r)$, and remember the results of this computation (use memoization so you never need to compute $g(r)$ again).

Now, at each time step, you have some set of active ranges, say $a,b,c,d$.  So, compute $f(a,b,c,d)$ by computing $g(a)+g(b)+g(c)+g(d)$, where you recompute the sum from scratch but you don't need to re-compute $g(\cdot)$ values you've computed before.  If $a,b,c$ were previously present and only $d$ is new, then you'll only need to compute $g(d)$.  You've previously computed $g(a),g(b),g(c)$, so there is no need to re-compute those values -- you can just look them up in your memoization table.  Finally, you apply the $+$ operator three times to sum up the four values $g(a),g(b),g(c),g(d)$.

The running time of this method is $O(n)$ evaluations of the $+$ operator and $O(n_+)$ evaluations of $g(\cdot)$ per time step, where $n$ is the total number of ranges active at that time step and $n_+$ is the number of new ranges introduced at that time step (i.e., which weren't active at the previous time step).

The advantage of this method is that it is extremely simple: it should be very easy to implement.  It might be the best choice when the $+$ operator is very fast and $g(\cdot)$ is very slow, because it avoids re-computing $g(\cdot)$ but it makes no attempt to minimize applications of $+$.  If $+$ is also very slow, then you might do better using one of the more sophisticated methods below.

Method 2: Prefix sums

Suppose $f$ is as above, but now evaluting $+$ is slow.  Then the basic idea of Method 2 is that you can remember prefix sums.  If you've computed the sum $g(a)+g(b)+g(c)+g(d)$, then the prefix sums are the sums of the prefixes of this expression: i.e., the values $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$.  Using the obvious method to compute the sum, it takes no extra effort to find the prefix sums (you generate them along the way).  So, you might as well remember the value of all of those prefix sums, and reuse them whenever possible.

I suggest that initially, you take all of the ranges that are initially active, you sort them by their end date (so that the longest-lived ranges come first in the sequence), and then you compute prefix sums.  Say the initial ranges are $a,b,c,d$, in order of decreasing end date.  Then you compute $g(a)$, $g(a)+g(b)$, $g(a)+g(b)+g(c)$, and $g(a)+g(b)+g(c)+g(d)$.  The latter value is exactly $f(a,b,c,d)$, which you output.  However you also remember the prefix sums.  At some point in the future, $d$ will expire, so now you can throw away the value of $g(a)+g(b)+g(c)+g(d)$ and remember just $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$.  You always use the longest of those prefix sums as the beginning point for adding in new elements.

Unfortunately, it's a bit of a challenge to turn this into a full algorithm that will be really useful, so I'll jump straight to Method 3, which is a generalization of this.

Method 3: binary tree

Here's a better method.  Sort the active ranges by decreasing end date.  We'll maintain a binary tree, with one leaf per active range.

Annotate each node with the result of evaluating $f(\cdot)$ on all of the ranges underneath that node (e.g., if the leaves that are descendants of that node correspond to ranges $a,b,c,d,e$, then that node will be annotated with the value of $f(a,b,c,d,e)$).  Notice that the annotation on the root is just the result of evaluating $f(\cdot)$ on the set of all active ranges, so it is the desired output.

When you move on to the next step, some ranges will expire and some new ranges will be added.  This means you'll need to delete some existing leaves and insert some new leaves (in the appropriate place, maintaining the sorted order).

When you delete a leaf, you'll need to update the value on each of its ancestor nodes, but each ancestor node can be updated with $O(1)$ evaluations of $+$.  Insertion works similarly.  So, inserting or deleting a leaf at depth $d$ takes $O(d)$ work.  If you use a balanced binary tree data structure, then the depth will be $O(\lg n)$, where $n$ is the total number of leaves, so each deleted/inserted leaf will take $O(\lg n)$ work.  There are a variety of possible implementations, e.g., using AVL trees, red-black trees, or other balanced tree data structures.  Or, you can ignore the rebalancing operations and hope that your tree will stay approximately balanced in practice and keep your implementation simple.

Ultimately, this requires $O(n_+)$ evaluations of $g(\cdot)$ and $O((n_+ + n_-) \lg n)$ evaluations of $+$ per time step, where $n$ denotes the total number of ranges active at that time, $n_+$ the number of ranges newly introduced at that time step, and $n_-$ the number of ranges that expired at that time step.  This is significantly better than Method 1, and it generalizes Method 2.

Method 4: Group operation

Finally, for completeness, let me mention one specific situation where one can achieve better running time.  Suppose the $+$ operation has an inverse.  In other words, suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $g$ is a slow function and $+$ is some group operation.  (In other words, $+$ is a binary operator that is commutative, associative, and has an inverse operator $-$ with the obvious properties: e.g., $x+y-y=x$.)  Assume $+$ and $-$ are fast to compute.

In this case, there is a good solution.  You can simply update the value of $f(\cdots)$ on the fly.  At each time step, some new ranges get added and some get removed, so you compute $g$ of each of those ranges and add the values that are being added and subtract the ones that are being removed.

For example, suppose at time step 0 we have $a,b,c$ active; then we compute $f(a,b,c)$.  Now suppose at time step 1 just $b,c$ are active: then we can compute $f(b,c)=f(a,b,c)-f(a)$, using a single computation of $g$ and a single subtraction (since we already know the value of $f(a,b,c)$, no need to recompute it).  Let's say that at time step 2 we have $b,c,d$ active: then $d$ is new, so we compute $f(b,c,d) = f(b,c)+f(d)$, which requires just a single computation of $g$ and a single addition.

You can further improve this using memoization: remember the value of $g$ at all the ranges you've computed it on.  Then to get from $f(a,b,c)$ to $f(b,c)$ requires just a single subtraction: there's no need to recompute $f(a)=g(a)$, since you've previously computed it.

I know you said that this doesn't apply to you, since you don't have any way to compute the inverse operation -- but I'm mentioning this for completeness, in case anyone else comes across a similar situation but does have inverses.

More reading, background, and tangential stuff

Here's some additional reading on topics that might be helpful or interesting to you.

Prefix sums are a helpful way to amortize effort, when dealing with commutative associative operations (like your $+$).
Fenwick trees are a nice generalization of prefix sums that allow certain powerful operations.
A more complex sort of situation with trying to reuse computation, with a monoid operation: Data structure for finding the sum of edge weights on a path.


What algorithm to find end state probabilities

Take your matrix, and normalize the rows to sum to 1. Denote the result by $A$; in your example,
$$
A =
\begin{bmatrix}
0& 1/2& 0& 0& 0& 1/2 \\
4/9& 0& 1/3& 2/9& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0 \\
0& 0& 0& 0& 0& 0
\end{bmatrix}
$$
Let $v$ be a row vector with $v_0 = 1$ and $v_i = 0$ otherwise. In your example,
$$
v = \begin{bmatrix} 1&0&0&0&0&0 \end{bmatrix}
$$
Then $vA^t$ gives the probabilities of being in each state after $t$ steps, and so $w := v \sum_{t=0}^\infty A^t$ gives the expected number of times in each state. Since a final state terminates the process, for each final state $i$, $w_i$ is in fact the probability of the process ending at $i$. The vector $w$ can be calculated using the formula
$$
w = v (I-A)^{-1}.
$$
In your case, we get
$$
w = \begin{bmatrix} 9/7 & 9/14 & 3/14 & 1/7 & 0 & 9/14 \end{bmatrix}
$$
In particular, the probabilities of terminating at the final states $2,3,4,5$ are (respectively) $3/14,1/7,0,9/14$.

Regarding algorithms, we can rephrase the problem as follows: given $v,A$, find the vector $w$ such that
$$
w(I-A) = v.
$$
This requires solving a system of linear equations, for which there are many algorithms.


Which algorithm for counting the occurrences of a certain pattern (spots) in an image?

The best way to get an orientation is to read a textbook on computer vision or image processing.  There are lots of techniques known, and that's often the best way to get an introduction to a broad topic like this.

Anyway, for some specific techniques, I would recommend that you learn about the following candidate approaches:

Learn about morphological operators, and experiment with a few combinations of them.
Learn about the watershed transform, which might solve your problem immediately.  More generally, learn about image segmentation techniques, of which there are many.
You might want to consider applying thresholding to the image as a pre-processing step.

Your task looks pretty easy, so I imagine you should be able to find a very effective combination of techniques if you learn about them and try them out on sample images.


Levenstein distance and dynamic time warp

There is in fact a whole bunch of related algorithms. In modern context I believe "time warp" would be called sequence alignment. Depending on whether you want to match complete strings or optimal substrings one gets Needleman-Wunsch and Smith-Waterman.

In your latter algorithm the costs seem to vary, that is one can attribute different costs for deletion and insertion of a character, as well as for changing characters. Your first algorithm seems to fix these costs to $1$ for all three possible changes.


Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored?

Yes, it could make your performance worse.

Memory, memory bandwidth, cache density are primary concerns. Larger data size can:

result in increased cache and translation lookaside buffer (TLB) misses;
require more RAM to avoid paging.

E.g. x86 CPUs always load (if not already in cache) a whole cache line from memory.

So, assuming a cache line of 64 bytes, there are 64 8-bit-integers per cache line, yet only eight 64-bit-integers. Thus resulting in eight times as many memory transfers for processing a large array.

Also consider that many compiler are smart enough to figure out how to perform automatic vectorization1.

Taking advantage of the processor's SIMD capabilities you can pack eight 16-bit integers into the same space as two 64-bit integers and do four times as many operations at once.

  Is there a performance hit when using variable sizes lower than the native variable size of the architecture?

There isn't a general rule.

x86 CPUs can operate on fractions of a register and there will be no slow down at all2.

Other CPUs (e.g. PowerPC) cannot process a fraction of a register. So performing multiple operations on small integers may require masking / cutting back partial results. Anyway it's just a simple AND operation and often the compiler can find a way to avoid it entirely.

As a corner case some instructions can be slower when performed with the CPU's "native size" (e.g. multiplication / division of 64-bit quantities vs 32-bit quantities on Intel Pentium IV).

Interesting readings are:

What Every Programmer Should Know About Memory by Ulrich Drepper (chapter 6, about maximizing the efficiency of the data cache)
int vs long long in 64 bit machine
Performance 32 bit vs. 64 bit arithmetic
The microarchitecture of Intel, AMD and VIA CPUs by Agner Fog

1) automatic vectorization is a major research topic in computer science

2) x86 processors can suffer a partial register stall if you, say, write to BX and then try to read from EBX (something to consider mixing integer of different sizes).


Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

Each summing approach can be represented by a binary tree: the leaves represent the original elements and each internal node (including the root) represents the result element of the addition of the elements represented by its two children. For example,

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

... can be regarded as the following tree:

      16
     /  \
    9    \
   / \    \
  4   \    \
 / \   \    \
1   3   5    7

Then we rewrite the cost of each addition as the sum of original elements. For example, the costs in the example above are:

4 = 1+3
9 = 4+5 = 1+3+5
16 = 7+9 = 1+3+5+7

Total cost: 4 + 9 + 16 = 29

We can see each number corresponding to a leaf is contributed to the total cost in the additions corresponding to its ascendants. For a leaf $e$, If we denote by $h(e)$ the height of $e$, and by $f(e)$ the number corresponding to $e$, then the total cost is exactly $\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$.

Note each tree represents a prefix code of the leaves. In the example above, the tree represents the prefix code:

1: 000
3: 001
5: 01
7: 1

If we regard $f(e)$ as the frequency of $e$, then $\sum_{e\ :\ \text{leaves}}f(e)\cdot h(e)$ is the average length of the code, which is optimized by Huffman coding. Note the answer in your link describes exactly how Huffman coding works.


Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start
$$ S \to cYc \to caYYc, $$
at which point it is clear that we cannot generate $caac$.
I assume you know how to generate the language $c\Sigma^*c$, as well as the language of all words with an equal number of $a$-s and $b$-s. Instead of combining them in a complicated way, write grammars for both, and then join them together using a rule of the sort $S \to S_1 \cup S_2$.


As Wikipedia reports, the fastest currently known algorithm for the gcd of two $n$-bit numbers runs in $O(n f(n))$ time where $f(n)$ is a slow-growing function of $n$ (roughly $\log n \cdot \log \log n$).  It is not known whether the gcd of two $n$-bit numbers can be computed in $O(n)$ time.

This means that the iterative algorithm for computing the gcd of $k$ $n$-bit numbers (as described in the question) runs in $O(kn f(n))$ time.  Obviously, any algorithm needs at least $\Omega(kn)$ time -- this lower bound follows from the fact that any algorithm needs to read the entire input.  This doesn't leave much of a gap between the trivial lower bound and the running time of the iterative algorithm.  In other words, it doesn't leave much room for improvement in running time.

That's the theoretical answer.  From a pragmatic perspective, the $O(n f(n))$-time algorithms only become faster than (asymptotically slower) alternatives once $n$ is fairly large.  As a result, if $n$ is not too large, these results might not mean much.

Also, from a pragmatic perspective, we can expect that $\gcd(a,\gcd(b,\gcd(c,d)))$ might be faster than $\gcd(\gcd(a,b),\gcd(c,d))$.  They both yield the same answer, but the former might often be faster, because typically one of the two arguments to the gcd will be small.  Computing $\gcd(x,y)$ might be faster in practice if $y$ is much smaller than $x$ (because the first step is to replace $y$ with $y \bmod x$) than when $x,y$ are about the same size.  So, you might benefit by performing the gcd's in an order that gets you down to a small number as soon as possible.


The kernel of the system doesn't use the C library (at least not it's I/O facilities).

The kernel does offer system calls like read(3) and write(3) in Unix, and translates them into whatever magic the underlying hardware requires to do this. For example, as a very rough description of how this goes, to write to a serial port, the kernel copies the individual bytes to the serial port's register, signals that a new character is ready to transmit, and waits for it to be shipped off before placing the next one there. To write into a file the kernel keeps track of where the writing to the file has to take place, asks for space in the underlying device if the file will grow, and writes into the allocated space. Each filessystem has its own (rather complex) data structures on disk and in memory to keep track of free and allocated space, and so on. To manipulate it (and the underlying blocks on disk) usually another complex layer talking to the hardware is interposed.

Thus one way of looking at an operating system kernel is as a huge library offering nifty functions (system calls) that allow the programmer to access complex, even under the hood radically different functionalities, by a simple interface. That the programmer uses the convenience of the standard C library, some other language's library, or even chooses to write the system calls directly in assembler, is irrelevant.

The kernel does write messages on occasion. For this it has internal functions (in the case of e.g. Linux it is printk that mimics printf(3)) to do this by tickling the underlying hardware the right way.


Is it possible to define a pairwise function that can either append to a tuple or make a tuple, potentially with nested tuples?

The problem with this is that there is no way to distinguish between (1, 2) and 1 . 2: both have to produce (1, 2). This means that for a left-associative ., 1 . 2 . 3 and (1, 2) . 3 have to produce the same result. (And switching to right-associative . does not help: it has the same issue with 1 . (2, 3).)

Some ways I could think of bypassing this:

The . operator does not directly produce a tuple, instead it produces a wrapper for a tuple. This way, you can distinguish between 1 . 2 and (1, 2). But you also have to include an "unwrap" operation at the end. Though that could be handled by an implicit conversion, which makes the unwrap operation invisible in code.
The . operator looks like it's binary, but it's actually variadic. I.e. (1, 2) . 3 . 4 compiles to operator(.) ((1, 2), 3, 4). Though I don't know of any language that would do something like this.


Mixed integer non convex optimization problem

No, you can't infer NP-hardness from such an algorithm. Indeed, why should the existence of a slow algorithm mean that there can't be a fast algorithm?

For example, consider the problem of sorting $n$ integers. Suppose the first algorithm I give you is a one that tries all $n!$ permutations. Can we now safely conclude that this problem is somehow hard? Of course not and we know that there are many much faster polynomial-time algorithms for the problem.


Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

First we'll clarify the problem a bit. We have $n$ eggs, which we can drop from any floor we want. We also have the constraint that we are allowed a total of $d$ drops of these eggs (rather than $d$ drops per egg). Obviously, when we drop an egg and it breaks, we can't drop it again. Let $f(n,d)$ be the maximum number $M$ such that with $n$ eggs and $d$ drops, we can completely describe the behavior of our experiment for floors $1,\dotsc,M$.

In other words, with $M=5$ the possible outcomes are [YYYYY] (the eggs break when dropped from all 5 floors), [NYYYY] (the egg survives a drop from floor 1 but no higher floor), and [NNYYY], [NNNYY], [NNNNy], and [NNNNN]. Obviously, in all possible descriptions, all the N's must come before all the possible Y's

With that out of the way, let's tackle the recursion
$$
f(n,d)=f(n-1,d-1)+1+f(n,d-1)
$$
Our plan of attack is to drop the first egg from floor $x$, yet to be determined.
That egg either breaks or doesn't:

If it breaks, we know it will break when dropped from any higher floor as well, so we're left with $n-1$ eggs and $d-1$ more drops. In other words, we're looking at the lower floors and there will be $f(n-1,d-1)$ of them, namely floors $1, 2,\dotsc, f(n-1,d-1)$.
Since we've already settled the behavior at floor $x$, we need to have $x=f(n-1,d-1)+1$.
If it doesn't break, we know it won't break when dropped from a lower floor, so we still have $n$ eggs and $d-1$ drops remaining, which will mean that we can determine the behavior of the higher $f(n,d-1)$ floors. They will start at floor $x+1$ and will cover floors $x+1, \dotsc, x+f(n,d-1)=f(n-1,d-1)+1+f(n,d-1)$, exactly as the recursion stated.

For example, you correctly observed that $f(1,5)=5$ but your value for $f(2,5)$ was low. In fact, $f(2, d)=d(d+1)/2$, which is 15 in the case where $d=5$. Start with the first drop from floor 5, and you'll see that you can indeed determine the egg behavior at all of the first 15 floors.


Let $n$ be the size of an AVL tree with height $h$. Then we have
$$ \log_2(n+1) \leq h \leq c\log_2(n+2) + b$$
where $c\approx 1.44$ and $b\approx -0.328$. So,
$$ 0.8(1.6)^h\lt df^h=2^{-b/c}\left(2^{1/c}\right)^h=2^{(h-b)/c}-2 \leq n \leq 2^h -1 \lt 2^h $$
where $d\approx 0.85$ and $f\approx 1.618$.

Now you can see that the only number among 1.1, 1.9 and 2.1 that is between 1.6 and 2 is 1.9. Hence the answer is C.

I would not say it is asking for a tight bound.


Nominal unification: How this lemma is proved?

chi's answer is mostly correct, but I've poured through the paper, and can probably fill in the gaps a bit:

The proof proceeds in 3 steps:

Show that it suffices to prove:
$$\nabla\vdash \sigma(\pi^{-1}.t) \approx \sigma(X) $$
Show that the above derivation is implied by
$$\nabla\vdash \sigma(t)\approx\pi.\sigma(X) $$
Show that in turn this is implied by the assumptions of the theorem.

The structure of the proof is a bit confusing, since it proceeds "backwards", from the conclusion of the theorem to the hypothesis.

The first step involves mostly unpacking the definition of substitutions and the notation $\sigma\ \circ\ [X:=t]$.

The second step is handled by lemmas in the paper (lemmas 2.14 and 2.12 if we're reading the same version). This step is the most complex of the proof.

The last part is performed by changing $\nabla\vdash \sigma(t)\approx\pi.\sigma(X)$ to $\nabla\vdash \pi.\sigma(X)\approx\sigma(t)$ by applying symmetry and once again applying using lemma 2.14 to move $\pi$ "inside" the permutation to get
$$\nabla\vdash \sigma(\pi.X)\approx\sigma(t) $$

which is exactly the assumption!

Again, the only real difficulty is that the proof is working backwards, starting from the conclusion and finding stronger and stronger statements until you get the hypothesis.


Does #$P$-Completeness imply approximation hardness?

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.)

Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #P paper [2]) but, relaxing your requirement a little, there's an FPRAS due to Jerrum and Sinclair [1]. This corresponds to counting perfect matchings in bipartite graphs.

References

[1] Mark Jerrum and Alistair Sinclair, "Approximating the permanent." SIAM Journal on Computing, 18(6):1149–1178, 1989. (PDF)

[2] Leslie Valiant, "The complexity of computing the permanent." Theoretical Computer Science, 8:189–201, 1979. (PDF)

[3] Dror Weitz, "Counting independent sets up to the tree threshold." STOC 2006. (Unpublished full version: PDF.)


$O(N^2)$ solution

First of all define dominant relation for points:

  Point $d(x_d, y_d)$ is dominating point $p(x_p, y_p)$ iff $x_p \le x_d$ and $y_p \le y_d$. Also easy to see that this relation is transitive, i.e. if $a$ dominating $b$ and $b$ dominating $c$, then $a$ dominating $c$.

Let $M$ be minimum(-size) dominating subset of set $S$. Now we need to check which point will be in $M$. Let answer on the question:

  Is $p \in S$ is $M$ or not?

We have 2 cases:

$\nexists d \in S, d$ is dominanting $p$, then $p \in M$, if we will not include $p$ in $M$ we will not be able to find a point that will dominate $p$.
$\exists d \in S, d$ is dominanting $p$, then $p \notin M$, because it will be more optimal include $d$ in $M$ and exclude $p$, as every point in $A$ that is dominated by $p$ is dominated by $d$ also, but $d$ is dominating at least one more point (itself).

First case make sure that $M$ will dominate $S$, second case that $M$ is minimal among all dominating subsets.

And now we have easy $O(N^2)$ solution: for each point $p \in S$ check membership in $M$; to do that we need to check that there is no point $d \in S$ that dominating $p$.

$O(N \log N)$ solution

To construct solution with $O(N \log N)$ time-complexity, let see some example of sets $S = \{A, B, C,..., N\}$ and $M = \{N, B, I, H\}$:

To find $M$ we need to sort points in $S$ by $x$ in descending order, and if $x's$ the same by $y$ in descending order (it can be done in $O(N \log N)$, let call this sorted list $L$.

Include first point from $L$ in $M$ and remember this point as $T$.
Iterates through $L$ (let $C$ current considered point from $L$):

if $C$ is dominated by $T$ than skip $C$ and go to next point in $L$;
else include $C$ in $M$ and set $T = C$
This step can be performed in $O(N)$.


Is $\{s_0 w s_1 : s_0s_1\in L_1, w\in L_2 \}$ context free if $L_1$ and $L_2$ are?

Class is right.

The pumping Lemma is not very helpful in this setting. It is usually used to show a given language non-context-free.

As for your language, first try to understand the special case, where $L_s = \{A\}$ for a special symbol $A$, that is try to prove that the language $\{ s_1As_2 \mid s_1s_2\in L_1 \}$ is context-free whenever $L_1$ is context-free.

In the comments below, Yuval gives a hint how to perform the construction with a PDA, for the general case. Start an automaton for $L_1$. At any nondeterministic moment (once during the computation) interrupt the $L_1$ computation and push a new bottom-of-stack symbol. Then use that as a marker to simulate a PDA for $L_2$ which stops when we accept by empty stack. Remove the marker, and happily resume the computation on the second part of $L_1$.

A simple construction using CF grammars is given by Yuval in his answer.


Why do we create universal turing machines?

Theoretically, the universal Turing machine $U$ was defined to prove the undecidability of certain problems. Roughly speaking, we're talking about a machine that is able to decide what any other Turing machine decides. So assuming that Turing machines fully capture the notion of decidability, then it holds that anything that can be decided, can also be decided by $U$. Conversely, any problem that is not decided by the universal machine $U$ is considered to be undecidable.
To be more concrete, the ability of $U$ to take as input an encoding of another machine $M$ and an input $w$ of $M$, enables us (the machine $U$) to ask questions about other machines $M$. For example, a consequence of this ability is that we can ask whether $M$ halts on $w$: is there a universal machine $U$ that decides whether $M$ halts on $w$? More formally, is there a machine $U$ that decides the language $Halt_{TM} = \{ \langle M, w\rangle: M \text{ is a TM and $M$ halts on the input $w$}\}$.
One, with a diagonalization argument, can prove that the $Halt_{TM}$ is undecidable. $Halt_{TM}$ is known as the halting problem: is there a program that eventually halts and tells us whether another program (which is given as input) halts?
So, thanks to universal machines, we can ask all these interesting questions about machines, and get undecidability results.


Heuristics for space-efficient storing of Unordered Finite Sets in a DFA

It sounds like you are describing a binary decision diagram, also known as a BDD.  BDD's have been studied extensively in the literature, so you might take a look at the literature.

In particular, the question of finding the best permutation is known  as the "variable ordering" problem for BDDs.  Finding the optimal variable ordering is NP-hard.  There are some heuristics, but they don't always work.  See https://en.wikipedia.org/wiki/Binary_decision_diagram#Variable_ordering.  Probably the easiest approach is to use an existing BDD library (the standard ones will typically incorporate some variable ordering heuristics).

You might also be interested in ZDDs.


Path of maximum value with bounded cost in DAG

Consider a SUBSET SUM instance with weights $w_1,\ldots,w_n$ and target $C$. We create an instance of your problem, with the same value of $C$. There are $n+1$ nodes $v_1,\ldots,v_n$, where node $v_i$ has cost and weight $w_i$. There is an edge from $v_i$ to $v_j$ iff $i < j$.

Any directed path in this DAG corresponds to a subset of the weights $w_1,\ldots,w_n$. You are thus looking for a subset of the weights with maximal sum under the constraint that the sum is at most $C$. Thus the solution to your problem is $C$ iff the SUBSET SUM instance is a Yes instance.


Approximation Algorithm for the Unique Coverage Problem

Suppose there are $m$ elements and $n$ sets (this is the meaning of your parameter $n$). The algorithm divides the set of elements into $\log n$ classes, so one of these classes, say class $i$, contains at least $m/\log n$ elements. Lemma 3 shows that if you pick each set with probability $1/2^i$, then in expectation you uniquely cover a $1/e^2$ fraction of the elements in class $i$. Thus, you uniquely cover at least $m/(e^2\log n)$ elements in expectation. On the other hand, the optimal cover uniquely covers at most $m$ elements. Thus the approximation ratio of this algorithm is at least $1/(e^2\log n)$.


As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$.

For the sake of simplicity, let's assume that $T$ is the unique MST. (This is not required, but it is easier to reason about correctness in this case.)

Now think about what would happen if we ran Prim's on the full graph after the new vertex and edges had been added. We would start with an arbitrary single vertex and successively add edges that are adjacent to the growing tree.

Here's the key idea: each edge that is added by Prim's on the full graph will either belong to $T$, or to $E'$. If at some step we tried to add an edge in $E$ but not in $T$, then $T$ would not be a (unique) MST.

Since we know that regular Prim's would only add edges from $E'$ and $T$, these are the only edges that need to be added to the priority queue.

As Hendrick Jan said in comments, it is certainly not the case that $|V|-1$ of the edges must be from the old graph, for all of the new edges may be less than the minimum weight edge in the old graph, in which case the MST would include all of the edges in $E'$.