COMP 285 - Design and Analysis of Computer Algorithms

When Offered: F, S, SS

3 Credit(s)
3 Lecture Hour(s)
0 Lab Hour(s)

This course covers analysis of efficient algorithms for sorting, searching, dynamic structure manipulation, path-finding, fast multiplication, and other problems. It introduces algorithmic techniques such as recursion, divide-and-conquer, and dynamic programming. It develops the following tools for algorithmic analysis: correctness proofs, algorithm synthesis, and discusses issues in non-computability. The course also overviews non-deterministic algorithms, and develops techniques to classify computationally hard problems. The concept of non-deterministic polynomial (NP)-completeness is introduced, and basic issues related to NP-completeness are discussed.

Prerequisite(s): COMP 280 and MATH 131.