Advanced algorithm analysis including the introduction of formal techniques and the underlying mathematical theory. NP-completeness. Search Techniques. Randomized Algorithms. Heuristic and Approximation Algorithms. Topics include asymptotic analysis of upper and average complexity bounds using big-O, little-o, and theta notation. Fundamental algorithmic strategies (brute-force, greedy, divide-and-conquer, backtracking, branch-and-bound, pattern matching, and numerical approximations) are covered. Also included are standard graph and tree algorithms. Additional topics include standard complexity classes, time and space tradeoffs in algorithms, using recurrence relations to analyze recursive algorithms, non-computable functions, the halting problem, and the implications of non-computability. Algorithmic animation is used to reinforce theoretical results. Upon completion of the course, students should be able to explain the mathematical concepts used in describing the complexity of an algorithm, and select and apply algorithms appropriate to a particular situation.

Course Syllabus