DM823: String Algorithms (5 ECTS)

STADS: 15014301

Level
Master's level course

Teaching period
The course is offered in the autumn semester.
The course is offered according to needs.

Teacher responsible
Email: rolf@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Prerequisites:
None

Academic preconditions:
The contents of DM507 Algorithms and Data Structures and DM508 Algorithms and Complexity should be known.

Course introduction
Data sets consisting partly or entirely of string data are common: Most database applications have strings as one of the data types used, and in some areas, such as word processing, bioinformatics, and web retrieval, fundamental data model in computer science, containing e.g. integers and multi-dimensional data as special cases.

On this course, we cover a number of advanced algorithms and data structures for fundamental problems on strings.

Expected learning outcome
- Describe algorithms and data structures covered in the course.
- Give proofs of correctness and complexity of algorithms and data structures covered in the course.
- Formulate the above in precise language and notation.
- Implement algorithms and data structures covered in the course.
- Perform experiments on these implementations and reflect on the results achieved.
- Describe the implementation and experimental work done in clear and precise language, and in a structured fashion.

Subject overview
Pattern matching, exact and approximate. Suffix trees, suffix arrays, and other string data structures. String sorting. Compression algorithms. String distance algorithms.

Literature
There isn't any litterature for the course at the moment.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Project assignment. The project must be passed in order to attend the oral exam.

Assessment and marking:

(b) Oral Exam, Danish 7 mark scale, external examiner.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger: 28 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.