CSE2001, Winter 2011

CSE2001: Introduction to Theory of Computation
Winter 2011

Web page contents:

General Information
Important Dates
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays at 2:30 p.m. in Stedman Lecture Hall E
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "[2001]".)
Office Hours: See April 2 announcement below for office hours during the rest of the term.

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 on a homework assignment 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.

If you get stuck while working on one of the assignments, I encourage you to come to my office hours to get help with it.

Marking Scheme

Homework assignments10%
Two term tests (20% each) 40%
Exam 45%


Important Dates

(Information will be added to this table thoughout the term.)

First class January 5
Quiz January 24
Test 1 in CLH D February 9
Reading week (no lectures) February 21-25
Drop deadline March 4
Test 2 March 21
Last class April 5
Exam period April 6-23



Other References

If you used Rosen's book, Discrete Mathematics and its Applications, for CSE1019, it has a chapter on the topics of this course with lots of exercises. (It is chapter 12 in the 6th edition.) This book is available on reserve at the library.

The following list gives other useful references.

Web Links


This section will be filled in as we go. Try not to fall behind in the reading. The sections refer to the course textbook. Whenever there is assigned reading, you should also do all of the associated exercises and problems at the end of the chapter.

DateSectionSuggested Exercises
Jan 50.1,0.20.1-0.6
Jan 100.3
Jan 120.40.10-0.12
Jan 191.11.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48
Jan 261.21.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44
Jan 311.41.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58
Feb 71.31.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40
Feb 143.13.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16, 3.22
Feb 163.23.10, 3.12, 3.13
Feb 283.33.22
Mar 24.1 (pp.165-169)4.1, 4.2, 4.3, 4.9, 4.11, 4.12, 4.15, 4.16, 4.19
Mar 74.24.5, 4.6, 4.7
Mar 95.1 (pp.187-192)5.12, 5.13
Mar 145.35.4-5.7, 5.9-5.11, 5.22, 5.23
Mar 282.12.1,2.3,2.4,2.6,2.8,2.9,2.15,2.16,2.25
Mar 302.3 and 4.1 (pages 170-172)2.2,2.13,2.30,2.31,2.32,2.35
Apr 42.22.5,2.7,2.10

Course Handouts

Solutions to assignments and tests are handed out in class. If you missed getting one, ask me for it.

Updated April 20, 2011