2016-17 Academic Catalog

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. Prerequisite: Computer Science 252 or instructor permission