| Instructor: | Mark Bun, mbun [at] bu [dot] edu | |
| Instr. Office Hours: | Mon 5:00-6:00 PM (MCS 114) | |
| Fri 5:00-6:00 PM (MCS 114) | ||
| Teaching Fellow: | Islam Faisal, islam [at] bu [dot] edu | |
| TF Office Hours: | Tue 5:00-6:00 PM (MCS B21) | |
| Thu 4:00-5:00 PM (MCS B21) | ||
| Class Times: | Tue, Thu 2:00-3:15 PM (EPC 209) | |
| Discussion Sections: | Wed 11:15-12:05 AM (MCS B31) | |
| Wed 12:20-1:10 PM (KCB 104) |
Course Website: https://cs-people.bu.edu/mbun/courses/332_F21. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.
Piazza: https://piazza.com/bu/fall2021/cs332. All class announcements will be made through Piazza, so please set your notifications appropriately. Please post questions about the course material to Piazza instead of emailing the course staff directly. It is likely that other students will have the same questions as you and may be able to provide answers in a more timely fashion. Active participation on Piazza may add extra points to your participation grade.
Gradescope: https://gradescope.com. Sign up for a student account on Gradescope using your BU email address. The entry code for the course is 2RYZ3P. Homework assignments are to be submitted to Gradescope in PDF format.
The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church's thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems.
CS 131 (Combinatoric Structures) and CS 330 (Introduction to Algorithms). If you have not completed the prerequisites for the course, please schedule a meeting with me before registering.
| Date | Topics | Reading/Reference | Handouts/Assignments |
|---|---|---|---|
| Thu 9/2 | Welcome, introduction | Sipser 0, Lec01, Lec01-ann | Collaboration and Honesty Policy, Math & Algorithms Review, HW0 out |
| Tue 9/7 | Sets, strings, and languages | Sipser 0, Lec02, Lec02-ann | L2 polls, HW 0 due, HW1 out |
| Thu 9/9 | Finite automata | Sipser 1.1-1.2, Lec03, Lec03-ann | L3 polls, Automata Tutor |
| Tue 9/14 | DFA-NFA equivalence, regular operations | Sipser 1.2, Lec04, Lec04-ann | L4 polls, HW 1 due, HW2 out |
| Thu 9/16 | Closure properties, regular expressions | Sipser 1.2-1.3, Lec05, Lec05-ann | L5 polls |
| Tue 9/21 | Regular expressions vs. FAs, distinguishable sets | Sipser 1.3, Lec06, Lec06-ann, Myhill-Nerode | L6 polls, HW 2 due, HW3 out |
| Thu 9/23 | Non-regular languages | Lec07, Lec07-ann, Myhill-Nerode | L7 polls |
| Tue 9/28 | Test 1 Review | Lec08 (no annotations) | No polls, HW 3 due |
| Thu 9/30 | Test 1 (in-class portion) | ||
| Tue 10/5 | Turing machines | Sipser 3.1, 3.3, Lec09, Lec09-ann | L9 polls, TM simulator, A real TM, Test 1 due (take-home portion), HW4 out |
| Thu 10/7 | TM variants and examples | Sipser 3.2, Lec10, Lec10-ann | L10 polls |
| Tue 10/12 | NO CLASS — Indigenous Peoples' Day (Monday schedule of classes) | HW 4 due, HW5 out | |
| Thu 10/14 | Closure properties, nondeterminism, Church-Turing thesis | Sipser 3.2, Lec11, Lec11-ann | L11 polls |
| Tue 10/19 | Decidable languages, Universal TM | Sipser 4.1, Lec12, Lec12-ann | L12 polls, HW 5 due, HW6 out, universal_TM.py |
| Thu 10/21 | Diagonalization, undecidability, unrecognizability | Sipser 4.2, Lec13, Lec13-ann | L13 polls |
| Tue 10/26 | More undecidability, reductions | Sipser 4.2, 5.1, Lec14, Lec14-ann | L14 polls, HW 6 due, HW7 out |
| Thu 10/28 | More reductions | Sipser 5.1, Lec15, Lec15-ann | L15 polls |
| Tue 11/2 | Test 2 Review | Lec16, Lec16-ann | HW 7 due |
| Thu 11/4 | Test 2 (in-class portion) | ||
| Tue 11/9 | Mapping Reductions | Sipser 5.3, Lec17, Lec17-ann | L17 polls, Test 2 (take-home portion) due, HW8 out |
| Thu 11/11 | Time complexity, space complexity | Sipser 7.1, 8.0, Lec18, Lec18-ann | L18 polls |
| Tue 11/16 | Hierarchy theorems, complexity class P | Sipser 9.1, 7.2, Lec19, Lec19-ann | L19 polls, HW 8 due, HW9 out |
| Thu 11/18 | More P, nondeterminsitic time, NP | Sipser 7.2-7.3, Lec20, Lec20-ann | L20 polls |
| Tue 11/23 | More on NP | Sipser 7.3-7.4, Lec21, Lec21-ann | L21 polls, HW 9 due |
| Thu 11/25 | NO CLASS — Happy Thanksgiving! | ||
| Tue 11/30 | NP-completeness | Sipser 7.4-7.5, Lec22, Lec22-ann | L22 polls, HW10 out |
| Thu 12/2 | More NP-completeness | Sipser 7.4-7.5, Lec23, Lec23-ann | L23 polls |
| Tue 12/7 | PSPACE, PSPACE-completeness | Sipser 8.1-8.2, Lec24, Lec24-ann | L24 polls |
| Thu 12/9 | Course Wrap-Up and Final Review | Lec25, Lec25-ann | HW 10 due |
| Wed 12/15 | Final Exam (in-class portion), 3-5 EPC 209 | Final exam (take-home portion) due |
Reading the textbook before class and reviewing it after class are important for solidifying your understanding of the course material. However, I do not want the exhorbitant price of the book to pose a barrier to your learning. Using an older edition of the text is fine (though beware that section numbers may be different). If the cost of the textbook still presents a burden for you, let me know and I can loan you a copy or recommend another solution.
Proof Techniques:
Richard Hammack, Book of Proof. Available online here.
Automata and Computability Theory:
Dexter Kozen, Automata and Computability.
Complexity Theory:
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.
Cristopher Moore and Stephan Mertens, The Nature of Computation.
There will be weekly homework assignments to be submitted on Gradescope most Tuesdays at 11:59PM. No late homework will be accepted. To accomodate extenuating circumstances, your lowest homework grade will be dropped.
You are allowed, and indeed encouraged, to collaborate with other students on solving the homework problems. However, you must write the solutions independently in your own words. Details of the collaboration policy may be found here: Collaboration and Honesty Policy
Some homework assignments may include optional "bonus" problems. Solving these problems will not directly contribute to your homework grade but may improve the letter grade you receive in the course if the final percentage we calculate is on the borderline between two letter grades. Solving bonus problems is also a good way to impress your instructor if you are seeking a recommendation letter, research opportunities, or a grading position.
You may want to use LaTeX to typeset your homework solutions. LaTeX is the standard document preparation system used in the mathematical sciences. Using LaTeX makes it easier for you to revise and edit your solutions and for us to read them, so you will never lose points for illegibility.
My preferred LaTeX editors are TexShop for Mac and TexStudio for Windows. If you would like to give LaTeX a try on the web without installing anything on your computer, Overleaf is a good option.
Not so short intro to LaTeX. A LaTeX tutorial.
Homework template files: tex, cls, jpg, pdf.
In an effort to make tests less time-consuming and less stressful, we are going to experiment with dividing each test into two parts: a traditional in-class portion, and a take-home portion. Two tests will be given during the semester and one will be given at our regularly scheduled final exam period.
The two 70-minute in-class tests are scheduled for Thursday, Sep. 30 and Thursday, Nov. 4. Each midterm will cover roughly one-third of the course content. A comprehensive in-class final will be held during the normal two-hour exam slot. Please wait until the official University final exam schedule is finalized before making your end-of-semester travel plans.
You may bring one double-sided 8.5" x 11" sheet of notes to each midterm test and two such sheets to the final. Note sheets may be either handwritten or typeset. You may not use any other aids during the exam, including but not limited to books, lecture notes, calculators, phones, or laptops.
The take-home portion of each test will be due on the Tuesday following the in-class portion, in line with the regular homework schedule. You will have at least one week to complete this portion. You are free to consult our course materials for these portions of the tests, but unlike homework assignments, they are to be completed individually.
Your active participation in class and in discussion sections is an essential part of your learning. Your participation grade will be determined by responses to in-class polls (adminstered through Google Forms), completed discussion worksheets, and other brief activities such as Homework 0. It will also be possible to increase your participation score by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.
