Computer Science 308-362B
Honours Algorithm Design

Instructor: Prof. Bruce Reed  

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.

Course Outline 

Assignments

Lecture summaries and links

Announcements