Uni-Logo
Algorithms and Complexity
 

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


Schedule

There will be an introductory session on Wednesday, 27th 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 further below.

There will be a pre-recorded online lecture combined with an interactive exercise lesson. The recorded lectures is available on a separate page. The interactive session takes places on Wednesdays 16:15 - 18:00 via Zoom. Details on how to access the Zoom meeting are given in the further below.

Note: There is no exercise session on June 15th.


Details for Online Events

Zoom: 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.

Zulip: We also use Zulip for communication among students and teaching staff. Zulip can be seen as a mixture of instant messenger and a classical forum. The link is also given on this website. Important note: Again: This website can only be accessed from within the university network or via VPN.

Video Lecutres: The recorded lectures will be published on the following page: Recordings and Slides


Exercises

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 04.05. exercise-01, QuickSort.py solution 01, QuickSort.py
O-Notation 11.05. exercise-02 solution 02
Linear Time Sorting 03.06. exercise 03, BucketSort.py, RadixSort.py, Queue.py, ListElement.py solution 03, BucketSort.py, RadixSort.py
Resolution of Collissions 10.06. exercise 04, HashTable solution 04, HashTable,
Hashfunctions 31.05. exercise 05 solution 05
Binary Search Trees 15.06. exercise 06, BST, input solution 06, BST
Balanced Trees 22.06 exercise 07 solution 07
Graph Traversal 29.06 exercise 08, AdjacencyList.py, Scheduling.py, dag.txt solution 08, Scheduling.py
Minimum Spanning Trees 07.07 exercise 09, TSP.py, AdjacencyMatrix.py, cities.txt Solution 09, TSP
Shortest Paths 15.07 exercise 10, Maze.py, WeighAdjList.py, maze.txt maze_vis.txt Solution 10, Maze.py, solution.txt
Dynamic Programming 20.07 exercise 11, DP.py, set1.txt, set2.txt, set3.txt solution 11, DP.py
String Matching 27.07 exercise 12, StringMatching, input solution 12, StringMatching
Bonus 03.08 exercise 13, Heap

Submission of Exercises

Handing in exercises is voluntary, but we highly 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 exercises are conducted via the course management system Daphne. There will be theortical and programming parts.

The submission works as follows: For each exercise sheet, create a subfolder exercise-xy in your SVN repository where xy 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 (More details are given on this separate page).

Solutions to theoretical exercises can be written in Latex (preferred), Word (or similar text programs) or handwritten scans which must be well readable. Here you can find a more detailed description how to submit solutions to programming tasks.


Literature