CS 173, Spring 2009: Skills list for first midterm

The first midterm will cover the material presented in lectures 1-14. Since you have not yet had time to do homework problems on the material from lectures 12-14, only more basic aspects of this material will be tested. The corresponding sections of Rosen are listed on the Lectures web page.

Specific skills you should know include:

• Everything on the skills list for the first quiz.
• Propositional and predicate logic
  • Know that any positive integer can be written as the product of primes. Do this for a specific integer. Know that there are infinite many primes.
  • Know that a statement of the form ∀ x, ∃ y P(x,y) is not equivalent to the statement ∃ y, ∀ x, P(x,y). We will not assume you fully understand the meaning of nested combinations of existential and universal quantifiers.
  • Negate a statement containing multiple quantifiers.
• Number Theory
  • Be able to define GCD(a,b) and LCM(a,b), compute values for specific inputs using prime factorizations.
  • State the division algorithm.
  • 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.
• Base-k number representations
  • Express a base-k number using a polynomial in k.
  • Know how to write hexadecimal numbers i.e. with the digits going from 0 through F.
  • Convert an integer from one base to another.
• 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 power set of A
    • 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.
  • Given a simple set identity (e.g. the ones in the tables on Rosen pp 124-125) recognize whether it's correct or not. If not, show a counter-example.
  • Know DeMorgan's laws and the distributive laws.
  • Know how to compute the cardinality of a set created using operations such as union, cartesian product, power set.
  • Given a set identity, recognize whether it's true. If not, give a counter-example.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain and co-domain.
  • Be able to quote back the definition of when a function is one-to-one (injective) and onto (surjective). Given a familiar function (e.g. absolute value on the integers), identify whether it's one-to-one and/or onto.
• Proof techniques.
  • Be able to write a simple direct proof, using familiar concepts, with good mathematical style.
  • Be able to convert a claim to its contrapositive and prove that using direct proof.
  • Given a claim, outline a proof by contradition. Fill in details of the proof if it involves familiar concepts.
  • Know the following standard ways to approach parts of a proof:
    • prove a universal claim by choosing a representative object of the appropriate type
    • prove an if/then statement by assuming whatever's in the hypothesis and proving the conclusion,
    • prove an existential claim by exhibit specific values that make the claim true
  • Disprove a universal claim by exhibiting a counterexample.
  • Identify mistakes in proofs, where the proof is of a type we've said you should know how to write.