#acl All:read Sabine Storandt:read,write Björn Buchhold:read,write Claudius Korzen:read,write Elmar Haußmann:read,write

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

Alle Angaben ohne Gewähr. Bei Fehlern bitte kurze Mail an die Dozentin.

== AUFGABE 1 (Programmm + Laufzeitbestimmung) ==

=== 1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2 ===

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

=== 1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen ===

Es gilt offensichtlich T,,n,, >= T,,n-1,, + T,,n-2,,.

Induktionsanfang: T_1 >= 1 und T_2 >= 1 gilt offensichtlich.

Induktionschritt: Nach Induktionsvoraussetzung ist T,,n-1,, >= F,,n-1,, und T,,n-2,, >= F,,n-2,,. Damit T,,n,, >= T,,n-1,, + T,,n-2,, >= F,,n-1,, + F,,n-2,, = F,,n,,.

=== 1.3 Funktion zur Berechnung von F_n in Zeit O(n), für n >= 2 ===

{{{
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 Funktion zum Suchen und Löschen eines Elementes aus einem Feld ===

{{{
def removeFromArray(A, x):
    i = 0
    # Find the element.
    while i < len(A) and A[i] != x:
        i = i + 1
    # If found, copy last element and shrink array by 1.
    if i < len(A):
       A[i] = A[-1]
       A.pop()
}}}

=== 2.2 Funktion zum Löschen eines Elementes aus einer Hashtabelle ===

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

=== 2.3 Laufzeit der Funktionen aus Aufgabe 2.1 und 2.2 ===

Die Funktion aus Aufgabe 2.1 hat Laufzeit Theta(i), wenn das Element an Stelle i steht bzw. Theta(n) wenn das Element nicht im Feld steht.

Die Funktion aus Aufgabe 2.2 hat Laufzeit Theta(1) im besten Fall (unter h(x) stehen in T nur konstant viele Elemente) und Laufzeit Theta(n) im schlechtesten Fall (alle Elemente in T werden auf h(x) abgebildet und das gesuchte Element ist nicht dabei oder steht ganz am Ende des Feldes).

=== 2.4 Klasse H nicht 1-universell, wenn |H| < m und |U| > m ===

Nach Definition von 1-universell müsste für alle x, y mit x != y gelten, dass |{h: h(x) = h(y)}| <= c * |H| / m < 1, also = 0.
Das heißt, für jedes Schlüsselpaar x, y mit x != y darf es keine Hashfunktion geben, unter der die beiden Schlüssel auf dasselbe abgebildet werden.
Für jede Hashfunktion h muss es aber zwei Schlüssel geben, die auf dasselbe abgebildet werden, weil es > m Schlüssel gibt aber nur m Plätze in der Hashtabelle.
    

== AUFGABE 3 (Binäre Heaps) ==

=== 3.1 Heapzustand (als Baum und als Feld) nach dem Einfügen von 5, 4, 3, 2, 1 (in der Reihenfolge)  ===

Von links nach rechts: oben = Baum, unten = Feld (x = beliebiger Wert an Position 0 im Feld)

{{{
5      4     3        2         1
      /     / \      / \       / \
     5     5   4    3   4     2   4
                   /         / \
                  5         5   3

x5   x45   x354   x2345     x12453
}}}

=== 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
}}}

=== 3.3 Laufzeit der Funktion aus Aufgabe 3.2 ===

Die Laufzeit is Theta(n).
Begründung: die Schleife läuft n - 2 = Theta(n) mal durch und in jedem Durchlauf gibt es eine konstante Anzahl von Anweisungen.

=== 3.4 Anzahl Blockoperationen der Funktion aus Aufgabe 3.2 ===

Die Anzahl Blockoperation is Theta(n/B).
Begründung: für das child_value liest man n Elemente von links nach rechts, eins nach dem anderen, das sind ~ n/B Blockoperationen.
Für das parent_value liest man n/2 Elemente von links nach rechts, eins nach dem anderen (und immer denselben Wert zweimal hintereinander), das sind ~ (n/2)/B Blockoperationen.
 
== AUFGABE 4 (Graphen) ==

=== 4.1 Zeichnung des Graphen + Darstellung durch Adjazenzlisten und Adjazenmatrix ===

Die Zeichnung ist trivial (ein Dreick, mit den Kanten einmal reihum, Gewicht jeweils 2).

Darstellung durch Adjazenzlisten (u,,1,, -> 0, u,,2,, -> 1, u,,3,, -> 2):

{{{
0 -> (1, 2)
1 -> (2, 2)
2 -> (0, 2)
}}}

Darstellung durch 3 x 3 Adjazentmatrix (x = spezieller Eintrag, der bedeutet "keine Kante"):

{{{
x 2 x
x x 2
2 x x
}}}

=== 4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten ===

{{{
# graph is represented as an array of n adjacency lists, where n = #nodes.
def numEdges(graph):
    count = 0
    for i in range(0, len(graph)):
        count += len(graph[i])
    return count
}}}

=== 4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix ===

{{{
# graph is represented as an array of n array, each of size n, where n = #nodes.
def numEdges(graph):
    count = 0
    n = len(graph)
    for i in range(0, n):
        for j in range(0, n):
            if graph[i][j] > 0:
                count += 1
    return count
}}}

=== 4.4 Laufzeit der Funktionen aus Aufgabe 4.2 und Aufgabe 4.3 ===

Die Laufzeit der Funktion aus Aufgabe 4.2 ist Theta(n), wobei n die Anzahl der Knoten ist.
Begründung: die Schleife wird n mal durchlaufen, und in jedem Schleifendurchlauf werden nur konstant viele Anweisungen ausgeführt.

Die Laufzeit der Funktion aus Aufgabe 4.3 ist Theta(n^2^), wobei n die Anzahl der Knoten ist.
Begründung: die äußere Schleife wir n mal durchlaufen und die innere ebenfalls, das gibt insgesamt n^2^ Durchläufe des Schleifenkörpers, der aus konstant vielen Anweisungen besteht.

== AUFGABE 5 (Edi-Tier) ==

=== 5.1 Editierdistanz zwischen REGAL und LAGER ===

{{{
   e L A G E R
e  0 1 2 3 4 5 
R  1 1 2 3 4 4
E  2 2 2 3 3 4
G  3 3 3 2 3 4
A  4 4 3 3 3 4 
L  5 4 4 4 4 4
}}}

=== 5.2 ED(x, y) = n - 1, falls n ungerade und x das Wort y rückwärts ist und alle Buchstaben verschieden ===

Falls n ungerade ist, ist der mittlere Buchstabe von x und y gleich.
Man also x mit n - 1 replace Operationen in y überführen.
Das zeigt aber erstmal nur ED(x, y) <= n - 1 (es könnte auch noch mit weniger Operationen gehen).
Die Alternative zu einem Replace wäre die benötigten Buchstaben durch Löschen und Einfügen hinzuzufügen.
Das hat Kosten 2 und hilft aber immer nur höchstens zwei Buchstaben, ist also auch nicht besser.

=== 5.3 ED(x, y) = ?, falls n gerade und x das Wort y rückwärts ist und alle Buchstaben verschieden ===

Falls n gerade ist, haben x und y keinen Buchstaben an derselben Stelle gemeinsam.
Man kann aber auf jeden Fall x mit n Replace Operationen in y überführen.
Mit demselben Argument wie oben (Einfügen und Löschen hilft höchstens zwei Buchstaben) geht es auch nicht besser.
Also in dem Fall ED(x, y) = n.

=== 5.4 ED(x, y) im niedrigsten Fall, wenn nur mindestens zwei verschiedene Buchstaben ===

Wenn x ein Palindrom ist (z.B. Hannah oder Hannnah), dann ist x = y und ED(x, y) = 0.
Für n = 2 geht das allerdings nicht, weil es mindestens zwei verschiedene Buchstaben geben muss, da ist dann ED(x, y) = 2.


== AUFGABE 6 (O-Notation, Logarith-Mus, W-keit) ==

=== 6.1 Zeigen Sie, dass 2n + 17 = O(n^2) über die Definition von O mittels C und n,,0,, ===

Für n >= 5 ist 2n + 17 <= n^2^ + n^2^ <= 2 n^2^. Also Bedingung per Definition erfüllt mit n,,0,, = 5 und C = 2.

=== 6.2 Wert von log,,2,, (2^64^ * 8^12^) ===

log,,2,, (2^64^ * 8^12^) = log,,2,, 2^64^ + log,,2,, 8^12^ = 64 + log,,2,, 2^36^ = 64 + 36 = 100.
Dabei wurde benutzt dass 8 = 2^3^ und "x hoch y hoch z" gleich "x hoch (y * z)" ist.

=== 6.3 Wahrscheinlichkeit guter Pivot (beide Teile >= n/4) bei Quicksort, bei zufälliger Wahl ===

Seien die Elemente ohne Beschränkung der Allgemeinheit 1, ..., n (es zählt nur die Reihenfolge nicht der Wert).
Wählt man eines der n/4 Elemente 1, ..., n/4 als Pivot ist der "vordere" Teil (Elemente < Pivot) kleiner als n/4.
Wählt man eines der n/4 Elemente n - n/4 + 1, ..., n als Pivot ist der "hintere" Teil (Elemente > Pivot) kleiner als n/4.
Wählt man eines der übrigen n/2 Elemente als Pivot, sind beide Teile >= n/4.
Die Wahrscheinlichkeit ist also 1/2.

=== 6.4 Wahrscheinlichkeit von 6.3 bei dreimaliger Wiederholung ===

Wir betrachten erst das Gegenereignis = selbst für die beste Aufteilung ist ein Teil < n/4.
Wenn das passiert, ist für alle drei Aufteilungen (von allen drei Pivots), der kleinste Teil n/4.
Nach Aufgabe 6.3 passiert das für jede Aufteilung mit Wahrscheinlichkeit 1/2.
Die Wahrscheinlichkeit, dass es für alle drei passiert ist also 1/8.
Die gefragt Wahrscheinlichkeit ist also 7/8.