...............................Lowest Common Ancestor CaIculations


Team Members | Overview | Source Forge | Contact 

This programming library is for performing LCA (Lowest Common Ancestor) calculations. It will start off as a uniprocessor sequential implementation, and hopefully later include Multiprocessor or PVM implementations.
The current algorithms under development is a sequential O(n) preprocessing solution conceived by Michael Bender and Martin Farach-Colton and Uzi Vishkin et all's PRAM solution.

Documents & Files


The presentation for CS410OSS at PSU is available.

Bender's method implementation in perl now available for download

Vishkins method implementation in C++ now available for download

Project Schedule An ongoing list of estimated completion dates. Milestones of what has been accomplished so far

Function Descriptions A list of what's available in this library. Methods, functions etc. Only Bender right now, Vishkin coming soon.

The journal articles of the two algorithms are on sourceforge



8-14-03: released Vishkins code.
8-13-03: did presentation for cs410oss
8-12-03: Created a presentation for my class.
8-10-03: Preparing Vishkin's for release, fixing bugs
8-08-03: Creating documentation for Bender's method
8-06-03: Preparing Bender's method for release.
8-04-03: Creating the mpich parallel version will need more time then is available in this class. We will now focus on completing and polishing off the two sequential versions.
8-01-03: Putting vishkins parallel mpich design on hold in interest of finishing the vishkin serial and bender programs
7-29-03: Parallel mpich vishkin PRAM model still under development. It is much more difficult then the serial one.
7-22-03: Serial single threaded of vishkin's code ready
7-14-03: currently working on vishkins code
7-14-03: Added docs on with the algorithms
7-13-03: Project Schedule document complete
7-12-03: initial CVS for vishkin algorithm
7-10-03: initial source on sourceforge CVS for bender algorithm
7-08-03: added a new developer, welcome ahsaneida
7-06-03: Started creating a project schedule.
7-05-03: Created this website.
7-03-03: Sourceforge approved the request to host this project.
6-30-03: Officially began this project. we have one team member, me.
6-28-03: registered this project on my Classes Wiki
 Copyright 2003 Zack Ramjan. All rights reserved