Note: This is the original class schedule, as planned for a fully face-to-face class. With the transition to online teaching, this is no longer accurate but is kept for reference. Please see the current schedule for current information.
The following gives a day-by-day breakdown of topics covered, readings assigned, and assignment handouts/due dates. Each topic includes several required readings that students should read before the topic is discussed in class – always look ahead a few days to see what readings you should be doing. Some topics also have supplemental (non-required) readings that students can look into if they want to delve more deeply into that topic.
The schedule in this class is flexible, and past dates will be updated to reflect what was actually covered. Future dates are always tentative and subject to change.
Topics: Class overview and syllabus review; introduction to theory of computing
Handout: Syllabus
Reading: Sections 0.1 – 0.2
Topics: Review of mathematical structures
Reading: Sections 0.3 – 0.4
Topics: Review of proof techniques
Assigned: Assignment 1
Reading: Section 1.1
Topics: Deterministic finite automata - day 1
Topics: Deterministic finite automata - day 2
Due: Assignment 1
Reading: Section 1.2
Topics: Nondeterministic finite automata
Assigned: Assignment 2
Reading: Sections 1.3 – 1.4
Topics: Regular expressions and non-regular languages (pumping lemma) - day 1
Topics: Regular expressions and non-regular languages (pumping lemma) - day 2
Due: Assignment 2
Topics: Review and problem day
Topics: Exam 1
Reading: Section 2.1
Topics: Context-Free Grammars - day 1
Assigned: Assignment 3
Reading: Section 2.1
Topics: Context-Free Grammars - day 2
Reading: Section 2.2
Topics: Pushdown automata
Reading: Section 2.3
Topics: Non-Context-Free Languages
Due: Assignment 3
Reading: Section 2.4
Topics: Deterministic Context-Free Languages and parsing
Assigned: Assignment 4
Reading: Chapter 3
Topics: Church-Turing Thesis - day 1
Topics: Church-Turing Thesis - day 2
Reading: Chapter 4
Topics: Decidability - day 1
Due: Assignment 4
Topics: Decidability - day 2
Topics: Review and problem day
Topics: Exam 2
Reading: Chapter 5
Topics: Reducability - day 1
Topics: Reducability - day 2
Reading: Section 6.1
Topics: Recursion Theorem
Reading: Sections 7.1 – 7.2
Topics: Time complexity basics and class P
Reading: Sections 7.3 – 7.5
Topics: Class NP and NP-completeness
Topics: Miscellaneous topics (TBD) - day 1
Topics: Miscellaneous topics (TBD) - day 2
Topics: Last day of class – review
Wednesday, May 6, 3:30-6:30