ASSIGNMENT 5 IS MARKED AND AVAILABLE FROM KAMRAN  DC2305 FRIDAY PM, and MONDAY, TUESDAY and after the exam

Class Time: Tuesdays and Thursdays 11:30 - 12:50 in DWE 3516    

Instructor : I. Munro 

Office: DC2343    Phone: ext 34433    email:     Office Hours: after class or by appointment

TA: K. Tirdad

Office: DC 2305    Phone: ext 35351    email: ktirdad (at) uwaterloo.ca     Office Hours: Wednesdays 4-5 or by appointment

The course continues the discussion of algorithms started in CS 341. Whereas CS 341 focuses on worst-case behaviour of deterministic algorithms, in this course students are exposed to algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and applications. However, in order motivate things better, the lectures are organized around problems instead of techniques. We usually devote more than a lecture to each problem and explore different ideas to devise an efficient algorithm. Along the way, we will indeed encounter new design techniques and variations on the analysis model (themes like amortization, randomization, approximation, online computation, etc., as promised in the handbook description), but the main emphasis is how to think about problems.
[You are of course responsible primarily for the material covered in the lectures (summarized below). The references to Cormen et al tend to give fuller explanations than time permits in class, they also include material you have seen in CS 341 and CS240. I have also included references to the original papers, mainly to introduce research issues to grad students. Note that these references are generally harder to read or go beyond the lecture materials.]

More details on the goals and coverage of the course can be found in the official course description.