1
00:00:00,000 --> 00:00:10,550

2
00:00:10,550 --> 00:00:14,050
>> DAVID J. MALAN: This is CS50 and
this is the start of week four.

3
00:00:14,050 --> 00:00:18,630
And, boy, is Volkswagen in
trouble all because of software.

4
00:00:18,630 --> 00:00:20,264
Let us take a look.

5
00:00:20,264 --> 00:00:20,930
[VIDEO PLAYBACK]

6
00:00:20,930 --> 00:00:25,560
-Cars, the smartest characters
in the Fast and Furious movies.

7
00:00:25,560 --> 00:00:29,100
This week German automaker
Volkswagen found itself

8
00:00:29,100 --> 00:00:32,490
in the middle of a scandal of
potentially criminal proportions.

9
00:00:32,490 --> 00:00:36,060
>> -Volkswagen is bracing for billions
in fines, possible criminal charges

10
00:00:36,060 --> 00:00:38,560
for its executives, as
the company apologizes

11
00:00:38,560 --> 00:00:41,840
for rigging 11 million cars to
help it beat emissions tests.

12
00:00:41,840 --> 00:00:44,950
>> -Certain diesel models were
designed with sophisticated software

13
00:00:44,950 --> 00:00:48,440
that used information including the
position of the steering and vehicle

14
00:00:48,440 --> 00:00:51,870
speed to determine the car was
undergoing emissions testing.

15
00:00:51,870 --> 00:00:55,650
Under that circumstance, the engine
would reduce toxic emissions.

16
00:00:55,650 --> 00:00:59,070
But the car was rigged to bypass
that when it was being driven.

17
00:00:59,070 --> 00:01:03,320
Emissions increased 10 to 40
times above acceptable EPA levels.

18
00:01:03,320 --> 00:01:04,280
>> [END PLAYBACK]

19
00:01:04,280 --> 00:01:05,220
>> DAVID J. MALAN: So let's
take a look at this

20
00:01:05,220 --> 00:01:07,250
and see exactly how this
might be implemented

21
00:01:07,250 --> 00:01:09,680
and how this might affect
so many cars like this.

22
00:01:09,680 --> 00:01:12,840
So in my hand here are the press
release that was issued by the EPA--

23
00:01:12,840 --> 00:01:14,620
the Environmental
Protection Agency which

24
00:01:14,620 --> 00:01:18,032
is the US regulatory agency that
handles environmental concerns,

25
00:01:18,032 --> 00:01:19,740
and then the actual
legal notice that was

26
00:01:19,740 --> 00:01:22,420
send to Volkswagen just a few days ago.

27
00:01:22,420 --> 00:01:26,530
>> So the EPA writes, and discloses now
publicly, a sophisticated software

28
00:01:26,530 --> 00:01:29,390
algorithm on certain
Volkswagen vehicles detects

29
00:01:29,390 --> 00:01:32,630
when the car is undergoing
official emissions testing

30
00:01:32,630 --> 00:01:36,505
and turns full emissions
controls on only during the test.

31
00:01:36,505 --> 00:01:38,380
The effectiveness of
these vehicles pollution

32
00:01:38,380 --> 00:01:43,260
emissions control devices is greatly
reduced during all normal driving

33
00:01:43,260 --> 00:01:44,320
situations.

34
00:01:44,320 --> 00:01:48,190
This results in cars that meet the
standards in the laboratory or testing

35
00:01:48,190 --> 00:01:52,790
station, but during normal operation
emit nitrogen oxides-- or NOx--

36
00:01:52,790 --> 00:01:54,950
at up to 40 times the standard.

37
00:01:54,950 --> 00:01:58,220
The software produced by Volkswagen
is a quote unquote, defeat device,

38
00:01:58,220 --> 00:02:00,650
as defined by the Clean
Air Act in the US.

39
00:02:00,650 --> 00:02:03,410
>> They go on to say that
the EPA and another agency

40
00:02:03,410 --> 00:02:07,020
uncovered the defeat device
software after independent analysis

41
00:02:07,020 --> 00:02:09,660
by researchers at West
Virginia University.

42
00:02:09,660 --> 00:02:14,160
NOx pollution contributes to
nitrogen dioxide, ground level ozone,

43
00:02:14,160 --> 00:02:15,700
and fine particulate matter.

44
00:02:15,700 --> 00:02:18,090
Exposure to these
pollutants has been linked

45
00:02:18,090 --> 00:02:20,870
with a wide range of
serious health effects,

46
00:02:20,870 --> 00:02:23,637
including increased asthma
attacks and other respiratory

47
00:02:23,637 --> 00:02:26,470
illnesses that can be serious enough
to send people to the hospital.

48
00:02:26,470 --> 00:02:28,660
Exposure to ozone and
particulate matter has also

49
00:02:28,660 --> 00:02:31,960
been associated with premature
death due to respiratory related

50
00:02:31,960 --> 00:02:35,690
or cardiovascular related effects.

51
00:02:35,690 --> 00:02:38,940
Children, the elderly, people with
preexisting respiratory disease

52
00:02:38,940 --> 00:02:42,840
are particularly at risk for
health effects of these pollutants.

53
00:02:42,840 --> 00:02:45,056
>> Suffice is to say, it's quite serious.

54
00:02:45,056 --> 00:02:46,930
And let's go on to read
just one more excerpt

55
00:02:46,930 --> 00:02:49,370
and then we'll take a look at
the underlying implications

56
00:02:49,370 --> 00:02:50,920
of this in the context of a car.

57
00:02:50,920 --> 00:02:53,730
Specifically, Volkswagen
manufactured and installed

58
00:02:53,730 --> 00:02:56,210
software in the so-called
electronic control

59
00:02:56,210 --> 00:02:59,320
module-- or ECM-- of
these vehicles that sensed

60
00:02:59,320 --> 00:03:03,580
when the vehicle was being tested for
compliance with EPA emission standards.

61
00:03:03,580 --> 00:03:07,510
Based on various inputs including the
position of the steering wheel, vehicle

62
00:03:07,510 --> 00:03:11,280
speed, the duration of the engine's
operation, and barometric pressure,

63
00:03:11,280 --> 00:03:13,720
these inputs precisely
tracked the parameters

64
00:03:13,720 --> 00:03:17,600
of the federal test procedure used for
emission testing for EPA certification

65
00:03:17,600 --> 00:03:18,400
purposes.

66
00:03:18,400 --> 00:03:21,850
>> During EPA's emission testing,
the vehicles ECM software

67
00:03:21,850 --> 00:03:25,060
ran software which produced
compliant emissions results.

68
00:03:25,060 --> 00:03:28,340
At all other times, the
vehicle ECM software

69
00:03:28,340 --> 00:03:31,090
ran a separate road
calibration which reduced

70
00:03:31,090 --> 00:03:34,360
the effectiveness of the
overall emission control system,

71
00:03:34,360 --> 00:03:37,864
specifically the selective catalytic
reduction of the Lean NOx trap--

72
00:03:37,864 --> 00:03:39,280
which we'll see about in a moment.

73
00:03:39,280 --> 00:03:43,040
As a result, emissions of NOx
increased by a factor of 10 to 40 times

74
00:03:43,040 --> 00:03:47,450
above the EPA compliant levels
depending on the type of drive cycle.

75
00:03:47,450 --> 00:03:50,800
>> So what this really means, and the
source code to the software running

76
00:03:50,800 --> 00:03:53,190
on the Volkswagen's has not
yet been publicly disclosed,

77
00:03:53,190 --> 00:03:56,460
is that, effectively, this
equivalent is somewhere there inside

78
00:03:56,460 --> 00:03:57,830
of Volkswagen's code.

79
00:03:57,830 --> 00:04:02,200
If you are being tested, and if the car
detects certain environmental factors

80
00:04:02,200 --> 00:04:04,330
like the steering wheel
position or the movement

81
00:04:04,330 --> 00:04:06,710
or lack thereof of the car or
any number of other factors

82
00:04:06,710 --> 00:04:09,940
that are currently hypothesized
to be part of this formula,

83
00:04:09,940 --> 00:04:12,370
they simply turn on
full emissions control.

84
00:04:12,370 --> 00:04:15,670
In other words, they start
emitting less of the pollutants.

85
00:04:15,670 --> 00:04:18,769
>> Else, in every other situation
when it's not detected as being

86
00:04:18,769 --> 00:04:20,790
in the laboratory, they just don't.

87
00:04:20,790 --> 00:04:24,320
And so you can simplify this into more
concrete pseudocode with something

88
00:04:24,320 --> 00:04:24,820
like this.

89
00:04:24,820 --> 00:04:27,810
If the wheels are turning but the
steering wheel isn't, suggestive

90
00:04:27,810 --> 00:04:30,060
that the car is on some
kind of rotating cylinder

91
00:04:30,060 --> 00:04:32,550
but in some kind of
warehouse being tested,

92
00:04:32,550 --> 00:04:36,070
then behave as the
EPA would like you to.

93
00:04:36,070 --> 00:04:37,960
Otherwise do not.

94
00:04:37,960 --> 00:04:40,420
So let's take a look
at a short video that

95
00:04:40,420 --> 00:04:45,391
takes a look at what the implications
are of this actually mechanically.

96
00:04:45,391 --> 00:04:48,620
>> [VIDEO PLAYBACK]

97
00:04:48,620 --> 00:04:52,800
>> -Last Friday the EPA announced that some
Volkswagen Audi cars made between 2009

98
00:04:52,800 --> 00:04:55,840
and this year were using
a so-called defeat device

99
00:04:55,840 --> 00:04:59,060
to get around emissions laws
designed to keep the air clean.

100
00:04:59,060 --> 00:05:01,700
But what does that mean exactly?

101
00:05:01,700 --> 00:05:04,666
>> Well, modern cars have dozens
of computers inside them.

102
00:05:04,666 --> 00:05:07,040
And some of those computers
help coordinate the functions

103
00:05:07,040 --> 00:05:09,590
of the engine for optimum
performance while making sure

104
00:05:09,590 --> 00:05:12,340
that there isn't too much garbage
coming out of the exhaust pipe.

105
00:05:12,340 --> 00:05:15,170
They've actually been working
this way for several decades now.

106
00:05:15,170 --> 00:05:17,380
Basically, every part
of a modern car's engine

107
00:05:17,380 --> 00:05:20,080
has a sensor or controller
on it, and these computers

108
00:05:20,080 --> 00:05:23,460
are reading in data thousands of
times per second making adjustments

109
00:05:23,460 --> 00:05:26,220
like the ratio of fuel to air
that's going into the cylinders.

110
00:05:26,220 --> 00:05:28,730
>> These cheating Volkswagen
and Audi models are diesels,

111
00:05:28,730 --> 00:05:30,890
and diesels have one more
really important computer

112
00:05:30,890 --> 00:05:34,030
controlled parameters, which is
the amount of unburned fuel going

113
00:05:34,030 --> 00:05:35,200
into the exhaust.

114
00:05:35,200 --> 00:05:36,310
Now that sounds bad.

115
00:05:36,310 --> 00:05:39,642
Doesn't sound like you would want
unburned fuel going into the exhaust.

116
00:05:39,642 --> 00:05:41,600
But in the case of a
diesel, you have something

117
00:05:41,600 --> 00:05:46,110
called a NOx trap which is a device that
absorbs and traps for nitrogen oxides

118
00:05:46,110 --> 00:05:48,880
that are pollutants that would
otherwise go into the atmosphere.

119
00:05:48,880 --> 00:05:53,040
And the effect of that NOx trap
is enhanced with unburned fuel.

120
00:05:53,040 --> 00:05:56,650
So a defeat device is a special program
inside these computers that can make it

121
00:05:56,650 --> 00:05:59,527
look like the car meets emission
standards even when it doesn't.

122
00:05:59,527 --> 00:06:01,110
Volkswagen had a problem on its hands.

123
00:06:01,110 --> 00:06:04,050
Its diesel engines were known
for getting great fuel economy,

124
00:06:04,050 --> 00:06:07,510
but the NOx trap only works well
when more fuel is being used.

125
00:06:07,510 --> 00:06:10,460
So the car would detect,
using this defeat device,

126
00:06:10,460 --> 00:06:13,870
when it was getting an emissions
test, it would use more fuel,

127
00:06:13,870 --> 00:06:16,830
make the NOx trap work well,
emissions would be fine.

128
00:06:16,830 --> 00:06:21,130
But then you get on the road, the device
turns off, you're burning less fuel

129
00:06:21,130 --> 00:06:24,256
but you're putting as much as 40 times
more pollutants into the atmosphere.

130
00:06:24,256 --> 00:06:26,130
But how the heck did
the car know that it was

131
00:06:26,130 --> 00:06:27,720
being tested for emissions compliance?

132
00:06:27,720 --> 00:06:30,590
The EPA says it was a sophisticated
system that checked things

133
00:06:30,590 --> 00:06:34,090
like steering wheel position,
speed, how long the engine was on,

134
00:06:34,090 --> 00:06:35,507
and even the atmospheric pressure.

135
00:06:35,507 --> 00:06:37,673
In other words, there was
no way this was accidental

136
00:06:37,673 --> 00:06:40,260
because the software was
designed very carefully to detect

137
00:06:40,260 --> 00:06:41,630
an official emissions test.

138
00:06:41,630 --> 00:06:43,588
That's some pretty serious
deception and that's

139
00:06:43,588 --> 00:06:45,420
why Volkswagen is in
such serious trouble.

140
00:06:45,420 --> 00:06:48,600
In fact, their CEO, Martin
Winterkorn, just stepped down.

141
00:06:48,600 --> 00:06:49,820
>> So what happens next?

142
00:06:49,820 --> 00:06:53,900
Well, if you're one of the half million
diesel Jettas, Beatles, Golfs, Passats,

143
00:06:53,900 --> 00:06:56,220
or Audi A3s effected,
the good news is is

144
00:06:56,220 --> 00:06:57,886
that your car is still safe to drive.

145
00:06:57,886 --> 00:07:00,510
You don't have to put it away
until Volkswagen issues a recall.

146
00:07:00,510 --> 00:07:02,509
But at some point they're
probably going to have

147
00:07:02,509 --> 00:07:04,230
to update the software inside your car.

148
00:07:04,230 --> 00:07:06,927
When that happens you might
get fewer miles per tank.

149
00:07:06,927 --> 00:07:09,260
Lawyers are already gearing
up for class action lawsuits

150
00:07:09,260 --> 00:07:12,500
so owners might get compensated
at some point in the future.

151
00:07:12,500 --> 00:07:15,832
But that's not going to
happen any time soon.

152
00:07:15,832 --> 00:07:16,711
>> [END PLAYBACK]

153
00:07:16,711 --> 00:07:19,960
DAVID J. MALAN: So this actually raises
an interesting bigger picture question

154
00:07:19,960 --> 00:07:20,660
as to trust.

155
00:07:20,660 --> 00:07:21,160
Right?

156
00:07:21,160 --> 00:07:24,300
All of us have iPhones or Androids or
something in our pockets most likely

157
00:07:24,300 --> 00:07:26,500
these days, or laptops
on our laps that are

158
00:07:26,500 --> 00:07:28,510
running software made
by Apple and Microsoft

159
00:07:28,510 --> 00:07:30,710
and bunches of other companies.

160
00:07:30,710 --> 00:07:34,240
But how do we know that what
these software products are doing

161
00:07:34,240 --> 00:07:37,680
is actually what these
companies say they are doing?

162
00:07:37,680 --> 00:07:39,610
>> For instance, who's to
say that every time you

163
00:07:39,610 --> 00:07:42,200
make a phone call on your iPhone
or Android phone or the like,

164
00:07:42,200 --> 00:07:45,650
that that phone number also isn't
being uploaded to some company's server

165
00:07:45,650 --> 00:07:48,399
because of some program you've
written, whether it's the operating

166
00:07:48,399 --> 00:07:51,070
system itself like iOS or Android,
or because you've downloaded

167
00:07:51,070 --> 00:07:53,880
some third party app
that somehow is listening

168
00:07:53,880 --> 00:07:57,120
to everything you're typing in or
everything you're actually saying.

169
00:07:57,120 --> 00:07:59,500
How do you know that, when
you guys are running Clang

170
00:07:59,500 --> 00:08:02,590
or Make to compile your
own software in CS50, how

171
00:08:02,590 --> 00:08:06,080
do you that CS50's own staff,
by way of the CS50 library,

172
00:08:06,080 --> 00:08:08,690
hasn't been logging every
string you've ever gotten

173
00:08:08,690 --> 00:08:10,276
or every inch you've ever gotten?

174
00:08:10,276 --> 00:08:12,900
Well, you could certainly look
at the source code for something

175
00:08:12,900 --> 00:08:15,233
like the CS50 library, you
could look at the source code

176
00:08:15,233 --> 00:08:18,170
for Linux operating system
running on CS50 IDE.

177
00:08:18,170 --> 00:08:23,090
But an amazing presentation
was given back in 1984

178
00:08:23,090 --> 00:08:26,730
in receipt of the Turing Award by a
very famous computer scientist known

179
00:08:26,730 --> 00:08:29,750
as-- named Ken Thompson who
received the Turing Award which

180
00:08:29,750 --> 00:08:33,500
is sort of computer science's
Nobel Prize, if you will,

181
00:08:33,500 --> 00:08:35,309
for his work on an
operating system called

182
00:08:35,309 --> 00:08:39,039
Unix, which is very similar in
spirit to what we use which is Linux.

183
00:08:39,039 --> 00:08:41,960
And the question he asked in his
acceptance speech, essentially

184
00:08:41,960 --> 00:08:44,910
laying down the framework for
years and years of discussion

185
00:08:44,910 --> 00:08:46,970
about trust and security, was this.

186
00:08:46,970 --> 00:08:50,410
To what extent should one trust a
statement that a program-- a piece

187
00:08:50,410 --> 00:08:53,010
of software-- is free of Trojan horses?

188
00:08:53,010 --> 00:08:56,500
Perhaps it is more important to trust
the people who wrote the software.

189
00:08:56,500 --> 00:08:58,650
>> And in fact, we've linked
to the talk that he

190
00:08:58,650 --> 00:09:02,400
gave when accepting this award
in the '80s on CS50's website

191
00:09:02,400 --> 00:09:04,030
under the Lectures page for today.

192
00:09:04,030 --> 00:09:06,071
Because what you'll see
is that he actually gives

193
00:09:06,071 --> 00:09:09,430
a fairly simple example of how even
a compiler like Clang or whatever

194
00:09:09,430 --> 00:09:13,950
compilers others have used in past,
what if embedded in the compiler we

195
00:09:13,950 --> 00:09:18,190
ourselves are using is a little if
condition that essentially says,

196
00:09:18,190 --> 00:09:22,360
if you notice that this code is using
the GetString function or the GetInt

197
00:09:22,360 --> 00:09:26,600
function, go ahead and insert
a back door or a Trojan horse

198
00:09:26,600 --> 00:09:29,340
such that that program
now has some zeros

199
00:09:29,340 --> 00:09:30,930
and ones that do something malicious.

200
00:09:30,930 --> 00:09:33,080
Logging all of your
keystrokes, uploading that data

201
00:09:33,080 --> 00:09:35,100
to some server, or really anything.

202
00:09:35,100 --> 00:09:37,290
>> And what Ken Thompson
goes on to do in his talk

203
00:09:37,290 --> 00:09:40,580
is to demonstrate that even if
you have access to the source

204
00:09:40,580 --> 00:09:43,794
code of a compiler that
maliciously might be doing this,

205
00:09:43,794 --> 00:09:46,210
it doesn't matter because
there's this chicken and the egg

206
00:09:46,210 --> 00:09:49,500
reality of the past many
years whereby compilers

207
00:09:49,500 --> 00:09:51,960
are used to compile themselves.

208
00:09:51,960 --> 00:09:55,440
In other words, way back when someone
had to have written the first compiler.

209
00:09:55,440 --> 00:09:59,060
And thereafter, any time they've updated
a compiler by changing its source code,

210
00:09:59,060 --> 00:10:02,020
adding features and recompiling it
for people like us to use, well,

211
00:10:02,020 --> 00:10:04,270
they're using the old
version of the compiler

212
00:10:04,270 --> 00:10:06,370
to compile the new
version of the compiler.

213
00:10:06,370 --> 00:10:08,370
And if you take a look
at the talk that he gave,

214
00:10:08,370 --> 00:10:10,970
you'll see that because
of that circularity,

215
00:10:10,970 --> 00:10:14,330
you can actually have bugs or
Trojan horses embedded in software

216
00:10:14,330 --> 00:10:14,990
we're using.

217
00:10:14,990 --> 00:10:18,010
And even if you look at the
source code for those programs,

218
00:10:18,010 --> 00:10:21,550
it might not even be evident
because the trickery is actually

219
00:10:21,550 --> 00:10:24,710
in some older version of a
compiler that ever since has been

220
00:10:24,710 --> 00:10:27,340
injecting the threat into our software.

221
00:10:27,340 --> 00:10:29,740
>> Which is only to say, we
really can't and should not

222
00:10:29,740 --> 00:10:32,939
trust software running on our laptops
or phones or any number of places.

223
00:10:32,939 --> 00:10:36,230
And in fact, later in this semester when
we start talking about web programming

224
00:10:36,230 --> 00:10:38,521
and actually start building
web applications ourselves,

225
00:10:38,521 --> 00:10:40,285
we'll talk about these
threats and others.

226
00:10:40,285 --> 00:10:43,410
Now, you might have wondered and noticed
that there was a tiny little Darth

227
00:10:43,410 --> 00:10:45,842
Vader in the clips that
The Verge was showing there

228
00:10:45,842 --> 00:10:47,550
about Volkswagen. If
you've never seen, I

229
00:10:47,550 --> 00:10:49,190
thought we should lighten
the mood because this is all

230
00:10:49,190 --> 00:10:50,780
very depressing and frightening.

231
00:10:50,780 --> 00:10:52,910
I'm going to look back
at Super Bowl 2011

232
00:10:52,910 --> 00:10:55,300
when a commercial by
Volkswagen-- and this

233
00:10:55,300 --> 00:10:59,620
almost makes them likable again--
aired for the first time on TV.

234
00:10:59,620 --> 00:11:04,039
It's the 60 second clip
that I think you'll enjoy.

235
00:11:04,039 --> 00:11:04,705
[VIDEO PLAYBACK]

236
00:11:04,705 --> 00:11:08,198
[MUSIC - THEME FROM "STAR WARS"]

237
00:11:08,198 --> 00:11:35,643

238
00:11:35,643 --> 00:11:38,138
[DOG BARKS]

239
00:11:38,138 --> 00:11:50,114

240
00:11:50,114 --> 00:11:53,607
[CAR STARTS]

241
00:11:53,607 --> 00:12:04,086

242
00:12:04,086 --> 00:12:05,955
[END PLAYBACK]

243
00:12:05,955 --> 00:12:06,830
DAVID J. MALAN: Yeah.

244
00:12:06,830 --> 00:12:07,663
I was just checking.

245
00:12:07,663 --> 00:12:11,360
That car is on the list of violations.

246
00:12:11,360 --> 00:12:12,000
All right.

247
00:12:12,000 --> 00:12:14,040
So we look at some
pseudocode a moment ago.

248
00:12:14,040 --> 00:12:15,380
And here's a bigger
snippet of pseudocode code

249
00:12:15,380 --> 00:12:16,921
that we've seen a few times thus far.

250
00:12:16,921 --> 00:12:19,970
And let's use this is an opportunity
now to introduce a new programming

251
00:12:19,970 --> 00:12:23,776
technique that we did
see algorithmically

252
00:12:23,776 --> 00:12:25,400
last week when we looked at merge sort.

253
00:12:25,400 --> 00:12:28,270
But let's formalize it and see how
we might use it in actual code,

254
00:12:28,270 --> 00:12:30,350
and then we're going to use this
technique down the road most

255
00:12:30,350 --> 00:12:32,000
likely to solve certain other problems.

256
00:12:32,000 --> 00:12:35,790
>> So this was one of the first programs we
ever wrote, albeit in pseudocode code.

257
00:12:35,790 --> 00:12:37,790
And what this program
allowed us to do course

258
00:12:37,790 --> 00:12:41,510
was to find Mike Smith in a phone book.

259
00:12:41,510 --> 00:12:46,216
And notice in particular lines eight
and 11 which had this Go To statement.

260
00:12:46,216 --> 00:12:48,090
And in fact, certain
languages, C among them,

261
00:12:48,090 --> 00:12:50,006
actually do have a
statement that is literally

262
00:12:50,006 --> 00:12:52,710
go to that allows you to
jump to a specific line.

263
00:12:52,710 --> 00:12:55,470
It's generally frowned upon because
it can be very easily abused

264
00:12:55,470 --> 00:12:58,490
and you can start jumping your
program all over the place as opposed

265
00:12:58,490 --> 00:13:00,690
to using the kind of
logic and the control flow

266
00:13:00,690 --> 00:13:04,000
that we've used thus far with just
loops and conditions and the like.

267
00:13:04,000 --> 00:13:08,660
>> But we can simplify this algorithm
in pseudocode code as follows.

268
00:13:08,660 --> 00:13:11,250
Instead of this iterative
or looping approach

269
00:13:11,250 --> 00:13:14,160
where we keep going back and
back and back to line three,

270
00:13:14,160 --> 00:13:18,300
why don't we just kind of punt and more
generally say in line seven and 10,

271
00:13:18,300 --> 00:13:20,570
just replace those two
pairs of lines with,

272
00:13:20,570 --> 00:13:22,810
else if Smith is earlier
in the book we'll

273
00:13:22,810 --> 00:13:25,110
search for Mike in the
left half of the book.

274
00:13:25,110 --> 00:13:28,560
Else if Smith is later in the
book, search for Mike in the right

275
00:13:28,560 --> 00:13:29,540
half the book.

276
00:13:29,540 --> 00:13:31,180
And notice already the circularity.

277
00:13:31,180 --> 00:13:31,680
Right?

278
00:13:31,680 --> 00:13:34,250
I'm searching for Mike in
the phone book and then

279
00:13:34,250 --> 00:13:37,090
I eventually hit maybe
line seven or maybe line 10

280
00:13:37,090 --> 00:13:41,089
and my instruction to myself is search
for Mike in half of the phone book.

281
00:13:41,089 --> 00:13:42,380
Well, how do I search for Mike?

282
00:13:42,380 --> 00:13:44,213
I'm in the middle of
searching for Mike, why

283
00:13:44,213 --> 00:13:45,860
are you sort of sending me in a circle?

284
00:13:45,860 --> 00:13:49,590
But that's OK because what is
happening to the size of the problem,

285
00:13:49,590 --> 00:13:52,630
as written in line 7 and 10?

286
00:13:52,630 --> 00:13:54,989
We're not just saying search
for Mike, search for Mike.

287
00:13:54,989 --> 00:13:56,280
We're specifically saying what?

288
00:13:56,280 --> 00:13:58,694

289
00:13:58,694 --> 00:14:01,610
Search for him in the left half of
the right half which is effectively

290
00:14:01,610 --> 00:14:03,440
half the size of the problem.

291
00:14:03,440 --> 00:14:07,170
So it's OK that we're kind of
engaging in this circularity,

292
00:14:07,170 --> 00:14:09,180
this circular argument,
because at least we're

293
00:14:09,180 --> 00:14:11,090
making the problem smaller and smaller.

294
00:14:11,090 --> 00:14:14,220
And eventually we're going to reach
that so-called base case where

295
00:14:14,220 --> 00:14:16,780
we have just one page left--
as our volunteer last week

296
00:14:16,780 --> 00:14:18,684
did-- we had one page
left and then we don't

297
00:14:18,684 --> 00:14:21,600
have to keep searching for Mike Smith
because he's either on that page

298
00:14:21,600 --> 00:14:23,080
or he is not.

299
00:14:23,080 --> 00:14:27,480
>> So how can we implement this idea, this
sort of circularity in actual code?

300
00:14:27,480 --> 00:14:31,030
Well, we can leverage a technique
that's generally known as recursion.

301
00:14:31,030 --> 00:14:33,960
And we've seen this in the
pseudocode for merge sort last week.

302
00:14:33,960 --> 00:14:37,190
Recall that this was the
pseudocode for merge sort.

303
00:14:37,190 --> 00:14:40,560
It's arguably even simpler than
bubble or selection or insertion sort

304
00:14:40,560 --> 00:14:43,310
just in terms of the simplicity
with which you can express it.

305
00:14:43,310 --> 00:14:46,750
>> But that's because
we're sort of circularly

306
00:14:46,750 --> 00:14:51,350
saying, search for something
by searching for it again.

307
00:14:51,350 --> 00:14:53,960
But we're searching either on
the left half or the right half

308
00:14:53,960 --> 00:14:56,070
and then eventually we're
merging in this case.

309
00:14:56,070 --> 00:14:58,520
But here, too, with
those two sort lines,

310
00:14:58,520 --> 00:15:01,320
did we again have this
idea of recursion.

311
00:15:01,320 --> 00:15:05,350
And concretely what this means,
in the context of an algorithm,

312
00:15:05,350 --> 00:15:10,880
is that a algorithm is recursive
if it uses or calls itself.

313
00:15:10,880 --> 00:15:14,330
>> Or in terms of C, a function is
recursive-- a function called

314
00:15:14,330 --> 00:15:18,510
foo is recursive if foo,
somewhere in its source code,

315
00:15:18,510 --> 00:15:21,250
calls the function foo itself.

316
00:15:21,250 --> 00:15:25,790
And that's bad if all foo ever does
is call itself again and again.

317
00:15:25,790 --> 00:15:30,600
It's OK if foo eventually stops, as does
merge sort, by saying, wait a minute,

318
00:15:30,600 --> 00:15:32,980
if this problem is super
small, for instance,

319
00:15:32,980 --> 00:15:35,840
or I found him whom I'm
looking for, just return.

320
00:15:35,840 --> 00:15:41,000
Don't recursively, don't
cyclically call myself again.

321
00:15:41,000 --> 00:15:44,200
>> And so let's take a look at
how this might actually work.

322
00:15:44,200 --> 00:15:48,430
So I'm going to go ahead and open
up two source code examples here.

323
00:15:48,430 --> 00:15:50,321
One of which is called sigma 0.

324
00:15:50,321 --> 00:15:52,320
And this is not at all
recursive, but let's take

325
00:15:52,320 --> 00:15:53,694
a look at what this program does.

326
00:15:53,694 --> 00:15:55,737
I've stripped out all
comments from it but all

327
00:15:55,737 --> 00:15:58,070
of the source code on CS50's
website has comments if you

328
00:15:58,070 --> 00:15:59,570
want to read through it again later.

329
00:15:59,570 --> 00:16:02,010
And let's do a couple
of sanity checks here.

330
00:16:02,010 --> 00:16:06,640
>> So at the top of this code,
we have include CS50.h.

331
00:16:06,640 --> 00:16:07,650
What does this do?

332
00:16:07,650 --> 00:16:08,990
Why is it here?

333
00:16:08,990 --> 00:16:11,740
In reasonable layman's terms.

334
00:16:11,740 --> 00:16:12,424
What does it do?

335
00:16:12,424 --> 00:16:12,858
Yeah.

336
00:16:12,858 --> 00:16:14,160
>> AUDIENCE: So that GetInt function works.

337
00:16:14,160 --> 00:16:16,243
>> DAVID J. MALAN: So that
the GetInt function works.

338
00:16:16,243 --> 00:16:18,115
Because inside of this
file, CS50.h, which

339
00:16:18,115 --> 00:16:20,950
we'll see before long in
terms of its source code,

340
00:16:20,950 --> 00:16:23,270
has a bunch of functions
declared-- GetInt, GetString,

341
00:16:23,270 --> 00:16:26,950
and a bunch of others-- and unless
we actually have that Include line,

342
00:16:26,950 --> 00:16:29,320
the compiler Clang is not
going to know that it exists.

343
00:16:29,320 --> 00:16:32,400
And same goes for line
two where int is defined

344
00:16:32,400 --> 00:16:35,101
printf, which is a function
we keep using quite a bit.

345
00:16:35,101 --> 00:16:37,850
Now, line four seems a little funky
because it's just a one liner.

346
00:16:37,850 --> 00:16:41,570
It's got a semicolon, no curly
braces, no code inside of it.

347
00:16:41,570 --> 00:16:44,640
But what did we call
this thing in weeks past?

348
00:16:44,640 --> 00:16:45,140
Yeah.

349
00:16:45,140 --> 00:16:46,060
So a prototype.

350
00:16:46,060 --> 00:16:48,390
And why do we have a
prototype which seems

351
00:16:48,390 --> 00:16:51,050
to be a little redundant
typically because we usually

352
00:16:51,050 --> 00:16:53,474
see the function again
later in the file, right?

353
00:16:53,474 --> 00:16:56,390
So why do we have-- you're just
scratching your head but I'll take it.

354
00:16:56,390 --> 00:16:57,302
Yeah.

355
00:16:57,302 --> 00:17:00,000
>> AUDIENCE: [INAUDIBLE]
function after the main.

356
00:17:00,000 --> 00:17:01,000
DAVID J. MALAN: Exactly.

357
00:17:01,000 --> 00:17:04,089
So that the compiler knows you
will eventually define or implement

358
00:17:04,089 --> 00:17:06,579
that function after main, presumably.

359
00:17:06,579 --> 00:17:08,462
So Clang and most
compilers are kind of dumb

360
00:17:08,462 --> 00:17:10,510
and they'll only know
what you tell them.

361
00:17:10,510 --> 00:17:12,569
And if you want to use
a function called sigma,

362
00:17:12,569 --> 00:17:15,710
you better teach the compiler
that it exists in advance.

363
00:17:15,710 --> 00:17:17,970
>> Now, main itself, even
though it's a bunch of lines,

364
00:17:17,970 --> 00:17:19,839
is pretty familiar hopefully by now.

365
00:17:19,839 --> 00:17:21,942
It's got a do while loop
whose purpose in life

366
00:17:21,942 --> 00:17:24,400
here apparently is to get a
positive integer from the user.

367
00:17:24,400 --> 00:17:27,349
And just keep pestering him
or her until they cooperate.

368
00:17:27,349 --> 00:17:30,670
Then in line 16 I have
an interesting call.

369
00:17:30,670 --> 00:17:31,570
IntAnswer.

370
00:17:31,570 --> 00:17:33,710
Which on the left hand
side gives me an Int

371
00:17:33,710 --> 00:17:36,650
which can store-- called Answer--
which is going to store, apparently,

372
00:17:36,650 --> 00:17:39,090
the return value of sigma.

373
00:17:39,090 --> 00:17:41,840
So sigma is just an
arbitrary but meaningful name

374
00:17:41,840 --> 00:17:44,500
that I've given to a function
whose purpose in life

375
00:17:44,500 --> 00:17:47,680
is to take one argument--
we'll call it N in this case--

376
00:17:47,680 --> 00:17:52,280
and just to take the sum of that number
plus every positive number that's

377
00:17:52,280 --> 00:17:53,200
smaller than it.

378
00:17:53,200 --> 00:17:58,140
>> So if I pass in the number 2 to
sigma, I want to add 2 plus 1

379
00:17:58,140 --> 00:18:00,240
plus 0-- not 0-- so that gives me 3.

380
00:18:00,240 --> 00:18:05,320
If I pass in 3 to sigma, I want to
have 3 plus 2 plus 1, which gives me 6.

381
00:18:05,320 --> 00:18:05,900
And so forth.

382
00:18:05,900 --> 00:18:09,750
So it just adds up all the
numbers less than or equal to it.

383
00:18:09,750 --> 00:18:12,040
>> Now, down here I'm just going
to print out the answer.

384
00:18:12,040 --> 00:18:17,330
So as a quick sanity check, let's
make sigma 0-- dot slash sigma 0--

385
00:18:17,330 --> 00:18:18,690
and let me type in 2.

386
00:18:18,690 --> 00:18:19,960
And I indeed get 3.

387
00:18:19,960 --> 00:18:21,240
Let me type in 3.

388
00:18:21,240 --> 00:18:22,860
I indeed get 6.

389
00:18:22,860 --> 00:18:27,636
And if anyone can do the math quickly,
if I do 50 what am I going get?

390
00:18:27,636 --> 00:18:29,839
>> AUDIENCE: [INAUDIBLE].

391
00:18:29,839 --> 00:18:30,880
DAVID J. MALAN: Well, no.

392
00:18:30,880 --> 00:18:33,340
But 1,275 which is pretty close.

393
00:18:33,340 --> 00:18:38,850
So this is the result of doing 50
plus 49 plus 48 plus 47 plus 46

394
00:18:38,850 --> 00:18:40,349
all the way down to 1.

395
00:18:40,349 --> 00:18:41,390
So that's all sigma does.

396
00:18:41,390 --> 00:18:43,350
But let's see how we've
implemented it now.

397
00:18:43,350 --> 00:18:45,790
So down here is the function itself.

398
00:18:45,790 --> 00:18:49,000
And this doesn't seem to have
anything to do with recursion yet.

399
00:18:49,000 --> 00:18:51,070
In fact, we're using an
old school technique.

400
00:18:51,070 --> 00:18:56,680
I'm initializing a variable called sum
to zero, then I have a foreloop here,

401
00:18:56,680 --> 00:19:00,790
and I'm declaring an Int called
I, setting it equal to 1--

402
00:19:00,790 --> 00:19:04,080
though I could set it equal to
zero, but since I'm doing addition,

403
00:19:04,080 --> 00:19:05,340
who cares if it's zero or one.

404
00:19:05,340 --> 00:19:06,660
It's going to have no effect.

405
00:19:06,660 --> 00:19:10,110
>> So I'm iterating so long as I is
less than or equal to m, which

406
00:19:10,110 --> 00:19:11,671
is the argument that was passed in.

407
00:19:11,671 --> 00:19:13,670
And then I just keep
incrementing I. And insight

408
00:19:13,670 --> 00:19:20,010
of the loop all I'm doing is doing sum
plus equals I. And that's deliberate.

409
00:19:20,010 --> 00:19:22,326
I don't want to do, in this
case, like sum plus plus.

410
00:19:22,326 --> 00:19:24,790
I want to actually add
the current value of I

411
00:19:24,790 --> 00:19:28,190
which keeps getting bigger and bigger
and bigger to the running tally.

412
00:19:28,190 --> 00:19:30,210
>> And then I return sum.

413
00:19:30,210 --> 00:19:33,850
And so answer gets the value sum.

414
00:19:33,850 --> 00:19:35,282
And then I print it out.

415
00:19:35,282 --> 00:19:37,740
So there's an opportunity here,
though, to kind of simplify

416
00:19:37,740 --> 00:19:41,260
this code conceptually
and the kind of blow one's

417
00:19:41,260 --> 00:19:43,250
mind in terms of the
simplicity even though it

418
00:19:43,250 --> 00:19:45,700
takes a while to sort
of appreciate why this

419
00:19:45,700 --> 00:19:47,330
is powerful in these small examples.

420
00:19:47,330 --> 00:19:50,380
Here is sigma one-- so the
second version of this code.

421
00:19:50,380 --> 00:19:55,290
Everything up top is identical so
that same story applies as before.

422
00:19:55,290 --> 00:19:59,220
But now let's look at the
implementation of sigma which

423
00:19:59,220 --> 00:20:05,040
I've whittled down to just these
lines-- four lines of code, really,

424
00:20:05,040 --> 00:20:06,980
plus some curly braces and white space.

425
00:20:06,980 --> 00:20:07,930
>> But what am I doing?

426
00:20:07,930 --> 00:20:11,050
If m is less than or equal to
zero, I need to kind of handle

427
00:20:11,050 --> 00:20:12,490
that super simple case.

428
00:20:12,490 --> 00:20:15,450
And if you hand me zero or anything
negative which is just weird,

429
00:20:15,450 --> 00:20:17,909
I'm just going to arbitrarily
but consistently return zero.

430
00:20:17,909 --> 00:20:20,200
I don't want this thing to
get into some weird infinite

431
00:20:20,200 --> 00:20:21,810
loop because of a negative value.

432
00:20:21,810 --> 00:20:25,070
So I'm just saying, if you give me
zero or less, I'm returning zero.

433
00:20:25,070 --> 00:20:28,220
>> But that's good because that's
that single page of the phone book

434
00:20:28,220 --> 00:20:28,790
that's left.

435
00:20:28,790 --> 00:20:32,660
I'm biting off a very specific problem
and not calling something recursively.

436
00:20:32,660 --> 00:20:36,580
But in line 31, what
do I seem to be doing?

437
00:20:36,580 --> 00:20:39,780
The parentheses are just keeping
things, hopefully, a little clearer.

438
00:20:39,780 --> 00:20:42,110
But all I'm doing is I'm
returning m-- whatever

439
00:20:42,110 --> 00:20:45,790
you hand me-- plus the
value of m-- sorry,

440
00:20:45,790 --> 00:20:49,052
plus the value of sigma of m minus 1.

441
00:20:49,052 --> 00:20:50,010
So what does this mean?

442
00:20:50,010 --> 00:20:53,965
If you give me the number 3 as input,
the answer I want to get ultimately

443
00:20:53,965 --> 00:20:57,307
is 6 because 3 plus 2 plus 1 gives me 6.

444
00:20:57,307 --> 00:20:59,390
But how do I think about
how this code is running?

445
00:20:59,390 --> 00:21:03,070
The first time I call sigma
and I pass in the value 3,

446
00:21:03,070 --> 00:21:07,960
that's like saying on a piece
of paper, here's the value 3

447
00:21:07,960 --> 00:21:09,920
and I've been passed this as sigma.

448
00:21:09,920 --> 00:21:13,090
3 is obviously not less than 0 so
the IF condition doesn't apply.

449
00:21:13,090 --> 00:21:14,020
The ELSE does.

450
00:21:14,020 --> 00:21:14,990
So what do I do?

451
00:21:14,990 --> 00:21:19,902
I want to return m, which is
3, plus sigma of m minus 1.

452
00:21:19,902 --> 00:21:21,110
So let me keep track of this.

453
00:21:21,110 --> 00:21:22,710
I'm going to put this
piece of paper down.

454
00:21:22,710 --> 00:21:24,668
And what value, to be
clear, am I going to pass

455
00:21:24,668 --> 00:21:26,540
into sigma at this point in the story?

456
00:21:26,540 --> 00:21:28,080
What number?

457
00:21:28,080 --> 00:21:28,610
2, right?

458
00:21:28,610 --> 00:21:29,670
3 minus 1 is 2.

459
00:21:29,670 --> 00:21:32,000
So I just need a little
scrap of paper here.

460
00:21:32,000 --> 00:21:33,931
So now sigma is getting called again.

461
00:21:33,931 --> 00:21:35,930
And I've deliberately put
this down because it's

462
00:21:35,930 --> 00:21:38,070
kind of like pausing
that version of the story

463
00:21:38,070 --> 00:21:40,720
because now I'm focused
on signal of m minus 1.

464
00:21:40,720 --> 00:21:42,660
So m was 3, m minus 1 is 2.

465
00:21:42,660 --> 00:21:45,110
So here is 2 that I've been passed.

466
00:21:45,110 --> 00:21:48,510
2 is obviously not less than
0 so that case doesn't apply.

467
00:21:48,510 --> 00:21:53,445
Else I return m, which is this
thing, plus sigma of what value?

468
00:21:53,445 --> 00:21:56,160

469
00:21:56,160 --> 00:21:59,650
So if sigma of 1-- because m is
right now 2 so 2 minus 1 is 1.

470
00:21:59,650 --> 00:22:01,950
So now I have just the value 1.

471
00:22:01,950 --> 00:22:04,810
I'm passing just the number
1 to the function sigma--

472
00:22:04,810 --> 00:22:09,120
or myself here-- so 1 is obviously not
less than zero, still doesn't apply.

473
00:22:09,120 --> 00:22:12,970
>> Else return 1 plus sigma of what?

474
00:22:12,970 --> 00:22:13,470
0.

475
00:22:13,470 --> 00:22:14,678
So let me just remember that.

476
00:22:14,678 --> 00:22:15,920
I'll get back to that later.

477
00:22:15,920 --> 00:22:18,060
Now I'm going to go ahead and jot
down the number 0 because that's

478
00:22:18,060 --> 00:22:19,470
my argument or parameter.

479
00:22:19,470 --> 00:22:22,400
I'm passed the number 0
and finally this process

480
00:22:22,400 --> 00:22:25,760
of just repeating myself ad
nauseum does cease because what

481
00:22:25,760 --> 00:22:28,820
do I immediately do once I see this 0?

482
00:22:28,820 --> 00:22:29,790
I return zero.

483
00:22:29,790 --> 00:22:31,790
So now you have to rewind the story.

484
00:22:31,790 --> 00:22:34,430
>> If I now go backwards in time,
what was the most recent thing

485
00:22:34,430 --> 00:22:36,670
I did if you were literally
rewinding a video?

486
00:22:36,670 --> 00:22:41,630
I'm going to pick up the most recent
1 and that gives me 1 plus 0 is 1.

487
00:22:41,630 --> 00:22:44,100
If I keep rewinding the
story, that's going to give me

488
00:22:44,100 --> 00:22:46,880
2 plus this running value, which is 1.

489
00:22:46,880 --> 00:22:47,789
So that's 3.

490
00:22:47,789 --> 00:22:49,330
And then I'm going to keep rewinding.

491
00:22:49,330 --> 00:22:54,220
When I first put down the number
3-- so 3 plus 3 gives me 6.

492
00:22:54,220 --> 00:22:57,272
>> And now, if you've rewound
the video up until this point,

493
00:22:57,272 --> 00:22:58,980
this was the very
first question I asked.

494
00:22:58,980 --> 00:23:01,450
When passed 3, what is sigma of 3?

495
00:23:01,450 --> 00:23:04,204
It's indeed 6, the sum of
all these pieces of paper.

496
00:23:04,204 --> 00:23:07,120
So if that takes a little while to
wrap your mind around, that's fine.

497
00:23:07,120 --> 00:23:10,700
But consider it was a little-- it
was very deliberate that I stacked

498
00:23:10,700 --> 00:23:12,990
these numbers on top of each other.

499
00:23:12,990 --> 00:23:17,440
It's kind of like having a
memory-- a record in time,

500
00:23:17,440 --> 00:23:19,940
like a scrubber in a video,
that I can indeed rewind in.

501
00:23:19,940 --> 00:23:24,350
And we're going to come back to
that metaphor in just a little bit.

502
00:23:24,350 --> 00:23:28,240
>> But first, it turns out that there's
a lot of geeks and funny people,

503
00:23:28,240 --> 00:23:29,614
I guess, at Google.

504
00:23:29,614 --> 00:23:31,530
Would someone who's very
good at Googling mind

505
00:23:31,530 --> 00:23:34,270
coming up for just a moment and
help me search for something?

506
00:23:34,270 --> 00:23:35,650
Very, very low key.

507
00:23:35,650 --> 00:23:37,870
Someone who's never
come up before, perhaps.

508
00:23:37,870 --> 00:23:38,370
OK.

509
00:23:38,370 --> 00:23:39,030
Yeah?

510
00:23:39,030 --> 00:23:39,530
Come on.

511
00:23:39,530 --> 00:23:41,410
Come on down.

512
00:23:41,410 --> 00:23:42,183
What's your name?

513
00:23:42,183 --> 00:23:42,870
>> SAM: Sam.

514
00:23:42,870 --> 00:23:44,290
>> DAVID J. MALAN: Sam, come on down.

515
00:23:44,290 --> 00:23:45,320
This is Same.

516
00:23:45,320 --> 00:23:46,280
Nice to meet you.

517
00:23:46,280 --> 00:23:46,780
Hey.

518
00:23:46,780 --> 00:23:47,580
Come on over.

519
00:23:47,580 --> 00:23:51,290
So all I need you to do, if
you could, Sam, here's Google.

520
00:23:51,290 --> 00:23:53,240
Can you search for the term recursion?

521
00:23:53,240 --> 00:23:55,770

522
00:23:55,770 --> 00:23:56,270
Don't spoil.

523
00:23:56,270 --> 00:23:59,940

524
00:23:59,940 --> 00:24:00,970
>> And now let's-- yeah.

525
00:24:00,970 --> 00:24:03,380
OK Click that.

526
00:24:03,380 --> 00:24:04,315
Better click that.

527
00:24:04,315 --> 00:24:07,020

528
00:24:07,020 --> 00:24:08,020
Ahh, get it.

529
00:24:08,020 --> 00:24:08,520
No?

530
00:24:08,520 --> 00:24:09,050
OK.

531
00:24:09,050 --> 00:24:10,430
So let's do a couple others.

532
00:24:10,430 --> 00:24:12,830
Not so much related
academically here, but have you

533
00:24:12,830 --> 00:24:14,520
ever searched Google for anagram?

534
00:24:14,520 --> 00:24:15,280
>> SAM: No.

535
00:24:15,280 --> 00:24:15,520
>> DAVID J. MALAN: OK.

536
00:24:15,520 --> 00:24:17,186
Search for anagram instead of recursion.

537
00:24:17,186 --> 00:24:22,540

538
00:24:22,540 --> 00:24:23,790
How about askew.

539
00:24:23,790 --> 00:24:25,515
You ever searched for askew?

540
00:24:25,515 --> 00:24:29,260

541
00:24:29,260 --> 00:24:32,692
Now, this one's a little hard to
see but hopefully everything's-- OK.

542
00:24:32,692 --> 00:24:34,150
It's just you and me enjoying this.

543
00:24:34,150 --> 00:24:34,690
OK.

544
00:24:34,690 --> 00:24:38,950
>> So finally, this one's--
it's a little askew.

545
00:24:38,950 --> 00:24:40,810
Now do a barrel roll.

546
00:24:40,810 --> 00:24:44,460

547
00:24:44,460 --> 00:24:45,310
Wonderful.

548
00:24:45,310 --> 00:24:45,910
All right.

549
00:24:45,910 --> 00:24:47,110
Big thank you to Sam.

550
00:24:47,110 --> 00:24:49,416
Here you go.

551
00:24:49,416 --> 00:24:50,400
Thanks.

552
00:24:50,400 --> 00:24:52,807
>> So what's going on in all
of these silly examples?

553
00:24:52,807 --> 00:24:55,640
So really, underneath the hood of
Google's millions of lines of code

554
00:24:55,640 --> 00:24:58,860
apparently is a few silly IF
conditions that are essentially

555
00:24:58,860 --> 00:25:01,160
checking if the user has
typed in this phrase,

556
00:25:01,160 --> 00:25:03,760
do something that probably took
a nontrivial amount of time

557
00:25:03,760 --> 00:25:06,080
to implement just to
be amusing in this way.

558
00:25:06,080 --> 00:25:08,430
But that's all it boils
down to underneath the hood.

559
00:25:08,430 --> 00:25:11,570
But, of course, recursion
is more of the geekier

560
00:25:11,570 --> 00:25:13,880
example among those special tricks.

561
00:25:13,880 --> 00:25:16,880
And surely there's others out there
as well that we perhaps haven't even

562
00:25:16,880 --> 00:25:18,230
discovered just yet.

563
00:25:18,230 --> 00:25:22,830
>> So take a look, or consider
now the following program,

564
00:25:22,830 --> 00:25:24,830
and certainly grab any
of these on your way out.

565
00:25:24,830 --> 00:25:28,820
I'm going to go ahead and
open up a program that's

566
00:25:28,820 --> 00:25:30,920
going to try to swap two values.

567
00:25:30,920 --> 00:25:33,210
But before we go there, let's do this.

568
00:25:33,210 --> 00:25:38,500
Could we get one more
volunteer, I think?

569
00:25:38,500 --> 00:25:40,480
Would you like to volunteer?

570
00:25:40,480 --> 00:25:40,980
No?

571
00:25:40,980 --> 00:25:41,890
Come on up.

572
00:25:41,890 --> 00:25:42,390
Come on up.

573
00:25:42,390 --> 00:25:42,890
All right.

574
00:25:42,890 --> 00:25:44,136
So your name is what?

575
00:25:44,136 --> 00:25:44,810
>> LAUREN: Lauren.

576
00:25:44,810 --> 00:25:45,768
>> DAVID J. MALAN: Lauren.

577
00:25:45,768 --> 00:25:46,890
Come on up, Lauren.

578
00:25:46,890 --> 00:25:50,140
So Lauren is being
challenged here as follows.

579
00:25:50,140 --> 00:25:52,310
Nice to meet you.

580
00:25:52,310 --> 00:25:55,730
So Lauren here has in front
of her two empty cups.

581
00:25:55,730 --> 00:25:57,570
And we have some orange
juice and some milk

582
00:25:57,570 --> 00:26:00,301
and we're going to go
ahead and do the following.

583
00:26:00,301 --> 00:26:01,550
We're just going to fill this.

584
00:26:01,550 --> 00:26:07,840
A few ounces of milk over here and let's
fill a little orange juice over here.

585
00:26:07,840 --> 00:26:11,475
>> And in front of all of
these audience members,

586
00:26:11,475 --> 00:26:13,550
swap the two values of these cups.

587
00:26:13,550 --> 00:26:16,970
Put the orange juice in the milk cup
and the milk in the orange juice cup.

588
00:26:16,970 --> 00:26:22,380

589
00:26:22,380 --> 00:26:26,150
How would you do this if you were at
home and had access to other supplies?

590
00:26:26,150 --> 00:26:27,400
LAUREN: Put it in another cup.

591
00:26:27,400 --> 00:26:28,191
DAVID J. MALAN: OK.

592
00:26:28,191 --> 00:26:31,940
So let's have a temporary
variable, if we will.

593
00:26:31,940 --> 00:26:35,871
And go ahead now and implement
this same swapping procedure.

594
00:26:35,871 --> 00:26:36,370
So, good.

595
00:26:36,370 --> 00:26:41,490
We've put OJ into the temporary
variable, milk into the OJ variable,

596
00:26:41,490 --> 00:26:44,481
and now the temporary variable
into the milk variable.

597
00:26:44,481 --> 00:26:44,980
OK.

598
00:26:44,980 --> 00:26:48,740
So very well done so far.

599
00:26:48,740 --> 00:26:50,990
So it turns out-- hold that
thought for just a moment.

600
00:26:50,990 --> 00:26:54,479
Here, to just geek it up a bit, this
would be the corresponding C code

601
00:26:54,479 --> 00:26:55,520
that we just implemented.

602
00:26:55,520 --> 00:26:58,650
We had two inputs, a and b, both of
which we'll just say for simplicity are

603
00:26:58,650 --> 00:26:59,260
int's.

604
00:26:59,260 --> 00:27:02,780
And notice here, if I want to swap
the values of two variables, a and b,

605
00:27:02,780 --> 00:27:06,890
we indeed need a middleman, a
temporary variable, a temporary cup,

606
00:27:06,890 --> 00:27:10,830
into which the pour one of the values
so that we have a placeholder for it.

607
00:27:10,830 --> 00:27:13,480
But then the code is exactly
as Lauren here implemented.

608
00:27:13,480 --> 00:27:15,500
>> Now, just to get a
little crazier, turns out

609
00:27:15,500 --> 00:27:20,930
that you can do this without
a temporary variable.

610
00:27:20,930 --> 00:27:24,870
To do this properly, though, we're going
to have to cheat with some chemistry.

611
00:27:24,870 --> 00:27:26,380
We have some extra cups here.

612
00:27:26,380 --> 00:27:29,600
So the closest thing that looks
like milk and water perhaps--

613
00:27:29,600 --> 00:27:34,090
or milk and OJ-- is we have some
water, so we'll fill this one up

614
00:27:34,090 --> 00:27:36,486
with a few ounces of clear water.

615
00:27:36,486 --> 00:27:38,332
That's probably too much.

616
00:27:38,332 --> 00:27:38,832
Yeah.

617
00:27:38,832 --> 00:27:39,934
That's definitely too much.

618
00:27:39,934 --> 00:27:40,600
Hold on one sec.

619
00:27:40,600 --> 00:27:43,520

620
00:27:43,520 --> 00:27:48,420
>> And now we have oil, which, as I recall
from middle school chemistry class,

621
00:27:48,420 --> 00:27:49,990
hopefully it doesn't mix with water.

622
00:27:49,990 --> 00:27:53,650
But it kind of sort of
looks like milk and OJ.

623
00:27:53,650 --> 00:27:55,760
So now, without using
a temporary variable,

624
00:27:55,760 --> 00:27:59,260
can you swap those two values?

625
00:27:59,260 --> 00:28:03,884
So oils goes into the water cup,
water goes into the oil cup.

626
00:28:03,884 --> 00:28:04,800
LAUREN: No other cups?

627
00:28:04,800 --> 00:28:05,940
DAVID J. MALAN: No other cups.

628
00:28:05,940 --> 00:28:07,860
And I've not actually
tested this before this year

629
00:28:07,860 --> 00:28:10,110
so I don't know if this will
actually work chemically.

630
00:28:10,110 --> 00:28:16,130

631
00:28:16,130 --> 00:28:18,650
That wasn't supposed to happen.

632
00:28:18,650 --> 00:28:19,761
Is it working?

633
00:28:19,761 --> 00:28:20,260
All right.

634
00:28:20,260 --> 00:28:20,990
So separating?

635
00:28:20,990 --> 00:28:21,490
Good.

636
00:28:21,490 --> 00:28:24,714
Now we got to get the
water into the other cup.

637
00:28:24,714 --> 00:28:27,630
Smarter chemistry concentrators could
probably do this better than me.

638
00:28:27,630 --> 00:28:28,510
>> LAUREN: The water's on the bottom.

639
00:28:28,510 --> 00:28:31,910
>> DAVID J. MALAN: The water-- that was
what's key the last time we did this.

640
00:28:31,910 --> 00:28:33,950
You have to do it in the right order.

641
00:28:33,950 --> 00:28:34,450
Yeah.

642
00:28:34,450 --> 00:28:35,270
That's-- OK.

643
00:28:35,270 --> 00:28:37,290
So now we have two cups of oil.

644
00:28:37,290 --> 00:28:37,790
OK.

645
00:28:37,790 --> 00:28:38,510
That's OK.

646
00:28:38,510 --> 00:28:40,110
But chemically if this worked than I--

647
00:28:40,110 --> 00:28:41,200
>> LAUREN: This is water.

648
00:28:41,200 --> 00:28:41,930
>> DAVID J. MALAN: That's mostly water.

649
00:28:41,930 --> 00:28:42,430
All right.

650
00:28:42,430 --> 00:28:44,210
But that's still the same cup as before.

651
00:28:44,210 --> 00:28:47,570
So pour it-- try it over there.

652
00:28:47,570 --> 00:28:49,300
OK.

653
00:28:49,300 --> 00:28:51,010
This is a good use of class time today.

654
00:28:51,010 --> 00:28:51,510
OK.

655
00:28:51,510 --> 00:28:53,890
So now we-- nice.

656
00:28:53,890 --> 00:28:55,460
Sort of.

657
00:28:55,460 --> 00:28:55,960
All right.

658
00:28:55,960 --> 00:28:56,690
So very good.

659
00:28:56,690 --> 00:29:00,006
Thank you to Lauren.

660
00:29:00,006 --> 00:29:01,950
Very well done.

661
00:29:01,950 --> 00:29:04,570
>> So just to blow your minds,
and this is perhaps something

662
00:29:04,570 --> 00:29:08,660
to play with if you like in CS50 ID,
you can, in fact, swap two variables

663
00:29:08,660 --> 00:29:11,470
without using a temporary integer.

664
00:29:11,470 --> 00:29:13,060
And this is the corresponding C code.

665
00:29:13,060 --> 00:29:16,110
And if you recall from last
Wednesday, we introduced, if briefly,

666
00:29:16,110 --> 00:29:19,720
some new operators in C. And does
anyone recall what the little carrot

667
00:29:19,720 --> 00:29:23,660
symbol is, that little triangular
symbol from the keyboard represents?

668
00:29:23,660 --> 00:29:26,003
What bitwise operator?

669
00:29:26,003 --> 00:29:26,770
>> AUDIENCE: EXOR.

670
00:29:26,770 --> 00:29:27,645
>> DAVID J. MALAN: EXOR.

671
00:29:27,645 --> 00:29:28,560
Exclusive Or.

672
00:29:28,560 --> 00:29:32,920
So if you want, just for fun at
home, to give a and b two arbitrary

673
00:29:32,920 --> 00:29:36,072
values like any eight-- and I
would choose an eight bit value.

674
00:29:36,072 --> 00:29:38,530
If you do this with 32 bits,
you'll very quickly get bored.

675
00:29:38,530 --> 00:29:42,150
But just give a an eight bit
value that's whatever, one or two,

676
00:29:42,150 --> 00:29:43,790
and give b a similar value.

677
00:29:43,790 --> 00:29:46,810
And then using the definition
of XOR from last Wednesday,

678
00:29:46,810 --> 00:29:52,560
apply that bit by bit, each of
those eight bits in each of a and b,

679
00:29:52,560 --> 00:29:54,980
and then do it exactly per this code.

680
00:29:54,980 --> 00:29:58,170
And it's not incorrect what
you see here on the screen.

681
00:29:58,170 --> 00:30:02,100
It indeed boils down
to three XOR operations

682
00:30:02,100 --> 00:30:05,910
and somehow magically a and
b will exchange positions

683
00:30:05,910 --> 00:30:08,010
without losing any information.

684
00:30:08,010 --> 00:30:11,580
>> So the oil and water trick is the
closest real world incarnation

685
00:30:11,580 --> 00:30:12,980
I could think of to mimic that.

686
00:30:12,980 --> 00:30:15,950
But it's surely easier to
use a temporary variable,

687
00:30:15,950 --> 00:30:16,920
as in this case here.

688
00:30:16,920 --> 00:30:21,190
And this too is an opportunity say,
too, this kind of micro optimization,

689
00:30:21,190 --> 00:30:23,590
as a computer scientist
would say, while kind of fun

690
00:30:23,590 --> 00:30:27,060
to brag about how you did this without
like swapping with an extra variable,

691
00:30:27,060 --> 00:30:28,640
it's not all that compelling.

692
00:30:28,640 --> 00:30:31,619
Because to save 32 bits, as
in the case of an actual int,

693
00:30:31,619 --> 00:30:33,410
isn't all that compelling
on a system where

694
00:30:33,410 --> 00:30:36,722
you might be using tens of megabytes
or even more such memory these days.

695
00:30:36,722 --> 00:30:38,680
And in fact, when we get
to a later problem set

696
00:30:38,680 --> 00:30:41,010
and you implement spell
checker and you'll

697
00:30:41,010 --> 00:30:43,550
be challenged to do so with
this as little RAM and as little

698
00:30:43,550 --> 00:30:46,820
time as possible on the
computer-- you still

699
00:30:46,820 --> 00:30:50,160
have a week to implement
it-- you'll have-- you'll be

700
00:30:50,160 --> 00:30:51,799
challenged to minimize those resources.

701
00:30:51,799 --> 00:30:53,840
And that's really the only
occasion this semester

702
00:30:53,840 --> 00:30:57,940
where you'll be encouraged to shave
off even the finest performance

703
00:30:57,940 --> 00:30:59,340
costs otherwise.

704
00:30:59,340 --> 00:31:02,200
>> So what-- how can we
see this in actual code?

705
00:31:02,200 --> 00:31:04,530
Let me go ahead now
and open up an example

706
00:31:04,530 --> 00:31:07,700
that deliberately is called
No Swap because it does not

707
00:31:07,700 --> 00:31:10,670
in fact swap the variables
as you actually might expect.

708
00:31:10,670 --> 00:31:12,260
So let's take a look.

709
00:31:12,260 --> 00:31:17,050
Here's a program that has no CS50
library going on, just standard I/O.

710
00:31:17,050 --> 00:31:19,560
Now we have a prototype
for swap up top which just

711
00:31:19,560 --> 00:31:21,540
means it's got to be defined later.

712
00:31:21,540 --> 00:31:22,550
And here's main.

713
00:31:22,550 --> 00:31:26,000
>> I arbitrarily assigned x and y,
respectively, the values one and two

714
00:31:26,000 --> 00:31:28,590
just because they're small
and easy to think about.

715
00:31:28,590 --> 00:31:32,280
And then I just have a bunch of printfs
where I have a sanity check. x is 1

716
00:31:32,280 --> 00:31:35,110
and y is 2 is presumably
what those printfs will say.

717
00:31:35,110 --> 00:31:36,530
So no magic thus far.

718
00:31:36,530 --> 00:31:40,100
>> Then I'm going to claim with
print def, swapping dot dot dot.

719
00:31:40,100 --> 00:31:43,730
I'm going to call the swap
function, passing in x and y.

720
00:31:43,730 --> 00:31:47,350
And let's assume for now that
swap is implemented exactly

721
00:31:47,350 --> 00:31:49,930
as it was a moment ago
with a temporary variable.

722
00:31:49,930 --> 00:31:52,670
And so I claim boldly, swapped.

723
00:31:52,670 --> 00:31:55,429
x is now this and y is now that.

724
00:31:55,429 --> 00:31:57,220
But the file, of course,
is called No Swap.

725
00:31:57,220 --> 00:31:58,678
So let's actually see what happens.

726
00:31:58,678 --> 00:32:04,450
If I compile no swap and then
do ./noswap , x is 1, y is 2.

727
00:32:04,450 --> 00:32:05,770
Swapping swapped.

728
00:32:05,770 --> 00:32:07,200
x is 1, y is 2.

729
00:32:07,200 --> 00:32:11,980
So it actually seems to be flawed even
though swap-- let's scroll down now--

730
00:32:11,980 --> 00:32:16,542
is implemented exactly per the
code I proposed a moment ago.

731
00:32:16,542 --> 00:32:19,000
So we're not going to get fancy
with the XOR stuff for now.

732
00:32:19,000 --> 00:32:21,890
This, too, should work just
like with the milk and OJ,

733
00:32:21,890 --> 00:32:25,820
but it doesn't seem to be working.

734
00:32:25,820 --> 00:32:27,180
>> So let's do this again.

735
00:32:27,180 --> 00:32:29,310
Maybe I just wasn't running it right.

736
00:32:29,310 --> 00:32:32,010
So let's run No Swap again.

737
00:32:32,010 --> 00:32:32,900
Maybe I-- no.

738
00:32:32,900 --> 00:32:34,400
So it's just not working.

739
00:32:34,400 --> 00:32:36,060
So let's do a little sanity check.

740
00:32:36,060 --> 00:32:39,690
Let me go ahead here in Swap
and just add, wait a minute,

741
00:32:39,690 --> 00:32:43,856
a is %i/n and let's
plug-in the value of a.

742
00:32:43,856 --> 00:32:45,730
Because I really want
to see what's going on.

743
00:32:45,730 --> 00:32:47,570
And indeed, this is
a debugging technique

744
00:32:47,570 --> 00:32:50,028
that you might be using in
office hours or at home already,

745
00:32:50,028 --> 00:32:53,560
akin to the first half of Dan
Armendariz's video in PSET3

746
00:32:53,560 --> 00:32:56,870
wherein we introduced print def as
a recommended technique, at least

747
00:32:56,870 --> 00:32:58,080
for simple cases.

748
00:32:58,080 --> 00:33:01,720
Let me go ahead and run make
no swap again, ./noswap.

749
00:33:01,720 --> 00:33:04,370

750
00:33:04,370 --> 00:33:05,840
>> Interesting.

751
00:33:05,840 --> 00:33:11,670
So notice what seems to be true. x
is 1, y is 2, but a is 2 when b is 1.

752
00:33:11,670 --> 00:33:16,790
So those two somehow got swapped
but x and y are not getting swapped.

753
00:33:16,790 --> 00:33:21,090
So to be clear, what's happening
is, up here I have x and y

754
00:33:21,090 --> 00:33:25,380
and those are variables local in the
scope of main, I'm passing in x and y

755
00:33:25,380 --> 00:33:26,170
to swap.

756
00:33:26,170 --> 00:33:29,080
Now, swap, as a separate function,
is free to call its arguments

757
00:33:29,080 --> 00:33:30,590
or its parameters anything it wants.

758
00:33:30,590 --> 00:33:33,280
Foo or bar or x or y or a or b.

759
00:33:33,280 --> 00:33:36,870
Just to make clear that they're
not identical to x and y per se,

760
00:33:36,870 --> 00:33:38,020
I've said a and b.

761
00:33:38,020 --> 00:33:40,040
But we could call them anything we want.

762
00:33:40,040 --> 00:33:43,960
>> And so it looks like
swap is being passed

763
00:33:43,960 --> 00:33:48,980
x-- AKA a-- and it's
being passed y-- AKA b.

764
00:33:48,980 --> 00:33:51,900
Somehow these three lines are
swapping those values exactly

765
00:33:51,900 --> 00:33:53,510
as Lauren did with the milk and OJ.

766
00:33:53,510 --> 00:33:56,010
But when we print out
the values, a and b

767
00:33:56,010 --> 00:34:01,340
are indeed swap but x and
y have no change to them.

768
00:34:01,340 --> 00:34:03,150
Recall that x and y are up here.

769
00:34:03,150 --> 00:34:05,320
>> So we can see this via
another technique as well.

770
00:34:05,320 --> 00:34:08,110
And this too is a technique
embedded in problem set three.

771
00:34:08,110 --> 00:34:10,780
Let's go ahead and do this in
CS50 ID if you haven't already.

772
00:34:10,780 --> 00:34:13,730
On the right hand side we
have this Debugger tab.

773
00:34:13,730 --> 00:34:16,159
And if you open this up,
there's some arcane information

774
00:34:16,159 --> 00:34:17,530
that's thrown at you initially.

775
00:34:17,530 --> 00:34:19,310
But let's tease this apart real fast.

776
00:34:19,310 --> 00:34:21,620
>> So one, you see local variables.

777
00:34:21,620 --> 00:34:26,230
Turns out that build into CS50 IDE, and
a lot of programming environments more

778
00:34:26,230 --> 00:34:28,060
generally, is a debugger.

779
00:34:28,060 --> 00:34:31,340
A tool that allows you to visually see
what's going on inside of your program

780
00:34:31,340 --> 00:34:34,380
without having to resort to adding
printfs and compiling and running

781
00:34:34,380 --> 00:34:37,588
and adding printf's and compiling and
running, which already, in office hours

782
00:34:37,588 --> 00:34:40,070
or home, is probably
getting pretty tedious.

783
00:34:40,070 --> 00:34:43,090
>> So here, in just a moment, we're
going to to see in real time

784
00:34:43,090 --> 00:34:44,760
the values of our local variables.

785
00:34:44,760 --> 00:34:47,880
We're also going to be able to set
what are called breakpoints which

786
00:34:47,880 --> 00:34:52,570
are opportunities in my program to pause
execution at a specific line of code

787
00:34:52,570 --> 00:34:53,710
that I'm curious about.

788
00:34:53,710 --> 00:34:54,210
Right?

789
00:34:54,210 --> 00:34:55,969
These programs run in a split second.

790
00:34:55,969 --> 00:35:00,450
It's kind of nice for us slower humans
to be able to pause, take a moment, see

791
00:35:00,450 --> 00:35:02,380
what's going on around
a certain line of code

792
00:35:02,380 --> 00:35:05,050
without the program plowing
through it and finishing entirely.

793
00:35:05,050 --> 00:35:08,510
So a breakpoints going to allow us to
break and pause at a certain point.

794
00:35:08,510 --> 00:35:12,990
>> Call stack is a fancy way of
saying what functions are currently

795
00:35:12,990 --> 00:35:14,140
being called at the moment.

796
00:35:14,140 --> 00:35:15,370
Main is always called first.

797
00:35:15,370 --> 00:35:17,230
But if Main calls a
function called Swap,

798
00:35:17,230 --> 00:35:20,470
we're actually going to see this
tower of functions that have been

799
00:35:20,470 --> 00:35:22,400
called in reverse chronological order.

800
00:35:22,400 --> 00:35:23,310
So let's see that.

801
00:35:23,310 --> 00:35:24,327
>> I'm going to zoom out.

802
00:35:24,327 --> 00:35:25,660
I'm going to go back to my code.

803
00:35:25,660 --> 00:35:27,540
And just because I want
to be pedantic here,

804
00:35:27,540 --> 00:35:31,100
I'm going to go ahead and click
just to the left of line five.

805
00:35:31,100 --> 00:35:32,830
And that creates a red dot.

806
00:35:32,830 --> 00:35:36,200
And notice on the right hand side
that the debugger knows, hey,

807
00:35:36,200 --> 00:35:41,020
I just said a breakpoint at
noswap.c line five, specifically

808
00:35:41,020 --> 00:35:42,480
at this line of code.

809
00:35:42,480 --> 00:35:45,090
So the debugger knows that I
have requested that the next time

810
00:35:45,090 --> 00:35:48,530
I run my program it pause
execution there rather than just

811
00:35:48,530 --> 00:35:50,390
running the whole thing super fast.

812
00:35:50,390 --> 00:35:53,889
>> So now I'm going to click the Debug
button at the very top of the IDE

813
00:35:53,889 --> 00:35:55,430
and that's going to do the following.

814
00:35:55,430 --> 00:36:00,680
It's going to open an initially somewhat
scary looking second terminal window--

815
00:36:00,680 --> 00:36:02,679
remote debugging from
host such and such--

816
00:36:02,679 --> 00:36:04,970
and we'll come back to what
all that means before long.

817
00:36:04,970 --> 00:36:09,020
But what's important for now
is that that red dot was hit,

818
00:36:09,020 --> 00:36:11,735
the debugger has deliberately
paused execution--

819
00:36:11,735 --> 00:36:15,560
not on that line per se but on the first
line of actual code in that function.

820
00:36:15,560 --> 00:36:18,040
And that's why line seven is
now highlighted in yellow.

821
00:36:18,040 --> 00:36:20,550
>> And now let's take a look
at the right hand side.

822
00:36:20,550 --> 00:36:27,300
It looks like, by default,
nicely enough, x has what value?

823
00:36:27,300 --> 00:36:27,860
0.

824
00:36:27,860 --> 00:36:29,750
And y has what value?

825
00:36:29,750 --> 00:36:30,410
Zero.

826
00:36:30,410 --> 00:36:35,540
And that's to be expected in the sense
that x and y-- that yellow line-- has

827
00:36:35,540 --> 00:36:36,770
not executed yet.

828
00:36:36,770 --> 00:36:38,510
So x should not have the value 1.

829
00:36:38,510 --> 00:36:41,470
It might have any other value,
a so-called garbage value.

830
00:36:41,470 --> 00:36:44,320
And we got lucky in that it's
zero at this point, essentially.

831
00:36:44,320 --> 00:36:46,400
>> So now there's only a few
buttons we need to care

832
00:36:46,400 --> 00:36:48,100
about when debugging in this way.

833
00:36:48,100 --> 00:36:49,970
Notice here, we have a Play button.

834
00:36:49,970 --> 00:36:51,877
And if we play or hit
resume, that's just

835
00:36:51,877 --> 00:36:53,710
going to run through
the rest of the program

836
00:36:53,710 --> 00:36:55,300
or until it hits another breakpoint.

837
00:36:55,300 --> 00:36:56,910
But I've not set any other
breakpoints so it's just

838
00:36:56,910 --> 00:36:58,118
going to run through the end.

839
00:36:58,118 --> 00:37:00,280
That kind of defeats the
purpose of poking around.

840
00:37:00,280 --> 00:37:03,290
>> So instead, I care about
these icons to the right.

841
00:37:03,290 --> 00:37:05,360
And if I hover over
them, as you should too,

842
00:37:05,360 --> 00:37:07,450
you'll see little tips-- tool tips.

843
00:37:07,450 --> 00:37:09,020
This one is step over.

844
00:37:09,020 --> 00:37:11,290
Now that doesn't mean skip
the following line of code.

845
00:37:11,290 --> 00:37:14,840
That just means execute it and
move to the next, move to the next,

846
00:37:14,840 --> 00:37:15,580
move to the next.

847
00:37:15,580 --> 00:37:17,610
In other words, via
that button, can I walk

848
00:37:17,610 --> 00:37:20,390
through my code one step at a time.

849
00:37:20,390 --> 00:37:21,914
Line by line, literally.

850
00:37:21,914 --> 00:37:23,830
Now, to the right of
that, there's another one

851
00:37:23,830 --> 00:37:25,163
that we'll see in just a moment.

852
00:37:25,163 --> 00:37:27,820
This is the so-called
Step Into icon that's

853
00:37:27,820 --> 00:37:30,300
going to allow me dive
into another function.

854
00:37:30,300 --> 00:37:31,800
But let's see this in just a moment.

855
00:37:31,800 --> 00:37:33,280
So I'm going to click step over.

856
00:37:33,280 --> 00:37:35,820
And now notice, as I click
this button at top right,

857
00:37:35,820 --> 00:37:41,260
keep your eyes roughly under Local
Variables and see what happens to x.

858
00:37:41,260 --> 00:37:44,115
x is now 1 because the
yellow line has now executed

859
00:37:44,115 --> 00:37:45,840
and we've moved on to line 8.

860
00:37:45,840 --> 00:37:49,840
And in just a moment y
should hopefully become 2.

861
00:37:49,840 --> 00:37:52,330
>> Now, nothing that interesting
happens for a bit.

862
00:37:52,330 --> 00:37:53,390
All this is is printf.

863
00:37:53,390 --> 00:37:58,010
And notice, in my secondary terminal
window, I see the output of print def.

864
00:37:58,010 --> 00:38:01,080
And now I have to make a
decision as the programmer.

865
00:38:01,080 --> 00:38:04,360
I can step over this line of
code, executing it but not

866
00:38:04,360 --> 00:38:06,220
getting curious about what's inside.

867
00:38:06,220 --> 00:38:11,130
Or I can actually step into it
and go inside of Swap itself.

868
00:38:11,130 --> 00:38:12,340
So let's do the latter.

869
00:38:12,340 --> 00:38:15,550
>> Let me go ahead and click
not Step Over but Step Into.

870
00:38:15,550 --> 00:38:17,300
Notice, all of a sudden
the window changes

871
00:38:17,300 --> 00:38:19,330
to highlight the first
line of code in Swap.

872
00:38:19,330 --> 00:38:20,710
That's line 21.

873
00:38:20,710 --> 00:38:25,220
And now, what's kind of funky is that,
if you look over here, as expected,

874
00:38:25,220 --> 00:38:29,720
a comma b is 1 and 2, respectively.

875
00:38:29,720 --> 00:38:33,840
Why is temp 32,767?

876
00:38:33,840 --> 00:38:36,560
Recalling that temp, much like
the empty cup a moment ago,

877
00:38:36,560 --> 00:38:38,980
is declared here on line 21.

878
00:38:38,980 --> 00:38:43,390
Why 32,000- I mean, why is
it just some weird value?

879
00:38:43,390 --> 00:38:43,890
Yeah?

880
00:38:43,890 --> 00:38:45,190
>> AUDIENCE: It's not initialized.

881
00:38:45,190 --> 00:38:46,940
>> DAVID J. MALAN: It's
not been initialized.

882
00:38:46,940 --> 00:38:49,370
So our computer always
has physical memory.

883
00:38:49,370 --> 00:38:50,544
It always has physical RAM.

884
00:38:50,544 --> 00:38:52,710
And there's always zero's
and one's in there, right?

885
00:38:52,710 --> 00:38:54,626
Because we're using our
computer all day long,

886
00:38:54,626 --> 00:38:57,210
you're using the CS50 IDE
or the servers all day long.

887
00:38:57,210 --> 00:39:01,159
So that RAM either has some zeros or
some one's or some zeros and ones.

888
00:39:01,159 --> 00:39:02,950
No matter whether or
not you're using them.

889
00:39:02,950 --> 00:39:05,270
You can't just have blank
spaces where you want bits.

890
00:39:05,270 --> 00:39:06,850
They're either zeros and ones.

891
00:39:06,850 --> 00:39:09,610
>> So it turns out that temp, because
we've not initialized it yet,

892
00:39:09,610 --> 00:39:14,580
we have those 32 bits but they've not
been initialized to any known values.

893
00:39:14,580 --> 00:39:18,110
So whatever they were most
recently used for-- those 32 bits--

894
00:39:18,110 --> 00:39:23,000
we're just seeing the artifacts of some
previous use of those particular 32

895
00:39:23,000 --> 00:39:23,500
bits.

896
00:39:23,500 --> 00:39:27,780
As soon as I click Step Over though,
phew, temp is going to get the value 1.

897
00:39:27,780 --> 00:39:31,600
And if I do it again, a is
going to be given the value 2

898
00:39:31,600 --> 00:39:33,830
and then b is going to
be given the value 1.

899
00:39:33,830 --> 00:39:36,390
>> And so what's nice now at
this point in the story

900
00:39:36,390 --> 00:39:39,750
is that the debugger is
showing me, super slowly

901
00:39:39,750 --> 00:39:42,640
at my own pace, what
the state of Swap is.

902
00:39:42,640 --> 00:39:47,490
But notice at the top here, notice
that the call stack actually

903
00:39:47,490 --> 00:39:49,180
has two layers to it.

904
00:39:49,180 --> 00:39:53,240
Now the one that's highlighted as
Swap, if I click on Main instead,

905
00:39:53,240 --> 00:39:57,100
notice how the local variables change
because the developer can just hop

906
00:39:57,100 --> 00:39:59,740
around and go into any different scope.

907
00:39:59,740 --> 00:40:04,070
So even though we're doing all of this
work and correctly swapping a and b,

908
00:40:04,070 --> 00:40:09,080
if I go back and forth between Swap
where a is 2 and b is 1 and Main,

909
00:40:09,080 --> 00:40:11,851
has Main been affected at all?

910
00:40:11,851 --> 00:40:12,350
No.

911
00:40:12,350 --> 00:40:13,930
So what's the takeaway here?

912
00:40:13,930 --> 00:40:18,200
Well, it turns out that any time
you call a function like Swap,

913
00:40:18,200 --> 00:40:21,600
and you pass it arguments, what
you're passing to the Swap function

914
00:40:21,600 --> 00:40:24,730
in this case is a copy
of those arguments.

915
00:40:24,730 --> 00:40:28,620
So if x and y are each respectively
32 bits, what Swap is getting

916
00:40:28,620 --> 00:40:30,760
is two new local
variables, or arguments,

917
00:40:30,760 --> 00:40:34,380
called a and b-- but those are arbitrary
names-- but the pattern of zeros

918
00:40:34,380 --> 00:40:39,520
and ones inside of a and b are
lined up to be identical to x and y

919
00:40:39,520 --> 00:40:42,610
but they are not the
same thing as x and y.

920
00:40:42,610 --> 00:40:46,880
>> It's as though Main has on its piece of
paper the number 1 and 2 for x and y,

921
00:40:46,880 --> 00:40:49,260
and then when it hands that
piece of paper to Swap,

922
00:40:49,260 --> 00:40:51,970
Swap very quickly gets
its own pen, writes down

923
00:40:51,970 --> 00:40:56,240
1 and 2 on its own sheet of paper,
hands back the original xy to Main

924
00:40:56,240 --> 00:40:58,790
and then does its own
thing with a and b.

925
00:40:58,790 --> 00:41:01,940
And this is now super important because
this has nontrivial implications

926
00:41:01,940 --> 00:41:06,260
for actually writing correct code
because it would seem we cannot swap

927
00:41:06,260 --> 00:41:07,500
two variables.

928
00:41:07,500 --> 00:41:09,150
>> I have written a correct Swap function.

929
00:41:09,150 --> 00:41:12,770
We've implemented it with Lauren as
a correct swap function in reality,

930
00:41:12,770 --> 00:41:16,700
but apparently none of that
matters if you can't actually

931
00:41:16,700 --> 00:41:19,530
swap two values permanently.

932
00:41:19,530 --> 00:41:21,970
So we need another way
to actually get at this,

933
00:41:21,970 --> 00:41:24,472
and we need to be able to
actually solve this problem.

934
00:41:24,472 --> 00:41:27,180
And it turns out-- and we'll come
back to this particular picture

935
00:41:27,180 --> 00:41:30,500
before long-- this is one way that
you might draw your computer's memory.

936
00:41:30,500 --> 00:41:31,460
It's just a rectangle.

937
00:41:31,460 --> 00:41:32,960
You could draw it any
number of ways but it's

938
00:41:32,960 --> 00:41:35,740
convenient to draw it as a
rectangle for the following reason.

939
00:41:35,740 --> 00:41:40,040
>> We're going to start today and beyond
talking about the so-called stack.

940
00:41:40,040 --> 00:41:43,870
And the stack is just a chunk
of RAM-- a chunk of memory--

941
00:41:43,870 --> 00:41:47,100
that functions have access
to when they're called.

942
00:41:47,100 --> 00:41:49,800
And so it turns out that at
the very bottom of this stack

943
00:41:49,800 --> 00:41:53,590
is where all of Main's local variables
and org C and org V and all that stuff

944
00:41:53,590 --> 00:41:56,950
are going to go by default. And if Main
calls some other function like Swap,

945
00:41:56,950 --> 00:42:00,330
well, Swap is going to get another
layer of memory up above it.

946
00:42:00,330 --> 00:42:04,490
>> And so just to give you a quick cursory
picture of this, if I go over here--

947
00:42:04,490 --> 00:42:09,450
and let me mirror this on the
overhead as well-- what really I have,

948
00:42:09,450 --> 00:42:12,100
if we care only about the
bottom of this picture for now,

949
00:42:12,100 --> 00:42:15,070
is that when I run a program
and Main gets called,

950
00:42:15,070 --> 00:42:18,330
Main is given a chunk of
RAM in my computer that is

951
00:42:18,330 --> 00:42:20,060
at the bottom of this so-called stack.

952
00:42:20,060 --> 00:42:22,143
And I'm going to draw it
deliberately as a square.

953
00:42:22,143 --> 00:42:24,540
So it's like 32 bits or four bytes.

954
00:42:24,540 --> 00:42:28,790
And if this main function has a
variable called x with a value of 1

955
00:42:28,790 --> 00:42:32,626
and it has a variable called
y with the value of 2, that's

956
00:42:32,626 --> 00:42:35,750
like taking this sliver of memory that
Main has been given by the operating

957
00:42:35,750 --> 00:42:38,850
system and dividing it up so that
the first local variable goes here,

958
00:42:38,850 --> 00:42:40,930
the second one goes here, and that's it.

959
00:42:40,930 --> 00:42:45,590
>> When Main calls Swap, Swap
gets its own slice of memory

960
00:42:45,590 --> 00:42:48,280
that we'll draw like this
from the operating system,

961
00:42:48,280 --> 00:42:50,820
and it's going to have its
own local variables based

962
00:42:50,820 --> 00:42:53,825
on our implementation earlier
with local variables a

963
00:42:53,825 --> 00:42:58,010
and b that initially
get the values 1 and 2.

964
00:42:58,010 --> 00:43:00,450
But then, as soon as
the Swap code executes,

965
00:43:00,450 --> 00:43:03,760
and Lauren actually swaps the
OJ and milk, what's happening?

966
00:43:03,760 --> 00:43:09,030
Well, this 2 is becoming a 1, this
1 is becoming a 2, and, by the way,

967
00:43:09,030 --> 00:43:13,360
there is a temp variable that's being
used that whole time that eventually

968
00:43:13,360 --> 00:43:14,470
goes away.

969
00:43:14,470 --> 00:43:16,720
But it doesn't matter
how much work you do

970
00:43:16,720 --> 00:43:22,160
in this line of-- in this memory space,
x and y are completely untouched.

971
00:43:22,160 --> 00:43:26,320
>> So we need some way of giving
Swap and functions like it

972
00:43:26,320 --> 00:43:32,640
secret access, if you will, to
functions like-- to memory like x and y.

973
00:43:32,640 --> 00:43:35,110
So let's take a look at
an example that helps

974
00:43:35,110 --> 00:43:38,220
us see exactly what's been
going on this whole time.

975
00:43:38,220 --> 00:43:40,284
I'm going to go ahead
and open up Compare Zero.

976
00:43:40,284 --> 00:43:42,200
And I'm going to close
our debugger, I'm going

977
00:43:42,200 --> 00:43:44,360
to close this scary looking message
the just says, wait a minute,

978
00:43:44,360 --> 00:43:45,800
you're in the middle debugging.

979
00:43:45,800 --> 00:43:48,383
I'm going to hide this tab here
just to go back to simplicity.

980
00:43:48,383 --> 00:43:50,160
So don't worry if GDB is killed.

981
00:43:50,160 --> 00:43:53,910
That just means that the program has
been quit, deliberately in this case,

982
00:43:53,910 --> 00:43:54,820
by me.

983
00:43:54,820 --> 00:43:57,700
>> And now Compare Zero does this.

984
00:43:57,700 --> 00:44:00,110
I'm using the CS50
library in standard I/O.

985
00:44:00,110 --> 00:44:04,319
I've got a main function that first
says, say something, and gets a string.

986
00:44:04,319 --> 00:44:06,110
Then says it again and
gets another string.

987
00:44:06,110 --> 00:44:09,910
And notice that these two strings
are called s and t, respectively.

988
00:44:09,910 --> 00:44:12,910
And now this program, Compare
Zero, its purpose in life,

989
00:44:12,910 --> 00:44:15,470
it's supposed to tell me,
did I type the same thing?

990
00:44:15,470 --> 00:44:16,910
And so I'm going back to week one.

991
00:44:16,910 --> 00:44:19,950
I'm using my equal equal operator
which is the quality operator.

992
00:44:19,950 --> 00:44:22,220
Not the assignment operator,
the equality operator.

993
00:44:22,220 --> 00:44:23,890
I'm just comparing s and t.

994
00:44:23,890 --> 00:44:27,470
>> So let's actually go ahead and do this.

995
00:44:27,470 --> 00:44:32,680
And I'm going to go ahead
and make Compare Zero.

996
00:44:32,680 --> 00:44:35,110
I'm going to do ./comparezero.

997
00:44:35,110 --> 00:44:37,150
And I'm going to go
ahead and say something

998
00:44:37,150 --> 00:44:43,450
like, let's do mom in lowercase
and how about mom in uppercase.

999
00:44:43,450 --> 00:44:45,034
And of course I type different things.

1000
00:44:45,034 --> 00:44:45,533
All right.

1001
00:44:45,533 --> 00:44:46,570
That's to be expected.

1002
00:44:46,570 --> 00:44:47,640
>> Let's run it again.

1003
00:44:47,640 --> 00:44:49,740
Both times do lowercase, lowercase.

1004
00:44:49,740 --> 00:44:51,490
That looks super identical to me.

1005
00:44:51,490 --> 00:44:52,930
Enter.

1006
00:44:52,930 --> 00:44:53,430
OK.

1007
00:44:53,430 --> 00:44:55,804
Maybe it's just weird because
it's not liking my grammar.

1008
00:44:55,804 --> 00:44:59,930
So let's do a capital MOM,
capital MOM, identical.

1009
00:44:59,930 --> 00:45:01,490
Different things.

1010
00:45:01,490 --> 00:45:03,907
>> So why is that?

1011
00:45:03,907 --> 00:45:06,240
Well, what's actually going
on underneath the hood here?

1012
00:45:06,240 --> 00:45:08,180
So let's go back over
here for just a moment

1013
00:45:08,180 --> 00:45:10,910
and consider what GetString
is actually doing.

1014
00:45:10,910 --> 00:45:13,385
When you call GetString,
that's a function we

1015
00:45:13,385 --> 00:45:16,510
ourselves wrote and it somehow gets a
sequence of characters from the user.

1016
00:45:16,510 --> 00:45:20,280
And let's assume that the first
time I call GetString, that gives me

1017
00:45:20,280 --> 00:45:21,930
a chunk of memory that looks like this.

1018
00:45:21,930 --> 00:45:26,990
And if I typed in all lowercase
m-o-m-- and what goes after it?

1019
00:45:26,990 --> 00:45:28,840
Just a quick sanity check.

1020
00:45:28,840 --> 00:45:29,780
>> Backslash zero.

1021
00:45:29,780 --> 00:45:30,510
We know that.

1022
00:45:30,510 --> 00:45:32,784
And recall that we played
around with Zamila's name

1023
00:45:32,784 --> 00:45:34,950
and a bunch of other names
when Rob was here looking

1024
00:45:34,950 --> 00:45:36,280
at what's going on inside of memory.

1025
00:45:36,280 --> 00:45:37,780
So that story's exactly the same.

1026
00:45:37,780 --> 00:45:40,160
This is what GetString
is returning to me.

1027
00:45:40,160 --> 00:45:44,780
Now, my code a moment ago stored
the return value of GetString

1028
00:45:44,780 --> 00:45:47,510
in a variable called s.

1029
00:45:47,510 --> 00:45:51,390
And then the second time I called it,
it stored it in a variable called t.

1030
00:45:51,390 --> 00:45:55,070
>> So if I go over here, I need
to draw this local variable--

1031
00:45:55,070 --> 00:45:59,610
and I'm generally going to
draw a string as just-- we'll

1032
00:45:59,610 --> 00:46:02,360
call it s-- as a little square here.

1033
00:46:02,360 --> 00:46:09,760
And now, somehow-- how does mom
go inside of this variable s?

1034
00:46:09,760 --> 00:46:12,010
Well, we need to go back
to first principles here.

1035
00:46:12,010 --> 00:46:15,660
What is GetString actually returning?

1036
00:46:15,660 --> 00:46:19,030
>> So it turns out that M-O-M
backslash zero, and any number

1037
00:46:19,030 --> 00:46:22,364
of other strings in memory like
Zamila and Rob or Andy or any others,

1038
00:46:22,364 --> 00:46:24,280
are of course in our
computer's RAM or memory.

1039
00:46:24,280 --> 00:46:27,760
And your RAM has like-- you have
a gig of RAM, two gigs of RAM,

1040
00:46:27,760 --> 00:46:30,860
or a billion or two billion bytes,
or maybe even more these days.

1041
00:46:30,860 --> 00:46:34,070
So let's assume, for today's purposes,
that it doesn't matter how we number

1042
00:46:34,070 --> 00:46:36,640
them, but we can number each
of those billion or two billion

1043
00:46:36,640 --> 00:46:37,880
or four billion bytes.

1044
00:46:37,880 --> 00:46:42,240
>> And let's just arbitrarily say that
this is the first bite, second bite,

1045
00:46:42,240 --> 00:46:43,380
third, fourth.

1046
00:46:43,380 --> 00:46:46,570
I'm deliberately not using zero for
today but we'll come back to that.

1047
00:46:46,570 --> 00:46:49,570
So in other words, if this is the
very first time I'm using the program,

1048
00:46:49,570 --> 00:46:52,715
I'm just getting lucky and the first
bite is at location one then two

1049
00:46:52,715 --> 00:46:53,590
then three than four.

1050
00:46:53,590 --> 00:46:57,430
And if I kept drawing, box number
two billion would be way over here.

1051
00:46:57,430 --> 00:47:02,200
>> So what do you think, then,
GetString actually returns?

1052
00:47:02,200 --> 00:47:06,010
It's not returning M-O-M backslash
zero per se because that clearly

1053
00:47:06,010 --> 00:47:08,180
won't fit in the box that I've drawn.

1054
00:47:08,180 --> 00:47:11,210
So what else might GetString actually
be returning all these weeks?

1055
00:47:11,210 --> 00:47:14,410

1056
00:47:14,410 --> 00:47:16,820
The answer is on the
board here somewhere.

1057
00:47:16,820 --> 00:47:20,390
You can't fit M-O-M backslash zero,
so what might make sense instead?

1058
00:47:20,390 --> 00:47:23,424
If you had to be super clever, putting
on the so-called engineering hat,

1059
00:47:23,424 --> 00:47:24,340
what could you return?

1060
00:47:24,340 --> 00:47:27,340
What's the least amount of information
you could return that would still

1061
00:47:27,340 --> 00:47:30,610
let you find M-O-M in memory?

1062
00:47:30,610 --> 00:47:31,270
Yeah?

1063
00:47:31,270 --> 00:47:31,950
>> AUDIENCE: One.

1064
00:47:31,950 --> 00:47:32,200
>> DAVID J. MALAN: One.

1065
00:47:32,200 --> 00:47:33,021
And why one?

1066
00:47:33,021 --> 00:47:35,520
AUDIENCE: Because it would tell
you where to go [INAUDIBLE].

1067
00:47:35,520 --> 00:47:38,391

1068
00:47:38,391 --> 00:47:39,390
DAVID J. MALAN: Exactly.

1069
00:47:39,390 --> 00:47:44,300
I am just going to return the address
of the string that I have gotten.

1070
00:47:44,300 --> 00:47:46,570
The address in this
case is location one.

1071
00:47:46,570 --> 00:47:51,280
So what really is being stored in s--
and every string variable thus far--

1072
00:47:51,280 --> 00:47:53,430
has just been the
address of that string.

1073
00:47:53,430 --> 00:47:57,840
>> Meanwhile, if I call
GetString a second time and I

1074
00:47:57,840 --> 00:48:03,300
type in literally the same thing--
M-O-M with lowercase-- M-O-M

1075
00:48:03,300 --> 00:48:06,200
and another backslash zero,
and now maybe my program's

1076
00:48:06,200 --> 00:48:09,820
been running for some time so maybe this
is 10, this is location 11, this is 12,

1077
00:48:09,820 --> 00:48:10,700
this is 13.

1078
00:48:10,700 --> 00:48:13,590
The computers using some other
memory for whatever reason.

1079
00:48:13,590 --> 00:48:18,172
What now goes in my second
variable in my program t?

1080
00:48:18,172 --> 00:48:19,390
10.

1081
00:48:19,390 --> 00:48:20,050
Exactly.

1082
00:48:20,050 --> 00:48:23,910
>> And so when we look at the
source code of this program

1083
00:48:23,910 --> 00:48:26,550
where I'm simply trying
to compare the two values,

1084
00:48:26,550 --> 00:48:32,180
is s equal equal to t, what's
the obvious human answer?

1085
00:48:32,180 --> 00:48:34,890
Just no because 1 does not equal 10.

1086
00:48:34,890 --> 00:48:36,861
And so herein lies an
opportunity for us really

1087
00:48:36,861 --> 00:48:39,610
to just go back to, again, first
principles and think about, well,

1088
00:48:39,610 --> 00:48:41,110
what's going on underneath the hood?

1089
00:48:41,110 --> 00:48:43,240
We've been talking about
bits and bytes and memory,

1090
00:48:43,240 --> 00:48:46,820
but it's actually useful to understand
because when you call GetString,

1091
00:48:46,820 --> 00:48:50,280
even though we think of it is
returning M-O-M or string mom

1092
00:48:50,280 --> 00:48:53,120
or Andy or Zamila or
the like, technically

1093
00:48:53,120 --> 00:48:55,510
it's just returning the address
of that chunk of memory.

1094
00:48:55,510 --> 00:48:56,910
>> But that's OK.

1095
00:48:56,910 --> 00:49:00,570
Because how do I know
where the string ends?

1096
00:49:00,570 --> 00:49:03,840
If I'm only given the beginning?

1097
00:49:03,840 --> 00:49:05,380
Well, the backslash zero, right?

1098
00:49:05,380 --> 00:49:08,800
Just in linear time I can
print out with print def M-O-M.

1099
00:49:08,800 --> 00:49:11,820
And as soon as I see backslash
zero, I don't care where I started,

1100
00:49:11,820 --> 00:49:14,950
I already know implicitly
where I need to end.

1101
00:49:14,950 --> 00:49:18,700
>> And so today marks the beginning-- and
let me do this dramatically because we

1102
00:49:18,700 --> 00:49:21,800
went through a lot of trouble to
get these here training wheels--

1103
00:49:21,800 --> 00:49:29,840
so today the training wheels start
to come off and we reveal at least--

1104
00:49:29,840 --> 00:49:31,373
>> [APPLAUSE]

1105
00:49:31,373 --> 00:49:33,220

1106
00:49:33,220 --> 00:49:36,160
>> That was well worth the trip
to Target this morning, yes?

1107
00:49:36,160 --> 00:49:39,600
So now-- there is, it turns
out, no such thing as string.

1108
00:49:39,600 --> 00:49:41,140
String does not exist.

1109
00:49:41,140 --> 00:49:43,760
It's a synonym that we've had
inside of the CS50 library.

1110
00:49:43,760 --> 00:49:48,660
Henceforth, we're going to start calling
s and t not strings but char stars.

1111
00:49:48,660 --> 00:49:51,180
And the char star we'll
tease apart before long.

1112
00:49:51,180 --> 00:49:53,510
But this is to say,
that even if we continue

1113
00:49:53,510 --> 00:49:56,180
using GetString for now,
technically I should

1114
00:49:56,180 --> 00:49:59,010
be saying char star and char star.

1115
00:49:59,010 --> 00:50:01,720
>> And it turns out what that star
is going to denote is something

1116
00:50:01,720 --> 00:50:04,340
called a pointer or an address.

1117
00:50:04,340 --> 00:50:06,110
And in fact, a teaser
for what lies ahead

1118
00:50:06,110 --> 00:50:09,760
is this 20 second clip from our
friend Nick Parlante at Stanford

1119
00:50:09,760 --> 00:50:12,927
who, quite some time ago, spend
a ridiculous amount of time,

1120
00:50:12,927 --> 00:50:15,010
as best I can tell in his
kitchen or his basement,

1121
00:50:15,010 --> 00:50:17,140
making claymation
introducing to the world

1122
00:50:17,140 --> 00:50:20,010
a character named
Binky with whom we will

1123
00:50:20,010 --> 00:50:22,010
be introduced next time to pointers.

1124
00:50:22,010 --> 00:50:24,588
So here is a preview of what's to come.

1125
00:50:24,588 --> 00:50:26,370
>> [VIDEO PLAYBACK]

1126
00:50:26,370 --> 00:50:27,510
>> -Hey, Binky.

1127
00:50:27,510 --> 00:50:28,260
Wake up.

1128
00:50:28,260 --> 00:50:30,672
It's time for pointer fun.

1129
00:50:30,672 --> 00:50:31,616
>> -What's that?

1130
00:50:31,616 --> 00:50:33,032
Learn about pointers?

1131
00:50:33,032 --> 00:50:34,450
Oh, goody.

1132
00:50:34,450 --> 00:50:35,431
>> [END PLAYBACK]

1133
00:50:35,431 --> 00:50:38,055
DAVID J. MALAN: And on that note,
we will see you on Wednesday.

1134
00:50:38,055 --> 00:50:47,590

1135
00:50:47,590 --> 00:50:48,090
All right.

1136
00:50:48,090 --> 00:50:48,740
Who's dancing?

1137
00:50:48,740 --> 00:50:49,240
Come on.

1138
00:50:49,240 --> 00:50:50,330
Who's dancing?

1139
00:50:50,330 --> 00:50:51,820
You want me to get it started?

1140
00:50:51,820 --> 00:50:53,770
I'll get it started.

1141
00:50:53,770 --> 00:50:54,270
Woooo!

1142
00:50:54,270 --> 00:51:04,070

1143
00:51:04,070 --> 00:51:07,580
>> LAUREN: Sweet fancy Moses.