Answer to Question 1
a) Die Funktionen in der Reihenfolge von O(g) zu O(f) sind: 3 * log(n), n * log(n), n^2 / log(n), log^2(n), 3 * sqrt{n}, n!, n^n.

b) Der Pseudocode für foo(n) führt im Inneren des While-Cyklus eine For-Schleife durch, die n Mal ausgeführt wird. Jede Durchlauf der For-Schleife verursacht O(1) Zeit (da doSomething() O(1) benötigt). Da die For-Schleife innerhalb eines While-Cyklus mit einer Schrittweite von i = 2*i läuft, führt dies zu einer Gesamtzahl von n/2 Durchläufen. Daher ist die Laufzeit von foo(n) O(n^2 / 2), was vereinfacht zu O(n^2) entspricht.

c) 
1. Bestimme die Anzahl der Zusammenhangskomponenten in einem ungerichteten Graphen mit n Knoten und m Kanten: O(m + n)
2. Bestimme, ob ein sortiertes Array mit n Zahlen eine gegebene Zahl enthält: O(log(n))
3. Rotiere ein Array mit n Elementen um 5 Stellen: O(n)

d) 
1. Eine geeignete Datenstruktur wäre ein (dynamisches) Array, da es ermöglicht, den besten Wurf zu speichern und schnell nachzuschlagen, wer der aktuelle Führende ohne einen Treffer ist. Relevant sind hier die Operationen "Suchen" und "Einfügen".
2. Eine Hashtabelle könnte für diese Aufgabe geeignet sein, wobei jeder Gartenzwerg als Schlüssel und seine Größe als Wert gespeichert wird. Dies ermöglicht es, schnell nach alten Zwergen zu suchen, die zwischen den neuen liegen. Relevant sind hier "Suchen" und "Einfügen".
3. Ein (2, 3)-Baum wäre eine gute Wahl, da er das Entnehmen des obersten Buches und das Setzen eines neuen Buches effizient ermöglicht. Hier sind "Entnehmen" und "Setzen" die relevanten Operationen.





****************************************************************************************
****************************************************************************************




Answer to Question 2
a) Im Min-Heap in Zustand 1 sind die Werte [5, 3, 8, 6, 7] gespeichert. Die angegebenen Operationen und ihre Auswirkungen auf den Heap sind:
1. State 2: Insert(9) - Der neue Wert 9 wird am Ende des Arrays hinzugefügt (im Heap-Modell als Kind von 8), was zu [5, 3, 8, 6, 7, 9] führt.
2. State 3: ExtractMin() - Das Minimum 5 wird entfernt und durch den nächsten kleinsten Wert 3 ersetzt, der nach dem Heap-Aufbau als Vater von 6 ist, was zu [3, 8, 6, 7, 9] führt.
3. State 4: Insert(2) - Der neue Wert 2 wird am Ende hinzugefügt und bildet den neuen Mindestwert im Heap, was zu [3, 8, 6, 7, 9, 2] führt.

b) Das Array A für den Min-Heap in Zustand 1 ist: [5, 3, 8, 6, 7]

c) Pseudocode für reduceToLargerHalf(H):
```
def reduceToLargerHalf(H):
    n = H.size() // 2
    for i in range(n):
        min_value = extractMin(H)
        print(min_value)
```

d) Die Aussage ist wahr. Eine Folge von n insert-Operationen mit Laufzeit Θ(1) pro Operation ist möglich, indem man für jedes Element im Heap den Index direkt als Wert verwendet (z.B. 0, 1, 2, ...). Da der Heap bereits die Indizes als Werte enthält, müssen keine Vergleiche oder Verschiebungen durchgeführt werden, um den Heap-Aufbau zu gewährleisten. Jede insert-Operation dauert dann tatsächlich nur konstante Zeit.





****************************************************************************************
****************************************************************************************




Answer to Question 3
a) Die Reihenfolge, in der die Knoten aus der Priority-Queue entnommen werden, wäre: A, B, D, E, C. Dabei wird bei Prioritätsgleichheit der alphabetisch kleinere Knoten gewählt. Der Kürzeste-Weg-Baum würde wie folgt aussehen (gezeichnet auf der Figur "figures/dijkstra.pdf"):
- Startknoten A mit Gewicht 0
- Kante A->B mit Gewicht 1
- Kante B->D mit Gewicht 2
- Kante D->E mit Gewicht 3
- Kante E->C mit Gewicht 4

b) Im ersten Fehlerhaften Zustand ist der Eintrag von C falsch, weil die Distanz von C sollte 6 sein (A-B-D-E-C), aber in der Tabelle steht 7. Im zweiten Fehlerhaften Zustand ist der Eintrag von B falsch, weil die Distanz von B sollte 3 sein (A-B), aber in der Tabelle steht 4.

c) Ein Beispiel für einen Graphen mit n Knoten und zwei Knoten s und t wäre ein vollständiger Graph (alle Knoten sind miteinander verbunden) mit Gewichten 1 auf jeder Kante. Wenn Dijkstra's Algorithmus mit Startknoten s ausgeführt wird, würde die Länge des bekannten kürzesten Weges von s zu t bei jedem Schritt um 1 verringern, bis der kürzeste Weg erreicht ist (also insgesamt n-3 Mal). Wenn man jedoch berücksichtigt, dass der kürzeste Weg bereits bekannt ist, bevor der Algorithmus gestartet wird, beträgt die Gesamtzahl der Änderungen \u0398(n) = n - 1.





****************************************************************************************
****************************************************************************************




Answer to Question 4
a) Im gegebenen Graphen mit ds = 1 und dt = 3 sind die Via-Knoten Knoten b und e, da sie jeweils eine Distanz von 1 zu s und 3 zu t haben.

b) Um Knoten f als Via-Knoten zu haben, müssten ds = 2 und dt = 4 sein. Dies würde bedeuten, dass der Knoten f eine Distanz von 2 von s entfernt ist und gleichzeitig eine Distanz von 4 zu t hat.

c) 
1. Wahr: Wenn ds + dt < dist(s, t), bedeutet das, dass die gesuchte Gesamtdistanz kleiner als die kürzeste Distanz zwischen s und t ist. Da ein Via-Knoten diese beiden Distanzen haben muss, kann es keinen geben, der beide Bedingungen erfüllt.
2. Falsch: Es gibt keine Garantie für genau einen Via-Knoten. Zum Beispiel könnte es mehrere Pfade mit gleicher Länge von s zu t geben, auf denen sich verschiedene Via-Knoten befinden.
3. Wahr: Wenn dt ≤ dist(s, t), müssen alle Via-Knoten entlang eines kürzesten Pfads von s zu t liegen, da sie beide Teilstrecken ds und dt der Gesamtdistanz erfüllen.

d) Um die Distanz von allen Knoten zu einem gegebenen Knoten x in O(n + m) Zeit zu berechnen, kann man den Bellman-Ford-Algorithmus verwenden. Dieser Algorithmus läuft n-mal durch alle Kanten und aktualisiert die kürzesten Pfade, wobei n der Knoten-Anzahl und m der Kanten-Anzahl entsprechen.

e) Der Algorithmus zur Suche nach Via-Knoten könnte wie folgt laufen:
1. Berechne zunächst mit dem Bellman-Ford-Algorithmus in O(n + m) Zeit die kürzesten Pfade von s zu allen Knoten.
2. Überprüfe für jeden Knoten v, ob dist(s, v) = ds und dist(v, t) = dt gilt.
3. Wenn beide Bedingungen erfüllt sind, markiere den Knoten v als Via-Knoten und füge ihn zur Liste der Via-Knoten hinzu.

Der Algorithmus bleibt in O(n + m), da die Berechnung der kürzesten Pfade und die Überprüfung für jeden Knoten in dieser Zeit erledigt werden kann.





****************************************************************************************
****************************************************************************************




Answer to Question 5
a) Alice hat keine Gewinnstrategie, wenn das Spiel mit den Steinen A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 2] beginnt. Wenn Alice einen Stein nimmt, verbleiben neun Steine, und Bob kann im nächsten Zug acht Steine nehmen, was das Spiel beendet. Da Bob den letzten Stein nimmt, gewinnt er. Alice hat keine Möglichkeit, dies zu verhindern.

b) Alice kann entscheiden, ob es bei n verbleibenden Steinen eine Gewinnstrategie gibt, indem sie prüft, ob für alle i < n (inklusive der Fälle, in denen Bob am Zug ist), bei i verbleibenden Steinen keine Gewinnstrategie existiert. Wenn Alice weiß, dass es für Bob keine Gewinnstrategie gibt, wenn nur ein Stein übrig bleibt, dann hat sie eine Gewinnstrategie, indem sie den letzten Stein nimmt.

c) Die Rekurrencerelation für das Array X kann wie folgt formuliert werden:
1. Basisfälle: X[0] = wahr (Alice gewinnt, wenn keine Steine übrig sind)
2. rekursiver Fall: X[i] ist wahr genau dann, wenn einer der folgenden Bedingungen erfüllt ist:
   a) X[i-1] == wahr (Alice kann den nächsten Zug verpassen und gewinnen, wenn Bob keine Gewinnstrategie hat)
   b) Für alle k in [1, a[i]] gilt: Wenn X[i-k] == falsch, dann gibt es keine Gewinnstrategie für Alice, da sie nach dem Entfernen von k Steinen nicht mehr gewinnen kann.

d) Pseudocode für den Algorithmus:
```
function aliceCanWin(A):
    n = length(A)
    X = [false] * (n + 1) # Array mit Initialisierung auf falsch
    X[0] = true

    for i in range(1, n+1):
        if X[i-1]: # Wenn Alice ohne Zug gewinnt
            X[i] = true
        else:
            for k in range(1, A[i]):
                if not X[i-k]: # Keine Gewinnstrategie für Alice nach dem Entfernen von k Steinen
                    break
            X[i] = false

    return X[n]
```

Dieser Algorithmus berechnet die Gewinnstrategie für Alice in O(n) Zeit, indem er rekursiv alle möglichen Zugsituationen prüft.





****************************************************************************************
****************************************************************************************




Answer to Question 6
a) Im Zustand 3 beginnt die Datenstruktur mit der Person C1 vorne, gefolgt von vera\u0308rgerten Personen C2 und C3. Dann folgen C4, C5 und C6. Die Operation help() entf\u00E4lt die vorderste Person (C1) aus der Schlange. Anschlie\u00DFend wird mit appease() alle vera\u0308rgerten Personen entfernt, also C2 und C3. Nach skip(C6, 2) bewegt sich C6 vorne an den dritten Platz, da zwei Personen (C1 und C2) u\u0308bersprungen wurden.

Im Zustand 4 wird nach queue(C8) die Person C8 am Ende der Schlange hinzugef\u00FCgt. skip(C8, 2) bewegt C8 vorne an den dritten Platz, da zwei Personen (C1 und C2) u\u0308bersprungen wurden. Danach wird mit skip(C8, 1) eine weitere Person (C3) u\u0308bersprungen, sodass C8 an den zweiten Platz kommt.

Vera\u0308rgerte Personen sind in beiden Zuständen hervorgehoben: In Zustand 3 sind das C2 und C3, in Zustand 4 ist keine Person mehr vera\u0308rgert, da alle entfernt wurden.

b) Eine Sequenz von Operationen f\u00Fcr n = N besteht aus einer skip-Operation mit Laufzeit \u0398(n), gefolgt von n - 1 queue-Operationen. Zun\u00E4chst wird eine Person (z.B. C1) in die Warteschlange gesetzt, was eine Laufzeit von 1 hat. Dann folgen n - 1 weitere Personen (C2 bis CN), wodurch die Gesamtlaufzeit n betr\u00E4gt. Die skip-Operation bewegt diese Person (C1) so oft vorne an den Anfang der Schlange, dass sie n - 1 Personen u\u0308berspringen muss, was eine Laufzeit von \u0398(n) erfordert. Am Ende kann die Person C1 noch mindestens eine Person (C2) u\u0308berspringen.

c) Um zu zeigen, dass jede Operation amortisiert konstante Kosten hat, betrachten wir den Amortisierten Prozess. F\u00Fcr jedes Element in der Warteschlange f\u00E4llt eine skip-Operation an, die \u2126(l) Zeit braucht, wobei l die Anzahl der u\u0308bersprungenen Personen ist. Da jede Person maximal einmal vera\u0308rgert wird und dann entf\u00E4lt wird, gibt es f\u00Fcr jede skip-Operation mit hohen Kosten eine appease-Operation mit \u2126(m) Zeit, die die vera\u0308rgerten Personen entfernt. Die Gesamtkosten der skip- und appease-Operationen f\u00Fcr eine Person sind also konstant. queue- und help-Operationen haben bereits konstante Kosten von 1. Da jede Operation entweder direkt oder indirekt durch eine andere Operation ausgeglichen wird, hat jede Operation amortisiert konstante Kosten.





****************************************************************************************
****************************************************************************************




