Note: The following provides a suggested course description,
objectives, and an outline. These may be modified pending discussion with
the Faculty Chairs, proposing faculty, and other curriculum
reviewers.
Course Description: Includes techniques for algorithm
complexity analysis and important design paradigms such as
divide-and-conquer, dynamic programming and the greedy method with many
practical examples. Covers efficient algorithms for problems in areas such
as sorting, searching, graph theory, computational geometry and algebraic
and numeric algorithms. Introduces complexity classes and problem
reductions.
Course Objectives: To expose students to important
techniques used in the design and analysis of efficient algorithms and to
complexity analysis.
Course Outline by Topical Areas:
- Models of computation and complexity measures
- Asymptotic notations and solving recurrences
- Paradigms for efficient algorithm design (divide-and conquer,
dynamic programming, greedy method)
- Sorting and order statistics, amortized analysis
- Graph algorithms (connectivity, path problems, maximum flow)
- Computation geometry
- Matrix multiplication, FFT algorithms
- String matching
- Reductions and NP-completeness
- Introduction to parallel algorithms
