CIS 420/520 Fall 2006

[ CIS 420/520 Home Page | Syllabus | Announcements ] Last updated 2006/11/16 08:28:58
The problem numbers refer to problems in the second edition of Sipser. Many of the problems may be in the first edition, but the second edition has more problems and the numbering is different. For your convenience, the assignment link is a page of the problems typed in from the second edition.

Assignment Schedule

Assignment Topic Problems Due
1 Deterministic Finite Automata Turn in: Sipser 1.6a,b,c,d, 1.36
Additional for CIS 520 to turn in: Sipser 1.33
Recommended (don't turn in): Sipser 1.1, 1.2, 1.3, 1.4, 1.5 		Friday, October 6
2 Nondeterminism Turn in: Sipser 1.7b,c,e,h 1.14, 1.15
Additional for CIS 520 to turn in: Sipser 1.57
Recommended (don't turn in): Sipser 1.8, 1.9, 1.10, 1.11, 1.16 		Monday, October 16
3 Regular Expressions, Pumping Lemma Sipser 1.21a, 1.46a,c, 1.53
Additional for CIS 520: Sipser 1.48
Recommended (don't turn in): Sipser 1.18, 1.19, 1.20, 1.29a,c 		Wednesday, October 25
4 Context Free Grammars Turn in: Sipser 2.4c, 2.6b, 2.16, 2.26
Additional for CIS 520 to turn in: Sipser 2.19
Recommended (don't turn in):: Sipser 2.1, 2.3, 2.4, 2.9 		Monday, November 6
5 Pushdown Automata, Non CFLs Turn in: Sipser 2.13, 2.17, 2.30d, 2.22
Additional for CIS 520 to turn in: Sipser 2.23
Recommended (don't turn in): Sipser 2.5, 2.7, 2.12, 2.30a,b,c 		Wednesday, November 15
6 Turing Machines Turn in: Sipser 3.8b,c, 3.15b,c,d,e
Additional for CIS 520 to turn in: Sipser 3.13
Recommended (don't turn in): Sipser 3.2, 3.5 		Monday, November 27
7 Decidability Turn in: Sipser 4.3, 4.12
Additional for CIS 520 to turn in: Sipser 4.14
Recommended (don't turn in): Sipser 4.11, 4.13 		Friday, December 1

About the assignments

Working diligently on the assignments is key to understanding the material in this course. Often it is not until you attempt to write down a formal description, diagram, or proof that you really "get" a concept.

Each assignment lists "recommended" problems that are not to be turned in for grading. The book has solutions to many of these and other problems. Working on these problems and then comparing your solution to the text book can be an effective method of mastering the material.

Assignments are due at the beginning of class on the due date indicated. Use machine copy if at all possible - in any case, writing and diagrams must be neat and legible. Work turned in must be your own - if you collaborate with anyone on any of the problems, or obtain part or all of a solution from another source, indicate that on the work you turn in. Academic honesty is expected and cases of suspected dishonesty will be handled according to university policy. In particular, copying someone else's work (including material found on the web) will not be tolerated. If solutions to assignments are obtained from outside sources, the source must be cited.