Solving for the minimum cost, colored, set cover

Unfortunately this is NP-hard (even if we use only the costs 0 and 1), so it's very unlikely that there exists a polynomial-time algorithm that will solve every instance.  I'll show this by reducing the NP-hard problem Exact Cover to your problem.  I'll work with the decision variant of your problem, in which we are given a number $q$ in addition to $U$, $C$, $S$ and $cost()$, and the task is to report whether or not there is a solution with cost at most $q$.  (With an algorithm that answers the decision problem, minimisation/maximisation can then be accomplished efficiently with binary search, and an actual solution realising that optimal solution size can also be recovered without too much extra difficulty.)

Recall that in the Exact Cover problem, we are given a collection $A = \{a_1, \dots, a_r\}$ of sets, each of which is a subset of some ground set $B$, and our task is to report whether or not it is possible to choose a subset $X \subseteq A$ of sets in $A$ such that every element in $B$ belongs to exactly one set in $X$.  To encode an instance of the Exact Cover problem as an instance of your problem:

For each set $a_i$ in $A$:

Add the set $a_i$ to $S$, as $s_i$.
Add a new colour $c_i$ to $C$.
Set $cost(b_j, c_i) = 0$ for every $b_j \in a_i$.
Set $cost(b_j, c_i) = 1$ for every $b_j \notin a_i$.

Set $U = \cup_{s_i \in S}s_i$ as usual.
Set $q = 0$.

Basically, we create a colour $c_i$ for each set $a_i$ in $A$, and set the costs of that colour so that ground elements from the corresponding set ($a_i$) get no cost, while every other ground element gets a positive cost.  This means that whenever there does exist an exact cover for $A$, it is possible to create a zero-cost solution to the corresponding constructed instance of your problem: just assign every ground-set element the colour corresponding to the unique set that contains it.  Thus, a "YES" answer to the Exact Cover problem implies a "YES" answer to the constructed instance of your problem.

In the other direction, we would like to show that a "YES" answer to the constructed instance of your problem implies a "YES" instance to the original Exact Cover problem instance.  So, we start by assuming a "YES" answer to the constructed instance of your problem.  This means that there exists a zero-cost assignment of colours to ground-set elements that could be produced by choosing a set cover from $S$, then choosing a colour for each set in the cover, and assigning that colour to all ground-set elements belonging to that set.  We can represent such a solution as a pair $(X, f)$, where $X \subseteq S$ is the set of ground-element sets chosen for the cover, and $f : X \to C$ is a function that maps a set in $X$ to a colour in $C$.  (Even though it is individual ground-set elements that we colour and not sets of them, $f$ is still well-defined for a feasible solution, since we require of every set $x \in X$ that every $e \in x$ is assigned the same colour.)

In order to easily build a solution to the original Exact Cover instance from $(X, f)$, we want the ground-set elements having some particular colour to be exactly the ground-set elements in some set in $A$: then we can simply go through each colour present in the solution to the your problem (i.e., in the range of $f$) and include the corresponding set from $A$ in the Exact Cover solution.  So in other words, we would like to have a solution $(X, f)$ that has $f(x_i) = c_i$ for each $x_i \in X$.  But this is complicated by the fact that $X$ could contain sets that overlap, which is of course forbidden in an Exact Cover solution.  Between any pair $x \in X, x' \in X$ there are two kinds of potential overlap: containment (either $x \subset x'$ or vice versa), and "proper overlapping", where $x \cap x' \neq \emptyset$ but neither set contains the other.

To address the problem of containment, it is easy to see that, whenever there exists a solution $(X, f)$ that contains a pair of sets $x \in X$ and $x' \in X$, one of which contains the other, then there also exists another solution $(X', f')$ with the same cost and in which the smaller of the two sets has been removed.  (If $x = x'$, then just remove either one arbitrarily.)  Iterating this process until we cannot apply it any more ensures that there must exist a solution $(X'', f'')$ in which no set in $X''$ contains any other set in $X''$.  (Note that all we care about is the fact that such a solution must exist; for the purposes of answering the YES/NO question about the original Exact Cover instance, we don't need to know a specific solution.)

This leaves the problem of "properly overlapping" sets.  I'll now show that these cannot occur in any zero-cost solution to your problem.

Suppose towards contradiction that there is some chosen set $x_i \in X''$ such that $f(x_i) \neq c_i$.  Then $f(x_i) = c_j$ for some $j \neq i$, with $x_j \in X''$ also.  But because there is no other set in $X''$ that contains $x_i$ as a subset, there must be at least one ground-set element $b \in x_i$ that is not also in $x_j$.  Thus assigning $b$ the colour $x_j$ incurs a cost of 1, which cannot be recouped via any other means.  Since we know that $(X'', f'')$ has a cost of 0, this is a contradiction.  Thus it follows that if there exists a zero-cost solution $(X, f)$ to the constructed instance of your problem, then there must also exist a zero-cost solution $(X'', f'')$ to it in which no chosen set contains any other chosen set and in which no set properly overlaps any other set.  $X''$ is, thus, an exact cover -- so the answer to the Exact Cover instance must also be "YES".

We have established that a "YES" answer to the constructed instance of your problem implies a "YES" answer to the original Exact Cover instance, and vice versa.  This implies that a "NO" answer to either instance implies a "NO" answer to the other, which in turn implies that the two problems are equivalent.  Since the construction of instance of your problem took only polynomial time and space, an algorithm that solves your problem in polynomial time could also be used to solve Exact Cover in polynomial time.  Since Exact Cover is NP-hard, it follows that your problem must be NP-hard too.


The relation of $e$ and $d$ is set so that encryption and decryption are inverses of each other, that is, if you encrypt a message then the ciphertext decrypts to the original message. Encryption and decryption are
$$ c = m^e \pmod{n}, \quad p = c^d \pmod{n}, $$
where $n = pq$ is part of the public key, $m$ is the message, $c$ the ciphertext, and $p$ the decrypted plaintext. We want $p = m$, i.e.,
$$ m = m^{ed} \pmod{n}. $$
This equation holds for all $m$ iff $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n)$ is Carmichael's function. For $n = pq$, $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. In practice, $\lambda(n)$ is replaced by Euler's function $\varphi(n) = (p-1)(q-1)$.


Is language {M | M halts and print "Hello World"} recursively enumerable?

Enumerate all turning machines $M_1, M_2, \dots, $ and simulate them in a dovetail fashion, i.e., proceed in rounds:

In the first round simulate $M_1$ for $1$ step;
In the second round simulate $M_1$ and $M_2$ for one (more) step each;
In the third round simulate  $M_1$, $M_2$ and $M_3$ for one (more) step each;
...

In general, at the $i$-th round you perform one additional step for all turning machines in $\{ M_1, \dots, M_i \}$ that have not yet halted. Whenever a Turing machine $M$ halts, check if its output is "Hello World" and, if so, return $M$.


Find the first integer with exactly $n$ divisors

Some observations: If p is a prime, then $p^{n-1}$ has exactly n divisors. And if for example p, q, r are different primes, then $p^{n-1} q^{m-1} r^{j-1}$ has exactly n * m * j divisors.

And that's the only way we can find numbers with exactly n divisors: We write n as a product n = n1 * n2 * n3 ..., then find primes p1, p2, p3 and so on, and the product $p1^{n1-1} p2^{n2-1} p3^{n3-1} ...$ has exactly n divisors.

If we sort so that n1 ≥ n2 ≥ n3, then a product that is not in the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ can be made smaller while having the same number of divisors by using the primes 2, 3, 5 in that order. For example, if we start with $2^3 5^2$ then $2^3 3^2$ has the same number of divisors, but is smaller. Likewise, $3^3 2^2$ can be replaced with $2^3 3^2$ with the same number of divisors, bit smaller.

So the smallest number with n divisors has the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ with n1 ≥ n2 ≥ n3 ... and n = n1 * n2 * n3 ...

Now a number like n = 1000, or n = $10^{1000}$, can be written as a product in many ways, so you need to reduce the number of possibilities. You can use an algorithm where you try all possible exponents for 2 that could lead to the smallest number with n divisors, then all possible exponents for 3, and so on.

Let n = p1 * p2 * p3 ... * pk, with primes p1 ≥ p2 ≥ p3 ≥ ... ≥ pk. Whenever we choose an exponent, that exponent is either p - 1 where p is the largest prime not used so far, or it is of the form ab - 1 where b is the smallest prime factor of ab, and ab is greater than that largest prime. (That's quite obvious, right? It's a prime or composite minus 1, and since the exponents are in descending order, its the largest prime minus 1, or greater than that).

n was the product of k primes. Let P be the k-th prime. If an exponent is of the form ab-1, then P is not a factor of the number. And if we have a factor $p^{ab-1}$, then replacing this with $p^{a-1} P^{b-1}$ gives a number with the same number of factors, but smaller unless $p^a < P$.

This hugely reduces the number of choices. Take n = $2^{1000}$ which is the product of 2,000 primes. The k-th prime is very roughly P ≈ 20,000.

We saw that the smallest number with n divisors can only have a factor $p^{ab-1}$ if $p^a < P$. We have $2^{15}≥P ≈ 20,000$, $3^{10} ≥ P$, $5^7≥P$, $7^6≥P$, $11^5≥$, and $13^4≥P$, so a ≤ 14 when p = 2, a ≤ 9 when p = 3, a ≤ 6 when P = 5, a ≤ 5 when P = 7, a ≤ 4 when P = 11, and a ≤ 3 when p ≥ 13. And we must have ab ≥ 5, b is the smallest prime factor of ab, and ab must only have prime factors 2 and 5.

As a result, the only composite exponents minus 1 that are possible in the smallest number with $10^{1000}$ divisors are: $2^{4*2-1}$, $2^{5*2 - 1}$, $2^{5*5 - 1}$, $2^{8*2-1}$, $2^{10*2 - 1}$, $3^{4*2-1}$, $3^{5*2 - 1}$, $3^{5*5 - 1}$, $3^{8*2-1}$, $5^{4*2-1}$, $5^{5*2-1}$, $5^{5*5-1}$, $7^{4*2-1}$, $7^{5*2-1}$, $7^{5*5-1}$, and $11^{4*2-1}$. This is followed by a huge number of factors $p^{5-1}$, finishing with a huge number of factors $p^{2-1}$.

Since the exponents have to be in non-decreasing order, there is only a small number of cases to try, even for a huge number like $n = 10^{1000}$.

PS. In your trivial examples, n = 4 = 2 * 2, the solution was $2^{2-1} 3^{2-1} = 6$, and with n = 6 = 3 * 2, the solution was $2^{3-1} 3^{2-1} = 12$.

PS. Assume you have a more moderately sized n, let's say an n that is the product of 10 primes, making P = 10th prime = 29. We have $2^5<29$, $3^3<29$, $5^2<29$, but $7^2 > 29$. Therefore the only possible factors with an exponent that is not a prime -1 are: $2^{4-1}$, $2^{9-1}$, $2^{6-1}$, $2^{8-1}$, $2^{10-1}$, $2^{25-1}$, $3^{4-1}$, $3^{9-1}$, $3^{6-1}$, and $5^{4-1}$.


'simple' algorithm that can predict disk usage or 'time to be full'

I'd try fitting a linear model (i.e., assume new data arrives at a constant rate) or an exponential one (i.e., new data is proportional to what is already there), and see which one is better.


Start learning about Theory of Distributed Systems?

Roger Wattenhofer's Principles of Distributed Computing lecture collection is also a good place to start.

It is freely available online, it assumes no prior knowledge on the area, and the material is very well up-to-date — it even covers some results that were presented at conferences a couple of months ago.


Answers to your questions in given order: (a) Yes, an NFA could in principle be converted into multiple distinct DFAs for the same language.  Note however: There is always a unique DFA having a minimum number of states; other DFAs would have to be 'redundant' in some sense.  (b) There may be different methods, though I am only aware of one.  As long as the resulting DFA recognizes the same language, I would say the conversion method would be considered correct.  (c) No, the expression d(q0,e,q2) would NOT be correct; however for every transition function $d$ there is a corresponding transitive closure $d^*$ for which that would be a valid expression.  (d) No, it is not correct to assume the existence of 'hidden' e transitions; all defined transitions, e or not, must be given explicitly, but it is permissible to leave some transitions undefined (and any NFA-to-DFA converter must handle that case).  (e) Not only is it NOT 'bad practice' to have multiple NFA states as one DFA state, that is the standard tactic used by the canonical NFA-to-DFA procedure.


Prove or disprove {wtw^R | |w| = |t|} is context free

Suppose $S_c$ is context free. Then let $p$ be the pumping length and choose $s = 0^{2p}0^p1^p0^{2p}$ in $S_c$ that satisfies the pumping lemma. Thus, we can break $s$ into $uvxyz$, with $|vxy| \leq p$ and $|vy| \geq 1$. And for all $i$, $uv^ixy^iz$ is a string in $S_c$.
We have three cases.

$vy$ contains all 0s and these 0s can be chosen from either the beginning $0^{2p}$ of $s$, middle $0^p1^p$ of $s$ or the last $0^{2p}$ of $s$. Now, by pumping lemma, since $uv^ixy^iz \in S_c$, for all $i$. We choose $i = 2$, so we have $s' = uv^2xy^2z = uvvxyyz$. Clearly, since $vy$ contains all 0s, and regardless which part of $s$ are chosen from, this string is the form of $wtw^R$ such that $|w|$ = $|t|$ = $w'$ with either $w$ is all 0's and $w'$ is not all 0s or vice verse. This implies that $w' \neq w^R$ or $w' \neq w$.

$vy$ doesn't contain any 0s in last $0^{2p}$ of $s$ (We choose in the last part of $s$, but it's essentially the same by choosing first or middle part of $s$). Similarly, either the length of $uv^2xy^2z$ is not multiple of 3 (since pumping will increase the number of 1's), or this string is the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ consists all 0s but $w'$ contains some 1s. Thus $w' \neq w^R$.

$vy$ contains some 0s and some 1s in last $0^{2p}$ of $s$. From pumping lemma, since $vxy \leq q$, $vxy$ must be sub-string of $0^p1^p$. Then, by pumping the string $s' = uv^ixy^iz$ for all $i$, the length is string is not multiple of 3 since pumping increases number of 0s or 1s, or the string is in the form of $wtw'$ such that $|w|$ $=$ $|t|$ $=$ $|w'|$ with $w$ is all 0s but $w'$ is not all 0s.

Thus, we can conclude that all three cases above reach contradiction and hence $S_c$ is not context free.


What is the formal name for an "entry" in an ontology?

My understanding is that an ontology, at the end of the day, really boils down to some database storing objects/entries, where each entry has a set of known attributes as well as relationships to other entries.

The more common understanding is that one can emulate1 any ontology as a theory in single sorted first order predicate logic. Because such a theory can be seen as an ontology itself, it "really boils down to ... database(s)" if and only if predicate logic boils down to databases. And indeed, there is a close connection, but it won't help you to understand ontologies.

  What is the formal name for an “entry” in an ontology?

Even in your database analogy, you are missing the fact that you also have to specify the database scheme itself in the ontology language. There are different components of an ontology, namely individuals, types/classes, attributes, interrelationships/relations, function terms, restrictions, rules, axioms, and events1. Your "entry" seems to be intended to describe the attributes of an individual, and the relations between individuals. This task is done by the rules, but note that rules are more powerful than this.

1If the ontology contains events, then it is unclear how to emulate it in predicate logic.

Just like vzn, I now have the urge to clean up some of the confusion from the question, independent of whether it will earn me downvotes or not. (People might argue that such explanations based on mathematical logic require too much background knowledge, are too unrelated to ontology, and only lead to confusion. They may be right...) Even if there are practical reasons to prefer RDF or OWL as ontology languages over predicate logic, the simple structure of the later makes it a good tool for explaining some essential components of an ontology language.

A theory in single sorted first order predicate logic consists of axioms and a signature describing the non-logical symbols, i.e. the constants, functions, and predicates (and their arity). The axioms are well formed logical sentences over the given signature (with equality). Let's take set theory as an example. The signature just consists of $S_{rel}=\{\in\}$ and $\operatorname{ar}(\in)=2$, i.e. "$\in$" is a binary predicate. The axioms are logical sentences like $\forall A \, \forall B \, ( \forall X \, (X \in A \iff X \in B) \Rightarrow A = B)$ (Axiom of extensionality).

As an ontology, such a set theory has (at least) the following components:

a single type/class (sets),
a single interrelationship/relation (set $A$ is an element of set $B$ written as $A\in B$),
and a set of axioms/rules

Further attributes and relations can be defined based on these, for example

$\operatorname{singleton}(A) \iff \exists S \, (S \in A) \land \forall X \, \forall Y \, ((X \in A \land Y \in A)\ \Rightarrow\ X=Y)$
$A\subset B\ \iff\ \forall X \, (X \in A\ \Rightarrow X \in B)$

In single sorted first order predicate logic, you could use such attributes (as well as attributes that are part of the signature) to emulate further types/classes. One can also define constants (like the empty set $\{\}$) and functions (like union $\cup$) based on these. So individuals can be emulated as constants and function terms as functions.


Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$

The expression that you write means what can we say about $f(n) + g(n)$ such that $f(n) \in O(n^2 + n)$ and $g(n) \in \Omega(n^2 + n \log n)$. First, we can rewrite the inputs to $f(n) \in O(n^2)$ and $g(n) \in \Omega(n^2)$. Hence, the we can say $f(n) + g(n) \in \Omega(n^2)$.

However, we cannot say $f(n) + g(n) \in \Theta(n^2)$. As a counterexample, $f(n) = n$ and $g(n)  = n^3$.

Anyhow, if you want to say there is a function $f(n)$ such that it is in $O(n^2 + n)$ and also in $\Omega(n^2 + n \log n)$, you're right. Although if $f(n) \in \Theta(n^2)$, it is in $\Omega(n^2)$ as well.


Determining the minimum number of edges to add in order to be 3-connected

For this special case of $3$-connectivity, it has been solved by Watanabe and Nakamura. The algorithm runs in $O(n(n+m)^2)$ time, where $n$ and $m$ are the number of vertices and edges of the input graph, respectively.

There is a polynomial time algorithm to find the minimum number of edges to add to a $k-1$-connected graph to produce a $k$-connected graph. See chapter 3 of László A. Végh's PhD thesis. The thesis states that it is not known if adding a minimum number of edges to produce a $k$-connected graph is NP-hard in general.


Compression of non-adjacent structure using grammar

Grammar-based compression (context-free)  is alwasy looking for repetitions and is blind for other "patterns"..
In your example "XaXbXcYaYbYcZaZbZc" a position based compression should be more senseful.
For example the following "position rules" are generating your string..

  i=0,1,2:
  pos(X)=1+2i
  pos(Y)=pos(X)+6
  pos(Z)=pos(Y)+6
  pos(a)=2+6i
  pos(b)=pos(a)+2
  pos(c)=pos(b)+2

Rules like that can be stored efficiently and they are easy to decompress.
(In general the best compression is not computable since the so-called Kolmogorov-complexity is not computable. It is always a question of the type of compression..)


How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

Pathfinding algorithms that are able to recompute the best path when the graph changes without doing a full recomputation are called "Incremental".

The incremental version of Dijkstra's algorithm has the horrible name DynamicSWSF-FP.

The much more common algorithm which combines this with A* is called LPA*


Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts.
If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise the halting problem would also be decidable.
To see this, construct a Turing machine $M'$ that simulates $M$ while always moving its head. When the simulation terminates, $M'$ keeps its head in place for one more step, and then halts. It is not hard to come up with an algorithm that builds $M'$ from $M$, thus showing that $M'$ is computable.
Then $\langle M', w \rangle \in L$ if and only if $M$ does not halt.


The following pushdown automaton should do the trick. I publish this only because the existing answer can be improved upon. (Note, I am using $e$ to denote $\epsilon$- (or $\lambda$-) transitions.

The idea is that the left-hand part counts the number of $a$'s (modulo 2).
Each time it has seen two $a$'s, it pushes $3$ $b$'s onto the stack. Nondeterministically, the machine can change to the right-hand state. It then matches a $b$ from the string fro each $b$ on the stack.


A quick literature review suggests that the fastest algorithm for deciding whether a dense bipartite graph has a perfect matching is still the matrix algorithm, which runs in time $O(|V|^\omega)$. You can reduce the space of the algorithm, see Isolation, Matching and Counting by Allender, Reinhardt and Zhou. A recent paper from 2010, which focuses on planar graphs, suggests that the result of Allender et al. is the best that is known.


How to find LCA in a directed acyclic graph?

Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- parents (storing parents of each node).

Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using parents, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.
Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.
LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).


The textbook proofs of Greibach NF I have seen, contain endless substitutions. This way to construct GrNF is much crisper.

The key is to understand what the nonterminal $[Y,A]$ actually represents.
It means a derivation that has a leftward "backbone" which starts from $A$ and ends just before $Y$, as in the picture below.

Now the first production in $H$ can be explained as follows. If I start with $A$ and want to produce GrNF then I must generate a terminal. We choose to generate the leftmost terminal $a$ of the subtree under $A$. So, we produce $a$, but we still must find a derivation $[Y,A]$ of the form in the picture, where $Y$ is the nonterminal that actually produces $a$ using the available production $Y\to a$.


What are the practical uses of ontologies?

I don't know about robotics, but ontologies are part of the standard toolkit for modern expert systems, especially those with a natural language processing component.

For example, consider the process of performing literature searches for systematic reviews in medicine. Of the millions of medical studies out there, reviewers need to find the 20 or so high-quality randomised control trial studies which are relevant to the clinical question that they want to answer. This is a classic needle-in-a-haystack problem, and computer scientists would like to build tools to aid the search.

Medical ontologies such as MeSH, ICD, and GALEN play a role in this, because they represent an "answer" to the question of what a given medical study is "about".


Errors occur in programming because programs are written by humans and humans make errors.


You don't explain how $2^N$ is calculated, so I'm assuming you repeatedly multiply by 2 (or equivalently, you repeatedly add the number to itself, or shift it left). Here's how this process looks on a 4-bit signed register. You start with $0001$, the answer for $N=0$. Doubling it, we reach $0010$, the answer for $N=1$. Doubling again, we reach $0100$, the answer for $N=2$. Doubling again, overflow occurs (why?).

If the register was unsigned, we could double one more time, obtaining $1000$, the answer for $N=3$. Then we would overflow when doubling again (why?).

I believe you now have the tools to solve your own exercise. I won't verify your answer, so no point asking about it below.


Does the Hack computer from "The Elements of Computing Systems" use Von Neumann architecture?

I had the same suspicion going through the Nand to Tetris course.
Indeed, if you look at John K. Bennett's annotated version of "The Elements of Computing Systems", specifically Chapter 5, he calls this out:

The Hack architecture would more properly be called a “Harvard Architecture,” since the data and instruction memories are separate.

We can also do some digging for ourselves.
If we consult Wikipedia, it states that the Harvard architecture is distinguished by:

The term "von Neumann architecture" has evolved to mean any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time because they share a common bus.
The design of a von Neumann architecture machine is simpler than a Harvard architecture machine—which is also a stored-program system but has one dedicated set of address and data buses for reading and writing to memory, and another set of address and data buses to fetch instructions.

The latter is indeed the architecture of the Hack machine, which has two separate memories and can do an instruction lookup, data lookup, and computation all in one step* of the CPU. You can see this in the book's diagram:

Last, this is also explicitly stated at the end of Chapter 5 of the original book:

Unlike Hack, most general-purpose computers use a single address space for storing both data and instructions. In such architectures, the instruction address as well as the optional data address specified by the instruction must be fed into the same destination: the single address input of the shared address space. Clearly, this cannot be done at the same time.... In contrast, the Hack architecture is unique in that it partitions the address space into two separate parts, allowing a single-cycle fetch-execute logic.

*Note: In the Hack machine language, it actually takes two steps (e.g. @dataaddr then D = M + 1) to do an operation on data in memory. However, during the second instruction, both the instruction and the data in memory can be read by the CPU simultaneously.


Converting Boolean circuit to Boolean formula in parallel

Take a look at the Tseitin transform.  The Tseitin transform can be applied in parallel, working separately on each gate.  Consequently, this can be implemented using one processor per gate, $O(1)$ time per gate, and the resulting formula has size $O(m)$.  Here I'm not counting the time to build the final formula; the final formula is a conjunction of the clauses produced by the processors, with each processor adding $O(1)$ clauses to the final conjunction.


Please check my answer to a pseudocode CASE statement question

This problem is about switch-case statements. So, if you can do a pseudo code of such a statement with the case being a DAY variable and the steps are clear, that would be correct.
So, your answer is totally correct and steps are clear. There's no one way of doing pseudo code.

switch(DAY)
  case 1:
    print("Monday")
  case 2:
    print("Tuesday")
  case 3:
    print("Wednesday")
  case 4:
    print("Thursday")
  case 5:
    print("Friday")
  case 6:
    print("Saturday")
  case 7:
    print("Sunday")
  default:
    print("Invalid Day!")

Above is another possible way to a case statement for the DAY variable as your question expects.


Turing machine to output enumeration of a language

Here is one way to approach this problem. Program a machine that acts as follows:

Initialize the tape with $\#01$ (or $\epsilon\#01$).
At each step, write $\#$, then go back to the previous $\#$ and copy the string written there, say $0^n1^n$.
Change the first $1$ to a $0$, add two $1$s at the end, and go to the next step.


Complexity of k-way merge with log n arrays of size n / log n

First of all, notice that whatever you were doing, the complexity up to this point can not possibly be $o(n \log n)$. If that were true, we could merge each sorted subsequence in time $O(n \log \log n)$, violating the well known bound of $\Omega(n \log n)$ for the worst case of a general sorting algorithm. In fact, $$\Theta\left(n \log \frac{n}{\log n} \right) = \Theta(n \log n - n \log \log n) = \Theta (n \log n)$$

Now, let's analyze the complexity of what you are proposing. In order to visualize all the merging that's going on, imagine inserting each sorted subsequence into a FIFO queue. At each step, we take the first two sequences of the queue, merge them, and put the result at the back of the queue. We take note of the sequence that is initially in front of the queue, and define a round as the set of all merging operations that happen between two subsequent appearances of the initial sequence at the front of the queue.

Observe that each round splits in half the queue size: let's say there are $r$ rounds, with $r \in \Theta(\log \log n)$. Let $\alpha = \frac{n}{\log n}$. Before the $h-$th round begins, the queue contains $\frac{n}{2^h \alpha}$ subsequences, each of which has length $2^h \alpha$. Therefore, the complexity of round $h$ is:

$$
\Theta\left( \frac{n}{2^{h+1} \alpha} \left( 2^{h+1} \alpha \log (2^{h+1} \alpha) \right) \right) = \Theta \left( n \log (2^{h+1} \alpha) \right)
$$

This yields an overall complexity of:

$$
\Theta\left( \sum_{h=0}^{r-1} n \log (2^{h+1} \alpha) \right) =
\Theta\left( nr \log \alpha + n\sum_{h=0}^{r-1} \log 2^{h+1} \right ) =
\Theta\left( nr \log \alpha + nr^2 \right )
$$

Now, remembering that:

$$
\Theta \left( \log \alpha \right) = \Theta \left( \log n - \log \log n \right) = \Theta(\log n)
$$

We conclude:

$$
\Theta\left( nr \log \alpha + nr^2 \right ) = \Theta(n \log n \log \log n)
$$


Determine wether a set of sets contains a partition of a given set

Without loss of any really interesting aspect, we can assume that $S_i\subseteq G$ for all $i\in I$. Otherwise, we can we can remove each $S_i$ which is not a subset of $G$. This reduction step takes $O(ng)$ times, where $n=\sum_{i\in I}|S_i|$ and $g=|G|$.

Now that $S_i\subseteq G$, this problem is the exact cover problem, which is one of Karp's 21 NP-complete problems. You can find all sort of information about it at its Wikipedia entry.

I have played briefly a game called Pentomino, which is an exact cover problem.


Recursively enumerable but non recursive subset of an infinte recursive language

Hint. Let $S$ be any infinite recursive language. By considering, e.g., the lexicographic order, we can talk of the first, second, third, etc. strings in $S$. Use this indexing to define what you need to define.


Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

For fixed $k$, the running time is polynomial, but if $k$ is part of the input, the running time is not polynomial. The number of such subsets is ${n \choose k}$, which is very roughly like $n^k$.  Thus, if $k$ is fixed to something like 3, this becomes $O(n^3)$ -- polynomial.  However, if $k$ is part of the input, the running time is exponential in $k$.


Take it as an exercise to prove that P=coP. In fact, any deterministic computation model is closed under complement.

Regarding your second question, P-completeness is a well-studied notion, and there are even books on it. We say that a problem in P is P-complete if every problem in P is logspace-reducible to it. Assuming that NC is different from P, any P-complete problem is not in NC. Back in the day, the class NC was considered to represent what can be solved in parallel, so P-complete problems were interesting since they provably (under the assumption that NC is different from P) couldn't be solved in parallel. Nowadays this interpretation of NC is less popular.

You might be tempted to define P-completeness the same way NP-completeness is defined, that is, using polytime reductions. However, under this definition all non-trivial problems in P are P-complete, the two sole exceptions being the empty language and its complement, another simple exercise.


Example of height-balanced tree that is not weight-balanced

Take a complete binary tree of height 2 (with 7 vertices), and add two children to the two left leaves. The tree is height-balanced but the root is not weight-balanced.


Data structure for optimal deduplication of common subsets

What you're looking for here is the intersection of two classes of data structures:

Persistent data structures, in which modifying a structure doesn't eliminate access to the old structure. This ensures that the shared parts don't have to be stored twice.
Uniquely represented data structures, as required by your "one canonical representation" phrase.

Unfortunately, most persistent balanced tree data structures are not going to be uniquely represented. One that is uniquely represented is the sorted Braun tree, but they do not share a lot of structure, and two trees with $O(1)$ differences can have structures that are different in $\Omega(n)$ locations.

If you nest Braun trees within Braun trees, you can get this down to $O(\sqrt{n \log n})$.

However, since your symbols are 64-bit integers, you're in a good spot. You can use path-compressed tries, which have a unique representation. They use $\Theta(n)$ nodes to store a set of $n$ symbols, and adding or deleting a symbol to an existing set of symbols allows sharing almost all of the original structure: no more than $2 + \min(n,w)$ new nodes are created, where $w$ is the word width (64 for you).


Given a set of sets, what is the largest common intersection between them?

I understand the problem to be the following:

  Given sets $A_1,\dots,A_n$, find the largest $k$ such that there exist $k$ distinct indices $i_1,\dots,i_k$ that make $A_{i_1} \cap \cdots \cap A_{i_k}$ have a non-empty intersection.

This can be solved in $O(nm)$ time, where $m$ denotes the maximum size of any of the $A_i$. It suffices to find $x$ in $A_1 \cup \cdots \cup A_n$ that maximizes $|\{i : x \in A_i\}|$ (i.e., the number of sets $A_1,\dots,A_n$ that contain $x$).  When you've found this $x$, you can output the corresponding set $\{i : x \in A_i\}$ of indices.  You can output the intersection $\cap_{i : x \in A_i} A_i$ too if you want.

Naively, this might appear to take $O(n^2m)$ time.  However, the algorithm can be implemented in $O(nm)$ time, by scanning through the elements of the sets, maintaining a hashtable with a counter for each element $x$ that counts the number of sets it is contained in, and incrementing the right counter as you encounter each element.

The correctness follows from the fact that if $A_{i_1} \cap \cdots \cap A_{i_k}$ has a non-empty intersection, there must be some $x \in A_1 \cup \cdots \cup A_n$ that is contained in $A_{i_1} \cap \cdots \cap A_{i_k}$, and thus the algorithm above will find that combination of indices.


If repetitions are allowed, the problem is in P, as the (immediate) losing nodes are the ones with no outgoing edges, first find these, then declare the nodes winning from which you can reach such a node, if you can reach only winning ones, its a losing node, and so on, rest are drawing.


Linear programs with strict inequalities and supremum objectives

Suppose that the supremum of a continuous function $f(x)$ subject to $Ax < b$ is $c$, and assume furthermore that the constraints imply a bound on $\|x\|_\infty$. Thus there is a sequence of feasible points $x_n$ such that $f(x_n) \to c$. Since all points in the sequence have bounded norm, it follows that some subsequence of $x_n$ converges to a limit point $y$ satisfying $f(y) = c$ and $Ay \leq b$. This implies that in the bounded case, your problem is equivalent to classical linear programming.

In the unbounded case this argument doesn't work. For example, the infimum of $x-y$ subject to $x-y > 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.


Is this the right way of thinking about it?

No.

An NFA (with or without $\varepsilon$-transitions) accepts if there is any sequence of transitions that leads to an accepting state, regardless of whether there are other sequences that lead to non-accepting states.  If the start state is accepting, then the empty string is accepted because the null sequence of transitions (no transitions at all) leads to an accepting state. It doesn't matter that there are other sequences that lead to non-accepting states.

$\varepsilon$-transitions are annoying to define formally. Informally (but completely accurately), they just allow the automaton to change state without reading an input character.


Modeling a sequential circuit as a transition system

To build a transition system from a sequential circuit, in general, one needs to define three components:

the states of the transition system, which are all possible combinations of
values of your inputs and registers in the circuit
transitions between states in the transition system, which result from the functions that determine the output and the registers (according to used logical circuits and wire connections)
labels for states in the transition system, which consist of all variables and registers that are evaluated true given the valuations in the circuit

As per the (contrived) circuit in C2, the states reflect only the possible values of the single register. In turn, the function of the output equals to the register (Y2=R3), while the current value of the register is the negation of its previous value. This should give you enough insights to build the transition system.

The circuit given in C1 is indeed more convoluted, but it can be decomposed into functions on how values (for the registers and the output Y1) change, which then can be used to derive possible transitions in the system. (This is done with respect to possible changes of the input X.) For example, Y1 = R1 && R2 and the form for the value of R1 is R1 = (X AND ...) OR (... AND ...), while the missing values ... can be traced down according to the wire connections of the circuit.

More details on modelling sequential circuits as transition systems can be found in [1].

[1] Baier, Christel, Joost-Pieter Katoen, and Kim Guldstrand Larsen. Principles of model checking. MIT press, 2008.


Showing Regular Languages are closed under removal of rightmost character

This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$.

Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.


Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

This doesn't work, because the stacks of the two PDAs aren't synchronized.  You can get to a state where $\text{PDA}_1$ pushes a symbol but $\text{PDA}_2$ pops a symbol.  What is $\text{PDA}_{1,2}$ supposed to do at that point?  It's screwed.

The product construction would work if there was a guarantee that the length of the stack of $\text{PDA}_1$ was always the same as the length of the stack of $\text{PDA}_2$ -- but as explained, this is not guaranteed.

Another way to put it: Your definition of $\delta_{1,2}$ does not make any sense.  The output is supposed to be an element of $Q \times \Gamma^*$, where here $\Gamma = \Gamma_1 \times \Gamma_2$.  However, a pair like $(\lambda'_1,\lambda'_2)$ is not an element of $(\Gamma_1 \times \Gamma_2)^*$.  If the length of $\lambda'_1$ was the same as the length of $\lambda'_2$, you could interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$: it is the string whose $i$th symbol is $(\lambda'_1[i],\lambda'_2[i])$.  Unfortunately, when the length of $\lambda'_1$ is different from the length of $\lambda'_2$, there's no way to interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$.  Consequently, your definition of $\delta_{1,2}$ is not well-formed: it does not have the proper type signature.

As you quite accurately summarize the situation:  One stack can grow ad infinitum while the other not and in order to access the previous element from the shorter stack, the PDA would need to indestructibly go through the potentially infinitely long stack. This could be fixed if we had an automaton with two separate stacks; however, such an automaton would be computationally equivalent to a Turing machine and thus is more powerful than a PDA (which only has one stack).


How to encode date as input in neural network?

Neural Networks are not magic. If you treat them like they are and just throw data at them without thinking you're going to have a very bad time.

You need to stop and ask youself "Is milliseconds since 1970 actually going to be predictive of the event I'm interested in?" The answer you should arrive at immediately is no. Why? For every instance you actually care about (events in the future, the past already happened) the time variable will take on a value that is greater than any value the time variable will take in your training data. Such a variable is very unlikely to help. Even worse it is likely to cause overfitting (a serious problem for powerful non-linear models like neural networks) if you aren't careful.

Now what might make sense is a variable like week of the year or month that could help you model seasonal or annual effects. I've done some work in agricultural disease prediction where Julian day ended up being a very important variable. Based on this experience, I suspect you'd be better off encoding this type of variable as a categorical variable rather than ordinal, your experience may very. Notice that month or week of the year are repeatable events that one is likely to see many times in your training data and it is possible to explain why such a variable could impact a financial outcome. Contrast this with milliseconds since 1970 which is just a monotonically increasing value.

Lastly, from your statement "Or is feeding it the time unnecessary as long as I feed it the rest of the data chronologically?" it sounds like you might not have a very good grasp of how neural networks work. With a standard feedforward neural network the order you feed the network your data is going to have no impact on the predictions. Order may impact training if you're using stochastic or mini-batch gradient descent, but this is only an artifact of the iterative (as opposed to batch) training method. If you want to model temporal dependence with a neural network you'll need to use something like a sliding window or a recurrent neural network.


As you correctly point out, the original formula is valid (in every model either there is some element for which p or q doesn't hold, or p and q hold for all elements).

To prove that your formula is valid, you cannot use resolution directly. Recall that with resolution, you can derive the empty clause from a clause set iff the clause set is unsatisfiable. Your formula is valid iff its negation is unsatisfiable. So to prove your formula is valid, you have to derive the empty clause from the clause set corresponding to the negation of your formula.

Let $\varphi$ be your original formula. $$\lnot \varphi \equiv \forall_x \forall_y \exists_z (px \land qy \land (\lnot pz \lor \lnot qz))$$
Skolemization replaces $z$ by a function symbol $f(x,y)$:
$$\lnot \varphi \equiv_{SAT} \forall_x \forall_y (px \land qy \land (\lnot pfxy \lor \lnot qfxy))$$
The corresponding clause set:
$$\{\{px\},\{qy\},\{\lnot pfxy, \lnot qfxy\}\}$$
From there it should be straight-forward to derive the empty clause:

Apply renaming $\nu_1 = \{x/x_1\}$ to $\{px\}$, yielding $\{px_1\}$, then
resolve $\{p x_1 \}$ with $\{ \lnot pfxy, \lnot qfxy\}$ by $\sigma_1 = \{ x_1 / fxy\}$, yielding $\{\lnot q fxy\}$
Apply renaming $\nu_2 = \{y / y_1\}$ to $\{qy\}$, yielding $\{qy_1\}$, then resolve $\{qy_1\}$ with $\{ \lnot qfxy \}$ by $\sigma_2 = \{y_1/fxy\}$, yielding the empty clause $\Box$

In conclusion, we have shown by resolution that $\lnot \varphi$ is unsatisfiable. Therefore $\varphi$ is valid.


Difference between Dominant strategy and Winning Strategy

Your intuition seems mostly correct. However don't forget that not all games are winner vs. loser, see e.g. Coordination games. The meaning of a winning strategy is somewhat meaningless there, unless you define the winner to be the one with the greater outcome (or allow multiple winners which gain more than a certain threshold). Dominance is still an important tool for those strategies.

There is another problem, because your definition of domination includes "better" in any case. This is a strict dominance. A weak dominance means "at least as good as" in all cases and "better" in at least one case, where case means an opponents strategy (or a set of strategies for multiple opponents).

Possible outcomes are only $\{\text{win},\text{lose}\}$: A winning strategy for you results in $\text{win}$ for any strategy of the opponent and is thus weakly dominant compared to any non-winning strategy, if there is one. But in many games an opponent can play so badly, that some non-winning strategies lead to a win nevertheless and so they are not strictly dominated by a winning strategy. But more important than the dominance of winning strategies is the dominance between non-winning strategies of your opponent. If s/he has a weakly dominant strategy relative to all other strategies and you can win against this single strategy, you have a winning strategy.
Possible outcomes are some set linear ordered set $A$ and you win, if your profit is greater than that of the opponent (this is not a usual definition, one would use other tools like equilibria in this case). For example in the following table each player has two strategies and yours correspond to the rows (each cell is: your outcome, others outcome):
$$\matrix{10,12&\mid &10,12\\\hline\\7,4 &\mid&7,4}$$
If you choose the second strategy you'll always win and if you choose the first one, you'll lose, but your outcome is higher, so choosing row $1$ dominates a winning strategy.

Resumé: Dominance is a much broader concept and for many  but not all games winning strategies are weakly dominant to at least one other strategy.


How to get initial flow for TSP with missing edges

Set the cost on the missing edges to $+\infty$, or some suitably large constant.   Then all paths are valid, and you can apply simulated annealing.  Simulated annealing will have a very strong incentive to avoid those edges.

In general, you cannot expect any algorithm to both (a) be guaranteed to find a valid path, and (b) be guaranteed to terminate in a reasonable amount of time.  That's because finding a valid path is the Hamiltonian path problem, which is NP-hard -- so even finding a single path could be extremely hard, depending on the input graph.  Since you presumably want an algorithm that terminates in a reasonable amount of time, that means you'll have to accept the possibility that the algorithm fails to output a valid path.  (If not, then you'll have to accept the possibility that the algorithms fails to terminate in your lifetime, which seems just as bad.)


$\tilde \Omega$ for division by logarithmic factor

The notation $\tilde\Omega$ isn't completely standard, and should be explained whenever used. Usually it hides logarithmic factors, and in that case, what you wrote holds.


Simplified big O notation of $O(nm)$ for $n\gg m$

It depends what "$n$ is much greater than $m$" means but, in general, no. For example, one common definition of "much greater" is that $m=o(n)$. But, in this case, we can still have, e.g., $m=n^\epsilon$ for some $\epsilon<1$, or $m=\log^c n$ for any $c\geq 0$ and, in both of these cases, $nm\neq O(n)$.

To get $nm=O(n)$, you need $m=O(1)$.


I do not agree with the downvoters of your question. This questions seems like a legit misunderstanding of the statement of the min-cost-max-flow theorem.
The theorem states that the value of the sum of edge weights in a minimum $s$-$t$ cut of a graph is equal to the value of the maximum $s$-$t$ flow in the graph interpreted as a flow network. It does not establish a one-to-one correspondence between flows and cuts.
In fact, this correspondence cannot be established in general. Here is a counter example of an unweighted undirected graph (all weights/capacities are unit):

$1$-$5$ max-flow/min-cut is equal to one. While there is a single minimum cut ({1 - 2}). There are a lot of possible maximum flows (take the unit of flow entering 2 and distribute it between 3 and 4 as you like).


Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

It's one of those proofs that's essentially obvious once you can prove Fagin's theorem that the existential fragment of SO is exactly NP. Alternating quantifiers in the SO formula takes you up the polynomial hierarchy more or less by definition.

Proposition 7.35 of Libkin's Elements of Finite Model Theory proves that MSO expresses complete problems at every level of PH. Corollary 9.9 of the same book is that SO=PH; but the proof consists of a sketch with an exercise to fill in one of the steps.  The proof that SO=PH is also essentially Exercise 7.5.18 of Ebbinghaus and Flum's Finite Model Theory (2nd ed.). Immerman's Descriptive Complexity states the equivalence as Theorem 7.21 and Corollary 7.22 but leaves the proof as an exercise and credits the result to Stockmeyer's paper.

Given all of that, I doubt you'll find a proof in print. The details probably are fiddly but your outline sounds correct.


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

Claim: Yes, that statement is true.

Proof Sketch: Let $T_1,T_2$ be two minimal spanning trees with edge-weight multisets $W_1,W_2$. Assume $W_1 \neq W_2$ and denote their symmetric difference with $W = W_1 \mathop{\Delta} W_2$.

Choose edge $e \in T_1 \mathop{\Delta} T_2$ with $w(e) = \min W$, that is $e$ is an edge that occurs in only one of the trees and has minimum disagreeing weight. Such an edge, that is in particular $e \in T_1 \mathop{\Delta} T_2$, always exists: clearly, not all edges of weight $\min W$ can be in both trees, otherwise $\min W \notin W$. W.l.o.g. let $e \in T_1$ and assume $T_1$ has more edges of weight $\min W$ than $T_2$.

Now consider all edges in $T_2$ that are also in the cut $C_{T_1}(e)$ that is induced by $e$ in $T_1$. If there is an edge $e'$ in there that has the same weight as $e$, update $T_1$ by using $e'$ instead of $e$; note that the new tree is still a minimal spanning tree with the same edge-weight multiset as $T_1$. We iterate this argument, shrinking $W$ by two elements and thereby removing one edge from the set of candidates for $e$ in every step. Therefore, we get after finitely many steps to a setting where all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $w(e)$.

Now we can always choose $e' \in C_{T_1}(e) \cap T_2$ such that we can swap $e$ and $e'$¹, that is we can create a new spanning tree

$\qquad \displaystyle T_3 = \begin{cases}
  (T_1 \setminus \{e\}) \cup \{e'\},  &w(e') \lt w(e) \\[.5em]
  (T_2 \setminus \{e'\}) \cup \{e\},  &w(e') \gt w(e)
\end{cases}$

which has smaller weight than $T_1$ and $T_2$; this contradicts the choice of $T_1,T_2$ as minimal spanning trees. Therefore, $W_1 = W_2$.

The nodes incident of $e$ are in $T_2$ connected by a path $P$; $e'$ is the unique edge in $P \cap C_{T_1}(e)$.


In counterfactual regret minimization, why are additions to regret weighted by reach probability?

Algorithm 1, which I refer to in the question, produces a strategy that minimizes cumulative counterfactual regret.
The motivation is to get a strategy which minimizes overall regret (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy.
In other words, cumulative counterfactual regret was designed to be:

computable with a reasonable runtime; and
an upper bound on overall regret, so that minimizing cumulative counterfactual regret minimizes overall regret.

In Regret Minimization in Games with Incomplete
Information it is proven that overall regret is bounded by cumulative counterfactual regret. I'm reading through the proof currently, and will update this answer with an intuitive explanation if possible.
But for future readers who come across this, reading that proof could be a promising direction for understanding the motivation behind Algorithm 1 and the underlying formulas.


Yes, the root has a higher probability of collision.

Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.

The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the probability that $\langle h(A),h(B) \rangle = \langle h(X),h(Y)\rangle$. The probability of the second part is $p^{-2}$ and the probability of the first is $p^{-1}(1-p^{-2})$, for a total of $p^{-1} + p^{-2} - p^{-3}$, which is slightly greater than $p^{-1}$, the probability of a single collision.

That assumes all of your leaves have different values. If the leaves are all the same but one, the probability of collision at the root is proportional to the logarithm (base 2) of the number of leaves times the collision probability of the underlying hash function.


What does it mean by saying "Asymptotically more efficient"?

First off, both algorithms "work" for all inputs.  The question is about performance.

The answers to that question are kind of crappy.  One way to say one algorithm is asymptotically more efficient than another is if there is some (problem-specific) input size such that for any larger input size the more efficient algorithm will take fewer "computational steps", usually by some abstract measure, e.g. number of comparisons.

The idea of the answers is that an asymptotically more efficient algorithm may still require more steps before that input size.  It can be the case that the asymptotically more efficient algorithm requires fewer steps for all inputs, but it doesn't need to be the case and in practice usually isn't.  So a better wording of the "correct" answer would be "$X$ will be a better choice for all inputs except possibly small inputs".

The wording still isn't that great though.  First off, many more factors go into deciding what algorithm is a "better choice", but I'll give them that the intent is clear enough in this case.  The real issue is "small" and "large".  One of my favorite papers is The Fastest and Shortest Algorithm for All Well-Defined Problems. This paper describes an algorithm which given any specification of a function and a proof that it can be computed in polynomial time will compute that function in optimal time complexity within a factor of $5$ plus an additive term.  For example, if I provided it an implementation of bubble sort as the function specification and the simple proof that it was $O(n^2)$, it would produce a sorting algorithm that was $O(n\lg n)$.  In fact, it would produce an algorithm that was $5cn\lg n + o(n\lg n)$ where $c$ was the constant factor of the asymptotically* optimal algorithm. This is amazing.  There's just one problem: the constant term – hidden in the $o(n\lg n)$ in this example – renders the algorithm almost certainly completely infeasible for virtually any real problem.  What do I mean by "completely infeasible"? I mean the heat death of the universe will happen many times over before that algorithm completes.  Nevertheless, for suitably "large" inputs it will be faster than bubble sort.  My point is it's almost certainly not physically possible to write down by any means a "suitably large" input, let alone compute on it.

At any rate, how I would word the correct answer would be: "$X$ requires fewer steps than $Y$ on sufficiently large inputs".  This is still a bit vague as there are multiple notions of "step" that could apply and an algorithm could be asymptotically more efficient by one metric and less efficient by another.  This wording avoids the value judgement of "better choice"; there are many reasons to choose asymptotically less efficient algorithms or even less efficient algorithms when constant factors/terms are specified such as cache-efficiency or implementation simplicity.

* There is a subtlety here. The asymptotically optimal algorithm may have a worse constant factor, $c$, than an asymptotically non-optimal algorithm. I think it will have the best value of $c$ for any asymptotically optimal algorithm, but it's conceivable that to squeeze out a slight gain in asymptotic efficiency, massive complexity is added that significantly increases the constant factor.


Hash size: Are prime numbers "near" powers of two a poor choice for the modulus?

If a string of 8 bit bytes is interpreted as a large integer, and you calculate the value modulo $2^{24}-1$ then the first, fourth, seventh byte etc. are all hashed to the same value, which means the hash will not be well distributed.


Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$

The operation $I$ on two bits can be written as the identity matrix,
$$
I =
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1
\end{pmatrix}\,.
$$

The operation $Z_0Z_1$ that performs $Z$ on both qubits can be written as
$$
Z_0Z_1 =
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1
\end{pmatrix}\,.
$$

Now, the operation that you ask about, $\frac12(I+Z_0Z_1)$ is simply the operation described by

$$
\frac12(I+Z_0Z_1) =
\frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1
\end{pmatrix} +
\frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1
\end{pmatrix}
=
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &1
\end{pmatrix}\,.
$$
This indeed performs as you describe. If the $1/2$ wasn't there, we would get that $|0\rangle$ becomes $2|0\rangle$. Note that his operator is not unitary (it returns "$0$" for $|01\rangle$ and $|10\rangle$, which means the qubit "disappears", this shouldn't be allowed by quantum mechanics.)


Count all possible unions in a collection of sets

I found the answer here.
It is called the union closure and the complexity appears to be the same as computing the number of maximal independent sets in a bipartite graph.


Density of uniform distribution over two disjoint squares

The density $p_R$ of the uniform distribution over a rectangle $R$ is given by $p_R(x) = 0$ if $x \notin R$, and $p_R(x) = 1/\mathit{area}(R)$ otherwise. Indeed, up to scaling the distribution must have this form, and the choice $1/\mathit{area}(R)$ ensures that $p_R$ is a distribution.
In your case, you have a mixture of two such distributions: with probability $1/2$ you take a uniform point in $[1,2] \times [1,2]$, and with probability $1/2$ you take a uniform point in $[3,4] \times [1.5,2.5]$. The density function of the mixture is the average of the density functions of the individual distributions.


Name for tree where each node has the aggregate of its children

Such tree is called Sum Tree or SumTree, where the property is maintained in bottom up fashion. In general if the value is additional value (node property) for some existing one like AVL it is Sum augmented AVL Tree.

If the property is inherent, like maintaining the prefix sum, it would be Fenwick Tree.

As far as I know there is no established name, but for other functions it is partial statistics tree. preferable name would be Tree augmented with $f$, to make it explicit.


I have two news for you. I start with the bad one.

The dark side of the question

Computation theory tells us that checking whether two programs, or
program fragments, are equivalent is not decidable.

What that means is only that there is no unique technique that can
check that equivalence of any pair of programs. This remains true if
you consider a single programming language, as long as it is Turing
complete. (Note: I do not understand what you intend when mentionning
Turing complete algorithms in your comment - and, by the way,
precisions should be integrated in the question, preferably to
comments).

No unique technique also means no unique finite set of techniques as
they could be applied simultaneously. It also means no infinite set
of techniques that is finitely describable, etc.

This can be formally proved on Turing machine with Rice theorem (which
is a bit subtle to use). The proof can be tediously transposed to any
other Turing complete formalisation of computation. But invoking
Church-Turing thesis is usually considered enough.

To summarize it, there is no way you can produce a system that will
take two arbitrary program fragments of a Turing Complete language and
tell you when they are equivalent semantically, i.e. when their
computation results are the same.

But do not despair, there is hope.

The bright side of the question

While the above is true when you make the question so general, it does
not mean that this can never be done. Actually, this, or problems very
close to it, is the object of considerable reasearch. The
undecidability statement should only be seen as a limitation to what is to
be expected, but there is considerable room within that limitation.

So, there are many situation when it is actually possible to apply a
procedure that will actually decide whether two (fragments of)
programs are actually equivalent. The applicability of such a
procedure can be defined by a language (that is not Turing complete),
or by some limitation on the computational power such fragments can
express (so that they do not have to be in the same language).

Much of the research related to type theory also concerns provability
of programs properties, and can lead to answers to your question. But
that is much outside my competence.

Many other techniques have been developed for your purpose.

About your examples

Your idea of running both codes and comparing results is a good one,
at least in simple cases, like your example.

But you have to run the code symbolically, and then use a symbolic
computation system to check that the answers are indeed the same.

So, assume that initially a==$a$ and b==$b$, where I use italics for
symbolic expressions, i.e. non evaluated formulae. The symbols $a$ and $b$ just stand for themselves, and have no associated value.

running the first code:

a = a + b; - - so a==$a+b$
b = a - b; - -  so b==$(a+b)-b$
a = a - b; - -  so a==$(a+b)-((a+b)-b)$

Recall, again, that what is in italics is just symbolic expressions, trees if you prefer. There is nothing to be computed.

running the second code:

int temp = a; - -  so temp==$a$
a = b; - -  so a==$b$
b = temp;; - -  so b==$a$

Now you give these results to a symbolic calculator that check that
the values of variables a and b are the same at the end. It must be able to simplify expressions such as $(a+b)-b$ and $(a+b)-((a+b)-b)$ to respectively $a$ and $b$, which requires using known algebraic properties of the operators $+$ and $-$.

It is actually a good technique (when applied properly - I goofed my first try),as it allowed me to notice that your two codes were not equivalent, and I corrected the first one.

Running the code symbolically is an example of a general paradigm
called abstract interpretation. The "casting out nines" test is a very
elementary example of these techniques.

Symbolic evaluation and abstract interpretations are a well
studied way of proving things about programs.

It is pretty much what is done by type checkers.

But it is far from the whole story about proving things about programs.
Large systems are being developed to prove properties of programs by
different means.

In other cases (probably for your sorting examples), it may be better to have a specification of what the
program is supposed to do and separately prove the two pieces of code
conformant with that specification. This avoid having to consider
simultaneously the specifics of two algorithms.


Does the underlying computational calculus in type theories affect decidability?

I don't think that the term "modern" helps distinguish anything.  One way to explain is to draw a distinction between "behavioral", or "semantic", type theories and "formal", or "syntactic", type theories.

Behavioral type theories start with a notion of computation (say, an operational semantics of some kind), and define types as descriptions of program behavior, ie specifications.  For example, one might specify that a function takes primes to primes as a description of how it behaves.  Membership in a type is a matter of truth, not formal proof, and is never remotely axiomatizable, by Gödel's Theorem.

Formal, or syntactic, type theories are given by a collection of rules, including axioms as no-premise rules.  They are inherently recursively enumerable, and never come close to any notion of truth.  In particular such type theories, which often enjoy a (n empty) correspondence with a logical system (the poorly named C-H Correspondence), have no inherent meaning, computational or not.  They are mere formalisms.

The two concepts may be linked by stipulating a priori that programs must be "well-typed" in the formal sense, with specifications of behavior refining types (for example, isolating the primes among the naturals). There are good reasons to take this viewpoint, namely that the rules prevent you from writing the code that you didn't want to write (eg, enforcing abstraction boundaries).  But they also prevent you from writing the code that you do want to write (they define up-front what are the programs).  The benefit of such restrictions is something called "the fundamental theorem", which states that syntactically well-formed programs enjoy behavioral properties associated to their types, a generalization of "type safety".  In particular, the parametricity theorem is an example; it expresses that abstraction is properly enforced.


Results on the languages recognized by undirected DFAs

I can only give a partial answer. Let $\mathcal{S}$ be the class of all regular languages recognized by a complete SDFA. Then $\mathcal{S}$ is a subclass of the class $\mathcal{G}$ of group languages. A group language is a language  whose syntactic monoid is a finite group , or equivalently, recognized by a finite permutation automaton (each letter induces a permutation on the set of states). The inclusion $\mathcal{S} \subset \mathcal{G}$ is strict. However, the following result holds, showing that $\mathcal{S}$ is a kind of generator for $\mathcal{G}$:

For every group language $L \subseteq A^*$, there is an alphabet $B$, a monoid morphism $f: A^* \to B^*$ and a language $K \subseteq B^*$ in $\mathcal{S}$ such that $L = f^{-1}(K)$.

Proof. Let $\mathcal{A} = (\{1, ..., n\}, A, \cdot, 1, F)$ be a permutation automaton recognizing $L$. It is a well-known fact that the group of all permutations on $\{1, ..., n\}$ is generated by the set $B$ of its transpositions (a transposition permutes two states and fixes all the other states). By construction, the automaton $\mathcal{B} = (\{1, ..., n\}, B, \cdot, 1, F)$ is a SDFA and hence recognizes a language $K$ of $\mathcal{S}$. Now, for each letter $a \in A$, there is a word $u_a \in B^*$ which defines in $\mathcal{B}$ the same permutation as $a$ in $\mathcal{A}$. Let $f: A^* \to B^*$ be the morphism defined by $f(a) = u_a$ for each letter $a \in A$. It should now be clear that $f^{-1}(K) = L$.

The class $\mathcal{PS}$ of languages recognized by a partial SDFA is of course larger than $\mathcal{S}$, but does not exhaust the class of all regular languages. Actually, one can show that if $L$ is in $\mathcal{PS}$, then the syntactic monoid of $L$ is an inverse monoid and in particular, its idempotents commute. This latter property is shared by the slightly larger class of reversible automata. See

J.-É. Pin, On the languages accepted by finite reversible automata, in 14th ICALP, Berlin, (1987), 237-249, LNCS 267, Springer Verlag


"State of the art" algorithms deciding entailment of propositional formulas?

Checking whether $P \Rightarrow Q$ is the same as checking that $P \land \lnot Q$ is unsatisfiable. Using the Tseytin transformation, you can convert $P \land \lnot Q$ into a form suitable for a SAT solver.
Conversely, satisfiability is a special case of your problem, since $P \Rightarrow \bot$ iff $P$ is unsatisfiable.


Time complexity of arithmetic operations

Your question is excellent! Unfortunately, my answer might disappoint you: the complexity of arithmetic operations depends on the computation model; to some extent, it's up to you to decide how much does it cost to add or multiply two numbers. Usually when analyzing algorithms, we assume the unit cost RAM model, in which arithmetic operations on two "reasonably sized" integers takes time $O(1)$. Here "reasonably sized" means of length $A\log n$, or equivalently, of absolute value at most $n^A$ (here $n$ is the size of the input). The constant $A>0$ should be fixed per algorithm. Its exact value doesn't matter, since we can simulate arithmetic operations on operands of size $m^2$ using $O(1)$ arithmetic operations on operands of size $m$.

In some cases, we have to do arithmetic on large integers. This happens in cryptography, for example. When adding or multiplying large numbers, operations no longer take $O(1)$ even in the unit cost RAM. For example, adding $m$-bit integers takes time $\Theta(m)$, and the best known algorithm for multiplication runs in $\tilde{O}(m\log m)$ (the tilde hides smaller multiplicative factors).

In most elementary algorithms, large integers do not show up, so you can just assume that arithmetic operations on variables take constant time. This is intended to be the case in all your examples.


Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

A lot of research in this area has been done, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection.
A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse a tree without stack. However, an extra bit per node is necessary to distinguish threads from child-pointers.
Wikipedia:Tree_traversal
As far as I know binary trees implemented using pointers in the usual fashion (left and right pointer per node) can be traversed using the method of threads, in a method attributed to Morris. The NIL-pointers are temporarily re-used to thread a path back to the root. The clever part is that during traversal one can distinguish the original edges from the temporary thread-links, using the way they form cycles in the tree).
Good part: no extra data structure. Bad part: slightly cheating, the stack is inside the tree in a clever way. Very clever.
A proof of the hidden stack is shown in P. Mateti and R. Manghirmalani: Morris's Tree Traversal Algorithm Reconsidered DOI:10.1016/0167-6423(88)90063-9
J.M. Morris: Traversing binary trees simply and cheaply. IPL 9 (1979) 197-200 DOI:10.1016/0020-0190(79)90068-1
Then there also is Lindstrom scanning. This method "rotates" the three pointers involved in each node (parent and two children). If you want to perform any decent pre-order or post-order algorithms you need extra bits per node. If you just want to visit all the nodes (three times, but you never know which visit you perform) then it can be done without the bits.
G. Lindstrom: Scanning list structures without stacks or tag bits. IPL 2 (1973) 47-51. DOI:10.1016/0020-0190(73)90012-4
Perhaps the most straightforward way is a method by Robson. Here the stack needed for the classic algorithm is threaded through the leaves.
J.M. Robson: An improved algorithm for traversing binary trees without auxiliary stack IPL 1 (1973) 149-152. 10.1016/0020-0190(73)90018-5
IPL = Information Processing Letters


Can the reproduction function of an evolutionary algorithm consider gene strength?

Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen?

Of course it can.

Anyway, consider that in GA this already happens implicitly. Using the established methods and genetic operators of genetic algorithms (not only reproduction but also crossover and mutation) the Holland's schema theorem states that low-order schemata with above-average fitness increase exponentially in successive generations.

(a schema is a template that identifies a subset of strings with similarities at certain string positions)

In Genetic Programming things are different:

GA representations are often fixed size whereas GP representations and usually variable sized;
GA normally have a semantic interpretation for a given location in a chromosome while GP solutions often do not exhibit location dependent meanings.

John Koza attempted to explain why genetic programming works by extending Holland's schema model and theorem to GP but with various differences / limitations (the class of problems and problem representations for which block processing is useful remains a challenging and open research topic in GP).

In GP your idea is the base of the modularization approach, e.g.

The encapsulation operation is a genetic operation that identifies a
potential useful subtree and gives it a name so that it can be referenced and used later (see Genetic Programming: On the Programming of Computers
by Means of Natural Selection)
Better yet, Adapting Representation through Learning (ARL). With ARL New subroutines are created using blocks of genetic material from the pool
given by the current population.

The detection of what are salient blocks of code is based on two notions: differential offspring-parent fitness and "active" blocks.

The process of discovering building blocks and creating new subroutines based on simple blocks of code is applied recursively so that subroutines of
any complexity can be discovered.

Subroutines beneficial to some individuals could be invoked also by other individuals. The end result is the collection of subroutines that acquires the necessary structure for solving the problem (take a look at Towards Automatic Discovery of Building Blocks in Genetic Programming by Justinian Rosca for a complete description).


Here's a simple proof of the non-computability of the Busy Beaver function:

Assume BB is computable. Then we can build a program that accepts a TM specification M and input x. Compute n = BB(|M|), where |M| is the number of states of TM M. Next, simulate M(x) for n time-steps. If M(x) halts, accept. If after n time-steps M(x) has not halted, reject. This program solves the Halting-Problem, a contradiction - QED.


Proving optimality of a dynamic programming algorithm

Since you're asking how to construct a proof of correctness, I'll give you some tips to get you started.  If you do all of these, I think you'll be able to make a lot more progress.

As Raphael suggests, make that you can write a recurrence relation for the solution.  You don't yet have a recurrence.  A recurrence is an equation for $DP[i][j]$ that is written solely in terms of $i,j,s$ and other "earlier" values of $DP[\cdot][\cdot]$.  Your equation involves a variable $k$, but what is $k$?  Where'd that come from?  It comes out of the blue.  How do we choose $k$?  You haven't yet given us a formula that computes $DP[i][j]$.  Until you do that, you can't possibly hope to prove your algorithm correct.  In fact, until you do that, you don't even have an algorithm!

Hint: I think you'll find you want to write something like

$$DP[i][j] = \min \{...\text{something}... : k=i-1,i,i+1,\ldots,j-1\}.$$

You fill in the $\text{something}$ part.  In short, I recommend that you formulate your recurrence more accurately.

Hint: try writing out the pseudocode for your dynamic programming algorithm, in standard form.  This will force you to write a recurrence for $DP[i][j]$.
Once you have a recurrence, your next step is to prove that it is correct.  Why does it give the correct answer for your problem?  Justify why the recurrence is correct.  Here you might use proof by induction.

See Raphael's answer, which gives an excellent overview for how to prove a dynamic programming algorithm correct.

I recommend that you review the proof of correctness for a few other dynamic programming algorithms.  (Look in a few standard algorithms textbooks; with any luck, they should show you several examples.)  You'll see that they have a similar structure, and this should help you structure your proof.
One more tip that will be very helpful.  You write "I assume (...)".  You might try proving that the "(...)" statement is true.


Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible.

Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum.
Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ except $x$.

If $c(x)\le 1 + \sigma$, return 0.
Else return $p(x)(c(x) -\sigma))$, where $p(x)$ is the penalty associated with $x$.

The time-complexity of the algorithm is $O(\ell)$, where $\ell$ is the sum of the length of $m$ and the length of $n$.

Since the algorithm above is simple and clear, there is no need to apply the heavy machinery of dynamic programming.

Exercises

Here are two exercises that prove the correctness of the algorithm above.

Exercise 1.  If $s(x)\le 1 + \sigma$, design a procedure to produce a merged array that does not have adjacent pairs of the same letter.

Exercise 2.  If $s(x)\gt 1 + \sigma$, then any merged array must have at least $s(x) -\sigma$ $x$s each of which is adjacent to another $x$. Design a procedure to produce a merged array that has no other penalties except for $s(x) -\sigma$ $x$s.


This is impossible. For large enough $n$, all your threshold gates will be "saturated", that is, they will have the same output on all large enough $n$, and in particular won't be able to distinguish between $n$ and $n+1$.


What is required for universal analogue computation?

I don't think the question can be answered unless we have a definition of what kind of computations we are talking about.

Universality of a machine model w.r.t. a class of computationw means that any computation in that class can be computed by a machine. Unless you define the class of "arbitrary analogue computations", we cannot answer what is universality w.r.t. to them.

Now, the functions you have listed will only give you polynomials and their quotient which is a rather small class of real functions, you cannot even compute simple functions like $2^x$, $\lfloor x \rfloor$, $\sqrt x$, ... using them.

If your question is if there are physical systems that starting from an initial state will reach another state in some time and if that is always computable, then the answer depends on what kind of physics we are talking about, and what it means to set up an initial configuration and observing the result, etc.

If we are just talking mathematically about classical physics (we can set any initial configuration to infinite precision and without any considerations about things like energy needed to set up the configuration and observing the result is similarly from mathematical point of view) then it has been know for long time that there are differential equations about computable functions s.t. their solution is not computable, see Marian B. Pour-El, and J. Ian Richards, "Computability in Analysis and Physics", 1989.

An interesting case is if the n-body problem is computable (and if I remember correctly the answer is no, at least for $n>4$).

Generally, if we can just check equality of two real numbers that gives a function which is not continuous w.r.t. typical typologies of information about real numbers and therefore cannot be computed by a Turing machine since any function (including higher type functions) that a Turing machine can compute is continuous (w.r.t. the topology of information).


Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n))

Let $d(n) = 2n$ and $e(n) = n$. Then
$$d(n)-e(n) = n.$$
Since $d(n) = O(n)$ and $e(n) = O(n)$, we have that $$f(n) = g(n) = n,$$
so
$$O(f(n)-g(n)) = O(n-n) = O(1),$$
and clearly $$n \neq O(1).$$


Before I go straight to your question, we have to get a clear picture of these two terms that might seem confusing;

1.rationality(an agent is able to perform given task x after analysing y,that is right fit for x).

2.intelligence.(an agent is able to perform given task x after analysing y inline with reasoning ie..why x?....).

could Goal-based agents be a rational agents at the same time ?
Basing on the above two hints,the answer is yes.

Does this concept limit intelligence to just human intelligence ?
According to artificial intelligence research,so far,we haven't reached at the level of human intelligence (artificial general intelligence).

Hope this can give you some insights.


"Unusual" coupling between a decision problem and a corresponding optimization problem

The answer does indeed depend on how you define a "corresponding" problem.

For example, it is well known 2-SAT is easy ("Given a 2-SAT formula, is it satisfiable?"). However, the optimization problem MAX-2-SAT ("Given a 2-SAT formula, find an assignment maximizing the number of clauses") is NP-hard. Even MIN-2-SAT is NP-hard.

For a given decision problem, you can have "corresponding" optimization problems which are either easy or hard, depending on whether we consider a minimization or a maximization problem. The st-connectivity problem is mentioned in the comments: deciding the existence of such a path is easy, finding a shortest st-path is easy, but finding a longest st-path is hard. Another graph theoretic example is with cuts: computing a minimum cut is easy, but computing a maximum cut is again hard.

You also have decision problems that don't have a corresponding optimization problem, such as primality testing.


Could a modification of Krom's proof system be used to solve 3-SAT in polynomial time?

Any proof in KPS (with whatever rules) can be rephrased as a sequence of lines, each of which is either a clause or follows from preceding lines according to one of finitely many inference rules. Additionally, the lines come from one of finitely many "patterns" (formulas with placeholders to variables), and so all proofs are polynomially bounded.

Suppose that the maximum depth of a pattern is $d$. Then your proof is also a proof in depth $d$ Frege. It is known that the pigeonhole principle needs $2^{\Omega(n^{1/5^d})}$ lines to refute in depth $d$ Frege. This implies that KPS systems cannot be complete for 3SAT, since all proofs in KPS are polynomially bounded.


This is addressed in the relevant information you quoted, specifically in the following sentence:

  Each stimulus was converted into 16 primitive numerical attributes (statistical moments and edge counts) which were then scaled to fit into a range of integer values from 0 through 15.

Many machine learning algorithms won't be successful with the raw raster data, instead requiring features such as the 16 "primitive numerical attributes" mentioned above. (Deep learning algorithms should work correctly with the raster data, though.)

Computing these numerical attributed is a one-way process: you cannot recover the glyph from its statistics. We compute these statistics since we think they are the salient features which distinguish one letter from another.


What kind of logarithm does $\log$ mean in Wikipedia articles?

It depends entirely on context. In mathematics as a whole, $\log$ usually denotes the natural logarithm (base $\mathrm{e}$). In computer science, the situation isn't as clean because we often want to talk about things like a number of bits or the height of a binary tree and, in those cases, the most natural (*baddum-tsh*) logarithm to use is base-$2$.  Some authors use $\ln$ and $\lg$ to explicitly denote base-$\mathrm{e}$ and base-$2$ logs, respectively; many authors just write $\log$ to mean whatever base is most appropriate for the situation.

Of course, Wikipedia is written by a huge number of unconnected authors, so you can't assume any consistent convention is used. Indeed, a careful Wikipedia editor would make sure that $\log$ is used consistently within an article, but you can't rely on everyone being careful.

It usually doens't matter. Changing the base of a logarithm just multiplies the answer by a constant factor because, for all $a,b>1$ and all $x>0$,
$$\log_a x = \frac{\log_b x}{\log_b a}\,.$$
In many situations, this multiplicative factor of $1/\log_b a$ isnt at all important. In the context of a big-$O$, big-$\Theta$, big-$\Omega$ etc bound, $O(\log n)$ means the same thing regardless of the base, since big-$O$ disregards constant factors. (But note that, e.g., $2^{\log_2 x}=x$, whereas $2^{\log_3 x}=x^{1/\log_2 3}\approx x^{1.58}$ so there are situations in which the base makes a big difference.)

Your specific example. In a comment, you say you're specifically interested in the page about tf-idf. I know nothing about document retrieval but my understanding from skim-reading that article is as follows. We're interested in ranking documents according to their relevance, and the relevance of a document is given by a score of the form $x\log y$, where $x$ and $y$ are statistics of the document. Since changing the base of the logarithm just multiplies all the scores by a constant, it doesn't change the ranking order. Therefore, it doesn't matter what base you use for the logarithm in this situation.


How do I verify that a DFA is equivalent to a NFA?

This is a problematic question. There is a way to check equivalence of automata, which I'll now explain, but I'm afraid it won't help you, as you will see at the end.

Recall that two sets $A$ and $B$ are equal iff $A\subseteq B$ and $B\subseteq A$ (this is the definition of set equality).
Thus, it is enough for you to verify that $L(D)\subseteq L(N)$ and $L(N)\subseteq L(D)$, where $D$ and $N$ are your DFA and NFA, respectively.

But how do you check containment of languages, you might ask. Well, now observe that $A\subseteq B$ iff $A\cap \overline{B}=\emptyset$ (where $\overline{B}$ is the complement of $B$).

Let's consider first checking whether $L(N)\subseteq L(D)$. To do this, you need to complement $D$ (very easy - swap the accepting an rejecting states), then construct the intersection automaton (e.g. with the product construction) with $N$, and check for emptiness, by finding a path to an accepting state.

The converse direction, however, will show why this doesn't help you. In order to check whether $L(D)\subseteq L(N)$, you need to complement $N$. But in order to complement an NFA, you first need to convert it to a DFA, rendering the whole idea pointless.

Essentially, the problem with your question is much deeper: you want to verify that you (an undefined computational model) executed a well-defined algorithm properly. So this is not really a computer-science problem.

I will say this: following the constructions I suggested, it is not hard to conclude that $L(D)\neq L(N)$ iff there is a word of length at most $2^{2n}$ ($n$ being the number of states of $N$) that is accepted by one and not by the other. So you can try all words up to this length.


How is Memory Access Time of Processor calculated?

The 8088 is $16 bit$ microprocessor with $8 bit$ data bus, it requires $2$ cycles to access word. During the second read counter is automatticaly incremented. In 8088 $1$ cycle is needed to apply valid physical memory address (and read or write). The missing $1$ cycle is for preparation. The cycles are not calculated, simply read from specification steps performed.

Cycle:

acquire valid address to address bus.
RD (or WR) signal is issued, DEN is asserted (if WR then data is put onto the data bus). DEN connects data bus buffers to external data.
allow memory to access data, if RD the data bus is sampled ot the end of cycle.
bus signals are deactivated, data sampling is finished (RD). If WR data is transfered to memory.


Yes.  Every* problem in $P$ can be reduced to any other problem in $P$ using polynomial-time reductions (since the reduction is allowed to do polynomial work, it can just solve the problem itself).

If $P=NP$, then it follows that every* problem in $NP$ can be reduced to any* other problem in $NP$ -- in other words, every* problem in $NP$ is $NP$-complete.  This implies that if $L \in P$ and if $P=NP$ then* $L$ is $NP$-complete.

Footnote *: There is an exception for the empty language ($\emptyset$) and the universal language ($\Sigma^*$).  For purposes of gaining a rough conceptual understanding, this technical detail can probably be safely ignored.


Can a 3 Color DFS be used to identify cycles (not just detect them)?

The moment you find a grey node, you have the edge that closes the cycle in hand. All other edges are part of the DFS tree. That is, store the "cycle-closing" edge and obtain the rest afterwards.

That is, assuming that those are the cycles you are interested in. Other cycles (such that contain more than one non-DFS-tree edge) are more complicated, but I don't think those are easy to cover. A directed graph may have super-exponentially many cycles, so you can't expect to list them all with a simple, linear-time traversal.


$\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

The goto table is only used immediately after a reduction action, which has just restored the parser state to the state in which the reduced non-terminal follows the dot. So the goto table for that state must have a state transition for that non-terminal; it's not an error entry.
So the error entries are never consulted.


Intuition why $ L= \{\langle M \rangle| \ L(M)=\Sigma ^* \}\notin RE $

The class RE contains all languages $L$ which can be expressed in the form
$$
x \in L \Longleftrightarrow \exists y \, P(x,y),
$$
for some computable predicate $P$.

Your language can be expressed in the following way:
$$
\langle M \rangle \in L \Leftrightarrow \forall x \exists t \, \text{"$M$ halts on $x$ after $t$ steps"}
$$
The quoted predicate is computable. This puts your language in $\Pi_2$, a level on the arithmetical hierarchy. There seems to be no natural way to come up with a simpler expression (less quantifiers), and this is why, intuitively, the language is not r.e. This kind of intuition usually works – write down an expression for your language in the most natural way, and this usually puts it in the correct level of the arithmetical hierarchy.

Your language is in fact $\Pi_2$-complete – every language in $\Pi_2$ can be reduced to it. Indeed, suppose that
$$
x \in L' \Longleftrightarrow \forall y \exists z \, P(x,y,z),
$$
where $P$ is computable. Given $x$, you can construct a Turing machine which on input $y$, goes over all $z$ in parallel, determines the value of each $P(x,y,z)$, and if it ever finds a value of $z$ such that $P(x,y,z)$ is true, it halts. This construction gives a reduction from $L'$ to your language.

Since your language is $\Pi_2$-complete, we know that it is not in $\Sigma_1$ (another name for RE), since the arithmetical hierarchy is strict. This means that there is no way to describe the language using fewer quantifiers (or using $\exists\forall$ rather than $\forall\exists$).

Your language is usually known as TOT, the language of all total Turing machines.


What's wrong with the following shuffle algorithm?

This approach cannot work, for the following simple reason. The probability to obtain any permutation is of the form $A/n^n$, for integer $A$. However, we need it to be $1/n!$, so we need $A = n^n/n!$. Unfortunately, for $n \geq 3$ this is not an integer.

One can still ask why we might expect this algorithm to work, and where is the gap between our intuition and reality.
After the $i$'th step of the algorithm, $A[i]$ is a uniformly random element. So if we randomize $A[0]$, then $A[1]$, then $A[2]$, and so on until $A[n-1]$, won't we get a random permutation?
While it is true that $A[n-1]$ will be completely random, this is not the case for other entries. Indeed, let us try to analyze the distribution of $A[0]$ as the algorithm progresses.
After the first iteration, $A[0]$ is uniformly random.
After the second iteration, $A[1]$ is uniformly random, but this comes at a cost: we might have swapped $A[0]$ and $A[1]$. This means that $A[0]$ will have a slight preference towards $1$ (the original value of $A[1]$) and $0$ (the value of $A[1]$ in case it was swapped with $A[0]$).
Quantitatively, after the second iteration, if $i > 1$ then
$$ \Pr[A[0] = i] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) = \frac{1}{n} - \frac{1}{n^2}, $$
since this happens when $A[0]$ was swapped with $A[i]$, and $A[1]$ was not swapped with $A[0]$. Similarly,
$$ \Pr[A[0] = 0] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n}, $$
accounting for the additionally possibility in which $A[1]$ is swapped with $A[0]$ in the second round. Finally,
$$ \Pr[A[0] = 1] = \frac{1}{n} \cdot \left(1 - \frac{1}{n}\right) + \left(1 - \frac{1}{n}\right) \cdot \frac{1}{n} = \frac{2}{n} - \frac{2}{n^2}, $$
accounting for the possibility that $A[0]$ was not swapped with $A[1]$, but $A[1]$ was swapped with $A[0]$.
Similar phenomena persist throughout the algorithm.


Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?

When $k = 1$ then answer is $M!$ (why?). In the general case, an explicit formula is probably too much to hope for, but it is possible to obtain asymptotics. For example, in this answer Brendan McKay shows that for $k=2$, the number of ways is asymptotically $e^{-5/2} (2n)! 4^{-n}$ when the diagonal is always zero. Without the condition on the diagonal, the answer will be $e^{-1/2} (2n)! 4^{-n}$ (I think). The same method, known as the configuration model, should give asymptotics for arbitrary $k$.


How to find the alphabetically min and max of substrings that begin with [a, b, c, d, e] and end with [h, i, j, k, l, n]

Find the last occurence of any h, i, j, k, l, n. If none is found, there is no solution. If the last one is found at position r, then the string we are looking for must start at position before r.
Then you start from the left looking for the first letter among a, b, c, d, e. If you don't find one before position r then there is no solution. Otherwise call this index l; the first string in the alphabet might start at index l.
Look further for more characters starting with a to e. If you find one at position l', you then find the first difference between the string starting at l and l', up to and including position r. If there is a different character, and the first character in the string starting at l' is earlier in the alphabet, replace l with l'.
Finally, the first string in the alphabet is the one starting at position l, and up to and including the first letter in 'h' to 'n'.


Recursive functions from O(n) complexity to O(log n)

r1 = reverse_string2(s[:mdpt])
   r2 = reverse_string2(s[mdpt:])

Here you go in recursion twice. In both recursions you will again recurse twice, etc, which makes $2*2*2... = O(2^{\log n}) = O(n)$. So the complexity is the same.