DM507: Algorithms and Data Structures

The Study Board for Science

Teaching language: Danish or English depending on the teacher
EKA: N330068112, N330068102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Bachelor

STADS ID (UVA): N330068101
ECTS value: 10

Date of Approval: 28-10-2022


Duration: 1 semester

Version: Archive

Entry requirements

The course cannot be chosen if you have passed DM578, or if DM578 is a compulsory form of your curriculum.

Academic preconditions

Students taking the course are expected to:
  • Have knowledge of the contents of DM549 Discrete Methods for Computer Science. In particular, some amount of mathematical maturity is assumed.
  • Be able to use the methods from DM550 Introduction to Programming. In particular, familiarity with programming in Java or Python is assumed.

Course introduction

The aim of the course is to enable the student to apply a wide range of existing algorithms and data structures for fundamental problems, as well as general methods for developing new algorithms and mathematical tools for analyzing the correctness and efficiency of algorithms. This is of paramount importance for the ability to develop efficient software, and is central to the understanding of upper and lower bounds for computational problems.

The course builds on the knowledge acquired in the courses DM549 Discrete Methods for Computer Science and DM550 Introduction to Programming, and gives an academic basis for studying the algorithmical and complexity theoretical topics that are part of the degree. In relation to the competence profile of the degree it is the explicit focus of the course to:
  • Give the competence to develop new variants of central algorithms and data structures developed within computer science.
  • Give skills to analyze pros and cons of algorithms, in particular with respect to the use of resources.
  • Give knowledge and understanding of a selection of core algorithms and data structures developed within computer science.

Expected learning outcome

The learning objective of the course is that the student demonstrates the ability to:
  • use the algorithms taught in the course on concrete problem instances.
  • give precise arguments for the correctness or incorrectness of an algorithm.
  • determine the asymptotic running time of an algorithm.
  • adapt known algorithms and data structures to special cases of known problems or new problems.
  • design new algorithms for problems similar to those taught in the course, including giving a precise description of the algorithm, e.g. using pseudocode.
  • make expedient choices of data structures.
  • design new data structures based on known data structures.
  • design and implement a larger program, using algorithms and data structures taught in the course.
  • give precise arguments for the choices made in connection with the previous four items.

Content

The following main topics are contained in the course:
  • Mathematical basis: recursion equations, invariants.
  • Algorithms: correctness and complexity analysis, divide and conquer (Master Theorem, Strassen's algorithm), greedy algorithms, dynamic programming, sorting algorithms (insertionsort, mergesort, heapsort, quicksort, countingsort, radixsort), graph algorithms (BFS, DFS, topological sorting of DAGs, connected components, strongly connected components, MST, SSSP, APSP), Huffmann coding.
  • Data structures: dictionaries (BSTs, red-black trees, hashing), priority queues, disjoint sets.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Spring

Tests

A mandatory project

EKA

N330068112

Assessment

Second examiner: None

Grading

Pass/Fail

Identification

Full name and SDU username

Language

Normally, the same as teaching language

Examination aids

To be announced during the course

ECTS value

2.5

Exam element b)

Timing

June

Tests

Written exam

EKA

N330068102

Assessment

Second examiner: External

Grading

7-point grading scale

Identification

Student Identification Card - Exam number

Language

Normally, the same as teaching language

Duration

3 hours

Examination aids

All common aids are allowed e.g. books, notes, computer programmes which do not use internet etc. 

Internet is not allowed during the exam. However, you may visit system DE-Digital Exam when answering the multiple-choice questions. If you wish to use course materials from itslearning, you must download the materials to your computer the day before the exam. During the exam itslearning is not allowed.

ECTS value

7.5

Additional information

The reexam in August is an oral exam with external examiner and grades according to the 7-point grading scale.

Indicative number of lessons

88 hours per semester

Teaching Method

Teaching activities are reflected in an estimated allocation of the workload of an average student as follows:

  • Intro phase (lectures) - 44 hours
  • Training phase: 44 hours

Teaching form: Assignments in study groups.

Teacher responsible

Name E-mail Department
Rolf Fagerberg rolf@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
BSc major in Computer Science - Registration 1 September 2019 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E23
BSc major in Computer Science and minor in Mathematics - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science and minor in Mathematics - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E23
BSc major in Computer Science and minor subject - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science and minor subject - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 2 E23
BSc major in Computer Science and minor subject - Registration 1 September 2019 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science special course - Registration 1 September 2019, 2020, 2021 og 2022 Bachelor of Science in computer science | Odense 2 E22
BSc major in Computer Science special course - Registration 1 September 2020, 2021 og 2022 Bachelor of Science in computer science | Odense 2 E23
No longer applicable (31 August 2020): BSc major in Computer Science - Registration 1 September 2019 Bachelor of Science in computer science | Odense 2 E22
No longer applicable (31 August 2020): BSc major in Computer Science and minor subject - Registration 1 September 2019 Bachelor of Science in computer science | Odense 2 E22
No longer applicable (31 August 2020): BSc major in Computer Science and minor subject area - Registration 1 September 2019 Bachelor of Science in computer science | Odense 2 E22
BSc major in Applied Mathematics - registration 1 September 2019 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E22
BSc major in Applied Mathematics - registration 1 September 2021 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E22
BSc major in Applied Mathematics - registration 1 September 2021 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E23
BSc major in Applied Mathematics - registration 1 September 2021 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E22
BSc major in Applied Mathematics - registration 1 September 2021 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E24
BSc major in Applied Mathematics - registration 1 September 2021 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E23
BSc major in Applied Mathematics - registration 1 September 2022 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E22
BSc major in Applied Mathematics - registration 1 September 2022 and 2023 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E23
No longer valid - 31 August 2021 BSc major in Applied Mathematics - registration 1 September 2020 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E22
No longer valid - 31 August 2021 BSc major in Applied Mathematics - registration 1 September 2020 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 4 E23
BSc major in Applied Mathematics - registration 1 September 2020 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 6 E23
BSc major in Applied Mathematics - registration 1 September 2020 Bachelor of Science (BSc) in Applied Mathematics | Bachelor of Science in Applied Mathematics | Odense 6 E22
BSc minor in Computer Science for major in Biology eller Chemistry - Registration 1 September 2020, 2021 og 2022 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Biology eller Chemistry - Registration 1 September 2020, 2021, 2022 and 2023 Bachelor of Science in computer science | Odense 6 E23
BSc minor in Computer Science for major in Biology, Chemistry or subject area outside Natural Science - Registration 1 September 2019 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Biology, Chemistry or subject area outside Natural Science - Registration 1 September 2019, 2020 and 2021 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Biology, Chemistry or subject area outside Natural Science - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 6 E23
BSc minor in Computer Science for major in Mathematics - Registration 1 September 2019 and 2020 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Mathematics - Registration 1 September 2019, 2020 and 2021 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Mathematics - Registration 1 September 2020 Bachelor of Science in computer science | Odense 6 E23
BSc minor in Computer Science for major in Mathematics - Registration 1 September 2020 and 2021 Bachelor of Science in computer science | Odense 6 E23
BSc minor in Computer Science for major in Physics - Registration 1 September 2019 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Physics - Registration 1 September 2020, 2021 og 2022 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Computer Science for major in Physics - Registration 1 September 2020, 2021, 2022 and 2023 Bachelor of Science in computer science | Odense 6 E23
BSc minor in Informatics for major subject area outside Natural Science - Registration 1 September 2022 Bachelor of Science in computer science | Odense 6 E22
BSc minor in Informatics for major subject area outside Natural Science - Registration 1 September 2022 and 2023 Bachelor of Science in computer science | Odense 6 E23
No longer applicable (31 August 2020): BSc minor in Computer Science for major in Mathematics - Registration 1 September 2019 og 2020 Bachelor of Science in computer science | Odense 6 E22
No longer applicable (31 August 2020): BSc minor in Computer Science for major in Mathematics - Registration 1 September 2020 Bachelor of Science in computer science | Odense 6 E23
No longer valid per. August 31, 2021: BSc minor in Computer Science for major in Physics - Registration 1 September 2019 and 2020 Bachelor of Science in computer science | Odense 6 E22
No longer valid per. August 31, 2021: BSc minor in Computer Science for major in Physics - Registration 1 September 2020 Bachelor of Science in computer science | Odense 6 E23

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.