Web page contents:

General Information

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

Announcements

• (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(w₁) and then run M(w₂). Then, if M(w₁) accepted and M(w₂) rejected, then accept <M,w₁,w₂>.
• (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.

Important Dates

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

Resources

Textbook

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.)

Other References

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

Date	Section	Suggested Exercises
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
Oct 28	3.3	none
Nov 4	4.2	4.5-4.8
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

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).

Course Handouts

• Mathematical Prerequisites
• Review questions on mathematical prerequisites (Solutions were handed out in class on Sep 16.)
• Declaration to be handed in with the first assignment
• Assignment 1
• Sample Quiz from 2012
• Assignment 2
• Java code to solve Assignment 1, Question 5 (It prints out the answers for all n.)
• Assignment 3 (corrected version posted Sep 25; see Sep 25 announcement above)
• Assignment 4
• Homework exercises from 2012
• Assignment 5
• Sample test 1 from 2012. More sample tests are available in the "Course Handouts" sections of web pages for previous terms here, here, and here.
• Assignment 6
• Some Java code to help you with assignment 6
• This file contains the description of the Turing machine shown on page 10 of the 2012 homework solutions posted above
• Assignment 7
• Assignment 8
• Sample test 2 and sample exam, and hints for the solutions
• Assignment 9
• Solutions for Assignment 8
• Assignment 10
• Assignment 11 (last one!)
• Review questions on decidability and recognizability (good review for bonus quiz and exam) You can look at solutions to these questions here
• The big picture from the last class
• There are links to some old exams and a set of exam review questions (with solution hints) here. This year we spent less time on context-free languages than in some previous years, so some of the questions on CFLs might be more difficult than I would expect you to do on this year's exam.

Updated December 31, 2014