## Algorithm Design Techniques

**COMP 360B
Winter 2004 Trottier 1090 TuTh
10:05-11:20am**

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.

Assignments are to be left in the box , McConnell
1st floor.

Late assignments -10% per day, including
weekends.

**Topics: (tentative)**
Introduction (1 lecture)

Greedy Algorithms (2 lectures)

Minimum Spanning Trees (2 lectures)

Dynamic Programming (2 lectures)

Shortest Paths in Graphs (2 lectures)

Network Flows (2 lectures)

Review (1 lecture), Midterm (1 lecture)

Matchings (2 lectures)

Linear Programming (2 lectures)

NP-complete problems (4 lectures)

Linear Programming (2 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
11:30-12:30

Teaching Assistants:

Maxime Descouteaux <mdesco@cim.mcgill.ca>

Office Hours: Mon 11-12, McConnell
408

Michel Langlois <michel.langlois@mail.mcgill.ca>

Office Hours: Wed 1-2, McConnell 111

**Midterm:** March 4, in class
(Note new date!)

*Final exam:* tba

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

Feb 9, 2004