FS20 (Moodle Mock)

MC 1

Sind $u, v$ Artikulationsknoten und benachbart, so ist die Kante ${u, v}$ eine Brücke.

Counterexample

→ Destroying vertices is much more destructive than removing edges.
Deleting only $e$ deletes only one deg off both.

Don’t be an idiot → read properly. That is the definition of Hall’s.

Again, choose the right option. Coupon collector for 3 is EV = 11/2 = 5.5.

3.2.1 Kleinster umschließender Kreis the naive version without doubling has a runtime of $O (n^{4})$ .

Proof:

Let $S$ be the support-set of the smallest enclosing circle.
We have success exactly when $S \subseteq Q$ for $∣ Q ∣ = k$ .
$Pr [success] = \frac{( k - 3 n - 3 )}{( k n )} \approx (\frac{k}{n})^{3}$ .
- all ways to choose a subset of size k containing $S$ , divided by all ways to choose a subset of size k.
Thus it still takes $O (n^{4})$ , no matter what fixed size $k$ we choose.

$Var [X - Y] = Var [X] - Var [Y]$ is FALSE! It’s $Var [X - Y] = Var [X] + Var [Y]$ as $Var [α X] = α^{2} Var [X]$ !

Variance is also not multiplicative!

Rules:

affine transformation $Var [a X + b] = a^{2} Var [X]$ (the b is just bias, not relevant for variation)
$Var [- X] = Var [X]$ .
$Var[X+Y]=Var[X]+Var[Y]+2\Cov[X,Y]$
- note $Var [X - Y] = Var [X] + Var [Y] - 2 \Cov [X, Y]$ .
linear combination also holds with this covariance term
- $Var [\sum_{i = 1}^{n} a_{i} X_{i}] = \sum_{i} a^{2} Var [X_{i}] + 2 \sum_{i < j} a_{i} a_{j} \Cov [X_{i}, X_{j}]$ .
- Bienaymé: if they’re pairwise independent
  - the sum of covariances disappears.
$Var [X] \geq 0$
For $X, Y$ independent, $Var [X \cdot Y] = E [X^{2}] E [Y^{2}] - E [X]^{2} E [Y]^{2}$ .

Covariance extra: