Official catalogue description:
A second course on designing and analyzing efficient algorithms to
solve computational problems. We will survey some algorithmic design
techniques that apply broadly throughout computer science, including
discussion of wide-ranging applications. A sampling of potential
topics: approximation algorithms (can we efficiently compute
near-optimal solutions even when finding exact solutions is
computationally intractable?); randomized algorithms (does flipping
coins help in designing faster/simpler algorithms?); online algorithms
(how do we analyze an algorithm that needs to make decisions before
the entire input arrives?); advanced data structures; complexity
theory. As time and interest permit, we will mix recently published
algorithmic papers with classical results.
Course Materials:
There is an anonymous feedback form
available for any comments that you have about the course. If you
have any suggestions or comments on the class (style, content,
workload, etc.), please feel free to use this form to let me know.
The CS department has an email newsletter, the
Carleton Sentinel, that we use for occasional updates on things
that might be of interest. Sign up here!
The final project will be: you read a paper with
a group; your group presents in approximately 15 minutes the
highlights of the problem and the solution. Links to the
papers that I propose follow. You may also propose an alternative.