COMS W3261: Summer 2021

This is the course page for the course offered Summer 2021. For the Summer 2022 course page, click here.

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.

Lecture attendance and participation is highly encouraged (but not strictly required.)

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.

Related courses and links