Answer to Question 1
Hier sind meine Antworten zu den gestellten Fragen:

a) Die Funktionen in der geforderten Reihenfolge:
3 * log(n), log^2(n), 3 * sqrt(n), n * log(n), n^2 / log(n), n!, n^n

b) Die Laufzeit von foo(n) ist Θ(n * log(n)).
Erklärung:
- Die äußere while-Schleife läuft log(n) mal, da sich i in jeder Iteration verdoppelt, bis n erreicht ist. 
- Die innere for-Schleife läuft in jeder Iteration der äußeren Schleife n mal.
- doSomething() benötigt konstante Zeit Θ(1).
Insgesamt ergibt sich eine Laufzeit von log(n) * n * Θ(1) = Θ(n * log(n)).

c) 
1. O(n+m) - Tiefensuche oder Breitensuche auf dem Graphen
2. O(log(n)) - Binäre Suche im sortierten Array 
3. O(n) - Linearer Durchlauf durch das Array, Verschieben der Elemente

d)
1. Datenstruktur: Heap (Minimum-Heap)
   Relevante Operationen: insert (Einfügen eines neuen Wurfversuchs), findMin (Finden des besten Versuchs)

2. Datenstruktur: (2,3)-Baum
   Relevante Operationen: insert (Einfügen der neuen Gartenzwerge), rangeSearch (Suchen der Zwerge zwischen den Größen der neuen)

3. Datenstruktur: Stack (als Array oder Liste implementiert)  
   Relevante Operationen: push (Buch oben drauflegen), pop (oberstes Buch entnehmen), top (oberstes Buch ansehen)





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




Answer to Question 2
a) Zustand 2 entsteht aus Zustand 1 durch push(16). Dabei wird 16 als neues Blatt eingefügt und dann mit seinem Elternknoten 8 getauscht, da 16 > 8.

Zustand 3 entsteht aus Zustand 2 durch popMin(). Dabei wird die Wurzel 2 entfernt, das letzte Blatt 15 an die Wurzel verschoben und dann solange mit dem kleineren Kind getauscht (7), bis die Heap-Eigenschaft wiederhergestellt ist.

Zustand 4 entsteht aus Zustand 3 durch push(7). Dabei wird 7 als neues Blatt eingefügt. Es sind keine Vertauschungen nötig, da 7 kleiner als sein Elternknoten 11 ist.

b) Das Array A, welches den Min-Heap in Zustand 1 repräsentiert, lautet:
A = [2, 4, 8, 5, 19, 6, 11, 7, 12, 17, 14]

c) Pseudocode für reduceToLargerHalf(H):

reduceToLargerHalf(H):
    n = H.size()
    for i = 1 to ⌊n/2⌋ do
        x = H.extractMin()
        print(x)

d) Die Aussage ist wahr. Wenn man die Elemente in aufsteigend sortierter Reihenfolge in den anfangs leeren Heap einfügt, muss bei keiner Operation ein Tausch durchgeführt werden, da jedes neu eingefügte Element bereits größer als sein Elternknoten ist. Somit hat jede insert-Operation eine Laufzeit von O(1).





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




Answer to Question 3
a) Die Reihenfolge, in der die Knoten aus der Priority-Queue entnommen werden, ist: A, C, B, E, F, D, G, H.

Der zugehörige Kürzeste-Wege-Baum ist in der Abbildung unten durch fett markierte Kanten gekennzeichnet:

A -- 3 --> C
|    1     |
9          2
|          |
B          E -- 8 --> F
           |    2     |
           3          5
           |          |
           D -- 6 --> G -- 3 --> H

b) Begründungen für die fehlerhaften Zustände:

Abbildung 1: Der Eintrag für Knoten H ist fehlerhaft. Die Distanz zu H kann nicht 12 sein, da der kürzeste Weg von A nach H über B, C, D, E, F und G eine Länge von 3 + 1 + 2 + 3 + 2 + 5 + 3 = 19 hat. Der Eintrag für H müsste unendlich sein, da H von A aus noch nicht erreicht wurde.

Abbildung 2: Der Eintrag für Knoten D ist fehlerhaft. Die Distanz zu D kann nicht 11 sein, da der kürzeste Weg von A nach D über C eine Länge von 3 + 2 = 5 hat. Der Eintrag für D müsste 5 sein, da dies die Länge des aktuell bekannten kürzesten Weges von A nach D ist.

c) Für jedes n > 3 kann folgender Graph konstruiert werden:

s -- 1 --> v1 -- 1 --> v2 -- 1 --> ... -- 1 --> v(n-2) -- 1 --> t
     n-1        n-2        n-3                  2             1

Bei der Ausführung von Dijkstras Algorithmus mit Startknoten s wird die Länge des aktuell bekannten kürzesten Weges von s zu t zunächst mit n-1 initialisiert (direkte Kante). Dann wird sie bei jedem Schritt um 1 verringert, wenn der nächste Knoten auf dem Pfad s, v1, v2, ..., v(n-2), t besucht wird. Insgesamt ändert sich die Länge also (n-1) - 1 = n-2 = Θ(n) Mal.





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




Answer to Question 4
a) Im gegebenen Graphen mit ds = 1 und dt = 3 sind die Knoten b und c Via-Knoten. Von s aus haben beide Knoten eine Distanz von 1 und von beiden Knoten zu t beträgt die Distanz 3.

b) Damit Knoten f ein Via-Knoten ist, muss gelten: ds = 2 und dt = 2. Denn die Distanz von s zu f beträgt 2 und die Distanz von f zu t ebenfalls 2.

c) 1. Wahr. Wenn ds + dt < dist(s, t), dann kann es keinen Knoten v geben, der gleichzeitig Distanz ds von s und Distanz dt zu t hat, da sonst ein kürzerer Weg von s nach t als dist(s, t) existieren würde.

2. Falsch. Auch wenn ds + dt = dist(s, t) ist, kann es mehrere oder gar keine Via-Knoten geben. Beispielsweise könnte es parallele Pfade geben, die diese Bedingung erfüllen.

3. Wahr. Sei v ein Via-Knoten. Dann ist dist(s, v) + dist(v, t) = ds + dt. Falls dt ≤ dist(s, t), folgt dist(s, v) + dist(v, t) ≤ dist(s, t). Da dist(s, t) aber die Länge eines kürzesten s-t-Pfades ist, muss Gleichheit gelten und v auf einem kürzesten s-t-Pfad liegen.

d) Von einem gegebenen Knoten x aus kann man mit einer Breitensuche die Distanzen zu allen anderen Knoten in O(n + m) berechnen. Dabei werden, ausgehend von x, alle Knoten schichtweise entsprechend ihrer Distanz zu x besucht und die Distanzen gespeichert.

e) 1. Führe eine Breitensuche von s aus durch und speichere für jeden Knoten v die Distanz dist(s, v). 
2. Führe eine Breitensuche von t aus durch und speichere für jeden Knoten v die Distanz dist(v, t).
3. Gib alle Knoten v aus, für die dist(s, v) = ds und dist(v, t) = dt gilt.

Beide Breitensuchen benötigen O(n + m) Zeit. Das Überprüfen der Bedingung und Ausgeben der Via-Knoten benötigt O(n) Zeit. Insgesamt liegt die Laufzeit also in O(n + m).





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




Answer to Question 5
a) Nein, Alice hat in diesem Fall keine Gewinnstrategie. Egal welchen Zug Alice am Anfang macht, Bob kann immer gewinnen. Wenn Alice einen oder zwei Steine nimmt, nimmt Bob anschließend drei Steine. Wenn Alice drei Steine nimmt, nimmt Bob vier. So kann Bob immer sicherstellen, dass er den letzten Stein (die 2) nimmt und somit gewinnt.

b) Alice kann folgendermaßen entscheiden, ob es bei n verbleibenden Steinen eine Gewinnstrategie gibt:
- Wenn es für Alice bei n-1 oder n-an keine Gewinnstrategie gibt, dann hat Alice jetzt eine Gewinnstrategie. Denn sie kann entweder 1 oder an Steine nehmen und Bob damit in eine Situation bringen, wo er verliert.  
- Andernfalls, wenn es sowohl bei n-1 als auch bei n-an eine Gewinnstrategie für den Spieler am Zug gibt, dann hat Alice jetzt keine Gewinnstrategie. Egal was sie macht, Bob kann immer in eine Gewinnposition gelangen.

c) Die Rekurrenz lautet:
- Basisfälle: 
  - X[0] = falsch
  - X[1] = wahr
- Rekurrenz für i > 1:  
  X[i] = (nicht X[i-1]) oder (i >= ai und nicht X[i-ai])

Das heißt, es gibt eine Gewinnstrategie bei i Steinen, wenn es entweder bei i-1 Steinen keine Gewinnstrategie gibt (dann nimmt man 1 Stein) oder wenn es bei i-ai Steinen keine Gewinnstrategie gibt und i >= ai ist (dann nimmt man ai Steine).

d) Pseudocode:

```
function aliceCanWin(⟨a1, ..., an⟩) : Bool
    X = new Array[n+1]
    X[0] = false
    X[1] = true
    
    for i = 2 to n:
        X[i] = (not X[i-1]) or (i >= ai and not X[i-ai])
    
    return X[n]
```

Der Algorithmus füllt das Array X gemäß der Rekurrenz und gibt am Ende X[n] zurück, was angibt, ob Alice eine Gewinnstrategie hat, wenn alle n Steine noch da sind. Die Laufzeit ist O(n), da die for-Schleife n-1 mal durchlaufen wird.





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




Answer to Question 6
a) Zustand 3 nach Ausführung von help(), appease() und skip(C6, 2) ausgehend von Zustand 2:
Customer-Support -> C1 -> C4 -> C5 -> C6 -> C7
C4 und C5 sind verärgert (ich würde sie z.B. rot markieren).

Zustand 4 nach Ausführung von queue(C8), skip(C8, 2) und skip(C8, 1) ausgehend von Zustand 3:  
Customer-Support -> C1 -> C8 -> C4 -> C5 -> C6 -> C7
C4, C5 und C6 sind verärgert.

b) Eine mögliche Sequenz für jedes n ∈ ℕ:
- n mal queue(Ci) für i = 1...n
- skip(Cn, n-1)
Am Ende darf Cn noch n-1 = Ω(n) Personen überspringen.
Die Sequenz besteht aus n+1 = Θ(n) Operationen.
Die skip-Operation überspringt n-1 Personen und hat damit Laufzeit Θ(n).

c) Wir weisen jeder Person zwei Guthaben zu:
1. 1 Guthaben beim Einfügen per queue()  
2. 1 Guthaben pro Person, die sie überspringt
Jede übersprungene Person verbraucht 1 Guthaben, um als verärgert markiert zu werden.
help() und appease() verbrauchen das Guthaben der entfernten Personen.

Damit hat queue() amortisierte Kosten von O(1). 
help() und appease() haben amortisierte Kosten von O(1) pro entfernter Person.
skip(p, k) hat amortisierte Kosten von O(1) pro übersprungener Person, da p genug Guthaben von den übersprungenen Personen erhält, um diese als verärgert zu markieren.





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




