University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

Computer Science 789
Topics: Online Algorithms
Fall 2006
Assignments and Lecture Topics

Revised December 20, 2006

Background.
Please review elementary probability.
Tuesday August 29, 2006.
Today we will discuss the meaning of an ``online" problem, and give two classic examples: the ski-rental problem and the cow path problem.
Please read Bartal's notes for Lecture 1.
The material for the first several lectures is included in the first Chapters 1 through 4 of your textbook.
Thursday August 31, 2006.
We will continue our discussion of the paging problem (or caching problem, or page replacement probelem), and we will introduce amortized analysis and the potential method of cost analysis. Unfinished topics will be carried over to Tuesday.
In preparation for today's lecture, please read Bartal's notes for Lecture 2 and Bartal's notes for Lecture 3.
If we finish the material above, I might begin the discussion of randomized algorithms for the paging problem.
Tuesday September 5, 2006.
We will continue our discussion from Thursday.
Be sure to read Bartal's notes for Lecture 4.
Thursday September 7, 2006. We will continue the same topics. I will present the proof of the 2-competitiveness of the Eager Watchman|(pdf version).
Tuesday September 12, 2006.
Turn in Assignment 1 at the beginning of class today.
Thursday September 14, 2006.
I will discuss some randomized algorithms for the paging problem.
Tuesday September 19, 2006.
We will discuss the homework problems due Tuesday. In particular, I will discuss an online algorithm for computing optimal offline costs.
Thursday September 21, 2006.
Get a clue! postscript format | pdf format.
I will continue giving hints on how to analyze online problems, with emphasis on reduction of non-perfect information games to perfect information games.
Tuesday September 26, 2006.
Turn in Assignment 2 at the beginning of class today.
I will spend most of the lecture going over how to work the ``Watchman" homework problems.
The Underemployed Watchman problem was a very fortunate choice, as it is quite simple to state, and yet has allowed us to visit most of the serious issues of the subject of competitive analysis of online algorithms. It is necessary for all students to firmly grasp the lessons learned before we move on to the more complex, traditional problems, such as the paging problem, the server problem, and the CNN problem.
Thursday September 28, 2006.
I will complete the analysis of the Underemployed Watchman problem.
Helpful concepts.
Tuesday October 3, 2006.
I will finish up the proof for the last homework problem.
Although the oblivious adversary does not know where the watchman is, it knows the watchman's program, and hence can compute the probability that the watchman is in state A, which we call pA.
Thursday October 5, 2006.
Solution to the last problem in postscript form.
Solution to the last problem in pdf form.
Tuesday October 10, 2006.
Thursday October 12, 2006.
Today we will discuss paging problems some more. Work these problems: postscript form pdf form
Tuesday October 17, 2006.
Thursday October 19, 2006.
Tuesday October 24, 2006.
The homework page was updated at Tue Oct 24 09:15:19 PDT 2006. postscript form pdf form
Thursday October 26, 2006.
Most of these problems are really due today. postscript form pdf form
No more extensions for the following problems:
Extensions for the other problems will have to be negotiated.
Tuesday October 31, 2006.
We will continue our discussion of the paging problem.
Thursday November 2, 2006.
We will introduce metrical task systems.
Tuesday November 7, 2006.
After intense pressure, I've given in and extended the due date of the homework to November 9.
We will continue our discussion of metrical task systems. postscript form pdf form
Thursday November 9, 2006.
Tuesday November 14, 2006.
Thursday November 16, 2006.
Tuesday November 21, 2006.
Thursday November 23, 2006.
Thanksgiving Day holiday.
Tuesday November 28, 2006.
Turn in the first part of the metrical task system assignment. The assignment manuscript was last updated at Nov 21 09:38 2006 PST
Thursday November 30, 2006.
Today I will talk about the server problem. See also this page. Here are instructions on how to read that page.
Tuesday December 5, 2006.
Notes on metrical task systems.
Notes on the paging problem.
Notes on the k-server problem.
Thursday December 7, 2006.
The mts file is updated, as of Wed Dec 13 04:38:50 PST 2006
Turn in the rest of the metrical task systems problems. postscript form pdf form
Thursday, December 14.
Final Examination. The final examination is scheduled for 10:10 AM. The examination will be comprehensive.
Hints for Problem 8 on the final exam.
Hints for Problem 9 on the final exam.
Practice final in postscript form.
Practice final in pdf form.
Wednesday, December 20.
I have submitted the grades to the registrar. You can access them online.
Have a Merry Christmas and a Happy New Year.

Back to Course Page