CSCI 3200 Algorithm Analysis

Advanced algorithm analysis including the introduction of formal techniques and the underlying mathematical theory. Topics include asymptotic analyses of complexity bounds using big-0, 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.

Credits

3

Prerequisite

CSCI 2900

Typically Offered

Demorest: Spring (Every other odd year)

Student Learning Outcomes

Upon the completion of this course, students will be able to demonstrate the following outcome-based learning skills:

1. Develop a basic understanding of the design and analysis of algorithms.
2. Become proficient with a variety of classic algorithms for numeric and nonnumeric problems such as sorting, VLSI design, matrix multiplication, scheduling, graph theory, and geometry.
3. Understand different algorithm design techniques such as approximation algorithm, divide-and-conquer, dynamic programming, greedy method.
4. Become proficient in comparing the computational complexity of different algorithms and analyze the time and space efficiency of algorithms.