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.
Exam
Please send the solutions (including program) to professor Crochemore (maxime DOT crochemore AT kcl DOT ac DOT uk)
by 31 January, 2010.