Algorithms and Complexity

Algorithms and Datastructures - Conditional Course
Undergraduate Course - Winter Term 2019/20
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: There will be no exercise leson on January 8.

Our regular meeting takes place each Wednesday from 12:15 pm to 2:00 pm in building 101 room SR 01-016.


Exam Review: Due to the current situation with COVID-19, exam reviews have to be conducted digitally. If you want to review your graded exam, please contact me (philipp.schneider(at)cs.uni-freiburg.de).

Time: The exam will take place on March 9 at 3 pm (9. März, 15 Uhr). The exam will take (at most) 120 minutes.

Place: Building 101 Room 026.

Mode: The exam will be a written exam.

Language: The exam questions will be given in English (it is OK to write answers in German).

Open Book: Everyone is allowed to bring anything that is written or printed on paper (books, cheat sheets, dictionary, etc.). Electronic devices are not allowed!

Student ID: Please remember to bring your student ID with you to the exam!

Slides and Recordings

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

No. Topic Slides Recordings

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


Exercises are voluntary, but we highly recommend doing them. If you want feedback for your solution, you can submit them to philipp.Schneider(at)cs.uni-freiburg.de (documents prepared with (La)TeX preferred, documents generated with MS Word or similar "Wysiwyg" editors are ok, if you send a scan of a handwritte solution make sure it is easily readable, i.e., no photos). Or bring it as hard copy to the subsequent exercise class (on the Wednesday after the exercise is assigned). No feedack will be given on late submissions (after due date).

Important Note: If you submit the exercises via email, *please* use the subject matter "AD EX [number]" (for [number] insert the current exercise sheet number). This allows me to filter out your submissions and ensures I do not overlook any. If you want to contact me per mail, use an email seperate from your exercise submission.

Topic(s) Assigned Date Due Date Exercises Solution Files

Sorting 23.10.2019 30.10.2019 Exercise 01 Solution 01 b_sort, c_sort, s_test
O-Notation 30.10.2019 06.11.2019 Exercise 02 Solution 02 -
Avg. Runtime, Hashing 06.11.2019 13.11.2019 Exercise 03 Solution 03 -
Hashing, Amort. Analysis 13.11.2019 20.11.2019 Exercise 04 Solution 04 -
Divide & Conquer 20.11.2019 27.11.2019 Exercise 05 Solution 05 -
Div & Con, Heaps, BSTs 27.11.2019 04.12.2019 Exercise 06 Solution 06 -
BST-, AVL-, (a,b)-Trees 04.12.2019 11.12.2019 Exercise 07 Solution 07 -
Graphs, DFS, BFS 11.12.2019 18.12.2019 Exercise 08 Solution 08 -
Shortest Paths 20.12.2019 15.01.2020 Exercise 09 Solution 09 -
Dyn. Programming 15.01.2020 22.01.2020 Exercise 10 Solution 10 -
Practice Lesson 23.01.2020 - Exercise 11 Solution 11 -


If you have a question to the lecture or the exercises, please use the forum (click on the word forum for the link) instead of writing an email. Then all of us and also your colleagues see the question and can answer to it. Feel free to also use the forum to discuss anything related to the topics and organization of the lecture.

Old Informatik 2 Exams

Please read this important disclaimer first: These exams originate from another course ("Informatik 2"). The exams are therefore in German. Topics and difficulty level may (and certainly will) differ from the actual exam of this course. Never the less (some of) the exercises may offer you additional practice for the upcoming exam. I put the material online since I was asked for it. You may use it at your own discretion.

Klausur Winter 2018/19,
Klausur Sommer 2018,
Klausur Winter 2016/17,
Klausur Sommer 2016,
Klausur Winter 2014/15,
Klausur Sommer 2014