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.
Schedule
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
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) | MP4 | ||
| 2 | Runtime Analysis MinSort and HeapSort, Induction | MP4 | ||
| 3 | O-Notation, L'Hopital | MP4 | ||
| 4 | Runtime Complexity, Associative Arrays | MP4 | ||
| 5 | Hash Maps, Universal Hashing | MP4 | ||
| 6 | Treatment of Hash Collisions, Priority Queues | MP4 | ||
| 7 | Dynamic Arrays, Amortized Analysis | MP4 | ||
| 8 | Cache Efficiency, Divide and Conquer | MP4 | ||
| 9 | Divide and Conquer, Master Theorem | MP4 | ||
| 10 | Linked Lists, Binary Search Trees | MP4 | ||
| 11 | Balanced Trees | MP4 | ||
| 12 | Graphs, BFS, DFS | MP4 | ||
| 13 | Shortest Paths, Dijkstra | MP4 | ||
| 14 | Edit Distance, Dynamic Programming | MP4 | ||
Exercises
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 | - | |
Forum
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
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