CPSC 046 01: Theory of Computation (Spring 2024)

Course Information

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).

Schedule (tentative)

Week 1

  • Topics: What it Computation?, DFA’s

  • Reading: Sections 0.2 and 1.1

  • Quiz 1 (Fri, Jan 26th)

Week 2

  • 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

  • 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

  • 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

  • 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

  • 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

  • Homework 6

  • 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