Theory of Computation
Spacetime: TTh 9:30–10:45pm in ECCR 245
Professor: Rafael Frongillo
Office hours: M 3:50–4:30pm in ECES 116, Th 9:009:30 in/outside ECCR 245 (Raf)
Office hours: Th 3:30–4:30pm in ECCR 1B06 (Abdul)
Syllabus: see below or jump to objectives, topics, coursework, writing, notes
Mailing List: Piazza, sign up here
Assignments/Grades/Schedule: Moodle (key: turingcomplete)
Textbook: Automata and Computability, Dexter Kozen, 1997
Optional textbook: Introduction to the Theory of Computation, Michael Sipser, 2002 (2nd or 3rd edition)
Resources
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. And another great reference, How to Prove It by Velleman.
LaTeX resources and guides: one, two, three, four
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
 Understanding a hierarchy of classes of problems or formal languages (regular, contextfree, contextsensitive, decidable, and undecidable)
 Understanding a hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)
 Understanding applications to pattern matching, parsing, and programming languages
 Computability Theory
 Understanding ChurchTuring thesis (Turing machines as "generalpurpose computers")
 Understanding the concept of reduction (solving a problem using a solution for a different problem)
 Understanding the concept of 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: 6 problem sets (40%), 9 short online quizzes (10%), 3 inclass quizzes (40%), and class participation (10%). Details on expectations of you for these categories follow.

Problem sets. There will be 6 sets of mostly proofbased problems (i.e., rigorous deductive arguments for a given mathematical statement).

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. Copying in any way from any source other than the resources provided or explicitly linked to on the course website or Moodle, 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. There will be a zerotolerance policy to violations of this requirement. Violators will be removed from the class and given a failing grade.

Your complete solution file must be submitted to Moodle as a single PDF file (apart from code, if applicable) by 11:50pm 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 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 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: 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.
Note that the above guidelines also largely apply to the inclass quizzes.
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 maintaining a positive learning, working, and living environment. CU Boulder will not tolerate acts of sexual misconduct, discrimination, harassment or related retaliation against or by any employee or student. CU’s Sexual Misconduct Policy prohibits sexual assault, sexual exploitation, sexual harassment, intimate partner abuse (dating or domestic violence), stalking or related retaliation. CU Boulder’s Discrimination and Harassment Policy prohibits discrimination, harassment or related retaliation based on race, color, national origin, sex, pregnancy, age, disability, creed, religion, sexual orientation, gender identity, gender expression, veteran status, political affiliation or political philosophy. Individuals who believe they have been subject to misconduct under either policy should contact the Office of Institutional Equity and Compliance (OIEC) at 3034922127. Information about the OIEC, the above referenced policies, and the campus resources available to assist individuals regarding sexual misconduct, discrimination, harassment or related retaliation can be found at the OIEC website.