Algorithms and Complexity

Algorithms and Datastructures - Conditional Course
Undergraduate Course - Summer Term 2019
Fabian Kuhn


Course Format

We provide recordings by Prof. Backofen and an exercise sheet every week. The solutions to the exercises and questions about the lecture are discussed in the exercise lessons.


Announcement: On Wednesday, May 22 there will be no exercise lesson. Exercise sheet 03 will be discussed in the week after, on May 29.

The exercise lessons take place on Wednesday from 16:15 pm to 17:45 pm in room 00-015, building 106.


There will be an oral exam. The date will be announced.

Slides and Recordings

Slides and recordings are taken from lectures from different years and differ slightly.

Topic Slides Recordings

Introduction, Sorting (You can ignore the part on organisation) PDF MP4
Runtime Analysis MinSort and HeapSort, Induction PDF MP4
O-Notation, L'Hopital PDF MP4
Runtime Complexity, Associative Arrays PDF MP4
Hash Maps, Universal Hashing PDF MP4
Treatment of Hash Collisions, Priority Queues PDF MP4
Dynamic Arrays, Amortized Analysis PDF MP4
Cache Efficiency, Divide and Conquer PDF MP4
Divide and Conquer, Master Theorem PDF MP4
Linked Lists, Binary Search Trees PDF MP4
Balanced Trees PDF MP4
Graphs, BFS, DFS PDF MP4
Shortest Paths, Dijkstra PDF MP4
Edit Distance, Dynamic Programming PDF MP4


If you want feedback to your solution, you can submit them to philipp.bamberger(at)cs.uni-freiburg.de or philipp.Schneider(at)cs.uni-freiburg.de or bring it as hard copy to the exercise lessons.

Topic(s) Assigned Date Due Date Exercises Sample Solution

Sorting 29.04.2019 08.05.2019 Exercise 01 Solution 01
O-Notation 08.05.2019 15.05.2019 Exercise 02 Solution 02
Average Runtime, Hash Functions 15.05.2019 29.05.2019 Exercise 03 Solution 03
Univ. Hashing, Collision Resolution 29.05.2019 05.06.2019 Exercise 04 Solution 04
Priority Queues, Amortized Analysis 05.06.2019 19.06.2019 Exercise 05 Solution 05
Master Theorem, Divide & Conquer 19.06.2019 26.06.2019 Exercise 06 Solution 06
Binary Search Trees 26.06.2019 03.07.2019 Exercise 07 Solution 07
AVL Trees, (a,b)-Trees 03.07.2019 10.07.2019 Exercise 08 Solution 08
Graph Traversal, Dijkstra 10.07.2019 17.07.2019 Exercise 09 Solution 09
Edit Distance, Dynamic Programming 17.07.2019 24.07.2019 Exercise 10 Solution 10