Web page contents:

General Information

Office Hours

Academic Honesty

Although you may discuss the general approach to solving a problem 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.

Marking Scheme

Announcements

• (Jan 4) Your exam grades and UNOFFICIAL final grades have been posted using courseInfo. The final grades must be approved by the department before they become official. To see those grades (and to check that I have recorded all of your grades correctly), log into a unix machine using your CS account and type "courseInfo 2001 2009-10 F". You can view your final exam in my office this week. (Send me email first if you want to be sure that I am available when you want to come see me, or you can just drop by.)
• (Dec 16) Question 14 on the exam review is harder than I thought. In fact, I don't think it is solvable using the pumping lemma; you probably have to use a stronger lemma (that we have not covered in class).
• (Dec 14) There was a mistake in my hint for review question 17 (see bottom of this page). Solutions to some of the questions have also been posted below.
• (Dec 13) Notice that a solution for Assignment 9 has been posted below now.
• (Dec 11) There will be a review session on Tuesday Dec 15 starting at 4:00p.m. in room S122 of the Ross building. The main purpose is for you to come and ask me questions about the course material or about problems that you are stuck on. The room is big, so that you can come and listen to one another's questions.
• (Dec 11) Hints for the exam review questions have been posted below.
• (Dec 9) There was a mistake in question 11 in the exam review questions. I have corrected it and reposted the questions below.
• (Dec 7) I have posted some review questions below for you to practice on before your exam.
• (Dec 3) My office hour on Dec 4 will be at 4:00 instead of 1:00.
• (Nov 25) In the solutions to Test 2, I forgot one rule in the grammar for question 2: there should also be a rule S -> 0.
• (Nov 24) I will be out of town on Nov 27 so my usual Friday office hour will be cancelled. However, I will be around on Nov 26 between 1:30 and 3:30 if you want to come ask questions then.
• (Nov 18) By popular demand, I have posted a sample test #2 at the bottom of this page.
• (Nov 17) The test on Thursday, Nov 19 will be in lecture hall C of the Computer Science and Engineering Building.
• (Nov 12) Due to a meeting, I have to change the time of my office hour tomorrow (Nov 13) from 2pm to 4pm.
• (Nov 11) The Career Centre is having a panel discussion on careers in information techonology. See this web site for more information.
• (Nov 6) I think I made a mistake in describing the way to convert a CFG to CNF in class on Nov 5 (but the example I worked out was correct). When removing the a rule of the form A -> B, you should add a rule A -> x for each rule B -> x in the CFG (where x is any string of terminals and variables). Thus, instead of applying the rule A -> B and then applying the rule B -> x, using the revised grammar you will simply apply the rule that allows you to replace A by x in one shot.
• (Nov 6) As announced in class yesterday, Test 2 will be on Nov 19. It may be in a different room, so check back here later for the location.
• (Oct 27) Today's class has been cancelled because there was an emergency situation in the Ross Building and we could not enter the classroom.
• (Oct 27) The fall exam schedule has been posted at the Registrar's web site.
• (Oct 25) Assignment 5 has been posted below.
• (Oct 19) For assignment 4, the range of the variable k is over the natural numbers.
• (Oct 9) Test 1 will be held in CLH F, not the usual classroom.
• (Oct 6) October 15 is "Succeed in Science" day at York. There are a number of special events planned. See this link for more information. Some events are geared to first-year and second-year students, but others, like the Computer Science town hall meeting are intended for all levels.
• (Oct 1) Reminder: today's quiz is in CLH F, not the usual classroom.
• (Sep 30) In exercise 2, when describing how integers are represented in reverse, the word "least" should be "most". Thus, the MOST significant bit is at the right end instead of the (usual) left end. The example input illustrates this. Sorry for the confusion this may have caused.
• (Sep 29) You don't have to handle negative integers in exercise 2; just non-negative ones (since the problem doesn't even say how negative numbers could be represented).
• (Sep 22) There will be a lecture today, as scheduled.
• (Sep 22) Exercise 2 has been posted below.
• (Sep 17) While I'm away, the TA for this course will hold two office hours on Monday Sept 21 from 4:00 to 5:00p.m. in CSEB2052 and on Friday, September 25 from 4:30 to 5:30p.m. in CSEB2052.
• (Sep 16) I will be out of town at a conference from Sep 18 to 25. A special guest lecturer will teach the classes while I'm away. I will try to check email while I'm away, but I might not be able to check email as frequently.
• (Sep 11) The second York programming contest of 2009-10 will be on Wednesday, September 16 from 7:00 to 9:00 p.m. See this page for more details.
• (Sep 7) There will be a programming contest on Friday, September 11 from 12:30 to 3:00 in CSEB 1006. See this page for more details.

Important Dates

First class	September 10
Quiz	October 1
Reading week (no lectures)	October 12-16
Test 1	October 22 in CLH F
Drop deadline	November 6
Test 2	November 19 in CSE C
Last class	December 8
Exam period	December 10-23

Resources

Textbook

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

Other 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

Reading

Course Materials

• Exercise 1
• Exercise 2 (see Sep 30 announcement above)
• Professor Datta's slides from Sep 24 lecture (powerpoint required)
• The proof that NFAs and DFAs have the same power (from the Sep 29 lecture)
• Exercise 3
• An example of the construction of a regular expression from a DFA (from the October 6 lecture).
• Exercise 4
• Exercise 5
• Exercise 6
• Exercise 7
• Exercise 8
• A sample second test from a few years ago
• Exercise 9
• Review questions (Question 11 was corrected on Dec 9)
• An old exam from a previous time I taught this course.
• Diagram from the last lecture
• Hints for exam review questions Note: in the hint for question 17, the line "for all strings x of length i" should read "for all strings x of length at most i".

Updated January 23, 2010