#  Schedule 

 



 ##  

  expand\_more  

 
  

 

Readings are in Sipser's [Introduction to the Theory of Computation, 2nd ed.](http://www-math.mit.edu/~sipser/book.html) unless otherwise specified.

Sort\#DayDateTopic & Lecture NotesReadingsOther HandoutsProblem Sets CS121Problem Sets

CSCI E-121

1

Tu

Sept. 2

Introduction and Overview

Preface

 

 

 

**Unit 1: Finite Automata**

2

Th

Sept. 4

Strings, Languages,  
and Induction

Ch. 0

 

 

 

3

Tu

Sept. 9

Finite Automata

Sec. 1.1-1.2

 

PS 0 due

 

4

Th

Sept. 11

NFAs vs. DFAs, Closure Properties

Sec 1.1-1.2

 

 

PS 0 due (Fri)  
  
 

5

Tu

Sept. 16

Regular Expressions

Sec 1.3

 

PS 1 due

 

6

Th

Sept. 18

Countability and Uncountaibility

Sec 1.3,   
Sec 4.2 (pp. 174-178)

 

 

PS 1 due (Fri)  
  
 

7

Tu

Sept. 23

The Pumping Lemma   
and Nonregular languages

Sec 4.2 (pp. 174-178),   
Sec. 1.4

 

PS 2 due

 

8

Th

Sept. 25

DFA Minimization  
Context Free Grammars

Sec. 1.4

 

 

PS 2 due (Fri)

**Unit 2: Context-Free Languages**

9

Tu

Sept. 30

Ambiguity of Context-free Grammars  
Pushdown Automata

Sec. 2.1

 

PS 3 due

 

10

Th

Oct. 2

Problem solving session  
  
 

Sec. 2.2

 

 

PS 3 due (Fri)

11

Tu

Oct. 7

CFGs vs. PDAs, Non-CF Languages

Sec. 2.2, 2.3

 

PS 4 due  
  
 

 

12

Th

Oct. 9

CF Recognition

Sec. 2.1

 

 

PS 4 due (Fri)

**Unit 3: Computability**

13

Tu

Oct. 14

CFL wrap-up  
Hilbert and Turing

Sec. 3.1

[Hilbert paper](/file_url/144)  
[Turing paper](/file_url/145)  
 

 

 

 

Th

Oct. 16

**Midterm Examination on Material thru Oct. 10**



 M[idterm](/file_url/146) 2008  
[Solutions](/file_url/252)

[Midterm 2012](/file_url/242)  
[Solutions](/file_url/253)

[Midterm review 2011](/file_url/243)  
[Solutions](/file_url/254)

[Midterm 1998](/file_url/244)  
[Solutions](/file_url/256)



 

14 

Tu

Oct. 21

Turing Machines and  
the Church-Turing Thesis

Sec. 3.2, 3.3

 

PS 5 due

 

15

Th

Oct. 23

Recognizability & Decidability

Sec. 3.2, 3.3, 4.1

 

 

 PS 5 due (Fri)

16

Tu

Oct. 28

Turing's Theorem

Sec. 4.1, 4.2

 

PS 6 due

 

17

Th

Oct. 30

Reducibility

Sec. 4.2, 5.1

 

 

PS 6 due (Fri)

18

Tu

Nov. 4

Partial Recursive Functions,   
Undecidable questions

Sec. 5.1, 5.3

 

PS 7 due



 

**Unit 4: Computational Complexity**

19

Th

Nov. 6

Computational Complexity

Sec. 7.1

 

 

PS 7 due (Fri)

20

Tu

Nov. 11

Polynomial Time

Sec. 7.2

 

PS 8 due  
  
 

 

21

Th

Nov. 13

NP

Sec. 7.3

 

 

PS 8 due (Fri)

22

Tu

Nov. 18

P vs. NP, NP-completeness

Sec. 7.4, 7.5

 

 

 

23

Th

Nov. 20

More NP-completeness

Sec. 7.5

 

 

 

24

Tu

Nov. 25

Cook-Levin and More on NP

Sec. 7.4, 10.4

 

 

 

 

Th

Nov. 27

**NO CLASS - THANKSGIVING**

 

 

 

 

25

Tu

Dec. 2

Glimpses Beyond & Conclusions

Sec. 10.4

[Fall 2010 final](/file_url/175)  
[Fall 2011 final](/file_url/176)  
[Fall 2012 final](/file_url/293)

PS 9 due (Tuesday, no late date)

 PS9 due (Tuesday)

 

 

TBD

 Review Section

 

 

 

 

 

 

 

 

 

 

TBD

**Final Examination**

**2013** [**Final Exam**](/file_url/300) **and** [**Solutions**](/file_url/301)