Answer to Question 1


a) Die korrekt sortierten Funktionen sind:

1. 3 * log(n)
2. 3 * sqrt{n}
3. log^2(n)
4. n * log(n)
5. n^2 / log(n)
6. n!
7. n^n

b) Die Funktion foo(n) hat eine Laufzeit von O(n^3). Dies ist so, weil der äußere Loop n mal läuft, der innere Loop ebenfalls n mal läuft und die Anweisung in Zeile 5 eine konstante Zeit von O(1) hat. Die Gesamtzeit ist also n * n * 1 = n^2.

c) Die Laufzeiten der angegebenen Probleme sind:

1. O(n) - Es kann eine Breadth-First-Search durchgeführt werden, die eine Laufzeit von O(n + m) hat. Da m <= n^2 ist, ist die Laufzeit O(n).
2. O(log n) - Das Array kann als Heap implementiert werden, wodurch eine Suche in O(log n) möglich ist.
3. O(n) - Das Array kann um 5 Stellen rotiert werden, indem es in 5 Teile geteilt und diese Teile dann in der richtigen Reihenfolge wieder zusammengesetzt werden.

d) Die geeigneten Datenstrukturen für die angegebenen Probleme sind:

1. Eine Priority-Queue (bspw. ein Heap) ist geeignet, um den besten Wurf zu finden und zu aktualisieren. Die relevanten Operationen sind Insert und Extract-Min.
2. Ein Array ist geeignet, um die Gartenzwerge zu speichern und zu sortieren. Die relevanten Operationen sind Insert und Sort.
3. Ein Stack ist geeignet, um die Bücher im Turm zu speichern und zu verwalten. Die relevanten Operationen sind Push und Pop.





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




Answer to Question 2


Die Zustände 2, 3 und 4 des Heaps aus Teilaufgabe a) sind wie folgt:

Zustand 2:
1. Entferne das kleinste Element (1) aus dem Heap.
2. Der neue Wurzelknoten ist nun der Wert 2.
3. Vergleiche den Wert 2 mit seinen Kindern 5 und 6.
4. Tausche den Wert 2 mit dem kleineren Kind 5.
5. Der linke Teilbaum ist nun ein Min-Heap, aber der rechte Teilbaum ist kein Min-Heap mehr.
6. Vergleiche den Wert 5 mit seinem Kind 10.
7. Tausche den Wert 5 mit dem größeren Kind 10.
8. Der rechte Teilbaum ist nun wieder ein Min-Heap.

Zustand 3:
1. Entferne das kleinste Element (2) aus dem Heap.
2. Der neue Wurzelknoten ist nun der Wert 3.
3. Vergleiche den Wert 3 mit seinen Kindern 4 und 5.
4. Tausche den Wert 3 mit dem kleineren Kind 4.
5. Der linke Teilbaum ist nun ein Min-Heap, aber der rechte Teilbaum ist kein Min-Heap mehr.
6. Vergleiche den Wert 4 mit seinem Kind 7.
7. Tausche den Wert 4 mit dem größeren Kind 7.
8. Der rechte Teilbaum ist nun wieder ein Min-Heap.

Zustand 4:
1. Entferne das kleinste Element (3) aus dem Heap.
2. Der neue Wurzelknoten ist nun der Wert 4.
3. Vergleiche den Wert 4 mit seinen Kindern 5 und 6.
4. Der linke Teilbaum ist nun ein Min-Heap, und der rechte Teilbaum ist ebenfalls ein Min-Heap.

Die Antwort auf Teilaufgabe b) ist das Array A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].

Der Pseudocode für reduceToLargerHalf(H) aus Teilaufgabe c) ist wie folgt:

1. L = []
2. while H.size() > n/2:
a. x = H.extractMin()
b. L.append(x)
c. if H.size() > 1 and H.get(1) > x:
i. H.heapifyDown(1)
3. return L

Die Methode reduceToLargerHalf(H) verwendet eine Schleife, um die kleineren Hälfte der Elemente aus H zu entfernen und in die Liste L einzufügen. In jedem Schleifendurchlauf wird das kleinste Element aus H entfernt und in L gespeichert. Wenn der Wurzelknoten von H größer ist als das gerade entfernte Element, wird der Heap mit heapifyDown() neu geordnet.

Die Antwort auf Teilaufgabe d) ist:

Für jedes n ∈ N existiert eine Folge von n insert-Operationen, sodass jede dieser insert-Operationen Laufzeit O(1) hat.

Begründung:

Die insert-Operation kann in konstanter Zeit durchgeführt werden, indem das neue Element am Ende des Arrays eingefügt wird und anschließend der Heap mit heapifyUp() neu geordnet wird. Wenn das Array zu Beginn leer ist, kann das neue Element direkt an der ersten Position eingefügt werden, ohne dass eine Neuordnung erforderlich ist. Da jede insert-Operation in konstanter Zeit durchgeführt werden kann, gibt es für jedes n ∈ N eine Folge von n insert-Operationen, die diese Eigenschaft erfüllt.





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




Answer to Question 3


a) Die Knoten werden aus der Priority-Queue in folgender Reihenfolge entnommen: A, B, D, C. Die Kanten des zugehörigen kürzesten Weges Baums sind AB, AD, DC.

b) Für die beiden fehlerhaften Zustände des Distanzarrays D gilt:

- Für den ersten Zustand ist der Eintrag von B mit 10 fehlerhaft. Der kürzeste Weg von A nach B ist AB mit Gewicht 5, nicht AD mit Gewicht 10.
- Für den zweiten Zustand ist der Eintrag von C mit 20 fehlerhaft. Der kürzeste Weg von A nach C ist AD mit Gewicht 10, dann DC mit Gewicht 10, insgesamt also 20. Der Eintrag von D mit 15 ist hingegen korrekt, da der kürzeste Weg von A nach D AD mit Gewicht 10 ist.

c) Für jedes n > 3 gibt es einen Graphen mit n Knoten, sodass sich bei der Ausführung von Dijkstras Algorithmus mit Startknoten s die Länge des aktuell bekannten kürzesten Weges von s zu t insgesamt ⌈n/2⌉ mal ändert.

Einen solchen Graphen erhält man, indem man n Knoten in zwei Reihen mit je ⌈n/2⌉ Knoten anordnet. Die Knoten in der oberen Reihe sind mit allen Knoten in der unteren Reihe verbunden, die Knoten in der unteren Reihe sind nur mit ihren Nachbarn in der unteren Reihe verbunden. Der Startknoten s ist der erste Knoten in der oberen Reihe, der Zielknoten t ist der letzte Knoten in der unteren Reihe.

Bei der Ausführung von Dijkstras Algorithmus wird der kürzeste Weg von s zu t zunächst über die Knoten in der oberen Reihe gefunden, danach über die Knoten in der unteren Reihe. Insgesamt ändert sich die Länge des aktuell bekannten kürzesten Weges von s zu t also ⌈n/2⌉ mal.





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




Answer to Question 4


a) Die Via-Knoten im gegebenen Graphen sind c und e, da der Abstand von s zu c und c zu t jeweils 1 und 3 ist.

b) Für Knoten f zu gelten, muss ds + dt = dist(s, f) + dist(f, t) sein. Wenn ds = 1 und dt = 3, dann muss dist(s, f) + dist(f, t) = 4 sein. Da der Abstand von s zu f 1 und der Abstand von f zu t 3 ist, ist Knoten f ein Via-Knoten für ds = 1 und dt = 4.

c) 1. Wahr, da der Abstand von s zu t kleiner als die Summe der Entfernungen von s und t zu einem Knoten sein muss.
2. Falsch, da es mehrere kürzeste Pfade geben kann.
3. Wahr, da alle Via-Knoten auf kürzesten Pfaden liegen.

d) Um die Distanz von allen Knoten zu einem gegebenen Knoten x in O(n + m) Zeit zu berechnen, können wir Breitensuche (BFS) verwenden. BFS durchsucht die Knoten in der Reihenfolge der Entfernung vom Startknoten x und speichert die kürzeste Entfernung jedes Knotens. Die Laufzeit von BFS beträgt O(n + m).

e) Um alle Via-Knoten in O(n + m) Zeit zu finden, können wir zwei BFS-Durchläufe verwenden. Der erste Durchlauf beginnt bei Knoten s und berechnet die Entfernung jedes Knotens von s. Der zweite Durchlauf beginnt bei Knoten t und prüft für jeden Knoten, ob seine Entfernung von s ds und seine Entfernung von t gleich dt ist. Wenn ja, ist der Knoten ein Via-Knoten. Die Laufzeit beträgt 2 \* O(n + m) = O(n + m).





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




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. Grund dafür ist, dass Alice unabhängig davon, ob sie einen oder zwei Steine nimmt, immer eine Anordnung von Steinen übrig bleibt, bei der Bob gewinnen kann. Wenn Alice einen Stein nimmt, bleiben die Steine 2, 3, 4, 5, 6, 7, 8, 9, 2 übrig. In diesem Fall kann Bob entweder einen Stein nehmen und dann die restlichen Steine (die ebenfalls eine Gewinnstrategie für Bob darstellen) oder er nimmt die Steine 2, 3, 4, 5, 6, 7, 8 und lässt Alice mit den Steinen 9 und 2 zurück. In diesem Fall gewinnt Bob ebenfalls, da Alice entweder einen oder beide Steine nehmen muss und Bob dann die restlichen Steine nimmt. Wenn Alice zwei Steine nimmt, bleiben die Steine 3, 4, 5, 6, 7, 8, 9, 2 übrig. Auch in diesem Fall kann Bob gewinnen, indem er entweder einen Stein nimmt und dann die restlichen Steine oder er nimmt die Steine 3, 4, 5, 6, 7, 8, 9 und lässt Alice mit den Steinen 2 zurück.

b) Wenn Alice weiß, ob es für jedes i < n eine Gewinnstrategie gibt, wenn i Steine übrig bleiben, kann sie entscheiden, ob es für n Steine eine Gewinnstrategie gibt, indem sie sich die letzten zwei Steine ansieht. Wenn die Zahlen auf den letzten zwei Steinen gleich sind, hat Alice keine Gewinnstrategie, da Bob die letzten zwei Steine nehmen kann und dann nur noch eine Anordnung von Steinen übrig bleibt, bei der Alice am Zug ist und bei der es keine Gewinnstrategie für sie gibt. Wenn die Zahlen auf den letzten zwei Steinen ungleich sind, hat Alice eine Gewinnstrategie, da sie die beiden Steine nehmen kann und dann nur noch eine Anordnung von Steinen übrig bleibt, bei der Bob am Zug ist und bei der es keine Gewinnstrategie für ihn gibt.

c) Die Rekurrenz für das dynamische Programm lautet wie folgt:

X[i] = false, wenn i = 1 oder i mod 2 = 0
X[i] = true, wenn i > 1 und i mod 2 = 1

Für i > 1 und i mod 2 = 1 gilt X[i] = true, da Alice in diesem Fall gewinnen kann, indem sie den Stein mit der Zahl i nimmt und dann nur noch eine Anordnung von Steinen übrig bleibt, bei der Bob am Zug ist und bei der es keine Gewinnstrategie für ihn gibt.

d) Hier ist ein möglicher Pseudocode für den Algorithmus:

aliceCanWin(a)
  n = length(a)
  if n = 1 then
    return false
  end if
  if n mod 2 = 0 then
    return false
  end if
  return true

Dieser Algorithmus hat eine Laufzeit von O(n), da er nur eine lineare Überprüfung der Länge der Eingabe durchführt.





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




Answer to Question 6


Die Antworten auf die Fragen und Unterfragen lauten wie folgt:

a)

Zustand 3:

1. help(): Die vorderste Person wird entfernt.
2. appease(): Alle verärgerten Personen werden entfernt.
3. skip(C6, 2): C6 wird zwei Plätze nach vorne bewegt, wobei C5 übersprungen wird, da C5 verärgert ist.

![Zustand 3](figures/amortized-queue.pdf)

Zustand 4:

1. queue(C8): C8 wird am Ende der Schlange eingefügt.
2. skip(C8, 2): C8 wird zwei Plätze nach vorne bewegt, wobei C7 übersprungen wird.
3. skip(C8, 1): C8 wird einen Platz nach vorne bewegt, wobei C6 übersprungen wird, da C6 verärgert ist.

![Zustand 4](figures/amortized-queue.pdf)

b)

Eine mögliche Sequenz von Operationen für n = 2k ist: queue(C1), queue(C2), skip(C2, k-1), help(), queue(C3), skip(C3, k-1), help(), ..., queue(C2k-1), queue(C2k), skip(C2k, k-1), help().

Die Erklärung ist, dass wir abwechselnd Personen einfügen und diese dann mit der skip-Operation so weit nach vorne bringen, dass sie die nächste Person überspringen können. Die letzte Person wird dann mit der help-Operation entfernt.

c)

Um zu zeigen, dass jede Operation amortisiert konstante Kosten hat, müssen wir eine Potenzfunktion definieren, die die tatsächlichen Kosten jeder Operation mit den amortisierten Kosten verrechnet.

Wir definieren die Potenzfunktion wie folgt:

- queue(p): 0
- help(): -1
- skip(p, k): k
- appease(): -m (m ist die Anzahl der entfernten verärgerten Personen)

Die amortisierten Kosten jeder Operation sind also die tatsächlichen Kosten plus die Änderung der Potenzfunktion.

Wir müssen nun zeigen, dass die amortisierten Kosten jeder Operation konstant sind.

- queue(p): Die tatsächlichen Kosten sind Θ(1), und die Potenzfunktion ändert sich nicht.
- help(): Die tatsächlichen Kosten sind Θ(1), und die Potenzfunktion wird um -1 verringert.
- skip(p, k): Die tatsächlichen Kosten sind Θ(l), wobei l ≤ k die Anzahl der übersprungenen Personen ist. Die Potenzfunktion wird um k vergrößert. Die amortisierten Kosten sind also Θ(l) + k = Θ(k) = Θ(1).
- appease(): Die tatsächlichen Kosten sind Θ(m), wobei m die Anzahl der entfernten verärgerten Personen ist. Die Potenzfunktion wird um -m vergrößert. Die amortisierten Kosten sind also Θ(m) - m = Θ(1).

Da die amortisierten Kosten jeder Operation konstant sind, hat jede Operation amortisiert konstante Kosten.





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




