Dr. Martin Kutz | Building 46 (MPII), Room 319, office hours: Tue. 3-5pm | |
Dr. Ulrich Meyer | Building 46 (MPII), Room 325, office hours: whenever available |
Lectures: | Mondays and Wednesdays, 11-13 h, Room 003, Building 45 |
First lecture: |
Monday, October 17, 2005 |
Tutorials: |
Tutorials started on Monday, October 31. Groups (register for tutorials) |
Final Exam: | Wednesday, 22 of February 2006 / 14-18 / HS001-002 (admitted students txt) | results | |
Re-exam: | Tuesday, 4 of April 2006 / 14-18 / HS002 | results |
The inspection of the re-exam is on Tuesday, April 11, from 10 to 11 am in room 024 (MPI ground floor).
Dates | Topic | Reference |
Oct 17,19 | BFS, DFS, SCC, topological ordering | CLR, Ch. 23 (CLRS, Ch. 22) |
Oct 23, 25 | Dijkstra's shortest-paths algortihm | KT 4.4 (PS: Dijkstra) |
Oct 25 | Prim's MST algorithm, priority queues | KT 4.5, 2.5 (PS: Prim) |
Oct 31 | Kruskal's MST algorithm, union-find | KT 4.5, 4.6 (PS: Kruskal) |
Nov 2 | interval scheduling: greedy algorithm and dynamic programming | KT 4.1, 6.1, 6.2 (ps pdf) |
Nov 7 | retrieving solutions from DP tables (ps pdf), Subset-Sum (ps pdf) | KT 6.2, 6.4 |
Nov 9 | Sequence alignment; longest common subsequences | KT 6.6, 6.7 |
Nov 14 | various recurrences (e.g., space-efficient sequence alignment [ps] [pdf]) | KT 5.1, 5.2 |
Nov 16 | more recurrences; Strassen's fast matrix multiplication | CLR 31.2 |
Nov 21 | network flow | KT 7.1, 7.2 |
Nov 23 | characterizations of maximum flows and min-cost circulations; scaling | KT 7.3, (7.13) |
Nov 28 | paradigms of randomized algorithms; elementary probablity theory | MR Preface, KT 13 |
Nov 30 | elementary probablity theory; randomized contention resolution | KT 13.1 |
Dec 2,5 | randomized and deterministic selection | KT 13.5, CLR 10.2 |
Dec 7 | quicksort | KT 13.5, CLR 8.4 |
Dec 12,14 | basics of hashing, hashing with chaining | KT 13.6 |
Dec 19 | Prefix Minima and Applications (Closest Pairs, Shortest Paths) | KT 13.7, Goldberg/Tarjan Technical Report 96-062 |
Dec 21 | SSSP with linear average-case time, repetition | slides |
Jan 9 | computational geometry, first convex hull algorithm | M^{4}, ps pdf |
Jan 11 | a better convex-hull algorithm; closest pairs | M^{4} 1.1; CLR 35.3, 35.4; KT 5.4; ps pdf |
Jan 16 | line-segment intersection; sweep line | M^{4} 2.1; ps pdf |
Jan 18 | Voronoi diagrams | M^{4} 7.1 |
Jan 23 | Voronoi-diagram computation | M^{4} 7.2 |
Jan 25 | ... continued | M^{4} 7.2 |
Jan 30 | Intro to Approximation Algs. | KT 11.1 |
Feb 1 | SLS Scheduling | KT 11.1, Script by R. Motwani |
Feb 6 | Approximation Schemes | Script by R. Motwani |
Feb 8 | k-Centers | KT 11.2 |
Feb 13 | Traveling salesman tours | CLR 37.2 |
Feb 15 | Set Cover | KT 11.3 |
If you have questions about the exercises or tutorials
you can either send them to the mailing list or to dsteurer AT mpi-sb.mpg.de.
Please make sure that you do not publish any hints or solutions to exercises
on the mailing list.
Exercises can be done in groups of one or two.
You can hand in your solutions to the exercises either during the Wednesday lecture or throw them into the course mail box on the ground floor of
the computer-science building by Wednesday 1 pm.
1st Assignment | due Wed, Nov. 2 | ps pdf |
2nd Assignment | due Wed, Nov. 9 | ps pdf |
3rd Assignment | due Wed, Nov. 16 | ps pdf |
4th Assignment | due Wed, Nov. 23 | ps pdf |
5th Assignment | due Wed, Nov. 30 | ps pdf |
6th Assignment | due Wed, Dec. 7 | ps pdf |
7th Assignment | due Wed, Dec. 14 | ps pdf |
8th Assignment | ungraded | ps pdf |
9th Assignment | due Wed, Jan. 18 | ps pdf |
10th Assignment | due Wed, Jan. 25 | ps pdf |
11th Assignment | due Wed, Feb. 1 | ps pdf |
12th Assignment | due Wed, Feb. 8 | ps pdf |
You can register for the course on this page.
You can withdraw from the lecture by sending an appropriate mail to
da05@mpi-sb.mpg.de
You can check whether you are already registered: list of subscribed students (last update 31.10.05)
Independent from registering, you can join the mailinglist of the lecture
on that page.
J. Kleinberg, E.Tardos. Algorithm Design. Addison Wesley Longman, 2006. (KT) |
K. Mehlhorn. Data Structures and Efficient Algorithms, Vol. 1-3. Springer Verlag, EATCS Monographs, 1984. |
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry, 2nd Edition, Springer Verlag, 2000. (M^{4}) |
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press 1990. (CLR) |
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, 2nd Edition. MIT Press 2001. (CLRS) |
K. Mehlhorn and S. Naeher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. |
R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (MR) |
R. K. Ahuja, R. L. Magnanti, and J. B. Orlin. Network Flows. Prentice Hall 1993. |
R. E. Tarjan. Data Structures and Network Algorithms. SIAM 1983. |
A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency. Springer 2003 |
Joseph Jaja. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. |