Here is a tentative schedule of what I have planned for each week. I reserve the right to change planned class session contents up to the point of that class session (but I will try not to).
Week 1—Mathematical literacy
Topic
Read before class
Assigned
Due
#1A: Tues 1/23
mathematical literacy
Quiz 1
Lab 1A
#1B: Thurs 1/25
Math literacy (cont.)
Sipser §0
lab 1B
homework 1 & 2
Sat 1/27
Labs 1A and 1B
Week 2—Automata
Topic
Read before class
Assigned
Due
#2A: Tues 1/30
Finite automata
Sipser §1.1
Lab 2A
#1B: Thurs 2/1
Nondeterminism; equivalence.
Sipser §1.2
Lab 2B
Sat 2/3
Labs 2A and 2B
Week 3—Regular Languages
Topic
Read before class
Assigned
Due
#3A: Tues 2/6
Regular Expressions; Equivalence to DFAs
Sipser §1.3
Lab 3A
Homework 3
Homeworks 1 and 2
#3B: Thurs 2/8
Regular Operators; Closure Properties
Review the closure proofs for DFAs, NFAs, and regular expressions in Sipser §1.1-1.3. These include the proofs that union (1.45), concatenation (1.47), and kleene star (1.49) are closed under the regular languages.
Lab 3B
Sat 2/10
Labs 3A and 3B
Week 4—Grammars
Topic
Read before class
Assigned
Due
#4A: Tues 2/13
Irregularity
Sipser §1.4, Malkin (See below).
Lab 4A
Homework 4
Homework 3
#4B: Thurs 2/15
Context-Free Grammars
Sipser §2.1
Lab 4B
Sat 2/17
Labs 4A and 4B
See Malkin (2022) for additional (optional) reading on the MyHill-Nerode theorem. Sipser only covers Myhill-Nerode briefly on pg. 90 in the exercises of §1.
Week 5—Automata Exam
Topic
Read before class
Assigned
Due
#5A: Tues 2/20
Exam
N/A
Exam 1 distributed (Due Tues 27th).
Homework 4
#5B: Thurs 2/15
Exam
N/A
Continue Exam 1
Week 6—Turing Machines
Topic
Read before class
Assigned
Due
#6A: 2/27
Turing Machines
Sipser §3 and §3.1. Optional—Erickson §6.1-6.5, Arora and Barak §1.2.
Lab 6A
Homework 6
Exam 1
#6B: Thurs 2/29
TM Variants
Sipser §3.2. Optional—Erickson §6.6, §6.7, and §9, Arora and Barak §2.1.2.
Lab 6B
Sat 3/2
Labs 6A and 6B
Week 7—The Universal Turing Machine (UTM)
Topic
Read before class
Assigned
Due
#7A: Tues 3/5
Nondeterministic TMs, equivalence.
Sipser §3.2 (on NTMs). Optional—Arora and Barak §2.1.2.
Lab 7A
Homework 7
Homework 6
#7B: Thurs 3/7
Encodings of everything (and I mean _everything!_)
Arora and barak §1.1.1, §1.3. Optional—Erickson §6.8.
Lab 7B
Sat 3/9
Labs 7A and 7B
Week 8—Decidability & More Math
Topic
Read before class
Assigned
Due
#8A: Tues 3/12
Decidability
Sipser §4.1.
Lab 8A
Homework 8
Homework 7
#8B: Thurs 3/14
Math Literacy Part II.
Sipser §4.2 up to "An undecidable language" (pp 207).
Lab 8B
Sat 3/16
Spring break begins :)
Labs 8A and 8B
Mon 4/1
Spring break ends :(
Week 9–Undecidability, Reducibility
Topic
Read before class
Assigned
Due
#9A: Tues 4/2
Undecidability & Reducibility
Sipser §4.2 "An Undecidable Language" through end of section; Sipser §5.1.
Lab 9A
Homework 9
Homework 8
#9B: Thurs 4/4
Mapping Reducibility; The Post Correspondence Problem (PCP).
Sipser §5.2 (Skip proof of Theorem 5.15), §5.3 and Osera's "Undecidable Proof Strategies" (see below).
No Homework (but sublinear space complexity will be on Exam 3).
Exam 3 released.
Lab 14A
Homework 13
#14B: 5/9
Syntactic models of computation---The Typed and Untyped Lambda Calculus
N/A
N/A
ALL HOMEWORK & LABS (except Lab 14A). I expect all late work to be handed in no later than May 9th, and will not be accepting any late submissions past this date. This is a hard deadline.
5/11
Lab 14A
Week (Complexity Exam)
Topic
Read before class
Assigned
Due
#15A: 5/14
Final Exam
Exam 3
#15B: 5/16
Final Exam
Exam 3 (Late due date)
#15B: 5/17
Final Exam
Exam 3 (HARD DEADLINE; PLEASE HAVE SUBMITTED BY END OF DAY)