Uni-Logo
Algorithms and Complexity
 


Algorithm Theory
Graduate Course - Winter Term 2021/22
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. Central topics are algorithms and data structures that go beyond what has been considered in the undergraduate course Algorithms and Datastructures. Basic algorithms and data structures knowledge, comparable to what is done in Algorithms and Datastructures is therefore assumed. The topics of the course include (but are not limited to):

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

Exam Information

  • Review: 12.05.22, 1:00 pm in room 00 015, building 106.
  • Date and time. 22.03.2022, 9:00 - 11:00 am (2 hours). Please arrive by 8:45 am.
  • Mode. The exam will be written.
  • Location. Building 101 Room 00-026. Enter only after the student ID has been checked at the entrance.
  • Allowed material. 5 A4 pages (corresponds to 5 singly-sided A4 sheets) of handwritten notes.
  • Preparation. Old exams are available further below. We will also offer an exam Q&A session on Friday 18th of March 4pm using our usual Zoom channel to discuss previous exam tasks. On Zulip you can make suggestions which exam tasks we should cover.
  • Corona Information. You have to bring a proof of vaccination (COVID App). Everyone has to wear a FFP2 mask or equivalent (a surgical mask is not sufficient) during the whole exam.

Lecture Format

Lectures: The lecture will be given in a recorded form. Each week we will release a new video which you are supposed to watch. Click here for the videos and slides.

Q&A Sessions: Each week on Tuesday from 16:15 - 17:45, we will organize a 90-minute Question and Answer session, where we can discuss any questions regarding the lecture material in detail. As long as possible and as long as there is sufficient interest, we will try to offer the Q&A session in a hybrid form. You can attend the session at the university in room 101-00-026 (3G rules apply = certificate of being vaccinated, recovered from COVID, or negatively tested needs to be shown). At the same time, the Q&A session can also be attended online through Zoom. The Zoom data is available here. Please also consider the section below on technical information.

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. The Zulip data is available here. Please consider the section below on technical information.


Schedule

Introductory Session: There will be an introductory event on Tuesday, October 19 at 16:15 pm. Like the Q&A session, the introductory event can be attended in person in room 101-00-026 or online through Zoom (zoom meeting info).

Exercises: There will be an exercise sheet every week which you should work on at home after watching the according lecture. The exercises will be published every Tuesday at 4 pm. They are due one week later (also at Tuesday 4 pm).

Exercise Classes: Questions to the exercises can be discussed in the Q&A sessions on Tuesday, 16:15 to 17:45. If there is sufficient interest, we might offer a separate exercise session at another time in the week.


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

Exercise sheet Assigned Due (4 pm) Solution

Exercise 01 (O-Notation, Divide & Conquer) 19.10.2021 26.10.2021 Solution 01
Exercise 02 (Divide & Conquer, FFT) 26.10.2021 02.11.2021 Solution 02
Exercise 03 (Greedy Algorithms) 02.11.2021 09.11.2021 Solution 03
Exercise 04 (Dynamic Programming) 09.11.2021 16.11.2021 Solution 04
Exercise 05 (Amortized Analysis) 16.11.2021 23.11.2021 Solution 05
Exercise 06 (Fibonacci Heaps) 23.11.2021 30.11.2021 Solution 06
Exercise 07 (Graph Algorithms) 30.11.2021 07.12.2021 Solution 07
Exercise 08 (Maximum Flow) 07.12.2021 14.12.2021 Solution 08
Exercise 09 (Matchings and Randomization) 14.12.2021 21.12.2021 Solution 09
Exercise 10 (Randomization I) 21.12.2021 11.01.2022 Solution 10
Exercise 11 (Randomization II) 11.01.2022 18.01.2022 Solution 11
Exercise 12 (Approximation) 18.01.2022 25.01.2022 Solution 12
Exercise 13 (Online Algorithms) 25.01.2022 01.02.2022 Solution 13

Technical Information

Zoom and Zulip: All details for the weekly Zoom meeting are given on a seperate website. To join Zulip, click on the invitation link which is also given on this website.
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.

Daphne: The exercises are submitted via Daphne Daphne. Please use this link 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/ws2122/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 on the following Tuesday at 4 pm sharp!


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