COMP-362: Honours Algorithm Design

Fall 2009

 

Time:

Tuesday and Thursday from 11:30am to 1:00pm

Room:

ENGTR 0070 (Trottier building)

 

Instructor:

Prof. Patrick Hayden

Office:

108N McConnell

Phone:

398-5491

Office hours:

Wednesday from 9am to 11am

Email:

patrick@cs.mcgill.ca

 

Teaching assistant:

Anil Ada (McConnell 337)

Office hours: Mondays 10-12


Topics:

Dynamic programming. Linear and integer linear programming. Graph algorithms: shortest paths, flows and matchings. NP-complete problems. Approximation algorithms. Fixed-parameter tractability. (3 credits)

 

Grading:

~5 homework assignments:

35%

 

25%

Midterm exam:

15%

or

0%

Final exam:

50%

 

75%

 

Course web page: http://www.cs.mcgill.ca/~patrick/cs362/2009A

Further materials, including a course discussion area, can be accessed through the Web CT Vista system:

Visit http://www.mcgill.ca/mycourses and log in using your McGill ID.

 

Topics and readings lecture by lecture:

http://www.cs.mcgill.ca/~patrick/cs362/2009A/readings.html

 

Other resources:

Lecture outlines from: 2003, 2004, 2005, 2008.

 

In case you haven’t heard:

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

 

Course textbooks:

 

Required: Algorithm Design

by Kleinberg and Tardos

 

Algorithm Design

 

Recommended: Introduction to Algorithms, 2/e

by Cormen, Leiserson, Rivest and Stein

 

 

Available free online from McGill or using VPN. Free registration required.

http://library.books24x7.com/toc.asp?bookid=3444