FS19

MC 1

4)

Sei $G$ ein Graph und $k\ge 1$ eine ganze Zahl. Wenn alle bis auf einen Knoten in $G$ Grad höchstens $k$ haben, dann ist $G$ $(k+1)$-färbbar.

Proof: Sei $v\in V$ der Knoten mit Grad $>k$. Sei o.B.d.A $G$ zusammenhängend mit Wurzel eines BFS baums.

• Färbe alle $u\ne v$ mit nur $k$ Farben in der Reihenfolge absteigender Distanz zu $v$
  • da jeder Knoten noch eine Elternknoten hat gilt $\mathrm{deg}(u)\le k-1$, thus mit $k$ Farben färbbar
• Dann lässt sich $G-v$ mit $k$ Farben färben.
• Die $k+1$-te Farbe ist dann nur für $v$ da!

MC 2

12)

$X$ s.t. $\mathrm{Pr}[X=2]=\mathrm{Pr}[X=10]=1/2$. What’s $\mathrm{Var}[X]$?
We have $\mathbb{E}[X]=2\cdot \frac{1}{2}+10{\cdot }_1\frac{1}{2}=6$. Then $\mathrm{Var}[X]=\frac{1}{2}(2-6{)}^2+\frac{1}{2}(10-6{)}^2=4^2+4^2=\frac{1}{2}32=16$ .

MC 3

19)

Nehme an $c(e)=1$ für alle $e\in A$. Dann ist $\text{maxflow}(N)=k$ genau dann wenn es in $N$ genau $k$ intern knotendisjunkte Pfade von $s$ nach $t$ gibt.

FALSE →
wir haben 1 knotendisjunkten Pfad, jedoch ist maxflow = 2.

Code Expert

1. Boxes

Keep in mind that $\mathrm{Pr}[X\ge 1]=1-\mathrm{Pr}[X=0]$, for $X=$ number of red balls picked out. This eliminates the need for DP.

My approach with summing over $\mathrm{Pr}[X=i]$ $1\le 1\le n$ also works, but I fucked up the probabilities just slightly.

2. Life Forces

pretty easy flow matching once again.