Instructor Jeffrey Finkelstein (room PSY 224), primary teaching fellow Oxana Poburinnaya (room PSY 223), secondary teaching fellow Maryam Ghasemi (room PSY 223).

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.

Schedule of lectures

  1. Mathematical definitions
    • Lecture   0  Sets, sequences, functions (Chapter 0)
    • Lecture   0  Alphabets, strings, and languages (Chapter 0)
  2. Models of computation
    • Lecture   1  What is an algorithm?
    • Lecture   2  What is a computer?
    • Lecture   3  The Turing machine model (Section 3.1)
    • Lecture   4  The Turing machine model (continued)
    • Lecture   5  Simulations (Section 3.2)
    • Lecture   6  Simulations (continued)
    • Lecture   7  The Church–Turing Thesis (Section 3.3)
  3. Computability
    • Lecture   8  Countable sets (Section 4.2)
    • Lecture   9  Uncountable sets (Section 4.2)
    • Lecture 10  The halting problem (Section 4.2)
    • Lecture 11  Decidability
    • Lecture 12  Reducibility (Section 5.1)
    • Lecture 13  Many-one reductions (Section 5.3)
    • Lecture 14  Kolmogorov complexity (Section 6.4)
  4. Midterm exam
  5. Complexity
    • Lecture 15  Time complexity (Section 7.1)
    • Lecture 16  Polynomial time (Section 7.2)
    • Lecture 17  Nondeterministic polynomial time (Section 7.3)
    • Lecture 18  Reductions (Section 7.4)
    • Lecture 19  NP-completeness (Section 7.4)
      Proof that Circuit Satisfiability is NP-complete (from Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein).
    • Lecture 20  Alternation and polynomial hierarchy (Section 10.3)
    • Lecture 21  Space complexity (Section 8.1)
    • Lecture 22  Polynomial space (Section 8.3)
    • Lecture 23  Sequential versus parallel computation (Section 10.5)
    • Lecture 24  Finite automata (Sections 1.1 and 1.2)
    • Lecture 25  Regular expressions (Section 1.3)
    • Lecture 26  Pumping Lemma (Section 1.4)
    • Lecture 27  Context-free grammars (Section 2.1)
    • Lecture 28  Pushdown automata (Section 2.2)
  6. Final exam

Homework

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.

Additional exercises

Exams

Lecture, discussion section, and office hours

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.

Monday
Prof. Homer's office hour in MCS 281
Oxana's office hours in PSY 223
Tuesday
Jeffrey's office hours in EMA 302
Maryam's office hours in PSY 223
Lecture in PSY B39
Wednesday

Oxana's office hours in PSY 223

Jeffrey's office hours in EMA 302
Prof. Homer's office hour in MCS 281
Discussion in MCS B31
Thursday
Prof. Homer's office hour in MCS 281
Maryam's office hours in PSY 223
Lecture in PSY B39

Collaboration

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.)

Grading (updated )

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.

Additional help

If you need additional tutoring,