FS23 Mock

1

2)

Man kann in Zeit $O(V+E)$ entscheiden, ob ein Graph $2$-Zusammenhängend ist.

TRUE → low-dfs, wenn kein Artikulationsknoten, dann true.

9)

Für $P$ eine endliche Punktmenge gilt $conv(P)\subseteq C(P)$!
Der Kreis ist ja “konvexer” als die Konvexe Menge.
Wenn es nicht stimmen würde, wäre ein Zertifikatspunkt außerhalt von $conv(P)$ ⇒ not convex hull.

10)

Allgemeine Lage

Keine 3 Punkte sind aligned

Der kleinste umschließende Kreis von $\{p_1,p_2,p_3\}$ ist der eindeutige Kreis der alle Punkte auf dem Rand hat → FALSE (einer kann so in der Mitte sein)

2

12)

Eulertour = Einmal die Runde. Eulerpfad ist nicht komplett die Runde

3

13)

$10$ faire Münzen. Jede Münze wird mit $p$ von einer Elster gestohlen (indep.).
Was ist die Prob, das max mindestens eine Münze die Zahl zeigt behält.

NICHT WALD!, weil es ja keine Expectation ist.

$\mathrm{Pr}[\text{mind. eine Zahl}]=1-\mathrm{Pr}[\text{keine Zahl mehr}]$ und dann ist der Rest nur computation.

14)

Ich habe dumm gerechnet einfach!!

4

19)

Remember, $k$-(Kanten/Knoten)-Zusammenhängend ⇒ $k-1,k-2$, etc…-(Kanten/Knoten)-Zusammenhängend.
→ wenn du mindestens k entfernen musst, musst du ja auch mindestens $k-1$ entfernen.

Planar = aufgezeichnet ⇒ $\chi (G)\le 4$

20)

$A,B$ independent and non-zero ⇒ $A\cap B\ne \varnothing$!

• independent and disjoint are close to opposites
• we want to preserve ratios after conditioning = indendence
  • see graphical representation.

Louis Trick: 3 Münzwürfe (wo X = don’t care)

• A := 1XX
• B := X1X
• C := XX1

1. $\mathrm{Pr}[A]+\mathrm{Pr}[B]\le \mathrm{Pr}[A\cup B]$
   1. basically inverted union bound
   2. this implies $\mathrm{Pr}[A\cap B]\le 0$.
   3. but since intersection always $>0$, false
2. $\mathrm{Pr}[A\mid B\cap C]=\mathrm{Pr}[A\mid B\cup C]$
   1. since $A$ stochastically indep from B, C, we don’t care about any of their union/intersections
   2. This is just lemma $\mathrm{Pr}[A\mid B]=\mathrm{Pr}[A]$ applied
3. $\mathrm{Pr}[A\cap B]=\mathrm{Pr}[A]\cdot \mathrm{Pr}[B]$
   1. definition
4. $\mathrm{Pr}[(A\cup B)\cap C]=(\mathrm{Pr}[A]+\mathrm{Pr}[B])\cdot \mathrm{Pr}[C]$.
   1. Since $C$ indep from $A,B$ we can decompose
   2. but then $A\cup B\ne A+B$, as their intersection is always non-zero
   3. thus false

21)

Negativ Binomial verteilt = Binomialverteilung für Geometrische Independents.

$X\sim -\text{Bin}(n,p)$ then $\mathbb{E}[X]=n/p$.

Thus d) is right → it’s exactly that.

5

A. a)

Prove $|A|=|B|$ in regular bipartite grpah

Use the degree counting trick:

• jeder Knoten hat gleichen Grad.
• Da graph bipartit muss die Summe der Grade in A und B übereinstimmen (jeder Knoten in A nur zu B verbunden und andersherum)