Answer to Question 1


a) Die Funktionen in der Reihenfolge n * log(n), n^2 / log(n), 3 * sqrt{n}, log^2(n), n!, n^n, 3 * log(n) sind in der O-Notation folgendermaßen groß: n * log(n) = O(n * log(n)), n^2 / log(n) = O(n^2), 3 * sqrt{n} = O(sqrt(n)), log^2(n) = O(log(n)^2) = O(log(n)), n! = O(n!), n^n = O(n^n), 3 * log(n) = O(log(n)). Da n * log(n) links von allen anderen Funktionen steht, muss es O(log(n)) sein, damit f \u2208 O(g) gilt.

b) Die Funktion foo(n) benötigt \u0398(n) Zeit, da die Schleife i < n ausgeführt wird und in jeder Iteration die Schleiche j von 1 bis n ausgeführt wird. Somit benötigt die Funktion \u0398(n^2) Zeit.

c) 0. O(n log(n)) 1. Die Anzahl der Zusammenhangskomponenten in einem ungerichteten Graphen kann mit der Tarjan-Algorithmus in O(V + E) Zeit berechnet werden, wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist. Da V = n und E = m, ergibt sich O(n + m) = O(n) für n > m. 1. O(sqrt(n)) 2. O(n) 3. O(n)

d) 1. Ein Listendatensatz ist geeignet, da die Entfernung zum Zielpunkt jeder Teilnehmer\in muss gespeichert werden. Die Operationen, die relevant sind, sind Hinzufügen und Entfernen eines Elements an der Anfangseite der Liste. 2. Ein Array oder eine Hash-Tabelle ist geeignet, da die Position der alten Gartenzwerge in der Reihenfolge der neuen Gartenzwerge gespeichert werden muss. Die Operationen, die relevant sind, sind Hinzufügen und Löschen eines Elements. 3. Ein Stack ist geeignet, da das oberste Buch stets entfernt und durch ein neues Buch ersetzt wird. Die Operationen, die relevant sind, sind Push und Pop.





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




Answer to Question 2


In dieser Aufgabe werden wir uns mit Min-Heaps befassen.

a) Gegeben sei folgender Min-Heap in Zustand 1 zusammen mit der rechts angegebenen Sequenz von Operationen, die diesen Heap schrittweise in verschiedene Zustaende uberfuhren. Zeichne die so entstehenden Zustaende 2, 3 und 4 des Heaps.

![heap-1](figures/heap-1.pdf)

Zur Loesung von Teilaufgabe a) zeichne ich die folgenden Zustaende des Min-Heaps:

2. Zustand: Nach der Operation "insert 7"
![heap-2](figures/heap-2.pdf)

3. Zustand: Nach der Operation "extractMin"
![heap-3](figures/heap-3.pdf)

4. Zustand: Nach der Operation "insert 5" und "insert 6"
![heap-4](figures/heap-4.pdf)

b) In der Vorlesung haben wir gelernt, wie Min-Heaps als Arrays umgesetzt werden koennen. Gib das Array A an, welches den Min-Heap in Zustand 1 aus Teilaufgabe a) repraesentiert.

Die Angabe "Min-Heap in Zustand 1 aus Teilaufgabe a)" impliziert, dass wir den Min-Heap in der Abbildung figures/heap-1.pdf haben. Um diesen Min-Heap als Array darzustellen, mussen wir die Elemente des Heaps in der richtigen Reihenfolge sortieren.

Die Elemente des Min-Heaps in der richtigen Reihenfolge sind: 2, 3, 4, 5, 6, 7.

Somit ist das Array A wie folgt: [2, 3, 4, 5, 6, 7]

c) Sei H ein Min-Heap mit n Elementen. Im Folgenden soll eine Methode reduceToLargerHalf(H) implementiert werden, welche die 2/n kleinsten Elemente aus H in sortierter Reihenfolge ausgibt, indem sie diese aus H loscht. Dazu stehen, neben den Heap-Operationen, die aus der Vorlesung bekannt sind, zusaetzlich noch folgende Operationen zur Verfugung:

- H.size() gibt die Anzahl der Elemente in H zurueck.
- print(x) gibt den Wert des Elements x aus.

Gib den Pseudocode fuer reduceToLargerHalf(H) an.

```java
function reduceToLargerHalf(H) {
  // Initialisiere zwei leere Arrays zur Speicherung der erloschenen Elemente
  let small = []
  let large = []

  // Solange der Heap noch Elemente enthaelt
  while (H.size() > 0) {
    // Entnehme das kleinste Element aus dem Heap
    let smallest = H.extractMin()

    // Fuege es den kleinsten Elementen hinzu
    small.push(smallest)

    // Wenn wir die Anzahl der Elemente im kleinen Array erreicht haben, so beende die Schleife
    if (small.length >= 2 / H.size()) {
      break
    }
  }

  // Sortiere die kleinsten Elemente und drucke sie aus
  let sortedSmall = small.slice(0, 2).sort((a, b) => a - b)
  print(sortedSmall)

  // Sortiere die ubrigen Elemente und speichere sie im groessen Array
  let remaining = H.elements.slice()
  let sortedLarge = remaining.sort((a, b) => a - b)
  large = sortedLarge

  // Rueckgabe des Arrays mit den groessen Elementen
  return large
}
```

d) Gegeben sei ein leerer Heap. Zeige oder widerlege: Für jedes n > N existiert eine Folge von n insert-Operationen, sodass jede dieser insert-Operationen Laufzeit Ω(1) hat. Begruende deine Antwort kurz.

Nein, dies ist nicht moglich. Die Lauf





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




Answer to Question 3


Antwort:

a) Die Reihenfolge der Knoten aus der Priority-Queue, die entnommen werden, ist wie folgt: A, B, C, D, E, F. Die Kanten des zugehörigen Kürzesten-Wege-Baums in der unteren Kopie sind: A -> B (3), B -> C (1), C -> D (2), D -> E (1), E -> F (1).

b) Der fehlerhafte Eintrag in der ersten Tabelle ist der von Knoten D mit der Distanz 12. Dieser Wert ist falsch, weil der kürzeste Weg von A nach D nur eine Länge von 5 hat. Der kürzeste Weg von A nach D führt über Knoten B und C.

Der fehlerhafte Eintrag in der zweiten Tabelle ist der von Knoten F mit der Distanz 11. Dieser Wert ist falsch, weil der kürzeste Weg von A nach F eine Länge von 6 hat. Der kürzeste Weg von A nach F führt über Knoten B, C und E.

c) Um eine solche Graphenkonfiguration zu erhalten, kann man folgende Graphen verwenden:

- Graphen mit 4 Knoten: Es gibt kein solches Graphen, da Dijkstras Algorithmus immer mindestens den Startknoten und ein anderes Knoten besuchen muss, um eine Änderung der Distanz zu erzwingen.
- Graphen mit 5 Knoten: Man kann folgendes Graphen verwenden:

```
A --3-- B --1-- C --1-- D --1-- E --2-- F
|         |         |         |         |
1         2         1         1         1
```

Der kürzeste Weg von S nach T hat eine Länge von 3, aber wenn man S mit 1 und T mit 2 markiert, so dass man den Knoten S und T nicht besucht, kann man die Distanz von S nach T insgesamt 5 Mal ändern.

- Graphen mit 6 Knoten: Man kann folgendes Graphen verwenden:

```
A --1-- B --1-- C --1-- D --1-- E --1-- F
|         |         |         |         |
1         1         1         1         1
|         |         |         |         |
2         2         2         2         2
```

Der kürzeste Weg von S nach T hat eine Länge von 3, aber wenn man S mit 1 und T mit 2 markiert, so dass man den Knoten S und T nicht besucht, kann man die Distanz von S nach T insgesamt 6 Mal ändern.

- Graphen mit n > 3 Knoten: Man kann folgendes Graphen verwenden:

```
A --1-- B --1-- C --1-- D --1-- ... --1-- N
|         |         |         |         |
1         1         1         1         1
|         |         |         |         |
1         1         1         1         1
|         |         |         |         |
...       ...       ...       ...       ...
|         |         |         |         |
1         1         1         1         1
|         |         |         |         |
1         1         1         1         1
|         |         |         |         |
B --1-- A --1-- C --1-- D --1-- ... --1-- N
|         |         |         |         |
1         1         1         1         1
```

Der kürzeste Weg von S nach T hat eine Länge von 2, aber wenn man S mit 1 und T mit 1 markiert, so dass man die Knoten S und T nicht besucht, kann man die Distanz von S nach T insgesamt n Mal ändern.





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




Answer to Question 4


Antwort:

a) In dem Graph aus der Abbildung mit ds = 1 und dt = 3 sind die Via-Knoten die Knoten, die genau die Distanz ds = 1 von s und die Distanz dt = 3 von t haben. In der Abbildung sind diese Knoten a und b markiert.

b) Um in dem Graph Knoten f zu einem Via-Knoten machen, muss die Distanz ds von s nach f die Distanz 1 haben und die Distanz dt von f nach t die Distanz 3 haben. Somit muss die Distanz von s nach f = 1 und die Distanz von f nach t = 2 sein.

c) 1. Falsch: Es kann auch dann einen Via-Knoten geben, wenn ds + dt > dist(s, t).
2. Falser: Es kann mehr als einen Via-Knoten geben.
3. Falsch: Es können Via-Knoten auch außerhalb des kürzesten s-t-Pfads liegen.

d) Dijkstra's Algorithmus kann in einem gerichteten Graphen mit n Knoten und m Kanten in O(n + m) Zeit die Distanz von allen Knoten zu einem gegebenen Knoten x berechnen. Dieser Algorithmus arbeitet iterativ und berechnet die kürzeste Distanz zu x von allen noch nicht berechneten Knoten. Er markiert die berechneten Knoten und geht dann zu den unmarkierten Nachbarn eines markierten Knotens, um deren Distanz zu aktualisieren.

e) Der folgende Algorithmus berechnet alle Via-Knoten in einem gerichteten Graphen mit n Knoten und m Kanten in O(n + m) Zeit:

1. Initialisiere eine Funktion `via_nodes(G, s, t, ds, dt)` mit den Parametern G (der Graph), s (Startknoten), t (Zielknoten), ds (Distanz von s nach s) und dt (Distanz von t nach t).
2. Initialisiere eine Funktion `shortest_path(G, s, t)` mit den Parametern G (der Graph), s (Startknoten) und t (Zielknoten), die mit Dijkstra's Algorithmus die kürzeste Distanz von s nach t berechnet.
3. In `via_nodes` berechne die kürzeste Distanz von s nach t mit `shortest_path(G, s, t)`.
4. Iteriere durch alle Knoten v im Graph G:
   a. Wenn die Distanz von s nach v (`dist(s, v)`) gleich ds und die Distanz von v nach t (`dist(v, t)`) gleich dt ist, füge v den Via-Knoten hinzu.
5. Rühre die Via-Knoten aus.

Der Algorithmus nicht überschreitet die vorgegebene Laufzeit, weil er Dijkstra's Algorithmus verwendet, der in O(n + m) Zeit arbeitet. Zusätzlich iteriert der Algorithmus nur durch alle Knoten im Graph, was in O(n) Zeit erfolgt. Somit hat der Algorithmus eine Gesamtlaufzeit von O(n + m).





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




Answer to Question 5


Antwort:

a) In dem gegebenen Beispiel mit den Steinen 1, 2, 3, 4, 5, 6, 7, 8, 9, 2 hat Alice keine Gewinnstrategie. Sie kann entweder einen Stein nehmen und Bob dann alle übrigen Steine nehmen und gewinnen, oder sie kann drei Steine nehmen und Bob dann nur einen Stein nehmen und gewinnen. Damit Alice gewinnen kann, müsste sie eine Anzahl von Steinen nehmen, die Bob nicht entweder alle oder einen Stein nehmen kann. In diesem Fall gibt es keine solche Anzahl, da 2, 3, 4, 5, 6, 7, 8 oder 9 Steine genommen werden können.

b) Alice kann entscheiden, ob es bei n verbleibenden Steinen eine Gewinnstrategie gibt, indem sie für jede Möglichkeit, wie viele Steine sie nehmen kann, berechnet, was Bob dann tun kann und ob er dann gewinnen kann. Wenn es für jede Möglichkeit keine Gewinnstrategie für Bob gibt, hat Alice eine Gewinnstrategie.

c) Rekurrenz:
X[i] = false, i > 0 und a_i > 1
X[i] = true, i > 0 und (X[i+1] = false oder a_i > a_i+1)
X[0] = false

d) Pseudocode:
function aliceCanWin(a1, ..., an): Bool
  let X = new Array(n+1)
  X[n] = false
  for i from n-1 downto 0 do
    X[i] = false
    if a_i > 1 then
      X[i] = true
      if i+1 <= n then
        if X[i+1] = false or a_i > a_i+1 then
          X[i] = true
  return X[0]





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




Answer to Question 6


Antwort:

a) In Zustand 3, nach der Ausführung der Operationen help(), appease(m) und skip(C6, 2), befindet sich Person C6 am Anfang der Schlange, da sie durch skip(C6, 2) um zwei Plätze nach vorne bewegt wurde. Alle veraürgerten Personen, die vor C6 standen, wurden durch appease(m) entfernt. Somit sind nur noch Person C6 und die Personen hinter ihr in der Schlange übrig. In Zustand 4, nach der Ausführung der Operationen queue(C8), skip(C8, 2) und skip(C8, 1), befindet sich Person C8 am Anfang der Schlange, da sie durch die beiden skip-Operationen um drei Plätze nach vorne bewegt wurde. Alle veraürgerten Personen, die vor C8 standen, wurden durch die skip-Operationen übersprungen. Somit sind nur noch Person C8 und die Personen hinter ihr in der Schlange übrig. Verärgerten Personen werden in den Abbildungen mit einem Kreis umgeben dargestellt.

b) Eine mögliche Sequenz von Operationen, die die Anforderungen erfüllen, ist: queue(P1), queue(P2), queue(P3), queue(P4), queue(P5), queue(P6), queue(P7), queue(P8), queue(P9), queue(P10), help(), skip(P1, 2), appease(2), queue(P11), queue(P12), queue(P13), queue(P14), queue(P15), queue(P16), queue(P17), queue(P18), queue(P19), queue(P20), skip(P1, 1), appease(1), queue(P21), queue(P22), queue(P23), queue(P24), queue(P25), queue(P26), queue(P27), queue(P28), queue(P29), queue(P30), skip(P1, 1), appease(1), queue(P31), queue(P32), queue(P33), queue(P34), queue(P35), queue(P36), queue(P37), queue(P38), queue(P39), queue(P40), skip(P1, 1), appease(1), queue(P41), queue(P42), queue(P43), queue(P44), queue(P45), queue(P46), queue(P47), queue(P48), queue(P49), queue(P50), skip(P1, 1), appease(1). Insgesamt besteht die Sequenz aus 51 Operationen. Es gibt insgesamt drei skip-Operationen, die Laufzeit ist konstant, und es gibt am Ende eine Person (P50), die noch 50 Personen überspringen darf.

c) Jede Operation in der Sequenz kann amortisiert konstante Kosten haben, indem man die Kosten der schlechtesten Fälle (z.B. wenn viele Personen übersprungen werden müssen) mit den Kosten der besseren Fälle (z.B. wenn keine Personen übersprungen werden müssen) verrechnet. Zum Beispiel hat die Operation queue(Px) eine konstante Zeitkomplexität, aber wenn man eine Person hinter einer großen Anzahl an Personen einfügt, kann die Zeitkomplexität der Operation appease() oder skip(Px, k) höher sein. Aber insgesamt bleiben die Kosten konstant, da die häufigen Fälle mit niedrigen Kosten und die seltenen Fälle mit höheren Kosten ausgeglichen werden.





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




