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:
-
Phases.
-
The Cruel Adversary.
-
LRU.
-
MRU.
-
The Oblivious Forgetful Adversary.
-
The Forgetful Randomized Paging Algorithm.
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