String Algorithms - Q3/2009

• Main
• Schedule
• Projects
• Participants

Announcements

• 05/03/09: Schedule for week 7 available.
• 03/03/09: Final Challenge (Finding motifs in strings). If you like to partipate, e-mail your solution to Thomas Mailund before Wednesday, March 18.
• 28/02/09: Preliminary exam questions and schedule available.
• 27/02/09: Schedule for week 6 available.
• 24/02/09: The oral exams will be on March 19-20 in Shannon-159.
• 20/02/09: Schedule for week 5 available.
• 13/02/09: Description of project 2 is available.
• 13/02/09: Schedule for week 4 available.
• 05/02/09: Schedule for week 3 available.
• 29/01/09: Schedule for week 2 available.
• 15/01/09: Schedule for week 1 available.
• 15/12/08: Initial www-pages ready.

About

String algorithms (i.e. algorithms and data structures for analysis and indexing of strings) are an important aspect of many computer science disciplines, such as data-compression, cryptography, speech- and image-recognition, and computational biology. Furthermore, string algorithms is an interesting theoretical field in itself, with many fascinating problems and elegant solutions.

This class gives an introduction to string algorithms. The class presents concrete techniques and string-algorithms and their implementation and analysis: exact and approximate pattern-matching; string distance calculations; repetition and periodicity search; construction and applications of suffix-trees and suffix-arrays.

See official course description.

Schedule

Lectures take place:

• Mondays 11.15-13.00, Shannon-157.
• Thursdays 09.15-10.00, Shannon-157.

First lecture is on Monday, January 26.

Check the weekly schedule for information about each lecture.

Literature

We will use the following book, which will be available in the GAD bookstore:

	Bill Smyth
	Computing Patterns in Strings
	Addison Wesley, 2003
	ISBN: 0201398397

Additional research papers will be handed out in class or made available for download.

Exam and Projects

Each student must participate in two mandatory projects. Currently three projects are planned. The projects can be done in groups of 2-3 students.

The final exam is an individual oral exam (20 min) which includes a presentation/discussion of topic covered in class and a presentation/discussion related to one of the mandatory projects. The presentation/discussion should take 12-15 minutes. See the list of exam questions for details.

The exam dates are March 19-20, 2009. The exam will take place in Shannon-159 according this exam schedule. Note that you have to pass both mandatory projects in order to qualify for the exam.

Lecturer

If you have any comments or questions related to the course, do not hesitate to contact one of the lectures:

Thomas Mailund

Office: 1110.326
Phone: +45 8942 3149
E-mail: mailund [at] birc.au.dk

Christian Nørgaard Storm Pedersen

Office: 1110.325
Phone: +45 8942 3121
E-mail: cstorm [at] birc.au.dk