Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 05	None		No class yet

	Wed	Jan 07	Introduction to the course Discrete mathematics review	P-NP-NP-Complete (Picture) Compexity Classes

2	Mon	Jan 12	Languages Proofs!	Chapter 0 Languages Notes Proofs Notes Proof Examples Induction Proofs Active Intro to Discrete Math	HW 0 due

	Wed	Jan 14	Proofs Other stuff

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

	Wed	Jan 21	DFAs

4	Mon	Jan 26	NFAs	Chapter 1.2	HW 2 due

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

5	Mon	Feb 02	Nonregular Languages	Chapter 1.4 Pumping Lemma for regular languages (Wikipedia)	HW 4 due

	Wed	Feb 04	Non-regular languages

6	Mon	Feb 09	Winter Break		No Class

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

7	Mon	Feb 16	Chapters 0-1	Paper Pencil	Exam 1

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

8	Mon	Feb 23	Pushdown Automata	Chapter 2.2

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

9	Mon	Mar 02	Non-Context-Free Languages	CFL Pumping Lemma	HW 7 due

	Wed	Mar 04	Equality of CFGs (Problem 2.6b) CFG wrap-up		HW 8 due

10	Mon	Mar 09	Turing Machines	Chapter 3.1 Turing Machines (PowerPoint) Turing Machine State Diagram Turing Machine Cartoon Turing Machine Simulator xkcd: Candy Button Paper xkcd: A Bunch of Rocks LEGO Turing machine

	Wed	Mar 11	Turing Machine Variants Algorithms Church-Turing Thesis	Chapter 3.2-3.3 Turing Machine Variants (PowerPoint) Turing Machine Simulator	HW 8 redo (2.31 and 2.32)

Spring Break Week

11	Mon	Mar 23	Church-Turing Thesis	Church-Turing Thesis Church-Turing Thesis Definitions	HW 9 due

	Wed	Mar 25	Decidable Languages	Chapter 4.1 Decidability Notes

12	Mon	Mar 30	Chapters 0-3	Pencil Paper Definition/Results sheet	Exam 2

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

13	Mon	Apr 06	Reducibility	Chapter 5.1 (skim 220-226) Reducibility Notes	HW 10 due

	Wed	Apr 08	PCP Reducibility	Chapter 5.2 (skim) Chapter 5.3 Reducibility Notes

14	Mon	Apr 13	Reductions Complexity	Chapter 7.1 Reducibility Notes NP-Complete Notes

	Wed	Apr 15	Complexity	Chapter 7.2-7.3 (Skim 290-291) Complexity Notes NP-Complete Notes	HW 11 due

15	Mon	Apr 20	NP NP-Complete	Chapter 7.4-7.5 (skim 305 to top of 311 and 314-318) Reduction Examples Complexity Notes	HW 12 due

	Wed	Apr 22	Final Exam Review Semester Wrap-up		HW 13 due (Thursday by 9am)

Ex	Mon	Apr 27	The whole book	Pen or Pencil Paper Definition/Results Sheet Brain	Exam 3 12:30-2:30pm