It's not problematic to have more than one goal node in A* if you just want to reach any goal node. You simply keep running the search until you have expanded the first goal node.

Provided that your $h(x)$ function is consistent (or just admissible if your graph is a tree) the way of breaking ties does not affect the optimality of the search. As A* always expands all nodes with $f(x) \lt C^*$ where $C^*$ is the true cost of the optimal solution, and never expands nodes with $f(x) \gt C^*$, the number of nodes that gets expanded will end up being the same (or almost the same, as we will see).

Consider this case: We have two nodes $a$ and $b$, who are both on the open list, and we have that $f(a) = f(b)$ and $h(a) \lt h(b)$. We choose to expand $a$ because of the lower $h$-value and discover that a goal node $g$ is a neighbor to $a$. As $h(x)$ is at least admissible the actual distance between $a$ and $g$ can not be shorter than $h(a)$ and therefore $f(g) \geq f(a)$. There are now two cases:

- If $f(g) \gt f(a)$, then we also have that $f(g) \gt f(b)$ and we therefore need to expand $b$ before we can conclude that we have found the fastest way to $g$.

- If $f(g) = f(a)$, then we also have $f(g) = f(b)$, but this only happens if the distance between $a$ and $g$ is $0$ and in that case $h(a)$  must also be $0$. We now have both $b$ and $g$ on the open list and their $f$-value is the same and so we expand $g$ as it is a goal node. In this case we do not need to expand $b$.

Had we expanded $b$ first, the exact same thing would have happened and we would have had to expand $a$ as well unless $h(b)$ was $0$. In other words, taking the lowest $h$-value first has no influence on the number of nodes expanded unless it is the case that $h(x) = 0$, in which case it does make sense to expand this node first. Note however, that only if the actual distance from $x$ to the goal is also $0$ (it could be more that $h(x)$) do we actually save a node from being expanded. So while A* always expands all nodes with $f(x) \lt C^*$ and never expands nodes with $f(x) \gt C^*$, the nodes with $f(x) = C^*$ could be expanded or not expanded depending on your tie-braking and the structure of the graph.


Dijkstra function for navigation for disadvantaged

Dijkstra's algorithm already solves your problem. If a staircase is unusable for the wheelchair-bound, then the corresponding edge should not appear in the graph. If some other route is usable but very slow, then it should be weighted accordingly.

The same kind of problem is already encountered with cars – some paths are too narrow for them. A smart GIS takes this into account, removing the corresponding edges when you navigate your car, and keeping them when you navigate your walk.

The difficult aspect here is obtaining this information – which path is suitable for the wheelchair-bound, and which ones should get penalties. Whether it can be done automatically (with a few mistakes) depends on your situation, which you haven't described in enough detail.


Finding which functions are bounded by $O(n^2)$

We have $n^2 + n = O(n^2)$. Indeed, if $n \geq 1$ then $n^2 \geq n$ and so
$$
n^2 + n \leq 2n^2.
$$


Why can't we compile 8086 Assembily for all OSs from any OS?

Porting to a different operating system is about a lot more than the particular assembly language you use.  Different operating systems have different system calls, different libraries, and different APIs, and converting from one to another is usually not something that can be done in an automated way -- even if both used exactly the same assembly language.  Most programs do need to access the filesystem, the network, display things on the screen, and so forth, and all of those require interaction with the OS and libraries.


Does the language defined in the details in NP-C or P?

Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete.

Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:

$k=0$, or
$k \in \{1,2\}$ and $G$ is not empty, or
$k = 3$ and $G$ has a triangle, which can be checked in $O(n)$ time.


Data structure for set of intervals - query for all intervals contains given point

There are many algorithms for this kind of problem.  See, e.g., segment trees and interval trees.  The kind of query you mention is known as a "stabbing query".

A segment tree takes $O(n \lg n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time, where $n$ is the number of intervals and $k$ is the number of intervals that contain $x$.  An interval tree takes $O(n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time.  Segment trees are static: they can't be easily modified after they're created.  Interval trees are dynamic: you can insert or delete an interval in $O(\lg n)$ time.

Other data structures exist as well.  There are also generalizations to higher dimensions, though the running time gets worse in higher dimensions.


Think of it this way. Fix $p$ and $q$ arbitrarily – for example, take $p = 4$ and $q = 5$. Then
$$
\begin{align*}
L_1 &= \{ a^4 b^{5i} : i \geq 0 \}, \\
L_2 &= \{ a^4 b^5 \}.
\end{align*}
$$
Now try to answer your question. The answer will be the same no matter what values you choose for $p$ and $q$.


Here is a reduction from CLIQUE to CLIQUE-or-almost.

Let $G$ be an arbitrary graph. Form a new graph $G'$ by adding two new vertices $x,y$ connected to all vertices of $G$, but not to each other. If $G$ contains a $k$-clique, then $G'$ contains a $(k+2)$-clique with a missing edge.

Conversely, suppose that $G'$ contains a $(k+2)$-clique $S$, possibly with a missing edge. If the clique doesn't contain a missing edge, then $S \setminus \{x,y\}$ is a clique of size at least $k$ in $G$. If $x,y \in S$ then the missing edge is $(x,y)$, and again $S \setminus \{x,y\}$ is a $k$-clique of $G$. In the remaining case, $|S \setminus \{x,y\}| \geq k+1$. Remove one vertex from the missing edge to obtain a clique of size at least $k$ in $G$.

For a reduction in the other direction, it is well-known that CLIQUE is NP-hard. Since CLIQUE-or-almost is clearly in NP, by definition there is a reduction from CLIQUE-or-almost to CLIQUE. One can construct such a reduction via the proof of the Cook-Levin theorem.


Bellman-Ford: Find all nodes that have minus infinite distance to source

Well after a morning of testing, I just figured out that my solution is RIGHT, the problem I had before is because of overflow (I use 10^19 to declare infinity for all vertices at the beginning and it can leads to overflow for some test cases).


What's the algorithm for floating points equality test?

You cannot meaningfully test floating point values for equality. A floating point value does not represent a real number, it represents a range of real numbers, but it fails to store the width of this interval. All you can do with floating point values is to test them for approximate equality, and it's up to you to define the approximation you're willing to make. You can test whether the difference is smaller than a certain constant ($|x-y| \le \epsilon$), or whether it's relatively small ($|x-y| \le \epsilon \min\{x,y\}$), or something else; the right method and the value of $\epsilon$ depend on the calculation.

There is a seminal article on this topic: the aptly titled What Every Computer Scientist Should Know About Floating Point Arithmetic by David Goldberg [PDF]. Sure, it's long — that shows how difficult floating point is to use, if you care about things like whether 0.1 + 0.2 equals 0.3. And no, there is no magic bullet that would let you sweep the difficulties under the carpet. There is a good, more accessible summary called What Every Programmer Should Know About Floating-Point Arithmetic*, or, Why don’t my numbers add up?

Applications that require exact computations, such as financial computations, do not use floating point. They use integer or fixed-point arithmetic.

Applications that use floating point require a careful, expensive analysis to find out what the uncertainty in the result is. Keep in mind that a floating point value does not really represent a real number $m \cdot 2^e$ nor even a specific interval like $\left[(m-\frac12) 2^e, (m+\frac12) 2^e\right]$, but an interval whose width increases as the computation becomes longer as the uncertainty accumulates.

There is a standard for floating point operations, which most (but not all) systems today implement: IEEE 754 (“IEEE floating point”). This standard defines storage formats, rouding rules, denormalized numbers, etc. It tries to arrange for typical computations to be as precise as possible. Arranging for 0.1 + 0.2 to equal 0.3 is beyond its abilities (that would be possible, but then it would cause 0.2 + 0.3 not to equal 0.5 or some similar misfit).

Some threads on Stack Overflow on this topic:

Is floating point math broken?
Why Are Floating Point Numbers Inaccurate?
Floating point inaccuracy examples
Why does changing the sum order returns a different result?


What's wrong with this LL grammar? (very short)

First note that $T = c^*$ (using regular expression syntax). We can therefore rewrite your grammar to:

S --> c*a | b | Sc

Rewriting even further, we can say that $S = (c^*a | b)c^*$, so $S$ is regular. It is not hard to come up with a grammar for this language:

S --> T a T | b T
T --> c T | λ

More generally, when trying to rewrite grammars to $LL$ form, one first removes left recursion using standard techniques (for instance here). Then one tries to remove any conflicts that are left, for which no general techniques are known - just try to figure out what the conflict means, and try to solve it accordingly.


Inside a modern high-end CPU, the "program counter" is probably not stored in a single place. Superscalar out-of-order execution requires more than one instruction to be executing at a single time, some of them executing speculatively.

To understand what's going on, you need to consider what the program counter is used for. I'm going to use the Intel Core 2 microarchitecture as an example, mostly because it's the only decent-but-uncluttered diagram that I could find. Most modern high-end CPUs are broadly similar, in that they have a Tomasulo-like pipeline with register renaming. A RISC (e.g. MIPS or ARM) might have fewer decode stages. Also, not all CPUs implement a retirement register file; there are other methods which do the same job.

Nonetheless, let's go with this for the moment.

Instructions are (broadly speaking) streamed from the top to the bottom of the diagram. They start in the cache (and of course may have to be fetched into the cache), go through decoding and being stored in different buffers, until they end up in the reservation station. Here it waits until it is ready to execute.

When everything that an instruction needs becomes available, it goes to an execution unit. In the diagram, the yellow parts are the "normal" execution units (integer, floating point). There are also execution units for memory operations, but we'll ignore those for the purpose of this discussion.

When an instruction has finished execution, the results are posted on the results bus (called the "common data bus" in Tomasulo's original paper). These results may wake up instructions which depend on those results, and the cycle continues.

Now, think for a moment about what the program counter is used for.

First off, let's think about instruction fetch. It needs to know what address to send to the instruction cache for lookup. Most of the time, it's the next address. However, do consider that the cache line width isn't a single instruction; in this example it's 128 bits. So the instruction fetch unit actually increments its "program counter" by 16 bytes, no matter how big each instruction is.

Branch instructions complicate instruction fetch. Unconditional branches are straightforward once you've recognised them, so the instruction fetch unit gets some input from pre-decoded instructions.

Conditional branches are similar, except that the instruction fetch unit needs to decide whether to guess that the branch was taken or not taken to keep instructions flowing.

So the IFU has an idea about what the "program counter" is, but it is granular, working on a cache line at a time.

Now let's think about execution. The CPU would like to execute instructions out of order if it can, however things can happen which complicate that. The most obvious problem is if the IFU incorrectly predicted a conditional branch. However, instructions can also raise exceptions, and also the CPU might need to respond to an external interrupt.

To achieve this, the CPU needs to be able to recreate the CPU state as if it was executing instructions sequentially at the time that the control flow was interrupted. This is the job of the reorder buffer.

The reorder buffer is conceptually a queue of instructions, ordered by the "logical order" (i.e. the order that they would be executed if this was a scalar in-order processor). An instruction enters the queue as it travels down the fetch-and-decode path. Once it is in the ROB, it can execute out-of-order.

When an instruction completes, its entry in the ROB is updated noting that it is now complete. An instruction can leave the queue (it is "retired") if it has completed, and every instruction before it in logical order has completed or retired.

The "result" of many instructions is to write a value into a register. If that value is used by a subsequent instruction which is awaiting execution (i.e. it's in the reservation station), then this is handled by the internal results bus. Either way, the result is also stored in the instruction's entry in the ROB. This arrow is not shown on the diagram, but it happens.

When an instruction retires, any register write that it does is stored into the retirement register file. Because instructions are retired in-order, this register file actually stores the state of the machine registers exactly as they would be if the instructions were executed in-order. This is why it's also called the "program visible state". This is the view of the registers that the program "sees", what is saved and restored on a context switch, and so on.

So the second place where there the "program counter" is stored is here, in the instruction retirement unit. This is the program counter as the program sees it, without any speculation, but it's decoupled from instructions that are being fetched and executed.

As an aside, the ROB is also how faults and exceptions are handled. If a fault occurs, then the ROB for the faulting instruction is updated with information about the fault, and every instruction after it in the ROB is removed, along with a flush of the fetch-and-decode parts of the pipeline. This ensures that instructions after the fault don't "happen" even if they have been executed already: the results of those instructions never make it to the program-visible state. Speculative execution is handled in a similar way.

A third place where the program counter may be stored is in the ROB itself. It may be convenient to store the program counter of each instruction along with the instruction. Note that it may not be necessary to store the whole program counter; it may be sufficient to store enough information to recreate the program counter as needed.

A final place where the program counter may be stored is as a general-purpose register. Exactly what this means is a bit complicated to explain if you don't know how register renaming works, but some instructions might need the value of the program counter (e.g. it might be used for memory addressing in position-independent code), in which case transient copies may be stored in reservation station entries of instructions which use it.

So what I hope you can see here is that the real answer is "it's complicated". The program counter is different from other registers in a modern CPU, and there is no one place where it's really "stored", because more than one instruction is "happening" at any given point in time.


Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

The vertices of $G'$ are exactly given by $(v, i)$ with $v\in Nodes$ and $i \in \{0, 1,\cdots, k\}$.  Edges in $G'$ are between $(u, i)$ and $(v, i)$ if $(u, v)$ is an edge of $G$, or between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}.$

We know $Nodes$ are 6 nodes, i.e., $H, B1, B2, Bus, P, M$ and $k=3$ as there are three kinds of shops, i.e., bank, post office and movie where $S_1$ is the set of banks, $S_2$ post offices and $S_3$ movies.

There are 24 vertices of $G'$
$$\begin{align}
(H,0),(B1,0), (B2,0), (Bus,0), (P,0), (M,0), \\
(H,1),(B1,1), (B2,1), (Bus,1), (P,1), (M,1), \\
(H,2),(B1,2), (B2,2), (Bus,2), (P,2), (M,2), \\
(H,3),(B1,3), (B2,3), (Bus,3), (P,3), (M,3). \\
\end{align}$$

The edges are
$$\begin{align}
&(H,0)(B1,0), (B1,0)(Bus,0), (Bus,0)(P,0), (P,0)(M,0), (H,0)(B2,0) \\
&(H,1)(B1,1), (B1,1)(Bus,1), (Bus,1)(P,1), (P,1)(M,1), (H,1)(B2,1) \\
&(H,2)(B1,2), (B1,2)(Bus,2), (Bus,2)(P,2), (P,2)(M,2), (H,2)(B2,2) \\
&(H,3)(B1,3), (B1,3)(Bus,3), (Bus,3)(P,3), (P,3)(M,3), (H,3)(B2,3) \\
&(H,0)(B1,1), (Bus,0)(B1,1), (H,0)(B2,1) \\
&(Bus,1)(P,2), (M,1)(P,2)\\
&(P,2)(M,3)\\
\end{align}$$

  What does it really mean "between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}$" ?

It means exactly what it means.

For $i=0$, $v$ must be one of two nodes in $S_{0+1}=S_1$, i.e., $B1$ and $B2$.

If $v$ is $B1$, $u$ must be either $H$ or $Bus$ since all edges in $G$ whose endpoints include $B1$ are $HB1$ and $BusB1$. So $(H,0)(B1,1)$ and $(Bus,0)(B1,1)$ are edges in $G'$.
If $v$ is $B2$, $u$ must be $H$ since the only edge in $G$ whose endpoints include $B2$ is $HB2$. So $(H,0)(B2,1)$ is an edge of $G'$.

It should be clear now what should happen if $i=1$ or $i=2$. Note $i$ cannot be 3 since there is no $S_{3+1}.$

  How many new nodes do need to make, 3 or 4 copies ? I only make 3 so far since there are only 3 errands.

Yes, besides the $G$ itself, we should make 3 copies of $G$, one copy of $G$ for each shop John should visit. There should be 4 copies of $G$ with 6 extra (red) edges.


How to find a minimum cut of a network flow?

The minimum cut is a partition of the nodes into two groups.

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition $A$. The rest of the nodes (the unreachable ones) can be called $B$. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in $A$ to a node in $B$.


Solve Time Complexity problem using Time Hierarchy

Your intuition that $ \text{TIME}(n^3 \times 2^n) \subsetneq \text{TIME}(2^{n^2})$ is correct.

It is easy to see that $2^{n^2}$ is time-constructible. Given $n$, you can compute $n^2$ in $\log^2 n$ time, then write 100...00 with $n^2$ zeros, in time $O(n^2)$.

The Time-Hierarchy Theorem states that, for such time-constructible  $f(n)$,

$$ \text{TIME}(o(\frac{f(n)}{\log f(n)})) \subsetneq \text{TIME}(f(n))$$

It is clear that $ n^3 \times 2^n \in o(\frac{2^{n^2}}{\log 2^{n^2}}) = o(\frac{2^{n^2}}{n^2}) $.

Therefore, $ \text{TIME}(n^3 \times 2^n) \subseteq \text{TIME}(o(\frac{2^{n^2}}{\log 2^{n^2}})) \subsetneq \text{TIME}(2^{n^2})$.


There are many possible approaches.  One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs.  There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity.

One approach is to measure similarity using the Levenshtein edit distance.  If you have $N$ strings, the naive way is to loop over all $N^2/2$ pairs, compute the edit distance for each, and save the pairs where the edit distance is below some threshold.  However, this doesn't scale when $N$ gets large.  Another alternative is to use fancier data structures and algorithms to find only the pairs of strings that are similar, e.g., BK-trees, ternary search trees, metric trees, Levenshtein automata, shingling, or other methods.  See, e.g., How fast can we identifiy almost-duplicates in a list of strings?, How to speed up process of finding duplicates/similar items in a large amount of strings?, Find all pairs of strings in a set with Levenshtein distance < d, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, and https://cstheory.stackexchange.com/q/4165/5038 for some references.  Credits to Pseudonym for part of this suggestion.

Alternatively, if you want to measure similarity using the number of characters the differ (i.e., like the edit distance but with only the "replace" operation and without the "insert" or "delete" operations), you could look at locality sensitive hashing as a way to find all pairs of similar strings.


Checking disjointness between subsets of a poset

Without further information, you can't do any better than $O(n^2)$ queries to $f$, where $n=|X|+|Y|$.  There is a simple adversary argument.

Imagine you have an algorithm that uses $o(n^2)$ queries.  Consider running it on a set $X,Y$ chosen so that $f(x,y)=0$ for all $x \in X, y \in Y$.  If the algorithm is correct, the algorithm must return F on this input.  Since the algorithm runs in $o(n^2)$ time, there must exist some pair of elements $x_0,y_0$ that was never queried.  Now run the algorithm on a pair of sets $X,Y$ chosen so that $f(x_0,y_0)=1$ but $f(x,y)=0$ for all other pairs $x,y$.  We see that $f$ always returns 0 during this execution, too, so this execution must follow exactly the same path as the first execution, and thus must also return F on this input.  However, returning F on this input is incorrect.  Therefore, there is no algorithm that takes $o(n^2)$ time and is always correct.


Find the shortest string that is not a sub-string of a set of strings

Here's one possible solution, similar to the linked question: Algorithm Request: “Shortest non-existing substring over given alphabet”

Use a sliding window over each input string to build your trie.

For n=1 to n=max(length(s)) where s is an input string, do:
For each s, construct window of size n, slide window over s adding each window (substring of size n) to the trie, then
Visit each parent of the leaf set of the trie. If there exists a parent node whose set of child nodes is smaller than the size of the alphabet, then you can form your desired string from this parent by appending a character from the alphabet that does not result in a string identical to one of the leaf nodes
If no such parent node exists, continue to next larger n


What do I need to know about algorithms?

If you do anything a bit complicated, you will almost certainly have to design your own algorithms. STL/boost are nice, amazing really, but it is useful to know how things work behinds the scenes and be able to reproduce it. This will help you tackle problems that the STL/boost, generic enough as they are, cannot handle; or problems that are entirely different from the ones the STL/boost can help with. Many times, algorithms and data structures that I've designed were built on top of STL/boost.

  Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms.

Chances are, if you make any interesting programs, you are going to find it useful to design some algorithms and data structures. Sometimes, the most effective optimizations cannot beat a simple change in methodology or representation.

Unless the algorithm you require/design is useful to a wider audience, it can sometimes be difficult to package it as a useful library. Perhaps you will find that something you made can be useful, and will publish it (github is chock full of these projects). Therefore, I think that if you program long enough, you will become a "library maintainer/implementer of some sort", even if you are the only one using it, for lack of publicity.

Bottom line: I don't think libraries like STL and Boost are making knowing algorithms less important at all; rather they are making more advanced algorithms within reach. While libraries such as these can sometimes make knowledge of their algorithms unnecessary for small programs, in practice it can important to know if you intend to design anything complex.


Show that the class of regular languages is closed under shuffle

Suppose, we have a simple string like $w = a_1b_1$ then what I understand you want to do is process $a_1$ in $D_A$ then jump to initial state of $D_B$ using $\epsilon$-transition and the process $b_1$ in $D_B$ but we don't know where $a_1$ ends and $b_1$ starts. So using non determinism we check all possibilities of where $a_i$ can end and $b_i$ can start.

To do that we start with a combined starting state $(q_A,q_B)$.
We have all the states possible by making $Q = Q_A \times Q_B$
Now we two kind of transitions from any state from $Q$ first we make transition in $D_A$ ignoring the transition in $D_B$ that way we can handle the case where the symbol is part of $a_i$. In a similar way we will add second kind of transitions assuming symbol is part of $b_i$.

Going this way there won't be any possibility left unchecked.

  How does it detect whether we are at DFA A OR B?

we don't have a marker between $a_i$ and $b_i$ so we make 2 guess at every state. First, The symbol is part of $a_i$ or $b_i$ we are currently in and second, that the current symbol is first symbol of the next $b_i$ if we currently checking $a_i$ and next $a_{i+1}$ if currently checking $b_i$


Non-trivial difference(s) between Computer Algebra System and Proof Assistant

There are two major differences: CAS and proof assistant tend to focus on different application domains, and they tend to take a different position on correctness vs ease of deriving results.
Most CAS focus on scientific calculations: calculations that are useful to physicists, to chemists, to mechanical engineers, to roboticists, etc. Proof assistants tend to focus on mathematics, computer science and software engineering.
In a proof assistant, it is crucial that you can only derive true propositions. That's the whole point. In contrast, CAS usually have hidden assumptions. For example, you might derive equations that are only true if one of the variables is nonzero, or if some intermediate result is nonnegative. These assumptions are not always explicit. When modelling a real-world problem, these assumptions are usually justified by the physics – if T is a temperature, there's no point in wondering what the equations would look like for T < 0 K.
Some systems can be classified as both CAS and proof assistants because they make all such assumptions explicit.
There's a good reason why CAS take shortcuts: it makes them easier to use for their application domain. When you work in a proof assistant, you often spend a lot of effort directing the computer to the "interesting" path. You have to figure out that at this step, x>=3, so you guide the proof by telling the proof assistant to consider the cases x<3 and x>=3 separately, then you repeat with y+z>x, and so on. A proof assistant gives results that are true for all inputs, but the cost of that is that you have to make the proof work for all inputs. A CAS can give results for general inputs, which is generally good enough for physics and physical engineering (basically, anywhere that's modelled by continuous mathematics – as opposed to software engineering which is typically modelled by discrete maths and there's no such thing as general inputs).


I'm not sure what do you mean that "$n \log n$ will converge to one value" because in fact $\log n$ diverges to infinity (so is $n \log n$).

Recall that $f(n) \in O(g(n))$ iff exists constants $c, N$ so that $f(n) \leq c \, g(n)$ for every $n \geq N$ (intuitively, $f(n)$ could be bound above by a constant multiple of $g(n)$ as $n$ grows large enough).

$n \log n \in O(n \log n + n)$ is then obviously true since $n \log n + n > n \log n$.

It is worth noting that the other side $n \log n + n \in O(n \log n)$ also holds because $n \leq n \log n$ as $n \geq \mathrm{e}$, so choosing $(c, N) = (2, \mathrm{e})$ proves this.


What is the correct representation of Master Theorem?

By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.


Is there any better way to find the closest points' distance?

This is the well-known closest pair of points problem, and you can solve it for $n$ points in $O(n \log n)$ time by divide and conquer.

A pretty cool randomized algorithm due to Rabin is also available.


Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time

The 2007 paper Linear-time ranking of permutations gives a linear time ranking algorithm for the lexicographic order, assuming arithmetic on numbers of length $O(n\log n)$ takes constant time.

The 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for the lexicographic order. Regarding the latter, it states

  The whole problem of ranking permutations in lexicographic order seems inextricably intertwined with
  the problem of computing the number of inversions
  in a permutation, and it seems that a major breakthrough will be required to do that computation in linear time, if indeed it it possible at all.

On the other hand, it does mention an $O(n\log n/\log\log n)$ algorithm for ranking permutations in lexicographic order due to Dietz.


Are there strongly-polynomial algorithms that take more than polynomial time?

No, any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model. That is the whole point of strongly-polynomial vs weakly-polynomial.

When you've analysed algorithms in the past, you've probably assumed that your arithmetic operations (addition, multiplication, etc.) take unit time. This is the arithmetic model of computation, where a step is defined as one arithmetic operation and input size is the number of integers. In the TM model, this isn't true, as a step is defined as moving the head and input size is defined as the number of bits used to represent the input. Thus arithmetic operations take time proportional to the number of bits used to represent them.

The definition restricts to TM space because that's the only condition you need to convert a polynomial time algorithm in the arithmetic model to a polynomial time algorithm in the TM model. The algorithm is already polynomial time in the arithmetic model, so as long as it's space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

In the case where you can't bound the space of your algorithm, you can't guarantee anything about the time when converting between the two models. There exist algorithms that take polynomial time in the arithmetic model but not in the TM model, and vice versa. Drawing examples from wikipedia let's elaborate on this.

An algorithm that is polynomial in the arithmetic model but not the TM model
Suppose given the integer $2^n$ we wish to compute $2^{2^n}$ by repeated squaring. The integer $2^n$ takes space proportional to $n$ (i.e. the bits used to represent it). However $2^{2^n}$ takes space proportional to $2^n$, which is exponential in the size of the input. In the arithmetic model this algorithm is clearly polynomial since we perform $O(n)$ multiplications assuming each takes unit time which is polynomial in the input size. However the resulting value is exponential in the size of the input, so in the TM model this would take exponential time simply to write the bits necessary to store the result. Note that if we could bound the space of the algorithm, then we can guarantee that it is polynomial in the TM model as well.

An algorithm that is polynomial in the TM model but not the arithmetic model
The standard GCD algorithm is one such example. Given two integers $a,b$ computing $gcd(a,b)$ takes $O((\log(a)+\log(b))^2)$ steps which is polynomial in the size of the input $\log(a)+\log(b)$. However in the arithmetic model the size of the input is just two integers and we can't bound the number of steps of the algorithm since it depends on the magnitude of $a$ and $b$.

Notice that the last example does not contradict the definition of strongly-polynomial. Strongly-polynomial doesn't say anything about algorithms that are polynomial in the TM model, it's only defined in the arithmetic model. If an algorithm is polynomial time in the arithmetic model and also happens to use space bounded in the size of input in the TM model, then it is strongly-polynomial.


If $L^*$ or $L^+$ is empty, can L be an infinite language?

1) You need to take a look at this page. Remember that there is an implication to be proved true or false.

2) Consider the fact $L \subseteq L^{+}$ and apply it to the case $L^{+} = \emptyset$.


If NP is a subset of DTIME[n^O(log n)] then what happens?

If $\textbf{NP} \subseteq \textbf{DTIME}(n^{O(\log n)})$, then we get $\textbf{P}^\textbf{NP} \subseteq \textbf{P}^{\textbf{DTIME}(n^{O(\log n)})} = \textbf{DTIME}(n^{O (\log n)})$. Continuing this reasoning, the entire polynomial hierarchy $\textbf{PH}$ is contained in $\textbf{DTIME}(n^{O(\log n)})$. By the time hierarchy theorem, $\textbf{DTIME}(n^{O(\log n)})$ is a proper subset of $\textbf{EXP}$ (and even of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$), so $\textbf{PH} \neq \textbf{EXP}$. In particular, we also get $\textbf{NP} \neq \textbf{EXP}$ and $\textbf{BPP} \neq \textbf{EXP}$ because both $\textbf{NP}$ and $\textbf{BPP}$ are in the polynomial hierarchy. For $\textbf{BPP}$ this is not that surprising since we already suspect it is contained in subexponential time.

What happens for $\textbf{PSPACE}$? Not much, as long as I'm aware of. We have $\textbf{PH} \subseteq \textbf{PP}$ and $\textbf{PH} \subseteq \textbf{P}^\textbf{#P}$ (by Toda's theorem), but I don't see any direct consequence for $\textbf{PP}$, let alone $\textbf{PSPACE}$.


Algorithm: ordering non-overlapping intervals

You can solve it in $O(n \lg n)$ time using a divide-and-conquer algorithm.

Explaining the main idea: a cleaner variant

To help me explain the main idea, I'm going to change the problem slightly.  I'll assume we're given a set of intervals, with no interval appearing more than once in the set, and where for any pair of overlapping intervals $I,I'$, one of them contains the other (i.e., either $I \subset I'$ or $I' \subset I$).  The goal is to output a forest (a collection of trees).

This variant of the problem is slightly more general, in that we're not assuming we have a single root interval that all others are contained in.  It's also slightly more specific in that I'm assuming we don't have the case of a trivial overlap containing a single point.

I'll show later in my answer how to remove these extra assumptions, but for now, let's go with this variant of the problem, as it makes explaining the main ideas easier.

Main idea: an algorithm for the cleaner variant

We'll use divide-and-conquer.  Let $x$ denote the median of the $2n$ endpoints of the intervals.  This can be computed in $O(n)$ time.

Use $x$ to partition the intervals into three collections:

The intervals that are wholly to the left of $x$ (i.e., their right endpoint is strictly less than $x$).
The intervals that are wholly to the right of $x$ (i.e., their left endpoint is strictly greater than $x$).
The intervals that contain $x$.

We'll first compute three forests, one forest for each of these three collections.  Call these forests $\mathcal{L}$ (the forest of the intervals on the left), $\mathcal{R}$ (for the intervals on the right), and $\mathcal{M}$ (for the intervals that contain $x$).  You can compute $\mathcal{L}$ and $\mathcal{R}$ by invoking the algorithm recursively.  You can compute $\mathcal{M}$ directly by sorting the intervals that contain $x$ by decreasing width and building a path of the intervals by descending size (each node in $\mathcal{M}$ has exactly one child; it is the next-smallest interval).

Now we need to join together the forests $\mathcal{L},\mathcal{R},\mathcal{M}$.  Since $\mathcal{M}$ is a path, given an interval $I$, you can find the smallest interval $I' \in \mathcal{M}$ such that $I \subset I'$ by using binary search.  Therefore, to join the forests, take the roots of $\mathcal{L}$ and $\mathcal{R}$ and use binary search in $\mathcal{M}$ to find the smallest interval containing it, and add a corresponding child relationship.  This is all you need to do to join them into a single forest, as there can be no other child relationships between $\mathcal{L},\mathcal{R},\mathcal{M}$.  Output the resulting forest.

What's the running time of this procedure?  Well, it takes $O(n)$ time to partition the intervals into these three collections.  You can compute $\mathcal{M}$ in $O(n)$ time (if you've done a single up-front precomputation to sort the intervals by decreasing width).  It will take at most $O(n \lg n)$ time to join $\mathcal{L}, \mathcal{R}, \mathcal{M}$ into a single forest, since each binary search operation can be done in $O(\lg n)$ time.  With a little more cleverness, you can speed up the merging to run in $O(n)$ time (pre-sort the intervals by their left endpoint once, and by the right endpoint; now you can join $\mathcal{L}$ and $\mathcal{M}$ by doing a merge on the sorted list of intervals of $\mathcal{L}$ and the sorted list of intervals of $\mathcal{M}$, both sorted by their left endpoint; join $\mathcal{R}$ and $\mathcal{M}$ similarly).  Therefore, the running time is $O(n)$ plus the time for the two recursive calls.  Finally, note that each recursive call is on at most $n/2$ intervals, due to the way we chose $x$ (there can be at most $n/2$ intervals wholly to the left of $x$, as each such interval contributes 2 endpoints to the $2n$ endpoints, and at most $n/2$ intervals wholly to the right of $x$).

Therefore, we get the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

whose solution is $T(n) = O(n \lg n)$.

Solving your original problem

Your original problem allows a pair of intervals to overlap in a single point, without either one containing the other.  This doesn't fundamentally change the problem.  You need to generalize the method for computing $\mathcal{M}$ slightly, as it is no longer guaranteed to be a simple path, but this is not hard to do.  Also, now $\mathcal{M}$ might have two leaves.  If so, for each root of $\mathcal{L},\mathcal{R}$, you need to compare it to both leaves to see whether it is contained in either one.  This doesn't change the overall running time.

Also, your original problem allows some intervals to appear in the input twice.  This is easy to accommodate: remove duplicates, count how many times each interval appears in the input, run the algorithm above, and then adjust the tree to account for multiplicities (e.g., by duplicating nodes, or however you would like them to appear in the final output).


Probability of hash collision in the case of two parallel hashes

You can think of concatenating the two hash values and treating the result as a single hash.  Then you have $n$ records, each of which has a single hash.  The probability of a collision among $n$ hashes is roughly $n^2/2^{b+1}$, if the hash outputs a $b$-bit value.  In your case if each of the two individual hashes is 64 bits long, after concatenation you have a 128-bit hash for the record, so $b=128$.

How did I obtain the formula $n^2/2^{b+1}$?  It's an application of the birthday paradox, with $n$ people born on a planet that has $2^b$ days in the year (instead of 365 days).  Or, if you prefer an intuitive argument: think of all ways to pick a pair of $b$-bit hashes.  There are about $n^2/2$ pairs of hashes. For each one, there's a $1/2^b$ probability that those pair of hashes are equal (that they collide).  So the total probability that at least one of these collide is about $n^2/2$ times $1/2^b$.  This is a crude estimate that isn't totally accurate, but it turns out to be a reasonable approximation as long as $n^2/2$ is fairly small compared to $2^b$.


on-the-fly decompress a flat-file database

What is "too large to fit in memory"? Current operating systems can handle processes with GiB of memory, if you use e.g. mmap(3) on Unix/Linux, you can work as if you had the whole file in memory and access it at random. That might be much faster than compressing/uncompressing on the fly. And (if I understand your question correctly) you want to access individual records (i.e., rows) by key, so you will have to compress only the remaining row and keep the key, working one row at a time (you don't want to have to uncompress from the start to be able to access row 102354 each time, don't you?). That will severely limit the compression gain.

If you can preprocess the data (a given, since you talk about compressing it), perhaps an even better bet is to use a simple(ish) database to store it, like Berkeley DB, the Unix standard DBM or it's GNU take GDBM or other, more modern, for performance tuned ones like Lightning Memory-Mapped Database LMDB.


MULT in a RISC - should instructions take the same amount of time in a RISC system

RISC processors are pipelined, and have been since the beginning.  That is, at a single time there are several instructions which are in different phase of execution.  That mean that there is two different numbers that you can give for the execution time.  One, the latency, which measures the time between the start of an instruction and its end.  The other, the throughput, which measures how many instructions can be executed in a given time.

When someone says that RISC have single clock instructions, they are thinking about throughput, that is that RISC processors are able to execute one instruction per clock, and not latency, that is that it take one clock to execute any given instruction.

Early RISCs did not have multiplication instructions. That was more a consequence of manufacturing process limitation of the time, which would not have allowed to put a multiplier on the chip along with the rest of the processor, than a fundamental characteristic of RISC.  With increased integration density, RISC acquired such instructions.

Note that it is possible to achieve bigger throughput than one instruction per cycle.  For that, you need to be able to decode several instructions per cycle, and have several execution unit. That is something called super-scalar and high-end processors are super-scalar since the early 90's.

Note also that the possibility to achieve the theoretical throughput in practice depend on the program (you need to have instructions which are independent to be able to execute them in parallel, you need to have the data available, and thus have pattern of memory accesses and a memory sub-system which together allow to provide the data rapidly enough).


Regular Expression: L= {w | every even position of w is '1'}

An odd position can either have 0 or 1 and every even position can only have 1. RE for this can be: $$ ((0 + 1)1)^* (\epsilon + (0+1))$$ Note that, it also contains the empty word.


What do you get when you add $O(n)$ to itself $n$ times?

The notation $O(n)$ stands for a function which is bounded by $Cn$ for some constant $C>0$ and large enough $n$.
If you have a two functions $f_1,f_2$ which are both $O(n)$, then so is their sum $f_1+f_2$: indeed, suppose that $f_1(n) \leq C_1n$ and $f_2(n) \leq C_2n$ for large enough $n$. Then $f_1(n) + f_2(n) \leq (C_1 + C_2)(n)$ for large enough $n$.
Similarly, if you have a single function $f(n)$ which is $O(n)$ and you add it to itself $n$ times then you get a function $nf(n)$ which is $O(n^2)$.
However, this fails when you add $n$ different functions which are $O(n)$. For example, consider the functions $f_k(n) = kn$ and the function $g(n) = f_1(n) + \cdots + f_n(n)$. Then $f_k(n) = O(n)$ for all $k$, but it is not true that $g(n) = O(n^2)$; rather, $g(n) = \Theta(n^3)$. (This means that $cn^3 \leq g(n) \leq Cn^3$ for some $c,C>0$ and large enough $n$.)
If we know that the functions $f_k$ are uniformly $O(n)$, that is, there is a single $C>0$ and a single $N>0$ such that $f_k(n) \leq Cn$ whenever $n>N$, then it does hold that $f_k(1) + \cdots + f_k(n) = O(n^2)$.
(It doesn't suffice to require just $C$ to be uniform. For example, if $f_k(n) = n+k^2$ then $f_k(n) \leq 2n$ for large enough $n$, but $f_1(n) + \cdots + f_n(n) = \Theta(n^3)$.)


Prof Knuth's MIX computer - Card Reader and illegal characters

I imagine the concepts developed in the Exercises are meant to be formally part of the MIX specification, but there will also be some degree of arbitrariness.

For example, the MIX character set of $56$ characters supports only upper case text, but also includes three Greek characters ($\Delta$, $\Sigma$, $\Pi$) and an arbitrary selection of punctuation characters (no '%', '?', '!' or '^'; '/' but no '\').

Similarly, the restriction on allowed characters in the card reader is probably just to make the point that not all input devices will support the full character set. Knuth may have regarded the typewriter terminal (which presumably does support the full character set) as the main input for program instructions, and may have seen the card reader as primarily for data input.

I think you can make your MIX implementation a completely faithful implementation or a looser interpretation of the original specification - it is your choice.


This just means that the elements stored in a binary search tree are one dimensional. Or more generally that they can be ordered in some meaningful way. You can think of this ordering as putting all the elements on a line, from "smallest" to "biggest" (for an appropriate notion of small and big depending on the particular case). And partitioning then always happens by cutting this line at some point. Hence the "1-dimensionality" of the binary search trees.

But in 2D space-partitioning for example, your data lives in a 2D space and you can not simply order them from "smallest" to "biggest". You need more freedom in the way you cut your space in half.

The trees themselves are just binary trees in both cases, the "dimension" comes from what the nodes represent and how the trees are used.


$O(n \log n)$ algorithm for disjoint segment visibility problem

W.o.l.g. we could assume $P$ is the origin point $(0,0)$.

List the endpoints of all segments, represent them in polar coordinate $(\theta,\rho) \in [0,2\pi) \times [0,\infty)$ and sort them by their degree.
Imagine there is an ray from $P$ pointing to the right, we sweep it for one round (by gradually changing its direction $\alpha$ from 0 to $2\pi$).  Let $R(\alpha)$ denotes the ray from $P$ to direction $\alpha$.  We wonder what's the segments $R(\alpha)$ hits, and what's their order on $R(\alpha)$.
Find out all segments hit $R(0)$, and sort them by their order on $R(0)$.  Store them in a balanced binary search tree (e.g. red-black tree).
Iterate over the points we found (and sorted) in step 1:
Each point $(\theta,\rho)$ indicates a segment would start/stop hitting the ray $R(\alpha)$ when $\alpha$ increase to $\theta$.  Update the binary search tree accordingly.
The elements that once be the smallest one in the binary search tree are the segments visible from $P$.

It's easy to check that the runtime of above algorithm is $O(n \log n)$.


Functor in category theory: The free theorem for fmap

Composition following from identity does not hold for the category of sets and functions (to my knowledge), if by that you mean the sets and functions in ZF(C) or the like that mathematicians usually consider. As you mentioned, the given argument relies on parametricity, and the functions definable in set theory needn't be parametric. In fact, assuming that all functions are parametric is anti-classical. Even in constructive scenarios which could admit parametric models, people might want to keep their options open.
It's probably not a huge surprise in light of the above, but things aren't going to work out in a lot of other situations, either. For instance, the argument you referenced is essentially appealing to parametricity to obtain naturality, because parametricity is a stronger requirement than naturality (based on a notion that doesn't involve composition). However, Haskell functions (or those of similar systems) are parametric with respect to a specific sort of "logical relation" that subsumes naturality with respect to a specific category. This parametricity does not automatically imply naturality even with respect to certain related categories. For instance, if you consider functors $\mathsf F, \mathsf G : \mathsf{Type}_M → \mathsf{Type}$ from a Kleisli category, then a parametric function with type $∀ a. \mathsf F(a) → \mathsf G(a)$ is not automatically natural. So, there are examples like this where functoriality doesn't automatically follow just from the identity rule.
For instance, consider the Kleisli category for lists. There is a functor:
$$\mathsf F : \mathsf{Type}_{\mathsf{List}} → \mathsf{Type}$$
$$\mathsf F\ A = \mathsf{List}\ A$$
where the action of $\mathsf F$ on arrows is given by the following code:
-- drops one element of the list unless it has only one element
contract : List A → List A
contract (_ :: xs@(_ :: _)) = xs
contract xs = xs

mapF : (A → List B) → List A → List B
mapF f [] = []
mapF f (x :: xs) = contract (f x) ++ mapF f xs

This action on arrows doesn't satisfy the composition rule, but it does satisfy the identity rule. There is a functorial action for this object mapping (it is the 'bind' operation), but mapF is another function with the same type and behavior on the Kleisli identity arrow (pure or return in Haskell).
I would imagine that composition following from identity is the exception rather than the rule.


Description of lists with functions in LISP

In PL theory, this is known as (a variant of) the Church-encoding of pairs.

The idea is the following: assume for the moment you only have a language with primitive  booleans (true, false, if-then-else) and primitive (first-class) functions. Pairs are not primitive, yet they can be encoded as follows.

In place of a pair $(x,y)$ we can consider the following function:
$$
p(b) = {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y
$$
It is immediate to verify that $p({\sf true}) = x$ and $p({\sf false}) = y$. So this function $p$ indeed encodes the information which lies inside a pair. Projections can then be defined as
$$
\pi_1(p) = p({\sf true}) \qquad
\pi_2(p) = p({\sf false})
$$
while the pair constructor becomes
$$
cons(x,y) = \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y
$$

Now, suppose we no longer have primitive booleans/conditional, but only have functions. We can still obtain something which behaves as a boolean through this encoding:
$$
{\sf true} = \lambda x y. x \qquad
{\sf false} = \lambda x y. y \qquad
$$
and (since now a boolean $b$ is a "binary" function)
$$
{\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y = b x y
$$
It is immediate to verify that
$$
{\sf if}\ {\sf true} \ {\sf then}\ x \ {\sf else}\ y = {\sf true} x y = x
$$
and the $\sf false$ analogous.

Once you combine both encodings, you get that
$$
\begin{array}{l}
cons(x,y) \\
= \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y \\
= \lambda b. b x y \\
\end{array}
$$
and
$$
{\sf car} = \pi_1 = \lambda p. p {\sf true} = \lambda p. p (\lambda x y. x)
$$
and its $\sf cdr$ analogous.

The LISP encoding you have is very similar to this encoding: it only have a few more twists for encoding $\sf nil$ as well, but that's a minor point.

The variable name $k$ which appears there in place of the "boolean" $b$ likely stands for "continuation", which is a key notion in PL theory.


Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?

What you are asking is simply how to balance a binary search tree (BST) $T$. By the way, the phrase "un-balanced AVL tree" is somewhat confusing since AVL tree is height balanced by definition.

If there is enough space for a whole new tree, then we can simply construct a new AVL tree from scratch, by removing one element from the $T$ and inserting it to the new tree repeatedly. You may call this cheating. While I would agree with you if I were on your side, I can also argue this is just an alternative simple way of balancing a BST, although slightly revolutionary and possibly heavy. Note that we can improve the performance of this approach by taking advantage of the fact that $T$ is a BST, as shown in the exercise 2 below.

Suppose we do not have that much space. Here is how we can balance $T$ in-place. Count the number of nodes in the left subtree of the root node and the number of nodes in the right subtree of the root. If their difference is greater than one, then let us find $m$, the median node of all nodes when the number of all nodes is odd or one of the two median nodes of all nodes when the number of all nodes is even.

Suppose $m$ is the left child of its parent node. Consider $R$, the right subtree of $m$ and $T'$, which is $T$ with the subtree with root $m$ removed. Note that all nodes of $R$ is smaller than all nodes of $T'$. So we can merge $R$ and $T'$ into a new BST $T''$ easily in $O(1)$ operations. Now set the right subtree of $m$ to $T''$ and set $m$ to be the root.
Otherwise $m$ is the right child of its parent node. This case is symmetric to the above case.

Now we have obtained a BST tree whose root is a median of all nodes. Repeat the process above on its left subtree and right subtree, as long as the subtree has more than 2 nodes. In the end, we will obtain a BST where the difference of the number of nodes in the left subtree and the number of nodes the right subtree of any node is at most 1. Let us call this kind of BST "optimally-balanced". Intuitively and apparently, you cannot make a BST more balanced than an optimally-balanced BST. It is not hard to prove that an optimally-balanced BST must be an AVL tree.

I might have skipped over a few boundary cases and a few finer points in the above explanation. Hopefully, the above is able to convince you that the answer to "is it possible to balance an already constructed 'un-balanced AVL tree'" is positive once you have taken some time to reflect.

Here are several related exercises that you can think about. $T$ is a given BST with $n$ nodes.

Exercise 1. Show that an optimally-balanced BST must be an AVL tree.

Exercise 2. If there is enough space, convert $T$ to an AVL tree in $O(n)$ time.  (Hint, convert $T$ to a sorted array first.)

Exercise 3.  With $O(1)$ working space, balance $T$ into an AVL tree in $O(n)$ time. (This might be a difficult exercise.)


Can a quantum computer (theoretically) do things a classical computer (literally) can't?

No. Quantum computers cannot solve undecidable problems.

A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation.  However, we already know that if a problem has no classical solution, then it must not have a quantum solution either.

Also, you said:

  that's "just" because the quantum computer is more powerful than the classical one.

This is an open problem.  We do not yet know if $BPP \subset BQP$.


Turing machine that accepts language with more a's than b's

Sit before a big empty sheet of paper. Write down a sequence of a's and b's. Now mechanically check whether that string should be accepted. You cannot use counting, that would be requiring an infinite number of "states" inside your head.
You can however use additional symols. A striked out b is just a new symbol that is written on the tape.

Turn your intuition into an algorithm. First informally, that is what Karolis has done. Then add information on how to implement this on a Turing tape. What direction is the head moving? Where will it stop? Then translate the whiles and untils into states and transitions (sort of goto-programming, which is improper unless you are programming a TM).

If you are a CS student, then you can do these steps. You can program. No matter whether it is C++, assembler, or Turing. That is just details.


3-SAT with negative-literals in each clause

Consider the all-zeroes assignment, $x_1=x_2=\cdots=x_n=0$.

What if all clauses have a positive literal?


Does local optimization in a genetic algorithm decrease diversity?

Adding on Raphael's answer:

in a hybrid genetic algorithm (HGA), mutation plays a different  role than it does in a "pure" GA.

The local refinement requirement of the mutation operator is unnecessary in the existence of an explicit local operator allowing the mutation operator to take a more exploratory role (see Evolutionary algorithms with local search for combinatorial optimization by Mark Land).

Using larger mutations, at least large enough to move from one basin to another, is a good idea.
you can introduce parameters to control the frequency / duration / probability of local search so reaching a balance between GA and hill climbing.

Hybrid Genetic Algorithms: A Review by Tarek El-Mihoub, Adrian Hopgood, Lars Nolle and Alan Battersby contains further details.
a nice approach you can try is to perform a local search only when the best offspring (solution) in the offspring population is also the best in the current parent population (aka BOHGA:  Best Only Hybrid Genetic Algorithm).

This allows GA to explore a wide search space.


Good snapshottable data structure for an in-memory index

Use any kind of persistent/immutable (i.e., functional) tree-based data structure.  The key is getting the locking right, as @Raphael pointed out in the comments.

The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free.  Let's suppose you use a treap (randomized binary search tree) for your data structure.  Here's an example of one written in Go: https://github.com/steveyen/gtreap.  The author describes it thusly:

  By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.

At any point in time the "current" state of the tree is represented by a pointer to the root of the tree.  Insertions are non-mutating.  Instead an insertion keeps the previous version of the tree completely intact, creates $O(\log n)$ new nodes for the path from the root to the correct insertion point, with pointers back to the nodes of the previous version that can be shared.

You use a lock to protect the pointer to the root.  Since the data structure is immutable reads can be done concurrently, and you can save pointers to old snapshots.  A read is:

lock
tmp = ptr_to_root
unlock
value = search(tmp, <value to search for>)
return value

Even though the search may take a while, you only hold the lock while copying the pointer, so the searches can happen concurrently.

A write is:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
unlock

In this version, writes do need to hold the lock during the entire process of creating the new version of the tree.  You can improve read performance (at the cost of sometimes having the write transaction fail) by changing the write to something like this:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, <new key/value pair>)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top

You may be able to do even slightly better (make it "lock free") if your programming language has atomic variables with an atomic compare-and-swap operation.  (For example by using C++11's atomic<T*>.)


How to find the pumping length of a context-free language?

As Raphael says in the comments, any sufficiently large number is suitable as a pumping length, however (also as he points out), the proof of the pumping lemma gives an upper bound for the minimum pumping length.

Similar to the pumping lemma for regular languages, we want to take a length that is sufficiently large that we can guarantee that we have used the same production at least twice. For regular languages this often easy to think of as the number states in a minimal DFA for that language.

For context free languages expressed with a grammar, we can take a similar approach and ask "how many symbols can be in the string before I know that I must have used some production twice?". To figure this out you may want to consider how many symbols any production could insert into the string, and what the parse tree for a sufficiently long string may look like (you can consider each level of the tree to be one production). If you do this correctly you can get a minimal pumping length for that grammar (not exactly a precise concept), then taking the minimum of these minimal lengths over all grammars for the language will give you the minimum for the language.

Further hint:

   If there's a rule with $m$ symbols on the right hand side, and the parse tree is $d$ levels deep, what's the maximum number of symbols in the string?


When and how to generate parse tree while top down parsing

As the name indicates, the parse tree is generated top-down. Specifically, you start with a place-holder node for the start symbol. Each time you predict a production, you fill in the placeholder with the right-hand side of the production, where each symbol is represented by a placeholder. Each time you shift over a token, you fill in the placeholder with the token's semantic value.

Since parsing nodes are expanded into the tree before their children, it's not possible to compute synthesized attributes with this algorithm, although inherited attributes can be computed when the node is predicted. You can slightly modify the algorithm to allow the computation of synthesized attributes by adding an "end production" pseudo-token at the end of every production. When a such a token is encountered, instead of shifting a token from the input, the code associated with the production is executed to fill in the synthesized attributes. However, it might be easier to compute attributes post-parse by performing one or more traverses over the parse tree.


Depending on the architecture, the immediate for branches may mean a byte address (x86) or a word address if fixed width instructions are mandated, which means that for a 16bits offset, the range is something like -2^17 to +2^17-1

Having fixed 64bits-wide instructions is quite rare (VLIW domain). If you add 32 bits, and if you keep the same number of registers (hence 5 bits for RS and RT) and the opcode part, I guess these extra bits would end in the offset part, so 16+32bits offset.
If instructions are fixed width, you may then have doubleword offsets : -2^-50 to +2^50-1

Practically, it does not make any sense to have such wide immediate offsets. No program is large enough to be several gigabyte long (I'm not counting libraries, which are generally called through indirect or direct branches over the full 32bits or 64bits address range, not conditional branches).

I could imagine that with 64bits instructions, some variants of the conditional branch instructions would offer 16 to 32bits immediate values, like : "BNE R1,#1234, @Somewhere" instead of using 48bits for the offset.


Why do we use worse-case when categorising problems?

Because average case requires a definition of "average". Specifically, average over what distribution of inputs?

Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing.

On the other hand, average-case doesn't necessarily correspond to anything very much. Suppose you just take the uniform distribution over inputs of a given length. Why would you feel that the mean number of steps the algorithm takes is a useful measure of anything? Probably your inputs don't look much like a uniform distribution. The mean based on any distribution doesn't give you any guarantees about actual performance on specific instances.

Also, and this might, sadly, be the real reason, average-case complexity is hard. It means you have to understand how the algorithm behaves on essentially all possible inputs, and getting good bounds for all kinds of input is a lot of work.

One place where average-case is used is amortized analysis.  Consider a dynamically sized hash table where, if the table is more than, say, three-quarters full, you copy everything into a new table that's double the size.  In this situation, inserting an element into a table of size $n$ can take up to $2n$ steps, which is horrible in the worst case. However, you only need to do this expensive copying operation once every $3n/4$ steps. On average, then, each insert operation causes $2n/(3n/4)=8/3$ amount of the work needed to double the size of the hash table. So, in a very strong sense, the average cost of growing the table is just a constant amount per insertion, and this is completely independent of what insertions are done.  This is practically very useful when analyzing algorithms that use hash tables.


Constructing a NFA from a regular expression

Your solution is nearly correct, however you need to remove the $c$-transition of $S_0$ and the $a$-transition from $S_0$ to $S_2$ and add a new state, say $S_3$, which is reached from $S_0$ via an $\varepsilon$-transition, has a $c$-transition to itself and an $a$-transition to $S_2$ (so that the word $cab$ is not recognized anymore, see benrg's comment below).
As for a general algorithm not that REs are built in a recursive manner by taking the symbols in your alphabet as "atoms" and then chaining them together using the basic operations $+$ (or $\cup$ as you denote it), $\ast$ and concatenation.
A NFA accepting the same language can then be built in a similar manner:

If the RE is just an atom $\alpha$, consider the NFA with one $\alpha$-transition to an accepting state
Suppose our RE is of the form $XY$ where $X$ and $Y$ are REs themselves and let $\mathcal A_X$ and $\mathcal A_Y$ denote the NFAs representing $X$ and $Y$ respectively. A NFA for $XY$ can be constructed by taking the NFAs $\mathcal A_X$ and $\mathcal A_Y$ and adding $\varepsilon$-transitions from all accepting states of $\mathcal A_X$ to the initial state of $A_Y$ and making the states of $\mathcal A_X$ not accepting.
Suppose our RE is of the form $X^\ast$ where $X$ is an RE. Take the associated NFA $\mathcal A_X$ and add $\varepsilon$-edges from its accepting states back to the initial one, which also needs to be made accepting.
Suppose our RE is of the form $X + Y$ where again $X$ and $Y$ are REs. Take $\mathcal A_X$ and $\mathcal A_Y$ and add a new initial state that has $\varepsilon$-transitions to the initial states of $A_X$ and $A_Y$.

Of course, this algorithm does not produce "optimal" NFAs, but it is a simple and general procedure to generate an NFA which accepts the same language as some given RE.


Which architecture do modern computers use?

Modern general-purpose high-performance processors use separate instruction and data caches, and so could be classified as modified Harvard even though they use a unified address space. (Some microcontrollers—usually to provide extra memory or protection without a memory protection unit—use a Harvard architecture in which data and code use separate address spaces.)

x86 might be considered a little more nearly "pure" von Neumann than some other ISAs in that self-modified code is guaranteed to be handled properly if a jump is used. Many other ISAs require an instruction synchronization instruction and may require explicit invalidation of any modified memory from the instruction cache (i.e., the instruction cache is not necessarily coherent).

Cross-modified code is somewhat more complex; even x86 requires a synchronizing instruction.


This problem is known as Euclidean $k$-center problem and is known to be NP-complete. There are some approximation algorithms but we don't have any PTAS algorithm.

Of course for $K \geq N$, the solution is trivial, with optimal value 0.


How does image reconstruction take place in neural network?

A plain CNN normally isn't used to produce an image as output; but if you combine it with deconvolution layers, then you can produce an image as output.


One option to generate the parse tree of the grammar, and check all the leaf strings if they are odd-parity absent. Even if you have recursive rules, one application of each rule is enough, because multiple occurrences of the same element does not affect the result.

However, there might be an easier way. Consider the following grammar on {a,b,c,d,e} alphabet with the following rules:

S -> A | B
A -> Abc | C
B -> cd | De
C -> aa
D -> b

Now you can assign odd-parity variables to each state. For example, a string at state S has number of missing instances = m (m=5 in this case). Let's denote it with p(S)=5.

From the first rule, p(A)=p(B)=p(S)=5. At the second rule, p(A) becomes 3, because at the first branch it eliminates 2 missing characters. Also p(C)=3, because p(A)=p(C), all other elements are missing.

At the third rule, p(B)=3 and p(D)=4. Fourth rule indicates p(C)=2 (2 a's, but the same element). Finally, p(D)=3.

Checking all ending states, p(B)=3, p(D)=3, and p(C)=2, which means the grammar has odd-parity. Verbally, there might be strings that end up with 3 elements missing, if they end up in state B or D.

In this way, you can decide if the grammar is odd-parity absent, just by looking at the grammar. The pseudo-code would be:

consumed_elements_set(S)={}
for each rule X with L as left-hand side:
    for each state R on the right hand side:
       consumed_elements_set(R)=consumed_elements_set(L)+terminals(X)
       p(R)=m-size(consumed_elements_set(R))
for each final state F:
    if p(F) is odd:
       print "not odd-parity absent!"


Algorithm to find what points are the nearest to other points

Use a data structure designed for nearest neighbor search.


Physical significance of Don't cares in Digital Logic design

Yes they do have physical significance.Input combinations  for which value of a function ( or a device) is not specified are called don't care conditions.
They are met when the number of inputs are more than expected.
For example, conversion of binary to BCD. Both are 4 bits long but using 4 bits 16 binary numbers are possible whereas only 10 BCD numbers.

Consider another example: Suppose there are 8 locations to be addressed and we have a total of 4 address lines. To address 8 locations we only need 3 bits hence three address lines. The forth extra address line is like dont care. We actually don't care the logical value of contained in that address line.

Actually don't cares allow us to choose from a class of many functions.
Each don't care bit represents 2 values {0 or 1}, hence a function containing 'k' don't care bits correspond to a class of $2^k$ distinct functions ( as 'k' inputs can give rise to $2^k$ combinations).
The task is to choose a function out these $2^k$ functions which has the most minimal representation. Thereby decreasing the number of inputs hence making the implementation faster.


If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

Probably not, since clauses can be encoded using only linear inequalities.
http://web.stanford.edu/~rrwill/cnf-sat-feasible.pdf


Maximizing a convex function with a linear constraint

Yes, Convex Optimization with equality constraint is NP-Hard in general. However, there exist mature techniques that find very nice approximate solutions to convex optimization problems, like Coordinate Descent.

Suppose you use coordinate descent and the matrix A has rank $k$. You can fix n-k-1 coordinates of your feasible solution $x = (x_1, x_2, x_3, ..., x_n)$ and then the solution vectors in the solution space are uniquely determined by one coordinate, for example $x_i$. In that case, you can just take the derivative of $f(\cdot)$ with respect to $x_i$ to find the maximum in this iteration.

Then we iteratively fix n-k-1 coordinate and improve the solution until a approximately optimal one is found.


Running time complexity of finding maximal power of divisor that divides natural number

Here is one more approach you could consider, depending on whether you care more about theoretical running time or pragmatic solutions:

Use binary search to find the smallest $k$ such that $p^{2^k}|n$ but $p^{2^{k+1}}\not|n$.
Compute $m = (n/p^{2^k}) \bmod p^{2^k}$.
Recursively find the smallest $i$ such that $p^i|m$ but $p^{i+1}\not|m$.

(In the third step, you know $0 \le i < 2^k$, so you have a narrower range for your search, and $m$ is smaller than $n$, so you are working with smaller numbers.)

Then it follows that the solution to your problem is $e=2^k + i$.

Note that $k \le \lg {\log n \over \log p}$, so you can find $k$ with binary search in $O(\log \log {\log n \over \log p})$ steps, where each step does a single trial division.  In the worst case, $m$ might not be much smaller than $n$, so this might not save you much.  But in many cases, $m$ will be vastly smaller than $n$, so step 3 is a lot easier than the original problem.  In particular, on average $m$ will be on the order of magnitude of $\sqrt{n}$ or less, so heuristically we might expect that after $\lg \lg n$ recursions we're dealing with constant-sized numbers, and heuristically we might expect the total running time to be dominated by step 1.  This won't always be true in the sense of worst-case complexity, though.


What's the regex corresponding to this DFA?

$$(00^*10^*1 ~~~ | ~~~ 10^*(10)^*110^*1)^*~~~10^*(10)^*110^*$$
This should be one representation. Not sure if it could be made simpler. The part from $($ to $|$ represents one lap in the upper cycle. The part from $|$ to $)$ represents a lap in the lower cycle. The last part represents the path from $A$ to $D$.


Difference between capacity miss and conflict miss

It will be capacity miss because capacity miss means that your cache is full and there is no way to accommodate the data A.
Yes it means Once the cache is fully occupied, conflict miss will never happen.


Consider a directed cycle from $A$ to $B$ and back with the minimum number of nodes, and subject to that, with the minimum number of edges. The directed cycle is composed of two paths: $A\to B$ and $B\to A$. Since the cycle minimizes the number of edges, these paths are simple. However, it may be that the two paths are not disjoint. If so, let $x$ be the first node on $B\to A$ which appears in $A\to B$. This decomposes the cycle as follows:
$$ A\to x \to B \to x \to A. $$
By construction, the cycle $x \to B \to x$ is simple (no nodes are repeated). Also, the condition on the number of edges guarantees that all nodes on this cycle do not appear in $A\to x$ or $x \to A$ (otherwise, we could take shortcuts that would shorten the cycle). Therefore, if we denote the optimal cost of an $A\to B\to A$ cycle by $c(A,B)$ (excluding the two endpoints) and the optimal cost of a simple $A\to B\to A$ cycle by $s(A,B)$, we have
$$
c(A,B) = \min(s(A,B), \min_x c(A,x) + s(x,B) + 1).
$$
We can compute $c(A,B)$ iteratively: start with $c(A,B) = s(A,B)$ (which you know how to compute), and then repeatedly apply the equation above until the situation stabilizes, which should happen within $n$ iterations or so.


Etymology of time and space "complexity"

Complexity refers to the complexity of the computation rather than the complexity of the algorithm. For example, Ritchie's Classes of predictably computable functions from 1963 "[studies] a sequence of classes of computable
functions for which a prediction of the complexity of the calculation may be
made in a comparatively simple fashion."

Hartmanis and Stearns, in their seminal 1965 paper On the computational complexity of algorithms, also use complexity in a similar sense: "One finds, however, that some computable sequences are very easy
to compute whereas other computable sequences seem to have an inherent
complexity that makes them difficult to compute." This paper is the source of the terminology, though they cite earlier papers (like Ritchie's from 1963) which had already used complexity in this sense.


Does a notion of a context-free complete language exist?

Yes.

Lautemann and Schwentick prove that Greibach's "hardest context-free grammar" with a neutral symbol is complete for $LOGCFL$ and hence $CFL$ also, under quantifier-free projection without BIT.

This is Corollary 4.3 in their paper


A specific version of a job scheduling problem

This scheduling problem is called non-preemptive job shop scheduling.  The classic reference is

  Edward G Coffman, Jr, and Peter J Denning: Operating Systems Theory, Prentice-Hall, 1973.

Job-shop scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the flow shop problem where the $a_i$ are in the same order for every task.)

It is called job shop scheduling because most of the early work on it was done by industrial engineers who were trying to optimize work schedules for machines in a factory, rather than computers.


Time complexity of heapsort is $O(n \log n)$ for all types of input. If we have all input we need $O(n)$ time to build the max-heap. Then for sorting the the data, we need to remove the first element of the array then heapify the remaining data and repeat it for $n$ times. Which the act of heapifying for all steps needs $O(n \log n)$ time.


Lowest common ancestor similar algorithm for a graph

If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime complexity is not as good as I would have expected intuitively. I asked a related question some time ago, but was too lazy to write an answer after I found the relevant solution in the "literature". I just wrote the answer now, and it starts as follows:

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg.
Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

Here is the relevant part from chapter 2.3.1:

We now give an $O(n + |e_\prec|)$ algorithm to compute the join of two elements $x$ and $y$. The algorithm returns $null$ if the join does not exist. We first assume that we are using the cover relation. To compute $join(x,y)$, we proceed as follows:

Step 0: Color all nodes white.
Step 1: Color all nodes reachable from $x$ as grey. This can be done by a BFS or a DFS starting from node $x$.
Step 2: Do a BFS/DFS from node $y$. Color all grey nodes reached as black.
Step 3: We now determine for each black node $z$, the number of black nodes that point to $z$. Call this number $inBlack[z]$ for any node $z$. This step can be performed in $O(n + |e_\prec|)$ by going through the adjacency lists of all black nodes and maintaining cumulative counts for $inBlack$ array.
Step 4: We count the number of black nodes $z$ with $inBlack[z]$ equal to $0$. If there is exactly one node, we return that node as the answer. Otherwise, we return $null$.


Instruction-level parallelism, data-level parallelism, loop-level parallelism, and task-level parallelism are not well defined terms.  The definable concept is parallelism.  Two operations can run simultaneously (or "in parallel") when the portions of the state they write are non-overlapping, and when the portion of the state written by each operation does not overlap with any of the state read by the other operation.

So two different instructions can run in parallel when the registers and memory they read and write don't overlap.  The sub-operations of a SIMD instruction can run in parallel because they are defined to only perform sub-operations that each read or write different portions of a vector register or cache line.

I like to say

  parallelism is as parallelism does

and what parallelism does is run multiple operations simultaneously.

The benefit of SIMD instructions, over just using 4 or 8 or N individual instructions that perform the same sub-operations, is that the fetch, decode, renaming, and scheduling units of the processor don't need to do as much work to exploit the parallelism between the sub-operations.


Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem

$\newcommand{\Y}{\mathsf{Y}}$

Did you leave out any parentheses by any chance? We should take $\Y = (\lambda  u x . x (u u x)) (\lambda  u x . x (u u x))$. Note that $x u u x$ is the same as $(x u u) x$, which is not the same as $x (u u x)$.

We use the abbreviations $V = (\lambda x y_1 \ldots y_n . Z)$ and $X = \Y V$, as in your question. Then we calculate:
\begin{align*}
\Y V
&= (\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) V \\
&= (\lambda x . x ((\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) x)) V \\
&= V ((\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) V) \\
&= V (\Y V)
\end{align*}
and hence
\begin{align*}
X y_1 \ldots y_n
&= \Y V y_1 \ldots y_n \\
&= V (\Y V) y_1 \ldots y_n \\
&= (\lambda x y_1 \ldots y_n . Z) (\Y V) y_1 \ldots y_n \\
&= (\lambda x y_1 \ldots y_n . Z) X y_1 \ldots y_n \\
&= [X/x, y_1/y_1, \ldots, y_n/y_n] Z \\
&= [X/x] Z.
\end{align*}


What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

A boolean function is called balanced if it is zero on half its inputs and one on half its inputs.  So, "balanced" might be the term you are looking for.


Nonuniform input distributions in average case analysis

Yes, the expected running time under some other distribution would still count as an example of average-case analysis.  However, when you describe it to someone, make sure you explain what distribution you're using.  I wouldn't recommend that you just call it "average-case analysis" without also explaining that you're using a non-standard probability distribution.

The worst-case distribution is always a point distribution that assigns all its probability to a single input.  In  other words, the worst-case probability distribution that makes the expected running time as large as possible is in fact just a single input: the input that makes the algorithm run as long as possible.  Consequently, this kind of worst-case analysis coincides with the "standard" notion of worst-case running time.  For this reason, there is no need for a special "name" for this; worst-case running time already covers it.

The same is true for best-case running time and the probability distribution that makes the expected running time as small as possible.


Let me answer the last question first.  It points out that the paper was written in 2002, when multi-core processors were much more expensive.  I think the authors were largely concerned with optimizing for the single-core case.

  ... how [is] random fairness ... any better on uni-processor systems in comparison to multiprocessor systems.

On a uniprocessor only one process can be scheduled at a time.  So everyone gets "woken up," but that just means they get moved from a waiting state to a ready state.  Then the scheduler is invoked and it chooses one of the ready processes to run, and lets that process run for some period of time.

The first thing the newly running process does is acquire the lock.  Then it does some processing and (if you are not unlucky) releases the lock.  In this case the next time the kernel scheduler gets control it chooses another "ready" process and starts it running.  If the first process released the lock, then the second process will acquire it, and so on.

On a multiprocessor on the other hand, all the processes might get "woken up" and then the scheduler starts some/many/all of them running simultaneously on different processors.  One of the processes will acquire the lock, but all the other processes will try to acquire the lock, immediately fail, and put themselves back to sleep on the wait queue.  So on all the processors but one you just wasted several kernel calls and several context switches just so you could tell a bunch of processes that there was nothing to do.

  does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

I think the case they have in mind is if you have multiple processes (on one processor), where each process acquires the same lock repeatedly for short periods of time.  In the unfair case the first process can run for a while and acquire and release the lock many times without doing a context switch.  Then the second process runs for a while and acquires and releases the lock many times.

In the "fair" case the first process locks/releases and then the second time it tries to lock it must be put to sleep, and the kernel has to do a context switch and wake up the other process.  The processes ping-pong back and forth doing "wake up, lock, unlock, work a little while, try-to-lock, get put to sleep."

  how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

I think they are making the observation that, on a uniprocessor, shortest-job-first (unfair) has shorter average wait times than does round-robin (fair).  But I don't understand how random decreases the average wait times compared to round-robin.


walk / traverse a disjoint set that has union rank and path compression

None of the hacks in the question are necessary, since it's definitely possible to merge two singly linked circular lists without maintaining any additional tail pointers.
Suppose you have heads x and y of two separate circular lists. We first save xn = x.next. Then, set x.next = y.next. Then, set y.next = xn. After these, it's easy to see that the two circular lists have been merged.


NP-completeness of solving quadratic equations over $\mathbb{Z}_2$

You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your problem is NP-hard. Showing that it is in NP is easier.


how is an arbitrary dimension "reshaper" turned into a function given a linear index?

If the index of $(i,j,k)$ is $p = i + xj + xyk$ then you can compute $i,j,k$ given $p$ as follows:

i = p mod x
j = (p / x) mod y
k = (p / x) / y

Using this you can solve your problem.


How does one simulate continuous gravity using a discrete timestep?

This is an example of Euler's Method

Using differentiation, you can find a better formula. Since discrete calculations only "drift" if they are non-linear, you only need to alter the position/time calculation.

// Repeat once per frame
position += velocity * deltaTime + gravity * Math.pow(deltaTime, 2.0) / 2.0;
velocity += gravity * deltaTime;

Even large timesteps align perfectly with the continuous graph:


After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected deterministically so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not necessarily give the certificate minimal among all possible discrete partitions, but rather minimal among some subset of them.


Find Length of longest substring with all 1's in a binary string with k queries

Observation: Type 2 query can only make the longest substring of 1 longer.

Let's call a substring of 1's a component. For example, there are 3 components in this string

1 1 1 0 0 1 0 1 1 1 1 0

When a 0 is changed to 1, only the components to its immediate left and right will be affected. The length of the other components remains the same.

string: 1 1 1 0 0 1 0 1 1 1 1 0
size  : 3 3 3 0 0 1 0 4 4 4 4 0

update position 7 to 1 (1-index)
string: 1 1 1 0 0 1 1 1 1 1 1 0
size  : 3 3 3 0 0 6 6 6 6 6 6 0

Hence, all you need to do is to keep track of the size of each component and merge them when necessary. You can do so using a Union-Find Disjoint Set data structure. You can have a variable to keep track of the size of the largest component and update its value if, after the merge, you get a larger component.


Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

Brooks' theorem states that every connected graph $G$ with maximum degree $\Delta$ can be colored (in linear time) using at most $\Delta + 1$ colors. In fact, the graphs that require $\Delta + 1$ colors are precisely complete graphs and odd cycles.

You state that we have a connected graph $G$ with an odd number of vertices and we want to color $G$ with $k$ colors, where $k = \Delta + 1$ when $\Delta$ is even and $k = \Delta$ otherwise. Let's break this down into cases:

$G$ is complete (i.e., $G$ is $K_n$ for $n = 3,5,7,\ldots$). By definition, $\Delta = n-1$ and since $n$ is odd, we have that $\Delta$ is even. Thus, we can color $G$ with $k = \Delta+1$ colors.
$G$ is a cycle (i.e., $G$ is $C_n$ for $n = 3,5,7,\ldots$). Clearly, for any non-trivial cycle we have that $\Delta = 2$ which is even. Again, we can color $G$ with $k = \Delta+1$ colors.
$G$ is not complete nor a cycle. By Brooks' theorem, we have that $\chi(G) \leq \Delta \leq k$, so we are done.


Closure of regular languages to shuffle using closure operations

The idea is to create two copies of the alphabet $\Sigma$, say $\Sigma_1,\Sigma_2$; each $\sigma \in \Sigma$ corresponds to $\sigma^{(i)} \in \Sigma_i$. You now show that the following languages are regular:
$$
\begin{align*}
\tilde{L}_1 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : a_1 \ldots a_n \in L_1 \}, \\
\tilde{L}_2 &= \{a_1^{(1)}b_1^{(2)}\ldots a_n^{(1)}b_n^{(2)} : b_1 \ldots b_n \in L_2 \},
\end{align*}
$$
where in both cases only some of the letters are constrained. Now take $\tilde{L}_1 \cap \tilde{L}_2$ and transform it to $L$.

I leave the rest of the details for you to complete.


Arithmetic coding and "the optimal compression ratio"

Beware: The phrase "optimal compression ratio" is perhaps a bit misleading.  It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it comes with -- you should really think of it as "the best compression ratio that is achievable, under a certain set of assumptions" (or "the best compression ratio that is achievable by a certain type of compression algorithm").  Since those assumptions often aren't literally true, there's no real guarantee that this is truly the smallest something can be compressed to.

In particular, one key assumption is that the symbols come from a memoryless iid source: i.e., there is a distribution on characters, and each character is sampled randomly from this distribution, independent of all previous characters.  For a source that satisfies this assumption, we can calculate the best achievable compression ratio; it is the entropy.

Of course we know this isn't true in practice; in English text, if the previous letter was 'q', the next one is much more likely to be a 'u' than otherwise.  So really you should think of the entropy as telling you "if you didn't take advantage of that type of knowledge, what is the best compression ratio you could achieve?".


I would like to rank the strength of those three Athletes based on their speed and endurance.

There is an infinite number of ways of doing that. The two lexicographic orders and weighted sums are only a few examples.

What do you really want?

  I would like to give a slightly greater weight (0.6) to the endurance.

This suggests that you want (linear) weighted sums. If that is to make sense, you need to normalize your values to a shared scale. You don't give units or ranges, so I'll have to guess.

Normalizing with the maximum values in the sample and assuming that values $0$ are possible, a weighted sum that gives weight $p \in [0,1]$ to endurance and $1-p$ to speed looks like this:

$\qquad\displaystyle w(a) = p \cdot \frac{\operatorname{end}(a)}{64} + (1-p) \cdot \frac{\operatorname{speed}(a)}{12}$.

Implementing this is so straight-forward that it's barely worth being called "algorithm"; you'll certainly find nothing in a textbook that lays out the details for your. Just code it down.


You are correct with $L^* = L^0 \cup \emptyset$.

But $L=\emptyset$ does not imply $L^0 = \emptyset$. Consider $L^i$ to be built incrementally: You start with $\epsilon$ and then add a word from $L$ to the end $i$ times.

If $i\ge 1$ and $L=\emptyset$, this will fail when you try to add the first word, since there are no words in $L$. So here $L^i$ becomes $\emptyset$. But for $L^0$ you never try to take a word from $L$. So the fact that $L$ is empty does not matter, you simply terminate after initialising your word as $\epsilon$.

Thus $L^0=\{\epsilon\}$ and $L^* = \{\epsilon\} \cup \emptyset = \{\epsilon\}$.


What is the shortest total path between pairs of points?

This appears to be a maximum matching problem.  Well, minimum matching, but you should be able to make the necessary adaptations.


You reduce $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ (for any $\epsilon < 1/20$) to $A$. The reduction is the identity function. Let's see why it works:

If a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has an independent set of size at least $(1/4-\epsilon)n \geq n/5$.
If a graph $G$ is a NO instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has no independent set of size $(1/8+\epsilon)n < n/5$.

Hence a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ if and only if it is a YES instance of $A$.


Why is selection sort faster than bubble sort?

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted.

To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books.  I'll use results from Knuth's Art of Computer Programming.

Average number of comparisons:

Bubble sort: $\frac{1}{2}(N^2-N\ln N -(\gamma+\ln2 -1)N) +\mathcal O(\sqrt N)$
Insertion sort: $\frac{1}{4}(N^2-N) + N - H_N$
Selection sort: $(N+1)H_N - 2N$

Now, if you plot those functions you get something like this:

As you can see, bubble sort is much worse as the number of elements increases, even though both sorting methods have the same asymptotic complexity.

This analysis is based on the assumption that the input is random - which might not be true all the time. However, before we start sorting we can randomly permute the input sequence (using any method) to obtain the average case.

I omitted time complexity analysis because it depends on implementation, but similar methods can be used.


on coq: Why is the proof complete after proving only for one induction when we have more than one variable?

You do not have to prove things by induction. For example, you can prove $\forall n : \mathbb{N} \,.\, n = n$ without induction by applying reflexivity. In your proof, we use induction on $a$, but then we do not need to use induction on $b$ and $c$ because we can finish the proof simply using other methods. We could have used induction on $b$ and $c$, and you should try to do so, to see how unecessary applications of induction just make your proof longer and less clear.

P.S. This has absolutely nothing to do with constructivity.


Can we have a poly time reduction from 2-SAT to 2-Coloring problem?

As rotia mentions in their comment, to make the question meaningful we must restrict the power of the allowable reductions. The two most obvious choices are to allow only logspace reductions or only AC0 reductions.

Since 2SAT is NL-complete (with respect to logspace reductions) whereas 2COL (2-colorability) is in L (this is a non-trivial result which follows from Reingold's theorem), if there is a logspace reduction from 2SAT to 2COL then L=NL, which is considered unlikely. Hence we do not expect such a reduction to exist; a fortiori we do not expect an AC0 reduction to exist.