CSC 501 - Algorithm Design and Analysis Credits: 3

Examines various techniques for designing algorithms, analyzes and compares algorithms in terms of storage and computational complexity, and examines proof techniques for doing the analysis. Analysis of run-time growth of algorithms includes the growth classes O, ?, ?, ?, and o. Worst-case, best-case and average-case analysis. Solving recurrences. Analysis of sorting algorithms. Design techniques to control growth including data structures, divide-and-conquer, dynamic programming, memorization, and greedy algorithms. Translation of real-world problems to graph problems and algorithms for graph problems including graph searches, topological sort, shortest path and minimum spanning tree. The classes P, NP, and proving a problem is NP-complete.

Prerequisite(s): MAT 318, CSC 111.