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

Suchen

Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen

Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?

Quicksort

Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.

Bäume

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

Graphen

Dijkstras Algortitmus anwenden.

Einen Algoritmus scheiben + Laufzeit?

Dynamische Programmierung

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

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