Algorithms and Datastructures - Conditional Course
Winter Term 2024/25
Fabian Kuhn, TA Gustav Schmid
Course Description
This lecture revolves around the design and analysis of algorithms. We will discuss the concepts and principles of a selection of the very basic but most commonly used algorithms and datastructures. Topics will include for example: Sorting, searching, hashing, search-trees, (priority-)queues and graphalgorithms (like shortest paths, spanning trees, breadth-first- and depth-first-searches).
Schedule
There will not be a session on the 16th of October!
There will be an introductory session on Wednesday, 23th of October 12:15 - 14:00. The session will take place in presence in Room SR 00-010/14 (G.-Koehler-Allee 101, ground floor).
The lecture will be in the flipped classroom format, meaning that there will be a pre-recorded lecture videos combined with an interactive exercise lesson. The interactive session takes places on Wednesdays 12:15 - 14:00 in presence in room SR 00-010/14 (G.-Koehler-Allee 101, ground floor).
The recorded lectures and corresponding slides are available on a separate page. Slides & Recordings
Forum: Zulip
We offer an instant messaging platform (Zulip) for all students to discuss all topics related to this lecture, where you are free to discuss among yourself or pose questions to us.
Most of the communication will happen over Zulip so it is highly recommended you sign up for Zulip and regularly check for updates.
You must be either inside the eduroam network or be connected to the university network via a VPN to access the Link!
For any additional questions or troubleshooting please feel free to contact the Teaching Assistant of the course schmidg@informatik.uni-freiburg.de.
Exam
In the exam we expect students to go beyond the algorithms that they have seen in the lecture. Instead we will ask students to come up with algorithms for new problems and have the students give mathematical arguments why their algorithm is both correct and efficient. The only real way to learn this skill is to participate in the lectures and do the exercises.
We will update exact information about the exam here in this website once we know it. We will have a written exam!
- Type of exam: Written Exam (changed from last term!)
- Date: 12.03.2025
- Time and Room: 14:00, room still to be determined
- Duration: 180 Minutes
- Allowed Material: The exam will be written on paper and so you will need a non erasable pen. Additionally we allow 6 A4-pages of hand written notes. (either 3 sheets of A4 paper with text on both sides, or 6 sheets of A4 paper with text only on a single side). We do not allow any form of electronic devices (so no calculator).
The above info is subject to change, so please check back here a few weeks before the actual exam.
Exercises
There will be theoretical and programming exercises, designed to teach you the algorithms and methods discussed in the lecture. The goal of this lecture is for you to be able to design algorithms yourself and prove guarrantees about these algorithms. This skill is not easy to come by and just reading a book will not get you there. Just implementing a few of these algorithms in the programming language of the month will not do. Instead the goal is to think ahead of time how an algorithm is supposed to behave, irrespective of the actual implementation in a certain language on a certain system. To learn this one has to actively sit down and invest some time to practice this! Actively participating in the exercises and working through the provided feedback is the best way to prepare for the exam!
Topic | Due (12 pm) | Exercise | Solution | |
Introduction | 30.10. | exercise-00, | solution 00 | |
Sorting | 06.11. | exercise-01, QuickSort.py | ||
Big O Notation | 06.11. | exercise-02 |
Submission of Exercises
Handing in exercises is voluntary, but we highly recommend doing it. If you want feedback to your solutions, you must submit them by Wednesday, 12 pm.
The submission is simply via Zulip: create a .zip archive containing all of your solution files and send that archive as a private Message to the TA.
Programming exercises should be solved using Python and handed in as .py files (inside the .zip file).
Solutions to theoretical exercises can be written in Latex (preferred), Word (or similar text programs) or handwritten scans which must be well readable. Its also possible to hand in written exercise sheets at the beginning of the lecture. For hand written solutions, either scanned or handed in, we expect that solutions are written up clearly on a separate piece of paper with proper structure.
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