Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 Mün;chen

Übungen zur Vorlesung
Effiziente Algorithmen und Datenstrukturen

Hinweise zum Übungsbetrieb:

	Leitung: Ingo Rohloff
	Zeit und Ort: Di 13:30 - 15:00, Hörsaal N1080
	Abgabe: In der Übung
	Leistungsnachweis: Einen Schein erhält, wer mindestens 40% der Punkte zu den Kontrollblättern erreicht und erfolgreich an der Semestralklausur teilnimmt.
	Hinweise zur Semestralklausur
	Die Klausur ist fertig korrigiert und die Scheine können in S2240 abgeholt werden.

Informationsblätter

	Folien zu Splay Trees ( gzipped )
	Folien zu Fibonacci Heaps ( gzipped )
	Folien zu Buckets ( gzipped )
	Folien zu Radix Heaps ( gzipped )
	Folien zu PriorityQueues (Zusammenfassung) ( gzipped )
	Folien zu Union/Find ( gzipped )
	Folien zu QuickSort ( gzipped )
	Folien zu RadixSort ( gzipped )
	Folien zu Selektions-Algorithmen ( gzipped )
	Folien zu Kürzestem-Wege Problem ( gzipped )
	Folien zu Topologischer Sortierung ( gzipped )
	Folien zu Artikulationsknoten und Blöcken ( gzipped )
	Folien zu Matrizenmulitplikation nach Strassen ( gzipped )
	Folien zu String Matching ( gzipped )
	Eine Zusammenfassung über Stringmatching im Web
	Folien zu Suffix Trees ( gzipped )
	Folien zu schneller Polynommultiplikation ( gzipped )
	Folien zu Approximationsalgorithmen ( gzipped )
	Rückblick und Zusammenfassung der Vorlesung ( gzipped )

Übungsblätter und Lösungsvorschläge

	Übungsblatt 1	-- Lösungsvorschlag 1 ( gzipped )
	Übungsblatt 2	-- Lösungsvorschlag 2 ( gzipped )
	Übungsblatt 3	-- Lösungsvorschlag 3 ( gzipped )
	Übungsblatt 4	-- Lösungsvorschlag 4 ( gzipped )
	Übungsblatt 5	-- Lösungsvorschlag 5 ( gzipped )
	Übungsblatt 6	-- Lösungsvorschlag 6 ( gzipped )
	Übungsblatt 7	-- Lösungsvorschlag 7 ( gzipped )
	Übungsblatt 8	-- Lösungsvorschlag 8 ( gzipped )
	Übungsblatt 9	-- Lösungsvorschlag 9 ( gzipped )
	Übungsblatt 10	-- Lösungsvorschlag 10 ( gzipped )
	Übungsblatt 11	-- Lösungsvorschlag 11 ( gzipped )
	Semestralklausur mit L"osungen	( gzipped )

Sonstiges

	Eine kleine Anleitung wie man C++ Programme in der SUN-Halle übersetzt.
	Einige Hinweise zur Bearbeitung der Kontrollblätter: Es dürfen maximal 2 Personen zusammen abgeben. Abgeben kann man in der Vorlesung, in der Übung oder bei mir direkt. Bitte immer Namen und Matrikelnummern angeben. Programmieraufgaben per E-Mail an rohloff@in.tum.de. Bitte wieder Namen und Matrikelnummern angeben. Den eigentlichen Programm-Source-Code als Attachment anhängen (Entweder mit ZIP oder TAR/GZIP gepackt oder jede Datei als eigenes Attachement.)
	Folien für den Algorithmus von Dijkstra und den Algorithmus von Prim.
	Der Testgraph auf Übungsblatt 4 als Datei : graph 1 Antwort sollte 89 sein.
	Ein zweiter größerer Testgraph : graph 2 Antwort sollte 200147900 sein.
	Ein dritter (noch grösserer, ca 3.8MegaByte download) Testgraph : graph 3 Antwort sollte 202468113 sein.
	Sie können davon ausgehen, dass für alle Werte X die in die Priority Queue eingetragen werden gilt: X < 230.
	Einige Beispielimplementierungen des Algorithmus von Dijkstra.
	Noch eine Beispielimplementierung des Algorithmus von Dijkstra in Java.
	Sie können bei der Eingabe für den Forward-Radix Sort mit Gruppen davon ausgehen, dass die Strings nicht mehr als 70 Zeichen enthalten und das keine zwei Strings gleich sind.
	Eine Testeingabe zum sortieren. (sortiert)
	Eine einfache Beispielimplementierung für Forward-Radix-Sort mit Gruppen. Ein Ablaufprotokoll um zu sehen, wie der Algorithmus funktioniert.
	Eine optimierte Beispielimplementierung für Forward-Radix-Sort mit Gruppen.