1
00:00:00,506 --> 00:00:08,636
[ Silence ]

2
00:00:09,136 --> 00:00:09,496
>> Alright.

3
00:00:09,496 --> 00:00:17,476
Welcome back, this is
CS50, the start of Week 3.

4
00:00:17,476 --> 00:00:20,076
So I got an email on
my Gmail inbox today

5
00:00:20,076 --> 00:00:21,776
that looked a little
something like this.

6
00:00:21,966 --> 00:00:25,266
It was from Harvard University,
Harvard University welcoming me

7
00:00:25,476 --> 00:00:28,816
and it's to say that Harvard
University is running an update

8
00:00:28,816 --> 00:00:31,066
on their servers and
requires all clients

9
00:00:31,066 --> 00:00:33,186
to confirm their web
mail access dot dot,

10
00:00:33,536 --> 00:00:35,376
confirm my web mail
access, regards.

11
00:00:35,686 --> 00:00:37,366
Thank you for using
Harvard University.

12
00:00:37,876 --> 00:00:42,196
So being an obedient user, I
went ahead and clicked that link

13
00:00:42,196 --> 00:00:45,956
and I found myself oh, add my
dot Harvard at the web mail log

14
00:00:46,096 --> 00:00:48,746
in but it wasn't quite
the web mail log in.

15
00:00:48,746 --> 00:00:52,686
If you look up top there you'll
actually see that I found myself

16
00:00:52,686 --> 00:00:57,126
of all places at Max Films
Online which actually sounds

17
00:00:57,126 --> 00:00:58,496
like I should've ended
up somewhere else

18
00:00:58,536 --> 00:01:01,776
but in fact it is Harvard's new
web mail system it would seem

19
00:01:01,776 --> 00:01:06,646
and so I proceeded to log in
with my username and my password

20
00:01:06,646 --> 00:01:10,256
and I clicked check mail
and then what happens?

21
00:01:10,566 --> 00:01:11,416
>> You have your mail.

22
00:01:11,696 --> 00:01:14,736
>> Alright, so now some
Max has my username

23
00:01:14,736 --> 00:01:16,536
and password somewhere
out on the internet.

24
00:01:16,536 --> 00:01:17,946
Now what can Max do with that?

25
00:01:18,136 --> 00:01:20,546
Well it can certainly
check my FAS mail at least,

26
00:01:20,546 --> 00:01:21,696
maybe there's nothing
even in there

27
00:01:21,696 --> 00:01:23,016
because I forwarded
it elsewhere.

28
00:01:23,306 --> 00:01:26,246
He can certainly send mail
now as though he were me

29
00:01:26,466 --> 00:01:28,146
but the thing is you
can do that any way even

30
00:01:28,146 --> 00:01:30,316
without having access to
someone's email account.

31
00:01:30,316 --> 00:01:32,366
You can for Gmails
terribly easily.

32
00:01:33,096 --> 00:01:34,576
And so what does that mean?

33
00:01:34,576 --> 00:01:37,466
Well, now he actually has,
let's say, a shell account.

34
00:01:37,546 --> 00:01:42,836
So you guys all have usernames
and passwords on cloud.cs50.net

35
00:01:43,016 --> 00:01:44,816
but for problem set
zero you also sign

36
00:01:44,816 --> 00:01:47,996
up for a so-called FAS account
which really is an email address

37
00:01:47,996 --> 00:01:51,116
of the form something fast
on Harvard.edu but it turns

38
00:01:51,116 --> 00:01:55,316
out FAS itself has a Linux
infrastructure not unlike ours

39
00:01:55,566 --> 00:01:58,606
called nice.FAS.Harvard.edu,

40
00:01:58,856 --> 00:02:02,696
the new instructional computing
environment, new as in came

41
00:02:02,726 --> 00:02:05,726
out about 10 years ago now
but it's another system

42
00:02:05,726 --> 00:02:08,656
like the cloud that you can
SSH to and you can right code

43
00:02:08,656 --> 00:02:11,786
for other courses and you can
send mail and such from it

44
00:02:12,086 --> 00:02:16,456
but the scary thing or at least
the compelling thing for Max is

45
00:02:16,456 --> 00:02:18,396
that now he has access
to a server,

46
00:02:18,396 --> 00:02:20,246
a server that's not
based in his own home.

47
00:02:20,246 --> 00:02:23,096
It's a server based maybe
somewhere across the ocean

48
00:02:23,096 --> 00:02:25,636
and now he can do pretty
much whatever he wants

49
00:02:25,736 --> 00:02:29,336
with your account on that
server including sending spam,

50
00:02:29,336 --> 00:02:31,006
including setting
up a file server

51
00:02:31,006 --> 00:02:33,136
and sharing files
illegally unbeknownst to you.

52
00:02:33,136 --> 00:02:35,956
So in short, he now has
access to some stored space

53
00:02:36,176 --> 00:02:40,036
and some username that you would
otherwise be responsible for.

54
00:02:40,036 --> 00:02:41,506
So what's the takeaway here?

55
00:02:42,096 --> 00:02:44,316
Well, certainly if
you get an email

56
00:02:44,496 --> 00:02:47,986
from regards Harvard
University, maybe not--

57
00:02:48,076 --> 00:02:50,056
don't necessarily
click on that link,

58
00:02:50,326 --> 00:02:52,076
but what this is
really a testament to

59
00:02:52,076 --> 00:02:54,606
and it will foreshadow what
we'll do later this semester,

60
00:02:54,796 --> 00:02:57,656
it is so terribly easy
to do what Max did,

61
00:02:57,656 --> 00:02:59,696
buying a domain name
certainly is pretty mindless.

62
00:02:59,696 --> 00:03:02,546
You can go to any number of
websites spend 5, 10, 15 dollars

63
00:03:02,746 --> 00:03:05,256
and now you own
maxfilmsonline.com,

64
00:03:05,526 --> 00:03:08,056
you'll need to host it somewhere
and we'll talk about this

65
00:03:08,056 --> 00:03:09,096
in detail into the course.

66
00:03:09,096 --> 00:03:11,196
If you wanna start your next
startup company or whatnot,

67
00:03:11,416 --> 00:03:13,466
it's actually very easy
to get started if it's

68
00:03:13,466 --> 00:03:15,286
at least an internet
startup on the web.

69
00:03:15,576 --> 00:03:18,056
So we'll talk a bit about
that so this part is easy

70
00:03:18,306 --> 00:03:19,386
and then it turns out if you go

71
00:03:19,386 --> 00:03:22,896
to the real
webmail.FAS.Harvard.edu,

72
00:03:23,086 --> 00:03:25,516
well by nature of the World
Wide Web and by nature

73
00:03:25,516 --> 00:03:28,906
of the language, HTML, in
which webpages are written,

74
00:03:29,146 --> 00:03:31,826
anyone on the internet can
see the so-called source code

75
00:03:31,826 --> 00:03:36,666
of webmails, of webpage and so
this stuff might look like Greek

76
00:03:36,706 --> 00:03:38,426
to some of you, some of
you might have programmed

77
00:03:38,426 --> 00:03:39,286
in this stuff before

78
00:03:39,286 --> 00:03:40,896
and actually I shouldn't
say program,

79
00:03:41,136 --> 00:03:43,556
HTML is not a programming
language as we'll see.

80
00:03:43,556 --> 00:03:45,716
It's a markup language,
more about aesthetics

81
00:03:45,806 --> 00:03:46,806
than it is about logic.

82
00:03:47,136 --> 00:03:51,176
But this kind of stuff, frankly,
can be very easily copied

83
00:03:51,656 --> 00:03:54,666
and then pasted into Max's
own homepage and if we go back

84
00:03:54,666 --> 00:03:57,046
to maxfilmsonline.com,
sure enough,

85
00:03:57,356 --> 00:03:59,066
there's the exact
same source code.

86
00:03:59,066 --> 00:04:02,476
He just pasted it in and now
he's probably changed one line

87
00:04:02,476 --> 00:04:04,946
of HTML so that when you
actually submit your username

88
00:04:04,946 --> 00:04:06,446
and password, it doesn't go

89
00:04:06,446 --> 00:04:09,266
to the server called
webmail.FAS.Harvard.edu,

90
00:04:09,486 --> 00:04:12,016
it goes to maxfilmsonline.com.

91
00:04:12,246 --> 00:04:13,566
So this is terribly common.

92
00:04:13,566 --> 00:04:15,616
This is what's generally
known as a phishing attack,

93
00:04:15,896 --> 00:04:20,266
P-H-I-S-H-I-N-G, which is
to say you try to lure hooks

94
00:04:20,266 --> 00:04:22,326
on unsuspecting user
into doing something

95
00:04:22,556 --> 00:04:24,266
that they might otherwise not

96
00:04:24,586 --> 00:04:26,626
if they actually
understood what was going on

97
00:04:26,626 --> 00:04:29,996
and it's a more general
notion of social engineering

98
00:04:29,996 --> 00:04:31,866
where you dupe people
into doing your bidding

99
00:04:32,046 --> 00:04:34,056
because they don't really
understand what's going on.

100
00:04:34,056 --> 00:04:35,326
So we'll talk a little
about this sort

101
00:04:35,326 --> 00:04:37,676
of stuff toward the tail end
in the context of web stuff

102
00:04:37,706 --> 00:04:41,166
but it certainly recurs and so
refer back if you find yourself

103
00:04:41,166 --> 00:04:43,646
at semester's end interested in
learning more about this stuff

104
00:04:43,856 --> 00:04:45,916
at the unofficial guide
to computer science

105
00:04:45,916 --> 00:04:46,796
at Harvard that we have.

106
00:04:46,796 --> 00:04:48,236
There's a bunch of
summaries of courses,

107
00:04:48,506 --> 00:04:52,086
among them Computer Science
105: Privacy and Security,

108
00:04:52,086 --> 00:04:54,126
which is more of a seminar
course in the spring

109
00:04:54,126 --> 00:04:55,476
in which you discuss and explore

110
00:04:55,476 --> 00:04:57,526
and understand these
kinds of issues better.

111
00:04:57,526 --> 00:05:02,066
So speaking of security, we
left off there last time looking

112
00:05:02,196 --> 00:05:04,736
at this thing called
secret key cryptography.

113
00:05:04,946 --> 00:05:06,866
Alright. There's many different
ways of describing this.

114
00:05:06,866 --> 00:05:09,466
You might hear it called
symmetric key cryptography,

115
00:05:09,466 --> 00:05:11,506
you might just hear it
called encryption in general,

116
00:05:11,836 --> 00:05:14,486
but this picture kind of
paints the right story for us.

117
00:05:14,486 --> 00:05:17,766
You have some plain text on the
left, some text, some message

118
00:05:17,796 --> 00:05:20,076
that I've typed in English
or whatever language I know,

119
00:05:20,376 --> 00:05:23,606
you then encrypt it, you
scramble it, but to do that,

120
00:05:23,646 --> 00:05:26,516
you need a secret, you need a
big number, you need a password,

121
00:05:26,516 --> 00:05:29,846
you need a passphrase, you
need some secret that only you

122
00:05:29,956 --> 00:05:32,216
and hopefully the recipient
knows and the output

123
00:05:32,216 --> 00:05:34,256
of this inscription process
is what we generally call

124
00:05:34,256 --> 00:05:37,786
ciphertext and then what's
nice about secret key crypto

125
00:05:38,096 --> 00:05:41,986
or symmetric key crypto is that
you can use the exact same key

126
00:05:42,136 --> 00:05:43,286
to decrypt this message.

127
00:05:43,286 --> 00:05:45,226
You essentially just
reverse the mathematics.

128
00:05:45,226 --> 00:05:45,916
Now what does that mean?

129
00:05:46,196 --> 00:05:46,966
Well, it depends.

130
00:05:46,966 --> 00:05:49,026
You're exploring this week,
as we'll discuss in a bit,

131
00:05:49,326 --> 00:05:52,216
Caesar cipher, Vigenere
cipher, and some other options

132
00:05:52,216 --> 00:05:53,936
in the hacker edition
but it boils

133
00:05:53,936 --> 00:05:55,706
down to generally
some basic math.

134
00:05:56,486 --> 00:05:58,776
So what's nice about
this system?

135
00:05:58,776 --> 00:05:59,806
Well, it's terribly easy.

136
00:05:59,806 --> 00:06:02,216
You, Alice, and Bob
agree on some key

137
00:06:02,216 --> 00:06:04,516
and now they can exchange
secret messages back and forth.

138
00:06:04,736 --> 00:06:06,346
But what's the problem
with this approach

139
00:06:06,936 --> 00:06:10,636
or with this general approach
to securing your information?

140
00:06:11,176 --> 00:06:13,646
You can-- go ahead.

141
00:06:13,646 --> 00:06:14,636
[ Inaudible Remark ]

142
00:06:14,636 --> 00:06:16,576
>> Yeah, it's very
vulnerable, right.

143
00:06:16,576 --> 00:06:18,496
If that key gets compromised,

144
00:06:18,496 --> 00:06:22,196
not only are all future messages
vulnerable to being decrypted

145
00:06:22,196 --> 00:06:24,226
by parties that shouldn't
have access to it

146
00:06:24,466 --> 00:06:27,206
because there's no
changing variable

147
00:06:27,206 --> 00:06:29,646
in this formula right
now, they can also go back

148
00:06:29,646 --> 00:06:31,706
if they had a record
of all of your messages

149
00:06:31,706 --> 00:06:32,846
that you've sent in years past.

150
00:06:33,336 --> 00:06:35,826
Well, they can go ahead and
decrypt all of those as well.

151
00:06:36,106 --> 00:06:39,596
So this is a recurring theme
in security that it's applying

152
00:06:39,596 --> 00:06:42,166
to claim that your data is
secure, it's to secure it

153
00:06:42,166 --> 00:06:43,656
with something like
a key but you have

154
00:06:43,656 --> 00:06:46,646
to understand what the
implications actually are.

155
00:06:46,646 --> 00:06:49,786
So this also did not address
one very common problem.

156
00:06:49,786 --> 00:06:51,886
These days, you go on
facebook.com and log

157
00:06:51,886 --> 00:06:54,496
in with your username and
password, you go on amazon.com

158
00:06:54,496 --> 00:06:56,806
and websites like this most
likely and you're probably

159
00:06:56,806 --> 00:07:00,066
at least familiar with the
notion of SSL or URLs that start

160
00:07:00,066 --> 00:07:04,006
with HTTPS where the
S stands for secure,

161
00:07:04,006 --> 00:07:05,616
something along those
lines and so

162
00:07:05,616 --> 00:07:07,506
that just means your
information is encrypted

163
00:07:07,506 --> 00:07:09,326
between you and the web server.

164
00:07:09,326 --> 00:07:12,676
But as we teased you with at the
end of last week, this is kind

165
00:07:12,676 --> 00:07:16,266
of a catch 22 in that if you
don't know anyone at Amazon

166
00:07:16,266 --> 00:07:17,896
or don't know anyone
at Facebook,

167
00:07:17,896 --> 00:07:21,296
how could you possibly have
agreed upon a shared secret,

168
00:07:21,326 --> 00:07:24,886
a key, a password, a big
number to use in this exchange

169
00:07:25,066 --> 00:07:26,646
and so thankfully,
for that purpose,

170
00:07:26,686 --> 00:07:29,336
there exists something called
public key cryptography

171
00:07:29,516 --> 00:07:31,386
which we won't focus so
much on in this course.

172
00:07:31,386 --> 00:07:32,766
There are security
courses at Harvard

173
00:07:32,766 --> 00:07:35,476
in which you can explore this
but the kinds of security we use

174
00:07:35,476 --> 00:07:39,896
with automated teller machines
these days, with online banking,

175
00:07:39,896 --> 00:07:42,706
with any form of
website that uses HTTPS,

176
00:07:42,706 --> 00:07:46,186
URLs realize there is a
solution to that chicken

177
00:07:46,266 --> 00:07:48,826
and the egg problem of
getting the key to someone

178
00:07:48,826 --> 00:07:50,196
but getting it to them securely.

179
00:07:50,416 --> 00:07:53,706
But the focus for P set 2
is on some symmetric key

180
00:07:53,706 --> 00:07:55,426
or some secret key ciphers.

181
00:07:55,676 --> 00:07:58,266
This recall stood for be
sure to drink your Ovaltine

182
00:07:58,266 --> 00:07:59,996
which is just a reference
to an older movie

183
00:08:00,236 --> 00:08:01,706
but it was a specific
incarnation

184
00:08:01,706 --> 00:08:05,506
of an algorithm called a
Caesar cipher or shift cipher,

185
00:08:05,736 --> 00:08:07,996
shift in that you
encrypt information just

186
00:08:07,996 --> 00:08:13,186
by rotating each letter by 1
place, by 2 places, by 25 places

187
00:08:13,186 --> 00:08:14,266
and after that it's
pretty useless

188
00:08:14,266 --> 00:08:15,396
because then you
get stuck in a loop

189
00:08:15,396 --> 00:08:18,046
because there's only 26 letters
in the alphabet, in this case,

190
00:08:18,116 --> 00:08:20,296
the key, does anyone
recall, was what number?

191
00:08:21,576 --> 00:08:21,746
>> 13?

192
00:08:21,746 --> 00:08:24,716
>> So it's 13 and you can infer
that just by knowing well,

193
00:08:24,716 --> 00:08:26,246
it's be sure to drink
your Ovaltine

194
00:08:26,246 --> 00:08:28,286
so how do I get from O to B?

195
00:08:28,466 --> 00:08:31,356
I rotate the letters 13
places, I wrap around when I get

196
00:08:31,356 --> 00:08:33,126
to Z back to A and sure enough

197
00:08:33,126 --> 00:08:35,226
that will give me the
ciphertext and vice versa.

198
00:08:35,556 --> 00:08:38,246
So it turns out too,
historically, this is an example

199
00:08:38,246 --> 00:08:42,506
of something called rot
13, R-O-T 13, for rotate 13

200
00:08:42,806 --> 00:08:45,716
and you'll see there's a bit of
geek humor in Pset 2 alluding

201
00:08:45,716 --> 00:08:49,696
to a more secure version of rot
13 but for now, the takeaway is

202
00:08:49,696 --> 00:08:52,146
that this is an example,
it's simple of this idea

203
00:08:52,146 --> 00:08:53,436
of a secret key cipher.

204
00:08:53,436 --> 00:08:55,496
So what specifically are
you doing in P set 2?

205
00:08:55,666 --> 00:08:58,376
Well, first, you're implementing
this notion of a Caesar cipher

206
00:08:58,376 --> 00:09:00,876
and you're gonna write a program
that takes these things--

207
00:09:00,876 --> 00:09:04,586
takes one of these things called
the command line argument, K,

208
00:09:04,586 --> 00:09:08,046
that is a word or number
or something that you type

209
00:09:08,126 --> 00:09:10,576
on the command line
after your program's name

210
00:09:10,576 --> 00:09:12,426
and hit Enter instead
of using something

211
00:09:12,426 --> 00:09:14,056
like get string to
get that input.

212
00:09:14,356 --> 00:09:17,416
And then if I type in 13 at
the prompt, you're then going

213
00:09:17,416 --> 00:09:20,226
to ask the user with get string
to give you an actual sentence,

214
00:09:20,286 --> 00:09:22,856
to give you some plain text and
what you're gonna have to then

215
00:09:22,856 --> 00:09:26,866
in this code is iterate, that
is walk from left to right

216
00:09:27,176 --> 00:09:29,736
across the string that the
user typed in, the plain text,

217
00:09:30,006 --> 00:09:32,836
and add essentially
that value of K to it.

218
00:09:32,836 --> 00:09:34,336
Maybe it's 13, maybe it's 1,

219
00:09:34,336 --> 00:09:36,486
it depends on what
number the user inputted

220
00:09:36,486 --> 00:09:38,986
and you're gonna have to do this
for character, for character,

221
00:09:38,986 --> 00:09:40,666
for character in
the user's input

222
00:09:40,976 --> 00:09:42,746
but you're probably gonna
need some conditions in there

223
00:09:42,746 --> 00:09:44,876
because if you hit a
period, at least according

224
00:09:44,876 --> 00:09:46,386
to our definition of
the Caesar cipher,

225
00:09:46,386 --> 00:09:47,836
you're not gonna
rotate punctation,

226
00:09:47,836 --> 00:09:49,836
you're only gonna rotate
alphabetical letters

227
00:09:50,136 --> 00:09:54,506
so A will become maybe B, B
will become maybe C. It depends

228
00:09:54,506 --> 00:09:56,986
on the value of K and so we'll
talk toward the end of today

229
00:09:56,986 --> 00:09:58,926
about a race again in characters

230
00:09:58,926 --> 00:10:01,106
and how you can actually do
this not only for this P set

231
00:10:01,106 --> 00:10:03,366
but more generally,
but realize by the end

232
00:10:03,366 --> 00:10:04,776
of this you'll be
able to decrypt one

233
00:10:04,776 --> 00:10:08,816
or more secret messages that
may await you in the P set.

234
00:10:09,346 --> 00:10:10,376
>> And then you move

235
00:10:10,376 --> 00:10:12,116
on to something a little
more sophisticated.

236
00:10:12,116 --> 00:10:14,456
So Caesar cipher,
not so secure, right?

237
00:10:14,456 --> 00:10:16,536
There are only 26 possible keys.

238
00:10:16,806 --> 00:10:18,216
I mean even I with
a piece of paper

239
00:10:18,216 --> 00:10:19,826
and pencil could
probably have figured

240
00:10:19,826 --> 00:10:22,866
out that these things said be
sure to drink your Ovaltine,

241
00:10:22,866 --> 00:10:24,616
I just guess and
check, guess and check,

242
00:10:24,616 --> 00:10:27,746
and I do that in average of
13 times maybe 26 times max

243
00:10:28,146 --> 00:10:30,626
and bam, I figured
out what the cipher--

244
00:10:30,626 --> 00:10:32,416
what the plain text
actually was.

245
00:10:32,786 --> 00:10:35,426
Well Mr. Vigenere actually
introduced a variant.

246
00:10:35,426 --> 00:10:37,686
It's still a shift cipher
but he realized well,

247
00:10:37,686 --> 00:10:39,026
if the fundamental problem is

248
00:10:39,026 --> 00:10:40,896
that these keys are
just too damn short,

249
00:10:40,936 --> 00:10:44,666
you only have a number between
0 and 25 or 1 and 26 depending

250
00:10:44,666 --> 00:10:49,586
on how you count, well why don't
we just use more than 1 key.

251
00:10:49,586 --> 00:10:53,206
In fact, why don't I use a
different key for each letter

252
00:10:53,486 --> 00:10:56,466
in my plain text so I might
rotate the first letter by 1

253
00:10:56,706 --> 00:10:59,916
but the second letter by 2
and the third letter by 3

254
00:11:00,166 --> 00:11:02,316
and then maybe I'll repeat
that process eventually.

255
00:11:02,316 --> 00:11:03,386
So Vigenere as you'll see

256
00:11:03,386 --> 00:11:07,206
in P set 2 spec introduces
the notion not of a key number

257
00:11:07,526 --> 00:11:11,586
but a key phrase, a keyword
whereby if it's A, B, C,

258
00:11:11,716 --> 00:11:16,386
you assume that okay, the key
ABC means first use a key of 1,

259
00:11:16,596 --> 00:11:19,896
then use a key of 2, then use
a key of 3, and then repeat,

260
00:11:19,936 --> 00:11:22,176
just keep using this keyword
again and again but look

261
00:11:22,176 --> 00:11:24,686
to the P set spec because like
a good computer scientist,

262
00:11:24,686 --> 00:11:26,836
as all URLs start
counting in 0 instead of 1

263
00:11:27,196 --> 00:11:28,336
but the idea is the same.

264
00:11:28,436 --> 00:11:31,316
The Vigenere cipher, same
idea as the Caesar cipher

265
00:11:31,316 --> 00:11:34,856
but you're using multiple keys
and you're just kind of thinking

266
00:11:34,856 --> 00:11:36,696
of them as a keyword
where each letter

267
00:11:36,696 --> 00:11:39,326
in the keyword represents
a different number.

268
00:11:39,326 --> 00:11:41,146
But what about the
hacker edition?

269
00:11:41,396 --> 00:11:44,136
So for those hackers among
you, you will find that we are,

270
00:11:44,136 --> 00:11:47,936
as someone acutely noted on the
bulletin board, help.cs50.net,

271
00:11:47,976 --> 00:11:50,456
that we are encouraging you
to make Crack this week.

272
00:11:50,806 --> 00:11:54,636
A program called Crack that when
run is responsible for taking

273
00:11:54,636 --> 00:11:57,676
as input someone's password
and figuring it out what--

274
00:11:57,676 --> 00:11:59,786
figuring out what
that password is.

275
00:11:59,786 --> 00:12:01,346
Now figuring out what
that password is,

276
00:12:01,666 --> 00:12:04,266
even though it's been
provided to you as ciphertext

277
00:12:04,346 --> 00:12:06,856
in encrypted form, it
turns out that on a lot

278
00:12:06,856 --> 00:12:10,276
of computer systems,
even MAC-OS, Linux, Unix,

279
00:12:10,276 --> 00:12:11,316
and in some form Windows,

280
00:12:11,586 --> 00:12:14,166
passwords are stored
somewhere on your hard drive.

281
00:12:14,166 --> 00:12:16,366
Otherwise, the computer
couldn't authenticate you,

282
00:12:16,396 --> 00:12:19,096
couldn't figure out yes or no
you should be allowed access

283
00:12:19,096 --> 00:12:20,546
when you type your
username and password.

284
00:12:20,766 --> 00:12:22,336
But they're not just
stored in plain text,

285
00:12:22,496 --> 00:12:24,736
they're not just stored as your
actual password in the file,

286
00:12:25,036 --> 00:12:26,986
they themselves are
generally encrypted

287
00:12:27,166 --> 00:12:29,556
and so that's what we hand you
the hackers for this P set.

288
00:12:29,556 --> 00:12:30,836
We're gonna hand you a file.

289
00:12:30,836 --> 00:12:33,916
A database from a real
Linux system with real users

290
00:12:34,206 --> 00:12:36,796
and their passwords are all
encrypted but thankfully,

291
00:12:36,796 --> 00:12:40,076
these humans who chose these
passwords weren't necessarily

292
00:12:40,076 --> 00:12:42,446
the sharpest, they certainly
weren't the most sophisticated

293
00:12:42,656 --> 00:12:45,626
and so they're not necessarily
the strongest passwords,

294
00:12:45,726 --> 00:12:48,546
that is odds are with a
little of savvy, a little bit

295
00:12:48,546 --> 00:12:50,796
of creativity in your
code, you can guess

296
00:12:51,306 --> 00:12:53,696
with high probability what
their passwords might be

297
00:12:53,956 --> 00:12:55,686
by writing a code
that takes advantage

298
00:12:55,686 --> 00:12:56,606
of certain assumptions.

299
00:12:56,606 --> 00:13:00,066
For instance, some of you might
have passwords that instead

300
00:13:00,066 --> 00:13:05,066
of being let's say
the word hello,

301
00:13:05,196 --> 00:13:07,356
suppose that were you
know your password

302
00:13:07,356 --> 00:13:08,336
but you might think alright,

303
00:13:08,336 --> 00:13:09,546
that's kind of too
easy to guess.

304
00:13:09,546 --> 00:13:11,726
I know I've been told that I
need to pick a better password

305
00:13:11,726 --> 00:13:13,986
and in fact the system made
me choose a stronger password.

306
00:13:14,186 --> 00:13:17,546
Well maybe you would
do H-E-L-L-0, right?

307
00:13:17,546 --> 00:13:20,086
It's stills pneumonically
useful for you to remember

308
00:13:20,256 --> 00:13:22,326
that it's hello but the O is a 0

309
00:13:22,646 --> 00:13:27,076
but maybe you can get more
clever still, H-E-1-1-0.

310
00:13:27,076 --> 00:13:29,286
Now, this is not an English
word that you would find

311
00:13:29,286 --> 00:13:31,476
in a dictionary, still
looks and feels like hello.

312
00:13:31,476 --> 00:13:32,886
You can remember it more easily

313
00:13:33,236 --> 00:13:36,486
but at least it's a little
more secure, secure in that

314
00:13:36,486 --> 00:13:38,116
if an adversary was
just guessing

315
00:13:38,116 --> 00:13:39,496
and checking passwords going

316
00:13:39,526 --> 00:13:41,336
through like the Oxford
English dictionary,

317
00:13:41,336 --> 00:13:43,326
just checking is this your
password, is this your password?

318
00:13:43,636 --> 00:13:45,436
Well, this is not gonna
appear most likely

319
00:13:45,506 --> 00:13:46,776
in that dictionary
so you're safe.

320
00:13:46,776 --> 00:13:50,916
But the problem is a lot of
people use the same trick,

321
00:13:51,246 --> 00:13:54,966
right, and if you're
the cryptanalyst,

322
00:13:54,966 --> 00:13:57,686
the hacker taking-- tackling
P set 2 hacker edition,

323
00:13:57,896 --> 00:14:01,046
well maybe you should be able
to leverage these very tricks

324
00:14:01,316 --> 00:14:03,696
that all of us think we're
being so clever in using.

325
00:14:03,766 --> 00:14:05,816
So it's unfortunately
not a clever trick

326
00:14:06,046 --> 00:14:08,756
if you're not the only one who
actually uses it in the world.

327
00:14:09,006 --> 00:14:10,686
Just to take it down the notch

328
00:14:10,686 --> 00:14:13,536
into putting context the
hacker edition of P set 2,

329
00:14:13,786 --> 00:14:18,086
we're fond of this clip from an
older movie called Spaceballs.

330
00:14:18,086 --> 00:14:18,646
[ Laughter ]

331
00:14:18,646 --> 00:14:26,346
>> Alright, what are you
doing to my daughter?

332
00:14:26,486 --> 00:14:31,166
>> Permit me to introduce the
brilliant young plastic surgeon,

333
00:14:31,736 --> 00:14:35,486
Dr. Philip Schlotkin,
the greatest nose job man

334
00:14:35,636 --> 00:14:38,106
in the entire universe
and Beverly Hills.

335
00:14:38,746 --> 00:14:39,166
>> Your highness.

336
00:14:39,906 --> 00:14:40,576
>> Nose job?

337
00:14:40,576 --> 00:14:41,466
I don't understand.

338
00:14:41,466 --> 00:14:42,786
She has already had a nose job.

339
00:14:42,786 --> 00:14:44,436
It was a sweet 16 present?

340
00:14:44,606 --> 00:14:46,686
>> No it's not what you think.

341
00:14:46,686 --> 00:14:47,546
It's much, much worse.

342
00:14:48,276 --> 00:14:51,526
If you do not give me the
combination to the F shield,

343
00:14:51,936 --> 00:15:01,766
Dr. Schlotkin will give your
daughter back her old nose!

344
00:15:01,766 --> 00:15:03,656
>> No! Where did you get that?

345
00:15:03,656 --> 00:15:05,156
>> Alright, I'll
tell, I'll tell.

346
00:15:05,236 --> 00:15:05,836
>> No daddy, no.

347
00:15:06,056 --> 00:15:07,496
You mustn't!

348
00:15:08,256 --> 00:15:09,086
>> You're right my dear.

349
00:15:09,846 --> 00:15:10,986
I'll miss your new nose

350
00:15:11,516 --> 00:15:19,796
but I will not tell them the
combination no matter what!

351
00:15:21,216 --> 00:15:25,316
>> Very well, Dr.
Schlotkin, do your worst.

352
00:15:26,086 --> 00:15:27,006
>> My pleasure!

353
00:15:27,796 --> 00:15:28,376
>> No, wait, wait.

354
00:15:28,376 --> 00:15:29,666
I'll tell, I'll tell.

355
00:15:29,666 --> 00:15:30,656
>> I knew it would work.

356
00:15:30,656 --> 00:15:33,526
Alright, give it to me.

357
00:15:35,116 --> 00:15:36,416
>> The combination is, 1.

358
00:15:36,416 --> 00:15:36,506
>> 1.

359
00:15:36,506 --> 00:15:36,596
>> 1.

360
00:15:36,596 --> 00:15:36,663
>> 2.

361
00:15:36,663 --> 00:15:36,736
>> 2.

362
00:15:36,736 --> 00:15:36,803
>> 2.

363
00:15:37,066 --> 00:15:37,186
>> 3.

364
00:15:38,756 --> 00:15:38,846
>> 3.

365
00:15:39,076 --> 00:15:39,166
>> 3.

366
00:15:39,166 --> 00:15:39,436
>> 4.

367
00:15:39,436 --> 00:15:40,056
>> 4.

368
00:15:40,056 --> 00:15:40,326
>> 4.

369
00:15:40,326 --> 00:15:40,416
>> 5.

370
00:15:40,416 --> 00:15:40,586
>> 5.

371
00:15:40,586 --> 00:15:40,746
>> 5.

372
00:15:40,906 --> 00:15:43,096
>> So the combination
is 1, 2, 3, 4, 5.

373
00:15:43,096 --> 00:15:45,936
That's the stupidest combination
I ever heard in my life.

374
00:15:45,936 --> 00:15:50,536
That's the kind of thing an
idiot would have on his luggage.

375
00:15:51,696 --> 00:15:52,276
>> Thank you, your highness.

376
00:15:52,276 --> 00:15:52,956
>> What did you do?

377
00:15:53,236 --> 00:15:54,196
>> I turned off the wall.

378
00:15:54,436 --> 00:15:55,296
>> No you didn't.

379
00:15:55,296 --> 00:15:57,886
You turned off the whole movie.

380
00:15:58,096 --> 00:16:03,396
>> I must have pressed
the wrong button.

381
00:16:04,966 --> 00:16:07,346
>> Well put it back on!

382
00:16:07,436 --> 00:16:08,536
Put the movie back on!

383
00:16:08,536 --> 00:16:09,716
>> Yes sir, yes sir.

384
00:16:10,016 --> 00:16:12,816
>> Let's go Arnold.

385
00:16:13,246 --> 00:16:14,346
Come Gretchen.

386
00:16:14,346 --> 00:16:20,266
Of course you know I still
have to bill you for this.

387
00:16:20,266 --> 00:16:20,516
[ Footsteps ]

388
00:16:20,516 --> 00:16:21,566
>> Well, did it work?

389
00:16:21,566 --> 00:16:22,036
Where's the king?

390
00:16:22,176 --> 00:16:22,616
>> It worked, sir.

391
00:16:22,616 --> 00:16:23,516
We have the combination.

392
00:16:23,836 --> 00:16:26,206
>> Great. Now we can
take every last breath

393
00:16:26,206 --> 00:16:28,066
of fresh air from
planet Druidia.

394
00:16:28,716 --> 00:16:29,476
What's the combination?

395
00:16:29,656 --> 00:16:31,626
>> 1, 2, 3, 4, 5.

396
00:16:32,066 --> 00:16:33,546
>> 1, 2, 3, 4, 5?

397
00:16:33,736 --> 00:16:34,166
>> Yes.

398
00:16:34,166 --> 00:16:34,846
>> That's amazing.

399
00:16:34,846 --> 00:16:36,226
I've got the same
combination on my luggage.

400
00:16:36,226 --> 00:16:38,146
[ Laughter ]

401
00:16:38,146 --> 00:16:40,866
>> Prepare Spaceball 1
for immediate departure.

402
00:16:40,926 --> 00:16:41,926
>> Yes, sir.

403
00:16:41,926 --> 00:16:44,856
>> And change the
combination on my luggage!

404
00:16:44,856 --> 00:16:45,366
[ Laughter ]

405
00:16:45,366 --> 00:16:45,433
>> Ahh!!

406
00:16:46,996 --> 00:16:50,016
>> Alright, I just need
a little break there.

407
00:16:50,896 --> 00:16:54,686
So a couple of announcements
of things to come and things

408
00:16:54,686 --> 00:16:55,856
that are already in progress.

409
00:16:55,856 --> 00:16:59,126
So if you've not yet started
P set 2, standard edition

410
00:16:59,126 --> 00:17:02,426
or if you have but you're
finding yourself not quite sure

411
00:17:02,426 --> 00:17:04,386
on what paths you go
down, do you realize

412
00:17:04,386 --> 00:17:05,666
if you didn't attend
it last night,

413
00:17:05,946 --> 00:17:07,746
the video of the
so-called walkthrough

414
00:17:07,746 --> 00:17:10,046
for problem set 2 is already
online, there's a video

415
00:17:10,046 --> 00:17:11,226
on the problem sets page.

416
00:17:11,656 --> 00:17:13,126
These walkthroughs
are led by Martha,

417
00:17:13,126 --> 00:17:15,036
one of our teaching
fellows each Sunday night

418
00:17:15,036 --> 00:17:17,836
and they are really meant to
be an opportunity again for you

419
00:17:17,836 --> 00:17:20,596
to get a sense of
where you should go--

420
00:17:20,646 --> 00:17:23,706
where to begin, what roads
to go down and what kinds

421
00:17:23,706 --> 00:17:25,466
of approaches you might
take to the problems.

422
00:17:25,466 --> 00:17:28,346
So certainly before you think
that ah, this isn't for me

423
00:17:28,346 --> 00:17:30,376
and throw up your hands
not knowing where to begin,

424
00:17:30,716 --> 00:17:32,426
you'd begin with
the walkthrough.

425
00:17:32,426 --> 00:17:34,116
Sections 2 are already
in progress,

426
00:17:34,156 --> 00:17:37,516
they started yesterday, they'll
continue today and Tuesdays,

427
00:17:37,606 --> 00:17:39,816
CS50 sections are
Sunday, Mondays, Tuesdays.

428
00:17:39,816 --> 00:17:42,146
If you have to switch out of
your section, that's fine.

429
00:17:42,146 --> 00:17:44,936
Follow the directions in the
email that you received to reach

430
00:17:44,936 --> 00:17:47,086
out to the head teaching
fellows but otherwise,

431
00:17:47,086 --> 00:17:49,806
certainly turn the
sections next as a resource

432
00:17:49,806 --> 00:17:53,316
for reinforcing what might
often feel a little bit fast,

433
00:17:53,316 --> 00:17:54,796
a little bit new in lectures.

434
00:17:55,026 --> 00:17:57,316
So a word on grades
2, so now that we know

435
00:17:57,316 --> 00:17:59,196
who your teaching fellows
are, we're gonna start turning

436
00:17:59,196 --> 00:18:02,396
through P set 0 and P set 1,
you should receive P set 0

437
00:18:02,396 --> 00:18:04,836
within the week, P set 1
within a week and a bit

438
00:18:05,016 --> 00:18:07,406
and then we'll be back on
track with P set 2 and onward.

439
00:18:07,556 --> 00:18:12,686
Per the syllabus, we used 3 axes
to evaluate your submissions

440
00:18:12,686 --> 00:18:13,586
of homework, correctness

441
00:18:13,736 --> 00:18:16,086
which generally means does
it work right, did you adhere

442
00:18:16,086 --> 00:18:19,856
to the spec, is it boggy
or not, two is design.

443
00:18:19,856 --> 00:18:21,836
Design is something we
really learn as we go

444
00:18:21,836 --> 00:18:24,296
and it's certainly much
more subjective but it boils

445
00:18:24,296 --> 00:18:27,496
down to did you make
some good decisions.

446
00:18:27,496 --> 00:18:29,786
There might not necessarily be
one right decision but did you

447
00:18:29,786 --> 00:18:32,136
at least make a compelling
decision that seems

448
00:18:32,136 --> 00:18:34,796
like a smart way to solve
a problem or for instance,

449
00:18:34,796 --> 00:18:37,236
did you just take your code
that worked for one part

450
00:18:37,236 --> 00:18:39,556
of the problem and just copy,
paste, paste, paste, paste,

451
00:18:39,556 --> 00:18:42,046
as opposed to implementing
something more obvious perhaps

452
00:18:42,046 --> 00:18:44,826
like a loop and so you'll
get feedback qualitatively

453
00:18:44,826 --> 00:18:47,346
from the teaching fellows
over time because realize

454
00:18:47,346 --> 00:18:51,816
that grade-- realize that the
problem sets being returned

455
00:18:51,816 --> 00:18:53,386
to you in this course
really are not just

456
00:18:53,386 --> 00:18:55,656
about taking off some
mark in our database

457
00:18:55,656 --> 00:18:58,516
or giving you just a pure number
but it really is an opportunity

458
00:18:58,516 --> 00:18:59,256
for the teaching fellows

459
00:18:59,256 --> 00:19:01,656
to continue teaching beyond
section, beyond lecture,

460
00:19:01,916 --> 00:19:04,946
and provide you with handwritten
or typed qualitative feedback

461
00:19:05,206 --> 00:19:07,516
so that you actually
do learn from mistakes

462
00:19:07,516 --> 00:19:09,216
or from otherwise poor decisions

463
00:19:09,416 --> 00:19:10,626
that you'll get better
at over time.

464
00:19:10,866 --> 00:19:13,486
Style is really the
aesthetics of one's code.

465
00:19:13,486 --> 00:19:16,846
Or your variables, Apley names
or things nicely indented.

466
00:19:17,186 --> 00:19:20,366
Frankly, too many students
frankly every semester kind

467
00:19:20,366 --> 00:19:21,846
of postpone the issue of style

468
00:19:21,846 --> 00:19:23,546
to the very last minute
and cut this corner.

469
00:19:23,546 --> 00:19:28,836
It's one of the easiest
ways to boost your score,

470
00:19:28,836 --> 00:19:32,386
boost the overall evaluation
because it's so easy

471
00:19:32,386 --> 00:19:33,436
to actually take care of

472
00:19:33,436 --> 00:19:35,036
and even though it might
seem silly right now

473
00:19:35,036 --> 00:19:36,866
to comment programs
that are only this long,

474
00:19:37,146 --> 00:19:39,666
maybe it might be silly to use
a variable name other than X

475
00:19:39,766 --> 00:19:41,026
when you only have one variable.

476
00:19:41,256 --> 00:19:43,936
Realize again by semester's end,
your programs are gonna get more

477
00:19:43,936 --> 00:19:45,776
and more interesting, more
and more sophisticated

478
00:19:45,916 --> 00:19:48,136
and these very much are
life lessons of sorts

479
00:19:48,136 --> 00:19:49,396
when it comes to programming.

480
00:19:49,396 --> 00:19:53,056
So realize too because
realistically you probably spend

481
00:19:53,056 --> 00:19:55,776
the most amount of time just
getting your program to work

482
00:19:55,776 --> 00:19:57,096
and getting it to
work correctly.

483
00:19:57,356 --> 00:20:00,086
We typically wait the access
of correctness a bit more

484
00:20:00,086 --> 00:20:01,916
than we do design and a
bit more than we do style.

485
00:20:02,126 --> 00:20:05,106
>> So for instance, if you don't
for instance comment your code,

486
00:20:05,106 --> 00:20:08,276
it's not gonna chip away a
third of the overall score.

487
00:20:08,466 --> 00:20:09,306
But what are the scores?

488
00:20:09,496 --> 00:20:10,756
We use very course metrics.

489
00:20:10,756 --> 00:20:14,516
So it's essentially a 5-bucket
scale where it pours all the way

490
00:20:14,516 --> 00:20:16,406
from the less, fair,
good, better, best.

491
00:20:16,986 --> 00:20:21,176
They roughly correspond to 1,
2, 3, 4, 5, but if you get a 3

492
00:20:21,176 --> 00:20:24,526
out of 5, yes the mathematicians
in the room will realize that 3

493
00:20:24,526 --> 00:20:27,006
to 5, that's 60 percent
my god, I got a D

494
00:20:27,006 --> 00:20:29,146
or a C already depending
on where the line is.

495
00:20:29,586 --> 00:20:30,166
Don't do that.

496
00:20:30,166 --> 00:20:31,466
It's irrelevant in CS50.

497
00:20:31,666 --> 00:20:33,626
So really in the
beginning of the semester,

498
00:20:33,836 --> 00:20:36,796
getting a whole bunch of
goods maybe even a fair so

499
00:20:36,796 --> 00:20:38,796
and then moving your way
through the term up to better

500
00:20:38,796 --> 00:20:40,186
and best or 4s and 5s.

501
00:20:40,396 --> 00:20:42,796
That really is the trajectory
we expect students to be on.

502
00:20:42,796 --> 00:20:49,846
So unlike my first Expos paper
in which I got like a C minus

503
00:20:49,846 --> 00:20:53,766
and was completely devastating,
a good in CS50 should not have

504
00:20:53,766 --> 00:20:55,826
that same psychological
effect that it had on me.

505
00:20:56,086 --> 00:20:56,986
Good is good.

506
00:20:57,416 --> 00:20:59,456
Poor, oh, poor is poor.

507
00:20:59,456 --> 00:21:00,966
So room for improvement
if it's poor.

508
00:21:00,966 --> 00:21:01,033
[ Laughter ]

509
00:21:01,033 --> 00:21:04,526
>> But starting off at
good is not a bad thing

510
00:21:04,526 --> 00:21:05,416
and also a pass-fail.

511
00:21:05,416 --> 00:21:07,306
So we still have the pink
forms at the end of the stage.

512
00:21:07,516 --> 00:21:10,386
Today, I believe is the deadline
for adding or dropping courses

513
00:21:10,386 --> 00:21:12,746
with no fee but up
until the fifth Monday

514
00:21:12,746 --> 00:21:15,566
of the semester can you
change letter-graded

515
00:21:15,566 --> 00:21:17,606
or pass-fail status with no fee

516
00:21:17,696 --> 00:21:19,986
so realize you still have some
time if that's of interest

517
00:21:20,246 --> 00:21:21,756
to decide beyond today.

518
00:21:21,756 --> 00:21:22,896
It's the fifth Monday
of the term

519
00:21:22,896 --> 00:21:25,566
for changing letter-graded
status without fee.

520
00:21:25,676 --> 00:21:29,156
So with that said, we've
been looking at data,

521
00:21:29,156 --> 00:21:31,446
we've been looking at you
in terms of your responses

522
00:21:31,446 --> 00:21:33,016
to P set 0 and P set 1.

523
00:21:33,286 --> 00:21:36,676
This is the mash up that we
made on the course's website

524
00:21:36,676 --> 00:21:39,446
where you can click around
and see which where all

525
00:21:39,446 --> 00:21:41,746
of you are actually from so
we like to look at this kind

526
00:21:41,746 --> 00:21:43,506
of demographic data and
it's really quite neat

527
00:21:43,506 --> 00:21:45,636
that we have folks from all
over the world, certainly.

528
00:21:46,086 --> 00:21:49,646
In terms of more local numbers,
we look at the breakdown

529
00:21:49,646 --> 00:21:51,836
by class and it's
actually pretty consistent

530
00:21:51,836 --> 00:21:52,926
as it's been over the years.

531
00:21:52,926 --> 00:21:55,416
We have a lot of sophomores,
roughly twice as many

532
00:21:55,416 --> 00:21:58,226
than in the other class but the
other three classes, freshmen,

533
00:21:58,226 --> 00:22:00,006
junior, and senior is
roughly about the same,

534
00:22:00,006 --> 00:22:02,536
about 100 of you each so
especially the seniors

535
00:22:02,536 --> 00:22:05,086
if you feel like I am the
only senior in this room

536
00:22:05,086 --> 00:22:07,706
who never actually took this
class before now, it's not true.

537
00:22:07,706 --> 00:22:09,766
There's like 99 or
so others of you.

538
00:22:09,766 --> 00:22:12,206
So realize we have good
numbers all around.

539
00:22:12,206 --> 00:22:15,726
Just for fun, we looked at
some of the other demograph--

540
00:22:15,726 --> 00:22:18,406
well actually, just for fun we
looked at some of the phone data

541
00:22:18,406 --> 00:22:20,516
and operating system data
but more importantly,

542
00:22:20,516 --> 00:22:24,276
we looked at the comfort level
so here too to reassure perhaps

543
00:22:24,436 --> 00:22:26,856
that there are more people
like you whether more comfy

544
00:22:26,856 --> 00:22:30,046
or less comfy, realize for the
first time this year the less

545
00:22:30,046 --> 00:22:32,646
comfortable students have
surpassed the other two pie

546
00:22:32,646 --> 00:22:34,656
slice this year, so
that's really good.

547
00:22:34,656 --> 00:22:37,606
So realize especially if you
are among those less comfortable

548
00:22:37,826 --> 00:22:41,346
that you are an increasing
chunk of the pie here.

549
00:22:41,716 --> 00:22:44,516
In terms of how much prior
experience specifically people

550
00:22:44,516 --> 00:22:49,506
have had, 0 courses is
the answer for 77 percent

551
00:22:49,586 --> 00:22:50,686
of the students in this room.

552
00:22:50,686 --> 00:22:52,246
So though you may
think that everyone

553
00:22:52,346 --> 00:22:54,246
around you has taken
one or more courses,

554
00:22:54,466 --> 00:22:56,136
only 17 percent have taken one

555
00:22:56,306 --> 00:22:58,526
and only 6 percent
have taken two or more.

556
00:22:58,806 --> 00:23:01,796
I was in-- I couldn't help
but notice the patterns

557
00:23:01,796 --> 00:23:03,846
of these charts, it doesn't look
quite as good on the overhead

558
00:23:04,176 --> 00:23:07,076
but I was teaching myself
keynote this morning.

559
00:23:07,076 --> 00:23:10,026
It's kind of fun what you
can do with these products.

560
00:23:10,026 --> 00:23:12,756
Anyhow. In terms of
phones and stuff,

561
00:23:12,756 --> 00:23:16,116
there's really no academic
basis for this one, but in terms

562
00:23:16,116 --> 00:23:19,056
of phones here, iPod Touches
are very popular apparently

563
00:23:19,056 --> 00:23:21,136
because Apple gives them to you
when you buy a Mac these days.

564
00:23:21,286 --> 00:23:23,626
iPhones though are pretty
popular, Blackberry Android,

565
00:23:23,916 --> 00:23:29,886
three of you have the Pre but
a lot of you are "normal."

566
00:23:29,886 --> 00:23:32,476
Many, many, many, almost
200 of you have just normal,

567
00:23:32,476 --> 00:23:34,246
what we would call
a normal cell phone.

568
00:23:34,246 --> 00:23:36,946
So we actually do ask this
data for useful purposes

569
00:23:36,946 --> 00:23:39,386
because the course is
increasingly focused on building

570
00:23:39,386 --> 00:23:42,466
out a suite of apps
particularly focused on campus.

571
00:23:42,626 --> 00:23:44,216
It's actually of
genuine interest to us

572
00:23:44,216 --> 00:23:46,836
to know exactly what the
user base is out there

573
00:23:46,956 --> 00:23:48,786
and it's hopefully useful
for you as you start

574
00:23:48,786 --> 00:23:51,386
to think toward the end of the
semester about final projects.

575
00:23:51,706 --> 00:23:53,696
If you build it,
would people come,

576
00:23:53,696 --> 00:23:54,836
would they actually use it?

577
00:23:54,986 --> 00:23:58,226
Well, there's a pretty good size
demographic of Blackberry users,

578
00:23:58,396 --> 00:24:00,756
iPhone users, Android
users, so those of you

579
00:24:00,756 --> 00:24:03,036
who might be interested
in doing mobile projects

580
00:24:03,036 --> 00:24:03,836
for your final project,

581
00:24:03,836 --> 00:24:07,106
you definitely have a
target audience these days.

582
00:24:07,106 --> 00:24:10,226
It's about 50-50 still
which is consistent

583
00:24:10,226 --> 00:24:12,336
with the other people's
statistics.

584
00:24:12,386 --> 00:24:15,856
Many of you over 150 are running
Mac OS snow LEOPARD the latest

585
00:24:15,856 --> 00:24:18,926
version followed by Windows 7,
some of you have an upgraded

586
00:24:18,926 --> 00:24:22,406
from 10.5 Mac OS, some of
you haven't or can't upgrade

587
00:24:22,406 --> 00:24:26,016
from 10.4 Tiger OS, a
bunch of you have Linux

588
00:24:26,056 --> 00:24:29,026
but it's pretty evenly
split overall.

589
00:24:29,196 --> 00:24:31,836
I will mention that if you
haven't noticed already,

590
00:24:31,836 --> 00:24:35,206
on CS50's website, thanks
to the support of friends

591
00:24:35,206 --> 00:24:37,706
in the industry, we have a
lot of resources available

592
00:24:37,846 --> 00:24:40,466
to CS50 students, many of
which are relevant particularly

593
00:24:40,466 --> 00:24:44,636
at term's end but we have access
for free to the iPhone and iPod

594
00:24:44,636 --> 00:24:46,356
and IOS-SDK so you don't have

595
00:24:46,356 --> 00:24:48,686
to pay the 99 dollars
to actually use that.

596
00:24:48,986 --> 00:24:52,396
We have under MSD an Academic
Alliance for CS50 students

597
00:24:52,686 --> 00:24:53,906
and their friends, all sorts

598
00:24:53,906 --> 00:24:56,656
of Window software including
Window 7 so if you're in that,

599
00:24:57,016 --> 00:25:01,986
especially the Vista bucket,
realize you can download

600
00:25:02,326 --> 00:25:03,996
for free following
the directions

601
00:25:03,996 --> 00:25:06,526
on our software page
and upgrade.

602
00:25:06,526 --> 00:25:09,556
Realize it comes with
absolutely no support from us

603
00:25:09,556 --> 00:25:11,956
but the software, the
DVDs and such are yours

604
00:25:11,956 --> 00:25:13,986
to download if you would like.

605
00:25:14,046 --> 00:25:17,476
So finally, and this was
actually my favorite number

606
00:25:17,476 --> 00:25:21,206
to be honest because
it really makes us,

607
00:25:21,326 --> 00:25:22,366
it really reaffirms some

608
00:25:22,366 --> 00:25:23,886
of the efforts we've
made in recent years.

609
00:25:24,196 --> 00:25:27,816
Now the most common reason
for taking 50 is actually

610
00:25:27,816 --> 00:25:30,136
as an elective and it's
now surpassed taking it

611
00:25:30,136 --> 00:25:31,206
for concentration credit

612
00:25:31,206 --> 00:25:33,316
which we thought was
quite interesting.

613
00:25:33,496 --> 00:25:35,826
It's a pretty big chunk of you
that don't know why you're here.

614
00:25:36,156 --> 00:25:38,616
So that's okay.

615
00:25:38,786 --> 00:25:41,876
We'll hopefully give you
a reason toward the end

616
00:25:42,176 --> 00:25:44,866
but it was nice to see that
we have a pretty equitable

617
00:25:44,866 --> 00:25:47,856
distribution now of people
who have to be here and people

618
00:25:47,856 --> 00:25:49,436
who actually want to be here.

619
00:25:49,436 --> 00:25:52,796
So with that said, let's
turn our attention back

620
00:25:52,796 --> 00:25:54,616
to the command line
for just a moment.

621
00:25:54,616 --> 00:25:57,296
So I'm gonna go into my
little terminal window here,

622
00:25:57,536 --> 00:26:00,596
those with PCs who have been
using potty, I'm using terminal

623
00:26:00,596 --> 00:26:02,996
on a Mac, I'm gonna
go ahead and SSH

624
00:26:02,996 --> 00:26:06,846
to cloud.cs50.net although
let me be extra careful

625
00:26:06,846 --> 00:26:08,166
and I'm gonna provide
my username.

626
00:26:08,166 --> 00:26:10,116
It's gonna then prompt
me for my password

627
00:26:10,656 --> 00:26:11,996
and now I'm at my prompt.

628
00:26:12,336 --> 00:26:14,736
Well, we recall from last
week, from your printouts,

629
00:26:14,736 --> 00:26:17,586
we looked at some, you know,
sort of warmup exercises,

630
00:26:17,636 --> 00:26:21,146
the annoying 99 bottles of beer
on the wall song was useful only

631
00:26:21,146 --> 00:26:22,746
in so far as it gave
us an opportunity

632
00:26:22,746 --> 00:26:24,306
to play with loops and such.

633
00:26:24,576 --> 00:26:27,646
So what I thought I'd do
is go ahead and start off

634
00:26:27,846 --> 00:26:30,706
by let's see doing beer.

635
00:26:31,136 --> 00:26:35,006
Let's say I'm gonna reinvent
one wheel here at least

636
00:26:35,006 --> 00:26:36,786
in real time, I'm gonna go ahead

637
00:26:36,786 --> 00:26:40,816
and reinvent beer 2.C
you can follow along

638
00:26:40,816 --> 00:26:41,676
at home if you would like.

639
00:26:41,716 --> 00:26:44,456
This song is gotta be printed
to the screen so I know I have

640
00:26:44,456 --> 00:26:49,056
to start off with include
standard IO.H. I don't think I

641
00:26:49,056 --> 00:26:51,416
need CS50's library but I'll
come back to that in a moment.

642
00:26:51,706 --> 00:26:54,236
I know mindlessly right now, I'm
just gonna start this program

643
00:26:54,236 --> 00:26:56,316
like this because I don't need
any command line arguments

644
00:26:56,396 --> 00:26:59,156
so I'm just gonna say void,
I don't need org C or org B

645
00:26:59,416 --> 00:27:00,506
and then what do I wanna do?

646
00:27:01,096 --> 00:27:04,886
Well, I'm first gonna tell the
user print F how many bottles

647
00:27:05,006 --> 00:27:06,826
of beer, question mark.

648
00:27:07,436 --> 00:27:10,436
And them I'm gonna leave a space
just for aesthetics and then oh,

649
00:27:10,436 --> 00:27:13,026
wait a minute, if I actually
wanna get this in from the user

650
00:27:13,026 --> 00:27:14,476
and I'm not using
command line arguments,

651
00:27:14,476 --> 00:27:15,576
I need to use what function?

652
00:27:15,926 --> 00:27:16,206
>> Get ints.

653
00:27:16,456 --> 00:27:18,656
>> So get in probably and
we'll see in just a week

654
00:27:18,656 --> 00:27:21,436
or two's time, how you
can solve these problems

655
00:27:21,436 --> 00:27:23,206
of getting ints-getting
strings from the user

656
00:27:23,376 --> 00:27:25,976
without using these training
wheels of the CS50 library.

657
00:27:25,976 --> 00:27:29,076
Before long we will take that
away and you'll realize it's--

658
00:27:29,216 --> 00:27:30,746
you're the better for it
because you can do more

659
00:27:30,746 --> 00:27:31,706
sophisticated things.

660
00:27:31,706 --> 00:27:33,216
But for now I'm gonna go ahead

661
00:27:33,216 --> 00:27:36,056
and use what I know
the cs50.H file

662
00:27:36,056 --> 00:27:38,366
so that gives me the
ability to use get ints

663
00:27:38,526 --> 00:27:39,446
and then what do I wanna do?

664
00:27:39,446 --> 00:27:41,236
Well, a little sanity
check and so even

665
00:27:41,236 --> 00:27:44,286
if it's not explicitly
said in future P sets,

666
00:27:44,526 --> 00:27:46,306
you should absolutely
always ensure

667
00:27:46,306 --> 00:27:49,606
that your program will not break
or crash or seg fault or do any

668
00:27:49,606 --> 00:27:52,326
of these weird things if the
user is just being difficult

669
00:27:52,586 --> 00:27:54,326
and so I'm gonna
do a sanity check.

670
00:27:54,426 --> 00:28:01,226
If N is less than, let's say
1, I'm gonna ahead and yell

671
00:28:01,226 --> 00:28:04,686
at the user and say
print F, let's say,

672
00:28:04,866 --> 00:28:07,206
sorry that makes no sense.

673
00:28:07,656 --> 00:28:11,296
New line. And then I don't
wanna just move on, right,

674
00:28:11,326 --> 00:28:12,796
because this would
be a logical error,

675
00:28:12,796 --> 00:28:15,706
I need to do what at this point?

676
00:28:15,706 --> 00:28:17,766
Yeah, so I'd probably
wanna return 1,

677
00:28:17,766 --> 00:28:21,026
1 being fairly arbitrary but
it's nonzero and that's the key,

678
00:28:21,086 --> 00:28:23,906
zero means good, anything
nonzero generally means bad

679
00:28:23,906 --> 00:28:25,506
and most people choose
their error codes

680
00:28:25,506 --> 00:28:27,486
with 1 and then move on up.

681
00:28:27,486 --> 00:28:29,226
If I didn't do this
and kept on going,

682
00:28:29,406 --> 00:28:31,606
I wouldn't actually stop
the user from proceeding

683
00:28:31,756 --> 00:28:34,316
so alternatively, I could use
a loop, maybe a do while loop

684
00:28:34,586 --> 00:28:37,396
but for this example I'm not
gonna add such sophistication.

685
00:28:37,396 --> 00:28:38,636
I'm just gonna go
ahead and abort

686
00:28:38,916 --> 00:28:42,066
if the user is not playing
along as they should.

687
00:28:42,356 --> 00:28:44,096
So now I'm gonna go
ahead and sing this song.

688
00:28:44,096 --> 00:28:45,066
So I could do this.

689
00:28:45,476 --> 00:28:53,016
So 4 int I gets, let's say, 99
while I is greater than or equal

690
00:28:53,156 --> 00:28:58,556
to 1 and then do I minus
minus on each iteration.

691
00:28:58,556 --> 00:29:01,236
I don't exactly know where
I'm going at but I know

692
00:29:01,236 --> 00:29:03,226
in general I wanna
start counting at 99

693
00:29:03,226 --> 00:29:06,736
and I probably wanna stop when
I hit zero or maybe really 1

694
00:29:07,036 --> 00:29:09,136
because remember in the
last verse of the song,

695
00:29:09,136 --> 00:29:11,406
I say one bottle beer in the
wall, one bottle of beer,

696
00:29:11,406 --> 00:29:12,396
take one down, pas it around,

697
00:29:12,656 --> 00:29:14,386
zero bottles of beer
on the wall.

698
00:29:14,576 --> 00:29:16,846
So I don't wanna count down
probably all the way to zero

699
00:29:16,846 --> 00:29:19,036
because then my last sentence
is gonna mention the number

700
00:29:19,576 --> 00:29:21,246
negative 1 which
would be incorrect

701
00:29:21,246 --> 00:29:23,056
so I'm just having a
little bit of foresight here

702
00:29:23,056 --> 00:29:24,676
so now I might do
something like this.

703
00:29:25,136 --> 00:29:27,796
So print F, how do I print 99?

704
00:29:27,796 --> 00:29:31,186
So 99 bottles of
beer on the wall.

705
00:29:31,966 --> 00:29:34,426
Alright, so now I've
already screwed up, right?

706
00:29:34,426 --> 00:29:37,016
I actually wanna use a
variable here not just 99

707
00:29:37,016 --> 00:29:40,546
so this becomes percent D for
digits and then I need a comma

708
00:29:40,546 --> 00:29:42,936
at the end here to
fill in that place

709
00:29:42,936 --> 00:29:44,826
over which it should
obviously be I.

710
00:29:44,946 --> 00:29:47,426
So now I have 99 bottles
of beer on the wall.

711
00:29:47,686 --> 00:29:50,516
The next sentence is easy,
so let me just paste it,

712
00:29:50,976 --> 00:29:54,396
99 bottles of beer,
I think that's right.

713
00:29:54,966 --> 00:29:59,576
So now I do a new phrase,
print F, take 1 down,

714
00:29:59,576 --> 00:30:03,936
pass it around, percent I.

715
00:30:05,126 --> 00:30:05,926
>> That one was easy.

716
00:30:06,016 --> 00:30:12,556
New line. Print F and pass
it around percent D bottles.

717
00:30:13,036 --> 00:30:14,556
The song's not only
annoying, it's boring.

718
00:30:14,956 --> 00:30:17,106
Beer on the wall-- on the wall,

719
00:30:17,106 --> 00:30:18,946
but so here is my
one moment of plot.

720
00:30:19,006 --> 00:30:21,646
I need to do something
slightly different here which is

721
00:30:21,646 --> 00:30:24,136
to insert what value for
this place holder now.

722
00:30:25,166 --> 00:30:25,376
>> I--

723
00:30:26,176 --> 00:30:28,746
>> Yeah, so probably I minus one
and I can put that in a variable

724
00:30:28,746 --> 00:30:29,626
but there's really no need.

725
00:30:29,626 --> 00:30:31,116
I can just do the
mathematics in line

726
00:30:31,346 --> 00:30:33,266
and so now I think I
have the right song.

727
00:30:33,266 --> 00:30:36,126
Ninety-nine bottles of beer on
the wall, 99 bottles of beer,

728
00:30:36,126 --> 00:30:37,686
so same thing, take one down,

729
00:30:37,686 --> 00:30:41,666
pass it around 98 bottles
of beer on the wall.

730
00:30:41,666 --> 00:30:44,116
So is there any risk that
this program is going to go

731
00:30:44,116 --> 00:30:45,486
to negative one or beyond?

732
00:30:46,976 --> 00:30:48,106
Okay. It doesn't seem to be.

733
00:30:48,106 --> 00:30:49,506
What if the user is difficult?

734
00:30:49,506 --> 00:30:53,096
What if the user
starts by typing in--

735
00:30:54,156 --> 00:30:55,336
well, there is a bug here.

736
00:30:56,566 --> 00:30:59,566
Yeah. So I actually was supposed
to start not at hard coded 99

737
00:30:59,566 --> 00:31:01,066
but at least what the
user actually wanted

738
00:31:01,066 --> 00:31:01,726
to start singing.

739
00:31:01,726 --> 00:31:03,466
Okay, so that's fixed
now, right?

740
00:31:03,466 --> 00:31:05,176
So now, it's not
hard coded as 99.

741
00:31:05,396 --> 00:31:08,086
So now supposed they typed
in 99, it obviously works.

742
00:31:08,296 --> 00:31:10,766
They typed in 299, still works.

743
00:31:10,826 --> 00:31:16,126
If they type in zero, it
should stop way up here.

744
00:31:16,126 --> 00:31:16,946
So I think we're okay.

745
00:31:17,296 --> 00:31:20,806
So this was essentially what
we call beer 1.C last time

746
00:31:20,806 --> 00:31:22,156
but I offered in beer two

747
00:31:22,156 --> 00:31:23,516
which you do have
among your printouts.

748
00:31:23,726 --> 00:31:25,226
There are some alternative
approaches.

749
00:31:25,226 --> 00:31:27,236
I'm gonna leave this here
for just a moment just

750
00:31:27,236 --> 00:31:29,466
so I can actually see
what I once did and kind

751
00:31:29,466 --> 00:31:31,506
of translate it now to
a different construct.

752
00:31:31,616 --> 00:31:37,186
I could actually do this
while N is greater than zero,

753
00:31:37,386 --> 00:31:38,176
you know what, I could just--

754
00:31:38,176 --> 00:31:40,096
let me get rid of this
for loop altogether.

755
00:31:40,096 --> 00:31:43,226
Now N, I don't use I, you
know, why don't I just plug

756
00:31:43,226 --> 00:31:48,096
in N there, plug in N there plug
in nothing there and then plug

757
00:31:48,096 --> 00:31:51,286
in N minus one here
and now is this an

758
00:31:51,286 --> 00:31:52,836
equivalent implementation?

759
00:31:53,866 --> 00:31:54,356
>> Decrement.

760
00:31:54,586 --> 00:31:56,806
>> Right, so I need to decrement
somewhere and I could be clever

761
00:31:56,806 --> 00:31:58,026
and I could actually
decrement it

762
00:31:58,156 --> 00:31:59,786
in a couple of different places.

763
00:32:00,096 --> 00:32:01,706
Here, I'm gonna go ahead
and actually just go

764
00:32:01,706 --> 00:32:03,966
with the obvious and
do N minus minus.

765
00:32:04,516 --> 00:32:05,966
Now-- or I could
be more explicit

766
00:32:05,966 --> 00:32:09,526
and get the same thing minus
one or as you might have seen

767
00:32:09,526 --> 00:32:11,746
in the textbook, you can
even say minus minus N.

768
00:32:11,746 --> 00:32:13,376
In this context,
they're all equivalent.

769
00:32:13,376 --> 00:32:15,406
So I'm just gonna say N
minus minus to be consistent

770
00:32:15,406 --> 00:32:17,086
from our earlier
sock example which is

771
00:32:17,086 --> 00:32:18,436
when we learned the syntax.

772
00:32:18,786 --> 00:32:19,836
Is this now equivalent?

773
00:32:21,146 --> 00:32:22,406
So it kind of is, right?

774
00:32:22,406 --> 00:32:24,876
I think the song would
be sung exactly the same.

775
00:32:24,876 --> 00:32:26,546
So what's an upside
of this approach?

776
00:32:26,546 --> 00:32:28,536
Well, I'm not introducing
a useless variable--

777
00:32:28,536 --> 00:32:31,466
an unnecessary variable I,
I'm just reusing what I have

778
00:32:31,836 --> 00:32:35,066
but at the same time this
is now destructive behavior.

779
00:32:35,066 --> 00:32:38,796
I've gotten an int from the user
calling it N and I'm using N

780
00:32:38,796 --> 00:32:41,956
to my advantage decrementing it
on each iteration but supposed

781
00:32:41,956 --> 00:32:44,846
at the very end of the
song I wanted to say thanks

782
00:32:44,846 --> 00:32:48,106
for playing N bottles
of beer on the wall.

783
00:32:48,106 --> 00:32:49,476
I've obviously lost
track of what?

784
00:32:49,666 --> 00:32:51,886
So the user's original input,

785
00:32:52,046 --> 00:32:53,786
and then there's another
one that's kind of harder

786
00:32:53,786 --> 00:32:54,706
to put your finger on.

787
00:32:54,706 --> 00:32:56,816
Which is better, the for
loop or the while loop.

788
00:32:56,816 --> 00:33:00,006
Anyone wanna argue for
the for or for the while?

789
00:33:00,976 --> 00:33:01,506
Which is better?

790
00:33:02,076 --> 00:33:03,716
>> The for loop.

791
00:33:03,826 --> 00:33:04,166
>> For loop.

792
00:33:04,166 --> 00:33:04,356
Why?

793
00:33:04,356 --> 00:33:09,016
>> It just seems better too.

794
00:33:09,016 --> 00:33:10,586
>> Okay. So that's not bad.

795
00:33:10,586 --> 00:33:11,596
No that's not bad, right?

796
00:33:11,596 --> 00:33:13,466
I mean frankly that would
be my answer sometimes

797
00:33:13,496 --> 00:33:14,146
to these questions.

798
00:33:14,146 --> 00:33:15,576
It just kind of feels right.

799
00:33:15,576 --> 00:33:18,426
Does anyone wanna argue one way
or the other more specifically?

800
00:33:18,426 --> 00:33:18,946
[ Inaudible Remark ]

801
00:33:18,946 --> 00:33:23,196
>> Does the for loop
use a while loop?

802
00:33:24,196 --> 00:33:24,376
>> Yeah.

803
00:33:24,376 --> 00:33:25,186
>> In what sense?

804
00:33:25,186 --> 00:33:27,406
Like is it underneath the hood
really using a while loop?

805
00:33:28,326 --> 00:33:29,266
So that depends.

806
00:33:29,266 --> 00:33:31,536
It's really up to the
compiler to decide how

807
00:33:31,536 --> 00:33:33,766
to implement something like
a for loop or something

808
00:33:33,766 --> 00:33:37,856
like while loop so they're
not likely being implemented

809
00:33:37,856 --> 00:33:38,496
with each other.

810
00:33:38,496 --> 00:33:41,106
It's lower level than that.

811
00:33:41,106 --> 00:33:41,316
[ Inaudible Remark ]

812
00:33:41,316 --> 00:33:42,036
>> What's that?

813
00:33:42,036 --> 00:33:43,196
[ Inaudible Remark ]

814
00:33:43,196 --> 00:33:44,146
>> Can I explain the difference?

815
00:33:44,406 --> 00:33:47,006
So, sure, so at the end of
the day frankly, there's none.

816
00:33:47,136 --> 00:33:49,566
There-- our looping constructs
that allow you to loop

817
00:33:49,656 --> 00:33:52,466
from something to something but
in the case of the for loop,

818
00:33:52,676 --> 00:33:56,636
recall that I had to do the
looping very explicitly.

819
00:33:56,696 --> 00:34:03,006
I had to say for int I gets N. I
is greater than or equal to one.

820
00:34:03,066 --> 00:34:06,656
I minus minus so in short, is
this kind of like a stick shift

821
00:34:06,726 --> 00:34:07,966
in a car, manual control.

822
00:34:07,966 --> 00:34:10,766
I have to be very much in
control of what's going

823
00:34:10,766 --> 00:34:13,896
on in the loop and very much
explicit whereas the while loop

824
00:34:13,896 --> 00:34:15,886
here, it gives me
much less control.

825
00:34:15,886 --> 00:34:18,216
It's kind of like automatic
but it's not quite automatic.

826
00:34:18,216 --> 00:34:20,596
It's not a perfect analogy
'cause still at the bottom

827
00:34:20,596 --> 00:34:23,126
of this thing I have to do
the decrementation myself.

828
00:34:23,526 --> 00:34:25,936
So at the end of the day,
it's mostly a stylistic thing.

829
00:34:25,936 --> 00:34:27,126
Which one makes the most sense?

830
00:34:27,346 --> 00:34:30,076
Frankly, I almost always
reach for a for loop because I

831
00:34:30,076 --> 00:34:32,906
like the explicitness of it even
though the syntax is a little

832
00:34:32,906 --> 00:34:34,486
ugly with the semicolons
and all that.

833
00:34:34,746 --> 00:34:35,316
I just kind of--

834
00:34:35,316 --> 00:34:38,336
once I understand how it
works I can then specify very

835
00:34:38,336 --> 00:34:42,146
pedantically initialize
condition update whereas while

836
00:34:42,326 --> 00:34:43,846
this to me just looks
a little uglier

837
00:34:43,906 --> 00:34:45,036
but these are just my eyes.

838
00:34:45,036 --> 00:34:47,686
So in short, it doesn't
matter and this is testament

839
00:34:47,686 --> 00:34:49,136
to what we emphasized
in the P set,

840
00:34:49,296 --> 00:34:52,376
that there really
is no one right ray

841
00:34:52,706 --> 00:34:54,266
to implement this things.

842
00:34:54,556 --> 00:34:56,736
Now let me go ahead and back
out of this for just a moment

843
00:34:57,226 --> 00:34:58,616
and let me go ahead and make--

844
00:34:58,986 --> 00:35:01,656
go into an alternative
implementation

845
00:35:01,656 --> 00:35:09,466
which we called beer,
let's say beer four.

846
00:35:10,906 --> 00:35:13,516
So in beer four, I decided
to get a little more clever.

847
00:35:13,516 --> 00:35:14,526
I've taken out the comments.

848
00:35:14,526 --> 00:35:16,146
You do have a printout
of this from today.

849
00:35:16,516 --> 00:35:20,226
So in beer four, the same
code I'm using up top here

850
00:35:20,516 --> 00:35:23,206
but now you notice,
actually don't wanna do this,

851
00:35:23,486 --> 00:35:24,366
let me back up actually.

852
00:35:24,366 --> 00:35:25,516
We'll start with a cleaner one.

853
00:35:25,956 --> 00:35:27,476
Beer three, one page prior.

854
00:35:28,076 --> 00:35:29,636
So the top of the
code is the same

855
00:35:29,946 --> 00:35:31,666
but notice what I've done here.

856
00:35:32,346 --> 00:35:36,646
Rather than cheat with the
parenthetical S which I kind

857
00:35:36,646 --> 00:35:39,116
of disclaimed last week that
isn't completely punting.

858
00:35:39,116 --> 00:35:41,296
I'm just taking parenthetical
S so I don't have to deal

859
00:35:41,296 --> 00:35:43,786
with plural expressions
of bottle--

860
00:35:43,966 --> 00:35:46,206
bottles or singular bottle.

861
00:35:46,386 --> 00:35:48,106
So here I wanted to
get a little smarter.

862
00:35:48,106 --> 00:35:50,136
So notice now in this
third version of beer,

863
00:35:50,136 --> 00:35:52,276
everything is the
same up top except

864
00:35:52,276 --> 00:35:54,166
for the stuff that's
inside the for loop

865
00:35:54,166 --> 00:35:55,186
and what's going on here?

866
00:35:55,456 --> 00:35:57,396
I still have this
place holder percent D.

867
00:35:57,646 --> 00:36:00,956
But now I have another place
holder percent S because I want

868
00:36:00,956 --> 00:36:03,646
to conditionally spit out bottle

869
00:36:03,646 --> 00:36:06,626
or bottles depending
on the value of I.

870
00:36:06,876 --> 00:36:07,846
Now, how do I do this?

871
00:36:07,846 --> 00:36:09,616
Well, I can actually do
this in a couple of ways

872
00:36:09,616 --> 00:36:12,336
and let me go ahead and delete
momentarily what I've started

873
00:36:12,336 --> 00:36:14,396
with to show you the
more explicit approach.

874
00:36:14,626 --> 00:36:16,986
To make this work, I kind
of need to say something

875
00:36:16,986 --> 00:36:22,296
like string S1 and then string
S2 because I might have one word

876
00:36:22,296 --> 00:36:23,826
in part of the song
and another word

877
00:36:23,826 --> 00:36:25,666
in the other depending
on the number.

878
00:36:25,996 --> 00:36:27,086
So now I might do this.

879
00:36:27,266 --> 00:36:34,606
So if I is greater than one
let's go ahead and say what?

880
00:36:34,816 --> 00:36:40,486
S1 gets, let's say what
value here, bottles.

881
00:36:41,116 --> 00:36:48,636
Otherwise, I'm going to
say-- keyboard problems--

882
00:36:48,736 --> 00:36:50,906
S1 gets bottle, right?

883
00:36:50,966 --> 00:36:54,596
So I've done my logic
in such a way

884
00:36:54,596 --> 00:36:56,596
that if I is greater than one.

885
00:36:56,596 --> 00:37:00,056
Well, I wanna say the plural,
if it's not greater than one

886
00:37:00,126 --> 00:37:03,266
and presumably equal to
one, I wanna say bottle

887
00:37:03,446 --> 00:37:05,076
and now what can I do over here?

888
00:37:05,076 --> 00:37:06,236
Well, notice, I can plug

889
00:37:06,236 --> 00:37:08,496
in percent D the
number then percent S,

890
00:37:08,806 --> 00:37:10,026
the string which I'm calling S1

891
00:37:10,026 --> 00:37:13,126
and then I can do it
again on this line below.

892
00:37:13,126 --> 00:37:13,976
And this is a branch.

893
00:37:13,976 --> 00:37:14,696
This is a condition.

894
00:37:14,696 --> 00:37:16,386
It's terribly explicit right now

895
00:37:16,656 --> 00:37:19,126
and so I have now
this variable S1

896
00:37:19,126 --> 00:37:20,596
that I can plug in dynamically.

897
00:37:20,826 --> 00:37:21,746
Why did I mention S2?

898
00:37:21,846 --> 00:37:23,996
Well, I kind of need
to do the same thing.

899
00:37:23,996 --> 00:37:25,616
So I kind of need this here.

900
00:37:25,836 --> 00:37:28,386
So I need a few copies of
this line because now I need

901
00:37:28,386 --> 00:37:34,236
to say actually, if S, let's
say bottles if it equals S1,

902
00:37:34,236 --> 00:37:36,576
then what do I have to do here?

903
00:37:36,576 --> 00:37:37,986
So now I have to
think about the logic

904
00:37:37,986 --> 00:37:39,816
for that second value, right?

905
00:37:39,816 --> 00:37:42,266
So for the second word in the
last sentence of the song,

906
00:37:42,266 --> 00:37:43,406
I need to think this through.

907
00:37:43,666 --> 00:37:44,336
So what do I do?

908
00:37:44,336 --> 00:37:45,896
Well, this is why I
kind of cleaned it up.

909
00:37:45,896 --> 00:37:49,736
So let me-- oh interesting my
undo feature is not undoing.

910
00:37:50,566 --> 00:37:52,836
Let me go back into the
original version here,

911
00:37:53,166 --> 00:37:55,006
so we can introduce one
other piece of syntax.

912
00:37:55,386 --> 00:37:59,546
So this is the one and only
I think ternary operator

913
00:37:59,546 --> 00:38:00,436
that we're going to use.

914
00:38:00,736 --> 00:38:03,796
So we've used a bunch of binary
operators, bi meaning two,

915
00:38:03,936 --> 00:38:08,056
X plus Y. The plus is a binary
operator 'cause it's got an

916
00:38:08,056 --> 00:38:09,866
upper end on the left and
upper end on the right.

917
00:38:10,136 --> 00:38:12,266
Turns out, then this is
a bit of a special case.

918
00:38:12,526 --> 00:38:14,546
There's this thing called
the ternary operator

919
00:38:14,736 --> 00:38:17,786
that actually has three upper
ends on the left, in the middle,

920
00:38:17,786 --> 00:38:21,516
and on the right and the special
syntax here is question mark

921
00:38:21,516 --> 00:38:22,126
and colon.

922
00:38:22,126 --> 00:38:24,296
And we introduced this not
because you need to now learn

923
00:38:24,296 --> 00:38:26,406
yet a new piece of syntax
but because you might see it

924
00:38:26,406 --> 00:38:27,896
and being able to
read this as useful.

925
00:38:28,186 --> 00:38:30,516
So notice what I've done
here in this very elegant,

926
00:38:30,516 --> 00:38:34,756
there say one liner, I'm
declaring a string called S1

927
00:38:34,756 --> 00:38:37,006
and then I'm assigning
it with equals

928
00:38:37,166 --> 00:38:38,846
to the following expression.

929
00:38:38,846 --> 00:38:41,016
Well, what does this
expression evaluate to?

930
00:38:41,266 --> 00:38:42,946
Well, notice the first
set of parenthesis.

931
00:38:42,946 --> 00:38:47,006
It says I equals equals one
as the parenthesis hint at,

932
00:38:47,146 --> 00:38:50,246
this is pretty much equivalent
to saying if parenthesis,

933
00:38:50,286 --> 00:38:53,276
something is true,
do this else do that?

934
00:38:53,796 --> 00:38:56,826
So really this is a
one line way of saying

935
00:38:56,866 --> 00:39:00,476
if something is true,
do this else do that.

936
00:39:00,846 --> 00:39:03,016
So the question mark
essentially denotes the

937
00:39:03,126 --> 00:39:04,326
"if" part of the construct.

938
00:39:04,566 --> 00:39:06,006
The colon denotes the else.

939
00:39:06,316 --> 00:39:08,276
This is identical to doing

940
00:39:08,556 --> 00:39:13,106
if I equals equals one then
set S1 equals a bottle L set S1

941
00:39:13,106 --> 00:39:16,696
equals bottles, but why
is this arguably better?

942
00:39:16,696 --> 00:39:19,036
Well, you saw how messy
my code was getting,

943
00:39:19,036 --> 00:39:20,236
it was such a simple thing and

944
00:39:20,236 --> 00:39:21,716
yet here I am writing
eight lines of code

945
00:39:21,716 --> 00:39:22,616
to solve this problem.

946
00:39:22,866 --> 00:39:25,936
This is why there is this
stuff called syntactic sugar

947
00:39:26,286 --> 00:39:28,756
as a geek would call it which
is just features that allow you

948
00:39:28,756 --> 00:39:30,426
to do something in
a different way

949
00:39:30,786 --> 00:39:33,376
but not necessarily something
that you couldn't do otherwise.

950
00:39:33,436 --> 00:39:36,186
So this is a ternary operator
using question mark and colon

951
00:39:36,506 --> 00:39:39,366
but the end of the day, the only
optimization I've achieved here

952
00:39:39,586 --> 00:39:43,136
is to plug in dynamically
S1 and/or S2

953
00:39:43,136 --> 00:39:46,146
so that my grammar
frankly is now correct.

954
00:39:46,146 --> 00:39:48,046
And I'm not cutting that
stupid little corner

955
00:39:48,046 --> 00:39:51,146
to say bottle parenthesis
S close parenthesis.

956
00:39:51,726 --> 00:39:53,906
But there's one more
improvement we can make on here,

957
00:39:53,906 --> 00:39:57,536
so one last focus
on this silly song.

958
00:39:57,886 --> 00:40:02,536
So notice in this version, I
decided to factor out the song

959
00:40:02,716 --> 00:40:03,406
because it feels

960
00:40:03,406 --> 00:40:05,976
like conceptually I could put
this in a function, right?

961
00:40:06,136 --> 00:40:08,086
>> Recall that a function
is like a black box

962
00:40:08,086 --> 00:40:10,986
that you yourself can implement
or that someone else implemented

963
00:40:10,986 --> 00:40:13,536
like print F but you yourself
can implement these things

964
00:40:13,766 --> 00:40:17,406
and if you can imagine-- if the
thing you want to achieve feels

965
00:40:17,406 --> 00:40:19,626
like just conceptually,
it can be bundled up

966
00:40:19,626 --> 00:40:21,436
and given a word like chorus.

967
00:40:21,806 --> 00:40:24,926
Well then it might very well
be a candidate for a function.

968
00:40:25,156 --> 00:40:26,866
And the fancy word here
that you might see in one

969
00:40:26,866 --> 00:40:29,626
of the recommended text is
hierarchical decomposition.

970
00:40:29,886 --> 00:40:32,886
This just means taking
out logical chunks of code

971
00:40:32,886 --> 00:40:35,876
that collectively kind of
have a conceptual definition,

972
00:40:36,146 --> 00:40:38,596
sing a song, sing the
chorus and putting them

973
00:40:38,596 --> 00:40:39,666
in a function of their own.

974
00:40:39,666 --> 00:40:42,226
So apparently, I've implemented
a function called chorus.

975
00:40:42,526 --> 00:40:44,406
It takes how many arguments?

976
00:40:45,816 --> 00:40:46,956
So it seems to take one.

977
00:40:46,956 --> 00:40:50,246
I'm being a little clever here
at the risk of being confusing

978
00:40:50,246 --> 00:40:52,756
and I'm trying to be-- show
off my coding skills here even

979
00:40:52,756 --> 00:40:54,296
though this is not the
most clear but let's see

980
00:40:54,296 --> 00:40:55,486
if we can tease this apart.

981
00:40:55,606 --> 00:40:56,826
I seem to have a while loop.

982
00:40:57,086 --> 00:40:59,266
Recall that a while loop
iterates again and again

983
00:40:59,266 --> 00:41:02,886
and again so long as the
thing in parenthesis is true

984
00:41:03,336 --> 00:41:05,796
or more generally none false.

985
00:41:06,136 --> 00:41:07,126
So not zero.

986
00:41:07,366 --> 00:41:09,226
So remember that false is zero.

987
00:41:09,996 --> 00:41:11,586
Anything else is true.

988
00:41:11,876 --> 00:41:14,736
So this has the effect of
iterating again and again

989
00:41:14,736 --> 00:41:19,156
and again while N is anything
other than zero, right?

990
00:41:19,156 --> 00:41:21,526
So this is why it's clever
if a little confusing,

991
00:41:21,686 --> 00:41:24,386
it's clever in that if I know
I'm decrementing N and N and N

992
00:41:24,386 --> 00:41:26,646
and N down, down, down
eventually, I'm gonna hit zero

993
00:41:26,646 --> 00:41:27,626
so this loop will stop.

994
00:41:27,626 --> 00:41:30,156
So it's just my clever way
of leveraging what I know

995
00:41:30,156 --> 00:41:32,976
to be a condition and a Boolean
expression in that condition

996
00:41:33,196 --> 00:41:36,586
and a variable that's going to
return conceptually true, true,

997
00:41:36,586 --> 00:41:39,196
true, true, true that is
nonzero, nonzero, nonzero

998
00:41:39,486 --> 00:41:41,736
and eventually false,
that is zero.

999
00:41:41,736 --> 00:41:43,196
So how did I implement chorus?

1000
00:41:43,616 --> 00:41:46,216
Well, chorus actually
is just a copy paste

1001
00:41:46,216 --> 00:41:48,426
of the code we just wrote
in the third version of beer

1002
00:41:48,426 --> 00:41:52,736
but I've wrapped it this time
with a functions declaration.

1003
00:41:52,996 --> 00:41:56,216
I'm returning void 'cause
this thing just sings.

1004
00:41:56,216 --> 00:41:57,146
It prints to the screen.

1005
00:41:57,186 --> 00:41:59,506
I don't need to actually
return something like get int

1006
00:41:59,716 --> 00:42:01,136
or return something
like get string.

1007
00:42:01,136 --> 00:42:03,226
I just wanted to print
its response to the screen

1008
00:42:03,526 --> 00:42:04,826
and then return immediately.

1009
00:42:05,106 --> 00:42:07,066
So I'm using this
little grammar trick here

1010
00:42:07,066 --> 00:42:09,366
but I could implement this we've
seen with an if and an else

1011
00:42:09,806 --> 00:42:12,386
but notice that I do
need to take as input

1012
00:42:12,386 --> 00:42:14,896
to this function the
number of bottles of beer,

1013
00:42:15,046 --> 00:42:17,756
let's call it B, that I
actually wanna sing about.

1014
00:42:18,116 --> 00:42:21,616
And once I actually take
in B, now I can plug in--

1015
00:42:21,616 --> 00:42:23,076
there's loop-- there's
no for loop here.

1016
00:42:23,376 --> 00:42:27,386
Notice that I plug in B
here, I plug in S1 for bottle

1017
00:42:27,386 --> 00:42:29,166
or bottles and I plug in S2.

1018
00:42:29,166 --> 00:42:30,766
It's the exact same thing.

1019
00:42:31,086 --> 00:42:33,266
So where is B actually changing?

1020
00:42:33,436 --> 00:42:36,426
Well, notice where did I
call this function chorus?

1021
00:42:36,926 --> 00:42:40,086
If I scroll back up, I mean
D in inside the while loop

1022
00:42:40,356 --> 00:42:44,476
and on every iteration I'm
calling chorus passing in N

1023
00:42:44,796 --> 00:42:47,166
but again just to be
clever if confusing,

1024
00:42:47,456 --> 00:42:49,916
I'm decrementing N
at the same time.

1025
00:42:49,916 --> 00:42:53,236
And so what really happens
here is the first time chorus

1026
00:42:53,626 --> 00:42:57,486
of bracket N minus minus is
called the number 99 does

1027
00:42:57,486 --> 00:42:58,806
in fact get passed in.

1028
00:42:59,056 --> 00:43:01,026
But the moment chorus
is done executing,

1029
00:43:01,026 --> 00:43:02,286
there's still a little more work

1030
00:43:02,286 --> 00:43:03,986
to be done before
the next iteration.

1031
00:43:04,216 --> 00:43:05,376
What's that little bit of work?

1032
00:43:05,766 --> 00:43:08,756
The minus minus then
actually needs to happen.

1033
00:43:08,816 --> 00:43:10,456
So I meant-- point
this out frankly not

1034
00:43:10,456 --> 00:43:13,546
because you should start
coding in the most succinct way

1035
00:43:13,546 --> 00:43:15,966
that you can 'cause arguably
every time I look at this,

1036
00:43:15,966 --> 00:43:18,526
I have to think alright, does
this actually subtract properly

1037
00:43:18,526 --> 00:43:21,046
or did I screw up my own code
but frankly when you look

1038
00:43:21,046 --> 00:43:23,286
in text books, when you
look in online references,

1039
00:43:23,286 --> 00:43:24,626
you're gonna see
syntax like this.

1040
00:43:24,866 --> 00:43:28,166
So it's worth at least tucking
it away so that you can reason

1041
00:43:28,166 --> 00:43:29,156
through what's going on.

1042
00:43:29,316 --> 00:43:29,896
Yeah?

1043
00:43:30,396 --> 00:43:37,636
[ Inaudible Remark ]

1044
00:43:38,136 --> 00:43:42,286
>> In this case because the
minus minus is applied inside

1045
00:43:42,286 --> 00:43:42,916
the parenthetical.

1046
00:43:42,916 --> 00:43:44,556
It first passes in
the current value

1047
00:43:44,746 --> 00:43:46,306
and the minus minus
happens after.

1048
00:43:46,796 --> 00:43:49,066
So 99 does in fact
get past correctly.

1049
00:43:49,296 --> 00:43:49,416
Yeah?

1050
00:43:49,916 --> 00:43:52,696
>> Is this a simpler
way then do you agree?

1051
00:43:52,696 --> 00:43:53,836
>> Is there-- is
this a simpler way?

1052
00:43:53,836 --> 00:43:54,766
[ Inaudible Remark ]

1053
00:43:54,766 --> 00:43:56,956
>> It's a good question.

1054
00:43:57,036 --> 00:44:00,966
I would say this is kind of
on the fence to be honest

1055
00:44:00,966 --> 00:44:04,046
because at this point, I haven't
really gained all that much

1056
00:44:04,076 --> 00:44:05,876
in adding this function
chorus, right?

1057
00:44:05,876 --> 00:44:07,956
Because really all I did
was move these six lines

1058
00:44:07,956 --> 00:44:10,606
of actual code from
my main function

1059
00:44:10,606 --> 00:44:11,916
into their own function.

1060
00:44:12,196 --> 00:44:14,966
So arguably here, I'd probably
leave it in main, right?

1061
00:44:14,966 --> 00:44:17,036
There's no sense in
creating work for your self,

1062
00:44:17,386 --> 00:44:19,226
re-breaking things
up into functions.

1063
00:44:19,226 --> 00:44:21,466
If at the end of the day, your
program is still just as long

1064
00:44:21,606 --> 00:44:23,316
and you haven't really
fundamentally improved it

1065
00:44:23,396 --> 00:44:24,576
but we need this ability.

1066
00:44:24,576 --> 00:44:27,416
We need this building block as
proceed later this week and next

1067
00:44:27,646 --> 00:44:29,366
so that as we start
to design again,

1068
00:44:29,366 --> 00:44:30,956
increasingly interesting
programs,

1069
00:44:31,206 --> 00:44:33,386
we have now this
primitive to deploy.

1070
00:44:33,776 --> 00:44:35,536
So here, I'd say
it's on the fence.

1071
00:44:35,536 --> 00:44:36,326
Beer obviously, frankly,

1072
00:44:36,326 --> 00:44:38,046
I'm pretty happy
with beer 1.C. Yeah?

1073
00:44:38,046 --> 00:44:41,386
>> So S1 and I don't
understand why that--

1074
00:44:41,956 --> 00:44:44,196
why do you need the string S2?

1075
00:44:44,196 --> 00:44:44,936
>> So good question.

1076
00:44:44,936 --> 00:44:47,736
Why do I need the string
S2 in addition to S1,

1077
00:44:47,736 --> 00:44:49,276
'cause my whole point
here is grammar

1078
00:44:49,316 --> 00:44:53,616
and because my wording changes
potentially in the last sentence

1079
00:44:53,616 --> 00:44:56,446
when I subtract off one of those
bottles of beer from the wall.

1080
00:44:56,736 --> 00:44:59,776
It's possible that I'll first
be singing about bottles of beer

1081
00:45:00,006 --> 00:45:03,006
but then I'm left in the last
sentence with one bottle of beer

1082
00:45:03,276 --> 00:45:07,186
so I need two variables S1 and
S2 just in case my grammar needs

1083
00:45:07,186 --> 00:45:08,696
to change according to the song

1084
00:45:08,916 --> 00:45:11,516
in the very last verse
that I'm singing.

1085
00:45:11,656 --> 00:45:13,016
>> But doesn't it
change like the image--

1086
00:45:13,436 --> 00:45:20,596
like grammar is does it change
like the image [inaudible]--

1087
00:45:20,596 --> 00:45:24,536
>> So it will change--
so if you reason through,

1088
00:45:24,536 --> 00:45:26,706
like what I would do is
take a simple example

1089
00:45:26,706 --> 00:45:30,896
like N equals three honestly
and just think through or jot

1090
00:45:30,896 --> 00:45:33,316
down what each phrase is
and what you'll find is

1091
00:45:33,346 --> 00:45:36,686
that initially, S1 and S2 are
both bottles 'cause I'm singing

1092
00:45:36,686 --> 00:45:37,716
about three bottles of beer.

1093
00:45:37,716 --> 00:45:39,376
Take one down pass it
around, two bottles of beer,

1094
00:45:39,626 --> 00:45:40,886
but then eventually
when I'm gonna get

1095
00:45:40,886 --> 00:45:42,446
to two bottles of
beer on the wall.

1096
00:45:42,446 --> 00:45:44,276
Two bottles of beer, take
one down pass it around,

1097
00:45:44,276 --> 00:45:48,856
one bottle of beer and that's
why I need this second variable

1098
00:45:48,856 --> 00:45:50,716
to handle that silly
little grammar,

1099
00:45:50,716 --> 00:45:52,146
that little corner case.

1100
00:45:52,556 --> 00:45:54,816
But let me go ahead
and turn our attention

1101
00:45:54,816 --> 00:46:01,666
to now a similar example that we
looked at which was at the start

1102
00:46:01,666 --> 00:46:03,366
of our discussion of arrays.

1103
00:46:03,696 --> 00:46:06,076
So recall that in the
context of arrays.

1104
00:46:06,076 --> 00:46:08,336
Let me pull up the
right visual here.

1105
00:46:08,556 --> 00:46:09,406
We described arrays.

1106
00:46:09,406 --> 00:46:12,446
It's just a chunk of memory and
a chunk of contiguous memory

1107
00:46:12,446 --> 00:46:14,456
such that if you wanna
able to store 10 ints,

1108
00:46:14,766 --> 00:46:16,636
yes you can declare
ten variables

1109
00:46:16,856 --> 00:46:19,936
but very quickly does the copy
paste become clearly the wrong

1110
00:46:19,936 --> 00:46:21,986
decision if your code is
starting to look like a mess

1111
00:46:22,276 --> 00:46:24,326
and now you're changing 10
different variable names.

1112
00:46:24,556 --> 00:46:27,706
So thankfully, we introduced
to the picture this notion

1113
00:46:27,706 --> 00:46:30,076
of an array, where you can
allocate just one bigger

1114
00:46:30,076 --> 00:46:33,996
variable, break it up into
conceptually identically sized

1115
00:46:34,086 --> 00:46:36,276
parts, each of which
can store an int,

1116
00:46:36,416 --> 00:46:37,986
each of which can store a char

1117
00:46:38,226 --> 00:46:40,906
or really any other data
structure as you we'll soon see

1118
00:46:41,036 --> 00:46:43,166
and the utility of this
was that we could now take

1119
00:46:43,166 --> 00:46:47,306
in multiple types--
multiple inputs from the user

1120
00:46:47,576 --> 00:46:50,526
but store them all
essentially in the same place.

1121
00:46:50,606 --> 00:46:52,656
So let me go ahead and
open this file here,

1122
00:46:52,796 --> 00:46:55,536
array 1.C which does
exactly this

1123
00:46:55,536 --> 00:46:58,526
and introduces just a
couple of new useful tricks.

1124
00:46:58,526 --> 00:47:00,356
I've stripped out the
comments from my version

1125
00:47:00,356 --> 00:47:01,676
but you have the
comments in yours.

1126
00:47:02,006 --> 00:47:03,986
Let's see if we can wrap
our minds around some

1127
00:47:03,986 --> 00:47:05,396
of the new tricks
we're using here.

1128
00:47:05,836 --> 00:47:10,116
So notice first at the top of
this program, I'm taking main

1129
00:47:10,376 --> 00:47:13,606
as the parameter to main because
I'm not gonna use any command

1130
00:47:13,606 --> 00:47:16,226
line arguments that's the
com but now notice here,

1131
00:47:16,226 --> 00:47:19,246
I'm declaring explicitly
a float but you know what?

1132
00:47:19,246 --> 00:47:20,796
This program's purpose
in life is

1133
00:47:20,826 --> 00:47:23,766
to ask a student what their
grades are for some class

1134
00:47:24,026 --> 00:47:25,426
and then just compute
their average.

1135
00:47:25,746 --> 00:47:29,686
But the catch is I don't
necessarily wanna hard code

1136
00:47:29,686 --> 00:47:32,486
into this program
ten different ints

1137
00:47:32,486 --> 00:47:34,276
or ten different
floats for their grades.

1138
00:47:34,446 --> 00:47:37,266
I wanna store them all together
in something called an array.

1139
00:47:37,266 --> 00:47:38,556
So what's the syntax for that?

1140
00:47:38,926 --> 00:47:41,026
When we began to
see this last week,

1141
00:47:41,296 --> 00:47:43,526
when you wanna declare
an array of floats,

1142
00:47:43,756 --> 00:47:45,756
you simply say what
data type you wanna use,

1143
00:47:45,756 --> 00:47:48,536
in this case float, the name
you wanna give this variable

1144
00:47:48,596 --> 00:47:51,256
and then the new piece of syntax
last week was square brackets

1145
00:47:51,506 --> 00:47:54,046
and then inside the square
brackets needs to go a number,

1146
00:47:54,486 --> 00:47:57,016
the number of buckets
that you want.

1147
00:47:57,116 --> 00:48:00,336
The number of spots that
you wanna reserve all

1148
00:48:00,336 --> 00:48:03,786
on this picture for floating
point values in this case.

1149
00:48:04,046 --> 00:48:06,966
Now what the heck is
capital Q-U-I-Z-Z-E-S?

1150
00:48:06,966 --> 00:48:09,926
Well, this actually derives
from a trick that I did

1151
00:48:09,926 --> 00:48:12,106
up here called defining
a constant.

1152
00:48:12,466 --> 00:48:15,096
So it turns out a useful feature
in a programming language is

1153
00:48:15,096 --> 00:48:17,746
if you know in advance that you
wanna have a hard coded number

1154
00:48:17,966 --> 00:48:21,126
but you're gonna use that number
in multiple places potentially,

1155
00:48:21,156 --> 00:48:23,886
maybe in a for loop, maybe
to declare your memories,

1156
00:48:24,296 --> 00:48:26,616
maybe to allocate
memory for the array.

1157
00:48:26,886 --> 00:48:29,256
It's really nice and
really compelling to factor

1158
00:48:29,256 --> 00:48:31,796
out that constant
like two and putting

1159
00:48:31,796 --> 00:48:33,116
in something called
the constant.

1160
00:48:33,346 --> 00:48:36,546
So anytime you wanna express
the number two in this program,

1161
00:48:36,816 --> 00:48:40,516
you just say quizzes again
and again and again rather

1162
00:48:40,516 --> 00:48:42,816
than typing two here,
two here, two here.

1163
00:48:43,096 --> 00:48:45,436
Now, just intuitively even
if you're new to programming,

1164
00:48:45,636 --> 00:48:47,796
while it might be
useful to define two

1165
00:48:47,796 --> 00:48:50,976
in terms of this constant.

1166
00:48:50,976 --> 00:48:51,916
How about over here, yeah?

1167
00:48:52,286 --> 00:48:54,376
>> What if they had four
quizzes instead of two?

1168
00:48:54,376 --> 00:48:56,926
>> What if they had four quizzes
instead of two in which case?

1169
00:48:56,926 --> 00:48:59,076
>> You wouldn't have to
fix all the twos later on.

1170
00:48:59,076 --> 00:49:00,146
>> Right. It's just
utility, right?

1171
00:49:00,146 --> 00:49:02,996
I don't have to go through
my code and change my number

1172
00:49:02,996 --> 00:49:04,866
in four different
places and frankly,

1173
00:49:04,866 --> 00:49:06,936
the more places it is
the more likely I am--

1174
00:49:06,936 --> 00:49:10,646
just or if I'm tired or if
I'm just a little disoriented

1175
00:49:10,646 --> 00:49:11,636
because the code
is getting much,

1176
00:49:11,636 --> 00:49:13,576
much bigger I might miss a spot.

1177
00:49:13,576 --> 00:49:16,526
And now I'm gonna be iterating
in some loop from zero to four

1178
00:49:16,526 --> 00:49:18,946
and yet over here I'm gonna
iterate from zero to two just

1179
00:49:18,946 --> 00:49:20,306
because I didn't
change that two.

1180
00:49:20,306 --> 00:49:22,366
So factoring it out
can be both useful

1181
00:49:22,366 --> 00:49:24,906
and it can also protect you
against stupid mistakes.

1182
00:49:25,166 --> 00:49:27,406
So what are we ultimately doing
in this first line of code?

1183
00:49:27,676 --> 00:49:30,456
I'm saying float,
grades bracket quizzes.

1184
00:49:30,456 --> 00:49:33,906
So this gives me an array
that looks like this.

1185
00:49:36,766 --> 00:49:39,036
Whereby, this is 32
bits, this is two--

1186
00:49:39,036 --> 00:49:40,266
32 bits, they're back to back.

1187
00:49:40,496 --> 00:49:43,066
This whole thing is called
grades but inside each

1188
00:49:43,066 --> 00:49:46,276
of these boxes can I fit
one floating point value,

1189
00:49:46,516 --> 00:49:47,506
then you notice the comma.

1190
00:49:47,636 --> 00:49:50,336
So it turns out you can either
declare variables one at a time

1191
00:49:50,336 --> 00:49:52,696
if need be or separate
them by commas

1192
00:49:52,746 --> 00:49:53,846
if it's the same data type.

1193
00:49:54,166 --> 00:49:56,566
So I also-- because I'm gonna
be computing their average.

1194
00:49:56,796 --> 00:49:59,096
I realized that I need the
summation of some numbers,

1195
00:49:59,306 --> 00:50:02,156
so I'm also declaring a
single float called sum.

1196
00:50:02,366 --> 00:50:03,976
This is somewhere
else in memory.

1197
00:50:04,086 --> 00:50:06,386
>> It's the same
shape or the same size

1198
00:50:06,616 --> 00:50:08,196
but this thing is
called sum now.

1199
00:50:08,796 --> 00:50:10,096
It is not part of the array.

1200
00:50:10,096 --> 00:50:12,056
It might end up somewhere
else altogether.

1201
00:50:12,056 --> 00:50:14,166
Only the array is
back to back even

1202
00:50:14,166 --> 00:50:16,126
if you're code is
on the same line.

1203
00:50:16,316 --> 00:50:19,586
Well, finally, it turns out
I'm gonna need an average in I

1204
00:50:19,906 --> 00:50:23,316
and actually, let me clean this
up because I don't actually need

1205
00:50:23,316 --> 00:50:24,476
to declare these up here.

1206
00:50:24,476 --> 00:50:27,546
I'm gonna do this a little
more tightly in here just

1207
00:50:27,546 --> 00:50:31,096
to be consistent with some past
examples rather than distract.

1208
00:50:31,286 --> 00:50:33,726
Okay, so now I'm
declaring those ints only

1209
00:50:33,726 --> 00:50:34,766
when I actually need them.

1210
00:50:35,016 --> 00:50:37,326
So what-- it doesn't
matter if you do that.

1211
00:50:37,326 --> 00:50:39,216
The approach I had up there
was sort of old school.

1212
00:50:39,216 --> 00:50:40,896
This is sort of a
newer tighter approach.

1213
00:50:41,196 --> 00:50:42,346
So how does this program work?

1214
00:50:42,346 --> 00:50:44,596
First a loop, from
zero to quizzes.

1215
00:50:44,626 --> 00:50:45,886
So this thing is
gonna iterate twice,

1216
00:50:46,206 --> 00:50:48,636
print F quiz number
something of something

1217
00:50:48,926 --> 00:50:50,616
and I'm just doing
some little aesthetics.

1218
00:50:50,616 --> 00:50:53,756
I'm printing out quiz number one
of two, quiz number two of two.

1219
00:50:53,756 --> 00:50:55,516
I'm trying to be a good
user interface here

1220
00:50:55,966 --> 00:50:58,286
and then notice the syntax
for using an array and this is

1221
00:50:58,286 --> 00:50:59,356
where it's really useful.

1222
00:50:59,616 --> 00:51:03,106
Even if you're on a loop, can
you use the same exact syntax

1223
00:51:03,316 --> 00:51:06,686
to grab each and each float
from the user and just increment

1224
00:51:06,796 --> 00:51:08,446
where you are in
the square brackets?

1225
00:51:08,816 --> 00:51:12,416
So by saying grades bracket I
close bracket, that means plug

1226
00:51:12,416 --> 00:51:15,776
in through first location
I equals zero then plug

1227
00:51:15,776 --> 00:51:19,076
in to location I equals
1 then, oh that's it.

1228
00:51:19,076 --> 00:51:21,816
Because quizzes itself
is just two.

1229
00:51:22,046 --> 00:51:23,706
So the syntax really
is identical

1230
00:51:23,706 --> 00:51:24,906
to what we might
have done last week.

1231
00:51:24,936 --> 00:51:26,496
But now because we
have the ability

1232
00:51:26,496 --> 00:51:29,206
to store multiple things
back to back to back,

1233
00:51:29,676 --> 00:51:31,746
we can start using
these variables like I

1234
00:51:31,956 --> 00:51:35,186
to just move our finger on the
board, move our place holder

1235
00:51:35,186 --> 00:51:37,166
and memory to store
more and more values.

1236
00:51:37,506 --> 00:51:38,226
Now what's this?

1237
00:51:38,226 --> 00:51:44,266
Well this is kind of simple if
unnecessarily distracting syntax

1238
00:51:44,266 --> 00:51:45,886
for implementing the
notion of averaging.

1239
00:51:46,226 --> 00:51:49,716
I first initialized sum to zero
then I go ahead and iterate

1240
00:51:49,716 --> 00:51:52,136
from zero to quizzes
then I go ahead and add

1241
00:51:52,236 --> 00:51:55,446
to my summation the
first grade bracket I,

1242
00:51:55,696 --> 00:51:58,536
the second grade bracket
I and then what do I have?

1243
00:51:58,536 --> 00:51:59,676
I have the sum of their grades

1244
00:51:59,676 --> 00:52:01,676
so now I know mathematically
to get the average.

1245
00:52:01,676 --> 00:52:03,516
I take the sum divided
by the total.

1246
00:52:03,746 --> 00:52:07,506
So that's whatever their sum is
divided by two and yet what's

1247
00:52:07,506 --> 00:52:08,496
with this crazy syntax?

1248
00:52:10,206 --> 00:52:12,126
What was I actually
trying to achieve here?

1249
00:52:12,126 --> 00:52:13,466
[ Inaudible Remark ]

1250
00:52:13,466 --> 00:52:16,016
>> Yeah. So it turns out some
of you might have for P set 1,

1251
00:52:16,016 --> 00:52:18,846
maybe P set 2 have been
using the-- actually--

1252
00:52:20,076 --> 00:52:21,166
probably not for P set 2.

1253
00:52:21,606 --> 00:52:25,056
For P set 1, you probably used
or considered using something

1254
00:52:25,056 --> 00:52:27,526
like the round functions so that
you could actually round the

1255
00:52:27,526 --> 00:52:29,486
change properly when
you convert it to cents

1256
00:52:29,776 --> 00:52:32,566
or you use the round function
in the math library most likely

1257
00:52:32,566 --> 00:52:33,576
and that's perfectly fine.

1258
00:52:33,576 --> 00:52:34,746
It exists for that reason,

1259
00:52:35,046 --> 00:52:37,176
but how do you think someone
else actually implemented the

1260
00:52:37,176 --> 00:52:37,916
round function?

1261
00:52:38,136 --> 00:52:40,446
Well, it turns out with these
very simple building blocks.

1262
00:52:40,446 --> 00:52:45,176
I can take for instance the
value of sum divided by quizzes.

1263
00:52:45,406 --> 00:52:47,276
This is not gonna give
me zero 'cause remember

1264
00:52:47,276 --> 00:52:50,616
that sum was initialized as a
float so this is what I think

1265
00:52:50,686 --> 00:52:54,006
to be the notion of an average
but supposed the user's--

1266
00:52:54,536 --> 00:52:57,416
supposed the student's
average right now is

1267
00:52:57,456 --> 00:53:02,176
like 99 point let's say six,

1268
00:53:02,616 --> 00:53:05,366
99.6 on their two
quizzes, right?

1269
00:53:05,366 --> 00:53:07,686
That-- the Harvard student
would really like to get,

1270
00:53:07,686 --> 00:53:08,686
what on their final grade?

1271
00:53:09,576 --> 00:53:10,916
Like 100 percent, right?

1272
00:53:10,916 --> 00:53:14,696
99.6 gets rounded up to 100
percent, that should be my grade

1273
00:53:14,746 --> 00:53:16,926
but not in the world
of a computer.

1274
00:53:16,926 --> 00:53:18,966
If what I'm ultimately
storing in their average

1275
00:53:18,966 --> 00:53:22,086
and on their transcript is
just a number from zero to 100,

1276
00:53:22,406 --> 00:53:24,906
what's gonna end up
there, if I cast to an int?

1277
00:53:25,006 --> 00:53:25,736
>> Ninety-nine.

1278
00:53:26,076 --> 00:53:27,156
>> It's gonna go to 99, right?

1279
00:53:27,156 --> 00:53:28,716
'Cause remember when
you cast to an int,

1280
00:53:28,716 --> 00:53:30,636
you throw away everything
after the decimal point.

1281
00:53:30,636 --> 00:53:33,006
So how do you actually
round if you yourself wanted

1282
00:53:33,006 --> 00:53:34,546
to implement this
notion of rounding?

1283
00:53:34,836 --> 00:53:36,426
Well, it turns out
using a computer,

1284
00:53:36,426 --> 00:53:39,736
just add 0.5 'cause that'll
push the right students

1285
00:53:39,806 --> 00:53:41,356
over the edge, right?

1286
00:53:41,356 --> 00:53:43,906
Assuming-- ignoring some
of the imprecision issues

1287
00:53:43,906 --> 00:53:49,146
that will push a student from
99.6 to a 100.1 but damn,

1288
00:53:49,416 --> 00:53:52,966
now the int rounds them
back down to just the 100.

1289
00:53:52,966 --> 00:53:54,246
So how do you implement round?

1290
00:53:54,546 --> 00:53:57,876
You know, it looks a little
syntactically distracting

1291
00:53:58,136 --> 00:54:00,566
but it just boils down to
push them over the edge 0.5

1292
00:54:00,606 --> 00:54:03,006
and then round back
down using the casting.

1293
00:54:03,096 --> 00:54:04,606
That's all it is to round.

1294
00:54:05,596 --> 00:54:06,886
Alright, let's take
a five minute break.

1295
00:54:09,286 --> 00:54:15,586
Alright, so before we move on to
something a little more visual,

1296
00:54:15,676 --> 00:54:20,286
just an emphasis on one
detail about string.

1297
00:54:20,406 --> 00:54:22,896
So again, an array
is a little something

1298
00:54:22,896 --> 00:54:25,716
that looks conceptually like
this and thus far we know

1299
00:54:25,716 --> 00:54:27,836
that we can put floats
in there certainly.

1300
00:54:27,916 --> 00:54:29,066
We can put ints in there.

1301
00:54:29,326 --> 00:54:31,086
We can put strings in there.

1302
00:54:31,286 --> 00:54:33,876
In fact, recall our brief
discussion last week of argv

1303
00:54:33,876 --> 00:54:37,516
which you'll spend more time
with in problems set 2, argv,

1304
00:54:37,516 --> 00:54:41,056
argument vector is an array
but each of the elements

1305
00:54:41,096 --> 00:54:43,146
in that array are
themselves, what?

1306
00:54:43,486 --> 00:54:47,736
Array is technically or more
higher level, they're strings.

1307
00:54:47,736 --> 00:54:51,226
Remember argv is the second the
parameter that main can take

1308
00:54:51,476 --> 00:54:54,626
and inside of argv is every
word that the user typed

1309
00:54:54,626 --> 00:54:58,096
at the prompts and if it's every
word, that means every string

1310
00:54:58,096 --> 00:54:59,106
that they typed at the prompt.

1311
00:54:59,346 --> 00:55:01,646
So argv is an array of strings.

1312
00:55:02,186 --> 00:55:04,426
So it turns out that
in the problems

1313
00:55:04,426 --> 00:55:05,986
that you'd expect
discusses this,

1314
00:55:06,166 --> 00:55:08,266
it turns out that
a string itself

1315
00:55:08,306 --> 00:55:13,316
that we call S-T-R-I-N-G right
now itself is actually an array

1316
00:55:13,316 --> 00:55:16,466
because the string as a series
of characters is just something

1317
00:55:16,466 --> 00:55:17,966
that looks like this where each

1318
00:55:17,966 --> 00:55:19,656
of these boxes is not
a float or an int.

1319
00:55:19,656 --> 00:55:21,956
It's actually char,
char, char, char,

1320
00:55:21,956 --> 00:55:24,876
char and then a special symbol
at the very end once you're

1321
00:55:24,876 --> 00:55:27,906
at the end of a string, so
that the computer can tell.

1322
00:55:28,026 --> 00:55:29,086
The word ends here.

1323
00:55:29,286 --> 00:55:31,476
Well, let's take a look at
how we can leverage this.

1324
00:55:31,536 --> 00:55:34,546
So here is string 1.C. It's
also among your printouts.

1325
00:55:34,946 --> 00:55:37,776
Notice I'm using
my familiar CS50.H,

1326
00:55:38,036 --> 00:55:39,616
my familiar standard IO.H

1327
00:55:39,826 --> 00:55:43,506
but also another header file
called string.H. It turns

1328
00:55:43,506 --> 00:55:45,576
out you don't need string.H

1329
00:55:45,576 --> 00:55:48,526
to use the data type
string because,

1330
00:55:48,526 --> 00:55:51,206
remember that S-T-R-I-N-G
is actually declared

1331
00:55:51,206 --> 00:55:52,376
in CS50's library.

1332
00:55:52,376 --> 00:55:55,586
The reason I need string.H is
because I wanna use a function

1333
00:55:55,586 --> 00:55:57,996
that we saw briefly last
week called string length

1334
00:55:58,126 --> 00:55:59,776
or strlen for short.

1335
00:56:00,266 --> 00:56:01,486
So what does this program do?

1336
00:56:01,486 --> 00:56:02,406
Not all that much.

1337
00:56:02,406 --> 00:56:05,036
Notice that the first thing
I do, is I'm not even dealing

1338
00:56:05,036 --> 00:56:06,436
with argv and argc here.

1339
00:56:06,436 --> 00:56:07,626
I'm instead getting a string

1340
00:56:07,626 --> 00:56:10,786
from the user via CS50's
library by a GetString.

1341
00:56:11,196 --> 00:56:13,826
It turns out and we'll see
this as we peel back the layers

1342
00:56:13,826 --> 00:56:16,626
of CS50's library and
actually look at its own code.

1343
00:56:16,906 --> 00:56:20,966
It turns out that what GetString
is really returning is not a

1344
00:56:21,006 --> 00:56:22,036
string per se.

1345
00:56:22,206 --> 00:56:23,476
It's returning an array.

1346
00:56:23,706 --> 00:56:26,726
An array of characters that,
we the humans interpret

1347
00:56:26,726 --> 00:56:29,746
as a string, a word, a
sentence, a phrase, or what not.

1348
00:56:30,066 --> 00:56:33,376
So what I'm actually
storing in S is an array.

1349
00:56:34,166 --> 00:56:35,936
Now that too is a
bit of white line.

1350
00:56:35,936 --> 00:56:37,516
It's something we'll
correct over time.

1351
00:56:37,516 --> 00:56:39,756
It turns out you can't
pass a whole array.

1352
00:56:39,796 --> 00:56:42,296
This picture here, you
don't pass this whole chunk

1353
00:56:42,296 --> 00:56:44,356
of memory back and
forth, back and forth.

1354
00:56:44,356 --> 00:56:45,536
It would just be
too inefficient.

1355
00:56:45,696 --> 00:56:47,746
You have to copy way too
much data back and forth.

1356
00:56:47,996 --> 00:56:50,646
In fact, what the
computer instead does is

1357
00:56:50,646 --> 00:56:54,946
when you return an array or pass
an array it actually underneath

1358
00:56:54,946 --> 00:56:57,056
the hood just returns
the address

1359
00:56:57,446 --> 00:57:00,406
of the first chunk
of memory in ram.

1360
00:57:00,906 --> 00:57:04,976
So for instance, if this lives
at byte number zero in your ram,

1361
00:57:04,976 --> 00:57:08,456
this is byte 2, byte 3, byte
4, byte 5, and so forth right

1362
00:57:08,456 --> 00:57:09,886
in your 2 gigabytes of ram.

1363
00:57:10,156 --> 00:57:12,826
If you return an array, what
gets returned in this case

1364
00:57:12,826 --> 00:57:14,666
for this array is
the number zero.

1365
00:57:14,996 --> 00:57:17,436
Now fortunately, zero never gets
returned even though I start

1366
00:57:17,436 --> 00:57:19,196
counting at zero, there's
other more important stuff

1367
00:57:19,196 --> 00:57:21,576
at the beginning of your
computer's ram but at the end

1368
00:57:21,576 --> 00:57:23,736
of the day, each of these
chunks just represents--

1369
00:57:23,776 --> 00:57:26,346
it can be addressed by
some number in memory.

1370
00:57:26,706 --> 00:57:29,616
So just as a teaser for now,
anytime we pass a string

1371
00:57:29,616 --> 00:57:31,516
or more specifically
an array of characters,

1372
00:57:31,726 --> 00:57:33,586
we're actually just
moving addresses around.

1373
00:57:33,586 --> 00:57:36,256
And this is when we'll see the
real power of C before long

1374
00:57:36,486 --> 00:57:39,086
but also some of the security
threats in moving things

1375
00:57:39,086 --> 00:57:40,646
around by memory address.

1376
00:57:41,126 --> 00:57:43,466
So here's the little sanity
check that's now consistent

1377
00:57:43,466 --> 00:57:44,366
with that revelation.

1378
00:57:44,636 --> 00:57:48,186
It turns out that the user might
not actually give you a string.

1379
00:57:48,286 --> 00:57:50,546
If you hit Enter without
providing a string,

1380
00:57:51,086 --> 00:57:54,806
you'll actually get a very
short string that doesn't seem

1381
00:57:54,806 --> 00:57:56,946
to have any characters
but it's not null.

1382
00:57:57,226 --> 00:58:00,086
But it turns out if you hit a
certain sequence of characters

1383
00:58:00,086 --> 00:58:02,206
on you keyboard, you
can actually pretend

1384
00:58:02,206 --> 00:58:06,416
to literally give the computer
nothing including not even a

1385
00:58:06,446 --> 00:58:07,196
carriage return.

1386
00:58:07,196 --> 00:58:09,056
Not even the return
key on you keyboard.

1387
00:58:09,416 --> 00:58:11,656
So anytime we started
dealing with strings,

1388
00:58:11,656 --> 00:58:16,266
it's super important to check,
does this string actually exist?

1389
00:58:16,546 --> 00:58:18,736
And we can check if a
string actually exists

1390
00:58:18,866 --> 00:58:22,226
or it's just nothingness by
using a Boolean expression

1391
00:58:22,476 --> 00:58:26,296
and by comparing that strings
name against the special value--

1392
00:58:26,496 --> 00:58:29,356
special constant using the
jargon from the last example

1393
00:58:29,356 --> 00:58:32,816
with quizzes, a special constant
called in all caps, null.

1394
00:58:33,096 --> 00:58:35,796
So essentially, when S is null

1395
00:58:35,796 --> 00:58:38,556
and this is why I said my
strings don't actually live

1396
00:58:38,556 --> 00:58:40,256
in memory at the address zero

1397
00:58:40,546 --> 00:58:42,776
when every time we draw a
picture of a computer's ram

1398
00:58:42,776 --> 00:58:43,716
which I just keep drawing

1399
00:58:43,746 --> 00:58:46,156
for now is this big
rectangle like this.

1400
00:58:46,526 --> 00:58:49,446
It turns out that if this is
memory location zero in ram,

1401
00:58:49,726 --> 00:58:52,216
there is in fact some
important stuff that lives

1402
00:58:52,216 --> 00:58:54,916
at the bottom conceptually of
your ram and that's the reserved

1403
00:58:54,916 --> 00:58:57,736
for the operating system
which is to say a program

1404
00:58:57,736 --> 00:58:58,846
that you yourself write,

1405
00:58:59,046 --> 00:59:01,736
you should never be
handed the address zero.

1406
00:59:01,936 --> 00:59:04,086
You should never be
told, here's an array,

1407
00:59:04,086 --> 00:59:07,136
it lives at address zero
because you know in advance

1408
00:59:07,356 --> 00:59:09,836
that must belong to the
operating system, can't be mine,

1409
00:59:09,836 --> 00:59:11,496
therefore, I should
not even go there

1410
00:59:11,846 --> 00:59:14,876
and so what the world has
adopted as a convention is

1411
00:59:14,876 --> 00:59:18,026
if you ever get back
the special value null,

1412
00:59:18,186 --> 00:59:19,466
this is actually a constant

1413
00:59:19,466 --> 00:59:21,676
that represents the
notion of the number zero.

1414
00:59:21,996 --> 00:59:23,676
This means something
bad happened.

1415
00:59:23,736 --> 00:59:26,536
The user did not actually give
you a string as you requested

1416
00:59:26,746 --> 00:59:30,026
and so the computer is returning
the address of the first chunk

1417
00:59:30,026 --> 00:59:32,916
of ram which by convention
is not yours

1418
00:59:33,096 --> 00:59:35,556
which means you better
check, is that string null

1419
00:59:35,556 --> 00:59:37,216
because if it is,
don't touch it.

1420
00:59:37,496 --> 00:59:38,756
Don't start traversing it

1421
00:59:38,756 --> 00:59:40,086
as though there are
characters there.

1422
00:59:40,086 --> 00:59:42,646
So in short, null is a
special sentinal value

1423
00:59:42,646 --> 00:59:44,186
that means something
bad happened.

1424
00:59:44,526 --> 00:59:45,436
Do not proceed.

1425
00:59:45,566 --> 00:59:46,806
It's a stop sign of sorts.

1426
00:59:47,156 --> 00:59:50,156
So if it does not equal
null, then I'm safe.

1427
00:59:50,356 --> 00:59:52,536
Then I know I've been handed
conceptually a string.

1428
00:59:52,636 --> 00:59:53,786
I've been handed an array.

1429
00:59:53,856 --> 00:59:55,586
I've been handed more
technically the address

1430
00:59:56,126 --> 00:59:58,186
of a chunk of memory but
more on that next week.

1431
00:59:58,426 --> 00:59:59,456
And so I can proceed.

1432
00:59:59,716 --> 01:00:02,146
Well, my purpose in life
with this program is simply

1433
01:00:02,146 --> 01:00:04,726
to iterate over the
string, and to demonstrate

1434
01:00:04,866 --> 01:00:05,976
that a string is just an array.

1435
01:00:06,046 --> 01:00:08,236
>> And if a string
is just an array,

1436
01:00:08,236 --> 01:00:10,926
that means I can use this new
syntax using square bracket

1437
01:00:10,926 --> 01:00:14,676
notation and print out one
character at a time by iterating

1438
01:00:14,676 --> 01:00:17,506
from the zero character to
character bracket zero--

1439
01:00:17,506 --> 01:00:20,206
to bracket one, to bracket
two, to bracket three dot, dot,

1440
01:00:20,206 --> 01:00:22,896
dot up until the very last
character in the string.

1441
01:00:23,206 --> 01:00:25,466
So first, let's run
this program.

1442
01:00:25,466 --> 01:00:29,016
Make string one, I'm gonna go
ahead and now run string one

1443
01:00:29,326 --> 01:00:31,886
and I'm gonna type
in H-E-L-L-O Enter

1444
01:00:32,096 --> 01:00:34,736
and all this program does is
print out every character one

1445
01:00:34,736 --> 01:00:36,606
at a time with a
new line character.

1446
01:00:36,606 --> 01:00:37,546
How did that happen?

1447
01:00:37,546 --> 01:00:38,156
Well let's see.

1448
01:00:38,376 --> 01:00:39,566
I first do a sanity check.

1449
01:00:39,646 --> 01:00:42,006
Did the user definitely
give me a legit strength

1450
01:00:42,306 --> 01:00:44,856
because if he did, then it
won't be null, so I'm safe,

1451
01:00:45,216 --> 01:00:46,096
then I have a for loop.

1452
01:00:46,096 --> 01:00:49,606
I'm gonna iterate from I
equals zero up to I is less

1453
01:00:49,606 --> 01:00:51,596
than the length of the
strength, so I don't want to--

1454
01:00:51,596 --> 01:00:53,126
you go up to the
equals the length

1455
01:00:53,156 --> 01:00:54,826
because I again I start
counting from zero,

1456
01:00:54,826 --> 01:00:57,036
so this is old stuff,
I plus plus.

1457
01:00:57,036 --> 01:01:00,476
So this for loop means walk
across the string from left

1458
01:01:00,476 --> 01:01:01,866
to right, then what do I do?

1459
01:01:02,066 --> 01:01:05,466
I declare a charge so I have a
specific variable to play with

1460
01:01:05,686 --> 01:01:10,406
and I store in C the Ith
character in my string S,

1461
01:01:11,326 --> 01:01:14,096
that is-- the square brackets
mean go to this location

1462
01:01:14,096 --> 01:01:15,116
which is initially zero,

1463
01:01:15,346 --> 01:01:17,116
get me the first character
then do what with it?

1464
01:01:17,246 --> 01:01:19,796
We'll present C as the
place holder for print F

1465
01:01:19,826 --> 01:01:23,466
for the notion of a character,
backslash N just puts the cursor

1466
01:01:23,466 --> 01:01:25,756
on the next line and so
I print out the letter C.

1467
01:01:26,086 --> 01:01:27,876
And so all I'm doing
there is printing

1468
01:01:27,876 --> 01:01:30,006
out what the Ith character is.

1469
01:01:30,006 --> 01:01:31,646
I can be a little
more specific here.

1470
01:01:31,706 --> 01:01:35,756
Let me go ahead and
say, the let's say,

1471
01:01:35,756 --> 01:01:39,166
character number percent D is,

1472
01:01:39,196 --> 01:01:41,396
and now I can just
plug in I here, oops!

1473
01:01:41,776 --> 01:01:43,136
Now I can plug in I here,

1474
01:01:43,716 --> 01:01:45,796
so I'm gonna explicitly
say what character is what?

1475
01:01:45,796 --> 01:01:48,066
Let's-- make compile
that, rerun that,

1476
01:01:48,816 --> 01:01:51,716
hello and now it's very
explicitly telling me character

1477
01:01:51,716 --> 01:01:53,466
zero is H, character one is E

1478
01:01:53,576 --> 01:01:55,496
and notice even though
this is a five letter word,

1479
01:01:55,496 --> 01:01:56,756
there is no character five.

1480
01:01:57,016 --> 01:01:58,536
In fact if I go to five,

1481
01:01:58,536 --> 01:02:01,046
I'm gonna be stepping beyond
the boundaries of the array

1482
01:02:01,046 --> 01:02:03,926
and let's just see as a little
sneak preview what might happen.

1483
01:02:03,926 --> 01:02:06,326
Well, a common mistake would
be to this, iterate from zero

1484
01:02:06,326 --> 01:02:08,716
to the length of the string,
that's actually gonna be one

1485
01:02:08,716 --> 01:02:10,296
to many, let's recompile
with make,

1486
01:02:10,796 --> 01:02:13,826
let's rerun with
string one, hit Enter,

1487
01:02:14,236 --> 01:02:15,866
now give it a word, hello.

1488
01:02:16,586 --> 01:02:18,236
Okay, so that's not too bad.

1489
01:02:18,236 --> 01:02:20,826
It's definitely buggy but at
least nothing bad happened.

1490
01:02:20,826 --> 01:02:22,346
Now let's just do
something stupid.

1491
01:02:22,596 --> 01:02:24,486
Let's assume that the
user's always gonna type

1492
01:02:24,486 --> 01:02:26,376
in 100 character string,
just to see if we--

1493
01:02:26,376 --> 01:02:27,656
at what point the
computer breaks.

1494
01:02:27,996 --> 01:02:31,276
I recompiled with make,
I'm gonna rerun string one,

1495
01:02:31,376 --> 01:02:36,626
hit Enter, H-E-L-L-O Enter,
okay, so far not bad, right?

1496
01:02:36,626 --> 01:02:39,826
I am so far not screwing
out things too much,

1497
01:02:40,366 --> 01:02:42,356
not let's go back
in here and say,

1498
01:02:42,426 --> 01:02:44,896
you know a hundred--
let's go to 10,000.

1499
01:02:45,296 --> 01:02:46,616
Now what does this really mean?

1500
01:02:46,766 --> 01:02:50,026
This means I have typed in
to be clear and apologies

1501
01:02:50,026 --> 01:02:52,336
that the board is getting a
little messy, this just means,

1502
01:02:52,336 --> 01:02:56,086
if I've typed in H-E-L-L-O,
I only have a string

1503
01:02:56,086 --> 01:03:01,076
of length five which
means H-E-L-L-O so now,

1504
01:03:01,076 --> 01:03:02,816
let me draw a rectangle
around this thing.

1505
01:03:03,236 --> 01:03:05,826
So this means I have one byte,
another byte, another byte,

1506
01:03:05,826 --> 01:03:07,686
another byte, another
byte and then it turns

1507
01:03:07,686 --> 01:03:08,746
out even though I don't see it,

1508
01:03:08,746 --> 01:03:12,416
there's always this special
sentinal value at the end

1509
01:03:12,416 --> 01:03:16,086
of a string that I don't see but
is there, it's backslash zero

1510
01:03:16,086 --> 01:03:17,856
which is essentially
the same as null

1511
01:03:18,046 --> 01:03:19,336
but its defined a
little differently

1512
01:03:19,336 --> 01:03:23,696
so it's backslash zero, you
don't see it but it is there.

1513
01:03:23,696 --> 01:03:25,796
So the length of the
string is indeed five

1514
01:03:25,846 --> 01:03:28,556
but when I accidentally
printed out the sixth character,

1515
01:03:28,726 --> 01:03:30,226
the reason I saw
a blank line was

1516
01:03:30,256 --> 01:03:32,556
because zero doesn't have
a keyboard equivalent,

1517
01:03:32,556 --> 01:03:33,586
so it just printed as blank.

1518
01:03:33,956 --> 01:03:34,966
But now, what am I doing?

1519
01:03:34,966 --> 01:03:38,176
I just iterated from zero to a
thousand which means literally,

1520
01:03:38,176 --> 01:03:40,816
I'm going here, here,
here, here,

1521
01:03:40,816 --> 01:03:43,296
here and thankfully 'cause
this program is so short,

1522
01:03:43,296 --> 01:03:44,846
it's not doing much
with my ram at all,

1523
01:03:45,076 --> 01:03:46,076
there's just nothing there.

1524
01:03:46,076 --> 01:03:47,766
It's all blanks, its all zeros.

1525
01:03:48,126 --> 01:03:50,606
But surely, if we
really get obnoxious,

1526
01:03:50,606 --> 01:03:53,746
we can push the limit
10,000 characters that way

1527
01:03:53,746 --> 01:03:58,286
in sanders must have some data
for us, so let's run string one,

1528
01:03:58,926 --> 01:04:02,396
type in just hello again,
still not being a good demo,

1529
01:04:02,396 --> 01:04:05,706
let's keep going and
let's multiply by a factor

1530
01:04:05,706 --> 01:04:11,506
of a hundred again, rerun,
H-E-L-L-O, there we go.

1531
01:04:12,096 --> 01:04:17,906
So now, 135,000 bytes that
way there is some data

1532
01:04:17,906 --> 01:04:19,606
that really does
not belong to me.

1533
01:04:19,606 --> 01:04:20,736
The operating system owns it.

1534
01:04:20,736 --> 01:04:23,096
And the moment it detected
that I was trying to touch

1535
01:04:23,096 --> 01:04:25,936
that memory over there,
it killed my program

1536
01:04:26,146 --> 01:04:27,856
and induced what's called
the segmentation fault

1537
01:04:27,856 --> 01:04:30,146
which as we'll see before
long just means my segments

1538
01:04:30,146 --> 01:04:31,576
of memory are overlapped.

1539
01:04:31,576 --> 01:04:33,726
I'm touching memory
that is not mine.

1540
01:04:33,726 --> 01:04:35,966
Now, obviously, if your
making this kind of mistake

1541
01:04:35,966 --> 01:04:38,376
in the program there's probably
some other issues going on,

1542
01:04:38,376 --> 01:04:38,566
right?

1543
01:04:38,566 --> 01:04:41,336
'Cause this was completely
contrived but it does hint

1544
01:04:41,336 --> 01:04:43,166
at the fact that if you
don't check the boundaries

1545
01:04:43,166 --> 01:04:45,886
of your arrays bad
things can happen.

1546
01:04:45,886 --> 01:04:47,786
And again as a teaser
to security,

1547
01:04:48,046 --> 01:04:50,556
when you start allowing the user
to write anywhere in memory,

1548
01:04:50,626 --> 01:04:54,076
I could put some dangerous
code, some crack code

1549
01:04:54,076 --> 01:04:56,466
that actually compromises
the system, let's me in

1550
01:04:56,766 --> 01:04:58,646
and that's how you induce
it by plugging at places

1551
01:04:58,646 --> 01:05:08,266
that you didn't expect
there to be code.

1552
01:05:08,336 --> 01:05:08,446
Yeah?

1553
01:05:08,446 --> 01:05:11,756
>> So instead of percent C

1554
01:05:11,756 --> 01:05:15,556
for the percent D there
will we see all of the data

1555
01:05:15,556 --> 01:05:17,396
that was actually
in those bytes?

1556
01:05:17,396 --> 01:05:20,436
>> A good questions, so supposed
I print out not percent C

1557
01:05:20,436 --> 01:05:23,816
but percent D, so I print this
character, not as a character

1558
01:05:23,816 --> 01:05:28,276
but as a number which
we know is the case

1559
01:05:28,416 --> 01:05:30,366
because the numbers are chars,

1560
01:05:30,366 --> 01:05:35,046
chars are numbers underneath
the hood, it just depends

1561
01:05:35,046 --> 01:05:37,926
on how I wanna view my world.

1562
01:05:38,626 --> 01:05:40,426
Let's actually see.

1563
01:05:40,426 --> 01:05:43,836
So let me go ahead and rerun
this thing now and type

1564
01:05:43,836 --> 01:05:49,286
in hello again and if fact
they were all zeros by default

1565
01:05:49,416 --> 01:05:55,426
but the last one was something
that I should not have touched.

1566
01:05:55,426 --> 01:05:56,936
So let's go ahead and do this.

1567
01:05:57,126 --> 01:06:01,006
Let's actually start using these
things for some useful purposes,

1568
01:06:01,006 --> 01:06:05,586
sort of game show style,
I came prepared here.

1569
01:06:05,586 --> 01:06:06,856
Thanks to the teaching fellows.

1570
01:06:06,856 --> 01:06:08,546
I know, it looks fun, alright.

1571
01:06:08,546 --> 01:06:09,396
So, don't cheat.

1572
01:06:09,926 --> 01:06:13,956
Someone who did not just see one

1573
01:06:13,956 --> 01:06:16,726
of the secret things
behind the doors here,

1574
01:06:16,796 --> 01:06:20,606
I need one volunteer, as our
little teaser here, yeah,

1575
01:06:20,606 --> 01:06:21,726
in the black shirt come on up.

1576
01:06:21,726 --> 01:06:25,526
Alright, so the goal at
hand now is to transition

1577
01:06:25,526 --> 01:06:30,596
from this very low level focus
we've had the past couple

1578
01:06:30,596 --> 01:06:36,386
of lectures on syntax and on
arrays and loops and all of this

1579
01:06:36,386 --> 01:06:40,596
and now take it up
a level conceptually

1580
01:06:40,706 --> 01:06:44,656
to actually solving
real problems

1581
01:06:44,656 --> 01:06:47,966
with some of these new tricks.

1582
01:06:47,966 --> 01:06:52,346
So, I have on the board
what I claim is going

1583
01:06:52,346 --> 01:06:56,396
to be my poor man's
implementation of an array.

1584
01:06:56,996 --> 01:07:01,326
I'm using pieces of paper and
behind each of these pieces

1585
01:07:01,326 --> 01:07:04,366
of paper is a number as though,
this is an eight byte array

1586
01:07:04,366 --> 01:07:10,056
up top or an eight int array
up top, and an eight int array

1587
01:07:10,056 --> 01:07:12,766
on the bottom, and
what's your name?

1588
01:07:13,386 --> 01:07:13,586
>> Talla [phonetic].

1589
01:07:13,786 --> 01:07:14,096
>> Talla.

1590
01:07:14,096 --> 01:07:14,336
>> Yes.

1591
01:07:15,626 --> 01:07:18,456
>> Okay, nice to meet
you, so your task here

1592
01:07:18,456 --> 01:07:21,486
and I'm giving you
no foreknowledge

1593
01:07:21,636 --> 01:07:27,676
of this is find me,
let's say, the number 50

1594
01:07:27,676 --> 01:07:33,156
in the top most array,
now you, the computer,

1595
01:07:33,156 --> 01:07:36,526
or you the human
have no foreknowledge

1596
01:07:36,526 --> 01:07:37,646
of this array, do you?

1597
01:07:37,646 --> 01:07:37,726
>> No.

1598
01:07:37,786 --> 01:07:40,926
>> Okay, you were not involved
in setting this up were you?

1599
01:07:40,976 --> 01:07:47,356
Okay, so you have no idea
where the number 50 might be.

1600
01:07:48,166 --> 01:07:52,816
So I ask you, the human or
computer, however you would

1601
01:07:52,816 --> 01:07:55,376
like to think of your
self, find me the number 50

1602
01:07:55,376 --> 01:07:56,836
in the top most array
implementing

1603
01:07:56,836 --> 01:07:57,976
that process however,
you see fit.

1604
01:07:57,976 --> 01:07:58,886
Find me 50.

1605
01:07:58,886 --> 01:08:02,086
Nope. 61. Nope, 171.

1606
01:08:02,086 --> 01:08:03,836
Nope, 179.

1607
01:08:03,836 --> 01:08:05,156
Nope, 121.

1608
01:08:05,156 --> 01:08:08,006
Nope, 51. Nope, 141.

1609
01:08:08,066 --> 01:08:09,496
Yes, the number 50!

1610
01:08:09,496 --> 01:08:10,536
Excellent, very nicely done!

1611
01:08:10,536 --> 01:08:12,456
So this is where the
algorithm got clever, alright.

1612
01:08:12,456 --> 01:08:12,523
[ Laughter ]

1613
01:08:12,523 --> 01:08:12,786
>> That's good.

1614
01:08:12,896 --> 01:08:13,276
No, it's good!

1615
01:08:13,276 --> 01:08:15,446
If you-- you ruin the
whole demo if you jumped

1616
01:08:15,556 --> 01:08:17,736
to the right answer too soon.

1617
01:08:17,966 --> 01:08:21,236
So, okay, so what was
your process there

1618
01:08:21,286 --> 01:08:25,856
if you could just explain
in words and let me rather

1619
01:08:25,856 --> 01:08:31,926
than talking into my chest,
why don't you take this?

1620
01:08:31,926 --> 01:08:31,993
[ Laughter ]

1621
01:08:31,993 --> 01:08:34,986
>> I started up the first
one and I just moved down

1622
01:08:35,106 --> 01:08:37,046
and then the wind
blew that one up

1623
01:08:37,196 --> 01:08:41,026
and I saw it was
12, so I skipped it.

1624
01:08:41,026 --> 01:08:41,093
[ Laughter ]

1625
01:08:41,093 --> 01:08:41,496
>> Okay, fair enough.

1626
01:08:41,496 --> 01:08:43,766
Okay, so that's pretty
reasonable, right?

1627
01:08:43,846 --> 01:08:46,796
'Cause anytime we've coded
something involving iteration,

1628
01:08:46,796 --> 01:08:48,766
moving from something
to something else.

1629
01:08:48,766 --> 01:08:52,596
We generally start
conceptually at the left.

1630
01:08:52,596 --> 01:08:57,166
I int I gets 0 and then we plus
plus but we could have started

1631
01:08:57,386 --> 01:09:00,516
from the other end and I
was hoping you wouldn't try

1632
01:09:00,646 --> 01:09:03,276
to be clever and
start at the other end

1633
01:09:03,276 --> 01:09:04,686
and it worked out okay.

1634
01:09:04,686 --> 01:09:06,286
But this is not terribly
efficient

1635
01:09:06,286 --> 01:09:09,146
because in the worst case
here, and very deliberate case,

1636
01:09:09,146 --> 01:09:11,396
it took you as many
as what, 8 or 7 steps

1637
01:09:11,396 --> 01:09:13,536
or more generally N steps where
N is the number of doors behind

1638
01:09:13,536 --> 01:09:14,306
which there are numbers here.

1639
01:09:14,336 --> 01:09:15,956
It took you N whole steps just
to answer that question for me.

1640
01:09:15,986 --> 01:09:16,946
So I asked you could
you have done better.

1641
01:09:16,976 --> 01:09:17,636
>> Suggest a random number?

1642
01:09:17,666 --> 01:09:18,266
Like random number here?

1643
01:09:18,296 --> 01:09:19,676
>> When you put it that way,
it sounds kind of it matches

1644
01:09:19,706 --> 01:09:20,516
but yes, could you
have done better

1645
01:09:20,546 --> 01:09:21,806
in finding me the number
50 with these numbers.

1646
01:09:21,836 --> 01:09:22,256
>> I don't think so.

1647
01:09:22,286 --> 01:09:22,556
>> Okay, so no.

1648
01:09:22,586 --> 01:09:23,096
The answer is no, right?

1649
01:09:23,126 --> 01:09:24,746
With no foreknowledge of these
numbers and with no assumptions

1650
01:09:24,776 --> 01:09:25,796
to govern what algorithm
you implement,

1651
01:09:25,826 --> 01:09:26,516
you just gotta try them all.

1652
01:09:26,546 --> 01:09:27,806
You have to brute force your
way through it as we say

1653
01:09:27,836 --> 01:09:29,096
in the hacker edition of
P set 2 with passwords.

1654
01:09:29,126 --> 01:09:30,416
Alright, so what if I give you
another piece of knowledge.

1655
01:09:30,446 --> 01:09:31,826
So suppose now that you have
a second array, but this time,

1656
01:09:31,856 --> 01:09:32,846
I'm not gonna be so
difficult with you.

1657
01:09:32,876 --> 01:09:33,986
I'm gonna actually give
you some assumptions

1658
01:09:34,016 --> 01:09:34,916
that you can leverage
if you see fit,

1659
01:09:34,946 --> 01:09:36,416
and the assumption you can now
make with the second array is

1660
01:09:36,446 --> 01:09:38,126
that same numbers may very well
be there including hopefully 50

1661
01:09:38,156 --> 01:09:39,746
but I spent sometime in advance
sorting these numbers for you.

1662
01:09:39,776 --> 01:09:40,946
So now, the list is
sorted, the array is sorted,

1663
01:09:40,976 --> 01:09:41,876
what is your algorithm
now gonna be?

1664
01:09:41,906 --> 01:09:43,136
>> I'm gonna-- I think that's
the second highest number,

1665
01:09:43,166 --> 01:09:44,096
so I figure it could
be here or there.

1666
01:09:44,126 --> 01:09:44,966
Okay, so you're taking
some liberties.

1667
01:09:44,996 --> 01:09:45,566
So the only-- actually,

1668
01:09:45,596 --> 01:09:46,826
no you're not 'cause I said
you have the same numbers.

1669
01:09:46,856 --> 01:09:47,456
I didn't say that part.

1670
01:09:47,486 --> 01:09:48,626
So you have some numbers
here and I want you

1671
01:09:48,656 --> 01:09:49,706
to find the number
50 and I say this

1672
01:09:49,736 --> 01:09:51,086
because we don't wanna base
this answer on this one now.

1673
01:09:51,116 --> 01:09:52,316
So how would you now find
the number 50 knowing

1674
01:09:52,346 --> 01:09:53,066
that these numbers are sorted?

1675
01:09:53,096 --> 01:09:53,756
What algorithm would you do?

1676
01:09:53,786 --> 01:09:54,086
>> The same one.

1677
01:09:54,116 --> 01:09:54,326
>> Same one.

1678
01:09:54,356 --> 01:09:55,016
Okay, what is that same one?

1679
01:09:55,046 --> 01:09:56,636
>> Just start at one end and
move out or maybe like depending

1680
01:09:56,666 --> 01:09:57,476
on what I get on the first time.

1681
01:09:57,506 --> 01:09:57,716
>> Okay, good.

1682
01:09:57,746 --> 01:09:59,036
So this is where I need to
correct my own self here.

1683
01:09:59,066 --> 01:10:00,506
If you know a little something
about the numbers in advance,

1684
01:10:00,536 --> 01:10:01,976
obviously, alright, 50 is they
are sorted, right here, right.

1685
01:10:02,066 --> 01:10:05,206
>> This is probably 50 but if we
don't know what the numbers are,

1686
01:10:05,206 --> 01:10:07,366
but we do know that
they're sorted, right,

1687
01:10:07,366 --> 01:10:09,386
we can at least strategize
a little bit.

1688
01:10:09,386 --> 01:10:12,176
Right? Recall what I did in
the first day or what we did

1689
01:10:12,176 --> 01:10:14,066
in the first day
together which was

1690
01:10:14,066 --> 01:10:15,236
if I'm looking for Mike Smith.

1691
01:10:15,576 --> 01:10:18,206
Now, I know he is in here but I
didn't start for instance here.

1692
01:10:18,206 --> 01:10:19,516
What was my strategy then?

1693
01:10:19,856 --> 01:10:22,776
>> You opened it in half and
you saw what letter you are on.

1694
01:10:22,916 --> 01:10:24,436
>> Okay, so let's try that
approach if you would,

1695
01:10:24,436 --> 01:10:25,606
if you don't mind my
nudging you toward

1696
01:10:25,606 --> 01:10:26,906
that approach like
the phonebooks.

1697
01:10:27,266 --> 01:10:28,356
Start roughly in the middle.

1698
01:10:28,386 --> 01:10:29,696
It's not an odd number
so we can.

1699
01:10:29,696 --> 01:10:32,036
Okay, 124 and now, what
decision can you make?

1700
01:10:32,036 --> 01:10:33,596
>> I can move down or up.

1701
01:10:33,736 --> 01:10:35,556
>> Alright, so you can move
left or right, down or up,

1702
01:10:35,556 --> 01:10:36,616
and which way do you wanna go?

1703
01:10:37,296 --> 01:10:37,496
>> Down.

1704
01:10:37,496 --> 01:10:38,516
>> And because, just be clear.

1705
01:10:38,516 --> 01:10:39,416
>> Because the number is lower.

1706
01:10:39,606 --> 01:10:40,516
>> Alright, so the
number is lower.

1707
01:10:40,516 --> 01:10:41,786
Right. It might be a
statement of the obvious.

1708
01:10:41,786 --> 01:10:43,726
This is what hopefully a
reasonably intelligent human

1709
01:10:43,726 --> 01:10:47,166
being would do but the visual
takeaway here is that now,

1710
01:10:47,396 --> 01:10:48,486
right, we can literally much

1711
01:10:48,486 --> 01:10:51,086
like we threw the phonebook away
the other day, we can throw half

1712
01:10:51,086 --> 01:10:54,346
of that puzzle away because
now the problem is half

1713
01:10:54,716 --> 01:10:56,306
as big, right.

1714
01:10:56,306 --> 01:10:57,916
So now what logic are
you going to apply?

1715
01:10:59,406 --> 01:11:00,726
>> Maybe pull that up.

1716
01:11:01,216 --> 01:11:02,366
Choose something in middle here.

1717
01:11:02,466 --> 01:11:03,476
>> Okay, go for it.

1718
01:11:03,476 --> 01:11:05,316
Choose something out
of the middle there.

1719
01:11:06,106 --> 01:11:08,316
Alright, so 51, so we're closer

1720
01:11:08,516 --> 01:11:10,256
but now notice the
takeaway here.

1721
01:11:10,256 --> 01:11:13,256
Obviously, it's not 51
because the numbers are sorted.

1722
01:11:13,256 --> 01:11:15,666
We know it's gonna be this way
and so tearing off this piece

1723
01:11:15,666 --> 01:11:18,716
of paper was effectively like
tearing off this piece of paper

1724
01:11:18,716 --> 01:11:21,786
and so now the bytes you're
taking becomes significantly

1725
01:11:21,786 --> 01:11:25,046
larger than they could have
been had you not known anything

1726
01:11:25,046 --> 01:11:26,076
about their sorted order.

1727
01:11:26,306 --> 01:11:28,306
So now the problem is finally
getting whittled down to,

1728
01:11:28,306 --> 01:11:30,676
ironically, what you would
have guessed the first time

1729
01:11:30,676 --> 01:11:32,106
and we've taken 3
steps to get there

1730
01:11:32,106 --> 01:11:33,646
but what are you now gonna do?

1731
01:11:34,226 --> 01:11:34,666
>> Pull that now.

1732
01:11:35,106 --> 01:11:36,456
>> Alright, and so now we find

1733
01:11:36,666 --> 01:11:38,186
that indeed the number
50 is there,

1734
01:11:38,186 --> 01:11:40,426
we have solved this
algorithm in maybe more steps

1735
01:11:40,786 --> 01:11:43,026
than you would have had you
taken your initial instinct,

1736
01:11:43,026 --> 01:11:44,016
though I had to push you along

1737
01:11:44,296 --> 01:11:46,446
but that does ultimately
beg the question.

1738
01:11:46,446 --> 01:11:50,036
Okay, sure that was faster, sure
on day 1, I was able to churn

1739
01:11:50,036 --> 01:11:53,656
through a thousand page
phonebook in just 10 tears

1740
01:11:53,656 --> 01:11:55,506
of the book in just
10 page flips.

1741
01:11:55,736 --> 01:11:57,216
That's pretty powerful,
certainly more

1742
01:11:57,216 --> 01:11:59,736
than a thousand page turns
but we have an assumption.

1743
01:11:59,996 --> 01:12:02,296
In this case, Verizon
sorted this thing for us,

1744
01:12:02,296 --> 01:12:05,306
in this case the teaching
fellows sorted this for us

1745
01:12:05,306 --> 01:12:07,776
which then begs the question
using these new skills,

1746
01:12:07,776 --> 01:12:09,896
using these powers
in C, how can we take

1747
01:12:09,896 --> 01:12:12,496
in inputs whether it's numbers,
whether it's a billion webpages,

1748
01:12:12,726 --> 01:12:15,306
sort them and then search
them more effectively.

1749
01:12:15,306 --> 01:12:17,296
So a big round of applause, if
we could, for our volunteer.

1750
01:12:17,796 --> 01:12:20,086
[ Applause ]

1751
01:12:20,586 --> 01:12:25,606
>> And we will see
you on Wednesday.