Algorithms

This course covers the analysis and design of algorithms. Good algorithm design is crucial for software performance. Topics include: efficiency analysis; big-O, omega, and theta notation for asymptotic upper, lower, and tight bounds on algorithm time complexity; recurrence equations; proof by induction and contradiction; brute-force, greedy, and divide-and-conquer algorithms; sorting algorithms including heapsort, mergesort, quicksort; graphs, trees, heaps; breadth and depth-first search; Dijkstra’s shortest-path algorithm; minimum spanning trees, Prim’s algorithm; maximum network flow; dynamic programming; NP-complete problems and the P and NP classes; and the halting problem as an example of a provably unsolvable problem. In-depth programming assignments.