Algorithm Design Techniques

COMP 360 Fall 2006 Trottier 1090 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.

Assessment:
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: (revised 2006.8.7) 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 avis@cs.mcgill.ca http://cgm.cs.mcgill.ca/~avis
Office Hours: Tu, Th 10:00-11:00

Midterm: October 19 in class.

Final exam: TBA

Academic Integrity: Please read http://www.mcgill.ca/integrity/

August 7, 2006