Skizze der Lösungen zur Nachklausur zur Vorlesung "Informatik II: Algorithmen und Datenstrukturen" im SS 2017

Alle Angaben ohne Gewähr.

AUFGABE 1 (O-Notation, Laufzeitbestimmung, Programm), Korrektur: Claudius Korzen

1.1 (5 Punkte) sqrt(n^2) = O(2^n) aber nicht Theta(2^n)

1. L'Hôpital #1: lim n^2 / 2^n = lim 2n / (ln 2 * 2^n) = 2 / ln 2 * lim n / 2^n
2. L'Hôpital #2: lim n / 2^n = lim 1 / (ln 2 * 2^n)
3. Der zweite Grenzwert ist offensichtlich 0 für n gegen unendlich
4. Damit gilt O(...) aber nicht Theta(...)

1.2 (5 Punkte) Ausgabe der Funktion in einer 4 x 4 Tabelle

0  1  2  3
1  2  4  7
2  4  8 15
3  7 15 30

1.3 (5 Punkte) Beweisen oder widerlegen Sie T(n, n) = Theta(n^2)

1. Es gilt T(n, n) >= T(n - 1, n) + T(n, n - 1) >= 2 * T(n - 1, n - 1)
2. Damit T(n, n) >= 2^n und somit Omega(2^n)
3. Damit nach Aufgabe 1.1 sicher nicht Theta(n^2)

1.4 (5 Punkte) Funktion mit selber Ausgabe und Laufzeit O(n * m)

1. def ftw(n, m):
2.     matrix = [i for i in range(m + 1)]  
3.     for i in range(1, n + 1):
4.         matrix.append([i])
5.         for j in range(1, m + 1):
6.             matrix[i].append(matrix[i-1][j] + matrix[i][j-1])
7.     return matrix[n][m]

AUFGABE 2 (Hashing), Korrektur: Axel Lehmann

2.1 (5 Punkte) Cuckoo Hashing mit m = 4, h1(x) = x mod 4, h2(x) = x^2 mod 4, Operationen: insert(7), insert(3), insert(5)

insert(7) -> h1(7) = 3, h2(7) = 1 -> T = [x, x, x, 7]
insert(3) -> h1(3) = 3, h2(3) = 1 -> T = [x, 7, x, 3]
insert(5) -> h1(5) = 1, h2(5) = 1 -> T = [x, 5, x, 7] und für die 3 ist kein Platz mehr (Zyklus)

2.2 (5 Punkte) Funktion, die nachprüft, ob ein insert gelingen wird

1. def check_insert(T, x):
2.     i = h1(x), i0 = h(x)
3.     while True:    
4.         if T[i] = -1:
5.             return True
6.         x = T[i]
7.         i = h1(x) if h1(x) != i else h2(x)
8.         if i == i0:
9.             return False

2.3 (5 Punkte) Wahrscheinlichkeit, dass Pr(h1(x) = h2(x)) für zufällige natürliche Zahl x

1. h1(x) = 0, 1, 2, 3, 0, 1, 2, 3, ...
2. h2(x) = 0, 1, 0, 1, 0, 1, 0, 1, ...
3. h1(x) = h2(x) genau dann wenn x mod 4 = 0 oder x mod 4 = 1
4. Die Wahrscheinlichkeit ist also 1/2

2.4 (5 Punkte) Beweis oder Gegenbeispiel, dass H = {h0, ..., hm-1 } 1-universell, mit hi(x) = i

1. Sei m > 1 und x und y zwei beliebige Schlüssel mit x != y
2. Dann ist hi(x) = i = hi(y) für alle i
3. Damit ist |{h : h(x) = h(y)}| = |H|
4. Für 1-Universalität müsste |...| <= |H| / m sein
5. Also nicht 1-universell