Review:
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.
- Compute expectation of the following:
- 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.
- Value of a throw of a biased die where 2 and 4 have twice the probability of any other side?
- Sum of values from a throw of two fair dice? Two fair dice and one biased die from b)? (Hint: use linearity of expectation)
- Number of rolls of a fair die until you see 4? Number of rolls of a biased die from b) until you see 4?
- 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.
- 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$.
- $f(n) = 2n^2 +3n +5$, $g(n) = n^2 / 5 - 15$
- $f(n) = n \log n$, $g(n) = 100n + \frac{10}{\log n}$
- $f(n) = (2^n)^2$, $g(n) = 2^{n^2}$
- 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.
- $T(n) = 2 T(n/2) + n$.
- $T(n) = 4 T(n/2) + 1$.
- $T(n) = 2 T(n/4) + n^4$.