Algorithmen und Datenstrukturen II

Qualifikationsziele: Die Absolventen dieses Moduls kennen die weiterführenden Algorithmen und Datenstrukturen der Informatik. Sie sind in der Lage, auch für komplexere Probleme eine algorithmische Lösung zu formulieren und algorithmische Lösungen in ihrer Leistungsfähigkeit einzuschätzen. Die Inhalte sind:

• Weiterführende Komplexitätsaspekte
• Elementare Aspekte zu Heuristiken, exakten Verfahren und Approximationsalgorithmen
• Enumerationsverfahren
• Probabilistische Ansätze
• Fortgeschrittene Datenstrukturen

Aktuelles

• Ergebnisse Wiederholungsklausur: Die Ergebnisse der Wiederholungsklausur können hier heruntergeladen werden. Die Einsicht der Klausur findet am Freitag, den 15.02.2019, zwischen 10:00 und 10:30 im Raum IZ 313 statt.
• Wiederholungsklausur: Die Wiederholungsklausur findet am 08.02.2019 von 12:00 Uhr bis 14:00 Uhr statt. Bitte seid 15 Minuten vorher anwesend. Der Klausurraum ist der IZ 313. Mitzubringen sind:
  • Ein gültiger Studentenausweis (plus gültiger Lichtbildausweis, falls kein Foto auf dem Studentenausweis vorhanden ist)
  • Ein dokumentenechter Stift (kein Rot!)
  • Ein Wörterbuch, falls nötig (auf Papier, ohne Notizen)
• Klausureinsicht: Die Einsicht findet am 06.09.2018 zwischen 13:00 Uhr und 14:30 Uhr im Raum IZ 313 statt.
• Klausur: Die Klausur findet am 03.08.2018 von 13:45 Uhr bis 15:45 Uhr statt. Bitte seid 15 Minuten vorher anwesend. Raumaufteilung:
  • Name A-K im Audimax
  • Name L-Z im PK 15.1
  Mitzubringen sind:
  • Ein gültiger Studentenausweis (plus gültiger Lichtbildausweis, falls kein Foto auf dem Studentenausweis vorhanden ist)
  • Ein dokumentenechter Stift (kein Rot!)
  • Ein Wörterbuch, falls nötig (auf Papier, ohne Notizen)
• Studienleistung erfolgreich erbracht (ohne Gewähr). Zu sehen sind die letzten fünf Stellen der Matrikelnummer.
• Die Übung am 16.05.18 fällt aus. Falls Bedarf besteht, können wir eine weitere Übung in der zweiten Hälfte des Semesters nachholen.
• Es gab einen kleinen Schreibfehler auf Blatt 1, der nun behoben ist. Bitte ladet euch die aktuelle Version von Blatt 1 erneut herunter. (Stand: 24.04.18)
• Bitte beachten: Am 24.04. und am 26.06. (jeweils Dienstage) benutzen wir den Ausweichtermin für die Vorlesung von 15:00 Uhr bis 16:30 Uhr im PK 2.2.

Material

Es gibt ein Skript zu dieser Vorlesung (Stand: 21.06.18). Achtung! Das ist ein dünner (und farbloser) Ersatz für eine lebende Vorlesung! Hinweise und Anmerkungen zum Skript mit einer kurzen Mail bei Dr. Arne Schmidt melden.

Vorlesungsnotizen

• Vorlesung 1 vom 12.04.18
• Vorlesung 2 vom 19.04.18
• Vorlesung 3 vom 24.04.18
• Vorlesung 4 vom 26.04.18
• Vorlesung 5 vom 03.05.18
• Vorlesung 6 vom 17.05.18
• Vorlesung 7 vom 31.05.18
• Vorlesung 8 vom 07.06.18
• Vorlesung 9 vom 14.06.18
• Vorlesung 10 vom 21.06.18
• Vorlesung 11 vom 26.06.18
• Vorlesung 12+13 vom 28.06.18 und 05.07.18

Große Übung

• Übung 1 vom 18.04.18: Organisation, Wiederholung Sortieren, Hausaufgaben (Programmierteil)
• Übung 2 vom 02.05.18: Dynamic Programming, Longest Common Subsequence
• Übung 3 vom 06.06.18: Branch-and-Bound für Knapsack, Euklidisches TSP
• Übung 4 vom 20.06.18: Komplexität, Reduktionen von 3SAT auf verschiedene Probleme. Das angesprochene Paper findet ihr auf arXiv.
• Übung 5 vom 04.07.18: Greedy_k, Kapitelzusammenfassung
• Übung 6 vom 11.07.18: Hashing, Besprechung Blatt 5

Hausaufgaben

• 0. Hausaufgabenblatt
  Für dieses Blatt gibt es keine Abgabe. Bitte bereitet die Aufgaben trotzdem für die erste kleine Übung vor, damit die Inhalte des Blattes besprochen werden können.
• 1. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 03.05.18, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 2. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 17.05.18, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 3. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 07.06.18, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 4. Hausaufgabenblatt
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 21.06.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 5. Hausaufgabenblatt (Es gibt ein Update für das Programm. Bitte HIER erneut herunterladen. Falls Probleme auftreten, bitte eine Mail an Dr. Arne Schmidt schreiben.)
  Abgaben in schriftlich, ausgearbeiteter Form: Bis spätestens Donnerstag, 05.07.17, 13:15 Uhr durch Einwurf im Kasten. Abgaben des Programmierteils: Per Mail an den Tutor mit der gleichen Abgabefrist. Alle Abgaben bitte mit Namen, Matrikelnummer und Gruppennummer versehen.
• 6. Hausaufgabenblatt
  Für dieses Blatt gibt es keine Abgabe. Bitte bereitet die Aufgaben trotzdem für die letzte große Übung vor, damit die Inhalte des Blattes besprochen werden können.
Hier sind die Javavorlage und Instanzen für den Programmierteil. (Hinweise: Die commons-lang und commons-math müssen nicht benutzt werden, können aber an der einen oder anderen Stelle behilflich sein. Nähere Hinweise dazu gibt es dann in den Blättern.
Da alle Instanzen gelöst werden sollen, bietet es sich an ein Skript zu schreiben, das nach und nach das Programm mit den unterschiedlichen Instanzen ausführt. Es gibt ein bash-Skript als Beispiel, dass unter Linux alle Instanzen löst und notfalls abbricht, falls mehr als zehn Minuten benötigt werden.)
Die Mail-Adressen der Tutoren sind:
• Mai Hellman: hellman@ibr.cs.tu-bs.de
• Yannic Lieder: lieder@ibr.cs.tu-bs.de
• Moritz Pfister: mpfister@ibr.cs.tu-bs.de
• Dennis Luck: dluck@ibr.cs.tu-bs.de
• Sabrina Hugo: hugo@ibr.cs.tu-bs.de
• Mohammad Mahhouk: mahhouk@ibr.cs.tu-bs.de

Klausuren

Sommer 2013, Sommer 2015, Sommer 2016, Sommer 2017

Mailingliste

Es gibt eine Mailingliste zu dieser Vorlesung. Bitte meldet euch da an, denn wir werden sie nutzen, um kurzfristig Informationen zu verteilen. Bei technischen Schwierigkeiten wendet euch bitte an Dr. Arne Schmidt.