Computer Science 789 Randomized Online Algorithms
Spring 2002
Assignments
This page will be updated frequently.
Most recent update: May 6, 2002.
-
January 23, 2002.
-
January 28, 2002.
-
Continuing discussion of the LFD algorithm.
-
January 30, 2002.
-
What does without loss of generality mean?
-
LFD is optimal for the paging problem.
Additional topics discussed on this page:
-
The paging problem satisfies the local optimality hypothesis
(LOH).
-
Does every online problem satisfy LOH? (Answer to be revealed in class.)
-
What can an online observer know about LFD's cache?
-
Find an optimal offline algorithm for the paging problem for k = 2
which does not satisfy LOH. This you should do on
your own before class on Wednesday. The hint is given on
the page.
-
Suppose that some other optimal offline algorithm "Opt," not necessarily LFD,
is used as a benchmark.
What can an online observer know about Opt's cache?
This is a much harder question, but it is important to be
able to understand it.
-
Work Functions.
-
Updating Work Functions.
-
February 4, 2002.
-
February 6, 2002.
-
Homework to Hand In in class Wednesday, February 6.
-
Today we will go over the Bookmarks
algorithm in class, filling in all the missing details of that proof.
-
February 11, 2002.
-
February 13, 2002.
-
February 20, 2002.
-
We will discuss work functions for the task system problem, and solve
the deterministic Ice Cream Problem, as given in
Dagstuhl Seminar 9626
I was unable to find a web page with the article, although I feel certain
that it's out there.
Since it's been a long time since Marek and I published that paper, I do
not remember whether our failure to coalesce equivalent "red" nodes was
deliberate. However, I am certain that we did not intend to make those
errors in the costs that we uncovered Wednesday.
-
February 25, 2002.
-
Today, we will continue working on the red-black graph that we
had on the board last Wednesday. I will bring full-page color copies
of the graph to class for everyone.
-
We will prove that the deterministic competitiveness of the problem
is 7/6, and in the process give a general method.
-
We will then discuss randomized algorithms for the same problem.
The randomized competitiveness is 12/11 against the oblivious adversary.
-
Read nfa and game.
Figures 1 through 5 will be distributed in class.
-
February 27, 2002.
Read boost, page 1 and
boost, page 2.
Today we will give a simple randomized algorithm for the ice cream problem
which is 11/10 competitive against the oblivious adversary.
-
March 4, 2002.
-
March 6, 2002.
-
The algorithm I gave Monday March 4 is not the simplest possible that is
optimally competitive. Improve my algorithm and
turn it in today.
-
March 11, 2002.
-
March 13, 2002.
-
March 18, 2002.
-
Today we will talk about the Uniform Metrical Task System (UMTS) problem.
-
The deterministic competitiveness of the MTS problem, with k states,
is 2k-1.
-
The randomized competitiveness of the UMTS problem, with k states,
is known to be between Hk and 2Hk.
-
For k = 2, the randomized competitiveness of the UMTS problem is
known to be 2, although the result (by
Chrobak and
Noga ) is not published.
-
March 20, 2002.
-
April 1, 2002.
-
Today we will finish up the discussion of the UMTS problem and move
on to the server problem.
-
HARMONIC is a memoryless randomized algorithm for the k-server problem.
There is a known lower bound on its competitiveness, which is conjectured
to be the true value. This conjecture is known to be true for k = 2, but
is open for larger k.
-
Random-Slack is a memoryless randomized algorithm for the 2-server
problem. Its competitiveness is known to be exactly 2.
(The competitiveness of any randomized online algorithm is taken to be
against the oblivious adversary unless otherwise specified.)
-
April 3, 2002.
-
Today we will continue the discussion of the server problem.
-
Task Systems (still being worked on)
-
April 6, 2002.
-
I am working on stuff for the exam, which is now scheduled for April 15.
Look for pointers to material here later today.
-
The Server Problem (still being worked on)
-
April 8, 2002.
-
April 10, 2002.
-
There is more stuff at
Task Systems.
-
I have moved lots of old pages into new directories, and tried to update the
links properly. It will be amazing if
I've made no mistakes, so if you detect a problem, please let me know.
-
I sent a "test email" to everyone in class whose email address I know.
If you didn't get it, I don't have your email address, so please send it
to me.
-
The pages behavioral potentials I
and behavioral potentials II have been
corrected and completed.
-
April 15, 2002.
Examination today. Closed book, no notes.
-
April 22, 2002.
-
May 13, 2002.
Final examination today. Closed book, no notes.

Back to
Course Page