MA-INF 1104 Advanced Algorithms

Dates

Subject When Where Start Lecturer
LectureMonday 12:30-14:00 and Wednesday 12:30-14:00 LBH III.03 October 21st 2015 Kratsch
Tutorial 1Monday 10:30-12:00 LBH E.23 October 26th 2015 Hols
Tutorial 2Monday 14:30-16:00 LBH III.03 October 26th 2015 Hols

Organization

In addition to signing up via basis please send an email to kratsch@cs.uni-bonn.de to provide your email address (using „[Advanced Algorithms]“ as the subject). You will receive occasional notifications, (updates to) the lecture notes, and the exercise sheets via email. Note that sending an email is not equivalent to signing up and comes with no obligations.

Exam

There will be a written exam at the end of the term. There are no requirements for admittance and the final grade is determined solely by the exam.

Exercise/Tutorial meetings

In the tutorials you will be given time and support to solve exercises in teams of two. Eva-Maria Hols will be present in both tutorials and answer your questions or give hints. There will be essentially no presentation of solved exercises since the focus is on solving things yourself. In particular, being able to explain a solution to your neighbor is highly beneficial, and being told that „this is actually quite easy“ is much more believable coming from your neighbor. We also found that (unsurprisingly?) students are much more apt at understanding one anothers problems with a task.

Exercise sets will focus on the current chapter in the lecture and you may have more than one meeting to work one the same set. Working at home is of course encouraged too. We will not grade or proof-read your solutions, but you can verify your ideas by asking Eva-Maria during the tutorial.

Prerequisites

There are no prerequisites other than having completed a Bachelor (typically in mathematics or computer science) or being close to doing so. Standard Bachelor lectures about algorithm design/analysis, discrete structures, logic, complexity are nevertheless beneficial. Being fluent with graphs, matrix-vector calculations, and Big-O notation is highly recommended.

If you do not have your Bachelor yet then you need contact the examination office to sign up for the lecture. You can still only use the grade for this course towards your Master degree.

Lecture notes

Lecture notes will be made available by email, likely on the second week of the term. Depending on progress, additional content may be added. The lecture notes have greatly benefitted from the books mentioned below but also from lecture notes of similar lectures at other universities. The lecturer takes credit only for errors and typos that can be found (and polite pointers by email are appreciated).

Topics

  1. Network flows
  2. Linear programming
  3. Approximation algorithms
  4. Randomized algorithms
  5. Exact exponential-time algorithms

This is a new lecture and content may be added or (unlikely) removed. Furthermore, the last 1-2 weeks will likely be used for some special topic that will not be covered by the exam.

Books

The following books are recommended and the relevant topics are stated next to them. Some of the books also cover the material of other chapters and is fine to use them for that as well. The first three books all largely cover the first half of the lecture and it is recommended getting one of them if you had no prior exposure to these topics. The part on randomized algorithms follows different materials but we will suggest a book anyway.

  1. Jon M. Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley, 2006. [network flow]
  2. Bernhard Korte and Jens Vygen. Combinatorial Optimization. Springer, 2012. [network flow]
  3. Norbert Blum. Algorithmen und Datenstrukturen. Oldenbourg Verlag, 2013. [linear programming]
  4. Vijay V. Vazirani. Approximation Algorithms. Springer, 2001. [approximation algorithms]
  5. [randomized algorithms]
  6. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. [exact exponential-time algorithms]

All of the books make good complementary reading and each offers much more material than we could hope to cover in the lecture. Students interested in one of the topics should use the opportunity to do some additional reading into the relevant book(s). Further material can be suggested if desired.

lehre/ws1516/advanced_algorithms.txt · Zuletzt geändert: 2015/11/10 15:17 von kratsch

Benutzer-Werkzeuge