Prelim 2 Topics

This list of topics is not necessarily complete. Everything covered through Friday's lecture (graph theory) will be in scope. Material covered since the last prelim and on the homework will be given heavier emphasis.

You can find a collection of relevant questions from exams from previous semesters here (solutions). For questions on graph theory, an optional homework can be found here .

• Combinatorics
  • Know and be able to apply sum rule, product rule, quotient rule)
  • Permutations and combinations
  • Combinatorial identities
  • Pascal's triangle
  • Balls and urns
  • Binomial theorem
  • Pigeonhole principle
• Probability
  • Definitions:
    • sample space, event, outcome, probability measure
    • equiprobable measure
    • conditional probabilty
    • independent events
    • random variable
    • independent random variables
    • expectation, variance
  • Theorems:
    • Bayes's rule
    • Linearity of expectation
    • Two equivalent definitions of expectation
    • Two equivalent definitions of variance
    • Markov's and Chebychev's inequalities
  • Working with probability trees
  • Relating random variables and events
  • Examples
    • Bernoulli trials
  • Analysis of simple probabilistic algorithms
• Graphs
  • Definitions:
    • graph, directed graph
      • adjacent vertices
    • degree, indegree, outdegree
    • graph isomorphism
    • clique number of a graph
    • path, cycle, Hamiltonian path, Eulerian path
      • complete graph
      • connected graph
      • chromatic number of a graph - bipartite graph
  • Theorems
    • Handshaking theorem
    • Conditions for a graph to have an Eulerian path/cycle