CS 332: Elements of the Theory of Computation, Spring 2021

Course Overview

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:
Instructor:   Mark Bun, mbun [at] bu [dot] edu
Instr. Office Hours:   Wed 4:00-5:00 PM
    Thu 9:00-10:00 AM
     
Teaching Fellow:   Nadya Voronova, voronova [at] bu [dot] edu
TF Office Hours:   Tue 3:00-4:00 PM
    Wed 9:00-10:00 AM
     
Teaching Asisstant:   Huiwen He, huiwenhe [at] bu [dot] edu
TA Office Hours:   Mon 7:00-8:00 PM
    Tue 4:00-5:00 PM
    Fri 3:00-4:00 PM (Tutoring session)
     
Class Times:   Mon, Wed 2:30-3:45 PM (online), Alternate viewing time: 8:00-9:15 PM
Discussion Sections:   Tue 9:30-10:20 AM (CAS 237)
  Tue 11:15-12:05 AM (CAS 237)
  Tue 12:30-1:20 AM (CAS 237)

Important Links

Course Website: https://cs-people.bu.edu/mbun/courses/332_S21. The website contains the course syllabus, schedule with assigned readings, homework assignments, and other course materials.

Piazza: https://piazza.com/bu/spring2021/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 2RB88B. Homework assignments are to be submitted to Gradescope in PDF format.


Catalog Description

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.

Prerequisites

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.

Course Outline


(Perpetually Tentative) Schedule

Date Topics Reading/Reference Handouts/Assignments
Mon 1/25 Welcome, introduction Sipser 0, Lec1, Lec1ann Collaboration and Honesty Policy, Math & Algorithms Review, HW0 out
Wed 1/27 Sets, strings, and languages Sipser 0, Lec2, Lec2ann HW0 due (Th), HW1 out
Mon 2/1 Finite automata Sipser 1.1-1.2, Lec3, Lec3ann Automata Tutor
Wed 2/3 DFA-NFA equivalence, regular operations Sipser 1.2, Lec4, Lec4ann HW1 due (Th); HW2 out
Mon 2/8 Closure properties, regular expressions Sipser 1.2-1.3, Lec5, Lec5ann
Wed 2/10 Regular expressions vs. FAs, distinguishable sets Sipser 1.3, Myhill-Nerode, Lec6, Lec6ann HW2 due (Th); HW3 out
Tue 2/16 Non-regular languages Myhill-Nerode, Lec7, Lec7ann
Wed 2/17 Test 1 Review Lec8, Lec8ann HW3 due (Th), Test 1 out
Mon 2/22 Turing machines Sipser 3.1, 3.3, Lec9, Lec09ann TM simulator, A real TM
Wed 2/24 TM variants and examples, closure properties Sipser 3.2, Lec10, Lec10ann Test 1 due (Th); HW4 out
Mon 3/1 More on closure properties, multi-tape TMs, nondeterminism Sipser 3.2, Lec11, Lec11ann
Wed 3/3 Church-Turing thesis, decidable languages Sipser 4.1, Lec12, Lec12ann HW4 due (Th); HW5 out, universal_dfa.py
Mon 3/8 Diagonalization Sipser 4.2, Lec13, Lec13ann
Wed 3/10 Undecidablility, unrecognizability Sipser 4.2, Lec14, Lec14ann HW5 due (Th); HW6 out
Mon 3/15 Reductions Sipser 5.1, Lec15, Lec15ann
Wed 3/17 Test 2 Review Lec16, Lec16ann HW6 due (Fr); Test 2 out
Mon 3/22 Mapping reductions Sipser 5.3, Lec17, Lec17ann
Wed 3/24 Computation history method Sipser 5.1-5.2, Lec18, Lec18ann Test 2 due (Fr)
Mon 3/29 NO CLASS — (Extra) Wellness Day
Wed 3/31 NO CLASS — Wellness Day
Mon 4/5 Time complexity, space complexity Sipser 7.1, 8.0, Lec19, Lec19ann
Wed 4/7 Hierarchy theorems, Complexity class P Sipser 9.1, 7.2, Lec20, Lec20ann HW7 out
Mon 4/12 Nondeterministic time, NP Sipser 7.3-7.4, Lec21, Lec21ann
Wed 4/14 More on NP Sipser 7.3-7.4, Lec22, Lec22ann HW7 due (Fr); HW8 out
Mon 4/19 NO CLASS — Patriots' Day
Wed 4/21 NP-completeness Sipser 7.4-7.5, Lec23, Lec23ann HW8 due (Fr); HW9 out
Mon 4/26 More NP-completeness, Space complexity Sipser 7.4-7.5, 8.1-8.2, Lec24, Lec24ann
Wed 4/28 Course Wrap-Up and Final Review Lec25, Lec25ann HW9 due (Fr)
Thu 5/6, 5PM Final Exam due

Texts and References

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.


Evaluation

Your grade in the course will be determined by homework assignments, three take-home tests, and class participation.
The following letter grades are guaranteed if you earn the corresponding percentages: A ≥90%, A- ≥85%, B+ ≥80%, B ≥75%, B- ≥70%, C+ ≥65%, C ≥60%. However, to correct for the possibility of assignments and exams being more difficult than anticipated, letter grades may be (significantly) increased above these guarantees.

Homework (45%)

There will be weekly homework assignments to be submitted on Gradescope every Thursday 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 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.

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.

Take-home tests (Test 1: 10%, Test 2: 10%, Final: 20%)

There will be three take-home tests, two during the semester and one due at the end of our regularly scheduled final exam period. Tests will be given according to the regular homework schedule, and you'll have one week to complete each one. Unlike homework assignments, these are to be completed individually.

Class Participation (15%)

Your active participation in class and in discussion sections is an essential part of your learning. Your participation grade will be determined by responding to short "check-in" quizzes after each lecture, as well as other brief activities such as completing Homework 0. Check-in quizzes will be based on our in-class polls and breakout discussions and will give you a chance to reflect on the day's material. They will be available on Gradescope for 24 hours following each class. 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.


Course Policies

Course Recording Policy

All class sessions will be recorded for the benefit of registered students who are unable to attend live sessions (either in person or remotely) due to time zone differences, illness or other special circumstances. Recorded sessions will be made available to registered students ONLY via a password-protected BU MyMedia channel. Students may not share these recordings with anyone not registered in the course and may not repost them in a public platform.

Students have the right to opt-out of being part of the class recording. Please contact your instructor or teaching assistant to discuss options for participating in the course while opting out of the class recording.

No student may record any classroom or other academic activity (including advising sessions or office hours) without my express written consent. Unauthorized use of classroom recordings – including distributing or posting them – is also prohibited. If you have (or think you may have) a disability such that you need to record classroom activities, or need other assistive services, you should contact Disability & Access Services (see below) to request an appropriate accommodation.

Academic Conduct

All Boston University students are expected to maintain high standards of academic honesty and integrity. It is your responsibility to be familiar with the Academic Conduct Code, which describes the ethical standards to which BU students are expected to adhere and students’ rights and responsibilities as members of BU’s learning community. All instances of cheating, plagiarism, and other forms of academic misconduct will be addressed in accordance with this policy. Penalties for academic misconduct can range from failing an assignment or course to suspension or expulsion from the university.

https://www.bu.edu/academics/policies/academic-conduct-code/
http://www.bu.edu/cas/current-students/phd-mfa-students/academic-policies-and-conduct-code/

Regrade Policy

If you find a mistake in the grading, Gradescope has a feature built in for requesting regrades. We will accept regrade requests for up to one week after each homework assignment or test is returned. Before submitting a regrade request, please make sure you have read and understood the distributed solutions. Regrade requests must point out specific factual errors in how the grader interpreted your solution. To ensure grading consistency, we cannot accommodate requests based on disagreements about how much a given mistake should correspond to a point value.

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.

https://www.bu.edu/academics/policies/attendance/

Absence Due to Religious Observance

If you must miss class due to religious observance, you will not be penalized for that absence and you will receive a reasonable opportunity to make up any work or examinations that you may miss. Please notify the instructor of absences for religious observance as soon as possible, ideally before the absence.

https://www.bu.edu/academics/policies/absence-for-religious-reasons/

Bereavement

In the event of the death of an immediate family member, you should notify your advisor, who will help you coordinate your leave. You will be automatically granted five weekdays of leave, and if necessary, you advisor will help you to petition the Dean for additional leave time. You may also request a leave of absence due to bereavement. Please contact your advisor, who will help you with the process.

https://www.bu.edu/academics/policies/student-bereavement/

Disability Services

Students with documented disabilities, including learning disabilities, may be entitled to accommodations intended to ensure that they have integrated and equal access to the academic, social, cultural, and recreational programs the university offers. Accommodations may include, but are not limited to, additional time on tests, staggered homework assignments, note-taking assistance. If you believe you should receive accommodations, please contact the Office of Disability Services to discuss your situation. This office can give you a letter that you can share with instructors of your classes outlining the accommodations you should receive. The letter will not contain any information about the reason for the accommodations.

If you already have a letter of accommodation, you are encouraged to share it with your instructor as soon as possible.

Disability & Access Services
25 Buick Street, Suite 300
617-353-3658
access@bu.edu
http://www.bu.edu/disability/

Grade Grievances

If you feel that you have received an arbitrary grade in a course, you should attempt to meet with the grader before filing a formal appeal. If the student and the instructor are unable to arrive at a mutually agreeable solution, the student may file a formal appeal with the chair. This process must begin within six weeks of the grade posting. To understand how an “arbitrary grade” is defined, please explore the following link.

https://www.bu.edu/academics/policies/policy-on-grade-grievances-for-undergraduate-students-in-boston-university-courses/

Incomplete Grades

An incomplete grade (I) is used only when the student has conferred with the instructor prior to the submission of grades and offered acceptable reasons for the incomplete work. If you wish to take an incomplete in this class, please contact the instructor as soon as possible but certainly before the submission of final grades. To receive an incomplete, you and your instructor must both sign an “Incomplete Grade Report” specifying the terms under which you will complete the class.

https://www.bu.edu/academics/policies/incomplete-coursework/

Student Health Services

Offers an array of health services to students, including wellness education and mental health services (behavioral medicine).

http://www.bu.edu/shs/
http://www.bu.edu/shs/wellness/
http://www.bu.edu/shs/behavioral/index.shtml

Medical Leave of Absence

If you must take a leave of absence for medical reasons and are seeking to re-enroll, documentation must be provided to Student Health Services so that you may re-enroll. To take a medical leave, please talk with SHS and your advisor, so that they may assist you in taking the best course of action for a successful return.

http://www.bu.edu/usc/leaveandwithdrawal/arranging/
http://www.bu.edu/academics/policies/withdrawal-leave-of-absence-and-reinstatement/

ISSO

The International Students & Scholars Office is committed to helping international students integrate into the Boston University community, as well as answering and questions and facilitating any inquiries about documentation and visas.

https://www.bu.edu/isso/