Algorithms and Complexity 2003:
Second Year Course

Textbook: Jeffrey J. McConnell, Analysis of Algorithms, Jones and Bartlett, 2001. Website.
Marking: The final mark for this course will be made up as follows: Popquizzes: 10%; Assignments: 30%; Test (end of 3rd term): 20%; Exam (end of 4th term): 40%.

Other recommended books: (recommendations are my personal opinion only)
Richard Neapolitan and Kumarss Naimipour, Foundations of Algorithms, D.C. Heath and Company, 1996. (Recommended!)
T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, ISBN 0-262-53091-0 (MIT Press paperback) or 0-07-013143-0 (McGraw-Hill). Recommended but expensive; covers much more than the course.
Udi Manber, Introduction to Algorithms, A Creative Approach, Addison Wesley, 1989. Good book, but perhaps a little hard to follow.

A number of books by Aho have been placed on reference in the library. I am not familiar with these books, but they cover the same work.

Assignments: (pdf versions have now been created using pdflatex and look better; apologies for low quality of previous pdf documents)

Assignment 1 (PDF version)
Assignment 2 (PDF version)
Assignment 3 (PDF version)
Assignment 3: bonus question (PDF version)
Assignment 4 (PDF version)
Assignment 5 (PDF version)
Tutorial (PDF version)

PopQuizzes: (Sorry, most of the popquizzes are not available online.)

Popquiz 1

Lecture notes:

Last year's notes pdf version Note: this covers only the first part of the course and has some gaps, but will be useful for the theoretical introduction of order notation and some examples to get used to this. It also contains a lot of material on recurrence equations which we are not covering this year (due to more emphasis on recurrence equations in Discrete Structures this year), but if you struggle with them I suggest revising this material (otherwise you'll have difficulty with the algorithm analyses in this course).
InsertionSort and BubbleSort analysis pdf version
MergeSort analysis pdf version
QuickSort analysis pdf version
Strassen's matrix multiplication algorithm pdf version
Search algorithms pdf version

Last updated: February 2004
Back to Konrad Scheffler's homepage