▲
CSCI 5444: Introduction to the Theory of Computation
Logistics
- Instructor:
Ashutosh Trivedi (ashutosh.trivedi@colorado.edu)
- Course URL: https://tinyurl.com/csci5444-20 .
- Course description:
- Introduces the foundations of automata theory, computability
theory, and complexity theory.
- Shows relationship between automata and formal languages.
- Addresses the issue of which problems can be solved by
computational means (decidability vs undecidability), and
- Introduces concepts related to computational complexity of problems.
- Requisites:
- Discrete Structures/ Discrete Mathematics
- Undergraduate Algorithms
- Class Meeting Times: Tuesday (11:10am—12:25pm) and Thursday (11:10am—12:25am)
- Office hours:
- Venue :
- Class meeting location: https://cuboulder.zoom.us/j/97964978770
- Lecture Videos: available via Moodle
- Office Hour location: https://cuboulder.zoom.us/j/97964978770
Relevant Textbooks
-
Required Text :
-
Other supplemental materials :
Assignments
- All assignments will be posted on moodle. Your identikey is needed for signing in.
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, context-free, context-sensitive, decidable, and undecidable)
- Understanding a hierarchy of classes of automata (finite automata, pushdown automata, and Turing machines)
- 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
- 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
- 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
- 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
- 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.
-
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
- 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:
- Weekly assignments (with least two scores omitted)
- In-class quizzes (three)
- The final project and presentations
- Class participation: you are expected to attend the class and to
regularly interact with the instructor in the class.
Schedule and Lecture Notes
# |
Date |
Description |
Chapter |
1 |
August 25 |
Introduction to theory of computation
|
0 |
Part One: Automata Theory
2 |
Week 1 — August 27 |
Regular languages and Deterministic Finite Automata
|
1.1 |
3 |
Week 2 — September 1 |
Nondeterministic Finite Automata (Subset Construction and Alternation)
|
1.2 |
4 |
Week 2 — September 3 |
Closure Properties for Regular Languages
|
1.1 |
5 |
Week 3 — September 8 |
Regular Expressions
|
1.3 |
6 |
Week 3 — September 10 |
Non-Regular languages: Pumping Lemma
|
1.4 |
7 |
Week 4 — September 15 |
Logic and Regular Languages
|
lecture notes |
8 |
Week 4 — September 17 |
Context-Free Languages: Grammars and Derivations
|
2.1 |
9 |
Week 5 — September 22 |
Pushdown Automata
|
2.2 |
10 |
Week 5 — September 24 |
Non-Context-Free Languages
|
2.3 |
11 |
Week 6 — September 29 |
Closure properties of CFLs
|
|
12 |
Week 6 — October 1 |
Wrap-up of Regular Languages and CFLs
|
2.1 — 2.3 |
13 |
Week 7 — October 6 |
In-Class Quiz I
|
1 and 2 |
Part Two: Computability Theory
14 |
Week 7 — October 8 |
Turing machines
|
3.1 |
15 |
Week 8 — October 13 |
Variants of Turing machines
|
3.2 and 3.3 |
16 |
Week 8 — October 15 |
Decidability: Decidable Languages
|
4.1 |
17 |
Week 9 — October 20 |
Halting Problem: Diagonalization and Reductions
|
4.2 |
18 |
Week 9 — October 22 |
Reductions: More undecidable problems
|
5.1, 5.2 |
19 |
Week 10 — October 27 |
Logics and Decidability
|
6.2 |
20 |
Week 10 — October 29 |
Wrap-up: Turing machines and decidability
|
3-4-5-6 |
22 |
Week 11 — November 3 |
In-class Quiz II
|
3-4-5-6 |
Part Three: Complexity Theory
23 |
Week 11 — November 5 |
Complexity
|
7.1 and 7.2 |
24 |
Week 12 — November 10 |
NP, co-NP, polynomial-time reductions and NP-completeness
|
7.3 |
25 |
Week 12 — November 12 |
NP-complete problems and reductions
|
7.4 |
26 |
Week 13 — November 17 |
Space Complexity Classes: Savitch's theorem
|
|
27 |
Week 13 — November 19 |
PSPACE and PSPACE-complete problems
|
7 |
28 |
Week 14 — November 24 |
In-class Quiz III
|
|
29 |
Week 15 — December 01 |
Special Topics: TBA
|
|
30 |
Week 15 — December 03 |
Special Topics: TBA
|
|
Notes
-
COVID-19.
It is your responsibility to observe campus policy on masks and physical distancing, and to complete a Daily Health Form.
If you do not comply with campus policy you will be required to leave the class.
If you are sick you must stay home and complete the Health Questionnaire and Illness Reporting Form remotely.
You are required to email the instructor to alert him about absence due to illness or quarantine.
The instructor will provide appropriate accommodation for students with a short-term illness or disability to make up the work missed.
If you disclose to the instructor that you have tested positive for COVID-19 or are having symptoms of COVID-19 or have had close
contact with someone who has tested positive for COVID-19, the instructor is required to submit that information to the Medical Services Public Health Office for the purposes of
contact tracing (contacttracing@colorado.edu and/or 303-492-2937).
You are NOT required to tell the instructor the nature of your illness or why you have to quarantine.
You are NOT required to produce a "doctor's notes" for absences due to illness, quarantine or health care appointments.
-
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.
-
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 .
-
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.
-
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.
-
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.
-
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.
- The web-page of a previous offering of the course is available here .