## 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