Algorithms Talk: Fast and Cache-Oblivious Dynamic Programming with Local Dependencies

[Philip Bille]

Talk on algorithms. All are welcome. Please forward to other
interested people.

When: Monday, Feb. 27, 13.15-13.45
Location: 322 / 205
Title: Fast and Cache-Oblivious Dynamic Programming with Local
Dependencies
Speaker: Morten Stockel

Abstract: String comparison such as sequence alignment, edit distance
computation, longest common subsequence computation, and approximate
string matching is a key task (and often computational bottleneck) in
large-scale textual information retrieval. For instance, algorithms
for sequence alignment are widely used in bioinformatics to compare
DNA and protein sequences. These problems can all be solved using
essentially the same dynamic programming scheme over a two-dimensional
matrix, where each entry depends locally on at most 3 neighboring
entries. We present a simple, fast, and cache-oblivious algorithm for
this type of local dynamic programming suitable for comparing large-
scale strings. Our algorithm outperforms the previous state-of-the-art
solutions. Surprisingly, our new simple algorithm is competitive with
a complicated, optimized, and tuned implementation of the best cache-
aware algorithm. Additionally, our new algorithm generalizes the best
known theoretical complexity trade-offs for the problem.