News

Die Anmeldung (bis Sonntag 18:00) und alle weitere Kommunikation findet im CMS statt: https://cc-lecture.cs.uni-saarland.de/gralgodat1718/

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

Plenarübung

Zusätzlich zu den Übungsgruppen und der Vorlesung bieten wir Dienstags von 12-14 Uhr regelmäßig eine Plenarübung an, in der Fragen zu dem Material der Vorlesung oder den Übungsblättern von dem Dozenten oder dem Assistenten beantwortet werden.

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; Stabiles Matching (Kleinberg & Tardos, Kapitel 1)
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)

Übungsgruppen

Sie werden anfang des Semesters auf folgende Übungsgruppentermine aufgeteilt.

Seminarraum 014, E1 3:

Seminarraum 015, E1 3:

Literatur