Uni-Logo
Algorithms and Complexity
 

Algorithms and Datastructures - Conditional Course
Winter Term 2023/24
Fabian Kuhn, TA Gustav Schmid

 


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, 17th of Oktober 12:15 - 14:00. The session will take place in presence in Room R 04 007 (G.-Koehler-Allee 106, 4th floor).

The lecture will be in the flipped classroom format, meaning that there will be a pre-recorded lecture videos combined with an interactive exercise lesson. The interactive session takes places on Wednesdays 12:15 - 14:00 in presence.

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!

For any additional questions or troubleshooting please feel free to contact the Teaching Assistant of the course Gustav Schmid schmidg@informatik.uni-freiburg.de.


Exam

  • Type of exam: The exam will be oral.
  • Date: to be determined.
  • 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.

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 25.10. exercise-01, QuickSort.py solution 01, QuickSort.py
O-Notation 08.11. exercise-02 solution 02
Linear Time Sorting 08.11. exercise 03, BucketSort.py, RadixSort.py, Queue.py, ListElement.py solution 03, BucketSort.py, RadixSort.py
Resolution of Collissions 22.11. exercise 04, HashTable solution 04, HashTable
Hashfunctions 29.11. exercise 05 solution 05
Binary Search Trees 06.12. exercise 06, BST.py, input.txt solution 06, BST
Balanced Trees 13.12 exercise 07 solution 07
Graph Traversal 20.12 exercise 08, AdjacencyList.py, Scheduling.py, dag.txt solution 08, Scheduling.py
Minimum Spanning Trees 10.01 exercise 09, TSP.py, AdjacencyMatrix.py, cities.txt Solution 09, TSP
Shortest Paths 24.01 exercise 10, Maze.py, WeighAdjList.py, maze.txt maze_vis.txt Solution 10, Maze.py, solution.txt
Dynamic Programming 17.01 exercise 11, DP.py, set1.txt, set2.txt, set3.txt solution 11, DP.py
String Matching 24.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 TA.

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. (Its also possible to hand in written exercise sheets at the beginning of the lecture)


Literature