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 2) UNOFFICIAL grades are now posted. You can check your grade by logging into a CS machine (either on campus or using ssh remotely) and typing "courseInfo 2001 2010-11 F". You can view your exam in my office during the week of January 3. (You can just drop by, or you can email me to make an appointment if you want to be sure I'll be there when you come.)
• (Dec 13) The Keele campus of York University will be closed on December 14 due to a major fire on the campus. (See York's main page for updates.) Consequently, my office hour on Tuesday will be cancelled.
• (Dec 8) There will be a review session (where you can come and ask questions and hear other students' questions) on Fri Dec 17 at 3:00 p.m. in room 002 of the Accolade West Building. My office hours for the rest of the term will be: Fri Dec 10, 11:00 a.m.-noon; Tue Dec 14, 10:30-11:30 a.m.; Thu Dec 16, 12:30-2:30 p.m.; Mon Dec 20, 2:00-4:00p.m. These office hours may become busier as they get closer to the exam, so I encourage you to come sooner rather than later for extra help. If you want to see me outside these times, you can try dropping by my office, or you can send me email to make an appointment.
• (Dec 8) The textbook has a proof that { ww : w is in {0,1}*} is not context-free on page 127. It is simpler than the proof I did in class.
• (Nov 23) I will have extra office hours on Nov 24 and Nov 25 at 3:00 p.m.
• (Nov 22) Test 2 will be held in lecture hall C of the CSE Building.
• (Nov 15) Clarification for Assignment 7: when a STM cuts a square out of the tape, it cuts the square where the head is currently located. After the cut, the head is located just to the right of the place where the square was cut out. For example, suppose the tape contents are abcde and the head is located at the d. If the STM inserts one square, then moves left two squares and cuts out one square, the resulting tape contents would be acd_e (where _ indicates a blank) and the head would be at the c.
• (Nov 4) Assignment 7 has been posted below.
• (Nov 4) For assignment 6, question 1, let's assume 0 is not a natural number. Also, I'm moving question 2 of assignment 6 to assignment 7.
• (Oct 28) There is an error on the solutions to Test 1 that I handed out today. For question 2, I forgot to draw transitions back and forth between the lower-left state and the upper-right state, both labelled by 0.
• (Oct 28) The fall exam schedule has been posted.
• (Oct 22) Test 1 will be held in VH C from 4:00 to 5:15. An old test has been posted below for you to practice on.
• (Oct 18) Since I will be attending the ACM regional programming contest on Oct 22, my office hour for that day is cancelled. You can come by my office on Thursday afternoon if you have questions.
• (Oct 10) Test 1 will cover material related to chapter 0 and chapter 1, plus pages 165 to 169 of the textbook.
• (Oct 7) There is a typo in assignment 3, part (b): it should ask for an example of a language where L is *different* from L-hat.
• (Sep 30) Due to a departmental seminar and meeting, my office hour on Friday, October 1 has changed again: it will be at 10:30 a.m. instead of 11:00 a.m.
• (Sep 24) The tentative dates for the tests are: October 5 for the quiz, October 26 for Test 1, November 25 for Test 2 (assuming I can book a larger room for those times).
• (Sep 23) Note that each homework assignment is due at the beginning of class on its due date. Assignment 2 has been posted below.
• (Sep 18) If you want some background reading on recurrences, you can take a look at some rough notes on recurrences that I wrote when teaching CSE1019. They will tell you far more than you need to know to answer assignment 1.
• (Sep 14) The first York programming contest of the new school year will be on Friday, September 17 in CSEB1004 from 3:00 to 5:00 p.m. All are welcome to attend. See the contest web page for more details about the contests.

Important Dates

First class	September 14
Reading week (no lectures)	October 11-15
Test 1 (location: VH C)	October 26
Drop deadline	November 12
Test 2 (location: CSE C)	November 25
Last class	December 9
Exam period	December 12-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

Reading

Course Handouts

• Assignment 1
• A1S.java contains a solution to the optional programming assignment #1.
• Assignment 2
• Assignment 3 (See correction in October 7 announcement above.)
• Optional programming assignment #3 (do not hand in): Quine.java is a little piece of Java code. Try compiling it and running it. What does it do? Figure out how it does what it does. Try to write a shorter programme (in the language of your choice) that accomplishes the same task.
• Last year's quiz (for practice)
• Some notes from the September 30 lecture giving details of the proof of Theorem 1.39 in the textbook.
• Assignment 4
• An example of constructing a regular expression that describes the language decided by a DFA. (Relates to October 7 lecture.)
• Assignment 5
• Last year's test 1 (for practice)
• Assignment 6
• Assignment 7
• Assignment 8
• Assignment 9
• Review questions for last year's final exam. There are also some hints for solving these problems.
• Assignment 10
• An exam from 2009 and another one from 2007. Note: This year, we spent more time on computability and less time on context-free languages than in previous years, so the relative weights of the different sections may be different on this year's exam than it was on these previous exams. (But they are still a good source of practice problems.) Note: the diagram that was originally missing from p.3 of the 2009 exam have now been added.
• The big picture from the last lecture. Note that in class, I drew {0^n 1^n 2^n : n >=0} in the wrong place by mistake; this diagram has it in the right place. Exercise: give a CFG for the complement of this language. Another exercise: show that L={0^i 1^j : j < i^2} is decidable but neither L nor its complement is context-free.

Updated January 2, 2011