CS 173: Skills list for Examlet 2
- Number Theory
- Quote back definitions, decide if simple statements
involving them are true, understand the corresponding shorthand
notation:
- a divides b, b is a multiple of a,
- x is odd, x is even
- x is prime, x is composite
- x is a perfect square
- x is a rational number
- x and y are relatively prime
- Special cases for divides:
zero is even, zero divides itself
but not any other integer, and every integer divides zero.
- Prime numbers, factoring a number into primes.
(Where we only consider numbers >= 2.)
- Special cases for prime: 0 and 1 are not prime (primes must
be greater than or equal to 2).
- Know the definitions of gcd(a,b) and lcm(a,b) and
be able to compute gcd(a,b) and lcm(a,b) for specific (smallish) values
of a and b.
- Write any (small) positive integer as a product of primes.
- Know that sqrt(2) is not rational.
- Know that there are infinitely many primes.
- Be able to state the Fundamental Theorem of Arithmetic:
Any integer >= 2 can be written as the product of
primes and each integer has only one prime factorization
(except for the order in which you write the factors).
- Define what it means for x and y to be congruent mod k
- Be able to state the "Division Algorithm" theorem.
- Compute the gcd of two larger numbers using the Euclidean algorithm,
i.e. trace the execution of the algorithm. Be able to reproduce
its pseudocode.
- Prove simple number theory claims using direct proof and the
definitions of the terms involved.
For example, if a divides b and a divides c, then
a divides b+c.
- 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.