Algorithmen und Datenstrukturen 1

ALGO1 · SoSe-2021

Overview

Allgemeine Infos

Der Kurs findet nur synchron und vollständig online statt, und ist didaktisch so konzipiert, dass Student:innen in kleinen Gruppen gemeinsam Übungsaufgaben diskutieren und währenddessen individuell von einem freundlichen und kompetenten Team betreut werden.

Ort und Zeit

Anmeldung

Bitte melden Sie sich in Moodle an.

Dozent

Tutor:innen

Voraussetzungen

Sie brauchen für den Kurs Basisfähigkeiten im Programmieren sowie grundlegende mathematische Fähigkeiten. Mit diesem Selbsttest können Sie vorab Ihre Fähigkeiten prüfen und auffrischen.

Buch

CLRS: Algorithmen – Eine Einführung (4. Auflage) von Cormen, Leiserson, Rivest, Stein. [Volltext als E-Book]

Wochenplan

Die Veranstaltung dauert 14 Wochen, die Pläne sind vorläufig:

  1. Einführung und Peaks · a
    CLRS Kapitel 1 · Plan · · Video · Folien · Organisationsfolien

  2. Suchen und Sortieren · a
    CLRS Kapitel 2 · Plan · · Video 1 · Video 2 · Folien

  3. Analyse von Algorithmen, Asymptotische Notation, Rekursionsgleichungen, Mastertheorem · a
    CLRS Kapitel 3, 4.3-4.5 · Plan · · Video · Folien · experiment.py · Lagebesprechung

  4. Elementare Datenstrukturen: Stapel, Warteschlangen, Verkettete Listen, Bäume · a
    CLRS Einleitung von Teil III und Kapitel 10, Kapitel 17.4 bis Mitte von 17.4.1 · Plan · · Video · Folien

  5. Darstellung von Graphen, Breitensuche, Tiefensuche · b
    CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Plan · ☆ · Video 1 · Video 2 · Video 3 · Folien

  6. Gerichtete Graphen, Suche, Topologisches Sortieren, Starke Zusammenhangskomponenten · b
    CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Plan · ☆ · Video · Folien

  7. Prioritätswarteschlangen, Heaps · a
    CLRS Kapitel 6 + Appendix B.5 · Plan · ☆ · Video · Folien

  8. Disjunkte Mengen, Union-Find · a
    CLRS Kapitel 21 ohne 21.4 (oder Algorithms 4ed. Kapitel 1.5) · Plan · ☆ · Video · Folien

  9. Minimale Spannbäume: Borůvkas Algorithmus, Jarník–Prims Algorithmus, Kruskals Algorithmus · b
    E Kapitel 7 (oder CLRS Kapitel 23) · Plan · ☆ · Video · Folien

  10. Dijkstras Algorithmus, kürzeste Wege · b
    E Kapitel 8 ohne 8.7 (oder CLRS Kapitel 24 außer 24.1 und 24.4) · Plan · ☆ · Video · Folien

  11. Wörterbücher, Hashing · a
    CLRS Kapitel 11 ohne 11.5 · Plan · ☆ · Video · Folien

  12. Traversierung, binäre Suchbäume, AVL-Bäume · a
    CLRS Kapitel 12 ohne 12.4 · Plan · ☆ · Video · Folien

  13. Greedy-Algorithmen, Scheduling, Huffman-Codierungen · b
    CLRS Kapitel 16 bis 16.3 · Plan · ☆ · Video · Folien

  14. Dynamische Programmierung, längste gemeinsame DNA-Teilsequenz · b
    CLRS Kapitel 15.4 · Plan · ☆ · Video · Folien

Übungen

Alleine ein Buch lesen oder Videos anschauen können Sie auch ohne diesen Kurs. Mit 1–2 anderen Student:innen zusammen Übungsaufgaben bearbeiten, und dabei unsere Unterstützung und unser Feedback erfahren, das sind die Qualitäten, die Sie ohne diesen Kurs nicht haben. Daher sind Übungen und die Möglichkeit zum direkten mündlichen Gespräch mit Tutor:innen oder dem Dozenten das zentrale Angebot dieses Kurses.

Manche Übungsaufgaben sind besonders, denn sie sind mit ⭐ markiert. Diese Aufgaben lösen Sie außerhalb des Synchronbetriebs und geben sie als PDF-Datei ab; fotografieren Sie hierzu Ihre lesbare Handschrift mit einer Scanner-App oder benutzen Sie solution-template.tex. Sie erhalten nützliches Feedback von den Tutor:innen auf Ihre Lösung, und Ihre Lösung wird anhand objektiver Kriterien entweder akzeptiert oder nicht akzeptiert. Wenn Ihre Lösung akzeptiert wird, erhalten Sie einen Stern ⭐, der möglicherweise Ihre Klausurnote verbessert. ⭐-Aufgaben verfolgen zwei Ziele: 1) Sie lernen, im sozialen Rahmen einer kleinen Gruppe Algorithmen für Ihnen vorher unbekannte algorithmische Probleme selbst zu entwickeln und zu analysieren. 2) Indem Sie die Lösung aufschreiben, verfassen Sie dadurch einen kurzen, wissenschaftlichen Text, und lernen dabei, die wissenschaftliche Sprache der Algorithmenforschung korrekt zu benutzen. Beide Aspekte sind wichtig und ergänzen sich gegenseitig, Sie sollten daher für Beides genügend Zeit einplanen. Folgende Regeln sind verpflichtend zu beachten:

Klausur

Die Klausur ist die einzige verpflichtende Komponente des Moduls B-ALGO1. Umfang, Schwierigkeit und Themen der Klausuren orientieren sich stark an den Vorjahren.

Falls Sie die Klausur bestehen, erhöhen gesammelte ⭐ Ihr Klausurergebnis um bis zu 10 %. Das heißt, eine mit 50 % der Punkte gerade so bestandene Klausur kann im besten Fall als 60 % gewertet werden, aber eine mit 49 % nicht bestandene Klausur bleibt nicht bestanden. Der Bonus berechnet sich als 10 % * #(von Ihnen gesammelte ⭐) / #(insgesamt verfügbare ⭐).

Verwandte Vorlesungen

Zusätzliche Literatur

Weitere Hinweise