Dienstag 08:00 - 10:00
Hörsaal H VI (Jügelhaus/Hörsaalgebäude)
Sprechstunde: Nach Vereinbarung
Freitag 10:00 - 12:00
Magnus Hörsaal (Robert-Mayer-Str. 11-15)
Sprechstunde: Nach Vereinbarung
E-Mail: ds18@ae.cs.uni-frankfurt.de
Sprechstunde: Nach Vereinbarung
Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).
Der Übungsbetrieb ist im zweiwöchentlichen Rhythmus organisiert. Die Abgabe des Blattes erfolgt normalerweise zwei Wochen später vor Beginn der Vorlesung. Für eine frühere Abgabe benutzen Sie bitte den großen Briefkasten neben Raum 312 (Robert-Mayer-Str. 11-15). Der Briefkasten wird am Tag der Abgabe um 8:00 geleert.
Sie können durch Teilnahme an den Übungen bis zu 10 Bonuspunkte, durch die Teilname an der zusätzlichen Programmierveranstaltung bis zu 3 Bonuspunkte erlangen, in Summe jedoch nicht mehr als 10.
| Gruppe 1 | Mo | 12 - 14 | NM 113 | Andreas Scholl | (ungerade Kalenderwochen) |
| Gruppe 2 | Mo | 12 - 14 | NM 113 | Andreas Scholl | (gerade Kalenderwochen) |
| Gruppe 3 | Mo | 14 - 16 | NM 102 | Anh Duong Vo | (ungerade Kalenderwochen) |
| Gruppe 4 | Mo | 14 - 16 | NM 102 | Anh Duong Vo | (gerade Kalenderwochen) |
| Gruppe 5 | Mo | 16 - 18 | NM 102 | Adrian Kretz | (ungerade Kalenderwochen) |
| Gruppe 6 | Mo | 16 - 18 | NM 102 | Adrian Kretz | (gerade Kalenderwochen) |
| Gruppe 7 | Di | 12 - 14 | H 9 | Jaro Eichler | (ungerade Kalenderwochen) |
| Gruppe 8 | Di | 12 - 14 | H 9 | Jaro Eichler | (gerade Kalenderwochen) |
| Gruppe 9 | Di | 14 - 16 | NM 102 | Marco Schmalhofer | (ungerade Kalenderwochen) |
| Gruppe 10 | Di | 14 - 16 | NM 102 | Marco Schmalhofer | (gerade Kalenderwochen) |
| Gruppe 11 | Mi | 12 - 14 | H 9 | Lukas Maurer | (ungerade Kalenderwochen) |
| Gruppe 12 | Mi | 12 - 14 | H 9 | Lukas Maurer | (gerade Kalenderwochen) |
| Gruppe 13 | Do | 12 - 14 | H 9 | Vincent Kühn | (ungerade Kalenderwochen) |
| Gruppe 14 | Do | 12 - 14 | H 9 | Vincent Kühn | (gerade Kalenderwochen) |
| Gruppe 15 | Do | 12 - 14 | NM 102 | Ehud Cseresnyès | (ungerade Kalenderwochen) |
| Gruppe 16 | Do | 12 - 14 | NM 102 | Ehud Cseresnyès | (gerade Kalenderwochen) |
| Gruppe 17 | Do | 14 - 16 | NM 102 | Stephan Gardoll | (ungerade Kalenderwochen) |
| Gruppe 18 | Do | 14 - 16 | NM 102 | Stephan Gardoll | (gerade Kalenderwochen) |
Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Datenstrukturen. Die Analyse von Datenstrukturen im Hinblick auf Laufzeit und Speicherplatzbedarf wird motiviert. Die asymptotische Notation wird eingeführt, und Methoden zur Lösung von Rekursionsgleichungen werden besprochen.
Elementare Datenstrukturen wie Listen, Keller und Warteschlangen werden beschrieben und analysiert. Weiter werden die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen diskutiert.
Der Begriff des abstrakten Datentyps wird eingeführt und motiviert, und effiziente Realisierungen der Datentypen des Wörterbuchs und der Prioritätswarteschlange unter Benutzung von Bäumen (beispielsweise AVL-, Splay-Bäume und B-Bäume) und Hashing (auch verteiltes Hashing und Bloom-Filter) werden besprochen. Außerdem werden effiziente Datenstrukturen für das Union-Find-Problem behandelt.
Die Kenntnis fundamentaler Datentypen sowie die Fähigkeit, den Prozess des Entwurfs und der Analyse von Datenstrukturen eigenständig durchführen zu können.
Hauptklausur: 03.08.2018 9:00 s.t.
Nachklausur: 11.10.2018 9:00 s.t.
Weitere Informationen werden zu rechtzeitig bekannt gegeben.
Die Videoaufzeichnungen der Vorlesung stehen hier zur Verfügung.
Altklausuren finden Sie hier.
Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.
Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.
Betrugsversuche bzw. Plagiate führen beim erstmaligen Verstoß dazu, dass bei allen Beteiligten die Bonuspunkte des gesamten Übungsblattes verfallen („gelbe Karte“). Beim zweiten Verstoß werden keinerlei Bonuspunkte für die Klausur angerechnet („rote Karte“) und der Vorfall wird dem Prüfungsamt angezeigt. Bitte beachten Sie, dass auch das Ermöglichen von Plagiaten („abschreiben lassen“) einen Betrugsversuch darstellt und geahndet wird.
Es steht das Skript von Herrn Prof. Dr. G. Schnitger zum download bereit, an dem sich diese Veranstaltung orientiert.