Exploring the limits of what computers can do


  • The Final Exam will be May 14 9am-12pm. You'll have an extra half hour (i.e., until 12:30pm) to turn in the final to account for any potential internet connectivity issues.
  • Here is a final exam review guide for the Final.
  • Homeworks 1-8 have been returned. Tests 1-5 have been graded.
  • Homework 4 and future homeworks will be partnered. We're using Teammaker to manage partnerships. If you and a classmate want to work with eachother, both of you need to go to Teammaker and select eachother. This week please choose partnerships by Saturday 10pm. I'll force partnerships after that (in order to give you enough time to work on the assignment.)
Please be aware that many elements of this website will change throughout the semester, including the course schedule. It is your responsiblity to review this page periodically for updates.

I value any and all student feedback. If you would like to provide anonymous course feedback, use the submission form here. Please be constructive in any comments so I can adjust the course as best possible.

Quick Links

Course Basics

CPSC 046 / MATH 046: Monday, Wednesday, Friday 9:20am-10:10am, hosted on Zoom.
Lab A: Friday 3:00pm - 4:30pm, hosted on Slack.
Instructor: Joshua Brody
Email: brody at cs.swarthmore.edu
Office Hours: Tuesday 3-4:30pm, Wednesday 12:30pm-2:00pm, and by appointment.
Office hours will be held in the #office-hours channel on slack.
Textbook: Introduction to the Theory of Computation, Third Edition by Sipser. (any edition is ok) Errata.
Course Discussion: Slack
Homework assignments: weekly, due Thursday 11:59pm
Waitlist Procedure. For spring 2021, please use the following waitlist procedure to stay active in the course and be considered for open positions:
  1. If you haven't already, please fill out the department waitlist request form.
  2. Stay current with the course lectures and labs by watching all lecture videos on Panopto.
  3. Please do not attend lecture or lab on zoom. Regrettably, there are too many students on the waitlist to manage all enrollees and waitlist students.
  4. I will stay in contact to provide updates.
There are no guarantees that following the waitlist procedure will result in obtaining a seat; I will replace students that drop based on the department lottery priorities and with students who follow the above steps and who can fit the opened lab spot into their schedule.

Welcome to CS46. This course is an introduction to the formal systems that are commonly used as abstract models for computational processes. We will study a variety of computational models, and classify and solve problems in each of them. While computers are now ubiquitous and the idea of an algorithm seems natural, where did these ideas originate? Why, for instance, do we have memory on our machines --- is it necessary for computation, or simply a convenience? Do other methods of computation even exist? Could we solve more interesting problems with another model? Along the way, this course will develop mathematical concepts which are fundamentally important for computer science: decidability, undecidability, and computational complexity. We will go beyond simply saying "this problem seems hard" and show that some computational problems are inherently harder than others, or simply unsolvable by computers. We will examine the limits of computers and computation, and consider the consequences of these limits. By approaching these topics from a formal standpoint, this course aims to teach students how to describe and to reason precisely about computational objects.


This is a living document. Please check regularly for updates!

Feb 10

(read: Chapter 0 and the course website)
Lab 1
hw 1

Feb 12

  Notation and proof techniques
(read: Chapter 0)

Feb 15


Feb 17

  Deterministic Finite Automata,
Regular Languages (read:1.1)
Lab 2
hw 2

Feb 19

  Deterministic Finite Automata

Feb 22

  Nondeterministic Finite Automata (read: 1.2)

Feb 24

Add deadline

Lab 3
hw 3

Feb 26

Test 1 (Feb 28)

Regular Expressions
(read: 1.3)

Mar 01

  Non-regular Languages,
the Pumping Lemma
(read: 1.4)

Mar 03

  Context-Free Grammars
(read: 2.1)
Lab 4
hw 4

Mar 05


Mar 08

  Pushdown Automata
(read: 2.2)

Mar 10

  Lab 5
hw 5

Mar 12

Test 2 (Mar 14)


Mar 15

  Non-context-free Languages,
the Pumping Lemma for context-free languages
(read: 2.3)

Mar 17

  Pushdown Automata, non-context-free languages. Lab 6

Mar 19

  Turing Machines
(read: 3.1-3.2)

Mar 22


Mar 24

Spring Break

Mar 26


Mar 29

  Enumerators and Functions
(read: 3.3)
hw 6

Mar 31

Test 3 (Apr 01)

the Church-Turing Thesis

Apr 02


Apr 05

  Decidability and undecidability
(read:4.1-4.2 )
Lab 8
hw 7

Apr 07


Apr 09


Apr 12

  Reductions (read: 5.1, 5.3) Lab 9
hw 8

Apr 14


Apr 16

Drop ends

Test 4 (Apr 18)


Apr 19

  More reductions Lab 10
hw 9

Apr 21


Apr 23


Apr 26

  time complexity: big O, class P
(read: 7.1-7.2)
Lab 11
hw 10

Apr 28


Apr 30

Test 5 (May 02)


May 03

  class NP, NP-completeness
(read: 7.2-7.5)
Lab 12

May 05


May 07