CS4631/M4631 - Theory of Computing

General Info

The course meeting time is 12:30MW and 9:00Th in Dunn 111. The text for the course is "Introduction to the Theory of Computation", Second Edition, by Michael Sipser. We will cover Chapters 1-5 and parts of 6, 7 and 9.

Grades will be assigned with approximately the following weights:

• Assignments: 20
• Midterm Test: 20
• Final Exam (3hr): 60
The midterm test will be held on October 25. For official detail see the MCS Department Web pages.

Check this URL regularly for information about the course.

An on-line text on similar material is http://www.cs.uky.edu/~lewis/educ.html

Assignment 1

From the text: 0.2 b,c,e,f, 0.6, 0.7, 0.11; 1.4 a,e,g, 1.6 a,b,e,i,

Due in class: September 18.

Assignment 2

From the text: Chapter 1: 1.5 d,e; 1.7 c,e; 1.10 b; 1.14 b; 1.16 b

Due in class: September 25.

NOTE: when a question has multiple parts, be sure to look at other parts of the question - especially earlier ones! - as they may provide useful hints.

Assignment 3

From the text: 1.20 a,b,d,h (find short strings!); 1.21 b; 1.29 b; 1.30.
Also: Use the pumping Lemma to show that the following languages over {a,b}are not regular:
i) the set of palindromes;
ii) the set of strings in which the number of a's is a perfect square.

Due in class: Oct 2.

Assignment 4

From the text: 1.27; 1.28 a; 2.1 b,d; 2.9; 2.14 Bonus: 2.17

Due in class: Oct 11.

Assignment 5

From the text: 2.2; 2.10; 2.17, 2.30 a,d; 2.44 Bonus: 2.35

Due in class: Oct 19.

Assignment 6

From the text: 3.2 b,c; 3.4; 3.7; 3.8 b.

Due in class: Nov 2.

Assignment 7

From the text: 4.2; 4.4; 4.6; 4.8; 4.10.

Due in class: Nov 13.

Assignment 8

From the text: 4.12; 4.16; 5.1; 5.2

Due in class: Nov 23.

Assignment 9

From the text: 5.3; 5.4; 5.17; 5.35

Due: Dec 1.