CS 173, Fall 2014: Skills list for eighth examlet

The proof for this examlet will be long. Therefore, you should expect a correspondingly smaller amount of short-answer material.

• Recursive definition
  • Understand how to read a recursive definition, e.g. compute selected values or objects produced by that definition.
  • Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
  • Define the Fibonacci numbers.
  • Know the definition of the k-dimensional hypercube graph, its shorthand name Q_k, and how many vertices it contains.
• Unrolling
  • Given a recursively defined function, find its closed form by "unrolling". Test questions will involve either doing certain key steps or a very simple example, not an entire long messy unrolling.
• Induction
  • Write inductive proofs that need to use the truth of the claim for more than one immediately previous value, e.g. multiple previous values, a previous value several steps back.
  • Determine whether an inductive proof requires more than one base case and, if so, which ones.
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
  • For recursively defined sets of objects (e.g. graphs), use induction to prove that they have some specific property (e.g. number of edges) and/or write a recurrence for the values of some property of the objects (e.g. number of edges).