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: 29-10-2021
Duration: 1 semester
Version: Approved - active
Comment
The course is offered as required and is not necessarily offered every year. Exam attempts for DM803 are offered in accordance to the following plan, when the course is offered: Spring (course Start February): ordinary Exam (June), first reexamination (August) and 2nd reexamination (January or March).
Entry requirements
Academic preconditions
Knowledge of algorithms and data structures and their analysis is assumed, including algorithm design techniques such as divide-and-conquer, balanced binary search trees such as red-black trees, priority queues via the heap implementation, disjoint sets, time and space analysis, including asymptotic notation and recursion equations, lower bounds for sorting, and basic understanding of probability theory. The prerequisites can be obtained through algorithms and discrete mathematics courses on a computer science bachelor education.
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 builds on competences obtained through algorithms courses in a computer science bachelor degree 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
ECTS value
10
Additional information
The exam consists of an oral examination and a project with an overall evaluation.
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
Teacher responsible
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.