Web page contents:

Instructors

Daytime Section

Evening Section

General Information

• Mondays, 16:00-18:00 in CSB2013,
• Tuesdays, 17:00-19:00 in CSB2031A,
• Fridays, 14:30-16:30 in CSB2013.

Take a look at the departmental guidelines on academic honesty.

Marking Scheme

Announcements

• May 5: I forgot to post the marking scheme for Assignment 3. It is as follows. Q1: 2,3,3,1 marks for the four parts. Q2: 3 marks. Q3: 5 marks. Q4: 5 marks. Q5: 5,2 marks for the two parts. Q6: 4 marks. Total 33 marks.
• May 3: UNOFFICIAL grades have been posted. You can find out your grade by typing "courseInfo 2001M 2003-04 W" or "courseInfo 2001N 2003-04 W". Final grades are subject to approval by the department.
• April 26: Announcement for Section M: Your third assignment can be picked up from the box in the hall outside my office (CSB3042). Assignment grades have been posted on courseInfo.
• April 8: Professor Ruppert's office hours for next week will be on April 12 and 13 from 1:00 to 2:00. (If you drop by at other times and find me in my office, you can also ask questions then.)
• April 7: Solutions to Assignment 3 have been posted below.
• April 4: Professor Ruppert's office hours will be held at the usual times this week (April 5, 1:30-2:30 and April 8, 11:30-12:30). Check back here later to find office hours for the following week.
• March 30: Note: TA office hours will be held (at the usual time and place) beyond the end of classes on April 5, 6 and 12. There will be no TA office hour on April 9 because it is a holiday.
• March 24: The marking scheme for Assignment 2 is as follows: Q1: 5 marks, Q2: 4 marks, Q3: 3 for a, 4 for b, Q4: 5 marks, Q5: 4 for a, 5 for b, 2 for c.
• March 20: Assignment 3 has been posted below.
• March 5: Professor Ruppert's office hour on Monday, March 8 is moved to Tuesday March 9, from 11:30-12:30.
• February 26: For daytime section students: the average on test 1 was about 17/30, and the mark distribution in section M was:
  0-4: 0 students
  5-9: 2 students
  10-14: 13 students
  15-19: 25 students
  20-24: 13 students
  25-30: 1 student.
  Don't panic if you didn't do as well as you would have liked to. It takes time to get accustomed to doing theoretical computer science and understanding and writing proofs. However, you should take a low mark as a warning that you should be doing more work for the course, so that you will do better in the rest of the course. Help is available in the office hours of the TAs and the instructor. Make use of them.
• February 25: The exam schedule has been posted.
• February 25: You will be asked to fill out course evaluation surveys on March 23 (in the evening section) and March 30 (in the daytime section).
• February 24: You can check your marks from your cs account using the courseInfo. Type "courseInfo 2001M" or "courseInfo 2001N".
• February 12: Note that there will not be TA office hours during reading week. Professor Ruppert's office hour on Monday, February 16 is cancelled. Send him email if you want to set up an appointment during reading week.
• February 10: You should hand your assignment solutions in by placing them in the drop box located near the main computer science office on the first floor of the Computer Science Building.
• February 5: Reminder: the test this weekend is not in your usual classroom. See below for locations.
• January 28: Take a look at Jeff Edmonds's notes which describe a different way of proving languages are not regular. Postscript version; PDF version.
• January 22: Please note: The TA office hours (and locations) listed above have been changed.
• January 20: Note about assignments: If you choose, you may do each assignment together with one other student. You and your partner should hand in a single set of solutions (and will receive the same mark). Although you may discuss general ideas about how to solve a problem with people other than your partner, you should take no written notes away from such a discussion, and you should not discuss detailed solutions. The solutions you hand in should be the work of you and your partner only. See the link above for policies regarding academic honesty.
• January 14: The NSERC undergraduate research award is a great way to spend a summer doing a research project and getting paid by the government to do so. There is an information session on Mon Jan 19 at 3pm in CSE 3003 where you can find out all about the programme. See this link for details.
• January 14: TA office hours have been posted above. Use them!
• January 9: The test dates have been posted below.
• January 7: If you enjoy problem-solving and writing code (and what computer scientist doesn't?), you should think about getting involved with York's team for the ACM programming contest. Training for next fall's competition will begin soon, with an organizational meeting next week. See this link for details.

Important Dates

	Daytime Section	Evening Section
First class	January 4	January 4
Test 1	February 8, 1:30-3:00pm in CSB B	February 8, 1:30-3:00pm in CSB C
Reading Week	February 16-20	February 16-20
Last date to drop course without receiving a grade	March 5	March 5
Test 2	March 7, 1:30-3:00pm in CSB B	March 7, 1:30-3:00pm in CSB C
Last class	April 1	March 30

Resources

Textbook

• 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.

Other References

• Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
• John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
• 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

• links to web pages on theoretical computer science

Reading

Section I: Regular Languages (about 5 weeks)

Section II: Context-Free Languages (about 3 weeks)

Section III: Turing Machines (about 4 weeks)

Course Handouts

• Assignment 1
• Assignment 2
• Assignment 3

Updated May 5, 2004