Introduction to the analysis of algorithms and data structures in a mathematically rigorous fashion. Mathematical fundamentals, counting, discrete probability, asymptotic notation, recurrences, loop invariants. Worst-case, probabilistic and amortized analysis techniques applied to sorting algorithms and classic data structures such as heaps, trees and hash tables. Design techniques such as branch and bound, divide and conquer, will be introduced as will correctness proofs for algorithms.
Fall 2019, Spring 2019, Fall 2018, Spring 2018, Fall 2017