1. [Yair Bartal] Suggest a novel online problem, preferably from your own
personal field of interest. Formalize it as well as you can and propose at
least two online algorithms for it. If possible, analyse the competitive
ratio of these algorithms, and indicate whether (and why) you can expect
your algorithm to achieve the best possible ratio (or close). Otherwise,
say as much as you can about the problem, e.g., what special cases of the
problem are easy to understand and under what conditions.

2. Give an implementation of the TIMESTAMP algorithm. Do you need one, two,
or more time stamps per element? Can you somehow restrict the number of bits
needed for representing a time stamp?

3. [Exercise 2.3] Modify the BIT algorithm so that it will also work for
the dynamic list model.

4. Make a library/Internet search to find out what is known about the optimal
offline algorithm for the list accessing problem. Especially, I am interested
in the running time of the optimal offline algorithm when the request
sequence is given.

5. Recall that in the ski rental problem there are T days of skiing (T is
unknown in advance). At the beginning of each day one has to decide whether
to rent skiing equipment at cost of 1 or buy at a cost of B (and then stop
renting). Propose randomized online strategies for this problem. What can
you say about the competitive ratio of your algorithms?