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: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)
Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> 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: <math>f(n) = O(g(n))</math>. (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 <math>h(k,i) = h_1(k) + i * h_2(k)</math> mit <math>h_1(k) = k \mod m</math> und <math>k_2 = 1 + k \mod (m-1)</math>. 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?