# Applied Algorithms (Autumn 2023)

#### Official course description:

##### Course info

##### Programme

##### Staff

##### Course semester

##### Exam

##### 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

##### Formal prerequisites

Before the course, the student should be able to:

- Perform basic analysis of algorithm correctness and complexity, using invariants and big-Oh notation.
- Use basic algorithms and data structures when programming (e.g., lists, queues, stacks, search trees, hashing, sorting algorithms, and basic graph algorithms).

##### 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.

##### Learning activities

Students will:

- Attend lectures to learn the theoretical and practical foundations of Applied Algorithms.
- Attend exercises, in which they implement algorithms, run experiments in a guided fashion, and practice talking and writing about algorithms, implementations, and experiments.
- Work on exercises outside of class, and write reports on the results of these exercises.

##### Mandatory activities

The course has 3 mandatory
assignments. You can work in groups of sizes up to 3.

Each MA assignment only consists of one assignment.

The pedagogical purpose of the mandatory activities is to prepare for the
exam assignment.

Written formative feedback will be provided by the teachers or TAs.

If the student fails to hand in a mandatory activity or they receive a
"not-approved", they must hand in a retry two weeks before the exam
submission deadline.

The student will receive the grade NA (not approved) at the ordinary exam, if the mandatory activities are not approved and the student will use an exam attempt.

##### Course literature

The course does not closely follow any textbook. However, some chapters of the following books will be useful:

- "A Guide to Experimental Algorithmics" by Catherine C. McGeoch
- "Computer Architecture: A Quantitative Approach" by Hennessy and Patterson

##### Student Activity Budget

Estimated distribution of learning activities for the typical student- Preparation for lectures and exercises: 7%
- Lectures: 14%
- Exercises: 14%
- Assignments: 28%
- Project work, supervision included: 28%
- Exam with preparation: 9%

##### Ordinary exam

**Exam type:**

D: Submission of written work with following oral, External (7-point scale)

**Exam variation:**

D2G: Submission for groups with following oral exam supplemented by the submission. Shared responsibility for the report.

**Exam submission description:**

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

**Group submission:**

Group

- 1-3

**Exam duration per student for the oral exam:**

20 minutes

**Group exam form:**

Mixed exam 2 : Joint student presentation followed by an individual dialogue. The group makes their presentations together and afterwards the students participate in the dialogue individually while the rest of the group is outside the room.

##### reexam

**Exam type:**

D: Submission of written work with following oral, External (7-point scale)

**Exam variation:**

D2G: Submission for groups with following oral exam supplemented by the submission. Shared responsibility for the report.

**Exam submission description:**

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

**Group submission:**

Group

- 1-3

**Exam duration per student for the oral exam:**

20 minutes

**Group exam form:**

Mixed exam 2 : Joint student presentation followed by an individual dialogue. The group makes their presentations together and afterwards the students participate in the dialogue individually while the rest of the group is outside the room.

##### Time and date

Ordinary Exam - submission Wed, 3 Jan 2024, 08:00 - 14:00Ordinary Exam Wed, 17 Jan 2024, 09:00 - 21:00

Ordinary Exam Thu, 18 Jan 2024, 09:00 - 21:00

Reexam - submission Wed, 28 Feb 2024, 08:00 - 14:00

Reexam Tue, 19 Mar 2024, 09:00 - 20:00