Anmeldung

Die Anmeldung 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

Sie dürfen einen beidseitig handschriftlich beschriebenen DIN A4 Merkzettel mit in die Klausur bringen, ansonsten nur einen schwarzen oder blauen Stift.

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

Die meisten Literaturangaben beziehen sich auf Kleinberg & Tardos (Pearson New International Edition). Achtung: In manchen Ausgaben sind Kapitel 4 und 5 sowie 12 und 13 vertauscht.

# Datum Thema Kapitel

1

19.10.

Anmeldung zur Vorlesung und den Übungsgruppen; Einführung und Überblick; Stabiles Matching

1

2

26.10.

O-Notation; Laufzeitanalyse ; Listenzusammenf ührung

2.1 - 2.4

3

02.11.

Prioritätswarte schlangen; damit Sortieren; binäre Halden

2.5

4

09.11.

Breiten- und Tiefensuche

3.1 - 3.4

5

16.11.

Divide & Conquer: Mergesort, Schnelle Fouriertransfor mation

4.1, 4.2, 4.6

6

23.11.

Greedy-Algorith men I: Intervall-Sched uling, Kürzeste Wege, Minimale Spannbäume

5.1, 5.4, 5.5

7

30.11.

Greedy-Algorith men II: Minimale Spannbäume, Huffmann-Kodier ung

5.5, 5.6, 5.8

8

07.12.

Dynamische Programmierung I: Gewichtetes Intervall-Sched uling

6.1, 6.2

9

14.12.

Dynamische Programmierung II: RNA-Faltung

6.5, (6.6)

10

21.12.

Datenstrukturen I: Allgemeines; Binäre Suchbäume

7.1, 7.2 in Dietzfelbinger , Mehlhorn und Sanders

11

04.01.

Datenstrukturen II: Dictionaries, Hashing, Hash-Tabellen

12.6

12

11.01.

Maximaler Fluss, Ford-Fulkerson Algorithmus, Minimaler Schnitt

7.1, 7.2

13

18.01.

Lineare Programmierung, Profitmaximieru ng, Dualität

7.1 - 7.4 und 7.6 in Dasgupta, Papadimitriou, Vazirani [pdf]

14

25.01.

NP-Härte, Starke Exponenzialhypo these (SETH), Orthogonale Vektoren

u.A. 8 in DPV [pdf]

15

01.02.

Maximale unabhängige Menge, Pfadzerlegung, Baumzerlegung

u.A. 10.4

Übungsgruppen

Sie werden anfang des Semesters auf folgende Übungsgruppentermine aufgeteilt.

Seminarraum 014, E1 3:

Seminarraum 015, E1 3:

Literatur