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 26th)
Week 2
Topics: Alphabets, Strings, Numbers, Languages, Sets
Reading: Sections 0.2, 0.3, 0.4, and 1.1
Quiz 2 (Fri, Feb 2nd)
Week 3
Topics: Regular Languages, Closure Properties, Product Construction
Reading: Sections 1.1
Quiz 3 (Fri, Feb 9th)
Week 4
Topics: NFA’s, NFA to DFA Conversion
Reading: Sections 1.2 and 1.3
Quiz 4 (Fri, Feb 16th)
Week 5
Topics: More Closure Properties, Regular Expressions, Pumping Lemma
Reading: Sections 1.2, 1.3, and 1.4
Quiz 5 (Fri, Feb 23rd)
Week 6
Topics: Context-Free Grammars, Pushdown Automata
Reading: Sections 2.1 and 2.2
Quiz 6 (Fri, Mar 1st)
Week 7
Topics: Chomsky Normal Form, CFL Closure Properties
Reading: Sections 2.1 and 2.2
No Quiz on Friday
Week 8
Spring Break!
Week 9
Topics: Turing Machines
Reading: Sections 3.1 and 3.2
Quiz 7 (Fri, Mar 22nd)
Week 10
Topics: Computability and Church-Turing Thesis
Reading: Sections 3.1 and 3.2
Quiz 8 (Fri, Mar 29th)
Week 11
Topics: Decidability and Undecidability
Reading: Sections 4.1 and 4.2
Quiz 9 (Fri, Apr 5th)
Week 12
Topics: Reductions, Time Complexity
Reading: Sections 5.1, 5.3, and 7.1
No Quiz on Friday
Week 13
Topics: Polynomial Time, Time Hierarchy Theorem
Reading: Sections 7.1, 7.2, and 9.1
Quiz 10 (Fri, Apr 19th)
Week 14
Topics: Non-Deterministic Polynomial Time, More Reductions
Reading: Sections 7.3 and 7.4
Quiz 11 (Fri, Apr 26st)
Week 15
Topics: Complexity Theory, Classes, and Zoo
Reading: Sections 7.4, 8.3, and 8.4
No Quiz on Friday
Final Exam
Thursday, May 9th at 2pm ET in SCI 204