Algorithmen und Datenstrukturen 1

ALGO1 · SoSe-2021

Overview

Klausur

Allgemeine Informationen

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.

Literatur

Wochenplan

Die Veranstaltung dauert 14 Wochen:

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

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

  3. Analyse von Algorithmen, Asymptotische Notation, Rekursionsgleichungen, Mastertheorem · a
    CLRS Kapitel 3, 4.3-4.5 · Plan · · 📽️ · 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 · · 📽️ · Folien

  5. Darstellung von Graphen, Breitensuche, Tiefensuche · b
    CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Plan · · 📽️1 · 📽️2 · 📽️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 · · 📽️1 · 📽️2 · Folien

  7. Prioritätswarteschlangen, Heaps · a
    CLRS Kapitel 6 + Appendix B.5 · Plan · · 📽️1 · 📽️2 · 📽️3 · Folien

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

  9. Minimale Spannbäume: Jarník–Prims Algorithmus, Kruskals Algorithmus · b
    E Kapitel 7 (oder CLRS Kapitel 23) · Plan · · 📽️1 · 📽️2 · 📽️3 · 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 · · 📽️1 · 📽️2 · 📽️3 · Folien

  11. Wörterbücher, Hashing · a
    CLRS Kapitel 11 ohne 11.5 · Plan · · 📽️1 · 📽️2 · Folien · cuckoo hashing

  12. Traversierung, binäre Suchbäume, AVL-Bäume · a
    CLRS Kapitel 12 ohne 12.4 · Plan · · 📽️1 · 📽️2 · 📽️3 · Folien

  13. Dynamische Programmierung, Fibonacci, längste gemeinsame DNA-Teilsequenz, Teilmengensumme, DP auf Bäumen · b
    E Kapitel 3 ohne 3.6 und 3.9 · Plan · · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien

  14. Greedy-Algorithmen, Scheduling, Huffman-Codierungen · b
    E Kapitel 4 · Plan · · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · 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:

Verwandte Vorlesungen

Zusätzliche Literatur

Weitere Hinweise