DM803: Advanced Data Structures
Study Board of Science
Teaching language: Danish or English depending on the teacher, but English if international students are enrolled
EKA: N340060102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master's level course approved as PhD course
STADS ID (UVA): N340060101
ECTS value: 10
Date of Approval: 02-10-2019
Duration: 1 semester
Version: Archive
Comment
15015701 (former UVA) is identical with this course description.
The course is offered when needed in the Spring semester.
Examination tests for DM803 are offered (as part of courses offered spring 2020): Ordinary examination June 2020 and re-examination in August 2020 and January 2021.
Examination tests for DM803 are offered (as part of courses offered spring 2020): Ordinary examination June 2020 and re-examination in August 2020 and January 2021.
Entry requirements
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
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
Content
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
Examination regulations
Exam element a)
Timing
June
Tests
Oral exam
EKA
N340060102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Examination aids
To be announced during the course, a closer description of the exam rules will be posted in itslearning.
ECTS value
10
Additional information
The exam consists of an oral examination and a project with an overall evaluation.
The examination form for re-examination may be different from the exam form at the regular exam.
Indicative number of lessons
Teaching Method
The teaching method is based on three phase model.
- Intro phase: 28 hours
- Skills training phase: 28 hours, hereof 28 hours tutorials
Activities during the study phase:
- Solve assignments
- Read the assigned literature
- Practice to apply the acquired knowledge