Computer Science 308-362B
Honours Algorithm Design

Winter 2016   Trottier 2120     TR 14:30 -16:00

Instructor: Prof. Bruce Reed

Assistant: Yelena Yuditsky  

Description: 3 credits; 3 hours; Prerequisite: 308-252,  
In previous courses, you have learnt how to analyse an algorithm to determine its computational complexity(worst case running time) and techniques for designing efficient algorithms to solve problems(dynamic programming, divide and conquer, and greedy approaches). This course focuses on problems for which we are unable to find such efficient algorithms. We first discuss how to show that it is unlikely we will find an efficient algorithm for a given problem. We then discuss how to handle such problems (settle for approximate not exact solutions, restrict our attention to easy instances of the problem, settle for a randomized algorithm which we expect to work quickly). This is an honours version of 360, with correspondingly more difficult course work and exams.


Note:  Students without prerequisite will be deleted from course list. 

* Course Outline 
* Assignments
* Lecture summaries and links
* Announcements

[ SOCS HOME ]

Send comments/questions to breed@cs.mcgill.ca

Jan 2,  2014