
Go To Sessions
Course Materials
Introduction to the Theory of Computation
by Michael Sipser
PWS Publishing Company
ISBN 053494728X
Course Goals
Students will gain an understanding of several fundamental models of computation, i.e., automata. They will learn about the capabilities and limitations of these automata, and the implications for computer science. Each of these types of automata corresponds to a class of formal languages, and students will study the structure of these languages. The course also teaches students basic concepts that are needed in more advanced computer science courses.
Course Policies
Grading will be based on three exams and a final. Exercises will be posted so that students can reinforce the ideas learned from the text and class.
They will not be graded, but some class time will be spent on discussing them.
Grading
Three Exams, each worth 25% of the total grade
Wednesday, September 18
Wednesday, October 16
Wednesday, November 13
Final Exam, worth 25% of the total grade
Course Term
From August 26, 2002 To December 6, 2002
Sessions:
August, 2002 
S 
M 
T 
W 
TH 
F 
S 




1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31






December, 2002 
S 
M 
T 
W 
TH 
F 
S 
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31







Basics: Mathematical Notions and Methods of Proof (Chapter 0)
From August 26, 2002 To August 28, 2002
Regular Languages and Finite Automata (Chapter 1)
From August 30, 2002 To September 16, 2002
ContextFree Languages and Pushdown Automata (Chapter 2)
From September 20, 2002 To October 14, 2002
Turing Machines and the Notion of Algorithm (Chapter 3)
From October 18, 2002 To October 25, 2002
Decidability (Chapter 4)
From October 28, 2002 To November 11, 2002
Reducibility (Chapter 5)
From November 15, 2002 To November 22, 2002
Time Complexity (Chapter 7)
From November 25, 2002 To December 06, 2002
This page has been viewed 50
times
since August 6, 2002.
