| Instructor: | Mark Bun, mbun [at] bu [dot] edu | |
| Instr. Office Hours: | Thu 5:00-6:00 (MCS 114) | |
| Fri 10:00-11:00 (MCS 114) | ||
| Teaching Fellow: | Nadya Voronova, voronova [at] bu [dot] edu | |
| TF Office Hours: | Fri 2:30-4:30 (MCS B30) | |
| Class Times: | Mon, Wed 2:30-3:45 (CAS B18) | |
| Discussion Sections: | Tue 9:30-10:20 (FLR 121) | |
| Tue 11:15-12:05 (FLR 121) | ||
| Tue 12:30-1:20 (FLR 121) |
Course Website: https://cs-people.bu.edu/mbun/courses/332_S20. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.
Piazza: https://piazza.com/bu/spring2020/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 MKB65D. Homework assignments are to be submitted to Gradescope in PDF format.
Top Hat: https://app.tophat.com/e/400708. We will be using the Top Hat classroom response system in class. The entry code for the course is 400708. You will be able to submit answers to in-class questions using Apple or Android smartphones and tablets, laptops, or through text message.
You can visit the Top Hat Overview (Top-Hat-Overview-and-Getting-Started-Guide) within the Top Hat Success Center which outlines how you will register for a Top Hat account, as well as providing a brief overview to get you up and running on the system.
Anonymous feedback: You can send Mark anonymous feedback here at any time. He will be the only one to read it. Include your name if you would like a response.
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 |
|---|---|---|---|
| Wed 1/22 | Welcome, introduction | Sipser 0-1.1, L01-ann | Collaboration and Honesty Policy, Math & Algorithms Review, Automata Tutor |
| Mon 1/27 | Finite automata, regular operations | Sipser 1.1-1.2, L02, L02-ann | HW1 out |
| Wed 1/29 | DFA-NFA equivalence, closure under regular operations | Sipser 1.1-1.2, L03, L03-ann | |
| Mon 2/3 | Non-regular languages, Pumping Lemma | Sipser 1.4, L04, L04-ann | HW1 due; HW2 out |
| Wed 2/5 | Regular expressions | Sipser 1.3, L05, L05-ann | |
| Mon 2/10 | Regular expressions cont'd, context-free grammars, Pumping Lemma for CFGs | Sisper 2.1, 2.3, L06, L06-ann | HW2 due; HW3 out |
| Wed 2/12 | Pushdown automata | Sipser 2.2, L07, L07-ann | Practice Midterm 1 distributed in class |
| Tue 2/18 | Equivalence of PDAs and CFGs | Sipser 2.2, L08, L08-ann | (Tue) HW3 due |
| Wed 2/19 | Midterm 1 Review | L09, L09-ann | Practice Midterm 1 solutions distributed in class |
| Mon 2/24 | MIDTERM 1 | ||
| Wed 2/26 | Turing machines | Sipser 3.1, 3.3, L10, L10-ann | TM simulator, A real TM |
| Mon 3/2 | TM variants, Church-Turing Thesis | Sipser 3.1-3.2, L11, L11-ann | HW4 out |
| Wed 3/4 | TM variants, Church-Turing Thesis (cont'd) | Sipser 3.1-3.2, L12, L12-ann | Mid-semester feedback |
| Mon 3/9 | NO CLASS — Spring Break | ||
| Wed 3/11 | NO CLASS — Spring Break | ||
| Mon 3/16 | Decidable languages | Sipser 4.1, L13, L13-ann | HW5 out |
| Wed 3/18 | Diagonalization | Sipser 4.2, L14, L14-ann | HW4 due |
| Mon 3/23 | Undecidable and unrecognizable languages, reductions | Sipser 4.2, 5.1, L15, L15-ann | HW6 out |
| Wed 3/25 | Mapping reductions | Sipser 5.3, L16, L16-ann | HW5 due |
| Mon 3/30 | Midterm 2 Review | L17, L17-ann | HW6 due |
| Wed 4/1 | MIDTERM 2 | Midterm 2 distributed on Piazza (due 4/2) | |
| Mon 4/6 | Time complexity, P | Sipser 7.1-7.2, L18, L18-ann | HW7 out |
| Wed 4/8 | Nondeterministic time, NP | Sipser 7.3-7.4, L19, L19-ann | |
| Mon 4/13 | More on NP | Sipser 7.3-7.4, L20, L20-ann | HW7 due; HW8 out |
| Wed 4/15 | Cook-Levin Theorem, NP-complete problems | Sipser 7.4-7.5, L21, L21-ann | |
| Mon 4/20 | NO CLASS — Patriots' Day | HW8 due (Tue); HW9 out | |
| Wed 4/22 | Space complexity, Savitch's Theorem | Sipser 8.1-8.2, L22, L22-ann | |
| Mon 4/27 | PSPACE-completeness, TQBF, time and space hierarchy theorems | Sipser 8.3, 9.1, L23, L23-ann | HW9 due |
| Wed 4/29 | Course Wrap-Up and Final Review | L24, L24-ann | |
| Tue 5/5-Thu 5/7 | Final Exam |
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 every Monday at 2PM. No late homework will be accepted. To accomodate extenuating circumstances, your two (edit 3/17) lowest homework grades 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 assigments 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. Collaboration is NOT allowed on bonus problems.
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.
There will be two 70-minute in-class midterm exams scheduled for Monday, Feb. 24 and Wednesday, Apr. 1. These dates are confirmed and are not subject to change. Each midterm will cover roughly one-third of the course content. A comprehensive final exam 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 exam and two such sheets to the final exam. 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.
Your active participation in class and in discussion sections is an essential part of your learning. Your participation grade will be determined by your engagement with the Top Hat classroom response system. It will also be possible to increase this score by thoughtfully asking and answering questions in lectures, in discussions, on Piazza, or during office hours.
