Archiv von discourse.mafiasi.de vom Saturday September 21, 2019.

AD Klausur Gedächnisprotokoll

13schuett

Hey Leute,

ich würde gerne zu der AD ein Gedächnisprotokoll anlegen (ja, bisschen spät, hab schon viel vergessen), aber deshalb wollte ich fragen ob jemand helfen könnte und sich auch noch an Aufgaben erinnert, oder heute bei der Klausureinsicht war und deshalb die Aufgaben noch vor Augen hat.

Das fällt mir noch ein, was dran kam:

  • A* Search anweden,
  • Bellman Ford anwenden, wie ist das da mit negativen Zyklen?
  • wie wirken sich negative Zahlen bei Dijkstra auf?
  • Heap: Insert (8 Zahlen in Heap wandeln)und ExtractMax?, in Array-Schreibweise aufschreiben
  • Induktionsbeweis:
  • bei drei kleinen Algorithmen die Laufzeit bestimmen, mit oder ohne Master-Theorem, angeben ob man es anwenden kann oder nicht
  • bei zwei Algorithmen die Laufzeit möglichst exakt bestimmen (zB for i = 1 to n, for j= i to n sum = sum + 1, j = 3^i)
  • Führe folgende Operationen auf einer Queue aus: Insert(7), Delete, Insert(5),..., wie in Probeklausur
  • BFS
  • entwickle einen Algorithmus, der einen MaximumSpanningTree aufspannt
  • entwickle eine Algorithmus, der mittels UnionFind Data Structures Zusammenhangskomponenten in einem Graph berechnet

Wär cool, wenn jemandem noch mehr einfällt.

13fischer

Es gab doch noch irgendeine Aufgabe mit einem Sortieralgorithmus, bei dem man

a) die Invariante bestimmen sollte, b) beweisen sollte, weshalb die Invariante korrekt ist und c) erklären sollte, ob der Algorithmus stabil ist und weshalb (nicht).

Hauke

Die Insert und Extract Operationen sollte man auf einem Stack ausführen.

Außerdem war da noch

  • Querbeet-Fragen
  • Prim-Alogrithmus

  • Kruskal anwenden

  • Tiefensuche

  • Insertionsort in Place , Invariante bestimmen, Code war gegeben

  • Nullsummenproblem, Dynamische Progrogrammierung

  • Binärbäume, Suchbaum