CPS360, Summer Semester 1998
Instructor: Travis Doom

This assignment calendar should be considered dynamic; it is subject to change depending upon class performance. This page was last modified on Monday, 29-Jun-1998 12:23:17 EDT. Assignments prior to this date should be accurate. Assignments listed after this date are projections and may not correspond to the actual material and assignments presented in class.

Week 1: Equivalence of Regular Languages and Finite Automata
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 5/18 Class overview, Review of prerequisite material, Symbols, Alphabets, Strings and Languages, Quiz #0 Read Ch. 1 (esp. 1.5), and 2;
Ch. 1 Problems: 43 - 51
W 5/20 Regular Languages, Regular Expressions, Finite Automata Read Ch. 3;
Ch. 3 Problems: 1-3, 8-9, 21-24, 30, 32, 34
F 5/22 Nondeterminism, Nondeterministic Finite Automata, Lambda-Transitions, Kleene's Theorem, Quiz #1 Read Ch. 4;
Ch. 4 Problems: 1, 5, 8, 11-16, 18, 31, 38

Week 2: Regular and Non-regular Languages
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 5/25 Memorial Day Observed, No Class No Class
W 5/27 Criterion for Regularity, the Indistinguishability Relation, Minimal Finite Automata Read Ch. 5;
Ch. 5 Problems: 2, 10, 25-27
F 5/29 The Pumping Lemma for RLs, Decision Problems, Quiz #2 Ch. 5 Problems: 28, 34, 35, 39-41

Week 3: CFLs, CFGs, and Pushdown Automata
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 6/1 Context-Free Grammars, Context-Free Languages, Ambiguity Read Ch 6;
Ch. 6 Problems: 1, 3-7, 13, 14, 17, 25, 27
W 6/3 Pushdown Automata Read Ch 7 (7.1-7.5);
Ch. 7 Problems: 1-2, 5-7, 13, 14, 29
F 6/5 Recitation, The Pumping Lemma for CFLs, Quiz #3 Read Ch 8;
Ch. 8 Problems: 1, 6, 10

Week 4: Turing Machines
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 6/8 Closure properties of CFLs, Noncontext-Free Languages, Introduction to Turing Machines Read Ch 9.1 - 9.4
Ch. 9 Problems: 1-2, 4, 6-8
W 6/10 Review of Course Material, Computation on TMs Prepare for Midterm Exam
F 6/12 Midterm Examination Relax

Week 5: Recursive and Recursively Enumerable Languages
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 6/15 Midterm Questions/Answers, Computing partial functions with Turing Machines, Unary representation, Multitape TMs Review Ch 9.1-9.4, Read Ch 9.5
Ch. 9 Problems: 9-10, 15ab, 31
W 6/17 Nondeterministic TMs, the Universal TM, Recursively Enumerable and Recursive Languages Read Ch 9.5-9.7, Ch 10.1
Ch. 9 Problems: 38, 41, 47-48
Ch. 10 Problems: 1, 6,
F 6/19 Undecidable langugages, the halting problem, the existance of non-RE languages, coRE languages, unsolvable decision problems, Quiz #4 Read Ch 10
Ch. 10 Problems: 7, 12, 16, 21no, 31

Week 6: Completeing the Chomsky Hierarchy
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 6/22 The Chomsky hierachy, unrestricted Grammars for TMs, context-sensitive Grammars for linear-bounded automata Read Ch 11
Ch. 11 Problems: 1, 3, 11, 13, 14, 17, 20
W 6/24 Group Presentation Day (@10 min) Review course material
F 6/26 Time and space complexity, P and NP, complete problems, reduction, decision problems, Quiz #5 Assigned Reading from Ch. 36 of CLR

Week 7: Conclusion
DATE TOPIC / READINGS HOMEWORK ASSIGNMENT
M 6/29 Class Review Prepare for Final
W 7/1 Final Examination End of Semester (1st half, summer)

Travis Doom, travis.doom@wright.edu.

Last modified: 06/29/98