CS 466/666, Fall 2008

Advanced Algorithms

(link to CS466/666, Fall 2007)

Instructor:

Ian Munro (DC2343, x34433, imunro "at" cs, office hrs:

I will be available from 10 to 12 most mornings until the exam

Meeting Time/Place:

Tues/Thurs 1:00-2:20, ES1 350

TAs:

Arash Farzan (DC2305B, x35351, afarzan "at" cs, office hrs:Wednesdays 11:00am-12:00pm)
Adam Bains (DC3551, x34714, abains "at" cs, office hrs:Wednesdays 3:00pm-4:00pm)

References:

There is no required textbook for this course. The following references have been placed on reserve in the DC library (for 3 hour loan), if they are of any assistance.

Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (2nd ed.), MIT Press, 2001 (QA76.6.C662) [CLRS]
Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68) [MR]
Vazirani, Approximation Algorithms, Springer-Verlag, 2001 (QA76.9.A43 V39) [V]
Borodin and El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998 (QA76.9.A43 B67) [BE]

Course Work:

General Policies
Assignment 1 (out September 16; due September 25 at noon)
Assignment 2 (out September 25; due October 9 at noon)
Assignment 3 (out October 9; due October 23 at noon)
Midterm (October 30 in class; this covers material up to and including Oct 28): An old midterm (with same instructor) is available.
Assignment 4 (out October 30; due November 13 at noon)
Assignment 5 (out November 13; due November 27 at noon)
Final exam (Dec 10 at 12:30)
Project for CS666 students (due December 15 at noon)

[Solutions can be found on reserve in the DC library (UWD: 1097)]

Announcements:

(Important announcements will be posted here.)

December 5: Assignment 5 ready for pick-up from DC2305B (refer to the posting in the newsgroup for details).
December 5: Solutions to all assignments are available in the library.
October 25: Assignment 3 solutions are in the library.
October 22: An old midterm (with same instructor) is available.
October 22: Solutions to assignment 2 is available in the library.
October 8: Solutions to assignment 1 are posted in the library (UWD: 1097).
September 29: Assignment 2 is fixed (last question corrected).
September 22: Assignment 1 is touched up and replaced. In particular, in problem 3, the production rule A::=A is corrected to A::=a. Moreover, in problem 5, an edge (e->f) with weight 2 is added to the example graph.

Newsgroup:

news:uw.cs.cs466 (for additional info, questions and replies from the TA, etc.)

Lecture Topics:

The lectures are organized around problems instead of techniques, to motivate things better. We usually devote more than a lecture to each problem and then 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 only for materials covered in the lectures (summarized below), but I have included below some extra references to papers and book chapters, mainly to introduce research issues to grad students (undergrad students: please ignore them, unless you have developed an intense passion for one of the problems :-). Note that these references are generally harder to read or go beyond the lecture materials.]

Topics of September 9, 11, 16:
Dynamic Programming and Greed: Optimal binary search trees (and a second example of dynamic programming)