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.
Schedule
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.
Exam
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) | MP4 | ||
| Runtime Analysis MinSort and HeapSort, Induction | MP4 | ||
| O-Notation, L'Hopital | MP4 | ||
| Runtime Complexity, Associative Arrays | MP4 | ||
| Hash Maps, Universal Hashing | MP4 | ||
| Treatment of Hash Collisions, Priority Queues | MP4 | ||
| Dynamic Arrays, Amortized Analysis | MP4 | ||
| Cache Efficiency, Divide and Conquer | MP4 | ||
| Divide and Conquer, Master Theorem | MP4 | ||
| Linked Lists, Binary Search Trees | MP4 | ||
| Balanced Trees | MP4 | ||
| Graphs, BFS, DFS | MP4 | ||
| Shortest Paths, Dijkstra | MP4 | ||
| Edit Distance, Dynamic Programming | MP4 | ||
Exercises
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 | |
Literature
- Introduction to Algorithms (3rd edition); T. Cormen, C. Leiserson, R. Rivest, C. Stein; MIT Press, 2009
- Algorithms and Data Structures; K. Mehlhorn und P. Sanders; Springer, 2008, available online
- Lectures on MIT Courseware:
Introduction to Algorithms 2005 und Introduction to Algorithms 2011