Studiegids

nl en

String, Pattern and Motif Search Algorithms

Vak
2012-2013

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

Website

Website