You seem to be pretty confused, so let's sort some things out.
First, it's "implies", not "replies". That is, the formula $\phi\implies \psi$ means that if $\phi$ holds, then $\psi$ holds.

To be more precise, the formula $\phi\implies \psi$ is true in one of two cases: either $\phi$ is false, in which case we say that the implication is vacuously true, or if both $\phi$ and $\psi$ are true.

Now, in LTL, the operator $G$ means that something holds in every position in the computation.
Let's examine the two "sides" of your formula with respect to that.

The formula $G(\phi\implies \psi)$ means that in every point of the computation, the formula $\phi\implies \psi$ is true, in the form mentioned above.

The formula $G\phi\implies G\psi$ means, as above, that either $G\phi$ is false, or both $G\phi$ and $G\psi$ is true.

Now it is fairly easy to see why the formula you have is true: if $G(\phi\implies \psi)$ is true, then, if $G\phi$ is true, then $\phi$ is true in every position, but then according to the LHS we have that $\psi$ is also true in every position, so $G\phi\implies G\psi$ is true.

For your second question, an informal way to think about this (there are many others, probably) is this: if you require that whenever $\phi$ holds, then $\psi$ must also hold, then in particular, if $\phi$ is always true, then $\psi$ is also always true.


What is the appropriate means of bias field in image processing?

Bias field is magnetic based inhomogenity in results of MRI, which comes from magnetic settings, patient position etc.
This term has no standard definition in terms of image processing.
Essentialy this is smooth, low frequency, gradiented signal, which covers valuable data.
In terms of MRI this is just artifact and very often when somebody says that image will be preprocessed or will get rid of artifacts, bias field is included (naming it simply - noise from equipement).


They say it in the paper.

  Let a wedge be a two-hop path in an
  undirected graph.

So it is a path with 2 edges, like 2/3 of a triangle.


Enumerating the elements of an integer lattice $\mathbb{Z}^n$

Your additional condition requires the tuples to be listed in ascending order of the sum of the absolute value of their components. We are free to choose the order of tuples with the same sum, so I propose the following procedure:

list(k,n) lists the $k$-tuples, where the absolute values sum to $n$:

For i=n downto -n:
  Output all outputs of list(k-1,n-|i|), each prefixed by i.

list(k) lists all $k$-tuples:

n=0;
While true:
  Output all outputs of list(k,n).
  n++.


Formal grammar with variables for consistent substitutions

You've created an affix grammar, so named because they were created to deal with affixes (prefixes and suffixes) in natural languages.

Specifically, this is a type of affix grammar where the "affixes" (what you call typed variables) are defined by the same type of grammar rather than coming from a simpler (finite) grammar. This creates a two-level grammar, specifically a type known as a Van Wijngaarden grammar after its creator.

It turns out that this type of grammar is in fact Turing-complete, so non-trivial semantic properties of such grammars are undecidable by Rice's theorem. On the one hand this makes them extremely powerful; on the other hand, it makes them not as useful in practice, since you could use some other Turing-complete system instead.


How to prove the equivalence between Hoare and Floyd assignment axioms?

but when I try $F = G[v/e]$ then from $\exists v' (F[v/v'] \land v=e[v/v'])$ I can't obtain $G$.

We can assume $v'$ not free in $G$. Then, we have

$$
\begin{array}{ll}
& \exists v' (F[v/v'] \land v=e[v/v']) \\
\iff & \mbox{\{def. $F$\}}\\
& \exists v' (G[v/e][v/v'] \land v=e[v/v']) \\
\iff & \mbox{\{property of $H[v/-][v/-]$\}}\\
& \exists v' (G[v/(e[v/v'])] \land v=e[v/v']) \\
\iff & \mbox{\{replacing equals with equals\}}\\
& \exists v' (G[v/v] \land v=e[v/v']) \\
\iff & \mbox{\{$[v/v]$ has no effect\}}\\
& \exists v' (G \land v=e[v/v']) \\
\iff & \mbox{\{$v'$ not free in $G$\}}\\
& G \land \exists v' (v=e[v/v']) \\
\implies & \mbox{\{logic\}}\\
& G
\end{array}
$$

The crucial step is to realize that any $v$ which occurs free in $G[v/e]$ is a $v$ that originated from $e$. Hence, $G[v/e][v/t] = G[v/(e[v/t])]$.

Also note that we don't get exactly $G$ but a slightly stronger postcondition. Since postconditions can be weakened, this is not an issue.


Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$

The idea is to split the sum into two parts: For individual values of i for $i <= a^{1/2}$, then for individual values of floor (a/i). For example find the smallest and largest values i where floor (a/i) = 1 or 1 <= a/i < 2. The values i^2 can be summed with a simple formula.

Here's how we can do this efficiently:

We have $a/i ≥ k$ iff $i ≤ a/k$ or $i ≤ \lfloor a/k \rfloor$. Define $g(k) = \lfloor a/k \rfloor$, then $a/i ≥ k$ iff $i ≤ g(k)$.

We have $\lfloor a/i \rfloor = k$ iff $a/i ≥ k$ but not $a/i ≥ k + 1$, that is $i ≤ g(k)$ but not $i ≤ g(k+1)$, or $g(k+1) < i ≤ g(k)$.

Define $f(n) = (n \cdot (n+1) \cdot (2n+1))/6$, then the sum of squares from $1^2$ to $n^2$ is $f(n)$. The sum of the squares $i^2$ for $g(k+1) < i ≤ g(k)$ is $f(g(k)-f(g(k+1))$.

So the sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor = k$ is $k \cdot (f(g(k)-f(g(k+1)))$. We pick some m close to $a^{1/2}$. The sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor ≤ m$ equals $k \cdot (f(g(k)-f(g(k+1)))$, summed for 1 ≤ k ≤ m. This covers all $i > g(m+1)$.

To this sum we add $\lfloor a/i \rfloor \cdot i^2 = g(i) \cdot i2$ for 1 ≤ i ≤ g(m+1).


Is knowing ALL factors of a large number an NP?

NP is a class of decision problems. Only decision problems can belong to NP. The problem "factor a number" is not a decision problem.

You can make up many decision problems that attempt to capture factoring. Here is one: the language of all quartets $(n,i,j,b)$ such that the $j$th bit of the $i$th prime factor of $n$ is equal to $b$. This language is in NP, since the factorization of $n$ functions as a witness (this uses the fact that primality can be tested in polynomial time; in fact, it is enough to know that primality is in NP, which is an easier fact). It is strongly suspected that this language is not NP-complete.


A problem in NP can be solved quickly if the answer is YES. Your inverted Turing machine finds the answer quickly if the answer to the original question is YES and the answer to the inverted question is NO. You need an answer quickly if the answer to the inverted question is YES and to the original is NO, and you don't have that.

Edit: Take for example the "Travelling Salesman" problem. I give you a list of cities to visit and ask you "is there a tour to visit them all that is at most 957 miles"? If the answer is YES then there is such a tour, so all your nondeterministic TM has to do is take such a tour and verify in polynomial time that it is indeed 957 miles or shorter. You only need to check one tour (the right one) to prove the answer is YES. If the answer is NO then you have to check all possible tours and see that none is short enough. Proving the answer is NO is a lot, lot harder.


Implementing Nesetril and Poljak's clique detection algorithm

The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication.
So let $\ell$ indeed be divisible by three. The auxiliary graph $H$ has a vertex for every $K_\ell$, and an edge between two vertices precisely when the corresponding vertices form a $K_{2\ell}$. Then $G$ has a $K_{3\ell}$ iff $H$ contains a triangle.

Example: Suppose we wish to find cliques of size 6 from a given graph $G$. The trivial algorithm that checks all 6-sets of $V(G)$ runs in time $\Theta(n^6)$. Let's see how we can improve on this.
Observe that $\ell = 2$, i.e., we are looking for cliques of size $3\ell = 6$. To build $V(H)$, we check all 2-sets in $O(n^2)$ time (but of course now the $K_2$'s are precisely the edges of $G$). Similarly to build $E(H)$, we spend $O(n^4)$ time. The graph $H$ has $\Theta(n^\ell)$ vertices, so a triangle can be detected in time $O(n^{\omega \cdot \ell})$ in it, where $\omega < 2.376$ is the exponent of matrix multiplication. In our case, this simplifies to $O(n^{4.752})$ time, beating the naive brute-force algorithm above.


Does the proof of undecidability of the Halting Problem cheat by reversing results?

Short version: The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that decides whether the input machine halts on the given string or not can't exist.

Long version: First we'll sketch the proof (or at least one version of it - there are many).

Assume that we have a Turing Machine $\mathrm{HALT}(\langle M\rangle, x)$ that decides whether the Turing Machine $M$ halts on input $x$ or not.
Using $\mathrm{HALT}$ we construct a machine $\mathrm{FLIP}(\langle M\rangle, x)$ which uses $HALT$ to check whether $M$ halts on $x$ or not, then does the opposite, i.e. if $M$ halts on $x$, $\mathrm{FLIP}$ loops, if $M$ does not halt on $x$, $\mathrm{FLIP}$ halts.
Finally we create a TM $\mathrm{C}(\langle M \rangle)$ (I ran out of good names), which takes the description of a TM and runs $\mathrm{FLIP}$ with input $(\langle M \rangle, \langle M \rangle)$, outputting whatever $\mathrm{FLIP}$ outputs.

It is important to note that as long as the decider $\mathrm{HALT}$ exists, each of these steps is simple to implement; $\mathrm{FLIP}$ just has to use $\mathrm{HALT}$ to check what to do, and $\mathrm{C}$ just duplicates its input to pass to $\mathrm{FLIP}$.

The contradiction arises when we look at what happens when we run $\mathrm{C}(\langle\mathrm{C}\rangle)$. Either $\mathrm{C}$ halts when given itself as input or not. $\mathrm{HALT}$ will decide this:

If $\mathrm{C}$ halts on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{Yes}$, but then $\mathrm{FLIP}$ will loop, so $\mathrm{C}$ will loop, contradicting $\mathrm{HALT}$.
If $\mathrm{C}$ loops on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{No}$, but then $\mathrm{FLIP}$ will halt, so $\mathrm{C}$ will also halt, contradicting $\mathrm{HALT}$.

As each of the steps in the construction is clearly sound, we can only conclude that $\mathrm{HALT}$ can't exist; we have constructed a case where no matter what it says, $\mathrm{HALT}$ can't possible decide what to output, i.e. the problem is undecidable. Just to really hammer on the point a bit, $\mathrm{HALT}$ can't exist - that is there can't be a TM that decides the Halting Problem - because there is at least one case we have explicitly constructed where there is no logically possible answer. Remember a decider is not allowed to output the wrong answer and has to output something, but in the case we have constructed, both possible answers are wrong.


One-dimensional packing problem: Optimal decomposition of music structure

If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails.
Let $G = (V, E)$ be an undirected graph with $n$ vertices $v_1, \dots, v_n$ and $m$ edges $e_1, \dots, e_m$.
Construct an instance of your problem  by creating $n'=n$ groups as follows:

For each vertex $v_i \in V$, add a new group with fitness $1$ containing all intervals $[j-1, j]$ where $j$ is such that $v_i$ is an endpoint of $e_j$.

Any independent set $S \subseteq V$ of $G$ induces of collection of non-intersecting groups (except for the boundaries of the intervals) with total fitness $|S|$.
On the converse, any subset of $S'$ non-intersecting groups must have total fitness $|S'|$ and induces an independent set of size $|S'|$ in $G$.
The claim follows since, assuming the ETH, there exists no $2^{o(n)}$-time algorithm for independent set.
Moreover, assuming $\mathsf{P} \neq \mathsf{NP}$, the above reduction also shows that for any constant $\epsilon>0$ there exists no polynomial-time $n^{1-\epsilon}$-approximation algorithm for your problem, even in the special case of unitary fitness. See, e.g., here.


How does RAM is shared in multi core environment?

I learnt that multi core processors have more than one processing units

Well having more than one processing unit is something present even outside multi-code processors.  Processors which are able to start the execution of several instructions in the same clock cycle are called super-scalar (the first super-scalar processor of Intel in the x86 family is the first Pentium).

Multi-core processors are in fact several processors on the same chip. (Sharing between cores is limited to cache, when sharing more you have architectures called with names like SMT -- simultaneous multi-threading -- or hyperthreading -- which is the name Intel is using).

  I want to know how they share Physical memory.

Modern processors have usually cache (in the x86 family, that started again in the early 90's) so when a core need data, it is usually fetched from the cache without needing to access the main memory.  There is several levels of cache.  The lowest one being used only by a core.  The other can be shared (and how depend on the details of a given model, for example you can have a four core processors with level 2 caches shared between 2 cores).

  There is not much performance gain right, as they have to wait for memory bus to be free?

If one need to access the main memory, it's slow (my rule of thumb: level 1 cache access is 3-5 cycles, level 2 is 20-25 cycles, main memory is 100-150 cycles but again details may vary and I've not looked at them recently).


How to find the cost of pseudocode with a nested loop and a nested if statement?

Big O analysis

The answer is O(n^2).

Good strategy for working this out is eliminate all constant time operations (unless it is a return / break that will change the loop), as everything will always be at least O(1).

This means you can eliminate everything inside the if, as well as the if. So you are left with a simple nested loop running over n

Hence O(n^2)

Cost analysis

You always assume worst case (unless explicitly told otherwise). Therefore assume if statement will be true and statements will run every loop (as there can exist a sorting order where this is true), so your statements will have the same cost as your loop


There is equivalence in an NP-hardness proof or not?

You only need to show that solving $P_1$ allows you to solve $P_2$ (and, hence, every other problem in NP).

$P_1$ might not be in NP so it's not necessarily the case that solving $P_2$ allows you to solve $P_1$.  On the other hand, if $P_1$ is in NP, then you already know that solving $P_2$ allows you to solve $P_1$, by definition of NP-completeness.


Maximum number of augmenting paths in a network flow

I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take  M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.


Is there a total binary computable function that specifies Turing machines with nonempty domain?

My Tip for you:
Check out the second recursion theorem and plug $\Psi$ in for $Q$.
If you can't continue on you own here is my solution:
The second recursion theorem implies that there is such a $m$ that:
$$\varphi_m \simeq \lambda n.\Psi(m,n)$$
($\simeq$ means that the left and right expression are equal for every input $n$ equal and if an expression in undefined for a certain $n$ this is also true for the other expression)
Case 1: $\Psi(m,n) = 1$
This implies $f(m) = 0$ and thus $\text{domain}(\phi_m) = \emptyset$.
But notice that $\varphi_m \simeq 1$ is implied by our assumption.
Thus the domain of $\varphi_m$ is $\{1\}$. That's a contradiction.
Case 2: $\Psi(m,n) = \text{undefined}$
This implies $f(m) = 1$ and thus $\text{domain}(\phi_m)\neq\emptyset$.
But once again $\varphi_m \simeq \lambda n.\Psi(m,n) \Rightarrow \varphi_m \simeq \text{undefined} \Rightarrow \text{domain}(\phi_m) = \emptyset$, which is a contradiction.


Reference request for coding Knight's Tour

The idea is that we have a board of size $n \times n$, where $n$ is say 8 for your usual chessboard. We start from one of the corners (typically), and place a knight chess piece to this corner cell. The question is, can we move the knight through the board such that we visit each cell exactly once?

In graph theoretic terms, this is the Hamiltonian path problem, which in general is NP-complete. The Warnsdorff's rule you describe in the comments is a way to solve the problem pretty efficiently in practice. More generally, the Warnsdorff's rule is a fail first heuristic. This means that by running into dead-ends quickly, we prune the search tree aggressively, and thus succeed quickly.

For a programming exercise (and for the easiness of presentation), it is convenient to represent the graph as an implicit graph: you will have no explicit graph stored, but instead you can just store the coordinates visited, and compute the edges "on the fly".

At every step, your knight is in position $v$ on the board. The set of possible next moves is given by the successor function ("what unvisited cells I can move to from my position $v$?"), let us denote the possible next cells by $N(v)$.
When considering what cell $u \in N(v)$ to pick, we look at the degree of the vertices in $N(v)$. In this case, the degree of a vertex $u \in N(v)$ is given by the number of possible moves the knight can take from $u$.
Let $N^\delta(v)$ denote the set of neighbors of a vertex $v$ with the smallest degree. Our goal is to choose the vertex with the smallest degree; this is really easy if there is only one choice, i.e. if $|N^\delta(v)| = 1$. If this is not the case, we can employ some tie breaking strategy.
A simple and a pretty effective tie breaking strategy is to pick the next vertex $u \in N^\delta(v)$ uniformly at random -- this is simple to implement as well.

For a programming exercise, I definitely recommend using implicit graphs, and also not fixing the chess piece as a knight. Instead, build say an array of moves your piece can take -- it's pretty fun to try to see how the set of possible moves affect path finding. It's also fun to experiment with vertex choosing heuristics other than Warndorff's, and similarly with tie-breaking strategies.


What machine learning techniques work on ASTs?

Your problem can be solved by existing machine learning methods. So, instead of searching for new technique you should choose from existing techniques. The main part of your problem which separates it from general machine learning problems is AST data which will act as input to your algorithm.

There are a lot of feature extraction techniques available which will help you convert AST data into usable format. I would suggest doing tree traversals to generate a feature vector from your AST and then applying machine learning techniques on it.


Does the AND-compression of SAT depends on the number of SAT instances?

Let me help you determine how you would answer your own question.

The way is to read the paper, and in particular, look at the theorems and the definitions of the notation and the assumptions.  Don't just read the abstract.  You have to read the whole paper.

For instance, you can look at Theorem 1.1, noticing the phrase "...for some $n$ and $t$..." -- to me, that suggests that $t$ is a constant in Theorem 1.

Or, you could look at Theorem 3.1, which explicitly mentions that $t$ is polynomial in $n$, where $n$ is the length of the SAT-instances, in the context of Theorem 3.1.

It's also often helpful to go back to the original paper that introduced the conjecture, and see how they formulated it.  In this case, you can learn (from reading the introduction to the paper you link to) that Bodlaender [2] was the originator of the conjecture, and Fortnow and Santhanam [3] proved the conjecture under a certain assumption.  The paper you link to (the Dell paper) might be assuming papers have read those prior work and are familiar with the technical details of the formulation of the conjecture.  So, go read those papers, too.

Bottom line: you can't stop at reading just the abstract or just the first sentence of the introduction.  You may have to dive into the details, and even into prior papers, to resolve questions like this.  These papers are written for other researchers (who are comfortable doing all that).


How to avoid cascading resizes when resizing hash tables?

You ask how to avoid cascading rehashes but you already gave the answer in your post. You keep the probability that bad events occur small.

Since you mention cuckoo hashing. The probability that you get a long probing sequence is $O(1/n^2)$. So if you rehash, you are inserting $n$ elements from scratch. The probability that the rehash is not successful is then $O(1/n)$, so with very high probability you are successful. In expectation you need only a constant number of tries. If you observe that you have problems with rehashing, then you should increase your table size and modify your load factor. Alternatively you can select a better family of hash functions.


For complexity classes A and B, what does $A^B$ mean?

An oracle is a way for a Turing Machine to ask a question and get it answered immediately, "magically". The way we usually model it is that the Turing Machine can write down the question on a special, extra tape, and then (say) the tape is erased and the answer immediately written on it.

More specifically, we usually suppose that the oracle is for a particular language, so we write a string on the tape, followed by some special "end-of-string" symbol; then, the formula disappears and is replaced by either "YES" or "NO".

For a concrete example, suppose our Turing Machine has an oracle for SAT. Then it can write a formula on the string and immediately find out if it's satisfiable or not.

Notice that, since SAT is NP-Complete, a TM with a SAT oracle can decide any language in NP in polynomial time: Just reduce the input to a SAT formula, and then ask the oracle about this SAT formula.

So we might write $P^{NP}$ for the set of languages that can be decided in polynomial time by a TM with an oracle for SAT.


If you start with a dag then the only thing you need to check is whether adding the edge $U\to V$ will not create a cycle. That is, there should not exist a path from $V$ to $U$ in the original graph.


Selecting vertices in a graph in an order to keep border vertices as few as possible

At first I didn't see how the problem underlying your actual application of using file buffers optimally matched your formulation. But as you mentioned in a comment, they are in fact two equivalent ways of describing the same problem, which amounts to generating a valid maximum-buffer-size-minimising sequence of operations, with each operation being one of "Load file $x$ to a free buffer slot", "Discard buffered file $y$ from its buffer slot" or "Process edge $(u, v)$" with $u$ and $v$ both being currently-buffered files:

Order vertices (your sequence of larger-by-one sets is equivalent to a vertex ordering) so as to minimise the maximum number of "border" vertices, which correspond to files already loaded into the buffer and which cannot be discarded yet because they are still needed in the future. A sequence of operations can be generated from this vertex order as follows: After choosing a vertex to blacken, load it to a free slot and immediately process all edges it has to existing black vertices (which we know by induction to be still in the buffer) in some arbitrary order, and then (again in arbitrary order) discard from the buffer any of them that have no more white neighbours.
Order edges so as to minimise the maximum number of "live" vertices, where a vertex becomes live the first time an edge it is incident on appears, and ceases to be live just after the last such edge. A sequence of operations can be generated from this edge order as follows: Load any vertices necessary for the current edge (in either order if neither is in the buffer yet), process the edge, discard from the buffer any vertex that is no longer live (again in arbitrary order).

I see now that your "border" is the same as my "live".

It's NP-hard

Fewest buffer slots needed to avoid reloading

If you want to know the smallest number of buffer slots required to process every file-pair (edge) without ever reloading a file (vertex), this problem is equivalent to the Vertex separation number problem, in which the goal is to choose, from all possible vertex orderings, an ordering that minimises the maximum number of "live" vertices, where a vertex is live at time $i$ iff it appeared before position $i$ in the sequence and has an edge to any vertex at position $\ge i$ in the sequence. Basically, a live vertex at some point in time is a file that has been loaded already but can't be discarded from the buffer yet because it is needed again in the future.

The vertex separation number is another name for the pathwidth of a graph, which is known to be NP-hard to compute. (And finding an actual solution -- a sequence of loads that meets this bound -- is at least as hard as this, of course.) No one knows how to solve an NP-hard problem exactly in subexponential time w.r.t. its size, so any algorithm to solve this problem will be likely be very slow for $n > 20$ vertices or so. The only bright side here is that you don't have to feel bad about using a brute-force solution, like trying all possible vertex orderings. Some tricks may give good speedups in practice, like branch and bound (noticing when your sequence of vertices so far is already worse than a complete solution found earlier, and halting recursion early).

Fewest loads needed for given buffer size

If you have a fixed number $b$ of buffer slots and want to know the smallest number of loads that would be needed using that many slots, this problem is at least as hard as the former one: Any algorithm that answers this question can easily be changed to answer the former one, by binary-searching on $b$ until you find that the answer is equal to the number of vertices (files), $n$. (Again, finding a sequence of loads meeting this bound is at least as hard as this.)

Heuristics

The above explains why you can't expect to solve large instances of this problem quickly and optimally. If you don't care too much about optimality, many heuristics are possible.

Probably the simplest, and what I would try first, is just trying many different random orders, measuring each, and returning the best. Alternatively, start from a random order and look for local improvements, like swapping each pair of vertices, and greedily take the new solution if it is better. When no better solution can be found, restart with a fresh random order. Repeat this as many times as you feel like.

Alternatively you could repeatedly choose a vertex of minimum degree, and process all edges incident on it that have not already been processed. A minimum-degree vertex can be chosen in constant amortised time, and this approach bounds the number of loads by $kn$, where $k$ is the degeneracy of the input graph -- a number that is likely to be low on sparse graphs. Often there are multiple elimination orderings, which may require different numbers of reloads, so this basic strategy could probably be improved quite a bit by tracking which vertices currently have all their neighbours already in the buffer, immediately processing all edges incident on them, and then discarding them.


Time spent on requirement and its effect on project success and development time

See Code Complete, By Steve McConnell, Table 3-1.
He compares the average cost of fixing defects based on when they're introduced and detected.
Detection at construction time costs 5-10 times more than detection at requirements time, and 10-100 times more post-release.

The table is based on the following sources:

"Design and Code Inspections to Reduce Errors in ProgramnDevelopment" (Fagan 1976)
Software Defect Removal (Dunn 1984)
"Software Process Improvement at Hughes Aircraft" (Humphrey, Snyder,
and WIllis 1991)

and several more


What algorithms for unification over (multidimensional) array terms?

By way of context, I'll assume the goal is to do unification in classical first-order logic in a fixed language $\mathscr{L}$. (Formatting and other corrections welcome.)

Briefly, you can treat arrays as terms and multidimensional arrays as arrays of arrays. You'll also introduce a new term symbol that doesn't occur in $\mathscr{L}$.

So for example, if you have a multidimensional array like the following,

\begin{pmatrix}
1 & 2 & 3\\
x & y & z
\end{pmatrix}

you'll first convert it to an array of arrays,

$$\text{((1 2 3) (x y z))}$$

and then convert it to terms. Assuming the term symbol a is not in your language, you can now represent your multidimensional array as follows:

    a(a(1,2,3),a(x,y,z))


Language consisting of all Turing machine encodings

The complexity of $A$ depends on the encoding used for Turing machines. It is easy to come up with an encoding in which every string encodes some Turing machine (there are lots of ways). In contrast, it is easy to come up with artificially "hard" encodings, say the $k$th Turing machine being encoded by $1^kb$, where $b=1$ iff the $k$th Turing machine halts on the empty input; under this encoding, $A$ is not decidable. Nevertheless, it seems intuitively clear that any reasonable encoding makes $A$ decidable, though it's hard to say anything more without knowing the exact encoding.


Method for measuring the 'similarity' between FSA grammars?

you might have more luck from another angle & looking into research into music piece similarity, there are researchers studying that, and while your approach can work, there are other approaches. there are large databases that look at many elements/ criteria such as lyrics, genre etc. eg Music genome project.

sometimes when theres a wide variety of algorithms a survey can help. here are two surveys on graph matching.

Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching
Brian Gallagher
Graph Similarity and Matching / Zager


Find shortest path that visits all nodes in a given set of nodes

I answered a more general problem a couple days ago. You simply want the destination pairs to be (a, b), (b, c), (c,d ),etc.

The gist is to translate the problem into a minimum-cost integer multi-commodity flow problem with a maximum capacity of $1$ per node, and one commodity between each pair of destinations.


Finding the minimum cut of an undirected graph

There are plenty of algorithms for finding the min-cut of an undirected graph. Karger's algorithm is a simple yet effective randomized algorithm.

In short, the algorithm works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success,
the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

See the Wikipedia entry for more details. For perhaps a better introduction, check out the first chapter of Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.


Search a sorted array that ends with zeros in O(log n) time

Here is a simple algorithm to solve the problem as in Yuval's comment.
Algorithm
Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-decreasing positive numbers and the rest are 0s.
Output: An index $k$ such that $A[k]=w$ or -1 if $w$ is not an element of $A$.
Procedure:

Check elements at index $1,2,4,8,\cdots$, until a zero is found or the index overflows. Let the index thus found be $p_0$. Let $p$ be the smaller of $p_0$ and $m-1$. Note $n\le p\lt 2n$.
Consider 0 as greater than all positive numbers so that $A[0], A[1], \cdots, A[p]$ becomes a sorted array. Conduct a binary search for $w$ on that array. If $w$ is found, return the index; Otherwise, return -1.

Algorithm analysis
Step 1 checks at most $\log_2(2n)=1+\log_2 n$ elements. Step 2 checks at most $\log_2(p+1) + 1 \le 2 + \log_2n$ elements. So the time-complexcity of the algorithm is $O(\log n)$.
This problem is a variation of the classic problem of searching sorted, unbounded/infinite lists. The algorithm above is a simple variation of the exponential search explained in this Wikipedia article. You are encouraged to take a look at that article for more intriguing variations. For example, a basic version of Bentley and Yao's algorithms checks elements at index 2, 4, 16, 256, 65536, $\cdots$ first.
Exercises
Exercise 1. (One minute or two) Assume that $w$ might not be positive and the first $n$ element of $A$ might not be positive instead. Adapt the algorithm slightly so that it still works.
Exercise 2. (One minute or two) Improve the algorithm so that it runs in $O(\log k)$ time where $k$ is the smaller of $n$ and the index of the first element in $A$ that is no less than than $w.$
Exercise 3. Let $B$ be a sorted array of $n$ distinct elements, one of which is $w$. Devise an algorithm that finds $w$'s index in $O(\min(k, n-k))$ time, where $k$ is $w$'s index.


A reasonable potential function here would be $C\ell$ or $C(k-\ell)$, where $\ell$ is the number of elements on the stack.

However, I don't think that the amortized cost can be bounded. Consider $k$ push operations followed by $M$ copy operations. The total cost is $k(M+1)$. If the amortized cost of push is $a$ and of copy is $b$, then $ka + Mb \geq k(M+1)$. Dividing by $M$ and letting $M\to\infty$, we obtain $b \geq k$.


What is the simplest known NP-Complete problem for testing P=NP solutions?

Since all NP-complete problems are basically equivalent, it's hard to say which one is the easiest. SAT was one of the original problems and has important practical applications, so it is really well studied. Writing fast SAT-solvers seems like a reasonably interesting hobby to me and getting started is not terribly hard. Integer Linear Programming is similarly important and well studied.

The only objective way to discern NP-complete problems that I know of is their approximability. Some problems are hard to approximate, for others you can get almost arbitrarily good solutions in polynomial time.

Subset sum is both very simple to understand and "simple" to solve. Simple to solve means that it has an easy Pseudo-polynomial algorithm and is easy to approximate. However, I don't know about any research involving the problem.


Why are the laws of an applicative functor defined the way they are?

As described in the original idioms paper, Applicative (called Idiom there) corresponds to a strong lax monoidal functor. This can be formulated as:

class (Functor f) => MFunctor f where
    unit :: () -> f ()
    pair :: (f a, f b) -> f (a, b)

The applicative functor laws are then equivalent to the above operations being "monoidal" in the following sense (plus the functor laws):

fmap snd (pair (unit (), u)) = u
fmap fst (pair (u, unit ())) = u
fmap (\(a, (b, c)) -> ((a, b), c)) (pair (u, pair (v, w))) = pair (pair (u, v), w)

The "strength" aspect comes from the fact that these operations (and the functor ones) are "first-class". In a language without higher-order functions, the lax monoidal functor would not be strong. (The usual presentation of Applicative doesn't even make sense in a language without higher-order functions whereas the MFunctor presentation does.)

So, dropping any of the laws means you don't have a lax monoidal functor.

Yet another way of looking at it is to note that the applicative functor operations and laws give rise to a family of operations: liftN :: ((a1, ..., aN) -> b) -> (f a1, ..., f aN) -> f b with unit = lift0 id and pair = lift2 id. Using Agda, we could present this more formally as:

open import Level

data List {i : Level}(A : Set i) : Set i where
    Nil : List A
    Cons : A → List A → List A

record ⊤ : Set where
    constructor tt

record _×_ (A B : Set) : Set where
    constructor _,_
    field
        fst : A
        snd : B

All : (Set → Set) → List Set → Set
All P Nil = ⊤
All P (Cons x xs) = P x × All P xs

module _ {F : Set → Set}
    (map : {A B : Set} → (A → B) → F A → F B)
    (unit : ⊤ → F ⊤)
    (pair : {A B : Set} → F A × F B → F (A × B))
 where
    pull : {As : List Set} → All F As → F (All (λ A → A) As)
    pull {Nil} tt = unit tt
    pull {Cons A As} (x , xs) = pair (x , pull {As} xs)

    liftN : {B : Set}{As : List Set} → (All (λ A → A) As → B) → All F As → F B
    liftN f xs = map f (pull xs)

This perspective arises due to the connection between monoidal categories and multicategories. A lax monoidal functor corresponds to a map of multicategories, liftN being the action on multiarrows. If Haskell had multi-ary functions, it would be natural to model it with a multicategory. The appropriate analogue of "functor" would be a map of multicategories, i.e. an applicative functor. From the multicategory perspective, the applicative functor laws are what make the action on multicomposition coherent. Roughly speaking, if we dropped, say, the associative law for pair, this would be akin to having functions with a binary tree of parameters instead of a list of parameters. One could explore generalized multicategories for this.


Modelling a basic sequential circuit as a transition system?

How does the transition system (denoted by $\texttt{TS}$) relate to the sequential circuit (denoted by $\texttt{SC}$)?

The states of $\texttt{TS}$ are all possible combinations of values of variable $x$ and register $r$ (no output variable $y$) in $\texttt{SC}$.
The label of each state in $\texttt{TS}$ consists of all the variables (including the register) which are evaluated true given the valuations in $\texttt{SC}$.
For example, $\{x, r, y \}$ for state $(x = 1, r = 1)$ means that all variables are true according to $\lambda_y = \lnot (x \oplus r)$ and $\delta_r = x \lor r$ given $x = 1, r = 1$.
The transitions (arcs with arrow) between states in $\texttt{TS}$ result from the functions $\lambda_y$ and $\delta_r$.
For example, $(x = 0,r = 1) \to (x = 0,r = 1)$ if the next input bit equals 0.

For more details and a general recipe for modeling sequential hardware circuits as transition systems, please refer to the book "Principles of Model Checking" (Section 2.1.2) by Christel Baier and Joost-Pieter Katoen. The MIT Press.


Is $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction?

No, this would contradict the time hierarchy theorem. Note that any language in $\mathsf{EXP}$ is polynomial time reducible to some language in $\mathsf{E}$ by padding. Suppose $L\in \mathsf{DTIME\big(2^{n^c}\big)}$, then consider $L'=\big\{x0^{|x|^c}\big|x \in L\big\}$. Obviously $L'\in \mathsf{E}$ and $L\le_p L'$, thus if $\mathsf{E}$ is closed under polynomial time reductions we have $L\in\mathsf{E}$ and consequently $\mathsf{E=EXP}$.


Is there any sort of formal definition of terms like 'data type', 'abstract data type', etc?

I good starting point is Benjamin Pierce's Types and programming languages (popularly referred to as "TAPL").


A regular expression for all strings that have exactly one double letter in them?

It took me a while to understand that your alphabet $\Sigma$ is $\{a,b\}$ and by /\ you meant the empty word $\epsilon$.

Your regular expression is the union of two sub-expression, namely:

(b + /\)(ab)*aa(ba)*(b + /\); and
(a + /\)(ba)*bb(ab)*(a + /\).

The first one (resp. second one) matches all the words that contain exactly one double letter, and that double letter is "a" (resp. "b"). Since the two sub-expression are similar (just swap "a" and "b"), I will only describe the first of the two.

A word $w$ that matches the first sub-expression contains exactly one occurrence of  "aa" and no occurrence of "bb", and can then be decomposed as
$$w = x \circ \, aa \, \circ y,$$
where "$\circ$" denotes concatenation and:

$x$,$y$ are strings that contain no double letters;
$x$ does not end with "a" (as otherwise you would have 3 consecutive "a"s in $w$).
$y$ does not start with "a".

We are then left with the task of finding a regular expression for $x$ and $y$.
Let's consider $y$ first.
Either $y = \epsilon$, or it must start with a $b$. Moreover, since no two characters in a row can be the same, $y$ is just an alternation of "b"s and "a"s. This can be expressed as $(ba)^*$ if $y$ has even length (i.e., if it ends with an $a$), and as $(ba)^*b$ if $y$ has odd length.

Therefore we can write the following regular expression for $y$: $(ba)^* + (ba)^*b$ and, by factorizing the common prefix, $(ba^*)(b+\epsilon)$.

The argument for $x$ is analogous, with the exception that $x$ is either $\epsilon$ or it must end with a "b". With a similar reasoning we get:
$x = (ab)^* + b(ab)^* = (b + \epsilon)(ab)^*$.

Substituting our regular expression for $x$ and $y$ back into the formula for $w$ we obtain:

$$
w = x \circ \, aa \, \circ y = \underbrace{(b + \epsilon)(ab)^*}_x \; aa \; \underbrace{(ba^*)(b+\epsilon)}_y .
$$.


Would it be possible that the intersection of two non-context-free languages is context-free?


How hard is finding the shortest path in a graph matching a given regular language?

This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:

The vertices of $G^\prime$ are $(V \times M) \cup \{\#\}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $\#$.
For each edge in $e \in E$ from $v_1$ to $v_2$, add an edge in $G^\prime$ from $(v_1, m_1)$ to $(v_2, m_2)$ with weight $w(e)$ if and only if there is an edge in $M$ from $m_1$ to $m_2$ that is labeled $\ell(e)$.
For each accepting state $m$ in $M$, add an edge in $G^\prime$ from $(t, m)$ to $\#$ with weight 0.

Then the shortest path in $G^\prime$ from $(s, m_0)$ to $\#$ (where $m_0$ is the initial state of $M$) gives the shortest path in $G$ from $s$ to $t$ matching $L(M)$. There cannot be a negative cycle in $G^\prime$, since dropping the $m$ states from the vertex labels would give a negative cycle in $G$, which we are assuming does not exist.

This also answers the question if $M$ is a DFA or regular expression instead of an NFA, since these can be converted to an equivalent NFA in polynomial time. We can also directly handle NFAs with $\varepsilon$-transitions: if $M$ contains an $\varepsilon$-transition from $m_1$ to $m_2$, add an edge in $G^\prime$ with weight 0 from $(v, m_1)$ to $(v, m_2)$ for each $v \in V$.

For fixed $M$, the product graph $G^\prime$ has only linearly more vertices and edges than the original graph $G$. This means that any fixed problem of the form "find the shortest path that visits edges in such-and-such order", such as the problems linked in the question, can be solved just as fast as the ordinary shortest path problem asymptotically.

As an implementation detail, note that there is no need to actually write down the whole product graph in memory. The vertices and edges can be generated dynamically while running the shortest path algorithm, which allows unused vertices to be skipped entirely.


prove language is Context-free and not regular

To prove that the language is Context Free, it suffices to give the Push Down Automaton, and that language is recognized by one of the simplest PDA.

To prove that the language is NOT regular, you don't only have to show that you can't find an appropriate Automaton (be it a FDA or FNA, they have equivalent expressive power), but that no one can.

That proof can't be shown with an example, because you want to prove that not a single FDA can recognize the language correctly. The proof shows a contradiction between having such FDA and that the FDA correctly rejects some words outside the language.

The idea is similar to the pumping lemma. Suppose that you have an FDA that recognizes the language, you are going to break it. That FDA is, as it name says, finite, let it's size (node count) be $N$. To recognize the words in $\left \{ a^ib^i | i\geq N \right \}$ it certainly has to do some loops.

By exploiting a loop of length $l$ (looping in it one time more than the expected), you can see that $a^{(i+l)}b^i$ should also be accepted by that FDA, so it fails to recognize the language, as it would accept words that are not in it.


Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem

First, note that $\log_4 3 = 0.792...$.  Now the key observation is that $n^{0.792..}$ grows asymptotically slower than $n \lg n$, i.e., $n^{0.792...} = O(n \lg n)$, or if you prefer, $n \lg n = \Omega(n^{0.792...})$.  Why?  Well, one way to see it is to notice that $n^{0.792...} = O(n)$ and $n = O(n \lg n)$: $n^{0.792...}$ grows asymptotically slower than $n$, because the exponent is smaller; and $n$ grows asymptotically slower than $n \lg n$.

What's up with the $\epsilon=0.2$? That's probably a clunky way of getting at the fact that $n^{0.792...}$ is smaller than $n^{1.000...}$.  In particular, $0.792 + 0.2 < 1.0000$.  Personally, I don't find it a particularly helpful explanation for why $n^{0.792...} = O(n)$, so I would suggest you ignore it.  If you find it confusing, it's not just you, and it doesn't represent some shortcoming in your understanding; it just seems like a confusing way to explain it to me.


Maintain your buy-order book as an array of companies.
For each company, keep a priority queue of prices (max for buy and min for sell).
For each price, keep a queue of orders.

To check for matching orders, for each company, call find-min() and find-max() on the company in the sell array and buy array to find the best buy/sell prices. If max > min, then try to fulfill the order. To fulfill the order, pull elements off of your buy and sell queues for that company and price, until one of your price queues is empty. When the price queue is empty, delete the corresponding element from its priority queue, and perform the check again.

This strategy costs constant time per order, and $O(\log p_i)$ per price change, where $p_i$ is the number of prices for company $i$.


How can I efficiently construct a CFG from a language

The best way is to learn is to look at examples, and see how they work.
One of the simplest "real" context-free languages is $\{\; a^mb^n \mid n = m \;\}$
Its grammar is $S\to aSb\mid \varepsilon$.
Now add in steps, the extra 3, and the more than ...
$\{\; a^mb^n \mid n = m+3 \;\}$
$\{\; a^mb^n \mid n \le m+3 \;\}$


Turing machines and their computational power

Your question is closely related to the Church–Turing thesis, which says that Turing machines can compute anything that can reasonably be described as an algorithm (i.e., a sequence of discrete steps). Variants, such as the physical Church–Turing thesis state that Turing machines can compute anything that can be computed by any physical mechanism. Note that these are described as "theses", rather than theorems. They're not formal claims about mathematics so they're not possible to prove.

We don't know how to build any physical device that could compute a non-Turing-computable function. This includes quantum computers, which can be simulated (though inefficiently) to arbitrary accuracy by non-quantum devices such as Turing machines.

We can certainly consider more powerful devices, though, even though we don't know of any way to build them. A typical construction is to take something that Turing machines can't do, and then imagine that we have a subroutine that instantly solves that problem. These are known as oracle machines, and they are provably more powerful than Turing machines. Indeed, one can define a whole infinite hierarchy of successively more powerful machines using this idea, with the caveat that we have no clue how to physically build such a thing.


Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states}

You need dovetailing. This is quite common in such problems.

As you pointed out, we can not simply run $M$ on an input $w$, since that might diverge. To avoid that, we enumerate all the possible pairs $(w,k)$ where $w$ is an input word, and $k$ is a natural. For each such pair, we run $M$ on input $w$ for at most $k$ steps. This will never diverge because $k$ bounds the computation. If $M$ within that bound visits all states, we accept. Otherwise, we try the next pair.

Note that, in order to enumerate all such pairs, we need a computable bijection $(\mathbb N\times \mathbb N) \to \mathbb N$ (or, equivalently, $(\Sigma^*\times \mathbb N) \to \mathbb N$). The existence of such a dovetailing function is one of the standard computability results.


What can be said in general about a homomorphism between two regular languages?

Some examples, to get the discussion going:

For an infinite family of languages with no homomorphisms between them, consider the languages $L_k=\{a,a^k\}\subseteq\{a\}^*$ for $k\ge 2$. If $f:L_i\to L_j$ were a homomorphism for $i\neq j$, then $f(a)$ would be either $a$ or $a^j$, and $f(a^i)$ would be $a^i$ or $a^{ij}$, neither of which is in $L_j$.
On the other hand, it is easy to find infinite chains of languages with homomorphisms between them, just consider $L_i=\{a^k\ |\ 1\le k\le i\}\subseteq\{a\}^*$ and the inclusion $L_i\to L_j$ for $i<j$.


When compiled into binary, what signifies the end of a string? How can this be differentiated from user input which compiles to the same binary?

Both programs in binary form and binary user data are usually stored in files, and normally the filesystem records the length of all its files separately. So, the operating system always knows the end of the binary string, which is supposed to be loaded and executed as a separate process. Please see this question and its answers for more information.

Could an attacker use a binary input with malicious code, added in the end of input string, to modify normal program behavior? Yes, and this method of attacking is called buffer overflow. Fortunately, modern programs normally don't use input functions, which can lead to the buffer overflow.


Direct construction of NFA for the difference of regular languages

The short answer is "yes".

Probably the easiest way to explain it is with an example; turning this into a formal algorithm should be straightforward.

The first NFA, $M$, accepts the language $(a\cup b)^*$:

$$q_0 = \epsilon \cup a q_0 \cup b q_0$$

with the start state being $q_0$.

This is probably not notation that you're used to, but the reason for using this will become clear soon; it's basically saying the same thing as the context-free grammar:

$$ S \rightarrow \epsilon $$
$$ S \rightarrow a S $$
$$ S \rightarrow b S $$

You can see how this is also a description of a NFA. Each term on the right-hand side is either a transition $aq_i$, which means read an $a$ and go to state $q_i$, or $\epsilon$ which means that the state is a final state.

The second NFA, $M$, accepts the language $(a\cup b)^*aa(a\cup b)^*$, that is, any string which contains $aa$. The start state is $q_1$; I've used unique state names for reasons that will become obvious in a moment. I deliberately picked an NFA which has some nondeterminism just to show that this works for that case.

$$q_1 = a q_1 \cup b q_1 \cup a q_2$$
$$q_2 = a q_3$$
$$q_3 = \epsilon \cup a q_3 \cup a q_3$$

We would like to construct a NFA which accepts the language:

$$Q_0 = q_0 \setminus q_1$$

expanding one level gives:

$$Q_0 = (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2)$$
$$ = \epsilon \cup a (q_0 \setminus (q_1 \cup q_2)) \cup b (q_0 \setminus q_1)$$
$$ = \epsilon \cup a Q_1 \cup b Q_0$$

where:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$

Note that we already had a state which handled the $b$ transition correctly. For the $a$ transition, we didn't, so we introduced one.

We continue:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$
$$= (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2 \cup a q_3)$$
$$= \epsilon \cup a (q_0 \setminus (q_1 \cup q_2 \cup q_3)) \cup b (q_0 \cup q_1)$$
$$= \epsilon \cup a Q_2 \cup b Q_0$$

where:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$

continuing again, going a little more slowly this time:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$
$$= (\epsilon \cup a q_0 \cup b q_0) \setminus ((a q_1 \cup b q_1 \cup a q_2) \cup (a q_3) \cup (\epsilon \cup a q_3 \cup b q_3))$$
$$= a (q_0 \setminus (q_1 \cup q_3)) \cup b (q_0 \setminus (q_1 \cup q_3))$$
$$= a Q_2 \cup b Q_2$$

Note that we used the fact that $\epsilon \setminus \epsilon = \varnothing$.

So in summary, we have the following NFA with start symbol $Q_0$:

$$Q_0 = \epsilon \cup a Q_1 \cup b Q_0$$
$$Q_1 = \epsilon \cup a Q_2 \cup b Q_0$$
$$Q_2 = a Q_2 \cup b Q_2$$

You can verify for yourself that this accepts the language.

There are several things to notice about this.

First off, the process must terminate; there are only a finite number of possible transition states which could be created.

Secondly, the running time could be exponential in the worst case; each transition state is of the form $\bigcup_i q_i \setminus \bigcup_j q_j$ where the left-hand side of the set minus is a subset of the states from the first machine and the right-hand side is the same for the second machine. There is a finite number of such subsets, but there could be exponentially many in general, and sometimes there will be. And the reason is...

...the final answer is a DFA! It's not hard to see that this will always be the case. Your question only asked for a method that didn't convert the two NFAs to DFAs first, and you never said anything about not constructing a DFA for the final answer.

Basically what we've done here is folded the NFA-to-DFA conversion algorithm together with the DFA difference algorithm, so one algorithm does both. I think this satisfies the requirements of your question.


Why do source and sink have to be distinct in Ford-Fulkerson?

In a flow network, the source and sink are "special".  The source is defined to have infinite incoming capacity, and the sink is defined to have infinite outgoing capacity -- they are different from all the other networks.  For any node with no incoming edges other than the source, it's true that the flow through that node has to be zero -- but the source is different, because it is special.

Why can't the source and sink be the same node?  Basically, because then you get a different problem with different characteristics.  That other problem is called the circulation problem, and there are algorithms for it.  They are a bit different, though, and your teacher probably doesn't want to confuse you by adding unnecessary complications.


A problem is NP-hard if every problem in NP can be reduced to it by some appropriate kind of reductions (typically, polynomial-time many-one reductions). A problem is NP-complete if it is in NP and is NP-hard.

Therefore, by definition, every NP-complete problem is NP-hard.


Structuring a Regression Model for NCAA Basketball Spreads/Totals

I think a natural approach would be to constrain the coefficient of adjO_T2 to be the negation of the coefficient of adjO_T1, the coefficient for adjD_T2 to be the negation of the coefficient for adjD_t1, etc.  Then, you could learn a logistic regression model subject to that constraint.
This could be implemented in practice by having only the coefficients of adjO_T1, adjD_T1, etc. be model parameters; the coefficients for adjO_T2, adjD_T2, etc., are not additional parameters, but are derived from the coefficients of adjO_T1, adjD_T1, etc.  You can write down a loss function, using the logistic loss, for the loss of any particular set of parameters, and then use optimization to find the parameters that minimize the loss on the training set.
Related: see the Bradley-Terry model.  The above is basically equivalent to using the Bradley-Terry model with exponential score function $p_i = e^{\beta_i}$ where here $\beta_i$ is a linear combination of the metrics for that team, and your goal is to learn the coefficients in that linear combination.  Then $\beta_i$ or $p_i$ represent the "strength" of team $i$, and the Bradley-Terry model says that the probability that team 1 beats team 2 is given by $p_1/(p_1+p_2)$, i.e., it is a function of their relative strengths.


Here are several approaches to compute $x^n$ from smaller powers of $x$:

doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$.
doing $x^2 \times x^{n-2}$. The former is $P(2)$, the latter $P(n-2)$.

But we don't need to use $P(1)$ and $P(2)$ at each step, right? we can use any $P(k)$ with $k<n$. So how about,

doing $x^{n/2} \times x^{n/2}$?
(or in general $x^{k} \times x^{n-k}$)

Now, assume each multiplication takes $M$ time. Which approach is the fastest?

EDT after comments:

the main idea of recursion (somewhat similar to induction), is that we can "solve" some problem by using the solutions of smaller problems.

So $P(n)$ can be easily computed by $P(n/2) \times  P(n/2)$ (assuming $n$ is even and above 2). But how do we compute $P(n/2)$? well, that's the magic, the above idea works for any number $n$ and specifically also for the number $n/2$ (as long as it is even and above 2); So how do we compute $P(n/2)$? We recurse!

  $P(n/2)  = P( (n/2)/2) \times P( (n/2)/2) $

Why does it work? because eventually ((n/2)/2)...)/2 will be either 1 or 2, and this is $P(1)$ or $P(2)$ that we know how to solve.

To sum up, the recursion will look like this:

function P(n):
if n=1 or n=2  return ....
else
   if n is even, return P(n/2) * P(n/2)
   if n is odd, return  ..... (very similar)...

I leave you to work out the details.

This is of course the faster way. The slower way, but maybe simpler to understand, is to do the recursion step by step. The function in this case will look like:

function P(n):
if n=1 or n=2  return ....
else
   return P(n-1) * x

This one works for any number $n$ and returns $x^n$. The last line just instantiates the function again with a smaller parameter.


It means that there exists a polynomial $f(x,y,z)$ such that the algorithm runs in time $f(|S|,n,\frac{1}{\epsilon})$.

Specifically, it means that there are constants $c_1,c_2,c_3\ge 0$ such that the algorithm runs in time $O(|S|^{c_1}\cdot n^{c_2}\cdot (\frac{1}{\epsilon})^{c_3})$.


Suppose you have a Turing machine with an $n$ sized tape with $k$ symbols and $s$ states. This system, as a whole, then has $s\cdot k^n \cdot n$ possible states it can be in ($s$ states, $k^n$ tape contents, $n$ tape head positions).

By definition $k$ and $s$ must be $O(1)$. If $n$ also is however, then the entire expression $s \cdot k^n \cdot n$ is a constant, and we can construct a finite state machine with that many states that has exactly the same behavior as the Turing machine.


Why is the initial state of Zobrist hashing random?

The initial elements are chosen randomly to minimize hash collisions. You can think of the Zobrist hash as a random hash function $h$, mapping board positions to bit vectors of length $N$, chosen from some collection of hash functions. What we are trying to accomplish is this: given any choice of positions $p_1,\ldots,p_n$ arising in the program, we want that with high probability over the choice of $h$, $h(p_i) \neq h(p_j)$.

The Zobrist hash family is 3-wise independent: for any 3 distinct positions $p_1,p_2,p_3$, the hashes $h(p_1),h(p_2),h(p_3)$ are uniformly distributed over all triplets of binary vectors of length $N$. In particular, the probability that $h(p_i) = h(p_j)$ is $2^{-N}$ (we actually only need 2-wise independence for this), and so the expected number of collisions is $\binom{n}{2} 2^{-N}$, which is the same as the expected number of collisions for a completely random hash function.

The Zobrist hash function has an important advantage over a completely random hash function: it is easy to compute. Moreover, it is easy to update after a move of a single piece on the board. It is this last property which makes it especially attractive for hashing board positions.

By choosing the initial elements at random, we guarantee that whatever the board positions $p_1,\ldots,p_n$ are, the probability of collision is small (assuming that the positions are chosen independently of the hash function). There could also be some intelligent choice for the initial elements satisfying that, but it is not clear what this choice should be, and how to analyze it. On the other hand, a random choice succeeds with high probability, which is why we choose the Zobrist table randomly.


This kind of approach is more often called dynamic programming than memoization but they are, indeed, related.

In dynamic programming, however, you usually write the order in which your function is called. (This is one key difference between them.) In this case, you will clearly see that you will compute $n$ longest[i][i] first, then $n-1$ longest[i][i+1], then $n-2$ longest[i][i+2] etc. each computation being in constant time. Giving a complexity of $n+(n-1)+\dots+2+1$=$n(n+1)/2$ i.e. $O(n^2)$.


If you can sort arrays of size $n-1$ then three recursive applications of this sorting procedure are enough, say prefix, suffix, prefix. You can see that using the zero-one sorting theorem, which states that a sorting algorithm works if it can sort zero-one inputs. I leave the case analysis to you.

This algorithm probably works for much smaller $k$. Moreover, it should be the case that given a sorting oracle for $k=cn$ you can sort in $O_c(1) $ time. One can even guess a formula, $O(c^{-1} \log c^{-1}) $.


Looking for the English name of algorithm using a precomputed array for interval sum computation

I think the array sum is the result of the prefix computation of the original array (link).


Sub-exponential time algorithm to compute playoff chances

A pragmatic solution is to use Monte Carlo: do one million random simulations, and for each team, count in how many simulations it made it to the top 5.  This should give you a good approximation of these probabilities, even though the number is not exact.
If you want the exact probabilities, I think there is a complex solution that has polynomial asymptotic running time.  I don't know whether it will be useful in practice.  We'll enumerate all possibilities for the set of teams that make the top-4 and the 5th team, and for each such combination, compute the exact probability obtaining such an outcome.  Asymptotically, if there are $n$ teams, this will involve enumerating $O(n^5)$ combinations, and I'll show below how to compute each of these probabilities in polynomial time, which yields a polynomial-time algorithm -- albeit one that might still be to slow to implement in practice.
Here's how to compute the probability of a particular combination of outcomes, namely, that a specified 4 teams make the top-4 (in some order) and one more specified team is #5.
For each game yet to be played, we can introduce a zero-or-one variable $x_i$ that records who wins.  We can write down a set of linear inequalities that characterize the conditions under which the desired outcome occurs.  The total number of wins of each team is a sum of some of these variables, and we want each of the top-4 teams to have at least as many wins as the #5 team, and every other team to have fewer wins than the #5 team, so we obtain inequalities comparing sums of these variables.  Also for each $x_i$ we have the inequality $0 \le x_i \le 1$. This gives us a linear program, or in other words, a convex polytope.  Now the question is to count the number of integer solutions to this linear program, or equivalently, the number of lattice points inside this convex polytope.  There are known polynomial-time algorithms for this problem; see Finding all solutions to an integer linear programming (ILP) problem.
However, I suspect this fancy algorithm might be non-trivial to code up and might not be very useful in practice, even though it is polynomial time in theory, because of the large polynomials involved.

If you care about the asymptotic running time, I think there might be an improvement to the latter algorithm.  For each team, enumerate all candidates for $t$, the number of wins of the #5-ranked team.  Introduce zero-or-one variables $y_i$, where $y_i=1$ means that team $i$ was in the top 5.  If we are counting solutions where team $j$ is in the top-5, force $y_j=1$.  We obtain an expression $e_i$ for number of wins of team $i$, where $e_i$ is linear in the unknowns $x_i$.  We can then add the inequalities
$$y_i t \le e_i \le t-1 + (3n-2-t) y_i$$
$$y_1 + \dots + y_n = 5$$
and count the number of solutions to this system.


Poly-time computability of inversion of poly-time real functions

In 1-dimensional case, the function has to be strictly-monotone.
Given $y_n$ do a binary search to find $x_n$.

If $\mathsf{P} = \mathsf{NP}$,
given $y_n$ we can guess $x_n$ and then verify that $f(x_n) = y_n$.
The dimension doesn't matter for this part.

For the other part, that is, if $INV_d$ is polytime then $\mathsf{P} = \mathsf{UP}$,
we can reduce it to $INV_2$ by noting that every 2-dimensional function
can be extended to a $d$-dimensional one by letting other coordinates map as identity.
So for $d'<d$,
$INV_d$ being polytime computable implies that $INV_{d'}$ is also polytime.
Therefore $INV_d$ being polytime implies that $INV_2$ is polytime and therefore $\mathsf{P}=\mathsf{UP}$.


Minimise given size using dynamic programming

A dynamic programming approach would be:
$f (p, k)$ is the minimum size when we considered prefix $\{x_1, x_2, \ldots, x_p\}$, and selected exactly $k$ items from it, the last one being $x_p$.
We add sentinels $x_0 = 0$ and $x_{n^2 + 1} = 1$ for our comfort.

Base: $f (0, 0) = 0$.

Transitions: $f (p, k) = \min\limits_{q = 1, 2, \ldots, p - 1} \max \left\{f (q, k - 1), x_p - x_q\right\}$.

Answer: $f (n^2 + 1, n + 1)$, the point number $n + 1$ being the added value $x_{n^2 + 1} = 1$.

In total, this takes $O(n^2)$ to calculate a single $f (p, k)$, and there are $O (n^3)$ such values, so the approach will take $O(n^5)$ time and $O(n^3)$ memory.

The memory could be reduced to $O(n^2)$ by calculating iteratively, like:

for k = 1, 2, ..., n+1:
    for p = 1, 2, ..., n^2 + 1:
        calculate f (p, k)

And storing $f (p, k)$ only for the current and the previous values of $k$ at every moment: the storage strategy can be to store $f (p, k)$ in f[p][k mod 2].

The time could be perhaps reduced to $O(n^3)$ by altering the function to optimize the $O (n^2)$ transition cost to something like $O (1)$ amortized.
But instead, let us consider another approach.

Say we want the answer to be at most $s$.
We can then greedily construct a subset.
First, let $x_{i_1}$ be the greatest possible: $i_1 = \max i : x_i \le s$.
Next, let $x_{i_2}$ be the greatest possible: $i_2 = \max i: x_i - x_{i_1} \le s$.
Then define $i_3 = \max i: x_i - x_{i_2} \le s$, and so on.
If this leads to $x_{i_n}$ such that $1 - x_{i_n} > s$, the answer can't be $s$.
Otherwise, we just constructed a subset of $\le n$ elements with the answer at most $s$.
As the value $i$ is always increasing, for a given fixed value $s$, the check whether $s$ can be the answer takes $O (n^2)$ time and $O (1)$ additional memory.

What's left is to run a binary search over the value $s$, and for each candidate $s$, execute the greedy algorithm above.
The number of binary search iterations can be $\log n$ (there are $O (n^4)$ possible candidates for $s$), or $\log C$ where $C$ is the required precision.
For example, if all $x_i$ are integers from $0$ to $L$, we have a binary search over integers from $0$ to $L \cdot n^2$, so it will complete in $O (\log (L \cdot n^2))$.

In total, this approach takes $O (n^2 \log n)$ or $O (n^2 \log C)$, which is better than an optimized dynamic programming approach would achieve.


Would models of computation in other conceivable universes be Turing complete?

The study of models of computation  extremely broadly construed is called "generalized recursion theory" (or "higher recursion theory," or "generalized/higher computability theory," or etc.). We can indeed rigorously define and study (from a theoretical standpoint of course) models of computation much stronger than what is "physically implementable" in even an ideal sense (according to our current understanding of physics). Some of these include:

Metarecursion theory, which develops an analogy between "computably enumerable" and "$\Pi^1_1$" (and extends to descriptive set theory by developing an analogy between "computably enumerable" and "coanalytic," and is further generalizable e.g. by Spector classes and Q-theory).
$\alpha$-recursion theory, where we shift from computing in the context of $\mathbb{N}$ to computing in the context of more complicated infinite sets with nice properties (and $\beta$-recursion and admissible recursion theory, which generalize $\alpha$-recursion in different directions).
Infinite-time Turing machines, which ... are basically exactly what they sound like.
Ordinal register machines, which are like infinite-time Turing machines but even more so; roughly, they're the analogue of Turing machines when we replace $\mathbb{N}$ by the class of all ordinals.
Kleene recursion, where we look at computations of "higher type" objects generally allowing the use of "lower type" objects (and their "equality predicates") as parameters.
Recursion over general structures, which is too broad to have a single name; see e.g. Blum-Shub-Smale machines (which really are a special case of previously-existing notions) or this book by Moschovakis.

There are also models of computation stronger than Turing machines which are based on "idealized" versions of phenomena which, while extremely exotic, are (somewhat) consistent with our current understanding of physics -  e.g. Malament-Hogarth.

Moreover, we can prove abstract results applicable to all models of computation satisfying some very basic properties. For example, the unsolvability of the halting problem generalizes to any situation where we have a notion of "universal machine." (Of course anything we can conceive has to be "permitted" by the laws of physics to which our physical brains are subject, but my point is that these limits are quite loose: we can conceive of blatantly un-physical objects.)


Some notations in Python convention

$S[:i]$ means the first $i$ letter of string $S$.
$S[-i:]$ means the last $i$ letter of string $S$. ($S[-0:]$ is the empty string, which is not Python convention.)

$S+T$ means the concatenation of $S$ and $T$.

The problem in clearer terms

Given two strings, $A$ and $B$, of equal length $n$, find whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$.

Brute force

For each $i$ in $0, 1, \cdots, n$, we can check if $A[:i]+ B[-(n-i):]$ is a palindrome. This search by brute force runs in $O(n^2)$. Its average time-complexity is $O(n)$ under some reasonable assumptions. It is very easy to implement.

Algorithm in $O(n)$

Let us take a closer look what happens when we get a palindrome. For example,
$$\begin{aligned}
A&=ab12321xy\\
B&=\text{**}5\text{***}4ba\\
C=A[\text{:}7]+B[-2\text{:}]&=ab12321ba\quad \text{which is a palindrome.}
\end{aligned}$$

Note that 12321 in $C$ is a palindrome that sits in the middle of $C$, which is not surprising since the central part of a palindrome is also a palindrome. Since the lengths of $A$ and $B$ are the same, that 12321 should sit in the middle of $A$ as well.

Note the remaining part after $12321$ has been removed, $abba$ is also a palindrome.

The above indicates the following simple algorithm.

Compare the letters at the front of $A$ with the corresponding letters at the behind of $B$ one by one so as to find $i_0$, the largest $i\le n/2$ such that $A[:i]+B[-i:]$ is a palindrome.
Starting from the center of $A$, expand both ways to find the longest palindrome sitting in the central of $A$. Let $c_A$ be its length. If $2i_0 + c_A\ge n$, return yes.
Starting from the center of $B$, expand both ways to find the longest palindrome sitting in the central of $B$. Let $c_B$ be its length. If $2i_0 + c_B\ge n$, return yes.
If we have reached here, return no.

Exercise

Given two strings, $A$ and $B$, devise an $O(n)$ algorithm that determines whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$, $0\le i \le\text{len}(A)$ and $0\le n-i \le\text{len}(B)$.
(This exercise should be easy if you know Manacher's algorithm.)


Can Tarjan's SCC algorithm find satisfying assignment to just 'any' digraph?

You have a faulty premise.  There is a 2SAT instance corresponding to $(a \implies b) \land (b \implies \neg c)$.  Just note that $x \implies y$ is equivalent to $\neg x \lor y$.  Then you can transform the original formula to $(\neg  a \lor b) \land (\neg b \lor \neg c)$, which is obviously a 2SAT instance.

That algorithm you refer to can solve 2SAT, but it can't solve anything stronger as is.  However, there are related graph-based algorithms to test satisfiability of arbitrary conjunctions of Horn clauses.


How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps

A naive solution could be that each general first launch a binary counter in its row and counts the current time until $k\log(k)$ steps and then run the FSSP. To do this you just need to detect the value of $k$ and compute $k\log(k)$ in less than $k\log(k)$ steps: sending a signal back and forth toward the other end while incrementing a binary counter gives you k written in binary in roughly $2k+\log(k)$ steps, so you also know $\log(k)$ (length of the counter). Within the $\Theta(k\log(k))$ steps left you have much more time than necessary to compute the product $k\times \log(k)$. And you're done.

I'm pretty sure that (1) there are more elegant solutions, (2) there is a general acceleration/slowdown theorem that could also be used here.


You are asking two questions, I will answer the second. Parameterized reduction from problem $P$ to $Q$ is a function $\phi$ with the following properties :

$\phi(x)$ can be computed in time  $f (k)·|x|^{O(1)}$, where $k$ is the parameter of $x$,
$\phi(x)$ is a yes-instance of $Q$ if and only if $x$ is a yes-instance of $P$.
If $k$ is the parameter of $x$ and $k′$ is the parameter of $\phi(x)$, then $k′ ≤ g(k)$ for some function $g$.

  Note that $f(k)$ need not to be a polynomial function in $k$, it could be like $2^k$ or $c^k$, where $c$ is constant.

Example: INDEPENDENT-SET instance $(G,K)$ into CLIQUE instance $(G',K)$ is a parameterized reduction. You can verify all three conditions mentioned above.

Reference : http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt3


Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?

Yes, it is possible to do so. Although a given PDA may have $\varepsilon$ loops that can induce infinite computation, we can sidestep this by converting the PDA to a CFG, then back to a PDA (using the standard methods). The second PDA is guaranteed to halt on all inputs (this is not too hard to see if you know the conversion method - essentially you guarantee that either a non-terminal from the CFG is added to the stack, or a terminal is read from the input at each broad step and the nondeterminism takes care of the rest, or equivalently, CFGs can always be parsed).

So then we can take the PDA for $L$, apply this transition, and we get a machine that always halts, and only halts in an accept state if the input is in $L$.


Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

Use a SAT solver that also allows you to express pseudo-Boolean constraints.

Encoding the verification of the existence of the tiling of an NxN grid as a CNF formula is straightforward.  Each grid position will have a set of variables associated with it of which only one will be set true if a particular tile occupies that position.  Add clauses that force exactly one of each set of variables to be set true.  Add other clauses that demand grid neighbors be the correct sort of tile out of the available choices.

The epsilon requirement means requiring that only a fixed number of the grid position variables for each tile type be set true, or that the number set be within a certain range.  This is complicated by the fact that the naive expression of such constraints in CNF takes a number of clauses exponential in the number of variables involved.  There are more efficient encodings that involve adder and comparison circuits, but a solver that accepts pseudo-Boolean constraints directly will either work without such encodings or will save you the trouble of creating these circuit encodings yourself.


Is Green's the best 16-input sorting network so far?

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.


Shift Organization algorithms (Constraint Programming + Marriage problem)

Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.


Memory address of variable after reassignment

"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM.

A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be accessed by other threads. This gives a Java compiler (and a JVM implementation, for that matter) a lot of freedom about what to do with it.

JVM code has two "local" areas where it may store data: the operand stack and the local variable array. If you want to read along, this is covered in section 2.6 of the JVM specification. As the names suggest, the operand stack is organised like a stack (mostly push and pop-type operations), and the local variable array is organised like an array (dereference-type operations).

The JVM is designed so that a compiler can emit code where every local variable has one exactly entry in the local variable array. To use the value, the compiler would emit code to transfer a value from the local variable array to the stack (the instruction is called "load"; there are variants for variables of different types, but we'll ignore this complication for now), and to write a value to the variable, there is a corresponding "store" instruction which transfers a value from the stack to the local variable array. Section 3.2 of the specification covers this.

The reason why the JVM is designed with this in mind is that it allows for very simple compilers. However, this is not the only possible way to generate code for the JVM.

A local variable cannot be accessed by another method (e.g. you can't pass it by reference like you can in C++), or on another thread. So the compiler has a lot of freedom about what it can do with one.

If a variable is extremely short-lived, for example, it may not need an entry in the local variable array. Consider, for example:

for (int i = 0; i < 10; ++i) {
    int x = f(i);
    g(x,x);
}

A simple way of compiling the body of this loop might be something like this.

// x = f(i);
iload i    // push i onto the stack
invoke f   // pop the argument, call f, and then push the return value on the stack
istore x   // pop the stack and store the value in local variable x
// g(x,x);
iload x    // This probably doesn't need to be explained, right?
iload x
invoke g

(Note that this isn't actually JVM bytecode. The JVM uses slot numbers in the bytecode stream, not names, and also has different "invoke" instructions depending on what "f" actually is; it might be a static method, or an interface method, or one of a number of other things. Nonetheless, this should give you the basic idea.)

The variable x doesn't really need to be stored in the local variable array. When this method calls the method f(), the return value is pushed onto the operand stack. Invoking the method g() requires two values to be on the top of the operand stack, representing its arguments. The JVM has an instruction (called "dup") which duplicates the value on the top of the operand stack, so the body of this loop could be compiled as:

iload i
invoke f
dup        // Duplicate the top value on the stack
invoke g

In fact, in this simple example, the compiler may not need to allocate local storage for i, either.

There are lots of other possibilities. The compiler might reuse local storage slots for local variables whose lifetimes don't overlap, or it might assign different locations to the same variable for different parts of the code; this is known as live range splitting. In a sense, the distinction between the operand stack and the local variable array when compiling for the JVM is very like the distinction between registers and the stack when compiling for a physical CPU, and many of the same ideas carry across.

Now, there are a few reasons why a compiler might not want to go to all this trouble.

First off, it can be a lot of work. Optimal register allocation is a formally unsolvable problem, although for some reasonable definitions of "optimal" it's NP-complete. Nonetheless, for stack machines like the JVM, very simple techniques work in practice.

Secondly, chances are good that if this is performance-critical code, it will be JIT-compiled anyway, and so many of these optimisations will be done by that part of the JVM implementation.

Thirdly, it complicates debugging. If a variable can be stored in more than one location, then the debugger needs to know where to find the value any point in the program. If the reason why you're optimising local variable storage is to reduce the size of the class file, chances are good that it won't help, because what you gain in the number of instructions you will probably lose in debugger metadata.

This is one reason why software projects often use "debug builds" during development.

One final thing: I've been talking about basic types like integers here, but one additional complication in optimising the storage of local variables is how it interacts with the garbage collector, since the garbage collector needs to know what heap objects are referred to by local variables.

Garbage collection is a more advanced topic, and you didn't ask about it, so I won't go into the details. It doesn't affect how a Java compiler would compile to JVM bytecode, but it may affect the design of the JVM implementation. Once again, a local variable can't be accessed by other methods or other threads, so this gives the JVM implementation a lot of freedom on how it can let the garbage collector know what is live and what isn't.


Priority queue with ubounded number of elements (i.e., with dynamic storage)

I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it to two-thirds of its size.


Chernoff bound when we only have upper bound of expectation

Yes, we can get a bound like this. To see why, we will need to look a little more closely at how Chernoff bounds are proved.  A relatively standard form of this kind of tail bound would assume that
$$
  X = X_1 + \cdots + X_n
$$
with all $X_i$ independent, discrete, supported in $[-1,1]$, with mean $\mu_i = 0$, variance $\sigma_i^2$.
The resulting tail bound ends up being that:
$$\operatorname{Pr}[X > \lambda\sigma]\le e^{-\lambda^2/4}$$
where $\sigma^2 = \sum_{i\in [n]} \sigma^2_i$ is the variance of $X$ and $\lambda\in[0,2\sigma]$.  (Here is a proof by Van Vu.)

I'm more or less going to first reproduce the proof, so you can get an idea of why decreasing the expectation turns out to be ok.

All Chernoff bounds are based on applying Markov's inequality to $e^{tX}$ to get that $\operatorname{Pr}[X > \lambda\sigma]\le \mathbb{E}[e^{tX}]e^{-t\lambda\sigma}$.  So the general method is to work out $\mathbb{E}[e^{tX}]$ and then optimize $t$.  We can do the MGF computation a little differently from the link, namely as
$$\mathbb{E}[e^{tX}] = \prod_{i\in [n]}\mathbb{E}[e^{tX_i}] \le
\prod_{i\in [n]}\mathbb{E}[(1 + tX_i + t^2X_i^2)]$$
where we first used independence of the $X_i$ and then $e^x\le 1 + x + x^2$ for $x\in [0,1]$.  Under the hypotheses we started with and linearity of expectation,
$$\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t^2\sigma_i^2\le e^{t^2\sigma_i^2}$$
so we get that
$$ \operatorname{Pr}[X > \lambda\sigma] \le e^{t^2\sigma^2 - t\lambda\sigma}$$
With $t = \lambda/2\sigma$ this is what we wanted (and since $t\in[0,1]$, all
the inequalities we used are valid).

Now let's assume that $\mu_i\le 0$ (instead of $= 0$ as before) and otherwise the same set of hypotheses.  Returning to the MGF computation, we get
$$
\mathbb{E}[(1 + tX_i + t^2X_i^2)] = 1 + t\mu_i + t^2\mathbb{E}[X_i^2] = 1 + t\mu_i + t^2\sigma_i^2 + t^2\mu_i^2
$$
Using that $x^2 + x < 0$ for $x\in (-1,0)$, this implies that
$$
\mathbb{E}[(1 + tX_i + t^2X_i^2)] \le 1 + t^2\sigma_i^2
$$
and so we get the same tail bound as before.

Finally, note you always have $\sigma^2_i\le 4$, so $\sigma^2\le 4n$.


How do I apply the Pumping Lemma to prove that this language is not regular?

Assume S is regular.
The pumping lemma says: There is a pumping length n. And if you take any string w in S with length > n, then w contains a non-empty substring in the first n symbols that can be repeated 0, 2, 3, 4, ... times, and the result is in the language. (Why is that? A regular language has a finite state machine. If that state machine has n states, then while you are processing the first n symbols, you must enter one state twice, say the state X. So you could take the symbols that took you from X back to X, and remove them, or duplicate them, or repeat them a million times, and your string would still be in the language). So w = xyz, xy has length ≤ n, y has length ≥ 1, and xz, xyz, xyyyyyyyyyz etc. are all in the language.
Take any string v with length k > n which doesn't end in a. The string w = v a^(7k) is in the language. When we split w into xyz, since the length of xy must be at most n, but v has a length k > n, we actually split into $w = xyz a^{7k}$.
The pumping lemma says that $xy^mz a^{7k}$ is in the language for every y. But for m ≠ 1, 7k is not seven times the length of $xy^mz$ so it is not in the language, therefore S is not regular.


Removing identical variables in CFG Unit Productions

In you example the production A->AA can not be removed. If that production is removed then the language described by the grammar will change. But in case of a production like A->A, the removal will not affect the language described by the Grammar.


Check if adding an edge to a DAG results in a cycle

Kahn's algorithm is known for topological sorting, but it can be used to find strongly connected components as well.  I use it for cycle checking, where an actual topological sort is not needed.  In this variant, nodes are discarded as they are visited, instead of being added to the output, and the error termination indicates at least one cycle.

It works by pruning off root or leaf nodes (having in-degree or out-degree 0 resp.) from the graph one at a time, until no more nodes of that type can be found.  Since this process cannot cut a cycle (all nodes on a cycle have indegree and outdegree > 0), it terminates with a nonempty graph if at least one cycle exists.

If we cut the maximum remaining edge e at each such termination point, we can continue the process to see if E\e still contains a cycle, and so on iteratively until we've cut enough edges to make E acyclic.  The last such edge cut k is the first k that makes E[1...k] cyclic.

Kahn's algorithm does this leaf-cutting process linearly by using a work queue of nodes to be deleted; it is initialized with the leaves of the entire graph (at least one of which must exist, if it's acyclic), and, as each is deleted, its parent node(s) are checked to see they in turn become leaves, and if so they are added to the work queue.  By checking the neighborhood of each deletion, it works linearly through the graph, without the need for indexing structures beyond the FIFO queue.

We can do the same neighbor-leafness check as we cut the maximum edge, and add any leaves created to the work queue, or, if none are created, continue cutting.

In order to make the max-cutting process linear, we have to find the maximum non-deleted edge via a descending scan of the edges array, but each scan starts where the previous left off, and the algorithm only does a single pass through the whole array, so that part is O(E) in total.  Overall I believe this method is O(V+E), the same as Kahn's alone.


An edge that connects more than two nodes in a graph?

When edges connect more than two nodes, you don't have a graph, you have a hypergraph. More precisely, since transitions are oriented (you're starting from a digraph) and there are probability on each transition, you have a weighted hyperdigraph. I'm not sure having this term will help you that much: as data structures go, this isn't that much of a classic.

Transitions with multiple origins rather remind me of Petri nets. If your probabilities are rational numbers and there are no loops, you can scale them to integers. Otherwise you would need to reach for probabilistic Petri nets, I think.


How do I compute this non terminal positions evaluation, for tic-tac-toe?


An algorithm for identifying a fruit with words

Have a look at decision trees.

You might rather quickly see a connection to your problem: think about what you should have at each node of the tree and what at each edge. Then think about what should be at the leaves (or very bottom) of the tree and how that might answer your problem.


I think  this Problem  is same as you asked and i solved this problem using  Treap .


In the PCP, can we remove all dominos with the same top and bottom strings and still get a match?

Intuitively this seems like it would be true at first, but it's because we think too literally about the domino example. Remember in the PCP the strings on the top and bottom of the domino are not necessarily the same length (i.e, the dominos are not necessarily rectangular)
Consider the following example
\begin{align*}
P=\left\{\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right),
\left(\begin{array}[c] \\
2  \\
2  \\
\end{array}  \right),
\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right),
\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)
\right\}
\end{align*}
Here notice there is a match by placing each of the dominos exactly once, and in the order they appear above. On the other had let's try another version.
\begin{align*}
P'=\left\{\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right),
\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right),
\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)
\right\}
\end{align*}
Notice $P'$ was obtained from $P$ by removing $\left(\begin{array}[c] \\
2  \\
2  \\
\end{array}  \right)$, which has the same string on top and bottom.
If there were a match in $P'$ it must start with $\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)$ since that is the only time starting and ending with the same letter that can be added to (there is no tile starting with $2$ on top to place after $\left(\begin{array}[ccc] \\
1 & & \\
1 & 2 & 3 \\
\end{array}  \right)$.
This can be followed by either another $\left(\begin{array}[cc] \\
4 & 4  \\
4 &   \\
\end{array}  \right)$, or $\left(\begin{array}[cc] \\
3 & 2  \\
4 &    \\
\end{array}  \right)$. The first is not helpful, and the second places the substring $32$ on the top, which can never be formed on the bottom. So $P'$ does not have a match.


How to traverse a graph in reverse with dfs

Just take the code for DFS and, every time it says "If there is an edge from $x$ to $y$", replace that with "If there is an edge from $y$ to $x$."


It's unnecessary to perform an LU factorization each time. Instead, you can compute a projection matrix $P$ from your dense matrix. Then, for any vector $x$ in your set, just check if $Px = x$.
In particular, suppose your original dense matrix $A^T$ has all of its rows independent (if it doesn't just delete rows until it does) and you wanted to know if adding any $x$ to the columns of $A$ would increase its rank. Then compute $P = A(A^T A)^{-1} A^T$ once. Here, $P$ projects any vector $x$ onto the column space of $A$, which is the row space of your original dense matrix $A^T$.
Alternatively, you can factor $A = QR$ using either Gram-Schmidt or Householder, in which case you would have $P = QQ^T$.
Then, for every $x$, concatenating it onto the columns of $A$ would increase its rank if and only if $Px \neq x$.


The computational complexity depends on what you want to measure. If you you're doing this computation on a common computer with floating point arithmetic, then you can estimate it mi $O(1)$, because every floating point operation (addition, multiplication and square root) is in $O(1)$.

If you use fixed point arithmetic for $n$-bit numbers, then addition can be done in $O(n)$, multiplication in $O(n^2)$, and square root in $O(n^2)$ steps (Note: For multiplication and addition are existing better bounds). Putting this together, you will add two $O(n)$-bit numbers and take the square root of the result which gives $O(n^2)$ steps.

As you can see, the runtime depends on the arithmetic used, and arithmetic determines what $n$ means. If you use $n$-bit complex number in a $n$ dimensional vector space (where $x^2$ denotes the scalar product), you probably will get other estimates.


Automated lip-reading: inferring what someone is saying, based upon video of them speaking

There appears to be some work in that area. See for example this paper and the references therein. There are also demonstrations of implemented systems on youtube, see for example this video


Why L is defined as L = SPACE$( \log n)$ instead of L = SPACE$(\log^2 n)$ or L = SPACE$(\sqrt n)$?

The complexity class $\mathsf{L}$ satisfies many desirable properties:

It is closed under concatenation and iteration.
The corresponding function class is closed under composition.
The same complexity class is obtained for any number of work tapes.
It is resilient under "reasonable" input transformations with polynomial blowup (see below).
It can accommodate most known NP-hardness reductions.
It is a subset of $\mathsf{P}$.
It supports pointers indexing the input.

What is an input transformation? Consider the case of graphs. We can encode a graph either as an adjacency matrix of as adjacency lists. We can convert between the two in logspace, and so a graph problem which is in $\mathsf{L}$ under one of them is also in $\mathsf{L}$ under the other.

Logspace is the natural space analog of $\mathsf{P}$, considering the containment $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{f(n)})$.

It also shows up in the refined Schaefer's dichotomy theorem, as the lowest non-trivial complexity class.


They are just saying that if $P$ is a shortest path, in $P$ there are not positive cost cycles, since removing the cycle would led to a smaller cost (and so to a better path).

Consider your example and suppose we want the shortest path beween $s$ and $v_k$, let $P=(s,v_1,\color{red}{v_i},\color{red}{v_{i+1}},\color{red}{v_{j-1}},\color{red}{v_i},v_{i+1},v_{j-1},v_{j+1},v_k)$.

Removing the cycle from $P$ we obtain $P'=(s,v_1,v_i,v_{i+1},v_{j-1},v_{j+1},v_k)$ where $cost(P')=cost(P)-6$, so to a better path in terms of cost.


Minimizing transportation cost through a network, multiple source/sinks

This is an instance of the minimum-cost circulation problem.  Replace each vertex $v$ by two vertices $v_\text{in}$,$v_\text{out}$.  Each edge $(u,v)$ is replaced by $(u_\text{out},v_\text{in})$, with capacity (upper bound) given by $c(u,v)$ and lower bound 0.  Then, add an edge $(v_\text{in},v_\text{out})$ with both the lower bound and upper bound set to $s(v)$.

There are polynomial-time algorithms for this problem.


If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

As there are no strings in $\emptyset$, any machine that computes it always rejects, so we can't map Yes-instance of other problems to anything. Similarly for $\Sigma^{\ast}$ there's nothing to map No-instances to.


How to remove a universal quantifier in Lean theorem prover

I've found an answer to the question I've posed. Here are the tactics I've used:

begin
   unfold pw_o,
   intros,
   cases a with h1 h2,
   let h3 : A := x,
   let h4 : (g_o x y → g_o x z) ∧ (g_o z x → g_o y x) := h2 x,
   apply (h4.left h1),
end

I've unfolded pw_o to make the universal quantifier explicit. After I've isolated pw_o y z as a hypothesis, I've replaced all occurrences of w with x. Since h4.left is a function from g_o x y to g_o x z, I've applied it to h1, which is a term of g_o x y, to obtain a term of g_o x z, which was the ultimate goal.


State true or false --> x = Θ(n⁴), y = Θ(n²) therefore x/y = Θ(n²)

It's true.  There are positive constants $c_1$, $c_2$, $c_3$ and $c_4$ such that, for all large enough $n$,
$$c_1n^4 \leq x\leq c_2 n^4 \quad\text{and}\quad c_3n^2\leq y\leq c_4n^2\,.$$  Therefore,
$$\frac{c_1}{c_4}n^2 \leq \frac{x}{y}\leq \frac{c_2}{c_3} n^2\,,$$
i.e., $x/y=\Theta(n^2)$.

By the way, in your argument, you say that $x$ and $y$ are polynomials. That's not necessarily true – for example, we could have $x=n^4+\log n$.


Knapsack problem with diminishing prices

Consider the special case where $V_i\le v_i(s)< V_i+\epsilon$ such that $\epsilon$ is a very small positive constant, then your problem is equivalent to the regular knapsack problem where item $i$ has price/value $V_i$. So your problem is still NP-hard.