Shannon's entropy works as a hashing or fingerprinting function here; they are not injective which means we have to be careful not to interpret too much into relations of values.

If $H(I_1) \neq H(I_2)$, then images $I_1$ and $I_2$ are certainly not the same.

If $H(I_1) = H(I_2)$ (or even $H(I_1) \approx H(I_2)$), however, we know nothing. The images might be similar, but the values can also be close because of non-injectivity.

We would like to have some smoothness, that is that two images are more different if $|H(I_1) - H(I_2)|$ is larger. Whether this is the case is certainly a quality criterion of such fingerprinting functions. Given your example, it does not seem as if entropy was a good fingerprint in this sense.

It would be confusing if any kind of entropy would be. Any rectangle of one color holds no information (entropy zero), yet two rectangles of different colors are as different as two images get.


For me a short-circuit isn't combinatorial nor sequential. It's an error, it may fry the circuits.

The circuit, regarded as a black box, is still in scope of the combinational logic definition: its output values depend only on the current values of the inputs;

You can make a logic inverter with high power relays. You set opposite tensions, the relays or the wires connecting them turn into melted metal. You have a memorised effect (blown circuit) : It is sequential!


Is a graph at least k-colorable? (Complexity)

Well, all graphs are colorable with $\geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).
As for the complement of this problem, note that you did not correctly invert the definition of the problem:
A problem $L$ is, after all, merely a set of strings over some finite alphabet $\Sigma$ representing some objects with some property.
Its complement is then the set $\Sigma^\ast \setminus L$ or the set of all strings not representing an object with the property.
If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $\mathsf P$.


How hexadecimal representation is more compact and intelligible for documentation?

This is just the ordinary English language use of the word "compact": taking up less space. As to whether it's more intelligible, eh, that's basically a matter of reader preference and very context-dependent. Probably nobody wants to read "The system supports up to 0x64 users."


Heights series in the DFS traversal of a binary tree

In each node, store the number of nodes that are in its subtree. This can be maintained efficiently during tree manipulation operations.

Then, you can find the $k$-th node of a DFS-traversal in time corresponding to its level: recurse left if the left subtree contains more than $k$ elements, recurse right if it contains more, stop if neither applies. With a simple counter, you get the level of the node you find.

This applies to trees in general.

In your special case, you already know all the numbers so just don't actually have to see the tree. "Search" for $k$ in the virtual tree where each subtree has $2^{L+1} - 1$ nodes, $L$ being the level. This gives you an $O(N)$-time algorithm, discounting the exponentiation.


The border between P and NP for some problems

Approximation algorithms are most often encountered in the context of optimization problems. Consider the problem of minimizing some function $f$ subject to constraints $C$. An $\alpha$ approximation algorithm (where $\alpha$ can depend on some parameters of the instance, such as the number of vertices in a graph) is a (usually) polynomial time algorithm which produces a feasible solution (that is, one satisfying the constraints $C$) whose value is at most $\alpha$ times the optimum.

In some cases, bicriteria approximation algorithms are considered. These are algorithms as above, with the only difference being that the solution doesn't satisfy the constraints $C$ but rather some weaker version of them $C'$. See this question for some examples.

In the case of 3-coloring, your notion is very similar to the following optimization version of 3-coloring: given a graph, find a 3-coloring which violates the least number of constraints. There are several hardness results that show that it is difficult to approximate the optimum, even if you are allowed to use more colors (in the spirit of bicriteria optimization problems). For example, Guruswami and Khanna, in their paper On the hardness of 4-coloring a 3-colorable graph, show that it is NP-hard to distinguish between the following two classes of graphs: (i) 3-colorable graphs, (ii) graphs in which every 4-coloring has an $\epsilon_0$-fraction of monochromatic edges (for some constant $\epsilon_0$).

Similarly, your relaxation of the Hamiltonian path problem can be rephrased as an optimization problem: the longest path problem. It is NP-hard for any constant $k$, and even for much larger $k$; see the paper mentioned in Wikipedia, On approximating the longest path in a graph by Karger, Motwani and Ramkumar.


This seems very confused. Probably you should state which programming language you are referring to as some of these concepts may have different definitions depending on the language or formalism. Much is arbitrary (possibly not always too consistent).  For example, you do not necessarily have booleans as a subtype of integers.

One important issue is to distinguish syntax (what you write to talk about entities) from semantics (the actual entities you wish to talk about). In a simple world, a type may be understood as a set of values that the language can manipulate through specific representations. A constant is a representation of a specific value. In many languages, a constant is a name that is given to a specific value in a given context. A variable is a place holder for a value, that may change.  Now this is to be interpreted a bit differently depending on the type of programming langusge, notably imperative of functional (there are other kinds).

Things get more complicated when you start aggregating values in various ways, because some language will let you consider aggregates where some components may change.

You should probably go back to a textbook on programming languages.

P.S. I agree that considering types as sets of values is too simplistic. But I am trying here to make as simple an answer as I can. This is precisely why considering boolean as a subtype of integer may not always be a good idea, or may not be as simple as it may seem.


I don't want to spoil the exercise, but I'd try to play with the fact that the property

$$
p_M(n,k):\ \mbox{$M$ accepts $n$ in exactly $k$ steps}
$$

is decidable. Then, we have that $\langle M \rangle \in T_{n+1}$ iff there are exactly $n+1$ pairs $(n,k)$ satisfying $p_M$.

Try to exploit this in your reduction.

  Can I use some kind of search algorithm to find a string in it and exclude it?

This approach is unlikely to work: to search, the new TM $N$ would need to run $M$ on some given inputs, but this is risky since $M$ can diverge and "block" the whole execution of $N$. It's safer to work with decidable predicates like $p_M$.


Smallest cost in weighted directed graph with combinations

You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions.

The example is rendered something like this (the exact syntax depends on the tool).

minimize 5*BX + 10*BZ + 4*CY + 6*CZ + 10*DX + 7*DYZ
subject to
BX + DX = 1  # project X is done once
CY + DYZ = 1  # project Y is done once
BZ + CZ + DYZ = 1  # project Z is done once
binary variables BX, BZ, CY, CZ, DX, DYZ in {0, 1}

The interpretation of, e.g., DYZ is that D is awarded the package of contracts for Y and Z if and only if DYZ has value 1.


What is the difference between abstract and concrete data structures?

The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations described by the ADT (possibly with some probability of success in the case of randomized structures), but each concrete structure may make different guarantees of the running times of each operation. The choice of which concrete data structure to implement for a given ADT usually depends on the priorities of efficiency of each operation (including initializing the structure) and the complexity of implementing and maintaining the various data types. Some concrete data structures have excellent theoretical guarantees, but the overhead is such that a slightly less theoretically optimal data structure may be a better choice in practice.

There are far too many ADT and corresponding concrete structures to list in a single answer, but here are a few examples:

A dictionary supports Find(x) queries. For an a key $x$, return the element in the dictionary with key $x$, if such an element exists. A dynamic dictionary also supports Insert(x) and Delete(x). Common implementations of a dictionary include different kinds of balanced binary search trees (e.g. red black tree) and various kinds of hash tables.
In addition to Find an ADT may require support of successor(x) queries. That is, maintain a set of keys $S$, and given key $x$, find the smallest key $t \in S$ such that $s < t$. Concrete data structures which support the Successor ADT include various binary search trees, and more complicated structures such as an X-fast trie or van Emde Boas tree (if the keys are integers).
A Priority Queue is an ADT that requires insert and delete-min operations (and sometimes other operations as well, such as find-min increase-key or delete-key). Data structures that implement the priority queue ADT include:

an unsorted linked list, which has fast insert but slow delete-min.
a sorted linked list which has fast delete-min but slow insert
a binary search tree, which has logarithmic insert and delete-min, and $sort(n)$ initialization time.
a binary heap which has logarithmic insert and delete-min, and linear time initialization.
There are also other variants of heap implementations.

An interval stabbing ADT maintains a set of intervals on the real line, and supports a stabbing(x) query, which returns the subset of intervals which contain (are stabbed by) the point $x$. Data structures that implement the stabbing query ADT include a Segment Tree and an Interval Tree.


find separate pairs of points with minimal total distance

Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then:

If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more.
If $N_S$ is odd, enumerate over all possible items $s_i$ in $S$ and for each of them, compute the best partition of $S \setminus \{s_i\}$, which is an even-size set, using the previous case. Return the best partition among all $N_S$ cases.

The total cost of this procedure is $O(N_S \log N_S)$ when $N_S$ is even and $O(N_S^2 \log N_S)$ when $N_S$ is odd.


Language of all sequences of permutations whose product is the identity

You haven't stated what happens to the empty word – I'm assuming it's accepted.

It is easy to check that the equivalence classes of the Myhill–Nerode relation correspond to all words multiplying to a certain permutation. Therefore the minimal DFA contains $n!$ states.

If the empty word is not allowed, there are $n!+1$ equivalence classes, one of them consisting only of $\epsilon$.


Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$

If the grammar can be really unrestricted (meaning the variables are allowed to totally disappear) the design of the grammar is not complicated.

Start with left and right boundaries. Assume the string already is of the wanted form (with boundaries): $L a^1\#a^2\#\dots\#a^k R$.

We can obtain the next string by adding one $a$ to each of the segments of $a$'s. We do this by having a symbol $W$ walking over the string from left to right while adding an $a$ after each $\#$. Basically this uses the production rule $W\#\to \#aW$. Of course $W$ starts at the left $L$ and disappears at the right $R$. Of course when the walker starts an extra $a\#$ at the left end must be generated.

A little tuning will make this work. At the end check that you did not forget to generate the string $a$.


Can a queue automaton recognize palindromes?

The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers for the end of the tape and for the head of the TM. Every time you make a move, you just go through the entire queue and re-push everything you pop, making whatever slight modification in head position and tape contents you require.

So this is computationally equivalent to a Turing Machine, so in particular it can recognize $L = \{ww^R \mid w \in \{0, 1\}^*\}$.


One approach is to recursively extend prefixes of the order. At each recursive call, we have a prefix $\phi$ of the order. We go over all remaining subsets, and for each subset $S$, we check whether the order $\phi < S$ is consistent. For each consistent $S$, we make another recursive call.

How do we check whether $\phi < S$ is consistent? This is a linear programming problem, whose solution we can speed up by starting the simplex algorithm from the "witness" showing that $\phi$ is feasible. There are two things to notice here: First, presumably you are assuming that all weights are positive. Second, we replace each constraints $A > B$ by $A \geq B+1$ (since LPs don't have strict constraints).

There are many optimizations which can be done here. For example, $S$ is always inclusion-minimal among the remaining subsets. Another optimization is to assume that the weights are ordered in a specific way (in your example, $x < y < z$); if you are really interested in all possible orders, you can always go over all permutations later.


Is there a name for the 'scope tree' organization?

As Raphael says in his comment, this is a hierarchical scope organization. But this can qualified any kind of tree structured scope, and you state in the title that it is tree structured.

The whole purpose of this hierarchy is to allow reusing the same name in a different scope, for some other naming purpose. So, given a name, you have to decide where to lokk for its meaning, in what scope.

As you suggest, you start for the current scope (to be defined ...) and you buble up to parent scopes until you find a definition for that name (a declaration usually). The first one you find is usually supposed to be the right one.

But there is a major problem remaining: which is the parent scope of any given scope? There are two major policies regarding this: static scoping also called lexical scoping, and dynamic scoping.

Static scoping corresponds roughly to the way scopes are embedded according to the program text. Dynamic scoping corresponds to the way scopes are embedded according to program execution.

So, for example, take a function foo that is declared in your program. If defines a new scope, with the variables local to foo. If the function uses a variable x that it does not declare, the meaning of the variable must be found in the parent scope. For dynamic scoping, the parent scope is that of the scoping structure (function, method, module, and whatever creates new scopes) that called the function foo. For static scoping the parent scope is the scoping structure in which the function foo was declared.

Static scoping is usually preferred because the meaning of a programming construct is independent of where it is actually used (possibly many different places), and depends only of where it is defined (only one place).  Hence program analysis, understanding, and maintenance is usually much easier with static scoping.

The story goes that dynamic scoping was invented more or less by accident, as it was used in the first Lisp interpreter in the late 1950s. People were not yet aware of the difference at the time. When they found out (see the Funarg controversy), the language was being used and it was to late. Until Scheme came in as a statistically scoped version of Lisp.

But there can be other ways of organizing scopes, of importing one scope into another, and so on. I suggest that you read the wikipedia page on scope, which you should have done before asking.


Are QR codes Turing-complete under the rules of Conway's Game of Life?

QR codes are limited to a maximum size 172x172, which is not nearly large enough to built a Turing complete state machine in.
A current implementation of a Turing machine in GoL takes 1714 by 1647 cells.
It is undoubtedly sub optimal, but compressing it to 172x172 seems a stretch.

However let's assume the QR code is a little larger than 1714 square.
All of the elements in the listed Turing machine are constructable using gliders and besides much larger universal Turing machines have been constructed that are fully replicable.
Given a large enough QR code most of the key space is arbitrary.
There are some fixed elements that would have to be destroyed.
There are no known patterns that cannot be destroyed by a well timed glider salvo and certainly the fixed patterns in the QR codes have been explored.

Given the amount of redundant parent patterns that reduce to the same child pattern it is quite likely it is possible.
Furthermore the error correction only has a local effect, so changing a pattern in the top corner does not affect data at the bottom.

If you change the question to:

  If I stamp my GoL grid with many QR codes, can I built a turing machine?

Then the answer is yes, because its trivial to collapse a QR code to a glider and a Turing machine can be constructed using gliders and only gliders.


Example of non extensible functions ( $f(x) \notin EXT $) for reduction

Every total uncomputable function cannot be extended to a total computable function. More generally, let $g$ be an uncomputable function, and let $h$ be a total computable one-to-one function, for example $h(x) = 2x$. Define a partial function $f$ by $f(h(x)) = g(x)$ (so $f$ is defined only on the range of $h$). The function $f$ cannot be extended to a total computable function.


Can there be a context-sensitive pumping lemma?

Here is some evidence that there is no pumping lemma for the context-sensitive
languages.

Of course, an answer hinges on the question what constitutes a pumping
lemma.  The weakest reasonable definition I could think of is this: A language
class $\mathcal{C}$ has a pumping lemma if there is a decidable ternary
predicate $P(\cdot,\cdot,\cdot)$ where $P(g,w,d)$ means:

$g$ is a word encoding a language $L(g)$ from $\mathcal{C}$ (think: grammar),
$w$ is a word in the language encoded by $g$
$d$ is a word encoding a pumpable computation/derivation for $w$ (think: NFA
computation with repeated state or CFG derivation tree with repeated
nonterminal). Here, pumpable means: there exist infinitely many words in $L(g)$.

Moreover, we want that given a language $L$ in $\mathcal{C}$ encoded by $g$,
for every sufficiently long word $w\in L$, there exists a word $d$ such that
$P(g,w,d)$.

For example, the pumping lemma for regular languages would give rise to
the predicate "$g$ encodes an $\varepsilon$-free NFA and $d$ encodes a
run that repeats a state and reads $w$". For suitable encodings, this
clearly satisfies the above conditions.

Now let us show that such a predicate does not exist for the context-sensitive
languages.

Observe that if a language class has a pumping lemma, then the infinity problem
(Given a grammar, does it generate an infinite language?) is recursively
enumerable: Given an encoding $g$, we can enumerate words $w$ and $d$ and check
whether $P(g,w,d)$. If we found such $w,d$, we answer 'yes', otherwise, we
continue the enumeration.

However, we show that the infinity problem for the context-sensitive languages
is not recursively enumerable. Recall that $\Pi_2^0$ is a level of the
arithmetic hierarchy that strictly includes the recursively enumerable
languages. Hence, it suffices to prove:

Claim: The infinity problem for the context-sensitive languages is $\Pi_2^0$-complete.

It is well-known that the infinity problem for recursively enumerable languages
is $\Pi_2^0$-complete (more often, one finds the formulation that the
finiteness problem is $\Sigma_2^0$-complete). Hence, it suffices to reduce the
latter problem to the infinity problem for the context-sensitive languages.

Given a TM $M$, we construct an LBA $A$ for the language
$$ \{u\#v \mid \text{$v$ is a shortlex-minimal accepting computation of $M$ on input $u$}\}. $$
Then, $L(A)$ is infinite iff $L(M)$ is infinite, which completes our proof.

Update: Tried to be clearer.
Update: Added example.


Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption

First, let me remark that $n=O(m)$ as in each clause only $3$ variables may appear, and that $m=O(n^3)$ without loss of generality as there can be at most $(2n)^3$ clauses up to repetition.

Your bound is not correct. Consider the case where some variable $X$ occurs positive in half the clauses and negative in the other half. This leads to roughly $\frac{m^2}{4}$ edges for $X$ alone. What is correct, however, is your suspicion that the parameter dependence is superlinear.

The reduction can be modified such that $|V|=3m+2n$ and $|E|=6m+n$. This would lead to a linear dependence of $k_{IS}$ on $k_{3-SAT}$. Consequently, with these parameterizations, independent set does not have a subexponential algorithm unless 3-SAT has.

However, there appears to be a further problem: The ETH uses a different parameterization. Namely just the number of variables, disregarding the number of clauses. I am not an expert in ETH. Possibly the sparsification lemma can help here.


Firstly you did not write the complete question, to complete it, if $S$ is the maximum sum of weights in any sub-grid of lenght $ \le L$, then we have to report $S$ and length of the sub-grid with smallest integral side where sum of weights inside it is $S$ ( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to you to figure out. In this answer my aim is to calculate $S$.

Now we come to some pre-requisites for solving the problems. Firstly you should be comfortable with segment tree implementation. Second you need familiarity with binary search. Lastly I also assume ( as you have mentioned ) you also have familiarity with computing the prefix/suffix sum arrays. Plus I assume the points are given in the array $arr$ .

Now I describe the algorithm.

It can be argued that one of the corner points of the square sub-grid we make should be a point from the set of points that is given to us. Thus for each point from $(x,y)$ from the set of points given to us, we consider the four possible squares, one with $(x,y)$ as bottom left corner, one with $(x,y)$ as top right corner, one with $(x,y)$ as bottom right corner and one with $(x,y)$ as bottom left corner.
I describe it for one case say when $(x,y)$ is bottom left corner of a square grid with size $L$ ( as to calculate $S$ we should take the side of the square sub-grid as long as possible which is $L$ ). That is our question reduces to finding the sum of weights of points in the red region in the figure below.
I have labelled the sum of weights of the other eight regions by using letters $a$-$h$. One way to calculate the sum of weights of the red region is to subtract the from total $a+b+c+d+e+f+g+h$.
I can calculate $b+a+h$ by using combination of binary search and prefix/suffix sum arrays. In a similar manner I can find the sums $b+c+d$,$d+e+f$ and $h+g+f$. But now the problem is that I have summed each of $b$,$h$,$d$ and $f$ twice. Thus I need to find the sum of weights $b$,$h$,$d$ and $f$ separately.
You can find the sum $h$ ( and similarly the three others ) using segment tree in $O(log(n)^2)$ where $n$ is the total number of points given. The trick is to build the segment tree on say the $x$ co-ordinate. And if there is a node
in the segment tree denoting the range $i$-$j$ ( $1 \le i \le j\le n$ ) then that node should store the $y$ co-ordinates of all points of array $arr$ from index $i$ to $j$ in sorted order, plus a suffix sum array for the same sorted array ( this is the main point, comment if you can't understand ). In this way by combination of querying on segment tree and binary search ( thus the $O(log(n)^2)$ factor comes ) you can find the sum of weights $h$.
So in nutshell you repeat the procedure for each point from the given set and for each point you try all $4$ square-sub grids of length $L$ and then select the one having maximum sum of the red region overall. The complexity will come out to be $O(nlog(n)^2)$ which is sufficient to pass the online judge.


How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of

languages described by regular expressions;
languages accepted by deterministic finite automata (DFAs);
languages accepted by nondeterministic finite automata (NFAs).

If, additionally, you've proven that some or all of these definitions are equivalent, you can use any of the appropriate ones.

In this case, your language is defined by a regular expression. If that's your definition of regular languages, you're already done.

Our reference question has more information.


Choosing a random edge with restrictions

You can't.  Consider the bipartite graph with a single edge $(u_0,v_0)$, with $u_0,v_0$ randomly chosen at time of creation of the graph.  Then sampling from $U$ has only a $1/2^n$ chance to hit $u_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u_0$ or $v_0$.  Without sampling either $u_0$ or $v_0$ you have no hope of outputting the edge $(u_0,v_0)$.  So after polynomially many samples, there's only an exponentially small chance of outputting that edge.  Yet a correct algorithm must always output that edge every time.  So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.


Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard

If you want to explicitly list all subsets of list, then the size of the output will be $\Omega( n \cdot 2^n )$.
Notice indeed at least half of these subsets have at least $\lfloor n/2 \rfloor$ elements, and just writing them out requires  $\Omega( n \cdot 2^n )$ space (and time).
If you want to iterate over each of these subsets but you don't necessarily need to explicitly list them, then you still need $\Omega(2^n)$ time since there are $2^n - 1$ subsets of interest.
An easy algorithm is as follows: maintain a binary counter $c$ of $n$ bits.
Intuitively, the counter represent the indicator vector of a subset $X$ of list (i.e., the $i$-th bit is $1$ iff the $i$-th element of list is included in $X$). Initially $c=0$. Increment $c$ until it overflows. Each time that a bit flips from $0$ to $1$ (resp. $1$ to $0$) you interpret this as adding (resp. removing) the corresponding element to $X$. The set resulting after each increment is the next set to consider.
This algorithm requires $O(2^n)$ time, plus whatever time you need to process these implicitly generated sets. To see this you can take a look at the amortized analysis of incrementing a binary counter (see, e.g., the section "Incrementing a binary counter" in Chapter 17 of CLRS). Essentially, the least significant bit flips at every increment, the second least significant bit only flips every other increment, and so on. The number of bit flips is then $\sum_{i=0}^{n-1} \frac{2^n}{2^i} < 2^n \cdot \sum_{i=0}^{+\infty} 2^{-i} = 2^{n+1} = O(2^n)$.
An application of this algorithm is generating all possible subset-sums of a set $S$ of integers (which is used used, e.g., in the split-and-list algorithm for the subset-sum problem), assuming that $\sum_{x \in S} x$ still fits into a constant number of memory words (and hence arithmetic operations can be carried out in constant time).
In this case adding (resp. removing) an element $x$ to the subset simply means increment the previous sum by $x$ (resp. $-x$).
Asking whether this problem belongs to $\textsf{P}$ or $\textsf{NP}$ or is $\textsf{NP}$-complete makes no sense, since these complexity classes are only defined for decision problems (and yours is not).


Chord algorithm - how to map nodes to keys?

Chord implementations use a defined function which is used to map the key identifiers (0, 2, 8, 11, 15 in your case) to the node identifiers (1, 5, 7, 10, 13). In the example you provided, the function works like this:

NodeID = KeyID % N

where NodeID is the (identifier) node where the key will be inserted, KeyID is the identifier of the key to be inserted, and N is the total number of nodes.

After you calculate the NodeID, it might be the case that this NodeID does not exist. For example, when KeyID is 0, the NodeID will be 0. Since NodeID doesn't exist, it will be allocated to the next highest (existing) node identifier which is NodeID = 1.

The keys identifier can be calculated using some hash algorithm.


Proving that Every Full Prefix-Free Language is Maximal

Suppose that $A$ is a full prefix-free language, that is,
$$
\sum_{x \in A} 2^{-|x|} = 1.
$$
Assume, for the sake of contradiction, that $A$ is not maximal. Then there is a word $y$ such that $A \cup \{y\}$ is also prefix-free. According to Kraft's inequality,
$$
\sum_{x \in A \cup \{y\}} 2^{-|x|} \leq 1.
$$
However, this implies that
$$
1 \geq \sum_{x \in A} 2^{-|x|} + 2^{-|y|} = 1 + 2^{-|y|} > 1,
$$
and so we reach a contradiction. This shows that $A$ is maximal.

The more interesting direction is the converse: if $A$ is maximal then $A$ is full. Let me give two proofs of this fact.

The first proof is by induction on the length of the maximal word in $A$ (note that if $A$ is maximal then it cannot be empty). If $A = \{\epsilon\}$ then $A$ is indeed full. Now suppose that $A$ contains some word of positive length. Since $A$ is prefix-free, $\epsilon \notin A$. Hence we can write
$$
A = \{ 0x : x \in A_0 \} \cup \{ 1x : x \in A_1 \},
$$
where $A_0,A_1$ are prefix-free, and have shorter maximal words. It is easy to check that $A_0,A_1$ are maximal: for example, if $A_0 \cup \{y\}$ were prefix-free, then $A \cup \{0y\}$ would be prefix-free. Applying the induction hypothesis, we see that
$$
\sum_{x \in A} 2^{-|x|} = \sum_{x \in A_0} 2^{-|0x|} + \sum_{x \in A_1} 2^{-|1x|} = \frac{1}{2} \sum_{x \in A_0} 2^{-|x|} + \frac{1}{2} \sum_{x \in A_1} 2^{-|x|} = \frac{1}{2} + \frac{1}{2} = 1.
$$

The second proof uses a probabilistic argument, though for the sake of presentation I will present it as a counting argument. Let $A$ be a prefix-free code which is not maximal, and let $n$ be the length of the maximal word in $A$. For a word $x$ of length at most $n$, let $B_n(x)$ denote all words of length $n$ of which $x$ is a prefix, and note that $|B_n(x)| = 2^{n-|x|}$. Since $A$ is prefix-free, the sets $B_n(x)$ for $x \in A$ are all disjoint. Therefore
$$
\left| \bigcup_{x \in A} B_n(x) \right| = \sum_{x \in A} |B_n(x)| = \sum_{x \in A} 2^{n-|x|} = 2^n \sum_{x \in A} 2^{-|x|} < 2^n.
$$
Therefore there is some word $w$ of length $n$ which has no word in $A$ as a prefix. So $A \cup \{w\}$ is also prefix-free, and we conclude that $A$ is not maximal.

Both proofs we presented above actually show the following stronger fact: every prefix-free code is a subset of a maximal prefix-free code. Let me quickly outline how to obtain this result using both proofs.

In the first proof, we prove the claim by induction. If $A = \emptyset$ then we can extend it to $A = \{\epsilon\}$, and if $A = \{\epsilon\}$ then $A$ is already maximal. So suppose that $A = 0A_0 \cup 1A_1$. The induction hypothesis shows how to extend $A_0,A_1$ to maximal prefix-free codes $B_0,B_1$ (respectively), and then $B = 0B_0 \cup 1B_1$ is maximal.

In the second proof, we obtain a maximal prefix-free code by adding to $A$ all words in
$$
\overline{\bigcup_{x \in A} B_n(x)}.
$$

In both proofs, one way to check that the extended code is maximal is by verifying that it is full.

For extra credit, the reader can try extending the ideas above to infinite prefix-free codes, that is, prefix-free codes containing countably many words.


I believe logarithmic time for all queries is achievable.  The main idea is to use an interval tree, where each node in the tree corresponds to an interval of indices.  I'll build up the key ideas by starting with a simpler version of the data structure (that can support get and set but not the other operations), then add features to support the other features as well.

A simple scheme (supports get and set, but not add or stab)

Say that an interval $[a,b]$ is flat if the function $f$ is constant on $[a,b]$, i.e., if $f(a)=f(a+1)=\cdots =f(b)$.

Our simple data structure will be an interval tree.  In other words, we have a binary tree, where each node corresponds to an interval (of indices).  We'll store the corresponding interval $I(v)$ in each node $v$ of the tree.  Each leaf will correspond to a flat interval, and they'll be arranged so that reading out the leaves left-to-right gives us a sequence of consecutive flat intervals which are disjoint and whose union is all of $[1,n]$.  The interval for an internal node will be the union of the intervals of its two children.  Also, in each leaf node $\ell$ we will store the value $V(\ell)$ of the function $f$ on the interval $I(\ell)$ corresponding to this node (note that this interval is flat, so $f$ is constant on the interval, so we just store a single value of $f$ in each leaf node).

Equivalently, you can imagine that we partition $[1,n]$ into flat intervals, and then the data structure is a binary search tree where the keys are the left endpoints of those intervals.  The leaves contain the value of $f$ at some range of indices where $f$ is constant.

Use standard methods to ensure that the binary tree remains balanced, i.e., its depth is $O(\lg m)$ (where $m$ counts the current number of leaves in the tree).  Of course, $m\le n$, so the depth is always at most $O(\lg n)$.  This will be helpful below.

We can now support the get and set operations as follows:

$\text{get}(i)$ is easy: we traverse the tree to find the leaf whose interval contains $i$.  This is basically just traversing a binary search tree.  Since the depth is $O(\lg n)$, the running time is $O(\lg n)$.
$\text{set}([a,b],y)$ is trickier.  It works like this:

First, we find the leaf interval $[a_0,b_0]$ containing $a$; if $a_0 < a$, then we split this leaf interval into the two intervals $[a_0,a-1]$ and $[a,b_0]$ (thus turning this leaf node into an internal node and introducing two children).
Next, we find the leaf interval $[a_1,b_1]$ containing $b$; if $b < b_1$, we split this leaf interval into the two intervals $[a_1,b]$ and $[b+1,b_1]$ (thus turning this leaf node into an internal node and introducing two children).
At this point, I claim that the interval $[a,b]$ can be expressed as the disjoint union of $O(\lg n)$ intervals corresponding to some subset of $O(\lg n)$ nodes in the tree.  So, delete all the descendants of those nodes (turning them into leaves) and set the value stored in those nodes to $y$.
Finally, since we modified the shape of the tree, we'll perform any necessary rotations to re-balance the tree (using any standard technique for keeping a tree balanced).

Since this operation involves a few simple operations on $O(\lg n)$ nodes (and that set of nodes can be easily found in $O(\lg n)$ time), the total time for this operation is $O(\lg n)$.

This shows that we can support both the get and set operations in $O(\lg n)$ time per operation.  In fact, the running time can be shown to be $O(\lg \min(n,s))$, where $s$ is the number of set operations performed up until now.

Adding support for add

We can modify the above data structure so that it can also support the add operation.  In particular, instead of storing the value of the function in the leaves, it'll be represented as the sum of numbers stored in a set of nodes.

More precisely, the value $f(i)$ of the function at input $i$ will be recoverable as the sum of the values stored in the nodes on the path from the root of the tree down to the leaf whose interval contains $i$.  In each node $v$ we'll store a value $V(v)$; if $v_0,v_1,\dots,v_k$ represent the ancestors of a leaf $v_k$ (including the leaf itself), then the value of function at $I(v_k)$ will be $V(v_0)+\dots + V(v_k)$.

It is easy to support the get and set operations using a variant of the techniques described above.  Basically, as we traverse the tree downward, we keep track of the running sum of values, so that for each node $x$ that the traversal visit, we'll know the sum of values of the nodes on the path from the root to $x$.  Once we do that, simple adjustments to the implementation of get and set described above will suffice.

And now we can support $\text{add}([a,b],\delta)$ efficiently.  First, we express the interval $[a,b]$ as the union of $O(\lg n)$ intervals corresponding to some set of $O(\lg n)$ nodes in the tree (splitting a node at the left endpoint and right endpoint if needed), exactly as done in steps 1-3 of the set operation.  Now, we simply add $\delta$ to the value stored in each of those $O(\lg n)$ nodes.  (We don't delete their descendants.)

This provides a way to support get, set, and add, in $O(\lg n)$ time per operation.  In fact, the running time per operation is $O(\lg \min(n,s))$ where $s$ counts the number of set operations plus the number of add operations.

Supporting the stab operation

The stabbing query is the most challenging to support.  The basic idea will be to modify the above data structure to preserve the following additional invariant:

  (*) The interval $I(\ell)$ corresponding to each leaf $\ell$ is a maximal flat interval.

Here I say that an interval $[a,b]$ is maximal flat interval if (i) $[a,b]$ is flat, and (ii) no interval containing $[a,b]$ is flat (in other words, for all $a',b'$ satisfying $1 \le a' \le a \le b \le b' \le n$, either $[a',b']=[a,b]$ or $[a',b']$ is not flat).

This makes the stab operation easy to implement:

$\text{stab}(i)$ finds the leaf whose interval contains $i$, and then returns that interval.

However, now we need to modify the set and add operations to maintain the invariant (*).  Each time we split a leaf into two, we might violate the invariant if some adjacent pair of leaf-intervals have the same value of the function $f$.  Fortunately, each set/add operation adds at most 4 new leaf intervals.  Also, for each new interval, it is easy to find the leaf interval immediately to the left and right of it.  Therefore, we can tell whether the invariant was violated; if it was, then we merge adjacent intervals where $f$ has the same value.  Fortunately, merging two adjacent intervals does not trigger cascading changes (so we don't need to check whether the merger might have introduced additional violations of the invariant).  In all, this involves examining $12=O(1)$ pairs of intervals and possibly merging them.  Finally, since a merger changes the shape of the tree, if this violates the balance-invariants, perform any necessary rotations to keep the tree balanced (following standard techniques for keeping binary trees balanced).  In total, this adds at most $O(\lg n)$ additional work to the set/add operations.

Thus, this final data structure supports all four operations, and the running time for each operation is $O(\lg n)$.  A more precise estimate is $O(\lg \min(n,s))$ time per operation, where $s$ counts the number of set and add operations.

Parting thoughts

Phew, this was a pretty complex scheme.  I hope I didn't make any mistakes.  Please check my work carefully before relying upon this solution.


Show that maximum disjoint set problem is NP Complete

Given MIS is NP-Complete, we can reduce MIS to MDS. Let $G = (V,E)$ the graph we have for MIS problem. For every vertex $v_i \in V$, create a set $S_i$ with edges of $v_i$, however, be careful that write each edge element as $v_iv_j$ even if it is $v_jv_i$. Reduction is completed after creating the sets $S_i$. There is an independent set in $G$ of size $m$ if, and only if, there are $m$ disjoint sets where sets are taken from independent set's vertices.

This reduction can be performed in polynomial time since we traverse each vertex $v$ and its edges. It can be performed in $O(V+E)$. Additionally, given a collection of sets, we can verify if they are disjoint and there are at least $k$ of them in polynomial time.

Consequently, MDS is NP-Complete


Context free languages belongs to NTIME(n)?

Hint: Every context-free language is accepted by a pushdown automaton.


Can a Big-Oh time complexity contain more than one variable?

Yes, of course.  This is fine and perfectly acceptable.  It is common and standard to see algorithms whose running time depends upon two parameters.

For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph.  This is perfectly valid.  The meaning of this is there exists a constant $c$ and numbers $n_0,m_0$ such that the running time of the algorithm is at most $c \cdot (n+m)$, for all $n>n_0,m>m_0$.  In other words, if the exact running time is $f(n,m)$, we say that $f(n,m) = O(n+m)$ if there exists $c,n_0,m_0$ such that $n>n_0$ and $m>m_0$ implies $f(n,m) \le c \cdot (n+m)$.

Yes, it is perfectly appropriate and acceptable to say that the first stage takes $O(n)$ time and the second stage takes $O(m)$ time.

Important: make sure you define what $n$ and $m$ are.  You can't say "this is an $O(n)$ time algorithm" without specifying what $n$ is.  If $n$ isn't specified in the problem statement, you need to specify it.  For instance, see graph algorithms, where we typically define $n = $ # of vertices and $m = $ # of edges.

As far as whether you can call them $O(n)$ time, no, of course not -- unless you somehow know that $m = O(n)$.  Of course, if you know that $m = O(n)$, then it follows that $m+n = O(n)$, so an $O(m+n)$ time algorithm is also an $O(n)$ time algorithm.  But if there is no guarantee that $m = O(n)$, then you cannot call it an $O(n)$ time algorithm.

This is basic stuff.  You'll find it all over algorithms textbooks.


First you move your mouse. Most mice now in days works using a laser, the laser is able to tell it's moving over a surface, inside the mouse the data from the laser is being turned into digital signals, that are then sent through the cord or through Bluetooth or whatever system you use to the computer. The computer meanwhile is expecting to get signals like these, it's constantly checking to see if it's gotten a new signal from the mouse, and when it does it knows how to interpret those signals to move the pointer on your screen.

Now you click on an icon, and that is then the mouse sending a different signal for a click or double click, the computer registers the click and then figures out what do to handle the click, since your mouse was above an icon, lets say a music file you have sitting on your desktop, it knows to try and open or run that file.

To determine what exactly it means to open or run the file it may look at a few different things, you may have some settings for that file that you've set which tell it how to open, but more generally it goes based on the extension. Let's say it's a .mp3 file, well you probably have a default music player app, and the computer knows to open that app and gives it some information about the file you clicked, I'm not sure on the format, but it probably gives it the name and location of the file you clicked on. The music player app now takes that file and assuming it's correctly formatted as an mp3 then it will know how to read the data in the file, and it will parse through that data and start to send messages back to the operating system telling it to output sound.

The OS now will send data about what sound needs to be played to whatever the default or current audio device you have, lets say they are speakers. The speakers will receive these signals and know what sort of sounds to put out, and then they have components in them that can vibrate in different ways, and they are told how to vibrate by the singles that were sent and thus sound is emitted.


Why is the intersection of these two Languages Recursively Enumerable, not Recursive?

Let $L_1$ be the full language. Certainly, $L_3 \cap L_1 = L_3$, which by assumption is not recursive.

I didn’t fully follow your reasoning in the second paragraph, but you might want to think some more about which Turing machine “must lead to halting” refers to. In particular, a Turing machine for our $L_1$ will halt on every string, but this does not tell you that any subset of the full language is recursive.

Edit: I’ll try to address your comments here where I have more space.

We are dealing with a double set structure: At the lowermost level, we have words. Languages are set of words, but we are also talking about sets of languages, i.e., sets of sets of words, such as the set of regular languages. The relationship between regular, recursively enumerable and recursive languages happens on the upper level: Let $L$ be any regular language, which means that it is accepted by a finite automaton $\mathcal{A}$. Because every finite automaton $\mathcal{A}$ can be implemented as a Turing machine $\mathcal{M}$, we know that $L$ must also be a recursive language. Since every such element $L$ of the set of regular languages is an element of the set of recursive languages, the former is a subset of the latter.

This does not mean much on the level of individual words. Let’s again take the language $L_1 := \Sigma^*$ of all words. This language is decided by the Turing Machine $\mathcal{M}_1$ that always accepts. Thus, $L_1$ is in the set of recursive languages and every word “leads to halting” for the specific machine $\mathcal{M}_1$. Now let us consider the language $L_3$ of Turing machines that terminate on the empty input. It can be accepted by a universal Turing Machine $\mathcal{M}_3$, so the language is recursively enumerable (and we know that it is not recursive). Sure, every word in the intersection of $L_1$ and $L_3$ will make both $\mathcal{M}_1$ and $\mathcal{M}_3$ terminate and accept.

But how do you build a single Turing machine from that that still accepts the intersection and will reject everything else? The first attempt would be to simulate both Turing machines and accept if both accept. As soon as one rejects, you reject. Indeed, this machine accepts the intersection and proves that the intersection is recursively enumerable. But if $\mathcal{M}_1$ accepts and $\mathcal{M}_3$ diverges, your machine will also diverge. To reject, you would have to figure out in finite time whether $\mathcal{M}_3$ is diverging on the current input or just takes a long time to accept. This is not possible to do for all inputs.


Are asymptotic lower bounds relevant to cryptography?

I'll try to give a partial answer, since I'm not fully aware of how this issue is considered by the entire crypto-community (maybe repost on crypto.SE?).

I would say there are two "kinds" of cryptographers: Theoretical and  Practical. I will not try to tell them apart (every practical-cryptographer is also a bit theoretician..) but I'll say that for theoretical cryptography - this issue doesn't really matter. For any security parameter, there will be an instance size that will provide that security level, and that is usually all that we care about.

Practical cryptographers care a lot about the issue you mention. For a given security parameter (say $2^{1024}$) cryptographers try to come up with the most efficient protocols, shaving the constant as much as possible. Look for instance for NIST's AES or SHA-3 competition. The algorithms were required to be both secure and efficient.
The issue here is that the notion of security is somewhat different from the "theoretical" one, and sometimes is not really asymptotic.

A concrete example I can think of is the discrete log or the DDH assumption (the security of many cryptographic schemes are based on these assumptions). We assume that for some group $G$ computing the log takes $O(|G|)$ time. (We can't be sure: it might be that $\text{P}=\text{NP}$ and this problem can be solved in $O(\log |G|)$). Cryptographers DO care about the actual time it takes to compute the log. More accurately, they care alot about special cases for which computing the log is easy. In many papers you will see the sentence "Let $G$ be a group in which DDH
is hard". See this survey for families of groups for which DDH is believed to be intractable (unless P=NP).


Selection in expected linear time: Why am I getting $O(n)$ bound instead of $\Omega(n \lg n)$?

You started with the induction hypothesis $T(k) \le ck/3$ for all $k<n$, but you didn't prove that $T(n)\le cn$.  You concluded that $T(n) \le c_1 n$, for a different constant $c_1 \ne c$.  For the induction proof to work, you have to use the same constant in the induction hypothesis and the conclusion.


Pathological data is supposed to be data that makes things go wrong in
some way for your intended computation. It can be called
pathological when it is rare enough in actual uses, so that things
work OK most of the time. This can sometimes be made mathematically
more precise (for example with probabilities), but the use of the
word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for
pathological people, meaning those people who are allergic to
tomatoes. It can actually kill in some cases.  But people allergic to
tomatoes are very rare so that tomato dishes are considered excellent,
except in pathological cases.

There are many algorithms that, while having a worst case complexity
above the optimal one, are on the average as good or better than worst
case optimal algorithm. If you compare quicksort and merge sort,
quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst
case. But people will often use quicksort, because they both are time
$O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for
quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the
fact that the $O(n^2)$ time complexity actually occurs only on
pathological (implying bad but rare) cases.


The entropy of a given attribute is non increasing over  refinement of partitions. This means that the best possible partition is singletons (one value per set). This is the method used for discrete attributes in known algorithms such as ID3 or C4.5.

As a side note, the number of partitions is given by Bell's number.


Is the knapsack problem NP-hard when $v_i=i$?

No, this problem is in $\mathbf{P}$. The main point being that the sum of all the values is $1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$, which is polynomial in the input size. Without the extra restriction of $v_i = i$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input.

So we can define $DP[i][v]$, where $1 \leq i \leq n$ and $0 \leq v \leq \frac{n(n+1)}{2}$, to be the minimum weight needed to get a value of at least $v$, using only the first $i$ items. If it cannot be achieved, we'll set $DP[i][v] = INF$. The final answer is the maximum $v$ such that $DP[n][v] \leq W$.

The DP values can be calculated as follows:

$DP[i][v] = \min(DP[i-1][v], w_i + DP[i-1][v - v_i])$.

The first term considers the possibility of the $i^{th}$ item not being chosen, and the second term is the possibility that it is chosen.

So the entire problem can be solved in $\mathcal{O}(n^3)$ time and $\mathcal{O}(n^3)$ space, which can be reduced to $\mathcal{O}(n^2)$ space by just reusing two arrays of size $\frac{n(n+1)}{2} + 1$.


Optimizing Fleury's algorithm to work in O(|V|+|E|)

Because a bridge in current graph may not be a bridge in the primary graph. Note Fleury's Algorithm deletes an edge after you pass it.

Consider the following graph:

You start at $A$, then move to $B$ and delete the edge $AB$.

Now $BE$ becomes a bridge so the algorithm then chooses $BC$. However, $BE$ is not a bridge in the primary graph, so you cannot detect it in advance.

According to Wikipedia

  If there are no vertices of odd degree, all Eulerian trails are
  circuits. If there are exactly two vertices of odd degree, all
  Eulerian trails start at one of them and end at the other.

So finding an Eulerian trail is essentially the same as finding a cycle (if there are exactly two vertices of odd degree, add an edge connecting them and find an Eulerian cycle in the new graph).


Why the number of adresses stored on RAM is equal to $2^x$ when has "x" adress lines?

$2^{20}$ "data" is rather a vague value. If you have 20 bits for address lines you can possibly have $2^{20}$ combinations. If each address line represent 1 bit of data then you've got  total $2^{20}$ bits of data to store in a memory. However most machines store 1 byte of data for every address combination giving you $2^{20}$ bytes or $1$ MB


Yes, these type systems exist. They're generally referred to as "Set-theoretic Type Systems", and there's a good rundown of them here. They've been extended a lot, particularly with regards to subtyping and datasort-refinement types.

For a practical application of them, checkout their use in TypeScript.

Basically, union types correspond to untagged unions, and intersection types are a single value that matches two types. So we have rules that look like this:

If $v : T_1$, then $v : T_1 \cup T_2$ for any $T_2$
If $v : T_1$ and $v : T_2$, then $v : T_1 \cap T_2$

These are both commutative, so there's a symmetric union rule.

Note the difference between normal types: the unions here are untagged, and we have very little information when using a value of a union type, since we have no runtime way of determining which half of the union it is.

Likewise, a value matching an intersection type is not a pair, it's a single value that happens to typecheck against both of the types in the intersection.

Under this formulation, we can treat polymorphic and existential types as infinite intersections and unions:

$\forall a \ldotp T$ is $\bigcap_{S \in TYPE} [S/a]T$
$\exists a \ldotp T$ is $\bigcup_{S \in TYPE} [S/a]T$

That is, if a value typechecks against a polymorphic type, then it checks against any instance of that type. And if a value typechecks against an existential type, there must be some concrete type that it typechecks against.

As you might expect, introducing these usually makes type inference undecidable, though there is a lot of research going on in this area that I will not claim to be an expert in.


Optimizing a join where each table has a selection

When an SQL statement is turned into an execution plan, several optimization techniques are used. The use of indices allow to efficiently (without a full scan) select tuples that agree with a selection condition. Another technique in use is semantic optimization, id est, to turn a query into an equivalent one with better behaviour. To do so, identities of relational algebra are used.

For specifically, in the example, the identity between selection and product

$\qquad \displaystyle \sigma_{\alpha}(C \times O) = \sigma_{\beta \wedge \gamma \wedge \delta}(R \times P) = \sigma_{\delta}(\sigma_{\beta}(R) \times \sigma_{\gamma}(P))$

(with $\beta$ being the part of the condition $\alpha$ which refers only to attributes from $C$ and $\gamma$ the one with attributes from $O$) can be used. Informally worded this identity is "pushing selection through joins/product" (the identity holding for join too). The identity can be thought as a kind of rewrite rule, reading it from left to right. So the following identity holds in the example :

$\qquad \displaystyle \begin{align}
  &\pi_{Name}(\sigma_{Preferred=True \wedge Complete=False}(C \Join_{CustomerId = Id} O)) \\
= &\pi_{Name}(\sigma_{Preferred=True}(C) \Join_{CustomerId = Id} \sigma_{Complete=False}(O))
\end{align}$

Doing so, you do not waste time computing the product of irrelevant tuples of $C$ and $O$. The more selective the $\beta$ and $\gamma$ predicates are, the larger the gain is. And IMO, I don't think you can ever lose some time using this rule.
For a more formal treatment of this aspect of optimization, one can look at the Static Analysis and Optimization chapter of the Foundation of Databases book.


Show that it is undecidable if two Turing Machines accept the same language

Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:

Some given one T.
Another that loops forever.

If you could decide if they accept the same language, you'd be able to decide if T halts or not. This is impossible - see the halting problem.

This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.


Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

Your bounds seem to be correct, assuming $n$ is the length of $p$, though writing $T(C1) = O(\log n)^2$ is wrong on two counts. First, it should be $O(\log^2 n)$ or $O((\log n)^2$) on the right. While $O(\log n)^2$ has the same meaning, it's not a "closed form", rather like writing $O(\sum_{k=1}^n k)$ instead of $O(n^2)$. Second, $T(C1)$ looks like $C1$ is some parameter like the input length or the number of vertices, whereas you intended $T(C1)$ to be the time needed to compute $C1$. Better notation would be $T_{C1}$, say, and you could include the input length $n$ as a parameter.

Moreover, note that there are faster integer multiplication algorithms, and some of them are used in practice in cryptographic contexts (not necessarily the ones which are asymptotically best). So you can get even better bounds on the running time depending on the implementation.

The reason you couldn't find the time complexity is that the algorithms use a constant number of two very common operations, namely multiplication and inverse modulo $p$, so the running times can be read immediately by experienced practitioners. This is even the case with more complicated operations such as modular exponentiation.


You can find this algorithm analyzed at the very beginning of these lecture notes, or in these lecture notes (which consider a better variant of the algorithm but only analyze your variant), as well as in many other resources.

These are the first two hits when searching for makespan approximation.


How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?

Regarding the first part:

// Stage 1: Check length is even, change as / bs to As / Bs

and

// Stage 2: Change As and Bs in first half to as and bs

Are to find the word middle, then just compare the first half against the second half. Here is a SIMILAR picture for you at JFLAP:

As you can see, at state "q2", I came back to the tape's beginning, to really starts the computation at the state "q3".

After got at the state "q3" you can jump straight to you algorithm part:

"// Stage 3: Compare first and second halves"

And complete your Turing Machine. But this was your question 1.a) and now you want to solve the question 2.a)

To do it, you will only need to use the step "// Stage 3: Compare first and second halves", from you algorithm.

To do it using a Multi-Tape Turing Machine, you are going to need 4 tapes, the word is to be placed at the tape 1 and the others tapes must to be clean, i.e., contain only blank symbols:

First step, if the tape 1 has only the blank symbol, accept the language.

Second step, if  the only symbol not marked at tape 1 is the blank symbol, reject the language.

Third step, is to copy the first symbol not marked from the tape 1 to the tape's 2 end. Then mark it at the tape 1.

Fourth step, is to copy the whole tape 1 to the tape's 3, and the tape 2 to the tape 4.

Fifth step, is to compare both tapes 3 and 4 are equal using yours algorithm step "// Stage 3: Compare first and second halves", but instead of failing to accept the language, go to the step Sixth.

Sixth step, if they are equal accept the language. If they are not, go to the Second step.


First, "fastest" is an ambiguous term--it can refer to latency or throughput/bandwidth.

Second, DMA is orthogonal to interrupts and polling.  I.e., the completion of the DMA can trigger an interrupt or be determined by polling an I/O register (or the memory that is being written in some cases).  (Explicit processor copying to/from memory is the alternative to DMA.)

Third, the tradeoffs between polling and interrupts will vary depending on the hardware.  In general, because an interrupt involves saving and restoring processor state, it has higher latency (saving and restoring state takes time).  When I/O events are extremely frequent and of a limited number of types, the overhead of repeatedly reading an limited number of I/O registers will be less than the overhead of context switching.  (Obviously, increasing the number of events polled--in terms of unique I/O registers or memory accesses--decreases the relative disadvantage of interrupts.)

With polling, the polling thread is taking up processor resources that could otherwise be used to run other code and the reading of an I/O device register (or ordinary memory location) when the polled event has not happened (the probed value has not changed) uses bandwidth that could otherwise be used for productive purposes.  Excessive polling could also reduce the availability of buffers between processors and I/O devices, delaying fast I/O communication behind slow communication (and in some cases the I/O bus is optimized for larger packets so small read responses [which do not communicate any new information] would waste bandwidth).

However, hardware can optimize interrupts in several ways.  It can coalesce interrupts at the I/O device or at an intermediate point between I/O devices and the processor.  At the processor, it is possible to fold interrupts together so that instead of immediately returning from an interrupt (with the overhead of restoring state) a pending interrupt is handled.  Some processors also have shadow registers that are used to avoid the need to save and restore state on interrupts.  (Software can also combine the use of interrupts and polling by performing some polling while in the interrupt handler.  This can reduce the number of interrupts.)

In theory, hardware could also reduce the overhead of polling with multithreading and throttling the execution of a polling thread that is not performing useful work.  (Even with efficient polling--where every read indicates an I/O has completed--multithreading can allow work to be done while waiting for the read of the I/O device register to be completed--this tends to have relatively high latency.)

In a very theoretical sense, I/O device register values could be pushed into cache when they change (a variant on DMA).  Such could reduce the wait time for reading such values (helping both interrupt handlers and polling) and facilitate hardware thread throttling (because the processor could quickly determine that no change had occurred).  However, such is incompatible with how most ISAs are defined and with how I/O devices are implemented, and such would greatly increase the complexity of the system.


Are there any PSPACE problems that don't exist in NP-Hard?

Assuming we use polytime reductions in both, all PSPACE-hard problems are NP-hard, which follows directly from the definition and from the easy fact NP$\subseteq$PSPACE: a languages $L$ is PSPACE-hard if all languages in PSPACE polytime-reduce to $L$. If $L$ is PSPACE-hard then in particular, all languages in NP polytime-reduce to $L$, and so $L$ is also NP-hard.

On the other hand, there are problems in PSPACE which are not NP-hard, for example $\emptyset$ and $\Sigma^*$. If P=NP then all other problems in PSPACE are NP-hard, since every non-trivial language (a language different from $\emptyset,\Sigma^*$) is NP-hard in this case. If P$\neq$NP then every problem in P also belongs to PSPACE and is not NP-hard.


Constructing a pushdown automaton that accepts L*

The Kleene star is, as you know, the union $\bigcup_n L^n$ of arbitrary powers $L\cdot L\cdot\ldots\cdot L$ of $L$.

If $M$ is the automaton that accepts $L$, then in order to make an automaton for $L^*$ you basically have to make it possible to restart the automaton after accepting $L$. Be careful in choosing final state or empty stack acceptance.


You effectively have a directed graph here, where your vertices are the entries of your array, and you have an edge $(i,j)$ between entries $i$ and $j$ iff $j$ depends on $i$. What you want is a topological sort of this graph (https://en.wikipedia.org/wiki/Topological_sorting).


ignoring overflow in two's complement addition of numbers with different signs[specific case]

Okay, let's take a look at your example:

 1001010
+0010101
--------
 1011111

Your numbers here only have 7 bits, so we have a smaller range than we typically deal with.  Nevertheless:

$1001010$ is

$-64 + 8 + 2$, which is $-54$.

$0010101$ is

$16 + 4 + 1$, which is $21$.

$21-54$ is $-33$.  Let's see whether our answer matches up:

$1011111$ is

$-64+16+8+4+2+1$, which is $-33$.

An intuitive way to think about this is that the number space is divided entirely in half (with $0$ acting as a positive number).  So, with the standard 8 bits, your numbers range from $-128$ to $127$.  There is no positive number from within that set that you could add to a negative number from that set and get a number either above $127$ or below $-128$.


To answer your first question: Spinlocks are only useful in a multiprocessing environment.
Spinning is waiting. If you're waiting for a lock to be released, and it must occur on the current CPU because there are no other CPUs, then a context switch must occur for the lock to be released. It follows that the current thread should just sleep, because it will need to anyway.
Of course, in a single-CPU environment, you can still spin-wait for other types of resource, such as a hardware device.
As Joppy indicated in the comment, putting a thread to sleep is a much heavier-weight operation than sitting in a loop. Whether or not it's worth spinning depends on a bunch of things, such as how expensive it is to sleep and context switch, and how long the lock is likely to be held.
There is a huge design space here. The default behaviour of Solaris kernel locks, for example, is to spin if the owner is running on another CPU, and sleep otherwise, the theory being that if the owner is making progress, it's more likely that the lock may be released soon. As a nice bonus, this automatically does the "right" thing on a single CPU.


You missed the second print instruction.

We can rephrase the algorithm as follows:

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    f(n/100)
    print n % 10
  }

Now we can do "recursion unrolling":

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      f(n/10000)
      print (n/100) % 10
    }
    print n % 10
  }

One more level:

function f (integer n) {
  if n equals 0 {
    print 0
  } else {
    print n % 10
    if n/100 equals 0 {
      print 0
    } else {
      print (n/100) % 10
      if n/10000 equals 0 {
        print 0
      } else {
        print (n/10000) % 10
        f(n/1000000)
        print (n/10000) % 10
      }
      print (n/100) % 10
    }
    print n % 10
  }

Suppose for the moment that all of n, n/100, n/10000 differ from zero. The executed code is then

print n % 10
print (n/100) % 10
print (n/10000) % 10
f(n/1000000)
print (n/10000) % 10
print (n/100) % 10
print n % 10

Hopefully you can see the pattern.

The printed string is always an odd-length palindrome with a 0 in the middle, a property which you can prove by induction.


I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ invertible on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/straightforward case, and so the left/rightness is flipped, and you have full inversion. The domain matters, as usual.
As pointed out in the comments, this is not necessarily the case for some kinds of the functions you give—re-encrypting after retrieving the original value $(g \circ f \circ g)(x)$ may not necessarily give the same encrypted code $g(x)$; but then, it’s not nearly useful to consider $g$ a function, for the normal rules don’t apply. Notice that we still take the value passed to $f$ (here, the decryptor) to be an encrypted value; we assume the domain of $f$ to be properly encrypted values. Mathematically we are unable to apply $f$ to anything else (though I could have used a name like $y = g(x)$). Programmatically, of course, the type system may permit values outside the domain to be given, and then we either get an error or garbage. Again, I consider those irrelevant and outside the domain here.
Versioned serialization actually doesn’t have this issue—a function that deserializes or serializes a different version than $f$ or $g$ is not $f$ or $g$, respectively, and therefore not relevant! The domain matters.
We also have $\forall x$ in the domain $h(x) = x$ by definition, and that means every $x$ is a fix-point of $h$ (this is trivially true for any identity).


Showing that a language satisfies the pumping lemma

Assume that pumping lemma is satisfied for $L$. Let $N$ be the pumping length.

Now take $z = ab^Nc^Nd^N \in L$. $|z| = 3N+1$ and hence this string can be pumped.

For this string, every choice of $u,v,w,x$ and $y$ that satisfies the conditions of pumping lemma will have a choice of $i \in \mathbb{N}$ such that $uv^iwx^iy \not\in L$. This is a contradiction. Hence $L$ is not context-free.


Hint: Your approach can be completed and you need to change only one word in the description of $L_1$ to get a description for $L_3$ that works.


Sublinear Homomorphism Property Testing Counter Example

Thanks to the help in the comments I was able to unfixate and find an answer to the question. I prove $\delta\left(f\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$.

Let $h:\mathbb{Z}_{n}\to\mathbb{Z}_{n}$ be an homomorphism.

• If $h\left(1\right)=f\left(1\right)$ then $h\left(1\right)=1$ and h is the identity function, since $h\left(0\right)=0$ and $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ due to homomorphisms definition and properties. We get $\delta\left(f,h\right)=1-\frac{1}{\sqrt{n}}\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$ (since they disagree on $n-\sqrt{n}$ values).

• Otherwise, $h\left(1\right)\neq f\left(1\right)$, that is $h\left(1\right)\neq1$. Assume by contradiction that exists $x\in\mathbb{Z}_{n}$ such that $h\left(x+1\right)=h\left(x\right)+1$, but due to homomorphisms definition we get $$h\left(x+1\right)=h\left(x\right)+h\left(1\right)=h\left(x\right)+1$$ which is a contradiction to $h\left(1\right)\neq1$. Since our function $f$ maintains that $$h\left(x+1\right)=h\left(x\right)+1$$ for $x\in\mathbb{Z}_{n}\backslash\left\{ q\sqrt{n}|0\leq q\leq\sqrt{n}-1\right\}$ , which means $n-\sqrt{n}$ “bad” pairs of $x$ and $x+1$. This means that in order to get any homomorphism, including $h$, we have to change at least one value for each pair, which means at least $\frac{\sqrt{n}-1}{2}$ values changed for each interval $\left[q\sqrt{n},\left(q+1\right)\sqrt{n}\right)\cap\mathbb{Z}_{n}$ (where $0\leq q\leq\sqrt{n}-1$), otherwise due to to the pigeonhole principle we have two consecutive values that are unchanged which is again a contradiction since then $h\left(x+1\right)=h\left(x\right)+1$. So in total we have at least $$\sqrt{n}\frac{\sqrt{n}-1}{2}=\frac{n-\sqrt{n}}{2}$$ values changed, which means $$\delta\left(f,h\right)\geq\frac{1}{2}-\frac{1}{2\sqrt{n}}$$


As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:

Bartek's suggestion: Use an array to store all the entries computed so far.
You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
Use matrix powering. There are vectors $x,y$ and a matrix $A$ such that $T[N] = x'A^N y$. This approach is very similar to the previous one.
Find an explicit solution to your recurrence $T[N] = \sum_{i=1}^4 c_i \lambda_i^n$ (there are other possible forms, but this is the most probable), and use this formula to calculate $T[N]$ directly.


Minimum words in a string given a dictionary

One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

Example:-

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)->f(boardrocks)
                ->f(rocks)
                ->f(s)

(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length m of the string in an array.

So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]


Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable

Given a Turing machine $M$ of $n$ states and a word $w$, you could solve the halting problem for $(M,w)$ if you knew the maximal number of steps $f(n,w)$ that a Turing machine $M$ with $n$ states can spend on $w$. If your language were decidable then you could compute $f(n,w)$ by trying all Turing machines on $n$ states until you find one in $B(n,w)$.

I'll let you figure out the details on your own.


Using FFT to solve pattern matching problem with don't cares

The idea behind the NOT is that $T^c P^R + TP^{Rc}$ is measuring disagreement rather than agreement. Disagreement can come in two ways: text says $0$, pattern says $1$ ($T^c P^R$); and text says $1$, pattern says $0$ ($TP^{Rc}$). That's why you need two summands.

In more detail, $T^cP^R$ measures the number of indices at which the text was $0$ and the pattern was $1$; $TP^{Rc}$ measures the number of indices at which the text was $1$ and the pattern was $0$; and their sum measures the number of indices at which the text and the pattern didn't match.

When the alphabet has size $r$, you can use a similar approach with $r$ summands (an even simpler solution uses $r(r-1)$ summands). I'll let you figure out the details. (No hints will be given, and solutions won't be verified.) Extra points if you manage to do this with the (possibly) optimal $\lceil \log_2 r \rceil$ summands.


center star alignment induces optimal alignments on pairs with the center string?

$S'_1$ indeed can have many extra gaps over $S_1$, but it doesn't matter and the distance $d(1,j)$ between the final strings in the MA: $S'_1$ and $S'_j$ would be exactly the same as $D(S_1, S_j)$.

Why? when we start the $j$ iteration, we do an optimal global alignment between $S'_1$ and $S_j$. At first, it looks as if $S'_1$ might contain disturbing gaps, which will cause the distance to get larger than the distance to $S_1$, and helpful gaps which will cause the distance to get smaller than the distance to $S_1$. Let's show that both aren't really helpful or disturbing! suppose S1 = abc:

Disturbing gap - e.g. S'1 = ab_c and Sj = abc. as $\delta(-,-)=0$, whenever we encounter a disturbing gap at $S'_1$ we can just add an extra space to $S_j$ at no cost and get the same distance.

Helpful gap - e.g. S'1 = ab_c and Sj = abxc. It isn't really helpful, as if the global alignment would have wanted to add a gap to $S_1$, it would just add it - it makes no difference that that gap was there before we started the alignment...

Gaps added after the $j$ iteration - if the center star algorithm will add gaps to $S'_1$ in iteration $k > j$, it will always adjust strings from previous iterations with gaps at the same place, including $S_j$ - and again because $\delta(-,-)=0$ it doesn't make any difference.

To summarize - as there's no help or disturbance, the alignment distance would be exactly as the global alignment $D(S_1, S_j)$ would have wanted it, plus some extra aligned gaps which can not disturb our distance.


Will floating point code return the same arithmetical results on two different computers?

As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot execute the same machine code on both Intel and ARM, so this answer is only hypothetic. Even on different Intel processors you have to take special care that exactly the same machine code gets executed. Some third party libraries like Intel-MKL use different machine specific code on different processors, and other libraries like FFTW measure speed at runtime, and select different algorithms (and hence different code) based on the outcome of these measurements.

Sometimes the compiler is able to inline a certain function (for example your rounding logic), and then you can end up with different results for identical input to that function at different parts of your code. Another very real non-reproducability for distributed floating point computations are potential reductions are the end of the computation. Because the result here depends on the order of the reduction steps, it is very easy to end up with slightly non-repreducible results.

I have run into the issues in the past, but never considered this to be a reason to switch to fixed-point algorithms. For robustness problems of "computational geometry" related code on the other hand, I consider integer or fixed point arithmetic to be an appropriate solution.

  Should I use fixed-point algorithms to circumvent this possibility?

In conclusion, there are several issues related floating point numbers, and even some problems where floating point numbers are not the most appropriate solution, but in general floating point arithmetic is still the way to go. So no, you should not abandon floating arithmetic in general, but only in the specific cases where it causes unsurmountable robustness problems.


Why doesn't Quantum Turing Machine contradict with Church-Turing thesis

Quantum Turing machines can be simulated by classical Turing machines. See Deutsch's fundamental paper Quantum theory, the Church-Turing principle and the universal
quantum computer.


You can use Xiaolin Wu algorithm, but the concept is not restricted to straight lines, it handles circles, ellipses, any kind of functions. Moreover this is concept of fast antialiasing, if you need some polyline you have to apply it for every segment. If you meant curves, these are locally flat segments, so this concept is still applicable.

The thin line might described $1px$ lines, but if you need thinner width (less than $1px$) the common algorithm that comes to mind is Gupta-Sproull, which is not that common due to computation time. The same is applicable here like in the Wu case, it is not limited to straight lines.

The idea of drawing lines (probably with Bresenham) and then blurring is more computationally expensive and weights are not normalised, which gives feeling of thicker lines.

The concepts described can easily be extended to thicker lines (using Bresenham and applying antialiasing to the outter layer) or even varying width lines (with Bresenham extension - the Murphy algorithm).

Techniques like MSAA or FXAA are too expensive, unless implemented on GPU with a lots of lines and no concern about perceptible width. After reading about Mathematica, it uses MLAA (Morphological Anti-Aliasing), graphics is rendered on GPU, also Mathematica's reference supports this statement merely by looking at de Moiré patterns.


Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

Knowing that integer programming (ILP) is NP-complete, it follows that mixed integer linear programming (MILP) is NP-complete too as MILP generalizes ILP.

My guess is that your thinking and feeling comes from insufficient testing: you don't have enough test cases with different structure, and you don't mention what algorithms you use. Even though both problems are hard, there are (even exact) algorithms that perform well on suitably structured instances. You should look at where the really hard instances are (they are not necessarily large), and try running your algorithms again.


Extracting maximum information from a set of exam answers and their scores

Hardness

Recovering the correct answers to the exam is NP-hard.  I'll show how to reduce one-in-three 3SAT to it.

Suppose we have a 3CNF formula $\varphi$ on $N$ variables $x_1,\dots,x_N$.  The $i$th question on the exam is "Is $x_i$ true?"  There is one answer sheet per clause of $\varphi$.  If $\varphi$ contains a clause mentioning variables $x_i,x_j,x_k$, say $x_i \lor \neg x_j \lor x_k$, then there's a corresponding answer sheet that has answered "Yes" to question $i$, "No" to question $j$, "Yes" to question $k$, and left all other questions blank, and this answer sheet received a score of exactly 1.

Now if you can extract the correct answer to all of the questions, then you can extract a satisfying assignment for the corresponding one-in-three 3-SAT problem -- a task that is NP-hard.

Therefore, you should not expect to find any efficient algorithm for your task (i.e., to extract the correct answers, given the scores on the answer sheets), at least in the worst case.

That's the bad news.  Now for the good news:

Algorithms

In practice, a good way to approach your problem might be to throw a SAT solver or ILP solver at it.  This sounds like the kind of problem that they might be effective at, in practice, if $N$ is not too large.  Your problem can be readily formulated as an instance of integer linear programming (ILP), or indeed as an instance of SAT.


Linear programming formulation of cheapest k-edge path between two nodes

The simplest way to compute the shortest path from $s$ to $t$ that traverses exactly $k$ edges is by increasing the size of the graph $k$-fold.

In particular, make $k$ copies of the vertices and $k-1$ copies of the edges, where for each edge $(u,v)$ in the original graph, we add an edge from the $i$th copy of $u$ to the $i+1$th copy of $v$ (for all $i$).  Now look for the shortest path from the 1st copy of $s$ to the $k$th copy of $t$ using a standard algorithm (e.g., Dijkstra's algorithm).  The running time will be $O(kn+km\lg(kn))$.

Only you can determine whether this kind of formulation will be compatible with your additional constraints and objective function (since you haven't told us what they are), but this kind of modification to the graph is a general approach for this sort of problem that is pretty flexible and might meet your needs.

You could presumably also combine this with your network flow / LP formulation.  Now there will be no cycles that can show up, as the resulting graph is acyclic (a dag).  I don't know if that will meet your needs.


Because it keeps the B-tree balanced?

In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, people would have suggested that by now. I believe that the reason why this is the case is that the current algorithm is the simplest way possible to solve the B-tree problem. i.e. there's no useful further reduction of the problem to find.

That said, you have to be consistent but you are free to decide whether you want a tree that for example has either left or right bias but never both.

When deleting you also have a choice in whether to borrow from left or right first, or whether to merge with left or right first. You need to do both but you can attempt either left or right first.

The B-tree algorithm has some ambiguity or arbitrary things about it. Some aspects of it can be done in any number of ways, the end result will be the same. This can be confusing if you are not used to dealing with such arbitrary and/or ambiguous things.


A fuzzy string matching algorithm for finding all occurrences from a set of strings in a large string

One approach: Build a BK tree containing the terms in your term list.  Given any word $w$, this lets you efficiently find the term that is closest to $w$ in Levenshtein edit distance.

Now the problem becomes easy.  Do a linear scan over the document.  For each word, look it up in the BK tree to find the closest match in your term list, and if it is close enough, output it.

Alternatively, you could read Peter Norvig's tutorial on spell checking, and the references he lists there, and try using that.  They might be especially effective if your fuzzy matching only considers very small Levenshtein edit distance (e.g., distance 1 or 2).


I dont know the solution of your problem: especially as we dont have a limit on the ID's. My "guessing" is that you cannot solve this problem with complexities you listed.

I will only answer your following question:

Does the usage of randomized leader election is eligible in the case of graph as described above?

I dont suggest using leader election. Its lower bound does not meet your requirement (it is still an open problem to solve the election problem with $O(D)$ time and $O(m + n \log n)$ message, Peleg 199*). The known randomized election algorithms so far do not work on arbitrary graphs. There is a new algorithm that runs in arbitrary graphs (but requires knowledge of $n$). This algorithm is not yet officially published (due to Peleg et al. 2012).

I will list the references later.


Tight instance for unweighted maximum coverage problem?

Here is one example:
take the universe   $$U=\{u_1,\dots,u_n,v_1,\dots,v_n\}$$
$S_i=\{u_i,v_i\}$ for $i=1,\dots,n$ , and  $S_{n+1}=\{u_1,\dots,u_n\}$, $m=n+1$, $k=n$


Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?

The question seems based on a faulty premise. There are multiple algorithms that Johnson invented, and you're confusing them.  One of his algorithms is for finding shortest paths (that's the one Wikipedia article talks about), another is for enumerating all cycles (that's the one the Stack Overflow answer cites).  They don't have the same running time.

Second, you're using some random person's code, but maybe that code sucks and isn't a good/valid implementation of the algorithm.  We don't do questions about code here.

Also, as David Richerby says, you obviously can't output all cycles in polynomial time if there are exponentially many of them (where there can be).  Therefore, you shouldn't expect an algorithm to enumerate all cycles with polynomial running time.

Finally, you can't disprove an asymptotic running time analysis by benchmarking it on 6 points.

I think you need to read Johnson's original paper, understand it, and implement it yourself.  Sometimes there are no shortcuts.


Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011

They clearly say that the example is only given as an example. If you believe you need 5 parity bits - use 5 bits. They use 4 bits in their example for no good reason.
True, they still wish you to mark it clearly. I guess the reason is (a) to make sure you know that the parity comes in powers of 2, and (b) to ease their grading. note you should not use positions 3,5,11, and 13! these are again only their example, and the note below the example clarifies you need not pay attention to it.

(at least, that's the way that I understand the question. There is a small ambiguity there that allows one to understand it the way you did)


Here are some ideas for you to start thinking.

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).

More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L_m$ for all $m$, and $3 \in L_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L_m$ (why?).

It remains to determine $L_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.


Complexity of a set partition derived problem

A set is a multiset (in which every element occurs once) and your partition problem can be used to find a subset of $S$ whose sum is $k$. [Note 1] So if there were a polynomial-time solution to your partition problem, it could easily be used to solve the subset sum problem in the same amount of time.
So the problem is NP-complete, but that doesn't stop it from having a pseudo-polynomial time solution. There are well-known DP algorithms to solve the subset sum problem which are polynomial in the magnitude of the inputs. Time complexity is always expressed as a function of the size of the inputs, as measured (for example) by the number of bits it takes to represent the input. The magnitude of a number is exponential in the size of the number (eg, a number represented in 100 bits could be as large as $2^{100}$). So time complexity polynomial in magnitude is still exponential in problem size.
In your problem, $n$ is a measure of problem size, whereas $k$ only measures numeric magnitude. So they are very different kinds of parameter.
Here's another longer explanation of pseudo-polynomial time in a StackOverflow answer.

Notes

Let $S$ be a set for which we seek a subset whose sum is $k$. Without loss of generality, we can assume that $\Sigma S \le 2k$ (because a solution for $k' = \Sigma S - k$ leads directly to a solution for $k$ using the set difference from $S$.) If $\Sigma S = 2k$ then a solution to the multiset partition problem yields two solutions to the subset sum problem. Otherwise, we form the multiset $S' = S \cup \{2k - \Sigma S\}$.  Obviously, $\Sigma S' = 2k$ and the element we added has a value less than $k$. We then compute the multiset partition of $\langle S', k\rangle$, which must be a partition into two pieces, at most one of which is a multiset (because there is at most one repeated element in $S'$, the one we added). If the first subset in the partition does not include the element we added, it is a solution to the original problem; otherwise, the second subset is.
Computing $\Sigma S$ and examining the result of the multiset partition solution are both linear time. So if the multiset partition algorithm were polynomial time, so would be the derived subset sum algorithm.