COSC3101, Winter 2002
COSC3101: Design and Analysis of Algorithms
Winter 2002
This web page contains information relevant to both sections of COSC3101. There is also a supplementary page for the daytime section.
Web page contents:
General Information
Announcements
Important dates
Resources
Course Handouts
General Information
Take a look at the departmental guidelines on academic honesty.
There is a newsgroup, york.cs.course.3101, you can use to discuss the course.
Marking scheme
| Four assignments (7.5% each) | 30% |
| Two 80-minute tests (15% each) | 30% |
| Final exam | 40% |
Daytime Section
Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Tuesdays and Thursdays, 13:00-14:30 in room 115 of the Chemistry and Computer Science Building
Office Hours: Tuesdays and Thursdays, 14:30-15:30, or by appointment
Evening Section
Instructor: Bo Yi
Office: Computer Science Building, room 2024
Telephone: (416) 736-2100 x33274
Facsimile: (416) 736-5872
Email: boyi@cs.yorku.ca
Lectures: Mondays, 19:00-22:00 in room 215 of Bethune College
Office Hours: Mondays and Thursdays, 18:00-19:00
Announcements
For A4, Q2: If you can give an algorithm for this problem whose running time is O(n^c) for some constant c, you will win $1000000 (U.S. dollars). Follow this link to see how to claim your prize. You will also get an automatic A+ in this course.
There is an omission in the solution to question 2 on assignment 2. The following should be added to the argument by cases. Case IV: z=y. The only change in the set of y's ancestors is the addition of x. But x > y, since the loop did not exit. So all of y's ancestors in A' are bigger than or equal to y.
Old announcements
Important Dates
| | Daytime Section | Evening Section |
| First class | January 3 | January 7 |
| Assignment 1 available | January 8 | January 8 |
| Last day to enrol without instructor's permission | January 11 | January 11 |
| Assignment 1 due | January 24 | January 24 |
| Assignment 2 available | January 24 | January 24 |
| Last day to enrol with instructor's permission | January 25 | January 25 |
| Test 1 | February 7 | February 18 |
| Reading week (no classes) | February 11-15 | February 11-15 |
| Assignment 2 due | February 21 | February 21 |
| Assignment 3 posted | February 21 | February 21 |
| Last day to drop without receiving a grade | March 1 | March 1 |
| Assignment 3 due | March 14 | March 14 |
| Assignment 4 available | March 14 | March 14 |
`
| Test 2 | March 19 | March 18 |
| Course/instructor evaluations | April 2 | April 1 |
| Last class | April 4 | April 1 |
| Assignment 4 due | April 5 | April 5 |
Resources
Textbook
- 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. Notice that we are using the 2nd edition, which has just been published. If you want to try to get by with the old edition, it will be up to you to figure out which chapters/pages of the old edition correspond to the reading you are assigned from the new edition.
Supplementary Reading
- Jeff Edmonds, Thinking About Algorithms Abstractly. These notes can be found here.
Other References
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
- Gilles Brassard and Paul Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
- Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
- Michael T. Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, 2002.
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 1994.
- 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.
- Robert Sedgewick, Algorithms (2nd edition), Addison-Wesley, 1988.
Ian Parberry's book, Problems on Algorithms, is a terrific source for practice problems on many topics covered in this course. Solutions to selected problems are also given. The book is available online for free; 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.
See my page of links for web
pages related to theoretical computer science.
Last summer term's COSC3101 web page.
Last fall term's COSC3101 web page.
Course Handouts
To view a course handout, select one of the following links. Most of
the documents are in PostScript format. (If you don't have a
PostScript viewer, you can obtain one from here.)
Course handouts are no longer online.
Updated September 16, 2002