Course Content
The Knuth-Morris-Pratt algorithm, the Boyer-Moore and Karp-Rabin algorithms and FFT-based algorithms for static string matching. [8 Lectures]
Suffix trees, suffix arrays and LCP arrays, their constructions and applications (in finding longest common substring, shortest unique substring, suffix/prefix overlaps, Lempel-Ziv factorization, etc.) [14 Lectures]
Succinct data structures and compressed text indexing: rank and select queries on bit vectors and sequences, Range minimum queries, Wavelet trees, Compressed suffix arrays, Burrows-Wheeler Transform and FM Index, compressed LCP arrays. [12 Lectures]
NP-hard problems and approximations: longest common substring (over multiple strings) median string problem, shortest superstring problem, etc. [8 lectures]
Text Books
- Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology by Dan Gusfield, Cambridge University Press, 2005. ISBN: 978-0521670357
- Compact Data Structures: A Practical Approach 1st Edition by Gonzalo Navarro, Cambridge University Press, 2016. ISBN: 978-1107152380.
Past Offerings
Course Metadata
| Item | Details |
|---|---|
| Course Title | Data Structures and Algorithms on Strings |
| Course Code | CS5022 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Venkatesh Raman (Faculty, IMSc Chennai) and Krithika Ramaswamy |
| Approved on | Senate 30 of IIT Palakkad |
| Course status | New |