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

Alle Angaben ohne Gewähr + hier wird sich in den nächsten Stunden noch einiges ändern.

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

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

sqrt(n) <= 1 * n für alle n >= 1. Daraus folgt sqrt(n) = O(n) mit C = 1 und n,,0,, = 1. (2 Punkte)

Angenommen sqrt(n) = Omega(n). Dann würde es C und n,,0,, geben, so dass für alle n >= n0 gilt: sqrt(n) >= C * n. Letzter Ausdruck impliziert n >= C² * n² (auf beiden Seiten quadrieren), darauf folgt 1 >= C² * n und somit n <= 1 / C². Das kann aber nicht sein für alle n >= n0. Also war die Annahme, dass sqrt(n) = Omega(n) falsch. Und damit ist sqrt(n) nicht Theta(n).

=== 1.2 (5 Punkte) Umformung von 2 hoch log_4 n ===

2 hoch (log,,4,,n) = (4 hoch (1/2)) hoch (log,,4,, n) = (4 hoch log,,4,, n) hoch (1/2) = n hoch 1/2 = sqrt(n)  

=== 1.3 (10 Punkte) Laufzeit für T(n) <= 2 * T(n/4) + A * sqrt(n) ===

Durch wiederholtes Einsetzen der Formel auf der rechten Seite (analog dazu, wie wir es in VL2a und für das ÜB2 gemacht haben), erhält man:

T(n)<<BR>>
<= 2 * T(n/4) + A * sqrt(n)<<BR>>
<= 2 * (2 * T(n/4^2^) + A * sqrt(n/4)) + A * sqrt(n) = 2^2^ * T(n/4^2^) + 2 * sqrt(n)<<BR>>
<= 2^2^ * (2 * T(n/4^3^) + A * sqrt(n/4^2^)) + 2 * sqrt(n) = 2^3^ * T(n/4^3^) + 3 * A * sqrt(n)<<BR>>
<= ...<<BR>>
<= 2^k^ * T(n/4^k^) + k * A * sqrt(n)

Für k = log,,4,, n enthält man T(n) <= sqrt(n) + log,,4,, n * A * sqrt(n) = Theta(sqrt(n) * log n)

== AUFGABE 2 (Programm, Laufzeitbestimmung, Hashing), Korrektur: Markus Näther ==

=== 2.1 (5 Punkte) Funktion num_unique, die Anzahl der verschiedenen Zahlen ausgibt ===

{{{
def num_uniq(elements):
    uniqs = {}
    for x in input:
        if x not in uniqs:
            uniqs[x] = 1
    return len(unqis.keys())
}}}

Wenn man len(...) nicht kannte, konnte man auch einfach explizit mitzählen.

=== 2.2 (5 Punkte) Laufzeit der Funktion num_unique aus Aufgabe 2.1 ===

Es gibt n Schleifendurchläufe. Annahme: das "not in" und das "uniqs[x] = 1" gehen amortisiert in Zeit Theta(1). Dann ist die Laufzeit insgesamt Theta(n).

=== 2.3 (5 Punkte) Erwartungswert der Ausgabe, falls Elemente zufällig aus {0, 1} ===

Pr(alle Elemente 0) = 2^^^-n^<<BR>>
Pr(alle Elemente 1) = 2^^^-n^<<BR>>
PR(der Rest) = 1 - 2 * 2^^^-n^<<BR>>

Nach der Definition des Erwartungswertes ist dann<<BR>>
E(Anzahl verschiede Elemente) = 1 * 2^^^-n^ + 1 * 2^^^-n^ + 2 * (1 - 2 * 2^^^-n^) = 2 * (1 - 2^^^-n^).

Für n = 3 ist das 1.75

== 2.4 (5 Punkte) 1-Universalität der gegebenen Klasse ==

Die Klasse hat nur 1 Element. Laut Definition ist sie dann 1-universell, wenn für jedes Schlüsselpaar x, y in U mit x != < gilt, dass |{h in H: h(x) == h(y)}| <= 1/m. Da unter h kein solches Schlüsselpaar kollidiert, ist die linke Seite = 0. Damit ist diese Klasse 1-universell.

<<BR>>
<<BR>>

== AUFGABE 3 (Potenzialfunktion), Korrektur: Björn Buchhold  ==

=== 3.1 (5 Punkte) Funktion binary_inc, die einen Binärzähler der Länge n, gegeben als Feld, hochzählt ===

{{{
def binary_inc(counter):
    for i in range(len(counter) - 1, -1, -1):
        if counter[i] == 1:
            counter[i] = 0
        else:
            counter[i] = 1
            return
    return
}}}

=== 3.2 (5 Punkte) Laufzeit von binary_inc als Theta(...) in Abhängigkeit von geeigneter Größe ===

Sei m die Anzahl Nullen "von rechts" (also bis zur ersten 1 bzw. n wenn alle 0) nach der Operation. Dann ist die Laufzeit gerade Theta(m). Begründung: die Schleife läuft von rechts nach links durch und in jeden Schleifendurchlauf wird das entsprechende Element auf 0 gesetzt und dann am Ende (falls nicht alle auf 0 gesetzt) eine 1 

=== 3.3 (5 Punkte) Gesamtlaufzeit von 2^n aufeinanderfolgenden Aufrufen ===

Sei Phi_i die Anzahl Nullen "von rechts" (wie oben) nach der i-iten Operation.<<BR>>
Fall 1: Phi,,i,, = 0. Dann hat die Operation einfach nur die letzte Stelle erhöht und die Kosten waren Theta(1) und das Potential hat sich um 1 geändert.<<BR>>
Fall 2: Phi,,i,, > 0. Dann ist T,,i,, = Theta(Phi,,i,,) gemäß Aufgabe 3.2 und vor der Operation stand an der letzten Stelle eine 1, also Phi,,i-1,, = 0.

In beiden Fällen ist T,,i,, <= A + B * (Phi,,i,, - Phi,,i-1,,), für geeignete A und B. Damit ist die Gesamtlaufzeit Theta(2^n^).

=== 3.4 (5 Punkte)  Gesamtlaufzeit, wenn bei einem anderen Zählerstand begonnen wird ===

Die Kosten sind identisch. Begründung: die Menge der Argumente, mit denen die Funktion aufgerufen wird, ist identisch. Nur die Reihenfolge ist eine andere.

<<BR>>
<<BR>>


== AUFGABE 4 (Bäume), Korrektur: Axel Lehmann ==

=== 4.1 (5 Punkte) Vollständiger binärer Baum der Tiefe 2 (3 Ebenen), der die Heapeigenschaft erfüllt, aber kein binärer Suchbaum ist ===

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

Begründung: Heapeigenschaft erfüllt (jeder Knoten ist größer als sein Elternknoten), aber kein binärer Suchbaum (zum Beispiel müsste für die Wurzel gelte: größer als linkes Kind, kleiner als rechtes Kind; das ist nicht der Fall).

=== 4.2 (5 Punkte) Vollständiger ternärer Baum der Tiefe 2 (3 Ebenen), mit Knoten von 1 bis 13 durchnummeriert ===

{{{
               1
        /      |      \
       2       3       4
     / | \   / | \   / | \
    5  6  7  8 9 10 11 12 13
}}}

=== 4.3 (5 Punkte) Anzahl Knoten in einem vollständigen ternären Baum in Abhängigkeit der Tiefe d ===

Nehmen wir an, die Wurzel ist auf Tiefe 0. Dann:<<BR>
Anzahl Knoten mit Tiefe 0: 1 = 3^^^0^<<BR>>
Anzahl Knoten mit Tiefe 1: 3 = 3^^^1^<<BR>>
Anzahl Knoten mit Tiefe 2: 9 = 3^^^2^<<BR>>
Usw.

Anzahl Knoten bei Gesamttiefe d: 3^^^0^ + 3^^^1^ + ... + 3^^^d^<<BR>>
Laut gegebener Formel ist das: (3^^^d+1^ - 1) / (3 - 1) = 1/2 * (3^^^d+1^ - 1)

=== 4.4 (5 Punkte) Indizes der Kinder und des Elternknoten für Knoten mit Index i ===

Indizes Kinder: 3i - 1, 3i, 3i + 1<<BR>>
Index Elternknoten: (i + 1) / 3 abgerundet 

<<BR>>


== AUFGABE 5 (Graphen), Korrektur: Niklas Schnelle ==

=== 5.1 (5 Punkte) Adjazenzlisten und Länge der kürzesten Wege ===

Die Adjazentlisten sehen so aus (wenn jede ungerichtete Kante, als Kante in beide Richtungen eingetragen wird):

u,,1,,: u,,2,,, u,,3,, ... u,,2,,: u,,1,,, u,,3,,, u,,4,, ... u,,3,,: u,,1,,, u,,2,,, u,,5,, ... u,,4,,: u,,2,, ... u,,5,,: u,,3,,

Die Längen der kürzesten Wege:

Für {u,,1,,, u,,2,,}, {u,,1,,, u,,3,,}, {u,,2,,, u,,3,,}, {u,,2,,, u,,4,,}, {u,,3,,, u,,5,,} : jeweils 1<<BR>>
Für {u,,1,,, u,,4,,}, {u,,1,,, u,,5,,}, {u,,2,,, u,,5,,}, {u,,3,,, u,,4,,} : jeweils 2<<BR>>
Für {u,,4,,, u,,5,,}: 3

=== 5.2 (5 Punkte) Funktion für Länge des kürzesten Weges zwischen u und v ===

{{{
def dist(adjacency_lists, u, v):
    visited = {}
    nodes = [(u, 0)]    
    while len(nodes) > 0:
        (x, dist) = nodes.pop(0)
        if x in visited: continue
        visited[x] = 1
        if x == v: return dist
        for y in adjacency_lists[x]:
           nodes.append((y, dist + 1))
}}}

Bemerkung: da der Graph zusammenhängend ist, wird v sicher erreicht und man braucht kein zusätzliches return am Ende.

=== 5.3 (5 Punkte) Laufzeit der Funktionen dist ===

Wie bei BFS wird jeder Knoten und jede Kante genau einmal angeschaut.<<BR>>
Die Laufzeit ist deshalb Theta(n + m).<<BR>>
Da der Graph zusammenhängend ist, und somit m >= n - 1, ist das Theta(m).<<BR>>

== AUFGABE 6 (String-Suche), Korrektur: Hannah Bast ==

=== 6.1 (10 Punkte) Funktion für vereinfachten Karp-Rabin mit Musterlänge 3 ===

{{{
def num_hits(T, P):
    if len(T) < 3: return 0
    w = 100 * T[0] + 10 * T[1] + T[2]
    p = 100 * P[0] + 10 * P[1] + P[2]
    hit_count = 0 
    for i in range(3, len(T)):
       if w == p: hit_count += 1
       w = 10 * (w % 100) + T[i]
    return hit_count
}}}

=== 6.2 (5 Punkte) Anzahl Blockoperationen der Funktion num_hits ===

Die Funktion geht einmal von vorne nach hinten durch das Feld der Länge n. Die Anzahl Blockoperationen ist von daher Theta(n / B).

=== 6.3 (5 Punkte) Erwartete Anzahl Treffer bei zufälligem Text und Muster ===

Sei I,,i,, = 1 genau dann wenn das Muster an Stelle matched.

Die Wahrscheinlichkeit, dass eine feste Stelle des Musters zu einer festen Stelle des Textes passt ist 10 * 1/10 * 1/10 = 1/10. Also ist Pr(I,,i,, = 1) = 1/1000, für i = 0, ..., n-3 (an der vorletzten und letzten Stelle kann ein Muster der Länge 3 nicht mehr matchen).

Die erwartete Anzahl Matches ist gerade sum,,i=0,...,n-3,, E I,,i,, = sum,,i=0,...,n-3,, Pr(I,,i,, = 1) = (n - 2)/1000. Für n = 3 ist das 1/1000. Für n = 1002 ist das 1.