CS 173, Spring 2010: Skills list for third quiz

The third quiz will cover the material presented in lectures 1-35. It will focus on the material since lecture 27 (the last lecture covered on the second midterm). The corresponding sections of Rosen are listed on the Lectures web page. Since you have not yet had time to do homework problems graphs and relations, only more basic aspects of this material will be tested.

• Everything on the skills lists for the previous quizzes and midterms.
• Structural and tree induction
  • You should know how to simple structural and tree induction proofs, like those on homework 9. We can't ask you to write such a proof on a short quiz, but we might ask you something simpler e.g. to write the inductive hypothesis for such a proof.
• Counting
  • Know the product rule, sum rule, and inclusion-exclusion principle.
  • 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.
  • Be able to state the Pigeonhole Principle and apply it in writing proofs.
• Relations
  • Define a relation on a set A.
  • Represent a relation as a set of pairs or a directed graph, convert between the two representations.
  • Define reflexive, irreflexive, symmetric, anti-symmetric, transitive. For any of these problems, determine if a specific relation has the property.
  • Define an equivalence relation, partial order, 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 or describe all of R's equivalence classes.
  • Define a partition of a set S. Know that the equivalence classes of an equivalence relation form a partition.
• Graphs
  • Define a graph (set of vertices/nodes plus a set of edges), simple graph.
  • Understand design options for graphs: directed vs. undirected, are multi-edges allowed, are self-loops allowed.
  • Know how to represent an edge as an ordered pair (directed) or a 2-element set (undirected).
  • Understand terminology: adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, subgraph, path, cycle/circuit, simple path.
  • Be able to write out the path connecting two vertices as a sequence of edges.
  • Define: degree of a vertex, in-degree and out-degree (directed graphs), connected components of a graph.
  • State the Handshaking theorem.
  • 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.
  • Know the numbers of vertices and edges in each special type of graph (except for Q_n).
  • Define an Euler circuit. Know that an Euler circuit exists if all vertices in the graph have even degree.
• Graph isomorphsim
  • Show that two graphs are isomorphic by giving a bijection between their vertices.
  • Prove that two graphs are not isomorphic by finding a feature that differs, e.g. one has a vertex with a degree that doesn't match any vertex degree in the other.