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
Week 2
Topics: Alphabets, Strings, Numbers, Languages, Sets
Reading: Sections 0.2, 0.3, 0.4, and 1.1
Quiz 1 (Mon, Sep 9th)
Homework 1 Assigned (Due Fri, Sep 20th at 11:59pm ET)
Week 3
Topics: Regular Languages, Closure Properties, Product Construction
Reading: Sections 1.1
Quiz 2 (Mon, Sep 16th)
Week 4
Topics: NFA’s, NFA to DFA Conversion
Reading: Sections 1.2 and 1.3
Quiz 3 (Mon, Sep 23rd)
Homework 2 Assigned (Due Fri, Oct 4th at 11:59pm ET)
Week 5
Topics: More Closure Properties, Regular Expressions, Pumping Lemma
Quiz 4 (Mon, Sep 30th)
Reading: Sections 1.2, 1.3, and 1.4
Week 6
Topics: Context-Free Grammars, Pushdown Automata
Reading: Sections 2.1 and 2.2
Quiz 5 (Mon, Oct 7th)
Homework 3 Assigned (Due Fri, Oct 25th at 11:59pm ET)
Week 7
Fall Break!
Week 8
Topics: Chomsky Normal Form, CFL Closure Properties
Reading: Sections 2.1 and 2.2
No Quiz on Monday
Week 9
Topics: Turing Machines
Reading: Sections 3.1 and 3.2
Quiz 6 (Mon, Oct 28th)
Homework 4 Assigned (Due Fri, Nov 8th at 11:59pm ET)
Week 10
Topics: Computability and Church-Turing Thesis
Reading: Sections 3.1 and 3.2
Quiz 7 (Mon, Nov 4th)
Week 11
Topics: Decidability and Undecidability
Reading: Sections 4.1 and 4.2
Quiz 8 (Mon, Nov 11th)
Homework 5 Assigned (Due Fri, Nov 22nd at 11:59pm ET)
Week 12
Topics: Reductions, Time Complexity
Reading: Sections 5.1, 5.3, and 7.1
Quiz 9 (Mon, Nov 18th)
Week 13
Topics: Polynomial Time, Time Hierarchy Theorem
Reading: Sections 7.1, 7.2, and 9.1
Quiz 10 (Mon, Nov 25th)
Homework 6 Assigned (Due Wed, Dec 11th at 11:59pm ET)
No Class on Friday (Thanksgiving Break!)
Week 14
Topics: Non-Deterministic Polynomial Time, More Reductions
Reading: Sections 7.3 and 7.4
No Quiz on Monday
Week 15
Topics: Complexity Theory, Classes, and Zoo
Reading: Sections 7.4, 8.3, and 8.4
Quiz 11 (Mon, Dec 9th)
Final Exam
TBA