[ Silence ]
>> Alright, welcome back to CS50.
This is the end of Week 3.
Couple of announcements, if you still need to make any changes
to your section please do so today.
You can email help@cs50.net otherwise follow the directions
that were in the email that the bot sent you this weekend with--
regarding your section assignments.
A few invitations, as well, so Zynga makers of Farmville
which may appear a little too often
in your Facebook walls is here today 6:30 p.m.
in a recruiting capacity in Maxwell Dworkin 119.
Maxwell Dworkin for those unfamiliar is the CS building
down the streets on the left, on Oxford Street.
It looks like there will be free food and free giveaways
and bring resumes and win an HP Mini Notebook.
So, that's 6:30 today.
For those of you looking for interns or full-time roles,
Brian Kernighan, is the man who thought me CS50 years ago.
He is a faculty at Princeton and he's here
on sabbatical this fall and he's actually gonna be giving a talk
tomorrow and giving out ice cream.
Tomorrow at 3:30 p.m. will be ice cream in Maxwell Dworkin
which is actually a weekly tradition over at the School
of Engineering followed by his talk
at 4 p.m. I remember this man,
frankly because his first lecture far out--
has far outshined mine.
He stood up on stage,
had apparently spent the summer growing a nice beard,
and then his algorithm was not putting on socks but was how
to shave using hedge clippers.
It's something that stays with you for some time.
But the talk he's giving on Thursday for those of interest
and realize, too, as if my being in 50 now is any indication,
he's very much adroit when it comes to speaking
to nontechnical or less technical audiences.
Do not fear we'll be over your head.
"The Changing Phase
of Programming" is his talk tomorrow.
The rapid evolution of languages, tools, environments,
and expectations presents major challenges and opportunities
for programmers and for software engineering education.
This is true across all kinds of programming
but is especially true for web systems
which are now routinely written in untyped scripting languages
and include Ajax, Mashups, toolkits, frameworks like Rails
and Django and a profusion
of interfaces all operating asynchronously
on distributed systems.
Few new pieces of jargon there
that we will touch upon towards semesters
and the growing popularity
of phone applications has not made life easier
for programmers or instructors.
For the past 10 years, I've been teaching a course
on advanced programming techniques that is more
and more stretched between important old material
and new unproven material that might be important.
In this talk I will illustrate some of the challenges
and discuss ways in which we might use complexity
and rapid change to advantage.
He's a wonderful man and a wonderful speaker to be honest.
So if you have some time tomorrow for a little ice cream
and talk, please do feel welcome to join.
And finally, Facebook.
Facebook is a social networking website.
[Laughter] They will be here on Monday in the form
of Thomas Carriero, who's one of CS50's former head TFs,
also in a recruiting capacity.
Lunch will be served.
For those unfamiliar or for those a little intrigued
by the opportunities that await in Mountain View,
Facebook is hiring brilliant engineers who want
to make an impact as we grow and shape the way the world connects
and shares with each other.
No one has ever done what we're trying to do at such speed
and scale on top of that we do it
with only about 500 engineers.
Our active user to engineer ratio is over one million users
to one engineer, and growing.
You won't be able to get that personal impact
in any other tech company in the world.
So if you'd like some lunch, if you'd like to reunite
with an alumnus and like to hear a bit more
about Facebook before class,
Monday 12 p.m. Maxwell Dworkin 1 not G119,
119 which is one floor up upstairs.
Alright, so we left off last time with a whole bunch
of pieces of paper on the wall and the challenges of the day,
were here's in a array and unfortunately was unsorted.
These were just semi random numbers in some random order
and the challenge at hand was find the number 50.
Now, a reasonable person as we--
as a reasonable person we might start at the left
and then move our array right word and you might start
to realize like this is a bit of a game
and jump ahead at some point.
But for the most part, you can't do much better than good luck
when it comes to searching an array of unsorted integers.
You might have some heuristics but again but at the end
of the day, if you don't know anything
about those numbers it really is just guess at work.
Now in fairness, it was deliberate on my part
that I put 50 all the way over here just
for demonstration's sake, but in the real world
that very much could happen and one of the themes today
in moving forward is gonna be this notion of worst cases,
worst possible inputs.
And in the worse possible case
in that small problem the thing I'm looking for is all the way
at the end which means I have to do a huge amount of work just
to find a single value.
Now thankfully there're approaches
that are more intelligent than that.
When we did this in the first day with the phonebook
and we did it last time with this second array of numbers
and the key difference there was that the second array
of numbers was sorted and this simple little detail was a
huge advantage.
Right, in the real world,
you can imagine the nightmare it would be
if Horizon just published a big book with numbers in the order
in which people signed up for telephone numbers,
right, from left to right.
Whether you have to search the whole damn phonebook
or at least half of it on average
to find some random friend whose number you're looking up.
Well same here.
If you don't know anything about the numbers,
you ultimately might have to check them all but not the case
if those numbers are actually sorted.
And so one of the questions we'll look at today is
if you are given a seemingly random sequence
of numbers not even certainly that large,
what are your options for actually sorting this?
Now, we'll use numbers because they're easy to talk about
but in the context of Facebook for instance,
you might wanna sort your friends.
You might wanna find friends of friends.
In the context of Google you might wanna search
or sort web pages so certainly could you apply what we'll look
at in this small context of numbers to really any type
of objects that you can impose some sorting on.
But first, some new tools for your toolkits,
thus far printf has probably been your primary tool
for debugging.
To debug a program means to find the bugs and remove them
or to chase down logical errors that you might have made
or even syntax errors that you might have made.
Now, if you've made a syntax error that is,
the characters you've typed at the keyboard just don't belong
where you put them, you put a semicolon in the wrong place,
you forgot a parenthesis.
Well, GCC nicely enough will just yell
at you before it even finishes compiling telling you I can't
compile this 'cause I don't know what you mean.
You've expressed yourself in an incorrect way.
But very often will you actually get your code to compile
and you'll be able to run it
and then you'll get segmentation fault,
which we've seen already it refers somehow to memory
and more on that next week as well.
You might just get the wrong output,
you might get the answer, you might get no answer
or whatsoever, and at this point your code yes compiles
but it's surely not correct and so you might go back
in as you have been and sorting printf statements here or there,
printing the value of this variable,
printing out what the user just wrote just
to do some sanity checks for yourself
and presumably you delete those printf statements before you
actually submit and call this program complete.
But this is a little bit hackish, right?
And its programs get longer than a few dozen lines,
a couple of hundred lines inserting printf statements all
over the place and then recompiling your code,
rerunning it, going back and changing the printf statements.
This really isn't the happiest workflow.
It doesn't scale very well and it's just not very interactive.
You have to kind of do-- make the change, compile, run.
Make the change, compile.
This is three steps just
to accomplish a relatively simple goal,
which is find my problem.
So thankfully, there exist tools.
And one we'll look at today is called GDB, the new debugger.
This is a program that you run
at the command line just like GCC itself.
But what happen is once you compile your program
with GCC you of course get your executable,
your binary the program like a.out or czar
or whatever the program is called.
What you do with GDB is you run GDB but pass it.
Your program is an argument and what GDB does
for you is essentially runs your program for you line by line
by line but slowly so that you can watch things happen step
by step and you can set what we'll call breakpoints which is
to say, if you only wanna see what's going
on at line 20 'cause you're pretty sure that's
where you're having some issues, you don't have to step
to the first 19 steps.
You can just say break at line 20, enter, then run the program.
It will run terribly fast and then pause at line 20 for you
to then poke around at what's going on inside the computer.
So it's gonna feel a little arcane at first.
In terms of interface, you'll find a nice cheat sheet
on CS50's website on the resources page.
But what I thought I'd do today and you'll see in sections
in the weeks to come are some new tricks of the trade
and to be honest with just a few commands
that I'll use myself here, you can get a lot done.
So I'm gonna go back in time to a program we used last week
which was called Buggy3.
As the name implied it was in fact buggy not
because it didn't compile or because there were syntax errors
but what was the problem
with this swapping program if you recall?
>> It didn't actually swap.
>> It didn't actually swap, right.
I claimed this swapped 2 numbers and yet we dug
in a little deeper, right?
I used a printf ad nauseam here
and it did actually swap those numbers when I added a printf
at the very bottom of my program here but then as soon
as the program-- as soon as swap the function returned--
just looking for my laser pointer,
as soon as swap returned it seemed all the hard work we have
done was for nothing and the values remained unchanged
in main.
Alright, so this is an approach that you might reasonably take
with printf, printing out every thing you wanna see line by line
and then as I did too, once I was done I deleted that line
from swap 'cause I don't want it printed out all over the place.
I just wanted it to print it out for debugging techniques.
Well, let's do this instead.
Let me go ahead and quit nano.
I'm gonna go ahead and make Buggy3.
And notice this.
There's a whole bunch of stuff that's been flashing
on the screen in the past few couple of weeks and some
of them we've talked a little bit about for instance -LCS50,
it's wrapping from over there.
That of course means link in CS50 library, -lm,
little sanity check is the math library.
>> So you can use functions like round
and a few others if you need them.
For those doing the hacker edition, -lcrypt means--
so use the crypt function.
So for those tackling the hacker edition, it involves cracking
or decrypting passwords
and there exist a function called crypt for that
and it is among other functions in a library called crypt.
Now, what's this other stuff?
Well, some of these things are flags, as we call them,
that have been configured by us.
We've pre-configured Make on the cloud for you.
And though you might resent us for this -Wall
or rather -Werror means even
if there's the slightest syntactical mistake
in this program or thing you really shouldn't do,
yell at the student and refuse to compile the code.
So, this is deliberate in that it really forces you
to get things perfectly right but there are some side effects.
Some of you might have gotten annoyed at the computer or at us
because you declare a variable X
and you're not quite ready to use it yet.
You're just, you know, you wanna use X
but you wanna write some more code first
and it won't let you even compile 'cause you're not using
X. Well again, this is a pedagogical tool
and it's also frankly a matter of good practice
because there's too much code out there,
too much code that's vulnerable out there that just hasn't been
as rigorously checked as this little configuration options
allow for.
Now, for today, we're taking--
making use of this guy over here, -ggdb is a flag
that we've been secretly including
and make all this time.
But what it does is I think I said a couple
of weeks ago is it adds to your program.
You're a.out, your czar, some additional bits
that re-help a program like GDB follow along where you are.
It includes things like line numbers essentially.
So that when you're walking
through what is otherwise just a file with 0s and 1s,
there're still some reminders inside your file as to
where those 0s and 1s came from.
What original line, so if you are still in a habit
of running GCC manually at the prompt, that's fine
but henceforth if you wanted to use GDB, you're gonna have
to include this flag as well manually.
So, we're all ready at the point frankly where you might
as well just be using Make 'cause it automates all of this
for you and saves you a whole lot of typing.
So now, I'm gonna go ahead and run the program itself
which is called Buggy3.
And of course, it seems to in fact be buggy.
And here are my printf statements that seemed
to be confirming that it is not in fact working.
And just to be clear, let me go back in nano Buggy3 and recall
that what we did last time was I did a little sanity check.
I said, printf A equals percent D, new line let's say,
comma A. So I wanna print out the value of A
and then I wanna print out the value of B.
So this was my sanity check.
So I'm gonna save, Enter, I'm gonna recompile with Make,
and I'm gonna re-run Buggy3,
and sure enough it seems to be working.
It starts off at 1-2, becomes 2-1,
but then reverses back to 1-2.
And this is how we concluded definitively.
This thing is not working as intended.
So let me remove these superfluous printf statements
'cause again, this isn't the best habit long term
to get into.
Let me recompile, so I have the freshest copy.
But now instead of running Buggy3,
I'm gonna run GDB space Buggy3 and then Enter.
You get a whole lot of stuff that's pretty useless,
just warrant the information and all this
but then you get a GDB prompt.
Alright, at the GDB prompt I get to do a few things,
among them run my program.
So one of the new tricks today, and again all this is documented
in a cheat sheet on CS50.net/resources.
I'm gonna hit Enter.
It apparently runs your program, so not all that useful yet.
I could've done this, you know, a second ago
at the original command line, but notice this as a teaser.
When a GDB tells you program exited normally,
it turns out that means that main returned what?
>> Zero.
>> Zero, right.
So as promised, returning 1 or 2 or 3 or 0 for success cases
in main thus have utility when you're using tools like this
so that you can actually see what's being returned
or be informed that it in fact all was well.
So this was not all that useful though, just running my program,
I wanna know what's wrong.
So I'm gonna go ahead and do this.
I'm gonna type break and then I'm gonna type main.
What' nice and let me move this up to the top,
I'm gonna type break main
and this step is what's called a breakpoint.
A pause point in the program at the function called main,
notice I get a slightly cryptic output
which is breakpoint number 1 is now at OX,
and what does this mean perhaps?
[ Inaudible Remark ]
>> Yes, so this is the address in memory.
So we'll talk more about this overtime.
Frankly, it's used for silly things, like photoshop,
colors, and web colors.
But hexadecimal notation is just another base system like binary
which we've discussed, decimal which we've grown up with,
0x typically denotes hexadecimal which is base 16,
and as we'll see this is just a more compact way
of representing numbers so that they don't get
ridiculously long.
So this just means in RAM, in my program's memory space,
in RAM lives a function called main, the so-called text segment
from last time but more on that to come.
And that is where it happens to live, is this relevant,
not so much for us just yet,
but as things get more advanced then we get more savvy,
certainly details like that can help.
But for us, it looks like we've set a breakpoint in this file
at line 21 'cause that's apparently where main began.
So now if I run and hit Enter,
notice that execution does break at line 21.
So again, the output is a little cryptic at first
but this is just telling me what happened.
This is saying, here's line 21, here's what's on line 21
but it hasn't executed line 21 yet.
In fact, it won't until I actually hit the command Next.
So I'm gonna go ahead and hit Next and now I'm on line 22,
X has already been assigned the value of 1 and which I confirm
by typing the command Print, so it is not printf or anything
like that, there's no parenthesis.
These are just commands in a program,
not functions, print X, Enter.
And in fact, X equals 1.
Now as this thing here,
the dollar-sign notation is just handy if you wanna get fancy
and refer back to the same answer later on, kinda of like
in a fancy graphing calculator allows you to do.
But for now, what we care about is that the answer is 1.
Meanwhile, if I type print Y-- well, that's weird.
How did Y become 3,223,540?
What-- 'Cause we haven't initialized it yet, right?
So this is 1 already.
A visual lesson that if you don't' initialize variables
in a program to something, who knows what they're gonna be.
This computer, the clouds have been on for several days time.
Even this program did some other stuff
when we first started it up, on--
but known to us or that we didn't see visually.
And surely the program might have used some
of the memory that's allocated to my program
for other purposes if temporarily.
But now Y happens to live at a certain location
and it just has this garbage value, a meaningless value
that I should absolutely not trust is anything legitimate
if I haven't assigned it a value explicitly
as I'm about to in line 22.
So even though I typed a few commands, I have not preceded
to continue executing this program.
We're still at line 22.
So now if type Next or if I'm getting a little lazy
with keystrokes, you can just type N, the first letter or two
of each command, N. Now I'm at line 24.
So now if I do print Y, I should hopefully see
in fact the answer is 2.
And again, ignore the dollar-sign stuff for now.
It's what's on the right hand side that's interesting.
Alright, so if I now type, oops, Next again,
this printf line is going to execute.
So I'm gonna see the programs output commingled with GDBs.
Alright, so there it is.
X is 1 on the left then I'm at line 25, let me go ahead
and I'm gonna scroll things up to the top
so you can see in front.
Let's type Next again, Y is 2, I claim in the moment
that we're swapping dot, dot, dot, so let's do Next.
Alright, so here's an interesting decision point.
This is a function call.
I am about to on line 27,
call the function Swap, which I wrote.
Remember it's lower in the file, called buggy3.c. I'm
about to call this function and so I can.
I'm gonna go ahead and do Next.
That function will execute.
Something will hopefully happen to X and Y, let's check.
Print X-- uh-oh, print Y, still nothing.
So that function seems in fact to have had no effect.
Now, this was not all that useful
in exercise 'cause now my program is pretty much done,
right?
I claimed swap, I then claimed
that X is something, Y is something.
I now hit this curly brace.
I hit Next again.
Now I'm this weird part of my world
because remember I've used other functions,
I've used printf and the like.
So don't get distracted
if you see stuff that's clearly not yours.
I know I'm at the end
of my program 'cause I already saw this curly brace pass me by.
So I'm just gonna go ahead and type continue
which undoes the effect of brake,
it just says, "Keep going.
Forget about this breakpoint.
I'm done caring.
And now, I'm in fact done with the program."
It finished up whatever leg work it needed to do at the end.
Alright, so this was not all that helpful.
All I did was very slowly discover what I'd already
discovered before with printf but here's the power
of something like GDB, let's redo this.
Let me rerun Run.
It's gonna automatically start at the beginning.
It still have that breakpoint, so I'm gonna hit again.
And now let me step through a little more quickly.
Next, with N, next, next, next, next.
Okay, here's an interesting point.
Now I wanna step into this function 'cause what's powerful
about a debugger is you can poke
around anywhere you want in your program.
So I'm gonna type a Step instead of Next.
Step means step into this function whereas Next means step
over this function while still executing it, Enter.
And now notice what I get as output.
I am being informed, okay, I am in the scope
as we've discussed of swap.
It was past these two arguments, A is 1, B is 2,
and the line I'm currently paused
at is line 41 of my program.
So here, too, it's helpful if you have two terminal
or two putty windows open, have your source code in one,
have GDB in the left hand one
and you can watch things progress in the big window.
So, let's see.
This is swap.
Actually I can also type List if you wanna see in the context
of GDB, what code you're currently dealing with,
with the line numbers on the left hand side,
but I'm on line 41 as this thing here says.
So this is uninteresting at the moment.
So let's do a quick check.
Print the value of temp and let me move it to the top.
I'm gonna print the value of temp, alright 0.
>> So it may be the case that just
by happened stance a variable seems to be initialized
to some value very often 0 but that's clearly not a guarantee.
So do not trust that.
So now let's go ahead and type Next, execute that line of code.
So now if I print temp, it should be--
if you recall I passed in 1 and 2 and I assigned it the value
of A. So in fact, yup, it's 1 here.
So a-- temp is currently 1.
Now I'm gonna clobber the value of B.
So let's do quick sanity check.
Print A, print B, and that's consistent with what I passed
in to swap, but here we go, we're about to execute line 42
and I'm gonna do this just by typing Next.
Next. Alright, so now I'm gonna do it again.
Print A, print B, and there it is.
So we are half way through the swapping process 'cause now A
and B happen to be the value of 2.
Now what can we do here?
Well, I can go ahead and just say, okay next, next,
I'm kinda losing interest in this and so as soon
as that function returns, notice it reminds me, I'm back in main,
I'm at line 28 and you're about to do this.
So in short, you have this power with just a few commands, Run,
Break, Next, Step, and Continue.
You can do a lot of useful things.
And there is yet more that we'll look at in this section
and is documented online.
But let me show you one last trick that's not terribly useful
for this program 'cause it's so short
but when we start writing programs that have multiple,
multiple, multiple functions that you wrote, that get called
in succession, watch what you can do.
I'm gonna hit Run and because it's not finished,
it's gonna yell at me start it from the beginning, that's fine.
I'm done with this iteration.
So, Y for Yes.
I'm at the top of my program, I broke in as usual.
I'm gonna go ahead and type Next, Next, and you can do up--
use the up arrows as before.
Next, I don't wanna take Next here.
I wanna hit Step to dive in.
And now suppose this is a reasonably sized program,
I'm actually getting disoriented with where I am,
what I've stepped in to and what not, that's fine.
You can do a little sanity check,
you can type the command back trace.
And as the name implies, it kind of looks back in time
at where you came from and what it says is this,
the place I am now is the first line.
I'm in frame 0.
So I'm in swap, I past in this variables, and that happens
to happen at this line.
Where did I come from?
In other words, how did I get to that line of code?
Well previously, in the other frame that is currently
in may RAM, I started in main.
So the reason this prints kind
of in reverse order is actually consistent
with that picture we drew on the board the other day.
When we talked about RAM having stacks and frames that grow
like this, it's the same idea.
Notice that main is on the bottom and swap is on top.
So if swap itself calls a third function,
it is gonna be located in RAM up here.
And so pictorially it's pretty consistent.
Okay, so a bit of world wind tour.
The next couple of problems that will encourage you and walk you
through the process of using this to the extent you need it--
but any questions on the usage, the concept, anything?
Yeah.
[ Inaudible Remark ]
>> Absolutely, you don't have to set breakpoints only at main
if you have a function called swap,
I could have typed the break swap.
Or if I again know that there's a certain line I care about,
I could even do this, break line, let's say 23,
'cause I care about line 23.
Then when I type Run, it will start running from the top
of the program as usual but stop at that specific line.
So it's actually quite versatile.
Yeah.
>> Can you break continue then break again?
>> Can you break and then continue again, yes.
So the-- yes.
The continue command is useful also in the context of loops.
Because if you set a breakpoint somewhere in the middle
of a loop, you might get bored with typing next, next, next,
next, next throughout all this lines, you really just wanna get
to the next iteration or the next iteration.
So if you type Continue, it's not gonna run to the bottom
of the program, it's gonna run
as the logic of your code suggest.
So it will iterate in this loop and if you hit
that same breakpoint again, you will in fact pause.
Now if you're iterating a hundred times and you only care
about the 99th iteration, this could very quickly get tedious.
But you'll see in the online PDF,
you can say like continue 98 times and then break.
So again, you pick up little tricks along the way.
Any other questions?
Yeah.
[ Inaudible Remark ]
>> So you can't start execution at a certain line.
Your program has start at the beginning
but you can break at any line.
And break just means pause here so I can poke around
and then it's up to you to decide
if you wanna continue execution
by hitting Next or Continue itself.
[ Inaudible Remark ]
>> No, so your-- if you wrote the code here, you're gonna have
to execute it from here to here.
You can't just say start running my program at a different point.
Alright, so that's a little tool for your toolkit, so to speak.
It might very well be useful for this P set if you're not
yet done or not yet started.
But for the next ones and ones moving forward,
it's one of this things honestly where statistically many
of you probably won't take this advice for at least a couple
of P sets but this is one of those things that certainly
in programing where if you spend
that frustrating first 30 minutes, maybe an hour
of learning something like this,
it will absolutely save you 10 times
that much time by semesters end.
But when you get comfortable with this stuff,
printf is not going to be your best friend
for very long 'cause it's so terribly limited
and so terribly tedious.
So invest this time, this week
or next just learning some of the basics of GDB.
And honestly, it's one of those things
that will absolutely help you help yourselves
and in the end save you time for sure.
So here are some numbers and the goal at hand is to get
to the point of actually having these numbers sorted
so that we can actually find pieces of data more efficiently.
Now again, I've chose some fairly simple numbers here
up on the board, you could imagine gaps in them like we had
on the chalk board on Monday
so that they're not just evenly spaced by 1 number apart
and you can certainly imagine each
of this things representing a web page or name
in the phonebook or anything that will lends itself
to actually being sorted.
But how do we go about sorting something like this?
Well, a human probably will just kind of scan the list and say,
alright, there is the number 1, let's move that, there's 2.
And we all have some kind
of intuition behind how you sort this numbers just
as a normal person probably already knows before taking
CS50, how to find someone
in the phonebook pretty intelligently, right.
Before this class, odds are you were not starting at the begging
and moving from left to right.
But how do we begin to now express what we
as humans consider to be intuition if not obvious
in a way that the computer can now understand
so that it can do our bidding using our own life lessons
but far more quickly than we could ourselves.
So if you don't mind, perhaps some fresh faces this time,
I have 8 pieces of paper and need another bite of volunteers.
If you'd hear me, come on up, 2, 3, no one ever wants
to come up from up here.
There you go, 4, 5, 6 and 7.
Let me see if I counted properly, 1, 2, 3, 4, 5, 6,
7 okay, good and 8 in the red.
Alright, so if you could, first part is easy.
And you have to be comfortable
on camera before you step on stage.
First part is easy, line yourselves up and let's say
over here, just so we have you all together in the same order
as the projectors indicating now.
Alright, thank you.
Alright, so line up if you could in this way.
[ Noise ]
>> And so that you are not anonymous, we wanna say,
who you are and one interesting thing
which might mean concentration house, sports, extracurricular,
whatever and just pass it down.
>> My name is Chi [phonetic], I wanna do CS.
>> Very nice.
>> May name is Mar [phonetic] and I'm in the best house
on campus, Eliot [phonetic] House.
[ Cheering ]
>> My name is Luis [phonetic], and I like yoghurt.
[ Laughter ]
>> My name is Daniel [phonetic] I also have the grand fortune
of being in Eliot House.
[ Cheering ]
>> Hi, my name is Aziza [phonetic]
and I'm in Eliot, too.
>> Hi, I'm Carl and I'm from Leverett.
[ Cheering ]
>> I'm Ron, freshman from Canada.
[ Cheering ]
>> I'm Ian, I'm on the Alpine ski team.
It's pretty fun.
>> Alright.
[Laughter] Alright, so, now you know these eight folks
and we have a couple of approaches
that we might take here.
So I'm gonna propose one and then see
if these eight can help me execute this method.
So as a human, I might take the step back and say, alright,
number 1, I'm gonna put you over here, number 2.
But don't do that just yet, right 'cause it's kinda--
there's this intuition that presumably all of us have
and we can sort this list in a couple of seconds.
Now ironically what we're
about to do is probably gonna take more than a few seconds.
But once this input gets larger than N equals A
and as N equals a million or a billion or the like,
surely some of this tricks will be again a leverage
to our advantage.
So, I'm actually gonna point out first.
If these folks are implemented in a computer,
they're probably implemented not as 8 variables, X1, X2,
X3 'cause we've already introduced arrays,
odds are they're just called number and that--
the size of this array numbers is probably 8 and each
of them is an int inside of this array.
But the catch is with the computer, I don't have this sort
of god-like ability to just look out on them all and see--
taking all of this numbers at once.
I have to be much more deliberate.
In an array, you can iterate from left to right,
from right to left, you can jump randomly by a random access
to any value inside the array by of the square bracket notation.
But you certainly can't see them all at once.
So just for visual's sake,
if you guys can just turn your papers
around so they're blank white on this side.
I mean this really is what the computer is handed.
There is 8 numbers, yes,
but I certainly can't take some aggregate view all at once.
I have to look more carefully.
So go ahead and flip back the normal way
and I'm gonna propose a very simple heuristic.
I'm gonna start at the beginning 'cause it's just easy to iterate
from left to right, I'm gonna look
at the first 2 elements, 0 and 1.
Index values, 0 and 1 and I see that the number 4 is
at location 0, and the number 2 is
at location 1, this is wrong, right.
>> The goal at hand is to sort this numbers
so you know what I'm gonna do,
the simplistic heuristic I can come
up with, I'm gonna say swap.
Now, go ahead and swap.
Now this took how many steps?
Well if we implemented this in code,
it's like at least 3 lines of code.
We need a temporary variable then we need
to clobber A then replace B and so forth.
Now in fairness, our swap function is a little
dysfunctional right now.
We have yet to see a working version
of swap but that's coming.
In fact we'll introduce that in something called pointers next
week that allows us to pass by reference
and not by value or by copy.
So let's take for granted today
that surely there's some solution to this problem
with swap, we just haven't done it ourselves yet.
So I swap these two guys and now what do I do?
Well, I don't have to look at them just yet in pair anymore,
I can advance one step, so I plus-plus.
Now 4 compared to 6 checks out.
I don't have to do a swap
so I can take another step, I plus-plus.
6 against 8, okay, plus-plus.
8 against 1, I need to do another swap.
So that'll take a few CPU cycles.
Now, you know, I could start backtracking
because clearly 1 should be going this way
but I'm gonna keep implementing the same approach, right.
You wouldn't change your code in the middle of a for loop,
it's gonna execute again and again in exactly the same way
so let's do the plus-plus.
8 and 3, alright, plus-plus.
8 and 7, plus-plus.
And 8 and 5, and now probably I do plus-plus.
My for loops condition are my wild condition, what it is,
realizes that I've gotten too big and so I reset
to the start of this list.
So it seems like I have a loop that's going this way, right,
so that's I plus-plus, I plus-plus, I plus-plus.
So I've looped through the whole array.
So that would seem to suggest I'm done.
I've looked at every value but obviously, no.
So just intuitively, how many more times am I gonna have
to come back to the end of this list much
like a typewriter going back
to the carriage return and go again.
If I do it once more, will it fix the problem?
>> No.
>> No, so maybe-- I feel like maybe 8 or so,
7 or 8 total times am I gonna have
to do this because why is that?
Well, intuitively, number 1 a moment ago was here.
But how far did she move down the list with just 1 step.
Now 8 made some pretty good progress so it seems
like there is some asymmetry in the benefits of this algorithm.
But again, anyone who is too small to be
on that N is only stepping one at a time.
It's but-- these small numbers like 1, number 3,
or bubbling up, if you will, pretty slowly
to this side whereas 8 is already in place.
So if that suggests in the worse case that 1 started over there,
let's say, well each iteration of this loop, plus, plus, plus,
plus, plus would number 1 just move 1 step which means I've got
to go back here, do it again, do it again, do it again as many
as 7 times or really N times.
N being 8, give or take to this again and again.
So let's do this once more
and this time I won't deliberately go
through all the verbiage,
let's see if you guys can execute now down the line.
So ready, this is iteration number 2.
[ Noise ]
>> Okay, now what do we do?
So I reset.
So it feels like if you're thinking this through,
I'm doing plus, plus, plus, plus, plus, plus,
then I'm going all the way back round,
it feels like we just have a nested loop.
You did this in scratch.
You might have done this in C already, maybe with visionaire
if you've already started that part.
And even visionaire can be done without a nested loop.
But it feels like a nested loop 'cause I'm looping again
and again and again and then I've got this bigger outer loop
that's bringing me back home after 8 or so steps.
Alright, let's go the third round.
Okay. Okay.
Okay and now, what do I do?
[ Inaudible Remark ]
>> Okay, so I go back to the beginning.
Alright, so hopefully we're almost there.
Now, can I stop?
Alright, so maybe intuitively,
you might think, yeah, it's right.
But again, you don't have that aggregate view.
The only way we're gonna know if we're done is
to keep checking pair wise, pair wise, pair wise, pair wise,
pair wise, now am I done?
So, visually yes, but on this iteration, I made a swap
and unless I've added some very sophisticated conditions
or checks all I know is I just made one swap.
So surely, if I made one swap, I might not be done because maybe
that number that I swapped has to bubble down even further.
So really the only way to this for sure is
to now do 1 additional pass and say, uh-hmm,
uh-hmm, uh-hmm, uh-hmm.
And now, maybe I have a counter, called counter.
And every time I do a swap, I increment this by 1, right.
And now, my counter is still just 0.
So now I'd be stupid frankly to go back to the beginning
and do this again, do this again, do this again.
So that then begs the question in total,
how many steps does this algorithm involve?
How much work does this algorithm involve?
Well in the best case, let's start with the easier one.
In the best case, this group of folks did not line up like that.
They lined up right like this.
In which case, how many steps does it take for me,
the computer, to sort N individuals.
>> One.
>> Eight.
[ Inaudible Remark ]
>> Okay, we have disagreement.
Everyone here says 1, and this guy says 8.
So which is it?
Well, it kinda boils down frankly to semantics.
What do we mean by step?
Do we mean one outer loop, maybe,
do we mean one individual, yeah, step maybe.
I'm gonna say-- minimally let's say 8.
Because let's literally count any line of code that I execute
or physically any step that I take.
So to know that all of this folks are sorted minimally,
I'm gonna have to check each pair keeping track
of how many swaps I do.
Still 0, now I can quit.
Even though I was in a loop,
some of you might have used a special instruction
in C called break that will break you out of a loop.
You might not have occasion to use this before but just
because you say a loop needs to iterate 8 times or N times,
you can break out if you want
if just this situation warrants at any point.
You could do this with scratch, too, with the stop all
or stop script block as well.
So now, what about the worse case?
Well, what was the worse case?
If you guys don't mind for the visual,
can you arrange yourselves in the worse possible case?
The worse case in not random, right?
Actually, worse case for our purpose is, is the most amount
of work that I might have to do to fix this problem.
Now in fact, this is the worse possible case because now,
everyone is in the wrong position.
And in fact, number 8 is way the heck over here,
number 1 is way over there.
This is the worse possible case.
That was actually somewhere in between, best and worse,
how many steps now is it gonna take me to sort this folks.
[ Inaudible Remark ]
>> So 64, if you count it up.
And can we generalize if these are actually N individuals,
as oppose to 8 specifically?
[ Inaudible Remark ]
>> And so, N squared.
And where does this number come from?
Y N squared, N times N. Oh, what's that?
>> Inner and outer loop.
>> Yeah. So it's this inner and outer loop.
The inner loop is obvious
to see 'cause I keep taking all these steps across the stage.
Every time I check for swapping opportunities, I'm taking 8
or maybe 7 steps but for simplicity, let's just round
up to 8 so we don't have to do N minus 1 all the time.
Let's say this took 8 steps to get here.
But now in the worse possible case, I'm gonna have
to reset myself like a typewriter all the way back
to the beginning with one more time then another time,
then another time.
And if number 1 needs to move, let's say 1, 2, 3, 4, 5, 6, 7.
If number 1 needs to participate in 7 swaps
which is really almost 8, so let's call it N
or we could really be fanatic
and do N minus 1, that's N swaps.
So in each iteration, she only moves maximally 1 step.
She only bubbles up a little to this N.
So to get here all the way here, I need to take N steps this way
and I need to do that as many as N times round.
So in the worse case to sort N individuals
with this algorithm it would seem to take,
give or take N squared.
N times 2 number of steps.
Now 8 times 8, 64, that's not that bad, right.
It felt like the intuitive human way was a little faster
but N squared isn't that bad but what
about when N is not 8 but 10.
So that's 10 squared, that's a 100 or 100, 10,000,
now we start getting a very and very quickly
to much larger scarier values and this feels
like it could very quickly start consuming a lot of resources.
So can we do better?
Let's try one other approach.
If you guys could reset to this random approach,
so we don't always consider best case worse case.
Let's see if we can't do something a little different.
So that was the simplest most naive algorithm I could come
up with a sort of a newbie computer swapping the things
that I see next to each other.
Let's try to leverage the common sense that most of us have,
that all of us have in this room when it comes
to finding the smallest number.
And let's just grab the smallest number then look
for the next smallest, then look for the next smallest, right,
'cause odds are when you glance at this numbers and you're told
to sort them, you probably latch on to the number 1 first.
Maybe the number 8 if you prefer to work backwards,
but at least the number 1 then 2, so let's see
if we can't leverage that.
So again visually, if you could flip your papers around,
this is what the computer sees in advance.
I just know there is eight elements,
I can't see them all at once.
So now if you could go back to normal, now,
I'm gonna be the computer and I'm gonna look
for the smallest possible value.
Alright, so 4, he is the smallest possible value
at this point in time.
So I'm gonna make a mental note.
Or in computer terms, I'm gonna use a variable
to remember 4 is the smallest and he is at location 0.
Alright, oh, disqualified.
He is no longer the smallest value, I've now found number 2
at location bracket 1, now I'm gonna remember that
and I'm gonna forget about him.
Alright, 'cause it's a lot easier to keep track
of one number than two at once.
So now, I keep looking 'cause maybe your not number 1.
So umm, you don't change my variables, definitely not.
One, we've already ousted number 2.
So here is the smallest possible value at location 0, 1, 2, 3,
at location 4, so I should remember that.
Do I now know I found the smallest?
>> No.
>> Alright.
So not-- technically no, visually obviously.
But technically no unless I was given an assumption,
here our 8 numbers, the smallest number is 1
but I was just given 8 numbers in random order,
the only way I know, number 1 is in fact the smallest is
by continuing a total of 8 or N steps.
But now what do I do, I remembered with some variable
that she's at location 4.
>> So what can I do?
Well unfortunately, this is an array.
An array thus far re-fixed the size.
When you create an array as we've seen like an array
for quizzes, we said two quizzes go here.
And we used the constant at that time.
And in fact in C, unlike some languages like PHP
and JavaScript we'll see,
when you declare an array it's a fixed size.
Now this is a problem because I might wanna move number 1
to the start of this list but there's no room.
Alright, I only have 8 slots I have 8 numbers.
I can I have temporary variables so I could hold you
out if you will from the array leaving kind of a duplicator
or a gap in it so what, what are my options?
How do I move number 1 to her appropriate place?
So I could swap, right?
What could I do?
You know, he doesn't' need to be there, right?
I definitely don't need number 4 there or really
in general any one other than 1 there.
So why don't I do that?
And actually before I do that,
what's an alternative before we correct-- do this right?
Alright, I could just-- guys could just-- that way, yeah.
But wait, that looks obvious, looks intuitive but that's 1, 2,
that was three steps 'cause each of these variables or each
of ints has to be moved deliberately
by the computer with a line of code.
So that's three steps to move these guys over,
maybe 4 to move him over as well.
Let's take the simpler approach.
4 again doesn't need to be there.
This numbers we given to me in random order.
Who cares if I mix them up even more if I don't care
where they are just yet.
So let's move number 1 over here, number 4 over there.
And now this is 1 swap not a 3 or 4 total swaps.
Now what do I do?
Well at the back at the end of the list, now nicely enough,
I can have a little optimization.
I never again need to look at number 1
because I already have decided--
[laughter] because I've already determined she's the smallest
so it would just be a waste of CPU cycles to start here again.
So I can maybe have another variable
that says start this time at number 1.
Not in number-- location 0, start at location 1.
So here we go.
Number 2, I found him.
He's already right here.
But I don't know that necessarily.
So now you might be thinking
but why didn't you just remember this the last time and I could
but that's a different algorithm.
That's more memory.
Right now I'm just using a couple of variables
to keep track of who and who's where and what they are.
So 2, is currently the smallest.
So I'm gonna remember that.
6 doesn't beat him, 8, 4, 3, 7, 5,
so that's another N minus 1 steps 'cause I didn't bother
looking at number 1 again.
So that's almost N steps.
He is in fact in the right place.
I don't have to do any work at all.
Now, let's continue I can move my left boundary here.
6 is currently my smallest number not beaten
by 8-- oh, beaten by 4.
4 is now the smallest.
Oh, 3 is now the smallest number.
No, nope I made metal note of where 3 is, what do I do?
>> Swap.
>> Swap 3 with 6.
And now I'll stop telling the story verbally if you guys,
I'll just point, can execute now, so.
Actually this really isn't very,
very clear if I just point and say nothing.
Okay, so [laughter] 4 is currently the smallest value
that I found.
So where do we move you?
So we swap this.
And again, it might seem that 8 is moving into his position
and that is true 'cause presumably it is bigger
and is moving up.
But for the most part,
these swaps are just moving random numbers
to other random location.
So we're not actually making the problem any worse fundamentally.
So now 8 is my smallest.
Oh, now 6 is, now 5 is.
So 5, alright, it's good.
And now 6 is my smallest, 7 is my-- 6 is my smallest,
6 is still smallest, 6 is still smallest and so no swaps.
Now I do the same thing, the same thing
so this begs the question.
This was a little more a little real world,
a little more human-oriented 'cause I just implemented
my commonsense.
I found the smallest number put her in place,
found the next smallest number, put him in place
and then repeat, repeat, repeat.
So how much time, how many steps did this algorithm take?
[ Inaudible]
>> So it's not N factorial.
It kind of feels like one of those expressions
but that would actually be really bad, right?
That's 8 times 7 times 6 times 5 times 4.
That gets really big quickly.
So it's actually not that bad.
[ Inaudible Remark ]
>> And log in, it's not that good.
[ Inaudible Remark ]
>> N squared, so you know what, it turns out it almost is.
It's not as bad as this.
It's almost N squared.
It feels like we had some optimizations.
We stopped looking at 1 then we stopped looking at 2
and we only took as many steps as we had to do
and on each time I didn't just blindly swap.
I actually looked for the optimal position for someone
by plucking out the smallest and yet I claim now
that this is still roughly N squared.
Why? Let's take a 5-minute break, give these guys are round
of applause and we'll be back in 5.
[ Applause ]
>> You guys can keep those.
If you can just meet the TF over there, that'd be great.
Okay, so the cliff hanger that we left off
with was how much time the selection sort take,
vis-a-vis bubble sort.
So bubble sort we said pretty much takes N
squared comparisons.
So N squared steps rather is something like bubble sorts
in the worst case-- oh, actually I'm the only one
who knows this bubble sort.
So the first algorithm we looked at and I was kind of trying
to hint it this just by using the--
by saying bubbling this way, bubbling that way.
But in this much as when we compare values,
one of them might bubble up that way
and the other one might bubble down this way.
The world generally calls that first algorithm
where we just did ParaWise swaps something bubble sort.
And what's nice about it is you could actually code it
up in any language very, very straightforwardly.
But the down side is it doesn't feel
like the most efficient thing.
How slow is it?
Well, we'll see and feel that in just a moment.
But in the worst case it was in fact, N squared.
But in the best case it was just N, right?
In the best case, when I was handed all of the humans
in the correct order, I just had to do a sanity check once
down the list of N people to see, I didn't make any swaps,
therefore I'd be foolish to do that again and again and again
so I can terminate
that algorithm early after just N steps.
Now the second algorithm we did might be called selection sort.
That's what the world generally calls it.
In as much as you are selecting
on each iteration the smallest value.
And you could completely flip it around and just select
on each iteration the largest value.
But the algorithm would be the same in the N.
So selection sort, it wasn't as clear
at first what the running time is.
What the performance of this actual algorithm is.
But let's see, so with selection sort,
to find the smallest element it might take me what?
N steps. So I have to look at N values
because number 1 might be all the way over here, then I swap
but then I leave number 1 in her correct place and so now I move
on to look for the next smallest element which might be
in the worst case, where?
Might be over here.
But this is only seven steps this time.
So it feels like an optimization is brewing here, right?
Because one, I don't have to looking at it as I said.
I'm just now looking for the smallest--
the next smallest value which happens to be 2.
I find him maybe worse case over here.
I swap him.
that takes just a single step or maybe three.
And here's where I'll start to wave my hands
at some implementation details.
But visually swapping those two people we can think
of that as just one step.
It's one swap, one operation.
So now I did eight steps to find number 1.
Took me seven steps, worse case to find number 2.
Might take me six steps then five then four,
so it seems that we have this kind of process, 8 plus 7 plus
and then down to 1 to find the very last person.
Those of you who would like looking at formulas
like this might see a little something
like I equals 1 up to 8.
Alright, so a little summation like that
and what has this actually work out to be if you use
that cheat sheet in the back of a-- like high school math book?
Alright, so if we actually do this out,
8 plus 7 plus 6 plus 5, I believe this works
out to be N times N minus 1 over 2, is that right?
Right, so how did I get to that?
Well, frankly you can-- What's that?
>> N plus 1.
>> And plus 1?
Okay, N times N plus 1 over 2, I get the end result
of a formula that's what?
If I actually multiply this
out well this is N squared plus N over 2.
So you know there's an N squared in there.
Is it N plus 1 or N minus 1?
>> Plus.
>> Okay, plus 1.
So, N plus 1-- N squared plus N over 2, now that feels better
than N squared alone was, right?
Because even though this is N squared plus N then I'm
having it.
So this actually feels pretty good, but here is the thing.
When it comes to actually implementing algorithms
and analyzing algorithms, it's in the context of computers,
these kinds of constant factors like the number 2,
this really isn't all that interesting.
I might claim selection sort is twice as fast give
or take than bubble sort.
Because look, it takes half as many steps.
Now again, N squared plus N, I'm kind of waving my hand
at some of the terms here.
But this, too, kind of means that you have the running time,
the amount of time it takes for this algorithm to run.
But you know what, who cares, right?
Every year CPUs and consumer PCs seems to get faster and faster
so that this year I might have a gigahertz computer,
next year I'm gonna have a 2 gigahertz computer
which means next year selection sort will be twice
as good as it is today.
Alright, so it's hard to make claims with algorithms
that are just these constant factors better than one another.
Because again, with the hardware you can kind
of hide those details.
What we really wanna do is find an algorithm that even
if computer-- if the computer speeds double next year, well,
my algorithm itself gets even more than twice as fast.
We really wanna ride the curve as best as possible.
But for now, we're gonna wave our hands for a bit
until we get more precise.
And this is to say if selection sort takes N squared plus N
over 2 steps, eh, this isn't that interesting.
And you know what, even this term here maybe this is relevant
when it's N squared, so that's 64 plus 8.
That's an 8 additional units of measure more than 64.
That's non trivial here.
But what if now N is a billion?
A billion squared plus another billion that's actually not all
that much more, so relative proportion.
So you know what, forget this.
This, in the long term as N gets bigger, this is kind
of a meaningless addition to the formula.
So we're gonna claim for now that selection sort, too,
in the worst case is actually pretty much comparable
to bubble sort.
>> Not if you line up the numbers precisely
but at least big picture if you think in terms of large N
and you compared the graphs, as we'll do in a moment,
that this formulas make.
You know, it's pretty much N squared.
And in fact, there's a problem with selection sort.
What if in the best case, I'm handed 1, then 2, then 3,
then 4 and I try to sort those elements with bubble sort.
How many steps is it gonna take to sort N people
in the best case with selection sort?
>> The same.
>> It's the same, right?
Because even though it felt
like this nicely intuitive algorithm just keeps selecting
the smallest possible value.
Well, what's gonna happen in the best case.
They're all lined up from 1 to 8.
I find number 1 here and I say, okay,
he's the current smallest then I find 2, uh-hmm, 3, uh-hmm,
uh-hmm and not until I get to the end do I realize,
we'll that was stupid I found him in the very first step,
now let me go back to the beginning.
I don't have to look at him anymore because now I have
to look for the next smallest
and so I'm looking now for 2, right.
So now where's the next smallest?
Well 2 is right here, but maybe there's 1.5
or something like that over there.
I have to keep looking and looking and looking
so here's the downside of selection sort.
In the best case, it too is N squared
so while it might feel more intuitive, it might feel
like the more obvious algorithm,
we've just made the situation worst 'cause I don't know
in advance what these elements are.
So let's add some nomenclature here
that computer scientists are fond of using.
There's a symbol that the world generally uses
to describe what's called the worst case
and this is the capital O, often written in italics
so this is what the world generally calls big O notation.
And if you say an algorithm is in big O of N squared
that just means in the worst possible case
if you handed everything completely out of order,
it might take as many as this many steps.
Now in the best case, we use a different symbol a Greek one
this time, omega.
Omega just is the fancy way of saying
in the best possible case this algorithm might take N steps.
So these two correspond
to bubble sorts' worst and best cases.
Now we can do the same symbology for selection sort
and so we now have big O of N squared for the worst case,
omega of N squared for the best case and just to toss
out one additional piece of jargon if you say theta
of N squared that just means it's essentially in both big O
of N squared and in omega.
So in other words, if these are the same, you can then whip
out this notation as well, this theta notation.
Now why do we use this?
'Cause it's just a nice shorthand way
of saying best case, worst case and we can now start to talk
about the efficiency of our algorithms.
We can talk about the quality of their design in terms
of their performance in a way that's not CPU specific.
It doesn't matter if it's Intel Inside or anything else
because now we're looking at a higher level than we have
in the weeks past at the underlying operation.
Swapping two things conceptually or stepping
down an array conceptually.
It's step after step after step.
So let's see if we can't visualize a couple
of these algorithms in a more rapid way
than humans here allowed for.
So this is a little program that's available online.
We've linked to it on CS50's website.
I switched over to one of the TF's PCs here
because it doesn't work properly on a Mac unfortunately.
The buttons don't appear on the bottom
but that's fine just realize if you play with it on your Macs,
you'll be missing some of the demo and notice
that in the bottom left hand corner of this little applet,
happens to be written in Java, I can choose a whole bunch
of sorts and I've preselected bubble sort,
that's the first thing we started with.
You can specify what the array is gonna look like at first,
you can specify a time delay here.
I'm gonna go ahead and just click start
and we'll see what happens.
So what you see on the board now is just a visualization
of what we did a moment ago with humans.
Each of these bars represents a number.
The taller the bar, the bigger the number, the smaller the bar,
the smaller the number, so small bar might be 1,
big bar might be like 100.
And what's happening here in red is that this algorithm much
like my feet on stage is looping from left to right,
left to right on an each iteration it's comparing two
elements making them red and then swapping them,
if in fact they are out of order.
And even though this is moving at a pretty good clip,
you can see a couple of features here.
One, it's kinda boring and it's kind
of slow even though those bars are moving in a decent clip left
to right but clearly visually are the larger elements bubbling
up to the right hand side
and gradually are the smaller elements bubbling
down if you will to the left hand side.
So it's almost done, almost done, almost done, almost done,
almost done and it only makes them red
when it actually swaps them, okay done.
And down here if you're curious afterwards to the play
with the demo in more detail,
it actually counts how many comparisons you're making,
how many swaps you're making and so forth.
So now let's do this, let me go ahead and click stop here.
I'm gonna change the algorithm to selection sort.
I'm gonna use the same speed to be fair and click start
and now less seems to be happening from unit of time,
there is less flashiness but notice now highlighted
in red is the smallest element just encountered and as soon
as it's found, by conforming, by going all the way to the right,
it drops it into place.
So visually, this algorithm is working kind
of the opposite direction.
The end result is of course gonna be the same
and it actually felt a little faster
and it absolutely did fewer swaps because this time
when we're swapping, we're really swapping it
as far away as we want.
We're not just doing these adjacent swaps but these too,
if you actually count out the number of steps
in the worst possible case,
you'll see these numbers N squared.
You've got 100 elements,
it's gonna be 100 squared possible steps for comparisons
or swaps and same deal for bubble sort as well.
So that then begs the question, can we do different
and why would we wanna do different?
Well let me toggle back here to these visuals
and see what the implications are for algorithms that are
in fact N squared or just in general not so well implemented.
So this is a little chart that I just I happen
to make up with Excel.
There's not all that much going--
oh kind of not the best fidelity on the screen here
but I'll point out the details that are actually important.
Here-- thanks, got it.
Okay, so on the X axis here we just had N so this happens
to be 0, this happens to be 33, 66 and so forth.
It doesn't matter what they are just on the right--
on that X axis, there's a value of N and it's increasing
so this implies more and more humans or more
and more numbers to sort.
Meanwhile on the Y axis here, this is meant to be--
depict time so and if you have 33 elements
as this suggests according to this chart here,
it's saying this takes 5 units of time
and this means more units of time and if it's up here,
that's even more units of time.
So the numbers frankly are irrelevant,
it's really the curves of these things
that are worth considering for just a moment.
So there's 3 different graphs here that I made with Excel.
One represents N, so the little diamonds or the ones here
on the left hand side and even though it's not going
up at a 45-degree angle based on how I did the axes,
it's obviously a straight line.
An algorithm that takes N steps, means if you increase the number
of humans or the number of numbers by 1,
it's gonna take you 1 more step to count it.
So consider for instance bubble sort in the best case.
If I didn't have 8 volunteers but I had 9 volunteers well
in the best case, it's gonna take me one additional step
to count that-- check that one additional human 'cause I just
have to take one 9th step over here so that we can see
as pictorially as this relationship here.
Now suppose I come up with a smarter algorithm as I did
in the first day of class.
Recall that the simplest algorithm
for counting all you guys is 1, 2, 3, 4, 5, 6, 7, 8,
this takes a while but it's slightly faster actually it's
twice as fast if I use that little grade school trick of 2,
4, 6, 8, 10, 12 and so now that algorithm is
in fact twice as fast.
It's still a straight line
and that's what this one what the squares represent.
So according to the axes,
I've chosen here it's still a straight line but notice
that it moves at a lesser gradient so that's good
because it means as N increases the amount of time taken
to count-- the amount of time involved in counting people
in 2s instead of 1 obviously is less
than if you're just counting them one at a time.
But here is really the end game, this thing here.
So recall that the other algorithm we deployed
in the very first day of class was that self-counting algorithm
where you guys all stood up and half of you sat down,
half of you sat down, half of you sat down so that we went
from like 500 to 250 to 125 and so forth
and so there were just one in theory person standing.
Now, it will took a while 'cause there's a lot of social issues
and coordination of all that going on but in theory,
on each iteration that problem was getting halved,
halved, halved.
Just like the phonebook getting halved, halved, halved.
Well, what does it look
like when you halve a problem again and again and again.
Well it looks like this chart here.
When we describe that algorithm as logarithmic or log base 2
of N, this is what it looks like and again it's curves here
that are interesting because it looks
like if I'm counting people in Sanders, the naive way one
at a time, I mean this is gonna take a ridiculous amount
of time, the chart literally goes up to the roof.
Now it's slightly better if I count you in 2s but even
that eventually for large N,
it's gonna take a ridiculous amount of time
but if we use something like the divide and conquer strategy
of the phonebook or as applied to humans having half
of you sit down, half of you sit down,
this is when this curve gets amazingly powerful, right.
Literally, on that first day of class, we could have had
like justice come back into Sanders, right, doubling--
more than doubling the number of students in the room and
yet the algorithm you guys were applying one more step, right,
'cause we could've made all of justice sit
down the moment they enter the room and we just-- right?
[Laughter] We know that we've taken a bite
out of the problem that's half as large as N itself.
So this is really the sort of golden ring that you're
after when you're trying to come up with the most efficient
or the most alluring algorithm possible and the payoffs
as this chart suggests are huge.
This is one 130 here, this means if we have 260 students that's
over here and then 500 or so over here, that chart
or that graph rather is flat lining
in this way far more so than these things.
Now of course, we cannot sort N elements in log N time, right.
Log N seems to be again what we're after.
>> The holy grail of algorithms 'cause look how much better it
is than anything we've looked at thus far.
But I claim we can't sort N individuals in logarithmic time
so neither of these algorithms were that good
and I don't think I can come up with one that's good
and intuitively why might that be the case?
Why can you not sort N people or N numbers
in the log base N of time?
So clearly, yeah?
>> So this at least gets you run
through from the beginning to the end.
>> Yeah. There's this one got to.
You can't possibly sort any individuals in less
than say N time because you don't know
if they're actually sorted unless you actually check
that list, right.
Otherwise, it's guesswork.
Now we-- the humans might glance at the list, oh, sort it.
But how did you do that?
Well maybe unbeknownst to you or your brain,
you actually did scheme that list at least one eye movement
for each person up here so that's at least 8 steps.
So this might work for searching and that's what we've--
this might work for counting.
I'm searching the phonebook, counting the students
but for sorting we need to spend a bit more.
Well, what would these algorithms feel like.
We'll here's a different chart, a different axis
but again it's the shape that we care about.
So here is the same chart
but we've given us more of a Y access.
Here is what I will call N so this is--
if you increase the number of students,
your algorithm increases by 1.
It's a 1 to N ratio here or rather it's a one to one ratio.
Here is log base 2 of N so when you--
right, this is how you can kind of mislead people
with statistics and charts and consulting and all of this
where I change your axis
and look how N looks you know not all of that much worse
than log base N-- log base 2 of N, right.
Your clients might as well buy the N algorithm,
it's not all that much slower.
But notice here if we actually are now looking at algorithms
as we're gonna start to in class that take may be N log N squared
or actually this is pretty rather-- sorry.
If we look at algorithms that take N squared time
like bubble sort and like selection sort, I mean my God,
if only we could sort N individuals in just N time.
You really start to feel the difference again even
irrespective of the axis.
The shapes of these graphs suggest
that if you can avoid N squared, you really should.
In fact if we zoom out even further,
there are some algorithms in this world
that are believed to be exponential.
This isn't even as bad as factorial,
exponential here at top.
If you have algorithm that takes 2 to the N steps
which we may discuss briefly in time, for more on this CS121,
CS124, I mean my God, this is absolutely an algorithm
to be avoided because here you are like 200,000 or so steps
and well, here is N down here at which point all
of these algorithms look better and better,
but this is the take away.
When you start looking at problems like Facebook faces
and Goggle faces and N is actually big,
these are the kinds of curves
that are particularly alluring for someone.
So can we do better and how can we describe these things.
Well, again we got big O, we've omega got and theta.
Let's see if we can't describe yet another running time here
but we need a tool for this.
So, we have talked certainly about the phonebook.
It's sort of ad nauseam at this point and that was an example
of divide and conquer.
Divide the phonebook in half and then do it again, do it again,
do it again and there in lies kind of the insight
of divide and conquer.
We did this too on Monday with the second array.
We dived into the middle of the array, then we dived
into the middle here, then the middle here and voila,
there was our element, the number 50.
So when you do something again and again and again
and the only thing that's changing is really the size
of the problem, the steps you are executing are still
the same.
I'm still tearing a phonebook in half.
It's just half as big now.
I'm going it again.
It's now a quarter as big but it's still the same algorithm.
Well, this is in general known as recursion
and we can write functions and I did this just kind
of for fun the other day, we can deliberately write functions
that recurs by calling themselves.
Now what do we mean by this.
Well, in the context of C, we can write a function and surely
that function can call itself.
If I define a function called, fu, if I want fu to call itself,
I just have to write the word fu open parenthesis,
close parenthesis, semicolon, inside fu itself,
but bad things happened when I did this last time.
What happened when I wrote literally a function fu
that called itself?
>> Seg fault.
>> So I got a seg fault.
Now why was that?
Well again just think back
to the building blocks we've been looking at, right?
Where you have memory in our computer,
we keep drawing it as a rectangle.
Every time you call a function, you add a frame to that stack.
In other words, you ask for some memory and conceptually it's
like putting it on top of the stack
of memory you've already asked for so you call fu, you call fu,
you call fu, fu, fu, fu, fu, what eventually happens?
>> Run out.
>> Right, you run out or you hit some other memory
that doesn't belong to you
and that's something we'll see before long called the heap
but in short doing this again and again and again is bad
so recursion does have this risk in it.
If you do the same thing again and again
but in each time allocate memory, you might run
into some trouble but perhaps it's nonetheless a technique we
can leverage.
So let's take a look at one piece of code here
that was among in the printouts from Monday
and this is something called sigma 1.
Just out of habit, I'm gonna start using VI sometimes instead
of nano.
It's just another text editor with more arcane commands
but it does the same thing.
I'm gonna scroll down
and introduce this relatively tiny program.
So this program here has a main function
and the first thing this function does is ask the user
for int so this is actually a good use
of the do-while construct because recall
that do-while tells the user to do something
and maybe get something from the user
but if the user is being difficult, I can force it
to loop again and again after I check that value.
So this chunk of code here is the comments explained.
I'm forcing the user to give me a positive integer,
not a negative nonzero but a positive integer.
Now at this line in the story,
I'm apparently declaring a variable called answer it's
of type int and I'm lining it with value of sigma
so I chose sigma based on this symbol here just to be clever
but sigma is apparently a function that I wrote.
It takes one argument.
I'm passing it apparently an integer
so let's see what it does.
Well actually, this is pretty simple,
it looks a little cryptic at first but this is
like day 1 stuff now, right.
Sigma is gonna return an int.
It's gonna take an int as it's argument
and I'm calling it M just
because on a little sanity check, I don't wanna get
into an infinite loop here by accident
so I'm making sure M is not less than 1.
If it is, I'm returning 0 just so bad things don't happen
and now what am I doing?
I'm declaring a variable called sum, initializing it to zero
and then this loop here.
Well, actually it's pretty straightforward.
I starts at 1 goes up to and through M
and on each iteration plus equals just does what?
It adds the thing on the right to the left.
This is equivalent and it's just shorthand notation
for saying sum equals sum plus I.
It's just a little more succinct than that.
So in the end, the sigma function just returns the sum
of all of the numbers from N down to 1 or down
to 0 which are equivalent.
Alright, so this is one way to do it.
Let me go ahead and go back to the original here
so this is plus equal 1, let me ago ahead and compile sigma 1.
I'm gonna run sigma 1 and I'll give it a positive integer
of 8 people.
Alright so 36, so that's 8 plus 7 plus 6 plus 5 let's do it
for 10.
Alright 55, okay let's do it for 100.
Alright, so this program seems to work
and frankly it's doing this a lot faster
than I could off the top of my head
so we have a nice useful program here.
But can we implement it in a different way.
Well, this is isn't necessarily the best way to implement it
but it's a nice way of demonstrating this idea
of recursion in a very simple context.
So this is version 2, sigma 2 and here we have same code.
Get the int, put it in N and make sure it's not less than 1
and then call sigma again and I'm gonna print out the answer.
So apparently, main is identical.
So let me scroll down to sigma
and here is something that's beautiful to my eyes at least.
So what does this mean, sad though that is.
So it returns an int.
It takes an int but now I just have 2, no 4 real lines of code
and even those are not all that interesting 'cause one is an if
and an else, what am I doing?
Well, first this is pretty much the same sanity check as before.
If M is less than or equal to 0, just return 0 right away
so that the user doesn't hand me a negative number
and completely break this program.
But notice this, all that work I did last time using a four loop,
an incrementing I and the sum and all this messy syntax.
it looks like I could just do this.
This is an example of recursion, right, just as I could look
for someone in the phonebook by looking
in the middle then going checking left
or right then doing it again.
Well technically you could sum numbers in the same way.
If you hand me the number 8, I can say the answer to sigma
of 8 is 8 plus sigma of 7 and I can completely punt on the rest
of the problem and let you deal with that, right.
You ask me for sigma 8, I say it's literally 8 plus sigma 7.
Well now, you come back to me and you say fine.
What's sigma of 7and I sort of smart ass say, 7 plus sigma
of 6, right and again and again.
Now, I'm sort of picking a contrived example here
but what's nice is just like with the phonebook,
just like with the counting students, we can take a bite
out of this problem, maybe it's only size 1, it's one number
but I can take a bite out of this problem
and then apply the exact same algorithm
to this slightly smaller problem.
And if I code this correctly, notice what happens.
If I code this correctly, I can take the small bite out
and then I can defer to who, to myself, right.
If I am now the sigma function who knows how
to compute this even though it's in this-- the smart aleck way,
well I can just say it's M plus sigma of M minus 1.
Now conceptually, what does that mean?
It means this is gonna get added to the return value
of sigma of N minus 1.
Well how do you compute that?
We'll here's sigma, you pass it now in the number 7 instead
of 8, 7 is not less than zero
so you don't return 0 what do you return?
You return 7 plus sigma of 6.
Now at this point, it gets to be a bit of a mind game, right.
'Cause now you have to keep saying call sigma, call sigma,
call sigma and you're never actually finishing any
of these answers until what?
When you call sigma of 0,
finally the seeming endless loop stops because at
that final 8th call you say, well what's sigma of 0?
>> And I don't give you again the smart aleck answer,
I instead say 0.
And that means you can then kind of reverse the process.
So you can say, okay if the answer
to that last question was 0 then a 0 plus 1
and that means 1 then the answer
to the previous question was 2 plus that and you can kind
of unwind in your mind and it's a little hard to think
of it first, but what's the end result.
You can implement in-- there's this beautiful way,
this very elegant sort of logical way,
the notion of summation that we just did but using just one line
of code and leveraging the code sigma that you already wrote.
Now what's the power of this?
Well once you have the ability to do things recursively,
you don't necessarily or you're not necessarily able
to solve problems in different in--
you're not necessarily to solve problems
that you couldn't otherwise using iteration and loops
but you can solve them a lot more intuitively
and you can use a programming technique recursion in a way
that really lends itself to the problem, and for that,
let me introduce this.
I'm gonna pull up a different demo here.
This one also happens to be implemented in Java
but it's just the visualization as in aside, the world has come
up with all sorts of sorts.
We won't look in this course at bozo sorts or cocktail sorts,
shaker sort but there's a whole bunch of them out there.
Let's pick the ones we did look at.
Bubble sort there, I'm gonna pick a selection sort here.
And it turns out one of our favorites
because of its power is something called merge sort.
So I've zoomed in on this graph.
What you see here is same kind of visualization as last time
but instead of the numbers being vertical,
this guy just implemented it sideways so in a moment,
I'm gonna click each of this graphs.
They're randomly oriented.
Small bars means small number, big bars means big number
and what you're gonna see assuming I click them all fast
enough is each of this 3 algorithms running
simultaneously and my claim is as we've seen bubble sort
in the worst case is N squared, selection sort
in the worst case is N squared
but this thing merge sort is an example of an algorithm that's
in N times log of N. So, it's not as good as log N
which was the case for divide and conquer and for searching,
but N log N is definitely smaller
than N times N 'cause log N is smaller than N. So here we go,
I give you in conclusion bubble sort,
the selection sort, the merge sort.
[ Pause ]
>> So that is what it means the solve problems effectively.
See you on Monday.
[ Noise ]