How to evaluate the accuracy of a method for the extraction of the principal lines of the palmprint

To understand how to evaluate the accuracy of your algorithm, the best way will be to understand how the result of your algorithm will be used.

It is likely that your algorithm is just a component in a system.  After all, it's not like being able to visualize the right-hand picture is somehow a useful and important goal in its own right.  Rather, it is likely a useful stepping stone along the way to some more meaningful goal.

For instance, maybe you want to do biometric authentication of the individual, and you are planning to use the palm print for authentication, so it is helpful to first extract the three principle lines of the palm.  In that case, you will probably take the result of your transformation and then feed it in as input to the next step of processing; ultimately, the final answer of the authentication process will be "yes, accept this is the right person" or "no, this is not the right person".  So, in this example, the ultimate goal is authentication.  Therefore, I would suggest that the way to evaluate your algorithm is to evaluate how well the palmprint authentication process works, when it uses your algorithm.  We could ask about the false accept rate (if an imposter tries to authenticate, what is the probability he/she is wrongly accepted?) and the false reject rate (if the legitimate individual tries to authenticate, what is the probability he/she is wrongly rejected?).  Those are two useful metrics for evaluating the accuracy of biometric authentication, so you could evaluate how accurate the process is when using your particular transformation as one of the stages.

In general, a useful way to evaluate accuracy is to look at how the output of your transformation will be used, find some metric that is meaningful and relevant to that particular application, and then measure that metric when we use the output of your transformation as input to the next stage of processing.  Of course, this does mean that we cannot evaluate your transformation in isolation -- but you know what?  In some sense, that might be unavoidable.

There is another option, but it will require more work, and may yield results that are harder to interpret.  You could hand-label each of the input images with a manually drawn line for each of the three principle lines.  Call this the "golden reference" lines.

Then, you could manually or automatically process the output of your transformation to get the three lines (by extracting the center of each of the three broad brush strokes we can see in your right-hand image).  Call these the "algorithmically inferred" lines.

Next, you could define some metric for the distance between the golden reference lines and the algorithmically inferred lines: for instance, maybe the average distance, or the root-mean-square distance.  Finally, you could evaluate your algorithm on a reasonable test set, using this metric to quantify how close your lines are to the golden reference lines.

The problem with this approach is that it is harder to make sense of the results of such an accuracy metric.  How do you tell when your algorithm is "good enough"?  Beats me.  The only way to know that is to look at how the output of your algorithm will be used -- which gets us back to my original suggestion of evaluating your algorithm as part of a larger system.


How to generate a connected random network topology for a specific number of nodes?

I played with your demo a little bit and I suppose given a distribution of points, $\beta$ and $\alpha$ can be chosen properly so that the generated graph is connected with a high probability. A brute-force approach can be choosing the parameters using a binary search.


Are there any steps or rules to draw a DFA?

Do not confuse defining an automaton and drawing an automaton.

The drawing is intended as a support for better intuition, and because
it can often be read more easily in a single look. That is what
drawing are usually for.

However, you are supposed to actually (be able to) give a formal
definition, with the mathematical notation you learned, including
specifying the transitions (not necessarily one by one).

In your example you could say, after specifying the transitions for
the accepted string: this is completed by all transitions on terminals
not yet considered in each state, each going to $q_{die}$, and all
transitions on $q_{die}$ going back to it.  Even this can be said more
formally.

It is up to you, and to your instructor, to decide on the proper level
of formalism. A drawing is usually enough in simple cases, as it is
clear how to get the formal mathematical definition from it.

But for some more abstract problems, drawings are inconvenient, and
the mathematical notation is much more easily used. Up to you to decide.

Constructing the automaton, as drawing or as math definition, depends
on the problem at hand. There are many way, and your problem may often
be to find the right one. Much of your course will be to teach you
ways of building automata. These are only early and very simple
exercises.

One point worth remembering. In order not to clutter drawings or
descriptions, the state $q_{die}$ (or some equivalent states) is often
onitted, as well as all transitions leading only to it (the reader is
supposed to complete as I explained above).  This is convenient, but
dangerous ... some constructions or reasonnings based on automata rely
on the fact that all transitions are taken into consideration ...  and
you may forget those that do not show explicitly.


I don't know what rule Jones intended to use, but I'd guess it's something like

$$
\dfrac{
\Gamma' = \Gamma,x_1:\tau_1,\ldots,x_n:\tau_n
\\
\Gamma' \vdash e_1 : \tau_1
\\
\cdots
\\
\Gamma' \vdash e_n : \tau_n
\\
\Gamma' \vdash e : \tau
}{
\Gamma \vdash {\sf let}\ x_1=e_1;\cdots;x_n=e_n\ {\sf in}\ e : \tau
}
$$

which handles mutual recursion in groups. The rule above does not consider patterns as in x [p] = e, but it could be amended to support those as well.

I think binding groups are usually neglected since mutual recursion can be translated into non-mutual one (e.g. exploiting Bekić's theorem). However, in a real-world language it's convenient to have mutual recursion, even if from a purely theoretical point it's redundant. Hence, having a typing rule for it and an inference algorithm is still quite useful.


Checking if the graph provided by a distance matrix is a tree

We can assume all weights are positive. Otherwise we can merge all pairs of nodes with distance $0$ to get an equivalent new distance matrix (a rigorous proof would be a little verbose here so I omit it).

We can process all distances from small to large. For a distance $d$ between node $u$ and node $v$, check if $u$ and $v$ are connected (initially there is no edge thus every pair of nodes is not connected). If they are not connected, add an edge with weight $d$ between them. Finally we will get a tree and we can check whether this tree satisfies the distance matrix.

To efficiently determine whether two nodes are connected, we can maintain a disjoint-set data structure where each disjoint set represents a connected component. With this data structure, we can build the tree in $O(N^2)$. In addition, computing all-pair distances in a tree takes $O(N^2)$ time, so the total running time is $O(N^2)$, which is sufficient for the constraints.

Correctness of the Algorithm

If the algorithm reports "yes", then we indeed build a tree satisfying the distance matrix.

On the other hand, if there is a tree $T$ satisfying the distance matrix, we claim that our algorithm will build $T$ finally. We prove this claim by mathematical induction. Suppose our algorithm processes the distances of pairs $(u_1,v_1),(u_2,v_2),\ldots$ in order. Denote by $D(u,v)$ the distance between $u$ and $v$ in the distance matrix.

Our algorithm always adds the edge $(u_1,v_1)$ with weight $D(u_1,v_1)$, while there is always an edge $(u_1,v_1)$ with weight $D(u_1,v_1)$ in $T$.
Assume our algorithm agrees with $T$ for pairs $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$.

If there is an edge $(u_n,v_n)$ in $T$ (it must have weight $D(u_n,v_n)$), then $u_n$ and $v_n$ are not connected through edges $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$, which means our algorithm will add this edge by inductive assumption.

Otherwise, there is a path connecting $u_n$ and $v_n$ with length $D(u_n,v_n)$ in $T$. All of the edges in this path must have weights less than $D(u_n,v_n)$, thus are already added by our algorithm (again, by inductive assumption) when processing $(u_n,v_n)$. This means when our algorithm processes $(u_n,v_n)$, $u_n$ and $v_n$ are already connected, thus our algorithm will not add the edge $(u_n,v_n)$.

Now we have proved our algorithm indeed builds $T$, thus will report "yes".


Algorithm to find sequence of minimum moves to sort 13 card hand

This problem is harder than you might think.  Your operation of removing a block of adjacent cards and re-inserting the block somewhere else is known as a transposition.  Sorting by transpositions has been studied in the context of bioinformatics and is known to be hard.  Of course, if you limit the length to 13 cards, then efficiency becomes much less of a concern--even an exponential algorithm is likely to be fast enough.

I recommend breaking the problem into two related parts.  The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N.  This may be inefficient, but for small N, should be fast enough.

The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...).  There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing.  For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13.  Then you can call the first part above as a subroutine.


Is there a free online computer calculator that is more powerful than wolframalpha.com?

There are absolutely huge numbers involved in this calculation, no wonder you won't get the result by simple numerical computation.

However,

Let $x = 52!$ and $y=3.1536\times 10^{16}$.

A crude lower bound yields:
$$ \frac{\prod_{i=1}^y(x-i)}{x^y} \geq (1 - \frac{y}{x})^y \geq 1-\frac{y^2}{x} .$$
Putting numerical values and wandering on the safe side of approximations you get:
$$1-\frac{y^2}{X} \geq 1-10^{-34}$$.

Thus,

$$ 1-10^{-34} \leq \frac{\prod_{i=1}^y(x-i)}{x^y} \leq 1 $$.

The value you are looking for is basically $1$.


The set of values is defined for a particular reduction relation. Each reduction relation defines its own set of values.

Reduction for the lambda calculus isn't just beta reduction, there are also context rules. There are several common notions of reduction for the lambda calculus, with different sets of context rules.

In the full lambda calculus, any lambda term with a hole is a context: the context rules are
$$
\frac{M \to M'}{M\,N \to M'\,N} \qquad
\frac{N \to N'}{M\,N \to M\,N'} \qquad
\frac{M \to M'}{\lambda x.M \to \lambda x.M'}
$$
This doesn't mimic what most programming languages do. Most programming languages don't start evaluating a function's body before the function receives its arguments (this becomes especially important when evaluating the function body causes side effects). This translates into omitting the third rule above altogether: there is no reduction under a lambda. The reduction relation without that context rule is known as weak head reduction. For weak head reduction, $\lambda x. M$ is a value for any term $M$: even if $M$ could be reduced, $\lambda x. M$ can't.

Call-by-value and call-by-name are refinements of weak head reduction which also restrict the form of terms that rules can be applied to: the first two rules above, and the beta rule, have constraints on the form of $M$ or $N$.

As far as I recall, TAPL focuses on applications of the lambda calculus to programming and so focuses on weak head reduction. (λz.id z) is a value. (id (λz.id z)) isn't a value, which is why the first step reduces it (the first step is id M → id M' where M → M': it's the id in the argument that reduces, not the outer id).


Greedy algorithm for Set Cover problem - need help with approximation

You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the first $tk$ sets found by the greedy algorithm cover all but at most $n/2^t$ elements. The idea now is to pick a value of $t$ such that $n/2^t < 1$. Since the number of elements left uncovered by the algorithm is an integer, if the number $m$ of elements left uncovered satisfies $m < 1$, then in fact $m = 0$, i.e., all elements are covered.

As a side note, you can actually improve on your reasoning and show that the first $k$ sets cover at least $(1-1/e)n$ elements, and so leave only $n/e$ elements uncovered. This improves the bound from your $k\log_2 n$ to the sharp $k\ln n$, which is known to be tight (unless P=NP).


For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

One way to show this is as follows. Make another copy of your alphabet, $\Sigma'$. Let $B'$ be the language $B$ over $\Sigma'$. The language $AB'$ is regular. By intersecting this with an appropriate context-free language, we can get the language of all words $xy'$, where $|x|=|y'|$, $x \in A$, and $y' \in B'$. Finally, we can remove the tags, replacing $\Sigma'$ with $\Sigma$.

Another way is using grammars. Construct an automaton $D(A)$ for $A$ and $D(B^R)$ for the reverse of $B$. Construct a grammar whose nonterminals encode a pair of states $(q_a,q_b)$, where $q_a$ is a state in $D(A)$ and $q_b$ is a state in $D(B^R)$. There will be productions $(q_a,q_b) \to \sigma_a (q'_a,q'_b) \sigma_b$ which correspond to transitions in both automata simultaneously, and productions $(q_a,q_b) \to \epsilon$ for all pairs of final states.

Yet another way is using NPDAs. The NPDA first simulates an automaton $D(A)$ for $A$, pushing a symbol $X$ into the stack whenever it reads a letter. It then nondeterministically transitions to simulating an automaton $D(B)$ for $B$ (only when reaching a final state of $D(A)$!), popping a symbol $X$ from the stack whenever it reads a letter. You should arrange matters so that the NPDA accepts only if it reaches a final state of $D(B)$, and moreover exhausts the stack. (You can do this using a special symbol found at the bottom of the stack.)

I'll let you work out the details.


Euclidean geometry theorem proving complexity

It is common to prove the decidability of first-order Euclidean geometry by encoding the language of Euclidean geometry into the language of real closed fields and then showing that the latter is decidable. A singly-exponential space upper bound on deciding the first-order theory of real closed fields was proven in Ben-Or, Kozen, and Reif (1986). This implies a doubly-exponential time upper bound.
I believe this is the best known complexity for the decision problem for general first-order sentences in the language of real closed fields. However, I am not sure whether deciding real closed fields is equivalent (bidirectionally) to deciding Euclidean geometry, since a typical encoding of (say) the language of Tarski's axioms into the language of real closed fields only uses a small subset of the possible polynomials. So maybe first-order Euclidean geometry can be decided with lower complexity than this. It is at least PSPACE-hard, since TQBF is easily encoded into first-order Euclidean geometry.


When is ε-removal from a CFG idempotent?

Pretending the start symbol to not be nullable will lead to an $\varepsilon$-removal algorithm which is idempotent on all CFGs.  I'll now formalize and prove this.

I define a non-terminal $A$ to be S-nullable iff

It is not $S$ (the start symbol); and
It either has a rule $A \to \varepsilon$ or it has a rule $A \to X_1 \ldots X_n$ where each $X_i$ is an S-nullable non-terminal.

The $\varepsilon$-removal algorithm then becomes:

Input: A context-free grammar $G = (N, \Sigma, S, P)$.

Output: A context-free grammar $G_\varepsilon$ with no S-nullable non-terminals and $L(G_\varepsilon) = L(G)$.

Procedure: let $G' = (N, \Sigma, S, P \setminus \{(A \to \varepsilon) \in P \mid A \not= S\})$. For each non-terminal $A$ in $N$ which is S-nullable in $G$, for each rule $B \to \alpha A \beta$ in $G'$, add the rule $B \to \alpha \beta$ to $G'$ if $\alpha \beta \not= \varepsilon$ or $B = S$ ($\alpha$ and $\beta$ are strings in $(N \cup \Sigma)^*$).  Let $G_\varepsilon$ be $G'$ after all such rules have been added.

Note that one-by-one addition of rules means that if we have $S \to ABCd$ and $ABC$ is nullable and we nullify $A$, $B$, $C$ in that order, we will first add $S \to BCd$, then add $S \to ACd$ and $S \to Cd$, then add $S \to ABd \mid Bd \mid Ad \mid d$.  In other words, it should be equivalent to doing the combinatorial expansion of rules one rule at a time.

Clearly $G_\varepsilon$ has no S-nullable rules: all $\varepsilon$ rules were removed (except $S \to \varepsilon$ if it was there), and no $\varepsilon$ rules were added (except maybe $S \to \varepsilon$).  Hence no non-terminal is S-nullable directly (since $S$ is never S-nullable), and the inductive case has no basis to apply to.

Hence the algorithm is idempotent: it only adds or removes rules if there is an S-nullable non-terminal in $G$.

Also the algorithm preserves language, i.e. $L(G_\varepsilon) = L(G)$, by translation of derivations.

When we derive $A \Rightarrow \varepsilon$, we can instead avoid introducing $A$ in the first place, unless $A = S$ in which case $S \to \varepsilon$ is a rule.  In the other direction, when we derive $\alpha \beta$ we can sprinkle it with (S-)nullable non-terminals and derive $\varepsilon$ from those.

Once more, with formality:

In one direction, when $\alpha \beta$ is derived from $A$ in $G_\varepsilon$ and $A \to \alpha \beta$ doesn't occur in $G$, this is because we added this rule based on finding $A \to \alpha B \beta$ with $B$ S-nullable. Either this rule occurs in $G$, in which case derive $\varepsilon$ from $B$, or this rule was itself added; let $\alpha' \beta' = \alpha B \beta$ such that we added $A \to \alpha' \beta'$ based on finding $A \to \alpha' C \beta'$ where $C$ is S-nullable.

Every inductive step searches for a right-hand side that's longer by 1 and bounded by the length of the longest rule in $G$, hence this process terminates.  Derive $\varepsilon$ from all the back-filled non-terminals (they're all S-nullable).  This will derive $\alpha \beta$ from $A$ in multiple steps, hence $\Rightarrow^*$ is preserved (in one direction).

In the other direction, if $\varepsilon$ is derived from $A$ (in a single step) where $A \to \varepsilon$ doesn't occur in $G_\varepsilon$, we know that $A \not= S$ (because we never remove $S \to \varepsilon$) and $A$ is S-nullable; hence we must have previously derived some sentential form containing $A$ in at least one derivation step.

Let $B \to \alpha A \beta$ be the rule which introduced the $A$ in question.   If $\alpha \beta \not= \varepsilon$, we added the rule $B \to \alpha \beta$. Use this rule instead.  (Any derivations performed between introducing and eliminating $A$ can still be performed, and have identical results.)

If $\alpha \beta = \varepsilon$, then either $B = S$ or $B$ is S-nullable.  If $B = S$ we added the rule $S \to \varepsilon$; use this to replace the derivation $\gamma \underline{S} \delta \Rightarrow \gamma A \delta$ with $\gamma \underline{S} \delta \Rightarrow \gamma \delta$.

If $B \not= S$ it is S-nullable (as $B \Rightarrow A \Rightarrow \varepsilon$) and some other rule introduced $B$ to our sentential form. Apply the same replacement; the number of recursive steps is bounded above by the number of derivation steps done so far.

Unrelated observation: if in $G$ we have rules $S \to \varepsilon$ and $A \to \alpha S \beta$ then $G_\varepsilon$ will still have those rules, i.e. it will not be essentially non-contracting.  However, if $S$ never occurs on the right-hand side of any rule in $G$, then $G_\varepsilon$ will be essentially non-contracting (and $S$ will also not occur on any right-hand side in $G_\varepsilon$).


To prove that problem X is undecidable you can reduce a problem Y (which has already been proved to be undecidable) to X. In fact if Y<mX then we know that X is at least as much hard as Y is. So what you have to do is to show a function f that maps instances of problem Y in instances of problem X, so that if y is an instance of Y with answer "yes" than f(y)=x is an instance of problem X with answer "yes", and if y is an instance of Y with answer "no" than f(y)=x is an instance of problem X with answer "no".


Does classification of a problem also require the algorithm used?

No. The classification of problems into complexity classes is based on the amount of resources required to solve the problem, not the resources that some programmer decides to use. If you have a smart algorithm that solves a problem in polynomial time, and a dumb one that uses exponential time, the problem itself is in polynomial time because it can be solved within that resource bound.


It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

You need to revisit the definition of ambiguity. The point is not whether multiple derivations exist; all non-linear grammars have many derivations per word.
You have to check if there is only one left-derivation per word. Equivalently, you can check right-derivations or syntax trees.

If you think this grammar is ambiguous, prove it by giving two different syntax trees for some word.

If you think it is unambiguous, see here for how to prove that; it's often more tricky.


Design a 1-bit ALU using the smallest MUX possible

If you consider the table as a 4 input combinational circuit and try to derive an expression from the K-map you will get
$$Z_0 = cont_0'cont_1a_0'b_0'+cont_0a_0b_0'+cont_0 a_0'b_0+cont_1'a_0b_0$$

Now you can see the pattern with $a_0$ and $b_0$ so you can make a smaller circuit with a 4x1 MUX having $a_0$ and $b_0$ as selection bit.


Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

... a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

This claim is false. In fact, at least one of them (or both are) is Turing-recognizable. Assume that both the set (problem) $A$ and its complement $\overline{A}$ are not decidable. Then if both $A$ and $\overline{A}$ were recognizable (recursively enumerable) then that would mean $A$ and hence $\overline{A}$ are decidable (Theorem 4.22), a contradiction.

  ... however, the Theorem 5.30 states something different.

This theorem states that $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable. In other words, both $EQ_{TM}$ and $\overline{EQ}_{TM}$ are not Turing-recognizable (recursively enumerable). This does not contradict to the above-stated claim.

Also, pay attention that the theorem 5.30 reduces $A_{TM}$ to $\overline{EQ}_{TM}$ (not to $EQ_{TM}$ as you claim in your post)  meaning that $EQ_{TM}$ cannot be Turing-recognizable (otherwise $\overline{A}_{TM}$ would be Turing-recognizable and hence decidable).

You are right, if a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable, and since the theorem 5.30 proves that $EQ_{TM}$ is not decidable, it follows that either $EQ_{TM}$ either, $\overline{EQ}_{TM}$ or both of them are not Turing-recognizable. But this result is weaker and does not contradict to the theorem 5.30. In fact the latter (weaker) result is not necessary since the theorem already establishes the stronger result.


Why does quicksort work well with virtual memory?

The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this:

  The hardware feature on modern computers that has
  the most drastic effect on the performance of algorithms
  is paging. Quicksort actually does not perform badly in
  a virtual memory situation (see [2]) because it has two
  slowly changing "localities" around the scanning
  pointers. In some situations, it will be wise to minimize
  page faults by performing the extra processing necessary
  to split the array into many partitions (instead of only
  two) on the first partitioning stage. Of course, the programs
  should be changed so that small subfiles are
  "insertionsorted" as they are encountered, because otherwise
  the last scan over the whole file will involve
  unnecessary page faults. Many internal sorting methods
  do not work well at all under paging, but Quicksort can
  be adapted to run quite efficiently.

The reference [2] cited there for further details is:

B.S., Gustavson, F.G., and Mankin, E. "Sorting in a paging environment." Comm. ACM 13, 8 (Aug. 1970), 483-494.

As it was suggested in the other answer, in more modern terms, the same property is phrased as quicksort having good cache locality; this is said for example in the 1994 paper "AlphaSort: A RISC Machine Sort" by Nyberg et al.; summary; the full text of this is found for example in Readings in Database Systems by Hellerstein and Stonebraker.


Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?

No, this implication is not known to be true, however it is believed that those are all separate classes.  (Unfortunately, I don't have any references to back up my claim now, but I still post this as an answer to point out the following.)

You are asking whether $\text{P} \neq \text{NP}$ implies that the polynomial hierarchy $(\text{PH})$ does not collapse to its first level.

The class $\text{NP}^\text{NP}$ is also known as $\Sigma_2^P$ which is one of the classes on the second level of the polynomial hierarchy.


Time complexity of travelling salesman problem

Time complexity using the recursive method is trying all "reachable" permutations of nodes before getting back to the first node which is in worst case $O(n!)$ (if all permutations are reachable).

However using recursion with memory may reduce it to the complexity of the DP solution. But using memory in itself is the idea behind the DP solution.


If $a = \prod_i a_i$ and $b = \prod_j b_j$ then $$\frac{a}{b} \pmod{m} = \prod_i a_i \pmod{m} \times \prod_j b_i^{-1} \pmod{m},$$
where the products on the right are performed modulo $m$.


What's an intuitive distinction between semi-computable problems and noncomputable problems/functions?

Intuitively, a set of numbers is computable or decidable or recursive if there is an algorithm deciding membership for the set. A set of numbers is semidecidable or recursively enumerable (r.e.) if it has verifiable "proofs" of membership. For example, the set of programs which halt is semidecidable, since given a program $A$ and a time bound $t$, one can check that $A$ halts after at most $t$ steps. But this set is not computable, since without the time bound, we don't know how long to wait for. (That's an intuitive explanation; you can google for a proof that the halting problem is not decidable.)

There are several equivalent definitions of semidecidable sets:

A set $S$ is semidecidable if there exists an algorithm $A$ which always terminates with either YES or NO as an answer, such that $x \in S$ iff there is a witness $w$ for which $A(x,w)$ answers YES.
A set $S$ is semidecidable if there exists an algorithm $A$ such that $x \in S$ iff $A(x)$ halts.
A set $S$ is semidecidable if there is an algorithm that enumerates all members of $S$.

See if you can show that all these definitions are equivalent. You might want to look up the technique of "dovetailing".

What about the digits of $e$? We need to phrase the problem of computing the digits of $e$ in our framework. The set of digits of $e$ is the set of pairs $(k,d)$, where $d$ is the $k$th decimal digit of $e=2.71828\ldots$, i.e. $\{(0,2),(1,7),(2,1),(3,8),(4,2),(5,8),\ldots\}$. Since there is an algorithm computing the $k$th digit of $e$ (e.g. using the Taylor series $e = \sum_{k=0}^\infty 1/k!$), the set of digits of $e$ (under this encoding) is computable.

Edit: Following the OP's comment, suppose we're interested in the set of positions $n$ such that the decimal expansion of $e$ contains the digit $2$ somewhere past the $n$th digit. This set is decidable, for the following reason: either the digit $2$ appears infinitely often, or its last appearance is at digit $N$. In the first case, the set in question contains all natural numbers, in the second case it is $\{0,\ldots,N-1\}$.

The same trick works for any fixed real number. Consider, however, the set consisting of pairs $(A,n)$ such that $A$ is an algorithm that enumerates the decimal expansion of some real number, which contains the digit $2$ somewhere past the $n$th digit. This set is not computable, only semidecidable, since one can reduce the halting problem to it and vice versa (how?).


Topology vs sigma-algebra's as a framework for approximate information?

What sort of structure we get depends on what we are trying to model. Your starting assumptions may well lead to $\sigma$-algebras, but in computer science we have a certain understanding of "approximate information" which is naturally captured by topology.

Consider the following pieces of information:

no information
it is raining
it is not raining

Clearly, "no information" approximates both "it is raining" and "it is not raining". If we think of "it is raining" as an observation that can be made, then the following assymetry is cruicial: having the information "it is not raining" is not equivalent to not having the information "it is raining". That is, if you don't receive some piece of information saying that $P$ holds, then you simply don't know. It is faulty to presume that you know $\lnot P$. This is the root cause of why the $\sigma$-algebra law of complementation is not valid in this context.

Now, to motivate closure under arbitrary unions and finite intersections (but not under arbitrary intersection), we need to take a slightly different point of view. Let us say that we want verifiable information, i.e., we say that we "have information $A$" if we can reasonably verify that $A$ holds.

To verify a binary conjunction $A \land B$, we verify both $A$ and $B$.
To verify an arbitrary disjunction $\bigvee_i A_i$ it is sufficient to verify a single $A_j$.

However:

To verify an infinite conjunction $\bigwedge_i A_i$ we would have to verify all $A_i$'s, and this may not be doable algorithmically (or in a physically realistic manner).
Just because we know how to verify $A$ does not mean that we also know how to verify $\lnot A$.

Example: to verify that a given machine $T$ halts it suffices to run the machine and wait until it stops. At this point we have verified that $T$ stops. (It is irrelevant what would have happened if $T$ did not stop!) But how could we verify that $T$ does not stop? It's not in general verifiable whether $T$ stops.

Another example: "$x > 0$" is a verifiable property of computable reals, but "$x \leq 0$" is not. (Recall that $x \in \mathbb{R}$ is computable if there is an algorithm which, for any given $n \in \mathbb{N}$ gives an interval $[a_n,b_n]$ with rational endpoints such that $a_n < x < b_n$ and $b_n - a_n < 2^{-n}$.) The verification algorithm works as follows: given an algorithm for computing $x$, find $n \in \mathbb{N}$ such that $0 < a_n$. If $x > 0$ then this algorithm will terminate after a finite time, thereby confirm that $x > 0$. If $x \leq 0$ then the algorithm will run forever, but that is OK because we only need to confirm $x > 0$, we are not trying to deny $x > 0$ in case it does not hold. In contrast, we cannot confirm $x \leq 0$ because there is no algorithm which takes as input $x \in \mathbb{R}$ and terminates if, and only if, $x \leq 0$.


Relabel to front, what does topological sort according to admissible network mean?

By definition an "admissible edge" $(u,v)$ is an edge that has a residual capacity $c_f(u,v) > 0$ and the height of the vertex it enters is greater than the vertex it leaves by exactly one $h.u = h.v + 1$.

1- When the list is initialized, there exist no admissible-edges in the admissible-network because the height difference between all pairs of vertices in the network is either $|V|$ or $0$; only the source vertex has a height of $|V|$ while all other vertices has a height of $0$. Therefore, no matter which order of vertices we use, the list will be topologically sorted.

2- After relabeling a vertex $u$, there is at least on edge leaving $u$, but there are no edges entering it (according to lemma 26.28 in CLRS book p.750). Therefore, there can exist no other vertex $v$ such that $(v,u)$ is an edge and $v$ precedes $u$ in the topological order. So moving $u$ to the front of the list keeps it topologically sorted.


Can loops like this one be algorithmically transformed into multiplication

The name for this optimization seems to be induction variable elimination, there are some nice slides explaining the idea here.


How do I select a subset such that the sum and the product are greater than some value?

Thanks to Yuval for the link. I think I can prove now that the problem, called PRODUCT, is NP-hard by a reduction from EQUAL-PARTITION, the variant of PARTITION in which we require both parts to have equal sizes.

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+nM/2+A/2\right)^2$ for large enough $M$ (i.e., $M = \max_i x_i$ ) and $A=\sum_{i}x_i$ , and let $a_i=M+x_i$ for all $i$ and $b_i=M+2A/n-x_i$ for all $i$.

This is a polynomial time reduction.

Now let us prove that EQUAL-PARTITION is solved $\iff$ PRODUCT is solved.

"$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that
$$
\sum_{i\in S}x_i=\sum_{i\in S'}x_i=A/2,
$$
where $S\cup S'=\{1,\ldots,n\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$.
Now take the solution to PRODUCT to be $S$. We have
\begin{align}
&\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\
\iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\
\iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\left(1+nM/2+A/2\right)\left(1+nM/2+A/2\right)=\left(1+nM/2+A/2\right)^2\\
\end{align}
"$\Leftarrow$" Suppose that PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that
\begin{align}
\require{overset}
&\left(1+\sum_{i\in S}a_i\right)\left(1+\sum_{i\in S}b_i\right)\geq\Delta\\
\iff&\left(1+\sum_{i\in S}(M+x_i)\right)\left(1+\sum_{i\in S}(M+2A/n-x_i)\right)\geq\Delta\\
\iff&\left(1+nM/2+\sum_{i\in S}x_i\right)\left(1+nM/2+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\left(\alpha+\sum_{i\in S}x_i\right)\left(\alpha+A-\sum_{i\in S}x_i\right)\geq\Delta\\
\iff&\alpha^2+\alpha A+A\sum_{i\in S}x_i-\left(\sum_{i\in S}x_i\right)^2\geq\Delta\\
\iff&\left(\sum_{i\in S}x_i\right)^2-A\sum_{i\in S}x_i+\Delta-\alpha^2-\alpha A\leq 0\\
\iff&X^2-AX+\Delta-\alpha^2-\alpha A\leq 0\\
\overset{(a)}{\iff}&X^2-AX+\Delta-\alpha^2-\alpha A= 0\\
\iff&X= A/2\\
\end{align}

Finally, PRODUCT is NP-hard.


Means that $|L^n|$ is the number of words in $L$ of length $n\in \mathbb{N}$ letters from $\Sigma$.

Actually, $L^n$ consists of the words that are composed of $n$ copies of words from $L$. The precise lengths of these words differ.

This exercise starts however with a very specific set $L$, it consists of all words of length 1 or 2. That means that $L^2$ consists of all words of length 2,3 or 4. (No need to verify in how many ways that can be done.) And this are 4+8+16 = 28 strings, exactly like you claimed.

This can be generalized for $L^n$.


Why multiple return values is not a common thing?

Functions are traditionally thought of as returning a single value - in math. Of course several values form a tuple, but oftentimes in math we are dealing with real-valued functions. I suspect that this origin of functions is the reason why multiple return values are not so common. That said, it's easy to emulate them in several ways (by returning a tuple, or by having several output parameters, i.e. ones passed by reference), and some common modern languages (such as Python) natively support this construction.


How to apply the substitution method to n/2?

You're entirely correct - if all you prove is $T(1)$ and $T(n/2) \Rightarrow T(n)$, then you prove that $T(n)$ holds for all powers of $2$. One way to fix that is to prove $T(n)$ for all odd $n$, but that defeats the idea of induction. Instead, usually one actually proves the stronger $T(\lfloor n/2 \rfloor) \Rightarrow T(n)$ or $T(\lceil n/2 \rceil) \Rightarrow T(n)$, and both are enough to deduce $T(n)$ for all $n$.

In many cases, if you can prove $T(n/2) \Rightarrow T(n)$ then you can also prove the stronger claims, but it's technically more awkward. So instead of dealing with this mess, you are only shown the weaker claim. The "interesting" ideas are found already there, and to prove the stronger claim requires just working harder but no new ideas (other than routine tricks used for handling floors and ceilings).


Efficiently finding the maximum pairwise GCD of a set of natural numbers

Solution 1
Time Complexity: $\mathcal{O}(n\sqrt{\max(s_i)})$
Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each $s_i$, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}[u]$ by one. The greatest GCD shared by two elements in $S$ will be the greatest $u$ where $\texttt{cnt}[u] > 2$.
For each $s_i$, we only need to check up to $\sqrt{s_i}$ for its divisors, so the complexity is $\mathcal{O}(n\sqrt{\max(s_i)})$.
Solution 2
Time Complexity: $\mathcal{O}(\max(s_i)\log(\max(s_i)))$
Given a value $x$, we can check whether there exists a pair with GCD equal to $x$ by counting all the multiples of $x$ in $S$ and checking whether that count is at least 2.
With that information, loop through all possible values of $x$ and keep the maximum one with at least two multiples in $S$. This works in $\mathcal{O}(\max(s_i)\log(\max(s_i)))$ time since
$$
\sum_{x = 1}^{\max(s_i)} \frac{\max(s_i)}{x} \approx \max(s_i)\log(\max(s_i)).
$$


Why does universe level restriction behave differently between inductive family and parameterized inductive type without axiom K in agda

Normally, Agda does an analysis to determine that your indexed type is equivalent to a parameterized type. Essentially, since A occurs in the result type, knowing that l : List A tells you what type A is 'stored' in the value l. The value is known, which means that tricks that involve embedding a universe into a small type within said universe to cause a paradox will not work.
However, the above reasoning basically presumes K for the universe. Really all we can say is that knowing the type List A lets us know that the stored type is equal to A, but without K, we don't know that there are no non-trivial equalities between types. I'm not sure if there is an example of how this extra degree of freedom would allow a paradox to be written, but even if no example is known, it is safer to require the larger size than to assume that the small size is consistent.


Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A

You have a reduction, but you don't know what size the new problem will be.

Say you have an instance of problem A of size n. And you can reduce it to an instance of problem B in time O (n^2). If you can reduce it to an instance of size $O(N^{1/2})$ then you are fine: You took O (N^2) for the reduction, and $O(N^{3/2})$ to solve the instance of B.

If you reduce the instance of problem A to an instance of size O (n log n) of problem B, then you will take O (n^3 log^3 n) to solve the instance of B.

So the time for the reduction and the time for solving B are not enough. You need to know the size of the new problem as well. (Of course you can't create an instance greater than O (n^2) in O (n^2) time, so the worst case is O (n^6), but it could be much better).

The answer that was given (O (n^3)) is definitely wrong. It doesn't follow from the information you were given.


Highly colored vertices in greedy coloring imply existence of subtrees

Let us prove the following claim by induction.

Let $T$ be a colored rooted tree in which each color appears at most once, and the colors of the children of a node are smaller than the color of the node.
Let $G$ be a greedily colored graph, and let $v$ be a vertex whose color is the same as the color of the root of $T$. Then we can embed $T$ into $G$ in such a way that the root gets mapped to $v$ and the colors of all nodes match.

If $T$ consists of a single node, this is clear. Otherwise, let $T_1,\ldots,T_m$ be the subtrees rooted at the children of the root of $T$. Since the colors of the roots of $T_1,\ldots,T_m$ are distinct and smaller than the color of the root of $T$, the node $v$ must have distinct neighbors $v_1,\ldots,v_m$ whose colors match the colors of the roots of $T_1,\ldots,T_m$. Inductively, we can embed $T_1,\ldots,T_m$ into $G$. Since all colors in $T$ are distinct, the embeddings are disjoint, and so can be put together to construct the desired embedding of $T$.
To derive your claim from this one, you need to show that every tree of size $k$ can be colored according to the prescriptions of this claim. You can use BFS to accomplish that.


How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

Let $S(n) = T(2^n)$. Then
$$
S(n) = T(2^n) = 4T(2^{n/2}) + n^2 = 4S(n/2) + n^2.
$$
You can solve this recurrence using the master theorem, and then use $T(n) = S(\log n)$ to obtain a solution for the original recurrence.


The main idea of the algorithm is to find a way to multiply two $n\times n$ matrices with less than $n^3$ "essential" multiplications (multiplications of two elements of the matrices). This forms part of a larger theory, algebraic complexity theory. Here are a few highlights:

Every algorithm for multiplying two matrices can be formulated (at a small loss) as a bilinear algorithm: you form some linear combinations $\alpha_1,\ldots,\alpha_k$ of entries of the first matrix, some linear combinations $\beta_1,\ldots,\beta_k$ of entries of the second matrix, compute $\gamma_i = \alpha_i \beta_i$, and then every entry of the product matrix is a linear combination of the $\gamma_i$.
This can be formulated as computing the tensor rank of the matrix multiplication tensor $\langle n,n,n \rangle = \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n x_{ij} y_{jk} z_{ik}$. The tensor rank is similar to the more familiar matrix rank, and corresponds to the number of "essential" multiplications ($k$ in the preceding example).
Any non-trivial bound on $\langle n,n,n \rangle$ for any $n$ translates to a non-trivial matrix multiplication algorithm for all $n$, via the same recursive approach as Strassen's algorithm (this approach is also known as tensorization). There are several extensions, culminating in Schönhage's asymptotic sum inequality.
The asymptotic sum inequality can handle identities involving disjoint sums of matrix tensors (in plain English, ways of multiplying several matrices at once using fewer "essential" multiplications than the trivial algorithm uses), and can even handle "approximate" identities (border rank). Strassen came up with another method (the laser method) that can handle non-disjoint sums, and this led to the Coppersmith-Winograd algorithm and its descendants, which is where things stand today.


Implement multi-fragment heuristics for the traveling salesman problem

there are almost no other information regarding this algorithm online
  [...]
  I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

I invite you to read my paper "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" appeared in the Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016) pp 278-287. DOI: 10.1007/978-3-319-52941-7_28.

You'll find a pseudo-code of the algorithm, which is similar to the "usual definition". It's explained with some examples of a small instance.
The paper also presents briefly other tour construction methods and gives experimental results for the Multi-Fragment algorithm and a comparative study to show the effectiveness of this method.

  If the first description is correct, I'm actually not understanding it
  fully and how could I implement it in practice.

It's correct but maybe a little bit hard to explain. The main idea is to move columns and rows following the criteria such that we can read the constructed tour from the $n−1$ cells contiguous to the diagonal {D[1][0],D[2][1],... D[n][n-1]}.

  In the first description, they mention the n−1 cells contiguous to the diagonal, but of course we have 2 of this n−1 cells, one in the left triangular matrix (currently from the top to the bottom 3,1,5) and one in the upper one (1,7,0). Is it ok to choose one arbitrarily?

The distances matrix in the Traveling Salesman Problem (TSP) is symmetric $(D[i][j]=D[j][i])$, we may consider only the upper/lower triangular portion of the matrix $D$.
There is another variant of the TSP which is the Asymmetric TSP.


How DMA improves I/O operation efficiency?

The DMA engine doesn't grab the bus for the duration of the whole transfer, only while specific data is being transferred. Yes, that means CPU acces to memory is hampered, but not shut off completely. The CPU can also work with data from its cache in the meantime.


About randomness and minmax algorithm with alpha beta pruning

It's neither faster nor slower, since it depends on your order. Your order might be the best possible order, in which case randomness hurts; or it might be the worst possible order, in which case randomness helps.

If you want to guarantee not hitting a worst case behavior, you can use randomness. But it might be better to choose the order heuristically using less than full randomness.


How do I manage flow control with no ELSE statement? (on Turing machine)

The following code should work:

whileNot read #
    while read 1
        write 0
        goRight
    while read 0
        write 1
        goRight

As for implementing IF-THEN-ELSE in general, it depends on the exact semantics of your programming language, which you haven't specified.


Algorithms for logical synthesis of multiple output bits?

as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function construction optimization is a very broad area handled by EE type papers/ applications/ algorithms, there are very many published. the general topic is "logic synthesis". there is also a very broad array of software built for this purpose both commercial and public domain. here is an example of a relatively recent survey of algorithms and also a technique of using known/ previously computed circuits in a library-like context. this paper is useful here in that it refs many of the top systems in use and gives a consolodated view that you seem to be asking for in particular.

Lazy Man’s Logic Synthesis / Yang, Wang, Mishchenko


Let's have a look at your grammar:

$\qquad \begin{align}
X &\to aE \mid IXE \mid (X)E \\
E &\to IE \mid BXE \mid \varepsilon \\
I &\to \text{++} \mid \text{--} \\
B &\to \text{+} \mid \text{-} \mid \varepsilon
\end{align}$

Note that $X$ does not need left-factoring: all rules have disjoint FIRST sets¹.
If you want to make this obvious, you can drop $I$ and inline it:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid BXE \mid \varepsilon \\
B &\to \text{+} \mid \text{-} \mid \varepsilon
\end{align}$

Similarly, we can inline $B$:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid XE \mid \varepsilon
\end{align}$

Now we see that we actually have to do left-factoring on $E$: we have obvious conflicts, and we get additional conflicts via $XE$. So, let's inline $X$ once at $XE$:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid aEE \mid \text{++}XEE \mid \text{--}XEE \mid (X)EE \mid \varepsilon
\end{align}$

And now we can left-factor as easily as in your example:

$\qquad \begin{align}
X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\
E &\to \text{+}P \mid \text{-}M \mid aEE \mid (X)EE \mid \varepsilon \\
P &\to \text{+}E \mid XE \mid \text{+}XEE \\
M &\to \text{-}E \mid XE \mid \text{-}XEE
\end{align}$

By now we can see that we are not getting anywhere: by factoring away $\text{+}$ or $\text{-}$ from the alternatives, we dig up another $X$ which again has both $\text{+}$ and $\text{-}$ in its FIRST set.

So let's have a look at your language. Via

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^* aI^n E \Rightarrow aI^nBXE$

and

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^* aI^n E \Rightarrow aI^nIE$

you have arbitrarily long prefixes of the form $+^+$ which end differently, semantic-wise: an LL(1) parser can not decide whether any given (next) $\text{+}$ belongs
to a pair -- which would mean choosing alternative $IE$ -- or comes alone -- which would mean choosing $BXE$.

In consequence, it doesn't look like your language can be expressed by any LL(1) grammar, so trying to convert yours into one is futile.

It's even worse: as $BXE \Rightarrow BIXEE \Rightarrow^* BI^n X E^n E$, you can not decide to chose $BXE$ with any finite look-ahead. This is not a formal proof, but it strongly suggests that your language is not even LL.

If you think about what you are doing -- mixing Polish notation with unary operators -- it is not very surprising that parsing should be hard. Basically, you have to count from the left and from the right to identify even a single $B$-$\text{+}$ in a long chain of $\text{+}$. If I think of multiple $B$-$\text{+}$ in a chain, I'm not even sure the language (with two semantically different but syntactically equal $\text{+}$) can be parsed deterministically (without backtracking) at all.

That would be the sets of terminals that can come first in derivations of a non-terminal/rule alternative.


Error in pivot selection algorithm for merge phase [Sorting]

The "Algorithm 1 Pivot selection" of that paper is rather sloppy. The critical mistake is, as you have noted, "the while loop in the algorithm is exited too early due to the stride being reduced down to zero before the correct pivot element has been found".
There are two other drawbacks.

The condition, a[len(a) − pivot − 2] < b[pivot + 1] is superfluous since it is implied by a[len(a) − pivot − 1] < b[pivot].
It does not handle the situation where there are equal elements in the array.

To address that critical mistake, make sure that the stride is always greater than 0. To prevent out-of-bounds exceptions, extreme boundary cases should be specially handled beforehand. To handle equal elements, equal signs can be included at some comparisons.
Here is a correct algorithm in C++ that selects the desired pivot, following the pseudocode in the paper with the aforementioned modifications.
// Return a pivot so that a[size-pivot:size] and b[0:pivot] should
// be swapped. If 0 is returned, no elements should be swapped.
// It is assumed that vector a and b are sorted of the same size.
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b) {
  size_t size = a.size();

  if (b[0] >= a[size - 1]) return 0;
  if (a[0] >= b[size - 1]) return size;

  size_t pivot = size / 2;
  size_t stride = std::max(1, pivot / 2);
  while (true) {
      if (a[size - pivot - 1] <= b[pivot]) {
          if (a[size - pivot] > b[pivot - 1]) return pivot;
          else pivot = pivot - stride;
      } else {
          pivot = pivot + stride;
      }

      stride = (stride + 1) / 2;
  }

  return pivot;
}

Note that the method above requires the size of a is equal to that of b. Otherwise, a few more lines of code are needed.
If you are not required to stick to the pseudocode in that paper, which is not very good anyway, please check another version of my answer, where I use my preferred version of binary search to select the desired pivot.


The answer to your question can be infered from the wWikipedia page on
"Standard RAID levels".

Parity is just one simple case of techniques for error detection, and the name
seems to be used here to stand for various techniques of error
detection and correction.

The idea of dedicated vs distributed parity, is related to whether the
redundancy of information is on a special dedicated disk or whether it
is distributed over all disks of the RAID system.

This does not apply to RAID 1 where redundancy is achieved by simple
duplication of Data.

In the case of RAID 3 (and apparently RAID 2), data is striped (read
"spread" for faster access) over several disk why the redundancy data
(parity bytes or bits) is in a separate dedicated disk.

In the case of RAID 5, the redundancy is spread over all the disks and mixed into the original base data
(distributed parity) so that the original data can be retrieved
from any set of n-1 disks, when any one of the n disks fails. The
content of the failed disk can be recomputed from the n-1 others.

Distributed parity seems to be preferred to dedicated parity, though the
wikipedia page is not really clear as to why. My own suspicion is that
it allows for more effective error correction than dedicated parity, which keeps the original data and the redundancy (parity) data separate.
But this should be checked.


How to reduce the low-rank matrix completion problem to integer programming?

Simplifying the problem:

  Given

  a positive integer $r$
  positive integers $m, n \geq 2$
  a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)

  determine whether it is possible to complete the given partial matrix $\mathrm A$ with values in $\{0,1\}$ such that the resulting completed matrix has rank at most $r$.

Let us consider an example.

Example

Let $r = 2$, $m = n = 3$ and

$$\mathrm A = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & *\end{bmatrix}$$

Visual inspection of partial matrix $\mathrm A$ tells us that if the unknown $(3,3)$ entry is $0$, then the rank of the completed matrix is $2$. However, it would be nice not to have to rely on visual inspection.

If the rank is at most $2$, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. From the $(1,1)$ entry, we obtain the equation

$$(u_{11} \cdot v_{11}) \oplus (u_{12} \cdot v_{12}) = 1$$

where addition and multiplication are done over the finite field $\mathbb F_2$. Translating the equation above to propositional logic, we obtain

$$\Phi_{11} := \mbox{Xor} \left( u_{11} \land v_{11}, u_{12} \land v_{12} \right)$$

If $a_{ij} = 1$, we have $\Phi_{ij}$. If $a_{ij} = 0$, we have $\neg \Phi_{ij}$. Taking the conjunction of the CNFs of $\Phi_{ij}$ or $\neg \Phi_{ij}$, we obtain the following formula

$$\Psi := \mbox{CNF} (\Phi_{11}) \land \mbox{CNF} (\neg \Phi_{21}) \land \mbox{CNF} (\neg \Phi_{31}) \land \mbox{CNF} (\Phi_{12}) \land \mbox{CNF} (\Phi_{22}) \land \mbox{CNF} (\neg \Phi_{32}) \land \mbox{CNF} (\Phi_{13}) \land \mbox{CNF} (\Phi_{23})$$

which is in CNF by construction. If $\Psi$ is satisfiable, then there are matrices $\mathrm U, \mathrm V \in \{0,1\}^{3 \times 2}$ such that $\rm A = U V^{\top}$ holds at all known entries of $\rm A$. Using SymPy:

from sympy import *

u11, u12, u21, u22, u31, u32 = symbols('u11 u12 u21 u22 u31 u32')
v11, v12, v21, v22, v31, v32 = symbols('v11 v12 v21 v22 v31 v32')

Phi11 = Xor(u11 & v11, u12 & v12)
Phi21 = Xor(u21 & v11, u22 & v12)
Phi31 = Xor(u31 & v11, u32 & v12)

Phi12 = Xor(u11 & v21, u12 & v22)
Phi22 = Xor(u21 & v21, u22 & v22)
Phi32 = Xor(u31 & v21, u32 & v22)

Phi13 = Xor(u11 & v31, u12 & v32)
Phi23 = Xor(u21 & v31, u22 & v32)
Phi33 = Xor(u31 & v31, u32 & v32)

Psi = to_cnf(Phi11) & to_cnf(Not(Phi21)) & to_cnf(Not(Phi31)) & to_cnf(Phi12) & to_cnf(Phi22) & to_cnf(Not(Phi32)) & to_cnf(Phi13) & to_cnf(Phi23)

print "Formula Psi is \n", Psi

# is Psi satisfiable?
print "\nSatisfiable? \n", satisfiable(Psi)

produces $\Psi$ (in CNF)

And(Or(Not(u11), Not(u12), Not(v11), Not(v12)), Or(Not(u11), Not(u12), Not(v21), Not(v22)), Or(Not(u11), Not(u12), Not(v31), Not(v32)), Or(Not(u21), Not(u22), Not(v21), Not(v22)), Or(Not(u21), Not(u22), Not(v31), Not(v32)), Or(Not(u21), Not(v11), u22), Or(Not(u21), Not(v11), v12), Or(Not(u22), Not(v12), u21), Or(Not(u22), Not(v12), v11), Or(Not(u31), Not(v11), u32), Or(Not(u31), Not(v11), v12), Or(Not(u31), Not(v21), u32), Or(Not(u31), Not(v21), v22), Or(Not(u32), Not(v12), u31), Or(Not(u32), Not(v12), v11), Or(Not(u32), Not(v22), u31), Or(Not(u32), Not(v22), v21), Or(u11, u12), Or(u11, v12), Or(u11, v22), Or(u11, v32), Or(u12, v11), Or(u12, v21), Or(u12, v31), Or(u21, u22), Or(u21, v22), Or(u21, v32), Or(u22, v21), Or(u22, v31), Or(v11, v12), Or(v21, v22), Or(v31, v32))

and the satisfying assignment

{v31: False, v11: True, v32: True, u31: False, v22: True, u22: True, u11: True, v21: False, u12: True, u21: False, v12: False, u32: False}

Hence,

$$\mathrm U = \begin{bmatrix} 1 & 1\\ 0 & 1\\ 0 & 0\end{bmatrix}$$

$$\mathrm V = \begin{bmatrix} 1 & 0\\ 0 & 1\\ 0 & 1\end{bmatrix}$$

and, thus,

$$\mathrm U \mathrm V^{\top} = \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + \begin{bmatrix} 0 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & \color{red}{0}\end{bmatrix}$$

Thus, if the missing entry of $\rm A$ is zero, then we obtain a rank-$2$ matrix.

Translating to binary integer programming, formula $x_i \lor x_j$ becomes the linear inequality $x_i + x_j \geq 1$ and $\neg x_i$ becomes $1-x_i$. From $\Psi$ (in CNF), we obtain $32$ linear inequalities

$$\begin{array}{rl} - u_{11} - u_{12} - v_{11} - v_{12} &\geq -3\\ - u_{11} - u_{12} - v_{21} - v_{22} &\geq -3\\ & \vdots\\ v_{31} + v_{32} &\geq 1\end{array}$$

plus the inequality constraints $0 \leq u_{ij}, v_{ij} \leq 1$ and the integrality constraints $u_{ij}, v_{ij} \in \mathbb Z$.

To summarize, we reduced a simplified version of the original matrix completion problem to SAT and then we reduced SAT to binary integer programming. However, the reduction to SAT requires the computation of the CNF of either $\Phi_{ij}$ or $\neg \Phi_{ij}$, which produces a formula whose number of conjuncts may be non-polynomial in $r$.


Is there a concept for an algorithm computing a function by first finding another algorithm?

There is a well-known algorithm, Levin's universal search algorithm, whose mode of operation is identical. Consider for example the problem of finding a satisfying assignment for a formula which is guaranteed to be satisfiable. Levin's universal search runs all potential algorithms in parallel, and if any algorithm outputs a satisfying assignment, stops and outputs this assignment. If the optimal algorithm for the problem runs in time $f(n)$, then Levin's algorithm runs in time $O(f(n))$ (with a possibly huge constant) if implemented correctly.

While Levin's algorithm is impractical (due to the huge constants involved), it is very interesting theoretically. See the Scholarpedia article for more on universal search.


Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

This is much easier than inclusion–exclusion.  Compute the number of natural numbers smaller than $N$ that contain none of the digits 2, 4, 6, 8 and subtract that from $N$ (or $N+1$ if you're including zero).  To compute the number of naturals that contain none of 2, 4, 6, 8, observe that, if $M\leq N$ (padded with zeroes so $M$ also has $d$ digits) then $M$ and $N$ must agree on their first $i$ digits (for some $0\leq i\leq d$), then the $(i+1)$st digit of $M$ must be less than the $(i+1)$st digit of $N$ and the $(i+2)$nd, ..., $d$th digits of $M$ can be any of 0, 1, 3, 5, 7, 9.


It really depends on the hardware, the memory type, ...

Usually, for memory accesses, reading extra data have no side effect so a CPU may read 32bits and use a multiplexer to extract the byte from the correct data lane.

There are still some signals that indicates the width of accesses and which byte is actually read, because some addresses may be mapped to I/O ports, and reading an I/O port can have side effects.

It can also be used to optimize access times : Imagine a 32bits CPU connected to a bridge component as an interface to a 8bits NOR FLASH (for example some boot BIOS). The bridge should check which bytes are needed to minimize the number of accesses to the FLASH chip.


I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of $s$:

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Where $|G|$ is the length of the program that computes $G(s)$ (often quite short, as for linear generators).

Note that in practice, random number generator attacks are not as described: they may fail or produce incomplete results. In that case, you may adapt the algorithm so that it returns $|s|$ when the result of the attack is unsatisfactory. The same remark goes for compression algorithms.

The caveat to this approach as opposed to compression algorithms is that compression algorithms are in general much more suited to computing KC as they are tailored to work on any string, whereas an attack can work only if $s$ happens to be in the image of $G$ (very unlikely).


Process B isn't looping; it runs and then quits. In other words, there won't be a second "leave note B" in your picture. There is a loop in process A (a busy wait, as it's called) and when process B removes its note, then execution will return to A's loop: A will check and see that there is milk so will remove its note and quit.


How to find all shortest paths between two nodes in a weighted undirected graph?

To tell whether a vertex $v$ is along some possible shortest path from $s$ to $t$, compute $d(s,v)$ (the length of the shortest path from $s$ to $v$) and $d(v,t)$, and then.....

You can compute $d(s,v)$ for all vertices $v$ efficiently using....

(It's your exercise, so I'll let you have the pleasure of working out how to fill in the blanks.)


Strongly connected orientations of undirected graphs

If $uv$ is a bridge then any orientation of $G$ either includes the edge $u\to v$ and has no path from $v$ to $u$, or vice-versa.

If $G$ has no bridge, then it is $2$-connected. A graph is $2$-connected if, and only if, it can be decomposed as $C\cup P_1 \cup\dots \cup P_k$ where $C$ is a cycle and each $P_i$ is a path (possibly just a single edge) that intersects $C\cup P_1\cup\dots\cup P_{i-1}$ at both its endpoints and nowhere else. Now construct your strongly connected orientation from this decomposition.


Assume that every single operation has a relative error ≤ eps. Starting with this, what if x = 1.001 and y = 0.999, or x = 10.01 and y = 9.99, or x = 1,001,000,000 and y = 999,000,000? How is log (x / y) affected, and how is log (x) - log (y) affected?


Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm

The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent_set_(graph_theory) or set packing.

One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$.  Note that $\|\sum_i v_i x_i \|_\infty \le t$ iff $-t \le \sum_i v_i x_{ij} \le t$ for all $j$, so this can be expressed using linear constraints.  Then, apply an off-the-shelf ILP solver and hope it terminates in a reasonable amount of time.

(The ILP solver will probably apply methods such as solving the associating linear program and then applying randomized rounding, so you don't need to implement it yourself.)

If $d$ is very small, it might be possible to solve the problem in something like $\tilde{O}(dkn^{k/2})$ time using meet-in-the-middle search combined with a nearest-neighbor data structure, but I haven't worked out the details, and I expect it won't scale to large $d$.


How can finite sets be represented as a type?

If you want a type system for finite sets that enforces the validity and unicity of all representations, then your type system must be able to model equality of elements. (Informal proof: insert x (insert y empty) has differently-shaped representations depending on whether x and y are equal.) This is impossible with algebraic datatypes alone, unless you're willing to restrict the domain of the sets to sufficiently simple sets (for example, you can use a bit vector to represent a finite subset of a finite set; you can use finite lists of positive integers to get a unique representation of finite sets of positive integers: store $\{x_1, \ldots, x_n\}$ as $[x_1, x_2-x_1, \ldots, x_n-x_{n-1}]$ where the $x_i$ are numbered in increasing order).

A sophisticated type system can of course represent anything you want. Basically, you need:

dependent types, so that the type definition can contain equality assertions;
induction, to build a data structure containing any number of elements.

For example, the calculus of inductive constructions admits representations of finite sets. You can look for examples in the Coq library and contributions.

If you're willing to relinquish either the requirement for unicity or for validity, you can make do with algebraic datatypes. Representing finite sets as finite lists yields a set representation where every datum is valid, but each set admits multiple representation ($n!$ representations for an $n$-element set if the elements have unique representations). Something like a sorted list or search tree can give a unique representation (assuming that the elements have a unique representation). For search trees, to have representation unicity, you need a balancing function that guarantees unicity (which may impact performance).

In the type systems found in typical programming languages, it is typical to implement sets with an underlying representation that may or may not be valid. The type system thus does not enforce that all representations are valid. It does, however, help to maintain this property: a finite set can be implemented as an abstract type. The type is implemented as a module which is sealed, ensuring that all elements of the finite set type have been built from constructors provided by the module. The correctness of the finite set modle code ensures the validity of set representations, and the type system helps by maintaining this invariant.


Can every DFA be converted to an equivalent one that has a single accept state

Myhill–Nerode theory implies the following result:

  Every DFA for a regular language has at least as many accepting states as the minimal DFA.

Indeed, suppose that the minimal DFA has $m$ accepting states. Let $w_1,\ldots,w_m$ be words which cause the minimal DFA to reach these states. Now consider any DFA for the same language, and let $q_1,\ldots,q_m$ be the states that the DFA reaches upon reading $w_1,\ldots,w_m$. Since $w_1,\ldots,w_m$ are in the language, all these states must be accepting. Furthermore, they must be different, since they are pairwise inequivalent (for each $i \neq j$ there exists a word $x$ such that $w_ix$ is in the language and $w_jx$ isn't, or vice versa). So the DFA contains at least $m$ accepting states.

It is not difficult to construct a regular language whose minimal DFA contains more than one accepting state - for example, the language of all words whose length is not divisible by 3. This language refutes your conjecture.


The function $f$ is a probability sub-distribution, which means that it's a like a probability distribution, only its integral can be less than $1$ (due to the observe statements). The return statement normalizes $f$ back to a bona fide probability distribution.

Outside of quantum computing, probabilities are non-negative.


How can you find all unbalanced parens in a string in linear time with constant memory?

Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $\Theta(\log(n))$ memory to store an index into a string of length $n$.

You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.

  using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren

So what does this stack contain? It's never going to contain () (an opening parenthesis followed by a closing parenthesis), since whenever the ) appear you pop the ( instead of pushing the ). So the stack is always of the form )…)(…( — a bunch of closing parentheses followed by a bunch of opening parentheses.

You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.

If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.

If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $\Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.

In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.

The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.

Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).

Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.


How does the Y combinator exemplify "Lambda calculus inconsistency"?

It's inspired from real events, but the way it's stated is barely recognizable and “should be regarded with suspicion” is nonsense.

Consistency has a precise meaning in logic: a consistent theory is one where not all statements can be proved. In classical logic, this is equivalent to the absence of a contradiction, i.e. a theory is inconsistent if and only if there is a statement $A$ such that the theory proves both $A$ and its negation $\neg A$.

So what does this mean regarding the lambda calculus? Nothing. The lambda calculus is a rewriting system, not a logical theory.

It is possible to view the lambda calculus in relation to logic. Regard variables as representing a hypothesis in a proof, lambda abstractions as proofs under a certain hypothesis (represented by the variable), and application as putting together a conditional proof and proof of the hypothesis. Then the beta rule corresponds to simplifying a proof by applying modus ponens, a fundamental principle of logic.

This, however, only works if the conditional proof is combined with a proof of the right hypothesis. If you have a conditional proof that assumes $n=3$ and you also have a proof of $n=2$, you can't combine them together. If you want to make this interpretation of the lambda calculus work, you need to add a constraint that only proofs of the proper hypothesis get applied to conditional proofs. This is called a type system, and the constraint is the typing rule that says that when you pass an argument to a function, the type of the argument must match the parameter type of the function.

The Curry-Howard correspondence is a parallel between typed calculi and proof systems.

types correspond to logical statements;
terms correspond to proofs;
inhabited types (i.e. types such that there is a term of that type) correspond to true statements (i.e. statements such that there is a proof of that statement);
program evaluation (i.e. rules such as beta) correspond to transformations of proofs (which had better transform correct proofs into correct proofs).

A typed calculus that has a fixed point combinator such as $Y$ allows building a term of any type (try evaluating $Y (\lambda x.x)$), so if you take the logical interpretation through the Curry-Howard correspondence, you get an inconsistent theory. See Does the Y combinator contradict the Curry-Howard correspondence? for more details.

This is not meaningful for the pure lambda calculus, i.e. for the lambda calculus without types.

In many typed calculi, it's impossible to define a fixed point combinator. Those typed calculi are useful with respect to their logical interpretation, but not as a basis for a Turing-complete programming language. In some typed calculi, it's possible to define a fixed point combinator. Those typed calculi are useful as a basis for a Turing-complete programming language, but not with respect to their logical interpretation.

In conclusion:

The lambda calculus is not “inconsistent”, that concept does not apply.
A typed lambda calculus that assigns a type to every lambda term is inconsistent. Some typed lambda calculi are like that, others make some terms untypable and are consistent.
Typed lambda calculi are not the sole raison d'être for the lambda calculus, and even inconsistent typed lambda calculi are very useful tools — just not to prove things.


What you're essentially asking is to find a total ordering of a graph of users whose partial orderings are results of querying a user for their relative rank. Your asymptotic complexity of the minimum necessary number of partial orders will relate to the Stirling number of the Second Kind mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. To find this total ordering (re: "how do I map the partial order into my range?") you would topologically sort the graph you're describing. Note that for every vertex, $u\leq_p v\Rightarrow (u,v) \in E$, and the graph would be directed.


What are the real world applications of set cover problem?

Set-cover heuristics are used in random testing ("fuzz testing") of programs.  Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes.  We'd like to do this over and over again.  If we do this naively, it will be less effective than it could be: typically many test cases cover basically the same code paths, but a small minority of test cases cover unusual code paths that would be interesting to test more intensively.

So, here's one solution that is used in industry.  We use a coverage measurement tool to instrument the program and record which lines of code are covered by each of the million test cases.  Then, we choose a small subset $S$ of those million test cases that has maximal coverage: every line of code covered by one of the million test cases will be covered by some test case in $S$.  $S$ is called a reduced test suite.  We then apply random mutation & testing to the reduced test suite $S$.  Empirically, this seems to make random testing more effective.  The smaller $S$ is, the more effective and efficient testing becomes.

So, how do we choose a reduced test suite $S$ that is as small as possible, while still achieving maximal coverage?  Answer: that's a set cover problem, so we use standard heuristics/approximation algorithms for the set cover problem.  The standard greedy approximation algorithm is typically used for this purpose.


Can one determinize finite automata over infinite trees?

This may be not explicitly spelled at many places in the literature, as deterministic tree automata are unable to capture specifications that are only expressible in branching-time logics.

Take for instance the property "There exists a node in the tree labeled with atomic proposition $x$" - this is equivalent to the CTL formula $\mathit{EF\,} x$.
This one cannot be represented as a deterministic tree automaton, but is easy to express as a non-deterministic Büchi tree automaton.
The reason is that a tree automaton accepts a tree $\langle T, \tau \rangle$ if all branches in the run tree for $\langle T, \tau \rangle$ are accepting. With non-determinstic tree automata, one can route the obligation to see an $x$ to somewhere in the tree. With deterministic automata, this is just not possible and thus one can only express $\mathit{AF}\, x$ in this form.

Hence, non-deterministic tree automata cannot be determinized in general.


Time-complexity for basic multiplication and division algorithms

The one loop that you see is for number of additions. But it is also assuming number of bits to be to the order of n. For one iteration, you will perform operation over O(n) bits. For n iterations, it will be to the order of n squared.


The distance $d_G(u,v)$ between two disconnected vertices $u,v$ of a graph is usually defined as $+\infty$.
As a consequence the diameter of a disconnected graph $G=(V,E)$ is
$$
\textrm{diam}(G) = \max_{u,v \in V} d_G(u,v) = + \infty.
$$


If a Triple Graph Grammar rule counts as a Mathematical Proof

A TGG defines (generates) a language of triples of graphs.
This can be used for many things, including establishing a notion of correctness for forward and backward transformations.  So if you have some transformation A -> B, you can check if it is correct by checking if there exists some A <-C->B that can be generated by the TGG.

Correct forward and backward transformations do not have to be bijections, although this could be enforced by analysing the TGG appropriately.

As a proof, one could use a TGG to generate proofs of consistency.  So given some A and B, I can prove that A and B are consistent (and whatever produced B from A or A from B correct), by determining a rule application sequence that takes you from some start triple graph to some A<-C->B.

So for your concrete syntax tree and AST you could check for consistency without recomputing the trees.  In practice, however, such a consistency checker can actually be slower than a recomputation (but is sometimes still better, e.g., if the computation was non-deterministic or required some form of decision making).


The program is actually using two variables. There is a global variable n, which is used by main(). There is a local variable, confusingly also named n, which is used by binary() and allocated on the stack.

Here are some excerpts from the code generated on my machine:

_binary:
...
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)
...

_main:
...
        movq    _n@GOTPCREL(%rip), %rsi
        movl    (%rsi), %edi
        movl    %eax, -4(%rbp)          ## 4-byte Spill
        callq   _binary
...
        .comm   _n,4,2                  ## @n

The first excerpt contains part of the code generated for binary(). The parameter n is passed in the register edi, and is then stored on the stack. The following command compares it to zero, implementing part of n>0.

The second excerpt contains part of the code generated for main(). The global variable n is allocated as a common symbol. The excerpt consists of the function call binary(n). You can see that n is pulled out of the global storage and put into edi, before calling binary().


Can a language be the one recognized by more than one automatons?

Yes, of course, it is possible.  For instance, the process of DFA minimization works as follows: given a DFA $M$, produce another DFA $M'$ that recognizes the same language but is as small as possible.  That tells you that it is possible to have two DFAs (deterministic finite-state automata) that recognize the same language.

If you want an explicit example: Let $M_1$ be a DFA with a single state (which is accepting) and self-loops on inputs $0$ and $1$.  Let $M_2$ be a DFA with two states (which are both accepting) and edges from state $s_0$ to $s_1$ on inputs $0$ and $1$, and edges from state $s_1$ to $s_0$ on inputs $0$ and $1$.  They both recognize the language $\{0,1\}^*$, i.e., they are two different DFA that recognize the same language.

The same holds for other common families of languages, e.g., context-free languages and pushdown automata; context-sensitive languages and context-sensitive grammars.


Error solving the next recurrence: $T(n)=7T(n/2)+n^2$

Some of your sums have typos, but you already have the right answer.

Here's a useful fact about logarithms:

$a^{\lg b} = 2^{(\lg a) \cdot (\lg b)} = 2^{(\lg b) \cdot (\lg a)} = b^{\lg a}$

Apply it to your answer, keeping in mind that $\lg 7 \approx 2.8 > 2$:

$O(7^{\lg n} + n^2) = O(n^{\lg 7} + n^2) = O(n^{\lg 7})$


Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?

The paper just uses the swaps to make the diagram simpler. It allows the authors to represent the relevant operation as a single box covering four wires, instead of the six underlying operations, when making larger circuits.

Here is a screen capture of the definition of the "MTSG" gate from the paper (note: the $V$ gate is just a square-root-of-NOT gate):

(They managed to make them look pretty terrible...)

And here's a place where it's used:

If you expand each MTSG box in that larger circuit into the underlying 6 operations, and align the diagram onto a fixed set of wires, you'll find you can easily slide any implied swap gates out of the circuit.

(But do keep in mind that it's possible that the first practical quantum computers will have limitations like 'only nearest neighbors in a 2d grid can interact'. That would force the use of many swap gates.)


How is the optimal number of hashes is derived in bloom filter?

We want to find the value of $k$ that minimizes the function
$$
f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k.
$$
When $m$ is large, $1 - 1/m \approx e^{-m}$, and so
$$
f(k) \approx \left(1 - e^{-kn/m}\right)^k.
$$
The logarithm of this is
$$
\log f(k) \approx k \log(1-e^{-kn/m}).
$$
The derivative of this approximation is
$$
\log(1 - e^{-kn/m}) + k \frac{\frac{n}{m}e^{-kn/m}}{1-e^{-kn/m}} =
\log(1 - e^{-kn/m}) + \frac{kn}{m} \frac{e^{-kn/m}}{1-e^{-kn/m}}.
$$
Let $x = e^{-kn/m} \in (0,1)$. The derivative is thus
$$
\log (1-x) - \log x \frac{x}{1-x} = \frac{(1-x)\log(1-x)-x\log x}{1-x}.
$$
It is not hard to check that the numerator is positive for $x<1/2$, zero at $x=1/2$, and negative for $x>1/2$. This means that when $k < \frac{m}{n}\log 2$, the approximation to $f(k)$ is decreasing, and when $k > \frac{m}{n}\log 2$, it is increasing. It thus reaches a minimum when $k = \frac{m}{n} \log 2$.


Usually, when we talk about the complement of a set we have some reference set to compare to.
In the setting of languages over some alphabet $\Sigma$, this means that the complement of some language $L$ would be $\overline L = \Sigma^\ast \setminus L$, i.e. the set of all strings over $\Sigma$ which are not in $L$.
In the particular case of
$$\mathrm{Sat} = \{\langle \psi \rangle \in \Sigma^\ast \mid \langle \psi \rangle \text{ encodes a satisfiable propositional formula } \psi \}$$
we find that
$$\overline{\mathrm{Sat}} = \{w \in \Sigma^\ast \mid w \text{ does not encode a satisfiable propositional formula } \psi \}$$
and hence, $\overline{\mathrm{Sat}}$ consists of all strings which represent unsatisfiable propositional formulas (i.e. ones that have no satisfying interpretations) and all strings which don't represent formulas at all.


How to prove "if every subset of a set is a CFL, then the set must be regular."

Suppose that $L$ is a language such that each subset of $L$ is context-free. I claim that $L$ must be finite, and so regular. Indeed, otherwise $L$ would have uncountably many subsets, and so not all of them could be context-free (since there are only countably many context-free languages).


Is the language of TMs that accept finite languages in $\mathbf{0}'$?

Your language $L$ is usually known as Fin or FIN, and is $\Sigma_2$-complete; see for example lecture notes of Cohen Wallace. Since the halting problem is in $\Sigma_1$, it follows that $L$ cannot be reduced to the halting problem.


DFA that accepts two more $1$'s than $0$'s

As mentioned this is not a regular language.

To prove this, recall that a language, $L$, is regular iff some DFA recognizes it.

We will show that no DFA recognizes $L$.
Consider the infinite set of strings $S=\{0^n : n \ge 0\}$.
Then any two strings in $S$ are of the form $\alpha=0^x$ and $\beta=0^y$, $x,y\ge0$, we may assume wlog that $x>y$.

Let $\lambda=1^{y+2}$.

Then $\alpha\lambda=0^x1^{y+2} \notin L$ (since $x>y \implies y+2 -x < 2$), but $\beta\lambda=0^y1^{y+2} \in L$.

Thus we have an infinite set of strings (prefixes), $S$, such that for every pair of distinct strings $\alpha,\beta \in S$ there exists another string (suffix) $\lambda$ where exactly one of $\alpha\lambda$ or $\beta\lambda$ is in $L$. Thinking about this, this means that if a DFA, $D$, recognizes $L$, then every string in $S$ must take $D$ to a different state (if $\alpha,\beta \in S$ both took $D$ to the same state then so would $\alpha\lambda$ and $\beta\lambda$ for any $\lambda$, but we know that only one of these strings is in $L$). So $D$ must have at least $|S|$ states, but $|S|=\infty$, thus $D$ cannot exist.


Is it impossible to truly emulate a system if its actual clock speed is the same?

That very much depends on how well the instruction set of the CPU to be emulated maps to the instruction set of the emulating CPU. Certainly, clock speed is not the deciding factor. It might very well be that a slower (clock wise) CPU A can emulate a faster CPU B.

This can be both because of more powerful instructions (e.g. SSE instructions that allow doing the same operation to multiple values at once), or improvements in instruction level parallelism (e.g. more adders, multipliers etc. so that more instructions can be executed simultaniously, smarter recognition of independent instructions). There are also strong contributions from larger caches and smarter branch prediction. All these factors (and probably many more that I don't know about) can be improved to increase the average number of instructions executed without changing the clock speed. Since clock-speed increases stalled some years ago, this kind of improvement has been a major contributor to performance increases in CPUs.

Of course it also strongly depends on the skill of the person writing the emulator. There will always be some overhead involved in translating the instructions for CPU B to instructions that work on A. The larger the difference between the two CPUs, the larger the overhead.


What are the benefits of languages that are not Turing complete?

The main advantage of having a Programming Language that is not Turing Complete is that your language can be strongly normalizing, that is, you can ensure that all terms halt with a unique, well formed value.

I've come across non-Turing complete languages primarily with proof assistants. When you're using programs to prove theorems, you need to make sure that all terms halt, since otherwise you can produce non-terminating terms of type False. This also ensures that type checking is decidable with dependent types, since we need to evaluate code with type checking. Agda and Coq are both languages that are not Turing Complete. This also ensures that you can't accidentally write an infinite loop, which is the motivation behind things like the Dhall language.

As for what you mention about program analysis, Rice's theorem means that any analysis of a Turing Complete language is either unsound or incomplete. So if you use restricted languages, you might be able to write analyses that are precise.


How to reduce the cost of search based on previous BFS?

You have two very different situations in the next search condition. If the graph is set up to represent a grid, then the obstacles are simply removed edges to the vertex where the obstacle is, by moving obstacles you have changed the graph, so any new problem is a search on a new graph and the old results are meaningless. For any two verticies, to see if the new obstacles block the old path is easy, however to see if replacing the edges from the old graph will shorten the path requires you to redo path finding. So in the case of the obstacles changing any algorithm would involve much more work then just redoing the BFS, which is quite simple. As for a changed user position you could sacrifice initial cost and search for all other searches upfront, depending on how many times you want to call the algorithm this may or may not pay off, this case is very situation dependent.


This problem is strongly NP-complete.

Suppose all the $A_j$ are odd. Then we know that since $i_{2j-1} + i_{2j} = A_j$ is odd, one of $i_{2j-1}$ and $i_{2j}$ is even and the other is odd. We can assume that $i_{2j-1}$ is odd and $i_{2j}$ is even. By letting $\pi_j = \frac{1}{2}(i_{2j-1}+1)$ and $\sigma_j = \frac{1}{2}(i_{2j})$, we can show that this is equivalent to asking for two permutations, $\pi$ and $\sigma$, of the numbers $1 \ldots n$ such that $\pi_j + \sigma_j = \frac{1}{2}(A_j+1)$.

This problem is known to be NP-complete; see this cstheory.se problem and this paper of W. Yu, H. Hoogeveen, and J. K. Lenstra referenced in the answer.


Average case of simple algorithm like binary search

The average case time complexity is $O(\log n)$ (with a suitable implementation).  Intuitively, each iteration typically removes a constant factor of the elements from the array.

Here's a more formal analysis. Consider an iteration to be "good" if it removes at least $1/3$ of the elements of the array.  Then an iteration is good with probability $2/3$.  Let $X_1$ denote the number of iterations until the first good iteration; this is a geometric random variable, so its expected value is $1.5$.  Let $X_2$ denote the number of iterations after the first good iteration, until the second good iteration.  Again, the expected value of $X_2$ is $1.5$.  And so on.  Now note that after $j$ good iterations, only a $(2/3)^j$ fraction of elements remain, so after at most $k = \lg_{2/3} n$ good iterations, the array will have only a single element and will terminate immediately.  The total number of iterations is $X_1 + X_2 + X_3 + \cdots + X_k$.  By linearity of expectation, the expected value of this sum is $1.5k$.  Thus the expected number of iterations until this terminates is $1.5 \lg_{2/3} n =  \frac{1.5}{\log(2/3)} \log n = O(\log n)$.

You can implement this so each iteration takes $O(1)$ time.  In particular, you don't actually remove elements in steps 3 and 4; you just keep track of the range of indices of non-removed elements.  That's always a consecutive range, so everything is easy.

In this way, the algorithm takes $O(\log n)$ iterations on average, and $O(1)$ time per iteration, for an average-case running time of $O(\log n)$.

Incidentally, with this implementation, the worst case running time is $O(n)$ rather than $O(\log n)$.  Each iteration of the loop removes at least one element from the array, so there can be at most $n$ iterations of the loop, and each iteration runs in $O(1)$ time, for a total of $O(n)$ worst-case running time.


Three for loops gets you to n^3.

EDIT:

for (int i=0; i < n; i++) // first n
..etc..
for (int j=0; j < n; j++)  // second n
...etc...

Outer two are n, that makes n^2 so far. Next look at inner loop:

for (int k=0; k <= j; k++) // third n

Innermost counts as another n for big O purposes even if running k to j instead of k to n. You're still on the order of n^3.

For that inner loop you're doing 1 + 2 + 3 ... loops as j iterates, so strictly speaking it's not exactly n^3 iterations, but n * n * (n+1)/2, but for big O purposes don't let that throw you off, it's n^3, the (n+1)/2 piece is just another layer of n. If n was 1,000,000 you'll end up with "on the order of" 10^18 loops.

Hope this helps.


A basic question about recursive computation

In pure untyped lambda calculus functions are anonymous. Generally, when you want to define a function recursively, you can simply have it "call" itself, for example:

if $n=0$ then $f(n) = 1$
if $n>0$ then $f(n) = nf(n-1)$.

In lambda calculus we don't have the same luxury, functions don't even have "names" in the first place, they are defined in terms of variable binding and variable substitution.
Still, there is a way to implement recursion, discovered by Haskell Curry, by using a particular lambda-term, called fixed-point combinator (if you are interested in details, any reasonable source on lambda calculus covers this aspect).
With the new notation, the authors are effectively introducing a mechanism to give names to functions, removing the problem entirely.


Language equivalency for modified CFG closed over intersection

It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar.
Here is more quote from that article on Wikipedia.

The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure under complement and under $\epsilon$-free string homomorphism are still open problems.

Since context-sensitive languages are closed under complement, the family of conjunctive languages is a strict subset of the family of context-sensitive languages. In fact, the family of languages generated by boolean grammars, grammars that extends conjunction grammars with negation operations, is also a strict subset of the family of the context-sensitive languages.

A related problem is the expressive power of intersections of context-free languages.
An infinite hierarchy of intersections of context-free languages by Liu and Weiner shows that ($d$-1)-intersection closure of context-free languages is strictly contained in the $d$-intersection closure of context-free languages, since the language $\{a_1^{n_1} a_2^{n_2} \cdots a_{d}^{n_{d}} b_1^{n_1} b_2^{n_2} \cdots b_d^{n_d} \mid n_1,n_2,\ldots ,n_d\ge 0\}$ is contained in the latter family of languages but not in the former family of languages for all $d\ge2$.


What factors must one consider choosing an NN structure?

Here is a list of parameters you should take into consideration (to name some):

The learning algorithm (gradient descent is the most explained of them)
The number of layers (3,4 layers is usually enough - input, 1 or 2 hidden, output). The output layer depends on your output (e.g., if you want to classify yes/no then your output layer consists of two nodes). The same applies for input layer. However, you may consider the case of using only a subset of the input for the learning. For instance, you may think that your problem is affected by $k$ variable. However, if you take $k'$ of them then you may get better results.
Number of nodes in the hidden layers (you select that by trial and error)
Number of training iterations (not too much to avoid over-fitting)
Size of training/testing data (there are some known rules like the 80:20 for example)
The type of the function used at the nodes (neurons) (e.g. $f(x) = 1/(1+e^x)$ or $f(x) = tanh(x)$), usually the first is sufficient.
An important issue is the pre-processing and post-processing of data (this is common in all pattern recognition techniques). You may for instance convert your data by applying a certain function $f$ and then run your experiments.

Note: given the many parameters you need to deal with, it is a good approach to use a search algorithm to select the best parameters for you. It is better be a heuristic search algorithm (e.g. genetic algorithm) if you had very large number of parameters set you will deal with (which is usually the case).

Note: use the Matlab NN library or Weka (open source). They would have all these parameters for you.  In fact, Weka has many other learning algorithms.

Note: Perhaps, you may want to use other algorithms then. If this is case, try support vector machines. There was a historical battle between these two algorithms (in the 1990's). SVM won it ! (I am not being very scientific here).


Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph.  For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$.  If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can be removed from $T$ and replaced with a lighter edge $f$, giving a tree $T-e+f$ with a smaller weight than $T$, contradicting the fact that $T$ is an MST.

As a concrete example, suppose $G$ is the path graph on vertex set $\{a,b,c\}$ and edge set $\{ab, bc\}$, with the edges $ab$ and $bc$ having weights  $1$ and $2$, respectively.  Then, edge $bc$ is not the lightest edge available, but it is a safe edge to add first and it is the lightest edge between $S$ and $V-S$ if we take $S = \{a,b\}$.