CS-321: Introduction to Theory of Computation

Course Schedule

Tentative schedule (check frequently for possible changes)

Week#	Monday	Tuesday	Wednesday	Thursday	Friday
Week #1 June 22-June 26	Topics: Preliminaries Readings: Section 1.1	Topics: Proof Techniques. Readings: Section 1.1 Examples on proof techniques. Notes: Homework 1 out, due June 30	Topics: Formal Languages Readings: Section 1.2 (the part on languages),Examples on induction over languages	Topics: DFAs Readings: Section 2.1	Topics: DFAs cont. and NFAs Readings: Section 2.2
Week #2 June 29 - July 3	Topics: NFAs Readings: Section 2.2 Notes: Quiz 1 (1.1to 2.1)	Topics: Equivalence of DFAs and NFAs Readings: Section 2.3 Notes: Homework 2 out, due July 7	Topics: Regular expressions. Readings: Section 3.1	Topics: Regular Expressions, REs to NFAs Readings: Section 3.1, 3.2	No Class
Week #3 July 6-July 10	Topics: Closure properties of Regular Languages	Topics: Closure properties of Regular Languages cont. and some questions about regular languages Readings: Section 4.1,4.2 Notes: Quiz 2(2.2 to 3.1) Notes: Homework 3 out, due July 14	Topics: Pumping lemma Readings: Section 4.3, Pumping Lemma DO's and DONT's (Dr. Alan Fern)	Topics: Pumping lemma cont. Readings: Section 4.3, Dr. Fern's notes	No Class
Week #4 July 13 - July 17	Topics: Context free grammars. Readings: Section 5.1 Notes: Quiz 3 (4.1 to 4.3)	Topics: CFGs, Parsing Readings: Section 5.1, 5.2 Notes: Homework 4 out, due July 21	Topics: Parsing and ambiguity. Readings: Section 5.2	Topics: NPDAs Readings: Section 7.1	Review class (4.3 to 5.2)
Week #5 July 20 - July 24	Topics: From CFGs to NPDAs. Readings: Section 7.2 Notes: Quiz 4 (5.1 to 5.2)	Topics: From NPDAs to CFGs Readings: Section 7.2	Review for mid-term exam.	Mid-Term exam: Sections 1.1 to 4.3 ( 10:00-11:00am at class location) (Closed-book, closed-notes)	Review class (7.1, 7.2) Notes: Homework 5 out, due July 31
Week #6 July 27 - July 31	Topics: Closure properties of CFLs. Readings: Section 8.2. Notes: Quiz 5 (7.1, 7.2)	Topics: Turing Machines. Readings: Section 9.1	Topics: Turing Machines. Readings: Section 9.1	Topics: Turing Machines cont'd. Readings: Section 9.1 Notes: Homework 6 out, due August 6	Review class (8.2, 9.1)
Week #7 August 3-August 7	Topics: Halting problem Readings: Section 12.1 Notes: Quiz 6 (8.2, 9.1)	Topics: Undecidable problems and Reduction Readings: Section 12.1	Topics: Undecidable problems and Reduction cont. Readings: Section 12.1	Review for final exam	No Class

Final Exam: August 13, 9:30am -10:50am (Class room location OWEN-101)


Go back to the home page