MUN Computer Science 1002 - Mini-Lab (lab 10)

Expectations, recurrences and growth of functions.




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$.