Welcome to Computer Science Theory
Mathematics teaches us to ask questions like `What is the value of f(x)?', `Do any objects of type Y exist?', and `Is Z true?' Theoretical computer science builds on this tradition, expanding our field of inquiry to include questions like `How much time (and other limited resources) does it take to evaluate f(x)?', `Can I write down formal instructions for finding a Y?', and `Can the truth of Z be computed?' In theoretical computer science, we define problems formally and think about how hard they are to solve under various models of computation.
Are you curious about the fundamental nature of computation? What makes some tasks `hard', and others `easy'? The mathematical tools theorists use to formally define concepts of security, privacy, and equity? This course may be for you. (Not convinced? Try Sipser's friendly argument in the preface of the textbook.)
The course is highly abstract: there will be no programming and problem sets will revolve around formal proofs. Students are expected to be comfortable with discrete mathematics and proofs. (For a refresher, see Chapter 0 of the textbook or the Lecture 0 recording, coming soon.)
Questions? Please email me at [first initial].[last name]@columbia.edu!
People. Instructor: Tim Randolph (twr2111). TAs: Eumin Hong (eh2890), Annie Sui (aqs2104), Quintus Kilbourn (qjk2000), Elena Gribelyuk (eg2995), and Brian Paick (bsp2121).
Dates and times. Monday and Wednesday during Summer B term, 10:10AM - 12:40PM EST. (Specifically: 6/28, 6/30, 7/7, 7/12, 7/14, 7/19, 7/21, 7/26, 7/28, 8/2, and 8/4.) See calendar.
Modality. There are three ways to attend:
- In-person class will be held in 417 International Affairs Building (here).
- Lectures will also be streamed live on Zoom with TA-moderated discussion. (see CourseWorks for Zoom links.)
- Lecture videos will be posted on the course YouTube channel 48 hours after class.
Resources & Quick Links.
- The text for the course is Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser.
- CourseWorks: Zoom links and passwords.
- Ed: Class question-and-answer forum.
- Gradescope: Submit assignments and exams and view grades here. The course code is X3JEX4.
- YouTube: Lecture recordings available here on the same day as class.
Enrollment. This is a 3-credit required course for the undergraduate CS program. The course requires Discrete Math (COMS W3203) as a prerequisite or instructor permission. The course number is W3261; the call number is 11381; the department is COMS; the (sub)term is Summer B 2021. My goal is to get every student who wants to attend into the course, even if this takes until the add/drop deadline. Please email me if you have enrollment concerns.
Office Hours. TA and instructor office hours can fill some of the void created by taking a course asynchronously, via livestream, or just in a large lecture hall. Please come to office hours, even if it's just to introduce yourself to me and/or the TAs! This will enhance your course experience. This semester, I'm offering several office hour blocks to accomodate students working from different time zones. Tim's office hours will be Tuesday 2:00PM-3:30PM EST (in-person), Thursday 6:30-8AM EST (virtual), Thursday 8:30-10AM (in-person) and Thursday 5:30-7:00PM EST (virtual). In-person hours will be held in my office, CSB 522, and virtual hours will be held on Zoom (see Courseworks/Zoom Class Sessions for links). (To access CSB 522, enter the CS department through Mudd, then walk down the hall and up the stairs.) TA hours coming soon, see calendar.
Livestream Etiquette. Feel free to ask questions during lecture! You can do this by unmuting or by posting the question in the chat; the TA monitoring Zoom will then bump it up to the instructor.
Homework. There will be six problem sets, each worth 12% of your grade. Each will have about six problems, be due on a Monday night at 11:59PM EST, and cover material up to and including the lecture of the previous Wednesday. Please anonymize your submission (no name, UNI, etc.) This helps us grade fairly; the solution is still linked to your Gradescope account. You're highly encouraged to write up your problem sets using LaTeX, a markup langauge for mathematics; the website Overleaf (essentially Google Docs for LaTeX) makes this easier.
Late work. You have a total of 3 late days for the semester. Late time is rounded up to the nearest day (cannot be subdivided) and is measured from submission time on Gradescope. Additional late days beyond the initial 3 will be penalized at a rate of 20% of the initial grade per late day. No homework will be accepted after 11:59PM EST on the Friday after the initial due date (4 days afterwards.) For exceptions to the above, please contact me through your academic adviser.
Regrade policy. To request a regrade, submit a detailed and clearly stated argument for what you believe is incorrect and why to Gradescope within 7 days after the assignment is returned. We'll respond within a week. Keep in mind that a regrade may lower the overall score and that regrades are final.
Exam. There will be one cumulative final exam worth 28% of your grade. You can take the exam remotely during any consecutive 12 hours within a certain 48-hour window (approximately concurrent with August 10 and 11).
Collaboration rules. For problem sets, you're welcome to use the textbook, your notes, and reference sources on the internet, and also to collaborate with your peers. You're encouraged to attend office hours to collaborate. However, you must write up your own solutions independently and cannot share written solutions or notes about problem sets. Please cite your collaborators and any external sources used.
The final exam will be open-book and open-note, but collaboration and internet use will not be allowed. Question-and-answer sites are prohibited for both homework and exams; posting or sourcing answers on the internet will result in a 0 on the assignment/test (at minimum). Students are also expected to adhere to the Columbia CS Academic Honesty Policy. Please contact the instructor or TAs with any questions.
Grading. 12% * 6 homeworks + 28% * 1 exam = 100%; possible extra credit.
Help make the course better! Submit anonymous feedback here.
Homework
- Problem Set 0 (Optional, no points) (PDF) (TEX)
- Problem Set 1 (Due 7/6/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Problem Set 2 (Due 7/12/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Problem Set 3 (Due 7/19/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Problem Set 4 (Due 7/26/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Problem Set 5 (Due 8/2/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Problem Set 6 (Due 8/9/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Final Exam (Due 8/11/21@11:59PM EST) (PDF) (TEX) (Solutions)
- Final Exam Topic Guide
Lectures
Lecture 0 [Video] [VIDEO NOTES]
Optional lecture: a quick review of discrete mathematics material. Sets, sequences, graphs, alphabets, strings, languages, boolean logic, proofs.
Reading: Preface: `To the Student' and `To the Educator.' Review Chapter 0 (pp. 1-25).
Lecture 1 (6/28) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Introduction to class. Alphabets, strings, and languages. Deterministic finite automata (DFAs), formal definition of computation and regular languages.
Reading: Chapter 1.1 (pp. 31-47). Syllabus (this website.)
Lecture 2 (6/30) [VIDEO (1) (2) (3)] [VIDEO NOTES (1) (2) (3)] [IN-CLASS NOTES]
Definition of regular languages. Regular languages are closed under union. Introduced Nondeterministic Finite Automata. Converting NFAs to DFAs, and the corollary result that regular languages are exactly those recognized by NFAs.
No class on 7/5 (University holiday.)
Lecture 3 (7/7) [VIDEO (1) (2) (3)] [VIDEO NOTES (1) (2) (3)] [IN-CLASS NOTES]
Proved that regular languages are closed under union, concatenation, and Kleene star using NFAs. Introduced regular expressions and showed that every language described by a regular expression is regular by reducing to an equivalent NFA.
Lecture 4 (7/12) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Showed that every regular language can be described by a regular expression using a new automaton called a Generalized NFA (GNFA). Thus the class of languages described by regular expressions is exactly the regular languages. Talked about nonregular languages and introduced the pumping lemma.
Lecture 5 (7/14) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
More practice with proving languages irregular using closure properties and the pumping lemma. Introduced context-free grammars and context-free languages. Defined derivations, parse trees and leftmost derivations.
Lecture 6 (7/19) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Review of context-free languages and definition of Chomsky Normal Form. The regular languages are a proper subset of the context-free languages. Introduction to pushdown automata and examples.
Lecture 7 (7/21) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Proof that a language is context-free if and only if some Pushdown Automaton recognizes it. The Pumping Lemma for context-free languages.
Lecture 8 (7/26) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Examples of the pumping lemma for context-free languages. Turing machines, Turing-recognizability and Turing-decidability.
Lecture 9 (7/28) [VIDEO (1) (2) (3)] [VIDEO NOTES (1) (2) (3)] [IN-CLASS NOTES]
Multitape TMS, Nondeterministic TMs, and enumerators. High-level descriptions and the Church-Turing thesis: from TMs to ``algorithms".
Lecture 10 (8/2) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Proving that many languages are decidable. The language A_{TM} is not decidable and its complement isn't even recognizable. A language is decidable if and only if it is Turing-recognizable and Co-Turing recognizable (so recognizability is not closed under complement.)
Lecture 11 (8/4) [VIDEO (1) (2)] [VIDEO NOTES (1) (2)] [IN-CLASS NOTES]
Turing reductions and proof that the halting problem is not decidable. The problem of determining whether a TM recognizes a regular language, or the empty language, is undecidable. Review of big-O and big-Omega notation and introduction to time complexity. The time complexity classes P and NP. (Is it true that P=NP?)