Algorithms and Datastructures - Conditional Course
Summer Term 2021
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 graphalgorithms (like shortest paths, spanning trees breadth-first- and depth-first-searches).
Exam
- Type of exam: TBD
- Date: TBD
- Time: TBD
- Duration: TBD
- Place: TBD
- Measures due to Corona: We might offer to do the exam online via a online conference system (we will clarify that later). If the exam takes place physically, we will have a large, well ventilated room and distancing measures. Also you should bring a mask when entering the building and the seminar room (you can remove it during the exam).
Announcements
The exercise session of 14.07.2021 will take place at 14:15.
There will be an introductory session on Wednesday, 21st of April 16:15 - 18: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 16:15 - 18:00. 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 | Exercise | Solution | |
| Sorting | 27.04.2021 | exercise 01 | solution 01 | |
| O-Notation | 02.05.2021 | exercise 02 | solution 02 | |
| Sorting Numbers Fast | 09.05.2021 | exercise 03 | solution 03 | |
| Resolution of Collisions | 16.05.2021 | exercise 04 | solution 04 | |
| Hashfunctions | 23.05.2021 | exercise 05 | solution 05 | |
| Binary Search Trees | 06.06.2021 | exercise 06 | solution 06 | |
| Binary Search Trees II | 13.06.2021 | exercise 07 | solution 07 | |
| Graph Traversal | 20.06.2021 | exercise 08 | solution 08 | |
| Minimum Spanning Trees | 27.06.2021 | exercise 09 | solution 09 | |
| Shortest Paths | 04.07.2021 | exercise 10 | solution 10 | |
| Dynamic Programming | 11.07.2021 | exercise 11 | solution 11 | |
| String Matching | 18.07.2021 | 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 python 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