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 >= 2 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, swap to the end and remove last element.
    if i < len(A):
       A[i], A[-1] = A[-1], A[i]
       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₁ -> 0, u₂ -> 1, u₃ -> 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²), 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² 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

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.

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² + n² <= 2 n². Also Bedingung per Definition erfüllt mit n₀ = 5 und C = 2.

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

log₂ (2⁶⁴ * 8¹²) = log₂ 2⁶⁴ + log₂ 8¹² = 64 + log₂ 2³⁶ = 64 + 36 = 100. Dabei wurde benutzt dass 8 = 2³ 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.