Computer Science Theory, Spring 2023

General Information

Instructor: Xi Chen, Lectures: MW 8:40-9:55am, 451 CSB; MW 10:10-11:25am, 451 CSB; MW 1:10-2:25pm, 501 Northwest Corner Building
Lectures will be streamed live on zoom and recorded; links can be found on Courseworks.
Office hours: Tuesday, Wednesday and Thursday 9-10pm on Zoom; see the google calendar below for the link.
Textboook: Introduction to the Theory of Computation, Third Edition, by Michael Sipser, Cengage Learning, 2013
Please follow this link to sign up on Piazza.
Lecture notes and homeworks are posted on the Lectures page.

Instructional Assistants

Google calendar of all office hours
Ryan Anselm, Email: raa2218@columbia.edu
Haozhe Chen, Email: hc3295@columbia.edu
Alice Chen, Email: yc3877@columbia.edu
Helen Chu, Email: hc2932@columbia.edu
Leyi Cui, Email: lc3542@barnard.edu
Yiming Fang, Email: yf2484@columbia.edu
Eumin Hong, Email: eh2890@columbia.edu
Nicolas Hortiguera, Email: nh2648@columbia.edu
Ziheng Huang, Email: zh2556@columbia.edu
Daniel Joo, Email: dsj2122@columbia.edu
Heeyun Kim, Email: hk3187@columbia.edu
Asa Kosto, Email: atk2142@columbia.edu
Alexander Lindenbaum, Email: al4008@columbia.edu
Leonidas Pappajohn, Email: lgp2116@columbia.edu
Alan Zhao, Email: asz2115@columbia.edu
Yunya Zhao, Email: yz3754@columbia.edu

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%, best four out of five (see below)
Midterm evaluation 40%
Final evaluation 40%
Midterm and final evaluations will be held on March 8 and May 1.

Homeworks

Five problem sets will be assigned during the semester. They will be assigned here. Each problem set is worth 100 points and only the four best of your five problem sets will be counted. The aggregate score of these four 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.
Since only four out of five assignments will be counted, this policy will allow you to skip one problem set for whatever reason you choose. Late assignments will not be accepted. In the case of a serious medical or family emergency, please provide necessary documentation to your advising dean and have the dean contact the instructor to discuss appropriate accommodations.
You are expected to adhere to the Academic Honesty Policy of the Department of Computer Science. You are not allowed to use the Internet for homeworks. You can consult the instructor and the TAs or collaborate with your fellow students, but you must acknowledge these sources by listing names of TAs and / or students you collaborate with at the beginning of each problem. Collaboration without acknowledgment is considered cheating. Erase records (whiteboard pictures or your own notes, etc) at the end of a group discussion so that you can write solutions in your own words by yourself.
Every student caught cheating will be referred to Colubmia's office of Student Conduct and Community Standards, as well as subject to academic penalty in the class.