Official course description, subject to change:
Preliminary info last published 22/08-19

Applied Algorithms

Course info
Language:
English
ECTS points:
7.5
Course code:
KSAPALG1KU
Offered to guest students:
yes
Offered as a single subject:
yes
Price (single subject):
10625 DKK (incl. vat)
Programme
Level:
MSc. Master
Programme:
Master of Science in Information Technology (Software Design)
Staff
Course semester
Semester
Efterår 2020
Start
24 August 2020
End
31 January 2021
Abbreviation
20202
Exam
Exam type
ordinær
Internal/External
ekstern censur
Grade Scale
7-trinsskala
Exam Language
GB
Abstract

In this course, you will learn how to implement some widely-used algorithms as fast and scalable programs on modern hardware, and how to evaluate your implementation using appropriate test cases and performance experiments.

Description

This course introduces the students to some classical examples of widely used algorithms and uses these to show how to implement an algorithm in a correct and scalable way in the context of a particular application. 
The focus of the course is the implementation, its correctness, the experimental analysis, and the connection to the performance models. 

Examples of well understood computational tasks that can be considered in depth are: 

  • shortest path for cars on road networks 
  • sorting: why different variants of quicksort differ in performance, how to sort strings
  • cache oblivious search trees as file system or database index 
  • matrix multiplication
  • matrix vector multiplication 
  • locality sensitive hashing 
  • k-means clustering 
  • minimum spanning tree 
  • edit distance 
  • approximate neighborhood 
  • distinct elements
  • job scheduling

The course introduces the different algorithmic tasks, the algorithms, the testing methodology and the performance models.  The exercises focus on implementation, testing and interpretation of the measurements

Intended learning outcomes

After the course, the student should be able to:

  • implement a (randomized, parallel) algorithm from a given high-level description (such as pseudo-code). In particular, this includes judging which data structures, libraries, frameworks, programming languages, and hardware platforms are appropriate for the computational task, and using them effectively in the implementation.
  • experimentally evaluate the correctness of an implementation by creating and using adequate test cases.
  • design, perform, and run a performance and scalability experiment. In particular, this includes creating and using adequate families of synthesized or real-world test cases, measuring the computational resource requirements of a particular implementation, and judging if the experimental results conform to a theoretical performance model.
Ordinary exam
Exam type:
D: Submission of written work with following oral, external (7-trinsskala)
Exam variation:
D2G: Submission of written work for groups with following oral exam supplemented by the work submitted. The group has a shared responsibility for the content of the report.
Exam description:

Mixed  2 Exam:

The group makes their presentations together and afterwards the Joint presentation students participate in the dialogue individually while the rest of the group is outside the room.

Hand-in: Implementation and experimental evaluation of a self-developed algorithm, or an algorithm as described in one or several research papers.

Duration of oral exam: 20 minutes per student

Group size: 1-3