Datenstrukturen und Algorithmen

News

  • 16.09.2015: Die Einsicht zur zweiten Klausur findet am 18.09.2015 von 11 bis 12 Uhr im AH I statt.
  • 14.09.2015: Die Ergebnisse der zweiten Klausur sind ab sofort im Übungssystem einsehbar.
  • 16.08.2015: Die erste Klausur und die dazugehörige Lösung sind nun in der Rubrik “Klausur” verfügbar.
  • 10.08.2015: Die Verteilung von Matrikelnummern auf Zeitblöcke für die Einsicht der ersten Klausur in Raum 5052 lautet wie folgt:
    000000-342999 14:00-15:00
    343000-345999 15:00-16:00
    346000-999999 16:00-17:00

    Die Einsicht für die zweite Präsenzübung läuft parallel dazu von 14:00 bis 17:00 Uhr ebenfalls in Raum 5052 (hier ist also keine spezielle Verteilung von Matrikelnummern auf Zeitblöcke nötig).

  • 07.08.2015: Die Einsicht für die erste Klausur und die zweite Präsenzübung findet zwischen 14 und 17 Uhr am 12.08.2015 in Raum 5052 statt. Eine Verteilung von Matrikelnummernbereichen auf Zeitblöcke wird später bekanntgegeben.
  • 05.08.2015: Die Ergebnisse der ersten Klausur und zweiten Präsenzübung sind ab sofort im Übungssystem einsehbar.
  • 02.08.2015: Korrektur Handout Seite 7 im Algorithmus Schnitt zweier Strecken. Hier muss man am Ende noch prüfen, ob alle Richtungen 0 sind und falls das so ist, false zurückgeben. Dies ist jetzt angepasst worden.
  • 31.07.2015: Unter der Rubrik “Klausur” ist ab sofort eine weitere alte Klausur von 2012 zu finden. Beachten Sie bitte, dass nicht alle Aufgaben der Klausur von 2012 für die Vorlesung in diesem Jahr relevant sind und sich die präsentierten Lösungen auch von denen für die aktuelle Vorlesung verlangten Lösungswegen unterscheiden können.
  • 27.07.2015: Die Hörsaalverteilung für die erste Klausur und die zweite Präsenzübung ist über das Übungssystem einsehbar (auch ohne Login). Ihren Zulassungs- und Anmeldestatus können Sie ebenfalls im Übungssystem unter der Rubrik “Übersicht” einsehen (nur mit Login). Überprüfen Sie diesen Status, um eventuelle Unstimmigkeiten früh genug zu erkennen, und teilen Sie uns etwaige Probleme bitte unverzüglich mit.
  • 19.07.2015: Die neue Version des Übungsgenerators generiert jetzt detailliertere Erklärungen für Rot-Schwarz-Baum-Aufgaben.
  • 18.07.2015: Die Anmeldung für die zweite Präsenzübung am 04.08.2015 ist ab sofort bis zum 24.07.2015 offen. Anmeldungen sind über das Übungssystem in der Rubrik “Übersicht” möglich.
  • 08.07.2015: Es gibt jetzt eine Rubrik “Wettbewerb”, in dem die Regeln, das Code-Gerüst und die Folien der Auswertung zur Verfügung stehen und die Daten/Implementierungen nachgereicht werden.
  • 08.07.2015: Unter der Rubrik “Klausur” ist ab sofort eine alte Klausur von 2012 zu finden. Wir werden diese Klausur am 17.07.2015 vorrechnen.
  • 06.07.2015: Klarstellung zu Blatt 9, Aufgabe 8b): Gemeint ist hier das Flussnetzwerk aus Aufgabenteil a).
  • 03.07.2015: Zeile 19 (Folie 33) sollte return inverseMap sein (statt return inverseMap(hull)).  In der Erklärung in der Vorlesung sollte e1.e1 = 1 = e2.e2 und e1.e2 = 0 = e2.e1 sein (hier wurden 0 und 1 versehentlich getauscht).
  • 24.06.2015: Wegen des Sommerfestes finden die Tutorien am Freitagnachmittag (26.06.2015) nicht statt und die Vormittagstutorien werden zusammengelegt. Nähere Informationen hierzu erhalten Sie bei ihrem Tutor.
  • 19.06.2015: Wegen des “RWTH FH Sports Day” findet das Tutorium 13 am Mittwoch, den 24.06.2015 um 18.15 Uhr nicht statt. Die betroffenen Studierenden können stattdessen ein beliebiges anders Tutorium besuchen.
  • 10.06.2015: Die Folien zum geschlossenen Hashing (siehe Vorlesung 12, Folie 21) wurden aktualisiert: hcInsert setzt nun ein Element an das Ende der Liste anstatt an den Anfang (wie man es auch intuitiv machen würde). Insbesondere sind nun Musterlösung und Folien konsistent.
  • 10.06.2015: Die Präsenzübung vom 03.06.2015 und deren Lösung sind nun in der Rubrik “Übungen” verfügbar.
  • 10.06.2015: Wir haben eine Ausgleichsregelung für die Zulassung zwischen der ersten Präsenzübung und der zweiten Hälfte der Hausaufgaben eingeführt (siehe unten). Außerdem fügen wir ab Blatt 7 zusätzliche Wiederholungsaufgaben alter Themen ein, welche wir mit einer Zeitangabe versehen, innerhalb derer diese Aufgaben zu lösen sein sollten (damit selbst kontrolliert werden kann, ob der Stoff auch in hinreichender Geschwindigkeit beherrscht wird). Diese Aufgaben werden besonders scharf bewertet, da es sich um Wiederholungen handelt. D.h. Folgefehler werden bei der Korrektur der Wiederholungsaufgaben nicht berücksichtigt.
  • 09.06.2015: Die Ergebnisse der ersten Präsenzübung sind im Übungssystem einsehbar. Außerdem haben wir auch eine Note dazu angegeben, die dem Ergebnis entsprechen würde, falls dies eine echte Klausur gewesen wäre. Statistiken können in der zugehörigen Rubrik im Übungssystem abgerufen werden. Die Einsicht findet am 18.06.2015 von 8:00 bis 11:00 Uhr in Raum AH II statt. Um die Auslastung einigermaßen gleichmäßig zu verteilen, bitten wir um die Einhaltung der folgenden Zeiten in Abhängigkeit vom Hörsaal, in welchem die Präsenzübung geschrieben wurde: Grüner Hörsaal von 8:00 bis 8:40 Uhr, Roter Hörsaal von 8:40 bis 9:20 Uhr, Großer Hörsaal (Audimax) von 9:20 bis 10:00 Uhr, alle: 10:00 bis 11:00 Uhr.
  • 05.06.2015: Ab sofort stehen die Regeln des Software-Wettbewerbs sowie das versprochene Code-Gerüst (inklusive naiver Implementierung und Beispieleingabe) zur Verfügung.
  • 03.06.2015: Bitte beachten Sie die neue Hörsaalverteilung für die heutige Präsenzübung! Sie können diese dem Übungssystem entnehmen.
  • 30.05.2015: Die Folien zu den Rot-Schwarz-Bäumen (Vorlesung 11) wurden aktualisiert. Dort passten die Bedingungen in den Algorithmen rbtDel und rbtDelFix nicht zusammen, wenn der zu löschende Knoten keine Kinder hat. Dieser Fehler ist nun behoben.
  • 29.05.2015: Ab sofort finden Sie in der Rubrik “Präsenzübung” auf dieser Website eine alte Präsenzübung und die dazugehörige Musterlösung. Beachten Sie bitte, dass die Verfahren in dieser Lösung geringfügig von den Verfahren aus der diesjährigen Vorlesung abweichen. Für die Präsenzübung am 03.06.2015 sind die Verfahren der laufenden Vorlesung maßgeblich.
  • 29.05.2015: Die Lösungen der Tutoraufgaben von Blatt 5 und der Aufgabengenerator wurden aktualisiert, um Rotationen vor ihrer Durchführung zu markieren.
  • 23.05.2015: Die Folie zu heapify (in Vorlesung 8) wurde aktualisiert. In der Abbruchbedingung wurde das > durch ein >= ersetzt, da man ansonsten bei gleichen Elementen unnötige Tauschoperationen vornimmt.
  • 21.05.2015: Ab sofort können Sie unter der Rubrik “Übungen” auf dieser Webseite unseren Übungsaufgabengenerator herunterladen.
  • 20.05.2015: Ein Hinweis zur anstehenden Präsenzübung: der Stoff der Präsenzübung umfasst Vorlesung 1 bis einschließlich Vorlesung 11.
  • 19.05.2015: Leider hatte sich ein Fehler auf Blatt 4, Aufgabe 6a) eingeschlichen. In der aktualisierten Version, soll beim Bestimmen der Komplexitätsklasse die Anzahl der Vergleiche von Arrayelementen gezählt werden und nicht die Anzahl der tatsächlich ausgeführten exchange Operationen. Wir entschuldigen uns für die kurzfristige Änderung. Die aktuelle Aufgabenstellung macht die Aufgabe jedoch leichter. Diejenigen, die bereits eine Lösung abgegeben haben, können bis zur regulären Abgabefrist noch eine aktualisierte Lösung zu dieser Aufgabe einwerfen. In jedem Fall wird die Aufgabe so korrigiert, dass die Änderung euch nicht zum Nachteil gereicht.
  • 11.05.2015: In der Zeit vom 25.5.2015 bis zum 5.6.2015 fallen aufgrund der Exkursionswoche und der Präsenzübung alle Tutorien aus. Bitte beachten Sie auch die nachfolgende, die Anmeldung zur Präsenzübung betreffende Meldung!
  • 11.05.2015: Ab sofort ist die Anmeldung zur Präsenzübung, die am 03.06.2015 von 18:15 bis 19:45 Uhr stattfindet, in unserem Übungssystem in der Rubrik “Übersicht” möglich. Die Anmeldung muss spätestens bis zum 22.05.2015 erfolgen, um an der Präsenzübung teilnehmen zu dürfen.
  • 07.05.2015: Das dritte Übungsblatt wurde aktualisiert. Eine der bisherigen Aufgaben ist nun eine Bonusaufgabe und wurde durch eine einfachere Aufgabe ersetzt. Beachten Sie außerdem, dass bei den Rekursionsgleichungsaufgaben nicht davon ausgegangen werden darf, dass die Rundung beim rekursiven Aufruf keinen Einfluss auf die Komplexitätsklasse hat.
  • 04.05.2015: Die Folien der dritten Vorlesung sowie das zweite Übungsblatt wurden aktualisiert, um eine einheitlichere Behandlung von Elementen und Schlüsseln in ADTs zu gewährleisten. Denken Sie daran, dass Sie die entsprechenden PDFs eventuell manuell neu laden müssen, da Ihr Browser die alten Version im Cache haben könnte.
  • 20.4.2015: Ab sofort können sich Studierende, welche noch keiner Übungsgruppe zugeordnet sind, selbst eine Gruppe im Übungssystem zuweisen. Die Auswahl ist hierbei jedoch auf die Tutorien beschränkt, die aktuell die kleinste Teilnehmerzahl haben.
  • 9.4.2015: Alle Vorlesungen werden aufgezeichnet durch die Video-AG.
  • 3.4.2015: Sie können sich ab sofort hier für das Übungssystem registrieren.
  • 11.3.2015: Wir sind online!

 

Wichtige Termine

  Wochentag Uhrzeit Erster Termin Raum
Regelmäßige Termine
Vorlesung Donnerstag 10:15 – 11:45 09.4.2015 Aula (Hauptgebäude)
Vorlesung Freitag 10:15 – 11:45 10.4.2015 Großer Hörsaal (Audimax)
Globalübung Mittwoch 12:15 – 13:45 23.4.2015 (Donnerstag 10:15h statt Mittwoch) Aula (Hauptgebäude)
Einmalige Termine
  Datum Uhrzeit Raum
Präsenzübung 03.06. 18:15 – 19:45 Hörsaalverteilung wird im Übungssystem bekanntgegeben
Klausur 04.08.   Hörsaalverteilung wird im Übungssystem bekanntgegeben
Einsicht zur Klausur 12.08. 14:00 – 17:00 5052
Wiederholungsklausur 14.09.   Hörsaalverteilung wird im Übungssystem bekanntgegeben
Einsicht zur Wiederholungsklausur      

 

Vorlesungen

Wichtig: Es kann vorkommen, dass die Globalübung und die Vorlesung getauscht werden. Dies wird rechtzeitig hier und in der Vorlesung bekannt gegeben.

Nr. Thema Datum Handout / Folien
1 Algorithmische Komplexität 09.4.2015 Algorithmische Komplexität /
Algorithmische Komplexität
2 Asymptotische Effizienz 10.4.2015 Asymptotische Effizienz /
Asymptotische Effizienz
3 Elementare Datenstrukturen 16.4.2015 Elementare Datenstrukturen /
Elementare Datenstrukturen
4 Suchen 22.4.2015 Suchen / Suchen
5 Rekursionsgleichungen 24.4.2015 Rekursionsgleichungen /
Rekursionsgleichungen
6 Master-Theorem 30.4.2015 Master-Theorem /
Master-Theorem
7 Sortieren 30.4.2015 Sortieren / Sortieren
8 Heapsort 07.5.2015 Heapsort / Heapsort
9 Quicksort 07.5.2015 Quicksort / Quicksort
10 Binäre Suchbäume 08.5.2015 Binäre Suchbäume /
Binäre Suchbäume
11 Rot-Schwarz-Bäume 15.5.2015 Rot-Schwarz-Bäume /
Rot-Schwarz Bäume
12 Hashing (1) 20.5.2015 Hashing (1) / Hashing (1)
13 Hashing (2) 21.5.2015 Hashing (2) / Hashing (2)
14 Elementare Graphenalgorithmen (1) 05.6.2015 Elementare Graphenalgorithmen / Elementare Graphenalgorithmen
15 Elementare Graphenalgorithmen (2) 11.6.2015  
16 Minimale Spannbäume 12.6.2015 Minimale Spannbäume / Minimale Spannbäume
17 Kürzeste Pfadalgorithmen 18.6.2015 Kürzeste Pfade / Kürzeste Pfade
18 Maximaler Fluss 25.6.2015 Maximaler Fluss / Maximaler Fluss
19 Dynamische Programmierung 02.7.2015 Dynamische Programmierung / Dynamische Programmierung
20 Algorithmische Geometrie 03.7.2015 Algorithmische Geometrie / Algorithmische Geometrie

 

Globalübungen

In der Globalübung werden die Lösungen der Übungsblätter besprochen. Am 3.6. findet zusätzlich zur Globalübung abends eine Präsenzübung statt.

 

Übungen

Begleitend zur Vorlesung gibt es Übungsblätter, die zu zweit oder zu dritt zu bearbeiten sind. Die Übungszettel werden jeweils mittwochabends auf dieser Seite online gestellt und sind in der Regel 14 Tage später (mittwochs) bis 12:15h Uhr abzugeben. Die Abgabe erfolgt durch Einwurf der Lösungen in die Übungskästen. Die Kästen befinden sich am Eingang Halifaxstraße des Informatikzentrums (Ahornstr. 55). Alternativ können die Lösungen auch vor der Abgabefrist direkt im Tutorium oder bei der Globalübung abgegeben werden.

Zusätzlich zu den abzugebenden Übungen werden in den wöchentlichen Kleingruppenübungen weitere Übungsaufgaben besprochen. Zu den Kleingruppen können Sie sich hier anmelden. Ein Tausch mit einem anderen Studierenden ist über das Übungssystem (nach der Verteilung auf die Tutorien) möglich.

Bitte beachten Sie, dass eine erfolgreiche Teilnahme am Übungsbetrieb für die Zulassung zur Klausur nötig ist. Näheres dazu entnehmen Sie bitte dem Abschnitt “Klausurzulassung”.

Nr. Abgabedatum Übungsblatt
0 15.04.2015 Übung 0
1 29.04.2015 Übung 1
2 06.05.2015 Übung 2
3 13.05.2015 Übung 3
4 20.05.2015 Übung 4
5 03.06.2015 Übung 5
03.06.2015 Präsenzübung
6 17.06.2015 Übung 6
7 24.06.2015 Übung 7
8 01.07.2015 Übung 8
9 08.07.2015 Übung 9
10 15.07.2015 Übung 10

Um zufällig generierte Übungsaufgaben inklusive Musterlösung zu erstellen, können Sie unseren Übungsaufgabengenerator verwenden. Zum Ausführen dieses Programms ist eine vorherige Installation von Java (Version 8 oder höher) notwendig. Zum Starten einfach java -jar DSALExercisesStudent.jar <options>  eingeben. Ein Hilfetext zu den möglichen Optionen kann mit java -jar DSALExercisesStudent.jar -h  angezeigt werden. Das Programm erstellt LaTeX Dateien, die mithilfe des Programms pdflatex in PDF Dateien übersetzt werden können.

Präsenzübung

Am 3.6. findet eine Präsenzübung statt (Umfang: 90 Minuten). In der Präsenzübung muss unter Klausurbedingungen und in Einzelarbeit ein zusätzliches Übungsblatt gelöst werden. Studenten, die die erste Präsenzübung nicht bestehen (weniger als 50% der Punkte), haben die Möglichkeit, an der Wiederholungsübung teilzunehmen. Diese findet parallel zur ersten Klausur statt. Studierende, die bei diesem zweiten Termin erfolgreich die Präsenzübung bestehen, haben die Möglichkeit, die Klausur am zweiten Termin zu schreiben.

Der Inhalt der Präsenzübung umfasst jeweils den gesamten Stoff, der bis zum Zeitpunkt der Übung in der Vorlesung behandelt wurde. Demnach umfasst die Wiederholungspräsenzübung den gesamten Vorlesungsstoff.

Bringen Sie Ihren Studierendenausweis (mit Bild, sonst noch einen weiteren Lichtbildausweis) und einen dokumentenechten Stift (nicht grün oder rot und insbesondere keinen Bleistift) zur Präsenzübung mit. Sie dürfen außerdem ein DIN A4 Blatt mit handschriftlichen (nicht gedruckten) Notizen auf beiden Seiten zur Präsenzübung mitnehmen. Weitere Hilfsmittel sind nicht zugelassen. Papier wird von uns gestellt.

Um sich besser auf die Präsenzübung vorzubereiten, machen wir eine alte Präsenzübung und ihre Musterlösung verfügbar. Beachten Sie bitte, dass die Verfahren in dieser Lösung geringfügig von den Verfahren aus der diesjährigen Vorlesung abweichen. Für die Präsenzübung am 03.06.2015 sind die Verfahren der laufenden Vorlesung maßgeblich.

Klausurzulassung

Um die Klausurzulassung zu erwerben, müssen jeweils mindestens 50% der Punkte aus den Übungen vor der Präsenzübung, 50% der Punkte in der Präsenzübung und 50% der Punkte aus den Übungen nach der Präsenzübung erreicht werden. Zulassungen aus vorherigen Semestern sind nur gültig, wenn bereits ein Prüfungsversuch stattgefunden hat. Falls jemand in der ersten Präsenzübung weniger als 50%, aber mindestens 33% der Punkte erreicht hat, so ist ein Ausgleich über die Punkte der zweiten Hälfte möglich, wenn die Summe der Prozentzahlen in der ersten Präsenzübung und der zweiten Hälfte mindestens 110 ergeben. Für die zweite Präsenzübung ist kein solcher Ausgleich möglich.

Studierende des Studiengangs Computational Engineering Science benötigen keine Zulassung zur Klausur. Die Teilnahme an Übungen und Präsenzübung wird dennoch dringend empfohlen.

Bonusregelungen:

Für Studierende aller Studiengänge gilt die folgende Bonusregelung: Bei einem Erreichen von jeweils mindestens 75% der Punkte aus den Übungen vor der Präsenzübung, 75% der Punkte in der Präsenzübung und 75% der Punkte aus den Übungen nach der Präsenzübung gibt es einen Bonus von einer Notenstufe auf das Klausurergebnis (aus einer 1.7 wird beispielsweise eine 1.3 und aus einer 2.3 eine 2.0). Ausgeschlossen sind die Noten 1.0 und 5.0.

 

Klausur

Die Klausur wird über eine Dauer von 2 Stunden in Einzelarbeit geschrieben.

Außer einem dokumentenechten Stift (blau oder schwarz, nicht rot oder grün) ist ein DIN A4 Blatt mit handschriftlichen (nicht gedruckten) Notizen auf beiden Seiten zugelassen. Andere Hilftsmittel sind nicht erlaubt. Insbesondere sind keine elektronischen Geräte wie Taschenrechner, Telefone oder gar Laptops erlaubt. Bringen Sie zur Klausur Ihren Studierendenausweis (mit Lichtbild) mit. Sollten Sie keinen Studierendenausweis mit Lichtbild besitzen, bringen Sie einen amtlichen Lichtbildausweis und einen Nachweis über Ihre Immatrikulation mit. Papier zur Lösung der Aufgaben sowie für Nebenrechnungen wird von uns gestellt. Sie dürfen kein eigenes Papier verwenden.

Parallel zur Klausur wird es einen Nachschreibetermin für die Präsenzübung geben. Diese wird eine Bearbeitungsdauer von 90 Minuten haben. Ansonsten gelten für die Präsenzübung die gleichen Voraussetzungen wie für die Klausur, insbesondere ist der Inhalt der gesamten Vorlesung prüfungsrelevant und es gilt dieselbe Regelung bezüglich der Hilfsmittel.

Zur Vorbereitung können Sie hier die erste Klausur von 2012 und die zugehörige Lösung (vorgerechnet am 17.07.2015) und hier die zweite Klausur von 2012 und die zugehörige Lösung herunterladen. Genau wie bei der alten Präsenzübung weichen die Notationen und Verfahren teilweise geringfügig von denen in der aktuellen Vorlesung ab. Für die Klausuren im laufenden Semester sind ausschließlich die Verfahren und Notationen aus der laufenden Veranstaltung maßgeblich.

Die erste Klausur aus dem Sommersemester 2015 und die entsprechende Lösung sind nun auch verfügbar.

Wettbewerb

Im Rahmen der Vorlesung findet ein Software-Wettbewerb statt. Ziel ist es, mit Hilfe von Vorlesungsinhalten und darüber hinausgehenden Ideen eine algorithmische Lösung zu einem Problem zu erarbeiten und diese zu implementieren. Wir stellen hier die genauen Regeln und ein Code-Gerüst, in welches die Implementierung einzubetten ist, zur Verfügung.

Wir freuen uns über die Teilnahme von insgesamt 14 Gruppen, die sich alle sehr gut geschlagen haben! Die Auswertung des Wettbewerbs wurde am 8.07.2015 in der Globalübung besprochen, die Folien kann man hier finden. Sieger ist Gruppe 13, bestehend aus René Schäfer, Johannes Seiffarth und Leon Wittwer mit ihrer Implementierung “WeirdTrigramStorage”. Wir danken allen Gruppen für ihre Teilnahme und hoffen, dass es Ihnen auch Spaß gemacht hat.

Außerdem stellen wir den Source-Code einiger Gruppen, die der Veröffentlichung zugestimmt haben und deren Lösung auf den Benchmarkdaten fehlerfrei funktionierte, hier zur Verfügung. Die verschiedenen Implementierungen, die in separate Paketen unterteilt sind, können über die Option -grp<x> ausgewählt werden, wobei x die zu testende Gruppennummer ist. In der Hilfe (-help) können Sie sehen, welche Gruppennummern verfügbar sind. Außerdem ist unsere “kompetitive” Implementierung verfügbar und kann mit -i2 ausgewählt werden.

Achtung: Beachten Sie (1) dass nicht alle Gruppen zugestimmt haben, die Implementierung mit dem Namen der Autoren zu versehen und (2) dass es bei dem Wettbewerb ausschließlich um hochperformanten Code ging und nicht darum Designentscheidungen zu treffen, die eine nachhaltige Wartbarkeit des Codes möglich machen.

Literatur

Die Vorlesung orientiert sich im Wesentlichen an:

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen – Eine Einführung, R. Oldenbourg Verlag , 1. Auflage 2004.

 

Kontakt

Sprechstunden sind nach Vereinbarung (per Mail) möglich.

Wenn Sie Fragen oder Anregungen haben, können Sie uns gerne kontaktieren:
Assistenten

Christian Dehnert, Friedrich Gretz, Benjamin Kaminski, Thomas Ströder
E-Mail
dsal15@i2.informatik.rwth-aachen.de