Transcript


00:14
okay I'd like to welcome you all to the
00:17
first meeting of the advanced data
00:20
structures class my name is Suraj sunny
00:23
and I guess as you know we're gonna meet
00:25
about three times a week Monday
00:27
Wednesday Friday at this time now today
00:31
I'd like to start by giving you a maybe
00:35
a brief overview of of the course
00:41
content as well as some administrative
00:43
information most importantly our website
00:46
information so that you can get all of
00:50
the other information you're going to
00:52
need in this course and then the balance
00:55
of the time I'm going to start on the
00:57
first topic that we'll be covering in
00:59
this course right now we have a number
01:04
of powerpoints all the PowerPoint
01:06
lectures are there on the website and
01:07
the powerpoints employ clipart taken
01:10
from a variety of sources and those are
01:13
identified here all right what are we
01:18
going to be doing in the class well as
01:20
the title says we're gonna study data
01:22
structures we study data structures for
01:25
a wide variety of applications you know
01:28
I suspect all of you have taken our data
01:32
structures class before you've taken a
01:33
large number of computer science
01:35
computer engineering type classes and so
01:38
you're already very well familiar with
01:41
the importance of studying data
01:44
structures and the role they play in the
01:47
development of any future software you
01:48
might have - right now we will start by
01:54
looking at structures suitable for
01:56
external sorting of course they're
01:59
suited for other applications - we look
02:02
at single and double ended priority
02:04
queues you've probably studied
02:07
single-ended queues a lot in terms of
02:09
the heap but we look at things for
02:11
extensions of the heap as well as in
02:14
terms of single ended priority queue
02:15
applications as well as structures for
02:18
double ended priority queues for
02:21
dictionaries multi-dimensional search
02:24
most
02:25
to what you've seen so far is dealt with
02:26
searching in one dimensions we look at
02:29
searching in more than one dimensions
02:31
our data structures that are useful in
02:34
computational geometry and when we get
02:37
to that part we will see that while many
02:40
years ago people maybe thought of
02:42
computational geometry is something only
02:44
mathematicians did most of what takes
02:46
place today is modeled as computational
02:48
geometry problems so these structures
02:50
are finding a very large application
02:55
data structures used in image processing
02:57
in packet routing and classification for
03:01
the internet and this is just a small
03:03
sampling of the applications for the
03:05
data structures we're going to be
03:07
looking at all right so so that was kind
03:15
of at the application level in terms of
03:17
what we actually will need we will be
03:20
doing complexity analysis for our data
03:22
structures and so for that you'll need
03:25
worst case complexity that's something
03:27
that you're all probably very familiar
03:29
with average complexity something you've
03:31
also seen reasonable amount of and then
03:34
amortize complexity something that many
03:37
of you have probably not seen so far
03:42
okay you need to know C++ at least you
03:47
need to be able to read it most of the
03:48
readings are in C++ we do have a
03:52
programming project in this class and
03:54
that can be done in pretty much any
03:56
high-level language though I suspect
03:58
most we would do it either in Java and
04:00
C++ you need to know asymptotic
04:05
complexity so you should be quite
04:09
familiar with the big old theta and
04:11
Omega notations most of what we'll be
04:13
doing is Big O but occasionally we will
04:15
be making use of the theta and Omega
04:18
notations you should have taken an
04:22
undergraduate data structures class so
04:24
you should be very familiar with stacks
04:27
and queues linked lists trees graphs
04:33
okay it's all that stuff you should know
04:36
before you walked in the room today I'll
04:42
really not be reviewing any of that
04:44
material okay
04:47
now as I said there is a website for the
04:49
course and this may be the most
04:52
important information I'm giving out
04:54
today you do need to go there you need
04:57
to browse through that website and see
04:59
what all information is there most of
05:05
the information there has been updated
05:06
for this semester there are some things
05:08
there that you'll see that are clearly
05:10
labeled summer 2005
05:12
that's not for this semester the
05:15
assignments that are there are summer's
05:17
assignments we have yet to replace those
05:19
with the assignments for this particular
05:21
semester okay but things that are not
05:25
dated are for fall just watch out for
05:29
there are a small number of places which
05:32
say summer 2005 we'd know those for now
05:34
we will update those later this week all
05:39
right so you can pretty much get the
05:42
handouts from the handouts corresponding
05:46
to all the PowerPoint we're using you
05:48
can download you can download the actual
05:49
PowerPoint files and go through them
05:53
using your own PowerPoint presentation
05:56
software you can find out information
05:58
about the book we're using about the
06:00
readings you can get past exams
06:06
solutions to these exams find out who
06:09
our TAS are what their office hours are
06:11
and so on and you can also find out
06:15
where my office is and what times you
06:19
can find me most easily okay all right
06:23
so be sure that you've noted down that
06:26
piece of information
06:33
okay yeah we do have assignments and
06:37
exams in this class 25% of the grade
06:41
comes from the assignments the total of
06:44
three assignments as I indicated one of
06:46
these as a programming assignment the
06:48
other two a paper and pencil assignments
06:53
there are three exams and each of those
06:57
counts for 25% of the grade the exams
07:02
tend not to be cumulative however if you
07:07
come into the second exam and they're
07:09
topics there that build on something
07:10
that was done in the first part you
07:13
certainly need to still remember what
07:14
was done in the first part to be able to
07:16
properly answer things that built on the
07:18
first part historically the great
07:31
cut-offs have been around 82% for an a
07:33
75 for a b-plus 70 for a be historically
07:39
almost all of the students end up in one
07:42
of those three categories where we do
07:45
sometimes get some C pluses since even
07:47
some C's
07:59
all right so you have any questions you
08:03
want to ask that kind of finishes the
08:05
administrative type stuff I wanted to do
08:08
before getting into the material for the
08:11
course any questions you have there's
08:19
got to be a question from this many of
08:22
you nope okay well guess as we go
08:27
through please ask questions often what
08:30
you find is that whatever is bothering
08:32
you is bothering everybody else too so
08:34
you're kind of doing a favor to
08:35
everybody by asking that question all
08:39
right so what we're going to be doing
08:42
today and in our next lecture is taking
08:48
a look at the notion of amortized
08:50
complexity so we'll end up looking at a
08:55
small number of examples maybe a total
08:57
of three examples and the use of
08:58
amortized complexity and then there'll
09:00
be a gap of three or four weeks before
09:03
we actually use amortized complexity to
09:06
analyze our data structures and that
09:10
will give you some time to feel
09:12
comfortable with the notion of amortized
09:14
complexity as we'll see amortized
09:17
complexity is very different from the
09:21
kinds of complexities you might have
09:23
seen a lot in the past namely worst case
09:26
and average unlike worst case and
09:30
average complexity which are fairly
09:32
intuitive amortize complexity has no
09:35
intuitive counterpart so it's a very
09:37
non-intuitive thing it's kind of hard to
09:39
and and for that reason it's a bit
09:41
difficult to kind of feel comfortable
09:43
with it all right so worst case
09:46
complexity you've seen average
09:48
complexity you've seen and amortized
09:50
perhaps some of you've seen but I
09:52
suspect the majority of you haven't
09:57
let's just take a quick look at worst an
10:02
average case and see what the
10:04
capabilities or limitations of these two
10:06
are Before we jump into amortized
10:09
complexity I stopped at take a look at
10:13
quicksort you don't really need to
10:15
remember what quicksort is it's a
10:17
sorting method and say you've been asked
10:24
to sort n distinct numbers and I come to
10:28
you and I say well I've got a quicksort
10:30
program and it's worst case time as 10 n
10:32
square microseconds on this particular
10:35
machine okay all right so I've got a
10:37
program of compiler dev machine it's
10:38
time and I come to you with a statement
10:41
of this type
10:43
well then from that statement what you
10:47
can conclude is that for every value of
10:51
n there is some sequence of n different
10:53
numbers or in distinct numbers for which
10:55
the runtime will actually be ten n
10:57
square microseconds now if I'd meant
11:03
that you can't do any worse than ten N
11:07
squared another worded that's different
11:09
and said the worst case time is at most
11:11
ten n square or most simply the run time
11:13
is at most ten and square okay but since
11:17
I said the worst case time is ten n
11:18
square then what I'm telling you is that
11:20
for every n you're going to spend ten N
11:24
squared microseconds on some input but
11:28
I'm also telling you that there is no N
11:32
and corresponding input for which you
11:36
will spend more than ten and square
11:37
microseconds okay so I'm telling you
11:41
both of these things okay and so there
11:43
is some you know an intuition behind
11:45
what I mean by this case now if I come
11:52
and tell you that the average time is
11:54
five n log n base two microseconds well
12:01
then what I'm telling you is if you look
12:03
at any n say for example N equals 1,000
12:06
well then there are 1,000 factorial
12:10
different logically different possible
12:13
inputs you can get depending upon how
12:15
you rearrange these thousand different
12:16
numbers okay so if you took the time
12:22
required by each of these 1,000
12:25
factorial sequences
12:27
to do your quick sort and he added up
12:30
all of that and you divided by 1,000
12:32
factorial well then what you'll get is
12:36
the average time okay again I'm making
12:38
the assumption that each of those
12:40
different sequences is sorted with the
12:42
same probability okay so I'm averaging
12:46
out over all possible inputs for a
12:49
particular n and saying that when you do
12:51
that your run time is going to be 5 n
12:54
log n all right so that's what I mean by
13:00
average all right let's see how we can
13:06
use this information so if you're going
13:09
to sort only 500 of these sequences okay
13:12
let's say n as a thousand and you're
13:15
going to sold only 500 and now I want to
13:17
know well how much time is it going to
13:19
take to sort these 500 well I can say
13:25
for sure that you won't take more than
13:27
500 times the worst case time and the
13:31
worst case time was ten and square okay
13:34
so I can use the worst case time to come
13:39
to the conclusion that my 500 sequences
13:42
all told will not take more than 500
13:44
times ten and square okay what I can't
13:48
do is tell you that it's going to take
13:50
500 times the average time I may have
13:57
good reason to expect that that's what's
13:59
going to happen okay if you pick the 500
14:02
sequences at random from that thousand
14:04
factorial pool there's a very good
14:06
likelihood you're going to run in this
14:08
much time but there's no certainty that
14:09
it will it's entirely possible you're
14:12
running close to this a lot more than
14:14
that okay all right so when you want to
14:18
make statements about the cost of
14:20
sorting some number of times you have to
14:22
then go reliably on the worst case well
14:29
let's turn our attention to performing a
14:31
sequence of tasks okay so I guess here
14:34
you could say we're doing a sequence of
14:35
sorts so let's look at it in a more
14:37
abstract context we got tasks that have
14:39
been done and
14:40
going to perform n tasks so if you're
14:44
thinking of a data structure for
14:45
single-ended prior to Q we'll say a heap
14:48
well then task one might be to insert my
14:53
own task to maybe to insert an item
14:55
class three maybe to insert task four
14:57
maybe to delete the men task five maybe
15:00
to find the mantastic could be delete
15:01
them and seven could be insert and so on
15:03
okay so I've got a sequence of tasks and
15:05
tasks may be different as in the single
15:10
ended prior to queue example you could
15:12
have a fine men insert delete men task
15:16
could be the same as in our sort example
15:19
sort the sequence or that sequence or
15:21
the third sequence all right so I got a
15:25
sequence of tasks and if I come and tell
15:29
you that the worst case cost of any
15:31
tasks in the sequence is given by C sub
15:34
worst case then and I also tell you that
15:40
C sub I is the actual cost of performing
15:43
the eyuth task in the sequence okay so
15:51
then I can conclude that the actual cost
15:53
of the itis cannot exceed the worst case
15:55
cost and so n times the worst case cost
16:02
is an upper bound on the cost of the
16:03
sequence of tasks all right we saw that
16:09
with our quicksort example similarly if
16:13
you just want to know the cost of the
16:14
first J tasks in the sequence
16:16
you just take J multiplied by the worst
16:18
case that'll give you the give you a
16:20
bound on the cost of the first J tasks
16:28
now if you knew the average then if you
16:33
knew all of the actual costs we know
16:36
that the average would be some of the
16:37
actual costs divided by the number of
16:39
tasks all right so here what one of the
16:48
inequalities that we had before seems to
16:51
apply n times the average is the cost of
16:55
the sequence but J times the average
17:00
doesn't tell you anything about the cost
17:03
of the first J cos now in most
17:13
applications determining the average
17:15
cost is quite hard and that's why you
17:17
probably haven't seen too many average
17:19
case analysis in any of the courses
17:21
you've taken in the past alright so if
17:30
you're performing a bunch of tasks then
17:33
we may be interested in getting a bound
17:36
on how much time does it take to perform
17:39
this entire sequence of tasks rather
17:41
than how much time does it take to
17:42
perform each individual task ok so
17:46
that's certainly true if you look at
17:48
single ended priority queue in most
17:51
applications you don't really care how
17:53
much time does it take to do a
17:55
particular insert or a particular delete
17:57
but this single ended product key was
18:01
embedded in a larger program and you
18:03
want to know how much time does this
18:04
program take to run from start to finish
18:06
so we want to know across the running of
18:09
this program you might have done 10,000
18:11
inserts 20,000 fine mins and 5,000
18:15
delete mins well how much time did it
18:17
take to do all of these tasks together
18:19
okay you know the only method we have
18:24
right now to give an accurate or a
18:27
lasting bound a true bound on the worst
18:30
case cost of a task sequence is to take
18:33
the worst case cost of an individual
18:35
operation or entity in that sequence and
18:38
multiplied by the number of
18:42
tasks in the sequence okay now what we
18:46
will see is that we can often do a lot
18:49
better than this by using the concept of
18:53
amortized complexity and that's why I'm
18:55
a pice complexities of interest that we
19:00
will study several data structures in
19:02
this class where the worst-case time to
19:07
say perform an insert might be order
19:10
event and from that you might conclude
19:13
this is a bad data structure but if you
19:16
add up the times across all operations
19:18
you might perform in any possible
19:20
sequence the cost of that sequence might
19:23
turn out to be very very low and this
19:25
data structure might outperform anything
19:27
else we know which gives a good per
19:30
operation guarantee whereas this new
19:33
structure gives a much better percy qin
19:36
s-- guarantee on performance okay so and
19:41
to arrive at that better bound on the
19:43
cost of a sequence we can't do that
19:45
using our traditional worst-case
19:47
analysis that'll give us a lousy bound
19:50
but amortized complexity would give us a
19:53
better bound showing that our data
19:55
structure in fact is good all right so
20:01
so the question then is well what what
20:03
is this amortized complexity yeah it
20:10
would look like you really have only two
20:12
types of complexity you got worst case
20:14
and you got average yeah amortize
20:17
complexity really bears no relationship
20:20
with the cost of performing an
20:22
individual task and it's in some sense
20:26
an accounting scheme where you basically
20:29
decide what you want to charge the task
20:32
okay so the amortized complexity of a
20:35
task is whatever you want to charge the
20:36
task how are there some rules that limit
20:40
the charging scheme you can use
20:46
before looking at the rule let's just
20:50
see how you might use amortized
20:52
complexity we essentially intend to use
20:54
amortize complex in a way similar to how
20:56
we were using worst case so if you
21:00
perform a task and times then
21:03
traditionally we would say the cost of
21:05
that sequence is n times the worst case
21:07
cost for a task okay
21:12
or if you had different tasks in there
21:16
like a search and insert and a delete
21:18
well then you may have different
21:20
worst-case cause for research for an
21:24
insert and delete in which case we could
21:26
just say if the first operation is a
21:28
search put in the worst case cost of a
21:31
search if the next one is a delete add
21:32
in the worst case cost it would delete
21:34
and so on okay so we might go one of
21:36
these two ways depending upon whether
21:38
there are all of the tasks are the same
21:41
okay so if you're just doing sort sort
21:43
sort sort we can just take the worst
21:45
case cost of a sort multiplied by n if
21:48
you're doing search in search search
21:49
search insert delete delete you would
21:51
take worst case poor task and add them
21:54
up now if you're using the amortized
22:00
complexity okay then we would do really
22:04
the same thing okay if all the tasks of
22:08
the same type of the same type we just
22:11
say n times the amortized cost and if
22:16
you had different types of tasks then
22:18
we'll take the amortized cost of each
22:20
task and add up so we intend to use
22:26
amortize complexity the same way as we
22:28
intend to use worst case complexity and
22:30
in both cases we're going to draw the
22:32
same conclusion that what you get from
22:35
here has to bound the cost of your
22:38
sequence of operations of your sequence
22:40
of tasks okay so both of these are
22:45
trying to achieve the same objective
22:47
bound the cost of a sequence and here it
22:51
is obvious to see that it's doing that
22:53
because you're taking the worst case
22:54
cost over tasks it's obviously bound the
22:57
cost of the sequence
22:59
okay now since the objective is the same
23:02
the charging scheme that you use has to
23:06
guarantee that whether you go this way
23:08
or that way you in fact bound the cost
23:10
of a sequence the real cost of the
23:13
sequence okay all right so because of
23:23
the way we're going to use amortized
23:24
cost we get a constraint on how you can
23:27
assign amortize cost okay so the wave
23:32
whatever way you choose to assign the
23:35
cost it has to satisfy this requirement
23:38
okay that if you take the sum of the
23:43
actual cost of the tasks that sum has to
23:46
be bounded by the sum of the amortized
23:48
cost because in the end this is the
23:50
conclusion we're going to draw now
23:58
certainly in order to satisfy this
23:59
constraint you could simply assign
24:02
amortized cost equal to worst-case cost
24:06
and that'll be one way to do it and you
24:08
would satisfy the constraint but then we
24:10
won't be able to get and get any better
24:12
complexity bound on our data structures
24:14
than using the old scheme all right so
24:22
so long as we satisfy this constraint
24:25
the way we'd intended to use amortize
24:28
complexity would be a valid thing to do
24:33
alright so the amortized cost of a task
24:36
is or could be anything it's whatever
24:41
you choose to assign it the only
24:43
requirement is that once you're done
24:45
assigning amortized costs this
24:47
relationship must hold
24:55
okay
25:00
as we will see the amortized complexity
25:04
of a task may not have any relationship
25:07
to the actual cost sometimes the
25:11
amortized cost of a task may exceed its
25:13
actual cost at other times it may be
25:15
less than its actual cost but when you
25:19
add up across the sequence the sum of
25:21
the amortized costs should never be less
25:23
than the sum of the actual costs alright
25:32
so we've seen this before you typically
25:34
have been using worst case you always
25:36
charge at least as much as something
25:38
cost okay and so you get that thing but
25:45
when we do amortize complexity you may
25:48
sometimes be charging something less
25:50
than it actually cost you and that's
25:52
permissible so long as when you add up
25:55
across the sequence you don't have a
25:56
cost that is less than the actual cost
26:05
okay right now when we do amortize
26:10
complexity analysis we will often make
26:13
use of the notion of a potential
26:15
function this is something that keeps
26:18
track of the amount by which you have by
26:24
which your amortized costs exceed the
26:27
sum of the actual costs in your sequence
26:29
okay so it's kind of it's like a
26:33
checkbook balance it just tells you how
26:38
much money do you have in the bank after
26:40
you take out all of your expenses things
26:43
that you charge for and like a bank we
26:45
require that this always be non-negative
26:47
that means the amount that is being
26:49
charged is always more than the amount
26:53
that is being taken out the amount
26:54
that's being taken out is the actual
26:56
cost the amount that you're charging is
26:58
the deposit all right so the potential
27:03
after you do the eyuth operation okay
27:07
it's defined to be the potential before
27:10
you do the aisle
27:12
so which means after you do the I minus
27:13
1 of operation okay and to that you add
27:18
in the amount you charge the is and the
27:22
amount the I of actually cost you so if
27:26
you charge the I of operation 10 units
27:29
and it only costs you six then you've
27:32
overcharged it by four so you have
27:34
accumulated a reserve of four that you
27:37
can apply to a future operation so you
27:40
can under Jap you operation by four so
27:43
the potential is keeping track of the
27:45
reserve that you have accumulated so
27:47
kind of like your bank balance and so p0
27:51
gives you the reserve at the time you
27:54
start p1 is how much reserve do you have
27:58
after the first operation p2 is the
28:00
reserve after the second p3 is the
28:02
reserve after the fourth and so on okay
28:05
and so long as your potential never
28:11
drops below what you started with p0
28:13
you're doing okay you're never charged
28:18
in operations and accumulative sense
28:20
less than what they're costing you all
28:25
right
28:26
so p3 may be less than p2 okay because
28:31
the amount you charged it was less than
28:34
what it actually cost p3 maybe more than
28:38
p2 because the amount you charged it was
28:40
more than what it actually cost so the
28:44
relationship between the piece could go
28:45
either way they could increase they
28:47
could decrease but since you're keeping
28:52
track of the balance in the O a charge
28:54
the requirement is that you never have a
28:59
P that drops below your starting balance
29:01
of p0 okay let's see that in in
29:09
mathematical terms okay all right so
29:13
starting with the definition I move the
29:15
P I minus 1 to this side and that gives
29:17
me the amount of overcharge for the i/o
29:21
operation if it's negative you're under
29:23
charge if it's positive it overcharged
29:24
okay so I'm going to move the P right
29:27
minus one to this side I'm going to sum
29:29
up across all of my operations all of
29:33
the tasks in my sequence okay then on
29:36
the right hand side I'm just left with
29:38
that okay so P I minus P I minus one is
29:42
the amount of the overcharge the over
29:43
charges amortized cost minus actual
29:45
constant all right so on the left hand
29:50
side I have a telescoping sum in that if
29:55
I put I equals 1 as P 1 minus p 0 then
29:58
at I equals 2 it is P 2 minus P 1 so the
30:00
P ones cancel out okay and then the I
30:04
equals 3 you have P 3 minus P 2 so the P
30:06
twos cancel out okay so here on the left
30:09
side here telescoping sum you're only
30:11
left with P n minus p0 and on the right
30:14
hand side you have the sum of the over
30:16
charges
30:21
and since we require that the sum of the
30:25
amortized cost be at least as big as the
30:27
sum of the actual costs the sum on the
30:32
right hand side has to be at least zero
30:37
so if you have a valid amortization
30:39
scheme then you will always have this
30:43
property the potential after n
30:46
operations minus the potential before
30:50
you started has to be at least zero and
30:54
and and and that's the only requirement
30:57
for amortized complexity assignment
31:02
alright we'll find this a handy way to
31:04
make sure that we have valid amortized
31:08
complexity assignments okay all right
31:13
any questions about the potential
31:14
function we'll see it I guess several
31:18
times in the next lecture probably not
31:20
again in this lecture yeah we'll come to
31:36
an example in a moment they'll give you
31:37
some idea we'll look at I'll name three
31:40
of the common methods used and we look
31:42
at examples but I guess at this time I
31:46
just want to get across the concept of
31:48
what an amortized cost is and how you
31:51
would use it
31:58
alright typically and our analyses will
32:00
start with p 0 equals 0 in which case
32:03
you know this term disappears so then
32:07
you want that the potential is always
32:08
non-negative and P I is the amount of
32:11
overcharge for the first I operations
32:16
now let's turn to an example we start
32:21
this example today we will finish it
32:22
next time so look at the problem of
32:27
rewriting complex arithmetic statements
32:30
as a sequence of simple arithmetic
32:32
statements so a complex arithmetic
32:35
statement I'm going to use that term to
32:37
mean something that has a bunch of
32:39
parentheses in it and simple ones will
32:41
be those that don't have any parentheses
32:44
so this arithmetic statement here I want
32:46
to replace this by a sequence which
32:49
looks like that so if you perform these
32:57
three statements in the end the value
32:59
assigned to a will be exactly what it
33:00
was assigned over there and what I want
33:06
to look at is how do you translate from
33:08
here to that alright to perform this
33:17
translation I'm going to employ a
33:22
procedure called process next symbol and
33:26
basically what this does is you know
33:29
first time it's going to come and take a
33:30
look at nay then a look at an equal sign
33:32
then it neck so it's going to extract
33:34
the symbols from my rhythmic statement
33:35
then we'll do something with it and in
33:42
order for it to perform its job properly
33:45
it's going to employ a stack and so
33:47
we're going to start with an empty stack
33:50
and then I'm going to just march left
33:53
you're right and I'm going to process
33:54
each symbol and when I'm done I should
33:56
have my translated set of statements
34:00
right so I assume there are n symbols in
34:04
my statement I'm going to go through
34:07
them from left to right
34:10
and I just process each symbol okay and
34:13
when I've processed the semicolon I'm
34:15
finished I've got my translated set of
34:17
statements all right so at a high level
34:25
this three line code is going to do the
34:28
job okay
34:30
the interesting part is well would you
34:31
how does the process next symbol work
34:37
all right so process next symbol will
34:42
pick up the next symbol from the
34:44
arithmetic statement and then if it's
34:49
not a left print if it's not a right
34:51
parenthesis or a semicolon it's just
34:53
going to add that symbol to the stack so
34:55
you'll push it onto the stack and then
35:01
if it finds the right parenthesis or
35:03
some I call and that's when it'll do
35:04
something interesting okay so when you
35:08
see a right parenthesis a semicolon at
35:10
that time you'll spit out a simple
35:12
statement otherwise you just collect
35:13
things on the stack let's see that
35:16
process and operation so here's my empty
35:18
stack as I start by extract the first
35:22
symbol that's a it's not a right
35:24
parenthesis semicolon so I push it to
35:27
the stack then I extract an equal sign
35:30
and X a plus the left parenthesis and
35:33
other left parenthesis and a a plus and
35:36
a B okay alright so most of the symbols
35:42
are easy you just put them onto a stack
35:44
you don't do anything with them and then
35:46
I've come to my first exception symbol
35:49
that's a right parenthesis okay so when
35:52
you see a right parenthesis at that time
35:55
what I'm going to do is I'm going to pop
35:58
things off the stack up to the first
36:00
left parenthesis and that'll give you my
36:01
first statement all right so when you
36:06
see a right parenthesis you just keep
36:08
popping from the stack to the first left
36:10
parenthesis and in this example I'm
36:12
going to assume all the parenthesis are
36:14
well-matched so you've got a well formed
36:16
statement and I'll create a new variable
36:22
for the left-hand side of the statement
36:24
write it out and put that new variable
36:26
in the staff okay all right so in this
36:29
case you'll take the be off the plus the
36:32
a the left parenthesis then I'll create
36:36
a statement which is z1 equals a plus B
36:40
and then this variable z1 I'll put that
36:44
onto the stack because this will become
36:46
a variable for some future statement so
36:55
the cost of process next symbol this
36:57
time I had to take the be off the plus
37:01
the a the equals in z1 so that three
37:03
four five symbols got taken off and I
37:05
got one put on so that cost me six the
37:09
previous process next symbols cost me
37:11
one I just put something on the stack
37:12
but this one cost me six units all right
37:17
so let's continue okay alright so next
37:22
SC a times so that just gets pushed onto
37:26
the stack that cost me one I see a see
37:29
that gets pushed on I see a plus I see a
37:31
D so all of those cost one each but then
37:35
I see a right parenthesis so now I start
37:37
popping okay so I prompt the D the plus
37:40
the see the times the z1 and the left
37:45
parenthesis and I write out my
37:47
expression using a new variable Z - okay
37:53
and then I put z2 onto the stack so this
37:58
invocation of process next symbol cost
38:01
me one to get the deed and the plus
38:03
that's one two three four five six seven
38:06
okay there were I guess six six pops and
38:10
then a left parenthesis got popped that
38:12
seven then I put this fellow on the
38:14
stack that's eight okay so at a cost of
38:16
eight on this invocation of process next
38:19
symbol so it's the same cost process
38:22
next symbol but it costs you different
38:23
amount each time you invoke it alright
38:28
so then I continue okay I get a plus I
38:33
put it on I got a why I put it on the
38:35
stack and now I see a semicolon
38:38
which is the end of statement maka and
38:40
at this time I need to flush the stack
38:43
okay
38:44
so when you see a semicolon you flush
38:47
the stack you pop everything off and you
38:49
create the last assignment statement and
38:59
this costs you the number of pops that
39:02
you have to do all right so that's how
39:08
I'm going to do my translation make use
39:11
of a stack at a high level I got a very
39:13
simple program just a for loop which
39:17
process symbols one at a time to be done
39:20
process next symbol pull the symbol out
39:22
of your statement classifies it if it's
39:26
not a right parenthesis or semi colon
39:28
you just push it on the stack if it's
39:30
one of the two you do some number of
39:31
pops and possibly a push aren't any
39:35
questions about how that works okay all
39:43
right so I also get the complexity okay
39:46
so first let's get the complexity of
39:48
process next symbol using our
39:50
traditional analysis schemes okay so
39:54
it's Big O of the number of pops that
39:57
you do and the number of pops you can do
40:05
depends on the index of the loop you're
40:08
in the loop that was invoking you when I
40:14
is 10 there can only be 9 symbols in the
40:18
stack okay so you can only do nine pops
40:21
when I is 20 they can only be 19 symbols
40:23
in the stack you can only do 19 pops so
40:27
one way is to say well the complexity of
40:29
this is order of I where I is the index
40:31
of that for loop
40:38
okay so now I want the overall
40:41
complexity so this one here has a
40:44
complexity disorder of AI and AI runs
40:47
from 1 to n added up that gives me n
40:49
squared
40:53
alternatively I could say well the worst
40:55
case complexity of this is n ok and
40:59
we're calling it n times source N
41:02
squared and that's a perfectly valid
41:11
analysis because bigger only gives you
41:13
an upper bound but you're left with the
41:16
wrong conclusion that this is a
41:18
quadratic process now you can actually
41:22
show that this thing runs in order of n
41:24
time even though an individual
41:28
invocation of process next symbol might
41:30
itself take you n time all right so the
41:36
thing is how do we come up with this
41:37
better bound as far as amortized
41:43
complexity goes there are three common
41:45
techniques people use one of these is
41:48
called the aggregate method another
41:50
one's called the accounting method and
41:51
then there's the potential function
41:53
method and we'll analyze our translation
42:01
example using all three of the methods
42:03
today we'll be able to do only the
42:05
aggregate method alright so the
42:10
aggregate method what you do is you
42:14
somehow obtain a good upper bound on the
42:17
whole sequence instead of worrying about
42:21
an individual invocation of process and
42:23
X symbol you tried to reason at a
42:26
different level and say well all n
42:28
invocations couldn't possibly take more
42:30
than so much time ok so you get the cost
42:32
of the whole sequence and then you
42:35
divide by the number of tasks in the
42:38
sequence to get the amortized cost poor
42:41
invocation of process next symbol and
42:44
because of that it's easy to see the the
42:47
sum of the actual cost cannot exceed the
42:49
sum of the amortized cost because you
42:51
started off with a
42:52
good bound on the some of the actual
42:54
past and / M okay
42:59
let's try this out this works quite well
43:02
on this particular example though as we
43:05
will see when we actually get to real
43:07
data structures this method is really
43:10
very limited use okay so we're going to
43:16
reason at a different level I don't care
43:18
how much an individual invocation of
43:20
process next symbol costs honor how much
43:22
does it cost to run it n times in the
43:26
context of a statement translation
43:31
alright so the actual cost of all the
43:36
invitations is really proportional to
43:40
the total number of stack pops and
43:43
pushes that you do you can't do more
43:48
pops and pushes so in that sense it's
43:50
really proportional to the total number
43:51
of pushes that you do all right
43:56
so across all of the n invocations if
44:00
you have only n symbols you can only do
44:02
n pushes to see the truth of that there
44:08
are some symbols not in the input that
44:09
are getting pushed like Z 1 Z 2 okay but
44:12
for each Z one you push there's a right
44:14
parenthesis that you don't push okay so
44:17
the total number of things you can push
44:19
cannot be more than n in fact it's going
44:21
to be less than n because the semicolon
44:23
doesn't have a corresponding thing that
44:24
gets pushed okay but that we use n as a
44:28
loose bound so the number of pushes is
44:31
at most n so the number of pops is at
44:34
most n the total number of pops and
44:39
pushes therefore can't be more than two
44:40
n so all n invocations cost you at most
44:47
two n units
44:51
you can get the amortized cost by
44:53
staking the cost of the sequence
44:55
dividing it by the number of tasks in
44:57
the sequence and saying that the
44:59
amortized cost of process next symbol is
45:01
2 even though it's worst case cost is n
45:06
it's amortized cost is only 2
45:22
all right few words about the aggregate
45:25
method I said it's not very useful it's
45:29
not very useful because you have to
45:30
first come up with a good bound on the
45:32
aggregate cost of your task sequence and
45:35
that's really what you are trying to
45:38
come or come at through a different
45:40
direction first computer an amortized
45:41
cost and then get the aggregate cost a
45:44
good bound on the aggregate cost but if
45:46
you first get a good bound on the
45:48
aggregate cost oh and why do you care
45:49
about the amortized why go through this
45:51
process of dividing by n only to
45:53
multiply it by n and the very next step
45:55
ok alright so in that sense the at the
46:03
aggregate method seems to be kind of a
46:10
not very relevant method you have to
46:13
figure out the aggregate cost a good
46:16
bound on the aggregate cost and if you
46:18
did that there's no point computing the
46:19
amortized cost after that ok now what
46:23
we'll see in the examples we're going to
46:24
deal with not in the next lecture next
46:26
lecture was to look at some simple
46:27
examples but three or four weeks down
46:30
the road when we look at real data
46:31
structure examples there we'll see that
46:35
coming up with the aggregate cost
46:37
directly using the aggregate method is
46:40
really going to be very very hard we're
46:42
gonna have to rely on one of the other
46:44
two schemes where we will first compute
46:47
the amortized cost and then add up the
46:50
amortized cost to get the aggregate okay
46:55
alright any questions all right so as I
47:03
said we'll continue with studying basic
47:05
amortized complexity one more lecture
47:07
and then now we'll get into real data
47:10
structures okay
47:14
you