Description: This course investigates methods for designing efficient and reliable algorithms. By carefully analyzing the structure of a problem within a mathematical framework, it is often possible to dramatically decrease the computational resources needed to find a solution. In addition, analysis provides a method for verifying the correctness of an algorithm and accurately estimating its running time and space requirements. We will study several algorithm desgin strategies that build on data structures and programming techniques introduced in Computer Science 136, including induction, divide-and-conquer, dynamic programming, and greedy algorithms. Particular topics of study include graph theory, computational geometry, string processing, approximation algorithms, and advanced data structure. In addition, we will provide an introduction to complexity theory and the complexity classes P and NP.

Format: lectures. Evaluation will be based on problem sets and programming assignments, and midterm and final examination.

Fulfills the Quantitative Reasoning requirement

Prerequisites: Computer Science 136 and Discrete Mathematics.

Scheduled Offerings:

	Spring 09	256-01	(LEC)	MWF	11:00-11:50	Heeringa
	Spring 10	256-01	(LEC)	MWF	11:00-11:50	Raghavan