Answer to Question 1
a: Die angegebenen Funktionen müssten entsprechend ihrer Wachstumsrate wie folgt angeordnet werden:
3 * log(n), log^2(n), 3 * sqrt(n), n * log(n), n^2 / log(n), n!, n^n

b: Die Laufzeit der Funktion foo(n) beträgt Θ(n log(n)). In jeder Iteration der while-Schleife wird die Variable i verdoppelt und die innere for-Schleife wird n mal ausgeführt. Die Anzahl der Durchläufe der while-Schleife entspricht log(n), da i von 1 beginnend verdoppelt wird, bis es n erreicht oder überschreitet. Also n mal log(n) macht Θ(n log(n)).

c: 
1. Die Anzahl der Zusammenhangskomponenten in einem ungerichteten Graphen kann mit einer Tiefen- oder Breitensuche bestimmt werden. Da jede Kante und jeder Knoten besucht wird, beträgt die Laufzeit O(n + m).
2. Um zu bestimmen, ob ein sortiertes Array eine gegebene Zahl enthält, kann eine binäre Suche verwendet werden, die eine Laufzeit von O(log(n)) hat.
3. Ein Array um eine feste Anzahl Positionen zu rotieren, kann in O(n) Zeit erfolgen, indem man die Elemente in einem neuen Array an den um die Rotationsanzahl verschobenen Positionen einfügt oder zwei Teilarrays invertiert und dann das gesamte Array invertiert.

d: 
1. Eine geeignete Datenstruktur wäre ein binärer Heap oder eine sortierte Liste. Relevant sind die Operationen 'Einfügen' für jeden neuen Versuch und 'Find-Min', um den besten Versuch zu finden, der noch nicht das Ziel getroffen hat.
2. Um die Gartenzwerge zwischen zwei Größen zu finden, könnte eine Datenstruktur wie ein balancierter binärer Suchbaum geeignet sein. Die relevanten Operationen wären 'Einfügen' für die neuen Gartenzwerge und 'Suche' für die Gartenzwerge, die sich in der Größenordnung zwischen den zwei neuen befinden.
3. Für den Bücherturm wäre ein Stapel (Stack) oder ein (dynamisches) Array geeignet. Die relevanten Operationen wären 'Push', um ein neues Buch auf den Stapel zu legen, und 'Pop', um das oberste Buch zu entfernen.





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




Answer to Question 2
a) Die Veränderungen des Min-Heaps durch die Sequenz von Operationen:

1. Zustand 2: push(16)
   Das Element 16 wird dem Heap hinzugefügt. Da 16 größer als alle anderen Werte im Heap ist, wird es am Ende als Blatt angehängt und bleibt an seiner Position, da keine Verschiebung nach oben erforderlich ist.

   Zustand 2 würde folgendermaßen aussehen:
   ```
         2
       /   \
      4     8
     / \   / \
    5   6 11 15
   / \ / \ /
   19 7 12 17 16
   ```

2. Zustand 3: popMin()
   Das Minimum (die Wurzel 2) wird entfernt. Dann nimmt das letzte Element (16) den Platz der Wurzel ein und wird nach unten verschoben (heapify), um die Heap-Bedingung wiederherzustellen. In diesem Fall wird 16 mit 4 vertauscht, da 4 das kleinere der beiden Kinder von 2 ist. Danach wird 16 mit 5 vertauscht, da 5 das kleinere Kind von 4 ist. Der Heap wäre dann wieder korrekt geordnet.

   Zustand 3 würde daher so aussehen:
   ```
        4
       /   \
      5     8
     / \   / \
    19 7  11 15
   / \
   12 17
   ```

3. Zustand 4: push(7)
   Das Element 7 wird dem Heap hinzugefügt. Diesmal wird das Element 7 eine Position nach oben im Heap verschoben, da es kleiner als sein Elternteil 19 ist. Es wird mit 19 getauscht.

   Zustand 4 würde folgendermaßen aussehen:
   ```
         4
       /   \
      5     8
     / \   / \
    7  6  11 15
   / \ / \
   19 17 12 16
   ```

b) Hier ist das Array A, welches den Min-Heap in Zustand 1 repräsentiert:

   A = [2, 4, 8, 5, 6, 11, 15, 19, 7, 12, 17, 14]

   Die Indizes des Arrays entsprechen den Positionen der Knoten im Heap, wenn er als vollständiger Binärbaum betrachtet wird.

c) Pseudocode für die Methode reduceToLargerHalf(H):
   ```
   procedure reduceToLargerHalf(H)
       n = H.size()
       half = ⌊n/2⌋
       for i from 1 to half
           minElement = H.popMin()
           print(minElement)
       end for
   end procedure
   ```
   Diese Methode entfernt die ⌊n/2⌋ kleinsten Elemente aus dem Heap H und gibt sie in sortierter Reihenfolge aus.

d) Die Aussage ist widerlegbar. Die Laufzeit einer einzelnen insert-Operation in einem Heap beträgt im besten Fall O(1), wenn das eingefügte Element sofort die korrekte Position als Blatt einnimmt und keine Umorganisierung erforderlich ist. Allerdings erfordern insert-Operationen normalerweise eine potenzielle Umstrukturierung des Heaps (Heapify-Vorgang), um die Min-Heap-Eigenschaft zu erhalten, wodurch die Laufzeit in Abhängigkeit von der Höhe des Heaps im Durchschnitt O(log n) ist. Daher gibt es keine Garantie, dass jede insert-Operation für alle n immer eine Laufzeit von Θ(1) haben wird. Für manche speziell konstruierte Eingabesequenzen könnten zwar für ein konkretes n insert-Operationen mit Θ(1) gefunden werden, jedoch nicht für jedes beliebige n.





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




Answer to Question 3
a) Die Reihenfolge, in der die Knoten aus der Priority-Queue entnommen werden, folgt den kürzesten Pfaden, die im Algorithmus gefunden werden. Wir beginnen bei Knoten A, also:

1. A (0) - Initialer Knoten
2. B (4) - Kürzester Weg B über A ist 4 Einheiten
3. C (7) - Kürzester Weg C über B (A -> B -> C) ist 4 + 3 = 7 Einheiten
4. E (11) - Kürzester Weg E über B (A -> B -> E) ist 4 + 7 = 11 Einheiten
5. F (12) - Kürzester Weg F über C (A -> B -> C -> F) ist 4 + 3 + 1 = 8 Einheiten, aber es ist bereits ein kürzerer Weg über E entdeckt (A -> B -> E -> F) mit 4 + 7 + 1 = 12 Einheiten
6. D (17) - Kürzester Weg D über E (A -> B -> E -> D) ist 4 + 7 + 6 = 17 Einheiten
7. G (14) - Kürzester Weg G über E (A -> B -> E -> G) ist 4 + 7 + 2 = 13 Einheiten, aber dieser Weg wurde überschrieben von dem Weg über F (A -> B -> E -> F -> G) mit 4 + 7 + 1 + 5 = 17 Einheiten
8. H (15) - Kürzester Weg H über G (A -> B -> E -> G -> H) ist 4 + 7 + 2 + 3 = 16 Einheiten

Da ich nicht auf der Figur zeichnen kann, würde ich den kürzesten Wege-Baum als eine Reihe von Linien beschreiben, die von A ausgehen und die Knoten in der genannten Reihenfolge mit den jeweilig kürzesten Pfaden verbinden. Dies würde zu einer Struktur führen, wo A mit B verbunden ist, B mit C, B weiterhin mit E, E mit D, E mit F, F mit G und G mit H.

b) Bei der Ausführung von Dijkstras Algorithmus gibt es bestimmte Regeln, die eingehalten werden müssen, die dazu führen, dass einige Tabellenzustände nicht auftreten können:

- Im ersten Beispiel gibt es einen falschen Eintrag bei H mit einer Distanz von 12. Betrachten wir jedoch die direkte Verbindung von A zu H über G mit einer Distanz von 9 (A -> G -> H), würde das bedeuten, dass H bereits eine kürzere Distanz zum Startknoten A haben müsste - nämlich 12 von A zu G und 3 von G zu H, also insgesamt 15 und nicht 12.
- Im zweiten Beispiel gibt es einen falschen Eintrag bei D mit einer Distanz von 11. Der kürzeste Weg von A zu D über die Knoten B und E beträgt aber 4 (A zu B) + 7 (B zu E) + 6 (E zu D), was 17 ergibt und nicht 11. Der Eintrag 11 ist also falsch.

c) Um einen Graphen zu konstruieren, bei dem sich die Länge des kürzesten Weges von s zu t Θ(n) -mal ändert, könnte man sich eine Struktur vorstellen, die aus einer Linie von Knoten besteht: 

s - v1 - v2 - v3 - ... - vn - t

Die Kanten zwischen den Knoten sind so gewichtet, dass jede Kante von vi zu vi+1 eine größere Gewichtung hat als alle vorherigen Kanten zusammen. Mit diesem Aufbau würde sich, während Dijkstras Algorithmus ausgeführt wird, die beste bekannte Distanz von s zu t jedes Mal erhöhen, wenn ein neuer Knoten in die Menge der besuchten Knoten aufgenommen wird, da jeder neuere Knoten die bisherige Schätzung des kürzesten Weges obsolet macht. Da es n - 3 Knoten zwischen s und t gibt, ändert sich die beste bekannte Distanz Θ(n) -mal.





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




Answer to Question 4
a) Im gegebenen Graphen suchen wir nach Via-Knoten, wobei ds = 1 und dt = 3 ist. Das bedeutet, wir suchen nach Knoten, die eine Entfernung von 1 von s und eine Entfernung von 3 von t haben. Die Knoten b und c haben eine Entfernung von 1 von s. Nun müssen wir prüfen, welche dieser Knoten genau eine Entfernung von 3 zu t haben. Der Knoten b hat eine Entfernung von 3 zu t, weil ein Pfad von b über f nach t führt. Der Knoten c hat keine Entfernung von 3 zu t, da der kürzeste Pfad von c nach t über d und e führt und somit eine Entfernung von 2 hat. Daher ist nur Knoten b ein Via-Knoten. 

b) Um Knoten f als Via-Knoten zu etablieren, müssten wir ds und dt so wählen, dass f genau ds Entfernungseinheiten von s und dt Entfernungseinheiten von t entfernt ist. Der kürzeste Pfad von s nach f ist über b mit einer Entfernung von 2. Der kürzeste Pfad von f nach t ist direkt mit einer Entfernung von 1. Demnach könnten wir ds = 2 und dt = 1 wählen, um f zu einem Via-Knoten zu machen.

c) Hier die Bewertungen der Aussagen:

   1. Wahr. Wenn die Summe von ds und dt kleiner als die Distanz von s zu t ist, bedeutet das, dass es keinen Weg gibt, von s über einen anderen Knoten nach t zu gelangen, ohne einen kürzeren Weg zu t zu haben als dist(s, t). Also kann es keinen Via-Knoten geben.
   
   2. Falsch. Es ist nicht notwendigerweise der Fall, dass genau ein Via-Knoten existiert, wenn ds + dt gleich der Distanz von s zu t ist. Es kann auch mehrere Via-Knoten geben, die auf verschiedenen gleich langen Pfaden von s nach t vorkommen.
   
   3. Falsch. Auch wenn dt kleiner als oder gleich der Distanz von s zu t ist, garantiert dies nicht, dass alle Via-Knoten auf einem kürzesten s-t-Pfad liegen. Es könnten auch Via-Knoten existieren, die auf einem längeren Weg zu t liegen, wenn ihr Abstand von s zu dt hinzuaddiert die geforderte Distanz ergibt.

d) Um die Distanz von allen Knoten zu einem gegebenen Knoten x in einem gerichteten Graphen in O(n + m) Zeit zu berechnen, kann man den Breath-First-Search (BFS) Algorithmus verwenden, bei dem n die Anzahl der Knoten und m die Anzahl der Kanten ist. BFS startet vom Knoten x und besucht systematisch alle erreichbaren Knoten in der Reihenfolge ihrer Entfernungen, wobei die Distanz jedes entdeckten Knotens gespeichert wird. Da jede Kante und jeder Knoten nur einmal besucht wird, beträgt die Laufzeit O(n + m).

e) Ein Algorithmus, der alle Via-Knoten ermittelt, könnte wie folgt aussehen:
   
   1. Führe BFS von Knoten s aus, um die Distanz von s zu allen anderen Knoten zu berechnen. Speichere dabei die Distanzen in einem Array distFromS.
   2. Führe BFS von Knoten t aus, um die Distanz von t zu allen anderen Knoten zu berechnen. Speichere dabei die Distanzen in einem Array distToT.
   3. Gehe alle Knoten durch und überprüfe für jeden Knoten v, ob distFromS[v] == ds und distToT[v] == dt gilt. Wenn ja, markiere v als Via-Knoten.
   4. Gib alle markierten Via-Knoten aus.

Da BFS eine Laufzeitkomplexität von O(n + m) hat und nur zwei Durchgänge von BFS benötigt werden, knüpft dieser Algorithmus an die Laufzeit von BFS an, und der Durchgang durch alle Knoten, um Via-Knoten zu identifizieren, ist auch in O(n), was bedeutet, dass die gesamte Laufzeit des vorgeschlagenen Algorithmus O(n + m) bleibt.





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




Answer to Question 5
a: Alice hat eine Gewinnstrategie, wenn das Spiel mit den Steinen A = ⟨1, 2, 3, 4, 5, 6, 7, 8, 9, 2⟩ beginnt. Alice kann im ersten Zug entweder einen Stein oder zwei Steine (da der rechteste Stein eine 2 ist) wegnehmen. Um zu gewinnen, sollte sie zwei Steine wegnehmen, da dann 8 Steine übrig bleiben. Bob hat dann die Möglichkeit, einen Stein oder acht Steine wegnehmen (da der rechteste Stein nun eine 8 ist). Sollte Bob einen Stein nehmen, so könnte Alice wiederum einen Stein oder sieben Steine wegnehmen. Wenn sie sieben Steine wegnimmt, bleibt nur ein Stein übrig, und Bob verliert beim nächsten Zug. Sollte Bob hingegen acht Steine nehmen, gewinnt Alice direkt. Daher hat Alice eine Gewinnstrategie.

b: Alice kann entscheiden, ob es bei n verbleibenden Steinen eine Gewinnstrategie gibt, indem sie folgendermaßen vorgeht: Sie betrachtet den rechtesten Stein und die Zahl darauf (nennen wir sie k). Sie kann diesen Stein oder k Steine wegnehmen. Sie prüft für beide Aktionen, ob es eine Gewinnstrategie für die verbleibende Anzahl von Steinen gibt. Wenn es für eine der beiden Aktionen eine Gewinnstrategie gibt (also X[n-1] = wahr oder X[n-k] = wahr für den aktuellen Spieler), dann gibt es auch für n Steine eine Gewinnstrategie.

c: Die Rekurrenz lässt sich wie folgt aufstellen:

Für i = 1: X[1] = wahr (da der einzige verbleibende Stein genommen wird und somit gewonnen wird).

Für i > 1: X[i] = ¬X[i-1] ∨ ¬X[i-k], wobei k der Wert des rechtesten Steins ist. Das heißt, es gibt eine Gewinnstrategie für i Steine, wenn es keine Gewinnstrategie für i-1 Steine gibt oder wenn es keine Gewinnstrategie für i-k Steine gibt (wir nehmen an, dass der Gegner am Zug ist).

d: Der Pseudocode könnte wie folgt aussehen:

```
def aliceCanWin(A):
    n = len(A)
    X = [false] * (n+1)
    X[1] = true  # Basisfall: Wenn nur ein Stein da ist, kann der Spieler diesen nehmen und gewinnen

    for i in range(2, n+1):
        k = A[i-1]
        if i-k > 0:
            X[i] = not X[i-1] or not X[i-k]
        else:
            X[i] = not X[i-1]

    return X[n]

# Beispielaufruf
print(aliceCanWin([1, 2, 3, 4, 5, 6, 7, 8, 9, 2]))  # soll `true` ausgeben
```

Die Funktion `aliceCanWin` gibt `true` zurück, wenn Alice eine Gewinnstrategie hat, andernfalls `false`. Der Algorithmus läuft in O(n) Zeit, da er nur einmal durch das Array `A` läuft und für jede Position im Array `X` einen Wert berechnet.





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




Answer to Question 6
a) Um den Zustand der Datenstruktur nach den angegebenen Operationen zu beschreiben, beginne ich mit Zustand 2 und führe die Operationen help(), appease() und skip(C6, 2) der Reihe nach aus.

- Zustand 3: 
  - help(): Entfernt die vorderste Person (C1) aus der Zustand 2.
  - appease(): Entfernt alle verärgerten Personen (C2 und C3) aus der Schlange, da sie die Personen sind, die in Zustand 2 mit einem doppelten Kreis markiert sind. 
  - skip(C6, 2): Person C6 wird vor Person C5 bewegt, weil sie 2 Personen überspringen darf, sofern keine davon verärgert ist. C4 ist bereits verärgert und markiert, daher darf C6 C4 nicht überspringen.

Der Zustand 3 der Datenstruktur wäre also wie folgt (ich beschreibe die visuelle Darstellung):
- Customer-Support → (C4) → (C5) → (C6) → (C7)
Hierbei sind C4 und C5 jetzt verärgerte Personen, was durch eine besondere Markierung dargestellt wird (z.B. könnte man sie umkreisen oder mit einem speziellen Symbol markieren).

- Zustand 4:
  - queue(C8): Fügt Person C8 am Ende der Schlange ein.
  - skip(C8, 2): Person C8 bewegt sich vor 2 Personen, also vor C7 und C6, da keine von ihnen als verärgert markiert ist.
  - skip(C8, 1): Person C8 kann nur eine zusätzliche Person überspringen, da C5 verärgert ist und nicht wieder übersprungen werden darf. Somit bewegt sich C8 vor C5, aber hinter C4.

Der Zustand 4 der Datenstruktur würde dann so aussehen (visuell dargestellt):
- Customer-Support → (C4) → (C8) → (C5) → (C6) → (C7)
Person C4 bleibt verärgert von der vorherigen skip-Operation, wobei C5 durch die erste skip-Operation von C8 verärgert ist und nun ebenso markiert wird.

Diese Zustände wären gezeichnet mit Personen als Kreise in einer Warteschlangen-Konfiguration, wobei verärgerte Personen besonders hervorgehoben werden.

b) Um eine Sequenz von Operationen anzugeben, die die gestellten Anforderungen erfüllt, nutzen wir die Tatsache, dass eine `skip`-Operation, die \(\Theta(n)\) übersprungene Personen hat, selbst \(\Theta(n)\) Laufzeit hat. Hier ist eine solche Sequenz von Operationen ausgehend von einer leeren Datenstruktur:

1. Füge \(n-1\) Personen mit \(queue(p)\) hinzu, was in \(\Theta(n)\) Zeit erfolgt.
2. Führe eine `skip(p, n)` Operation durch, wobei `p` die zuletzt hinzugefügte Person ist. Diese Operation hat eine Laufzeit von \(\Theta(n)\), da sie \(n-1\) Personen überspringt.

Am Ende der Sequenz wird `p` vor allen \(n-1\) Personen stehen und kann noch immer alle \(n-1 = \Omega(n)\) Personen überspringen, sollte es erforderlich sein. Die restlichen Personen in der Warteschlange sind alle verärgert, da sie übersprungen wurden.

c) Um zu zeigen, dass in jeder Abfolge von `queue`, `help`, `skip` und `appease` Operationen jede Operation amortisiert konstante Kosten hat, kann man das Konzept der Amortisierten Analyse verwenden:

Für `queue` und `help` Operationen ist es offensichtlich, dass sie in konstanter Zeit \(\Theta(1)\) ausgeführt werden können.

Für `skip` Operationen kann man Argumentieren, dass, obwohl die Zeitkomplexität \(\Theta(l)\) ist, wo \(l \leq k\) die Anzahl der übersprungenen Personen ist, jede Person höchstens einmal übersprungen werden kann, bevor sie als verärgert markiert wird und danach nicht mehr übersprungen werden darf. Daher kostet das einmalige Überspringen einer Person konstante Zeit und die Gesamtkosten werden auf die Anzahl der Operationen verteilt.

Für `appease` Operationen fallen Kosten von \(\Theta(m)\) an, wobei \(m\) die Anzahl der verärgerten Personen ist. Da jede verärgerte Person jedoch nur durch eine vorherige `skip` Operation verärgert wurde, kann man die Kosten der `appease` Operation auf die `skip` Operationen umlegen, die zu den verärgerten Personen geführt haben. So haben auch `appease` Operationen amortisiert konstante Kosten, denn jede Person wird nur einmal verärgert und einmal besänftigt.

Insgesamt kann man sagen, dass unabhängig von der Reihenfolge und Anzahl der Operationen, die Kosten jeder Operation, wenn über die gesamte Sequenz verteilt, konstant bleiben.





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




