CS 173, Spring 2010: 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.

When you take the exam, you cannot use cheat sheets, calculators, other electronic devices, etc. We try to write the questions so that such assistance won't be required.

Specific skills you should know include:

• Everything on the skills list for the first quiz.
• Propositional and predicate logic
  • 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.
• Pseudocode
  • Be able to read and write simple bits of pseudocode. (We aren't picky about the precise syntax.)
• Number Theory
  • Be able to state the "Division Algorithm" theorem.
  • Compute n mod m for specific values of n and m.
  • Define when two integers are congruent mod m. Determine whether this is true for two specific integers and a specific m.
  • 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.
• 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.
  • Know what happens if one of the inputs to these operations is the empty set.
  • 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 for sets.
  • Given the cardinality of sets A and B, know how to compute the cardinality of the power set of A and the cardinality of the cartesian product of A and B.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, and image.
• 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 the negation or contrapositive of a statement, moving all negations onto individual propositions.
  • Convert a claim to its contrapositive and prove that using direct proof.
  • Given a claim about the non-existence of something, 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 exhibiting 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.