Lec 14 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Lecture 14: Competitive Analysis: Self-organizing Lists

View the complete course at: http://ocw.mit.edu/6-046JF05

License: Creative Commons BY-NC-SA

More information at http://ocw.mit.edu/terms

More courses at http://ocw.mit.edu

And this is going to use some
of the techniques we learned

last time with respect to
amortized analysis.

And, what's neat about what
we're going to talk about today

is it's a way of comparing
algorithms that are so-called

online algorithms.
And we're going to introduce

this notion with a problem which
is called self organizing lists.

OK, and so the set up for this
problem is that we have a list,

L, of n elements.
And, we have an operation.

Woops, I've got to spell things
right, access of x,

which accesses item x in the
list.

It could be by searching,
or it could be however you want

to do it.
But basically,

it goes and touches that
element.

And we were to say the cost of
that operation is whatever the

rank of x is in the list,
which is just the distance of x

from the head of the list.
And the other thing that we can

do that the algorithm can do,
so this is what the user would

do.
He just simply runs a whole

bunch of accesses on the list,
OK, accessing one element after

another in any order that he or
she cares to.

And then, L can be reordered,
however, by transposing

adjacent elements.
And the cost for that is one.

So, for example,
suppose the list is the

following.

OK, I missed something here.
It doesn't matter.

Well, I'll just make it be what
I have so that it matches the

online video.
OK, so here we have a list.

And so, if I do something like
access element 14 here,

the element of key 14,
OK, that this costs me one,

two, three, four.
So here the cost is four to

access.
And so, we're going to have

some sequence of accesses that
the user is going to do.

And obviously,
if something is accessed more

frequently, we'd like to move it
up to the front of the list so

that you don't have to search as
far.

OK, and to do that,
if I want to transpose

something, so,
for example,

if I transpose three and 50,
that just costs me one.

OK, so then I would make this
be 50, and make this be three.

OK, sorry, normally you just do
it by swapping pointers.

OK, so those are the two
operations.

And, we are going to do this in
what's called an online fashion.

So, let's just define online.
So, a sequence,

S, of operations is provided
one at a time for each

operation.
An online algorithm must

execute the operation
immediately without getting a

chance to look at what else is
coming in the sequence.

So, when you make your decision
for the first element,

you don't get to see ahead as
to what the second,

or third, or whatever is.
And the second one you get,

you get and you have to make
your decision as to what to do

and so forth.
So, that's an online algorithm.

Similarly, an off-line
algorithm, OK,

may see all of S in advance.
OK, so you can see an off-line

algorithm gets to see the whole
sequence, and then decide what

it wants to do about element
one, element two,

or whatever.
OK, so an off-line algorithm

can look at the whole sequence
and say, OK, I can see that item

number 17 is being accessed a
lot, or early on move him up

closer to the front of the list,
and then the accesses cost less

for the off-line algorithm.
The online algorithm doesn't

get to see any of that.
OK, so this is sort of like,

if you're familiar with the
game Tetris.

OK, and Tetris,
you get one shape after another

that starts coming down,
and you have to twiddle it,

and move it to the side,
and drop it into place.

And there, sometimes you get a
one step look-ahead on some of

them so you can see what the
next shape is,

but often it's purely online.
You don't get to see that next

shape or whatever,
and you have to make a decision

for each one.
And you make a decision,

and you realize that the next
shape, ah, if you had made a

different decision it would have
been better.

OK, so that's the kind of
problem.

Off-line Tetris would be,
I get to see the whole sequence

of shapes.
And now let me decide what I'm

going to do with this one.
OK, and so, in this,

the goal is for any of the
algorithms, either online or

off-line is to minimize the
total cost, which we'll denote

by, I forgot to name this.
This is algorithm A here.

The total cost,
C_A of S, OK,

so the cost of algorithm A on
the sequence,

S.
That's just the notation we'll

use for what the total cost is.
So, any questions about the

setup to this problem?
So, we have an online problem.

We're going to get these things
one at a time,

OK, and we have to decide what
to do.

So, let's do a worst-case
analysis for this.

OK, so if we're doing a
worst-case analysis,

we can view that we have an
adversary that we are playing

against who's going to provide
the sequence.

The user is going to be able to
see what we do.

And so, what's the adversary
strategy?

Thwart our plots,
yes, that's his idea.

And how is he going to thwart
them, or she?

Which is what for this problem?
What's he going to do?

Yeah.
No matter how we reorder

elements using the transposes,
he's going to look at every

step and say,
what's the last element?

That's the one I'm going to
access, right?

So, the adversary always,
always accesses the tail

element of L.
No matter what it is,

no matter how we reorder
things, OK, for each one,

adversary just accesses the
tail.

So the cost of this,
of any algorithm,

then, is going to be omega size
of S times n,

OK, because you're always going
to pay for every sequence.

You're going to have to go in
to pay a cost of n,

OK, for every element in the
sequence.

OK, so not terribly in the
worst-case.

Not terribly good.
So, people in studying this

problem: question?
That analysis is for the online

algorithm, right.
The off-line algorithm,

right, if you named those
things, that's right.

OK, so we're looking at trying
to solve this in an off-line

sense, sorry,
in an online sense.

OK, and so the point is that
for the online algorithm,

the adversary can be incredibly
mean, OK, and just always access

the thing at the end,
OK?

So, what sort of the history of
this problem is,

that people said,
well, if I can't do well in the

worst-case, maybe I should be
looking at average case,

OK, and look at,
say, the different elements

having some probability
distribution.

OK, so the average case
analysis, OK,

let's suppose that element x is
accessed with probability,

P of x.
OK, so suppose that we have

some a priori distribution on
the elements.

OK, then the expected cost of
the algorithm on a sequence,

OK, so if I put all the
elements into some order,

OK, and don't try to reorder,
but just simply look at,

is there a static ordering that
would work well for a

distribution?
It's just going to be,

by definition of expectation,
the probability of x times,

in this case,
the cost, which is the rank of

x in whatever that ordering is
that I decide I'm going to use.

OK, and this is minimized when?
So, this is just the definition

of expectations:
the probability that I access x

times the cost summed over all
the elements.

And the cost is just going to
be its position in the list.

So, when is this value,
this summation,

going to be minimized?
When the element is most likely

as the lowest rank,
and then what,

what about the other element?
OK, so what does that mean?

Yeah, sort them,
yeah, sort them on the basis of

decreasing probability,
OK?

So, it's minimized when L is
sorted, OK, in decreasing order

with respect to P.
OK, so just sort them with the

most likely one at the front,
and then just decreasing

probability.
That way, whenever I access

something with some probability,
OK, I'm going to access,

it's more likely that I'm going
to access.

And that's not too difficult to
actually prove.

You just look at,
suppose there were two that

were out of order,
and show that if you swap them,

you would improve this
optimization function.

OK, so if you didn't know it,
this suggests the following

heuristic,
OK, which is simply keep

account of the number of times
each element is accessed,

and maintain the list in order
of decreasing count.

OK, so whenever something is
accessed, increment its count,

OK, and that will move it,
at most, one position,

which only costs me one
transposed to move it,

perhaps, forward.
OK, actually,

I guess it could be more if you
have a whole bunch of ties,

right?
Yeah.

So, it could cost more.
But the idea is,

over time, the law of large
numbers says that this is going

to approach the probability
distribution.

The frequency with which you
access this, divided by the

total number of accesses,
will be the probability.

And so, therefore you will get
things in decreasing

probability, OK,
assuming that there is some

distribution that all of these
elements are chosen according

to, or accessed according to.
So, it doesn't seem like

there's that much more you could
really do here.

And that's why I think this
notion of competitive analysis

is so persuasive,
because it's really amazingly

strong, OK?
And it came about because of

what people were doing in
practice.

So practice,
what people implement it was a

so-called move to front
heuristic.

OK, and the basic idea was,
after you access an element,

just move it up to the front.
OK, that only doubles the cost

of accessing the element because
I go and I access it,

chasing it down paying the
rank, and then I have to do rank

number of transposes to bring it
back to the front.

So, it only cost me a factor of
two, and now,

if it happens to be a
frequently accessed elements,

over time you would hope that
the most likely elements were

near the front of that list.
So, after accessing x,

move x, the head of the list
using transposes,

and the cost is just equal to
twice the rank in L of x,

OK, where the two here has two
parts.

One is the access,
and the other is the

transposes.
OK, so that's sort of what they

did.
And one of the nice properties

of this is that if it turns out
that there is locality in the

access pattern,
if it's not just a static

distribution,
but rather once I've accessed

something, if it's more likely
I'm going to access it again,

which tends to be the case for
many input types of patterns,

this responds well to locality
because it's going to be up near

the front if I access it very
soon after I've accessed.

So, there is what's called
temporal locality,

meaning that in time,
I tend to access,

so it may be that I access some
thing's very hot for awhile;

then it gets very cold.
This type of algorithm responds

very well to the hotness of the
accessing.

OK, so it responds well to
locality in S.

So, this is sort of what was
known up to the point that a

very famous paper was written by
Danny Sleator and Bob Tarjan,

where they took a totally
different approach to looking at

this kind of problem.
OK, and it's an approach that

matter you see everywhere from
analysis of caching and

high-performance processors to
analyses of disk paging to just

a huge number of applications of
this basic technique.

And, that's the technique of
competitive analysis.

OK, so here's the definition.
So, online algorithm A is alpha

competitive.
If there exists a constant,

k, such that for any sequence,
S, of operations,

the cost of S using algorithm A
is bounded by alpha times the

cost of opt, where opt is the
optimal offline algorithm.

OK, so the optimal off-line,
the one that knows the whole

sequence and does the absolute
best it could do on that

sequence, OK,
that's this cost here.

This is sometimes called God's
algorithm, OK,

not to bring religion into the
classroom, or to offend anybody,

but that is what people
sometimes call it.

OK, so the fully omniscient
knows absolutely the best thing

that could be done,
sees into the future,

the whole works,
OK?

It gets to apply that.
That's what opts algorithm is.

And, what we're saying is that
the cost is basically whatever

this alpha factor is.
It could be a function of

things, or it could be a
constant, OK,

times whatever the best
algorithm is.

Plus, there's a potential for a
constant out here.

OK, so for example,
if alpha is two,

and we say it's two
competitive, that means you're

going to do, at worst,
twice the algorithm that has

all the information.
But you're doing it online,

for example.
OK, it's a really pretty

powerful notion.
And what's interesting about

this, it's not even clear these
things should exist to my mind.

OK, what's pretty remarkable
about this, I think,

is that there is no assumption
of distribution,

of probability distribution or
anything.

It's whatever the sequence is
that you give it.

You are within a factor of
alpha, essentially,

of the best algorithm,
OK, which is pretty remarkable.

OK, and so, we're going to
prove the following theorem,

which is the one that Sleator
and Tarjan proved.

And that is that MTF is four
competitive for self organizing

lists.
OK, so the idea here is that

suppose the adversary says,
oh, I'm always going to access

the thing at the end of the list
like we said in the beginning.

So, the adversary says,
I'm always going to access the

thing there.
I'm going to make MTF work

really bad, because you're going
to go and move that thing all

the way up to the front.
And I'm just going to access

the thing way at the end again.
OK, well it turns out,

yeah, that's a bad sequence for
move to front,

OK, and it will take a long
time.

But it turns out God couldn't
have done better,

OK, by more than a factor of
four no matter how long the list

is.
OK, that's pretty amazing.

OK, so that's a bad sequence.
But, if there's a way that the

sequence exhibits any kind of
locality or anything that can be

taken advantage of,
if you could see the whole

thing, MTF takes advantage of it
too, OK, within a factor of

four.
OK, it's a pretty remarkable

theorem, and it's the basis of
many types of analysis of online

algorithms.
Almost all online algorithms

today are analyzed using some
kind of competitive analysis.

OK, not always.
Sometimes you do probabilistic

analysis, or whatever,
but the dominant thing is too

competitive analysis because
then you don't have to make any

statistical assumptions.
OK, just prove that it works

well no matter what.
This is remarkable,

I think.
Isn't it remarkable?

So, let's prove this theorem,
we're just going to spend the

rest of the lecture on this
proof.

OK, and the proof in some ways
is not hard, but it's also not

necessarily completely
intuitive.

So, you will have to pay
attention.

OK, so let's get some notation
down.

Let's let L_i be MTF's list
after the i'th access.

And, let's let L be opt's list
after the i'th access.

OK, so generally what I'll do
is I'll put a star if we are

talking about opt,
and have nothing if we're

talking about MTF.
OK, so that's going to be the

list.
So, we can say,

what's the list?
So, we're going to set it up

where we have one in operation
that transforms list i minus one

into list i.
OK, that's what the i'th

operation does.
OK, and move to front does it

by moving whatever the thing
that was accessed to the front.

And opt does whatever opt
thinks is the best thing to do.

We don't know.
So, we're going to let c_i be

MTF's cost for the I'th
operation.

And that's just twice the rank
in L_i minus one of x if the

operation accesses x,
OK, two times the rank in L_i

minus one because we're going to
be accessing it in L_i minus one

and transforming it into L_i.
And similarly,

we'll let c_i star be opt's
cost for the i'th operation.

And that's just equal to,
well, to access it,

it's going to be the rank in
L_i minus one star,

whatever its list is of x at
that step, because it's got to

access it.
And then, some number of

transposes, t_i if opt forms t_i
transposes.

OK, so we have the setup where
we have two different lists that

are being managed,
and we have different costs in

the list.
And, we're interested in is

comparing in some way MTF's list
with opt's list at any point in

time.
And, how do you think we're

going to do that?
What technique do you think we

should use to compare these two
lists, general technique from

last lecture?
Well, it is going to be

amortized, but what?
How are we going to compare

them?
What technique did we learn

last time?
Potential function,

good.
OK, we're going to define a

potential function,
OK, that measures how far apart

these two lists are.
OK, and the idea is,

if, let's define that and then
we'll take a look at it.

So, we're going to define the
potential function phi mapping

the set of MTF's lists into the
real numbers by the following.

phi of L_i is going to be twice
the cardinality of this set.

OK, so this is the
precedes-operation and list,

i.
So, we can define a

relationship between any two
elements that says that x

precedes y in L_i if,
as I'm accessing it from the

head, I hit x first.
OK, so what I'm interested in,

here, are in some sense the
disagreements between the two

lists.
This is where x precedes y in

MTF's list, but y precedes x in
opt's list.

They disagree,
OK?

And, what we're interested in
is the cardinality of the set.

And we're going to multiply it
by two.

OK, so that's equal to two
times; so there is a name for

this type of thing.
We saw that when we were doing

sorting.
Anybody remember the name?

It was very briefly.
I don't expect anybody to

remember, but somebody might.
Inversions: good,

OK, twice the number of
inversions.

So, let's just do an example.
So, let's say L_i is the list

with five elements.
OK, I'll use characters for the

order just to keep things
simple.

So, in this case phi of L_i is
going to be twice the

cardinality of the set.
So what we want to do is see

which things are out of order.
So here, I look at E and C are

in this order,
but C and E in that order.

So, those are out of order.
So, that counts as one of my

elements, EC,
and then, E and A,

A and E.
OK, so those are out of order,

and then ED,
DE, out of order,

and then EB,
BE, those are out of order.

And now, I go C,
A, C, A.

Those are in order,
so it doesn't count.

CD, CD, CB, CB,
so, nothing with C.

Then, A, D, A,
D, those are in order,

A, B, A, B, those are in order.
So then, DB,

BD, so BD.
And that's the last one.

So, that's my potential
function, which is equal to,

therefore, ten,
because the cardinality of the

set is five.
I have five inversions,

OK, between the two lists.
OK, so let's just check some

properties of this potential
function.

The first one is notice that
phi of L_i is greater than or

equal to zero for all i.
The number of inversions might

be zero, but is never less than
zero.

OK, it's always at least zero.
So, that's one of the

properties that we normally have
we are dealing with potential

functions.
And, the other thing is,

well, what about phi of L0?
Is that equal to zero?

Well, it depends upon what list
they start with.

OK, so what's the initial
ordering?

So, it's zero if they start
with the same list.

Then there are no inversions.
But, they might start with

different lists.
We'll talk about different

lists later on,
but let's say for now that it's

zero because they start with the
same list.

That seems like a fair
comparison.

OK, so we have this potential
function now that's counting up,

how different are these two
lists?

Intuitively,
we're going to do is the more

differences there are in the
list, the more we are going to

be able to have more stored up
work than we can pay for it.

That's the basic idea.
So, the more that opt changes

the list, so it's not the same
as ours, in some sense the more

we are going to be in a position
as MTF to take advantage of that

difference in delivering up work
for us to do.

And we'll see how that plays
out.

So, let's first also make
another observation.

So, how much does phi change
from one transpose?

How much does phi change from
one transpose?

So, basically that's asking,
if you do a transpose,

what happens to the number of
inversions?

So, what happens when a
transposing is done?

What's going to happen to phi?
What's going to happen to the

number of inversions?
So, if I change,

it is less than n minus one,
yes, if n is sufficiently

large, yes.
OK, if I change,

so you can think about it here.
Suppose I switch two of these

elements here.
How much are things going to

change?
Yeah, it's basically one or

minus one, OK,
because a transpose creates or

destroys one inversion.
So, if you think about it,

what if I change,
for example,

C and A, the relationship of C
and A to everything else in the

list is going to stay the same.
The only thing,

possibly, that happens is that
if they are in the same order

when I transpose them,
I've created an inversion.

Or, if they were in the wrong
order when I transpose them,

now they're in the right order.
So therefore,

the change to the potential
function is going to be plus or

minus two because we're counting
twice the number of inversions.

OK, any questions about that?
So, transposes don't change the

potential very much,
just by one.

It either goes up by two or
down by two, just by one

inversion.
So now, let's take a look at

how these two algorithms
operate.

OK, so what happens when op i
accesses x in the two lists?

What's going to be going on?
To do that, let's define the

following sets.

Why do I keep doing that?

OK, so we're going to look at
the, when we access x,

we are going to look at the two
lists, and see what the

relationship is,
so, based on things that come

before and after.
So, I think a picture is very

helpful to understand what's
going on here.

OK, so let's let,
so here's L_i minus one,

and we have our list,
which I'll draw like this.

And somewhere in there,
we have x.

OK, and then we have L_i minus
one star, which is opt's list,

OK, and he's got x somewhere
else, or she.

OK, and so, what is this set?
This is the set of Y that come

before x.
So, that basically sets A and

B.
OK, those things that come

before x in both.
And, some of them,

the A's come before it in x,
but come after it in,

come before it in A,
but come after it in B.

OK, and similarly down here,
what's this set?

That's A union C,
good.

And this one?
Duh.

Yeah, it better be C union D
because I've got A union B over

there, and I've got x.
So that better be everything

else.
OK, and here is B union D.

OK, so those are the four sets
that we're going to care about.

We're actually mostly going to
care about these two sets.

OK, and we also know something
about the r here.

The position of x is going to
be the rank in L_i minus one of

x.
And here, this is our star.

It's just to the rank in L_i
minus one star of x.

So, we know what these ranks
are.

And what we're going to be
interested in is,

in fact, characterizing the
rank in terms of the sets.

OK, so what's the position of
this?

Well, the rank,
we have that r is equal to the

size of A.
What's the size of B plus one?

OK, and r star is equal to the
size of A plus the size of C

plus one.
So, let's take a look at what

happens when these two
algorithms do their thing.

So, when the access to x
occurs, we move x to the front

of the list.
OK, it goes right up to the

front.
So, how many inversions are

created and destroyed?
So, how many are created by

this?
That's probably a,

how many inversions are
created?

How many inversions are
created?

So, we move x to the front.
So what we are concerned about

is that anything that was in one
of these sets that came,

where it's going to change in
order versus down here.

So, if I look in B,
well, let's take a look at A.

OK, so A, those are the things
that are in the same order in

both.
So, everything that's in A,

when I move x to the front,
each thing in A is going to

count for one more inversion.
Does everybody see that?

So, I create a cardinality of A
inversions.

And, we are going to destroy,
well, everything in B came

before x in this list,
and after x in this.

But after we move x,
they're in the right order.

So, I'm going to destroy B
inversions, cardinality of B

inversions.
OK, so that's what happens we

operate with move to front.
We destroy.

We create A inversions and
destroy B inversions,

OK, by doing this movement.
OK, now, let's take a look at

what opt does.
So, each transpose,

we don't know what opt does.
He might move x this way or

that way.
We don't know.

But each transpose,
I opt, well,

we're going to be interested in
how many inversions it creates,

and we already argued that it's
going to create,

at most, one inversion per
transpose.

So, he can go and create more
inversions, OK?

So, let me write it over here.
Thus --

-- the change in potential is
going to be, at most,

twice, A minus B plus t_i.
OK, so t_i, remember,

was the number of transposes
that opt does on the i'th step

for the i'th operation.
OK, so we're going to create

the change in potential is,
at most, twice this function.

So, we are now going to look to
see how we use this fact,

and these two facts,
this fact and this fact,

OK, to show that opt can't be
much better than MTF.

OK, good.
The way we are going to do that

is look at the amortized cost of
the I'th operation.

OK, what's MTF's amortized
cost?

OK, and then we'll make the
argument, which is the one you

always make that the amortized
cost upper bound the true costs,

OK?
But the amortized cost is going

to be easier to calculate.
OK, so amortized cost is just C

hat, actually,
let me make sure I have lots of

room here on the right,
c_i hat, which is equal to the

true cost plus the change in
potential.

OK, that's just the definition
of amortized cost when given

potential functions,
OK?

So, what is the cost of
operation i, OK,

in this context here?
OK, we accessed x there.

What's the cost of operation i?
Two times the rank of x,

which is 2r.
OK, so 2r, that part of it.

OK, well, we have an upper
bound on the change in

potential.
That's this.

OK, so that's two times the
cardinality of A minus

cardinality of B plus t_i.
OK, everybody with me?

Yeah?
OK, I see lots of nods.

That's good.
OK, that's equal to 2r plus two

of size of A minus,
OK, I want to plug in for B,

and it turns out very nicely.
I have an equation involving A,

B, and r.
So, I get rid of the variable

size of B by just plugging that
in.

OK, and so what do I plug in
here?

What's B equal to?
Yeah, r minus size of A minus

one.
I wrote it the other way.

OK, and then plus t_i.
OK, and this is since r is A

plus B plus one.
OK, everybody with me still?

I'm just doing algebra.
We've got to make sure we do

the algebra right.
OK, so that's equal to,

let's just multiply all this
out now and get 2r plus,

I have 2A here minus A.
So, that's 4A.

And then, two times minus r is
minus 2r.

Two times minus one is minus
two.

Oh, but it's minus-minus two,
so it's plus two.

OK, and then I have 2t_i.
So, that's just algebra.

OK, so that's not bad.
We've just got rid of another

variable.
What variable did we get rid

of?
r.

It didn't matter what the rank
was as long as I knew what the

number of inversions was here.
OK, so that's now equal to 4A

plus two plus 2t_i.
And, that's less than or equal

to, I claim, four times r star
plus t_i using our other fact.

Since r star is equal to the
size of A plus the size of C,

plus one, then that's greater
than or equal to the size of A

plus one.
OK, if I look at this,

I'm basically looking at A.
The fact that A,

what did I do here?
If r star is greater than or

equal to A plus one,
right, so therefore,

A plus one, good.
Yeah, so this is basically less

than or equal to 4A plus four,
which is four times A plus one.

I probably should have put in
another algebra step here,

OK, because if I can't verify
it like this,

then I get nervous.
This is basically,

at most, 4A plus four.
That's four times A plus one,

and A plus one is less than or
equal to r star.

And then, 2t_i is,
at most, 4TI.

So, I've got this.
Does everybody see where that

came from?
But what is r star plus t_i?

What is r star plus t_i?
What is it?

It's c_i star.
That's just c_i star.

So, the amortized cost of i'th
operation is,

at most, four times opt's cost.
OK, that's pretty remarkable.

OK, so amortized cost of the
i'th operation is just four

times opt's cost.
Now, of course,

we have to now go through and
analyze the total cost.

But this is now the routine way
that we analyze things with a

potential function.
So, the costs of MTF of S is

just the summation of the
individual costs,

OK, by definition.
And that is just the sum,

i equals one,
to S of the amortized cost

plus, minus the change in
potential.

OK, did I do this right?
No, I put the parentheses in

the wrong place.
Now I've got it right.

Good.
I just missed a parenthesis.

OK, so this is,
so in the past what I did was I

expressed the amortized cost as
being equal to c_i plus the

change in potential.
I'm just throwing these two

terms over to the other side and
saying, what's the true cost in

terms of the amortized cost?
OK, so I get c hat of i plus

phi sub L_i minus one minus phi
of L_i, OK, by making that

substitution.
OK, that's less than or equal

to since this is linear.
Well, I know what the sum of

the amortized cost is.
It's, at most,

4c_i star.
So, the sum of them is,

at most, to that sum,
I equals one to S of 4c_i star.

And then, as happens in all
these things,

you get a telescope with these
terms.

Every term is added in once and
subtracted out once,

except for the ones at the
limit.

So, I get plus phi of L_0 minus
phi of L sub cardinality of S.

And now, this term is zero.
And this term is greater than

or equal to zero.
OK, so therefore this whole

thing is less than or equal to,
well, what's that?

That's just four times opt's
cost.

And so, we're four competitive.
OK, this is amazing,

I think.
It's not that hard,

OK, but it's quite amazing that
just by doing a simple

heuristic, you're nearly as good
as any omniscient algorithm

could possibly be.
OK, you're nearly as good.

And, in fact,
in practice,

this is a great heuristic.
So, if ever you have things

like a hash table that you're
actually seeing by chaining,

OK, often it's the case that if
when you access the elements,

you're just bringing them up to
the front of the list if it's an

unsorted list that you've put
them into, just bring them up to

the front.
You can easily save 30 to 40%

in run time for the accessing to
the hash table because you will

be much more likely to find the
elements inside.

Of course, it depends on the
distribution and so forth,

for empirical matters,
but the point is that you are

not going to be too far off from
the ordering that an optimal

algorithm would do,
optimal off-line algorithm:

I mean, amazing.
OK: optimal off-line.

Now, it turns out that in the
reading that we assigned,

so, we assigned you Sleator and
Tarjan's original paper.

In that reading,
they actually have a slightly

different model where they count
transposes that move in excess

to element x towards the front
of the list as free.

OK, so, and this basically
models, so here's the idea is if

I actually have a linked list,
and when I chase down,

once I find x,
I can actually move x up to the

front with just a constant
number of pointer operations to

splice it out and put it up to
the front.

I don't actually have to
transpose all way back down.

OK, so that's kind of the model
that they use,

which is a more realistic
model.

OK, I presented this argument
because it's a little bit

simpler.
OK, and the model is a little

bit simpler.
But in our model,

they have, when you access
something, you want to bring it

up to the front,
or anything that you happen to

go across during that time,
you could bring up to the front

essentially for free.
This model is the splicing in,

splicing x in and out of L in
constant time.

Then, MTF is,
it turns out,

too competitive.
It's within a factor of two of

optimal, OK, if you use that.
And that's actually a good

exercise to work through.
You could also go read about it

in the reading to understand
this better, to look to see

where you would use those
things.

You have to have another term
representing the number of,

quote, "free" transposes.
But it turns out that all the

math works out pretty much the
same.

OK, let's see,
another thing I promised you

is, what if, to look at the
case, what if they don't start

with the same lists?
OK, what if the two lists are

different when they start?
Then, the potential function at

the beginning might be as big as
what?

How big are the potential
function start out as if the

lists are different?
So, suppose we're starting out,

you have a list,
and opt says,

OK, I'm going to start out by
ordering my list according to

the sequence that I want to use,
OK, and MTF orders it according

to the sequence it must use.
What list is opt going to start

out with as an adversary?
Yeah, it's going to pick the

reverse of what ever MTF starts
out with, right,

because then,
if he picks the reverse,

what's the number of
inversions?

It's how many inversions in a
reverse ordered list?

Yeah, n choose two,
OK.

Is it n choose two,
or n minus one choose two?

n minus one choose two,
OK, inversions that you get

because it's basically a
triangular number when you add

them up.
But in any case,

it's order n^2,
worst case.

So, what does that do to our
analysis here?

It says that the cost of MTF of
S is going to be,

well, this is no longer zero.
This is now n^2.

OK, so we get that costs of MTF
of S is, at most,

four times opt's thing plus
order n^2, OK?

And, if we look at the
definition, did we erase it

already?
OK, this is still for

competitive, OK,
since n^2 is constant as the

size of S goes to infinity.
This is, once again,

sort of your notion of,
what does it mean to be a

constant?
OK, so as the size of the list

gets bigger, all we're doing is
accessing whatever that number,

n, is of elements.
That number doesn't grow with

the problem size,
OK, even if it starts out as

some variable number,
n.

OK, it doesn't grow with the
problem size.

We still end up being
competitive.

This is just the k that was in
that definition of

competitiveness.
OK, any questions?

Yeah?
Well, so you could change the

cost model a little bit.
Yeah.

And that's a good one to work
out.

But if you say the cost of
transposing, so,

the cost of transposing is
probably moving two pointers,

approximately.
No, one, three pointers.

So, suppose that the cost of,
wow, that's a good exercise,

OK?
Suppose the cost was three

times to do a transpose,
was three times the cost of

doing an access,
of following a pointer.

OK, how would that change the
number here?

OK, good exercise,
great exercise.

OK, hmm, good final question.
OK, yes, it will affect the

constant here just as when we do
the free transpose,

when we move things towards the
front, that we consider those as

free, OK.
Those operations end up

reducing the constant as well.
OK, but the point is that this

constant is independent of the
constant having to do with the

number of elements in the list.
So that's a different constant.

So, this is a constant.
OK, and so as with a lot of

these things,
there's two things.

One is, there's the theory.
So, theory here backs up

practice.
OK, those practitioners knew

what they were doing,
OK, without knowing what they

were doing.
OK, so that's really good.

OK, and we have a deeper
understanding that's led to,

as I say, many algorithms for
things like, the important ones

are like paging.
So, what's the comment page

replacement policy that people
study, people have at most

operating systems?
Who's done 6.033 or something?

Yeah, it's Least Recently Used,
LRU.

People have heard of that,
OK.

So, you can analyze LRU
competitive, and show that LRU

is actually competitive with
optimal page replacement under

certain assumptions.
OK, and there are also other

things.
Like, people do random

replacement algorithms,
and there are a whole bunch of

other kinds of things that can
be analyzed with the competitive

analysis framework.
OK, so it's very cool stuff.

And, we are going to see more
in recitation on Friday,

see a couple of other really
good problems that are maybe a

little bit easier than this one,
OK, definitely easier than this

one.
OK, they give you hopefully

some more intuition about
competitive analysis.

I also want to warn you about
next week's problem set.

So, next week's problem set has
a programming assignment on it.

OK, and the programming
assignment is mandatory,

meaning, well,
all the problem sets are

mandatory as you know,
but if you decide not to do a

problem there's a little bit of
a penalty and then the penalties

scale dramatically as you stop
doing problem sets.

But this one is
mandatory-mandatory.

OK, you don't pass the class.
You'll get an incomplete if you

do not do this programming
assignment.

Now, I know that some people
are less practiced with

programming.
And so, what I encourage you to

do over the weekend is spent a
few minutes and work on your

programming skills if you're not
up to snuff in programming.

It's not going to be a long
assignment, but if you don't

know how to read a file and
write out a file,

and be able to write a dozen
lines of code,

OK, if you are weak on that,
this weekend would be a good

idea to practice reading in a
text file.

It's going to be a text file.
Read it in a text file,

decent manipulations,
write out a text file,

OK?
So, I don't want people to get

caught with this being mandatory
and that not have time to finish

it because they are busy trying
to learn how to program in short

order.
I know some people take this

course without quite getting all
the programming prerequisites.

Here's where you need it.
Question?

No language limitations.
Pick your language.

The answer will be written in,
I think, Java,

and Eric has graciously
volunteered to use Python for

his solution to this problem.
We'll see whether he lives up

to that promise.
You did already?

OK, and George wrote the Java
solution.

And so, C is fine.
Matlab is fine.

OK, what else is fine?
Anything is fine.

Scheme is fine.
Scheme is fine.

Scheme is great.
OK, so any such things will be

just fine.
So, we don't care what language

you program in,
but you will have to do

programming to solve this
problem.

OK, so thanks very much.
See you next week.