1
00:00:00,506 --> 00:00:08,976
[ Silence ]

2
00:00:09,476 --> 00:00:12,256
>> Welcome to almost
the end of CS50.

3
00:00:12,326 --> 00:00:14,776
This is week 11.

4
00:00:14,776 --> 00:00:16,816
Week 12, as you know,
is the end game.

5
00:00:16,816 --> 00:00:19,266
So last lecture this
coming Monday.

6
00:00:19,266 --> 00:00:21,086
Quiz 1 is this coming Wednesday,

7
00:00:21,086 --> 00:00:22,326
so a few announcements
about that.

8
00:00:22,786 --> 00:00:25,486
So quiz same place as last time.

9
00:00:25,486 --> 00:00:27,486
See the hand up that's on the
website if you haven't already.

10
00:00:27,696 --> 00:00:30,796
I'll be holding those last
minute late night panick office

11
00:00:30,796 --> 00:00:32,976
hours Tuesday night in
[inaudible name] Cafe

12
00:00:32,976 --> 00:00:35,386
on the ground floor at
8 p.m. till whenever.

13
00:00:35,736 --> 00:00:37,386
If you have questions that
you would like to address

14
00:00:37,386 --> 00:00:38,606
at that point in
time, and the TF's

15
00:00:38,606 --> 00:00:40,496
and CA's have some
as well this week.

16
00:00:40,866 --> 00:00:44,246
Coming up is P set 5's deadline.

17
00:00:44,246 --> 00:00:48,326
So this little guy has yet to
have anyone submit photographs

18
00:00:48,326 --> 00:00:51,726
of him, and my God, I walked
all over campus for like 2 hours

19
00:00:51,726 --> 00:00:54,176
with that friend taking these
photographs, and I know some

20
00:00:54,176 --> 00:00:57,706
of you guys have found some of
these photos because Ken and I

21
00:00:57,706 --> 00:00:59,936
and Alex and Jansu have
all been photographed;

22
00:01:00,116 --> 00:01:02,446
but no one's actually submitted
their little map of photos.

23
00:01:02,446 --> 00:01:04,506
You have till Friday at
midnight of this week

24
00:01:04,506 --> 00:01:07,976
for that amazing prize
coming up next Monday.

25
00:01:08,246 --> 00:01:11,256
So also this week we
have this little blurb,

26
00:01:11,256 --> 00:01:16,056
the Harvard extension school has
put together this program here,

27
00:01:16,056 --> 00:01:17,656
very fancy invitation here.

28
00:01:17,656 --> 00:01:20,646
There is a panel discussion
with a number of alumni

29
00:01:20,936 --> 00:01:23,396
and fairly famous people
led by our own Harry Lewis,

30
00:01:23,396 --> 00:01:25,126
a professor in the
computer science department.

31
00:01:25,376 --> 00:01:27,986
It's entitled "No More Teachers
No More Books" higher ed

32
00:01:27,986 --> 00:01:29,206
in the networked age.

33
00:01:29,206 --> 00:01:32,356
This is this Wednesday at 4
o'clock if this interests you.

34
00:01:32,666 --> 00:01:35,606
And then they've also invited
some of us, 10 or fewer,

35
00:01:35,826 --> 00:01:37,456
to the faculty club afterwards.

36
00:01:37,456 --> 00:01:40,256
So we thought we'd turn this
into a faculty club reception

37
00:01:40,256 --> 00:01:42,476
with David and team if
you would like to join us.

38
00:01:42,476 --> 00:01:45,076
Go ahead and go to
CS50.net/rsvp.

39
00:01:45,486 --> 00:01:47,926
Among other things you'll have
chances to chat with faculty,

40
00:01:47,926 --> 00:01:50,906
myself, some of the TF's and
CA's, also Craig Silverstein

41
00:01:50,906 --> 00:01:54,526
who is Google employee number 1,
and who's actually on this panel

42
00:01:54,526 --> 00:01:55,626
that Harry is moderating.

43
00:01:55,626 --> 00:01:57,306
So take a peek at that
if you're interested.

44
00:01:57,506 --> 00:01:58,656
This, I thought,
was kind of timely.

45
00:01:58,656 --> 00:02:02,536
So I was literally riding the
T this morning, and the Metro,

46
00:02:02,536 --> 00:02:07,036
this free paper in Boston had
this ad here, or this article.

47
00:02:07,386 --> 00:02:09,806
New Best Friend for
MBTA Busriders,

48
00:02:09,806 --> 00:02:13,366
and it goes on to discuss an API
that the MBTA has just released

49
00:02:13,596 --> 00:02:16,546
in hopes, frankly, that other
people will now implement the

50
00:02:16,546 --> 00:02:18,216
rest of this tool for them.

51
00:02:18,216 --> 00:02:21,596
So they have opened up a shuttle
and API by which you can find

52
00:02:21,596 --> 00:02:25,246
out the next times of buses
actually arriving in real time.

53
00:02:25,246 --> 00:02:27,996
So not printed schedules,
but actual real time data

54
00:02:27,996 --> 00:02:28,786
for a number of the routes.

55
00:02:28,786 --> 00:02:30,946
So frankly, even if you
submitted your proposal already,

56
00:02:31,256 --> 00:02:33,436
do feel free to bite off
something that's perhaps a

57
00:02:33,536 --> 00:02:35,476
little different
if that appeals.

58
00:02:35,536 --> 00:02:39,336
Also today at 3 p.m., so
half an hour after lecture,

59
00:02:39,336 --> 00:02:42,846
Apple Computer itself is
going to be offering a seminar

60
00:02:42,846 --> 00:02:44,056
on iPhone development.

61
00:02:44,056 --> 00:02:46,576
So whether you're tackling
an iPhone app project,

62
00:02:46,576 --> 00:02:49,186
or even are just
curious, or like pizza,

63
00:02:49,456 --> 00:02:52,626
come by at 3 p.m.
Maxwell Dworkin 119.

64
00:02:52,626 --> 00:02:55,006
That's 1 floor up on the
computer science building.

65
00:02:55,006 --> 00:02:55,896
And what else?

66
00:02:55,896 --> 00:02:57,346
We got anything else here?

67
00:02:57,716 --> 00:03:00,426
OK. So I'm told UC
elections are in progress.

68
00:03:00,996 --> 00:03:05,556
And I'm a bit of a packrat when
it comes to maintaining archives

69
00:03:05,556 --> 00:03:07,916
of things, so look
at what I found.

70
00:03:08,016 --> 00:03:09,056
[ Laughter and applause ]

71
00:03:09,056 --> 00:03:10,886
So I'd like perhaps
to take a chance

72
00:03:10,886 --> 00:03:13,626
to re-declare my candidacy
some 10 years later.

73
00:03:13,896 --> 00:03:16,496
This is perhaps an example
of how not to do web design,

74
00:03:16,496 --> 00:03:19,376
or this is what happens when
you try to design a website

75
00:03:19,376 --> 00:03:21,676
around an animated gif
that you just really want

76
00:03:21,676 --> 00:03:22,816
to use for some purpose.

77
00:03:22,886 --> 00:03:26,746
If you actually click through
this you'll see my very verbose

78
00:03:26,746 --> 00:03:30,036
platform that I had at the time,
including a letter to freshmen,

79
00:03:30,136 --> 00:03:31,296
some campaign posters.

80
00:03:31,686 --> 00:03:34,726
And just to give you a little
retrospect from 10 years ago,

81
00:03:35,056 --> 00:03:38,936
the undergraduate counsel,
so this is 1996 or 1997.

82
00:03:38,936 --> 00:03:41,326
The undergraduate counsel
today suffers from 2 problems.

83
00:03:41,326 --> 00:03:42,986
Not only does the
counsel lack the attention

84
00:03:42,986 --> 00:03:45,266
of the student body, it
lacks respect as well.

85
00:03:45,596 --> 00:03:47,616
As recent voting
turnout suggests,

86
00:03:47,616 --> 00:03:48,846
most students neither know

87
00:03:48,846 --> 00:03:50,616
who their representatives
are, nor do they care.

88
00:03:51,006 --> 00:03:53,486
Lowell House, our favorite
house given the number of you

89
00:03:53,486 --> 00:03:57,036
in this class, for instance
is home to some 450 students

90
00:03:57,376 --> 00:04:00,626
yet only 25 of them
voted in 1997.

91
00:04:00,626 --> 00:04:03,226
So I do hope that things have
come a long way since then.

92
00:04:03,266 --> 00:04:07,876
This platform didn't take me
very far, clearly, but good luck

93
00:04:07,876 --> 00:04:10,666
to those in this
year's elections,

94
00:04:10,926 --> 00:04:12,676
which I gather are
now in progress.

95
00:04:12,676 --> 00:04:14,186
So please, if nothing else,

96
00:04:14,186 --> 00:04:16,066
no animated gif's in
your own projects.

97
00:04:16,306 --> 00:04:19,606
Finally, I've been told
to wear this today.

98
00:04:19,606 --> 00:04:22,756
Our own Yuki Machita has been
designing our CS50 store.

99
00:04:22,756 --> 00:04:24,016
It's store.CS50.net.

100
00:04:24,326 --> 00:04:26,696
And I'm told those
of you who celebrate,

101
00:04:26,946 --> 00:04:28,426
they make wonderful
Christmas gifts.

102
00:04:28,426 --> 00:04:30,196
So keep that in mind perhaps.

103
00:04:30,446 --> 00:04:33,446
But today is ultimately
about life after 50.

104
00:04:33,946 --> 00:04:36,236
This handout that you
have here is an excerpt

105
00:04:36,236 --> 00:04:38,356
from the course catalogue,
and all of the courses

106
00:04:38,356 --> 00:04:41,816
that you are qualified
to take after CS50;

107
00:04:41,816 --> 00:04:43,736
some of them this spring,
some of them next fall,

108
00:04:43,956 --> 00:04:46,906
and 1 or 2 of them only being
offered the spring thereafter.

109
00:04:47,156 --> 00:04:50,666
So today realize it's not just
about advertising some courses

110
00:04:50,666 --> 00:04:52,896
that we think you might want
to take, but it's also meant

111
00:04:52,996 --> 00:04:54,996
to be a little more
academic than that,

112
00:04:54,996 --> 00:04:56,236
and to give you guys a sense

113
00:04:56,386 --> 00:04:58,586
of what more there is
in computer science.

114
00:04:58,786 --> 00:05:01,466
So many of you statistically
will consider CS50

115
00:05:01,466 --> 00:05:02,866
to be a terminal course.

116
00:05:02,866 --> 00:05:03,986
You got out of it what you want,

117
00:05:04,316 --> 00:05:05,506
and that's sort of
enough for you.

118
00:05:05,776 --> 00:05:07,526
But realize that
there's a lot of holes

119
00:05:07,526 --> 00:05:08,846
that you can begin to fill in.

120
00:05:08,846 --> 00:05:11,536
Realize that this course
surveys a lot of fields,

121
00:05:11,536 --> 00:05:15,016
a lot of subfields that you can
really only begin to appreciate

122
00:05:15,016 --> 00:05:18,216
and master by taking full
fledged courses in these fields.

123
00:05:18,216 --> 00:05:21,696
So what we have today is a team
of computer science faculty

124
00:05:21,696 --> 00:05:24,576
who will be giving you a
taste, yes, of these 5 courses

125
00:05:24,576 --> 00:05:27,496
that you might take this spring
or coming fall; but also a taste

126
00:05:27,496 --> 00:05:29,016
of computer science itself.

127
00:05:29,216 --> 00:05:31,316
So realize that there's
so much more out there.

128
00:05:31,316 --> 00:05:33,016
You've only begun to
scratch the surface,

129
00:05:33,316 --> 00:05:36,396
and it really takes a good
amount of time and attention

130
00:05:36,396 --> 00:05:39,326
to really feel like
you've honed this stuff.

131
00:05:39,326 --> 00:05:40,826
So with that said, allow me

132
00:05:40,826 --> 00:05:42,656
to introduce Professor
Greg Morrisett

133
00:05:42,656 --> 00:05:46,636
who teaches computer science 51,
which is historically, sure OK,

134
00:05:46,636 --> 00:05:48,356
which is historically
the follow up...

135
00:05:49,516 --> 00:05:51,546
[ Applause ]

136
00:05:52,046 --> 00:05:55,936
... to computer science
50, and this is the course

137
00:05:55,986 --> 00:05:59,586
that I myself took as a second
course in computer science.

138
00:05:59,636 --> 00:06:01,956
So it's a little close
to my heart as well.

139
00:06:02,306 --> 00:06:03,086
>> Professor Greg
Morrisett: Thank you David.

140
00:06:03,416 --> 00:06:06,776
Good morning, afternoon...

141
00:06:07,666 --> 00:06:09,586
sorry. What is CS51?

142
00:06:09,586 --> 00:06:14,536
CS50 is entitled
something like programming.

143
00:06:14,536 --> 00:06:15,026
What's it called?

144
00:06:15,056 --> 00:06:16,706
What's the official name?

145
00:06:17,396 --> 00:06:19,566
Programming 1 or
something, introduction

146
00:06:19,566 --> 00:06:20,476
to computer science 1.

147
00:06:20,936 --> 00:06:24,116
51 has the wonderful
title of introduction

148
00:06:24,116 --> 00:06:25,426
to computer science 2.

149
00:06:26,166 --> 00:06:27,406
So what's the 2 all about?

150
00:06:27,976 --> 00:06:30,816
Well I hope most of you
realize at this point

151
00:06:30,816 --> 00:06:33,816
that programming
is not that hard.

152
00:06:34,456 --> 00:06:37,786
I teach 5th graders
sometimes how to program.

153
00:06:38,176 --> 00:06:39,616
Scratch is kind of
fun for doing that.

154
00:06:40,196 --> 00:06:41,906
What I have learned is
that you can teach just

155
00:06:41,906 --> 00:06:43,206
about anybody how to program.

156
00:06:43,696 --> 00:06:47,246
But it's very, very
hard to program well

157
00:06:47,286 --> 00:06:49,726
and that's what 51 is all about.

158
00:06:49,726 --> 00:06:52,036
It's not just programming, now
it's taking it to the next level

159
00:06:52,776 --> 00:06:54,956
and seeing how you
can program well.

160
00:06:55,226 --> 00:06:56,536
What do I mean by well?

161
00:06:57,046 --> 00:06:59,916
You need to be able to write
code that's reliable, efficient,

162
00:06:59,956 --> 00:07:02,996
that it obeys the contracts that
it has with the outside world

163
00:07:02,996 --> 00:07:05,786
in terms of correctness,
in terms of efficiency.

164
00:07:06,236 --> 00:07:07,276
It should be testable.

165
00:07:07,746 --> 00:07:10,066
The ideal code you should
be able to prove correct.

166
00:07:10,466 --> 00:07:12,116
It should be easy to maintain.

167
00:07:12,656 --> 00:07:14,686
It should be beautiful,
something you want

168
00:07:14,686 --> 00:07:17,106
to take home and
show to your mom.

169
00:07:17,106 --> 00:07:18,986
Really good code is elegant.

170
00:07:19,686 --> 00:07:21,046
And that's what 51 is about.

171
00:07:21,046 --> 00:07:22,796
The other part of 51
is that it's supposed

172
00:07:22,796 --> 00:07:26,526
to expand your problem solving
skills by making it possible

173
00:07:26,526 --> 00:07:29,886
to quickly and easily recognize
the right tool for the job.

174
00:07:30,526 --> 00:07:34,396
So the right tool might be
a data structure, algorithm.

175
00:07:34,946 --> 00:07:37,956
It may be a conceptual way to
think or frame the problem,

176
00:07:37,956 --> 00:07:41,286
or to break it up into more
easily solved subproblems.

177
00:07:41,496 --> 00:07:43,016
It may even be a
programming language.

178
00:07:43,676 --> 00:07:47,586
And the prime directive of
CS51 is that at all costs

179
00:07:47,586 --> 00:07:49,516
to be as lazy as possible.

180
00:07:50,046 --> 00:07:52,816
A really good programmer
is so lazy they will go

181
00:07:52,816 --> 00:07:56,326
out of their way to write
code to make it possible

182
00:07:56,326 --> 00:07:57,876
to not write code in the future.

183
00:07:58,666 --> 00:08:02,056
So they pull out the right
things into libraries,

184
00:08:02,056 --> 00:08:04,226
into reusable data
structures and algorithms.

185
00:08:04,856 --> 00:08:06,926
They keep interfaces
small and simple,

186
00:08:06,926 --> 00:08:10,256
and they reuse somebody
else's code whenever they can.

187
00:08:11,026 --> 00:08:13,676
But 1 other thing that they do,
and the thing that I'm going

188
00:08:13,676 --> 00:08:16,566
to highlight just today, is they
pick the right programming tool

189
00:08:16,566 --> 00:08:17,136
for the job.

190
00:08:17,136 --> 00:08:19,156
So they may pick the
right programming language

191
00:08:19,156 --> 00:08:22,306
for the job, and to give you
an idea of this I want you

192
00:08:22,306 --> 00:08:23,846
to think just for a second

193
00:08:23,846 --> 00:08:28,366
as if the Arabs had never
invented the numeric notation

194
00:08:28,366 --> 00:08:29,186
that we use today.

195
00:08:29,526 --> 00:08:31,656
And instead we were still
stuck with Roman numerals.

196
00:08:32,346 --> 00:08:35,286
Imagine trying to
write an algorithm just

197
00:08:35,336 --> 00:08:37,106
to multiply 2 Roman numerals.

198
00:08:37,946 --> 00:08:39,136
It's actually very hard to do.

199
00:08:39,746 --> 00:08:42,606
About the only way I know how to
do it, that's even reasonable,

200
00:08:42,606 --> 00:08:44,656
is to translate them first
into Arabic numerals,

201
00:08:45,286 --> 00:08:50,186
some form of numbers and do
the algorithm at that level,

202
00:08:50,236 --> 00:08:51,346
and then convert them back.

203
00:08:51,976 --> 00:08:54,356
So the way, the language
that you have

204
00:08:54,356 --> 00:08:57,186
for conceptualizing your problem
can have a strong influence

205
00:08:57,706 --> 00:09:00,676
on whether you can find a
solution and how efficient

206
00:09:00,676 --> 00:09:02,266
or how elegant the solution is.

207
00:09:03,116 --> 00:09:06,966
Now it's true that often
times we don't have the luxury

208
00:09:07,346 --> 00:09:10,436
of picking the language or
the tools that we're using

209
00:09:10,436 --> 00:09:13,176
for a particular programming
task, but if you can think

210
00:09:13,176 --> 00:09:16,506
in a different language, at
the right level of abstraction

211
00:09:16,566 --> 00:09:20,306
about a problem, and if you
understand how those mechanisms

212
00:09:20,306 --> 00:09:22,326
are realized, how
they're implemented,

213
00:09:22,566 --> 00:09:24,546
then you could take those
ideas and translate them back

214
00:09:24,586 --> 00:09:26,836
into the programming environment
that you are forced to use.

215
00:09:27,336 --> 00:09:30,116
And that happens day to day
in real programming tasks.

216
00:09:30,116 --> 00:09:33,536
It is not thinking necessarily
at the level of C code,

217
00:09:33,536 --> 00:09:35,766
but thinking at a much
higher level of abstraction

218
00:09:36,066 --> 00:09:37,696
and then be able to
decompose the problem

219
00:09:37,696 --> 00:09:38,806
and translate it back down.

220
00:09:38,976 --> 00:09:40,746
So here's a simple example.

221
00:09:41,206 --> 00:09:43,006
This is 1 of the data
structures that we'll look at.

222
00:09:43,006 --> 00:09:44,176
It's the red-black tree.

223
00:09:44,256 --> 00:09:47,476
It's a data structure that
goes back to Sedgewick and...

224
00:09:47,576 --> 00:09:48,606
Michael's laughing.

225
00:09:48,606 --> 00:09:50,316
You cover this in 124?

226
00:09:50,566 --> 00:09:52,556
Nope. That's why we do it in 51.

227
00:09:53,196 --> 00:09:55,496
So it's a balanced binary tree.

228
00:09:55,496 --> 00:09:56,396
There are many flavors of these

229
00:09:56,396 --> 00:09:58,726
like B trees, 23
trees, AVL trees.

230
00:09:59,026 --> 00:10:01,756
Very useful for representing
sets or finite maps,

231
00:10:01,756 --> 00:10:06,236
or tables when you need to have
efficient support for lookup,

232
00:10:06,236 --> 00:10:08,966
insertion, deletion,
and so forth.

233
00:10:09,796 --> 00:10:12,996
The key thing about red-black
trees is that in order

234
00:10:12,996 --> 00:10:16,446
to maintain good asymptotic
balance for lookup or insertion,

235
00:10:16,736 --> 00:10:18,136
you have to keep
the tree balanced.

236
00:10:18,656 --> 00:10:20,936
And these 2 invariants up
here, these 2 properties,

237
00:10:21,416 --> 00:10:25,956
are properties that ensure that
your tree is always bushy enough

238
00:10:25,956 --> 00:10:28,236
that you can guarantee
logarithmic access time

239
00:10:28,236 --> 00:10:29,926
for insertion or deletion.

240
00:10:30,296 --> 00:10:32,026
So these 2 invariants
say that every node,

241
00:10:32,056 --> 00:10:33,626
red node, has a red child.

242
00:10:34,286 --> 00:10:36,946
No red node has a red
child, and every path

243
00:10:36,946 --> 00:10:39,126
from the root has the same
number of black nodes.

244
00:10:39,126 --> 00:10:42,066
So it's just a way of laying out
the tree in a balanced fashion

245
00:10:42,426 --> 00:10:44,406
so that no chain is too deep.

246
00:10:44,616 --> 00:10:47,016
And if you insert
a new node and end

247
00:10:47,016 --> 00:10:50,126
up breaking these
invariants, so here we have...

248
00:10:50,626 --> 00:10:53,036
this new number, 25,
inserted into the tree.

249
00:10:53,036 --> 00:10:54,596
We've broken that invariant.

250
00:10:55,216 --> 00:10:57,696
Then you have to reorganize
the tree on the fly

251
00:10:58,066 --> 00:10:59,366
to restore the invariants.

252
00:10:59,596 --> 00:11:04,596
OK? Now the algorithms for doing
this, if you formulate them

253
00:11:04,716 --> 00:11:07,886
in 1 language they can be
very tricky to get right.

254
00:11:07,886 --> 00:11:09,036
And if you formulate them

255
00:11:09,036 --> 00:11:10,876
in another they can
actually be quite simple.

256
00:11:11,476 --> 00:11:15,206
So here is the code for doing
insertion and re-balancing

257
00:11:15,716 --> 00:11:17,526
in a high level language
called ML.

258
00:11:17,526 --> 00:11:19,096
It's a functional
programming language,

259
00:11:19,336 --> 00:11:21,086
and it's 1 of the languages
that we'll be looking at,

260
00:11:21,086 --> 00:11:24,576
and provides certain features
such as pattern matching

261
00:11:24,986 --> 00:11:26,476
on algebraic data types

262
00:11:26,506 --> 00:11:29,966
that makes writing this
code essentially a 1 pager,

263
00:11:30,056 --> 00:11:30,856
or a 1 slide.

264
00:11:31,896 --> 00:11:35,356
If you look at your favorite
algorithms textbook for example,

265
00:11:35,356 --> 00:11:38,316
Sedgewick has an algorithms
textbook, you look at the code

266
00:11:38,316 --> 00:11:42,886
for doing this and see
it's 4 times the size

267
00:11:42,886 --> 00:11:43,996
of that code up there.

268
00:11:44,166 --> 00:11:46,906
Here is the code for doing
insertion, except I ran

269
00:11:46,906 --> 00:11:49,316
out of room and actually have
to double the amount of code

270
00:11:49,316 --> 00:11:52,896
down here and repeat it
except swap red and black.

271
00:11:53,246 --> 00:11:56,616
And also I didn't show you
the subroutines, tree insert,

272
00:11:56,616 --> 00:11:58,076
left rotate and right rotate.

273
00:11:58,826 --> 00:12:00,736
This is what left
rotate looks like.

274
00:12:00,736 --> 00:12:04,316
And right rotate is just
like it except you sort

275
00:12:04,316 --> 00:12:05,766
of flip things around
and make...

276
00:12:06,826 --> 00:12:10,126
so the point is that
actually staring at this code

277
00:12:10,126 --> 00:12:11,756
and deciding whether
you've got it right,

278
00:12:11,856 --> 00:12:15,016
and whether you're respecting
those 2 properties can be very

279
00:12:15,016 --> 00:12:15,586
hard to do.

280
00:12:15,586 --> 00:12:18,016
And if you test the code,
you may find out that

281
00:12:18,016 --> 00:12:21,256
in your particular test cases
it seems to pass all the tests.

282
00:12:21,876 --> 00:12:24,366
But if you've got a
really tricky problem,

283
00:12:24,466 --> 00:12:26,226
you'd like to have
more than just testing

284
00:12:26,226 --> 00:12:27,286
as your form of assurance.

285
00:12:27,806 --> 00:12:29,726
You might like to go
back and formally prove

286
00:12:29,996 --> 00:12:32,466
that your code respects these
properties that I mentioned.

287
00:12:33,016 --> 00:12:36,046
Proving that your algorithm
is correct is pretty easy

288
00:12:36,596 --> 00:12:37,986
on 1 page of code.

289
00:12:38,726 --> 00:12:40,086
It's certainly a lot
easier than doing it

290
00:12:40,086 --> 00:12:41,966
on 4 pages of low level code.

291
00:12:42,666 --> 00:12:44,536
This code also has
other advantages.

292
00:12:44,646 --> 00:12:48,096
It's safe with respect to
exceptions, and multi threading,

293
00:12:48,476 --> 00:12:49,846
whereas the C code is not.

294
00:12:50,666 --> 00:12:53,436
And how do you get
those properties?

295
00:12:53,676 --> 00:12:56,546
Part of that is because
the language is forcing you

296
00:12:56,546 --> 00:12:57,836
into a certain discipline

297
00:12:57,836 --> 00:12:59,786
that gives you those
properties for free.

298
00:13:00,326 --> 00:13:03,356
On the other hand this code
is doing functional updates

299
00:13:03,436 --> 00:13:06,086
to a data structure,
whereas the C code is doing

300
00:13:06,086 --> 00:13:07,006
imperative updates.

301
00:13:07,816 --> 00:13:11,296
And how do you efficiently
translate a high level language

302
00:13:11,296 --> 00:13:13,916
like this down into
something like C code?

303
00:13:14,836 --> 00:13:16,826
That's something that we're
going to be looking at in 51.

304
00:13:17,196 --> 00:13:21,256
The goal in this class is to
give you an understanding,

305
00:13:21,256 --> 00:13:23,626
not just of 1 programming
language, but of a bunch

306
00:13:23,626 --> 00:13:27,066
of linguistic abstractions that
you're going to run into over

307
00:13:27,066 --> 00:13:29,066
and over again; although usually
they'll have different names

308
00:13:29,066 --> 00:13:30,516
like Microsoft will
give it some name,

309
00:13:30,516 --> 00:13:31,716
and Google will give
it a different name.

310
00:13:32,056 --> 00:13:34,236
And you want to be able to
recognize these abstractions

311
00:13:34,236 --> 00:13:36,726
and apply them wherever you are.

312
00:13:36,756 --> 00:13:39,096
You may be operating
in an OO language

313
00:13:39,096 --> 00:13:40,896
and you need the
concept of a closure.

314
00:13:41,626 --> 00:13:43,876
How can you represent
closures as objects?

315
00:13:43,876 --> 00:13:45,826
How can you represent
objects as closures?

316
00:13:46,486 --> 00:13:48,706
These are some of the ideas that
we'll be talking about in some

317
00:13:48,706 --> 00:13:51,126
of the linguistic
mechanisms like laziness,

318
00:13:51,126 --> 00:13:53,046
that we'll be using
in the class.

319
00:13:54,236 --> 00:13:56,036
We're also going to be
seeing some exposure

320
00:13:56,036 --> 00:13:57,356
to software engineering
techniques.

321
00:13:57,356 --> 00:14:00,096
I call these software
engineering in the small.

322
00:14:00,596 --> 00:14:04,396
So instead of training you
how to code 50 million lines

323
00:14:04,396 --> 00:14:07,756
of code, which is basically
something nobody knows how

324
00:14:07,756 --> 00:14:10,396
to do well, witness Microsoft.

325
00:14:10,706 --> 00:14:13,496
We're going to be talking
about at least little things

326
00:14:13,496 --> 00:14:15,616
that you can do to make
your code more readable,

327
00:14:15,616 --> 00:14:17,326
more testable, more
maintainable.

328
00:14:17,966 --> 00:14:20,116
So simple things
like modular design

329
00:14:20,116 --> 00:14:22,986
and how do you use language
mechanisms to get modularity?

330
00:14:23,496 --> 00:14:25,876
How do you do integration
and unit tests?

331
00:14:26,266 --> 00:14:29,766
And how do you read somebody's
code in a critical way?

332
00:14:29,766 --> 00:14:30,846
How do you do code reviews?

333
00:14:31,536 --> 00:14:33,696
We're also going to be
looking at abstract models

334
00:14:33,696 --> 00:14:36,656
of computation beyond simple
programming languages.

335
00:14:36,996 --> 00:14:39,836
So we'll be looking at for
example, models for space

336
00:14:39,836 --> 00:14:43,576
and time, and this is
a good prelude into 124

337
00:14:43,576 --> 00:14:44,716
which Michael will
tell you about.

338
00:14:45,116 --> 00:14:48,266
We'll be talking about models
for reasoning about code

339
00:14:48,266 --> 00:14:49,536
at a high level abstraction,

340
00:14:49,606 --> 00:14:51,636
like a substitution
model of evaluation.

341
00:14:52,066 --> 00:14:56,106
We'll also be talking about how
to prove properties of code,

342
00:14:56,106 --> 00:14:57,446
like how do you prove
the correctness?

343
00:14:57,446 --> 00:14:59,236
Or how do you prove the
asymptotic efficiency

344
00:14:59,236 --> 00:15:02,366
of your code in a very rigorous,
informal, mathematical way.

345
00:15:03,406 --> 00:15:05,906
OK, so that's really all
I have to say about 51.

346
00:15:06,376 --> 00:15:08,036
I'll be around the
whole time though,

347
00:15:08,036 --> 00:15:09,226
in case you have any questions.

348
00:15:10,096 --> 00:15:13,686
Let me now hand the
mic over to Matt Welch,

349
00:15:13,686 --> 00:15:15,136
who's another professor
in computer science,

350
00:15:15,806 --> 00:15:17,086
and he'll be telling
you about CS61.

351
00:15:17,086 --> 00:15:19,446
If there are any questions
while he's coming up here,

352
00:15:20,076 --> 00:15:20,786
I'll be happy to yield.

353
00:15:23,586 --> 00:15:24,216
No? Good.

354
00:15:25,516 --> 00:15:29,576
[ Applause ]

355
00:15:30,076 --> 00:15:32,026
>> Matt Welch: I'm
assuming there's...

356
00:15:32,026 --> 00:15:32,526
Hi everybody.

357
00:15:33,076 --> 00:15:36,786
I'm going to do the rest of this
in Latin because we are standing

358
00:15:36,786 --> 00:15:40,786
with these esteemed gentlemen
on the left and on the right.

359
00:15:40,876 --> 00:15:44,636
So what I want to do is talk
to you a little bit about CS61.

360
00:15:44,636 --> 00:15:47,716
CS61 and CS51 are like 2
sides of the same coin.

361
00:15:47,716 --> 00:15:49,276
They're both intended
to be classes

362
00:15:49,696 --> 00:15:52,336
that are taken right
after taking CS50.

363
00:15:52,416 --> 00:15:56,626
In fact a lot of freshmen are
also taking CS61 this semester.

364
00:15:57,376 --> 00:15:59,646
CS61 is an introduction
to computer systems

365
00:15:59,646 --> 00:16:01,186
and how computers
work internally.

366
00:16:01,636 --> 00:16:05,506
So the basics of the
class, we meet on Tuesdays

367
00:16:05,506 --> 00:16:08,736
and Thursdays at 2:30.

368
00:16:09,256 --> 00:16:10,756
The pre-requisite is this class,

369
00:16:10,756 --> 00:16:12,526
or just any C programming
experience.

370
00:16:12,526 --> 00:16:17,156
You can in fact use CS61 for
the CS concentration breadth

371
00:16:17,316 --> 00:16:20,756
requirement that is to satisfy
the need to have several classes

372
00:16:20,756 --> 00:16:21,916
with different middle digits.

373
00:16:22,106 --> 00:16:25,206
You can also use it
for the CS secondary.

374
00:16:25,676 --> 00:16:30,586
We generally say that most
students who have an interest

375
00:16:30,586 --> 00:16:32,256
in CS, whether you're
going to be a concentrator

376
00:16:32,526 --> 00:16:36,056
or just do the secondary,
should take both CS51 and CS61

377
00:16:36,056 --> 00:16:39,296
because they really
compliment each other nicely.

378
00:16:40,066 --> 00:16:41,406
So what's CS61 all about?

379
00:16:41,406 --> 00:16:43,686
Really this class is about
understanding the guts

380
00:16:43,686 --> 00:16:45,886
of how computers work,
getting under the hood

381
00:16:45,886 --> 00:16:49,496
and really driving down on
the things that matter to you

382
00:16:49,496 --> 00:16:51,326
as a programmer in
terms of the performance

383
00:16:51,326 --> 00:16:52,266
of the code that you write.

384
00:16:52,266 --> 00:16:56,576
So what we try to do is
understand how a processor works

385
00:16:56,576 --> 00:16:59,256
internally, and then how
do you write good C code

386
00:16:59,256 --> 00:17:02,186
that can map well onto what
the processor knows how to do.

387
00:17:02,536 --> 00:17:04,436
This is extremely
important in real world

388
00:17:04,436 --> 00:17:06,026
because in the real world
you're going to be expected

389
00:17:06,026 --> 00:17:08,106
to write programs
that perform well.

390
00:17:08,106 --> 00:17:10,126
And that are, of
course, also correct.

391
00:17:10,766 --> 00:17:13,196
We'll talk a lot about
caching and memory management.

392
00:17:13,196 --> 00:17:15,506
That is, how to lay out the
data structures in your program

393
00:17:15,846 --> 00:17:17,926
so that they give the best
performance on the processor

394
00:17:17,926 --> 00:17:20,066
and the memory architecture of
the machine that you're using.

395
00:17:20,786 --> 00:17:23,476
We'll talk a lot
about concurrency.

396
00:17:23,476 --> 00:17:28,076
So every computer that you can
buy today basically has multiple

397
00:17:28,076 --> 00:17:31,206
processors, multiple cores
on the same processor chip.

398
00:17:31,206 --> 00:17:33,446
And in order to make use
of those you generally need

399
00:17:33,446 --> 00:17:36,596
to write programs that can do
multiple things simultaneously.

400
00:17:36,956 --> 00:17:40,026
Threading and processes
are 2 straightforward ways

401
00:17:40,026 --> 00:17:41,966
of accomplishing that,
but writing this kind

402
00:17:41,966 --> 00:17:44,016
of code is very complicated
because the threads have

403
00:17:44,016 --> 00:17:44,966
to interact with each other.

404
00:17:44,966 --> 00:17:46,766
So this is 1 of these
things that you need

405
00:17:46,766 --> 00:17:47,696
to understand how to do.

406
00:17:48,126 --> 00:17:50,476
And just generally how
to write rock solid

407
00:17:50,476 --> 00:17:51,776
and fast systems codes.

408
00:17:51,776 --> 00:17:54,486
CS61 is extremely
practical if you want

409
00:17:54,486 --> 00:17:55,766
to improve your programming
skills.

410
00:17:56,696 --> 00:18:00,136
The reason that I introduced
the class is because we saw

411
00:18:00,136 --> 00:18:03,286
that there is a huge gap between
many of the concepts presented

412
00:18:03,566 --> 00:18:05,356
in computer science
classes in the reality

413
00:18:05,356 --> 00:18:06,596
of how real systems work.

414
00:18:06,596 --> 00:18:08,266
And so as you learn
how to program

415
00:18:08,266 --> 00:18:11,296
in higher level languages like
Java or ML, that you do need

416
00:18:11,296 --> 00:18:12,956
to have an understanding
of how those map

417
00:18:12,956 --> 00:18:14,226
down onto what's happening

418
00:18:14,226 --> 00:18:16,646
at the physical electronics
inside the computer.

419
00:18:17,006 --> 00:18:18,686
That's really critical
for performance.

420
00:18:18,686 --> 00:18:21,156
So you need to understand
operating system...

421
00:18:21,156 --> 00:18:23,256
you need to know these
details to understand things

422
00:18:23,256 --> 00:18:24,836
like operating systems,
databases,

423
00:18:24,836 --> 00:18:26,026
compilers, and so forth.

424
00:18:27,166 --> 00:18:30,256
Let me tell you a story that
I think motivates the need

425
00:18:30,256 --> 00:18:31,586
for a class like CS61.

426
00:18:31,586 --> 00:18:35,346
How many of you have heard
of this case of Ken Thompson

427
00:18:35,346 --> 00:18:37,586
who is 1 of the coinventors
of Unix and C,

428
00:18:37,996 --> 00:18:40,086
hacking the original
Unix system?

429
00:18:40,086 --> 00:18:41,496
Has anybody heard
this story before?

430
00:18:42,156 --> 00:18:45,476
This is a fascinating
lesson in why not

431
00:18:45,476 --> 00:18:48,076
to trust the code
that you're running.

432
00:18:48,076 --> 00:18:51,286
So Ken Thompson, he coinvented
the Unix operating system.

433
00:18:51,636 --> 00:18:53,196
He won the Turing Award,

434
00:18:53,196 --> 00:18:56,166
which is the computer
science community's equivalent

435
00:18:56,166 --> 00:18:57,246
of the Nobel Prize.

436
00:18:57,246 --> 00:18:58,956
The Turing Award is
awarded once a year

437
00:18:59,256 --> 00:19:01,326
to an emminent computer
scientist, and it's a really,

438
00:19:01,326 --> 00:19:03,126
really big deal to
win the Turing Award.

439
00:19:03,536 --> 00:19:06,536
And as part of winning
the Turing Award,

440
00:19:06,806 --> 00:19:11,126
the winner is asked to give
a lecture on their work.

441
00:19:11,126 --> 00:19:13,996
And during his Turing
Award lecture Thompson made

442
00:19:13,996 --> 00:19:14,716
the submission.

443
00:19:15,286 --> 00:19:18,396
He basically reminded people
back in the early days

444
00:19:18,396 --> 00:19:21,796
of the Unix system he
wanted to be able to log

445
00:19:21,796 --> 00:19:24,036
in into any Unix computer
that was installed,

446
00:19:24,926 --> 00:19:26,656
without having to
have an account.

447
00:19:26,656 --> 00:19:29,226
So what he did was
he hacked the log

448
00:19:29,226 --> 00:19:31,496
in program, and added
a backdoor.

449
00:19:31,826 --> 00:19:35,306
Yeah? So he added a special
password that only he knew,

450
00:19:35,636 --> 00:19:38,086
that if he tried to log in with
a password then it would let

451
00:19:38,086 --> 00:19:38,486
him in.

452
00:19:39,346 --> 00:19:44,046
Yeah, OK? And that was
really great for debugging.

453
00:19:44,266 --> 00:19:46,536
He wasn't trying to do anything
malicious with it, but he wanted

454
00:19:46,536 --> 00:19:48,056
to understand what
was going on inside.

455
00:19:48,386 --> 00:19:50,656
The problem was that
everybody had the source code,

456
00:19:50,656 --> 00:19:52,406
back in those days
everything was open source

457
00:19:52,406 --> 00:19:54,826
so if somebody happened to
look at the code for log

458
00:19:54,826 --> 00:19:55,746
in they would notice

459
00:19:55,826 --> 00:19:57,286
that there's this
backdoor in the code.

460
00:19:57,286 --> 00:19:59,276
He didn't want people
to know about this.

461
00:19:59,276 --> 00:20:01,396
He wanted to cover his tracks.

462
00:20:01,396 --> 00:20:03,936
So what he did was he
hacked the C compiler,

463
00:20:04,896 --> 00:20:07,316
and the C compiler
then understood

464
00:20:07,496 --> 00:20:12,336
when it was compiling log in.C
to add the code for the backdoor

465
00:20:12,336 --> 00:20:13,946
to it before compiling.

466
00:20:14,846 --> 00:20:16,036
Anybody see what's
going on here?

467
00:20:16,526 --> 00:20:19,766
Yeah? So if you looked
at log in.C itself,

468
00:20:19,766 --> 00:20:22,316
you would not see
the backdoor code.

469
00:20:22,706 --> 00:20:24,616
Alright, so what's the problem?

470
00:20:25,746 --> 00:20:26,876
This works right?

471
00:20:26,876 --> 00:20:28,806
So if you're looking for login.C
you won't see the backdoor,

472
00:20:28,806 --> 00:20:30,536
but there's somewhere else you
could look that you'd notice

473
00:20:30,536 --> 00:20:31,256
where the backdoor is.

474
00:20:31,256 --> 00:20:31,616
Where is it?

475
00:20:33,056 --> 00:20:34,916
In the C compiler code itself.

476
00:20:34,916 --> 00:20:36,416
Remember the source
code for everything,

477
00:20:36,416 --> 00:20:37,496
including the C compiler,

478
00:20:37,496 --> 00:20:39,566
was just sitting right
there on every Unix system.

479
00:20:39,566 --> 00:20:41,536
So you could just look at
the source of the C compiler.

480
00:20:41,646 --> 00:20:43,116
So here's what he did.

481
00:20:44,356 --> 00:20:48,206
He hacked the C compiler
to recognize

482
00:20:48,386 --> 00:20:51,286
when it was compiling itself...

483
00:20:52,776 --> 00:20:58,346
to add the code to add the code
to login.C for the backdoor.

484
00:20:58,706 --> 00:21:00,586
This is a true story.

485
00:21:00,666 --> 00:21:01,536
I'm not making this up.

486
00:21:02,026 --> 00:21:06,656
And so then he deleted that
version of the C compiler,

487
00:21:06,656 --> 00:21:09,616
so now we have a C
compiler in binary form only

488
00:21:10,826 --> 00:21:14,176
that would always,
everytime it compiled itself,

489
00:21:14,176 --> 00:21:16,456
would inject this
additional backdoor code

490
00:21:16,456 --> 00:21:18,686
into the new version
of the C compiler,

491
00:21:19,266 --> 00:21:22,306
which would then inject the
backdoor code into log in.

492
00:21:22,386 --> 00:21:24,866
OK, so this is amazing.

493
00:21:24,866 --> 00:21:26,776
This is just so cool right?

494
00:21:26,776 --> 00:21:28,596
It's just extremely nefarious.

495
00:21:28,946 --> 00:21:31,756
The only way that you would
have been able to understand

496
00:21:31,756 --> 00:21:33,546
that this was happening is
if you were able to look

497
00:21:33,546 --> 00:21:37,616
at the machine code for either
the C compiler or for the log in

498
00:21:37,616 --> 00:21:39,726
and notice that there's
this backdoor there.

499
00:21:40,006 --> 00:21:42,236
It was never present
in source code form.

500
00:21:42,236 --> 00:21:45,836
So there's no source code that
represents the backdoor anymore.

501
00:21:46,766 --> 00:21:48,756
This is an interesting problem.

502
00:21:48,996 --> 00:21:50,996
In CS61 one of the key
skills you're going

503
00:21:50,996 --> 00:21:53,236
to gain is being able
to read machine code

504
00:21:53,236 --> 00:21:55,016
and understand what the
machine code is doing.

505
00:21:55,606 --> 00:21:57,866
So what we're going
to do in CS61,

506
00:21:57,866 --> 00:21:59,146
learn how machines really work.

507
00:21:59,146 --> 00:22:01,576
You're going to really be an
expert at using things like GDB.

508
00:22:01,576 --> 00:22:04,776
We're going to debug the hardest
and the most interesting bugs.

509
00:22:04,776 --> 00:22:06,996
We're going to drive down
to the machine code level

510
00:22:06,996 --> 00:22:07,786
in order to do that.

511
00:22:08,836 --> 00:22:11,676
Hacking binaries for fun
and profit, 1 of the labs

512
00:22:11,676 --> 00:22:15,856
in the this class, I'm going
to give you a broken binary

513
00:22:15,856 --> 00:22:18,546
and you're going to
exploit a buffer overrun bug

514
00:22:18,546 --> 00:22:20,876
in that binary and
cause that binary

515
00:22:20,876 --> 00:22:22,516
to do things it was
not designed to do.

516
00:22:22,516 --> 00:22:23,836
This is basically the jist

517
00:22:23,836 --> 00:22:26,556
of how most viruses
and worms propagate.

518
00:22:26,806 --> 00:22:28,516
You're going to measure

519
00:22:28,516 --> 00:22:30,616
and improve the performance
of your programs.

520
00:22:30,616 --> 00:22:32,656
We're going to be very focused
on getting good performance,

521
00:22:32,966 --> 00:22:36,006
and you're going to write multi
threaded concurrent programs

522
00:22:36,006 --> 00:22:36,846
like a professional.

523
00:22:36,846 --> 00:22:38,006
So you're really going
to understand how

524
00:22:38,006 --> 00:22:40,336
to exploit all those
extra cycles

525
00:22:40,336 --> 00:22:41,366
and cores on your machines.

526
00:22:42,876 --> 00:22:44,696
So this sounds like
it's a lot, it's hard,

527
00:22:44,696 --> 00:22:47,006
but I want to emphasize this
is an introductory class.

528
00:22:47,006 --> 00:22:50,446
All of you can take CS61
and be successful in it.

529
00:22:50,446 --> 00:22:52,056
So it's challenging
but it's a lot of fun.

530
00:22:52,316 --> 00:22:55,236
This is not intended just for
hardcore CS concentrators.

531
00:22:56,116 --> 00:22:57,916
We have 5 lab assignments.

532
00:22:58,756 --> 00:23:00,896
The first one I give you
a binary and it asks you

533
00:23:00,896 --> 00:23:02,536
for a series of 7 passwords.

534
00:23:02,536 --> 00:23:04,106
You have to get all
7 passwords right.

535
00:23:04,686 --> 00:23:05,916
I don't give you
the source code.

536
00:23:07,216 --> 00:23:08,636
So how do you figure out
what the passwords are?

537
00:23:08,636 --> 00:23:10,296
You have to disassemble
the binary,

538
00:23:10,296 --> 00:23:11,636
read the machine instructions,

539
00:23:11,636 --> 00:23:14,096
and understand what it's
trying to ask you for.

540
00:23:14,426 --> 00:23:17,486
This is a lot of fun and
it's quite addictive.

541
00:23:17,566 --> 00:23:19,046
You'll do this buffer
overrun bug,

542
00:23:19,046 --> 00:23:20,686
you'll implement your
own version of malloc.

543
00:23:20,686 --> 00:23:22,926
I promise after doing this
you will understand how

544
00:23:22,986 --> 00:23:23,636
pointers work.

545
00:23:24,636 --> 00:23:28,156
Write your own Unix
shell and you're going

546
00:23:28,156 --> 00:23:30,786
to build your own concurrent
multi threaded internet service.

547
00:23:30,786 --> 00:23:33,436
So there will be 1
midterm exam and 1 final.

548
00:23:33,436 --> 00:23:35,256
So that's basically what
the whole course is.

549
00:23:35,746 --> 00:23:37,356
I'm going to skip over this.

550
00:23:37,356 --> 00:23:39,606
You can go look on the website
to look at the syllabus.

551
00:23:39,836 --> 00:23:41,246
And I just want to
leave you with this.

552
00:23:41,546 --> 00:23:44,356
So this is my favorite way
of representing what CS61 is.

553
00:23:44,356 --> 00:23:45,876
How many of you know
what this is from?

554
00:23:46,476 --> 00:23:47,466
This is from the Matrix.

555
00:23:47,716 --> 00:23:52,086
So this is how I think of it,
which is CS61 is the red pill.

556
00:23:52,996 --> 00:23:55,906
If you take CS61 you're going
to understand what's going

557
00:23:55,906 --> 00:23:57,366
on at all these lower levels

558
00:23:57,366 --> 00:23:58,876
of what's really
happening inside the system.

559
00:23:58,876 --> 00:24:01,036
So I encourage you to take CS61

560
00:24:01,036 --> 00:24:03,616
and I will show you how
deep the rabbit hole goes.

561
00:24:03,776 --> 00:24:03,996
Thanks.

562
00:24:05,516 --> 00:24:16,296
[ Applause ]

563
00:24:16,796 --> 00:24:21,476
>> Well we'll switch
the movie real quick.

564
00:24:22,036 --> 00:24:25,226
>> This is my former professor,
Professor Michael Mitzenmacher,

565
00:24:25,226 --> 00:24:29,876
who teaches computer
science 124.

566
00:24:30,516 --> 00:24:34,256
>> Professor Michael
Mitzenmacher: So I'm really

567
00:24:34,426 --> 00:24:40,796
into algorithms and how they
can be used in actual reality.

568
00:24:40,856 --> 00:24:43,936
So to start with I thought I'd,
before explaining the course,

569
00:24:43,996 --> 00:24:47,886
explain some of the research
I do by way of a movie;

570
00:24:48,166 --> 00:24:52,306
try and give evidence that it's
not just that we come out here

571
00:24:52,306 --> 00:24:54,556
and say yeah, algorithms
are important and useful

572
00:24:54,556 --> 00:24:56,066
and allow you to do cool things.

573
00:24:56,486 --> 00:24:58,346
But actually like to show you

574
00:24:58,346 --> 00:25:00,116
that they allow you
to do cool things.

575
00:25:00,486 --> 00:25:02,046
So hopefully this will go.

576
00:25:03,516 --> 00:25:08,856
[ Silence ]

577
00:25:09,356 --> 00:25:11,186
>> In a perfect hash
table we can look

578
00:25:11,186 --> 00:25:13,466
up any rhythm in constant time.

579
00:25:13,466 --> 00:25:16,946
We construct perfect hash
tables on the GPU using a hybrid

580
00:25:16,946 --> 00:25:18,566
of 2 randomized constructions.

581
00:25:19,296 --> 00:25:21,036
A thread is a sign to each item.

582
00:25:21,616 --> 00:25:24,946
First it leads the randomly
chosen top level hash function,

583
00:25:25,116 --> 00:25:27,356
and uses it to choose
a bucket to hash to.

584
00:25:28,006 --> 00:25:29,566
The item then commits a counter

585
00:25:29,616 --> 00:25:32,236
for it's bucket using
an atomic operation.

586
00:25:32,986 --> 00:25:35,286
We prefix on the
array of final counts,

587
00:25:36,086 --> 00:25:38,896
at which point we know a base
and an offset for each item.

588
00:25:39,606 --> 00:25:42,626
We allocate memory and then
each item writes itself

589
00:25:42,706 --> 00:25:45,456
to the location defined
by it's base plus offset.

590
00:25:46,136 --> 00:25:49,696
Within a bucket, we organize
the items using Cuckoo hashing.

591
00:25:50,426 --> 00:25:52,906
The table is broken
up into 3 subtables,

592
00:25:53,246 --> 00:25:54,956
each with it's own
hash function.

593
00:25:55,556 --> 00:25:58,426
Items that cannot fit into
the first table proceed

594
00:25:58,426 --> 00:26:00,616
to the 2nd one, and
items that cannot fit

595
00:26:00,666 --> 00:26:02,846
into the 2nd table
proceed to the 3rd.

596
00:26:02,966 --> 00:26:07,136
An item that fails to fit
into the 3rd table, like H,

597
00:26:07,136 --> 00:26:09,696
goes back to the 1st table
and evicts the item currently

598
00:26:09,826 --> 00:26:11,716
in the location that it wants.

599
00:26:11,886 --> 00:26:13,506
The eviction process continues

600
00:26:13,506 --> 00:26:15,316
until all items have
found a spot.

601
00:26:15,636 --> 00:26:17,896
Each bucket is processed
within a block.

602
00:26:18,416 --> 00:26:20,426
We write out the
Cuckoo hash tables

603
00:26:20,426 --> 00:26:23,106
with all the 1st tables
together, then all the 2nd,

604
00:26:23,106 --> 00:26:24,886
and then all the 3rd tables.

605
00:26:25,426 --> 00:26:29,716
This allows more coalesced
access for parallel lookups.

606
00:26:32,016 --> 00:26:33,646
Hash tables are useful

607
00:26:33,646 --> 00:26:35,736
for representing voxel
live surface data.

608
00:26:36,366 --> 00:26:38,916
Only the surface voxels are
stored in the hash table,

609
00:26:39,136 --> 00:26:40,896
greatly reducing the
storage requirements.

610
00:26:41,436 --> 00:26:42,836
This is called spacial hashing.

611
00:26:43,306 --> 00:26:45,396
Here we are using
spacial hashing

612
00:26:45,426 --> 00:26:47,806
to find the interception
of 2 moving surfaces.

613
00:26:48,656 --> 00:26:51,436
At every frame we read a
point cloud for each surface,

614
00:26:51,436 --> 00:26:53,026
and construct a hash table

615
00:26:53,026 --> 00:26:54,736
for the voxels containing
the points.

616
00:26:55,396 --> 00:26:58,606
We find the green intersections
by looking up the voxels

617
00:26:58,676 --> 00:27:00,686
of 1 surface and the
table of the other.

618
00:27:01,636 --> 00:27:04,736
We use the hash tables to
flood fill along the surface

619
00:27:04,956 --> 00:27:07,276
to find a blue region
inside the other object.

620
00:27:08,636 --> 00:27:10,636
Here we compute a in difference,

621
00:27:10,866 --> 00:27:12,826
subtracting 1 running
man from the other.

622
00:27:13,436 --> 00:27:15,606
The user can move the
men around interactively.

623
00:27:16,376 --> 00:27:21,446
We achieve a frame rate of about
27 frames per second using a

624
00:27:21,446 --> 00:27:25,676
virtual voxel grid of size
128 cubed with surfaces

625
00:27:25,676 --> 00:27:28,896
of roughly 160,000 points.

626
00:27:30,516 --> 00:27:34,836
[ Silence ]

627
00:27:35,336 --> 00:27:38,496
Matching is another important
application of hash tables.

628
00:27:39,136 --> 00:27:41,386
Here we have 2 different images

629
00:27:41,386 --> 00:27:43,116
of a carved relief
from Persepolis.

630
00:27:44,036 --> 00:27:45,836
We use a sobel edge detector

631
00:27:46,066 --> 00:27:48,766
to select distinctive
feature points in both images.

632
00:27:49,836 --> 00:27:52,846
We encode triples of
points from 1 image in a way

633
00:27:52,846 --> 00:27:55,166
that is invariant to
translation, rotation,

634
00:27:55,166 --> 00:27:58,196
and scaling, and store the
codes into a hash table.

635
00:27:58,946 --> 00:28:02,106
Then we look up triples from
the other image in the table.

636
00:28:02,816 --> 00:28:05,576
We find the match, we
look for a correspondence.

637
00:28:06,046 --> 00:28:09,326
In this case the top ranked
correspondence matches the 2

638
00:28:09,326 --> 00:28:10,926
images almost perfectly.

639
00:28:11,326 --> 00:28:14,236
This technique is
called geometric hashing.

640
00:28:17,446 --> 00:28:19,266
In this clip of 2
people fighting,

641
00:28:19,546 --> 00:28:21,466
you look for the following
man on the upper left.

642
00:28:23,186 --> 00:28:24,986
The graph shows the
number of votes

643
00:28:24,986 --> 00:28:27,046
for the best correspondence
in each frame.

644
00:28:27,456 --> 00:28:30,306
The best match usually aligns
the query shape to the man

645
00:28:30,306 --> 00:28:32,036
in black, but when he bends

646
00:28:32,066 --> 00:28:34,846
down the algorithm cannot
find enough matching triples.

647
00:28:35,426 --> 00:28:37,836
When there is a perfect
match we find it.

648
00:28:39,236 --> 00:28:41,486
Here we recognize
some of the monuments

649
00:28:41,516 --> 00:28:43,276
that Mac Harding dances in front

650
00:28:43,376 --> 00:28:46,226
of in a semi famous
You Tube video.

651
00:28:46,226 --> 00:28:48,176
This image of Saint
Basil's Cathedral

652
00:28:48,176 --> 00:28:50,166
at the Kremlin matches
Mac's video.

653
00:28:51,216 --> 00:28:55,806
It does not match this
Bangkok street scene.

654
00:28:56,346 --> 00:28:59,216
Here we match this image of
the Taj Mahal to the video.

655
00:28:59,216 --> 00:29:04,436
We don't get a good match at
Progue Castle, as expected.

656
00:29:05,236 --> 00:29:07,736
We match a video
frame, including buoying

657
00:29:07,736 --> 00:29:09,416
for all potential
correspondences,

658
00:29:09,706 --> 00:29:11,296
in about 2 seconds on average.

659
00:29:11,776 --> 00:29:13,526
The construction
of the hash table

660
00:29:13,526 --> 00:29:16,326
for about 3 million items
takes 44 milliseconds.

661
00:29:16,906 --> 00:29:18,096
Thank you for your attention.

662
00:29:19,516 --> 00:29:24,806
[ Applause ]

663
00:29:25,306 --> 00:29:25,616
>> Alright.

664
00:29:25,676 --> 00:29:29,116
So I'm not promising that the
end of 124 you'll be able to do

665
00:29:29,116 --> 00:29:32,406
that necessarily, but I am
promising that you'll get a lot

666
00:29:32,406 --> 00:29:34,786
of the skills that you
will need to go forward

667
00:29:35,106 --> 00:29:37,496
into your further classes
where you will be able

668
00:29:37,496 --> 00:29:39,496
to take algorithms
and data structures,

669
00:29:39,806 --> 00:29:41,536
and find cool things
to do with them.

670
00:29:41,866 --> 00:29:45,996
I view CS124 as putting the real
science in computer science,

671
00:29:46,086 --> 00:29:48,626
that it's going to give you
the tools you need to do a lot

672
00:29:48,626 --> 00:29:51,706
of really interesting things
all the way down the line.

673
00:29:53,516 --> 00:30:05,636
[ Silence ]

674
00:30:06,136 --> 00:30:08,846
Alright, so the course goal
for this is to provide everyone

675
00:30:08,846 --> 00:30:11,446
with a solid background in
algorithms and data structures

676
00:30:11,446 --> 00:30:14,526
in preparation for future
work, graduate level work,

677
00:30:14,526 --> 00:30:17,446
in algorithms, further work
in your undergraduate classes,

678
00:30:17,886 --> 00:30:19,266
or for jobs in industry.

679
00:30:19,266 --> 00:30:22,816
One of the things that I'm
always excited and relieved

680
00:30:22,816 --> 00:30:24,596
to hear afterwards is
that when people go

681
00:30:24,596 --> 00:30:27,406
out on their job interviews,
they always come back

682
00:30:27,406 --> 00:30:30,086
and tell me that they were
asked questions that have...

683
00:30:30,086 --> 00:30:32,966
exactly do with something
they learned in CS124.

684
00:30:33,306 --> 00:30:35,286
This is the sort of
skills people are looking

685
00:30:35,286 --> 00:30:37,726
for when they're looking for a
job, not just that you know how

686
00:30:37,726 --> 00:30:40,636
to program, but that you know
how to think about problems,

687
00:30:40,686 --> 00:30:43,846
that you know the ways to attack
problems, that you know the sort

688
00:30:43,846 --> 00:30:46,386
of tricks and techniques that
can be used to solve problems

689
00:30:46,686 --> 00:30:48,456
to get working code solutions.

690
00:30:48,886 --> 00:30:51,456
And so the key course goal
is to actually get you ready,

691
00:30:52,316 --> 00:30:54,266
whether this means you're
going on in your studies,

692
00:30:54,266 --> 00:30:55,736
or going on in the work world.

693
00:30:56,786 --> 00:31:02,316
So the class set up, I welcome
people from all different areas.

694
00:31:02,316 --> 00:31:05,606
Certainly the bulk of people
tend to be computer science

695
00:31:05,606 --> 00:31:07,226
and applied math concentrations,

696
00:31:07,226 --> 00:31:09,926
but we also get people every
year from biology, physics,

697
00:31:09,926 --> 00:31:13,096
economics, mathematics, and
other areas because more

698
00:31:13,096 --> 00:31:16,076
and more as other fields are
doing more and more computing,

699
00:31:16,326 --> 00:31:18,416
the people in those fields
are finding that they need

700
00:31:18,416 --> 00:31:20,456
to understand algorithms
and how they work.

701
00:31:21,236 --> 00:31:24,076
The assigments in the
class, because I do believe

702
00:31:24,076 --> 00:31:27,316
in algorithm practice and
not just algorithm theory,

703
00:31:27,316 --> 00:31:28,136
they tend to be a mix.

704
00:31:28,136 --> 00:31:30,746
There are certainly going
to be plenty of theoretical

705
00:31:30,746 --> 00:31:33,146
and mathematical work,
but we're also going

706
00:31:33,146 --> 00:31:34,586
to have programming assignments.

707
00:31:34,586 --> 00:31:38,396
My joke is I find that
this maximizes the feelings

708
00:31:38,396 --> 00:31:39,246
of unhappiness.

709
00:31:39,246 --> 00:31:41,666
The mathematicians are unhappy
because they have to program,

710
00:31:41,666 --> 00:31:43,876
and non mathematicians are
unhappy because they have

711
00:31:43,916 --> 00:31:47,356
to do math, but really is
the best way to get both ends

712
00:31:47,356 --> 00:31:49,356
to understand not
just how algorithms...

713
00:31:49,446 --> 00:31:51,706
to think about them abstractly,

714
00:31:51,706 --> 00:31:54,366
but also to implement
them and how...

715
00:31:54,366 --> 00:31:56,836
the tangible gains they
can actually get you

716
00:31:56,836 --> 00:31:57,796
in real problems.

717
00:31:58,486 --> 00:32:01,666
So this class, CS50, is
the minimum prerequisite,

718
00:32:02,436 --> 00:32:06,336
but I should point out
certainly 51 and 61,

719
00:32:06,336 --> 00:32:09,656
121 and strong math
backgrounds are all helpful

720
00:32:09,976 --> 00:32:12,036
but not at all required.

721
00:32:13,416 --> 00:32:16,806
The sort of topics we're
going to cover, a rough list.

722
00:32:16,806 --> 00:32:19,696
We'll go over graph algorithms.

723
00:32:19,696 --> 00:32:22,586
We'll go over a variety of
techniques for solving problems,

724
00:32:22,586 --> 00:32:24,206
reading algorithms,
divide and conquer,

725
00:32:24,206 --> 00:32:26,246
dynamic programming,
linear programming.

726
00:32:26,556 --> 00:32:28,176
We'll look at things
like hashing,

727
00:32:28,406 --> 00:32:30,196
something that you
just saw a video on,

728
00:32:30,196 --> 00:32:31,676
some advanced hashing
techniques.

729
00:32:32,226 --> 00:32:35,206
And randomness, how to use
randomness in algorithms,

730
00:32:35,206 --> 00:32:37,956
how to understand how randomness
can help you in algorithms.

731
00:32:38,586 --> 00:32:41,646
We'll look at MP complete
problems, and how to solve them.

732
00:32:41,996 --> 00:32:44,016
If you've learned
anything about incomplete,

733
00:32:44,016 --> 00:32:47,096
MP complete problems, that may
seem like an odd statement;

734
00:32:47,096 --> 00:32:49,866
that MP complete problems are
supposed to be the problems

735
00:32:49,866 --> 00:32:51,956
that we're not supposed
to be able to solve.

736
00:32:51,956 --> 00:32:55,476
But of course in the real world
you can't just go to your boss

737
00:32:55,476 --> 00:32:58,136
and say, well this
problem's MP complete

738
00:32:58,206 --> 00:32:59,596
so I don't have to
do it anymore.

739
00:32:59,846 --> 00:33:02,086
They're going tricks back
to solutions, so we'll come

740
00:33:02,086 --> 00:33:04,426
up with ways and
techniques in thinking

741
00:33:04,426 --> 00:33:07,266
that we'll let you solve them
for practical situations.

742
00:33:08,796 --> 00:33:12,736
Currently scheduled, if I
read the book right, Tuesday,

743
00:33:12,736 --> 00:33:14,856
Thurday 11:30 to 1:00.

744
00:33:14,856 --> 00:33:17,136
I hope you'll consider
it for this spring.

745
00:33:17,136 --> 00:33:19,986
If not I'll hope you'll consider
it for your next spring,

746
00:33:20,026 --> 00:33:22,376
offer it every year, and
I hope to see you there.

747
00:33:22,376 --> 00:33:23,096
Thanks.

748
00:33:24,516 --> 00:33:28,486
[ Applause ]

749
00:33:28,986 --> 00:33:32,066
>> So next up is going to be
Professor Hanspeter Pfister.

750
00:33:32,066 --> 00:33:35,336
He teaches computer science
171, which is visualization.

751
00:33:35,336 --> 00:33:38,606
This is actually a
course like CS61 and CS179

752
00:33:38,606 --> 00:33:41,366
that actually didn't
exist in my time.

753
00:33:41,366 --> 00:33:44,156
And to be honest it's sort of
with envy that I see what kind

754
00:33:44,156 --> 00:33:46,296
of courses they've added to the
undergraduate roster, because

755
00:33:46,296 --> 00:33:47,516
and this isn't just saying this

756
00:33:47,516 --> 00:33:49,156
because my former
professors are here,

757
00:33:49,156 --> 00:33:50,656
or because I think
I need to say this.

758
00:33:51,016 --> 00:33:53,196
A lot of these, I think,
are great fun and the fact

759
00:33:53,196 --> 00:33:54,376
that you can take these courses

760
00:33:54,376 --> 00:33:57,096
after just 50 alone is
really quite empowering.

761
00:33:57,096 --> 00:33:58,296
So, Professor Pfister.

762
00:33:59,076 --> 00:34:01,756
>> Professor Pfister: Thanks
a lot and thanks for coming.

763
00:34:02,216 --> 00:34:04,036
So I'm teaching visualization,

764
00:34:04,036 --> 00:34:06,326
so you might ask well
what is visualization?

765
00:34:06,686 --> 00:34:10,016
Visualization is essential
to convey information

766
00:34:10,436 --> 00:34:11,896
through visual representations.

767
00:34:12,186 --> 00:34:16,286
So we're talking about graphs,
charts, maps, and all kinds

768
00:34:16,286 --> 00:34:18,956
of fancy ways to visually
depict information.

769
00:34:18,956 --> 00:34:21,236
And in particular
this class will focus

770
00:34:21,236 --> 00:34:23,836
on interactive applications
of visualization

771
00:34:24,216 --> 00:34:26,486
where you can actually
interact with any of these

772
00:34:26,836 --> 00:34:27,996
in an interactive way.

773
00:34:28,576 --> 00:34:32,546
So if the previous courses
were more about the science

774
00:34:32,546 --> 00:34:35,506
of computer science,
this class is much more

775
00:34:35,506 --> 00:34:38,296
about the design and
computer science.

776
00:34:38,296 --> 00:34:40,886
So it's a combination of both
design and computer science.

777
00:34:41,376 --> 00:34:43,646
And as a matter of fact, only
about a third of the students

778
00:34:43,646 --> 00:34:46,026
in this class are
CS concentrators.

779
00:34:46,026 --> 00:34:47,956
So this is really a
class that should appeal

780
00:34:48,366 --> 00:34:51,246
to pretty much everybody because
I believe everybody is dealing

781
00:34:51,246 --> 00:34:51,966
with information.

782
00:34:52,756 --> 00:34:54,336
Now why is this class important?

783
00:34:54,726 --> 00:34:58,136
I think actually visualization
is 1 of the big topics

784
00:34:58,316 --> 00:34:59,936
that we currently
have to deal with.

785
00:35:00,376 --> 00:35:03,456
It's because we're living in the
age of information explosion.

786
00:35:03,976 --> 00:35:06,346
So we have too much
information online.

787
00:35:06,656 --> 00:35:09,866
We can't really make sense
of it all in just text form,

788
00:35:10,236 --> 00:35:12,326
and so we need some
other representations

789
00:35:12,756 --> 00:35:14,296
in order to understand it all.

790
00:35:15,026 --> 00:35:17,466
This is even more
so in the sciences

791
00:35:17,976 --> 00:35:20,866
where people have coined the
phrase 'industrial revolution

792
00:35:20,866 --> 00:35:21,416
of data'.

793
00:35:21,836 --> 00:35:25,356
So we're now able to collect
data at a much faster rate

794
00:35:25,446 --> 00:35:28,226
than what we're able to
process or comprehend.

795
00:35:28,786 --> 00:35:31,236
And that's because we have
all these great sensors

796
00:35:31,606 --> 00:35:34,806
from the very small to the
very large that provide us

797
00:35:34,806 --> 00:35:35,896
with more and more data.

798
00:35:36,666 --> 00:35:40,596
So in order to understand all
of this we need some means

799
00:35:40,966 --> 00:35:43,476
to basically look at the data,

800
00:35:43,476 --> 00:35:46,886
and this is probably the
worst possible way to do that.

801
00:35:47,316 --> 00:35:50,246
So instead of just looking
at numbers, we want to look

802
00:35:50,246 --> 00:35:51,546
at visual representations.

803
00:35:52,136 --> 00:35:55,586
And as Donald Norman, one of
the great industrial designers

804
00:35:55,736 --> 00:35:59,826
and ACI expert has said, it
is things that make us smart.

805
00:36:00,436 --> 00:36:02,826
So we learned how
to write down things

806
00:36:02,826 --> 00:36:04,196
so we can preserve history.

807
00:36:04,546 --> 00:36:06,736
We learned how to make
pictures and graphs

808
00:36:07,056 --> 00:36:10,286
so that we can understand
information and convey it.

809
00:36:10,916 --> 00:36:14,256
So this class, or I
should say visualization

810
00:36:14,256 --> 00:36:15,946
in general, will help us think.

811
00:36:16,016 --> 00:36:17,746
I hope the class will
help you think too.

812
00:36:18,256 --> 00:36:20,746
It releases the load
on working memory.

813
00:36:21,186 --> 00:36:23,276
It all floats from our cognition

814
00:36:23,276 --> 00:36:25,776
because we can literally
represent the information

815
00:36:25,826 --> 00:36:26,756
in a different medium.

816
00:36:27,206 --> 00:36:29,496
And it uses the power
of human perception.

817
00:36:29,866 --> 00:36:33,686
So as you may know, our visual
system is the biggest sensory

818
00:36:33,686 --> 00:36:37,096
organ and it's represented
in our brain with about half

819
00:36:37,096 --> 00:36:39,786
of the neurons in the brain,
so we have a huge amount

820
00:36:39,786 --> 00:36:42,486
of perceptual power
that we can actually use

821
00:36:42,536 --> 00:36:43,666
to understand information.

822
00:36:44,746 --> 00:36:48,796
So the goals of the class are to
teach you the principles of how

823
00:36:48,796 --> 00:36:51,366
to make effective
graphs, charts, maps,

824
00:36:51,366 --> 00:36:55,536
and visualizations; and then how
to teach you to gather the data,

825
00:36:55,666 --> 00:36:57,596
in particular from
online sources.

826
00:36:58,046 --> 00:37:00,226
So we're going to teach
you how to use Python,

827
00:37:00,546 --> 00:37:03,776
which is a very nice and simple
to learn scripting language,

828
00:37:04,086 --> 00:37:06,236
to scrape information
from webpages.

829
00:37:06,886 --> 00:37:10,016
And then using that
information that you gathered,

830
00:37:10,016 --> 00:37:13,626
implement interactive
visualizations using a Java

831
00:37:13,626 --> 00:37:15,136
framework called processing.

832
00:37:15,776 --> 00:37:18,126
And again, processing is
relatively easy to learn.

833
00:37:19,176 --> 00:37:22,436
And finally we have a
few programming homeworks

834
00:37:22,436 --> 00:37:25,786
and a final project where you
can put all of those skills

835
00:37:25,856 --> 00:37:27,596
that you're learning
in the class to use.

836
00:37:28,226 --> 00:37:30,816
So what I'd like to do next
is show you a few projects

837
00:37:30,856 --> 00:37:33,056
that students have
done last year.

838
00:37:33,116 --> 00:37:35,446
And I'm going to start
with Jason Gowell.

839
00:37:35,966 --> 00:37:39,836
So Jason actually in all
this, the students start

840
00:37:39,836 --> 00:37:42,626
with a question study
of personal interest.

841
00:37:43,306 --> 00:37:45,476
I'm sorry I can't fit it
all on the screen right now,

842
00:37:45,476 --> 00:37:49,036
but he started with the question
'what is the energy used

843
00:37:49,036 --> 00:37:51,196
of the different buildings
on the Harvard campus?'

844
00:37:51,856 --> 00:37:53,186
And it turns out that

845
00:37:53,186 --> 00:37:54,956
that information is
actually available

846
00:37:54,956 --> 00:37:57,676
from the Harvard Office of...

847
00:37:57,826 --> 00:37:59,076
what is it called...

848
00:37:59,866 --> 00:38:02,276
I guess of Public Buildings.

849
00:38:02,736 --> 00:38:06,586
So what he did is he
plotted the yearly energy use

850
00:38:06,816 --> 00:38:08,016
of the different buildings

851
00:38:08,086 --> 00:38:11,646
on the map using circles
representing the size

852
00:38:12,046 --> 00:38:13,046
of the energy use.

853
00:38:13,626 --> 00:38:16,196
And as you may be able
to see here on the right,

854
00:38:16,486 --> 00:38:17,866
he also has a pie chart

855
00:38:17,866 --> 00:38:20,566
that shows you how the
different buildings use

856
00:38:20,566 --> 00:38:23,356
that energy depending
on the type of energy.

857
00:38:23,766 --> 00:38:24,986
So let me move this over.

858
00:38:25,456 --> 00:38:30,166
So green is electricity, red is
steam, blue is chilled water.

859
00:38:30,646 --> 00:38:34,326
And you can see that depending
on the building shown up here

860
00:38:34,326 --> 00:38:38,666
with their name, you have very
different energy usage patterns.

861
00:38:39,306 --> 00:38:42,636
And as a matter of fact,
if I were able to scroll,

862
00:38:42,976 --> 00:38:46,796
you could actually see that this
energy usage pattern changes

863
00:38:46,936 --> 00:38:47,696
over the years.

864
00:38:47,696 --> 00:38:50,156
So down here he has
a visualization

865
00:38:50,156 --> 00:38:52,706
of how this changes over
the course of the year,

866
00:38:53,276 --> 00:38:56,446
and the pie chart up there
will automatically update.

867
00:38:57,406 --> 00:39:00,796
Now going back here, let me
just show you the last bit

868
00:39:00,796 --> 00:39:04,526
of the visualization, which
is you also have a list view

869
00:39:05,006 --> 00:39:10,166
that shows you the biggest
and smallest energy consumers

870
00:39:10,226 --> 00:39:11,936
on the Harvard campus over here.

871
00:39:12,396 --> 00:39:15,756
And again, depending
on the time of year,

872
00:39:16,196 --> 00:39:18,236
you have different buildings

873
00:39:18,286 --> 00:39:19,756
that use different
amounts of energy.

874
00:39:20,236 --> 00:39:22,026
So this was an effective
visualization

875
00:39:22,026 --> 00:39:24,426
to show you the energy
usage on the Harvard campus.

876
00:39:27,076 --> 00:39:30,736
Next project I'd like to show
is by Navin Sinha [phonetic].

877
00:39:31,186 --> 00:39:34,916
Navin was interested in
finding good restaurants

878
00:39:34,916 --> 00:39:36,676
in the Cambridge
and Boston area.

879
00:39:37,216 --> 00:39:39,776
And instead of just building
yet another visualization

880
00:39:39,776 --> 00:39:45,406
of the ratings, he actually went
to the different newspapers here

881
00:39:45,406 --> 00:39:48,416
in town, Boston Magazine,
Boston Globe, Boston Herald,

882
00:39:48,416 --> 00:39:52,136
and Boston Phoenix, and
he computed an average,

883
00:39:52,136 --> 00:39:55,306
or compound score for
each of the restaurants

884
00:39:55,346 --> 00:39:56,806
that those newspapers rate.

885
00:39:57,416 --> 00:39:59,896
And then what he's showing
here is the deviation

886
00:40:00,156 --> 00:40:03,486
from this average score between
the different newspapers.

887
00:40:03,976 --> 00:40:06,766
So let's quickly look at that.

888
00:40:07,516 --> 00:40:11,576
[ Silence ]

889
00:40:12,076 --> 00:40:14,446
So here again is
this visualization.

890
00:40:14,996 --> 00:40:16,766
Let's first turn
off the filter here.

891
00:40:16,766 --> 00:40:21,446
You can actually see the
name of the restaurant here.

892
00:40:21,766 --> 00:40:25,386
So number 1 is Hoya,
followed Les [inaudible name],

893
00:40:25,386 --> 00:40:28,826
followed by Number 9,
followed by Uni, and so on.

894
00:40:29,136 --> 00:40:31,406
So for those of you
who like to eat well,

895
00:40:31,406 --> 00:40:33,246
you probably recognize
some of these names.

896
00:40:33,286 --> 00:40:36,186
So the restaurants are
ordered from right to left,

897
00:40:36,626 --> 00:40:39,836
the top ranked restaurant
on the average rating being

898
00:40:39,836 --> 00:40:41,236
on the right most side.

899
00:40:41,826 --> 00:40:43,506
But then he's showing
the deviation.

900
00:40:44,346 --> 00:40:48,586
Bars that go above the line show
that this particular newspaper,

901
00:40:48,586 --> 00:40:52,636
for example Boston Magazine,
has ranked this restaurant here,

902
00:40:52,636 --> 00:40:57,556
Aura, on average higher than
the compound average score

903
00:40:57,556 --> 00:40:58,996
of all of the ratings.

904
00:40:59,566 --> 00:41:02,016
And similarly some of
them are ranked lower.

905
00:41:02,416 --> 00:41:04,946
So you might see for example
the Boston Herald seems

906
00:41:04,946 --> 00:41:06,926
to be more critical of
some of the restaurants

907
00:41:06,956 --> 00:41:08,846
that are typically
ranked highly,

908
00:41:09,326 --> 00:41:13,286
and then some others are ranked
a little better over here.

909
00:41:13,776 --> 00:41:16,146
Then you can look at the
different categories.

910
00:41:16,146 --> 00:41:18,656
So here are the inexpensive
restaurants.

911
00:41:19,096 --> 00:41:21,136
You might find out that Garden

912
00:41:21,136 --> 00:41:25,746
at the Cellar is a very good
value if you like good food

913
00:41:25,746 --> 00:41:27,176
and don't want to
spend so much money.

914
00:41:27,706 --> 00:41:30,686
You can conversely look at
the expensive restaurants.

915
00:41:31,006 --> 00:41:34,466
Not surprisingly, most of them
are here in the top category.

916
00:41:34,976 --> 00:41:37,866
I'm sorry, you can't
really see some of the bars

917
00:41:37,866 --> 00:41:41,156
on this projector, but I'll
just show you these are all top

918
00:41:41,156 --> 00:41:42,226
ranked and expensive.

919
00:41:42,716 --> 00:41:46,996
But then this one here,
Moo, is actually expensive

920
00:41:47,066 --> 00:41:49,316
but doesn't get such a
good compound ranking.

921
00:41:49,316 --> 00:41:51,556
So it might not be such a
great value for your money.

922
00:41:52,396 --> 00:41:55,946
You may want to find out which
cuisine is ranked highest,

923
00:41:55,946 --> 00:41:59,666
and it turns out
Japanese actually is...

924
00:42:00,216 --> 00:42:04,606
Oya and Uni and the
Oshi suishi bar.

925
00:42:05,106 --> 00:42:08,566
They're all ranked
very highly, and so on.

926
00:42:09,496 --> 00:42:11,976
Let me show you another
example from last year.

927
00:42:13,226 --> 00:42:18,596
Karen Hanson, she works
in the microcellular

928
00:42:18,736 --> 00:42:23,546
and biology laboratory and she's
going to apply to grad school,

929
00:42:23,546 --> 00:42:27,266
and she wanted to find out
how are the different MCB labs

930
00:42:27,266 --> 00:42:30,436
around the country
deal with admissions.

931
00:42:31,026 --> 00:42:34,076
So she put together this
nice visualization...

932
00:42:35,176 --> 00:42:38,836
again I probably cannot
move this, I'm sorry.

933
00:42:38,836 --> 00:42:40,896
But she put together
a nice visualization

934
00:42:40,896 --> 00:42:45,366
of admissions based on
different schools and based

935
00:42:45,366 --> 00:42:48,466
around the country, showing
you what are the areas

936
00:42:48,466 --> 00:42:50,346
where admissions
are relatively high.

937
00:42:50,516 --> 00:42:52,346
So definitely California
is 1 of them,

938
00:42:52,766 --> 00:42:54,046
Massachusetts being another.

939
00:42:54,446 --> 00:42:56,576
And then showing you
the sort of statistics

940
00:42:56,576 --> 00:42:59,776
of the typical student that
gets into these programs.

941
00:43:00,486 --> 00:43:02,786
And then over here she
also has more information

942
00:43:02,786 --> 00:43:05,986
about each school, how many
students they admit per year,

943
00:43:06,316 --> 00:43:09,746
and what kind of characteristics
that each school is looking for.

944
00:43:09,746 --> 00:43:13,426
And then also the top faculty in
the country that admit students

945
00:43:13,426 --> 00:43:16,276
in MCB, and what kind of profile

946
00:43:16,276 --> 00:43:17,676
that they're typically
looking for.

947
00:43:18,916 --> 00:43:22,126
So lastly related to
this, there was a project

948
00:43:22,196 --> 00:43:25,726
by Shao Hai [phonetic] who
also was interested in MCB,

949
00:43:25,726 --> 00:43:29,696
but he looked at the
publication records of faculty

950
00:43:30,246 --> 00:43:31,686
at MCB here at Harvard.

951
00:43:32,436 --> 00:43:35,586
What he did, he has a
visualization showing you the

952
00:43:35,586 --> 00:43:39,736
different publications
that the faculty have.

953
00:43:39,736 --> 00:43:41,956
So you have the list of
faculty here on the right,

954
00:43:42,686 --> 00:43:46,186
and then the size of the circle
shows you how many papers a year

955
00:43:46,426 --> 00:43:47,176
they published.

956
00:43:47,546 --> 00:43:48,996
You can see the legion,
but I happen

957
00:43:48,996 --> 00:43:51,406
to know the big circle
is 30 papers a year.

958
00:43:52,156 --> 00:43:54,936
So this professor here had
30 publications a year.

959
00:43:55,306 --> 00:43:58,536
The X axis is numbers
of years since PhD,

960
00:43:58,856 --> 00:44:00,146
so this is a senior person,

961
00:44:00,146 --> 00:44:02,236
and here is actually
a more junior person.

962
00:44:02,736 --> 00:44:05,866
And the Y axis is if
they were a senior author

963
00:44:05,866 --> 00:44:09,376
or a junior author, i.e.
first author on the paper.

964
00:44:09,836 --> 00:44:12,166
So you can see some of the
more junior faculty tend

965
00:44:12,166 --> 00:44:15,566
to put themselves as first
authors, whereas most

966
00:44:15,566 --> 00:44:17,856
of the senior faculty
tend to be senior authors.

967
00:44:19,076 --> 00:44:21,676
Again he was interested in
this particular question.

968
00:44:21,936 --> 00:44:26,256
He also did a timeline
of publications over time

969
00:44:26,256 --> 00:44:27,426
for each of the faculty.

970
00:44:27,426 --> 00:44:30,456
So you can see that the
senior faculty tend to peter

971
00:44:30,456 --> 00:44:35,306
out after a certain number of
years of being in the business.

972
00:44:36,256 --> 00:44:38,696
So I think these were
some really fun examples

973
00:44:38,696 --> 00:44:39,496
from last year.

974
00:44:39,956 --> 00:44:42,026
I invite you to go
to the website

975
00:44:42,026 --> 00:44:43,386
and you'll see a lot more.

976
00:44:43,916 --> 00:44:46,836
And I also want to briefly
mention the topics we'll cover.

977
00:44:47,146 --> 00:44:50,176
We'll talk about perception,
sort of the fundamentals

978
00:44:50,206 --> 00:44:52,866
of interaction, design,
and visual design.

979
00:44:53,316 --> 00:44:57,756
And then we'll talk about
different visualization types

980
00:44:58,216 --> 00:45:00,896
such as graphs, maps,
trees and networks.

981
00:45:01,406 --> 00:45:03,946
We talk about how to visualize
high dimensional data.

982
00:45:04,016 --> 00:45:07,106
And finally we have some guest
lectures of people coming

983
00:45:07,106 --> 00:45:08,996
in talking about
application areas

984
00:45:09,456 --> 00:45:11,206
such as scientific
visualization,

985
00:45:11,596 --> 00:45:13,326
or life science visualization,

986
00:45:13,366 --> 00:45:15,206
or even visualization
in the arts.

987
00:45:15,356 --> 00:45:18,226
So I hope to see you all
during shopping period,

988
00:45:18,356 --> 00:45:19,236
and thanks a lot.

989
00:45:20,516 --> 00:45:24,516
[ Applause ]

990
00:45:25,016 --> 00:45:27,106
>> So we have just 1
more teaser for you.

991
00:45:27,106 --> 00:45:29,926
This one from Professor
Krzysztof Gajos who's teaching

992
00:45:29,926 --> 00:45:33,776
computer science 179, which is
sensibly about user interfaces.

993
00:45:34,016 --> 00:45:35,936
>> Professor Krzysztof Gajos:
Hi my name is Krzysztof Gajos.

994
00:45:35,936 --> 00:45:38,086
How many of you here are
first years at Harvard?

995
00:45:39,526 --> 00:45:40,246
Well so am I.

996
00:45:40,916 --> 00:45:42,646
I'm very excited to be here.

997
00:45:42,646 --> 00:45:45,246
I think what makes Harvard
computer science incredibly

998
00:45:45,246 --> 00:45:47,936
exciting is not only
the computer scientists,

999
00:45:48,006 --> 00:45:49,146
but everybody else at Harvard.

1000
00:45:49,146 --> 00:45:52,896
It's the fact that Harvard
focuses not only on the bits,

1001
00:45:53,036 --> 00:45:55,476
but also on the rest
of the world.

1002
00:45:55,536 --> 00:46:00,736
We are here to make an impact.

1003
00:46:00,886 --> 00:46:03,816
Greg, Matt, and Michael
told you a lot

1004
00:46:03,946 --> 00:46:06,706
about how you can solve
problems, and the skills

1005
00:46:06,706 --> 00:46:07,976
that you need for
solving problems.

1006
00:46:08,256 --> 00:46:12,436
And I think this is actually
important for computer science.

1007
00:46:12,676 --> 00:46:14,636
In fact let me start
with a story

1008
00:46:14,636 --> 00:46:16,046
from my own undergraduate
experience.

1009
00:46:16,676 --> 00:46:21,046
My first research opportunity
down at the technical college,

1010
00:46:21,166 --> 00:46:23,106
a little bit down the river,

1011
00:46:23,776 --> 00:46:26,126
was with an information
retrieval group.

1012
00:46:26,756 --> 00:46:29,456
David Cargo was incredibly
interested in web search.

1013
00:46:29,486 --> 00:46:32,406
It was a time of Alta Vista,
Web Crawler, Meta Crawler,

1014
00:46:33,686 --> 00:46:38,796
and each week he would start
the meeting by bringing up 1

1015
00:46:38,796 --> 00:46:42,186
of those new search engines
because they tended to pop

1016
00:46:42,186 --> 00:46:43,456
up roughly once a week.

1017
00:46:43,996 --> 00:46:46,756
He would test it
always in the same way.

1018
00:46:46,756 --> 00:46:48,686
He would type in his name
and see what came up.

1019
00:46:49,256 --> 00:46:51,596
And inevitably the first
thing that would come

1020
00:46:51,596 --> 00:46:56,666
up in those engines would be a
publications database that...

1021
00:46:56,666 --> 00:46:59,946
that said his name more than
once, or another website

1022
00:46:59,946 --> 00:47:02,426
that mentioned him but it
was never his homepage.

1023
00:47:03,096 --> 00:47:05,776
And 1 day I knew that
things had changed.

1024
00:47:06,546 --> 00:47:07,296
He looked different.

1025
00:47:08,156 --> 00:47:09,676
There was suspense
in the classroom.

1026
00:47:10,266 --> 00:47:12,356
He was going to tell us
something very special.

1027
00:47:12,996 --> 00:47:15,796
He brought up a search engine,
a brand new search engine,

1028
00:47:15,856 --> 00:47:19,166
typed in his name,
and out came his name.

1029
00:47:19,406 --> 00:47:21,956
What was the search engine?

1030
00:47:23,386 --> 00:47:25,156
No it was not Alta
Vista, it was Google.

1031
00:47:27,436 --> 00:47:28,906
What was special about Google?

1032
00:47:28,906 --> 00:47:30,036
What made Google special?

1033
00:47:31,166 --> 00:47:34,586
It was the fact that there
was a very important problem,

1034
00:47:34,716 --> 00:47:38,936
search problem, that has
been around for many years.

1035
00:47:38,966 --> 00:47:40,256
There were lots of
people working on it,

1036
00:47:40,966 --> 00:47:44,296
and Google guys figured out
how to solve that problem well.

1037
00:47:45,756 --> 00:47:48,386
They used all of the skills
and computer science and came

1038
00:47:48,386 --> 00:47:50,026
up with the great solution.

1039
00:47:50,346 --> 00:47:52,896
They started with a well
defined problem and they came

1040
00:47:52,896 --> 00:47:55,456
up with a great solution,
and that made them great.

1041
00:47:57,296 --> 00:48:00,416
But I argue that besides
being incredibly smart,

1042
00:48:01,176 --> 00:48:04,656
[inaudible name]
incredibly lacking.

1043
00:48:05,096 --> 00:48:08,076
How many great problems,
well specified problems,

1044
00:48:08,076 --> 00:48:10,026
can you name off the
top of your head?

1045
00:48:11,716 --> 00:48:13,176
Probably not that many, right?

1046
00:48:14,196 --> 00:48:17,246
I think as computer scientists
we need another skill,

1047
00:48:17,246 --> 00:48:19,356
and this is the skill that
all of these people have.

1048
00:48:20,566 --> 00:48:23,706
These people have the skill
of going out in the world

1049
00:48:25,146 --> 00:48:26,396
and finding the problem.

1050
00:48:27,056 --> 00:48:30,246
They go talk to people, figure
out that people have the problem

1051
00:48:30,246 --> 00:48:32,426
that they themselves
might not even know about,

1052
00:48:32,806 --> 00:48:34,986
and then they come up with
such a compelling solution

1053
00:48:35,236 --> 00:48:37,126
that they change how
the world operates.

1054
00:48:38,126 --> 00:48:41,716
And this actually is
the premise of CS179.

1055
00:48:42,256 --> 00:48:47,416
CS179, called the usable
interactive systems,

1056
00:48:47,886 --> 00:48:49,466
will be offered for
the first time,

1057
00:48:49,596 --> 00:48:51,406
kind of on a permanent
basis, this spring.

1058
00:48:51,406 --> 00:48:53,766
It was offered once before
by a visiting faculty.

1059
00:48:54,446 --> 00:48:57,756
And this class is not
about solving problems.

1060
00:48:57,756 --> 00:48:59,306
It's not about understanding
problems.

1061
00:48:59,596 --> 00:49:00,996
It's about discovering problems.

1062
00:49:01,746 --> 00:49:04,086
So the fundamental question

1063
00:49:04,086 --> 00:49:06,026
of this class is what
is computer science,

1064
00:49:06,236 --> 00:49:06,956
and what it's not.

1065
00:49:07,586 --> 00:49:09,446
Unfortunately many people,

1066
00:49:09,556 --> 00:49:12,686
not you because you wouldn't be
here, think of computer science

1067
00:49:12,866 --> 00:49:13,896
as something like this.

1068
00:49:14,526 --> 00:49:16,536
But this is not what
computer science is.

1069
00:49:16,876 --> 00:49:21,856
Computer science is an extremely
powerful intellectual tool kit

1070
00:49:22,816 --> 00:49:24,596
for discovering and
solving problems.

1071
00:49:25,166 --> 00:49:28,686
And the successes of computer
scientists depends not only

1072
00:49:28,726 --> 00:49:30,526
on how well you can
solve the problems,

1073
00:49:31,076 --> 00:49:32,366
but on what problems you solve.

1074
00:49:33,206 --> 00:49:38,026
And in CS170 we'll
precisely focus

1075
00:49:38,296 --> 00:49:40,476
on this entire lifecycle
of innovation.

1076
00:49:40,886 --> 00:49:44,126
In CS179 you will
learn how to discover

1077
00:49:44,126 --> 00:49:46,656
that there exists a
problem, a powerful problem,

1078
00:49:46,696 --> 00:49:49,356
a problem that if you solved
it could change people's lives.

1079
00:49:50,246 --> 00:49:52,116
You will learn how
to invent solutions.

1080
00:49:52,696 --> 00:49:55,626
And when we invent
solutions to problems

1081
00:49:55,626 --> 00:49:57,606
that we've just discovered,
it's not just

1082
00:49:57,606 --> 00:50:01,026
about writing codes
to specification.

1083
00:50:01,116 --> 00:50:02,576
It's figuring out what aspects

1084
00:50:02,576 --> 00:50:04,076
of the problem are
actually important.

1085
00:50:04,446 --> 00:50:06,506
It's figuring out who
the stakeholders are

1086
00:50:06,506 --> 00:50:09,276
and whose needs you
should address first.

1087
00:50:09,726 --> 00:50:12,466
It's about figuring out
what you need to do in order

1088
00:50:12,466 --> 00:50:17,526
for your solution to actually
be sustainable and productive.

1089
00:50:17,526 --> 00:50:21,666
An extremely important skill
that you will learn in CS179 is

1090
00:50:21,666 --> 00:50:23,316
that you are not
an average person,

1091
00:50:24,286 --> 00:50:27,196
which is actually a terrible
handicap because it means

1092
00:50:27,196 --> 00:50:31,046
that you have no idea
what normal people think.

1093
00:50:31,736 --> 00:50:34,966
When we design solutions we
design for different people.

1094
00:50:34,966 --> 00:50:36,966
We design for people
who love control.

1095
00:50:37,156 --> 00:50:39,996
We design solutions for
people who like to tweek.

1096
00:50:40,436 --> 00:50:43,316
But this is not what
other people like to do,

1097
00:50:43,316 --> 00:50:46,936
and we will actually learn about
our own biases and what makes...

1098
00:50:47,856 --> 00:50:49,256
and how we can overcome them.

1099
00:50:50,306 --> 00:50:52,646
We'll also learn how to formally

1100
00:50:52,646 --> 00:50:58,066
and informally evaluate our
ideas, and actually a big part

1101
00:50:58,066 --> 00:51:01,196
of the class is going
to be critique sessions.

1102
00:51:01,476 --> 00:51:03,636
Once a week we are going
to meet in small groups,

1103
00:51:03,716 --> 00:51:09,526
present our contributions for
the week, and other students

1104
00:51:09,526 --> 00:51:12,026
in that small group will
actually present formative

1105
00:51:12,736 --> 00:51:15,506
critiques of whatever progress
you and your group made

1106
00:51:15,886 --> 00:51:17,456
to help you improve your system.

1107
00:51:17,996 --> 00:51:21,656
One of the greatest assets
that we have as innovators,

1108
00:51:21,656 --> 00:51:23,156
is other innovators,
other people

1109
00:51:23,156 --> 00:51:24,736
who understand the
innovation process

1110
00:51:25,016 --> 00:51:27,516
and who can offer
useful feedback

1111
00:51:27,516 --> 00:51:29,276
that can help shape
your solutions.

1112
00:51:30,126 --> 00:51:32,216
And finally this class
will be about teamwork.

1113
00:51:32,786 --> 00:51:35,896
All of the projects will
be done in teams of 3,

1114
00:51:37,106 --> 00:51:39,906
and the projects will
last most of the semester

1115
00:51:40,386 --> 00:51:42,716
with a couple of short breaks.

1116
00:51:42,716 --> 00:51:47,206
So on the practical side,
the main prerequisite

1117
00:51:47,206 --> 00:51:50,646
for this class is CS50 or any
kind of programming experience.

1118
00:51:51,216 --> 00:51:52,196
We will be using...

1119
00:51:52,396 --> 00:51:57,766
the specific programming
skills that you will need

1120
00:51:57,766 --> 00:51:58,946
to be successful in this class.

1121
00:51:58,946 --> 00:52:01,366
We'll let you cover in the
class all you need to know,

1122
00:52:01,686 --> 00:52:03,406
is how to think like
a programmer.

1123
00:52:04,606 --> 00:52:05,766
Lectures will be twice a week.

1124
00:52:05,766 --> 00:52:06,986
We'll have critique sessions,

1125
00:52:07,326 --> 00:52:10,336
and we'll have regular
weekday assignments.

1126
00:52:10,636 --> 00:52:11,956
There may be final exam.

1127
00:52:11,996 --> 00:52:12,966
I haven't decided yet.

1128
00:52:13,806 --> 00:52:18,836
An exciting thing is, Apple has
offered to lend us iPod Touchs.

1129
00:52:19,226 --> 00:52:21,856
Every team of 3 will have
their own iPod Touch,

1130
00:52:21,856 --> 00:52:25,476
and iPod Touch web development
will give the platform

1131
00:52:26,146 --> 00:52:28,096
that we'll use for
innovating and discuss.

1132
00:52:28,996 --> 00:52:29,556
Any questions?

1133
00:52:33,486 --> 00:52:37,576
OK. I will see you in
the spring of 2010.

1134
00:52:38,516 --> 00:52:42,596
[ Applause ]

1135
00:52:43,096 --> 00:52:45,246
>> So I thought I'd leave
you guys with 1 thought.

1136
00:52:45,326 --> 00:52:47,386
So truth be told, I think
there's something very

1137
00:52:47,386 --> 00:52:49,446
empowering about
studying computer science.

1138
00:52:49,446 --> 00:52:52,376
And I say this having
defected from gov long ago.

1139
00:52:52,866 --> 00:52:54,996
I can think of enumerable
experiences,

1140
00:52:54,996 --> 00:52:57,256
just in the real world
with this background I had;

1141
00:52:57,256 --> 00:52:59,266
not just in 50, but
in networking courses

1142
00:52:59,266 --> 00:53:02,656
and in theory courses, where I
actually realized very quickly I

1143
00:53:02,726 --> 00:53:06,056
understand better what
this person I'm talking

1144
00:53:06,056 --> 00:53:08,036
to is actually talking about.

1145
00:53:08,036 --> 00:53:11,056
So case in point, Comcast
is my, was for years,

1146
00:53:11,056 --> 00:53:12,416
my cable modem provider.

1147
00:53:12,606 --> 00:53:15,776
And every night around like 9
p.m. I would just lose internet

1148
00:53:15,776 --> 00:53:16,956
connectivity altogether,

1149
00:53:16,956 --> 00:53:19,406
and this happened again
and again and again.

1150
00:53:19,406 --> 00:53:21,946
And I talked to so many damn
representatives on the phone

1151
00:53:21,946 --> 00:53:24,216
about this pattern, and of
course the irony there being

1152
00:53:24,216 --> 00:53:26,476
such a big company, oh
sir we can send someone

1153
00:53:26,476 --> 00:53:28,516
out between 9 a.m.
and 5 p.m. everyday.

1154
00:53:28,516 --> 00:53:32,676
But it only happens after 5 p.m.
and so I hypothesized for them

1155
00:53:32,676 --> 00:53:34,886
on the phone, you know
maybe this has to do

1156
00:53:34,886 --> 00:53:36,556
with some real world
usage patterns.

1157
00:53:36,556 --> 00:53:38,836
Right? A lot of my neighbors
come home around 7 p.m.,

1158
00:53:38,836 --> 00:53:40,826
8 p.m. Perhaps this
is putting more

1159
00:53:40,826 --> 00:53:42,346
of a load on your equipment.

1160
00:53:42,546 --> 00:53:43,166
No, no, no, no.

1161
00:53:43,166 --> 00:53:45,956
It looks fine right now sir,
at 9 a.m. in the morning.

1162
00:53:46,166 --> 00:53:50,056
And long story short, this sort
of instinctive understanding

1163
00:53:50,056 --> 00:53:52,706
of how routers work
and how local hardware

1164
00:53:52,706 --> 00:53:55,816
and electronics work, helped
me realize maybe there was

1165
00:53:55,816 --> 00:53:57,336
something a little
more to it then.

1166
00:53:57,586 --> 00:54:00,006
Cisco, for instance, is
a very popular company

1167
00:54:00,006 --> 00:54:01,116
that makes really expensive

1168
00:54:01,116 --> 00:54:03,866
and really high powered
routers and switches.

1169
00:54:03,866 --> 00:54:06,386
And in my consulting
life some months ago,

1170
00:54:06,386 --> 00:54:09,156
we had just deployed this
real world Cisco switch,

1171
00:54:09,456 --> 00:54:11,686
a Cisco firewall actually.

1172
00:54:11,886 --> 00:54:13,566
And I'd never used
these things before.

1173
00:54:13,566 --> 00:54:15,076
A lot of the stuff
was over my head.

1174
00:54:15,076 --> 00:54:18,516
The documentation's like this
thick, but I knew from CS143,

1175
00:54:18,516 --> 00:54:20,666
networking, you know, how a
router is supposed to work,

1176
00:54:20,666 --> 00:54:22,206
how a firewall is
supposed to work.

1177
00:54:22,416 --> 00:54:25,236
And there too this firewall,
brand new out of the box,

1178
00:54:25,236 --> 00:54:27,926
installed by very expensive
consultants, was crashing

1179
00:54:27,926 --> 00:54:29,956
on us again and again everyday.

1180
00:54:30,236 --> 00:54:33,836
And frankly I whipped out my
CS50 skills SSH into this thing,

1181
00:54:33,836 --> 00:54:36,586
because it's really just a
Unix computer that's running,

1182
00:54:36,756 --> 00:54:39,756
and found all of
these core files

1183
00:54:39,756 --> 00:54:41,546
which I really didn't
understand but I knew

1184
00:54:41,546 --> 00:54:44,286
from my time 10 years
ago weren't necessarily a

1185
00:54:44,286 --> 00:54:44,806
good thing.

1186
00:54:44,806 --> 00:54:46,806
And sure enough the
firmware, the software running

1187
00:54:46,806 --> 00:54:49,406
on this Cisco, very expensive
switch, was just buggy.

1188
00:54:49,516 --> 00:54:51,916
Cisco had screwed up, and the
thing was seg faulting once a

1189
00:54:51,916 --> 00:54:53,466
night around a particular time.

1190
00:54:53,686 --> 00:54:54,726
But it was these instincts,

1191
00:54:54,726 --> 00:54:57,606
being able to solve these
problems myself and being able

1192
00:54:57,606 --> 00:54:58,716
to identify problems,

1193
00:54:58,716 --> 00:55:01,156
as Krzysztof has mentioned
there, in the real world.

1194
00:55:01,156 --> 00:55:02,496
It's like wow, wouldn't
it be great

1195
00:55:02,496 --> 00:55:04,666
if we had this Twitter
agregator.

1196
00:55:04,666 --> 00:55:08,576
Why? Not because it's terribly
useful, but because we can.

1197
00:55:08,576 --> 00:55:10,956
And that's the sense of
empowerment that I got from all

1198
00:55:10,956 --> 00:55:12,786
of these computer
science courses I got.

1199
00:55:12,936 --> 00:55:15,196
And whether you're considering
majoring or minoring,

1200
00:55:15,196 --> 00:55:17,646
or just dabbling in computer
science, hopefully you gather

1201
00:55:17,646 --> 00:55:19,046
from the faculty
who joined us today,

1202
00:55:19,246 --> 00:55:20,836
that there's many
different directions

1203
00:55:20,836 --> 00:55:22,316
in which you guys
can go after this.

1204
00:55:22,316 --> 00:55:25,426
So I hope you will join us
next semester on Wednesday

1205
00:55:25,426 --> 00:55:28,966
for quiz 1, and also on
Monday for our final class.

1206
00:55:29,046 --> 00:55:30,486
See you on Wednesday!

1207
00:55:32,516 --> 00:55:43,270
[ Music ]