## Algorithm Design Techniques

**COMP
360A
Fall 2005 Trottier 0060 TuTh
11:35-12:55**

return to: course home page
also check:
announcements

**Required Text: ***Introduction to
Algorithms*, Cormen, Leiserson, Rivest, Stein (2nd edition)

Full text available on-line at: http://www.library.mcgill.ca/lists/books247.html

**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 homework
assignments (20%). The higher of the mark computed in this way and your
final exam
mark (taken as 100%) will be converted to a letter grade.

Late
assignments -10% per day, including weekends.

**Topics: (revised 2005.9.7) Subject to
revision. **
Introduction (1 lecture)

Greedy Algorithms (2 lectures)

Network Flows (2 lectures)

Matchings (2 lectures)

Linear Programming (3 lectures)

Review (1 lecture), Midterm (1 lecture)

Integer Programming (1 lecture)

NP-complete problems (4 lectures)

Dealing with NP-complete problems (4 lectures)

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

**Texts on Reserve at PSEL(Schulich) Library:**
*Introduction to Algorithms,* Cormen,
Leiserson, Rivest, Stein

*Computer Algorithms*, Baase and Van
Gelder

**Instructor: ** David Avis

McConnell 308 avis@cs.mcgill.ca
http://www.cs.mcgill.ca/~avis

Office Hours: Tu, Th
10:00-11:00

Teaching Assistants:

Melanie Coggan

Office Hours: W 12-1 pm mcogga@cs.mcgill.ca

T.A. room, Trottier 3106

**Midterm:** October 20 (tentative) in
class.

*Final exam:* Thurs, Dec 8, 2-5pm,
Wong 1050

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

August 26, 2005