AUFGABE 1 (Hashing)

1.1 Hashtabelle für "ab", "aab", "aabb", "aabbb", "aaabbb"

h("ab") = 3 * 1 + 1 mod 4 = 0
h("aab") = 3 * 2 + 1 mod 4 = 3
h("aabb") = 3 * 2 + 2 mod 4 = 0
h("aabbb") = 3 * 2 + 3 mod 4 = 1
h("aaabbb") = 3 * 3 + 3 mod 4 = 0

0 -> "ab", "aabb", "aaabbb"
1 -> "aabbb"
2 -> [leer]
3 -> "aab"

1.2 Werte für h(x) alle gleich wenn n_a = n_b

Wenn n_a = n_b = n dann ist h(x) = 3 * n_a + n_b mod 4 = 4 * n mod 4 = 0.

1.3 Funktion zur Berechnung von h(x)

int hash(String x) {
  int na = 0;
  int nb = 0;
  for (int i = 0; i < x.length(); i++) {
    if (x.charAt(i) == 'a') na++;
    else if (x.charAt(i) == 'b') nb++;
    else return -1;
  }
  return (3 * na + nb) % 4;
}

1.4 H nicht 1-universell

H = {h1, h2}, wobei h1(x) = (3 * na + nb) mod 4 und h2(x) = (na + 3 * nb) mod 4.

Wenn H 1-universell wäre, dann müsste für jedes Schlüsselpaar x <> y gelten dass |{ h in H : h(x) = h(y)}| <= |H| / m = 1/2 < 1, d.h. keine der beiden Funktionen h1 und h2 dürfte die beiden Schlüssel auf dasselbe abbilden. Aber z.B. für x = "a" und y = "aaaaa" gilt sowohl h1(x) = h1(y) (beide = 3) als auch h2(x) = h2(y) (beide = 1).

AUFGABE 2 (Prioritätswarteschlangen)

2.1 Einfügen von 7, 6, 5, 4, 3, 2, 1

7     6     5         4         3          2           1
     /     / \       / \       / \       /   \       /   \
    7     7   6     5   6     4   6     4     3     4     2
                   /         / \       / \   /     / \   / \
                  7         7   5     7   5 6     7   5 6   3

2.2 Zustand nach Einfügen von x1, ..., x7 mit x1 < ... < x7

       x1   
     /    \
   x2      x3
  /  \    /  \
 x4  x5  x6  x7

2.3 Funktion zum Sortieren mittels Prioritätswarteschlange

int[] pqSort(int[] array) {
  int[] result = new int[array.length];
  PriorityQueue<int> pq;
  for (int i = 0; i < array.length; i++) {
    pq.add(array[i]);  // add = insert element into PQ. 
  }
  for (int i = 0; i < array.length; i++) {
    assert !pq.empty();
    result[i] = pq.poll(); // poll = get smallest element from PQ and remove it.
  }
  return result;
}

2.4 Laufzeit als Theta(...) wenn array bereits sortiert ist

Die erste Schleife (for ...) von der Funktion oben läuft in Theta(n), aber die zweite Schleife (while ...) braucht trotzdem Theta(n * log n), weil die ersten n/2 pops schon Theta(log n) Zeit brauchen.

Alternative: man kann die Funktion aus Aufgabe 2.3 auch so modifizieren, dass sie (mittels einer einfachen zusätzlichen Schleife am Anfang) in Theta(n) Zeit prüft, ob das Feld schon sortiert ist. Dann wäre die Antwort hier einfach Theta(n).

AUFGABE 3 (Dijkstra)

3.1 Dijkstra auf Wagenrad-Graph mit n = 5

Iteration 0:  dist(u_1) = 0, alle anderen noch unerreicht.
Iteration 1:  dist(u_2) = dist(u_5) = 3, dist(u_6) = 1, alle anderen noch unerreicht.
Iteration 2: dist(u_2) = dist(u_3) = ... = dist(u_5) = 2, dist(u_6) = 1.
Jetzt werden nacheinander u_2, ..., u_5 gesettled, ohne dass sich noch was ändert.

3.2 + 3.3 Für allgemeine n

Iteration 0:  dist(u_1) = 0
Iteration 1:  dist(u_2) = dist(u_n) = 3, dist(u_{n+1}) = 1
Iteration 2:  dist(u_2) = dist(u_3) = ... = dist(u_{n+1}) = 2
Jetzt werden nacheinander u_2, ..., u_n gesettled, ohne dass sich noch was ändert.

3.4 Durchmesser

Von jedem Knoten auf der Felge ist der maximale dist Wert 2, siehe Argument oben für Knoten 1 und für alle anderen Knoten auf der Felge ist es genauso (Symmetrie). Von der Nabe aus ist der maximale dist Wert 1. Also ist der Durchmesser genau 2.

AUFGABE 4 (O-Notation + Induktionsbeweis + Laufzeitbestimmung)

4.1 (log n)^k = O((log n)^{k+1})

(log n)^k <= C * (log n)^k * log n für C = 1 und n >= n0 = 2 (weil dann log n >= 1).

4.2 Nicht Theta

(log n)^k / (log n)^{k+1} = 1 / log n -> 0 für n -> unendlich. Für Theta müsste es aber > 0 sein, also kein Theta.

4.3 Induktionsbeweis für sum_{i=1}^n (n - i) = 1/2 * n * (n - 1)

Induktionsanfang n = 1:
Linke Seite = sum_{i=1}^1 (1 - i) = 0
Rechte Seite = 1/2 * 1 * (1 - 1) = 0.

Induktionsschritt n -> n+1:
sum_{i=1}^{n+1} (n + 1 - i) = sum_{i=1}^n (n + 1 - i) ... weil das letzte Glied in der Summe 0 ist.
Das ist = sum_{i=1}^n (n - i) + n ... einfach n mal +1 herausziehen
Das ist = 1/2 * n * (n - 1) + n ... nach Induktionsvoraussetzung für die Summe
Das ist = n * (1/2 * (n - 1) + 1) = 1/2 * n * (n - 1 + 2) = 1/2 * n * (n + 1) ... durch einfache Umformung

4.4 Programm erklären + Laufzeit

Das Programm sortiert in aufsteigender Reihenfolge. Z.b 3, 2, 1 -> 2, 1, 3 -> 1, 2, 3 Die Laufzeit ist Theta(sum_{i=1..n} (n-i)) und das ist nach Aufgabe 4.3 = Theta(1/2 * n * (n-1)) = Theta(n^2)