== 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 >= 1 und damit, log n <= (log n)^2^, also gilt O mit n,,0,, = 2 und C = 1.

Falls Theta, müsste auch Omega sein, dann würde es C, n,,0,, geben, so dass für alle n >= n,,0,, gilt, dass log n >= C * log^2^ n. Dann wäre aber log n <= 1/C für alle n >= n,,0,,. Aber z.B. für n = max(n,,0,,, 2^1 + 1/C^) ist n >= n,,0,, 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^2^). 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^2^).


== 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^2^ 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^1^.
Induktionsschritt i -> i + 1: Nach Induktionsvoraussetzung ist die Kapazität nach der i-ten Reallokation 2^i^. Es wird also das nächste Mal beim Einfügen des (2^i^ + 1)-sten Elementes wieder realloziert, und dann auf 2 * 2^i^ = 2^i+1^.

=== 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 [[http://ad-teaching.informatik.uni-freiburg.de/AlgoDatSS2013/vorlesung-8b.pdf#page=12|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).