Gedächtnisprotokoll AD08-1

Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.

Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.

Multiple-Choice Teil

• Hashing
• P/NP

asymptotische Laufzeiten

Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)

Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)
Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.

Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)

Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).

Suchen

Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.

Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?

Quicksort

Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt

• Zeigen Sie, dass eine Vertauschung von A[j] und A[j+1] mit A[j] > A[j+1] diese Eigenschaft nicht zerstört.
• Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)

Hashing

Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an.

Bäume

Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.

Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.

Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))

Gegeben: Ein Heap. Entfernen Sie das grösste Element (Heap-Extract-Max) und geben Sie den Heap nach der Operation an.

Graphen

Dijkstras Algortitmus anwenden.

Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle < 100%). Gesucht ist der Weg mit dem geringsten Verlust.

• Warum kann der optimale Pfad keine Zyklen enthalten?
• Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?
• Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.

Geben die folgenden Algortithmen einen MST (minimal-spanning-tree) zurück?

• Alg 1
  • initialisiere T mit der Leeren Menge
  • für jede Kante x tue
    • Wenn T vereinigt x Zyklenfrei
      • T <- T vereinigt x

• Alg 2
  • initialisiere T mit der Kantenmenge
  • für jede Kante x sortiert von gross nach klein tue
    • Wenn T ohne x verbunden
      • T <- T ohne x

Dynamische Programmierung

Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen

• Randbedingungen formulieren
• Rekursionsgleichung formulieren
• Algorithmus implementieren
• Laufzeit?