>> PROFESSOR: So the agenda for this week, not that much stuff.
But hopefully very, very helpful and relevant for you guys this week.
But we're going to spend maybe 15, 20 minutes just quickly talking
about link list.
Link lists are going to be covered on the quiz.
So perhaps it would be very helpful to learn a bit about what that is.
>> We're going to spend the vast majority of today's section
going over quiz zero practice problems.
And then we'll save maybe 20, 30 minutes at the end for any lingering questions
anyone has.
>> And then, the last five minutes, I'm going
to give a pump up speech for the quiz.
You guys all want to be here for that.
Because it's going to be a good time.
>> All right, so some material on link list.
How they're typically structured is you have what's called a node, right?
You have these things called nodes, which are structs.
I'll go over how to create a node in the next slide.
But essentially all linked lists is is data that
has been strung together via pointers.
>> And so the advantage we have of using a linked list over,
perhaps, like an array, is the fact that in an array
you need one contiguous block of memory all in the same place, one
after another, to be able to have that.
Whereas a linked list, you could have random little bits of memory
all over your computer strung together by pointers.
>> And in this way you can access information
that comes one after the other, after the other
without needing just a huge chunk of memory in your computer somewhere.
And so this is one of the major reasons why we use link list.
>> Secondly, it's very easy to dynamically resize the link list because in array,
when you declare an array, you have a certain set value.
Let's say I wanted to create an array of 10 integers.
I create an array of 10 integers, and that's it.
It's 10.
I don't know what to do after that.
If I wanted to make it 11, can't do it.
If I want to make it 9, can't do it.
>> Whereas in a link list, you can add and delete and insert wherever you want.
You can dynamically resize your structure here, your data structure.
And that gives us a lot more added flexibility
that we don't typically have with arrays.
>> Anyone confused on the basic structure of how a link list is
or why we have to use one over an array?
Yeah, we'll go over in detail how to actually create one.
But this is just kind of the general sense right now.
Cool.
And so arrays are strung together of these lovely little things
called nodes.
All a node is is a type of struct.
Remember, a struct is if you wanted to create a certain type of variable
in C that doesn't already exist, you, as a programmer,
can actually create that yourself.
>> And so this type of data structure is called a node,
has actually been created by us, that doesn't exist within C on its own.
And the way that you create one is you have
the header of typedef struct, which tells the compiler I'm
about to create a struct.
>> We're going name it "node."
And inside we're going to declare a variable in,
which is going to store a value.
And then we're also going to have a pointer called "next"
that points to the next node in the link list.
And then you finish that off by just repeating node again so
the compiler knows, OK that's the end of my struct.
>> And so in this way, we're kind of creating a cute little array
kind of thing with a value and with a pointer.
And you can link them all together with those pointers.
So that they can all kind be strung together in a chain.
>> Cool.
Can you hear that a bit better?
>> AUDIENCE: Yeah.
>> PROFESSOR: All right.
So the way that, as you guys can see, a typical link list is structured
is you have a head.
You have the head value which isn't being pointed by any other pointer.
But it's going to point at, or reference, another node.
The node after is going to reference the node after that, and so on and so forth
until you eventually hit the end of your link list.
And you just won't have a pointer there.
>> And so, think like, on a chain, or even if any of you guys made, I don't know,
like with Fruit Loops when you were little.
You would string them together and wear them around your neck.
Think it's the exact same thing.
You have these little things that you can string together that point to one
after it, to the one after it, and so on and so forth
until you have a chain of a data structure
that you can use however you like.
>> So the way that this we would typically insert or delete
any node from a link list is very different
depending on where that node is.
So, for example, because pointers are always
pointing at a specific value, when you delete or insert a node,
you want to make sure that the pointer is all pointing at the right things.
>> So if you wanted to potentially insert a new node with the value of one
inside a sorted link list, we all know here
from the picture that's going to go in between head and two, right?
Because one fits right there.
But the way in which we would do that is by first dereferencing the pointer
from head and sending that to one.
>> But we come into of a problem here.
Can anyone see what the problem is if we were to first dereference
the pointer from head to one?
What problem might we run into if we try to add this to the front of our array?
>> AUDIENCE: [INAUDIBLE]
PROFESSOR: Exactly.
So here we have a pointer that was once pointing from the head to two.
But if you get rid of that pointer, you point it to one,
we now have no idea where to go to find two.
Because as I said before, you've got a giant chunk of memory in your computer.
All these nodes could be randomly interspersed
in any place in your computer.
And you don't know how to go about finding that.
>> And so you need to have pointers pointing to all nodes at the end.
Or else if you accidentally dereference one
without first assigning a value first, you're
just going to lose everything afterwards.
>> So what we're going to do is, you would first
want to create a pointer on the node you want to insert.
Point it to where you want to insert it to,
and then afterwards you could point head back to one.
>> Does that make sense to everybody here?
Great.
Think of it as just like a chain.
If you add a chain, it's kind of intuitive
how you'd go about inserting that.
>> OK, so that is actually much shorter than I thought it would be,
a five-minute spiel on link lists.
Just so you guys have the basic idea of what that is.
>> Here we have the agenda for quiz zero.
Don't let this intimidate you.
I know it's a lot of information.
It looks very scary.
It's also a lot of, I think, CSC kind of terms.
Things like hexadecimal strings, pointers, dynamic memory allocations
are very scary sounding terms.
>> But we're going to break them down, do some practice problems
so that you guys all are ready for this test.
How many of you guys have already started studying?
>> OK, you guys probably want to start getting started
on that, because the quiz is tomorrow.
Or Thursday for some of you.
Yeah, so we're going to go over some practice problems.
If you guys all want to take out a sheet of paper, a pencil.
We're going to just spend the vast majority of today's section
going over some of that so you guys have an idea of what to expect on the quiz.
>> OK.
A couple of logistical details as well, for anybody
who has not been to that link there, if you go to cs50.yale.edu, on the front
this page there is a link that says "About Quiz Zero."
Link takes you there.
If you haven't read it, please read it.
Because it tells you really important information regarding the quiz.
>> I'm going to pull this out from that just because, physically,
if you guys don't know where to go, we will have problems.
And so if your last in terms with A to N, go to the law school auditorium.
And if your last starts with P to Z, go to Davies Auditorium.
And this only applies for people in the Wednesday section.
>> If you're taking the quiz on Thursday, you go to SSS 114
where your lecture typically is.
AUDIENCE: [INAUDIBLE]
PROFESSOR: O to Z, you're going to go to the Davies auditorium.
I'm going to change that, right?
>> Oh, yeah, you just fail automatically.
>> Oh yeah, that's you Christa.
Yeah, my bad.
Yep, O to Z, you're going to go to Davies Auditorim.
I'm going to fix this once I upload.
Yeah.
>> And then also something important to mind
is that Wednesday, if you are officially enrolled in the Wednesday section,
you must take your quiz on Wednesday.
And if you're enrolled in Thursday, you must take your quiz Thursday.
And it's during class time.
Where, I think it's like 1:00 to 2:15 on Wednesdays and 2:30 to 3:45
on Thursdays.
>> If you have an irreconcilable conflicts, Dean's excuses are the only thing,
unfortunately, we can take.
Because we have had a vast majority of requests
to switch from Wednesday to Thursday.
Which we can't honor unless we have a Dean's request.
>> OK.
So before we get started on a couple of the practice problems,
I'm just going to go over Andy's helpful tips for success.
You guys, when you study, you really want to practice writing code by hand.
The first time I ever took a CS quiz, I hadn't
practice writing code by hand before and it was extremely
shocking at how difficult it was.
>> When you guys don't get into the habit of typing out everything,
it comes very naturally being able to have autocompleted
brackets and semicolons there.
When you write it out by hand, sometimes it's
very, very easy to forget a semicolon, or forget to close a bracket,
or forget to close a colon, or something like that.
>> So when you write code by hand, it's a very different feel.
So you guys, when you're working through some of the practice problems,
it would good to really practice today.
Or tomorrow, I suppose, if you're taking the quiz on Thursday.
>> Secondly, we have the last, like, eight year's worth of practice
quizzes online.
This year's quiz will probably be very, very similar to all of them.
They're all very similar.
You kind of get into the style of the type of questions
that we ask, the type of functions that we'll write it in,
et cetera, et cetera.
>> So take the practice quizzes, especially under time constraints.
75 minutes to do the quiz is not a lot of amount of time.
It's very, very long.
And so you guys really want to make sure that you guys are
in the habit of writing code by hand quickly.
Because you don't want the first time to see a quiz of that length
be on your quiz.
You guys really want to make sure that you practice beforehand.
>> Fourth, you want to review the lecture and section slides.
You don't have to memorize things.
Actually, everyone is allowed a one sheet of white paper notes,
front and back.
You guys can type or write.
If you find yourself needing to memorize anything, put it down on that sheet.
>> I guarantee you, you don't want to be stuck in the middle of that quiz
being like, oh yeah, what's the runtime of this sort versus that sort.
Just put it down and copy it straight from your note sheet.
Then you can actually just use your brain to think about the problems
rather than having to recall facts.
And so really take advantage of any niche details
that you think you need to memorize, plop it down on the review sheet.
>> OK, any questions logistically regarding the quiz
before we start some quiz problems practice?
Yeah?
>> AUDIENCE: I haven't had a chance to look at the quiz [INAUDIBLE]
but is it going to be application mostly,
or is there also going to be, like, knowledge questions?
>> PROFESSOR: It's a lot.
So, the way that I would described the quiz
is-- I put together some practice problems
that I pulled from all the quizzes.
But you'll see that there's two main types of questions we'll ask you.
>> One is a very low level detail of stuff.
We'll give you a small chunk of code and say, is there an error here?
What would be printing out here?
What will this code produce, et cetera.
So very low level information details.
>> And on the flip side, we'll have very high level knowledge-based questions.
Can you explain what the difference between a binary search
and a linear search is?
Why would we want to use one over the other?
Perhaps, what is GDB?
Why do we want to use GDB?
Higher level, more fundamental understanding questions.
So you'll see a mixture of the two of them on your quiz.
>> Anything else before we head straight into it?
OK.
AUDIENCE: One more.
PROFESSOR: Oh, one more.
Sorry.
>> AUDIENCE: Yeah, it's all right.
So you're saying 75 minutes is too short, like it is unlikely
that we will finish?
Or, like, 75 minutes is exactly as much time
as we would need if we were appropriately prepared?
PROFESSOR: OK, so the quiz is challenging.
It is definitely challenging.
You will find yourself short on time.
You're probably going to hit, like 10, 15 minutes to go, and being like, shit.
I have so much left to do.
And that's totally fine.
Everyone's going to feel the same way.
>> Just be very aware of how much time you have.
And so that's why I tell you guys do the practice quizzes.
Because it really gives a great sense of what the quiz is going to be like.
So if you find yourself being able to finished the practice
quizzes in a good amount of time, you can pace yourself well,
then you won't have a problem on Wednesday or Thursday.
>> Cool.
So if everyone wants-- I think most people have sheets of paper
out already.
I'm going to essentially just give you sample questions,
give you guys, like, a few minutes to do them.
And we'll go over as a class what the answers to them are.
>> So this is a very typical early question we'll
ask you, just converting numbers between different bases.
Binary, as you guys can recall, is base two.
Decimal is base 10, or what we as humans typically interpret.
Hexadecimal is base 16, which is zero through nine as well as A through F.
>> So there's four numbers I'm asking you guys to convert here.
I'll give you like, three to four minutes to think through how
we would go about solving this.
>> AUDIENCE: Are we allowed calculators?
>> PROFESSOR: You won't need calculators, yeah.
I think basic addition, I think, is all you guys will be asked to do.
>> And just so I kind of have a sense of when everyone is done, look up,
wave, I don't know, smile, look happy if you're done.
Yeah.
Maybe a couple more minutes.
>> OK, let's bring it in.
I'm purposely going to give you guys less time
than you probably need to do some of these problems,
simply because I want to make sure that we get through a bunch of problems.
So no worries if you didn't have a chance to finish.
Totally OK as long as you have an idea of how to go about this.
So let's go ahead and do the first one.
>> So first, does anyone want to tell me in binary, what do each of these digits
represent in terms of their values?
Yeah?
>> AUDIENCE: Two to the power zero, two to one.
PROFESSOR: Exactly.
So.
>> Right, so typically when we're in base 10
all these represent are, like, 10 to the base of zero, right?
That's your one's place.
All your 10's place is is 10 to the power of one.
You 100's place is 10 to the power of two.
>> Whatever base you're in is going to do with the exact same thing,
just with a different base.
So binary, all that is is base two.
You're going to convert all the digits into two to whatever power
of that digit.
And so in this sense, we can have an easier way
of being able to add up or sum all the numbers in order
to convert into base 10.
>> So does anyone want to tell me what the answer to the first one is in base ten?
>> AUDIENCE: Two, [INAUDIBLE]
PROFESSOR: Yeah.
AUDIENCE: 42.
PROFESSOR: 42, there you go.
So the way we got this answer was by doing two the first, which is two.
Plus two the third, which is eight.
Plus two to the fifth, which is whatever is left over.
You sum them up and it's 42.
>> Is anyone confused on how we got that?
So basic addition, like I said, you should be OK.
If not, well, we can practice that too.
But that's all right.
Cool.
>> Does anyone want to give me the answer to the second one as well?
>> 50?
Good.
Anyone confused on how we got that either?
Cool, I'll have the answers on the next slide.
So no worries if you need to copy it down.
>> OK, so hexadecimal is a bit trickier.
but I'm going to show you guys a shortcut for how to do it.
So hexadecimal, as you remember, all it is be 16.
And because we as humans don't actually have 16 numbers to represent that,
we go from zero to nine, which our first 10 values, and then we do A through F,
which are the next six values.
>> And so the easiest way to go from any binary number to hexadecimal
is to break them up into halves.
And so any binary number we'll give you will probably have eight digits.
You can just break them up in the middle.
>> So the first one-- one one, one one, one, one, one one.
Kind of think it up, you know, draw a slash or a comma in between them.
And you can just convert directly whatever
this is to the first number of hexadecimal,
and whatever here is to the second of hexadecimal.
>> So remember from common notation, what do hexadecimal values start with?
>> AUDIENCE: Zero.
>> PROFESSOR: 0X.
So we know that any time we ask you to convert any number to hexadecimal,
or any time you see any number that starts with 0X,
you know that it's a hexadecimal value.
>> And then you're going to be asked to determine what these two digits are.
And the way you do that, tallying up that half and tallying up that half.
So in this example, what would one, one, one, one be?
What value would that be?
That'd be F, right?
That'd be 15.
>> So this would be F. One, one, one, one here is also
F. So one, one, one, one, one, one, one, one in hexadecimal, all it is is 0XFF.
Because this half represented F, the value of 15,
and this half represented F, the value 15.
Because remember, we're counting from zero to nine.
A is like 10, B is like 11, F is 15.
>> Does that make sense to everybody how we got from binary to hexadecimal?
>> AUDIENCE: And so how did we get 15 from the one, one, one, one?
PROFESSOR: Yeah, this is binary, right?
Imagine this is just a binary number.
So you have two to the zeroth, which is one.
AUDIENCE: Oh, OK.
So you just total it out.
>> PROFESSOR: Yeah, and then you just total that out.
That's all it is.
>> AUDIENCE: OK.
>> PROFESSOR: OK.
>> AUDIENCE: So you go from binary to decimal to hexadecimal?
>> PROFESSOR: That's the easiest way to do so, yeah.
You're not going to decimal because decimal only has zero to nine.
We're just kind of splitting this up into two.
>> AUDIENCE: [INAUDIBLE] using decimal to find
what it matches up to in hexadecimal.
PROFESSOR: I mean, you're tallying up using basic math.
AUDIENCE: Yeah.
PROFESSOR: Yeah, pretty much.
It is a bit confusing.
But just know that you can divide up whatever
this value is into just halves.
Look, what is this in binary?
What number is that?
It's going to be something from zero to F.
>> Here is also going to be something from zero to F.
And then you can just put those two right there.
>> AUDIENCE: OK.
PROFESSOR: Yep.
OK.
So you guys want to try the next one then?
Zero, one, zero one, one, zero, one zero.
I'll give you guys like 30 seconds, since you probably didn't know
the trick to how to do this earlier.
>> OK, anyone want to get this one a shot?
>> 0X5A.
PROFESSOR: 0X5A.
5a.
Good.
So this here would be-- you want to tell us how you got that?
First, how did you get the five?
>> AUDIENCE: Because zero, one, zero, one is five.
>> PROFESSOR: Does everyone understand why zero, one, zero, one is five?
You've got one here.
You have nothing in two to the first.
In two to the second, you have one, which is four.
So you add the four plus the one, you have five.
Everyone good?
OK.
And then what this be and why?
What number does A correspond to?
>> AUDIENCE: 10.
>> PROFESSOR: And what this in base two?
AUDIENCE: [INAUDIBLE]
PROFESSOR: Exactly.
So this second value here would be 0X5A.
>> Everyone good on how to convert?
It's a lot simpler than you think it is.
I just want to make sure you know helpful tips
and tricks for how to do that.
>> AUDIENCE: Why can you just split it in the middle like that?
Just be like, OK, I'm only going to care about these first [INAUDIBLE]?
>> PROFESSOR: Because that's actually the way hexadecimal values are represented.
0X, that actually means nothing other than telling you
that it's a hexadecimal number.
And this always represents the first four digits.
And this always represents the last four digits.
And so these two digits just correspond to different bits.
>> AUDIENCE: So we will always--
>> PROFESSOR: You're always going to get eight value bits.
>> AUDIENCE: Is that just like a thing here or that a thing all over?
PROFESSOR: That's just a thing in computers, yep.
AUDIENCE: OK.
Awesome.
>> PROFESSOR: Also, so in this example we converted from binary to decimal,
and from binary to hexadecimal.
You guys want to make sure you also practice going the other way around.
So if I gave you 0XFF, you could draw that out in binary, right?
>> You convert F into binary, which is one, one, one, one,
convert F to binary, which is one, one, one, one.
>> So we may ask you to do the other way around.
So decimal to binary, or hexadecimal to binary.
So you want to make sure you know both ways.
We'll probably ask you a combination of the two.
>> Yeah, you have a question?
I can see-- you're good?
AUDIENCE: Yeah.
PROFESSOR: OK.
Am I good to erase this?
Great.
>> All right, so answers are here if anyone is curious later on and get confused.
OK.
>> AUDIENCE: Does it matter if we put our letters in capitol or lowercase?
>> PROFESSOR: It does, because in hexadecimal, by convention,
all the characters are uppercase.
So A through F are going to be uppercase.
If you put a lowercase a, I don't know if we would necessarily mark it wrong.
But theoretically, that's not technically
how you're supposed to have it.
So they should all be uppercase.
Yeah, good question.
>> OK.
Second question.
Consider this lovely program here.
I'll ask the question, I'll come back this.
>> So, firstly, what's inside of standard io.h that's of interest to the program?
Secondly, what does void signify in line three?
And third, what does returning zero from main, as line six, generally signify?
If you guys want to write those down, since I have to switch back
to the slide just so you can see code.
This is an example of, like, maybe a higher level question where we ask you
what things mean in a program.
>> Everyone good for me to go back to the slide?
OK, cool.
So I'll give you guys like maybe three minutes to look at this one real quick.
>> OK, so this one's like fairly easy, conceptually.
Does anyone want to tell me what's first inside by hash including
our standard io.h library file?
Why do we need that library included for this program?
What here do we need it for?
>> Yeah?
>> AUDIENCE: Is that when you put that printf?
>> PROFESSOR: Exactly.
So printf, any time you take an input from the user
and print something to the screen, that's
the standard input, output library.
Think of it that way-- input, output.
>> Do I have an output?
Yes, I do.
So I know that I'm always going to need the standardize i.o library.
>> So printf is the function by which we need to access
and hashtag include the standard i.o library.
OK.
>> Secondly, it what does void signify?
We have the int main(void), what does void here mean here on line three?
Yeah, in the back.
>> AUDIENCE: [INAUDIBLE]
>> PROFESSOR: Exactly.
So remember, we've learned starting with our pset
that you can actually specify command line
arguments that your program, that you main function, takes as you, the user,
call it.
If we have void, that means that you could just run the program directly
without any command line arguments.
Everyone clear on that?
OK.
>> And lastly why do we bother doing this return zero thing here?
Why do we even have an int main?
Why can't we just have void main void?
Yeah?
AUDIENCE: Just so that we can be sure that the program is
exiting successfully, as opposed to if it was numbered.
And we would know that that's a different kind of error.
>> PROFESSOR: Yeah, exactly.
This is just a very conventional thing that we do,
is that just at the end of your program, just to make sure
that your main function is running correctly,
we always want to do return zero.
Even though we may necessarily not see that printed anywhere.
>> Because as programmers, you know, if you have many different lines of code
and you don't know where these are going wrong,
and if an error happens you want to make sure that you get that error.
And so typically if something goes wrong we'll have a return of one just
to make sure we know that it is.
So if you see a return zero, that typically
means your program is executed successfully.
Good?
Cool.
>> OK, second program here.
Consider that.
And if you guys see a float, you guys can probably
have a good idea of what I'm about to ask you.
>> So when this program executes, as you can see,
I am declaring a float inside my main function.
I'm naming it "answer," and I'm setting that equal to one divided by 10.
I'm printing out, to one decimal place, that float.
And then I'm returning zero.
>> So when executing the program, think back to greedy now,
this program prints 0.0.
As we all know, hopefully we all know, one divided by 10 is not a 0.00,
it's 0.1.
But explain why this program thinks that 1 divided by 10 prints to 0.1 other
than 0.1?
I'll give you guys maybe like 30 seconds to just quickly think about that
and I'll go back to the program.
>> OK.
Anyone want to give it a shot?
In three sentences or less, because typically we're
going to restrict all answers to three sentences or less
so you don't just regurgitate random things onto your quiz.
>> Yeah, take a shot.
>> AUDIENCE: So I think there's this thing called, like, [INAUDIBLE]
So there might be, for instance, there might be, like, 0.09,
that where you print the first digit, it would be to 0.0?
>> PROFESSOR: Close, not quite.
Christabell?
>> AUDIENCE: You're dividing one and 10, and they're both integers.
And so the way that it's going to store it is as an integer.
And so the closest integer would be 0.0.
And so that's 0.1.
PROFESSOR: Yeah, that's really good.
That's the right answer.
So this is a very confusing concept for a lot of kids.
And I really want to make sure that this is reinforced in everyone's head.
>> So what we call floating point imprecision,
where the reason why a lot of your programs in greedy
didn't work initially was because you forgot to cast your variable.
So what Christabell said was entirely correct.
>> A float is inherently imprecise.
Because in a computer, right, we have a finite amount of bits of memory
we can use to represent numbers.
So, for example, this CS50 ID is-- I think it's a 64-bit computer.
>> A float can only be represented by a finite amount of those bits.
And so 0.1 with infinite zeros, that's was 0.1 is, right?
But we can't actually store that number in our computer.
We just don't have enough memory to do so.
>> And so the nearest approximation of what's stored in memory is actually
something like 0.000 something, something, something, something.
Which, once you truncate it, rounds down to 0.0.
>> And so this example is just one that demonstrates lots of issues
we have whenever we're trying to incorrectly do math
without casting as a different integer.
So just be wary of this happening.
>> On quizzes, if we give you a block of code and it's like,
what prints out at the end?
And if it's some random value you guys should know why that's happening.
Yeah?
>> AUDIENCE: Truncate is get rid of everything after a certain point?
[INAUDIBLE]
PROFESSOR: Yeah, so actually this is a really bad example,
because 0.100 whatever actually would truncate down to 0.1.
But if you were to run it-- I don't remember, because last year they
ran it on a different program.
They ran it in something called the CS50 Appliance, which
is different from the ID.
That was a 32-bit system, I think.
And so there were different numbers.
>> But essentially, just know that the whole concept of truncation
and how it just cuts things off.
And so if it rounds--
>> AUDIENCE: Without rounding.
>> PROFESSOR: Exactly.
Yeah.
Cool.
>> Hi, in the back.
We're just going over some quiz review questions.
>> All right.
So consider a different program here.
I'm going to give you guys a couple minutes to read over this.
This is something that was for a very recently that I think blew a lot of you
guys's minds.
But we're going to talk through this again just
to make sure you understand it completely.
OK.
Anyone need more time to read through this code?
OK.
>> So it seems to me that in this program I'm
creating two strings by using GetString.
One called s and one called t.
And if they're equal equals to each other,
it should print "You type the same thing."
>> But elsewise, it would print, "You typed different things," right?
Seems very, very simple.
But, however, if I actually try to write this program,
it seems that even when I input the exact same strings,
it still prints out, "You typed different things!"
Does anyone want to take a shot at why this program always
responds that the inputs are different, even
when the words themselves are the same?
>> So if I were to input-- David love to use an example like mom, right?
Lowercase M-O-M for S, T equals lowercase M-O-M.
If I ran this through that code, why would it
print out "you typed different things?"
>> Does anyone need more time to think about this?
OK, I think we're good.
Yeah?
>> AUDIENCE: OK, so it's something about where it's stored in the memory, right?
>> PROFESSOR: Yep.
>> AUDIENCE: Where it's like, if this string s is stored at memory spot--
I'm inventing this-- is zero.
PROFESSOR: Sure.
AUDIENCE: And string t is stored at memory spot,
like, 167, and then zero does not equal 167.
>> PROFESSOR: Exactly.
OK, so remember this incredible revelation we explained to you guys
this past week, that strings don't really exist?
When we create something called string we're, in reality,
creating something called char star.
Which all it is is a pointer to a string or to an array of chars.
>> And so in this example, if I were to input M-O-M the way
that my computer would store it is within memory backslash zero, right?
Those four characters, chars, would be stored somewhere.
>> And then these four characters, backslash zero,
are stored somewhere else, right?
I have no idea where the addresses are, they're somewhere in my computer.
But I don't exactly know where they are.
>> When I create a string s, all that really is
is a pointer to the start of this string.
And when I create this t value, all that is a pointer to here.
And so when you're trying to equate and check
to see if s is equals equals to t, the computer
is really just returning to you the address of this m
and the address of that m.
And because they're two separate pieces of data
that are stored in two different addresses in your computer,
your computer's never going to recognize them as being the same.
Does anyone want to give a shot at what we
would have to do if we wanted to correct this and have a correct running program
instead?
Think about that for a couple seconds.
What do we need to change to get this program functioning
the way we want it to function?
>> Yeah, want to take a stab at it?
>> AUDIENCE: Can we try to dereference the pointer and check through the array?
PROFESSOR: That's one way to do it.
So, what's your name again?
I'm sorry, remind me.
>> Zee: Zee.
PROFESSOR: Yeah, so what Zee suggested would absolutely work.
Right?
We could dereference the pointer and actually go and access
the physical data inside of here.
And we can just compare the whole screen.
>> We can say, OK, pointer, give me what's inside here.
It would return an m.
And I would say, pointer, give me what's inside here.
Return an m.
Do those match?
Yes.
Then we move on.
>> We keep checking the entire two strings all the way up until the end
and see if those are equal, if all the values are equal.
And if all the values are equal, then we know the strings are true.
Absolutely, that's how we would do it?
>> Does anyone confused on any of this?
The whole concept of how strings are really just pointers,
and how they don't really exist?
And why we get errors like the way we get it?
Because I guarantee you guys, pointers and string allocation and memory
are going to come up.
>> Yeah?
>> AUDIENCE: [INAUDIBLE] dereference it, you just put a star [INAUDIBLE]
PROFESSOR: Right.
So to derererence a pointer means to go to that address of the pointer
and obtain the data, the value there.
And the way to do that is star pointer.
Don't confuse that.
>> AUDIENCE: [INAUDIBLE].
>> PROFESSOR: Yeah.
AUDIENCE: So you can just write if star s equal equals star t.
>> PROFESSOR: Well, no.
No.
>> AUDIENCE: That's not good enough, right?
>> PROFESSOR: It's not, because you're only checking the first letter.
You're probably going to need some sort of a loop that
iterates through every single character in both strings.
Yeah.
So if you wanted to just check to see if they started with the same thing,
you can do if, star s is equal to star t.
Then you know that at least they started with the same character.
>> Yeah?
>> AUDIENCE: So the way you do that would be
like an embedded for loop or pointer?
PROFESSOR: Yeah.
Pretty much just a for loop.
Remember, David in class mentioned the free syntactic sugar?
And he had this very confusing thing of star t
plus one, where it would integrate through and it move the pointer?
The easier way of doing this is just t of i.
>> So it's just an array.
The way that you would have a for loop that ran from zero to i, where
i is the length of the string, you could just
write that instead of doing the whole pointer, reference thing.
So these things are exactly equivalent in your computer.
>> You guys probably won't need to know that,
but it's good to just kind of have in the back your mind.
Just know that the computer recognizes different blocks of code
as the same thing.
Because this is just far more user friendly for us to present it like it's
an array.
It's just easier.
>> AUDIENCE: So use strlen to like, get--
PROFESSOR: Yeah.
AUDIENCE: OK.
PROFESSOR: You could use strlen or, if you
didn't have strlen you can just do up until you hit backslash zero for both.
Either would work.
Yeah.
AUDIENCE: So it's to dereference every single character if we were actually
writing this code, we could just do t brackets i
like with the star in front of it?
>> PROFESSOR: Yeah, equals equals s bracket i, and then keep moving i
down up until you hit the end.
Yeah, that's what you would do.
And I'll actually have a next example of when we actually
write strlen so you guys will kind of get to play around with it a bit.
>> So is everyone clear on just memory, strings, pointers, quality addresses?
Some higher level concepts that you will for sure need to know on the quiz
tomorrow.
>> All right.
Good.
Yep.
OK, so one thing that we'll also ask you, as we do every year on a quiz, is,
suppose that you've forgotten (which we seem to forget to do annually)
in which header file strlen is declared.
And so we have to rewrite it ourselves.
>> Here are a list of guidelines that we can present you
guys where you get to assume that s the string will not be null.
You can assume that s will be terminated with a backslash zero.
So you know that's what it's going to end with.
>> And, for instance, that the length of hello would be five.
So you can assume that hello will be five, H-E-L-L-O.
You don't have to assume that the backside zero accounts for the length.
>> This last thing here, do not worry about integer overflow.
Does anyone remember what integer overflow is?
>> AUDIENCE: Goes beyond the length of the [INAUDIBLE].
>> PROFESSOR: Yeah, can you explain a bit, what does that mean?
>> AUDIENCE: So, I guess it goes back to the truncating example earlier.
But if you have just so many numbers that go beyond the number of bits
that you can actually assign it that it will just kind of cut off.
PROFESSOR: Yeah, so on a typical computer, how many bits do we have?
AUDIENCE: 32?
PROFESSOR: Yeah, 32, right.
And so that's, what, four billion, two billion?
Four billion, up to four billion positive integers, right?
Two billion negative, two billion positive,
depends on how you want to do it.
>> And so basically we can have enough integers that can go up
to two to the 31st minus 1, right?
Because once we hit two to the 32nd, we don't
have that much memory in our computer.
>> And so, theoretically, I could come up with a number
that is, like, two to the 46th.
It's a huge-ass number, but theoretically you could.
And so integer overflow is if you try to create an integer that goes beyond what
your computer is capable of storing.
>> And so you guys for this example don't have
to worry about us giving you a giant string that is two to the 32nd chars
long.
That would be really mean.
>> All right, so I'm just going to give you guys the base structure of this.
You're going to create a function called int strlen where
a pass in, a char star, or string, pointer to the string called s.
>> All right, everyone copy that down.
Cool.
Oops-- other way.
>> So this is kind of like a harder piece of problem,
so I'll give you guys maybe five to six minutes to kind of brainstorm
and write this function out.
>> AUDIENCE: We don't account for [INAUDIBLE],
we don't have to use integer?
>> PROFESSOR: No, you don't.
I'll give you guys a hint.
A while loop may be very useful here.
Yeah.
Here's
candy.
Candy will also be available for the quiz, I think.
So you guys will be all sugared up tomorrow.
Can I-- you got it.
>> AUDIENCE: OK.
PROFESSOR: Yeah.
>> Maybe 30 more seconds or so.
>> All right, if you're not done, no worries.
We'll move through this together.
OK.
So I'm going to just the layout the basic structure for this function here.
Int strlen.
First, does anyone want to tell me what that int signifies?
We need to have in this function.
>> AUDIENCE: Strlen [INAUDIBLE].
PROFESSOR: Exactly.
So whatever happens in here, we need to return an integer.
And as specified in the spec, we want to return--
Go for it guys, just keep going.
It's all good.
Eat it all so I don't have to take it back, actually.
The int just signifies that you're going to be returning an integer.
>> What is this char star s?
What does that mean?
>> AUDIENCE: Like, what's being input in.
PROFESSOR: Exactly.
And what is almost the same thing as char star?
AUDIENCE: String?
PROFESSOR: Exactly.
So all we're doing is giving this a pointer to a string.
OK.
Cool.
>> Also, don't forget, if we forget to give you these brackets,
don't forget to write them yourself.
Because theoretically, your code is incorrect if you forget to write them.
Just always pay attention.
Like, little things that you don't notice
when you're programming on your laptop, because your laptop does it for you?
Don't forget when you're writing by hand.
Yeah?
>> AUDIENCE: But how incorrect?
Like, do we get the whole problem wrong?
>> PROFESSOR: No, no.
Don't worry.
It's actually theoretically possible for you to get full points on a question
even if your code will never run in real life.
I suggest you don't try to make that happen.
For example, like if everything that's here is right,
but you forget a colon or a bracket, your code won't actually run.
But we may be merciful.
>> Yeah?
>> AUDIENCE: Do you have to comment on our handwriting?
>> PROFESSOR: No, no, no worries about that.
No commenting.
Style should be good.
Like, don't smush everything on one line.
We will not be happy with you if you do that.
>> Does anyone want to give me the first line?
Hint, it's very easy.
>> Yeah?
>> AUDIENCE: Int, n equals zero.
Just set up counter.
PROFESSOR: So we want some sort of a counter, right?
I'm just going to name it "count" for the sake of readability.
What do we want to set it equal to?
>> AUDIENCE: Zero.
PROFESSOR: Yep.
Semicolon.
It's also very weird drawing semicolons.
Just practice doing that.
>> So we want to first have a counter of type int.
Because we want to count up how many characters or letters are
in this string, right?
Very easy first step.
>> OK, maybe a bit more complex now, how are we going to do so?
Does anyone want to give me the line of code
that may be able to help loop through whatever this is?
>> Yeah, brave soul in the back?
>> AUDIENCE: OK, so while point asterisks, the yeah, star of s,
is not equal to zero, then do something?
PROFESSOR: That's really, really close.
Really close.
So I'm going to address two things with that.
First of all, it's not exactly zero.
What is it?
It's the null terminator, which is backslash zero.
So they're different in terms of how they're stored.
So you're really close.
>> And secondly, we don't want to just move the pointer.
We want to actually access the values, right?
And so how do we do that?
Very easy.
Don't think about pointers, don't think about memories.
Go back to week two of this course.
>> AUDIENCE: [INAUDIBLE].
PROFESSOR: As of, remember?
What are strings?
How are they stored in memory?
>> AUDIENCE: They're raised.
>> PROFESSOR: They are raised.
So how do we access each character inside?
>> AUDIENCE: [INAUDIBLE].
PROFESSOR: Exactly.
So while-- what goes inside here?
S of --
>> AUDIENCE: I.
>> PROFESSOR: Oh, i doesn't exist, does it?
>> AUDIENCE: Oh, count?
>> PROFESSOR: We can just use count, can't we?
>> AUDIENCE: Sorry, I called it i.
>> PROFESSOR: Yeah, it's all good.
We have a variable up here that's already been declared as our counter.
So why don't we just use that to move through the while loop?
Does that make sense?
>> So while s of count-- does anyone want to give me what happens after here?
AUDIENCE: It does not equal.
PROFESSOR: Does not equal, right?
It's the bang equals, exclamation point equals,
whatever you guys want to call it does not equal--
>> AUDIENCE: [INAUDIBLE].
>> PROFESSOR: Yeah.
Remember single quote is for a char, double quotes are for a string.
Be careful when using them.
So when we're looking through the array, the last character,
we know we don't want it to be backslash zero.
>> So while.
We are not at the end of the string.
What do we want to do inside?
>> AUDIENCE: We want to add to the counter so it counts plus plus?
PROFESSOR: Exactly.
So here we're going to do count, count plus plus.
Missing one more line.
We're almost there.
What are we forgetting to do?
>> AUDIENCE: Returning zero?
>> PROFESSOR: You want to return zero?
>> AUDIENCE: No, returning to strlen.
Wait.
PROFESSOR: Which is stored in?
AUDIENCE: Count.
Count.
PROFESSOR: Exactly.
So here we're going to return count.
>> Because what we're doing here ultimately--
we have a counter variable that's going to increment through our string.
We're going to keep going, keep going, around and around in this loop.
And while we're not on the end of this string, which is the null terminator.
>> And every time we go through it, we're adding to our counter.
And we're going further along in this array.
And at the end, once we hit the null terminator,
we know, oh, we can break, return the count.
We have our strlen.
>> Does everyone get how this was implemented?
While loops-- I know we haven't done too much with them,
but they're usually very, very useful if you
don't know what you're stopping condition necessarily has to be.
>> Question?
>> AUDIENCE: Can we write null on the while condition?
>> PROFESSOR: While?
Yeah, so in this problem I had you guys assume that s will not be null.
Because remember, theoretically, if I gave you
a pointer that was too large of memory, it would give you the null, right?
That's what the operating system would do.
>> So if I didn't tell you to assume s would be null, you need to check.
So up here, you would do, if s equals equals null, return one.
Something like that.
AUDIENCE: [INAUDIBLE] zero.
PROFESSOR: OK, I'll tell you why we can't do that.
Because remember in memory, right, here.
We'll go here.
>> You've got giant blocks of memory all with grids
that store different values, right?
And so all a string is-- for example, if we are to input hello,
it would be H-E-L-L-O backslash zero, right?
And then who knows, like random things that are in here after it.
>> We don't actually know what's there.
And so if you were to do instead of backslash zero,
null, it may not be null.
Because it just may mean some random other things
that don't belong in your string.
And so the way that we always know that a string ends is with a backslash zero.
And so that's always how we check to see the end of a string.
>> Null, all that means is if you have a non-existent pointer, first of all,
or if your memory is just so large that you can't return it, then it'd be null.
So be very careful when differentiating the difference between null
and the backslash zero.
Yeah.
>> Everyone OK with this?
OK.
>> So I had you guys write out strlen.
Feasibly we could also ask you write out A to I, remember that "Atwoa"
or whatever you guys want to call it?
That function in Vigenere and Caesar, that
converts an Ascii value to an integer?
That also has come up on past quizzes of functions we've asked you to write.
>> Pretty much any function that you've used and is
very easy to write yourself, sensors like is lower,
is upper, to lower, to upper.
Functions that would convert a string from lowercase to uppercase.
We all know how to do that, right?
It's pretty easy.
Just want to make sure that you can-- it's the same thought process.
You just iterate through and you turn things.
You either count or when you turn things differently.
>> I would suggest-- I don't know if we're going
to ask you to memorize what capital A or capital Z, or lowercase A or lowercase
z are in Ascii, but I would suggest perhaps writing that down in case
we do.
Just so you guys have a reference.
Like uppercase A is, what, 197?
And then lowercase is like 50 something.
65, yeah, there you go.
So just pretty much know the difference between them is 32.
That's pretty important.
Yeah.
Am I good on this?
OK.
>> AUDIENCE: We could theoretically write some
of these down as well on our little--
>> PROFESSOR: You theoretically could just copy the function down.
That's true.
>> AUDIENCE: Not [INAUDIBLE].
>> PROFESSOR: You guys have a sheet.
You guys have a note sheet.
You can type it.
You can write it.
You can do whatever you want with it.
Yeah.
So theoretically, if you want to, go for.
>> AUDIENCE: [INAUDIBLE] but we don't really
necessarily need to remember the value, we can just
use the to upper or to lower function, right?
PROFESSOR: Yeah.
But if we gave you a question that says write to upper,
then you would need to write it.
So you guys can assume that you guys have access to all functions,
but if you want to use to upper or to lower, what do you also have to do?
>> AUDIENCE: [INAUDIBLE] use CS50 [INAUDIBLE]
>> PROFESSOR: Is it CS50.h?
Be careful there.
>> So to upper, to lower, is upper, is lower,
functions that involve string manipulation are
all within either the Ascii or within the math library
or within the string library.
So if you guys use those functions, be careful to remember
to include that header.
So perhaps also something you want to include in your sheet,
what are the header?
What are the libraries you've been using?
What functions are inside those libraries?
It's important.
>> Yeah?
>> AUDIENCE: Could we just cop out and do hashtag
through the absolutely every letter we've ever
seen like on all of the questions?
>> PROFESSOR: You could.
I don't know how happy we're going to be to grade
that quiz when every piece of code is twice as long as it needs to be.
I don't know, we might take off a point for style.
But theoretically your code would be right.
You guys could cop out and just include everything.
That's fine too, yeah.
AUDIENCE: [INAUDIBLE].
PROFESSOR: Yeah.
I would suggest not doing that though.
Yeah.
AUDIENCE: Cool.
PROFESSOR: Good question.
AUDIENCE: So, the worst case scenario.
PROFESSOR: The worst case.
If you totally forget, you could do that.
Yeah.
>> Yep, code is right there.
I used n instead of count but, you know, whatever floats your boat.
AUDIENCE: Wait, so we wouldn't have to hashtag
include because we're starting at the int?
>> PROFESSOR: Yeah, I just assumed that we were asked to write the function.
If you wanted to be safe, you could probably put it there.
But I just didn't bother, yeah.
>> I don't even know if you need any library for this.
Because you're not really printing out anything or anything, right?
Yeah, I don't know if you need a library.
>> OK.
This is also a bit more along the lines of memory manipulation.
This kind of bit tricky.
Think about this.
You have a function called func.
I could have named it whatever, but I choose to name it func.
I have it above my main.
Remember, you want to have a function after your main,
you want to make sure you include the prototype of the top.
>> But in this case it was so short that I felt that I could just
include it atop the main.
I didn't need to have the prototype, because it's already written above.
So all I'm doing in my main function is creating integer x equals 10.
I'm calling my func function, and then printing up something.
>> And then that's actually what func is doing.
You guys want to think through this.
Because it's a bit tricky.
It's very, very tricky, actually.
Think through what this program would be outputting.
I'll give you guys two minutes.
>> Good discussions?
>> AUDIENCE: Yeah.
>> PROFESSOR: Yeah.
All right, so this is tricky for a reason.
And this is why I wanted to bring this to everyone's attention.
Does anyone want to give me a suggestion, an attempt?
What would this print out?
Totally fine if you're wrong.
Yeah?
>> AUDIENCE: I think it's 100 and then 10 on two separate lines.
>> PROFESSOR: And a 10?
Does anyone have any other guesses?
Yeah?
>> AUDIENCE: Maybe just 10 because func is not returning anything?
>> PROFESSOR: OK, so we have guess number one
is that guess number two is just going to print out 10.
Does anyone have any other guesses?
OK.
So let's walk through this, right?
Whenever you get a piece of code, don't just look at it and be like,
ah, that's so much stuff!
I'm so confused!
Like, calm yourself down.
Just know that you could just look through code line by line.
That's all it is.
It's like reading a book.
>> So with any function, we always start at main.
So we're going to start at int main void,
even the program's already run down, right?
Start at in main void.
Int x equals 10.
>> So I'm going to erase this.
I'm going to draw the memory just so you guys can kind of see what's happening.
>> Remember down here we have our stack?
Up here we have our heap somewhere up here.
Stack grows up, right?
And within the stack, you have the mains function as well as
all of mains local variables.
>> So here, int x equal 10.
Within our main function we're creating a variable called x.
We're setting that equal to 10.
Here you've got some x, and you're setting that equal to 10, right,
within main.
Everyone good?
>> Function.
So now, within our main function, we're calling
the function we've written above.
So we're now enter the second function.
We're going to create another variable int x equals 100.
What's happening here at the stack?
What happens when you call a function that creates new variables?
What happens here at the stack?
>> AUDIENCE: [INAUDIBLE] piles on top?
PROFESSOR: Yeah.
So it actually creates a copy.
And it kind of piles on top.
Think of the stack-- a stack of books, a stack of anything.
Piles on top, first in last out, last in, first out.
>> So it's going to create an x here.
>> That's going to have all funcs variables.
Great.
So now we have two different x's that represent two very different things.
Then we're going to print out the integer of x.
So let's print 100, right?
Because here it's 100.
So that's the first thing that it's going to print out.
As this function returns nothing, now that function, that line in main
is done.
Everyone good with me so far?
>> So we're now through two out of the three lines of our main function.
Now we're going to the third line.
We're going to printf.
What is this x within main?
What does that represent?
>> What value is x now?
>> AUDIENCE: 100.
>> PROFESSOR: It's 100?
AUDIENCE: Still 10.
PROFESSOR: Still 10.
Yeah.
Because remember, within our func, x equals 100.
But if we return back to our main function,
that variable is stored in a different place on our stack.
>> So now we need to go back to the main stack, mains local variables.
And here x is equal to 10.
And so we're going to print out 10.
>> So she was absolutely right.
We're going to have the output of 100 and 10.
Yeah?
AUDIENCE: When you malloc, is it the heap or the stack that is [INAUDIBLE]?
PROFESSOR: When you malloc, you're taking memory from the heap
and allocating it.
So that you don't have to mess with any of this.
So I guess the bigger takeaway here is something called scope.
>> For those of you who were at the review session last night,
we talked briefly about this.
Scope defines how and when your variables exist.
Or within what frames do your variables exist.
>> Pretty much the rule of thumb generally is, your variables-- if you create them
inside curly braces-- they exist only inside those curly braces.
>> So for example in our function of func, you see those two braces.
If you're creating anything inside of it,
chances are all you're doing is creating a stack and storing that there.
Same thing in main.
That's just stored inside of main.
>> Also you want to be very, very careful here.
Because scope also lends itself to different examples.
So for example a for loop, for int i equals 0.
I is less than, I don't know, 10.
I plus plus.
And you've got code inside of it, right?
>> Where does this variable, i, actually only exist?
Only inside of your for loop.
So I bet many of you guys have probably encountered this error when
you're doing programs in your psets.
How many of you guys have tried to use i outside of a for loop and had an error?
Like an unreferenced integers or something like that?
>> The reason why that happens is because here you're
creating something that only exists within your for loop.
And if you try to use it, i doesn't actually exist outside of it.
So basically a computer saying, I don't know what you're talking about.
All I know is that an i was here, but now no longer.
>> So if I were to create a for loop inside, right?
And I'm going to create another, like int j, and have it do whatever.
And you have a code inside of that loop, j only exists here.
But that also exists within i.
And so j only exists within this for loop,
whereas i exists in the whole thing.
>> Everyone clear?
Same thing with conditional statements if you want to create anything.
Same thing with while loops if you want to create anything.
That's something to be very, very careful about.
So this was a really good problem in the sense that it demonstrated two things.
It demonstrated first, scope.
And it demonstrated also memory allocation.
Because you guys should know that functions grow upwards in the stack.
And that when you call functions, you're creating
essentially a new stack of memory.
That is very different from what your mains memory is.
Yeah.
Whew!
Everyone OK on that?
That was confusing.
Very good topics to go over, because you're probably
going to get some tricky things like that on the quiz.
Yeah.
Cool.
I'll put you get 100 on one line and then 10 on the other.
Yeah, very good.
>> OK, now you guys will get the chance to be the TAs.
You get to answer all the lovely emails that I sometimes get.
>> So, Dear Andi, I see I think something's going wrong with my compiler.
I'm certain that my code is correct, but I keep getting a segmentation fault
every time I run.
What's going on?
Please help, lots of love.
>> If you guys got something like that how would you respond?
These are actually very common questions we'll ask you.
Is if, we'll give you a scenario, we'll give us
your best guess at what's going on.
Anyone have a stab at what's going on?
Yeah?
>> AUDIENCE: Maybe dereferenced the null, something like the pointer
is pointing at something null.
PROFESSOR: Yeah, that'd be an example of when that would happen.
But what's the larger picture of what's going on here?
AUDIENCE: Is it you're trying to access memory that you're not
supposed to have access to?
PROFESSOR: Exactly.
So think of a seg fault, an off limits, restricted area in memory
that you should not be touching.
>> So pretty much when you're trying to index-- like for example,
you've declared an array from zero to nine.
But you try to touch that 10th value, you don't have access to that.
Because you haven't declared it.
And so your computer is going to look at that be like,
uh oh, you're trying to go outside the bounds of an index.
I'm going to give you a segmentation fault.
>> Think of as segment, right?
An extra segment, the fault is when you try to breach something
and you shouldn't be there.
Segmentation fault is anytime you try to touch things
that you shouldn't be touching.
>> So common examples are an index.
Of course, if you're trying to touch that was null,
that would also work as well.
If your pointer was trying to touch things that shouldn't touch,
that could also work as well.
Most typically you'll see this in an array.
Everyone good?
>> AUDIENCE: So if you want to access the 10th point
and there's only a limit of nine or something.
>> PROFESSOR: Yeah, exactly.
Pretty much.
Cool.
>> Dear Andi.
So we've got these wonderful things called sorts.
If Merge sort-- as we saw in example when
David did the whole thing in class-- why,
if it's so much faster than any of the other sorts,
why do we even bother knowing any of the other sorts?
>> What is this question really asking you?
What's the three word--
AUDIENCE: What's the trade-off?
PROFESSOR: Exactly.
That's what the question's asking.
What's the trade-off between Merge sort verses any other sorts?
>> AUDIENCE: Takes memory, right?
>> PROFESSOR: Do you explain that a bit more?
First let's explain Merge store.
How does Merge sort work?
>> AUDIENCE: So it works by dividing everything into half
and then putting it together and reallocating it in order,
like every time you merge the sets.
PROFESSOR: Pretty much.
So I can draw this out, but it would take me five minutes to draw it out.
Look back on to the section slides where we covered Merge sort.
Exactly.
>> So the way Merge sort works is it divides things in half,
and then it just looks at the first values of all of them
and sorts only that.
Continuously creates new arrays and puts things more and more in order.
And so while that's really, really fast because it's-- you know,
a binary search is n log of n.
You're creating so many different arrays that you're
using a huge amount of memory.
And so while it is faster, the trade off here is that you're using more memory.
>> And so, hint, sorts and searches were covered a lot more this year
than they have been in years previous.
You guys should see that reflected accordingly on the quiz.
I would definitely spend time going over what all of the different sorts
are, how binary search, how linear search work.
How to perhaps pseudocode code those out.
What are the running times?
Something like running times is very easy to copy down onto a note sheet,
right?
>> It's really hard when you're in the middle the test
and you have to figure that out.
Copy it down.
I guarantee you you're going to need to know that.
What are the trade-offs?
Worst case, best case scenarios for all of them, very get to know.
Yeah?
>> AUDIENCE: Do we need to know how to code Merge sort?
Like, do we need to remember the recursive?
>> PROFESSOR: I highly doubt it, just because it's like fairly complicated.
But it may not be infeasible if we ask you to use pseudocode it out.
Yeah.
>> Yep, OK, one more.
This may have come up in you last piece in a bit.
Yeah?
Did everyone hear that?
>> OK, so pretty much first of all, what type of program
would be giving you an output like this?
Remember we asked you to learn about this new type of debugging tool?
What was the name of it?
Valgrind, right
>> It was a program where you could call that could
keep track of all the memory you're using in your program and was going on.
So if you've got something, like, definitely lost, 40 bytes in one block.
Probably you're not remembering to free it.
Because if you're using bytes of memory, that means you've accessed that memory,
but you haven't been able to free.
So you want to make sure that you're also
using free-- that's a function-- to free all
of the memory reallocated by malloc.
>> Cool.
So this slide, I'll have it up.
It's everywhere in a lot of lectures, in a lot of section slides.
You really want to make sure you just know all of this.
Either in your note sheet or if you want to memorize it, feel free to.
That's really, really, really important.
>> Also a very good question that we may ask.
Why is Selection sort-- look at Selection sort-- all of the runtimes
are n squared.
Regardless of how the list comes to you as, so why is Selection sort--
I'll give you guys 30 second think about this.
Because it's kind of confusing.
It involves some conceptual thought.
Why would the run times be the same in both the worst and best case scenarios?
>> Yeah?
>> AUDIENCE: Because Selection sort each position or space in this little array
thing or whatever.
So even in the best case scenario, even if it's perfectly sorted,
it would still have to be like, OK, one.
In my first place I have one.
And go through all of them.
OK, one is the smallest.
And then it goes again and is like, OK, two
is the smallest of all of the things.
But it still has to check each and every one.
PROFESSOR: Yeah.
So for example, let's just say we have a list, already sorted,
an array one to five.
The way that Selection sorts is that it goes through, it checks these two.
Then it checks those two.
And then it checks, and it checks.
It keeps checking all of them, regardless of whether or not
it's actually sorted.
Because that's simply the way the sort works.
>> And so this question is kind of like a conceptual question we'll ask.
Where first, you to know what Selection sort
is, right, to be able to answer the question.
You have to be able to understand conceptually what's going on.
And then you can apply it and think, OK let's just imagine worst case scenario.
They're all in descending order.
How would that affect it?
>> What if it's ascending order?
If it's already sorted?
How would that affect the runtimes?
And then Selection sort, you'll notice that it doesn't actually matter.
Because you're checking all the values regardless of what's happening.
>> And so good things to remember.
Why some sorts differ from others and how best and worst case scenarios
would affect all of them.
>> I'm going to really hit in sorts because that will be on the quiz.
Yeah.
OK.
There's six minutes left.
I can take three minutes of questions.
I can also hang around for like 20 minutes after section
if you want to ask questions as well.
Does anyone just have really brief questions or conceptual issues
they're unclear about right now?
Yeah?
>> AUDIENCE: Can you talk a little bit about bitwise operators?
>> PROFESSOR: Yeah.
So bitwise operators are something that you probably
might just want to put on your sheet.
So quickly-- I don't want to go too much in depth
because Harvard, in their review session, covered it pretty well.
Bitwise operator, there's five of them, right?
>> There's this, which is x or function, there's ampersand, which is the and.
Pipe, which is the or.
And then you have the two different types of shifts.
>> If I give you two values, if I give you, like, one and one.
What would that evaluate to?
If I give you true and true, true?
What about true or false?
Still true, right?
Because there's an or.
We'll most likely give you numbers.
So remember, one equals true, zero equals false.
And we might give you these things and ask you to tell us what happens.
Harvard covers it within the first 10 minutes of their study session
really, really well.
So you guys want to make sure you look back on that.
>> AUDIENCE: Is pisa5 going to be on the quiz?
PROFESSOR: No.
Don't even look at pisa5 right now.
It's hard.
Just don't even bother looking at pisa5.
>> However, as some hints and suggestions, I
would suggest you start pisa5 as soon as the quiz is over.
This will be the hardest week, but then you guys
will be passed it on the hills of rolling green and puppies,
and it's fine.
>> This class gets significant easier after the fifth pset.
AUDIENCE: Office hours are Sunday, Monday?
PROFESSOR: Yeah, so office hours will the Sunday to Monday for the pset.
Office hours tonight essentially will just be review for the quiz.
If anyone wants to come in and ask the TAs a question, we'll be there.
>> I'll take maybe one more question if anyone has a question?
Yeah?
AUDIENCE: When you're defining nodes, [INAUDIBLE]
if you say node star and then next, does the computer automatically
understand that you're referring to another pointer?
>> PROFESSOR: No.
>> AUDIENCE: You have to relink it [INAUDIBLE]?
>> PROFESSOR: So basically the struct of a node is, remember,
it's like you create the node and then you have a pointer called next.
All you're doing is having the structure there.
You have to assign that pointer somewhere.
So the computers doesn't know what it's doing yet.
You have to actually assign it when you're creating your linked list.
And that's what mainly pset 5 will be on.
So no worries about any of that right now.
>> AUDIENCE: So we don't need to focus too much on link list, just
the general conception?
>> PROFESSOR: Just pretty much stacks, queues, link lists, trees, hash tables.
Just be able to know what they are.
We're not going to ask you like anything specific
because we haven't really done a pset that the covers any of that yet.
>> So in the last two minutes before I set you free to kill this quiz.
Pretty much, like, think about how far you guys have come in this class.
>> I remember when week two of this class, some of you
spend three hours writing water.
How long would it take you guys to write water now?
30 seconds, maybe?
Think about how much you guys have learned.
CS is a really, really hard subject.
There's no doubt of that.
It's hard, that's why no one studies it.
It's just hard.
And it's totally fine.
>> And I'm really proud that everyone has made it this far.
Psets are not easy.
They take a lot of time.
You guys, I will never ask you to write the game of 15 or Vigenere on the pset.
No need to just freak out about that.
All we're testing here is to evaluate your conceptual knowledge, as well
as some of your basic skills of coding.
The test is designed to be really challenging.
Like, it is designed for you to not get 100.
It's also designed for you to probably not be able to finish in 75 minutes.
And that's totally fine.
I'm a student myself.
I know, I hate it when I walk out of a quiz be like, shit.
That was really hard.
Probably what's going to happen-- and that's totally fine,
I'm telling you guys right now.
The means on these things are not high at all.
>> And for those of you who have been getting, like,
threes on your problem sets, that does not mean you're
going to get a 60 percent in this class.
If you get 60% on the quiz, that does not
mean you're going to get a D in this class.
We see, especially I, for those of you in my section,
I see how hard you guys are all working.
And I keep track of that.
>> You guys will be fine.
There's no institutional memory of happiness at the end of the semester.
Because all the Harvard kids are telling their friends, oh, you'll be fine.
No one is telling you guys that here.
So I have to tell you guys that here.
>> You guys will be fine.
I'm so proud of all of you guys.
The test will be hard.
Study for it, and afterwards just throw it away.
Get ready to learn new things.
And eat candy.
We've have lots of candy.
>> Get a good night's sleep.
Don't not sleep, because that'd be really bad.
CS is a lot of logic.
If you don't sleep, you can't function, and your brain can't function.
And I'll be here for the next 20 minutes if anyone wants to hang around.
You guys are going to kill it.
Good luck.