What is more important in an algorithm, small runtime or small memory usage?

The best algorithm must certainly depend on the environment. What type of system is your client? What type of system is your server? What kind of transport system stands between them?

If, for example, your clients are Raspberry Pis then it is likely you want to reduce the amount of work you need to do on the client end - take the log(n) option.

If, your client is a Mars Rover you want to minimise the amount of data you need to send and minimise the computation required at the client. Perhaps use the log(n) option, perhaps not - depends on the cost of transporting the data and the computation cost at the other end.

If, however, your server is the LHC then use the n approach - you have probably the largest data bandwidth on the planet and the least amount of time to offload that data you've just collected.


The difference between theoretical complexity and practical efficiency

Big O Formally

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

Big O Informally

$O(f(n))$ is the set of functions that grow slower (or equally fast) than $f(n)$. This means that whatever function you pick from $O(f(n))$, let's name her $g(n)$, and you pick a sufficiently large $n$, $f(n)$ will be larger than $g(n)$. Or, in even other words, $f(n)$ will eventually surpass any function in $O(f(n))$ when $n$ grows bigger. $n$ is the input size of your algorithm.

As an example. Let's pick $f(n) = n^2$.

We can say that $f(n) \in O(n^3)$. Note that, over time, we allowed notation abuse so almost everyone writes $f(n) = O(n^3)$ now.

Normally when we evaluate algorithms, we look at their order. This way, we can predict how the running time of the algorithm will increase when the input size ($n$) increases.

In your example, both algorithms are of order $O(n^2)$.
So, their running time will increase the same way (quadratically) as $n$ increases. Your second algorithm will be four times slower than the first one, but that is something we're usually not interested in **theoretically*. Algorithms with the same order can have different factors ($c$ in the formal definition) or different lower order terms in the function that evaluates the number of steps. But usually that's because of implementation details and we're not interested in that.

If you have a algorithm that runs in $O(log(n))$ time we can safely say it will be faster than $O(n)$ [1] because $log(n) = O(n)$. No matter how bad the $O(log(n))$ algorithm is implemented, no matter how much overhead you put in the algorithm, it will always [1] be faster than the $O(n)$ algorithm. Even if the number of steps in the algorithms are $9999*log(n) = O(log(n))$ and $0.0001*n = O(n)$, the $O(log(n))$ algorithm will eventually be faster [1].

But, maybe, in your application, $n$ is always low and will never be sufficiently large enough so that the $O(log(n))$ algorithm will be faster in practice. So using the $O(n)$ algorithm will result in faster running times, despite $n = O(log(n))$

[1] if $n$ is sufficiently large.


What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

It is called monotonicity with respect to the inclusion ordering of sets.

More precisely, it is in this case increasing monotonicity since the order is preserved. If the order was reversed, it would be decreasing monotonicity.

It can also be called direct monotonicity and reverse monotonicity,  as increasing/decreasing seems used mostly for numeric functions.

The function is said to be strictly monotone iff (in the direct case)

$$\forall x,y : x\supsetneq y \Rightarrow f(x) \supsetneq f(y)$$


How to optimize a function by maximizing 1 variable and minimizing another?

You can't.  The optimal solution is not well-defined.  In general there will be a range of tradeoffs between minimizing time and uncompressed size, and you haven't specified anything that would allow uniquely identifying which you want.

Your first step is that you need to specify a single objective function, where the goal is to find a solution that maximizes the objective function.  Then you can try applying standard methods from mathematical optimization, e.g., gradient descent, Newton's method, and so on.


Minimize same placed elements in a list of permutations (Heap)

My initial guess, based on some cursory knowledge about Permutohedrons:

Given your set $S = {1,2,3,...}$, generate all permutations $P(S)$ and define a multigraph $G(V,E)$ where $V = P(S)$ (each permutation is a vertex) and the edge-set $E$ consists of pairs of permutations that share an element at a common location (e.g. $123456$ and $123465$ are connected by $4$ edges).

Your problem is then picking a subset of $V' \subset V$ s.t. the subgraph induced by $V'$ has as few edges as possible.

Considerations:

You can use a weighted graph instead of a multigraph. Replace $n$ edges with 1 edge with weight $n$. The optimization objective would then be total edge weight of the induced subgraph.
Based on the many symmetries, I would guess that it should be possible to achieve a very good (maybe even optimal) solution with a greedy algorithm.

Possible greedy algorithm:

Construct graph, initialize $V' = \emptyset$
Until $|V'| = n$:

For each $v \in V \setminus V'$: $v^+ :=$ total weight of edges between $v$ and $w\in V'$
If $v^+ = 0$, add $v$ to $V'$. Else, add vertex with lowest $v^+$.


You misread the text.  The authors of PETSc are just telling you that you can't avoid Amdahl's law.

They have done their best to parallelize every aspect of the linear solver.  But a real program is not just a call to a linear solver.  First you generate a matrix and then you pass the matrix to the linear solver.  If your matrix generator is slow, your whole program will be slow.

For example, suppose your original program spends 1000 seconds generating the matrix $A$ and vector $b$ and then you call a linear solver.  Your old (sequential) linear solver took 1000 seconds to find $x$ such that $Ax = b$.  Now you replace your old sequential linear solver with PETSc.  Suppose the PETSc authors did such a good job that the PETSc parallel linear solver finds $x$ in just 1 second!  Now how long does it take your program to run?  1001 seconds.  You got less than 2x speedup!  You need to do some work on your matrix generation code if you want to get a better speedup.

Pretty much the authors of PETSc are just telling you that a parallelized linear solver library is not a magic bean.


Understanding memory mapping conceptually

With memory-mapped files, a file is mapped to a pointer p, and byte #i of the file can be accessed through the pointer p+i. For each byte in the file, there must be an address available in the logical address space. With 32 bit, there are only 2^32 possible logical addresses, so 2^32 bytes in a memory mapped file that can be accessed at all.

You are confusing address space and RAM. A 64 bit computer with just 1 GB if RAM can memory map multi-terabyte files without problems. There will be lots of paging, but it will work. With a 32 bit computer, no chance.


Is there a Tree with deterministic traversal, but which nodes can vary?

You can do this with any binary space partitioning tree, such as a k-d tree or an octree.

Your basic approach can actually be made to work.  The reason you think it won't work is because you have a misunderstanding about how nearest-neighbor search is done in these trees.  Let me show you how they work and how to adapt them to your situation: you'll see that your idea does work fine and is quite a nice approach.

The basic principle of nearest-neighbor search is:

Each subtree represents a (rectangular) region of space.
You'll keep track of the closest point to $p$ found so far.
For each subtree T, you'll figure out whether it's possible that any point in the region corresponding to T could be closer to $p$ than the closest found so far.  If not (if it's impossible), then you won't look at T or any subtree of T.  Otherwise, you'll recursively test each child of T.

This yields a recursive algorithm that explores some subset of the nodes in the tree.

The basic point is that nearest-neighbor search doesn't explore just one path through the tree.  Rather, it might "fork" and explore multiple paths.  However, it's still faster than looking at every leaf, because they're able to prune some (but not all) subtrees.

For example, build an octree representing $P$, the set of all points.  Each leaf of the octree corresponds to one point in $P$.  Each internal node of the octree corresponds to an "octant" (a rectangular volume of 3D space).

Next, augment the octree as follows: each internal node $x$ has a bit that indicates whether any of the leaves under $x$ are active (whether any of them correspond to points in $S$).  Call the octant "active" if it contains at least one point of $S$, so the bit for node $x$ indicates whether the corresponding octant is active.  You can update these active bits efficiently: adding or removing a point to $S$ can be done in $O(\log |P|)$ time.

Now, to find the neighbor nearest to point $p$, invoke $\text{Closest}(p, r)$, where $r$ is the root node of the octree and the procedure Closest is defined as follows:

$\text{Closest}(p, x)$:

If $x$ is not active, return $\infty$.
If $x$ is a leaf, return $d(p,x)$.
Otherwise, set $\text{curBest}$ to $\infty$.
For each child $y$ of $x$, do:

If $y$ is active and $d(p,y) < \text{curBest}$, set $\text{curBest} := \min(\text{curBest}, \text{Closest}(p, y))$.

Return $\text{curBest}$.

Here we define $d(p,y)$ (the distance from $p$ to an octant $y$) to be the distance from $p$ to the nearest point in $y$, i.e., the minimum of $d(p,z)$ where $z$ ranges over all points in $y$.  Notice that this can be computed efficiently through a straightforward but ugly case analysis.

Notice that the structure of the octree depends only on $P$, but not on which points are active.  Thus, you don't need to adjust the partitioning or split points as you change which points are active.

You can do the same with a k-d tree instead of an octree.

There is no guarantee about what the worst-case running time of this procedure will be.  However, in practice, I would expect this to be pretty efficient, as large swathes of the octree can be "pruned".  In particular, I would expect it to be faster than the naive algorithm of computing $d(p,s)$ for each $s \in S$, if $S$ is large.


Checking large number of configurations with multiple constraints

Apparently, based on your comments, each condition is a linear inequality, you have a list of conditions, and you want to test whether an assignment satisfies all of the conditions, or find an assignment that satisfies all of the conditions.

Testing whether an assignment satisfies all of the conditions is just a simple matter of programming. For each inequality, you just plug in the values of the variables, then test whether the inequality holds or not.  No special solver or anything is needed.

It's also possible to find an assignment that satisfies all of the conditions, i.e., find values for all of the variables that makes all of the conditions true.  This is exactly the linear programming problem.  There are good, efficiently algorithms known for linear programming.  You can use any off-the-shelf linear programming solver.  They should very rapidly find a valid configuration.


Vertex cover algorithms for directed graphs?

Thanks for the edit!  This isn't vertex cover; it's something different.

There are simple algorithms for this problem.  Decompose the graph into a dag of strongly connected components.  (The dag is sometimes called "the metagraph".)  Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one vertex and add it to $S$.

The result will be the smallest set $S$ that meets your conditions.  This can be done in $O(V+E)$ time.

Answer to the original version of your question (now irrelevant):

Your problem, as stated, is trivial: the solution is the empty set $S=\emptyset$.

If, on the other hand, you meant that $e_{ij} > 0$ implies $i \in S$, the problem is also trivial: the set $S$ has to include the source vertex of every edge.  So, you just loop over all the edges $(i,j)$ and add $i$ to $S$.


How to convert a decision tree to an automaton?

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language.
The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision tree to an automaton.
Here are some examples:

Determining whether a person is overweight given their age, gender, height, and weight. This can be solved by a decision tree, or by a table.
Deciding whether a 64x64 image describes a dog or a cat. This can also be solved by a decision tree, though that's not recommended.
Deciding whether a given integer is a prime. This decision problem defines a language, the language of primes. Agrawal, Kayal and Saxena gave an efficient procedure for solving this problem in 2002, which however cannot be implemented by the kind of automata usually considered in theory of computation classes (DFA, NFA, PDA).
Deciding whether a given string is a palindrome. This decision problem defines a language, and can be solved by a pushdown automaton, but not by a DFA/NFA.


Indexing into a pattern database - Korf's Optimal Rubik's Cube solution

You don't explain what the numbers from 0 to 23 mean, but according to this answer, you can represent the state of the corners using eight pairs $(p_i,o_i)$, where $(p_0,\ldots,p_7)$ is a permutation of $(0,\ldots,7)$, $o_i \in \{0,1,2\}$, and $o_7$ (say) is determined by $o_0,\ldots,o_6$. In total, this gives $8! \cdot 3^7 = 88179840$ degrees of freedom. Assuming that you can decompose your $\{0,\ldots,23\}$ to pairs $(p_i,o_i)$, you can easily convert a position to an index by encoding separately the permutation $(p_0,\ldots,p_7)$ (which the AAAI paper explains how to do) and the values $o_0,\ldots,o_6$, which you can encode in base 3. Putting the two values together in the obvious way (for example, $3^7p + o$ or $8!o + p$), we get an index.


Local variables get assigned global addresses based upon call tree

This sounds similar to register allocation.  Normally, register allocation is done at the scope of a single function, but it can also be done globally (interprocedurally).  If you ignore all recursive and mutually recursive calls, you might be able to apply standard algorithms for register allocation to your situation.


No, the problem you've described is actually quite easy.  The high-level reason is that the index $i$ is roughly $n$ bits long, so we can actually afford to spend time polynomial in $n$.

Consider the following related problem: Given two integers $n$ and $k$, describe the $k$th move in the solution of the $n$-disk puzzle.  The input size is $\lg n + \lg k < n + \lg k$, but in fact, only the least significant bit of $n$ matters.  So even if $\lg k$ is significantly smaller than $n$, we can solve this problem in time polynomial in $O(\log k)$.

Suppose the disks are numbered from $0$ to whatever in increasing order by size, and pegs are numbered 0=source, 1=destination, and 2=spare.  Let us write $k = (2p+1)\cdot 2^d$ for some integers $p$ and $d$.  Then on turn $k$:

If $d+n$ is odd, then disk $d$ moves from peg $(p\bmod 3)$ to peg $((p+1)\bmod 3)$.
If $d+n$ is even, then disk $d$ moves form peg $(-p\bmod 3)$ to peg $((-p-1)\bmod 3)$.

We can easily compute $p$ and $d$ in time $O(\log k)$ by looping through the binary representation of $k$ from the least significant bit upward.  That's it.

Now suppose you really want the $i$th bit in the output sequence, where $i$ is part of the input instead of $k$.  If every turn is encoded using the same number of bits — specifically, $\lg(n+1)$ bits for the disk number, $2$ bits for the from-peg, and $2$ bits for the to-peg — then we just have to compute the $k$th move, where $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, and then extract the appropriate bit.  (Notice that $\lg(n+1)+4$ is linear in the input size, since we need to know $n$ to determine the output.)

On the other hand, if we're using a variable-length representation for the disk numbers, then we can find the move number $k$ in polynomial time by binary search.  We need to know  the total number of turns needed to move the top $m$ disks, for all $m\le k$, but this is given by the recurrence
$$
M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)
$$
which we can evaluate in polynomial time by dynamic programming.  The remaining details are left as a boring exercise for the reader.

(I assume I've made at least one off-by-one or parity error, but hopefully the main idea is clear.)


Finding a good loop invariant for a powering procedure

No, you can't say that $power \leq x^n$ is a loop invariant, since it is not maintained by the loop. For example, if $x > 1$ and at the current iteration $power = x^n$, then the invariant is satisfied at the beginning of the loop but not at the end of the loop.

Also, this loop invariant doesn't help you prove that at the end $power = x^n$, which is presumably your end goal.

Try to think of an invariant which describes the value of $power$ in terms of $x$ and $i$.


Reachability matrix in time $O(|V| \cdot |E|)$

This algorithm doesn't work. Consider a graph with four vertices 1,2,3,4 and edges $1\to2\to3\to4$. Your algorithm outputs $T(1,4)=0$ even though 4 is reachable from 1.

The running time analysis of the algorithm can be improved to $O(VE)$. The first loop takes time $O(V^2)$. The number of pairs $(v,u)$ in the second loop is the number of edges $E$, and for each pair $(v,u)$, the maximal number of $w$s is $V$. So the second loop runs in time $O(VE)$.


Time complexity of writing a number as power of 2's

Division by 2 is linear in the number of digits (lets call that $s$) $O(s)$ aka. $O(\log n)$.

output = [];
bool carry;
for(digit in digits){ // most significant digit first
    if(carry) digit+=10;

    carry = isOdd(digit);
    push_front(output, floor(digit/2));

}
if(output.front == 0) pop_front(output);
//carry is the new bit to push to the front of the result
// and output is the new digit array

Because the number of digits decreases with a constant rate (1 digit every 3 to 4 divisions). This algorithm results in a $O(s^2)$ time complexity aka. $O(\log^2 n)$.


Sample K representative frames within a video

The question misses a lot of detail, so I will try to make an educated guess.

I don't know of any specific algorithm for the task you are trying to achieve, but the first step towards your solution would be perhaps the computation of the average of the magnitude of the optical flow throughout the whole duration of a video. Why: you said that an interesting feature in your videos is the fact that the camera moves less while filming something interesting. Then, the magnitude of optical flow vectors will be expectedly smaller. If you plot the average magnitude of optical flow throughout time of the video, you could start to see parts where there is potentially something interesting here and there.

Edit: look-up at the algorithm used by Youtube for "smart" thumbnail selection. E.g. https://stackoverflow.com/questions/28263511/smart-video-thumbnail-generator-algorithm


An infinite language with no infinite RE or co-RE subsets?

Let's prove a more general result using diagonalization. Suppose $L_1, L_2, \ldots$ is a countably infinite list of infinite languages. Then there is an infinite language $L$ that doesn't contain any of them.

We construct $L$ in infinitely many steps. At each step $t$, we keep a list of words $A_t$ in the language, and a list of words $B_t$ outside the language; these will be monotone increasing, that is, $A_t \subseteq A_{t+1}$ and $B_t \subseteq B_{t+1}$. The lists $A_t,B_t$ will always be finite and disjoint, and furthermore $|A_t|$ will grow without bounds. We can take $L$ to be the union of all $A_t$.

Let $A_{-1}=B_{-1} =\emptyset$.
At step $t$, let $B_t = B_{t-1} \cup \{x\}$ for some $x \in L_t \setminus A_{t-1}$, and $A_t = A_{t-1} \cup \{y\}$ for some $y \notin B_t$. Now $|A_t| = |B_t| = t$.

Step $t$ ensures that $L$ doesn't contain $L_t$, and at the same time that $|L| \geq t$. Taking $t\to\infty$, we deduce that $L$ is infinite and is not a superset of any $L_t$.


How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

I won't go into the details of your specific case but try to answer the general problem.

In the unrestricted case there is a mapping from each of the $n$ (=512) input states to one of 2 output states and you want to restrict the function as follows:

Create a partitioning of the initial $n$ input states into subsets.
Your adapted function maps each of these subsets to an output

Proceed as follows:

Enumerate all input states from 1 to $n$ (this is then the index of that state)
Write a function $f(i)$ that generates all rotations/symmetric versions of an input state $i$ and take the lowest index of that set
Partition the set $1..n$ according to $f$, i.e. if $f(x) = f(y)$, they are in the same class. The result is a pairwise disjoint set of sets, where each set consists of 'similar' input states that should therefore also have the same output.
Let $P$ be the number of these sets.

Answering your questions should then be easy:

You could assign each of the $P$ sets an arbitrary output to get a unique function. $\Rightarrow 2^P$ functions
A bitstring of length $P$
Generate random integers (with more than $P$ bits each) and take the last $P$ bits.

a. Maybe consider the distribution of values generated by your RNG, i.e.: are the last $P$ bits uniformly (or whatever you desire) distributed?


What you have been trying to implement is a first-in-first-out(FIFO) fixed-sized data structure, which is commonly called a circular queue, circular buffer, cyclic buffer or ring buffer.

In addition to the requirement of circular queue, you want the numbers rolling around an interval such as from 0 to 99. Since all the numbers in use are contiguous, it is enough to use just two numbers, the smallest of them and the largest of them to represent them.

In fact, since the number of files is a constant once the maximum number of files have been reached, it is enough if we keep track of the count of all numbers ever used. So we can construct a much simplified special implementation of the circular queue.

Similarly to your code, we should use the modulo technique. Here is a simple and fully-working Javascript implementation. Both get operation and update operation runs in $O(1)$.

// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

The above implementation works for all possible integer pairs limit >= maximumKept. In particular, it works even if limit is maximumKept.

Here is a sample usage:

function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());


Do poly-time algorithms exist whose time complexity is unprovable?

Here is an example. Suppose that you're working within axiom system A, say ZFC. Gödel showed that if A is consistent then A can't prove that A is consistent. Consider the following program:

  On input $x$, go over all strings of length $\log |x|$, and check if one of them is a proof of the consistency of A. If so, loop for $2^{|x|}$ iterations. Otherwise, halt.

This is polynomial time if and only if A is consistent. If A could prove that this algorithm terminates in polynomial time then A has just proved that A is consistent, which is impossible if A is indeed consistent. Yet if we believe that A is consistent, then the machine does run polynomial time; but A unfortunately isn't strong enough to prove it.

Your second question asks whether there is an algorithm that, given a Turing machine $T$, answers in polynomial time whether $T$ is a polynomial time Turing machine. Unfortunately, this is undecidable. Suppose that we only consider Turing machines which don't depend on their input (say the first thing they do is erase their input). Such a machine $T$ runs is polynomial time if and only if it halts on the empty tape. Deciding whether a Turing machine halts is impossible.


What is an array that can be iterated circularly an infinite amount of times called?

The answer is circular buffer.
Such structure could be implemented using array or linked list, but you cannot call explicit array-based circular buffer as linked-list.

FSA cannot be "executed" infinitely (type 3 machine only uses fixed input and reads it ones), unless your FSA definition covers Turing Machines.


NSPACE for checking if two graphs are isomorphic

The algorithm you proposed can be made to work in $O(n \log n)$-space, where $n$ is number of vertices. While permuting the vertices of graph $G_1$, you can also keep the mapping and reverse mapping from and to original vertices. That way you need not rewrite the whole graph. And you can still check if a particular edge in $G_1$ maps to an edge in $G_2$ and vice-versa.

Also, planar graph isomorphism is log-space.


Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

Modern computers are not more powerful than a TM.
The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world.  For instance, it would include mechnical devices, electronic devices, a human following a procedure "mechnically", and so on.
Wikipedia does not define "can be calculated by an effective method" as "can be calculated by a TM".  It doesn't define "mechnical" as can be calculated by a TM.  Rather, it says that the Church-Turing hypothesis asserts that any computation that can be carried out mechnically, can be carried out by a TM.  That's not a definition of what it means to carry out a computation mechnically -- that's a consequence of the Church-Turing hypothesis.
I think you are getting confused about the difference between a definition of computation, vs what the Church-Turing thesis claims/asserts/conjectures to be true about computation. The Church-Turing thesis is not intended as a definition of computation; it's intended as a statement/claim/assertion about computation.  The Church-Turing hypothesis doesn't provide a formal definition of "effective computation" or "mechnical means"; it leaves that up to the intuition.


Going deeper with pseudo-polynomial time algorithm for set partitioning

You can extend the dynamic programming algorithm to handle this variant. Suppose that the weights are $w_1,\ldots,w_n$. You are looking for a vector $x \in \{0,\pm 1\}^n$ such that $\sum_{i=1}^n x_i w_i = 0$, and $\sum_{i=1}^n |x_i| w_i$ is as large as possible. This suggests two possible approaches. The first approach is to construct a large table keeping track of all possible pairs of values $(\sum_{i=1}^m x_i w_i, \sum_{i=1}^m |x_i| w_i)$, where $x_1,\ldots,x_m \in \{0,\pm 1\}^m$. This leads to an $O(nM^2)$ algorithm, compared to the $O(nM)$ subset-sum or partition algorithms.

The second approach is to explicitly list all vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$ (using dynamic programming), and choose the one maximizing $\sum_{i=1}^n |x_i| w_i$. This takes time $O(nM + nS)$, where $S$ is the number of vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$. In practice $S$ might be small enough for this approach to be practical.


Computing inverse matrix when an element changes

The Sherman-Morrison formula could help:

$$ (A + uv^T)^{-1} = A^{-1} - \frac{A^{-1} uv^T A^{-1}}{1 + v^T A^{-1} u}. $$

Let $u = (a'_{ij}-a_{ij}) e_i$ and $v = e_j$, where $e_i$ is the standard basis column vector. You can check that if the updated matrix is $A'$ then
$$ A^{\prime -1} = A^{-1} - \frac{(a'_{ij}-a_{ij})A^{-1}_{i\rightarrow} A^{-1T}_{\downarrow j}}{1 + (a'_{ij}-a_{ij})A^{-1}_{ij}}.$$


“Left identity” of Monad laws in Haskell is wrong

You should be more precise. When you say that f(x), f a and m >>= f are "the same", that does not make sense as written. f(x) and f a cannot be the same, they do not even use the same variables. Did you mean to compare f(u), f u and u >>= f? It is true that f(u) and f u are the same thing, but u >>= f is not. If f has type a -> m b (where m is the monad) then

in f u the type of u must be a, but
in u >>= f the type of u must be m a

So the types don't even match. Furthermore, if you look at concrete examples, you will see that >>= is not "just notation". It actually does things.

If we now look at the left identity law

return u >>= f  ≣  f u

we see that we cannot just rewrite the left-hand side to f u, or even f (return u). We must take into account what return and >>= do in a specific case. For instance, in the list monad we define

return x = [x]

and

(xs >>= f) = concat (map f xs)

The left identity law holds because of how concat and map work:

return x >>= f      ≣
[x] >>= f           ≣
concat (map f [x])  ≣
concat [f x]        ≣
f x

The above calculation was not just "notation"!


Mapreduce does not seem to have received significant academic attention and/or widespread enthusiasm nor does it seem to have yet been integrated into much of the large previously-existing literature and theory on parallelism. This is partly due to it being relatively new, but there may be other reasons.

One possible angle: this is apparently not widely acknowledged or recognized but MapReduce seems mainly oriented towards & optimized for what are known as embarrassingly parallel problems where the problem space can easily be partitioned into independent parts requiring virtually no intercommunication, i.e. the "map" step. (this is partly the basis of some criticism of the simplicity of the model as in the Wikipedia article.)

The "reduce" step is a communication-heavy step of merging/combining/aggregating the separate results into a combined structure. [1] are slides on the background & structure of typical embarrassingly parallel problems, which classic examples are:

image processing,
fractal calculations e.g. Mandelbrot set, and
Monte Carlo calculations.

Another angle is that MapReduce has some similarities to the "master-slave" design pattern where the "master" distributes jobs and also handles collecting the results, and some surveys on "master-slave" decomposition of parallel problems may be available.

Embarrassingly parallel problems are also naturally "finely granular" and Mapreduce seems especially suited to "fine-grained" parallelism problems (such that the "fine grains" can be highly distributed over many computing machines). "Fine-grained" parallelism is possibly not studied as much from an academic point of view because its intrinsically theoretically less problematic.

Another angle: it's similar to "Bulk Synchronous Parallel" [4]. The reduce step is similar to "barrier synchronization".

A survey from 2006 by academic parallelism experts [2] that was meant to be very comprehensive and forward-looking at the time identified 7 widespread "dwarves" or basic parallelism structures found in algorithms (Section 3.2). Conspicuously and surprisingly, none have a MapReduce-like structure; i.e. MapReduce type problems are absent from the survey (but note Monte Carlo methods are one of the "dwarves" and is again regarded as embarrassingly parallel).

This would also tend to support the view that MapReduce is a kind of "toy" parallelism model. However! that point is not meant to detract from its widespread usefulness in many applications. Particularly with parallelism there can be great value in simpler models that avoid complexity and thereby also various pitfalls.

[1] Embarrassingly parallel overview

[2] The landscape of parallel computing: the view from Berkeley

[3] Current parallel models for computation tcs.se

[4] Is the mapreduce framework a type of BSP tcs.se


Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

Condition 3 as in the question, "$\forall i >0,  \exists  z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we "pump down" $uvwxy$ to $uwy$.
The difficulty of applying pumping lemma comes from, indeed, recognizing "the possible cases for the $vx$" correctly and organizing them in a way that is easy to pump the word up or down to be not in the language.
Since the condition on the words in $L$ is about the number of $a$s, $b$s or $c$s in them, we will classify $v$ and $x$ also in the number of $a$s, $b$s or $c$s in them. For pumping length ${n}$, we will let $z$ be $a^n\#b^n\#c^n$, the simplest word in $L$ with length at least $n$.

If either $v$ or $x$ contains $\#$, $uwy$ will have less than 2 $\#$s, hence not a word in $L$.

Otherwise, all symbols in $v$ must be the same, and all symbols in $x$ must be the same.
Since we have 3 symbols, $a,b,c$ in $z$, (at least) one of $a,b,c$ will be missing in $vx$.
The number of $a$s, the number of $b$s and the number $c$s in $uvwxy$ are the same. Since $uv^2wx^2y$ is $vx$ "more than" $uvwxy$, the number of that missing symbol in $uv^2wx^2y$,  will be less than both the number of $s_v$ in it if $s_v$ is the symbol in $v$, and the number of $s_x$ in it if $s_x$ is the symbol in $x$.
Since $|vx|\ge1$, either $s_v$ or $s_x$ exists. This means $uv^2wx^2y$ is not in $L$.

Since we can always pump $z$ outside of $L$, $L$ does not satisfy the pumping lemma. So, $L$ cannot be context-free.

I can assume that v or y are only in first part $u$ or second $v$ or $w$
but also $vxy$ can be in between $a's$ and $b's$ including the $\#$ between them.

I don't quite understand your statement literally.
However, apparently, you wanted to say that given $z$, there are various possibilities for $u$, $v$, $w$, $x$ and $y$, which is totally true. Only the usage of some abstraction or general property (which might be simple or complicated) will enable us to cover all of them. That is where the fun or wisdom are.


Why is the complexity of the BFS O(V + E)?

Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$.

This can be viewed as a simple instance of aggregate analysis.


Division modulo a prime in modular arithmetic

To divide $b$ by $a$, you follow two steps: first you find $u$ such that $au \equiv 1 \pmod{p}$, and then you compute $bu \pmod{p}$. To find $u$, you run the extended GCD algorithm on $a$ and $p$. If it is indeed the case that $a \not\equiv 0 \pmod{p}$, then since $p$ is prime $(a,p) = 1$. So the GCD algorithm will come up with numbers $u,v$ such that $$ au + pv = 1. $$ In other words, $au \equiv 1 \pmod{p}$.


Regular expression for words containing single 1 and even number of 0s

If a word contains exactly one 1 and an even number of zeroes, then we can decompose it in one of two different ways:

An even number of 0s, followed by 1, followed by an even number of 0s.
An odd number of 0s, followed by 1, followed by an odd number of 0s.

You take it from here.


Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?

I think you might be confusing a couple of things.

First, the complement of any problem in NP is in CoNP by definition. No further conditions are required. Second, admitting a polynomial time algorithm to verify solutions, and belonging to the class NP, are equivalent statements.

Third, Goldbach's conjecture is a mathematical statement, which under standard axioms is either true or false. That means that as a decision problem, in the same fashion that any other mathematical statement, Goldbach's conjecture has a constant time solution: machine A answers "true", machine B answers "false". Necessarily one of them is right, and they both take constant time. Obviously this is not helpful at all.

So you probably meant to ask about the problem that given an even integer N > 2 asks you to decide whether it can be expressed as the sum of two primes. This problem is indeed in NP as you said, because if N = p + q for primes p, q. Then $\left<p,q\right>$ is a solution that can be verified in polynomial time, by using the poly-time algorithm to first check that p and q are indeed primes, and then any addition algorithm. I don't know if there is a polynomial time algorithm for this problem, but I wouldn't be surprised if there is one.

If Goldbach's conjecture is true, then the machine that answers "yes" without even looking at the input accepts the language described above and runs in constant time.


How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?

I can see some similarity too, but only in a loose sense; there are also some significant differences.

Here's the similarity.  Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$.  Then you can think of the Bitcoin proof-of-work as being: find $x$ such that $H_2(x)=0$.  This is loosely similar to the Goldwasser-Sipser protocol; you could imagine that Merlin is the bitcoin miner and Arthur is the verifier, and the goal is for Merlin to prove to Arthur that Merlin has probably done at least about $2^{d-1}$ hash computations.  Or, if we let $S$ denote the set of values $x$ such that Merlin has computed $H_2(x)$, you could think of the goal being to prove that $|S|$ is at least $2^{d-1}$ or so.  Now if you imagine that Arthur always chooses $y=0$ in the Goldwasser-Sipser interactive proof, we get the same kind of computation.  So in that sense there is a similarity.

However, the correspondence is imperfect.  The threat models for the two schemes are quite different: Goldwasser-Sipser deals with a Merlin with unbounded computational power, whereas Bitcoin assumes the miner's computational power is limited.  The requirements for the hash function are quite different: Goldwasser-Sipser only needs a pairwise independent hash, whereas Bitcoin needs a cryptographically secure hash.  Also the nature of the set $S$ is different: in Goldwasser-Sipser the set $S$ is well-defined and there is a method specified in advance that Merlin can use to prove that a certain value is an element of the set, whereas in my analogy $S$ is only loosely defined and we don't have a clear way to prove that an element is a member of $S$.


how to prove the following is a bijection?

One option could be adding more parameters to $\chi$ so to make both $\Gamma$ and a fresh name source $\phi \in {\sf Names}^\infty$ explicit:

$$
\begin{array}{l}
\chi(\Gamma, x, X;\phi) = X \mbox{ if } x \not\in\Gamma
\\
\chi(\Gamma, x, \phi) = X \mbox{ if } x:X \in\Gamma
\\
\chi(\Gamma, \lambda x. t, X;\phi) = abs(X, \chi(\Gamma;x:X, t, \phi))
\\
\chi(\Gamma, t_1 t_2, \phi) = app(\chi(\Gamma, t_1, \phi^1),\chi(\Gamma, t_2, \phi^2))
\\
\qquad \mbox{where } \phi = \phi^1_0 \phi^2_0 \phi^1_1 \phi^2_1 \phi^1_2 \phi^2_2 \ldots
\end{array}
$$

You can then state a form of injectivity as
$$
\chi(\Gamma, t_1, \phi) = \chi(\Gamma, t_2, \phi) \implies t_1 = t_2
$$
and surjectivity as
$$
\forall T.\ \exists \Gamma, t, \phi.\ \chi(\Gamma, t, \phi) = T
$$

Note that some stronger forms of injectivity do not hold. E.g.
$$
\chi(\Gamma_1, t_1, \phi) = \chi(\Gamma_2, t_2, \phi) \implies \Gamma_1 = \Gamma_2 \land t_1 = t_2
$$
is false since
$$
\chi(x:X,x, \phi) = \chi(y:X,y, \phi) \land x:X \neq y:X
$$
Similarly, this does not hold:
$$
\chi(\Gamma, t, \phi_1) = \chi(\Gamma, t, \phi_2) \implies \phi_1 = \phi_2
$$
since only a finite portion on $\phi$ is needed by $\chi$.


How to prove that "Total" is not recursive (decidable)

A set $A$ is recursive iff $A$ is recursive enumerable and $A^c$ is recursive enumerable. You know that $Halt$ is recursive enumerable but not recursive so $Halt^c$ must not be recursive enumerable. You can show that $Total$ is not recursive enumerable (and therefore not recursive) by showing that it is reducible from $Halt^c$.

Formally, to show that $Halt^c \leq_M Total$ you need to find a total computable function $f$ such that $$x \in Halt^c \Leftrightarrow f(x) \in Total$$


Which areas in CS will be (or have been) most affected by fully homomorphic cryptography?

Before turning to your actual question, let me mention that there aren't any practical implementations of fully homomorphic encryption. There are some implementations that are far from being practical, and it's hard to guess whether that will change in the foreseeable future.

Fully homomorphic encryption is a goal in itself, as it enables outsourcing computation resources without sacrificing privacy. As such, its applications are mainly outside computer science, in the same way that the word processor Microsoft Word doesn't have any applications inside computer science (other than writing papers; though you should do that in LaTeX).

That said, fully homomorphic encryption could be used as a building block for other cryptographic applications. Vaikuntanathan's technical survey article contains some pointers in Section 6.4: verifiably outsourcing computation; and constructing short non-interactive zero-knowledge proofs. The latter has other applications and is not an end in itself, see Groth's technical survey article.


Run-time of Hungarian algorithm - matrix formulation


Decomposing a bipartite graph of maximal degree d to d matchings

Possible approach: If a bipartite graph is $d$-regular then it can be decomposed into $d$ perfect matchings by Hall's theorem. Any bipartite graph of maximal degree $d$ can be completed to a $d$-regular bipartite graph (possibly by adding vertices).


Thirty-one game. Prediction of the winner

This kind of question can be answered using a simple recursive procedure.

A state of the game consists of:

a sequence $a_1,\ldots,a_n$ describing how many cards of each value in $1,\ldots,n$ remain (in your case, $n = 6$).
the number of "points" remaining $p$.

Your initial state is $\vec{a}=(4,4,4,4,4,4)$ and $p = 31$.

For each state $(\vec{a},p)$, there is a sequence of possible moves, which in this case is
$$
N(\vec{a},p) = \{ (a_1,\ldots,a_{i-1},a_i-1,a_{i+1},\ldots,a_n),p-i : i \in [n], a_i \geq 1, i \leq p \}.
$$
Let us say that a position is winning if the first player wins when starting from it. A position is winning iff there is a next position which is losing, and so the winning predicate $W(\vec{a},p)$ satisfies the recurrence
$$
W(\vec{a},p) = \bigvee_{\vec{b},q \in N(\vec{a},p)} \lnot W(\vec{b},q).
$$
When $N(\vec{a},p) = \emptyset$, the disjunction is empty, and so $W(\vec{a},p)$ is false.

In your case, you can easily calculate $W((4,4,4,4,4,4),31)$ to be true. The winning moves are $1,2,5$.

Here is sage code that calculates this:

@CachedFunction
def game(cards, target):
    return [i for i in range(len(cards)) if target >= i and cards[i] >= 1\
    and len(game(cards[:i] + (cards[i]-1,) + cards[i+1:], target-i)) == 0]

This code also allows cards with value zero. You can run it like so:

sage: game((0,4,4,4,4,4,4),31)
[1, 2, 5]

It outputs the set of winning moves (if any).


Representation of unsigned integer on a little endian, big endian computer

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer

According to the dictionary, the definition of "numerical value" is "a real number regardless of its sign", in other words absolute value. Since the integer is unsigned, its numerical value is itself, and that will not change no matter how the integer is stored, little or big endian style, written on a napkin with lipstick in base seven, notches on a bedpost, or whatever. Therefore, the first line of the question is meaningless, which is always a nice start.
Additionally, the question confuses memory representation and integers. Two bytes in memory that look like (0x00,0x01) represent the integer 0x0100 in little-endian mode, but you can't say "let's add 255 to (0x00,0x01)" because (0x00,0x01) is not the number 0x0001 although it looks like it.
A correctly worded question would be:
"There are two bytes in memory. A big-endian cpu reads them with a uint16 load instruction and gets an uint16 value. A little-endian cpu reads the same two bytes and gets an uint16 value that is 255 higher than the big-endian cpu's value. What are the two bytes in memory?"
(One could also ask what uint16 one of the cpus gets)
Then it's pretty simple:
Memory    uint16     uint16
dump      read by LE read by BE
0x66 65   0x6566     0x6665
0x65 66   0x6665     0x6566    correct
0×00 01   0x0100     0x0001    correct
0×01 00   0x0001     0x0100
0×42 43   0x4342     0x4243    correct
0×43 42   0x4243     0x4342

According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.

Having nuked the question, let's play jeopardy and try to figure out what question you and your colleagues are answering.
Basically, to misquote a famous crook, you're having a disagreement over what the word "represents" represents. One thinks it is the memory representation in little-endian (although it is written wrong in the question, and honestly if the word "memory" was mentioned it wouldn't hurt for ease of comprehension) and the other thinks it's the integer itself (probably because the 0x values are written as integers not bytes). So you're both picking from a different column of my table above.
We will have to wait for the end of the war between little endians and big endians to know what the peace treaty says about who's right.
Another way to not fix the question would be: If the memory representation of a 2-byte unsigned integer on a little endian computer looks like it is 255 more than that on a big endian computer to a human reading the memory bytes in big endian order, which of the following choices represent(s) the unsigned integer?
However, this reveals to all the rampant systemic endianness supremacy asserting that humans of the wrong endianness are lower-class citizens. This implicit endianness bias and oppression must stop! As of today, the DIE commitee dictates that everyone will switch to the more inclusive and safe middle-endianness, and both-endians colonizers will be sentenced to pay reparations to native middle-endians.


What is the property of a PL that extracting a subroutine should not change the meaning?

I believe you are looking for Morris style Contextual Equivalence. Which says that the meaning of
a term (in your case a subroutine) should not change in any context.

If, $⟦ \cdot ⟧ : term \to \mathcal{D}$, is the meaning function then
$$\forall C. ⟦C[t]⟧ = ⟦ C ⟧ \circ ⟦ t ⟧ $$
Where $C[\cdot]$ is a context with a hole in it.


Logarithmic space verifier with unbounded witness

Let $N$ be the total number of configurations of the machine other than the witness tape, namely state, location of the input tape head, contents of the work tape, and location of the work tape head. Note that $N$ is polynomial in $n$.

We can assume without of generality that at each step, the machine reads a bit from the witness tape, and it affects its decision (we can accommodate that by adding dummy bits to the witness tape at locations where the original machine doesn't read the witness tape). The machine terminates once the witness tape runs out.

I claim that for any witness $w$, there is an equivalent witness $w'$ with $|w'| < N$. Here equivalent means that when the machine terminates, it is in the same configuration. The proof resembles that of the pumping lemma: if $|w| \geq N$, then some configuration must repeat, and so we can remove the corresponding part from the witness.

Thus, without loss of generality, the witness is of size at most $N=\operatorname{poly}(n)$. So this definition coincides with the usual definition of $\mathsf{NL}$.


What is a good reference to learn about state transition systems?

One of the key uses of state transition systems, also known as labelled transition systems, is for modelling concurrent systems.

One very nice, delightful even, book that uses labelled transition systems to give semantics to concurrent formalisms CCS and the $\pi$-calculus is
Communicating and Mobile Systems: the Pi-Calculus by Robin Milner. Definitely worth reading.

Principles of Model Checking by Christel Baier and Joost-Pieter Katoen is about model checking concurrent systems, so early in the book labelled transition systems are introduced to give semantics to such systems. This book also talks about probabilistic labelled transitions too.

Another possibility is Concurrency: State Models & Java Programs by Jeff Magee & Jeff Kramer. This book takes a more practical approach, but comes with an analyzer for systems described using labelled transition systems.

I don't know much about continuous dynamic systems. Perhaps you want to look at hybrid systems?


Comparing turing based programming languages

The notion  you are looking for is probably Turing completeness.  All languages that are Turing complete are essentially equivalent in what problems they can solve (at least in principle).   Most general-purpose programming languages are Turing complete.


How does the problem of "Scheduling to Minimize Lateness" exhibit optimal substructure?

Let us refine the "definition" of the optimal substructure property given in CLRS into two definitions.

A problem exhibits strongly optimal substructure if every optimal solution to the problem contains optimal solutions to subproblems.
A problem exhibits weakly optimal substructure if there is at least one optimal solution to the problem contains optimal solutions to subproblems.

What you see in the problem of "Interval Scheduling to Minimize Lateness" is the weakly optimal substructure. Take your example of three jobs $J=\{J_1, J_2, J_3\}\,$ with processing time $t_1=6,t_2=2,t_3=2\ $ and deadlines $d_1 = 2, d_2 = 7, d_3 = 8.\,$ One optimal solution is to schedule $J1,J2,J3\,$ in that order, which contains optimal solutions to all subproblems.
Weakly optimal substructure happens often when the goal of an optimization problem is not restricting enough to guarantee every optimal solution must contain optimal solutions to subproblems.
Here is a version of the interval scheduling problem that exhibits strongly optimal substructure. There are two changes in the problem statement compared to the previous one. What is to be minimized is their total lateness instead of their maximum latess. Also the lateness of a job is allowed to be negative. While this version of the problem is rather trivial to solve, it does serve to illustrate the concept of strongly optimal substructure.

Input: A finite set $J= \{J_1, J_2, \ldots, J_n\}\,$ of $n$ jobs, their processing time $t_1, t_2, \ldots, t_n$ and deadlines $d_1, d_2, \ldots, d_n$. We assume that all jobs were available to start at the common start time $0$.
Output: A schedule of these jobs to minimize their total lateness. Each job must continue processing once started. At any time, there can be at most one job that is being processed. Suppose a job $J_i$ is scheduled at time $s_i$, then its lateness is defined to be $l_i = s_i + t_i - d_i\,$. The total lateness is the sum of all $l_i$.


Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

The answer seems to be negative, according to Corollary 4.12 of Verifying Time Complexity of Deterministic Turing Machines by David Gajser (ArXiv).


Recursive type encoding on System F (and other pure type systems)

There is a convention in category theory that the same symbol is used for a type constructor and the map function over that type constructor. Hence, if f : X -> Y then F f : F X -> F Y.


How to remove null production from context free grammar?

Your simplification is wrong. The language of the first grammar includes $b$, but the one of the second grammar does not.
If you replace the definition of $A$ in the productions of $B$ you obtain $B \to b \mid \epsilon$. Then if you replace $A$ and $B$ with their definition in $S$ you have.
$$
S \to a \mid bb \mid b \mid aba \mid aa
$$


Does increasing k in a k-way set-associative cache always lead to a better miss rate?

It's not guaranteed; it may depend on the data. Let's say an 8-way associative cache can hold 8 items at position 512k + j for each fixed j, and a 4-way associative cache can hold 4 items at position 1024k + j. My algorithm accesses locations 1024k + 512 + j for just four values k all over again. And locations 1024k + j for lots of values k, so there is basically no cache reuse.

In this case, 4-way associative caches has lots of hits and 8-way almost none. (There may be some mistake made somewhere, but you should figure out a pattern where 4-way ends up better).

For random access patterns, and for not carefully constructed patterns, higher associativity will be better. There is of course the problem that picking one out of 8 sets will take more time than picking one out of 2 or out of 4 sets.


Proving big-theta complexity with constants in $f(n)$

You can find the definitions of big O notations on Wikipedia. They agree with your definition of big $\Theta$.
As for your actual question, the answer is actually quite subtle. Sometimes it is possible to find constants $c_1,c_2,n_0$ which work for all values of the parameters. For example, in your case, all $n \geq 1$ satisfy
$$
1 \cdot n^{\max(a,b)} \leq n^a + n^b \leq 2 \cdot n^{\max(a,b)},
$$
and so you can say that $n^a + n^b = \Theta(n^{\max(a,b)})$.
(As a side note, you can also say that $n^a + n^b = \Theta(n^a + n^b)$, or that $n^a + n^b = \Theta(n^a + 2n^b)$; but usually we aim at the simplest possible expression, or an expression of a particular form, say $n^\alpha \log^\beta n$.)
In other cases we are not so lucky. For example, $\log^k n = O(n)$ for all $k$, but the relevant constants depend on $k$. Sometimes this makes no difference, but in other cases it is important to know that the constants depend on $k$. When it does matter, we sometimes use the notation $O_k(n)$ to stress that the hidden constants depend on $k$. This is not completely standard, but pretty common. When the hidden constants are independent of some parameter, we can explicitly say so – $n^a + n^b = \Theta(n^{\max(a,b)})$, where the hidden constants are independent of $a,b$.
In your case, since you are only interested in an isolated estimate, you don't care about the dependence of the hidden constants on the parameters. So for you, $\log^k n = O(n)$ holds, even though the hidden constants depend on $k$, since for any particular $k$ this statement holds. This is the usage in the master theorem, for example – the constants there depend on the parameters, but usually it makes no difference, because the parameters are fixed in any given application, in the vast majority of circumstances.


Yuval Filmus already pointed you towards recommender systems, which in your case is the right way to go.

However, since you asked for a graph formulation and tagged it with graph-theory, we will go out of our way to put this into such a setting.

Definitions

A graph is called bipartite if its vertices can be partitioned into two sets, say $U$ and $V$ in such a way that all edges are between $U$ and $V$.  (Coincidentally a graph is bipartite if and only if it is two-colorable.)

A bipartite graph is called complete if every edge between $U$ and $V$ are present, i.e., it is isomorphic to $K_{n,m}$ for some $n,m \in \mathbb{N}$.

A bipartite graph is called a bicluster if its connected components induce complete bipartite graphs.

The problem

An editing problem is a graph problem where we want to add or delete (as few as possible) edges to make a graph have a certain property.  So let us define Bicluster Editing as the following problem:

Given a bipartite graph $G = (V, U, E)$ and a natural number $k \in \mathbb N$, does there exists a set of edges $E'$ such that $G' = (U, V, E')$ is a bicluster and $|E \triangle E'| \leq k$ (where $\triangle$ is the symmetric difference)?

Now, what does this mean?  If such a set exists for a small $k$, you have partitioned your users and foods into equivalence classes such that in every equivalence class, all the users like the same foods and all the foods are liked by the same users, changing the graph very little.

Is it practical? No.  But at least it's NP-complete.


Finding a minimal width strip which encloses a set of points in the plane

Take the convex hull of your set of points. Then use "rotating calipers" to
find the optimal strip.
What is needed here to make this work is a lemma that characterizes a
potentially optimal solution: Could the optimum occur without one supporting line
through two points ("flush" to the hull)?

Added. Yes, that flush-lemma holds, because more-horizontal strips are preferred. So: for each edge $e$ of the convex hull $H$,
extend $e$ to a line $L_1$, and let $L_2$ be
the parallel line supporting $H$ on the other side. Compute the vertical distance between $L_1$ and $L_2$.
Select the shortest distance among all alternatives.


"Graph search" is a very general term that includes breadth-first-search and depth-first-search. Let's say you wanna do BFS on this problem.

For this problem, think of a matrix, or a state, as a node in the graph. The pseudocode might look like this:

Push the "input node" into a queue.
While desired output node is not found:

Pop an element from the queue
Go through all the "moves" that could be done on that node. For a 3x4 matrix there would be 12 possible moves.
Push the results of each move into the queue.

Hope this helps!


Prove the following language is regular?

The answer depends on whether $L_1$ is a language over $\{a,b\}$ or over $\{a,b,c\}$.

$L_1$ is a language over $\{a,b\}$

In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular:
$$
L_2 = \{wcv \mid |w|_a+2|v|_b \equiv 3 \bmod 5 , w,v \in \{a,b\}^*\}.
$$
Your language is $L = L_1cL_1 \cap L_2$.

$L_1$ is a language over $\{a,b,c\}$

In this case we have to be more careful. Given a DFA (or an NFA) for $L_1$, we construct one for $L$ which in three stages:

Simulate $L_1$ and keep track of the number of $a$s modulo 5. Whenever at an accepting state of $L_1$, add a nondeterministic move to stage 2.
Read $c$.
Simulate $L_1$ (starting from its initial state again) and keep track of the number of $b$s modulo 5. A state is accepting if it is accepting for $L_1$ and the constraint $|w|_a+2|v|_b$ is satisfied, where $w$ is the word read at the first stage, and $v$ is the word read at the third stage.

I'll let you fill in the details.


What is the difference between Big O, Omega, and Theta?

Check the definitions, e.g. in Hildebrand's Introduction to asymptotics. In a nutshell, for the usual computer science use for running times (all relevant functions positive), it is said that:

$f(n) = O(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \le c g(n)$
$f(n) = \Omega(g(n))$ if there are $n_0$ and $c > 0$ so that for all $n \ge n_0$ it is $f(n) \ge c g(n)$
$f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Theta(g(n))$.

Note that the last implies two possibly different $n_0$ values, and different values for $c$ (one each for $O$ and $\Omega$).
Informally, $O(\cdot)$ gives an upper bound, $\Omega(\cdot)$ gives a lower bound, while $\Theta(\cdot)$ gives a sharp bound.
Some examples:
$\begin{align*}
   n
     &= O(2^n) \\
   (3/2)^n
     &= \Omega(n^3) \\
   n^2 (\sin n + \cos n)
     &= \Theta(n^2)
\end{align*}$}
There are functions that don't have a simple expression, like:
$\begin{align*}
   f(n)
     &= \begin{cases}
           n^2 & n \text{ odd} \\
           n^5 & n \text{ even}
        \end{cases}
\end{align*}$
Here clearly $f(n) = \Omega(n^2)$ and $f(n) = O(n^5)$, both best possible among functions $n^\alpha$; there is no simple $g$ so that $f(n) = \Theta(g(n))$.
Lower and upper bounds don't need to be "best possible" in any sense. Often people take great care to get best bounds, but they aren't implied in the notation at all.
To use $\Omega$ to mean best case and $O$ for worst case is misleading at best. For example, the best case for bubblesort on an array of $n$ elements is $\Theta(n)$ (bounded below and above by a linear function in the number of elements; when sorting an already sorted array it does one pass over the data), it's worst case is $\Theta(n^2)$ (if the data are in reverse order). We could say it is $\Omega(n^{1/2})$ and $O(n^3)$ as well, both valid for best and worst cases.


What type of an algorithm is being used for directory structure scanning?

For most file systems, a directory lists its entries in a certain order, so reading ("scanning") an individual directory will return its entries in that order.

But when it comes to scanning whole directory structures, there is no such thing as "core scanning": there isn't a common implementation for that.

I think depth-first is more popular; e.g. GNU find only supports depth-first scanning.  This may be due to depth-first scanning consuming less memory on average; it can't be due to breath-first search being harder to implement, as it's just a matter of treating your list of files to visit as a queue rather than a stack.


What is the worst case time-complexity of removing the root of a Binary Search Tree?

I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward.

For it to then still be a binary tree that node needs to be closest to the root in value.
The worst case will turn out to be that all nodes have two children, and in that case the node closest in value to the root is either the leftmost leaf on the right side or the rightmost leaf on the left side.

So with deletion we're looking at two operations to perform:

finding the element to delete (that's $\mathcal{O}(1)$ when we're deleting the root, as You've correctly pointed out)
finding a replacement for the root (turns out to be $\mathcal{O}(\log n)$ as we'll see...)

To find that replacement you have to traverse a full path from root to leaf, which in a binary tree could be anywhere between length $\log n$ and $n$.
But note that if the path were any longer than $\log n$ nodes, we'd have to have some node with only one child, in which case we can simply move that node up a level and save ourselves any further effort.
(This also kind of shows that the worst case is in fact what I've claimed above since in any other case we could stop earlier.)

Thus at worst we'll have $\mathcal{O}(\log n)$.


Which Data Structure should I use to store words from a novel?

You will probably end up using two nested data structures. I would use a hashmap with the words as keys. The value would be an array/list/set (depending on what you want to do with the occurrence data) containing an item for each occurrence of the word. The item would store whatever you needed (line number, etc). The number of occurrences would just be the size of this array/list/set.


How to partition a tree on a fixed budget of edge cuts?

There is a straightforward dynamic programming algorithm to find the exact answer whose running time is something like $O(nk^2t^2)$, where each partition's total weight is about $t$.  This is far too slow for your parameter settings.

To get an approximation, one trick is to pick a parameter $r$ and divide every weight by $r$ and then round to the nearest integer.  Then, you have a new instance where the weights are much smaller, and you can find an exact solution to this using dynamic programming.  That will then be an approximate solution to the original problem -- not necessarily the optimal answer, due to rounding, but it might get close.

When rounding, you might get some improvement by using randomized rounding.  For example, if the division gives you a number like $2.7$, you flip a biased coin; with probability $0.7$, you round this to the integer $3$, and with probability $0.3$, you round it to the integer $2$.

There may be better solutions, but this is one simple thing you could try.


Spanning tree with chosen leaves NP-Complete proof

The question you link to shows that the problem can be solved in polynomial time.  If the problem was NP-complete, then this would prove that P = NP.  Of course, it's a famous open problem to prove that P = NP or P != NP.  Therefore, you shouldn't expect anyone to know of any such proof.

Also, many computer scientists expect P != NP; if they're right, then the problem you list is not NP-complete.


Show that this language is in NP $\cap$ coNP

Hint: Use the fact that $\ell$ is one-to-one, and so to every $v$ there corresponds a unique $u$ such that $\ell(u) = v$.


In this answer we prove the colored path problem is NP-hard for $c\ge 7$. I don't know whether it is NP-hard for $2\le c\le 6$. Without loss of generality, we prove the NP-hardness for  the Hamiltonian Path problem variant, i.e., asking whether there exists such a colored Hamiltonian path, insteand of the TSP variant.
We use the normal reduction from 3SAT (with $n$ variables and $m$ clauses) to Hamiltonian Path with the following changes:

For each variable, we only have $2m$ nodes: $v_1,v_2,\ldots,v_{2m}$. The $i$th clause corresponds to nodes $v_i,v_{i+1}$ and $v_{2m-i+1},v_{2m-i}$, i.e., if the $i$th clause contains the positive literal of this variable, we have the path $v_i\rightarrow c_i\rightarrow v_{i+1}$, where $c_i$ is the node corresponding to the $i$th clause; and if the $i$th clause contains the negative literal of this variable, we have the path $v_{2m-i+1}\rightarrow c_i\rightarrow v_{2m-i}$. In addition, we add a blank node $b_i$ between $v_i$ and $v_{i+1}$.

For each variable, for each $i$, we give $v_i$ and $v_{2m-i}$, $b_i$ and $b_{2m-i}$ the same color. In addition, we give $c_i, b_i, b_{2m-i}$ the same color if the variable is contained in the $i$th clause.
The following graph is constructed from $(x_1\vee \neg x_2\vee x_3) \wedge(x_2\vee \neg x_3\vee \neg x_4)$. The number above a node represents its color.

We remove the edges to the sink node $t$. Instead, we add paths that pass through the blank nodes that may potentially not be visited due to visits of clause nodes. In the example above, the added edges form the following structure.

In the example above, we ask whether there is a Hamiltonian path with colors 1-2-3-4-5-4-3-2-6-3-7-8-7-3-6-...-11-3-8-14. You can check this reduction indeed works.


Efficient algorithm to compute the diameter of a convex set?

I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:
$$
\max  \sum_i (x^2_i+y^2_i-2x_i y_i) \\
Ax \le b \\
Ay \le b.
$$
Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \frac{1}{2} \sum_i (x_i-y_i)^2 = \frac{1}{2} \sum_i (x_i^2+y_i^2 - 2x_iy_i)$.
The objective function can also be written as $\frac{1}{2} z^T Q z$, where $z=(x,y)$ and:
$$
Q= \begin{bmatrix}
I & -I \\
-I & I
\end{bmatrix}.
$$


Yes, that's correct. Assuming the speed of the cache doesn't change, a cache miss takes a fixed amount of time, and if the number of instructions per time unit increases, then more instructions get delayed because of the cache miss.
Modern processors try different methods to counteract this. Obviously you can use bigger caches which may lead to fewer cache misses. The disadvantage is that with the same technology, a bigger cache will run slower. Another method is organising the cache in such a way that "normal" code doesn't produce unneeded cache misses.
Another method is "streaming", where the cache figures out that you are reading from consecutive memory addresses, and uses this to start loading data before it is needed, reducing the average cost of a cache miss. That is often automatically. There may be instructions that load data from memory without caching it - if you process a gigabyte of data in consecutive memory, then caching any of it is pointless.
Then comes out-of-order execution: You may have one instruction waiting because of a cache miss, but other instructions not affected by this can go on executing. And with hyperthreading the processor executes two or more threads interleaving instructions; if thread A has to wait, then thread B continues at full speed.


Is an intersection between NPC and coNPC always DPC?

NO, it is not always so.

$L_1=\{<0,\varphi>|\varphi\ \mathrm{is\ satisfiable}\}$

$L_2=\{<1,\varphi>|\varphi\ \mathrm{is\ unsatisfiable}\}$

$L_1\cap L_2=\emptyset$

EDIT: As commented below by David Richerby, $L_1=SAT$ and $L_2=UNSAT$ would likewise falsify your claim in the question.


Determining if my artificial neural network needs additional layers

There isn't any hard and fast rule to determine that how much hidden layers would work. In your case, extra layer won't help that much, but extra features can (I'm pretty much sure). Weather forecasting, as far as I know, isn't something which can be determined using only 4 features (considering your input neurons). You can always come up with more and more features, which effectively help in predicting the weather. So, I'd suggest to look for more features (about 10 to 15 useful features), and come up with the following configuration of the network:
1.) Input: Number of neurons in he input layer should be equal to the number of features you calculate for each data entry.
2.) Output: If you can categorize the weather in, say, 5 different categories (sunny, rainy, foggy, stormy, meteor shower), then there can be 5 output neurons.
3.) Hidden: Number of neurons in the hidden layer is normally the mean value of the number of input, and output neurons. You can also have same number of neurons in the input, and hidden layer.


An algorithem for finding the number of primes of the form 4k+3 under some n

Here is a simple algorithm in Python that count the primes of the form $4k+3$ that are less than a positive integer $n$. It uses the standard sieve of Eratosthenes.
import math

def number_of_primes_4kp3(n):
    is_prime = [True] * n

    for p in range(2, int(math.sqrt(n)) + 1):
        if is_prime[p]:
            for j in range(p * p, n, p):
                is_prime[j] = False

    count = 0
    for i in range(3, n, 4):
        if is_prime[i]:
            count += is_prime[i]

    return count

print("n    ", "number of primes 4k+3")
for i in range(1, 9):
    count = number_of_primes_4kp3(10 ** i)
    print("10**" + str(i), count)

It takes about 20 seconds for the Python program above on an old Mac computer of mine to compute number_of_primes_4kp3(10 ** 8), returning 2880950.
When I use Java instead and only compute is_prime for odd numbers (which doubles the performance roughly), it takes less than half a second.


Implementation of caches on CPUs with pipelines

http://caps.cs.binghamton.edu/papers/aggarwal_ics_2005.pdf

I've found this paper which explains in the introduction that with higher associative caches the datapath to read data, compare tags and drive output becomes too long to use with high clock frequencies. Therefore the cache access is split into the 3 stages: decode set, compare tags and read, drive data. It goes further and explains that the access can have an extra stage added to avoid redundent reads of data and only read data after comparing and matching the correct tag, which improves power usage.

Although not really related to my question the paper also explains cache set and way prediction techniques to reduce the latency by parallelising address calculation and the cache read operation, the original paper refers to an article on the alpha 21264 microprocessor on how to implement the prediction.
http://mixteco.utm.mx/~merg/AC/pdfs/alpha_21264.pdf

The technique is to reduce the latency by not waiting on the address calculation stages in the CPU pipeline. This is done by predicting the address of the data to be read and checking at the end of the operation.


Primitive Recursion and course-of-values recursion - examples?

The idea is to use some appropriate coding. A primitive recursive encoding of pairs is an encoding $\mathbb{N}^2 \to \mathbb{N}$, denoted by $\langle x,y \rangle$, such that the following functions are recursive: $e(x,y) = \langle x,y \rangle$, $p_1(\langle x,y \rangle) = x$, $p_2(\langle x,y \rangle) = y$. Coming up with a primitive recursive encoding of pairs is tedious but possible. Using such an encoding you can implement the first type of recursion in your question. The second type uses a more elaborate encoding scheme, which you can figure out on your own.

More explicitly, here is how you would implement a recursion of the first type:
$$
G(x,y) = \langle p_2(y), g(x,p_1(y),p_2(y)) \rangle \\
h(0) = \langle c_1,c_2 \rangle, \quad h(x+1) = G(x,h(x)) \\
f_1(x) = p_1(h(x))
$$
The trick in this case is that instead of computing the function $f_1$ itself, we compute the function $h(x) = \langle f_1(x), f_1(x+1) \rangle$; the value of $h$ at the point $x+1$ only depends on its value at the point $x$.

For the second type, similarly we compute the function $k(x) = [f_2(0),\ldots,f_2(x)]$ instead of $f_2$ itself; the value of $k$ at the point $x+1$ only depends on its value at the point $x$.


Interview Question with Arrays and Consecutive Subintervals

Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$.

The trick is done using a monotonic double-ended queue, one where all the elements are either in descending or ascending order. Furthermore, for each element we keep track of the index we encountered it, so we can invalidate it from the queue.

Suppose that we iterate over elements in a stream, and wish to maintain the minimum value (the maximum is analogous). Let's call the current value $x$ and the current index $i$. We first initialize an empty double-ended queue $Q$ and start iterating:

Remove all elements from the queue that would be made irrelevant by $x$. Since we know our queue is in ascending order, this is very simple, we keep
removing elements from the back that are bigger than $x$. They are now irrelevant for the window, as $x$ is newer and smaller.

while not empty(Q) and peek_back(Q).value > x:
    pop_back(Q)

Add $x$ to the back of the queue, but keep track of its index as well.

push_back(Q, value=x, index=i)

Invalidate old items in the queue. We only have to do this if the item is in the front of the queue, otherwise its harmless (this lazy removal is what allows us to keep $O(1)$ time).

while peek_front(Q).index <= i - window_size:
    pop_front(Q)

Now peek_front(Q) contains the smallest element in our window, so we can use it and then keep iterating.

Note that steps #2 and #4 are $O(1)$ time, and steps #1 and #3 are $O(r)$ time where $r$ is the number of removed elements from the queue. However since each element is only added once to the queue, the $O(r)$ steps must be amortized $O(1)$.


Finding number of edges with weight less than k on the path between two nodes in a tree

You can answer each query in time $O(\log^3 n)$, plus whatever time is needed to answer a lowest-common-ancestor query (a tricky $O(1)$-time solution exists, but you might as well go with the easier $O(\log n)$-time solution, since it doesn't hurt the final time complexity), after doing $O(n\log^3 n)$ preprocessing.

We only need counts from each vertex to the root

Let's call the number of edges of weight less than $k$ on the path from a vertex $v$ to the root $f(v, k)$.  We can calculate the desired final answer -- the number of edges of weight less than $k$ on the path from $a$ to $b$ -- using $f(a, k) + f(b, k) - 2f(lca(a, b), k)$, where $lca(u, v)$ is a the lowest common ancestor of $u$ and $v$.

From now on we will focus on answering the simpler question of computing $f(v, k)$.

Heavy-light decomposition

The heavy-light decomposition decomposes the tree into disjoint paths in such a way that at most $O(\log n)$ such "heavy paths" are visited on the path from any vertex to the root.  This can be accomplished with a DFS in $O(n)$ time.  The idea here is that, since the heavy paths are disjoint, if we have a way to quickly compute the number of edges of weight less than any given $k$ for each one, then we can nearly compute $f(v, k)$ for any $v$ and $k$ just by summing these counts over all heavy paths that we visit on the way from $v$ to the root.  And we do have a way to do this counting: Simply by sorting the edges within each heavy path by weight in a preprocessing step, we can later binary-search for any $k$ to count the number of edges of weight less than $k$ in this particular heavy path in $O(\log n)$ time.

But why only "nearly"?  Because we have so far ignored the possibility that $v$ might not begin exactly at the bottom of a heavy path -- it could begin part-way up.  We could try to "patch things up" by walking down to the bottom of the heavy path containing $v$, subtracting 1 from the count for each edge of weight less than $k$ that we see -- but this won't be worst-case efficient, since an individual heavy path can be as long as $n-1$ edges.  We need a way to handle this bottommost heavy path efficiently.

As noted by commenter xskxzr, the issue of beginning part-way up a heavy path is not only confined to the bottommost vertex $v$ in a path to the root -- it can also happen in the middle of such a path, such as in the path from 11 to 0 in the figure on the linked page.  Fortunately, the same trick, described next, works for both cases.

Fenwick trees of sorted lists

The subproblem we are now focussed on is: Given the ordered list of edge weights $x_1, \dots, x_m$ encountered while traversing down a particular heavy path, we want to preprocess this list to enable us to be able to later efficiently answer queries of the form "How many of the first $r$ elements are less than $k$?", with both $r$ and $k$ part of the query.  One way is to use a Fenwick tree which has as its elements not individual integers, but sorted lists of integers.

A "regular" Fenwick tree with single-integer elements takes $O(n)$ space.  Since each $x_i$ belongs to at most $O(\log n)$ buckets, increasing the size of the Fenwick tree's elements from single integers to sorted lists of integers fortunately only increases space usage by a $\log n$ factor.  The associative operation in a "regular" Fenwick tree is usually addition; in our Fenwick tree it's "set union".  For efficiency, all lists should be populated in a first pass, and then only sorted once, in a second pass.  This can be done in $O(n\log^2 n)$ time for a single heavy path, so $O(n\log^3 n)$ overall.

To process an $(r, k)$-query for a particular heavy path, a subquery in that heavy path's Fenwick tree is performed on each of the sequence of buckets found by stripping least-significant 1-bits from $r$, and the counts from these subqueries are summed.  That much is standard for Fenwick trees, but the individual subqueries are more complicated: Instead of just reading out the integer value from each bucket, we must binary-search the sorted list in that bucket for $k$; the leftmost position where $k$ appears (or would appear) tells us the number of edges of weight less than $k$ in that bucket.

An example might help: Suppose $r = 43$.  In binary, 43 is 101011 (32 + 8 + 2 + 1).  To answer a query for $r = 43$ (and some $k$ value), we would binary-search for $k$ in the following 4 buckets: 101011, 101010, 101000, 100000.  Each bucket is found by stripping the least-significant 1-bit from the previous bucket, so there cannot be more than $\log n$ subqueries.  Each subquery is a binary search, so cannot take longer than $O(\log n)$ time.  Finally, there are at most $O(\log n)$ heavy paths encountered on the path from any vertex to the root, so the worst-case time to compute $f(v, k)$ is $O(\log^3 n)$.


Is the problem of deciding whether two programs have the same semantics decidable?

Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are limits to what we can do, if we allow the language in which these properties are defined to be rich enough, so the answer to your question, in the general case, would have to be negative.

More specifically though, behind every specific metamorphic process that can be automated there is also a specific strategy, so there are also limits to the efficacy of those malware pieces. Because of that, it may be possible, given some knowledge of this strategy, to target its syntactical features in a controlled way, and automatically crack the code behind it, preventing it from attacking.

Malware creators have the initiative though, which gives them an advantage. This advantage can be amplified with technical skill and mathematical sophistication, so it's not advisable to base your security strategy on the ability to detect and deactivate a piece of software that already entered your system.


What type of operations are seen the most at the physical disk level — reads or writes? Why?

The proportion of reads to writes would be workload and system dependent. Before filtering by caching, reads will typically be more common, if for no other reason than code being read-only and data writes being dependent on at least an equal proportion of reads.

Under paging, discarding a clean (stored) page reduces the number of storage accesses, so there is an incentive for the OS to prefer paging out such pages. This biases toward reads (paging-in) at the storage level. (Obviously, allowing dirty pages to accumulate endangers responsiveness since eventually the best page to replace would be dirty so that demand for a not present page would be delayed by the required writeback. Maintaining a modest free list would ameliorate this issue.)

For an in-memory database (with persistence) or a log (or backup) server, writes would presumably dominate. In the former case reads are satisfied by memory by design; in the latter case reads are simply less common.

For many tasks oriented toward content consumption such as webserving and gaming where writes are much less common, storage reads can easily dominate even with caching.

Prefetching can also increase the number of read requests. If the cost of a read miss is high and the cost of an unused read is moderate, even somewhat aggressive prefetching can be beneficial.

The relative costs of reads and writes can also be a factor that can bias OS policies with respect to caching/prefetching. SSDs generally provide much higher read bandwidth than write bandwidth and do not penalize random accesses, reducing the cost of prefetching under low memory utilization.

Overprovisioning memory (in terms of cost per unit of work) can reduce the frequency of storage reads (moving toward the in-memory database model) and may be a reasonable design choice due to an impracticality of sharing memory across more work (and the non-linear cost per bit), a preference for responsiveness over average throughput, or a desire for load tolerance (i.e., the extra memory may not be worthwhile for average throughput or responsiveness but may avoid issues under high load).

Persistent (battery-backed or inherently persistent) memory can greatly reduce the number of writes to actual storage.

RAID will generally amplify the number of writes but not the number of reads seen by disks (RAID systems typically rely on the disks' internal error detection to detect read errors but write to more than one disk on a write).


A JIT (Just-In-Time) compiler compiles code at run-time, i.e. as the program is running. Therefore the cost of compilation is part of the execution time of the program, and so should be minimized.

The opposite of this is an ahead-of-time (AOT) compiler which is basically synonymous with "batch compiler". This converts the source code to machine code and then just the machine code is distributed. Therefore, the compiler can be very slow as it doesn't impact the execution time of the resulting program.

Nowadays, when people say "compiler" they typically mean an AOT compiler. Indeed, the term "AOT compiler" only really started becoming popular relatively recently when people started making AOT compilers for JIT compiled languages, particularly JavaScript. Many of these languages, e.g. C#, compile to an intermediate language for a VM which is then JIT compiled to machine code at run-time. The term "AOT compiler" has the connotation that the source code will be compiled directly to machine code, so no form of JIT compilation is required at run-time.

"Batch compiler" is a bit of an archaic term at this point.  The real contrast to a batch compiler when the term was popular was an incremental compiler.  Incremental compilation is often associated with languages like Lisp where you had a REPL and you could interactively request the language implementation to compile a specific function. If a function was executed whose compilation had not been requested before, it would typically be interpreted. A batch compiler, by contrast, compiled all functions at once, i.e. in a batch.


Selecting random element from complement of set

Yes actually, and it's quite simple.

Sample a random integer $q$ from $[n-k]$.
Initialize $c = |\{x \in S \mid x \leq q\}|$.
While $c > 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$.
Return $q$.

This works because steps 2 and 3 forms a bijective mapping from $[n -k]$ to $[n] \setminus S$. Finally the algorithm runs in $O(k)$ because it's possible to check if $q \notin S$ in $O(1)$ time either by using a $O(n)$ memory bitset or a hash table and both steps $2$ and $3$ take at most $k$ steps.


Linear-time algorithm for solving a set of inequalites

for this algorithm it's enough to check sum of two smallest element is bigger than the maximum element.

We find Min1, Min2, Max.

if Min1 + Min2 < Max there is no. O(n)
else all of them is true.


Interview Question: Insert switch to maximize time lightbulb spends on

Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:

Note1 If a[i+1] = a[i] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.

Note2 The optimal value we add between $a[i]$ and $a[i + 1]$  for some $i$ is either equal to $a[i] + 1$ or to $a[i+1] - 1$.
Proof. Assuming the claim is not true, there is an optimal value strictly between $a[i]+1$ and $a[i+1]-1$. However, if the bulb is turned off in this interval we can push it back to $a[i]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a[i+1]-1$ increasing the length of turned on pulp in this interval.

So now we can loop over the array, and for each $i$, if $a[i] \neq a[i+1]-1$, we try to add the value $a[i]+1$ and the value $a[i+1]-1$, these are 2*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
 1. The length of light-on since the begin.
 2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a[i]$ and $a[i+1]$ with time stamp $k \in (a[i], a[i+1])$, the total value of on-light will be total value of on light from the begin to $i$ + the total off-light from $a[i+1]$ till the end + the total on-light in the interval between $a[i]$ and a[i+1] after adding $k$ (Which is either $k - a[i]$ or $a[i+1] - k$ depending on the original status of the interval).
Summary, In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$


From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:

  Read the list in chunks of $k$, convert them to strings, and sum the chunks.

Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. Adding the chunks takes time $\Theta(k+2k+\cdots+n) = \Theta(k(1+2+\cdots+n/k)) = \Theta(k(n/k)^2) = \Theta(n^2/k)$. In total, we get a complexity of $\Theta(n(k+n/k))$. The optimal choice of $k$ is $\sqrt{n}$, and this gives a complexity of $\Theta(n^{3/2})$. In contrast, the trivial algorithm has $k = 1$ and so complexity $\Theta(n^2)$.

More generally, you can consider $d$ levels of recursion. Let $f_d(n)$ denote the optimal complexity of such a scheme, measuring just the merging steps. Clearly $f_1(n) \approx n^2/2$. Given an algorithm with $d$ levels, we can construct a $d+1$-level algorithm which cuts the input into chunks of length $k$, runs the $d$-level algorithm on each of them, and concatenates the result. This takes time roughly $(n/k)f_d(k) + n^2/2k$. For example,
$$
\begin{align*}
2f_2(n) &\approx \max_k nk + n^2/k \approx 2n^{3/2} & (k=\sqrt{n}), \\
2f_3(n) &\approx \max_k 2nk^{1/2} + n^2/k \approx 3n^{4/3} & (k=n^{2/3}), \\
2f_4(n) &\approx \max_k 3nk^{1/3} + n^2/k \approx 4n^{5/4} & (k=n^{3/4}).
\end{align*}
$$
We get that $2f_d(n) \approx dn^{(d+1)/d}$. Calculus shows that the best choice of $d$ is $d = \log n$, in which case we obtain $2f_{\log n}(n) = \Theta(n\log n)$. However, this scheme is not necessarily achievable.

If we choose a branching factor of 2 then we get an algorithm whose running time is $\Theta(n\log n)$ which resembles merge sort. In fact, the sorting lower bound gives a lower bound of $\Omega(n\log n)$ on any such merging procedure.

We can also prove the lower bound directly. For a sequence $\sigma_1,\ldots,\sigma_m$ of chunk lengths summing to $n$, define its potential by
$$
\Phi(\vec\sigma) = nH(X_{\vec\sigma}), \text{ where } \Pr[X_{\vec\sigma} = i] = \frac{\sigma_i}{n}.
$$
Here $H$ is the entropy function.

The potential function starts at $\Phi(1,\ldots,1) = n\log n$ and ends up at $\Phi(n) = 0$. Suppose that $\vec\tau$ is obtained from $\vec\sigma$ by merging $\sigma_i$ and $\sigma_j$ to a new chunk $\tau_k$. We can sample $X_{\vec\sigma}$ by first sampling $X_{\vec\tau}$, and if the result is $k$, sample according to the marginal distributions $\frac{\sigma_i}{\sigma_i+\sigma_j},\frac{\sigma_j}{\sigma_i+\sigma_j}$. Calculation shows that
$$
\begin{align*}
\Phi(\vec\sigma) = nH(\vec\sigma) &= nH(\vec\tau) + n\Pr[X_{\vec\tau}=k] h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + (\sigma_i+\sigma_j) h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + O(\sigma_i+\sigma_j).
\end{align*}
$$
Here $h$ is the binary entropy function.

This shows that the potential difference is a lower bound on the running time. Since the overall potential difference is $n\log n$, we obtain a lower bound of $\Omega(n\log n)$. Furthermore, the calculation shows that it's best to always merge chunks of identical size.


Advances in recent time in Von-neumann self replication idea

For those who don't know, I am the world's only producer of a von Neumann 29-state self-replicating cellular automaton.
Indeed, respecting vNCA, I am the world's expert.  Ask Sayama (U Binghamton), Reggia(U of Maryland), or Adamatzky (U of South of England).
While DW may be a moderator, he does not know anything about von Neumann's cellular automata, I dare say he has not designed such self-replicators, and he certainly had not designed a machine zygote.  For my design of a machine zygote, see here:
https://www.researchgate.net/publication/235432119_Computational_Ontogeny
One more thing, it is 29 states, not 28.


What is the time complexity of subset testing?

Since you talk about sets I assume that there are no duplicates.

You can  assume $n \le m$ otherwise you can answer "no" in time $O(1)$.
You can further assume $\max_{a \in A} a \le \max_{b \in B} b$, otherwise the answer is again "no", and can be found in time $O(\min\{m, U\})$, where $U = \max_{a \in A} a$.

Your problem can be solved in $O(\min\{m \log n, U\})$ worst-case time. To do so use the best of the following two strategies:

Sort $A$. Keep a counter $x$ of how many elements from $B$ have been found in $A$. Initially $x=0$. For each element of $b \in B$ (in arbitrary order), determine whether $b \in A$ using a binary search. If $b \in A$ increment $x$. After all elements of $B$ have been examined, return true if and only if $x=n$.
Keep an array $X[0, \dots, U]$ of $U+1$ boolean elements. Initially all the elements of $X$ are false. For each element $b \in B$, check if $b \le U$ and if that is the case set $X[b]$ to true. Iterate over the elements $a \in A$ and check whether $X[a]$ is true for all of them. If this is the case return true, otherwise return false.

Notice that $\Omega(m \log n)$ is a lower bound on the worst-case time complexity needed to solve your problem (as a function of $m$ and $n$) in the algebraic computation tree model. See Corollary 3 on page 147 (155 of the pdf file) here.

You can also solve your problem in $O(m)$ expected time by using a hashset $H$:

Insert all the elements of $B$ into $H$. This takes $O(1)$ expected time per insert operation, i.e., $O(m)$ time in total.
For each element $a \in A$, check whether $a \in H$. This takes $O(1)$ expected time per check.


What goes wrong with sums of Landau terms?

What you are doing is a very convenient abuse of notation.

Some pedants will say that what you write is nonsense, as $\mathcal{O}(f)$ denotes a set and you cannot do arithmetic operations on them the way you are doing.

But it is a good idea to ignore those pedants and assume that $\mathcal{O}(f)$ stands for some member of the set.
So when we say $f(n) = g(n) + \mathcal{O}(n)$, what we really mean if that $f(n) - g(n) \in \mathcal{O}(n)$.
(Note: some pedants might shudder at this statement too, claiming that $f(n)$ is a number and $f$ is the function!)

This makes it very convenient to write expressions like

$$ n \le \sum_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$$

What this means is that there is some $f \in \mathcal{O}(n^{1/3})$ such that

$$ n \le \sum_{k=1}^n k^{1/k} \le n + f(n)$$

In your case of

$$\sum_{k=1}^{n} \frac{1}{k} = \sum_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$$

you are abusing it even further and you need to be careful.

There are two possible interpretations here: Does the $\mathcal{O}(1)$ refer to a function of $n$, or a function of $k$?

I believe the right interpretation is to interpret it as a function of $k$.

If you try thinking of it as a function of $n$, thought not incorrect, it might lead to potential fallacies, like thinking $k$ is $\mathcal{O}(1)$ and trying to write $\sum_{k=1}^{n} k  = \sum_{k=1}^{n} \mathcal{O}(1)$

If you try thinking of it as a function of $k$, then it is true that, if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) and $g$ is never $0$,  that

$$ S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(k)) =  \mathcal{O}(\sum_{k=1}^{n} |g(k)|)$$

Note that in the middle, we have used the convenient abuse of notation $\mathcal{O}(g(k))$ to mean that for some function $h \in \mathcal{O}(g)$ the sum is $\sum_{k=1}^{n} h(k)$. Note that the final function inside the $\mathcal{O}$ refers to a function of $n$. The proof is not that difficult, but you have to cater to the fact that you are dealing with an asymptotic upper bound (i.e. for sufficiently large arguments), but the sum starts right at $1$.

If you try thinking of it as a function of $n$, then it is also true that if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) then

$$ S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$$

So your proof is essentially correct, in either interpretation.