Admission requirements
The students should have taken a course in Algorithms.
Description
String algorithms are well suited for educational purposes as they nicely combine elegant combinatorial results with practical applications of growing common interest. Very important data of huge size can be treated as a text. One example is the web, for which indexing and search issues have clear practical impact and deserve the use of the most sophisticated algorithmic techniques. Another main application is the treatment of biological sequences for which storage and analysis tasks raise many challenging algorithmic problems.
Course objectives
The goal of this course is to give the student an overview of algorithms on strings. We will range from basic problems to more specific ones, and we will show different solutions and corresponding example for the same (or related) problem highlighting how, besides theoretical complexity issues, things change in practice, leading the student to have hands-on the difference between worst case theoretical complexity of a problem, practical behavior of algorithms, and fixed parameter tractability.
Timetable
The most recent timetable can be found at the LIACS website
Mode of instruction
Lectures
Assessment method
Written exam and possible oral.
Reading list
Jewels of Stringology, M.Crochemore and W.Rytter, World Scientific, 2002.
Introduction to Computational Molecular Biology, J.Setubal and J.Meidanis, PWS, 1997.
Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology,
Dan Gusfield, Cambridge University Press, 1997.
Registration
You have to sign up for classes and examinations (including resits) in uSis. Check this link for more information and activity codes.
There is a limited capacity for students from outside the master Computer Science programme. Please contact the study-advisor.
Contact information
Study coordinator Computer Science, Riet Derogee