Graduate Course
"Algorithms Theory"
Winter Term 2010/11
Matthias Westermann
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: HS 00-026, 101
- Wednesday 16-18: HS 00-026, 101
Exercise courses
The exercise courses are supervised by Marco Muñiz.
They take place every two weeks and start on 08.11.2010.
| Day | Time | Room | Teaching Assistant | Language |
| Tuesday | 12-14 | 051-00-034 | Ahmed Mahdi | English |
| Wednesday | 12-14 | 051-00-031 | Julian Jarecki | German |
| Thursday | 12-14 | 101-00-010/014 | Ahmed Mahdi | English |
| Thursday | 12-14 | 101-01-009/013 | Florian Geißer | German |
| Thursday | 14-16 | 051-00-031 | Florian Geißer | German |
| Friday | 12-14 | 051-00-006 | Julian Jarecki | German |
Exercise sheets
- Assignment 1, hand in by 03.11.2010 before the lecture
- Assignment 2, hand in by 17.11.2010 before the lecture
- Assignment 3, hand in by 01.12.2010 before the lecture
- Assignment 4, hand in by 15.12.2010 before the lecture
- Assignment 5, hand in by 12.01.2011 before the lecture
- Assignment 6, hand in by 26.01.2011 before the lecture
The solutions can be submitted in English or German and in groups up to two students. Please write down your name, your matriculation number, and the name of your tutor at the head of each sheet. Drop it into the box in building 051 ground floor which is labeled with the name of your tutor. You can hand in your solution by mail, too. Please ask your tutor for his mail address.
Final exam
- Credit points: 6
- Date final exam: 09.03.2011 at 10:15-11:45 in room 101-00-026 and 101-00-036.
- Date exam inspection: 10.03.2011 at 12:30-14:00 in room 051-02-026.
- Eligibility: at least 50% of the points in the exercises.
- Permitted resources: one on both sides handwritten DIN A4 page and a non-programmable calculator.
Slides
- Introduction
- Geometric Divide and Conquer
- Fast Fourier Transformation
- Randomisation
- Hashing
- Amortized Analysis
- Binomial Heaps
- Fibonacci Heaps
- Union-Find Data Structures
- Greedy Algorithms
- Shortest Paths
- Minimum Spanning Trees
- Bin Packing
- Dynamic Programming: Introduction
- Dynamic Programming: Matrix Chains
- Dynamic Programming: Optimal Search Trees
- Dynamic Programming: Edit Distance
- String Matching
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