Title: Sem2
Tags: PProg AnW AnW::Wahrscheinlichkeit AnW::Algorithmen AnW::GraphTheory

Q: Wann ist ein Graph \(k\)-zusammenhängend (\(k\)-knoten-zusammenhaengend)?
A: Jeder separator hat mindestens Grösse \(k\) (\(\geq\) k)
(einzige Ausnahme: vollständiger Graph \(K_n\), hier per Definition \((n-1)\)-zusammenhängend)
i.e. - man muss \(\geq k\) Knoten (und deren anliegende Kanten) entfernen, damit \(G\) nicht mehr zusammenhaengend ist
Jeder Kantenseparator hat mindestends Grösse \(k\).
i.e. - man muss \(\geq\) \(k\) Kanten entfernen, damit \(G\) nicht mehr zusammenhängend ist
Facts:
1-zusammenhängend \(\iff\) zusammenhängend
\(k\)-zusammenhängend \(\implies\) \((k-1)\)-zusammenhängend
1.23
1.24

Q: Was ist ein vollständiger Graph? Was ist der Knoten- und Kantenzusammenhang?
A: Ein Graph \(K_n\), der alle möglichen Kanten \(\{u,v\} \in {[n] \choose 2}\) enthält wobei \(V = [n]\).
Knoten- sowie Kantenzusammenhang gleich: \(n-1\) zusammenhängend
kann nicht disconnected durch Entfernen von Kanten/Knoten werden, somit gilt hier die (normale) Definition von k-Zusammenhang nicht (ist jedoch mit Satz von Menger kompatibel).

Q: Was ist die Definition von Pfad und Kreis?
A: Pfad: eine Sequenz \((v_1, v_2, \dots, v_k)\) von verschiedenen Knoten, wobei zwischen aufeinanderfolgenden jeweils eine Kante besteht
Länge: Anzahl der Kanten (Gewicht!), bei \(k\) Knoten \(k-1\)
keine Knoten wiederholt, somit keine Kanten wiederholt
Kreis: ein Pfad wobei \(v_{start} = v_{end}\) (auch: geschlossener Pfad)

Q: Was ist die Definition des d-dimensionalen Hyperwürfels?
A: Der \(d\)-dimensionale Hyperwürfel \(Q_d\) hat die Knotenmenge \(\{0, 1\}^d\) - die Menge aller Sequenzen von \(d\) Nullen und Einsen, wobei zwei Knoten \((a_1 , . . . , a_d )\) und \((b_1 , . . . , b_d )\) genau dann durch eine Kante verbunden werden, wenn es eine und nur eine Koordinate \(i\) gibt, für die \(a_i \neq b_i\) gilt.
Q_3 ist Skellett von normalem D6 Wuerfel

Q: Was ist die Definition eines u-v-Separators (u-v-Kantenseparators)?
A: X ist u-v-Separator wenn:
\(X \subseteq V \setminus \{u, v\}\) eine Knotenmenge, für die u und v in verschiede-
nen Zusammenhangskomponenten von \(G[V \setminus X]\) liegen
X ist u-v-Kantenseparator wenn:
\(X \subseteq E\) eine Kantenmenge, für die u und v in verschiede-
nen Zusammenhangskomponenten von \(G[V,E \setminus X]\) liegen

Q: Was ist die Definition eines Artikulationsknotens und einer Bruecke?
A: v Artikulationsknoten \(\iff G \setminus \{v\}\) nicht zusammenhaengend
e Bruecke \(\iff G \setminus \{e\}\) nicht zusammenhaengend

Q: \(\{x,y\}\) ist Brücke \(\implies\)...
A: \(\{x,y\}\) ist Brücke \(\implies deg(x) = 1\) oder \(x\) ist Artikulationsknoten
(gleichermassen für \(y\))
Jede Brücke hat mindestens einen Artikulationsknoten als Endpunkt
- stimmt nur nicht, wenn graph \(K_2\) ist, also nur zwei verbundene Knoten

Q: Jede Brücke hat mindestens einen Artikulationsknoten als Endpunkt
A: - stimmt nur nicht, wenn graph \(K_2\) ist, also nur zwei verbundene Knoten
Blatt (leaf) ist nie Artikulationsknoten
alle zusammenhängenden Graphen ausser endlich vielen Ausnahmen.
deg(x) = 1 oder x ist Artikulationsknoten

Q: Jeder
Artikulationsknoten grenzt an mindestens eine Brücke
A: für unendlich viele zusammenhängenden Graphen nicht.
zB zwei "vierecke", wobei ein Knoten aus einem mit zwei aus dem anderen verbunden ist

Q: Was sagt der Satz von Menger?
A: G ist k-zusammenhängend \(\iff\) für alle \(u,v\) mit \(u \neq v \in V\) gibt es k intern-knotendisjunkte Pfade \(u \to v\)
G ist k-kantenzusammenhängend \(\iff\) für alle \(u,v\) mit \(u \neq v \in V\) gibt es k intern-kantendisjunkte Pfade \(u \to v\)

Q: Was ist ein bipartiter Graph?
A: Wenn sich V in zwei disjunkte Mengen A und B zerlegen lässt, sodass Kanten von G nur zwischen A und B verlaufen. Jede Kante e muss also einen Endpunkt in A und einen Endpunkt in B haben.
Beispiele:
Hyperwürfel
Pfade
Kreise sind genau dann bipartit, wenn sie gerade Länge haben.

Q: Wie ist eine Eulertour definiert? Wie können wir einfach feststellen, ob eine Graph eine Eulertour enthält?
A: \(:=\) geschlossener Weg (Zyklus), der jede Kante genau ein mal enthaelt
\(\iff\) Grad jedes Knotens gerade (und maximal eine Zusammenhangskomponente mit Kanten)
der Läufer-Algorithmus liefert uns \(O(|E|)\) die Kanten der Eulertour

Q: Was sagt der Satz von Dirac?
Gilt der Satz für jeden Graphen? Was ist mit \(K_2\)?
A: \(G=(V,E)\) mit \(|V| >= 3\) und Minimalgrad \(\delta(G) \geq |V|/2\) hat einen Hamiltonkreis

Q: Wie kann man effizient Artikulationsknoten und Brücken finden?
Gib an:
1. Beschreibung des Algorithmus, Definition von low Zahlen
2. Bedingungen für Artikulationsknoten/Brücke (Hint: root beachten!)
A: Wir führen DFS aus in \(O(|V|+|E|)\)
\(low[v]\) - kleinste DFS (pre) Nummer, die durch gerichteten Pfad aus Baumkanten gefolgt von max. einer Restkante erreicht werden kann.
\(low[v]\) = \(\min\left\{dfs[v], \min_{(v,w) \in E} \left\{{dfs[w] \text{ wenn $(v,w)$ Restkante, $low[w]$ wenn $(v,w)$ Baumkante} }\right\}\right\}\)
\(v\) ist Artikulationsknoten \(\iff\)
1. \(v \neq\) root und \(v\) hat ein Kind \(w\) im DFS-Baum mit \(low[w] \geq dfs[v]\)
    wenn nicht: \(low[w] < dfs[v]\), es gibt einen Pfad von Vorgänger von \(v\) zu \(u\)
2. \(v = root\) und \(v\) hat \(\geq 2\) Kinder im DFS-Baum
"w erreicht maximal v, aber keine Knoten vor v"
Baumkante \(e = (v,w)\) ist Brücke \(\iff low[w] > dfs[v]\)
"w erreicht weder v noch Knoten vor v"
    wenn nicht: es gibt Kante zu \(v\) oder Vorgänger von \(v, \;v\) ist erreichbar durch anderen Weg von \(w\)
eine Restkante ist nie Brücke

Q: Was ist die Definition eines Blocks, was ist die Block-Zerlegung eines Graphen?
A: Wir definieren folgende Äquivalenzrelation:
\(e \,\rho\, f \iff e = f\) ODER es gibt einen Kreis durch \(e\) und \(f\)
Die Äquivalenzklassen sind "Blöcke"
Zwei Blöcke schneiden sich (wenn überhaupt) in genau einem Artikulationsknoten
Block-Zerlegung
A = {Artikulationsknoten} (normalerweise nicht sehr viele)
B = {Blöcke}
\(G = (A \cup B, E_t), \{a,b\} \in E_t \iff a \in A\) adjazent zu Knoten \(b \in B\)
\(\Rightarrow\) bipartit

Q: Was ist die Definition eines Matchings?
Was ist ein perfektes Matching?
Wann überdeckt ein Matching einen Knoten?
A: \(M \subseteq E\) ist ein Matching \(\iff e \cap f = \emptyset\) für alle \(e,f \in M\) mit \(e \neq f\)
"kein Knoten in V ist inzident zu mehr als einer Kante aus \(M\)"
\(M\) überdeckt \(v \iff\) es gibt \(e \in M\) mit \(v \in e\)
\(M\) ist perfekt \(\iff |M| = |V|/2\)
"jeder Knoten wird durch genau eine Kante aus \(M\) überdeckt"
\(|V|\) ist ungerade \(\implies\) es gibt kein perfektes Matching von \(V\)
Algorithmen
Greedy-Matching: wähle zufällig eine Kante, füge sie zu M hinzu und lösche sie und alle inzidenten Kanten bis \(|E| = \emptyset\)
\(\implies\) findet inklusionsmaximales Matching in \(O(|E|)\)
Augmentierende Pfade (in bipartitem Graphen): finde augm. Pfad \(P\) (mit BFS in Stufen), verbessere \(M\) mit \(M = M \oplus P\) bis \(M\) maximum (kein augm. Pfad mehr in \(G\))
\(\implies\) kardinalitätsmaximales Matching in \(O( {|V|}*|E|)\)
Hopcroft-Karp (in bipartitem Graphen): Verbesserung von augm. Pfaden: kardinalitätsmaximales Matching in bipartitem Graphen in \(O(\sqrt {|V|}*|E|)\)
(gleiche Laufzeit auch allgemein möglich)
Gabow: Finden eines perfekten Matchings in \(2^k\)-regulärem bipartiten Graphen in
\(O(|E|)\): Berechne Eulertour, lösche jede zweite Kante, iteriere
(lässt sich verallgemeinern für \(k\)-reguläre bipartite Graphen)
Gabow: \(O(|V|^3)\) für kardinalitätsmaximales Matching von kleinstmöglichem Gewicht

Q: Wann ist ein Matching \(M\) inklusionsmaximal? Wann kardinalitätsmaximal?
A: M ist inklusionsmaximal (maximal) \(\iff\) es gibt kein \(M' \subseteq E\) mit \(M \subseteq M'\) und \(|M'| > |M|\)
"man kann keine weitere Kante hinzufügen, sodass \(M\) noch ein Matching ist"
M ist kardinalitätsmaximal (maximum) \(\iff\) es gibt kein \(M' \subseteq E\) mit\(|M'| > |M|\)
"es gibt kein grösseres Matching"
\(M\) kardinalitätsmaximal\(\implies M \)inklusionsmaximal
Satz:
\(|M_{inc}| \geq |M_{max}|/2\)

Q: Was sagt der Satz von Hall (Heiratssatz)?
Für einen bipartiten Graphen \(G = (A \uplus B, E)\) ...
A: Sei \(G = (A \uplus B, E)\) ein bipartiter Graph.
Es gibt ein Matching \(M\) mit \(|M| = |A| \iff |X| \leq |N(X)|\) für alle \(X \subseteq A\)
Wenn \(|N(X)| < |X|\), können wir nicht jeden Knoten aus \(X\) matchen, somit kein Matching mit \(|A|\) möglich
Satz von Hall + \(|A| = |B|\)
Wie oben: Wenn \(|N(X)| < |X|\), können wir nicht jeden Knoten aus \(X\) matchen, somit kein perfektes Matching möglich

Q: Jeder Graph der eine gerade Anzahl Knoten und einen Hamiltonkreis hat, enthält _____________.
A: Jeder Graph der eine gerade Anzahl Knoten und einen Hamiltonkreis hat, enthält ein perfektes Matching.
Konstruktiver Beweis - auf Hamiltonkreis jede zweite Kante zu Matching hinzufügen

Q: Was sagt der Satz von Brooks über (fast) alle Graphen bzgl. Faerbungen?
A: Für \(K_n\) und \(C_{2n+1}\) gilt \(\chi(G) = \Delta(G) + 1\)

Q: Mit wie vielen Kanten laesst sich jeder Sterngraph faerben? Warum?
A: 2, obwohl der Maximalgrad n-1 ist (Mitte des Sterns)

Q: Was ist die Definition eines diskreten Wahrscheinlichkeitsraums?
A: Ergebnis des Zufallsversuch ist \(x \in \Omega\) (in unserem Fall abzählbar)
Ein Ereignis \(x\) tritt ein, wenn \(x \in A\)
definiert durch Ergebnismenge und Wahrscheinlichkeiten von Elementarereignissen

Q: Was sagt der Additionssatz? (für paarweise disjunkte Ereignisse)
A: paarweise disjunkt, sonst haben wir Boolsche Ungleichung

Q: Wie kann man die Siebformel (Kontext: diskrete Wahrscheinlichkeitsräume) anwenden? (bzw.: Was ist das Prinzip von Inklusion/Exklusion?)
\(Pr[\bigcup_{i=1}^n A_i] =\)?
A: Überschneidungen der Ereignisse duerfen nicht doppelt gezählt werden
zB. für n = 3:
\(Pr[A_1 \cup A_2 \cup A_3] = Pr[A_1] + Pr[A_2] + Pr[A_3] - Pr[A_1 \cap A_2] - Pr[A_2 \cap A_3] - Pr[A_1 \cap A_3]+ Pr[A_1 \cap A_2 \cap A_3]\)
+ obere Schranke (l ungerade)
- untere Schranke (l gerade)
Auf Laplace-Raum Anwenden: Siebformel, die man bei Kardinalität von Mengen anwenden kann zB.
zB; Zahlen zwischen 1 und 10^10, die nicht von 2,3,5 teilbar sind.
1- teilbare Zahlen
teilbare = total/2 + total/3 + total/5 - total/lcm(2,3) - total/lcm(2,5) - total/lcm(3,5) + total/lcm(2,3,5)

Q: Wie kann man mit der Boolschen Ungleichung (Union Bound) die Wahrscheinlichkeit der Vereinigung beliebiger Ereignisse abschätzen?
A: gilt immer, da wir einfach alle Wahrscheinlichkeiten addieren und nicht disjunkte Ai, Aj ignorieren

Q: Was ist die Definition eines Laplace-Raums?
A: Alle Elementarereignisse haben die selbe Wahrscheinlichkeit \(P[\omega] = \frac{1}{|Q|}\)
Somit gilt:
das Ergebnis des modellierten Zufallsexperiments auf Ω ist uniform verteilt/gleichverteilt

Q: Wie ist die bedingte Wahrscheinlichkeit \(Pr[A | B]\) definiert?
A: Intuition:
Weitere Intuition:
Wir nehmen von der Wahrscheinlichkeit, dass A und B passieren, \(Pr[B]\) wieder heraus, bzw. \(/Pr[B]\) ist skalierung auf neuen Wahrscheinlichkeitsraum
Weitere Fakten:
\(Pr[* | B]\)bildet eigenen Wahrscheinlichkeitsraum

Q: Wie können wir \(Pr[A_1 \cap \dots \cap A_n]\) berechnen?
Was sagt der Multiplikationssatz?
A: Proof:
Alle Terme außer \(Pr[A_1 \cap \dots \cap A_n]\) (letzter Term!) kürzen sich!

Q: Was sagt der Satz der totalen Wahrscheinlichkeit? Wie können wir \(Pr[B]\) mit (u.a.) bedingten Wahrscheinlichkeiten berechnen?
\(Pr[B] =\)
A: Können es auch so schreiben:
\(Pr[B] = \sum Pr[B \cap A_i]\)
\(A_i\) müssen paarweise disjunkt sein!
Aufteilung der Ergebnismenge, zB \(Pr[B \,|\, \, A]\) und \(Pr[B \,|\, \text{not}\, A]\)
Intuition: \(A_i\) covern die gesamte Ergebnismenge (bzw. zumindest B) - somit haben wir insgesamt die Wahrscheinlichkeit, dass B eintritt, wenn davor irgendetwas eingetreten ist

Q: Was sagt der Satz von Bayes? Inwiefern gibt er uns eine weitere Möglichkeit, \(Pr[A | B]\) zu berechnen?
A: \(A_i\) müssen paarweise disjunkt sein! (da wir den Satz der totalen Wahrscheinlichkeit anwenden)
Auch philophisch sehr interessant

Q: Gib jeweils ein Beispiel einer solchen Situation an!
A: geordnet mit Zurücklegen:
- Anzahl möglicher Versuchsausgänge bei \(k\) Münzwurfen mit \(n = 2\) (mögliche Versuchsausgänge bei einem Münzwurf). Bei jedem Münzwurf gibt es zwei Möglichkeiten, somit \(2*2*\dots*2 = 2^k\) gesamt
geordnet ohne Zurücklegen:
- Anzahl verschiedener Sequenzen von Farben beim Ziehen von \(k\) Kugeln aus Urne mit \(n\) Kugeln
ungeordnet mit Zurücklegen:
- Think of (n-1 + k) positions. Then you want to choose the position of (n-1) "separators" such that if "separator" y is at position j all spaces between "separator" (y-1) and y are allocated to the y-th element of the set . ---|------|---|--........
- You have k instructions that say "one of this type" and n-1 instructions that say "switch to the next type", so that's k + n-1 in total, with k that have to be "one of this type"
- https://math.stackexchange.com/questions/964801/how-to-use-ncrn-k-with-unordered-sampling-with-replacement
ungeordnet ohne Zurücklegen:
- Anzahl \(k\)-elementiger Teilmengen einer \(n\)-elementigen Menge

Q: Wann sind Ereignisse \(A_1, ..., A_n\) unabhängig?
A: Für alle Teilmengen! Kann umständlich werden (\(O(2^n)\)), bei 2 Ereignissen aber noch einfach

Intuition: \(A, B\) unabhängig \(\iff \overline A , B\) unabhängig

Q: Was ist die Definition einer Zufallsvariable?
A: Eine Zufallsvariable ist eine Funktion\(X: \Omega \to \mathbb{R}\)

Q: Wie funktioniert der Greedy-Färbungs-Algorithmus?
Beantworte dafür folgende Fragen:
- Was können wir mit ihm berechnen?
- Was ist die Laufzeit?
- Mit wie vielen Farben kommt der Algorithmus aus, wie können wir das beeinflussen (Heuristik)?
- Wie lautet der Pseudocode?
A: Greedy-Färbung (\(O(|E|)\)):
c ist minimum der Farben, die noch von keinem Nachbar verwendet wird
Verwendet maximal \(\Delta + 1\) viele Farben, kommt ganz auf Anfangs gewählte Reihenfolge an (\(\Delta := max_{v \in V} \;deg(v)\))
- Für alle Graphen G gibt es eine Reihenfolge, mit der Greedy-Färbung mit \(\chi(G)\) Farben auskommt
- Andererseits: Es gibt eine Reihenfolge, mit der ein bipartiter Graph mit \(|V|/2\) vielen Farben gefärbt wird
Heuristik:
\(|N(v_i)\; \cap\; \{v_1,\; \dots, \;v_{i-1}\} | \leq k\) für alle \(i\) mit \(2 \leq i \leq n \implies\) Greedy-Färbung braucht \(\leq k+1\) Farben (siehe Pseudocode, \(c[v_i]\) ist maximal \(k+1\))
(\(v_i\) hat höchstens \(k\) bereits gefärbte Nachbarn)
Somit machen wir folgendes:
\(v_n :=\) Knoten mit kleinstem Grad. Lösche \(v_n\). \(v_{n-1} :=\) Knoten mit kleinstem Grad im Restgraph. Lösche \(v_{n-1}\).
Repeat
In jedem Subgraph gibt es \(v\) mit \(deg(v) \leq k \implies\) Heuristik liefert Reihenfolge für \(k+1\) Farben

Q: Wie funktioniert der Greedy-Matching-Algorithmus? Was können wir mit ihm berechnen, worauf kommt es an, was ist die Laufzeit?
A: bestimmt inklusionsmaximales Matching in \(O(|E|)\)
da wir immer e und alle inzidenten Kanten löschen, sind alle verbleibenden Kanten in \(E\) unüberdeckt
The key idea is that every edge in a non maximum matching is incident to one edge in a maximum matching (as if it's not incident to any in that matching then we can add it to the maximum matching) and at most two

Was ist die Definition des Erwartungswerts einer Zufallsvariable \(X\)?

Q: Was ist die Definition einer Indikatorvariable? Wofür ist das Konzept nützlich?
\(X_{\overline A} =\) \(B=A_1 \cap \dots \cap A_n \implies X_B = \)
\(C=A_1 \cup \dots \cup A_n \implies X_C = \)
A: \(X: \Omega \to \{0,1\}\) mit \(X_A(\omega) = 1 \iff \omega \in A\)
\(E[X_A] = Pr[A]\)
Rechnen mit Indikatorvariablen:
\(X_{\overline A} = 1-X_A\) \(B=A_1 \cap \dots \cap A_n \implies X_B = X_{A_1} * \dots * X_{A_n}\)
\(C=A_1 \cup \dots \cup A_n \implies X_C = 1-X_{\overline C} = 1 - \prod_{i=1}^n X_{\overline A_i}\)
Beispiel:
Nützlich mit Linearität des Erwartungswerts, macht Berechnungen oft viel einfacher

Q: (Hint: gehe über \(\omega \in \Omega\))
A: L 2.29 Erwartungswert

Beweise:

Q: Inwiefern ist der Erwartungswert linear?
(Linearität des Erwartungswertes)
A: \(X = a_1 X_1 + ... + a_n X_n + b \implies E[X] = a_1E[X_1 ] + ... + a_nE[X_n] + b\)

Q: Was ist die Definition der Dichtefunktion und Verteilungsfunktion?
A: Dichtefunktion: weist allen Zahlen (in R) die Wahrscheinlichkeit zu, dass die Zufallsvariable diese Zahl annimmt
\(f_x: \mathbb{R} \to [0,1], \;x \mapsto Pr[X=x]\)
Verteilungsfunktion: weist allen Zahlen (in R) die Wahrscheinlichkeit zu, dass die Zufallsvariable X diese Zahl oder eine kleinere annimmt
\(F_x: \mathbb{R} \to [0,1], \; x \mapsto Pr[X \leq x]\)
definieren jeweils die Zufallsvariable eindeutig

What is the speedup of a program?

Q: What does Amdahl's law state? Derive it! What upper bound for \(S_p\) does it give us?
A: - fixed workload
- gives upper bound on speedup achievable with p processors (optimize time it takes to complete fixed amount of work)
Derivation:
\(f\) ... seq part of OG part of program (that's only executed once)
\(S_p = \frac{\frac{W_p}{T_p}}{\frac{W_1}{T_1}}\)
Amdahl: \(W\) constant, hence \(S_p = \frac{T_1}{T_p} = \frac{fT + (1-f)T}{fT+\frac{(1-f)T}{p}} = \frac{1}{f+\frac{1-f}{p}}\)
In a graph: function with decreasing growth rate, always bounded!
Some background:
in some ways "pessimistic": not false per se but makes assumptions that are not adequate for many concurrent workloads
\(\Rightarrow\) often we don't want to optimize just for execution time but rather execute more in the same time (e.g. computer game ray tracing)
(also different parts of program can have different parallelizability, ...)
"Amdahl’s law considered a fixed workload and provides us with an upper bound on the speedup achievable when increasing the number of processors at our disposal"
even with a ton of processors p, there is still the serial part left, e.g. f = 0.25, we can achieve a speedup of at most 4

Q: What does Gustafson's law state? Derive it!
A: - fixed time (but no fixed workload)
- we try to do as much as we can in given time with \(p\) processors (optimize amount work done), parallel work per processor is fixed
- (sequential part does not increase with increased work!)
\(f\) ... seq part of OG part of program (that's only executed once)
if there was no serial work, \(S_p\) would be \(p\)
Derivation:
\(S_p = \frac{\frac{W_p}{T_p}}{\frac{W_1}{T_1}}\)
\(T\) ist konstant
\(\Rightarrow S_p = \frac{W_p}{W_1} = \frac{f * W + (1-f) * W * p}{W} = f + (1 - f) * p\)
In a graph: linear function, unbounded speedup!

Wie ist folgende Wahrscheinlichkeit allgemein definiert?

Q: How do synchronized blocks and wait/notify in java work, what are they good for?
A: each java object has a monitor (that can be locked/unlocked by a thread)
 - only one thread at a time may hold the lock on a monitor
 - other threads attempting to lock that monitor are blocked until they can get lock
synchronized(o) { ... }
 - thread calling tries to lock monitor of o, does not proceed until it has lock
 - once execution is completed, unlock op. is performed on monitor of o
o should not be of a wrapper type (Integer, ...)
each java object also has wait set (of threads) which we can manipulate as follows:
(wait/notify always within synchronize block!!!)
o.wait()
places thread calling method in wait set of object o, releases lock of o
o.notify()
exactly one thread in wait set of o gets woken up, attempts to get lock of o back
- as soon as you write to something that can change a waiting condition
o.notifyAll()
all threads in wait set of o get woken up and try to get the lock
blocked state: competing to acquire locked
waiting state: waiting in wait set
example:
wait/notify are useful to make sure no deadlocks can happen

Q: How does the ExecutorService framework work? What is it good for, what are problems?
A: extends Callable<E> \(\Rightarrow\) E call
extends Runnable \(\Rightarrow\) void run
problem: running out of threads. not good for divide and conquer implementations. waiting threads can't help others during that time
waiting for other tasks to complete will block the current thread. If your executor service has a fixed number of threads, it might deadlock if the last running thread waits for another task to complete.

Q: How does the ForkJoin framework work? What are it's advantages compared to ExecutorService?
In Java implementations, which classes do we have to extend (to get return value/no return value)?
A: uses ExecutorService but has own scheduler that has queue per thread and employs work stealing:
 - first considers tasks in own queue, if none left (e.g. only waiting on other threads) can steal work from other threads
Much better in situations where threads have to wait for other threads - they can help other threads during that time
-----------
ForkJoinPool.invoke(ForkJoinTask<T> task) - Performs the given task, returning its result upon completion.
inside compute method (which returns Future) of: Task extends RecursiveTask<V>:
task.fork() - spawn new task
task.join() - wait for task to complete, returns result
(RecursiveAction also possible, doesn't return <V>
we can also run the compute method which is fine here for optimizing a bit by hand)
internally creates DAG of the tasks
analysis (e.g. in task graphs)
Good for analysis as we know the runtime is asymptotically optimal

Q: A pipeline is balanced \(\iff\)
(assuming one execution unit per stage only)
A: A pipeline is balanced \(\iff\) no stage is longer than the first
\(T\) ... longest stage
\(n\) ... number of stages
\(L\) ... sum of length of stages
throughput: \(\frac{1}{T}\) (elements/time)
latency (only if balanced): \(L\)
total duration: \(L + (n-1) * T\) (time)

Q: Wann ist eine Zufallsvariable bernoulli-verteilt? Gib die Dichtefunktion \(f_x\) an!
Was sind: \(E[X], Var[X]\)?
A: \(W_X = \{0,1\}\)
\(Pr[X=1] = p\)
\(Pr[X=0] = 1-p\)
\(E(X) = p\)
\(Var(X) = E(X^2) - E(X)^2 = p - p^2 = p(1-p)\)
Beispiel: Münzenwurf, Indikator für Kopf

Q: Wann ist eine Zufallsvariable binomialverteilt? Gib die Dichtefunktion an! Was sind \(\mathbb{E}[X]\), \(Var[X]\)?
A: \(n *\) Bernoulli-Experiment (mit gleichem p), wie oft tritt das Ereginis ein?
\(Var(X) = n * Var(Bernoulli(p)) = np(1-p)\)
Beispiel: mal Münzenwurf und wir zählen wie oft Kopf vorkommt

Q: Wann ist eine Zufallsvariable geometrisch verteilt? Gib die Dichte- und Verteilungsfunktionen \(f_x\) und \(F_x\) (Hint: Gegenw'keit!) an! Inwiefern ist so eine Zufallsvariable gedächtnislos?
A: \(X :=\) Anzahl Versuche bis und einschliesslich erstem Erfolg (zB. Münzwürfe bis erstes Mal Kopf geworden wird)
\(p\) ... Erfolgswahrscheinlichkeit pro Versuch
\(E(X) = \sum_{k=1}^{\infty} P(X \geq k) = \sum_{k=1}^{\infty} (1-p)^{n-1} = \frac{1}{1-(1-p)}=\frac{1}{p}\)
\(Var(X) = \frac{1-p}{p^2}\)
Extra Fakten:
- Herleitung von \(F_X(x)\):
mit Partialsumme \(s_n = \sum_{i=1}^{n}ar^{i-1}\):
oder mit Gegenwahrscheinlichkeit
- Gedächtnislos:
- Beweis von \(E(X) = 1/p\):
- Alternativer Beweis von \(E[X] = 1/p\):
(\(K_1\) := Kopf im ersten Wurf)

Q: Hint: Bedingt auf X > s
A: S 2.45
Gedächtnislosigkeit
W'keit, dass nach s Versuchen nach weiteren t Versuchen Ergebnis kommt ist W'keit dass nach t Versuchen Ergebnis kommt

Q: Wann ist eine Zufallsvariable \(X\) negativ binomialverteilt mit Ordnung \(n\)? Was ist die Dichtefunktion \(f_z(z)\)? Was sind \(E(X), Var(X)\)?
A: Warten auf \(n-\)ten Erfolg, \(n\) mal unabhängige geometrisch verteilte Zufallsvariablen (zB. \(X:=\) Anzahl Würfe bis \(n\) mal Kopf geworfen wurde)
\(E(X) = n*1/p\)
\(Var(X) = n*\frac{1-p}{p^2}\)
Idee: letzter Durchgang muss Erfolg sein, andere \(n-1\) Erfolge können bei jeglicher "Position" sein, wobei es \(z-1 \choose n-1\) verschiedene Möglichkeiten dafür gibt
Beweis von \(E(X)\):
\(X_i\) = Anzahl Experimente nach (i-1)-tem Erfolg bis i-tem Erfolg (\(X_i -Geo(p)\)), \(E[X_i] = 1/p\)
Durch Linearität von Erwartungswert: \(E(X) = \sum_{i=1}^nE(X_i) = n*1/p\)
Varianz analog, Linearität gilt da \(X_i\) unabhängig sind

Q: Task graphs - how are they defined (what's their use?), what do the following mean?
- \(T_1\) (work)
- \(T_p\)
- \(T_\infty\) (span)
- speedup
- parallelism
compute the above values in the below task graph:
A: A task graph is a directed graph \(G=(V,E)\) where \(e=(u,v) \iff u\) is a dependency of \(v\) (\(u\) has to be computed before \(v\)'s execution can be started) \(\to\) models ForkJoin program execution
Further, there is a cost function \(c: V \to \mathbb{N}\)
- \(T_1\) (work, sum of costs) \(:= \sum_{v \in V} c(v)\)
- \(T_p\) (execution time on p processors): (depends on scheduler, tasks usually ask for the minimum)
- \(T_\infty\) (span, critical path) \(:=\) longest path from root to sink, \(\max_{P: \text{ path in G}} \;\sum_{v \in P}c(v)\)
\(\frac{T_1}{T_p} :=\) speedup
\(\frac{T_1 }{ T_\infty}:=\)  "parallelism" (best speedup possible), "wider" graph better
work law (lower bound on execution time, at best linear speedup):
\(T_p \geq T_1 / p\)
span law (critical path always has to be executed, no matter how many processors):
\(T_p \geq T_\infty = \lim_{p \to \infty}T_p\)
aufpassen: nodes sind tasks normalerweise, auch zB. u.U. Variablen

Q: Wann sind Zufallsvariablen \(X_1, ..., X_n\) unabhängig?
A: (gemeinsame Dichte gleich Produkt der Randdichten)
Jede Zufallsvariable "enthält" sozusagen mehrere Ereignisse, die wir alle auf Unabhängigkeit zu den anderen Zufallsvariablen prüfen
Weiteres:
Bei Indikatorvariablen \(X, Y\) (nicht bei 3 oder mehr!):
\(X, Y\) unabhängig \(\iff f_{x,y}(1,1) = f_x(1) * f_y(1)\)
\(X_1, \dots, X_n\) unabhängig \(\implies\) alle Teilmengen auch unabhängig

Q: Was sagt die Waldsche Identität?
A: Beweis:

Q: Wie ist die Varianz einer Zufallsvariable X definiert? Wie können wir sie (einfacher) berechnen? Wann gilt folgendes:
\(Var(X+Y) = Var(X)+Var(Y)\)
\(Var(X*Y) = Var(X)*Var(Y)\)
A: \(Var[X] := E[(X-E[X])^2]\)
Berechnung fast immer so:
\(Var(-X) = Var((-1)*X) = (-1)^2*Var(X) = Var(X)\)
- Linearität bei unabhängigen Zufallsvariablen
- Multiplikativität meistens nicht
- ("eine Stufe unter Erwartungswert bezüglich Rechenregeln")

Q: What is a bad interleaving? Give an example!
A: to prevent bad interleaving: synchronization between threads, ...
example: concurrent increments
Generally we mean interleavings of statements in program order. However, definition allows for any kind of interleaving (potentially caused by compiler too!)

What is the definition of concurrency? What is the definition of parallelism?

In what sense does the JVM have to warm-up?

Q: What is the definition of throughput (in the context of pipelines)?
What is the difference between asymptotic throughput and lead-in throughput?
A: zwei Definitionen (erstere ist einfacher, beide in Ordnung bei Prüfung):
- throughput: \(\frac{1}{T}\) (elements/time)
- lead-in throughput: \(\frac{n}{duration}\) (elements/time)
A pipeline is balanced \(\iff\) no stage is longer than first
\(T\) ... longest stage
\(n\) ... number of execution elements (in DDCA this would be instructions)
\(L\) ... sum of length of stages (of one execution element)
latency (only if balanced): \(L\)
duration: \(D = L + (n-1) * T\) (time)

Q: What is the definition of latency (in the context of pipelines)?
A: time to process one work item (in DDCA: instruction) - "length" of all elements of one work item
\(\Rightarrow\) sum of length of all stages, \(L\)
only defined for balanced pipelines
A pipeline is balanced \(\iff\) no stage is longer than the first
\(T\) ... longest stage
\(n\) ... number of execution elements
\(L\) ... sum of length of stages
throughput: \(\frac{1}{T}\) (elements/time)
latency (only if balanced): \(L\)
total duration: \(L + (n-1) * T\) (time)

What is instruction level parallelism (ILP)?

What is divide and conquer style parallelism? What are two common patterns?

How is efficiency in the context of analysis of parallel programs defined?
Hint: efficiency per core in terms of speedup

Q: How can we compute the total duration \(D\) of a fully used pipeline?
A: duration: \(L + (n-1) * T\) (time)
A pipeline is balanced \(\iff\) no stage longer than first
\(T\) ... longest stage
\(n\) ... number of execution elements (in DDCA this would be instructions)
\(L\) ... sum of length of stages (of one execution element)
throughput: \(\frac{1}{T}\) (elements/time)
lead-in throughput: \(\frac{n}{duration}\)
latency (only if balanced): \(L\)
duration: \(D = L + (n-1) * T\) (time)

Q: How are the following terms defined?
- mutual exclusion
- critical section
A: - mutual exclusion
not more than one thread can execute code in critical section at one timestep
- critical section
pieces of code that satisfy the following:
1. Mutual exclusion
2. Deadlock-freedom
3. Starvation-freedom
Reference:

What does starvation mean (in the context of threads)?

Q: How is speedup defined?
A: oder auch:
\(S_p = \frac{\frac{W_p}{T_p}}{\frac{W_1}{T_1}}\)
Amdahl: \(W\) constant, hence \(S_p =\frac{T_1}{T_p}\)
Gustafson: \(T\) constant, hence \(S_p =\frac{W_p}{W_1}\)

What is a liveness property?

Q: What is vectorisation?
Hint: single op on ...
A: i.e. special instruction that runs single operation on whole array/segment of data

What is busy waiting?

Q: When does a program have a data race? Give an example!
Give one more general definition (1) and the one used by Java (2) (Hint: variable accesses)!
A: 1. General Definition:
2. Java Definition
- multiple threads access a shared variable
- at least one of the accesses is a write
- the accesses are not "properly synchronized"
"properly synchronized" depends on PL. In context of JMM: volatile, locks, ...
anderes Beispiel:

Q: How is parallelism (max speedup) defined?
A: \(p \to \infty\)
äquivalent:
\(T_p \leq T_\infty\)

What is a process? What does multiprocessing mean?

Q: How is the parallel execution time \(T_p\) defined?
A: Amdahl: \(T_p \geq f * T_1 + \frac{(1 - f) * T_1}{p}\)
\(T_\infty = f * T_1\)
\(S_\infty = 1 / f\)

What is work partitioning, what is it good for? Which task granularity is ideal?

Q: What is the definition of a livelock?
A: \(\iff\) loop in state diagram (excluding CS!)
example:

What does locality mean in the context of parallel programming?

Q: Was sagt die Ungleichung von Markov? Leite sie aus der Definition des Erwartungswerts her!
A: \(X(\omega) \geq 0\) für alle \(\omega \in \Omega\)
\(t > 0\)
\(\Rightarrow Pr[x \geq t] \leq \frac{E(X)}{t}\)
nur für \(X\), das nur nicht-negative Werte annimmt! Liefert manchmal bessere bounds als Chebyshev

Q: Was sagt die Ungleichung von Chebyshev? Leite sie aus der Ungleichung von Markov her!
Hint: Chebyshev quadrieren!
A: Sei \(t > 0\)
\(\Rightarrow Pr[|X-E(X)| \geq t] \leq \frac{Var(X)}{t^2}\)
- nur für grosse \(t\) sinnvoller bound
- gute Idee: \(t\) als \(C * \sqrt{Var(X)}\) waehlen, dann kürzt sich \(Var(X)\) weg und es bleibt \(\frac{1}{C^2}\)
Beweis:

Welche der folgenden Gleichungen gelten, und wann?

Q: Wann gilt Multiplikativität des Erwartungswerts?
(also folgendes: \(E(X*Y) = E(X) * E(Y)\))
A: nur wenn \(X_1,\dots X_n\) unabhängig

Q: Wann gilt \(Var[X* Y] = Var[X] * Var[Y]\)?
A: Gilt im Allgemeinen nicht

Q: Wie funktioniert der Miller-Rabin Primzahltest?
A: the idea of miller rabin is that iff n is prime, Z_n is a field and x^2 = 1 => x in {1, -1}.
so if we find some x such that x^2 = 1 but x is not in {1,-1} we know that Z_n is not a field and n not prime.
the algorithm does the same as the one on wikipedia (which makes the main point of the algorithm a bit clearer imo), it might just terminate earlier when it's already clear what the sequence of a^(2^i d) will be
- Wähle \(a \in \{2, ..., n-1\}\) uniform:
- \(a^{\frac{(n-1)}{2}} \in \{1,n-1\}\) wenn \(a\) prim ist
        - falls \(n-1\): andere Basis
        - falls andere Zahl: return false, wir haben Zertifikat gefunden!
        - falls \(a^{\frac{(n-1)}{2}}=1\): wiederhole Schritt 2 für \(a^{(n-1)/4}\), \(a^{(n-1)/8}\), ... bis \(a^d\) mit ungeradem \(d\) (dann können wir nicht mehr weiter die Wurzel ziehen). Falls auch = 1, return true
- "nicht prim" immer richtig
- \(Pr[\text{"prim"}\,|\, \text{nicht prim}] \leq 1/4\)
- Laufzeit: \(O(poly(\log n))\)
Wenn \(n\) prim ist, muss gelten (für alle \(a\)): \(a^{n-1} = 1 \mod{n}\) (kleiner Satz von Fermat)
Ausserdem gilt:
\(x^2 = 1 \implies x \in \{1,-1\}\)
Proof:
\(x^2 = 1 \implies x^2 - 1 = (x+1)(x-1) = 0\)
Hence \(x+1 = 0\) or \(x-1 = 0\) which follows \(x = 1\)or \(x = -1 =n-1\)
Alle Algorithmen haben einseitigen Fehler. Falls \(n\) Primzahl: immer korrekte Ausgabe.
----------------------------
Weitere Algorithmen:
Fermat-Primzahltest:
Wähle \(a \in \{2, ..., n-1\}\) uniform:
(if \(\gcd(a, n) > 1\) oder) \(a^{n-1} \neq 1\): return false
else: return true
- "nicht prim" immer richtig
- \(Pr[\text{"prim"}\,|\, \text{nicht prim}] = \frac{|PB_n|}{n-1}<1/2\) wenn \(n\) nicht Carmichael \(\implies\) Verbesserung auf \(\frac{1}{2^k}\) durch k*Wiederholung
\(PB_n\) = \(\{a \in Z_n^* \,| \,a^{n-1} = 1\}\)
\(n\) ist Carmichael Zahl \(\iff n\) nicht prim, \(PB_n = Z_n^*\)
Test failed bei allen a \(\in PB_n\), somit in \(\frac{|PB_n|}{n-1}\) der Fälle. Falls \(n\) keine Carmichael-Zahl ist (\(PB_n \neq Z_n^*\)), gilt nach Lagrange-Theorem: \(|PB_n| < \frac{|Z_n^*|}{2}\) und somit \(\frac{|PB_n|}{n-1} < 1/2\)
Euclid-Primzahltest (GGT):
Wähle \(a \in \{2, ..., n-1\}\) uniform:
if \(\gcd(a, n) > 1\): return "nicht prim"
else: return "prim"
- "nicht prim" immer richtig
- \(Pr[\text{"prim"}\,|\, \text{nicht prim}] = \frac{|Z_n^*|}{n-1}\) (kann sehr schlecht sein, zB. für \(n=p^2, p\) prim)
- Runtime: \(O(\log(a*n)^3)\)für Euclidean Algorithm
Zertifikate  für \(n\) nicht prim:
- Triviales: \(a\), sodass \(a | n\) \(\implies\) wir müssen nur bis \(\sqrt{n}\) überprüfen
- Euklid: \(a\), sodass \(\gcd(a,n) > 1\)
- Fermat: \(a\), sodass \(a^{n-1} \neq 1 \mod n\)
- Miller-Rabin: Sei \(n-1 = 2^kd, d \in \mathbb{N}\) ungerade. \(a\), sodass:

Q: Kann ein deterministischer Algorithmus immer als randomisierter Algorithmus gesehen werden?
A: Ja: mit randombit input \(R = 0\)

Q: Kann man Monte Carlo in Las Vegas Algorithmen umwandeln und Las Vegas in Monte Carlo Algorithmen? Wenn ja, wie?
A: Las Vegas \(\rightarrow\) Monte Carlo
geht immer: Wir brechen ab, wenn zu lange Laufzeit und geben dann \(???\) aus. Wahrscheinlichkeit für Überschreitung von Laufzeitbound kann mit Markov analysiert werden.
\(\Rightarrow Pr[\text{X} \geq t] \leq \frac{E(X)}{t}\)
Monte Carlo \(\rightarrow\) Las Vegas
geht nicht, es bleibt immer eine gewisse Fehlerw'keit (auch wenn diese            beliebig klein sein kann, ist sie immer \(> 0\), egal wie oft wir A ausführen)
\(Pr[A(I) \text{ inkorrekt}] > 0 \implies Pr[A(I) \text{ inkorrekt}]^n > 0\)
"A Las Vegas algorithm can be converted into a Monte Carlo algorithm by running it for set time and generating a random answer when it fails to terminate. By an application of Markov's inequality, we can set the bound on the probability that the Las Vegas algorithm would go over the fixed limit."

Q: Was ist der Unterschied zwischen Las Vegas und Monte Carlo Algorithmen?
A: Monte Carlo Algorithmus:
- Korrektheit ist Zufallsvariable
- Immer gleiche Laufzeit
- Manchmal falscher Output
Beispiele: Miller-Rabin (oder andere Primzahltests), Target Shooting
Las Vegas Algorithmus:
- Laufzeit ist Zufallsvariable T
- Ausgabe ist immer korrekt
Alternative Betrachtung:
- Läuft bist korrekte Antwort gefunden oder Laufzeitlimit erreicht, dann ist Output \(???\) (Zufallsvariable, ob \(???\) ausgegeben wird oder nicht, dafür immer gleiche Laufzeit)
- Den Algorithmus von 2. können wir so lange ausführen, bis die Ausgabe nicht \(???\) ist. Dann ist die Laufzeit \(X - Geo(Pr[A(I) \neq ???])\).
Beispiele: Quickselect, Finden von Duplikaten
Umwandlung:
Las Vegas \(\rightarrow\) Monte Carlo
geht immer, siehe Betrachtung 2 (wir brechen ab, wenn zu lange Laufzeit. Wahrscheinlichkeit für Überschreitung von Laufzeitbound kann mit Markov analysiert werden)
Monte Carlo \(\rightarrow\) Las Vegas
geht nicht, es bleibt immer eine gewisse Fehlerw'keit (auch wenn diese beliebig klein sein kann, ist sie immer \(> 0\))

Q: Was ist ein deterministischer Algorithmus?
A: Ein Algorithmus, der bei gleicher Eingabe immer die gleiche Ausgabe liefert
Randomisierte Algorithmen sind im allgemeinen nicht deterministisch
- Input: \(I\). Zusätzlich hat der Algorithmus Zugriff auf Zufallsvariablen R
- Output: \(A(I,R)\)
- \(A(I)\) ... Zufallsvariable, die dem Wert von \(A(I, R)\)
bei einer zufälligen Wahl von R entspricht
• nicht-deterministisch: selbe Eingabe, nicht unbedingt selber Output

Q: Was ist ein randomisierter Algorithmus?
A: - Input: \(I\). Zusätzlich hat der Algorithmus Zugriff auf Zufallsvariablen R
- Output: \(A(I,R)\)
- \(A(I)\) ... Zufallsvariable, die dem Wert von \(A(I, R)\)
bei einer zufälligen Wahl von R entspricht
• deterministisch: selbe Eingabe, selber Output
• nicht-deterministisch: selbe Eingabe, nicht unbedingt selber Output

Q: When is a pipeline balanced?
A: A pipeline is balanced \(\iff\) the latency is the same (constant) for all its inputs (not just for a constant number of execution elements/instructions)

Q: What is a re-entrant lock?
A: A lock that a thread holding the lock can acquire multiple times - avoids livelocks/deadlocking itself (has to release multiple times afterwards)

Q: How does the Peterson Lock algorithm work?
A: - mutual exclusion
- deadlock-free
- starvation-free
- fair
proof of mutual exclusion:
proof of starvation-freedom:
proofs see https://dl.acm.org/doi/pdf/10.5555/2385452

Q: When is a lock algorithm fair (in a fcfs sense)?
A: \(D_{A} \to D_{B} \implies CS_A \to CS_B \)
equivalently:
A fair lock is acquired in the order it is requested.
threads überholen sich nicht wenn doorways hintereinander ausgeführt wurden (wenn gleichzeitig - keine Aussage)
e.g. bakerly lock

Was ist die Definition eines Netzwerks?

Q: Was ist die Definition eines Flusses \(f\) (gegeben ein Netzwerk \(N\))? Was ist der Wert dieses Flusses?
A: Zulässigkeit: \(0 \leq f(e) \leq c(e)\) für alle \(e \in A\)
Flusserhaltung: für alle \(v \in V\setminus\{s,t\}\) muss die Summe eingehender Flusswerte equivalent zur Summe ausgehender Flusswerte sein
ganzzahliger Fluss - alle \(f(e)\) ganzzahlig
Wert = Nettoabfluss aus s = Nettozufluss zu t

Beweise folgendes Lemma:

Q: Was ist die Definition eines s-t-Schnitts (S,T) eines Netzwerks N und was ist die Kapazität dieses Schnitts?
A: komplett unabhängig von Flüssen
Fluss \(f\) und \((S,T)\) Schnitt mit \(val(f) = cap(S,T)\) sind Beweis, dass \(f\) maximal und \((S,T)\) minimal ist

Beweise (muss nicht ganz genau sein):

Q: What is a semaphore and what operations does it support? How would you implement one in java using monitors?
A: has int value S (initialised to >= 0), operations are atomic
acquire(S)
wait until S > 0
dec(S)
release(S)
inc(S)
java implementation using monitors:
can be used to implement/do the following:
 - lock (lock = acquire, unlock = release, initialised with S=1).
 - barrier: synchronize N threads
 - producer/consumer scenarios
rendezvous:
other implementation options:

Q: What is the concept of barriers? How can we implement a reusable barrier using monitors?
A: langsam wegen turnstile
Can be implemented using monitors (below) or semaphores (above):
non reetrant:
reentrant:

Q: Was besagt das Maxflow-Mincut-Theorem?
A: es gibt immer max flow (unendliches Problem) und mincut (endliches Problem, \(2^{(n-2)}\) viele)
\(\Rightarrow\) trotzdem löst man mincut mittels maxflow
\(\leq\) gilt auch, ist aber Lemma aus Definition
Falls wir somit Fluss und \((S,T)\)-Schnitt finden, für die obiges gilt, ist \(f\) maximal und \((S,T)\) minimal

Q: How can we use await and signal with java locks (from Lock interface) and what are their semantics?
A: semantics same as wait/notify
await inside while loop because of:
- spurious wakeups
- signal calls from other threads that did not change the waiting condition, thread should continue to wait

Q: How does the bakery lock algorithm work?
Why does it fulfill the following:
- starvation-free
- fair (FIFO)
A: "ticket lock", similar to a queue
- mutual exclusion
- deadlock-free
- starvation-free
- fair (FIFO)

Q: Does starvation freedom imply deadlock freedom?
A: Yes! it's a stronger guarantee
definition of deadlock freedom:
with the assumption that threads get scheduled, e.g. in case of lock algos
at least one thread calling method \(\implies\) some thread will complete call in finite number of instructions
facts:
starvation-free \(\implies\) deadlock-free
\(\cong\) if some thread tries to enter CS, then one must eventually succeed

Q: How does the filter lock algorithm work?
A: - mutual exclusion
- deadlock free
- starvation free (https://dl.acm.org/doi/pdf/10.5555/2385452#page=54&zoom=auto,-416,37, proof by induction)
- but NOT fair - threads can overtake each other (first to enter dorway section does not imply first to enter CS). doorway is only before entering the "filter" here

Q: How do you implement a barrier in Java (using monitors)?
A: non reetrant:
reentrant:
auch schön aber nicht ideal für exam
semaphore implementation:

Q: What is Java's volatile keyword useful for?
A: write to volatile variables establishes happens-before relationship with subsequent reads of that same variable (across threads)
Analyse von JMM über Synchronization Actions, die mitunter bestimmter Ordnungsrelation unterliegen:
 - read/write volatile
 - lock/unlock ops
HB = Program Order (PO) + Synchronizes With (SW)
e.g. Peterson lock: wenn nur victim volatile -> beide threads können in CS, flag(X) kann als false gelesen werden (wir wissen nicht, wann genau es gelesen wird, könnte auch weit vor loop sein. Grundsätzlich wird nur sequentielle Semantik befolgt) ein fix hier wäre, die order beim lesen im loop zu ändern, somit kein so gutes Beispiel

Q: Explain the concepts of the locks using the following instructions:
- TAS
- CAS
A: using AtomicBoolean
- getAndSet(boolean new): sets new and returns previous
- compareAndSet(boolean expect, boolean update): set value to updated \(\iff\) current is expect. return true on success, false otherwise
TAS lock:
CAS (compare and swap) lock
- mutual exclusion
- deadlock-free
- however: not starvation free, not fair
advantage: constant memory instead of linear in terms of threads
-------------
- possible improvements to the TAS lock:
1. TATAS (test and test and set)
reduces congestion on l
2. exponential backoff
empirically proven to reduce congestion (by a ton!)

Q: Wie ist das Restnetzwerk \(N_f\) eines Netzwerks \(N\) definiert?
A: \(f\) ist maximal \(\iff\) es gibt keinen gerichteten Pfad in \(N_f\) von s nach \(t\)
um wieviel können wir den Fluss noch erhöhen: gleiche Kante wie in N mit diesem Wert
um wieviel können wir Fluss noch verringern: entgegengesetzte Kante mit ursprünglichem Flusswert
Beispiel:

Q: Wie können wir aus dem Restnetzwerk \(N_f\) ablesen, ob \(f\) ein maximaler Fluss ist?
Wenn \(f\) maximal ist, gibt es einen s-t-Schnitt mit \(val(f) = cap(S,T)\)? Wie finden wir diesen?
A: \(f\) ist maximal \(\iff\) es gibt keinen gerichteten s-t-Pfad in \(N_f\)
\(\Rightarrow\) sonst können wir \(f\) entlang dieses Pfades um die minimale Restkapazität (des Pfades) verbessern.
Wenn \(f\) maximal ist, ist ein minimaler Schnitt gegeben durch die Menge \(S\) aller von \(s\) in \(N_f\) erreichbaren Knoten (es kann auch mehrere geben, zB. o--o--o)

Q: Wie funktioniert der Ford-Fulkerson-Algorithmus? Was beträgt die Laufzeit, funktioniert der Algorithmus immer?
A: Laufzeit: ein Schritt (\(N_f\) updaten, Pfad suchen) geht in \(O(m)\). In einem Netzwerk kann kein Fluss Wert grösser \(nU\) haben (von \(s\) aus max. \(n-1\) Kanten, gebounded von \(U\), der maximalen Kapazität).
Da in einem ganzzahligen Netzwerk in jedem Schritt \(f\) um mindestens 1 verbessert wird, ist die Laufzeit \(O(mnU)\)
- terminiert nicht immer, wenn \(c: A \to \mathbb{R}\) (irrationalie Kapazitäten)
- terminiert immer, wenn \(c: A \to \mathbb{N}_0\), in \(O(mnU)\) wenn \(U = \max_{e\in A} c(e)\)
 - erhöht Fluss immer um ganzzahlige Werte
 - terminiert nicht bei jedem Netzwerk mit irrationalen Kapazitäten
Weitere Algorithmen:
Capacity-Scaling in \(O(mn(1 +log U))\)
Einschränkung: ganzzahlige Kapazitäten.
 - gut, wenn \(U\) klein ist
Dynamic Trees in \(O(mn \log n)\)
ohne Einschränkung
-------------------
Beispiel, für das Ford-Fulkerson nicht funktioniert: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/07DemoFordFulkersonPathological.pdf

Q: Welche weiteren Algorithmen ausser Ford-Fulkerson gibt es für das Maxflow-Problem noch und welche Laufzeit haben sie?
A: Capacity-Scaling in \(O(mn(1 +log U))\)
Einschränkung: ganzzahlige Kapazitäten.
 - gut, wenn \(U\) klein ist
Dynamic Trees in \(O(mn \log n)\)
ohne Einschränkung

Q: Wie funktioniert der Jarvis-Wrap Algorithmus? Was ist die Laufzeit?
A: - Code:
- Intuition/Idee:
Wir spannen einen Faden um Nägel auf Holzbrett
- Runtime: (input n Punkte in \(R^2\) in allgemeiner Lage)
\(O(n)\) pro FindNext-Aufruf, \(h\) Aufrufe (Anzahl Ecken von \(conv(P)\)) \(\rightarrow O(nh)\)
lower bound \(O(n)\), upper bound \(O(n^2)\)
Edge cases:
 - 3 Punkte auf Geraden: Erweiterung totaler Ordnung, wir nehmen weitest entferntesten Punkt
 - 2 Punkte mit gleicher x-Koordinate: lexikographisch kleinster Punkt (kleinste y-Koordinate)
Randkante \(\iff\) alle Punkte links von Randkante
Bestimmung von p "links von" qr:
erste Zeile von zweiter und dritter Abziehen, dann nach dritter Spalte entwickeln
naiver \(O(n^3)\) Algorithmus: gehe durch alle qr Paare und prüfe ob Randkante

Q: Wie ist die konvexe Hülle \(conv(S)\) von \(S \subseteq \mathbb{R}^d\) definiert?
Was ist das Convex-Hull Problem?
Was ist die Definition einer Randkante? Wie ergibt sich aus dieser Definition ein einfacher \(O(n^3)\) Algorithmus?
A: auch: minimale konvexe Menge, die S enthält
- einfacher \(O(n^3)\) Algorithmus:
gehe durch alle qr Paare und prüfe ob Randkante, \({n \choose 2}\) mal \(O(n)\)
- Bestimmung von p "links von" qr:
erste Zeile von zweiter und dritter Abziehen, dann nach dritter Spalte entwickeln
- Reduktion des Sortierens auf das Convex-Hull Problem gibt lower bound für Laufzeit:
\((x_1, \dots, x_n) \mapsto ((x_1,x_1^2, \dots, (x_n,x_n^2))\)
in \(O(n)\) erhält man aus Eckenfolge der Konvexen Hülle dieser Punkte die sortierte Folge der Punkte
\(\Rightarrow\) Kann man ConvexHull in \(t(n)\) lösen, so kann man in \(t(n)+O(n)\) Zeit sortieren.
(kann auf jede kontinuierliche, konvexe Funktion \(f\) angepasst werden, die auf \(\mathbb{R}\) definiert ist, zB. \(x^4, e^x\))
---------
Lösung für das Convex-Hull Problem

Q: When is a history \(H\) linearizable?
Is the above linearizable?
A: A history \(H\) is linearizable if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent \(\Rightarrow\) intra thread order).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
- inter thread order is obeyed: \(\to_{H} \subset \to_{S}\) (\(m_o \to m_1\) in \(H \implies m_o \to m_1\) in \(S\)) (subset because we could have overlapping calls in H which now have to be ordered in \(S\))
---
An Object \(o\) is linerarizable \(\iff \forall H\), \(H | o\) is linerarizable
---
nice property: composability
If we have two objects that are linearizable, any combination of histories of the two objects is also linearizable!
----
Applications:
- For given history/execution we can decide if it is linearizable or not (by showing that there is some history \(S\) which adheres to definition: choosing linearization points for overlapping method calls - reordering operations while adhering to PO and intra thread order)
- We can use it as an assumption to show correctness
linearizable \(\implies\)sequentially consistent (not other way around)
sequential history \(S\) is legal \(\iff\) for every object \(x\), \(S | x\) adheres to sequential specification (e.g. fulfills pre/post cond.)
\(H'\) is extended from \(H\) by:
 - appending responses to pending invocations that took effect
 - discarding pending invocations that did not take effect
history is well formed \(\iff\) all per thread projections are sequential
all data accesses are made using atomic variables (or in Java: volatile, other Synchronization Actions) \(\implies\) sequentially consistent and linearizable

Q: What is the consensus problem? What requirements do we have on a consensus protocol?
How are the following defined:
- class C solves n-thread consensus
- consensus number of some class C
A: requirements:
- wait free: must return in finite time for each thread
- consistent: all threads decide on same value
- valid: the common decision value is some thread's input
-----
concurrent consensus object is linearizable to a sequential consensus object in which the thread whose value was chosen completes its decide() first
definitions:
- A class C solves n-thread consensus if there exists a consensus protocol (that works for n threads) using any number of objects of class C and any number of atomic registers
- Consensus number of C: largest n such that C solves n-thread consensus.
consensus numbers of some objects:
- atomic registers: 1
- wait free FIFO queue (no peek), LIFO queue, TAS, getAndSet, getAndIncrement: 2
- CAS, FIFO queue (with peek): \(\infty\)
- wait-free FIFO queues, wait-free RMW operations and CAS cannot be implemented with atomic registers!
constructive proof that CAS has consensus number \(\infty\):
theorems from slides:
- Atomic registers have consensus number 1
- there is no wait-free implementation of n-thread consensus, n>1, from read-write registers
- CAS has consensus number \(\infty\)
- There exists no wait-free implementation of a FIFO-queue using atomic registers
- Test-And-Set, getAndSet, getAndIncrement have consensus number 2

Q: When is a history sequentially consistent?
A: A history \(H\) is sequentially consistent if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent \(\Rightarrow\) intra thread order, PO).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
---
An Object \(o\) is sequentially consistent \(\iff \forall H\), \(H | o\) is sequentially consistent
---
Ordnung zwischen Threads nicht gegeben, wir können nur interne Ordnung beachten
Applications:
- For given history/execution we can decide if it is sequentially consistent or not (by showing that there is some history \(S\) which adheres to definition: order operations while adhering to PO)
- We can use it as an assumption (not as useful as linearizability though as not composable)
linearizable \(\implies\)sequentially consistent (not other way around)
history is well formed \(\iff\) all per thread projections are sequential
example: not linearizable but sequentially consistent
not composable, not a local property!
all data accesses are made using atomic variables \(\Rightarrow\) sequentially consistent and linearizable

Q: What is the definition of a deadlock?
A: wikipedia:
In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock.
important: circular waiting between threads such that no progress can be made anymore
avoiding deadlocks:
 - make sure no cycle can occur through resource ordering: total order on lock objects
deadlock-freedom: if one or more threads are calling the method, one will finish its execution in finite time
alternative definition:
acyclic graph containing locks and threads as vertices
- edge from lock to thread if thread has lock
- edge from thread to lock if thread wants lock
deadlock occurs iff graph has cycle

Q: LocalRepair-Algorithmus für das Convex-Hull Problem:
- Fülle die Lücken im Pseudocode aus!
A: - Code:
-------------------------------
- Analyse:
1. Sortieren in \(O(n \log n)\)
2. \(2(n-1)-h\) mal Verbessern (Startfolge hat \(2n-2\) Knoten, am Ende \(h\)) \(\Rightarrow O(n)\)
3. \(2n\) mal nicht verbessern (while condition false, 2 mal pro Punkt, ein mal unten, ein mal oben) \(\Rightarrow O(n)\)
\(\Rightarrow\) wenn schon sortiert, nur \(O(n)\)
- Reduktion des Sortierens auf das Convex-Hull Problem gibt lower bound für Laufzeit:
\((x_1, \dots, x_n) \mapsto ((x_1,x_1^2, \dots, (x_n,x_n^2))\)
in \(O(n)\) erhält man aus Eckenfolge der Konvexen Hülle dieser Punkte die sortierte Folge der Punkte
\(\Rightarrow\) Kann man ConvexHull in \(t(n)\) lösen, so kann man in \(t(n)+O(n)\) Zeit sortieren.
- Extra Fakten:
Liefert auch Triangulierung
--------
Lösung für das Convex-Hull Problem

Q: State a history \(H\) that is sequentially consistent but NOT linearizable.
A: A: r.write(1)
A: void
B: r.write(2)
B: void
A: r.read
A: 1
e.g. this. We simply need a situation where adhering to the intra thread order is not possible without violating sequential specification
while any history from a program that uses atomic registers like this would be linearizable, we can also argue about histories that are not possible to happen in practice or that are due to compiler optimizations
A history \(H\) is sequentially consistent if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
A history \(H\) is linearizable if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
- inter thread order is obeyed: \(\to_{H} \subset \to_{S}\) (\(m_o \to m_1\) in \(H \implies m_o \to m_1\) in \(S\))
history is well formed \(\iff\) all per thread projections are sequential

Q: State a history \(H\) that shows that sequentially consistent objects are not composable.
- i.e.: per object projections are sequentially consistent but whole history is not!
1. Here is an example, fill in the gaps! (T2 before T1):
2. state a history using queues
Hint: two objects A, B, two threads: symmetric, xxy, yyx
A: - 1.
A: q.enq(x)
B: p.enq(y)
A: p.enq(x)
B: q.enq(y)
A: q.deq // y
B: p.deq // x
per thread:
A:
A: q.enq(x)
A: p.enq(x)
A: q.deq // y
B:
B: p.enq(y)
B: q.enq(y)
B: p.deq // x
- 2.
T1: B = 42
T1: A = 1
T2: read A = 1
T2: read B = 0
--------------
an equivalent legal sequential history (per def of sequential consistency) would be as follows:
A: q.enq(y)
A: q.enq(x)
A: q.deq // y
B: p.enq(x)
B: p.enq(y)
B: p.deq // x
However, respecting the order of method calls between threads, this is not possible (B: p.enq(y) after B: p.enq(x) and A: q.enq(y) after A: q.enq(x) not both possible)
another example:
actually I don't think this works now because it doesn't work as just one history
A history \(H\) is sequentially consistent if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
A history \(H\) is linearizable if there exists a legal sequential history \(S\) that is equivalent to \(H\) (meaning all per thread projections are equivalent).
For this equivalent history \(S\) the following must hold:
- it is legal: the sequential specification is obeyed, appears as if executed on single thread
- it is sequential: the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response. (a plausible history that could result from sequential execution)
- inter thread order is obeyed: \(\to_{H} \subset \to_{S}\) (\(m_o \to m_1\) in \(H \implies m_o \to m_1\) in \(S\))
history is well formed \(\iff\) all per thread projections are sequential

Q: Of which terms is race condition the umbrella term?
A: We define race condition as the umbrella term for: bad interleaving, data race
bad interleavings:
data race

Q: When is a method wait-free?
A: definition:
A method is wait-free if it guarantees that every call finishes its execution in a finite number of steps.
"all threads eventually make progress"
\(\cong\) starvation-freedom without assumption that threads get scheduled
facts:
wait-free \(\implies\) lock-free (but not vice versa)
wait-free \(\implies\) starvation-free

Q: When is a method lock-free?
A: definition:
A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.
"at least one thread always makes progress"
\(\cong\) deadlock-freedom without assumption that threads get scheduled/progress conditions
some facts:
wait-free \(\implies\) lock-free (but not vice versa)
lock-free \(\implies\) deadlock-free
some threads could starve
main method: CAS

Q: When is an algorithm non-blocking? When is it blocking?
A: non-blocking: failure or suspension of one thread cannot cause failure or suspension of another thread
blocking: a thread can indefinitely delay another thread
with locks

Q: When is a method deadlock-free?
A: definition of deadlock freedom:
with the assumption that threads get scheduled and progress inside CS, e.g. in case of lock algos
at least one thread calling method \(\implies\) some thread will complete call in finite number of instructions
facts:
starvation-free \(\implies\) deadlock-free
\(\cong\) if some thread tries to enter CS, then one must eventually succeed

Q: When is a method starvation-free?
A: definition:
with the assumption that threads get scheduled, e.g. for lock algos
any thread calling method will complete call in finite number of steps
(any thread calls method \(\implies\)that thread will complete call in finite number of steps)
facts:
starvation-free \(\implies\) deadlock-free
\(\cong\) if any thread tries to enter CS, then that thread succeeds
any method using a lock that we can't be sure is starvation free could be non-starvation free!

Q: Explain when a history \(H\) is:
- sequential
- well-formed
- complete
A: A history H is sequential if the first event of H is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response.
well-formed: all per thread projections are sequential
complete: no pending responses (complete(H): remove pending invocations)

Q: Wie ist ein Hamiltonkreis definiert?
Welcher der folgenden Graphen hat einen Hamiltonkreis:
- \(H_d\)
- n * m Gitter
A: - Kreis, der jeden Knoten des Graphen genau ein mal enthält
(nicht effizient berechnbar im allgemeinen)
\(\Leftarrow\): Wir können konstruktiv Hamiltonkreis finden, siehe Sketch:
\(\Rightarrow\): Wenn \(m\cdot n\) nicht gerade, gibt es keinen Hamiltonkreis (indirekt):
Schachmuster, Hamiltonkreis muss gerade Anzahl Knoten verwenden (gleich oft weiss wie schwarz)
gleiche Anzahl schwarze wie weisse Knoten \(\implies\)gerade Zahl von Knoten
- \(H_d\): für d = 2 Hamiltonkreis bestimmen, Sequence spiegeln und bei oberem Teil 0, unterem 1 anfügen => Hamiltonkreis für d= 3

Q: Wie funktioniert der Läufer-Schildkröte-Algorithmus zum Finden der Kanten einer Eulertour?
A: Voraussetzungen: Grad jedes Knotens gerade, Graph zusammenhängend
Idee:
- schneller Läufer, der Knoten besucht, bis er nicht mehr weiter kann
- langsamer Läufer sucht dann nach Knoten, die unbesuchte Nachbarn haben
Korrektheit:
Da in G jeder Knoten geraden Grad hat, liefert jeder Lauf des schnellen Läufers einen neuen Zyklus und im verbleibenden Graphen hat noch immer jeder Knoten geraden Grad. Zwei Zyklen können zu einem neuen zusammengefügt werden.
Laufzeit:
Jeder der beiden Läufer besucht jede Kante jeweils maximal ein Mal \(\implies O(m)\)

Q: Beschreibe zwei Algorithmen zum Finden von Hamiltonkreisen mit jeweils einer Überschrift! Was sind ihre jeweiligen Zeit- und Speicherkomplexitäten?
A: - 1. Existenz von 1-x-Pfaden
Zeit: \(O(n^2 \;2^n)\)
Speicher: \(O(n\;2^n)\)
- 2. Wege mit Start- und Endknoten s der Länge n zählen
Zeit: \(O(n^{2.81}\;log(n) \;2^n)\)
Speicher: \(O(n^2)\)
_______________________________
1. Existenz von 1-x-Pfaden
Zeit: \(O(n^2 \;2^n)\)
Speicher: \(O(n\;2^n)\)
2. Wege mit Start- und Endknoten s der Länge n zählen
Zeit: \(O(n^{2.81}\;log(n) \;2^n)\)
Speicher: \(O(n^2)\)
Idee des Algorithmus:
\(W_{\emptyset}\) ist die Menge aller Wege der Länge n von s zu s, enthält insbesondere auch alle Hamiltonkreise (sogar zwei mal!).
Wir wollen nun die ungewünschten Wege, die nicht alle Knoten besuchen, herausfiltern: \(\bigcup_{v \in V} W_{\{v\}}\) (Anzahl aller Wege, die jeweils einen Knoten nicht enthalten)
Resultat: \(\frac{1}{2}(|W_{\emptyset}| - | \bigcup_{i=1}^{n} W_{\{i\}} | )\)
\(=\frac{1}{2}\left( |W_\emptyset| + \sum_{S \subseteq V,\, S \neq \emptyset} (-1)^{|S|}W_S \right)\)

Q: Was ist das Travelling Salesman Problem (TSP)? Gib einen Algorithmus zum finden einer 2-Approximation für das metrische TSP an!
A: Input:
- vollständiger Graph auf n Knoten: \(K_n\)
- Distanzen zwischen je zwei Knoten: \(l: E={[n] \choose 2} \to \mathbb{R}\)
- (metrisch wenn Dreiecksungleichung gilt : \(l(u,w) \leq l(u,v) + l(u,w)\) für alle \(u, v, w \in V\) und \(l \in {\mathbb{R}_{0}^{+}}^{E}\))
Gesucht:
- minimaler Hamiltonkreis (nicht nur Wert): \(\min_{H:\; \text{Hamiltonkreis}} \sum_{e \in E(H)}{l}(e)\)
Laufzeit:  \(O(n^2)\)
Algorithmus:
1. Berechne MST \(\to\) T
2. Verdopple alle Kanten in T\(\to\) T'
3. Berechne Eulertour in T' \(\to\) E
4. Kürze E ab (überspringe Knoten, die wiederholt vorkommen) \(\to\) H
Analysis:
1. \(cost(T) \leq cost(OPT-e) \leq cost(OPT)\)
2. \(cost(T') = 2cost(T) \leq 2cost(OPT)\)
3. \(cost(E) = cost(T') \leq 2cost(OPT)\)
4. \(cost(H) \leq cost(E) \leq 2cost(OPT)\) (mit Dreiecksungleichung)
NP-complete:

Wann ist ein Graph \(G\) k-regulär?

Q: Seien \(X\) und \(Y\) zwei unabhängige Zufallsvariablen mit \(E(X) = E(Y) = 1\) und \(Var(X) = Var(Y) = 10\)
Berechne:
\(Var((X + 3Y)*E[X - 3Y] + E[X + 2Y]*(X+Y))\)
A: Var((x + 3Y)*E[X -3Y] + E[X + 2Y]*(X+Y)) =
Var(-2(x + 3Y) + 3(X + Y)) = Var(X -3Y) =
Var(X) + (-3)^2Var(Y) =
Var(X) + 9Var(Y) =
10 + 90 =
100

Q: Gilt folgende Behauptung? Wenn nicht, gib ein Gegenbeispiel an!
\(G\) hat eine Eulertour und \(|V|\) ist gerade \(\implies\) es gibt ein perfektes Matching in \(G\)
A: Gilt nicht, nur bei Hamiltonkreis
Gegenbeispiel: Mitsubishi-Logo

Q: Was ist die Definition eines M-augmentierenden Pfades (im Kontext von Matchings)?
Wann gibt es immer einen M-augmentierenden Pfad und wie ergibt sich daraus ein Algorithmus zum finden eines maximum-Matchings (in bipartiten Graphen)?
A: Ein M-augmentierender Pfad hat abwechselnd Kanten aus M und nicht aus M (endet und beginnt mit unüberdecktem Knoten)
(\(\iff\)statement)
damit erhalten wir einen Algorithmus: Wir können mit dem augmentierendem Pfad P das Matching M vergrössern.
\(M \oplus P = (M \cup P){/}(M \cap P)\)
BFS von \(L_0\) aus in Stufen, "folgt" augmentierenden Pfaden, bis unüberdeckter Endknoten gefunden wurde
Laufzeit gesamt (für bipartite Graphen!): \(O(|V|*|E|)\)
(maximal \(|V|/2\) Iterationen (perfektes Matching hat \(|V|/2\) Kanten), \(O(|E|)\) pro Iteration in bipartiten Graphen, sonst \(O(|V|*|E|)\) pro Iteration)
Verbesserung (auch nur für bipartite Graphen!): Hopcroft und Karp, \(O(\sqrt{|V|} * |E|)\)
Algorithmen
Greedy-Matching: wähle zufällig eine Kante, füge sie zu M hinzu und lösche sie und alle inzidenten Kanten bis \(|E| = \emptyset\)
\(\implies\) findet inklusionsmaximales Matching in \(O(|E|)\)
Augmentierende Pfade (in bipartitem Graphen): finde augm. Pfad \(P\) (mit BFS in Stufen), verbessere \(M\) mit \(M = M \oplus P\) bis \(M\) maximum (kein augm. Pfad mehr in \(G\))
\(\implies\) kardinalitätsmaximales Matching in \(O( {|V|}*|E|)\)
Hopcroft-Karp (in bipartitem Graphen): Verbesserung von augm. Pfaden: kardinalitätsmaximales Matching in bipartitem Graphen in \(O(\sqrt {|V|}*|E|)\)
(gleiche Laufzeit auch allgemein möglich)
Gabow: Finden eines perfekten Matchings in \(2^k\)-regulärem bipartiten Graphen in
\(O(|E|)\): Berechne Eulertour, lösche jede zweite Kante, iteriere
(lässt sich verallgemeinern für \(k\)-reguläre bipartite Graphen)
Gabow: \(O(|V|^3)\) für kardinalitätsmaximales Matching von kleinstmöglichem Gewicht

Q: Gilt folgende Aussage? Wenn ja, gib einen Beweis an. Wenn nein, warum nicht?
Jeder k-reguläre Graph enthält ein perfektes Matching
A: Gilt so nicht, Graph muss bipartit sein!
(siehe Beispiel 1.55 im Skript)
---------------------------------
Satz von Frobenius:
\(s = k * |X|\) (jeder Knoten hat Grad k)
\(s \leq k * |N(X)|\) (mehrere Knoten in X können Kante zu selbem Knoten aus N(X) haben)
\(\implies k *|X| \leq k * |N(X)|\)
\(\implies |X| \leq |N(X)|\)
\(\implies G\) enthält Matching mit \(|M| = |A|\) (Satz von Hall)
\(\implies G\) enthält ein perfektes Matching (da \(G\) k-regulär und bipartit ist \(|A| = |B|\))

Q: Wie funktioniert Christofides-Algorithmus zur Berechnung einer 3/2-Approximation des TSP?
(Hint zur Analyse: Betrachte \(M\) und \(OPT \Rightarrow\) Unterteilung in Pfade)
A: Input:
- vollständiger Graph auf n Knoten: \(K_n\)
- Distanzen zwischen je zwei Knoten: \(l: E={[n] \choose 2} \to \mathbb{R}\)
- (metrisch wenn Dreiecksungleichung gilt : \(l(u,w) \leq l(u,v) + l(u,w)\) für alle \(u, v, w \in V\) und \(l \in {\mathbb{R}_{0}^{+}}^{E}\))
Gesucht:
- minimaler Hamiltonkreis (nicht nur Wert): \(\min_{H:\; \text{Hamiltonkreis}} \sum_{e \in E(H)}{l}(e)\)
Laufzeit:  \(O(n^3)\)
Algorithmus:
1. Berechne MST \(\to\) T
2. Berechne minimales perfektes Matching M von \(U := \{v \in T \;| \;deg(v) \;\text{ungerade}\}\) \(\to\) M (in \(O(n^3)\), Gabow)
3. Berechne Eulertour in T \(\cup\) M \(\to\) E
4. Kürze E ab (überspringe Knoten, die wiederholt vorkommen) \(\to\) H
Analysis:
1. \(cost(T) \leq cost(OPT-e) \leq cost(OPT)\)
2. Wir betrachten den Hamiltonkreis mit min. Gewicht (Ergebnis von TSP), OPT. \(U := \{v \in T \;| \;deg(v) \;\text{ungerade}\}\) unterteilt diesen in \(|U|\) viele Pfade. Wir behalten nur die Knoten in \(U\) und kürzen die restlichen Knoten ab. Es gilt \(cost(C_U) \leq cost(OPT)\)(mit Dreiecksungleichung). Nun enthält \(C_U\) zwei perfekte Matchings von \(U\) (\(|U|\) gerade mit Handschlagslemma), eines davon mit \(cost(M) \leq \frac{1}{2} cost(OPT)\), das von uns in Schritt 2 gefunden wurde.
3. \(cost(E) = cost(T \cup M) \leq \frac{3}{2}cost(OPT)\)
4. \(cost(H) \leq cost(E) \leq \frac{3}{2}cost(OPT)\) (mit Dreiecksungleichung)
NP-complete:

Q: Ein Graph \(G\) ist \(k\)-partit \(\iff \chi(G) \dots\)
A: Ein Graph \(G\) ist \(k\)-partit \(\iff \chi(G) \leq k\)
Konzepte von \(k\)-partit / Färbungen hängen zusammen!

Q: Was ist eine (Knoten-)Färbung? Wie ist die chromatische Zahl \(\chi(G)\) definiert?
A: schwieriges Problem, schon "Gilt \(\chi(G) \leq 3?\)" ist NP-vollständig
Algorithmen:
Bipartiter Graph:
"Gilt \(\chi(G) = 2?\)" \(\iff G\) ist bipartit
\(\implies\) in \(O(|E|)\) mit DFS/BFS
Greedy-Färbung (\(O(|E|)\)):
Verwendet maximal \(\Delta + 1\) viele Farben, kommt ganz auf Anfangs gewählte Reihenfolge an (\(\Delta := max_{v \in V} \;deg(v)\))
- Für alle Graphen G gibt es eine Reihenfolge, mit der Greedy-Färbung mit \(\chi(G)\) Farben auskommt
- Andererseits: Es gibt eine Reihenfolge, mit der ein bipartiter Graph mit \(|V|/2\) vielen Farben gefärbt wird
Heuristik:
\(|N(v_i)\; \cap\; \{v_1,\; \dots, \;v_{i-1}\} | \leq k\) für alle \(i\) mit \(2 \leq i \leq n \implies\) Greedy-Färbung braucht \(\leq k+1\) Farben (siehe Pseudocode, \(c[v_i]\) ist maximal \(k+1\))
(\(v_i\) hat höchstens \(k\) bereits gefärbte Nachbarn)
Somit machen wir folgendes:
\(v_n :=\) Knoten mit kleinstem Grad. Lösche \(v_n\). \(v_{n-1} :=\) Knoten mit kleinstem Grad im Restgraph. Lösche \(v_{n-1}\).
Repeat In jedem Subgraph gibt es \(v\) mit \(deg(v) \leq k \implies\) Heuristik liefert Reihenfolge für \(k+1\) Farben 3-färbbarer-Graph: \(O(|V|+|E|)\) mit \(O(\sqrt{|V|})\) Farben
- Bäume können in 2 Farben gefärbt werden
- max 6 Farben für planare (keine überschneidenden Kanten) Graphen (da es \(v\) mit \(deg(v) \leq 5\) gibt)

Q: Jeder Block eines Blockgraphen lässt sich mit k Farben färben. Mit wie viel Farben kann der ganze Graph gefärbt werden?
A: Mit \(k\) Farben durch Vertauschen der Farbklassen (damit Farbe bei Artikulationsknoten übereinstimmt)

Q: Sei \(G=(V,E)\) ein 3-färbbarer Graph. Wie können wir \(G\) bestmöglich färben?
A: 3-färbbarer-Graph: \(O(|V|+|E|)\) mit \(O(\sqrt{|V|})\) Farben
every time we color a vertex with deg > sqrt(n) and its neighborhood, we color > sqrt(n) vertices. and we can only do this sqrt(n) times as a graph has sqrt(n)^2=n vertices

Q: Gilt folgende Aussage für einen zusammenhängenden Graph \(G\)? Warum?
Knotenzusammenhang \(\leq\) Kantenzusammenhang \(\leq\) Minimalgrad
A: Da \(G\) zusammenhängend ist, wird mit Entfernen eines Knotes mindestens eine Kante entfernt, eventuell aber auch mehr.
Minimalgrad \(\delta(G)\) ist ein einfacher upper-bound für Kantenzusammenhang, nach Entfernen aller Kanten von Knoten mit min. Grad ist der Graph sicher nicht mehr zusammenhängend. Wir können jedoch auch zB. zwei mit nur einer Kante verbundene Graphen \(K_n\) haben \(\implies\) nur 1-zusammenhängend

Q: Wann sind zwei Ereignisse \(A, B\) unabhängig?
A: Ereignisse \(A, B\) sind unabhängig\(\iff Pr[A \cap B] = Pr[A]*Pr[B]\)

Q: Gib einen Algorithmus für das folgende Problem an!
Gesucht: möglichst grosse stabile Menge (\(S \subseteq V\), sodass \(G[S]\) keine Kante enthält) in \(G = (V,E)\)
Was ist \(E[|S|]\)? Wie sollten wir \(p\) wählen? (Hint: Ableiten!)
A: Hinzugefügen von Knoten v mit W'keit \(p\) (dass \(S_v=1\)). Wenn auch Nachbar hinzugefügt, wird einer der Knoten wieder entfernt. Somit erhalten wir mit \(S =\{v\in V | S_v=1\}\) eine stabile Menge.
\(X_v\) := Wert, der in Zeile 1 für \(S_v\) gewählt wird
\(Y_e = 1\), falls \(S_u = S_v = 1\)
\(X = \sum_{v \in V} X_v\)
\(Y = \sum_{e \in E} Y_e\)
Wir haben \(|S| \geq X - Y \implies E[|S|] \geq E[X] - E[Y]\)
\(E[X] = np, \;E[Y] = mp^2\)
\(\implies E[|S|] \geq np - mp^2\)
Bestimmen von maximalem p durch Ableiten nach p:
\((np - mp^2)' = n - 2mp = 0 \iff n = 2mp \iff p = \frac{n}{2m}\)
Einsetzen in lower bound für \(E[|S|]\):
\(E[|S|] \geq E[X] - E[Y] = np - mp^2 = \frac{n^2}{2m} - \frac{n^2}{4m} = \frac{n^2}{4m}\)

Q: Wie ist die bedingte Zufallsvariable \(X|A\) definiert? Was ist \(Pr[(X|A) = x]\)?
Wie können wir diese Definition zur Berechnung des Erwartungswerts \(E[X]\) verwenden?
A: \(X\) wird zu \(X|A: A \to \mathbb{R}\) mit \(f_{X|A}(x) = Pr[X=x|A]\)
Wobei:
\(Pr[(X|A) = x] = Pr[X=x|A] = \frac{Pr[\{\omega \in A: X(\omega) = x\}]}{Pr[A]}\)
\(E[X|A] = \sum_{x \in W_A} x * Pr[X=x|A] = \sum_{\omega \in A}X(\omega)*Pr[\omega|A]\)
Idee: bedingte Wahrscheinlichkeiten mit Konzept von Zufallsvariablen verbinden
Nützliches Resultat (Satz der totalen Wahrscheinlichkeit für Erwartungswert):
Seien \(A_1, \dots, A_n\) disjunkt, \(\bigcup_{i=1}^{n} A_i = \Omega\), \(Pr[A_i] > 0\) für alle \(i\):
\(\Rightarrow E[X] = \sum_{i=1}^{n} E[X|A_i] * Pr[A_i]\)

Q: Wie ist die gemeinsame Dichte \(f_{X,Y}(x,y)\) definiert? Wie kann man damit die Randdichten \(f_X(x)\) und \(f_Y(y)\) berechnen?
A: Gemeinsame Dichte \(f_{X,Y}(x,y)\):
\(f_{X,Y}(x,y) = Pr[X=x, Y=y] = Pr[\{\omega \in \Omega\,|\,X(\omega) = x, Y(\omega) = y\}]\)
Mit dieser können wir auch die Randdichten \(f_X(x)\) und \(f_Y(y)\) berechnen:
\(f_X(x) = \sum_{y \in W_Y}f_{X,Y}(x,y)\) bzw. \(f_Y(y) = \sum_{x \in W_X}f_{X,Y}(x,y) = Pr[Y=y]\)
(weniger wichtig, lässt sich gut aus obigem ableiten)
Analog für Verteilungsfunktion \(F\)
Gemeinsame Verteilung \(F_{X,Y}(x,y)\):
\(F_{X,Y}(x,y) = Pr[X \leq x, Y \leq y] = Pr[\{\omega \in \Omega\,|\,X(\omega) \leq x, Y(\omega) \leq y\}]\)\(= \sum_{y' \in W_Y:\, y' \leq y} \left( \sum_{x' \in W_X:\, x' \leq x}f_{X,Y}(x',y')\right)\)
Mit dieser können wir die Randverteilungen \(F_X(x)\) und \(F_Y(y)\) berechnen:
\(F_X(x) = \sum_{x\in W_X:\,x\ \leq x} f_X(x') = \sum_{x' \leq x} \sum_{y \in W_Y} f_{X,Y}(x',y)\)

Q: How is a lock defined? What does a (correct) lock implementation require?
A: - Generally: a token/resource that can be acquired by at most one thread at a time.
- Functionality: typically provided by a programming language to enforce mutual exclusion, by guarding/protecting a critical section. A lock can be acquired/locked by a thread, and is then held until it is released/unlocked.
A (correct) lock implementation needs to enable the following:
- mutual exclusion
- deadlock freedom
- (possibly: starvation freedom)
In Java, each object can be used as a lock (intrinsic/monitor lock), but the JDK also provides more complex locks.
lockout: Needlessly preventing a thread from entering a critical section.

Q: What is a map operator?
A: Definition:
- operates on each element of a collection independently to create a new collection of the same size
no combining of results
generalization: stencil which does not have to operate on each element independently, e.g. floating average with neighbours
Examples:
- vector addition that computes the sum of a collection of tuples (containing the n^th element of both vectors, see below for FJ code)
- doubling every value in array
- converting every array element to some other format
subset of data parallelism

Q: What is a reduce operator?
A: Definition:
- produce a single answer from a collection via an associative operator.
inherently sequential: data[i] may depend on having computed data[i-1]
Examples:
- max
- count (size of array, Strings that start with A, ...)
- rightmost (that has some property)
- sum

Q: What are the definitions of data parallelism and task parallelism? How do these two concepts differ?
A: Data parallelism:
- run same task on different parts of data
map, reduce operators are a form of data parallelism (vector operations, sum, ...)
frameworks: MPI, CUDA
Task parallelism:
- running many different tasks on the same (or different) data at the same time
- communication usually by passing on data from one thread to the next
- one can draw a task graph
e.g. pipelining
frameworks: ForkJoin
often a program has both concepts present in some way

Q: What is the ABA-problem? List 5 solutions to it and briefly explain them!
A: Thread 1 reads M as A.
In the meantime, thread 2 writes M to B and then back to A (or more threads/modifications such that M is A again in the end).
Thread 2 reads M again and still sees A, thinking M was not modified.
Example: Queue with node pool
Initially, the queue looks like this: A (head) -> B
1. Thread A: deq(), reads first = a, next = b
2. Thread B: deq a, enq a, deq b. Queue is now: A (head) ->
3. Thread A: head = b
Solutions:
- DCAS (double compare and swap): not available on most platforms
two CAS in one atomic operation - this way in the above example we could make sure we only write head=b if first = a, next = b and otherwise we retry the full operation. Can be achieve in Java with AtomicMarkableReference: atomic reference with mark bit
- Garbage collection: too slow for runtime kernel. GC has to be implemented in some way itself
makes sure that no pointer conflicts happen (with very high probability)
- Pointer tagging: solves ABA problem with very high probability
pointers point to a certain byte in memory. pointer 32 byte aligned \(\Rightarrow\) all pointers only take values of multiples of 32 \(\Rightarrow\) least significant 5 bits are always 0 and can be used for tagging
(pointer is different if there is one access inbetween read of current value and CAS, CAS notices this and retries)
- Hazard pointers: might be expensive in terms of resources
(Threads X, Y)
Pointer marked as hazardous are not allowed to be modified by any other threads.
- Load Linked/Store Conditional instruction (store conditional following load link only stores new value if no changes were made;e.g. ARM); Transactional memory (only commit if values didn't change)
occurrs when trying to implement a lock-free datastructure (e.g. stack, queue)
extra:

Sei \(Z:= X + Y\), \(X\) und \(Y\) sind unabhängig.
Dann ist: \(f_z(z) =\)
Hint: Satz der totalen Wahrscheinlichkeit

Q: Seien \(f_1, \dots, f_n\) reelle Funktionen \(\mathbb{R} \to \mathbb{R}\).
\(X_1, \dots, X_n\) unabhängig \(\implies ?\)
A: Seien \(f_1, \dots, f_n\) reelle Funktionen \(\mathbb{R} \to \mathbb{R}\).
\(X_1, \dots, X_n\) unabhängig \(\implies f_1(X_1), \dots, f_n(X_n)\) unabhängig
Kein \(\iff\) statement, Bedingung ist hinreichend, aber nicht notwendig!

Q: Wann gilt folgendes: \(Var(X+Y) = Var(X)+Var(Y)\)? Gib ein Beispiel, wann es nicht gilt!
A: "Gegenbeispiel" mit abhängigen Zufallsvariablen:
Sei \(Var(X) \neq 0, Y = -X\):
\(Var(X+Y) = Var(0) = 0 \neq 2Var(X) = Var(X) + Var(Y)\)

Q: Wann ist eine Zufallsvariable \(X\) poisson-verteilt mit Parameter \(\lambda\)?
Was sind \(E(X), Var(X)\)? Wie ist \(f_x(i)\) definiert (Hint: ein Term, Lambda)?
A: Für Ereignisse, wo jedes einzelne zwar unwahrscheinlich ist, jedoch insgesamt ein paar zu erwarten sind. \(\lambda\) ist der bis derzeit gemessene Durchschnitt.
summiert auf 1 mit Taylor-Expansion von \(\exp\) und herausnehmen des Faktor \(e^{-\lambda}\)
\(W_X = \mathbb{N_0}\)
\(E(X) = Var(X) = \lambda\)
\(Bin(n, \lambda/n)\) für \(n \to \infty\) konvergiert gegen die
Poisson-Verteilung mit Parameter \(\lambda\)
Beispiel: Anzahl der Herzinfarkte in der Schweiz, die in einer Stunde auftreten, wenn der gemessene Durchschnitt soweit \(\lambda\) Herzinfarkte pro Stunde ist
\(    f_x(i)=
\begin{cases}
    \frac{e^{-\lambda}\lambda^i}{i!},& i\in \mathbb{N_0}\\
    0,              & \text{sonst}
\end{cases}\)

Q: Was sagt (die erste) Chernoff Ungleichung?
A: Seien \(X_1, \dots, X_n\) unabhängige bernoulli-verteilte Zufallsvariablen mit \(Pr[X_i = 1] = p_i, Pr[X_i = 0] = 1-p_i\)
Dann gilt für \(X = \sum_{i=1}^{n} X_i\):
\(Pr[X\geq (1+\delta)E(X)] \leq e^{-\frac{1}{3}\delta^2E(X)}\)
alle Ungleichungen geben Upper-Bounds; meistens für \(X \geq \dots\)
manchmal nützlich, weitere Umformungen zu machen zB e mit 2 zu ersetzen
(iii) nur bei relativ großen t

Q: Sei \(T-Geo(p)\) Gib eine möglichst gute obere Schranke für \(Pr[T > s]\) an!
A: \(Pr[T > s] = Pr[\text{$s$ mal kein Erfolg}] = (1-p)^s\)
gar keine Schranke notwendig, wir können die Wahrscheinlichkeit so einfach berechnen!

Q: Wahr oder falsch? Begründe!
Ist \(Y\) unabhängig von \(X\), so ist auch \(X · Y\) unabhängig von \(X\).
A: Gleiches Beispiel funktioniert auch, um zu zeigen, dass wenn \(Y\) unabhängig von \(X\), so ist auch \(X + Y\) unabhängig von \(X\) auch falsch ist.
\(Pr[X+Y=2, X=1] = 1/2\)
\(Pr[X+Y=2] \cdot Pr[X=1] = 1/4\)

Q: Sei \(f\) ein maximaler Fluss für ein Netzwerk \(N\). Wir wollen den minimalen Schnitt finden, um zu zeigen, dass f maximal ist. Wie können wir diesen im Restnetzwerk einfach bestimmen?
A: alle von s in \(N_f\) aus erreichbaren Knoten bilden dann den minimalen Schnitt
zB. hier \(\{s,d,e\}\)
(FS17 Probeklausur)

Q: What is the concept of Transactional Memory (TM)?
A: - Programmer defines atomic code sections (in execution one "transaction")
Declarative approach: the underlying implementation is left to the system (e.g locking. user is not concerned with the how, only the what)
Transactions
cannot produce deadlocks! (starvation could be possible, depends on implementation. in scala stm we only retry a constant number of times, so its starvation free)
- run in isolation: snapshot of global state is taken before it starts
- appear serialized: as if executed sequentially
- can be aborted (if relevant state changed before commit), then retried automatically
- guarantee consistency: running transaction always sees consistent data. either by aborting early or snapshot at the start
Of the ACID properties in database transactions, it fulfills the following:
A (atomicity), C (consistency), I (isolation)
Implementations (WIP!):
- Hardware TM: can be fast, limited scope, small transcations
- Software TM: more flexible, slow
Pros:
simple code, less error prone
higher level semantics (declarative)
composable
Cons:
either slow or very limited functionality
I/O instructions cannot be performed
Design choices:
- strong isolation: shared state accessed by a transaction is also accessed outside of a transaction \(\implies\) transactional guarantees upheld
- flattened nesting: inner aborts \(\implies\) outer aborts, outer commits \(\implies\)inner commits visible
- closed nesting: same as flattened but: inner aborts do not imply outer aborts
scala stm syntax example:

Q: What is the concept of the MPI (message passing interface) framework/distributed memory?
How can deadlocks occurr (while matching send to recv)?
A: Idea:
- State is mutable, but not shared: Each thread/task has its private state
- Tasks cooperate via message passing
Process identification:
Basic functions:
Single Program Multiple Data: We can make processes with different ranks complete different tasks
Sources of deadlocks:
Solutions to "unsafe" code:
example program

Q: How can we implement a reusable barrier using semaphores?
A: reusable:
non-reusable:
slow because of turnstile
semaphore semantics:
has int value S (initialised to >= 0), operations are atomic
acquire(S)
wait until S > 0
dec(S)
release(S)
inc(S)
implementation using java monitors:

Q: What do the following terms mean in the context of MPI send/recv?
- blocking/non-blocking
- synchronous/asynchronous
You may explain it via the following operations:
Send, SSend, Isend, Issend, Recv, Irecv
A: blocking/non-blocking (concerns buffering only):
- blocking (Send, recv, ...): send/recv buffer is available for reuse (doesn't mean matching recv has been posted)
- non-blocking (Isend, Irecv, ...): one has to check themselves if the send\recv buffer is available for reuse. must return to the user without requiring a matching receive at the destination (but data might be sent before returning!)
synchronous/asynchronous (concerns when send returns):
- synchronous: only completes successfully if matching receive was posted and receiver started to receive message (rendezvous; this has true blocking semantics)
- asynchronous (one of the options for Send, default): does not wait for matching receive to be posted. message is stored in local buffer
There are 4 different send modes and 1 receive mode, both in blocking and nonblocking variant:
- Send (default): data is copied into local buffer, returns OR call will only return once the data has been transmitted to the receiver (same as Ssense then. e.g. if buffer space full)
- Ssend (synchronous): only completes successfully if matching receive was posted and receiver started to receive message (rendezvous)
- Bsend (buffering): data is copied into local buffer if there is no matching receive (else it can send directly)
- Rsend (ready): can only be called if there is matching receive. can offer better perf., otherwise can be replaced by Ssend or Send
- Recv (receive): In case there's a receive operation started and no matching send is posted, the process will block until the receive buffer is filled with the data it is expecting. In this situation an computation or other MPI communication will be blocked/halted unless MPI_Recv has returned.
non-blocking variants of these methods may return before the send/receive has completed. We use MPI.Wait() (either MPI.Wait() returns or MPI.Test() returns true) to make sure the methods have completed and send/recv buffers can be reused:
Isend, Issend, Ibsend, Irsend, Irecv
difference between Issend and Isend:
both return immediately
only difference is semantics of MPI.Wait():
- Isend returns from MPI.Wait() if either the message is saved in a buffer or it has been transmitted to the receiver
- Issend only returns from MPI.Wait() if the message has been transmitted to the receiver

Q: Fill out the following (standard mpi send constructor in MPJ):
Hint: only one buffer
What are the differences to that of Comm.Recv(...)?
A: basically the exact same, just src instead of dest
Unless sendtype and recvtype differ, sendcount and recvcount should be equal.

Q: How do the following MPI collective operations work?
- Reduce, Allreduce
- Scan
A: MPJ documentation:
offsets only concern where message are saved in buffer
no root for scan! works based on rank
visually:
implementations:

Q: How do the following MPI collective operations work?
- Broadcast
- Alltoall
A: MPJ documentation:
similar to matrix transpose - every process gathers one column in its own buffer
visually:
example: vector-matrix-multiplication
- broadcast the full vector to all processes
- scatter the matrix (per row), transmitting one row to each process
- compute subresults locally (one vector entry)
- gather full resulting vector

Q: How do the following MPI collective operations work?
- Gather
- Scatter
- Allgather
A: MPJ documentation:
collect buffer of each process in one buffer
- sendcount: how many items to send to each thread, per thread. usually same as recvcount (only if e.g. another data type is used this makes sense)
distribute buffer elements from one process to others
visually:
example: vector-matrix-multiplication
- broadcast the full vector to all processes
- scatter the matrix (per row), transmitting one row to each process
- compute subresults locally (one vector entry)
- gather full resulting vector

Q: What are differences between the actor model and communicating sequential processes?
Name three differences regarding:
- processes/actors
- how message passing works respectively
- synchronization
A: Both are mathematical models for concurrent computation involving actors/processes passing messages
Key differences:
- CSP processes are anonymous \(\longleftrightarrow\) actors have identities
- CSP uses explicit channels for message passing\(\longleftrightarrow\)  actor systems transmit messages to named destination actors
- CSP message-passing is fundamentally synchronous, rendezvous between sender/reveiver \(\longleftrightarrow\) actor mode message passing is fundamentally asynchronous
MPI is an implementation of message passing and uses ideas from both concepts:
- Communicators in MPI correspond to indirect naming in CSP (explicit channels)
- The idea of passing messages between computational units originated from the Actor Model first and is also present in MPI.

Sei \(A\) ein Las-Vegas-Algorithmus mit
\(Pr[A(I) \text{ ist korrekt}] \geq \varepsilon\)
Sei \(A_\delta\) für \(\delta > 0\) ein Algorithmus, der entweder die erste Ausgabe verschieden von \(???\) ausgibt oder der nach \(N = \varepsilon^{-1} \ln(\delta^{-1})\) Versuchen \(???\) ausgibt
Beweise:
\(Pr[A_\delta(I) \text{ ist falsch}] \leq \delta\)
(Wiederholung Las Vegas)

Q: Sei \(A\) ein Monte-Carlo-Algorithmus, der entweder JA oder NEIN ausgibt, mit
 \(Pr[A(I) =JA] = 1,\; I\text{ ist JA-Instanz}\)
 \(Pr[A(I) =NEIN] \geq \varepsilon, \; I\text{ ist NEIN-Instanz}\)
Sei \(A_\delta\) für \(\delta > 0\) ein Algorithmus, der entweder die erste Ausgabe von \(\text{NEIN}\) oder der nach \(N = \varepsilon^{-1} \ln(\delta^{-1})\) Versuchen \(\text{JA}\) ausgibt
Beweise:
\(Pr[A_\delta(I) \text{ ist falsch}] \leq \delta\)
(Wiederholung Monte Carlo einseitiger Fehler)
A: Wenn A(I)=Nein ist die Ausgabe immer korrekt, denn dann ist I sicher eine NEIN-Instanz.
Wenn A(I)=Ja kann es sein, dass I doch eine NEIN-Instanz ist.

Q: Sei \(\varepsilon > 0\) und \(A\) ein Monte-Carlo-Algorithmus, der entweder JA oder NEIN ausgibt, mit
 \(Pr[A(I) \text{ korrekt}] \geq 1/2+\varepsilon\)
Sei \(A_\delta\) für \(\delta > 0\) ein Algorithmus, der \(N = 4\varepsilon^{-2} \ln(\delta^{-1})\) Aufrufe macht und dann die Mehrheit der erhaltenen Antworten ausgibt
Beweise:
\(Pr[A_\delta(I) \text{ ist falsch}] \leq \delta\)
(Wiederholung Monte Carlo zweiseitiger Fehler)
Hint: \(\delta = \varepsilon\)
A: \(N/2\) so gewählt, dass sich mit zweiter Chernoff-Schranke alles ausser \(\delta\) wegkürzt
Fehlerreduktion geht nur, wenn Fehlerwahrscheinlichkeit strikt kleiner als \(1/2\) ist.

Q: Target Shooting: Wie sollten wir N wählen, damit die Ausgabe des Algorithmus mit W'keit mindestens \((1-\delta)\) im Intervall \([(1-\varepsilon)\frac{|S|}{|U|}, (1+\varepsilon)\frac{|S|}{|U|}]\) liegt?
Gegeben:
- zwei endliche Mengen \(S, U\) mit \(S \subseteq U\)
- \(I_s: U \to \{0,1\}\) mit \(I_s(u) = 1 \iff u \in S\)
Gesucht:
- möglichst gute Schätzung für\(\frac{|S|}{|U|}\)
Jedes \(Y_i = I_s(u_i)\) ist Bernoulli-verteilt mit \(p = \frac{|S|}{|P|}\)
Hint: Chernoff zwei Mal!
A: wir wählen \(N\) zufällige Punkte und testen jeweils, ob der Punkt in \(S\) ist
Wie sollten wir \(N\) wählen?

Q: Wie funktionieren folgende Primzahltests, was ist ihre Fehlerwahrscheinlichkeit?
- Fermat (Analyse: Carmichael)
- Euklid (Analyse: \(Z_n^*\))
A: Fermat-Primzahltest:
Wähle \(a \in \{2, ..., n-1\}\) uniform:
if \(\gcd(a, n) > 1\) oder \(a^{n-1} \neq 1\): return false
else: return true
- "nicht prim" immer richtig
- \(Pr[\text{"prim"}\,|\, \text{nicht prim}] = \frac{|PB_n|}{n-1}<1/2\) wenn \(n\) nicht Carmichael \(\implies\) Verbesserung auf \(\frac{1}{2^k}\) durch k*Wiederholung
\(PB_n\) = \(\{a \in Z_n^* \,| \,a^{n-1} = 1\}\)
\(n\) ist Carmichael Zahl \(\iff n\) nicht prim, \(PB_n = Z_n^*\)
Test failed bei allen a \(\in PB_n\), somit in \(\frac{|PB_n|}{n-1}\) der Fälle. Falls \(n\) keine Carmichael-Zahl ist (\(PB_n \neq Z_n^*\)), gilt nach Lagrange-Theorem: \(|PB_n| \leq \frac{|Z_n^*|}{2}\) und somit \(\frac{|PB_n|}{n-1} < 1/2\)
Euclid-Primzahltest (GGT):
Wähle \(a \in \{2, ..., n-1\}\) uniform:
if \(\gcd(a, n) > 1\): return "nicht prim"
else: return "prim"
- "nicht prim" immer richtig
- \(Pr[\text{"prim"}\,|\, \text{nicht prim}] = \frac{|Z_n^*|}{n-1}\) (kann sehr schlecht sein, zB. für \(n=p^2, p\) prim)
- Runtime: \(O(\log(a*n)^3)\)für Euclidean Algorithm
Zertifikate  für \(n\) nicht prim:
- Triviales: \(a\), sodass \(a | n\) \(\implies\) wir müssen nur bis \(\sqrt{n}\) überprüfen
- Euklid: \(a\), sodass \(\gcd(a,n) > 1\)
- Fermat: \(a\), sodass \(a^{n-1} \neq 1 \mod n\)
- Miller-Rabin: Sei \(n-1 = 2^kd, d \in \mathbb{N}\) ungerade. \(a\), sodass:

Q: Wie funktionieren folgende Algorithmen?
- QuickSort
- QuickSelect
Was ist ihre Laufzeit, welche Art von randomisiertem Algorithmus sind sie (Monte Carlo oder Las Vegas)?
A: beide immer korrekt, Laufzeit ist Zufallsvariable \(\implies\) Las Vegas
QuickSelect: Partitionieren von QuickSort mit Binary Search. Wir partitionieren und sehen uns dann den Index an; linker Teil wenn zu gross , rechter wenn zu klein

Q: Which consensus numbers do the following datastructures/objects have:
- atomic registers
- FIFO queue (without peek)
- LIFO stack (without peek)
- FIFO queue (with peek)
- TAS
- CAS
A: - atomic registers: 1
- FIFO queue (without peek): 2
- LIFO stack (without peek): 2
- FIFO queue (with peek):  \(\infty\)
- TAS: 2
- CAS: \(\infty\)
2 thread consensus with TAS
2 thread consensus with Stack
2 thread consensus with Queue
N thread consensus with Queue with atomic peek (peek needs some form of synchronized or CAS or similar)
- propose value
- enqueue thread id
- return proposed(q.peek()), which returns the first added thread id's proposal
N thread consensus with CAS:

Q: Give an algorithm solving 2-thread consensus using TAS!
A: 2 thread consensus with TAS
-----------------------
- atomic registers: 1
- FIFO queue (without peek): 2
- LIFO stack (without peek): 2
- FIFO queue (with peek):  \(\infty\)
- TAS: 2
- CAS: \(\infty\)
2 thread consensus with Stack
2 thread consensus with Queue
N thread consensus with Queue with atomic peek (peek needs some form of synchronized or CAS or similar)
- propose value
- enqueue thread id
- return proposed(q.peek()), which returns the first added thread id's proposal
N thread consensus with CAS:
general form of a consensus implementation

Q: Give an algorithm solving N-thread consensus using CAS!
Extra: How could we solve N-thread consensus with a wait-free FIFO queue that supports atomic peek()?
A: N thread consensus with CAS:
N thread consensus with Queue with atomic peek (peek needs some form of synchronized or CAS or similar)
- propose value
- enqueue thread id
- return proposed(q.peek()), which returns the first added thread id's proposal
-----------------------
- atomic registers: 1
- FIFO queue (without peek): 2
- LIFO stack (without peek): 2
- FIFO queue (with peek):  \(\infty\)
- TAS: 2
- CAS: \(\infty\)
2 thread consensus with TAS
2 thread consensus with Stack
2 thread consensus with Queue
general form of a consensus implementation

Q: Give an algorithm solving 2-thread consensus using a wait-free Stack/Queue!
A: 2 thread consensus with Stack
2 thread consensus with Queue
-----------------
- atomic registers: 1
- FIFO queue (without peek): 2
- LIFO stack (without peek): 2
- FIFO queue (with peek):  \(\infty\)
- TAS: 2
- CAS: \(\infty\)
2 thread consensus with TAS
N thread consensus with Queue with atomic peek (peek needs some form of synchronized or CAS or similar)
- propose value
- enqueue thread id
- return proposed(q.peek()), which returns the first added thread id's proposal
N thread consensus with CAS:

Q: Prove the following:
Theorem: There is no wait-free implementation of a FIFO queue with atomic registers
A: 1. Show/state that FIFO queue can implement 2-thread consensus
2. Assume there is a wait-free implementation of a FIFO queue with atomic registers
\(\Rightarrow\) there is a 2 thread consensus implementation using atomic registers, a contradiction

Q: List 3 approaches to apply parallelism to improve sequential processor performance!
A: • Vectorization: SIMD, N-at a time
• Instruction Level Parallelism (ILP): execute multiple instructions in parallel: Superscalar CPUs, branch prediction, out of order execution, pipelining
• Pipelining: break instructions into several stages so different stages (i.e. different parts of several instructions) can be executed at the same time

Q: What are two improvements we can make to a TAS-lock? Write pseudocode!
A: 1. TATAS (test and test and set)
reduces congestion on l
2. exponential backoff
empirically proven to reduce congestion (by a ton!)
TAS lock:
l.getAndSet(value semantics:
- returns previous ("get")
- writes value ("sets")

Q: Das Long-Path-Problem ist wie folgt definiert:
- input: \(G, k \in \mathbb{N}\)
- output: true \(\iff G\) enthält Pfad der Länge \(k\)
Bunte Pfade Problem:
- input: \(G\), \(\gamma: V \to [k]\)
- output: true \(\iff G\) enthält bunten Pfad der Länge \(k-1\)(mit \(k\) Knoten; alle \(k\) Knoten haben verschiedene Farbe)\(\iff \)___________
1. Vervollständige den Pseudocode der Methode Bunt(G,i) und Regenbogen(G,\(\gamma\)) und die Lücke oben!
2. Was ist die Laufzeit von Regenbogen(G,\(\gamma\))?
A: 1. Pseudocode
Bunte Pfade:
- input: \(G\), \(\gamma: V \to [k]\)
- output: true \(\iff G\) enthält bunten Pfad der Länge \(k-1\)(mit \(k\) Knoten; alle \(k\) Knoten haben verschiedene Farbe)\(\iff \bigcup_{v \in V} P_{k-1}(v) \neq \emptyset\)
2. Laufzeit:
pro Aufruf von Bunt(G,i) (Terme des Produkts von aussen nach innen; Faktor \(i\) für \(\gamma(v) \notin R\)):
\(O(\sum_{v \in V} \deg(v) {k \choose i} i) = O({k \choose i}i m)\)
Gesamt (Summenformel von \(i=0\) bis \(k\) ist \(2^k\), \(i\leq k\)):
\(O(\sum_{i=1}^{k-1} {k \choose i} im) = O(2^kmk)\)
------------------------------
Zum Algorithmus:
- LongPath(G,k) lösen wir mit Regenbogen(G,\(\gamma\)) wobei \(\gamma: V \to [k+1]\) eine zufällig gleichverteile Färbung von \(V\) ist
- \((G,\gamma)\) enthält einen bunten Pfad der Länge \(k\)  \(\implies G\) hat einen Pfad der Länge \(k\), womit das Long-Path Problem gelöst ist
Wir definieren folgende Menge für unseren DP-Algorithmus:
- \(P_i(v) = \{S \in {[k] \choose i+1} \; | \; \exists \text{\;in $v$ endender genau mit $S$ gefärbter bunter Pfad}\}\)
(die Menge aller Färbungen von \(i+1\) Knoten mit \(k\) Farben, für die es in \(v\) endenden Pfad mit selber Färbung gibt)
Long Path: NP-schwer, kann auf Hamiltonkreis-Problem reduziert werden

Q: Was sagt die binomische Formel?
Beweise mit ihr folgendes:
\(\sum_{k=0}^{n} {n \choose k} = 2^n\)
A: \((a+b)^n = \sum_{k=0}^n {n \choose k} a^kb^{n-k}\)
Herleitung:
\((a+b)^n = (a+b)(a+b)\cdots(a+b)\)
Für jeden Term der neuen Summe müssen wir uns also \(n\) mal zwischen \(a\) und \(b\) entscheiden, wir bilden also eine Menge \(E_i= \{e_1, e_2, \dots, e_k\}\), wobei \(e_i \in E \iff\) wir entscheiden uns für \(a\) bei Term \(i\) des Produkts. Zwei solche Mengen \(E_i, E_j\) korrespondieren zum gleichen Term vom Produkt, wenn sie gleich gross sind und es gibt \({n \choose k}\)viele solcher Mengen mit gleicher Kardinalität.
Sei \(a=b=1\):
\((a+b)^n =2^n= \sum_{k=0}^n {n \choose k}\)
Intuitiv: \(2^n\) ist die Zahl aller möglichen Teilmengen, in der Summe wird die Zahl der Teilmengen aufgeteilt auf verschiedene Kardinalitäten summiert

Q: Find the minimum \(p\) such that \(T_p = T_\infty\) for the following task graph:
(use the strategy seen during the exercise session!)
A: aufpassen: nodes sind tasks normalerweise, auch zB. u.U. Variablen

Q: Wie können wir das Maximum-Bipartite-Matching Problem mittels maximaler Flüsse lösen?
A: Wir bilden einen bipartiten Graphen auf folgendes Netzwerk ab:
\(G = (U \uplus W, E) \mapsto N_G = (U \uplus W \uplus \{s,t\}, A,c,s,t)\)
- \(s \neq t\) sind zusätzliche Knoten
- \(A = \{s\} \times U \;\cup \;\{(u,w) \in U\times W \;|\;\{u,w\} \in E\} \;\cup\; W \times \{t\}\)
- c \(\equiv1\)
Anschliessend wenden wir Ford-Fulkerson an
Es gilt:
\(\max_{f \text{ Fluss in }N_G}val(f) = \max_{M \text{ Matching in }G} |M|\)
Wobei wir mit \(f\) auch ein konkretes kardinalitätsmaximales Matching finden können (Kanten mit \(f(e)=1\))
(nicht eindeutig, ob Kanten von \(s\) nach \(A\) oder \(B\) gehen \(\Rightarrow\) es gibt zwei Wege, \(N_G\) zu konstruieren)

Q: Wie können wir das kantendisjunkte/knotendisjunkte u-v-Pfade Problem mittels maximaler Flüsse lösen?
1. Wie definieren wir \(N_G^* = (V,A,c,u,v)\)?
2. Wie können wir nach Berechnung des maximalen Flusses die kantendisjunkten Pfade ablesen?
3. Welche Veränderung des Graphs \(N_G^*\) ist zum finden knotendisjunkter Pfade notwendig?
A: Wir konstruieren ein Netzwerk, in dem alle Kanten von ungerichtet zu zwei gerichteten umgewandelt werden:
\(G = (V,E), u,v \in V\; \mapsto\; N_G^* = (V,A,c,u,v)\)
- \(A = \{(x,y),(y,x) | \{x,y\} \in E\}\)
- \(c \equiv 1\)
1. Berechne ganzz. maximalen Fluss in \(N_G^* \Rightarrow\) Flusswerte \(\in\{0,1\}\)
2. Starte bei \(u\) und finde einen Pfad nach \(v\) durch noch nicht besuchte Kanten mit Fluss \(1\)
3. Markiere Kanten als besucht
4. Wiederhole \(val(f)\) mal
(bei Kreisen: lösche Kanten)
\(\max_{f \text{ Fluss in }N_G}val(f) =\)maximale Anzahl kantendisjunkter \(u-v\)-Pfade = Grösse des kleinsten u-v-Kantenseparators = min. Anzahl Kanten, die \(u\) und \(v\) trennen
Für knotendisjunkte u-v-Pfade:
Wir ersetzen jeden \(x \in V \setminus \{u,v\}\) durch \(x_{\text{in}}\) und \(x_{\text{out}}\), wobei mit \(x_{\text{in}}\) alle eingehenden und \(x_{\text{out}}\) alle ausgehenden Kanten verbunden sind und es eine Kante \(e=(x_{\text{in}},x_{\text{out}})\) mit \(c(e) = 1\) gibt.
Hiermit lässt sich der Satz von Menger beweisen:
G ist \(k\)-zusammenhängend \(\iff\) für alle \(u,v\) (\(u \neq v\)) gibt es mind. \(k\) intern knotendisjunkte \(u-v\)-Pfade
\(\Leftarrow\): einfach
\(\Rightarrow\): mit obigem Algorithmus

Prove that the Peterson Lock Algorithm satisfies mutual exclusion!
The code is given here as reference:

Prove that the following algorithm does not satisfy mutual exclusion using a state space diagram:

Q: Das Min-Cut Problem ist wie folgt:
Input: ungewichteter, ungerichteter Multigraph (mehrere Kanten zwischen Knoten möglich) ohne Schleifen
Output: \(\mu(G) = \min_{C \subseteq E,\,(V,E\setminus C) \text{ unzusammenhängend}} |C|\)  (Grösse des kleinstmöglichen Kantenschnitts)
Wie kann man es mit Flüssen und mit (random) Kantenkontraktionen lösen? Gib die jeweiligen Laufzeiten und die Fehlerwahrscheinlichkeit des randomisierten Algorithmus (eine Kontraktion, ein Aufruf von \(Cut(G)\), MC Wiederholungen) an!
A: Lösungsansätze:
1. Mit Flüssen (minimale s-t-Schnitte mit fixem s; Dynamic Trees)
\((n-1)O(mn\log n) = O(mn^2\log n) = O(n^4\log n)\)
2. Mit Kantenkontraktion
Das Kontrahieren von \(e =\{u,v\}\) gibt uns \(G / e\). \(u\) und \(v\) werden zu einem neuen Knoten \(x_{u,v}\), der zu allen Kanten inzident ist, zu denen \(u\)/\(v\) inzident war, ausser denen zwischen \(u\) und \(v\).
- \(\mu(G/e) \geq \mu(G)\)
- es gibt minimalen Kantenschnitt \(C\), sodass \(e \notin C \implies \mu(G/e)=\mu(G)\)
(eindeutiger Schnitt wenn nur noch zwei Knoten. Laufzeit: \(O(n^2)\), \(n\) Iterationen je \(O(n)\))
- Analyse von einer Kantenkontraktion:
Sei \(C\) ein minimaler Schnitt mit \(|C| = k\):
\(\Pr[\mu(G) = \mu(G/e)] \geq \Pr[e \notin C] = 1-\frac{k}{|E(G)|}\geq1-\frac{k}{\frac{1}{2}nk} = 1 - \frac{2}{n}\)
Begründung Schritt 3: Für \(v \in V\) ist \(deg(v) \geq k\) (sonst ist \(|C| < k\)) + Handschlaglemma: \( |E(G)| = \frac{1}{2} \sum_{v \in V} deg(v) \geq\frac{nk}{2}\)
- Analyse des gesamten Algorithmus \(Cut(G)\):
\(\hat{p}(G) = \Pr[\text{Cut(G) gibt $\mu(G)$ aus}]\) (also keine essenzielle Kante wird kontrahiert)
\(\hat{p}(n) = \inf_{G=(V,E), |G| = n} \hat{p}(G)\)
Für alle \(n\geq 3:\hat{p}(n) \geq (1-\frac{2}{n})\hat{p}(n-1)\) (Proof at the end)
\(\Rightarrow \hat{p}(n) \geq \frac{n-2}{n} \frac{n-3}{n-1} \frac{n-4}{n-2} \dots \frac{2}{4} \frac{1}{3} \hat{p}(2) = \frac{2}{n(n-1)} = \frac{1}{n \choose 2}\)
Somit ist der Erwartungswert der Wiederholungen, bis \(\mu(G)\) ausgegeben wird, höchstens \(n \choose 2\).
- Monte Carlo Wiederholungen:
Wir wiederholen \(Cut(G)\) \(\lambda{ n \choose k}\) mal und geben den niedrigsten gesehenen Wert aus.
Laufzeit: \(\lambda{n \choose 2}O(n^2) = O(\lambda n^4)\)
Fehlerwahrscheinlichkeit:
\(\Pr[\text{Output}\neq \mu(G)] = \Pr[\text{Cut(G) gibt nie $\mu(G)$ aus}]= (1-\hat{p}(n))^{\lambda{n \choose 2}}\leq (1-\frac{1}{n \choose 2})^{\lambda{n \choose 2}} \leq e^{-\lambda}\)
Nicht besonders berauschend, es gibt auch deterministischen Algorithmus mit ähnlicher Laufzeit...
Aber: Bootstrapping!
Idee: letzte Kontraktionen besonders "teuer" - wir brechen davor ab und wenden für diese obigen Algorithmus mit \(\lambda = 1\) an.
Nach erster Iteration Laufzeit \(O(\lambda n^3)\), im Grenzwert \(O(n^2\text{polylog}( n))\)
-------------------------

Q: Wie ist das kleinster umschliessender Kreis Problem definiert?
Gib zwei einfache, deterministische und einen einfachen, randomisierten Algorithmen für das Problem an und erkläre deren Laufzeit und Korrektheit!
A: Das kleinster umschliessender Kreis Problem ist wie folgt definiert:
Input: eine endliche Punktemenge \(P \subseteq \mathbb{R}^2\)
Output: \(C(P)\), kleinster umschliessender Kreis von P (\(P \subseteq C^\bullet\))
Wir überprüfen für alle Mengen von Punkten aus \(P\) mit Kardinalität 3, ob die dadurch definierte minimale Kreisscheibe alle Punkte aus \(P\) enthält
Laufzeit:
Laufzeit: \(O(n^3)\)
Hier finden wir die Kreisscheibe aus 3 Punkten aus \(P\) mit maximalem Radius.
Beweis (Korrektheit):
Wir nehmen an, \(C(T)\) (Zeile 5) definiert nicht den kleinsten umschl. Kreis. Somit gibt es \(Q\), sodass \(\text{radius}(C(Q)) < \text{radius}(C(T))\) und \(C(Q)\) umschliesst alle Punkte aus \(P\). Ein Widerspruch, da \(C(Q)\) mindestens einen Punkt aus \(T\) dann nicht umschliessen kann.
Erwartete Laufzeit:
erwartete Laufzeit ändert sich nicht, wenn wir statt \(3\; C > 3\) Punkte wählen

Q: Das kleinster umschliessender Kreis Problem ist wie folgt definiert:
Input: eine endliche Punktemenge \(P \subseteq \mathbb{R}^2\)
Output: \(C(P)\), kleinster umschliessender Kreis von P (\(P \subseteq C^\bullet\))
Erkläre den in der Vorlesung gesehenen finalen randomisierten Algorithmus für das Problem!
Was ist die erwartete Laufzeit?
A: Idee: Wir wählen zufällig \(Q \subseteq P\) mit \(|Q| = 11\), konstruieren \(C(Q)\) in konstanter Zeit und überprüfen dann, ob alle \(P \in C^\bullet(Q)\) sind. Wenn nicht, verdoppeln wir alle Punkte ausserhalb von \(C(Q)\), von denen wir wollen, dass sie in zukünftigen Iterationen gewählt werden (Zeile 2).
Erwartete Laufzeit: Eine Iteration \(O(n)\) (jeweils für Zeile 2 und 4), \(O(\log n)\) erwartete Iterationen \(\implies O(n \log n)\)
\(\Rightarrow\) Las Vegas Algorithmus
Analyse (für erwartete Iterationen):
- Upper bound:
Schritt 2: Sampling Lemma. Schritt 5: Teleskopieren
- Lower bound:
maximal 3 Punkte sind essentiell, nach \(k\) Runden muss mind. einer dieser Punkte \(k/3\) mal verdoppelt worden sein und hat somit \(2^{k/3}\) Kopien (pro Runde können maximal 2 Punkte in Q gewählt werden, sonst terminiert der Algorithmus)
- Zusammen:
Sampling Lemma:
Proof:

Q: Beweise folgendes Lemma (Sampling Lemma):
A: Proof:

Q: Convex Hull:
Wie ist folgende Ordnung definiert?
- \(p_1 \prec_q p_2\)
Vervollständige:
A: ---------------
- Bestimmung von p links von qr:
erste Zeile von zweiter und dritter Abziehen, dann nach dritter Spalte entwickeln
Randkante \(\iff\) alle Punkte links von Randkante

Q: Matching-Algorithmen: Was ist die Laufzeit folgender Algorithmen, wie funktionieren sie grob gesagt und wofür werden sie gebraucht?
- Greedy Matching
- Augmentierende Pfade
- Hopcroft-Karp
- Gabow (perfekte Matchings)
- Gabow (kardinalitätsmaximale Matchings)
A: Greedy-Matching: wähle zufällig eine Kante, füge sie zu M hinzu und lösche sie und alle inzidenten Kanten bis \(|E| = \emptyset\)
\(\implies\) findet inklusionsmaximales Matching in \(O(|E|)\)
Augmentierende Pfade (in bipartitem Graphen): finde augm. Pfad \(P\) (mit BFS in Stufen), verbessere \(M\) mit \(M = M \oplus P\) bis \(M\) maximum (kein augm. Pfad mehr in \(G\))
\(\implies\) kardinalitätsmaximales Matching in \(O( {|V|}*|E|)\)
Hopcroft-Karp (in bipartitem Graphen): Verbesserung von augm. Pfaden: kardinalitätsmaximales Matching in bipartitem Graphen in \(O(\sqrt {|V|}*|E|)\)
(gleiche Laufzeit auch allgemein möglich in nicht-bipartiten Graphen)
Gabow: Finden eines perfekten Matchings in \(2^k\)-regulärem bipartiten Graphen in
\(O(|E|)\): Berechne Eulertour, lösche jede zweite Kante, iteriere
Das Finden der Eulertour und löschen jeder zweiten Kante geht in \(C*|E|=O(|E|)\). Pro Schritt wird \(|E|\) halbiert, womit die Laufzeit wie folgt ist:
\(\sum_{i=1}^k C*\frac{|E|}{2^{i-1}} =C|E|*\sum_{i=1}^k \frac{1}{2^{i-1}} \leq C|E|*2=O|E|)\)
(lässt sich verallgemeinern für \(k\)-reguläre bipartite Graphen)
Gabow: \(O(|V|^3)\) für kardinalitätsmaximales Matching in gewichteten Graphen von kleinstmöglichem Gewicht (insbesondere für metrisches TSP hilfreich)

Q: What is the difference between the concept of coarse-grained and fine-grained locking?
1. What is their general concept
2. How do the implementations for a linked list look like? How do we handle locking for remove/add/contains?
A: - coarse-grained:
One lock protects the whole datastructure. Works but results in a significant bottlenkneck and eliminates parallelism.
- fine-grained:
Only lock part of the datastructure (ideally the least amount of objects necessary) by splitting it in pieces that can be operated on independently (no mutual exclusion is then required if there are no overlaps!)
However: requires careful consideration of special cases
- in this example: one slow thread can block other quicker ones, a lot of locking/unlocking happening (\(O(n)\)). can be parallelized better but still not ideal
- contains and add don't need hand over hand but one lock (contains is possibly fine without too but lecture does it differently, probably some invariant but not practically required)
---------------
other concepts (first 4 with locks):
- coarse-grained
- fine-grained
- optimistic synchronization
- lazy synchronization
- lock-free

Q: What is the concept of optimistic synchronization compared to lazy synchronization?
A: - optimistic synchronization
1. Find nodes without locking
2. then lock nodes and
3. check that everything is okay (validation)
- lazy synchronization
validate doesn't traverse list, instead just checks if not marked and not disconnected
contains is wait-free, no locking: simply returns if node can be reached and is not marked as deleted
hand over hand locking for add and remove, no locking for contains
extra: skip lists:
--------------
other concepts (first 4 with locks):
- coarse-grained
- fine-grained
- optimistic synchronization
- lazy synchronization
- lock-free

Q: We have seen 3 lock-free datastructures during the lecture:
- Lock-free stack
- Lock-free list-based set
- Lock-free unbounded Queue
What methods/techniques are used to implement them, respectively? Read through the solution and explain the code!
A: Lock-free stack:
- using CAS to set remove/add to head of stack atomically
- not necessarily better performance (backoff can increase it!)
- not wait-free
Lock-free list-based set:
- uses DCAS to atomically set reference and mark bit
- threads help each other (in find method)
example where CAS doesn't work (thread A calls remove a, thread B remove b)
Lock-free unbounded Queue:
- uses CAS and helping technique

Q: Lock free list: Why does CAS alone not work here?
A: example where CAS doesn't work (thread A calls remove a, thread B add b. add b does not happen; examples with two remove also exist)
-------
Lock-free stack:
- using CAS to set remove/add to head of stack atomically
- not necessarily better performance (backoff can increase it!)
- not wait-free
Lock-free list-based set:
- uses DCAS to atomically set reference and mark bit
- threads help each other
Lock-free unbounded Queue:
- uses CAS and helping technique

Q: What makes a stencil different to a map? (parallel operators/programs)
Give one example for each!
A: A stencil is a map operator that does not have to operate on each element independently, e.g. floating average with neighbours
Definition of map operator:
- operates on each element of a collection independently to create a new collection of the same size
Accepted examples:
- vector addition that computes the sum of a collection of tuples (containing the n^th element of both vectors, see below for FJ code)
- doubling every value in array
- converting every array element to some other format

Q: Coupon Collector:
Es gibt \(n\) verschiedene Bilder, in jeder Runde erhalten wir gleichwahrscheinlich eine Kopie eines der Bilder.
\(X :=\) Anzahl Runden, bis wir alle \(n\) Bilder gesammelt haben
Wann ist \(E[X]\) niedriger: Wenn uns die ersten \(0.1n\) Bilder oder die letzten \(0.1n\) Bilder geschenkt werden? Berechne die jeweiligen Erwartungswerte!
A: letzte k Bilder sind besser

Q: Das Long-Path-Problem ist wie folgt definiert:
- input: \(G, B \in \mathbb{N}\)
- output: true \(\iff G\) enthält Pfad der Länge \(B\)
1. Wie ist das Bunte Pfade Problem definiert und wie hilft es uns, das Long-Path Problem zu lösen?
2. Vervollständige: \(P_i(v) = \{\)___________\(\}\)
A: 1. Bunte Pfade Problem:
- input: \(G\), \(\gamma: V \to [k]\)
- output: true \(\iff G\) enthält bunten Pfad der Länge \(k-1\)(mit \(k\) Knoten; alle \(k\) Knoten haben verschiedene Farbe\(\iff \bigcup_{v \in V} P_{k-1}(v) \neq \emptyset\)
Wir setzen \(B = k+1\) und wählen eine zufällig gleichverteilte Färbung \(\gamma: V \to [k+1]\)
- \((G,\gamma)\) enthält einen bunten Pfad der Länge \(k\)  \(\implies G\) hat einen Pfad der Länge \(k\), womit das Long-Path Problem gelöst ist
2. DP-Mengen-Definition:
- \(P_i(v) = \{S \in {[k] \choose i+1} \; | \; \exists \text{\;in $v$ endender genau mit $S$ gefärbter bunter Pfad}\}\)
(die Menge aller Färbungen von \(i+1\) Knoten mit \(k\) Farben, für die es in \(v\) endenden Pfad mit selber Färbung gibt)
---------------------------------
Algorithmus:

Q: Wir lösen das Long-Path-Problem (gibt es Pfad der Länge \(k\)) wie folgt:
1. Wir färben \(V\) zufällig gleichverteilt mit \(k+1\) Farben
2. Wir finden heraus, ob es einen bunten Pfad (alle Knoten verschieden gefärbt) mit \(k+1\) Knoten gibt und geben den Wahrheitswert davon aus
Nun fragen wir uns, was ein lower bound für die Fehlerwahrscheinlichkeit dieses Algorithmus ist (Ausgabe false wobei \(G\) doch einen Pfad der Länge \(k-1\) enthält). Vervollständige und begründe!
\(p_\text{erfolg} :=\) W'keit, dass es bunten Pfad in \((G,\gamma)\) gibt
Sei P ein Pfad mit \(k\) Knoten:
- Ein Versuch:
Laufzeit: \(O(2^kkm)\)
\(p_\text{erfolg} \geq \Pr[\text{P ist bunt}] = \)___  \(\geq\)  ___
- \(\lceil{\lambda e^k}\rceil\) Versuche:
Laufzeit: \(O(\lambda (2e)^kkm)\)
Wahrscheinlichkeit, dass Algorithmus Pfad nicht findet \(\leq\) ____ \(\leq (e^{-e^{-k}})^{\lceil{\lambda e^k}\rceil} \leq\) _______
A: Erwartete Antwort:
Mit folgender Begründung für 1:
-----------------------------
Diesen Fakt verwenden wir:

Q: Ein Graph \(G\) ist bipartit \(\iff\)\(G\) enthält keine Kreise _____ Länge
A: Ein Graph \(G\) ist bipartit \(\iff\)\(G\) enthält keine Kreise ungerader Länge
Können wir einfach wie folgt checken:
BFS, abwechselnd Knoten färben. Wenn ein Knoten einen Nachbarn mit gleicher Farbe hat, return false, sonst true

Q: Solve the following wait/notify task by filling in the blanks:
Hints:
- if we are waiting for some condition to change as consumer, put synchronized OUTSIDE the while loop. otherwise condition could change right after while loop check, producer notifies but no one is waiting and after that we wait forever
- don't use synchronized with a reference that could change during execution of the synchronized block - store it in a variable and use that variable as the object! (or make sure reference cannot change)
- make sure synchronized block does not cover too little code leading to insufficient synchronization
- call OBJECT.notify explicitly specifying object if it's not this
A: - Solution
- make sure no deadlocks can happen when using nested synchronized blocks! this code leads to a deadlock e.g. (o1/o2 are static and shared):
- Subtle things one could do wrong in this task (credits to https://n.ethz.ch/~aellison/pprog2023):
- Could we have the `synchronized (...) { x.wait(); }` inside the while loop check? -> No. The required state change and `notify` could happen right after we check the while loop. Then we will wait forever. By using `synchronized` we ensure that the `notify` cannot occur while we are doing the check.
- Do we need to store `var next = customersLine.get(0);`? -> If we didn't store the customer in a variable and instead read `customersLine.get(0);` at different times, the following could happen:
    0. there are 2 customers in line, but neither of them have started waiting yet (so they both just finished executing `foodTruck.addCustomer(this)`)
    1. the `FoodTruck` thread writes `mealReady = true` (it was able to pass the while loop since there are customers in line)
    2. the `FoodTruck` thread reads `customersLine.get(0)`, but before it can acquire the lock, the first customer sees that his meal is ready and removes himself from the line (i.e. he passes the while loop and executes `foodTruck.serveCustomer(this)`). He can do this since the `FoodTruck` thread is not holding any locks. Now the second customer is at position 0.
    3. the `FoodTruck` thread acquires the lock on the first customer, then since `customersLine.get(0)` now points to the second customer, it will try to call notify on him without holding his lock. This leads to an exception.
- Should everything be wrapped inside the `synchronized (this) {...}` in FoodTruck? -> If not, the following could happen:
    0. there is 1 customer in line, but he hasn't started waiting yet (so the customer just finished executing `foodTruck.addCustomer(this)`)
    1. the `FoodTruck` thread writes `mealReady = true` (it was able to pass the `wait` since there is a customer in line)
    2. the customer continues: he sees that his meal is ready, so he can get past the `wait` and call `foodTruck.serverCustomer(this)`, removing himself from `customersLine`
    2. the `FoodTruck` thread gets an error when reading `customersLine.get(0)`, since the list is now empty.
    This solution also solves the previous problem, since by holding the lock the entire time we know that `customersLine.get(0)` will not change.

Q: Fork-Join:
Wir wollen wie folgt einen floating-average berechnen:
Vervollständige:
A: Idee: left und right felder, die im Konstruktor schon gesetzt werden und jeweils input Feld links/rechts von derzeitiger Sequenz enthalten
public class AvgFJ extends RecursiveAction{
    private double[] data;
    private int start;
    private int length;
    private double left;
    private double right;
    public static void fjAvg(double[] data) {
        ForkJoinPool fjp = new ForkJoinPool();
        AvgFJ task = new AvgFJ(data, 0, data.length, 0, 0);
        fjp.invoke(task);
    }
    public AvgFJ(double[] data, int start, int length, double left, double right){
        this.data = data;
        this.start = start;
        this.length = length;
        this.left = left;
        this.right = right;
    }
    protected void compute(){
        if(length == 1){
            data[start] = (left+data[start]+right)/3;
        }
        else{
            int newLength = length/2;
            AvgFJ firstHalf = new AvgFJ(data, start, newLength, left, data[start+newLength]);
            AvgFJ secondHalf = new AvgFJ(data, start + newLength, length - newLength, data[start+newLength-1], right);
            firstHalf.fork();
            secondHalf.compute();
            firstHalf.join();
        }
    }
}
start-length params:
newLength = length/2
- left has start = start, length = newLength
- right has start = start + newLength, length = length - newLength
from-to params:
mid = (from + to)/2
- left has from = from, to = mid
- right has from = mid, to = to
max triple: schlauer Weg, die überkreuzenden Tripel bei Aufteilung einzuschliessen: einfach eine Hälfte immer 2 grösser machen

What is the definition of a pack operation?

Q: Beweise:
Für jedes inklusionsmaximale Matching \(M_\text{inc}\) gilt:
\(|M_\text{inc}| \geq \frac{1}{2} |M_\text{max}|\)
A: Jede Kante in \(M_\text{max}\) hat mindestens einen Endpunkt in \(M_\text{inc}\) (sonst kein \(M_\text{inc}\) ).
Andererseits ist jeder Knoten aus \(M_\text{inc}\) maximal zu einer Kante aus \(M_\text{max}\) inzident (sonst \(M_\text{max}\) kein Matching):
Somit haben wir:
\(|M_\text{max}| \leq |\text{Endpunkte in }M_\text{inc}| \leq |2M_\text{inc}|\)
every edge in M_max is adjacent to some vertex in M_inc
but: there might be some vertices in M_inc that are not adjacent to any edge in M_max
More detailed explanation:
We have the two statements: (1): every edge in M_max is adjacent to at least 1 edge of M_inc (otherwise we could add that edge to M_inc) (2): Because M_max is a matching, every vertex in M_inc (of which there is 2 * |M_inc|) is adjacent to at most 1 edge in M_max (otherwise it cannot be a matching). From (1) we know that there is no edge in M_max that we don't count if we compare the number of vertices in M_inc to M_max using (2). From (2) we know: 2*|M_inc| >= |M_max| (we couldn't make this conclusion if we only had (2) and not (1) since that would allow for there to be edges in M_max that do not touch any vertex in M_inc)

Q: ForkJoin prefixsum with \(O(\log n)\) span:
Describe how the algorithm works by answering the following questions:
- What do we compute in the first and second pass respectively?
- How is "fromLeft" in the second pass defined?
- How do we get the final output?
A: 1. First pass: builds tree bottom up
sum = sum of sum of children with leaves sum being input values
2. Second pass: traverses tree top down
- Root given a fromLeft of 0
- Node takes its fromLeft value and:
left child: fromLeft = fromLeft
right child: fromLeft= fromLeft + left child’s sum (from part 1)
- At the leaf for array position i, output[i]=fromLeft+input[i] (we can get leafes by looking at array size)
fromLeft is basically prefix sum shifted to right by one
\(O(n)\) work, \(O(\log n)\) span
-------
\(O(n)\) span Quicksort is possible

Q: Artikulationsknoten finden:
Vervollständige den Pseudocode!
A: Weitere Infos:
\(low[v]\) - kleinste DFS (pre) Nummer, die durch gerichteten Pfad aus Baumkanten gefolgt von max. einer Restkante erreicht werden kann.
\(low[v]\) = \(\min\left\{dfs[v], \min_{(v,w) \in E} \left\{{dfs[w] \text{ wenn $(v,w)$ Restkante, $low[w]$ wenn $(v,w)$ Baumkante} }\right\}\right\}\)
\(v\) ist Artikulationsknoten \(\iff\)
1. \(v \neq\) root und \(v\) hat ein Kind \(w\) im DFS-Baum mit \(low[w] \geq dfs[v]\)
    wenn nicht: \(low[w] < dfs[v]\), es gibt einen Pfad von Vorgänger von \(v\) zu \(u\)
2. \(v = root\) und \(v\) hat \(\geq 2\) Kinder im DFS-Baum
"w erreicht maximal v, aber keine Knoten vor v"
Baumkante \(e = (v,w)\) ist Brücke \(\iff low[w] > dfs[v]\)
"w erreicht weder v noch Knoten vor v"
    wenn nicht: es gibt Kante zu \(v\) oder Vorgänger von \(v, \;v\) ist erreichbar durch anderen Weg von \(w\)
eine Restkante ist nie Brücke

Q: Write down the pseudocode of Dekker's Algorithm!
Hint: variables volatile boolean wantp, wantq; int turn
What properties out of the following does it fulfill:
- mutual exclusion
- deadlock-freedom
- starvation-freedom
- FIFO fairness
A: Properties:
- mutual exclusion
- deadlock freedom
- starvation freedom
not fair! doorway section can only be wantp = true, which does not guarantee who gets in CS first (turn variable decides)

Q: Wie funktioniert Gabows Algorithmus zum finden von perfekten Matchings in \(2^k\)-regulären bipartiten Graphen?
- Beschreibe den Algorithmus in einem Satz
- Zeige, dass die Laufzeit des Algorithmus \(O(|E|)\)ist
Hint: jede zweite Kante
A: Gabow: Finden eines perfekten Matchings in \(2^k\)-regulärem bipartiten Graphen in
\(O(|E|)\)
Idee: Berechne Eulertour, lösche jede zweite Kante, iteriere bis der Graph \(2^0\) regulär und somit ein perfektes Matching ist
Laufzeit: Das Finden der Eulertour und löschen jeder zweiten Kante geht in \(C*|E|=O(|E|)\). Pro Schritt wird \(|E|\) halbiert, womit die Laufzeit wie folgt ist:
\(\sum_{i=1}^k C*\frac{|E|}{2^{i-1}} =C|E|*\sum_{i=1}^k \frac{1}{2^{i-1}} \leq C|E|*2=O(|E|)\)
(lässt sich verallgemeinern für \(k\)-reguläre bipartite Graphen)

Q: 1. Was ist die Laufzeit des LocalRepair-Algorithmus für das Convex-Hull Problem? Analysiere Anhand des Pseudocodes!
2. Inwiefern gibt der LocalRepair-Algorithmus eine untere Schranke für das Sortieren? Vervollständige folgende Aussage: "Kann man ConvexHull in _____ lösen, so kann man in _____ Zeit sortieren"
A: - Analyse:
1. Sortieren in \(O(n \log n)\)
2. \(2(n-1)-h\) mal Verbessern (Startfolge hat \(2n-2\) Ecken da Punkt \(1\) und \(n\) doppelt gezählt, am Ende \(h\)) \(\Rightarrow O(n)\)
3. \(2n\) mal nicht verbessern (while condition false, insgesamt 2 mal pro Punkt, ein mal unten, ein mal oben) \(\Rightarrow O(n)\)
\(\Rightarrow\) wenn schon sortiert, nur \(O(n)\)
- Reduktion des Sortierens auf das Convex-Hull Problem gibt lower bound für Laufzeit:
\((x_1, \dots, x_n) \mapsto ((x_1,x_1^2, \dots, (x_n,x_n^2))\)
in \(O(n)\) erhält man aus Eckenfolge der Konvexen Hülle dieser Punkte die sortierte Folge der Punkte
\(\Rightarrow\) Kann man ConvexHull in \(t(n)\) lösen, so kann man in \(t(n)+O(n)\) Zeit sortieren.
-------------------------------
- Extra Fakten:
Liefert auch Triangulierung
--------
Lösung für das Convex-Hull Problem

Q: Gegeben drei Punkte \(p,q,r \in \mathbb{R}^2\):
- Wie können wir feststellen, ob \(p\) links von der Gerade \(qr\) liegt? Gib eine Formel an!
Hint: Determinante
A: - Bestimmung von p links von qr:
erste Zeile von zweiter und dritter Abziehen, dann nach dritter Spalte entwickeln

Q: Wie können wir das Bildsegmentierungs-Problem von einem Maximierungs- in ein Minimierungsproblem umwandeln?
- Schreibe folgenden Term um, damit Minimum statt Maximum gesucht wird:
\(\max(q(A,B)) =\max(\sum_{p \in A} \alpha_p + \sum_{p\in B} \beta_p - \sum_{e \in E, |e \cap A| = 1} \gamma_e) \)
Input:
\(G=(P,E)\) mit \(\chi: P\to\) Farben
- \(\alpha: P \to \mathbb{R}_0^+\)      \(\alpha_p\) grösser \(\implies\) eher im Vordergrund
- \(\beta: P \to \mathbb{R}_0^+\)      \(\beta_p\) grösser \(\implies\) eher im Hintergrund
- \(\gamma: E\to \mathbb{R}_0^+\)      \(\gamma_e\) grösser \(\implies\) eher im gleichen Teil
A: \(\max(q(A,B)) =\max(\sum_{p \in A} \alpha_p + \sum_{p\in B} \beta_p - \sum_{e \in E, |e \cap A| = 1} \gamma_e) =\max(\sum_{p \in P} (\alpha_p + \beta_p) -\sum_{p \in A} \beta_p - \sum_{p\in B} \alpha_p- \sum_{e \in E, |e \cap A| = 1} \gamma_e)\)
\(=\sum_{p \in P} (\alpha_p + \beta_p) - \min(\sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e)\)
--------------------------
Somit minimieren wir \(q'(A,B) = \sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e\) indem wir in folgendem Netzwerk den minimalen (S,T) Schnitt (= Partition von A und B für min. \(q'\)) finden:
- \(N = (P \cup \{s, t\}, E', c, s, t)\)
- \(s, t\) neu
- \(e = (s,p)\) für alle \(p \in P\) mit \(c(e) = \alpha_p\)
- \(e = (p,t)\) für alle \(p \in P\) mit \(c(e) = \beta_p\)
- \(e= (p_1,p_2)\) und \(e = (p_2,p_1)\) für alle \(p_1, p_2 (p_1\neq p_2) \in P\) mit \(c(e) = \gamma_e\)
Für den minimalen s-t-Schnitt gilt:
\(cap(S,T) = \sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e = q'(A,B)\)
- Somit berechnen wir den maximalen Fluss in \(N\), der uns den minimalen s-t-Schnitt liefert, der der Partition \((A,B)\) die \(q'\) minimiert entspricht.

Q: Vervollständige die Lücken (Bildsegmentierung):
Input:
\(G=(P,E)\) mit \(\chi: P\to\) Farben
- \(\alpha: P \to \mathbb{R}_0^+\)      \(\alpha_p\) ______ \(\implies\) ______
- \(\beta: P \to \mathbb{R}_0^+\)      \(\beta_p\) ______ \(\implies\) ______
- \(\gamma: E\to \mathbb{R}_0^+\)      \(\gamma_e\) ______ \(\implies\) ______
Qualitätsfunktion, die wir maximieren wollen: \(q(A,B) =\sum_{p \in A} \alpha_p + \sum_{p\in B} \beta_p - \sum_{e \in E, |e \cap A| = 1} \gamma_e\)
Somit minimieren wir \(q'(A,B) = \)_____________ indem wir in folgendem Netzwerk den _____ (S,T) Schnitt (= Partition von A und B für min. \(q'\)) finden:
- \(N = (P \cup \{s, t\}, E', c, s, t)\)
- \(s, t\) neu
- \(e = (s,p)\) für alle \(p \in P\) mit \(c(e) = \)____
- \(e = (p,t)\) für alle \(p \in P\) mit \(c(e) = \)____
- \(e= (p_1,p_2)\) und \(e = (p_2,p_1)\) für alle \(e=\{p_1, p_2\} \in E\) mit \(c(e) = \)____
A: Input:
\(G=(P,E)\) mit \(\chi: P\to\) Farben
- \(\alpha: P \to \mathbb{R}_0^+\)      \(\alpha_p\) grösser \(\implies\) eher im Vordergrund
- \(\beta: P \to \mathbb{R}_0^+\)      \(\beta_p\) grösser \(\implies\) eher im Hintergrund
- \(\gamma: E\to \mathbb{R}_0^+\)      \(\gamma_e\) grösser \(\implies\) eher im gleichen Teil
Qualitätsfunktion, die wir maximieren wollen:
\(\max(q(A,B)) =\max(\sum_{p \in A} \alpha_p + \sum_{p\in B} \beta_p - \sum_{e \in E, |e \cap A| = 1} \gamma_e) =\max(\sum_{p \in P} (\alpha_p + \beta_p) -\sum_{p \in A} \beta_p - \sum_{p\in B} \alpha_p- \sum_{e \in E, |e \cap A| = 1} \gamma_e)\)
\(=\sum_{p \in P} (\alpha_p + \beta_p) - \min(\sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e)\)
Somit minimieren wir \(q'(A,B) = \sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e\) indem wir in folgendem Netzwerk den minimalen (S,T) Schnitt (= Partition von A und B für min. \(q'\)) finden:
- \(N = (P \cup \{s, t\}, E', c, s, t)\)
- \(s, t\) neu
- \(e = (s,p)\) für alle \(p \in P\) mit \(c(e) = \alpha_p\)
- \(e = (p,t)\) für alle \(p \in P\) mit \(c(e) = \beta_p\)
- \(e= (p_1,p_2)\) und \(e = (p_2,p_1)\) für alle \(p_1, p_2 (p_1\neq p_2) \in P\) mit \(c(e) = \gamma_e\)
Für den minimalen s-t-Schnitt gilt:
\(cap(S,T) = \sum_{p \in A} \beta_p + \sum_{p\in B} \alpha_p+ \sum_{e \in E, |e \cap A| = 1} \gamma_e = q'(A,B)\)
- Somit berechnen wir den maximalen Fluss in \(N\), der uns den minimalen s-t-Schnitt liefert, der der Partition \((A,B)\) die \(q'\) minimiert entspricht.

Q: How is deadlock detection implemented usually?
Give two examples of deadlock avoidance techniques (Hint: databases!)
A: deadlock detection:
- finding cycles in dependency graph
deadlock avoidance:
- two phase locking with retry (release lock on fail), used by databases. deadlocks can occur but are resolved easily by aborting transaction
- resource ordering (cf. bank account examples, lock in some order to avoid circular dependencies)

Balls into Bins:
Wir haben \(m\) Bälle, die jeweils gleichverteilt in einen von \(n\) Körben geworfen werden (\(0 < m \leq n\)).
Berechne die Wahrscheinlichkeit, dass zwei oder mehr Bälle im gleichen Korb landen!

Q: Prove the following:
Let a lock be fair and deadlock free. Then it is also starvation free.
fair, deadlock free \(\implies\) starvation free
A: With deadlock freedom any number of threads with overlapping doorway intervals is not a problem as it's only a finite number of threads where the fairness property doesn't apply (if you keep starting more threads one set of threads which have an overlapping doorway interval will be before/after another)
If we do not have deadlock freedom, the problem is that we can't make any assumptions about threads with overlapping doorway intervals - they could wait indefinitely.

Q: Complete the Java Code with Scala-STM syntax!
A: Ref.View<...>
STM.atomic(new Runnable() { public void run() { }});
int result = STM.atomic(new Callable() { public Integer call() { }});
A transaction is automatically retried when it runs into some read or write conflict, until the operation completes, an exception (throwable) is thrown or when there are too many retries. When a read or writeconflict is encountered, the transaction uses a bounded exponential backoff to prevent cause more contention and give other transactions some room to complete. (from documentation)

Q: Vervollständige den Pseudocode (Finden von Hamiltonkreisen)
- 1. Existenz von 1-x-Pfaden
DP Definition: \(P_{S,x} = 1 \iff \dots\)
Output: Wahrheitswert von ...
Code:
A: - 1. Existenz von 1-x-Pfaden
DP Definition: \(P_{S,x} = 1 \iff \)es gibt einen 1-x Pfad, der genau die Knoten aus S enthält
Output: Wahrheitswert von
\(\exists x \in N(1)\)mit \(P_{[n],x} = 1\)
Code:

Q: Vervollständige den Pseudocode (Finden von Hamiltonkreisen)
- 2. Wege mit Start- und Endknoten s der Länge n zählen
DP Definition: \(W_{S} = \dots\)
Output: \(\frac{1}{2}(|W_{\emptyset}| - \dots )\)
Code:
A: - 2. Wege mit Start- und Endknoten s der Länge n zählen
DP Definition: \(W_{S} = \) Wege der Länge n mit Start- und Endknoten s, die keine Knoten in S besuchen
Output: \(\frac{1}{2}(|W_{\emptyset}| - | \bigcup_{i=1}^{n} W_{\{i\}} | )\)
\(=\frac{1}{2}\left( |W_\emptyset| + \sum_{S \subseteq V,\, S \neq \emptyset} (-1)^{|S|}W_S \right)\)
Code:

Q: Seien \(X, Y, Z\) unabhängige Zufallsvariablen
Gilt folgendes? Wenn nein, gib ein Gegenbeispiel an!
\(E[\max(X,Y,Z)] = \max(E[X],E[Y],E[Z])\)
A: da \(X,Y,Z\) unabhängig sind, betrachten wir die Fälle, in denen das maximum 0 ist (also \(X=0,Y=0,Z=0\)) davon ist die wahrscheinlichkeit 1/8, also ist \(E[\max(X,Y,Z)] = 7/8\)
\(\max(E[X],E[Y],E[Z]) = 1/2\) jedoch

Q: Sei \(X\) die Augenzahl bei einem Wurf mit einem \(D6\) Würfel.
Berechne: \(E[X^2]\)
Zusatzfrage: Wie berechnen wir allgemein \(E[X^2]\)?
A: - \(W_x\) und \(f_x(x)\) sind bekannt
Quadriere jedes \(x \in W_x\) und verwende gegebene Wahrscheinlichkeiten für E[X]
Der Wahrscheinlichkeit Raum {1,4,9,16,25,36} und dann alles p=1/6
- \(f_x(x)\) nicht ganz klar
zB: Graph, in dem random mit W'keit \(p\) Kanten rot gefärbt werden und wir zählen deren Anzahl
Wir können schreiben:
\(X= \sum_{i=1}^m X_i\) where \(X_i = 1 \iff\) Kante \(i\) ist rot gefärbt worden mit \(Pr[X_i=1]=E[X_i] = p\)
\(\Rightarrow X^2 = (\sum_{i=1}^m X_i)\cdot (\sum_{i=1}^m X_i)= \sum_{i=1}^m \sum_{j=1}^m X_i \cdot X_j\), wobei wenn \(i = j: E[X^2] = E[X]\) (da \(X_i * X_j = 1 \iff X_i = X_j = 1\) und wegen \(i=j\) gilt \(X_i = X_j\))
man muss abhängigkeiten mit einbeziehen, wenn die Zufallsvariable komplizierter ist und zB. irgendwas zählt (zB. in einem Graphen, in dem irgendwas zufällig gilt, wie bei dem triangles exercise)
hier wird gewürfelt und der quadrierte wert ist X^2
bei einem graphen in dem random mit w'keit p zB kanten rot gefärbt werden und wir zählen die anzahl, müsste man X^2 aufteilen (mit indikatorvariablen) und in m^2-m fällen ist E(X^2) = p^2 und in m fällen (wenn wir bei X^2 als summe i = j haben) E(X^2) = E(X) = p beim einen X werden m Kanten unabhängig gefärbt, beim anderen nur ein mal ein würfel geworfen

Q: Beantworte folgende Fragen:
- 1.
- 2.
Wie können wir diese Eigenschaften im Allgemeinen überprüfen?
A: - 1.
- 2.
- Threads in CS at the same time \(\iff (a_3,b_3)\) reachable
- Deadlock exists \(\iff\) there is reachable state which has only incoming edges
- Livelock exists \(\iff\) there exists cycle in state diagram without (!) CS (i.e. there exists cycle in which neither of the threads are in the CS)
\(\Rightarrow\)not even just one state in CS

Q: What's wrong about this consensus implementation?
A: 1. not wait free! uses locks (synchronized)
Note: consensus number of volatile registers is 1, hence cannot implement 2 thread consensus!

Q: - Wie ist das Min-Cut Problem definiert?
- Wie können wir es durch Berechnung des maximalen Flusses in einem Netzwerk lösen, mit welcher Laufzeit?
A: Das Min-Cut Problem ist wie folgt:
Input: ungewichteter, ungerichteter Multigraph (mehrere Kanten zwischen Knoten möglich) ohne Schleifen
Output: \(\mu(G) = \min_{C \subseteq E,\,(V,E\setminus C) \text{ unzusammenhängend}} |C|\)  (Grösse des kleinstmöglichen Kantenschnitts, minimale Menge von Kanten um G unzusammenhängend zu machen)
Lösungsansatz mit Flüssen:
- Statt Multikanten Gewichte, statt ungerichteten Kanten je zwei gerichtete
Wir fixieren ein \(s\) und suchen den minimalen s-t Schnitt unter allen \(t \in V \setminus \{s\}\):
\((n-1)O(mn\log n) = O(mn^2\log n) = O(n^4\log n)\) mit Dynamic Trees

Q: Vervollständige den Pseudocode (Min-Cut-Problem) und beantworte die Fragen unten:
- Was ist die Laufzeit von einer Iteration von \(Cut(G)\)?
- Kontrahiere \(e\) in folgendem Graphen:
A: - Laufzeit: \(O(n^2)\), \(n\) Iterationen je \(O(n)\)für Kontraktion und e i.i.d. wählen
________________
Min-Cut:
Input: ungewichteter, ungerichteter Multigraph (mehrere Kanten zwischen Knoten möglich) ohne Schleifen
Output: \(\mu(G) = \min_{C \subseteq E,\,(V,E\setminus C) \text{ unzusammenhängend}} |C|\)  (Grösse des kleinstmöglichen Kantenschnitts)
- \(\mu(G/e) \geq \mu(G)\)
- es gibt minimalen Kantenschnitt \(C\), sodass \(e \notin C \implies \mu(G/e)=\mu(G)\)

Q: Min-Cut:
- Analyse von einer Kantenkontraktion:
Sei \(C\) ein minimaler Schnitt mit \(|C| = k\):
\(\Pr[\mu(G) = \mu(G/e)] \geq\) _______ \(= 1-\frac{k}{|E(G)|} \geq\) ______ \(= 1 - \frac{2}{n}\)
- Analyse des gesamten Algorithmus \(Cut(G)\):
\(\hat{p}(G) = \Pr[\text{Cut(G) gibt $\mu(G)$ aus}]\) (also keine essenzielle Kante wird kontrahiert)
\(\hat{p}(n) = \inf_{G=(V,E), |G| = n} \hat{p}(G)\) (lower bound über alle Graphen)
Für alle \(n\geq 3:\hat{p}(n) \geq \)______ \(\hat{p}(n-1)\)
\(\Rightarrow \hat{p}(n) \geq \frac{n-2}{n} \)________ \(\hat{p}(2) = \frac{2}{n(n-1)} = \frac{1}{n \choose 2}\)
Somit ist der Erwartungswert der Wiederholungen, bis \(\mu(G)\) ausgegeben wird, höchstens ____.
A: - Analyse von einer Kantenkontraktion:
Sei \(C\) ein minimaler Schnitt mit \(|C| = k\):
\(\Pr[\mu(G) = \mu(G/e)] \geq \Pr[e \notin C] = 1-\frac{k}{|E(G)|}\geq1-\frac{k}{\frac{1}{2}nk} = 1 - \frac{2}{n}\)
Begründung Schritt 3: Für \(v \in V\) ist \(deg(v) \geq k\) (sonst ist \(|C| < k\)) + Handschlaglemma: \( |E(G)| = \frac{1}{2} \sum_{v \in V} deg(v) \geq\frac{nk}{2}\)
- Analyse des gesamten Algorithmus \(Cut(G)\):
\(\hat{p}(G) = \Pr[\text{Cut(G) gibt $\mu(G)$ aus}]\) (also keine essenzielle Kante wird kontrahiert)
\(\hat{p}(n) = \inf_{G=(V,E), |G| = n} \hat{p}(G)\) (lower bound über alle Graphen)
Für alle \(n\geq 3:\hat{p}(n) \geq (1-\frac{2}{n})\hat{p}(n-1)\) (Proof at the end)
\(\Rightarrow \hat{p}(n) \geq \frac{n-2}{n} \frac{n-3}{n-1} \frac{n-4}{n-2} \dots \frac{2}{4} \frac{1}{3} \hat{p}(2) = \frac{2}{n(n-1)} = \frac{1}{n \choose 2}\)
Somit ist der Erwartungswert der Wiederholungen, bis \(\mu(G)\) ausgegeben wird, höchstens \(n \choose 2\).

Q: Min-Cut:
Ein Aufruf: \( O(n^2)\)
- Monte Carlo Wiederholungen:
Wir wiederholen \(Cut(G)\) \(\lambda{ n \choose k}\) mal und geben den niedrigsten gesehenen Wert aus.
Laufzeit: \(\lambda{n \choose 2}O(n^2) = \)______
Fehlerwahrscheinlichkeit:
\(\hat{p}(G) = \Pr[\text{Cut(G) gibt $\mu(G)$ aus}]\) (also keine essenzielle Kante wird kontrahiert)
\(\hat{p}(n) = \inf_{G=(V,E), |G| = n} \hat{p}(G)\) (lower bound über alle Graphen)
\(\hat{p}(n) = \frac{1}{n \choose 2}\)
\(\Pr[\text{Output}\neq \mu(G)] = \Pr[\text{Cut(G) gibt nie $\mu(G)$ aus}]= \)_________ \(\leq \)_________\(\leq e^{-\lambda}\)
Nicht besonders berauschend, es gibt auch deterministischen Algorithmus mit ähnlicher Laufzeit...
Aber: Bootstrapping!
Idee: letzte Kontraktionen besonders "teuer" - wir brechen davor ab und wenden für diese obigen Algorithmus mit \(\lambda = 1\) an.
Nach erster Iteration Laufzeit _________, im Grenzwert ___________
A: - Monte Carlo Wiederholungen:
Wir wiederholen \(Cut(G)\) \(\lambda{ n \choose k}\) mal mit \(k = 2\) und geben den niedrigsten gesehenen Wert aus.
Laufzeit: \(\lambda{n \choose 2}O(n^2) = O(\lambda n^4)\)
Fehlerwahrscheinlichkeit:
\(\Pr[\text{Output}\neq \mu(G)] = \Pr[\text{Cut(G) gibt nie $\mu(G)$ aus}]= (1-\hat{p}(n))^{\lambda{n \choose 2}}\leq (1-\frac{1}{n \choose 2})^{\lambda{n \choose 2}} \leq e^{-\lambda}\)
Nicht besonders berauschend, es gibt auch deterministischen Algorithmus mit ähnlicher Laufzeit...
Aber: Bootstrapping!
Idee: letzte Kontraktionen besonders "teuer" - wir brechen davor ab und wenden für diese obigen Algorithmus mit \(\lambda = 1\) an.
Nach erster Iteration Laufzeit \(O(\lambda n^3)\), im Grenzwert \(O(n^2\text{polylog}( n))\)

Q: Seien \(A,B,C\) unabhängige Ereignisse
Welche der folgenden sind dann unabhängig?
\(A \cap B\) und \(C\)
\(A \cup B\) und \(C\)
\(A \cup B\) und \(B \cap C\)
Beweise schnell/Argumentiere mit Skript!
A: Sei Omega gegeben durch die Ergebnisse von drei unabhängigen Münzwürfen einer fairen Münze, wobei A das Ereignis ist, dass die erste Münze Kopf zeigt, B, dass die zweite Kopf zeigt, C, dass die dritte Kopf zeigt. Pr[A u B] * Pr[B n C] = (Pr[A] + Pr[B] - Pr[A n B]) Pr[B]Pr[C] = (1/2 + 1/2-1/4) * 1/4 = 3/16 Pr[(A u B) n (B n C)] = Pr[(A n B n C) u (B n B n C)] = Pr[A n B n C] + Pr[B n C] - Pr[A n B n C] = Pr[B n C] = 1/4

Q: Wann sind zwei Indikatorvariablen \(X, Y\) unabhängig?
A: Bei Indikatorvariablen \(X, Y\) (nicht bei 3 oder mehr!):
\(X, Y\) unabhängig \(\iff f_{x,y}(1,1) = f_x(1) * f_y(1) \iff \Pr[X = 1, Y =1]=\Pr[X=1]\cdot\Pr[Y=1]\)

Q: Fill in the gaps - barrier implemented in MPI:
A: 1. root receives one message from all threads
2. root sends one message to all threads, allowing them to return from recv and continue execution
"synchronization point" is when root received messages from all threads

We divide pipelined throughput by sequential/non-pipelined throughput and get:
a), b), c): \(\frac{\frac{1}{50}}{\frac{1}{100}} = 2\)
d):  \(\frac{\frac{1}{10}}{\frac{1}{30}} = 3\)
Also possible to do the following:
\(S_p = \frac{T_{seq}}{T_{par}}\)

Q: How do
- Requests.Waitall(Requests[] r) and
- Request.Wait()
work in MPI?
A: - Wait Request.Wait()
- Waitall Requests.Waitall(Requests[] r)
Only returns when all requests given as the argument/of the object have finished (it does not return until it is safe to modify the send/recv buffer). Used primarily with nonblocking "I" operations.
In case of Recv when matching send was posted and message was sent (receive buffer can be reused)
In case of Issend when matching Recv was posted and message has been transmitted to the receiver
In case of Isend if either the message is saved in a buffer or it has been transmitted to the receiver

Q: Give an example of a history that is not sequentially consistent!
A: T1: write A = 1
T2: write B = 1
T1: read (B == 0)
T2: read (A == 0)
---------------------
T1: B = 42
T1: A = 1
T2: read A = 1
T2: read B = 0