CS 173, Spring 2009: Skills list for third quiz

The second midterm 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). Since you have not yet had time to do homework problems on the material from lectures 33-35, only more basic aspects of this material will be tested. The corresponding sections of Rosen are listed on the Lectures web page.

• 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 8. 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.
  • Compute that expected value of a sum of random variables is the sum of their expected values (linearity of expectation).
• 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.
  • Give the degree sequence of a graph.
  • Define: Euler circuit, Euler path, Hamilton circuit, Hamilton path
  • Recognize when two graphs are isomorphic. Identify features which show that two graphs are not isomorphic (e.g. different vertex degrees).
  • State the Euler circuit theorem and Euler path theorem.