CS 173, Fall 2009: 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 formulas for counting permutations, combinations, combinations with repetition, permutations with indistinguishable objects.
  • Know the Binomial Theorem, Pascal's Identity, Vandermonde's Identity.
  • Know the formula for a binomial distribution, and for the expected value of a binomial random variable.
  • 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.
• 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.
  • 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.
• 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 and prove that your answer is correct.
  • Define an equivalence relation, partial order, strict partial order.
• Graphs
  • Define a graph (set of vertices plus a set of edges), simple graph.
  • Understand terminology: directed vs. undirected graph, adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, self-loop, subgraph, path
  • Define: degree of a vertex, in-degree and out-degree (directed graphs).
  • State the Handshaking theorem. Know that a graph has an even number of vertices of odd degree.
  • 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.
  • Recognize when two graphs are isomorphic. Identify features which show that two graphs are not isomorphic (e.g. one has a vertex with a degree that doesn't match any vertex in the other).