Course Description

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata and regular languages; context-free languages; Turing machines and computability; NP-completeness and glimpses of computational complexity theory.

The primary goal of the course is to broaden the student's computer science education by adding a philosophical dimension, asking and answering such timeless questions as "what can and cannot be computed?" and "what makes some computational problems easy, others hard, and still others unsolvable?" By design, the ideas and techniques taught in this course are about aspects of computation so fundamental as to not depend upon changing trends in hardware of software technology.

This course has substantial mathematical content. It is expected that a student who enrols for this course already knows how to write mathematical proofs and is generally mathematically mature. If a student passes this basic criterion and is interested in thinking philosophically about what a computer can or cannot do, then this course should be great fun.

Administrative Information

Instructor

Amit Chakrabarti

Teaching Assistant

Omar Sharif

Boxian Wang

Zoom link

We may occasionally have a lecture, an x-hour, or an office hour held remotely, on Zoom. The relevant Zoom links are posted on the course's Canvas page.

Getting Help

Please use Ed Discussion

to ask any questions related to the course and do not use email unless there is a very good reason to avoid Ed Discussion.

Prerequisites

Either CS 30 or CS 31, or

a strong mathematics backround and permission of the instructor

Required Textbook

Michael Sipser.   Introduction to the Theory of Computation (third edition).

Suggested additional reading; not a required book

J. E. Hopcroft and J. D. Ullman.   Intro. to Automata Theory, Languages and Computation (2nd edition).

Work and Grading

Grading Scheme

Weekly homework (35%); Quizzes (14%); Midterm exam (20%); Final exam (27%); Participation (4%)

Homework and Exam Schedule

Seven homework sets, due Mondays at 10:00 pm

Quiz 1: In class; during an x-hour in early February

Quiz 2: In class; during an x-hour in late February

Midterm exam: Take home, with time limit

Final exam: Take home, with time limit