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