EECS2001, Summer 2015
EECS2001: Introduction to Theory of Computation
Web page contents:
Instructor: Eric Ruppert
Office: Lassonde Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Wednesdays from 19:00 to 22:00 in room 106 of the Accolade West Building
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "".)
Instructor office hours: The course is over, so there are no longer any regular office hours.
It is important that you look at the departmental
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.
|Two term tests (20% each) ||40%|
- (Aug 28) I have posted UNOFFICIAL grades for the course. They will become official if they are approved by the department. See the June 21 announcement to see how to check the full record of all your grades in the course. (If you run courseInfo after the fall term has begun, you should instead type "courseInfo 2001 2014-15 S".) You can visit me to pick up your last assignment and view your final exam. If you want to be sure that I will be there when you stop by, you can send me an email message to arrange an appointment. Enjoy your break and good luck with your studies in the fall term.
- (Aug 13) In addition to regular office hours, I will have an extra office hour on Thursday, August 20 from 14:00 to 16:00 in Lassonde 3042.
- (Aug 13) Updated grades have been posted. See June 21 announcement below to see how to check them.
- (Aug 10) There will be a review session on Tuesday, August 18 from 20:00 to 22:00 in room 0004 of the Technology Enhanced Learning (TEL) Building. This will be an opportunity for you to come and ask questions about the course or any exercises that you have had difficulty with, and listen to answers to questions that other students ask.
- (Aug 6) There will be a 30-minute bonus quiz given during the August 19 lecture.
- (Aug 6) Do not submit Question 3 of Assignment 10. It will instead be part of Assignment 11.
- (Aug 5) The exam schedule is now posted at the Registrar's web site.
- (Aug 3) Regarding Assignment 9: If we have several objects x,y,z that can be encoded (in some fixed alphabet) by <x>, <y> and <z>, then the encoding of all three, denoted <x,y,z> can simply be the concatenation <x> # <y> # <z> (where # is a symbol that is not used in the encodings of the individual components, so that you can see where each component begins and ends).
- (Jul 29) There will be extra office hours in advance of Test 2 on Thursday, July 30 from 15:00 to 16:00 and Tuesday, August 4 from 17:00 to 19:00, all in Lassonde 3042. Due to the Simcoe Day holiday, there will be no office hour on Monday, August 3.
- (Jul 20) Today's and Wednesday's office hour is moved to LAS 1006.
- (Jul 16) The solutions to A7 that I handed out yesterday had some omissions. In Question 1(b), if when simulating a step of the TM, the CTM finds a bottom symbol at the top of the right pile, it should treat it as if it were a blank symbol (and if the TM's step moves right, the CTM should not remove the card from the right pile). Thus, the bottom symbol on the right pile is treated like an unlimited number of blank symbols on the simulated TM's tape. Similarly, when simulating a left move and the top card of the left pile contains a blank symbol, the CTM should not remove the card, and instead just add a card with a leftend symbol to the right pile. Also, there is no need to have a blank symbol in Gamma-Sigma in question 1(a).
- (Jul 13) Over the next little while, office hours will be held by TAs instead of me. The times for those office hours are: July 20 17:00-18:00 in LAS 1006, July 22 18:00-19:00 (note later time than usual) in LAS 1006, and July 27 17:00-18:00 in LAS 2013.
- (Jul 13) You can determine your grade for assignment 6 by running this piece of Java code on the file you submitted. See Jun 21 announcement below for information about checking the records of your grades.
- (Jun 22) There will be an extra TA office hour on Wednesday June 24 from 14:00 to 15:00 in Lassonde room 2013.
- (Jun 22) The office hour on Monday June 29 from 17:00 to 18:00 will be done by a TA in Lassonde room 2013 instead of the usual location. The university will be closed on July 1, so there will be no office hour that day. However, there will be an extra TA office hour on Thursday July 2 from 17:00 to 18:00 in Lassonde room 2013.
- (Jun 21) I have posted your grades online. To see your grades, login to a departmental machine and type "courseInfo 2001". (See this link for information about logging into departmental machines from home.)
- (Jun 19) The office hour on Monday, June 22 will be extended for an extra hour, so that it will run from 17:00 to 19:00 (in my office).
- (Jun 10) The office hour on Monday, June 15 is cancelled. Instead, I will be available on Tuesday, June 16 from 17:00 to 18:00.
- (Jun 1) Solutions to the review exercises have been posted at the bottom of this page, along with an old sample quiz.
- (May 29) The classroom has been switched to room 106 of the Accolade West Building, starting with the June 3 class.
- (May 18) Bethune College is looking for a class representative for this course. This is a good opportunity to learn some skills and to help your classmates. See this link for more information.
(Information will be added to this table thoughout the term.)
|First class ||May 20|
|Quiz ||June 3|
|Test 1 ||June 24|
|Dominion Day (no lecture) ||July 1|
|Drop deadline ||July 13|
|Summer Break (no lecture) ||July 22|
|Test 2 ||August 5|
|Last class ||August 19|
|Exam period ||August 21 to 28|
Michael Sipser. Introduction to the Theory of Computation,
Third Edition. Course Technology, 2012. Errata. (If you have an older edition, it will be fine too.)
Note that the bookstore offers temporary access to an electronic version of the book more cheaply than the price of a hard copy. (However, if you plan to take EECS4115, some instructors use the same textbook for that course.)
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.
This section will be filled in as we go. Try not to fall behind in the reading. The sections refer to the course textbook.
Our goal is to cover the following chapters/sections of the textbook, roughly in the following order: 0, 1, 4.1 (pages 194-197 only), 3, 4.2, 5.1 (pages 216-220 only), 5.3, 2.1-2.3, 4.1 again (pages 198-200 only), 5.1 again (pages 225-226 only).
|May 20||0.1-0.4||0.1-0.6, 0.10-0.13 and review exercises|
|May 27||1.1||1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48 |
|June 3||1.2 ||1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44 |
|June 10||1.3||1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40 |
|June 17||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 |
|June 24||3.1||3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16(a-d), 3.22|
|July 8||3.2, 3.3||3.10, 3.12, 3.13 |
|July 15||4.2, 5.1 (pages 216-220)||4.5-4.8; 5.10, 5.11, 5.13|
|July 29||5.3||5.4-5.7, 5.9, 5.22, 5.23, 5.28-5.30|
|Aug 12||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|
|Aug 19||2.2, 2.3||2.5, 2.7, 2.10; 2.2, 2.13, 2.30, 2.31, 2.32, 2.35 |
Solutions to assignments and tests will be handed out in class. If you missed getting one, ask me for it.
Updated August 28, 2015