CS 173, Spring 2010
Skills list for second quiz

The first quiz will cover the material presented in lectures 1-22, with an emphasis on more recent material. Since you have not yet had time to do homework problems on the material from lectures 20-22, 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 lists for the first quiz and the first midterm
• Logic and proof construction
  • Meaning of nested quantifiers
  • Proof by cases
  • "Without loss of generality"
• Functions
  • Identify key components of a function: domain, co-domain, image.
  • Define the properties one-to-one (injective), onto (surjective), one-to-one correspondence (bijection), composition, increasing, strictly increasing.
  • Identify whether a concrete example has one of these properties.
  • Prove that a specific function does/doesn't have one of these properties.
  • Prove that a general type of function has one of these properties, e.g. composition of two injective functions is injective.
• Set Theory
  • Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.
  • Prove a set equality by proving inclusion in both directions.
• Induction and recursive definition
  • Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
  • Know that "recurrence relation" is a synonym for recursive definition. (The base case is sometimes called the "initial condition".)
  • Use induction ("strong" or "weak") to prove a formula is correct for all integers starting at some base case.
  • Use induction to prove that a non-formula claim (e.g. a divisibility relation) holds for all integers starting at some base case.
  • Given a recursive definition of a function, find the output value for a specific input.
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
  • Identify key parts of an inductive proof: induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Define the Fibonacci numbers.
  • In a short quiz, you obviously can't do a whole complex proof by induction. But we might ask you to outline one, or fill in missing parts of one.
• Big Oh
  • Define what it means for a function f to be O(g), Ω(g), and/or θ(g). where g is another function.
  • For specific functions f and g, identify whether f is O(g), Ω(g), and/or θ(g).
  • Know the big-O relationships among key primitive functions: constant, log n, n, n log n, polynomials of higher orders, exponentials, factorial.
  • We will not ask you to prove these relations for this quiz. That will be on the second midterm.