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 MW 8:40am-9:55am in 501 NWC
Lectures for Section 002 will take place MW 10:10am-11:25am in 501 NWC
The two sections share the same gradescope and edstem pages (both linkable through courseowrks).Office hours: The full schedule can be found in the course calendar:
Note the different locations for different office hours! (CS TA room in 1st floor Mudd, Milstein 502 in Barnard, CSB 488 through 4th floor Mudd, and 514 CSB for Prof. Malkin).
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.
The final grade is determined by quizzes (10%), homework (20%), and two 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.
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).
There will be two exams, in class:
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. 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