---

Algorithms and Datastructures - Conditional Course
Summer Term 2023
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, 19th of April at 14:15 in presence in room 051-00-031.

There will be a pre-recorded online lecture combined with an interactive exercise lesson. The interactive session takes places on Wednesdays 14:15 - 16:00 in room 051-00-031.

The recorded lectures and corresponding slides are available on a separate page. Slides & Recordings

Forum: Zulip

We will offer an instant messaging platform (Zulip) for all students to discuss all topics related to this lecture, where you are free to discuss among yourself or pose questions to us.

Most of the communication will happen over Zulip so it is highly recommended you sign up for Zulip and regularly check for updates.

You must be either inside the eduroam network or be connected to the university network via a VPN to access the Link!

Exercises

There will be theoretical and programming exercises, designed to teach you the algorithms and methods discussed in the lecture. Actively participating in the exercises and working through the provided feedback is the best way to prepare for the exam!

	Topic	Due (12 pm)	Exercise	Solution
	Sorting	26.04.	exercise-01, QuickSort.py	solution 01, QuickSort.py
	O-Notation	03.05.	exercise-02	solution 02
	Linear Time Sorting	10.5.	exercise 03, BucketSort.py, RadixSort.py, Queue.py, ListElement.py	solution 03, BucketSort.py, RadixSort.py
	Resolution of Collissions	17.05.	exercise 04, HashTable	solution 04, HashTable plot-logscale, plot-linear
	Hashfunctions	24.05.	exercise 05	solution 05
	Binary Search Trees	07.06.	exercise 06, BST.py, input.txt	solution 06, BST
	Balanced Trees	14.6	exercise 07	solution 07
	Graph Traversal	21.06	exercise 08, AdjacencyList.py, Scheduling.py, dag.txt	solution 08, Scheduling.py
	Minimum Spanning Trees	28.06	exercise 09, TSP.py, AdjacencyMatrix.py, cities.txt	Solution 09, TSP
	Shortest Paths	05.07	exercise 10, Maze.py, WeighAdjList.py, maze.txt maze_vis.txt	Solution 10, Maze.py, solution.txt
	Dynamic Programming	12.07	exercise 11, DP.py, set1.txt, set2.txt, set3.txt	solution 11, DP.py
	String Matching	25.01	exercise 12, StringMatching, input	solution 12, StringMatching

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, 12 pm.

The submission is simply via Zulip: create a .zip archive containing all of your solution files and send that archive as a private Message to the tutor: Mohsen Al-Zeqri

Programming exercises should be solved using Python and handed in as .py files (inside the .zip file).

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

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