Exploring the limits of what computers can do

Announcements

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

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) Lab 9
hw 8

Apr 14

  

Apr 16

Drop ends

Test 4 (Apr 18)
11

Apr 19

   More reductions Lab 10
hw 9

Apr 21

  

Apr 23

  
12

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

May 03

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

May 05

  

May 07