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