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

None

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

See itslearning for syllabus lists and additional literature references.

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

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 Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

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.