CS 173, Spring 2015: Skills list for third examlet

• Logic
  • Know what it means for a statement to be "vacuously true."
• Modular arithmetic
  • For congruence mod k, know which integers are in the equivalence class of x. Know the shorthand notation [x].
  • Know when [x] and [y] are equal as elements of Z_k.
  • Do arithmetic in Z_k (e.g. addition, multiplication, taking integer powers), keeping intermediate results small.
• Set Theory
  • Notation
    • set builder notation for defining sets
    • set membership and inclusion notation: ⊆, ∈
    • special symbol for the empty set: ∅
    • an ordered pair, triple, n-tuple
  • Define formally, be familiar with standard notation, compute the values for concrete input sets
    • A is a subset of B
    • The cartesian product of two sets A and B, of three or more sets
    • The cardinality of a set
    • The complement of a set (given some specified universe).
    • The union, intersection, and difference of two sets.
  • Know the meaning of the term disjoint.
  • Know what happens if one of the inputs to these operations is the empty set.
  • Given a simple set relationship, recognize whether it's correct or not. If not, show a counter-example.
  • Know DeMorgan's laws and the distributive laws for sets.
  • Cardinality
    • Know the inclusion-exclusion formula relating the cardinality of sets A and B to that of their union and intersection.
    • Given the cardinality of two sets A and B, compute the cardinality of their Cartesian product.
    • Apply these two formulas to real-world counting problems.
• Set Theory Proofs
  • Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.