Description: This course introduces formal models of computation including finite automata, regular languages, context-free grammars, and Turing machines. These models provide a mathematical basis for the study of computability - the study of what problems can be solved and what problems cannot be solved. Applications to compiler design and program verification will also be covered.

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

Fulfills the Quantitative Reasoning requirement

Prerequisites: Computer Science 256 or both a 300-level mathematics course and permission of the instructor.

Scheduled Offerings:

	Fall 08	361-01	(LEC)	MWF	11:00-11:50	Heeringa
	Fall 09	361-01	(LEC)	MR	1:10-2:25	Raghavan