0
Analysis of Algorithms: insertion sort example, beginning
of analysis
Preceded by: insertion sort; pseudocode; loop invariant
Introductory text, shown during opening frames with title and credits.
0
ok So let's give an example
of that.
Let's give an example of insertion sort.
3.333
Imagine we're doing 8,
2, 4, 9, 3, 6; so we start out with 2 - key equals 2 - and we
figure out that we want to insert it there, so now we have 2,
8, 4, 9, 3, 6.
Imagine that we are sorting the array {8, 2, 4, 9, 3, 6}. We start out with 2, so the key equals 2, and we figure out that we want to insert it in there, before 8. Now we have {2, 8, 4, 9, 3, 6}
there The lecturer often points to the blackboard and simply says there (or over here in the next sentence) without saying where.
25
Then we look at the 4, and we
say: "Oh, that goes over here." So we get 2, 4, 8, 9,
3, 6, ok, after the second iteration of the outer loop.
Then we look at the 4 and we say :"That goes over here." So, after the second iteration of the outer loop we get {2, 4, 8, 9, 3,
6}
look at again using look at to mean "select, direct our attention to"
39.333
Then we look at 9, and we
discover immediately it just goes right there. Very little work
to do on that step.
The next key is 9, and we discover immediately that it goes right back to the same position where it came from. There is very little work to do on that step.
right there another pointing, and there is over there in the next sentence and in there in the sentence after that.
47.53299999999999
OK so we have
exactly the same thing output after that iteration, and we look
at the three, that's going to be inserted over there, 2, 3,
4, 8, 9, 6,
So we have exactly the same output after that iteration, and the next key is 3, and it's going to be inserted over there, right after 2.
the same thing output the word thing is unnecessary here: the same output. People do often say it's the same thing, meaning simply "it's the same."
62.73299999999999
and finally we
look at the 6, that goes in there, 2, 3, 4, 6, 8, 9, and at
that point we're done.
Finally, we look at 6, and it goes right before 8, and at that point we are done.
we are done we have finished what we have been doing
74.00000000000001
OK? Question? [A
student asks whether the array indices start at 1 or at 0.] The
array indices here starts at 1, yes, A[1-n], ok?
In many programming languages, as you probably know, array indices start at 0, not 1.
indices irregular plural of index. Since it's plural, the verb form should have been start, not starts.
96.40000000000002
OK So this is
the insertion sort algorithm, and it's the first algorithm
that we're going to analyze. Okay, we're going to pick
out... pull out some tools we have from our math background to
help to analyze it. So, first of all let's took ... take a
look at the issue of running time
So this is the insertion sort algorithm, and it's the first algorithm we are going to analyze. We're going to pull out some tools from our math background to help to analyze it. First of all, let's take a look at the issue of running time.
we're going to pull out The lecturer actually says we're gonna. This is common in fast speech. Another common abbreviation is I wanna, for "I want to."
pull out some tools ... from our math background a joking way to say that we are going to need some math tools for algorithm analysis
116.933
So the running time
depends -- of this algorithm -- depends on a lot of things. OK?
So one thing it depends on is on the input itself.
The running time of this algorithm depends on a lot of things. One thing it depends on is the input itself.
the input itself the specific input that is given to the algorithm
135.53299999999982
OK? So for
example if the input is already sorted OK? then insertion sort has
very little work to do. OK? because every time through it's
going to be like this case.
For example, if the input is already sorted, then insertion sort has very little work to do because every time through it's going to be like this case.
this case The lecturer points to the row in which 9 is the key.
154.86700000000005
Doesn't
have to shuffle too many guys over because they are already in
place. OK? whereas .. In some sense, what's the worst case
for insertion sort?
It doesn't have to move too many numbers over because they are already in place. In some sense, what's the worst case for instertion sort?
too many guys the word guys can be used informally for almost anything
in some sense "in some sense that we have not yet defined," we are still talking informally. It's unusual to follow this expression with a question.
166
Yeah, if it's
reverse-sorted then it's going to have to do a lot of work,
because it's going to have to shuffle everything over on
each step.OK of the outer loop.
[A student answers the question.] Yes, if it's reverse-sorted then it's going to have to do a lot of work, because it's going to have to
shuffle everything over on each step.of the outer loop.
reverse-sorted sorted in reverse order
because it's going to have to He actually says 'cos it's gonna have to. Another example of common abbreviations.
177.667
In addition to the actual
input, it depends of course on the input size.
In addition to the actual input, it depends of course on the input size.
187.1329999999999
So here, for
example, we did six elements. It's gonna take longer if we
do for example do 6 times 10 to the 9th elements.
So here, for example, we did six elements. It's going to take longer if we, for example, do 6 times 10 to the 9th elements (6*109)
It is going to take longer "it is going to take more time than sorting six elements." take + duration: How long does it take to walk there? It takes a week to drive from New York to California.
200.6669999999999
OK So if
we're sorting a lot more stuff, it's gonna take us a
lot longer.
If we are sorting a lot more stuff, it's going to take us a lot longer.
stuff another general word that can be used to refer to many different things
208.53300000000004
So typically
the way we handle that is we're going to parameterize
things in the input size. So we're going to talk of time as
a
function of the size of things we are sorting. So we
can look at what is the behavior of that. OK?
Typically, the way we handle that is [the following:] we're going to parameterize the complexity of the algorithm in the input size. We're going to talk of time as a function of the size of the arrays we are sorting.
the way we handle that is we're going to There is no connection (except by intonation) between the two parts of the sentence. In writing, you would need an explicit connection: The way we are going to handle this is the following: we are going to.... Or, more likely, We are going to handle this in the following way: we will ...
parameterize things... things we are sorting Those are two different kinds of things, and neither of them are really "things" that you can hold in your hand.
the behavior of that What is "that" here? The gesture suggests that he means "the behavior of the graph of that function."
233.8
And the last thing I wanna
say about running time is generally we want upper bounds on the
running time. We want to know that the time is no more than a
certain amount.
And the last thing I want to say about running time is [that] generally we want upper bounds on the running time.
the last thing I wanna say Another common use of the word thing.
is generally There is no syntactic connection between the first and the second parts of this sentence. They are connected by intonation.
247.33300000000006
And the reason
is because that represents a guarantee to the user. OK? So if I
say it's not gonna run... for example if I tell you:
"here's a program and it won't run more than 3
seconds" OK? that gives you real information about how you
can use it for example in a real-time setting..
The reaon is that it (an upper bound) represents a guarantee to the user. For example, if I tell you "here's a program, and it won't run more than 3 seconds" -- that gives you real information about how you can use it, for example, in a real-time setting..
the reason is because often said instead of the reason is that
real-time A real-time application is a program that processes data from events in the real world, and there is a tight limit on how much time can pass between the event and the program's response.
266.667
OK whereas if I said:
"Here's a program and... you know... it goes at least
three seconds" you don't know if it's gonna go,
you know, for three years. Doesn't give you that much
guarantee if you're a user of it.
Whereas if I said: "Here's a program and it goes at least
three seconds" you don't know if it's going to go for three years. [This] doesn't give you that much guarantee if you're a user of it.
The gestures and body language of the speaker indicates that he is going to make a joke.
that much guarantee same as much guarantee or particularly much guarantee
If I said A counter-to-fact condition
283.00000000000006
So generally we
want upper bounds because it represents a guarantee to the
user.
So, generally we want upper bounds because [providing an upper bound] represents a guarantee to the user. OR because they represent a guarantee to the user.
we want upper bounds because it represents Here the word it most likely refers to the action of providing an upper bound. Another possibility is that it refers to a single upper bound. The sentence is sloppy.
293.6669999999999
Sooo, (lifts the
blackboard) there are different kinds of analyses that people
do.
analyses irregular plural of analysis
305
Grammar topics:
- Spoken language:
- simple connections (so, OK)
- fillers (umm, actually, essentially)
- pointing phrases (right here, over there, in there)
- Irregular plural of nouns
index - indices; analysis - analyses
- Contrary-to-fact conditionals and the use of would
ex6
Expressions:
look at (an abtract thing); the same thing; we're done (are you done?); take (time duration);
Vocabulary:
thing; stuff; depend on;
CS terminology :
loop, inner loop, outer loop, loop invariant; array index, indices; algorithm analysis; running time; upper bound; real-time;