This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$.

Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making $S' = S \cup \{x, x - n\}$ for some sufficiently large $x$ and solving your problem to find the $K = 2$ maximum equal subsequence sums. Then iff the answer includes $x$ and $x - n$ there is a subset that sums to $n$ and we efficiently solved the given subset sum problem.


Gradient descent overshoot - why does it diverge?

If you overshoot by 10% you are fine, for example if the solution is 0 and the starting value 1000, you go to -100, +10, -1, +0.1 etc. If you overshoot by 80%, you converge but much smaller. If you overshoot by 110% you go from 1,000 to -1,100, +1,210, -1,331 etc. - divergence.


Verifying execution of code in trustless environment

This is the problem of securely outsourcing computation.  There's lots of work on this problem in the cryptographic literature; if you do a search at [Crypto.SE] and [Security.SE], you should find some references.  Many of the schemes are probabilistic: if you the remote computer cheats, you have some chance of detecting that fact.  I know of two general approaches: one based on cryptographic commitments, and another based on SNARKs. You should be able to turn up papers on  how SNARKs work.


Best problems that are prone to parallelization?

Tasks that are easily parallelizable are sometimes called embarassingly parallel. Straightforward examples are computing fractals like Julia or Mandelbrot sets (since all points are independent of each other) or brute-force searches.

You can find many other examples on the wikipedia page.


Showing that the number of primitive-recursion programs for each function is countably-infinite

I proved that there are infinite number of definitions using the following construction

That works in principle, but be careful about what $f$ is in that term, formally.

  Now the issue is that this is not the only way to construct an infinite number of equivalent definitions

Right you are!

  How can I show that there is a 1−1 correspondence of the set of all primitive recursive definitions with the set of naturals numbers?

You don't have to do this explicitly.
Use that the class of countable sets is closed against taking subsets.


Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?

The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy.

The similarities are obvious, both notations talk about formulas with increasing quantifier complexity. The important distinction is that the polynomial hierarchy talks about bounded quantification, i.e. your space is limited (the witnesses must be of polynomial size). If the quantification is not bounded you have much more power, e.g. a formula for "program $p$ halts on input $x$" can be written in a $\Sigma_1$ form, which means that the halting problem is in the first level of the arithmetical hierarchy.

To avoid confusion the levels of the polynomial hierarchy are actually denoted by $\Sigma_i^p$, however when it is obvious from the context the $p$ is usually omitted. Note that the superscript in $\Sigma_1^1$ means that the quantification is over sets, which puts it above any level in the arithmetical hierarchy with quantification over the naturals.


Adding Big-O and little-o notation to get a little-o

No. You are misusing Landau notation.

$o(f) + O(g) \not\subseteq o(f + g)$ even if $f \in O(g)$. The best you can get is $O(f + g)$. If $g \in o(f)$, you get $o(f)$.
$\log k$ and $\log n$ are incomparable as long as you can not put $k$ and $n$ in some kind of relation.

Assuming that $k \in \omega(1) \cap O(n)$, you can show that both $o(n \log k) \subseteq o(n \log n)$ and $O(n \log (n/k)) \subseteq o(n \log n)$. Then, we would indeed deduce that the proposed algorithm would take $o(n \log n)$ comparisons, contradicting the known lower bound.


You can choose a random threshold $t \leq n$ such that the first $t$ of the first individual is taken and then you take the rest from the other individual, so in your case, if $t = 4$, your new individual is $(3,1,3,2,22,5,5)$.  As Richerby clarifies below, you take the first $t$ elements from the first individual and put the remaining $n-t$ elements in the order they appear in the second individual.

Making sure that you take the correct number is done by simply counting using a hashmap.  Below, correct_count is a map from an element in an individual to the number of times it occurs, ind1 and ind2 are the two individuals you're trying to crossover.

correct_count = {}
for x in ind1:
    correct_count{x} += 1

t = random(n)
new_ind = ind1[0:t]
count = {}
for a in new_ind:
    count{a} += 1
for x in ind2:
    if count{x} != correct_count{x}:
        new_ind.append(x)
        count{x} += 1


Implementing Dynamic Programming Solutions

One easy way to do dynamic programming is memoization -- just do the regular recursion, but store any results computed and reuse them if the same (sub)problem shows up. Recursion is at the very hearth of dynamic programming, what is usually programmed is a careful unrolling of the recursion.


The given answer can't be correct: Just from the last digits it claims that the result of subtracting an odd number from an even number is even.

However, you also made a mistake in your calculation: The 2's complement should be 0111 0001 1111.


Context formal language recognizing even number of 0's and odd number of 1's

This language is, in fact, regular – it is accepted by an automaton with just four states. I suggest that you first figure out what this automaton is and use what you learn to figure out a grammar. In particular, you don't need any context-free "tricks" or techniques.

If you need to, mouse-over the yellow area below to see a more detailed hint for the automaton.

   Think about what data you need to know when you reach the end of the string, in order to decide if your input is in the language. What is the value of that data when you haven't read any input? How do you update that data as you read the input?


Interchangeable role of public/private key pair and encoding/decoding algorithms

Any RSA variant that goes beyond textbook RSA (which is insecure) will probably not have symmetric encryption/decryption.

Examples are RSA + OAEP or RSA used to encrypt an AES key which is used to actually encrypt the message.


3-SUM hardness vs lower bounds on the complexity

The reason we need complexity assumptions like the 3SUM conjecture is that we cannot prove meaningful lower bounds in any non-trivial computational models. Our best lower bounds are in bounded depth models or in monotone models, or use techniques such as diagonalization which usually apply only to somewhat contrived problems. Whereas we have exponential lower bounds on circuit size for circuits of bounded depth and for monotone circuits, the best lower bound for SAT is linear.

Since we cannot prove meaningful lower bounds on interesting problems in unrestricted computation models, we use the paradigm of reductions: assume that a specific problem is hard, and conclude that other problems are hard. The most celebrated example is, of course, the theory of NP-hardness. It is easy to criticize this methodology: the hardness assumptions that we make are sometimes controversial. Things are particularly bad in cryptography, where sometimes the hardness assumption made in a paper is a thinly veiled version of the assumption that the construction suggested in the paper works.

3SUM hardness is not a new assumption, but has recently found new interest in the community. It explains the complexity of the best known algorithms for many different problems. As such, it is coming to be viewed as the analog of NP-hardness for problems inside P. As an added bonus, 3SUM hardness makes much more accurate predictions on the complexity of problems: rather than just stating that an NP-hard problem cannot be solved in polynomial time, 3SUM hardness allows us to determine the best exponents (smallest $\alpha$ such that the problem can be solved in time $O(n^\alpha)$) of certain problems.


Complexity of the problem to determine if a spanning tree exists inside a connected graph

When $k = 2$, this is just the Hamiltonian path problem, which is known to be NP-complete.


From one perspective, a picture is a 2D image, because it has height and width.

But from a machine learning perspective, we can think of a picture as a point in a high-dimensional space.  In particular, suppose we have a greyscale picture that is $m\times n$ pixels, i.e., $m$ pixels wide and $n$ pixels high.  Then there are a total of $mn$ pixels in the image.  Each pixel has a greyscale intensity, which we can think of as a real number in the interval $[0,1]$.  Therefore, we can think of the picture as being a collection of $mn$ real numbers.  In other words, the picture can be treated as a $mn$-dimensional vector -- as an element of $\mathbb{R}^{mn}$.  Thus, any particular picture can be thought of as an element of a high-dimensional space.

The latter perspective arises natural for some machine learning approaches to computer vision, e.g., where we feed the pixels of the image into the machine learning algorithm, where each pixel value is treated as a separate pixel.

(A color image can be thought of as an element of $\mathbb{R}^{3mn}$: for each pixel, we have three numbers, corresponding to the intensity in the red, green, and blue channels.)


Would adding recursive named functions to Simply typed lambda calculus make it Turing complete?

If all you have this definition rule (which doesn't perform any computation), it won't help you. You also need a way to use this definition, like you did in your code example: you implicitly used another language construct, where a definition is available in the next line.

To make things precise, I'll consider a construct which combines a definition with a way to use that definition — a “let … in …” construct (a recursive one, since the function is available while you're defining it).

$$\frac{
  \Gamma, f \colon T \vdash M : T \qquad
  \Gamma, f \colon T \vdash N : T' \qquad
}{
  \Gamma \vdash (\mathtt{let\:} f \colon T = M \mathtt{\:in\:} N) : T'
}$$

From a typing perspective, it doesn't matter whether $T$ is a function type or whether $M$ is an abstraction. These restrictions would ensure that you can find a nice execution semantics (the general rule like phrased above allows recursive definitions like let x : int = x + 1 in x which cannot be usefully evaluated, but you can always define such cases as looping forever).

With this language construct, you do have a Turing-complete language, and you can define a fixpoint combinator (even with the abstraction restriction).

let Y : (int→int)→(int→int)  = λg. g (Y g) in …

$Y$ is a fixpoint combinator over the integers. You can make a similar definition at any type.

You can't make a polymorphic fixpoint combinator. This restriction comes with the simply typed lambda calculus. If you added polymorphism (which in itself does not allow recursive functions, for example System F is normalizing), you could get a polymorphic fixpoint combinator with a suitably generalized recursive let construct.


CFL Closure Properties prove or disprove for the following languages

1) If $L$ is a CFG then assume $S$ is the start symbol of the grammar rules. Then introduce a new start symbol $S' \rightarrow SS\dots SS$ ($k$ times). So if $w \in L^k$ then $w$ can be written as $u_1u_2\dots u_k$ where $S \Rightarrow^* u_1$, $\dots$, $S \Rightarrow^* u_k$ and so $S' \rightarrow SS\dots S \Rightarrow^* u_1u_2\dots u_k$. Now suppose that $S' \Rightarrow w$. Then since $S' \Rightarrow SS\dots S \Rightarrow^* w$, $w$ clearly in $L^k$. Thus, $L^k$ is CF.

2) $L_1 = \{ 0^i | i \in N\}$, $L_2 = \{ 0^i1^j2^k | i,j,k \in N, i=j \ or  \ j=k\}$, $L_3 = \{ 0^i1^j2^k | i,j,k \in N\}$. Clearly $L_1 \subset L_2 \subset L_3$. But $L_2$ is not CFL, so not DCFL.


How is electricity brought to the transistors?

Electrictiy is brought by wires as usual. But electricity involves 2
kinds of characteristics: voltage (in Volts: V) and current (in
Amperes: A).  Transitors and other similar devices come in various
types. The basic idea is that there are three connectors. A reference
connector (ground), and two others. One correspond to a control
circuit and the other to a controlled circuit. The transistor can have
a high or low resistance to current produced by some source, thus
controlling the flow of electricity and the voltage between the ground
and the controlled circuit connector. The state high or low resistance
is fixed by a small current (bipolar transistor) or by a voltage
(triode vacuum tube, field-effect transistor) between the control
connector and the ground.

The ground connector is called the emitter, source or cathode, for
respectively the bipolar transistor, field-effect transistor and
triode. The controlling connector is the base, gate, or grid, and the
controlled connector is the collector, drain or anode.

The idea is that the controlling circuit uses little energy to
transmit a logical signal to a circuit that can carry much more
energy (the product of voltage and intensity). This can regenerate a
distorted signal, and also make it powerful enough to be sent to
several other circuits, or actuate other devices. With appropriate
circuitry it makes for the various logical gates.

The simplest device to understand may the triode, though it is not a
transistor, strictly speaking, but its vacuum tube ancestor. There is a voltage
between cathode and anode, and by heating the cathode, the (negatively charged)
electrons are freed and can be attacted by the anode that has a
positive charge. However, there is the grid in between: if the grid
has a positive voltage, it will atract the electrons even more, and
they will speed through it with enough momentum to go through (most of
them) and reach the anode. But if the grid is charged negatively, it
will create an obstacle that electrons cross with difficulty and
little current will atually go through.  The working of the
field-effect transistor (FET) has some similarity to that, but I am no specialist.


Wikipedia outlines such an example. Consider the coNP-complete problem UNSAT: given a CNF $\varphi$ on $n$ variables, we want to convince the verifier that $\varphi$ is not satisfiable. We arithmetize $\varphi$ to a polynomial $p$ and choose some large prime $q$. Let
$$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$$
The protocol proceeds as follows:

Prover sends verifier a prime $q \in (2^n,2^{n+1})$, and the latter verifies that $q$ is prime.
Prover sends verifier $p(z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(0) + p(1) = 0$, and sends prover a random $r_1$.
Prover sends verifier $p(r_1,z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(r_1,0) + p(r_1,1) = p(r_1)$, and sends prover a random $r_2$.
Eventually, verifier gets $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$, and verifies that it has the correct value by evaluating $p$ directly.

Because the degree of $p$ is small compared to $q$, if the prover is cheating then the verifier will probably catch her (see Wikipedia for the proof, or work it out yourself using the Schwartz-Zippel lemma).


You could smooth the path of the road by fitting a spline to it (or some other curve), with parameters chosen based on the zoom level to ensure that it follows a smooth path on the screen.


What does the complexity class $\mathsf{XP}$ stand for?

There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (parameterized problems are sometimes defined as subsets of $\Sigma^*\times\Pi^*$, classical problems as subsets of $\Sigma^*$). It can be noted that both formulations describe non-uniform XP, while the time bound $O(n^{f(k)})$ refers to uniform XP. In any case, the important difference is that for XP, the exponent of $n$ may depend on the parameter, for FPT it mustn't.

The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.


Issue in comparing classifiers for pattern recognition

There isn't an easy way to do this. In fact a recent paper by Charles Parker explains some of the problems with using ROC curve measurements (there's a friendly overview at my blog - self promotion alert!!). His paper does make some recommendations on the best ways to compare different classifiers, so you will find something useful there.


Suppose you know the list of colors that appear in contiguous parts of an optimal ordering. Then, you can easily find this optimal ordering: simply put as many nodes of the current color in your list as the parent-child order allows and proceed with the next color in your list. This greedy strategy is optimal, because once you have started a color, you will not 'regret' taking a node of the same color later as it adds no cost and only gives more options. If you put all 'free' nodes that already have their parents processed in separate lists, this can be done in $O(n)$, where $n$ is the number of nodes in your forest.

Of course, we do not know this list, so we should figure out how to find it. The number of color lists you would have to check in an uninformed search is $c(c-1)^{k}$, where $c$ is the number of colors you have and $k$ the minimal number of color switches in the final order. If you're lucky, $c$ and $k$ are sufficiently small for a brute-force search and we are done.

However, this will quickly become unfeasible, so I doubt you can afford to spend the $O(c(c-1)^k n)$ time required to do a brute-force search$^1$. Finding an optimal list 'looks hard'. I have no formal proof of e.g. NP-hardness, but it is clear that decisions made early on depend on the structure of the entire forest, so the most natural approach is to try to create subdivisions of by 'cutting' the forest to get subproblems and use e.g. dynamic programming. However, since the nodes can be ordered in many ways, I do not see how to represent these cuts with only polynomially many states. Another hint is that you can see this as a special case of the scheduling problem with partial order requirements.

So, since I think it likely we cannot find an efficient exact solution, you should try an heuristic approach or can perhaps even find an approximation algorithm. I will finish with some observations that may help you in developing such an approach:

If we decide on the last color in list first and build the ordering backwards, observe that we can only choose nodes where all descendants have the same color: if not, there is a node of another color that should be later in the list. Since we would select all children of the same color as a parent if we had chosen a front to back order in an optimal ordering, we should select only subtrees of the same color where the root has no parent of the same color. It is possible that for some colors, there are no such subtrees, which means that we have less options for the final color.
If there is a color for which you can select all remaining nodes, you should select that color. This may occur quite often if the correlation between the color ordering and node ordering is high.
One idea for an heuristic is to select the color that is 'blocking' the most nodes of other colors: you can look at the total number of 'chains' of nodes of the same color that are accessible after removing the color or at the number for a specific color you would like to remove first or the maximum number over all colors.

$^1$: You could be slightly more clever and do recursive backtracking where you can prune some searches, but this has the same worst case running time.


Find longest path by number of edges, excluding cycles

The problem you are defining is called Longest Path (and occasionally Longest $s$-$t$-Path) and is NP-complete.

That is, there is an algorithm for solving it, but you shouldn't keep you hopes up when it comes to the running time of the algorithm: it's unlikely to run in polynomial time.

The trivial algorithm is to check for every permutation of the graph, in time $O(d! \cdot 2^{dn})$, but this becomes intractable extremely quickly.  It is possible to bring this down to $O(2^n \cdot \text{poly}(n))$.

You have three options as far as I can see it:

limit the length of the path you need to some reasonable integer $k$ and solve with FPT techniques
use an approximation algorithm
limit the type of input graph to certain smaller and easier graph classes.

Note 1: As Yuval Filmus points out, the problem Longest Path is usually referring to the undirected version.  However, the problem remains NP-complete also in its directed version by a reduction from Directed Hamiltonian Path (Between Two Vertices) (Garey & Johnson, 1979).

Note 2: Yuval Filmus also pointed out that it is solvable in single-exponential time.

Note 3: The problem is solvable in linear time on DAGs, and if you allow repeating edges, the answer is always infinite when your graph has a cycle.


Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?

"Nothing is always."

Without any prior knowledge, the worst case time-complexity of converting an adjacency matrix representation of a graph in 0,1 values to a corresponding adjacency list representation is $\Theta(n^2)$.

However, if we know the graph is a sparse matrix with number of edges $m=o(n^2)$ and its adjacency matrix is stored in some compressed format like Yale format, then we can expect a conversion takes $o(n^2)$ time.


The asymptotic running time of your algorithm is $O(mn\log n)$, as you mention. If we don't know anything further about $m$ or $n$, there is no way to simplify this. If you know that $m = O(f(n))$, then the running time is also $O(f(n)n\log n)$. For example, if you know that $m = O(\sqrt{n})$, then the running time is also $O(n^{1.5}\log n)$. It will be $O(n\log n)$ only if $m = O(1)$, that is, $m$ is constant.


smn-theorem: Application by instantiating s with other function

I think you are reading it backwards.

Usually you want to find $h$ such that $\varphi_{h(n)}(i) = f(n,i)$, where $f$ is a computable partial function. Further, you want $h$ to be total recursive (or even more: primitive recursive).

In order to prove that such an $h$ exists, as well as to concretely define it, one picks any index $m$ for $f$, so that $\varphi_m = f$, and chooses $h(n) = s(m,n)$.

Note that, when reading the reasoning above in the other direction, it becomes wrong. That is: it is not the case that, since $\varphi_{h(n)}(i) = f(n,i)$ we can conclude $h(n) = s(m,n)$.

Indeed, $h$ may also be another function, like e.g. $h(n) = pad(s(m,n))$ where $pad$ is a padding function (which returns the Gödel number for an equivalent TM, such that said Gödel number is larger). Infinitely other (computable) $h$ exist.


Recurrence relation and time complexity of recursive factorial

Your understanding of how recursive code maps to a recurrence is flawed, and hence the recurrence you've written is "the cost of T(n) is n lots of T(n-1)", which clearly isn't the case in the recursion. There's a single recursive call, and a multiplication of the result.

Assuming the numbers aren't large, the multiplication is constant time, and it's a single operation, not a multiplier on the number of recursive calls:

$$
T(n) = T(n-1) + c_{1}
$$

The base case is $T(1) = c_{2}$

If we simplify things further, and assume $c_{1} = c_{2} = 1$ (it makes no difference to the final asymptotic analysis anyway), you get:

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

And the same final result as the StackOverflow question of $T(n) = n$.


Let me try to help you with.

1) The problem here is that you are missing the big picture. Lamport's Bakery Algorithm (LBA) is just a deadlock-free algorithm that is used for mutual exclusion, so inside a bigger software. One typical way to use it is this (Java-like example):

mutex.lock();
try {
    CS(); // critical section
} finally {
    mutex.unlock(); // mutex has to be released also in case of error
}

For the way LBA is designed it does not allow a thread to "change idea" while waiting (there is no timeout notion in the algorithm): once a thread has called lock() it has to wait until lock() returns (possibly waiting all the other threads' unlock()). This does not mean that a thread is forced to enter in the CS once the lock is acquired. One thread could call lock(), wait until it returns and check if it is still required to run the CS. See below:

mutex.lock();
try {
    if(!tooMuchTimeHasPassed()) {  // is it still meaningful to enter CS?
        CS(); // critical section
    }
} finally {
    mutex.unlock(); // mutex has to be released also in any case
}

The example allow this scenario: one thread acquires the lock, notices that running CS is useless and stops by releasing the lock.

2) The boolean value, as you can see here, is not used to notify other threads about the fact that you have a certain priority or that you are inside the CS: it is only used to say to the other threads that you are still choosing a number. How can some threads decide which of them has the highest priority if some threads have not picked a number yet? In order to acquire the lock one thread A must ensure he has a priority higher then all the others (the outer for loop). If A discovers that another thread B is still searching for a number (the max() operation is not atomic and may require a lot of time) then it waits for B to pick a number and later checks who can go first.

Hope it helped!


Well, let's see. Please point out if I understood the problem model incorrectly.

Suppose we have $n = 5$ elements. Suppose it's sorted in the way $s = [1, 3, 4, 0, 2]$. Then using linear search we are going to with probability $(1/2)^3$ have 2 steps in our search and with probability $(1/2)^4$ have 4 steps in our search.

So, what's the average number of steps we need to find an element giving arbitrary sorting $s$? Let's say $X$ - number of steps needed in our search. Probability to get $X=i$ steps is equivalent to request a search for an element $k \in \{0,1,2,..,n-1\}$ giving we have it at the $i$th position. That is $$P(X = i) = \sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position)P(the\ element\ k\ is\ at\ ith\ position)$$ Then we notice that $P(the\ element\ k\ is\ at \ ith\ position) = \frac{(n-1)!}{n!} = \frac{1}{n}$ because we have an element at a fixed position and $(n-1)!$ possible permutations for other elements out of the total $n!$ possible permutations of our $n$ elements.
Then we notice that $\sum_{k=0}^{n-1} P(search\ for\ k\ |\ the\ element\ k\ is\ at \ ith\ position) = 1$. It means that $P(X=i) = \frac{1}{n}$. So, the expectation is just $\sum_{k=1}^{n} \frac{k}{n} = \frac{n+1}{2}$.

Of course, the second part is much easier to derive, it's just $$E(X|sorted\ in\ decreasing\ probability) = \sum_{k=1}^{n-1} \frac{k}{2^{k}} + \frac{n}{2^{n-1}}$$ (just notice that the elements are going to be from $1$ to $n-1$ and then the element $0$, however $0$ could be the pre-last element because it have same probability as $n-1$). So, we just calculating the expectation of the probability distribution, though this time not for the joint probability but conditional.


How earliest that the data TLB (Translation Lookaside Buffer) can be accessed in an instruction execution pipeline?

Often the effective address is the sum of a small constant and a value from a register. Not always, so this trick does not always apply. The trick then is to make a gamble: access the TLB based on just the value from the register, in parallel with adding the offset to it. Usually the small offset won't change the page being accessed, if that works out then you might have the result from the TLB a cycle earlier. Of course there needs to be a check afterwards to see if the upper bits of the virtual address didn't change, and if it fails the TLB access has to be re-done.

There is even a patent for this, with way more detail: Guess mechanism for faster address calculation in a pipelined microprocessor


Is a physical process with unbounded input Turing equivalent?

No.  You can't just sweep everything under the rug like that.  The answer depends on what model of reality / physics you subscribe to.

If your model of reality is continuous (e.g., Newtonian physics), then it's not necessarily true that that every physical machine is computable by a TM.  TM's are discrete, not continuous; if physics is actually continuous, then your assumption is probably not correct.  (It might be true that the outcome of a process can be computed to an arbitrary degree of accuracy by a TM, but that's a subtly different statement.  TM's compute discrete values, not continuous values.)

If your model of reality is discrete and finite, then it might be true that that every physical machine is computable by a TM.  But now the number of states is not unbounded.

You can't have it both ways.  Or, to put it another way, you can't just assume things without justification.


R-tree insertion procedure when leaf is full

Nope, you are wrong!

In your example, if you keep adding nodes to the leftmost entry, the splits propagate upwards. There will be more levels, but as they propagate upwards, the leafs are always in the same level, thus it always makes a balanced tree, as long as you make sure you follow the insertion and splitting rules tightly (e.g. make sure there are always $m$ minimum objects in a node)


Every problem in NP is decidable. Since determining whether Diophantine equations have solutions is undecidable, it cannot be in NP.  Therefore, although the solution to the equation is a certificate, the size of this certificate is not bounded by any polynomial in the size of the input.


I don't get why the time complexity of insertion on a linked list is O(1)

That is correct. There is no random indexing in a linked list so you will have to traverse it from the start until you reach the right index, requiring a $O(n)$ search. After that you have $O(1)$ reference/pointer bookkeeping for the insertion operation.


If you can represent/model a Conditional IF statement with AND + NOT or OR + NOT

This is partly possible.

Assume your code is

if (a==b)
  x = y;
else
  z = w;

where all vars are ints

This can be rewritten as

c = (a==b) -1 // true 1-1=0; false 0-1=0xfffffffff

x = (~c &  y) | (c & x); // or ~(~(~c&y)&~(c&x)) to only use & and ~
z = (c &  w) | (~c & z);

This can be applied to arbitrarily complex expressions, even nested, but you cannot have function calls, which seriously limits application area.

Note that this is routinely used to program SIMD extensions like SSE or AVX. In SIMD, you do several operations simultaneously and the only way to perform if-then-else if by mean of masking and anding/oring.

Similarly, there is the same problem on a GPU where hundred of processing elements work simultaneoulsy. It is hidden from the user, but internally the controller transforms if-then-else to logic ops. It even keeps track of it across function calls.


I'm quite confused about the convergence of pix2pix cGAN, how can we tell whether my model is well trained?

Create a test set, by taking a subset of the training set (make sure to not train on this test set!). Then evaluate the model against the given labels in the test set.
Also, this trick is very useful generally, since it works for any supervised machine learning model.


Complexity of Hamiltonian path and clique problem

In the clique problem we are required to determine if there exists a clique of a certain size (given as input), so the observation that every clique contains a Hamiltonian path won't help much (a graph $G$ with $n$ vertices may contain cliques of size $<n$, but not have a Hamiltonian path).

$Clique=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k\right\}$

$HPath=\left\{G | \hspace{1mm} G \text{ contains a Hamiltonian path}\right\}$

Since the instances to the problems are not of the same type, it isn't really interesting to talk about their intersection (which is empty), so what you probably have in mind is the set:

$L=\left\{\langle G,k\rangle | \hspace{1mm} G \text{ contains a clique of size }\ge k \land G \text{ contains a Hamiltonian path}\right\}$.

$L$ can be shown to be NP-complete using a simple reduction from $HPath$ (think about how to change the instance to the HPath problem, to an instance of $L$, without ruining the properties of the graph).


Increase-key and decrease-key in a binary min-heap

The reason that your operation is not listed, is that one is not simply interested in all operations that can be easily implemented using a certain data structure, but rather the other way. Given a set of operations, what is the most efficient way (in terms of space and time) to implement these operations. (But I add more to this later)

Binary heaps implement the abstract data structure priority queue, which asks for operations is_empty, add_element (a key with its priority), find_min, and delete_min. More advanced queues also allow one to decrease the priority of the key (in a min_heap) or even increase it. In fact, you have given an implementation.

Two remarks. Your operation is used in the heapify function, that efficiently constructs a heap from an array. In heapify your operation is repeated (starting from the last key).

Then, most importantly, your code uses the position of the node. For the pure data structure priority queue that is cheating. That data structure asks to perform a certain operation given a key. So in order to decrease or increase the priority of an element, you will first have to locate it. I think that is the main reason it is not listed.


You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number of edges and vertices of the graph. The clusters from each connected components are then fusioned to create the resulting clusters.


I can give you the intuition behind Bellman-Ford.  It is beautiful!  I'm going to do it in an indirect way.  I want to share a warm-up puzzle that might seem unrelated, but stay with me.

Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the lock will still open up.  For instance, if the code was 2749, then you  could enter in 32675049, and the lock would open up, because 32675049 contains 2749 as a subsequence.
Challenge: what is the shortest sequence you can come up with, that will guarantee to open the lock?  You could of course enter in each of the $10^4$ possible codes one by one, but that would require you to enter 40,000 digits; can you find a faster way?

Go ahead, see if you can solve it on your own.
Hint:

 Whatever the secret code is, we need it to appear as a subsequence of your chosen sequence.   If we start with 0123456789, we are guaranteed to get at last one digit into the code.  Can you take it from there?

Hint:

 You should be able to find a sequence of length 40 that suffices.

Really, I want you to solve it yourself!  It'll be rewarding and help you understand Bellman-Ford.

Now back to Bellman-Ford.  Let's consider a graph with no negative cycles, but where edge distances can be positive or negative.  The relax operation has an interesting property:

Suppose the shortest path from $s=v_1$ to
$v_n$ is via the path  $v_1 \to v_2 \to \cdots \to v_{n-1} \to v_n$.  If we do some sequence of relax operations, that includes Relax($v_1,v_2$), Relax($v_2,v_3$), ..., Relax($v_{n-1},v_n$) as a subsequence, then $d[v_n]$ will hold the correct distance from $s$ to $v_n$.

In other words, this refers to a sequence of relax operations where we do some relaxes, then Relax($v_1,v_2$), then relax on some other edges, then Relax($v_2,v_3$), then relax on some more edges, and so on.  The property holds no matter what other relax operations you do in the middle -- you can add as many extra relax operations  in the middle anywhere you want and they won't do any harm.
Moreover, once $d[v_n]$ gets set to the correct value, it stays correct forever.
So if our goal is to come up with the correct distance in $d[v_n]$, we can think of that as a digital door lock   like the one above: there is some secret code (the code is a sequence of edges, namely, $(v_1,v_2),\dots,(v_{n-1},v_n)$) that is not known to us, but if we do a sequence of relax operations on some sequence of edges, and if the secret code appears as a subsequence in there, then the lock will open  (i.e.,, $d[v_n]$ will get set to the correct distance), and will stay open forever after (i.e., $d[v_n]$ will hold the correct value from there on).
So this is just like the digital door lock puzzle above!  The challenge is to construct a sequence of edges, so that if we relax edges in that sequence, it'll surely include the code (the shortest path) as a subsequence.  Now you can verify that the sequence of edge relaxations done by Bellman-Ford exactly matches the solution to the digital door lock puzzle above.
I'll let you prove the property I mentioned above.  It follows from the two lemmas you quoted.


Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?

For convenience of description, we consider the problem as a coloring problem where vertices in $V_1$ are colored red and vertices in $V_2$ are colored blue.

The following is a reduction from 3SAT.

For any instance of 3SAT with $n$ variables (assume $n\ge 4$ without loss of generality), construct a complete graph of $2n$ vertices $V=\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ where $v_i^0, v_i^1$ respectively represent the positive and negative literals of the $i$th variable. We also add some additional structures. Note that only named vertices can be in more than one structure.

For each $i$, add the following structure (note I emit the edges among named vertices and the same below):

This structure ensures all the unnamed vertices are colored red, and at least one of $v_i^0$ and $v_i^1$ must be colored red.
For each clause $l_1\vee l_2\vee l_3$, say their corresponding vertices are $u,v,w\in V$, add the following structure:

This structure ensures all the unnamed vertices are colored red, and at least one of $u,v,w$ must be colored red.
For each $i$, for each pair of vertices $\{u,v\}\subseteq V$, add the following structure:

If both $v_i^0$ and $v_i^1$ are colored red, then all the unnamed vertices must be colored red, and at least one of $u$ and $v$ are colored red. Note this holds for all pairs $\{u,v\}$, so if both $v_i^0$ and $v_i^1$ are colored red, there are at most one vertex colored blue, which is impossible. As a result, this structure ensures at least one of $v_i^0$ and $v_i^1$ is colored blue. Combined with the first type of structures, it is ensured that $v_i^0$ and $v_i^1$ are colored different colors.

Now if there is a proper coloring, exactly one of $v_i^0$ and $v_i^1$ is colored red. If it is $v_i^0$, assign the $i$th variable 1, otherwise 0, then the assignment is a valid assignment for the 3SAT instance.

On the other hand, if there is a valid assignment for the 3SAT instance, color $v_i^0$ red and $v_i^1$ blue if the $i$th variable is assigned 1, otherwise color $v_i^0$ blue and $v_i^1$ red. Note the subgraph induced by $\{v_1^0, v_1^1, \ldots, v_n^0, v_n^1\}$ is a complete graph, this is a legal coloring. All unnamed vertices in the first two kinds of structures are colored red, and for a structure of the third type, if both $u$ and $v$ are colored blue, color all the three unnamed vertices blue, otherwise color them red. This is a proper coloring. Q.E.D.


Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Yes, there are such proofs. They are based on the Low Basis Theorem.

See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? question on cstheory for more.


How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases.

Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$,
express $n$ as a sum of $d_i$:s with as few coins as possible.

A naive approach is to use the largest possible coin first,
and greedily produce such a sum.

For instance, the coins with value $6$, $5$ and $1$
will give correct answers with greedy for all numbers between $1$ and $14$
except for the number $10 = 6+1+1+1+1 = 5+5$.


Proof (by contradiction) of the emptiness problem

$M_1$ rejects everything, including $w$, unless $M$ accepts it (crucial). $M_1$ will then be a machine that always rejects, if and only if $M$ rejects $w$.
The white box treats $M$ and $w$ as constants. They are still something that $S$ received as input, and we know that.
$R$ is a hypothetical machine that decides if its input is a machine that always rejects.
$S$ will receive unknown $\langle M,w \rangle$ as its input. Should $R$ work as intended, then $S$ in fact solves the general problem of deciding if $M$ accepts $w$, which is exactly $A_{TM}$.
It has been proven that $A_{TM}$ is not decidable.

Therefore,

$R$ cannot exist.
Our reference question has more information on the subject. You may find particularly interesting to see how this kind of proof can be generalized (look for Rice's theorem).


Your version of the TSP is actually NP-hard, exactly for the reasons you state. It is hard to check that it is the correct solution. The version of the TSP that is NP-complete is the decision version of the problem (quoting Wikipedia):

  The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems.

In other words, instead of asking "What is the shortest possible route through the TSP graph?", we're asking "Is there a route through the TSP graph that fits within my budget?".


Suppose without loss of generality that there is one source $\emptyset$ and one sink $S$. For each node $v$ in your digraph, you can compute recursively the number $N_v$ of unique maximum length paths from $\emptyset$ to $v$: at $\emptyset$ we have $N_\emptyset = 1$, and at other points, $N_v = \sum_u N_u$, where the sum goes over all immediate predecessors of $u$.

This suggests the following encoding for maximal paths at a node $v$. Suppose the immediate predecessors of $v$ are $u_1,\ldots,u_k$, in some arbitrary but fixed order. We will encode all paths as numbers in the range $[0,N_v)$ ($=\{0,\ldots,N_v-1\}$) in the following way: all paths through $u_1$ will be encoded in $[0,N_{u_1})$, all paths through $u_2$ will be encoded in $[N_{u_1},N_{u_1}+N_{u_2})$, and so on. Inside each interval, we apply the same encoding scheme recursively. By applying this scheme for $v = S$ (the sink), we get an efficient encoding system for all maximal paths.


Is SAT a single language or a union of languages?

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turing machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th symbol turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

Note. The way a machine encodes the input can have a big effect on its time and place complexity note the adjacency lists and adjacency matrices representations of graphs.


Linked List in Maximal Scoring Subsequences Algorithm

What element would operate as the head of the linked list in this case?

That's of course $L_{k-1}$.

If you are surprised why this works in $O(n)$, that paper has already explained:

  Once a list element has been by-passed by this chain, it will be examined again only if it is being deleted from the list, either in Step 2 or Step 4. The work done in the “reconsider” loop of Step 4 can be amortized over the list item(s) being deleted. Hence, in effect, each list item is examined a bounded number of times, and the total running time is linear.

Let's consider the example given in the paper. The sequence is $(4, -5, 3, -3, 1, 2, -2, 2, -2, 1, 5)$. The list is initially empty. The first subsequence $(4)$ comes, we keep a pointer to the head of the list, like

H <- (4)

Next, we sWe add it to the end of the list. We search $I_1$ and find $L_1>L_2$, so we keep a pointer to the head, like

H <- (4)  (3)
^         /
 \       /
  -------

Next, we skip $-3$ and the subsequence $(1)$ comes. We search $I_2$ and find $L_2=L_3$. Since $I_2$ points to the head, we assert there is no such $j$ such that $L_j<L_3$ and keep a pointer to the head, like

H <- (4)  (3)  (1)
^         /    /
 \       /    /
  ------------

Next, the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3<R_4$, so we apply step 4 and get (note $I_3$ need to be reconsidered after merging while no change is needed here since it points to the head)

H <- (4)  (3)  (1,2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3=R_4$, so we keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(1)$ comes. We search $I_4$ and find $L_4=L_5$, then search $I_3$ and find $L_3<L_5, R_3>R_5$. We keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)  (1)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Next, the last subsequence $(5)$ comes. We search $I_5$ and find $L_5<L_6, R_5<R_6$, then we merge $I_5$ and $I_6$ and get

H <- (4)  (3)  (1,2) <- (2)  (1,5)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Note $I_5$ needs to be reconsidered. Since $I_5$ points to $I_3$, we search $I_3$ first and find $L_3<L_5, R_3<R_5$, so we merge $I_3,I_4,I_5$ and get

H <- (4)  (3)  (1,2,−2,2,−2,1,5)
^         /    /
 \       /    /
  ------------

We then reconsider $I_3$ and no change is needed since it points to the head.


Yuval's comment is correct. When the flag is set, the processor executes one instruction and then issues a trap (i.e. an interrupt), which is typically caught by the operating system.
The purpose is to help with debugging.
Programmers who are debugging their software want to set breakpoints at specific locations. This can be implemented using a variety of mechanisms, including the processor's debug registers, modifying code (i.e. overwriting an instruction with another instruction which causes a trap; the single-byte INT3 instruction on x86 is for precisely this purpose), or through the virtual memory system (i.e. marking a page in such a way that executing code in that area causes a page fault).
From the earliest days, another desired feature is single-step debugging, where the processor executes one instruction at a time and then returns control to the debugger. Many early CPUs would actually let you stop and "toggle" the processor clock to support single-stepping, but this required additional specialised hardware to make use of it which would add to the cost of a home machine.
Hence, the trace flag.
As a final note, I'm not surprised at all that you didn't know this. Very little attention is paid these days to the kind of support needed by both the CPU and OS to implement a debugger. Code modification, for example, interferes with the instruction pipeline on modern superscalar CPUs, so some extra circuitry is needed to make techniques like INT3 work.


What is fastest algorithm for factoring out square from number

Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.


State complexity of homomorphisms of regular languages

Here is a simple construction that disproves your conjecture.

Let $a,b$ two relatively prime integers. It is known that the largest integer that cannot be represented as a non-negative integer combination of $a,b$ is $ab-a-b$.

Consider now the language $L = (0+1)^*$ and the homomorphism $h$ given by $h(0) = 0^a$ and $h(1) = 0^b$. Then $L$ is accepted by a one-state DFA, while $h(L)$ requires $ab-a-b+1$ states.


Running time analysis of a linear algorithm seems to me quadratic

Inner while loop will be executed at most $L$ times, where $L$ is number of integers that will be added to stack $A$, and it will be at most $N$ pushes to stack, because A.push(i) is called in outer for loop, so body of inner while loop (A.pop()) will be executed at most $N$ times.


Proving the given language isn't context free using Pumping Lemma

The pumping segments $v$ and $x$ can be anywhere in the string assuming they are at most $n$ apart, i.e., $|vwx|\le n$. Like you I get five possibilities, but I think you wrote some special cases rather than the general picture.

Inside one of the $a$-segments, for instance :

the first $u=a^i$, $vwx=a^j$, $y=a^{n-i-j}ba^nba^n$ where $i+j\le n$ and $j\ge 1$. Or
the second $u=a^nba^i$, $vwx=a^j$, $y=a^{n-i-j}ba^n$ where $i+j\le n$ and $j\ge 1$. Or
the third $\dots$ .

Or overlapping with one of the $b$'s. Of course because of the lengths we cannot overlap with both $b$'s.

First: $u=a^{n-i}$, $vwx=a^iba^j$, $y=a^{n-j}ba^n$ where $0\le i,j\le n$, $i+j< n$ .
Second $\dots$ .

However this does not solve the pumping problem. Note we repeat the strings $v,x$ when pumping. In these last cases we do not know how $v,x$ look. Do they contain the $b$? More cases.

A shortcut to the proof would be to make the following observation.

The pumping segments cannot contain $b$.

That leaves five cases for the position of $v$, $x$ in the three $a$-segments. Either deal with them or argue

Now that $v$, $x$ can only contain $a$'s we can pump either one or two of the three $a$-segments in $z$. That means after pumping they cannot all contain the same number of $a$'s


What information do we get from a compiler's parse tree?

Prelude It might be useful to be pedantic and start with a surprising fact: compilers do  not use context free grammars, contrary to what you've been told. Instead they use  something closely related but subtly different, which might be termed context-free transducers (please let me know if there's an official name for it). They relate to context free grammars as Mealy-machines do to finite state machines.

The reason why CFGs are not used is that CFGs only give a yes/no answer. That's not enough for the subsequent stages of a compiler. Instead, subsequent stages need a good representation of the input program to work with. This representation is the abstract syntax tree (AST). Something similar happens in lexical analysis: contrary to what most compiler courses tell you, the lexer does not use a finite state machine or regular expression to nail down the lexical structure of a language, because regular expressions and finite state machines also only give a yes/no answer. We want the output of the lexical stage to be a token-list for consumption by the parser. Mealy machines deliver token lists.

If this is the case, why do compiler courses usually use regular expressions and finite state machines for the lexical analysis and CFGs for parsing? Do compiler teachers lie to us? No, they want to help us understand:

The concepts are really similar, e.g. a Mealy machine is just a finite state machine where every transition carries not just an input action (as they do with finite state machines) but also a corresponding output action. Likewise context free transducers are just CFGs where every production is also associated with an output.
Teachers don't want to be overly formal, and expect the students to bridge the gap between
finite state machines and lexer / CFG and parser themselves. In practise students almost always do.

Main point. With  this pedantic caveat we can come to the original question: what is the parse tree used for?

The parse tree contains the
 "how a string is in the CFG". The parse tree is used to construct the abstract syntax tree (AST) which is a concise representation of the program that is used by later phases in the compiler, in particular the type checker (for statically typed languages) and the code generator. The advantage of ASTs over other program representations such as strings is that ASTs make access to the immediate sub-programs of a program easy, e.g. the program

if C then P else Q

has three immediate sub-programs namely C, P and Q. The AST for the program has three pointers to the sub-programs:

Both, code-generation and type-checking, involve the recursive invocation of code-generation/type-checker on the immediate sub-programs (plus some glue-code). Hence ASTs provide exactly the information needed for efficient type-checking and code generation.

The relationship between parse trees and ASTs is simple.
The parse tree contains the exact information about how a string 'fits' into the CFG. Every production applied when consuming the input string is noted down in the order used. This
information has a natural tree shape, whence the name "parse tree". An AST is a parse-tree with redundant information removed. An example of redundant information are properly balanced brackets. Another example is the node labelling that
gives the aforementioned information about what productions were used to derive the string. Such information
is important for checking if the input string (or more precisely token-list)
is syntactically valid, but once that has been acertained, this information is no longer
needed for compilation and hence discarded.

Let us look at an example. Consider the arithmetic expression $4 *(3+17)$ in the obvious grammar of arithmetic expressions:
$$
   E \ \ \rightarrow\ \ E + E \ |\ E * E \ |\ ( E ) \ |\ 0 \ |\ 1 \ |\ 2 \ |\ ...
$$
Let's ignore the ambiguity and left-recursion in that grammar. Here is a plausible parse tree for $4 *(3+17)$

(Note that the parse tree is usually not constructed explicitly, but is implicity in the structure of the recursion throughout the parsing process.)
The corresponding AST is simpler, but still contains all relevant information, including
precedence of the addition over the multiplication, in its pointer structure:

Summary: compilers construct ASTs (good representation of the program for future compiler stages) from parse trees (which tell "how" the program is in the CFG).


Need help understanding this optimization problem on graphs

You can think of the parent sets as incident nodes; that is if $V_i$ is in the parent set of $V_j$, there is a (directed) edge from $V_i$ to $V_j$.

An ordering "consistent" with this graph in the sense of the exercise is a topological sorting, that is a topological ordering $V_{\pi(1)}, \dots, V_{\pi(n)}$ has no pair $(i,j)$ with $i<j$ so that there is an edge from $V_{\pi(j)}$ to $V_{\pi(i)}$.

The problem is then to find an ordering as consistent with the graph as possible.


Find the k length path that maximize a node associate metric

A brute-force approach is to do a backtracking search starting from $s$.  Something like:
Search($s$, $n$, $S$):

If $n=1$, yield $S \cup \{s\}$ and return.  Otherwise:

For each vertex $v$ that is adjacent to $s$, do:
a. Call Search($v$, $n-1$, $S \cup \{s\}$).

If you invoke Search($vs$, $10$, $\emptyset$), this will generate all possible sets of vertices that can arise from a path of length 10; now calculate the cost of each such subset, and keep the largest one.
$6^{10}$ is about 60 million, so this might complete within a few seconds on most graphs.


If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?

Your idea is correct.

You should take the following path to formally write it up/prove it. First assume that $L$ is accepted by some DEA $M=(Q,\Sigma,\delta,q_0,F)$ then define a new NEA $M'=(Q',\Sigma,\delta',q'_0,F')$ based on $M$. Just express you ideas formally, for example start with

$Q'=Q\cup\{q_\text{new1},q_\text{new2}\}$,
$F'=\{q_\text{new2}\}$,
....

Then you should prove, using the acceptance criteria for $M$ and $M'$, that $w\in L(M) \iff wv\in L(M')$, for all $v\in \Sigma^2$.

Alternative approach

The following idea will also prove the statement but results in an easier proof. First show that the language of words with exactly two characters is regular, and then argue with the closure properties for regular languages.


What real-world computer languages cannot be described by deterministic grammars?

Yes.  Many modern programming languages have this property, including Algol 60, C, and C++; see below for details.

Algol 60 famously had the dangling else problem, for some programs, it was ambiguous how they should be parsed (what parse tree should be result).

Many modern languages resolve this by picking a grammar that resolves the ambiguity in a particular way.  However, this requires carefully constructing the grammar to eliminate ambiguity.  Often the most natural way to write the grammar leads to a grammar that is ambiguous, and you have to transform the grammar to avoid the ambiguity.

Another approach is to use a GLR parser, which can handle these grammars.  Then you can check at runtime whether there are multiple possible parsers, and resolve the ambiguity.

Another classic example is the C and C++ programming languages.  The reference grammar for C is not context-free, because when you see a name, you need to know whether it is the name of a type or of a variable to know how to parse the statement.  For instance, consider the expression

(A)*B

If A is a variable, this is the multiplication of two variables and is equivalent to A*B.  However, if A is the name of a type, then this is a pointer dereference and type-cast (so B is a variable name that holds a pointer type), and equivalent to (A) *B.

Similarly,

A*B;

could be either a variable declaration (if A is the name of a type, this is declaring a variable named B whose type is pointer-to-A) or a multiplication (if A and B are the names of variables).

Compilers typically fix this by including extra code that "goes outside" the language of pure context-free grammars.  They keep track of all variable names and type names in scope, and use this to guide parsing in case of this ambiguity.  See the lexer hack.

See also LL and LR in Context: Why Parsing Tools Are Hard and Bison's manual pages on its GLR parser (which includes a discussion of another ambiguous case in the C++ grammar).

Lastly: I think the question has some confusion about the difference between ambiguity vs non-determinism.  Automata and languages can be deterministic/non-deterministic, but not grammars.  Grammars and languages can be ambiguous/unambiguous.   See Are there inherently ambiguous and deterministic context-free languages? and Grammatical characterization of deterministic context-free languages and If a parser can parse a non-deterministic grammar, is the parser non-deterministic?.  The above examples actually qualify both as ambiguous grammars and non-deterministic languages.


Deterministic query complexity and polynomial degree

According to Table 2 in Aaronson, Ben-David and Kothari, the best separation between degree $\deg f$ and decision tree complexity $D(f)$ is $D(f) = \Omega(\deg f)^2)$, achieved by Göös, Pitassi and Watson, and the best upper bound is $D(f) = O((\deg f)^3)$ (perhaps already from the classic work of Nisan and Szegedy).


What are the differences between the set of Real Numbers and the Java datatype float?

The set of double precision floating point numbers in Java has the following elements:
Integers from 1 to $2^{53}-1$, multiplied by $2^e$ for integers e in some fixed range (which I am too lazy to look up right now).
+Infinity and -Infinity
+NaN and -NaN
+0 and -0.
The last six are not real numbers (+0 and -0 are both similar, but not quite the same as the real number 0).
Real numbers which are not Java floating-point numbers are 0, those numbers that are either too large or too small, requiring an integer e outside the allowable range, those that are not integer multiples of a power of two, and those that are integer multiples of a power of two with an integer > $2^{53}$.


Obtaining a recurrence from a rational generating function

Suppose that
$$ G(x) = \sum_{n=0}^\infty g_n x^n. $$
Using the given equation (ending at $i_m$, a better choice of variables), we have
$$
1 = (1-x^{i_1}-\cdots-x^{i_m}) G(x) =
\sum_{n=0}^\infty (1-x^{i_1}-\cdots-x^{i_m}) g_n x^n = \\
\sum_{n=0}^\infty g_n x^n - \sum_{n=i_1}^\infty g_{n-i_1} x^n - \cdots - \sum_{n=i_m}^\infty g_{n-i_m} x^n = \\
\sum_{n=i_m}^\infty (g_n - g_{n-i_1} - \cdots - g_{n-i_m}) x^n - H(x),
$$
where $\deg H(x) < i_m$. Comparing coefficients, we find out that for $n \geq i_m$,
$$ g_n = g_{n-i_1} + \cdots + g_{n-i_m}. $$

More generally, you could have allowed coefficients in front of the monomials.


No, you still consume one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol.

Here's a simple example: the grammar of context-free grammars. Informally, a CFG is a sequence of productions, where each production consists of a non-terminal, the derives symbol ($\to$) and a replacement list, which is a possibly-empty sequence of non-terminal and terminal. Formally, we have

$$\begin{align}
Grammar &\to \lambda \\
Grammar &\to Nonterminal \ Arrow \ Derivation \ Grammar \\
Derivation &\to \lambda \\
Derivation &\to Nonterminal \ Derivation \\
Derivation &\to Terminal \ Derivation \\
\end{align}$$

That's not an LL(1) grammar, because when $Derivation$ is on top of the stack and the next input symbol is $Nonterminal$, then there are two possible actions:

Predict $Derivation \to \lambda$, which means popping the $Derivation$ off the stack without consuming the input token.
Predict $Derivation \to Nonterminal Derivation$, which means popping the $Derivation$ off the stack and replacing it with $Derivation \  Nonterminal$; then matching the $Nonterminal$ from the input and the $Nonterminal$ on top of the stack, discarding both.

How can the parser decide which action to take? If it can only see one input symbol, then it has no way to decide. But if it can see 2 input symbols, then it can choose action 1 if the second next input symbol is $Arrow$ and action 2 in any other case.

So we can conclude that our grammar for grammars is LL(2).


How to efficiently use an AVL tree to store partial sums?

Instead of storing the whole $i_{th}$ sum in each node, just store the partial sum of the left sub tree.


How to apply Arden's theory to determine a regular expression

Arden's theorem states that $A^*\,B$ is the least fixed point of the equation:
$$ X = A\,X\,\cup B$$
and that $A\,B^*$ is the least fixed point of the equation:
$$X = X\,B\,\cup A$$
In your case, $R = Q\,P^* = a^* (a b)^*$.


The word routine is used here in its non-technical sense: normal, usual, plain. It just means a proof by induction where nothing special happens.


Dijkstra has running time $\mathcal{T}(G) \in \Theta(|E| + |V| \log |V|)$. If the graph is dense then $|E| \in \Theta(|V|^2)$, which means that $\mathcal{T}(G) \in \Theta(|V|^2)$.

A quadratic running time means that a graph with twice as much nodes will take four times as much time to be processed. If $1000$ nodes required $6$ hours, then it is not surprising that $2000$ nodes will take about one day.

As you know, constants depend on the machine you're running your code on, it is therefore impossible to judge the speed of your code having the clock running time as the only datum; however your times strike me as particularly high for a reasonably modern personal computer, I would expect them to be a couple of orders of magnitude lower.


Algorithm to build tri-nodes in MapleStory

Problems (a),(b),(c) can be solved in polynomial time; simply enumerate all possible ways of choosing a subset of 6 cards and test each subset to see whether it satisfies all of the constraints.
If you care about a practical algorithm, I would suggest using a SAT solver.  It is easy to express this problem as an instance of SAT.  Use boolean variable $x_i$ to represent whether the $i$th card in the deck is chosen or not.  Then you can write boolean constraints that express each of your constraints.  I suggest using an off-the-shelf solver like Z3 to solve this instance of SAT; they will tell you whether any solution exists, and if so, give you one example.  If you want to find all solutions, look up algorithms to find all satisfying instances to SAT.
Problems (d),(e) are more challenging but can also be solved in the same way.  Iterate over $m=5,4,3,\dots$ and for each $m$ use a SAT solver to test whether there exists a solution for that value of $m$.  There are at most 120 different cards, so you can imagine having a deck and a sidebar of all the other cards not in the deck; let $x_i$ represent whether the $i$th card in the deck is chosen, and $y_i$ represent whether the $i$th card in the sidebar is chosen, and express as an instance of SAT.


Storing the output requires roughly $n|x|$ bits (where $|x|$ is the size of $x$ in bits); this is since the numbers involved have magnitude $\Theta(x^n)$. This is all that Horner's method requires, since it only keeps track of one value, the current "partial sum".

In contrast, the naive method keeps track of two values: the current partial sum, and also the current power of $x$. Each of these requires (towards the end of the process) roughly $n|x|$ bits to store, and both of them require $2n|x|$ bits in total.


Why does memory data isn't organized in two or more lines?

The notion of a "line" is an abstraction we impose.  Currently our memory works as follows: you provide an address to the memory module that you want to read, and it returns the value at that address; or if you want to update memory, you provide an address and the new value, and it overwrites the value at that address with the new value.
Why do we build memory that way?  Well, the current way is simple and works, and can be implemented efficiently in circuits.  If you wanted to consider some other alternative, you'd have to think about what are the benefits and what are the costs.  I'm not clear on exactly how your counter-proposal would work, but I expect it would add complexity (which ultimately might add to the cost of implement the memory subsystem, and also might make the system harder to understand for programmers) without a benefit that would make it worthwhile.  If you wanted to dive into this in more detail, you'd probably start by learning how RAM works at the circuit level.  Our current RAM is highly optimized to minimize the number of gates needed, i.e., to minimize cost.


Initial temperature in simulated annealing algorithm

As noted by Thomas Klimpel in the comments, a certain acceptance probability is often used, which is equal to say $0.8$. The following is a simple iterative method to find a suitable initial temperature, proposed by Ben-Ameur in 2004 [1]. In the following, $t$ is a strictly positive transition, $\max_t$ and $\min_t$ are the states after and before the transition, $\delta_t$ the cost difference $E_{\max_t} - E_{\min_t}$ and $\pi_{\min_t} \dfrac{1}{|N(\min_t)|}$ the probability to generate a transition $t$ when the energy states are distributed in conformance with the stationary distribution

$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)}$$, where $N(i)$ denotes the set of neighbors of $i$.

Finally, $\text{exp}(-\delta_t/T)$ is the probability of accepting a positive transition $t$. Now, we can have an estimation $\hat{\chi}$ of the acceptance probability $\chi(T)$  based on a "random" set $S$ of positive transitions:

\begin{eqnarray}
\hat{\chi}(T) &=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|} \text{exp}(- \delta_t / T)}{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|}} \\
 &=& \dfrac{ \sum_{t \in S} \text{exp}(- E_{\max_t} / T) }{ \sum_{t \in S} \text{exp}(- E_{\min_t} / T) }.
\end{eqnarray}

We want to find a temperature $T_0$ such that $\chi(T_0) = \chi_0$, where $\chi_0 \in ] 0,1 [$ is the acceptance probability we desire.

$T_0$ is computed by an iterative method. Some states and a neighbor for each state is generated. This gives us a set of transitions $S$. The energies $E_{\max_t}$ and $E_{\min_t}$ corresponding with the states of the subset $S$ are stored. Then a value for $T_1$ is chosen, which can be any positive value. $T_0$ is then found with the recursive formula

$$T_{n+1} = T_n \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{1/p}$$, where $p$ is a real number $\geq 1$.

When $\hat{\chi}(T_n)$ gets close to $\chi_0$ we can stop. $T_n$ is now a good approximation of the wanted initial temperature $T_0$. For more explantion, proofs and discussion, please see the first section of the original paper [1].

[1] Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.


Why are not all recursive languages undecidable?

You are correct. The problem of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable.

Do not mistake a language for its class! Telling whether $L$ is in a class is definitely not the same as deciding membership in $L$.


How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$

The special case where $v=0$  and $Y=\{\frac12\sum_{i=1}^m x_i\}$ is the partition problem, which is NP-complete.


It is not clear what is your question, but I will guess that it is "what is my mistake in my proof of $P = NP$?"
In addition to the fact that the algorithm does not guarantee to find the minimal path (because the algorithm cant deterministicaly choose the endMem nodes), the number of possible $\log n$-walks given $\log n$ nodes is not polynomial: $(\log n)! \sim \left(\frac{\log n}{e}\right)^{\log n}\sqrt{2\pi\log n}\sim \frac{\sqrt{2\pi\log n}}{n}e^{\log n \log \log n}\sim \sqrt{2\pi\log n}\times n^{\log\log n - 1}$.
As for the space complexity, to check there are no overlap between two $\log n$-walks, you need to keep track of the whole path (and not only two consecutive $\log n$-walks). That needs $\Omega(n\log n)$ space ($n$ nodes with a binary encoding of size $\log n$). So the corresponding Turing Machine use polynomial space, not logarithmic space.


Does the concept of the array pre-date physical computer memory implementations?

Here's a thought. Consider the venerable spreadsheet. No, not the program, but the piece of paper. It was a regular array of cells, with column and row check sums and corner balancing for verification. They were used to hold accounting data back in the days when this was done by hand.

While not data in memory, it does embody the concept of a regular array of data.

I can't find a date on the use of paper spreadsheets, but I did find this:

  However, the spreadsheet has been in existence, as a paper based
  product, for longer than any of the computer based products. In the UK
  it was called “Multi-column analysis paper”. In the USA it was called
  a “spreadsheet” hence the name of the computer based version.

http://www.bygsoftware.com/Excel/Standards/SS_801_spreadsheetsbriefhistory.htm


What is average number of cycles in an undirected ordered graph of size n?

Hint: Suppose that there are $Z_m$ cycles of length $m$, and that $p_m$ is the probability that a specific cycle of length $m$ is in the graph. Then the expected number of cycles is
$$ \sum_{m=3}^n Z_m p_m $$
due to linearity of expectation.

Here is the entire calculation. In the $G(n,p)$ model, in which each edge is present with probability $p$ independently, clearly $p_m = p^m$. The number of ordered $m$-tuples of points is $n!/(n-m)!$. Each cycle of length $m$ is described by $2m$ such tuples: choose a starting point and an orientation. Therefore the total number of cycles of length $m$ is $n!/2m(n-m)!$, and the expected number of cycles is
$$ E = \sum_{m=3}^n \frac{n!}{2m(n-m)!} p^m. $$

In order to estimate this number, let's find the largest term. The ratio of two successive terms is roughly
$$ \frac{p^{m+1}}{(n-m-1)!} \frac{(n-m)!}{p^m} = (n-m)p. $$
When $p$ is constant, we see that the most important term corresponds to $m = n$, namely $n! p^n/(2n)$, and we deduce that for large enough $n$, the expected number of cycles satisfies
$$ 2(n-1)! p^n \leq E \leq 2n! p^n. $$


Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages?

Using NFAs does prove the result for regular languages, since NFAs accept exactly the regular languages. In principle, one could give a proof using DFAs but it's likely to be very fiddly and probably not enlightening. It's much easier to give the proof using NFAs and separately show that anything accepted by an NFA is also accepted by a DFA.

Indeed, it's even easier to give the proof using regular expressions! This is part of the point behind giving the three equivalent characterizations of the regular languages: it means that, when you want to prove something about regular languages, you can use whatever system makes the proof easiest.


For AVL trees, how do we know if a RL or a LR rotation is needed?

In this case the tree is right-left unbalanced. That's because when you insert $B$ it causes the root node to become unbalanced. You can tell its right-left unbalanced from the path that goes from the newly inserted node to the root node i.e. $B$ is the right child of $A$ and $A$ is the left child of $C$. Therefore, it needs a left-right rotation.


What can Idris not do by giving up Turing completeness?

Idris is Turing Complete! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total.

Interestingly, having data and codata is enough to model Turing Completeness since you can write a monad for partial functions. I did this, years ago, in Coq - it's probably bitrotted by now but here it is nevertheless: http://eb.host.cs.st-andrews.ac.uk/Partial/partial.v.

You do need one escape to actually run such things, but Idris allows you to do that.

Idris won't reduce partial functions at the type level, in order to keep type checking decidable. Also, only total programs can reasonably be believed as proofs.


Shortest decimal expansion within binary interval

Decimal numbers with k digits to the right of the decimal point are $10^{-k}$ apart. So if you choose k large enough that $10^{-k} < 2·2^n$, then there is a decimal number with k decimals inside the interval. You can for example calculate it as $round (x·10^k) / 10^k$.

You may be lucky, and a number with fewer decimals may be inside the interval. Rounding the result to k-1 or fewer decimals may give a result in that interval.


Reading CLRS analysis of hashing with chaining

I assume that you are talking about the hash-table that uses an adjacency list for the elements that have the same hash key (hash table using chaining). Let's look at a very simple example.

We have a hash table such as the following:

key : like list of elements
1   : x_11 -> x_12 -> ... -> x_11000000 -> NULL  // 1000000 elements
2   : NULL                                       // 0 element
3   : x31 -> NULL                                // 1 element

If you look at keys 1 and 3, which one is more likely to be visited? The answer is 1, because it has more elements than all other lists. Therefore, we are more likely to find the mysterious element in 1's linked list.


Non-deterministic Finite Automata | Sipser Example 1.16

You are confusing $\epsilon$ with a letter. It's not a letter! It's just the empty string.

Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is labeled with an arbitrary word. We say that the word-NFA accepts a word $w$ if there is a walk from an initial state to a final state such that if we concatenate the edge labels across the walk, we get $w$. In symbols, a word-NFA accepts $w$ if there is a sequence of transitions
$$
q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n
$$
such that:

$q_0$ is an initial state. (The usual model only allows one initial state, but we can relax that requirement.)
$q_n$ is a final state (also called an accepting state).
Each transition $q_{i-1} \stackrel{w_i}\to q_i$ corresponds to a transition of the word-NFA.
$w = w_1 \ldots w_n$.

An NFA is a word-NFA in which all transitions are labeled by letters (i.e., words of length exactly 1), and an $\epsilon$-NFA is one in which all transitions are labeled by letters or $\epsilon$ (i.e., words of length at most 1). Usually we also require that there be a unique initial state.

A word-NFA accepts $\epsilon$ if there is a sequence of transitions
$$
q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n
$$
such that $q_0$ is an initial state, $q_n$ is a final state, and all transitions are valid. In particular, if some state is both initial and final, then the word-NFA accepts $\epsilon$ (this correponds to $n = 0$).


Algorithm for Items Best Fit/Arangement in a Box

Yes, there are plenty of algorithms.

Here are some existing literature about packing rectangles.

What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?
Pack rectangular objects of different sizes in a fixed size rectangle?
Approximation Algorithms for Rectangle Packing Problems.
Optimal rectangle packing.

Here are some libraries that can be used readily.

Python 2D rectangle packing library
Rectangle packing program
Github topic on packing algorithms


Why is my own implementation of Bubble Sort so much slower than another one I found online?

From your pastebin, here is the first place you go wrong:

unsorted1 = unsorted2 = [randint(1, 99) for _ in range(count)][:]

Here you assign unsorted1 and unsorted2 to point to the same list. So when you call some_other_bubble_sort on unsorted2, it is in fact no longer shuffled! It is sorted.

The solution is to first assign unsorted1 and then unsorted2 to a copy:

unsorted1 = [randint(1, 99) for _ in range(count)]
unsorted2 = unsorted1[:]

That makes your algorithm only slightly less than twice as slow. That can be explained simply by the fact your implementation does a lot more stuff. In Python the little things add up, like setting switched to True every iteration.


Solution verification: solving $T(n) = T(n-1) + 2/n$

Although the final result is correct, your solution is not.

The recurrences of the form $T(n) = T(n-1) + 2/n$ is often called "decrease and conquer"; while the ones of the form $T(n) = T(n/2) + O(1)$ is called "divide and conquer". Generally, they are different and cannot be reduced to each other.

Hint: To solve $T(n) = T(n-1) + 2/n$, you can expand it and notice that $1 + 1/2 + \cdots + 1/n = H(n) = \Theta(\lg n)$, the $n$-th partial sum of the harmonic series (wiki).


What is the difference between the semantic and syntactic views of function types?

These are not called constructive and nonconstructive! The one you call "nonconstructive" works just as well in constructive mathematics (you have to be a bit careful about how you define the $\bot$ value, but that is a technical detail).

Rather, you are asking about semantic and syntactic distinctions. We imagine that the expressions we write in a program correspond to abstract mathematical objects. For example, the syntactic expression (fun n => 2 + n) 2 denotes the number $4$. (Under this view "evaluating a program" is about finding out which abstract mathematical object it denotes.)

We can then ask what mathematical objects corresponding to expressions of type a -> b. Presumably they are actual mathematical functions (although that is not so clear in the presence of computational effects). But they are not all functions, because those functions that can be expressed in a programming language have special properties, such as:

they are Turing computable (because programming langauges can be interprted by Turing machiens).
they are continuous (because in finite time we can only get finite information about input, and continuity essentially says that only finite amount of input is required to produce a finite amount of output).

So, it may make sense to restrict to special kinds of mathematical functions (only computable ones, only continuous ones). This way our mathematical objects will correspond more closely to our programs, and so presumably we will have a better setup. (In fact, as soon as we have a language with recursion, we cannot think of expressions of type a -> b as just ordinary functions, but rather somehting like the continuous ones--but let me not go there just now.)

As you say, most programers take a syntactic view, in which functions are syntactic expressions. This is certainly a possibility that can go a long way. But the semantic view in which we think of programs as denoting mathematical objects has its benefits too. Mathematicians know an awful lot about computability and continuity, and you can bring the knowledge in when you take the semantic view.

A trivial application of the semantic method is this: suppose we want to implement comparison of functions eq : (nat -> nat) -> (nat -> nat) -> bool which tells us whether two functions f, g : nat -> nat are equal. How do we do it? The answer is that we cannot implement it because that would give us a discontinuous function. But proving this fact using only syntactic methods is much harder. In fact, I do not know how to do it without using some computability theory, which again is a semantic method. You may think it is obvious that eq cannot be implemented, in which case you should wonder why eq : (nat -> bool) -> (nat -> bool) -> bool can be implemented (and the implementation was first found using semantic methods).

Another area where the semantic view is needed is numerical computation. It is absurd to claim that a program (syntactic entity) for solving a differential equation has nothing to do with differential equations (semantic entity).

Let me also say what the constructive-nonconstructive distinction is. This is about the logic you use to do math. If we use nonconstructive logic, which is the traditional way to do it, then we will be able to prove that there exist non-computable functions. Consequently, there will be functions we cannot implement. But if we use constructive logic, then it is impossible to prove existence of a non-computable function. (In fact, we may add an axiom to constructive logic which says "all maps are computable", although I would advise against this: how do you know that all external input that is coming into your computer from the universe is computable?) This is not the traditional way, but it is one that programers can sympathize with.

Lastly, I want to nitpick about something your write in your title. Definitions are not constructive or non-constructive. They just are. Constructivity is important when we prove and construct things. Function types in a programming language are defined a la type theory in terms of:

a type constructor, such as ->
rules for forming terms, such as $\lambda$-abstraction
rules for using terms, such as application
equations which are supposed to hold, such as $\beta$-reduction.

This works equally well in constructive and non-constructive logic, because it is just syntax. There are meta-theorems which say that for finite discrete objects (syntax, natural numbers, finite graphs, lists, ...) there is no difference between constructive and non-constructive logic (I am skipping over a lot of details). But when you ask for the semantics of your type, i.e., what mathematical object it corresponds to, then it makes a difference.


Closest k points - performance on large lists

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points.

I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q| * k * log |L|)$.
I did some performance test of different spatial indexes here (Figure 28) with 2D and 3D datasets, you should be able to get around 100,000 $k$-nearest neighbor searches per second (on an index with 10,000,000 points). Some of these spatial indexes have updates rates of up to 1,000,000 updates per second, see Figure 40 in the same document. Especially quadtrees and the PH-Tree have high updates rates.

Not sure that it matters, but the PH-Tree uses internally z-curves (Morten order), which means that the ordering of elements uses z-order and is independent of insertion/deletion order. However, also note that the PH-Tree does not support duplicates, there can be only one point at any given coordinate.


Unfortunately both sides contain the empty string. As you say, the Kleene star of the empty set also contains the empty string: $\varnothing^* = \{ \lambda\}$. The Kleene star of a language $L$, equals $L^* = \cup_{i\ge 0} L^i$, where $L^0 = \{\lambda\}$ and $L^i = L \cdot L^{i-1}$ for $i\ge 1$.

On the other hand $h(\lambda) = \lambda$ for any morphism $h$, so $\lambda \in h^{-1}(K)$ whenever $\lambda \in K$. As $L^*$ contains the empty string this is the case here.

However, this does not mean the two sets are equal.
Consider $h:\{a,b\}^*\to \{a\}^*$ defined by $h(a) = a$ and $h(b) = aa$ and $L=\{a\}$.


Find an algorithm that finds a minimal hitting set for sets limited in size

Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S_i$ as edges and of the elements $\{1,\ldots,n\}$ as vertices. We can assume that each edge connects two vertices, since singleton edges can easily be eliminated.

Both algorithms below can be extended to the case of general $k$.

Algorithm 1: Maximal matching Pick a maximal matching, and take all vertices containing it. This is a vertex cover since if there is an edge which isn't covered, the matching isn't maximal. Every vertex cover must contain at least one vertex per edge in the matching, and our solution contains two vertices per matching edge, hence it's a 2-approximation.

Algorithm 2: Linear programming Consider the following LP relaxation: there is a variable $0 \leq x_i \leq 1$ for every vertex, and a constraint $x_i + x_j \geq 1$ for every edge $(i,j)$. Find a solution minimizing $\sum_i x_i$, and take all vertices such that $x_i \geq 1/2$. This is clearly a vertex cover, and its value is at most twice the value of the LP, hence it's a 2-approximation.


Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

Fist of all the $\Omega(n \log n)$ lower bound only applies to comparison-based algorithms, that is only to algorithm that can only obtain information on the relative orders of two input elements by pairwise comparisons.
They do not have to be divide and conquer algorithms and they do not have to generate any tree. The lower bound simply follows from the fact that there are $n!$ possible permutations of the input elements and any correct algorithm must be able to output all of them (given the inverse permutation as its input).
This means that the number of branches on the longest computation of the algorithm must be at least:
$$
\log ( n! ) > \log (n/e)^n
=  n \log n - n \log e
>  n \log n - 1.44 n = \Omega(n \log n).
$$
Also, even in the case of comparison based-algorithms, an absolute lower bound of  $n \log n$ (without the constant hidden in the $\Omega(\cdot)$ notation, as you write in the question) on the number of comparisons cannot possibly exist since, when $n=2^k$, each element in Mergesort is compared at most $k-1$ times, showing that the total number of comparisons is at most $n(k-1) = n \log n - n$.
Your proposed algorithm is not clear to me but, in general,
if you change the model of computation by allowing other operations to be performed in addition to comparisons then the $\Omega(n \log n)$ lower bound does not apply anymore.
For example, given any constant $c$, in the word-RAM model you can sort a collection of $n$ elements between $0$ and $n^c$ in linear time using Radix sort, as long as the chosen word size $w$ allows to write $n$ in a (constant number of) memory word(s), as it is usually the case (it is standard to assume $w=\Theta(\log n)$).


Point and Application of Recursive and Recursive Enumerable Languages

Recursive languages correspond to whatever can be computed in your favorite programming languages. Recursively enumerable languages correspond to whatever can be enumerated in your favorite programming languages — for example, all provably true mathematical theorems.

Your question assumes a particular list of canonical language classes, including four classes: regular languages, context-free languages, recursive languages, and r.e. languages. However, this list is rather arbitrary, and it omits modern complexity classes, including the all-important classes $\mathsf{P}$ and $\mathsf{NP}$.

The class $\mathsf{P}$ is intended to capture what can be computed efficiently (whether it succeeds in this goal is another question). The class $\mathsf{NP}$ captures problems which can be solved using "exhaustive search", that is, SAT solvers, IP solvers, and the like.

It turns out that $\mathsf{NP}$ captures many natural combinatorial problems, many of which are "equally hard". This leads most researchers to think that these "equally hard" problems are actually hard, that is, cannot be computed efficiently, a conjecture known as $\mathsf{P} \neq \mathsf{NP}$.

Computational complexity theory mentions many other complexity classes of interest. Practically speaking, a relevant class of languages are those which can be decided in quasilinear time (broadly construed) in the RAM machine model. This class roughly corresponds to problems which can be solved in practice even on "big data".


Loop-local variable in Cytron's SSA algorithm

Congratulations for implementing Cytron's algorithm! You are one of a select few who have attempted it.

Most compilers these days tend to use a much simplified algorithm which inserts and then removes redundant phi nodes. We will go through that later. Be aware that although it produces minimal SSA form on reducible flow graphs, it sometimes doesn't on irreducible flow graphs. But all in good time.

I'm going to go through a couple of related points, some of which you've probably already noticed, but I'm going to mention anyway to make this answer a bit more self-contained.

First off, the definition of $\mathit{HasAlready}$ in the paper is doesn't make a lot of sense. It is defined as follows:

  $\mathit{HasAlready}(*)$ is an array of flags, one for each node, where $\mathit{HasAlready}(X)$ indicates whether a $\phi$-function for $V$ has already been inserted at $X$.

Already, we see a problem: Where's $V$ in this query? But then, in figure 11, we see this code:

  $\texttt{if}\,\mathit{HasAlready}(X) < \mathit{IterCount}$

  ...

  $\,\,\,\,\,\,\,\,\mathit{HasAlready}(X) \leftarrow \mathit{IterCount}$

So $\mathit{HasAlready}(X)$ should clearly be an integer, not a flag. Its value represents the highest-numbered variable that has had a $\phi$-function introduced for each basic block.

Secondly, if you are constructing SSA form using basic blocks, then Cytron's algorithm as published doesn't deal with multiple assignments to the same variable within a basic block, because the they don't need $\phi$-functions. The set of assignments to a variable $V$ (denoted $\mathcal{A}(V)$ in the paper) only refers to the last assignment in a basic block.

Now what you've identified is the dual of this: the only "uses" which matter are any that occur before the first assignment in a basic block. That also means that no potential reaching definition of a variable is "used" in a basic block if there are no uses before that first assignment in the block.

Now I've forgotten a lot of the details here, but that might explain the pop issue in the renaming algorithm: there isn't an assignment to x in basic block 1 as far as Cytron's algorithm is concerned.

OK, now that's out of the way, here's what most compilers tend to do: insert $\phi$-functions everywhere for everything (using variable scopes so we don't go completely crazy), and then remove the redundant ones.

In your case, let's suppose that x is declared outside the loop and initialised with 0. We rename every assignment, then insert a $\phi$ at the start of every block (except the start block) with the incoming values from the last assignment in all predecessors:

0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_1 := Phi(x_0, x_2)
    r_1 := Phi(r_0, r_1)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    x_3 := Phi(x_0, x_2)
    r_3 := Phi(r_0, r_1)
    r := i_3
    ret

This is already valid SSA form, it is just not minimal SSA form.

Now we iteratively apply two transformations:

If there is a Phi assignmment whose value is unused, remove it.
If there is a Phi assignment whose arguments are the returned value
of the assignment and one other value, remove it and rename the assigned variable to that other value.

An example of the first rule is in block 2, with r_3. That is unused, so we remove it.

An example of the second rule is in block 1, with r_1. Here, r_1 can be replaced with r_0 everywhere. In general, you might find something like this:

v_1 := Phi(v_1, v_2, v_2, v_1, v_2)

In that case, remove the Phi and replace v_1 with v_2 everywhere.

It should be clear why these two simplifications are valid transformations. What's interesting is that if you apply these two rules until none apply any more, you get minimal SSA form if the flow graph is reducible.

In your case, you get this:

0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    r := i_3
    ret

Now you can see that all of the Phi nodes for x have been eliminated, as we would hope. Also, x_0 and r_0 are dead definitions, but they can be removed later.

Just as a last comment, the very notion of a "basic block" isn't necessarily that important in modern compilers any more, after you have resolved scopes and before you generate assembly language.

The "sea of nodes" representation is a case in point. Many modern IRs tend to think in terms of sequencing constraints instead of linear blocks of code. That way, you don't have to deal with basic blocks specially as in this example.

If you think of each instruction as its own "basic block", then Cytron's algorithm should work perfectly!


Using your convention that the machine EITHER changes symbol OR moves Left/Right, then this is the machine you are looking for:

<q1,a,b,q2>
<q1,b,a,q2>
<q2,a,R,q1>
<q2,b,R,q1>

In other words, the machine alternates between the 'switch the letter' state and the 'move right' state.  [I am adopting the convention that the absence of a transition - say on space - is equivalent to halting; otherwise one needs another transition to cover that]


$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.

E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n < 2n$ and $2n \in O(n)$).

However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 < k n$ for all sufficiently large $n$.


First of all, every deterministic finite automaton is a fortiori a non-deterministic finite automaton. An finite automaton is deterministic if there are no $\epsilon$ moves, and for each state $s$ and alphabet symbol $\alpha$ there is a unique outgoing edge at $s$ labeled $\alpha$. If a finite automaton satisfies this condition, then it you can think of it both as a DFA and as an NFA. If it doesn't satisfy this condition, it is an NFA.