Graduate Course
"Algorithms Theory"
Winter Term 2011/12
Alexander Souza
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 very basic problems and, more generally, investigate advanced design and analysis techniques. Central topics are some algorithms and data structures which have not at all or not sufficiently extensive been discussed in the undergraduate course Informatik II. These include, but are not limited to:
- Divide and conquer: geometrical divide and conquer, fast Fourier transformation
- Randomization: randomized quicksort, probabilistic primality testing, RSA, univeral and perfect hashing
- Amortized analysis: binomial queues, Fibonacci heaps, union-find data structures
- Greedy procedures: shortest path, minimum spanning trees, bin packing problem, scheduling
- Graph algorithms
- Dynamic programming: matrix chain product problem, edit distance, longest common subsequence problem
- String matching and text compression: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm, suffix trees, Huffman coding, Lempel-Ziv-Welch data compression algorithm
The knowledge of algorithms and data structures described in chapters 1 to 6 of the book "Algorithmen und Datenstrukturen" by Thomas Ottmann and Peter Widmayer is a prerequisite for understanding the topics of this course.
Lectures
- Tuesday 16-18 c.t.: 101-00-026
- Wednesday 16-17 c.t.: 101-00-026
Course Evaluation
- Evaluation Forms: German, English.
- Please eMail your filled form to the Studienberatung
Slides / Recordings
-
All slides and recordings can be found on our webserver.
The slides are modifications of earlier versions of Prof. Dr. Ottmann and Prof. Dr. Albers.
Exercise courses
The exercise courses are supervised by Thomas Janson.
They take place every two weeks.
| Day | Time | Room | Teaching Assistant | Language |
| Thursday | 8-10 | 101-01-018 | Ahmed Mahdi | english |
| Thursday | 8-10 | 051-00-034 | Florian Geißer | german |
| Friday | 12-14 | 101-00-018 | Julian Jarecki | german |
(Here is a list of the tutorial groups (Update November 16). The password is the last name of the lecturer)
Schedule
Exercise sheets
| Sheet | Publication | Submission | Discussion |
| Assignment 1 | October 26 | November 2 | November 10/11 |
| Assignment 2 | November 9 | November 16 | November 24/25 |
| Assignment 3 | November 23 | November 30 | December 8/9 |
| Assignment 4 | December 7 | December 14 | December 22/23 |
| Assignment 5 | December 21 | January 11 | January 19/20 |
| Assignment 6 | January 18 | January 25 | February 2/3 |
| Assignment 7 | February 1 | February 8 | February 16/17 |
Final exam
- Credit points: 6
- Date final exam: 27.02.2012 at 9:00-10:30 in room 101-00-026 and 101-00-036.
- Eligibility: at least 50% of the points in the exercises, one black board presentation.
- Registration: Via the web-page of the "Vorlesungsverzeichnis" until 11.2.2012.
- Announcement in the Lecture of 21.12.2011: video, pdf, pdf 4up, pdf with annotations
- Permitted resources: one on both sides handwritten DIN A4 page and a non-programmable calculator.
Literature
- 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
- lecture of last year: Matthias Westermann: Graduate Course "Algorithm Theory", Winter Term 2010/11