Schedule of topics and homework problem problems. Solutions to the problem sets will be discussed in the workshops. Problem sets are not turned in. See Reading Assignments for homework that will be turned in.
date  topic 
Thu Jan 19  Introduction. Mathematical notation. 
Tue Jan 24  Proofs. Problem Set 1. 
Thu Jan 26  Proofs. About "getting the direction right" in proofs. 
Tue Jan 31  Regular languages. Problem set 2: Construct the following NFA that accepts strings that end in 00. Use the proof of the reduction of a NFA to a DFA to construct the DFA for this language. Sipser 1.31, 1.36, 1.37, 1.38, 1.40, and 1.45. 
Thu Feb 2  Regular languages 
Tue Feb 7  Regular expressions. Do these problems and bring your solutions to the workshop: Exercises 1.18, 1.28, 1.21 (b), 1.24 (ad), 1.25, 1.26 (for T1 only), 1.27. 
Thu Feb 9  (Andrew Reinders teaches) See new readings to outline, listed on readings page. Work on these problems over the weekend and bring your solutions to class Tuesday: 1.49, 1.54. Optional makeup Quiz 2: complete and bring to class Tuesday. For workshop Wednesday, work on these exercises and bring your solutions to workshop: 2.4bcef, 2.5bcef, 2.6b, 2.9, 2.11, 2.27. 
Tue Feb 14  Finished regular languages and began contextfree languages. 
Thu Feb 16  Quiz 3. Enjoy your weekend. 
Tue Feb 21  More on context free languages. Work on these exercises and bring your solutions to workshop Wednesday:

Thu Feb 23  Finished context free languages. Makeup Quiz 3. Turn this in on class on Tuesday 28 Feb. You may use textbook and other academic sources, but you should not search for solutions to the specific problems or collaborate. Readings on Chapter 3 are due Sunday midnight. Study and/or solve following problems to prepare for class Tuesday and for the workshop Wednesday:

Tue Feb 28  Finish Pumping Lemma for CFL. In class: Problem 2.31. Workshop this week:

Thu Mar 1  Ch 3: ChurchTuring Thesis For class Tuesday Mar 6 class and workshop Wed Mar 7:
For class Thursday Mar 8, prepare by outlining Chapter 4 section 1 (pages 165  172). You will not turn in the outlines yet, but you should have them done. 
Tue Mar 6  Quiz 4: Pumping Lemma and PDAs. The questions will be similar to the problems listed for Feb 23 and Feb 28 (excluding 2.43). Ch 3: ChurchTuring Thesis 
Thu Mar 8  Ch 4: Decidability (Sec 4.1) Read and outline rest of Chapter 4. The turnin deadline (this time only) is NOON TUESDAY (March 20) rather than Sunday night. See also the problems for this week. 
Tue Mar 20  Ch 4: Decidability (Sec 4.2) Class today: Proof that the Halting Problem is undecidable Problems for workshop Wednesday: 4.3, 4.5, 4.9 (answer in book), 4.10, 4.6, 4.7, 4.28. Special reading assignment: read Section 5.1 to the end of Theorem 5.4 (pages 187192). Do not turn in yet. 
Thu Mar 22  Ch 5: Reducibility Class today: Theorems 5.1, 5.2, 5.3, 5.4 Reading assignment due Sunday night: outline of Section 5.1 and 5.3 (skip section 5.2). 
Tue Mar 27  Ch 5: Reducibility Class today: Sec. 5.3. and problems 5.28 (Rice's Theorem). We will start working on the following problems and finish them in workshop: 5.9, 5.13, 5.16 (busy beaver), 5.25, 5.30. Makeup Quiz 4 handed out. Due at start of class Tuesday April 3. 
Weds Mar 28  Workshop and Review Session: special 90+ minute session, beginning with Reducibility problems, followed by discussion of all material to date for review for midterm. 
Thu Mar 29  Midterm (Automata and Decidability) There will be six problems covering the following topics:
Reading assignment due *Monday* night at midnight: Outline Chapter 7.1  7.4. Although this is fairly long, you already know much of your material, so your notes can be brief. The details of the proof of the CookLevin are complicated, so at this point just try to grasp the highlevel idea: you can revise your notes on this proof for the next set of outlines. 
Tue Apr 3  Ch 7: Time Complexity Makeup Quiz 4 due. 
Wed April 4  Workshop and following class: 7.9, 7.11, 7.17 
Thu Apr 5  Ch 7: Time Complexity  problems 7.27 
Tue Apr 10  Ch 7: Time Complexity  problems 7.24, 7.26, 7.29, 7.36, 7.42 (Andrew Reinders runs class) Makeup Quiz 4 returned. 
Wed Apr 11  Workshop: problems 7.26, 7.29, 7.36, 7.42 
Thu Apr 12  Class Cancelled Reading outlines due Sunday: Chapter 8, Sections 8.18.3 
Tue Apr 17  Quiz 5 (Time Complexity) Space Complexity (Sec 8.18.3: outlines due midnight Monday April 16) Space complexity classes; Savitch's theorem; Quantified Boolean Formulas 
Wed April 18  Workshop  Problems 8.8, 8.9, 8.11, 8.16 
Thu Apr 19  Space Complexity PSPACEcompleteness; Games Makeup Quiz 5. Due in class Tuesday Apr 24. My notes on Savitch's Theorem, PSPACECompleteness, and Games. 
Tue Apr 24  Space Complexity (Definition of an oracle, Sec 9.2 up to page 349, and Section 10.3 Alternating Machines, pages 380386: outline due midnight Sunday April 22) Alternating machines; Polynomial Hierarchy 
Wed April 25  Workshop  Exercise 8.3, 8.13, 10.12, 10.13, 10.14. 
Thu Apr 26  Space Complexity & the Polynomial TIme Hieararchy My notes on the polynomial time hierarchy. Problem set on polynomial hierarchy. You will complete and turn in for a grade in class on Tue May 6. (This replaces a quiz.) 
Tue May 1  Conclusion of Time and Space Complexity 
Wed May 2  No workshop! 
Fri May 11  Final Exam (Complexity) 4:00pm5:30pm. You may bring your outlines and textbook. 