Course Agenda Course Outline Syllabus
Gradebook

MATH 421: Theory of Computation

Tentative Course Outline

Topics  Reading  Assignments
Introduction  Chapter 0

0.1
0.2
0.3 - 0.4		    
Regular Languages
  • Finite automata
  • Nondeterminism
  • Regular expressions
  • Nonregular languages
  Chapter 1

1.1
1.2
1.3
1.4		  





Context-Free Languages
  • Context-free grammars
  • Pushdown automata
  • No-context-free languages
  Chapter 2

2.1
2.2
2.3		  
***** Midterm Exam I *****
The Church-Turing Thesis
  • Turing machines
  • Variants of Turing machines
  • The definition of algorithm
  • TM simulator
  Chapter 3

3.1
3.2
3.3		  
Decidability
  • Decidable languages
  • Undecidability
  Chapter 4

4.1
4.2		  
Reducibility
  • Undecidable problems from Language Theory
  • Mapping reducibility
  • Reductions via computation histories
  • Rice's Theorem
  Chapter 5

5.1
5.3
5.1
notes		  
***** Midterm Exam II *****
Time Complexity
  • Measuring complexity
  • The Class P
  • The Class NP
  • NP-completeness
  • Additional NP-complete problems
  Chapter 7

7.1
7.2
7.3
7.4
notes		  
Space Complexity
  • Savitch's theorem
  • The Class PSPACE
  • PSPACE-completeness
  • The Classes L and NL
  • NL-completeness
  Chapter 8

8.1
8.2
8.3
8.4
8.5		  
***** Final Exam *****