Algorithm Theory
Graduate Course - Winter Term 2018/19
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 Informatik II. Basic algorithms and data structures knowledge, comparable to what is done in Informatik II, or , 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
The exam will take place on Thursday, 28th of March 2019, 10:00 am, in room 026, building 101.
The exam questions will only be given in English (it is OK to write the answers in German). Everyone is allowed to bring a summary consisting of at most 5 A4 pages (corresponds to 5 single-sided A4 sheets!) and a dictionary to the exam. No other material is allowed! Please remember to bring your student ID with you to the exam!
We published past exams for practice in a separate section below.
Schedule
Lecture
- Monday 14:15-16:00 Room: 101-00-026
- Thursday 10:15-12:00 biweekly! Room: 101-00-026
Tutorials
- English Tutorial (Johannes Kalmbach): Thursday 10:15-12:00 biweekly! Room: 101-00-026
- German Tutorial (Pascal Bachor): Thursday 16:15-18:00 biweekly! Room: 51-00-034
Exercise Material
Exercise sheet | Assigned | Due (14.15 pm) | Solution | |
Exercise 01 (O-Notation, Divide & Conquer) | 22.10.2018 | 05.11.2018 | Solution 01 | |
Exercise 02 (Divide & Conquer, Greedy Algorithms) | 05.11.2018 | 19.11.2018 | Solution 02 | |
Exercise 03 (Dyn. Programming, Amort. Analysis) | 19.11.2018 | 03.12.2018 | Solution 03 | |
Exercise 04 (Data Structures, Graph Algorithms) | 03.12.2018 | 17.12.2018 | Solution 04 | |
Exercise 05 (Matching, Probability Theory) | 17.12.2018 | 07.01.2019 | Solution 05 | |
Exercise 06 (Randomization) | 08.01.2019 | 21.01.2019 | Solution 06 | |
Exercise 07 (Randomization, Approx. Algorithms) | 21.01.2019 | 04.02.2019 | Solution 07 | |
Exercise 08 (Approx., Online, Parallel Algorithms) | 04.02.2019 | 18.02.2019 | Solution 08 |
Submission
You need to submit one solution per group (of at most two people). Submit your exercise solutions via one of the following options:
- Hand in as hard copy in lecture (before the deadline).
- Drop a hard copy into the Algorithm Theory [German/English] box in building 051.
- Send a digital version per mail to your tutor (click on the names below) with the subject 'AT_[SheeetNumber]'
With respect to digital submissions, we prefer solutions prepared with Latex, Word is ok, Scans must be well readable (no photos).
Grading
Your solutions will be graded by one of our tutors, Johannes Kalmbach (English tutorial) or Pascal Bachor (German tutorial). You can pick up your graded solutions during the next tutorial session.
Achieving 50% of the maximum achievable points on the exercise sheets is sufficient to be admitted to the exam.
Lecture Material
All slides and recordings can be found on our Webserver.
Partly, the slides are modifications of earlier versions of
Prof. Dr. T. Ottmann and Prof. Dr. S. Albers.
Forum
If you have a question to the lecture or the exercises, please use the forum instead of writing an email. Then all of us and also your colleagues see the question and can answer to it. Feel free to also use the forum to discuss anything related to the topics and organization of the lecture.
Past Exams
- Algorithm Theory Exam Fall 2018
- Algorithm Theory Exam Spring 2018
- Algorithm Theory Exam Spring 2017
- Algorithm Theory Exam Fall 2016
- Algorithm Theory Exam Spring 2016
- Algorithm Theory Exam Fall 2015
- Algorithm Theory Exam Spring 2015
- Algorithm Theory Exam Fall 2014
- Algorithm Theory Exam Spring 2014
- Algorithm Theory Exam Fall 2013
- Algorithm Theory Exam Spring 2013
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