EECS2001, Fall 2014
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: Tuedays and Thursdays from 16:00 to 17:30 in room 105 of the Life Sciences 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: see December 8 announcement
TA office hours: Tuesdays, 13:30-14:30 in room 2013 of the Lassonde building.
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%|
- (Dec 31) Exam grades and UNOFFICIAL final grades have been posted. (The final grades are still
subject to approval by the department.) Type "courseInfo 2001 2014-15 F" to check yours.
If you would like to view your final exam, you can drop by my office in early January.
Happy new year.
- (Dec 8) Getting extra help during exam period:
- Dec 8, 13:30-14:30 office hour in Lassonde 3042
- Dec 9, 13:30-14:30 TA office hour in Lassonde 2013
- Dec 12, 14:30-15:30 office hour in Lassonde 3042
- Dec 15, 13:30 review session in Chemistry 115
- Dec 16, 13:30-14:30 TA office hour in Lassonde 2013
- Dec 17, 17:00 review session in Chemistry 115
- Dec 18, 14:30-15:30 office hour in Lassonde 3042
- or email me to make an appointment outside these times.
- (Dec 5) The Imitation Game, a movie about Alan Turing, is opening next week. See here for a review by a computer scientist.
- (Dec 4) The solution I handed out for the first question on the quiz is much more complicated than necessary. You could just run M(w1) and then run M(w2). Then, if M(w1) accepted and M(w2) rejected, then accept <M,w1,w2>.
- (Dec 4) There will be optional review sessions prior to the exam on December 15 at 1:30pm and Dec 17 at 5:00pm, both in room 115 of the Chemistry Building. In these sessions, you can come and ask any questions you might have about the course material.
- (Nov 25) There will be a 40-minute bonus quiz during class on December 4 about proving that languages are or are not decidable or recognizable. I posted some practice exercises at the bottom of this page to help you prepare for that quiz.
- (Nov 22) I have posted your grades to test 2. Use "courseInfo 2001" to see your grade. The last column gives your score as a percentage so far. The results of the busy beaver contest are also available.
- (Nov 20) In your solution to part (b) of Assignment 10, the constant c should be constant with respect to z, but c may depend on M or w. In part (d) of the question, M' should be M'M,w (CORRECTED!).
- (Nov 14) Solutions to Assignment 8 have been posted at the bottom of the page.
- (Nov 12) There will be an extra TA office hour on November 28 from 14:30-15:30 in Lassonde 2013. However, the regularly scheduled TA office hour on December 2 will not be held.
- (Nov 11) Test 2 will be in two different rooms. Students with surnames starting with a letter between A and L should write in Vari Hall C, and students with surnames starting with a letter between M and Z should write in the regular classroom.
- (Nov 7) There will be an extra TA office hour on Wednesday, November 12 from 14:00-15:00 in room 2013 of the Lassonde Building.
- (Nov 5) On Assignment 7, the constant k in the time bound is different from the dummy variable k in the definition of the set C. (I should have used two different letters for these two quantities.)
- (Oct 29) I will have my usual office hour on October 30, even though there is no lecture that day.
- (Oct 29) To determine your mark for Assignment 6, download A6.java, compile it with "javac A6.java" and then run "java -ea A6 < a6.txt". A lot of students submitted syntactically incorrect files. If it was easy to see how to correct the syntax, I did so and ran the tester on the corrected file (but gave a 20% penalty for the syntax error).
- (Oct 29) To check my records of your marks, type "courseInfo 2001" on one of the EECS unix machines.
- (Oct 21) Since there is no class next Thursday (co-curricular days), there is no assignment being handed out today: use your time to solve more exercises from the textbook.
- (Oct 21) You can also submit assignment 6 via the web here.
- (Oct 9) The test on October 14 will be held in two different rooms. You should write in Vari Hall C if your surname starts with a letter between A and L and in the regular classroom if your surname starts with a letter between M and Z.
- (Oct 7) There will be an extra TA office hour on Friday, October 10 from 12:00 to 13:00 in Lassonde 2013.
- (Oct 7) I realized that the letter a is used in two different ways in Assignment 4: the italic a in the definition of EXTRA(L) is a variable that can be any character of Sigma, and the typewriter font a in part (a) of the problem is a particular letter in the alphabet Sigma used in part (a). To avoid confusion, you might want to replace the a's that appear in the definition of EXTRA(L) by c's.
- (Sep 25) In Question 2 of Assignment 3, there should be a transition from state E to state E labelled by the character . A corrected version of the assignment appears below. (This will only affect your answer to part (d).)
- (Sep 24) There will be a programming contest on October 2 from 11:00 to 13:00 in Lassonde 1004. All are welcome. See this link for more information.
- (Sep 23) The average grade on Assignment 1 was 17/26 (=66%). The marks were allocated as follows: 1 mark for Q1, 4 for Q2a, 4 for Q2b, 2 for Q2c, 2 for each part of Q3, 5 for Q4. Because Q5 was challenging, I treated it as a bonus question (5 bonus marks for getting the right answer).
- (Sep 20) There will be a programming contest on Sep 23 from 1 to 3pm in Lassonde 1004. All are welcome to come. See this link for more information.
- (Sep 17) Test 2 will be on November 13. (An incorrect date was posted on this web page earlier.)
- (Sep 16) Clarification: In assignment 1, question 3a and 3b, the domain of m is also the non-negative integers.
- (Sep 16) If you are interested in a career in computing, you might be interested in joining the ACM.
- (Sep 15) The Design Exchange is sponsoring a design competition for post-secondary students. See this link for more information.
- (Sep 9) Bethune College is seeking class representatives for the Fall term. See this letter for more details.
(Information will be added to this table thoughout the term.)
|First class ||September 9|
|Quiz ||September 25|
|Test 1 (See Oct 9 announcement for location) ||October 14|
|Co-curricular days (no lectures) ||October 29 to November 2|
|Drop deadline ||November 7|
|Test 2 (See Nov 11 announcement for location) ||November 13|
|Study day (no lecture) ||December 2|
|Last class (and bonus quiz) ||December 4|
|Exam period ||December 9 to December 22|
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).
|Sep 9||0.1, 0.2||0.1-0.6 and review exercises|
|Sep 16||0.3, 0.4||0.10-0.13|
|Sep 23||1.1||1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48|
|Sep 30||1.2||1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44|
|Oct 2||1.3||1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40 |
|Oct 7||1.4||1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58 |
|Oct 9||pages 194-197||4.1, 4.2, 4.3, 4.10, 4.12, 4.13, 4.16, 4.21|
|Oct 16||3.1||3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16(a-d), 3.22
|Oct 21||3.2||3.10, 3.12, 3.13|
|Nov 6||5.1 (pages 215-220), 5.3||5.4-5.7, 5.9-5.11, 5.13, 5.22, 5.23, 5.28-5.30|
|Nov 25||2.1||2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.17, 2.25, 2.26|
|Nov 27||2.2||2.5, 2.7, 2.10|
Solutions to assignments and tests will be handed out in class. If you missed getting one, ask me for it.
Updated December 31, 2014