For all I can understand of your problem, you want to find a median
point serving as center such that half your points are north, half
south, half west, half east.

This is not a center of gravity, since distances do not seem to
matter. This can be done by computing separately the median for all $X$s and
for all $Y$s. There are no giraffe effect, or lone star effect, or other.

Computing this median $X_M$ and $Y_M$ for all $X$s and $Y$s can be done in linear time $O(n)$
where $n$ is the number of points, as indicated in wikipedia and StackOverflow.

Then for any point $(X,Y)$ you can know  whether it has more points
south (low ordinates) by checking whether $Y > Y_M$, and conversely
for more points north.

Similarly by comparing $X$ to $X_M$ you can tell whether ther are more
points east or west of point $(X,Y)$

You can get similar results along any direction.


Is there an algorithm to find all the shortest paths between two nodes?

For the $k$ shortest paths, there are algorithms; see for instance here.

Enumerating all shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths.


Sure.  Caching is a standard optimization that can be applied in many situations.  I'm not sure there's much more to say there.

The other optimization that might be useful here is to choose the order in which you test the predicates.  I would suggest using ID3 to construct a decision tree that identifies which predicates you test, and in what order.  This may reduce the number of predicate computations you need to do, to determine the type of an object.


How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$?

There are two implications involved in the correctness. Every string in $L$ can be derived by the CFG (completeness) and every string derived by the grammar belongs to $L$ (consistency). I think you want an argument to formalize the first implication by induction.

Assuming the string $x\in L$ starts with an $a$, there must be a position with letter $b$ such that the string is of the form $aubv$ such that the $\#_a(u)=\#_b(u)$. The argument I know is by counting. Read the letters in $x$ one by one, and add $1$ for each $a$, subtract $1$ for each $b$. As the number of $a$'s equals the number of $b$'s, the count starts and stops with $0$. The counts becomes $1$ after the first letter, and must drop back to $0$ at some position with a $b$. In between we have seen an equal number of $a$'s and $b$'s.

Now that $x=aubv$ with $x\in L$ and $u\in L$ it is easy to argue that also $v\in L$.


Are "TM M accepts some string of length greater than 100" and "TM M accepts some string of length at most 100" decidable?

I might be wrong ( ignore if you understand it correctly, I am beginner myself ), but I think you are misunderstanding the Rice Theorem. Broadly speaking any non-trivial property of the languages recognized by Turing machines is not decidable. A property is trivial if it holds for all or for none of the languages recognized by Turing machines. There are various posts explaining/regarding the theorem. For example I referred to the answer here How to show that a function is not computable? while learning the theorem. ( Skip to end if you only needed hint )
Coming to your case,  the languages are  $L_1=\{\langle M \rangle \;| \; \text{M accepts some string of length greater than 100} \}$ and $L_2=\{\langle M \rangle \;| \; \text{M accepts some string of length less than equal to 100} \}$
It is not difficult to see that in both the cases you are trying to decide non-trivial properties and thus both $L_1$ and $L_2$  are undecidable. As for your reasoning it is flawed as I commented, because knowing that size of a language is finite and being able to construct a Turing machine deciding it, is different from being able to decide whether an arbitrary Turing machine recognizes a language of finite size.
On a side note you could have approached the problem by first seeing that if both of the languages were decidable, the  halting problem would become decidable which we no is not true.


What is the reason of using Gaussian model for Background Modeling?

The Gaussian function is ubiquitous in statistics and many other fields. One reason is the Central Limit Theorem, which says that the means of independent identically distributed random variables themselves have a normal (Gaussian) distribution. This is why you see the bell curve in nature so often.

The Gaussian PDF may not look simple at a first glance, but it is actually very simple to differentiate and integrate. Remember that exp(x) is its own derivative and its own indefinite integral. It is also one of very few functions whose Fourier Transform can be computed analytically.

Finally, the reason Stauffer and Grimson and others used the Gaussian Mixture Model, is that it is an easy way of approximating a complicated multi-modal distribution.


does godel's incompleteness theorem shed any light on dynamic vs typed languages?

Haskell is Turing-complete.  That means, any computation that can be expressed in Clojure, can also be expressed in Haskell (and vice versa).  Consequently, there is no difference in the expressibility of the two languages.  This remains true despite the type system.

I'm not aware of any insight that Godel's incompleteness theorem offers into whether statically typed languages are "better" than untyped languages (for some unspecified definition of "better").


Solving Recurrence Relation (quicksort )

Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken as $1$ without loss of generality. Then we have
$$
\begin{align*}
T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\
&\leq 4T\left(\frac{n}{4}\right) + 2 \frac{n}{2} + n \\
&\leq 8T\left(\frac{n}{8}\right) + 4 \frac{n}{4} + 2 \frac{n}{2} + n \\
&\leq \dots
\end{align*}
$$
More generally, we get
$$
T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kn.
$$
Assuming $n = 2^k$ and $T(1) = C$, this gives
$$
T(n) \leq 2^kC + k2^k = \mathcal{O}(n\log n).
$$
You can get a lower bound in exactly the same way.


Show that problem is PSPACE-complete - path in directed graph

Given $k$ and $l$ you can check if there is a path between these nodes using DFS. DFS requires polynomial space and time. So,  that problem is in PSPACE.

Update: I'd be glad to take into account the downvoter's opinion and improve the answer.


A classical result of Lovász (On covering of graphs) states that a graph on $n$ vertices can be decomposed into at most $n/2$ paths and cycles, and so into at most $n$ paths.


Is it possible to write an HTML compiler with no mutable state?

In theory, any program can be treated as functional by treating every operation as "replace the world with a world this piece of state replaced by a different value". In practice ... this actually works pretty well.

Your code will look something like:

root_node = parse_html()

for each operation:
    root_node = root_node.replace_using_operation(operation)

For a leaf or node that you know won't be affected by this operation, replace_using_operation looks like:

fn replace_using_operation(self, op):
    return self

For the typical non-leaf case, replace_using_operation will look like:

fn replace_using_operation(self, op):
    children = new List<Node>();
    # pedantically, this is not "functional", but realistically it is.
    # if your language has generators or a iterator map function you can
    # make it purely functional, but most people find this easier to read.
    for each ch in self.children:
        children.append(ch.replace_using_operation(op))
    new_self = new Node(children)
    delete self
    return new_self

Of course, depending on what knowledge you have of the operation, you might want to perform different operations on some children. Also note that you're perfectly free to pass additional arguments (including snapshots of other branches of the tree - just remember you don't own them) or to have entirely separate replace_* functions instead of passing operation as an argument.

This code is only a very rough skeleton, after all.


Big o notation for sublinear algorithm in streaming algorithm

A function $f$ is $\log^{O(1)}N$ if there exists a constant $k$ such that $f(n) \leq \left(\log N\right)^k$ (and not $\underbrace{\log … \log}_{k\text{ times}} N$), so you were right on this point.
The notation $N^{\alpha}$, $\alpha < 1$ is NOT another notation for $\log^{O(1)}N$ but another complexity family. If you chose $0 < \alpha < 1$ and $0 < k$, $\log ^kN$ will always be $o(N^{\alpha})$.


Characterization of lambda-terms that have union types

I just want to explain why intersection types are well-suited to characterize classes of normalization (strong, head or weak), whereas other type systems can not. (simply-typed or system F).

The key difference is that you have to say: "if I can type $M_2$ and $M_1→M_2$ then I can type $M_1$". This is often not true in non-intersection types because a term can be duplicated:

$$ (\lambda x.Mxx)N → MNN$$

and then typing $MNN$ means that you can type both occurrences of $N$ but not with the same type, for example
$$M:T_1→T_2→T_3 \qquad N:T_1 \qquad N:T_2$$
With intersection types you can transform this into:
$$M:T_1\wedge T_2→T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$$
and then the crucial step is now really easy:
$$(\lambda x.Mxx):T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$$
so $(\lambda x.Mxx)N$ can by typed with intersection types.

Now about union types: suppose you can type $(\lambda x.xx)(\lambda y.y)$ with some union type, then you can also type $\lambda x.xx$ and then get for some types $S, T_1, \dots$ $$x : T_1\vee T_2 \vee \dots \vee T_n ⊢xx:S$$ But you still have to prove that for every $i$, $x:T_i⊢xx:S$ which seems impossible even is $S$ is an union type.

This is why I don't think there is an easy characterization about normalization for union types.


If $L_1 = L_2$ then $L_1 \cap \overline{L_2} = \emptyset$

While that is true, the reverse is false. The right-hand side is also true if $L_2 \supsetneq L_2$. Therefore, deciding the right-hand side does not solve equality.


There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). Perhaps one version is the original, and another is a widely known strengthening; or perhaps one version is the original, and another is the one appearing in textbooks, which is slightly weaker (since the proof of the complete theorem is too long or too difficult). Sometimes an apparently weaker version of the theorem is equivalent to the full theorem with a short proof (for example, Hilbert's Nullstellensatz).

As Raphael mentions in his comment, here you are encountering two common versions of the Master Theorem, one of which is stronger and can handle your case. If you were writing a paper, I would recommend citing a source which states (and preferably proves) the version of the theorem you use.


Is distinguishing Hadamard matrices _really_ NP-hard?

Both sources you cite are from the same author. Note the full quote:

  For identifying the equivalence of two Hadamard matrices of order $n$, a complete search compares $(2^n n!)^2$ pairs of matrices and is known to be an NP-hard problem when $n$ increases.

I don't think the author knows what NP-hard entails and confuses it with simply exponential. Further evidence of this is that he states that a complete search (an algorithm) is NP-hard, when that is a property of a problem, not an approach or algorithm.

This source from a different author similarly misuses the term NP-hard:

  The classification of Hadamard matrices of orders $n \geq 32$ is still remains [sic] an open and difficult problem since an algorithmic approach of an exhaustive search is an NP hard problem.

In fact the wording is very similar and found in a field study. It would surprise me if the source of this error wasn't the original paper(s) above being copied without thought.

Since these authors consistently seem to misunderstand the meaning of NP-hard, I think their claims (that come without proof or reference) can be safely dismissed.


Infinite Union operation of Formal Languages

Virtually every standard language class contains singleton languages, e.g. those languages containing exactly one word ($L_w = \{w\}$).

If a class containing every $L_w$ were closed under infinite union then it would contain any arbitrary infinite language $L$ since

$$
L = \bigcup_{w\in L} L_w
$$

More in general, we can write any language (finite or infinite) using an infinite union of singletons or empty languages.

$$
L = \bigcup_{w \in \Sigma^*} \{w\ |\ w\in L\}
$$

where $\{w\ |\ w\in L\}$ is $\{w\}$ when $w\in L$ and the empty language otherwise. (I wish set comprehensions had a standard notation for free and bound variables! Here, $w$ is free.)


find the shortest path between two nodes where the number of edges is minimal

Hint: Given a graph $G$, add two new vertices $s,t$, each connected to all vertices in the original graph. When does there exist a path from $s$ to $t$ of length $n+1$?


Is it possible that the halting problem is solvable for all input except the machine's code?

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ uses $H$ to determine if $M(\langle M\rangle)$ halts and, if so, $Q$ loops; otherwise, $Q$ halts. Now, $Q(\langle Q\rangle)$ halts if, and only if, it doesn't halt.

  Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself?

No. If you change the definition of the halting problem in this way, the proof still works. We don't care what happens when $H$ receives $\langle H\rangle$ as input because the contradiction comes after we give input $\langle Q\rangle, \langle Q\rangle$ to $H$.

Second, if you modified $H$ to detect that input, we could get the same contradiction by using any other machine $Q'$ that is equivalent to $Q$ in the sense that, for any input $w$, $Q'(w)$ halts if, and only if, $Q(w)$ halts. There are infinitely many of these and $H$ can't detect all of them because it's undecidable whether two Turing machines are equivalent.


Time complexity of finding predecessor for a dictionary implemented as a sorted array

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key.

But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a sorted random access datastructure.

This particular interface is, in general, more useful and more efficient than the key-based interface previously presented, since it more accurately represents the cost of iterating through the dictionaries elements. Most such interfaces do, in fact, take some kind of cursor ("iterator" in C++ parlance) as an argument and return another cursor as a result.


Maximum number of similar groups of a given size that can be made from a given array

The function
$$f:\mathbb{N}\rightarrow\{0, 1\}:f(k) =
\begin{cases}
1; &\text{if there is a solution of size $k$,}\\
0; &\text{otherwise}
\end{cases}
$$
is monoton, since if there is  no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $[1, |B|]$, and output the greatest $k$ for which there is a solution of size $k$. Thereby, we turned the problem into a decision problem with an $O(\log |B|)$ factor in the running time.

For a fixed value of $k$, a greedy solution suffices. If we have $F_i$ copies of some element $B_i$, then each set can contain at most $\left\lfloor\frac{F_i}{k}\right\rfloor$ of this element. So we have a solution of size $k$ if and only if
$$\sum\limits_{i=1}^{n} \left\lfloor\frac{F_i}{k}\right\rfloor \geq A.$$

As an exercise, try to prove that the greedy solution is optimal. The running time can be bounded in $O(|B|\log|B|).$


What are Predictive Clustering Trees in machine learning?

Clus might get you started. It uses predictive clustering trees and is described in this article, although you'll probably need a student account to get access to that article.

They have a list of publications that you should also find instructive.


How do I mathematically express a set generated using two loop variables within a single for loop?

You attempt is basically correct, assuming that the for-loop is short for nested loops. You'd usually write it like

$\qquad\displaystyle\{ (n-j)(n-k) \mid j \in \{n, \dots, 2n\}, k \in \{n, \dots, 0\}\}$.

Now we note that we can write

$k$ instead of $n-k$ (in the code, reverse the direction of the for-loop) and
$-j$ with $j \in \{0, \dots, n\}$ instead of $n-j$ with $j \in \{n, \dots, 2n\}$ (do you see why?).

So we get

$\qquad \displaystyle \{ -jk \mid j, k \in \{0, \dots, n\}\}$.

If, on the other hand, the for-loop is supposed to step j and k simultaneously, building all combinations is not what happens. Then, you'd have

$\qquad\displaystyle \{ (n-j)(n-k) \mid (j,k) \in \{ (n,n), \dots, (2n,0) \} \} $

which we can rewrite by noting that

$j \in \{n, \dots, 2n\} \iff (n-j) \in \{0, -n\}$ and
$k \in \{n, \dots, 0\} \iff (n-k) \in \{0, n\}$ and

to

$\qquad\displaystyle \{ -jk \mid (j,k) \in \{(0,0), \dots, (n,-n)\} \}$.

But now $j$ and $k$ only differ by the sign, so we can rewrite using only one variable:

$\qquad\displaystyle \{ -x^2 \mid x \in \{0, \dots, n\}\}$.


If I understand your problem correctly, it is NP-hard (and so NP-complete) since you can reduce Hamiltonian Path to it. Given an undirected graph, make it into a directed graph by splitting each undirected edge into two directed edges going in both directions, and ask whether there is a path of length $n-1$.


Let's try to figure out which words are in $L$ and which aren't. If a word $w$ contains 00 or 11 then it is certainly in $L$. Otherwise, it alternates between zeroes and ones. If it contains 0101 or 1010 then it is in $L$. We are left with the words of length at most three, that is $\epsilon,1,0,10,01,101,010$. These are the only words not in $L$. Since $L$ is cofinite, it is regular.


How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

Suppose that $P$ is a multivariate polynomial with integer coefficients. Then $P$ vanishes on all natural inputs iff it vanishes on all integer inputs. You can prove this by showing that if $P$ is not the zero polynomial then there is a natural input on which it is non-zero. This, in turn, you can prove by induction on the number of variables.

The base case is when $P$ is a univariate polynomial. In this case it is not hard to check that $P$ is non-zero for sufficiently large integer input. Suppose next that $P$ is a $(d+1)$-variate polynomial. Choose one variable $x$ which appears in some monomial of $P$, and write $P$ as a univariate polynomial whose coefficients are $d$-variate polynomials. Suppose that the highest power of $x$ that appears in $P$ is $x^n$, and that the corresponding coefficient is the $d$-variate polynomial $Q$ in the other variables. The induction hypothesis shows that there is an input on which $Q \neq 0$. Applying the base case again, we find a non-zero input for $P$.


Why is the processes address space a continuous block in RAM?

The term virtual memory applies as soon as there is a mapping from logical (process specific) addresses to physical one.  The mapping may be as simple as adding a base to the logical address to get the physical one or as complex as the segmentation followed by paging of x86.  The representation you show seems to assume the first.


Meaning of: "'If factoring large integers is hard, then breaking RSA is hard,' is unproven"

The easiest way to think about it is to think of the contrapositive.

The statement:

  if factoring large integers is hard, then breaking RSA is hard

is equivalent to the following:

  if breaking RSA is easy, then factoring large integers is easy

This statement has not been proven.

What they're saying is, assume we have an algorithm that solves factoring in polynomial time. Then we can use it to construct an algorithm that solves RSA in polynomial time.

But, there could be some other way to crack RSA that doesn't involve factoring integers. It's possible that we will find we can crack RSA in a way that doesn't let us factor integers in polynomial time.

In short, we know that RSA is at least as easy as factoring. There are two possible outcomes: RSA and factoring are of equivalent difficulty, or RSA is a strictly easier problem than factoring. We don't know which is the case.


Paths in a graph with two kinds of costs

This is NP-hard by reduction from Partition.

Given an instance of the Partition problem consisting of $n$ nonnegative integer values $x_1, \dots, x_n$, we can generate an instance of your problem as follows:

Make $n+1$ vertices $s_0, \dots, s_n$.  Let $u = s_0$ and $v = s_n$.
Make $n$ vertices $a_1, \dots, a_n$, and edges $s_{i-1}a_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}a_i) = x_i$ and $W_2(s_{i-1}a_i) = 0$.
Make another $n$ vertices $b_1, \dots, b_n$, and edges $s_{i-1}b_i$ for every $1 \le i \le n$ having weights $W_1(s_{i-1}b_i) = 0$ and $W_2(s_{i-1}b_i) = x_i$.
Also add edges $a_is_i$ and $b_is_i$ having both weights 0 for every $1 \le i \le n$.
Set $c_1 = c_2 = \frac{1}{2}\sum_{i=1}^n x_i$.

The original Partition instance has a solution if and only if the above-constructed instance of your problem has a solution.  Basically, for each number $x_i$, we must visit exactly one of the vertices $a_i$ or $b_i$, incurring a cost of $x_i$ for one of the two weights (and zero cost for the other weight).


Is there a systematic way to know when to alpha-transform free variables?

The answer here is the same as in the other question: one thing is missing here!

Your addition result should be:

$$3 + 4 = \lambda g . \lambda z . 3 g (4 g z) = \lambda g . \lambda z . 7 g z$$

Note that $g$ is now a lambda parameter, not a free variable! So now if you want to apply this to something, it'll get substituted in the same everywhere:

$$7 q r = (\lambda g . \lambda z . 7 g z) q r = q q q q q q q r$$


How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding

There's a way that neither needs to store the number of padded bits, nor - in most real life scenarios *) - add a pseudo symbol.

The idea is this: The maximum padding is 7 bits, so if after the last encoded symbol, we pad with the first bits of a symbol that is encoded as 8 or more bits, the decoder will stop in the middle of decoding when the bit stream finishes, so no extraneous symbol gets decoded.

For this to work, the total byte length of the Huffman encoded data needs to be known when decoding.

*) If there is no existing symbol of length 8 or longer, then an end-of-file pseudo-symbol needs to be created. This should be added with the least possible frequency, in order not to make the encoding of real symbols grow in length, if possible. The length of the end-of-file symbol does not matter. If it is shorter than 8 bits, it can just be repeated multiple times to pad the last byte, and if longer than 8 bits, only the first bits necessary to pad the final byte will be used.


Functorial type constructors in System F

The usual (categorical) characterization of inductive data types is as initial $F$-algebras for a functor $F$.  An $F$-algebra is a pair of a type, $A$, and a function $a : FA \to A$.  A homomorphism of $F$-algebras, $\varphi : (A,a) \to (B,b)$ is a function $\varphi : A \to B$ which satisfies $\varphi\circ a = b\circ F\varphi$.  An $F$-algebra, $(\mu F,\mathsf{in}_F)$, is initial if there exists a unique homomorphism from it to any other $F$-algebra.  This means we have a function which takes an $F$-algebra $(A,a)$ and produces a function $\mathsf{fold}_A(a):\mu F\to A$ which satisfies $$\mathsf{fold}_A(a)\circ\mathsf{in}_F=a\circ F(\mathsf{fold}_A(a))$$
The type of $\mathsf{fold}$ in System F would be $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$.  The free theorem for this (as calculated by this) specializes to
$$\forall \alpha,\beta. \forall \varphi : \alpha\to \beta.
   \forall a : F \alpha \to \alpha.
   \forall b : F \beta \to \beta.\\
    \varphi \circ a = b \circ F \varphi \implies \varphi \circ \mathsf{fold}_{\alpha}(a) = \mathsf{fold}_\beta(b)$$
which further specializes to
$$\forall \beta.
   \forall b : F \beta \to \beta.
    b\circ \mathsf{fold}_{F\beta}(Fb) = \mathsf{fold}_\beta(b)$$
and
$$\forall \beta. \forall \varphi : \mu F\to \beta.
   \forall b : F \beta \to \beta.\\
    \varphi \circ \mathsf{in}_F = b \circ F \varphi \implies \varphi \circ \mathsf{fold}_{\mu F}(\mathsf{in}_F) = \mathsf{fold}_\beta(b)$$
If we can prove $\mathsf{fold}_{\mu F}(\mathsf{in}_F) = id_{\mu F}$, then this would mean that $(\mu F,\mathsf{in}_F)$ was an initial $F$-algebra as the above equation says: "any $F$-algebra homomorphism $\varphi : (\mu F, \mathsf{in}_F)\to(B,\beta)$ is $\mathsf{fold}_\beta(b)$ and thus exists and is unique". Of course to do this we need to actually give a definition of $\mu F$, $\mathsf{fold}$, and $\mathsf{in}_F$.

By noting that $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$ is isomorphic to $\mu F \to \forall \alpha.(F\alpha\to\alpha)\to\alpha$, there's an obvious choice for both $\mathsf{fold}$ and $\mu F$: simply set $\mu F = \forall \alpha.(F\alpha\to\alpha)\to\alpha$ and $\mathsf{fold}$ to be the inverse image of $id$ with respect to that isomorphism.  Explicitly, $$\mathsf{fold} = \Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.\lambda g\!:\!\mu F.g[\alpha]a$$ All that remains is to define $\mathsf{in}_F$ and show that $\mathsf{fold}_{\mu F}(\mathsf{in}_F) = id_{\mu F}$.  The easiest way to define $\mathsf{in}_F$ is to just follow the types: $\mathsf{in}_F : F\mu F \to \forall \alpha.(F\alpha\to\alpha) \to \alpha$ so $$\mathsf{in}_F = \lambda x\!:\!F\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.a(F(\mathsf{fold}_{\alpha}(a))x)$$
This definition is particularly convenient as you may have noticed that while I've shown that if there's a homomorphism $\varphi : (\mu F,\mathsf{in}_F)\to(A,a)$ then it is $\mathsf{fold}_A(a)$, and I've shown that there is a function $\mathsf{fold}_A(a):\mu F\to A$, I haven't shown that $\mathsf{fold}_A(a)$ is a homomorphism. That is, I haven't shown $\mathsf{fold}_A(a)\circ\mathsf{in}_F = a\circ F(\mathsf{fold}_A(a))$, but with the above definitions of $\mathsf{fold}$ and $\mathsf{in}_F$ this is easily shown by normalizing. To finish, $$\begin{align}
\mathsf{fold}_{\mu F}(\mathsf{in}_F)
& = \mathsf{in}_F\circ\mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)) \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(a\circ F(\mathsf{fold}_{\alpha}(a)) \circ \mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(\mathsf{fold}_\alpha(a)\circ \mathsf{in}_F \circ \mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(\mathsf{fold}_\alpha(a)\circ \mathsf{fold}_{\mu F}(\mathsf{in}_F))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.\mathsf{fold}_\alpha(a)g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.g[\alpha]a \\
& = \lambda g\!:\!\mu F.g
\end{align}$$


Finding the k-th smallest ternary sum of elements from three different arrays

You can first sort the three arrays. In the following answer we assume these arrays are already sorted.

You can maintain a priority queue $Q$. Initially it contains only $a_0+b_0+c_0$. Then in each iteration, you pop the smallest element (say $a_r+b_s+c_t$), and add $a_{r+1}+b_s+c_t$, $a_r+b_{s+1}+c_t$ and $a_r+b_s+c_{t+1}$ (duplicates are not allowed, while it is easy to check whether a combination already exists in $Q$). Now we can claim the popped sum in the $i$-th iteration is the $i$-th smallest sum.

This algorithm takes $O(n\log n)$ time. If the given three arrays are already sorted, the time is reduced to $O(k\log k)$.

We can use mathematical induction on $i$ to prove the correctness. Suppose the $i$-th smallest sum is $a_r+b_s+c_t$, then we have the following chain:

\begin{align}
&a_0+b_0+c_0\\
\le\ &a_1+b_0+c_0 \\
\le\ &\cdots \\
\le\ &a_r+b_0+c_0 \\
\le\ &a_r +b_1+c_0 \\
\le\ &\cdots \\
\le\ &a_r +b_s+c_0 \\
\le\ &\cdots \\
\le\ &a_r+b_s+c_t.
\end{align}

For convenience, we denote by $S_0,\ldots,S_{\ell}$ these sums in the chain. Let $S_j$ be the first sum in the chain that is not popped before the $i$-th iteration. Then in the iteration that $S_{j-1}$ is popped, $S_j$ is added to $Q$ according to our algorithm. This means the sum popped in the $i$-th iteration must be no more than $S_j$, thus no more than $S_{\ell}=a_r+b_s+c_t$. By inductive assumption, the first $i-1$ smallest sums are popped before the $i$-th iteration, so the sum popped in the $i$-th iteration is exactly the $i$-th smallest sum.


Perfect matching in a bipartite regular graph in linear time

There is a classical linear time algorithm of Gabow and Kariv.

The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, you find another vertex which has unused edges, and start a new walk from there. Eventually, you will have decomposed all edges into cycles. If you're careful, you can implement this algorithm in $O(n)$; see Wikipedia for hints.

Since the graph is bipartite, all cycles have even length. Remove from each cycle every other edge to obtain a bipartite 2-regular graph. Now repeat the same process to obtain a perfect matching.

This algorithm works more generally for $d$-regular graphs whenever $d$ is a power of 2. It runs in time $O(m)$ even for non-constant $d$ (here $m$ is the number of edges). Cole, Ost, and Shirra devised an $O(m)$ time algorithm for any value of $d$, Alon devised a simple $\tilde{O}(m)$ algorithm for the same problem, and Goel, Kapralov and Khanna gave a randomized $\tilde{O}(n)$ algorithm in the same setting.


Good "serializer" ADT implementations for Synchronization

This is the first I've ever heard of serializers, and I don't know of any libraries that implement them.  From reading the course notes you pointed to and the paper by Hewitt and Atkinson referenced in the course notes, there seem to be two differences between serializers and monitors.  The first is that serializers have a more "elegant" but less efficient way of waiting for invariants to become true, the second is that a notion of reader/writer locks seems to be built-in to serializers, but wasn't built in to the original notion of monitors.

The present-day conception of a monitor largely follows Lampson and Redell. "Experience with processes and monitors in Mesa," Comm. ACM 23(2):106-117, 1980.  A monitor is an object (some private data with public methods that act as the interface to the abstract data type that the object implements) with a private mutex.  Every public method starts by acquiring the mutex, and releases the mutex on exit.  In Java this would be equivalent to marking every public method "synchronized".  In C++11 this would be equivalent to declaring a private mutex, m, and having every public method begin with a declaration std::unique_lock<std::mutex> lock(m) (an RAII-style critical section).

While in monitors the notion of condition variables is explicit, in a serializer the condition variables are implicit in the enqueue...until statement.  In a monitor you could implement something similar by associating a condition variable, cv, with each monitor.  Then the enqueue...until (<invariant-test>) statement is written cv.wait(m, []{return <invariant-test>;}) (that's C++ syntax for an anonymous function that returns true when the invariant is satisfied.)  And you would then need to make sure that you cv.notify_all() at the end of each public procedure (in C++ I would do this by subclassing unique_lock, giving it a destructor that calls cv.notify_all() in addition to releasing the mutex.)

Finally, the serializer has this bizarre join_crowd/leave_crowd operation.  It took me a while to figure this one out, but as best I've been able to determine it is a slightly weird way of implementing a reader-writer lock.  In a serializer when you want a reader-lock you join the crowd and you release the reader-lock by leaving the crowd.  (The "crowd" is the set of readers.)  I think monitors make this operation much clearer.  You can protect a monitor by a reader/writer mutex instead of a normal mutex.  The rule for when you can acquire the read lock instead of the write lock is completely clear in monitors: a method that does any mutation of the data structure must be protected with a write-lock.  Only if the method is completely immutable (const in C++ parlance) can you protect it with the read-lock.  (Note though that C++11 didn't include reader/writer locks for very good reasons, so if you wanted to do this in C++ you'd need to use Boost's reader/writer locks.)

I can hazard some guesses about why serializers never got much notice.  The first reason is that they were proposed by Carl Hewitt, who was the primary proponent of the Actor model of concurrent programming, and the Actor model uses different terminology than most people in the systems programming community are used to.  The second reason is that the serializer enqueue...until statement requires you to add a notify_all() at the end of each public method.  This in turn causes every thread waiting on an invariant to wake up and retest its invariant.  Standard condition variables allow you to put notify_one() statements only where they are actually useful, which can lead to real performance benefits.  Finally, it is not clear (to me) how to use the join_crowd/leave_crowd operation correctly, while it is at least easy to state what you must not do with a reader/writer lock (and even then reader/writer locks are one of the most common causes of bugs in multi threaded programs, so who knows what horrors would have been perpetrated in a world where serializers were standard practice.)


Typically, graph problems don't depend on the "names" of the vertices. Finding a route from Paris to Berlin doesn't get any easier or harder if you rename the cities Sirap and Nilreb, or 6 and 32, or anything else.  Indeed, in many cases, the vertices of the graph don't even have explicit names: they're just a set.  Since changing the names of the vertices makes no difference, an algorithm doesn't become less powerful by assuming that the names are $1, \dots, n$, where $n$ is the total number of vertices. That is, there is no loss of generality in doing this.

$1, \dots, n$ is a useful choice of names because computers are good at dealing with numbers and because, typically, the vertices will be stored in some kind of array anyway (an array of adjacency lists or just an adjacency matrix).  It makes sense to name the vertex after the array cell it occupies, so that the algorithm never has to worry about the distinction between "vertex $x$" and "the place where vertex $x$ is stored".


Mapping between kernel-level thread and user-level thread

I don't know the book, so what follows is only my speculation. Take it as such.

"User vs kernel level threads" might mean two different things. Carefully check your book terminology.

One interpretation is that user level threads are those who execute users' programs, while kernel level threads execute OS code. This is the interpretation you described in your question.

Another possible interpretation is the following. The OS provides processes and threads as usual. Within a OS-provided thread CPU time, user code might choose to run several subroutines concurrently. I.e., within the same OS thread, user code can execute a subroutine for 100ms, and then jump to another one for 100ms, and so on. Essentially, the user code is implementing a scheduler among several sub-threads. These "simulated" threads can be named "user level threads". In practice, some programming language implementations provide these, often called "green threads" or something similar. Note that the OS is completely unaware of those user level threads.

If at that point your book is referring to such threads, then the sentence you quoted simply means that each user thread, to be executed, must be run inside a OS provided thread. A simple implementation is to map N user level threads to a single OS thread, but running N user threads exploiting M OS threads is also possible.


Count minimum number of steps to destroy all blocks

A very similar  problem is the one of clearing the board in an instance of the Two-Dots that only has one column.
This is a single-player game played on a column of colored dots. A move consists of removing a contiguous group of at least two dots that all share the same color and then consolidating all remaining dots.
The goal is to clear the column in the fewest number of moves.
A dynamic programming algorithm for this problem is devised in section 4.2.1 of this paper.  As you suggest $C(i,j)$ is defined as the minimum number of moves needed to clear all (and only) the dots in rows $i$ through $j$.
Your problem has a couple of minor differneces:

A move always deletes a maximal (w.r.t. inclusion) monochromatic group of adjacent dots.
You can also remove a single "dot" if it doesn't match with any neighboring dot.

Here the constraint in 1) can be safely relaxed since it is the case that there is always an optimal solution for the Two-Dots problem that also satisfies such constraint.
To account for 2) you need to redefine $C(i,i) = 1$ (since a single dot can be removed with a single move) and
and, for $i<j$, $C(i,j) = \min \{C_1(i,j), C_2(i,j), 1 + C(i+1,j) \}$ where $C_1$ and $C_2$ are as in the paper and $1 + C(i+1, j)$ considers the case where the first dot is not matched with anything in an optimal solution.


Solving a problem with instance of size $n$ in $O(n)$

You are not doing anything wrong. Typically, you would want to consider the running time with respect to some variable defined in the question. In this case, you could either consider it to be linear in $n$, or to be exponential in the number of bits in the input.
When talking about formal algorithms in the context of turing machines, the running time is defined with respect to the size of the input (which in this case would result in an exponential algorithm).
In other contexts, the running time is usually calculated with respect to one of the following things:

Number of elements in the input list, if the problem's input is a list
The values given in the input (for example, $n$ in this case)
The size of the input in bits


One loop invariant is "$n_0/n$ is a power of 2 and $n \geq 1$", where $n_0$ is the original value of $n$.

The loop invariant holds initially (before the first iteration of the loop) since $n_0 = n$, and $n_0 \geq 2$. As for what happens in the loop, there are several cases:

If $n$ is odd then $n = 2k+1$ for some $k$; since $n > 1$ (otherwise the loop would have terminated), moreover $n \geq 3$, and so $n_0 = 2^t (2k+1)$ for some $t \geq 0$ and $k \geq 1$, showing that $n_0$ isn't a power of 2.
If $n$ is even then the value of $n$ in the next iteration is $n' = n/2 \geq 1$, and so $n_0/n' = 2n_0/n$ is also a power of 2.

If the loop terminates naturally then necessarily $n = 1$, and so the loop invariant guarantees that $n_0 = n_0/n$ is a power of 2.

Finally, since $n/2 < n$, the value of $n$ keeps decreasing; since always $n \geq 1$, it cannot decrease forever, i.e., the loop terminates. In fact, the running time is $\Theta(\log n)$.


Note that you're looking for a model of $\{A\}$, not of $\Gamma \cup \{A\}$ (which obviously has no finite model since all the constants need to be pairwise distinct).

Proof by contradiction would be “assume $A$ has only infinite models or no model at all”. This isn't likely to lead anywhere.

Compactness could let you find a model of some set of sentences but you'd still have to prove the existence of a finite model at some point. Anyway, there is an easy direct proof.

The smallest model of a set of sentences is the one that collapses all the ways in which the differences between elements don't matter. You don't have to go all the way to apply this intuition: you can find a smaller model by collapsing some elements that don't matter. Here, you have an infinite number of constants; to find a finite model, you'll have to map infinitely many to the same element of the model (possibly to several elements).

In particular, if some constants do not appear in your theory at all, they can all be mapped to the same model element.

   The theory is $\{A\}$. This is a finite theory, consisting of (one) finite formula. Only a finite number of constants appear in this formula. Let $C(A)$ be the set of constants that appear in $A$. Define $\mathscr{M}: c \mapsto c$ if $c \in C(A)$, $c \mapsto c_1$ if $c \notin C(A)$. Then $\mathscr{M}$ satisfies $A$.


What are the characteristics of a typeless programming language?

It depends on what happens if the programmer tries to do something like add two things with the wrong operator.  If it causes a compile-time error, the language is probably statically typed.  If it throws a runtime error complaining that the two have the wrong type, the language is probably dynamically typed.  If it doesn't throw an error and just tries to add those two things (possibly resulting in gibberish), it might be untyped.

To put it another way, it depends how those operations are implemented.  If they are implemented to keep track of the type of the variables and check that those types match what is expected, it is typed.  If it doesn't keep track of types, then it is untyped or weakly typed.

See https://en.wikipedia.org/wiki/Type_system and https://www.sitepoint.com/typing-versus-dynamic-typing/.


Proof: We first notice a few things about the graph $G(V(M' \oplus M), M'\oplus M)$:

If there exists a cycle in $G$, it will be of even length. One can easily see this because if it was of odd length, two edges of the same matching would have to be incident to the same vertex which contradicts the definition of a matching. Hence, cycles don't contribute to the difference in edges (remember, $|M'| > |M|$)
There can be paths of even and odd length. The former are not of any interest since they contain the same amount of edges from both matchings, not contributing to the difference. On the other hand, paths of odd length that are $M$-augmenting contain exactly one more edges of $M'$ than of $M$. This is because the paths edges alternate between edges of $M'$ and $M$ (also for the even paths) since no two edges of the same matching can constitute a path (as they don't share common vertices). Moreover, a paths of odd length that is $M'$ augmenting isn't of much interest since it doesn't contribute to the difference in edges.

From (2.) follows that only the $M$-augmenting paths of odd length contribute to the difference $|M'| - |M| > 0$ (those paths can also be of length 1). Since each of those paths extends the matching $M$ by one edge, there must at least exist $|M'| - |M|$ of those $M$-augmenting paths since $|M| + |M'| - |M| = |M'|$. Notice that there can be more than $|M'| - |M|$ augmenting paths of $M$ if $M'$ is not a maximum matching (why?).


Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Assuming inorder and preorder sequences are given -

1. For binary tree : Starting with the root node, traverse the preorder sequence and for each node, binary search on the given inorder sequence, separating the left and right subtrees. Recurse on the next node with the new piece of the inorder sequence. Time complexity in worst case : T(n) = T(1) + T(n-1) + O(logn) = O(nlogn)

2. For balanced binary tree : Follow the same procedure as in 1. But, since the tree is balanced, the time complexity in worst case is different: T(n) = 2T(n/2) + O(logn) = O(n)

3. For binary search tree : Traverse the preorder sequence and at each node, keep a flag (=key of the parent node). If the next node in the sequence is less than the flag, then the node gets to be the left or right child of the current node. Else, we go back to the parent recursively and apply the same procedure to it. Time complexity = O(n) since we are creating nodes in the preorder sequence.


The running time for the loop will be
$$ O\left(\sum_{i=2}^n (1+\log \min(\operatorname{lcm}(1,2,\ldots,i-1),i))\right). $$
The $1$ takes care of the arithmetic operations beyond GCD, and the other term is the running time of GCD, as given to your. The arguments to GCD are lcm and i. The value of lcm at iteration $i$ is $\mathrm{lcm}(1,2,\ldots,i-1)$, explaining the complete formula.

We can upper bound this sum by
$$ O\left(\sum_{i=2}^n (1 + \log i)\right) \leq O\left(\sum_{i=2}^n (1 + \log n)\right) = O(n\log n). $$


Binary decision diagram for a six-figure Boolean function

So finally this should be the correct solution:

The variable ordering is $x_{0} < x_{5} < x_{1} < x_{4} < x_{2} < x_{3}$. The BDD is:


Coloring graph with constraints on assortativity

Your problem is NP-hard.  Consider the special case where $M=0$; then your problem is as hard as the graph coloring problem, which is NP-hard. (Ok, with an additional constraint on the distribution function, but it will still be NP-hard.)  In particular, if $M=0$ and the graph is $C$-colorable, then the optimal solution have $|M-M(G)|=0$; if the graph is not $C$-colorable, then the optimal solution will have $|M-M(G)|>0$.  So, if we could find the optimal solution for your problem for arbitrary $M$, we could determine whether the graph is $C$-colorable by setting $M=0$, finding the optimal solution, and checking whether $|M-M(G)|=0$.
One possible approach to finding an approximate solution would be to try local search or simulated annealing.


How do set partitions get mapped by restricted growth functions

We want to define a sequence of nonnegative integers $[a_1, a_2,\dotsc, a_n]$ with $a_1=0$ such that for each $1\le i\le n$ we'll have $a_i\le 1+\max\{a_1,\dotsc, a_{i-1}\}$ (Note the last index; the definition you gave would allow $a_i$ to be anything). This condition doesn't uniquely determine $a_i$, rather it gives several possibilities in general.

Let's generate some of these sequences.

The shortest is just $[0]$
To set $a_2$ we must have $a_2\le1+\max\{0\}=1$ so $a_2$ could be either $0$ or $1$, giving us the length-2 sequences $[0,0]$ and $[0,1]$
To set $a_3$ we either start from $[0,0]$ or $[0,1]$. From $[0,0]$ we see that $a_3$ could be either $0$ or $1$, giving us $[0,0,0]$ and $[0,0,1]$. From $[0,1]$ we could have $a_3=0,1,2$, giving us $[0,1,0], [0,1,1],[0,1,2]$.

Let's look at the length-3 sequences, $[0,0,0],[0,0,1],[0,1,0],[0,1,1],[0,1,2]$, and see how they give rise to partitions of the 3-element set $\{a,b,c\}$.

$[0,0,0]$ tells us that each element lives in set 0, giving us the partition $\{a,b,c\}$.
$[0,0,1]$ tells us that elements $a,b$ live in set 0 and $c$ lives in set 1, giving us the partition $\{a,b\},\{c\}$.
Similarly, $[0,1,0]$ gives rise to the partition $\{a,c\},\{b\}$.
Similarly, $[0,1,1]$ gives us $\{a\},\{b,c\}$.
Finally, $[0,1,2]$ gives us $\{a\},\{b\},\{c\}$.

By inspection, these five growth functions give rise to all the five possible partitions of the set $\{a,b,c\}$.


Converse of pumping lemma for regular expressions

Yes, $L_>=\{0^i1^j: i > j > 0\} $ is a non-regular language.

However, it does not satisfy the pumping lemma for regular languages. Assume for the sake of contradiction that $p$ is a pumping length for $L_>$. Consider $w=0^{p+1}1^p$. Let $w=xyz$ with $|y|>1$ and $|xy|<p$. Then $y$ contains 0 only. There is no more 0's than 1's in $xy^0z=xz$. That contradicts that $p$ is a pumping length.

The most we can say is that all words in $L_>$ can be pumped up.

  If $L$ is a RE and $L'$ is not, then $LL'$ is also not a RE?

No. A simple counterexample is $L=\Sigma^*$, the language of all words while $L'$ is any non-regular language that contains the empty word such as $\{a^{n^2}\mid n\in \Bbb N_0\}$. $LL'$ is still the language of all words, which is regular.

Exercise 1. Find two languages $A$ and $B$ such that

$A$ is regular
$B$ is not regular
$A\subsetneq B$
$AB$ is regular.

Exercise 2. Find a non-regular language that satisfies the pumping lemma for regular languages.


Number of ways n can be written as sum of at least two positive integers

Let us denote the array ways after $t$ iterations of the outer loop by $w_t$. The recurrence implemented by the code is
$$
w_0(n) = \begin{cases}
1 & \text{if } n = 0, \\
0 & \text{if } n > 0.
\end{cases} \\
w_t(n) = \begin{cases}
w_{t-1}(n) & \text{if } n < t, \\
w_{t-1}(n) + w_t(n-t) & \text{if } n \geq t.
\end{cases}
$$
You can prove by induction that $w_t(n)$ is the number of representations of $n$ as a sum of natural numbers between $1$ and $t$ (without regard to order). (This is also the number of representations of $n$ as a sum of at most $t$ natural numbers.)

The code returns $w_{n-1}(n)$, which is the number of representations of $n$ as an arbitrary sum of natural numbers, other than the representation $n$.

As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $\tilde O(\sqrt{n})$, much faster than your $\Theta(n^2)$ algorithm.


Satisfiability of at least k linear equations over Z2 is NP-hard

Consider any clause $x \lor y \lor z$, and the following table:
$$
\begin{array}{c|c|c|c}
\text{satisfied literals} & [x]+[y]+[z] & [x\oplus y] + [x\oplus z] + [y\oplus z] & [x\oplus y\oplus z] \\\hline
0 & 0 & 0 & 0 \\\hline
1 & 1 & 2 & 1 \\\hline
2 & 2 & 2 & 0 \\\hline
3 & 3 & 0 & 1
\end{array}
$$
Here $[x]$ is 1 if $x$ is satisfied and 0 otherwise.

The first row sums to 0, and the rest sum to 4 (ignoring the column labeled "satisfied literals"). Can you use this to your advantage?


Confused between turing-completeness and universal approximation - are they related?

A CNN can approximate a function on a fixed number of input variables, say $n$ of them.  The set of functions on $n$ input variables isn't "Turing-complete".  For instance, a boolean function $f:\{0,1\}^n \to \{0,1\}$ is always computable, as it can be computed by a program that just hardcodes the truth-table of $f$; and the set of such functions is not "Turing-complete".

Complication: CNN's actually approximate continuous functions $f:\mathbb{R}^n \to \mathbb{R}$... but a similar point remains (at least if the input is bounded).

Turing-completeness isn't really connected to universal approximation.  For one thing: Turing-completeness talks about languages, which are subsets of $\{0,1\}^*$ and thus refers to discrete entities.  Universal approximations talks about functions $f:\mathbb{R}^n \to \mathbb{R}$, and thus refers to continuous entities.

To qualify for "universal approximation", it's enough to be able to approximate all functions of $n$ variables (for each function, there exists a neural network that approximates it), so it talks about functions on inputs of bounded length.  Turing-completeness requires the ability to compute all computable functions, which is a set of functions that has no fixed upper limit on the number of variables, i.e., it is a set of functions on inputs of unbounded length.  Universal approximation could thus, in some sense, be considered "weaker" than Turing-completeness (though strictly speaking they are incomparable; neither implies the other).


You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time.
Deciding means that it return a positive answer iff $w \in L$ and a negative otherwise.

Your approach will return a positive answer in every case. Thus your TM will accept the language $\Sigma^*$ where $\Sigma$ is the input alphabet of your TM.


How to classify simple priority queue algorithm

You can't prove an algorithm is correct without a specification what correctness means.

This algorithm isn't a priority queue.  A priority queue has two properties: pop always removes the highest-priority item; and it resolves ties (in priority) in a FIFO fashion.  Your algorithm doesn't do that; if the first 20 items in the last are all low priority, but there's a high-priority item elsewhere, a priority queue would return the high-priority item, but your algorithm returns a low-priority item.

A true priority queue is easy to implement if you only have three priority levels: you just have three ordinary queues, one for each priority level.  When pushing an item, push it onto the corresponding queue.  When popping an item, first look at the level-3 queue and pop off of it if it is non-empty; otherwise check the level-2 queue and pop from it if it is non-empty; otherwise pop from the level-1 queue if the other two queues are empty.  This achieves $O(1)$ time for all priority queue operations.

Possibly you are looking for information on process schedulers; this is studied in the operating systems area.


"So why was assembly language created?"

Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day.  It works the same as machine level code: with instructions and operands.

"Which one came first?"

Wikipedia has a good article about the History of Programming Languages

"Why am I studying about assemblers in my computer engineering class?"

  Though it's true, you probably won't find yourself writing your next
  customer's app in assembly, there is still much to gain from learning
  assembly.

  Today, assembly language is used primarily for direct
  hardware manipulation, access to specialized processor instructions,
  or to address critical performance issues. Typical uses are device
  drivers, low-level embedded systems, and real-time systems.

  Assembly language is as close to the processor as you can get as a programmer
  so a well designed algorithm is blazing -- assembly is great for speed
  optimization. It's all about performance and efficiency. Assembly
  language gives you complete control over the system's resources. Much
  like an assembly line, you write code to push single values into
  registers, deal with memory addresses directly to retrieve values or
  pointers. (source: codeproject.com)


Find the longest path from root to leaf in a tree

Ran G. gave hints towards an efficient algorithm, though perhaps he left out some details. Computing all root-leaf paths is indeed a little inefficient if you are doing work over and over again, for example, if you compute each path and then compute the length.

Perform the following recursive algorithm starting with LongestPath(root) will give
what you want. Essentially, it computes recursively the longest path for each subtree. At each node this requires building the new paths and returning the longest one.

 LongestPath(node)
   If node is a leaf, return (node,0)
   If node is not a leaf:
    For each edge (node,length,next):
       Let (p,l) = LongestPath(next)
       Let (path,len) = (p++[next], l + length)
    Return element (path,len) from previous step with largest value len

This is a combination if pseudo-code with some Haskell notation, so I hope it is comprehensible.


Does Gödel's first incompleteness theorem apply to quantifier-free arithmetics?

What you are referring to is called Baby Arithmetic ($\mathsf{BA}$) in Peter Smith's book An introduction to Gödel's Theorems.

  $\mathsf{BA}$'s language [has] one single individual constant $0$, the one-place function symbol $S$, and the two-place function symbols $+$ and $\times$.  [...] it lacks quantifiers and variables.

$\mathsf{BA}$ is complete, negation complete, and decidable.


It would be possible for that access, but nevertheless, it is not a good idea.

Even with relatively small caches, the cache miss rate of most programs is well under 10%. If a designer did what you proposed, what would likely happen is

access 1 is looked up in the cache while a memory access is started;
the cache reports the lookup is a success;
the next instruction that wants to access memory now cannot proceed. It could look up the cache, but (with your scheme) it would need to look up memory at the same time, and the memory subsystem is still working on access 1. (In fact, in has just started working on it.)

The point is that the memory subsystem cannot possibly support as anywhere near
as many lookups per second as the CPU can issue. One of the points of the cache is reduce the load on it to level it can support.


Show that approximation ratio for a convex hull algorithm is $\pi/2$

Here is a suggestion as to where to start. Suppose that the optimal solution has diameter $D$. Its optimal value is at least $2D$. If you could somehow show that the set selected by the greedy algorithm has diameter $d \leq D$, then it would follow that its value is at most $\pi d \leq \pi D$.


Given n numbers How to find out a set of numbers whose sum equal to a certain given number

One possible solution is based on knapsack.

Consider the list elements $a_1$, $a_2$, $\ldots$, $a_n$ in any fixed order.
Calculate the following boolean function: $f (k, t)$ is true if it is possible to have the sum of exactly $t$ from some subset of $a_1$, $a_2$, $\ldots$, $a_k$, and false otherwise.
Here, $k$ spans from $0$ to $n$, inclusive, and $t$ goes from $0$ to $s$: we don't need larger sums.

The calculation can be performed in $O (n \cdot s)$ using dynamic programming.
Just observe that $f (k, t) = f (k - 1, t)\mathrm{~or~} f (k, t - a_k)$: for the element $a_k$ and for every possible target sum $t$, we either drop the element from consideration, or take it into our sum.
In the latter case, we must have the chance to take it again, hence the transition to $(k, t - a_k)$ instead of $(k - 1, t - a_k)$.

Now, knowing which $(k, t)$ pairs are possible and which are not, we can recursively construct all possible answers in $O((n + s) \cdot R)$, where $R$ is the number of answers.
Indeed, descend from $(n, s)$ down to $(0, 0)$.
When we are at $(k, t)$, we can see whether $(k - 1, t)$ and $(k, t - a_k)$ are possible, and descend only into the possible branches.
As every descent takes at most $n + s$ steps, finding $R$ possible answers will happen in $(n + s) \cdot R$ time.
Actually, it will be faster since some descent paths share a common start, and some $a_k$ are greater than $1$.


The transition function in a Markov decision process

The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real.

It is somewhat strange that the range is stated as $[0,\infty)$ rather than $[0,1]$. In fact, a perhaps better way of thinking of $T$ is as a function from $A \times U$ to the set of distributions over $A$. That is, $T$ gets a state and an action, and outputs a distribution over the set of states.

The semantics of $T$ are as follows: when at state $a$ and performing action $u$, the probability of moving to state $b$ is $T(a,u,b)$. Thus for all $a \in A$ and $u \in U$ we must have $\sum_{b \in A} T(a,u,b) = 1$.


Solutions to synchronization problem need to be executed in critical section

Atomicity and mutual exclusion are different concepts that are related in that either can be used to implement the other.  The important property of mutexes and semaphores is not so much that they are atomic as they guarantee that only one process can get past a particular point at a time.  Atomic read-modify-write hardware primitives like test_and_set() and compare_and_swap() can be used to implement mutual exclusion, but it is not true that atomic hardware operations are required to implement mutual exclusion - Lamport, Leslie; The Mutual Exclusion Problem Has Been Solved, CACM 34(1):110, 1991.

Mutual exclusion requires two different primitives.  For example with a mutex you need both a try_acquire() operation and a release() operation.  You would typically use something like a test_and_set instruction to implement try_acquire(), but a simple store operation is usually sufficient to implement release().  (And test_and_set is not required to implement try_acquire() as demonstrated by Lamport, it's just easier if you have such an atomic instruction.)  Similarly, a semaphore has different down() and up() operations.

Further, most mutexes provide acquire() operations that do more than just try_acquire(), they also provide an efficient way of waiting for the mutex to become available if the try_acquire() should fail.

Conversely: a mutex can be used to implement a complex atomic operation.  Suppose you want to implement an atomic increment operation on a machine that has a mutex (perhaps implemented without atomicity by using something like Lamport's Bakery Algorithm) but you don't have direct access to any atomic instructions.  Something like the following will work:

mutex   m
integer i

atomic_increment():
  m.acquire()
  i = i+1      # only one process at a time can be at this code point
  m.release()

So neither mutual exclusion nor atomicity is more "fundamental" than the other, they are really two different things that can be used to implement each other.


Solution: Modify Johnson's algorithm

Johnson's algorithm can be used to enumerate all cycles in $G$.  It can be easily modified to enumerate only and all the cycles that contain $v$.

Johnson's algorithm works by numbering the vertices from $1$ to $n$, and classifying each cycle according to the smallest-numbered vertex in the cycle.  It first enumerate all cycles whose smallest-numbered vertex is $1$, then all whose smallest-numbered vertex is $2$, and so on.

So, here is the modification to Johnson's algorithm.  Choose a vertex numbering where $v$ receives the number $1$, and the other vertices are numbered in any order.  Run Johnson's algorithm, but only enumerate the cycles whose smallest-numbered vertex is $1$.  This will enumerate all the cycles containing $v$, and only the cycles containing $v$.

Running time

The running time of this algorithm is $O((m+n)(q+1))$, where $q$ is the total number of cycles containing $v$, $n$ is the number of vertices, and $m$ is the number of edges.  Its space consumption is $O(n+m)$.

References

Here is a full citation to Johnson's paper describing the algorithm:

[Finding all the elementary circuits of a directed graph][1]. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

See also Find the Simple Cycles in a Directed Graph.  For help understanding Johnson's algorithm, see

https://stackoverflow.com/q/2908575/781723
https://stackoverflow.com/q/2939877/781723
What is the difference in 'logical array blocked' and array list B, and what do they represent?

For pointers to implementations of Johnson's algorithm and discussion of other algorithms to find all cycles in a graph, see https://stackoverflow.com/q/546655/781723.  I don't know if there's a way to modify them to enumerate only cycles that contain $v$.


Time complexity of linear iteration bounded by logarithmic iteration?

Derp, nevermind. I observed that on the last iteration, the inner loop takes $N$ steps. On the previous iteration, the inner loop would take $\frac{N}{2}$ steps. Overall, this would take $N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$ steps, which has a geometric sum to $2N$ steps. Therefore, the loop is $O(N)$.


Is Bounded Waiting satisfied for this 2 process Solution?

In the following, I treat the first two statements acquire(lock1) acquire(lock2) as "trying", the middle two statements withdraw(from, amount) deposit(to, amount) as the "critical section", and the last two statements release(lock2) release(lock1) as "exiting".

This algorithm does not satisfy the bounded waiting property. Consider the following execution: $P_1$ and $P_2$ simultaneously execute acquire(lock1) and $P_1$ wins. $P_1$ acquires lock2 successfully, enters the critical section, and then exit by releasing locks. Now, $P_1$ and $P_2$ contend on acquire(lock1) again and $P_1$ wins again .... In this way, $P_2$ is actually starved.


For what values of A and B is the gap-VC-[A,B] problem NP-HARD?

Vertex cover has an easy $2$-approximation, so gap-VC-[$1/4,3/4$] is easy. The best unconditional hardness result is by Dinur and Safra, which gives $1.3606$ hardness. Since $(3/4)/(1/2) = 1.5 > 1.3606$, their method definitely doesn't imply gap-VC-[$1/2,3/4$]-hardness. Assuming the Unique Games Conjecture, the hardness of vertex cover is $2-\epsilon$, but this doesn't necessarily imply that gap-VC-[$1/2,3/4$] is hard - you'd have to look at the proof to determine that.

In summary, I have no idea what the correct answer is, and I'm not sure that anyone else knows which answer is correct (unconditionally).


Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$

A paper of Day gives the following hint: Show that for every $c$, every long enough string $z$ contains a prefix $x$ with $K(x) < |x| - c$.

He also gives a hint to the hint: Use the fact that a machine for computing $x$ can use both the given program $\pi$ and its length $|\pi|$, which gives it an extra $\log|\pi|$ bits of information.


Counting number of paths between two vertices in a DAG

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. For each other vertex $w\in V\setminus \{v\}; \delta^+(w)>0$ we can compute the value of $C(w)$ using the following formula
$$C(w) =\sum\limits_{x\in N^+(w)}C(x),$$
where $N(w)$ is the set of neighbors of $w$.

Note that $C(w)$ depends merely on the value of $C$ at the neighbors of $w$ and since a DAGs define a natural ordering over the vertices of the graph (namely the topological ordering), such that all neighbors of a vertex are smaller that it upon this ordering, we can compute $C(w)$ for all vertices $w$ according to their topological ordering using dynamic programming.

The correctness of the solution can be proved with induction over the diameter of the graph or over the length of the longest path from $u$ to $v$ for example.

The running time can be bounded by. $O(n+m)$ and the space complexity by $O(n)$.


What are the prerequisites for instruction pipelining to work?

The main use case for pipelining is when your latency is large, but actual work is small. You hide the latency by scheduling many operations such that the latencies overlap but the actual work does not.

It can't be used if the latencies are not independent. An example is calling people from a phone just to say "yes". The actual work is very small, the latency is very large, however your phone can only call one person at a time so you can't actually apply pipelining.

If you had multiple phones however you could start dialing the next person while the previous phone is still ringing.


Vectorization vs Asynchronous parallelism

Vectorization and asynchronous parallelism are not exactly comparable. Its like comparing apple and orange. Have a look at Difference between parallel, concurrent and asynchronous.
Vectorization uses the support for different vector instruction in modern processors. For e.g. Intel support AVX512 and AVX256 instructions. Here 512 and 256 are number of bits. So if the operand are 64 bit double values, the hardware can process 8 or 4 set of operands, parallelly.  Operation(+,-,* ...) are applied on vector inputs (8 or 4 set of operands) instead of (8 or 4 times) on  scalar (single set of operands) inputs.
for(int i=0;i<1000;i++)
for(int j=0;j<8;j++)
c[i][j]=a[i][j]+b[i][j]
On a Intel processor this code fragment will be replaced by vector instructions by the optimizing compiler . So it is equivalent to something like:
for(int i=0;i<1000;i++)  { c[i][0]=a[i][0]+b[i][0] , c[i][1]=a[i][1]+b[i][1], ..., c[i][7]=a[i][7]+b[i][7] }
This require that there should be no dependency among consecutive iteration instructions. All eight addition operation execute in parallel by the vector processing hardware of the processor on eight different operand sets. Granularity in vectorization is at the level of 'instructions'.
Asynchronous operations can happen on even single core systems. For e.g., I/O processing. Yes it is the case that, two or more set of operations happen in parallel, but it is not necessary that both are computation operation. It could a memory operation and computation Or a I/O operation and computation. Granularity in Asynchronous operation is 'set of instructions' like a program or a interrupt vector routine.


Finding potential function for dynamic array

You've already proved it! You said you were meant to bound it by $3n$ and you've bound it by $2n$. Well, $2n \leq 3n$, right?


Is there any precedence for symbols for constructing parse trees?

Operator precendences have to be specified, either in the grammar or using other means. There is no inherent precendence to rules, but you can fix one arbitrarily.


Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?

Short answer: Yes. $10100$ is included.

Long answer:

Let's go through how this particular set is constructed. First, the expression
$$
10^n
$$
(in this context) denotes a single string consisting of a $1$ followed by $n$ $0$s (so the string depends on one variable $n$). Then, the set
$$
\{10^n \mid n \ge 1\}
$$
denotes the set of strings $\{10, 100, 1000, 10000, \ldots\}$. This set can also be denoted using the Kleene-star operation as $100^*$ or $10^+$. Note that this set does not depend on $n$ -- rather, $n$ is just a dummy variable used to describe the elements of the set.

Finally, the set
$$
\{10^n \mid n \ge 1\}^*
$$
then denotes a concatenated sequence of elements of the original set, like $10100$, $1000$, $1010000010$, etc. When you use the $*$ operation, the string used each time does not have to be the same (that is, you can change $n$ for each repetition). So you can do $10$ first, then $100$, then $10$ again, etc.


Approximating a series for asymptotic upper bound

To make things a bit simpler, let us assume that we use base 4 logarithm. Following your steps, for $n = 4^k$ and $T(1) = 0$ we get
$$
\begin{align*}
T(n) &= \frac{n^2}{(\log_4 n)^2} + 4\frac{(n/4)^2}{(\log_4 n-1)^2} + 16\frac{(n/16)^2}{(\log_4 n - 2)^2} + \cdots \\ &=
\frac{n^2}{(\log_4 n)^2} \left[ 1 + \frac{1}{4(1-1/\log_4 n)^2} + \frac{1}{16(1-2/\log_4 n)^2} + \cdots \right].
\end{align*}
$$
Let us now use the series expansion
$$
\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots.
$$
Substituting this in the expression above, we get
$$
\begin{align*}
\frac{T(n)}{n^2/\log^2_4n} &= 1 + \frac{1}{4} + \frac{1}{16} + \cdots \\ &+
2\left[ \frac{1}{4\log_4 n} + \frac{2}{16\log_4 n} + \cdots \right] \\ &+
3 \left[ \frac{1}{4\log_4^2n} + \frac{2^2}{16\log_4^2n} + \cdots \right] + \cdots \\ &\approx \frac{4}{3} + \frac{8/9}{\log_4 n} + \frac{20/9}{\log_4^2 n} + \cdots
\end{align*}
$$
The error in the approximation is polynomially small: for example
$$
\sum_{k=0}^{\log_4 n-1} \frac{1}{4^k} = \frac{4}{3} - \frac{4/3}{4^{\log_4 n}} = \frac{4}{3} - \frac{4/3}{n}.
$$
The error is somewhat larger for the other summands, but still polynomially small. Taylor's theorem (or direct calculation) shows that if we truncate the series for $1/(1-x)^2$ after the term $(d+1)x^d$ then we get an error of $O(x^{d+1})$. Altogether, this shows that the following asymptotic statements hold:
$$
\begin{align*}
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + O\left(\frac{n^2}{\log_4^3 n}\right), \\
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + O\left(\frac{n^2}{\log_4^4 n}\right), \\
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + \frac{20}{9} \frac{n^2}{\log_4^4 n} + O\left(\frac{n^2}{\log_4^5 n}\right), \ldots \\
\end{align*}
$$


prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves

Apparently, the question is messed up. Either the original homework question is wrong or there is serious misunderstanding reading or copying the original homework question.

Here is the correct title and question, "How to prove the complete recursion tree for computing $F_n$ has $F_n$ leaves where $F_n$ is the $n$-th Fibonacci number?".
Here the Fibonacci sequence is defined classically by $F_1=1$, $F_2=1$ and $F_{n+1}=F_n + F_{n-1}$. Note that we exclude $F_0=0$.

The complete recursion tree for n = 5 would look like the following, where we have $5=F_5$ leaves.

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

The proposition $P(n)$ for $n\ge1$ is the complete recursion tree for computing $F_n$ has $F_n$ leaves. The base case $P(1)$ and $p(2)$ are true by definition. If we use strong induction, the induction hypothesis $IH(k)$ for $k\ge2$ is for all $n\le k$, $P(n)$ is true. It should be routine to prove $P(k+1)$ given $IH(k)$ is true.

The main point of this answer is to point out the number of leaves in the complete recursion tree for computing $F_n$, the $n$-th Fibonacci number should be $F_n$ if $F_0=0$ is not in the definition of Fibonacci sequence.  Or it should be $F_{n+1}$ if $F_0=0$ is included in the base case and $F_2$ is not included in the base case.

Here is an easy exercise to describe the general situation.

Exercise. Let $S_1, S_2, \cdots$ be a sequence defined by $S_1=a$, $S_2=b$, $S_{n+1}=S_{n}+S_{n-1}$ for some $a$ and $b$. Show that the complete recursion tree to compute $S_n$ has $F_n$ leaves, where $F_n$ is the $n$-th Fibonacci number.


To show that Vertex Cover and 3SAT is "equivalent", you have to show
that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step.

Assuming you are familiar with how the reduction is done, (if not ,refer to the document).

Since you only asked about
how this setup proves that if there exists a k-covering, then the boolean expression in CNF is satisfiable.

This is effectively the "only if" part to the proof that the two are "equivalent". So all you need to do is to show that as long as there is a k Vertex Cover for the graph constructed in the reduction, you have a satisfying solution to 3SAT.

The proof:

Since there is a k Vertex Cover, then one and only one node of each of the variable gadgets must be in the Vertex Cover. (This is because k = variables+2clauses,if you don't choose one of the variable in the variable gadget then the middle connection in the gadget is not incident, and if you choose in one gadget, you will end up with variables + 1 + 2 clauses, we'll show that you must choose 2 nodes in each clause gadget in the next sentence.)

We must have 2 nodes in each clause gadget because if we don't, then one of the connection in the clause gadget is not incident.

So set the variable corresponding to the one node that is selected in each of the variable gadgets to TRUE.

Now we have two scenarios for each of the clause gadgets:

One: A gadget can have a connection with a variable Node that is set to TRUE. In this case the gadget has a variable which is TRUE, the gadget is therefore satisfied.

Two: A gadget does not have a connection with a variable Node set to True. Then it must select all 3 of its Nodes to make the edges all incident. And that is not possible when we have a k Vertex Cover.

Hope this answers your question :))


The instance in the example is "almost" the right one, however you are right that, as given, it does not prove tightness. The instance is missing two more jobs of size $m$.

After we include these two jobs, we have 2 jobs of each size from $2m-1$ to $m+1$ and 3 jobs of size $m$ (for $n=2m+1$ jobs in total, as stated).

Under the modified greedy algorithm, the maximum load will be $4m-1$. However, one can instead schedule a job of size $2m-i$ with a job of size $m+i$ for each $i=1,2,..., \lfloor  m/2 \rfloor$, and the remaining 3 jobs of size $m$ separately on the same machine. The maximum load will then be $3m$.


Rice's Theorem for Turing machine with fixed output

A word $w$ belongs to $L_5$ if for all $x \in \{0,1\}^*$ it is the case that $M_w(w) = x$. In particular, if $w \in L_5$ then $M_w(w) = 0$ and $M_w(w) = 1$, which can't both be true. So no word belongs to $L_5$.


Variant of the knapsack problem and box stacking

This is a good dynamic programming exercise.  Here's a hint.

   Let $f(i)$ denote the maximum height that can be achieved if you have the $i$th box at the bottom.  Can you find a recursive relation to let you compute $f$ in a recursive fashion?

Think about that one.  If you get stuck, here's another hint:

   Oops, you'll probably discover that doesn't quite seem to work.  What additional information would we like to know about the box at the bottom, to enable you to find a recursive relation?  You might need to add an extra parameter to $f$, so it becomes $f(i,\text{something})$ -- what should you put as the "something"?

If you can answer those hints, you should be very close to finding a dynamic programming algorithm for the problem.


Algorithm to find a subgraph such that all of its edges has an anti edge

Here is one approach, which assumes that the adjacency lists are sorted. First, compute the reversed graph (your anti graph) in linear time. Then, compute the intersection by first merging the adjacency lists from both the original graph and the reversed graph, and then looking for edges which appear twice. This takes linear time since the lists are sorted.


How is the difficulty of any problem (not just decition problems) classified?

When we say that the optimization problem $\max \{ f(x) : x \in X \}$ is NP-hard, what we really mean is that the following decision problem is NP-hard:

  Is there an $x \in X$ such that $f(x) \geq y$?

This turns optimization into a decision problem that can be analyzed using the complexity classes you know of.

There are also complexity classes specifically for functions or for optimization problems. Some examples are:

FP, the class of functions computable in polynomial time;
APX, the class of problems that can be approximated in polynomial time, and the associated classes APX-hard and MaxSNP;
PPAD and its friends, classes of problems of the general form "given $x$, find $y$ such that $P(x,y)$", where for each $x$ we are guaranteed that such a $y$ exists.


What is beta and k parameter in Incremental Decision Tree

It appears that $\beta$ is a constant, and $k$ ranges over the integers.  See paragraph 3 of Section IV.B.
Line 1 of Algorithm 2 tells you that $\beta$ is a parameter: it says "Select parameters $\beta$ and ..."  Based on the body text in Section IV.B, presumably "if $t= \beta^k$" means "if there exists $k \in \mathbb{N}$ such that $t=\beta^k$".


Using $s^* = \epsilon + s^*s$, we have
$$
0^+(10^+0)^*0^* = \\
0^+ (\epsilon + (10^+0)^*10^+0)0^* = \\
0^+0^* + 0^+(10^+0)^*10^+00^*
$$
Similarly,
$$
0^+(10^+0)^* =
0^+ (\epsilon + (10^+0)^*10^+0) = \\
0^+ + 0^+(10^+0)10^+0
$$
Therefore it suffices to convince oneself that $0^+0^* = 0^+$ and $0^+00^* = 0^+0$.
If you want to turn it into a completely formal proof, you'll need to satisfy a list of axioms and derivation rules, but the proof will likely follow similar steps.


What progress has been made on persistent catenable deques in the last decade?

I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though.

I don't think there are any published simplifications since then. As far as I can tell, the T&M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have slowed down in the last few years.
As far as adding splitting while maintaining constant-time concat, you can look at Brodal et al's "Purely Functional Worst Case Constant Time Catenable Sorted Lists" for some references. I don't think this problem is solved yet. As far as I know, the best known result is O(lg lg n) concat and O(lg min(n - i,i)) split, from Kaplan & Tarjan's "Purely functional representations of catenable sorted lists". For the insertion and deletion case that involves lookup, see the lower bounds I mentioned in another question on ropes. For the insertion and deletion case without lookup, you can use an order-maintenance structure.


For the game you describe, take a look at binary search.  It will find the answer in logarithmically many queries: the logarithm of the search space.  In some cases interpolation search can perform even better.

For the application you mention at the end, take a look at TCP's congestion avoidance algorithm (additive increase, multiplicative decrease), as David Richerby suggests.


You seem to already know the correct procedure but you have calculated the shortest paths incorrectly.

Procedure:

Create a source vertex ($s$) and add zero-weight edges from the source to all vertices.
Compute single-source shortest path from the source to each vertex. (If a negative-weight cycle exists, there is no solution to the set of constraints.)
The constraints are solved by assignments $x_i = \delta(s, x_i)$ where $\delta(s, x_i)$ is the shortest path from $s$ to $x_i$.

x1 = -1 (s -> x3 -> x4 -> x1)
x2 = -2 (s -> x3 -> x4 -> x2)
x3 =  0 (s -> x3)
x4 = -2 (s -> x3 -> x4)

Source: See slides 6-10 of http://courses.csail.mit.edu/6.006/spring11/lectures/lec17.pdf


How to represent software code for code generation / automatic programming? How to integrate procedural and declarative knowledge?

Use some form of metamodelling :

  The outputs are represented as abstract syntax trees (ASTs):

  and constructed by a decoder with a dynamically-determined modular structure paralleling the structure of the output tree.

References

Modelling homogeneous generative meta-programming
Abstract Syntax Networks for Code Generation and Semantic Parsing
Canonical Abstract Syntax Trees
Pattern Reification as the Basis for Description-Driven Systems
Metamodelling: State of the Art and Research Challenges
DSL development based on target meta-models. Using AST transformations for automating semantic analysis in a textual DSL framework
The Machine that Builds Itself:
How the Strengths of Lisp Family Languages
Facilitate Building Complex and Flexible
Bioinformatic Models
Reasoning About LLVM Code Using Codewalker
Foundations of meta-programming


Scheme computes (- a b c) as a - b - c, i.e., strictly left to right.

It really makes no sense to talk about associativity in Scheme, which applies to how an otherwise ambiguous expression like a # b # c is to be interpreted, either as (a # b) # c or a # (b # c) (or even forbid such combinations). In Scheme no such ambiguity is possible, everything is prefix. And the function called is responsible to decide what to do with it's arguments, even if the number of arguments is variable (as in this case). It is probably more natural to work left-to-right.


What is a flow through the cut in the Ford-Fulkerson algorithm?

Consider a graph of two node $s$ and $t$ and one edge $(s,t)$ with a flow $f$, $f(s,t)=1$.

Let $S=\{s\}$ and $T=\{t\}$. Then the flow across the cut $(S, T)$ is, apparently 1. Or,
$$f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)= f(u,v)=1.$$

$\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the flow from $S$ to $T$.  $\sum_{u\in S} \sum_{v\in T}f(v,u)$ is the flow from $T$ to $S$. Their difference is the flow across $(S,T)$.

Note that all ideas above does not depend on which is source node nor which is sink node. The flow across a cut $(S,T)$ just means how much (water, current, resource, etc) is flowing from $S$ to $T$.

It happens that it is required the source node is in $S$ and the sink node is in $T$ in that part of the proof. That requirement does NOT affect the explanation above. It is just a convenience measure since in a flow network we are only interested in that kind of cut. However, it does make the situation somewhat confusing.

Now let $s$ be the source node and $t$ be sink node. So that the cut $(S,T)$ above is indeed a cut as required in the proof.

  the first part $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?

The first part $\sum_{u\in S} \sum_{v\in T} f(u,v)=f(u,v)$ is not necessarily the amount of flow entering the network at the source node, although it happens to be in the current example.

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)=0$ is not necessarily the amount of flow leaving the network at the sink node. In fact, it is not in the current example!
The amount of flow leaving the network at the sink node is
$\sum_{u\in V}f(u,t)=1$. Now, can you read the following again?

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the flow from $T$ to $S$ while $\sum_{u\in V}f(u,\text{the sink node})$ is the flow from all nodes to the sink node.
Even if $T$ consists of the sink node only, these two sums are different. The former is for flow from the sink node and the latter is for flow to the sink node. They are not only different. They are very different! They are too different.

Here are a few easy exercises about a general flow network $G=(V,E)$ with source node $s$ and sink node $t$ and a flow $f$.

Exercise 1. The amount of flow entering the network at the source node is the flow across the cut $(\{s\}, V\setminus\{s\})$.

Exercise 2. The amount of flow leaving the network at the sink node is the flow across the cut $(V\setminus\{t\}, \{t\})$.

Exercise 3. The amount of flow across any cut is the same.


Simulating a sequence of events concurrently subject to a happened-before partial order

Try identifying all dependencies between actions, then build a DAG that represents the dependencies: each vertex is an action, each edge is a dependency between two actions.  From this you can identify how to perform the maximum number of actions in parallel.  Basically, the algorithm is:

Find all the sources.  Perform all of those actions at once.
Delete all of those sources, and the edges going out of them.
Go back to step 1.

A source is a vertex with in-degree zero, i.e., with no edges entering into it.  In your context, it will be an action all of whose dependencies have been satisfied.

For instance, if action 1 must occur before action 2, which must occur before action 4, and action 3 must occur before action 4, the resulting order you get using this algorithm is: first actions 1 + 3 are performed (because they are the two sources); then action 2; then action 4.


What does "no value is acceptable" in Machine Learning hypothesis representation

Yes, that's right.  Those two hypotheses are equivalent, in that they assign the same classification to every possible instance.  Sometimes there are two different ways to represent the same thing.


Question on word probability for hierarchical softmax used in natural language processing

I have figured out my confusion.

The indicator function is $\lbrack x \rbrack$ is set to output a $-1$ or a $1$ based on the argument being false or true, respectively.

When the authors say "let $ch(n)$ be an arbitrary fixed child of node $n$", they mean arbitrary in the sense of left child or right child. But in order for our function to work, we must decide on this arbitrary decision. So, let us assume $ch(n)$ ouputs the left child of unit $n$.

Then as we go down our tree, if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $ it means the next node on our path is to the left of the parent node $n(w,j)$ and if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = -1$ it means that the next node is to the right of $n(w,j)$.

As a result, since we defined $ch(n)$ to indicate the left child, all left probabilities are calculated as $\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$ since $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $. Now we know that the probability on the right must then be   $1 -\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$. This is where I was confused since the function outputs $\sigma(-v_{n(w,j)}'^T\cdot v_{w_I})$. But let $a=v_{n(w,j)}'^T\cdot v_{w_I}$ and we can verify that $\sigma(-a)=1-\sigma(a)$.

We have $\sigma(a) = \frac{1}{1+e^{-a}}$, now observe that

$\begin{align*}
1 - \sigma(a) &= \frac{1+e^{-a}}{1+e^{-a}}-\frac{1}{1+e^{-a}}\\
&=\frac{e^{-a}}{1+e^{-a}}\\
&=\frac{1}{e^a}\times \frac{1}{1+e^{-a}}\\
&=\frac{1}{1+e^a}\\
&=\frac{1}{1+e^{-(-a)}}\\
&=\sigma(-a).
\end{align*}$

Hence the function $$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

simply multiplies probabilities along the branches corresponding to the path from the root node to the proper leaf node $w$.


How to calculate run time of insertion sort and Merge sort?

In sorting algorithms you can count the number of comparsions and consider it as run time of worst case. Just add one static counter in your code it will reflect the time complexity in a better form. Otherwise the general approach of calculating run time works fine always. Most language has a function that gives system time.


Estimating the number of distinct elements

The idea is that the hash function $h$ maps elements to random elements. Now think about the likelihood that the last $k$ digits of a random number are $0$. There's a 50/50 chance that the number ends with $0$, but it becomes more and more unlikely as you increase the number of zeroes at the end. For $000$, the probability is already down to $\frac{1}{8}$, and for ten zeroes it's around one in one thousand. So it's very unlikely that any one random number has a lot of zeroes at the end.

So what's the maximum number of zeroes can you expect when you take $d$ random numbers? It's unlikely that one of the $d$ numbers ends in loads of zeroes, but the probabilities are so that it's likely that at least one has $\log{d}$ zeroes.

If you do this with one hash function, that's a pretty rough estimator, but due to the so-called median trick you can do it a couple of times with different hash functions, use the median of the outputs, and the certainty of the result increases exponentially in the number of different hash functions (they have to be independent).


Bound covariance of two discrete random variables

This follows from Pinsker's inequality. The inequality states that for any two distributions (here, discrete) $P$, and $Q$, it holds that

$$\|P-Q\| \le \sqrt{2D_{\text{KL}}(P\|Q)} $$
where $D_{\text{KL}}(\cdot \|\cdot)$ is the Kullback–Leibler divergence and $|P-Q|$ is their total variation.

For the right-hand side, recall that for any $X,Y$ random variables with joint distribution $p_{x,y}(x,y)$ and marginals $p_x(x)$, $p_y(y)$, we have
$$I(X,Y) = D_{\text{KL}}(p_{x,y} \| p_x p_y).$$

So if we define $P = p_{x,y}$ and $Q=p_xp_y$, we obtain the desired right-hand side.

On the other hand, by definition,
$$
\begin{align}
\| P - Q\| & = \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \\
& \ge \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \cdot xy \\
& = \sum_{x,y}|p(x,y)xy - p_x(x)x\cdot  p_y(y)y|\\
& \ge \left|\sum_{x,y} \left(p(x,y)xy - p_x(x)x\cdot  p_y(y)y\right)\right|\\
& = \left|E[XY] - E[X]E[Y]\right| \\
&= |\text{cov}(X,Y)|.
\end{align}
$$
The first equality follows since $x,y \in [0,1]$ and each term is non-negative. The rest of the derivation is mostly algebra. I'm probably missing a factor 2 of the normalization of the total variation. This will give the right constant inside the square root.


Karatsuba multiplication on numbers with odd length

Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ :

$a = 2 * 10^2 + 34$
and
$b = 8 * 10^2 + 57$
; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.

It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.

Thus, $ab = 16 \cdot 10^{2*2} + 386 \cdot 10^2 +  1938 = 200538$.

I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).


Evaluating correctness of various definitions countable sets

The Wikipedia theorem is correct. More generally, if $A$ is an ordered set and there exists a surjection $g\colon A \twoheadrightarrow B$ then there exists an injection $f\colon B \hookrightarrow A$ given by $f(b) = \min g^{-1}(b)$. This is an injection since $g(f(b)) = b$.

More generally, if you assume the axiom of choice then you don't need to assume that $A$ is ordered, since the axiom of choice guarantees the existence of a function $f\colon B \to A$ satisfying $f(b) \in g^{-1}(b)$ for all $b \in B$.


Round-robin scheduling: allow listing a process multiple times?

The advantage of this approach is that round robin scheduling is very efficient, so you don't need to rely on a more complex scheduler, which would steal cycles. Introducing longer time slices for higher priority processes would decrease the responsiveness of other threads and make it harder for the OS to jump in to deal with an interrupt and so forth. Maintaining separate lists of processes would require a much more complex scheduler, which would be more expensive in terms of cycles. I don't see how there would be any problem with fairness, though. I guess the problem is that the granularity is fairly course: processes can only have integer multiples of the basic time-slice.

One negative point is that removing a process would be more costly, as each occurrence of the process would have to be removed from the queue. Perhaps this can be done lazily, though.


least significant bit,and most significant bit

"Most significant bit" is a concept that depends on the size of the machine word. If $a + b + c = 10$ and the machine word has size $64$, then the MSB is $0$. It is $1$ only if the machine word has size $2$. (Under your definition, the MSB is always $1$, unless the number is $0$, in which case it is undefined.)


Doubt with a problem of grown functions and recursion tree

Instead of having logarithms in the working, I'll substitute $n=2^m$:
$$
T(n)
= n\sum_{i=0}^{m} \left(\frac{3}{2}\right)^i
= n \frac{\left(\frac{3}{2}\right)^{m+1}-1}{\frac{3}{2}-1}
= 2n \left(\left(\frac{3}{2}\right)^{m+1}-1\right)
= 2n \left(\frac{3}{2}\right)^{m+1}-2n
$$
I believe the previous step is where you didn't expand the $2n$ into the first term. I am also not making any guess of what the master theorem or order of complexity is. Guesses should not be necessary anyways, since we just assume $T(1) \in \Theta(1)$.

Simplifying by keeping only the first term, and removing constants:

$$T(n) \in \Theta(n 1.5^{\log{n}})$$

Then, with some rearranging:

$$n 1.5^{\log_2{n}} = 2^{\log_2{n}}1.5^{\log_2{n}} = 3^{\log_2{n}}=2^{\log_2{3}\log_2{n}}=n^{\log_2{3}}$$

Thus:

$$T(n) \in \Theta(n^{\log_2{3}})$$


"Non-trivial properties" for Rice's theorem are properties of the language, not of the machine itself - for instance, it's decidable how many states a TM has, which is certainly a non-trivial property!  See Perplexed by Rice's theorem for a bit of a clarification on this.  Now, one of your two properties is a property of the language, while one is a property of the machine; this should allow you to apply Rice's theorem in one case but not the other.  Note that this isn't conclusive evidence that the other case is solvable, but it's guidance that you might try looking for a positive answer there.

(Note that this is meant to be a very loose hint just to guide you; I can certainly go into more specific details if you'd like...)


If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability?

Hint: Using XOR clauses you can express "$x = \lnot y$", and this allows you to simulate general clauses by Horn clauses.


For your particular problem, the null hypothesis is

$H_0: \mu_{manifacturer} = \mu_{competitors}$

and the alternative hypothesis is

$H_1: \mu_{manifacturer} > \mu_{competitors}$.

Basically, the null hypothesis states that there is no difference between the widget under test and the widgets made by other competitors. The alternative hypothesis states that, instead, there is a difference and the widget under test is better than the widgets made by the competitors.

Now, in your statistical significance test, you are trying to determine if you can reject the null hypothesis, i.e, if the data can be used to demonstrate for a specific confidence level that the widget made by this manufacturer may be better than the ones made by the competitors on the market. Note that I wrote "may be". If you can not reject the null hypothesis on the basis of the available data, this is interpreted by saying that statistically the data do not provide enough evidence to support your assumption that the widget under test is better.

See this Wikipedia article and this one on Statistical hypothesis testing for additional information.


The equivalence relations cover problem (in graph theory)

Although I don't know the name for such problem, I can show this problem is NP-hard.

For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph.

According to this article, finding the chromatic index for a triangle free graph is NP-complete.


They are not all equivalent.

Strings in the expression $(a^nb^n)^k$ have several (i.e., $k$) copies of the same string $a^nb^n$, whereas in $a^{n_1}b^{n_1}\dots a^{n_k}b^{n_k}$ the number of letters in each $a^{n_i}b^{n_i}$ may differ.

As $aaabbbaaabbbaaabbb$ versus $aabbaaaabbbbab$.

A shorter way of denoting words with different numbers would be
$\{ a^nb^n \mid n\ge0\}^*$.

Now check out your three languages and the given grammar.