Description:  Asymptotic analysis of upper and average complexity bounds; Identifying differences among best, average, and worst case behaviors; Big oh, little oh, omega, and theta notation; Standard complexity classes; Empirical measurements of performance; Time and space tradeoffs in algorithms; Using recurrence relations to analyze recursive algorithms; Algorithmic strategies including bruteforce, greedy, divideandconquer, backtracking, branchandbound, heuristics and pattern matching; Introduction to P and NP. (Prerequisite: ITBP319) 
Topics Outline:   Review of proof techniques (SO: a)
 Basic algorithmic analysis: Asymptotic analysis of upper and average complexity bounds; best, average, and worst case behaviors; bigO, littleo, ?, and ? notation; standard complexity classes; empirical measurements of performance; time and space tradeoffs in algorithms;
(SO: a, b, c)
 Recurrence relations to analyze recursive algorithms
(SO: a, b, m)
 Fundamental algorithmic strategies: Bruteforce; greedy; divideandconquer; backtracking; branchandbound; heuristics; pattern matching and string/text algorithms; numerical approximation
(SO: a, b, c, n, i, j)
 Fundamental data structures: Implementation strategies for graphs and trees; performance issues for data structures
(SO: b, c, g, i, j, k)
 Graph and tree algorithms: Depth and breadthfirst traversals; shortestpath algorithms (Dijkstra?s and Floyd?s algorithms); transitive closure (Floyd?s algorithm); minimum spanning tree (Prim?s and Kruskal?s algorithms); topological sort
(SO: b, c, g, i, j, k)
 Machines and Computability
(SO: a)
