DM803: Advanced Data Structures (10 ECTS)
STADS: 15015701Level
Master's level course approved as PhD course
Teaching period
The course is offered when needed.
Teacher responsible
Email: kslarsen@imada.sdu.dkTimetable
| Group | Type | Day | Time | Classroom | Weeks | Comment |
|---|---|---|---|---|---|---|
| Common | I | Tuesday | 10-12 | IMADA Seminarrum | 36,37,38,39,40,41,43,44,46,47,49,50,51 | |
| Common | I | Tuesday | 10-12 | U7 | 45 | |
| Common | I | Tuesday | 10-12 | Spørg underviseren | 45,48 | |
| Common | I | Tuesday | 10-12 | U10 | 48 | |
| Common | I | Wednesday | 08-10 | IMADA Seminarrum | 36,37,38,39,40,41,43,44,45,46,47,48,49,50,51 |
Show personal time table for this course.
Prerequisites:
None
Academic preconditions:
Bachelor's degree. 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
There isn't any litterature for the course at the moment.
Website
This course uses e-learn (blackboard).
Prerequisites for participating in the exam
Mandatory assignments (15015712).
Assessment and marking:
Oral exam. Danish 7 mark scale, external examiner (15015702).
Terms for reexam according to the rules decided by the Study Board.
Expected working hours
The teaching method is based on three phase model.
Forelæsninger, antal timer 28.
Eksaminatorietimer/opgaveregning, antal timer 28.
Educational activities
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.
