#acl -All:read


== AUFGABE 1 (Programmm + Laufzeitbestimmung) ==

=== 1.1 Programm für zweitgrößte Zahl ===

{{{
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) ===

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