## Algorithm Design Techniques

**COMP
360
Winter 2008 Trottier 0060 TuTh
10:05-11:25**

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: 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: M
10:30-11 W 1-1:30 or by appointment.

No office hours April 14-18

Teaching Assistant: Anil
Ada aada at
cs.mcgill.ca

For
office hours and other information: http://www.cs.mcgill.ca/~aada/360.html

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

January 8, 2008