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
Censorship: 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: Approved - active

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.

Entry requirements

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

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

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

June

Tests

Oral exam

EKA

N340060102

Censorship

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

56 hours per semester

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

Name E-mail Department
Kim Skak Larsen kslarsen@imada.sdu.dk Institut for Matematik og Datalogi, Datalogi

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Team at Registration & Legality

NAT

Recommended course of study

Profile Programme Semester Period