Week | Topic | Reading |
---|---|---|
Week 1, 4/2-4 |
| Sipser, Chapter 0 Sipser, Section 1.1 Selected lecture notes |
Week 2, 4/9-11 |
| Sipser, Section 1.2
Selected lecture notes |
Week 3, 4/16-18 |
| Sipser, Section 1.2
Selected lecture notes |
Week 4, 4/23-25 |
| Sipser, Sections 1.3, 1.4
Selected lecture notes |
Week 5, 4/30-5/2 |
| Sipser, Chapter 1
Selected lecture notes |
Week 6, 5/7-9 |
| Sipser, Sections 2.1, 2.2
Selected lecture notes |
Week 7, 5/14-16 |
| Sipser, Sections 2.2, 2.3
Selected lecture notes |
Week 8, 5/21-23 |
| Sipser, Sections 3.1, 3.2
Selected lecture notes |
Week 9, 5/28-30 |
| Sipser, Sections 3.3, 4.1, 4.2 |
Week 10, 6/4-6 |
| Sipser, Sections 5.1, 5.2
Selected lecture notes |
Final Exam 8 AM Thursday, June 13 |
Assignments are due at the beginning of class on the due date indicated. Writing and diagrams must be legible - use machine copy if possible. Work turned in should be your own - if you collaborate with anyone on any of the problems, 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.
Electronic copy of possible solutions to exercises will not be available, but I will provide a paper copy on request.
Assignment | Topic | Problems | Due |
---|---|---|---|
1 | Deterministic Finite Automata | Turn in: Sipser 1.4a,b,c,d, 1.29
Additional for CIS 520 to turn in: Sipser 1.26 Recommended (don't turn in): Sipser 1.1, 1.2, 1.3 | 4/11 |
2 | Nondeterminism | Turn in: Sipser 1.5a,b,c,f, 1.10, 1.11
Additional for CIS 520 to turn in: Sipser 1.42 Recommended (don't turn in): Sipser 1.6, 1.7, 1.8, 1.9, 1.12 | 4/18 |
3 | Regular Expressions, Pumping Lemma | Sipser 1.16a, 1.23a,b, 1.36
Additional for CIS 520: Sipser 1.41 Recommended (don't turn in): Sipser 1.13, 1.14, 1.15, 1.17 | 4/30 |
4 | Context Free Grammars | Turn in: Sipser 2.6a,b, 2.15, 2.19
Additional for CIS 520 to turn in: Sipser 2.25 Recommended (don't turn in):: Sipser 2.1, 2.3, 2.4, 2.9 | 5/14 |
5 | Pushdown Automata, Non CFLs | Turn in: Sipser 2.13, 2.17, 2.18d, 2.26
Additional for CIS 520 to turn in: Sipser 2.27 Recommended (don't turn in): Sipser 2.5, 2.7, 2.12, 2.18a,b,c | 5/23 |
6 | Turing Machines | Turn in: Sipser 3.8, 3.14
Additional for CIS 520 to turn in: Sipser 3.13 Recommended (don't turn in): Sipser 3.2, 3.5 | 5/30 |
7 | Decidability | Turn in: Sipser 4.3, 4.10, 4.12
Additional for CIS 520 to turn in: Sipser 4.13 | 6/6 |
Last updated 2002/06/05 14:22:09