The prerequisite for this course is CS 330, Introduction to Analysis of Algorithms. If you have not yet taken that course, you should at least be taking it concurrently.
This course provides the answer to three questions about the nature of computation.
Course textbook Introduction to the Theory of Computation, by Michael Sipser. Get the second edition, because it will be cheaper. Buy it used or borrow from a friend.
Unless otherwise specified, bring homework to lecture on the day it is due. If you are unable to bring it to lecture, please place it in the Computer Science department homework drop box for CS 332.
Models of computation and computability theory.
Covers entire course, but focuses on complexity theory.
You are welcome to attend any office hours listed below that are convenient for you.
If you would like to meet us outside of these times, please contact us.
Work together as much as possible, as often as possible, with as many people as possible. Explain things to each other. However, when you write your homework, write it in your own words! Also, you must list your collaborators at the top of your homework.
You all know how to perform a web search. If you look hard enough, you can probably find solutions to some of the problems given in the homework assignments. I urge you to not do this; give the problem an honest half hour, then ask for help from the instructor, the teaching fellow, or other students. If you must consult an external source as a guide, you must cite your sources.
If you do not list your collaborators and cite your sources, you are knowingly submitting another's work as your own and are committing plagiarism. I will report plagiarism to the Dean. Please review Boston University's Academic Conduct Code. (I also know how to perform a web search, so keep that in mind if you are using a web source as a guide. In general, you are always better off submitting a blank solution then a plagiarized one.)
Attendance will not be recorded or graded. Attend the lectures if and only if you find them helpful and will be awake and alert.
You are allowed three and only three late homework submissions throughout the semester. A late submission is accepted with no penalty until the beginning of the following lecture. No submissions will be accepted beyond that time. Specifically, if the homework is due on Tuesday, you may submit it on the following Thursday, and if the homework is due on Thursday, you may submit it on the following Tuesday.
Each homework and each exam will be graded according to the following (linear) scale. If m is the maximum raw score earned by any student, and you earn a raw score of g, your scaled score becomes (g / m). If m = 0, everyone gets a 0. If everyone colludes to keep m low, I will give everyone a low score.
After the scaling described above, your total homework points, total midterm exam points, and total final exam points will count towards your final course grade in the following amounts.
If you need additional tutoring,