CS 173, Spring 2009: Skills list for the final

The final will be no more than twice as long as the midterms, 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 lecture 37, and no discussion or homeworks covering lectures 38-40, 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:

• Relations
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • 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.
  • Show that a relation is, or isn't, an equivalence relation, an partial order, and/or a strict partial order.
  • 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 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.
• Cardinality
  • Define what it means for two sets to have the same cardinality, and for a set to be countable.
  • Know that any infinite subset of the integers or the rationals is countable, but the reals and intervals of the reals (e.g. [0,1]) aren't countable.
  • Know that there are mathematical functions that can't be computed by any program.
• 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 that K₅ and K_3,3 are not planar. (You don't have to be able to explain why.)
  • 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 simple, connected, planar graph).
  • Know that any planar graph can be colored with 4 colors, and that this was proved at U. Illinois in the 1970's.