Theory of Computation

Space-time: TTh 12:30–1:45pm in FLMG 157
Professor: Rafael Frongillo
Syllabus: below; jump to: objectives, topics, coursework, writing, notes
Textbook: Automata and Computability, Kozen 1997; optional: Sipser

Office hours

Course tools

Schedule

Note: K = Kozen's book, so K.1 means the first chapter (lecture) of the book

Date Reading Topic Event
Aug 27 K.1 Introduction
Aug 29 K.2-4 Deterministic finite automata
Sep 3 K.5-6 Nondeterministic finite automata
Sep 5 K.7-8 Finish NFAs; Regular expressions
Sep 10 K.8-10 Regular expressions and automata

DUE: Problem Set 1 in Gradescope

Sep 12 K.11-12 Pumping lemma!
Sep 17 K.13-14 DFA minimization
Sep 19 K.19-20 Context-free grammars
Sep 24 K.21 Normal forms

DUE: Problem Set 2 in Gradescope

Sep 26 K.22 CFL pumping lemma
Oct 1 K.23-24 PDAs and CFLs
Oct 3 K.25,K.F PDAs and CFLs
Oct 8 K.26-27 (optional) Parsing, review

DUE: Problem Set 3 in Gradescope

Oct 10 K.28-29 Turing machines!
Oct 15 (up through Oct 3 and Problem Set 3)

In-Class Quiz 1

Oct 17 K.30 Other models
Oct 22 K.31 Universal TMs, Diagonalization
Oct 24 K.32 Decidability

DUE: Problem Set 4 in Gradescope

Oct 29 NO CLASS (snow)
Oct 31 K.33 Reductions
Nov 5 K.34 Rice's theorem
Nov 7 K.35-36 (optional) Fun stuff; Review

DUE: Problem Set 5 in Gradescope (actually Nov 8)

Nov 12 Review; Complexity
Nov 14

In-Class Quiz 2

Nov 19 Sipser 7.1-7.4 Complexity: P, NP, NP-completeness

(see also Tim Roughgarden's course, Week 2)

Nov 21 Sipser 7.4-7.5 NP-completeness reductions

(Tim)

Dec 3 Sipser 7.4-7.5 More NP-completeness reductions

(Tim)

Dec 5 Practice: P or NP-complete?

(Tim)

Dec 10 Michael: Baker-Gill-Solovay

DUE: Problem Set 6 in Gradescope

Dec 12 TBA: Gödel's incompleteness theorems
Dec 16

DUE: Optional Problem Set in Gradescope

Resources

Syllabus

Course Objectives

The objective of this course is provide an introduction to the theory of computation covering the following three branches of theoretical computer science:

  1. Automata Theory
    • Formalization of the notion of problems via formal languages
    • Formalization of the notion of computation using "abstract computing devices" called automata
    • Hierarchy of classes of problems or formal languages (regular, context-free, context-sensitive, decidable, and undecidable)
    • Hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)
    • Applications to pattern matching, parsing, and programming languages
  2. Computability Theory
    • Church-Turing thesis (Turing machines as "general-purpose computers")
    • Reduction (solving a problem using a solution for a different problem)
    • Undecidability (when a problem can not be solved using computers)
  3. Complexity Theory
    • Complexity classes : how to classify decidable problems based on their time and space requirements
    • Complexity classes P and NP
    • When a problem is intractable (NP-completeness)
    • Using reductions to prove problems intractable

Topics Covered

  1. Regular Languages (3-4 weeks)
    • Regular expressions
    • Deterministic finite-state machines
    • Nondeterministic finite-state machines
    • Regular grammars
    • Languages that aren't regular: pumping lemma
    • Closure properties
  2. Context-Free Languages (2-3 weeks)
    • Context-free grammars
    • Push-down automata
    • Languages that aren't context-free: pumping lemma for CFLs
    • Deterministic context-free languages
    • Closure properties
  3. Computability Theory (3-4 weeks)
    • Turing machines
    • Recursive vs. recursively-enumerable sets
    • Decidability and the halting problem
    • Reductions
  4. Complexity Theory (2-3 weeks)
    • Time and space complexity
    • P and NP
    • NP-completeness
    • Other complexity classes
  5. Special Topics: TBA (1 week)

Coursework and Grading

Your grade will be based on four components, with your grade broken down roughly as follows: 5-6 problem sets (30%), 8-10 short online quizzes (10%), 3 in-class quizzes (50%), and class participation (10%). Details on expectations of you for these categories follow.

  1. Problem sets.   There will be 5 sets of mostly proof-based problems (i.e., rigorous deductive arguments for a given mathematical statement).

    • The purpose of problem sets is to give you feedback on your understanding. As such, we will grade more leniently than we will the quizzes, with an emphasis on constructive feedback rather than penalizing mistakes.

    • Collaboration is allowed on the problem sets, in groups of up to 3, but you may not copy in any way from your collaborators and you must respect CU academic policies at all times. You may discuss the problems verbally, but you must write up your solutions separately. You must list and describe the extent of your collaborations prominently at the top of your submission (and if you work alone, write e.g. "Collaborators: None"). Copying in any way from any source other than the resources provided or explicitly linked to on the course website, including the Web or another student (past or present), is strictly forbidden. See the Honor Code section below. If you are unsure about whether something is permitted, please ask before the assignment is due. Violators may be removed from the class and given a failing grade.

    • Your complete solution file must be submitted to Gradescope as a single PDF file by 11:00pm on the due date. Late or improperly formatted solutions could receive no credit. (I strongly recommend using LaTeX to produce your solutions.)

    • Your solutions must be detailed, clear, and succinct. Explain in words how you set up your analysis and explain in detail why your solution is correct, but only give details relevant to the solution. (See below for solution-writing advice.)

    • If figures/graphs are requested, they must be sufficiently and properly labeled to receive credit.

    • Some topics will only be covered through the problem sets.

  2. Online quizzes.   I will periodically assign quizzes to help you study, to be taken online via Moodle. You are welcome to consult the textbook or other resources for these quizzes. Typically the quizzes will allow the best of 2 or 3 attempts, however, so you are encouraged to try the first time without outside materials.

  3. In-class quizzes.   We will have three in-class quizzes, which one could think of as midterm exams. The in-class quizzes are cumulative, in the sense that all material up until that point in the course will be fair game, but the bulk of the exam will be in the most recent unit. These quizzes are "closed book".

  4. Participation.   I expect you to participate in class, and on Piazza, by contributing to the discussions and helping your fellow students out with clarification questions. (Note however that you may not post hints for problem sets on Piazza.) Most importantly, have fun working through the material with your classmates!

Advice on Writing Solutions

Your solutions for the quizzes and problem sets should have the following properties, which the grader and I will be looking for:

  1. Clarity: All of your work and answers should be clear and well separated from other problems. If we cannot quickly identify and understand your solution, we cannot evaluate it. The more clear you make your work, the more likely you are to get full credit.

  2. Completeness: Full credit for all problems is based on both sufficient intermediate work (the lack of which often produces a “justify” comment) and the final "answer". There are many ways of solving most problems, and we need to understand exactly how you chose to solve each one. A good rule of thumb: if you were to present your solution to the class and everyone would understand the steps, the level of detail should be sufficient.

  3. Succinctness: The work and solutions that you submit should be long enough to convey exactly why the answer you get is correct, yet short enough to be easily digestible by someone with a basic knowledge of the material. If you find yourself doing more than half a page of dense algebra, generating more than a dozen numeric values or using more than a page or two per problem, you are probably not being succinct. Clearly indicate your final answer if appropriate. Note: for problem sets, it is usually best to rewrite your solution to a problem before you hand it in; often you can make the solution much more succinct.

Other Notes

  1. Honor Code.   All students enrolled in a University of Colorado Boulder course are responsible for knowing and adhering to the academic integrity policy. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access to academic materials, clicker fraud, resubmission, and aiding academic dishonesty. All incidents of academic misconduct will be reported to the Honor Code Council (honor@colorado.edu; 303-735-2273). Students who are found responsible for violating the academic integrity policy will be subject to nonacademic sanctions from the Honor Code Council as well as academic sanctions from the faculty member. Additional information regarding the academic integrity policy can be found at the Honor Code Office website.
  2. Accommodation for Disabilities.   If you qualify for accommodations because of a disability, please submit your accommodation letter from Disability Services to your faculty member in a timely manner so that your needs can be addressed. Disability Services determines accommodations based on documented disabilities in the academic environment. Information on requesting accommodations is located on the Disability Services website (www.colorado.edu/disabilityservices/students). Contact Disability Services at 303-492-8671 or dsinfo@colorado.edu for further assistance. If you have a temporary medical condition or injury, see Temporary Medical Conditions under the Students tab on the Disability Services website and discuss your needs with your professor.
  3. Religious Holidays.   Campus policy regarding religious observances requires that faculty make every effort to deal reasonably and fairly with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, you should notify your instructor of any conflict at least two weeks in advance. See the campus policy regarding religious observances for full details.
  4. Classroom Behavior.   Students and faculty each have responsibility for maintaining an appropriate learning environment. Those who fail to adhere to such behavioral standards may be subject to discipline. Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with race, color, national origin, sex, pregnancy, age, disability, creed, religion, sexual orientation, gender identity, gender expression, veteran status, political affiliation or political philosophy. Class rosters are provided to the instructor with the student's legal name. I will gladly honor your request to address you by an alternate name or gender pronoun. Please advise me of this preference early in the semester so that I may make appropriate changes to my records. For more information, see the policies on classroom behavior and the Student Code of Conduct.
  5. Discrimination and Harassment.   The University of Colorado Boulder (CU Boulder) is committed to fostering a positive and welcoming learning, working, and living environment. CU Boulder will not tolerate acts of sexual misconduct intimate partner abuse (including dating or domestic violence), stalking, protected-class discrimination or harassment by members of our community. Individuals who believe they have been subject to misconduct or retaliatory actions for reporting a concern should contact the Office of Institutional Equity and Compliance (OIEC) at 303-492-2127 or cureport@colorado.edu. Information about the OIEC, university policies, anonymous reporting, and the campus resources can be found on the OIEC website. Please know that faculty and instructors have a responsibility to inform OIEC when made aware of incidents of sexual misconduct, discrimination, harassment and/or related retaliation, to ensure that individuals impacted receive information about options for reporting and support resources.