DM803: Advanced Data Structures (10 ECTS)

STADS: 15015701

Level
Master's level course approved as PhD course

Teaching period
The course is offered when needed.

Teacher responsible
Email: kslarsen@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:

• the subject in DM553 and courses recommended for that, in particular
• data structures such as balanced search trees, priority queues via the heap implementation, disjoint sets
• time and space analysis, including asymptotic notation, recursion equations, amortized analysis

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.

The course build on competences obtained in DM553 Complexity and Computability in particular, and gives competences for master thesis work in the area.

With reference to the educations competence profile, the course has focus on

• comprehending a complex problem
• analyzing and working with complex assignments
• working towards solutions, both independently and as part of a team

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
The following main topics are contained in the course: 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, etc.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Report. Pass/fail, internal marking by teacher.

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

Terms for reexam according to the rules decided by the Study Board.

Expected working hours
The teaching method is based on three phase model.
Intro phase: 28 hours
Skills training phase: 28 hours, hereof:
 - Tutorials: 28 hours

Educational activities

Educational form
Activities during the study phase:

• Solve assignments
• Read the assigned literature
• Practice to apply the acquired knowledge

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.