CSE2001, Fall 2009
CSE2001: Introduction to Theory of Computation
Web page contents:
Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Tuesdays and Thursdays, 16:00-17:30 in Room 203 in the North wing of the Ross building
Email: [my last name]@cse.yorku.ca (Please use a York mail account when sending me email, and start your subject line with "".)
The course is over, so there are no more office hours for the course.
It is important that you look at the departmental
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.
|Two term tests (20% each) ||40%|
- (Jan 4) Your exam grades and UNOFFICIAL final grades have been posted using courseInfo. The final grades must be approved by the department before they become official. To see those grades (and to check that I have recorded all of your grades correctly), log into a unix machine using your CS account and type "courseInfo 2001 2009-10 F". You can view your final exam in my office this week. (Send me email first if you want to be sure that I am available when you want to come see me, or you can just drop by.)
- (Dec 16) Question 14 on the exam review is harder than I thought. In fact, I don't think it is solvable using the pumping lemma; you probably have to use a stronger lemma (that we have not covered in class).
- (Dec 14) There was a mistake in my hint for review question 17 (see bottom of this page). Solutions to some of the questions have also been posted below.
- (Dec 13) Notice that a solution for Assignment 9 has been posted below now.
- (Dec 11) There will be a review session on Tuesday Dec 15 starting at 4:00p.m. in room S122 of the Ross building. The main purpose is for you to come and ask me questions about the course material or about problems that you are stuck on. The room is big, so that you can come and listen to one another's questions.
- (Dec 11) Hints for the exam review questions have been posted below.
- (Dec 9) There was a mistake in question 11 in the exam review questions. I have corrected it and reposted the questions below.
- (Dec 7) I have posted some review questions below for you to practice on before your exam.
- (Dec 3) My office hour on Dec 4 will be at 4:00 instead of 1:00.
- (Nov 25) In the solutions to Test 2, I forgot one rule in the grammar for question 2: there should also be a rule S -> 0.
- (Nov 24) I will be out of town on Nov 27 so my usual Friday office hour will be cancelled. However, I will be around on Nov 26 between 1:30 and 3:30 if you want to come ask questions then.
- (Nov 18) By popular demand, I have posted a sample test #2 at the bottom of this page.
- (Nov 17) The test on Thursday, Nov 19 will be in lecture hall C of the Computer Science and Engineering Building.
- (Nov 12) Due to a meeting, I have to change the time of my office hour tomorrow (Nov 13) from 2pm to 4pm.
- (Nov 11) The Career Centre is having a panel discussion on careers in information techonology. See this web site for more information.
- (Nov 6) I think I made a mistake in describing the way to convert a CFG to
CNF in class on Nov 5 (but the example I worked out was correct). When removing the a rule of the form A -> B, you should add a rule A -> x for each rule B -> x in the CFG (where x is any string of terminals and variables). Thus, instead of applying the rule A -> B and then applying the rule B -> x, using the revised grammar you will simply apply the rule that allows you to replace A by x in one shot.
- (Nov 6) As announced in class yesterday, Test 2 will be on Nov 19. It may be in a different room, so check back here later for the location.
- (Oct 27) Today's class has been cancelled because there was an emergency situation in the Ross Building and we could not enter the classroom.
- (Oct 27) The fall exam schedule has been posted at the Registrar's web site.
- (Oct 25) Assignment 5 has been posted below.
- (Oct 19) For assignment 4, the range of the variable k is over the natural numbers.
- (Oct 9) Test 1 will be held in CLH F, not the usual classroom.
- (Oct 6) October 15 is "Succeed in Science" day at York. There are a number of special events planned. See this link for more information. Some events are geared to first-year and second-year students, but others, like the Computer Science town hall meeting are intended for all levels.
- (Oct 1) Reminder: today's quiz is in CLH F, not the usual classroom.
- (Sep 30) In exercise 2, when describing how integers are represented in reverse, the word "least" should be "most". Thus, the MOST significant bit is at the right end instead of the (usual) left end. The example input illustrates this. Sorry for the confusion this may have caused.
- (Sep 29) You don't have to handle negative integers in exercise 2; just non-negative ones (since the problem doesn't even say how negative numbers could be represented).
- (Sep 22) There will be a lecture today, as scheduled.
- (Sep 22) Exercise 2 has been posted below.
- (Sep 17) While I'm away, the TA for this course will hold two office hours on Monday Sept 21 from 4:00 to 5:00p.m. in CSEB2052 and on Friday, September 25 from 4:30 to 5:30p.m. in CSEB2052.
- (Sep 16) I will be out of town at a conference from Sep 18 to 25. A special guest lecturer will teach the classes while I'm away. I will try to check email while I'm away, but I might not be able to check email as frequently.
- (Sep 11) The second York programming contest of 2009-10 will be on Wednesday, September 16 from 7:00 to 9:00 p.m. See this page for more details.
- (Sep 7) There will be a programming contest on Friday, September 11 from 12:30 to 3:00 in CSEB 1006. See this page for more details.
(Information will be added to this table thoughout the term.)
|First class ||September 10|
|Quiz ||October 1|
|Reading week (no lectures) ||October 12-16 |
|Test 1 ||October 22 in CLH F|
|Drop deadline ||November 6|
|Test 2 ||November 19 in CSE C|
|Last class ||December 8|
|Exam period ||December 10-23|
Michael Sipser. Introduction to the Theory of Computation,
Second Edition. Thomson Course Technology, 2005. Errata.
- 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.
This section will be filled in as we go.
|Oct 20||pages 166-169|
|Nov 12||2.2 (pages 109-114)|
|Nov 17||2.2 (pages 115-122)|
|Nov 24||pages 170-172,3.1|
|Nov 26||3.2, 3.3|
|Dec 3||pages 187-192|
Updated January 23, 2010