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
 Perl was used for the implementation of "Bender's Algorithm". This allowed for rapid development. The mapping between algorithm and code was also clearer with perl. The code created includes:
  • Routines for performing LCA preprocessing, and queries
  • Tree generators
  • a sample driver to test the library

We have successfully passed tests ensuring correctness and linear operation up to 1.5 million nodes.

 

 

 

 



[previous slide]   [next slide]

 

Copyright 2003, Zack Ramjan