# MUN Computer Science 1002 - Mini-Lab (lab 10) Expectations, recurrences and growth of functions.

### Review:

• Lectures 30-31.

### Vocabulary

• Expectation, linearity of expectation
• Tower of Hanoi, recurrence relations
• Big-Oh and Big-Theta notation
• Master Theorem for solving recurrences

## Mini-lab: solve either on your own or in groups

Solve each of the following exercises.

1. Compute expectation of the following:
1. Value of a throw of a fair die (with equal probability of 1,2,3,4,5,6)? Hint: it does not have to be a natural number.
2. Value of a throw of a biased die where 2 and 4 have twice the probability of any other side?
3. Sum of values from a throw of two fair dice? Two fair dice and one biased die from b)? (Hint: use linearity of expectation)
4. Number of rolls of a fair die until you see 4? Number of rolls of a biased die from b) until you see 4?
5. Number of 1s in a random binary string of length n? Hint: start by introducing an indicator random variable for each bit, then looking at their sum.
2. Determine for each of the following whether $f(n) \in O(g(n))$, $g(n) \in O(f(n))$ or both (that is, $f(n) \in \Theta(g(n))$). In each case, give values for $n_0$ and $c$.
1. $f(n) = 2n^2 +3n +5$, $g(n) = n^2 / 5 - 15$
2. $f(n) = n \log n$, $g(n) = 100n + \frac{10}{\log n}$
3. $f(n) = (2^n)^2$, $g(n) = 2^{n^2}$
3. Use Master theorem (slide 12 in lecture 31) to determine the asymptotic growth rate of functions defined by the following recurrences (that is, for which $g(n)$ without constants or terms other than the leading term is $T(n) \in \Theta(g(n))$ -- i.e., $\Theta(n^2), \Theta(2^n), \Theta(n\log n)$..). In all of them, set $T(1) = 1$ to be the base of the recursion.
1. $T(n) = 2 T(n/2) + n$.
2. $T(n) = 4 T(n/2) + 1$.
3. $T(n) = 2 T(n/4) + n^4$.