This is a three-credit required course for the undergraduate CS program. The course requires Discrete Math (COMS W3203) as a prerequisite, or the instructor's permission.
Lectures will take place on Tuesdays 8:40-9:55am, and on Thursdays 10:10-11:25am (see zoom links on courseworks). Everyone is required to either attend lecture, or go through the recording within the next day (or any combination).
We will use the Piazza discussion board . Use this to ask questions about course material, logistics, and schedule.
Homework and quizzes will be administered through Gradescope (questions about grading should be submitted on gradescope).
Class recordings, lecture notes, homework solutions, and other supplementary files, will be posted on Courseworks.
The contact information for the teaching staff is below. You may reach us either by posting a private question on piazza (goes to all staff), or by emailing the instructor and head TA, as appropriate.
This course is an introduction to models of computation, computability, and complexity. We will ask questions like: How do we define the abstract notion of "computation" or a "computer"? What problems can be computed? What problems can be computed efficiently? Can we prove that some problems can never be computed, no matter how fast our computers become? The course is highly mathematical and abstract; in particular, there will be minimal programming assignments (if any) and homework problems will frequently involve proving or disproving various assertions. Students are expected to be comfortable with the material covered in Discrete Math (W3203) or the equivalent.
Topics (not exhaustive): automata and the languages they define, context-free grammars and the languages they define, Turing machines, basic complexity theory (such as P vs. NP).
For each quiz that you submit, your score will automatically be increased by 25% of the total point value, up to a 100% ceiling. For example, on a quiz with a maximum of 10 points, a score of 2 will be converted to 4.5, a score of 6.5 will be converted to 9, and scores of 7.5 and above will all be converted to 10. A quiz that is not submitted gets a score of 0. The lowest quiz score will be dropped.
You must take the quiz alone, without discussion with anyone else (although you are welcome to go over lecture material with other students). You don't have to finish the quiz in a single pass - you could submit part of it, and then go back and complete the rest (as long as it's before the deadline, and you do it on your own without any discussion with others). You are allowed to use your class notes/ textbook when taking the quiz, although the intention is that the quiz should be solvable without any materials (after you have gone over the previous lectures and digested them). No late quizzes will be accepted.
The quiz is meant to be easier than homework problems, and meant to be completed quickly - within at most 15 minutes if you've already gone over and understood the class material to date. If you find yourself working much longer, contact us and come to office hours (sooner rather than later).
See below for our policies on lateness, collaboration, etc (quick summary: you have some budget of late hours, you are allowed some limited and clearly acknowledged discussion on homework, you should not cheat, we won't tolerate it).
The final grade is determined by quizzes (10%), homework (20%), and four exams (70%) (see more information about quiz grading above). The worst quiz of each student will be dropped, and the worst homework of each student will get half the weight (namely, half of the worst homework will be dropped). Being able to solve the quizzes and homework is crucial for understanding and getting comfortable with the material - it is unlikely you will do well on the exams otherwise. Each of the exams will test one unit of the class, and will be weighted roughly according to how many lectures are covered by this topic (the exact weighting will be announced). There is no cumulative exam (although the material in general builds on earlier material).There will be 3 exams for the class, and their relative weight is determined by the number of lectures they each cover (9,9,3, respectively). The exams will be given through gradescope, and timed at 75 minutes (you will also get an extra 15 minute grace period to upload your solutions), over a window of at least 24 hours. It is open notes and textbook, but no other resources (in particular, no internet resources are permitted). All work you submit must be your own.
Late quizzes will not be accepted. For homework, we allow up to 120 hours of lateness with no penalty throughout the semester, provided you use at most 48 hours for any one homework. Any part of an hour (e.g., a minute) counts as a full hour. This lateness time is provided to allow for last minute upload/internet problems, or in case you're busy with another project, observing a religious holiday, have a minor sickness or another issue.
Any homework that is late beyond the 120 hours total or 48 hours per one assignment will not be accepted.
In some cases the above lateness policy may be canceled, and no late homework will be accepted for a certain homework (e.g., before a test). You will be notified of any such case when the homework is given out.
For other emergenices (e.g., a serious family or medical emergency), please provide all necessary documentation to your advising dean, and have the dean contact me to discuss appropriate accommodations. This maintains your privacy, and saves me from having to evaluate and verify your doctor's note or family situation.
All students are assumed to be aware of the computer science department academic honesty policy .
For quizzes and exams, no collaboration is allowed.
For homework, collaboration in groups of two or three students is allowed, but not required (and for most students, I would not encourage it in this class). Collaboration in groups of more than three students is not allowed. If you do collaborate, you must write your own solution (without looking at anybody else's solutions), and list the names of anyone with whom you have discussed the problems. If you use a source other than the textbook in doing your assignment, explain the material from the source in your own words and acknowledge the source. In any case, you are not allowed to look at written solutions of any other student, even if you worked on solving the homework together. Collaboration without acknowledgment is considered cheating. Obviously, you are also not allowed to look at solutions from other classes, other institutions, previous years, and so on. If you are in doubt, ask the professor. Homework should constitute your own work.
Every student caught cheating will be referred to Colubmia's office of Student Conduct and Community Standards, as well as subject to academic penalty in the class.
Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. Copies are currently available at the Columbia bookstore. The book's website and errata are available here. We will generally follow the book in class, but some departures are possible. Students are responsible for all material taught in class.
Optional text: Introduction to Automata Theory, Languages and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman
CS 3261 constitutes the last CS Theory course required to be taken by all CS majors. Students interested in the material covered by this coure are strongly encouraged to pursue some of the advanced courses offered in theoretical computer science. In particular, the following courses are very closely related in spirit to the topics covered in CS 3261:
In addition, the following courses (and quite a few others!) benefit from and relate to some of the topics covered by our course: