CS4631/M4631 - Theory of Computing

Dr. R. Rosebrugh

Assignments

General Info

The course meeting time is 8:30MWF in Barclay 311. The text for the course is "Languages and Machines, An Introduction to the Theory of Computer Science", Second Edition, Thomas A. Sudkamp. We will cover Chapters 2-9 and parts of 11, 14 and 15.

Grades will be assigned with approximately the following weights:

The midterm test will be held on October 28. For official detail see the MCS Department Web pages.

Check this URL regularly for information about the course.

Assignments

Assignment 1

From the text: 1.18, 1.25, 1.31, 1.37, 1.39. Due Sept. 20.

Assignment 2

From the text: 2.4, 2.6, 2.8, 2.13, 2.19, 2.29; Prove identity 11 from table 2.3.1. Due Oct 4.

Assignment 3

From the text: 3.2, 3.3, 3.6, 3.9, 3.22 (see 2.19), 3.42, 3.47. Due Oct 15.

Assignment 4

From the text: 4.4, 4.11, 6.6, 6.17, 6.26. Due Oct. 25.

Assignment 5

From the text: 6.30, 6.40, 7.2, 7.6, 7.11: a,b,e, 7.12, 7.16, 7.20. Due Nov 8.

Assignment 6

From the text: 7.19, 7.23, 8.3: a, c, d, g, k, 8.6, 8.12, 8.13. Due Nov 22.

Assignment 7

From the text: 8.17: d,e, 8.28 (for er_a(L) see 8.27), 9.2, 9.7, 9.18. Due Dec 4