Web page contents:

General Information

Section A

Section B

Both Sections

• Tuesdays 17:00-18:00, CSEB2013
• Thursdays 10:00-11:00, CSEB2013

Academic Honesty

You may work on the homework assignments in pairs. If you choose to do this, you and your partner should hand in a single solution set with both of your names on it.

Although you may discuss the general approach to solving a problem with other people (besides your partner), 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 (Section B): I have posted UNOFFICIAL final grades. You can check yours by typing "courseInfo 2001B 2005-06 F".
• Dec 7: The exam will be held in two rooms. Students with family names starting with A-L, please go to Curtis Lecture Hall A. Students with family names starting with M-Z, please go to Curtis Lecture Hall G.
• Dec 6: (Section B only): Eric Ruppert will have extra office hours on Tuesday Dec 6 (3 to 4 p.m., but I'll continue longer if more people are waiting to ask questions) and on Wednesday Dec 7 (3 to 4 p.m., but I'll continue longer if more people have questions). Send email if you need to make an appointment outside those times.
• Dec 5: Extra-long TA office hour on Thursday, Dec 8: 10 a.m. to 12 noon.
• Dec 5: Assignment 3 solutions have been posted below.
• Nov 26: (Section B only): Eric Ruppert will be out of town (and probably not checking email much) from Dec 1 to Dec 4.
• Nov 20: Assignment 3 has been posted below.
• Nov 16: The TA office hour on Nov 22 is cancelled.
• Nov 11: Solutions to assignment 2 have been posted below.
• Nov 8: The deadline for assignment 2 has been extended. It is now due at 4:00 p.m. on Friday, November 11.
• Nov 8: There is an upcoming information session about internship opportunities with Research In Motion. November 15, 5:30-7:30p.m., room N102. To register, email your name to obtower at yorku dot ca. See this link for more details about York's Internship Programme.
• Oct 27: Course evaluations will be done in class on November 23 and 24.
• Oct 27: The December exam scheduled has been posted on the Registrar's web site.
• Oct 24: (Section B only) During the term you can check your grades on assignments and tests from any of the department's unix machines by typing 'courseInfo 2001B'. The marks for assignment 1 have been posted.
• Oct 21: The second homework assignment has been posted below.
• Oct 18 (Section B only): I made a mistake in the lecture yesterday. For the language L = {1^r u : u is a binary string with at least r 1's}, I didn't specify whether r=0 is allowed. If it is allowed in the definition of L, then a regular expression for L is (0 union 1)*, since we can take r=0 and any binary string for u (since every binary string has at least 0 1's in it). If we define L such that r must be greater than 0, then a regular expression for L is 10*1(0 union 1)*, because the string must start with 1, and contain at least one more 1.
• Oct 16: The dates for test 2 have been posted below.
• Oct 13: Solutions to the first problem set have been posted below.
• Oct 11: There are excellent opportunities for you to take CSE courses in Europe, either for one month next summer or for a whole fall or winter term. The financial cost of doing this is heavily subsidized. For more information, go to an information meeting in CB129 on Oct 28 from 2 to 3:30 p.m.
• Oct 8: One TA office hour has changed again. Starting on October 13, the weekly TA office hour will be on Thursdays from 10:00 to 11:00 instead of Fridays. The location is still CSEB 2013. The Tuesday TA office hour is unchanged.
• Sep 23: The dates for the first test are Wednesday, October 19 for section B (Ruppert) and Thursday, October 20 for section A (Turpin). These are in-class tests.
• Sep 22: The TA office hour on Sep 27 will be extra-long, from 16:00 to 18:00.
• Sep 19 (Section B only): Eric Ruppert will be away for the week of September 26, and email to him might not get read until the following week. Another professor will be teaching the lectures.
• Sep 19 (Section B only): During the week of Sep 19, the instructor's office hour will be Wednesday 16:00-17:00. There will be no office hours the week of Sep 26. Starting the week of Oct 3, office hours will be Mon 19:00-20:00, Wed 14:00-15:00, or by appointment.
• Sep 8: The first York programming contest of the new school year will be held next week. See this link for all the exciting details.
• Sep 8: WiCSE (Women in Computer Science and Engineering) is holding a workshop on Sept. 16th from 9 am. to 2 p.m. in CSE3033 entitled "Personal Mastery: Time Management, Public Speaking Skills and Your Leadership Style". See this link for details. (Male students are welcome but since registration is limited to 50, priority is given to female students.)

Important Dates

	Section A	Section B
First class	September 8	September 7
Assignment 1 posted	September 19	September 19
Class cancelled (Rosh Hashanah)	October 4	October 5
Thanksgiving (no class)		October 10
Assignment 1 due	October 12	October 12
Class cancelled (Yom Kippur)	October 13
Test 1 (in class)	October 20	October 19
Assignment 2 posted	October 21	October 21
Assignment 2 due	November 11 (4pm)	November 11 (4pm)
Last date to drop course without receiving a grade	November 11	November 11
Test 2 (in class)	November 15	November 16
Assignment 3 due	December 5	December 5
Last class	December 6	December 5

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

• Chapter 0. (Some of this will be a review of stuff you already know.)
• Chapter 1.
• Chapter 2.
• Chapter 3.
• Chapter 4.
• Section 5.1 (up to page 192), Section 5.3.

Course Handouts

Assignment solutions have been taken offline.

• Assignment 1
• Assignment 1 marking scheme
• Assignment 2
• Assignment 2 marking scheme
• Assignment 3 (pdf version)
• An exam from last year (pdf version). Note: a different textbook was used last year, so terminology and topics covered might be a little different from this year.

Updated January 4, 2006