Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 10	None		No class yet

	Wed	Jan 12	Introduction to the course Discrete mathematics review	Course website

2	Mon	Jan 17	Languages Proofs!	Chapter 0 Languages Notes Proofs Notes Proof Examples Induction Proofs P-NP-NP-Complete Computational Complexity (Just for picture) Compexity Classes	HW 0 due

	Wed	Jan 19	More proofs and other review stuff		HW 1 due

3	Mon	Jan 24	Finite Automata	Chapter 1.1 Finite State Machines Notes JFlap JFlap Tutorial

	Wed	Jan 26	DFAs		HW 2 due

4	Mon	Jan 31	NFAs	Chapter 1.2

	Wed	Feb 02	Snow	Snow	Snow Day!

5	Mon	Feb 07	Regular Expressions	Chapter 1.3 xkcd: Regular Expressions	HW 3 due

	Wed	Feb 09	Nonregular Languages	Chapter 1.4	HW 4 due (Friday)

6	Mon	Feb 14	Winter Break		No Class

	Wed	Feb 16	Chapters 0-1 (Catch up and review)		HW 5 due (Friday)

7	Mon	Feb 21	Context-Free Grammar	Chapter 2.1 Grammar Notes C++ Grammar Java Grammar A simple grammar

	Wed	Feb 23	Chapters 0-1		Exam 1

8	Mon	Feb 28	Pushdown Automata Non-Context-Free Languages	Chapter 2.2	HW 6 due

	Wed	Mar 02	Non-Context-Free Languages	Chapter 2.3	HW 7 due

9	Mon	Mar 07	Pushdown Automata Non-Context-Free Languages		HW 8 due

	Wed	Mar 09	Turing Machines	Chapter 3.1 Turing Machine stuff (See picture near middle) Turing Machine Cartoon Turing Machine Applet TM Program xkcd: Candy Button Paper xkcd: A Bunch of Rocks LEGO Turing machine

10	Mon	Mar 14	Turing Machine Variants Algorithms	Chapter 3.2-3.3

	Wed	Mar 16	Turing Machines Church-Turing Thesis	The Interactive Nature of Computing: Refuting the Strong Church-Turing Thesis	HW 9 due

Spring Break Week

11	Mon	Mar 28	Decidable Languages	Chapter 4.1 Decidability Notes

	Wed	Mar 30	Chapters 0-3	Pencil Paper Definition/Results sheet	Exam #2

12	Mon	Apr 04	The Halting Problem	Chapter 4.2 Halting Problem Notes

	Wed	Apr 06	Reducibility	Chapter 5.1 Reducibility Notes

13	Mon	Apr 11	Reducibility	Chapter 5.2-5.3 Reducibility Notes	HW 10 due

	Wed	Apr 13	Reducibility

14	Mon	Apr 18	Complexity	Chapter 7.1-7.2 Complexity Notes	HW 11 due

	Wed	Apr 20	NP NP-Complete	Chapter 7.3-7.4 NP-Complete Notes	HW 12 due

15	Mon	Apr 25	NP-Complete	Chapter 7.4-7.5 Reduction Examples Complexity Notes

	Wed	Apr 27	Final Exam Review Semester Wrap-up		HW 13 due (Friday--no lates!)

Ex	Wed	May 04	The whole book	Pen or Pencil Paper Definition/Results Sheet Brain	Exam #3 @ 12:30pm