Uni-Logo
Algorithms and Complexity
 


Algorithms and Datastructures - Conditional Course
Winter Term 2020/21
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: The exam will be oral.
  • Date: TBD
  • Duration: 30 Minutes.

Announcements

ALL the exercise sessions will start 1 hour earlier than previously announced, that is they will take place on Tuesday 11:15 - 13:00

There will be an introductory session on Tuesday, 3rd of November 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 Tuesday 11:15 - 13: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:

Recordings and Slides

Exercises


Topic Due (4 pm) Exercise Solution

Sorting 08.11.2020 exercise 01 solution 01
O-Notation 15.11.2020 exercise 02 solution 02
Sorting Numbers Fast 22.11.2020 exercise 03 solution 03
Resolution of Collisions 29.11.2020 exercise 04 solution 04
Hashfunctions 06.12.2020 exercise 05 solution 05
Binary Search Trees 13.12.2020 exercise 06 solution 06
Binary Search Trees II 20.12.2020 exercise 07 solution 07
Graph Traversal 10.01.2021 exercise 08 solution 08
Minimum Spanning Trees 17.01.2021 exercise 09 solution 09
Shortest Paths 24.01.2021 exercise 10 solution 10
Dynamic Programming 31.01.2021 exercise 11 solution 11
String Matching 07.02.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