Two Glass Balls and a Tower

May 7, 2007
3:45 pm
Halligan 111
Speaker: Prof. Amihood Amir, Bar-Ilan University
Host: Prof. Diane Souvaine


The bounded divide-and-conquer technique has been pioneered in Pattern Matching by Karl Abrahamson. Since its inception, the technique has proven useful in numerous results in combinatorial pattern matching and computational biology. Its wide use warrants a deeper study.

We will review and abstract the idea and show how it has aided in efficiently computing Hamming distance, less-than matching, masked maximum, and approximate weighted sequences matching.