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.

A Note On Course Philosophy. The goal of this course is for you to learn broadly about CS theory and (ideally) to enjoy yourself while doing it. You should understand the ways in which the structure of the course supports this goal, and if it doesn't, you should intervene to make it better. To that end, you'll see a lot of rationale footnotes1 explaining why things are as they are.

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

SYLLABUS

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: Eumin Hong, Melody Hsu, Yunya Zhao.

    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.

Homework

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.
  • Lecture 0 [VIDEO] [VIDEO NOTES]
    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.
In the lefthand pane is a copy of my syllabus for an introductory computer science theory course offered to students in their second or third year of the computer science major. (COMS 3261: Computer Science Theory, taught at Columbia in Summer 2022.)

I like to begin with an introduction to computer science theory, which is often unfamiliar and intimidating to my students. What is this course about, and why should students care? I try to keep these questions in mind throughout the course.







Course evaluations are critical to my practice of reflection and improvement. I use a Google Form for custom questions.
In surveys, my students report that they prefer simple course webpages over the Learning Management System. I attempt to integrate my syllabus with web resources without getting overly complicated.


Omitted from this example: an embedded calendar widget, which tracks TA hours and one-time events like review sessions and take-home exams.












This course is highly cumulative and was taught on a compressed six-week summer schedule. Short, targeted, regular problem sets keep students from falling behind in their practice.


To some extent, this syllabus is already "annotated": I want students to know why the course is structured as it is (and to challenge the rules when they disagree with my reasoning).

Requiring students to provide a justification for late work by email ensures that most submit work on time while allowing me flexibility to give extensions. There is relative consensus that enforcing deadlines by docking grades does not support the goal of equitable grading [1], so I offer students who miss deadlines alternative opportunities to demonstrate mastery.
[1] Feldman, Joe. Grading for Equity: What It Is, Why It Matters, and How It Can Transform Schools and Classrooms. Corwin Press, 2018.
Take-home, open-book exams reduce time pressure and allow students to do their best work while stretching their abilities on harder problems. In post-class surveys, my students overwhelmingly report that a take-home final is more helpful for their learning than an in-class final.








I grade students using the maximum of two formulas to give them credit for their best work (both the final exam and problem sets are comprehensive.) I'm actively experimenting with summative evaluations and grading methods in order to accurately capture what my students know.

Minimum grading is an emerging practice in US higher education. The example given in bullet (2) demonstrates how it can affect student scores. Consider: which average grade is most likely to reflect what our hypothetical student knows? Which is more likely to motivate them to continue learning and putting effort into the course? The debate over minimum grading and other progressive practices is ongoing, but current research indicates minimum grading has little to no effect on grade inflation [2].
[2] Carey, Theodore, and James Carifio. "The minimum grading controversy: Results of a quantitative study of seven years of grading data from an urban high school." Educational Researcher 41.6 (2012): 201-208.










I prefer to post full solutions to help students make corrections, even though this practice requires rewriting problem sets.









The Course Skeleton provides a bird's eye view of what we've done in the class, along with when we covered it and the relevant course resources.


"Lightning Reviews" are videos that go over definitions and the basics of core concepts, while "Examples" are videos with worked versions of the core problems and skills that students may struggle with.








Short review videos are my compromise between not offering video content (thus making it harder for students to review and providing one fewer way to interact with the class) and posting full videos of class (which seems to hurt attendance, and later, student learning).