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.