News
- 12.9.2018: Die Ergebnisse der 2. Klausur sind ab sofort im Übungssystem einsehbar. Die Einsicht zur 2. Klausur findet am Montag 17.9.2018 im AH 1 (Informatikzentrum) statt. Bringen Sie ihre BlueCard zur Einsichtnahme mit. Die Uhrzeit hängt von Ihrer Matrikelnummer ab:
000000-377999: 13:00 Uhr bis 14:00 Uhr
378000-999999: 14:00 Uhr bis 15:00 UhrFalls Sie die Klausur im dritten Versuch nicht bestanden haben und eine Ergänzungsprüfung wünschen, muss diese spätestens während der Einsicht schriftlich beantragt werden.
- 6.9.2018: Die zweite Klausur findet am 10.9. im für alle angemeldeten Studierenden im Großen Hörsaal (Audimax) statt. Einlass ist ab 10:15 Uhr, die Klausur beginnt pünktlich um 10:30 Uhr. Bitte bringen Sie ihren Studierendenausweis und dokumentenechte Stifte mit. Als Hilfsmittel ist ein handbeschriebenes A4 Blatt (Vorder- und Rückseite) zugelassen.
- 21.8.2018: Die Einsicht zur 1. Klausur bzw. 2. Präsenzübung findet am 23.8.2018 im AH 1 (Informatikzentrum) statt. Bringen Sie ihre BlueCard zur Einsichtnahme mit. Die Uhrzeit hängt von Ihrer Matrikelnummer ab:
000000-369999: 14:30 Uhr bis 15:15 Uhr
370000-377999: 15:15 Uhr bis 16:00 Uhr
378000-999999: 16:00 Uhr bis 16:45 UhrBeachten Sie, dass Sie nicht automatisch zum zweiten Klausurtermin angemeldet werden. Wenn Sie an der zweiten Klausur teilnehmen möchten, müssen Sie sich selbst über das VZPA anmelden. Falls Sie die Klausur im dritten Versuch nicht bestanden haben und eine Ergänzungsprüfung wünschen, muss diese spätestens während der Einsicht schriftlich beantragt werden.
- 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 | |
|---|---|---|---|
| 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.
| 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 | Rekursionsgleichungen | 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 Graphenalgorithmen | 15.6.2018 | l14+15_handout | l14+15_folien | notizen14+15 |
| 15 | Elementare Graphenalgorithmen | 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:
- Mindestens 50% aller in den Übungen erreichbaren Punkte bis zur Präsenzübung (d.h. Blatt 1 bis einschließlich Blatt 6)
- Mindestens 50% aller in den Übungen erreichbaren Punkte ab der Präsenzübung (d.h. ab Blatt 7)
- 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