CS 173: Skills list for Examlet 10
- Counting
- Know the sum rule, product rule, bijection rule, generalized product rule, and how to use them to count the sizes of simple sets.
- Know the permutation rule P(n,k) and combination/subset rule () for counting sequences and subsets, as well as how to use them to count objects
- Know how to combine multiple counting rules to count more complicated objects
- Know the formulas for P(n,k) and () so as to be able to compute numerical solutions to small-ish instances of counting problems
- Know how to adapt some useful examples from the Notes like counting paths in the integer grid (Example 22), or number of integer solutions to a linear equation (Example 23) to solve other problems (e.g., Notes Example 24, Worksheet Problem 2, Homework Problems 3-5)
- Probability
- Know what a sample space, probability distribution, and event are
- Know the definition of conditional probability and independence
- Know how to compute (possibly conditional) probabilities involving uniform probability distributions by "counting twice" (cardinality of the event and the sample space). This includes both simple concrete numerical probabilities, e.g., throwing a fixed number of dice or flipping a coin a fixed number of times, as well as computing more general formulas, e.g., Worksheet Problem 2, Homework Problem 3
- Know the sum rule, difference rule, union bound, and monotonicity rule for general probability distributions
- Know Kolmogorov's rule and Bayes' rule for conditional probability, as well as implications of independence
- Know how to combine multiple rules to compute the (possibly conditional) probability of a certain event using (possibly conditional) probabilities of other events
- Be able to determine if simple statements involving probabilities are true, e.g., Worksheet Problem 5