Gedächtnisprotokoll AD11-1

Klausur zu Algorithmen & Datenstrukturen, WS 10/11, 1. Termin, Dienstag, 15.02.2011

Es gab insgesamt 2 Varianten der Klausur, 100 Punkte, 9 Aufgaben und 120 Minuten Zeit. 
Kann gut sein, dass die Reihenfolge der Aufgaben etwas anders war. Die Punkte sind auch eher eine Abschätzung.

Aufgabe 1

Bei folgenden Fragen ist jeweils Ja/Nein anzukreuzen (1P) und zu begründen (2-3P).

a) <math>f(n) = \left\{\begin{matrix} n^{4} + 2^{7} \;\;mit\; n < 3^{10} \\ n^{3} + 2^{8} \;\;mit\; n \geq 3^{10} \end{matrix}\right .</math>

Ist <math>f(n) \in O(n^3)</math>?

b) Gilt <math>g \in \Theta(f) </math> genau dann, wenn <math>g \in o(f) </math> und <math>g \in \omega(f) </math> gilt?

c) Ist <math>o(f) \subseteq O(f) ?</math>

d) Ist <math>ln(n) \in O(\sqrt{n}) ? </math>

Aufgabe 2

Gegeben folgende Rekkurenzgleichung:

<math>T(n) = \left\{\begin{matrix} 0 \;\;\;\;\;\; n = 0 \\ 3T(n-1) + 2 \;\;\;\;\;\; n > 0 \end{matrix}\right.</math>

a) Geben Sie die Werte von T(n) an für n = 0, 1, 2, 3, 4

b) Bringen Sie die Gleichung durch die Substitutionsmethode in eine Darstellung ohne Summenzeichen (geometrische Reihe war im Anhang angegeben, Induktionsbeweis war nicht zu führen)

c) Hätte man auch das Master-Theorem anwenden können?

Aufgabe 3

Gegeben waren 2 Heaps (A und B) in graphischer Darstellung.

a) Geben Sie A in Array-Darstellung an.

b) Führen Sie die Operation ExtractMax an A aus und zeichnen Sie das Resultat.

c) Führen Sie an B die Operation IncreaseKey aus [es war ein Blatt, dessen Wert erhöht wurde] und zeichnen Sie das Resultat.

Aufgabe 4

a) Suchbaum gegeben. Fügen Sie die 19 ein [war ein Blatt] und löschen Sie die 25 [hatte 2 Kinder].

b) Warum braucht man Rot-Schwarz-Bäume?

Aufgabe 5

a) Wenden Sie Kruskals Algorithmus an und bestimmen sie einen MST (ähnlich zur Probeklausur; 5P)

b) Gegeben war ein gerichteter Graph. Geben sie mittels DFS eine topologische Sortierung des Graphen an. (2P)

c) Gegeben war ein Flussnetzwerk. Man musste wie in einer Iteration zunächst das Restnetzwerk zeichen, darin einen Erweiterungspfad finden und daneben eine weitere Zeichnung des neuen Flussnetzwerks machen (5P).

d) Mit welchem der folgenden Algorithmen kann man negative Zyklen in einem Graphen finden/erkennen? BFS, DFS, TopoSort, Bellman-Ford, Dijkstra, oder Edmond-Karps? (2P)

e) Was sind die Unterschiede und Gemeinsamkeiten zwischen den Algorithmen von Dijkstra, Bellman-Ford und Floyd-Warshall? (6P)

Aufgabe 6

a) Wann ist ein Algorithmus stabil? (1P)

b) Geben Sie die Worst-Case-Laufzeiten bei bester Implementierung an für Quicksort, Bubblesort, Mergesort und Heapsort (6P).

c) Was ist der Unterschied zwischen einem Stack und einer Queue? (2P)

d) Kommentieren Sie folgende Aussage: "Algorithmen sind auf Bäumen oft schneller als auf Arrays." (2P)

Aufgabe 7

...?

Aufgabe 8

Wieder einige Fragen zum Ankreuzen, manchmal mit Begründung.

a) Gehen Sie im Folgenden immer davon aus, dass P != NP.

• Ist <math>P \subseteq NP? </math>
• Ist <math>P \subseteq coNP? </math>
• Ist ...?

b) Folgt aus P = NP auch coP = coNP? (Mit Begründung, 2P)

c) Kann man ein Problem aus P immer auf ein NP-vollständiges Problem reduzieren? (Mit Begründung; 3P)

d) Sind alle Probleme in NP entscheidbar? Was ist mit den Problemen in coNP? (Mit Begründung; 4P)

Aufgabe 9

a) Angenommen P != NP. Ist folgendes Problem dann NP-schwierig: Gegeben ein Flussnetzwerk und eine natürliche Zahl k. Gibt es einen Schnitt mit einer niedrigeren Kapazität als k? (4P)

b) Polynomialzeitreduktion (5P). Gegeben:

1. Hamiltonkreis-Problem HC: Eingabe ungerichteter Graph. Gibt es einen Hamiltonkreis?

2. "Kreis"-Problem Gk: Eingabe ungerichteter Graph mit gewichteten Kanten und einem <math>k \in N</math>. Gibt es einen einfachen Kreis, dessen Kantengewicht-Summe über k liegt?

Das "Kreis"-Problem sei in NP. Zum Nachweis der NP-vollständigkeit reduzieren Sie HC auf Gk in Polynomialzeit.