Theory of Computation
Spacetime: 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
 Tues 11:00  12:30 in Idea Forge (Justin)
 Thurs 10:30  11:30 in ECAE 124 (Michael)
 Thurs 1:45  3:15 in Idea Forge (Justin)
 Fri 1:00  2:00 in ECES 118 (Raf)  CANCELED 12/13
 Mon Dec 16 12:30  1:30 in ECES 118 (Raf)
Course tools
 Piazza: Announcements, discussion, clarification questions
 Moodle: Gradebook, online "quizzes" (study aides)
 Gradescope: Problem set submission, feedback (entry code: 9V45NE)
 Google Drive: All lecture scribbles / notes / slides
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.24  Deterministic finite automata  
Sep 3  K.56  Nondeterministic finite automata  
Sep 5  K.78  Finish NFAs; Regular expressions  
Sep 10  K.810  Regular expressions and automata  DUE: Problem Set 1 in Gradescope 
Sep 12  K.1112  Pumping lemma!  
Sep 17  K.1314  DFA minimization  
Sep 19  K.1920  Contextfree grammars  
Sep 24  K.21  Normal forms  DUE: Problem Set 2 in Gradescope 
Sep 26  K.22  CFL pumping lemma  
Oct 1  K.2324  PDAs and CFLs  
Oct 3  K.25,K.F  PDAs and CFLs  
Oct 8  K.2627 (optional)  Parsing, review  DUE: Problem Set 3 in Gradescope 
Oct 10  K.2829  Turing machines!  
Oct 15  (up through Oct 3 and Problem Set 3)  InClass 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.3536 (optional)  Fun stuff; Review  DUE: Problem Set 5 in Gradescope (actually Nov 8) 
Nov 12  Review; Complexity  
Nov 14  InClass Quiz 2  
Nov 19  Sipser 7.17.4  Complexity: P, NP, NPcompleteness  (see also Tim Roughgarden's course, Week 2) 
Nov 21  Sipser 7.47.5  NPcompleteness reductions  (Tim) 
Dec 3  Sipser 7.47.5  More NPcompleteness reductions  (Tim) 
Dec 5  Practice: P or NPcomplete?  (Tim)  
Dec 10  Michael: BakerGillSolovay  DUE: Problem Set 6 in Gradescope  
Dec 12  TBA: Gödel's incompleteness theorems  
Dec 16  DUE: Optional Problem Set in Gradescope 
Resources
 Drawing and simulating automata
 For simulation, intuition, working through problems: http://automatonsimulator.com/
 For drawing (e.g. on problem sets): http://madebyevan.com/fsm/
 Proofs
 Discrete Mathematics and Its Applications by Rosen  nice introduction to proofs among other topics.
 Mathematics for Computer Science, by Lehman, Leighton, Meyer. Chapters 1 and 2 especially.
 Advice on writing proofs, by Cathy O'Neil. See also Book of Proof by Hammack.
 How to Prove It by Velleman.
 Latex resources and guides
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:
 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, contextfree, contextsensitive, decidable, and undecidable)
 Hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)
 Applications to pattern matching, parsing, and programming languages
 Computability Theory
 ChurchTuring thesis (Turing machines as "generalpurpose computers")
 Reduction (solving a problem using a solution for a different problem)
 Undecidability (when a problem can not be solved using computers)
 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 (NPcompleteness)
 Using reductions to prove problems intractable
Topics Covered
 Regular Languages (34 weeks)
 Regular expressions
 Deterministic finitestate machines
 Nondeterministic finitestate machines
 Regular grammars
 Languages that aren't regular: pumping lemma
 Closure properties
 ContextFree Languages (23 weeks)
 Contextfree grammars
 Pushdown automata
 Languages that aren't contextfree: pumping lemma for CFLs
 Deterministic contextfree languages
 Closure properties
 Computability Theory (34 weeks)
 Turing machines
 Recursive vs. recursivelyenumerable sets
 Decidability and the halting problem
 Reductions
 Complexity Theory (23 weeks)
 Time and space complexity
 P and NP
 NPcompleteness
 Other complexity classes
 Special Topics: TBA (1 week)
Coursework and Grading
Your grade will be based on four components, with your grade broken down roughly as follows: 56 problem sets (30%), 810 short online quizzes (10%), 3 inclass quizzes (50%), and class participation (10%). Details on expectations of you for these categories follow.

Problem sets. There will be 5 sets of mostly proofbased 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 solutionwriting 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.


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.

Inclass quizzes. We will have three inclass quizzes, which one could think of as midterm exams. The inclass 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".

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:

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.

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.

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
 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; 3037352273). 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.
 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 3034928671 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.
 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.
 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.
 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, protectedclass 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 3034922127 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.