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 3) I have posted UNOFFICIAL final grades for this course. They must be approved by the department before becoming official. To see yours, login to a departmental machine (running linux) and type the command
  courseInfo 2001 2007-08 F
  This will give you a list of your recorded grades for all assignments and tests too. You can come to my office to take a look at your final exam for the next little while. (Later, they will be archived in the departmental office.)
• (Dec 3) See above for pre-exam office hours.
• (Nov 28) My last regularly scheduled office hour will be on Dec 3. I will still have office hours during exam period, but they may not be at the usual times. I will post the times on this page soon.
• (Nov 21) Due to an unexpected meeting, I have to postpone my office hour on Friday, Nov 23: I'll be in my office between 1:30 and 4:00 that day if you want to drop by.
• (Nov 1) Test 2 will not be held in the usual classroom: instead, it will be in RS137.
• (Nov 9) The deadline for Assignment 4 has been moved to Nov 21.
• (Nov 7) Do you know about York's internship programmes and international study opportunities? The CSE dept is very active in both. Lots of our students do internships in industry, and we offer an international B.Sc. degree in computer science and you can take York CSE courses in foreign universities in the summertime. These are things you might want to think about in the future.
• (Nov 6) Course evaluations will be done in class on Nov 21.
• (Oct 29) Some students have been asking how much detail they should provide in their solutions to Assignment 3. First, some general guidelines.

  When you give a CFG for a language, you should explain what each variable represents (in other words, give a precise description of the set of strings that can be generated by each variable). You don't have to give a formal proof that the variables do generate that set (unless I ask you to).

  When you give a PDA for a language, you don't have to give a detailed proof of correctness (unless I ask you to). You should at least give some indication of what each state represents. One very precise way to say why the PDA works is to say for each state $i$, what properties of $x$ and $y$ must be true if the PDA can be in state $i$ with $x$ on the stack after reading input string $y$. (Note that you should be capable of giving a more formal proof of correctness if you actually really understand how the PDA you built works. Doing this is an excellent way to debug your solution, but for this assignment, I don't want you to hand in such a detailed proof.)

  I am asking for a detailed proof in 1(b). I would also like a detailed proof for question 4.

• (Oct 26) There is a typo in my solution to Assignment 2, Question 1: Line 5 should be "Then change that 0 to a 1 and leave the rest of the bits unchanged."
• (Oct 15) Due to departmental meetings, I have to shift my office hours this week. On Oct 15, my office hour will be from 1:00-1:30 and 2:30-3:00. On Oct 19, my office hour will be 2:30-3:30.
• (Oct 3) I will have an extra office hour on Oct 9 from 13:00 until 14:00.
• (Oct 3) Here is a sample test from a previous year. (The test uses notation from an older textbook, so + means union in regular expressions.)
• (Oct 1) There were two errors in the solutions I handed out for assignment 1. In the diagram for question 3, there should be an arrow from B to A labelled by (1 1). (Incidentally, to improve the size of the DFA, one could combine states B and B' into a single state, and also combine C and C' into a single state.) The other error is in the diagram for question 5: state 8 should be an accepting state.
• (Oct 1) The slides that Professor Datta used during the week of Sep 24 are posted here.
• (Sep 20) When you hand in your first assignment (at the beginning of next Monday's lecture), please submit a separate sheet of paper with your name and student number, the date, and the following signed declaration: "I have read and understood the policy on academic honesty on the CSE2001 course web page."
• (Sep 17) I will be away for the week of Sept 24. There will still be lectures (by a substitute instructor) in the usual time and place. I will do my best to answer email during the week. The office hours will be held at the regular times by TAs instead of me in the following locations:
  Monday, September 24, 13:00-14:00: Nathan Mekuz in CSEB 3003.
  Wednesday, September 26, 19:00-20:00: Nathan Mekuz in CSEB 3003.
  Friday, September 28, 10:30-11:30: Celia Li in CSEB 2052.
• (Sep 15) There are a few clarifications about assignment 1. For question 3, the game cannot really be played with fewer than 2 people, so the DFA should reject any string of length 0 or 1. There is a typo in question 4: "languages" should be "language". For question 5, your NFA should also accept the string "0" (so the last sentence of the first paragraph should read: "The first digit should never be 0 unless it is the only digit to the left of the decimal point or it is the only character in the string.").
• (Sep 6) The first York Programming Contest of the year will be held next Wednesday, September 12 from noon to 2:00 p.m. in CSEB 1004. All are welcome. See this page for more information.
• (Aug 30) There will soon be a series of programming contests at York, in preparation for the ACM Contest. Send me your email address if you want to be added to the mailing list to get information about these. More information about the contests appears on this page.

Important Dates

First class	September 5
Assignment 1 posted	September 10
Assignment 2 posted	September 21
Assignment 1 due	September 24
Thanksgiving (no class)	October 8
Test 1	October 10
Assignment 2 due	October 15
Drop deadline	November 9
Test 2	November 19
Last class	December 3

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 Handouts

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4 Deadline changed to Nov 21.
• Assignment 5

Updated January 3, 2008