Work Functions. We say that a work function w is a "cone" if Supp(w) consists of a single configuration. We define an operator called "update." If w is a work function and r is a request, then (w update r) is a work function. The meaning of the update operator is that, if w is the work function before a request r, then (w update r) is the work function after that request. Thus, if r^t is the request at step t, and if w^t is the work function after step t, then w^t = (w^{t-1} update r^t). What is the domain of a work function? This is controversial, as there are two sensible answers. Define Config_t to be the set of all configurations that are possible after step t, according to the rules of the problem. For example, in the paging problem, Config_t is all possible cache configurations which contain the page r_t. It would make sense to say that the domain of the work function w^t is Config_t, but an alternative is to define the domain of w^t to be Config, the set of all configurations. In the paging problem, Config is the set of all distinct unordered k-tuples of pages. {Footnote: unordered, because from the standpoint of work functions, all cache locations are equivalent, and it does not matter how long a given page has been in the cache. This is true despite the fact that some online algorithms, such as LRU, keep an ordering of the cache pages based on how long they've been in the cache.} The way to think of it is that we change change the rules so that, after reading or writing the requested page, an algorithm can eject any number of pages (including the one just requested) and replace them with arbitrary other pages, at a cost of 1 each, of course. We call this a "non-lazy move," and an algorithm that never makes such a move we call "lazy." Common sense tells us that an algorithm can do just as well or better by never making non-lazy moves, but an offline algorithm could do it without harm by using its knowledge of the future. By allowing non-lazy moves, any configuration can be achieved after each step, thus allowing the domain of the work function to be all of Config. Theoretically, these two approaches are equivalent, so the choice should be made on practical grounds. For purposes of computer programs, restricting the domain is usually the best choice, because it decreases the size of the data structures needed. But for purposes of writing definitions and proofs, allowing the domain to be Config is simpler, so that is the choice we make. {Footnote: if you were writing a program, even Config_t might be very large, so you would like the domain of w^t to be even more restricted. How small could you make it?} Let X^0 be the initial configuration, i.e., the initial cache. Define w^0 as follows: for any configuration Y, w^0(Y) = |X^0,Y|. Thus, Supp(w^0) = {X^0}. If w is any work function and if r is any request, let Config_r be the set of all possible cache configurations that contain r. We then define the work function (w update r) as follows: For any configuration Y, (w update r)(Y) = min_{X in Config_r}(w(X) + |X,Y|). Finally, for any step t, define w^t = (w^{t-1} update r^t), where r^t is the request at step t. Note that we abuse notation by writing Config_r^t and Config_t to mean the same thing. Exercise we'll work Monday in class: Consider the request sequence (abc)daeac for the paging problem for k=3. Compute Supp(w^t) for t = 0,1,2,3,4,5. Try to work it out in advance so that you can help me.