CS 173: Skills list for Examlet 11
- Summations
- Know the closed forms of arithmetic and geometric series
- Know how to manipulate simple summations to derive a closed form, e.g., using known closed forms for other summations
- Recurrences
- Know how to use unrolling to find closed forms of simple recurrences.
In particular:
- Predict the form after unrolling k times
- Find the value of k that matches the base case
- Plug in the correct value of k and simplify (esp. removing log(n) terms from exponents) to find a closed form
- Know how to execute the recursion tree method to find closed forms of recurrences.
In particular:
- Compute the "extra work" at level k in the tree
- Compute the number of (internal) levels in the tree
- Compute the number of leaves and therefore the total work at the leaves
- Manipulate and simplify (esp. removing log(n) terms from exponents) the resulting sum(mation) into a closed form