Lectures: Mon, Wed 4:30-5:20. Fridays 3:30-4:20. (If there is any difficulty with this time change, please email me.) Ryerson 276
Homepage: http://www.cs.uchicago.edu/~kalai/online2004
Course Description: The course will cover competitive analysis of online algorithms. Offline algorithms attempt to make optimal decisions with full information about a problem. In contrast, online algorithms make a sequence of decisions, in the face of unknown future information. Online algorithms bring together problems (and ideas) from a variety of areas, such as caching, game theory, finance, routing, data structures, and statistics. A unifying, small set of tools may be applied to all of these problems.
Admin: Grading will be based on a collection of homework assignments, a take-home final, and class participation. As part of class participation, each student will give a class presentation on a topic chosen in consultation with the instructor.
Readings: There is no required textbook. Instead, a collection of survey papers, lecture notes, and research papers will be made available on the course webpage and/or handed out in class. A recommended (but not required) text is Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv. This book will be available to review in the TTI library.
Pieces of this course are based on a course on Approximation and Online Algorithms by Avrim Blum.