>> DAVID MALAN: All right.
We are back.
So in this segment on programming what I thought we'd do is a mix of things.
One, do a little bit of something hands-on,
albeit using a more playful programming environment--
one that is demonstrative of exactly the kinds of ideas
we've been talking about, but a little more formally.
Two, look at some of the more technical ways
that a programmer would actually solve problems like the searching problem
that we looked at before and also a more fundamentally
interesting problem of sorting.
>> We just assumed from the get go that that phone book was sorted,
but that alone is actually kind of a hard problem with many different ways
to solve it.
So we'll use these as a class of problems
representative of things that might be solved in general.
And then we'll talk about in some detail what
are called data structures-- fancier ways like linked lists
and hash tables and trees that a programmer would actually
use and generally use on a whiteboard to paint
a picture of what he or she envisions for implementing
some piece of software.
>> So let's do the hands-on portion first.
So just get your hands dirty with an environment called scratch.mit.edu.
This is a tool that we use in our undergraduate class.
Even though it's designed for ages 12 and up,
we use it for the up part of that quite a bit
since it's a nice, fun graphical way of learning
a little something about programming.
So head to that URL, where you should see a page quite like this,
and go ahead and click Join Scratch at top right
and choose a username and a password and ultimately get yourself
an account-- scratch.mit.edu.
I thought I'd use this as an opportunity first to show this.
A question came up during the break about what code actually looks like.
And we were talking during the break about C,
in particular-- particularly a lower level in an older language.
And I just did a quick Google search to find C code
for binary search, the algorithm that we used to search that phone book earlier.
This particular example, of course, doesn't search a phone book.
It just searches a whole bunch of numbers in the computer's memory.
But if you'd like to just get a visual sense of what an actual programming
language looks like, it looks a little something like this.
So it's about 20-plus, 30 or so lines of code,
but the conversation we were having over break
was about how this actually gets morphed into zeros and ones
and if you can't just revert that process and go from zeros and ones
back to code.
>> Unfortunately, the process is so transformative
that it's a lot easier said than done.
I went ahead and actually turned that program, Binary Search,
into zeros and ones by way of a program called The Compiler that I
happen to have here right on my Mac.
And if you look at the screen here, focusing specifically
on these middle six columns only, you'll see only zeros and ones.
And those are the zeros and ones that compose exactly that searching program.
>> And so each chunk of five bits, each byte of zeros and ones here,
represent some instruction typically inside of a computer.
And in fact, if you've heard the marketing slogan "Intel inside"-- that,
of course, just means you have an Intel CPU or brain inside the computer.
And what that means to be a CPU is that you have an instruction set,
so to speak.
>> Every CPU in the world, many of them made by Intel these days,
understands a finite number of instructions.
And those instructions are so low level as add these two numbers together,
multiply these two numbers together, move this piece of data from here
to here in memory, save this information from here to here in memory,
and so forth-- so very, very low-level, almost electronic details.
But with those mathematical operations coupled
with what we discussed earlier, the representation of data
as zeros and ones, can you build up everything
that a computer can do today, whether it's textual, graphical, musical,
or otherwise.
>> So this is very easy to get lost in the weeds of quickly.
And there's a lot of syntactical challenges
whereby if you make the simplest, stupidest of typos none of the program
will work whatsoever.
And so instead of using a language like C this morning,
I thought it would be more fun to actually do
something more visual, which while designed for kids
is actually a perfect manifestation of an actual programming
language-- just happens to use pictures instead of text
to represent those ideas.
>> So once you indeed have an account on scratch.mit.edu,
click the Create button at top left of the site.
And you should see an environment like the one I'm about to see on my screen
here.
And we'll spend just a little bit of time playing here.
Let's see if we can't all solve some problems together in the following way.
>> So what you'll see within this environment-- and actually just let
me pause.
Is anyone not here?
Not here?
OK.
So let me point out a few characteristics of this environment.
>> So at the top left of the screen, we have Scratch's stage, so to speak.
Scratch is not only the name of this programming language;
it's also the name of the cat that you see by default there in orange.
He is on a stage, so much like I described
the turtle earlier as being in a rectangular white board environment.
This cat's world is confined entirely to that rectangle up top there.
>> Meanwhile, on the right hand side here, it's
just a scripts area, a blank slate if you will.
This is where we're going to write our programs in just a moment.
And the building blocks that we shall use to write this program-- the puzzle
pieces, if you will-- are those right here in the middle,
and they're categorized by functionality.
So, for instance, I'm going to go ahead and demonstrate at least one of these.
I'm going to go ahead and click the Control category up top.
>> So these are the categories up top.
I'm going to click the Control category.
Rather, I'm going to click the Events category, the very first one up top.
And if you'd like to follow along even as we do this, you're quite welcome to.
I'm going to click and drag this first one, "when green flag clicked."
And then I'm going to drop it just roughly at the top of my blank slates.
>> And what's nice about Scratch is that this puzzle piece, when
interlocked with other puzzle pieces, is going to do literally
what those puzzle pieces say to do.
So, for instance, Scratch is right now in the middle of his world.
I'm going to go ahead and choose now, let's say, the Motion category,
if you'd like to do the same-- Motion category.
And now notice I have a whole bunch of puzzle pieces here
that, again, kind of do what they say.
And I'm going to go ahead and drag and drop the move block right over here.
>> And notice that as soon as you get close to the bottom of the "green flag
clicked" button, notice how a white line appears,
as though it's almost magnetic, it wants to go there.
Just let go, and it will snap together and the shapes will match.
And now you can perhaps almost guess where we're going with this.
>> If you look at the Scratch stage over here and look to the top of it,
you'll see a red light, a stop sign, and a green flag.
And I'm going to go ahead and watch my screen--
for just a moment, if you could.
I'm going to click the green flag right now,
and he moved what appears to be 10 steps or 10 pixels, 10 dots, on the screen.
>> And so not that exciting, but let me propose
without even teaching this, just using the own your own intuition-- let
me propose that you figure out how to make Scratch walk right off the stage.
Have him make way for the right side of the screen, all the way to the right.
Let me give you a moment or so to wrestle with that.
You might want to take a look at other categories of blocks.
All right.
So just to recap, when we have the green flag clicked here
and move 10 steps is the only instruction, each time I
click the green flag, what's happening?
Well, that's running my program.
So I could do this maybe 10 times manually,
but this feels a little bit hackish, so to speak,
whereby I'm not really solving the problem.
I'm just trying again and again and again and again
until I sort of accidentally achieve the directive
that I set out to achieve earlier.
>> But we know from our pseudocode earlier that there's
this notion in programming of looping, doing something again and again.
And so I saw that a bunch of you reached for what puzzle piece?
Repeat until.
So we could do something like repeat until.
And what did you repeat until exactly?
>> OK.
And let me go with one that's somewhat simpler for just a moment.
Let me go ahead and do this.
Notice that, as you may have discovered under Control,
there is this repeat block, which doesn't look like it's that big.
There's not much room in between those two yellow lines.
But as some of you might have noticed, if you drag and drop,
notice how it grows to fill the shape.
>> And you can even cram more.
It'll just keep growing if you drag and hover over it.
And I don't know what's best here, so let
me at least repeat five times, for instance, and then go back to the stage
and click the green flag.
And now notice it's not quite there.
>> Now some of you proposed, as Victoria just did, repeat 10 times.
And that generally does get him all the way,
but wouldn't there be a more robust way than arbitrarily figuring out
how many moves to make?
What might be a better block than repeat 10 times be?
>> Yeah, so why not do something forever?
And now let me move this puzzle piece inside there and get rid of this one.
Now notice no matter where Scratch starts, he goes to the edge.
And thankfully MIT, who makes Scratch, just
makes sure that he never disappears completely.
You can always grab his tail.
>> And just intuitively, why does he keep moving?
What is going on here?
He seems to have stopped, but then if I pick up and drag
he keeps wanting to go over there.
Why is that?
Truly, a computer is literally going to do what you tell it to do.
So if you told it earlier do the following thing forever, move 10 steps,
it's going to keep going and going until I hit the red stop sign
and stop the program altogether.
>> So even if you didn't do this, how could I
make Scratch move faster across the screen?
More steps, right?
So instead of doing 10 at a time, why don't we
go ahead and change it to-- what would you propose-- 50?
So now I'm going to click the green flag, and indeed, he goes really fast.
>> And this, of course, is just a manifestation of animation.
What is animation?
It's just showing you the human a whole bunch of still images really,
really, really fast.
And so if we're just telling him to move more steps,
we're just having the effect be to change where he is on the screen
all the more rapidly per unit of time.
>> Now the next challenge that I proposed was to have him bounce off the edge.
And without knowing what puzzle pieces exist-- because it's fine
if you don't get to the stage of the challenge-- what
do you want to do intuitively?
How would we have him bounce back and forth, between the left and right?
>> Yeah.
So we need some kind of condition, and we
seem to have conditionals, so to speak, under the Control category.
Which of these blocks do we probably want?
Yeah, maybe "if, then."
So notice that among the yellow blocks we have here, there is this "if"
or this "if, else" block that will allow us to make a decision to do this
or to do that.
And you can even nest them to do multiple things.
Or if you've not gone here yet, go ahead to the Sensing category
and-- let's see if it's here.
>> So what block might be helpful here to detect if he's off the stage?
Yeah, notice that some of these blocks can be parametrized, so to speak.
They can be sort of customized, not unlike HTML yesterday with attributes,
where those attributes kind of customize the behavior of a tag.
Similarly here, can I grab this touching block and change and ask the question,
are you touching the mouse pointer like the cursor
or are you touching the edge?
>> So let me go in and do this.
I'm going to zoom out for a moment.
Let me grab this puzzle piece here, this puzzle piece this,
and I'm going to jumble them up for just a moment.
I'm going to move this, change this to touching edge,
and I'm going to motion do this.
So here are some ingredients.
I think I've got everything I want.
>> Would someone like to propose how I can connect these maybe top to bottom
in order to solve the problem of having Scratch move right to left to right to
left to right to left, each time just bouncing off the wall?
What do I want to do?
Which block should I connect to the "when green flag clicked first"?
>> OK, so let's start with the "forever."
What goes inside next?
Someone else.
OK, move steps.
All right.
Then what?
So then the if.
And notice, even though it looks sandwiched together tightly,
it will just grow to fill.
It will just jump in where I want it.
>> And what do I put between the if and the then?
Probably "if touching edge."
And notice, again, it's too big for it, but it will grow to fill.
And then turn 15 degrees?
How many degrees?
Yeah, so 180 will spin me all the way around.
So let's see if I got this right.
Let me zoom out.
>> Let me drag Scratch up.
So he's a little distorted now, but that's fine.
How can I reset him easily?
I'm going to cheat slightly.
So I'm adding another block, just to be clear.
I want him to point 90 degrees to the right by default,
so I'm just going to tell him to do that programmatically.
And here we go.
We seem to have done it.
It's a little weird, because he's walking upside down.
Let's call that a bug.
That's a mistake.
A bug is a mistake in a program, a logical error that I, the human, made.
Why is he going upside down?
Did MIT screw up or did I?
>> Yeah, I mean, it's not MIT's fault. They gave me a puzzle piece
that says turn some number of degrees.
And at Victoria's suggestion, I'm turning 180 degrees,
which is the right intuition.
But turning 180 degrees literally means turning 180 degrees,
and that's not really what I want, apparently.
Because at least he's in this two-dimensional world,
so turning is really going to flip him upside down.
>> I probably want to use what block instead, based on what you see here?
How might we fix this?
Yeah, so we could point in the opposite direction.
And actually even that's not going to be enough,
because we can only hard code to pointing left or right.
>> You know what we could do?
It looks like we have a convenience block here.
If I zoom in, see something we like here?
So it looks like MIT has an abstraction built in here.
This block seems to be equivalent to which other blocks, plural?
>> This one block seems to be equivalent to this whole trio of blocks
that we have here.
So it turns out I can simplify my program by getting rid of all of that
and just put this in here.
And now he's still a little buggy, and that's fine for now.
We'll leave that be.
But my program is even simpler, and this, too,
would be representative of a goal in programming--
is to ideally make your code as simple, as compact as possible,
while still being as readable as possible.
You don't want to make it so succinct that it's hard to understand.
>> But notice I've replaced three blocks with one,
and that's arguably a good thing.
I've abstracted away the notion of checking whether you're
on the edge with just one block.
Now we can have fun with this, in fact.
This doesn't add so much intellectual value but playful value.
I'm going to go ahead and grab this sound here.
So let me go ahead, and let me stop the program for a moment.
I'm going to record the following, allowing access to my microphone.
>> Here we go.
Ouch.
Let's try this again.
Here we go.
OK, I recorded the wrong thing.
Here we go.
Ouch.
All right.
Now I need to get rid of that.
All right.
>> So now I have a recording of just "ouch."
So now I'm going to go ahead and call this "ouch."
I'm going to go back to my scripts, and now
notice there's this block that's called play sound "meow" or play sound "ouch."
I'm going to drag this, and where should I put this for comical effect?
Yeah, so now it's kind of buggy, because now this block--
notice how this "if on edge, bounce" is kind of self-contained.
So I need to fix this.
Let me go ahead and do this.
Let me get rid of this and go back to our original, more deliberate
functionality.
So "if touching edge, then" I want to turn, as Victoria proposed,
180 degrees.
And do I want to play the sound "ouch" there?
>> Yeah, notice it's outside that yellow block.
So this, too, would be a bug, but I've noticed it.
So I'm going to drag it up here, and notice now it's inside the "if."
So the "if" is this sort of like arm-like blot
that's only going to do what's inside of it.
So now if I zoom out at the risk of annoying--
>> COMPUTER: Ouch, ouch, ouch.
>> DAVID MALAN: And it will just go on forever.
Now just to accelerate things here, let me go ahead and open up,
let's say-- let me go to some of my own stuff from class.
And let me open up, let's say, this one made by one of our teaching fellows
a couple of years ago.
So some of you might recall this game from yesteryear,
and it's actually remarkable.
Even though we've done the simplest of programs right now,
let's consider what this actually looks like.
Let me hit play.
>> So in this game, we have a frog, and using the arrow keys--
he takes bigger steps than I remember-- I have control over this frog.
And the goal is to get across the busy road without running into the cars.
And let's see-- if I go up here, I have to wait for a log to scroll by.
This feels like a bug.
This is kind of a bug.
All right.
I'm on this here, there, and then you keep
going until you get all the frogs to the lily pads.
Now this might look all the more complex,
but let's try to break this down mentally
and verbally into its component blocks.
So there's probably a puzzle piece that we haven't seen yet
but that's responding to keystrokes, to things I hit on the keyboard.
>> So there's probably some kind of block that says, if key equals up,
then do something with Scratch-- maybe move it 10 steps this way.
If down key is pressed, move 10 steps this way, or left key, move 10 steps
this way, 10 steps that.
I've clearly turned the cat into a frog.
So that's just where the costume, as Scratch calls it-- we
just imported a picture of the frog.
>> But what else is happening?
What other lines of code, what other puzzle pieces
did Blake, our teaching fellow, use in this program, apparently?
What's making everything move-- what programming construct?
>> Motion, sure-- so the move block, for sure.
And what's that move block inside of, most likely?
Yeah, some kind of loop, maybe a forever block, maybe a repeat block--
repeat until block.
And that's what's making the logs and the lily pads and everything else move
back and forth.
It's just happening endlessly.
>> Why are some of the cars moving faster than the others?
What is different about those programs?
Yeah, probably some of them are taking more steps at once and some of them
fewer steps at once.
And the visual effect is fast versus slow.
>> What do you think happened?
When I got my frog all the way across the street and the river
onto the lily pad, something noteworthy happened.
What happened as soon as I did that?
It stopped.
That frog stopped, and I got a second frog.
So what construct must be used there, what feature?
>> Yeah, so there's some kind of "if" condition up there, too.
And it turns out-- we didn't see this-- but there's other blocks in there that
can say, if you are touching another thing on the screen,
if you're touching the lily pad, "then."
And then that's when we make the second frog appear.
So even though this game is certainly very dated, even though at first glance
there's so much going on-- and Blake did not whip this up in two minutes,
it probably took him several hours to create this game
based on his memory or videos of yesteryear's version of it.
But all of these little things going on the screen in isolation
boil down to these very simple constructs-- movements or statements
like we've discussed, loops and conditions, and that's about it.
There's a few other fancier features.
Some of them are purely aesthetic or acoustic,
like the sounds I just played with.
But for the most part, you have in this language, Scratch,
all of the fundamental building blocks that you
have in C, Java, JavaScript, PHP, Ruby, Python,
and any number of other languages.
Any questions about Scratch?
All right.
So we won't dive in deeper to Scratch, though you're welcome this weekend,
especially if you have kids or nieces and nephews and such,
to introduce them to Scratch.
It's actually a wonderfully playful environment with, as its authors say,
very high ceilings.
Even though we started with very low-level details,
you can really do quite a bit with it, and this is perhaps
a demonstration of exactly that.
>> But let's now transition to some more sophisticated problems, if you will,
known as "searching" and "sorting," more generally.
We had this phone book earlier-- here's another one just for discussion--
that we were able to search more efficiently because
of a significant assumption.
And just to be clear, what assumption was I making
when searching through this phone book?
That Mike Smith was in the phone book, though I
would be able to handle the scenario without him
there if I just stopped prematurely.
The book is alphabetical.
And that's a very generous assumption, because that
means someone-- I'm kind of cutting a corner,
like I am faster because someone else did a lot of hard work for me.
>> But what if the phone book were unsorted?
Maybe Verizon got lazy, just threw everyone's names and numbers in there
maybe in the order in which they signed up for phone service.
And how much time does it take me to find someone like Mike Smith?
1,000 page phone book-- how many pages do I have to look through?
>> All of them.
You're sort of out of luck.
You literally have to look at every page if the phone book is just
randomly sorted.
You might get lucky and find Mike on the very first page, because he
was the first customer to order phone service.
But he might have been the last, too.
>> So random order is not good.
So suppose we have to sort the phone book or in general sort data
that we've been given.
How can we do that?
>> Well, let me just try a simple example here.
Let me go ahead and toss a few numbers on the board.
Suppose the numbers we have are, let's say, four, two, one, and three.
And, Ben, sort these numbers for us.
>> OK, good.
How did you do that?
All right.
So start with the smallest value and the highest,
and that's really good intuition.
And realize that we humans are actually pretty
good at solving problems like this, at least
when the data is relatively small.
As soon as you start to have hundreds of numbers, thousands of numbers,
millions of numbers, Ben probably couldn't do it quite that fast,
assuming that there were gaps in the numbers.
Pretty easy to count to a million otherwise, just time consuming.
>> So the algorithm it sounds like Ben used just now
was search for the smallest number.
So even though we humans can take in a lot of information visually,
a computer is actually a little more limited.
The computer can only look at one byte at a time
or maybe four bytes at a time-- these days maybe 8 bytes at a time--
but a very small number of bytes at a given time.
>> So given that we really have four separate values here--
and you can think of Ben as having blinders on if he were a computer such
that he can't see anything other than one number at a time--
so we generally will assume, like in English, we'll read from right to left.
So the first number Ben probably looked at was four and then very quickly
realized that's a pretty big number-- let me keep looking.
>> There's two.
Wait a minute.
Two is smaller than four.
I'm going to remember.
Two is now the smallest.
Now one-- that's even better.
That's even smaller.
I'm going to forget about two and just remember one now.
>> And could he stop looking?
Well, he could based on this information,
but he'd better search the rest of the list.
Because what if zero were in the list?
What if negative one were in the list?
He only knows that his answer is correct if he's exhaustively
checked the whole list.
So we look at the rest of this.
Three-- that was a waste of time.
Got unlucky, but I was still correct to do so.
And so now he presumably selected the smallest number
and just put it at the beginning of the list, as I'll do here.
Now what did you do next, even though you didn't think about it nearly
to this extent?
Repeat the process, so some kind of loop.
There's a familiar idea.
So here is four.
That's currently the smallest.
That's a candidate.
Not anymore.
Now I've seen two.
That's the next smallest element.
Three-- that's not smaller, so now Ben can pluck out the two.
>> And now we repeat the process, and of course three gets pulled out next.
Repeat the process.
Four gets pulled out.
And now we're out of numbers, so the list must be sorted.
>> And indeed, this is a formal algorithm.
A computer scientist would call this "selection sort,"
the idea being sort a list iteratively-- again
and again and again selecting the smallest number.
And what's nice about it is it's just so darn intuitive.
It's so simple.
And you can repeat the same operation again and again.
It's simple.
>> In this case it was fast, but how long does it actually take?
Let's make it seem and feel a little more tedious.
So one, two, three, four, five six, seven, eight, nine, 10, 11, 12, 13, 14,
15, 16-- arbitrary number.
I just wanted more this time than just the four.
So if I've got a whole bunch of numbers now-- it
doesn't even matter what they are-- let's
think about what this algorithm really is like.
>> Suppose there are numbers there.
Again, doesn't matter what they are, but they're random.
I am applying Ben's algorithm.
I need to select the smallest number.
What do I do?
And I'm going to physically do it this time to act it out.
Looking, looking, looking, looking, looking.
Only by the time I get to the end of the list can
I realize the smallest number was two this time.
One's not in the list.
So I put down two.
>> What do I do next?
Looking, looking, looking, looking.
Now I found the number seven, because there's gaps in these numbers--
but just arbitrary.
All right.
So now I can put down seven.
Looking looking, looking.
>> Now I'm assuming, of course, that Ben doesn't
have extra RAM, extra memory, because, of course,
I'm looking at the same number.
Surely I could have remembered all of those numbers,
and that's absolutely true.
But if Ben remembers all of the numbers he's seen,
he hasn't really made fundamental progress
because he already has the ability to search
through the numbers on the board.
Remembering all of the numbers doesn't help,
because he can still as a computer only look at, we've said, one number
at a time.
So there's no sort of cheat there that you can leverage.
>> So in reality, as I keep searching the list,
I literally have to just keep going back and forth through it, plucking out
the next smallest number.
And as you can kind of infer from my silly movements,
this just gets very tedious very quickly,
and I seem to be going back and forth, back and forth quite a bit.
Now to be fair, I don't have to go quite as, well, let's see-- to be fair,
I don't have to walk quite as many steps each time.
Because, of course, as I select numbers from the list,
the remaining list is getting shorter.
>> And so let's think about how many steps I'm actually
traipsing through each time.
In the very first situation we had 16 numbers,
and so maximally-- let's just do this for a discussion--
I had to look through 16 numbers to find the smallest.
But once I plucked out the smallest number, how
long was the remaining list, of course?
Just 15.
So how many numbers did Ben or I have to look through the second time around?
15, just to go and find the smallest.
But now, of course, the list is, too, smaller than it was before.
So how many steps did I have to take the next time?
14 and then 13 and then 12, plus dot, dot, dot, until I'm left with just one.
So now a computer scientist would ask, well, what does that all equal?
It actually equals some concrete number that we could certainly
do arithmetically, but we want to talk about the efficiency of algorithms
a little more formulaically, independent of how long the list is.
>> And so you know what?
This is 16, but like I said before, let's just call the size of the problem
n, where n is some number.
Maybe it's 16, maybe it's three, maybe it's a million.
I don't know.
I don't care.
What I really want is a formula that I can
use to compare this algorithm against other algorithms
that someone might claim are better or worse.
>> So it turns out, and I only know this from grade school,
that this actually works out to the same thing as n over n plus one over two.
And this happens to equal, of course, n squared plus n over two.
So if I wanted a formula for how many steps
were involved in looking at all of those numbers again and again
and again and again, I would say it's n squared plus n over two.
But you know what?
This just looks messy.
I just really want a general sense of things.
And you might recall from high school that there
is the notion of highest order term.
Which of these terms, the n squared, the n, or the half,
has the most impact over time?
The bigger n gets, which of these matters the most?
>> In other words, if I plug in a million, n squared
is going to be most likely the dominating factor,
because a million times itself is a lot bigger
than plus one additional million.
So you know what?
This is such a darn big number if you square a number.
This doesn't really matter.
We're just going cross that out and forget about it.
And so a computer scientist would say that the efficiency of this algorithm
is on the order of n squared-- I mean truly an approximation.
It is sort of roughly n squared.
Over time, the bigger and bigger n gets, this
is a good estimation for what the efficiency or lack of efficiency
of this algorithm actually is.
And I derive that, of course, from actually doing the math.
But now I'm just waving my hands, because I just
want a general sense of this algorithm.
>> So using the same logic, meanwhile, let's consider another algorithm
we already looked at-- linear search.
When I was searching for the phone book--
not sorting it, searching through the phone book--
we kept saying that it was 1,000 steps, or 500 steps.
But let's generalize that.
If there's n pages in the phone book, what's
the running time or the efficiency of linear search?
It's on the order of how many steps to find
Mike Smith using linear search, the first algorithm, or even the second?
>> In the worst case, Mike is at the end of the book.
So if the phone book has 1,000 pages, we said last time, in the worst case,
it might take roughly how many pages to find Mike?
Like 1,000.
It's an upper bound.
It's a worst possible situation.
But again, we're moving away from numbers like 1,000 now.
It's just n.
>> So what's the logical conclusion?
Finding Mike in a phone book that has n pages
might take, in the very worst case, how many steps on the order of n?
And indeed a computer scientist would say
that the running time, or the performance or the efficiency
or inefficiency, of an algorithm like a linear search is on the order of n.
And we can apply the same logic of crossing something out
as I just did to the second algorithm we had with the phone book,
where we went two pages at a time.
>> So 1,000 page phone book might take us 500 page turns, plus one
if we double back a bit.
So if a phone book has n pages, but we're doing two pages at a time,
that's roughly what?
N over two, so that's like n over two.
But I made the claim a moment ago that n over two--
that's kind of the same as just n.
It's just a constant factor, computer scientists would say.
Let's only focus on the variables, really--
the biggest variables in the equation.
>> So linear search, whether done one page at a time or two pages at a time,
is sort of fundamentally the same.
It's still on the order of n.
But I claimed with my picture earlier that the third algorithm was not
linear.
It was not a straight line.
It was that curved line, and the algebraic formula there was what?
Log of n-- so log base two of n.
And we don't have to go into too much detail on logarithms today,
but most computer scientists wouldn't even tell you what the base is.
Because it's all just constant factors, so to speak,
just slight numeric differences.
And so this would be a very common way for particularly formal computer
scientists at a board or programmers at a white board
actually arguing which algorithm they would use
or what the efficiency of their algorithm is.
>> And this isn't necessarily something you discuss in any great detail,
but a good programmer is someone who has a solid, formal background.
He's able to speak to you in this kind of way
and actually make qualitative arguments as
to why one algorithm or one piece of software
is superior in some way to another.
Because you could certainly just run one person's program
and count the number of seconds it takes to sort some numbers,
and you can run some other person's program
and count the number of seconds it takes.
But this is a more general way that you can use to analyze algorithms,
if you will, just on paper or just verbally.
Without even running it, without even trying sample inputs,
you can just reason through it.
And so with hiring a developer or if having him or her sort of argue to you
why their algorithm, their secret sauce for searching billions
of web pages for your company is better, these
are the kinds of arguments they should ideally be able to make.
Or at least these are the kinds of things
that would come up in discussion, at least in a very formal discussion.
All right.
So Ben proposed something called selection sort.
But I'm going to propose that there's other ways of doing this, too.
What I didn't really like about Ben's algorithm
is that he kept walking, or having me walk, back and forth
and back and forth and back and forth.
What if instead I were to do something like these numbers here
and I were to just deal with each number in turn as I'm given it?
>> In other words, here's my list of numbers.
Four, one, three, two.
And I'm going to do the following.
I'm going to insert the numbers where they belong rather
than selecting them one at a time.
In other words, here's the number four.
>> Here's my original list.
And I'm going to maintain essentially a new list here.
So this is the old list.
This is the new list.
I see the number four first.
My new list is initially empty, so it is trivially the case
that four is now assorted list.
I'm just taking the number I'm given, and I'm putting it in my new list.
>> Is this new list sorted?
Yeah.
It's stupid because there's just one element, but it's absolutely sorted.
There's nothing out of place.
It's more interesting, this algorithm, when I move to the next step.
>> Now I have one.
So one, of course, belongs at the beginning or the end of this new list?
The beginning.
So I have to do some work now.
I've been taking some liberties with my marker
by just drawing things where I want them,
but that's not really accurate in a computer.
A computer, as we know, has RAM, or Random Access Memory,
and that's one byte and another byte and another byte.
And if you have a gigabyte of RAM, you have a billion bytes,
but they're physically in one location.
You can't just move stuff around by drawing it on the board
wherever you want.
So if my new list has four locations in memory,
unfortunately the four is already in the wrong place.
>> So to insert the number one I can't just draw it here.
This memory location doesn't exist.
That would be cheating, and I have been cheating pictorially for a few minutes
here.
So really, if I want to put one here, I have to temporarily copy the four
and then put the one there.
>> That's fine, that's correct, that's technically possible,
but realize that's extra work.
I didn't just put the number in place.
I first had to move a number, then put it in place,
so I kind of doubled my amount of work.
So keep that in mind.
>> But I'm now done with this element.
Now I want to grab the number three.
Where, of course, does it belong?
In between.
I can't cheat anymore and just put it there,
because, again, this memory is in physical locations.
So I have to copy the four and put the three over here.
Not a big deal.
It's just one extra step again-- feels very inexpensive.
>> But now I move on to the two.
The two, of course, belongs here.
Now you start to see how the work can pile up.
Now what do I have to do?
Yeah, I have to move the four, I then have to copy the three,
and now I can insert the two.
And the catch with this algorithm, interestingly enough,
is that suppose we have a more extreme case where it's let's say eight, seven,
six, five, four, three, two, one.
This is, in many contexts, the worst case scenario,
because the darn thing is literally backwards.
>> It doesn't really affect Ben's algorithm,
because in Ben's selection sort he's going to keep
going back and forth through the list.
And because he was always looking through the whole remaining list,
it doesn't matter where the elements are.
But in this case with my inserting approach-- let's try this.
>> So one, two, three, four, five, six, seven, eight.
One, two, three, four, five, six, seven, eight.
I'm going to take the eight, and where do I put it?
Well, at the beginning of my list, because this new list is sorted.
And I cross it out.
>> Where do I put the seven?
Darn it.
It needs to go there, so I have to do some copying.
And now the seven goes here.
Now I move on to the six.
Now it's even more work.
>> Eight has to go here.
Seven has to go here.
Now the six can go here.
Now I grab the five.
Now the eight has to go here, seven has to go here,
six has to go here, and now the five and repeat.
And I'm pretty much moving it constantly.
>> So at the end, this algorithm-- we'll call it insertion sort-- actually
has a lot of work, too.
It's just different kind of work than Ben's.
Ben's work had me going back and forth all the time,
selecting the next smallest element again and again.
So it was this very visual kind of work.
>> This other algorithm, which is still correct-- it will get the job done--
just changes the amount of work.
It looks like initially you're saving, because you're just
dealing with each element up front without walking all
the way through the list like Ben was.
But the problem is, especially in these crazy cases where it's all backwards,
you're just kind of postponing the hard work
until you have to fix your mistakes.
>> And so if you can imagine this eight and seven and six and five
and later four and three and two moving their way through the list,
we've just changed the type of work we're doing.
Instead of doing it at the beginning of my iteration,
I'm just doing it at the end of every iteration.
So it turns out that this algorithm, too, generally called insertion sort,
is also on the order of n squared.
It's actually no better, no better at all.
>> However, there's a third approach I would encourage us to consider,
which is this.
So suppose my list, for simplicity again, is four, one, three,
two-- just four numbers.
Ben had good intuition, good human intuition
before, by which we fixed the whole list eventually-- insertion sort.
I coaxed us along.
But let's consider the simplest way to fix this list.
>> This list is not sorted.
Why?
In English, explain why it's not actually sorted.
What does it mean not to be sorted?
>> STUDENT: It's not sequential.
>> DAVID MALAN: Not sequential.
Give me an example.
>> STUDENT: Put them in order.
>> DAVID MALAN: OK.
Give me a more specific example.
>> STUDENT: Ascending order.
DAVID MALAN: Not ascending order.
Be more precise.
I don't know what you mean by ascending.
What's wrong?
>> STUDENT: The smallest of the numbers is not in the first space.
>> DAVID MALAN: Smallest number's not in the first space.
Be more specific.
I'm starting to catch on.
We're counting, but what's out of order here?
>> STUDENT: Numerical sequence.
DAVID MALAN: Numerical sequence.
Everyone's kind of keeping it here-- very high level.
Just literally tell me what's wrong like a five-year-old might.
>> STUDENT: Plus one.
>> DAVID MALAN: What's that?
>> STUDENT: Plus one.
>> DAVID MALAN: What do you mean plus one?
Give me a different five-year-old.
What's wrong, mom?
What's wrong, dad?
What do you mean this isn't sorted?
>> STUDENT: It's not the right place.
>> DAVID MALAN: What's not in the right place?
>> STUDENT: Four.
DAVID MALAN: OK, good.
So four is not where it should be.
In particular, is this right?
Four and one, the first two numbers I see.
Is this right?
No, they're out of order, right?
In fact, think now about a computer, too.
It can only look at maybe one, maybe two things at once--
and actually only one thing at a time, but it can at least
look at one thing then the next thing right next to it.
>> So are these in order?
Of course not.
So you know what?
Why don't we take baby steps fixing this problem
instead of doing these fancy algorithms like Ben, where
he's sort of fixing it by looping through the list
instead of doing what I did, where I just kind of fixed it as we go?
Let's just literally break down the notion of order-- numerical order,
call it whatever you want-- into these pairwise comparisons.
>> Four and one.
Is this the correct order?
So let's fix that.
One and four, and then we'll just copy that.
All right, good.
I fixed one and four.
Three and two?
No.
Let my words match my fingers.
Four and three?
>> It's not in order, so I'm going to do one, three, four, two.
OK, good.
Now four and two?
We need to fix this, too.
So one, three, two, four.
So is it sorted?
No, but is it closer to sorted?
>> It is, because we fixed this mistake, we fixed this mistake,
and we fixed this mistake.
So we fixed three mistakes arguably.
Still doesn't really look sorted, but it is objectively closer to sorted
because we fixed some of those mistakes.
>> Now what do I do next?
I kind of reached the end of the list.
I seemed to have fixed all the mistakes, but no.
Because in this case, some numbers might have bubbled up closer
to other numbers that are still out of order.
So let's do it again, and I'll just do it in place this time.
One and three?
It's fine.
Three and two?
Of course no, so let's change that.
So two, three.
Three and four?
And now let's just be particularly pedantic here.
Is it sorted?
You humans know it's sorted.
>> I should try again.
So Olivia is proposing I try again.
Why?
Because a computer doesn't have the luxury of our human eyes
of just glancing back-- OK, I'm done.
How does the computer determine that the list is now sorted?
Mechanically.
>> I should go through once more, and only if I
don't make/find any mistakes can I then conclude as the computer, yep,
we're good to go.
So one and two, two and three, three and four.
Now I can definitively say this is sorted, because I made no changes.
Now it would be a bug and just foolish if I, the computer,
asked those same questions again expecting different answers.
Shouldn't happen.
>> And so now the list is sorted.
Unfortunately, running time of this algorithm is also n squared.
Why?
Because you have n numbers, and in the worst case you have to move n numbers
n times because you have to keep going back to check and potentially fix
these numbers.
And we can do a more formal analysis, too.
>> So this is all to say we've taken three different approaches, one
of them immediately intuitive off the bat from Ben
to my suggested insertion sort to this one
where you kind of lose sight of the forest for the trees initially.
But then if you take a step back, voila, we've fixed the sorting notion.
So this is, dare say, a lower level perhaps
than some of those other algorithms, but let's
see if we can't visualize these by way of this.
>> So this is some nice software that someone
wrote using colorful bars that's going to do the following for us.
Each of these bars represents a number.
Taller the bar, the bigger the number, smaller the bar,
the smaller the number.
So ideally we want a nice pyramid where it starts small and gets big,
and that would mean that these bars are sorted.
So I'm going to go ahead and choose, for instance, Ben's algorithm
first-- selection sort.
>> And notice what it's doing.
The way they've chosen to visualize this algorithm
is that, just like I was walking through my list,
this program is walking through its list of numbers,
highlighting in pink each number that it's looking at.
And what's about to happen right now?
>> The smallest number that I or Ben found suddenly
gets moved to the beginning of the list.
And notice they did evict the number that was there,
and that's perfectly fine.
I didn't get into that level of detail.
But we need to put that number somewhere,
so we just moved it to the open spot that was created.
So I'm going to speed this up, because otherwise it
becomes very tedious quickly.
Animation speed-- there we go.
So now same principle I was applying, but you
can start to feel the algorithm, if you will, or see it a little more clearly.
And this algorithm has the effect of selecting the next smallest element,
so you're going to start to see it ramp up on the left.
And on each iteration, as I proposed, it does a little less work.
It doesn't have to go all the way back to the left end of the list,
because it already knows those are sorted.
So it kind of feels like it's accelerating, even though each step is
taking the same amount of time.
There's just fewer steps remaining.
And now you can kind of feel the algorithm cleaning up the end of it,
and indeed now it's sorted.
>> So insertion sort is all done.
I need to re-randomize the array.
And notice I can just keep randomizing it,
and we'll get an approximation of the same approach, insertion sort.
Let me slow it down to here.
Let's start that over.
Stop.
>> Let's skip four.
There we go.
Randomize they array.
And here we go-- insertion sort.
Play.
Notice that it's dealing with each element it encounters right away,
but if it belongs in the wrong place notice
all of the work that has to happen.
We have to keep shifting more and more elements to make room
for the one we want to put in place.
>> So we're focusing on the left end of the list only.
Notice we haven't even looked at-- we haven't highlighted in pink anything
to the right.
We're just dealing with the problems as we go,
but we're creating a lot of work for ourselves still.
And so if we speed this up now to go to completion,
it has a different feel to it indeed.
It's just focusing on the left end but doing a little more work as needed--
kind of smoothing things over, fixing things,
but dealing ultimately with each element one at a time
until we get to the-- well, we all know how this is going to end,
so it's a little underwhelming perhaps.
>> But the list in the end-- spoiler-- is going to be sorted.
So let's look at one last one.
We can't just skip now.
We're almost there.
Two to go, one to go.
And voila.
Excellent.
>> So now let's do one last one, re-randomizing with bubble sort.
And notice here, especially if I slow it down, this does keep swooping through.
But notice it just makes pairwise comparisons-- sort of local solutions.
But as soon as we get to the end of the list in pink,
what's going to have to happen again?
Yeah, it's going to have to start over, because it only
fixed pairwise mistakes.
And that might have revealed yet others.
And so if you speed this up, you'll see that, much as the name implies,
the smaller elements-- or rather, the larger elements-- are starting
to bubble up to the top, if you will.
And the smaller elements are starting to bubble down to the left.
And indeed, that's kind of the visual effect as well.
And so this will end up finishing in a very similar way, too.
>> We don't have to dwell on this particular one.
Let me open this now, too.
There's a few other sorting algorithms in the world, a few of which
are captured here.
And especially for learners who aren't necessarily visual or mathematical,
as we did before, we can also do this audially
if we associate a sound with this.
And just for fun, here's a few different algorithms,
and one of them in particular you're going to notice is called "merge sort."
>> It is actually a fundamentally better algorithm,
such that merge sort, one of the ones you're about to see,
is not order of n squared.
It's on the order of n times log of n, which is actually smaller and thus
faster than those other three.
And there's a couple other silly ones that we'll see.
>> So here we go with some sound.
This is insertion sort, so again it's just dealing with the elements
as they come.
This is bubble sort, so it's considering them pairs at a time.
And again, the biggest elements are bubbling up to the top.
>> Next up selection sort.
This is Ben's algorithm, where again he's selecting iteratively
the next smallest element.
And again, now you can really hear that it's speeding up but only in so far
as it's doing less and less work on each iteration.
This is the faster one, merge sort, which is sorting clusters of numbers
together and then combining them.
So look-- the left half is already sorted.
>> Now it's sorting the right half, and now it's going to combine them into one.
This is something called "Gnome sort."
And you can kind of see that it's going back and forth,
fixing work a little bit here and there before it proceeds to new work.
And that's it.
There's another sort, which is really just for academic purposes,
called "stupid sort," which takes your data, sorts it randomly,
and then checks if it is sorted.
And if it is not, it re-sorts it randomly, checks if it's sorted,
and if not repeats.
And in theory, probabilistically this will complete,
but after quite a bit of time.
It's not the most efficient of algorithms.
So any questions on those particular algorithms or anything
related there, too?
>> Well, let's now tease apart what all these lines are that I've been drawing
and what I'm assuming the computer can do underneath the hood.
I would argue that all of these numbers I keep drawing-- they need to get
stored somewhere in memory.
We'll get rid of this guy now, too.
>> So a piece of memory in a computer-- so RAM DIMM is
what we searched for yesterday, dual inline memory module-- looks like this.
And each of these little black chips is some number of bytes, typically.
And then the gold pins are like the wires that connect it to the computer,
and the green silicon board is just what keeps everything all together.
So what does this really mean?
If I kind of draw this same picture, let's suppose for simplicity
that this DIMM, dual inline memory module,
is one gigabyte of RAM, one gigabyte of memory, which is how many bytes total?
One gigabyte is how many bytes?
More than that.
1,124 is kilo, 1,000.
Mega is million.
Giga is a billion.
>> Am I lying?
Can we even read the label?
This is actually 128 gigabytes, so it's more.
But we'll pretend this is just one gigabyte.
So that means there's a billion bytes of memory available to me
or 8 billion bits, but we're going to talk in terms of bytes now,
moving forward.
>> So what that means is this is one byte, this is another byte,
this is another byte, and if we really wanted
to be specific we would have to draw a billion little squares.
But what does that mean?
Well, let me just zoom in on this picture.
If I've got something that looks like this now, that's four bytes.
>> And so I could put four numbers here.
One, two, three, four.
Or I could put four letters or symbols.
"Hey!" could go right there, because each of the letters,
we discussed earlier, could be represented
with eight bits or ASCII or a byte.
So in other words, you can put 8 billion things inside
of this one stick of memory.
Now what does it mean to put things back to back to back in memory like this?
This is what a programmer would call an "array."
In a computer program, you don't think about the underlying hardware, per se.
You just think of yourself as having access to a billion bytes total,
and you can anything you want with it.
But for convenience it's generally useful
to keep your memory right next to each other like this.
So if I zoom in on this-- because we're certainly not going
to draw a billion little squares-- let's suppose that this board represents
that stick of memory now.
And I'll just draw as many as my marker ends up giving me here.
So now we have a stick of memory on the board
that's got one, two, three, four, five, six, one, two, three, four, five, six,
seven-- so 42 bytes of memory on the screen total.
Thank you.
Yes, did my arithmetic right.
So 42 bytes of memory here.
So what does this actually mean?
Well, a computer programmer would actually generally
think of this memory as addressable.
In other words, every one of these locations in memory, in hardware,
has a unique address.
>> It's not as complex as One Brattle Square, Cambridge, Mass., 02138.
Instead, it's just a number.
This is byte number zero, this is one, this is two, this is three,
and this is 41.
Wait a minute.
I thought I said 42 a moment ago.
I started counting at zero, so that's actually correct.
Now we don't have to actually draw it as a grid, and if you draw it as a grid
I think things actually get a bit misleading.
What a programmer would, in his or her own mind,
generally think of this memory as is just like a tape,
like a piece of masking tape that just goes on and on forever
or until you run out of memory.
So a more common way to draw and just think about memory
would be that this is byte zero, one, two, three, and then dot, dot, dot.
And you have 42 such bytes total, even though physically it might actually
be something more like this.
>> So if you now think of your memory as this, just like a tape,
this is what a programmer again would call an array of memory.
And when you want to actually store something in a computer's memory,
you generally do store things back-to-back to back-to-back.
So we've been talking about numbers.
And when I wanted to solve problems like four, one, three, two,
even though I was just drawing only the numbers four, one, three,
two on the board, the computer would really have this setup in memory.
>> And what would be next to the two in the computer's memory?
Well, there's no answer to that.
We don't really know.
And so long as the computer doesn't need it,
it doesn't have to care what is next to the numbers it does care about.
And when I said earlier that a computer can only look at one address at a time,
this is kind of why.
>> Not unlike a record player and a reading head
only being able to look at a certain groove in a physical old-school record
at a time, similarly can a computer thanks
to its CPU and its Intel instruction set,
among whose instruction is read from memory
or save to memory-- a computer can only look
at one location at a time-- sometimes a combination of them,
but really just one location at a time.
So when we were doing these various algorithms,
I'm not just writing in a vacuum-- four, one, three, two.
Those numbers actually belong somewhere physical in memory.
So there are tiny little transistors or some kind
of electronics underneath the hood storing these values.
>> And in total, how many bits are involved right now, just to be clear?
So this is four bytes, or now it's 32 bits total.
So there are actually 32 zeros and ones composing these four things.
There's even more over here, but again we don't care about that.
>> So now let's ask another question using memory,
because that at the end of the day is in variance.
No matter what we might do with the computer, at the end of the day
the hardware is still the same underneath the hood.
How would I store a word in here?
Well, a word in a computer like "hey!" would be stored just like this.
And if you wanted a longer word, you can simply
overwrite that and say something like "hello" and store that here.
>> And so here, too, this contiguousness is actually an advantage,
because a computer can just read from right to left.
But here's a question.
In the context of this word, h-e-l-l-o, exclamation point,
how might the computer know where the word begins and where the word ends?
In the context of numbers, how does the computer
know how long the sequence of numbers is or where it starts?
Well, it turns out-- and we won't go too much
into this level of detail-- computers move stuff around in memory
literally by way of these addresses.
So in a computer, if you're writing code to store things
like words, what you're really doing is typing
expressions that remember where in the computer's memory these words are.
So let me do a very, very simple example.
>> I'm going to go ahead and open up a simple text program,
and I'm going to create a file called hello.c.
Most of this information we won't go into in great detail,
but I'm going to write a program in that same language,
C. This is far more intimidating, I would argue, than Scratch,
but it's very similar in spirit.
In fact, these curly braces-- you can kind of
think of what I just did as this.
>> Let's do this, actually.
When green flag clicked, do the following.
I want to print out "hello."
So this is now pseudocode.
I'm kind of blurring the lines.
In C, this language I'm talking about, this line print hello
actually becomes "printf" with some parentheses and a semi-colon.
>> But it's the exact same idea.
And this very user-friendly "when green flag clicked" becomes
the much more arcane "int main void."
And this really has no mapping, so I'm just going to ignore that.
But the curly braces are like the curved puzzle pieces like this.
>> So you can kind of guess.
Even if you've never programmed before, what does this program probably do?
Probably prints hello with an exclamation point.
>> So let's try that.
I'm going to save it.
And this is, again, a very old school environment.
I can't click, I can't drag.
I have to type commands.
So I want to run my program, so I might do this, like hello.c.
That's the file I ran.
But wait, I'm missing a step.
What did we say is a necessary step for a language like C?
I've just written source code, but what do I need?
Yeah, I need a compiler.
So on my Mac here, I have a program called GCC, GNU C compiler,
which allows me to do this-- turn my source code into, we'll call it,
machine code.
>> And I can see that, again, as follows, these
are the zeros and ones I just created from my source code,
all of the zeros and ones.
And if I want to run my program-- it happens
to be called a.out for historical reasons-- "hello."
I can run it again.
Hello, hello, hello.
And it seems to be working.
>> But that means somewhere in my computer's memory are the words
h-e-l-l-o, exclamation point.
And it turns out, just as an aside, what a computer would typically
do so that it knows where things start and end-- it's
going to put a special symbol here.
And the convention is to put the number zero at the end of a word
so that you know where it actually ends, so that you
don't keep printing out more and more characters than you actually intend.
>> But the takeaway here, even though this is fairly arcane,
is that it's ultimately relatively simple.
You were given sort of a tape, a blank space on which you can write letters.
You simply have to have a special symbol, like arbitrarily
the number zero, to put at the end of your words so that the computer knows,
oh, I should stop printing after I see the exclamation point.
Because the next thing there is an ASCII value of zero,
or the null character as someone would call it.
But there's kind of a problem here, and let's revert back
to numbers for a moment.
Suppose that I do, in fact, have an array of numbers,
and suppose that the program I'm writing is
like a grade book for a teacher and a teachers classroom.
And this program allows him or her to type in their students' scores
on quizzes.
And suppose that the student gets 100 on their first quiz, maybe
like an 80 on the next one, then a 75, then a 90 on the fourth quiz.
>> So at this point in the story, the array is of size four.
There's absolutely more memory in the computer, but the array, so to speak,
is of size four.
Suppose now that the teacher wants to assign a fifth quiz to the class.
Well, one of the things he or she is going to have to do
is now store an additional value here.
But if the array the teacher has created in this program is of size for,
one of the problem with an array is that you can't just keep adding to memory.
Because what if another part of the program has the word "hey" right there?
>> In other words, my memory can be used for anything in a program.
And if in advance I typed in, hey, I want to input four quiz scores,
they might go here and here.
And if you suddenly change your mind later and say I want a fifth quiz
score, you can't just put it wherever you want,
because what if this memory is being used
for something else-- some other program or some other feature of the program
that you're running?
So you have to think in advance how you want to store your data,
because now you've painted yourself into a digital corner.
>> So a teacher might instead say when writing a program
to store his or her grades, you know what?
I am going to request, when writing my program,
that I want zero, one, two, three, four, five, six, eight grades total.
So one, two, three, four, five, six, seven, eight.
The teacher can just over-allocate memory when writing his or her program
and say, you know what?
I'm never going to assign more than eight quizzes in a semester.
That's just crazy.
I'll never allocate that.
So that this way he or she has the flexibility to store student scores,
like 75, 90, and maybe one extra where the student got extra credit, 105.
>> But if the teacher never uses these three spaces,
there's an intuitive takeaway here.
He or she is just wasting space.
So in other words, there's this common tradeoff in programming
where you can either allocate exactly as much memory as you want,
the upside of which is that you're super efficient-- you're not being wasteful
at all-- but the downside of which is what if you change your mind when
using the program that you want to store more data than you originally intended.
>> So maybe the solution is, then, write your programs in such a way
that they use more memory than they actually need.
This way you're not going to run into that problem,
but you're being wasteful.
And the more memory your program uses, as we discussed yesterday, the less
memory that's available for other programs,
the sooner your computer might slow down because of virtual memory.
And so the ideal solution might be what?
>> Under-allocating seems bad.
Over-allocating seems bad.
So what might be a better solution?
Reallocating.
Be more dynamic.
Don't force yourself to choose a priori, at the beginning, what you want.
And certainly don't over-allocate, lest you be wasteful.
>> And so to achieve that goal, we need to throw this data structure,
so to speak, away.
And so what a programmer will typically use
is something called not an array but a linked list.
In other words, he or she will start to think of their memory
as being kind of a shape that they can draw in the following way.
If I want to store one number in a program-- so it's September,
I've given my students a quiz; I want to store the students' first quiz,
and they got a 100 on it-- I am going to ask my computer,
by way of the program I've written, for one chunk of memory.
And I'm going to store the number 100 in it, and that's it.
>> Then a few weeks later when I get my second quiz,
and it's time to type in that 90%, I am going
to ask the computer, hey, computer, can I have another chunk of memory?
It's going to give me this empty chunk of memory.
I'm going to put in the number 90, but in my program somehow or other--
and we won't worry about the syntax for this-- I need
to somehow chain these things together.
And I'll chain them together with what looks like an arrow here.
>> The third quiz that comes up, I'm going to say, hey, computer,
give me another chunk of memory.
And I'm going to put down whatever it was, like 75,
and I have to chain this together now somehow.
Fourth quiz comes along, and maybe that's toward the end of the semester.
And by that point my program might be using memory
all over the place, all over physically.
And so just for kicks, I'm going to draw this forth
quiz-- I forget what it was; I think maybe an 80 or something--
way over here.
>> But that's fine, because pictorially I'm going to draw this line.
In other words, in reality, in your computer's hardware,
the first score might end up here because it's
right at the start of the semester.
The next one might end up here because a bit of time has passed
and the program keeps running.
The next score, which was a 75, might be over here.
And the last score might be an 80, which is over here.
>> So in reality, physically, this might be what your computer's memory looks like.
But this is not a useful mental paradigm for a computer programmer.
Why should you care where the heck your data is ending up?
You just want to store data.
>> This is kind of like our discussion earlier of drawing the cube.
Why do you care what the angle is of the cube
and how you have to turn to draw it?
You just want a cube.
Similarly here, you just want to grade book.
You just want to think of this as a list of numbers.
Who cares how it's implemented in hardware?
>> So the abstraction now is this picture here.
This is a linked list, as a programmer would call it,
insofar as you have a list, obviously of numbers.
But it's linked pictorially by way of these arrows,
and all these arrows are-- underneath the hood, if you're curious,
recall that our physical hardware has addresses zero, one, two, three, four.
All these arrows are is like a map or directions, where if 90 is-- now
I got to count.
>> Zero, one, two, three, four, five, six, seven.
It looks like the 90 is at memory address number seven.
All these arrows are is like a little scrap of paper
that's giving directions to the program that says follow this map
to get to location seven.
And there you will find the student's second quiz score.
Meanwhile, the 75-- if I continue this, this is seven, eight, nine, 10, 11, 12,
13, 14, 15.
>> This other arrow just represents a map to memory location 15.
But again, the programmer generally does not care about this level of detail.
And in most every programming language today, the programmer
won't even know where in memory these numbers actually are.
All he or she has to care about is that they are somehow linked together
in a data structure like this.
>> But it turns out not to get too technical.
But just because we can perhaps afford to have this discussion here,
suppose that we revisit this issue here of an array.
Let's see if we regret going here.
This is 100, 90, 75, and 80.
>> Let me briefly make this claim.
This is an array, and again, the salient characteristic of an array
is that all of your data is back to back to back in memory-- literally
one byte or maybe four bytes, some fixed number of bytes away.
In a linked list, which we might draw like this, underneath the hood who
knows where that stuff is?
It doesn't even need to flow like this.
Some of the data could be back to the left up there.
You don't even know.
>> And so with an array, you have a feature known as random access.
And what random access means is that the computer can jump instantly
to any location in an array.
Why?
Because the computer knows that the first location is
zero, one, two, and three.
>> And so if you want to go from this element to the next element,
you literally, in the computer's mind, just add one.
If you want to go to the third element, just add one-- next element, just
add one.
However, in this version of the story, suppose
the computer is currently looking at or dealing with the number 100.
How do you get to the next grade in the grade book?
>> You have to take seven steps, which is arbitrary.
To get to the next one, you have to take another eight steps to get to 15.
In other words, it's not a constant gap between the numbers,
and so it just takes the computer more time is the point.
The computer has to search through memory in order
to find what you're looking for.
>> So whereas an array tends to be a fast data structure-- because you
can literally just do simple arithmetic and get where you want by adding one,
for instance-- a linked list, you sacrifice that feature.
You can't just go from first to second to third to fourth.
You have to follow the map.
You have to take more steps to get to those values, which
would seem to be adding a cost.
So we're paying a price, but what was the feature that Dan was seeking here?
What does a linked list apparently allow us to do,
which was the origin of this particular story?
>> Exactly.
A dynamic size to it.
We can add to this list.
We can even shrink the list, so that we're only using as much memory
as we actually want and so we're never over-allocating.
>> Now just to be really nit-picky, there's a hidden cost.
So you shouldn't just let me convince you that this is a compelling tradeoff.
There's another hidden cost here.
The benefit, to be clear, is that we get dynamism.
If I want another element, I can just draw it and put a number in there.
And then I can link it with a picture here,
whereas over here, again, if I've painted myself into a corner,
if something else is already using the memory here, I'm out of luck.
I've painted myself into the corner.
>> But what's the hidden cost in this picture?
It's not just the amount of time that it takes
to go from here to here, which is seven steps, then
eight steps, which is more than one.
What's another hidden cost?
Not just time.
Additional information is necessary to achieve this picture.
>> Yeah, that map, those little scraps of paper, as I keep describing them as.
These arrows-- those aren't free.
A computer-- you know what a computer has.
It has zeros and ones.
If you want to represent an arrow or a map or a number, you need some memory.
So the other price you pay for a linked list,
a common computer science resource, is also space.
>> And indeed so, so commonly, among the tradeoffs
in designing software engineering systems is time and space--
are two of your ingredients, two of your most costly ingredients.
This is costing me more time because I have to follow this map,
but it's also costing me more space because I have to keep this map around.
So the hope, as we've kind of discussed over yesterday and today,
is that the benefits will outweigh the costs.
>> But there's no obvious solution here.
Maybe it is better-- a la quick and dirty,
as Kareem proposed earlier-- to throw memory at the problem.
Just buy more memory, think less hard about solving the problem,
and solve it in an easier way.
And indeed earlier, when we talked about tradeoffs,
it wasn't space in the computer and time.
It was developer time, which is yet another resource.
>> So again, it's this balancing act trying to decide which of those things
are you willing to spend?
Which is the least expensive?
Which yields the better results?
Yeah?
>> Indeed.
In this case, if you're representing numbers in the maps--
these are called in many languages "pointers" or "addresses"--
it's double the space.
That needn't be as bad as double if right now we're just storing numbers.
Suppose that we were storing patient records in a hospital--
so Pierson's names, phone numbers, social security numbers, doctor
history.
This box might be much, much bigger, in which case
a tiny little pointer, the address of the next element-- it's not a big deal.
It's such a fringe cost it doesn't matter.
But in this case, yeah, it's a doubling.
Good question.
>> Let's talk about time a little more concretely.
What's the running time of searching this list?
Suppose I wanted to search through all the students' grades,
and there's n grades in this data structure.
Here, too, we can borrow the vocabulary of earlier.
This is a linear data structure.
>> Big O of n is what's required to get to the end of this data structure,
whereas-- and we haven't seen this before-- an array gives you
what's called constant time, which means one step or two steps or 10 steps--
doesn't matter.
It's a fixed number.
It has nothing to do with the size of the array.
And the reason for that, again, is random access.
The computer can just immediately jump to another location,
because they're all the same distance from everything else.
There is no thinking involved.
All right.
So if I can, let me try to paint two final pictures.
A very common one known as a hash table.
So to motivate this discussion, let me think about how to do this.
>> So how about this?
Suppose that the problem we want to solve now
is implementing in a dictionary-- so a whole bunch of English words
or whatever.
And the goal is to be able to answer questions of the form is this a word?
So you want to implement a spell checker, just
like a physical dictionary that you can look things up in.
Suppose I were to do this with an array.
I could do this.
>> And suppose the words are apple and banana and cantaloupe.
And I can't think of fruits that start with d, so we're just
going to have three fruits.
So this is an array, and we're storing all of these words
in this dictionary as an array.
The question, then, is how else could you store this information?
>> Well, I'm kind of cheating here, because each of these letters in the word
is really an individual byte.
So if I really wanted to be nit-picky, I should really
be dividing this up into much smaller chunks of memory,
and we could do exactly that.
But we're going to run into the same problem as before.
What if, as Merriam Webster or Oxford does every year-- they add words
to the dictionary-- we don't necessarily want to paint ourselves
into a corner with an array?
>> So instead, maybe a smarter approach is to put apple in its own node or box,
as we would say, banana, and then here we have cantaloupe.
And we string these things together.
So this is the array, and this is the linked list.
If you can't quite see, it just says "array," and this says "list."
>> So we have the same exact issues as before,
whereby we now have dynamism in our linked list.
But we have a fairly slow dictionary.
Suppose I want to look up a word.
It might take me big O of n steps, because the word might
be all the way at the end of the list, like cantaloupe.
And it turns out that in programming, sort
of the holy grail of data structures, is something
that gives you constant time like an array
but that still gives you dynamism.
>> So can we have the best of both worlds?
And indeed, there is something called the hash table
that allows you to do exactly that, albeit approximately.
A hash table is a fancier data structure that we
can think of as the combination of an array--
and I'm going to draw it like this-- and linked lists
that I'll draw like this over here.
>> And the way this thing works is as follows.
If this now-- hash table-- is my third data structure,
and I want to store words in this, I don't
want to just store all of the words back to back to back to back.
I want to leverage some piece of information
about the words that will let me get it where it's faster.
>> So given the words apple and banana and cantaloupe,
I deliberately chose those words.
Why?
What's sort of fundamentally different about the three?
What's the obvious?
They start with different letters.
>> So you know what?
Rather than put all my words in the same bucket, so to speak,
like in one big list, why don't I at least try an optimization
and make my lists 1/26 as long.
A compelling optimization might be why don't
I-- when inserting a word into this data structure,
into the computer's memory, why don't I put all the 'a' words here,
all the 'b' words here, and all the 'c' words here?
So this ends up putting an apple here, banana here, cantaloupe here,
and so forth.
>> And if I have an additional word like-- what's another?
Apple, banana, pear.
Anyone think of a fruit that starts with a, b, or c?
Blueberry-- perfect.
That is going to end up here.
And so we seem to have a marginally better solution,
because now if I want to search for apple, I
first-- I don't just dive into my data structure.
I don't dive into my computer's memory.
I first look at the first letter.
>> And this is what a computer scientist would say.
You hash into your data structure.
You take your input, which in this case is a word like apple.
You analyze it, looking at the first letter in this case,
thereby hashing it.
Hashing is a general term whereby you take something as input
and you produce some output.
And the output in that case is the location
you want to search, the first location, second location, third.
So the input is apple, the output is first.
The input is banana, the output should be second.
The input is cantaloupe, the output should be third.
The input is blueberry, the output should again be second.
And that's what helps you take shortcuts through your memory
in order to get to words or data more effectively.
>> Now this cuts down our time potentially by as much as one out of 26,
because if you assume that you have as many "a" words as "z"
words as "q" words, which isn't really realistic--
you're going to have skew across certain letters of the alphabet--
but this would be an incremental approach that does allow
you to get to words much more quickly.
And in reality, a sophisticated program, the Googles of the world,
the Facebooks of the world-- they would use a hash table
for a lot of different purposes.
But they wouldn't be so naive as to just look at the first letter
in apple or banana or pear or cantaloupe,
because as you can see these lists could still get long.
>> And so this might still be sort of linear-- so sort of slow,
like with the big O of n that we discussed earlier.
So what a real good hash table will do-- it will have a much bigger array.
And it will use a much more sophisticated hashing function,
so that it doesn't just look at the "a."
Maybe it looks at "a-p-p-l-e" and somehow converts those five letters
into the location where apple should be stored.
We're just naively using the letter 'a' alone, because it's nice and simple.
>> But a hash table, in the end, you can think
of as a combination of an array, each of which
has a linked list that ideally should be as short as possible.
And this is not an obvious solution.
In fact, much of the fine tuning that goes on underneath the hood when
implementing these kinds of sophisticated data structures
is what is the right length of the array?
What is the right hash function?
How do you store things in memory?
>> But realize how quickly this sort of discussion
escalated, either so far that it's kind of over one's head at this point, which
is fine.
But we started, recall, with truly something low-level and electronic.
And so this again is this theme of abstraction,
where once you start to take for granted, OK, I've got it-- there's
physical memory, OK, got it, every physical location has an address,
OK, I got it, I can represent those addresses as arrows--
you can very quickly start to have more sophisticated conversations that
in the end seem to be allowing us to solve problems like searching
and sorting more effectively.
And rest assured, too-- because I think this
is the deepest we've gone into some of these CS topics proper-- we've
done in a day and a half at this point what you might typically do over
the course of eight weeks in a semester.
>> Any questions on these?
No?
All right.
Well, why don't we pause there, start lunch a few minutes early,
resume in just about an hour?
And I'll linger for a bit with questions.
Then I'm going to have to go take a couple calls if that's OK.
I'll turn on some music in the meantime, but lunch should be around the corner.