CS 173: Skills list for "Examlet B"

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]_k (and the shorthand [x] for when k is clear from context).
- Know when [x]_k and [y]_k 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 subset/inclusion (⊆)
  - 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 (while keeping it arbitrary!) and showing it's in the larger set.

Collections of sets

Write simple proofs involving collections of sets and/or functions whose input and/or output values are sets.
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).
Interpret set-builder definitions of sets containing other sets.
Given a specific set A, list the elements of its power set.
Define the power set $\mathbb {P}$ (A) for a set A.
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.)

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.