Algorithms and Datastructures - Conditional Course
Winter Term 2021/22
Fabian Kuhn
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 graph algorithms (like shortest paths, spanning trees, breadth-first- and depth-first-searches).
Exam
- Type of exam: The exam will probably be oral.
- Date: TBD
- Duration: approx. 20 minutes.
Announcements
There will be an introductory session on Wednesday, 20.10.2021, 12:15 - 14:00. The session will take place online via the conference system Zoom. Details on how to access the Zoom meeting are given below in the section Lecture Material.
Schedule
There will be a pre-recorded online lecture combined with an interactive online exercise lesson. The recurring date is Wednesday 12:05 - 13:50. If the number of participants is low, then the recurring date can be changed in agreement with all participants and the tutor. Details on how to access the Zoom meeting are given below in the section Lecture Material.
Lecture Material
All details for the weekly Zoom meeting and for Zulip are given on a seperate website. Important note: This website can only be accessed from within the university network. This can be done either by accessing the internet via the university eduroam, or by establishing a VPN tunnel to the university network. Note that you have to cancel the VPN tunnel again before you enter the Zoom meeting.
The recorded lectures will be published on the following page:
Exercises
| Topic | Due (4 pm) | Exercise | Solution | |
| Sorting | 24.10.2021 | exercise 01 | solution 01 | |
| O-Notation | 31.10.2021 | exercise 02 | solution 02 | |
| Sorting Numbers Fast | 7.11.2021 | exercise 03 | solution 03 | |
| Resolution of Collisions | 14.11.2020 | exercise 04 | solution 04 | |
| Hashfunctions | 21.11.2021 | exercise 05 | solution 05 | |
| Binary Search Trees | 28.11.2021 | exercise 06 | solution 06 | |
| Binary Search Trees II | 05.12.2021 | exercise 07 | solution 07 | |
| Graph Traversal | 12.12.2021 | exercise 08 | solution 08 | |
| Minimum Spanning Trees | 19.12.2021 | exercise 09 | solution 09 | |
| Shortest Paths | 09.01.2022 | exercise 10 | solution 10 | |
| Dynamic Programming | 16.01.2022 | exercise 11 | solution 11 | |
| String Matching | 23.01.2022 | exercise 12 | solution 12 | |
Submission of Exercises
Handing in exercises is voluntary, but we recommend doing it. If you want feedback to your solutions, you must submit them by Sunday. The submission works as follows: send an email to alkida.balliu at cs.uni-freiburg.de or dennis.olivetti at cs.uni-freiburg.de.
Solutions can be written in Latex (preferred), Word (or similar text programs) or handwritten scans. For exercises that require to write code, please also attach the source code.
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