ICS Theory Group

CompSci 269S, Fall 2006: Theory Seminar

Dec 1, 2006, in CS 253

Cache-Oblivious Dynamic Programming

Rezaul Alam Chowdhury and Vijaya Ramachandran

Presented by Kevin Wortman


We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.