CS 173, Spring 2010: 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 some brief homework problems on the material
from lectures 37-39, and no discussion or homeworks covering lecture
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:
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).
- Know how to prove 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 K5 and K3,3 are not planar.
(You don't have to be able to explain why.)
- Know that Kuratowki's theorem states that every non-planar
graph contains a subgraph homeomorphic to
K5 or K3,3. But you don't have to have a
clear model of exactly what homeomorphic means.
- 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.
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 that any planar graph can be colored with 4 colors, and that
this was proved at U. Illinois in the 1970's.
Cardinality
- Define what it means for two sets to have the same cardinality:
i.e. there is a bijection mapping one onto the other.
- Know that a countable set is a set with the same cardinality as the
integers.
- Know that the integers and the rationals are both
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.
- You won't need to reproduce the construction
for mapping the rationals to/from the integers, nor the diagonalization
method used to prove that the reals are uncountable.
-----------------------------------------------------------