Are there algorithms for which we cannot determine if they ever halt?

As you point out, the general problem of deciding if a TM stops on any given initial tape content is undecidable. In this answer I'll assume you are talking about the concrete existence (to the point of being possible to indicate, not just demonstrate) of one such machine.

As it happens, the (hypothetical) problem of deciding if a particular TM always halts gets arbitrarily complex as the machines themselves get more complex. It is quite impressive how problems involving even very small machines exist that defy our current understanding. It is possible to conjecture that, for any given limited set of resources, there will be some relatively small machine that is "out of reach", whose behaviour is impossible for us to determine.

Your formula does not add significantly to this idealized scenario.


Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

The PDA first guesses whether $m=n$ or $n=k$. According to the guess, it either just checks that $m=n$, or just checks that $n=k$.
What your heuristic argument suggests is that this language cannot be accepted by a deterministic PDA. You can likely show this by adapting the proof here.


Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

There are a lot of things which could have gone wrong, but it is really hard to say, especially since you don't tell us the bad values of $n_l$ and $p^2$. So for now, here are some comments:

SHA1 is slow relative to non-cryptographic hashes. If you are lucky then your programming language already has a fast hash implementation.
There is no need to take the absolute value of the last 32 bits. Instead, consider it as an unsigned integer (unless you're using a language such as Java which doesn't have them).
Since the last 32 bits of the SHA1 hash are very random, you can take them modulo any modulus that you want (assuming it is small compared to $2^{32}$). There is no particular advantage in choosing a prime or a prime power.
Due to the random nature of the hash, you don't expect sentence snippets falling into the same bucket to have anything in common, unless they're exactly equal.
If everything is random and $n_l/p^2$ is very small compared to $n_l$ then you expect the distribution of balls in each bucket to be roughly Poisson with expectation $n_l/p^2$. Assuming this, for $n_l/p^2 = 3$, the probably to get at least 6 balls in some bucket is roughly $0.084$, so you would expect this fraction of buckets to contain at least 6 balls. Assuming a maximum value of roughly $100,000$ buckets (my estimate from your graph), you expect to see 7 buckets having at least 12 balls. You shouldn't be getting buckets with a few tens of elements, though: the probability of having any bucket with at least 20 balls is at most $8 \cdot 10^{-6}$, for example.

In view of this, I suggest you pick some particular experiment and compare the distribution of the number of balls in buckets to the corresponding Poisson distribution. If you find any major discrepancy (an ill-defined concept), let us know the exact values of $n_l$ and $p^2$ you used.


How to properly calculate the order of growth of an exponential algorithm?

In this answer we assume the arithmetic model of computation, in which each arithmetic operation has cost 1.

The question has bad notation. Define function expt b n to compute b^n as:

expt b 0 = 1
expt b n = b ⋅ expt b (n − 1)

Computing expt b n requires computing n-1, computing expt b (n-1), and multiplying that expression by b. So the cost of expt b n is $2 +$ the cost of expt b (n-1). expt b 0 has cost 0.

Putting the above together, we see the cost of exp b n is $2 +$ the cost of exp b (n-1), $= 4 +$ the cost of exp b (n-2), $\ldots$, $= 2n +$ the cost of exp b 0, $= 2n$.


Implication of Berman and Hartmanis conjecture

Two languages $X$ and $Y$ are $p$-isomorphic if there's a polynomial-time computable bijection $f\colon X\to Y$ such that $w\in X\iff f(w)\in Y$.

Now, suppose that P$\,=\,$NP.  Assuming we're defining NP-completeness in terms of polynomial-time many-one reductions, every language in NP, except for $\emptyset$ and $\Sigma^*$ is NP-complete.  To see this, let $Y\in\mathbf{NP}\setminus\{\emptyset, \Sigma^*\}$ and pick two strings $w_{\mathrm{in}}\in Y$ and $w_{\mathrm{out}}\notin Y$. For any language $X\in \mathbf{NP}$, we can reduce $X$ to $Y$ in polynomial time using the function
$$f(w) = \begin{cases}
\,w_{\mathrm{in}} &\text{if }w\in X\\
\,w_{\mathrm{out}} &\text{if }w\notin X\,.
\end{cases}$$
Since $X$ can be decided in polynomial time, we can compute $f$ in polynomial time.  Note that there is a small error in the proof quoted in the question, which claims that all languages in P would be NP-complete if P$\,=\,$NP.  This is incorrect: if we took $Y=\emptyset$ or $Y=\Sigma^*$, the reduction wouldn't work because one of $w_{\mathrm{in}}$ and $w_{\mathrm{out}}$ wouldn't exist.

So, we've established that, if P$\,=\,$NP, then every finite language is NP-complete; we also know that some infinite languages, such as $\mathrm{SAT}$ are NP-complete.  But now suppose that there's a $p$-isomorphism between every pair of NP-complete languages.  That means that, in particular, there's a bijection between every finite language and $\mathrm{SAT}$. But there can't be a bijection between a finite set and an infinite set.


Data versioning in a relational database

I've seen a thesis on this subject, but that was long ago.

One thing to search for a combination of relational databases and versioning, which will produce things such as tuple versioning; another is temporal databases.

As far as I know, there really is no standard way to address your problem. How best to model it depends on what information you want to be in the snapshot and on how you want to use the information later.

For instance, if you never ever want to pose queries that combine information from different snapshots, you can save each snapshot to a different database.
That allows you to use the same constraints and queries on your snapshots that you use on the live data.

If you never need to pose queries that combine information from your live operational state with information from your snapshots, you probably want to save the snapshots to a different database than the live information. That way, you can at least continue to use constraints and queries on the live data that do not take the extra snapshot information into account.  On the snapshots, you will need to rewrite the constraints and queries. But it will be easier to pose queries that combine information from different snapshots.

To be honest, I don't understand what you mean by "add a header object/table for all relevant input data". If all of the snapshots are put into the same database, without creating separate tables for each snapshot, I expect to see one or two columns for every table whose tuples should be in the snapshot. The extra column(s) would contain a snapshot identifier: a timestamp or a foreign key into a new table with more information about snapshots. In case of two columns, they would indicate the first and last snapshot in which the given tuple is present. This can save space if you have many snapshots, but it can also make querying harder.


You want to enumerate first by sum, then by lexicographic order of some sort (it's impossible to tell which type exactly from your example). Replacing actual elements with indices, here is the order you're interested in for $A \times B$:
$$
(0,0) \\
(1,0), (0,1) \\
(2,0), (1,1), (0,2) \\
\ldots
$$
It's a simple exercise to generate this order for $A \times B$. Generating the order for $A \times B$ is somewhat more challenging, but still not too bad. When generating the triples summing to $n$, if we focus on just the first two parts of each pair, then we're interested in a list of all pairs $(i,j)$ such that $i+j \leq n$, in some sort of lexicographic order. Whichever variant of the lexicographic order you choose, you should be able to figure out how to generate it by looking at some examples.


Finding shortest path from a node to any node of a particular type

I don't have enough rep to comment, but here are some suggestions rather than a definitive answer. These algorithms assume the graph is fixed.

Let $k$ be the number of types. The number of nodes is $n$, similarly $m$ for edges.

Case 1: $k$ is acceptably small.

Strategy: Just store the info.

Preprocessing: $\mathcal{O}(k(n + m))$,
Memory: $\mathcal{O}(kn + m)$,
Query Time: $\mathcal{O}(1)$

Simply store the shortest distance to any type for each node. This can be done in $\mathcal{O}(k)$ space per node. The values can be obtained by running BFS $k$ times,  once for each type. Let $D[v][t]$ be the distance from node $v$ to any node of type $t$, initialized to $\infty$.

For each type $t$, find the connected component of nodes of just that type, by BFS. During the BFS, keep a set (the "boundary" nodes) of all nodes of other types that are encountered. Now BFS using that set as a starting point, record the distance in $D[v][t]$ for each node encountered. Runtime is $\mathcal{O}(n + m)$ for each type $t$.

Querying: $\mathcal{O}(1)$, just look up the value in $D$.

Case 2: $k$ is not that small. But the graph is very dense.

Strategy: Utilize bidirectional search after graph transform.

Preprocessing: $\mathcal{O}(n + m)$, Memory: $\mathcal{O}(n + m)$

Query Time: $\mathcal{O}(n + m)$ (but possibly better in practice, see: http://en.wikipedia.org/wiki/Bidirectional_search)

We will be adding nodes / edges and transforming the undirected graph into a directed one.

Create $k$ supernodes, $S[t]$, one for each type. For edges that link different types of nodes: $e_{u,v}$ where $type(u) \neq type(v)$, create additional edges from $v$ and $u$ directly to the supernode of the other type (directed into the supernode). Next convert all the original undirected edges into two directed edges, one in each direction.

At most, we've added $n + m$ extra links and $k < n$ (assuming a node can belong to only one type) extra nodes, preserving the memory and time bounds. The transformation itself takes $\mathcal{O}(n + m)$ time. Essentially, the supernodes allow us to search in both directions, without affecting correctness. While we BFS from the starting node, we can also BFS in reverse from the supernode of the target type. This can be more efficient if the nodes originally had large degrees (big branching factor).

Querying: To find the shortest path from node $v$ to type $t$, run a bidirectional BFS from $v$ and $S[t]$. Depending on the graph, this could be significantly faster than just a BFS for very dense graphs, and will not be asymptotically slower.


Is there an efficient algorithm to extract the farthest ends of a thin contour?

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them.

Exploiting the very same idea, if you try finding pixels with the least number of surrounding pixels and apply limited BFS Flood Fill to find out where it can go - at the endpoints there is only one way out. Also going by curvature and then applying the same idea would tell apart the extra bends from results.


Graph add at most 2 edges to make all graph nodes degree even

Your proposed "broken" solution is actually quite close to the actual solution. You don't need any well known algorithm to do it, but instead you have to notice the following things:

Given that odd == 2, and the two odd vertices are $v,u$ - then we can "fix" them by either connecting them if they are not connected, or by finding another vertex $w$ such that $(v,w),(w,u)\notin G$ and then add the two edges.
Given that odd == 4, the only way to "fix" them is by connecting them to each other, in 2 groups of 2: each edge on two different vertices.

Then, the actual code would look like this:
boolean addEven(boolean[][] graph) {
    int odd = 0;
    List<Integer> odd_vertices = new ArrayList<Integer>();

    for (int i = 0; i < graph.length; i++) {
        int deg = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                deg++;
            }
        }
        if (deg % 2 == 1) {
            odd++;
            odd_vertices.add(i);
        }
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd == 0) {
        return true;
    } else if (odd == 2) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        for (int k = 0; k < graph.length; k++) {
            if (!graph[a][k] && !graph[b][k]){
                return true;
            }
        }
        return false;
    } else if (odd == 4) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        int c = odd_vertices.get(2);
        int d = odd_vertices.get(3);
        if ((!graph[a][b] && !graph[c][d]) ||
            (!graph[a][c] && !graph[b][d]) ||
            (!graph[a][d] && !graph[b][c])) {

           return true;
        }
        return false;
    } else {
        return false;
}

Of course, this code is just to illustrate how the changes are reflected in the code. You can change it to be more general or optimize it, but I will keep it as is (especially because its hard to write code without a proper editor)


How to distinguish between the different frequency domains?

Hopefully whoever you are talking to would actually define the terms they were using before they started slinging them around.  I've heard some of these used in multiple contexts.  Wikipedia has an article that tries to encompass some of the different things people might be talking about when they use the term frequency domain.

The domain we are referring to here is the well-defined mathematical term for the set of legal inputs to a function.  There are multiple kinds of transforms (Laplace, Z, various kinds of Fourier transforms). The domains we are referring to are the (mathematical) domains of the function that results from the transform.

I tend to think of the s-domain as being associated with the Laplace transform:
$F(s) = \mathcal{L}[f] = \int_0^{\infty} e^{-st}f(t) \mathrm{d} t$.  The function $F(s)$ is potentially defined for the entire continuous complex plane, so the domain is the complex plane.  (Although for most functions $f$ there would be a region of convergence.)  I haven't personally heard the term s-domain in any other context.  For the Z transform you might hear "Z-domain" (which is also the entire continuous complex plane).

I think if I heard a scientist use the term Fourier domain my initial assumption would be that they were (probably) talking about the Fourier decomposition of a periodic function into a Fourier series.  (If I heard an engineer use the term Fourier domain I would think they were probably talking about a discrete Fourier transform, see below.)  Most people who use Fourier series in their daily work use the exponential Fourier series:
$c_n = F(n) = \mathcal{F}[f] = \frac{1}{2\pi}\int_{-\pi}^{\pi}f(x)e^{-inx}\mathrm{d}x$.  So the domain here (the subscript $n$ of $c_n$) is the integers.  (If I were talking to a student I would assume they were talking about the sine/cosine version, which is also defined across the integers (but inconveniently with two different series across the non-negative integers (once for sines and once for the cosines))).

For an engineer, and especially a computer engineer like me, I would assume that we were talking about the discrete Fourier transform.   This applies to periodic functions that are band limited (i.e., have very little energy in frequencies above some value.)  In that case the time (or space)-domain signal can be sampled at a finite rate and the transform is:
$X_k = \mathcal{F}[\{x_n\}] = \sum_{n=0}^{N-1}x_n e^{-2\pi i k n / N}$.  Here again the domain (the subscript $k$ of $X_k$) is the integers, and in this case just a finite sequence of integers $\{0, N-1\}$.

Finally, if I was talking to a scientist or mathematician and they used the term Fourier domain, my initial assumption that they were talking about a Fourier decomposition might be wrong.  They might instead be talking about a continuous Fourier transform:
$F(\omega) = \mathcal{F}[f] = \int_{-\infty}^{\infty}f(t)e^{-2\pi i \omega t} \mathrm{d} t$.  The domain of the function $F$ is the entire real line.  Note that there is some similarity with the Laplace transform but with the Fourier transform we are typically only looking at $s=2\pi i \omega$, the complex unit circle, (although sometimes it might be useful to look at the rest of the plane), and for the Laplace transform we are only looking at positive time.

Complex frequency domain could refer to the continuous Fourier transform, I suppose, but I would tend to think of it as referring to the same thing as the s-domain.

All these transforms are related, but in any conversation you need to be clear whether the time domain is continuous or discrete and whether the time domain function/signal repeats or not.  You should also make clear whether the time domain function's range is real or complex.  Then in the frequency domain you might be talking about complex frequencies (like in the Laplace transform or Z transform) or real frequencies, and, if real frequencies, continuous or discrete.  Sometimes you can infer from context, but sometimes not.  The range in the frequency domain is more often the complexes rather than the reals.

You should start every conversation with a boring list of definitions.


Yes, all functions $f(n)$ satisfy $f(n) \in O(f(n))$. The definitions are meaningful even if $f(n)$ isn't the running time of any function. Indeed, this notation comes from number theory, where $f(n)$ is usually some error term. Even in computer science, sometimes big O notations is used while analyzing algorithms for something other than a running time or space requirements.


I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

If I understand OP's question correctly - the question is what is the time-complexity estimate for MSD radix sort, taking into account what OP calls AmountofNodes or recursive frames for an MSD sort, which must fill the count[] array ($R$) per each recursive frame and than iterate through the count[] array to create subfiles. I couldn't find this in the literature and I presume jsguy hasn't found a satisfactory explanation either.

I'm going to assume we are talking about the Naive MSD sort as described in the OP's pseudo code. (otherwise if you have 20 items in a subfile and $R = 256$, a hash-table would be significantly cheaper than the count[] array).

From the looks of it worst case time-complexity for that should be $\Theta(NW + NR^{(W-1)})$, where each item is unique. Specifically a worst-case number of $R$ calls will happen if none of the recursive calls terminate early (before $W_{i-1}$) and if a subfile is broken up as much as possible from the root (the maximum number of recursive calls started from any subfile is $R$).

Considering a set of subfiles $N$ - if the set is already dense duplicates only cost $W$ ($N > R^W$ and all combinations appear), if the set is sparse ($N < R^W$ and without duplicates), adding a duplicate costs at most $R(W-1)$ (if a single subfile would otherwise have terminated early at $W_1$).

If the set $N$ is sparse, either some combinations will not diverge at level $W_0$ (which is always more expensive than diverging at some further level $W_x$) or as many as possible will diverge at each level but some will terminate before $W_{i-1}$ because the branch will have only a single item remaining - therefore for sparse sets the worse-case is to have maximal divergence at each level $W$ until there are two duplicates in each subfile, for which the above estimate of $R(W-1)$ per item should apply.

edit: As to why people use MSD Radix sort, I hope someone that works with an application that utilizes Radix sort can answer that, I suspect there are cases like long RNA strings where there are very long strings with a very small $R$, and the ability to parallelize is an advantage (just a guess though). My worst case estimate definitely sounds pretty bad, but I think in practice no one tries to split a file of two duplicate items into $R$ buckets at every single $W_i$.


Is there an optimization algorithm that could help match the maximum number clients to servers with constraints?

The problem is NP-hard.  Consider the following special case: there is only one server, and its radius is infinite (or very large). Then your problem becomes the problem of finding an independent set in a planar graph.  That problem is known to be NP-hard.  Since a special case of your problem is NP-hard, then your problem must be at least as hard in the general case.
There are many ways to deal with NP-hard problems.  Probably one reasonable approach is to formulate your problem as integer linear programming, and then solve with an off-the-shelf ILP solver.  Another approach is to formulate it as an instance of SAT (with a pseudoboolean constraint/cardinality constraint for counting the number of clients that are serviced), and solve with an off-the-shelf SAT solver, like Z3 (which has good support for pseudoboolean constraints).


Program transformations for numeric stability

There actually is some research on improving the numerical stability of floating point expressions, the Herbie project. Herbie is a tool to automatically improve the accuracy of floating point expressions. It's not quite comprehensive, but it will find a lot of accuracy improving transformations automatically.

Cheers,

Alex Sanchez-Stern


MAX 2-SAT is polynomial time reducible to 2-SAT?

I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless P=NP.

Let $\phi$ be a 2-SAT formula with $m$ clauses.
If you really want to reduce an instance $\phi$ of 2-SAT to (the decision version of) MAX-2-SAT, then this simply amounts to checking whether at least $m$ (i.e., all) clauses of $\phi$ are satisfiable.


About a step in the analysis of Quicksort by Sedgewick and Wayne

Let $\rho_N = C_N/(N+1)$. The next to last equation shows that
$$
\rho_N = \rho_{N-1} + \frac{2}{N+1}.
$$
Therefore
$$
\rho_N = \frac{2}{N+1} + \cdots + \frac{2}{2+1} + \rho_1.
$$
Multiplying by $N+1$,
$$
C_N = (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1} + \rho_1\right).
$$
Since $\rho_1$ is a constant whereas $2/3 + \cdots + 2/(N+1) \to \infty$, we deduce that
$$
C_N \sim (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1}\right).
$$
We can estimate this expression in many ways, for example by approximating the series by an integral (this is what the authors suggest when they mention the area under the curve $2/x$). Or we can recognize that it is roughly equal to $2H_{N+1}$, twice the $(N+1)$st harmonic number, and so using the well-known estimate $H_N \sim \log N$,
$$
C_N \sim 2N\log N.
$$

Finally, regarding the relevance to Quicksort, my guess is that $C_N$ is the average number of comparisons performed on a random array of length $N$; but you should be able to tell by reading the book.


Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

Yes. As you note, $f(n) = \sum_{i=0}^{k}0\cdot n^{i} = 0$ is a perfectly valid polynomial in $n$ (for every fixed $k$).

What you have left over without the oracle calls is just a polynomial time algorithm. This observation also underlies the fact that any polynomial-time solvable problem has a polynomial-time reduction to any other non-trivial problem.


How can repeated addition/multiplication be done in polynomial time?

From what you said, I suppose that you consider complexity in terms of number of bits of the input.

Say you add up two numbers $a$ and $b$, with respectively $n_1$ and $n_2$ bits, then the result is at most $\max(n_1, n_2) + 1$ bits since $a + b \leq 2 \times \max(a, b)$.

For the multiplication, the result is at most $2 \times \max(n_1, n_2)$ bits since $a \times b \leq \max(a, b)^2$.

The important thing is that the number of bits necessary to represent the sum / product of two numbers is polynomial in the number of bits to represent those numbers. Hence, for $i$ numbers, the number of bits necessary to represent the answer is still polynomial in the number of bits of the input (since composition of polynomial functions yields polynomial functions).

Edit: actually, the really important thing is that $i$ is not part of the input, it is fixed. Otherwise, if you take for instance $2 \times 2 \times \ldots \times 2 = 2^i$, the answer takes $2^{i-1}$ bits, while the input takes $i + \log i$ bits. But if $i$ is fixed, then $2^{i-1}$ is a constant. This kind of distinction happens quite often in computer science, especially in the field of fixed parameter tractability.


To understand this problem you have to understand the rules for the safety checks. I am not going to give a detailed explanation of these but you can go here to read more about it. I will try to give an explanation of why C request 1 is safe but A request 1 is not.

There is a value associated with a process and a resource called need. The need is an n-tuple where n is the number of different resources. In this case n is just 1. Calculating the need is just taking the max and subtracting the has for each resource. And there is a safety check that if no process has a need less than or equal to the n-tuple of available  resources after a request then that request should be denied.

For C requests 1 it appears that the previous state is after B requests 1. In this C request 1 step we see A has a need (6), B has a need (1) and C has a need (4). Since there is only one resource the n-tuple of available resources is just (1) so this can be granted as B has a need of (1).

For A requests 1 the previous state is the initial state. We then calculate the need of A is (5), B is (2) and C is (5). And the resulting n-tuple of available resources is (1). There is no need which is less than or equal to this so we should reject it.

Be careful when reading more about the subject. The notation is often different, the letters A,B and C are often used to represent resources and p's will be used for processes. You will also be dealing with n-tuples of greater values.


Determine if items can be ordered grouping two simultaneous criteria

There is a $O(n)$ time algorithm for your problem, using standard graph algorithms.  You basically reduce it to connected components decomposition, which can be done in linear time.

Build an undirected (multi-)graph, where we have one vertex for each letter in the input.  For each pair of items that share the same number, say Xi and Yi, add an undirected edge between X and Y.  This might introduce repeated edges.  That's ok.  Leave them as is; don't collapse them down to a single edge.

Once you have this graph, your items can be ordered if and only if every connected component of this graph is a simple path.  You can test this condition by decomposing into connected components using standard algorithms, then for each connected component, checking that no vertex has degree $\ge 3$ and that either (i) the component consists of only a single vertex, or (b) there exist exactly two vertices in the component with degree 1.  The whole thing can be done in linear time.

The idea here is that we're trying to find an ordering of the letters (the vertices), subject to some constraints: each edge (X,Y) represents a constraint that the letter X has to be adjacent to Y in the final ordering of letters.  The graph I defined above encodes exactly the constraints that apply, if we want to find an ordering of the items.  Notice that there exists a valid ordering of the items if and only if there exists a valid ordering of the letters that respects the edge-constraints: given an ordering of the letters, each letter represents the group of items containing that letter, and you can easily arrange what order to put the numbers in.

The key insight here is to build a graph with one vertex per letter rather than one vertex per item.  Once you do that, everything falls out more or less straightforwardly.

Credits: I thank Raphael for a crucial idea that helped me find this,  AlexDev for pointing out some subtleties that helped me work out the details, and reinierpost, whose answer helped me realize a few other tricky details.

By the way, you might notice that my solution ends up looking very similar to reinierpost's elegant algorithm.  Indeed, when the graph is connected, my solution is equivalent to his algorithm: his y[A] is just the degree of the vertex A in the graph I defined.  The difference comes when the graph is not connected; my algorithm handles that case correctly, but I think his algorithm gets a few corner cases wrong.  Nonetheless, the ideas are extremely similar -- and I hope my exposition helps understand the ideas behind his elegant algorithm.

This algorithm also generalizes to the case where you have more than two attributes.  For instance, suppose each item has a letter, a number, and a color.  Start by forming a graph with a vertex per letter and an edge (X,Y) whenever there are two items that share an attribute and whose letters are X,Y respectively; use the same techniques to look for a valid ordering of the letters.  Then, for each letter, you need to look for a valid ordering of the items containing that letter.  This can be done by a recursive call.  There is a slight twist, in that during recursive calls you might have an additional constraint indicating which item the sequence must start and/or end at, but it's easy to adjust the algorithm to take this into account.  In this way you get an algorithm whose running time is $O(kn)$, where $n$ is the number of items and $k$ the number of attributes.


How to calculate number of nodes opened by BFS?

In the case of the above diagram, as you mention, there is no constant branching factor. This means that we cannot solve for the number of nodes explored using the formula you give above.

Instead, we must use knowledge of how BFS works in order to calculate which nodes were visited before Node I was found. In BFS, nodes adjacent to the current node are marked, and then placed in a queue. The next element in the queue is visited (and removed from the queue), and this process repeats. Use this process to figure out which nodes are visited before Node I, and then charge a cost of 2kB for visiting each node.


Partitioning planar graphs without minimizing edge cuts

One general method is to perturb the node weights slightly, find a good partition, and repeat that $n$ times with $n$ different perturbations.

The basic algorithm is something like this:

Repeat until you have $n$ distinct balanced partitions of $G$:

Copy $G$ to $G'$.  Randomly perturb the weight of each node in $G'$ by a tiny amount (a different random change for each node).
Find a balanced partition of $G'$.  This corresponds to a partition of $G$.
If this is a legal, balanced partition of $G$ and you haven't seen this partition of $G$ before, add it to your list of distinct partitions.

If you choose the amount of the perturbation correctly, then you can expect this will need only $O(n)$ iterations of the loop to find $n$ distinct partitions.

Let's see in a little more detail how to make this work in your setting and why it works.  The basic idea is to add a tiny, tiny random perturbation to each node's weight.  This won't affect the total weight of any group in your partition by very much: the sum of a bunch of of tiny numbers is still quite small, and in particular, we can ensure it will be much smaller than 1.  Since the total weight of any group of vertices in $G$ has to be an integer, the change in its total weight can't be enough to make it jump up to the next integer.   Consequently, this won't change the relative order of vertex-groups (if one vertex-group has a smaller weight than another vertex-group, after perturbation its weight cannot become larger); all it can do is break ties.

However, this basic idea has a problem: after perturbation, the vertex weights in $G'$ are no longer integers.  It's possible that your underlying algorithm (e.g., Metis) requires the vertex weights to be integers.   If so, here is how we can fix things up and preserve the integrality of node weights.  The idea is to first scale up all of the weights by a large integer constant $c_1$, then add a small integer perturbation to each node weight.  Formally, let $w_v$ be the weight on node $v$.  We're going to pick integer constants $c_1,c_2$ and for each node $v$ set

$$w'_v = c_1 w_v + r_v,$$

where $r_v$ is a random integer chosen from $\{0,1,\dots,c_2\}$ (chosen independently for each node).  We'll use $w'_v$ as the weight of node $v$ in $G'$.

How do we choose $c_1,c_2$?  Basically, we need $c_2$ to be large enough so that each iteration is likely to give you a new partition, and we need $c_1/c_2$ large enough so that a balanced partition of $G'$ is likely to also be a balanced partition of $G$.  One reasonable setting is to use $c_2=100n$ and $c_1 = 100 |V| c_2$.  Alternatively, if your underlying algorithm is OK with non-integer vertex weights, you could instead pick $r_v$ randomly from the range $[0,1/(100|V|)]$ and just leave $c_1=1$.

Why does this work?  Well, first note if we divide all the weights in a graph by a constant, that has no effect on the set of balanced partitions -- so we might as well consider the weights to be $w''_v = w_v + r_v/c_1$.  Now I claim that a balanced partition of $G'$ is almost certainly a balanced partition of $G$.  Any single group in the partition has at most $|V|$ vertices, and the weight of each node in the group has been randomly increased by at most $c_2/c_1$, so the total increase in the weight of that group is at most $|V|c_2/c_1=0.01$.  Originally the total weight of a vertex-group has to be integer, so this perturbation is not enough to make it jump up to the next integer.  Now, depending upon your definition of balanced, most likely the following will be true: any balanced partition in $G'$ has a high probability of being a balanced partition in $G$.

Also, the random perturbations ensure that, if you look at two perturbed graphs $G'_1,G'_2$, it is unlikely that the optimum partition of $G'_1$ is the same as the optimum partition of $G'_2$.

So, I suggest you give this a try.

Important caveats: There are no guarantees this will work.  From a theoretical perspective, it's not guaranteed to work.  Indeed, I suspect your problem might be NP-hard, so it would be too much to expect this to always work.  But in practice, this often works, if you are in a situation where your underlying algorithm (e.g., Metis) is able to find the optimum partition in a reasonable amount of time.  As a pragmatic guideline, it's more likely to work if the underlying algorithm can find an exact optimum rather than an approximate-optimum (e.g., maximally balanced rather than close-to-maximally-balanced).  However, as I said, there are no guarantees, so the best way to find out whether it will work in your particular situation is to try it out and see.


The algorithm relies on two facts:

If $n$ is even, $n=2k$, we have $a^n = a^{2k}=a^ka^k = a^{n/2}a^{n/2} = (a^{n/2})^2$
If $n$ is odd, $n=2k+1$, we have $a^n=a^{2k+1}=a^1a^{2k}=a(a^ka^k)=a(a^{(n-1)/2})^2$

In other words, we have
$$
a^n=\begin{cases}
(a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is even}\\
a(a^{\lfloor n/2 \rfloor})^2 &\text{if $n$ is odd}
\end{cases}
$$
You've computed $pow(a, n)$ by changing it to a problem involving an instance of the half-sized problem $pow(a, n/2)$ along with a squaring and possibly a multiplication by $a$.


Double ended queue data abstraction and axioms

Like you say items can be added to a double ended queue on both sides, yet you have only a single AddQ operator. More substantial is the change to the axioms. An item added at the end can (after several operations) be retrieved from the front.


Proof of bucket sort worst case being all elements in one bucket

For an upper bound on the worst-case cost, it's sufficient to show that it can't be worse. Assuming that insertion sort takes $\leq cn^2$ steps on $n$ elements, consider the sum

$\qquad\displaystyle \sum_{i=1}^n c |B_i|^2$;

it is an upper bound on the cost of sorting all the buckets. For an upper bound on the worst case for bucket sort, maximize this function subject to $\sum |B_i| = n$ (and add the remaining cost, which is $O(n)$ for all inputs).

For a lower bound on the worst-case cost, we have to find an infinite class of actual inputs and show that their cost behaves as claimed. $[0, \dots, 0]$ serves to show an $\Omega(n^2)$ lower bound, as you note.


Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution

"$O(n^2)$ is indeed an upper bound for the recurrence" means $T(n) \in O(n^2)$.
That is, $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \le c n^2$.

"$\Omega(n^2)$ must be a lower bound for the recurrence" means $T(n) \in \Omega(n^2)$. That is $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \ge c n^2$.

This is exactly the same as 1).

Yes. In this step you use induction to show that $T(n) \le d n^2$ for some choice of a constant $d > 0$.


Finding maximal and average number of time slots in an Adaptive tree walk protocol

It is clear that you cannot know the maximum if $p \neq 1$, because there is always some chance, no matter how small, that neither station will transmit after any $n$ attempts.

However, if $p=1$ then the answer is always 3 (both average and maximum): first all stations under 1 transmit (both A and C), then under 2 (same), then under 4 (just A – success).

Regarding the average (excepted value), it's a combination of two things: the average tries you need until any station transmits, and the expected value of a successful transmission assuming at least one station transmitted. The first is a standard geometric distribution, where the expected value is $E=1/p$.


Running Time Analysis of a Simple Binary Search Algorithm

Sorting the big set takes time $O(n\log n)$. You perform $m$ binary searches, each taking $O(\log n)$, for a total of $O(m\log n)$ time spent on binary search. The total running time of the algorithm is thus
$$
O(n\log n + m\log n) = O((n + m)\log n) = O(n\log n),
$$
assuming $m \leq n$.

Note that it is even better to sort the smaller list, since then the running time improves to $O(n\log m)$.


Do data points mean Eigenfaces in higher dimensional space?

Each blue data point in the animated picture stands for an image of a face whose dimension is much higher in the context of Eigenfaces for Recognition. They are the original data points. It does NOT mean Eigenfaces.

When the long swinging black solid rod becomes still under the "viscous friction" exerted by the red lines, its direction is the most significant eigenface in that context, which is defined as an eigenvector of the biggest eigenvalue of the covariance matrix of the face images. The projection of the blue points onto that long black rod viewed as vectors starting from the center of the blue points is the first principal component.


Convert given string to Palindrome with given substring

Here is a description of a simple brute force approach that works in $O(n^2)$, where $n$ is the length of $S_1$.

Let $m$ be the length of $S_2$. If $m>n$, return -1 immediately, indicating impossibility.

Keep a counter on how many characters will be changed. Change $S_1$ so that its substring with length m that starts at index 0 is the same as $S_2$. Mark the indexes where characters have been changed. Also chang $S_1$ so that ist substring that starts at index n-1-0 and goes backwards to index n-m-0 is $S_2$ backward. However, abort this try if we have to change the characters that has been marked. Now change the remaining characters of $S_1$ to make it a palindrome. That is, if the character at index $i$ is not same as the character at index $n-1-i$, change the later to be the former. Once done, the counter tells us how many changes is needed to make $S_1$ a palindrome that has $S_2$ as its substring starting at index 0.

Repeat the above with index 0 replaced with index $1, 2, \cdots, n-m$, keeping tracking of the minimal number of changes.

The above description should be enough to set you up. You may want to improve it or look for better algorithms.


Unfortunately, that's not possible with the standard data structure for union-find (namely, with the union by rank method).

The data structure has invariants that in some cases require making $y$ be the root (namely, when $x$'s rank is smaller than $y$'s rank, you are required to make $y$ the root).  If you force $x$ to be the root in such a situation, then you destroy the invariants, which might make subsequent Find/Union operations slow.

It sounds like you are thinking that perhaps we can reorganize the inner structure of the tree under $x$ or the tree under $y$.  Unfortunately, it's not possible to do that in the standard Union-Find data structure.  The data structure doesn't have child pointers (doesn't have any way to get from $x$ to its children, or from $y$ to its children), so there is no way for a data structure to change the inner structure of the tree under $x$ or the tree under $y$.

So if you want to achieve this, you will probably need an entirely new data structure.  If so, you should probably ask a new question and specify your requirements in terms of the externally observable behavior of the API's, rather than in terms of the internal state of the data structure.


Identifying an object in an image based on color (AI ?)

The general class for this problem is Template matching. The most common approach is performing a cross correlation of the template, in your example an apple, and an image which may contain the template.

A Google search for "template matching fast normalized cross correlation" will bring up some literature that should be helpful.


How much math does one need to know to understand discrete math/structures for computer science?

Normally, classes at universities have prerequisite lists. If there are some courses on the list you haven't taken, you should ask the professor whether you really need them.

Discrete math courses can vary dramatically in what you really need to understand them. You may or may not need to have done proofs; (some discrete math classes teach you how to do proofs). I'd guess you probably don't need to know calculus. Calculus isn't really needed to understand discrete math, but if calculus is a prerequisite for the class, there are a number of good examples and homework problems that the professor might use that would indeed require calculus. And you can certainly teach discrete math classes that require basic abstract algebra as a prerequisite.


Balanced k-means clustering would probably work reasonably well here.  Unfortunately the true cost structure can't be modelled with this (or any clustering algorithm that I know of); you would need to instead use some increasing function of the distance from the cluster centroid (this could be just the distance itself, or e.g. a small positive power).  Balanced k-means will then try to cluster the teams into divisions in such a way that the sum of these per-team costs is minimised, while enforcing a hard upper bound (your max) on the number of teams in a division.  The chosen number k of divisions, as well as these upper bounds, implies a lower bound on the division size, though this won't necessarily agree with your desired min.  Hopefully, playing with the parameters a bit could get you close.

The idea is basically the same as regular k-means clustering, except that in the assignment phase, instead of assigning each point (team) to its nearest cluster (division), you solve an instance of the Assignment Problem in which each team is represented as a worker and each division is represented as max job slots: this enforces that each division receives at most max teams.  The problem can be solved with e.g. the Hungarian algorithm.

There's a paper here, but it seems to be behind a paywall unfortunately: https://link.springer.com/chapter/10.1007/978-3-662-44415-3_4


What is the difference between python list and c++ vector?

Both python list and c++ vector are implemented as dynamic arrays (https://en.wikipedia.org/wiki/Dynamic_array).
(Essentially arrays that get reallocated when they are too small.)
Now the important difference between the python and c++ version don't come from the data structures themselves, but rather from the language. In c++ you can store structs, primitive data types pointers etc. in a vector. But in python everything is a pointer in the sense that an e.g. an integer is stored in the heap and it has an annotation attached to it that says "i am an integer". That's required because python has a dynamic type system. And the elements stored in the list are only pointers to the actual elements. This mechanism also allows python to store different data types in the same list. This is another reason why python is kinda slow.


Training a HMM with Baum-Welch gives different results across runs

It is impossible to locate the issue for sure without inspecting the implementation and results in more detail than is ontopic here. For instance, numeric algorithms always have potential issues related to the precision of the used number format, especially when dealing with (very small) probabilities.

That said, two notes.

Baum-Welch does only find local optima.
Insufficient training data can cause parameter estimations to vary wildly.

So I recommend you try more training data if possible. Otherwise, just run the algorithm many times and pick the best model (according to the likelihood of the training data according to the resp. model) you find.


One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by using a topological sort on the graph.

This surely is a bit overkill and is probably also not the most efficient solution ($O(n^2)$ for building the graph).


This answer is just so that the question is not left unanswered.

The OP is correct: the book got it wrong.


No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs.

$$k+1,\:k+2,\:k,\:k+2,\:k-1,\:k+2,\:\ldots,\:2,\:k+2,\:1,\:k+2,\:x_1,\:x_2,\:\ldots,\:x_k$$

Note that, for $a\in\{1,\:2,\:\ldots,\:k+1\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ copies of $k+2$, then a subsequence of $x_1,x_2,\ldots,x_k$. It is not profitable to begin anywhere else, since the maximum bounded subsequence beginning with $k+1$ has length at least $k+2$.

Let the adversary in this lower bound choose a random permutation $\pi$ on $\{1,2,\ldots,k\}$ and answer as though $x_j=\pi(j)+1/2$. This setting ensures that every maximum bounded subsequence beginning with $a\in\{1,\:2,\:\ldots,\:k-1\}$ has length exactly $k+2$. By the following argument, however, the algorithm cannot be sure of this fact unless it sorts $x_1,x_2,\ldots,x_k$.

Suppose that the algorithm cannot infer the order of $x_i$ and $x_j$. Without loss of generality, assume that $i=\pi^{-1}(\pi(j)-1)$, so that $x_i$ immediately precedes $x_j$ in the imagined sorted order of $x_1,x_2,\ldots,x_k$. It is consistent with the algorithm's observations that

$$x_\ell=\begin{cases}\pi(j)+1/2&\text{if }\ell=i\\\pi(\ell)+1/2&\text{if }\ell\ne i,\end{cases}$$

which would give rise to a bounded subsequence of length $k+3>k+2$.


The best way is to read out the digits and then say "hex(adecimal)". Don't say "forty-one hex" because "forty" means four times ten, whereas the four in 41h stands for four times sixteen. Don't say "sixty-five in hex" because then the person you're talking to doesn't know if you mean "The decimal number sixty-five, only written out in hex, i.e., four-one-hex" or "The number six-five-hex, i.e., one hundred and five decimal."


Expected number of random interval flips needed for sorting a random array

$\Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $\Omega(n!)$ iterations on average.  Obviously, you need to try at least $\Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation).

Also, one can show that $O(n! \cdot n \lg n)$ is an upper bound on the number of iterations needed.  Here's why.  It's known that there is a constant $c$ such that composing $k=c n \lg n + o(n \lg n)$ randomly chosen transpositions gives you something that is close to a random permutation.  So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant.  Each one is approximately a random permutation (independent of all others).  After checking $\Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order.  Therefore, your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.  Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort -- thus your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.

So we know that the answer is at least $\Omega(n!)$ and at most $O(n! \cdot n \lg n)$.  Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn't leave much of a gap -- it almost totally resolves the question.  If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap -- but lacking clear motivation for studying this problem, it's not clear it's worthwhile to spend that level of energy on it.

How do we know that composing $O(n \lg n)$ random transpositions gives you something close to a random permutation?  That was proven in the following paper:

Generating a Random Permutation with Random Transpositions.  Persi Diaconis, Mehrdad Shahshahani.  1981.

See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.


Proof of Co-Problem being in NP if Problem is in NP using negated output

A problem is in NP if for all instances where the answer is “Yes” you can guess a hint and verify it in polynomial time. Nothing at all is said for instances where the answer is “No”. That distinction between “Yes” and “No” answers is essential.
What your proof attempt shows is that if a problem X is in NP, then the co-problem “Does X have the answer ‘No’” is in co-NP, as we would expect, and says nothing about NP.


$a^*b^* / b^* = \{ w \ | \ \exists \ x, \ x \in b^* \land wx \in a^*b^*\} = a^*b^*$. This is because $wx \in a^*b^* \text{ AND } x \in b^*$ means $w$ is of the form $a^ib^j$ for some $i,j \in \mathbb{N} \cup \{0\}$. Finish it off now.


Find a minimum-cardinality Hall-violator

This is not an answer - just a long note.

The question is related to the problem of Minimum vertex cover with minimum overlap of one side .
Suppose we have a minimum vertex cover $C$ of size $m$. By Konig's theorem, $m$ also equals the size of the maximum matching, so $m < n$.

Since $C$ is a vertex cover, any vertex not in $C$ must have all its neighbors in $C$. So $N(X\setminus C)\subseteq Y\cap C$. Hence:
\begin{align}
|N(X\setminus C)|
&\leq |Y\cap C|
\\
&= m-|X\cap C|
\\
&= m-n+|X\setminus C|
\\
&< |X\setminus C|
\end{align}
so $X\setminus C$ is a Hall-violator.
Now, if $X\cap C$ is large, then $X\setminus C$ is small.

However, I am not sure that finding a $C$ which maximizes $X\cap C$ also yields the smallest Hall violator.


Why hasn't functional programming researched dynamic trees?

"In computer science, functional programming is a programming paradigm.  A style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data." - Wikipedia

"changing state and mutable data"  in other words "dynamic".

So your question is a bit like asking why left isn't right.


Intersection of Decision Tree Boundaries in Higher Dimensions

Yuval Filmus has articulated an elegant solution, which I'll expand on.
Given a leaf of a decision tree, it is easy to characterize the set of values of $x$ that reach that leaf.  Namely, you take the conjunction of all the conditions along the path from the root to the leaf.  For trees of the form you list, this will have the form $[\ell_1,u_1] \times \cdots \times [\ell_4,u_4]$, i.e., the set of all $x$ such that $\ell_1 \le x_1 \le u_1 \land \cdots \land \ell_4 \le x_4 \le u_4$, where you can explicitly compute $\ell_1,\dots,\ell_4,u_1,\dots,u_4$.
Now apply the following algorithm:

For each pair of leaves, with one leaf in the first tree and the other leaf in the second tree, such that the two leaves lead to different classifications:

Compute the set of values $x$ that reach the first leaf, the set of values $x$ that reach the second leaf, and compute their intersection.  Output the intersection (this is one set of points where the decision trees differ).

The union (i.e., disjunction) of all of those outputs will be the complete set of points where the two trees give a different decision.

It is possible to come up with algorithms that might be faster; however, I'm not sure whether they will lead to a significant improvement in higher dimensions.
One approach is to construct a new tree via a "product construction".  Thus, each node in the new tree is a pair $(u,v)$, where $u$ is a node in your first tree and $v$ is a node in your second tree.  The root of the tree is $(r_1,r_2)$, where $r_1$ is the root of your first tree and $r_2$ is the root of your second tree.  You can build the new tree top-down, starting from $(r_1,r_2)$, then splitting using the condition at one of these two nodes ($r_1$ or $r_2$).  As you build the tree, keep track of the set of values that can reach each new node $(u,v)$.  If this set is empty, you can prune it and don't need to explore any of its children.  This might reduce the number of nodes you need to expand.  In the worst case, there is no speedup, but in practice, it might help a little.

It gets more interesting if each classifier is an ensemble/forest of trees; then the best solution would probably be to use a SMT solver.


You're asked to calculate the running time of the segment, not the value returned. In terms of running time, multiplication by 8 is a single operation, so the running time is (roughly) $T(n)=T(n/2)+n^2$.


Find out whose turn it is to buy the croissants

There are two categories of solutions to this sort of problem that I'm aware of: biased lotteries and filtered/generated random sequences.

First, let's dispense with easy but wrong solutions that keep no state.  Any lottery-style solution that maintains no state will have the number of wins in a binomial distribution, which fails the "as many times" criterion.  You can select a random sequence that picks all people equally (just going around the list does that; permutations provide randomness), but once people start going on vacation your sequence now has holes.  Unless you keep track, you will again find yourself with binomial distributions instead of maintenance of equal effort.

Let's also commit to having actual randomness.  You might want this so that, for instance, a person cannot schedule their vacation on the basis of a deterministic algorithm so that they are never present when it is their turn to buy croissants (until they use up all their vacation days, I suppose).

So, on to the two types of solutions.

To construct a biased lottery, first note that we can pick from pretty much any continuous distribution (with finite deviation) to generate numbers for our lottery.  The loser can then be the person with the lowest number.  Then the simplest bias is to keep track of whether each individual has bought more or less than their share.  You can measure the bias in units of croissants.  You can tune the degree of randomness by changing the width and shape of the distribution--this will also determine how far away any individual can get from "the same number of times".  Gaussians are easy; they allow for reasonable surprise without having tails that are too long ("unfair").  So the basic shape of the solution is (in Scala code)

case class Employee(var bias: Double) {
  def eat         { bias -= 1 }
  def buy(n: Int) { bias += n }
  def roll        = bias + stdev * Random.nextGaussian
}

You can keep track of who bought last and give them a hefty bias bonus (e.g. 10*stdev) to keep people from buying twice in a row save in the edge case where vacation structure allowed everyone to have bought "last" time.  (i.e. you buy, then go on vacation.)  Same thing for not being present on the day they're selected.  (If someone is absent every other day they eventually will come up as they burn through their bias bonus; I consider this a feature rather than a bug.)

So, you collect your list of present employees for the day, have them all roll for the lottery, pick the lowest, and update.  You can choose whether to have the buying bonus be equal to the number of employees (good when the cost is negligible but the trip to get croissants is burdensome), the number of employees present (good if the trip is easy but the cost is burdensome), or something in between (to acknowledge both burdens).  It's probably better to only have the "eat" penalty for people who are present, but you can do it either way if you feel that merely being on vacation doesn't give you a right pitch in less.
To construct a filtered random sequence, first you need to generate a random sequence.  Shuffling a list of the employees is as good a way as any to start.  Just go through the list, in order, from day to day.  If someone can't buy because they're absent or can't be told or bought before, skip them.  Now you have a problem: you're accumulating people who have been skipped.  That's okay, though.  When you get to the end of your sequence, append the list of skipped employees to the full list before shuffling.  Now the probability of coming up is proportional to the number of times you've been skipped, which maintains the "same number of times" property.

If you use a standard shuffle, it's also particularly easy to quantify the randomness when there are no vacations.  If you picked people completely at random, the knowledge of who was to bring next would contain $\log_2(N)$ bits of information if there were $N$ employees.  Instead, however, only $N!$ instead of $N^N$ possible sequences are allowed, so the information is reduced by $\log_2\left[\left( {N!} \over {N^N} \right)^{1/N}\right] \approx -{1 \over {\log(2)}} + {\log_2{\sqrt{2 \pi / N}} \over N } \approx -1.4$ bits (for large $N$; for $N=10$ it's $~1.14$).

Personally I favor the biased lottery solution as the control over the randomness is better.  With filtered sequences, you can come up with more complex ways to generate sequences.  For example, rather than taking a random permutation, perform local swaps out to a certain distance, or allow swapping of people out of the pool entirely (but they go onto the skipped-list)—but these things require more algorithmic effort.  With the lottery, you just adjust the standard deviation.


Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Check the first element.  Then check the last.  Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on.  Stop upon bounding the location of x to a region at the front or back of the list.

Once you've bounded it you can just do a binary search.

Can you see why this works?


Unique path sums in a DAG using vertex instrumentation

The paper of Ball can be found here: http://www.cs.ucr.edu/~gupta/teaching/260-08/Papers/pathprof.pdf

I think the solution is easy. In addition to the global variable r, we keep a global variable lastVertex. Before exiting a vertex v, we set lastVertex=v. Now, when entering a vertex, we know which vertex we came from and we only need to keep a map in each vertex from each possible previous vertex to the corresponding transformation of r. This is only slightly less efficient than with edges, as we need to do a lookup in a map in each vertex. For larger graphs, this may be memory intensive though.


What is complexity class $\oplus P^{\oplus P}$

$\oplus P^{\oplus P}$ denotes the class $\oplus P$ equipped with what's known as an oracle for $\oplus P$ — we say that it has been given the ability to determine whether or not a string $s$ is a member of a language $L$ contained in the class $\oplus P$ in a single operation.

I see that another commenter (sdcwc) has linked to the proof of $\oplus P^{\oplus P} = \oplus P$ (see these notes on a lecture from CS 538 at Rutgers). A complexity class $C$ that is an oracle to a class $B$ such that $B^C= B$, is said to be low for the class $B$. In this case, we say that $\oplus P$ is low for itself.


Why is least fixed point (lfp) important in program analysis

Any form of recursion or iteration in programming is actually a fixed point. For instance, a while loop is characterized by the equation

while b do c done  ≡  if b then (c ; while b do c done)

which is to say that while b do c done is a solution W of the equation

W  ≡  Φ(W)

where Φ(x) ≡ if b then (c ; x). But what if Φ has many fixed points? Which one corresponds to the while loop? One of the basic insights of programming semantics is that it is the least fixed point.

Let us take a simple example, this time recursion. I will use Haskell. The recursive function f defined by

f :: a -> a
f x = f x

is the everywhere undefined function, because it just runs forever. We can rewrite this definition in a more unusual way (but it still works in Haskell) as

f :: a -> a
f = f

So f is a fixed point of the identity function:

f ≡ id f

But every function is a fixed point of id. Under the usual domain-theoretic ordering, "undefined" is the least element. And indeed, our function f is the everywhere undefined function.

Added on request: in the comments OP asked about the partial order for semantics while loops (you presumed it was a lattice but it need not be). A more general question is what is the domain-theoretic interpretation of a procedural language which can manipulate variables and has the basic control structures (conditionals and loops). There are several ways of doing this, depending on what exactly you want to capture, but to keep things simple, let's assume that we have a fixed number $n$ of global variables $x_1, \ldots, x_n$ that the program can read and update, and nothing else (no I/O or exceptions, or allocation of new variables). In that case a program can be seen as a transformation of the initial state of the variables to the final state, or the undefined value if the program cycles. So, if each variable holds an element of a set $V$, a program will correspond to a mapping $V^n \to V^n \cup \{\bot\}$: for every initial configuration $(v_1, \ldots, v_n) \in V^n$ of the variables, the program will either diverge and yield $\bot$, or it will terminate and produce the final state, which is an element of $V^n$. The set of all maps $V^n \to V^n \cup \{\bot\}$ is a domain:

we use the flat ordering on $V^n \cup \{\bot\}$ which has $\bot$ at the bottom and all the elements of $V^n$ "flat" above it, and then $V^n \to V^n \cup \{\bot\}$ is ordered pointwise,
the least element is the function which always maps to $\bot$, corresponding to the program while true do skip done (and many others),
every increasing sequence has a supremum

Just to give you an idea of how this works, the semantics of the program

x_1 := e

would be the function which takes as input $(v_1, \ldots, v_n) \in V^n$, calculates the value $v_e$ of the expression e in state $(v_1, \ldots, v_n)$, and returns $(v_e, v_2, \ldots, v_n)$.


Adjacency matrix and recognizing hierarchy?

By definition you can check if a graph is a tree (regardless of its representation) with these facts:

The graph does not have cycles.
It only has a single connected component.

The first condition can be checked with a simple DFS checking if there is a back edge. The connected components can be counted using either DFS or BFS.

Regarding to an adjacency matrix, every tree is a bipartite graph. See this, but keep in mind that proving that a a graph is bipartite does not mean it is a tree.


Once you get the point, you can use Flood Fill Algorithm to replace the current color in the region containing the point with the new color.

Basically, this algorithm starts from a specified point and then recursively(or iteratively) keep replacing the current color with the new specified color in the neighbouring points till it reaches the boundary of the region.

It detects the boundary by checking for points having different color(different from current and new color). So you don't have detect/store the regions in advance.


According to the rules:

  player divides the original stack into two stacks that must be unequal.


Number of calls with length 2 array in quick-sort

First, note that you can write your recurrence as
$$
T_N = \frac{2}{N}\sum_{i=0}^{N-1} T_i.
$$
Consider now the generating function
$$
T(x) = \sum_{N=0}^\infty T_N x^N.
$$
We calculate
$$
\frac{T(x)}{1-x} = \sum_{N=0}^\infty \sum_{i=0}^N T_i x^N =
\frac{1}{2} \sum_{N=2}^\infty (N+1)T_{N+1}x^N = \frac{1}{2} \sum_{N=3}^\infty NT_Nx^{N-1}.
$$
On the other hand,
$$
\frac{d}{dx} T(x) = \sum_{N=0}^\infty NT_Nx^{n-1}.
$$
We conclude that $T(x)$ satisfies the differential equation
$$
\frac{d}{dx} T(x) = \frac{2T(x)}{1-x} + 2x.
$$
Additionally, $T(0) = 0$. Plugging this into Wolfram alpha, we obtain the solution
$$
T(x) = \frac{x^2(3x^2-8x+6)}{6(1-x)^2}.
$$
Using $1/(1-x)^2 = \sum_{N=0}^\infty (N+1)x^N$, we obtain for $N \geq 3$ that
$$
T_N = \frac{6(N-1)-8(N-2)+3(N-3)}{6} = \frac{N+1}{6}.
$$

Having computed the solution by brute force, it is easy to prove by induction. Suppose that $N \geq 3$. Then
$$
T_N = \frac{2}{N} \sum_{i=0}^{N-1} T_i =
\frac{2}{N} \left(1 + \sum_{i=3}^{N-1} \frac{i+1}{6}\right) =
\frac{2}{N} \left(1 + \frac{(N-3)(N+4)}{12} \right) = \frac{N+1}{6}.
$$


Collisions of prefixes of MD5 hashes in some fixed interval

Just to complete Yuval's answer, there are plenty of collisions if you pick the first 9 digits of the MD5.

For example:

md5('40236')  = f46657d67 3d95ccf8d12b1075ab7c653
md5('400704') = f46657d67 e7a3de02f64013bfcbd932c

Let $m = 2^{36}$ (nine hex digits), $n = 2^{24}$ (three bytes for an UNSIGNED MEDIUMINT);
assuming that MD5 is a good hash :), the probability $P(n)$ of a collision is:

$1 - m! / (( m - n )! * m^n) \approx 1 - e^{-n^2/2m} = 1 - \frac{1}{e^{2048}}$

And you'll find a collision on the first 9 digits with high probability ($P(n) \approx 0.99$) every $n = 2^{20}$ strings picked (whatever they are). See Birthday problem on Wikipedia.

So even if you use the binary encoding (three bytes) you obviously get plenty collisions:

Starting from 000000, the first  is:

md5( 0x013701 ) = 8015b8be cf7b0a7e744cd54ac76a302f
md5( 0x0725c6 ) = 8015b8be cf8140319e919766901824bf

Note that 0x0725c6 is a 19 bit number.


Is this a syntax error or a semantic error?

The classification as lexical/syntax/semantic error is largely artificial, governed by separate parts of your compiler: it the "lexical analysis" phase detects the error, it is deemed lexical; if the parsing (syntax analysis) phase does, it is classified as "syntax error", others are reported as "semantic errors" (or just pass through without detection, giving rise to a runtime error). This is more am implementation detail than a firm distinction. It is e.g. possible to do away with separate lexical analysis and do all as parsing, some "syntax errors" aren't really parsing errors, but undefined variables, some semantic problems can be detected when parsing. Some languages (infamously C++) are complex enough that checking syntax requires checking much beyond context free grammar aspects to catch "syntax errors".


Historical examples of bad security policies/mechanisms that we got stuck with through switching costs?

There were some boo-boos with WiFi, thus the various generations of security protocols. Fortunately, most of the heavy lifting is done in firmware that is uploaded to the card/computer.

Initial (analog) cell phone technologies were trivial to intercept, newer (digital) ones much harder, but there were (are?) still gaps. Needless to say, switching required redoing much infrastructure and everybody getting new phones.

For some entertaining war stories, check out Ross Anderson's "Security engineering" (available as PDFs for each chapter on his homepage). Nicely written, a real classic.


Priority of symbols in a notation for projections

No, there is no convention.

In some languages, there is an idiomatic name for the function that extracts the first element of the tuple (e.g., fst, hd) and/or the function that extracts the second element (e.g., snd).


What's the difference between a broadcast algorithm and a flooding algorithm?

Broadcast routing is of three types :

1.) N-way unicast routing - There are N destinations and the source sends a copy of the packet to each destination by making N copies of the packet
and addressing each copy to a different destination.

2.) Uncontrolled flooding - The source node sends a copy of the packet to
all of its neighbors. When a node receives the packet, it
duplicates the packet and send to all of its neighbors except the sender.

3.) Controlled flooding - A source node puts its address and broadcast
sequence number into the packet. It sends the packet to all of it's neighbor. Each node maintains a list of the source address and
sequence number of each broadcast packet it has received. When a node receives a broadcast packet. If the received broadcast message has the source address and sequence number already present in the list then it will drop the packet otherwise make a copy and forward it to all the neighbors except sender.


Karp hardness of digraph coloring without monochromatic dicycle

Our problem is $\mathrm{NP}$-complete by a Karp reduction from $\mathrm{NAE}$-$\mathrm{3SAT}$

In fact, both the undirected and directed version are $\mathrm{NP}$-complete. First, we will describe the reduction for the undirected version. Then, we show how to orient all the edges of the undirected graph to obtain a digraph to finish the reduction for the directed version.

REDUCTION FOR UNDIRECTED VERSION

Given an instance of $\mathrm{NAE}$-$\mathrm{3SAT}$, we will construct an undirected graph such that there exists a solution for the $\mathrm{NAE}$-$\mathrm{3SAT}$ instance if and only if it is possible to color the vertices of this graph by $2$ colors such that no cycle is monochromatic.

For each clause $j$, create a $K_3$ cycle each vertex of which corresponds to one literal of clause $j$.

Now, for each pair of opposite literals (one positive and one negative literal of the same variable) $l_{jm}=x_i$ and $l_{kn}=\lnot x_i$, we connect them by a gadget as follows. (Here, $l_{ab}$ is literal $b$th of clause $a$, where $1\leq b\leq 3$)

The gadget to connect $l_{jm}$ and $l_{kn}$ is described now:

Connect $l_{jm}$ and $l_{kn}$ by an edge
Create $3$ new vertices $a$, $b$, $c$ (each gadget has its own three vertices like these)
Connect these $3$ vertices $a$, $b$, $c$ to form a $K_3$ cycle
Connect each of $a$, $b$, $c$ with both $l_{jm}$ and $l_{kn}$

Call the obtained undirected graph $G$. Set $k=2$. The reduction returns the instance $(G,k)$ of our problem.

Now, we prove the correctness of our reduction (for the undirected version).

If the given $\mathrm{NAE}$-$\mathrm{3SAT}$ is satiafiable, then given a solution, one can color all the $\mathrm{TRUE}$ literal-vertices $\mathrm{RED}$ and all the $\mathrm{FALSE}$ literal-vertices $\mathrm{GREEN}$. For each gadget described above, we color $a$ and $b$ by $\mathrm{RED}$ and $c$ by $\mathrm{GREEN}$. Next, we show that this is a solution to the produced instance of our problem.

Clearly, we use only $k=2$ colors as required. For each $K_3$ corresponding to one of the clauses, its $3$ vertices cannot be colored by the same color, because a solution to an $\mathrm{NAE}$-$\mathrm{3SAT}$ instance would make every clause containing both $\mathrm{TRUE}$ literal (colored $\mathrm{RED}$) and $\mathrm{FALSE}$ literal (colored $\mathrm{GREEN}$).

For each gadget of $2$ opposite literals $l_{jm}$ and $l_{kn}$, we have that these $2$ are colored by different colors. So, every cycle (contained in this gadget) that contains both these two vertices is already non-monochromatic. Only one other cycle (contained in this gadget) is the $K_3$ of $a$, $b$ and $c$. But as mentioned above, $a$ is colored $\mathrm{RED}$ and $c$ is colored $\mathrm{GREEN}$. All other possible cycles in $G$ need to cross from a $K_3$ clause to other $K_3$ clause by passing through a gadget. But, to pass through a gadget of, say $l_{jm}$ and $l_{kn}$ (colored by different colors), such a cycle has to be non-monochromatic.

Conversely, if we can color $G$'s vertices by $2$ colors without making any cycle monochromatic, then we will now show that the given $\mathrm{NAE}$-$\mathrm{3SAT}$ instance is satiafiable.

For each literal-vertex $l_{jm}=x_i$, if $l_{jm}$ is colored $\mathrm{RED}$, we assign $x_i$ to $\mathrm{TRUE}$, otherwise assign it to $\mathrm{FALSE}$.

For each literal-vertex $l_{jm}=\lnot x_i$, if $l_{jm}$ is colored $\mathrm{RED}$, we assign $x_i$ to $\mathrm{FALSE}$, otherwise assign it to $\mathrm{TRUE}$.

Since each clause is a $K_3$ cycle, it has to contain both $\mathrm{RED}$ literal-vertex (assigned to $\mathrm{TRUE}$) and $\mathrm{GREEN}$ literal-vertex (assigned to $\mathrm{FALSE}$).

It is left to prove the consistency of the above mentioned assignment. This is guaranteed by the gadgets. Suppose to the contrary that there exist two oppisite literals $l_{jm}$ and $l_{kn}$ colored by the same color, that w.l.o.g. we can assume to be $\mathrm{RED}$. Then it is impossible to properly color $a$, $b$ and $c$. Indeed, since $a$, $l_{jm}$ and $l_{kn}$ form a cycle, we deduce that $a$ must be colored $\mathrm{GREEN}$. Similarly, $b$ and $c$ are also colored $\mathrm{GREEN}$. But, now the cycle $(a,b,c)$ is monochromatic. Thus, the above assignment is consistent. And we obtain a solution to the given $\mathrm{NAE}$-$\mathrm{3SAT}$.

REDUCTION FOR DIRECTED VERSION

We use exactly the same above reduction. Now, we have to orient all the edges of $G$ to obtain a digraph. For each, $K_3$ clause cycle, we are free to choose one of two ways to turn it into a directed cycle (dicycle). For each gadget of two opposite literals $l_{jm}$ and $l_{kn}$, we can orient to have an arc $(l_{jm},l_{kn})$ (the other way can be finished similarly). Now, we orient to make $3$ cycles: $(l_{jm},l_{kn},a)$, $(l_{jm},l_{kn},b)$, $(l_{jm},l_{kn},c)$. Then, we make one more cycle, namely $(a,b,c)$. By orienting like this, we can use all the above arguments for the undirected version. Note that the possible dicycles that cross from clause to clause still have to be non-monochromatic.


Differences between linear/nonlinear vs. deterministic/nondeterministic neural nets

Non linear means that there may be a correlation with the input, but it is not a linear one. A function is say to be linear in some argument (the input) when the ratio result/argument is constant. In your case, it is the ratio output/input. Actually, the mathematical definition is a bit more general.

Non determinism is of a different nature. The input/output relation is said to be non-deterministic when one of several result may occur, without any a priori known cause. This is usually modelelled mathematically, either by using a relation rather than a function, of by considering a function from the input domain to the domain of subsets of the output domain.

For example: if you consider inputs and outputs in the domain of integer, for each integer input, you have a set of possible outputs that are all integers.

When this set always contains only a single element, the function is deterministic, and the set can be replaced by this unique element.


How can Kruskal's algorithm return different spanning trees?

Cuts aren't made as part of Kruskal's algorithm; they are used in a proof that it always returns a minimum spanning tree. See e.g. here.

But you don't need them to answer the question in the title; instead, take as your graph a triangle with all 3 edges the same weight. Then any order on these edges is allowed and Kruskal's algorithm will return the tree consisting of the first 2 edges, whichever they are.


Context free grammar for {a^mb^n | m ≠ n}

Hint: Start with a CFG for the language $\{ a^{n+t} b^n : n \geq 0, t \geq 1 \}$.


Write through and write back cache policies

When you want a general formula for a particular case, just derive it.

Let the main memory access time be $x$, and the cache access time be $y$. Let the hit ratio be $h$ and the fraction of requests that are reads be $p$.

Now,
$$\begin{align}\text{Average access time}&=\text{Weighted average of read and write times}\\&=\text{Fraction of reads}\times\text{Average read time}+\text{Fraction of writes}\times\text{Average write time}\tag1\end{align}$$

Let us now go through the read process. Firstly, there are two possibilites - a cache hit or a miss. If it is a hit, the cache access time is the total read time. If it is a miss, then the total read time is the sum of the time taken to access the cache and the time taken to access the memory. The fraction of hits is given by the hit ratio. Again, we take the weighted average.

$$\begin{align}\text{Average read time}&=\text{Fraction of hits}\times\text{Cache access time}+\text{Fraction of misses}\times(\text{Cache access time}+\text{Memory access time})\\
&=hy+(1-h)(x+y)\tag2\end{align}$$

Now, the writes. It is given that the write policy is the write through policy. This means that when a write is made, irrespective of a hit or a miss, memory is accessed as well. As the memory access time dominates over the cache access time, and the hit ratio for writes is not given, ignore the difference in the times of accessing just the memory and accessing the cache and the memory.

$$\begin{align}\text{Average write time}&=\text{Main memory access time}=x\tag3\end{align}$$

Combining $(1),(2),(3)$, we get,
$$\begin{align}\text{Average access time}&=p\left[hy+(1-h)(x+y)\right]+(1-p)x\end{align}$$

Here, $p=0.85,h=0.92,x=100\text{ns},y=10\text{ns}$. Substituting,
$$\begin{align}\text{Average access time}&=0.85\left[0.92\times10+(1-0.92)(100)\right]+(1-0.85)\times100\\
&=0.85\times17.2+15\\
&=29.62\text{ns}\end{align}$$

Similarly, you can attempt the other cases mentioned in your question.


PSpace-completeness under PSpace reductions

Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that first decides whether its input $w$ is in $Y$ and then maps to a fixed "yes" instance of $X$ if so, and a fixed "no" instance if not.

Note also that the actual definition of PSPACE-completeness requires that every language in the whole of PSPACE reduces to the complete language. The definition you've given is circular, since it defines PSPACE-completeness in terms of itself.


Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?

Sure.  You can simultaneously run multiple threads on different CPUs in parallel; and also a single CPU can context switch between threads (i.e., both what you are calling simultaneous multithreading + temporal multithreading).   Nothing prevents it.


Selecting a polygon within an array of complex polygons

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive  x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to below then decrement. If the winding number is zero, then the point lies outside of the polygon, otherwise it lies inside.

You probably don't want to test every polygon every time the point moves, so I would pre-compute a bounding box or sphere for every polygon. I would then only test winding numbers against those polygons whose bounding shapes collide with the point in question.

Hope this helped.
Good luck!


The output of $f$ doesn't have to be of logarithmic size. This is why there is something to show.

To give an example, the function $f(x) = x$ can be computed in constant space but its output length is linear.


Is the tree shown a valid red-black tree?

You are correct $-$ the red-black tree you have drawn is not balanced.

For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed.

However for your tree, the path 00 results in a black height of $2$ and the path 1000 results in a black height of $3$. 0 = go left, 1 = go right.


What happens when two processes hold an election using bully algorithm simultaneously

Both processes will anounce themselves. However, the one with the highest indentifier will become the leader. For example, 3 and 4 announce themselves. 3 asks who has an id greater than me, and 4 responds. Then 3 knows 4 is the new leader. 4 does the same. No process replies. 4 tells everyone that he's the new leader.


Solve a recurrence using the master theorem

$f(n) = (n\cdot \lg n)^{1/2}$ and $n^{\log_b a}=n^{2/3}$, thus
$f(n) = O(n^{\log_b a})$ and even $f(n) = O(n^{\log_b a - \epsilon})$ for $\epsilon < 1/6$.

Why? because
$$\lim_{n\to\infty} \frac{f(n)}{n^{\log_b a - \epsilon}} = \lim_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} =  \lim_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\text{for }\epsilon< 1/6$$

Thus case 1 of the Master theorem should apply, and $T(n) = \Theta(n^{2/3})$.


Datastructure for a set of axis aligned rectangles that enables querying for point containment

Quadtrees sounds like a good choice.

How about the k-d tree of 2 dimension, which is also explained in a course note and at geeksforgeeks?

Each of the 2-dimensional versions of interval tree, range tree and segment tree may have a fair chance to solve the question efficiently.

I have used all above data structures to solve the same or similar or more complex queries. Depending on your situation, you may want to make some adjustment.

If the number of given points is much smaller than the number of possible points in the given rectangle domain, such as 22000 points in a $10^{18}$ by $10^{18}$ square, then some other choice might be even better. I once used a red-black tree, whose leaf nodes is another red-black tree and whose internal nodes of the same parent represent a partition of the contiguous rows represented by their parent into disjoint contiguous set of rows. The red-black tree at each leaf node stores the points in one particular row. In this way (and with a bit more technique), my final answer is able to run the fastest among all solution to the problem. Of course, my example may not be useful to your situation at all. Well, I hope that might encourage you to develop your own data structure that fits your situation more.


Efficient map data structure supporting approximate lookup

What you are looking for is "approximate near neighbor search" (ANNS) in the Levenshtein/edit distance. From a theoretical perspective, edit distance has so far turned out to be relatively hard for near-neighbor searches, afaik. Still, there are many results, see the references in this Ostrovsky and Rabani paper. If you are willing to consider alternative distance metrics for which there are simpler and better solutions, move on to the next paragraph. For ANNS in edit distance, there is a result due to Indyk, who shows how to build a data structure of size $n^{O(\sqrt{d})}$ that answers any query in time $O(d)$ and reports a string which is at most three times further than the string nearest to the query string (this generalizes to size $n^{O(d^\epsilon)}$ and approximation $3^{1/\epsilon}$). Here $n$ is the number of strings and $d$ is the maximum length of any string. The Ostrovsky and Rabani paper I linked above improve this result by mapping strings to vectors so that the $\ell_1$-distance (a kind of natural geometric distance similar to the euclidean distance) between vectors approximates the edit distance between the corresponding strings (this is called a "low-distortion embedding"). Once this is done, an ANNS data structure for $\ell_1$ can be used, and these turn out to be more efficient (see next paragraph).

If you are willing to consider other distances, then locality sensitive hashing (LSH) does a great job. Locality sensitive hashing is a technique pioneered by Indyk and Motwani for solving the ANNS problem, where points that live in a high-dimensional space (read long vectors, long strings, etc.) are hashed into a small number of buckets so that points that are near each other are mapped to the same bin with good probability and points that are far from each other are mapped to different bins, also with good probability. There is a great and very accessible survey article by Indyk and Andoni in CACM. This technique is simple and fast, and has small space requirements; there is code out there too (I think the article links to the code). It works well for things like Hamming distance (and in certain regimes $\ell_1$ distance) and Euclidean distance, cosine distance. Also, Muthu and Sahinalp design LSH schemes for a very natural generalization of edit distance, the block edit distance (where a some edit operations can operate on a block of symbols).

This kind of question is a good fit for cstheory.SE. There is a related question there, but it seems to ask for exact near neighbor.


Is this NP-hard: min-weight n-clique in a complete n-partite graph

The decision version of your problem (whether there is a clique of weight at most something) is NP-hard, by reduction from 3-SAT. Let $\varphi$ be a 3CNF formula with $m \geq 7$ clauses. We create an $m$-partite graph. Each part corresponds to a clause, has $7$ vertices corresponding to all satisfying assignments for the clause, and $m-7$ dummy vertices. All edges touching a dummy vertex have weight $1$. Edges connecting two conflicting assignments also have weight $1$. Edges connecting two non-conflicting assignments have weight $0$. The graph has a clique of weight $0$ iff $\varphi$ has a satisfying assignment.

We can also get a hardness of approximation result this way. Given a 3CNF formula $\varphi$ with $m \geq 7$ clauses, we create an $(m+1)$-partite graph. There is a part corresponding to each clause, which has $8$ vertices corresponding to all assignments to the clause, and $m-7$ dummy vertices. In addition, there is a part with $m+1$ special vertices. All edges touching a dummy vertex have weight $m^2$. Edges connecting two conflicting assignments also have weight $m^2$. Edges connecting two non-conflicting assignments have weight $0$. Edges connecting satisfying assignments (for clauses) and special vertices have weight $0$. Edges connecting non-satisfying assignments and special vertices have weight $1$. The minimal clique in this graph has weight equal to the minimal number of unsatisfied clauses in any assignment to $\varphi$. Therefore for every $\epsilon > 0$ it is NP-hard to decide, for $(m+1)$-partite graphs, whether the minimal clique has value $0$ or at least $(1/8-\epsilon)m$. In fact, by modifying $\epsilon$ slightly we get the same result for $m$-partite graphs.


Why bound of linear function is same as that of quadratic equation

$O$ only gives an upper bound; see also here. Clearly, $n^2$ is -- up to a constant factor -- an uppper bound for linear functions.

In fact, you can prove that

  $n^{k_1} \in O(n^{k_2})$ for all $k_1 \leq k_2$.

Together with

  $n^{k_1} + n^{k_2} \in O(n^{\max \{k_1,k_2\}})$ for all $k_1,k_2$

and the obvious

  $cn^k \in O(n^k)$ for all $c,k$,

you get a general version of your statement.


Halting problem under spatial restrictions

Yes (for Turing machines)

$A(n,B,d)$ can decide whether $B(n,d)$ will halt.

Note the fact that $B$'s writable memory is limited to $n$ units. This means that the number of possible states of $B$ is just $2^n$ (each possible memory configuration that $B$ may assume). Note also that $B$ halts iff it never goes back to a previously visited state, otherwise it would loop. This means that, if $B$ halts, it cannot do more than $2^n-1$ state transitions (as each state is visited only once).

Thus we can exploit the $2 \cdot n + c$ writable memory units of $A$ to build a machine which simulates B and counts the number of states it visits. We can do that by keeping the memory of $B$ in the first $n$ units, and a state counter $\gamma$ in some other $n+1$ units. We increment $\gamma$ at each state transition of $B$.

If $B$ halts, sooner or later the simulation of $B$ will reach a "HALT" instruction, and then we know $B$ halts. If $B$ does not halt, $\gamma$ will increase forever: as soon as $\gamma = 2^n$, we know that $B$ does not halt.


Lambda terms are simplified by the β-reduction rule:
$$(\lambda x.M)N\,\rightarrow_\beta\,M[x:=N]$$

It means, if you have a subterm that looks like $(\lambda x.M)N$ (called redex) you can replace it by $M[x:=N]$, which is $M$ with $N$ substituted for $x$. The replacement $M[x:=N]$ is often called contractum. (Capital letters likes $M$ and $N$ are used to denote terms.)

In your case, the first reduction would be:

$$(\underbrace{(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)}_{\mbox{redex}})(\lambda sz.sz)
\rightarrow_\beta \underbrace{(\lambda n.(\lambda sz.(\lambda sz.sz)s(nsz)))}_{\mbox{contractum}}(\lambda sz.sz)$$
where we replaced $m$ with $\lambda sz.sz$. Note that we now have $\lambda sz$ inside $\lambda sz$ which isn't very convenient (yet allowed). It is better to rename bound variables ($\alpha$-conversion) to be distinct, for example to:

$$(\lambda n.(\lambda uv.(\lambda sz.sz)u(nuv)))(\lambda sz.sz)$$

Some notes:

Substitution applies only to free variables. Bound variables stay always intact.
Sometimes substitution is not directly possible. For example, you cannot substitute $x:=y$ into $\lambda y.xy$ because $y$ is bound under $\lambda$. You'd get $\lambda y.yy$ which would change the meaning of the term. So first, you have to rename the bound variable first, for example to $\lambda z.xz$ and then you can safely substitute $x:=y$ to get $\lambda z.yz$. The Wikipedia article gives formal definition of substitution and shows when it's necessary to rename bound variables.
Lambda associates to the right, so $\lambda sz.sz$ is $\lambda s.(\lambda z.sz)$.
Application associates to the left, so $xyz$ is $(xy)z$.


Why are comparisons so expensive on a GPU?

GPUs are SIMD architectures.  In SIMD architectures every instruction needs to be executed for every element that you process.  (There's an exception to this rule, but it rarely helps).

So in your MinMax routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement takes up a cycle as well (even if it doesn't actually get "executed").

This problem is sometimes called thread divergence.  If your machine has something like 32 SIMD execution lanes, it will still have only a single fetch unit.  (Here the term "thread" basically means "SIMD execution lane".)  So internally each SIMD execution lane has a "I'm enabled/disabled" bit, and the branches actually just manipulate that bit.  (The exception is that at the point where every SIMD lane becomes disabled, the fetch unit will generally jump directly to the "else" clause.)

So in your code, every SIMD execution lane is doing:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

It may be the case that on some GPUs this conversion of conditionals to predication is slower if the GPU is doing it itself.  As pointed out by @PaulA.Clayton, if your programming language and architecture has a predicated conditional move operation (especially one of the form if (c) x = y else x = z) you might be able to do better.  (But probably not much better).

Also, placing the c < min conditional inside the else of c > max is unnecessary.  It certainly isn't saving you anything, and (given that the GPU has to automatically convert it to predication) may actually be hurting to have it nested in two different conditionals.


Number of $1$'s in a Kolmogorov-random number

I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.

Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the first argument in such a way so that there was no doubt where it ends, i.e. putting $0$ in between every digit and ending with $1$). $j$ denotes the $j$-th number with less than $n/4$ ones in a lexicographic order. The only problem we have now, is to evaluate how big $j$ can be.

We have $$j_{\max}=\sum\limits_{i\leq n/4}\binom{n}{i}$$

Often, when proving Second Shannon's Theorem, the above sum (even more general, with $\lambda n,\ \lambda\in (0,1/2]$) is evaluated to be less than $2^{nH(\lambda)}$ with $H(\lambda)$ being the entropy of a non-fair coin throw.

Thus, we get $j_{\max}\leq 2^{nH(1/4)}$. Since $H(\lambda)\leq 1$, a number with less than $n/4$ ones cannot be random besides finitely many cases.

More exactly, $$C_U(x)\leq 2\log(n) + nH(1/4) + c$$ and this, for $n$ large enough, is less than $n$.


Any evidence that one way functions exist?

AES is widely believed to be secure: many smart people have tried to break it and haven't been able.  This is not a proof, and it is arguable exactly how strong this evidence is, but it does count as heuristic evidence of some sort.  The fact that we haven't been able to find an algorithm to break AES does seem to count as some sort of heuristic evidence that no such algorithm exists -- again, not ironclad, not a proof, arguable how strong the evidence is, some might even call it weak evidence, but still evidence of some sort.

Moreover, it is easy to prove that if AES is secure, then the function $F$ defined by

$$F(k) = \text{AES}_K(0)$$

is one-way, where $0$ represents the block of 128 zero bits.  To be precise, if AES is a secure PRP, then $F$ is a secure one-way function -- this latter statement can be mathematically proven in a 100% rigorous way.  Here by "security" I refer to concrete security rather than asymptotic security.  If you're interested in asymptotic security, you'll need something more.

Thus, this is heuristic evidence that one-way functions exist: in particular, we have heuristic evidence that the $F$ defined above is one-way.  You can form your own judgement about how persuasive or how strong this evidence is; that probably comes down to a personal judgement.


Would increasing system memory speed reduce a Von Neumann Architecture bottleneck?

No, increasing the memory speed won't help solve the Von Neumann architecture bottleneck. The reason is as memory size is increased the time required to access the memory contents increases. So no matter how fast the memory is, if it is large it will be slower. So faster, smaller memories called caches are used to provide the illusion of a large, fast memory to the user.


Yes. Enumerate over all pairs $(M,p)$ of probabilistic Turing machines $M$ and polynomials $p$. Interpret each such pair in the following way: on input $x$, run $M$ for $p(|x|)$ steps, and if it doesn't halt, output "yes".


What is the difference between a lock convoy and lock/thread contention?

There are two blocking approaches used in locking algorithms when a lock is busy. spin wait or block (go to sleep, relinquish processor and wait for OS to awake the thread and re-schedule). Lock convoy as mentioned will happen when blocking strategy is used.
OS schedule threads on a core in time-sliced manner. Every thread get the processor for some per-determined time-slice, say 2 ms. OS in a round-robin fashion schedule all the threads in the ready-queue one by one. If say a thread after it get schedule and start its execution, say after 100 us, ask for a lock. If the lock is busy, the thread unable to get the lock, blocks and relinquishes processor. So remaining 1.9ms (2ms-100us) time slice is not used by the thread. Even after it is awaken by the OS when lock is free, the thread has to wait for its turn in the round-robin queue. The number of active threads could be in 100's.
Lock contention causes convoy effect.


why is the NL solution PATH negated unsufficient to prove unreachability

maybe i was a bit to specific, i had a general misunderstanding in how non-deterministic machines work. Here is what i figured:

an accepting nondeterministic turing machine always gives the right answer ("found something, therefore a solution exists",
on the other hand, a reject means "did not find anything" which is not the same as "there is no solution"

therefore a reject can't be trusted and any algorithm which uses a reject from a non deterministic (Existance) machine has to double check. Also this implies, that a non-deterministic machine could give a false negative.