Beschreibung

Die Vorlesung umfasst folgende Themengebiete aus dem Bereich der Algorithmen und Datenstrukturen:

und vieles mehr.

Vorkenntnisse

Programmierung 1 und 2 sowie Mathematik für Informatiker 1 und 2 (bzw. Analysis 1 und 2) sind hilfreich, aber keine unbedingte Voraussetzung. Zumindest paralleles Hören von Programmierung 1 und Mathematik für Informatiker 1 ist jedoch empfehlenswert.

Formalitäten

Arbeitsaufwand

Klausur

Um zur Klausur zugelassen zu werden, müssen Sie 50% der möglichen Punkte in den Übungsaufgaben erlangen. Die Aufgaben dürfen in Kleingruppen bis zu 3 Personen bearbeitet werden. Hier gilt jedoch, dass jede/r jede Aufgabe verstanden haben soll und diese im Zweifelsfall in der Übungsgruppe vorrechnen kann.

Benotung

Die Endnote ergibt sich ausschließlich aus den Klausurergebnissen: Die Beste der erlangten Klausurnoten wird zur Endnote. Sie können die Nachklausur also gefahrlos nutzen, um Ihre Note aufzubessern.

Achtung: Das Bestehen der Klausur kann nur dann als erfolgreiche Prüfungsleistung anerkannt werden, wenn Sie sich rechtzeitig über das LSF-Portal oder die entsprechenden Registrierungsportale für Studenten/innen anderer Fakultäten anmelden.

Terminplan

Datum Thema
19. Oktober Anmeldung zur Vorlesung und den Übungsgruppen; Einführung und Überblick; Binäre Suche
26. Oktober O-Notation, Laufzeitanalyse
02. November Sortieralgorithmen I
09. November Sortieralgorithmen II
16. November Selektion und Mediansuche in Linearzeit
23. November Master-Theorem; Strassen-Matrix-Multiplikation
30. November Stacks und Queues; amortisierte Analyse
07. Dezember Binäre Suchbäume
14. Dezember AVL-Bäume
21. Dezember Binomial-Heaps
04. Januar Breiten- und Tiefensuche
11. Januar Minimale Spannbäume; Greedy-Algorithmen
18. Januar Kürzeste Pfade; Dynamische Programmierung
25. Januar Weiterführende Themen I (Streamingalgorithmen)
01. Februar Weiterführende Themen II (Onlinealgorithmen)

Literatur