Helsinki Algorithms Seminar: "Revisiting the classical greedy shortest common superstring algorithm" Jarno Alanko, UH

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design.

Jarno Alanko
Doctoral Student, University of Helsinki

Revisiting the classical greedy shortest common superstring algorithm

Abstract:

In 1990, Esko Ukkonen showed how to compute a greedy approximation for the NP-hard shortest common superstring problem in linear time. We revisit this old algorithm by improving the space complexity from O(n log n) bits to O(n log σ) by applying modern compressed data structures to the problem. After index construction, a practical implementation of our algorithm uses roughly 5 n log σ bits of space and reasonable time for a real dataset that consists of DNA fragments.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!