1
00:00:00,000 --> 00:00:09,572

2
00:00:09,572 --> 00:00:12,030
ROB BOWDEN: Hi, I'm Rob Bowden,
and let's talk about quiz0.

3
00:00:12,030 --> 00:00:13,280

4
00:00:13,280 --> 00:00:14,545
>> So, first question.

5
00:00:14,545 --> 00:00:17,750
This is the question where
you needed to code the number

6
00:00:17,750 --> 00:00:21,270
127 in the binary bulbs.

7
00:00:21,270 --> 00:00:23,550
If you wanted, you could
do the regular conversion

8
00:00:23,550 --> 00:00:25,950
from bi-- or, from decimal to binary.

9
00:00:25,950 --> 00:00:28,300
But that's probably going
to take a lot of time.

10
00:00:28,300 --> 00:00:31,750
I mean, you could figure out that,
OK, 1 is in there, 2 is in there,

11
00:00:31,750 --> 00:00:33,650
4 is in there, 8 is in there.

12
00:00:33,650 --> 00:00:39,280
Easier way, 127 is 128 minus one.

13
00:00:39,280 --> 00:00:42,013
That leftmost light bulb is the 128-bit.

14
00:00:42,013 --> 00:00:43,490

15
00:00:43,490 --> 00:00:47,860
So 127 is really just all
of the other light bulbs,

16
00:00:47,860 --> 00:00:51,420
since that's the leftmost
light bulb minus 1.

17
00:00:51,420 --> 00:00:52,800
That's it for that question.

18
00:00:52,800 --> 00:00:54,060
>> Question one.

19
00:00:54,060 --> 00:00:56,710
So with 3 bits you can
represent 8 distinct values.

20
00:00:56,710 --> 00:01:01,000
Why, then, is 7 the largest non-negative
decimal integer you can represent?

21
00:01:01,000 --> 00:01:04,050
Well, if we can only
represent 8 distinct values,

22
00:01:04,050 --> 00:01:07,430
then what we're going to be
representing is 0 through 7.

23
00:01:07,430 --> 00:01:08,745
0 takes up one of the values.

24
00:01:08,745 --> 00:01:09,980

25
00:01:09,980 --> 00:01:11,190
>> Question two.

26
00:01:11,190 --> 00:01:14,610
With n bits, how many distinct
values can you represent?

27
00:01:14,610 --> 00:01:19,080
So, with n bits, you have 2
possible values for each bit.

28
00:01:19,080 --> 00:01:22,300
So we have 2 possible values for
the first bit, 2 possible values

29
00:01:22,300 --> 00:01:24,450
for the second, 2
possible for the third.

30
00:01:24,450 --> 00:01:28,730
And so that's 2 times 2 times 2, and
ultimately the answer is 2 to the n.

31
00:01:28,730 --> 00:01:30,010

32
00:01:30,010 --> 00:01:31,100
>> Question three.

33
00:01:31,100 --> 00:01:33,450
What's 0x50 in binary?

34
00:01:33,450 --> 00:01:39,490
So remember that hexadecimal has a very
straightforward conversion to binary.

35
00:01:39,490 --> 00:01:43,180
So here, we just need to look at
the 5 and the 0 independently.

36
00:01:43,180 --> 00:01:45,110
So what's 5 in binary?

37
00:01:45,110 --> 00:01:48,400
0101, that's the 1 bit and the 4 bit.

38
00:01:48,400 --> 00:01:49,900
What's 0 in binary?

39
00:01:49,900 --> 00:01:50,520
Not tricky.

40
00:01:50,520 --> 00:01:52,180
0000.

41
00:01:52,180 --> 00:01:54,970
So just put them together, and
that's the full number in binary.

42
00:01:54,970 --> 00:01:57,640
01010000.

43
00:01:57,640 --> 00:02:00,439
And if you wanted you could
take off that leftmost zero.

44
00:02:00,439 --> 00:02:01,105
It's irrelevant.

45
00:02:01,105 --> 00:02:02,920

46
00:02:02,920 --> 00:02:05,733
>> So then alternatively,
what is 0x50 in decimal?

47
00:02:05,733 --> 00:02:08,649
If you wanted, you could-- if you're
more comfortable with the binary,

48
00:02:08,649 --> 00:02:11,340
you could take that binary answer
and convert that into decimal.

49
00:02:11,340 --> 00:02:13,870
Or we could just remember
that hexadecimal.

50
00:02:13,870 --> 00:02:21,140
So that 0 is in the 0-th place, and
the 5 is in the 16 to the first place.

51
00:02:21,140 --> 00:02:25,990
So here, we have 5 times 16 to the
first, plus 0 times 16 to the zero,

52
00:02:25,990 --> 00:02:27,520
is 80.

53
00:02:27,520 --> 00:02:29,710
And if you looked at the
title to the question,

54
00:02:29,710 --> 00:02:32,920
it was CS 80, which was kind of a
hint to the answer to this problem.

55
00:02:32,920 --> 00:02:34,460

56
00:02:34,460 --> 00:02:35,420
>> Question five.

57
00:02:35,420 --> 00:02:40,320
We have this Scratch script, which is
repeating 4 times peanut butter jelly.

58
00:02:40,320 --> 00:02:42,800
So how do we now code that in C?

59
00:02:42,800 --> 00:02:47,730
Well, we have here-- the part in bold
is the only part you had to implement.

60
00:02:47,730 --> 00:02:51,950
So we have a 4 loop that's looping 4
times, printf-ing peanut butter jelly,

61
00:02:51,950 --> 00:02:53,910
with new line as the problem asks for.

62
00:02:53,910 --> 00:02:55,250

63
00:02:55,250 --> 00:02:57,490
>> Question six, another Scratch problem.

64
00:02:57,490 --> 00:03:00,210
We see that we are in a forever loop.

65
00:03:00,210 --> 00:03:05,000
We're saying the variable i
and then incrementing i by 1.

66
00:03:05,000 --> 00:03:09,580
Now we want to do that in C. There are
multiple ways we could have done this.

67
00:03:09,580 --> 00:03:12,840
Here we happened to code the
forever loop as a while (true).

68
00:03:12,840 --> 00:03:16,600
So we declare the variable i, just
like we had variable i in Scratch.

69
00:03:16,600 --> 00:03:21,950
Declare the variable i, and forever
while (true), we say the variable i.

70
00:03:21,950 --> 00:03:25,260
So printf %i-- or you could've used %d.

71
00:03:25,260 --> 00:03:27,985
We say that variable, and
then increment it, i++.

72
00:03:27,985 --> 00:03:29,560

73
00:03:29,560 --> 00:03:30,830
>> Question seven.

74
00:03:30,830 --> 00:03:35,560
Now we want to do something very similar
to Mario dot c from problem set one.

75
00:03:35,560 --> 00:03:39,110
We want to print these hashtags,
we want to print a five

76
00:03:39,110 --> 00:03:40,700
by three rectangle of these hashes.

77
00:03:40,700 --> 00:03:41,770

78
00:03:41,770 --> 00:03:43,162
So how are we going to do that?

79
00:03:43,162 --> 00:03:45,370
Well, we give you a whole
bunch of code, and you just

80
00:03:45,370 --> 00:03:47,560
have to fill in the print grid function.

81
00:03:47,560 --> 00:03:49,540
>> So what does PrintGrid look like?

82
00:03:49,540 --> 00:03:51,480
Well you're past the
width and the height.

83
00:03:51,480 --> 00:03:53,520
So we have an outer 4
loop, that's looping

84
00:03:53,520 --> 00:03:57,650
over all of the rows of this
grid that we want to print out.

85
00:03:57,650 --> 00:04:01,250
Then we have the inter-nested 4 loop,
that's printing over each column.

86
00:04:01,250 --> 00:04:06,210
So for each row, we print for
each column, a single hash.

87
00:04:06,210 --> 00:04:10,045
Then at the end of the row we print a
single new line to go to the next row.

88
00:04:10,045 --> 00:04:11,420
And that's it for the whole grid.

89
00:04:11,420 --> 00:04:12,810

90
00:04:12,810 --> 00:04:13,675
>> Question eight.

91
00:04:13,675 --> 00:04:17,170
A function like PrintGrid is said to
have a side effect, but not a return

92
00:04:17,170 --> 00:04:17,670
value.

93
00:04:17,670 --> 00:04:19,209
Explain the distinction.

94
00:04:19,209 --> 00:04:23,080
So this relies on you remembering
what a side effect is.

95
00:04:23,080 --> 00:04:25,180
Well, a return value--
we know PrintGrid doesn't

96
00:04:25,180 --> 00:04:28,180
have return value, since
right here it says void.

97
00:04:28,180 --> 00:04:31,150
So anything that returns void
doesn't really return anything.

98
00:04:31,150 --> 00:04:32,200

99
00:04:32,200 --> 00:04:33,620
So what is the side effect?

100
00:04:33,620 --> 00:04:36,620
Well, a side effect is
anything that sort of persists

101
00:04:36,620 --> 00:04:39,500
after the function ends
that wasn't just returned,

102
00:04:39,500 --> 00:04:41,340
and it wasn't just from the inputs.

103
00:04:41,340 --> 00:04:44,970
>> So, for example, we might
change a global variable.

104
00:04:44,970 --> 00:04:46,590
That would be a side effect.

105
00:04:46,590 --> 00:04:49,000
In this particular case, a
very important side effect

106
00:04:49,000 --> 00:04:51,070
is printing to the screen.

107
00:04:51,070 --> 00:04:53,110
So that is a side effect
that PrintGrid has.

108
00:04:53,110 --> 00:04:54,980
We print these things to the screen.

109
00:04:54,980 --> 00:04:56,370
And you can think of
that as a side effect,

110
00:04:56,370 --> 00:04:58,690
since that's something that
persists after this function ends.

111
00:04:58,690 --> 00:05:01,481
That's something outside the scope
of this function that ultimately

112
00:05:01,481 --> 00:05:03,380
is being changed, the
contents of the screen.

113
00:05:03,380 --> 00:05:05,200

114
00:05:05,200 --> 00:05:05,839
>> Question nine.

115
00:05:05,839 --> 00:05:07,880
Consider the program below,
to which line numbers

116
00:05:07,880 --> 00:05:09,740
have been added for
the sake of discussion.

117
00:05:09,740 --> 00:05:13,480
So in this program we are just
calling GetString, storing it

118
00:05:13,480 --> 00:05:16,220
in this variable s, and then
printing that variable s.

119
00:05:16,220 --> 00:05:16,720
OK.

120
00:05:16,720 --> 00:05:19,090
So explain why line one is present.

121
00:05:19,090 --> 00:05:20,920
#include cs50 dot h.

122
00:05:20,920 --> 00:05:23,820
Why do we need to #include cs50 dot h?

123
00:05:23,820 --> 00:05:26,180
Well we're calling the
GetString function,

124
00:05:26,180 --> 00:05:28,840
and GetString is defined
in the cs50 library.

125
00:05:28,840 --> 00:05:31,600
So if we didn't have
#include cs50 dot h,

126
00:05:31,600 --> 00:05:35,760
we would get that implicit declaration
of the GetString function error

127
00:05:35,760 --> 00:05:36,840
from the compiler.

128
00:05:36,840 --> 00:05:40,110
So we need to include the library--
we need to include the header file,

129
00:05:40,110 --> 00:05:42,870
or else the compiler won't
recognize that GetString exists.

130
00:05:42,870 --> 00:05:44,380

131
00:05:44,380 --> 00:05:46,140
>> Explain why line two is present.

132
00:05:46,140 --> 00:05:47,890
So standard io dot h.

133
00:05:47,890 --> 00:05:50,430
It's exactly the same
as the previous problem,

134
00:05:50,430 --> 00:05:53,310
except instead of dealing with
GetString, we're talking about printf.

135
00:05:53,310 --> 00:05:56,654
So if we didn't say we need
to include standard io dot h,

136
00:05:56,654 --> 00:05:58,820
then we wouldn't be able
to use the printf function,

137
00:05:58,820 --> 00:06:00,653
because the compiler
wouldn't know about it.

138
00:06:00,653 --> 00:06:01,750

139
00:06:01,750 --> 00:06:05,260
>> Why-- what is the significance
of void in line four?

140
00:06:05,260 --> 00:06:08,010
So here we have int main (void).

141
00:06:08,010 --> 00:06:10,600
That's just saying that we
aren't getting any command line

142
00:06:10,600 --> 00:06:12,280
arguments to main.

143
00:06:12,280 --> 00:06:17,390
Remember that we could say int
main int argc string argv brackets.

144
00:06:17,390 --> 00:06:20,400
So here we just say void to say we
are ignoring command line arguments.

145
00:06:20,400 --> 00:06:21,840

146
00:06:21,840 --> 00:06:25,225
>> Explain, with respect to memory, exactly
what GetString in line six returns.

147
00:06:25,225 --> 00:06:27,040

148
00:06:27,040 --> 00:06:31,640
GetString is returning a block of
memory, an array of characters.

149
00:06:31,640 --> 00:06:34,870
It's really returning a
pointer to the first character.

150
00:06:34,870 --> 00:06:37,170
Remember that a string is a char star.

151
00:06:37,170 --> 00:06:41,360
So s is a pointer to the first
character in whatever the string is

152
00:06:41,360 --> 00:06:43,510
that the user entered at the keyboard.

153
00:06:43,510 --> 00:06:47,070
And that memory happens to be malloced,
so that memory is in the heap.

154
00:06:47,070 --> 00:06:49,080

155
00:06:49,080 --> 00:06:50,450
>> Question 13.

156
00:06:50,450 --> 00:06:51,960
Consider the program below.

157
00:06:51,960 --> 00:06:55,579
So all this program is doing
is printf-ing 1 divided by 10.

158
00:06:55,579 --> 00:06:57,370
So when compiled and
executed, this program

159
00:06:57,370 --> 00:07:01,170
outputs 0.0, even though
1 divided by 10 is 0.1.

160
00:07:01,170 --> 00:07:02,970
So why is it 0.0?

161
00:07:02,970 --> 00:07:05,510
Well, this is because
of integer division.

162
00:07:05,510 --> 00:07:08,580
So 1 is an integer, 10 is an integer.

163
00:07:08,580 --> 00:07:11,980
So 1 divided by 10, everything
is treated as integers,

164
00:07:11,980 --> 00:07:16,380
and in C, when we do integer division,
we truncate any decimal point.

165
00:07:16,380 --> 00:07:19,590
So 1 divided by 10 is
0, and then we're trying

166
00:07:19,590 --> 00:07:24,410
to print that as a float, so
zero printed as a float is 0.0.

167
00:07:24,410 --> 00:07:27,400
And that's why we get 0.0.

168
00:07:27,400 --> 00:07:28,940
>> Consider the program below.

169
00:07:28,940 --> 00:07:31,280
Now we're printing 0.1.

170
00:07:31,280 --> 00:07:34,280
So no integer division,
we're just printing 0.1,

171
00:07:34,280 --> 00:07:37,100
but we're printing it
to 28 decimal places.

172
00:07:37,100 --> 00:07:41,810
And we get this 0.1000, a whole bunch
of zeros, 5 5 5, blah blah blah.

173
00:07:41,810 --> 00:07:45,495
So the question here is why does it
print that, instead of exactly 0.1?

174
00:07:45,495 --> 00:07:46,620

175
00:07:46,620 --> 00:07:49,640
>> So the reason here is now
floating point imprecision.

176
00:07:49,640 --> 00:07:53,410
Remember that a float is only 32 bits.

177
00:07:53,410 --> 00:07:57,540
So we can only represent a finite number
of floating point values with those 32

178
00:07:57,540 --> 00:07:58,560
bits.

179
00:07:58,560 --> 00:08:01,760
Well there's ultimately infinitely
many floating point values,

180
00:08:01,760 --> 00:08:04,940
and there's infinitely many floating
point values in between 0 and 1,

181
00:08:04,940 --> 00:08:07,860
and we're obviously able to
represent even more values than that.

182
00:08:07,860 --> 00:08:13,230
So we have to make sacrifices to
be able to represent most values.

183
00:08:13,230 --> 00:08:16,960
>> So a value like 0.1, apparently
we can't represent that exactly.

184
00:08:16,960 --> 00:08:22,500
So instead of representing 0.1 we do the
best we can represent this 0.100000 5 5

185
00:08:22,500 --> 00:08:23,260
5.

186
00:08:23,260 --> 00:08:26,306
And that's pretty close, but
for a lot of applications

187
00:08:26,306 --> 00:08:28,430
you have to worry about
floating point imprecision,

188
00:08:28,430 --> 00:08:30,930
because we just can't represent
all floating points exactly.

189
00:08:30,930 --> 00:08:32,500

190
00:08:32,500 --> 00:08:33,380
>> Question 15.

191
00:08:33,380 --> 00:08:34,679
Consider the code below.

192
00:08:34,679 --> 00:08:36,630
We're just printing 1 plus 1.

193
00:08:36,630 --> 00:08:38,289
So there is no trick here.

194
00:08:38,289 --> 00:08:41,780
1 plus 1 evaluates to 2, and
then we're printing that.

195
00:08:41,780 --> 00:08:42,789
This just prints 2.

196
00:08:42,789 --> 00:08:43,850

197
00:08:43,850 --> 00:08:44,700
>> Question 16.

198
00:08:44,700 --> 00:08:49,450
Now we're printing the character
1 plus the character 1.

199
00:08:49,450 --> 00:08:52,110
So why does this not
print the same thing?

200
00:08:52,110 --> 00:08:57,680
Well the character 1 plus the character
1, the character 1 has ASCII value 49.

201
00:08:57,680 --> 00:09:04,840
So this is really saying 49 plus 49, and
ultimately this is going to print 98.

202
00:09:04,840 --> 00:09:06,130
So this does not print 2.

203
00:09:06,130 --> 00:09:08,070

204
00:09:08,070 --> 00:09:09,271
>> Question 17.

205
00:09:09,271 --> 00:09:11,520
Complete the implementation
of odd below in such a way

206
00:09:11,520 --> 00:09:14,615
that the function returns true if
n is odd and false if n is even.

207
00:09:14,615 --> 00:09:16,710

208
00:09:16,710 --> 00:09:19,330
This is a great purpose
for the mod operator.

209
00:09:19,330 --> 00:09:24,530
So we take our argument n,
if n mod 2 equals 1, well

210
00:09:24,530 --> 00:09:28,030
that means that n divided
by 2 had a remainder.

211
00:09:28,030 --> 00:09:33,270
If n divided by 2 had a remainder, that
means that n is odd, so we return true.

212
00:09:33,270 --> 00:09:34,910
Else we return false.

213
00:09:34,910 --> 00:09:39,070
You also could have done n mod 2 equals
zero, return false, else return true.

214
00:09:39,070 --> 00:09:41,600

215
00:09:41,600 --> 00:09:43,640
>> Consider the recursive function below.

216
00:09:43,640 --> 00:09:46,920
So if n is less than or
equal to 1, return 1,

217
00:09:46,920 --> 00:09:50,430
else return n times f of n minus 1.

218
00:09:50,430 --> 00:09:52,556
So what is this function?

219
00:09:52,556 --> 00:09:54,305
Well, this is just the
factorial function.

220
00:09:54,305 --> 00:09:55,410

221
00:09:55,410 --> 00:09:57,405
This is nicely represented
as n factorial.

222
00:09:57,405 --> 00:09:58,720

223
00:09:58,720 --> 00:10:02,310
>> So question 19 now, we want to
take this recursive function.

224
00:10:02,310 --> 00:10:04,530
We want to make it iterative.

225
00:10:04,530 --> 00:10:05,874
So how do we do that?

226
00:10:05,874 --> 00:10:07,790
Well for the staff
solution, and again there's

227
00:10:07,790 --> 00:10:11,090
multiple ways you could have done
that, we start with this int product

228
00:10:11,090 --> 00:10:11,812
equals 1.

229
00:10:11,812 --> 00:10:13,520
And throughout this
for loop, we're going

230
00:10:13,520 --> 00:10:17,590
to be multiplying product to ultimately
end up with the full factorial.

231
00:10:17,590 --> 00:10:21,870
So for int i equals 2, i is
less than or equal to n, i++.

232
00:10:21,870 --> 00:10:24,130
>> You might be wondering why i equals 2.

233
00:10:24,130 --> 00:10:28,380
Well, remember that here we have to
make sure our base case is correct.

234
00:10:28,380 --> 00:10:32,180
So if n is less than or equal
to 1, we're just returning 1.

235
00:10:32,180 --> 00:10:34,830
So over here, we start at i equals 2.

236
00:10:34,830 --> 00:10:39,090
Well if i were 1, then the-- or
if n were 1, then the for loop

237
00:10:39,090 --> 00:10:40,600
wouldn't execute at all.

238
00:10:40,600 --> 00:10:43,190
And so we would just
return product, which is 1.

239
00:10:43,190 --> 00:10:45,920
Similarly, if n were
anything less than 1--

240
00:10:45,920 --> 00:10:49,290
if it were 0, negative 1, whatever--
we'd still be returning 1,

241
00:10:49,290 --> 00:10:52,260
which is exactly what the
recursive version is doing.

242
00:10:52,260 --> 00:10:54,660
>> Now, if n is greater
than 1, then we're going

243
00:10:54,660 --> 00:10:56,550
to do at least one
iteration of this loop.

244
00:10:56,550 --> 00:11:00,630
So let's say n is 5, then we're
going to do product times equals 2.

245
00:11:00,630 --> 00:11:02,165
So now product is 2.

246
00:11:02,165 --> 00:11:04,040
Now we're going to do
product times equals 3.

247
00:11:04,040 --> 00:11:04,690
Now it's 6.

248
00:11:04,690 --> 00:11:07,500
Product times equals 4, now it's 24.

249
00:11:07,500 --> 00:11:10,420
Product times equals 5, now it's 120.

250
00:11:10,420 --> 00:11:16,730
So then ultimately, we're returning
120, which is correctly 5 factorial.

251
00:11:16,730 --> 00:11:17,510
>> Question 20.

252
00:11:17,510 --> 00:11:22,480
This is the one where you have to fill
in this table with any given algorithm,

253
00:11:22,480 --> 00:11:25,735
anything that we've seen, that
fits these algorithmic run

254
00:11:25,735 --> 00:11:28,060
times these asymptotic run times.

255
00:11:28,060 --> 00:11:33,270
So what is an algorithm that
is omega of 1, but big O of n?

256
00:11:33,270 --> 00:11:35,970
So there could be infinitely
many answers here.

257
00:11:35,970 --> 00:11:39,790
The one that we've seen probably most
frequently is just linear search.

258
00:11:39,790 --> 00:11:42,050
>> So in the best case
scenario, the item we're

259
00:11:42,050 --> 00:11:44,050
looking for is at the
beginning of the list

260
00:11:44,050 --> 00:11:47,400
and so in omega of 1 steps,
the first thing we check,

261
00:11:47,400 --> 00:11:49,740
we just immediately return
that we found the item.

262
00:11:49,740 --> 00:11:52,189
In the worst case scenario,
the item is at the end,

263
00:11:52,189 --> 00:11:53,730
or the item isn't in the list at all.

264
00:11:53,730 --> 00:11:56,700
So we have to search
the entire list, all n

265
00:11:56,700 --> 00:11:58,480
elements, and that's why it's o of n.

266
00:11:58,480 --> 00:11:59,670

267
00:11:59,670 --> 00:12:04,880
>> So now it's something that's both
omega of n log n, and big O of n log n.

268
00:12:04,880 --> 00:12:08,650
Well the most relevant thing
we've seen here is merge sort.

269
00:12:08,650 --> 00:12:12,950
So merge sort, remember,
is ultimately theta

270
00:12:12,950 --> 00:12:16,920
of n log n, where theta is defined
if both omega and big O are the same.

271
00:12:16,920 --> 00:12:17,580
Both n log n.

272
00:12:17,580 --> 00:12:18,690

273
00:12:18,690 --> 00:12:21,970
>> What's something that's omega
of n, and O of n squared?

274
00:12:21,970 --> 00:12:23,990
Well, again there's
multiple possible answers.

275
00:12:23,990 --> 00:12:26,440
Here we happen to say bubble sort.

276
00:12:26,440 --> 00:12:28,840
Insertion sort would also work here.

277
00:12:28,840 --> 00:12:31,400
Remember that bubble sort
has that optimization where,

278
00:12:31,400 --> 00:12:34,630
if you are able to get
through the entire list

279
00:12:34,630 --> 00:12:37,402
without needing to do
any swaps, then, well,

280
00:12:37,402 --> 00:12:40,110
we can immediately return that
the list was sorted to begin with.

281
00:12:40,110 --> 00:12:43,185
So in the best case scenario,
it's just omega of n.

282
00:12:43,185 --> 00:12:45,960
If it's not just a nicely
sorted list to begin with,

283
00:12:45,960 --> 00:12:48,270
then we have O of n squared swaps.

284
00:12:48,270 --> 00:12:49,330

285
00:12:49,330 --> 00:12:55,610
And finally, we have selection sort
for n squared, both omega and big O.

286
00:12:55,610 --> 00:12:56,850
>> Question 21.

287
00:12:56,850 --> 00:12:58,870
What's integer overflow?

288
00:12:58,870 --> 00:13:02,160
Well again, similar to earlier,
we only have finitely many bits

289
00:13:02,160 --> 00:13:04,255
to represent an integer,
so maybe 32 bits.

290
00:13:04,255 --> 00:13:06,300

291
00:13:06,300 --> 00:13:09,180
Let's say we have a signed integer.

292
00:13:09,180 --> 00:13:12,800
Then ultimately the highest
positive number we can represent

293
00:13:12,800 --> 00:13:15,910
is 2 to the 31 minus 1.

294
00:13:15,910 --> 00:13:19,370
So what happens if we try to
then increment that integer?

295
00:13:19,370 --> 00:13:25,320
Well, we're going to go from 2 to the 31
minus 1, all the way down to negative 2

296
00:13:25,320 --> 00:13:26,490
to the 31.

297
00:13:26,490 --> 00:13:29,470
So this integer overflow is
when you keep incrementing,

298
00:13:29,470 --> 00:13:32,330
and ultimately you can't
get any higher and it just

299
00:13:32,330 --> 00:13:34,520
wraps all the way back
around to a negative value.

300
00:13:34,520 --> 00:13:35,850

301
00:13:35,850 --> 00:13:37,779
>> What about a buffer overflow?

302
00:13:37,779 --> 00:13:39,820
So a buffer overflow--
remember what a buffer is.

303
00:13:39,820 --> 00:13:41,000
It's just a chunk of memory.

304
00:13:41,000 --> 00:13:43,350
Something like an array is a buffer.

305
00:13:43,350 --> 00:13:46,120
So a buffer overflow is when
you try to access memory

306
00:13:46,120 --> 00:13:47,880
beyond the end of that array.

307
00:13:47,880 --> 00:13:50,410
So if you have an
array of size 5 and you

308
00:13:50,410 --> 00:13:53,700
try to access array bracket
5 or bracket 6 or bracket 7,

309
00:13:53,700 --> 00:13:56,610
or anything beyond the
end, or even anything

310
00:13:56,610 --> 00:14:00,790
below-- array bracket negative 1--
all of those are buffer overflows.

311
00:14:00,790 --> 00:14:02,810
You're touching memory in bad ways.

312
00:14:02,810 --> 00:14:04,090

313
00:14:04,090 --> 00:14:04,730
>> Question 23.

314
00:14:04,730 --> 00:14:05,760

315
00:14:05,760 --> 00:14:09,100
So in this one you need
to implement strlen.

316
00:14:09,100 --> 00:14:11,630
And we tell you that you can
assume s will not be null,

317
00:14:11,630 --> 00:14:13,790
so you don't have to
do any check for null.

318
00:14:13,790 --> 00:14:16,190
And there are multiple ways
you could have done this.

319
00:14:16,190 --> 00:14:18,440
Here we just take the straightforward.

320
00:14:18,440 --> 00:14:21,780
We start with a counter, n. n is
counting how many characters there are.

321
00:14:21,780 --> 00:14:25,560
So we start at 0, and then we
iterate over the entire list.

322
00:14:25,560 --> 00:14:29,092
>> Is s bracket 0 equal to the
null terminator character?

323
00:14:29,092 --> 00:14:31,425
Remember we're looking for
the null terminator character

324
00:14:31,425 --> 00:14:33,360
to determine how long our string is.

325
00:14:33,360 --> 00:14:35,890
That is going to terminate
any relevant string.

326
00:14:35,890 --> 00:14:39,400
So is s bracket 0 equal
to the null terminator?

327
00:14:39,400 --> 00:14:42,850
If it's not, then we're going to
look at s bracket 1, s bracket 2.

328
00:14:42,850 --> 00:14:45,050
We keep going until we
find the null terminator.

329
00:14:45,050 --> 00:14:48,580
Once we've found it, then n contains
the total length of the string,

330
00:14:48,580 --> 00:14:49,942
and we can just return that.

331
00:14:49,942 --> 00:14:51,180

332
00:14:51,180 --> 00:14:51,865
>> Question 24.

333
00:14:51,865 --> 00:14:53,010

334
00:14:53,010 --> 00:14:56,050
So this is the one where you
have to make the trade off.

335
00:14:56,050 --> 00:14:59,810
So one thing is good in one
way, but in what way is it bad?

336
00:14:59,810 --> 00:15:02,980
So here, merge sort tends to
be faster than bubble sort.

337
00:15:02,980 --> 00:15:06,530
Having said that-- well, there
are multiple answers here.

338
00:15:06,530 --> 00:15:12,930
But the main one is that bubble sort
is omega of n for a sorted list.

339
00:15:12,930 --> 00:15:14,950
>> Remember that table we just saw earlier.

340
00:15:14,950 --> 00:15:17,600
So bubble sorts omega of
n, the best case scenario

341
00:15:17,600 --> 00:15:20,010
is it's able to just go over
the list once, determine

342
00:15:20,010 --> 00:15:22,270
hey this thing is already
sorted, and return.

343
00:15:22,270 --> 00:15:25,960
Merge sort, no matter what
you do, is omega of n log n.

344
00:15:25,960 --> 00:15:29,200
So for sorted list, bubble
sort's going to be faster.

345
00:15:29,200 --> 00:15:30,870

346
00:15:30,870 --> 00:15:32,430
>> Now what about linked lists?

347
00:15:32,430 --> 00:15:36,070
So a linked list can grow and shrink
to fit as many elements as needed.

348
00:15:36,070 --> 00:15:38,489
Having said that-- so
usually the direct comparison

349
00:15:38,489 --> 00:15:40,280
is going to be a linked
list with an array.

350
00:15:40,280 --> 00:15:41,600

351
00:15:41,600 --> 00:15:44,050
So even though arrays can
easily grow and shrink

352
00:15:44,050 --> 00:15:47,130
to fit as many elements
as needed, a linked list

353
00:15:47,130 --> 00:15:49,600
compared to an array-- an
array has random access.

354
00:15:49,600 --> 00:15:52,960
We can index into any
particular element of the array.

355
00:15:52,960 --> 00:15:56,430
>> So for a linked list, we can't
just go to the fifth element,

356
00:15:56,430 --> 00:16:00,260
we have to traverse from the beginning
until we get to the fifth element.

357
00:16:00,260 --> 00:16:03,990
And that's going to prevent us from
doing something like binary search.

358
00:16:03,990 --> 00:16:08,150
Speaking of binary search, binary search
tends to be faster than linear search.

359
00:16:08,150 --> 00:16:11,120
Having said that--
so, one possible thing

360
00:16:11,120 --> 00:16:13,380
is that you can't do binary
search on linked lists,

361
00:16:13,380 --> 00:16:14,730
you can only do it on arrays.

362
00:16:14,730 --> 00:16:18,030
But probably more importantly,
you can't do binary search

363
00:16:18,030 --> 00:16:20,690
on an array that is not sorted.

364
00:16:20,690 --> 00:16:23,990
Upfront you might need to sort
the array, and only then can

365
00:16:23,990 --> 00:16:25,370
you do binary search.

366
00:16:25,370 --> 00:16:27,660
So if your thing isn't
sorted to begin with,

367
00:16:27,660 --> 00:16:29,250
then linear search might be faster.

368
00:16:29,250 --> 00:16:30,620

369
00:16:30,620 --> 00:16:31,740
>> Question 27.

370
00:16:31,740 --> 00:16:34,770
So consider the program below,
which will be in the next slide.

371
00:16:34,770 --> 00:16:37,790
And this is the one where we're
going to want to explicitly state

372
00:16:37,790 --> 00:16:39,980
the values for various variables.

373
00:16:39,980 --> 00:16:41,990
So let's look at that.

374
00:16:41,990 --> 00:16:43,160
>> So line one.

375
00:16:43,160 --> 00:16:45,457
We have int x equals 1.

376
00:16:45,457 --> 00:16:47,040
That's the only thing that's happened.

377
00:16:47,040 --> 00:16:50,440
So at line one, we see in our
table, that y, a, b, and tmp are all

378
00:16:50,440 --> 00:16:51,540
blacked out.

379
00:16:51,540 --> 00:16:52,280
So what is x?

380
00:16:52,280 --> 00:16:53,860
Well we just set it equal to 1.

381
00:16:53,860 --> 00:16:55,020

382
00:16:55,020 --> 00:16:58,770
And then line two, well,
we see that y is set to 2,

383
00:16:58,770 --> 00:17:00,550
and the table is already
filled in for us.

384
00:17:00,550 --> 00:17:03,040
So x is 1 and y is 2.

385
00:17:03,040 --> 00:17:05,890
>> Now, line three, we're now
inside the swap function.

386
00:17:05,890 --> 00:17:07,560
What did we pass to swap?

387
00:17:07,560 --> 00:17:11,609
We passed ampersand x for
a, and ampersand y for b.

388
00:17:11,609 --> 00:17:15,160
Where the problem earlier
stated that the address of x

389
00:17:15,160 --> 00:17:17,520
is 0x10, and the address of y is 0x14.

390
00:17:17,520 --> 00:17:18,970

391
00:17:18,970 --> 00:17:21,909
So a and b are equal to
0x10 and 0x14, respectively.

392
00:17:21,909 --> 00:17:23,670

393
00:17:23,670 --> 00:17:26,250
>> Now at line three, what are x and y?

394
00:17:26,250 --> 00:17:28,554
Well, nothing has changed
about x and y at this point.

395
00:17:28,554 --> 00:17:30,470
Even though they're
inside a main stack frame,

396
00:17:30,470 --> 00:17:32,469
they still have the same
values they did before.

397
00:17:32,469 --> 00:17:34,030
We haven't modified any memory.

398
00:17:34,030 --> 00:17:35,710
So x is 1, y is 2.

399
00:17:35,710 --> 00:17:36,550

400
00:17:36,550 --> 00:17:37,050
All right.

401
00:17:37,050 --> 00:17:40,300
So now we said int tmp equal to star a.

402
00:17:40,300 --> 00:17:44,410
So at line four, everything
is the same except for tmp.

403
00:17:44,410 --> 00:17:47,130
We haven't changed any values
of anything except for tmp.

404
00:17:47,130 --> 00:17:49,230
We are setting tmp equal to star a.

405
00:17:49,230 --> 00:17:50,620
What is star a?

406
00:17:50,620 --> 00:17:56,240
Well, a points to x, So star a
is going to equal x, which is 1.

407
00:17:56,240 --> 00:18:00,080
So everything is copied
down, and tmp is set to 1.

408
00:18:00,080 --> 00:18:01,110
>> Now the next line.

409
00:18:01,110 --> 00:18:03,380
Star a equals star b.

410
00:18:03,380 --> 00:18:10,000
So by line five-- well again, everything
is the same except whatever star a is.

411
00:18:10,000 --> 00:18:10,830
What is star a?

412
00:18:10,830 --> 00:18:13,720
Well, we just said star a is x.

413
00:18:13,720 --> 00:18:16,400
So we're changing x to equal star b.

414
00:18:16,400 --> 00:18:18,960
What is star b? y. b points to y.

415
00:18:18,960 --> 00:18:21,030
So star b is y.

416
00:18:21,030 --> 00:18:25,140
So we're setting x equal to y,
and everything else is the same.

417
00:18:25,140 --> 00:18:29,130
So we see in the next row that x is now
2, and the rest are just copied down.

418
00:18:29,130 --> 00:18:31,120
>> Now in the next line, star b equals tmp.

419
00:18:31,120 --> 00:18:34,740
Well, we just said star b is y,
so we're setting y equal to tmp.

420
00:18:34,740 --> 00:18:37,450
Everything else is the same,
so everything gets copied down.

421
00:18:37,450 --> 00:18:42,050
We're setting y equal to tmp, which is
one, and everything else is the same.

422
00:18:42,050 --> 00:18:43,210
>> Now finally, line seven.

423
00:18:43,210 --> 00:18:44,700
We're back in the main function.

424
00:18:44,700 --> 00:18:46,350
We're after swap is finished.

425
00:18:46,350 --> 00:18:48,972
We have lost a, b, and
tmp, but ultimately we

426
00:18:48,972 --> 00:18:51,180
aren't changing any values
of anything at this point,

427
00:18:51,180 --> 00:18:52,800
we just copy x and y down.

428
00:18:52,800 --> 00:18:56,490
And we see that x and y are
now 2 and 1 instead of 1 and 2.

429
00:18:56,490 --> 00:18:58,160
The swap has successfully executed.

430
00:18:58,160 --> 00:18:59,500

431
00:18:59,500 --> 00:19:00,105
>> Question 28.

432
00:19:00,105 --> 00:19:01,226

433
00:19:01,226 --> 00:19:03,100
Suppose that you encounter
the error messages

434
00:19:03,100 --> 00:19:06,790
below during office hours
next year as a CA or TF.

435
00:19:06,790 --> 00:19:08,930
Advise how to fix each of these errors.

436
00:19:08,930 --> 00:19:11,160
So undefined reference to GetString.

437
00:19:11,160 --> 00:19:12,540
Why might you see this?

438
00:19:12,540 --> 00:19:15,380
Well, if a student is using
GetString in their code,

439
00:19:15,380 --> 00:19:20,310
they have properly hash included cs50
dot h to include the cs50 library.

440
00:19:20,310 --> 00:19:22,380
>> Well, what do they
need to fix this error?

441
00:19:22,380 --> 00:19:26,810
They need to do a dash lcs50 at the
command line when they're compiling.

442
00:19:26,810 --> 00:19:29,501
So if they don't pass
clang dash lcs50, they're

443
00:19:29,501 --> 00:19:32,000
not going to have the actual
code that implements GetString.

444
00:19:32,000 --> 00:19:33,190

445
00:19:33,190 --> 00:19:34,170
>> Question 29.

446
00:19:34,170 --> 00:19:36,190
Implicitly declaring
library function strlen.

447
00:19:36,190 --> 00:19:37,550

448
00:19:37,550 --> 00:19:40,360
Well this now, they haven't
done the proper hash include.

449
00:19:40,360 --> 00:19:41,440

450
00:19:41,440 --> 00:19:45,410
In this particular case, the header file
they need to include is string dot h,

451
00:19:45,410 --> 00:19:48,710
and including string dot h, now
the student-- now the compiler

452
00:19:48,710 --> 00:19:51,750
has access to the
declarations of strlen,

453
00:19:51,750 --> 00:19:54,120
and it knows that your code
is using strlen correctly.

454
00:19:54,120 --> 00:19:55,380

455
00:19:55,380 --> 00:19:56,580
>> Question 30.

456
00:19:56,580 --> 00:20:00,240
More percent conversions
than data arguments.

457
00:20:00,240 --> 00:20:01,540
So what is this?

458
00:20:01,540 --> 00:20:06,470
Well remember that these percent
signs-- how they're relevant to printf.

459
00:20:06,470 --> 00:20:08,890
So in printf we might percent--
we might print something

460
00:20:08,890 --> 00:20:11,380
like percent i backslash n.

461
00:20:11,380 --> 00:20:15,310
Or we might print like percent i,
space, percent i, space, percent i.

462
00:20:15,310 --> 00:20:18,950
So for each of those
percent signs, we need

463
00:20:18,950 --> 00:20:21,560
to pass a variable at the end of printf.

464
00:20:21,560 --> 00:20:26,980
>> So if we say printf paren percent
i backslash n close paren,

465
00:20:26,980 --> 00:20:30,270
well, we say that we're
going to print an integer,

466
00:20:30,270 --> 00:20:33,970
but then we don't pass printf
an integer to actually print.

467
00:20:33,970 --> 00:20:37,182
So here more percent
conversions than data arguments?

468
00:20:37,182 --> 00:20:39,390
That's saying that we have
a whole bunch of percents,

469
00:20:39,390 --> 00:20:42,445
and we don't have enough variables
to actually fill in those percents.

470
00:20:42,445 --> 00:20:44,850

471
00:20:44,850 --> 00:20:50,010
>> And then definitely, for question 31,
definitely lost 40 bytes in one blocks.

472
00:20:50,010 --> 00:20:52,350
So this is a Valgrind error.

473
00:20:52,350 --> 00:20:54,720
This is saying that
somewhere in your code,

474
00:20:54,720 --> 00:20:59,010
you have an allocation that is 40
bytes large so you malloced 40 bytes,

475
00:20:59,010 --> 00:21:00,515
and you never freed it.

476
00:21:00,515 --> 00:21:02,480

477
00:21:02,480 --> 00:21:05,140
Most likely you just need
to find some memory leak,

478
00:21:05,140 --> 00:21:07,650
and find where you need to
free this block of memory.

479
00:21:07,650 --> 00:21:08,780

480
00:21:08,780 --> 00:21:11,910
>> And question 32,
invalid write of size 4.

481
00:21:11,910 --> 00:21:13,250
Again this is a Valgrind error.

482
00:21:13,250 --> 00:21:15,440
This doesn't have to do
with memory leaks now.

483
00:21:15,440 --> 00:21:20,750
This is, most likely-- I mean, it's
some sort of invalid memory rights.

484
00:21:20,750 --> 00:21:23,270
And most likely this is some
sort of buffer overflow.

485
00:21:23,270 --> 00:21:26,560
Where you have an array, maybe
an integer array, and let's

486
00:21:26,560 --> 00:21:30,115
say it's of size 5, and you
try to touch array bracket 5.

487
00:21:30,115 --> 00:21:34,150
So if you try to write to that
value, that's not a piece of memory

488
00:21:34,150 --> 00:21:37,440
that you actually have access to, and
so you're going to get this error,

489
00:21:37,440 --> 00:21:39,272
saying invalid write of size 4.

490
00:21:39,272 --> 00:21:42,480
Valgrind is going to recognize you're
trying to touch memory inappropriately.

491
00:21:42,480 --> 00:21:43,980
>> And that's it for quiz0.

492
00:21:43,980 --> 00:21:47,065
I'm Rob Bowden, and this is CS50.

493
00:21:47,065 --> 00:21:51,104