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

Makeup Lectures on March 8:

3:30-5:00pm: MLH 217

7:30-9:00pm: MLH 214

Instructor:
Hantao Zhang
Office: 201B MLH, Email: hantao-zhang@uiowa.edu Tel: (319) 353 2545 Office hours: Tu, 1:00-2:30pm; Th, 9:00-10:30am; or by appointment |
TA:
Kyle Diederich
Office: 101N MLH, Email: kyle-diederich@uiowa.edu Tel: (319) 353 2545 Office hours: Mon, 12:00-1:30pm; Wed, 11:00-12:30pm; or by appointment |

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 topics:

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

- Homework 1 (30 points) Due date: 1/31/2017

Page 83-84: 1.4 (a, c, e, f, g); 1.5 (c-g); 1.6 (a-e).

sample solution - Homework 2 (30 points) Due date: 2/9/2017

Page 84-86: 1.7 (c-e); 1.13; 1.16; 1.17; 1.18.

sample solution - Homework 3 (30 points) Due date: 2/21/2017

Page 86-93: 1.21 (alternative methods are fine); 1.28; 1.42; 1.46 (a, c); 1.71.

Page 154-156: 2.4 (b,c,e); 2.9; 2.10.

sample solution - Homework 4 (30 points) Due date: 3/2/2017

Page 155-157: 2.6 (d); 2.12; 2.13; 2.14; 2.25; 2.30 (a,d); 2.31.

sample solution - Homework 5 (30 points) Due date: 3/9/2017

Page 187-189: 3.2 (b,d); 3.8 (b,c) (describe how the tape is changed and how the head moves);3.15 (b,d); 3.16 (c,d).

sample solution - Homework 6 (30 points) Due date: 3/30/2017

Page 211-212: 4.11; 4.13; 4.17; 4.21; 4.28.

- First Midterm on March 21 (30 percent of the final score)

The exam is close book and notes, except one sheet of notes.

Midterm summary

Sample solutions to the test questions

Sample solutions to two problems in Chapter 2 - Second Midterm on April 27 (30 percent of the final score)
- Quiz (15 minutes) on May 4 (10 percent of the final score)

**
The final grade is based on the final score and curved for those whose final score is at least 30% of the full final score.
**

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 download/print the lecture notes on the day of the class as it will be updated most likely on that day.

- 1 Introduction PDF
- 2 Regular Languages PDF part 2 PDF
- 3 Context-free Languages PDF DPDA PDF
- 4 Turing Machines PDF
- 5 Decidability PDF
- 6 Reducibility PDF
- 7 Time Complexity PDF
- 8 NP Completeness PDF
- 9 Space Complexity PDF
- 10 Advanced Topics PDF