Piazza page: https://piazza.com/umanitoba.ca/fall2017/comp7720
All announcements for the class will be posted on the Piazza page. The page will also be the central place for class discussions and for any questions about the lectures and assignments.
Description:
This course provides an introduction to online algorithms and their applications. In contrast to the traditional `offline' algorithms, an online algorithm does not have access to the whole input. Instead, it receives its input piece by piece as a sequence. Upon receiving a piece of the input, the algorithm has to take an irreversible decision to process it. Online algorithms have many applications in practice, and have been studied extensively in theory also.
Our goal in this course is to design and analyze online algorithms with provable theoretical guarantee on the quality of the resulting solutions.
We cover a variety of online problems in different contexts which include system problems (e.g., paging), data structures (e.g., self-adjusting lists), graph problems (e.g., coloring and matching), packing problems (bin packing and scheduling), computational geometry (searching and exploring) problems. We also study alternative analysis techniques which have been recently introduced (e.g., advice complexity and bijective analysis).
The course involves a project for which students are expected to work an online setting of a problem (possibly related to their own research) and design and analyze online algorithms for such problem.
Here is a sample exam; the final exam will be similar to this sample, and its questions will have same headings.
Here are the solutions for the final exam.
Textbooks:
There is no required textbook. We use "Online Computation and Competitive Analysis" by Borodin and El-Yaniv as a reference.
Throughout the course, students are referred to surveys and research papers with respect to their project.
Projects:
An important component of the course a final research project.
Here is a template for project proposal. The Latex files for the template can be found here and here.
Here are some notes and tips you can use when preparing your presentations.