Algorithm Design Techniques

 COMP 360              Fall 2009   Trottier 0060   TuTh 11:35 - 12:55

return to:  course home page      also check:  announcements

Required Text: Algorithm Design, J. Kleinberg and E. Tardos, Pearson 2006.

Additional material for this text available from WebCT

Prerequisite:  308-251
 Students without the prerequisites will be deleted from the course list.

There will be one midterm exam (20%)  and a final exam (60%) in the exam period.
There will be 4 or 5 homework assignments (20%). 

Late assignments  -10% per day, including weekends.

Topics:   Subject to revision. 

Introduction (1 lecture)

Greedy Algorithms (3 lectures)

Dynamic Programming (3 lectures)

Network Flows (3 lectures)

Matchings (2 lectures)

Review (1 lecture), Midterm (1 lecture)

Linear and Integer Programming (2 lectures)

NP-complete problems (4 lectures)

Approximation algorithms (4 lectures)

Wrap up and Case Study: Travelling Salesman Problem (1-3 lectures)

Texts on Reserve at PSEL(Schulich) Library:

Algorithm Design, Kleinberg and Tardos

Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein

Computer Algorithms, Baase and Van Gelder

Instructor:  David Avis
McConnell 308            
Office Hours: Tu, Thurs 10-11

Teaching Assistants:

Theresa Deering          theresa.deering at
Gheorghe Comanici        ghitzah at

Mandatory statements:

In accord with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.

McGill University values academic integrity.  Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see for more information).


August 25, 2009