Weekly Notes 
Topics 
Reading 
Assignments 
Week 1 
 Startup tasks:
 Syllabus, Survey, and call the roll
 Edited slides from the text are on (and may be updated) D2L. Please safeguard them.
 Monday  Big ideas in 420 (Chapter 1 slides):
 WF: Chapter 2 (and JiT math  Appendix A)
 An interesting video
whose first part covers countable and uncountable sets (Thanks, Jude!)
 Notes from previous semesters:

Chapters 1 and 2, App A 
HW1a Due Monday 9/4/17
HW1b Due Wednesday 9/6/17

Week 2 
 Chapter 2: Strings and Languages (we will use strings and languages all semester!)
 Notes from previous semesters:

Chapter 2 
HW1a Due Monday 9/4/17
HW1b Due Wednesday 9/6/17
HW2 Wednesday 9/14/16.

Week 3 
 Chapter 2: Strings and Languages (we will use strings and languages all semester!)
 Chapter 5: Finite State Machines (DFSM) (aka finite automata)
 FSM Machine Creator
 Notes from previous semesters:

Chapters 1, 3, 5 
HW2 Wednesday 9/14/16.
HW3 Due 9/20/17.

Week 4 
 Chapter 5: More Finite State Machines
 Chapter 6: Regular Expressions
 Exam 1 after Reg Exp

Chapter 5 
HW3 is here Due Wed 9/20/17
HW4 is here Due Wed 9/27/17

Week 5 
 Chapter 6: Regular Expressions
 Exam soon  Probably Monday week after next
 Notes from previous semesters:
Chapter 8: Pumping Theorem and Closure Properties (SKIPPED)

Chapters 5 and 6 
HW4 is here Due Wed 9/27/17
HW5 is HW5 is due Fri 10/4/17

Week 6 
 Chapter 6: Regular Expressions (prove every FSM has equivalent RE)
 Chapter 8: Pumping Theorem and Closure Properties (SKIPPED)
 Chapter 10: Brief summary of RL, FSM, RE (we skip, but useful)
 Chapter 11: Context Free Grammars and Context Free Languages (CFG and CFL)
 Notes from previous semesters:
 Pumping Lemma for Regular Languages

Chapters 6, 8, and 10 
HW5 is HW5 is due Fri 10/4/17

Week 7 
 Exam Monday of this week: 10/9/17 on these
topics (updated for fall 2017)
 Chapter 11: Context Free Grammars and Context Free Languages (CFG and CFL)
 Friday: Fall break

Chapter 11 
HW5 is ready here
Due Mon 10/13/14
Exam next week

Week 8 
 D2L: PDA screencast and quiz due 11:59 p.m. Sunday 10/22/17
 Chapter 11: Context Free Grammars and Context Free Languages (CFG and CFL)
 Notes from previous semesters:

Chapter 2 
 HW6 is ready here Due FRI 10/29/14

Week 9 
 D2L: PDA screencast and quiz due 11:59 p.m. Sunday 10/22/17
 Chapter 11: Context Free Grammars and Context Free Languages (CFG and CFL)
 Chapter 11: Standard (eg Chomsky Normal) Form CFL
 Notes from previous semesters:


 HW7a and HW7b are ready here. Due Monday 10/30/17 and Wednesday 11/01/17

Week 10 
 Chapter 12: PDA and CFL
 Chapter 13: CFL or Not (ie Pumping Lemma)
 Chapter 16: Summary of CFL
 Chapter 17: Turing Machines: basics, variants, Universal TM
 Notes from previous semesters:

Chapter 2 
 HW7a and HW7b are ready here. Due Monday 10/30/17 and Wednesday 11/01/17

Week 11 
 Exam THIS WEEK on Wednesday 11/8/17 covering CFG, CFL, PDA
 Chapter 17: Turing Machines: basics, variants, Universal TM
 Notes from previous semesters:

Chapters 17 
 Exam 2: Wednesday 11/8/17
 HW8 is ready here Due FRI 11/17/17

Week 12 
Topics for the week:
 Chapter 18: ChurchTuring Thesis
 Chapter 19: Unsolvability of the Halting Problem [Trouble(<Trouble>)]
 Notes from previous semesters:


 HW8 is ready here Due FRI 11/17/17
 HW9 is ready here Due ??? 11/??/17

Week 13 
Thanksgiving Week!


 HW10 is ready here Due MON 11/12/12
 HW 11 is ready! Due Friday after break, 11/30/12
 HW 11 is ready! Due Friday
Wednesday after
break, 12/04/13 12/06/13

Week 14 
 Happy Thanksgiving!
 Do you want to schedule a review session next week? On Monday???
 Topics for the week:
 Chapter 19: Unsolvability of the Halting Problem [Trouble(<Trouble>)]
 Chapter 20: Decidable and Semidecidable Languages
 Chapter 21: Decidablity and Undecidablity Proofs
 Notes from previous semesters:


 HW 11 is ready! Due Friday
Wednesday after
break, 12/04/13 12/06/13

Week 15 
 Comprehensive Final Exam Next Week:
8:00 a.m.  10:00 a.m., Wednesday, December 13, 2017
 Topics for Final Exam from last
year
 Do you want to schedule a review session this week? On
Tuesday???
 Review Session: Tuesday 12/15/15 at 12:30. Room ???
 Topics for the week:
 Chapter 27: Introduction to the Analysis of Complexity
 Chapter 28: Time Complexity Classes: P and NP
 Chapter 24: The Chomsky Hierarchy and Beyond (Page 540 and 541 only)
 Notes from previous semesters:
 Chapter 7: Complexity
 Other topics:


 HW 11 is ready! Due Friday
Wednesday after
break, 12/04/13 12/06/13

Week 16 
 Comprehensive Final Exam:
8:00 a.m.  10:00 a.m., Wednesday, December 13, 2017


Comprehensive
Final Exam 
Notes for entire semester 