Algorithm Theory
Graduate Course - Winter Term 2016/17
Fabian Kuhn
Exam Spring 2017
The exam will take place on Wednesday, September 6, 09:00-11:00 in building 101, room 010/014.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
Exam date: 28.03.2017, 9:00-11:00
Exam place: Building 101, Room 026
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 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
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.
Schedule
Lectures
- Monday 14:15-16:00 : 101-00-026
- Thursday 10:15-12:00 : 101-00-026
Exercises
Responsible for the exercises are Mohamad Ahmadi and Philipp Bamberger.
Exercise classes take place (roughly) every second week (usually) on Mondays (tentative).
- Group A (German Tutorial): Monday 14:15-16:00, 101-00-026
Tutor: Philipp Bamberger (Philipp.Bamberger@cs.uni-freiburg.de)
- Group B (English Tutorial): Monday 14:15-16:00, 51-00-006
Tutor: Mohamad Ahmadi (mahmadi@cs.uni-freiburg.de)
- 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 on Mondays afternoon 14:15-16:00 (roughly) every second week. In the tutorials the solutions that have been handed in 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 Mohamad Ahmadi (mahmadi@cs.uni-freiburg.de) to sign up for the exercises. Please sign up for the exercises by Thursday evening, Oct. 20. Please indicate in your email when signing up whether you prefer an English or a German tutorial group.
Timeline
The new exercise sheet will be released on this website on Thursdays every second week; your solution is supposed to be handed in until Thursday, 10:00 a.m., in the week in which the solution is due. You can hand it in either before the lecture or in the respective letter box (Algorithm Theory WS 16/17 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 next tutorial session when the corresponding solutions are discussed.
Exercise Material
Problem Set | Assigned | Due (10:15) | Solution / Additional Material | |
Problem Set 1 (Landau-Notation - Divide & Conquer) | 20.10.2016 | 27.10.2016 | Sample Solution | |
Problem Set 2 (Divide & Conquer - FFT - Greedy) | 27.10.2016 | 10.11.2016 | Sample Solution | |
Problem Set 3 (D&C - Greedy - Dynamic Programming) | 10.11.2016 | 24.11.2016 | Sample Solution | |
Problem Set 4 (Amortized Analysis, Data Structures) | 24.11.2016 | 08.12.2016 | Sample Solution | |
Problem Set 5 (Network Flow) | 08.12.2016 | 22.12.2016 | Sample Solution | |
Problem Set 6 (Matching, Probability Theory) | 22.12.2016 | 19.01.2017 | Sample Solution | |
Problem Set 7 (Randomized Algorithms) | 19.01.2017 | 30.01.2017 | Sample Solution | |
Problem Set 8 (Approximation and Online Algorithms) | 30.01.2017 | 06.02.2017 | Sample Solution |
Lecture Material
Slides / Recordings