Final Exam Study Guide

Topics:

  1. Discrete Probability

    • basic definitions: experiment, sample space, event, probability of event
    • sum & complement rule
    • conditional probability
      • independence
    • Bayes' theorem
    • random variables
      • probability mass function and cumulative distribution function
    • probability distributions
      • Bernoulli distribution
      • uniform distribution
      • binomial distribution
    • expected value
      • linearity of expectations
  2. Graphs

    • basic graph terms/defs
    • special graphs (complete, bipartite, etc.)
    • graph representations
    • graph isomorphism
    • connectivity
      • connected components
      • cut vertices/edges
    • graph traversals
      • Euler paths/circuits
      • Hamiltonian paths/circuits
      • Traveling salesperson problem
      • shortest path & Dijkstra's algorithm
    • graph coloring
      • basic graph coloring algorithm
  3. Trees

    • basic tree terms/defs
    • spanning and minimum spanning trees
      • Prim's MST algorithm
      • Kruskal's MST algorithm
  4. Modeling Computation

    • working with formal grammars
      • deriving sentences
    • deterministic finite state automata
      • recognizing strings/languages
    • pumping lemma