COSC3101, Winter 2003
COSC3101: Design and Analysis of Algorithms
Winter 2003
Sections M and P
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
There are
separate web pages sections N and Q.
General Information
Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Section M Lectures: Tuesdays and Thursdays, 13:00-14:30 in Curtis Lecture Hall H
Section P Lectures: Mondays, 19:00-22:00 in room 118 of Winters College
Office Hours: Mondays from 17:30 to 18:30, Thursdays from 14:30 to 15:30 or by appointment.
There is a newsgroup, york.cs.course.3101, that
you can use to discuss the course.
Take a look at the departmental
guidelines
on academic honesty.
Announcements
- May 5: UNOFFICIAL grades are now available. Type courseInfo 3101M 2002-03 W or courseInfo 3101P 2002-03 W.
- Apr 25: Marks for A4 are now available from courseInfo. The assignments themselves are outside my office door.
- Apr 16: Marks for A3 are now available from courseInfo. The assignments themselves are outside my office door.
- Apr 9: Here is another old exam to practice on.
- Apr 9: Assignment 4 solutions have been posted below.
Old announcements
Important Dates
| | Section M |
Section P |
| First class | Tuesday, January 7 |
Monday, January 6 |
| Assignment 1 due | Tuesday, January 28 |
Monday, January 27 |
| Test 1 | Tuesday, February 11 |
Monday, February 10 |
| Reading week (no classes) | February 17-21 |
February 17-21 |
| Assignment 2 due | Thursday, February 27 |
Thursday, February 27 |
| Last date to drop course without receiving a grade |
Friday, March 7 | Friday, March 7 |
| Test 2 | Thursday, March 13 |
Monday, March 17 |
| Assignment 3 due | Wednesday, March 19 |
Wednesday March 19 |
| Last class | Thursday, April 3 |
Monday, March 31 |
| Assignment 4 due | Monday, April 7 |
Monday, April 7 |
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.
Optional Supplementary Reading
- Jeff Edmonds, How to Think About Algorithms. These notes are
on sale at the university bookstore.
- 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; 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.
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.
- Anany Levitin, Introduction to the Design and Analysis of
Algorithms, Addison-Wesley, 2003.
- Robert Sedgewick, Algorithms (2nd edition), Addison-Wesley, 1988.
- Daniel Solow, How to Read and Do Proofs (3rd edition), Wiley, 2002.
Web Links
Reading
Don't fall behind with your reading. The reading in the text is
required. The reading in Edmonds's notes is optional, but helpful.
(Edmonds's notes are also a good source of additional examples for
many topics covered in the course.)
| Week | Topics | Reading in CLRS | Reading in Edmonds |
| Jan 6 | Introduction | 1, 2.1, 2.2 | 1.3 |
| Jan 6 | Asymptotic Notation | 3 | 1.4 |
| Jan 6, Jan 13 | Sums | Appendix A | 1.5 |
| Jan 13 | Recurrences | 4 | 1.6 |
| Jan 20 | Invariants, Pre- and Post-conditions | none | 3 |
| Jan 20 | Divide-and-conquer | 2.3 | 11.1 |
| Jan 20 | Arithmetic algorithms | 31.2 (review 31.1) | 4.3, 11.2.2 |
| Jan 27 | Heapsort | 6 | 6.1 |
| Jan 27, Feb 3 | Quicksort | 7 | 11.2.1 |
| Feb 3 | Linear-time selection | 9 | 11.2.1 (page 173) |
| Feb 10 | Lower bounds for max, searching and sorting. Counting sort. | 8.1, 8.2 | 6.2.1, 17.3 |
| Feb 24 | Radix sort, bucket sort | 8.3,8.4 | 6.2.2 |
| Feb 24, Mar 3, Mar 10 | Dynamic programming | 15 | 16 |
| Mar 10, Mar 17 | Greedy algorithms | 16.1-16.3, 16.5 | 10 |
| Mar 17, Mar 24 | MST algorithms | 23 | 10.2.3 |
| Mar 24 | Searching algorithms | 22 | 8 |
| Mar 31 | Shortest Path algorithms | 24.3, 25.1, 25.2 | 8.2 |
Course Handouts
Assignments have been taken offline.
Updated April 25, 2003