▲

CSCI 5444: Introduction to the Theory of Computation

Logistics

Relevant Textbooks

Assignments

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)
  2. Computability Theory
    • Understanding Church-Turing thesis (Turing machines as a notion of "general-purpose computers")
    • Understanding the concept of undecidability , i.e., when a problem can not be solved using computers
    • How to show undecidability using the concept of problem reduction
  3. Complexity Theory
    • Complexity classes : how to classify decidable problems based on their time and space requirements
    • Complexity classes P and NP, and Intractability (NP-completeness)
    • How to prove NP-completeness?
    • Space Complexity: NL-completeness and PSAPCE-completeness

Topics Covered

  1. Regular Languages (3 weeks)
    • Deterministic finite-state machines
    • Nondeterministic finite-state machines
    • Regular expressions
    • Properties of regular languages
    • Languages that aren't regular: pumping lemma
  2. Context-Free Languages (2 weeks)
    • Context-free grammars
    • Pushdown automata
    • Properties of Context-free languages
    • Languages that aren't context-free: pumping lemma for CFLs
  3. Computability Theory (4 weeks)
    • Turing machines and their variants
    • Church-Turing thesis
    • Decidable languages
    • Undecidability
    • Proving Undecidability of a given problem using problem reductions
    • Rice's theorem
    • Famous undecidable problems such as Post Correspondence Problem (PCP), Tiling problem, halting problems for multistack and two-counter machines.
  4. Complexity Theory (3-4 weeks)
    • Time and space complexity
    • Complexity classes P and NP, and NP-Completeness
    • Famous NP-complete problems
    • Complexity class PSPACE and Pspace-Completeness
    • Complexity classes L and NL, and NL-completeness
  5. Special Topics (guest lectures and class projects: presentations in Week 16)
    • Monadic Second-Order Logic and Automata (Elements of Finite Model Theory by Leonid Libkin)
    • Regular transformations on words and trees (TBA)
    • Descriptive complexity (Descriptive Complexity by Neil Immerman)
    • Randomized Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
    • Quantum Computation (Computational Complexity by Sanjeev Arora and Boaz Barak)
    • Interactive proofs and complexity class IP (Computational Complexity by Sanjeev Arora and Boaz Barak)
    • PCP Theorem and hardness of Approximation (Computational Complexity by Sanjeev Arora and Boaz Barak)
    • Timed and hybrid Automata (TBA)
    • Probabilistic Automata (TBA)

Grading

The overall grade will be based on a cumulative score computed by adding together the grades from:

Schedule and Lecture Notes

# Date Description Chapter
1 August 27 Introduction to theory of computation 0

Part One: Automata Theory

2 Week 1 — August 29 Automata, Turing machines and the Entscheidungsproblem 1.1
3 Week 2 — September 3 Regular Languages and Expressions 1.4
4 Week 2 — September 5 Deterministic Finite Automata 1.1
5 Week 3 — September 10 Deterministic Finite Automata II 1.1-1.3
6 Week 3 — September 12 Non-Regular languages and NFAs 1.2,1.4
7 Week 4 — September 17 More NFAs, Kleene's Theorem lecture notes
8 Week 4 — September 19 Context-Free Languages: Grammars and Derivations 2.1
9 Week 5 — September 24 In-Class Quiz I 1 and 2

Part Two: Computability Theory

10 Week 5 — September 26 Turing machines 3.1
11 Week 6 — October 1 Turing machines, cont. 3.2 and 3.3
12 Week 6 — October 3 Decidability and Undecidability 4.1, 4.2
13 Week 7 — October 7 Undecidability, reductions, Rice's Theorem 5.1,5.2, 5.3
14 Week 7 — October 9 P and NP 7.1-7.4
15 Week 8 — October 15 NP completeness, Reductions 7.1-7.5
16 Week 8 — October 17 More Reductions, approximation preserving reductions Chapter 7
17 Week 9 — October 22 In class Problem Solving See slides from last Thursday for the problems and definitions
18 Week 9 — October 24 In class Quiz II

Part Three: Complexity Theory

19 Week 10 — October 29 Class cancelled due to weather
20 Week 10 — October 31 Time Complexity, the Time Hierarchy Theorem 7.1 - 7.4 and 9.1. See also these and these lecture notes
21 Week 11 — November 5 Circuit Complexity 7.1 - 7.4 and 9.1. See also these lecture notes
22 Week 11 — November 7 Randomized Complexity 10.2. See also these lecture notes
23 Week 12 — November 12 Polynomial Hierarchy 10.3. See also these lecture notes
24 Week 12 — November 14 Polynomial Hierarchy 10.3. See also these lecture notes
28 Week 13 — November 19 Space complexity, L and NL 8.4, 8.5. See also these lecture notes
29 Week 13 — November 21 Space complexity, continued.
30 Week 14 — November 25-30 Thanksgiving Break, no class. Reading material: these notes.
31 Week 15 — December 3 Unique Games Conjecture Problem Solving Session Slides
32 Week 15 — December 5 Intro to Quantum Computing lecture notes

Notes

  1. Accommodation Statement. If you qualify for accommodations because of a disability, please submit to me a letter from Disability Services in a timely manner (for exam accommodations provide your letter at least one week prior to the exam) so that your needs can be addressed. Disability Services determines accommodations based on documented disabilities. Contact Disability Services at 303-492-8671 or by e-mail at dsinfo [AT] colorado.edu. If you have a temporary medical condition or injury, see Temporary Injuries under Quick Links at the Disability Services website and discuss your needs with me.
  2. Religious Observances. 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 full details here .
  3. 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 differences of race, color, culture, religion, creed, politics, veteran's status, sexual orientation, gender, gender identity and gender expression, age, disability, and nationalities. 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.
  4. 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.
  5. Honor Code. All students enrolled in a University of Colorado Boulder course are responsible for knowing and adhering to the academic integrity policy of the institution. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access, 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 honorcode.colorado.edu.
  6. Accessibility This course requires the use of the Zoom conferencing tool, which is currently not accessible to users using assistive technology. If you use assistive technology to access the course material, please contact your faculty member immediately to discuss.
  7. The web-page of a previous offering of the course is available here .