AUFGABE 1 (Programmm + Laufzeitbestimmung)

1.1 Programm für zweitgrößte Zahl

def secondLargest(A):
    max1 = A[0]
    max2 = A[1]
    if max2 > max1:
        max1, max2 = max2, max1
    for i in range(2, len(A)):
        if A[i] > max2:
            if A[i] > max1:
                max2 = max1
                max1 = A[i]
            max2 = A[i]
    return max2

1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen

TODO

1.3 Funktion zur Berechnung von F_n in Zeit O(n)

def fastFibonacci(n):
    fibs = [1] * n
    for i in range(2, n):
        fibs[i] = fibs[i - 1] + fibs[i - 2]
    return fibs[n-1]

AUFGABE 2 (Felder + Hashing)

2.1 Suchen und Löschen eines Elementes aus einem Feld

def removeFromArray(A, x):
    i = 0
    while i < len(A) and A[i] != x:
        i = i + 1
    if i < len(A):
       A[i], A[-1] = A[-1], A[i]
       A.pop()

2.2 Löschen eines Elementes aus einer Hashtabelle

def removeFromHashTable(T, h, x):
    removeFromArray(T[h(x)], x)

AUFGABE 3 (Binäre Heaps)

3.2 Funktion zur Überprüfung der Heapeigenschaft

def checkHeapProperty(heap):
    for i in range(2, len(heap)):
        child_value = heap(i)
        parent_value = heap(i/2)
        if child_value < parent_value:
            return False
    return True

AUFGABE 1 (Diverses)

1.1 log n = O(log^2 n) aber nicht Theta

Sei log der Logarithmus zur Basis 2. (Wir können die Basis beliebig wählen, weil sich log_b1 und log_b2 nur um einen (positiven) konstanten Faktor ln b1 / ln b2 untertscheiden, für b1, b2 > 1.

Für alle n >= 2 ist log n >= 2 und damit, log n <= (log n)², also gilt O mit n₀ = 2 und C = 1.

Falls Theta, müsste auch Omega sein, dann würde es C, n₀ geben, so dass für alle n >= n₀ gilt, dass log n >= C * log² n. Dann wäre aber log n <= 1/C für alle n >= n₀. Aber z.B. für n = max(n₀, 2^{1 + 1/C}) ist n >= n₀ und log n > 1/C. Es reicht auch als Argument, dass log n für hinreichend große n beliebig groß wird (wenn auch langsam).

1.2 Was macht das Programm das da steht

Es berechnet die Anzahl der verschiedenen Elemente im Eingabefeld. Begründung: zu Beginn nimmt man an, dass alle Elemente verschieden sind, dann wäre diese Anzahl = #Größe des Feldes. Dann geht man von links nach rechts durch, und immer wenn man ein Element findet, dass man schon mal gesehen hat, zieht man 1 ab.

1.3 Laufzeit im besten und schlechtesten Fall

Bester Fall: Theta(n). Begründung: das passiert z.B. wenn alle Elemente gleich sind. Dann bricht die innere Schleife immer schon nach dem ersten Durchlauf ab. Schneller als Theta(n) geht nicht, weil die äußere Schleife immer n mal durchläuft.

Schlechtester Fall: Theta(n²). Begründung: das passiert z.B. wenn alle Elemente verschieden sind. Dann läuft die innere Schleife immer ganz zum Ende und die Laufzeit ist proportional zu sum_{i=1,...,n} i = Theta(n²).

AUFGABE 2 (Hashing)

2.1 Zustand der Hashtabelle nach Einfügen von 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Für h(x) = x² mod 5 ist: h(1) = 1, h(2) = 4, h(3) = 4, h(4) = 1, h(5) = 0, h(6) = 1, h(7) = 4, h(8) = 4, h(9) = 1, h(10) = 0. Zustand der Hashtabelle also:

0 : 5, 10
1 : 1, 4, 6, 9
2 : nix
3 : nix
4 : 2, 3, 7, 8

2.2 Beweis, dass h(x + 5) = h(x)

h(x+5) = (x+5)^2 mod 5 
       = (x^2 + 10x + 5) mod 5
       = (x^2 mod 5) + (10x mod 5) + (5 mod 5)
       = x^2 mod 5 = h(x) 

Alternativ:

h(x+5) = (x+5)^2 mod 5
       = (((x+5) mod 5) * ((x+5) mod 5)) mod 4
       = ((x mod 5) * (x mod 5)) mod 5
       = x^2 mod 5 = h(x) 

2.3 Pr(h(x) = i) für i = 0, 1, 2, 3, 4

Nach 2.2 ist die Verteilung für einen zufälligen Schlüssel aus N dieselbe wie für einen zufälligen Schlüssel aus {1, 2, 3, 4, 5}. Und dafür ist:

Pr(h(x) = 0) = 1/5 ... nur die 5 wird auf 0 abgebildet
Pr(h(x) = 1) = 2/5 ... 1 und 4 werden auf 1 abgebildet
Pr(h(x) = 2) = 0   ... nix wird auf 2 abgebildet
Pr(h(x) = 3) = 0   ... nix wird auf 3 abgebildet
Pr(h(x) = 4) = 2/5 ... 2 und 3 werden auf 4 abgebildet

2.4 Additivität von Universalität

Sei m die Größe der Hashtabelle und x, y ein beliebiges Schlüsselpaar mit x != y. Dann

H1 c-universell => |{h in H1 : h(x) = h(y)|| <= c * |H1| / m
H2 c-universell => |{h in H2 : h(x) = h(y)|| <= c * |H2| / m

Da H1 und H2 disjunkt ist ein h aus H entweder in H1 oder in H2, und |H| = |H1| + |H2|, und somit

|{h in H : h(x) = h(y)}| = |{h in H1 : h(x) = h(y)}| + |{h in H2 : h(x) = h(y)}|
                        <= c * |H1| / m + c * |H2| / m
                         = c * |H| / m.

Und damit ist H auch c-universell.

AUFGABE 3 (Dynamische Felder)

3.1 Wann i-te Reallokation wenn c1 = 1 und immer Verdoppelung

Dann Größe nach i-ter Reallokation 2^i. Induktionsanfang i = 1: erste Reallokation beim Einfügen des zweiten Elemente. Größe vor der Reallokation 1, danach 2 = 2¹. Induktionsschritt i -> i + 1: Nach Induktionsvoraussetzung ist die Kapazität nach der i-ten Reallokation 2ⁱ. Es wird also das nächste Mal beim Einfügen des (2ⁱ + 1)-sten Elementes wieder realloziert, und dann auf 2 * 2ⁱ = 2ⁱ⁺¹.

3.2 Gesamtanzahl Blockoperationen bei Einfügen von n Elementen

#IOs bis zur ersten Reallokation: Theta(1)
#IOs von der i-ten Reallokation: Theta(2^i / B)
#IOs ab da bis zur (i+1)-ten Reallokation: Theta(2^i / B)
#IOs insgesamt also Theta(sum_{i=1}^k 2^i / B) = Theta(2^k / B) = Theta(n / B), k = #Anzahl Reallokationen

AUFGABE 4 (a,b-Bäume)

4.1 (2,3)-Baum nach Einfügen von 1, 2, 3, 4, 5, 6

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

4.2 Wann zum ersten Mal Tiefe 3

Nach dem Einfügen von 8. Begründung: dann bekommt die Wurzel zum ersten Mal 4 Kinder und muss aufgespalten werden.

4.3 Wann zum ersten Mal Tiefe 4

Nach dem Einfügen von 16. Begründung: der Baum für die Knoten 9, 10, 11, 12, 13, 14, 15, 16 sieht dann so aus wie der Baum für 1, 2, 3, 4, 5, 6, 7, 8 und die (nach 4.2 neue) Wurzel bekommt dann zum ersten Mal wieder vier Kinder und muss aufgespalten werden.

4.4 Amortisierte Kosten für n beliebige Operationen

Theta(n * log n), siehe Vorlesung 8b, Folie 12.

AUFGABE 5 (Graphen)

5.1 Dijkstra von S nach Z

Hier erst nochmal der Graph mit Buchstaben als Knotennamen (A, B, C, D, E, F, G, H, J). Startknoten ist A, Zielknoten ist G (nicht J).

A --1-- B --1-- C
|       |       |
2       2       2
|       |       |
D --1-- E --1-- F
|       |       |
2       2       2
|       |       |
G --1-- H --1-- J

Dann macht Dijkstra Folgendes:

Runde 1: dist[A] = 0 gelöst, dist[B] = 1, dist[D] = 2
Runde 2: dist[B] = 1 gelöst, dist[C] = 2 neu, dist[E] = 3 neu, dist[D] = 2 unverändert
Runde 3: dist[D] = 2 gelöst, dist[G] = 4 neu, dist[C] = 2 und dist[E] = 3 unverändert
Runde 4: dist[C] = 2 gelöst, dist[F] = 4 neu, dist[G] = 4 und dist[E] = 3 unverändert
Runde 5: dist[E] = 3 gelöst, dist[H] = 5 neu, dist[F] = 4 und dist[G] = 4 unverändert
Runde 6: dist[G] = 4 gelöst.

Bemerkung 1: man kennt den richtigen Wert für dist[G] zwar schon in Runde 4, aber aufhören darf man erst in Runde 6. Da sollte man dann aber auch aufhören.

Bemerkung 2: Man hat an zwei Stellen die Auswahl zwischen zwei Knoten für die nächste Runde. In Runde 3 könnte man statt D auch C lösen (beide dist = 2). In Runde 6 könnte man statt G auch erst F lösen (beide dist = 4), dann würde G erst in Runde 7 gelöst.

5.2 Programm zur Berechnung des Durchmessers

void computeDiameter(Graph G) {
  int maxSoFar = -INFINITY; 
  for (int i = 0; i < G.size(); i++) {
    int[] dist = computeDijkstra(G, i);
    for (int j = 0; j < G.size(); j++) {
      if (dist[j] != INFINITY && dist[j] > maxSoFar) { maxSoFar = dist[j]; }
    }
  }
  return maxSoFar;
}

AUFGABE 6 (String Matching)

6.1 Knuth-Morris-Pratt für T = BANANANENA und P = NANA

Vorberechnung für das Muster (Positionen hier 1 bis 4, nicht 0 bis 3, kann man aber machen wie man will):

1234
NANA
0012

Ausführung des Algorithmus (Positionen hier 1 bis 10, nicht 0 bis 9, kann man aber machen wie man will):

1234567890
BANANANENA
N
 N
  NANA     ... MATCH an Positionen 3 bis 6 in T, weiter in T ab Stelle 7 - P[4] = 5
    NANA   ... MISMATCH an Position 8 in T / 4 in P, weiter in T ab Stelle 8 - P[3] = 7
      NA   ... MISMATCH an Position 8 in T / 2 in P, weiter in T ab Stelle 8 - P[1] = 8
       N   ... ENDE, weil < |P| Positionen in T übrig

6.2 Anzahl Vergleiche des trivialen Algorithmus

14 Vergleiche, wenn der Algorithmus aufhört wenn <|P| Positionen in T übrig. Sonst 18 Vergleiche. Beide Lösungen OK.

1234567890
BANANANENA
N          1 
 N         1
  NANA     4
   N       1
    NANA   4
     N     1
      NA   2
-------------
       N   1
        NA 2
         N 1

6.3 Maximal viele Vergleiche beim trivialen Algorithmus

T = a...a (n mal), P = a...a (m mal). Dann an jeder Position m Vergleiche (mehr geht nicht). Insgesamt Theta(n * m).