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 poll Operationen schon Theta(log n) Zeit brauchen (es wird nach jedem poll das letzte Element an die Wurzel gesetzt, und weil dieses das größte ist, muss man es wieder ganz nach unten durchsickern lassen, und das dauert für die ersten n/2 Operationen jeweils Theta(log (n/2)) = Theta(log n) Zeit).

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) = 2, dist(u_{n+1}) = 1
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 aus der Summe herausziehen.
Das ist = 1/2 * n * (n - 1) + n ... nach Induktionsvoraussetzung für die Summe.
Das ist = n * (1/2 * (n - 1) + 1) = n * 1/2 * (n - 1 + 2) = 1/2 * n * (n + 1) ... durch einfache Umformung.

4.4 Programm erklären + Laufzeit

In der i-ten Iteration der äußersten Schleife, i = 0, ..., n - 1, wird einfach das größte Element aus dem Bereich von 0 bis n - 1 - i an die Stelle n - 1 - i getauscht. Effektiv sortiert das Progamm damit. Zum Beispiel: 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)