Exploring the limits of what computers can do

Announcements

  • Lab 12 is due 11:59pm Wednesday, April 27.
  • Labs 1 through 9 are graded and returned.
  • Link to Automata Tutor 3.0.
  • 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).
  • 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 19

quiz 1

 Introduction
(read: 0.1 and the course website)		 lab 1

Jan 21

quiz 2

 Notation and proof techniques
(read: 0.2-2.3)
2

Jan 24

quiz 3

 proofs and different sizes of infinity
(lecture 2.1 video, lecture 2.1 notes)		 practice problems 1
lab 2

Jan 26

   diagonalization, deterministic finite automata
and regular languages (read:1.1)
(lecture 2.2 video, lecture 2.2 notes)

Jan 28

   DFAs and equivalence classes (read: note on Myhill-Nerode Thm)
(lecture 2.3 video, lecture 2.3 notes)
3

Jan 31

   practice problems 2
lab 3

Feb 02

   nondeterministic finite automata (read: 1.2)

Feb 04

Drop/add ends

 regular expressions
(read: 1.3)
4

Feb 07

   non-regular languages
and the Pumping Lemma for regular languages
(read: 1.4)		 practice problems 3
lab 4

Feb 09

   context-free grammars
(read: 2.1, note on regular grammars)

Feb 11

  
5

Feb 14

   pushdown automata
(read: 2.2)		 practice problems 4
lab 5
exam 1 review

Feb 16

  

Feb 18

  
6

Feb 21

exam 1 (on gradescope)

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

Feb 23

   intro to Turing machines
Turing machines
(read: 3.1)

Feb 25

   more Turing machines
even more Turing machines!
(variations and extensions)
(read: 3.2)
7

Feb 28

   practice problems 6
lab 7

Mar 02

   enumerators and functions
(read: 3.3)

Mar 04

   computability
the Church-Turing Thesis
 

Mar 07

Spring Break

Mar 09

Mar 11
8

Mar 14

   decidability and undecidability
(read: 4.1-4.2)		 practice problems 7
lab 8
exam 2 review

Mar 16

  

Mar 18

  
9

Mar 21

Exam 2

 reductions (read: 5.1, 5.3)
Rice's Theorem
(read: note on Rice's Thm)
many approaches to E_TM		 practice problems 8
lab 9

Mar 23

  

Mar 25

  
10

Mar 28

   practice problems 9
lab 10

Mar 30

  

Apr 01

  
11

Apr 04

   time complexity: big O, class P
(read: 7.1-7.2)		 practice problems 10
practice 10 bonus
lab 11
exam 3 review

Apr 06

  

Apr 08

  
12

Apr 11

Exam 3

 class NP, NP-completeness
(read: 7.2-7.5)		 practice problems 11

Apr 13

  

Apr 15

  
13

Apr 18

   practice problems 12
lab 12

Apr 20

  

Apr 22

   the Recursion Theorem (read: 6.1)
14

Apr 25

   practice 13
final review

Apr 27

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

Apr 29

    
 

May 06

Final Exam Friday May 6, 9AM SCI 181