Jonas Mocks

Mock 1

Part 1 (MC)

Q5: $\sigma [aX]=\mid a\mid \sigma [X]$ and not simply $a\sigma [X]$!
Q6: Gedächtnislosigkeit: $\mathrm{Pr}[X>s+t\mid X>s]=\mathrm{Pr}[X>t]$ not $X>s$!
Q9: Karger is a MC algorithm always terminates but may return non-minimum cut.

Part 3 (Single Choice)

Q15: A server crashes on each day with $p\in (0,1)$. Let $X$ be the first day of the crash. Given that the server has survived 5 days, return $\mathbb{E}[X|X>5]$
Answer: Memorylessness → $5+\mathbb{E}[X]=5+\frac{1}{p}$ und nicht nur $1/p$.

Q16: Randomised incremental algorithm for enclosing circle. What’s the expected number of times we have to recompute upon inserting a point?
Answer: we only have to recompute when $p_i$ is part of the 3 points that define a circle: $\mathbb{E}[X]={\sum }_{i=1}^{n}3/i=3\cdot O(\log n)$.

Q17: Coupon collector for $n=3$.
Answer: $\mathbb{E}[X]=\mathbb{E}[X_1]+\mathbb{E}[X_2]+\mathbb{E}[X_3]$ with $X_i\sim \text{Geo}((3-i+1)/3)$ so $\mathbb{E}[X]=3/3+\frac{1}{\frac{2}{3}}+\frac{1}{\frac{1}{3}}=1+1.5+3=5.5$.
My mistake was not summing 1/p but p directly.

Part 4 (MC)

Q18: b) MC error reduction.
For a one sided error (i.e. it fails with p = $ϵ$) $\mathrm{Pr}[\text{all fail}]=(1-ϵ{)}^t\le e^{-ϵt}$ over $t$ runs. So setting $t=\lceil e^{-1}\ln {\delta }^{-1}\rceil$ gives $e^{-ϵt}=e^{-ϵ/ϵ\ln {\delta }^{-1}}=\delta$.
Then $\mathrm{Pr}[\text{one succeeds}]=1-\mathrm{Pr}[\text{all fail}]\ge 1-\delta$.
The $N=\lceil 4{ϵ}^{-2}\ln {\delta }^{-1}\rceil$ bound is only needed for a one-sided error case with $1/2+ϵ$.

Q19: independent poisson variables sum together (ex: via convolution formula).

Q21: the colour coding algorithm from the lecture is Monte Carlo (result may still be wrong).

Part 5 (Proofs)

W1, probability We have coins and peaks (T, H, T) and they are not independent.
$X=\sum X_i$ but we cannot use Chernoff to bound.
So instead, we ignore 2/3 of the coins and only care about blocks of 3 coins that are non-overlapping and thus independent. Let $Y_i$ be the indicator of block $i$ being a peak.
Then $X\le Y$ and $\mathrm{Pr}[X\le n/48]\le \mathrm{Pr}[Y\le n/48]$. As $Y\sim \text{Bin}(n/3,1/8)$ we can use Chernoff and get the result.

Technique: lower bound the sum of dependent $X_i$ and then apply Chernoff!

W2
a) Greedy path. As deg(v) >= d for all, there are always $d-(|P|-1)$ edges to a node not on the path left. We stop when $d-(|P|-1)\le 0⟺d+1\le |P|$ and thus the path has $d$ edges.

Solution: Let $P=v_0\dots v_k$ be a longest path in $G$. Every neighbour of $v_0$ must lie on $P$ → otherwise you could extend $P$ contradicting maximality. Since $v_0$ has $\ge d$ neighbours, all among $v_1,\dots ,v_k$, we get $k\ge d$.

b) from a) we know there is a longest path $P$ of length $\ge 2$. We choose a $v_k$ neighbour of $v_0$ (we know all of them are on the path from a.) with $k$ maximal.
We get $C=v_0,v_1,\dots ,v_k,v_0$. Since $k\ge d\ge 2$ the closed walk $C$ has $\ge 3$ vertices and since they are pairwise distinct (they lay on a path), $C$ is a cycle with $|C|=k+1\ge d+1$.

c) Greedy grow a path, keeping list of “visited”. When no more neighbour exists, the current path is non-extendable. By a) and b) the furthest neighbour of $v_0$ along the path yields a cycle of length $\ge d+1$.
Correctness: follows from a) and b) applied to our path.
Runtime: every vertex enters at most once, every adjacency list only scanned constant amount of time. $O(|V|+|E|)$.

Part 6 (CE)

2 Probability of success $\text{score}\ge T$, with optimal “playing/choices”. So we go backwards.

• Backward DP → when optimal choice, it depends on all future possible states.
• dp[i][j] = Math.max(dp[i+1][j+1], dp[i+1][j+2]*p[i] + dp[i+1][j]*(1 - p[i])).

Mock 2

Part 1 (MC)

Q3 The complete Graph for $n\ge 3$ contains exactly $(n-1)!$ distinct Hamiltonian cycles.
False! it’s $(n-1)!/2$ → cycles counted twice, once for each direction!

Q6 If $A,B$ independent, then $A,\bar{B}$ also independent. True
Proof is easy:

• $\mathrm{Pr}[A\cap \bar{B}]=\mathrm{Pr}[A]-\mathrm{Pr}[A\cap B]$ ($A\cap \bar{B}=A\setminus B$)
• $\mathrm{Pr}[A]-\mathrm{Pr}[A\cap B]=\mathrm{Pr}[A]-\mathrm{Pr}[A]\mathrm{Pr}[B]$ (by indep.)
• $\mathrm{Pr}[A](1-\mathrm{Pr}[B])=\mathrm{Pr}[A]\mathrm{Pr}[\bar{B}]$.

Part 2 Algos

Give a minimum $s-t$ cut and prove that your flow is indeed maximal:
Solution:

• Give $S=\{\}$, $T=\{\}$ and count the capacity of the edges crossing that cut (only in forward direction)
• Then say: by MaxFlow MinCut theorem, $\text{val}(f)\le \text{cap}(S,T)$ and as my flow and cut are equal, $f$ is maximal and $(S,T)$ is a minimal cut!

Include Proof

Make sure to state the proof here!

Part 3 (Numeric)

Q1 3 cards from 52 card deck, prob = all heart
$\frac{13\cdot 12\cdot 11}{52\cdot 51\cdot 50}$. Calculate cleanly!

Q2 $X\sim \text{Geo}(1/4)$. Compute $\mathrm{Pr}[X\le 2]$!
Two ways:

• $1-\mathrm{Pr}[X>2]=1-{\left(1-\frac{1}{4}\right)}^2=1-\frac{9}{16}=\frac{7}{16}$ (i.e. probability we rolls above at least twice)
• $\mathrm{Pr}[X\le 2]=\mathrm{Pr}[X=0]+\mathrm{Pr}[X=1]+\mathrm{Pr}[X=2]$
  • $\mathrm{Pr}[X=0]=0$
  • $\mathrm{Pr}[X=1]=1/4$
  • $\mathrm{Pr}[X=2]=(1-1/4{)}^1\cdot 1/4$

Geometric probs

$\mathrm{Pr}[X=i]=(1-p{)}^{i-1}\cdot p$ for a geometric distribution!!!!

Don’t be an idiot.

Q16: Jarvis Hull runtime $=O(nh)$. FindNext takes $O(n)$ scan all points to find the “right most”. Then repeat $h$ times, once for each corner.

Q17: $X=\min$ of two dice roll.
I am an idiot and forgot the squaring I think.
Right way to do it is $\mathbb{E}[X]={\sum }_{i=1}^6\mathrm{Pr}[X\ge i]$. with $\mathrm{Pr}[X\ge i]={\left(\frac{7-i}{6}\right)}^2$.

Part 4 (MC)

Q1:

1. Every tree contains at most one perfect matching
   1. true → proven by induction
   2. the leaves force it
2. Every 3-regular graph contains a perfect matching.
   1. false, counterex is literally in the notes
   2. Frobenius theorem requires bipartiteness

Q2:

1. Expected number of comparisons of randomised Quicksort is $2n\ln n$.
   1. For each pair of numbers, we count comparisons
   2. probability of comparison falls of harmonically for further apart.
   3. This gives prob = $2\ln n$
   4. Repeat $n$ times.

Q3:

1. $\mathbb{E}[X^2]\ge \mathbb{E}[X{]}^2$ for every $X$. True.
   1. $X^2$ then always gives a positive internal value
   2. $(\sum X{)}^2$ can have some cancelling each other out internally

Q4:

1. Distinct number of $s-t-$cuts in a Network is exactly $2^{n-2}$. true
   1. $s\in S$ and $t\in T$ fixed.
   2. For the rest, we can either put them in $S$ or $T$ (binary choice)
   3. $2^{n-2}$ vertices free to choose!

Part 5 Proofs

W1: c) Hashing collisions for $n$ keys into $m=n$ buckets. Prove that $\mathrm{Pr}[X\ge n-1]\le \frac{2}{n-1}$.

• There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ distinct pairs of keys.
• Split into two cases: $X_i,X_j$ share zero/one keys
  • if zero: independent case $\mathrm{Pr}[X_i\cap X_j]=\mathrm{Pr}[X_i]\mathrm{Pr}[X_j]$ and thus covariance vanishes
  • if one: $\mathrm{Pr}[X_i\cap X_j]=\frac{1}{n^2}$ the probability that all three hash into the same bucket. But then covariance also vanishes.
• $\mathrm{Var}[X]={\sum }_{i=1}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\mathrm{Var}[X_i]=\left(\genfrac{}{}{0ex}{}{n}{2}\right)(p(1-p))=\left(\genfrac{}{}{0ex}{}{n}{2}\right)\left(\frac{1}{n}-\frac{1}{n^2}\right)$.
• We upper bound $\mathrm{Var}[X]\le \mathbb{E}[X]$ as $\mathbb{E}[X]=\frac{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{n}$.
  • Then $\mathrm{Pr}[X\ge n-1]=\mathrm{Pr}[X-\frac{n-1}{2}\ge \frac{n-1}{2}]$ in which we can sub in $\mathbb{E}[X]$.
  • $\mathrm{Pr}[X\ge n-1]=\mathrm{Pr}[X-\mathbb{E}[X]\ge \mathbb{E}[X]]\le \mathrm{Pr}[|X-\mathbb{E}[X]|\ge \mathbb{E}[X]]$.
  • Then Chebychev, upper bounding $\mathrm{Var}[X]$ again.
    • $\mathrm{Pr}[X\ge n-1]\le \mathrm{Var}[X]/t^2=\frac{\mathrm{Var}[X]}{\mathbb{E}[X{]}^2}\le \frac{\mathbb{E}[X]}{\mathbb{E}[X{]}^2}=\frac{1}{\mathbb{E}[X]}=\frac{2}{n-1}$

W2:

1. Prove that a $k$-regular bipartite graph has a perfect matching
   1. we prove $|A|=|B|$ by using that each edge counts one for both sides
      1. as $\sum \mathrm{deg}(a)=\sum \mathrm{deg}(b)⟹|A|k=|B|k⟹|A|=|B|$.
   2. For Hall, choose $X\subseteq A$.
      1. ${\sum }_{x\in X}\mathrm{deg}(x)\le {\sum }_{y\in N(x)}\mathrm{deg}(y)$ as the subset of $X$ incident edges $\subseteq$ $N(X)$ incident edges.
      2. $k|X|\le k|N(X)|⟹|X|\le |N(X)|$.

Mock 5

Part 1 (MC)

Mini-Proof for $X\sim \text{Geo}(p)$ and $Y\sim \text{Geo}(q)$ then $\min (X,Y)\sim \text{Geo}$ as well.
Proof: We know that for a geometrically distributed ZV $\mathrm{Pr}[X>k]={\left(1-p\right)}^k$ as we need k non-successes.

• $\mathrm{Pr}[\min (X,Y)>k]=\mathrm{Pr}[X>k]\mathrm{Pr}[Y>k]=(1-p{)}^k(1-q{)}^k$
• Thus $\mathrm{Pr}[\min (X,Y)>k]=((1-p)(1-q){)}^k$
• $\min (X,Y)\sim \text{Geo}((1-p)(1-q))$.

If $\mathbb{E}[X]$ exists (is finite), then $\mathrm{Var}[X]$ is also finite. False!
Proof For a symmetric distribution with infinite tails $\mathrm{Pr}[X=i]=e^{-|i|}$ we never reach zero, as $e^{-|i|}>0$, but as it’s symmetric $\mathbb{E}[X]=0$.
But $\mathrm{Var}[X]$ is infinite, as there’s p-mass at infinite distance.

Worst Case runtime of Quickselect is $\Theta (n^2)$. True
→ only the expected runtime is $O(n)$! For worst case pivot choices we can still get $O(n^2)$

Worst case vs. Expected

Always make sure to check whether it’s expected runtime or worst-case runtime.

Part 2 (Algos from Lectures)

Review Quickselect Exp. Runtime proof.
The gist:
“For each call of QuickSelect, the pivot has a 1/2 chance of reducing the number of elements to $3/4n$. Thus $T\le \sum \mathbb{E}[\text{"pivot in middle"}]{\left(\frac{3}{4}\right)}^{j-1}n\le 2n\sum (\frac{3}{4}{)}^{j-1}=8n$.”

Part 3 (Numeric)

Walds Identity: For $N$ and $X$ independent ZV with $Z:={\sum }_{i=1}^n{X}_i$ then $\mathbb{E}[Z]=\mathbb{E}[N]\cdot \mathbb{E}[X]$.

Wie viele runs von Karger für minCut prob >= 1 - 1/e?
Wir wissen, dass $\hat{p}(n)\ge 1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Nach $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ runs gilt:

• $Pr[\text{kein min cut gefunden}]={\left(1-\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\right)}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}\le \frac{1}{e}$
  • $(1-x)\le e^{-x}$ also gilt auch $(1-1/x{)}^n\le (1/e^{1/x}{)}^n=1/e^{n/x}$.

Part 4 (MC)

Every $2$-vertex connected graph with at least $3$ vertices is also $2$-edge connected. True!
Intuitively: removing a vertex $=$ removing at least $1$ edge (as it’s $2$-vertex connected it can’t be disjoint).
Thus if we have to remove at least 2 vertices to make the graph disjoint, we also have to remove $\ge 2$ edges.

• This is “vertex-conn(G) ⇐ edge-conn(G) ⇐ min-deg(G)”
  That would already suffice, but here is a proof without it:
  Proof: For contradiction assume such a graph exists. Let $e\in E$ with $e=\{u,v\}$ be the edge for which $G-e$ is disjoint.
• if both $u$ and $v$ have degree $1$, $G$ is $1$-vertex-connected as $|V|\ge 3$ and removing $u$ isolates $v$.
• Assume WLOG $\mathrm{deg}(u)>1$. Then in $G^{\prime }=(V\setminus \{u\},E^{\prime })$, $E^{\prime }\subseteq E-e$, also removes the edge $e$ from the graph.
• Thus $G^{\prime }$ is disjoint as there is no path from $v$ to any of $u$‘s neighbours anymore (otherwise $e$ is not a bridge)

$\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ can only hold if $X$ and $Y$ are independent. False.
For $X=\{-1,0,1\}$ uniform and $Y=X^2$ we have dependence:

• $\mathrm{Pr}[X=-1\cap Y=1]=1/3$ but $\mathrm{Pr}[X=-1]\mathrm{Pr}[Y=1]=1/3\cdot 2/3=\frac{2}{9}$.
  But $\mathbb{E}[XY]=\mathbb{E}[X^3]=\mathbb{E}[X]=0$ and $\mathbb{E}[X]=0$ and $\mathbb{E}[Y]=\mathbb{E}[X^2]=2/3$.
  Thus $\mathbb{E}[XY]=0=\mathbb{E}[X]\mathbb{E}[Y]$.

$G$ has at most $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ distinct minimum cuts. True.
(Proven in Theory-Sheet 7 ex 1.b.)
Karger finds a specific min-cut $s\in S$, $S$ set of all min-cuts with probability $1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Thus ${\sum }_{s\in S}Pr[\text{CUT}(G)=s]\ge 1/\left(\genfrac{}{}{0ex}{}{n}{2}\right)\cdot |S|$. This implies that $S\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$ as the sum of probabilities must $\le 1$.

Karger finds all of them in expectation in $O(n^2\log n)$. This holds because we have a coupon collector over the cuts, which adds a $\log n$ factor to the $O(n^2)$ to find a single one.

Part 5 (Proofs)

W1 c) Compute $\mathbb{E}[X(X-1)]$ exactly, deduce $\mathrm{Var}[X]$ and use Chebychev to show…
To compute $\mathbb{E}[X(X-1)]=\mathbb{E}[X^2]-E[X]$ notice that $\mathbb{E}[X^2]=$

• $\mathbb{E}[(X_1+\cdots +X_n)(X_1+\cdots +X_n)]={\sum }_{i=1}{\sum }_{j=1}\mathbb{E}[X_i{X}_j]$
• ${\sum }_{i=1}{\sum }_{j=1}\mathbb{E}[X_i{X}_j]={\sum }_{i\ne j}\mathbb{E}[X_i{X}_j]+{\sum }_{i=1}^n\mathbb{E}[X_i^2]$
  • we know $X_i\in \{0,1\}$ so $\mathbb{E}[X_i^2]=\mathbb{E}[X_i]$
• For $\mathbb{E}[X_i{X}_j]={\sum }_{l\in \{0,1\}}{\sum }_{k\in \{0,1\}}i\cdot j\mathrm{Pr}[X_i=l\cap X_j=k]$ which is $1$ only for $l,k=1$ thus $\mathbb{E}[X_i{X}_j]=\mathrm{Pr}[X_i{X}_j]=1/n\cdot 1/(n-1)$.
• Therefore ${\sum }_{i\ne j}\mathbb{E}[X_i{X}_j]=\frac{n(n-1)}{n(n-1)}=1$.
  Chebychev gives us $\mathrm{Pr}[X\ge 6]=\mathrm{Pr}[|X-1|\ge 5]\le \frac{\mathrm{Var}[X]}{5^2}=\frac{1}{25}$.

W2 b) Let $G$ be a graph with exactly two vertices $u,v$ of odd-degree. Show that $G$ contains a $u$-$v$-path.
Proof: Assume for contradiction that $G$ does not.

• then $u$ and $v$ lie in different connected components.
• The connected component with $u$ is itself a graph and the handshake lemma holds → sum of degrees is even.
• But it contains exactly one odd-degree vertex, while the handshake tells us that the sum must be even → contradiction.
• Thus $u$ and $v$ in the same component → u-v-path.