Die Anmeldung zu den Übungsgruppen ist ab sofort bis zum 18.4. 23:55 geöffnet. Sie finden die Anmeldung hier.
Die Termine und Räume für die Tutorien finden Sie hier.

Wir gehen davon aus, dass Sie zu Terminen zu denen Sie sich anmelden auch Zeit haben. Ein nachträglicher Wechsel der Übungsgruppe ist nicht vorgesehen.

Die Zuteilung findet dann am 19.4. Die ersten Tutorien werden in der Folgewoche stattfinden. Den genauen Termin werden wir rechtzeitig bekannt geben.

Algorithmen und Datenstrukturen 1 (SS 2024)

Vorlesung

Prof. Dr. Ulrich Meyer

LSF

Dienstag 08:00 - 10:00 Hörsaal H V (Jügelhaus/Hörsaalgebäude)
Donnerstag 08:00 - 10:00 Hörsaal H V (Jügelhaus/Hörsaalgebäude)

Sprechstunde: Nach Vereinbarung

Übungsbetrieb

Alex Schickedanz
Daniel Allendorf

E-Mail: algo124@ae.cs.uni-frankfurt.de
Sprechstunde: Nach Vereinbarung

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen Abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).

Es gibt wöchentlich Übungsblätter. Die Abgabe des Blattes erfolgt online. Der genaue Ablauf wird rechtzeitig bekannt gegeben.

Sie können durch die Teilnahme an den Übungen bis zu 10 Bonuspunkte erhalten. Diese werden linear auf 10% der Klausurpunkte einer bestanden Klausur angerechnet.

Termine der Übungsgruppen

GruppeTagUhrzeitRaum
Gruppe 1Mo10-12NM 114
Gruppe 2Mo14-16NM 114
Gruppe 3Mo16-18NM 114
Gruppe 4Di10-12H 13
Gruppe 5Di14-16NM 113
Gruppe 6Di16-18NM 112
Gruppe 7Mi08-10NM 114
Gruppe 8Mi10-12NM 114
Gruppe 9Mi14-16H 13
Gruppe 10Mi16-18online
Gruppe 11Do12-14NM 114
Gruppe 12Do14-16NM 113
Gruppe 13Do16-18NM 113
Gruppe 14Fr10-12NM 120
Gruppe 15Fr12-14NM 120
Gruppe 16Fr16-18H 13

Hinweise zu den Übungsabgaben

  • Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
  • Wie immer gilt: Was unsere Tutoren nicht lesen können, müssen sie auch nicht korrigieren und gibt dementsprechend auch keine Punkte.
  • Da es eine online Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.
  • Wir stellen eine LaTeX Vorlage zur Verfügung.

Zur Onlineabgabe:

  • Die Abgabe wird Ihnen automatisch zugeordnet. Es schadet jedoch nicht Matrikelnummer und Namen darauf zu vermerken.
  • Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
  • Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
    • Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
    • Zur Not können Sie Scans oder Bilder zu einer PDF zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.

Plagiate und Betrugsversuche:

  • Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
    • … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf das Blatt.
    • … wird beim zweiten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt. Außerdem werden keine weiteren Abgaben der Beteiligten mehr korrigiert.
  • Wichtig: Wer bereits in einer unseren anderen Veranstaltung erwischt wurde, bekommt keine Verwarnung. In dem Fall wird die Bonifikation sofort aberkannt. Leider sehen wir uns zu diesem Schritt gezwungen nachdem die Zahlen der abgeschriebenen Lösungen in den letzten Semestern massiv angestiegen sind.
  • Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

Inhalt

Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die Analyse im Hinblick auf Laufzeit und Speicherplatzbedarf wird motiviert. Die asymptotische Notation wird eingeführt, und Methoden zur Lösung von Rekursionsgleichungen werden besprochen.

Elementare Datenstrukturen wie Listen, Keller und Warteschlangen werden beschrieben und analysiert. Der Begriff des abstrakten Datentyps wird eingeführt und motiviert, und effiziente Realisierungen der Datentypen des Wörterbuchs und der Prioritätswarteschlange unter Benutzung von Bäumen und Hashing werden besprochen. Außerdem werden effiziente Datenstrukturen für das Union-Find-Problem behandelt.

Die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen diskutiert. Weiterführende Algorithmen für Graphenprobleme wie minimale Spannbäume und kürzeste Wege werden besprochen, und der Einsatz von Datenstrukturen in diesen Verfahren wird exemplarisch vorgestellt.

Lernergebnisse / Kompetenzziele

Wissen und Verstehen: Die Studierenden sollen grundlegende Algorithmen und Datenstrukturen mit deren Eigenschaften und Leistungsparametern kennen und diese Parameter in asymptotischer Notation verstehen und vergleichen können

Können: Die Studierenden lernen, Datenstrukturen fur neue Problemstellungen eigenständig zu entwerfen und deren Leistungsparameter zu analysieren (instrumentale Kompetenz). Dadurch sollen sie im Beruf z.B. in der Lage sein, bestehende Software durch geeignetere Datenstrukturen zu beschleunigen (systemische Kompetenz).

Kommunikative Kompetenzen werden durch Arbeiten in Gruppenübungen und die dortige Vorstellung und Diskussion von Übungsaufgaben erworben.

Literatur

  • [CLRS] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. (Eng) MIT Press, 2002.
  • [GTM] Goodrich, Tamassia, Mount. Data Structures and Algorithms in C++. (Eng) Wiley & Sons, 2004.
  • [DMS] Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen: Die Grundwerkzeuge. Springer Vieweg, 2014.
  • [KT] Kleinberg, Tardos. Algorithm Design. (Eng) Pearson, 2006.
  • [S] Sedgewick. Algorithmen in C++. Pearson Studium, 2002.

Klausurtermine

Hauptklausur: Montag, 29.07.2024
Nachklausur: Mittwoch, 25.09.2024

Materialien

Folien

Videoaufzeichnungen

Folien zu den Videos

Altklausuren

Altklausuren finden Sie hier.

Übungsblätter

Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.

Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.

Beachten Sie auch die Hinweise zu Plagiaten und Betrugsversuchen.

Selbsttests

Selbststests sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können. Die PDF Dateien gibt es mit und ohne JavaScript Validierung. Um diese nutzen zu können, benötigen Sie einen entsprechenden Reader der das unterstützt, z.B. der Reader von Adobe. Die Version ohne JS sollte mit allen Readern funktionieren.

Skript

Es stehen Skripte von Herrn Prof. Dr. G. Schnitger zu Datenstrukturen und Theoretische Infromatik 1 zur Verfügung.

Hinweis: Mit der Zeit sollen die beiden Skripte neu aufgeteilt werden in Skripte für Algo1 und Algo2. Bis dahin sind hier noch die Skripte zu DS und GL1.