CS 173, Spring 2009
Skills list for second quiz

The first quiz will cover the material presented in lectures 1-21, with an emphasis on more recent material. Since you have not yet had time to do homework problems on the material from lectures 20 and 21, 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
  • Definitions of domain, co-domain, image, one-to-one (injective), onto (surjective), one-to-one correspondence (bijection), composition, increasing, strictly increasing.
  • Identify whether concrete examples 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.
  • 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.
  • Define the Fibonacci numbers.
• 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).
  • We will not ask you to prove these relations for this quiz. That will be on the second midterm.
  • Given a recursively defined function, guess its closed form by "unrolling". Only very easy examples or examples directly from lecture.