HOME / CLASSES / COMPUTER SCIENCE 121 AND CSCI E-121: INTRODUCTION TO THE THEORY OF COMPUTATION /

Schedule

Readings are in Sipser's Introduction to the Theory of Computation, 2nd ed. unless otherwise specified.
 
 
# Day Date Topic & Lecture Notes Readings Other Handouts Problem Sets CS121

Problem 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
Turing paper

 

  
Th Oct. 16

Midterm Examination on Material thru Oct. 10

 

 Midterm 2008
Solutions

Midterm 2012
Solutions

Midterm review 2011
Solutions

Midterm 1998
Solutions
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
Fall 2011 final
Fall 2012 final

PS 9 due (Tuesday, no late date)

 

  PS9 due (Tuesday)
    TBD  Review Section  

 

  
 
  TBD

Final Examination

2013 Final Exam and Solutions