CS 173: Skills list for Sixth CBTF Test
The sixth CBTF test will have 5 questions on topics related to using the recursion tree method to analyze algorithm running time, and counting. The specific skills it will test are
- Recursion Trees
- Given a recursively defined function, find its closed form by drawing
a recursion tree and adding up the work at all levels.
(Examples would look like those presented in Jeff's notes posted on the course webpage, e.g.
the level sums are constant or increase in a pattern based on
the key summations given above.)
- Find a big-O solution for a simple recursive definition, of the types that we've
seen as examples of unrolling and recursion trees.
- Counting
- Know the product rule, sum rule, generalized product, the correspondence rule, the division rule for counting.
- Apply these rules to find the size of simple sets.
- Know what the number of ways of ordering r objects out of n is (P(n,r)) and how many ways of picking a subset of size k from a set of size n (n choose k).
- Use permutations and combinations to count objects.
- Combine all the counting rules to solve more complicated problems.