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

22C:135 Introduction to Theory of Computation

2:30-4:15 T.Th., 110 MacLean Hall

SPECIAL ARRANGEMENT ON SITTING, TESTING, ETC., CAN BE MADE IF YOU HAVE A DISABILITY.

TEXTBOOK 1: Formal Models of Computation: The Ultimate Limits of Computing

TEXTBOOK 2: Introduction to the Theory of Computation

Homeworks (TEN homeworks, each counts for three percent of final score)

• Homework 1: (due date: Sep. 6, 2005 ) There are two problems from Sipser's textbook (1st ed.)
  Page 84: Problem 1.4 (all 14 languages) 20 points (2nd ed: Problem 1.6)
  Page 86: Problem 1.15 (all eight languages) 10 points (2nd ed: Problem 1.20)
• Homework 2: (due date: Sep. 15, 2005 ) There are five problems from Sipser's textbook (2nd ed.)
  1.16, 1.21, 1.32, 1.37, 1.40(b)

  For Sipser's textbook (1st ed.), these problems are
  1.12, 1.16, 1.25, 1.30, 1.32(b),

• Homework 3: (due date: Sep. 27, 2005 ) One problem from Art Fleck's book: Problem 3.12 (see also Lecture Notes).
  There are four problems from Sipser's textbook (2nd ed.)
  1.27, 1.46 (a)(d), 1.53

  For Sipser's textbook (1st ed.), these problems are
  1.22, 1.23(a)(d), 1.36

• Homework 4: (due date: Oct. 6, 2005 )
  There are four problems from Sipser's textbook (2nd ed.)
  2.9, 2.14, 2.23, 2.26

  For Sipser's textbook (1st ed.), these problems are
  2.9, 2.14, 2.19, 2.27
  

Exams (TWO midterms, no final exam)

First Midterm on 10/11 (30 percent of final score)

Sample solutions to the test

A sample solution of 2.45

Second Midterm on ???? (35 percent of final score)

Class Participation (5 percent of final score)

Lecture Notes

• Week 1: Introduction, Regular Expressions PDF
• Week 2: Finite State Automata PDF
• Week 3: Finite Automata vesus Regular Expressions PDF
• Week 4: Properties of Regular Languages PDF
• Week 5: Transducers and Minimization PDF
• Week 6: Grammars PDF
• Week 6: Context-Free Grammars PDF