CS 173, Fall 2015: Skills list for twelfth examlet

• Logic and proofs
  • Recap from the past: give the negation of a statement or the contrapositive (if/then statements only), simplifying it so that all negations are on individual propositions/predicates.
  • Write a proof by contradiction.
• Collections of sets
  • Manipulate sets containing other sets using standard set operations. (Be careful of getting the right number of brackets in examples involving the empty set and sets with only one element.)
  • Define the power set P(A) for a set A.
  • Given a specific set A, list the elements of its power set.
  • Correctly interpret set-builder definitions of sets containing other sets.
  • Correctly interpret definitions for functions whose input and/or output values are sets (i.e. when the domain and/or co-domain is a power set).
  • Write simple proofs involving collections of sets and/or functions whose input and/or output values are sets.
• Partitions
  • Define a partition of a set A: be able to state the properties informally and also write them precisely in formal notation.
  • Determine whether a specific set P is a partition of some specific set A.
  • Know that the equivalence classes of an equivalence relation on A form a partition of A.
• Counting
  • Know the shorthand notation for binomial coefficients (number of combinations) and its definition in terms of factorials.
  • Know the formula for computing the number of combinations of k objects from n types, with repetition.
  • Know the Binomial Theorem and Pascal's Identity.
  • Be able to solve practical counting problems involving combinations, combinations with repetition, and applications of the Binomial Theorem.