Algorithm Theory
Graduate Course - Winter Term 2015/16
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, etc.
- Amortized analysis: binomial queues, Fibonacci heaps, union-find data structures
- Greedy algorithms: minimum spanning trees, bin packing problem, scheduling
- Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
- Graph algorithms: network flows, combinatorial optimization problems on graphs
Exam
Post-Exam Review: Friday, September 23, 2016, 14:00-15:00 in room 106-00-004.
The exam questions will be in English. Everyone is allowed to bring 5
handwritten A4 pages (corresponds to 5 single-sided A4 sheets!), a
pocket calculator, and a dictionary to the exam. No other material
is allowed!
To get a feeling for the type of questions, here
are the last exams:
- 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
- Algorithm Theory Exam Fall 2012
Note however that the set of topics of the 2011/12 lecture on which the fall 2012 exam was based was not the same as this time.
Schedule
Lectures
- Monday 14:15-15:00 : 101-00-026
- Thursday 10:15-11:45 : 101-00-026
Exercises
Responsible for the exercises are
Mohamad Ahmadi and Oleksii Saukh.
Exercise tutorials will (usually) be weekly on
Mondays from 15:15-16:00. Any changes to the this schedule will be announced here.
- Group A (German Tutorial): Monday 15:15-16:00, 101-00-026
Tutor: Gabriel Kalweit (gabrielkalweit@gmail.com)
The suggested assignment of students can be found here: German Group - Group B (English Tutorial): Monday 15:15-16:00, 82-00-006 (Kinohörsaal)
Tutor: Hamid Ghodselahi(hghods@cs.uni-freiburg.de) and Yannic Maus
The suggested assignment of students can be found here: English Group - 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.
- 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
Sign up for Exercises
Exercise tutorials will take place weekly on Monday afternoon 15:15-16:00. In the tutorials the solutions of the previous week are discussed. In order to be admitted to the exam, you need to have 50% of all exercise points. Exercises could be done in groups of 2 students. Please send an email (including name and matriculation number of both students) to Hamid Ghodselahi (hghods@cs.uni-freiburg.de) to sign up for the exercises. Please sign up for the exercises by Thursday evening, Oct 22. We might be able to offer German exercise tutorials (there will definitely be English tutorials). In case you'd prefer to have the exercise tutorials in German, please also indicate this in your email when signing up.
Timeline
The new exercise sheet will be released on this website on Wednesdays; your solution is supposed to be handed in until Thursday, 10:00 a.m., in the week following its release date. You can hand it in either before the lecture or in the respective letter box (Algorithm Theory WS 15/16 Group A (German) or B (English)) in building 051, first floor. You could also send it by E-mail to your tutor. Your tutor will return the corrected exercise sheet in the tutorial session on the Monday after your submission.
Exercise Material
Lecture Material
Slides / Recordings