CSE 2001
Introduction to Theory of Computation
Summer 2013

Department of Computer Science and Engineering,
York University

Course Description

The course introduces different theoretical models of computers and studies their capabilities and theoretical limitations. Topics covered typically include the following.

What's New


Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca


Monday 19:00 to 22:00 in CLH K (CLH is Curtis Lecture Halls).

Instructor Office Hours

Monday and Thursday from 17:00 to 18:00 in LAS 3052A.


Michael Sipser, Introduction to the Theory of Computation, Third Edition Cengage Learning, 2013. Book web site.

If you have the second edition, here is the errata.

The textbook is required; it is available at the York University Bookstore.


General prerequisites; CSE1019 3.00.

Evaluation Scheme

Assignements (4 @ 5% each)      20%
Tests (2 @ 20% each)       40%
Final exam       40%
Total 100%

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty. Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.

Readings, Suggested Exercises, and Lecture Transparencies

Additional References

Ding-Zhu Du and Ker-I Ko, Problem Solving in Automata, Languages, and Complexity, Wiley, 2001.

John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 2003.

Daniel Solow, How to Read and Do Proofs: An Introduction to Mathematical Thought Processes, Wiley,2002.

Jeff Edmonds, Abstract Thinking, Intro to the Theory of Computation: SC/COSC 2001 3.0 Lecture Notes, Winter 99-00 Version 0.2, available here.