CS 173, Fall 2008: Skills list for the final

The final will be about twice as long as the midterms, though 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 did not do homework problems based on the material in lectures 39-41, we will assume less detailed knowledge of these topics.

We will assume that you still remember the topics from the midterm 1 and midterm 2 skills lists. You should also know about number representations (end of lecture 9) which was left off the second midterm skills list.

Here's list of new skills you should know. See the Lectures web page for the corresponding sections of Rosen.

Specific skills you should know include:

• Counting
  • Know the formulas for counting permutations, combinations, combinations with repetition, permutations with indistinguishable objects.
  • Know the Binomial Theorem, Pascal's Identity, Vandermonde's Identity.
  • Apply these formulas to solve word problems.
• Discrete Probability
  • Calculate probabilities by comparing often an event occurs to the size of the sample space.
  • Define conditional probability, compute the conditional probability of two specific events.
  • Define what it means for two events to be independent. Decide whether two specific events are independent
  • Know the formula for Bernoulli trials. Apply the formula to word problems.
  • Define a (discrete) random variable. Compute the expected value of a random variable.
  • Compute that expected value of a sum of random variables is the sum of their expected values (linearity of expectation).
• Relations
  • Define a relation from A to B, or on a set A.
  • Represent a relation as a set of pairs, a directed graph, or a matrix.
  • Count the number of possible relations between two sets or on a single set.
  • Define reflexive, irreflexive, symmetric, anti-symmetric, transitive. For any of these problems, determine if a specific relation has the property and prove that your answer is correct.
  • Compute the transitive, reflexive, or symmetric closure of a relation.
• Equivalence relations and partial orders
  • Define an equivalence relation, partial order, total order. Determine if a specific relation is one of these, prove your answer correct.
  • 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.
  • Represent a partial order using a Hasse diagram.
  • Define and know how to compute a topological sorting of a partial order.
  • Know the difference between a minimum and a minimal element of a partially ordered set, similarly for maximum and maximal.
• Graphs
  • Define a graph (set of vertices plus a set of edges), planar graph
  • Define: directed vs. undirected graphs, simple graph, multigraph, pseudograph, bipartite graph
  • Define: adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, region/face (planar graphs), loop, subgraph, union of two graphs
  • Define: degree of a vertex, in-degree and out-degree (directed graphs), degree of a face (planar graph),
  • State the Handshaking theorem. State the similar theorem for faces.
  • Define special graphs K_n, C_n, W_n, Q_n, K_n,m and know their full names (e.g. "complete bipartite graph"). Beware: W_n contains n+1 vertices.
  • Represent a graph using an adjacency matrix or adjacency lists
  • Give the degree sequence of a graph.
  • Define: path, circuit/cycle, simple path, connected graph.
• Bigger-scale facts about graphs
  • Recognize when two graphs are isomorphic, when one is a subdivison of another, when two graphs are homeomorphic. Explain why you are right, e.g. match up the vertices to show isomorphism, point out an incompatibility in vertex degress to prove non-isomorphism. (Don't worry about stating the formal definitions.)
  • Define: Euler circuit, Euler path, Hamilton circuit, Hamilton path
  • State the Euler circuit theorem and Euler path theorem.
  • State Euler's theorem for planar graphs
  • State Kuratowski's theorem.
  • We saw various corollaries of Euler's theorem relating numbers of edges and vertices, in lecture and homework 12. You don't have to memorize these equations. But be able to prove these (or similar) equations given some hints about what facts to start with.
• Graph coloring
  • Define: coloring of a graph, chromatic number of a graph
  • Compute chromatic number for easy cases.
  • Draw the dual of a graph graph
  • State the four color theorem.
  • Take a real-world problem (e.g. final exam scheduling) and explain how to represent it as a graph coloring problem.
• Trees
  • Define a tree (connected graph with no cycles), a forest, rooted tree.
  • Define and use rooted tree terminology: root, leaf, internal vertex, parent, child, sibling, ancestor, level of a vertex, height of tree
  • Define: binary tree, full binary tree, balanced binary tree
  • Know key facts: a tree has one more vertex than edges, a full binary tree with n internal vertices has n+1 leaves (and thus 2n+1 vertices total),
  • Know key facts about binary trees of height h: ≤ 2^h leaves, &le 2^h+1 + 1 vertices, ≥ h+1 vertices
  • Define what a prefix code is, identify whether a code is or isn't a prefix code.