Computer Science 789 Online Algorithms
Fall 1999
Assignments
This page will be updated frequently.
Most recent update: December 7, 1999.
-
August 31, 1999.
The topics of today's lecture will be
-
Review of Proof Techniques.
-
Review of Dynamic Programming.
-
September 2, 1999.
The topics of today's lecture will be
-
Symbolic Logic.
-
Review of Proof Techniques.
-
Review of Dynamic Programming.
-
Game Theory and Game Graphs.
-
September 7, 1999.
The topics of today's lecture will be
-
Game Theory and Game Graphs.
-
Review of Probability.
-
Potentials.
-
September 9, 1999.
-
Today we will not introduce much new material.
Instead, we will follow the Central European tradition of
having an "exercise session" in which we will go over
some of the missing proofs in the handouts.
-
In addition, time permitting, we will introduce
game potentials.
-
Homework due.
Assignment 1
will be due on Tuesday, September 14, in class.
-
September 14, 1999.
The primary topic of today's lecture will be
-
An introduction to competitiveness.
Please read everything in your textbook up to page 19.
-
We will also go over some of the homework problems.
-
October 5, 1999.
The primary topic of today's lecture will be
game graphs and how they are useful for competitive analysis.
Dr. Bein will introduce the topic, giving specific game graphs that are
useful for competitive analysis of the paging problem.
Take a look at Anna Naydenova's drawing of
the master graph for
lower bound proofs for the trackless paging problem for k=2,
which Dr. Bein introduced during today's lecture.
Please look at the updated versions of
Handouts 3 and 4.
-
Homework due.
Assignment 2
will be due on Thursday, October 7, in class.
-
October 7, 1999.
The primary topic of today's lecture will be
game graphs and how they are useful for competitive analysis.
At least two students will present solutions to homework problems on the
board.
We will also show how to use competitive game graphs to find bounds on
the competitiveness of a number of deterministic and randomized
algorithms, including the homework problems due today.
-
October 12, 1999.
Dr. Bein will be lecturing today. He will be demostrating the reduction
of the problem of finding the competitiveness of a simple algorithm
for the paging problem to a problem involving game graphs.
-
October 14, 1999.
The primary topic of today's lecture will be
proof of the lower bound of for competitiveness of randomized algorithms
for the paging problem.
We shall see how MIXED0 and MARK for k = 2 are the barely random
and the behavioral versions, respectively, of the same concept.
-
October 19, 1999.
Dr. Bein will be lecturing today while I am attending an articulation
conference at UNR. I might get back in time for the last part of class.
Although subject to change without notice, his plan is to present the
1-bookmark algorithm for the paging problem for k = 2.
-
October 21, 1999.
We will backtrack once again over missing details of the proof of the
1.5-competitiveness of the
1-Bookmark algorithm for the paging problem for cache size 2.
-
October 26, 1999.
We will introduce work functions for metrical task systems, a very
general model that includes many problems, such as the paging problem
and the k-server problem.
-
October 28, 1999.
We will continue our discussion of work functions in metrical task systems.
-
November 2, 1999.
We will continue our discussion of work functions in metrical task systems,
and will work out the competitiveness of the example given last Thursday.
-
November 4, 1999.
We will show how the problem of determining competitiveness of a particular
metrical task system reduces to the problem of determining the competitiveness
of a game graph where the black nodes are the offset functions.
-
November 9, 1999.
We will introduce the work function algorithm (WFA) for metrical task systems.
We will give a detailed analysis of the paging problem using work functions.
We will discuss the relationship between LRU and WFA for the paging problem.
We will introduce the "Workfunctions are Everything" theorem.
Basically, any algorithm for any metrical task system can be
replaced by a work-function based algorithm that is at least as good.
-
Homework due.
Assignment 3
will be due on Tuesday, November 16, in class.
-
Quiz.
There will be a short quiz
on Tuesday, November 23.
Postscript version.
-
Final Examination.
The final examination
will be given at 18:00 on Tuesday, December 14, in our
regular classroom. It will be two hours in length.
In order to work Problem 2 on the final exam, you should use Corollary 2
in Handout 8.

Back to
Course Page