# CS 173, Fall 2014: Skills list for third examlet

• Course logistics
• Know the day and time of your assigned discussion section. (We reserve the right to deduct a point from examlets missing this information, especially for repeat offenders.)
• 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 Zk.
• Do arithmetic in Zk (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.