Lecture ``Algorithms & Data Structures'' - WS 2005/06

Lecturers

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

Time and Place

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)

Exams

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).

Session Topics

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 M4, ps pdf
Jan 11 a better convex-hull algorithm; closest pairs M4 1.1; CLR 35.3, 35.4; KT 5.4; ps pdf
Jan 16 line-segment intersection; sweep line M4 2.1; ps pdf
Jan 18 Voronoi diagrams M4 7.1
Jan 23 Voronoi-diagram computation M4 7.2
Jan 25 ... continued M4 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

Assignments

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
Here are sample solutions to some of the exercises:   [ps] [pdf]
and these are soutions to the recurrences from sheet 4: [ps] [pdf]

Subscription & Mailing List

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.

References

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. (M4)
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.