CS 173: Skills list for "Examlet D"

• Graph coloring
  • Know that a (vertex) coloring of a graph is labelling of each vertex with a color, such that adjacent vertices always have different colors.
  • Know that the chromatic number of a graph is the minimum number of colors required to color it.
  • Know the shorthand notation χ(G).
  • Know that graph coloring is useful for (among other things) register allocation in compilers for programming languages like C and Java.
  • Know that if D is the maximum degree of any vertex in a graph G, then G can be colored with D+1 colors.
  • Know that the "greedy" coloring algorithm often produces pretty good colorings fast, but is not guaranteed to produce the best solution.
• Two-way bounding
  • Understand the difference between an exact result, an upper bound, and a lower bound.
  • Prove an equality by establishing upper and lower bounds. E.g. prove that the chromatic number of a graph G is n.
  • Prove a set equality by proving inclusion in both directions.
• Summations
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
  • Extract the first or last term in a sum or product.
  • Rewrite a sum or product so that its index variable starts at a different number.
  • Know the closed form for the sum of the first n positive integers.
  • Know the closed form for a geometric series, especially two common cases: sum of (1/2)^k and sum of 2^k.
  • Know how to adjust a closed form for changes in the start/end index values.
• (Easy) Induction
  • Given a claim, identify/state the key parts of an inductive proof: the induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Be able to state a (strong) inductive hypothesis. (We always use strong hypotheses in this class, but some of you may have used weak hypotheses in other classes.)
  • Use induction to prove a formula (equality or inequality) 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.
  • Any proofs for this first half of the examlet will have very simple structure. In particular, the truth of the claim at n=k depends only on the claim being true at n=k-1, with only one base case required​

• 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 requires both a base case (or cases) and a recursive step/formula.
  • Define the Fibonacci numbers.
• ​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. (We will take off points both for missing base cases and also for extra base cases.)
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.​​​​