Datenstrukturen und Algorithmen

News:

  • Die Einsicht zur zweiten Klausur findet nicht am Montag, den 22.09., sondern am Freitag, den 19.09., von 10:00 bis 11:30 im AH I statt.
  • Die Ergebnisse der zweiten Klausur sind online.
  • Die Ergebnisse der zweiten Klausur wurden nach der Einsicht aktualisiert.
  • Die zweite Klausur nebst Lösung ist nun unter der Rubrik Klausur erhältlich.

Wichtige Termine

Datum Uhrzeit Raum
Präsenzübung 23.05. 10:00 – 12:00 AM, FT, Aula 2,
AH IV
Wiederholung der Präsenzübung 05.08 09:00 – 11:00 AH V
Klausur  05.08. 09:00 – 11:30 Gr, Fo 2, AM,
Ro, Aula 1
Einsicht zur Klausur 13.08. 14:00 – 17:00 5052
Wiederholungsklausur 15.09. 12:30 – 14:30 Fo1
Einsicht zur Wiederholungsklausur 19.09. 10:00 – 13:00 AH I

Vorlesungen

Die Vorlesungen finden jeden Donnerstag von 10:15 bis 11:45 im Fo1 sowie jeden Freitag von 10:15 bis 11:45 im Großen Hörsaal statt.

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 (annotiert)
Organisation 14.04. Prezi
1 Einführung 14.04. lec01_handout lec01_annotiert
2 Asymptotische Komplexität 17.04. lec02_handout lec02_annotiert
3 Rekursion 24.04. lec03_handout lec03_annotiert
4,5 Datenstrukturen 1 & 2 25.04.
02.05.
lec04_05_handout lec04_05_annotiert
6,7 Suchen & sortieren 08.05.
09.05.
lec06_07_handout lec06_07_annotiert
8 Zusammenfassung 12.05. lec08_handout lec08_annotiert
9 Suchbäume + AVL-Bäume 15.05. lec09_handout lec09_annotiert
9b AVL-Bäume 04.08. PseudoCode
10 2-3-4-Bäume 22.05. lec10_handout lec10_annotiert
10b 2-3-4-Bäume 03.08. Schema
11 Rot-Schwarz-Bäume + Nachtrag 30.05.
02.06.
lec11_handout lec11_annotated
12 Hashing 02.06.
06.06.
lec12_handout lec12_annotiert
12b Zusammenfassung 20.06. zsfsg_2_handout zsfsg_2_annotiert
13 Elementare Graphen-algorithmen

20.06.
26.06.
27.06.

lec13_handout lec13_annotiert
14 Minimale Spannbäume

27.06.

lec14_handout lec14_annotiert
15 Kürzeste Pfade

03.07.

lec15_handout lec15_annotiert
16 Flussnetzwerke

04.07.

lec16_handout lec16_annotiert
17 Dynamische Programmierung

10.07.

lec17_handout lec17_annotiert
18 Algorithmische Geometrie

11.07.

lec18_handout lec18_annotiert
19 Zusammenfassung

17.07.

lec19_handout lec19_annotiert

Die Evaluation der Vorlesung (ohne handschriftliche Kommentare) finden Sie hier.

Globalübungen

Die Globalübungen finden jeden Montag von 10:15 bis 11:45 im Fo1 statt. Die Evaluation der Globalübung (ohne handschriftliche Kommentare) finden Sie hier.

Übungen

Begleitend zur Vorlesung und Globalübung gibt es Übungen, die zu zweit oder zu dritt zu bearbeiten sind. Die Übungszettel werden jeweils Montag abends auf dieser Seite online gestellt und sind 7 Tage später (Montag) bis 9 Uhr abzugeben. Die Abgabe erfolgt durch Einwurf der Lösungen in die Übungskästen. Die Kästen befinden sich am Eingang Halifaxstr. des Informatikzentrums (Ahornstr. 55).
Die Übungen werden in wöchentlichen Kleingruppen besprochen, die von Dienstag bis Freitag zu verschiedenen Terminen stattfinden. Die Termine der Gruppen entnehmen sie bitte der folgenden Tabelle oder im CampusOffice. Hier können Sie auch die Gruppen Nummer herausfinden.
Zu den Kleingruppen können sie sich hier anmelden. Ein Tausch mit einem anderen Studierenden ist nur nach beidseitiger Zusage und mit Information an uns (per Mail) möglich.

Gruppe Termin Raum
1 Mi, 12:15 – 13:45 Uhr SG 422
2 Di, 8:15 – 9:45 Uhr BS 218
3 Di, 16:15 – 17:45 Uhr BS 312
4 Di, 16:15 – 17:45 Uhr 5054
5 Di, 18:15 – 19:45 Uhr 5055
6 Di, 18:15 – 19:45 Uhr 5052
7 Mi, 8:15 – 9:45 Uhr 5055
8 Mi, 10:15 – 11:45 Uhr 5055
9 Mi, 12:15 – 13:45 Uhr 5054
10 Mi, 12:15 – 13:45 Uhr 5055
11 Mi, 14:15 – 15:45 Uhr 5052
12 Mi, 14:15 – 15:45 Uhr 5054
13 Do, 8:15 – 9:45 Uhr 5054
14 Do, 8:15 – 9:45 Uhr 5055
15 Do, 18:15 – 19:45 Uhr 5056
16 Fr, 17:15 – 18:45 Uhr 5056
17 Do, 17:15 – 18:45 Uhr 5054
18 Do, 8:15 – 9:45 Uhr 5056
19 Fr, 17:15 – 18:45 Uhr 5055
20 Fr, 17:15 – 18:45 Uhr 5054

 

Bitte beachten Sie, dass für die Zulassung zur Klausur eine erfolgreiche Teilnahme (mindestens 33% in den Übungen vor der Präsenzübung und mindestens 33% in den Übungen nach der Präsenzübung) an den Übungen nötig ist. Es wird Bonusaufgaben geben (mit * gekennzeichnet), welche mit Zusatzpunkten versehen sind (diese Aufgaben müssen also nicht bearbeitet werden, Punkte daraus gehen aber positiv auf das Punktekonto ein).

Das letzte Übungsblatt wird eine Probeklausur sein, welche mit einer Musterlösung ausgegeben wird (diese fließt nicht in die Bewertung ein)

Nr. Ausgabe Abgabe Übung Musterlösung Lösung Tutorien
1 21.04.2014 28.04.2014 Uebung1 Loesung1 Loesung-Tutoraufgaben1
2 28.04.2014 05.05.2014 Uebung2 Loesung2 Loesung-Tutoraufgaben2
3 05.05.2014 12.05.2014 Uebung3, Sourcecode Loesung3 Loesung-Tutoraufgaben3
4 12.05.2014 19.05.2014 Uebung4 Loesung4 Loesung-Tutoraufgaben4
5 19.05.2014 Praesenz-Uebung-2012   – Praesenz-Uebung-2012-Loesung
5 23.05.2014 23.05.2014 Praesenz-Uebung Praesenz-Uebung-Loesung   –
6 26.05.2014 02.06.2014 Uebung6 Loesung6 Loesung-Tutoraufgaben6
7 02.06.2014 16.06.2014 Uebung7 Loesung7 Loesung-Tutoraufgaben7
8 16.06.2014 23.06.2014 Uebung8 Loesung8 Loesung-Tutoraufgaben8
9 23.06.2014 30.06.2014 Uebung9 Loesung9 Loesung-Tutoraufgaben9
10 30.06.2014 07.07.2014 Uebung10 Loesung10 Loesung-Tutoraufgaben10
11 07.07.2014 14.07.2014 Uebung11 Loesung11 Loesung-Tutoraufgaben11
12 14.07.2014 21.07.2014 Uebung12 Loesung12 Loesung-Tutoraufgaben12

Zur Vorbereitung für die anstehende Klausur stellen wir die Klausur des Sommersemesters 2012 mit Lösung bereit.

Eine grafische Übersicht über die bis einschließlich Übung 12 erreichten Punkte finden Sie hier.

Die aktuelle Version 1.1.10 des Übungsaufgabengenerators finden Sie hier. Die zugehörige Lizenz ist hier einzusehen. Zum Ausführen dieses Programms ist eine vorherige Installation von Java (Version 7 oder höher) notwendig. Zum Starten einfach java -jar ExerciseCreator.jar <options>  eingeben. Ein Hilfetext zu den möglichen Optionen kann mit java -jar ExerciseCreator.jar -h  angezeigt werden. Das Programm erstellt LaTeX Dateien, die mithilfe des Programms pdflatex in PDF Dateien übersetzt werden können.

Präsenzübung

Während des Semesters 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 33% der Punkte) haben die Möglichkeit an der Wiederholungsübung teilzunehmen. Diese findet am Termin des ersten Klausurtermins statt. Studierende, die bei diesem Termin erfolgreich die Präsenzübung bestehen haben die Möglichkeit die Klausur am 2. 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, d.h. die Wiederholungsklausur umfasst den gesamten Vorlesungsstoff. Bitte beachten Sie, dass für die Zulassung zur Klausur eine erfolgreiche Teilnahme an der Präsenzübungen (33% der Punkte) nötig ist.

Die Hörsaalverteilung für die Präsenzübung ist wie folgt:

Hörsaal Matrikelnummern
AH IV 000000-321999
Aula 2 322000-331399
AM 331400-335299
FT 335300-999999

Bringen Sie Ihren Studentenausweis (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. Weitere Hilfsmittel sind nicht zugelassen. Papier wird von uns gestellt.

Die Ergebnisse der Präsenzübung sind als Übungsblatt 5 im Übungssystem einsehbar. Eine grafische Übersicht über das Ergebnis finden Sie hier.

Die Ergebnisse der zweiten Präsenzübung sind als Übungsblatt -1 im Übungssystem einsehbar. Eine grafische Übersicht über das Ergebnis finden Sie hier.

Klausurzulassung

Um die Klausurzulassung zu erwerben müssen 50% der Punkte aus den Übungen und der Präsenzübung erreicht werden (insgesamt) und in jedem Bereich (vor der PÜ, PÜ, nach der PÜ) mindestens 33%. Zulassungen aus vorherigen Semestern sind nur gültig, wenn bereits ein Prüfungsversuch stattgefunden hat.

Es gibt keine Ausgleichsregelungen.

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:

Bei einem Erreichen von über 75% (insgesamt) der Punkte gibt es einen Bonus von 0.3 (eine Notenstufe) auf das Klausurergebnis. Ausgeschlossen sind die Noten 1.0 und 5.0.

Am Ende des Übungsbetriebes erhalten die besten 10% der Studierenden außerdem eine Urkunde.

Klausur

Zur Teilnahme an der Klausur ist eine Anmeldung erforderlich. Alle Studenten müssen sich bis zum 23.05. im Campus zur Klausur anmelden.

Die Klausur wird über eine Dauer von 2 Stunden in Einzelarbeit geschrieben.
Als Hilfsmittel ist neben dokumentenechten Stiften ausschießlich ein DIN A4 Blatt, das beidseitig mit Notizen (handschriftlich oder gedruckt) versehen sein darf, 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 über das Notizblatt hinaus 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 die selbe Regelung bezüglich der Hilfsmittel.

Die Hörsaalverteilung für die erste Klausur und die zweite Präsenzübung lautet wie folgt:

Hörsaal Matrikelnummern
Gr 000000-320999
Fo 2 321000-330999
AM 331000-333399
Ro 333400-334799
Aula 1 334800-999999
AH V Präsenzübung

Die Ergebnisse der beiden Klausuren sind im Übungssystem unter der Übungsübersicht einzusehen. Das Notenschema lautet wie folgt:

114-120 1.0
108-113.5 1.3
102-107.5 1.7
96-101.5 2.0
90-95.5 2.3
84-89.5 2.7
78-83.5 3.0
72-77.5 3.3
66-71.5 3.7
60-65.5 4.0
0-59.5 5.0

Eine grafische Verteilung der Punkte bei der ersten Klausur finden Sie hier. Eine grafische Verteilung der Noten bei der ersten Klausur finden Sie hier (mit Bonus und ohne Bonus). Die grafischen Übersichten für die erste Klausur nach der Einsicht finden Sie hier: Punkteverteilung nach Einsicht, Notenverteilung nach Einsicht (mit Bonus) und Notenverteilung nach Einsicht (ohne Bonus).

Die Hörsaalverteilung für die zweite Klausur lautet wie folgt:

Hörsaal Matrikelnummern
Fo1 000000-999999

Eine grafische Verteilung der Punkte bei der zweiten Klausur finden Sie hier. Eine grafische Verteilung der Noten bei der zweiten Klausur finden Sie hier (mit Bonus, ohne Bonus). Die grafischen Übersichten für die zweite Klausur nach der Einsicht finden Sie hier: Punkteverteilung nach Einsicht, Notenverteilung nach Einsicht (mit Bonus) und Notenverteilung nach Einsicht (ohne Bonus).

Die Klausur vom 5.8.2014 und deren Lösung, die Präsenzübung vom 5.8.2014 und deren Lösung sowie die Klausur vom 15.9.2014 und deren Lösung sind zur zusätzlichen Vorbereitung in späteren Semestern hier erhältlich.

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

Florian Corzilius, Stefan Schupp, Thomas Ströder

E-Mail

dsal14@i2.informatik.rwth-aachen.de