CS 173: Skills list for "Examlet A"

• Math prerequisites
  • Algebraic manipulations with: equations, inequalities, fractions, absolute value, squares and square roots, i (square root of -1)
  • 2nd order polynomials: solving, factoring, finding roots. Easy cases only: don't worry if you don't remember the quadratic formula.
  • Basic rules for manipulating exponents and logs
  • Defining and composing numerical functions. E.g. if f(x) = x-6 and g(x) = 7x, then g(f(x)) = 7(x-6).
• Numbers and sets
  • Know what sets these symbols represent: R, N, Z, Z⁺, Q, C.
  • Notation for set membership, e.g. x ∈ Z
  • Know that 0 belongs to N but not Z⁺. (There's two conventions about what's in N. This is the one we are using this term.)
  • Know the notations [a,b] and (a,b) for closed and open intervals of the real line.
  • Know the definitions of the floor and ceiling functions, i.e. ⌈ x ⌉ and ⌊ x ⌋
• Propositional and predicate logic
  • Know the truth tables for basic logical operators, especially implies. Know that, unless there is specific indication otherwise, "or" means inclusive or.
  • Know the meaning of the universal and existential quantifier, shorthand notation, and basic terminology such as "scope" of a quantifier.
  • Translate between English and logical shorthand. 
  • Know the distributive, commutative, and associative laws and that "p implies q" is equivalent to "(not p) or q".
  • Given a new, fairly simple, logical equivalence, figure out whether it's correct or not and explain why using a truth table or counter-example.
  • Identify non-statements (e.g. questions) and statements which are neither true not false, because they contain variables not bound by a quantifier.
  • Decide whether a complex statement is true, given information about the truth of the basic statements it's made out of.
  • Identify the hypothesis and the conclusion of an if/then statement.
  • Given a statement, give its negation.
  • Given an if/then statement, give its converse, and contrapositive. Know that the contrapositive is equivalent to the original statement, but the converse is not.
  • Simplify a negation or contrapositive by moving all negations onto individual propositions. This requires knowing certain key logical equivalences: double negation, DeMorgan's laws, and the rules for negating if/then statements and quantifiers.
• Number Theory
  • Know 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
  • Apply the definition of divides to zero and to negative numbers (these aren't really 'edge cases' - the same exact definition applies!). For example, explain why zero is an even number.
  • 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.
  • 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 and Proof techniques.
  • Write a simple direct proof, using familiar concepts, with good mathematical style. Make sure your statements are in logical order, starting with the given information and ending with what you needed to show.
  • Write a proof by cases
  • Convert a claim to its contrapositive and prove that using direct proof.
  • Know the following standard ways to approach parts of a proof:
    • prove a universal claim by working with a 'representative' object of the appropriate type (not a concrete example)
    • prove an if/then statement by assuming whatever's in the hypothesis and proving the conclusion
    • disprove a universal claim by giving a concrete counterexample
    • prove an existential claim by giving specific values that make the claim true
  • Know what it means for a statement to be "vacuously true."
  • Write a proof by contradiction 
• 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.