COMP-362: Honours Algorithm Design

Fall 2011

 

Time:

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

Room:

McConnell 103

 

Instructor:

Prof. Patrick Hayden

Office:

108N McConnell

Phone:

398-5491

Office hours:

Wednesday from 9am to 11am

Email:

patrick@cs.mcgill.ca

 

Teaching assistant:

Omar Fawzi (omar.fawzi@mail.mcgill.ca)

Office hours: Mondays 9:30-11:30 in McConnell 311


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 materials:

Alexandre Fréchette’s lecture notes from the 2009 version of this course.

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/2011A/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: Algorithms

by Dasgupta, Papadimitriou and Vazirani

 

       

A late draft is available for free online.

 

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