COMS W3261: Summer 2023

Please complete the Post-Course Feedback Form (Web Form)! Thank you!

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? Join us in studying the theory of computer science.

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?" We'll build 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 footnotes¹ explaining why things are as they are.

¹Like this.

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

Resources & Quick Links.

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: K3VK75). We probably won't use CourseWorks.

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

• Who, What, Where, When (click to expand/collapse)

People. Instructor: Tim Randolph (twr2111, t.randolph@columbia.edu). TAs: Charlie Heus (ch3593) and Larry Davis (lrd2139).

Dates and times. Monday and Wednesday during Summer A term, 1:00PM - 4:10PM EST: 5/22, 5/24, 5/31, 6/5, 6/7, 6/12, 6/14, 6/21, 6/23 (!), 6/26, and 6/28. (No class 5/29, and 6/19 which are Memorial Day and Juneteenth, respectively. Note that we'll have class on Friday, June 23, which is the make-up day for Juneteenth.) The take-home final exam will be held sometime within the range 6/29-7/2. The add/drop deadline is Friday, 5/26. See calendar.

Locations. Class is held in Schermerhorn 614. 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. If stranded at the CS department door, text me at the number listed in my email signature.)

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/Wednesday 10:00-11:45am EST in-person in the CS lounge, 5:30pm-6:30pm on Wednesdays and occasional Sundays via Zoom. See calendar for details/adjustments. Charlie and Larry (TAs): see calendar.

Please come to office hours at least once, even if only to introduce yourself! If you can't make office hours, email me to set up another time.

• Assignments and Grading (click to expand/collapse)

Homework. There will be five problem sets. 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.)²

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.

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?)

¹The rapid turnaround time isn't intended to be punishing: it's designed to keep you on top of a fast-moving, cumulative course and to let us give you feedback in reasonable time.
²This helps us grade fairly; the solution is still linked to your Gradescope account.
³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.

Late work. You have a total of 5 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 Friday 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.

Regrades. To request a regrade, submit clear and detailed argument explaining why you think the grade is incorrect 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).

Accommodations. Assignments and tests are asynchronous/remote to give you the time and space to do them in the way that best meets your needs. If you're concerned about an assignment or the lectures, if additional resources would help, if you encounter a personal emergency, or for other assistance, contact the course staff.

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 to solve homework problems. 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). You're also expected to adhere to the Honor Code and the Columbia CS Academic Honesty Policy.

Grading. Your grade will be the maximum of two formulas:¹
   1) 15% * 5 homeworks + 25% * 1 exam = 100%.
   2) 8% * HW1 + 10% * HW2 + 12% * HW3 + 14% * HW4 + 16% * HW5 + 40% * 1 exam = 100% .

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.
Grading procedures are subject to amendment based on a class discussion early in the semester.

¹Formula 1 is intended to reward consistent hard work on problem sets, and downweight the exam; Formula 2 is designed to reward you for persistent improvement over the course of the term.

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 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).

Help make the course better! Submit anonymous feedback here.