Partial Range Query on Inverted File with Combined Index

I don't think you've got the idea for an inverted file quite right.  If there are three attributes (X, Y, and Z), the natural approach is to have three inverted lists:

The first list maps from the value of X to the record (or from the value of X to the Name, if the Name is unique for each record and is how the record is identified).
The second list maps from the value of Y to the record (or from the value of Y to the Name, if the Name is unique for each record).
The third list maps from the value of Z to the record (or from the value of Z to the Name, if the Name is unique for each record).

So, if there are three attributes, we might end up with three inverted files.

See Figure 1.2 in the book for an example of an inverted file.

Now for the idea of a combined index.  A combined index for the attribute ordering XYZ would be a sorted list of records, where the sort order works as follows:

If two records differ in their X attribute, then order them by the value of their X attribute (and ignore their Y,Z attributes).
If two records have the same X attribute but differ in their Y attribute, then order them by the value of their Y attribute (ignoring their Z attribute).
If two records have the same X and Y attributes but differ in their Z attribute, then order them by the value of their Z attribute.

This is known as lexicographic order, where the attributes are taken in the order X,Y,Z.  You can think of this as XYZ-lexicographic order.  Once we sort using this particular order, we get a combined index for the attribute ordering XYZ.

Of course we could also form a combined index for other attribute orderings as well.  We might form multiple combined indices, each with a different attribute ordering.  The order in each combined index is different.  If there are $n$ attributes, we could have up to $n!$ different combined indices, corresponding to the $n!$ different permutations (orderings) on the $n$ attributes.  Nothing says we have to store all of those possible combined indices; we could store just one of them, or some of them, or all of them, or none of them.

A combined index is different from an inverted file.

However, you might notice that if you have a combined index for attribute order XYZ, then this obviates the need for an inverted file for attribute X, since you can use the combined index for XYZ in any place where you would have wanted an inverted file for X.

This is all explained pretty clearly in the book you cited.  I recommend you work through the example in Figures 1.1 and 1.2 in the book, to better understand inverted lists.


As is often the case, using a formal definition is helpful:

Let $V$ a finite set. $G=(V,E)$ is

a graph if $E \subseteq \left\{\{v_1, v_2\} \mid v_1, v_2 \in V \right\}$ and
a digraph if $E \subseteq \left\{(v_1,v_2) \mid v_1, v_2 \in V\right\}$.

Note the central difference: edges are sets in graphs and pairs in digraphs. In particular, simpleness is implied by this definition. Extending the definition is also easy:if $E$ was a multiset, you could have non-simple graphs. If the edges had more than two components, you'd have hypergraphs.

Disclaimer: People define (di)graphs in different ways; this is one very common variant. For example, if you are uncomfortable with digraphs (formally) not being graphs, you define them like this:

Let $V$ a finite set and $E \subseteq V^2$. We call the pair $G=(V,E)$ a graph. We say

$G$ is undirected if and only if $(v_1,v_2) \in E \Longleftrightarrow (v_2,v_1) \in E$ and
$G$ is directed otherwise.

This defines undirected graphs as special cases of directed graphs. Note that with this definition, extensions to labeled graphs (edges get markings) may be awkward: We want the complete digraph with to be different from the complete undirected graph (as the former has two labeled edges between between every pair of nodes, the latter only one); by this definition, they are the same. Note how the first definition I gave circumvents this issue nicely; sometimes definitions are (re)made with later needs in mind.


Solving road trip problem in linear time

This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.


AVL tree with fixed height and as few elements as possible

Generally tree height is defined as the length of the longest path from the root to a leaf. Therefore you're right that the two trees have the same height, but they actually have height 3.

As far as your second question, about how to draw the smallest possible AVL tree of a given height $n$, the trick is to think inductively. Construct a new tree of height $n$ by joining the smallest possible AVL trees of height $n-1$ and height $n-2$ as subtrees of a new common root. Using the definition of AVL trees, it's a straightforward exercise to see that (1) this new tree is a valid AVL tree and (2) it's the smallest possible AVL tree of height $n$.

To get the height 7 tree in particular, find the base case minimal AVL trees of heights 0 and 1, and repeat the above construction 6 times.


Do we create a programming language by writing a compiler?

The short answer is no.

You can think of a programming language as a mathematical formalism used for expressing computation. A compiler/interpreter is a just a piece of an actual software that carries out that computation, and should not serve as the language specification.

That being said, in addition to lexical and syntax specification of a language, you should also define semantic specification, i.e., what does a (syntactically correct) program written in your language actually mean. The obvious semantics to start with is operational semantics, where the meaning of a program is given in terms of how the program actually runs. That is, it (mathematically) precisely defines how programs execute. On top of this semantics you should build an actual compiler/interpreter with optimizations and so forth.

Specifying full operational semantics of your language will give you a formal language documentation and it will make you understand your language to the very details. Also, it will allow you to formally reason about some aspects of the language. Writing down operational semantics is really a good habit.

There are other useful semantics as well, such as axiomatic, denotational, and game semantics. However, they are more advanced and typically don't make their way into a compiler/interpreter.


Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US.

UP: If $x \in L$, then there is exactly one "proof" ("witness", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs".

US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be zero proofs, or 2+ proofs, as long as there is not exactly one.


Is there a software algorithm that can generate a non-deterministic chaos pattern?

No deterministic algorithm can generate a non-deterministic output.

A non-deterministic algorithm (e.g., a NDFA) could, but they exist only in theory, not in practice.

An algorithm with access to a random number generator can generate a random output, and therefore its output is not deterministic.  For instance, in practice by reading from /dev/urandom or CryptGenRandom(), you can get random bits, which can be used to produce random output, or to seed a pseudorandom number generator.  (You don't need a quantum random number generator to get random numbers.)

Chaos theory is pretty much irrelevant here.


The definition of context-sensitive grammar requires that every production be of the form

$$\alpha A \beta \to \alpha \gamma \beta$$
where $A \in N, \alpha,\beta,\gamma\in (\Sigma\cup N)^* \text{ and } |\gamma| \ge 1$.

Assuming $\Sigma=\{a,b\}$ and $N=\{X,Y\}$, the production $bX\to abY$ does not satisfy this criterion. The only possible decomposition of the left-hand side is $\alpha=b,\beta=\epsilon$, and that doesn't match the right-hand side. So it's not a context-sensitive grammar.

However, that doesn't stop the language generated by that production from being context-sensitive. There is an alternative characterisation of grammars (which is, in fact, often used instead of Chomsky's original context-sensitive criterion), which are the non-contracting grammars. A non-contracting grammar consists only of productions of the form $\alpha\to\beta$ where $\alpha,\beta\in(\Sigma\cup N)^+\text{ and }|\alpha|\le|\beta|$. These grammars are weakly equivalent to context-sensitive grammars; in other words, for any context-sensitive grammar, there exists at least one non-contracting grammar which generates the same language, and vice versa. (This is a weak equivalence because the grammars don't produce the same derivations.) Furthermore, there is a mechanical procedure which can convert a non-contracting grammar into a context-sensitive grammar.

The production you ask about is certainly non-contracting, so (unless other productions in the grammar are contracting) the language is context-sensitive.

If this question appears on a test or class assignment, you should verify which definition of "context-sensitive grammar" your professor uses. Because of they generate exactly the same languages, and because non-contracting grammars are often easier to write, some people use the non-contracting criterion as a definition of "context-free grammar".


Is a register machine built out of automata of some sort?

I can only react to this as seen from the perspective of a theoretical computer scientist.
A finite state machine/automaton is, as you know, usually represented by a finite directed graph. The vertices of the graph repesent the states of the automaton, the edges are the instructions: in state $p$, upon reading symbol $a$, move to state $q$.
Next to this graph is the "machine interpretation". The machine has a control unit and an input tape. That control unit is represented by the finite graph.
From these finite state machines/automata we can build more complex automata by adding external memory. For instance the pushdown automaton. The external memory is a single stack. The edges/instructions of the finite state repesentation are now extended with tests and instructions of the external pushdown: test what is the topmost symbol $A$, pop $A$ and push a new sequence $\alpha$.
The register machine likewise is obtained by choosing another external memory type. That of registers. The machine has a finite, fixed, number of registers each holding a natural number. Each register can be tested for zero, incremented and decremented. The instructions of the register machine are added to the finite state control. So we get edges/instructions of the form: in state $p$ upon reading $a$, when register $i$ is nonempty, increment it by $1$ and move to state $q$. If we allow the register machine to read $\varepsilon$, that is compute without reading input, these machines are Turing complete (even with two registers).


What will be T(n) after second step in a Recurrence Relation

What you get is correct, but you haven't gone further one more step, but two more steps.

T(n) = 2T(n - 1) + n

First :

T(n - 1) = 2T(n - 2) + (n - 1)

T(n) = 4T(n - 2) + 2(n - 1) + n

Second :

T(n - 2) = 2T(n - 3) + (n - 2)

T(n) = 8T(n - 3) + 4(n - 2) + 2(n - 1) + n

Third :

T(n - 3) = 2T(n - 4) + (n - 3)

T(n) = 16T(n - 4) + 8(n - 3) + 4(n - 2) + 2(n - 1) + n


What is an algorithm for what I am trying to do?

You find the local maxima and minima by taking the derivative and setting it to 0.  This leaves you with a non-linear equation $f'(x)=0$ to solve.

The easiest, and most reliable, way to find the zeros of a continuous non-linear equation, $g(x)=0$, is called the Bisection Method.

Find two points $x_-$ and $x_+$ where $g(x_-) < 0$ and $g(x_+) > 0$.  (These are particularly easy to find for odd-degree polynomials, since there will always be at least one real root.)

Now evaluate $g(x_\star)$ where $x_\star = (x_- + x_+)/2$.  If $g(x_\star) > 0$ then let $x_+ = x_\star$ and repeat.  Else if $g(x_\star) < 0$ then let $x_- = x_\star$ and repeat.

Because you are interested in the range [-4,6] you also need to evaluate $f(-4)$ and $f(6)$, because the local maxima may not be inside the range.  (Your function obviously has no finite global maximum. $f(10)$ is about 18000, and grows from there and $f(-10)$ is also about 18000 and grows from there.


In fact, you have been correct all along. However, you have not finished Christofides algorithm yet.

The next step is "Calculate Euler tour".
In the last picture, you have obtained a multigraph all of whose vertices have even degrees. So it must have an Eulerian path. For example, let us select the Eulerian path A -> F -> A -> C -> B -> D -> E -> D -> A.

The last step is "Remove repeated vertices, giving the algorithm's output".
Removing the second A and the second D on that above path, we obtain a wanted output, A -> F -> C -> B -> D -> E -> A. Done.

Please note it is not very meaningful to apply Christofides algorithm on the given graph.

"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality". The given distances do not obey the triangle inequality, since d(B,D) + d(D, E) = 1 + 4 < 6 = d(B,E). Moreover, the (direct) distance between A and B is not given, raising doubt whether this is a travelling salesman problem at all.


If L is context-free, must FH(L) be context-free?

The intuition developed in the comments is right. The answer is NO, there is a counter-example, a CFL for which the first halves are not CFL.

$L = \{ a^m b^n c^n a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c\}$, from the answer on our sister site.

   Proof by Pumping lemma: pick $a^p b^p c^p \in \mathrm{FH}(L)$; pumping either destroys the "$b^n c^n$"- or the "first half"-property.

A slight adaptation of that language is
$K = \{ a^m b^n c^n \#\# a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c,\#\}$. We can now "force" the point where the cutting site of the first half is and get another proof technique.

   Let $H = FH(K) \cap a^*b^*c^*\#$. This means we only consider first halves where the middle is exactly at the point between the two $\#$-symbols. Thus. $m+2n+1=1+3m$, or $m=n$. Thus $H=\{a^nb^nc^n \mid n\ge 1\}\#$. Now if $K$ is context-free then $H$ is context-free (via the closure property intersection by regular languages). This language is close to a standard non-context-free example $\{a^nb^nc^n \mid n\ge 1\}$. This in turn can be obtained by right quotient with $\#$ which also preserves context-freeness.


Locally finite graph without an optimal path

It can happen. Let $P_0,P_1,\ldots$ be a one-way infinite path, where $P_0$ is the start node, and the edge from $P_i$ to $P_{i+1}$ has weight $1/2^{i+1}$. Let $Q_0,Q_1,\ldots$ be a one-way infinite path, where $Q_0$ is the goal node, and the edge from $Q_i$ to $Q_{i+1}$ has weight $1/2^{i+1}$. Connect $P_i$ to $Q_i$ with an edge of weight $1/2^{i-2}$. The weight of the path $P_0-\cdots-P_i-Q_i-\cdots-Q_0$ is
$$(1/2+\cdots+1/2^i)+1/2^{i-2}+(1/2^i+\cdots+1/2) = \\
(1+\cdots+1/2^{i-1})+1/2^{i-2} = \\
(2-1/2^{i-1})+1/2^{i-2} = \\
2+1/2^{i-1} \, .
$$ So for each $\epsilon > 0$ there is a $P-Q$ path of weight $2+\epsilon$, but there is no path of weight $2$.


Nice conjecture on tree isomorphism.
However, here is a counterexample.

Exercise. Construct a counterexample using a binary tree.


A modern computer is designed to handle many more interrupts than you could possibly generate with your keyboard.

  You should expect interrupts to range upward from 1,000 per second for computers running Windows 2000 Server

See this link.


Variable cur and root points to the same object at the start. Think of it as assigning an object two names - root and cur.
In test1 you changed the object pointed to by root. This means that the name root has been assigned to a different object. However, cur remains to be the name of the object at the start. So now root and cur do not point to the same object.
In your test2 you did not change the object pointed by root, but you modified the object shared by both cur and root, through root so changes to this shared object will be reflected in both.
Try to read this for more info https://realpython.com/python-variables/


Is there a proof of the recursive algorithm for generating all permutations of a sequence?

Hint: Prove by induction that $\mathrm{permute}(l,n)$:

Adds to $P$ all permutations obtained from $l$ by permuting coordinates $n,\ldots,|l|$.
Leaves $l$ unchanged. That is, the value of $l$ after running the function is the same as its value before running it.


This is partly a matter of terminology, and as such, only requires that you and the person you're talking to clarify it beforehand. However, there are different topics that are more strongly associated with parallelism, concurrency, or distributed systems.

Parallelism is generally concerned with accomplishing a particular computation as fast as possible, exploiting multiple processors. The scale of the processors may range from multiple arithmetical units inside a single processor, to multiple processors sharing memory, to distributing the computation on many computers. On the side of models of computation, parallelism is generally about using multiple simultaneous threads of computation internally, in order to compute a final result. Parallelism is also sometimes used for real-time reactive systems, which contain many processors that share a single master clock; such systems are fully deterministic.

Concurrency is the study of computations with multiple threads of computation. Concurrency tends to come from the architecture of the software rather than from the architecture of the hardware. Software may be written to use concurrency in order to exploit hardware parallelism, but often the need is inherent in the software's behavior, to react to different asynchronous events (e.g. a computation thread that works independently of a user interface thread, or a program that reacts to hardware interrupts by switching to an interrupt handler thread).

Distributed computing studies separate processors connected by communication links. Whereas parallel processing models often (but not always) assume shared memory, distributed systems rely fundamentally on message passing. Distributed systems are inherently concurrent. Like concurrency, distribution is often part of the goal, not solely part of the solution: if resources are in geographically distinct locations, the system is inherently distributed. Systems in which partial failures (of processor nodes or of communication links) are possible fall under this domain.


Sort deck of cards with least no of moves

Given a permutation $\pi:[n]\to[n]$ of cards from $1$ to $n$ you can find the first card to move to the front the following way:

$c \leftarrow n$
for each $k$ from $n$ down to $1$ do
$\space\space\space$ if $c = \pi(k)$ then
$\space\space\space\space\space\space$ $c \leftarrow c - 1$
$\space\space\space$ end if
end for
return $c$

In other words, choose the highest card, for which there is another card of higher value in front of it. More formally, choose a maximum $c\in[n]$ such that there exists a $c' > c$ with $\pi(k') = c'$, $\pi(k) = c$ and $k' < k$. Clearly, this card is not in order yet and since it is the one with the highest value it must be moved first if we want to keep the number of moves minimal. For the permutation $3,1,4,2$ this card is clearly card number $2$.


Predicting the next number output by a random number generator

It is a well-known fact concerning (cryptographically secure) pseudorandom generators (PRGs) that pseudorandomness is equivalent to next-bit unpredictability. That is, distinguishing the output of a PRG from the uniform distribution is just as hard as predicting its next bit of output (when the PRG works on a uniformly distributed seed). This goes back to a result by Yao.

Further reading:

Yao's test
Next-bit test
Pseudorandomness

If we are talking about standard (i.e., not necessarily cryptographically secure) random number generators (RNGs), then things are a bit different. If the RNG simply has to fulfill a set of heuristics, then it can be the case that it does so despite being (almost) fully predictable. (As an extreme example, consider the rather naive heuristic $\lim_{n \to \infty} E(|G(1^n)|_0) = \lim_{n \to \infty} E(|G(1^n)|_1) = \frac{1}{2}$, that is, the string $G(1^n)$ tends to have just as many zeroes as ones and the "generator" $G(1^n) = 0^{\lfloor \frac{n}{2} \rfloor} 1^{\lceil \frac{n}{2} \rceil}$.)

Breaking such an RNG would involve statistical tests and ad hoc methods; your chances of success depend on what the heuristics are and how much computational power and RNG data you have available. Without having detailed these things, it cannot really be said whether it is feasible to break it or not.


Computability of sequential cubic-order algorithms

Estimate the constant of the leading term in your complexity, i.e., write your complexity as $c n^3 + o(n^3)$. You can get an idea of $c$ by a careful inspection of your algorithm and you can test it experimentally.

Then decide what "can be solved using today's technology" means. You probably want your program to terminate withing a certain amount of time $T$. Estimate how many operations $N_T$ your machine can perform within time $T$.

Finally solve $c n^3\le N_T$, i.e., $n \le \sqrt[3]{n/c}$.

Keep in mind that this is just an estimate there are a lot of thing that can go wrong: $c$ depends on a lot of practical factors (the language of your implementation, the target architecture, cache locality, ...), the complexity of the algorithm might not be uniform across different instances of the same size, the complexity of the algorithm might not scale up nicely, the asymptotic notation is... asymptotic while you're dealing with small input sizes, and more.
You know the details of your algorithm so you probably have a better idea of how these factors will impact your estimate.


Iterative deepening is not actually the same as iterative lengthening, but they're very similar concepts.

In an iterative deepening search (using depth-first), you use the depth (a measure of distance between nodes) as a limiting factor. So, if you're performing an iterative deepening depth-first search starting at point a, and you set a depth limit of 2, you're asking the algorithm to perform a depth-first search from point a, but to not continue the depth-first search after you get two points away from your starting point a.

e.g.

                       a             In our example, the algorithm would never
                      / \            visit point e. It is more than 2 points
                     b   c           away from a (its depth is greater than 2)
                   /
                  d
                 /
                e

The algorithm will therefore explore all paths from a that are equal to a length of 2 (do not go deeper than depth 2).

In an iterative deepening search, you slowly increase (iterate) the depth at which you limit the search. It tries all paths of length 1 and then all paths of length 2 and so on. This means if there's a path of length 1 to a goal that you're trying to find, this algorithm would find it before trying any paths of length 2, 3, 4, et cetera.

Similarly, an iterative lengthening search uses the cost (or "length") of a path to limit the search rather than the depth. This is useful in situations where connections are weighted. The algorithm would explore all possiblities with a cost of 1 or less, then all possibilities of a cost of 2 or less, and so on. For a real-life example, the cheapest (cost) way to get somewhere is not always the same as the simplest (depth) way to get there. You might have to catch seven buses and a helicopter, but it's cheaper than renting out the Concorde for a single flight. You could consider an iterative deepening search to be a specific case of an iterative lengthening search where you define the "length" that you're iterating as the depth.


How close are common programming languages to not being Turing complete?

Common programming languages are very firmly Turing-complete, if you take an idealized view where programs can use an arbitrary large amount of memory. There typically isn't a single feature that you can isolate without which the language wouldn't be Turing-complete.

Intuitively speaking, Turing completeness requires two things:

A way for programs to manipulate an amount of memory that doesn't solely depend on the size of the input. Any form of object creation that can build bigger objects from smaller objects is suitable: objects, structures, pairs, lists, malloc, new, etc. Even stack-based allocation is enough provided that there is a way to access objects at any distance from the top of the stack (with only stack-based allocation and only access to the top of the stack, you only get a pushdown automaton). Many weaker forms of data manipulation are also suitable: for example, in a language like Lisp or Python where integers don't have a limited size, the basic integer operations alone are enough for Turing completeness.
A way for programs to keep running or halt based on some part of the data. While loops, recursion plus some form of conditional (e.g. if or case/switch) and goto plus some form of conditional are the three common ways, but there are others.

I think that the best way to understand what makes a language Turing-complete is to look at examples of languages that are powerful, but not Turing-complete. I'll give two examples that illustrate the two main families of such languages (other than languages that operate in bounded memory).

Consider an imperative language with integer operations and arrays, but only for loops (for i = 1 to n, where i cannot be modified during the loop), not arbitrary (while) loops and no recursion. BlooP and early versions of FORTRAN are examples. In such a language, you can only express primitive recursive functions — functions where the amount of computation is bounded in the size of the input. The language is not Turing-complete — cannot express arbitrary recursive functions — because of the bound on computation time.

A functional language can be made non-Turing-complete by restricting recursion through a type system that restricts all functions to be terminating. If the type system is decidable (i.e. if it is decidable whether the program is well-typed), then such a language cannot be Turing-complete (because the halting problem is undecidable). Languages used for theorem proving, such as Coq and Agda, are of this kind.

See also What can Idris not do by giving up Turing completeness?

On a side note, theorem provers require the user to input termination proofs (i.e. they don't find them themselves). So you could make a theorem prover with an undecidable type system: if you get a correct proof accepted, you're happy, otherwise you give up after a while. But it wouldn't be user-friendly. Most theorem provers have a decidable type system: you enter a term, and either it's accepted or you get a type error back. What theorem provers don't have is decidable type inference: if you type a term with partial type information and it's rejected, you don't know whether it's because the term cannot be typed or because the inference engine wasn't smart enough.


Describe a turing machine that accepts Language L = {www| w is {a,b}*}

Let $\ell$ be the length of the input.
You can assume w.l.o.g. that $\ell=3k$ for some integer $k$. If this is not the case (which can be easily checked by your TM), then the answer is trivial.
The problem boils down to finding $k$. In order to do so you can use the following strategy:

"mark" the two rightmost unmarked tape cells;
"mark" the leftmost unmarked cell;
If the cell immediately to the right of the current head position is marked, then you are done since the head must be in position $k$. Otherwise, repeat from step 1.


As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete.

I suspect what's meant, though, is the following:

  Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP?

This is definitely not trivial, but the answer turns out to be the same: Ladner's theorem says that if there are no NP-intermediate problems then P=NP.

It's worth noting that Ladner's theorem is constructive in that Ladner provides a specific example of a language $X$ such that if P$\not=$NP then $X$ is NP-intermediate. (I'm not making the stronger claim that it doesn't need the excluded middle, although I suspect that's true.) Moreover, the proof is pretty short; see e.g. here.


How to verify number with Bob without Eve knowing?

First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes.

(To honour long-standing traditions, the two honest parties involved in the conversation are called Alice and Bob. In your text, you said "you". My real name is not "Alice", but I will respond just as if you wrote that Alice wants to verify Bob's phone number.)

The simple (but weak) answer is to use a hash function. Alice writes on the card: "return to me the SHA-256 hash of your phone number". SHA-256 is a cryptographic hash function which is believed to be secure, as far as hash functions go. Computing it by hand would be tedious but still doable (that's about 2500 32-bit operations, where each operation is an addition, a word shift or rotate, or a bitwise combination of bits; Bob should be able to do it in a day or so).

Now what's weak about that ? SHA-256, being a cryptographic hash function, is resistant to "preimages": this means that given a hash output, it is very hard to recover a corresponding input (that's the problem that Eve faces). However, "very hard" means "the easiest method is brute force: trying possible inputs until a match is found". Trouble is that brute force is easy here: there are not so many possible phone numbers (in North America, that's 10 digits, i.e. a mere 10 billions). Bob wants to do things by hand, but we cannot assume that Eve is so limited. A basic PC can try a few millions SHA-256 hashes per second so Eve will be done in less than one hour (less than 5 minutes if she uses a GPU).

This is a generic issue: if Bob is deterministic (i.e. for a given message from Alice, he would always return the same response), Eve can simulate him. Namely, Eve knows everything about Bob except the phone number, so she virtually runs 10 billions of Bobs, who differ only by their assumed phone number; and she waits for one of the virtual Bobs to return whatever the real Bob actually returned. The flaw affects many kinds of "smart" solutions involving random nonces and symmetric encryption and whatsnot. It is a strong flaw, and its root lies in the huge difference in computing power between Eve and Bob (now, if Bob also had a computer as big as Eve's, then he could use a slow hash function through the use of many iterations; that's more or less what password hashing is about, with the phone number in lieu of the password; see bcrypt and also this answer).

Hence, a non-weak solution must involve some randomness on Bob's part: Bob must flip a coin or throw dice repeatedly, and inject the values in his computations. Moreover, Eve must not be able to unravel what Bob did, but Alice must be able to, so some information is confidentialy conveyed from Bob to Alice. This is called asymmetric encryption or, at least, asymmetric key agreement. The simplest algorithm of that class to compute, but still reasonably secure, is then RSA with the PKCS#1 v1.5 padding. RSA can use $e = 3$ as public exponent. So the protocol goes thus:

Alice generates a big integer $n = pq$ where $p$ and $q$ are similarly-sized prime integer, such that the size of $n$ is sufficient to ensure security (i.e. at least 1024 bits, as of 2012). Also, Alice must arrange for $p-1$ and $q-1$ not to be multiples of 3.
Alice writes $n$ on the card.
Bob first pads his phone number into a byte sequence as long as $n$, as described by PKCS#1 (this means: 00 02 xx xx ... xx 00 bb bb .. bb, where 'bb' are the ten bytes which encode the phone number, and the 'xx' are random non-zero byte values, for a total length of 128 bytes if $n$ is a 1024-bit integer).
Bob interprets his byte sequence as a big integer value $m$ (big-endian encoding) and computes $m^3 \mathrm{\ mod\ } n$ (so that's a couple of multiplications with very big integers, then a division, the result being the remainder of the division). That's still doable by hand (but, there again, it will probably take the better part of a day). The result is what Bob sends back to Alice.
Alice uses her knowledge of $p$ and $q$ to recover $m$ from the $m^3 \mathrm{\ mod\ } n$ sent by Bob. The Wikipedia page on RSA has some reasonably clear explanations on that process. Once Alice has $m$, she can remove the padding (the 'xx' are non-zero, so the first 'bb' byte can be unambiguously located) and she then has the phone number, which she can compare with the one she had.

Alice's computation will require a computer (what a computer does is always elementary and doable by hand, but a computer is devilishly fast at it, so the "doable" might take too much time to do in practice; RSA decryption by hand would take many weeks).

(Actually we could have faster by-hand computation by using McEliece encryption, but then the public key -- what Alice writes on the card -- would be huge, and a card would simply not do; Eve would have to transport a full book of digits.)


Number of rounds in interactive proofs - Arora & Barak

It could be that both definitions are used by different authors. Whenever you use the concept of rounds, make sure to tell the reader what you mean by a round. In any case, the two concepts differ by a factor of $2$.


Ideally when training an agent you would reach an equilibrium between both player strategies strategies (hopefully a Nash equilibrium). When using only self-play this equilibrium might be different to the one you would reach when competing against a specific player, in particular, taking into consideration that the other player might not be very efficient, may have a different reward structure, etc.

Now, answering your specific question about the environment.. I would say that the critical aspect is the game being played. You should check if you are dealing with a zero-sum game, cooperative vs non-cooperative, etc.


If you increase the address space for an OS, does the Phys Mem used by the program increase?

No.  Due to the way virtual memory works, you can have more virtual pages than physical pages (frames).  Some virtual pages might not be mapped to any physical page.

It doesn't really make sense to talk about "if you increase the address space size, the number of pages increases".  It might be slightly more useful to think of it as "if you increase the number of pages, the address space size increases".

But really, in any given architecture, the address space size is often fixed and cannot be modified: the size of a virtual address is fixed and cannot be changed, and that determines the number of pages and thus the maximum size of the available virtual address space.


Programmatically checking equivalence of statements

So, there are two possibilities, depending on how complex your statements are.

If your statements are relatively simple, then there's a good chance they fit in what is decidable with Satisfiability Modulo Theories. It's basically a way of taking a SAT solver and integrating it with a solver for a specific theory, for example, theory of linear arithmetic. Here is a list of common theories.

If your statements are too complex, then reducing these equations to a normal form becomes undecidable. This is because there are ways to encode logic and computation in arithmetic, so determining the equivalence of some formulas can be equivalent to solving arbitrary logical equations.

The decidability of your problems depends heavily on whether you're using integers or reals, linear or non-linear arithmetic, etc. As was mentioned in the comments, if you can encode arbitrary Diophantine equations, then you're definitely undecidable.

Regardless of decidability, your problem is definitely $NP$-hard. Suppose we could efficiently check if the normal form of problems were syntactically the same. Then we could efficiently solve 3SAT by checking if a boolean formula is equivalent to False.


Superscalar processors and complex instructions

You should understand that any program is a sequence of instructions (ok, you an think of it as a collection of threads, where every thread is a sequence of instructions or a virtual process that executes that series of instructions). The instructions are supposed to be executed one after another. Single pipeline processor fetches instruction as they are ought to, every clock cycle and keeps its functional unit executing an instruction per cycle. This is not very true actually because execution takes multiple cycles and you fetch next instruction before previous is complete. But we pretend that instructions are still executed one after another and you still need one FU. Superscalars, however, cheat. They tell to the user that they still execute her program as designed, one instruction after another, yet take a window of neighbor instructions and execute them at once. They introduce extra FUs (Wikipedia called them "redundant") for this technique, called "Instruction Level Parallelism" (ILP).

Superscalars also have to entail a complex dependency detection and maintenance mechanism. As Amdahl has explained), because instructions of the same thread operate on the same data set, you have a lot of dependencies, especially among neighbor instructions and, thus cannot gain a lot of parallelism at ILP. The parallel pipelines are therefore sometimes used to execute different threads. This is full-scale parallelism already (except the synchronization cases and cache contention, which prevents any advantage of TLP over ILP, especially if von Neumann bottleneck is considered). Such TLP is known as hyperthreading. Yet, it is true parallelism since now threads are indeed executed in parallel, as if there are multiple cores, rather than parallelism is emulated by periodically switching threads on a single pipeline and, therefore, is also called "simultaneous multithreading".

I do not even see any reason to differentiate between multicore and hyperthreading. Since different pipelines execute different threads, this means that they have separate instruction pointer, set of registers and everything you need for the context, which are switched. Might be the common cache and shared FUs is the only things that distinguishes single core from multiple cores. Yes, shared cache. This may save you from cache incoherence /memory consistence problems that can happen in truly multicore system.


Confusion about data types, compilers, hardware data representation and static vs dynamic typing

First, you must be aware that computer science is full of terms which have multiple, related but conflicting definitions.  The fact that two authors are using the same term such as "type" does not mean they are using the same definition and thus there may be inconsistencies if you are not careful when you try to combine different sources.

A type is a property attached to entities (values, variables, ...) which allow to know what operations are allowed on those things and what is the result of those operations (including the type of the result).  That means that type determines the interpretation of the bits pattern representing a value, but that's not the only effect of types.  It is common to introduce several types which gives the same meanings to bits patterns, just to prevent to use them in some context (an extreme example would be to have different types for X and Y coordinates to be sure they are not swapped at the wrong time).

A language may be:

statically typed: an analysis of the program allows to know the type of an entity without the need to execute it (that is what you were thinking about).  That is common for languages which are compiled.
dynamically typed: value carries information about their type. Choices which need that information must be done at execution time, looking at the information attached to the value at hand. That is common for languages which are interpreted.
untyped: operations assume that their arguments are correct (note that this is different from implicit conversions, implicit conversions tries to conserve a notion of value, in an untyped language that does not happen), there is no typing error (but an argument may be invalid and trigger an error) nor choice of behavior depending on types. Nowadays the more common languages which are untyped are the assembly languages. Historically languages like BLISS and BCPL were also in that class.  The original TCL language was also in that class.

Note that it is quite common for languages to have aspects of several kinds. C++ for instance has a notion of static type which determines some things such as overload resolution, a notion of dynamic type which determines other things such as virtual function dispatch and reinterpret_cast allows to circumvent the typing system and behave in an untyped way.  A language may be defined in a dynamic way, as if the values carried the type information, but a compiler may analyze a program and remove part of the checks that would be needed and even remove the need to attach a dynamic type information on some values.  And a language may have types (static or dynamic) but be used in an untyped way (Lisp variants often have a notion of dynamic type, but lists are also often used to represented everything not built-in).

  So my question is this: if data types 'exist only in the compiler'

I've tried to show that this assumption is false. It may be true for some languages, but others attach type information to values (and that's the case for object oriented one -- I've in the past described OO as a way to get the benefits of dynamic typing without dropping completely the benefits of static typing --, if there is a dynamic dispatch based on type, you need to have dynamic type information).  Note that the information may be part of the value as a tag, as a pointer to a type-descripting data structure (the vptr of common implementation of C++), or even implicitly (that area of memory is used only to store values of that type, the bits don't have to show what type is the value, the place where they are is giving the information).

References

Types and Programming by B. Pierce (but IIRC it is strongly oriented towards static typing)

Concepts, Techniques, and Models of Computer Programming by P. van Roy and Seif Haridi, wider of scope but also more oriented towards dynamic typing and may also be useful to organize things before a reference such as B. Pierce which is more concerned about just typing issues.


Does an enumerator print the first occurrence of a word in finite time?

Your interpretation is correct, and the easiest way to look at it is to know both definitions of recursively enumerable sets:

There is an algorithm (potentially running forever) that enumerates the members of $S$.
There is an algorithm for which the algorithm halts only on elements of $S$.

These two definitions are equivalent, and if you use the second one then you can easily answer your own question.

However, do note an important caveat. Although for any given word $w \in S$ there is some time $T_w$ such that after $T_w$ steps, $w$ will have been enumerated. However, there is no way to bound $T_w$ from above as a function of $w$. It can grow faster than any computable function.


The statement does not hold.

For $A = \{a, aaba\}$ and $B = \{a, abaa\}$ we find

$|g(A,B) = \{a, abaa, aaba, aababaa\}| = 4 > 3 = |\{aa, aabaa, aabaabaa\}|  = |A\cdot B|$.

As a sidenote, I'd say this could actually be a worthwile exercise task, once students are reasonably experienced with standard proof techniques. After all, you only really learn how to attack such problems from practising.


Looking for interesting unanswered questions within complexity theory for a project

Do something interesting with visibly languages. They are a relatively recent topic with many useful practical applications. For example, I would find it interesting to better understand the role of synchronization here, compared to the role of synchronization for the theory of codes. Already the simplest case could be interesting, where the visibly language just distinguishes between inner symbols and separator symbols, and the considered codes are just bifix code.

David Richerby is right that this questions allows opinion biased answers. The origins of the opinions voiced in this answer can be found here.


It depends what you mean by this puzzle. If you mean specifically Calibron 12 then no, there is no growth factor (there are only ever 12 pieces) so the solution can be found in constant time (a very slow constant).

If however you want to know about puzzles of this nature it is hard to determine. The problem could potentially be phrased as, Is there some arrangement of these $n$ objects that can completely fill this square. Now to me this does not seem likely to be polynomial-time in nature (I am speculating based on the permutations of arrangements, but I do not have a proof).

The bin packing comparison does not really work however since this has almost nothing to do with separating $n$ objects into  the smallest number of bins. This is a category of questions called tiling problems.

Here is a paper that deals with Rectangle tiling, which is a related problem.


Why does an acceptor send the highest numbered proposal with number less than n as a response to prepare(n) in paxos?

As I was writing my question I realized what I believe to be the correct answer and wanted to share it just in case someone else was wondering this step in Paxos, or maybe correct it if its not 100% correct (or clear).

Recall that, in Paxos, the actual goal is to achieve some consensus (agreement) on some value. The actual value is not very important as long as its from the valid set of values. However, we only care that our protocol somehow achieves some agreement. Thus, if we are a proposer and want to propose a value, what we really care is that some value is agreed amongst the processes participating in the protocol (since that the goal of a consensus algorithm, that some valid value is accepted). If for some reason, we were desperate for our value to be accepted at some point, we could eventually re-run a different instance of Paxos later (or more instances of Paxos until that value is chosen), so its ok to try to suggest the value later (to a different paxos instance) if we really need to (but that will be a different set of rounds of Paxos, starting with round zero and doing Paxos all over again). Its crucial to understand that suggesting the value to the same paxos instance is pointless since the point is that once paxos reaches consensus, that it sticks to it. We have to run paxos for a different set of values if we want our value to still be decided at some point.

But, the point of the step that "acceptors respond with the highest-numbered proposal that the current acceptor has seen", is to guarantee that if a value in the past (with lower sequence number) had been ratified, then why complicate agreement by considering a different value? It's easier to eventually agree at some value if we just keep that ratified value instead. Furthermore, and the more important reason is, imagine if we decided to discard the value we had ratified previously and instead ratify the new incoming one. Well, if we did that and update our state it could be very bad, because, one important property we wish our algorithm to have is, "once an agreement by majority has been reached, we wish it to be impossible for our system to change its mind" (because consensus has occurred already, so a change in mind is completely unnecessary). If we take this new (wrong) approach I have suggested, then that property could not hold. However, if instead, we always just respond with the highest ratified value, then the proposer on the other side is bound to learn the chosen value, if one has been chosen (if he queries some majority). Thus, the safe thing to do is, just send the proposer the current ratified value with the highest sequence number, that way, if a value was chosen, then the system is not able to change its mind if a consensus occurred (since its not necessary for it to change its mind since some value has already been accepted by some majority!). The whole point of consensus means that we agree on something, so changing the value can be viewed as breaking consensus.


If a NAND gate is universal, why you don't have NAND OISCs

With such an instruction set, all you could express are straight-line programs.  Without branches, you can't have loops.  Thus, the program would not be able to handle arbitrary-length inputs: it would be limited to dealing with fixed-size inputs (or inputs with a fixed known upper bound on the size of the input).  So, that wouldn't be very satisfactory.


Why is backpropagation called backwards propagation of error, when it back propagates error derivatives?

It's actually the error for the neurons. The actual reason for derivation is this:

You find an error then you find the derivative of the error according to some differential equation.
Gradients you obtain using that derivative is basically to determine how much one single neuron in the network made mistake. Gradient at one neuron means if you update the weights or biases according to that you decrease the error network makes.

Backpropagation is the mathematical system for assesing how much one neuron made mistake so you can improve it. Definition is true in that sense.


Maximizing the sum of adjacent pairs of elements

The following answer is due to Reuven Bar-Yehuda.

Let us call an order maximal if it maximizes the objective function $\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1))$.

Lemma 1. If $\pi$ is maximal then for all $1<i<j<n$,
$$\pi(i-1) < \pi(j+1) \text{ iff } \pi(i) < \pi(j).$$

Proof. Suppose that $\pi(i-1) < \pi(j+1)$ and $\pi(i) > \pi(j)$. Form the permutation $\sigma$ by reversing the order all $\pi(i),\ldots,\pi(j)$. Then
$$
\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\
a(\sigma(i-1)) a(\sigma(i)) + a(\sigma(j)) a(\sigma(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\
a(\pi(i-1)) a(\pi(j)) + a(\pi(i)) a(\pi(j+1)) - a(\pi(i-1)) a(\pi(i)) - a(\pi(j)) a(\pi(j+1)) = \\
(a(\pi(i-1)) - a(\pi(j+1)) (a(\pi(j)) - a(\pi(i)) > 0. \quad \square
$$

Lemma 2. If $\pi$ is maximal then $\pi(1) < \pi(i)$ for all $i \neq n$ and $\pi(n) < \pi(j)$ for all $j \neq 1$.

Proof. Both claims have a similar proof, so we only prove the first. Suppose that $\pi(1) > \pi(i)$ for some $i \neq n$. Form the permutation $\sigma$ by reversing the order of $\pi(1),\ldots,\pi(i)$. Then
$$
\sum_{k=1}^{n-1} a(\sigma(k)) a(\sigma(k+1)) - \sum_{k=1}^{n-1} a(\pi(k)) a(\pi(k+1)) = \\
a(\sigma(i)) a(\sigma(i+1)) - a(\pi(i)) a(\pi(i+1)) = \\
(a(\pi(1)) - a(\pi(i)) a(\pi(i+1)) > 0. \quad \square
$$

Theorem. If $\pi$ is maximal then $\pi$ is the following permutation or its reverse:
$$ 1,3,5,\ldots,6,4,2. $$
Proof. Lemma 2 shows that $a(\pi(1))$ and $a(\pi(n))$ are both smaller than $a(\pi(2)),\ldots,a(\pi(n-1))$, and so $\{\pi(1),\pi(n)\} = \{1,2\}$. Without loss of generality, assume that $\pi(1) = 1$ and $\pi(n) = 2$.

Lemma 1, applied with $i=2$ and $j=3,\ldots,n-1$, shows that $\pi(2)$ is smaller than $\pi(3),\ldots,\pi(n-1)$, and so $\pi(2) = 3$.

Lemma 1, applied with $j=n-1$ and $i=3,\ldots,n-2$, shows that $\pi(n-1)$ is smaller than $\pi(3),\ldots,\pi(n-2)$, and so $\pi(n-1) = 4$.

Continuing in this way, we recover the rest of $\pi$. $\quad \square$


The verb assemble and the noun Assembler is useful when it's important to point out that the program generates machine code with a 1:1 correspondence to the atomic instructions of the (Assembly) language.

But only a few simple directives (e.g. macros) need be added to the Assembler to reach something that gives more readable and compact code that can be, for all intents and purposes, considered high level.

If this was all that was added, you supply the actual macros, e.g. FUNC, CALL, STRUCT, etc. yourself, and can build your own language.

These macros are not the atomic Assembly Language instructions; nor are the directives built into the Assembler that lets you create them. Neither the macros you write, nor the directives are part of the agreed-upon Assembly syntax for the CPU.

For most intents and purposes, Compiler can be substituted for Assembler, and it's clear that you mean the program that generates an exe from text (or a tool). Perhaps some distinction could be useful when you mean language-specific such programs that can't parse Assembly, but there are ones that can do both.


How were weights chosen in Runge-Kutta (4) method?

You can enter a known function that is the solution of a known differential equation, write down the Taylor series up to say 6 terms, and then substitute it into the Range-Kutta formula or any other formula.

Once you calculate it, you will find that with the Runge-Kutta formula, you add up lots of different constants which magically add up to zero. If you change the constants to what you proposed, most likely these constants add up to something that isn't zero, introducing huge errors into your solutions.


Why use binary search trees when hash tables exist?

The most obvious answer is that trees can be traversed in their natural order very efficiently.  If you need to visit every element of a dictionary in alphabetical order, a tree can support this directly, where a hash table cannot.

Another answer is that trees can be made immutable - where insertion and deletion only involve recreating a small number of elements back to the root, whereas hash tables can only be completely duplicated.

A related answer for mutable data is that trees can be modified concurrently, only requiring locking single nodes, whereas hash tables have to be locked as a whole if concurrent processes are to get consistent results.


Irregularity of language of prefixes of decimal expansion of pi

The pumping lemma tells you that, if $L_\pi$ is regular, there is a word of the form $uvw$ such that $uv^kw\in L_{\pi}$ for all $k\in\Bbb N$, where $|v|>0$.

Note that if a word is in $L_\pi$, any nonempty prefix of that word is also in $L_\pi$. In particular, $uv^k\in L_\pi$ for all $k\in\Bbb N$. In other words, $uv$, $uvv$, $uvvv$, $\cdots$ are prefixes of the decimal expansion of $\pi$.

So $\pi=uvvv\cdots$, which contradicts the fact that $\pi$ cannot be written as a repeating decimal.

Here are several exercises that describe the general situation. The first two exercises are pointed out by gnasher729's comment. The last exercise comes from Yuval's comment

Exercise 1. Show the set of all prefixes of the decimal expansion of a rational number is a regular language.

Exercise 2. Show the set of all prefixes of the decimal expansion of an irrational number is not a regular language.

Exercise 3. What about binary expansion? What if the base is changed to another number?

Exercise 4. A language is a prefix language if for any two of its words $w_1$ and $w_2$, either $w_1$ is a prefix of $w_2$ or $w_2$ is a prefix of $w_1$. Show that for a prefix language $L$, $L$ is regular if and only if $L$ is context-free. In particular, $L_\pi$ cannot be context-free.


Is Breadth First Search Space Complexity on a Grid different?

It depends what you mean by a "on a grid".

If you mean that you are working with the graph of a complete grid, with number_rows * number_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices:

Yes, that's correct.  The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity is O(number_rows + number_cols) for BFS or O(number_rows * number_cols) for DFS.

If you mean that you are working with a graph that is a subgraph of a complete grid, then:

No, that's incorrect.  The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity of both could be as large as O(number_rows * number_cols), as explained in https://stackoverflow.com/a/50912382/781723.


Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

$n$ element tree has depth $\lceil{\log_2n}\rceil-1$. If $h$ is the height of nodes in any $n$ element heap from leaves then the nodes are situated at the depth of $\lceil{\log_2n}\rceil-1-h$ from the root.

Now, at most $2^{\lceil{\log_2n}\rceil-1-h} = \lceil{\frac{n}{2^{h+1}}}\rceil$ nodes/leaves are possible with $\lceil{\log_2n}\rceil-1-h$ depth in a heap.

Note that depth is the number of edges from the root & height is the number of edges from the highest level in a heap.


Smallest possible integer not obtained from sumset

One possible way is computing the product
$$ \prod_{a \in C} (1+x^a). $$
This is a polynomial $p(x)$.  The coefficient of $x^j$ will be non-zero if and only if $j$ can be represented as the sum of some subset of $C$.  Therefore, given $p(x)$, you can read off the set of all numbers that are obtainable as the sum of some subset, and then find the smallest that isn't obtainable (i.e., the smallest integer $j$ such that $x^j$ has coefficient $0$ in $p(x)$).

As a bonus, you'll also get the number of possible representations of each number which is representable.

The running time is polynomial in $N$, and doubtless you can optimize the degree of the polynomial. (This is dynamic programming in disguise.)

If you're after an algorithm polynomial in the input length (the input can be either $A$ or $C$), that's a different question.  The problem is that the input can be very small; though perhaps such inputs can be handled separately.


Best algorithm to find highest possible number of points from unique cards

I don't know why D.W. believes this is NP-complete, because it isn't. In order to solve the problem let us first change it (without loss of generality):

For each player only keep the highest rated card of a particular character. The lesser rated card(s) will never be part of the optimal solution.

For each player add a virtual card to their hand for each character they're missing, with rating -1 (or -inf if ratings can be negative). This ensures this card is never picked, but normalizes the problem.

Duplicate each player 5 times.

Negate ratings to turn them into costs.

Let's assume we had $p$ players and $c$ characters in the roster. After this transformation we have a typical assignment problem, where we have $5p$ workers and $c$ tasks. Viewing cards as tasks and 'player hand slots' as workers, we have an associated cost $c(w, t)$ for a worker $w$ and task $t$ combination, and our goal is to minimize the total cost.


There are statistical models for relative ranking.  I'd suggest taking a look at the Bradley–Terry model.  The data is sometimes known as paired comparison data.

See also Analysis and classification based on data points,  Peer grading design - choosing a graph, to get accurate rankings/ratings, https://stats.stackexchange.com/q/83005/2921.


Is $\{u u^R u : u \in \Sigma^*\}$ context-free?

Based on : Pumping Lemma for Context-Free Languages for reversal language

By @lukas.coenig

{ww$^R$w| w $\in$ {a,b}*} doesn't seem to be a context-free language over $\Sigma$  of length two.

Assuming this language isn't context free over an alphabet of size 2 to prove it also over size of 3.. and so on by induction might be interesting..(and if true by induction than there is probably a better way to prove it)


There are several possible layers to your question.

Why must PDAs have a stack? -- By definition! That's just how it is.
But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition.
Why is it interesting? -- See reinierpost's answer.
Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over.

I'd like to expand on the second bullet a little. How do different definitions come about?

If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models.

To list just a few examples of ideas people have had:

finite memory --> regular
single stack --> context-free
single queue --> Turing-complete
two stacks --> Turing-complete
infinite tape --> Turing-complete
heaps --> we don't really know
monoids --> all kinds of interesting things

And so on and so on.

Note that you can also modify other elements:

The alphabet -- make it infinite, or continuous.
The transition function -- make it a relation, or allow $\varepsilon$-transitions.
The state set -- make it infinite, or allow multiple starting states.
The inputs -- make them infinite, or trees, or timed sequences.
Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?)

Interesting things can happen!

That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is.


Interactive example of Dynamic scoping and evaluation order of expressions

I do not know other environments in existing languages, whether
statically or dynamically scoped. Also, that would be language
specific, hence off topic here.

Without a system environment, the way I would do this would be to
insert print statement in my program, either by hand if I am poor, or
with a some programmable program transformation system. I actually did
it often a very long time ago for debugging purposes, applying program
transformations I had developed in such a program transformation
system.

Your example is rather simple as the formal parameters j and k are
never modified, so that everything can be assumed to be call by value.
But things can get very hairy when formal parameters get modified in
the function, depending on the parameter passing mode.

I am also a bit surprised that your system gives you the post value
of i in f2 at the beginning rather than at the end of the trace.

You may try to trace the values of variable that are not visible in
the function currently executed, for example by printing them with a
function defined at the right place. But that can only work when the
function uses static scoping.

My basic philosophy is that dynamic scoping is an endless source of
problems because you cannot know what a free variable stands for, as
it may vary from call to call. I know that some people like it and say
it is useful. I will not comment.

Dynamic scoping was invented as a bug in the first Lisp interpreter, in the late fifties.
When they realized what they had done, the beast was out. Scheme
corrected that, but much later.

I am not sure I answered you. But I now realize this question is borderline on this site.


Polynomial time reductions using binary search

Is OPT = m? is a coNP decision problem.  A "no" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.

The same is true for the question Is OPT > m?.  There is no polynomial-time verifiable certificate for the "yes" answer to either of these questions unless NP = coNP.

Is OPT < m? is an NP decision problem.  A "yes" answer has a certificate verifiable in polynomial time, the certificate being a valid bin packing that uses fewer than $m$ bins.


If I understand your problem correctly then you probably didn't find any research because the problem is easy to solve.
Unless I missed something, you want to maintain an edge-weighted "layered" DAG $G=(L_0, \cup \dots \cup L_k, E)$ (as defined in your question) and support the following two operations:

Init(): Create a graph with only one layer $L_0$, a single vertex $r \in L_0$, and no edges.

Query(): return $\min_{v \in L_k } d(r,v)$.

Add_Layer($L_{k+1}, E'$): you are given a new set $L_{k+1}$ of vertices and a set of weighted edges $E' \subseteq(L_k \times L_{k+1})$. The vertex set of $G$ is updated to $L_0 \cup \ldots \cup L_k \cup L_{k+1}$ and the edge set of $G$ is updated to $E \cup E'$.

You can do the above by storing: 1) for each vertex $v \in L_k$, the distance $D[v]$ form $s$ to $v$ in $G$, and 2) the minimum distance $d^*$ from $s$ to a vertex of the last level.
The init operation amounts to setting $D[r]=0$. To perform the query operation just return $d^*$.
To implement Add_Layer($L_{k+1}, E'$), you proceed as follows:

Set $d^*$ to $+\infty$,
For each vertex $v \in L_{k+1}$:

Set $D[v] = +\infty$
For each edge $(u,v)$ in $E'$:

Update $D[v]$ to $\min\{D[v], D[u] + w(u,v) \}$

Update $d^*$ to $\min\{d^*, D[v]\}$

Notice that this requires time proportional to $|L_{k+1}| + |E'|$, and is therefore asymptotically optimal. Notice also that this solution does not need to store $G$.


Counting the number of tree when the set of the subtrees is given

You can't do it at all, let alone do it efficiently. Consider a tree $T$ and let its set of subtrees be $S$. If you're told $B=S$, the cardinality could be anything between $1$ and $|S|$, inclusive, because $A$ could be any subset of $S$ that contains $T$.


Yes. you're right (for $k,n \geq 1$). Also you can right the final answer as $O((kl^k)^n)$.


Is $L = \{\langle M, w \rangle: \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$ decidable?

You can prove that $L$ is undecidable using a diagonal argument: Assume $M$ decides $L$. Then, define $\tilde{M}$ as follows: On input $x$, run $M$ on input $\langle x, x \rangle$. If it accepts, go through all states and then halt; otherwise halt without going to some dedicated state $q_0$.

If you now run $\tilde{M}$ on input $\tilde{M}$, it runs $M$ on input $\langle \tilde{M}, \tilde{M} \rangle$. Since $M$ decides $L$, it accepts if and only if $\tilde{M}$ on input $\tilde{M}$ does not go through some state. This contradicts the construction of $\tilde{M}$. Hence, $L$ is not decidable.


what are Structural recursion, primitive recursion, recursion combinator and recursion principles?

The recursion combinator you mention seems to be the recursor associated to an inductive (or recursive) data type. In the paper this seems to be the type describing the syntax of lambda terms. Here, I'll take lists as a simpler recursive type.

Note that the "lists of naturals type" can be intuitively described as the "least" type admitting these constructors:
$$
\begin{array}{l}
nil : list \\
cons : nat \to list \to list
\end{array}
$$
Recursive types as the one above have an associated induction principle. For instance, if we wanted to prove a property on all lists $p(l)$, it would suffice to prove

the base case $p(nil)$, and
the inductive case $p(l) \implies p(cons\ n\ l)$ for any $n,l$.

If we had more constructors, we would have move base or inductive cases, accordingly.

Similarly, we can define a function $f : list \to A$ by induction. That is to define $f(l)$ on all lists, all we have to do is to define

what is the result in base case, i.e. $f(nil) = a : A$
provided we already defined $f(l)$, we need to define $f(cons\ n\ l)$ for all $n,l$.

Note that step 2 amount to define a function $g : nat\to A \to A$, which takes $n:nat$ and $f(l):A$ and produces $g(n)(f(l)) = f(cons\ n\ l)$.

We can generalize this by crafting a combinator that given $a,g$ produces $f$ defined as above. This is called the (primitive) recursor.

$$
\begin{array}{l}
rec : A \times (nat \to A \to A) \to (list \to A) \\
rec(a,g)(nil) = a \\
rec(a,g)(cons\ n\ l) = g(n)(rec(a,g)(l))
\end{array}
$$

Usually this is called fold_right or foldr in functional programming languages.

Note how, roughly, $a$ replaces $nil$, and $g$ replaces $cons$. Indeed, in the general case, the recursor takes one argument for each constructor of the recursively defined type at hand.

If you have a general fixed point combinator like Church's $Y$, you can easily encode the above. However, in many type theories, you don't have that luxury, since $Y$ causes the inconsistency of the related logic. Instead, for any recursive type you define, you get a restricted version of $Y$ which is the recursor: each type has its own recursion combinator. This ensures the termination of the calculus, which is important to ensure the consistency of the logic.


Time complexities of state-of-the-art SAT solvers with respect to length of the formula

For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.)

Consequently, any algorithm for 3SAT whose running time is polynomial in the number of clauses would also be polynomial in the number of variables; and any algorithm for 3SAT whose running time is polynomial in the number of variables would also be polynomial in the number of clauses.

It is known that there is a polynomial-time algorithm for 3SAT, if and only if there is a polynomial-time algorithm for SAT, if and only if there is a polynomial-time algorithm for CircuitSAT (e.g., for formulas).  Also, despite decades of work on SAT solvers, no one knows any algorithm for 3SAT that runs in polynomial time (or indeed in less than exponential time in the worst case).  You could take this as evidence that there is no polynomial-time algorithm for 3SAT; which implies that there is no polynomial-time algorithm for SAT or CircuitSAT, either, and also implies that P != NP.

Justification: Let $n$ denote the number of variables and $m$ the number of clauses.  We have $n \le 3m$ (a variable that doesn't appear in any clause can be ignored) and $m \le 8n^3$ (each clause has three literals, and you can ignore repeated clauses).  It follows that $n/3 \le m \le 8n^3$ and $\sqrt[3]{m/8} \le n \le 3m$, i.e., each is polynomially related to the other.

I see that you revised your question.  That clarifies that I think you have a misconception.  You talk about "run[ning] [a SAT solver] on arbitrary Boolean formulas".  However, you can't run a SAT solver on an arbitrary Boolean formula.  SAT solvers only work on CNF formulas.

However, we do know that any Boolean formula can be converted to an equisatisfiable CNF formula of size at most polynomial in the size of the formula, and vice versa.  If you had an algorithm that could test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula, then it would follow that you have an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the size of the formula (every 3CNF formula is a Boolean formula), and thus an algorithm that could test satisfiability of 3CNF formulas in time polynomial in the number of variables -- which contradicts the available evidence.  So, if you believe that there is no algorithm to solve 3SAT in time polynomial in the number of variables, then you should also believe that there is no algorithm to test satisfiability of arbitrary Boolean formulas in time polynomial in the size of the formula.


Invariant For Nested Loop in Matrix Multiplication Program

You need the line C(i:j) = 0 just before the innermost loop; otherwise, the code is incorrect.

Assuming that line is in place, here is the (strongest possible) invariant just before the assignment in the innermost loop:
\begin{align*}
C_{IJ} &= \sum_{k=1}^{n} A_{Ik}B_{kJ} & \text{for all $I$ and $J$ such that $1\le I < i$ and $1\le J\le n$}
  \\
\text{and}~~~ C_{iJ} &= \sum_{k=1}^{n} A_{ik}B_{kJ} & \text{for all $J$ such that $1\le J< j$}
  \\
\text{and}~~~ C_{ij} &= \sum_{K=1}^{k-1} A_{iK}B_{Kj}.
\end{align*}
(Yes, the whole thing.)  The invariant just after the assignment has $k$ in place of $k-1$ in the last sum, but is otherwise identical.


Are $AC^{0}$ algorithms interesting to research communities?

$\mathsf{AC^0}$ algorithms are quite weak. For example, $\mathsf{AC^0}$ cannot compute parity or majority. However, it can compute approximate majority, as shown by Ajtai; see Viola, On Approximate Majority and Probabilistic Time, for a better construction and for references to Ajtai's work.

$\mathsf{TC^0}$ is a slightly stronger class, also consisting of polynomial size circuits having constant depth, but allowing threshold gates. Such circuits can compute division, as shown by Hesse, Division is in Uniform $\mathsf{TC^0}$, improving on works of others (starting with Beame, Cook and Hoover). The related problem of iterated integer multiplication is also in $\mathsf{TC^0}$.


Adding words to DFA, maintaining minimality

For number 2, I think you would just check if the DFA ever enters an accept state, instead of just checking if it ends in an accept state.  So just run the algorithm as normal, but halt and accept as soon as the automation transitions to an accept state, instead of waiting until the end of the input.  (The number of times the automation enters an accept state is the number of substrings of the language contained in the input string)

Not sure about number 1 though.  I am not sure what operations (if any) minimal DFAs are closed under, but I think the number of operations required by a slightly modified version of Hopcraft's algorithm would be proportional to the size of a word you add via union.


Demonstrate that DPDA is closed under complement by construction

I didn't have time to write this before but I found an answer. Here is what I did:

Let $O$ be the original $PDA$. We will construct a new $PDA$, call it $M$ ($M$ stands for modified).

To find the complement of $O$, we can flip final states to be non-final states and vice-versa. It is the same procedure as for finite automatas. However, there is a subtlety. The main problem is that in the original PDA $O$ the input $w$ can lead to a state $S$ which is not a final state but could perform an $\epsilon-move$ and get to an accepting state $S'$. Flipping states as mentioned above, would make $M$ end in $S$ with the input $w$ which would be a final state (causing $M$ to accept accept the input) even though it will later make an $\epsilon-move$ to $S'$, a non-accepting state. Therefore, both $O$ and $M$ will accept $w$. Something similar happens if $S$ was a final state and $S'$ a non-final state reachable from $S$ through an $\epsilon-move$.

In order to overcome this problem, we must make sure that all $\epsilon$-moves happen before we read the next symbol. That is, we will enter a reading state only when a path of $\epsilon$-moves is followed and we reach a state which has no $\epsilon$-move available. We call these latter states reading states, as they need an actual symbol to perform a new transition.

Define $M$'s states to be tuples of the form $<q, n>$ where $q \in Q$ ($Q$ is the set of states of the original $PDA$) and $n \in \{1, 2, 3, 4\}$.

If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$ if $q \in F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$ in $M$ if $q \notin F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$.
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$ in $M$
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$ in $M$

In those definitions, we let states of the form $<q, 2>$ and $<q, 3>$ consume $\epsilon$-moves imitating $\epsilon$-moves of $O$ until there are no more. Then, perform an $\epsilon$-move to a reading state. Now for the reading states,

If $\delta(q, a, X) = <q', \alpha>$ in $O$, let $\delta(<q, 1>, a, X) =  \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$ in $M$.

By making this definition, we consume a symbol of the input and move to a state of the form $<q, 3>$ to begin a new series of $\epsilon$-moves.

Finally, make states of the form $<q, 4>$ be accepting states of $M$ if $q \notin F_O$. Also, make $<q_0, 3>$ the initial state of $M$ if $q_0$ is the initial state of $O$.

What we did is the following:

Create 4 "floors" of states (the second element of the tuple in states of $M$ determines in which floor we are). Floor 3 imitates $\epsilon$-moves of $O$ possibly reaching an accepting state $q$ of $O$. If that is the case, we move to floor 2; otherwise, we remain in floor 3. When there are no more $\epsilon$-moves to follow of $O$, we define $\epsilon$-moves of $M$ to reach a reading state. Floors 1 and 4 correspond to reading states. If we were on floor 3, we go to floor 4. If we were in floor 2, we reach floor 1. Only states $<q, 4>$ (states that are in floor 4) are accepting states of $M$, provided that $q$ is not an accepting state of $O$.

Please let me know if I made a typo at writing this. I could've easily mistaken. Also, my English is not very good so feel free to edit and rephrase things better.


Are neural networks inherently imperfect because they mimic an imperfect machine (human)?

It's better to think of neural networks as inspired by human biology, not that they're using exactly the same mechanism.

The notion of "inherently imperfect" isn't well-defined, so the question isn't meaningful.  And, no, neural networks aren't always imperfect.  For instance, suppose the learning task was "label everything 0".  If you give a neural network a training set with one million examples, all of which have the label 0, then the neural network might well learn to output label 0 on all possible inputs.

As far as moral implications, it's not clear that it matters much why neural networks are imperfect; what's important is that they are often imperfect.  But moral implications are probably more a matter of the study of ethics and philosophy than the science of computing, so I'll leave that there.

Finally, I encourage you to avoid binary thinking.  Don't divide the world into "perfect" vs "imperfect".  An engineer would say that in practice nothing is perfect; it's all about degrees of imperfection.  One system might be good enough, or better than the reasonably available alternatives, even if it's not 100% perfect.


Constructive proof to show the quotient of two regular languages is regular

The quotient of two languages $R$ and $L$ is
$$R/L = \left\{x\in \Sigma^{*} : \exists y \in L. xy \in R\right\}$$

Here is a constructive solution using a non-deterministic finite automaton (NFA) to show $R/L$ is regular when both $R$ and $L$ are regular.

Let $(Q_1,\Sigma,\delta_1,s_1,F_1)$ and $(Q_2,\Sigma,\delta_2,s_2,F_2)$ be deterministic finite automata for $R$ and $L$ respectively. Define a NFA

$$D=(Q_1 \times \{s_2\} \times \{1\} \cup Q_1 \times Q_2\times \{2\}, \Sigma, \delta, (s_1,s_2, 1), F_1 \times F_2\times \{2\})$$
where the transitions are:

$\delta((q_1,s_2,1),\sigma) = \{ (\delta_1(q_1,\sigma),s_2, 1)\}$.
$\delta((q_1,s_2,1),\epsilon) = \{ (q_1,s_2, 2)\}$.
$\delta((q_1,q_2,2),\sigma) = \{ (\delta_1(q_1,\sigma),\delta_2(q_2,\sigma), 2)\}$.

I'll leave it as an exercise for you to verify the language accepted by $D$ is $R/L$.


Algorithms computing if a number is a multiple of 3

What about a finite state automaton for the job?

Of course the magic is just computation modulo 3. Adding symbol $a$ behind string $x$ means the "binary value" of the string goes from $val(x)$ for $x$ to $2\cdot val(x)+a$ for $xa$. Consequently from state $p$ and symbol $a$ we move to state $2p+a \bmod 3$, for $p\in \{0,1,2\}$ and $a\in \{0,1\}$. Note $x\in \{0,1\}^*$ is a string, wheras $val(x)\in \Bbb{N}$ is its value as binary string.


Lower bound for finding kth smallest element using adversary arguments

I am going to briefly outline a sketch of an adversary argument.

Consider your selection algorithm playing against an opponent that we will call the adversary.The aim of the adversary is to provide an input $X$ for your algorithm that maximizes the number of comparison operations done by your algorithm. Indeed, your algorithm can be seen as a comparison tree, in which a path corresponds to a partial order. When the algorithm asks the adversary about a pair $(x, y)$ of elements, the adversary returns either $x < y$ or $y < x$. The adversary answers can never contradict previous outcomes.

Assume that the $k$-th largest element is $x^*$: considering the partial order associated to any leaf of the comparison tree, then $x^*$ must be comparable with every other element in order for the algorithm to be correct, so that the algorithm must have made at least one comparison $(y, z)$ $\forall y \neq x^*$ whose outcome is either $y < z \leq x^*$ or $x^* \leq z < y$. Call such a comparison crucial for an element $y$. Obviously, the adversary wants to maximize the number of non crucial comparisons done by your algorithm.

Let $L$ be the set of $k−1$ largest elements; your algorithm needs to correctly identify all of the elements in $L$ and also the largest element in $X \setminus L$, i.e. $x^*$. Observe that each element in $X \setminus L$ has lost at least one crucial comparison. Now, the adversary has a strategy that forces each of the $k - 1$ elements in $L$ to win at least $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$ comparisons, none of which is crucial for $X \setminus L$. Adding the remaining $n - k$ crucial comparisons for $X \setminus L$ you obtain the lower bound. For details, please read the following, excellent, Jeff Erikson notes.


Does a polynomial solution to weakly-NP Complete problem mean P = NP?

All weakly NP-complete problems are NP-complete by definition,
so yes, a polynomial time algorithm would imply P = NP.


Finding undirected cycles in linear time (triangulating graphs while minimizing degree)

Which algorithm does "Eulers technique to find an Eulerian cycle" refer to?

It probably refers to the Hierholzer algorithm (wiki) which takes linear time.

The algorithm below is from the wiki article.

Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$.
It is not possible to get stuck at any vertex other than $v$, because the even degree of all vertices ensures that, when the trail enters another vertex $w$ there must be an unused edge leaving $w$.
The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and join the tour formed in this way to the previous tour.

  What is the "simple modification" in question?

Hierholzer algorithm aims to apply to Eulerian graphs which are (and should be) graphs with every vertex of even degree. In your problem, $H$ is not necessarily an Eulerian graph.

So it needs modifications: In step 1, the closed tour from $v$ to $v$ may not exist at all; and in step 2, you may not be able to start another trail from $u$, or you may not be able to return to $u$.

  Thus $H−C_{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

This can be seen from Figure 7(b) in the paper.


Simple question: Pushdown automata transition

This depends on the formalism you are using.

As a "abstract data structure" you would have simple instructions like push(symbol), pop, top, isempty that you then can program as an add-on to a finite state automaton.

In standard formal language theory one uses a single instruction of the form you describe $(p,a,A,q,\gamma) \in \delta$ means: in state $p$ with $A$ on top of the stack we can pop $A$ and push the symbols $\gamma$ and move to state $q$. Thus we can indeed push several symbols at once, and we always pop one. With this single instruction we can also pop a symbol (by not pushing anything back) or keep the stack unchanged (by pushing back what has been popped).

In the Sipser book the formalism is different for instance.


Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation.

The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. You can't do that if you don't know the nodes at the start of the algorithm.  However, Dijkstra doesn't need to do this and, even if you do know the graph before you start, it's not very efficient.  It's enough to add the nodes to the queue as you discover them.  This variant of the algorithm is often called "uniform-cost search" (especially in AI), though some people argue that it's just Dijkstra's algorithm and that Dijkstra never really intended to add all the nodes to the queue at the start.

If you look at the two algorithms/versions of the algorithm, you'll see that a node that classical Dijkstra thinks is at distance infinity is a node that has not yet been added to the queue in uniform-cost.

Ariel Felner gave a good analysis of the relationship between classical Disjkstra and uniform-cost in Dijkstra's Algorithm versus Uniform Cost Search or a Case Against Disjkstra's Algorithm (Proc. 4th Intl. Symposium on Combinatorial Search (SoCS 2011), AAAI Press, 2011; PDF).


What are the minimum and maximum numbers of elements in a heap of height h?

A heap of height $h$ is complete up to the level at depth $h-1$ and needs to have at least one node on level $h$.
Therefore the minimum total number of nodes must be at least
$
\sum_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h.
$, and this tight since an heap with $2^h$ nodes has height $h$.


Concatenation of the intersection of two languages

First, you may notice that there is a one-sided containment here. It always holds that
$(L_1\cap L_2)L_3\subseteq L_1L_3\cap L_2L_3$ (prove it!)

From this, you see that in order for the equality to fail, you need to get a strict containment.
Intuitively, this means that you need the concatenation with $L_3$ to add words to both $L_1$ and $L_2$.

One way to achieve this is, for example, to first let $L_1\cap L_2=\emptyset$, and then "tailor" $L_3$ to fix this emptiness.

A concrete example is below (hidden as spoiler, hover mouse to see it):

  $L_1=\{a\}$, $L_2=\{aa\}$, $L_3=\{a,\epsilon\}$.


Solving a variant of the Exact cover problem

There's no pseudopolynomial algorithm for exact cover (unless P=NP), so it is easy to show that this implies there is no pseudopolynomial algorithm for twice-exact-cover, either.

For instance, here's an easy reduction.  Given an instance $(S,X)$ of exact cover (where $S$ is a collection of subsets of $X$), let $X' = X \cup \{a\}$ where $a \notin X$ is a new symbol, and $S' = S \cup \{X', \{a\}\}$.  Now there is a twice-exact-cover for $(S',X')$ iff there is an exact cover for $(S,X)$.  So, if you could solve twice-exact-cover in pseudopolynomial time, you could solve exact cover in pseudopolynomial time, too.


How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?

It is very unlikely indeed that finiteness is truly what you are looking for. Would you really be happy with a program that takes $10^{10^{40}}$ steps to complete?

If I am right, "non-haltingness" is not the real quality you are looking for. It is "halting within a reasonable time".

The best way to express this is not as a pure timeout, but by defining a measure of utility which declines with an increasing number of steps. That will give your evolutionary mechanism a steady "push" in the right direction. As for whether it is $1/n$, $1/\sqrt n$, $2^{-n/c}$, that is something you can decide.

Of course in practice a program that takes more than a certain number of steps is going to carry on going for ever. But you can encapsulate this intuition into the algorithm by saying that if, after $n$ steps, the overall utility has declined to a point when it is too low to be worth considering and it is never going to increase if you carry on stepping. Thus the timeout is still there, but as an implementation detail and not as a primary principle-in-itself.


From the Barendregt lambda calculus book, we can find theory $CL$ (combinatory logic) defined as follows

$$
    K P Q = P \qquad
    S P Q R = P R (Q R)
$$

where $K,S$ are constant symbols (for the well known combinators), while $P,Q,R$ range over all the possible $CL$ terms (built from $K,S$, variables and application). The relation $=$ is postulated to be a congruence.

The $CL$ theory can be extended with the following $A_\beta$ axioms:

$$
\begin{array}{ll}
A.1 & K = S(S(KS)(S(KK)K))(K(SKK)) \\
A.2 & S = S(S(KS)(S(K(S(KS)))(S(K(S(KK)))S)))(K(K(SKK))) \\
A.3 & S(S(KS)(S(KK)(S(KS)K)))(KK)=S(KK) \\
A.4 & S(KS)(S(KK)) = \\
    & \qquad S(KK)(S(S(KS)(S(KK)(SKK)))(K(SKK))) \\
A.5 & S(K(S(KS)))(S(KS)(S(KS))) = \\
    & \qquad S(S(KS)(S(KK)(S(KS)(S(K(S(KS)))S))))(KS)
\end{array}
$$

(I have double checked these, but I can't swear I got them right.)

Corollary 7.3.15 states that $CL\ +\ A_\beta$ is equivalent to $\lambda$ (the theory of the $\lambda$ calculus with $\beta$ conversion, but no $\eta$ or extensionality).

Hence, in principle one can use "only" the above laws to prove $SKK=SKS$.

The convenience of the above laws is self-evident, I think.

A similar set of axioms is found in the same book for $\lambda\eta = \lambda + \bf ext$. These are $A.3,A.4,A.5$ (hence no $A.1,A.2$) and

$$
\begin{array}{ll}
A.6 & S(S(KS)K)(K(SKK)) = SKK
\end{array}
$$


#3-Coloring Problem for Tree with Some Pre-Colored Nodes

Many problems on trees can be solved using dynamic programming. Let me explain how to solve a similar problem, independent set with fixed vertices. In this problem, you are given a tree $T$ and an independent subset $I$ of its nodes, and your task is to count all independent sets which contain $I$.

Arbitrarily root $T$ at some vertex $r \in T$. For every vertex $v \in T$, let $T_v$ be the subtree of $T$ rooted at $v$. For every $v \in T$, we will calculate two quantities:

$\alpha_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ and $v$.
$\beta_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ but not containing $v$.

We calculate these quantities recursively, as explained below, and output $\alpha_r + \beta_r$, which is the total number of independent sets in $T$ containing $I$.

The base case is when $v$ is a leaf. If $v \in I$ then $\alpha_v = 1$ and $\beta_v = 0$, and otherwise $\alpha_v = \beta_v = 1$.

Now suppose that $v$ is an internal node, say with children $v_1,\ldots,v_m$. If $v \in I$ then $\beta_v = 0$ and $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, since an independent set containing $v$ cannot contain any of its children. If $v \notin I$ then it is still the case that $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, and additionally $\beta_v = \prod_{i=1}^m (\alpha_{v_i} + \beta_{v_i})$, since we don't have any constraints on the $v_i$.

Now that the algorithm is laid out, you can check that it runs in linear time. Your problem can be solved in a similar fashion, also in linear time.


Can the subset sum problem work with an undefined set?

If you only have extra impurities, then the DECOMP program described in the following paper will efficiently solve the problem -- even if you only have an approximate mass difference $d$ to work with:

DECOMP--from interpreting Mass Spectrometry peaks to solving the Money Changing Problem (Böcker S., Lipták Z., Martin M., Pervukhin A., Sudek H. 2008)

The paper cites earlier papers by the same authors that describe the underlying Round Robin algorithm -- a very nice and fast algorithm based on Frobenius numbers for solving a problem that people previously resorted to tables computed using brute-force to solve.

To deal with "negative impurities" (components that should be present but are absent from the experimental sample), I think your best option is to try all possible "missing mass" values $a$ in a small range that includes zero, and for each such value $a$, use DECOMP to solve two problems: One that finds all possible combinations of "missing" components that solves for $a$, and one that finds all possible combinations of "extra" components that solves for $d+a$.  Every pair of (missing, extra) component multisets is then a solution for the chosen $a$.

Bear in mind that, if there is a subset of components that sums to zero, then there will be an infinite number of solutions, since it is always possible to add another copy of this component subset to a solution to get another valid solution.


Subgraph Isomorphism checking in Multigraphs

Submultigraph isomorphism is clearly NP complete:

it's easily seen to be in NP (an isomorphism can be specified in space polynomial in the size of the graphs, and it's easy to check that a proposed isomorphism is valid);
it includes the NP-complete subgraph isomorphism problem as a special case.

The more interesting question is what the best known algorithms are; I'm afraid I can't help with that.


How long is the word "cat"?

If I write "catcat", how long is the word "cat"?

If I write nothing at all, how long is the word "cat"?


Why is the Mersenne Twister regarded as good?

The initial Mersenne-Twister (MT) was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs.
This page lists the Mersenne-Twister features in detail:
Positive Qualities

Produces 32-bit or 64-bit numbers (thus usable as source of random bits)
Passes most statistical tests

Neutral Qualities

Inordinately huge period of $2^{19937} - 1$
623-dimensionally equidistributed
Period can be partitioned to emulate multiple streams

Negative Qualities

Fails some statistical tests, with as few as 45,000 numbers. Fails LinearComp Test of the TestU01 Crush and BigCrush batteries.
Predictable — after 624 outputs, we can completely predict its output.
Generator state occupies 2504 bytes of RAM — in contrast, an extremely usable generator with a huger-than-anyone-can-ever-use period can fit in 8 bytes of RAM.
Not particularly fast.
Not particularly space efficient. The generator uses 20000 bits to store its internal state (20032 bits on 64-bit machines), but has a period of only $2^{19937}$, a factor of 263 (or 295) fewer than an ideal generator of the same size.
Uneven in its output; the generator can get into “bad states” that are slow to recover from.
Seedings that only differ slightly take a long time to diverge from each other; seeding must be done carefully to avoid bad states.
While jump-ahead is possible, algorithms to do so are slow to compute (i.e., require several seconds) and rarely provided by implementations.

Summary: Mersenne Twister is not good enough anymore, but most applications and libraries are not there yet.


Maximum subset pairwise not divisible by $K$

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words,

$$K \mid ( n_1 + n_2 ) ~~~~ \Longleftrightarrow ~~~~ K \mid \left((n_1 ~mod ~K) + (n_2 ~mod ~K)\right).$$

The second concept that you need to consider is that, the sum of two numbers $r_1 \neq r_2$ is $K$, only if one of them is strictly smaller than $K/2$ and the other is no less than $K/2$. In other words,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ r_1 <K/2, ~r_2 \geq K/2~~~~~~ (r_1 \neq r_2,~\text{w.l.g.}~r_1 < r_2).$$

The third concept that you need to consider is that, if the sum of two numbers $r_1 \neq r_2$ is $K$, they both deviate from $\lceil K/2 \rceil -1$ by a certain $k \leq \lceil K/2 \rceil$, i.e.,

$$r_1 + r_2 = K ~~~\Rightarrow~~~ \exists_{k \leq \lceil K/2 \rceil -1}~~~\text{such that}~~~ r_1 = \lceil K/2 \rceil -1 -k, ~r_2  = \lceil K/2 \rceil +k.$$

So, for evey $k$ in the third concept, you need to put either $r_1$ or $r_2$ in the solution set, but not both of them. You are allowed to put one of the numbers that are actually divisible by $K$ and if $K$ is even, you can add only one number that its remainder is $K/2$.

Therefore, here is the algorithm.

Given a set ${\cal N}=\{ n_1, n_2, \cdots, n_N \}$, let's find the solution set ${\cal S},$

Consider ${\cal R} = \{ r_1=(n_1 ~mod ~K), r_2=(n_2 ~mod ~K), \cdots, r_N=(n_N ~mod ~K) \}$
${\cal S} \gets \emptyset$
for $k \gets 1$ to $\lceil K/2 \rceil -1$:
$\hspace{1.3em}$ if $count({\cal R},k) \geq count({\cal R},K-k)$:
$\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=k$
$\hspace{1.3em}$ else:
$\hspace{2.6em}$ add all $n_i$ to ${\cal S}$, such that $r_i=K-k$
add only one $n_i$ to ${\cal S}$ such that $r_i=0\hspace{1em}$// if exists
if $K$ is even:
$\hspace{1.3em}$ add only one $n_i$ to ${\cal S}$ such that $r_i=K/2\hspace{1em}$// if exists
Output ${\cal S}$

The algorithm is quite long, but the idea is very simple.