Answer to Question 1


a) Die Funktionen n * log(n), n^2 / log(n), 3 * sqrt{n}, log^2(n), n!, n^n, 3 * log(n) sind alle O(log(n)).

b) Eine mögliche Funktion f, die die Laufzeit von foo(n) minimiert, wäre z.B. f(n) = n^2 / log(n).

c)

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

d)

1. Die Teilnehmenden eines Wettbewerbs sollen mit einem Sandsa\u0308ckchen mo\u0308glichst nah an ein Ziel werfen. Sie haben beliebig viele Versuche, um die Entfernung zum Zielpunkt zu minimieren, wobei immer nur der beste Versuch pro Teilnehmer:in gespeichert wird. Wer den Zielpunkt genau getroffen hat, wirft nicht nochmal. Die Jury mo\u0308chte nach jedem Wurf wissen, wer bisher den besten Versuch hatte, aber den Zielpunkt noch nicht getroffen hat. Eine mögliche Datenstruktur wäre eine Liste, die die Versuche jedes Teilnehmers enthält. Die relevanten Operationen wären:
* Hinzufügen eines neuen Versuchs
* Entfernen eines alten Versuchs
* Bestimmen des aktuellen besten Versuchs
* Bestimmen des aktuellen besten Versuchs eines anderen Teilnehmers
1. Edsger bekommt jeden Tag zwei neue Gartenzwerge von Ada geschenkt. Begeistert mo\u0308chte er Ada immer erzählen, welche alten Gartenzwerge von der Gro\u0308\u00dfe her zwischen den Gro\u0308\u00dfen der beiden neuen Gartenzwerge liegen. Eine mögliche Datenstruktur wäre ein Array, das die alten Gartenzwerge enthält. Die relevanten Operationen wären:
* Hinzufügen eines neuen Gartenzwerges
* Entfernen eines alten Gartenzwerges
* Bestimmen des aktuellen größten Gartenzwerges
* Bestimmen des aktuellen kleinsten Gartenzwerges
1. Eine Lesegruppe verwaltet einen Turm von Bu\u0308chern, wobei das oberste Buch zum Lesen weggenommen oder





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




Answer to Question 2


a) Die Zustände 2, 3 und 4 des Min-Heaps in Zustand 1 sind wie folgt:

Zustand 2:
1. 4
2. 5
3. 6
4. 7
5. 8
6. 9
7. 10
8. 11
9. 12
10. 13
11. 14
12. 15
13. 16
14. 17
15. 18

Zustand 3:
1. 4
2. 5
3. 6
4. 7
5. 8
6. 9
7. 10
8. 11
9. 12
10. 13
11. 14
12. 15
13. 16
14. 17
15. 18

Zustand 4:
1. 4
2. 5
3. 6
4. 7
5. 8
6. 9
7. 10
8. 11
9. 12
10. 13
11. 14
12. 15
13. 16
14. 17
15. 18

b) Das Array A, das den Min-Heap in Zustand 1 aus Teilaufgabe a) repra\u0308sentiert, ist wie folgt:

A = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

c) Der Pseudocode für die Methode reduceToLargerHalf(H) ist wie folgt:

```
reduceToLargerHalf(H):
    n = H.size()
    for i in range(n // 2):
        print(H.popMin())
```

d) Es gibt keine Antwort auf diese Frage, da es keine spezifische Frage oder Unterfrage gibt. 





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




Answer to Question 3


a) Die Reihenfolge der Knoten aus der Priority-Queue, die bei der Ausführung von Dijkstras Algorithmus auf dem obigen Graph entnommen werden, ist: A, B, C, D, E, F, G, H.

b) Der Eintrag von A in D ist fehlerhaft, weil die Distanz des Startknotens mit 0 initialisiert wird und nicht mit 2.

c) Ein Graphen mit n Knoten sowie zwei Knoten s und t, sodass sich bei der Ausführung von Dijkstras Algorithmus mit Startknoten s die La\u0308nge des aktuell bekanntesten ku\u0308rzesten Weges von s zu t insgesamt \u0398(n) Mal a\u0308ndert, ist ein vollständiger Graph mit n Knoten und n-1 Kanten. 





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




Answer to Question 4


a) Die Via-Knoten sind f und g.

b) ds = 2 und dt = 2.

c) 1. Falsch, es kann keinen Via-Knoten geben, wenn ds + dt < dist(s, t).
2. Wahr, wenn ds + dt = dist(s, t), gibt es immer genau einen Via-Knoten.
3. Falsch, es gibt keine Via-Knoten auf einem ku\u0308rzesten s-t-Pfad, wenn dt > dist(s, t).

d) Um die Distanz von allen Knoten zu einem gegebenen Knoten x berechnen zu können, kann man in einem gerichteten Graphen in O(n + m) Zeit die Distanz von jedem Knoten zu x berechnen und die Summe aller Distanzwerte berechnen.

e) Ein Algorithmus, der alle Via-Knoten ausgibt, könnte wie folgt funktionieren:
1. Erstelle eine Liste mit allen Knoten des Graphen.
2. Berechne die Distanz von jedem Knoten zu s und t.
3. Vergleiche die Distanz von jedem Knoten zu s und t mit den gesuchten ds und dt.
4. Markiere alle Knoten, die die gesuchten ds und dt erfüllen.
5. Geben die markierten Knoten als Via-Knoten aus.

Der Algorithmus ist in O(n + m) Zeit implementierbar, da er nur eine Liste durchlaufen und jeden Knoten nur einmal berechnen muss. 





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




Answer to Question 5


A: Alice hat eine Gewinnstrategie, wenn das Spiel mit folgenden Steinen beginnt? Begru\u0308nde deine Antwort. A = \u27e81, 2, 3, 4, 5, 6, 7, 8, 9, 2\u27e9

Antwort: Alice hat eine Gewinnstrategie, wenn das Spiel mit folgenden Steinen beginnt? Begru\u0308nde deine Antwort. A = \u27e81, 2, 3, 4, 5, 6, 7, 8, 9, 2\u27e9

B: Angenommen, Alice wei\u00df fu\u0308r jedes i < n, ob es bei i verbleibenden Steinen fu\u0308r die Person, die gerade am Zug ist, eine Gewinnstrategie gibt. Wie kann Alice entscheiden, ob es bei n verbleibenden Steine eine Gewinnstrategie gibt?

Antwort: Alice kann entscheiden, ob es bei n verbleibenden Steinen eine Gewinnstrategie gibt, indem sie prüft, ob es bei n verbleibenden Steinen möglich ist, genau einen Stein zu nehmen, ohne dass Bob im nächsten Zug gewinnen kann. Wenn dies möglich ist, hat Alice eine Gewinnstrategie.

C: Wir wollen nun ein dynamisches Programm entwickeln, welches berechnet, ob Alice eine Gewinnstrategie hat. Dazu legen wir ein Array X an, um die Teillo\u0308sungen zu verwalten. Dabei gibt X[i] \u2208 {wahr, falsch} an, ob es fu\u0308r die Person, die aktuell am Zug ist, eine Gewinnstrategie gibt, wenn noch i Steine u\u0308brig sind. Stelle die Rekurrenz auf, mit deren Hilfe das Array X korrekt ausgefu\u0308llt werden kann. Hinweis: Achte darauf, auch Basisfa\u0308lle der Rekurrenz anzugeben, falls no\u0308tig.

Antwort: Das dynamische Programm kann mit Hilfe einer Rekurrenz berechnet werden. Die Basisfälle sind X[0] = wahr und X[1] = wahr. Die Rekurrenz ist dann gegeben durch die Bedingung, dass X[i] = wahr, wenn es bei i verbleibenden Steinen möglich ist, genau einen Stein zu nehmen, ohne dass Bob im nächsten Zug gewinnen kann. Wenn dies nicht möglich ist, ist X[i] = falsch.

D: Gib einen Algorithmus in Pseudocode an, der als Eingabe die Elemente a1 , . . . , an erha\u0308lt und in O(n) Zeit ausgibt, ob Alice als Startspielerin eine Gewinnstrategie hat. Verwende folgende Signatur: aliceCanWin(\u27e8a1 , . . . , an \u27e9) : Bool

Antwort: Der Algorithmus kann wie folgt





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




Answer to Question 6


Zustand 1:

- queue(C1)
- help()
- skip(C1, 1)
- queue(C2)
- help()
- skip(C2, 1)
- queue(C3)
- help()
- skip(C3, 1)
- queue(C4)
- help()
- skip(C4, 1)
- queue(C5)
- help()
- skip(C5, 1)
- queue(C6)
- help()
- skip(C6, 1)
- queue(C7)
- help()
- skip(C7, 1)
- queue(C8)
- help()
- skip(C8, 1)
- queue(C9)
- help()
- skip(C9, 1)
- queue(C10)
- help()
- skip(C10, 1)
- queue(C11)
- help()
- skip(C11, 1)
- queue(C12)
- help()
- skip(C12, 1)
- queue(C13)
- help()
- skip(C13, 1)
- queue(C14)
- help()
- skip(C14, 1)
- queue(C15)
- help()
- skip(C15, 1)
- queue(C16)
- help()
- skip(C16, 1)
- queue(C17)
- help()
- skip(C17, 1)
- queue(C18)
- help()
- skip(C18, 1)
- queue(C19)
- help()
- skip(C19, 1)
- queue(C20)
- help()
- skip(C20, 1)
- queue(C21)
- help()
- skip(C21, 1)
- queue(C22)
- help()
- skip(C22, 1)
- queue(C23)
- help()
- skip(C23, 1)
- queue(C24)
- help()
- skip(C24, 1)
- queue(C25)
- help()
- skip(C25, 1)
- queue(C26)
- help()
- skip(C26, 1)
- queue(C27)
- help()
- skip(C27, 1)
- queue(C28)
- help()
- skip(C28, 1)
- queue(C29)
- help()
- skip(C29, 1)
- queue(C30)
- help()
- skip(C30, 1)
- queue(C31)
- help()
- skip(C31, 1)
- queue(C32)
- help()
- skip(C32, 1)
- queue(C33)
- help()
- skip(C33, 1)
- queue(C34)
- help()
- skip(C34, 1)
- queue(C35)
- help()
- skip(C35, 1)
- queue(C36)
- help()
- skip(C36, 1)
- queue(C37)
- help()
- skip(C37, 1)
- queue(C38)






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




