Grundlagen: Algorithmen und Datenstrukturen

Administrativa

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

• Organisatoren:
  • Vorlesungen: Tobias Lasser
  • Übungen: Theodor Cheslerean-Boghiu, Thomas Friedrich, Erdal Pekel, Lukas Stevens
• Kontakt:
  • Chat-Plattform https://zulip.in.tum.de, stream #GAD-Allgemein
  • in Ausnahmefällen: via Email
• 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.