DM823: String Algorithms (5 ECTS)

STADS: 15014301

Level
Master's level course approved as PhD 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.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None.

Academic preconditions:
Students taking the course are expected to:

• Have knowledge of methods for the design, correctness analysis, and time analysis of algorithms, corresponding to the contents of the course DM507 Algorithms and Data Structures.
• Be able to use these methods with precision and level of abstraction corresponding to a Bachelor's degree in Computer Science.

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, strings are the core data type. Additionally, strings are a generic and fundamental data model in Computer Science, containing e.g. integers and multi-dimensional data as special cases.

The aim of the course is to give the student knowledge of a number of algorithms and data structures for problems on strings and to enable the student to apply these, or variants thereof, which is important in situations where string data appears.

The course builds on the knowledge acquired in the course DM507 Algorithms and data structures, as well as other algorithmic courses in the Bachelor's programme in Computer Science, and gives competences for master thesis
work in the area.

In relation to the competence profile of the degree it is the explicit focus of the course to:

• Give knowledge and understanding of a collection of specialized models and methods developed within Computer Science based on research on highest international level, as well as of models and methods aimed at applications in other subject areas.
• Give skills to describe, analyze and solve computational problems by using the methods learnt, to analyze pros and cons of different methods in Computer Science, as well as to develop new variants of the methods learnt where the problem at hands requires this.
• Give the competence to plan and execute scientific projects on a high technical level.

Expected learning outcome
The learning objectives of the course is that the student demonstrates the ability to:

• Explain the functionality and correctness of the algorithms and data structures covered.
• Analyze the algorithms and data structures covered wrt. time and space complexity.
• Design efficient algorithms and data structures for variants of the problem scenarios covered.
• 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
The following main topics are contained in the course:

• Pattern matching, exact and approximate.
• Suffix trees, suffix arrays, and other string data structures.
• String sorting.
• Compression algorithms.
• Algorithms for string distance measures.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Project assignment. Pass/fail, internal evaluation by teacher.

Assessment and marking:
Oral Exam, Danish 7-mark scale, external examiner.

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

Educational activities

Educational form
Activities during the study phase: Project.

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.