This is a three-credit required course for the undergraduate CS program. The course requires Discrete Math (COMS W3203) as a prerequisite (see prerequisite resources below).
Lectures for Section 001 will take place TR 8:40am-9:55am in 451 CSB
Lectures for Section 002 will take place TR 10:10am-11:25am in 451 CSB
The two sections share the same gradescope and edstem pages (both linkable through the courseowrks page for the class). The class is typically not recorded, but the notes from class (as well as homework solutions) will be posted on courseworks.Office hours: The full schedule can be found in the course calendar:
Note the different locations for different office hours! In-person office hour locations include: CS TA room on 1st floor Mudd, CSB 5th floor lounge, Milstein 502 in Barnard, and 514 CSB for Prof. Malkin. There is one TA who will be holding office hours over zoom, and occasionally other TAs or the professor may also do that. Make sure to check the calendar (including location/modality) before showing up for office hours.
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).
You will always have at least 24 hours for each quiz.
See below for our policies on lateness, collaboration, regrade requests 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).
You will always have at least a week for each full homework (there will also likely be up to two half-sized homeworks before exams).
In particular, if a TA (or the professor) tell a student something, even if they accidentally make a mistake in their reasoning, the student is still responsible for catching that (at least if they are going to write something based on it), by fully understanding the problem and solution. We will also not look at your solution in advance to tell you if it is correct or not. Instead, we will try to help you figure out where there is a gap in your understanding, and why you are not confident about your solution (regardless of whether or not it is correct), towards helping you understand the material and do better.
To receive disability-related academic accommodations for this course, students must first be registered with their school's Disability Services (DS) office. Detailed information is available online for both the Columbia and Barnard registration processes. Refer to the appropriate website for information regarding deadlines, disability documentation requirements, and drop-in hours(Columbia)/intake session (Barnard). For this course, students registered with the Columbia DS should refer to the DS Testing Accommodations page for more information about accessing exam accommodations.
The final grade is determined by quizzes (10%), homework (20%), and two exams (70%) 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.
There will be two exams, in class:
We will grade answers both for correctness and clarity. We grade what you wrote, not what you meant. If you submit more than one solution to a problem, we will grade whichever solution we want (we may choose the worst one or the one that is easiest to grade). If you write "I do not know how to solve this" on a homework or exam problem, you will get 15% of the points for that problem.
We will accept regrade requests for assignments on Gradescope up to one week after grades are released. Please read the published solutions and the rubric before submitting a regrade request. To submit a regrade request on Gradescope, click on the question and click "Request Regrade", then write a few sentences explaining why you think your answer is correct. When we receive a regrade request, if we realize that we made a mistake in applying the rubric, we will correct the mistake. Note that this may result in the grade going down (or up, or no change).
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. 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. 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