Note: This schedule is being updated for the transition to online teaching, and so is a little uncertain at the moment. For reference and list of topics in the originally-planned course, see the original schedule.
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.
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
Classes temporarily suspended this week as we move to online teaching.
In the online class structure that follows, topics are organized by week rather than by lecture-day. Each week corresponds to a module in Canvas, and the module (with quiz) must be completed by the end of the week.
Reading: Chapter 3
Topics: Church-Turing Thesis
Due: Assignment 4 – due April 1 at 11:59pm
Reading: Chapter 4
Topics: Decidability
Monday: Mid-term Exam 2 (more information in Canvas)
Wednesday: Mid-term Exam 2 solutions discussion
Reading: Chapter 5
Topics: Reducability
Assigned: Assignment 5
Reading: Chapter 7
Topics: Time Complexity
Due: Assignment 5 – due Wednesday, April 29 at 3:30pm
Monday Topic: To be determined (class choice)
Wednesday Topic: Review for final exam
Wednesday, May 6, 3:30-6:30