Presentation for Open Source Project: lcalibrary
Introduction
  • Description of LCA
  • The use of LCA
  • Trivial solution n^2
  • Better solutions
  • This Project
Bender's Method
  • Brief overview
  • more info here
Vishkin's Method
  • Brief overview
  • more info here
Development process
  • Perl for Bender
  • C++ for vishkin
  • Library with sample drivers
  • To do: mpich

 

Definition of "Lowest Common Ancestor"

Consider a tree with 4 nodes. Lets say we are talking about somebody's ancestry or family tree.

 

 

Text Box: Bob Text Box: Joe Text Box: Mary

Text Box: Dave

 

 

Text Box: Dan

 


Joe has two children, Mary and Bob. Mary has two children, Dan and Dave.

The question we would like to ask is: Given any two nodes (people) what is the lowest  node (person) that connects both.

Example: LCA(Dan, Dave) = Mary. Mary is lowest node that connects Dan and Dave
Example: LCA(Bob, Dave) = Joe. Since Bob is Dave's uncle, there common ancestor is Joe

[home]   [next slide]

Copyright 2003, Zack Ramjan