Uni-Logo
Algorithms and Complexity
 


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:

Recordings and Slides

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