Fall 2008

Announcements

Important Dates

Resources

Reading

Course Handouts

Office: Computer Science Building, room 3042

Telephone: (416) 736-2100 ext. 33979

Facsimile: (416) 736-5872

Lectures: Mondays, Wednesdays and Fridays, 15:30-16:30 in room 215 of Bethune College

Email: [my last name]@cse.yorku.ca

Office Hours: Tuesdays 14:00-15:00 and Fridays at various times. You can also try dropping by my office when I'm in or making an appointment by sending me email.

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.

Quiz | 5% |

Test 1 | 20% |

Test 2 | 20% |

Exam | 40% |

Homework Problems | 15% |

- (Mar 3) I have posted UNOFFICIAL grades. You can access them by logging into a cs machine and typing "courseInfo 3101 2008-09 F". (If you're at home, you can do a remote login with ssh.)
- (Feb 22) I will office hours on Tuesday from 2pm until people stop coming to ask questions. I'll also be available on Wednesday in the late afternoon (around 3:30). I have posted an old exam at the bottom of this page for you to practice on. Reminder: you are allowed to bring one 8.5x11 inch page of handwritten notes into the exam with you (but no other aids).
- (Feb 19) The review session tomorrow will be in our usual classroom, BC215.
- (Feb 18) As mentioned last week, we'll have another optional review session on Friday Feb 20 at 3:30 (check back here for the location). I'll only be answering questions during that session, so come with questions.
- (Feb 10) I have booked a room for another optional review session this Friday, Feb 13 right after our class. Come prepared with questions to ask.
- (Feb 10) I have to cancel my office hour today. I will be available tomorrow afternoon if you want to come ask questions. (Or you can send me email.)
- (Feb 9) The exam schedule has been posted on the Registrar's web site.
- (Feb 4) I forgot a factor of 2 in the solutions to assignment 7, question 2. The recurrence in case I should be S[i,j] = 2P(L[i+1]) + S [i+1,j+1], since Hindrek gets to put both copies of the card in his pocket when he finds a match.
- (Feb 3) Hint for Assignment 8: an algorithm that runs in Theta(n^2) time will not be sufficient for full marks. There are more efficient solutions.
- (Feb 2) Depending on demand, I may have an optional review session on Friday, after our class, in which I will try to answer any questions you have.
- (Feb 2) Dates that have been changed due to the strike have now been posted below, including the date of Test 2.
- (Feb 2) The departmental town hall meeting (mentioned in the announcement below) has been changed to a pizza party on the first floor of the Computer Science and Engineering Building (near the computer labs) at noon on Thursday, Feb 5.
- (Feb 1)
~~You are invited to a departmental Town Hall Meeting to welcome you back and to answer questions you might have. It will be on Thursday, Feb 5 at 4:00p.m. in lecture hall B of the Computer Science and Engineering Building. Pizza and pop will be available.~~ - (Jan 30) Classes will resume on Monday, Feb 2.
- (Jan 26) Classes may be starting up again soon, if Bill 145 receives royal assent. Check the York website for details. The timetable for the return to classes is on this page.
- (Jan 21) I will be attending a workshop out of town next week (Jan 26-30). If classes do resume during that time, I have arranged for a special guest lecturer to teach the 3101 classes, so they will proceed as normal. However, my office hours will not be held during that week. I will be reachable by email.
- (Jan 9) I posted a preview of assignment 9 below.
- (Jan 5) My regular office hours have now resumed, so the first one of the new year will be Jan 6.
- (Dec 19) I hope you enjoy the holidays. Have a Merry Christmas if you celebrate it, and a happy new year.
- (Dec 19) When classes resume, we will have to move fairly quickly through the remaining material. I recommend that you do a bit of reading ahead (see reading below). You should also do your best to continue practicing the ideas that we learned in class before the strike so that you don't get rusty. A good source of exercises on most of the topics we have covered so far is Ian Parberry's book (see link below for online version). If you want a good source of problems on dynamic programming and greedy algorithms go to uvatoolkit.com, click on "Continue problem solving..." and look for problems labelled DP or greedy. Click on the little globe for the problem statement. Once you have solved the problem (in Java, C or C++), you can submit your solution to an online judge which will tell you whether you solved the problem correctly or not.
- (Dec 19) Here is some information from the latest update from the University Senate. At this point, classes will not resume before January. You will get at least 24 hours notice before classes resume. There will probably be 13 days of classes for the fall term after classes resume (so the term will have 11 weeks of classes instead of the usual 12). After those classes, there will be an exam period of 12 days, and then the winter term will begin. Reading week during the winter term will be cancelled this year. If you think this strike has gone on TOO LONG, feel free to contact the President of the University to communicate your desire for a speedy resumption of classes. You can also try sending a similar message to the union leadership, though I'm not sure how much good that will do.
- (Dec 19) I will have my usual Friday office hour on Dec 19 at 2p.m. I will also have one on Monday, Dec 22 at 2p.m. After that, the university will close for the holidays, so I will not have office hours until the new year.
- (Dec 10) I will be out of town for a few days. This means that my office hour on Fri, Dec 12 is cancelled and my office hour on Tue, Dec 16 will be postponed to Wednesday Dec 17 at 2p.m. (this time will change to 4:30 p.m. if classes have resumed by the 17th). If classes resume while I am out of town, I have arranged for someone to teach them for me. I will try to continue to respond to email while I am away from Toronto.
- (Nov 14) My office hour next Tuesday will be later than usual. It will be from 15:30-16:30 because I am running a programming contest earlier in the afternoon. (You are welcome to come to that contest; the problems on the contests are often good practice for CSE3101 topics. See this page for details.)
- (Nov 7) For Assignment 8, you may assume that a solution exists. In other words, for every time between 8:00 a.m. and 10:00 p.m., there is some volunteer who is willing to work at that time.
- (Nov 6) TA's and contract faculty are on strike. The university administration has decided to suspend all classes. So there will not be any 3101 lectures until further notice. A lot of information about the strike is posted at York's "labour dispute toolkit". Check back here too for further announcements.
I am not on strike, so I will continue to hold office hours (although I may change the times of some of them, so check back here), and I am also reachable by email. I may work at home more often during the strike to avoid the hassle of crossing picket lines.

Some deadlines will be postponed as a result of the strike: Homework problem #7 will now be due in the second class when classes resume. Homework problem #8 will now be due in the fourth class when classes resume. The date of the second test, the last class, and the exam period may get postponed (depending on the length of the strike). I'll post further information here when I know it.

I recommend that you use the extra time you have as a result of the strike to catch up on reading, to do some extra studying of the parts of the course you have been having trouble with and to DO LOTS OF EXERCISES. It's important to keep working on the course because otherwise you might get rusty if the strike is prolonged. If you want to read ahead, you can start with chapter 23, which we will be covering next, when classes resume. If you want some extra help on any topic, come see me during my office hours or send me email to make an appointment to see me at another time.

- (Oct 24) The makeup test next week will be in room SLH 107.
- (Oct 24) There is a possibility that the union representing teaching assistants and temporary instructors at York will go on strike, although the union is still negotiating with the university administration. I hope the strike will not happen. However, the university administration has decided to suspend classes if a strike does occur. See this link for details. If a strike does occur, I'll post updates here about how this will affect the course.
- (Oct 21) There will be an optional makeup test next week. It will cover the same material as test 1, plus sorting (but not dynamic programming). If you do better on the makeup test than you did on test 1, I will replace your mark for test 1 by your mark for the makeup test. We can't give up more lecture time for optional tests, so the makeup test will be held outside the usual lecture time. In class yesterday everybody agreed that Wednesdays at 7pm is a good time, so it will probably be next Wednesday, Oct 29. If you cannot attend the test on Wed Oct 29 at 7pm, please let me know. To prepare for the makeup test, I suggest that you do lots of exercises. The text has good exercises on searching and sorting, but doesn't have too many on basic proofs of correctness for loops and recursive programmes. For exercises on the latter topic, I suggest Jeff Edmonds's or Ian Parberry's book (see supplementary reading section, below).
- (Oct 20) There was a typo on the solutions to assignment 4 that I handed out today: The array "A" and the array "S" are both supposed to be "S".
- (Oct 9) A reminder: you may bring one handwritten 8.5x11 inch piece of paper with you to use during your test.
- (Oct 8) office hours for the next week: Friday Oct 10 at 1:00, Wednesday Oct 15 at 11:00. (No office hour next Tue Oct 14.)
- (Oct 7) Clarification for homework problem #4: The algorithm should return the k elts whose values are closest to the median. For example, if the elements of the array {1,34,56,99,100,101,102,103,150}, then the median is 100 and the 5 elements closest to the median are {99,100,101,102,103}.
- (Oct 3) To prepare for the test, I suggest you do lots of problems. A good source of problems for loop invariants and proving correctness of programmes is Ian Parberry's online book, which you can download by making a donation to the charity of your choice. (See the link in the supplementary reading section, below.)
- (Oct 3) There is such a thing as a free lunch. Our department has invited consultants to review our computer science and engineering programmes and make recommendations on how they can be improved. The consultants want to meet with students. Your input and comments would be valuable to the consultants. You can meet with them on Wednesday, Oct 8 from 12:00 to 13:00 in 3033 CSEB, where lunch will be served.
- (Oct 2) Hint for assignment 3. One way to strengthen the claim is to subtract a lower order term. But there are other things you can try. For example, you could try proving T(n) <= c(n-d)^(log_2 3), where c, d are some constants.
- (Sep 29) If you want to take a CS course in Europe next summer, spend a month (or more!) in Europe (and have the university pay for your airfare), go to an information meeting on Friday, Oct 3 at 10:30 in CSEB 3033. I really think this is an amazing opportunity. (If you cannot attend the meeting but are interested, you should contact Professor Tourlakis or Professor Gryz.)
- (Sep 22) A student pointed out a little error in my solution to exercise 1(c): My discussion of the running time omitted the time to perform the decrement of j. Since j has O(log n) bits, it could be done in O(log n) time, giving an overall running time of O(n log n). However, that bound is not tight. It turns out that decrementing a counter from n to 0 takes Theta(n) time in total, although this is a little tricky to see. (If you want to know more about this, take CSE 4101 with me in the winter). So, the overall time for the algorithm really is Theta(n). If you said O(nlogn), I'll still give full marks.
- (Sep 16) There will be an interesting lecture called Coping with Impossible Problems that is open to the public on November 9. It is organized by the Royal Canadian Institute. See their site for details.
- (Sep 13) There will be a series of programming contests in the fall term. See this page for details. Doing them would be good practice for this course.
- (Sep 5) There will be a quiz on background mathematics on Friday, September 12. It will be worth 5% of your final grade. See handout below for a summary of what will be covered. Some of the material also appears in your textbook in Chapter 3 and Sections A, B.1 and B.3 of the appendix. A good resource for proof techniques is
*How to Read and Do Proofs*(see reading list below).

First class | Wednesday, September 3 |

Quiz | Friday, September 12 |

No class (university holiday) | Wednesday, October 1 |

Test 1 | Friday, October 10 |

Thanksgiving (no class) | Monday, October 13 |

Makeup test for test 1 (see announcements above) | Wednesday, October 29 |

Assignment 7 due | Wednesday, February 4 |

Assignment 8 due | Friday, February 6 |

Test 2 | Monday, February 9 |

Last class | Wednesday, February 18 |

Exam period | February 20-March 3 |

Last date to drop course without receiving a grade | Tuesday, March 10 |

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and
Clifford Stein,
*Introduction to Algorithms, 2nd edition*, MIT Press & McGraw-Hill, 2001. For known errata, follow this link. Copies of the text are on reserve at the Steacie Library. You can also access an electronic version of the textbook through the York Library website.

- Jeff Edmonds,
*How to Think About Algorithms*, Cambridge University Press, 2008. - Ian Parberry's book,
*Problems on Algorithms*, has lots of practice problems for many topics covered in this course. Solutions to selected problems are also given. The book is available online; the author asks that you make a small donation to charity if you choose to download the book. Follow this link to access the book.

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The Design and Analysis of Computer Algorithms*, Addison-Wesley, 1974. - Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani,
*Algorithms*, McGraw Hill, 2008. This is a really nice little book. - Michael R. Garey, and David S. Johnson,
*Computers and Intractability: A Guide to the Theory of NP-Completeness*, W. H. Freeman and Company, 1979. - Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,
*Concrete Mathematics: A Foundation for Computer Science (2nd edition)*, Addison-Wesley, 1994. - Jon Kleinberg and Éva Tardos,
*Algorithm Design*, Pearson, 2006. - Donald E. Knuth,
*The Art of Computer Programming (3rd edition), Volume 1: Fundamental Algorithms*, Addison-Wesley, 1997. Sections 1.1 and 1.2 are a good reference for the material covered during the first few weeks of the course. TAOCP also has lots of good exercises with solutions. - Donald E. Knuth,
*The Art of Computer Programming (2nd edition), Volume 3: Sorting and Searching*, Addison-Wesley, 1998. - Anany Levitin,
*Introduction to the Design and Analysis of Algorithms*, Addison-Wesley, 2003. - Steven S. Skiena,
*The Algorithm Design Manual*, Springer, 2008. - Steven S. Skiena and Miguel A. Revilla,
*Programming Challenges: The Programming Contest Training Manual*, Springer, 2002. This book covers many topics of the course from a more problem-oriented different angle. - Daniel Solow,
*How to Read and Do Proofs (3rd edition)*, Wiley, 2002.

- Algorithmics Animation Workshop
- links to web pages on theoretical computer science
- web page of this course the last time I taught it.

Week | Topics | Reading in CLRS |

prereq | Background Math | See handout below |

Sep 3 | Introduction | 1, 2.1, 2.2, 31.2 |

Sep 8 | Loop invariants | none |

Sep 15 | Proving correctness | 2.3 |

Sep 22 | Divide and conquer | 4 |

Sep 29 | Master Theorem, Selection | 4 (see also Section 6 of these notes), 9.3 |

Oct 6 | More on selection (incl. Problem 9.3-3). Sorting. | 8 |

Oct 13 | Sorting. Dynamic Programming. | 8, 15 |

Oct 20 | Dynamic Programming. | 15 |

Oct 27 | More Dynamic Programming, including all-pairs shortest paths | 25.1, 25.2 |

Nov 3 | Greedy Algorithms | 16 |

Feb 2 | Greedy Algorithms for MSTs | 23 |

Feb 9 | Graph algorithms | 22.1 to 22.3 |

Feb 16 | Dijkstra's algorithm | 24.3 |

- Mathematical prerequisites
- Some review questions on mathematical prerequisites
- Homework problem 1
- Homework problem 2
- Homework problem 3
- Homework problem 4
- Homework problem 5
- Homework problem 6
- Homework problem 7--revised due date: February 4
- Homework problem 8--revised due date: February 6
- Homework problem 9
- An example of a 3101 exam from a previous year

*Updated March 3, 2009
*