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

**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: Tu, Thurs
10-11

Teaching Assistants:

Theresa Deering theresa.deering at mail.mcgill.ca

Gheorghe Comanici ghitzah at gmail.com

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 **www.mcgill.ca/integrity**
for more
information).** *

August 25, 2009