Is it true that the set $0^{n^2}$ is not regular because it does not grow linearly?

Yes, that's true. That follows from the pumping lemma as explained in the paragraph you quoted.

  Therefore, $a^{n^2} b^n$ ... is not regular?

Yes, that's also true for the same reason.

  Also, I know that $a^n b^n$ is not regular, but what about $a^{cn} b^{dn}$ for any integer coefficients $c$ and $d$?

The language $\left\{a^{cn} b^{dn} \mid n \in \mathbb{N}\right\}$ where $c$ and $d$ are fixed is regular if and only if $c$ or $d$ is equal to 0.


termination of two concurrent threads with shared variables

This trace is possible, in two separate threads T1 and T2. $state$ is $(x,y)$.

T1: ... $state=(0, 4)$
T1: x = x + 1; y = y - 1 $~~state=(1, 3)$
T1: x = x + 1; y = y - 1 $~~state=(2, 2)$
T2: x == y evaluates to true, pass and then x = 0; $~~state=(0, 2)$
T1: x != y evaluates to true, x = x + 1; y = y - 1 $~~state=(1, 1)$
T2: y = 2 $~~state=(1, 2)$
T1: x != y evaluates to true, x = x + 1; y = y - 1 $~~state=(2, 1)$
$state=(3, 0)$
$state=(4, -1)$
...

(Note that it works even if x = expr; is atomic)

There are other possible interleavings. The point $(2,2)$ is common to all of them, where T1 has pending (logically) atomic instructions:

T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y - 1); pop@y; repeat
T2: (x != y) ? repeat : x = 0; y = 2;

In the first case, T1 proceeds to stop and then T2 can only proceed and the final state is $(0,2)$.

If T2 finally skips the repeat and (T1:push x) is run before (T2:x = 0) then T1 will stop looping and the same final state is reached.

If T2 finally skips the repeat and (T1:push x) is run after (T2:x = 0) then T2 can proceed after the stop independently of (T1:y = 2).

state = (0, 2)
T1: push(x + 1); pop@x; push(y - 1); pop@y; ...
T2: y = 2;

If T2 is run now then it will loop as above, so T1 proceeds:

state = (1, 2); stack = 1
T1: pop@y; ...
T2: y = 2;

If T2 is run now, this will go to the final state $(1,1)$. Otherwise:

state = (1, 1)
T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y + 1); pop@y; repeat
T2: y = 2;

If T2 does not act before push y, this will stop and go to the state $(1,2)$. If it does, then the state is $(1, 2)$ and this will loop into $(2,1)$, $(3,0)$, ...

To sum up the possible final states are $(0,2)$, $(1,1)$, $(1,2)$. I don't think it was worth the effort though, since I probably made mistakes.


Showing that graph of spanning trees are connected

Use induction on the number of edges and vertices in $G$.  Fix some edge $e$ of $G$.  If $S$ and $T$ are two different spanning trees that do not use $e$, apply the induction hypothesis on the graph $G\setminus e$.  If both use $e$, apply the inductive hypothesis to the contracted graph $G/e$.  If only one does, w.l.o.g., $S$, replace $T$ by $T'$, obtained by adding $e$ to $T$ and removing any edge in the (unique) cycle in $T+e$.  Either $T'$ is $S$, or we are back in a previous case.


Proving there exists an infinite number of Turing machines is a decidable problem

Given $L(M)$, there are countably infinite number of Turing machines that accept this language. You already describe in your post how to generate these machines. Thus the problem

  are there infinitely many Turing machines that recognize L(M)

is decidable. The TM machine that decides it simply outputs $1$ (ACCEPTS) on any input $\langle M \rangle$.

Note that your TM $N$ does not need to construct all machines, it just needs to always response "YES" since for any $M$ indeed there exists infinite number of TMs accepting $L(M)$.


What are examples of $\mathsf{NL}$-complete problems?

Here are three more examples, taken from an assignment by Trevisan:

Given an NFA and a word, determining whether the NFA accepts the word.
Reachability in DAGs.
Determining whether a digraph is strongly connected.

Planken shows that the Simple Temporal Problem with bounded weights is NL-complete (see the link for definitions).

There are likely many others. Schaefer's dichotomy theorem, in particular, gives many examples.


Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

Let's start by considering the case of a full tree (depth $\lg n$, contains exactly $n$ leaves, where $n$ is a power of two).  It's possible to build an algorithm for this case with space complexity $O(\lg n)$ and total running time $O(n)$.

In particular, Hendrik Jan describes an elegant algorithm whose running time is $O(n)$.  Let me flesh out the details.  Consider a $\lg n$-bit counter, whose value is stored in binary, and that supports one operation: Increment (adds one to the counter).  How many bits needed to be flipped by each invocation of the Increment operation?   The answer is $\lg n$ in the worst case (when you increment from $0111 \cdots 1$ to $1000 \cdots 0$), but a standard analysis shows that the amortized number of bit-flips is $O(1)$ -- the amortized analysis is a standard exercise in many algorithms textbooks.

Note that you can treat any bit-string $x$ of length $\le \lg n$ bits as a specification of a path from the root of the tree to some node $n(x)$ ($0$ means go left; $1$ means go right; the most significant bit is the first branch taken in the path; the least significant bit is the last branch).
Suppose the $\lg n$ bits stored in the counter are denoted $b_1,\dots,b_{\lg k}$.  Treat the bit-string stored in the counter as a specification of a path to a leaf.  Also, for each index $i$, store a pointer to the node $n(b_1 \cdots b_i)$, i.e., the node reached by following the path that corresponds to the first $i$ bits in the counter (the $i$ most significant bits).  This takes $O(\lg n)$ space.

Now we're going to repeatedly increment the counter, and update the pointers.  We only need to update a pointer when its corresponding bit flips: e.g., if $b_i$ changes, we'll need to update the pointer $n(b_1 \cdots b_i)$.  This update can be done in $O(1)$ time, by using the pointer to $n(b_1 \cdots b_{i-1})$ and then looking at its left or right child (depending on whether $b_i=0$ or $b_i=1$ after the update).  Importantly, whenever bit $i$ flips, so do all of the bits $i,i+1,i+2,\dots,\lg n$, so all of the pointers will be updated as necessary.  Thus, at every point in time all $\lg n$ pointers are correct.

What's the running time?  We only update a pointer when its corresponding bit changes.  Each time we update a pointer, we do $O(1)$ work.  Therefore, the total number of operations is equal to the total number of bits that have changed, as we increment the counter from $1$ to $n$.  But now it's a standard result that the amortized running time of the Increment operation is $O(1)$ bit flips: i.e., you can increment the counter $n$ times, at the cost of a total of $O(n)$ bit flips.  Therefore, the running time of this algorithm is $O(n)$, and the space complexity is $O(\lg n)$.  The constants hidden by the big-O notation are relatively small: e.g., the total number of bit flips is $\le 2n$, so you'll follow about $2n$ child pointers, and you only need space for $\lg n$ pointers.

What if the tree is not full?  In other words, maybe the tree has $n$ leaves and depth $c \lg n$.  Then a bunch of subtrees are missing.  However, I think it is possible to just skip over them as you increment the counter.  Therefore, it looks to me like the total running time should remain $O(n)$ for this case, and the space complexity will be $O(\lg n)$.  I confess I haven't checked the details of this part carefully, but it looks like it should work out.


If A is in P and B is non-trivial, then A ≤p B

First, it's important to realize here that the output of a decision problem will always be "Yes" or "No." So what this is saying is basically that $B$ has at least two inputs $x,y$ where $x \in L_B$ and $y \not \in L_B$, if $L_B$ is the set (language) of all accepted inputs to $B$.

Let's let $B$ be SAT. We'll take two instances, $x = v_1 \vee \neg v_1$, which has a solution and thus is in SAT, and $y = v_1 \wedge \neg v_1$.

Let's let $A$ be the undirected graph-connectivity problem. We know that we can solve this in polynomial time using Breadth First Search.

So, given a graph $G$ as input to $A$, we'll define a function $f$:

$f(G) = x$ if $BFS(G)$ returns connected

$f(G) = y$ if $BFS(G)$ returns not connected

Clearly, we can compute $f(G)$ in linear time for any graph, since it's just a breadth-first search. Moreover, we see that $G$ is connected if and only if $f(G) \in SAT$.

The whole process is kind of trivial (in the mathematical sense), because we're basically saying "If we could solve $B$ in polynomial time, we could also solve $A$ in polynomial time". But we can always solve $A$ in polynomial time, so the whole thing is trivially true.

It holds for the same reason $P \implies \top$ is always true.


What are the implications of Homotopy Type Theory?

I won't lie: I don't understand the homotopy part of homotopy type theory. But I have a decent grasp of Univalence, which is the axiom at the heart of Homotopy Type Theory (HoTT).
The main idea of univalence is that we treat equivalences (essentially, isomorphisms) as equalities. When two types are isomorphic, you have a way to get from one to the other and back, and the round-trip is the identity in both directions. But there's no way to lift properties between isomorphic types: if you have a proof that 2 is the only even prime for unary natural numbers, you can't automatically lift the proof of that property to binary natural numbers, even though you can convert 2 back and forth between the formats.
The eliminator for equality (sometimes also called the $J$ axiom) allows you to lift any property between equal things. So if we have an equality for every isomorphism, then we could transport the above property from unary to binary numbers. This is what univalence gives us: an axiomatic way to lift properties over isomorphisms.
The main implications of this are:

For programming: univalence is specifically about equality types, which are dependent types, so it only really affects dependently typed languages. What it allows us to do in those languages is to write code using efficient data structures, show that those structures are isomorphic to simpler structures, prove things about the simpler structures, and automatically lift those proofs back to the automatic structures.
For math, it makes formal something that has been implicit for a long time, which is that mathematicians tend to treat isomorphic things as if they were equal. Univalence provides a foundation that justifies this. So it brings the "formalized" math of proof assistants closer to the way mathematicians think of math.

There are also some cool things you can do with univalence. You can define Higher Inductive Types (HITs), where in addition to giving data constructors for inductive types, you give path constructors, which are equalities that must hold. When you pattern match, you then have to show that you preserve these equalities.
HITs allow you to do things like "define integers as a natural plus a sign but, but ensure that positive and negative 0 are truly equal.
However, there are some strange consequences to univalence. First, it means that we cannot have $Refl : x \equiv x$ as the sole way to construct an equality proof, because univalence lets us construct equalities between things that are definitely not syntactically identical. This means that univalence is incompatible with "Uniqueness of identity proofs" and axiom $K$. In practice, this means that the rules of dependent pattern matching must be weakened to be consistent with univalence. Jesper Cockx has a whole line of research on how to do this well.
The other problem is that we lose "canonicity" i.e. the idea that every term can be fully evaluated to a value in canonical form. For equality, Refl is the only canonical proof of equality. So this means that when running programs, sometimes we get "stuck" on the use of univalence as an axiom. This makes sense: we basically said "pretend I have a function that transforms isomorphisms into equalities". We never gave that function, so if we try to evaluate code that calls it, we'll get stuck.
The main effort to solve this problem is Cubical Type Theory. Cubical models equality in such a way that canonicity is preserved, but univalence can be proved as a theorem in the language. So univalence is now not an axiom, it's an actual function that can be applied.
If you're interested in this more, there are two main resources I'm familiar with. The HoTT Book is the canonical reference. There's also  Univalent Foundations in Agda, which is less focused on the homotopy theory, and more on the implications that univalence has for logic. I'm sure there are also more books I'm not familiar with. The Cubical Agda paper is also good.


Running Floyd-Warshall algorithm on graph with negative cost cycle

I think the answer is 4, and here is why.

Assume the graph is fully connected with all edges having weight of -1.

Now let's consider the three loops of Floyd-Warshall algorithm:

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:

Since -2 is "shorter" than -1, after we finish k = 1, the weight for i -> k = 1 -> j is -2 for most i and j (exceptions would be i = k and j = k).

After we finish k = 2, the weight for i -> k = 2 -> j is -4 for most i and j. This is because i -> 1 -> 2 -> 1 -> j is the shortest, giving us -4.

And so on and so on for the exponential growth.

Floyd-Warshall algorithm does not guarantee that we will find a simple shortest path, that is, a path containing only one instance of each vertex.


How does the ID3 Algorithm differ from a generic Decision Tree learning algorithm

The ID3 algorithm is an algorithm for inferring a decision tree: given a training set, it tries to find a decision tree that tends to label a large fraction of the training set accurately.  See, e.g., https://en.wikipedia.org/wiki/ID3_algorithm.

There is no such thing as "the generic decision tree learning algorithm".  There is no such generic algorithm.

There are many algorithms for learning a decision tree.  ID3 is probably the most well-known algorithm for decision tree learning, and the simplest, but there are other algorithms.  Other algorithms include C4.5, CART, and others.


How does a computer remember the address of a data variable in a program, in the main memory?

Suppose the computer stores the address of 'a' as 0x00104.

No, 'computer'(?) nowhere stores the address of 'a'. Compiler or assembler converts source code into object modules. Those object modules have instructions and data. 'a' is symbolic address which is bound by compiler to relocatable address. The linkage editor or loader in turn bind the relocatable address to absolute address. So, there is no storage but binding. Note that the absolute binding can be done at either compile time, load time or execution time where relocatable address binding will be done in any case by the compiler.


What is the difference between a state machine and a database

State machines and databases are quite different entities, and their usage (or functionality) is very different.
In this answer, I'll just try to separate them with respect to the similarity you mention. This is by no means a comprehensive description of neither state machines nor databases.
The states of a state machine can indeed be thought of as representing data (although this is not always obvious, and sometimes state machines do not reveal what data they store in their states). However, the crucial element of a state machine is the transitions between the states, which represent the behaviour of the machine.
That is, a state machine does something. It computes. During its run (or runs, in nondeterministic models), it moves from state to state according to some predetermined set of rules, and possibly according to a given input, and this process is called a computation. At the end of the computation (if it's finite), you might receive an output, from which you can derive some information.
For example, a Turing machine receives an input and if it halts, tells you whether the input is accepted or rejected, from which you can formalize a decision problem.
Similarly, an automaton does the same, but without external memory.
In contrast, a database merely stores data. How this storage is done, which operations are allowed on the data, and what their respective complexity is, are all interesting questions, and their answers depend on the type of database you use.
However, databases do not compute anything by themselves, they just store the data, possibly efficiently.


Which algorithm to use to find all common substring (LCS case) with really big strings

I came across this problem before. I compressed the strings and applied dynamic programming on the compressed strings.

For compression techniques, I followed the methods described in this paper:
http://pdf.aminer.org/000/145/966/data_compression_using_long_common_strings.pdf

The speed was decent. But, it consumed some space though.


Calculate the area of the shape created by multiple paths

With the help from some of the hints on this post and elsewhere, I came up with a solution.
The Data Structure
The data structure is relatively simple. It is a collection of Nodes that are connected by Edges.

Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.
The Algorithm
Find All Cycles

Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.

Record whether the angle between the connecting edges is a reflex angle (> 180 degrees) or not.

Record the series of nodes visited

Mark the edge as used

Follow that new edge to the next node and repeat until reaching the first node again.

At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an outside cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.
Repeat this cycle finding process until every edge has been used.
Filter Polygons
Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.
Calculate the Area of Each Remaining Polygon
At this point, we just need to calculate the area of each polygon and add them together for our solution.
Some Details
It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.
Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.
Example
All of the cycles from my original example are represented here:

For more information on my process and a walk through of the algorithm, you can see my case study.


Not a counter model, for as you say, the antecedent is not true when $x = 0$.
A counter model:  Every number has a number less than it in $\mathbb{R}$, however there are no least number.
A counter model:  For $x$, let $y = 1/x$, so the antecedent holds, there is no $y$ such that for all $x$, we have that $x \cdot y = 2$.
Not a counter model:  The consequent is always true, let $y = \epsilon$, then for all $x$, it holds that $yxy = x$.


Is this scheduling problem with arrival times, deadlines, and costs NP-hard?

The following observation enables a polynomial-time algorithm:

Whenever the time slot $t_i$ for a job $i$ has been chosen, it's optimal to assign the same time slot for all lower-cost jobs that overlap $t_i$, as doing so will incur zero additional cost.  Therefore, choosing the time slot for the most costly job "magnetises" all the jobs that can be assigned the same time slot, and partitions the remaining jobs into two sets: those whose intervals are completely to the left of this time slot, and those whose intervals are completely to the right.  The subproblems for these two sets of jobs can then be solved independently.

A general subproblem can be described by an interval $(a, b)$ and a maximum cost $c$: the jobs in this subproblem consist of all those jobs whose intervals fall within $(a, b)$ and which have cost at most $c$.  The optimal solution for a subproblem can be found by trying every possible time slot for the most costly job in the subproblem, and solving the corresponding 2 subproblems for each attempt.  A plain recursive strategy would take exponenential time, but there are only $O(n^3)$ distinct subproblems to solve: There are only $O(n)$ "basic intervals" (maximal intervals that do not cross the beginning or end of any job interval) to consider, so there are at most $O(n^2)$ possible intervals (blocks) of these, and $O(n)$ possible different job costs.  Thus dynamic programming can be applied.  It should be possible to test each of the $O(n)$ possible time slots available for the most costly job in $O(1)$ time each, excluding the time needed to solve subproblems, for $O(n^4)$ time and $O(n^3)$ space overall -- not fast, but certainly polynomial.


context sensitive language finite or infinite

It's a standard theorem that it's undecidable whether a given context-sensitive grammar generates the empty language or not.

From this, we can prove that it's undecidable whether a context-sensitive grammar is finite or infinite.  Let $L$ be a context-sensitive language.  By the standard closure properties for CSL's, if $L$ is context-sensitive, then so is $L^+$.  Now if $L$ is empty, then $L^+$ is empty (and thus finite); but if $L$ is non-empty, then $L^+$ is infinite.  Consequently, if it were decidable to check whether a CSL is finite or infinite, we could apply that decider to $L^+$ and learn whether $L$ was empty or not -- but the theorem mentioned above implies this is impossible.

Therefore, determining whether a given context-sensitive grammar generates a finite or infinite language is undecidable.

Footnote: You can find a proof of the standard theorem above in many places; e.g., these lecture notes from CS 373 at U Illinois.  The result is also mentioned in passing on Wikipedia, which cites Hopcroft and Ullman -- a standard resource on formal languages.  The same Wikipedia article also mentions some smaller classes of languages that are contained in CSL.


If A and B are NP-complete, then A ∪ B need not be NP-complete

P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.


Can someone help me fully grasp idea and time/space complexity with this code?

You are completely correct in your analysis.
Space.  You construct an array $x$ which has length the same as that of $b$, which is $n$.  It contains a pair for each element in $b$, so it has size $O(n)$.  The other variables do not count, hence space complexity is indeed $O(n)$.
Time.  You correctly observed that the sorting of $x$ takes time $O(n \log n)$, and that both iterations take time $O(n)$.  Everything else is arithmetic operations, which all run in $O(1)$ time.  Hence, something like $O(n) + O(n \log n) + O(n) + O(1)$, which all in all results in a time complexity of $O(n \log n)$.
Well done!


Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?

No - even within (say) the class of $\Sigma_1$ (= c.e., r.e., semidecidable, ...) sets, there is lots of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions).
The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing degree is strictly between ${\bf 0}$ (= computable) and ${\bf 0'}$ (= halting problem)? This was answered about a decade later by the Friedberg-Muchnik theorem, which showed that there are Turing-incomparable (so a fortiori many-one-incomparable) c.e. sets. Their argument generalizes immediately to get a countably infinite sequence of Turing-incomparable c.e. sets. Later, Sacks proved that whenever we have c.e. sets $A<_TB$ we can in fact find a sequence $(C_i)_{i\in\mathbb{N}}$ of c.e. sets which are Turing-incomparable to each other and which all lie strictly between $A$ and $B$ in terms of Turing reducibility (this is basically his density theorem + a bit of elaboration). Note that Sacks' theorem also shows that there are infinite increasing and infinite decreasing sequences of Turing degrees as well as infinite antichains.
So there is extremely rich non-linearity there. In fact, though, that's only the beginning of the story. The structure of $\mathcal{R}$ (= the Turing degrees of c.e. sets, ordered by Turing reducibility) turns out to be extremely complicated, and there are still many major open questions about it. Soare's old book Recursively enumerable sets and degrees contains a lot of information on the topic, which really picks up in earnest at chapter $7$ (where priority arguments, the method developed by Friedberg and Muchnik and later elaborated by Sacks and others, are first introduced); Soare also wrote a medium-length survey paper on the topic.

EDIT: Even though it's not directly related to the OP let me address a common related question: namely, how the c.e. degrees (= Turing degrees of c.e. sets) sit inside the poset of all Turing degrees.
We know that every c.e. set is Turing reducible to the halting problem, so every c.e. degree is $\le_T{\bf 0'}$. The converse however is false: there are degrees below ${\bf 0'}$ which are not c.e. degrees. There is a "syntactic" characterization of $\{{\bf d}: {\bf d}\le_T{\bf 0'}\}$ but it's more complicated; see here.
(Incidentally, the easiest way I know to prove the existence of a non-c.e. degree below ${\bf 0'}$ is to $(i)$ prove Sacks' density theorem and $(ii)$ construct a minimal noncomputable degree below ${\bf 0'}$. This is rather a lot of work, but as far as I know there's no easier way of doing this!)
There is however a sense in which the degrees below ${\bf 0'}$ are "c.e. in flavor." Specifically, say that a set $X\subseteq\mathbb{N}$ is $2$-c.e. if $X=A\setminus B$ for c.e. sets $A,B$. We can similarly define $3$-c.e. and $n$-c.e. sets for all finite $n$, and even continue this into the transfinite in a precise sense. The resulting "hierarchy" (scarequotes since it's not linear!) is called the Ershov hierarchy, and with help from the limit lemma we can show that every set computable from ${\bf 0'}$ is $\alpha$-c.e. for some ordinal (or rather, ordinal notation) $\alpha$. The fact that $\le_T{\bf 0'}$ doesn't imply c.e. is extended by a general, if somewhat technical, non-collapsing result for the Ershov hierarchy; for example, there is a $2$-c.e. set not Turing-equivalent to any c.e. set (which I believe is due to Cooper).


Is there an algorithm to minimize working set during a topological traversal?

Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs.

We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph, whose pathwidth we want to compute. Now create an directed graph $H$, with vertex $v'$ for each vertex $v$ of $G$. For each edge $(u, v)$ of $G$, create a vertex $e_{(u,v)}$ and directed edges $(v', e_{(u,v)}'), (u', e_{(u,v)}')$.

Now consider a topological ordering of $H$. Define the corresponding sequence of working sets as $X_1, \ldots, X_p$. We prove that $X_1, \ldots, X_p$ is a path-decomposition of $G$. The working sets include only vertices of type $v'$, because the other vertices do not have outgoing edges. The working sets by definition satisfy the intersection property $i \le j \le k \rightarrow X_i \cap X_k \subseteq X_j$. If there is an edge $(u, v)$ in $G$, then there are edges in $H$ from both $v'$ and $u'$ to $e_{(u,v)}'$ so there must be a working set $X_i$ with $v', u' \in X_i$. Therefore each edge is a subset of some bag of the path decomposition and therefore $X_1, \ldots, X_p$ is a path decomposition of $G$.

We can also show that any path-decomposition of $G$ corresponds to a topological ordering of $H$ (consider the elimination ordering of the underlying interval graph). $\square$

For positive results, I would suggest at looking at some analogies of pathwidth for DAGs in literature. With a quick search I found the notions of directed pathwidth and DAG-width, but seems that they are not relevant here as they are trivial for DAGs.


Graphs in space efficient representation

Farzan and Monroe, Succinct Representations of Arbitrary Graphs, give such a representation with constant query time. See their Theorem 8.


The problem of equivalence of a CFG and a RG?

There is no algorithm which can determine for any context-free grammar $G_1$ and regular grammar $G_2$ whether $L(G_1) = L(G_2)$.

However, it may well be possible to determine for particular $G_1$ and $G_2$, using heuristic proof techniques (aka human intuition).

Good luck with the assignment.


Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?

If $T(n) = \Theta(n^3\log n)$ then it is always the case that $T(n) = \Omega(n^2)$ and $T(n) = O(n^4)$.
If $T(n)$ is the worst-case complexity of an algorithm, then furthermore its average-case complexity is $O(n^4)$, always.


Design an NFA to accept a, ad, abc, abd, but not e, abcd?

Your automaton has loops so it accepts an infinite language.

For finite languages $\{w_1, \dots, w_n\}$, it's easy to write them as regular expression

$\qquad w_1 \mid \ldots \mid w_k$

and apply Thompson's construction. If the resulting automaton is too ugly for your taste, determinize and minimize according to the canonical textbooks.

Warning: Determinizing automata for finite languages can blow up automaton size exponentially.

Note how this approach scales neatly to more concise representations of finite languages and even infinite languages -- all you need is a regular expression. Or any other formalism equivalent to finite automata, as the proofs of equivalence are usually constructive.


Constructing a PDA for the language $\{a^m b^n : m < 2n < 3m \}$

To handle the inequality $m \lt 2n$, you arrange to push a marker for each $a$, and pop two markers for each following $b$. This way the number of markers on the stack indicates the number of $a$'s. When the stack is empty, the equality is reached.

To handle the inequality $2n \lt 3m$, you could to arrange to push three markers for each $a$ and pop two markers for each following $b$. However, a stack won't let you push different numbers of markers.

There is no general way of “merging” two automata in this way. If the two automata use the stack at different rates, it may not be possible to merge them without having two stacks. This is reflected in the properties of languages recognized by pushdown automata: the intersection of two context-free languages is not always context-free.

To get an idea of what to do here, I think it helps to write a context-free grammar for this language. A grammar needs to break down the language into some recursive structure, which leads us to expressing elements of the language as expansions of shorter elements. I'll look at what happens when $b$s are added; you could obtain a different grammar by similar means by looking at what happens when $a$s are added.

If you add $1$ to $n$, what happens to the possible values of $m$? For the maximum value, it's easy: it increases by $2$, because $m \lt 2n \iff m+2 \lt 2(n+1)$. For the minimum value, it's more difficult: we need to find the threshold for $\frac{2}{3}n$, so it depends on whether $n$ is a multiple of $3$, which we cannot express in a grammar rule. However, if we add three $b$s at a time, it's easy: the minimum number of $a$s increases by $2$, because $2n \lt 3m \iff 2(n+3) \lt 3(m+2)$.

Let $L$ be the desired language. The rule above tells us how words in $L$ can be constructed from shorter words; we still need to check the base cases.
$$ \begin{align}
  L \cap a^* &= \varnothing \\
  L \cap a^* b &= \{ab\} \\
  L \cap a^* b^2 &= \{a^2b^2, a^3b^2\} \\
  L \cap a^* b^3 &= \{a^3b^3, a^4b^3, a^5b^3\} \\
\end{align} $$
We have all the information needed to construct a grammar for $L$.
$$
\begin{array}{rl}
  S &\to a b \\
  S &\to a^2 b^2 \\
  S &\to a^3 b^2 \\
  S &\to a^3 b^3 \\
  S &\to a^4 b^3 \\
  S &\to a^5 b^3 \\
\end{array}
\qquad
\begin{array}{rl}
  S &\to a^2 S b^3 \\
  S &\to a^3 S b^3 \\
  S &\to a^4 S b^3 \\
  S &\to a^5 S b^3 \\
  S &\to a^6 S b^3 \\
\end{array}
$$
If you're unsure about the correction of this construction, prove that all words in $L$ are recognized by this grammar (construct a derivation) and prove that all the words recognized by this grammar are in $L$ (by induction over the rules).

Now you can apply a systematic method for constructing a non-deterministic pushdown automaton from a grammar. Since the right-hand part of every rule is the same, it is enough to have a single element in the stack alphabet. Push this symbol for each batch of 2 to 6 $a$'s (this is non-deterministic); pop it for 3 $b$'s.


Mathematical optimization on a noisy function

One could replace the exact function $f(x,p)$ by the noisy function $f(x+\Delta x, p + \Delta p)$, where $p$ is an artificial parameter used to describe the noise dependency such that $\Delta x$ and $\Delta p$ contain the noise.

Some techniques used in stochastic optimization and robust optimization might be applicable.
Because $\frac{\partial f}{\partial x}\approx 0$ near the maxima, $\Delta x$ is less dangerous than $\Delta p$.
Sometimes $\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$ can be approximated accurately while evaluating $f(\tilde{x}, \tilde{p})$. Often, this is only true in theory, because it is not implemented, and some parts would require special care.
The desired "smallness" of $\Delta p$ (and $\Delta x$) is an "end user" decision. One can offer heuristics to control it, but a runtime proportional to $1/\epsilon^2$ is too slow for fully automatic accuracy handling.
The given noise vs runtime tradeoff is what sets this problem apart from better studied problems. Problems were the noise is just unavoidable are more common and better studied.


Are all problems approached and solved in fundamentally the same way?

What you're missing is that, although all NP-complete problems can be reduced to one another, so it is true that solving one lets you solve them all, that doesn't mean that they're all equally easy, so they're not all "the same problem".

In particular, the reduction takes some amount of time to perform.  Although all problems in NP can be reduced to, say, SAT, that doesn't mean that all problems in NP are as easy as SAT.  Some require very little effort to translate to SAT; others require much more effort. And there's no bound1 on how much effort might be needed, as you look at more and more complex problems within NP.

A way to make this concrete is with the time hierarchy theorem.  That says that, essentially, allowing more time for computations lets you compute more things, and it applies to nondeterministic machines as well as deterministic ones.  So, solving SAT instances takes some amount of time but, if you allow yourself more time than that, you can solve strictly more things.

1 OK, its always a polynomial but there's no bound on the degree of that polynomial.


What is the difference between SIZE(n^k) and P/poly?

SIZE($n^2$) consists only of problems that can be solved by circuit families of size at most $O(n^2)$.  P/poly contains problems that can be solved by circuit families of size at most $O(n^3)$, and those solved by families of size at most $O(n^4)$, and so on.
In particular, P/poly = $\cup_k$ SIZE($n^k$).


Asymptotic Runtime of Interrelated Functions

Here is one approach.  Plug in the definition of $T(n)$ into your first equation, and we get

$$S(n) = 2S(n/4) + S(n/8) + 2T(n/8).$$

Now plug in again and we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4T(n/16).$$

Keep plugging in and eventually we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + 8S(n/64) + \dots + O(1).$$

Now solve that recurrence relation for $S(n)$, noting that now you have a single function (you don't have two interrelated functions any longer).


Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?

This answer assumes that a 2CNF representation of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs.

Let's say that a clause $C$ is consistent with a function $f$ if $\lnot C \Rightarrow \lnot f$. Let $C_1,\ldots,C_m$ be the collection of 2-clauses consistent with your function $f$. Then $f$ has a 2CNF representation if and only if $f = C_1 \lor \cdots \lor C_m$. This gives a quasilinear time algorithm for deciding whether $f$, given as a truth table, has a 2CNF representation.


Are depth-first/breadth-first considered special cases of best-first?

The answer to your question is, in both cases, No.

The reason is as follows: Both depth-first search and breadth-first search are uninformed search algorithms. A distinctive feature of these algorithms is that they stop once the goal node is generated.

Now, if all operators are given the same cost (so that you consider them to have the same cost equal to 1), then:

Breadth-first search is guaranteed to find the solution, and also to deliver an optimal one. This is, it is both complete and admissible (some people refer to this also as been optimal).
Depth-first search, however, is neither complete nor admissible because it is bounded by a maximum depth. It might well happen that the goal lies beyond it and thus, it cannot guarantee to find it.

Best-First search, on the other hand, uses an OPEN list where nodes are sorted in increasing order of $f(n)=g(n)+h(n)$ where: $g(n)$ is the cost of the current path from the start node to node $n$, and $h(n)$ is an estimate of the remaining effort to reach the goal from $n$. As such, $f(n)$ stands for an estimate of the best path from the start node to the goal that goes through node $n$. However, in contrast with the case of uninformed search algorithms, Best-first search algorithms halt only when the solution is about to be expanded! This makes a lot of sense. Under a number of assumptions (such as admissibility of the heuristic function), sorting nodes in ascending order guarantees that the true cost is above the estimation given by $f(n)$, so that only when expanding a goal you can ensure that all the other nodes stand for potential solutions with a cost greater or equal than the cost of the current solution.

Therefore, from your definitions of $f(n)$ (and assuming unit costs):

Making $f(n)=\mathrm{depth}(n)$ would result in an algorithm that expands nodes in the same order than a breadth-first search algorithm (up to tie-breaking). In addition, it will expand more nodes than it since after generating the goal, it has to expand all nodes in the current level before expanding the goal ---in the next level.
Your second choice, $f(n)=\mathrm{depth}(n) + i$, with $i$ been "the number of nodes visited before visiting" is rather confusing to me. I do not know what you might mean by "visited before visiting". In spite of it, however, note that a Best-First search algorithm would proceed further after generating the goal node much the same.

Your question makes a lot of sense. In case you want to access additional material related to it, please refer to Robert C. Holte. Common Misconceptions Concerning Heuristic Search". Symposium on Combinatorial Search SoCS 2010. Pages 46--51. See, specifically, the bottom of the left column in page 49.

Hope this helps,


Sort a list of points to form a non-self-intersecting polygon

Thanks to the advice of Rick Decker, I was able to create an algorithm based on the first half of the Grahm Scan convex hull algorithm, as detailed here.

The first step of the Grahm Scan is to sort the points in a set based on the angle  made with the X axis when drawing a line through the point and the lower-right point of the set. This seems to solve the problem for all point sets that I can think of, with a single addition...

If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

Here is an implementation of the algorithm in JavaScript:

function sortPoints(points) {
    points = points.splice(0);
    var p0 = {};
    p0.y = Math.min.apply(null, points.map(p=>p.y));
    p0.x = Math.max.apply(null, points.filter(p=>p.y == p0.y).map(p=>p.x));
    points.sort((a,b)=>angleCompare(p0, a, b));
    return points;
};

function angleCompare(p0, a, b) {
    var left = isLeft(p0, a, b);
    if (left == 0) return distCompare(p0, a, b);
    return left;
}

function isLeft(p0, a, b) {
    return (a.x-p0.x)*(b.y-p0.y) - (b.x-p0.x)*(a.y-p0.y);
}

function distCompare(p0, a, b) {
    var distA = (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y);
    var distB = (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
    return distA - distB;
}


Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$?

Any oracle relative to which $\mathsf{NP=EXP}$ would do the trick. You can find a construction of such an oracle in Heller's paper. Clearly if $\mathsf{NP=EXP}$ then $\mathsf{NP=coNP=EXP}$ but $\mathsf{P\neq NP}$ by the time hierarchy theorem.

I don't know whether there are known oracle constructions who collapse the hierarchy to $\Sigma_i$ and not to $\Sigma_{i-1}$, but it's an interesting question (I would guess the answer is in the affirmative).


How connected are information theory and algorithmic information theory?

I don't have the background to give a deep answer about how deeply connected the fields are, but Li and Vitanyi's An Introduction to Kolmogorov Complexity and Its Applications--probably the most widely known textbook on AIT--repeatedly incorporates mathematical and conceptual material from information theory (such as Shannon entropy) into its presentation of AIT.  Here is a quotation from the third edition (p. 73) that illustrates a connection that might be considered deep:

  We are interested in a measure of information content of an individual
  finite object, and in the information conveyed about an individual
  finite object by another individual finite object. Here, we want the
  information content of an object x to be an attribute of x alone, and
  not to depend on, for instance, the means chosen to describe this
  information content. Making the natural restriction that the
  description method should be effective, the information content of an
  object should be recursively invariant (Section 1.7) among the
  different description systems. Pursuing this thought leads
  straightforwardly to Kolmogorov complexity.

(Apart from the fact that most of the paragraph clearly seems to be discussing Shannon information, it comes immediately after a paragraph that discusses a quotation by Shannon.)


Finding the subset of $S$ that sums up to $k$ using a black box in $O(n)$ time

Let $S = \{a_1,\ldots,a_n\}$, and denote $S^t$ the set after deciding the fate of $a_t$. If you want to use induction, here is your induction hypothesis:

If there is a subset of $S$ that sums to $k$, then there is a subset of $S^t$ that sums to $k$.
Every subset of $S$ that sums to $k$ includes $S^t \cap \{a_1,\ldots,a_t\}$.


How does recursion works when there are 2 or more consecutive recursive calls?

Just like any other two consecutive statements in an ordinary programming language, they're executed one after the other.

However, since the two recursive calls operate on disjoint sections of the array, you could, in principal, execute them in parallel.


what is a good source for learning how to design a programming language?

This was a bit too long for a comment. And in a way it is an answer.

I fear that if you have to ask that question, you are not yet mature
enough in the field to actually do the job. Furthermore, the kind of
things you need to learn and do depends very much on what the language
is for. If it is for general programming, you have to understand the
various kinds of structural choices that have to be made. The best
source is a general course on programming, not just programming in
one specific language. To understand what is scope (it varies), what
are variables (they come in different brands), what is environment and
binding, to distinguish between functional, imperative or logical
paradigms, and so on.

Designing a language is highly dependent on what you want to say
(program) and how you want to do it. Look for "programming paradigms."

Learn several advanced programming languages (Haskell, CAML or
others), not just what is commonly used by programmers. When you know
enough languages, you will naturally know how you would want to design
one, if you still do.

And of course, you have to learn all the implementation techniques for
theses structures and features. But that you will largely find in
books on compiler and interpreter writing. Maybe you can start with that.

You do not have to do that. But cemeteries are full of programming
languages that no one ever looked at.

Creating a language is a long, long work, with slim chances of success. Make sure it is worth spending a significant part of your life doing it.


Is it possible to have high compression but low predictability?

Yes. A cryptographic stream cipher can generate an incredibly long string  (e.g. ChaCha20 can generate $256 \times 2^{128}$ bits) from a single small key (e.g. 256 bits).

If you do not know the key that was used this stream is impossible to predict.


Chomsky hierarchy type determined by language

No, a finite set of languages does not (usually) characterise infinite classes of languages. So any such specific tests are probably easy to fool.

For CFL in particular, there the Chomsky-Schützenberger characterisation. So if your model can deal with finitely many types of nested parentheses, it's probably at least as powerful as NPDA.

The generic proof technique for showing that one model is more powerful than another is simulation. You can find some examples via simulation and, of course, in the literature.

Proof of the opposite is usually done by counter-example, i.e. a language that can be expressed in one but not the other model.


Sounds like you are reading The Art of Multiprocessor Programming.

  "All function calls have a linearization point at some instant between their invocation and their response"

    Okay that's fine, they occur somewhere within a function call, but what are they?

Side effects of the functions. http://en.wikipedia.org/wiki/Side_effect_(computer_science):

  A function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

In C/C++ side effects are basically writing to memory that is not on the function stack.

  "All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition"

    Occur instantly at their LP's??? I don't understand this.

It means that memory writes become visible to other CPUs in the system at that point. Imagine a function of 100 instructions. Instruction 90 is CAS which is a linearization point. Once the instruction has completed the effects of preceding memory writes become visible to other CPUs instantly (release semantics). This happens some time after the function has been called but before it returned (on instruction 90 of 100).

Note, that memory writes may not always be visible to other CPUs in the system if linearization points are not employed.


Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The  characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $(-1)^n,2^n$. After substituting the initial conditions you get $f(n)=\frac{1}{3}(-1)^n+\frac{2}{3}2^n$.


Why does merge sort run in $O(n^2)$ time?

This is actually a mathematical matter and not the matter of the worst case running time. First you have to know that Big O does not represent worst case running time of some algorithms. Big O comes from mathematics and it represents an asymptotic upper bound for some mathematical functions.

You can see that the graph of $n^2$ is always above the graph of $n\log n$. so you can say $n^2$ is an upper bound on $n\log n$ as the value of $n\log n$ is always less than $n^2$. So mathematically you can say $n\log n=O(n^2)$. Similarly graphs of all $n^i$ for $i\geq 2$ are always above the graph of $n\log n$. So you can say $n\log n$ is also $O(n^3),O(n^4),O(n^5),\ldots$

But one thing you have to remember that though $n\log n$ is $O(n^2)$ but $n\log n$ is not $\Theta(n^2)$, because $n\log n$ is not $\Omega(n^2)$. Mathematically you can say $n\log n$ is $o(n^2)$.

If you still have any confusion regarding my answer, you can ask me here.


Closure under reversal of regular languages: Proof using Automata

You are asking two questions. I will only answer the second one. Recall that $L^* = \bigcup_{n=0}^\infty L^n$. I will show that $(L^k)^R = (L^R)^k$, and then it easily follows that $(L^*)^R = (L^R)^*$.

To show that $(L^k)^R = (L^R)^k$, notice that:
$$
(L^k)^R = \{ (w_1\ldots w_k)^R : w_1,\ldots,w_k \in L \} = \\
\{w_k^R \ldots w_1^R : w_k,\ldots,w_1 \in L \} = \\ \{z_k \ldots z_1 : z_k,\ldots,z_1 \in L^R \} = (L^R)^k.
$$
If you want to be more formal, you can prove this by induction on $k$. The crucial observation is $(xy)^R = y^R x^R$, which you can also prove by induction if you want to be very formal.


Any common problems solvable by DFA/NFA or PDA except recognizing languages?

In imperative programming, state machines are quite common, and they usually look more or less like the following pseudo-code:

state = INITIAL_STATE;

while (token = read_an_input_token(input))
{
   if (state == STATE_1)
   {
      if ([some condition on the token])
      {
         [some actions]
         state = [some state]
      }
      else if ([another condition on the token])
      [etc.]
   }
   else if (state == STATE_2)
   [etc.]
}

if (state != ACCEPTING_STATE)
{
   [error handling, perhaps abort]
}
else
{
   [apply finishing touches]
}

All kinds of variations may occur: you'll see case statements being used in languages that have them, the order in which the conditions are tested and the way they are grouped may vary, more input scanning may occur than just reading separate tokens, et cetera.

You're likely to see similar loops wherever a regular language needs to be parsed. For instance, command line utilities usually parse their arguments in this way. (Mine do, anyway.)

There are other approaches to using state machines in software; I think this is the most popular and most informal one.


Edge Constraint satisfaction in a Directed Graph Path?

Assume first that the $x_i$ can take any arbitrary values. Then the constraint $A_i + B_i x_i = V$ just states that $V \equiv A_i \pmod{B_i}$. Two such constraints are contradictory if $A_i\not\equiv A_j \pmod{(B_i,B_j)}$, where $(B_i,B_j)$ is the GCD of $B_i$ and $B_j$. The Chinese Remainder Theorem should show (after some work) that any set of constraints in which no two are contradictory can be simultaneously satisfied. (Prove or refute!)

The constraint that $x_i \geq 0$ doesn't actually impose any further constraints. Indeed, take a solution $V$ to the original problem. By adding to $V$ a large enough multiply of $\prod_i B_i$, we obtain another solution in which all $x_i$ are non-negative.

This reduces your problem to the following problem:

  Given a directed graph and a set of forbidden pairs of edges, does there exist a path from $s$ to $t$ that doesn't contain a forbidden pair of edges?

Unfortunately, this problem is NP-complete, by reduction from SAT. Given $m$ clauses $\varphi_1,\ldots,\varphi_m$, there will be $m+1$ vertices $v_0,\ldots,v_m$. For each literal $\ell \in \varphi_i$, there is a corresponding edge from $v_{i-1}$ to $v_i$. Two complementary literals form a forbidden pair. A legal path from $v_0$ to $v_m$ exists iff the instance is satisfiable.

There are now two options:

Either your particular instance has more structure, which you can employ to get a more efficient solution;
Or your original problem is also NP-hard.


Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

Hint: to express "the set $S$ has size $\ge 1$" in propositional logic (without using the "size" operator), you can write $\exists x . x \in S$.  How would you express "the set $S$ has size $\ge 2$"?  Does that give you any ideas for how to use relational algebra to solve your question?


Is there a way a proving a language regular/non-regular that works for every possible language?

No, there isn't. It is undecidable, even for context-free languages. It is decidable for deterministic context-free languages.

References are easy to find with Google; for instance,

Undecidable Problems for Context-free Grammars, by Hendrik Jan Hoogeboom
Deciding whether a context-free language is regular [closed], on the Theoretical Computer Science Stack Exchange, in which user babou lists

A regularity test for pushdown machines,  R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. Valiant, JACM 1975


Is this the correct "standard form" of nonlinear programming (optimization) problem and if it is why it's in this form?

There is no "standard form" that you must use. You don't have to write an optimization problem in that way. This is a useful representation in a number of ways; it is very general; and it facilitates some kinds of analysis (e.g., KKT conditions).  But there are no police forcing you to express your optimization problem in this way; you can use whatever you find most useful.

Note that every optimization problem can be expressed in this way, as $h(x)=0$ can express arbitrary constraints on $x$ and $f(x)$ can express an objective function.  So, it is nice from this perspective.


Homework?

See the problem "Cutting Wood", which involves cutting rather than glueing, but is otherwise equivalent. Provided the orders matters (as noted by Marzio).

  Your favorite sawmill charges by length to cut each board of lumber.
  For example, to make one cut anywhere on an 8 ft. board of lumber costs \$8.
  The cost of cutting a single board of wood into
  smaller boards will depend on the order of the cuts.
  As input, you are given a board of length $n$ marked with $k$ locations to cut

solution to exercise (pdf) Found in several places on the web, don't know the original.


Finding constrained random time intervals with a constrain also on their sum

Let’s consider general parameters $n$, $\min$, $\max$, with $0<\min<\max$ and $tot=1$ (you can transform your problem to this form simply by considering 15 minutes as the measure unit for time). What you are trying to do is to sample from the intersection of the following two set:

the set $S=\left\{(x_i)_{i=1}^{n}|\Sigma_{i=1}^{n}x_i=tot=1\right\}$, the canonical n-dimensional simplex, and
the set $C=\left\{(x_i)_{i=1}^{n}|\forall i\, x_i \in [\min,\max]\right\}=[\min,\max]^n$ which is a n-dimensional hypercube in the first octant.

To see the shape of this set let’s fix $n=3$, so we now are in a $3$-dimensional space and the hypercube is an actual cube. The cube depends on the parameters $\min$ and $\max$. If you keep the radius $R=\frac{\min-\max}{2}$ constant and change the mid-point $m=\frac{\min +\max}{2}$ of the interval $[\min,\max]$ you are translating the cube with direction $\left(1,1,1\right)$. Instead if you change radius $R$ but keep the mid-point $m$ constant you get are expansion (the edge of) the cube.

The intersection of the simplex and the cube is a hexagon, whose regularity depends on the value of $R$. Moreover, it may happen that the hexagon collapses to a triangle, or to a point or to the emptyset (in these two cases you can sample only one point or none at all, so the problem is trivially solved). So, if we know how to compute the vertices of the hexagon, the problem reduces to a sampling from a hexagon.

To compute the vertices notice that they lie only on those edges of the cube such that one end-point lies “above” the simplex and the other “below”. So you could search all the couple of adjacent vertices of the cube such that one end-point satisfy the constraint $x+y+z\geq1$ and the other satisfy the constraint $x+y+z\leq1$. For all these couples $\left(e_1,e_2\right)$ you can parametrize the segment $e_1e_2$ in the form $Le_1+(1-L)e_2$ for all $L$ in $\left[0,1\right]$ and then find that particular $L$ such that the point on the segment lies on the simplex, i.e. find L such that $x_L +y_L + z_L=1$ where $(x_L,y_L,z_L)= Le_1+(1-L)e_2$.

Once you have computed the six vertices of the hexagon you should be able to decide if it is really a hexagon -if all vertices are distinct- or a triangle -if there are only three distinct vertices- or something trivial.

To sample from a triangle you can, for example, find a transformation $\varphi$ from the canonical simplex to the triangle, sample from the simplex (for example as in cs.stackexchange.com/q/3227/755 as suggested by D.W.) and then transform the sample using $\varphi$. To ensure uniformity you should sample uniformly in the simplex and normalize $\varphi$ with the norm of the determinant $d$ of its jacobian matrix (when $d\neq 0$), i.e. use the transformation $\psi =\begin{cases}\varphi & \text{if }  d=0\\\frac{\varphi}{d} &\text{if } d\neq 0   \end{cases}$.

To sample from a hexagon you can divide the hexagon in six triangles drawing the edges from the vertices to an inner point of the hexagon (for example $\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$; infact, this point is a possible sample if and only if there is at least one sample), choose randomly one of them, and then sample from that triangle. In this case to get uniformity, on top of sampling uniformly from triangles, you should choose the triangles using a probability distribution $\left(p_i\right)_1^6$ of the form $p_i =\frac{\text{area of the }i\text{-th triangle}}{\text{area of the hexagon}}$ (with this choiche you cover also the case of a collapsed hexagon). However, I suppose there are much more refined methods to sample from a triangle or from a hexagon.

Generalizing to grater values of $n$, instead of a hexagon divided in six triangles, you should get a $n-1$ dimensional convex surface whose vertices can be computed as above. This surface can be divided in some $n-1$ dimensional simplicial polytopes. So you select randomly one of these polytopes accordingly to their volume, find a transformation from the $n-1$ canonical simplex to this polytope and use it to transform a sample from the $n-1$ dimensional simplex.


Why can't we sort an Array in O(n) using Fibonacci Heap?

Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.

Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?


Removing left recursion with terminals only

You'll need to introduce a new non-terminal to factor this, like:
$\begin{align*}
   G &\to id A \\
   A &\to < id \mid > id
\end{align*}$
Then you'll need to get rid of the left recursion.


This is A053632. The prefixes of this sequence convergence to the more well-known A000009, the number of partitions into distinct (or odd) parts. You shouldn't expect a clean formula, though it's of course easy to calculate small terms using dynamic programming.


Decide whether there exists a walk of weight exactly k

We start by converting your graph into an NFA $A$, by replacing the weights with strings. Positive weights $k > 0$ are replaced by $a^k$, negative weights $k < 0$ are replaced by $b^{-k}$, and zero weights are replaced by $\epsilon$ (the empty string). We make $v_1$ the initial state and $v_2$ the only accepting state. Consider now the context-free language $L_k = \{ w : \#_a(w) - \#_b(w) = k \}$. We construct a context-free grammar for $L_k \cap A$ and check whether $L_k \cap A = \emptyset$.

The size of the generated NFA is polynomial in $n + \sum_{ij} |w_{ij}|$ where $n$ is the number of vertices and $w_{ij}$ are the weights. The size of a grammar for $L_k$ is polynomial in $k$. In order to intersect it with $A$, we convert it to a PDA, use the product construction, and then convert back. We get a CFG of size polynomial in $n + \sum_{ij} |w_{ij}| + k$. Checking emptyness takes polynomial time, so the entire algorithm takes time polynomial in $n + \sum_{ij} |w_{ij}| + k$, showing that the problem is in NP if the weights and the target sum are encoded in unary (otherwise the bound we get is only NEXP).

Interestingly, this argument doesn't work for real weights. The natural extension would be to find a basis for the weights over $\mathbb{Q}$, clear off the denominators, and have a pair of symbols $(a_i,b_i)$ for each element in the basis. The argument fails since $L_{\mathbf{k}} = \{ w : \forall i \#_{a_i}(w) - \#_{b_i}(w) = k_i \}$ is not context-free if there is more than one pair of symbols.

  Is the problem with real weights (given as linear combinations over $\mathbb{Q}$ of some $\mathbb{Q}$-linearly independent set) decidable?


distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete

First they are different kind of problems. One is a class of decision problems, the other one is a class of function problems. So lets interpret the question as $\mathsf{FP^{\#P}}$ vs. $\mathsf{\#P\text{-}complete}$.

Second, the kind of reductions used for completeness are not simple polynomial time Turing reductions, see the definition of #P-complete.

A polynomial time TM with access to a $\mathsf{\#P}$ problem might be able to do things that a $\mathsf{\#P}$ machine cannot do. For example, it can check if a $\Sigma^p_2$ formula is satisfiable and output $1$ if it is and $0$ if it is not.


Add on interval, Query for number of elements less than val

Decompose the array to blocks of size $T = \sqrt{n \cdot log(n)}$ and Store the sorted corresponding subarray in each block. For each block $k$ store variable $bound[k]$ which is the number added to the whole subarray of the block. For the second query iterate over blocks and use binary search over $x - bound[k]$ on $k$th block. Time complexity would be $O(\frac n T log(T)) = O(\frac{n \cdot log(n)}{\sqrt{n \cdot log(n)}}) = O(\sqrt{n \cdot log(n)})$.

For updating queries, for each block $k$ that it's subarray is completely in the interval [ L, R ] update $bound[k]$ to $bound[k] + x$. Now we have at most two blocks which are modified but their subarray are not completely in the query interval. Iterate over the modified elements and update them by $x$. Now in each of those blocks you have two sorted arrays (modified and unmodified elements) and you are trying to merge them into one. This can be done in linear time, so rebuilding those two blocks takes $O(T)$. This way time complexity of each update query would be $O(\frac n T + T) = O(\sqrt{n \cdot log(n)})$.

Total complexity: $O((n + q)\sqrt{n\cdot log(n)})$.


Why do TPTP Performance plots look like this?

I can speculate/hypothesize.  Each solver has many heuristics and proof tactics.  Imagine that corresponding to each heuristic is a class of instances that are easy to solve if you use that heuristic, but hard if you don't (e.g., if you don't have a heuristic for it and you fall back to the generic methods, maybe you're effectively exploring the entire exponentially large space of possible solutions to try to find one that works).  An example would be 2SAT; if you use the right algorithm, it can be solved in linear time, but if you blindly search, that will take exponential time.

So, in this model, if an instance is handled by one of the prover's heuristics, it is solved very rapidly; otherwise you fall back to some generic method that may take exponential time.  This would lead to a kind of "very fast or very slow" dichotomy.  And the set of instances that a prover is fast on may be different for each prover, because prover uses a different set of heuristics.  In other words, this hypothesis would explain the observed behavior.

I have no data and no hard evidence, so this is merely speculation.  It could be entirely wrong.


Does 2-edge-colourability imply 2-colourability?

Hint: Consider a cycle in your graph. The edge colors must alternate, so the cycle must have even length. A graph is bipartite iff it has no odd cycles.


How does an admissible heuristic ensure an optimal solution?

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal.

Look at this simple example.

Let $A$ and $G$ be respectively the starting and goal nodes. Let $h(N)$ be an estimate of the path's length from node $N$ to $G$, $\forall N$ in the graph. Moreover, let $c(N, X_{i})$ be the step cost function from node $N$ to its neighbour $X_i$, $\forall N$ and $i=1..m$, where $m$ is the number of neighbours of $N$ (i.e., a function that returns the cost of the edge between node $N$ and one of its neighbours).

Let the heuristics be

$h(B) = 3$
$h(C) = 4$

This heuristics function $H$ is not admissible, because $$h(C) = 4 > c(C, G) = 2$$

If the $A^*$ algorithm starts initially from node $A$, it will select next node $B$ for expansion and, after this, it will reach node $G$ from there.
And the path will be  $A \rightarrow B \rightarrow G$ with cost $4$, instead of $A \rightarrow C \rightarrow G$  with cost $3$. If the heuristic function was admissible this would not have happened.


if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

Your question isn't entirely clear, but it seems you're asking if every false graph property has a counterexample. Obviously this is true: by definition there must be some graph for which the property doesn't hold. On the other hand, a proof that the property doesn't hold for all graphs may not necessarily give an example of such a graph; this is called a non-constructive proof.


I can think of two approaches. Each generates a single sample at a time; any modifications to the graph are undone before generating the next sample.

Compute the shortest path, then remove r of the edges you take and generate the next-shorted path. This can be used to generate nCr samples, though many will coincide. For better quality, you probably want to also apply this to its own output: find the initial shortest path, remove 2 edges, find the intermediate shortest path, remove 2 edges, find the final shortest path. For a reasonably large graph, I would just calculate the edge(s) to remove at random in each step. Variant: instead of removing a single edge, remove both that edge and all other edges that go in/out of either vertex (I would consider the graph undirected for this step).
Randomize the weights as you pass them to A*. That is, when you advance from one node to the next, multiply that edge's weight by a number between 0.9 and 1.1 (probably with a Gaussian distribution actually). On rare occasions this might generate loops, especially if you widen the random range.


For your specific problem, I propose a regular expression in a ad-hoc meth, and the outcome was: (notation comes from Regular Expressions)

  (a*(b(b+)?ab?)?)*

I found it with the next methodology: moving from simple to more complex ( states to final states)

To arrive to $q_3$, you need to put a
This a comes from $q_1$ or $q_2$
If it comes from $q_1$, use a b else it comes from $q_2$, so use one o more b's: b+
But, $q_2$ comes from b too, so union these two possibilities, a comes from b((b+)?)
For that, we have b(b+)?a in regular expression to go from $q_1$ to $q_3$
Now, If you want to move from $q_3$ to $q_0$, you need a extra b, so use b?. This is the part of regular expression: b(b+)?ab?
To start you probably have empty string, or a's or b to go from $q_0$ to $q_1$
Above can achieve with a* and visit $q1$ or not visit is express like: a*(b(b+)?ab?)?
Finally, you could have a nothing of that, or more than once this strings, so you should use *, and take as regular expression: (a*(b(b+)?ab?)?)*

Test Cases

I tested with the next strings and all match with the regex:

aaaaba
aababaaaaaa
abbbbbba
abbbbbbab
abbbbbbabaaaa
abbbbbbaba
bab
ba
babaaaa
aaaaa
bbba

In the other hand, you may be interested in consider algorithms to converting DFA to Regular expression, so you can find a dynamic programing algorithm, and the full description of this approach is given in the book of Models of Computation, Chapter 4. And other method, Brzozowski algebraic method. All above, because with the powerset constructive you can obtain a DFA from NFA.


'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges

It is known that regular languages are closed under homomorphisms. In particular, if $L$ were regular than so would $h(L) = \{b^nc^n : n \geq 0\}$ be, where $h$ is the homomorphism given by $h(a) = \epsilon$, $h(b) = b$, $h(c) = c$. Since $h(L)$ is not regular, so is $L$ non-regular.

More generally, you can use proof by contradiction together with operations under which regular languages are closed. The idea is to start with your language, perform a bunch of operations, and end up with a non-regular language. If all operations you used preserve regularity, then you can conclude that the original language is not regular.


existence of a permutation that satisfies order-constraints

Yes.  That task is called topological sorting.


How big is the capacity of a standard memory cell that the pointer is linking to?

That depends on the underlying architecture. Most machines today use byte addresses, but machines that addressed words (i.e. 16, 18, 32, even 36 bits) were reasonably common. If I recall correctly, most RISC machines were unable to address anything but words (but gave addresses in bytes). At least, such an address caused the CPU to fetch both words and snip out and assemble the piece wanted.

What your favorite language does above the machine's intrincacies, ask them. Often they will refuse to handle pointers that aren't aligned at some "machine natural boundary", like the size of a C double, 8 bytes. Even on machines that have no penalty attached to non-aligned address acces.


${\rm D{\small OMINOSA}}$ is NP-hard

Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is:

  Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

Obviously, the optimization problem, the problem of actually finding a solution to the game is at least as hard, or harder, than the decision problem.

We will convert a $1\text{-}3\text{-in-}{\rm S{\small AT}}$ formula to a corresponding grid, that will only be coverable iff there is a satisfiable assignment to the formula. Furthermore, the covering can actually be used to recover the satisfying assignment.

Therefore, if the construction presented is correct, and one could solve a game in polynomial time on a DTM, then it would imply ${\rm P=NP}$. This implies ${\rm D {\small OMINOSA}}$ is NP-hard.

Reduction from $1\text{-}3\text{-in-}{\rm S{\small AT}}$ to ${\rm D {\small OMINOSA}}$

Introduction

Most of the $3\text{-}{\rm S{\small AT}}$ problems/variants have a pretty good correspondence to ${\rm C{\small IRCUIT}S{\small AT}}$. It can be important to think of the problems in parallel; as they are related to each-other, almost anything in one problem can be related to in the other.

${\rm C{\small IRCUIT}S{\small AT}}$ has a planar variant, to which it reduces, called ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$. This conversion is very elegant, and basically allows you to take any planar embedding, find the remaining crossing wires, and use a "gadget" to let the wires cross via a planar "gate" (collection of gadgets, with input and output wires).

Conveniently, most of the $3\text{-}{\rm S{\small AT}}$ variants also have reductions to planar variants, which parallel ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, and are very related; easily reducible from one to another, and easy to reason about. So whenever I come to a planar problem that might be NP-hard, I think in terms of the planar variants of $3\text{-}{\rm S{\small AT}}$, and their parallels in ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$.

The planar variants are important to know, because they make help make reductions to planar/geometric problems, like Euclidean TSP (incidentally a pretty rare reduction to find and learn). Thus, there is ${\rm P{\small LANAR}}\text{-}3\text{-}{\rm S{\small AT}}$, and a parellel, ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$, to aid in such reductions.

Other $3\text{-}{\rm S{\small AT}}$ variants are important to know because some of them are weaker; that is, seemingly "easier", yet still NP-complete. They seem easier to solve at first glance - and they are much simpler - yet are still NP-complete. NP-complete, but simpler; and therefore easier to make reductions to, in many cases.

For example, there is $1\text{-in-}3\text{-}{\rm S{\small AT}}$. For some problems, you can easily make an exactly $1\text{-in-}3$ gadget, while making "at least 1 in 3", like the standard $3\text{-}{\rm S{\small AT}}$ uses, would be non-obvious and make for huge constructions.

Another example is ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$. Monotone makes things a lot simpler when you have a construction that can't easily negate values.

Even more amazing is that ${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ has a planar variant: ${\rm P{\small LANAR}}\text{-}{\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$! So this makes things a lot easier; you don't have to cross "wires" (remember, there are parallels in ${\rm C{\small IRCUIT}S{\small AT}}$ to these), and trust me, while crossing gadgets are fun to make, they tend to be very non-obvious and difficult.

$$
\begin{array}{c|c|c|ccc}
&&&&\hspace{1em}&\hline\\
{\rm\mathbf{P{\small ROBLEM}}}
  &\scriptsize{{\rm\mathbf{MONOTONE}}}
  &\scriptsize{{\rm\mathbf{PLANAR}}}
  &\scriptsize{{\rm\mathbf{1\text{-in-}3}}}
  &&{\rm\mathbf{NP\text{-}hard}}
  \\
\hline\\
{\rm\mathbf{3\text{-} S{\small AT}}}
  & \text{No} & \text{No} & \text{No}
  && \text{Yes}\\
\hline\\
{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}
  & \text{Yes} & \text{No} & \text{No}
  && {\text{No}}^1\\
{\rm\mathbf{P{\small LANAR}\text{-}3\text{-} S{\small AT}}}
  & \text{No} & \text{Yes} & \text{No}
  && {\text{Yes}}^2\\
{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}
  & \text{No} & \text{No} & \text{Yes}
  &&
          {\text{Yes}}^3\\
\hline\\
\genfrac{}{}{0}{1}
  {\rm\mathbf{P{\small LANAR}}}
  {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}
  & \text{No} & \text{Yes} & \text{Yes}
  &&
          {\text{Yes}}^4\\\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{M{\small ONOTONE}\text{-} }}}
  {{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}}
  & \text{Yes} & \text{No} & \text{Yes}
  &&
          {\text{Yes}}^5\\\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{P{\small LANAR}\text{-}}}}
  {{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}}
  & \text{Yes} & \text{Yes} & \text{No}
  && {\text{Yes!}}^6\\
\hline\\
\genfrac{}{}{0}{1}
  {{\rm\mathbf{P{\small LANAR}\text{-}M{\small ONOTONE}\text{-} }}}
  {{\rm\mathbf{1\text{-in-}3\text{-}S{\small AT}}}}
  & \text{Yes} & \text{Yes} & \text{Yes} && {\text{Yes}}^7\\
\end{array}
$$

Pure literal elimination
Schaefer's dichotomy theorem
The Problem of Compatible Representatives
Minimum Weight Triangulation is NP-Hard
Schaefer's dichotomy theorem
Finding Perfect Auto-Partitions is NP-hard
Optimal Binary Space Partitions in the Plane

One way to start with a reduction, is to try to find "gadgets" that resemble wires, and a gadget that resembles a clause of one of the $3\text{-}{\rm S{\small AT}}$ variants. As a bonus, many of the variants are planar, we can probably get away without crossing wires.

What is a "gadget"? A gadget is some construction in the problem, that is helpful as a building block to build gates/wires/clauses. Some gadgets will have a restricted set of states; for example, a gadget with two states can be used as a variable; one state is "true" and the other is "false". A gadget with two states, that can be "long", can bend, and split, is useful as a wire - if it can interact with a variable, and become constrained to extend the state of the variable to another location. A gadget with exactly three states can perhaps be used as a clause; if it can be used to constrain "one of three" wires via each one of its three states. Similarly, one might want all sorts of logic gates, like a not-gadget, an or-gadget, an xor-gadget etc; where you can have some sort of constraint via the gadget that relates 2 or 3 wires in such a way.

A Building-block

First, let's reserve a number, for example, $\mathbf 1$, on the board. We will make $\mathbf 1$ a building block for everything else.
We will use a corner to make sure that $\mathbf 1$ can never connect to another $\mathbf 1$, except in this corner, where it must.
Below (in the three figures) is the corner, and how we place the $\mathbf 1$s there.
We will use the $\star$ to indicate unique values in all the grid, in all the diagrams.
In fact, we will cover our grid with $\star$ values before overlaying them with important values; therefore, by default cover everything with $\star$ values.

As you can see, by placing the $3$   $\mathbf{1}$s the pair $\mathbf{(1,1)}$ must be used up in this configuration; it must use one of the dashed-tiles. Now $\mathbf{(1,1)}$ can never happen elsewhere in the board, which is what we need.

There are alternate ways of reserving a number, either against the wall with $4$ of them, or in the middle of nowhere, with $5$ of them in a cross. Any way is fine, as long as $\mathbf{(1,1)}$ is forced.

A Wall

Now, it would be very useful to be able to make "walls" and "corners" all over the place, not just at the sides of the grid. Look what happens if we line up pairs of ones in a line; the one's have no choice but to pair with their neighbors, making a "wall" of width $4$.

Images below, from left to right:

A line of pairs of $\mathbf 1$s.
The only possible tiling of that $\mathbf 1$-square.
The only possible tiling of (almost) all the $\mathbf 1$s in the line.
The wall line, drawn for emphasis.

An initial attempt at a wire

Now, by placing two "walls" opposite each-other, and leaving a space of $\mathbf 1$ between the walls, perhaps we can come up with a "wire"-like gadget.

Showing only the wall-borders, this is what we get in the figures below (left to right):

Placing two walls opposite each-other.
Putting unique numbers inside.
Rightmost two: Two possible states of the wire.

How it works:

  There cannot be any holes in the tube/wire, therefore, if the the tiles are shifted up, then they all must be shifted up, all along the tube; if they are shifted down, it will "suck" down all of them. Thus, we can send a "signal" from one side of the wire to the other; in other words, propagate a value.

Thus, now we can propagate a value across long distances!

Remaining limitations are:

We cannot bend a wire,
We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Bending a Wire, Part 1: Wall Below

Next problem is, we need to be able to bend a wire, not just go straight ...

So. We will break the bending part down into two parts; the upper part and the lower part. First the lower part. Ignore the upper part of the bend, we will do that later.

The figures below show a bit of a problem with bending; the top of the wire is "loose", it seems difficult to make a wall that turns a sharp 90 degrees.

Left to right:

The top of a wire is "loose".
What happens if we try to bend it; we want to wire to be in between the blue lines. Again, Ignore the upper part of the bend, we will do that later.
As you can see, the top $\mathbf 1$s are loose, they can tile along the wall, or through the wire! This is no good.

One solution is as follows:

Pick a $\mathbf{(x,1)}$ pair near the bend. Take the value of that $\mathbf x$ square, let us name it $\mathbf{ q \star}$; this means the number is unique in the entire grid, just like $\mathbf \star$, and is reused once, here in this bend only. Because this $\mathbf x$ is paired with a $\mathbf 1$, it cannot be paired with a $\mathbf 1$ again. Therefore, we place it right on top of the rightmost-topmost $\mathbf 1$. Now, we can clearly see, the only option remaining to pair for that $\mathbf 1$ is to its right, and thus it will solidify the wall.

Illustration below, description from left to right:

The situation with the problem.
Pick a square, let $\mathbf{q \star}$ be the square value of any square in the bend (of course not $\mathbf 1$s though).
The two togglings of the rightmost-topmost $\mathbf 1$ tilings; this time, only one of them is valid.

However, how can we be sure this $\mathbf {{q}{\star}}$ won't ruin the wire? Below you can see the states of the wire, and that the $\mathbf {{q}{\star}}$ will not hamper with it.

From left to right:

The current construction.
Two rightmost figures: The states of the wire; empirically, they are not hampered by the introduction of $\mathbf {{q}{\star}}$.

Now we still have a loose $\mathbf 1$ on top; the leftmost-topmost-$\mathbf 1$.

We will do the same thing; pick a pair $\mathbf{({r}{\star},1)}$ that is already paired in the bend-tiles, and place $\mathbf{r}{\star}$ on top of the leftmost-topmost-$\mathbf 1$.

Illustration below, left to right:

Our current construction.
The problem: leftmost-topmost-$\mathbf 1$ can pair with a number in the wire, or with the wall; we want it to only pair with the wall.
Choosing an $\mathbf{r}{\star}$, and using the same number on top of the leftmost-topmost-$\mathbf 1$.

And we finally get our lower bend. Illustration below, descriptions, from left to right:

Left: Our final construction for a bend.
Right: How to continue the wire to the left.

Bending a Wire, Part 2: Wall Above

The walls to make the top corner of the bend are much simpler. You simple align a vertical wall with a horizontal wall. Illustration below, description from left to right:

The wire-bend we want to make.
Place the vertical section of the wall squares down.
Tiling the  squares of the vertical-wall.
Placement and tiling of the horizontal wall; it can meet the vertical wall, and form a corner.

Now you should be convinced that we can place and bend wires. We still can't split or cross wires though, more on that later.

Remaining limitations are:

We cannot bend a wire,
We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

A Valued Wire

Now we have wires, it would be nice to have a valued-wire, where we can see the value of a wire, like an LED on a circuit board. So what we do, is take a wire, say of length $7$, and introduced a named $\star$ square, we'll call it ${\mathcal T}{\star}$, and another named square, we'll call it ${\mathcal F}{\star}$. These are both unique to each valued wire section, ie. only twice, and they will only get reused within a single valued wire. They are placed in pairs, the two ${\mathcal T}{\star}$ squares right next to each-other, and the two ${\mathcal F}{\star}$ squares next to each-other, with a single $\star$ square separating them. Illustrated below, description from left to right:

Left: A wire.
Right: The square-configuration.

So how do we tell if a wire is true or false? Well, a wire has two states. In each of these states, one of ${\mathcal T}{\star}$ or ${\mathcal F}{\star}$ will be paired in the same tile; the value that is paired is the value of the wire. Illustration below, desciption from left to right:

Left, right: The two states of the valued wire;
Left: Wire is valued trued, as the ${\mathcal T}{\star}$ squares share a single tile
Right: Wire is valued false as the ${\mathcal F}{\star}$ squares share a single tile.

We can now have named variable that we can use, to place our ${\rm 3\text{-}S{\small AT}}$ variables down on the grid. We can connect two valued wires and force them to have the same value, or if we connect them with an odd-length, force them to have different values; and using wires, we can do this long-distance, across the grid. Using wires, we can propagate the values of the named variables all over the place.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Not-gate

A not-gate is unnecessary as it is implicit: simply using an off-by-one wire length we can negate the value of the wire.

A Clause Gate

Now I can demonstrate a simple clause gadget; it will connect to $3$ wires, and force one of them to be "pulled" state, and force the other two to be in the "pushed" state. We can use this, this is an exactly one-in-three relationship; we set the odd-wire-state to mean "true", and the other two wire-states to mean "false", and we are set.

Illustrations below, descriptions from left to right:

The wire-layout of the clause gadget. It makes a "plus" sign; the joining of 3 wires in one spot.
Fill the wire with unique $\star$ squares.
The three states of the center square. Each of these states "pulls" exactly one wire into the center, the essential point of the gate; to act like a ${\rm 1\text{-in-}3\text{-}S{\small AT}}$ clause.

Now let's take a look at the different states. Illustration below, description from left to right:

The left wire is pulled into the center; the other two are pushed out.
The bottom wire is pulled into the center; the other two are pushed out.
The bottom-right wire is pulled into the center; the other two are pushed out.

Now, if you attach wires with the right length-parity (even or odd length) to the end of this gate, only one of them could be true, the other two false (depending if you attach them oddly, you can generalize this a bit). Thus we can connect $3$ values into a $1\text{-in-}3$ CNF clause.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

Splitting a Wire

To split a wire, we first line up two wires next to each-other. Next, as a visual aid, we label each of the wires with two ${\mathcal T}{\star}$ squares, one next to the other. This will allow us to see when the wire is "true": when the two ${\mathcal T}{\star}$ squares of a wire in a single tile, then it will be true, otherwise false. Each wire should get its own pair of ${\mathcal T}{\star}$ pairs, so we'll name one pair ${\mathcal T}_1{\star}$ and the other ${\mathcal T_2}{\star}$. Then we introduce three new named-unique $\star$ values, $a{\star},b{\star},c{\star}$. We will place these three next to each-other, once on each wire. However, on one wire, keep a single $\star$ squares between the $a{\star},b{\star},c{\star}$ squares and the ${\mathcal T}{\star}$ pair. On the other wire, put two $\star$ squares between the $a{\star},b{\star},c{\star}$ squares.

Illustration below, description from left to right:

Wire layout. Note the walls are a bit thick, so the wires are drawn closer together for illustration purposes; in reality, they are a bit farther apart.
The square-values; the ${\mathcal T}{\star}$ values on top, and the split-connectors $a{\star},b{\star},c{\star}$ beneath.

What this does is force the wires not to be different; if $a{\star},b{\star}$ is tiled on one wire, then the second wire cannot be off-by-one, because then that would imply $a{\star},b{\star}$ is tiled on the second wire, and thus $a{\star},b{\star}$ would be tiled twice. Illustration below, description from left to right:

Example state of the left wire, valued as true.
Bad state of the second wire; it tries to be differently valued, but then it gets a duplicate pair.
Good state of the second wire, now they are the same value, and there are no duplicate pairs.

If you play around with the other two possible states, you will see this extends to those as well, and it works both ways. Thus these two wires are now the same; we have successfully split a wire. We can split the wire as many times as we like, each time using a new set of $a{\star},b{\star},c{\star}$.

Remaining limitations are:

We cannot split a wire,
We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

A Cordless Wire!

Well, to my delight, splitting a wire turned out to be cordless! That is, in the illustrations above, I lay the wires next to each-other, but there is no reason to! We can place the wires anywhere on the grid, and they'd still be "entangled" so-to-speak. This saves us a lot of trouble:

We don't even have to worry about crossing wires. This lets us reduce from non-planar variants of ${\rm\mathbf{3\text{-} S{\small AT}}}$
We have to do any annoying layout, getting the wires to their locations, it is easy! Like a cordless phone! Freedom!
We don't have to worry about wire-length parity/off-by-one layout.
We can make pretty minimally sized reduction; the variables will each get a single set of long wire strips, with a lot of cordless connections along the wires. These connections will be to clause-gates, which will reside in its own location on the grid. The clause will now only consist of the clause gadget and three cordless wires sticking out of it.

Remaining limitations are:

We cannot cross wires,
We might have annoying layout issues because we must be careful about wire-length parity.

The Reduction, first attempt

Let $\Phi(\mathbf x)= \bigwedge_i C_i$ be a $1\text{-in-}3\text{-}{\rm S{\small AT}}$ boolean formula.

For each $x_j \in \mathbf x$, lay-out a single long wire, in rows, near the bottom of the grid.
For each $C_i \in \Phi(\mathbf x)$, make a clause-gate at the top of the grid; you can lay them out however you like; best fill it up in a square area, but you can lay it out in a single long row as well.
For each $x_j$ variable participating in a clause $C_i$, place a cordless-wire at one of the $3$ wire-pins of the clause gate; place the other $a{\star},b{\star},c{\star}$ of each connection onto the corresponding variable wire/row. Negated terms should just place the cordless connection to the clause a distance of one farther away, changing the wire-length-parity, and negating the value.

What it might look like:

Figure: A clause, directly connected to cordless wires. "Hotspots" are the way we symbolize the $a{\star},b{\star},c{\star}$ from here on. These hotpots will each be connected to the variables in the grid.

And here is what the grid might look like:

Figure: The resulting game-board. The variables are lined up in rows on the bottom. The clauses are spread out across the top. This layout gives quadratic blowup; a smarter layout can avoid quadratic blowup.

Last Minute Details

Recall the decision problem:

  Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles?

So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But our reduction requires a lot of unique variables, much more than $\mathcal O(n)$. There are several ways to solve this issue.

One way, is to square the size of the grid in both axes. So now our $\mathcal O\left(|\mathbf x|\times \left|\Phi(\mathbf x)\right|\right)$ grid is merely $\in \mathcal O\left(n\right)$, which means all of our unique numbers can be bounded by $n$. Then, we must fill up the rest of the grid, reusing our unique numbers, but being very careful not to place any numbers that our adjacent to each-other in our grid, adjacent to each-other in the filler-space of the rest of the grid. There are several creative ways to do this, I'll leave that as an exercise. This method induces an additional quadratic blowup, obviously.
Another, more succinct, more complex way, is to diversify the $\mathbf 1$ block. Instead of just one building block, we can use $\mathcal O(n)$ building blocks, and then we can reuse the numbers they pair with. This method allows us to avoid quadtratic blowup.

Graph sources

Dominosa.Part.I.tex (writelatex)
Dominosa.Part.II.tex (writelatex)
Dominosa.Part.III.tex (writelatex)
Dominosa.Part.IV.tex (writelatex)


Are there graphs for which A* cannot be admissible?

The heuristic function $h:V \longrightarrow \mathbb{R}_{\geq 0}$ is *an input to the $A^*$ algorithm. If the function is admissible then $A^*$ algorithm gives you the solution; however as you have noted for infinite graphs the edge weights must have a positive lower bound.

The point of the heuristic function is to find the shortest path in the least amount of time, i.e. lower the computational complexity; because you are making informed decisions based on a heuristic (hence the name).

Recall the heuristic function is admissible if $h(v)$ is always less than (or equal to) the true path cost to the goal node.

There is always an admissable $h$ namely $h(v)= 0$ for all $v$. In this extreme case it becomes Dijkstra's algorithm.

Returning to the example you gave if you plug in the input $A^*(G,h)$ where $G$ is a description of $G$ and $h = 0$ then $A^*$ won't halt (geometric series $r = 2 \implies \sum_i r^i = \frac{1-r^{n+1}}{1-r} \leq 2$ for all finite partial sums). But lets see if we can bypass that; lets try: \begin{equation} h(v) = \begin{cases} 3 & \text{if } v = q_1 \\ 0 & \text{else}\end{cases} \end{equation} as you can see $h$ is admissible (because $d(q_1 , \text{goal}) = 3$ on the nose) and $A^*$ will pick "goal" as its first node (because its two choices are $f(q_1) = 4$ or $f(\text{goal}) = 2$).


Why is my run time calculation of selection sort different?

Both of you get the same result, $\Theta(n^2)$.
Your calculation is more detailed, and takes into account all parts of the code. In contrast, the calculation in the textbook only considers the most significant part of the code (time-wise), and counts the number of iterations rather than the running time.
If I were writing the textbook, I would rephrase this sentence along the following lines:

The running time of selection sort is dominated by the inner loop (5–7), which runs $\frac{n(n-1)}{2}$ times. The total running time is proportional to that, and so it is $\Theta(n^2)$.

There is no need to carry the various constants as you do. The correct way to simplify your original formula is to state that $T(n) = \Theta(n^2)$, since you can't say anything more about the constants $c_1,\ldots,c_5$ anyway.


What is the closest result relating perfect shuffle closure of primitive words?

I am not aware of any result of this type. And as your example shows, the set Q of all primitive words is not closed under this operation.

You can find subsets of Q which will result only in primitive words. For example a a+ b b+. The perfect shuffles will be from a a+ (ba)+ b b+ and all of these are primitive again (though not from the original set).

The results on square-free shuffle seem to be not about the perfect shuffle, but the general case. Then they say that at least one square-free word is in the shuffle. That should be easy to show for primtive words. In your example, all resulting words are primitve except the one from the perfect shuffle.


Is there a class of formal grammars that generate Recursive Languages only?

I cannot answer the question as asked, but here is what partial result I found,
which may interest you.

I will first address the following problem.

Is there a formal family of automata recognizing all and only recursive languages?

The answer to that question is no. This can be proved by diagonalization.

Suppose such a family F of automata, They can be enumerated as
integers like TM, and there is a F-universal Turing Machine U that can
simulate them given their integer representation. So given such an
automaton M and an input X, U(M,X) can tell wether X in in the
recursive language recognized by M, and always halt. Now, we modify U
into a machine U' that lies when X=M. Then consider the language
string X recognized by executing U'(X,X). By construction, the TM U'
will always halt with an answer (yes or no), thus recognizing a
recursive set. But it gives for any X an answer different from the one
given by automaton X. So the language recognized is different from any
of the languages recognized by the automata in the family F. So the
family F cannot recognize all recursive languages. This establishes
the result by contradiction.

However, this is not the question asked. The question is :

Is there a formal family of grammars generating all and only recursive languages?

This question is about a generative device rather than a
recognizer. Simulating a generative device will always halt and give
me an answer if a string is in the language. But it will tell me
nothing when a string is not in the language. Simulating generation
will just give a non-halting computation if used for recognition.

To do better, I would have to pair each grammar with the grammar for
the complement language, in which case I would have a recognizer, by
simulating both in parallel, being sure that one will find the input
string. But we have seen that such a recognizer cannot exist. So
pairing such grammars for complementarity is not possible.

Given such a grammar, we would know there is another one that is its
complement, but it would be undecidable whether any given one is the one generating the
complement language.

But I do not know at this point whether such a grammatical formalism can exist.