Welcome to Computer Science Theory

Are you curious about the fundamental nature of computation? What makes some problems hard, and others easy? The formal concepts required to think abstractly about what computers can do, including topics in programming languages, cryptography, security, software engineering, economics and many more? Computer science theory may be for you.

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 the scope of inquiry to include questions like "How much time (and other limited resources) does it take to evaluate f(x)?", "Can I formally specify a procedure for finding a Y?", and "Can the truth of Z be computed?"

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.

Questions? Please email me at t.randolph@columbia.edu!


Resources & Quick Links.

Course evaluations. There are two course evaluations for this course: the standard evaluation, available on Courseworks, and a supplemental evalation specific to this course. Please fill out both! I'll read your feedback carefully and use it to improve the course.

The text for the course is Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser.

The question-and-answer forum for this class is hosted on Ed. For homework, exams, and grades we'll use Gradescope (course code: 2KGDW8). We probably won't use CourseWorks.

Supplemental explanations and examples will be posted on the course YouTube channel.

For HW template files, notes from TA office hours, and other useful tidbits, check out the TA-run Github repo.

  • Who, What, Where, When (click to expand/collapse)
  • People. Instructor: Tim Randolph (twr2111, t.randolph@columbia.edu). TAs: To be announced.

    Dates and times. Tuesday and Thursday during Summer A term, 1:00PM - 4:10PM EST: 5/24, 5/26, 5/31, 6/2, 6/7, 6/9, 6/14, 6/16, 6/21, 6/23, and 6/28. The take-home final exam will be held within the range 6/29-7/1. See calendar.

    Locations. Lecture location is 428 Pupin. My office hours will be held in the CS Lounge, or in my office (CSB 522) if lounge space isn't available. (To reach CSB 522, enter Mudd at the 4F campus level and go into the CS department. Go down the hallway, past the CS lounge, and climb the stairs at the end.)

    Enrollment details. This is a 3-credit required course for the CS major. COMS W3203 Discrete Math (or instructor permission) is a prerequisite. My goal is to enroll every student who wants to participate in the course. Please email me if you have enrollment concerns.
    Course number: COMS W3261. Call number: 10332. Catalog; Vergil.

    Office and TA Hours. Tim: Monday/Tuesday 9-10:30am EST in-person, Thursday 5:30-6:30pm EST on Zoom. See calendar for details/adjustments. Please come to office hours at least once, even if it's just to introduce yourself! Eumin, Melody and Yunya (TAs): see calendar.

  • Assignments and Grading (click to expand/collapse)
  • Homework. There will be five problem sets. Each will have about six problems, be due on a Tuesday night at 11:59PM EST, and cover material up to and including the lecture of the previous Thursday. The rapid turnaround time is intended to keep you on top of a fast-moving and cumulative course without large, delayed assignments.

    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. Here's a quick tutorial. Why bother with LaTeX? (1) It's a handy language used by almost all people who write up math and science. (2) It may be required in future courses. (3) It gets increasingly convenient as the equation you want to typeset gets more complex.

    The goal of the homework is to practice using the mathematical machines, proofs, and concepts you'll use in this course and beyond. It's intended to be challenging and complex without being frustrating or confusing. To that end, the homework is annotated with a rationale (why are we doing this?) and references (if the question is baffling, where should we look for help?)

    Late work. You have a total of 3 late days for the course. Late time is rounded up to the nearest day (cannot be subdivided) and is measured from submission time on Gradescope. No homework will be accepted after 11:59PM EST on the Saturday after the initial due date (4 days afterwards); this rule exists so that we can share homework solutions.

    If you need an emergency exception to the late work policy, please email me before the due date with your reason(s) and a new proposed due date, which should be before Friday at 11:59 pm. I'm happy to discuss accommodations.

    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. You can take the exam remotely during any consecutive 12 hours within a certain 48-hour window (likely 6/30-7/1).

    Resource and collaboration rules for assignments. For problem sets, you're welcome to refer to (1) the textbook, (2) your notes, and (3) course materials (videos, ed posts, and anything else linked on this page). You can cite results proved or stated in class or on previous homeworks, but please don't cite results from the internet or later in the textbook without independent proof. (For example, a theorem from a later chapter might make a homework question trivial; don't cite this, as it defeats the point of the question.)

    You're welcome to collaborate with your peers on problem sets, in office hours or elsewhere. However, you must write up your own solutions independently. Please also don't share written solutions, and cite your collaborators.

    Contact the course staff if you're unsure whether a resource or collaboration is allowed, or if you need accommodation! We don't want to adjudicate after the fact.

    Academic Honesty Violations. Distributing written solutions, using question-and-answer sites (StackExchange, Chegg, etc.) to solve homework problems, and posting or sourcing answers on the internet will result in a 0 on the assignment (at minimum). Students are also expected to adhere to the Honor Code and the Columbia CS Academic Honesty Policy. Please contact the instructor or TAs with any questions.

    Grading. Grades will be calculated using the maximum of the following two formulas. The first is intended to reward consistent hard work on problem sets, and the second is intended to reward persistence and improvement.

    Formula 1: 15% * 5 homeworks + 25% * 1 exam = 100% (+ possible extra credit).
    Formula 2: 8% * HW1 + 10% * HW2 + 12% * HW3 + 14% * HW4 + 16% * HW5 + 40% * 1 exam = 100% (+ possible extra credit).

    Percentages to letter grades will be calculated as follows: 60.0-69.9%: D; 70.0-72.9%: C-, 73.0-76.9%: C, 77.0-79.9%: C+, 80.0-82.9%: B-, 83.0-86.9%: B, 87.0-89.9%: B+, 90.0-92.9%: A-, 93.0+%: A; threshold for A+ TBD based on extra credit distribution and extraordinary effort.

    Missing and severely deficient work. This class has three policies intended to correct grade discrepancies resulting from missing or severely deficient work:

    1. 1. A 50% grade floor. This is better thought of as a translation + rescaling of the grade range (50-100%) to five equal quintiles than "free half-credit".
    2. 2. Missing work calculated with respect to other problem sets: A missing problem set will be given a grade of (average of other problem sets) - 25%, calculated at the end of the term. For example, a student who recieves a 90% on 4 submitted assignments and does not submit 1 assignment would recieve a total HW grade of (90+90+90+90+(90-25))/5 = 85% rather than a (90+90+90+90+0)/5 = 72%.
    3. 3. I'll reach out to any student who misses a problem set or submits mostly deficient work to schedule a time to chat about the problem set. This may feel like a reward or a penalty depending on your perspective.
    4. Note that missing work will still significantly hurt your grade (I trust you to do the math yourself.)

Help make the course better! Submit anonymous feedback here.



A homework template and copies of the HW files can be downloaded from the TA-run Github repo. Submit to Gradescope (course code: 2KGDW8). Don't forget to anonymize your submission!

Course Content

Course evaluations. There are two course evaluations for this course: the standard evaluation, available on Courseworks, and a supplemental evalation specific to this course. Please fill out both! I'll read your feedback carefully and use it to improve the course.

The Course Skeleton contains a bulleted summary of everything we've covered this summer. It's designed as a place to help you start studying and organize your thoughts, but it is not a substitute for notes! Spot an erratum in the homework or solutions? Please post on Ed.
    1. Summary. A 30-minute review of discrete mathematics material. We introduce sets, sequences, graphs, alphabets, strings, languages, boolean logic, and proofs.
    2. Resources. Sipser 0.2, 0.3, and 0.4, pp. 3-25.
    3. Just for fun. Sipser, Preface: "To the Student" and "To the Educator".
  • Lecture 1 (See course skeleton for outline) [NOTES]
  • Lightning Review 1: Strings, Languages, DFAs [VIDEO] [NOTES]
  • Example 1: Designing and Building a DFA [VIDEO] [NOTES]
  • Lecture 2 (See course skeleton for outline) [NOTES]
  • Lightning Review 2: NFAs [VIDEO] [NOTES]
  • Bonus Review 1: Epsilon Transitions [VIDEO] [NOTES]
  • Bonus Review 2: Proving Regularity Using Closure Properties [VIDEO] [NOTES]
  • Lecture 3 (See course skeleton for outline) [NOTES] [Kahoot: DFAs/NFAs]
  • Example 2: Converting NFAs to DFAs [VIDEO] [NOTES]
  • Lightning Review 3: Regular Expressions [VIDEO] [NOTES]
  • Lecture 4 (See course skeleton for outline) [NOTES]
  • Example 3: From DFA to GNFA to Regular Expression [VIDEO] [NOTES]
  • Lightning Review 4: The Pumping Lemma [VIDEO] [NOTES]
  • Lecture 5 (See course skeleton for outline) [NOTES]
  • Example 4: Proving Nonregularity Using the Pumping Lemma [VIDEO] [NOTES]
  • Lightning Review 5: Context-Free Grammars [VIDEO] [NOTES]
  • Lecture 6 (See course skeleton for outline) [NOTES] [Kahoot: CFGs]
  • Lightning Review 6: Pushdown Automata [VIDEO] [NOTES]
  • Lecture 7 (See course skeleton for outline) [NOTES]
  • Example 5: Using the Context-Free Pumping Lemma [VIDEO] [NOTES]
  • Lightning Review 7: Turing Machines [VIDEO] [NOTES]
  • Lecture 8 (See course skeleton for outline) [NOTES]
  • Example 7: Proving Decidability and Recognizability [VIDEO] [NOTES]
  • Lecture 9 (See course skeleton for outline) [NOTES]
  • Example 6: Reducing Variant TMs to TMs [VIDEO] [NOTES]
  • Lightning Review 8: Proving Undecidability via Paradox [VIDEO] [NOTES]
  • Lecture 10 (See course skeleton for outline) [NOTES]
  • Example 8: Proving Undecidability and Unrecognizability via Reduction [VIDEO] [NOTES]
  • Lecture 11 (See course skeleton for outline) [NOTES]
Video lectures from Summer 2021 are available on last summer's course page. These are not required viewing and the content may not match up exactly.