CS 173, Fall 2009: Skills list for the final

The final will be no more than twice as long as the midterms (probably somewhat shorter), but you will have the full three hours to work on it. The exam will cover all the material from the course, with an emphasis on what was covered since the second midterm. Since you had only a brief HW problem on the material from lectures 39/40, and no discussion or homeworks covering lectures 41, we'll only ask superficial "headline" questions about this material. (See below for details.)

We will assume that you still remember the topics from the skills lists for the previous exams and the quizzes. Here's the new skills:

Specific skills you should know include:

• Counting
  • Be able to state the Pigeonhole Principle and apply it in writing proofs.
• Relations
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Prove that a relation is, or isn't, an equivalence relation, an partial order, and/or a strict partial order.
  • Don't get confused if it's a relation between objects consisting of 2 or 3 numbers (e.g. pairs of integers or intervals of the real line) or 2D objects (e.g. lines, graphs).
  • For an equivalence relation R, define the equivalence class [x] of an element x. For a specific element x, determine what's in [x]. List or describe all the equivalence classes for R.
  • Define a partition of a set S. Know that the equivalence classes of an equivalence relation form a partition.
  • Suppose R is a relation on a set S. Show that an operation on S is well-defined on the equivalence classes of R.
• Planar Graphs
  • Define what it means for a graph to be planar. Show that a (small!) example graph G is planar by drawing a 2D picture of G that doesn't have any crossing edges.
  • Know what a face is (including the unbounded region outside the graph).
  • Know what the degree of a face is (i.e. number of edges in its boundary)
  • Know (or be able to quickly reconstruct) the fact that the sum of the face degrees is twice the number of edges, for a planar graph.
  • State Euler's formula (for a connected, planar graph).
  • Know that K₅ and K_3,3 are not planar. (You don't have to be able to explain why.)
  • Be able to recognize when two graphs are homeomorphic (aka one is a subdivision of the other or they are both subdivisions of some third graph). But you don't have be able to define subdivision or homeomorphic.
  • State Kuratowski's theorem.
  • Know that a graph can be drawn on the plane if and only if it can be drawn on a sphere.
  • Know that there are exactly 5 Platonic solids (polyhedra with uniform vertex and edge degrees) and we somehow derived this from their relationship to planar graphs.
  • 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 any planar graph can be colored with 4 colors, and that this was proved at U. Illinois in the 1970's.