[Week 4]
[David J. Malan] [Harvard University]
[This is CS50.] [CS50.TV]
>> All right, this is CS50, and this is the start of week 4,
and this is one of the slowest possible sorting algorithms.
Which one was it that we just watched there?
That was bubble sort, in order big O(n^2) + sum,
and indeed we are not the only ones in this world to seem to know
what bubble sort is or its running time.
Indeed, this was an interview with Eric Schmidt of Google
and former senator Barack Obama just a few years ago.
>> Now, Senator, you're here at Google,
and I like to think of the presidency as a job interview.
Now, it's hard to get a job as president, and you're going through the rigors now.
It's also hard to get a job at Google.
We have questions, and we ask our candidates questions,
and this one is from Larry Schwimmer.
You guys think I'm kidding? It's right here.
What is the most efficient way to sort a million 32-bit integers?
[laughter]
Well—
I'm sorry.>>No, no, no, no.
I think the bubble sort would be the wrong way to go.
>> Come on, who told him this?
Last week recall we took a break from code, at least for a day,
and started focusing on some higher level ideas and problem solving more generally
in the context of searching and sorting,
and we introduced something that we didn't slap this name on last week,
but asymptotic notation, the Big O, the Big Omega,
and sometimes the Big Theta notation, and these were simply ways
of describing the running time of algorithms,
how much time it takes for an algorithm to run.
>> And you may recall that you talked about the running time in terms of the size
of the input, which we generally call n, whatever the problem may be,
where n is the number of people in the room,
the number of pages in a phone book, and we started to write things out
like O(n^2) or O(n) or O(n log n),
and even when the math didn't quite work out so perfectly
and it was n² - n/2 or something like that
we would instead just throw away some of the lower order terms,
and the motivation there is that we really want a
sort of objective way of evaluating
the performance of programs or the performance of algorithms
that at the end of the day has nothing to do, for instance,
with the speed of your computer today.
>> For instance, if you implement bubble sort,
or you implement merge sort or selection sort on today's computer,
a 2 GHz computer, and you run it,
and it takes some number of seconds, next year there's a 3 GHz
or a 4 GHz computer, and you might then claim that "Wow, my algorithm
is now twice as fast," when in reality that's obviously not the case.
It's just the hardware has gotten faster, but your computer
has not, and so we really want to throw away things like
multiples of 2 or multiples of 3 when it comes to describing
how fast or how slow an algorithm is and really just focus
on n or some factor thereof,
some power thereof as in the case of the sorts from last week.
And recall that with the help of merge sort
we were able to do so much better than bubble sort and selection sort
and even insertion sort.
>> We got down to n log n, and again,
recall that log n generally refers to something that grows
more slowly then n, so n log n thus far was good
because it was less than n².
But to achieve n log n with merge sort
what was the basic germ of an idea that we had to leverage
that we also leveraged back in week 0?
How did we tackle the sorting problem cleverly with merge sort?
What was the key insight, perhaps?
Anyone at all.
Okay, let's take a step back.
Describe merge sort in your own words.
How did it work?
Okay, we'll row back to week 0.
Okay, yeah.
[inaudible-student]
Okay, good, so we divided the array of numbers into 2 pieces.
We sorted each of those pieces, and then we merged them,
and we've seen this idea before of taking a problem that's this big
and chopping it up into a problem that's this big or this big.
>> Recall the phone book example.
Recall the self-counting algorithm from weeks ago,
so merge sort was summarized by this pseudocode here.
When you're given n elements, first it was sanity check.
If n < 2 then don't do anything at all
because if n < 2 then n is obviously 0 or 1,
and so if it's either 0 or 1 there's nothing to sort.
You're done.
Your list is already trivially sorted.
But otherwise if you've got 2 or more elements go ahead and divide them
into 2 halves, left and right.
Sort each of those halves, and then merge the sorted halves.
But the problem here is that at first glance this feels like we're punting.
This is a circular definition in that if I've asked you to sort these n elements
and you're telling me "All right, fine, we'll sort those n/2 and those n/2 elements,"
then my next question is going to be "Fine, how do you sort the n/2 elements?"
>> But because of the structure of this program,
because there is this base case, so to speak,
this special case that says if n is < some fixed value like 2 return immediately.
Don't respond with that same circular answer.
This process, this cyclicity will eventually end.
If I ask you "Sort these n elements," and you say, "Fine, sort these n/2,"
then you say, "Fine, sort these n/4, n/8, n/16,"
eventually you'll divide by a big enough number
that you'll have just 1 element left, at which point you can say,
"Here, here is a sorted single element."
Then the brilliance of this algorithm up here is to derive from the fact
that once you have all of these individually sorted lists,
all of which are of size 1, which seems to be useless,
once you start merging them and merging them
you build up finally as Rob did in the video a finally sorted list.
>> But this idea extends far beyond sorting.
There is this idea embedded in this program known as recursion,
the idea whereby you are a program,
and to solve some problem you call yourself,
or put in the context of programming languages you are a function,
and in order to solve a problem, you the function call yourself
again and again and again, but you the function
can't call yourself infinitely many times.
Eventually you have to bottom out, so to speak,
and have some hard-coded base condition that says
at this point stop calling yourself so that the whole process
finally does in fact stop.
What does this really mean, to recurse?
>> Let's see, if we can do a simple, trivial example with, say,
3 people with me up here on stage, if someone is comfortable.
1, come on up, 2 and 3.
If you 3 want to come up here.
If you want to stand right next to me here in a line, suppose that the problem at hand
is very trivially count the number of people who are here.
But frankly, I'm tired of all these counting examples.
This is going to take some time, 1, 2, and dot, dot, dot.
It's going to take forever.
I'd rather just punt this problem altogether with the help of—what's your name?
Sara.>>Sara, all right.
Kelly.>>Kelly and?
>> Willy.>>Willy, Sara, Kelly, and Willy.
Right now I have been asked the question by someone
how many people are up on this stage, and I have no idea.
This is a really long list, and so instead I'm going to do this trick.
I'm going to ask the person next to me to do most of the work,
and once she is done doing most of the work
I'm going to do the least amount of work possible and just add 1
to whatever her answer is, so here we go.
I've been asked how many people are on stage.
How many people are on stage to the left of you?
The left of me?>>Okay, but don't cheat.
That's good, that's correct, but if we want to continue this logic
let's assume that you similarly want to punt this problem to the left of you,
so rather than answer directly go ahead and just pass the buck.
Oh, how many people are to the left of me?
How many people are to the left?
1.
[laughter]
Okay, so 0, so what now Willy has done
is you've returned your answer this direction saying 0.
Now, what should you do?>>1.
Okay, so you're the 1, so you say, "All right, I'm going to add 1
to whatever Willy's count was," so 1 + 0.
You're now 1 so your answer to the right is now—
1.>>And mine would be 2.
Good, so you're taking the previous answer of 1,
adding the minimal amount of work you want to do, which is +1.
You now have 2, and you then hand me which value?
3, I mean, sorry, 2.
Good.
>> Well, we had 0 to the left.
Then we had 1, and then we add 2,
and now you're handing me the number 2,
and so I'm saying, okay, +1, 3.
There's indeed 3 people standing next to me on this stage,
so we could have obviously done this very linearly,
very much in the obvious fashion, but what did we really do?
We took a problem of size 3 initially.
We then broke it down into a problem of size 2,
then a problem of size 1, and then finally the base case
was really, oh, there's no one there,
at which point Willy returned effectively a hard-coded answer a couple of times,
and the second one was then bubbled up, bubbled up, bubbled up,
and then by adding in this one additional 1
we've implemented this basic idea of recursion.
>> Now, in this case it didn't really solve a problem
any more effectively then we've seen thus far.
But think about the algorithms we've done on stage thus far.
We had 8 pieces of paper on the chalkboard,
on video when Sean was looking for the number 7, and what did he really do?
Well, he didn't do any kind of divide and conquer.
He didn't do any kind of recursion.
Rather he just did this linear algorithm.
But when we introduced the idea of sorted numbers on stage live last week
then we had this instinct of going to the middle,
at which point we had a smaller list of size 4 or another list of size 4,
and then we had the exact same problem, so we repeated, repeated, repeated.
In other words, we recursed.
Thank you very much to our 3 volunteers here for demonstrating recursion with us.
>> Let's see if we can't make this now a little more concrete,
solving a problem that again we could do pretty easily,
but we'll use it as a stepping stone to implementing this basic idea.
If I want to compute the summation of a bunch of numbers,
for instance, if you pass in the number 3,
I want to give you the value of sigma 3,
so the sum of 3 + 2 + 1 + 0.
I want to get back the answer 6,
so we'll implement this sigma function, this summation function
that, again, takes in input, and then returns the summation
of that number all the way down to 0.
We could do this pretty simply, right?
We could do this with some kind of looping structure,
so let me go ahead and get this started.
>> Include stdio.h.
Let me get myself into main to work with here.
Let's save this as sigma.c.
Then I'm going to go in here, and I'm going to declare an int n,
and I'm going to do the following while the user does not cooperate.
While the user has not given me a positive number
let me go ahead and prompt them for n = GetInt,
and let me give them some instructions as to what to do,
so printf("Positive integer please").
Just something relatively simple like this so that by the time we hit line 14
we now have a positive integer presumably in n.
>> Now let's do something with it.
Let me go ahead and compute the summation, so int sum = sigma(n).
Sigma is just summation, so I'm just writing it in the fancier way.
We'll just call it sigma there.
That's the sum, and now I'm going to print out the result,
printf("The sum is %d, \n", sum).
And then I'll return 0 for good measure.
We've done everything that this program requires except the interesting part,
which is to actually implement the sigma function.
>> Let me go down here to the bottom, and let me declare function sigma.
It's got to take a variable that's of type integer,
and what data type do I want to return presumably from sigma?
Int, because I want it to match my expectations on line 15.
In here let me go ahead and implement this
in a pretty straightforward way.
>> Let's go ahead and say int sum = 0,
and now I'm going to go have a little for loop here
that's going to say something like this,
for (int i = 0; I <= number; i++) sum += i.
And then I'm going to return sum.
I could have implemented this in any number of ways.
I could have used a while loop.
I could have skipped using the sum variable if I really wanted to,
but in short, we just have a function that if I didn't goof declares sum is 0.
Then it iterates from 0 on up through the number,
and on each iteration it adds that current value to sum and then returns sum.
>> Now, there's a slight optimization here.
This is probably a wasted step, but so be it. That's fine for now.
We're at least being thorough and going 0 all the way on up.
Not very hard and pretty straightforward,
but it turns out that with the sigma function we have the same opportunity
as we did here on stage.
On stage we just counted how many people were next to me,
but instead if we wanted to count the number 3 + 2 + 1
on down to 0 we could similarly punt to a function
that I'll instead describe as being recursive.
Here let's do a quick sanity check and make sure I didn't goof.
>> I know there's at least one thing in this program that I did do wrong.
When I hit enter am I going to get any kind of yelling at me?
What am I going to be yelled at about?
Yeah, I forgot the prototype, so I'm using a function called sigma on line 15,
but it's not declared until line 22, so I best proactively go up here
and declare a prototype, and I'll say int sigma(int number), and that's it.
It's implemented at the bottom.
>> Or another way I could solve this,
I could move the function up there, which isn't bad,
but at least when your programs start to get long, frankly,
I think there's some value in always having main at the top
so that you in the reader can open the file and then immediately see
what the program is doing without having to search through it
looking for that main function.
Let's go down to my terminal window here, try making sigma make sigma,
and I screwed up here too.
Implicit declaration of function GetInt means I've forgotten to do what else?
[inaudible-student]
Good, so apparently a common mistake, so let's put this up here,
cs50.h, and now let's go back to my terminal window.
>> I'll clear the screen, and I'll rerun make sigma.
It seems to have compiled. Let me now run sigma.
I'll type in the number 3, and I did get 6, so not a rigorous check,
but at least it seems to be working at first glance, but now let's rip it apart,
and let's actually leverage the idea of recursion, again,
in a very simple context so that in a few weeks' time
when we start exploring fancier data structures than arrays
we have another tool in the toolkit with which to
manipulate those data structures as we'll see.
This is the iterative approach, the loop-based approach.
>> Let me instead now do this.
Let me instead say that the summation of number
on down to 0 is really the same thing as
number + sigma(number - 1).
In other words, just like on stage I punted to each of the people next to me,
and they in turn kept punting until we finally bottomed out at Willy,
who had to return a hard-coded answer like 0.
Here now we're similarly punting to sigma
the same function as was originally called, but the key insight here
is that we're not calling sigma identically.
We're not passing in n.
We're clearly passing in number - 1,
so a slightly smaller problem, slightly smaller problem.
>> Unfortunately, this isn't quite a solution yet, and before we fix
what might be jumping out as obvious at some of you
let me go ahead and rerun make.
It seems to compile okay.
Let me rerun sigma with 6.
Whoops, let me rerun sigma with 6.
We've seen this before, albeit accidentally last time as well.
Why did I get this cryptic segmentation fault? Yeah.
[inaudible-student]
There's no base case, and more specifically, what probably happened?
This is a symptom of what behavior?
Say it a little louder.
[inaudible-student]
It's an infinite loop effectively, and the problem with infinite loops
when they involve recursion in this case, a function calling itself,
what happens every time you call a function?
Well, think back to how we laid out the memory in a computer.
We said that there's this chunk of memory called the stack that's at the bottom,
and every time you call a function a little more memory gets put
on this so-called stack containing that function's local variables or parameters,
so if sigma calls sigma calls sigma calls sigma
calls sigma where does this story end?
>> Well, it eventually overruns the total amount
of memory that you have available to your computer.
You overrun the segment that you're supposed to stay within,
and you get this segmentation fault, core dumped,
and what core dumped means is that I now have a file called core
which is a file containing zeros and ones
that actually in the future will be diagnostically useful.
If it's not obvious to you where your bug is
you can actually do a bit of forensic analysis, so to speak,
on this core dump file, which, again, is just a whole bunch of zeros and ones
that essentially represents the state of your program in memory
the moment it crashed in this way.
>> The fix here is that we can't just blindly return sigma,
the number + sigma of a slightly smaller problem.
We need to have some kind of base case here,
and what should the base case probably be?
[inaudible-student]
Okay, so long as the number is positive we should actually return this,
or put another way, if number is, say, <= to 0
you know what, I'll go ahead and return 0,
much like Willy did, and else, I'm going to go ahead
and return this, so it's not that much shorter
than the iterative version that we whipped up first using a for loop,
but notice that there's this sort of elegance to it.
Instead of returning some number and performing all this math
and adding things up with local variables
you're instead saying "Okay, if this is a super easy problem,
like the number is < 0, let me immediately return 0."
>> We're not going to bother supporting negative numbers,
so I'm going to hard code the value of 0.
But otherwise, to implement this idea of summing
all of these numbers together you can effectively take a small bite
out of the problem, much like we did here on stage,
then punt the rest of the problem to the next person,
but in this case the next person is yourself.
It's an identically named function.
Just pass it a smaller and smaller and smaller problem each time,
and even though we haven't quite formalized things in code here
this is exactly what was going on in week 0 with the phone book.
This is exactly what was going on in past weeks with Sean
and with our demonstrations of searching for numbers.
It's taking a problem and dividing it again and again.
>> In other words, there's a way now of translating
this real world construct, this higher level construct
of divide and conquer and doing something again and again
in code, so this is something we will see again over time.
Now, as an aside, if you're new to recursion you should at least understand now
why this is funny.
I'm going to go to google.com,
and I'm going to search for some tips and tricks on recursion, enter.
Tell the person next to you if they weren't laughing just now.
Did you mean recursion?
Did you mean—ah, there we go.
Okay, now that's the rest of everyone.
A little Easter egg embedded somewhere there in Google.
As an aside, one of the links we put on the course's website
for today is just this grid of various sorting algorithms,
some of which we looked at last week, but what's nice about this visualization
as you try to wrap your mind around various things related to algorithms
know that you can very easily now start with different types of inputs.
The inputs all reversed, the inputs mostly sorted, the inputs random and so forth.
As you try to, again, distinguish these things in your mind
realize that this URL on the course's website on the Lectures page
might help you reason through some of those.
>> Today we finally get to solve this problem from a while back,
which was that this swap function just didn't work,
and what was the fundamental problem with this function swap,
the goal of which was, again, to exchange a value here and here
such that this happens?
This didn't actually work. Why?
Yeah.
[inaudible-student]
Exactly, the explanation for this bugginess
simply was because when you call functions in C
and those functions take arguments, like a and b here,
you are passing in copies of whatever value you're providing to that function.
You are not providing the original values themselves,
so we saw this in the context of buggyc,
buggy3.c, which looked a little something like this.
>> Recall that we had x and y initialized to 1 and 2, respectively.
We then printed out what they were.
I then claimed that I was swapping them by calling swap of x, y.
But the problem was that the swapping worked,
but only in the scope of the swap function itself.
As soon as we hit line 40 those swapped values
were thrown away, and so nothing
in the original function main was actually changed at all,
so if you think back then as to what this looks like in terms of our memory
if this left-hand side of the board represents—
and I'll do my best for everyone to see this—if this left-hand side of the board
represents, say, your RAM, and the stack is going to grow on up this way,
and we call a function like main, and main has 2 local variables, x and y,
let's describe those as x here, and let's describe these as y here,
and let's put in the values 1 and 2, so this here is main,
and when main calls the swap function the operating system
gives the swap function its own swath of memory on the stack,
its own frame on the stack, so to speak.
It also allocates 32 bits for these ints.
It happens to call them a and b, but that's totally arbitrary.
It could have called them whatever it wants, but what happens when main
calls swap is it takes this 1, puts a copy there, puts a copy there.
>> There is 1 other local variable in swap, though, called what?>>Tmp.
Tmp, so let me give myself another 32 bits here,
and what did I do in this function?
I said int tmp gets a, so a has 1, so I did this when we last played with this example.
Then a gets b, so b is 2, so now this becomes 2,
and now b gets temp, so temp is 1,
so now b becomes this.
That's great. It worked.
But then as soon as the function returns
swap's memory effectively disappears so that it can be reused
by some other function in the future, and main is obviously completely unchanged.
We need a way of fundamentally solving this problem,
and today we'll finally have a way of doing this whereby
we can introduce something called a pointer.
It turns out that we can solve this problem
not by passing in copies of x and y
but instead by passing in what, do you think, to the swap function?
Yeah, what about the address?
We haven't really talked about addresses in much detail,
but if this blackboard represents my computer's memory
we could certainly start numbering the bytes in my RAM
and say this is byte #1, this is byte #2, byte #3,
byte #4, byte #...2 billion if I have 2 gigabytes of RAM,
so we could certainly come up with some arbitrary numbering scheme
for all the individual bytes in my computer's memory.
>> What if instead when I call swap
rather than pass in copies of x and y
why don't I instead pass in the address of x here,
the address of y here, essentially the postal address
of x and y because then swap, if he's informed
of the address in memory of x and y,
then swap, if we trained him a little bit,
he could potentially drive to that address, so to speak,
x, and change the number there, then drive to the address of y,
change the number there, even while not actually getting copies of those values himself,
so even though we talked about this as being main's memory
and this as being swap's memory the powerful and the dangerous part of C
is that any function can touch memory anywhere in the computer,
and this is powerful in that you can do very fancy things with computer programs in C.
This is dangerous because you can also screw up very easily.
In fact, one of the most common ways for programs these days to be exploited
still is for a programmer not to realize
that he or she is allowing a data
to be written in a location in memory that wasn't intended.
>> For instance, he or she declares an array of size 10
but then accidentally tries to put 11 bytes into that array of memory,
and you start touching parts of memory that are no longer valid.
Just to contextual this, some of you might know that
software often prompts you for serial numbers or registration keys,
Photoshop and Word and programs like this.
There exist cracks, as some of you know, online where you can run a little program,
and voila, no more request for a serial number.
How is that working?
In many cases these things are simply finding in the computers
text segments in the computer's actual zeros and ones
where is that function where the serial number is requested,
and you overwrite that space, or while the program is running
you can figure out where the key is actually stored
using something called a debugger, and you can crack software that way.
This isn't to say that this is our objective for the next couple of days,
but it has very real-world ramifications.
That one happens to involve theft of software,
but there's also compromise of entire machines.
>> In fact, when websites these days are exploited
and compromised and data is leaked and passwords are stolen
this very often relates to poor management of one's memory,
or, in the case of databases, failure to anticipate
adversarial input, so more on that in the weeks to come,
but for now just a sneak preview of the sort of damage that you can do
by not quite understanding how things work underneath the hood.
Let's go about understanding why this is broken
with a tool that will become more and more useful
as our programs get more complex.
Thus far when you've had a bug in your program
how have you gone about debugging it?
What have your techniques been thus far, whether taught by your TF
or just self-taught?
[Student] Printf.
Printf, so printf has probably been your friend in that if you want to see
what's going on inside of your program
you just put printf here, printf here, printf here.
Then you run it, and you get a whole bunch of stuff on the screen
that you can use to then deduce what is actually going wrong in your program.
>> Printf tends to be a very powerful thing,
but it's a very manual process.
You have to put a printf here, a printf here,
and if you put it inside of a loop you might get 100 lines
of output that you then have to sift through.
It's not a very user-friendly or interactive mechanism for debugging programs,
but thankfully there exists alternatives.
There's a program, for instance, called GDB, the GNU Debugger,
which is a little arcane in how you use it.
It's a little complex, but frankly,
this is one of those things where if you put in this week and next
the extra hour to understand something like GDB
it will save you probably tens of hours in the long run,
so with that, let me give you a teaser of how this thing works.
>> I'm in my terminal window.
Let me go ahead and compile this program, buggy3.
It's already up to date.
Let me run it just like we did a while back, and indeed, it's broken.
But why is this? Maybe I screwed up the swap function.
Maybe it's a and b. I'm not quite moving them around correctly.
Let me go ahead and do this.
Rather than just run buggy3 let me instead run this program GDB,
and I'm going to tell it to run buggy3,
and I'm going to include a command line argument, -tui,
and we'll put this in future problems at spec to remind.
And now this black and white interface popped up that, again,
is a little overwhelming at first because there's all this
warranty information down here, but at least there's something familiar.
In the top of the window is my actual code,
and if I scroll up here let me scroll to the very top of my file,
and indeed, there's buggy3.c, and notice at the bottom of this window
I have this GDB prompt.
>> This is not the same as my normal John Harvard prompt.
This is a prompt that's going to allow me to control GDB.
GDB is a debugger.
A debugger is a program that lets you walk through
execution of your program line by line by line,
along the way doing anything you want to the program,
even calling functions, or looking, more importantly,
at various variable's values.
Let's go ahead and do this.
I'm going to go ahead and type in run at GDB's prompt,
so notice at the bottom left of the screen I've typed run,
and I've hit enter, and what did that do?
It literally ran my program, but I didn't actually see much go on here
because I have not actually told the debugger
to pause at a particular moment in time.
Just typing run runs the program.
I don't actually see anything. I can't manipulate it.
>> Instead let me do this.
At this GDB prompt let me instead type break, enter.
That's not what I meant to type.
Let's instead type break main.
In other words, I want to set something called a breakpoint,
which is aptly named because it will break or pause
execution of your program at that particular place.
Main is the name of my function.
Notice that GDB is pretty smart.
It figured out that main happens to start roughly at line 18
of buggy3.c, and then notice here at top left
b+ is right next to line 18.
That's reminding me that I have set a breakpoint at line 18.
This time when I type run, I'm going to run my program
up until it hits that breakpoint,
so the program will pause for me at line 18.
Here we go, run.
Nothing appears to have happened, but notice at bottom left
starting program, buggy3, breakpoint 1 in main at buggy3.c line 18.
What can I do now?
>> Notice I can start typing things like print,
not printf, print x, and now that's strange.
The $1 is just a curiosity, as we'll see
every time you print something you get a new $ value.
That's so that you can refer back to previous values just in case,
but for now what print is telling me is that the value of x at this point in the story
is apparently 134514032.
What? Where did that even come from?
[inaudible-student]
Indeed, this is what we'll call a garbage value, and we've not talked about this yet,
but the reason that you initialize variables
is obviously so that they have some value that you want them to have.
But the catch is recall that you can declare variables
like I did a moment ago in my sigma example
without actually giving them a value.
Recall what I did over here in sigma.
I declared n, but what value did I give it?
None, because I knew that in the next few lines
GetInt would take care of the problem of putting a value inside of n.
>> But at this point in the story of line 11
and line 12 and line 13 and line 14
throughout those several lines what is the value of n?
In C you just don't know.
It's generally some garbage value, some completely random number
that's left over essentially from some previous function
having been run, so as your program runs
recall that function gets function, function, function.
All these frames get put on memory, and then those functions return,
and just like I suggested with the eraser their memory is eventually reused.
Well, it just so happens that this variable x in this program
seems to have contained some garbage value like 134514032
from some previous function, not one that I wrote.
It could be something that comes effectively with the operating system,
some function underneath the hood.
>> Okay, that's fine, but let's now advance to the next line.
If I type "next" at my GDB prompt and I hit enter,
notice that the highlighting moves down to line 19,
but the logical implication is that line 18
has now finished executing, so if I again type "print x"
I should now see 1, and indeed, I do.
Again, the $ stuff is a way of GDB reminding you
what the history of prints are that you've done.
Now let me go ahead and print out y, and indeed, y is some crazy value as well,
but no big deal because in line 19 we're about to assign it
the value 2, so let me type "next" again.
And now we're on the printf line.
Let me do print x.
Let me do print y. Frankly, I'm getting a little tired of printing this.
Let me instead type "display x" and "display y,"
and now every time I type a command in the future
I will be reminded of what's x and y, what's x and y, what's x and y.
>> I can also, as an aside, type in "info locals."
Info is a special command.
Locals means it shows me the local variables.
Just in case I forget or this is a crazy, complicated function
that I or someone else wrote info locals will tell you
what are all the local variables inside this local function
that you might care about if you want to poke around.
Now, printf is about to execute, so let me go ahead and just type "next."
Because we're in this environment we're not actually seeing it
execute down here, but notice it's getting a little mangled here.
But notice it's overriding the screen there,
so it's not a perfect program here, but that's okay because I can always poke around
using print if I want.
>> Let me type next again, and now here's the interesting part.
At this point in the story y is 2, and x is 1,
as suggested here, and again,
the reason this is automatically displaying now is because I used the command
display x and display y, so the moment I type next
in theory x and y should become swapped.
Now, we already know that's not going to be the case,
but we'll see in a moment how we can dive deeper to figure out why that's true.
Next, and unfortunately, y is still 2 and x is still 1, and I can confirm as much.
Print x, print y.
Indeed, no swapping has actually happened, so let's start this over.
Clearly swap is broken.
Let's instead type "run" again.
Let me say yes, I want to restart it from the beginning, enter.
>> Now I'm back up at line 18.
Now notice x and y are garbage values again.
Next, next, next, next.
If I get bored I can also just type n for next.
You can abbreviate it to the shortest possible sequence of characters.
Swap is now broken.
Let's dive in, so instead of typing next,
now I'm going to type step so that I'm stepping inside of this function
so that I can walk through it, so I hit step and then enter.
Notice that the highlighting jumps down lower in my program to line 36.
Now what are the local variables?
Info locals.
Nothing just yet because we've not gotten to that line,
so let's go ahead and say "next."
Now we seem to have tmp, print tmp.
Garbage value, right? I think so.
How about print a, print b, 1 and 2?
In a moment, as soon as I type next again
tmp is going to take on a value of 1, hopefully,
because tmp is going to be assigned the value of a.
>> Now let's do print a, print b,
but now print tmp, and it's indeed 1.
Let me do next. Let me do next.
I've finished the swap function.
I'm still inside of it in line 40, so let me print a,
print b, and I don't care what tmp is.
It looks like swap is correct when it comes to swapping a and b.
But if I now type next, I jump back to line 25,
and of course, if I type in x and print y
they're still unchanged, so we haven't fixed the problem.
But diagnostically now perhaps with this GDB program
we've at least gotten one step closer to understanding
what's going wrong without having to litter our code by putting a printf here,
printf here, printf here and then running it again and again
trying to figure out what's going wrong.
>> I'm going to go ahead and quit out of this altogether with quit.
It's going to then say, "Quit anyway?" Yes.
Now I'm back at my normal prompt, and I'm done using GDB.
As an aside, you don't need to use this -tui flag.
In fact, if you omit it you get essentially the bottom half of the screen.
If I then type break main and then run
I can still run my program, but what it will do is more textually
just show me the current line one at a time.
The -tui, textual user interface,
just shows you more of the program at once, which is probably a bit conceptually easier.
But indeed, I can just do next, next, next,
and I'm going to see one line at a time, and if I really want to see what's going on
I can type list and see a whole bunch of neighboring lines.
>> There's a video that we've asked that you watch for problem sets 3
in which Nate covers some of the intricacies of GDB,
and this is one of those things, honestly, where some non-trivial percentage of you
will never touch GDB, and that will be a bad thing
because literally you will end up spending more time later this semester
chasing down bugs then you would if you put in that half hour/hour
this week and next learning to get comfortable with GDB.
Printf was your friend.
GDB should now be your friend.
>> Any questions on GDB?
And here's a quick list of some of the most powerful and useful commands.
Yeah.>>Can you print a string?
Can you print a string? Absolutely.
It doesn't have to just be integers.
If a variable s is a string just type in print s.
It will show you what that string variable is.
[inaudible-student]
It will give you the address and the string itself.
It will show you both.
And one last thing, just because these are good to know too.
Backtrace and frame, let me dive into this one last time,
same exact program with GDB.
Let me go ahead and run the textual user interface version,
break main.
Let me go ahead and run again. Here I am.
Now let me go next, next, next, next, next, step, enter.
>> And now suppose I'm now in swap deliberately, but I'm like "Damn, what was the value of x?"
I can't do x anymore.
I can't do y because they're not in scope.
They're not in context, but no problem.
I can type backtrace.
That shows me all of the functions that have executed up to this point in time.
Notice that the one on the bottom, main, lines up with main
being on the bottom of our picture here.
The fact that swap is above it lines up with swap being above it in memory here,
and if I want to get back to main temporarily I can say "frame."
What number? Main is frame #1.
I'm going to go ahead and say "frame 1."
>> Now I'm back in main, and I can print x, and I can print y,
but I can't print a or b.
But I can if I say, "Okay, wait a minute. Where was the swap?"
Let me go ahead and say "frame 0."
Now I'm back where I want to be, and as an aside,
there's other commands too, like if you're really getting bored typing next, next, next, next,
you can generally say things like "next 10," and that will step through the next 10 lines.
You can also write "continue" when you really get fed up with stepping through it.
Continue will run your program without interruption until it hits another breakpoint,
whether in a loop or lower down in your program.
>> In this case we continued to the end, and the program exited normally.
This is a fancy way, inferior process.
Just your program exited normally.
More on that in the video and in debugging sessions to come.
That was a lot.
Let's take our 5-minute break here, and we'll return with structs and files.
>> If you have dived into this week's pset already
you'll know that we use in the distribution code,
the source code that we provide to you as a starting point, some new techniques.
In particular, we introduced this new keyword called struct, for structure,
so that we can create customized variables of sorts.
We also introduced the notion of file I/O, file input and output,
and this is so that we can save the state
of your Scramble board to a file on disc
so that the teaching fellows and I can understand
what's going on inside of your program without having to manually play
dozens of games of Scramble.
We can do this more automatedly.
>> This idea of a struct solves a fairly compelling problem.
Suppose that we want to implement some program
that somehow keeps track of information on students,
and students might have, for instance, an ID, a name
and a house at a place like Harvard, so these are 3 pieces of information
we want to keep around, so let me go ahead and start writing a little program here,
include stdio.h.
Let me do include cs50.h.
And then start my main function.
I won't bother with any command line arguments,
and here I want to have a student, so I'm going to say
a student has a name, so I'm going to say "string name."
Then I'm going to say a student also has an ID, so int id,
and a student has a house, so I'm also going to say "string house."
Then I'll order these a little more cleanly like this.
Okay, now I have 3 variables with which to represent a student, so "a student."
>> And now I want to populate these values, so let me go ahead and say something like
"id = 123."
Name is going to get David.
Let's say house is going to get Mather,
and then I'm going to do something arbitrarily like printf("%s,
whose ID is %d, lives in %s.
And now, what do I want to plug in here, one after the other?
Name, id, house; return 0.
Okay, unless I screwed up somewhere here
I think we have a pretty good program that stores one student.
Of course, this is not all that interesting. What if I want to have 2 students?
That's no big deal. I can support 2 people.
Let me go ahead and highlight this and go down here,
and I can say "id = 456" for someone like Rob who lives in Kirkland.
>> Okay, wait, but I can't call these the same thing,
and it looks like I'm going to have to copy this,
so let me say that these will be David's variables,
and let me get some copies of these for Rob.
We'll call these Rob's but this isn't going to work now
because I have—wait, let's change me to id1, name1 and house1.
Rob will be 2, 2.
I've got to change this here, here, here, here, here, here.
Wait, what about Tommy? Let's do this again.
Obviously if you still think this is a good way of doing this, it's not,
so copy/paste bad.
But we solved this a week ago.
>> What was our solution when we wanted to have multiple instances of the same data type?
[Students] An array.
An array, so let me try to clean this up.
Let me make some room for myself at the top, and let me instead do this here.
We'll call these people, and instead I'm going to say "int ids,"
and I'm going to support 3 of us for now.
I'm going to say "string names," and I'll support 3 of us,
and then I'm going to say "string houses," and I'm going to support 3 of us.
Now in here instead of David getting his own local variables
we can get rid of those.
That feels good that we're cleaning this up.
I can then say David is going to be [0] and names[0]
and houses[0].
And then Rob we can similarly save on this.
Let's put this down here, so he's going to arbitrarily be ids[1].
He's going to be names[1],
and then lastly, houses[1].
>> Still a little tedious, and now I have to figure this out,
so let's say "names[0], id[0], houses[0],
and let's pluralize this.
Ids, ids, ids.
And again, I'm doing it, so again, I'm already resorting to copy/paste again,
so odds are there's another solution here.
I can probably clean this up further with a loop or something like that,
so in short, it's a little better but still feels like
I'm resorting to copy/paste, but even this, I claim,
is not really fundamentally the right solution because
what if sometime we decide you know what?
We really should have been storing email addresses for David and Rob
and everyone else in this program.
We should also store phone numbers.
We should also store emergency contact numbers.
We have all these pieces of data that we want to store,
so how do you go about doing that?
>> You declare another array at the top, and then you manually add
an email address[0], email address[1]
for David and Rob and so forth.
But there's really just an assumption underlying this design
that I am using the honor system to know that
[i] in each of the several arrays
just so happens to refer to the same person,
so [0] in ids is number 123,
and I'm going to assume that names[0]
is the same person's name and houses[0]
is the same person's house and so forth for all of the various arrays that I create.
But notice that there's no fundamental linkage
among those 3 pieces of information, id, name and house,
even though the entity we're trying to model in this program is not arrays.
Arrays are just this programmatic way of doing this.
What we really want to model in our program is a person
like David, a person like Rob inside of which
or encapsulating is a name and ID and a house.
>> Can we somehow express this idea of encapsulation
whereby a person has an ID, a name and a house
and not resort to really this hack whereby we just
trust that bracket something
refers to the same human entity in each of these disparate arrays?
We can actually do this.
Let me go above main for now, and let me create my own data type
for really the first time.
We used this technique in Scramble,
but here I'm going to go ahead and create a data type,
and you know what, I'm going to call it student or person,
and I'm going to use typedef for define a type.
I'm going to say that this is a structure,
and then this structure is going to be of type student, we'll say,
even though it's a little dated now for me.
We'll say "int id."
We'll say "string name."
Then we'll say "string house,"
so now by the end of these few lines of code
I have just taught clang that there exists
a data type besides ints, besides strings, besides doubles, besides floats.
>> As of this moment in time line 11, there is now a new data type called students,
and now I can declare a student variable anywhere I want,
so let me scroll down here to people.
Now I can get rid of this, and I can go back down to David here,
and for David I can actually say that David,
we can literally name the variable after myself,
is going to be of type student.
This might look a little weird, but this isn't all that different
from declaring something as an int or a string or a float.
It just so happens to be called student now,
and if I want to put something inside of this structure
I now have to use a new piece of syntax, but it's pretty straightforward,
david.id = 123, david.name = "David" in capital D,
and david.house = "Mather,"
and now I can get rid of this stuff here.
Notice we've now redesigned our program in really a much better way
in that now our program mirrors the real world.
>> There's a real-world notion of a person or a student.
Here we have now a C version of a person or more specifically a student.
Inside of that person are these relevant characteristics,
ID, name and house, so Rob essentially becomes the same thing down here,
so student rob, and now rob.id = 456,
rob.name = "Rob."
The fact that the variable is called Rob is sort of meaningless.
We could have called it x or y or z.
We just named it Rob to be semantically consistent,
but really the name is inside of that field itself,
so now I have this.
This too doesn't feel like the best design in that I've hard coded David.
I've hard coded Rob.
And I still have to resort to some copy and paste every time I want new variables.
Moreover, I have to apparently give each of these variables a name,
even though I'd much rather describe these variables
more generically as students.
>> Now we can merge the ideas that have been working well for us
and instead say, "You know what, give me a variable called students,
and let's have it be of size 3," so now I can refine this further,
get rid of the manually declared David,
and I can instead say something like students[0] here.
I can then say students[0] here,
students[0] here, and so forth, and I can go around
and clean that up for Rob.
I could also go about now maybe adding a loop
and using GetString and GetInt to actually get these values from the user.
I could go about adding a constant because this is generally bad practice
to hard code some arbitrary number like 3 right here
and then just remember that you should put no more than 3 students in it.
It would probably be better to use #define at the top of my file
and factor that out, so indeed, let me go ahead and generalize this.
>> Let me open up an example that's among today's
examples in advance, structs1.
This is a more complete program that uses #define up here
and says we're going to have 3 students by default.
Here I'm declaring a class worth of students,
so a classroom of students, and now I'm using a loop
just to make the code a little more elegant, populate the class
with the user's input, so iterate from i = 0 on up to students, which is 3.
And then I prompt the user in this version
what's the student's ID, and I get it with GetInt.
What's the student's name, and then I get it with GetString.
What's the student's house? I get it with GetString.
And then at the bottom here I just decided to change
how I'm printing these out and to actually use a loop,
and who am I printing?
According to the comment I'm printing anyone in Mather,
and that's it so Rob and Tommy and so forth—actually Tommy's in Mather.
Tommy and David would be printed in this case, but how is this working?
We haven't seen this function before, but take a guess as to what this does.
Compares strings.
>> It's a little non-obvious how it compares strings because it turns out
if it returns 0 that means the strings are equal.
If it returns a -1 that means one comes alphabetically before the other,
and if it returns +1 that means the other word comes alphabetically
before the other, and you can look online or at the man page
to see exactly which way is which, but all this is now doing is it's saying
if the [i].house is equal to "Mather"
then go ahead and print out so and so is in Mather.
But here's something we haven't seen before, and we'll come back to this.
I don't recall ever having to do this in any of my programs.
Free is apparently referring to memory, freeing memory,
but what memory am I apparently freeing in this loop at the bottom of this program?
It looks like I'm freeing a person's name
and a person's house, but why is that?
>> It turns out all these weeks that you've been using GetString
we've kind of been introducing a bug into every one of your programs.
GetString by design allocates memory so that it can return to you a string,
like David, or Rob, and you can then do whatever you want
with that string in your program because we've reserved the memory for you.
The problem is all this time every time you call GetString
we, the authors of GetString, have been asking the operating system
to give us a bit of RAM for this string.
Give us a bit of RAM for this next string.
Give us some more RAM for this next string.
What you, the programmer, have never been doing
is giving us that memory back,
so for these several weeks all of the programs you've written
have had what's called a memory leap whereby they keep using
more and more memory every time you call GetString, and that's fine.
We deliberately do that in the first weeks because it's not that interesting
to have to worry about where the string is coming from.
All you want is the word Rob to come back when the user types it in.
>> But moving forward we now have to start getting more sophisticated about this.
Any time we allocate memory we better eventually hand it back.
Otherwise in the real world on your Mac or PC you might have occasionally experienced
symptoms where your computer is grinding to a halt eventually
or the stupid spinning beach ball is just occupying the computer's
entire attention and you can't do things.
That can be explained by any number of bugs, but among those possible bugs
are things called memory leaks whereby someone who wrote that piece of software
you're using didn't remember to free memory
that he or she asked the operating system for,
not using GetString, because that's a CS50 thing, but using similar functions
that ask the operating system for memory.
If you or they screw up and never actually return that memory
a symptom of that can be that a program slows and slows and slows down
unless you remember to call free.
>> We'll come back to when and why you would call free,
but let's go ahead just for good measure and try running this particular program.
This was called structs1, enter.
Let me go ahead and run structs1, 123, David Mather,
456, Rob Kirkland, 789,
Tommy Mather, and we see David's in Mather, Tommy's in Mather.
This is just a little sanity check that the program is working.
Now, unfortunately, this program is a little frustrating in that
I did all that work, I typed in 9 different strings, hit enter,
was told who was in Mather, yet obviously I knew who was in Mather already because I typed it.
It would be at least nice if this program is more like a database
and it actually remembers what I have typed in
so I never again have to input these student records.
Maybe it's like a registrarial system.
>> We can do this using this technique known as file I/O, file input and output,
a very generic way of saying any time you want to read files or write files
you can do this with a certain set of functions.
Let me go ahead and open this example structs2.c,
which is almost identical, but let's see what it now does.
At the top of the file I declare a class of students.
I then populate the class with the user's input,
so those lines of code are exactly like before.
Then if I scroll down here I print everyone who is in Mather arbitrarily like before,
but this is an interesting new feature.
These lines of code are new, and they introduce something here,
FILE, all caps, and it has * in here as well.
Let me move this over here, a * over here as well.
>> This function we haven't seen before, fopen,
but it means file open, so let's skim through these,
and this is something we'll come back to in future psets,
but this line here essentially opens a file called database,
and it specifically opens it in such a way that it can do what to it?
[inaudible-student]
Right, so "w" just means it's telling the operating system
open this file in such a way that I can write to it.
I don't want to read it. I don't want to just look at it.
I want to change it and add stuff potentially to it,
and the file is going to be called database.
This could be called anything.
This could be database.txt. This could be .db.
This could be a word like foo, but I arbitrarily chose to name the file database.
This is a little sanity check that we'll come back to in great detail over time,
if fp, for file pointer, does not equal NULL that means all is well.
>> Long story short, functions like fopen sometimes fail.
Maybe the file doesn't exist. Maybe you're out of disc space.
Maybe you don't have permission to that folder,
so if fopen returns null something bad happened.
Conversely, if fopen does not return null all is well
and I can start writing to this file.
Here's a new trick.
This is a for loop that's iterating over each of my students,
and this looks so similar to what we've done before,
but this function is a cousin of printf called fprintf for file printf,
and notice it's different in only 2 ways.
One, it starts with f instead of p,
but then its first argument is apparently what?
[Students] File.>>It's a file.
This thing called fp, which we'll eventually tease apart what a file pointer is,
but for now fp simply represents the file that I have opened,
so fprintf here is saying print this user's ID to the file, not to the screen.
Print the user's name to the file, not to the screen,
the house to the file, not to the screen, and then down here, obviously,
close the file, and then down here free the memory.
>> The only difference between this version 2 and version 1
is the introduction of fopen and this FILE with *
and this notion of fprintf, so let's see what the end result is.
Let me go into my terminal window.
Let me run structs2, enter.
Looks like all is well. Let's rerun structs2.
123, David Mather, 456, Rob Kirkland,
789, Tommy Mather, enter.
Looks like it behaved the same, but if I now do ls
notice what file is in here among all my code, database,
so let's open that, gedit of database, and look at that.
It's not the sexiest of file formats.
It really is one piece of data line per line per line,
but those of you who use Excel or CSV files, comma separated values,
I could certainly have used fprintf to instead maybe do something like this
so that I could actually create the equivalent of an Excel file
by separating things with commas, not just new lines.
>> In this case if I had instead used commas instead of new lines
I could literally open this database file in Excel if I instead made it look like this.
In short, now that we have the power to write to files
we can now start persisting data, keeping it around on disc
so that we can keep information around again and again.
Notice a couple of other things that are now a bit more familiar.
At the top of this C file we have a typedef
because we wanted to create a data type that represents a word,
so this type is called word, and inside of this structure
it's a little fancier now.
Why is a word made up of apparently an array?
What is a word just intuitively?
>> It's an array of characters.
It's a sequence of characters back to back to back.
LETTERS in all caps happens to be we arbitrarily say the maximum length
of any word in the dictionary that we're using for Scramble.
Why do I have a +1?
The null character.
Recall when we did the Bananagrams example we needed a special value
at the end of the word in order to keep track
of where words actually ended, and as the problem set specification says
here we're associating with a given word a boolean value,
a flag, so to speak, true or false.
Have you found this word already, because we realize
we really need a way of remembering not only what a word is in Scramble
but whether or not you, the human, have found it
so that if you do find the word "the" you can't just type the, enter, the, enter, the, enter
and get 3 points, 3 points, 3 points, 3 points.
We want to be able to blacklist that word by setting a bool
to true if you've already found it, and so that's why we
encapsulated it in this structure.
>> Now, down here in Scramble there's this other struct called dictionary.
Absent here is the word typedef because in this case
we needed to encapsulate the idea of a dictionary,
and a dictionary contains a whole bunch of words,
as implied by this array, and how many of those words are there?
Well, whatever this variable called size says.
But we just need one dictionary.
We don't need a data type called dictionary.
We just need one of them, so it turns out in C
that if you don't say typedef, you just say struct, then inside the curly braces
you put your variables, then you put the name.
This is declaring one variable called dictionary
that looks like this.
By contrast, these lines are creating a reusable data structure called word
that you can create multiple copies of, just like we created
multiple copies of students.
>> What does this ultimately allow us to do?
Let me go back into, let's say, a simpler example from simpler times,
and let me open up, let's say, compare1.c.
The problem here at hand is to actually peel back
the layer of a string and start taking off these training wheels
because it turns out that a string all this time
is as we promised in week 1 really just a nickname,
a synonym from the CS50 library for something that looks a little more cryptic,
char*, and we've seen this star before.
We saw it in the context of files.
>> Let's now see why we've been hiding this detail for some time now.
Here is a file called compare1.c,
and it apparently asks the user for 2 strings, s and t,
and then it tries to compare those strings for equality in line 26,
and if they're equal it says, "You typed the same thing,"
and if they're not equal it says, "You typed different things."
Let me go ahead and run this program.
Let me go into my source directory, make a compare1. It compiled okay.
Let me run compare1.
I'll zoom in, enter.
Say something. HELLO.
I'll say something again. HELLO.
I definitely didn't type different things.
>> Let me try this again. BYE BYE.
Definitely not different, so what's going on here?
Well, what is really being compared in line 26?
[inaudible-student]
Yes, so it turns out that a string, data type, is kind of a white lie.
A string is a char*, but what is a char*?
A char*, as they say, is a pointer,
and a pointer is effectively an address,
a sum location in memory, and if you happen to have typed in a word like HELLO,
recall from past discussions of strings
this is like the word HELLO.
Remember that a word like HELLO can be represented
as an array of characters like this
and then with a special character at the end called the null character,
as the \ denotes.
What is actually a string?
Notice that this is multiple chunks of memory,
and in fact, the end of it is only known once you look through the whole string
looking for the special null character.
But if this is a chunk of memory from my computer's memory,
let's arbitrarily say that this string just got lucky,
and it got placed at the very beginning of my computer's RAM.
This is byte 0, 1, 2, 3, 4, 5, 6...
>> When I say something like GetString and I do string s = GetString
what's really being returned?
For these past several weeks, what's really being stored in s
is not this string per se, but in this case what's being stored is
the number 0 because what GetString actually does
is it doesn't physically return a string.
That doesn't even really make conceptual sense.
What it does return is a number.
That number is the address of HELLO in memory,
and string s then, if we peel back this layer, string doesn't really exist.
It's only a simplification in the CS50 library.
>> This really is something called char*.
Char makes sense because what's a word, like HELLO?
Well, it's a series of chars, a series of characters.
Char* means the address of a character,
so what does it mean to return a string?
A nice, simple way of returning a string
is rather than try to figure out how I return to 5 or 6 different bytes
let me return to the address of which byte?
The first one.
In other words, let me give you the address of a character in memory.
That's what char* represents, the address of one single character in memory.
Call that variable s.
Store in s that particular address, which I arbitrarily said is 0,
just to keep things simple, but in reality it's generally a bigger number.
>> Wait a minute.
If you're only giving me the address of the first character, how do I know what the address is
of the second character, the third, the fourth and the fifth?
[inaudible-student]
You only know where the end of the string is by way of this handy trick,
so when you use something like printf, what printf literally takes as its argument,
recall that we use this %s placeholder, and then you pass in
the variable that's storing a string.
What you're really passing is the address of the first character of that string.
Printf then uses a for loop or a while loop upon receiving that address,
for instance, 0, so let me do this now,
printf("%s\n,"s);
When I call printf("%s\n,"s); what I'm really providing printf with
is the address of the first character in s, which in this arbitrary case is H.
>> How does printf know what exactly to display on the screen?
The person who implemented printf implemented a while loop or a for loop
that says does this character equal the special null character?
If not, print it. How about this one?
If not print it, print it, print it, print it.
Oh, this one is special. Stop printing and return to the user.
And that's literally all that's been happening underneath the hood,
and that's a lot to digest in the first day of a class,
but for now it's really the building block of understanding everything
that's been going on inside of our computer's memory,
and eventually we'll tease this apart with a little help
from one of our friends at Stanford.
>> Professor Nick Parlante at Stanford has done this wonderful video sequence
from all sorts of different languages that introduced
this little Claymation character Binky.
The voice you're about to hear in just a few second sneak preview
is that of a Stanford professor, and you're getting
only 5 or 6 seconds of this right now,
but this is the note on which we'll conclude today
and begin on Wednesday.
I give you Pointer Fun with Binky, the preview.
[♪ Music ♪] [Professor Parlante] Hey, Binky.
Wake up. It's time for pointer fun.
[Binky] What's that? Learn about pointers?
Oh, goody!
>> We will see you on Wednesday.
[CS50.TV]