Uni-Logo
Algorithms and Complexity
 

Algorithm Theory
Graduate Course - Winter Term 2024/25
Fabian Kuhn

 


Course Description

The design and analysis of algorithms is fundamental to computer science. In this course, we will study efficient algorithms for a variety of basic problems and, more generally, investigate advanced design and analysis techniques. The central topics are algorithms and data structures that go beyond what has is covered in a standard Algorithms and Data Structures lecture. Basic algorithms and data structures knowledge, comparable to what is done in the basic Algorithms and Data Structures lecture in the computer science bachelor program in Freiburg is therefore assumed. The topics of the course include (but are not limited to):

  • Divide and conquer algorithms: geometric divide and conquer, fast fourier transformation
  • Greedy algorithms: minimum spanning trees, scheduling, matroids
  • Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
  • Amortized analysis and advanced data structures: Fibonacci heaps, union-find data structures
  • Graph algorithms: network flows, combinatorial optimization problems on graphs
  • Randomization: median, randomized quicksort, probabilistic primality testing, randomized graph algorithms
  • Approximation and online algorithms

Schedule

Lectures: Tuesdays, 16:15 - 18:00, room 101-00-026

Exercise Tutorials: Fridays, 10:15 - 12:00, room 101-00-026

Exercises: There will be an exercise sheet every week which you should work on at home. We accept and also recommend to submit the exercise sheets in groups of at most four people. The exercises will be published every Friday and they are due one week later.

Lecture Material

We provide recordings and the annotated slides of the Tuesday lectures. For convenience, we also provide lecture videos that we prepared for the Algorithm Theory lecture in the winter term 2020/21. Those videos are more polished than the videos from the live lectures. Note that the material that we covered in 2020/21 is very similar to the material covered in the current lecture. It is however not identical


Important note: The recordings can only be accessed from within the university network. This can be done by establishing a VPN tunnel to the university network.

Exam Information

The exam will take place after the semester either in February or March 2025 (an exact date will be published here once it is known). The exam will be a two-hour written exam. The only material allowed at the exam will be 6 A4 pages of handwritten notes (6 one-sided or 3 double-sided A4 sheets).

Forum

Instant Messenger: 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. Please consider the section below on technical information.


Exercises

Format: All submissions must be in, or converted to pdf format and be written in English. We strongly recommend to prepare your solutions with Latex for best readability (being able to work with latex is a good skill to have anyway). Solutions prepared with Word or similar text editors are ok. Scans or photos of handwritten solutions in pdf format are ok as well, but must be well readable!

Submission Guidelines: The exercises will be conducted online with the course management system Daphne. The solution of each exercise must be uploaded to your SVN repository each one in a separate folder named exercise-XY, where XY is the exercise number (with a leading 0 if that number is smaller than 10). More on the submission via SVN in the technical information section.

Team Submission: Teams will be allowed. We recommend to build teams of three or four members. Teams may consist of at most four members. In case you submit your solution as part of a team, each team member must still submit a copy of the solution pdf to their respective SVN-repository (c.f. technical information). The members of the teams must be clearly marked on the top of the solution pdf.

Responsible for the exercises are Marc Fuchs, Salwa Faour and Attila Edmund Mályusz.

Exercise sheet Assigned Due (10 am) Solution
Exercise 01 (Divide & Conquer) 18.10. 25.10. Solution 01
Exercise 02 (FFT) 25.10. 04.11. Solution 02
Exercise 03 (Greedy) 01.11. 08.11. Solution 03
Exercise 04 (Dynamic Programming) 08.11. 15.11. Solution 04
Exercise 05 (Dynamic Programming and Amortized Analysis) 15.11. 22.11. Solution 05
Exercise 06 (Union-Find) 22.11. 29.11. Solution 06
Exercise 07 (Fibonacci Heaps) 29.11. 06.12. Solution 07
Exercise 08 (Max-Flow) 06.12. 13.12. Solution 08
Exercise 09 (Max-Flow) 13.12. 20.12. Solution 09
Exercise 10 (Matching) 20.12. 10.01.

Technical Information

Zulip: The Zulip data is available here.
Important note: This website can only be accessed from within the university network. This can be done by establishing a VPN tunnel to the university network.
An introduction to Zulip is given here: Getting Started (in particular, note that Zulip supports Latex)

Daphne: The exercises are submitted via Daphne. To register for the Algorithm Theory course with your rz-account. On Daphne, an overview of the points you achieved so far is given. Exercises are also published there.

Subversion (SVN): After registration, a SVN repository will be created for you with an URL of the following form:

https://daphne.informatik.uni-freiburg.de/ws2324/AlgoTheo/svn/your-rz-account-name

You should do a "checkout" of your SVN-repository (using the URL described above) to get a local copy on your pc. With the command "update" you synchronize your local copy with the current version on the server. Through the command "commit" you upload your local files to your repository on the server. A more detailed overview can be found here. There are different subversion clients you can use. For Windows Tortoise-SVN is recommended.

Note that every solution of an exercise sheet must be uploaded ("committet") to a separate folder named exercise-XY, where XY is the exercise number (with a leading 0 if smaller than 10). This folder will be automatically locked (that is, no commits are possible anymore) after the submission deadline!


Past Exams

Literature

  • Jon Kleinberg and Éva Tardos: Algorithm Design, Addison Wesley
  • Thomas H. Cormen, Charles E. Leiserson, Robert L. Rivest, and Cliford Stein: Introduction to Algorithms, MIT Press
  • Thomas Ottmann and Peter Widmayer: Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag