Midterm 2 Study Guide

Topics:

1. Algorithms and Runtime complexity
   • definitions of big-O, big-Omega, big-Theta notation
   • determining big-O/Theta estimates
   • relative orders of growth
   • classes of problems
2. Induction
   • proof by mathematical induction
   • proof by strong induction
   • proof of recursive functions by induction
3. Counting
   • basic counting techniques:
   • sum rule
   • product rule
   • subtraction rule
   • division rule
   • r-permutations/combionations (with/without replacement)
   • permutations of indistinguishable objects
   • binomial theorem
   • pigeonhole principle and applications
   • combinatorial proof techniques