AlgoDatKlausur SS2018 
Datum: 8.8.18

-Theoriefragen (waren zum Ankreuzen); bitte kreuzen Sie bei den folgenden Fragen alle Antworten an, die zutreffen. Es ist immer mindestens eine Antwort richitg und mindestens eine Antwort falsch.

1. Welche Laufzeit hat Dijkstra?
O(E log V)
O(V log E)
O(E)

2. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie
Schlüssel möglichst gleichmäßig abbildet. 
Universelles Hashing wird dazu verwendet, Kollisionen zu vermeiden
//ein paar weitere Antworten

-Hashing: Gegeben seien die folgenden Zahlen(Zahlen können abweichen)
	  Zahl	h(Zahl)
	A 2     leer
	B 6     leer
	C 4     leer
	D 5     leer
	E 1     leer
	F 3     leer

und die Hashfunktion h=
Berechnen Sie die Hashwerte dieser Zahlen mithilfe von h und fügen Sie sie in die Spalte der Tabelle ein.

Fügen Sie die Zahlen gemäß der linearen Sondierung mit Inkrementierung in der oben gegebenen Reihenfolge in die unten stehende Hashtabelle ein. 

//Hashtabelle mit 6 Spalten 

Welche der folgenden Hashtabellen könnte entstehen durch Einfügen der oben gegebenen Werte in beliebiger Reihenfolge?

//3 ausgefüllte Hashtabellen

-Java:
Die Klassen Bicycle und Car erben von der Klasse Vehicle.
Ergänzen Sie die Lücken im Quellcode(einzufügen war "extends", "public abstract class", "public class".

Das folgende Programm wird ausgeführt. Was wird ausgegeben?
//ein Bicycle und zwei Car wurden in einem Array erzeugt und je eine Methode aufgerufen, die Zahlen ausgibt.

Was wird jetzt ausgegeben? //Es wurde auf 4.Zeile im Array zugegriffen, obwohl das Array nur 3 hat

Was wird jetzt ausgegeben? //Es wurde auf ein uninitialisiertes Array von Vehicle zugegriffen

-Kruskal: Graph gegeben mit allen Kanten gewichtet, aber 3 Kanten mit Gewicht x,y,z

Welches Gewicht dürfen die Kanten X,Y,Z maximal haben, damit sie auf jeden Fall ausgewählt werden?
Geben Sie eine obere Schranke an.

-Dijkstra: Graph gegeben
Führen Sie den Dijkstra-Algorithmus durch. Fügen Sie in die unten stehende Tabelle die Werte der kürzesten Wege zu den einzelnen Knoten ein.

//Tabelle 
A B C D E F G H I J

Zeichnen Sie in den unten stehenden Graphen die kürzesten Wege zu den Knoten ein

//gleicher Graph

-Edmonds-Karp: //Flussgraph gegeben, bei dem bereits ein paar Iterationen angewendet wurden

Zeichnen Sie den Pfad ein, den Edmonds-Karp in der nächsten Iteration findet.

Welches ist der maximale Fluss?
F=

Wie groß ist die Kapazität des minimalen Schnittes?

-Dynamische Programmierung: Palindrom: Wort, das vorwärts und rückwärts gleich ist; gesucht: Algorithmus, der die Anzahl der Palindrome in einem Wort erkennt

a) Welche Laufzeit hätte der Brute-Force-Ansatz (alle Möglichkeiten ausprobieren)?

Musterantwort: O(n^3)

b) Entwickeln Sie eine Rekursionsgleichung, die die Anzahl an Palindromen in einem Wort ermittelt.

c) Welche Laufzeit hätte der Algorithmus mit dynamischer Programmierung (Hinweis: Diese Aufgabe lässt sich unabhängig von b lösen)?