String Algorithms - Q2/2007

• Main Page
• Weekly Schedule
• Mandatory Projects
• List of Participants

Announcements

• 17/12/07: Feedback about project 2 has been sent to you, so if you expect something but have not received any, then let us know. Your program has been tested on gene42.txt.
• 13/12/07: Info about exam (question, schedule etc.) is available.
• 13/12/07: Schedule for week 7 is available.
• 05/12/07: Schedule for week 6 is available.
• 28/11/07: The description of mandatory project 2 is available.
• 28/11/07: Schedule for week 5 is available.
• 19/11/07: Schedule for week 4 is available.
• 12/11/07: Schedule for week 3 is available.
• 12/11/07: The description of mandatory project 1 is available.
• 08/11/07: The oral exam will be on January 21-23, 2008, in Shannon-159.
• 08/11/07: Schedule for week 2 is available.
• 22/10/07: Schedule for week 1 is available. First lecture is on Monday, November 5, in Store Aud.
• 21/08/07: Time and place available.
• 02/07/07: 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 12.15-14.00, Store Aud.
• Thursdays 11.15-12.00, Lille Aud.

First lecture is on Monday, November 5 in Store Aud.

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 January 21-22, 2008. 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: 090.224B
Phone: +45 8942 3149
E-mail: mailund [at] daimi.au.dk

Christian Nørgaard Storm Pedersen

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