Exploring the limits of what computers can do

Announcements

  • All homeworks have been returned.
  • Graded quizzes are available for pickup outside SCI 258.

Schedule

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

Jan 22

no lab: MLK Day Jan 21 (makeup lab Wed evening) (Jan 21)

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

Jan 24

   Notation and proof techniques
(read: Chapter 0)
2

Jan 29

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

Jan 31

Drop/add ends (Feb 01)

 equivalence classes
nondeterministic finite automata (read: 1.2, note on Myhill-Nerode Thm)
3

Feb 05

   regular expressions
(read: 1.3)		 practice problems
Hw 2

Feb 07

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

Feb 12

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

Feb 14

   pushdown automata
(read: 2.2)
5

Feb 19

   practice problems
Hw 4

Feb 21

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

Feb 26

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

Feb 28

Exam 1 (in lab) (Mar 04)
7

Mar 05

   enumerators and functions
(read: 3.3)		 midterm review

Mar 07

   computability
the Church-Turing Thesis
 

Mar 12

Spring Break

Mar 14
8

Mar 19

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

Mar 21

  
9

Mar 26

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

Mar 28

  
10

Apr 02

   practice problems
hw 8

Apr 04

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

Apr 09

   practice problems
midterm review

Apr 11

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

Apr 16

Exam 2 (in lab)

 hw 9

Apr 18

  
13

Apr 23

   more NP-complete problems practice problems
hw 10

Apr 25

   the Recursion Theorem (read: 6.1)
14

Apr 30

   practice problems
final review

May 02

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

May 11

Final Exam9am-noon, SCI 181