2017/2018 Edition

String algorithms

Lecturer: Prof. Maxime Crochemore (King's College London, UK & Universite Paris-Est, France).

About the lecturer | Course Summary | Slides | Exam

About the lecturer: Prof. Maxime Crochemore received his PhD in 1978 and his Doctorat d'etat in 1983 at the University of Rouen. He got his first professorship position at the University of Paris-Nord in 1985 where he acted as President of the Department of Mathematics and Computer Science for two years. He became professor at the University Paris 7 in 1989 and was involved in the creation of the University of Marne-la-Vallee where he is Professor, emeritus from 2007. He also created the Computer Science research laboratory of this university in 1991 and was the director until 2005. From 2004 to 2006, he was Deputy Scientific Director of the Information and Communication Department of CNRS. Prof. Crochemore was Senior Research Fellow from 2002 to 2007 and is presently Professor at King's College London. He has been the recipient of several French grants on string algorithmics and bio-informatics. He participated in a good number of international projects in algorithmics and supervised more than twenty PhD students.

Course summary:
The domain of Algorithms on words or sequences is fond of combinatorial properties of words. They are used to analyse the behaviour of algorithms in conjunction with statistical results, and sometimes lead to improving their design up to optimal characteristics.
Conversely, some combinatorial properties on words, obtained without any algorithmic objectives, surprisingly yield algorithms that are efficient according to various aspects.
We give a few examples of these two phenomena in order to emphasise the need for more intensive studies on combinatorics on words.
Examples of this interplay between algorithms and combinatorics on words are taken from string matching under several constraints and from sequence assembly. The notion of periodicity in words is central to most examples.

Please send the solutions (including program) to professor Crochemore (maxime DOT crochemore AT kcl DOT ac DOT uk)
by 31 January, 2010.