Algorithm Theory
Graduate Course - Winter Term 2014/15
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: Thursday, October 1, 106-00-015, --> 14:00-16:00
Exam date: August 25 (Tuesday), 2015, 09:00-10:30.
Exam place: 101-01-009/13.
The exam questions will be in English and German. It will be ok to
answer the questions in German. 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 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
Schedule
Lectures
Thursday, Feb. 12: No lecture, question and answer session, discussion of last exercise sheet- Monday 14:15-15:00: 101-00-026
- Thursday 10:15-11:45: 101-00-026
Exercises
Responsible for the exercises are Hamid Ghodselahi and Yannic Maus. 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: Betim Musa (musab@informatik.uni-freiburg.de) - Group B (English Tutorial): Monday 15:15-16:00, 106-00-007
Tutor: Mohamad Ahmadi (mohamad.ahm@gmail.com)
Sign up for Exercises
Exercise tutorials will take place weekly on Monday afternoon 14:15-15:00. In the tutorials the solutions of the previous week are discussed. It is mandatory to hand in hard copied exercise solutions. In order to be admitted to the exam, you need to have 50% of all exercise points. Exercises should be done in groups of 2 students. Please team up with a colleague and 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 23. 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 (hard copied) 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 14/15 Group A (German) or B (English)) in building 051, first floor. Your tutor will return the corrected exercise sheet in the tutorial session on the Monday after your submission.Exercise Material
Problem Set | Assigned | Due (10:00 a.m) | Solution / Additional Material | |
Exercise 01 (Divide and Conquer) | 22.10.2014 | 30.10.2014 | - | |
Exercise 02 (FFT and DFT) | 29.10.2014 | 6.11.2014 | - | |
Exercise 03 (Greedy TSP and Matroids) | 05.11.2014 | 13.11.2014 | - | |
Exercise 04 (Dynamic Programming) | 12.11.2014 | 20.11.2014 | - | |
Exercise 05 (Edit Distance & Binomial Heap) | 19.11.2014 | 27.11.2014 | No Sample Solution | |
Exercise 06 (Fibonacci Heap & Amortized Analysis) | 26.11.2014 | 4.12.2014 | - | |
Exercise 07 (Union-Find) (updated 8.12.2014) | 03.12.2014 | 11.12.2014 | - | |
Exercise 08 (Amortized Analysis, Ford-Fulkerson) | 10.12.2014 | 18.12.2014 | - | |
Exercise 09 (Network Flows) | 17.12.2014 | 08.01.2015 | - | |
Exercise 10 (Matching & Probability Theory) | 07.01.2015 | 15.01.2015 | - | |
Exercise 11 (Primality Testing, Randomized Min-Cut) | 14.01.2015 | 22.01.2015 | - | |
Exercise 12 (Randomized Min-Cut, Approx. Alg.) | 21.01.2015 | 29.01.2015 | - | |
Exercise 13 (Approximation Algorithms) | 29.01.2015 | 05.02.2015 | - | |
Exercise 14 (Online & Parallel Algorithms) | 05.02.2015 | 12.02.2015 | - |
Lecture Material
Slides / Recordings
- 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.
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