Materialien zur Vorlesung Entwurf und Analyse von Algorithmen

++Aktuell++ 1.3.2005: Die Übungsscheine sind ausgestellt und können bei Frau Beck in Raum D 219 abgeholt werden

Auf dieser Seite werden alle wichtigen Mitteilungen im Zusammenhang mit der Vorlesung Entwurf und Analyse von Algorithmen von Prof. Dr. Ulrik Brandes gesammelt.

Termine

Vorlesung: (U. Brandes) Mi 08:30 - 10:00 Uhr, D 406 Fr 08:30 - 10:00 Uhr, D 301 Übung: (C. Pich) Mo 12:15 - 14:00 Uhr, G 421 Mo 14:15 - 16:00 Uhr, G 421 Mündliche Prüfungen: Februar/März 2005 (Termine nach Vereinbarung)

Übungsblätter

Übungsblätter werden freitags in der Vorlesung ausgegeben, sind aber auch im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) erhältlich. Die Aufgaben sind innnerhalb einer Woche zu bearbeiten, und werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben. Die Besprechung der Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die aktive Teilnahme an den Übungen ist Voraussetzung für einen Übungsschein. Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.

	1. Übungsblatt (Ausgabe: 22.10.2004, Abgabe: 29.10.2004, 10 Uhr) Rekursionsabschätzungen (pdf, ps)
	2. Übungsblatt (Ausgabe: 29.10.2004, Abgabe: 4.11.2004, 16 Uhr) Amortisierte Analyse, Select (pdf, ps)
	3. Übungsblatt (Ausgabe: 5.11.2004, Abgabe: 11.11.2004, 16 Uhr) Union-Find (pdf, ps)
	4. Übungsblatt (Ausgabe: 12.11.2004, Abgabe: 18.11.2004, 16 Uhr) Automaten, Bäume (pdf, ps)
	5. Übungsblatt (Ausgabe: 19.11.2004, Abgabe: 25.11.2004, 16 Uhr) MST, Matchings (pdf, ps)
	6. Übungsblatt (Ausgabe: 26.11.2004, Abgabe: 2.12.2004, 16 Uhr) Minimale Schnitte (pdf, ps)
	7. Übungsblatt (Ausgabe: 3.12.2004, Abgabe: 9.12.2004, 16 Uhr) Maximale Flüsse I (pdf, ps)
	8. Übungsblatt (Ausgabe: 10.12.2004, Abgabe: 16.12.2004, 16 Uhr) Maximale Flüsse II (pdf, ps)
	9. Übungsblatt (Ausgabe: 17.12.2004, Abgabe: 23.12.2004, 14 Uhr) Maximale Flüsse III (pdf, ps)
	10. Übungsblatt (Ausgabe: 22.12.2004, Abgabe: 13.1.2005, 16 Uhr) Maximale Flüsse IV (pdf, ps)
	11. Übungsblatt (Ausgabe: 14.1.2005, Abgabe: 20.1.2005, 16 Uhr) Algorithmische Geometrie I (pdf, ps)
	12. Übungsblatt (Ausgabe: 21.1.2005, Abgabe: 27.1.2005, 16 Uhr) Algorithmische Geometrie II (pdf, ps)
	13. Übungsblatt (Ausgabe: 28.1.2005, Abgabe: 3.2.2005, 16 Uhr) Algorithmische Geometrie III (pdf, ps)
	14. Übungsblatt (Ausgabe: 4.2.2005, Abgabe: 10.2.2005, 16 Uhr) String-Matching (pdf, ps)

Skript

Zu der entsprechenden Vorlesung in den vergangenen Semestern wurde ein Skript (ps, pdf) erstellt. Zusätzlich steht ein Kapitel über maximale Flüsse (ps.gz, pdf) sowie Ergänzungen zur Highest-Label-Implementation des Algorithmus von Goldberg und Tarjan (pdf) zur Verfügung.

Weitere Informationen

	Informationen zum Account-Tool
	Semesterapparat in der Bibliothek
	Kurzskripte zu Grundlagen
	Definitionen zur O-Notation
	Prüfercodes
	Hao und Orlin: A Faster Algorithm for Finding a Minimum Cut in a Graph, SODA '91.
	Gomory und Hu: Multi-Terminal Network Flows, J. Soc. Indust. Appl. Math 9(4), 1961.
	Erich's Packing Center über Packprobleme
	Knuth-Morris-Pratt-Algorithmus, University of California, Irvine
	Einteilung in die Übungsgruppen (Stand: 25.10.2004, nur lokal lesbar)

An dieser Stelle werden weitere für die Vorlesung benötigte Informationen bereitgestellt.