Algorithms and Complexity

Algorithms and Datastructures - Conditional Course
Summer Term 2020
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).


  • Type of exam: The exam will be oral.
  • Date: 11th September.
  • Time: Each Student will be assigned a time slot. We will contact you with the exact time you should appear.
  • Duration: 30 Minutes.
  • Place: Probably some seminar room in building 106. We will clarify that soon.
  • 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).


There will be an introductory session on Wednesday, 13th of May 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.


There will be a pre-recorded online lecture combined with an interactive online exercise lesson. The recurring date is Wednesdays 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 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. Alternatively, the required information is also available in the forum of this course (there is an according announcement).

The recorded lectures will be published on the following page:

Recordings and Slides


The exercises will be conducted online with the course management system Daphne. There will be theoretical and programming exercises.

Topic Due (4 pm) Exercise Solution

Sorting 20.05. exercise 01, QuickSort, SelectionSort, MergeSort solution 01, QuickSort, plot-linear, plot-logscale
O-Notation 27.05. exercise 02 solution 02
Sorting in Linear Time 03.06. exercise 03, BucketSort, RadixSort, Queue, ListElement solution 03, BucketSort, RadixSort, plot
Resolution of Collissions 10.06. exercise 04, HashTable solution 04, HashTable, plot-logscale, plot-linear
Hashfunctions 17.06. exercise 05 solution 05
Binary Search Trees 24.06. exercise 06, BST, input solution 06, BST
Balanced Trees 01.07 exercise 07 solution 07
Graph Traversal 08.07 exercise 08, AdjacencyList, Scheduling, dag, forest solution 08, Scheduling, dag, forest
Minimum Spanning Trees 15.07 exercise 09, TSP, AdjacencyMatrix, cities solution 09, TSP
Shortest Paths 22.07 exercise 10, Maze, WeighAdjList, maze solution 10, Maze, maze_vis
Dynamic Programming 29.07 exercise 11, DP, set1, set2, set3 solution 11, DP
String Matching 05.08 exercise 12, StringMatching, input solution 12, StringMatching

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 Wednesday, 4 pm (the week after it has been released). The submission works as follows: For each exercise sheet, create a subfolder uebungsblatt-xx in your SVN repository where xx is the number of the exercise sheet (one-digit numbers with a leading zero, i.e., 01, 02,...). Upload your exercises (theoretical and programming) into that folder. Your programming exercises must be uploaded directly into this folder (no subfolder) to be checked automatically by Jenkins.

Solutions to theoretical exercises can be written in Latex (preferred), Word (or similar text programs) or handwritten scans.

Here you can find a more detailed description how to submit solutions to programming tasks.