Exploring the limits of what computers can do

Announcements

  • Wednesday office hours this week are cancelled. Instead I'll have office hours Thursday 12:30-2:00pm. Next week we'll resume standard office hour times.
  • Homeworks 1-5 have been returned. Tests 1-3 have been graded.
  • Homework 7 is out and due 11:59pm Thursday April 15. It is a partnered homework
  • Test 4 will be on Sunday April 18.
  • 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.


Schedule

This is a living document. Please check regularly for updates!
WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS/Homework     
1

Feb 10

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

Feb 12

  Notation and proof techniques
(read: Chapter 0)
2

Feb 15

 

Feb 17

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

Feb 19

  Deterministic Finite Automata
3

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

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

 
5

Mar 08

  Pushdown Automata
(read: 2.2)

Mar 10

  Lab 5
hw 5

Mar 12

Test 2 (Mar 14)

6

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

Mar 22

 

Mar 24

Spring Break

Mar 26

8

Mar 29

  Enumerators and Functions
(read: 3.3)
Lab7
hw 6

Mar 31

Test 3 (Apr 01)

Computability
the Church-Turing Thesis

Apr 02

 
9

Apr 05

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

Apr 07

 

Apr 09

 
10

Apr 12

  Reductions (read: 5.1, 5.3)

Apr 14

 

Apr 16

Drop ends

Test 4 (Apr 18)

11

Apr 19

  More reductions

Apr 21

 

Apr 23

 
12

Apr 26

  time complexity: big O, class P
(read: 7.1-7.2)

Apr 28

 

Apr 30

 
13

May 03

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

May 05

 

May 07