Datenstrukturen und Algorithmen

News

  • 15.8.2018: Die Ergebnisse der Klausur und der 2. Präsenzübung können Sie nun im Übungssystem einsehen. Genaue Informationen zur Einsicht am 23.8.2018 folgen.
    Hinweis: Der Notenbonus aus den Übungen wird im Übungssystem noch nicht angezeigt.
  • 8.8.2018: Die Hörsaalverteilung für die erste Klausur ist wie folgt:

    000000-376699: Großer Hörsaal (Audimax)
    376700-379999: H01 (C.A.R.L.)
    380000-999999: Aula 1 (Hauptgebäude)

    Nachholpräsenzübung: Hörsaal H02 (C.A.R.L.) 

    Einlass ist ab 11:15 Uhr, die Klausur beginnt pünktlich um 11:30 Uhr. Bitte bringen Sie ihren Studierendenausweis und dokumentenechte Stifte mit. Als Hilfsmittel ist ein handbeschriebenes A4 Blatt (Vorder- und Rückseite) zugelassen.
    Zeitgleich findet die Wiederholungspräsenzübung im Hörsaal H02 (C.A.R.L.) statt. Hierfür gelten die gleichen Hinweise.

  • 20.7.2018: Wir haben einige alte Klausuren zu Übungszwecken bereitgestellt. Diese sind im Abschnitt ‘Klausur’ zu finden.
  • 19.7.2018: Hier ist der Übungsgenerator aus 2014: DSALExercisesStudent.  Im Zweifelsfalle gelten die Verfahren aus der Vorlesung von diesem Jahr. Beispielaufrufe zum Anzeigen eines Hilfetexts bzw. um LaTeX Code für eine Mergesort Aufgabe zu generieren:
    java -jar DSALExercisesStudent.jar -h
    java -jar DSALExercisesStudent.jar -a mergesort -l 8 -e exercise.tex -t solution.tex
  • 10.7.2018: Wir haben eine alte Klausur hochgeladen, die wir in der kommenden Globalübung vorrechnen werden.
  • 10.7.2018: Die Definition in Aufgabe 2 hatte einen Fehler..
  • 7.7.2018: In der Aufgabe 6 vom Übungsblatt 11 wurde die Definition der Pfadmengen Pi^k_v angepasst, da sie für den Fall v=t nicht ganz eindeutig war.
  • 3.7.2018: In der Aufgabe 3 vom aktuellen Übungsblatt war leider ein kleiner Fehler. Wir haben das Blatt nochmal aktualisiert.
  • 25.6.2018: Die Nachkorrektur der Präsenzübung ist abgeschlossen. Die aktualisierten Punktzahlen wurden in das Übungssystem eingetragen. Sie können Ihre Präsenzübung im Tutorium abholen.
  • 19.6.2018: Es gab einen kleinen Fehler in den Hinweisen zur Aufgabe 2 des aktuellen Übungsblattes. Dieser ist nun behoben und das Blatt aktualisiert.
  • 13.06.2018: Die Ergebnisse der Präsenzübung sind nun im Übungssystem verfügbar. Sie können Ihre Präsenzübung in Ihrem Tutorium einsehen.
  • 11.06.2018: In den Folien der 12. und 13. Vorlesung ist n der Anzahl belegte Slots in der Hashtabelle T und nicht (wie versehentlich angegeben wurde) die Kardinalität der Menge U. Die wurde in den Notizen der 13. Vorlesung korrigiert.
  • 08.06.2018: Informatik-Studierende können sich bis 2. Juli bewerben für ein “Porsche IT Campus RWTH Stipendium” in der Höhe von 356 pro Monat für mindestens ein Jahr. Weitere Informationen finden Sie hier: http://www.rwth-aachen.de/go/id/qpdd
  • 17.5.2018: Die Anmeldung zur Präsenzübung ist nun im Übungssystem freigeschaltet. Sie können sich bis zum 29.5. anmelden. Weitere Informationen zur Präsenzübung finden Sie weiter unten auf dieser Seite. Die Hörsaalverteilung wird noch bekannt gegeben.
  • 7.5.2018: Aufgrund einiger Rückfragen und kleiner Fehler wurde das aktuelle Übungsblatt (Übung 4) aktualisiert. Bitte aktualisieren Sie auch Ihren Cache, damit sichergestellt ist, dass Sie wirklich die aktuelle Version herunterladen.
  • 2.5.2018: Die zentrale Hochschulverwaltung hat uns heute mitgeteilt, dass der H01 am Freitag nicht verfügbar ist. Die Globalübung findet ausnahmsweise am Freitag 13:15 in dem Roten und dem Grünen Hörsaal statt.
  • 26.4.2018: Am Dienstag den 1.5.2018 fallen aufgrund des Feiertages die Tutorien aus. Sie können in dieser Woche ein anderes Tutorium besuchen. Am Freitag, den 4.5.2018 um 13:15 Uhr findet im H01 ausnahmsweise eine Globalübung und keine Vorlesung statt.
  • 19.4.2018: Die Frist für die Anmeldung zu den Übungsgruppen ist vorbei. Falls Sie noch nicht angemeldet und noch keinem Tutorium zugewiesen sind, kontaktieren Sie bitte die Assistenten (s. unten). 
  • 12.4.2018: Die Anmeldung für das Übungssystem ist nun freigeschaltet. Sie können sich hier mit Ihrer @rwth-aachen.de Adresse registrieren.
  • 5.4.2018: Die Termine für die Globalübung (ursprünglich Montags 08:30) und die Vorlesung (ursprünglich Dienstags 14:14) haben sich im Vergleich zu den Angaben im CAMPUS-System getauscht (s. unten).
  • 5.4.2018: In der ersten Vorlesung (13.4), sowie in der ersten Globalübung (24.4), werden wir einige organisatorische Fragen klären. Bis dahin brauchen Sie sich um nichts zu kümmern!
  • 4.4.2018: Die erste Vorlesung findet am Freitag den 13.4.2018 statt. Die erste Globalübung ist am 24.4.2018. Die weiteren Termine sind unten aufgeführt. Bitte beachten Sie, dass am 16.4.2018 und am 17.4.2018 keine Vorlesung und keine Globalübung stattfinden.
  • 4.4.2018: Wir sind online!

 

Wichtige Termine

  Wochentag Uhrzeit Raum
Regelmäßige Termine
Vorlesung Montag 8:30 – 10:00 H01
Vorlesung Freitag 13:15 – 14:45 H01
Globalübung Dienstag 14:15 – 15:45 Aula (Hauptgebäude)

Bitte beachten Sie, dass im CampusOffice die Vorlesung und Globalübung anders eingetragen sind.

 

Einmalige Termine
  Datum Uhrzeit Raum
Klausur 13.8. 11:00 – 14:00 Hörsaalverteilung wird im Übungssystem bekanntgegeben
Wiederholungsklausur 10.9. 10:00 – 13:00 Hörsaalverteilung wird im Übungssystem bekanntgegeben
Präsenzübung 7.6. 18:30 – 20:00 Hörsaalverteilung wird im Übungssystem bekanntgegeben

 

Vorlesungen

Nr. Thema Datum Handout Folien Notizen
1 Algorithmische
Komplexität
13.4.2018  l1_handout  l1_folien  notizen01
2 Asymptotische Effizienz 20.4.2018  l2_handout  l2_folien  notizen02
3 Elementare Datenstrukturen 23.4.2018  l3_handout  l3_folien  notizen03
4 Suchen 27.4.2018  l4_handout  l4_folien   notizen04
5 Rekursions­gleichungen 30.4.2018  l5_handout  l5_folien  notizen05
6 Mastertheorem 7.5.2018  l6_handout  l6_folien  notizen06
7 Sortieren 11.5.2018  l7_handout  l7_folien  notizen07
8 Heapsort 14.5.2018  l8_handout  l8_folien  notizen08
9 Quicksort 18.5.2018  l9_handout  l9_folien  notizen09
10 Binäre Suchbäume 28.5.2018 l10_handout  l10_folien  notizen10
11 Rot-Schwarz Bäume 1.6.2018  l11_handout  l11_folien  notizen11
12 Hashing I 4.6.2018  l12_handout  12_folien  notizen12
13 Hashing II 11.6.2018  l13_handout  l13_folien  notizen13
14 Elementare Graphen­algorithmen 15.6.2018  l14+15_handout  l14+15_folien  notizen14+15
15 Elementare Graphen­algorithmen 18.6.2018      
16 Minimale Spannbäume 22.6.2018  l16_handout  l16_slides  notizen16
17 Kürzeste Pfade 25.6.2018  l17_handout  l17_slides  notizen17
18 Kürzeste Pfade + Maximale Flüsse 29.6.2018  l18_handout  l18_slides  notizen18
19 Maximale Flüsse 2.7.2018      
20 Dynamische Programmierung 6.7.2018  l19_handout  l19_slides  notizen20
21 Algorithmische Geometrie 9.7.2018  l20_handout  l20_slides  notizen21

 

Für die Vorlesungen brauchen Sie sich nicht anzumelden. Es gibt kein l2p Lernraum für diese Veranstaltung.

Globalübungen

Nr. Thema Datum Notizen
1 Relationen, Pseudocode, Laufzeitanalyse, Baum Traversierung 24.4.2018  notizen01
2 O-Notation, Average-Case Analyse, Rekursionsgleichungen 4.5.2018 im Roten und Grünen Hörsaal  notizen02
3 Rekursionsbäume, Mastertheorem 8.5.2018 notizen03
4 Fixpunktinduktion, Mergesort, Heapsort 15.5.2018 notizen04
5 Mastertheorem, Binäre Suchbäume 29.5.2018 notizen05
6 Präsenzübung 2015 5.6.2018
7 Hashing, Laufzeiten 12.6.2018 notizen07
8 Graphenalgorithmen 19.6.2018 notizen08
9 Dijkstra 26.6.2018 notizen09
10 Flüsse 3.7.2018 notizen10
11 Dynamisches Programmieren 10.7.2018 notizen11
12 Klausur vorrechnen 17.7.2018  

 

Für die Globalübungen brauchen Sie sich nicht anzumelden. Es gibt kein l2p Lernraum für diese Veranstaltung.

Übungen

Begleitend zur Vorlesung gibt es Übungsblätter, die zu dritt zu bearbeiten sind. Die Übungszettel werden jeweils donnerstagabends auf dieser Seite online gestellt und sind in der Regel 7 Tage später (donnerstags) bis 16:00 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.

Die Lösungen zu den Übungsaufgaben werden in den wöchentlichen Kleingruppenübungen besprochen. Es gibt kein l2p Lernraum für diese Veranstaltung.

Sie könnnen ihre Punkte im Übungsystem einsehen. Ein Tausch der Übungsgruppe mit einem anderen Studierenden ist ebenfalls über das Übungssystem 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 Lösung
1 19.04.2018  Übungsblatt 01  Musterlösung 01
2 26.04.2018  Übungsblatt 02  Musterlösung 02
3 3.5.2018  Übungsblatt 03  Musterlösung 03
4 9.5.2018  Übungsblatt 04  Musterlösung 04
5 17.5.2018  Übungsblatt 05  Musterlösung 05
6 30.5.2018  Übungsblatt 06  Musterlösung 06
7  14.6.2018  Übungsblatt 07 Musterlösung 07
8  21.6.2018  Übungsblatt 08 Musterlösung 08
9  28.6.2018  Übungsblatt 09 Musterlösung 09
10  5.7.2018  Übungsblatt 10 Musterlösung 10
11  12.7.2018  Übungsblatt 11 Musterlösung 11

Klausurzulassung und Bonusregelung

Folgende Kriterien müssen für die Zulassung zur Klausur erfüllt werden:

  1. Mindestens 50% aller in den Übungen erreichbaren Punkte bis zur Präsenzübung (d.h. Blatt 1 bis einschließlich Blatt 6)
  2. Mindestens 50% aller in den Übungen erreichbaren Punkte ab der Präsenzübung (d.h. ab Blatt 7)
  3. Mindestens 50% der in der Präsenzübung erreichbaren Punkte.

Es gibt kein Zulassungskriterium für CES-Studierende.

Es gilt außerdem folgende Bonusregelung für alle Studiengänge: Bei mindestens 70% in allen drei oben genannten Punkten wird die Klausurnote um eine Notenstufe (0.3) verbessert. Das heißt aus einer 2.3 wird beispielsweise eine 2.0 (gilt nicht bei 1.0 und 5.0).

Wenn Sie die Kriterien nicht erfüllen, melden wir Sie beim ZPA als nicht zugelassen (NZ).

Präsenzübung

Am 7.6. um 18:30 Uhr findet eine Präsenzübung statt. In der Präsenzübung muss unter Klausurbedingungen und in Einzelarbeit ein zusätzliches Übungsblatt gelöst werden. Die Bearbeitungsdauer der Präsenzübung beträgt 90 Minuten. Die Hörsaalverteilung wird noch bekannt gegeben. Zur Erwerbung der Klausurzulassung müssen mindestens 50% der Punkte erlangt werden.

Der Inhalt der Präsenzübung umfasst den gesamten Vorlesungsstoff bis einschließlich Vorlesung 10 (Binäre Suchbäume) sowie die Inhalte der Globalübungen und Übungsblätter 1 bis (einschließlich) 6.

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 zwei alte Präsenzübungen verfügbar. Beachten Sie bitte, dass die Verfahren in den Lösungen geringfügig von den Verfahren aus der diesjährigen Vorlesung abweichen können. Für die Präsenzübung am 07.06.2018 sind die Verfahren der laufenden Vorlesung maßgeblich.

Die Ergebnisse der Präsenzübung sind nun im Übungssystem verfügbar. Sie können Ihre Präsenzübung in Ihrem Tutorium einsehen. Die Präsenzübung von diesem Jahr mit zugehöriger Musterlösung ist ebenfalls unten verfügbar.

PÜ12 Lösung12
PÜ15 Lösung15
PÜ18 Lösung18

Wiederholungstermin

Für Studierende, die nicht an der ersten Präsenzübung teilnehmen konnten oder nicht genügend Punkte erziehlt haben, gibt es eine zweite Präsenzübung am ersten Klausurtermin (13.8.2018). Bei bestandener zweiter Präsenzübung und genügend Punkte in den Übungen können Sie dann am zweiten Klausurtermin (10.9.2018) die Klausur regulär mitschreiben.

Beachten Sie, dass die zweite Präsenzübung die gesamten Inhalte aller Vorlesungen, Globalübungen und Übungsblätter umfasst. Ansonsten gelten die gleichen Bedingungen wie bei der ersten Präsenzübung. Es ist auch möglich den Klausurbonus über die zweite Präsenzübung zu erhalten. Studierende, die bereits die Klausurzulassung über die erste Prasenzübung erworben haben, können jedoch nicht an der zweiten Präsenzübung teilnehmen.

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.

Zu Übungszwecken stellen wir einige alte Klausuren zur Verfügung. Beachten Sie bitte, dass die Verfahren in den Lösungen von den Verfahren aus der diesjährigen Vorlesung abweichen können. Für die Klausur sind die Verfahren der laufenden Vorlesung maßgeblich.

Klausur12.1 Lösung12.1
Klausur12.2 Lösung12.2
Klausur15.1 Lösung15.1
Klausur15.2 Lösung15.2

 

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

Sebastian Junges, Benjamin Kaminski, David Korzeniewski, Tim Quatmann,
E-Mail
dsal18@i2.informatik.rwth-aachen.de