Why some rules in Elementary Cellular Automata halt and others don't?

Your problem is formalized in research as follows: given a CA, is it "Turing complete"? This has been proved for a limited set of CAs including rule 110 in the early 2000s by Cook in a notable proof. it was probably first proved for a CA for the game of life by Conway in the 1970s. There are empirical ways of analyzing CAs that can rule out Turing completeness, and "signs/ circumstantial evidence" that a CA might be Turing complete, but no CA can be proved Turing complete or not from a finite number of example cases.

TMs can execute an arbitrary number of steps and then halt, so that is a characteristic required of the CA simulation. But there is no standard way of defining whether a CA "halts" and thats up to the universality mapping. There is currently no general theory of CA←→TM mappings. There are different mappings in the literature and Cooks mapping is also called "weakly Turing complete" because it requires infinitely recurring patterns specified on the CA input.

There is no general way to find whether particular CAs and rules are universal. This is essentially equivalent to the halting problem in general.

Unfortunately Wikipedia does not highlight Turing completeness in CAs. Here are two useful alternative references.

Universal Cellular Automaton / Wolfram Mathworld by Weisstein
Universality in Elementary Cellular Automata / Cook


largest subset of pairwise intersecting intervals

First, suppose the intervals $[l_1,r_1],\ldots,[l_n,r_n]$ are pairwise intersecting, then we have $l_i\le r_j$ for any $i,j$, which means for any $i$,  $l_i\le\max_k l_k\le r_k$, i.e. all these intervals contain the point $\max_k l_k$.

The observation above leads to the algorithm mentioned in jaxa 9831's answer:

  First, sort the intervals according to their left endpoints. Then at each left endpoint, check how many intervals cross that point. Finally, report the optimal one.

To efficiently find the point that maximum intervals cross, we can use an algorithm mentioned in GeeksforGeeks. Roughly speaking, we first sort all endpoints, and maintain a counter initialized with 0. We then travel these endpoints from left to right. Each time we come across a left endpoint, we increase the counter by 1, while each time we come across a right endpoint, we decrease the counter by 1. The maximum value of the counter represents the maximum number of pairwise intersecting intervals.


How shall I understand the undesirable consequences of dynamic scoping?

I think you're right that that example is a bit confused. I believe the fix is the following, if I got my parantheses right.

e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)

should instead be

e' = (λ (f : num → num) (λ (x : str) f) ("zero"))(e)(7)

If we evaluate e first we'll get:

(λ (x : num) λ (y : num) x + y)(42).

x = 42
(λ (y : num) x + y).

We've finished evaluating e, since we got to a lambda. But evaluating it in the above expression will cause the bad addition "zero" + 42, since, regardless of what we do with the environment, the x="zero" binding will be the closest. The immediate reduction of the above gives:


Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10

The goal of a recurrence relation is to make a complicated problem easier to think about, which is very general. It allows us to express a function in terms of itself, but still reason about what the value of the function for an input is.

Sometimes you care about the exact value of the function, in which case you'd prefer to rewrite it in an exactly equivalent way (or just plug in a number and follow the recursion chain until you have your answer).

Other times, you're just worried about the extreme "if my worst enemy plugged a value into this function, what would it do?" case.

Rewriting the equation as an inequality let's us remove an entire recursive call of the function, which makes doing substitutions to figure out an easier to reason about form of the function a more achievable goal.

So yes, $T(N) = T(N-1) + T(N-2) + 10$, may exactly describe the run time of your program, or the amount of money in my bank account after $N$ days (I wish), but we don't care about that precision, because $T(N) < 2T(N-1) + 10$ is an upperbound, and we just want to know that our program will finish before the heat death of the universe, or that I have enough money in my bank account for dinner.

Note the benefit here. Perhaps because your algorithm had a recursive nature to it, it might have been really easy to come up with the $T(N) = T(N-1) + T(N-2) + 10$ description of the run time. Easy to come up with, but hard to think about what the function actually means. So now that we have this building block, we come up with an upper bound (that we know is true), but has less recursion (which our brains don't like). This is nice on its own, but it also let's us continue to expand the recursive definition until we understand the underlying pattern, and can remove the recursion completely.


Course teaching time complexities in real life systems

I don't think these things are usually treated as a single topic in either research or education, but there are quite a few adjacent topics that are relevant. I'll list some here, starting with...
I/O-complexity
One perspective on the algorithmic analysis of computer storage, memory and caches is the field of I/O-complexity or external memory algorithms. These lecture notes from a course by Mark de Berg are a good introduction (in Part II). Note that this perspective assumes an abstract I/O model that has a two layer memory hierarchy (a small and fast internal memory and a big but slow external memory), which of course is a simplified version of what a modern computer has. Still, this perspective makes it possible to design efficient algorithms for dealing with massive data (think running an algorithm on an array/matrix a few ten GB big, or more!).
Another advantage of treating "external memory" only in the abstract means that we only need to design one algorithm to deal with both SSD's, hard-disks, or even a slow internet connection, as long as we are satisfied with treating our external memory as a monolithic blob. There are many other tricks you may want to try in practice, but this is highly dependent on your specific machine or operating system.
Operating Systems
Okay, but what if I really want to know how to use multiple cache layers, how to ensure seeking goes efficiently on my hard-disk, or how to play nice with my OS's paging? These topics (among others) are usually treated in a course called "Operating systems". Another aspect that frequently is the focus of such a course is concurrency (e.g. how does your OS manage to run all those processes "at the same time"? ), and dealing with multiple processes and threads programmatically. Some mild form of parallelism may also be covered.
Parallelism
So, what about those 100s of computing cores? Making use of those things to compute efficiently is known as parallelism and courses with that word in their title are common. There are quite a few models there to use in the analysis of parallel algorithms, the PRAM model is common. Again, this is an abstract model that may or may not allow you to use the full power of your expensive GPU (or arrays of relative cost-efficient Sony Playstation 3 cores. Cryptanalystist are a rare breed of "mostly theoretical" computer scientists that actually have use of massive computation power, see these slides of Dan Bernstein on some thoughts of using GPU's for crypto).
However, unless you have a very extreme needs for high performance computing, "using GPUs" in practice usually means using one of the APIs/frameworks designed to use them, like OpenGL. There are courses called computer graphics or something similar that teach how to work with these APIs.
Speaking of high performance computing, this is a field of its own, a bit on the intersection of parallel and distributed computing. (see also this answer for the difference between distributed computing, concurrency, and parallelism)
I should also mention that there are also courses on databases that go beyond just teaching how to use them and also teach how all those operations are implemented efficiently.
But nobody will teach you this one simple trick!
We've already covered quite some courses, certainly enough to fill a few semesters, but you may have already gathered from the multiple caveats above that there's always a manner of tricks that simply depend too much on the specifics of your setup that there's no good reason to teach it, or do theoretical research on. Still, having the knowledge of the courses above at least should give you a good idea on when it might be a good idea to depend on some strange trick, or whether there actually is a well-understood way to solve your problem. One interesting trick is to compress everything and make it fit in main memory. (see also the video explaining how their entire system works)


Average depth of a Binary Search Tree and AVL Tree

Your question refers to average depth of the nodes in a BST, but it's easiest answer this by thinking about the overall height of the tree first. In the worst case, the depth of the tree can be $n$, assuming it's not a balanced tree and the inputs are sorted, so the resultant tree ends up being a very deep linked list. In that case, the average depth of nodes in the tree can be $\frac{n}{2}$. But assuming the tree is balanced, or the input is randomized, the expected depth will be $O(\log n)$ because the number of nodes present at each depth in the tree grows exponentially with the depth of the tree. ($2^0$ nodes at depth 0, and $2^1$ nodes at depth 1, etc). This is of course, subject to the constraint that the count of all nodes is equal to $n$, so the height of the tree will be $O(\log n)$.

The average depth of all the nodes in the tree will of course grow as the depth of the tree increases, and since the number of nodes present at a particular depth increases exponentially with the depth, the larger the tree is, the denser the deeper layers of the tree will be, and the more the deeper layers will dominate the average. So the average depth of nodes in the tree will approach the height of the tree, which we know to be $O(\log n)$. So the average depth of nodes in the tree is also $O(\log n)$.

Your professor mentioned that AVL trees will always have an average depth of $O(\log n)$. This is because AVL trees are balanced, so everything mentioned above always applies to AVL trees. They cannot end up being linear.

This is just an intuitive argument, not a proof. If you need a proof, see CLRS (Cormen Leiserson Rivest Stein) Introduction to Algorithms Third Edition pg 300. They have 3 pages of algebra as a proof.


Why MIT lecture breadth-first search algorithm is so complicated?

I think this is best handled by contacting the lecturer, but here are four reasons.

A Kain0_0 remarks, your solution is recursive, while his isn't.

Didactic considerations behind this might be:

Recursion is hard for some students. Perhaps it hasn't been taught at this point in the course, or is considered an unnecessary burden.
Most BFS implementations in practice do not use recursion. Programmers need to spot algorithms in other peoples' code all the time. There is value in presenting algorithms in their most common form.

Furthermore,

You're sweeping some stuff under the carpet. He makes his data structures explicit, because he wants to show how much time and space his algorithm uses. You don't: you leave the recursive call stack implicit, and you don't show how .children and .index are represented or created.
He's doing more. He can report the level at which the node was found. You don't keep that information.


Unification --- removing equations and updating the solution

If all you have is the solution to these equations (the most general unifier for $D$), I don't know of any good algorithm for your problem that will be better than "compute the answer from scratch" in general.

However, if you are willing to save some extra information on the side while you are solving $D$, then yes there are methods to do what you want -- with some caveats.  In particular, you can use a persistent union-find data structure to help.  Normally, we'd use union-find for unification (to compute the solution, i.e., the most general unifier).  Here the idea is to instead use a persistent union-find data structure.  This provides the ability to "roll back" some of the union operations and then go forward from there.

See the following research paper:

A persistent union-find data structure.  Sylvain Conchon, Jean-Christophe Filliâtre.  ACM SIGPLAN Workshop on ML, 2007.  See also https://www.lri.fr/~filliatr/puf/ .

Caveats: Their data structure is only semi-persistent, i.e., only partially persistent.  This means you can roll back to an earlier version of the data structure and make modifications from there, but you can't do any more than that.

One consequence is that the efficiency of the above approach will depend upon the order in which you process the equations.  If you want to remove a few equations that were processed near the end and then compute the new solution, this will be very efficient (with the above data structure).  But if you want to remove an equation that was processed near the beginning and then compute the new solution, this will be relatively slow.  In other words, suppose your equations are $D=\{D_1,\dots,D_n\}$ and you compute the solution (most general unifier) by processing the equations in the order $D_1,D_2,\dots,D_n$ (to process an equation you call the Union operation on the union-find data structure).  Now suppose you want to remove equation $D_i$.  With the above partially persistent union-find data structure, you can do this by rolling back the state of the union-find data structure to its state after processing $D_1,\dots,D_{i-1}$, then processing equations $D_{i+1},\dots,D_n$ starting from there.  If $i$ is close to $n$, this will be efficient (it will take $n-i$ Union operations), but if $i$ is small, it won't be much better than just starting from scratch.

In principle if we had a confluently persistent union-find data structure we could remove this limitation.  However, I don't personally know of any efficient confluently persistent union-find data structure.  I'm not sure whether such a thing has been studied in the literature or not; this answer seems to suggest it was an open problem, at least as of 2010.  (Here is a survey on confluent persistence.)


Simple Representation of Matrices with the Given Equivalence Relationship

When you are dealing with binary matrices, this is the problem of graph canonization.  There is no known polynomial-time algorithm for this problem, and determining whether it can be done in polynomial time is a famous open problem, but there are techniques that are often reasonably efficient in practice (e.g., Nauty).  (The relationship is that every graph corresponds to a binary matrix, namely, it adjacency matrix, and versa.)

When you have non-binary matrices, you can think of this as a graph with labels on the edges.  There are standard techniques for reducing this to the standard graph canonization problem, by converting each labelled edge to a small subgraph.  See, e.g., Graph isomorphism problem for labeled graphs, On graph isomorphism for weighted graphs, What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?.


How to compute linear recurrence using matrix with fraction coefficients?

Your matrix formulation doesn't work- you need to use different $n$s in the matrices.

One idea to rescue your original approach is as follows. First, factor $10^{14} + 7 = 98794607 \times 1012201$ (only the second factor is prime). It is enough to compute $M_n$ modulo the two factors. The first factor is smaller than $2^{32}$, so you can store the first $10000$ Motzkin numbers modulo it using only 40KB. The second factor is prime and larger than $10003$, so you can use modular division, in which you multiply with the inverse (see here for how to calculate the inverse). This only works since $n+3$ will actually have an inverse, and that's why we factored $10^{14} + 7$.


As far as I know, I think it is possible to build a functional implementation of solve that does behave as a deterministic function, with no side effects.  Yes, there might be multiple possible outputs that are all valid.  However, I think it's possible to pick an implementation where it always outputs the same answer.  (Certainly, the existence of multiple possible outputs doesn't on its own render it impossible to build such an implementation.)

Here is a simpler example, to give you some intuition.  Suppose we want to find a solution to $|x|=c$, where $c$ is a constant given in advance.  Then there are two solutions ($x=+c$ and $x=-c$).  Nonetheless, you can still build a functional program to output a solution to this, i.e., on input $c$, the code returns a solution to $|x|=c$.  An example implementation is the identity function (always return whatever the input was).  This is functional and has no side effects.

So just because there are multiple valid outputs doesn't require the code to randomly or nondeterministically choose among them.  Often you can write code that outputs one of them, and is consistent and deterministic about which one it outputs.

For instance, here is a plausible such implementation for your particular problem:

Solve the linear system "minimize $x_1$ such that $Ax=b$" using linear programming.  (Here I write $x_1$ for the first variable of $x$, i.e., I am assuming $x=(x_1,\dots,x_n)$.)  (If it has no solution, return "No solution".)  Let $u^{(1)}$ denote the resulting such solution.
Solve the linear system "minimize $x_2$ such that $Ax=b$ and $x_1 = u^{(1)}_1$" using linear programming.  Let $u^{(2)}$ denote the resulting such solution.
Solve the linear system "minimize $x_3$ such that $Ax=b$ and $x_1 = u^{(1)}_1$ and $x_2 = u^{(2)}_2$" using linear programming.  Let $u^{(3)}$ denote the resulting such solution.
Repeat, until you have obtained $u^{(n)}$, where $n$ is the number of variables.  Return $u^{(n)}$.

Note that this algorithm returns the lexicographically least solution to $Ax=b$.  Because linear programming is in P, I believe each "solve the linear system" step can be implemented with a deterministic, functional algorithm.


If you have at least one abstraction just go on $\beta$-reducing. It just works like taking an input $x$ and computing $f(x)$.

$$ (\lambda x. x + 1)1$$
is an application.

$$ [1/x](x + 1)$$
$$ (1+1) \rightarrow_\beta 2$$


Writing a multitasking operating system for a processor without MMU

It's actually not that hard to design an operating system that doesn't require an MMU. There are a few conveniences you'll have to do without, but nothing insurmountable.

Since different tasks will have to be loaded at different addresses, all your code (except for the kernel, the standard library, and any other code that's part of your base runtime environment) has to be compiled as position-independent. This means relative jumps and a base address for heap access stored in a register. Spending one register as a base address might seem costly if you're used to x86-32's four general registers, but most modern architectures have more, and even 8088 has the segment registers precisely for that.
A Unix-like architecture has to be revised, because you can't implement fork. That's ok, most operating systems don't have fork. (You can have vfork.)
You can't preallocate large gobs of space without also allocating the corresponding memory. This means no growing of the stack or heap on the fly by allocating one more page at a time.

If you have an MPU, then your tasks can still be separated from each other as usual in multitasking operating systems. Without an MPU, memory separation can only be cooperative if you allow tasks to execute arbitrary code. One way to achieve memory separation without an MPU is to restrict tasks to use only verified code on a virtual machine and implement memory protection in software as part of the VM engine.

uClinux is a project based on the Linux kernel that runs on processors (including ARM Cortex-M) without an MMU. Its restrictions on multitasking are essentially what I outlined above.


Difference between Computing Architecture and Platform in Computer Science

Architecture generally refers to a design-level structure or organization for an entire system.

Platform generally refers to something (an operating system, a library, a programming language, a programming environment) which you can build other things on.


How to prove the NP-completeness of 15-Partition Problem

I think this could work.

We multyply all the numbers by fifteen and we also multiply $B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers of size one for each bucket to the input.

As twelve is less than fifteen, we have to use exactly twelve of them to fill each bucket, then we have to use other three numbers to fill each bucket. As random_hacker says in the comment, if we use more than twelve numbers in a bucket, we will not be able to cover the gaps in another bucket and so that bucket won´t be able to reach the quantity it should reach.

We see that if the big numbers fill the buckets in 15-partition, they also fill the buckets in 3-partition. Also, if we put four or more big numbers in a bucket, we will have more than fifteen numbers in that bucket


I'm not aware of any general methods, and personally I'm not interested in tricks which are only useful in exams. However, I can explain how to find an expression for your particular example. The way to get better with this kind of exercise is to solve a few of them.

A word which contains exactly one $aa$ has the form $xaay$, where $x,y$ contain no $aa$, $x$ doesn't end with $a$, and $y$ doesn't start with $a$. This suggests first determining how to write a regular expression for the set of words avoiding $aa$.

If a word avoids $aa$, then any two occurrences of $a$ are separated by $b^+$.  We can describe all such words by the following infinite regular expression: $$b^* + b^*ab^* + b^*ab^+ab^* + b^*ab^+ab^+ab^* + \cdots.$$
This can be represented by the finite regular expression $b^* + b^*(ab^+)^*ab^*$.

For the sake of our original problem, we need to impose the further constraint that the word not end with $a$. We obtain the following infinite regular expression for the set of all words avoiding $aa$ and not ending with $a$:
$$
b^* + b^*ab^+ + b^*ab^+ab^+ + \cdots = b^*(ab^+)^*.
$$
Similarly, a regular expression for the set of all words avoiding $aa$ and not starting with $a$ is $(b^+a)^*b^*$.

Putting everything together, a regular expression for the set of all words containing exactly one copy of $aa$ is
$$
b^*(ab^+)^*aa(b^+a)^*b^*.
$$


Why do the swap step in Prim's algorithm for minimum spanning trees?

Charles Leiserson is presenting a proof to what is known as the blue rule in Tarjan's "Data Structures and Network Analysis" book.

The proof goes by contradiction, that is you assume that the edge $(u,v)$ is not in the MST $T$. Don't be confused by the board, it has to be $(u,v)\not \in T$. Let $(a,b)$ the edge that we swap with $(u,v)$. Bot edges are cut edges between $A$ and $A\setminus V$.
The tree $T'$ after the swap has weight
$$w(T')=w(T)+w((u,v))-w((a,b)).$$
As a consequence $w(T')<w(T)$, which is a contradiction and therefor the assumption $(u,v)\not\in T$ was wrong.

Notice that this proof uses the assumption that all edge weights are distinct, however it is easy to modify it for general edge weights.


Where are C++ templates inside of the lambda cube?

But is that exactly where they are located in the lambda cube?

The lambda cube is not a giant spectrum on which all programming languages can be classified. It is precisely eight languages, which combine a lambda calculus (values abstracted over values) with all possible combinations of three features:

Values abstracted over types (parametric polymorphism)
Types abstracted over types (kinds / type constructors)
Types abstracted over values (dependent types)

So, the C++ template language isn't anywhere on the lambda cube, since it isn't any of those 8 languages.

The second thing to keep in mind is that we can't mix up C++ features and C++ template features. Just because C++ has lambdas, this doesn't (necessarily) mean that its template language has them.

It is possible to ask, which of the three lambda-cube features does C++ have? It would seem that it features the full power of the lambda cube, but I'm not enough of a C++ expert to know for sure.


That is not possible, when a deadlock occurs, the system is in an UNSAFE state. A safe state wouldn't have any purpose if a deadlock could occur.


Is hedge union always as fast as divide and conquer?

While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are worse than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell containers package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with containers. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.

Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.


A dense NP complete language implies P=NP

This is a nice homework problem about Mahaney's theorem.

Note that the complement of a "dense" language is a sparse language. Moreover if a language is  $\mathsf{NP}$-complete its complement is $\mathsf{coNP}$-complete.

If there is a "dense" $\mathsf{NP}$-complete language, there is a sparse $\mathsf{coNP}$-complete language.

Mahaney's theorem tells us that there is no sparse $\mathsf{NP}$-complete language unless $\mathsf{P}=\mathsf{NP}$.

We can adopt the proof to show that there is no sparse $\mathsf{coNP}$-complete language unless $\mathsf{P}=\mathsf{coNP}$ which is equivalent to $\mathsf{P}=\mathsf{NP}$ (since $\mathsf{P}$ is closed under complements).

In summary, the answer is no unless $\mathsf{P}=\mathsf{NP}$. Note that if $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is $\mathsf{NP}$-complete.

ps:
You may want to try the following and then use Mahaney's theorem: there is a sparse $\mathsf{NP}$-complete set iff there is a sparse $\mathsf{coNP}$-complete set.
However I doubt that a proof for this statement would be much easier than a proof for Mahaney's theorem.


Which language families admit inductive definitions?

We can study families of languages in terms of their closure properties, it then makes sense to consider languages which generate the family under those closure properties.

Some work in this area has been done (particularly for cones/AFLs) and there may be known results for some or all of the families of languages that you mention but the only result which I know off the top of my head is for the context-free languages:

The context-free languages are the smallest cone generated by the Dyck language on two symbols.

For a proof of this theorem and some similar results for other language classes within context-free see Berstel's book which is now freely available on his website here.


Delete a node with 2 children in a binary search tree

Your approach works in your example, but not in general. For example, if the node with key 5 also has a left child with key 4.5, it will not be correct because the resulting tree is not a binary search tree anymore.

You have to replace the node to be deleted (4) not with its right child (5), but with its successor in the key ordering, which is the least-valued node in its right sub-tree (in your example, that is indeed 5, but in my example it would be 4.5, not 5).


Prove EXPTIME \ NP is not a subset of NP-Hard?

Hint: note co-NP $\subseteq$ EXPTIME, and co-NP-complete $\cap$ NP = $\emptyset$ since NP $\neq$ co-NP, it remains to prove co-NP-complete $\nsubseteq$ NP-hard.

   Further hint: if co-NP-complete $\subseteq$ NP-hard, try to show for each language $L\in$ NP, you can build a NTM deciding $\bar L$, thus NP $\subseteq$ co-NP, a contradiction.


Need an adaptive algorithm for participant subgroups that balances repeated pairings

It sounds like the stakes are low, so I would suggest something simple and "good enough", rather than looking for fancy algorithms that will be guaranteed to give the optimal solution.  One approach is to take the approach you're already considering, but break ties randomly.  This seems like it may do well enough in practice: it is possible to get  into a bad situation, but the randomness might make that unlikely; and this might occasionally have one student participate a little more than they otherwise would, but that I'd expect that to average out over time and so maybe it isn't a big deal.


Efficiently find smallest unique substring

You can try suffix array approach which find all suffix of a given string of length n in O(n) time.
There are many algorithm to construct suffix array from a given input string.
Look at complete taxonomy here
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

For your problem you can use suffix array couple with some additional counter to find solution.


Logic gate which checks if the input is a negative number and changes its output based on that

You miss the obvious solution, just wire the MSB to output.


Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings?

Consider a two state automaton for the language $a^*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state.

Making the initial state final, would also accept $a^*$.


Which parser has the highest reduce moves?

The number of reductions in a successful parse is strictly dependent on the grammar, since every production must be reduced exactly once.

Consequently, all LR parsing algorithms which can parse a given grammar will parse all sentences accepted by the grammar using the same number of reduction steps (and the same number of shift steps).

The only moment in the parse where an extra reduction might possibly occur is just before an error action for a sentence which cannot be parsed by the grammar. The sequence of reduction/shift steps is still the same for all parsing algorithms up to and including the last shift; the only possible difference is some algorithms can perform more reductions before the error is noted.

This will be affected not only by the choice of parsing algorithm but also by the particular parse table compression algorithm used, since table compression generally involves replacing some error actions with the state default action in order to reduce table size. (Since the sentence is not recognised by the grammart, the parser will not be able to shift the lookahead token. So replacing an error action with a default reduction action must still produce an error before the lookahead token is shifted.)


This is not a simple question, and you shouldn't expect a simple answer.  There are a range of similar questions in this space: why do we study asymptotic running time?  why do we use asymptotic running time analysis to analyze algorithms?  why do we study complexity theory?  Each of those has multiple answers; there is not just a single reason why we do it, and different people may have different reasons.
Asymptotic running time analysis has advantages and disadvantages.  You've accurately identified one of the disadvantages: a good asymptotic running time doesn't guarantee good running time in practice.  But if you focus on only a single advantage or disadvantage you're not going to get the full picture of the strengths and weaknesses of that style of analysis.  Some of the advantages are that analysis is relatively tractable, it is not specific to a particular architecture, it provides useful information about scalability, and at least some of the time it has useful predictive power at identifying algorithmic bottlenecks.  For instance, the difference between a $O(n^2)$ time algorithm and a $O(n \log n)$ time algorithm can often be significant, even if we are ignoring the constant factors.  Some of the disadvantages are that constant factors can be important, cache and memory hierarchy effects can be very important yet are ignored by asymptotic running time analysis, and (like any metric)  optimizing solely for asymptotic running time can lead to absurd results of little practical utility (see galactic algorithms and Goodhart's law).
I think it's also useful to examine the alternative.  I encourage you to explore the alternative to asymptotic running time analysis and work through what you'd propose in its stead.  If you don't try to come up with a concrete proposal, it's easy to assume that it can't be that hard to find something better... but when you're forced to commit to something specific, you might discover that it's more challenging than you anticipated.  For instance, I encourage you to familiarize yourself with Knuth's analysis of algorithm running time on MIX in his TAOCP series.  There he does concrete running time analysis, with no asymptotics, taking into account the constant factors.  If you force yourself to work through the details of that, you'll quickly discover the disadvantages of that: it's super-tedious, very specific to a particular computer architecture, and often not much more enlightening.
We could similarly discuss each of the other topics - e.g., why or why not to study complexity theory - and you'd find that they too have nuances.
I also want to highlight for you that the theory and algorithms community is a broad one, with a range of different styles of work.  You seem to be lumping it all together into one pile, but there's a spectrum of work: some of it is super-theoretical and far afield from practice, some of it is highly practical and motivated by concrete problems and may have immediate impact, and there is a range of work at various point in between those extremes.  I think it's important to understand that there is some work in the theory community that is of great practical relevance or has had major impact, just as there is work that much more theoretical and not motivated by near-term impact.
Since you asked for theoretical frameworks that are focused on meeting industry's needs, you might also be interested in the Word RAM model, cache-oblivious algorithms, and the parallel external memory model.
I strongly encourage you to read the following resources, as they are closely related to your question: Why polynomial time is called "efficient"?, Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms, Justification for neglecting constant factors in Big O.


Tokenisation does not search. [Note 1]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.
Although there are other tokenisation algorithms, the most common one -- usually called maximal munch -- works as follows.
At each step:

Find the longest match of each pattern starting at the current input point. (This can be done in a single linear-time left-to-right scan of the input.)

Select the longest of all these matches. If more than one pattern has the same longest match, select the pattern which comes first in the list of patterns. Report the selected pattern and the corresponding matched prefix as the next token.

Remove the matched prefix from the input, and continue from the first step.

In effect, the match in the first step is a match of a regular expression created from the disjunction of all the patterns. The regular expression matching algorithm is modified so that:

It also reports which alternative matched, and

It leaves unmatched input in the input strean, rather than insisting that the regular expression match the entire input.

For your answer C, the regular expression created is $c^*+b^++ab+ac^*$.  (Some tokenisers would correct the first pattern to $c^+$ because selecting an empty match would cause the above algorithm to fall into an endless loop.)
The longest prefixes successively matched by this disjunction are:

$ab$ (3rd alternative). The 4th alternative matches $a$, but that us shorter.

$bb$ (2nd alternative) The second alternative will also match $b$, but that's not the longest prefix matched by this pattern.

$a$ (4th alternative)

$acc$ (4th alternative)

Notes

This should be intuitive. After all, most programs are read left to right and token order matters: $a = b + c;$ cannot be written as $a b c =+ ;$, and the parser will expect to see the tokens in left-to-right order, so if the lexer produced the stream,  $a b c =+ ;$, the parser would get confused.


The Transport layer offers services as:

Connection-oriented communication
Same order delivery
Reliability
Flow control
Congestion avoidance
Multiplexing

The network layer is responsible for packet forwarding including routing through intermediate routers.

The answer is definitely Network layer.


A matching in which all the vertices in $A$ are matched is known as a perfect matching. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is zero-one. The permanent-vs.-determinant question is analogous to the more famous P-vs.-NP question.

When $m > n$, you can add $m-n$ dummy vertices to $A$ and connect them to all vertices in $B$. The number of perfect matchings in the new graph is exactly $(m-n)!$ times the number of perfect matchings in the old graph.


It's difficult to call Reed-Solomon a fountain code. This is due to two reasons.

The first reason is rather technical.
Let's assume you use a systematic code. After sending the message itself (the systematic part), the "fountain" is the remaining redundancy symbols = evaluation of the polynomial in other points. In order to be decoded correctly, you must attach to each symbol the index it belongs to, i.e., the point it is evaluated in. You cannot permute the symbols order and still decode correctly, hence the index is crucial.
So RS by itself doesn't fit the decoding properties of fountain codes, where any order of received symbols is OK. However, this is merely a technicality since you can always send the symbol along with its index (this is also done in fountain codes).

The second reason is more meaningful and inherent.
In a (systematic) $[n,k]$ block codes (e.g., Reed-Solomon), there are exactly $n-k$ redundancy symbols. That's it. You don't have a "fountain" of "infinite" number of redundancy symbols you can send. You only have $n-k$, and once the decoder receives enough of them it will be able to decode. Using RS notations, you can evaluate the polynomial only in points in the finite field $\mathbb{F}$, and there is a finite (and relatively small) amount of them.

So the "fountain" in block-codes reduces to only be re-sending the $n-k$ redundancy symbols again and again, and requiring the decoder to collect (almost) all of them. This is not as good as the properties fountain codes are providing.


Reference request: Category theory as it applies to type systems

Category theory is not necessary to understand programming languages, it's not even necessary to do advanced research on programming languages. Most programming language people don't know (much) category theory.

Category theoretical methods have been useful mostly in a small part of programming language research, namely in the analysis of functional programming, particularly, since Moggi's great discovery that some computational effects have monadic structure. In the 1990s, following Moggi's breakthrough, a lot research was done to extend categorical methods to other forms of programming languages. However, to the best of my knowledge categorical methods have not been found all that useful for  OO, concurrent, parallel and distributed computation, timed computation or compilers. For this reason, people have mostly abandoned extending categorical methods.

Categorical approaches to typed programming work well in pure functions. Indeed some simple typing systems are categories. This is described in e.g.

Categories for Types by Roy Crole
Introduction to higher order categorical logic by Joachim Lambek and Phil Scott.

There is now a lot of work on types for concurrent processes (e.g. session types) and none of that is categorical in nature as of Sept 2016.

That said, one can never know too much mathematics, and knowing category theory is useful. So it's a question of cost/benefit. If you like maths, if maybe you have a bit of background in algebra (e.g. what's the free group over a set, free ring etc) then learning category theory will be easy, and if you plan on doing work that is (inspired by) functional programming, knowing categories will be useful.

Finally, category theory is beautiful mathematics, and worth studying simply because it's so neat.

See Uday Reddy's contribution in this discussion for a different view.


If you use augmented AVL (or any self-balancing tree like RB) tree with additional pointers for quantiles then maintaining median and quantiles work in logarithmic time. Inorder traversal is always sorted so if juggling with pointers is not good option for you, maintain tree, with one insert and delete per move and caclulated statistics during inorder traversal.

It is good to keep online algorithms whenever possible, keeping say mean or variance as accumulators, not recalculating all the time.

I have similar need, only maintaining median, mean, standard deviation and kurtosis. Here I keep threaded AVL tree with additional online version of statistics, moving median pointer on insert/delete.


What determines the entropy of a program's source code?

This is a classical question in the foundations of Kolmogorov complexity: does the programming language matter for the sake of defining minimal description length? It depends on your model, but in general the answer is "no" or "almost no".

Suppose that $P_1,P_2$ are two Turing complete programming languages. In particular, in $P_1$ you can write an interpreter $I$ for $P_2$. Therefore any program $\pi$ written in $P_2$ can be converted in $P_1$ by pasting together $I$ and $\pi$. What is the length of the combined program? In any reasonable programming language, it is $O(|\pi|)$, and so different programming languages only have at most a constant multiplicative advantage over each other. If we are more stringent in our requirements on the programming languages, the answer should be $|\pi| + O(1)$, which is what happens in Kolmogorov complexity. In this case different programming languages only have at most a constant additive advantage over each other.

The idea behind $\pi + O(1)$ is that you should be able to concatenate the code for $I$ with $\pi$. But in practice this is not quite possible. Suppose for example that $P_1$ is $C$. We need to write $\pi$ as a string. If the character set of $\pi$ includes backslash or double quotes, then we will need to escape these, which could result in a multiplicative blow-up. Still, we get a $C$ program whose length is $O(|\pi|)$. If we are careful in our definitions then we can prevent this — check any introductory text on Kolmogorov complexity for the details.


A sub-permutation (not necessarily initial) corresponds to the removal of rows and columns in your restriction matrix. So your problem can be reduced to the case $N = 0$ (you also have to check that your sub-permutation conforms to the restriction matrix). In order to determine whether a restriction matrix admits any permutation, treat it as an $n \times n$ bipartite graph, and check whether the graph has a perfect matching.

Here is an example. Consider your restriction matrix
$$
\begin{matrix}
1&1&1&0 \\
1&1&0&1 \\
1&0&1&1 \\
0&1&1&1
\end{matrix}
$$
Choosing the first three elements to be $1,2,3$ is the same as deleting the first three rows and columns. We get $\begin{matrix} 1 \end{matrix}$, which has a perfect matching as a $1\times 1$ bipartite graph.

In contrast, choosing the first three elements to be $3,4,2$ is the same as deleting the first three rows (say) and columns $3,4,2$ (rows and columns might be switched depending on the representation). We get $\begin{matrix} 0 \end{matrix}$, which doesn't have a perfect matching.


Fast algorithm for finding the size of each connected component in a graph of 2D points

You can do it in $O(n \log n)$ time by forming an Euclidean minimum spanning tree, and then dropping any edge with length greater than $t$.


Should names of built-in funtions be part of BNF grammar?

If your language has a small set of functions and there is no mechanism for adding other ones, then you could include the function names as keywords. But that's not a very likely scenario, unless your "language" is just a desk calculator (and even then, these days many calculators allow you to define functions).

So in general, it's not going to be feasible to include all the function names in the lexer, and unless function names are somehow lexically distinguished from other identifiers, all the lexer can do is report that it has found an identifier.

Assuming the grammar is unambiguous, a common idiom is to use a unit rule in the BNF in order to encapsulate whatever needs to be done to turn an identifier into a function reference (and similarly for identifiers representing other kinds of things) [Note 1][Note 2]:

function_name: IDENTIFIER
type_name:     IDENTIFIER
...

term:          function_name '(' optional_expresion_list ')'

But that won't work if certain expressions in the language would be ambiguous without knowing whether an identifier in the expression names a function or some other kind of thing. That's not very common for function names, but C and derived languages famously feature an analogous ambiguity with type names in C.

It's not totally unknown, though. For example, in awk, string concatenation is expressed with simple operand juxtaposition, so that

first "-" second

is the concatenation of two variables and a string containing a dash. The result is that

first (second)

is ambiguous: if first names a function, it could only be a function call; otherwise, it could only be string concatenation. If the language insists of declaration before use (awk doesn't), it would be possible to disambiguate by distinguishing according to the type of first.

The implementation involves sharing a symbol table between the parser and the scanner. The scanner looks each identifier up in the symbol table, and returns a token based on the broad type (or "kind") of symbol. If the scanner does not find the symbol, it will return a token of type UNDEFINED_SYMBOL or some such, which will be required (or at least allowed) in grammar rules where a new symbol is defined.

This technique is commonly called "semantic feedback". Much care must be taken to ensure that the symbol table seen by the lexer while it is examining a token corresponds to the actual semantic state at the moment in which the parser is examining the token. Since lexers typically consume tokens in advance of the parse (or at least one token), this guarantee is not as easy as it might look at first glance.

Semantic feedback is often discouraged, both because of this fragility and because it contaminates the lexer with data which should be private to the parser. But sometimes it is the simplest solution.

As it happens, awk does not use this approach, in part because it does not require functions to be declared prior to use. Instead, it has a whitespace-aware lexical rule: a parenthesis which immediately follows an identifier without intervening whitespace is used in a function call expression; if there is intervening whitespace, the parenthesis must be a grouping parenthesis and the expression is treated as a concatenation. This rule is the source of occasional confusion about apparently mysterious errors (see below).

That rule could be expressed in two ways (at least):

The lexer could return a FUNCTION_NAME token when it sees that the character immediately following an identifier is a (. In that case, the grammar might include

term: FUNCTION_NAME '(' optional_parameter_list ')'
    | '(' expression ')'

The lexer could distinguish between two kinds of open parenthesis: a parenthesis which immediately follows an identifier, and all the other ones. So then the grammar might include:

term: function_name OPEN_APPLY optional_parameter_list ')'
    | '(' expression ')'

(A third possibility exists, in which the function name and the following parenthesis are recognized as a single token, leading to the rather odd-looking grammar rule FUNCTION_NAME optional_parameter_list ')'. Some real-world implementations actually use this for efficiency, but it's confusing for the reader.)

Editorial comment (i.e. my opinion)

On the whole, you should attempt to avoid playing tricks in your lexer. Ambiguities like the ones mentioned above should be treated as flaws in the language design rather than challenges to be overcome by clever hacks in the parser, particularly if you are designing a language. History demonstrates that ambiguities like the above not only complicate parsers, but also confuse people using the language in question.

A casual search for "most vexing parse" will show the extent of confusion created by an ambiguity in the C++ language. And the use of juxtaposition for concatenation in awk creates so many confusing parse errors that the Gnu awk manual has a chapter about how to write concatenation, citing the alleged explanation for the syntax given by one of the awk authors: "It seemed like a good idea at the time."

Notes

In this post, I use yacc syntax for the BNF, with the convention that terminals (tokens) are represented either by UPPER_CASE or by quoted characters, and non-terminals are spelled in lower_case.
While some languages might be content to not allow higher-order types, almost all languages -- even C -- allow the target of a function application expression to be a computed value. So if you find yourself writing the above rule, you might want to think about its implications for the semantics of your language.


Calculating the number of unique BST generatable from n keys, why is my number so large

You overcounted some of the trees and left out two other possibilities. In your Case 1, for example, there is only one possible BST of that form, namely the one with 2 in the root, 1 in the left subtree and 3 in the right subtree (the leftmost tree below). Remember that you have to maintain the binary search tree condition: a node with value $k$ must have each of the values in its left subtree less than or equal to $k$ and each of the values in the right subtree must be greater than or equal to $k$. As a consequence, a BST with node values $\{1, 2, \dotsc,n\}$ must have inorder traversal equal to $\langle1, 2, \dotsc,n\rangle$. When $n=3$, then, we'll have these five BSTS:


Finding an optimal solution for a problem is very difficult. for example in sorting you can prove that the optimal solution with comparison is $O(n \log n)$ but may be you can find an algorithm with $O(n)$ without comparison like hashing! another good example is NP Complete problems we even can't prove they haven't polynomial algorithm. so it is very hard to find an optimal solution for deep blue and similar algorithms and proving that the algorithm is optimal is very hard too.


Why are CFLs not closed under intersection?

Let us assume $2$ CFLs $L_1$ and $L_2$ and their corresponding grammars be $S_1$ and $S_2$ respectively.
It is very straightforward to see that the union of the two, represented by the new grammar as
$$S \to S_1 \mid S_2$$
is also a CFG, as the rule of being context-free is still not violated. Context-free grammar

But to prove that they are not closed under intersection, I'll provide an example.
Let $L_1$ and $L_2$ respectively be:
$$L_1 = \{ a^nb^nc^m \mid n, m \ge 0 \}$$
$$L_2 = \{ a^mb^nc^n \mid n, m \ge 0 \}.$$
It is not hard to see that $L_1 \cap L_2$ is
$$L = \{ a^nb^nc^n \mid n, m \ge 0 \},$$
which is not CFL (No PDA cannot accept that language).
Hope this explains.


Big-O complexity when c is a tiny fraction

Medium answer - yes. As you said for the previous case, in the long run $n^4$ outpaces all of them. This is still true despite the constant in front.

Check it out: plot.

Also, remember that $n^3$ and $n^4$ are both $O(n^4)$, and in fact are both $O(n^{10})$ because big-O is an upper bound. So you might ask "is there any tighter big-O bound on this function than $O(n^4)$, like $O(n^3)$, and the answer would be no.


How to count the combinations not greater than a given volume in a knapsack problem?

Why did it fail?

Look at the code cache = new int[size+1][volume+1];. Suppose size is 1 and volume is $10^9$. One int uses 4 bytes. So this cache will use $4 \times 2 \times 10^9$ bytes, which is about 8G, which is way much bigger than the limit, 32768K. So the online judge will show you out-of-memory error.

  Could a DP solution without backtracking be found for this?

The right strategy here is called "meet in the middle". Here is the idea of the algorithm, where $w$ is the volume of the bag.

Split the items into $A$ and $B$, two lists of approximately equal size.
Compute all possible sums of items in A, appending them to array arrA. Sort arrA.
Compute all possible sums of items in A, appending them to array arrB. Sort arrB.
For each number in arrA, find the last element in arrB such that the sum of the two is not greater than $w$. Let its index be $upper$. Add $upper + 1$ to the total.
Return total.

The time-complexity of the algorithm is $O(n2^{n/2})$, which comes from sorting two arrays of size about $2^{n/2}$. For $n= 30$, we get $30\times 2^{30/2}=30\times32768$, which is about 1 million.

The space-complexity of the algorithm is $O(2^{n/2})$. For example, if $n= 30$, we allocate two arrays of longs of size $2^{15}$, which spans $2\times2^{15}\times8$ bytes, which is less than 600K. We need some extra work memory for sorting and etc, which will at most triple the memory allocated specifically for our algorithm.

Here is the implementation in Java.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();
        final int w = sc.nextInt();
        final long[] v = new long[n];
        for (int i = 0; i < n; ++i) v[i] = sc.nextLong();

        int total;
        if (n == 1) {
            if (v[0] <= w) total = 2;
            else total = 1;
        } else {
            final int half_n = n / 2;

            final long[] front = getSortedSums(v, 0, half_n);
            final long[] behind = getSortedSums(v, half_n, n);

            int lastIndexFront = front.length - 1;
            while (front[lastIndexFront] > w) lastIndexFront--;

            int upper = behind.length - 1;
            for (int i = 0; i <= lastIndexFront; i++) {
                while (front[i] + behind[upper] > w) upper--;
                total += upper + 1;
            }
        }

        System.out.println(total);
    }

    // Return all possible sums of elements in the specified segment of v,
    // sorted. Note the first sum is 0, representing the empty sum.
    private static long[] getSortedSums(long[] v, final int low, final int high) {
        int index = 0;
        final long[] sums = new long[1 << (high - low)];
        for (int i = low; i < high; i++) {
            long u = v[i];
            int end = 1 << (i - low);
            for (int j = 0; j < end; j++) {
                sums[++index] = sums[j] + u;
            }
        }
        Arrays.sort(sums);
        return sums;
    }
}


Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?

If the goal is to find the shortest solution to the 8-puzzle, DFS is indeed a very poor method.  It's not a matter of faster or slower; DFS is not correct (it finds a solution, but it's not guaranteed to be the shortest solution).  You could use BFS and that will work fine.  Even better is to use A* or some related algorithm; it will find the shortest solution even faster than BFS.

If the goal is to find any solution to the 8-puzzle, without regard to how many moves the solution takes, DFS is a fine method.  Actually, you could use either DFS or BFS for that.  The 8-puzzle has only 181440 reachable states, so the data structures won't grow too large.


How to prove semi-decidable = verifiable?

Its obvious why a semi-decidable language is verifiable ($w$ would be the machine's computation history on $x$). Now, we will show the other way:

Let $V(x,w)$ be a verifier for $L$. Define $M(x)$ as the following algorithm:

Let $S$ be an empty array (of turing machine emulations)
For every $w\in\Sigma^*:$

Add a new emulation of $V(x,w)$ to $S$.
For every emulation $E\in S:$

Compute one step for $E$. If, $E$ accepted, then accept.

This algorithm is correct, since if $x\in L$ then there is some $w\in\Sigma^*$ with $V(x,w)=True$ and therefore the algorithm will accept.

If the algorithm accepted, then there must be some $w\in\Sigma^*$ where $V(x,w)=True$ and thus $x\in L$ by definition


$b_4$ is what is called a trap state, that is, a state that exists just so that all possible transitions are explicitly represented, even those that do not lead to a final state.

It doesn't change the language that is being defined, and can be omitted for the sake of brevity.


If understand the question correctly you want to find a $k$-coloring of the given graph, given an ordered list of the vertex such that vertex with the same colors are consecutive in this list.

If that is the case then this problem can be solved greedy.

We should only find maximal independent sets which are contiguous segments in your list starting from the beginning. Start with an empty set. Go for every vertex in the ordered list, if the vertex is not connected to any other node in the set, include it. Otherwise, paint all vertex in the set with the same color, notice they form a consecutive interval in the list, then clear the list and include the current node you are processing. At the end you should paint all nodes remaining in the list with the same color.

Rationale

We should partition the list in minimum amount of intervals such that all vertex within the same interval are not connected to any other vertex (they are an independent set). Since the first vertex in the list belong to an interval, this interval should start at this vertex. The proposed algorithm will find maximal interval containing this vertex. It is impossible to find any bigger interval containing the first vertex (since the one chosen is maximal) and it doesn't make any sense to find any smaller interval, since not taken vertex will only increase our restrictions in the future while taking next intervals.

Pseudocode

Graph := Relations between vertex. Graph[u] is the list of all neighbors of u
List := Order of vertex. List[1] = v1, List[2] = v2, etc...

S := {} (Set with all nodes in the interval we are keeping)
color := 0 (Number of colors used so far)

# Iterate through all vertex
for vertex in List:

   # Check this node is not connected to any other node in S
   ok := True
   for neig in Graph[vertex]:
      if neig in S:
          ok := False
          break

   if ok:
       # If vertex is not neighbor of any other vertex in S, include it in.
       S.add(vertex)
   else:

       # Paint all vertex in S with color
       paint(S, color)

       # Increase color, since an interval of nodes was painted
       color += 1

       # Reset S, starting with current node.
       S := {vertex}

# Don't forget to paint last interval

# Paint all vertex in S with color
paint(S, color)

# Increase color, since an interval of nodes was painted
color += 1

Complexity and details

Notice in the implementation you don't need to maintain the set of taken nodes S explicitly, since all nodes in that set belong to an interval they can be easily represented with two pointer (the begin of the interval and the end of the interval). The overall complexity of this solution is $O(|V| + |E|)$, since every node is visited once in the first loop, and edges are traversed twice, one per endpoint. Regarding paint function, it is potentially linear in the number of vertex it is painting, but that is ok, since we paint each vertex exactly once.


Is it possible to implement a WeakMap with primitive keys and weak values?

Okay. My confusion with this question is that I assumed that what you wanted is a weak value map, which it appears is what you want, and this can be implemented in a straightforward manner (at least as straightforward as a weak key map). I'm using (slightly modified) terminology from Designing Efficient and Safe Weak References in Eiffel with Parametric Types.  The JavaScript WeakMap is indeed a weak key map, and, as you seem to understand and D.W. states, it makes no sense to have weak references to primitive values, and thus primitive values as keys in a weak key map.

As far as a weak value map, it's implemented basically the same as a weak key map. For example, for a mark-sweep GC, during the sweeping phase if the GC notices that a value in a weak value map is dead it removes all entries in the map referencing it.  A weak key map is basically the same only it considers the keys.  The Eiffel paper also talks about weak vectors and doubly weak maps where either the key or the value dying results in the entry being removed.

A weak reference primitive as described in the paper or as in e.g. Java's WeakReference would make this a straightforward exercise. You'd just wrap a Dictionary<Key, WeakReference<Value>> to clean out entries on access, say.


In general, you can look at hard combinatorial instances. If 50 variables is not a hard limit, try e.g., an instance arising from combinatorial block design having 105 variables described in [1]. The actual instance in DIMACS format is here provided by the authors. For the instance, the authors write in [1] that: "We issue a challenge for any solver to solve it in less than one day."

Something that will be not as hard, but still not entirely trivial is coloring Mycielski graphs. These are graphs with clique number 2, but the chromatic number can be arbitrarily large. Again, if 50 variables is really a hard limit, it seems the largest Mycielski graphs you can consider is the Grötzsch graph if you use the obvious encoding to CNF. The obvious encoding will have 33 variables if you test for 3-colorability (UNSAT), and 44 variables if you test for 4-colorability (SAT).

[1] Van Gelder, Allen, and Ivor Spence. "Zero-one designs produce small hard SAT instances." Theory and Applications of Satisfiability Testing–SAT 2010. Springer Berlin Heidelberg, 2010. 388-397.


Understanding recursion tree for withdrawal formula

Your recurrence expands into a recurrence tree in the following way. Each node has a label. If the label $n$ is $a$ or smaller, then the node is a leaf. Otherwise, the node has two children, one labeled $n-a$, the other one labeled $a$.

Suppose that you create this tree starting with a root labeled $n$. The root has two children: one is labeled $n-a$, and the other one, labeled $a$, is a leaf. The node labeled $n-a$ has two children, one labeled $n-2a$, and the other one is a leaf. And so on.

It takes roughly $n/a$ steps until this process terminates (since we start with $n$, have to get to $a$ or less, and drop by $a$ each time). Therefore the height of the tree is roughly $n/a$.


I found (surprisingly many) copies of that text on the web (see
http://www.slideserve.com/janna/virtual-memory). That helps
ascertaining there is no vocabulary mismatch.

The 32-bit entry makes for $2^{32}$ physical (not logical as you write in
your comment) address space for pages, i.e. $2^{32}$ frames.  The address
of the logical page is used for indexing the page-table, and the 4
bytes content of the corresponding entry of the page table is the
address of a page frame, i.e. a physical page.

So you have $2^{32}$ physical pages. But there is nothing in the above text that tells the size of the logical space. It could be much larger, with logical page addresses of 8 bytes, or it could be smaller which did happen on some architectures. For more details on this, see this discussion regarding virtual memory on 32 bits hardware. There may be other issues with more recent 64 bits hardware. The size of the page-table would tell you what is the size of the virtual memory space, i.e. of logical addresses.

Does this clarifies the problem?


It's pretty straightforward from an operational perspective.  It finds all the facts deduced by firing all the rules for exactly one round on the current database.  Typically, you'll have $I_{n+1} = I_n \cup T_P(I_n)$ so that $I_n$ is a monotonically growing database.

Concretely, say you have the following rules and facts.

p(a).
q(X) :- p(X).
r(X) :- q(X).

Then the initial database is $I_0 = \{\mathtt{p(a)}\}$.  $T_P(I_0) = \{\mathtt{q(a)}\}$, so $I_1 = \{\mathtt{p(a)}, \mathtt{q(a)}\}$.  Then $T_P(I_1) = \{\mathtt{q(a)},\mathtt{r(a)}\}$ and $I_2 = \{\mathtt{p(a)}, \mathtt{q(a)},\mathtt{r(a)}\}$.  Finally, $T_P(I_2) = \{\mathtt{q(a)},\mathtt{r(a)}\}$.  At which point $I_3 = I_2$ which would be an implementation's signal to stop.  (In my particular formulation I didn't include facts as consequences but you could do that as well.  It's not clear if your definition treats facts as rules with empty heads.)


How many tapes would Turing Machine require to find the sum of 2 integers (expressed in base2)?

Anything that can be computed with any reasonable extension of a Turing machine can be computed with the standard Turing machine that has a single one-way infinite tape.

For example, you can simulate a four-tape machine by interleaving the characters of the tapes so that, e.g., the four tapes

$$\begin{array}{cccc}
    a_1 & a_2 & a_3 & \cdots\\
    b_1 & b_2 & b_3 & \cdots\\
    c_1 & c_2 & c_3 & \cdots\\
    d_1 & d_2 & d_3 & \cdots
\end{array}$$

with the single tape
$$a_1\ b_1\ c_1\ d_1\ a_2\ b_2\ c_2\ d_2\ a_3\ b_3\ c_3\ d_3\ \cdots$$


Proof high-entropy sequences are hard to compress

You are looking for Shannon's source coding theorem.


Algorithms that must compute a global property?

A silly example: Checking if a graph has more than m nodes. :-)
Some more interesting examples:

Checking if a graph is connected.
Checking if a graph has an Eulerian cycle. A graph is Eulerian iff all degrees are even and the graph is connected: https://en.wikipedia.org/wiki/Eulerian_path
Checking if a graph has a perfect matching: https://en.wikipedia.org/wiki/Blossom_algorithm


2) Suppose that $\mathsf{NP} \subseteq \mathsf{coNP}$: in particular, SAT is in $\mathsf{coNP}$, and its complement coSAT, the set of boolean formulas that are not satisfiable, is in $\mathsf{NP}$. But coSAT is coNP-complete, so that we have a coNP-complete language in $\mathsf{NP}$, i.e. $\mathsf{coNP} \subseteq \mathsf{NP}$.

3) This depends on your definition of a CSP, I guess. Following the definition of a non-uniform CSP, the constraint satisfaction problem of a relational structure $\Gamma$ is the set of relational structures $\Delta$ on the same signature such that $\Delta$ homomorphically maps to $\Gamma$. Here, the signature is $\{E\}$, where $E$ is a binary relational symbol that indicates adjacency in graphs. Suppose that there exists $\Gamma$ such that $\mathrm{CSP}(\Gamma)$ is the $k$-CLIQUE problem. Then, letting $K_k$ be the $k$-clique, we have that $K_k$ homomorphically maps to $\Gamma$. But if $v$ is any vertex of $K_k$, we have that $\{v\}$ homomorphically maps to $K_k$, and since the composition of homomorphisms is a homomorphism, we have that $\{v\}$ has a homomorphism to $\Gamma$, a contradiction since $\{v\}$ does not contain a $k$-clique. Thus, the k-CLIQUE problem cannot be represented as a non-uniform constraint satisfaction problem.

Please let me know if the definition I used for the CSP is not the one you are used to!


outside of bitcoin, how does a network negotiate what the next blockchain should be?

Here's how Bitcoin works.  I suppose we could say that each node can "propose" a different next block.  What this really means is that each node can select a "proposed" next block and start mining to attempt to append that block to the blockchain.  Bitcoin's proof-of-work  basically creates a lottery among all of the nodes who are doing this; it's random which one will win, but there will be only one winner, and once there is a winner, everyone will know which one won.

Nothing stops dishonest nodes from attempting to "propose" many different next blocks and mine from them.  If 100% of the network is dishonest, then you're screwed anyway.  So if you want any security at all, you need to assume that at least 51% of the nodes are honest.  And the crucial part is to look at how the honest nodes will behave.

The way that a protocol works is that it specifies how an honest node should work.  If the node is honest, it will follow the protocol faithfully -- that's more or less the definition of honest, in the world of protocols.  The Bitcoin protocol specifies how an honest node should determine what transactions to include in its proposed next block: include all of the transactions that it is aware of, and that are valid.  It also provides a mechanism to help all of the honest nodes learn of all possible transactions.

So, if at least 51% of the nodes are honest, they'll all "propose" the same next block (since they're all honestly applying the same validity checks) and start mining from that next block.

What about protocols other than Bitcoin?  No one ever promised that other protocols would be secure.  No one ever promised that merely using a blockchain (a hash-chained ledger) is sufficient to ensure security.  Bitcoin is a clever combination of multiple interlocking mechanisms that work together to provide security -- the beauty and magic is in how they fit together.  If you take away some of those mechanisms and keep only others, there's no reason to expect the result to necessarily be secure.  And it's not really possible to analyze the security of an unspecified protocol, where the only information we have about it is that "it uses a blockchain but isn't Bitcoin".


How to generate all combinations given an array of elements using backtracking?

I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases.
Combinations
So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways.
$$\sum_{k=0}^n{n\choose k} = 2^n$$
This is a subtle hint that you can think of a combination as a set of binary choices. Let us have $n$ levels in our search tree, not including the root level. At level $i$, we give ourselves the choice to add or not to add element $i$ to our current combination. In this way, we construct a tree of uniform depth such that any path from root to leaf constructs a unique combination and we also claim that all possible combinations are represented by the tree. Now we can just compute a DFS, and every time our search reaches a leaf node, we add the current path to the list of combinations (If you're wondering how to keep track of the current path, there are already many posts/resources about that). If you prefer to do it recursively, this is also trivial.
The difficult part of these problems is indeed coming up with the representation. Let's go back and take a look at your original proposal.
Permutations
Again lets think of our choices at every step. We construct a tree to represent these choices. At a node $p$ at level $i$, we can select any of the remaining numbers not present in the path $root\rightarrow ...\rightarrow p$. Therefore, every root to leaf path in our tree now represents a permutation of all $n$ elements. In order to also get the permutations of subsets of $1,2,...,n$, we consider all paths in the tree beginning at the root as possible permutations.
This seems to be what your tree depicts, and it is a common way to view the problem. Simply performing a DFS while keeping track of the current path should be sufficient to obtain an answer.


Are entities in a many-to-many relation related individually?

As far as I could understand, there are 3 entities here.

Map
Road
Road Segment

And the relationships between them are:

Map M:N Road
Road 1:N Road Segment
Map 1:N Road Segment

A map could have multiple roads and a road could in multiple maps. A road could have multiple segments, in each map it is a part of. And a road segment would be related to one map and one road.

And to identify whether two segments are related to same road we can query the Road Segment entity to get which segments are related to same roadId.


Find the number using binary search against one possible lie

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey.

In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result.

There are other elegant ways to handle up to $k$ of lies by only using $O(\log n + k)$ time (where $k$ might be a function of $n$).


Building on top of polygon intersection, a naive process would just intersect each polygon with every other polygon and using the area of the polygons and the area of the intersection could compute what you call the overlapping reign percentage. This is easily parallel, and one could use a simple bounding box intersection to avoid computing the polygon intersect when the polygons's bounding boxes don't overlap.


1 & 3. Not related to OpenCV. In this context, projecting into the unit sphere is the same as normalizing, which is making the vector's L2 norm (AKA the Euclidean norm or commonly marked as $||u||_2$ or in short $||u||$) equal 1. This is done to simplify the term in the beginning of step two: $\cos{\alpha} = \frac{v*u}{||u||\cdot||v||}=v*u$

2. Before you divide the vector with the focal length (distance between the plane and $P$), the projected point is a point in space that is on the image plane. This point would change if the focal length changes, but what you really want here is a point that is independent of the focal point, since it shouldn't matter to the pose of the $ABC$ triangle. Dividing with the focal length here is like changing the focal length to 1.


The reason that loops are faster than recursion is easy.
A loop looks like this in assembly.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

A single conditional jump and some bookkeeping for the loop counter.

Recursion (when it isn't or cannot be optimized by the compiler) looks like this:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

It's a lot more complex and you get at least 3 jumps (1 test to see if were done, one call and one return).
Also in recursion the parameters need to be set up and fetched.
None of this stuff is needed in a loop because all the parameters are set up already.

Theoretically the parameters could stay in place with recursion as well, but no compilers that I know of actually go that far in their optimization.

Differences between a call and a jmp
A call-return pair is not very much more expensive then the jmp. The pair takes 2 cycles and the jmp takes 1; hardly noticeable.
In calling conventions that support register parameters the overhead for parameters in minimal, but even stack parameters are cheap as long as the CPU's buffers do not overflow.
It is the overhead of the call setup dictated by the calling convention and parameter handling in use that slows down recursion.
This is very much implementation dependent.

Example of poor recursion handling
For example, if a parameter is passed that is reference counted (e.g. a non const managed type parameter) it will add a 100 cycles doing a locked adjustment of the reference count, totally killing performance vs a loop.
In languages that are tuned to recursion this bad behavior does not occur.

CPU optimization
The other reason recursion is slower is that it works against the optimization mechanisms in CPU's.
Returns can only be predicted correctly if there are not too many of them in a row. The CPU has a return stack buffer with a (few) handfuls of entries. Once those run out every additional return will be mispredicted causing huge delays.
On any CPU that uses a stack return buffer call based recursion that exceeds the buffer size is best avoided.

About trivial code examples using recursion
If you use a trivial example of recursion like Fibonacci number generation, then these effects do not occur, because any compiler that is 'knows' about recursion will transform it into a loop, just like any programmer worth his salt would.
If you run these trivial examples in a enviroment that does not optimize properly than the call stack will (needlessly) grow out of bounds.

About tail recursion
Note that sometimes the compiler optimizes away tail recursion by changing it into a loop. It is best to only rely on this behavior in languages that have a known good track record in this regard.
Many languages insert hidden clean up code before the final return preventing the optimization of tail recursion.

Confusion between true and pseudo recursion
If your programming environment turns your recursive source code into a loop, then it is arguably not true recursion that is being executed.
True recursion requires a store of breadcrumbs, so that the recursive routine can trace back its steps after it exits.
It is the handling of this trail that makes recursion slower than using a loop. This effect is magnified by current CPU implementations as outlined above.

Effect of the programming environment
If your language is tuned towards recursion optimization then by all means go ahead and use recursion at every opportunity. In most cases the language will turn your recursion into some sort of loop.
In those cases where it cannot, the programmer would be hard pressed as well.
If your programming language is not tuned towards recursion, then it should be avoided unless the domain is suited towards recursion.
Unfortunately many languages do not handle recursion well.

Misuse of recursion
There is no need to calculate the Fibonacci sequence using recursion, in fact it is a pathological example.
Recursion is best used in languages that explicitly support it or in domains where recursion shines, like the handling of data stored in a tree.

  I understand any recursion can be written as a loop

Yes, if you are willing to put the cart before the horse.
All instances of recursion can be written as a loop, some of those instances require you to use an explicit stack like storage.
If you need to roll your own stack just to turn recursive code into a loop you might as well use plain recursion.
Unless of course you've got special needs like using enumerators in a tree structure and you don't have proper language support.


Decision problems in $\mathsf{P}$ without fast algorithms

Perhaps the following problems fit into your examples:

(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms
for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
AKS-primality test in $O((\log n)^{12})$ time.
Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.


Determine whether a flow can satisfy node demands in a directed acyclic graph

Add a new source $s'$ and the edge $(s', s)$ with maximum and minimum capacity $R$.

For each vertex $v$ with demand $d$ do the following:

Replace $v$ with two vertices $v_1$ and $v_2$.
Replace all the former edges $(u,v)$ with $(u, v_1)$
Replace all the former edges $(v, u)$ with $(v_2, u)$.
Add the edge $(v_1, v_2)$ with minimum capacity $d$.

The problem is now equivalent to checking whether there exists a feasible flow in a network with minimum and maximum edge capacities.

This problem is well known and can be reduced to max-flow (see, e.g., "Balances and Pseudoflows" in the book Algorithms by Jeff Erickson).

Essentially, if $D$ is the sum of all the edges' minimum capacities:

Add a new source vertex $s^*$ and a new target vertex $t^*$.
Add the edge $(s^*, s')$ with maximum capacity $+\infty$.
For each edge $(u,v)$ with minimum capacity $c \neq 0$ and maximum capacity $C$, add the edge $(u, t^*)$ with capacity $c$, the edge $(s^*, v)$ with capacity $c$, remove the minimum capacity from $(u,v)$, and change the maximum capacity of $(u,v)$ to $C-c$ (if $C$ was $+\infty$ then the new capacity is also $+\infty$).
Check whether the maximum flow from $s^*$ to $t^*$ is equal to $D$.


Lower Bound for Time Complexity of Pairing Problem

This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.

The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)$.

For the upper bound, we can solve the problem by sorting both lists.

For the lower bound, if we fix the second array to be $y_i = i$, then we are essentially sorting the first array $X$. Stated differently, there is a reduction from sorting to this problem, with the same value of $n$ and no extra comparisons. Since sorting takes $\Omega(n\log n)$ comparisons in the worst case, this problem also requires $\Omega(n\log n)$ comparisons.

So far we have only discussed worst-case complexity, and the same argument also works for average-case complexity. The best-case complexity is $\Theta(n)$. This means that we can find a correct algorithm that runs in time $O(n)$ on some input; and every correct algorithm requires $\Omega(n)$ comparisons on every input.

For the upper bound, consider the algorithm that first checks whether both $X$ and $Y$ are increasing ($2(n-1)$ comparisons). If so, it returns the mapping $(x_i,y_i)$. Otherwise, it transfers control to an arbitrary correct algorithm.

The lower bound follows from the same reduction from sorting, since sorting is known to require at least $n-1$ comparisons on any input. Indeed, the same argument used to prove this shows that any algorithm for the pairing problem requires $2(n-1)$ comparisons on any input.


How to identify named points by coordinates?

I will assume the graph is connected (otherwise, break it down into connected components and recurse on each connected component).

Pick a single vertex.  Find an edge that uses that vertex.  That gives you two possibilities for the coordinates of that vertex.  Try one of them, propagate its implications, and see if it leads to a contradiction or a consistent assignment of coordinates to vertices. If it leads to a contradiction, try the other possibility.  If either leads to a consistent assignment, output that assignment.  If both lead to a contradiction, abort with an error.

So all that remains is to describe how to propagate the implications.  Suppose we have picked node AA and we assign it to location (2,2).  Then we find all edges between node AA and some other unassigned node.  This will let us assign a location to other other nodes, or abort with a cancellation.  For instance, once we assign AA to location (2,2), the edge AA,BB = (1,1),(2,2) causes us to assign BB to location (1,1) (which might trigger more implications) and the edge AA,CC = (1,1),(3,3) causes a contradiction (since AA can't be in location (2,2)).  Once this process completes, we check whether the resulting assignment is consistent with all of the edges; if not, we've found a contradiction.  Propagation can be done with any standard graph traversal algorithm, like DFS or BFS.

The running time to propagate the implications is linear in the size of the graph.  We only have to do that twice (once for each assumption about the location of the starting vertex), so the total running time is linear, i.e., $O(|V|+|E|)$.


If I understand the notation correctly, only $ab$ can fit both $(a+b)^{*}$ and $(a^{n}b^{n})^{n}$. I see no other way of stacking more $b$'s after the a's, since $a+$ suggest you should have at least one $a$ in every repetition of the expression in parentheses.

$(a+b)^{*}-ab$ seems like a regular language to me, since $ab$ rejects, $a+b$ just consumes one or more $a$'s before a $b$. If we can construct a DFA for $a+b$, we can construct one for $(a+b)^{*}$ as well.


set cover where only certain special subsets are allowed

Your problem is hardly easier than the general set cover problem.

Given a set $G=\{b, c, g, h\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=[\{c,g\}, \{b,c\}, \{g,h\}, \{b\}, \{c\}, \{g\}, \{h\}]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $[\{c,g\}, \{b,c\}, \{g,h\}]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.


If xor-ing a one way function with different input, is it still a one way function?

The function $h$ may not be one-way anymore.

We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way.
Assume $g$ is a one-way function that preserves size, and define $f$  on input $w=bx_1x_2$ in the following way,
$$f(bx_1x_2) = \begin{cases} g(x_1)\,x_2 & b=0 \\ x_1\, g(x_2) & b=1 \end{cases}$$
(assuming $b\in\{0,1\}$ and $|x_1|=|x_2|$.)
It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z_1z_2$ with $|z_1|=|z_2|=n$.
Then a possible preimage of $Z$ is
$$u=0 \,0^n \,\langle g(0^n)\oplus z_2\rangle$$
$$v=1 \, \langle g(0^n)\oplus z_1\rangle \, 0^n$$

because $f(u) = g(0^n)\, \langle g(0^n)\oplus z_2\rangle$ and
$f(v) = \langle g(0^n)\oplus z_1\rangle \, g(0^n)$ thus their XOR gives
exactly $z_1\,z_2$ as required.


How internet speed is manipulated at the physical level

This is a very wide topic indeed.

Basically, there are two ways to measure and control the speed of a connection: physical speed and logical speed.

Physical speed is determined by the technology, protocol and sometimes the physical conditions of the line. For example, a Fast Ethernet has a physical speed of about 100 Mbps, meaning that it could in theory transmit information at 100 Mbps at physical layer (brute bits). Most current optical fibre connections can reach several gigabit per second of brute speed.

In some case, the physical conditions may affect the physical speed for a particular link. In those cases, a initial negotiation when the link is established determines the maximum physical attainable speed. This is how old modem and current xDSL systems work.

On the other hand, there is a logical speed in the line, usually lower than the physical connection. In most current systems, at a logical (more abstract) level, the information travels in packets. Ethernet for example uses Ethernet packets, which usually is comparable to IP packets but not always. ATM networks use ATM packets that contains 53 bytes of data (48 of them are payload).

Now the relationship between both speeds: single packets travel at physical speed. If you have at home a GPON (fiber) connection, it may have a physical speed of 2.4 Gbps. Every GPON packet will travel at 2.4 Gbps. So how the speed provided to the user is limited? Limiting the packet rate at a higher level. Send a 1 Kbps packet every 1 ms, and you just limited the perceived speed to 1 Mbps. This can be easily done by software, allowing all kind of traffic control, burst control, congestion control, monitoring, etc.

Deploying a high-speed physical connection to provide low-speed logical speed services has several advantages:

The same physical link can serve for different logical speeds. Same technology makes the deployment easier and the manufacturing cheaper.
Logical speed can be modified to any value, at any time, simply by a change in the configuration of one or more devices. No need to replace equipment unless you need to provide more speed that the one supported by the physical layer.
The same physical link can be used by more people, and this is key. If you have a 1 Mbps service using fibre or cable connection, the physical layer would be unused between your packets. But it can be used for other user's packets, it is shared. And it is aggregated in the network hierarchy. A 10 Gbps link can carry thousands of low-speed link from thousands of users.

I hope this is clear and answers your question, but certainly it is just a very simplified overview. Feel free to ask more questions or clarifications.


Let's assume you have $n$ datasets, $x_k$ is the $k$th dataset. It's length we denote by $l_k$, its elements are $$x_k =\big\{x_k(1), x_k(2), \dots, x_k(l_k)\big\},$$
and its mean and variance are respectively
\begin{align}
\mu_k &= \frac{1}{l_k}\sum_{i=1}^{l_k} x_k(i),\\
\sigma_k^2 &= \frac{1}{l_k}\sum_{i=1}^{l_k} x_k(i)^2 - \mu_k^2.
\end{align}
Then, noting that $l_k\mu_k = \sum_{i=1}^{l_k} x_k(i)$:
\begin{align}
\mu &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^n\sum_{i=1}^{l_k} x_k(i)\\
\mu &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^nl_k\mu_k
\end{align}
and in similar fashion
\begin{align}
\sigma^2 &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^n\sum_{i=1}^{l_k} x_k(i)^2 - \mu^2\\
\sigma^2 &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^nl_k\left(\sigma^2_k + \mu_k^2\right) - \mu^2
\end{align}
When $l_k = N$ for all $k$ the above simplifies:
\begin{align}
\mu &= \frac{1}{n}\sum_{k=1}^n\mu_k\\
\sigma^2 &= \frac{1}{n}\sum_{k=1}^n\left(\sigma^2_k + \mu_k^2\right) - \mu^2
\end{align}
however when the datasets have different sizes the above does not simplify, and you need to take that into account.


How does Rabin fingerprint finds breakpoints (chunk boundary)?

I know I'm very late to this question, but I want to try and provide an answer for anyone who stumbles across this as I have. I went and deciphered the original paper by Michael Rabin, and found that the Rabin-fingerprint was designed to NOT be shift-resistant. In his paper (http://www.xmailserver.org/rabin.pdf) he used the fingerprint to detect any data-modification in files as the fingerprint would be different if any bit was changed. So, I have no idea why the LBFS paper is claiming to use fingerprinting for dynamic chunk borders because that's exactly what it is not meant for. Look for a different rolling hash if you want shift-resistant chunk borders. That being said fingerprinting would be a great way to check whether two chunks are the same or not.


Equivalence between alternative definitions of NP

The definition of $\text{NP}$ in terms of verification can be formally stated as follows:

  A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$:
  $$x \in L \iff \exists u: V(x,u) = 1.$$

  Here $u$ serves as a certificate.

To prove that the other definition $\text{NP}$ in terms of NTM implies the one above, you should construct such a polynomial verifier $V$ with the desired property. That is, for every $x \in L$, you need to find a certificate $u$ (you are not given a certificate $u$) such that $V(x,u) = 1$. Note that for every $x \in L$, there is a sequence of nondeterministic choices that makes the NTM $M$ accept $x$. This sequence is the certificate we need. What the polynomial verifier $V$ need to do is just to simulate the action of $M$ using these nondeterministic choices.


The reason has little to do with the problems in $\mathbf{P}$ and $\mathbf{NP}$ themselves; it is due to the computation models they describe. Recall that, if $A$ and $B$ are complexity classes, $A^B$ only really makes sense if $A$ can be expressed as a class of machines which can be equipped with oracle access (to the problems in $B$). $A^B$ does not make sense if $A$ cannot be expressed in terms of machines (which can use oracles).

This means the class $A^B$ is not obtained simply by taking the class $A$ (as a set of languages) and performing some operation on them using $B$ as a parameter (as the rather deceivingly simple "exponentiation-looking" notation would lead you to believe). Rather, it is a class belonging to a machine model of its own accord, namely the machine model of $A$ given oracle access to problems in $B$. In fact, it is rather surprising that the whole thing is well-defined, that is, that taking any two machine models for $A$ and granting both of them oracle access to $B$ yields the same class $A^B$ (actually, this only works if you are so careful as to give them both oracle access in a proper way).

That we can obtain relativizing results from certain (i.e., relativizing) proofs is, thus, even more surprising. As you can see, these are the sort of proofs which still work even if you replace the machine models with any closely-related ones (i.e., their oracle versions). Since they generalize in this way, they actually turn out to be very useful in that we can derive corollaries from them (for the respective relativized classes). An example of such a proof would be the inclusion $\mathbf{BPP} \subseteq \Sigma_2$.

In a nutshell, $\textbf{P}^A \neq \textbf{NP}^A$ does not really tell us anything about the relation of $\textbf{P}$ to $\textbf{NP}$ since $\textbf{P}^A$ (resp., $\textbf{NP}^A$) can be a class which is completely unrelated to $\textbf{P}$ (resp., $\textbf{NP}$). For an extreme example, consider what happens when $A$ is the class of languages which are (efficiently) reducible to the halting problem; in this case $\mathbf{P}^A$ contains languages which are not even recursively enumerable. And there are even classes which have been shown to be equal, but which do not relativize in almost any way (e.g., $\mathbf{IP}$ and $\mathbf{PSPACE}$).


Relations among different boolean approximations

The new parameters are polynomially related to the old parameters. In fact, for every $0<\delta,\epsilon<1$ it is the case that $d_{0,f,\epsilon} = \Theta_{\delta,\epsilon}(d_{0,f,\delta})$. This is proved in the same way that the usual relation regarding $d_{f,\epsilon}$ is proved, as detailed below.

Suppose we are given $0<\delta,\epsilon<1$. Let $g$ be some continuous function satisfying $g(0) = 0$ and $g(x) = 1$ for $1-\delta \leq x \leq 1+\delta$. The Weierstrass approximation theorem shows that there is some polynomial $G$ such that $|G(0)| \leq \epsilon/2$ and $|G(x)-1| \leq \epsilon/2$ for all $1-\delta \leq x \leq 1+\delta$. Let $G_0(x) = G(x) - G(0)$, so that $G_0(0) = 0$ and $|G_0(x)-1| \leq \epsilon$ for all $1-\delta \leq x \leq 1+\delta$. The polynomial $P = G_0(p_{0,\delta})$ has degree $(\deg G_0)d_{0,f,\delta}$ and satisfies $P(x) = 0$ whenever $f(x) = 0$, and $|P(x)-1| \leq \epsilon$ whenever $f(x) = 1$. This shows that $d_{0,f,\epsilon} \leq (\deg G_0) d_{0,f,\delta}$. Since $G_0$ only depends on $\delta,\epsilon$, this proves that $d_{0,f,\epsilon} = O_{\delta,\epsilon}(d_{0,f,\delta})$.


Every model of computation has a supported list of instructions, each associated with its time complexity. Thread handling is not a basic instruction in any model I'm aware of, but probably for practitioners of parallel computation, it is. The time complexity really depends on your viewpoint. If you're interested in optimizing the inner working of the operating system, then thread creation is not a basic operation at all, and its cost is associated with the algorithms implementing it. If you're interested in parallel computation, then probably thread creation is a primitive operation of unit cost. It all depends on the context.


van Emde Boas tree: why store max recursively?

take a look here he explains what you are saying , the theory does not guarantee the algorithm performance so what you pointed at to be weird is not but it is equivalent both cases and give the same $O(\log \log (u) )$ but it may differ in performance as you said .


Since $A \in \mathsf{NP} \cap \mathsf{coNP}$, there is a witness both for $x \in A$ and for $x \notin A$. An NP machine which wishes to (non-deterministically) find out whether $x \in A$ or not can guess the answer ($x \in A$ or $x \notin A$) and then verify it using a witness.