AUFGABE 1 (Programmm + Laufzeitbestimmung)

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

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), 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 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 4 (Graphen)

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