| [ CIS 420/520 Home Page | Syllabus | Announcements ] | Last updated 2007/11/26 10:13:48 |
| Assignment | Topic | Problems | Due |
|---|---|---|---|
| 0 | Math review | To sharpen your math skills, you should do the exercises and
problems in Sipser chapter 0. If you don't need sharpening,
it should only take a few minutes to mentally work up the answers.
Otherwise, it is worth writing out some or all of the solutions.
You do not need to turn in this assignment. | Friday, September 28 |
| 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 5 |
| 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 15 |
| 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 24 |
| 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 5 |
| 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 | Friday, November 16 New date! |
| 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 26 |
| 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, November 30 |
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.