CSCI 361

CSCI 361 - Fall 2024

Theory of Computation

Home | Lectures | Assignments | Resources | CS@Williams

Home

Instructor:	Shikha Singh
Email:	ss32@williams.edu
GLOW page:	CSCI 361 GLOW
Office Hours:	Check the calendar below.

Lectures:	TR 8:30 am - 9:45 am (01) and TR 9:55 am - 11:10 am (02).
Classroom	Wachenheim 116
Textbook	Introduction to the Theory of Computation by Michael Sipser (3rd ed)

Course Description

This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free languages, and Turing machines. These models provide a mathematical basis for the study of computability theory. The class also explores important topics in complexity theory: hardness of problems and reductions and characterizations of time and space complexity classes.

Objectives. By the end of the course, the students should be able to:

reason about the power and limitations of computation through the use of abstract, formal models
reason about the hierarchy and power of important complexity classes
distinguish between problems that are tractable, intractable, and uncomputable
gain experience with mathematical problem solving and proof writing

Syllabus & Textbook

Course Syllabus

Primary Textbook: Introduction to the Theory of Computation by Michael Sipser (3rd edition).
Supplemental readings from other sources may be assigned on an ad hoc basis.

Readings can be found on the Lectures page.

Course calendar