Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 07	None		No class yet

	Wed	Jan 09	Introduction to the course Discrete mathematics review	P-NP-NP-Complete (Picture) Computational Complexity (see picture) Compexity Classes

2	Mon	Jan 14	Languages Proofs!	Chapter 0 Languages Notes Proofs Notes Proof Examples Induction Proofs HW0 Answers	HW 0 due

	Wed	Jan 16	Proofs Other stuff

3	Mon	Jan 21	Finite Automata	Chapter 1.1 Finite State Machines Notes JFlap JFlap Tutorial	HW 1 due

	Wed	Jan 23	DFAs		HW 2 due

4	Mon	Jan 28	NFAs	Chapter 1.2

	Wed	Jan 30	Regular Expressions	Chapter 1.3 Regular Expressions xkcd: Regular Expressions	HW 3 due

5	Mon	Feb 04	Nonregular Languages	Chapter 1.4	HW 4 due

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

6	Mon	Feb 11	Winter Break		No Class

	Wed	Feb 13	Chapters 0-1	Paper Pencil	Exam 1

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

	Wed	Feb 20	Pushdown Automata	Chapter 2.2

8	Mon	Feb 25	Pushdown Automata Non-Context-Free Languages	Chapter 2.3	HW 6 due

	Wed	Feb 27	Non-Context-Free Languages	CFL Pumping Lemma	HW 7 due

9	Mon	Mar 04	Turing Machines	Chapter 3.1 Turing Machine State Diagram Turing Machine Cartoon Turing Machine Applet TM Program xkcd: Candy Button Paper xkcd: A Bunch of Rocks LEGO Turing machine	HW 8 due

	Wed	Mar 06	Turing Machine Variants Algorithms	Chapter 3.2-3.3 Turing Machines (PowerPoint) Turing Machine Variants (PowerPoint)

10	Mon	Mar 11	Turing Machines Church-Turing Thesis	Church-Turing Thesis Definitions Church Turing Thesis

	Wed	Mar 13	Quantum Computing (?)		HW 9 due

Spring Break Week

11	Mon	Mar 25	Decidable Languages	Chapter 4.1 Decidability Notes

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

12	Mon	Apr 01	Undecidability	Chapter 4.2 Halting Problem Notes How Dr. Seuss would prove the halting problem undecidable

	Wed	Apr 03	Reducibility	Chapter 5.1 (skim 220-226) Reducibility Notes

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

	Wed	Apr 10	Reducibility

14	Mon	Apr 15	Complexity	Chapter 7.1-7.2 Complexity Notes NP-Complete Notes	HW 11 due

	Wed	Apr 17	NP NP-Complete	Chapter 7.3-7.5 Reduction Examples Complexity Notes	HW 12 due

15	Mon	Apr 22	Quantum Computing	How to do 2ⁿ things all at once xkcd: Quantum Teleportation Quantum Finish

	Wed	Apr 24	Final Exam Review Semester Wrap-up		HW 13 due

Ex	Mon	Apr 29	The whole book	Pen or Pencil Paper Definition/Results Sheet Brain	Exam 3 9:00am