>> JASON HIRSCHHORN: Welcome to A5, everyone.
We have an exciting week ahead of us, mostly because there are so many new
faces in this room.
It's wonderful.
A lot of you are here by accident, which is even better.
So hopefully you'll keep joining us.
>> This week we're going to spend the bulk of section
preparing for the quiz.
So per our agenda, we're going to talk a bit about resources for the class,
but also for the quiz, and then, again, spend the bulk of class talking
about questions.
Once we're done answering your questions, or if your questions
naturally lead us to some coding, I have sample problems from midterms
past that we will code live in section together that also bring up some other
good topics to cover.
>> So first, as we've gone through for the past couple of weeks to remind you
guys, there are a ton of resources available for this course.
Many of them will be incredibly helpful to you as you continue to
study for quiz 0, because it's Tuesday afternoon.
So all of you have been studying for a bit.
>> There are lecture notes and source code that you should
definitely check out.
Watch the shorts.
Check out study.cs50.net.
And then, listed below, a number of other resources.
>> Again, quiz 0 is tomorrow at 1 o'clock.
If you haven't done so already, check out the About Quiz 0 document on the
course's homepage to figure out where you're taking the quiz.
The quiz starts at 1:10 and ends 70 minutes later.
So if you show up after 1:10, you're going to get that many fewer minutes
than 70 to take the quiz.
So make sure you're there on time.
If you're an extension student or have some other testing considerations, it
might not be at 1 o'clock tomorrow.
But again, check the About Quiz 0 document to make sure you know when
you're taking the quiz.
I wrote 75 minutes up here.
I think that's right, not 70.
>> It covers all the material from a week 0 to last week's lecture on Wednesday.
And again, for this quiz, per that document, you get one two-sided and 8
1/2 by 11 sheet of paper that you get to use as notes during the quiz.
Many people, if not most people, have found that the single most helpful way
to study for the quiz is to make a study sheet, a
one-sider, of their own.
So look at past ones if you've seen past ones.
Reach out to friends to see what they're putting on theirs.
>> But hands-down, the best way you can study is to go through everything and
whittle it down to what should or should not belong on that sheet of
paper, because that's just a really helpful way for you to make sure
you're going through everything and have some familiarity with it.
Most people, we find, even though they have the sheet of paper sitting right
next to them on the quiz, don't turn to it, because, again, that very
process of going through the information has helped them learn it.
>> Does anybody have any questions about quiz 0?
Has everybody--
I'm not going to do a show of hands.
Never mind.
I was going to ask who started studying.
But I don't want to make you all not raise your hands.
So like I said-- yes, Avi, go ahead.
>> AVI: What would be a useful thing to put on the one-pager?
>> STUDENT: That's up to you.
>> JASON HIRSCHHORN: You get to use your judgment.
Useful things to put on the one-pager, if you are confused about the big O
runtime of different types of searches and sorts, put that on there in a
handy dandy chart.
That way, if you're asked that on the quiz, you don't need to try and figure
it out or reason through the runtime.
You can just copy it down.
If you look at quizzes past, a lot of times, there's running time questions.
So that would be an example of a good thing to put on your one-pager.
>> Other good things to put on, if you're confused about how to declare a
function or what the different parts of the function declaration are, write
that on there, a generic version and then maybe an example.
If you're confused about pointers, a diagram of how pointers work is
probably really helpful.
If you're confused about recursion, a sample recursive function on there
could also prove to be really helpful.
Does that give you some ideas?
>> AVI: You need to understand the entire compiling process, like
how that all works?
>> JASON HIRSCHHORN: Everything that has been covered could
show up on the quiz.
Questions--
but again, some things will be weighted heavily than others.
Some things have come up again and again in class, in
lecture, and section.
Other things have not come up that often.
>> We've talked a lot about #include and -l something and what those mean in
the compilation process.
We've talked a lot about GDB, cling, those different flags that we use when
we compile something, and what make15, for example, really
means and really does.
We have not talk as much about every single step in
the compilation process.
We've still talked about it.
So it's still something that you should be familiar with.
But again, we're not going to be--
things that come up more often in class are more likely to come up more
often and be more heavily weighted on the quiz.
>> Cool.
Any other questions about quiz 0?
>> OK, so I put a list of topics on the board.
I went through the syllabus.
I went through the review section from last night and those slides to come up
with a non-exhaustive list of topics that we have covered so far in CS50
and things that might appear on the quiz.
So I'm not going to go through every single one of these.
That would take much more time than we have now.
But I put this up here to hopefully jog your memory as to things that may
or may not be as familiar with you.
>> And I'd love to spend the bulk of section answering your questions about
these topics, topics that aren't covered here.
We can write pseudo code.
We can write real code to ensure that you--
I can answer your question and help everybody fundamentally understand a
lot of these topics so you'll feel prepared and comfortable going into
the quiz tomorrow.
So read over the list.
You hopefully have come to section with some questions as well.
When you're ready, raise your hand and we will get started.
>> Keep in mind, the questions you have, there are no stupid questions.
We've heard that a lot.
And the questions you have, I am willing to bet, many other people both
sitting here and watching online have as well.
So you can only help people by asking questions.
Marcus.
>> MARCUS: Between the stack and the heap, is there a pre-allocated
percentage of memory that's defined as this is for the stack or for the heap?
Or how does that work, exactly?
>> JASON HIRSCHHORN: Great question.
I'm going to back trace a little bit.
Does everybody--
please be honest here.
I know I'm asking you to raise your hand in front of your peers.
But are there people who feel uncomfortable with the stack and heap
and would like to go over that and what those mean?
Raise your hand if--
OK.
Thank you.
So we're going to go over the stack and the heap really quickly and then
move into answering your question.
>> So if we draw out a box to represent memory on your computer, what are some
things that go in this box?
Main.
A main function.
Where does main go?
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: So we'll put main down here.
What else goes in this box?
>> STUDENT: The functions that you call.
>> JASON HIRSCHHORN: The functions that we call.
And where do they go?
>> STUDENT: In the stack.
>> JASON HIRSCHHORN: They go in the stack.
So we're going to call this thing down here the stack.
And up top, we have the heap.
So memory is not a box just like this.
But it is actually pretty similar.
It's going to be a lot of boxes over and over, depending on how big your
computer is or how big your memory is.
>> At the quote-unquote "bottom" is the stack.
And there are multiple things that go on the stack.
And those depend on the functions you have in your code.
You always have one function in your code called main, so there's always a
section down here in the stack devoted to main.
>> These sections in the stack are called stack frames.
When you call another function, say main calls a binary search function,
we put another frame on the stack.
More specifically, we are going to donate a chunk of memory on our
computer to store binary search's local variables and to run the binary
search code.
>> So we call binary search.
In this chunk of memory, we're going to store its local variables.
We're going to store its printf calls.
Whatever happens, that function is going to be stored right there.
Binary search is going to execute.
It is going to complete execution.
What is the word in C that signifies that a function should
complete its execution?
>> STUDENT: Return.
>> JASON HIRSCHHORN: Return.
So whenever you see a return statement, the function ends
when it hits that.
So binary search will hit its return.
This part of memory will essentially be freed up.
And main will go back to execution.
So main will pause wherever was, call binary search, get some return value,
and continue execution.
This stack frame will go away.
>> If we call a recursive function, which is a function that calls itself over
and over, we might get-- say we did binary search recursively.
We might get binary search version one, binary search two, binary search
three, binary search four, binary search five.
And then this final binary search five will hit the base case, and the stack
frames will go back and keep closing until we get back to main.
We can go over recursion in a bit.
But all this is to say, if you're calling multiple functions at a time,
there'll be multiple stack frames on the stack.
>> The heap, on the other hand, up here, is not for functions,
not for local variables.
It's for dynamically allocated variables.
So these are variables that can be initialized in either main or a
function that main calls.
Anywhere in your code, they can be initialized.
And to initialize a dynamically allocated variable.
What function in C do we use?
>> STUDENT: Malloc.
>> JASON HIRSCHHORN: Malloc.
You call malloc.
You get a space of memory.
And that space of memory is on the heap.
And that space of memory stays there until you call free.
>> So dynamically allocated variables in heap will exist for as long as you
want them to exist, and they won't go away until you explicitly
tell them to go away.
You can create them in one function.
That function's stack frame will go away.
But that variable will still exist in the heap until it is freed,
potentially by the function that called binary search or whatever.
>> So those heap variables stay there for as long as you want
them to stay there.
And they get put here.
And then the next one gets put there.
They keep getting filled in, and they stay there until you call free.
>> And essentially, the heap and the stack, getting to Marcus's question,
grow towards each other.
And if they run into one another, you've used up all the memory in your
computer, and your program will quit because you don't have any more memory
left to use.
In between them, there are potentially other things.
But for the scope of this course, you don't need to worry about that.
>> So that was the answer to your question.
Don't worry about it.
But that was the long answer.
All you need to know is the heap and the stack will--
one starts at the bottom.
The stack does.
The heap's up there.
They will grow closer to one another.
>> And if they touch, that's a problem.
You ran out of memory.
But also, in addition to knowing where they are, what is stored in both the
stack and heap.
Curtis.
>> CURTIS: When they collide, is that a stack overflow?
>> JASON HIRSCHHORN: When they collide, that's not a stack overflow.
A stack overflow is a different area that we can go over if you want to.
OK, we'll come back to that in a bit.
>> STUDENT: What's the word called when they hit each other, the
stack and the heap?
>> JASON HIRSCHHORN: For now, don't worry about.
Just know--
I will answer that question after class.
If they run into each other, you ran out of memory, because there's no more
space there.
>> STUDENT: Sorry, what's a seg fault?
>> JASON HIRSCHHORN: A segment fault can be called for--
it depends why the seg fault's called.
Sometimes, your stack overflow, it'll say seg fault as the error.
>> STUDENT: What about dereferencing a null variable?
Is that a seg fault?
>> JASON HIRSCHHORN: Dereferencing a null pointer--
OK, so if you have a pointer that you set equal to null, pointers, recall,
store memory addresses as their values.
And a null pointer is essentially storing 0, the 0-th
address in that variable.
So 0x, 0, 0, 0, 0, et cetera.
That 0-th address in memory that's not in our picture, that's up there
somewhere, that's reserved for the computer.
We're not allowed to touch it.
>> So when your program's executing, if something is trying to go to memory
address 0, it knows that that is an empty value.
It knows nothing should be there.
So if you try and use something there and treat something like there or
trying to go to that location, you're going to get a seg fault or an error.
Does that answer your question?
>> And now we'll go back to stack overflow.
Things in the stack, as you guys have seen before, in-- let's draw a close
up of a stack frame.
Can everybody see that?
So we have our stack frame.
We're saving an array in as a local variable in this function.
So say our array has five spots.
All five of those will be stored in that stack frame.
>> If we start writing beyond the bounds of this array--
so if we start writing into, let's say that's 0.
Those are the five indexes of our array.
If we start writing into index 5, which we don't have when we have an
array of size 5, we start writing into index 6, 7, 8, 9, we can get a Stack
Overflow error.
>> Generally it's not--
you will probably get into trouble if you go over by one.
But generally, you will get into the most trouble if you go over by a lot
and you go so far over that you write over the return address of that
function, which is located at the bottom of the stack frame.
>> Because, right?
You-- in the-- sorry.
Not "because right."
>> In the stack frame, you have your local variables.
At the very bottom of the stack frame is the return address.
That's where the function goes when it's over.
And if you overwrite that return address, then when this stack frame,
when you're going through the stack frame and executing each line, you're
going to go to your new return address that's written there instead of the
actual one.
And that's how we've seen some security breaches
can happen with computers.
>> So stack overflow, in short, is when you overwrite the part in the stack
you're supposed to use, the local variable you're supposed to use, and
in particular when you start overwriting important things like the
return address.
And that's where you'll get an error.
Or maybe even you could start even writing into--
say binary search was right above main.
If you overwrote a lot, you could write into main.
But generally, you get an error before then, because the computer knows
you're doing something you shouldn't be doing.
Yeah.
>> STUDENT: What's the difference between a stack overflow
and a buffer overflow?
>> JASON HIRSCHHORN: Buffer overflow is a more generic type of
what I've just described.
>> STUDENT: So a stack overflow is an example of a buffer overflow.
>> JASON HIRSCHHORN: Exactly.
This is an array we can think of as a buffer, a space for things to go in.
This is a stack buffer overflow.
We could have a heap buffer overflow.
If there was a buffer, which there often is an array the heap, and we
overwrote those bounds, then we would have a heap buffer overflow.
>> And beyond the scope of this course, they're detected a bit differently.
The compiler has special ways of detecting each.
But a buffer overflow is a more generic type of what I described,
which was a stack buffer overflow.
Did that answer your question?
Sweet.
>> Were there any other questions related to the stack or the heap?
Yeah.
>> STUDENT: I know you have to free strings because they're in the heap
and you don't want to leak memory.
But do you have to free global variables and stuff like that?
Or are they automatically freed?
>> JASON HIRSCHHORN: Good question.
So in CS50.H, we create this thing for you called a string.
A string is really what?
>> STUDENT: Char star.
>> JASON HIRSCHHORN: A char star, a pointer to a character, a pointer to
an array of characters.
That's what the string is.
So we need to free it, because getstring, which we used a lot--
string name equals getstring--
that mallocs for us some memory on the heap and then returns a pointer to the
first character of that string, a char star.
>> So ostensibly, if you have not been writing free on any of your strings
that you've called so far, you have been leaking some memory.
Of course we haven't talked about it, so nobody's gotten in
trouble for doing it.
But going forward, yes.
When you call getstring, you're mallocing some space on the heap.
And if you don't call free later on that string, you have a memory leak.
That answer your question?
>> Yeah
>> STUDENT: So to do that, do we use free right before return?
Like, within the scope of, I guess if we say, like, int main, within the
scope of the code that's within those curly braces, right before--
you know where you'd usually put return.
Do you put free before that?
>> JASON HIRSCHHORN: So you can put free wherever you want to put free.
Because these are dynamically allocated variables, because they can
live beyond the scope of a particular function, if you call malloc in a
separate function, for example, getstring, you can call free in main.
You don't need to call it in the specific function
where malloc is called.
But you do need to call it before main returns.
>> And it really depends.
It depends on why you malloced that space in the first place.
Some people will call free pretty quickly.
Some people won't call free until the end of their program.
And they'll go through and free everything.
It depends on why you called malloc.
>> STUDENT: And what would you say if you called use getstring?
You'd say free what?
>> JASON HIRSCHHORN: So the syntax for free is simply free, open paren, close
paren, and the name of the pointer.
So if you write string name equals getstring, you put name in here.
That's the name of the pointer.
And it knows to free that memory.
>> STUDENT: So when it frees that memory, the pointer still points to that place
in the memory?
Or is the pointer also emptied of the address that it points to.
>> JASON HIRSCHHORN: We should try that.
We should code that.
Let's come back when we get to coding, and let's code that.
And if you want to figure out the answer to that, you can also code that
in the meantime.
But that's a great question.
>> STUDENT: Is it possible to free something too soon?
So you still need it for your program, and you freed that memory space?
>> JASON HIRSCHHORN: Yes.
It is possible, if you free something and then you use it again, you will
run into an error.
But that's on you, because you freed something and then called it later.
So that was a programmer's mistake.
But yes.
You could write that.
>> Any more questions on--
yes.
>> STUDENT: So if you are supposed to just free it in general before the
program ends, does that mean if the program ends and you don't free it,
that memory is still allocated?
>> JASON HIRSCHHORN: If your program ends and you forget to free something, then
that memory was allocated throughout the lifetime of your program.
When your program closes completely, that memory is not going
to stay there forever.
The computer is smart enough to know that when the program closes, it
should get rid of all of the memory that was associated with that program.
>> However, there are tools you can run on a program to detect if, when the
program finished, you forgot to free some memory.
And for your next problem set where you'll be using malloc and using
pointers, you will be running this program on your program to see if,
when main returns, you had some things that were left unfreed.
>> So they're not going to stay malloced forever in your computer.
That would be wasteful, because very quickly, computers
would run out of memory.
But if they run until the end of your program and they're not freed and your
program exits, that's still a problem that this tool will help you address.
>> STUDENT: Is that Valgrind?
>> JASON HIRSCHHORN: It's called Valgrind.
And you'll be--
>> STUDENT: But we don't have to know that for the quiz, though?
I mean, it was talked about a little bit in lecture.
>> JASON HIRSCHHORN: So Valgrind is the name of that tool.
Knowing what it does is enough for the quiz.
But you have not used it yet on your problem set because we haven't had a
problem set that has explicitly dealt with malloc or you using malloc.
So you haven't used Valgrind yet.
But you will use it sooner rather than later.
>> STUDENT: Can you repeat what Valgrind is?
>> JASON HIRSCHHORN: Sorry?
>> STUDENT: Can you repeat what the purpose of Valgring is?
>> JASON HIRSCHHORN: Valgrind is the name--
like GDB helps you debug your program, Valgrind helps you figure out if
things have not been freed when your program closes.
So you'll run it on your program.
And your program exits, and it'll say your program called malloc this many
times for this many bytes, and you only called free this many times.
And so you left these many bytes without being freed.
Or it'll say you've freed everything.
Good job.
>> STUDENT: OK.
And it's called Valgring?
>> JASON HIRSCHHORN: V-A-L-G-R-I-N-D.
>> STUDENT: A question about pointers.
So say you have n star x equals something.
That equals, whatever you're putting there, is that what's being put inside
what x is pointing to, or the pointer of x?
>> JASON HIRSCHHORN: Can you repeat the question?
Can we draw it while you say it?
>> STUDENT: In the quiz, actually, the one you sent us, it was like, char
star truth equals CS50 rocks, right?
So does that mean that that CS50 rocks is what the truth is pointing to?
>> JASON HIRSCHHORN: So you're talking about a char star in a string, how
that works?
Yeah.
OK.
Let's draw this over here.
>> [SIDE CONVERSATION]
>> JASON HIRSCHHORN: So this variable is going to be of type char star.
How big is a variable of type char star?
How many bytes?
>> STUDENTS: Four.
>> JASON HIRSCHHORN: It's four bytes.
How many rights is a variable of type int star?
>> STUDENTS: Four.
>> JASON HIRSCHHORN: Four bytes.
If it's a pointer, then it is always four bytes, because pointers, their
value is a memory address.
And memory addresses on the CS50 appliance are four bytes long.
So when we call getstring, or when we say, stringname equals, and then in
double quotes put a string, we are putting--
well, that's a little different.
We'll do getstring as the example.
Or char star something equals the string.
Sorry, give me the example that you read?
>> STUDENT: char star truth equals "cs50 rocks" in double quotes.
>> JASON HIRSCHHORN: So this star, this we'll call this variable x for our
generic purposes.
We've created a variable called x.
It's type char star.
It is a pointer to a series of characters.
So down here--
>> So this is how this would work in memory.
This would store a memory address.
It would store the memory address of the first character in the array.
And then when you followed the pointer, you would
get the first character.
>> And if you're reading this thing like a string, your computer is smart
enough to know, read this whole thing until it gets to a backlash 0.
But if you're reading it a character at a time, so you're iterating through
this string, then you will just read a character at a time until you get to
backslash 0.
That might not answer your question, though.
>> STUDENT: Yeah, but you haven't malloced that space
yet for that pointer.
>> JASON HIRSCHHORN: So I'm not quite sure exactly what you're looking at,
because I didn't make that quiz.
That was supposed to be a helpful resource from another TF.
If you are creating a string on the stack or as a local variable, it'll
just be array of charges rather than generally a char star pointing to
another string.
But I don't know.
That could be a pointer to another string on the stack as well.
Yeah.
>> STUDENT: I know that you need to allocate memory if the pointer is
getting declared inside of another function.
Do you need to do the same thing if it's being declared inside of main,
you're using it inside of main?
>> JASON HIRSCHHORN: So yes.
You can declare a pointer to any memory address in memory.
It can be the memory address of a local variable, though oftentimes,
people don't declare memory addresses to local variables because they go
away once that function returns, which is why we generally malloc things.
But yes, you could declare a pointer to another local variable.
It's just generally not done.
But I can take a look at that specific thing after class.
Yeah.
>> STUDENT: I think this is sort of what's being asked.
It does seem strange to be initializing a pointer not as an
address, but as what seems like a value.
It seems like the CS50 is what's inside the thing being pointed to and
not the actual address, right?
>> JASON HIRSCHHORN: So that's not the case, though.
That's not what's happening.
When you declare a char star, it's a memory address.
Pointers are all memory addresses pointing to something else.
That something else could be on the stack, but almost always is on the
heap in the way we will see it used.
But stringname equals double-quote "getstring," we can see that and we
can look through that and code that.
getstring string is not being saved in that variable, or whatever the string
name is is not being saved in that variable, because that's not how
pointers work.
Does that make sense?
>> STUDENT: Yeah.
>> JASON HIRSCHHORN: OK.
Hopefully, that wasn't confusing to anyone.
But if it was, we can look at it again in a bit, because we're actually going
to code something that will hopefully work with strings and help you feel
more comfortable with them.
>> Any other questions related to these topics or other topics that
I'll put back up?
And--
right now.
Yes, Alden.
>> ALDEN: So this is completely unrelated, but can we just go over
really quickly what we need to know about the difference between a 32 and
64-bit machine?
>> JASON HIRSCHHORN: Yes.
So 32 bits is how many bytes?
>> ALDEN: It's four bytes.
>> JASON HIRSCHHORN: It's four bytes.
And 64 bits is how many bytes?
>> STUDENT: Eight.
>> JASON HIRSCHHORN: Eight bytes.
So again, eight bits is one byte.
Your CS50 appliance is a 32-bit machine.
So memory addresses are four bytes long.
There are 2 to the 32 memory addresses.
0 to 2 to the 32 minus 1.
And I am not positive, but that's probably the scope of what you need to
know for a 32-bit machine, that memory addresses are, again, four bytes long,
and that's the maximum amount of memory addresses.
>> Also, data types--
this might be something as well that's worth noting.
The size of a data type depends on the machine you're working with.
So a char, a single character, is how many bytes on our CS50 appliance?
One byte.
And it's actually one byte as well on a 64-bit machine.
>> And most data types are the same number of bytes on both machines.
But some data types will be different on both machines.
So that would be potentially the only thing you need to know.
>> But even that, I think, is beyond the bounds--
I'm almost positive, if you look back at old quizzes, it says, assume for
coding problems you're using a 32-bit machine.
But there are, to go along with that in case you're interested, there are
data types that are the same size on all machines.
>> If you've seen something like uint32_t, you may or may
not have seen that.
That's a data type.
That is saying, be 32 bits no matter what machine this is on.
So when people are writing portable code, they probably won't use ints.
They'll instead use these other data types that they know will be the same
size on every single machine.
Madhu.
>> MADHU: I had a question about the compilation process.
So if you're writing a program that uses a library like CS50 or something
like that, I know that that library has to, at some point, be
compiled and linked in.
But how much of that happens during the compilation of your program?
What part of that library process occurs when you're
compiling your own program?
>> JASON HIRSCHHORN: So let's go over generally the steps of this process.
You write your .c file.
In your .c file, you #include your header libraries, for example, cs50.h.
What does that sharp include line do to your program?
Akchar.
>> AKCHAR: It adds the prototypes of the functions from the header
files in the libraries.
>> JASON HIRSCHHORN: Exactly.
It adds those function prototypes to your code.
So when your code is being compiled in the early stages, the compiler knows
that these functions really exist, and that somewhere they have been defined.
The .h files don't include the definitions for these functions or how
they actually work.
Cs50.h just includes something that says getstring is a real thing that
can happen.
And standardio.h says printf is a real thing that can happen.
>> So your c language with this .header file gets turned into some
machine-readable code, which eventually gets turned into binary
code, 0's and 1's.
And that's the code that ultimately gets executed.
The -l cs50 line-- for example, when you're writing Clang--
and then you include -l cs50, you type that in.
And you see that.
When you write make, you'll see that line up here.
And we'll see that in a second when we code or later on when we code.
>> But that -l cs50 line does something a bit different than
the #include cs50.h.
What does that -l cs50 line do?
Avi?
>> AVI: I want to say that it links the library to the function
call, like the .o files.
>> JASON HIRSCHHORN: So very close, if not spot-on.
The -l cs50 takes the binary file and merges it with your binary file.
So cs50.h, there's no point in turning cs50.h from C language to binary every
single time it's being used.
That would be silly, because that would waste a lot of time.
So it has already been compiled and turned into an executable.
And now it is going to be merged with your file at the end.
So those 1's and 0's are going to merge with your ones
and 0's at the end.
So now you'll actually have the actual 1's and 0's that define how getstring,
for example, works, or how printf, for example, works.
>> And for more information, there's a short compilers that Nate gives that
you should check out that goes through these steps.
But--
yes.
>> STUDENT: Are they always in .o files when they're in the library form,
ready to be merged, linked-- like they're in the binary code?
>> JASON HIRSCHHORN: OK.
What--
>> STUDENT: Is that always the case for the libraries when you link them?
>> JASON HIRSCHHORN: Yes.
So there's .s files, which will be machine code, which will also be
cryptic to you.
You don't need to worry about those.
But generally, yeah, they'll be in .o files ready to go.
>> STUDENT: So when you ship to a library, do you only ship
the .h and the .o?
You don't ship the .c or the .s.
>> JASON HIRSCHHORN: So--
and this is in this short as well, if this information seems to be coming a
little quickly.
But the short on compilers talks about this as well.
When you ship a library, if you ship the .h, the header file, those
function prototypes, and the 1's and 0's, that's all you need to give.
You don't need to give how the function works, the .c file.
Because the point of abstraction, or the point APIs, the point at this SPL,
the Stanford portable library, it's for you to not worry about how new
GRect works, or how move works, or how add works.
All you need to know is that add is a function that you can
use, and it does this.
So you really don't need to know how it's written in C. You just need to
know, here are the functions, what they do, and here are the 1's and 0's
when you really want to use them.
>> Cool.
Any more questions on compilers or other topics on the board?
>> STUDENT: I have a question of implementing recursive functions.
A question about recursion.
I had a feeling that would come up.
So let's quickly go through recursion with a specific
example, a factorial function.
Because this is an example that often comes up or is used
to illustrate recursion.
>> So "4!" is read as 4 factorial.
And what does 4 factorial mean?
What does that do?
How do you calculate 4 factorial?
4 times 3 times 2 times 1.
>> So another way to write 4 factorial is to write this.
4 times 3 factorial.
Because 3 factorial is 3 times 2 times 1.
So 4 times 3 factorial is 4 times 3 times 2 times 1.
This is why factorial is a great candidate for recursion, because it's
clear that there is something that happens over and over and over on a
smaller number of things until you reach the end.
When you reach 1, 1 factorial is 1.
You can't go much further.
0 factorial is also defined as 1.
So when you get to 1 or 0, you're at the end, and you can
start going back up.
So if we wanted to write a recursive function to calculate a factorial,
we're going to write some pseudocode for that now.
Before we write that pseudocode--
I'll give you guys a couple of minutes to write the pseudo code or just think
about it-- there are two things every recursive function needs.
What are those two things?
>> JACK: It has to call itself.
>> JASON HIRSCHHORN: Noah?
Oh, Jack.
Go ahead.
>> JACK: It has to call itself.
>> JASON HIRSCHHORN: So a recursive function needs a recursive call, a
call to itself.
That's one.
And what's the other thing?
>> JACK: A base case.
>> JASON HIRSCHHORN: A base case.
A base case is, here's when we stop.
So your function gets called.
The base case comes first.
You want to know if you're at the end.
And if you're not at the end, you make your recursive call.
And you go through this function again, check your base case again.
If you're not the end, you make another recursive call,
et cetera, et cetera.
>> That's why recursive functions always need those base cases and those
recursive calls.
If you don't have a recursive call, it wouldn't be a recursive function.
If you didn't have a base case, you would go forever and
there would be no ending.
And the base case always comes first, because you will always want to check
if you're at the end first.
So before we do some pseudocode, why don't you take a minute to think about
how a recursive factorial function would be written?
>> Also, as many as you are doing, writing it out on a sheet of paper is
what you're going to have to do on the quiz tomorrow.
So probably good practice to make sure the code you're writing
down on sheet of paper--
or you can do that.
You know where the semicolons are.
You remember the syntax.
Because you're not be able to have a compiler tell you made an error.
>> Also, along those lines, tomorrow, when you have coding problems, if you
are rushed for time, or if you're very confused as to how you're supposed to
write the particular thing in c, it would behoove you to write pseudo-code
or write comments in as well.
Because there's partial credit for a lot of the questions on the quiz.
So you might be rushed, or you might just be confused.
Writing in comments or pseudo-code are often ways that you
can get partial credit.
>> So don't leave something blank on the quiz.
There's no penalties for putting things in.
In fact, putting in pseudo-code or comments is going to help the grader
figure out if you actually know what you're talking about, and maybe award
you some partial credit for that.
>> Also along those lines, write clearly.
If we can't really what you're writing, we're not going to call you
at midnight tomorrow to figure out what you wrote.
We're just going to take off points.
Write clearly so we can hear, or rather, we can read what you wrote.
>> And if it says two sentences, don't write a paragraph.
Follow the instructions.
Write clearly.
And write in those comments or pseudocode for questions that could
award partial credit.
>> OK, let's go to factorial.
So we have a function factorial.
If I were to actually write this in C, what do I need to put before the name
of the function?
The return type, which, in this case, we'll give it int.
And then inside the curly braces, is what goes inside the curly braces for
a function?
>> STUDENTS: Argument type.
>> JASON HIRSCHHORN: Its arguments.
So factorial will probably take an argument.
It'll probably only take one argument.
And we'll say it'll take an integer called x.
And again, when writing the prototype of a function or writing the function
in your code before defining it, you write the data type and the name of
that variable for that function only.
So you can pass some number into this function, it'll be referred to as x
internally.
>> We have our factorial function.
We need two things, a base case and a recursive call.
What is the base case for factorial?
Somebody who wrote it out and who hasn't spoken yet, what is the base
case for factorial?
>> STUDENT: If n is less than 2, return 1.
>> JASON HIRSCHHORN: If n is less than 2, return 1.
I like that, because that takes care of 0 and 1.
So we'll do x < 2, return 1.
If we get passed 0, if we get passed 1, this function will
immediately return 1.
If we get passed some number greater than or equal to 2, we're going to
have our recursive call.
>> And so how is that going to work?
Can somebody else who worked on this who hasn't spoken yet give me the
recursive call for this function in pseudocode?
If we get passed in a number x and it's greater than 2, what
do we want to do?
We also have an example written on the side that might give you a hint.
>> STUDENT: Call x times the factorial of x minus 1?
>> JASON HIRSCHHORN: Exactly right.
We're going to return x times the factorial of x minus 1.
And that, even though I wrote up, basically, what you said in English,
this factorial function will get called again.
It'll execute on x minus 1.
It'll return with some integer, and then it'll multiply these two
together, and that value will be returned to whatever called this
factorial function, which might be another instance of
this factorial function.
>> So that is an example of a recursive function, a very
simple recursive function.
But most of them will be like this.
If you would like a good recursive challenge for the quiz, try coding
binary search recursively.
Because if you did binary search for problem set three, you probably did it
iteratively in a while loop.
>> But it can also be written recursively.
You're going to need to write your own separate function that takes some
different command-line arguments-- or not command-line arguments, some
different just regular arguments.
But you could write binary search recursively as well.
>> STUDENT: So you could have also written, instead of x minus 1, you
could have also written x minus minus, or you could have
written minus minus x.
Can you just explain really quickly why those would be different things,
like what the difference is between x minus minus and minus minus x?
>> JASON HIRSCHHORN: No, I'm not going to go into that.
But I will talk to you about it after class. x minus minus, minus minus x
decrement x by 1.
But they do it a bit differently.
But I don't want to go into that.
Other questions about recursion or this function?
That's not really even pseudocode.
That's basically the code in C you would write for this.
>> OK, any other questions about topics up here?
Yeah.
>> STUDENT: I have a quick rundown of floating point and precision.
>> JASON HIRSCHHORN: Floating point and precision.
Can somebody really quickly give me a rundown of
floating point and precision?
You all had to do this for your problem set, so you're all
familiar with it.
Or maybe not all of you.
Anyone?
Give me a started spot.
Floating point and precision.
What's the problem?
Yes.
Victoria?
>> VANESSA: Vanessa.
>> JASON HIRSCHHORN: Vanessa.
Sorry.
>> VANESSA: There's only a finite number of numbers that can be represented
because you're on a, in our case, a 32-bit system.
So you kind of have to make up some numbers.
>> JASON HIRSCHHORN: So that's exactly right.
There are only a certain amount of numbers that can be represented.
If you multiply two very large numbers, it might overflow the amount
of spaces you have to represent an integer.
That's why sometimes we use a long long instead of an int.
That has more spaces.
That can hold a larger number.
>> Floating point precision has to do with that, but also has to do with the
fact that decimal numbers are not always represented.
Sorry.
Let me put this back up.
The decimal number 1.0 is not always represented like you would expect,
1.000000000.
It is sometimes represented as 1.000000001 or 0.999999999.
It might be even 89 thrown in there somewhere.
So those decimal numbers aren't represented exactly like you would
expect them to be represented.
>> So in problem set--
was it two?--
problem set two, where we dealt with floating point numbers, when we wanted
them to represent exactly what we wanted them to represent, the number
of pennies, or the number of cents, we multiply them by 100.
We rounded them.
And then we cut off everything behind the decimal point.
That was to ensure that they would actually equal exactly what we wanted
them to equal.
>> Because when you take something that's a float and turn it into an int, you
cut off everything to the right of the decimal point.
Because there's some floating point imprecision, 100.000 might be
represented as 99.999999999.
And if you just cut off everything to the right right away, you're going to
get the wrong number.
Yeah.
>> STUDENT: I had a question about casting.
What order does it occur in?
If you'd do float, brackets, 1 divided by 10, does it do 1 divided by 10,
then get 0.1, then turn it into a float?
>> JASON HIRSCHHORN: If you do float 1 divided by 10--
>> STUDENT: Yeah, and then equals--
well, it would normally have it equal in--
Yeah.
You want to make it a float, right?
>> JASON HIRSCHHORN: OK, so we're going to use that to segue into figuring out
the answers to these questions through coding.
Because you'll probably have a lot of these minute questions, and a good way
to solve them is through coding.
So we're going to code this right now, and then we're going to go back and
code the question you had.
>> So the first line--
I shouldn't have written it-- what is the first thing we want to do when we
open up a new file in gedit?
>> STUDENT: Include.
>> JASON HIRSCHHORN: Include what?
>> STUDENT: CS50 library.
>> JASON HIRSCHHORN: OK.
What else should we include?
We're just going to check what happens when you cast something to a float.
But what do we need to include if we're going to write a C program?
>> STUDENT: Standard I/O.
>> JASON HIRSCHHORN: stdio.h.
We actually don't need, for this program, cs50.h, even though it's
always helpful to include it.
But we do always need stdio.h.
>> STUDENT: When coding in C?
>> JASON HIRSCHHORN: When coding in C.
>> So I save it as this .c file.
I get some nice syntax highlighting.
I wrote void inside main.
What does void mean?
>> STUDENT: Doesn't take any command-line arguments.
>> JASON HIRSCHHORN: Void means, in this case, main doesn't take any
command-line arguments.
In other cases, it means the function doesn't take command-line arguments.
Or the function, if I were to write void main(void), that would say main's
not returning anything.
So void just means nothing.
What would I write if I were to take command-line arguments?
>> STUDENT: int arc c string arc v.
>> JASON HIRSCHHORN: int argc string argv.
Is that right?
>> STUDENT: It's char star argv brackets.
>> JASON HIRSCHHORN: So you could write string argv brackets or char star argv
brackets, but you need the brackets.
Because argv is an array of strings, remember.
It's not just one string.
So string argv is, here's one string called argv.
String argv brackets is, here's an array of strings.
So int argc string argv brackets would be something that I
would probably write.
>> So you wanted to save in an integer?
>> STUDENT: Yeah, integer.
Or in a float.
>> JASON HIRSCHHORN: In a float?
Like, float x equals 1 divided by 10.
>> JASON HIRSCHHORN: OK.
How do I print out a float in printf?
What?
>> STUDENT: %f.
>> JASON HIRSCHHORN: %f.
What's an integer?
d or i.
What's a string?
>> STUDENT: s.
>> JASON HIRSCHHORN: s.
How do I get a new line?
>> STUDENT: Backslash n.
>> JASON HIRSCHHORN: What do I return if main runs correctly?
>> STUDENT: 0.
Do I need to write that line, though?
>> STUDENT: No.
OK, we won't write it, then.
Can everybody read that?
It looks a bit small.
Can everybody see, or should I make it bigger?
I think for the camera, we'll make it a bit bigger, though.
>> JASON HIRSCHHORN: If I want to turn this .c file into an executable, what
do I write?
>> STUDENT: Make test.
>> JASON HIRSCHHORN: Sorry?
>> STUDENT: Make test.
>> JASON HIRSCHHORN: Make test.
We were talking about this line earlier.
Clang.
What's clang?
The name of the compiler.
What's this line?
>> STUDENT: Sets it up for use of GDB.
>> JASON HIRSCHHORN: Sets it up for use of GDB.
This line, what's that?
>> STUDENT: Source code.
>> JASON HIRSCHHORN: That's the source file, the .c file.
What do these two lines do?
Or these two not lines.
>> STUDENT: It names it test.
>> JASON HIRSCHHORN: So the dash o says, name it something differently.
And here you're calling it test.
If I didn't have that in, what would it name this?
>> STUDENT: A.out.
>> JASON HIRSCHHORN: A.out.
What does this do?
>> STUDENT: Links the math library.
>> JASON HIRSCHHORN: It links in the math library.
We didn't include the math library, but since that's so common, they've
written make to always include the math library.
And likewise, this includes the CS50 library.
>> OK, so if we list, we now have an executable called test.
To execute it, I write test.
I see that my floating point, as expected, equals 0.
Does that--
so--
>> STUDENT: Then if you put float now, like you cast it as float--
>> JASON HIRSCHHORN: Cast the 1 to a float?
>> STUDENT: No, cast the full thing--
yeah.
If you just did that, would that make it 0.1?
>> JASON HIRSCHHORN: OK, so really quickly, 1 divided by 10, those are
integers being divided.
So when you divide integers, they're 0, and you're saving that 0 in a
float, because the slash is just integer division.
So now we're turning something into a float.
>> Let's see what happens.
We'll make test.
So now we see that that slash was not integer division, it was floating
point division.
Because one of its arguments had been cast to a float.
So now it was saying, treat this division like we're dealing with
floating points, not with integers.
And so we get the answer we expect.
>> Let's see what happens--
oops.
If I wanted to print more decimal spots, how could I do that?
>> STUDENT: Point dot f, or as many decimal places as you want.
>> JASON HIRSCHHORN: So I print 10 decimal spots.
And we now see we're getting some weird stuff.
And that goes back to your question about floating point imprecision.
There's weird stuff stored in here.
>> OK, does that answer your question?
What else did you want to code quickly?
>> STUDENT: I just wanted to see whether or not, if you freed up some pointer,
whether that pointer still had stored in it the address of what it had been
pointing to previously.
>> JASON HIRSCHHORN: OK, so let's do that.
Char star ptr, this creates a variable called ptr of type char star.
How do I write malloc?
Alden?
>> ALDEN: Just malloc.
But then it has to be size of, and in this case, I guess you'd
be pointing to char.
So it'd be char.
>> JASON HIRSCHHORN: OK, so more generically, Inside--
let's edit.
Inside malloc, you want the number of bytes on the heap.
Generally, what we've seen that we're doing is we're going to malloc
strings, for example, or arrays of integers.
So if we want 10 integers, or 10 chars, 10 will give us 10.
And then size of chars would give us that size of chars, which in
this case is 1 byte.
We get 10 bytes.
If we were to write size of int, that would give us 40 bytes.
>> So more generically, inside of malloc is the number of bytes you want.
In this case, we're getting 1 byte.
Which seems like a weird use of malloc, but for our
purposes makes sense.
So there's that.
>> We're going to call free.
We get rid of it and we use ptr again.
And what did you want to check?
>> STUDENT: I just wanted to check whether or not there was anything
inside of it.
>> JASON HIRSCHHORN: So whether it pointed to anything?
>> STUDENT: Yeah, exactly, whether it still had a memory address.
>> JASON HIRSCHHORN: So you want to check the value of ptr?
>> STUDENT: Yeah, exactly.
>> JASON HIRSCHHORN: What do I write here if I want to check the value of the
point-- what is, Jordan said, the value?
Or what is stored inside of ptr?
>> STUDENT: A memory address.
>> JASON HIRSCHHORN: A memory address.
So if I write just this, it'll give me the value of ptr.
And how do I print out a memory address?
What's the format string for a memory address?
>> STUDENT: %p.
>> JASON HIRSCHHORN: %p.
%s is a string.
%p for pointer.
Is that right?
That is right.
So ptr equals--
it still has something in it.
This is probably a more interesting question.
What does that line do?
>> STUDENT: Seg faults.
>> JASON HIRSCHHORN: What?
>> STUDENT: I think it seg faults.
>> JASON HIRSCHHORN: Hm?
>> STUDENT: I think it'll seg fault.
>> JASON HIRSCHHORN: So this line of code, star ptr, what
does the star mean?
>> STUDENT: Content of.
>> JASON HIRSCHHORN: Yeah.
Go to get the content of.
So this is going to go to the memory address there and give me that.
I used %c right here because there are characters stored there.
So we're going to go to that address we just saw-- or it'll probably be a
little bit different this time we run the program.
But we'll go to that address which we know still exists
and see what's there.
>> So it didn't seg fault.
It just didn't give us anything.
It might have actually given us something, we just can't see it.
And that goes back to this idea--
and we're not going to get too much into this, because that's beyond the
scope of this course.
But we talked about right here, if we went beyond the bounds of the array by
1, we might not get in trouble.
>> Sometimes, when you just go off by 1, you're doing something wrong, and you
could get in trouble.
But you don't always get in trouble.
It depends how much of a bad thing you do, you're going to get in trouble.
Which isn't to say, be sloppy with your code.
But it is to say, the program won't always quit, even if you go somewhere
you're not supposed to go.
>> A good example of that is, a lot of people in their problem set 3, which
was 15, did not check the bounds of the board.
So you looked to the left, looked to the right, looked to the top, looked
to the bottom.
But you didn't check to see if the top was actually going to be on the board.
And a lot of people who did that and turned that in, their program worked
perfectly, because where that board was stored in memory, if you went one
above it or checked that memory address, there wasn't anything
particularly horrible about that, so your program wasn't
going to yell at you.
>> But we would still take off points if you didn't check that, because you
were doing something you weren't supposed to do, and you could have
gotten in trouble.
Odds are, though, you probably didn't.
So this is to show that, yes, we can still go to it.
And we're not getting in trouble in this case.
If we tried to do read the next 100 characters, we'd
probably get in trouble.
And you can code reading the next 100 characters if you want by doing some
sort of for loop.
Yeah.
>> STUDENT: Since we were assigned that space an actual value, we wouldn't
actually be able to see anything.
Should we try it with setting that equal to like c or something?
>> JASON HIRSCHHORN: Great question.
How do I set that value--
what line of code do I write on line seven to do what you said?
>> STUDENT: Star ptr equals single quote c end single quote.
>> JASON HIRSCHHORN: So that's putting a character, c, at that location,
because again, that star means go to there.
And when used on the left hand side of an assignment operator, that equals
sign, we're not going to get that value so much as set that value.
Now let's see what happens.
>> We put something there and it was there.
We called free.
Some stuff probably happened on the heap.
So it's not there anymore.
But again, we're not getting in trouble for going there.
>> I'm doing this out in code to illustrate that a lot of these
questions that you have, they're really interesting
answers a lot of time.
And they're really good questions.
And you can figure them out on your own if, for example,
we're not in section.
Yeah.
>> STUDENT: Because you're not sending the pointer anywhere, do you need to
use malloc?
>> JASON HIRSCHHORN: So this goes back to your initial question.
[? ?]
Is it just a local variable?
Malloc here is not that compelling.
The use of malloc here is not that compelling because it's
just a local variable.
>> STUDENT: So could you do char star ptr equals hello?
>> JASON HIRSCHHORN: Oh.
So we're going to now get back to your initial question.
I think you weren't satisfied with my answer.
OK?
Like that?
>> STUDENT: Yeah.
Wait.
>> JASON HIRSCHHORN: And where do you want to print out?
So we'll print out a string like that?
>> STUDENT: Interesting.
>> JASON HIRSCHHORN: So this says this argument has the type of a character.
So this should be a character.
>> STUDENT: Just takes the first one.
>> JASON HIRSCHHORN: So this is what I said before.
Like I said, it's not storing the string inside variable pointer.
It's storing--
>> STUDENT: The first value of the string.
>> JASON HIRSCHHORN: The address of the first value of the string.
If we were to print out this, we're getting the value inside pointer.
And we'll see it is, indeed, a memory address.
>> Does that make sense?
Sorry.
Wait, does that answer your question, though?
>> STUDENT: Yeah.
>> JASON HIRSCHHORN: This line of code is creating a string and then another
variable pointer that's pointing to that string, that array.
Yeah.
>> STUDENT: So if we went one memory address further, would we get the h?
Has it been stored as a string?
>> JASON HIRSCHHORN: Like, we did--
so this is valuable to do.
This is point arithmetic, which you guys have seen before and should be
relatively comfortable with.
This is akin to writing--
if we were to write this line of code, we've seen array notation before.
This should give us the second value in this array, h.
>> If we did this, this should also give us the second value in that array.
Because it is going not to the memory address of the first thing, but the
memory address of the thing one over.
And then the star operator dereferences that pointer.
And again, let's see.
We get h again.
>> STUDENT: What exactly does dereference mean?
>> JASON HIRSCHHORN: Dereference is a fancy word for go to.
Go to that and get what's there is to dereference a pointer.
It's just a fancy word for that.
>> STUDENT: If we wanted to print the whole string, could we
do ampersand pointer?
>> JASON HIRSCHHORN: OK, we are going to pause here.
We are going to end here.
Ampersand gives you the address of a location, so when you do ampersand of
a variable, it gives you the address where that variable is stored.
Ampersand pointer will give you the address of ptr where ptr is in memory.
>> We're not going to go on with this example.
You can figure out these things on your own.
But again, this might even be verging a bit beyond what you need to know for
the scope of this mid-term--
or this quiz, rather.
Sorry.
>> We are going to move on, because I would like to do one coding problem
before time is up.
And we are going to code what I think is the most compelling of these
examples, atoi.
So this was a question on a quiz two years ago.
And I have it on the board here.
>> People were asked on the quiz--
they were given a little more tesxt in the question, but I eliminated the
text because it was unnecessary for our purposes now.
It was just some background on what atoi did.
But you all know and are very familiar with atoi.
>> I suggest you code this on a sheet of paper.
I also suggest you use the strategy that we've gone over
a lot in our section.
First, make sure you understand what atoi's doing.
Draw a picture or come up with some mental image of it in your head.
Next, write out pseudocode for this.
On the quiz, if all you get is pseudocode, at least you
put something down.
And then map that pseudocode onto C. If you have a check in your
pseudocode, like check if something is 1, that maps onto an if
condition and so forth.
And finally, code the program in C.
>> So go back to atoi and take five minutes to code this on a sheet of
paper, which is probably about the amount of time you would take on a
quiz to code atoi.
Five to 15 minutes, five to 12, five to 10 minutes, is about the amount of
time you'd spend on this question in the quiz.
So take five minutes now, please.
And if you have any questions, raise your hand and I'll come around.
>> [SIDE CONVERSATIONS]
>> JASON HIRSCHHORN: OK, so that was five minutes.
That was probably about the amount of time you'd spend on that on a quiz,
maybe the low end of that time.
We'll recap in a bit.
Let us start coding this.
And if we don't get all the way through, the answers to this and this
quiz question are available, again, Fall 2011 is when this question
appeared on the quiz.
>> And it was worth eight points on the quiz then.
Eight points is on the high end of the amount of points something is worth.
Most questions are in the range of one to six points.
So this is a more challenging question, for sure.
Can anybody get me started?
>> Generally, what are we going to want to do with this
function atoi, logically?
What do we want to do?
So we're going to write some pseudocode.
>> STUDENT: Convert characters into integers.
>> JASON HIRSCHHORN: Convert characters into integers.
OK.
So how many characters are we going to need to go through?
>> STUDENT: All of them.
>> STUDENT: All the characters in the string.
>> JASON HIRSCHHORN: All of the characters in the string.
So if we wanted to go through every character in a string, what is a thing
in C we've seen that has allowed us to go through every
character in a string?
>> STUDENTS: A for loop.
>> JASON HIRSCHHORN: A for loop.
So we're going to loop through every character in s.
>> Then what are we going to want to do when we get a specific character?
Say we're getting passed a 90.
We get the 9.
It's a character.
What do we want to do with that character 9?
>> STUDENT: Subtract it from character 0?
>> STUDENT: Add 0?
>> JASON HIRSCHHORN: Subtract it from character 0?
>> STUDENT: Yeah.
>> JASON HIRSCHHORN: Why do you want to do that?
>> STUDENT: [INAUDIBLE]
value.
Its int value.
>> JASON HIRSCHHORN: OK, so we take the character 9, subtract it from
character 0 to get an actual integer 9.
Sweet.
And how do you know that character 9 minus 0 character is 9?
What chart did you look at?
>> STUDENT: There are logically nine places between 9 and 0.
Or you could look at the ASCII table.
>> JASON HIRSCHHORN: ASCII table.
But yes, you're correct as well.
So we subtract 0.
So now we have the integer 9.
And what do we want to do with that?
If we have 90, it's the first integer we have, what we want to do?
>> STUDENT: I'd put in a temporary integer array, then do math to it
later to make it into an end.
>> JASON HIRSCHHORN: OK.
>> STUDENT: You can start at the end of the array and then move forward so
that every time you move forward, you multiply it by 10.
>> JASON HIRSCHHORN: OK.
That sounds like a pretty compelling idea.
We can start at the end of our array, and we can use strleng.
We can use strleng in here.
We'll get the length of our string.
We start at the end.
And + the first one, we just take that integer, and maybe we create like a
new integer variable up top where we're storing everything.
So we loop through every char in s from back to front, we subtract 0, and
then we take it, and depending on where it is, we multiply it
by a power of 10.
Because the first one, what do we multiply the rightmost character by?
>> STUDENT: 10 to the 0.
>> JASON HIRSCHHORN: 10 to the 0.
What do we multiply the second rightmost character by?
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: What?
>> STUDENT: 10 to the 1.
>> JASON HIRSCHHORN: 10 to the 1.
The third-rightmost character?
>> STUDENT: 10 to the 2.
>> JASON HIRSCHHORN: 10 to the 2.
>> STUDENT: Sorry, I don't understand what we're doing here.
>> JASON HIRSCHHORN: OK, let's go back, then.
So we're going to get passed in a string.
Because we're writing atoi.
So we get passed in a string.
Say we're getting passed in the string 90.
>> The first thing we're going to do is set a new integer variable that we're
just going to create as our new integer.
That's what we're going to return at the end.
We need to go through every character in the string because we've determined
that we need to touch each one and then add it to our new integer.
>> But we can't just add it as a number.
We can't just take 9 and add 9 to our integer.
It depends on what place it is in the string.
We're going to need to multiply it by a power of 10.
Because that's how base 10 works.
>> So we're going to get the actual character, or the actual integer
number, by subtracting character 0 from character 9 like we did with
subtracting character capital A from whatever character we had in one of
those problems.
So we'll actually get a number from 0 to 9 saved as a real number, and we'll
multiply it by a power of 10 depending on where we are in the string.
And then we're going to add it back into our new integer variable.
>> So what this would look like would be-- we'll draw over here.
If we get passed in the string 90--
>> STUDENT: [INAUDIBLE].
>> JASON HIRSCHHORN: But atoi takes a string.
So we're going to go through the holding.
We'll get passed in 90.
We go from the back to the front.
We take the 0.
>> STUDENT: I'm sorry.
Maybe this is stupid.
If we're getting passed in a string, why is 90 what we're
getting passed in?
Because 90 is an integer.
>> JASON HIRSCHHORN: Because atoi takes a string and turns it into the integer
representation of that string.
But the string 90 is not the integer 90 or the number 90.
The string 90 is an array of two, or three characters, rather, the 9
character, the 0 character, and the backslash 0 character.
>> And we're writing atoi because, for example, when you take the command
line argument, and it's saved in argv, it's saved as a string.
But if you want to treat it as a number, you need to convert it to an
actual integer.
Which we did one of our problem sets.
Which we did in a number of our problem sets.
Everyone that took an integer as a command line argument.
So that's why our atoi function takes a string.
>> So again, in our example here, we're going to take the last one.
We're going to subtract the character 0 from it, because the characters 0
subtracted by the character 0 gives you the actual number 0, according to
the ASCII math that we do.
>> Because characters are represented as different than their actual-- the
character a, for example, lowercase a is 97.
It's not-- oops!
It's not whatever you would expect it to be, 0, for example.
So you have to subtract the character a to get 0.
>> So we're going to do that here to get the actual number.
And then we are going to multiply it by a power of 10 depending on where it
is in the string, and then take that and add it to our place holder
variable so we can come up with our final new integer.
Does that makes sense to everyone?
>> So we're not going to code this right now, because we're
getting short on time.
I apologize for the timing of that.
But this is what, hopefully, you would be able to do on the quiz-- at the
very least, get this pseudocode written out.
>> And then, if we were to write the pseudocode, actually, we could do this
pretty quickly.
Each line of comments we we wrote here translates to about
one line of C code.
Declaring a new variable, writing a loop, some subtraction, some
multiplication, and some assignment.
We'd probably also want to write a return line.
We might also want to put some checks in here.
Yeah.
>> STUDENT: So can we treat s as the actual string?
Because I know it's just an address.
Like, how would you get the length of the string being passed through?
>> JASON HIRSCHHORN: So how did the length of a string?
Strlen.
>> STUDENT: strlen, yeah.
But can you put s as the argument for that?
>> JASON HIRSCHHORN: So strlen takes a char star.
And it follows that char star, and it keeps counting until it gets to a
backslash 0. strlen was actually one of the other programs we
were going to code.
That's another good one to code.
That one's a bit easier, because if you're going to think about that
conceptually--
I just said it out loud-- strlen follows a pointer and keeps going and
counting and keeping track until you reach a backslash 0.
>> STUDENT: OK, got it.
>> JASON HIRSCHHORN: So best of luck on quiz 0 tomorrow.
If you have any questions, I'll be outside after this.
Feel free to email me.
Reach out to your own TF if you're not in my section, or get my
email if you want it.
>> If you want to freak out and just send me an email, a freakout email, I'll
send you back, like, a smiley face, or, like, a joke or something.
So feel free to do that as well.
Good luck again, and I'll see you all next week.