Schedule for weeks 1 through 16

Wk	Day	Date	Topic	Resources	Events

1	Mon	Jan 09	Introduction to the course Discrete mathematics review	P-NP-NP-Complete (Picture) Compexity Classes

	Wed	Jan 11	Languages Proofs!	Chapter 0 Languages Notes Proofs Notes Proof Examples Induction Proofs AIDMA 2.7.2

2	Mon	Jan 16	Proofs Other stuff

	Wed	Jan 18	Finite Automata	Chapter 1.1 Finite State Machines Notes JFlap JFlap Tutorial	HW 1 due

3	Mon	Jan 23	DFAs

	Wed	Jan 25	NFAs	Chapter 1.2	HW 2 due

4	Mon	Jan 30	Regular Expressions	Chapter 1.3 Regular Expressions Notes xkcd: Regular Expressions	HW 3 due

	Wed	Feb 01	Nonregular Languages	Chapter 1.4 Pumping Lemma for regular languages (Wikipedia)	HW 4 due

5	Mon	Feb 06	Non-regular languages

	Wed	Feb 08	Chapters 0-1 (Catch up and review)	Exam 1 Format	HW 5 due

6	Mon	Feb 13	Winter Break		No Class

	Wed	Feb 15	Chapters 0-1	Paper Pencil	Exam 1

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

	Wed	Feb 22	Nothing		Icepocalypse 2023: No class

8	Mon	Feb 27	Pushdown Automata	Chapter 2.2 (Skim Proof Idea/Proof of Lemma 2.27 if you wish (most of 121-124))

	Wed	Mar 01	Pushdown Automata Non-Context-Free Languages	Chapter 2.3	HW 6 due

9	Mon	Mar 06	Non-Context-Free Languages	Notes/Solutions from last time CFL Pumping Lemma Notes

	Wed	Mar 08	Turing Machines	Chapter 3.1 Turing Machines (PowerPoint) Turing Machine State Diagram Turing Machine Simulator xkcd: Candy Button Paper xkcd: A Bunch of Rocks LEGO Turing machine	HW 7 due

10	Mon	Mar 13	Turing Machine Variants Algorithms Church-Turing Thesis	Chapter 3.2-3.3 Turing Machine Variants (PowerPoint) Turing Machine Simulator	HW 8 due

	Wed	Mar 15	Church-Turing Thesis	Church-Turing Thesis Notes Church-Turing Thesis Definitions	HW 9 due

Spring Break Week

11	Mon	Mar 27	Review

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

12	Mon	Apr 03	Decidable Languages	Chapter 4.1 Decidability Notes

	Wed	Apr 05	Undecidability	Chapter 4.2 Halting Problem Notes Sample Decidable/Undecidable Proofs (from Ch 4 and 5) How Dr. Seuss would prove the halting problem undecidable

13	Mon	Apr 10	None		No class

	Wed	Apr 12	Reducibility	Chapter 5.1 Reducibility Notes	HW 10 now due Friday!

	Fri	Apr 14	Not a class day		HW 10 due

14	Mon	Apr 17	PCP Reducibility	Chapter 5.2 (skim 228-233) Chapter 5.3 Reducibility Notes

	Wed	Apr 19	Reductions Complexity	Chapter 7.1 Reducibility Notes NP-Complete Slides

15	Mon	Apr 24	Complexity	Chapter 7.2-7.3 (Skim 290-291) NP-Completeness Notes NP-Complete Slides	HW 11 due

	Wed	Apr 26	Review NP ~~NP-Complete~~	~~Chapter 7.4 (skim 305 to top of 310)~~ ~~Reduction Examples~~	HW 12 due

	Fri	Apr 28	Not a class day		HW 13 due

Ex	Tue	May 02	The whole book	Pen or Pencil Paper Book and notes Definition/Results Sheet Computer (for notes, not for chatGPT or Google) Brain	Exam 3 9-11am