Proseminar
"Datenstrukturen und Effiziente Algorithmen"
Sommersemester 2004
Prof. Dr. Susanne Albers und Markus Schmidt
Vergabe der Themen erfolgt bis zum 21. April 2004 bei Markus Schmidt, GB 79 Zimmer 006.
Anmeldung zum Proseminar: Auf den Internetseiten des Prüfungsamtes kann ein Anmeldeformular zum Proseminar ausgedruckt werden, das ausgefüllt bis zum 30.07.2004 beim Prüfungsamt abzugeben ist. Ort und Zeit: Mi 9-11, SR 00-034 GB 051
Dieses Proseminar richtet sich an Bachelor-Studierende des zweiten Semesters.
Es werden Kenntnisse über Datenstrukturen und Effiziente Algorithmen,
die in den Veranstaltungen Informatik I und Informatik II vermittelt werden,
vertieft und erweitert. Das Seminar ist eher theoretisch orientiert, d.h.
die untersuchten Datenstrukturen und Algorithmen werden auch hinsichtlich
ihrer Güte (mathematisch) analysiert. Die Teilnehmer lesen im Proseminar
selbstständig fachliches Material und stellen es in einem Vortrag
von ca. 45 Minuten den anderen Studierenden vor. Zusätzlich ist bis
zum Ende der Vorlesungszeit dieses Semesters eine schriftliche Ausarbeitung
von 5-10 Seiten anzufertigen.
Literatur
- T.H. Cormen, C.E. Leiserson und R.L. Rivest. Introduction to Algorithms. MIT Press 1990.
- R.E. Tarjan. Data Structures and Network Algorithms. SIAM 1983.
Themen
| Nr. | Titel | VortragendeR | Termin |
| 1 | Quicksort | Gunnar Ritter | 28.04.2004 |
| 2 | Sorting in linear time | Vito Di Leo Grammelspacher | 05.05.2004 |
| 3 | Hashing | Markus Grützner | 05.05.2004 |
| 4 | Disjoint sets | Marius Heinzmann | 12.05.2004 |
| 5 | Heaps | Mirko Herbstritt | 19.05.2004 |
| 6 | Search trees | Michael Schröder | 19.05.2004 |
| 7 | Linking and cutting trees | Holger Neub | 26.05.2004 |
| 8 | Fast Fourier transformation | Jens Keller | 09.06.2004 |
| 9 | Minimum spanning trees | Tobias Langner | 23.06.2004 |
| 10 | Shortest paths | Fabian Kiss | 30.06.2004 |
| 11 | Network flows | Nikolay Eliseev | 07.07.2004 |
| 12 | Matching | Lucien Laurien | 07.07.2004 |
| 13 | Computational geometry | Christoph Birkenbihl | 14.07.2004 |
| 14 | Approximation algorithms | Jens Heidrich | 14.07.2004 |
| 15 | String matching | Christoph Hanke | 21.07.2004 |
| 16 | RSA cryptosystem | Anne Repky | 21.07.2004 |