• Description of LCA
• The use of LCA
• Trivial solution n^2
• Better solutions
• This Project

• Brief overview
• more info here

• Brief overview
• more info here

• Perl for Bender
• C++ for vishkin
• Library with sample drivers
• To do: mpich

Now that we have determined the calculation of LCA is useful, we can consider a trivial solution.

For all nodes in the tree, create a table that stores the LCA of any two nodes. So we simple calculate the LCA(X,Y) where X and Y are all the possible LCA queries based upon the tree.

This works fine, but is dreadfully slow. Supposing that our data set is huge, this would be quite tedious, in fact it is O(n^3).

[previous slide]   [next slide]