Comparing floating-point numbers as integers In the article http://floating-point-gui.de/errors/comparison/, a method for comparing floating-point numbers is suggested:

There is an alternative to heaping conceptual complexity onto such an apparently simple task: instead of comparing a and b as real numbers, we can think about them as discrete steps and define the error margin as the maximum number of possible floating-point values between the two values.
This is conceptually very clear and easy and has the advantage of implicitly scaling the relative error margin with the magnitude of the values. Technically, it’s a bit more complex, but not as much as you might think, because IEEE 754 floats are designed to maintain their order when their bit patterns are interpreted as integers.

So instead of some complex variant of abs(b - a) < ε, we interpret a and b as integers and find abs(b - a) < ε(steps(a, b)) where ε is somehow variable with regards to the density of floating-point numbers in the vicinity of a and b. But how exactly?
Also, does this method really alleviate checking for NaNs and Infs? Or are some of these "heaps of conceptual complexity" inevitable if you want a solid, generic method of floating-point comparison?
The following C code produces 1677722:
#include <stdio.h>

int main(int argc, char *argv[])
{
    double x, y, z, a, b;
    int steps;

    sscanf("0.1", "%f", &x);
    sscanf("0.2", "%f", &y);
    sscanf("0.15", "%f", &z);

    a = x + y;
    b = z + z;
    steps = *(int*)&b - *(int*)&a;

    printf("%d\n", steps);
}

Edit: Rephrased so the word "discrete" is not misused. Rewrote "steps(a, b) < ε(a, b)" into "abs(b - a) < ε(steps(a, b))" to indicate that it may still just be floating-point operations, but that ε is chosen variably.

There are a few fine tricks in the IEEE P754 format, which allows the use of integer operations for comparisons, or for rounding... It is useful for hardware implementations, for CPUs without an FPU, for some optimized libraries that need fast comparisons...

Caveats:
- The sign bit (MSB) must be handled separately.
- NaNs must be checked.

When comparing 0, denormals, normals or infinites of the same sign, integer comparisons work for floating point numbers.

Answer:

I think what this is describing is a matter of scaling.

Say you are comparing two floating-pointnumbers with a precision to two decimal places.

If you multiply both by 100 you have raised their values by two orders of magnitude, and end up with integers to compare.

This can be computationally more efficient, since every flop takes more time than an intop.


Can this question be solved without knowing the Page Table Entry? I'm preparing for the exams and this question came up -

  Consider a machine with $64MB$ physical memory and a $32$-bit virtual address space. If the page size is $4KB$, what is the approximate size of the page table?
  (A) 16MB
  (B) 8MB
  (C) 2MB
  (D) 24MB

The way I've solved it -
Physical Address Space = $64MB = 2^{26}B$
Virtual Address = $32$-bits, $\therefore$ Virtual Address Space = $2^{32}B$
Page Size = $4KB=2^{12}B$
Number of pages =$\,\Large\frac{2^{32}}{2^{12}}$$=2^{20}$ pages.
Number of frames =$\,\Large\frac{2^{26}}{2^{12}}$$=2^{14}$ frames.
$\therefore$ Page Table Size = $2^{20}\times 14\,bits \approx 2^{20}\times 16\,bits\approx 2^{20}\times 2B= 2MB.$

Some books claim the answer to be $8MB$ and I don't see why, but that confuses me.
Is this the correct way to solve it? Is the answer correct?

Your answer and calculation is correct, if we used a one-level page table.

However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like.

A two-level page table is probably a more likely implementation strategy.  The first 9 bits of the virtual address will be used as an index into the first-level table; they yield the entry in the second level.  The next 11 bits of the virtual address will be used as an index into the second-level table.

With this strategy, the size of the entire page table is $1+k$ pages, or $(1+k) \times 2^{12}$ bytes, where $k$ is the number of second-level table entries.  The worst case is $k=2^9$, in which case the entire page table takes up approximately $2^9 \times 2^{12} = 2^{21}$ bytes, i.e., 2 MB.  In other words, the worst case for a two-level page table is approximately the same as the size of a one-level page table.  However, the best case is much less.

I don't know how the books got 8 KB, but that seems clearly wrong, absent further assumptions; that would only allow 4096 entries in the entire page table, which clearly isn't enough to maintain a virtual-to-physical mapping for all of virtual memory.

obvious it can be solved. u can calculate the size of page table entry easily.

size of page table entry = No. of bits used for frame number(convert it into byte), here bits in frame no. is 14 bits so it is approximately equal to 2 byte. so size of each entry of page table be 2B.


Detection of redundant boolean constraints I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin transformation. From the nature of my problem I know that there are redundant constraints. For example, I have a rule:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4)) \,\,\,\,\,\,(1)$$

and another:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4), \:OR\:(x5,x6))\,\,\,\,\,\, (2)$$
where $x_i$ are inputs. Both constraints have in common subnodes, for example $OR (x1,x2)$. Due to this I know that there is no point in having both constraints - if the first one becomes FALSE, then the second equals FALSE too. So the second one is redundant. This example is the easiest. One more, closer to what might be found in my formula:
$$AND\:(x1,\:x2,\: OR \:(AND \:(x3,x4), \:AND\:(x5,x6)))\,\,\,\,\,\,(3)$$
and the second one:
$$AND\:(x3,x4)\,\,\,\,\,\,(4)$$
In this case, I can simplify the first one to the form of:
$$AND\:(x1,\:x2,\:AND\:(x5,x6))\,\,\,\,\,\,(5)$$
due to (4).

I prefer to have a lot of small rules (by a lot I mean $10^3$ or $10^4$, which in CNF become $10^5-10^6$ of clauses).  The rules are not complicated - 10 ANDs and ORs and 20-30 inputs per rule at most, but they are usually much simpler.

Is there an efficient way to remove such redundancy from a formula? Is it possible with CNF formulation or I should use some other representation of the formula (BDD, for example)?  Any help and directions will be useful.

The simplification you're describing is called subsumption.  It's a standard technique and some SAT solvers (e.g. minisat) will apply it along with other simplification techniques as a preprocessing step before attacking the SAT problem itself.  In particular, subsumption and equivalent variable substitution together, applied to the generated CNF formula, are enough to do the common subformula elimination you described in the question.  That's because each circuit transformation yields an output variable, and output variables derived from the same circuit can be efficiently identified and reduced to references to a single variable.  After that normal subsumption rules applied to clauses will eliminate the common subformulas.

If you're using a solver that doesn't do this preprocessing, then you can do thr rough equivalent of it during conversion to CNF.  First you'll need to apply duplicate circuit suppression while you're doing the Tseitin tranformation.  As you're doing the transformation to CNF, memoize each circuit you've converted. If you encounter the circuit again, skip the circuit conversion and use the same output variable that you used for the memoized circuit.  Once you've converted everything to clauses, do normal clause subsumption, i.e. check each clause A against every other longer B clause to see if A's literals are a subset of B's.  If so, then A subsumes B and clause B can be discarded from the formula.

there are basically 3 fundamental techniques that can be found in various algorithms for solving SAT, and there is a lot of research on this topic in SAT solver minimization/ simplification heuristics, often integrated into leading solvers. in other words a lot of this logic is already built into good SAT solvers and it is often treated as an optimizing "black box" by practitioners.

KJ mentions subsumption in his answer.
Davis-Putnam algorithm & DPLL use subsumption & another technique called "unit propagation". this applies to formulas where there are some single-literal clauses. the truth value can be "propagated" to other clauses in a sort of chain-reaction that also can trigger other new simplifications such as subsumption.
a more general technique can be seen in the Quine-Mccluskey method of generating/ enumerating minterms and new more efficient "minterm covers". this can lead to exponential blowup but find simplifications that are not available from unit propagation or subsumption.

another more general/ emerging technique is to look at clause-variable graphs (eg Decomposing SAT problems by Herwig) which can reveal the overall structure of the SAT instance and "dependent vs independent variables" also known as "backbone" related elements (active area of research).


Is there an algorithm that can solve any two-player game? Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.

Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors "White's turn" and "Black's turn".

Given a directed graph $G$ with such a two-coloring, with one priveleged node called the "initial node", a strategy for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:

$s$ is defined only on nodes at which it is $P$'s turn.
If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.
If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.
$s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.

Now, I'll call a complete path through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called endstates. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.

Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.

It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.

Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?

I don't mind if no such algorithm is actually known, but is there an existence or impossibility proof?

(Note that you're excluding games with randomness, such as backgammon.)

Yes. In particular, endgame tablebases use most of such an algorithm.

Wbool,Wfull,Bbool,Bfull = set(),set(),set(),set()
keep_going = False
for v in nondraw_endstates:
 keep_going = True
 if is_a_victory_for_white_(v):
  Wbool.insert(v)
  Wfull.insert([v,0])
 else:
  Bbool.insert(v)
  Bfull.insert([v,0])
n = 1
while keep_going:
 keep_going = False
 for v in Wbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Wbool:
    continue
   if white's_turn_(u):
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Wbool:
     avoidable = True
     break
   if not avoidable:
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
 for v in Bbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Bbool:
    continue
   if not white's_turn(u):
    Bbool.insert(u)
    Bfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Bbool:
     avoidable = True
     break
    if not avoidable:
     Bbool.insert(u)
     Bfull.insert([u,n,v])
     keep_going = True
     continue
 if (initial_node in Wbool) or (inital_node in Bbool):
  keep_going = False
 else:
  n = n+1

Suppose the game is locally finite. If white has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Wfull's triples to all non-endstate white nodes is a winning strategy for white.  If black has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Bfull's triples to all non-endstate black nodes is a winning strategy for black. If only finitely many nodes can reach the non-draw endstates and neither side has a winning strategy then the while loop will terminate and white can always stay out of Bbool and white doing so guarantees that white won't lose. Bblack can always stay out of Wbool and black doing so guarantees that black won't lose.

If the while loop terminates, then it does so in an amount of time that's bounded above by a polynomial in (the number of nodes that can reach the non-draw endstates). Furthermore, by reduction from the circuit value problem, deciding who has a winning strategy is P-complete even when $G$ is (finite and) acyclic and there are no draw states.

No. I believe that if we consider games that include draws (such as chess), and if we use a board that it is arbitrarily large (i.e. "infinite"), and if we use some huygens chess pieces (a huygens is a chess piece which jumps prime numbers of squares), then no algorithm can solve such a game. This is because the set of prime numbers itself is not completely known.


Can epsilon be in the input alphabet of an FST? Can epsilon be in the input alphabet of an FST ?

The alphabet $\Sigma$ of an automaton can be any nonempty set of finite symbols. Surely Greek-speakers would be upset if we forbade $\{\alpha, \beta, \dots, \epsilon, \dots, \omega\}$ as a valid alphabet! If you want, you can use $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$ as your alphabet.  Or $\{A, \alpha, \clubsuit,8\}$. Or any other finite, nonempty set.

However, certain symbols have special meanings and we tend not to use them in automaton alphabets. For example, if you want your alphabet to consist of the symbols $\}$ and $\{$, things get a bit awkward: you start writing $\Sigma = \{\},\{\}$ and, er, yeah, that doesn't quite work.  Likewise, it's confusing if $\Sigma$ contains symbols such as ${}^*$, $($, $)$, $+$ and so on: you can easily write $\Sigma = \{{}^*, (, ), +\}$ but, now, when you try to write regular expressions over that alphabet, it's impossible to tell which characters in the regular expression are symbols from $\Sigma$ and which are operators in the regular expression.

$\epsilon$ fits into this second class. When $\epsilon$ isn't in the alphabet, we use that symbol to denote the empty string. As such, if you include $\epsilon\in\Sigma$, it becomes unclear whether writing "$\epsilon$" means "the empty string" or "the string containing one symbol, which is the Greek equivalent of 'e'". So, as a practical matter, we usually prefer not to use $\epsilon$ as a symbol in the alphabet. If you do need to include $\epsilon$ in your alphabet, you should use some other symbol to denote the empty string and you should say so. Similar reasoning applies to all other symbols that could be confused in this and other ways.

Basically, the epsilon (denoted by $\epsilon$) is a string, namely empty string (altrenatively denoted by $\lambda$) cannot be a part of an alphabet since a string itself consists of finite sequence of elements of the alphabet, i.e., symbols. Empty string is a string of length zero and so it is not a symbol by definition.

Furthermore, by the formal definition of finite automata, the input alphabet is defined as a finite set of symbols, i.e., not strings and hence the empty string cannot be an input symbol.

However, epsilon is allowed as a part of the input in generalization of NFA, called NFA with $\epsilon$-moves. In this case the transition function is defined as a function from $\Sigma \cup \{\epsilon\}$ into $2^Q$. But epsilon is still not a member of alphabet it is just a part of definition of the transition function.


Proving P = NP without mathematical statements / computer program This is my first post after being a passive user for some time now.
I wish to ask some questions if I may.  I am not a mathematician but my question relates to the field of maths/computer science.  In particular, the P vs NP problem.  I am aware that this is a problem that elite professionals have not yet been able to solve ...

Regardless, I would like to ask:

If a person who is neither a mathematician nor a programmer were to come up with a flowchart or a series of steps written in basic English that allegedly provides a solution to one of the P vs NP problem, would that be counted as 'proving' that P = NP .. in order to claim the Clays Institute prize :) ? Or is it a must for one to write the solution as mathematical proofs / computer program?

Thank you.

A Turing machine, it must be remembered, is a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to P versus NP, most computer scientists would try to find a formulation of it which did come as close as possible to a plain english description in order to get as strong an understanding of the solution as possible.

But there is a fundamental problem with the sort of question that you're asking. What does it mean for someone who would be able to solve P versus NP — and by showing that they are equal, no less — to not actually be either a computer scientist or a mathematician? Perhaps they are not employed professionally as a computer scientist or mathematician, but this is beside the point if they have the skill to solve what some (Scott Aaronson, for example) describe as the most important mathematical problem we've ever considered. If someone has the training (or has even self-taught) to successfully tackle the problem, and also to clearly communicate the solution to others by identifying the major sub-routines and their roles in solving e.g. SAT or HAMPATH, then whether they are employed or even have degrees is an irrelevant detail; they are nevertheless in that case a mathematician or a computer scientist. Better still if they can describe how their solutions overcome classic obstacles such as oracle results, such as oracles A for which PA ≠ NPA (or the opposite) by showing specifically what sorts of structure in the problem the algorithm takes advantage of, which would not be accessible in the oracle model. The problem, however, is that most people who dream of solving P versus NP as amateurs or outsiders seem to lack the communication skills to actually describe their work adequately, or (by virtue of not having read enough) they are unaware of results which would make their approach to solving the problem doomed from the start.

As with all dreams of glory these days, there is a basic problem with the fantasy of being the one to resolve P versus NP. The problem is that it's bound to be nearly impossible. Not actually impossible, mind you, or at least not necessarily impossible; just nearly so. As someone bright with ambition, it is possible  for one to lose sight of the fact that there are many other bright people: many of whom have also thought about the problem; and many of whom are brighter than oneself, even by a couple of orders of magnitude. And that there have been such bright people for as long as the problem has been around; and yet it remains unsolved. Yes, it's possible in principle that everyone is thinking about it the wrong way, and have been for decades. But is that really particularly likely? Nobody should expect themselves to be the one person who can spot the one sign-error that everyone else is making, because if everyone else is making that error then there must be something about the problem that will lead one to make the same mistake. Or — in the more likely event that the reason why the problem remains unsolved is not that people keep making simple mistakes or haven't yet thought of the one simple trick that dissolves the whole thing — what makes the problem fundamentally difficult is essentially an objective difficulty of the problem, and no clever dancing steps will allow one to simply waltz gracefully past all obstacles; that what is required is an approach which is not merely novel, but quite profound, identifying subtle structures that there was good reason for nobody to have seen before. The sort of structure which one is most likely to spot by thinking continuously about the problem for years.

If you want to be realistic about what it would take to solve the P versus NP problem, you might compare it to similarly famous breakthroughs in the past few decades, such as the proofs of the four-colour theorem, Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive). There's no particular reason to suspect that P versus NP will be different; so that if in the end it is resolved by an amateur, chances are extremely strong that it would be by someone with similar background knowledge and awareness of techniques of someone who is academically trained. Any realistic amateur who dreams of solving P versus NP would do well to keep that in mind.

A proof that P = NP might get accepted by a mathematical journal, but it will never be accepted by the elite professionals. The reasons is that they know that P != NP (at least for all practical purposes). They also know that it is unbelievable difficult to prove this, so even a proof that P != NP will be received with a healthy amount of skepticism by the elite professionals.

The elite professionals have more elaborate reasons than that many bright minds tried and failed to construct a polynomial algorithm for NP or prove N != NP. However, they reasonably expect that this argument should be the most convincing for a layperson. They are probably right that reference to barriers related to relativizing proofs, natural proofs or algebrizing proofs are rarely convincing for a non-expert. If too many "amateurs" try to resolve P vs NP in a certain way (for example by logical resolution, or by reducing it to a linear programming problem), then somebody will go through the pain (this sometimes takes years) to prove that this specific angle of attack is likely doomed to fail.

Edit I'm delighted that this answer continues to attract (negative) feedback. Let me therefore replace the second part of the answer (which seems unrelated to the feedback, but may distract from the main point) by the following quote from Truth vs Proof:

  We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed that in other sciences P != NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.

This change is not intended to reduce the amount of feedback, but to make it perfectly clear that this answer is serious about the fact that the experts "know that P != NP", even so they can't proof it.

23 Nov 2013 Thanks again for all the feedback. For the record, the answer now has 7 downvotes, 1 upvote and 14 comments (8 by me). Due to the amount of comments, interesting references and justifications given in the comments are hidden, so I decided to add some of them here:

As Gödel himself wrote to von Neumann, if P=NP were true "for all practical purposes", then his incompleteness theorem would only be true in theory, but effectively false in practice.
In his 1971 paper, Stephen Cook ... unable to produce counterexamples for the Davis-Putnam procedure (solved by Haken 1985). Today, many techniques, results and counterexamples are available for "disproving" proposed efficient NP-solvers. Also P = NP contradicts the "law of conservation of difficulty", the "qualitative infinitary <-> quantitative finitary" correspondence, ...
A long time ago, Scott Aaronson wrote this comment:

  anonymous: You claim (as being fact!) that 3SAT is a language in NP that cannot be computed in polynomial time. But you cannot prove it. Is that your scientific method? Yes. As a firm believer in science and reason, I strive to distinguish clearly between what I can prove and what I merely know is true.

Scott is famous for trying to demonstrate what it means that he "knows" something, for example by betting $200,000: scottaaronson.com/blog/?p=458


Find common min in logarithmic time I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(\log n)$ time. Is this possible to achieve, either for worst-case or amortized complexity?
Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.

Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.

You can't.  There is no such data structure.  Assuming you have a separate instance per set, and each instance is initialized separately (using only information about the set it represents and not any information about any of the other sets), these running times are not achievable.

In particular, when you have two sets, finding the minimum common element takes $\Omega(n)$ time.  Indeed, testing disjointness requires $\Omega(n)$ time, as explained here.  Now, imagine starting with two sets $S_1,S_2$ over the universe $\{1,2,\dots,n-1\}$.  Let $T_1=S_1 \cup \{n\}$ and $T_2 = S_2 \cup \{n\}$.  Now $T_1,T_2$ are guaranteed to have a common element.  So, if you had a good data structure for your problem, store $T_1$ in one instance of the data structure and $T_2$ in another.  Then, if we had a way to find the minimum element of $T_1 \cap T_2$ in $o(n)$ time, this would give us a way to test disjointness of $S_1,S_2$ in $o(n)$ time (just test whether the minimum element is smaller than $n$) -- but we already know the latter is not possible.  It follows that the former is not possible, either, i.e., any data structure for your problem must take $\Omega(n)$ time to find the minimum common element of two sets.

This doesn't mean that your application can't be solved efficiently. There still could be a way to solve your application in $O(n^2 \log n)$ time; this result doesn't rule that out.

Here is an idea to solve the problem, given 2 sets:

You can hold "sets" by a red black tree. In addition, for every node in the tree we associate one bit to determine if its subtree contains an element in both sets. For sake of presentation, it is called the insertion bit. I assume the red black tree sorts the elements from left to right.

When inserting an element to the tree, the algorithm checks if the element exists in the tree (i.e., in the other the set). If not- we insert the element as usual. If not,  by traveling from the root to the leaf containing the element, the algorithm turns on the insertion bit of the corresponding nodes. In the worst case it takes $O(\log n)$.

When deleting an element,   the algorithm checks if the element exists in the tree, and if the insertion bit is turned on. If the element does not exists in the tree- we return an error. If the element exists, and the insertion bit is off, then we delete the element as in the Red Black tree algorithm. Otherwise, by traveling from the root to the leaf containing the element, the algorithm turns off the insertion bit of the corresponding nodes. Deletion takes $O(\log n)$.

Finally, the algorithm for finding  minimal element shared by both sets begins with the root. If the insertion bit of the root is turn off- then the sets are disjointed, the the algorithm returns an error. Otherwise, the algorithm travels recursively to the left child if its insertion bit is turned on, and otherwise it travels to  the right child. The algorithm stops at the element with the minimal value. The algorithm runs at $O(\log n)$.

I am trying to think how to generalized the for a larger number of sets...


Split in AVL tree with complexity $O(\log n)$ Can the split operation be implemented for AVL trees with complexity $O(\log n)$? I'm interested in links to articles or any specific information about this subject.

The split operation divides the AVL tree into two derived AVL trees, based on key. One of the derived trees should contain all the vertices in which all keys less than the original key, and the second the rest.

I know this can be done in $O(\log^2 n)$ time.  Here's a link to implementation with complexity $O(\log^2 n)$:
https://code.google.com/p/self-balancing-avl-tree/

I also know how to merge two AVL trees, such that the keys of one tree are all smaller than the keys of the other, in $O(\log n)$ time.
Here's an implementation with complexity $O(\log n)$:

def Merge(l, r) {
    if (!l || !r)
        return l ? l : r;
    if (l->h <= r->h)
        r->l = Merge(l, r->l), Rebalance(r);
    else
        l->r = Merge(l->r, r), Rebalance(l);
}

Yes, this is possible.

You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.

One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the height of the taller tree and $h_2$ is the height of the shorter tree. As such, merging a list of trees that have descending or ascending heights costs only $O(h_{\max} - h_{\min})$, since the sum telescopes.

Let us define a function split(T,v) that takes in a tree, T and a value to split at, v. Suppose that each node of the tree stores its left child and right child in addition to the value at that node. Use the following algorithm:

First we check to see if the input tree is simply a leaf or not.
If T is not a leaf, compare the value of its root node, v' with v.
If v' < v then recursively call split on the left subtree. Store the values of the recursive call as L' (returned left tree), R' (returned right tree), and r (option type indicated if the value v was found or not). Construct the new right tree, newR = Node(R',v',R), and return (L',r,newR).
Else if v' > v then recursively call split on the right subtree. Store the values of the recursive call as L' (returned left tree), R' (returned right tree), and r (option type indicated if the value v was found or not). Construct the new left tree, newL = Node(L',v',L), and return (newL,r,R').
Else if v' = v, return L, SOME(v), R.
If T is a leaf, we must have reached the root of the tree without finding the input value v to split at. Return that you couldn't find the leaf by passing back NONE.

Why is this logarithmic? Well, you only ever traverse one root-to-leaf path of the tree, at most. We can easily reconstruct nodes in constant time since we're just re-assigning $O(\log n)$ references (in an imperative language) or reassigning $O(\log n)$ values that take a constant time to generate (in a functional language).

Here's the corresponding code for the algorithm. It's written in SML, but I'd be willing to clarify what anything means in the comments.

fun split(T,v) =
  case T of
    Leaf => (Leaf, NONE, Leaf)
  | Node(L,v,R) =>
      case compare(v, v') of
        LESS =>
          let
            val (L',r,R') = split(L,k)
          in
            (L',r,Node(R',r,R))
          end
      | GREATER =>
          let
            val (L',r,R') = split(R,k)
          in
            (Node(L',v',L),r,R')
          end
      | EQUAL => (L, SOME(v), R)

See this document for more details. It provides a more thorough explanation of the above.


Automaton equivalent of the π calculus? If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing Machine, but with support for communication channels or signals of some type, but I'm not sure, and would appreciate some direction.

The question doesnt make too much sense because the $\pi$-calculus was proven Turing complete, or in other words equivalent to a Turing machine ever since its inception by Milner in 1992. There is a reference on Wikipedia.


Algorithms online problems I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations.

As far as I can see, the sites that I found (CodeChef, Project Euler) seem to be more programming oriented, even if I like the format and their challenge. That is, even when speed is somehow important, you cannot not know the exact complexities values for the algorithm (the lovely greek letters), maybe some demonstration of the efficiency of the solution.

An online course or a book is acceptable if it is more problems oriented. In my opinion, these are the kind of questions that a development top company should ask anyway.

Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms (MIT Press, 3rd edition, 2009) is a good book for understanding and solving time complexity and correctness of
algorithms mathematically.


2:1 Mutual exclusion with semaphores I'm stuck on this semaphore exercise (it's a exam question of a previous exam and I'm studying for that exam):

There are three processes: A, B and C. Process A wants to execute method a(); Process B wants to execute b(); and Process C c();. The Processes are each started once.

The execution of a(); must not overlap with the execution of b(); or c();. However b(); and c(); must always be able to run concurrently. The order of execution must not be forced.

I can use as many semaphores as I want. With every solution I tried so far I always get the case that when e.g. b(); is executing and a(); is waiting, that I will also block c();. The solution is probably simple but I'm too blind to see it.

There's a simple solution which takes advantage of the fact that semaphores naturally allow controlling access to a resource with multiple instances. Model the exclusion as a resource with two instances. A requires both instances while B and C each require one. When A starts, it grabs both instances, preventing B and C from starting. When B or C starts, it grabs one instance, which allows the other to start concurrently, but blocks A.

A:                  B:                  C:
  V(S, 2)             V(S, 1)             V(S, 1)
  …                   …                   …
  P(S, 2)             P(S, 1)             P(S, 1)

This solution works even if the processes run multiple times. A critical ingredient that makes it work is that A atomically excludes both B and C from running.

If you treat B and C's resources as distinguishable, with A requiring both, you run into a classical problem, which is the order of grabbing locks. This problem is similar to the dining philosophers problem. When A starts, it either grabs the B resource first, or the C resource first. Let's say A grabs B, and then tries to grab C. If C is not available, what should happen? If A keeps the B resource then it prevents process B from starting. So A must release B and try again. Since A knows that C is busy, it can wait on C first. In this particular exercise, where the processes only run once, this works. Note that this requires semaphores with a non-blocking “try” operation.

A:                  B:                  C:
  lock(B)             lock(B)             lock(C)
  if try_lock(C):     …                   …
    …                 release(B)          release(C)
    release(C)
    release(B)
  else:
    release(B)
    lock(C)
    lock(B)
    …
    release(B)
    release(C)

If B and C could run multiple times, this strategy wouldn't work: A must never keep one lock while waiting for the other, because that prevents the corresponding process from running again. In this case, I think there's no wait-free solution with only binary semaphores.

Use two binary semaphores : x and y.

x will provide mutual exclusion between A and B while y will provide mutual exclusion between A and C.

When A wants to execute a() then it must check that neither of b() and c() is being executed. Thus code for A would be like this:

lock(x)
lock(y)
a()
unlock(y)
unlock(x)

For B code would be like this:

lock(x)
b()
unlock(x)

For C code would be like this

lock(y)
c()
unlock(y)

You may check different execution sequences to verify my answer.


Efficient N-Ary GCD Algorithm Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for exactly two input values?  E.g. gcd(a, b, c, ...) vs. gcd(a, gcd(b, gcd(c, ...)))

If so, then what is such an algorithm?

If not, then is it known whether there cannot exist such an algorithm?

As Wikipedia reports, the fastest currently known algorithm for the gcd of two $n$-bit numbers runs in $O(n f(n))$ time where $f(n)$ is a slow-growing function of $n$ (roughly $\log n \cdot \log \log n$).  It is not known whether the gcd of two $n$-bit numbers can be computed in $O(n)$ time.

This means that the iterative algorithm for computing the gcd of $k$ $n$-bit numbers (as described in the question) runs in $O(kn f(n))$ time.  Obviously, any algorithm needs at least $\Omega(kn)$ time -- this lower bound follows from the fact that any algorithm needs to read the entire input.  This doesn't leave much of a gap between the trivial lower bound and the running time of the iterative algorithm.  In other words, it doesn't leave much room for improvement in running time.

That's the theoretical answer.  From a pragmatic perspective, the $O(n f(n))$-time algorithms only become faster than (asymptotically slower) alternatives once $n$ is fairly large.  As a result, if $n$ is not too large, these results might not mean much.

Also, from a pragmatic perspective, we can expect that $\gcd(a,\gcd(b,\gcd(c,d)))$ might be faster than $\gcd(\gcd(a,b),\gcd(c,d))$.  They both yield the same answer, but the former might often be faster, because typically one of the two arguments to the gcd will be small.  Computing $\gcd(x,y)$ might be faster in practice if $y$ is much smaller than $x$ (because the first step is to replace $y$ with $y \bmod x$) than when $x,y$ are about the same size.  So, you might benefit by performing the gcd's in an order that gets you down to a small number as soon as possible.

The runtime of gcd depends on the size of the result relative to the size of the inputs, especially the smaller input.

If you start with inputs of equal size, the runtime depends on the ratio between inputs and final result. Best to calculate x = gcd (a, b), y = gcd (x, c) and so on.