EECS2001, Winter 2016

EECS2001: Introduction to Theory of Computation
Winter 2016

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Lassonde Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays from 14:30 to 16:00 in room 105 of the Life Sciences Building
Tutorials: Mondays from 11:30 to 13:00 in room 106 of the Life Science Building
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "[2001]".)
Instructor office hours: Wednesdays 12:00-13:00 and Fridays 14:00-15:00 or by appointment.
TA office hours: Tuesdays and Thursdays from 12:00-13:00 in Lassonde 2013.

Learning Outcomes

The main goal of this course is to develop your ability to think clearly and carefully about computing, and to express those thoughts about computing in a precise way. By the end of this course, you should be able to do the following things.

Design machines (e.g., finite automata, Turing machines) to solve specified problems
Design regular expressions and context-free grammars for a given formal language
Explain why an object designed according to one of the above two bullets correctly meets its specification
Prove simple properties about models of computation (e.g., that the class of regular languages is closed under complement)
Demonstrate limits of computing by proving that a problem is not solvable within a particular model of computation
Show how one problem can be reduced to another

Academic Honesty

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

Marking Scheme

Four quizzes (5% each)	20%
Two term tests (20% each)	40%
Final exam	40%

Announcements

(Apr 12) UNOFFICIAL final grades have been posted. They will not become official until they are approved by the department. You can view your grade by logging into a departmental Unix machine and typing "courseInfo 2001 2015-16 W". You may view your final exam by coming to my office during the week of April 25-29. (If you want to be sure that I'll be there when you come, send me an email message to set up an appointment.)
(Apr 5) One more office hour added: Wed Apr 6, 13:00-14:00 in Lassonde 3042.
(Mar 29) Before the exam, there are the following office hours:
- Wed Mar 30 12:00-13:00 Lassonde 3042
- Thu Mar 31 12:00-13:00 Lassonde 2013 (TA)
- Fri Apr 1 13:30-14:30 Lassonde 3042
- Mon Apr 4 14:30-? LSB 105 (Review session)
- Tue Apr 5 12:00-13:00 Lassonde 2013 (TA)
- Wed Apr 6 15:00-16:00 Lassonde 2013 (TA)
(Mar 28) There was a mistake in my solution to Test 2, Question 4: The sentences "So <M',1> ∈ L₄" and "So <M',1> ∉ L₄" should be reversed.
(Mar 24) Since the university has cancelled classes due to bad weather, my office hour today and the TA's office hour today is also cancelled.
(Mar 22) Quiz #4 will focus on the material on context-free languages covered in lectures up to and including March 23 (corresponding to pages 101-116 of the textbook).
(Mar 21) My office hour on Wednesday, March 23 is cancelled (sorry for the short notice). Instead, I will have an extra office hour on Monday, March 28 at 10:00.
(Mar 18) The bonus assignment is posted below. Hand it in on March 28 in class.
(Mar 16) There will be a programming contest to award the 2016 York Programming Champion Cup. It will be on March 23 from 7:00 to 10:00 p.m. in Lassonde 1006. See this link for more details.
(Mar 16) News: A computer beat the world's best human Go player. See this article from today's Globe and Mail.
(Mar 15) Prior to the exam, there will be a review session on Monday April 4 at 2:30 p.m. in LSB 105.
(Mar 14) The EECS department is hosting a public lecture on computer animation by Norman Badler on March 18 at 11:00 in LSB106. See this link for details.
(Mar 9) I will have an extra office hour on Monday, March 14 from 10:00 to 11:00.
(Mar 2) The April exam schedule has been posted.
(Mar 2) There was a bug in the solution I handed out for Question 4 on Quiz 3: the label 0,1 -> L should be 0,1,blank -> L.
(Feb 25) Quiz 3 will focus on all of Chapter 3 and pages 194-197 and 201-206 of Chapter 4.
(Feb 25) I will have an extra office hour on Monday, February 29 from 10am to 11am, in case you have last-minute questions before the quiz.
(Feb 22) You can check my records of your grades in the course by logging into a departmental Unix machine and typing "courseInfo 2001".
(Feb 21) My office hour on Friday, Feb 26 is cancelled, but I will have an additional office hour on Thursday, Feb 25 from 14:30-15:30.
(Feb 18) There will be a programming contest on Wednesday, February 24 from 19:00 to 21:00 in Lassonde 1006. See this link for more information.
(Feb 17) The Lassonde School of Engineering is looking for students to participate in the Lassonde Inclusivity Project. For more information, see this message.
(Feb 13) During reading week, office hours will continue as usual, except that there will be no office hour on Friday, February 19.
(Feb 1) The test on February 8 will be in Accolade East 001 (in the basement) at 11:30 a.m.
(Jan 27) My office hour on Friday, January 29 will be at 13:00 instead of 14:00.
(Jan 20) There will be a series of lectures by eminent computer scientists at York this term, and you are invited. The first one is on Friday, January 22 at 11am in ACW 005. These will give you an opportunity to hear about some of cutting edge topics in computer science research. See this link for more information about the speakers and topics of the lectures.
(Jan 18) A number of students missed quiz 1 because they enrolled late. For any student who missed quiz 1, I will move the weight of the missed quiz to the final exam. (To be fair to students who did write the quiz, I will do the same for any student does better on the exam than on quiz 1.)
(Jan 6) Office hours for the course have been posted above. The first one is on January 7.
(Jan 6) Bethune College is looking for a class representative for this course. For more information, see this link.
(Jan 3) There will be no tutorial before the first lecture on January 4.

Important Dates

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

All term tests and quizzes will be held during the tutorial time slot (Mondays, 11:30 to 13:00).

First class (lecture only) Monday, January 4

Quiz 1 Monday, January 11

Quiz 2 Monday, January 25

Test 1 in ACE001 Monday, February 8

Reading Week (no classes) February 15-19
Quiz 3 Monday, February 29

Drop deadline Friday, March 4

Test 2 in LSB106 Monday, March 14

Quiz 4 Monday, March 28

Last class Wednesday, March 30

Review session in LSB105 Monday, April 4 at 2:30 p.m.

Exam period April 6 to 20

Resources

Textbook

Introduction to the Theory of Computation, Third Edition

Errata

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.

Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation, Third Edition. Pearson Addison-Wesley, 2007. Solutions to selected exercises and errata can be found on the textbook's web site.
John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
Elaine Rich. Automata, Computability and Complexity: Theory and Applications. Pearson Prentice Hall, 2008. Good book for more examples and applications.
Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes, Fifth Edition. Wiley, 2009.
Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Dover, 2011.

Web Links

The web page for this course the last time I taught it is here.
Jeff Edmonds has some online notes that he uses when he teaches this course.
links to web pages on theoretical computer science
Scooping the Loop Snooper, a poem by Geoffrey K. Pullum that proves the halting problem is undecidable.

Reading

This schedule is approximate. Try not to fall behind in the reading. The sections refer to the course textbook.

Week Section Suggested Exercises

January 4 0.1-0.4 0.1-0.6, 0.10-0.13 and review exercises

January 11 1.1 1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48

January 18 1.2 1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44

January 25 1.3 1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40

February 1 1.4, pages 194-197 1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58; 4.1, 4.2, 4.3, 4.10, 4.12, 4.13, 4.16, 4.21

February 8 3.1, 3.2 3.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

February 22 3.3, 4.2 4.5-4.8

February 29 5.1 (pages 216-220) 5.10, 5.11, 5.13

March 7 5.3 5.4-5.7, 5.9, 5.22, 5.23, 5.28-5.30

March 14 2.1 2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.17, 2.19, 2.25, 2.26

March 21 2.2 2.5, 2.7, 2.10

March 28 2.3 and pages 198-200 2.2, 2.13, 2.30, 2.31, 2.32, 2.35; 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.

Mathematical prerequisites for the course
Review exercises on mathematical prerequisites
Solutions to the above review exercises. You should look at these only after you have solved the problems yourself.
Sample Quiz 1 from a previous year
Sample Test 1 from a previous year; all questions except 2 and 4 would be reasonable questions for Quiz #2.
Some more exercises about finite automata
An example of constructing a regular expression from a DFA using the method described in January 27 lecture
Some more exercises about regular expressions and proving languages are not regular
Sample Test 2 from last year.
For practice on the material of Chapters 2-5, solve the problems on Assignments 6-11 from last summer (see this link). Solutions for Assignments 7-11 will be handed out in class. You can check your solution to Assigment 6 using this Java programme: A6.java.
These review questions are good practice for Test 2. Sketches of solutions.
Practice for exam: an old test, an old exam and hints for the solutions. A set of exam review questions and hints for answering them. Another old exam
Bonus homework assignment
Slides from March 23 lecture.
The big picture from the last lecture.

Updated April 12, 2016

First class (lecture only)	Monday, January 4
Quiz 1	Monday, January 11
Quiz 2	Monday, January 25
Test 1 in ACE001	Monday, February 8
Reading Week (no classes)	February 15-19
Quiz 3	Monday, February 29
Drop deadline	Friday, March 4
Test 2 in LSB106	Monday, March 14
Quiz 4	Monday, March 28
Last class	Wednesday, March 30
Review session in LSB105	Monday, April 4 at 2:30 p.m.
Exam period	April 6 to 20

Week	Section	Suggested Exercises
January 4	0.1-0.4	0.1-0.6, 0.10-0.13 and review exercises
January 11	1.1	1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48
January 18	1.2	1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44
January 25	1.3	1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40
February 1	1.4, pages 194-197	1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58; 4.1, 4.2, 4.3, 4.10, 4.12, 4.13, 4.16, 4.21
February 8	3.1, 3.2	3.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
February 22	3.3, 4.2	4.5-4.8
February 29	5.1 (pages 216-220)	5.10, 5.11, 5.13
March 7	5.3	5.4-5.7, 5.9, 5.22, 5.23, 5.28-5.30
March 14	2.1	2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.17, 2.19, 2.25, 2.26
March 21	2.2	2.5, 2.7, 2.10
March 28	2.3 and pages 198-200	2.2, 2.13, 2.30, 2.31, 2.32, 2.35; 4.4, 4.5, 4.11, 4.14, 4.31

EECS2001: Introduction to Theory of Computation Winter 2016