Welcome to Theory of Computation!
There will be weekly lectures and labs (attendance required).
There will also be discussions on Slack.
Please see the course syllabus for more information.
Please direct any questions or concerns to Michael Wehar (mwehar1@swarthmore.edu).
Week 1
Topics: What it Computation?, DFA’s
Reading: Sections 0.2 and 1.1
Quiz 1 (Fri, Jan 20th)
Week 2
Topics: Alphabets, Strings, Numbers, Languages, Sets
Reading: Sections 0.2, 0.3, 0.4, and 1.1
Quiz 2 (Fri, Jan 27th)
Week 3
Topics: Regular Languages, Closure Properties, Product Construction
Reading: Sections 1.1
Quiz 3 (Fri, Feb 3rd)
Week 4
Topics: NFA’s, NFA to DFA Conversion
Reading: Sections 1.2 and 1.3
Quiz 4 (Fri, Feb 10th)
Week 5
Topics: More Closure Properties, Regular Expressions, Pumping Lemma
Reading: Sections 1.2, 1.3, and 1.4
Quiz 5 (Fri, Feb 17th)
Week 6
Topics: Context-Free Grammars, Pushdown Automata
Reading: Sections 2.1 and 2.2
Quiz 6 (Fri, Feb 24th)
Week 7
Topics: Chomsky Normal Form, CFL Closure Properties
Reading: Sections 2.1 and 2.2
No Lab on Friday
Week 8
Spring Break!
Week 9
Topics: Turing Machines
Reading: Sections 3.1 and 3.2
Quiz 7 (Fri, Mar 17th)
Week 10
Topics: Computability and Church-Turing Thesis
Reading: Sections 3.1 and 3.2
Quiz 8 (Fri, Mar 24th)
Week 11
Topics: Decidability and Undecidability
Reading: Sections 4.1 and 4.2
Homework 5 Assigned
Quiz 9 (Fri, Mar 31st)
Week 12
Topics: Reductions, Time Complexity
Reading: Sections 5.1, 5.3, and 7.1
Quiz 10 (Fri, Apr 7th)
Week 13
Topics: Polynomial Time, Time Hierarchy Theorem
Reading: Sections 7.1, 7.2, and 9.1
Homework 6 Assigned
Quiz 11 (Fri, Apr 14th)
Week 14
Topics: Non-Deterministic Polynomial Time, More Reductions
Reading: Sections 7.3 and 7.4
Quiz 12 (Fri, Apr 21st)
Week 15
Topics: Complexity Theory, Classes, and Zoo
Reading: Sections 7.4, 8.3, and 8.4
TBA
Final Exam
TBA