CS 332: Theory of Computation (Fall 2020)

This course is an introduction to the theory of computation. This is the branch of computer science that aims to understand which problems can be solved using computational devices and how efficiently those problems can be solved. To be able to make precise statements and rigorous arguments, computational devices are modeled using abstract mathematical "models of computation." The learning objectives of the course are to:

• Foremost, understand how to rigorously reason about computation through the use of abstract, formal models.
• Learn the definitions of several specific models of computation including finite automata, context-free grammars, and Turing machines, learn tools for analyzing their power and limitations, and understand how they are used in other areas of computer science.
• Learn how fundamental philosophical questions about the nature of computation (Are there problems which cannot be solved by computers? Can every problem for which we can quickly verify a solution also be solved efficiently?) can be formalized as precise mathematical problems.
• Gain experience with creative mathematical problem solving and develop the ability to write correct, clear, and concise mathematical proofs.

Index of Links

Course website: https://bu-cs332.github.io

Zoom:

• Lecture & instructor office hours: https://bostonu.zoom.us/j/96833730296?pwd=bkMzcC85ZTZDMENXZ3FRK2swYjNQQT09
• Discussion sections: https://bostonu.zoom.us/j/94584806858?pwd=bzNXeTVKYWVVbldiWlVnWENQam1FUT09
• T.F. office hours: https://bostonu.zoom.us/j/94746608666?pwd=bkFhUmZBQXErOWVzQWl2NCtzdTArUT09

Piazza: https://piazza.com/bu/fall2020/cs332

Gradescope: https://www.gradescope.com. Use Entry Code 9W7J53.

Plickers: Get your link here.

Teaching Format

The teaching will follow the Learn from Anywhere (LfA) policy, allowing both in-person and remote students. We will experiment with different methods of teaching, including lecturing, recorded lecturing, flipped class, problem solving in class.

If you are joining the class remotely, please keep your microphone muted when not speaking, and do not talk to others from your remote learning environment while on the microphone. We suggest that if you are comfortable with it, you can turn on your video cameras, especially when asking a question so that your facial expressions can clarify your questions.

We will the use Plickers response system for questions during the lectures. You will be able to submit answers to in-class questions using your web browser. However, we will provide appropriate accommodations if you miss any of the classes.

Finally, 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.

Prerequisites

• CS 131: Combinatoric Structures
• CS 330: Introduction to Analysis of Algorithms

You are not supposed to be registered for the class if you have not met the prerequisites.

Course Outlines

• Automata and Formal Language Theory. Deterministic finite automata, nondeterministic finite automata, regular expressions. Pumping Lemma, non-regular languages. Pushdown automata and context-free languages.
• Computability Theory. Turing Machines and the Church-Turing thesis. Decidability, halting problem. Reductions. Rice's Theorem, Recursion Theorem. Kolmogorov complexity.
• Complexity Theory. Time complexity, space complexity, hierarchy theorems. Complexity classes P, NP, PSPACE and the P vs. NP question. Polynomial time reductions and NP-completeness.
• Advanced topics subject to time constraints. Approximation algorithms, randomized algorithms, cryptography, quantum computation.

The schedule listed here is tentative and subject to change.

Discussion sections

Attendance of discussion sections is optional but encouraged for you to better understand the materials.

Required Textbook

Michael Sipser, Introduction to the Theory of Computation, 3rd Edition. ISBN-13: 978-1133187790.
See here for a list of errata.

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.

Other Resources

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.

Homework (30%)

There will be weekly homework assignments to be submitted on Gradescope every Tuesday at 2PM. No late homework will be accepted. To accomodate extenuating circumstances, your two 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.

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. Collaboration is NOT allowed on bonus problems.

You are expected to present your homework cleanly so that the graders do not mistakenly take away your points. 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.

For LaTeX editors, you can try 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. LaTeX Stack Exchange is a good place to go for more fancy LaTeX tricks.

Homework template files: source zip, and its pdf output.

Midterm 1 (10%), Midterm 2 (10%), Final Exam (20%)

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.

Class Participation (30%)

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

Academic Conduct

Attendance Policy

Students are expected to attend each class session unless they have a valid reason for being absent. If you must miss class due to illness or another reason, please notify the instructor as soon as possible, ideally before the absence.

Consistent attendance is necessary for remote students in order to follow the classes. All students are expected to be responsible for preparing the equipments for them to be able to either attend the class and exams, either in-person or remotely.

Absence Due to Religious Observance

Bereavement

Disability Services

Grade Grievances

Incomplete Grades

Student Health Services

Medical Leave of Absence

ISSO