CS 3800: Theory of Computation
Fall 2019


The story. From the ice cream dispenser at the shop around the corner to your smart phone: most mechanical and electronic devices we use today can be viewed as machines that process some input and output something in response. They differ vastly, however, in the capabilities they have regarding reading (can I read the input only once? or as often as I like?), processing (am I equipped with some memory allowing me to take notes? how many notes can I take?), and outputting (can I go back and make corrections to the result? or are responses immediately consumed by the recipient?).

The course. You will learn the foundations of the power of various computational devices.
  • In Part I of the course we will begin by looking at simple automata and then gradually increase their reasoning power to the point that the machines we finally consider are, in principle, as powerful as today's computers (although they have an annoyingly rigid syntax).
  • In Part II we will investigate computational problems that cannot be solved by any automated machine. This is known as the study of computability (or the lack thereof).
  • In Part III we will go back to “solvable” (decidable, computable) problems and zoom in on their levels of difficulty: in computing we don't just care about whether a problem can be solved, but how fast this can be done, possibly depending on the size of the input to the problem. We can only scratch the surface of this vast field known as complexity theory. The famous P vs. NP problem falls within it, and we will discuss it.
A Clock Automaton

TABLE OF CONTENTS

Synopsis

Course Staff

Prerequisites

Course Topics

Course Components and Course Credit

Course Milestones

Textbook

Synopsis

There is a second section to this course, with a different CRN, and different logistics, taught by prof. Walter Schnyder. The two sections are not synchronized; you need to stay with your assigned course.

Course Staff

Instructor: Thomas Wahl Thomas Wahl Teaching assistants:

Prerequisites

Formal: enrollment at the Undergraduate level, plus a grade of at least D- in Fundamentals II (CS 2510) or equivalent, and perhaps other courses; check with your academic advisor.

Content:

Course Topics

The following list is tentative; data on a particular topic is likely to change before the topic is covered.
The individual topics below do not map one-to-one to class meetings. Instead, extra information given in the form

(09/05 [Ch. 10, 11])

behind a topic indicates that we covered/will cover that topic on September 5, and that the required reading (if any) for that lecture is from the textbook [1], chapters 11 and 10, in this order (which may, as the example shows, differ from the order in the textbook).

Part 0: Introduction, Basic Concepts, Whetting Appetite

  1. Why study the Theory of Computing? Don't we all want to become programmers? (09/05)
  2. Overview: Automata and Machines; Computability; Complexity (09/05 [Ch. 0.1])
  3. Course logistics. How to succeed in the course
  4. Tools and Supplies: math; logic; proofs (09/05 [Ch. 0.2–0.4])

Part I: Automata and Computational Machines

  1. (Deterministic) Finite automata and regular languages (09/10 [Ch. 1.1])
  2. Nondeterministic Automata; Determinization; Equivalence (09/12 [Ch. 1.2])
  3. Regular expressions (09/17 [Ch. 1.3])
  4. Equivalence of regular expressions and FSAs (09/19 [Ch. 1.3])
  5. Non-regular languages; Pumping Lemma (09/24 [Ch. 1.4])
  6. Adding power: automata with unbounded storage (09/24 [Ch. 2.2])
  7. Context-free grammars; Regular grammars (09/26 [Ch. 2.1])
  8. Equivalence CFG-PDA; Non-CFLs; Compilers and Automata (10/01 [Ch. 2.2–2.3])
  9. Adding more power: Automata with R/W memory access (10/03 [Ch. 3.1])
  10. Turing machines: Examples and Variants (10/08 [Ch. 3.1–3.2])
  11. Turing machines: Examples and Variants (10/10 [Ch. 3.1–3.2])
  12. Enumerators; Notion of Algorithm; Midterm prep (10/14 [Ch. 3.2–3.3])

Part II: Computability

  1. Decidable problems concerning automata and grammars (10/22 [Ch. 4.1])
  2. Diagonalization; TM Acceptance Problem is undecidable (10/29 [Ch. 4.2])
  3. Problem reductions; More undecidable problems (10/31 [Ch. 5.1])
  4. More problem reductions; Rice's Theorem (11/05 [Ch. 5.1])
  5. Mapping reductions; Undecidability in Practice (11/05 [Ch. 5.3])

Part III: Computational Complexity

  1. Measuring computational efficiency: “big-O” notation (11/12 [Ch. 7.1])
  2. Polynomial-time problems; Complexity class P (11/14 [Ch. 7.2])
  3. Nondeterministic poly-time; Complexity class NP (11/19 [Ch. 7.3])
  4. NP-completeness and NP-complete problems (11/21 [Ch. 7.4])
  5. NP-completeness in practice: Partial and approximate algorithms (11/26)
  6. NP-completeness in practice: Probabilistic algorithms; Exam prep (12/03)

Course Components and Course Credit

Class Meetings

Given the size of this class, we will spend most of our meetings on interactive lectures. “Interactive” means that there will be discussions, questions, answers, exercises, and perhaps quizzes and short presentations of (homework) solutions by students. Active participation in the course is not only highly desirable for everyone's benefit (including the instructor's) but is part of your course credit. You can achieve this credit portion in many ways: correct answers, incorrect answers, good questions, not so good questions, volunteer presentations, suggestions for improving the class. Most of these can happen in class, or on Piazza (see below Communication).

Attendance is highly recommended and to some extent required for the participation part of your course credit, but we will not keep attendance records. If you need to miss class, courtesy suggests to inform your instructor, but otherwise you are responsible for catching up on missed material, turning in homeworks, etc.

Communication

We will generally communicate via Piazza. You will be signed up for Piazza near the start of the class (no self-enrollment). We use Piazza in two ways:
  1. Q & A: for questions, answers, and comments on any aspect of the class: homeworks, lecture, logistics, whatever. You may post anonymously if you like, but we don't encourage it. Note that your identity will always be visible to the instructors. For personal and private matters, please send email to the appropriate course staff, or come to office hours.
    Within the common-sense rules of respectful online behavior, I want Piazza to be a platform as open as possible. You will never be judged by the instructor for what you ask on Piazza (and if students resort to judgment of peers, I will intervene). This is a mutual learning and teaching tool. Everybody wants to learn (including the instructor), everybody can help with the instruction (including all students). If you think you know the answer to a question that someone asked, go for it; and don't be afraid to not be 100% right on the money. We will collectively get it in shape.
    That said, following the Q & A part of Piazza is optional. If you feel you have no questions or opinions, and you are not curious what other students are thinking and discussing, then you may abstain from the Q & A. Use good judgment.
  2. Announcements: you can find them on Piazza under Resources→Course Information. This part of Piazza is not optional: you must stay on top of these announcements, as they will rarely be made via email.

Homeworks

They will be given out approximately once a week, with some exceptions to accommodate exams and major holidays. The release date is generally Friday, the due date the following Friday 11:00pm. We expect to be able to grade homeworks within a week.

Late homeworks will not be accepted. This class is fast-paced, so we cannot afford to derail the schedule by giving extensions. If you cannot finish the homework, turn in partial solutions, for partial credit.

Collaboration: Before the due date, you may ask clarification questions in public forums such as Piazza. Please do not discuss homework problems in person with anyone other than the course staff (or your homework partner(s), if we end up doing homeworks in groups). In particular, to state the obvious, the solutions need to be worked out and formulated by yourself (and homework partners). Therefore, clarification questions on public forums must not give away any information (not even implicitly). You are also not allowed to consult printed or online material to search for solutions. We will discuss in class why such behavior would not even make sense.

Exams

There will be two exams, following different rules:
  1. Midterm: this will be a 100-mins in-class exam, on October 17. It will be closed-book, closed-notes. We will examine basic understanding of the class material up to this point, mostly covering Parts 0 and I of the Course Topics.
  2. Final: this will go over 100mins as well and be held on Friday December 6, 2019, 10:30am-12:30pm. It will be open notes: you can bring a 2-page cheat sheet, but no book. The Final will be cumulative and likely go somewhat deeper than the Midterm.
In both exams, no advanced electronic devices (cell phones, laptops, tablets) will be allowed, whether connected to the Internet or not. Please make every effort to be available during the exam days, as there will generally be no make-ups.

Course Credit

Your final grade will depend on the following contributions to the class (the “1-2-3-4” rule):
The following table shows which percentages guarantee each letter grade. This means that, per the instructor's discretion, they may be adjusted down, class-wide or on an individual basis.

A A- B+ B B- C+ C C- F
95 90 85 80 75 70 65 60 <60

In all aspects of this class, we will of course apply Northeastern's Academic Integrity Policy.

Course Milestones

Textbook

The following book is required: Both electronic and printed versions are available from the publisher and the usual online retailers; you can also e-rent the electronic version.
Errata are available on the webpage for the book.

Notation and terminology: while we will stay close to the book, there may be variations. In cases of doubt, stick to what was used in class.

Contents: what we will cover in class is neither a subset nor a superset of the material contained in the book, but it is close to being a subset. There are plenty of other textbooks on this (relatively standard) material, but reading beyond the textbook is not required to do well in this class. If you are interested in particular topics, do ask the instructor for further references.