Basic techniques for designing and analyzing algorithms: dynamic programming, divide and conquer, balancing. Upper and lower bounds on time and space costs, worst case and expected cost measures. A selection of applications such as disjoint set union/find, graph algorithms, search trees, pattern matching. The polynomial complexity classes P, NP, and co-NP; intractable problems.

Usually Offered:	Fall and Spring
Credit:	3 hours (class)
Prerequisite:	CS 381 and 483
University Catalog:	CS 580
Schedule:	Spring 2005 Instructor: Mike Atallah