1
00:00:00,000 --> 00:00:06,180

2
00:00:06,180 --> 00:00:07,820
>> JASON HIRSCHHORN: Welcome
to A5, everyone.

3
00:00:07,820 --> 00:00:11,270
We have an exciting week ahead of us,
mostly because there are so many new

4
00:00:11,270 --> 00:00:12,350
faces in this room.

5
00:00:12,350 --> 00:00:12,920
It's wonderful.

6
00:00:12,920 --> 00:00:15,740
A lot of you are here by accident,
which is even better.

7
00:00:15,740 --> 00:00:18,220
So hopefully you'll keep joining us.

8
00:00:18,220 --> 00:00:20,220
>> This week we're going to spend
the bulk of section

9
00:00:20,220 --> 00:00:21,870
preparing for the quiz.

10
00:00:21,870 --> 00:00:26,580
So per our agenda, we're going to talk
a bit about resources for the class,

11
00:00:26,580 --> 00:00:30,350
but also for the quiz, and then, again,
spend the bulk of class talking

12
00:00:30,350 --> 00:00:31,390
about questions.

13
00:00:31,390 --> 00:00:33,900
Once we're done answering your
questions, or if your questions

14
00:00:33,900 --> 00:00:39,010
naturally lead us to some coding, I
have sample problems from midterms

15
00:00:39,010 --> 00:00:43,180
past that we will code live in section
together that also bring up some other

16
00:00:43,180 --> 00:00:45,420
good topics to cover.

17
00:00:45,420 --> 00:00:48,280
>> So first, as we've gone through for the
past couple of weeks to remind you

18
00:00:48,280 --> 00:00:51,700
guys, there are a ton of resources
available for this course.

19
00:00:51,700 --> 00:00:55,020
Many of them will be incredibly helpful
to you as you continue to

20
00:00:55,020 --> 00:00:57,280
study for quiz 0, because
it's Tuesday afternoon.

21
00:00:57,280 --> 00:00:59,630
So all of you have been
studying for a bit.

22
00:00:59,630 --> 00:01:02,640
>> There are lecture notes and source
code that you should

23
00:01:02,640 --> 00:01:04,050
definitely check out.

24
00:01:04,050 --> 00:01:05,019
Watch the shorts.

25
00:01:05,019 --> 00:01:07,470
Check out study.cs50.net.

26
00:01:07,470 --> 00:01:11,770
And then, listed below, a number
of other resources.

27
00:01:11,770 --> 00:01:14,020
>> Again, quiz 0 is tomorrow
at 1 o'clock.

28
00:01:14,020 --> 00:01:18,230
If you haven't done so already, check
out the About Quiz 0 document on the

29
00:01:18,230 --> 00:01:21,370
course's homepage to figure out
where you're taking the quiz.

30
00:01:21,370 --> 00:01:25,770
The quiz starts at 1:10 and
ends 70 minutes later.

31
00:01:25,770 --> 00:01:29,610
So if you show up after 1:10, you're
going to get that many fewer minutes

32
00:01:29,610 --> 00:01:30,940
than 70 to take the quiz.

33
00:01:30,940 --> 00:01:33,570
So make sure you're there on time.

34
00:01:33,570 --> 00:01:38,690
If you're an extension student or have
some other testing considerations, it

35
00:01:38,690 --> 00:01:40,400
might not be at 1 o'clock tomorrow.

36
00:01:40,400 --> 00:01:43,540
But again, check the About Quiz 0
document to make sure you know when

37
00:01:43,540 --> 00:01:44,760
you're taking the quiz.

38
00:01:44,760 --> 00:01:46,440
I wrote 75 minutes up here.

39
00:01:46,440 --> 00:01:48,580
I think that's right, not 70.

40
00:01:48,580 --> 00:01:53,420
>> It covers all the material from a week 0
to last week's lecture on Wednesday.

41
00:01:53,420 --> 00:01:59,350
And again, for this quiz, per that
document, you get one two-sided and 8

42
00:01:59,350 --> 00:02:03,770
1/2 by 11 sheet of paper that you get
to use as notes during the quiz.

43
00:02:03,770 --> 00:02:08,570
Many people, if not most people, have
found that the single most helpful way

44
00:02:08,570 --> 00:02:11,970
to study for the quiz is to
make a study sheet, a

45
00:02:11,970 --> 00:02:13,730
one-sider, of their own.

46
00:02:13,730 --> 00:02:17,710
So look at past ones if
you've seen past ones.

47
00:02:17,710 --> 00:02:19,960
Reach out to friends to see what
they're putting on theirs.

48
00:02:19,960 --> 00:02:23,610
>> But hands-down, the best way you can
study is to go through everything and

49
00:02:23,610 --> 00:02:26,530
whittle it down to what should or should
not belong on that sheet of

50
00:02:26,530 --> 00:02:30,570
paper, because that's just a really
helpful way for you to make sure

51
00:02:30,570 --> 00:02:33,620
you're going through everything and
have some familiarity with it.

52
00:02:33,620 --> 00:02:36,690
Most people, we find, even though they
have the sheet of paper sitting right

53
00:02:36,690 --> 00:02:39,840
next to them on the quiz, don't turn
to it, because, again, that very

54
00:02:39,840 --> 00:02:43,290
process of going through the information
has helped them learn it.

55
00:02:43,290 --> 00:02:45,370
>> Does anybody have any questions
about quiz 0?

56
00:02:45,370 --> 00:02:50,120

57
00:02:50,120 --> 00:02:51,450
Has everybody--

58
00:02:51,450 --> 00:02:53,230
I'm not going to do a show of hands.

59
00:02:53,230 --> 00:02:53,550
Never mind.

60
00:02:53,550 --> 00:02:54,790
I was going to ask who
started studying.

61
00:02:54,790 --> 00:02:58,360
But I don't want to make you
all not raise your hands.

62
00:02:58,360 --> 00:03:01,290
So like I said-- yes, Avi, go ahead.

63
00:03:01,290 --> 00:03:04,205
>> AVI: What would be a useful thing
to put on the one-pager?

64
00:03:04,205 --> 00:03:05,875
>> STUDENT: That's up to you.

65
00:03:05,875 --> 00:03:08,210
>> JASON HIRSCHHORN: You get
to use your judgment.

66
00:03:08,210 --> 00:03:13,220
Useful things to put on the one-pager,
if you are confused about the big O

67
00:03:13,220 --> 00:03:17,510
runtime of different types of searches
and sorts, put that on there in a

68
00:03:17,510 --> 00:03:18,760
handy dandy chart.

69
00:03:18,760 --> 00:03:22,250
That way, if you're asked that on the
quiz, you don't need to try and figure

70
00:03:22,250 --> 00:03:23,560
it out or reason through the runtime.

71
00:03:23,560 --> 00:03:24,730
You can just copy it down.

72
00:03:24,730 --> 00:03:28,320
If you look at quizzes past, a lot of
times, there's running time questions.

73
00:03:28,320 --> 00:03:34,150
So that would be an example of a good
thing to put on your one-pager.

74
00:03:34,150 --> 00:03:37,450
>> Other good things to put on, if you're
confused about how to declare a

75
00:03:37,450 --> 00:03:40,570
function or what the different parts of
the function declaration are, write

76
00:03:40,570 --> 00:03:43,400
that on there, a generic version
and then maybe an example.

77
00:03:43,400 --> 00:03:47,290
If you're confused about pointers,
a diagram of how pointers work is

78
00:03:47,290 --> 00:03:48,660
probably really helpful.

79
00:03:48,660 --> 00:03:52,440
If you're confused about recursion, a
sample recursive function on there

80
00:03:52,440 --> 00:03:54,980
could also prove to be really helpful.

81
00:03:54,980 --> 00:03:57,290
Does that give you some ideas?

82
00:03:57,290 --> 00:04:01,820
>> AVI: You need to understand the
entire compiling process, like

83
00:04:01,820 --> 00:04:03,220
how that all works?

84
00:04:03,220 --> 00:04:06,620
>> JASON HIRSCHHORN: Everything
that has been covered could

85
00:04:06,620 --> 00:04:08,060
show up on the quiz.

86
00:04:08,060 --> 00:04:08,930
Questions--

87
00:04:08,930 --> 00:04:11,300
but again, some things will be
weighted heavily than others.

88
00:04:11,300 --> 00:04:14,330
Some things have come up again
and again in class, in

89
00:04:14,330 --> 00:04:15,590
lecture, and section.

90
00:04:15,590 --> 00:04:17,220
Other things have not
come up that often.

91
00:04:17,220 --> 00:04:22,900
>> We've talked a lot about #include and
-l something and what those mean in

92
00:04:22,900 --> 00:04:24,390
the compilation process.

93
00:04:24,390 --> 00:04:29,120
We've talked a lot about GDB, cling,
those different flags that we use when

94
00:04:29,120 --> 00:04:33,100
we compile something, and what
make15, for example, really

95
00:04:33,100 --> 00:04:34,510
means and really does.

96
00:04:34,510 --> 00:04:38,110
We have not talk as much about
every single step in

97
00:04:38,110 --> 00:04:39,240
the compilation process.

98
00:04:39,240 --> 00:04:40,410
We've still talked about it.

99
00:04:40,410 --> 00:04:42,550
So it's still something that you
should be familiar with.

100
00:04:42,550 --> 00:04:44,610
But again, we're not going to be--

101
00:04:44,610 --> 00:04:49,140
things that come up more often in class
are more likely to come up more

102
00:04:49,140 --> 00:04:52,495
often and be more heavily
weighted on the quiz.

103
00:04:52,495 --> 00:04:53,280
>> Cool.

104
00:04:53,280 --> 00:04:54,580
Any other questions about quiz 0?

105
00:04:54,580 --> 00:04:57,660

106
00:04:57,660 --> 00:05:00,050
>> OK, so I put a list of
topics on the board.

107
00:05:00,050 --> 00:05:01,550
I went through the syllabus.

108
00:05:01,550 --> 00:05:07,340
I went through the review section from
last night and those slides to come up

109
00:05:07,340 --> 00:05:13,710
with a non-exhaustive list of topics
that we have covered so far in CS50

110
00:05:13,710 --> 00:05:16,800
and things that might
appear on the quiz.

111
00:05:16,800 --> 00:05:19,900
So I'm not going to go through
every single one of these.

112
00:05:19,900 --> 00:05:22,370
That would take much more
time than we have now.

113
00:05:22,370 --> 00:05:26,880
But I put this up here to hopefully jog
your memory as to things that may

114
00:05:26,880 --> 00:05:28,420
or may not be as familiar with you.

115
00:05:28,420 --> 00:05:32,850
>> And I'd love to spend the bulk of
section answering your questions about

116
00:05:32,850 --> 00:05:35,130
these topics, topics that
aren't covered here.

117
00:05:35,130 --> 00:05:36,130
We can write pseudo code.

118
00:05:36,130 --> 00:05:40,010
We can write real code
to ensure that you--

119
00:05:40,010 --> 00:05:44,280
I can answer your question and help
everybody fundamentally understand a

120
00:05:44,280 --> 00:05:48,330
lot of these topics so you'll feel
prepared and comfortable going into

121
00:05:48,330 --> 00:05:50,150
the quiz tomorrow.

122
00:05:50,150 --> 00:05:52,300
So read over the list.

123
00:05:52,300 --> 00:05:54,780
You hopefully have come to section
with some questions as well.

124
00:05:54,780 --> 00:05:58,480
When you're ready, raise your hand
and we will get started.

125
00:05:58,480 --> 00:06:01,590

126
00:06:01,590 --> 00:06:05,200
>> Keep in mind, the questions you have,
there are no stupid questions.

127
00:06:05,200 --> 00:06:06,250
We've heard that a lot.

128
00:06:06,250 --> 00:06:09,490
And the questions you have, I am willing
to bet, many other people both

129
00:06:09,490 --> 00:06:11,740
sitting here and watching
online have as well.

130
00:06:11,740 --> 00:06:13,770
So you can only help people
by asking questions.

131
00:06:13,770 --> 00:06:15,070
Marcus.

132
00:06:15,070 --> 00:06:18,040
>> MARCUS: Between the stack and the
heap, is there a pre-allocated

133
00:06:18,040 --> 00:06:22,880
percentage of memory that's defined as
this is for the stack or for the heap?

134
00:06:22,880 --> 00:06:25,010
Or how does that work, exactly?

135
00:06:25,010 --> 00:06:26,230
>> JASON HIRSCHHORN: Great question.

136
00:06:26,230 --> 00:06:28,640
I'm going to back trace a little bit.

137
00:06:28,640 --> 00:06:30,910
Does everybody--

138
00:06:30,910 --> 00:06:31,660
please be honest here.

139
00:06:31,660 --> 00:06:34,130
I know I'm asking you to raise your
hand in front of your peers.

140
00:06:34,130 --> 00:06:38,510
But are there people who feel
uncomfortable with the stack and heap

141
00:06:38,510 --> 00:06:42,980
and would like to go over that
and what those mean?

142
00:06:42,980 --> 00:06:43,880
Raise your hand if--

143
00:06:43,880 --> 00:06:44,420
OK.

144
00:06:44,420 --> 00:06:45,120
Thank you.

145
00:06:45,120 --> 00:06:48,420
So we're going to go over the stack and
the heap really quickly and then

146
00:06:48,420 --> 00:06:50,370
move into answering your question.

147
00:06:50,370 --> 00:06:58,250
>> So if we draw out a box to represent
memory on your computer, what are some

148
00:06:58,250 --> 00:07:02,160
things that go in this box?

149
00:07:02,160 --> 00:07:03,630
Main.

150
00:07:03,630 --> 00:07:04,020
A main function.

151
00:07:04,020 --> 00:07:05,890
Where does main go?

152
00:07:05,890 --> 00:07:08,090
>> STUDENT: [INAUDIBLE].

153
00:07:08,090 --> 00:07:09,390
>> JASON HIRSCHHORN: So we'll
put main down here.

154
00:07:09,390 --> 00:07:12,180

155
00:07:12,180 --> 00:07:13,430
What else goes in this box?

156
00:07:13,430 --> 00:07:16,000

157
00:07:16,000 --> 00:07:18,140
>> STUDENT: The functions that you call.

158
00:07:18,140 --> 00:07:19,020
>> JASON HIRSCHHORN: The functions
that we call.

159
00:07:19,020 --> 00:07:20,440
And where do they go?

160
00:07:20,440 --> 00:07:21,300
>> STUDENT: In the stack.

161
00:07:21,300 --> 00:07:22,380
>> JASON HIRSCHHORN: They
go in the stack.

162
00:07:22,380 --> 00:07:27,350
So we're going to call this
thing down here the stack.

163
00:07:27,350 --> 00:07:31,880
And up top, we have the heap.

164
00:07:31,880 --> 00:07:35,450
So memory is not a box just like this.

165
00:07:35,450 --> 00:07:37,330
But it is actually pretty similar.

166
00:07:37,330 --> 00:07:40,840
It's going to be a lot of boxes over
and over, depending on how big your

167
00:07:40,840 --> 00:07:43,730
computer is or how big your memory is.

168
00:07:43,730 --> 00:07:46,950
>> At the quote-unquote "bottom"
is the stack.

169
00:07:46,950 --> 00:07:50,880
And there are multiple things
that go on the stack.

170
00:07:50,880 --> 00:07:53,840
And those depend on the functions
you have in your code.

171
00:07:53,840 --> 00:07:57,780
You always have one function in your
code called main, so there's always a

172
00:07:57,780 --> 00:08:00,480
section down here in the
stack devoted to main.

173
00:08:00,480 --> 00:08:03,980
>> These sections in the stack
are called stack frames.

174
00:08:03,980 --> 00:08:09,580
When you call another function, say main
calls a binary search function,

175
00:08:09,580 --> 00:08:11,075
we put another frame on the stack.

176
00:08:11,075 --> 00:08:13,830

177
00:08:13,830 --> 00:08:17,320
More specifically, we are going to
donate a chunk of memory on our

178
00:08:17,320 --> 00:08:22,960
computer to store binary search's local
variables and to run the binary

179
00:08:22,960 --> 00:08:24,150
search code.

180
00:08:24,150 --> 00:08:26,810
>> So we call binary search.

181
00:08:26,810 --> 00:08:30,440

182
00:08:30,440 --> 00:08:33,340
In this chunk of memory, we're going
to store its local variables.

183
00:08:33,340 --> 00:08:35,270
We're going to store its printf calls.

184
00:08:35,270 --> 00:08:38,159
Whatever happens, that function is
going to be stored right there.

185
00:08:38,159 --> 00:08:40,350
Binary search is going to execute.

186
00:08:40,350 --> 00:08:42,210
It is going to complete execution.

187
00:08:42,210 --> 00:08:47,450
What is the word in C that signifies
that a function should

188
00:08:47,450 --> 00:08:49,306
complete its execution?

189
00:08:49,306 --> 00:08:50,040
>> STUDENT: Return.

190
00:08:50,040 --> 00:08:50,870
>> JASON HIRSCHHORN: Return.

191
00:08:50,870 --> 00:08:53,230
So whenever you see a return statement,
the function ends

192
00:08:53,230 --> 00:08:54,350
when it hits that.

193
00:08:54,350 --> 00:08:56,740
So binary search will hit its return.

194
00:08:56,740 --> 00:09:01,360
This part of memory will essentially
be freed up.

195
00:09:01,360 --> 00:09:03,510
And main will go back to execution.

196
00:09:03,510 --> 00:09:07,240
So main will pause wherever was, call
binary search, get some return value,

197
00:09:07,240 --> 00:09:08,700
and continue execution.

198
00:09:08,700 --> 00:09:10,840
This stack frame will go away.

199
00:09:10,840 --> 00:09:14,810
>> If we call a recursive function, which
is a function that calls itself over

200
00:09:14,810 --> 00:09:18,480
and over, we might get-- say we
did binary search recursively.

201
00:09:18,480 --> 00:09:21,520
We might get binary search version one,
binary search two, binary search

202
00:09:21,520 --> 00:09:24,090
three, binary search four,
binary search five.

203
00:09:24,090 --> 00:09:27,950
And then this final binary search five
will hit the base case, and the stack

204
00:09:27,950 --> 00:09:31,010
frames will go back and keep closing
until we get back to main.

205
00:09:31,010 --> 00:09:32,530
We can go over recursion in a bit.

206
00:09:32,530 --> 00:09:35,530
But all this is to say, if you're
calling multiple functions at a time,

207
00:09:35,530 --> 00:09:39,250
there'll be multiple stack
frames on the stack.

208
00:09:39,250 --> 00:09:42,900
>> The heap, on the other hand, up
here, is not for functions,

209
00:09:42,900 --> 00:09:44,380
not for local variables.

210
00:09:44,380 --> 00:09:48,920
It's for dynamically allocated
variables.

211
00:09:48,920 --> 00:09:57,210
So these are variables that can be
initialized in either main or a

212
00:09:57,210 --> 00:09:58,640
function that main calls.

213
00:09:58,640 --> 00:10:00,790
Anywhere in your code, they
can be initialized.

214
00:10:00,790 --> 00:10:04,360
And to initialize a dynamically
allocated variable.

215
00:10:04,360 --> 00:10:06,970
What function in C do we use?

216
00:10:06,970 --> 00:10:07,600
>> STUDENT: Malloc.

217
00:10:07,600 --> 00:10:09,240
>> JASON HIRSCHHORN: Malloc.

218
00:10:09,240 --> 00:10:10,800
You call malloc.

219
00:10:10,800 --> 00:10:12,260
You get a space of memory.

220
00:10:12,260 --> 00:10:15,020
And that space of memory
is on the heap.

221
00:10:15,020 --> 00:10:18,840
And that space of memory stays
there until you call free.

222
00:10:18,840 --> 00:10:22,670
>> So dynamically allocated variables in
heap will exist for as long as you

223
00:10:22,670 --> 00:10:25,250
want them to exist, and they won't
go away until you explicitly

224
00:10:25,250 --> 00:10:26,760
tell them to go away.

225
00:10:26,760 --> 00:10:29,670
You can create them in one function.

226
00:10:29,670 --> 00:10:31,930
That function's stack
frame will go away.

227
00:10:31,930 --> 00:10:35,490
But that variable will still exist
in the heap until it is freed,

228
00:10:35,490 --> 00:10:39,650
potentially by the function that called
binary search or whatever.

229
00:10:39,650 --> 00:10:42,580
>> So those heap variables stay there
for as long as you want

230
00:10:42,580 --> 00:10:43,490
them to stay there.

231
00:10:43,490 --> 00:10:46,090
And they get put here.

232
00:10:46,090 --> 00:10:47,450
And then the next one gets put there.

233
00:10:47,450 --> 00:10:50,210
They keep getting filled in, and they
stay there until you call free.

234
00:10:50,210 --> 00:10:52,870
>> And essentially, the heap and the stack,
getting to Marcus's question,

235
00:10:52,870 --> 00:10:54,500
grow towards each other.

236
00:10:54,500 --> 00:10:57,730
And if they run into one another, you've
used up all the memory in your

237
00:10:57,730 --> 00:11:01,330
computer, and your program will quit
because you don't have any more memory

238
00:11:01,330 --> 00:11:02,420
left to use.

239
00:11:02,420 --> 00:11:07,290
In between them, there are
potentially other things.

240
00:11:07,290 --> 00:11:10,980
But for the scope of this course, you
don't need to worry about that.

241
00:11:10,980 --> 00:11:12,020
>> So that was the answer
to your question.

242
00:11:12,020 --> 00:11:13,520
Don't worry about it.

243
00:11:13,520 --> 00:11:15,550
But that was the long answer.

244
00:11:15,550 --> 00:11:17,800
All you need to know is the
heap and the stack will--

245
00:11:17,800 --> 00:11:18,900
one starts at the bottom.

246
00:11:18,900 --> 00:11:19,570
The stack does.

247
00:11:19,570 --> 00:11:20,790
The heap's up there.

248
00:11:20,790 --> 00:11:21,990
They will grow closer to one another.

249
00:11:21,990 --> 00:11:23,110
>> And if they touch, that's a problem.

250
00:11:23,110 --> 00:11:24,500
You ran out of memory.

251
00:11:24,500 --> 00:11:28,760
But also, in addition to knowing where
they are, what is stored in both the

252
00:11:28,760 --> 00:11:30,512
stack and heap.

253
00:11:30,512 --> 00:11:31,410
Curtis.

254
00:11:31,410 --> 00:11:33,570
>> CURTIS: When they collide,
is that a stack overflow?

255
00:11:33,570 --> 00:11:35,670
>> JASON HIRSCHHORN: When they collide,
that's not a stack overflow.

256
00:11:35,670 --> 00:11:38,340
A stack overflow is a different area
that we can go over if you want to.

257
00:11:38,340 --> 00:11:40,020
OK, we'll come back to that in a bit.

258
00:11:40,020 --> 00:11:42,730
>> STUDENT: What's the word called
when they hit each other, the

259
00:11:42,730 --> 00:11:44,450
stack and the heap?

260
00:11:44,450 --> 00:11:46,640
>> JASON HIRSCHHORN: For now,
don't worry about.

261
00:11:46,640 --> 00:11:47,750
Just know--

262
00:11:47,750 --> 00:11:50,530
I will answer that question
after class.

263
00:11:50,530 --> 00:11:52,680
If they run into each other, you ran out
of memory, because there's no more

264
00:11:52,680 --> 00:11:53,330
space there.

265
00:11:53,330 --> 00:11:55,450
>> STUDENT: Sorry, what's a seg fault?

266
00:11:55,450 --> 00:11:58,710
>> JASON HIRSCHHORN: A segment
fault can be called for--

267
00:11:58,710 --> 00:12:02,240
it depends why the seg fault's called.

268
00:12:02,240 --> 00:12:06,260
Sometimes, your stack overflow, it'll
say seg fault as the error.

269
00:12:06,260 --> 00:12:08,180
>> STUDENT: What about dereferencing
a null variable?

270
00:12:08,180 --> 00:12:10,040
Is that a seg fault?

271
00:12:10,040 --> 00:12:11,480
>> JASON HIRSCHHORN: Dereferencing
a null pointer--

272
00:12:11,480 --> 00:12:17,850
OK, so if you have a pointer that you
set equal to null, pointers, recall,

273
00:12:17,850 --> 00:12:20,270
store memory addresses
as their values.

274
00:12:20,270 --> 00:12:23,660
And a null pointer is essentially
storing 0, the 0-th

275
00:12:23,660 --> 00:12:26,670
address in that variable.

276
00:12:26,670 --> 00:12:30,010
So 0x, 0, 0, 0, 0, et cetera.

277
00:12:30,010 --> 00:12:35,030
That 0-th address in memory that's not
in our picture, that's up there

278
00:12:35,030 --> 00:12:38,800
somewhere, that's reserved
for the computer.

279
00:12:38,800 --> 00:12:40,130
We're not allowed to touch it.

280
00:12:40,130 --> 00:12:44,680
>> So when your program's executing, if
something is trying to go to memory

281
00:12:44,680 --> 00:12:48,990
address 0, it knows that
that is an empty value.

282
00:12:48,990 --> 00:12:50,820
It knows nothing should be there.

283
00:12:50,820 --> 00:12:53,420
So if you try and use something there
and treat something like there or

284
00:12:53,420 --> 00:12:58,355
trying to go to that location, you're
going to get a seg fault or an error.

285
00:12:58,355 --> 00:13:00,520
Does that answer your question?

286
00:13:00,520 --> 00:13:03,170
>> And now we'll go back
to stack overflow.

287
00:13:03,170 --> 00:13:09,560
Things in the stack, as you guys have
seen before, in-- let's draw a close

288
00:13:09,560 --> 00:13:11,966
up of a stack frame.

289
00:13:11,966 --> 00:13:15,050
Can everybody see that?

290
00:13:15,050 --> 00:13:16,650
So we have our stack frame.

291
00:13:16,650 --> 00:13:23,260
We're saving an array in as a local
variable in this function.

292
00:13:23,260 --> 00:13:29,510
So say our array has five spots.

293
00:13:29,510 --> 00:13:33,230
All five of those will be stored
in that stack frame.

294
00:13:33,230 --> 00:13:37,540
>> If we start writing beyond the
bounds of this array--

295
00:13:37,540 --> 00:13:43,990
so if we start writing into,
let's say that's 0.

296
00:13:43,990 --> 00:13:46,800
Those are the five indexes
of our array.

297
00:13:46,800 --> 00:13:50,980
If we start writing into index 5, which
we don't have when we have an

298
00:13:50,980 --> 00:13:55,900
array of size 5, we start writing into
index 6, 7, 8, 9, we can get a Stack

299
00:13:55,900 --> 00:13:57,960
Overflow error.

300
00:13:57,960 --> 00:14:00,510
>> Generally it's not--

301
00:14:00,510 --> 00:14:04,910
you will probably get into trouble
if you go over by one.

302
00:14:04,910 --> 00:14:08,640
But generally, you will get into the
most trouble if you go over by a lot

303
00:14:08,640 --> 00:14:12,770
and you go so far over that you write
over the return address of that

304
00:14:12,770 --> 00:14:16,080
function, which is located at the
bottom of the stack frame.

305
00:14:16,080 --> 00:14:16,520
>> Because, right?

306
00:14:16,520 --> 00:14:17,670
You-- in the-- sorry.

307
00:14:17,670 --> 00:14:18,550
Not "because right."

308
00:14:18,550 --> 00:14:20,470
>> In the stack frame, you have
your local variables.

309
00:14:20,470 --> 00:14:27,090
At the very bottom of the stack
frame is the return address.

310
00:14:27,090 --> 00:14:28,790
That's where the function
goes when it's over.

311
00:14:28,790 --> 00:14:33,750
And if you overwrite that return
address, then when this stack frame,

312
00:14:33,750 --> 00:14:36,680
when you're going through the stack
frame and executing each line, you're

313
00:14:36,680 --> 00:14:40,350
going to go to your new return address
that's written there instead of the

314
00:14:40,350 --> 00:14:40,910
actual one.

315
00:14:40,910 --> 00:14:45,050
And that's how we've seen
some security breaches

316
00:14:45,050 --> 00:14:46,780
can happen with computers.

317
00:14:46,780 --> 00:14:52,760
>> So stack overflow, in short, is when
you overwrite the part in the stack

318
00:14:52,760 --> 00:14:55,440
you're supposed to use, the local
variable you're supposed to use, and

319
00:14:55,440 --> 00:14:58,070
in particular when you start overwriting
important things like the

320
00:14:58,070 --> 00:14:59,100
return address.

321
00:14:59,100 --> 00:15:00,090
And that's where you'll get an error.

322
00:15:00,090 --> 00:15:03,980
Or maybe even you could start
even writing into--

323
00:15:03,980 --> 00:15:05,370
say binary search was
right above main.

324
00:15:05,370 --> 00:15:07,790
If you overwrote a lot, you
could write into main.

325
00:15:07,790 --> 00:15:10,230
But generally, you get an error before
then, because the computer knows

326
00:15:10,230 --> 00:15:12,270
you're doing something you
shouldn't be doing.

327
00:15:12,270 --> 00:15:12,560
Yeah.

328
00:15:12,560 --> 00:15:13,910
>> STUDENT: What's the difference
between a stack overflow

329
00:15:13,910 --> 00:15:16,940
and a buffer overflow?

330
00:15:16,940 --> 00:15:19,420
>> JASON HIRSCHHORN: Buffer overflow
is a more generic type of

331
00:15:19,420 --> 00:15:20,395
what I've just described.

332
00:15:20,395 --> 00:15:22,610
>> STUDENT: So a stack overflow is an
example of a buffer overflow.

333
00:15:22,610 --> 00:15:23,420
>> JASON HIRSCHHORN: Exactly.

334
00:15:23,420 --> 00:15:28,700
This is an array we can think of as a
buffer, a space for things to go in.

335
00:15:28,700 --> 00:15:30,600
This is a stack buffer overflow.

336
00:15:30,600 --> 00:15:33,210
We could have a heap buffer overflow.

337
00:15:33,210 --> 00:15:36,870
If there was a buffer, which there often
is an array the heap, and we

338
00:15:36,870 --> 00:15:40,600
overwrote those bounds, then we would
have a heap buffer overflow.

339
00:15:40,600 --> 00:15:44,870
>> And beyond the scope of this course,
they're detected a bit differently.

340
00:15:44,870 --> 00:15:48,040
The compiler has special
ways of detecting each.

341
00:15:48,040 --> 00:15:50,660
But a buffer overflow is a more generic
type of what I described,

342
00:15:50,660 --> 00:15:54,090
which was a stack buffer overflow.

343
00:15:54,090 --> 00:15:56,240
Did that answer your question?

344
00:15:56,240 --> 00:15:57,910
Sweet.

345
00:15:57,910 --> 00:16:01,850
>> Were there any other questions related
to the stack or the heap?

346
00:16:01,850 --> 00:16:04,920

347
00:16:04,920 --> 00:16:05,510
Yeah.

348
00:16:05,510 --> 00:16:08,220
>> STUDENT: I know you have to free strings
because they're in the heap

349
00:16:08,220 --> 00:16:09,305
and you don't want to leak memory.

350
00:16:09,305 --> 00:16:12,240
But do you have to free global variables
and stuff like that?

351
00:16:12,240 --> 00:16:14,335
Or are they automatically freed?

352
00:16:14,335 --> 00:16:15,700
>> JASON HIRSCHHORN: Good question.

353
00:16:15,700 --> 00:16:22,340
So in CS50.H, we create this thing
for you called a string.

354
00:16:22,340 --> 00:16:23,800
A string is really what?

355
00:16:23,800 --> 00:16:24,810
>> STUDENT: Char star.

356
00:16:24,810 --> 00:16:29,180
>> JASON HIRSCHHORN: A char star, a pointer
to a character, a pointer to

357
00:16:29,180 --> 00:16:30,650
an array of characters.

358
00:16:30,650 --> 00:16:32,210
That's what the string is.

359
00:16:32,210 --> 00:16:36,050
So we need to free it, because
getstring, which we used a lot--

360
00:16:36,050 --> 00:16:38,370
string name equals getstring--

361
00:16:38,370 --> 00:16:43,560
that mallocs for us some memory on the
heap and then returns a pointer to the

362
00:16:43,560 --> 00:16:47,230
first character of that
string, a char star.

363
00:16:47,230 --> 00:16:52,760
>> So ostensibly, if you have not been
writing free on any of your strings

364
00:16:52,760 --> 00:16:55,600
that you've called so far, you have
been leaking some memory.

365
00:16:55,600 --> 00:16:57,430
Of course we haven't talked about
it, so nobody's gotten in

366
00:16:57,430 --> 00:16:58,520
trouble for doing it.

367
00:16:58,520 --> 00:16:59,980
But going forward, yes.

368
00:16:59,980 --> 00:17:03,990
When you call getstring, you're
mallocing some space on the heap.

369
00:17:03,990 --> 00:17:07,640
And if you don't call free later on that
string, you have a memory leak.

370
00:17:07,640 --> 00:17:09,440
That answer your question?

371
00:17:09,440 --> 00:17:10,606
>> Yeah

372
00:17:10,606 --> 00:17:15,020
>> STUDENT: So to do that, do we use
free right before return?

373
00:17:15,020 --> 00:17:18,510
Like, within the scope of, I guess if
we say, like, int main, within the

374
00:17:18,510 --> 00:17:24,410
scope of the code that's within those
curly braces, right before--

375
00:17:24,410 --> 00:17:26,140
you know where you'd
usually put return.

376
00:17:26,140 --> 00:17:27,950
Do you put free before that?

377
00:17:27,950 --> 00:17:31,000
>> JASON HIRSCHHORN: So you can put free
wherever you want to put free.

378
00:17:31,000 --> 00:17:33,810
Because these are dynamically allocated
variables, because they can

379
00:17:33,810 --> 00:17:39,170
live beyond the scope of a particular
function, if you call malloc in a

380
00:17:39,170 --> 00:17:44,140
separate function, for example,
getstring, you can call free in main.

381
00:17:44,140 --> 00:17:46,050
You don't need to call it
in the specific function

382
00:17:46,050 --> 00:17:47,570
where malloc is called.

383
00:17:47,570 --> 00:17:50,340
But you do need to call it
before main returns.

384
00:17:50,340 --> 00:17:51,120
>> And it really depends.

385
00:17:51,120 --> 00:17:54,960
It depends on why you malloced that
space in the first place.

386
00:17:54,960 --> 00:17:57,320
Some people will call
free pretty quickly.

387
00:17:57,320 --> 00:17:59,220
Some people won't call free until
the end of their program.

388
00:17:59,220 --> 00:18:00,660
And they'll go through
and free everything.

389
00:18:00,660 --> 00:18:03,597
It depends on why you called malloc.

390
00:18:03,597 --> 00:18:11,270
>> STUDENT: And what would you say
if you called use getstring?

391
00:18:11,270 --> 00:18:13,320
You'd say free what?

392
00:18:13,320 --> 00:18:20,040
>> JASON HIRSCHHORN: So the syntax for free
is simply free, open paren, close

393
00:18:20,040 --> 00:18:22,130
paren, and the name of the pointer.

394
00:18:22,130 --> 00:18:26,410
So if you write string name equals
getstring, you put name in here.

395
00:18:26,410 --> 00:18:27,760
That's the name of the pointer.

396
00:18:27,760 --> 00:18:30,570
And it knows to free that memory.

397
00:18:30,570 --> 00:18:33,920
>> STUDENT: So when it frees that memory,
the pointer still points to that place

398
00:18:33,920 --> 00:18:34,970
in the memory?

399
00:18:34,970 --> 00:18:39,020
Or is the pointer also emptied of
the address that it points to.

400
00:18:39,020 --> 00:18:40,290
>> JASON HIRSCHHORN: We should try that.

401
00:18:40,290 --> 00:18:41,430
We should code that.

402
00:18:41,430 --> 00:18:43,880
Let's come back when we get to
coding, and let's code that.

403
00:18:43,880 --> 00:18:46,000
And if you want to figure out the answer
to that, you can also code that

404
00:18:46,000 --> 00:18:46,690
in the meantime.

405
00:18:46,690 --> 00:18:49,100
But that's a great question.

406
00:18:49,100 --> 00:18:53,480
>> STUDENT: Is it possible to
free something too soon?

407
00:18:53,480 --> 00:18:58,530
So you still need it for your program,
and you freed that memory space?

408
00:18:58,530 --> 00:18:59,200
>> JASON HIRSCHHORN: Yes.

409
00:18:59,200 --> 00:19:03,020
It is possible, if you free something
and then you use it again, you will

410
00:19:03,020 --> 00:19:06,890
run into an error.

411
00:19:06,890 --> 00:19:10,810
But that's on you, because you freed
something and then called it later.

412
00:19:10,810 --> 00:19:13,940
So that was a programmer's mistake.

413
00:19:13,940 --> 00:19:14,780
But yes.

414
00:19:14,780 --> 00:19:17,760
You could write that.

415
00:19:17,760 --> 00:19:19,240
>> Any more questions on--

416
00:19:19,240 --> 00:19:19,760
yes.

417
00:19:19,760 --> 00:19:22,820
>> STUDENT: So if you are supposed to just
free it in general before the

418
00:19:22,820 --> 00:19:25,490
program ends, does that mean if the
program ends and you don't free it,

419
00:19:25,490 --> 00:19:27,580
that memory is still allocated?

420
00:19:27,580 --> 00:19:31,330
>> JASON HIRSCHHORN: If your program ends
and you forget to free something, then

421
00:19:31,330 --> 00:19:34,390
that memory was allocated throughout
the lifetime of your program.

422
00:19:34,390 --> 00:19:37,670
When your program closes completely,
that memory is not going

423
00:19:37,670 --> 00:19:39,490
to stay there forever.

424
00:19:39,490 --> 00:19:42,080
The computer is smart enough to know
that when the program closes, it

425
00:19:42,080 --> 00:19:46,440
should get rid of all of the memory that
was associated with that program.

426
00:19:46,440 --> 00:19:51,240
>> However, there are tools you can run
on a program to detect if, when the

427
00:19:51,240 --> 00:19:54,720
program finished, you forgot
to free some memory.

428
00:19:54,720 --> 00:19:57,960
And for your next problem set where
you'll be using malloc and using

429
00:19:57,960 --> 00:20:02,610
pointers, you will be running this
program on your program to see if,

430
00:20:02,610 --> 00:20:06,530
when main returns, you had some
things that were left unfreed.

431
00:20:06,530 --> 00:20:09,130
>> So they're not going to stay malloced
forever in your computer.

432
00:20:09,130 --> 00:20:11,720
That would be wasteful, because
very quickly, computers

433
00:20:11,720 --> 00:20:12,960
would run out of memory.

434
00:20:12,960 --> 00:20:16,450
But if they run until the end of your
program and they're not freed and your

435
00:20:16,450 --> 00:20:20,260
program exits, that's still a problem
that this tool will help you address.

436
00:20:20,260 --> 00:20:21,520
>> STUDENT: Is that Valgrind?

437
00:20:21,520 --> 00:20:22,910
>> JASON HIRSCHHORN: It's
called Valgrind.

438
00:20:22,910 --> 00:20:23,520
And you'll be--

439
00:20:23,520 --> 00:20:25,780
>> STUDENT: But we don't have to know
that for the quiz, though?

440
00:20:25,780 --> 00:20:27,600
I mean, it was talked about
a little bit in lecture.

441
00:20:27,600 --> 00:20:33,600
>> JASON HIRSCHHORN: So Valgrind
is the name of that tool.

442
00:20:33,600 --> 00:20:37,180
Knowing what it does is
enough for the quiz.

443
00:20:37,180 --> 00:20:40,200
But you have not used it yet on your
problem set because we haven't had a

444
00:20:40,200 --> 00:20:43,520
problem set that has explicitly dealt
with malloc or you using malloc.

445
00:20:43,520 --> 00:20:45,330
So you haven't used Valgrind yet.

446
00:20:45,330 --> 00:20:47,760
But you will use it sooner
rather than later.

447
00:20:47,760 --> 00:20:48,710
>> STUDENT: Can you repeat
what Valgrind is?

448
00:20:48,710 --> 00:20:49,190
>> JASON HIRSCHHORN: Sorry?

449
00:20:49,190 --> 00:20:51,240
>> STUDENT: Can you repeat what
the purpose of Valgring is?

450
00:20:51,240 --> 00:20:53,100
>> JASON HIRSCHHORN: Valgrind
is the name--

451
00:20:53,100 --> 00:20:59,890
like GDB helps you debug your program,
Valgrind helps you figure out if

452
00:20:59,890 --> 00:21:03,210
things have not been freed
when your program closes.

453
00:21:03,210 --> 00:21:05,110
So you'll run it on your program.

454
00:21:05,110 --> 00:21:09,230
And your program exits, and it'll say
your program called malloc this many

455
00:21:09,230 --> 00:21:13,670
times for this many bytes, and you
only called free this many times.

456
00:21:13,670 --> 00:21:16,520
And so you left these many bytes
without being freed.

457
00:21:16,520 --> 00:21:18,050
Or it'll say you've freed everything.

458
00:21:18,050 --> 00:21:19,070
Good job.

459
00:21:19,070 --> 00:21:19,480
>> STUDENT: OK.

460
00:21:19,480 --> 00:21:21,060
And it's called Valgring?

461
00:21:21,060 --> 00:21:24,940
>> JASON HIRSCHHORN: V-A-L-G-R-I-N-D.

462
00:21:24,940 --> 00:21:25,970
>> STUDENT: A question about pointers.

463
00:21:25,970 --> 00:21:30,080
So say you have n star
x equals something.

464
00:21:30,080 --> 00:21:33,330
That equals, whatever you're putting
there, is that what's being put inside

465
00:21:33,330 --> 00:21:36,120
what x is pointing to,
or the pointer of x?

466
00:21:36,120 --> 00:21:37,690
>> JASON HIRSCHHORN: Can you
repeat the question?

467
00:21:37,690 --> 00:21:39,340
Can we draw it while you say it?

468
00:21:39,340 --> 00:21:42,710
>> STUDENT: In the quiz, actually, the
one you sent us, it was like, char

469
00:21:42,710 --> 00:21:46,520
star truth equals CS50 rocks, right?

470
00:21:46,520 --> 00:21:52,190
So does that mean that that CS50 rocks
is what the truth is pointing to?

471
00:21:52,190 --> 00:21:55,810
>> JASON HIRSCHHORN: So you're talking
about a char star in a string, how

472
00:21:55,810 --> 00:21:56,460
that works?

473
00:21:56,460 --> 00:21:56,890
Yeah.

474
00:21:56,890 --> 00:21:57,700
OK.

475
00:21:57,700 --> 00:21:59,140
Let's draw this over here.

476
00:21:59,140 --> 00:22:07,100
>> [SIDE CONVERSATION]

477
00:22:07,100 --> 00:22:11,130
>> JASON HIRSCHHORN: So this variable
is going to be of type char star.

478
00:22:11,130 --> 00:22:14,580
How big is a variable
of type char star?

479
00:22:14,580 --> 00:22:15,510
How many bytes?

480
00:22:15,510 --> 00:22:16,450
>> STUDENTS: Four.

481
00:22:16,450 --> 00:22:18,210
>> JASON HIRSCHHORN: It's four bytes.

482
00:22:18,210 --> 00:22:21,420
How many rights is a variable
of type int star?

483
00:22:21,420 --> 00:22:22,210
>> STUDENTS: Four.

484
00:22:22,210 --> 00:22:24,910
>> JASON HIRSCHHORN: Four bytes.

485
00:22:24,910 --> 00:22:28,280
If it's a pointer, then it is always
four bytes, because pointers, their

486
00:22:28,280 --> 00:22:30,070
value is a memory address.

487
00:22:30,070 --> 00:22:35,160
And memory addresses on the CS50
appliance are four bytes long.

488
00:22:35,160 --> 00:22:42,900
So when we call getstring, or when we
say, stringname equals, and then in

489
00:22:42,900 --> 00:22:46,140
double quotes put a string,
we are putting--

490
00:22:46,140 --> 00:22:46,920
well, that's a little different.

491
00:22:46,920 --> 00:22:48,630
We'll do getstring as the example.

492
00:22:48,630 --> 00:22:52,150
Or char star something
equals the string.

493
00:22:52,150 --> 00:22:54,360
Sorry, give me the example
that you read?

494
00:22:54,360 --> 00:22:57,590
>> STUDENT: char star truth equals
"cs50 rocks" in double quotes.

495
00:22:57,590 --> 00:23:02,260
>> JASON HIRSCHHORN: So this star, this
we'll call this variable x for our

496
00:23:02,260 --> 00:23:04,060
generic purposes.

497
00:23:04,060 --> 00:23:05,970
We've created a variable called x.

498
00:23:05,970 --> 00:23:07,610
It's type char star.

499
00:23:07,610 --> 00:23:10,950
It is a pointer to a series
of characters.

500
00:23:10,950 --> 00:23:12,200
So down here--

501
00:23:12,200 --> 00:23:23,710

502
00:23:23,710 --> 00:23:25,890
>> So this is how this would
work in memory.

503
00:23:25,890 --> 00:23:27,410
This would store a memory address.

504
00:23:27,410 --> 00:23:31,770
It would store the memory address of
the first character in the array.

505
00:23:31,770 --> 00:23:33,830
And then when you followed
the pointer, you would

506
00:23:33,830 --> 00:23:35,200
get the first character.

507
00:23:35,200 --> 00:23:38,780
>> And if you're reading this thing like
a string, your computer is smart

508
00:23:38,780 --> 00:23:42,930
enough to know, read this whole thing
until it gets to a backlash 0.

509
00:23:42,930 --> 00:23:45,530
But if you're reading it a character at
a time, so you're iterating through

510
00:23:45,530 --> 00:23:49,910
this string, then you will just read a
character at a time until you get to

511
00:23:49,910 --> 00:23:50,850
backslash 0.

512
00:23:50,850 --> 00:23:52,335
That might not answer your
question, though.

513
00:23:52,335 --> 00:23:55,610
>> STUDENT: Yeah, but you haven't
malloced that space

514
00:23:55,610 --> 00:23:58,400
yet for that pointer.

515
00:23:58,400 --> 00:24:02,510
>> JASON HIRSCHHORN: So I'm not quite sure
exactly what you're looking at,

516
00:24:02,510 --> 00:24:03,640
because I didn't make that quiz.

517
00:24:03,640 --> 00:24:06,370
That was supposed to be a helpful
resource from another TF.

518
00:24:06,370 --> 00:24:11,380
If you are creating a string on the
stack or as a local variable, it'll

519
00:24:11,380 --> 00:24:16,920
just be array of charges rather than
generally a char star pointing to

520
00:24:16,920 --> 00:24:18,600
another string.

521
00:24:18,600 --> 00:24:20,550
But I don't know.

522
00:24:20,550 --> 00:24:25,065
That could be a pointer to another
string on the stack as well.

523
00:24:25,065 --> 00:24:27,240
Yeah.

524
00:24:27,240 --> 00:24:31,116
>> STUDENT: I know that you need to
allocate memory if the pointer is

525
00:24:31,116 --> 00:24:33,360
getting declared inside
of another function.

526
00:24:33,360 --> 00:24:36,740
Do you need to do the same thing if it's
being declared inside of main,

527
00:24:36,740 --> 00:24:39,570
you're using it inside of main?

528
00:24:39,570 --> 00:24:43,590
>> JASON HIRSCHHORN: So yes.

529
00:24:43,590 --> 00:24:46,670
You can declare a pointer to any
memory address in memory.

530
00:24:46,670 --> 00:24:51,440
It can be the memory address of a local
variable, though oftentimes,

531
00:24:51,440 --> 00:24:55,760
people don't declare memory addresses
to local variables because they go

532
00:24:55,760 --> 00:24:59,890
away once that function returns, which
is why we generally malloc things.

533
00:24:59,890 --> 00:25:04,630
But yes, you could declare a pointer
to another local variable.

534
00:25:04,630 --> 00:25:06,360
It's just generally not done.

535
00:25:06,360 --> 00:25:09,480
But I can take a look at that
specific thing after class.

536
00:25:09,480 --> 00:25:10,650
Yeah.

537
00:25:10,650 --> 00:25:12,350
>> STUDENT: I think this is sort
of what's being asked.

538
00:25:12,350 --> 00:25:16,930
It does seem strange to be initializing
a pointer not as an

539
00:25:16,930 --> 00:25:20,760
address, but as what
seems like a value.

540
00:25:20,760 --> 00:25:25,970
It seems like the CS50 is what's inside
the thing being pointed to and

541
00:25:25,970 --> 00:25:28,820
not the actual address, right?

542
00:25:28,820 --> 00:25:30,520
>> JASON HIRSCHHORN: So that's
not the case, though.

543
00:25:30,520 --> 00:25:32,470
That's not what's happening.

544
00:25:32,470 --> 00:25:35,910
When you declare a char star,
it's a memory address.

545
00:25:35,910 --> 00:25:38,860
Pointers are all memory addresses
pointing to something else.

546
00:25:38,860 --> 00:25:41,480
That something else could be on the
stack, but almost always is on the

547
00:25:41,480 --> 00:25:43,440
heap in the way we will see it used.

548
00:25:43,440 --> 00:25:46,860

549
00:25:46,860 --> 00:25:53,500
But stringname equals double-quote
"getstring," we can see that and we

550
00:25:53,500 --> 00:25:55,010
can look through that and code that.

551
00:25:55,010 --> 00:26:01,190
getstring string is not being saved in
that variable, or whatever the string

552
00:26:01,190 --> 00:26:04,580
name is is not being saved in that
variable, because that's not how

553
00:26:04,580 --> 00:26:06,070
pointers work.

554
00:26:06,070 --> 00:26:06,770
Does that make sense?

555
00:26:06,770 --> 00:26:07,170
>> STUDENT: Yeah.

556
00:26:07,170 --> 00:26:08,570
>> JASON HIRSCHHORN: OK.

557
00:26:08,570 --> 00:26:11,690
Hopefully, that wasn't
confusing to anyone.

558
00:26:11,690 --> 00:26:15,732
But if it was, we can look at it again
in a bit, because we're actually going

559
00:26:15,732 --> 00:26:19,240
to code something that will hopefully
work with strings and help you feel

560
00:26:19,240 --> 00:26:22,170
more comfortable with them.

561
00:26:22,170 --> 00:26:24,869
>> Any other questions related to these
topics or other topics that

562
00:26:24,869 --> 00:26:26,119
I'll put back up?

563
00:26:26,119 --> 00:26:32,280

564
00:26:32,280 --> 00:26:34,840
And--

565
00:26:34,840 --> 00:26:36,310
right now.

566
00:26:36,310 --> 00:26:37,630
Yes, Alden.

567
00:26:37,630 --> 00:26:39,860
>> ALDEN: So this is completely unrelated,
but can we just go over

568
00:26:39,860 --> 00:26:42,760
really quickly what we need to know
about the difference between a 32 and

569
00:26:42,760 --> 00:26:46,345
64-bit machine?

570
00:26:46,345 --> 00:26:47,740
>> JASON HIRSCHHORN: Yes.

571
00:26:47,740 --> 00:26:52,111
So 32 bits is how many bytes?

572
00:26:52,111 --> 00:26:53,060
>> ALDEN: It's four bytes.

573
00:26:53,060 --> 00:26:54,360
>> JASON HIRSCHHORN: It's four bytes.

574
00:26:54,360 --> 00:26:58,420
And 64 bits is how many bytes?

575
00:26:58,420 --> 00:26:59,112
>> STUDENT: Eight.

576
00:26:59,112 --> 00:27:00,610
>> JASON HIRSCHHORN: Eight bytes.

577
00:27:00,610 --> 00:27:03,980
So again, eight bits is one byte.

578
00:27:03,980 --> 00:27:08,340
Your CS50 appliance is
a 32-bit machine.

579
00:27:08,340 --> 00:27:13,650
So memory addresses are
four bytes long.

580
00:27:13,650 --> 00:27:17,460
There are 2 to the 32
memory addresses.

581
00:27:17,460 --> 00:27:21,310
0 to 2 to the 32 minus 1.

582
00:27:21,310 --> 00:27:27,630
And I am not positive, but that's
probably the scope of what you need to

583
00:27:27,630 --> 00:27:35,230
know for a 32-bit machine, that memory
addresses are, again, four bytes long,

584
00:27:35,230 --> 00:27:39,620
and that's the maximum amount
of memory addresses.

585
00:27:39,620 --> 00:27:41,680
>> Also, data types--

586
00:27:41,680 --> 00:27:45,020
this might be something as
well that's worth noting.

587
00:27:45,020 --> 00:27:49,610
The size of a data type depends on
the machine you're working with.

588
00:27:49,610 --> 00:27:56,760
So a char, a single character, is how
many bytes on our CS50 appliance?

589
00:27:56,760 --> 00:27:57,980
One byte.

590
00:27:57,980 --> 00:28:02,310
And it's actually one byte as
well on a 64-bit machine.

591
00:28:02,310 --> 00:28:05,920
>> And most data types are the same number
of bytes on both machines.

592
00:28:05,920 --> 00:28:11,620
But some data types will be different
on both machines.

593
00:28:11,620 --> 00:28:14,590
So that would be potentially the
only thing you need to know.

594
00:28:14,590 --> 00:28:16,710
>> But even that, I think,
is beyond the bounds--

595
00:28:16,710 --> 00:28:20,990
I'm almost positive, if you look back
at old quizzes, it says, assume for

596
00:28:20,990 --> 00:28:24,090
coding problems you're using
a 32-bit machine.

597
00:28:24,090 --> 00:28:26,620

598
00:28:26,620 --> 00:28:30,620
But there are, to go along with that in
case you're interested, there are

599
00:28:30,620 --> 00:28:35,920
data types that are the same
size on all machines.

600
00:28:35,920 --> 00:28:42,670
>> If you've seen something like
uint32_t, you may or may

601
00:28:42,670 --> 00:28:43,260
not have seen that.

602
00:28:43,260 --> 00:28:44,290
That's a data type.

603
00:28:44,290 --> 00:28:47,570
That is saying, be 32 bits no matter
what machine this is on.

604
00:28:47,570 --> 00:28:50,350
So when people are writing portable
code, they probably won't use ints.

605
00:28:50,350 --> 00:28:53,260
They'll instead use these other data
types that they know will be the same

606
00:28:53,260 --> 00:28:54,780
size on every single machine.

607
00:28:54,780 --> 00:28:58,080

608
00:28:58,080 --> 00:28:58,250
Madhu.

609
00:28:58,250 --> 00:29:00,150
>> MADHU: I had a question about
the compilation process.

610
00:29:00,150 --> 00:29:04,110
So if you're writing a program that uses
a library like CS50 or something

611
00:29:04,110 --> 00:29:06,840
like that, I know that that library
has to, at some point, be

612
00:29:06,840 --> 00:29:08,590
compiled and linked in.

613
00:29:08,590 --> 00:29:13,380
But how much of that happens during
the compilation of your program?

614
00:29:13,380 --> 00:29:15,880
What part of that library process
occurs when you're

615
00:29:15,880 --> 00:29:18,560
compiling your own program?

616
00:29:18,560 --> 00:29:24,020
>> JASON HIRSCHHORN: So let's go over
generally the steps of this process.

617
00:29:24,020 --> 00:29:26,280
You write your .c file.

618
00:29:26,280 --> 00:29:33,530
In your .c file, you #include your
header libraries, for example, cs50.h.

619
00:29:33,530 --> 00:29:39,480
What does that sharp include
line do to your program?

620
00:29:39,480 --> 00:29:40,525
Akchar.

621
00:29:40,525 --> 00:29:43,350
>> AKCHAR: It adds the prototypes of
the functions from the header

622
00:29:43,350 --> 00:29:45,120
files in the libraries.

623
00:29:45,120 --> 00:29:45,600
>> JASON HIRSCHHORN: Exactly.

624
00:29:45,600 --> 00:29:49,870
It adds those function prototypes
to your code.

625
00:29:49,870 --> 00:29:55,230
So when your code is being compiled in
the early stages, the compiler knows

626
00:29:55,230 --> 00:29:59,250
that these functions really exist, and
that somewhere they have been defined.

627
00:29:59,250 --> 00:30:02,460
The .h files don't include the
definitions for these functions or how

628
00:30:02,460 --> 00:30:03,950
they actually work.

629
00:30:03,950 --> 00:30:07,960
Cs50.h just includes something that says
getstring is a real thing that

630
00:30:07,960 --> 00:30:09,270
can happen.

631
00:30:09,270 --> 00:30:14,240
And standardio.h says printf is
a real thing that can happen.

632
00:30:14,240 --> 00:30:23,190
>> So your c language with this .header
file gets turned into some

633
00:30:23,190 --> 00:30:27,750
machine-readable code, which eventually
gets turned into binary

634
00:30:27,750 --> 00:30:30,030
code, 0's and 1's.

635
00:30:30,030 --> 00:30:33,590
And that's the code that ultimately
gets executed.

636
00:30:33,590 --> 00:30:38,550
The -l cs50 line-- for example,
when you're writing Clang--

637
00:30:38,550 --> 00:30:41,830
and then you include -l cs50,
you type that in.

638
00:30:41,830 --> 00:30:42,180
And you see that.

639
00:30:42,180 --> 00:30:43,890
When you write make, you'll
see that line up here.

640
00:30:43,890 --> 00:30:47,740
And we'll see that in a second when
we code or later on when we code.

641
00:30:47,740 --> 00:30:50,390
>> But that -l cs50 line does something
a bit different than

642
00:30:50,390 --> 00:30:52,440
the #include cs50.h.

643
00:30:52,440 --> 00:30:56,300
What does that -l cs50 line do?

644
00:30:56,300 --> 00:30:56,820
Avi?

645
00:30:56,820 --> 00:31:00,310
>> AVI: I want to say that it links
the library to the function

646
00:31:00,310 --> 00:31:02,710
call, like the .o files.

647
00:31:02,710 --> 00:31:08,200
>> JASON HIRSCHHORN: So very
close, if not spot-on.

648
00:31:08,200 --> 00:31:16,220
The -l cs50 takes the binary file and
merges it with your binary file.

649
00:31:16,220 --> 00:31:21,410
So cs50.h, there's no point in turning
cs50.h from C language to binary every

650
00:31:21,410 --> 00:31:23,130
single time it's being used.

651
00:31:23,130 --> 00:31:26,650
That would be silly, because that
would waste a lot of time.

652
00:31:26,650 --> 00:31:30,420
So it has already been compiled
and turned into an executable.

653
00:31:30,420 --> 00:31:35,430
And now it is going to be merged
with your file at the end.

654
00:31:35,430 --> 00:31:38,370
So those 1's and 0's are going
to merge with your ones

655
00:31:38,370 --> 00:31:39,150
and 0's at the end.

656
00:31:39,150 --> 00:31:43,670
So now you'll actually have the actual
1's and 0's that define how getstring,

657
00:31:43,670 --> 00:31:47,890
for example, works, or how printf,
for example, works.

658
00:31:47,890 --> 00:31:52,750
>> And for more information, there's a
short compilers that Nate gives that

659
00:31:52,750 --> 00:31:55,410
you should check out that goes
through these steps.

660
00:31:55,410 --> 00:31:56,050
But--

661
00:31:56,050 --> 00:31:56,560
yes.

662
00:31:56,560 --> 00:32:01,700
>> STUDENT: Are they always in .o files
when they're in the library form,

663
00:32:01,700 --> 00:32:06,764
ready to be merged, linked-- like
they're in the binary code?

664
00:32:06,764 --> 00:32:07,600
>> JASON HIRSCHHORN: OK.

665
00:32:07,600 --> 00:32:08,420
What--

666
00:32:08,420 --> 00:32:11,780
>> STUDENT: Is that always the case for
the libraries when you link them?

667
00:32:11,780 --> 00:32:12,500
>> JASON HIRSCHHORN: Yes.

668
00:32:12,500 --> 00:32:17,300
So there's .s files, which will be
machine code, which will also be

669
00:32:17,300 --> 00:32:17,975
cryptic to you.

670
00:32:17,975 --> 00:32:19,410
You don't need to worry about those.

671
00:32:19,410 --> 00:32:24,930
But generally, yeah, they'll
be in .o files ready to go.

672
00:32:24,930 --> 00:32:27,170
>> STUDENT: So when you ship to
a library, do you only ship

673
00:32:27,170 --> 00:32:28,880
the .h and the .o?

674
00:32:28,880 --> 00:32:32,210
You don't ship the .c or the .s.

675
00:32:32,210 --> 00:32:33,070
>> JASON HIRSCHHORN: So--

676
00:32:33,070 --> 00:32:36,260
and this is in this short as well, if
this information seems to be coming a

677
00:32:36,260 --> 00:32:36,700
little quickly.

678
00:32:36,700 --> 00:32:39,870
But the short on compilers
talks about this as well.

679
00:32:39,870 --> 00:32:43,290
When you ship a library, if you ship
the .h, the header file, those

680
00:32:43,290 --> 00:32:46,290
function prototypes, and the 1's and
0's, that's all you need to give.

681
00:32:46,290 --> 00:32:50,640
You don't need to give how the
function works, the .c file.

682
00:32:50,640 --> 00:32:56,360
Because the point of abstraction, or the
point APIs, the point at this SPL,

683
00:32:56,360 --> 00:32:59,650
the Stanford portable library, it's
for you to not worry about how new

684
00:32:59,650 --> 00:33:04,220
GRect works, or how move works,
or how add works.

685
00:33:04,220 --> 00:33:06,520
All you need to know is that add
is a function that you can

686
00:33:06,520 --> 00:33:08,880
use, and it does this.

687
00:33:08,880 --> 00:33:12,760
So you really don't need to know how
it's written in C. You just need to

688
00:33:12,760 --> 00:33:15,460
know, here are the functions, what they
do, and here are the 1's and 0's

689
00:33:15,460 --> 00:33:18,870
when you really want to use them.

690
00:33:18,870 --> 00:33:19,530
>> Cool.

691
00:33:19,530 --> 00:33:26,980
Any more questions on compilers
or other topics on the board?

692
00:33:26,980 --> 00:33:30,300
>> STUDENT: I have a question of
implementing recursive functions.

693
00:33:30,300 --> 00:33:31,170
A question about recursion.

694
00:33:31,170 --> 00:33:33,030
I had a feeling that would come up.

695
00:33:33,030 --> 00:33:38,310
So let's quickly go through
recursion with a specific

696
00:33:38,310 --> 00:33:40,690
example, a factorial function.

697
00:33:40,690 --> 00:33:44,920
Because this is an example that
often comes up or is used

698
00:33:44,920 --> 00:33:46,170
to illustrate recursion.

699
00:33:46,170 --> 00:33:52,390

700
00:33:52,390 --> 00:33:56,410
>> So "4!" is read as 4 factorial.

701
00:33:56,410 --> 00:33:59,120
And what does 4 factorial mean?

702
00:33:59,120 --> 00:34:00,696
What does that do?

703
00:34:00,696 --> 00:34:02,235
How do you calculate 4 factorial?

704
00:34:02,235 --> 00:34:05,250

705
00:34:05,250 --> 00:34:07,960
4 times 3 times 2 times 1.

706
00:34:07,960 --> 00:34:11,889
>> So another way to write 4 factorial
is to write this.

707
00:34:11,889 --> 00:34:16,780

708
00:34:16,780 --> 00:34:19,022
4 times 3 factorial.

709
00:34:19,022 --> 00:34:22,080
Because 3 factorial is
3 times 2 times 1.

710
00:34:22,080 --> 00:34:27,580
So 4 times 3 factorial is 4
times 3 times 2 times 1.

711
00:34:27,580 --> 00:34:32,679
This is why factorial is a great
candidate for recursion, because it's

712
00:34:32,679 --> 00:34:36,630
clear that there is something that
happens over and over and over on a

713
00:34:36,630 --> 00:34:39,820
smaller number of things until
you reach the end.

714
00:34:39,820 --> 00:34:42,570
When you reach 1, 1 factorial is 1.

715
00:34:42,570 --> 00:34:43,719
You can't go much further.

716
00:34:43,719 --> 00:34:47,219
0 factorial is also defined as 1.

717
00:34:47,219 --> 00:34:50,679
So when you get to 1 or 0, you're
at the end, and you can

718
00:34:50,679 --> 00:34:53,219
start going back up.

719
00:34:53,219 --> 00:34:59,540
So if we wanted to write a recursive
function to calculate a factorial,

720
00:34:59,540 --> 00:35:02,170
we're going to write some
pseudocode for that now.

721
00:35:02,170 --> 00:35:03,300
Before we write that pseudocode--

722
00:35:03,300 --> 00:35:05,660
I'll give you guys a couple of minutes
to write the pseudo code or just think

723
00:35:05,660 --> 00:35:09,600
about it-- there are two things every
recursive function needs.

724
00:35:09,600 --> 00:35:12,530
What are those two things?

725
00:35:12,530 --> 00:35:13,220
>> JACK: It has to call itself.

726
00:35:13,220 --> 00:35:13,680
>> JASON HIRSCHHORN: Noah?

727
00:35:13,680 --> 00:35:14,460
Oh, Jack.

728
00:35:14,460 --> 00:35:15,100
Go ahead.

729
00:35:15,100 --> 00:35:16,640
>> JACK: It has to call itself.

730
00:35:16,640 --> 00:35:19,220
>> JASON HIRSCHHORN: So a recursive
function needs a recursive call, a

731
00:35:19,220 --> 00:35:20,220
call to itself.

732
00:35:20,220 --> 00:35:20,770
That's one.

733
00:35:20,770 --> 00:35:21,510
And what's the other thing?

734
00:35:21,510 --> 00:35:22,250
>> JACK: A base case.

735
00:35:22,250 --> 00:35:23,780
>> JASON HIRSCHHORN: A base case.

736
00:35:23,780 --> 00:35:26,940
A base case is, here's when we stop.

737
00:35:26,940 --> 00:35:29,510
So your function gets called.

738
00:35:29,510 --> 00:35:31,410
The base case comes first.

739
00:35:31,410 --> 00:35:33,710
You want to know if you're at the end.

740
00:35:33,710 --> 00:35:37,110
And if you're not at the end, you
make your recursive call.

741
00:35:37,110 --> 00:35:39,880
And you go through this function again,
check your base case again.

742
00:35:39,880 --> 00:35:42,575
If you're not the end, you make
another recursive call,

743
00:35:42,575 --> 00:35:44,130
et cetera, et cetera.

744
00:35:44,130 --> 00:35:47,110
>> That's why recursive functions always
need those base cases and those

745
00:35:47,110 --> 00:35:48,210
recursive calls.

746
00:35:48,210 --> 00:35:51,280
If you don't have a recursive call, it
wouldn't be a recursive function.

747
00:35:51,280 --> 00:35:53,210
If you didn't have a base case,
you would go forever and

748
00:35:53,210 --> 00:35:54,780
there would be no ending.

749
00:35:54,780 --> 00:35:57,870
And the base case always comes first,
because you will always want to check

750
00:35:57,870 --> 00:36:00,420
if you're at the end first.

751
00:36:00,420 --> 00:36:04,770
So before we do some pseudocode, why
don't you take a minute to think about

752
00:36:04,770 --> 00:36:09,360
how a recursive factorial function
would be written?

753
00:36:09,360 --> 00:36:23,340

754
00:36:23,340 --> 00:36:26,010
>> Also, as many as you are doing, writing
it out on a sheet of paper is

755
00:36:26,010 --> 00:36:27,960
what you're going to have to
do on the quiz tomorrow.

756
00:36:27,960 --> 00:36:32,160
So probably good practice to make
sure the code you're writing

757
00:36:32,160 --> 00:36:34,420
down on sheet of paper--

758
00:36:34,420 --> 00:36:35,160
or you can do that.

759
00:36:35,160 --> 00:36:36,710
You know where the semicolons are.

760
00:36:36,710 --> 00:36:37,660
You remember the syntax.

761
00:36:37,660 --> 00:36:40,400
Because you're not be able to have a
compiler tell you made an error.

762
00:36:40,400 --> 00:37:02,356

763
00:37:02,356 --> 00:37:07,240
>> Also, along those lines, tomorrow, when
you have coding problems, if you

764
00:37:07,240 --> 00:37:11,490
are rushed for time, or if you're very
confused as to how you're supposed to

765
00:37:11,490 --> 00:37:16,030
write the particular thing in c, it
would behoove you to write pseudo-code

766
00:37:16,030 --> 00:37:18,160
or write comments in as well.

767
00:37:18,160 --> 00:37:21,940
Because there's partial credit for a
lot of the questions on the quiz.

768
00:37:21,940 --> 00:37:24,840
So you might be rushed, or you
might just be confused.

769
00:37:24,840 --> 00:37:28,030
Writing in comments or pseudo-code
are often ways that you

770
00:37:28,030 --> 00:37:29,360
can get partial credit.

771
00:37:29,360 --> 00:37:31,440
>> So don't leave something
blank on the quiz.

772
00:37:31,440 --> 00:37:33,490
There's no penalties for
putting things in.

773
00:37:33,490 --> 00:37:37,650
In fact, putting in pseudo-code or
comments is going to help the grader

774
00:37:37,650 --> 00:37:40,410
figure out if you actually know what
you're talking about, and maybe award

775
00:37:40,410 --> 00:37:42,030
you some partial credit for that.

776
00:37:42,030 --> 00:37:44,510
>> Also along those lines, write clearly.

777
00:37:44,510 --> 00:37:47,650
If we can't really what you're writing,
we're not going to call you

778
00:37:47,650 --> 00:37:49,900
at midnight tomorrow to figure
out what you wrote.

779
00:37:49,900 --> 00:37:51,520
We're just going to take off points.

780
00:37:51,520 --> 00:37:56,570
Write clearly so we can hear, or rather,
we can read what you wrote.

781
00:37:56,570 --> 00:38:00,230
>> And if it says two sentences,
don't write a paragraph.

782
00:38:00,230 --> 00:38:02,280
Follow the instructions.

783
00:38:02,280 --> 00:38:03,500
Write clearly.

784
00:38:03,500 --> 00:38:07,720
And write in those comments or
pseudocode for questions that could

785
00:38:07,720 --> 00:38:10,270
award partial credit.

786
00:38:10,270 --> 00:38:12,520
>> OK, let's go to factorial.

787
00:38:12,520 --> 00:38:15,000
So we have a function factorial.

788
00:38:15,000 --> 00:38:18,400

789
00:38:18,400 --> 00:38:21,550
If I were to actually write this in C,
what do I need to put before the name

790
00:38:21,550 --> 00:38:22,800
of the function?

791
00:38:22,800 --> 00:38:24,880

792
00:38:24,880 --> 00:38:30,060
The return type, which, in this
case, we'll give it int.

793
00:38:30,060 --> 00:38:35,450
And then inside the curly braces, is
what goes inside the curly braces for

794
00:38:35,450 --> 00:38:36,850
a function?

795
00:38:36,850 --> 00:38:37,950
>> STUDENTS: Argument type.

796
00:38:37,950 --> 00:38:39,150
>> JASON HIRSCHHORN: Its arguments.

797
00:38:39,150 --> 00:38:42,680
So factorial will probably
take an argument.

798
00:38:42,680 --> 00:38:44,500
It'll probably only take one argument.

799
00:38:44,500 --> 00:38:49,450
And we'll say it'll take
an integer called x.

800
00:38:49,450 --> 00:38:52,770
And again, when writing the prototype of
a function or writing the function

801
00:38:52,770 --> 00:38:57,110
in your code before defining it, you
write the data type and the name of

802
00:38:57,110 --> 00:39:01,370
that variable for that function only.

803
00:39:01,370 --> 00:39:06,350
So you can pass some number into this
function, it'll be referred to as x

804
00:39:06,350 --> 00:39:07,340
internally.

805
00:39:07,340 --> 00:39:08,755
>> We have our factorial function.

806
00:39:08,755 --> 00:39:12,030

807
00:39:12,030 --> 00:39:15,850
We need two things, a base case
and a recursive call.

808
00:39:15,850 --> 00:39:20,900
What is the base case for factorial?

809
00:39:20,900 --> 00:39:24,850
Somebody who wrote it out and who hasn't
spoken yet, what is the base

810
00:39:24,850 --> 00:39:26,100
case for factorial?

811
00:39:26,100 --> 00:39:28,400

812
00:39:28,400 --> 00:39:30,930
>> STUDENT: If n is less
than 2, return 1.

813
00:39:30,930 --> 00:39:33,520
>> JASON HIRSCHHORN: If n is
less than 2, return 1.

814
00:39:33,520 --> 00:39:37,216
I like that, because that
takes care of 0 and 1.

815
00:39:37,216 --> 00:39:45,290
So we'll do x < 2, return 1.

816
00:39:45,290 --> 00:39:47,870
If we get passed 0, if we get
passed 1, this function will

817
00:39:47,870 --> 00:39:49,790
immediately return 1.

818
00:39:49,790 --> 00:39:54,020
If we get passed some number greater
than or equal to 2, we're going to

819
00:39:54,020 --> 00:39:55,370
have our recursive call.

820
00:39:55,370 --> 00:39:57,855
>> And so how is that going to work?

821
00:39:57,855 --> 00:40:01,070
Can somebody else who worked on this
who hasn't spoken yet give me the

822
00:40:01,070 --> 00:40:07,380
recursive call for this function
in pseudocode?

823
00:40:07,380 --> 00:40:10,770
If we get passed in a number x
and it's greater than 2, what

824
00:40:10,770 --> 00:40:13,370
do we want to do?

825
00:40:13,370 --> 00:40:17,930
We also have an example written on the
side that might give you a hint.

826
00:40:17,930 --> 00:40:20,770
>> STUDENT: Call x times the
factorial of x minus 1?

827
00:40:20,770 --> 00:40:22,020
>> JASON HIRSCHHORN: Exactly right.

828
00:40:22,020 --> 00:40:24,610

829
00:40:24,610 --> 00:40:37,750
We're going to return x times
the factorial of x minus 1.

830
00:40:37,750 --> 00:40:41,810
And that, even though I wrote up,
basically, what you said in English,

831
00:40:41,810 --> 00:40:44,580
this factorial function
will get called again.

832
00:40:44,580 --> 00:40:46,320
It'll execute on x minus 1.

833
00:40:46,320 --> 00:40:49,320
It'll return with some integer, and
then it'll multiply these two

834
00:40:49,320 --> 00:40:52,050
together, and that value will be
returned to whatever called this

835
00:40:52,050 --> 00:40:55,010
factorial function, which might
be another instance of

836
00:40:55,010 --> 00:40:58,420
this factorial function.

837
00:40:58,420 --> 00:41:01,360
>> So that is an example of a recursive
function, a very

838
00:41:01,360 --> 00:41:02,530
simple recursive function.

839
00:41:02,530 --> 00:41:04,530
But most of them will be like this.

840
00:41:04,530 --> 00:41:11,170
If you would like a good recursive
challenge for the quiz, try coding

841
00:41:11,170 --> 00:41:13,230
binary search recursively.

842
00:41:13,230 --> 00:41:18,950
Because if you did binary search for
problem set three, you probably did it

843
00:41:18,950 --> 00:41:21,730
iteratively in a while loop.

844
00:41:21,730 --> 00:41:23,700
>> But it can also be written
recursively.

845
00:41:23,700 --> 00:41:26,310
You're going to need to write your own
separate function that takes some

846
00:41:26,310 --> 00:41:29,020
different command-line arguments-- or
not command-line arguments, some

847
00:41:29,020 --> 00:41:30,910
different just regular arguments.

848
00:41:30,910 --> 00:41:33,870
But you could write binary search
recursively as well.

849
00:41:33,870 --> 00:41:36,190
>> STUDENT: So you could have also written,
instead of x minus 1, you

850
00:41:36,190 --> 00:41:39,502
could have also written x minus
minus, or you could have

851
00:41:39,502 --> 00:41:40,830
written minus minus x.

852
00:41:40,830 --> 00:41:44,740
Can you just explain really quickly why
those would be different things,

853
00:41:44,740 --> 00:41:49,510
like what the difference is between
x minus minus and minus minus x?

854
00:41:49,510 --> 00:41:51,320
>> JASON HIRSCHHORN: No, I'm not
going to go into that.

855
00:41:51,320 --> 00:41:55,500
But I will talk to you about it after
class. x minus minus, minus minus x

856
00:41:55,500 --> 00:41:57,780
decrement x by 1.

857
00:41:57,780 --> 00:41:59,090
But they do it a bit differently.

858
00:41:59,090 --> 00:42:00,340
But I don't want to go into that.

859
00:42:00,340 --> 00:42:04,330

860
00:42:04,330 --> 00:42:09,090
Other questions about recursion
or this function?

861
00:42:09,090 --> 00:42:10,140
That's not really even pseudocode.

862
00:42:10,140 --> 00:42:15,060
That's basically the code in
C you would write for this.

863
00:42:15,060 --> 00:42:19,393
>> OK, any other questions
about topics up here?

864
00:42:19,393 --> 00:42:19,864
Yeah.

865
00:42:19,864 --> 00:42:23,130
>> STUDENT: I have a quick rundown of
floating point and precision.

866
00:42:23,130 --> 00:42:24,260
>> JASON HIRSCHHORN: Floating
point and precision.

867
00:42:24,260 --> 00:42:26,920
Can somebody really quickly
give me a rundown of

868
00:42:26,920 --> 00:42:28,210
floating point and precision?

869
00:42:28,210 --> 00:42:30,420
You all had to do this for your
problem set, so you're all

870
00:42:30,420 --> 00:42:31,700
familiar with it.

871
00:42:31,700 --> 00:42:35,090
Or maybe not all of you.

872
00:42:35,090 --> 00:42:36,602
Anyone?

873
00:42:36,602 --> 00:42:39,530
Give me a started spot.

874
00:42:39,530 --> 00:42:40,750
Floating point and precision.

875
00:42:40,750 --> 00:42:42,380
What's the problem?

876
00:42:42,380 --> 00:42:42,960
Yes.

877
00:42:42,960 --> 00:42:43,680
Victoria?

878
00:42:43,680 --> 00:42:44,480
>> VANESSA: Vanessa.

879
00:42:44,480 --> 00:42:45,285
>> JASON HIRSCHHORN: Vanessa.

880
00:42:45,285 --> 00:42:45,680
Sorry.

881
00:42:45,680 --> 00:42:51,550
>> VANESSA: There's only a finite number
of numbers that can be represented

882
00:42:51,550 --> 00:42:57,930
because you're on a, in our
case, a 32-bit system.

883
00:42:57,930 --> 00:43:03,080
So you kind of have to
make up some numbers.

884
00:43:03,080 --> 00:43:03,910
>> JASON HIRSCHHORN: So that's
exactly right.

885
00:43:03,910 --> 00:43:08,110
There are only a certain amount of
numbers that can be represented.

886
00:43:08,110 --> 00:43:11,770
If you multiply two very large numbers,
it might overflow the amount

887
00:43:11,770 --> 00:43:13,950
of spaces you have to represent
an integer.

888
00:43:13,950 --> 00:43:17,930
That's why sometimes we use a
long long instead of an int.

889
00:43:17,930 --> 00:43:19,210
That has more spaces.

890
00:43:19,210 --> 00:43:21,210
That can hold a larger number.

891
00:43:21,210 --> 00:43:24,310
>> Floating point precision has to do with
that, but also has to do with the

892
00:43:24,310 --> 00:43:29,300
fact that decimal numbers are
not always represented.

893
00:43:29,300 --> 00:43:29,540
Sorry.

894
00:43:29,540 --> 00:43:31,280
Let me put this back up.

895
00:43:31,280 --> 00:43:36,610
The decimal number 1.0 is not always
represented like you would expect,

896
00:43:36,610 --> 00:43:40,770
1.000000000.

897
00:43:40,770 --> 00:43:50,360
It is sometimes represented as
1.000000001 or 0.999999999.

898
00:43:50,360 --> 00:43:52,780
It might be even 89 thrown
in there somewhere.

899
00:43:52,780 --> 00:43:56,560
So those decimal numbers aren't
represented exactly like you would

900
00:43:56,560 --> 00:43:58,430
expect them to be represented.

901
00:43:58,430 --> 00:44:00,010
>> So in problem set--

902
00:44:00,010 --> 00:44:00,860
was it two?--

903
00:44:00,860 --> 00:44:05,290
problem set two, where we dealt with
floating point numbers, when we wanted

904
00:44:05,290 --> 00:44:08,690
them to represent exactly what we wanted
them to represent, the number

905
00:44:08,690 --> 00:44:12,860
of pennies, or the number of cents,
we multiply them by 100.

906
00:44:12,860 --> 00:44:14,750
We rounded them.

907
00:44:14,750 --> 00:44:18,660
And then we cut off everything
behind the decimal point.

908
00:44:18,660 --> 00:44:22,020
That was to ensure that they would
actually equal exactly what we wanted

909
00:44:22,020 --> 00:44:22,410
them to equal.

910
00:44:22,410 --> 00:44:26,870
>> Because when you take something that's
a float and turn it into an int, you

911
00:44:26,870 --> 00:44:29,860
cut off everything to the right
of the decimal point.

912
00:44:29,860 --> 00:44:33,900
Because there's some floating point
imprecision, 100.000 might be

913
00:44:33,900 --> 00:44:37,440
represented as 99.999999999.

914
00:44:37,440 --> 00:44:40,350
And if you just cut off everything to
the right right away, you're going to

915
00:44:40,350 --> 00:44:41,600
get the wrong number.

916
00:44:41,600 --> 00:44:44,050

917
00:44:44,050 --> 00:44:44,180
Yeah.

918
00:44:44,180 --> 00:44:45,290
>> STUDENT: I had a question
about casting.

919
00:44:45,290 --> 00:44:47,500
What order does it occur in?

920
00:44:47,500 --> 00:44:54,480
If you'd do float, brackets, 1 divided
by 10, does it do 1 divided by 10,

921
00:44:54,480 --> 00:44:58,910
then get 0.1, then turn
it into a float?

922
00:44:58,910 --> 00:45:01,470
>> JASON HIRSCHHORN: If you do
float 1 divided by 10--

923
00:45:01,470 --> 00:45:02,550
>> STUDENT: Yeah, and then equals--

924
00:45:02,550 --> 00:45:04,240
well, it would normally
have it equal in--

925
00:45:04,240 --> 00:45:04,690
Yeah.

926
00:45:04,690 --> 00:45:06,760
You want to make it a float, right?

927
00:45:06,760 --> 00:45:12,790
>> JASON HIRSCHHORN: OK, so we're going to
use that to segue into figuring out

928
00:45:12,790 --> 00:45:15,390
the answers to these questions
through coding.

929
00:45:15,390 --> 00:45:18,180
Because you'll probably have a lot of
these minute questions, and a good way

930
00:45:18,180 --> 00:45:19,100
to solve them is through coding.

931
00:45:19,100 --> 00:45:21,320
So we're going to code this right now,
and then we're going to go back and

932
00:45:21,320 --> 00:45:24,020
code the question you had.

933
00:45:24,020 --> 00:45:24,950
>> So the first line--

934
00:45:24,950 --> 00:45:29,390
I shouldn't have written it-- what is
the first thing we want to do when we

935
00:45:29,390 --> 00:45:32,250
open up a new file in gedit?

936
00:45:32,250 --> 00:45:34,190
>> STUDENT: Include.

937
00:45:34,190 --> 00:45:35,920
>> JASON HIRSCHHORN: Include what?

938
00:45:35,920 --> 00:45:37,952
>> STUDENT: CS50 library.

939
00:45:37,952 --> 00:45:39,920
>> JASON HIRSCHHORN: OK.

940
00:45:39,920 --> 00:45:42,590
What else should we include?

941
00:45:42,590 --> 00:45:46,820
We're just going to check what happens
when you cast something to a float.

942
00:45:46,820 --> 00:45:48,605
But what do we need to include if we're
going to write a C program?

943
00:45:48,605 --> 00:45:49,300
>> STUDENT: Standard I/O.

944
00:45:49,300 --> 00:45:50,625
>> JASON HIRSCHHORN: stdio.h.

945
00:45:50,625 --> 00:45:54,880
We actually don't need, for this
program, cs50.h, even though it's

946
00:45:54,880 --> 00:45:55,920
always helpful to include it.

947
00:45:55,920 --> 00:45:58,260
But we do always need stdio.h.

948
00:45:58,260 --> 00:45:59,660
>> STUDENT: When coding in C?

949
00:45:59,660 --> 00:46:15,770
>> JASON HIRSCHHORN: When coding in C.

950
00:46:15,770 --> 00:46:17,090
>> So I save it as this .c file.

951
00:46:17,090 --> 00:46:18,590
I get some nice syntax highlighting.

952
00:46:18,590 --> 00:46:22,890
I wrote void inside main.

953
00:46:22,890 --> 00:46:24,792
What does void mean?

954
00:46:24,792 --> 00:46:26,740
>> STUDENT: Doesn't take any
command-line arguments.

955
00:46:26,740 --> 00:46:28,900
>> JASON HIRSCHHORN: Void means, in this
case, main doesn't take any

956
00:46:28,900 --> 00:46:29,700
command-line arguments.

957
00:46:29,700 --> 00:46:32,720
In other cases, it means the function
doesn't take command-line arguments.

958
00:46:32,720 --> 00:46:36,560
Or the function, if I were to write void
main(void), that would say main's

959
00:46:36,560 --> 00:46:38,460
not returning anything.

960
00:46:38,460 --> 00:46:39,960
So void just means nothing.

961
00:46:39,960 --> 00:46:42,510
What would I write if I were to
take command-line arguments?

962
00:46:42,510 --> 00:46:45,250

963
00:46:45,250 --> 00:46:47,150
>> STUDENT: int arc c string arc v.

964
00:46:47,150 --> 00:46:49,055
>> JASON HIRSCHHORN: int
argc string argv.

965
00:46:49,055 --> 00:46:54,050

966
00:46:54,050 --> 00:46:55,572
Is that right?

967
00:46:55,572 --> 00:46:58,720
>> STUDENT: It's char star argv brackets.

968
00:46:58,720 --> 00:47:01,730
>> JASON HIRSCHHORN: So you could write
string argv brackets or char star argv

969
00:47:01,730 --> 00:47:03,710
brackets, but you need the brackets.

970
00:47:03,710 --> 00:47:06,290
Because argv is an array
of strings, remember.

971
00:47:06,290 --> 00:47:07,360
It's not just one string.

972
00:47:07,360 --> 00:47:10,350
So string argv is, here's
one string called argv.

973
00:47:10,350 --> 00:47:13,630
String argv brackets is, here's
an array of strings.

974
00:47:13,630 --> 00:47:17,865
So int argc string argv brackets
would be something that I

975
00:47:17,865 --> 00:47:18,810
would probably write.

976
00:47:18,810 --> 00:47:23,050
>> So you wanted to save in an integer?

977
00:47:23,050 --> 00:47:24,285
>> STUDENT: Yeah, integer.

978
00:47:24,285 --> 00:47:25,840
Or in a float.

979
00:47:25,840 --> 00:47:26,710
>> JASON HIRSCHHORN: In a float?

980
00:47:26,710 --> 00:47:30,790
Like, float x equals 1 divided by 10.

981
00:47:30,790 --> 00:47:32,040
>> JASON HIRSCHHORN: OK.

982
00:47:32,040 --> 00:47:40,160

983
00:47:40,160 --> 00:47:42,240
How do I print out a float in printf?

984
00:47:42,240 --> 00:47:45,100

985
00:47:45,100 --> 00:47:46,714
What?

986
00:47:46,714 --> 00:47:47,560
>> STUDENT: %f.

987
00:47:47,560 --> 00:47:48,300
>> JASON HIRSCHHORN: %f.

988
00:47:48,300 --> 00:47:50,810
What's an integer?

989
00:47:50,810 --> 00:47:52,110
d or i.

990
00:47:52,110 --> 00:47:53,000
What's a string?

991
00:47:53,000 --> 00:47:54,240
>> STUDENT: s.

992
00:47:54,240 --> 00:47:56,140
>> JASON HIRSCHHORN: s.

993
00:47:56,140 --> 00:47:57,550
How do I get a new line?

994
00:47:57,550 --> 00:47:58,800
>> STUDENT: Backslash n.

995
00:47:58,800 --> 00:48:04,610

996
00:48:04,610 --> 00:48:07,100
>> JASON HIRSCHHORN: What do I return
if main runs correctly?

997
00:48:07,100 --> 00:48:08,360
>> STUDENT: 0.

998
00:48:08,360 --> 00:48:09,430
Do I need to write that line, though?

999
00:48:09,430 --> 00:48:10,170
>> STUDENT: No.

1000
00:48:10,170 --> 00:48:11,513
OK, we won't write it, then.

1001
00:48:11,513 --> 00:48:16,450

1002
00:48:16,450 --> 00:48:17,190
Can everybody read that?

1003
00:48:17,190 --> 00:48:18,485
It looks a bit small.

1004
00:48:18,485 --> 00:48:20,160
Can everybody see, or should
I make it bigger?

1005
00:48:20,160 --> 00:48:23,480

1006
00:48:23,480 --> 00:48:25,100
I think for the camera, we'll make
it a bit bigger, though.

1007
00:48:25,100 --> 00:48:35,750

1008
00:48:35,750 --> 00:48:38,410
>> JASON HIRSCHHORN: If I want to turn this
.c file into an executable, what

1009
00:48:38,410 --> 00:48:39,260
do I write?

1010
00:48:39,260 --> 00:48:41,610
>> STUDENT: Make test.

1011
00:48:41,610 --> 00:48:42,080
>> JASON HIRSCHHORN: Sorry?

1012
00:48:42,080 --> 00:48:42,790
>> STUDENT: Make test.

1013
00:48:42,790 --> 00:48:44,040
>> JASON HIRSCHHORN: Make test.

1014
00:48:44,040 --> 00:48:46,700

1015
00:48:46,700 --> 00:48:48,410
We were talking about
this line earlier.

1016
00:48:48,410 --> 00:48:49,140
Clang.

1017
00:48:49,140 --> 00:48:51,270
What's clang?

1018
00:48:51,270 --> 00:48:52,200
The name of the compiler.

1019
00:48:52,200 --> 00:48:53,920
What's this line?

1020
00:48:53,920 --> 00:48:55,580
>> STUDENT: Sets it up for use of GDB.

1021
00:48:55,580 --> 00:48:59,230
>> JASON HIRSCHHORN: Sets
it up for use of GDB.

1022
00:48:59,230 --> 00:49:02,338
This line, what's that?

1023
00:49:02,338 --> 00:49:03,290
>> STUDENT: Source code.

1024
00:49:03,290 --> 00:49:06,010
>> JASON HIRSCHHORN: That's the
source file, the .c file.

1025
00:49:06,010 --> 00:49:08,150
What do these two lines do?

1026
00:49:08,150 --> 00:49:10,245
Or these two not lines.

1027
00:49:10,245 --> 00:49:12,300
>> STUDENT: It names it test.

1028
00:49:12,300 --> 00:49:15,410
>> JASON HIRSCHHORN: So the dash o says,
name it something differently.

1029
00:49:15,410 --> 00:49:16,790
And here you're calling it test.

1030
00:49:16,790 --> 00:49:18,900
If I didn't have that in,
what would it name this?

1031
00:49:18,900 --> 00:49:20,260
>> STUDENT: A.out.

1032
00:49:20,260 --> 00:49:22,340
>> JASON HIRSCHHORN: A.out.

1033
00:49:22,340 --> 00:49:25,366
What does this do?

1034
00:49:25,366 --> 00:49:27,670
>> STUDENT: Links the math library.

1035
00:49:27,670 --> 00:49:29,550
>> JASON HIRSCHHORN: It links
in the math library.

1036
00:49:29,550 --> 00:49:32,880
We didn't include the math library, but
since that's so common, they've

1037
00:49:32,880 --> 00:49:35,780
written make to always include
the math library.

1038
00:49:35,780 --> 00:49:39,050
And likewise, this includes
the CS50 library.

1039
00:49:39,050 --> 00:49:43,010
>> OK, so if we list, we now have
an executable called test.

1040
00:49:43,010 --> 00:49:45,150
To execute it, I write test.

1041
00:49:45,150 --> 00:49:48,330
I see that my floating point,
as expected, equals 0.

1042
00:49:48,330 --> 00:49:50,890

1043
00:49:50,890 --> 00:49:51,590
Does that--

1044
00:49:51,590 --> 00:49:52,060
so--

1045
00:49:52,060 --> 00:49:55,210
>> STUDENT: Then if you put float now,
like you cast it as float--

1046
00:49:55,210 --> 00:49:56,870
>> JASON HIRSCHHORN: Cast
the 1 to a float?

1047
00:49:56,870 --> 00:49:59,180
>> STUDENT: No, cast the full thing--

1048
00:49:59,180 --> 00:49:59,500
yeah.

1049
00:49:59,500 --> 00:50:02,460
If you just did that, would
that make it 0.1?

1050
00:50:02,460 --> 00:50:07,170
>> JASON HIRSCHHORN: OK, so really quickly,
1 divided by 10, those are

1051
00:50:07,170 --> 00:50:08,690
integers being divided.

1052
00:50:08,690 --> 00:50:13,580
So when you divide integers, they're
0, and you're saving that 0 in a

1053
00:50:13,580 --> 00:50:17,170
float, because the slash is
just integer division.

1054
00:50:17,170 --> 00:50:19,180
So now we're turning something
into a float.

1055
00:50:19,180 --> 00:50:21,650
>> Let's see what happens.

1056
00:50:21,650 --> 00:50:22,900
We'll make test.

1057
00:50:22,900 --> 00:50:25,870

1058
00:50:25,870 --> 00:50:31,090
So now we see that that slash was not
integer division, it was floating

1059
00:50:31,090 --> 00:50:32,640
point division.

1060
00:50:32,640 --> 00:50:35,700
Because one of its arguments
had been cast to a float.

1061
00:50:35,700 --> 00:50:38,380
So now it was saying, treat this
division like we're dealing with

1062
00:50:38,380 --> 00:50:40,140
floating points, not with integers.

1063
00:50:40,140 --> 00:50:42,760
And so we get the answer we expect.

1064
00:50:42,760 --> 00:50:44,620
>> Let's see what happens--

1065
00:50:44,620 --> 00:50:47,103
oops.

1066
00:50:47,103 --> 00:50:51,646
If I wanted to print more decimal
spots, how could I do that?

1067
00:50:51,646 --> 00:50:55,550
>> STUDENT: Point dot f, or as many
decimal places as you want.

1068
00:50:55,550 --> 00:51:02,280

1069
00:51:02,280 --> 00:51:04,440
>> JASON HIRSCHHORN: So I print
10 decimal spots.

1070
00:51:04,440 --> 00:51:06,610
And we now see we're getting
some weird stuff.

1071
00:51:06,610 --> 00:51:09,650
And that goes back to your question
about floating point imprecision.

1072
00:51:09,650 --> 00:51:10,950
There's weird stuff stored in here.

1073
00:51:10,950 --> 00:51:13,650

1074
00:51:13,650 --> 00:51:15,275
>> OK, does that answer your question?

1075
00:51:15,275 --> 00:51:18,550

1076
00:51:18,550 --> 00:51:20,200
What else did you want
to code quickly?

1077
00:51:20,200 --> 00:51:25,470
>> STUDENT: I just wanted to see whether or
not, if you freed up some pointer,

1078
00:51:25,470 --> 00:51:30,410
whether that pointer still had stored in
it the address of what it had been

1079
00:51:30,410 --> 00:51:32,170
pointing to previously.

1080
00:51:32,170 --> 00:51:34,100
>> JASON HIRSCHHORN: OK,
so let's do that.

1081
00:51:34,100 --> 00:51:38,030
Char star ptr, this creates a variable
called ptr of type char star.

1082
00:51:38,030 --> 00:51:39,280
How do I write malloc?

1083
00:51:39,280 --> 00:51:40,550
Alden?

1084
00:51:40,550 --> 00:51:41,800
>> ALDEN: Just malloc.

1085
00:51:41,800 --> 00:51:44,820

1086
00:51:44,820 --> 00:51:51,040
But then it has to be size of, and
in this case, I guess you'd

1087
00:51:51,040 --> 00:51:52,465
be pointing to char.

1088
00:51:52,465 --> 00:51:54,450
So it'd be char.

1089
00:51:54,450 --> 00:51:57,520
>> JASON HIRSCHHORN: OK, so more
generically, Inside--

1090
00:51:57,520 --> 00:51:58,770
let's edit.

1091
00:51:58,770 --> 00:52:05,100

1092
00:52:05,100 --> 00:52:09,260
Inside malloc, you want the number
of bytes on the heap.

1093
00:52:09,260 --> 00:52:12,320
Generally, what we've seen that we're
doing is we're going to malloc

1094
00:52:12,320 --> 00:52:14,940
strings, for example, or
arrays of integers.

1095
00:52:14,940 --> 00:52:21,600
So if we want 10 integers, or 10
chars, 10 will give us 10.

1096
00:52:21,600 --> 00:52:24,370
And then size of chars would give
us that size of chars, which in

1097
00:52:24,370 --> 00:52:25,120
this case is 1 byte.

1098
00:52:25,120 --> 00:52:26,250
We get 10 bytes.

1099
00:52:26,250 --> 00:52:28,540
If we were to write size of int,
that would give us 40 bytes.

1100
00:52:28,540 --> 00:52:31,520
>> So more generically, inside of malloc
is the number of bytes you want.

1101
00:52:31,520 --> 00:52:34,620
In this case, we're getting 1 byte.

1102
00:52:34,620 --> 00:52:36,900
Which seems like a weird use
of malloc, but for our

1103
00:52:36,900 --> 00:52:38,470
purposes makes sense.

1104
00:52:38,470 --> 00:52:40,420
So there's that.

1105
00:52:40,420 --> 00:52:43,420
>> We're going to call free.

1106
00:52:43,420 --> 00:52:47,040
We get rid of it and we use ptr again.

1107
00:52:47,040 --> 00:52:48,750
And what did you want to check?

1108
00:52:48,750 --> 00:52:50,550
>> STUDENT: I just wanted to check whether
or not there was anything

1109
00:52:50,550 --> 00:52:51,900
inside of it.

1110
00:52:51,900 --> 00:52:53,050
>> JASON HIRSCHHORN: So whether
it pointed to anything?

1111
00:52:53,050 --> 00:52:57,740
>> STUDENT: Yeah, exactly, whether
it still had a memory address.

1112
00:52:57,740 --> 00:53:02,220
>> JASON HIRSCHHORN: So you want
to check the value of ptr?

1113
00:53:02,220 --> 00:53:03,470
>> STUDENT: Yeah, exactly.

1114
00:53:03,470 --> 00:53:07,940

1115
00:53:07,940 --> 00:53:10,160
>> JASON HIRSCHHORN: What do I write here
if I want to check the value of the

1116
00:53:10,160 --> 00:53:11,880
point-- what is, Jordan
said, the value?

1117
00:53:11,880 --> 00:53:13,720
Or what is stored inside of ptr?

1118
00:53:13,720 --> 00:53:14,620
>> STUDENT: A memory address.

1119
00:53:14,620 --> 00:53:16,330
>> JASON HIRSCHHORN: A memory address.

1120
00:53:16,330 --> 00:53:20,520
So if I write just this, it'll
give me the value of ptr.

1121
00:53:20,520 --> 00:53:22,800
And how do I print out
a memory address?

1122
00:53:22,800 --> 00:53:26,470
What's the format string
for a memory address?

1123
00:53:26,470 --> 00:53:27,430
>> STUDENT: %p.

1124
00:53:27,430 --> 00:53:28,050
>> JASON HIRSCHHORN: %p.

1125
00:53:28,050 --> 00:53:29,500
%s is a string.

1126
00:53:29,500 --> 00:53:30,750
%p for pointer.

1127
00:53:30,750 --> 00:53:40,820

1128
00:53:40,820 --> 00:53:43,540
Is that right?

1129
00:53:43,540 --> 00:53:44,790
That is right.

1130
00:53:44,790 --> 00:53:49,450

1131
00:53:49,450 --> 00:53:51,040
So ptr equals--

1132
00:53:51,040 --> 00:53:53,350
it still has something in it.

1133
00:53:53,350 --> 00:53:56,110

1134
00:53:56,110 --> 00:53:57,645
This is probably a more
interesting question.

1135
00:53:57,645 --> 00:53:59,198
What does that line do?

1136
00:53:59,198 --> 00:54:00,830
>> STUDENT: Seg faults.

1137
00:54:00,830 --> 00:54:01,310
>> JASON HIRSCHHORN: What?

1138
00:54:01,310 --> 00:54:02,678
>> STUDENT: I think it seg faults.

1139
00:54:02,678 --> 00:54:03,574
>> JASON HIRSCHHORN: Hm?

1140
00:54:03,574 --> 00:54:04,920
>> STUDENT: I think it'll seg fault.

1141
00:54:04,920 --> 00:54:08,265
>> JASON HIRSCHHORN: So this line
of code, star ptr, what

1142
00:54:08,265 --> 00:54:10,152
does the star mean?

1143
00:54:10,152 --> 00:54:11,240
>> STUDENT: Content of.

1144
00:54:11,240 --> 00:54:11,560
>> JASON HIRSCHHORN: Yeah.

1145
00:54:11,560 --> 00:54:13,910
Go to get the content of.

1146
00:54:13,910 --> 00:54:16,830
So this is going to go to the memory
address there and give me that.

1147
00:54:16,830 --> 00:54:21,030
I used %c right here because there
are characters stored there.

1148
00:54:21,030 --> 00:54:23,390
So we're going to go to that address we
just saw-- or it'll probably be a

1149
00:54:23,390 --> 00:54:25,190
little bit different this
time we run the program.

1150
00:54:25,190 --> 00:54:28,010
But we'll go to that address
which we know still exists

1151
00:54:28,010 --> 00:54:29,260
and see what's there.

1152
00:54:29,260 --> 00:54:35,640

1153
00:54:35,640 --> 00:54:37,110
>> So it didn't seg fault.

1154
00:54:37,110 --> 00:54:38,970
It just didn't give us anything.

1155
00:54:38,970 --> 00:54:43,350
It might have actually given us
something, we just can't see it.

1156
00:54:43,350 --> 00:54:45,110
And that goes back to this idea--

1157
00:54:45,110 --> 00:54:47,270
and we're not going to get too much into
this, because that's beyond the

1158
00:54:47,270 --> 00:54:48,460
scope of this course.

1159
00:54:48,460 --> 00:54:51,260
But we talked about right here, if we
went beyond the bounds of the array by

1160
00:54:51,260 --> 00:54:54,890
1, we might not get in trouble.

1161
00:54:54,890 --> 00:54:58,550
>> Sometimes, when you just go off by 1,
you're doing something wrong, and you

1162
00:54:58,550 --> 00:54:59,220
could get in trouble.

1163
00:54:59,220 --> 00:55:00,820
But you don't always get in trouble.

1164
00:55:00,820 --> 00:55:05,170
It depends how much of a bad thing you
do, you're going to get in trouble.

1165
00:55:05,170 --> 00:55:07,790
Which isn't to say, be sloppy
with your code.

1166
00:55:07,790 --> 00:55:12,080
But it is to say, the program won't
always quit, even if you go somewhere

1167
00:55:12,080 --> 00:55:14,130
you're not supposed to go.

1168
00:55:14,130 --> 00:55:18,170
>> A good example of that is, a lot of
people in their problem set 3, which

1169
00:55:18,170 --> 00:55:22,350
was 15, did not check the
bounds of the board.

1170
00:55:22,350 --> 00:55:25,860
So you looked to the left, looked to the
right, looked to the top, looked

1171
00:55:25,860 --> 00:55:27,000
to the bottom.

1172
00:55:27,000 --> 00:55:31,540
But you didn't check to see if the top
was actually going to be on the board.

1173
00:55:31,540 --> 00:55:35,220
And a lot of people who did that and
turned that in, their program worked

1174
00:55:35,220 --> 00:55:38,960
perfectly, because where that board was
stored in memory, if you went one

1175
00:55:38,960 --> 00:55:42,300
above it or checked that memory
address, there wasn't anything

1176
00:55:42,300 --> 00:55:44,870
particularly horrible about that,
so your program wasn't

1177
00:55:44,870 --> 00:55:45,970
going to yell at you.

1178
00:55:45,970 --> 00:55:48,870
>> But we would still take off points if
you didn't check that, because you

1179
00:55:48,870 --> 00:55:50,850
were doing something you weren't
supposed to do, and you could have

1180
00:55:50,850 --> 00:55:51,860
gotten in trouble.

1181
00:55:51,860 --> 00:55:54,040
Odds are, though, you probably didn't.

1182
00:55:54,040 --> 00:55:57,790
So this is to show that, yes,
we can still go to it.

1183
00:55:57,790 --> 00:55:59,010
And we're not getting in
trouble in this case.

1184
00:55:59,010 --> 00:56:04,000
If we tried to do read the
next 100 characters, we'd

1185
00:56:04,000 --> 00:56:06,000
probably get in trouble.

1186
00:56:06,000 --> 00:56:09,400
And you can code reading the next 100
characters if you want by doing some

1187
00:56:09,400 --> 00:56:10,110
sort of for loop.

1188
00:56:10,110 --> 00:56:10,850
Yeah.

1189
00:56:10,850 --> 00:56:16,250
>> STUDENT: Since we were assigned that
space an actual value, we wouldn't

1190
00:56:16,250 --> 00:56:17,050
actually be able to see anything.

1191
00:56:17,050 --> 00:56:21,740
Should we try it with setting that
equal to like c or something?

1192
00:56:21,740 --> 00:56:22,640
>> JASON HIRSCHHORN: Great question.

1193
00:56:22,640 --> 00:56:25,340
How do I set that value--

1194
00:56:25,340 --> 00:56:28,980
what line of code do I write on line
seven to do what you said?

1195
00:56:28,980 --> 00:56:34,040
>> STUDENT: Star ptr equals single
quote c end single quote.

1196
00:56:34,040 --> 00:56:36,970
>> JASON HIRSCHHORN: So that's putting
a character, c, at that location,

1197
00:56:36,970 --> 00:56:40,200
because again, that star
means go to there.

1198
00:56:40,200 --> 00:56:43,320
And when used on the left hand side of
an assignment operator, that equals

1199
00:56:43,320 --> 00:56:47,270
sign, we're not going to get that
value so much as set that value.

1200
00:56:47,270 --> 00:56:48,520
Now let's see what happens.

1201
00:56:48,520 --> 00:56:54,700

1202
00:56:54,700 --> 00:56:56,770
>> We put something there
and it was there.

1203
00:56:56,770 --> 00:56:58,000
We called free.

1204
00:56:58,000 --> 00:57:00,100
Some stuff probably happened
on the heap.

1205
00:57:00,100 --> 00:57:01,890
So it's not there anymore.

1206
00:57:01,890 --> 00:57:07,440
But again, we're not getting
in trouble for going there.

1207
00:57:07,440 --> 00:57:10,260
>> I'm doing this out in code to illustrate
that a lot of these

1208
00:57:10,260 --> 00:57:12,410
questions that you have, they're
really interesting

1209
00:57:12,410 --> 00:57:13,650
answers a lot of time.

1210
00:57:13,650 --> 00:57:15,260
And they're really good questions.

1211
00:57:15,260 --> 00:57:19,010
And you can figure them out on
your own if, for example,

1212
00:57:19,010 --> 00:57:19,990
we're not in section.

1213
00:57:19,990 --> 00:57:20,940
Yeah.

1214
00:57:20,940 --> 00:57:24,430
>> STUDENT: Because you're not sending the
pointer anywhere, do you need to

1215
00:57:24,430 --> 00:57:26,530
use malloc?

1216
00:57:26,530 --> 00:57:28,400
>> JASON HIRSCHHORN: So this goes back
to your initial question.

1217
00:57:28,400 --> 00:57:28,620
[?  ?]

1218
00:57:28,620 --> 00:57:29,980
Is it just a local variable?

1219
00:57:29,980 --> 00:57:32,280
Malloc here is not that compelling.

1220
00:57:32,280 --> 00:57:35,260
The use of malloc here is not
that compelling because it's

1221
00:57:35,260 --> 00:57:36,500
just a local variable.

1222
00:57:36,500 --> 00:57:40,970
>> STUDENT: So could you do char
star ptr equals hello?

1223
00:57:40,970 --> 00:57:41,400
>> JASON HIRSCHHORN: Oh.

1224
00:57:41,400 --> 00:57:43,300
So we're going to now get back
to your initial question.

1225
00:57:43,300 --> 00:57:46,885
I think you weren't satisfied
with my answer.

1226
00:57:46,885 --> 00:57:48,220
OK?

1227
00:57:48,220 --> 00:57:49,226
Like that?

1228
00:57:49,226 --> 00:57:49,682
>> STUDENT: Yeah.

1229
00:57:49,682 --> 00:57:50,932
Wait.

1230
00:57:50,932 --> 00:57:54,090

1231
00:57:54,090 --> 00:57:57,850
>> JASON HIRSCHHORN: And where
do you want to print out?

1232
00:57:57,850 --> 00:58:00,026
So we'll print out a string like that?

1233
00:58:00,026 --> 00:58:06,380

1234
00:58:06,380 --> 00:58:07,630
>> STUDENT: Interesting.

1235
00:58:07,630 --> 00:58:09,900

1236
00:58:09,900 --> 00:58:14,285
>> JASON HIRSCHHORN: So this says this
argument has the type of a character.

1237
00:58:14,285 --> 00:58:17,200

1238
00:58:17,200 --> 00:58:18,620
So this should be a character.

1239
00:58:18,620 --> 00:58:25,170

1240
00:58:25,170 --> 00:58:26,280
>> STUDENT: Just takes the first one.

1241
00:58:26,280 --> 00:58:28,610
>> JASON HIRSCHHORN: So this
is what I said before.

1242
00:58:28,610 --> 00:58:34,240
Like I said, it's not storing the
string inside variable pointer.

1243
00:58:34,240 --> 00:58:35,120
It's storing--

1244
00:58:35,120 --> 00:58:36,350
>> STUDENT: The first value
of the string.

1245
00:58:36,350 --> 00:58:40,810
>> JASON HIRSCHHORN: The address of
the first value of the string.

1246
00:58:40,810 --> 00:58:46,940
If we were to print out this, we're
getting the value inside pointer.

1247
00:58:46,940 --> 00:58:51,005
And we'll see it is, indeed,
a memory address.

1248
00:58:51,005 --> 00:58:53,595

1249
00:58:53,595 --> 00:58:56,440
>> Does that make sense?

1250
00:58:56,440 --> 00:58:56,940
Sorry.

1251
00:58:56,940 --> 00:58:58,996
Wait, does that answer your
question, though?

1252
00:58:58,996 --> 00:58:59,790
>> STUDENT: Yeah.

1253
00:58:59,790 --> 00:59:05,830
>> JASON HIRSCHHORN: This line of code is
creating a string and then another

1254
00:59:05,830 --> 00:59:09,115
variable pointer that's pointing
to that string, that array.

1255
00:59:09,115 --> 00:59:14,320

1256
00:59:14,320 --> 00:59:14,980
Yeah.

1257
00:59:14,980 --> 00:59:19,200
>> STUDENT: So if we went one memory
address further, would we get the h?

1258
00:59:19,200 --> 00:59:21,990

1259
00:59:21,990 --> 00:59:23,150
Has it been stored as a string?

1260
00:59:23,150 --> 00:59:24,400
>> JASON HIRSCHHORN: Like, we did--

1261
00:59:24,400 --> 00:59:28,540

1262
00:59:28,540 --> 00:59:30,790
so this is valuable to do.

1263
00:59:30,790 --> 00:59:33,780
This is point arithmetic, which you guys
have seen before and should be

1264
00:59:33,780 --> 00:59:35,550
relatively comfortable with.

1265
00:59:35,550 --> 00:59:36,905
This is akin to writing--

1266
00:59:36,905 --> 00:59:41,980

1267
00:59:41,980 --> 00:59:46,350
if we were to write this line of code,
we've seen array notation before.

1268
00:59:46,350 --> 00:59:55,900
This should give us the second
value in this array, h.

1269
00:59:55,900 --> 01:00:05,010
>> If we did this, this should also give
us the second value in that array.

1270
01:00:05,010 --> 01:00:08,320
Because it is going not to the memory
address of the first thing, but the

1271
01:00:08,320 --> 01:00:10,530
memory address of the thing one over.

1272
01:00:10,530 --> 01:00:14,360
And then the star operator dereferences
that pointer.

1273
01:00:14,360 --> 01:00:16,940
And again, let's see.

1274
01:00:16,940 --> 01:00:18,664
We get h again.

1275
01:00:18,664 --> 01:00:20,980
>> STUDENT: What exactly does
dereference mean?

1276
01:00:20,980 --> 01:00:23,650
>> JASON HIRSCHHORN: Dereference
is a fancy word for go to.

1277
01:00:23,650 --> 01:00:26,390
Go to that and get what's there
is to dereference a pointer.

1278
01:00:26,390 --> 01:00:28,240
It's just a fancy word for that.

1279
01:00:28,240 --> 01:00:29,986
>> STUDENT: If we wanted to print
the whole string, could we

1280
01:00:29,986 --> 01:00:31,930
do ampersand pointer?

1281
01:00:31,930 --> 01:00:33,490
>> JASON HIRSCHHORN: OK, we are
going to pause here.

1282
01:00:33,490 --> 01:00:35,480
We are going to end here.

1283
01:00:35,480 --> 01:00:41,760
Ampersand gives you the address of a
location, so when you do ampersand of

1284
01:00:41,760 --> 01:00:44,080
a variable, it gives you the address
where that variable is stored.

1285
01:00:44,080 --> 01:00:48,580
Ampersand pointer will give you the
address of ptr where ptr is in memory.

1286
01:00:48,580 --> 01:00:50,140
>> We're not going to go on
with this example.

1287
01:00:50,140 --> 01:00:52,640
You can figure out these
things on your own.

1288
01:00:52,640 --> 01:00:55,740
But again, this might even be verging a
bit beyond what you need to know for

1289
01:00:55,740 --> 01:00:58,000
the scope of this mid-term--

1290
01:00:58,000 --> 01:00:59,070
or this quiz, rather.

1291
01:00:59,070 --> 01:01:00,270
Sorry.

1292
01:01:00,270 --> 01:01:03,770
>> We are going to move on, because I would
like to do one coding problem

1293
01:01:03,770 --> 01:01:05,100
before time is up.

1294
01:01:05,100 --> 01:01:09,340
And we are going to code what I think
is the most compelling of these

1295
01:01:09,340 --> 01:01:11,020
examples, atoi.

1296
01:01:11,020 --> 01:01:14,520
So this was a question on
a quiz two years ago.

1297
01:01:14,520 --> 01:01:17,810
And I have it on the board here.

1298
01:01:17,810 --> 01:01:20,680
>> People were asked on the quiz--

1299
01:01:20,680 --> 01:01:23,640
they were given a little more tesxt in
the question, but I eliminated the

1300
01:01:23,640 --> 01:01:26,640
text because it was unnecessary
for our purposes now.

1301
01:01:26,640 --> 01:01:29,180
It was just some background
on what atoi did.

1302
01:01:29,180 --> 01:01:31,425
But you all know and are very
familiar with atoi.

1303
01:01:31,425 --> 01:01:35,620
>> I suggest you code this
on a sheet of paper.

1304
01:01:35,620 --> 01:01:39,310
I also suggest you use the strategy
that we've gone over

1305
01:01:39,310 --> 01:01:41,040
a lot in our section.

1306
01:01:41,040 --> 01:01:44,130
First, make sure you understand
what atoi's doing.

1307
01:01:44,130 --> 01:01:47,580
Draw a picture or come up with some
mental image of it in your head.

1308
01:01:47,580 --> 01:01:51,120
Next, write out pseudocode for this.

1309
01:01:51,120 --> 01:01:53,120
On the quiz, if all you get is
pseudocode, at least you

1310
01:01:53,120 --> 01:01:54,550
put something down.

1311
01:01:54,550 --> 01:02:00,070
And then map that pseudocode onto
C. If you have a check in your

1312
01:02:00,070 --> 01:02:03,760
pseudocode, like check if something
is 1, that maps onto an if

1313
01:02:03,760 --> 01:02:05,750
condition and so forth.

1314
01:02:05,750 --> 01:02:07,850
And finally, code the program in C.

1315
01:02:07,850 --> 01:02:15,000
>> So go back to atoi and take five minutes
to code this on a sheet of

1316
01:02:15,000 --> 01:02:19,480
paper, which is probably about the
amount of time you would take on a

1317
01:02:19,480 --> 01:02:21,260
quiz to code atoi.

1318
01:02:21,260 --> 01:02:27,060
Five to 15 minutes, five to 12, five to
10 minutes, is about the amount of

1319
01:02:27,060 --> 01:02:30,150
time you'd spend on this
question in the quiz.

1320
01:02:30,150 --> 01:02:31,670
So take five minutes now, please.

1321
01:02:31,670 --> 01:02:35,957
And if you have any questions, raise
your hand and I'll come around.

1322
01:02:35,957 --> 01:06:39,570

1323
01:06:39,570 --> 01:06:41,066
>> [SIDE CONVERSATIONS]

1324
01:06:41,066 --> 01:08:35,279

1325
01:08:35,279 --> 01:08:37,580
>> JASON HIRSCHHORN: OK, so
that was five minutes.

1326
01:08:37,580 --> 01:08:39,880
That was probably about the amount of
time you'd spend on that on a quiz,

1327
01:08:39,880 --> 01:08:42,120
maybe the low end of that time.

1328
01:08:42,120 --> 01:08:44,010
We'll recap in a bit.

1329
01:08:44,010 --> 01:08:45,740
Let us start coding this.

1330
01:08:45,740 --> 01:08:49,479
And if we don't get all the way through,
the answers to this and this

1331
01:08:49,479 --> 01:08:54,189
quiz question are available, again,
Fall 2011 is when this question

1332
01:08:54,189 --> 01:08:54,913
appeared on the quiz.

1333
01:08:54,913 --> 01:08:57,830
>> And it was worth eight points
on the quiz then.

1334
01:08:57,830 --> 01:09:01,140
Eight points is on the high end of the
amount of points something is worth.

1335
01:09:01,140 --> 01:09:04,790
Most questions are in the range
of one to six points.

1336
01:09:04,790 --> 01:09:08,500
So this is a more challenging
question, for sure.

1337
01:09:08,500 --> 01:09:09,750
Can anybody get me started?

1338
01:09:09,750 --> 01:09:13,260

1339
01:09:13,260 --> 01:09:15,380
>> Generally, what are we going
to want to do with this

1340
01:09:15,380 --> 01:09:17,550
function atoi, logically?

1341
01:09:17,550 --> 01:09:19,569
What do we want to do?

1342
01:09:19,569 --> 01:09:22,279
So we're going to write
some pseudocode.

1343
01:09:22,279 --> 01:09:24,090
>> STUDENT: Convert characters
into integers.

1344
01:09:24,090 --> 01:09:26,700
>> JASON HIRSCHHORN: Convert characters
into integers.

1345
01:09:26,700 --> 01:09:27,479
OK.

1346
01:09:27,479 --> 01:09:30,870
So how many characters are we
going to need to go through?

1347
01:09:30,870 --> 01:09:32,295
>> STUDENT: All of them.

1348
01:09:32,295 --> 01:09:34,100
>> STUDENT: All the characters
in the string.

1349
01:09:34,100 --> 01:09:35,540
>> JASON HIRSCHHORN: All of the
characters in the string.

1350
01:09:35,540 --> 01:09:42,180
So if we wanted to go through every
character in a string, what is a thing

1351
01:09:42,180 --> 01:09:44,560
in C we've seen that has allowed
us to go through every

1352
01:09:44,560 --> 01:09:45,939
character in a string?

1353
01:09:45,939 --> 01:09:46,819
>> STUDENTS: A for loop.

1354
01:09:46,819 --> 01:09:48,069
>> JASON HIRSCHHORN: A for loop.

1355
01:09:48,069 --> 01:09:52,020

1356
01:09:52,020 --> 01:09:55,330
So we're going to loop through
every character in s.

1357
01:09:55,330 --> 01:10:00,940
>> Then what are we going to want to do
when we get a specific character?

1358
01:10:00,940 --> 01:10:02,480
Say we're getting passed a 90.

1359
01:10:02,480 --> 01:10:03,460
We get the 9.

1360
01:10:03,460 --> 01:10:04,240
It's a character.

1361
01:10:04,240 --> 01:10:07,440
What do we want to do with
that character 9?

1362
01:10:07,440 --> 01:10:10,082
>> STUDENT: Subtract it from character 0?

1363
01:10:10,082 --> 01:10:11,860
>> STUDENT: Add 0?

1364
01:10:11,860 --> 01:10:13,350
>> JASON HIRSCHHORN: Subtract
it from character 0?

1365
01:10:13,350 --> 01:10:13,800
>> STUDENT: Yeah.

1366
01:10:13,800 --> 01:10:15,573
>> JASON HIRSCHHORN: Why do
you want to do that?

1367
01:10:15,573 --> 01:10:16,560
>> STUDENT: [INAUDIBLE]

1368
01:10:16,560 --> 01:10:17,010
value.

1369
01:10:17,010 --> 01:10:18,380
Its int value.

1370
01:10:18,380 --> 01:10:21,580
>> JASON HIRSCHHORN: OK, so we take the
character 9, subtract it from

1371
01:10:21,580 --> 01:10:25,820
character 0 to get an
actual integer 9.

1372
01:10:25,820 --> 01:10:27,070
Sweet.

1373
01:10:27,070 --> 01:10:31,255

1374
01:10:31,255 --> 01:10:37,000
And how do you know that character
9 minus 0 character is 9?

1375
01:10:37,000 --> 01:10:39,222
What chart did you look at?

1376
01:10:39,222 --> 01:10:43,130
>> STUDENT: There are logically nine
places between 9 and 0.

1377
01:10:43,130 --> 01:10:44,620
Or you could look at the ASCII table.

1378
01:10:44,620 --> 01:10:45,120
>> JASON HIRSCHHORN: ASCII table.

1379
01:10:45,120 --> 01:10:46,490
But yes, you're correct as well.

1380
01:10:46,490 --> 01:10:47,780
So we subtract 0.

1381
01:10:47,780 --> 01:10:49,010
So now we have the integer 9.

1382
01:10:49,010 --> 01:10:49,970
And what do we want to do with that?

1383
01:10:49,970 --> 01:10:54,970
If we have 90, it's the first integer
we have, what we want to do?

1384
01:10:54,970 --> 01:10:58,180
>> STUDENT: I'd put in a temporary integer
array, then do math to it

1385
01:10:58,180 --> 01:11:02,088
later to make it into an end.

1386
01:11:02,088 --> 01:11:03,020
>> JASON HIRSCHHORN: OK.

1387
01:11:03,020 --> 01:11:06,990
>> STUDENT: You can start at the end of
the array and then move forward so

1388
01:11:06,990 --> 01:11:10,350
that every time you move forward,
you multiply it by 10.

1389
01:11:10,350 --> 01:11:10,830
>> JASON HIRSCHHORN: OK.

1390
01:11:10,830 --> 01:11:12,250
That sounds like a pretty
compelling idea.

1391
01:11:12,250 --> 01:11:16,040
We can start at the end of our array,
and we can use strleng.

1392
01:11:16,040 --> 01:11:17,030
We can use strleng in here.

1393
01:11:17,030 --> 01:11:18,870
We'll get the length of our string.

1394
01:11:18,870 --> 01:11:20,100
We start at the end.

1395
01:11:20,100 --> 01:11:29,170
And + the first one, we just take that
integer, and maybe we create like a

1396
01:11:29,170 --> 01:11:32,270
new integer variable up top where
we're storing everything.

1397
01:11:32,270 --> 01:11:37,340
So we loop through every char in s from
back to front, we subtract 0, and

1398
01:11:37,340 --> 01:11:42,790
then we take it, and depending on
where it is, we multiply it

1399
01:11:42,790 --> 01:11:45,860
by a power of 10.

1400
01:11:45,860 --> 01:11:50,644
Because the first one, what do we
multiply the rightmost character by?

1401
01:11:50,644 --> 01:11:51,440
>> STUDENT: 10 to the 0.

1402
01:11:51,440 --> 01:11:53,170
>> JASON HIRSCHHORN: 10 to the 0.

1403
01:11:53,170 --> 01:11:56,010
What do we multiply the second
rightmost character by?

1404
01:11:56,010 --> 01:11:57,450
>> STUDENT: [INAUDIBLE].

1405
01:11:57,450 --> 01:11:57,960
>> JASON HIRSCHHORN: What?

1406
01:11:57,960 --> 01:11:59,150
>> STUDENT: 10 to the 1.

1407
01:11:59,150 --> 01:12:00,420
>> JASON HIRSCHHORN: 10 to the 1.

1408
01:12:00,420 --> 01:12:03,754
The third-rightmost character?

1409
01:12:03,754 --> 01:12:04,580
>> STUDENT: 10 to the 2.

1410
01:12:04,580 --> 01:12:05,350
>> JASON HIRSCHHORN: 10 to the 2.

1411
01:12:05,350 --> 01:12:07,200
>> STUDENT: Sorry, I don't understand
what we're doing here.

1412
01:12:07,200 --> 01:12:08,640
>> JASON HIRSCHHORN: OK,
let's go back, then.

1413
01:12:08,640 --> 01:12:12,500
So we're going to get
passed in a string.

1414
01:12:12,500 --> 01:12:14,470
Because we're writing atoi.

1415
01:12:14,470 --> 01:12:15,260
So we get passed in a string.

1416
01:12:15,260 --> 01:12:17,640
Say we're getting passed
in the string 90.

1417
01:12:17,640 --> 01:12:19,930
>> The first thing we're going to do is set
a new integer variable that we're

1418
01:12:19,930 --> 01:12:22,150
just going to create
as our new integer.

1419
01:12:22,150 --> 01:12:24,630
That's what we're going
to return at the end.

1420
01:12:24,630 --> 01:12:30,110
We need to go through every character in
the string because we've determined

1421
01:12:30,110 --> 01:12:34,430
that we need to touch each one and
then add it to our new integer.

1422
01:12:34,430 --> 01:12:36,330
>> But we can't just add it as a number.

1423
01:12:36,330 --> 01:12:38,270
We can't just take 9 and
add 9 to our integer.

1424
01:12:38,270 --> 01:12:40,560
It depends on what place
it is in the string.

1425
01:12:40,560 --> 01:12:42,960
We're going to need to multiply
it by a power of 10.

1426
01:12:42,960 --> 01:12:45,580
Because that's how base 10 works.

1427
01:12:45,580 --> 01:12:49,050
>> So we're going to get the actual
character, or the actual integer

1428
01:12:49,050 --> 01:12:53,860
number, by subtracting character 0
from character 9 like we did with

1429
01:12:53,860 --> 01:12:57,560
subtracting character capital A from
whatever character we had in one of

1430
01:12:57,560 --> 01:12:58,120
those problems.

1431
01:12:58,120 --> 01:13:04,190
So we'll actually get a number from 0 to
9 saved as a real number, and we'll

1432
01:13:04,190 --> 01:13:07,590
multiply it by a power of 10 depending
on where we are in the string.

1433
01:13:07,590 --> 01:13:19,430

1434
01:13:19,430 --> 01:13:22,575
And then we're going to add it back
into our new integer variable.

1435
01:13:22,575 --> 01:13:32,840

1436
01:13:32,840 --> 01:13:37,890
>> So what this would look like would
be-- we'll draw over here.

1437
01:13:37,890 --> 01:13:40,086
If we get passed in the string 90--

1438
01:13:40,086 --> 01:13:41,336
>> STUDENT: [INAUDIBLE].

1439
01:13:41,336 --> 01:13:43,190

1440
01:13:43,190 --> 01:13:45,540
>> JASON HIRSCHHORN: But
atoi takes a string.

1441
01:13:45,540 --> 01:13:46,350
So we're going to go through
the holding.

1442
01:13:46,350 --> 01:13:49,900
We'll get passed in 90.

1443
01:13:49,900 --> 01:13:51,540
We go from the back to the front.

1444
01:13:51,540 --> 01:13:53,920
We take the 0.

1445
01:13:53,920 --> 01:13:55,080
>> STUDENT: I'm sorry.

1446
01:13:55,080 --> 01:13:55,880
Maybe this is stupid.

1447
01:13:55,880 --> 01:13:59,440
If we're getting passed in a string,
why is 90 what we're

1448
01:13:59,440 --> 01:14:00,260
getting passed in?

1449
01:14:00,260 --> 01:14:03,160
Because 90 is an integer.

1450
01:14:03,160 --> 01:14:06,820
>> JASON HIRSCHHORN: Because atoi takes a
string and turns it into the integer

1451
01:14:06,820 --> 01:14:08,320
representation of that string.

1452
01:14:08,320 --> 01:14:13,650
But the string 90 is not the integer
90 or the number 90.

1453
01:14:13,650 --> 01:14:17,920
The string 90 is an array of two, or
three characters, rather, the 9

1454
01:14:17,920 --> 01:14:22,740
character, the 0 character, and
the backslash 0 character.

1455
01:14:22,740 --> 01:14:26,260
>> And we're writing atoi because, for
example, when you take the command

1456
01:14:26,260 --> 01:14:30,230
line argument, and it's saved in
argv, it's saved as a string.

1457
01:14:30,230 --> 01:14:32,940
But if you want to treat it as a number,
you need to convert it to an

1458
01:14:32,940 --> 01:14:34,700
actual integer.

1459
01:14:34,700 --> 01:14:37,210
Which we did one of our problem sets.

1460
01:14:37,210 --> 01:14:38,800
Which we did in a number
of our problem sets.

1461
01:14:38,800 --> 01:14:41,690
Everyone that took an integer
as a command line argument.

1462
01:14:41,690 --> 01:14:46,490
So that's why our atoi function
takes a string.

1463
01:14:46,490 --> 01:14:51,910
>> So again, in our example here, we're
going to take the last one.

1464
01:14:51,910 --> 01:14:55,050
We're going to subtract the character
0 from it, because the characters 0

1465
01:14:55,050 --> 01:14:58,810
subtracted by the character 0 gives you
the actual number 0, according to

1466
01:14:58,810 --> 01:15:00,950
the ASCII math that we do.

1467
01:15:00,950 --> 01:15:04,870
>> Because characters are represented as
different than their actual-- the

1468
01:15:04,870 --> 01:15:08,830
character a, for example,
lowercase a is 97.

1469
01:15:08,830 --> 01:15:10,260
It's not-- oops!

1470
01:15:10,260 --> 01:15:13,290
It's not whatever you would expect
it to be, 0, for example.

1471
01:15:13,290 --> 01:15:16,200
So you have to subtract the
character a to get 0.

1472
01:15:16,200 --> 01:15:18,950
>> So we're going to do that here
to get the actual number.

1473
01:15:18,950 --> 01:15:22,560
And then we are going to multiply it by
a power of 10 depending on where it

1474
01:15:22,560 --> 01:15:27,030
is in the string, and then take that
and add it to our place holder

1475
01:15:27,030 --> 01:15:32,520
variable so we can come up with
our final new integer.

1476
01:15:32,520 --> 01:15:35,080
Does that makes sense to everyone?

1477
01:15:35,080 --> 01:15:37,730
>> So we're not going to code this
right now, because we're

1478
01:15:37,730 --> 01:15:38,830
getting short on time.

1479
01:15:38,830 --> 01:15:40,860
I apologize for the timing of that.

1480
01:15:40,860 --> 01:15:44,620
But this is what, hopefully, you would
be able to do on the quiz-- at the

1481
01:15:44,620 --> 01:15:47,710
very least, get this pseudocode
written out.

1482
01:15:47,710 --> 01:15:50,840
>> And then, if we were to write the
pseudocode, actually, we could do this

1483
01:15:50,840 --> 01:15:51,490
pretty quickly.

1484
01:15:51,490 --> 01:15:55,230
Each line of comments we we wrote
here translates to about

1485
01:15:55,230 --> 01:15:56,970
one line of C code.

1486
01:15:56,970 --> 01:16:01,780
Declaring a new variable, writing
a loop, some subtraction, some

1487
01:16:01,780 --> 01:16:07,070
multiplication, and some assignment.

1488
01:16:07,070 --> 01:16:09,020
We'd probably also want to
write a return line.

1489
01:16:09,020 --> 01:16:12,040
We might also want to put
some checks in here.

1490
01:16:12,040 --> 01:16:12,655
Yeah.

1491
01:16:12,655 --> 01:16:15,720
>> STUDENT: So can we treat
s as the actual string?

1492
01:16:15,720 --> 01:16:18,730
Because I know it's just an address.

1493
01:16:18,730 --> 01:16:22,090
Like, how would you get the length of
the string being passed through?

1494
01:16:22,090 --> 01:16:25,310
>> JASON HIRSCHHORN: So how did
the length of a string?

1495
01:16:25,310 --> 01:16:25,830
Strlen.

1496
01:16:25,830 --> 01:16:26,660
>> STUDENT: strlen, yeah.

1497
01:16:26,660 --> 01:16:30,550
But can you put s as the
argument for that?

1498
01:16:30,550 --> 01:16:34,620
>> JASON HIRSCHHORN: So strlen
takes a char star.

1499
01:16:34,620 --> 01:16:38,090
And it follows that char star, and it
keeps counting until it gets to a

1500
01:16:38,090 --> 01:16:41,865
backslash 0. strlen was actually
one of the other programs we

1501
01:16:41,865 --> 01:16:42,850
were going to code.

1502
01:16:42,850 --> 01:16:44,560
That's another good one to code.

1503
01:16:44,560 --> 01:16:47,270
That one's a bit easier, because if
you're going to think about that

1504
01:16:47,270 --> 01:16:47,830
conceptually--

1505
01:16:47,830 --> 01:16:51,620
I just said it out loud-- strlen follows
a pointer and keeps going and

1506
01:16:51,620 --> 01:16:54,210
counting and keeping track until
you reach a backslash 0.

1507
01:16:54,210 --> 01:16:56,530
>> STUDENT: OK, got it.

1508
01:16:56,530 --> 01:17:00,200
>> JASON HIRSCHHORN: So best of
luck on quiz 0 tomorrow.

1509
01:17:00,200 --> 01:17:03,170
If you have any questions, I'll
be outside after this.

1510
01:17:03,170 --> 01:17:05,610
Feel free to email me.

1511
01:17:05,610 --> 01:17:08,480
Reach out to your own TF if you're
not in my section, or get my

1512
01:17:08,480 --> 01:17:10,005
email if you want it.

1513
01:17:10,005 --> 01:17:13,140
>> If you want to freak out and just send
me an email, a freakout email, I'll

1514
01:17:13,140 --> 01:17:16,710
send you back, like, a smiley face,
or, like, a joke or something.

1515
01:17:16,710 --> 01:17:18,190
So feel free to do that as well.

1516
01:17:18,190 --> 01:17:20,750
Good luck again, and I'll
see you all next week.

1517
01:17:20,750 --> 01:17:23,435