What problems can computers even solve, really?

Announcements

  • Thanks for a great semester, and enjoy your summer!
  • All homeworks have been returned!

Schedule

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

Jan 16

no class: MLK Day

 Introduction
Reading: Chapter 0		 Lab 0
Homework 1

Jan 18

  

Jan 20

   Notation and proof techniques
Reading: Chapter 0 (seriously!)
2

Jan 23

   deterministic finite automata
and regular languages (read:1.1)
Practice problems
Homework 2

Jan 25

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

Jan 27

   nondeterministic finite automata (read: 1.2)
3

Jan 30

Drop/add ends

 regular expressions (read: 1.3)  
Practice problems
Homework 3

Feb 01

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

Feb 03

  
4

Feb 06

   context-free grammars
(read: 2.1)		  
Practice problems
Homework 4

Feb 08

   pushdown automata
(read: 2.2)

Feb 10

  
5

Feb 13

    
Practice problems
Homework 5

Feb 15

   non-context-free languages
and the Pumping Lemma for context-free languages
(read: 2.3 & note on regular grammars)

Feb 17

   intro to Turing machines
6

Feb 20

   more Turing machines!
(variations and extensions)
(read: 3.1-3.2)		  
Midterm review

Feb 22

Exam 1 (in lab)

Feb 24

  
7

Feb 27

   enumerators and functions (read: 3.3)  
Practice problems
Homework 6

Mar 01

   computability
the Church-Turing Thesis

Mar 03

  
 

Mar 06

Spring Break

Mar 08

Mar 10
8

Mar 13

   decidability and undecidability
(read: 4.1-4.2)		  
Practice problems
Homework 7

Mar 15

  

Mar 17

  
9

Mar 20

   reductions (read: 5.1, 5.3)
Rice's Theorem
(read: Note on Rice's Theorem)		  
Practice problems
Homework 8

Mar 22

  

Mar 24

CR/NC/W Deadline
10

Mar 27

   time complexity: big O, class P
(read: 7.1-7.2)		  
Practice problem
Midterm review

Mar 29

  

Mar 31

  
11

Apr 03

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

Apr 05

Exam 2 (in lab)

Apr 07

  
12

Apr 10

   NP-completeness
Hampath reduces to TSP		  
Practice problems
Homework 10

Apr 12

  

Apr 14

   approximation algorithms
(read: 10.1)
13

Apr 17

    
Practice problems
Homework 11

Apr 19

   general grammars and context-sensitive grammars
(read: note on general grammars (parts 1-2))

Apr 21

  
14

Apr 24

   the Recursion theorem (read: 6.1)  
Final review

Apr 26

  

Apr 28

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

May 05

Final Exam (9am-12pm SCI 181)
registrar schedule