Transcript


00:19
okay but last time we started to talk
00:23
about amortized complexity and today
00:27
what we'll be doing is we'll pick up
00:29
with the example we started last time on
00:31
translating an arithmetic statement into
00:33
a collection of simpler simplest
00:36
statements and then we look at one
00:38
additional example a binary counter for
00:41
amortized complexity now before I
00:44
continue with the discussion of
00:46
amortized complexity are there any
00:47
questions you have pending from our last
00:50
meeting all right so last time we saw
01:03
that there were three ways two or three
01:07
commonly used ways to determine the
01:09
amortized complexity of tasks the first
01:12
of these was the aggregate method and
01:14
the example we looked at namely
01:17
translating a north-america statement
01:19
for that one we saw how to get the
01:22
amortized complexity of process next
01:23
symbol using the aggregate method
01:26
oh I mentioned the accounting method we
01:29
didn't see how to use it we look at that
01:31
now and we also take a look at the
01:33
potential function method alright so
01:38
first let's have a quick review of what
01:40
the potential function is this is a
01:43
slide from our last lecture so basically
01:45
a potential function is a function which
01:49
keeps track of the cumulative excess
01:52
that you've been charging operations
01:54
beginning at time zero so P I gives you
01:59
the excess charge made to the first I
02:04
operation so we say this is the
02:05
potential after the eyuth operation in
02:08
your operation sequence so the potential
02:12
after the eyuth operation has a
02:13
relationship with the potential after
02:15
the I minus first operation which again
02:18
is the potential before the eyuth
02:20
operation so and that relationship is
02:26
the potential after the operation is the
02:29
potential before
02:31
plus the amount by which you overcharge
02:33
the i/os operation okay so the balance
02:37
in your bank goes up by the excess of
02:40
what you put into the bank - what you
02:43
take out then we did this telescoping
02:50
sum we move the P I minus one to this
02:52
side in some of some lower all of the
02:54
operations in our sequence and we saw
03:00
that on the left side all terms except
03:02
for p0 and PN would cancel out okay so
03:06
we ended up with this equality and
03:08
basically what this says is the
03:11
difference between the potential when
03:13
you're done and the potential when you
03:14
started is the cumulative sum of the
03:17
excesses and if you have a proper
03:23
amortization scheme so if you assigned
03:26
legally acceptable amortized costs then
03:29
your potential should increase or at
03:33
least it should not decrease so the
03:34
potential at the end should at least be
03:36
GU the potential when you start now in
03:39
most applications of the potential of
03:44
potential functions we start with p0
03:47
equal to zero so essentially then you
03:51
know that you have a proper amortization
03:52
scheme if PN is non-negative okay let's
04:02
go through a numeric example using the
04:07
arithmatic statement
04:12
all right so the actual cost of
04:16
processing the a is a 1 you just push it
04:19
onto the stack the actual cost of
04:22
processing the equal is a 1 and for an X
04:25
it's 1 for a plus it's 1 left
04:28
parenthesis and other left parenthesis
04:30
and a a plus a B okay so each of the
04:35
first several invitations to process
04:37
next symbol has an actual cost of 1 all
04:39
we do is we push something on the stack
04:41
for actual cost as in our last lecture
04:45
we'll be using the number of pops and
04:47
pushes now when you see the right
04:51
parenthesis okay
04:53
well then we're going to pop the be the
04:55
plus the a in the left parenthesis okay
04:57
so that's one two three four pops and
05:00
then we'll do a push we'll put a new
05:02
symbol on like a z1 so the actual cost
05:06
of processing that right parenthesis is
05:08
5 when you see the times you just push
05:12
it onto the stack so that has a cost of
05:13
1 same thing for the see the plus and
05:16
the D now when I see that right
05:20
parenthesis I'm going to pop this be the
05:23
plus the see the times I got a Z sitting
05:26
out there z1 representing this and this
05:30
left parenthesis okay so I'll be popping
05:32
1 2 3 4
05:34
the z 1 5 and that left parenthesis 6
05:36
and then I'll push a z2 onto the stack
05:39
so that's a cost of 7 all right then I
05:43
see a plus actually what cost this one
05:45
see a why the actual cost is 1 when you
05:48
see a semicolon we're going to flush the
05:50
stack so I popped the wide the Plus this
05:54
whole thing here is represented by Z 2
05:56
then this plus the X the equal in the 8
05:59
okay so the number of pops 1 2 3 4 that
06:04
whole thing 4 5 6 and 7
06:06
okay and there's no push so that has an
06:10
actual cost of 7 okay all right for
06:15
amortized costs let's suppose I guess
06:17
okay the amortized cost us two and in
06:20
fact we computed last time using the
06:22
aggregate method that 2 works
06:25
all right so and we do charge each of
06:28
these operations - now if this is a
06:40
correct amortization scheme then my
06:43
potential should be non-negative
06:47
so let me compute the potential so I'm
06:51
starting with a potential of zero okay
06:53
so here I have an overcharge I'm
06:58
charging the operation to with the
06:59
actual cost is 1 so the credit in the
07:02
bank becomes 1 so my potential is 1 okay
07:04
the accumulation of all of the over
07:06
charges okay then here again my bank
07:11
balance goes up by one I'm overcharging
07:13
by one so the potential becomes two then
07:15
the potential becomes three four five
07:18
six seven okay so so far I'm always
07:27
overcharging the operations okay and
07:31
then when I see that right parenthesis I
07:33
have an undercharge okay I'm charging it
07:36
to what it cost me five so now my
07:38
potential would drop okay so now my
07:41
potential drops to 6 okay then again I
07:44
have an overcharge so it starts building
07:46
again okay right then I see the right
07:52
parenthesis and again the actual cost
07:56
exceeds the amount you're charging it's
07:58
your potential again drop okay and this
08:01
time your potential will drop by five
08:03
okay then your potential increases again
08:07
until you see the next fellow who's
08:09
being charged less than it actually cost
08:11
you and that's the semicolon was charged
08:13
five units less than it actually cost
08:15
and so your potential will drop by five
08:17
and now become two I said the purpose of
08:21
the potential function is to keep track
08:23
of the cumulative over charges and if
08:26
you have an undercharge then it's a
08:27
subtract over charge it adds to it now
08:31
you have a correct amortization scheme
08:33
if your potential function is always
08:34
non-negative
08:40
all right now in this particular example
08:45
we might get the feeling that if you
08:50
look at this potential function value it
08:53
agrees with the number of items on the
08:55
stack okay when the potential function
08:57
is 1 only A's on the stack when it's 2
08:59
both the a and the e Koller on the stack
09:01
when it's 3 the a equal and exit on the
09:03
stack okay so at least in this
09:07
particular example the value of the
09:10
potential function is the stack size
09:13
except at the end when the stack size is
09:15
empty and my potential function has a
09:17
value of 2 that's something you can
09:22
prove more formally that if you start if
09:24
you use an amortized cost of 2 then your
09:27
potential independent of the example
09:29
you're dealing with will be stack size
09:32
except at the end when it would be 2 all
09:38
right let's turn to the accounting
09:40
method
09:42
all right the general strategy in the
09:44
accounting method is to guess okay you
09:49
guess an amortized cost and then you
09:54
show that your potential function is
09:57
non-negative or your potential remains
09:59
non-negative and because you'd like to
10:06
guess as small an amortized cost as
10:09
possible for which you can show that the
10:11
potential is non-negative so the the
10:19
challenge in using this method of course
10:21
is having a good crystal ball to look
10:23
into so that you can guess something for
10:26
which you can prove the potential is
10:27
non-negative
10:32
let's take a look an example here and
10:35
that's our translation sach translation
10:38
example okay so to use the accounting
10:42
method I have to start by guessing and
10:45
since we've already done an analysis
10:47
using the aggregate method it's not hard
10:49
to get something that's going to work
10:50
but in a real application of the scheme
10:53
you would use only one of the three
10:55
methods so you wouldn't already know
10:57
which guess is going to work and
11:00
typically you may try several guesses
11:03
the first several don't work and then
11:05
you find one that works and once you
11:08
find something that works you might try
11:09
something smaller than that to see if
11:10
that works
11:11
okay so it's kind of a guessing game and
11:14
then seeing what you can prove alright
11:19
so here we know that 2 is going to work
11:21
and so I'm gonna start by guessing 2 to
11:23
illustrate the method alright so i'm
11:31
going to start with p 0 equal to 0 and
11:33
show that the potential is non-negative
11:36
when you guess an amortized cost of 2
11:42
now in order to show this we will first
11:48
prove what I said in the previous slide
11:51
that the potential after the eyuth
11:55
operation is at least equal to the
11:57
number of elements on the stack after
12:00
the @ symbol is processed in fact we can
12:03
show that it's exactly equal to the
12:05
number of elements on the stack except
12:07
at the end when the potential is 2 and
12:09
your number of items is 0 that's where
12:12
that greater than equal comes to because
12:14
in the end you become bigger ok all
12:17
right so you can prove that thing here
12:19
certainly it's true when you start and
12:22
then you use mathematical induction to
12:23
show if it's true before the eyuth
12:25
operation is going to be true after the
12:27
operation and that proof actually is
12:31
going to be embedded in this same
12:34
example when we look at the potential
12:35
function method so I'm not going to go
12:37
through it here ok so so we have to show
12:43
this and as we said earlier at least on
12:46
this example
12:46
we can verify it's true but you can
12:48
prove by induction that this in fact is
12:51
the case that the potential is at least
12:54
equal to the number of symbols on the
12:55
stack so once you have shown that the
12:59
number of symbols or elements on the
13:02
stack can never be negative and so then
13:05
you've shown that the potential is
13:06
non-negative and so your guess of two is
13:09
a correct guess all right so the trick
13:15
here is to guess the right thing and
13:17
then show that the potential is
13:19
non-negative let's look at the potential
13:29
method here the strategy is instead of
13:34
guessing the amortized cost we're going
13:36
to guess a potential function a
13:41
potential function has to be
13:44
non-negative to be a valid potential
13:45
function so any non-negative function
13:48
could be guessed and depending upon the
13:50
function you start with you will then be
13:53
able to establish different amortized
13:54
costs all right so you guess a potential
14:00
function
14:00
it's got to be non-negative and then
14:06
we'll use the definition of potential
14:07
function which says that the change in
14:10
potential okay so the potential after
14:14
the i/o operation minus the potential
14:16
before the I minus first before the is
14:18
okay so the change in potential is the
14:23
amortized cost of the I operation minus
14:25
the actual cost of the i/o operation see
14:29
a potential goes up by the amount of
14:31
overcharge for the i/o operation so I'm
14:35
going to use this which they said is the
14:37
definition of the potential function and
14:40
then from here I can get an equation for
14:43
amortized cost which says amortized cost
14:45
is the actual cost plus the change in
14:48
potential function so if I know the
14:52
actual cost of the operation and if
14:55
you've already guessed a potential
14:57
function then you can compute Delta P
15:00
okay so if you know this and you can
15:04
compute this from the function you've
15:06
guessed you add the two together you get
15:08
the amortized constant so to use this
15:14
method you have to still do some
15:16
guessing you could have a good crystal
15:18
ball look into it guess a good potential
15:20
function the only requirement is these
15:24
functions have to be non-negative
15:26
once you've guessed that we use this
15:29
equation so you have to know the actual
15:31
cost of the operation and then add to it
15:34
the change in potential which you
15:36
compute by looking at your potential
15:38
function let's see how that works for
15:43
our stack example all right guessing a
15:52
potential function here isn't hard
15:54
because we've already seen an example
15:56
and I've said you could prove this works
15:59
okay so the potential function we're
16:01
going to guess is that the potential
16:04
after the i/o operation is the number of
16:06
symbols on the stack
16:15
except at the end where my guess is the
16:18
potential is - all right so from this
16:32
guess we can verify first that it's a
16:35
valid potential function okay that means
16:37
that P P I minus p0 must be at least
16:41
zero so p 0 is 0 and then P I is going
16:48
to be at least zeros the number of
16:50
things on the stack right so satisfies
16:53
the minimal requirement it's
16:55
non-negative and then we're going to
16:57
plug in our equation to figure out the
17:00
amortized cost
17:04
all right so we'll do this in 3 cases
17:07
looking at the three different
17:09
possibilities for what happens in
17:11
process next symbol the simplest is when
17:13
you are not processing a right
17:15
parenthesis or a semicolon and that time
17:17
we just push something push that symbol
17:20
under the stack so at this time the
17:24
process next symbols actual cost is 1
17:26
you just do a push and so when you push
17:31
something on the stack the number of
17:33
items on the stack goes up by one which
17:35
means the potential goes up by one
17:37
so the number of elements goes up by one
17:40
because you did a push you didn't take
17:41
anything off and from the definition of
17:44
a potential function the change in
17:46
potential is 1 and then we have an
17:53
equation which says amortize cost is
17:55
actual cost plus change in potential
17:57
actual cost is 1 change in potential is
18:00
1 and so the amortized cost is 2
18:13
okay
18:19
any questions right so I guess the
18:31
question is both the accounting method
18:34
and potential function method the
18:38
quality of what you get from there is
18:40
depends a lot on your guess and that's
18:42
very true can you verify that you've got
18:45
the best guess really all you can do is
18:50
once you get I will suppose you look at
18:53
the accounting method okay so you guess
18:55
some costs and then you're able to push
18:58
through the proof that the potential is
18:59
non-negative well then you may try a
19:01
smaller guess to see if you can push
19:04
through a proof with the smaller guess
19:05
and that's really all you can do I mean
19:07
there's really no way to or let me put
19:11
it different it's very hard to show that
19:14
you can't do better and the same is true
19:19
here you try some potential function see
19:21
what you can prove yeah once you have
19:37
the amortized cost okay we can then add
19:39
up amortized cost to figure out the cost
19:41
of the whole sequence okay if you look
19:43
at actual costs right and then if you
19:48
look at this example itself okay so the
19:52
actual cost we know for a process next
19:55
symbol is let's say one when you're
20:00
processing something other than a right
20:04
parenthesis or semicolon but we process
20:06
a right parenthesis the actual cost
20:10
could be ending and when you process
20:14
semicolon the actual cost could be n so
20:16
if you try to add up using that then
20:18
your complexity becomes n times the
20:20
number of right parenthesis which could
20:21
be half as many symbols as in the whole
20:23
things you end up with n square using
20:26
this scheme we're going to be able to
20:28
show that even though
20:30
Anshul cost of processing a right
20:33
parenthesis could be as high as order of
20:34
n the amortized cost is only two and so
20:38
when we add up across all of process
20:40
next symbols your total cost becomes at
20:42
most two n so the amortized cost enables
20:47
us to establish better bounds on the
20:50
complexity of sequences of operations
20:53
then you can get using the worst case
20:57
analysis scheme and that's why we do it
21:11
well we're trying it question is are
21:14
there any restrictions on the amortized
21:16
cost independent of the method you are
21:19
using the objective is to arrive at the
21:23
smallest amortized cost for which the
21:25
potential is non-negative that's why you
21:35
keep guessing until you come up with the
21:37
smallest amortized cost now typically
21:40
what happens is you know when we come to
21:42
looking at the data structures where
21:43
these methods are really very important
21:46
or useful what we'll be trying to show
21:50
is that even though the worst-case cost
21:54
over insert operation is order n the
21:57
amortized cost is order of log N and
21:59
that's really all we'll be trying to
22:01
show and so the objective would be to
22:03
come up with a potential function that
22:05
allows us to prove log n typically in
22:09
that kind of situation it doesn't matter
22:10
whether it's log n or to log N or 0.5
22:13
log N or something we just want to show
22:15
an order log n type thing okay all right
22:23
so we so we've seen that the amortized
22:26
cost is two if you're not processing a
22:29
right parenthesis or a semicolon and
22:32
that's with this guess for potential
22:34
function
22:37
right now let's look at the second case
22:39
you're processing a right parenthesis
22:41
okay so the actual cost of processing
22:46
next symbol is the number of pops that
22:49
you do plus one because you do a push
22:52
okay so as the number of pops plus one
22:59
so the change in your potential
23:03
potential is how many people you have on
23:05
the stack so the potential changes by
23:09
the number you take off plus what you
23:12
put back on okay so you do this many
23:14
pops and one push so your potential
23:18
decreases by this amount okay so the
23:21
potential change is actually the
23:22
negative of this okay all right so the
23:28
potential change is the negative of the
23:31
decrease because we're keeping track of
23:32
cumulative increases okay so the
23:34
potential change is one minus the number
23:36
of pops the actual cost is number of
23:39
pops plus one the amortize is the sum of
23:42
the actual plus potential change so
23:48
that's the actual that's the potential
23:51
change the number of pops cancels out
23:53
and you get an amortized of two
24:11
and we will see several other examples
24:14
where the unknown terms conveniently
24:18
cancel out so that you end up with an
24:20
amortized cost that doesn't depend upon
24:23
the length of the sequence of tasks all
24:34
right the last case is you're processing
24:36
a semicolon so the actual cost is the
24:39
number of pops and the number of pops is
24:42
the potential after the previous
24:44
operation because the potential is
24:46
defined as the number of items on the
24:47
stack the change in potential the number
24:58
of items on the stack goes down by that
25:00
because you flush everything off so the
25:12
change in potential is the potential at
25:15
the end which we define to be - okay we
25:18
had that exception it's - at the end
25:20
okay subtract the number of items that
25:26
you took off so that's PN minus 1 is the
25:32
number of items okay all right so the
25:35
amortized cost is the actual cost which
25:38
is the number of pops unless PN minus 1
25:42
the potential change is the potential at
25:44
the end which is 2 and the potential yes
25:46
before the end which is PN minus 1 okay
25:49
so actual cost is PN minus 1 potential
25:52
changes to minus PN minus 1 and the peas
25:55
cancel out and you again get an
25:57
amortized cost of 2
26:06
all right so the potential method you
26:09
guess a potential function it's got to
26:11
be a non-negative function then you have
26:14
to know the actual cost of operations
26:16
add up the actual constants and add the
26:19
potential change that gives you the
26:21
amortized cost now one of the things you
26:26
might have noticed here is if I had
26:29
defined my potential function without
26:33
that exception potential function that
26:36
the potential is number of items on the
26:38
stack independent of whether it's the PN
26:43
or any of the other piece okay so the
26:45
only thing that would change is this
26:47
analysis here this is the only thing
26:50
that uses PN okay so this would change
26:54
and what we would have here is Delta P
26:57
would change because now PN would be
27:00
zero after the semicolon is processed
27:04
there are no items on the stack so this
27:06
is zero okay and the potential before is
27:10
that so this becomes minus of PN minus 1
27:12
and then when you plug it in here you
27:15
get amortized cost to zero okay so with
27:21
a guess for potential function being
27:24
potential as number of items on the
27:26
stack the first two cases are unchanged
27:28
we still get to as the amortized cost
27:30
for those two cases but now we get an
27:33
amortized cost here that is zero okay so
27:36
we get a slightly better amortized cost
27:41
but both analyses are correct one
27:45
establishes two as the amortized cost of
27:47
every invocation of process next symbol
27:49
the other one said that it's two for
27:52
every invocation but it is zero when the
27:56
symbol you're processing is semicolon
28:03
when we do our data structure analyses
28:06
we'll see that it's that the accounting
28:11
method and the potential function method
28:13
a particularly useful relative to the
28:16
aggregate method because they allow us
28:18
to come up with different amortized
28:21
costs for different operations when you
28:23
use the aggregate method you you know
28:25
you just add up all the cost divided by
28:26
the numbers you end up with the same
28:28
amortized cost for every operation but
28:31
using these two it becomes possible to
28:34
say that the amortized cost of an insert
28:36
is log n that the amortized cost I would
28:38
delete is 1 for example so here we've
28:43
seen it in this particular example we've
28:45
got a different amortized cost for
28:46
processing a semicolon when I change the
28:49
definition of potential function we
28:52
could have done the same thing in the
28:53
case of the accounting method we could
28:57
have started off by guessing that the
28:59
amortized cost is 2 except when you
29:01
process a semicolon then it is 0 and
29:04
we'd be able to show that the potential
29:06
is non-negative okay so these two
29:09
schemes are very useful because they
29:13
also allow you to prove different
29:17
amortized costs for different operations
29:19
in a sequence alright so let's take a
29:23
look at another example then look at a
29:26
binary counter ok all right so we're
29:30
gonna look at a counter that has n bits
29:34
and the counter is going to start at 0
29:37
and you're going to change it so from 0
29:39
we'll go to 1 then 2 3 each time you
29:42
change the counter the cost of the
29:44
change is the number of bits that
29:46
changes so for example if your counter
29:50
is in this state when you add a 1 it's
29:52
going to go into that state and the
29:55
number of bits that changed with these 3
29:56
at the end the 0 became a one and those
29:58
two ones became a 0 so the cost of that
30:01
incremental 3
30:08
what we want to determine is what is the
30:14
cost of M increments starting at zero if
30:24
you use the worst case method well then
30:26
if you got n bits all n bits might
30:29
change in the worst case okay so your
30:32
worst case cost is n and that for
30:34
example happens when you go from this
30:37
state of the counter to that state if
30:39
it's a six bit counter all right so if
30:45
you have n bits an incremental cost you
30:49
n you make M increments so your cost is
30:51
order of MN okay simple analysis now
30:59
what we'll see is that if we use the
31:03
idea of amortized cost of any of these
31:06
three schemes the actual we can
31:10
establish a much better bound and that's
31:12
going to be that it's M instead of n
31:16
times m it doesn't depend upon how many
31:17
bits in the counter all right so let's
31:23
see how we're going to do it so first we
31:24
use the aggregate method that's it in
31:28
the aggregate method I say well I'm
31:30
doing M increments starting from this
31:31
state
31:32
somehow I'm going to figure out the
31:34
total cost of these as an aggregation
31:39
rather than saying each one is going to
31:41
cost me at most n and then I do n times
31:43
M okay so I say well every time you do
31:47
an increment this bit changes okay so
31:52
from 0 this will go to 1 and then when
31:55
the counter becomes 2 the 1 will become
31:56
a 0 when the counter becomes 3 the 0
31:58
will become a 1 and so on ok so every
32:01
time we do an increment that rightmost
32:02
bit changes so if we do M increments
32:05
there are going to be M changes to the
32:07
rightmost bit
32:11
now the bit next to that this fellow
32:14
here changes only half as fast as that
32:16
one so the number of increments of the
32:21
next bit is M over 2
32:28
the bit next to this one is going to
32:30
change any half as fast as that one so
32:34
that's going to go M over 4 times and
32:43
the bit next to that will go half as
32:45
fast as the one to its right so that's
32:47
going to go am over 8 times so I add up
32:51
all the changes M for the rightmost bit
32:54
M over 2 for the next one M over 4 for
32:56
the next one add them up and you get a
32:59
total that is smaller than 2 times M all
33:09
right so the total cost of M increments
33:11
is at most two times M now once you've
33:15
done this that's what we wanted there's
33:16
really no point going the next step in
33:18
telling me what the amortized cost of an
33:21
increment is but if the problem was tell
33:24
me the amortized cost well then you got
33:25
to go one more step and you take your
33:28
bound which is 2 M divided by the number
33:30
of operations M and I you say that the
33:33
amortized cost of an increment is 2
33:41
aren't any questions with that example
33:48
okay all right so in the binary counter
33:52
example as in the stack example the
33:54
aggregate method is doable in that it's
33:57
not too difficult to employ but again
34:01
when we get to real data structures will
34:04
find that the aggregate method is really
34:06
either very hard to use or if you try to
34:09
use it you would not get a good mount
34:13
alright so let's go to the accounting
34:15
method so here you have to start with a
34:20
guess
34:21
well guessing is easy when you know the
34:24
answer so you guess - and then you have
34:29
to show that the potential is going to
34:32
be will satisfy this property that pm-
34:35
p0s ran equal to zero all right so let's
34:46
look at the first increment okay so I'm
34:52
going to charge the first increment two
34:53
units but the first increment has an
34:58
actual cost of only one because that
34:59
rightmost bit that changes from zero to
35:01
one so I'm going to be left with this
35:03
one extra unit now typically when you're
35:10
using the accounting method the
35:11
challenge is figuring out some way of
35:13
keeping track of the excess charges in
35:16
the stack example we said the cumulative
35:20
excess is the number of items in the
35:22
stack and so with whatever example or
35:29
problem you're working with you need
35:30
some way of conveniently keeping track
35:32
of the excess and a technique that is
35:38
often used is called a credit system
35:40
where you find convenient spots to leave
35:44
the excess instead of just computing one
35:47
big number and saying the excesses now
35:49
five and then it becomes 10 and 20 you
35:51
have an accounting scheme where you
35:53
leave parts of it on different parts of
35:55
your of the instance that you're working
35:57
with and we'll see how that works here
35:59
okay all right
36:01
that one unit is going to be used to pay
36:03
for the change of the rightmost bit but
36:06
I'm going to be left with one additional
36:08
unit then I have to keep track of so
36:12
this additional unit is going to be kept
36:15
track of as a credit that's going to be
36:17
placed on the rightmost one or the only
36:19
one okay so okay so we start from this a
36:24
configuration okay I'm going to use a
36:28
credit system where I'm going to keep
36:29
credits on the bits of the counter and
36:31
the sum of the credits will be the total
36:34
amount of overcharge so far so it'll be
36:36
the potential value starting with a
36:38
potential of zero right so when I go
36:44
from this configuration to that one okay
36:46
I have a one unit of overcharge and
36:49
we'll keep that as a credit on that
36:52
rightmost one in fact as we will see the
36:57
credit scheme I'm going to use is going
37:00
to ensure that every bit that is a one
37:03
in my counter will have a credit of 1 on
37:05
it and then when it comes time to pay
37:10
for an operation to pay for an actual
37:12
cost I'm going to use up the credits on
37:15
these ones ok let's go through a few
37:19
iterations of this to feel a little
37:22
comfortable about this ok all right so I
37:24
start from here I'm going to do another
37:26
increment by 1 and the actual cost now
37:30
is going to be - okay this bit is going
37:34
to change and that bit is going to
37:35
change ok so I've got to figure out
37:38
there's an actual cost of 2 how do I pay
37:40
for the actual cost using some of the
37:45
amortized cost and some of my credits I
37:48
must always have enough from the
37:50
amortized and credits to pay for the
37:52
operation if you don't have enough from
37:55
the credits you have got from previous
37:57
operations plus the amortized cost of
37:59
this one then your potential becomes
38:01
negative so you got to pay for every
38:05
operation as it occurs from accumulated
38:07
credits and from the at the amortized
38:11
cost of the current one otherwise you
38:13
have an incorrect amortization scheme
38:15
okay alright so I'm going to go from
38:19
this state to that state because the
38:21
other thing I said was the way I'm going
38:23
to keep track of the potential value is
38:27
but placing a 1 on every bit that's one
38:30
so there got to be enough credits to
38:31
cover all my 1 bits okay alright so what
38:37
I will do is I've got an amortized cost
38:40
of 2 okay
38:42
now certainly I could have used all of
38:44
that to to pay for the actual cost but
38:47
then I have a real hard time keeping
38:49
track of credits and generalizing my
38:53
costing scheme ok so instead what I'm
38:56
going to do is and this is what I'm
38:59
going to do independent of which
39:01
iteration you run ok the two units of
39:06
amortized cost would always get used in
39:09
this fashion when you change when you do
39:13
an increment ok there's always one bit
39:17
that was previously a zero and becomes a
39:19
one okay all of the bits on the right
39:21
that are ones switched from one to zero
39:23
and then the right was zero switches
39:26
from zero to one okay so the cost of
39:30
switching that zero to one is going to
39:32
get paid from the amortized cost that
39:36
leave me with one unit of amortized cost
39:37
which I'll put as a credit on that zero
39:40
that changed to a one okay so one unit
39:44
is used to pay for the cost of switching
39:47
the leftmost
39:48
sorry the right was zero from zero to
39:50
one the other one unit is left as a
39:52
credit on that bit that became a 1
39:55
everybody tools right would have
39:57
switched from 1 to 0 and they're going
40:00
to get paid for by the credits and those
40:02
credits will drop to zero ok all right
40:06
so all the ones that got changed we get
40:10
paid for by the credits
40:12
the zero that got changed will get paid
40:15
for from the amortized cost the balance
40:17
of the amortized cost will remain as a
40:19
credit on that single zero that became a
40:21
1
40:25
all right so the second increment
40:28
there's enough credits in the system to
40:31
pay for and leave credits the way I
40:33
wanted let's go to the third increment
40:40
same thing the rightmost zero that gets
40:46
changed
40:48
okay the rightmost zero will get changed
40:49
from a zero to one so one unit of the
40:51
amortized cost goes to pay for that the
40:54
other one becomes a credit if there any
40:58
ones to the right of that they would
41:00
have changed but there aren't any ones
41:01
to the right of this okay so there
41:04
aren't any other fellows that you have
41:05
to pay for if you go to number four so
41:15
the rightmost zero is going to change
41:18
the actual cost of changing that is paid
41:21
for from the amortized cost of this
41:23
operation and then to leave a credit of
41:26
one on this fellow once it has changed I
41:29
use the other unit of the amortized cost
41:34
to the right of this fellow there's a
41:36
bunch of ones that got changed all of
41:38
those get paid for from the credits that
41:40
are sitting there all right so this
41:46
accounting scheme shows that from the
41:51
credits on the ones and the amortized
41:54
cost of the current operation we can
41:56
always pay for the actual cost of the
41:58
current operation so the potential is
42:07
the number of credits and the number of
42:12
credits can never be negative so your
42:15
potential is always non-negative and so
42:18
we have a proper accounting scheme or a
42:23
proper amortization scheme
42:28
all right any questions that
42:39
all right so the the idea of credits is
42:42
coming up with some convenient way of
42:44
keeping track of the excess charge you
42:47
have up to this point and by convenient
42:51
I mean it's got to be something that is
42:53
amenable to your being able to show that
42:55
you got enough credits in the system to
42:57
pay for the actual cost of each
42:59
operation in the case of the stack
43:04
example we kept track of the credits as
43:06
a single number number of items in the
43:08
stack but when you get to more involved
43:10
examples a single number it doesn't
43:12
really work you have to be able to place
43:15
credits at convenient spots so that you
43:17
can show that you can pay for the
43:19
operations alright let's look at the
43:24
potential method applied here again
43:27
starting point is guess a suitable
43:30
potential function and derive the
43:35
amortized cost using this formula okay
43:39
so guess the function and then plug it
43:43
in with that alright the potential
43:49
function is is the sum of the over
43:54
charges and from the example that we
43:57
just worked through we know that the sum
43:59
of the over charges or a good guess for
44:02
a function for that is the number of 1s
44:04
in the counter so having done that it's
44:10
easy to get a potential function that's
44:12
going to give us a good answer the
44:14
potential after the eyuth increment is
44:17
the number of ones in the counter so
44:20
when you start the potential is zero
44:22
since the number of ones is never
44:24
negative the potential is always
44:25
non-negative so at least it satisfies
44:28
the non-negative requirement for a
44:29
potential function all right so now we
44:35
have to arrive with the amortized cost
44:37
as actual plus potential change so to
44:41
figure out that I'm going to let Q be
44:44
the number of once at the right end of
44:46
the counter so for example in this case
44:48
I've got four ones at the right end
44:51
initially when you start Q is zero the
44:53
right end bit is a 0 whenever the
44:57
rightmost bit is a 0 Q is 0 Russ in the
45:04
actual cost of the is increment the
45:06
rightmost ones switched to 0 and then
45:09
then next to it you have a 0 that
45:11
switches to a 1 okay so the actual cost
45:15
is 1 plus the number of rightmost ones
45:19
now we need a formula for the change in
45:22
potential so the change in potential
45:26
these Q bits change from 1 to 0 so the
45:29
potential goes down by that amount
45:31
this fellow changes from 0 to 1 so the
45:33
potential goes up by 1 because of that
45:36
ok so the change in potential it goes up
45:40
by 1 because the rightmost 0 goes from 0
45:43
to 1 and it goes down by Q because all
45:46
of those ones become 0 that's the change
45:48
in the number of ones in the
45:50
representation so the potential change
45:53
is 1 minus Q the amortized cost is just
45:57
the sum of the actual plus potential
45:59
change so the actual is cost is 1 plus Q
46:05
potential changes 1 minus Q atom
46:08
together that hues cancel out
46:10
conveniently and you get two as the
46:12
amortized cost
46:30
all right questions about this example
46:38
all right so we start by guessing the
46:41
potential function okay in this case I'm
46:44
going to guess the potential is the
46:46
number of ones in the counter after the
46:48
operation so then I the first thing to
46:52
do is to make sure your function is a
46:53
non-negative function alright so make
46:56
sure it's not negative but not negative
46:58
I mean that TI is always going equal to
47:00
p0 and usually p 0 0 so it's
47:04
non-negative in the normal sense okay
47:06
all right now to get the actual cost
47:08
once you have the potential function so
47:10
get the amortized cost we need to use
47:12
this formula which says you've got to
47:14
know the actual cost you got to know the
47:15
potential change so I first derive the
47:19
actual cost the actual cost is 1 because
47:23
there's always a 0 that switches to 1
47:24
plus the number of ones at the right end
47:27
ok so the actual cost is 1 plus Q the
47:31
potential change potential is number of
47:33
1s in the counter so look at how many
47:36
ones became a 0 and how many zeros
47:37
became a 1 and that will tell me the
47:40
difference okay so for the potential
47:43
change there's 1 0 that becomes a 1 so
47:47
the potential goes up by 1 because of
47:49
that there are Q ones that become a 0
47:52
so the potential drops by Q because of
47:54
that because potential the number of
47:57
ones ok so the potential change is 1
47:59
minus Q so I know the actual cost 1 plus
48:04
Q I know the potential change 1 minus Q
48:07
I add the 2 and get the amortized cost
48:10
which is 2 ok
48:19
there are other questions are you
48:29
looking over here yes that's one minus q
48:33
all of that is just an example to show
48:37
you that here okay the change in
48:39
potential the potential here is one two
48:41
three four number ones the potential
48:44
here is one two okay so the potential
48:47
going from here to here is dropped by
48:48
two okay so what happened was this zero
48:52
became a one so you went up by one these
48:55
three ones became with zero so you
48:56
dropped by three so 1 minus 3 2 okay now
48:59
or negative 2 so the potential change is
49:02
minus 2 when you went from here to here
49:04
okay and and that's what we can reason
49:06
an abstract setting it's going to be 1
49:08
minus Q okay all right other questions
49:13
yeah from of course what can you
49:39
conclude now that we know that the
49:40
amortized cost of an incremental to what
49:43
I can conclude is that if you do 1,000
49:46
increments your cost will be mm okay
49:49
previously I as you said I know the best
49:52
is 1 and the worst is and if there are n
49:54
bits and if you did 1,000 increments all
49:58
you can say is the the cost is somewhere
50:00
between 1000 and 1000 times n now I can
50:03
tell you it's no more than 2,000 so I've
50:07
given you a better bound okay all right
50:12
other questions okay so we'll see you
50:16
Monday