CS 173, Fall 2014: Skills list for seventh examlet

• 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 forms for two key summations: sum of the first n integers and sum of (1/2)^k (for k from 1 to n).
• (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 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.