Nearest neighbour based on subjective human comparison - is this a thing?

Distance metric learning

It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items.  If the human tells you that A is more similar to B than to C, then you learn that $D(A,B) < D(A,C)$ (probably).  Based on many instances of this, you can learn a distance metric $D(\cdot,\cdot)$.  Then, you can use $k$-nearest neighbors with this distance metric.

Overview

How does distance metric learning work?  Well, you can do a search and you'll find a lot of material.  Basically, you identify some features that you think might be relevant.  So, let $f(A)$ denote the feature vector associated to $A$.  Then you want to learn a distance metric of the form

$$D(A,B) = d(f(A),f(B))$$

where $d : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ is the distance function that you want to learn.  There are various methods for this.  In one of them, we assume that $d$ takes the form

$$d(x,y) = (x-y)^\top A (x-y)$$

where $A$ is some positive semidefinite matrix that is to be learned.  The training set gives us comparisons of the form $d(x_A,x_B) < d(x_A,x_C)$, i.e.,

$$(x_A-x_B)^\top A (x_A-x_B) < (x_A-x_C)^\top A (x_A-x_C).$$

You could then form a convex optimization problem of the form

minimize $||A||_F$

subject to $A \succeq 0$ and $(x_A-x_C)^\top A (x_A-x_C) < (x_A-x_B)^\top A (x_A-x_B)$ for all $x_A,x_B,x_C$ in the training set.

Here $||A||_F$ is the Frobenius norm.  Also $A \succeq 0$ means that $A$ is positive semidefinite).  (This can be expressed by writing $A=M^\top M$ and using the entries of $M$ as your unknowns, though sometimes it is easier to leave it in the form $A$.)  Then we apply some algorithm for convex optimization to learn $A$ or $M$.

That's one example of a method; there are many others.  For instance, you might add a margin to the inequality above, and require that $d(x_A,x_B) < d(x_A,x_C)-1$ (so they are well-separated).

The effectiveness will be partly determined both by the metric learning method you use, but the set of features you come up with are also extremely important.  You'll want to use your domain knowledge about what attributes of items might be relevant or helpful in determining similarity.  If you have good features,  you'll probably find that distance metric learning is more effective.

To learn more

There are many schemes for distance metric learning.  A websearch and a search on Google Scholar should turn up a bunch of candidates.  You want to learn a distance metric from relative comparisons.  See also https://en.wikipedia.org/wiki/Similarity_learning.


A connected forest is a tree (as well as a forest).

The terms spanning forest and spanning tree refer to an ambient graph. Given a connected graph $G$, a spanning tree is a subset of the edges of $G$ (spanning all vertices) which forms a tree. Similarly, if $G$ is a graph with $c$ connected components, then a spanning forest is a subset of the edges of $G$ (spanning all vertices) which is a disjoint union of $c$ trees.


What happens during the DFA reversal construction if the initial state is final?

Yes.  It will be both initial and final in the reversed automaton.

(Separately: If you want the reversed automaton to be a DFA, you may have to be a bit careful about your construction for reversing a DFA, as DFAs are not allowed to contain epsilon transitions.)


Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n)

The problem with your proof is in the definition of $n_0$. The function $n(g)$ can be unbounded (as a function of $g$).

A much simpler proof would be to take $g = f$.


What's the time complexity of this function?

Denote the time complexity of $f$ on inputs $a,k,n$ by $T(k,n)$ (the time complexity doesn't depend on $a$ in your model). The time complexity satisfies the recurrence
$$
T(k,n) = (n-k+1)T(k+1,n) + \Theta(n-k+1).
$$
with base case $T(n,n) = \Theta(1)$. Define
$$
S(k,n) = \frac{T(k,n)}{(n-k+1)!}.
$$
Then $S(n,n) = \Theta(1)$ and for $k < n$,
$$
S(k,n) = S(k+1,n) + \Theta\left(\frac{1}{(n-k)!}\right).
$$
It follows that
$$
S(k,n) = \Theta\left(\frac{1}{(n-k)!} + \cdots + \frac{1}{1!} + 1\right) = \Theta(1),
$$
and so $T(k,n) = \Theta((n-k+1)!)$.
If you take $T(n) = \max_{1 \leq k \leq n} T(k,n)$, then indeed $T(n) = \Theta(n!)$.


What's the point of Indirect Addressing?

Indirect addressing is possible without instructions that implement it explicitly. These instructions exist for our convenience, and not just for reaching a position that doesn't fit the address space of a direct addressing instruction (although this will become quite natural if your program is big enough): that's how we implement subprograms and arrays, for instance.


Simple question about grammar derivations

Actually you have to study the working of a parser in detail to get the answer to your question.

Parsers can be top down or bottom up. In top down parsing, we try to derive the input string from the start symbol. In bottom up parsing, the reverse procedure is applied, i.e. we try to reduce the input string to the start symbol.

Let me try to answer your question by explaining the working of recursive descent parser, a general top down parser.

Recursive descent parser will choose the productions based on the order in which they are specified. I will explain with an example.

The grammar given is

    S-> aAB | bAB
    A-> d | a
    B-> b

Let the input be

    bab

The input pointer points to the first symbol 'b'. The recursive descent parser will start with start symbol S. The working is as follows

    S-> aAB

Whenever a terminal symbol is obtained, it is checked for match with the current input symbol. Input symbol 'b' doesn't match with the terminal 'a'. So the parser will backtrack and choose the next production

    S->bAB

The terminal symbol matches with the input. Hence input pointer is advanced and it points to 'a'. Next substitute for A.

    S-> bdB

Input symbol and the obtained terminal does not match. So backtrack and choose the next production for A.

    S-> baB

Now a match is obtained and B is replaced with its production

    S->bab

Thus input is successfully parsed.
The steps in derivation can be summarised as

    S-> aAB (backtrack)
     -> bAB
     -> bdB (backtrack)
     -> baB
     -> bab


Decision tree and information-theoretic lower bound

No.  The outcome is the median, not the sorted list. Thus, there are only 3 possible outcomes, not 3! outcomes.  The information-theoretic lower bound says that if there are N possible outcomes, then it takes at least $\lceil \lg N \rceil$ comparisons.  (Proof: given $k$ comparisons, you can only produce $2^k$ different outcomes.)  Here $N=3$.


Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2): You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1  h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T2′ of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

v ← root(T1)
h′ ← h1
  whileh′ >h+1do
  if balance factor (v) = -1 then h′ ← h′ − 2
  else h′ ← h′ − 1
  v ← rightchild(v)

This takes O(h1) time.
Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left subtree is the subtree rooted at v and whose right subtree is T2′.
Note that this is a valid binary search tree, since all the keys in the subtree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T2′. The balance factor of the root of this new tree is h−h′, which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h′ +1, which is 1 bigger than v’s height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm.
Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n)

you can find more answer in this question :
Merging of height balanced trees

and this algorithm can help you for more details :
A Fast Merging Algorithm MARK R. BROWN


Maximal cliques in a multipartite graph - efficient?

A maximal clique and a maximum clique are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$.

You mention bipartite graphs, but the complete $k$-partite graph is not bipartite if $k \geq 3$ (but it is for $k=2$). A bipartite graph contains no triangles, so in such a graph a maximum clique has size (at most) 2, so an efficient algorithm can just return a single edge.

Let $G = K_{n_1,\ldots,n_q}$ for positive integers $n_1,n_2,\ldots,n_q \geq 2$. You can verify that $G$ has maximum clique size $q$, and a total of $n_1 \cdot n_2 \cdots \cdot n_q$ such cliques. An algorithm for enumerating all of them reduces to basic combinatorics (pick one vertex, then how many choices for the remaining vertices do you have when forming a clique?)


Rearrange a sequence of real numbers to satisfy polynomial inequalities

Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs).

Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. Pick the first $n$ primes larger than $7$, $p_1,\ldots,p_n$. We construct the following sequence $\mathbf{a}$:

For each edge $(i,j)$, the numbers $p_i,p_j,p_{ij}$
For each vertex $i$, the numbers $p_i,p_i^3$
$m$ copies of $3$
$n-m$ copies of $5$
$9n/2$ copies of $2$
$11$ copies of $7$

Note that some numbers appear more than once. The intended solution sequence consists of eleven copies of $7$ followed by $n$ segments of length $12$ of the following two forms:
either
$$ 5,p_i,p_i^3,2,2,2,2,2,2,2,2,2 $$
where $1 \leq i \leq n$, or
$$ 3,p_i,p_i^3,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3 $$
where $1 \leq i \leq n$ and for $\alpha \in \{1,2,3\}$,
$$ x_\alpha,y_\alpha,z_\alpha = 2,2,2 \quad \text{or} \quad p_i, p_ip_j, p_j \text{ for some edge } (i,j).$$
A sequence of that form encodes a vertex cover given by the vertices appearing in the second position in segments of the second form. It should be clear that such a sequence exists if and only if a vertex cover exists. It remains to show how we can test that a sequence is of that form using a single polynomial $f$ which is "run" on all chunks of length $12$.

We let $f = -f'$, where the function $f'(u,v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3)$ is a non-negative function which attains zero on exactly inputs of the following forms:

$3 \in \{v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3\}$
$5 \in \{v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3\}$
$u = 5$, $w=v^3$ and $x_1=y_1=z_1=x_2=y_2=z_2=x_3=y_3=z_3=2$
$u = 3$, $w=v^3$ and for each $\alpha \in \{1,2,3\}$, either $x_\alpha=y_\alpha=z_\alpha=2$ or $x_\alpha=v$ and $y_\alpha=x_\alpha z_\alpha$

This polynomial can be constructed using the following three rules:

A condition $I = J$ is represented by $(I - J)^2$
Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \lor C_2$ is represented by $C_1 C_2$
Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \land C_2$ is represented by $C_1 + C_2$

Let $\mathbf{b}$ be any permutation of $\mathbf{a}$ for which your condition holds. Since $f'$ is non-negative, it must be that one of the above conditions holds for each segment of length $12$. In particular, any segment of length $12$ must contain $3$ or $5$ somewhere. Considering the number of these compared to the length of the sequence, we see that its general form is: eleven arbitrary elements followed by $n$ segments starting with $3$ or $5$. Each segment starting with $5$ is of the form
$$ 5,q,q^3,2,2,2,2,2,2,2,2,2. $$
We conclude that $q = p_i$ for some $1 \leq i \leq n$. Each segment starting with $3$ is of the form
$$ 3,q,q^3,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3. $$
As before, $q = p_i$ for some $1 \leq i \leq n$. Furthermore, for each $\alpha \in \{1,2,3\}$, either $x_\alpha = y_\alpha = z_\alpha = 2$ or $x_\alpha = p_i$ and $y_\alpha = p_i z_\alpha$. In the latter case we conclude that $z_\alpha = p_j$ and $y_\alpha = p_ip_j$ for some edge $(i,j)$.

In both cases, none of the elements in the segments are equal to $7$, and we conclude that the first eleven elements in the sequence must be $7$. Let $S$ be the set of $i$ such that there is a segment of the form $3,p_i,\ldots$. Since there are exactly $m$ copies of $3$, $|S| = m$. For every edge $(i,j)$, the number $p_{ij}$ appears somewhere, and the only legal place is a $3$-segment. We conclude that $S$ is a vertex cover of length $m$.

This shows that if your condition holds then the graph has a vertex cover of size $m$. Conversely, if the graph has a vertex cover of size $m$ then we can construct a sequence satisfying your condition by assigning each edge to one of the vertices covering it. This proves the validity of the reduction. The reduction is also polynomial time (note that the primes $p_1,\ldots,p_n$ can be found using brute force), showing that your problem is NP-hard, and so NP-complete.


Complexity of brute force primality test in the number of digits

In the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$

You are on the right track. The upper bound $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$ is pretty good.

We can simplify the formula a little bit and strength the result a little bit.

Proposition. The number of integers between $2$ and $\sqrt n$ (inclusively) is $\Theta(10^{\frac p2})$, where $p$ is the number of digits of $n$ in base 10.

Proof. Since $p$ is the number of digits of $n$ in base 10, we know $10^{p-1}\le n<10^p$. The number of integers between 2 and $\sqrt n$ is $\lfloor\sqrt n\rfloor-1$. I will leave the rest of the proof to you.


Need help understanding the tuple relational calculus

From Wikipedia:

A tuple is of the form $T=(D,R,h)$ where $D$ is the domain, $R$ is a set of relation names, and $h$ is a mapping that associates a column name to each relation in $R$. To represent a tuple, we can see $D$ as the set of keys, and $R$ the table associated with those set of keys, and $h$ the column names of the table.


Typing contexts are the way to remember previously declared variables when type-checking a program/term. The rule for term abstraction usually is something like
$$\dfrac{\Gamma,x:A\vdash e : B}{\Gamma\vdash \lambda x.e : A\to B}$$
In the conclusion, $x$ is not in $\Gamma$ yet. At this point, $x$ is declared to be the variable of the function $\lambda x.e$ and this variable appears in $e$. So, $x$ is a free variable in $e$. The typing rule above expresses that $\lambda x.e$ is of type $A\to B$ under context $\Gamma$ iff $e$ is of type $B$ under context $\Gamma,x:A$. So in the premise of the rule, we are type-checking the body of $\lambda x.e$ (which is $e$), but we need to remember that $x$ (which appears free in $e$) is a variable of type $A$.


Time complexity of functions that call each other

To help with your intuition, change the code by substituting the code for bar into foo:

int foo(int x)
{
  if(x < 1) return 1;
  else if (x < 2) return 2; // foo(0) + bar(1), x = 1
  else return foo(x-1) + foo(x-1) + bar(x/2);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

So now it is obvious that T (x) ≥ $Θ(2^x)$, since foo (x) does two recursive calls to foo (x-1). Also makes it obvious that the result is foo (x) ≥ $Θ(2^x)$, and that result can be calculated in linear time.


How to find highest normal form of a relation, given its functional dependencies

In your example $C$ is derived attribute from $A, B$, but none of: $D, E, F, G$ is more dependent on $C$ than $A, B$, or solely functionaly dependent on $C$, so there is no transitive dependency. Since you have 2NF it is in 3NF.

For BCNF it is sufficient to be in 3NF and do not have overlapping candidate keys, which you do not have, hence it is in BCNF.


Finding the element that occurs the most in a very large file

When you have a really large file and many elements in it, but the most common element is very common -- occurs $> 1/k$ fraction of the time -- you can find it in linear time with space $O(k)$ words ( the constant in the $O()$ notation is very small, basically 2 if you don't count the storage for auxiliary things like hashing). Moreover, this works great with external storage, as the file is processed in sequence one element at a time, and the algorithm never "looks back". One way to do this is via a classical algorithm by Misra and Gries, see these lecture notes. The problem is now known as the heavy hitters problem (the frequent elements being the heavy hitters).

The assumption that the most frequent element appears $> 1/k$ fraction of the time for $k$ a small number may seem strong but it is in a way necessary! I.e. if you will have sequential access to your file (and in case the file is huge random access will be too expensive), any algorithm which always finds the most frequent element in a constant number of passes will use space linear in the number of elements. So if you don't assume something about the input you cannot beat a hash table. The assumption that the most frequent element is very frequent is maybe the most natural way to get around the negative results.

Here is a sketch for $k = 2$, i.e. when there is a single element that occurs more than half the time. This special case is known as the majority vote algorithm and is due to Boyer and Moore. We will keep a single element and a single count. Initialize the count to 1 and store the first element of the file. Then process the file in sequence:

if the current element of the file is the same as the stored element, increase the count by one
if the current element of the file is different from the stored element, decrease the count by one
if the updated count is 0, "kick out" the stored element and store the current element of the file; increase the count to 1
proceed to the next element of the file

A little bit of thinking about this procedure will convince you that if there exists a "majority" element, i.e. one that occurs more than half the time, then that element will be the stored element after the whole file is processed.

For general $k$, you keep $k-1$ elements and $k-1$ counts, and you initialize the elements to the first $k$ distinct elements of the file and the counts to the number of times each of these elements appears before you see the $k$-th distinct element. Then you run essentially the same procedure: an element's count is increased each time it is encountered, all element counts are decreased if an element that is not stored is encountered, and when some count is zero, that element is kicked out in favor of the current element of the file. This is the Misra-Gries algorithm.

You can of course use a hash table to index the $k-1$ stored elements. At termination, this algorithm is guaranteed to return any element that occurs more than $1/k$ fraction of the time. This is essentially the best you can do with an algorithm that makes constant number of passes over the file and stores only $O(k)$ words.

One final thing: after you found $k$ candidate "heavy hitters" (i.e. frequent elements), you can make one more pass over the file to count the frequency of each element. This way you can rank the elements between each other and verify whether all of them occur more than $1/k$ fraction of the time (if there are less than $k-1$ such elements, some of the elements returned by the algorithm might be false positives).


Minimum Weight Directed Subgraph ensuring all pairs reachability?

This problem is a generalized version of the famous Minimum Spanning Strong Subdigraph or MSSS [1]. This problem is NP-hard and there are several heuristic algorithms for it. You may look at the reference given in this solution and the related papers to find out more about this problem.

Note that this problem itself is a simplified version of Minimum Equivalent Graph of a Digraph [2]. Therefore, there are some algorithms that you can use as a heuristic for this problem.

[1] Bang-Jensen, Jorgen, Jing Huang, and Anders Yeo. "Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs." SIAM Journal on Discrete Mathematics 16.2 (2003): 335-343.

[2] Martello, Silvano, and Paolo Toth. "Finding a minimum equivalent graph of a digraph." Networks 12.2 (1982): 89-100.


Is finding a path with more red vertices than blue vertices NP-hard?

Your solution does not work because Dijkstra and Bellman-Ford cannot interpret "simple path" feature. And they will indeed fall in any negative cycle.

I think the best to show NP-completeness, is to use the Hamiltonian path problem. Let's take a graph $G'$ of $N$ red vertices.

Then you build a graph $G$, adding $s$, $t$ and $N-1$ blue vertices to $G'$. You first chain with edges all the blues vertices from the source to the last blue one ($s$->$b_1$->$b_2$->...->$b_{N-1}$). Then you put edges from $b_{N-1}$ to every red vertex and an edge from every red vertex to $t$.

So a single path from $s$ to $t$ passes necessarly through all blue nodes ($N-1$) and then have to pass to all red nodes ($N$) to answer to

Is there a simple path in $G$ from $s$ to $t$ with more red than blue vertices ?

which is thus like answer to:

Is there an Hamiltonian path in $G'$

So your problem is indeed NP-complete.


Showing that the language of graphs and nodes on an odd cycle is in NL

The question is ambiguous. Specifically, it is not clear what "different vertices that appear in that cycle" means. It can mean two things (1) the size of the set of nodes that appear in the path, or (2) the total number of nodes in that path, i.e., the length of that cycle (minus 1).

If the interpretation is (2), then the language is clearly NL:
you perform a random walk (of length $\le n$), counting the number of nodes you see. If you get back to $v$ and the number of nodes is odd, you accept, otherwise you reject.

If the interpretation is (1), I don't see an immediate way to show it is in NL.


I'm not sure I understand why do you need a priority queue.

The best algorithm should be as follows (pseudocode):

1) count the words
2) sort them by count

Counting each word you can loop through each word and update the count in the hash table for each word.    This is done $n$ times and you need $O(1)$ for accessing + $O(1)$ updating the hash table thus $O(n)$.

Sorting is $O(n \log n)$. Thus the complexity is $O(n \log n)$.


The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm

In fact the algorithm determines whether the vertex $k$ is "intermediate" on the path from $i$ to $j$.  If indeed $d_{ik}^{(k-1)} + d_{kj}^{(k-1)} < d_{ij}^{(k-1)} $ during the computation we know that (up to the first $k$ vertices) the vertex $k$ is needed to obtain a shorter path between $i$ and $j$.

So, in my opinion, the algorithm takes into account the structure of the graph!


Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

To write the profit as a mathematical expression, you need to set up a little more notation for the buys and sells. Let $x[1], \ldots, x[n]$ be the stock prices on days $1, \ldots, n$. For each buy and sell, let $b$ denote the day on which the stock is bought, and $s$ the day on which it is sold. The problem says that we must have $1 \leq b < s \leq n$. The profit from this single transaction is $P = x[s] - x[b]$.
However, the problem allows many buys and sells, say $(b_1, s_1), \ldots, (b_k, s_k)$ for some numbers which must satisfy $$1 \leq b_1 < s_1 < b_2 < s_2 < \cdots < b_k < s_k \leq n.$$
The total profit from these $k$ transactions is
$$ P = \sum_{i = 1}^k \left(x[b_i] - x[s_i]\right). $$
Of course the tricky part is that you don't know ahead of time what $k$ should be, so you're not only trying to optimise over the $b_i$ and $s_i$ variables, but also $k$.


There are many kinds of NIM. The one in the picture is a rather classic example. Take either one or two tokens, the one who takes the last token looses.

Does not sound like the version you suggest. Your game does not state what happens with the divided heaps?


Comparing different asymptotic notations

Well, we know how the algorithm C running time grows - it's linear, and it's two-side (lower and upper) bound.

However there is still not enough information to choose the best (meaning: fastest in practice) algorithm here, because:

We know only upper bounds for algorithms A and B - they might be more efficient than C actually, we just don't know that yet.
We don't know constants, hidden in the $\Theta$ bounds - they might make the algorithm C less practical than A or B for limited problem size.

Using the given information we can say only that for some sufficiently large problem size the algorithm C might win over algorithms A and B.


Which "entity" is working at more deeper level than Characters of a program?

There are many pieces of software involved in rendering an "A" when you type it in to a program like a text editor.

First, the key press is handled by the hardware of the keyboard, which sends a signal to the OS's keyboard driver. This is where stuff like the
state of the shift key and caps lock get noted (though the
information about which modifier keys are pressed will usually just
be passed along with the information about the key pressed, rather
than "a" turning into "A" just yet).
The key press information next gets passed to the window manager
(which is usually part of the OS), to determine which program has
"keyboard focus" at the moment. If nothing has focus, the window
manager might discard the key press here (though it might also
intercept other presses, like ALT+Tab).
Next the active program likely gets a key-press event. Often the
program's event processing happens in a library provided by the
window system, though what it will do with the events after they
happen is up to the application itself.
An editor program will likely interpret a key press like "A" as input
for a file you have open. It will add the character to its memory
buffer representing the file's contents. This may be the first place
where the ASCII representation for "A" becomes relevant, as keyboards
and windowing systems often use their own codes for key presses. (Note though that a modern editor will probably use some encoding of Unicode, rather than ASCII to represent text. This adds some extra complication, but makes it possible to handle text in any language, not only English.)
Now the program has to draw the "A" to the screen. First it will
probably have to do a bunch of calculations to determine how it wants
to lay out all its text. Many editors wrap long lines of text, for
instance, which can be pretty complicated to get right.
Once the program has decided exactly where on the screen it wants to
put each part of its text, it will render them using a font. The font
describes what each glyph should look like (this is also very
complicated). The font render (which is often part of a library
provided by the OS or window manager, though an application can do
its own rendering if it really wants to) transforms the "A" to a
specific set of pixels.
Next, the pixels for the "A" (along with those for the other text,
and the rest of the editor's UI) get sent to the graphics driver.
Other programs may also be sending their own pixels if other windows
are visible alongside the editor. The window manager will usually
also have some parts of the screen that it manages itself (like the
taskbar, but sometimes also the borders of the windows).
The graphics driver sends on all the data to the hardware graphics
card in the machine. Some PCs these days (especially laptops) don't
have a dedicated graphics card, but they'll have a chip on the
motherboard that does essentially the same thing. The graphics card
will assemble all the graphics into a buffer representing all the
pixels of the screen. It will send the contents of that buffer to the
monitor every time it needs to redraw the screen (usually 60 times
per second, though other refresh rates are becoming more common).

The steps above are intended to be fairly general. Typing a key into a specific program on your computer may not have exactly the steps I describe (it could have more or fewer). For instance, if your editor is a console application rather than a graphical one, you may not have any window manager involved, and very basic fixed-width font rendering might be done directly by the hardware of the graphics card.

The exact boundaries between some of the layers may also be hard to distinguish in some cases, especially when the application is using libraries provided by the OS, window manager or graphics driver for some of the steps (like the event loop and font rendering).


Generically, these are sometimes called subset/containment dictionaries. The fact that you had partial matching in your question (but deleted it) is actually not a coincidence, because subset/containment queries and partial matching are equivalent problems for sets.

You probably want to use an UBTree (unlimited branching tree) for this; it's basically a modified trie. See Hoffmann and Koehler (1998) for more details.

You could also have a look at the more recent set-trie data structure proposed by Savnik (2013) for the same purpose. (If you miss the color in the graphs in that preprint paper and don't have access to the official Springer publication [in which the colors aren't missing], there's precursor to that paper which has almost the same graphs/info and no missing colors.)

Both papers (Hoffmann & Koehler, and respectively Savnik) have experimental results, so you can have some idea what they can handle in practice. Both seem to handle data sets with a cardinality of U around 1M.

If you somehow have TCAM hardware (or the money for it), there's a way to leverage that for subset/superset queries. You can actually do both subset/superset queries in parallel assuming you have enough TCAM words (2x |U|).
Since TCAM words can be configured to be 144-bit wide, you and you have only 95 bits/letters to test, you wouldn't even need to bother with Bloom/hashing, you'd have an exact test using TCAM; this is trivial enough I'll even say here how: every {0, 1} bit-vector corresponding to every set in your U is simply turned into a {0, *} vector for subset queries and to a {1, *} vector for superset queries.

A more general problem tackled in ETI (no free copy, sorry) is finding a set with given similarity measure. For example, the similarity measure can be $J(Q,S)=\frac{|Q\cap S|}{{|Q\cup S|}}$ and the query for a given $Q$ can be to find all $S$ (in the database) with $J(Q,S)\geq 0.3$. Both the constant and the similarity measure are user-definable as a predicate in ETI. (The $J$ given as example here is called the Jaccard index.)


Integer Linear programming formulation if then condition

you can introduce a binary variable z verifying the following constraints :

(A-1) <= 12*z
z<= 0.5*A
-(1-z)*12 <= B-A <= (1-z)*12
-12*z <= B <= 12*z


How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal?

If you delete all subsets in $B$ that contain no string from $A$, then this is exactly the (Minimum) Set Cover problem, which is NP-hard, meaning that almost certainly no efficient (that is, polynomial-time) algorithm exists.

Testing each possible combination can be done in $O(m2^n)$ time if there are $n$ sets in $B$ and $m$ elements in $A$, which is better than factorial time.  (We don't care about the order of the subsets we select.)


Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear?

Below you can find a (non-optimized) python implementation of the algorithm. First, I give some hints explaining why this implementation runs in linear time. These hints assume that you know what is roughly going on, and that you have read the code.

The algorithm runs up to two threads at any given time. Initially only one thread is run. Whenever reaching a decision point (a clause with two unassigned variables), it kills the other thread and "forks" the current thread into two. The current thread is killed if it reaches an unsatisfiable clause, and if both threads are dead then the algorithm returns "unsatisfiable".

The algorithm is careful to maintain the following properties:

The two threads are run in lockstep, each step running in $O(1)$ (apart from forking).
Forking takes time $O(t)$, where $t$ is the number of steps since the last fork (or since the start or the algorithm).
The total running time of all non-killed threads is $O(n+m)$ (where $n$ is the number of variables and $m$ is the number of clauses).

These properties guarantee that the main body of the algorithm runs in time $O(n+m)$. The initialization step also runs in time $O(n+m)$, and so the entire algorithm runs in time $O(n+m)$.

There are two somewhat non-trivial implementation details:

Maintaining the partial assignments for the threads. Each thread needs to maintain a partial assignment. Upon reaching a decision point, this partial assignment needs to be forked. A naive implementation would take $O(n)$ to copy the partial assignment. The implementation below uses a two-tiered strategy to handle this: there is a reference assignment which is common to both threads, and there is a per-thread addition. The implementation also keeps track on which variables were set during each thread, and uses this to maintain this data structure.
Handling the repercussions of an assignment. Whenever a variable is assigned, we need to check on all other clauses containing this variable. This is done by precalculating all clauses containing each variable, and keeping a stack of "clauses to check" for each thread. Since a variable could appear in many clauses, we copy one clause to the stack in each iteration. This forces us to keep a state machine (with two states).

The code below accepts two parameters: n is the number of variables, and clauses is a list of pairs of instances of Literal. For example, to check whether the 2CNF $(x_0 \lor \lnot x_1) \land (\lnot x_0 \lor x_2)$ is satisfiable, run

  EIS(3, [(Literal(0,True),Literal(1,False)), (Literal(0,False),Literal(2,True))])

Here is the complete code:

class Literal:
    def __init__(self, var, value):
        self.var = var
        self.value = value
    def __repr__(self):
        if self.value:
            return '+x%d' % (self.var,)
        else:
            return '-x%d' % (self.var,)

def EIS(n, clauses):
    """
Solve a 2SAT formula 'clauses' on 'n' variables.
The formula is given as a list of pairs of Literal.
Returns a satisfying assignment or None if formula is unsatisfiable."""
    ## construct for each variable a list of clauses it appears in
    clauses_by_variable = [[] for _ in range(n)]
    for index,clause in enumerate(clauses):
        for literal in clause:
            clauses_by_variable[literal.var].append(index)
    ## initialization
    # reference assignment
    reference_assignment = [None for _ in range(n)]
    # thread variables:
    # thread is alive
    thread_live = [True, False]
    # thread is currently updating the stack (either (var,index) or None)
    thread_stack_update = [None, None]
    # new assignment (as partial assignment)
    thread_assignment = [[None for _ in range(n)] for _ in range(2)]
    # variables assigned in this thread
    thread_assigned_variables = [[] for _ in range(2)]
    # next unhandled clause
    thread_next_clause = [0, 0]
    # stack of clauses to handle
    thread_stack = [[], []]
    ## main loop
    while True:
        # check whether any threads are alive
        if all(not thread_live[thread] for thread in range(2)):
            return None
        # advance all live threads
        for thread in range(2):
            if not thread_live[thread]:
                continue
            # check whether thread is updating the stack
            if thread_stack_update[thread] is not None:
                var, index = thread_stack_update[thread]
                if index < len(clauses_by_variable[var]):
                    thread_stack[thread].append(clauses_by_variable[var][index])
                    thread_stack_update[thread] = var, index+1
                else:
                    thread_stack_update[thread] = None
                continue
            # determine next clause to handle
            if len(thread_stack[thread]) > 0:
                next_clause = thread_stack[thread].pop()
            else:
                next_clause = thread_next_clause[thread]
                thread_next_clause[thread] += 1
            # check whether we have finished handling all clauses
            if next_clause == len(clauses):
                assignment = []
                for var in range(n):
                    value = thread_assignment[thread][var]
                    if value is None:
                        value = reference_assignment[var]
                    if value is None:
                        value = True # arbitrary value
                    assignment.append(value)
                return assignment
            # otherwise, read clause and current assignment to variables
            clause = clauses[next_clause]
            ref_values = [reference_assignment[clause[i].var] for i in range(2)]
            thr_values = [thread_assignment[thread][clause[i].var] for i in range(2)]
            curr_values = [ref_values[i] if thr_values[i] is None else thr_values[i] for i in range(2)]
            # check whether current clause is already satisfied
            if any(clause[i].value == curr_values[i] for i in range(2)):
                continue
            # check whether current clause is unsatisfiable
            if all(clause[i].value != curr_values[i] and curr_values[i] is not None for i in range(2)):
                # kill current thread
                thread_live[thread] = False
                continue
            # check whether there is a forced assignment
            if curr_values[0] is not None:
                forced = clause[1]
            elif curr_values[1] is not None:
                forced = clause[0]
            elif clause[0] == clause[1]: # clause contains two identical literals
                forced = clause[0]
            else:
                forced = None
            # handle forced assignment, if any
            if forced is not None:
                thread_assigned_variables[thread].append(forced.var)
                thread_assignment[thread][forced.var] = forced.value
                thread_stack_update[thread] = (forced.var,0)
                continue
            ## we have reached a decision point
            # update reference assignment
            for var in thread_assigned_variables[thread]:
                reference_assignment[var] = thread_assignment[thread][var]
            # undo assignments in threads
            for thr in range(2):
                for var in thread_assigned_variables[thr]:
                    thread_assignment[thr][var] = None
            # initialize threads
            for thr in range(2):
                thread_live[thr] = True
                thread_assigned_variables[thr] = [clause[0].var]
                thread_assignment[thr][clause[0].var] = [False,True][thr]
                thread_stack[thr] = []
                thread_stack_update[thr] = (clause[0].var,0)
                thread_next_clause[thr] = next_clause


Does NTIME($n^\alpha$) $\subset$ EXPTIME imply NP $\subset$ EXPTIME?

Upon reflection this is an easy consequence of the Time Hierarchy Theorem.

NTIME$(n^\alpha) \subseteq$ TIME$\left(2^{n^\alpha}\right)$ by brute force
TIME$\left(2^{n^\alpha}\right) \subset$ TIME$\left(2^{n^{2\alpha}}\right)$ by the Time Hierarchy Theorem
TIME$\left(2^{n^{2\alpha}}\right) \subseteq$ EXPTIME obviously

So there's nothing new here.


The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those sequences would cross the join. So, for a linear sequence, you need to repeat the first three items at the end, giving $10\,003$, improving on the obvious solution of length $40\,000$.

(Thanks to PålGD for pointing out the issue with cyclicity.)


Yes, it is true that there exist two edge-disjoint paths between any two vertices in a connected bridgeless graph.

Define a closed trail as a trail whose last vertex is its first vertex. Note, a trail contains two edge-disjoint paths between any two of its vertices.

Trail combining lemma. Let $G$ be a graph.  Suppose a closed trail passes vertex $v$. Another closed trail passes vertex $u$. If those two trails share one vertex, there is a closed trail that passes both $u$ and $v$.

Proof. You can convince yourself easily by drawing a few situations. Done.

Let us prove the following proposition.

A graph is connect and bridgeless if and only if any two vertices are included in a closed trail.

Proof.

"$\Leftarrow$": Obvious.

"$\Rightarrow$": Suppose $G$ is connected and bridgeless. $v$ and $w$ are two vertices.

Let $$T_v=\{u : u \text{ is a vertex of } G \text{ such that there is closed trail that passes }v\text{ and } u\}.$$
Suppose $u\in T_v$ and $s$ be a neighboring vertex of $u$, i.e., $\{u,s\}$ is an edge.

There is a closed trail that passes $v$ and $u$ by the definition of $T_v$.
There is a closed trail that passes $u$ and $s$, since edge $\{u,s\}$ is not a bridge.

Thanks to the lemma, we have a closed trail that passes $v$ and $s$. In other words, $T_v$ contains all neighborhoods of all its vertices. That means $T_v$ (with all edges between its points) is a connected component, which must be $G$ itself. In particular, there is a closed trail that passes $v$ and $w$. Proof is complete.

A very similar characterization of bridgeless connected graphs is Robbins' theorem. If $G$ is connected and bridgeless, that theorem says we can choose a direction for each edge of $G$, turning it into a directed graph that has a path from every vertex to every other vertex.


Polynomial reduction from unbounded knapsack problem to general integer programming

Hint: What do you know about the complexity class of the unbounded knapsack problem?  Is it in P?  Is it NP-hard?

Now what do you know about the complexity class of LP?  Is it in NP?

Think a bit about your answers to those two questions and see if that helps you see one path forward.  (There's a short proof of your desired result that doesn't require much detailed mathematics.)

Once you've figured that out:  if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...)

Once you've worked out that: you should now know there is a reduction. So look at the proofs of each of the steps of reasoning I walked you through. Review these proofs. Those proofs will construct a reduction for you. So, work out what reduction is implicit in the proofs. You should be able to take it from here!


How memory remapping of physical address space that is above 4GB RAM works?

I am not entirely sure what your question is but I will try to answer. I think your confusion comes from the fact that some peripherals (typically PCI and APIC) use memory-mapped registers that "steal" memory from the physical address space (the famous 1GB hole described in the blog post). But those memory-mapped registers do not use RAM at all. They simply steal part of the address space and thus some physical addresses that would normally refer to RAM now serve another purpose. Now if you only have 4GB of RAM and the RAM is mapped at 0, a peripheral at 0x10000012C cannot create a hole in the RAM address space because the RAM is mapped from 0 to 0xffffffff. I attached a picture that hopefully makes this clearer.

In summary: when we say "memory-mapped register" what we really mean is "physical-address-space-mapped register", this has nothing to do with RAM.

Note, however, that any peripheral (memory-mapped or not), could also use some RAM, through DMA. But this is a totally different thing because by doing so it does not steal any physical address (and thus does not create a hole).

Finally note that all of this is simplified anyway because there isn't necessarily a unique physical address space in the system, each device may have a different view of the system. See 1 for a relatively clear explanation. Thus in the picture above, I am really referring to the CPU's physical address space.

1: Not your parents’ physical address space, Gerber et al, PDF


As I stated on the CSTheory post, this is solved via maximum matching. The following should give enough intuition to show that each agent $a_i$ has a $q_i$-matching iff a transformed graph $G'$ has a matching. First, construct the graph $G$. Now, for each agent $a_i$ and quota $q_i$, make a new graph $G'$ that has $q_i$ copies of $a_i$. That is to say, if agent $a_i$ has quota $q_i = 3$, make 2 new nodes $a_i', a_i''$ that have the same tasks as $a_0$.

Here is an illustration to help. Supposed we have the complete bipartite graph $K_{2,3}$ where agent $q_1 = 2, q_2 = 1$.

Original graph $G$, and modified graph $G'$:

We see that agent $a_1$ has two copies in the new graph $G'$, while agent $a_2$ maintains just his lone copy. Solving for the maximum matching in $G'$ and then merging all copies of an agent to the original and you will have your best possible assignment. Since the edges are unweighted, one possible solution is (and merged solution):


Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?

The complexity of the square-root sum problem is a long-standing open question. The stumbling block is that, although we know how to compute square roots efficiently, we don't know if it's possible to determine whether $\sum_i \sqrt{x_i}\leq k$ by evaluating only a polynomial number of bits of each square root.

The specific problem with the algorithm you propose in the question is that the phrase "compute the square root of each value" is underspecified. Any irrational square root (e.g., $\sqrt{2}$) requires computing an infinite number of bits, so you need to state what precision you're using.


If you want to obtain a minimal DNF in this way, it is generally a good idea to follow the Quine-McCluskey algorithm (https://en.wikipedia.org/wiki/Quine-McCluskey_algorithm). Otherwise, it is easy to get stuck when you use distributivity to combine each term with just one of several possible partners (if you look at your kmap, this would correspond to arranging the $1$ into pairs in such a way that none of them combine into larger blocks).

One other problem with your computation is that you lost the term $A'BC'D'$ when forming pairs (the reason why you still ended up with five pairs os that $A'BCD$ is covered twice).


thanks for your interest in call-by-push-value.  The fact that functions (all functions, not just lambda-abstractions) are computations is the main difference between call-by-push-value and call-by-value (where functions are values), and it does seem strange at first.  But the mystery is (somewhat) resolved when you see the CK-machine, which is a kind of operational semantics that uses a computation and a stack.  In terms of that machine, a function of type A -> B is a computation that aims to pop a value of type A and then behave as a computation of type B.  For example:

    print "hello".
    lambda x.
    print "hello again".
    return x

is a computation that first prints "hello", then pops x ("lambda" means "pop"), then prints "hello again", then returns x.  And actually, the same phenomenon of "lambda" as "pop" is present in call-by-name; that's why call-by-push-value manages to subsume call-by-name.

I hope that helps!  I should also say that the origin of call-by-push-value is that it was empirically observed within the models.  The slogan was designed to fit the language and not the other way round.  But that's just saying probably a less helpful answer, because it's just saying "the language is that way because the models say so".


Yes, you are absolutely right.  GeeksforGeeks is just wrong in this case.

Your analysis is correct.  The language $L=\{a^n b^{2m} \mid n \ge 1, m \ge 1\}$ certainly is regular.  Your DFA seems fine.  I don't know why the GeeksforGeeks article claims it is not; but in any case they are wrong.  It's a strange example; even by their own notions of what counts as a "regular pattern", $b^{2m}$ is a "regular pattern", so I don't know why they are giving that example.

Even if we try to look at better examples, the claim is still wrong.  For instance, consider the language

$$L = \{a^n a^p \mid n \ge 0, p \text{ is prime}\}.$$

This language is described by the concatenation of a "regular pattern" and a "non-regular pattern", so that article claims it should be not regular -- but they're wrong.  In fact, $L$ is regular, as $L  = \{a^m \mid m \ge 2\}$.

This whole notion of a "regular pattern" and "non-regular pattern" in that article is pretty much baloney.  I realize what they're trying to do -- they're trying to look for a shortcut to quickly tell whether a language is regular based on the syntax of the description of the language -- but those proposed rules are not a reliable way to tell whether a language is regular or not, and the notion of a "regular pattern" is not well-defined.  That's not a standard concept -- it's just something someone on the Internet made up.  At best, it is a way to form a quick guess at whether a language is regular or non-regular -- but I would recommend always following that up by proving your guess is correct, as their proposed rules are a bit dodgy.

Perhaps a lesson is to rely on primary sources, like well-regarded textbooks, and don't trust too much what you read on the Internet.


Range sum query - tree representation efficiency

This approach does work. A "Binary-Indexed-Tree" is just an implicit balanced binary tree with some extra "compression". See this answer for the details on how and why this is done, but essentially the purpose is just to run in fewer cycles.
Your approach works fine asymptotically and will probably even perform fine in practice.

First, is the resulting tree produced by your queue always guaranteed to be "short"? The answer is yes. The easiest way to see this is notice that your queue's use is naturally into "epochs", where each epoch builds roughly one level of the tree.
First, as a simplification, don't bother tracking the marked separately from the others. Instead, just repeat the loop until Q has only one element, and then let that be your root. This simplifies your state and makes it easier to follow.
while q.size() > 1:
   next = []
   while q.size() > 0:
       a := q.pop()
       if q.empty():
           next.push(a)
       else:
           b := q.pop()
           next.push(make_parent(a, b))
   for v in next:
       q.push(v)
root := q.pop()

If the queue contains all $n$ before an iteration, then afterwards it will contain either $\lfloor n / 2 \rfloor$ or $\lfloor n / 2 \rfloor + 1$ nodes depending on whether $n$ is is even or odd.
In addition, the maximum height of the nodes in the array will increase by at most one, since each node is only paired with one other (a careful analysis will show it always increases by exactly one, but we don't actually care).
The first observation tells us that the loop will run for $O(\log n)$ iterations. The second therefore tells us that the resulting tree will have height at most $O(\log n)$ since the height of the trees in the queue increase by at most 1 every iteration.
So the tree may not be perfectly "balanced", but its height is still bounded by $O(\log n)$ and thus any operation that runs in time bounded by the tree's height will run in $O(\log n)$ time.

The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.

This is actually straightforward. Suppose your tree has nodes in some levels that look the below, where the [--...--] indicate the range of values in the original array that the node represents.
Corresponding queries will be drawn with (...) instead. There are (generically) only a few kinds to worry about:

    [---------------45-----------------]
    [------------30----------][---15---]
  (- - Q1 - -)
           (- - Q2 - -)
                        (- - Q3 - -)
                        (- - - - - Q4 - - - -)
  (- - - - - - - - Q5 - - - - - - - - - - -)

Note that Q2 and Q4 have a symmetric forms that I'm omitting.

Q1 only traverses the left half
Q2 only traverses the left half
Q3 traverses both halves
Q4 traverses both halves
Q5 covers the entire range, so it won't traverse either

Thus we only really need to analyze Q3 and Q4.
Q4 totally covers the right half, so that "traversal" is guaranteed to be constant. So only the left half is traverses to any non-constant depth.
Thus the only "interesting" case is the Q3-type query, which only partially crosses the left child range and the right child range.
Note that the type-Q3 query extends to the left edge of the right child, and to the right edge of the left child.
This means that in the subtrees, there will be no type-Q3 queries, which can't extend to either edge. All queries will either completely miss each node, completely cover them, or extend past an edge.
So there will be at most one type-Q3 query in the entire tree (note that type Q5 also check both children, but that they are "fast").
Since there can only be one of them, you can essentially ignore them in the analysis - at most $O(\log n) + O(\log n) = O(\log n)$ nodes will be visited.


Can someone help me understand cache conscience radix sort? (excerpt from journal article attached)

The naming in the pseudo-code seems to be making things more confusing than they need to be, and it also seems to be glossing over some detail, but here's what I think is going on.

Let's just jump right in on a small example.
Suppose we have a data set, the integers 0-7 in binary:
$000, 001, 010, 011, 100, 101, 110, 111$. But obviously they're not necessarily given to you in sorted order. Let's say the input is actually:
$110, 101, 000, 010, 100, 111, 001, 011$.

If all this data fits in the cache, then you just run normal radix sort. That's the first branch of the if statement. For illustration, lets say that the cache can only hold two elements. Therefore, we end up in the else branch. The "reverse sorting" step splits the input into two sub-buckets based on the most significant bit.
So we get two buckets:

$1: (10, 01, 00, 11)$ and $0: (00, 10, 01, 11)$. We recursively call our function on each of these smaller buckets. Since they are smaller, they might now fit inside the cache, and we could run normal radix sort.

So now we're in the recursive call on the first sub-bucket. The input is
$1:(10, 01, 00, 11)$. However, our cache size is only 2. Therefore we move into the else branch again. We split the input into
$11:(0,1)$ and $10:(1, 0)$. and call the function recursively. Now finally on each of these recursive calls, the input is small enough to fit in the cache, and we run normal radix sort.

The other recursive calls function similarly.
Their pseudo-code seems to be missing how the partitions are pieced back together in a cache conscious way. Maybe this is obvious or covered elsewhere in the paper.


Does this "set intersection" problem have a different name?

To the best of my knowledge, there is no other name for this.


Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)

Define $\ell(v)$ to be the leaves reachable from a node $v$. Note the following:

  Lemma 1: For all non-leaf nodes $v$ we have: $$\ell(v) = \cup_{u \in c(v)} \ell(u)$$ where $c(v)$ is the set of all children of $v$.

We now construct an algorithm around this:

Let $A = \{v_1, v_2, \ldots, v_n\}$ be the reverse topological order of nodes in $G$.
For all $v \in A$:

If $v$ is a leaf node, define $\ell(v) = \{v\}$.
Otherwise, define $\ell(v)$ as we did in Lemma 1.

Now the complexity of this is $O(km + n)$ where $k$ is the average cost of union-ing the $\ell$-sets of the children of a non-leaf node. How you go about union-ing the sets is up to you. Standard merging is easy to implement. You could also try using a disjoint-set data structure, but this becomes tricky because a node might have multiple parents.


Why classification represents all computations?

First, you're not entirely correct when you say that a "Turing machine could do any computation that is possible to compute". What you're referring to is known as the Church-Turing thesis and it's not a statement of fact, but more like a statement of confidence. A better way of stating it would be "Any task that we would agree would be described as 'computation' can be accomplished by a TM". This wouldn't be true or false until we could somehow formalize the part "... we would agree  would be described as computation ...".

One reason that we have for being confident in the C-T thesis is that people have come up with many apparently different ways of modeling what we call computation and in every case it has turned out to be the case that anything that these models can do can also be done by a TM.

Take, for instance, addition. While your instructor may not have shown you, it's not difficult to build a TM that when given two (binary, say) representations of integers, produces on its tape a representation of the number that is the sum of the two original inputs. Any text I know of includes examples of such computations and there are literally hundreds of online examples of TMs that can add, subtract, multiply, compare numbers, and do other tasks that we'd call computation.

In a sense, you can do these computational tasks without explicitly showing how as long as you can decide whether an input string was in a language, which is what you mean by "classification". The classification problems you've seen take the form, I suspect, of "Given a language $L$, make a TM that determines whether of not an input string is in the language". These decision problems are just disguised forms of what you've described as "computation".

Here's an example: Suppose you had a language, $A$, consisting of all triples, $(x,y,z)$ where $x,y,z$ were binary representations of integers such that $x+y=z$ and you had a TM, $M$, that when given any such triple, could decide whether or not that triple was in $A$ or not. From this TM, you could make another, $M'$, that would do addition. All it would have to do to add $x$ and $y$ would be to try all possible strings $z$ and for each one use $M$ to decide whether $(x,y,z)$ was in the language $A$. Sure, it would take a long time to come up with an answer, but once you hit upon the right $z$, all that $M'$ would have to do would be to write the $z$ it found on its tape.

That equivalence, between classification and computation, gives some justification for the apparent approach your instructor has adopted (though a weak justification, in my opinion). My advice to you would be to search out some examples of computation, like addition, that would give you an idea about the tasks TMs can do.


Recursive DP vs Graph Traversal solutions to path-based problems

Both approaches are valid.  Assuming you're using memoization, they're largely equivalent; two different ways of thinking about the same thing.


Binary exponentiation of matrix - complexity

The solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + O(1)
$$
(this is the correct form of your recurrence) is $T(n) = O(\log n)$. If you want to be more accurate, the solution of the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C
$$
is (for $n \geq 1$)
$$
T(n) = C\lfloor \log_2 n \rfloor + T(1).
$$
In your case $C$ is not really constant, but rather depends on the parity of $n$. Accordingly, we can consider the recurrence
$$
T(n) = T(\lfloor n/2 \rfloor) + C_{n \bmod 2},
$$
whose solution is
$$
T(n) = C_1 \#_1(\mathrm{bin}(n)) + C_0 \#_0(\mathrm{bin}(n)) + T(0);
$$
here $\mathrm{bin}(n)$ is the binary representation of $n$, and $\#_0,\#_1$ is the number of $0$-s and $1$-s, respectively.


To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle.  It is just a mathematical truth that (1) there exists an oracle relative to which P=NP, and that (2) there exists an oracle relative to which P≠NP.

This means that if you have an approach to prove P≠NP and the same proof would equally prove a stronger result “PA≠NPA for all oracles A,” then your approach is doomed to fail because it would contradict (1).

In other words, there is some fundamental difference between proving P≠NP and proving e.g. the time hierarchy theorem, because the proof of the latter just uses diagonalization and is equally applicable to any relativized world.

Of course, this does not mean that there is no proof for P≠NP.  Such a proof (if one exists) must fail to prove the stronger result mentioned above.  In other words, some part of the proof must distinguish the nonrelativizing world from arbitrary relativized worlds.


Question regarding notation of a language decidability

The languages are not the same.

In the first one, $w$ is a part of the input.
In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.


It's because languages are the best (only?) way we have of formalizing the concept of a "problem."

An algorithm (Turing Machine) has performance, which we express via big-O complexity. A problem (language) belongs to a complexity class. These are usually defined by existence: if there exists a machine accepting a language $L$ which runs in given performance (space or time), then the language belongs to the corresponding complexity class.

There's a few reasons for this. First is that languages are platform independent. You're not worrying about whether an integer is 32 or 64 bits, or whether floating point operations run in parallel with other operations. These things give performance speedup at the micro-level, but complexity analysis is interested in the macro level. As you scale from 100 to $10^6$ to $10^9$ to $10^{12}$ inputs, how does the algorithm performance change? Does it go from using 1 million tape cells to 1 billion, or from 1 million to more cells than there are atoms in the universe?

The second is that languages are just a nice abstraction for data. You need something you can do proofs about, something you can model formally. Encoding your input and output as a string mean that you're now dealing not with bits in memory, but with mathematical objects with specific properties. You can reason about them and prove proofs about them in a formal, and very simple sense.

Complexity theory tends to be focused on decision problems because they end up being difficult. When the decision version of travelling salesman is NP-complete (i.e. is there a tour shorter than length $k$), then obviously finding the shortest path is harder. There isn't as much focus on function/optimization problems because there's still a lot of open questions and unsolved problems about the simpler decision problems.

I guess here's my challenge to you: find way to mathematically describe problems that isn't languages. I don't know if languages are special, but I think they're the simplest tool we've got, the easiest one to deal with.


Hint: You have a 3SAT formula $\varphi$ in CNF with $n$ clauses and a maximal $m \le n$ number of clauses can be satisfied. What happens if $m < n$? And what about $m = n$?


Lexicographic Order of Expression [Automata Theory]

The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language $a^*b^*$, assuming that $a < b$. Note for instance that
$1 < a < a^2 < \dotsm < a^n < \dotsm$, but $\dotsm <a^nb <\dotsm <a^2b < ab < b$.


Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by
$$
\begin{align*}
L(i,i) &= \sum_{j \neq i} X(i,j) \\
L(i,j) &= - X(i,j).
\end{align*}
$$
Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K_n$ we can associate a degree $n-1$ monomial $X(T)$ as follows. Root the tree at the vertex $n$. For every non-root vertex $i$ with parent $j$, we include the variable $X(i,j)$ in the monomial. In total $X(T)$ is a product of $n-1$ monomials, one for every edge in the tree.

Let $M$ be the $(n,n)$ minor of $L$. We will show that $\det M = \sum_T X(T)$. You can derive the matrix-tree theorem from this statement by substituting the actual graph for the indeterminates $X(i,j)$. If you wish, you can run the entire proof after doing the substitution, and then you don't have to talk about indeterminates.

Recall that
$$\det M = \sum_{\pi \in S_{n-1}} (-1)^\pi \prod_{i=1}^{n-1} M_{i\pi(i)}.$$
We can write every permutation $\pi$ as a product of cycles $\pi_1,\ldots,\pi_{\ell(\pi)}$ and of fixed points $F(\pi)$, and then we get
$$
\begin{align*}
\det M &= \sum_\pi (-1)^\pi \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} (-X(i,\pi(i))) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right) \\ &=
\sum_\pi (-1)^{\ell(\pi)} \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} X(i,\pi(i)) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right),
\end{align*}
$$
using the formula $(-1)^\pi = \prod_{t=1}^{\ell(\pi)} (-1)^{|\pi_t|+1}$. We can rewrite this as
$$ \det M = \sum_\pi D(\pi), $$
where $D(\pi)$ is the expression appearing above.

If we open up all the sums, we find that $\det M$ is a (weighted) sum of monomials of the form $X(\alpha) = \prod_{i=1}^{n-1} X(i,\alpha(i))$. For each $\alpha$, we can look at the directed graph in which $i$ points at $\alpha(i)$. It's not hard to see that each such graph consists of a (possibly empty) collection of cycles $\alpha_1,\ldots,\alpha_{\ell(\alpha)}$ and a tree $T(\alpha)$ rooted at $n$. We will show that the coefficient of $X(\alpha)$ equals $1$ if $\ell(\alpha) = 0$, and vanishes otherwise. This will complete the proof.

Consider first the case that $\ell(\alpha) = 0$. In this case the only permutation $\pi$ for which $X(\alpha)$ appears in $D(\pi)$ is the identity permutation (since every $X(\beta)$ appearing in any other $D(\pi)$ contains some cycle), ans so the coefficient of $X(\alpha)$ in $\det M$ is indeed $1$.

Next, consider the case in which $\ell = \ell(\alpha) \neq 0$. In this case, for every subset $S$ of the cycles of $T(\alpha)$, $X(\alpha)$ appears in $D(\pi)$ for $\pi = \pi(S)$ which consists of the cycles in $S$, and it only appears in these $D(\pi)$. For every $S$, the coefficient of $X(\alpha)$ in $D(\pi(S))$ is $(-1)^{|S|}$. Therefore the total coefficient of $X(\alpha)$ in $\det M$ is
$$
\sum_{S \subseteq \{\alpha_1,\ldots,\alpha_\ell\}} (-1)^{|S|} =
\sum_{S_1 \subseteq \{\alpha_1\}} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_1| + \cdots + |S_\ell|} = \\
\sum_{S_1 \subseteq \{\alpha_1\}} (-1)^{|S_1|} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_\ell|} = (1-1)^\ell = 0.
$$
(This is just inclusion-exclusion. The previous case is the case $\ell=0$.)
This completes the proof.

This proof is taken from lecture notes by Jacques Verstraete. See also Mark Muldoon's lecture notes, which presents this argument as a version of inclusion-exclusion.


A more formal way to define the down function is
$$
\mathit{down}(x,y) =
\begin{cases}
(x-1,y) & \text{if } x > 0, \\
(y-1,0) & \text{if } x = 0 \text{ and } y > 0, \\
\text{undefined} & \text{if } x=y=0.
\end{cases}
$$


Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M $ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.


Why is quicksort better than other sorting algorithms in practice?

Short Answer

The cache efficiency argument has already been explained in detail. In addition, there is an intrinsic argument, why Quicksort is fast. If implemented like with two “crossing pointers”, e.g. here, the inner loops have a very small body. As this is the code executed most often, this pays off.

Long Answer

First of all,

The Average Case does not exist!

As best and worst case often are extremes rarely occurring in practice, average case analysis is done. But any average case analysis assume some distribution of inputs! For sorting, the typical choice is the random permutation model (tacitly assumed on Wikipedia).

Why $O$-Notation?

Discarding constants in analysis of algorithms is done for one main reason: If I am interested in exact running times, I need (relative) costs of all involved basic operations (even still ignoring caching issues, pipelining in modern processors ...).
Mathematical analysis can count how often each instruction is executed, but running times of single instructions depend on processor details, e.g. whether a 32-bit integer multiplication takes as much time as addition.

There are two ways out:

Fix some machine model.

This is done in Don Knuth's book series “The Art of Computer Programming” for an artificial “typical” computer invented by the author. In volume 3 you find exact average case results for many sorting algorithms, e.g.

Quicksort: $ 11.667(n+1)\ln(n)-1.74n-18.74 $
Mergesort: $ 12.5 n \ln(n) $
Heapsort:  $ 16 n \ln(n) +0.01n $
Insertionsort: $2.25n^2+7.75n-3ln(n)$

[source]

These results indicate that Quicksort is fastest. But, it is only proved on Knuth's artificial machine, it does not necessarily imply anything for say your x86 PC. Note also that the algorithms relate differently for small inputs:

[source]
Analyse abstract basic operations.

For comparison based sorting, this typically is swaps and key comparisons. In Robert Sedgewick's books, e.g. “Algorithms”, this approach is pursued. You find there

Quicksort: $2n\ln(n)$ comparisons and $\frac13n\ln(n)$ swaps on average
Mergesort: $1.44n\ln(n)$ comparisons, but up to $8.66n\ln(n)$ array accesses (mergesort is not swap based, so we cannot count that).
Insertionsort: $\frac14n^2$ comparisons and $\frac14n^2$ swaps on average.

As you see, this does not readily allow comparisons of algorithms as the exact runtime analysis, but results are independent from machine details.

Other input distributions

As noted above, average cases are always with respect to some input distribution, so one might consider ones other than random permutations. E.g. research has been done for Quicksort with equal elements and there is nice article on the standard sort function in Java


Resolving NP problem with a deterministic turing machine

Transforming non-deterministic moves from a NDTM to deterministic moves in a DTM, needs exponential states to be explained. For example, a non-deterministic move can be done in $2$ different possibilities. Hence, the different combination of $n$ non-deterministic moves needs $2^n$ different deterministic computation path to be explained, as an instance.


If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$

The basic observation is
$$
\begin{align*}
A^c &= (A^c \cap B^c) \cup (A^c \cap B) \\ &=
(A \cup B)^c \cup (B \cap (A^c \cup B^c)) \\ &=
(A \cup B)^c \cup (B \cap (A \cap B)^c).
\end{align*}
$$
Using this you can recursively enumerate $A^c$. I'll let you figure out how.


Where have I gone wrong in "proving" this big-O identity?

You should be able to work out the answer yourself.  Here's the general procedure:

Since you know of a counterexample to the original claim, plug those $f,g$ into each step of your proof and find the first step in your proof where the proof goes wrong.  In other words, find the first claim made in the proof that isn't correct for that choice of $f,g$.  That will help you pinpoint the step in your proof that is flawed, i.e., that makes a conclusion that doesn't follow logically from the previous steps.


Your recurrence is
$$
T(n) = \begin{cases}
T(n-1) + n & \text{if $n>1$ is odd}, \\
2T(n-1) + \log n & \text{if $n$ is even}, \\
1 & \text{if $n=1$}.
\end{cases}
$$
We can convert it to a more amenable pair of recurrences. If $n > 1$ is odd then
$$
T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1).
$$
If $n > 2$ is even then
$$
T(n) = 2T(n-1) + \log n = 2T(n-2) + 2(n-1) + \log n.
$$
Finally,
$$
T(2) = 2T(1) + \log 2 = 2 + \log 2.
$$

We obtain the two recurrences
$$
T(2m+1) =
\begin{cases}
2T(2(m-1)+1) + (2m+1) + \log (2m) & \text{if $m > 0$}, \\
1 & \text{if $m = 0$}.
\end{cases} \\
T(2m) =
\begin{cases}
2T(2(m-1)) + 2(2m-1) + \log(2m) & \text{if $m > 1$}, \\
2 + \log 2 & \text{if $m = 1$}.
\end{cases}
$$
Both recurrences are of the form $S(m) = 2S(m-1) + \Theta(m)$. The simplest way of solving this is considering $R(m) = S(m)/2^m$, which satisfies the recurrence $R(m) = R(m-1) + \Theta(m/2^m)$. Since $\sum_{m=0}^\infty m/2^m$ converges, we see that $R(m) = \Theta(1)$ and so $S(m) = \Theta(2^m)$. This implies that $T(2m+b) = \Theta(2^m)$ (for $b=0,1$), and so $T(n) = \Theta(2^{n/2})$.


Concurrency: Is it order-independability or interruptibility of tasks?

Concurrency is working with tasks that may run simultaneously.  In my experience, when this term is used, the main focus is on correctness: making sure a system works as intended.

One way of doing that is to impose additional constraints on the system and ensure that they are always met.  Order independence and interruptability are examples of two such constraints.  You may want them to hold for your concurrent system.   But they are not required properties of concurrent systems in general: for many concurrent systems, they do not hold and do not need to hold.

For instance, in MySQL, you can configure to what extent you want your transactions to be isolated, with full serializability (order independence) as the highest level.


Is Binary Search Related to Binary Search Tree?

A balanced binary search tree describes the working of the binary search algorithm on a sorted list. The root should contain the middle element, the left subtree the left half, the right subtree the right half, and so on recursively. The tree also has to be balanced, that is, to reflect the fact that we chose the middle element as the root. In this sense, a binary search tree is a generalization of binary search on a sorted list.


Cover points with minimal number of spheres of fixed radius

Construct a graph. Represent every point by a node and connect two nodes with an edge if the distance of the represented points is $\leq R$.

Then, a minimial clique cover of the graph tells you which points should belong to the same sphere, one per cluster; pick the center of each set as center for the sphere.

Unfortunately, Minimal Clique Cover is NP-hard so no efficient algorithm is known for it. There may be algorithms suitable for your application in the literature, though.

Does it get any better? I don't have a proof, but this feels like a clustering problem to me which tend to be NP-hard. You may want to try and apply the ideas of hierarchical clustering.


Your original grammar is ambiguous:

L → L : L
L → id R

Suppose we have id : id : id. (For simplicity, I'm just letting R derive the empty string, but any valid derivation of the Rs would end up with the same ambiguity.) That needs to be derived from S → L → L1 : L2, but from there, either L1 or L2 can derive L : L. In effect, the two cases correspond to : associating to the left or associating to the right, but with longer sequences of :-separated id R clauses, the number of possible parses increases exponentially.

Your rewrite does not eliminate this ambiguity, it just makes it harder to see.

In short, you need to decide how : associates. It probably makes most sense for it to associate to the left, but an LL grammar really only handles right-association. (That's not a huge problem since you can reassociate the AST easily enough, but with an LR parser generator you wouldn't have to do any of this.) If we rewrite L as right-associative, we automatically eliminate the left-recursion problem:

S  → L
L  → L'
L  → L' : L
L' → id R

(Really, L' is not very useful in this case; it would have been almost as simple to write L → id R | id R L. But in either case, you end up needing to factor out the common prefix.)


Understanding N process Peterson's algorithm

The way the N-process Peterson's algorithm works is slightly different than how the 2-process version is presented above. We can reason about the N-process version a little more like this:

When a process wants to start running (i.e.: executes lock()), it imagines that it's joining an imaginary queue of processes. It doesn't know exactly how many processes are in the queue nor exactly what position in the queue it is in (because of the vagaries of concurrency). It does know that the queue can only have N possible positions because there are N total processes. The goal is for to only allow a process to exit the lock() procedure once it is sure that it is at the head of the queue.

To keep the notation consistent with the pseudocode listed above, we'll say that position 0 is the tail (back) of the queue, position N-1 is the head (front) of the queue, position N-2 is second from the front, etc... , and position -1 means you're not in the queue at all (i.e.: has not executed lock()).

What each process does is it makes an estimate of what its potential position is in this queue and declares that it is the most recent process to estimate that it is in that position (if that position is not -1). Initially, when a process first starts the lock() procedure, it will of course estimate that it is at the back of the queue (i.e.: position 0). These estimates of where each process thinks it is in the queue and who is the most recent process to think they are in each position is shared information. In the pseudocode the position estimates per process are stored in the flags array and the list of most recent process per position is in the turn array.

Then, each process looks around at this shared information to see if it can update its estimate of where it is in the queue. These updates can only move a process's estimate one position forward in the queue (i.e.: closer to the head). You can update your position in two situations: 1) if another process comes later than you and thinks it is in the same position as you, 2) if everyone else thinks they're strictly behind you. Whenever you see one of these situations happen, you can update your estimate of your position to move one step toward the head.

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;                 // I think I'm in position "count" in the queue
    turn[count] = i;                  // and I'm the most recent process to think I'm in position "count"

    "wait until                       // wait until
     (for all k != i, flags[k]<count) // everyone thinks they're behind me
     or (turn[count] != i)"           // or someone later than me thinks they're in position "count"

                                      // now I can update my estimated position to "count"+1

 }                                    // now I'm at the head of the queue so I can start my critical section

Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;                        // I'm not in the queue anymore

As noted before, this is slightly different than the presentation of the 2-process version as given above. However, we can reframe that presentation in this framework easily with only some slight modification. Note that in the 2-process case, the queue only has two potential positions, the head (position 1) and the tail (position 0) of which only position 0 is explicitly claimed.

flag[0]=0;                   // I am at the tail of the queue
turn=0;                      // and I am the most recent process to join the queue

while (flag[1]==0            // while you are in the queue
    && turn==0)              // and I joined the queue later than you did
  { }                        // I will wait

//Critical Section

flag[0]=-1;                  // I am no longer in the queue


There are constants $c,C,\epsilon > 0$, such that $1+x+cx^2 \le e^x \le 1+x+Cx^2$ whenever $|x| \leq \epsilon$.


Do we want largest or smallest priority in the A* algorithm?

It's just two ways of saying the same thing.  High priority means most urgent but is often represented by low numbers – my "number-one priority" is the most urgent thing on my to-do list.  Perhaps it would be clearer if people used phrases like "lowest priority value" or even "highest priority (lowest priority value)". It's often inconvenient to reformulate the algorithm to make high priority correspond to big numbers. For example, if I decide that "priority 10" means the most important thing on my to-do list, that kind of limits my lists to ten items, unless I want to number them 10, 9, ..., 1, 0, -1, -2, ..., which seems a bit silly.

Similar confusion comes up in other settings where smaller numbers represent bigger or higher things. For example, in photography, aperture is measured in f-stops but a higher f-number means a smaller aperture.


Is the "data path cycle" the same thing of the "fetch-decode-execute cycle"?

Data path cycle is not widely used terminology.  I believe Tanenbaum made it up.  I don't have the 5th edition, but if I look up Tanenbaum's slides on Google (for example: http://www.verlab.dcc.ufmg.br/_media/cursos/arquitetura/2011-1/transparencias/tanembaum_4.pdf) it appears that he is using data path cycle to refer to a single clock cycle.  As in "the amount of time for all the signals to propagate all the way through the data path."  Think of it as the amount of time required to perform one micro-instruction.

But Tanenbaum uses a multi-cycle-per-instruction microcoded organization, so the fetch-decode-execute cycle (for instructions rather than microinstructions) usually involves multiple clock cycles.


Should two DFAs be complete before making an intersection of them?

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton?

If there is no transition in one of the automata, then that one won't accept the input word. Therefore, the automaton for the intersection should not accept either; not having a transition is one way to make sure of that.


Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ramifications of the concept of computation. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models are the same from the point of view of computability theory. Computability theory, while an interesting mathematical subject, is not a good model for real-world computation for this reason, as you mention.

Complexity theory started its life as an attempt to address this issue. Complexity theory studies how difficult it is, in terms of time and space, to compute certain predicates and functions. From the point of view of complexity theory, not all computation models are the same, and Turing machines are taken as the reference model. However, even complexity theory is not very realistic, since it treats all computational models polynomially equivalent to Turing machines in the same way (two models are polynomially equivalent if any problem solvable in time $T(n)$ and space $S(n)$ in one model can be solved in time $T(n)^c$ and space $S(n)^c$ in the other, where $n$ is the input size and $c$ is some positive constant). For example, Turing machines are not good models for real computers since they do not support random access (accessing an arbitrary point in memory in time $O(1)$). Of course, random access can be simulated by a Turing machine, but the simulation can be slow. It is often said that sorting can be done in time $O(n\log n)$, but this is not the case for Turing machines, which probably require $\Omega(n^2)$ or move even for sorting integers. Therefore in the area of algorithms, other models such as the RAM machine replace Turing machines.

Finally, quantum computers can be modelled in several different ways, such as the quantum Turing machine. Everything computable using quantum computers is also computable using classical computers, and so from the point of view of computability theory, quantum Turing machines are just another equivalent model. However, quantum Turing machines are widely conjectured not to be polynomially equivalent to classical Turing machines: for example, factoring and discrete logarithm are "easy" for quantum Turing machines (solvable in polynomial time), while it is conjectured that they are "hard" for classical Turing machines (cannot be solved in polynomial time; though some people think that integer factoring might be solvable in polynomial time). So from the point of view of complexity theory, quantum Turing machines are different from classical Turing machines.


Why do I get really different results with my benchmarking code I made?

While benchmarking metal is mostly outside of the realms of computer science -- we usually don't want to worry about issues of materials and physics -- there are some general remarks here.
Tl;dr: benchmarks are inherently fickle.

Your benchmark process is not alone on the machine. Other processes and interrupts can cause your process to be stalled non-deterministically¹.
Therefore, if your benchmark is only a few seconds long (or less?), random events can dominate the measurement. You want to measure for long periods of time (so you get "average noise") on a machine where almost nothing else is running (so there's little noise) and compare with exactly the same system but the CPU (so the noise is the same).

Flops figures in the literature (or ad leaflets) are often theoretical peak figures. They just look at the CPU construction and say, okay, ideally (no pipeline stalls, no context switches, no memory delay, ...) at this frequency (which a store-bought, flawed chip may not be able to attain) the FP-ALU can compute this many operations per second.
This number is never attained. You can of course try to determine a "real" peak number by running different benchmarks and taking the maximum. Averages probably depend heavily on the benchmark.

Flops are only one type of operation. What about all the others?

Real computation performance depends on many factors that range from the architecture of the CPU to the design of the program being run on it. One notable example would be the length of the pipeline. All else being equal, a chip with a longer pipeline will outperform one with a shorter pipeline on long chains of operations without any conditional jumps -- and exactly the other way around if there are (many) such jumps!

If not, what ways are useful to get an aproximate result of how fast is a CPU.

I am not sure that there is a general measure for "CPU speed". Different CPUs excel at different things. Also, relative measures like "computation power" per Watt become increasingly relevant.

That said, I'm sure books have been written about all these issues. I can't recommend one, but doing some literature research may pay off -- especially at your level, since it'll point you towards many other great things to learn!

It's not really non-deterministally or random, of course. But when looking at a CPU as a black box, it might as well be.


Are CPU architectures biased towards procedural runtimes?

It is probably more the case that modern computer architectures are designed with the goal of improving the quality of code generated by compilers against a budget of cost in die area and power used. Runtime libraries are just a specific instance of compiled code that needs to be executed in an efficient manner.

For a very long time, the target language for most architectures has been the "C" language. This reflects the modest demands that that language makes on its hardware and the fact that it has become an almost universal systems programming language (Sorry Rust and Go, you have a long way to go to beat C).

A consequence of this seems to be that new languages are often defined in terms of their C equivalent semantics just so that they will avoid needing processor facilities that are likely to be absent on current computers.

The payoff for a processor that matches well with modern compilers is that code from those compilers runs well and the processor has at least a chance to be competitive. The cost of failure here dooms the processor before it can get started. Just two examples in the negative include the iAPX-432 and the Itanium, both by Intel. Both had a very poor relationship with their compilers (Ada and C respectively) with the failure of the products turning into a blame game between silicon and software.


Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

Found a solution here, as glsl, which at one time had near exactly the same restrictions I wanted:

float rand(vec2 co){
    return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

or as I implemented it: $\operatorname{mod}\left(\sin \left(a\cdot 12.9898+b\cdot 78.233\right)\cdot 43758.5453,\ 1\right)$


A PDA is a special (degenerated) case of a TM. Specifically, TM can be seen as a PDA whose stack's head can read from within the stack and not only the top of the stack.

Therefore, simulation of a PDA by a TM is trivial.


Regularity of a language constructed from a know regular language

As you mention, if $n$ was fixed, then this is not too difficult to prove.
So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$.
To this end, consider some word $x\in \Sigma^*$, and suppose $x^m\in A$ for some $m$.
Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m>k$, then there exist $0\le i<j\le m$ such that the run of $D$ on $x^i$ reaches the same state as on $x^j$. But this implies that $x^{m-{j-i}}$ is also accepted by $D$.
Thus, it's enough to consider $n\le k$. So you can rewrite your language as
$$\{x| \exists n\le k,\ x^n\in A\}$$
And this is regular.


Context free grammar for language with even number of $0$'s and $1$'s

The most common approach to show that two sets are the same is to show that they are subsets of each other.

In this case, that means (1) every string with an even number of $0$s and $1$s has a derivation in the grammar, and (2) every derivation of the grammar has an even number of $0$s and $1$s.

In attempting (2), a reasonable approach is to prove inductively, from smaller strings to bigger strings.

For example, considering $S \to 0S0S$, since the number of $0$s increases by 2 and the number of $1$s stays the same, the resulting string has the desired property when the smaller $S$ strings in the right hand side do.

However, I think you'll find the $S \to BABAS$ case hard to prove correct, which suggests that's where you need to look for a counterexample. Indeed, here's one:

0101010 = (B:0)(A:1)(B:0)(A:1010)(S:) = (B:0)(A:1)(B:0)(A:(1(A:0)1(A:0)))(S:)


Memoization is related to dynamic programming in the following way.
Let $V$ be the set of all possible inputs to the function $f$. Draw an edge from $x \in V$ to $y \in V$ if the computation of $f(x)$ invokes $f(y)$. The resulting graph is a directed acyclic graph (DAG).
Now suppose that you want to compute $f(x)$. Let $V(x)$ be the set of all vertices reachable from $V(x)$. In dynamic programming, we arrange $V(x)$ in reverse topological order, and compute $f$ in that order.
As an example, consider the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$, with base cases $F(1) = 1$ and $F(0) = 0$. In this case $V$ consists of all natural numbers, the edges are $n\to n-1$ and $n \to n-2$ (for all $n \geq 2$), $V(n) = \{0,\ldots,n\}$, and reverse topological order is $0,\ldots,n$. That is, we compute $F(0),F(1),F(2),\ldots,F(n)$ in this order. Whenever compute $F(m)$, all other values of $F$ which are needed are already available.

How do we compute the complexity of a memoized function? We imagine that instead of implementing it in a recursive fashion, we use dynamic programming. This means that each recursive call now takes $O(1)$; but when running $f(x)$, we actually evaluate $f$ on all inputs in $V(x)$.

In your case, $V(x)$ consists of all prefixes of $x$. In order to evaluate the running time, you need to compute, for each $n$, the running time of your procedure $T(n)$ on inputs of length $n$, assuming that all recursive calls are $O(1)$. The final answer is then $T(0) + \cdots + T(n)$.


is there a (FLAC like) loseless compression coding format for EEG data?

For single channel with raw signal, the best option is Elias gamma, for single channel frequency signal, the best option is to use Range encoder. For multiple channels, this is still viable option to compress each channel and then compress them together interleaving signal (one sample from all electrodes, then another sample from all electrodes).

If you have multiple channels, there are inter-channel correlations, which should be used for compresion, standard method is to use DPCM or use DCT-IV for decorrelation (this is the very same transform like in JPEG) and then use arithmetic codding of any kind. For online setting - compress signal as it goes - this is very good idea.

Another standart approach is Karhunen-Loeve transform. Do not use autoregressive methods, use Elias gamma in the pipeline instead.
Another approach is to use DCT transform to remove redundancy of interchannels (decorrelation) and compress in minimal frequency form.

If you need to store volumes of EEG data, my advice is to clear it from noises and store bands you are interested in, otherwise you store mainly hard to compress noise.


Yes, if you follow the canonical conversion of augmented grammars, a first step is adding a new start symbol $S'$ and the production $S' \to S$, since the algorithm may later "change" $S$.

However, it may not be necessary at all times. If you ask whether or not it is necessary specifically in this case, why don't you try without it and check if you get a valid answer?


What does exactly theoretical computer science entail?

CS isn't neatly divided into "applied" and "theoretical".  Work that seeks to build systems and solve practical problems tends to get described as "applied"; work that seeks to increase our knowledge of computation tends to get described as "theoretical". Machine learning covers a spectrum that includes both.

If somebody said to me "I'm a theoretical computer scientist", I probably wouldn't assume they did machine learning – but only because people who do machine learning tend to say "I do machine learning."


Why is the unit of image size not Pixel²?

Because "pixel" isn't a unit of measurement: it's an object. So, just like a wall that's 30 bricks wide by 10 bricks tall contains 300 bricks (not bricks-squared), an image that's 30 pixels wide by 10 pixels tall contains 300 pixels (not pixels-squared).


Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\{1,\ldots,n\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total,
$$
k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\
\frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1)
$$
We conclude that $\log N(n,k) = \Theta(n \log k)$.

For the exact expression, consult a paper of Kløve or the OEIS.


Use Rice's theorem to show that the language of optimisable Turing machines is undecidable

There is some TM which is not in $L'$, and there is some TM which is in $L'$. So the definition of $L'$ determines a nontrivial property on r.e. languages and so by Rice's theorem it is not decidable.


Is CPU Registers part of Primary Memory?

CPU registers are often counted as part of primary memory (since they are directly accessed by the CPU - see Wikipedia) and are often volatile, so it seems likely that the expected answer is (1).

However, this is one of those annoyingly ambiguous questions which depend on the student memorising a very specific set of definitions and ignoring any exceptions.