Theory of Computation

Space-time: TTh 9:30–10:45pm in ECCR 245
Professor: Rafael Frongillo
Office hours: M 3:50–4:30pm in ECES 116, Th 9:00-9: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:

  1. 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, context-free, context-sensitive, 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
  2. Computability Theory
    • Understanding Church-Turing thesis (Turing machines as "general-purpose 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)
  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: 6 problem sets (40%), 9 short online quizzes (10%), 3 in-class quizzes (40%), and class participation (10%). Details on expectations of you for these categories follow.

  1. Problem sets.   There will be 6 sets of mostly proof-based 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 (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 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 zero-tolerance 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 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 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 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: 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 in-class quizzes.

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 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 303-492-2127. 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.