CS 4306:Algorithm Analysis

3 Class Hours 0 Laboratory Hours 3 Credit Hours
Prerequisite: CS 3305 and CS 3305L
Advanced algorithm analysis including the introduction of formal techniques and the underlying mathematical theory. Topics include asymptotic analyses of complexity bounds using big-O, little-o, omega, and theta notations. Fundamental algorithmic strategies (brute-force, greedy, divide-and-conquer, backtracking, branch-and-bound, pattern matching, parallel algorithms, 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, NP-completeness, the halting problem, and the implications of non-computability.