EECS2001, Fall 2016

EECS2001: Introduction to Theory of Computation
Fall 2016

Web page contents:

General Information
Important Dates
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Lassonde Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Lectures: Tuesdays and Thursdays from 16:00 to 17:30 in room 106 of the Life Sciences Building
Tutorials: Mondays from 16:00 to 17:30 in room 106 of the Life Science Building
Email: [my last name] (Please use a York mail account when sending me email, and start your subject line with "[2001]".)
Office hours: The course is over so there are no more office hours.

Learning Outcomes

In this course, you will be invited to develop your ability to think clearly and carefully about computing, and to improve your skills in expressing those thoughts about computing in a precise way. By the end of this course, you will be able to do the following things.

How to Learn This Material

Some of the skills that you will develop in this course may be quite new to you, and different from things you have done in previous courses. This is good: it means you're learning new and (I hope) exciting things. However, it means that you will need practice to master them. Just participating in classes isn't enough. There are suggested exercises from the textbook. Web pages for this course in previous terms also include many more problems to work on. Do lots.

You learn by struggling with problems. However, if you get too stuck or don't know how to begin, help is available. Talk to your classmates (however; see the notes below about academic honesty regarding discussing assignment problems with others). Go to office hours; the instructor and TA are there to help you! You also learn by making mistakes and getting feedback about them. Just make sure that you use the feedback to improve your understanding.

Groups of students can learn a lot by explaining their solutions to the suggested exercises from the textbook to one another and critiquing the solutions of others. After all, learning how to explain solutions clearly is one of the learning objectives of this course. Seeing where other students' solutions are unclear to you helps you make your own explanations clearer. Be aware that a problem may have many different correct solutions; just because someone's solution is different from yours doesn't necessarily mean that one of them is wrong.

It takes time to build new skills, so it helps if you work on exercises regularly: don't leave all the work to the days right before a test.

Sometimes students ask for more exercises with worked-out solutions. (The textbook has some, but maybe not enough.) There is a whole shelf of textbooks that cover the material of this course in the library (some are recommended below), and many have more examples or exercises with solutions.

Marking Scheme

Weekly homework assignments15%
Quiz 5%
Test 1 20%
Test 2 20%
Final exam 40%

For each homework assignment, you may either work by yourself or with a partner. If you work with a partner, the two of you should hand in a single set of solutions with both of your names on it. Both partners should work on every problem, since the assignments are intended to help you learn the material and receive feedback on your work.

If you get stuck when working on a problem, I encourage you to come to office hours to get help with it.

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty.

The solutions you hand in should be the work of you and your partner (if you have one). Thus, if you discuss an assignment problem with anyone other than your partner for that assignment, you may discuss only the general approach to solving the problem, not the details of the solution, and you should not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people (besides your partner) with whom you have discussed the problems. While writing your solutions to hand in, you may look at the course textbook and your own lecture notes, but no other outside sources.


Important Dates

Information may be added to this table thoughout the term.

First class Thursday, September 8
Quiz (surnames A-L in CLH C, M-Z in LSB 106) Monday, September 19
Thanksgiving (no class) Monday, October 10
Test 1 (surnames A-L in CLH C, M-Z in LSB 106) Thursday, October 13
Reading day (no class) Thursday, October 27
Drop deadline Friday, November 11
Test 2 (surnames A-L in CLH C, M-Z in LSB 106) Monday, November 14
Last class Monday, December 5
Exam period December 7 to 22



Other References

If you used Rosen's book, Discrete Mathematics and its Applications, for EECS 1019, 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 schedule is approximate and may be adjusted during the term. Try not to fall behind in the reading. The sections refer to the course textbook.

WeekSectionSuggested Exercises
September 50.1-0.40.1-0.6, 0.10-0.13 and review exercises
September 121.11.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48
September 191.2 1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44
September 261.31.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40
October 31.41.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58
October 10pages 194-1974.1, 4.2, 4.3, 4.10, 4.12, 4.13, 4.16, 4.21
October 173.1, 3.23.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16(a-d), 3.22; 3.10, 3.12, 3.13
October 243.3, 4.2 4.5-4.8
October 315.1 (pages 216-220)5.10, 5.11, 5.13
November 75.35.4-5.7, 5.9, 5.22, 5.23, 5.28-5.30
November 142.12.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.17, 2.19, 2.25, 2.26
November 212.2, 2.32.5, 2.7, 2.10; 2.2, 2.13, 2.30, 2.31, 2.32, 2.35
November 28pages 198-200 4.4, 4.5, 4.11, 4.14, 4.31

Course Handouts

Solutions to tests will be handed out in class. If you missed getting one, ask me for it.

Updated January 3, 2017