Seminar in advanced topics in data structures (0368.434.301) Fall 2004
Guidlines and bibliography
Tuesday 14-16 Kaplun 319
Please fill out the online teaching survey !
Introduction lecture on suffix trees.
Papers:
The Boyer-Moore algorithm and its analysis
Sections 2.2, 3.1, 3.2 in the book by Gusfield
Presentation by Idan Spector
Linear time construction of suffix trees
Chapter 6 in the book by Gusfield
Presentation by Itamar Axelrod
The LCA problem revisited
M. A. Bender and M. Farach-Colton
Presentation by Dvir Halevi
Selected applications of suffix trees
Based on Chapters 7 and 9 in the book by Gusfield
Presentation by Daphna
Suffix arrays: A new method for on-line string searches
U. Manber and G. Myers, SIAM J. Comput., 22(5):935--948, Oct. 1993.
and
Simple linear work suffix array construction
J. Karkkainen and P. Sanders
Presentation by Amitai Kfir
Seminumerical string matching
Chapter 4 in the book by Gusfield
Presentation by Daniel Glasner
Faster algorithms for string matching with k mismatches
A. Amir, M. Lewenstein and E. Porat
Presentation by Eytan
Overlap matching
A. Amir and R. Cole and R. Hariharan and M. Lewenstein and E. Porat
Presentation by Itamar Nabriski
Compressed suffix arrays and suffix trees with applications to text indexing and string matching
R. Grossi and J.S. Vitter
Presentation by Itay Dar
An analysis of the Burrows-Wheeler transform
G. Manzini
Presentation by Assaf Oren
PC trees and circular-ones arrangements
W.L. Hsu and R.M. McConnell
Presentation by Noa Bar Yossef
PQ tree, PC tree, and planar graphs
W.L. Hsu and R.M. McConnell
Presentation by Roi Barkan