Exploring the limits of what computers can do

Announcements

  • The final exam is cancelled.
  • Homework 10 is available and due 10pm Sunday, May 3.
  • Homeworks 1-5 have been returned, as well as quizzes up to 7.
  • You can register your partner preferences here, including the preference to work alone or to be assigned a random partner. Note that you will work with different partners throughout the semester (you are only allowed to repeat the same partnership 4 times update: there is no limit on repeated partnerships).
  • After you submit each homework, please fill out the post-homework survey.

Schedule

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

Jan 20

no class/lab: MLK Day

(no class -- lab makeup Wed evening) hw 0

Jan 22

lab in the evening!

Introduction
(read: Chapter 0 and the course website)

Jan 24

  Notation and proof techniques
(read: Chapter 0)
2

Jan 27

  deterministic finite automata
and regular languages (read:1.1)
practice problems
hw 1

Jan 29

  DFAs and equivalence classes (read: note on Myhill-Nerode Thm)

Jan 31

Drop/add ends

nondeterministic finite automata (read: 1.2)
3

Feb 03

  practice problems
hw 2

Feb 05

  regular expressions
(read: 1.3)

Feb 07

  non-regular languages
and the Pumping Lemma for regular languages
(read: 1.4)
4

Feb 10

  context-free grammars
(read: 2.1, note on regular grammars)
practice problems
hw 3

Feb 12

 

Feb 14

  pushdown automata
(read: 2.2)
5

Feb 17

  practice problems
hw 4

Feb 19

 

Feb 21

  non-context-free languages
and the Pumping Lemma for context-free languages
(read: 2.3)
6

Feb 24

  intro to Turing machines
Turing machines
more Turing machines
even more Turing machines!
(variations and extensions)
(read: 3.1-3.2)
practice problems
hw 5

Feb 26

 

Feb 28

 
7

Mar 02

Exam 1 (in lab)

enumerators and functions
(read: 3.3)
midterm review

Mar 04

  computability
the Church-Turing Thesis

Mar 06

 
 

Mar 09

Spring Break

Mar 11

Mar 13

Mar 16

Extended Spring Break (go home, minimize contact, wash hands frequently please)

Mar 18

Mar 20

8

Mar 23

video
notes

decidability and undecidability
(read:4.1-4.2 pdf)
practice problems
hw 6

Mar 25

video
notes

Mar 27

video
notes

9

Mar 30

video
notes

reductions (read: 5.1, 5.3 pdf)
Rice's Theorem
(read: note on Rice's Thm)
note on E_TM
practice problems
hw 7

Apr 01

video
notes

Apr 03

video
notes

10

Apr 06

video part 2
notes

practice problems
hw 8
quiz 7

Apr 08

video
notes

Apr 10

video
notes

11

Apr 13

video
notes

time complexity: big O, class P
(read: 7.1-7.2 pdf)
practice problems
midterm review
quiz 8

Apr 15

video
notes

Apr 17

video
notes

12

Apr 20

video
notes

Exam 2 (in lab)

class NP, NP-completeness
(read: 7.2-7.5 pdf)
hw 9

Apr 22

video
notes

Apr 24

video
notes

13

Apr 27

video
notes

the Recursion Theorem (read: 6.1 pdf) practice problems
hw 10

Apr 29

video
notes

May 01

video
notes

Course review
(read: rhyming proof that the Halting Problem is undecidable)
 

May 13

Final Exam (cancelled)