22c:135 Introduction to Theory of Computation, Spring 2013
This page, http://www.cs.uiowa.edu/~hzhang/c135/, is always under construction.
22C:135 Theory of Computation, Spring 2013
Prerequisite: C or better in Algorithms (22C:31) or its equivalent
1:30-2:20 MWF, 213 MacLean Hall
We will also use
https://piazza.com/class#spring2013/22c135 for announcements and discussions.
Goals and Objectives
This course is a theoretic exploration of computing devices.
Some of the questions we ask and attempt to answer are
the following. Are there problems that cannot be solved on any
computing device? How does one determine if a given problem can or cannot be
computationally solved? If we place bounds on the resources (time and
space) available to a computer, then what can be said about which
problems can and which problems cannot be solved on a computer? How
does the power of a computer change, if it has access to random bits?
In attempting to answer these questions we will study the following
- Computation models: Finite State Automata.
- Regular Expressions and Regular Grammars.
- Context-free Grammars and Pushdown Automata.
- Computation models: Turing machines (TM).
- Turing-decidable and Turing-recognizable languages.
- Enhancements of TMs: multi-tape TMs, non-deterministic TMs.
Equivalence of these and the standard TM.
- Diagonalization. Acceptance problem is undecidable;
Acceptance problem is recognizable; the complement of the Acceptance problem is unrecognizable.
- Reductions. Examples of other undecidable languages. Rice's theorem. Post's Correspondence Problem (PCP) is undecidable.
- Running time of Turing Machines. The classes P, NP, NP-hard, and NP-complete.
- Cook-Levin Theorem, some reductions.
- Space complexity, Savitch's Theorem, PSPACE.
Quantified boolean formula satisfiability is PSPACE-complete. So is Generalized Geography.
- The space heirarchy and the time heirarchy theorems.
Introduction to the Theory of Computation (second edition)
by Professor Michael Sipser.
The book is available in Iowa Book Store and
the latest errata can be found at
Homeworks (5 homeworks, each counts for five percent of the final score)
LATE-DUE HOMEWORK ARE NOT ACCEPTED.
In general you will be better off turning in what you have on time
rather than seeking extra time to complete your work. There will be no
make-up exams in general and exceptions will be rare and only for
students whose reasons are included in the University's policy on
"Excused Absences from Examinations".
- Homework 1 (50 points) Due date: 2/11/2013
Page 83-90: 1.4(g); 1.5(f); 1.6 (h); 1.13; 1.16;
1.28 (c); 1.31; 1.37; 1.41; 1.46(a).
A sample solution of Homework 1 is here.
- Homework 2 (50 points) Due date: 2/25/2013
Page 128-129: 2.4(e); 2.6 (b); 2.12; 2.14; 2.16; 2.23; 2.24; 2.26; 2.30(a)(d); 2.32; 2.35.
A sample solution of Homework 2 is here.
- Homework 3 (50 points) Due date: 3/11/2013
Page 159-160: 3.8(b)(c); 3.12; 3.15(b)-(e); 3.16(b)-(d).
Page 183-184: 4.4, 4.10, 4.12, 4.24, 4.28.
A sample solution of Homework 3 is here.
- Homework 4 (50 points) Due date: 4/8/2013
Page 211-213: 5.1, 5.2, 5.3, 5.9, 5.12, 5.14, 5.21, 5.22, 5.23, 5.30(b).
A sample solution is here.
- Homework 5 (50 points) Due date: 4/24/2013
Page 294-299: 7.6, 7.7, 7.12, 7.16, 7.17, 7.20, 7.21, 7.24, 7.28.
A sample solution of Homework 5 is here.
Exams (One midterm and one final exam)
Midterm on March 13 (30 percent of final score)
Final exam (10am-12pm, May 15) (40 percent of final score)
For the policies on ACADEMIC DISHONESTY and PROCEDURE FOR COMPLAINT,
see the Student Academic Handbook,
of the Colleage of Liberal Arts and Sciences.
The instructor of this course will follow the policies outlined at
for ACCOMMODATIONS FOR DISABILITIES, UNDERSTANDING SEXUAL HARASSMENT,
REACTING SAFELY TO SEVERE WEATHER.
Class Participation (5 percent of final score)
You are expected to study all the material in each chapter covered
in the class even if that material is not explicitly discussed in
class or in the homework.
The lecture notes are a supplement to the course textbooks. They
are supposed to help you understand the textbook material better,
they are a replacement for neither the textbook nor the lecture
Please only print the lecture notes on the day of the class
as it's updating.
2 Regular Languages
3 Context-free Languages
4 Turing Machines
7 Time Complexity
8 NP Completeness
9 Space Complexity
10 Advanced Topics