This page, http://www.cs.uiowa.edu/~hzhang/c131/, is always under construction.

A sample final exam of problems can be found here.

This will be the course web page where the assignments are posted.

Instructor:
Hantao Zhang
Office: 201B MLH, Email: hzhang@cs.uiowa.edu, Tel: 353 2545 Office hours: MW 3:30-4:30pm, Fr 12:30-1:30pm |
Teaching assistant:
Nery Chapeton-Lamas
Office: 201N MLH, Email: nerychapeton@gmail.com, Tel: 353 2547 Office hours: Tu., Th, 12:30-2:00pm |

This course is a mathematical exploration of the limits of the power of computers. Some of the questions we ask and attempt to answer are the following. Are there problems that cannot be solved on any computer? 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? What happens when we relax the notion of solving a problem to "approximately" solving a problem - does this fundamentally change which problems can and which problems cannot be solved on a computer?

In attempting to answer these questions we will study the following topics:

- Computation models: Finite State Automata.
- Regular Grammar and Context-free Grammar.
- Turing machines. Definitions and examples. 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.

- Homework 1 (30 points) Due date: 9/8/10

Page 83-86: 1.4(a),(c),(e)-(g); 1.5(c)-(f); 1.6 (e)-(i); 1.13; 1.16.

- Homework 2 (30 points) Due date: 9/15/10

Page 86-90: 1.28; 1.29(b); 1.31; 1.33; 1.35; 1.41; 1.46 (a)(d); 1.49.

- Homework 3 (30 points) Due date: 9/22/10

Page 128-129: 2.6 (b)(d); 2.13; 2.14; 2.15; 2.16.

- Homework 4 (30 points) Due date: 9/29/10

Page 130-131: 2.24; 2.25; 2.30d); 2.31; 2.35.

- Homework 5 (30 points) Due date: 10/06/10

Page 160: 3.6; 3.8(b),(c). For 3.8, please provide a high level description and then the detailed implementation of each high level description.

- Homework 6 (30 points) Due date: 10/27/10

Page 161: 3.15(b)-(e)

Page 183: 4.4, 4.7, 4.10, 4.12, 4.19.

- Homework 7 (30 points) Due date: 11/03/10

Page 211-212: 5.9, 5.12, 5.14, 5.15, 5.30(b)(c).

- Homework 8 (30 points) Due date: 11/15/10

Page 211-212: 5.4, 5.21, 5.23, 5.32(a).

- Homework 9 (30 points) Due date: 11/29/10

Page 294-296: 7.6, 7.9, 7.10, 7.11, 7.12, 7.17.

- Homework 10 (30 points) Due date: 12/08/10

Page 296-298: 7.20, 7.21, 7.24, 7.28, 7.34;

The instructor of this course will follow the policies outlined at
http://www.clas.uiowa.edu/faculty/teaching/new_policytemplate.shtml
for ACCOMMODATIONS FOR DISABILITIES, UNDERSTANDING SEXUAL HARASSMENT,
REACTING SAFELY TO SEVERE WEATHER.

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
itself*.

Please only print the lecture notes on the day of the class as it's updating.

- 1 Introduction PDF
- 2 Automata and Regular Languages PDF
- 3 Context-free Languages PDF
- 4 Turing Machines PDF
- 5 Decidability PDF
- 6 Reducibility PDF
- 7 Time Complexity PDF
- 8 NP complete problems PDF
- 9 Space complexity PDF

Updated