CSE2001, Fall 2010
CSE2001: Introduction to Theory of Computation
Fall 2010
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
General Information
Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 7362100 ext. 33979
Facsimile: (416) 7365872
Lectures: Tuesdays and Thursdays, 16:0017:30 in Stedman Lecture Hall B
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "[2001]".)
Office Hours
See December 8 announcement, below, for my office hours during the rest of the term.
Academic Honesty
It is important that you look at the departmental
guidelines
on 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
Homework assignments  10% 
Quiz  5% 
Two term tests (20% each)  40% 
Exam  45% 
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 201011 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:3011:30 a.m.; Thu Dec 16, 12:302:30 p.m.; Mon Dec 20, 2:004: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 contextfree 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 lowerleft state and the upperright 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 Lhat.
 (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
(Information will be added to this table thoughout the term.)
First class  September 14 
Reading week (no lectures)  October 1115 
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 1223 
Resources
Textbook
Michael Sipser. Introduction to the Theory of Computation,
Second Edition. Thomson Course Technology, 2005. Errata.
Other References
If you used Rosen's book, Discrete Mathematics and its Applications, for CSE1019, 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.
 DingZhu Du and KerI 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. AddisonWesley, 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. McGrawHill, 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
Reading
This section will be filled in as we go.
Date  Section 
Sep 14  0.1,0.2 
Sep 16  0.3 
Sep 21  0.4 
Sep 23  1.1 
Sep 28  1.2 
Sep 30  1.3 
Oct 19  1.4, pages 165169 
Oct 21  3.1 
Oct 28  3.2, 3.3 
Nov 4  Random Access Machines (not in textbook) 
Nov 9  4.2 
Nov 16  pages 187192 
Nov 18  5.3 
Nov 30  2.1 
Dec 2  2.3 
Dec 7  2.2 
Dec 9  pages 170172 

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 contextfree 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 contextfree.
Updated January 2, 2011