CIS 720: Introduction to the Theory of Computation - Spring 96

ASSIGNMENTS

Finite State Machines and Regular Languages

Reading
Davis, Sigal, and Weyuker, Chapter 9.

Exercises: Due Feb 1
From Section 9.1: 1(e), 4, 6, and 7.
From Section 9.2: 3 and 4.
From Section 9.4: 3, 4, and 5.

Exercises: Due Feb 13
From Section 9.5: 2(a,b,d,g), 4, 7, and 8.
From Section 9.6: 2(b).
From Section 9.7: 2, 5, 6(a,b), 8, and 10.

The General Theory of Computation

Reading
Jones, Chapters 1 through 5.

Exercises: Due Feb 27
From Chapter 2: 2.8.1.
From Chapter 3: 3.4.2 and 3.4.6.
From Chapter 4: 4.8.2.
From Chapter 5: 5.3.1 and 5.3.3

Notes: (a) For 5.3.1 and 5.3.3 detailed sketches will suffice. (b) For 5.3.3 you may use informal C, C++, ML, Scheme, or whatever in place of Pascal.

Reading
Jones (the new version), Through Chapter 7.
My CIS 767 Class Notes, Sections 1 through 8.

Exercises: Due April 9
From Jones Chapter 7: Exercise 7.8.2.
From the 767 Notes: Problem 5.1(a,b,c).
From the 767 Notes: Problem 6.1.
From the 767 Notes: Problem 6.2.
From the 767 Notes: Problem 7.2(a,c) .
From the 767 Notes: Problem 7.4.
From the 767 Notes: Problem 7.7.
From the 767 Notes: Problem 8.9.
From the 767 Notes: Problem 8.10.

Computational Complexity Theory

Reading
Davis, Sigal, and Weyuker, Chapter 15.
Hopcroft and Ullman, Chapter 12.

Exercises: Due April 30
From DSW, Section 15.2: Exercise 4.
From DSW, Section 15.2: Exercise 5.
From DSW, Section 15.2: Exercise 8.
From DSW, Section 15.2: Exercise 9.
From DSW, Section 15.2: Exercise 10.
From DSW, Section 15.2: Exercise 13.
From DSW, Section 15.4: Exercise 1.
From DSW, Section 15.2: Exercise 7.
From DSW, Section 15.2: Exercise 8.
From DSW, Section 15.2: Exercise 9.

Back to the CIS 720 Home Page

Last noted modification: 25 January 1996

Jim Royer / royer@top.cis.syr.edu