Grundlagen: Algorithmen und Datenstrukturen

Administrativa

Vorlesung mit Übungen für Bachelor-Studierende (IN0007).

  • Organisatoren:
  • Kontakt:
  • Termine:
    • Vorlesung: Dienstags, 14:15 - 15:45, MW 2001
    • Vorlesung: Mittwochs, 13:20 - 14:05, MW 2001
    • Übungen: in Gruppen, siehe TUMonline und Moodle
  • Erste Vorlesung: 26. April 2022
  • Prüfungen:
    • reguläre Prüfung: 23. Juli 2022, 9:15 - 10:45
    • Wiederholungsprüfung: 12. Oktober 2022, 11:00 - 12:30
  • Kurssprache: Deutsch

Inhaltsübersicht

  • Grundlagen Algorithmen und Datenstrukturen
  • Komplexitätsanalyse (Effizienmaße, Landau-Symbole, Maschinenmodell)
  • Datenstrukturen für Sequenzen (Arrays, Listen, Stacks, Queues)
  • Hashing (Verkettung, universelles Hashing, Sondierverfahren, perfektes Hashing)
  • Sortieren (SelectionSort, InsertionSort, MergeSort, QuickSort, untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort, externes Sortieren)
  • Priority Queues (binäre Heaps, Binomialheaps)
  • Suchstrukturen (binäre Suchbäume, AVL-Bäume, (a,b)-Bäume)
  • Graphen (Repräsentationen, Traversierung mit BFS und DFS, Zusammenhang, topologische Sortierung, kürzeste Wege, minimale Spannbäume)
  • Pattern Matching (naive Suche, KMP Algorithmus)
  • optional: Datenkompression (Huffman Codes, Lempel-Ziv Verfahren)

Kursmaterialien

Alle Materialien werden über Moodle bereitgestellt (Zugang beschränkt auf Kursteilnehmer, Registrierung via TUMonline).
Zur Kontaktaufnahme benutzen Sie bitte die Chat-Plattform https://zulip.in.tum.de, stream #GAD-Allgemein.