Gedächtnisprotokoll AD09-1

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten).

Muss nicht richtig sein ;)

1. O-Notation

2. - Was ist wenn ein NP-schweres Problem in P liegt? - n^log2 7 in Theta(n^3)

3. NP Formale Sprache von Eulerkreis

4. Rekurrenzgleichung - T(0)=0, T(n) = 3T(n-1) + 3 - Was muss Abbildung von L->M machen damit es Reduktion ist?

5. Suchbäume - Kann ein RS-Baum ein AVL-Baum sein? - Alle Suchbäume von {1,2,3}

6. Stack/Queue/Array

7. Kruskal

8. Median/Mittelwert - schechtste Laufzeit von: Heapsort, Radixsort und Sortieren durch Auswahl

9. Heap - malen - Sind alle Heaps spezielle Suchbäume?

10. AVL - - Komplexität von Medianberechnung - rotieren