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.)
- 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
- 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.
- 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.