## Honours Algorithm Design

**308-362B
Winter 2016 Trottier 1080 MW 8:30-10:00**

return to: course home page also check: announcements

**Texts:
***Algorithm Design*,
Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006 (not required)

*Linear Programming, *
Vasek Chvatal, W.H. Freeman, 1983 (this text will be made available online)

We will use Chvatal for the first part of the course. It is out of print but the appropriate sections will be provided to students.

**Prerequisite:** COMP252

Students without the prerequisites will be
deleted from the course list.

**Assessment:**

There will be one midterm exam, in class on march 8th,
and a final exam in the exam period. There will be 5 or 6 homework assignments.
It will be possible to obtain up to 20 marks on the assignments and up to 20
marks on the midterm exam. The final will be worth the remainder. Thus if a student
obtains 13 points on the assignment and 17 on the midterm then he has 30/30
for term work and his final is marked out of 70.

Assignments are to be emailed to the TA.

Late assignments will not be accepted or marked.

**Topics: (tentative)**
Linear and Integer Linear Programming (6 lectures)

NP-complete problems (4 lectures)

Midterm (1 lecture)

Dealing with NP-complete problems (14 lectures)

Review and Perspective(1 lecture)

**Other Resources**
*Introduction to Algorithms,* Cormen, Leiserson,
Rivest, Stein

*Computer Algorithms*, Baase and Van Gelder

**Instructor: ** Bruce Reed

McConnell 301 breed@cs.mcgill.ca
Office Hours: Wednesday; 10:00-12:00

Professor Reed's office hours on March 23,30, and April 6th are cancelled,
He will hold office hours from 10-12 on March 24th and April 7th, and be
available for consultation by email the week of the 30th.
**Teaching Assistant:**

Lena Yuditsky

McConnell 109 yuditskyl@gmail.com
Office Hours: Monday 13:00-15:00

**Midterm:** in class March 8th

*Final exam:* tba

In case you have not 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
here for more information.)

*Last update:January 2 2013*