Computer Science Theory, Summer 2026

General Information

• Instructor: Xi Chen, Lectures: MW 10:10am--1:20pm, 702 Hamilton Hall
• Office hours: Friday 2:30pm--3:30pm in CSB 503 and Sunday 8:30pm--9:30pm on Zoom
• Textboook: Introduction to the Theory of Computation, Third Edition, by Michael Sipser, Cengage Learning, 2013
• Please follow this link to sign up on Piazza.
• Gradescope entry code: PKZ6VP.
• Lecture notes and homeworks are posted on the Lectures page.

Instructional Assistants

• Sofia Hirao, Email: ssh2204@columbia.edu, Office hours: Tuesday 4pm--5pm in CS Learning Center and Thursday 4pm--5pm on Zoom.
• Philip Kaelbling, Email: pak2154@columbia.edu, Office hours: Monday and Wednesday 8pm--9pm on Zoom.

Course Description

• In Computer Science Theory you will learn computational thinking and get to know the fundamental models of computation that underlie modern computer hardware, software, and programming languages. You will also discover that there are limits on how quickly computers can solve some problems and that there are some problems that no computer can solve.
• The course will cover the important formal languages in the Chomsky hierarchy -- the regular languages, the context-free languages, and the Turing recognizable / decidable languages -- as well as the formalisms that generate these languages and the machines that recognize them. The course will introduce the basic concepts of computability and complexity theory by focusing on the question, What are the fundamental capabilities and limitations of computers?
• Topics covered in Computer Science Theory are required background to many Computer Science upper division courses in programming languages, compilers, natural language processing, computer hardware and logic design, analysis of algorithms, computational complexity, learning theory, and cryptography.

Prerequisites

• COMS W3203 Discrete Mathematics

Grading

• Five problem assignments: 20%
• Quiz 1 on June 3: 20%
• Quiz 2 on June 17: 20%
• Final exam on July 1: 40%
• Quizzes and the final exam will all be held in person during class.

Homeworks

• Five problem sets will be assigned. They will be assigned here on Wednesday and due on next Monday at midnight. The aggregate score of these five assignments will constitute 20% of your final grade. Homeworks must be typed or legibly written and scanned (LaTeX is preferred but not required). Post your solutions on Gradescope before 11:59pm on the due date. Late assignments will not be accepted.