# 2nd Long Exam Solutions

1. **Answer: c**

a is true since given any pair of vertices $v_k$ and $v_l$ where $k \neq l$, either $k < l$ or $l < k$. This implies that $\{v_k,v_l\} \in E$ or $\{v_l,v_k\} \in E$, which mean the same thing since $\{v_k,v_l\} = \{v_l,v_k\}$. Therefore this means that for any pair of vertices, there exists an edge that connects said pair. This is the definition of any complete graph. b is also true since any complete graph is connected. This means that the answer is c.

2. **Answer: a**

shortest paths:

- $\{v_1,v_5 \},\{v_5,v_3 \}$ with a path length of 3,
- $\{v_2,v_1 \},\{v_1,v_4 \}$ with a path length of 5,
- $\{v_4,v_1 \},\{v_1,v_5 \},\{v_5,v_3 \}$ with a path length of 6,

3. **Answer: c**

I is not true since $v_1$ and $v_5$ have an odd degree. But since these two are the only vertices with odd degrees, it has an Euler path making II true. If $\{v_1,v_5\}$ is removed from the graph then all edges will have an even degree making III true.

4. **Answer: b**

$(a,b)$ is not an undirected edge so it does not guarantee the existence of $(b,a)$, which means there might be no path from $a$ to $b$, so a is not true, a cycle of three edges cannot be bipartite so c cannot be true. b is true since a complete graph can contains all possible edges.

5. **Answer: b**

b is not true, if the tree only has one vertex then the root is a leaf. a is true via the definition of ancestors and descendants. c is true since $a$ and $b$ are on the same level. d is also true since a child of $a$ and a child of $b$ have the same level.

6. **Answer: c**

a and b is not a true since d,e,b,f,c,a is not a valid depth first traversal. d is not true since abcdef is not a valid depth first traversal. Only c is true.

7. **Answer: b**

- a: $52^4 = 7311616$
- b: $62^2 + 62^3 + 62^4 = 15018508$
- c: $2^{20} = 1048576$
- d: $26^5 = 11881376$

8. **Answer: b**

- a. ${12 \choose 9} = \frac{12!}{9!3!} = 220$
- b. ${12 \choose 7} = \frac{12!}{7!5!} = 792$
- c. ${12 \choose 10} = \frac{12!}{10!2!} = 66$

9. **Answer: c**

a is true, since the coefficient can be calculated as ${2m \choose m} = \frac{(2m)!}{(2m-m)!m!} = \frac{(2m)!}{m!}$. b is also true since ${n \choose (n-r)} = \frac{n!}{(n-(n-r))!(n-r)!} = \frac{n!}{n!(n-r)!}$.

10. **Answer: b**

- a: $\frac{1}{6^3}(6) = \frac{1}{36}$
- b: $\frac{1}{20}$
- c: $b(4;20,0.4) = {20 \choose 4}0.4^{4}0.6^{16}\approx 0.0345$
- d: $\frac{1}{2^6} = \frac{1}{64}$

11. **Answer: c**

a is true since $p(\overline{R})=1-p(R) = 1$. b is also true from the definition of conditional probabilities.

12. **Answer: d**

| non-crit damage | crit damage | expected damage |
| --------------- | ----------- | ----------------------------- |
| $x$ | $2.2x$ | $0.7x + 0.3 (2.2x) = 1.36x$ |
| $x$ | $1.6x$ | $0.4x + 0.6(1.6x) = 1.36x$ |
| $x$ | $2.5x$ | $0.85x + 0.15(2.5x) =1.225x$ |
| $x$ | $1.9x$ | $0.55x + 0.45(1.9x) = 1.405x$ |

13. **Answer: d**

refer to the balls and boxes example, the posterior probability can increase, decrease or become zero depending on the evidence

14. **Answer: a**

with E as the root you get 5 leaves, with A or D you get 4 leaves.

15. **Answer: d**

a is not true, since $p(E \cap \overline{E}) = 0$, while $p(E) \neq 0$ and $p(\overline{E}) \neq 0 $. b is also not true. Assuming $E$ is independent from $E$ then, $p(E \cap E)=p(E) = p(E)p(E)$. This equality has no solutions other than $p(E) = 1$ which contradicts $E \neq S$.

16. **Answer: a**

a since the vertices of each have a degree of two. You can construct counterexamples from the other choices:

- b: a tree with one root and one child
- c. a complete graph with 4 vertices
- d. two vertices connected by one edge

17. **Answer: c**

18. **Answer: d**

You can construct counterexamples for each choice

- a: a complete graph with 4 vertices will have a degree weight of $4(3)=12=3n$
- b: a cycle of three vertices will have degree weight of $6=2n$,
- c. a complete graph with 2 vertices will have one edge.

19. **BONUS**

20. **Answer: d**

- $b(3;20,0.75)\approx2.8\times 10^{-8}$
- $b(3;20,0.25)\approx 0.13$
- $b(5;20,0.75)\approx 3.4 \times 10^{-6}$
- $b(5;20,0.25)\approx 0.2$