# 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