Presentation for Open Source Project: lcalibrary
  • 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

With some simple dynamic programming we can turn the O(n^3) into an O(n^2) but that is still not good enough.

We want the fastest solution possible, in fact, a solution that runs in linear time would be best. Our goal is to preprocess our dataset in O(n) to provide O(1) lookups.
This is the underlying reason behind this project. A tool which allows us to process data, and run queries against it, all as fast as possible.






[previous slide]   [next slide]


Copyright 2003, Zack Ramjan