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

• (Apr 23) Exam grades and UNOFFICIAL final grades have now been posted. You can check them by typing "courseInfo 2001 2010-11 W". You can drop by my office to look at your exam during the next week. You can also come by to pick up any old assignments that you have not yet received. (You can email me if you want to be sure that I will be in my office when you come.)
• (Apr 2) There will be an optional review session on Friday, April 8 at 11:00 a.m. in CSEB 3033. My office hours for the remainder of the term will be:
  • Monday, Apr 4 from 1:00-2:00
  • Tuesday, Apr 5 from 4:00-5:00
  • Thursday, Apr 7 from 1:00-2:00
  • Friday, Apr 8 from 11:00-1:00 (review session CSEB3033)
  I will likely be around at other times on Thursday and Friday afternoon in my office, but you can email me if you want to make sure that I will be there for a particular appointment.
• (Mar 18) The test on March 21 will be held in room 121 of the Chemistry Building.
• (Mar 16) The review session on Friday at 4pm will be in CSEB3033.
• (Mar 15) There will be review sessions before Test 2. The first will be on Wed Mar 16 at 4pm in CSE3033. The second will be on Friday Mar 18 at 4pm (location to be announced). No new material will be covered in these sessions; they are just an opportunity to ask questions and hear my answers to other people's questions. So bring questions.
• (Mar 14) Use this link for the poll to decide when the review session will be scheduled. Please complete the poll before 3:00pm on Mar 15. Note that there are 8 options to check (click on the accordion if they are not all shown to you). The time of the review session will be posted here when it is decided.
• (Mar 12) There will be two open forum sessions where you can give your feedback about York services to students and suggest ideas for improved services. All science and engineering students are invited to attend, and refreshments will be provided. See this flyer for details.
• (Mar 10) Results of the Busy Beaver Contest are now available.
• (Mar 10) To submit the bonus question on assignment 6, put your programme in a file called EQ.java and use the "submit 2001 a6 EQ.java" command. (See Feb 26 announcement for more information about the submit command.) If you have discussed the problem with another student, you should also submit a declaration explaining this.
• (Mar 8) Marks up to assignment 5 are now posted. Please check to make sure that all marks are recorded correctly by typing "courseInfo 2001".
• (Mar 7) Due to popular demand, I will accept solutions to question 3 of Assignment 5 until 11:59 p.m. on March 8.
• (Feb 26) Instructions for submitting Assignment 5. See also the next announcement.
• (Feb 25) It seems that Question 1 on Assignment 5 is harder than I expected it to be. Therefore, I am making it a bonus question for Assignment 5. (I.e., you can earn full marks just for submitting a correct solution to Question 2, but it will be possible to get bonus marks by also submitting a correct solution to Question 2.)
• (Feb 16) My office hour on February 18 is cancelled. There will be no office hour on Feb 21 since the university is closed. I will have my ordinary office hours on Feb 23 and 25 during reading week, and you can send me email if you want to arrange a meeting outside of those times during reading week.
• (Feb 9) You can use "courseInfo 2001" from a CSE machine to check your marks (including for Assignment 2).
• (Feb 4) Solutions to Assignment 2 have been posted below.
• (Feb 3) There will be a review session on Monday, February 7 starting at 4:00 p.m., and continuing until you stop asking questions. It will probably be in CSEB3033 (unless I can find a better room between now and Monday). No new material will be covered in this session, but it will be an opportunity for you to ask questions and hear answers to other students' questions.
• (Feb 3) The registrar has scheduled a day of makeup classes on April 5 for the class that was missed on Feb 2 due to the snow flurries. Thus our last class will be on April 5 instead of April 4.
• (Feb 2) Please read all of the following important information related to today's closure of the university.
  • The university is closed today, so there will be no class and my office hour is cancelled.
  • Assignment 2, which was due today, is now due on Thursday, February 3 before 5:00 p.m. Bring it to my office (CSEB 3042). If I am not there when you come by, you can slip it under the door. I will release solutions to Assignment 2 on the website on Friday so that you can see them to study for the test.
  • Test 1 will cover all material up to the end of the January 31 lecture. This includes Chapter 0 and Chapter 1 (excluding Section 1.3).
  • The quiz has been marked. You may check your mark by logging into a departmental unix machine and typing "courseInfo 2001". I suggest that you drop by my office on Thursday afternoon to pick up your quiz and Assignment 1 so that you can use the feedback to prepare for Test 1.
  • I would like to try to schedule an optional review session prior to Test 1. This would be like an office hour (but held in a large room so many students can come) where you can ask questions about the course material and listen to my answers to other students' questions. No new material would be covered during this session. If you would like to attend such a session, please fill out the Doodle poll using this link today so that I can schedule the session (if enough people want it). Check this website again to find out if and when the session is scheduled.
  • I will be available in my office on Thursday afternoon if you have questions related to the course.
  • Below, I have posted last term's test 1 for you to practice on. (Since we have not covered Section 1.3 yet, try designing a DFA for question 3 instead of writing a regular expression. We have not covered the material related to question 4 yet.)
  • The above assumes the university will be re-opened tomorrow. If it is not, please check the web site again for further updates.
• (Feb 1) There was a typo on the due date for Assignment 3: It should be February 9, not February 3.
• (Jan 29) There will be another programming contest on Friday, February 4 in CSEB1004 at 2:30p.m. See this link for more information.
• (Jan 27) The test on Febrary 9 will be held in Curtis Lecture Hall D instead of the usual lecture room.
• (Jan 27) There will be a programming contest on Friday, Jan 28 from 2:30 to 4:00 in CSEB 1004. (Notice the time and location have changed since I announced it in class.) This means my office hour will be noon, as usual, not 2pm. (If you come at the later time and I am not in my office, you can look for me in CSEB 1004.)
• (Jan 23) Your answer to part (b) and (c) of Assignment 1 should not be in expressed in Leutonian. I would like the answer to be some expression involving l. For example, it might be a(l) = l^2+17 (not the right answer, but just to give you an idea of what kind of answer I am looking for).
• (Jan 10) The Natural Sciences and Engineering Research Council of Canada (NSERC) offers funding for undergraduate students who wish to spend the summer doing research with a professor or at a company. There will be an information session about this programme on Friday, January 14 from 10:30 to 11:30 in CSEB 3033. Follow this link for more information about eligibility requirements and the application procedure.
• (Jan 5) The course textbook is a good reference book to have. But since it is quite expensive, you might be interested in the York bookstore's new service: you can rent the course textbook for a term. See this link for more information.

Important Dates

First class	January 5
Quiz	January 24
Test 1 in CLH D	February 9
Reading week (no lectures)	February 21-25
Drop deadline	March 4
Test 2	March 21
Last class	April 5
Exam period	April 6-23

Resources

Textbook

Michael Sipser. Introduction to the Theory of Computation, Second Edition. Thomson Course Technology, 2005. Errata.

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, Second Edition. Addison-Wesley, 2001. 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.
• Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
• Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Saunders College Publishing, 1990.

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
Jan 5	0.1,0.2	0.1-0.6
Jan 10	0.3
Jan 12	0.4	0.10-0.12
Jan 19	1.1	1.1-1.6 (a few parts of each), 1.27, 1.31-1.34, 1.48
Jan 26	1.2	1.7-1.11 (a few parts of each), 1.13-1.16, 1.38, 1.42, 1.44
Jan 31	1.4	1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58
Feb 7	1.3	1.12, 1.17-1.23, 1.28(b), 1.36, 1.39, 1.40
Feb 14	3.1	3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.15, 3.16, 3.22
Feb 16	3.2	3.10, 3.12, 3.13
Feb 28	3.3	3.22
Mar 2	4.1 (pp.165-169)	4.1, 4.2, 4.3, 4.9, 4.11, 4.12, 4.15, 4.16, 4.19
Mar 7	4.2	4.5, 4.6, 4.7
Mar 9	5.1 (pp.187-192)	5.12, 5.13
Mar 14	5.3	5.4-5.7, 5.9-5.11, 5.22, 5.23
Mar 28	2.1	2.1,2.3,2.4,2.6,2.8,2.9,2.15,2.16,2.25
Mar 30	2.3 and 4.1 (pages 170-172)	2.2,2.13,2.30,2.31,2.32,2.35
Apr 4	2.2	2.5,2.7,2.10

Course Handouts

• Mathematical Prerequisites
• Declaration to be handed in with Assignment 0.
• Assignment 0
• Assignment 1
• Assignment 2
• Assignment 3 (Note deadline is February 9.)
• Last term's Test 1
• Assignment 4
• Assignment 5 (See Feb 25 announcement, above)
• This directory has some Java code that might be helpful for Assignment 5.
• Assignment 6
• Information on marking of Assignment 5
• Assignment 7
• You might find DFA.java useful as a starting point for solving the bonus question on Assignment 6. (It at least gives you the routine to read in a DFA from a description YUDFADF.) This Java programme reads in a DFA and a string and then runs the DFA on the string.
• Assignment 8
• Sample test 2 (for practice)
• Sample final exam (for practice)
• Assignment 9
• In the handouts section of last term's web page there are more practice exams and a set of review questions that you can use to study for the exam.
• Assignment 10 (For part (a), you do not have to give a formal proof that your answer is correct.)
• The big picture from the last class

Updated April 20, 2011