DM803: Advanced Data Structures (5 ECTS)

STADS: 15003501

Level
Master's level course

Teaching period

Offered when needed.

Teacher responsible
Email: kslarsen@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal

Prerequisites:
None

Academic preconditions:
The content of DM508 Algorithms and Complexity should be known.

Course introduction
Advanced data structures are of great importance in theoretical as well as in more applied areas of computer science. The development of an algorithm with optimal time complexity often depends on the design of a data structure with just the right properties. Likewise, the choice or design of an efficient data structure often makes the difference between a large program which is too slow, and one that meets the user demands. The purpose of this course is to give the participants a thorough understanding of advanced data structures such that later the participants will be able to use them when approaching complex problem solving and programming.

Expected learning outcome
At the end of the course, the student should be able to:

• explain the functionality and correctness of the covered algorithms and data structures
• analyze the covered algorithms and data structures wrt. time and space complexity
• design efficient algorithms and data structures for variants of the covered problem scenarios
• explain the problems involved in implementing the covered algorithms and data structures in standard programming languages

Subject overview
Priority queues, height and weight balanced trees, multi-way trees, randomized search structures, disjoint sets with variations, hashing methods, techniques such as global rebuilding, persistency, dynamization, and relaxed balance.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

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

Terms for reexam according to the rules decided by the Study Board.
The exam form is changed from external examiner to internal examiner.

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

Forelæsninger, antal timer 21.
Eksaminatorietimer/opgaveregning, antal timer 21.
Educational activities

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.