String Algorithms Q4/2012
Announcements
- 11/05/12: Preliminary exam questions and schedule available below.
- 30/04/12: The oral exam will be on Thursday, June 14.
- 30/04/12: The lecture on May 3 is cancelled. Handin project 2 by e-mail to cstorm, or in class on Monday, May 7.
- 07/3/12: 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.
Schedule
Lectures take place:
- Mondays 10.15-12.00 in Room 1110.214 (at BiRC).
- Thursdays 12.15-13.00 in Room 1110.214 (at BiRC).
First lecture is on Thursday, March 29 in Room 1110.214.
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 (if allowed accoring to CopyDan rules).
Exam and projects
Each student must participate in all 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-13 minutes. See the list of exam questions for details.
The exam date is Thursday, June 14, 2012. The exam will take place in Room 1111-100 (ground floor in the BiRC building) according this preliminary exam schedule. You have to pass all 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:
Office: 1110.326
Phone: +45 8942 3125
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