CS 173: Skills list for Sixth Written Test

The sixth written test will have 3 questions on topics related to using the recursion tree method to analyze algorithm running time, counting, and probability. 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.
  • Know how to count the number of ways of choosing k objects from n types with repetition.
  • Know the Binomial theorem and be able to apply it to solve counting problems.
  • Know how to count the number of sequences with repeated elements.
  • Know the mathematical definition of the multinomial coefficient and its relationship to counting problems.
  • Know the multinomial theorem and be able to apply it to solve counting problems.
  • Be able to state and apply the Pigeonhole Principle to problems.
  • Apply the pigeonhole principle in writing proofs.
  • Know the Principle of Inclusion-Exclusion, and be able to apply it to count the cardinality of a set.
  • Know how to prove an equation combinatorially. That is be able to identify a set such that both sides of an equation count its cardinality.
  • Apply combinatorial proofs to problems.
• Probability
  • Know what a probability space is.
  • Know how to solve a problem by identifying a sample space, a probability distribution, and calculate the probability of an event.
  • Apply the method to compute probability of events.
  • Know the definition of conditional probability.
  • Know how to compute the conditional probability of events.
  • Know Bayes rule, and how to use it to compute conditional probabilities.
  • Know the definition of independence of two events, and its consequences.
  • Know how to determine if a pair of events are independent.