1
00:00:00,000 --> 00:00:00,270

2
00:00:00,270 --> 00:00:01,790
DAVID MALAN: Welcome back, everyone.

3
00:00:01,790 --> 00:00:05,030
So yesterday, you'll recall that
we focused on these topics here.

4
00:00:05,030 --> 00:00:08,380
So we had four overarching topics--
privacy, security, and society;

5
00:00:08,380 --> 00:00:11,960
internet technologies; cloud computing;
and ultimately, web development.

6
00:00:11,960 --> 00:00:14,170
>> Did anyone have the
bandwidth or the time

7
00:00:14,170 --> 00:00:16,900
to watch a little John
Oliver last night?

8
00:00:16,900 --> 00:00:20,120
It's actually pretty amusing,
if not a little frightening.

9
00:00:20,120 --> 00:00:24,700
Any questions on anything
we did yesterday?

10
00:00:24,700 --> 00:00:27,600
Any clarifications?

11
00:00:27,600 --> 00:00:35,580
Any questions that you want to make
sure we touch on today in some form?

12
00:00:35,580 --> 00:00:37,300
So clean slate.

13
00:00:37,300 --> 00:00:38,760
>> So what's on the agenda for today?

14
00:00:38,760 --> 00:00:41,301
So I thought we'd begin today
with a look at what's generally

15
00:00:41,301 --> 00:00:44,460
known as computational thinking-- at
the risk of oversimplifying, thinking

16
00:00:44,460 --> 00:00:46,636
like a computer, perhaps
thinking like an engineer,

17
00:00:46,636 --> 00:00:48,510
and trying to start to
organize your thoughts

18
00:00:48,510 --> 00:00:52,039
or to give you a better sense of
what's involved in actually commanding

19
00:00:52,039 --> 00:00:54,080
a computer to do something
by way of programming.

20
00:00:54,080 --> 00:00:56,663
And we'll keep it at a pretty
high level, pretty much English,

21
00:00:56,663 --> 00:00:59,850
but try to use of familiar
examples to formalize how

22
00:00:59,850 --> 00:01:01,450
you would go about solving problems.

23
00:01:01,450 --> 00:01:04,080
>> And we will revisit some CS
topics, like abstraction,

24
00:01:04,080 --> 00:01:06,040
which came up a couple
of times yesterday,

25
00:01:06,040 --> 00:01:07,554
algorithms, and then representation.

26
00:01:07,554 --> 00:01:09,720
And that's where we'll begin
today in just a moment.

27
00:01:09,720 --> 00:01:11,481
Then we'll take a look at programming.

28
00:01:11,481 --> 00:01:13,480
We'll take a look at some
fundamental constructs

29
00:01:13,480 --> 00:01:16,450
with which you might be familiar
and might even find quite intuitive.

30
00:01:16,450 --> 00:01:18,370
>> We'll look, in fact,
at a sample programming

31
00:01:18,370 --> 00:01:21,244
environment that's very accessible,
very playful, and indeed targeted

32
00:01:21,244 --> 00:01:22,555
for ages 12 and up.

33
00:01:22,555 --> 00:01:25,930
We will spend a few minutes there
and then take things to a lower level

34
00:01:25,930 --> 00:01:30,360
and actually talk about some of
the algorithms and data structures,

35
00:01:30,360 --> 00:01:32,360
so to speak, that
programmers typically use

36
00:01:32,360 --> 00:01:35,040
to solve problems far more
efficiently than you might

37
00:01:35,040 --> 00:01:37,322
be able to do without them altogether.

38
00:01:37,322 --> 00:01:40,280
Then after lunch, we'll take a look
at technology stacks, which is just

39
00:01:40,280 --> 00:01:42,240
a fancy way of saying
collections of technologies

40
00:01:42,240 --> 00:01:43,690
that you might use to
solve some problem.

41
00:01:43,690 --> 00:01:46,670
And we'll talk about the alphabet
soup of languages that exist today--

42
00:01:46,670 --> 00:01:50,930
Java and Python and C++ and PHP and
Ruby and all sorts of other things.

43
00:01:50,930 --> 00:01:53,740
>> We'll take a look briefly
at design patterns.

44
00:01:53,740 --> 00:01:57,730
Programmers, over time,
have adopted methodologies

45
00:01:57,730 --> 00:02:00,690
that tend to help them
solve problems more readily.

46
00:02:00,690 --> 00:02:04,390
When you start to see yourself writing
the same kind of code again and again,

47
00:02:04,390 --> 00:02:08,080
people formalize those repetitions
and ascribe names to them

48
00:02:08,080 --> 00:02:10,084
and then use them and
promote them, ultimately.

49
00:02:10,084 --> 00:02:12,250
And we'll talk a little bit
about mobile strategies,

50
00:02:12,250 --> 00:02:16,099
like what does it mean to actually
make a mobile app or a mobile website.

51
00:02:16,099 --> 00:02:17,140
Do you do it for Android?

52
00:02:17,140 --> 00:02:17,730
Do you do it for iOS?

53
00:02:17,730 --> 00:02:19,160
Do you do it for both of those?

54
00:02:19,160 --> 00:02:20,326
And what are the trade-offs?

55
00:02:20,326 --> 00:02:23,180
And then finally, we'll take
a look web programming, which

56
00:02:23,180 --> 00:02:25,380
is a collective term
really describing any time

57
00:02:25,380 --> 00:02:28,410
you write software that's
meant to run on the web,

58
00:02:28,410 --> 00:02:30,430
whether on phones or
desktops or laptops.

59
00:02:30,430 --> 00:02:33,490
We'll take a brief look at
databases and the design

60
00:02:33,490 --> 00:02:39,049
therein, if only because almost any
interesting web-based application

61
00:02:39,049 --> 00:02:40,590
these days has some kind of database.

62
00:02:40,590 --> 00:02:42,380
Otherwise, it would
just be static content.

63
00:02:42,380 --> 00:02:45,254
And a database allows you to make
changes over time, whether yourself

64
00:02:45,254 --> 00:02:45,960
or from users.

65
00:02:45,960 --> 00:02:47,820
And we'll consider how you
would go about designing

66
00:02:47,820 --> 00:02:50,510
that database and the kind of jargon
that might come up in an engineer's

67
00:02:50,510 --> 00:02:52,790
discussion at a white board
when actually implementing

68
00:02:52,790 --> 00:02:53,900
an app for the first time.

69
00:02:53,900 --> 00:02:57,002
>> We'll talk briefly about
APIs, useful services

70
00:02:57,002 --> 00:02:59,960
that you can use to stand on the
shoulders of others, whether companies

71
00:02:59,960 --> 00:03:02,619
or individuals, and solve your
own problems more quickly.

72
00:03:02,619 --> 00:03:04,785
And then we'll dabble perhaps
a bit with JavaScript,

73
00:03:04,785 --> 00:03:08,900
a programming language that's used
both in browsers these days, but also

74
00:03:08,900 --> 00:03:09,820
in servers.

75
00:03:09,820 --> 00:03:11,890
And perhaps, we'll
revisit, time permitting,

76
00:03:11,890 --> 00:03:15,670
some of the hands-on web stuff we
did yesterday and integrate the two

77
00:03:15,670 --> 00:03:17,630
together before we adjourn.

78
00:03:17,630 --> 00:03:22,380
>> So with that-- what's ahead-- is
there anything missing that you

79
00:03:22,380 --> 00:03:26,289
would like to make sure we insert
and touch on at some point.

80
00:03:26,289 --> 00:03:28,330
If it's springs to mind,
bring it up before long.

81
00:03:28,330 --> 00:03:32,010
But why don't we begin with a
look at computational thinking.

82
00:03:32,010 --> 00:03:35,420
>> And let me propose that
computational thinking is, again,

83
00:03:35,420 --> 00:03:38,830
sort of the high level description of
what a computer scientist might do.

84
00:03:38,830 --> 00:03:42,470
And indeed, let's start
with three ingredients that

85
00:03:42,470 --> 00:03:44,207
might go into computational thinking.

86
00:03:44,207 --> 00:03:45,790
This is just one way of describing it.

87
00:03:45,790 --> 00:03:48,490
We could certainly define
this in any number of ways.

88
00:03:48,490 --> 00:03:50,630
>> But let me propose,
for the sake of today,

89
00:03:50,630 --> 00:03:53,910
that the world's problems,
all of the world's problems,

90
00:03:53,910 --> 00:03:56,730
when approached by a
computer scientist could

91
00:03:56,730 --> 00:04:00,990
be viewed as what we'll
call inputs, which

92
00:04:00,990 --> 00:04:08,142
need to get fed into what we'll call
algorithms, which then yield outputs.

93
00:04:08,142 --> 00:04:10,600
In other words, the entire
world of problem-solving I claim

94
00:04:10,600 --> 00:04:13,140
can be distilled into
these three ingredients.

95
00:04:13,140 --> 00:04:14,450
So what do I mean by inputs?

96
00:04:14,450 --> 00:04:17,060
Inputs is just what you're
handed in order to solve.

97
00:04:17,060 --> 00:04:20,052
>> For instance, here's
an old school problem.

98
00:04:20,052 --> 00:04:22,760
If I have a phone book here and
I want to look something into it,

99
00:04:22,760 --> 00:04:23,760
this is my input.

100
00:04:23,760 --> 00:04:26,260
I have 1,000 or so
pages in a phone book.

101
00:04:26,260 --> 00:04:27,780
This is the input to my problem.

102
00:04:27,780 --> 00:04:31,507
And I want to find something
like Mike Smith, so a friend

103
00:04:31,507 --> 00:04:33,840
whose name and number is
hopefully in this address book.

104
00:04:33,840 --> 00:04:36,430
>> This is before the days of cell
phones, so I can't just search for it.

105
00:04:36,430 --> 00:04:38,540
So I have to do it old
school and actually search

106
00:04:38,540 --> 00:04:41,331
these inputs for some answer.

107
00:04:41,331 --> 00:04:43,580
And that answer is just going
to be called the output.

108
00:04:43,580 --> 00:04:44,871
So the input is the phone book.

109
00:04:44,871 --> 00:04:47,787
The algorithm is whatever set of
steps I use to find Mike Smith.

110
00:04:47,787 --> 00:04:50,120
And the output is, hopefully,
Mike Smith's phone number.

111
00:04:50,120 --> 00:04:52,703
And this then would be just
representative of most any problem

112
00:04:52,703 --> 00:04:55,210
to with you are handed inputs
and want to produce outputs.

113
00:04:55,210 --> 00:04:59,459
>> So before we consider the process
by which we can solve that problem,

114
00:04:59,459 --> 00:05:01,250
finding Mike Smith and
something like that,

115
00:05:01,250 --> 00:05:04,090
let's consider the first and
the last-- inputs and outputs.

116
00:05:04,090 --> 00:05:08,060
Physically, of course, the input here
is a whole bunch of paper glued together

117
00:05:08,060 --> 00:05:09,400
in the form of a phone book.

118
00:05:09,400 --> 00:05:13,660
But computers, of course-- laptops
and desktops and even phones

119
00:05:13,660 --> 00:05:16,430
these days-- those are
electronic devices.

120
00:05:16,430 --> 00:05:20,920
>> And at the end of the day, what's
the only input to a computer?

121
00:05:20,920 --> 00:05:23,299
Well, it's something like
this power cord here.

122
00:05:23,299 --> 00:05:25,590
I plug it into the wall, and
I get a flow of electrons,

123
00:05:25,590 --> 00:05:27,048
which allows me to run the machine.

124
00:05:27,048 --> 00:05:30,420
Or maybe those electrons are
created by way of my battery.

125
00:05:30,420 --> 00:05:33,790
But at the end of the day, that's
the only thing going into my laptop.

126
00:05:33,790 --> 00:05:35,772
And so much interesting
stuff is ultimately

127
00:05:35,772 --> 00:05:37,480
coming out, whether
by way of the printer

128
00:05:37,480 --> 00:05:40,320
or the screen or audially or the like.

129
00:05:40,320 --> 00:05:45,320
>> So if all we have as our
fundamental input to a computer

130
00:05:45,320 --> 00:05:49,160
is electricity, so just
electrons going in and or out,

131
00:05:49,160 --> 00:05:54,465
and so how can we use that input
to actually represent information?

132
00:05:54,465 --> 00:05:57,090
In other words, how do we get
from a simple flow of electricity

133
00:05:57,090 --> 00:06:00,350
to representing actual
numbers or actual letters

134
00:06:00,350 --> 00:06:03,620
or actual images on the screen
or actual movies or e-mails

135
00:06:03,620 --> 00:06:05,690
or any number of these
higher level concepts,

136
00:06:05,690 --> 00:06:07,680
if you will, that at the
end of the day somehow

137
00:06:07,680 --> 00:06:11,950
have to be stored in this
electronic mechanical device

138
00:06:11,950 --> 00:06:16,260
using only those simple ingredients--
electrons coming in and out?

139
00:06:16,260 --> 00:06:19,530
>> So it would seem that,
in the simplest form,

140
00:06:19,530 --> 00:06:23,260
the only kind of states
I have in my world, so

141
00:06:23,260 --> 00:06:25,350
to speak-- conditions
in my world-- is either

142
00:06:25,350 --> 00:06:33,020
I have electrons flowing, electricity
flowing, or I do not-- so on, off.

143
00:06:33,020 --> 00:06:35,850
And let's formalize on and off,
as a computer scientist might,

144
00:06:35,850 --> 00:06:37,255
with just 1 and 0.

145
00:06:37,255 --> 00:06:39,880
Let's just describe some arbitrary
but consistent number to it.

146
00:06:39,880 --> 00:06:41,970
1 means on, 0 means off.

147
00:06:41,970 --> 00:06:45,427
Or you might also view this as
true means on and false means.

148
00:06:45,427 --> 00:06:47,510
You could also do black
and white or red and blue.

149
00:06:47,510 --> 00:06:48,759
You just need two descriptors.

150
00:06:48,759 --> 00:06:52,240
And a computer scientists would
generally just use 0 and 1.

151
00:06:52,240 --> 00:06:58,980
>> So if that's the case, my only alphabet
is consisting of 0's and 1's, how

152
00:06:58,980 --> 00:07:03,360
could I possibly get to even the number
2 in a computer, let alone the number 3

153
00:07:03,360 --> 00:07:06,140
or a letter of the alphabet
or an image or a movie?

154
00:07:06,140 --> 00:07:08,910
How do we sort of bootstrap
ourselves from this basic principle

155
00:07:08,910 --> 00:07:12,080
of 0's and 1's and actually
represent something more interesting?

156
00:07:12,080 --> 00:07:14,430
>> Well, let's put that question
on hold for just a moment

157
00:07:14,430 --> 00:07:17,520
and consider something
hopefully familiar,

158
00:07:17,520 --> 00:07:21,150
even if you haven't really thought about
it in any detail for 10, 20, 30, 40, 50

159
00:07:21,150 --> 00:07:22,520
more years.

160
00:07:22,520 --> 00:07:24,780
This is what?

161
00:07:24,780 --> 00:07:28,050
How would you pronounce that?

162
00:07:28,050 --> 00:07:30,770
Not a trick question.

163
00:07:30,770 --> 00:07:32,950
A number, but what is it?

164
00:07:32,950 --> 00:07:34,842
1, 2, 3, or 123.

165
00:07:34,842 --> 00:07:37,800
And I liked how you said 1, 2, 3,
because that's one way of viewing it.

166
00:07:37,800 --> 00:07:39,870
1, 2, 3, it's a sequence
of three symbols.

167
00:07:39,870 --> 00:07:42,005
It's pictures that we
now have words for.

168
00:07:42,005 --> 00:07:44,880
And if you sort of read them all
together, a typical human in English

169
00:07:44,880 --> 00:07:46,600
would say 123.

170
00:07:46,600 --> 00:07:48,350
And that's sort of a
higher level concept,

171
00:07:48,350 --> 00:07:50,340
feels like a reasonably big number.

172
00:07:50,340 --> 00:07:51,490
>> But how did we get there?

173
00:07:51,490 --> 00:07:54,640
Well, it might be a while since
you've thought about it like this,

174
00:07:54,640 --> 00:07:56,680
but back in my day, I
kind of learned this

175
00:07:56,680 --> 00:08:01,030
as the 1's column, the 10's
column, and the 100's column.

176
00:08:01,030 --> 00:08:06,400
So as Lakisa says, it is
1, 2, 3, but it's also 123.

177
00:08:06,400 --> 00:08:08,700
But how do we get from
the former to the latter?

178
00:08:08,700 --> 00:08:12,340
>> Well, you would typically do in
the 100's column, I have a 1.

179
00:08:12,340 --> 00:08:14,794
So that's like saying 100 times 1.

180
00:08:14,794 --> 00:08:16,210
And then in 10's column, I have 2.

181
00:08:16,210 --> 00:08:18,464
So that's like saying 10 times 2.

182
00:08:18,464 --> 00:08:19,630
In the 1's column, I have 3.

183
00:08:19,630 --> 00:08:21,720
So that's like saying 1 times 3.

184
00:08:21,720 --> 00:08:24,290
>> And if I add these things
together, this, of course,

185
00:08:24,290 --> 00:08:27,470
is 100 plus the 10 plus 3.

186
00:08:27,470 --> 00:08:31,750
And oh, that's why I get this
higher level notion of 123.

187
00:08:31,750 --> 00:08:37,220
It's just basic math, whereby these
symbols have weights to them, if you

188
00:08:37,220 --> 00:08:39,620
will, placeholder or column values.

189
00:08:39,620 --> 00:08:42,090
And once I multiply everything
out, I get this number.

190
00:08:42,090 --> 00:08:47,840
>> So how many of you know how to speak
binary-- 0's and 1's-- like a computer?

191
00:08:47,840 --> 00:08:50,410
OK, perfect, no one, or
none of you think you do.

192
00:08:50,410 --> 00:08:52,550
But I would claim you
actually know this already.

193
00:08:52,550 --> 00:08:55,330
We just need to sort of tweak
our mental model a little bit.

194
00:08:55,330 --> 00:08:57,250
But the process is exactly the same.

195
00:08:57,250 --> 00:09:01,460
>> Let me leave this one up there and
instead pull this down for a moment.

196
00:09:01,460 --> 00:09:05,060
In the world of computers,
we only have 0's and 1's.

197
00:09:05,060 --> 00:09:07,240
And so the thing that's
going to change is what?

198
00:09:07,240 --> 00:09:10,920
Well, in my human world, the
decimal system, dec meaning 10,

199
00:09:10,920 --> 00:09:12,740
I have how many digits at my disposal?

200
00:09:12,740 --> 00:09:15,270

201
00:09:15,270 --> 00:09:16,540
10, right?

202
00:09:16,540 --> 00:09:17,880
0 through 9, of course.

203
00:09:17,880 --> 00:09:21,210
>> And that's why we have the
10's place and the 100's place.

204
00:09:21,210 --> 00:09:22,380
Where is that coming from?

205
00:09:22,380 --> 00:09:24,430
Well, this is 10 to the power of 0.

206
00:09:24,430 --> 00:09:28,440
This is 10 to the power of 1, 10
to the power of 2, and so forth.

207
00:09:28,440 --> 00:09:32,110
You just keep multiplying your columns
by 10, starting off with just 1

208
00:09:32,110 --> 00:09:33,700
in the rightmost one here.

209
00:09:33,700 --> 00:09:35,490
>> So in the world of
computers, if you only

210
00:09:35,490 --> 00:09:39,600
have binary-- bi meaning
2-- or 0's and 1's, we just

211
00:09:39,600 --> 00:09:42,420
really need to change
the base of that math.

212
00:09:42,420 --> 00:09:46,410
So in other words, now we'll just
have the 1's column and the--

213
00:09:46,410 --> 00:09:51,270
where is this going-- the 2's column,
the 4's column, and maybe beyond.

214
00:09:51,270 --> 00:09:52,250
Why is that?

215
00:09:52,250 --> 00:09:55,650
Well, this is 2 the 0-th power.

216
00:09:55,650 --> 00:09:57,270
This is 2 the 1.

217
00:09:57,270 --> 00:09:59,610
This is 2 to the 2, and so on.

218
00:09:59,610 --> 00:10:04,910
>> So whereas here, we have 1, 10's,
100's, 1,000's, 10,000's, 100,000's, 1

219
00:10:04,910 --> 00:10:10,560
millions, and so forth, here
we have 1, 2, 4, 8, 16, 32, 64.

220
00:10:10,560 --> 00:10:13,950
You just keep multiplying by 2,
instead of keep multiplying by 10.

221
00:10:13,950 --> 00:10:16,780
So now, if the goal at
hand is to represent

222
00:10:16,780 --> 00:10:20,240
numbers using only 0's and 1's,
let's consider how we get there.

223
00:10:20,240 --> 00:10:26,540
>> This, of course, is the pattern 0
0 0, but what number conceptually

224
00:10:26,540 --> 00:10:27,490
does it represent?

225
00:10:27,490 --> 00:10:35,430
Well, 4 times 0 plus 2 times 0 plus
1 times 0, let's add those together.

226
00:10:35,430 --> 00:10:40,030
4 times 0 is, of course, 0, plus 2
times 0 is, of course, 0 plus 1 times 0

227
00:10:40,030 --> 00:10:40,850
is, of course, 0.

228
00:10:40,850 --> 00:10:44,910
So ah, this represents the
number we humans know as 0.

229
00:10:44,910 --> 00:10:47,810
>> Well, now, let's very
quickly fast forward.

230
00:10:47,810 --> 00:10:53,600
If I'm instead not representing
0 0 0, but let's do 1 0 1,

231
00:10:53,600 --> 00:10:57,010
that might be how Lakisa, earlier,
would just pronounce it 1 0 1.

232
00:10:57,010 --> 00:11:01,020
But now, how do we take it to the higher
level the number we humans might know?

233
00:11:01,020 --> 00:11:04,220
So what is this number?

234
00:11:04,220 --> 00:11:06,060
It's 5, the number we know as 5.

235
00:11:06,060 --> 00:11:06,870
>> Well, why is that?

236
00:11:06,870 --> 00:11:09,620
Well, we can really sort of
walk through it methodically

237
00:11:09,620 --> 00:11:14,880
4 times 1, 2 times 0, 1 times 1.

238
00:11:14,880 --> 00:11:19,880
Add those together, so
this is 4 plus 0 plus 1.

239
00:11:19,880 --> 00:11:21,577
And that's, indeed, 5.

240
00:11:21,577 --> 00:11:24,660
So it's getting a little tedious now
doing the arithmetic again and again.

241
00:11:24,660 --> 00:11:26,300
But the process is exactly the same.

242
00:11:26,300 --> 00:11:28,380
>> The only thing that has
changed in our world

243
00:11:28,380 --> 00:11:32,740
is that our columns are 1, 2, 4, 8, 16,
and so forth, instead of 1, 10, 100,

244
00:11:32,740 --> 00:11:33,740
1,000.

245
00:11:33,740 --> 00:11:40,000
And that's just because our alphabet has
shrunk from 0 through 9 to just 0 to 1.

246
00:11:40,000 --> 00:11:50,851
>> So as a little quiz here, how would
you represent the number 7 in binary?

247
00:11:50,851 --> 00:11:51,350
0?

248
00:11:51,350 --> 00:11:53,490
Well, 0, you mean 0 0 0?

249
00:11:53,490 --> 00:11:58,140

250
00:11:58,140 --> 00:11:59,693
Say it again , Karina.

251
00:11:59,693 --> 00:12:03,010

252
00:12:03,010 --> 00:12:03,550
Perfect.

253
00:12:03,550 --> 00:12:04,370
Why is that?

254
00:12:04,370 --> 00:12:08,530
It's effectively 4 plus 2 plus 1.

255
00:12:08,530 --> 00:12:09,580
So good.

256
00:12:09,580 --> 00:12:14,364
>> How do we represent a little
another-- how about number 2?

257
00:12:14,364 --> 00:12:18,360

258
00:12:18,360 --> 00:12:20,690
Close, but backwards.

259
00:12:20,690 --> 00:12:21,660
So what is this?

260
00:12:21,660 --> 00:12:26,290
Is 4 plus 1, so that's 5 again.

261
00:12:26,290 --> 00:12:28,310
>> So what's-- I'm sorry, Karina?

262
00:12:28,310 --> 00:12:29,220
0 1 0.

263
00:12:29,220 --> 00:12:34,762
0 1 0 would be 2, because again, even
if it sort of doesn't jump out at you,

264
00:12:34,762 --> 00:12:35,470
just do the math.

265
00:12:35,470 --> 00:12:40,390
4 times 0, 0, 2 times
1 is 2, 1 times 0 is 0.

266
00:12:40,390 --> 00:12:42,830
So this is the number we know as 2.

267
00:12:42,830 --> 00:12:44,030
>> How about the number 8?

268
00:12:44,030 --> 00:12:51,240

269
00:12:51,240 --> 00:12:52,730
Hm?

270
00:12:52,730 --> 00:12:53,330
Good.

271
00:12:53,330 --> 00:12:56,130
So we kind of need another placeholder.

272
00:12:56,130 --> 00:12:59,570
We need 1 0 0 0.

273
00:12:59,570 --> 00:13:02,280
And that's true of our sort
of old school decimal system.

274
00:13:02,280 --> 00:13:05,280
How do you represent the number 1,000?

275
00:13:05,280 --> 00:13:08,480
>> Well, you would seem to be
kind of in a tough spot,

276
00:13:08,480 --> 00:13:10,390
if ask you to represent
the number 1,000,

277
00:13:10,390 --> 00:13:14,960
because even if you give yourself like
9 of these, 9 of these, 0 of these,

278
00:13:14,960 --> 00:13:18,730
which is the biggest number you
have, you didn't quite get to 1,000.

279
00:13:18,730 --> 00:13:26,920
So if you 1,000, you just need another
position, so that you can do 1 0 0 0,

280
00:13:26,920 --> 00:13:29,460
ergo the number 1,000.

281
00:13:29,460 --> 00:13:34,200
>> So now, let's map this sort of
conceptual discussion back to hardware,

282
00:13:34,200 --> 00:13:37,470
where again, the input was just
this little power cable, electricity

283
00:13:37,470 --> 00:13:39,300
coming in and flowing out.

284
00:13:39,300 --> 00:13:44,740
And so for that to be mapped from here
to there, well, what do we really need?

285
00:13:44,740 --> 00:13:49,460
Well, you can think of being inside of a
computer, a whole bunch of light bulbs,

286
00:13:49,460 --> 00:13:50,450
if you will.

287
00:13:50,450 --> 00:13:52,040
They're really called transistors.

288
00:13:52,040 --> 00:13:55,121
And transistors are just switches
that can either be on or off.

289
00:13:55,121 --> 00:13:56,870
So you can think of a
transistor that's on

290
00:13:56,870 --> 00:14:00,730
is allowing electricity to flow and
a transistor that's off as stopping

291
00:14:00,730 --> 00:14:02,170
electricity from flowing.

292
00:14:02,170 --> 00:14:04,130
And rather than take
over the lights here,

293
00:14:04,130 --> 00:14:06,450
why don't I do this sort
of new school style.

294
00:14:06,450 --> 00:14:11,360
So this might be a 1, a flashlight
being on, only barely though.

295
00:14:11,360 --> 00:14:14,050
And this might be a 0, and now it's off.

296
00:14:14,050 --> 00:14:18,277
>> So using this physical device, I
can now represent the binary system.

297
00:14:18,277 --> 00:14:19,235
I just need two states.

298
00:14:19,235 --> 00:14:21,660
It doesn't matter what
color it is or what it is.

299
00:14:21,660 --> 00:14:25,920
All that matters is that I have
one state on and another state off.

300
00:14:25,920 --> 00:14:30,605
So using my phone here, how do I
represent the number we know as 0?

301
00:14:30,605 --> 00:14:34,490

302
00:14:34,490 --> 00:14:38,550
Or put equivalently, what
number am I representing now?

303
00:14:38,550 --> 00:14:39,810
0, because the device is off.

304
00:14:39,810 --> 00:14:41,560
>> And if I do this?

305
00:14:41,560 --> 00:14:43,583
And now, how do I
represent the number 2?

306
00:14:43,583 --> 00:14:46,380

307
00:14:46,380 --> 00:14:50,930
Can I borrow your phone
here, as we did yesterday?

308
00:14:50,930 --> 00:14:58,490
So let's see, so if I want to represent
the number 2, is this the number 2?

309
00:14:58,490 --> 00:14:59,050
No.

310
00:14:59,050 --> 00:15:02,250
What number am I accidentally
representing here?

311
00:15:02,250 --> 00:15:03,550
This is actually the number 3.

312
00:15:03,550 --> 00:15:05,008
>> So which one do I want to turn off?

313
00:15:05,008 --> 00:15:09,634
The black phone or-- well, if they're--
black phone or the white phone?

314
00:15:09,634 --> 00:15:10,300
The white phone.

315
00:15:10,300 --> 00:15:17,020
So if I turn this off and we
line it up over here, we have a 1

316
00:15:17,020 --> 00:15:19,487
in the 2's place and
a 0 in the 1's place.

317
00:15:19,487 --> 00:15:21,195
And so I'm now
representing the number 2.

318
00:15:21,195 --> 00:15:24,680
And this, Of course, would be the number
3, because now both of these lights

319
00:15:24,680 --> 00:15:25,350
are on.

320
00:15:25,350 --> 00:15:27,480
>> And I'll stop here,
but it stands to reason

321
00:15:27,480 --> 00:15:31,100
if I want to represent the
number 4 or 8 or higher,

322
00:15:31,100 --> 00:15:32,529
I'm going to need more phones.

323
00:15:32,529 --> 00:15:33,820
But that's all that's going on.

324
00:15:33,820 --> 00:15:37,800
So if you've ever heard that
inside of a-- thank you-- computer

325
00:15:37,800 --> 00:15:42,269
is millions of transistors, that's
just millions of tiny little switches.

326
00:15:42,269 --> 00:15:44,310
And they're not light
bulbs that turn on and off,

327
00:15:44,310 --> 00:15:48,340
but they do either allow electricity
to flow somewhere or stop it.

328
00:15:48,340 --> 00:15:52,140
And so there's your two
states-- on or off, on or off.

329
00:15:52,140 --> 00:15:55,730
>> So we would seem now
to have this ability

330
00:15:55,730 --> 00:16:00,590
to represent this concept that
we'd like in actual hardware.

331
00:16:00,590 --> 00:16:05,520
But all we have now is the ability
to represent numbers it would seem.

332
00:16:05,520 --> 00:16:08,580
So how do we go about representing
letters of the alphabet, which

333
00:16:08,580 --> 00:16:12,310
feels like the next sort of feature you
would want to add to a modern computer

334
00:16:12,310 --> 00:16:14,280
once you have numbers?

335
00:16:14,280 --> 00:16:16,930
>> And indeed, if you think about
it, historically, computers

336
00:16:16,930 --> 00:16:19,426
were introduced really to serve
as calculators numerically.

337
00:16:19,426 --> 00:16:21,300
But of course, these
days, they do much more.

338
00:16:21,300 --> 00:16:23,799
Even when they boot up, you
typically see one or more words.

339
00:16:23,799 --> 00:16:27,420
So how do you represent words,
if all you have is, again,

340
00:16:27,420 --> 00:16:31,054
electricity at the end of the
day, or equivalently 0's and 1's?

341
00:16:31,054 --> 00:16:34,430

342
00:16:34,430 --> 00:16:35,690
>> Yeah.

343
00:16:35,690 --> 00:16:38,320
Yeah, I mean, we kind of did
this yesterday in some form,

344
00:16:38,320 --> 00:16:40,200
where at some point,
I think I arbitrarily

345
00:16:40,200 --> 00:16:46,741
said that, if we want to represent the
letter A, we could just call that a 1.

346
00:16:46,741 --> 00:16:49,990
It was in the context of cryptography,
where we just needed some kind of code,

347
00:16:49,990 --> 00:16:51,160
some kind of mapping.

348
00:16:51,160 --> 00:16:56,680
>> So maybe A will be represented as a
1, and B will be represented as a 2,

349
00:16:56,680 --> 00:17:01,560
and Z will be represented
as a 26, for instance.

350
00:17:01,560 --> 00:17:07,430
And then the only caveat is that if I'm
going to encode letters in my emails

351
00:17:07,430 --> 00:17:10,430
or in my text messages
as numbers, you all

352
00:17:10,430 --> 00:17:12,640
have to agree to use the
same set of conventions.

353
00:17:12,640 --> 00:17:14,619
And indeed, the world
has done exactly that.

354
00:17:14,619 --> 00:17:18,040
>> There is a system in the world
called ASCII, American Standard

355
00:17:18,040 --> 00:17:21,640
Code for Information Interchange,
which is simply a decision some years

356
00:17:21,640 --> 00:17:25,720
ago that the humans made that
decided that A is going to equal, not

357
00:17:25,720 --> 00:17:32,260
1, 2, and 26, and so forth-- it's a
little different-- but 65, 66, 67.

358
00:17:32,260 --> 00:17:34,010
And I'll pull up a
chart in just a moment.

359
00:17:34,010 --> 00:17:34,580
But it's arbitrary.

360
00:17:34,580 --> 00:17:36,329
But it doesn't matter
that it's arbitrary.

361
00:17:36,329 --> 00:17:38,620
The world has to just be consistent.

362
00:17:38,620 --> 00:17:40,540
>> Now, more recently,
there's something fancier

363
00:17:40,540 --> 00:17:45,430
called Unicode, because the world's kind
of realized, after inventing computers,

364
00:17:45,430 --> 00:17:50,977
that there's more than well
256 symbols in the world

365
00:17:50,977 --> 00:17:53,560
that we might want to represent,
especially when you introduce

366
00:17:53,560 --> 00:17:58,420
Asian languages and other symbologies
that need more expressiveness than you

367
00:17:58,420 --> 00:18:02,150
can fit in the earliest version of
this code, which was called ASCII.

368
00:18:02,150 --> 00:18:05,250
So Unicode actually allows
you to use more 0's and 2.

369
00:18:05,250 --> 00:18:08,830
In particular, you keep hearing the
word bytes in society and even just

370
00:18:08,830 --> 00:18:09,400
yesterday.

371
00:18:09,400 --> 00:18:12,040
And a byte is what again?

372
00:18:12,040 --> 00:18:14,840
>> What's a byte?

373
00:18:14,840 --> 00:18:15,700
It's just 8 bits.

374
00:18:15,700 --> 00:18:17,150
So what does that really mean?

375
00:18:17,150 --> 00:18:22,400
Well, that means, earlier, when we were
talking about binary and I was using

376
00:18:22,400 --> 00:18:28,010
arbitrarily three bits when we were
talking about binary-- the 1's place,

377
00:18:28,010 --> 00:18:33,600
the 2's place, and the 4's place-- well,
a byte just means that you're talking

378
00:18:33,600 --> 00:18:38,730
not in units of three but
four, five, six, seven eight,

379
00:18:38,730 --> 00:18:46,910
which gives us 8's place,
16's, 32's, 64's, and 128's.

380
00:18:46,910 --> 00:18:50,010
>> In other words, a bit isn't all
that useful a unit of measure,

381
00:18:50,010 --> 00:18:53,132
because it's just like one tiny little
piece of information, on or off.

382
00:18:53,132 --> 00:18:54,840
So some years ago,
the world just decided

383
00:18:54,840 --> 00:18:59,060
it's slightly more convenient to talk in
terms of bytes, eight things at a time.

384
00:18:59,060 --> 00:19:01,670
And so thus was born
the notion of a byte.

385
00:19:01,670 --> 00:19:03,640
And so we have eight bits here.

386
00:19:03,640 --> 00:19:06,810
>> And it turns out, too, for similar
reasons, the world decided years

387
00:19:06,810 --> 00:19:12,439
ago that to represent an ASCII letter,
you're going to use units of 8 bits.

388
00:19:12,439 --> 00:19:14,230
So even if you don't
need that many, you're

389
00:19:14,230 --> 00:19:18,130
always going to use 8 bits to
represent a letter of the alphabet.

390
00:19:18,130 --> 00:19:20,950
And this is convenient,
because then if you

391
00:19:20,950 --> 00:19:28,720
receive a message that has a 0 0 0 1 1
1 1 0 followed by another 1 1 1 0 1 0

392
00:19:28,720 --> 00:19:33,320
0 1, so if you receive 16
bits, the world can just

393
00:19:33,320 --> 00:19:37,460
assume that the first 8 are one letter
and the second 8 are another letter.

394
00:19:37,460 --> 00:19:39,240
>> Doesn't matter how many there are.

395
00:19:39,240 --> 00:19:41,460
It just matters that
we're all consistent

396
00:19:41,460 --> 00:19:42,950
when we're interpreting these bits.

397
00:19:42,950 --> 00:19:44,377
And this was just random.

398
00:19:44,377 --> 00:19:47,210
That means something, but I didn't
really think about what it means.

399
00:19:47,210 --> 00:19:49,620
>> So it's a small white lie.

400
00:19:49,620 --> 00:19:51,990
Originally, ASCII
actually used only 7 bits.

401
00:19:51,990 --> 00:19:54,180
And the eighth bit is
called extended ASCII.

402
00:19:54,180 --> 00:19:56,290
But the point is, ultimately, the same.

403
00:19:56,290 --> 00:19:58,850
The world generally
standardized on 8 bits.

404
00:19:58,850 --> 00:20:04,290
>> So this would seem to be a little
limiting, because I can only

405
00:20:04,290 --> 00:20:07,970
represent capital A,
capital B through capital Z.

406
00:20:07,970 --> 00:20:10,940
But indeed not, if I go to--
there's a bunch of resources

407
00:20:10,940 --> 00:20:13,695
online, for instance,
asciitable.com, this

408
00:20:13,695 --> 00:20:16,310
is going to be a little
overwhelming at first.

409
00:20:16,310 --> 00:20:18,910
But I'll point out
what's important here.

410
00:20:18,910 --> 00:20:24,090
>> This just happens to be-- and I'll
walk-- let's see, if I go over here.

411
00:20:24,090 --> 00:20:27,990
Here is, in the decimal
column, the number 65.

412
00:20:27,990 --> 00:20:32,201
And on the right hand column letter
character, Chr, is the letter A.

413
00:20:32,201 --> 00:20:34,450
And you can ignore, for now,
everything in the middle.

414
00:20:34,450 --> 00:20:36,769
This is hexadecimal,
octal, and an HTML code.

415
00:20:36,769 --> 00:20:39,810
To this site is just trying to throw
a lot of information at you at once.

416
00:20:39,810 --> 00:20:42,970
But all we care about is the decimal
column and the character column.

417
00:20:42,970 --> 00:20:46,190
>> So by this logic, what is
the number that the world

418
00:20:46,190 --> 00:20:50,510
has decided represents a lowercase a?

419
00:20:50,510 --> 00:20:52,230
Yeah, 97.

420
00:20:52,230 --> 00:20:55,850
And just to confuse
potentially slightly,

421
00:20:55,850 --> 00:21:03,715
what number has the world decided
would represent the number 1?

422
00:21:03,715 --> 00:21:06,900

423
00:21:06,900 --> 00:21:10,910
Right, because we-- 49, it seems
here, down in the bottom left.

424
00:21:10,910 --> 00:21:12,320
>> Now, what do I mean by that?

425
00:21:12,320 --> 00:21:14,830
So it turns out that
in computer systems,

426
00:21:14,830 --> 00:21:16,840
there is generally a
fundamental difference

427
00:21:16,840 --> 00:21:19,920
between a number and a character.

428
00:21:19,920 --> 00:21:22,330
A number is the thing we
learned growing up when

429
00:21:22,330 --> 00:21:23,830
we were super young in grade school.

430
00:21:23,830 --> 00:21:25,110
It's things you count with.

431
00:21:25,110 --> 00:21:30,220
But a character is just a shape, a
glyph, so to speak, on the screen.

432
00:21:30,220 --> 00:21:36,200
>> Now, we humans sort of see
something that looks like this.

433
00:21:36,200 --> 00:21:39,060
And we say, oh, that is the number 2.

434
00:21:39,060 --> 00:21:44,999
But no, that's just a symbol that looks
like what we know as the number 2.

435
00:21:44,999 --> 00:21:46,790
And so there's this
fundamental distinction

436
00:21:46,790 --> 00:21:50,340
between actual numbers and characters.

437
00:21:50,340 --> 00:21:52,130
This is a number.

438
00:21:52,130 --> 00:21:54,420
But generally, in the
context of a computer,

439
00:21:54,420 --> 00:21:56,809
if you instead see
something like this quoted--

440
00:21:56,809 --> 00:21:58,600
and you don't always
have to see it quoted,

441
00:21:58,600 --> 00:22:01,474
but for the sake of discussion-- if
you see quotes around the number,

442
00:22:01,474 --> 00:22:02,730
this is now a character.

443
00:22:02,730 --> 00:22:06,330
So this number 2 underneath
the hood inside of a computer

444
00:22:06,330 --> 00:22:12,220
would be represented with a pattern
of bits that represent the number

445
00:22:12,220 --> 00:22:14,850
50 according to the chart online.

446
00:22:14,850 --> 00:22:18,300
>> However, if a computer
just sees this, this

447
00:22:18,300 --> 00:22:24,580
would be represented with the
pattern of bit 0 0 0 0 0 0 1 0.

448
00:22:24,580 --> 00:22:29,595
Whereas, this character would
actually be represented as-- and now,

449
00:22:29,595 --> 00:22:34,710
I got to think a little harder-- so this
character would be represented with 0

450
00:22:34,710 --> 00:22:39,080
0 1-- what do I need here?

451
00:22:39,080 --> 00:22:44,450
0 0 1 1 0 0 1 0.

452
00:22:44,450 --> 00:22:45,480
How did I do this?

453
00:22:45,480 --> 00:22:49,580
Well this is the number 50, if you
multiply it out using these columns,

454
00:22:49,580 --> 00:22:53,530
this is the number 2, and so
that's why there is this dichotomy.

455
00:22:53,530 --> 00:22:55,850
>> And this is just a
teaser now for features

456
00:22:55,850 --> 00:22:59,710
that exist in programming languages
that we'll touch on briefly later today.

457
00:22:59,710 --> 00:23:01,950
In programming languages,
you have generally,

458
00:23:01,950 --> 00:23:04,495
but not always, things
call different data types.

459
00:23:04,495 --> 00:23:06,870
In other words, a programmer--
when he or she is writing,

460
00:23:06,870 --> 00:23:11,150
a programmer gets to decide in what
format to store his or her data.

461
00:23:11,150 --> 00:23:14,120
You can either store data as
raw numbers, like the number 2.

462
00:23:14,120 --> 00:23:17,940
Or you can store them as strings,
or sequences of characters

463
00:23:17,940 --> 00:23:21,550
that you would generally express with
quotes in your programming language.

464
00:23:21,550 --> 00:23:25,230
>> You can have things called--
I'll oversimplify and call them

465
00:23:25,230 --> 00:23:28,870
real numbers-- so numbers that
aren't integers like the number 2,

466
00:23:28,870 --> 00:23:31,310
but numbers like 4.56.

467
00:23:31,310 --> 00:23:33,490
So real numbers can also
have decimal points,

468
00:23:33,490 --> 00:23:36,340
so that's a different fundamental
piece of data in a computer.

469
00:23:36,340 --> 00:23:41,920
And then you can even have
other data types still.

470
00:23:41,920 --> 00:23:45,810
So that's just a teaser really of
the simplest of design decisions

471
00:23:45,810 --> 00:23:50,960
that a programmer might
make underneath the hood.

472
00:23:50,960 --> 00:23:52,925
>> So any questions just yet?

473
00:23:52,925 --> 00:23:57,320

474
00:23:57,320 --> 00:23:59,860
So let's try to make
this a little more real.

475
00:23:59,860 --> 00:24:02,120
This hardware is not
so much in use anymore.

476
00:24:02,120 --> 00:24:07,420
But most everyone in this room probably
grew up with and still uses hard drives

477
00:24:07,420 --> 00:24:08,010
in some way.

478
00:24:08,010 --> 00:24:10,100
>> Even though most of
our laptops no longer

479
00:24:10,100 --> 00:24:15,900
have devices that operate like this,
instead laptops today generally

480
00:24:15,900 --> 00:24:18,590
have solid state drives
with no moving parts.

481
00:24:18,590 --> 00:24:22,840
And that tends to be more expensive,
unfortunately, but a little bit faster

482
00:24:22,840 --> 00:24:27,230
and a-- well, often, a lot faster,
which is one of the reasons.

483
00:24:27,230 --> 00:24:28,980
And also it doesn't
generate as much heat.

484
00:24:28,980 --> 00:24:31,680
It can be smaller, so it's
generally a net positive.

485
00:24:31,680 --> 00:24:35,030
>> But this allows us to map a
little more concretely what

486
00:24:35,030 --> 00:24:38,460
we're talking about at the 0's and
1's level now to a physical device.

487
00:24:38,460 --> 00:24:40,810
It's one thing for me to talk
about 0's and 1's in terms

488
00:24:40,810 --> 00:24:43,990
of my phone or abstractly in terms
of switches being on and off.

489
00:24:43,990 --> 00:24:45,340
But what about hard drives?

490
00:24:45,340 --> 00:24:48,495
In your laptops, if you have an older
one, or in your desktop computer,

491
00:24:48,495 --> 00:24:51,200
or certainly in servers
today, where you have

492
00:24:51,200 --> 00:24:53,070
hard drives that have
a terabyte of space,

493
00:24:53,070 --> 00:24:55,560
4 terabytes of space,
well what does that mean?

494
00:24:55,560 --> 00:24:59,560
>> A hard drive with 1
terabyte of space means

495
00:24:59,560 --> 00:25:03,890
there's 1 trillion bytes
inside of it somehow,

496
00:25:03,890 --> 00:25:10,450
or equivalently 8 trillion bits inside.

497
00:25:10,450 --> 00:25:16,240
1 terabyte would be 8 terabits
or 1 trillion bits, which

498
00:25:16,240 --> 00:25:19,330
means if you have a hard
drive, you have somehow

499
00:25:19,330 --> 00:25:22,400
or other a trillion 0's
and 1's inside of it.

500
00:25:22,400 --> 00:25:25,360
And if we just take a look at an
arbitrary picture of a hard drive

501
00:25:25,360 --> 00:25:30,110
representative, this is what a hard
drive might typically look like inside.

502
00:25:30,110 --> 00:25:32,600
>> It, too, is kind of like
an old phonograph player

503
00:25:32,600 --> 00:25:35,350
but generally with
multiple records inside, so

504
00:25:35,350 --> 00:25:38,270
to speak-- multiple
platters, as they're called,

505
00:25:38,270 --> 00:25:42,259
metal circular disks, and
then a little reading head,

506
00:25:42,259 --> 00:25:43,550
much like an old record player.

507
00:25:43,550 --> 00:25:46,589
And that reading head moves back and
forth and somehow reads the bits.

508
00:25:46,589 --> 00:25:49,380
And what's on these platters, even
though we humans can't see them,

509
00:25:49,380 --> 00:25:52,757
either in reality or in this picture,
there's tiny little magnetic particles.

510
00:25:52,757 --> 00:25:55,090
And even if you've long
forgotten how electricity works,

511
00:25:55,090 --> 00:25:57,550
a magnetic particle
that's charged generally

512
00:25:57,550 --> 00:26:00,570
has a north end and a south
end-- so north and south.

513
00:26:00,570 --> 00:26:03,000
And so the world just
decided some time ago

514
00:26:03,000 --> 00:26:06,570
that, if a magnetic protocol essentially
is aligned like this, north-south,

515
00:26:06,570 --> 00:26:07,610
let's call that a 1.

516
00:26:07,610 --> 00:26:10,470
If it's instead south-north,
let's just call that a 0.

517
00:26:10,470 --> 00:26:13,350
And so if you have at
your disposal a trillion

518
00:26:13,350 --> 00:26:16,300
tiny little magnetic
particles-- and hopefully,

519
00:26:16,300 --> 00:26:18,740
the hardware ingenuity in
order to flip those around

520
00:26:18,740 --> 00:26:24,450
as you see fit-- if you want to
represent a whole bunch of 0's, you

521
00:26:24,450 --> 00:26:28,120
just need 8 magnetic particles
all aligned like this.

522
00:26:28,120 --> 00:26:30,330
And if you want to represent
eight 1's, you just

523
00:26:30,330 --> 00:26:33,170
need 8 magnetic particles aligned
back to back to back like this.

524
00:26:33,170 --> 00:26:35,515
>> What do I mean by the
magnetic particles?

525
00:26:35,515 --> 00:26:38,390
Frankly, all these years later, the
thing that still comes to my mind

526
00:26:38,390 --> 00:26:42,139
is this guy, if you
grew up with this thing.

527
00:26:42,139 --> 00:26:43,930
This is a little-- for
those unfamiliar-- a

528
00:26:43,930 --> 00:26:47,810
little childhood toy that
has this hairless man here

529
00:26:47,810 --> 00:26:51,690
that has all these tiny little black
magnetic particles that come with it.

530
00:26:51,690 --> 00:26:53,930
And using that red stick,
which is just a magnet,

531
00:26:53,930 --> 00:26:58,460
you can sort of give him a mustache or
eyebrows or hair or anything on him.

532
00:26:58,460 --> 00:27:00,710
So in fact, if we zoom
in, for instance, this

533
00:27:00,710 --> 00:27:02,950
is the kind of game you
can play with Wooly Willy.

534
00:27:02,950 --> 00:27:06,570
>> And this is only to say, these
are much larger magnetic particles

535
00:27:06,570 --> 00:27:09,890
than are actually on a hard drive,
and far fewer magnetic particles.

536
00:27:09,890 --> 00:27:11,640
But let's actually see
then if you do have

537
00:27:11,640 --> 00:27:14,720
tiny magnetic particles in a
hard drive, how you can actually

538
00:27:14,720 --> 00:27:19,090
use those to represent data.

539
00:27:19,090 --> 00:27:20,070
>> [VIDEO PLAYBACK]

540
00:27:20,070 --> 00:27:24,190
>> -The hard drive is where your PC
stores most of its permanent data.

541
00:27:24,190 --> 00:27:27,170
To do that, the data
travels from RAM along

542
00:27:27,170 --> 00:27:31,720
with software signals that tell the
hard drive how to store that data.

543
00:27:31,720 --> 00:27:36,570
The hard drive circuits translate those
signals into voltage fluctuations.

544
00:27:36,570 --> 00:27:40,880
These, in turn, control the hard drive's
moving parts-- some of the few moving

545
00:27:40,880 --> 00:27:43,440
parts left in the modern computer.

546
00:27:43,440 --> 00:27:47,650
>> Some of the signals control a motor,
which spins metal-coated platters.

547
00:27:47,650 --> 00:27:50,980
Your data is actually
stored on these platters.

548
00:27:50,980 --> 00:27:56,250
Other signals move the read/write heads
to read or write data on the platters.

549
00:27:56,250 --> 00:28:00,100
This machinery is so precise
that a human hair couldn't even

550
00:28:00,100 --> 00:28:02,800
pass between the heads
and spinning platters.

551
00:28:02,800 --> 00:28:04,887
Yet, it all works at terrific speeds.

552
00:28:04,887 --> 00:28:05,470
[END PLAYBACK]

553
00:28:05,470 --> 00:28:06,780
And you can see at the
tail end of the video,

554
00:28:06,780 --> 00:28:08,340
there are generally multiple platters.

555
00:28:08,340 --> 00:28:10,250
And so that reading head
isn't just reading the top.

556
00:28:10,250 --> 00:28:12,458
It's kind of like three or
four or more reading heads

557
00:28:12,458 --> 00:28:14,920
that move like this,
reading data simultaneously.

558
00:28:14,920 --> 00:28:17,407
>> So there's a lot of
complexity and sort of timing

559
00:28:17,407 --> 00:28:18,740
that's involved in a hard drive.

560
00:28:18,740 --> 00:28:21,920
And the thing is spinning really darn
fast, so there's a lot of complexity.

561
00:28:21,920 --> 00:28:25,220
But let's zoom in a little deeper and
see where are these magnetic particles

562
00:28:25,220 --> 00:28:27,370
and how are we're getting at them.

563
00:28:27,370 --> 00:28:28,750
>> [VIDEO PLAYBACK]

564
00:28:28,750 --> 00:28:31,830
>> -Let's look at what we
just saw in slow motion.

565
00:28:31,830 --> 00:28:35,230
When a brief pulse of electricity
is sent to the read/write head,

566
00:28:35,230 --> 00:28:39,000
it flips on a tiny electromagnetic
for a fraction of a second.

567
00:28:39,000 --> 00:28:41,390
The magnet creates a
field, which changes

568
00:28:41,390 --> 00:28:44,600
the polarity of a tiny, tiny
portion of the metal particles

569
00:28:44,600 --> 00:28:46,960
which coat each platter's surface.

570
00:28:46,960 --> 00:28:50,020
A pattern series of these tiny
charged up areas on the disk

571
00:28:50,020 --> 00:28:54,590
represents a single bit of data in the
binary number system used by computers.

572
00:28:54,590 --> 00:28:57,510
>> Now, if the current is sent one
way through the read/write head,

573
00:28:57,510 --> 00:28:59,899
the area is polarized in one direction.

574
00:28:59,899 --> 00:29:01,940
If the current is sent in
the opposite direction,

575
00:29:01,940 --> 00:29:04,020
the polarization is reversed.

576
00:29:04,020 --> 00:29:06,440
How do you get data off the hard disk?

577
00:29:06,440 --> 00:29:08,190
Just reverse the process.

578
00:29:08,190 --> 00:29:10,440
So it's the particles on the
disk that get the current

579
00:29:10,440 --> 00:29:12,260
in the read/write head moving.

580
00:29:12,260 --> 00:29:14,580
Put together millions of
these magnetized segments,

581
00:29:14,580 --> 00:29:16,220
and you've got a file.

582
00:29:16,220 --> 00:29:21,030
>> Now, the pieces of a single file may be
scattered all over a drive's platters,

583
00:29:21,030 --> 00:29:24,060
kind of like the mess
of papers on your desk.

584
00:29:24,060 --> 00:29:27,590
So a special extra file keeps
track of where everything is.

585
00:29:27,590 --> 00:29:30,440
Don't you wish you had
something like that?

586
00:29:30,440 --> 00:29:31,290
>> [END PLAYBACK]

587
00:29:31,290 --> 00:29:36,260
>> So being alluded to there, perhaps, is
that topic from yesterday of deletion.

588
00:29:36,260 --> 00:29:38,380
When you delete a
file, yesterday we said

589
00:29:38,380 --> 00:29:41,020
that a computer actually does
what, when you drag something

590
00:29:41,020 --> 00:29:44,110
to the Recycle bin or trash bin?

591
00:29:44,110 --> 00:29:45,150
It just forgets it.

592
00:29:45,150 --> 00:29:47,540
But the 0's and 1's,
the magnetic particles

593
00:29:47,540 --> 00:29:50,640
that look like red and blue
things here, or my arm here,

594
00:29:50,640 --> 00:29:52,350
are still there on the hard drive.

595
00:29:52,350 --> 00:29:56,090
>> And so there exists software--
Norton Utilities and Yesteryear

596
00:29:56,090 --> 00:29:58,159
and other more modern
software-- that just

597
00:29:58,159 --> 00:30:01,200
will scan a whole hard drive looking
at all those 0's and 1's, because it

598
00:30:01,200 --> 00:30:06,890
turns out that most file formats--
Word documents, Excel files, images,

599
00:30:06,890 --> 00:30:10,380
video files-- all have certain
patterns that are common among them.

600
00:30:10,380 --> 00:30:12,550
Every video file might
be of a different video,

601
00:30:12,550 --> 00:30:14,870
but the first several
bits are usually the same.

602
00:30:14,870 --> 00:30:16,790
Or the last several bits
are usually the same.

603
00:30:16,790 --> 00:30:19,910
>> And so with high probability,
you can look for those patterns.

604
00:30:19,910 --> 00:30:23,700
And even if the file has been forgotten,
you can say with high probability,

605
00:30:23,700 --> 00:30:28,460
but this looks like a Word document,
lets recover it and un-forget it,

606
00:30:28,460 --> 00:30:28,990
if you will.

607
00:30:28,990 --> 00:30:32,330
And so that's how you can recover
data that's either been accidentally

608
00:30:32,330 --> 00:30:36,560
deleted or deleted or deliberately
deleted for whatever purposes.

609
00:30:36,560 --> 00:30:42,530
>> By contrast, secure deletion does what
in the context of a picture like this?

610
00:30:42,530 --> 00:30:44,059
Exactly, makes them all random.

611
00:30:44,059 --> 00:30:46,350
So it sort of moves some of
them down, some of them up,

612
00:30:46,350 --> 00:30:49,433
leaves some of them unchanged, and
generally makes random noise out of it,

613
00:30:49,433 --> 00:30:52,960
or just maybe makes all of
them 0's or all of them 1's.

614
00:30:52,960 --> 00:30:56,350
And that too can generally
scrub your data away.

615
00:30:56,350 --> 00:31:00,160
>> So let's return now to the issue
of computational thinking, whereby

616
00:31:00,160 --> 00:31:03,270
we have the formula inputs.

617
00:31:03,270 --> 00:31:06,390
And algorithms gives
you outputs ultimately.

618
00:31:06,390 --> 00:31:09,270
We focus now on inputs and
outputs, because now, I

619
00:31:09,270 --> 00:31:12,159
claim we have a way of
representing inputs and outputs.

620
00:31:12,159 --> 00:31:13,450
We're just going to use binary.

621
00:31:13,450 --> 00:31:15,910
>> And no matter what we
want to represent today,

622
00:31:15,910 --> 00:31:20,230
whether it's a number or a letter
or thousands thereof in a phone book

623
00:31:20,230 --> 00:31:23,210
or images or movies, at the end
of the day, it's all 0's and 1's.

624
00:31:23,210 --> 00:31:26,640
And I claim that, even though this
is a super simple world with just 0's

625
00:31:26,640 --> 00:31:28,240
and 1's, we can build ourselves up.

626
00:31:28,240 --> 00:31:32,210
And we've seen one example of
that with letters thus far.

627
00:31:32,210 --> 00:31:35,615
>> So let's focus now on this
middle ingredient, an algorithm.

628
00:31:35,615 --> 00:31:38,190
And let's return to this
example of Mike Smith.

629
00:31:38,190 --> 00:31:41,689
So in this phone book, which admittedly,
we don't use so much anymore,

630
00:31:41,689 --> 00:31:42,980
there's a problem to be solved.

631
00:31:42,980 --> 00:31:45,040
We want to find someone like Mike Smith.

632
00:31:45,040 --> 00:31:47,520
>> And what might I do to find Mike?

633
00:31:47,520 --> 00:31:51,197
Well, I could just open up this
book, start at the first page,

634
00:31:51,197 --> 00:31:52,780
and realize, oh, I'm in the A section.

635
00:31:52,780 --> 00:31:53,510
Mike's not there.

636
00:31:53,510 --> 00:31:55,510
I need the S section for Smith.

637
00:31:55,510 --> 00:31:58,192
So just keep turning one page at a time.

638
00:31:58,192 --> 00:32:00,900
Let me pretend that this is all
white pages and not yellow pages,

639
00:32:00,900 --> 00:32:02,910
because we're not going to find
Mike in the yellow pages anyway.

640
00:32:02,910 --> 00:32:04,034
But I'm in the white pages.

641
00:32:04,034 --> 00:32:05,340
And now, I'm in the B section.

642
00:32:05,340 --> 00:32:06,810
I still haven't found him.

643
00:32:06,810 --> 00:32:08,890
So I keep turning one page at a time.

644
00:32:08,890 --> 00:32:10,130
>> This is an algorithm.

645
00:32:10,130 --> 00:32:12,440
It's a set of instructions
for solving some problem.

646
00:32:12,440 --> 00:32:16,480
In other words, look at
page, if Mike's not on it,

647
00:32:16,480 --> 00:32:20,020
turn page, and repeats
again and again and again,

648
00:32:20,020 --> 00:32:21,760
ideally looking down as you're doing it.

649
00:32:21,760 --> 00:32:24,120
So is this algorithm,
this process, correct?

650
00:32:24,120 --> 00:32:27,400

651
00:32:27,400 --> 00:32:28,830
>> Sorry.

652
00:32:28,830 --> 00:32:30,056
No, I hear some nos.

653
00:32:30,056 --> 00:32:33,250

654
00:32:33,250 --> 00:32:36,125
OK, but it is-- yeah,
it's certainly tedious.

655
00:32:36,125 --> 00:32:39,000
Like, we'll be here all day if I
keep looking for Mike at this speed.

656
00:32:39,000 --> 00:32:41,430
But let me claim it's correct.

657
00:32:41,430 --> 00:32:43,850
It's stupid, but it's correct.

658
00:32:43,850 --> 00:32:47,209
>> At the end of the day, long as it might
take, I will find Mike if he's in there

659
00:32:47,209 --> 00:32:48,250
and I'm paying attention.

660
00:32:48,250 --> 00:32:50,230
And I eventually reach his page.

661
00:32:50,230 --> 00:32:52,890
And if I get too far, if
I get to the T section,

662
00:32:52,890 --> 00:32:55,900
then I can slightly optimize
and just say, hm, all done.

663
00:32:55,900 --> 00:32:57,980
I don't even need to waste
time going to the Z's.

664
00:32:57,980 --> 00:33:00,010
But this is a very
linear approach, if you

665
00:33:00,010 --> 00:33:03,370
will, a very sort of left-to-right
approach, a straight line.

666
00:33:03,370 --> 00:33:05,560
And its correct but slow.

667
00:33:05,560 --> 00:33:09,250
>> So I remember from grade school, sort
of an optimization from a first grader,

668
00:33:09,250 --> 00:33:13,756
where I learned how to count not
by ones but by twos-- so 2, 4, 6.

669
00:33:13,756 --> 00:33:15,630
It's A, lot harder to
do, but in theory, it's

670
00:33:15,630 --> 00:33:20,149
faster-- 8, 10, 12, 14, and so forth.

671
00:33:20,149 --> 00:33:21,190
How about that algorithm?

672
00:33:21,190 --> 00:33:23,150
Is it more efficient?

673
00:33:23,150 --> 00:33:23,880
Is it faster?

674
00:33:23,880 --> 00:33:25,365
>> AUDIENCE: It's efficient.

675
00:33:25,365 --> 00:33:28,560
>> DAVID MALAN: Yeah, so it's def-- it's
literally twice as fast, assuming I

676
00:33:28,560 --> 00:33:30,170
don't get tripped up with my fingers.

677
00:33:30,170 --> 00:33:32,294
It's twice as fast, because
I'm turning through two

678
00:33:32,294 --> 00:33:36,560
pages at once instead of one, but it's
potentially in correct, because why?

679
00:33:36,560 --> 00:33:37,852
>> AUDIENCE: You're skipping some.

680
00:33:37,852 --> 00:33:41,185
DAVID MALAN: Right, what if Mike happens
to be sandwiched-- maybe when I'm later

681
00:33:41,185 --> 00:33:44,370
in the phone book, Mike happens to be
sandwiched between these two pages,

682
00:33:44,370 --> 00:33:46,720
and I just blindly skip over it.

683
00:33:46,720 --> 00:33:48,490
So we need a little fix there.

684
00:33:48,490 --> 00:33:51,290
Once I hit the T section, I
can't just confidently say,

685
00:33:51,290 --> 00:33:52,420
we didn't find Mike Smith.

686
00:33:52,420 --> 00:33:53,770
I probably have to double back.

687
00:33:53,770 --> 00:34:00,210
Or in fact, once I reach someone
named S-N, instead of S-M for Smith,

688
00:34:00,210 --> 00:34:02,790
immediately, I could double
back, because maybe he

689
00:34:02,790 --> 00:34:03,900
was on the previous page.

690
00:34:03,900 --> 00:34:05,070
>> But I don't have to double back far.

691
00:34:05,070 --> 00:34:08,030
In theory, if I do it at the right
time, I just go back one page.

692
00:34:08,030 --> 00:34:10,139
So it's adding only one extra step.

693
00:34:10,139 --> 00:34:13,070
So I've gone twice as fast,
but it cost me one extra page.

694
00:34:13,070 --> 00:34:14,699
But that feels like a net win.

695
00:34:14,699 --> 00:34:17,230
>> But this is not how most people in
this room would solve this problem.

696
00:34:17,230 --> 00:34:20,313
What would a typical person, maybe a
few years ago do, to find Mike Smith?

697
00:34:20,313 --> 00:34:22,900

698
00:34:22,900 --> 00:34:24,800
Yeah, didn't find Mike.

699
00:34:24,800 --> 00:34:27,190
What do I do?

700
00:34:27,190 --> 00:34:31,027
So get a little closer, but I do
know-- what is true about a phone book?

701
00:34:31,027 --> 00:34:32,110
AUDIENCE: It's sequential.

702
00:34:32,110 --> 00:34:32,760
DAVID MALAN: It's sequential.

703
00:34:32,760 --> 00:34:33,750
It's alphabetical.

704
00:34:33,750 --> 00:34:36,540
And so if I'm in the M section,
Mike is clearly to the right,

705
00:34:36,540 --> 00:34:39,949
I can literally tear
the problem in half--

706
00:34:39,949 --> 00:34:44,360
it's usually easier than that-- tear
the problem in half and throw it away,

707
00:34:44,360 --> 00:34:47,627
so that now, I have a problem that's
no longer 1,000 pages-- that was hard,

708
00:34:47,627 --> 00:34:50,210
because I think I actually tore
the phone book this time-- not

709
00:34:50,210 --> 00:34:52,219
1,000 pages, but 500.

710
00:34:52,219 --> 00:34:54,750
>> So the problem is literally half as big.

711
00:34:54,750 --> 00:34:58,170
And that's pretty compelling, because
with my previous algorithms, version

712
00:34:58,170 --> 00:35:02,870
1 and 2, I was only making the problem
one page smaller, two pages smaller

713
00:35:02,870 --> 00:35:03,470
at a time.

714
00:35:03,470 --> 00:35:07,230
Whereas now, I made it 500
pages smaller all at once.

715
00:35:07,230 --> 00:35:10,089
>> OK, so now, Karim proposes
that I go to the right half.

716
00:35:10,089 --> 00:35:12,380
So I'm going to go roughly
to the middle, give or take.

717
00:35:12,380 --> 00:35:15,185
And if I did this mathematically,
I could go right to the middle.

718
00:35:15,185 --> 00:35:17,060
And now, I realize, oh,
I'm in the T section.

719
00:35:17,060 --> 00:35:18,280
I actually did go too far.

720
00:35:18,280 --> 00:35:21,670
>> But I can, again, tear the
problem in half, throw it away.

721
00:35:21,670 --> 00:35:23,330
And my bytes not as big.

722
00:35:23,330 --> 00:35:28,780
It's only, what, 256 pages or 250
pages, give or take right now.

723
00:35:28,780 --> 00:35:31,570
But it's still way more
than one page or two pages.

724
00:35:31,570 --> 00:35:33,345
>> And so now, I go roughly to the middle.

725
00:35:33,345 --> 00:35:35,330
Oh, I didn't go quite far enough now.

726
00:35:35,330 --> 00:35:37,880
So I repeat, repeat, repeat,
repeat, until I'm hopefully

727
00:35:37,880 --> 00:35:40,360
left with just one page.

728
00:35:40,360 --> 00:35:44,000
>> So that invites the question, if I
started with roughly 1,000 pages,

729
00:35:44,000 --> 00:35:47,340
how many steps did it take me
with version 1 of my algorithm?

730
00:35:47,340 --> 00:35:50,420
Well, if Mike is in the S
section, in the worst case,

731
00:35:50,420 --> 00:35:52,630
that's pretty close to
the end of the alphabet.

732
00:35:52,630 --> 00:35:56,559
So if the phone book has 1,000 pages,
I'll find Mike within 1,000 pages,

733
00:35:56,559 --> 00:35:57,100
give or take.

734
00:35:57,100 --> 00:35:59,750
Maybe it's like 800 or so, but
it's pretty close to 1,000.

735
00:35:59,750 --> 00:36:01,680
>> Whereas, in the second
algorithm, how many

736
00:36:01,680 --> 00:36:06,840
page turns maximally might I
require to find Mike Smith?

737
00:36:06,840 --> 00:36:09,970
There's 1,000 pages, but I'm
doing them two at a time.

738
00:36:09,970 --> 00:36:13,045
Right, so max like 500ish, because
if I go through the whole phone book,

739
00:36:13,045 --> 00:36:14,170
at which point, I can stop.

740
00:36:14,170 --> 00:36:16,669
But I can shave off a few by
just stopping at the T section.

741
00:36:16,669 --> 00:36:19,880
But it's at worst case 500 pages.

742
00:36:19,880 --> 00:36:24,710
>> So how many times can I divide a
1,00o-page phone book in half again

743
00:36:24,710 --> 00:36:30,450
and again and again-- from
1,000 to 500 to 250 to 125?

744
00:36:30,450 --> 00:36:32,250
How long before I hit one page?

745
00:36:32,250 --> 00:36:35,510

746
00:36:35,510 --> 00:36:36,370
Yeah, it's about 10.

747
00:36:36,370 --> 00:36:40,780
Depending on rounding and such, it's
about 10 pages total need to be turned

748
00:36:40,780 --> 00:36:43,290
or phone books need to be torn.

749
00:36:43,290 --> 00:36:44,710
>> So that's pretty powerful.

750
00:36:44,710 --> 00:36:48,170
We started with a 1,000-page problem
in all three of these stories.

751
00:36:48,170 --> 00:36:51,850
But in the first algorithm, it
took me, worst case, 1,000 page

752
00:36:51,850 --> 00:36:52,740
turns to find Mike.

753
00:36:52,740 --> 00:36:55,590
Second algorithm, 500
pages to find Mike.

754
00:36:55,590 --> 00:36:58,480
Third algorithm, 10 pages to find Mike.

755
00:36:58,480 --> 00:37:00,230
And it's even more
powerful when you think

756
00:37:00,230 --> 00:37:01,860
about sort of an opposite scenario.

757
00:37:01,860 --> 00:37:05,680
Suppose that the phone company next
year maybe merges two towns together,

758
00:37:05,680 --> 00:37:08,550
and the phone book is suddenly
this thick, instead of this that,

759
00:37:08,550 --> 00:37:12,470
so 2,000 pages instead of 1,000.

760
00:37:12,470 --> 00:37:15,640
Well, my first algorithm looking for
Mike Smith in a 2,000-page phone book,

761
00:37:15,640 --> 00:37:21,460
worse case, it's going to take
how many page turns next year?

762
00:37:21,460 --> 00:37:24,800
>> Phone book is 2,000 pages,
so-- well, not one more.

763
00:37:24,800 --> 00:37:29,540
If the phone book is twice as thick in
the first algorithm, first algorithm,

764
00:37:29,540 --> 00:37:30,380
2,000, right?

765
00:37:30,380 --> 00:37:33,005
In the worst case, Mike is really
close to the end of the book,

766
00:37:33,005 --> 00:37:34,110
so it's 2,000 page turns.

767
00:37:34,110 --> 00:37:38,070
Second algorithm going by
twos, like 1,000 pages.

768
00:37:38,070 --> 00:37:41,490
>> But how about in my third
and most recent algorithm?

769
00:37:41,490 --> 00:37:44,950
If the phone company doubles the
number of pages from 1,000 to 2,000,

770
00:37:44,950 --> 00:37:47,770
how many more times need I tear
that book in half to find Mike?

771
00:37:47,770 --> 00:37:48,710
>> AUDIENCE: Just one.

772
00:37:48,710 --> 00:37:51,001
>> DAVID MALAN: Just one more,
because with one page tear,

773
00:37:51,001 --> 00:37:53,270
I can literally divide
and conquer, if you will,

774
00:37:53,270 --> 00:37:57,410
that problem in half taking
a massive bite out of it.

775
00:37:57,410 --> 00:38:01,420
And so this is an example of
efficiency and arguably an algorithm

776
00:38:01,420 --> 00:38:04,100
with which all of us are
sort of intuitively familiar.

777
00:38:04,100 --> 00:38:07,780
But it's just as correct
as my other algorithms

778
00:38:07,780 --> 00:38:09,630
with that tweak for
the second algorithm,

779
00:38:09,630 --> 00:38:11,290
but it's so much more efficient.

780
00:38:11,290 --> 00:38:14,030
>> And in fact, what a computer
scientist, or in turn a programmer,

781
00:38:14,030 --> 00:38:17,580
would typically do when writing
code is try to figure out,

782
00:38:17,580 --> 00:38:19,960
all right, I don't want my
program just to be correct,

783
00:38:19,960 --> 00:38:23,220
I also want it to be efficient
and solve problems well.

784
00:38:23,220 --> 00:38:26,450
Imagine in the real world today,
like Google indexes, searches

785
00:38:26,450 --> 00:38:31,580
like billions of pages, imagine if they
used the first algorithm to find cats

786
00:38:31,580 --> 00:38:34,620
among a billion pages-- looking at
the first page in their database,

787
00:38:34,620 --> 00:38:37,700
the second, the third, just looking
for a cat, looking for a cat.

788
00:38:37,700 --> 00:38:40,350
That's pretty darn slow it would seem.

789
00:38:40,350 --> 00:38:43,170
They could instead use something
called binary search, which

790
00:38:43,170 --> 00:38:47,420
is no coincidence-- bi meaning two, we
keep dividing something in 2, in half--

791
00:38:47,420 --> 00:38:50,205
they could use binary search
and maybe find cats even faster,

792
00:38:50,205 --> 00:38:51,830
or whatever it is you're searching for.

793
00:38:51,830 --> 00:38:54,125
>> And frankly, there's
even fancier algorithms

794
00:38:54,125 --> 00:38:56,250
that do much more than just
dividing things in half

795
00:38:56,250 --> 00:38:58,180
in order to find information quickly.

796
00:38:58,180 --> 00:39:00,880
And we'll talk a little bit
about those after lunch today.

797
00:39:00,880 --> 00:39:02,640
So let me just try to represent this.

798
00:39:02,640 --> 00:39:05,380
We don't need to go into
any math or actual numbers.

799
00:39:05,380 --> 00:39:07,070
We can talk about this in the abstract.

800
00:39:07,070 --> 00:39:11,580
>> But let me just propose, if you
were having a discussion now

801
00:39:11,580 --> 00:39:13,491
with the engineers
proposing this algorithm

802
00:39:13,491 --> 00:39:15,490
and you're trying to make
a calculated decision,

803
00:39:15,490 --> 00:39:17,285
because maybe the
engineer says to you, you

804
00:39:17,285 --> 00:39:19,910
know what, I can implement a
linear search in like two minutes.

805
00:39:19,910 --> 00:39:21,150
It's that easy.

806
00:39:21,150 --> 00:39:24,790
Binary search is not that fancy, but
it's going to take me like 10 minutes,

807
00:39:24,790 --> 00:39:26,650
so 5 times as long.

808
00:39:26,650 --> 00:39:30,900
>> There's a trade here, even in terms
of deciding what software to write.

809
00:39:30,900 --> 00:39:34,760
Do you write the simpler algorithm,
which will just take you two minutes?

810
00:39:34,760 --> 00:39:39,880
Or do you spend more time, 10 minutes,
writing the fancier algorithm?

811
00:39:39,880 --> 00:39:43,540
How do you decide that kind of question?

812
00:39:43,540 --> 00:39:46,710
Or you could make it a little more real.

813
00:39:46,710 --> 00:39:50,610
I tell my boss it's going to take
me either one week or 10 weeks

814
00:39:50,610 --> 00:39:52,490
to implement the
software in this way, how

815
00:39:52,490 --> 00:39:56,103
do you decide which
algorithm to green-light?

816
00:39:56,103 --> 00:39:56,603
Karim?

817
00:39:56,603 --> 00:39:57,550
>> AUDIENCE: The audience, I guess.

818
00:39:57,550 --> 00:39:57,960
>> DAVID MALAN: The audience.

819
00:39:57,960 --> 00:39:59,460
What do you mean by the audience?

820
00:39:59,460 --> 00:40:03,460
>> AUDIENCE: If it's going
to be used by users

821
00:40:03,460 --> 00:40:09,050
who [INAUDIBLE] by users [INAUDIBLE].

822
00:40:09,050 --> 00:40:11,232
But if it's something you're
just doing for yourself

823
00:40:11,232 --> 00:40:13,946
to facilitate a problem,
[INAUDIBLE] quicker.

824
00:40:13,946 --> 00:40:16,820
DAVID MALAN: Yeah, it's quick and
dirty is a good way to describe it.

825
00:40:16,820 --> 00:40:18,695
In fact, if you're
describing much of my time

826
00:40:18,695 --> 00:40:23,630
in grad school, whereby often times,
I wrote bad code consciously so--

827
00:40:23,630 --> 00:40:26,490
at least, that's how I
rationalized it-- consciously so,

828
00:40:26,490 --> 00:40:30,670
because even though I was writing code
that was relatively slow to execute,

829
00:40:30,670 --> 00:40:33,750
I was able to write the code itself
pretty fast, spending just minutes

830
00:40:33,750 --> 00:40:35,107
or hours not days.

831
00:40:35,107 --> 00:40:37,190
And it turned out, I
occasionally needed to sleep.

832
00:40:37,190 --> 00:40:41,270
So even if my code required 8
hours to run, well that's fine,

833
00:40:41,270 --> 00:40:42,850
I'll just go to sleep while it runs.

834
00:40:42,850 --> 00:40:46,350
>> So at the time, I thought this was
very clever, even though I apparently

835
00:40:46,350 --> 00:40:48,990
worked through my PhD very slowly.

836
00:40:48,990 --> 00:40:52,270
But the converse of that is
that, if I were writing software

837
00:40:52,270 --> 00:40:55,930
for other people who
mattered more than me, well,

838
00:40:55,930 --> 00:40:59,580
having them wait 8 hours to
get back their search results

839
00:40:59,580 --> 00:41:01,350
is not all that compelling.

840
00:41:01,350 --> 00:41:04,090
And so spending more time
up front to write software

841
00:41:04,090 --> 00:41:07,300
that is more efficient, more
like our third algorithm,

842
00:41:07,300 --> 00:41:09,780
probably benefits the users over time.

843
00:41:09,780 --> 00:41:12,710
So it really depends over
time how those costs add up.

844
00:41:12,710 --> 00:41:14,960
If you're going to be writing
software to use it once,

845
00:41:14,960 --> 00:41:17,240
probably might as well do
quick and dirty, as they say.

846
00:41:17,240 --> 00:41:18,198
Just throw it together.

847
00:41:18,198 --> 00:41:20,560
It's code that embarrasses
you, it's so bad,

848
00:41:20,560 --> 00:41:23,860
but it gets the job done correctly,
even though it's not efficient.

849
00:41:23,860 --> 00:41:27,200
Conversely, you spend more time
on something, get it just right.

850
00:41:27,200 --> 00:41:30,730
And then amortized over time,
that upfront cost of time

851
00:41:30,730 --> 00:41:34,330
is probably worthwhile, if you keep
optimizing for the common case.

852
00:41:34,330 --> 00:41:37,620
>> And indeed, that's a theme in
programming, or computer science more

853
00:41:37,620 --> 00:41:41,390
generally, trying to optimize
not for the uncommon case

854
00:41:41,390 --> 00:41:44,390
but the common case-- what operation
is going to happen again and again?

855
00:41:44,390 --> 00:41:47,730
If you're going to have billions
of users searching on your website,

856
00:41:47,730 --> 00:41:52,030
you should probably spend the extra
weeks up front writing better software,

857
00:41:52,030 --> 00:41:53,670
so that all of your users benefit.

858
00:41:53,670 --> 00:41:57,840
Now, let's try to capture this a
little pictorially, but not so much

859
00:41:57,840 --> 00:41:58,610
numerically.

860
00:41:58,610 --> 00:42:01,680
>> So here's just an old school chart.

861
00:42:01,680 --> 00:42:04,260
And let me say that this is time.

862
00:42:04,260 --> 00:42:06,660
And it doesn't matter what--
actually, no, not time.

863
00:42:06,660 --> 00:42:08,320
Let's put that on the other axis.

864
00:42:08,320 --> 00:42:15,700
Let's say that this is the time,
and this is size of problem.

865
00:42:15,700 --> 00:42:17,830
>> And a computer scientist
might generally call

866
00:42:17,830 --> 00:42:20,820
this just n. n is like
our go-to variable, where

867
00:42:20,820 --> 00:42:26,351
n is a number, n number, and it's the
number of whatever inputs you have.

868
00:42:26,351 --> 00:42:28,100
So in this case, n is
the number of pages.

869
00:42:28,100 --> 00:42:30,150
So it might be 1,000 in
the case we just told.

870
00:42:30,150 --> 00:42:31,969
>> So time can be any unit of measure.

871
00:42:31,969 --> 00:42:32,760
Maybe, it's second.

872
00:42:32,760 --> 00:42:33,410
Maybe, it's days.

873
00:42:33,410 --> 00:42:34,590
Maybe, it's like page turns.

874
00:42:34,590 --> 00:42:35,215
Doesn't matter.

875
00:42:35,215 --> 00:42:38,840
Whatever you want to count in, that
will be time or cost equivalently.

876
00:42:38,840 --> 00:42:42,400
>> So with that very first
algorithm, if I, for instance,

877
00:42:42,400 --> 00:42:45,920
had a 1,000-page phone book,
I'm going to draw a dot there,

878
00:42:45,920 --> 00:42:51,450
because if it's 1,000 pages, it took
roughly 1,000 page turns, give or take.

879
00:42:51,450 --> 00:42:54,100
And then if I had a
2,000-page phone book,

880
00:42:54,100 --> 00:42:57,200
and I'm going to draw a second
dot here, because for 2,000 pages,

881
00:42:57,200 --> 00:42:59,810
it's like 2,000 seconds
or page turns or whatever.

882
00:42:59,810 --> 00:43:02,480
And so when I said earlier, it's
kind of a linear relationship,

883
00:43:02,480 --> 00:43:06,020
that was deliberate, because I wanted
later on-- right now-- to draw a line.

884
00:43:06,020 --> 00:43:07,770
It's kind of a straight
line relationship.

885
00:43:07,770 --> 00:43:10,180
The slope is 1/1, if you will.

886
00:43:10,180 --> 00:43:14,630
>> Meanwhile, the second algorithm
said, if you've got 1,000 pages

887
00:43:14,630 --> 00:43:17,680
and you were using the second algorithm,
where I counted by 2's, turning

888
00:43:17,680 --> 00:43:22,564
two pages at a time, should I draw a
dot below or above my original dot?

889
00:43:22,564 --> 00:43:23,450
>> AUDIENCE: Below.

890
00:43:23,450 --> 00:43:27,992
>> DAVID MALAN: Below, because as we saw,
it takes less time, half as much time.

891
00:43:27,992 --> 00:43:29,950
So the dot should be half
as high as the other.

892
00:43:29,950 --> 00:43:33,330
And same deal over here, this dot
should probably be roughly there.

893
00:43:33,330 --> 00:43:39,666
And so my second algorithm, similarly,
has a linear relationship with time.

894
00:43:39,666 --> 00:43:41,990
And we can draw it as such.

895
00:43:41,990 --> 00:43:45,950
>> So now, the third and final
algorithm is a little harder to draw.

896
00:43:45,950 --> 00:43:49,530
But intuitively, if I've got 1,000
pages with my third algorithm,

897
00:43:49,530 --> 00:43:52,340
it should only take me like 10 steps.

898
00:43:52,340 --> 00:43:57,500
And if I've got 2,000 pages
with my third algorithm,

899
00:43:57,500 --> 00:44:01,570
it should take me not 10
steps, but 11, just one more.

900
00:44:01,570 --> 00:44:03,610
So we're only barely going to see this.

901
00:44:03,610 --> 00:44:06,010
>> And it turns out, if
I zoom in on this, I'm

902
00:44:06,010 --> 00:44:09,320
going to exaggerate for effect,
the shape of that line, ultimately,

903
00:44:09,320 --> 00:44:11,990
is not a straight line--
because, indeed if it were,

904
00:44:11,990 --> 00:44:15,390
it would look more like the
others-- it's actually a curved line

905
00:44:15,390 --> 00:44:19,265
that, if we zoom in, is going
to look much more like this.

906
00:44:19,265 --> 00:44:21,670
It-- well, OK, ignore this part.

907
00:44:21,670 --> 00:44:25,330
That was my pen going of angle.

908
00:44:25,330 --> 00:44:29,000
It's a curved line that is always
increasing, always, always, always

909
00:44:29,000 --> 00:44:32,100
increasing, but only just barely.

910
00:44:32,100 --> 00:44:36,260
>> And so over time, you have a
relationship that's more like this.

911
00:44:36,260 --> 00:44:37,540
It almost looks straight.

912
00:44:37,540 --> 00:44:40,330
But it's ever so slowly increasing.

913
00:44:40,330 --> 00:44:44,780
But for almost all points along
your x-axis, horizontal axis,

914
00:44:44,780 --> 00:44:46,550
it's lower than those other lines.

915
00:44:46,550 --> 00:44:49,930
>> So this might be a relationship
n, whereby if you have n pages,

916
00:44:49,930 --> 00:44:51,100
takes you n seconds.

917
00:44:51,100 --> 00:44:53,320
This might be a relationship n/2.

918
00:44:53,320 --> 00:44:56,710
You have n pages, it takes
you n/2 seconds, half as many.

919
00:44:56,710 --> 00:45:00,590
And this is a logarithmic
relationship, which

920
00:45:00,590 --> 00:45:08,920
if you recall, log base 2 of n captures
this kind of growth, so to speak.

921
00:45:08,920 --> 00:45:12,000
So this is the sort of holy
grail among the three of these

922
00:45:12,000 --> 00:45:15,940
here, because it's just so much more
efficient, but arguably more complex

923
00:45:15,940 --> 00:45:18,610
to implement.

924
00:45:18,610 --> 00:45:20,510
Any questions?

925
00:45:20,510 --> 00:45:26,220
>> Well let me do this, let
me open up a text window

926
00:45:26,220 --> 00:45:29,100
just so we can try to
formalize something here.

927
00:45:29,100 --> 00:45:32,410
So let me go ahead now and
implement this algorithm

928
00:45:32,410 --> 00:45:35,170
for finding Mike Smith in code,
if you will, pseudocode code.

929
00:45:35,170 --> 00:45:36,620
I'm not going to use Java or C++.

930
00:45:36,620 --> 00:45:38,610
I'm just going to use sort of
English-like syntax, which we

931
00:45:38,610 --> 00:45:40,151
would generally call pseudocode code.

932
00:45:40,151 --> 00:45:41,660
Here, I have a blank window.

933
00:45:41,660 --> 00:45:48,180
And I'm saying step 1 of the very
first algorithm is pick up phone book.

934
00:45:48,180 --> 00:45:51,740
Step 2 is open book to first page.

935
00:45:51,740 --> 00:45:58,080
Step 3 will be look at
page for Mike Smith.

936
00:45:58,080 --> 00:46:02,740
If on page, call Mike.

937
00:46:02,740 --> 00:46:11,640
else turn page and go to step 3.

938
00:46:11,640 --> 00:46:13,590
Done, let's say.

939
00:46:13,590 --> 00:46:18,110
>> And so it's not quite perfect,
which we'll see in a moment.

940
00:46:18,110 --> 00:46:21,050
But let's consider what
concepts I've introduced here.

941
00:46:21,050 --> 00:46:24,450
So steps 1 and 2 and 3
are pretty much verbs.

942
00:46:24,450 --> 00:46:26,544
They're statements, actions-- do this.

943
00:46:26,544 --> 00:46:28,710
And so in a programming
language, we would generally

944
00:46:28,710 --> 00:46:32,349
call them statements or
functions or procedures,

945
00:46:32,349 --> 00:46:33,640
call them any number of things.

946
00:46:33,640 --> 00:46:35,460
But they're just actions-- do this.

947
00:46:35,460 --> 00:46:40,370
>> Step 4 is fundamentally different,
because it's kind of asking a question.

948
00:46:40,370 --> 00:46:42,400
It's saying we're kind
of at a fork in the road.

949
00:46:42,400 --> 00:46:48,000
If Mike is on the page, call
him, so turn left, if you will.

950
00:46:48,000 --> 00:46:52,170
And if not, go back to some
other page-- or rather, sorry,

951
00:46:52,170 --> 00:46:56,650
go back to some other step, which
induces some kind of looping construct.

952
00:46:56,650 --> 00:46:59,530
And we do it again and again and again.

953
00:46:59,530 --> 00:47:01,300
>> And actually, you know what?

954
00:47:01,300 --> 00:47:01,800
Yeah.

955
00:47:01,800 --> 00:47:04,704

956
00:47:04,704 --> 00:47:09,010
else if at end of book stop.

957
00:47:09,010 --> 00:47:11,624
So we need kind of a third
condition, because you

958
00:47:11,624 --> 00:47:14,290
can't keep turning the page ad
nauseum, because eventually, I'll

959
00:47:14,290 --> 00:47:15,320
hit the end of the book.

960
00:47:15,320 --> 00:47:18,546
And a bug in a program might be
not anticipating that scenario.

961
00:47:18,546 --> 00:47:21,420
And then I just realized, oh, wait
a minute, I need a third scenario.

962
00:47:21,420 --> 00:47:23,900
If I'm out of pages, I
should really just stop.

963
00:47:23,900 --> 00:47:25,330
Otherwise, it's undefined.

964
00:47:25,330 --> 00:47:29,260
What's going to happen if I keep
saying turn the page and go back,

965
00:47:29,260 --> 00:47:31,810
this is when computers
freeze or crash, when you hit

966
00:47:31,810 --> 00:47:34,160
some unanticipated situation like that.

967
00:47:34,160 --> 00:47:37,280
>> Now, what about Mike
Smith's third algorithm--

968
00:47:37,280 --> 00:47:43,150
pick up the phone book,
open book to first-- to

969
00:47:43,150 --> 00:47:48,640
no, not first page this time,
to middle-- oh, well, that'd

970
00:47:48,640 --> 00:47:49,640
be the second algorithm.

971
00:47:49,640 --> 00:47:50,590
Let's just skip to the third.

972
00:47:50,590 --> 00:47:50,930
>> AUDIENCE: Oh, I'm sorry.

973
00:47:50,930 --> 00:47:51,971
>> DAVID MALAN: That's fine.

974
00:47:51,971 --> 00:47:58,590
Let's just skip to the third-- open
to middle and now look for Mike Smith.

975
00:47:58,590 --> 00:48:02,300
if on page, call Mike.

976
00:48:02,300 --> 00:48:04,910
And then what do we want to say here?

977
00:48:04,910 --> 00:48:06,134
else what?

978
00:48:06,134 --> 00:48:10,620

979
00:48:10,620 --> 00:48:12,370
We can express this
in any number of ways.

980
00:48:12,370 --> 00:48:13,369
There's no right answer.

981
00:48:13,369 --> 00:48:20,819

982
00:48:20,819 --> 00:48:23,735
OK, if not again, but we need to
be-- OK, we do want to divide in two,

983
00:48:23,735 --> 00:48:25,630
but do we want to go left or go right?

984
00:48:25,630 --> 00:48:29,560
How do we express that notion?

985
00:48:29,560 --> 00:48:31,790
Well, in Mike's case, yes, that's fair.

986
00:48:31,790 --> 00:48:35,050
But OK, so that's actually a good point.

987
00:48:35,050 --> 00:48:35,550
That's fine.

988
00:48:35,550 --> 00:48:36,924
We'll keep going with this logic.

989
00:48:36,924 --> 00:48:38,182
So--

990
00:48:38,182 --> 00:48:39,810
>> AUDIENCE: Less than half.

991
00:48:39,810 --> 00:48:40,560
DAVID MALAN: Yeah.

992
00:48:40,560 --> 00:48:49,820
So else if page is, we'll say, less
than Smith, to the left of Smith,

993
00:48:49,820 --> 00:48:52,220
then-- let's see, is
this going to complicate?

994
00:48:52,220 --> 00:49:01,885
else if page comes before Smith,
tear in half, throw away which half?

995
00:49:01,885 --> 00:49:05,643

996
00:49:05,643 --> 00:49:09,140
>> AUDIENCE: I thought
that was [INAUDIBLE].

997
00:49:09,140 --> 00:49:11,650
>> DAVID MALAN: I'm hearing both answers.

998
00:49:11,650 --> 00:49:12,431
>> AUDIENCE: Left.

999
00:49:12,431 --> 00:49:14,430
DAVID MALAN: OK, throw
away left half, as Lakisa

1000
00:49:14,430 --> 00:49:19,700
said earlier, the left
half, then I kind of

1001
00:49:19,700 --> 00:49:23,940
want to just go to-- I go to the right.

1002
00:49:23,940 --> 00:49:27,380
Or equivalently, and I made a little
bit of a mess of the beginning here,

1003
00:49:27,380 --> 00:49:30,760
I effectively want to
go to step 2 again,

1004
00:49:30,760 --> 00:49:38,270
where open to the middle-- or open--
yeah, let's just say, pages to middle.

1005
00:49:38,270 --> 00:49:39,020
And this fixes it.

1006
00:49:39,020 --> 00:49:39,936
It's no longer a book.

1007
00:49:39,936 --> 00:49:42,210
It's just half of a book,
so open pages to middle.

1008
00:49:42,210 --> 00:49:44,010
>> else-- were almost there.

1009
00:49:44,010 --> 00:49:54,000
Step 6, else if page comes after Smith,
tear in half, throw away right half,

1010
00:49:54,000 --> 00:49:55,680
then go to step 2.

1011
00:49:55,680 --> 00:49:58,920

1012
00:49:58,920 --> 00:50:05,230
else quit, a fourth scenario if
we have no pages left to turn.

1013
00:50:05,230 --> 00:50:06,394
So we could clean this up.

1014
00:50:06,394 --> 00:50:07,560
And we should clean this up.

1015
00:50:07,560 --> 00:50:10,656
This is very pseudocode code, if you
will, very high level description.

1016
00:50:10,656 --> 00:50:12,280
But it does generally capture the idea.

1017
00:50:12,280 --> 00:50:16,040
>> And, again, in this scenario, we
have the notion of a condition,

1018
00:50:16,040 --> 00:50:20,450
a branch, a fork in the road, making
a decision-- if this, go this way,

1019
00:50:20,450 --> 00:50:23,082
else if, go this way,
else if, go that way.

1020
00:50:23,082 --> 00:50:25,040
And this is a very common
programming technique

1021
00:50:25,040 --> 00:50:27,721
to decide which direction
to go, so to speak.

1022
00:50:27,721 --> 00:50:29,970
And we also have some kind
of looping structure, where

1023
00:50:29,970 --> 00:50:32,440
we're doing something again and again.

1024
00:50:32,440 --> 00:50:34,820
>> Now, it turns out, much
as in this example,

1025
00:50:34,820 --> 00:50:37,660
being super precise is important.

1026
00:50:37,660 --> 00:50:42,180
But we've also seen something
that we keep calling abstraction.

1027
00:50:42,180 --> 00:50:45,490
What does it mean to pick up phone book?

1028
00:50:45,490 --> 00:50:47,740
We're just kind of taking
for granted in this room

1029
00:50:47,740 --> 00:50:49,340
that that has some semantic meaning.

1030
00:50:49,340 --> 00:50:51,740
All of us just kind of know, oh,
well, pick up the phone book.

1031
00:50:51,740 --> 00:50:52,864
What does that really mean?

1032
00:50:52,864 --> 00:50:59,060
Well, that really means extend
hand, lean over, extend fingers,

1033
00:50:59,060 --> 00:51:03,890
pinch book between fingers,
stand up, pull hand towards you.

1034
00:51:03,890 --> 00:51:05,940
And we could be really
pedantic about this,

1035
00:51:05,940 --> 00:51:08,640
really being super precise
as to what I'm doing.

1036
00:51:08,640 --> 00:51:13,300
But all of those steps collectively are
what it means to pick up a phone book.

1037
00:51:13,300 --> 00:51:16,940
>> And so earlier, when I said, each
of these first two statements

1038
00:51:16,940 --> 00:51:20,830
can be thought of as a
proceed or a function,

1039
00:51:20,830 --> 00:51:24,090
really it represents what we
keep calling an abstraction.

1040
00:51:24,090 --> 00:51:28,770
It's like a high level conceptual
description of a problem that

1041
00:51:28,770 --> 00:51:31,110
actually involves quite a few steps.

1042
00:51:31,110 --> 00:51:34,190
And so this, too, is a
recurring topic in programming,

1043
00:51:34,190 --> 00:51:41,125
whereby I might write a program
using syntax like this--

1044
00:51:41,125 --> 00:51:42,000
pick_up_phone_book().

1045
00:51:42,000 --> 00:51:44,344

1046
00:51:44,344 --> 00:51:46,510
And then syntactically, I'm
going to steal something

1047
00:51:46,510 --> 00:51:48,090
from most programming languages.

1048
00:51:48,090 --> 00:51:51,270
>> Now, step 1 looks even
more like a function,

1049
00:51:51,270 --> 00:51:53,160
as a programmer would call it.

1050
00:51:53,160 --> 00:51:58,650
It looks like code that someone
has given a name to and given

1051
00:51:58,650 --> 00:52:03,300
to me to use somehow-- in other
words, what the line I've highlighted

1052
00:52:03,300 --> 00:52:07,050
represents functionality that maybe
I didn't even implement myself.

1053
00:52:07,050 --> 00:52:10,410
Someone older, wiser than
me already figured out

1054
00:52:10,410 --> 00:52:12,700
how you express the notion
of picking up a phone book.

1055
00:52:12,700 --> 00:52:15,860
And it's like the five steps I just
rattled off, off the top of my head.

1056
00:52:15,860 --> 00:52:19,350
>> But he or she already implemented
this, gave those several steps

1057
00:52:19,350 --> 00:52:22,339
a name, pick_up_phone_book.

1058
00:52:22,339 --> 00:52:24,380
And the parentheses is
just what most programmers

1059
00:52:24,380 --> 00:52:27,100
do at the end of statements like this.

1060
00:52:27,100 --> 00:52:30,190
I now can stand on his or her
shoulders and never again,

1061
00:52:30,190 --> 00:52:32,465
think about what it means
to pick up a phone book.

1062
00:52:32,465 --> 00:52:34,090
I can just say, pick up the phone book.

1063
00:52:34,090 --> 00:52:36,690
And that's exactly what
all of us humans did here.

1064
00:52:36,690 --> 00:52:38,940
>> When we were probably 1
year old, 2 years old,

1065
00:52:38,940 --> 00:52:41,690
someone had to teach us what it
meant to pick up a phone book.

1066
00:52:41,690 --> 00:52:43,810
And ever since then,
we've abstracted away

1067
00:52:43,810 --> 00:52:46,739
from those very uninteresting
mechanical steps.

1068
00:52:46,739 --> 00:52:48,530
And we just have an
intuitive understanding

1069
00:52:48,530 --> 00:52:50,480
of what it means to
pick up a phone book.

1070
00:52:50,480 --> 00:52:55,730
>> And you can extrapolate now
to more complicated things--

1071
00:52:55,730 --> 00:52:57,640
construct a building.

1072
00:52:57,640 --> 00:52:59,940
Like, to some people,
that actually has meaning.

1073
00:52:59,940 --> 00:53:03,080
To contractors, to architects,
that has some meaning.

1074
00:53:03,080 --> 00:53:06,400
And they would know what to do, if
I said, go construct a building.

1075
00:53:06,400 --> 00:53:10,520
>> But most of us in the room couldn't
deal with that level of abstraction.

1076
00:53:10,520 --> 00:53:14,850
You need to tell us like go get
the shovel and go get the concrete

1077
00:53:14,850 --> 00:53:17,250
and nail the pieces of wood
together and whatever else

1078
00:53:17,250 --> 00:53:18,830
is involved in building a building.

1079
00:53:18,830 --> 00:53:21,690
And that's because we have not
yet been programmed to understand

1080
00:53:21,690 --> 00:53:23,629
what it means to construct a building.

1081
00:53:23,629 --> 00:53:24,920
We don't have that abstraction.

1082
00:53:24,920 --> 00:53:26,570
We don't have that functionality.

1083
00:53:26,570 --> 00:53:29,930
>> And so what you'll see in
programming languages, in general,

1084
00:53:29,930 --> 00:53:34,570
especially more modern languages,
like Java, PHP, Ruby, and Python,

1085
00:53:34,570 --> 00:53:37,610
they're much more mature
than older languages,

1086
00:53:37,610 --> 00:53:40,140
like C and C++ and yet others.

1087
00:53:40,140 --> 00:53:42,580
And so they come with more
functionality built in.

1088
00:53:42,580 --> 00:53:45,640
More code has been written
by people in the past

1089
00:53:45,640 --> 00:53:50,520
that we can now call or
summon or use, as I'm hinting

1090
00:53:50,520 --> 00:53:52,231
at with this highlighted line here.

1091
00:53:52,231 --> 00:53:55,230
And so even though we're not talking
about programming languages per se,

1092
00:53:55,230 --> 00:54:00,230
just pseudocode code, all of the
ideas are still in that discussion.

1093
00:54:00,230 --> 00:54:04,600
And it turns out precision is
super important, as is abstraction.

1094
00:54:04,600 --> 00:54:06,570
And let's try to
communicate that as follows.

1095
00:54:06,570 --> 00:54:11,000
>> I accidentally might have spoiled
this by flashing a slide on the screen

1096
00:54:11,000 --> 00:54:12,260
prematurely.

1097
00:54:12,260 --> 00:54:16,550
But let me ask for a brave volunteer,
if you don't mind coming up.

1098
00:54:16,550 --> 00:54:19,040
You'd be in front of the
camera, if you're OK with that.

1099
00:54:19,040 --> 00:54:24,950
Would anyone like to come up and give
instructions to your colleagues here?

1100
00:54:24,950 --> 00:54:29,540
Just have to come over here and
stand over here and say some words.

1101
00:54:29,540 --> 00:54:32,890
>> Victoria is smiling the most
and avoiding my eyes the most.

1102
00:54:32,890 --> 00:54:34,740
Would you be willing to come on up?

1103
00:54:34,740 --> 00:54:35,240
OK.

1104
00:54:35,240 --> 00:54:38,480
And if everyone else at your seats
could take out a piece of scrap paper,

1105
00:54:38,480 --> 00:54:39,750
if you will.

1106
00:54:39,750 --> 00:54:40,760
Lined paper is fine.

1107
00:54:40,760 --> 00:54:41,990
Come around this way.

1108
00:54:41,990 --> 00:54:44,580
Or some of the paper that
you were given yesterday,

1109
00:54:44,580 --> 00:54:46,493
just any blank sheet
of paper, if you could.

1110
00:54:46,493 --> 00:54:52,240

1111
00:54:52,240 --> 00:54:54,870
And if you don't have any, just
ask your neighbor if you could.

1112
00:54:54,870 --> 00:55:04,220

1113
00:55:04,220 --> 00:55:07,580
>> So for the moment, for
this example, Victoria

1114
00:55:07,580 --> 00:55:11,520
is going to play the role of
a programmer, an engineer, who

1115
00:55:11,520 --> 00:55:16,130
needs to program you all, as
the computers, to do something.

1116
00:55:16,130 --> 00:55:19,570
And we'll see what assumptions
you decide to make.

1117
00:55:19,570 --> 00:55:22,700
We'll see how precise she chooses to be.

1118
00:55:22,700 --> 00:55:26,220
And if this demonstration goes
pedagogically well, lots of mistakes

1119
00:55:26,220 --> 00:55:29,220
will be made, that we'll then use
that as an opportunity for discussion.

1120
00:55:29,220 --> 00:55:32,010
But the challenge for you should
be to avoid those mistakes,

1121
00:55:32,010 --> 00:55:32,896
be a good programmer.

1122
00:55:32,896 --> 00:55:35,520
And so the challenge at hand, if
you'd liked to walk over here,

1123
00:55:35,520 --> 00:55:38,799
is in front of Victoria on the screen
here-- and hopefully, none of you

1124
00:55:38,799 --> 00:55:40,590
remember this when I
flashed on the screen.

1125
00:55:40,590 --> 00:55:44,097
And do not turn around at all, because
there is another screen in this room

1126
00:55:44,097 --> 00:55:44,930
that I can turn off.

1127
00:55:44,930 --> 00:55:46,620
So don't turn around.

1128
00:55:46,620 --> 00:55:49,090
>> In front of Victoria
is that same scream.

1129
00:55:49,090 --> 00:55:54,170
And her job now is to tell you all
on your piece of paper what to draw.

1130
00:55:54,170 --> 00:55:57,020
And we will see, based on
verbal instructions alone,

1131
00:55:57,020 --> 00:56:00,020
computer code, if you will,
how accurate your drawings

1132
00:56:00,020 --> 00:56:02,330
are-- your implementations are.

1133
00:56:02,330 --> 00:56:02,980
Make sense?

1134
00:56:02,980 --> 00:56:03,604
>> AUDIENCE: Yeah.

1135
00:56:03,604 --> 00:56:04,980
DAVID MALAN: OK, execute.

1136
00:56:04,980 --> 00:56:06,030
>> AUDIENCE: Draw a square.

1137
00:56:06,030 --> 00:56:09,050
>> [LAUGHTER]

1138
00:56:09,050 --> 00:56:12,310
>> DAVID MALAN: And no
questions may be asked.

1139
00:56:12,310 --> 00:56:13,720
Can only do what you're told.

1140
00:56:13,720 --> 00:56:17,570

1141
00:56:17,570 --> 00:56:22,550
Oh, and if you have today's slides
open in a tab, don't look at your tab.

1142
00:56:22,550 --> 00:56:23,670
OK?

1143
00:56:23,670 --> 00:56:26,135
>> AUDIENCE: OK, draw a circle.

1144
00:56:26,135 --> 00:56:32,544

1145
00:56:32,544 --> 00:56:34,872
A slope-- can I say slope?

1146
00:56:34,872 --> 00:56:35,830
DAVID MALAN: Up to you.

1147
00:56:35,830 --> 00:56:38,230

1148
00:56:38,230 --> 00:56:38,980
AUDIENCE: A slope.

1149
00:56:38,980 --> 00:56:46,330

1150
00:56:46,330 --> 00:56:49,795
And a triangle.

1151
00:56:49,795 --> 00:56:50,850
>> DAVID MALAN: All right.

1152
00:56:50,850 --> 00:56:52,286
And stay here for just a moment.

1153
00:56:52,286 --> 00:56:56,046

1154
00:56:56,046 --> 00:56:58,910
And I'm going to come
around in just a moment.

1155
00:56:58,910 --> 00:57:02,420
And no need to put your names on it.

1156
00:57:02,420 --> 00:57:05,030
Let me come around and
collect your drawings,

1157
00:57:05,030 --> 00:57:08,330
if you don't mind tearing them out.

1158
00:57:08,330 --> 00:57:12,110
>> Here is what we got back.

1159
00:57:12,110 --> 00:57:14,770
I'll project it on the screen.

1160
00:57:14,770 --> 00:57:18,310
I see a square, a circle,
a slope, and a triangle.

1161
00:57:18,310 --> 00:57:20,130
So that was one answer there.

1162
00:57:20,130 --> 00:57:23,640
And let's-- whoops.

1163
00:57:23,640 --> 00:57:25,370
Thank you.

1164
00:57:25,370 --> 00:57:30,710
Here's another assortment,
and one behind it.

1165
00:57:30,710 --> 00:57:34,130

1166
00:57:34,130 --> 00:57:37,120
>> So they all seem to capture the spirit.

1167
00:57:37,120 --> 00:57:38,600
Thank you.

1168
00:57:38,600 --> 00:57:44,970
There's another, and here's another one.

1169
00:57:44,970 --> 00:57:51,590
The slope interpretation is a
little different, little curvy.

1170
00:57:51,590 --> 00:57:57,140
And the closest, either because of the
wonderful specificity with which you've

1171
00:57:57,140 --> 00:58:03,520
described, or maybe you kind of
saw it before, this is indeed

1172
00:58:03,520 --> 00:58:06,340
what Victoria was actually describing.

1173
00:58:06,340 --> 00:58:09,190
>> But now, those of you who
didn't get it quite right,

1174
00:58:09,190 --> 00:58:11,140
let's offer some objections here.

1175
00:58:11,140 --> 00:58:13,770
So Victoria first said draw a square.

1176
00:58:13,770 --> 00:58:15,830
And now, we can assume
for the sake of today

1177
00:58:15,830 --> 00:58:17,538
that everyone knows
how to draw a square.

1178
00:58:17,538 --> 00:58:20,590
But that's not wholly clear, right?

1179
00:58:20,590 --> 00:58:23,220
How else could you have
drawn a square, or where

1180
00:58:23,220 --> 00:58:27,114
might be some of the ambiguities
here for the computer?

1181
00:58:27,114 --> 00:58:28,280
AUDIENCE: Location and size.

1182
00:58:28,280 --> 00:58:28,980
DAVID MALAN: Location, right?

1183
00:58:28,980 --> 00:58:32,070
All of you had a paper of some shape,
generally rectangles, but slightly

1184
00:58:32,070 --> 00:58:32,830
different sizes.

1185
00:58:32,830 --> 00:58:36,250
But you certainly could have drawn,
if you wanted, a huge square, maybe

1186
00:58:36,250 --> 00:58:37,220
a tiny square.

1187
00:58:37,220 --> 00:58:38,417
Maybe, it was rotated.

1188
00:58:38,417 --> 00:58:39,500
I don't think we saw that.

1189
00:58:39,500 --> 00:58:41,790
But it could have been more diamond
like but still, nonetheless,

1190
00:58:41,790 --> 00:58:42,900
mathematically a square.

1191
00:58:42,900 --> 00:58:44,850
So that was arguably ambiguous.

1192
00:58:44,850 --> 00:58:46,709
>> Then she said, draw a circle.

1193
00:58:46,709 --> 00:58:49,250
Some of you did draw it next to
it, which isn't unreasonable,

1194
00:58:49,250 --> 00:58:52,450
because humans tend to think or read
right to left in most languages, so not

1195
00:58:52,450 --> 00:58:53,017
a bad guess.

1196
00:58:53,017 --> 00:58:55,100
But that circle could have
been inside the square,

1197
00:58:55,100 --> 00:58:57,600
could have been around the
square, could have been elsewhere

1198
00:58:57,600 --> 00:58:59,480
on the sheet, so arguably ambiguous.

1199
00:58:59,480 --> 00:59:03,290
>> Slope might have been maybe
taking the most liberties verbally

1200
00:59:03,290 --> 00:59:04,200
with what that means.

1201
00:59:04,200 --> 00:59:06,980
And some of you interpreted
it as a squiggly line

1202
00:59:06,980 --> 00:59:08,560
or a straight line or the like.

1203
00:59:08,560 --> 00:59:11,719
And then triangle, too, could have
been oriented in any number of ways.

1204
00:59:11,719 --> 00:59:14,760
So in short, even with something that
you glance and you're like, wow, so

1205
00:59:14,760 --> 00:59:17,020
simple, a child could
draw this, well not

1206
00:59:17,020 --> 00:59:19,640
really, unless you're
super, super persuasive

1207
00:59:19,640 --> 00:59:22,045
and tell the computer
exactly what to do.

1208
00:59:22,045 --> 00:59:24,420
So if we could, if you have
another sheet of paper, let's

1209
00:59:24,420 --> 00:59:26,710
try this once more.

1210
00:59:26,710 --> 00:59:29,880
And I'm going to give Victoria one
other example on the screen here.

1211
00:59:29,880 --> 00:59:34,060
And again, don't turn around
and don't look at your slides.

1212
00:59:34,060 --> 00:59:37,304
And I'll give her a moment to
think about how to describe this.

1213
00:59:37,304 --> 00:59:39,012
Don't let them see
the fear in your eyes.

1214
00:59:39,012 --> 00:59:40,820
>> [LAUGHTER]

1215
00:59:40,820 --> 00:59:43,710
>> And again, this time leverage
some of those takeaways

1216
00:59:43,710 --> 00:59:48,130
and try to get almost everyone
at least the right answer.

1217
00:59:48,130 --> 00:59:52,260
>> AUDIENCE: OK, take a
piece of paper, look

1218
00:59:52,260 --> 00:59:54,500
in the middle of that piece of paper.

1219
00:59:54,500 --> 00:59:59,591
In the middle of that piece
of paper, draw a cube.

1220
00:59:59,591 --> 01:00:01,244
>> [LAUGHTER]

1221
01:00:01,244 --> 01:00:02,660
DAVID MALAN: What have we learned?

1222
01:00:02,660 --> 01:00:03,540
We were so close.

1223
01:00:03,540 --> 01:00:06,320

1224
01:00:06,320 --> 01:00:09,045
OK, repeat if you could, for everyone.

1225
01:00:09,045 --> 01:00:13,210
>> AUDIENCE: In the middle of the
piece of paper, draw an object,

1226
01:00:13,210 --> 01:00:14,842
which looks like a cube.

1227
01:00:14,842 --> 01:00:17,332
>> DAVID MALAN: OK, that's
all you get to work with.

1228
01:00:17,332 --> 01:00:20,010

1229
01:00:20,010 --> 01:00:23,080
Allow me to be analytical
and not so much critical,

1230
01:00:23,080 --> 01:00:25,720
but to make the claim
that Victoria definitely

1231
01:00:25,720 --> 01:00:28,967
seems to be thinking in very
high level abstractions, which

1232
01:00:28,967 --> 01:00:29,800
is not unreasonable.

1233
01:00:29,800 --> 01:00:32,160
Because otherwise, we'd all
be pretty dysfunctional,

1234
01:00:32,160 --> 01:00:35,740
if we had to be ever so precise
with everything we do in the world.

1235
01:00:35,740 --> 01:00:38,890
>> But saying go to the middle-- I
thought we were on such a good track

1236
01:00:38,890 --> 01:00:42,340
there, like go to the very middle
of the page, and then draw a cube.

1237
01:00:42,340 --> 01:00:45,730
So she's thinking in abstractions,
because she's still viewing

1238
01:00:45,730 --> 01:00:48,490
what's on the screen as indeed a cube.

1239
01:00:48,490 --> 01:00:51,185
But there's so many opportunities
for interpretation there.

1240
01:00:51,185 --> 01:00:53,560
And in fact, there's so many
other ways you could express

1241
01:00:53,560 --> 01:00:55,101
that, which I'll propose in a moment.

1242
01:00:55,101 --> 01:00:59,770
So here we have one incarnation
of the picture-- whoops-- one

1243
01:00:59,770 --> 01:01:02,830
incarnation of the picture, so a
little three dimensionality to it,

1244
01:01:02,830 --> 01:01:04,160
which is nice.

1245
01:01:04,160 --> 01:01:08,470
>> Here's another one, where you have the
same, though it's kind of an open cube.

1246
01:01:08,470 --> 01:01:12,020
Some folks took it a little
more flat, two dimensional.

1247
01:01:12,020 --> 01:01:13,910
And that's fine.

1248
01:01:13,910 --> 01:01:17,380
So there, indeed in the
center of the paper.

1249
01:01:17,380 --> 01:01:22,720
This one I think you'll
like, because if we go here,

1250
01:01:22,720 --> 01:01:25,130
this is what she was describing.

1251
01:01:25,130 --> 01:01:29,570
So now, let me propose how else
we might describe this situation.

1252
01:01:29,570 --> 01:01:34,070
>> Back in the day, one of the most
more common ways to learn programming

1253
01:01:34,070 --> 01:01:38,900
was to write code, writes
lines of instructions,

1254
01:01:38,900 --> 01:01:42,640
that controlled a little
turtle on the screen.

1255
01:01:42,640 --> 01:01:45,660
Logo and other variants of this
was the name of the language.

1256
01:01:45,660 --> 01:01:47,550
And the turtle lived in a world.

1257
01:01:47,550 --> 01:01:49,970
>> So suppose this rectangular
space is his world.

1258
01:01:49,970 --> 01:01:53,340
And you would start by assuming-- I
don't really know how to draw turtle,

1259
01:01:53,340 --> 01:01:54,740
so let's do it like this.

1260
01:01:54,740 --> 01:01:57,340
And then he's got a shell
and then maybe some feet.

1261
01:01:57,340 --> 01:01:59,840
So you might have this little
character on the screen.

1262
01:01:59,840 --> 01:02:02,270
>> And the object of this
programming language

1263
01:02:02,270 --> 01:02:06,070
was to compel the turtle
to go up, down, left, right

1264
01:02:06,070 --> 01:02:08,420
and to put his pen down
or pick his pen up,

1265
01:02:08,420 --> 01:02:12,720
so he could actually draw on the screen
in this very flat rectangular world.

1266
01:02:12,720 --> 01:02:16,850
So where I thought you might be going,
and where you should consider diving

1267
01:02:16,850 --> 01:02:19,520
down to mentally when describing
instructions more generally,

1268
01:02:19,520 --> 01:02:21,720
I would claim, is put your
pen down in the middle--

1269
01:02:21,720 --> 01:02:23,100
and we'll get rid of the
turtle, because I can't really

1270
01:02:23,100 --> 01:02:24,680
keep drawing him very well.

1271
01:02:24,680 --> 01:02:27,170
>> And now, how else could
I say draw a cube?

1272
01:02:27,170 --> 01:02:32,830
Well, we could say something like draw
a diagonal line northeast, for instance,

1273
01:02:32,830 --> 01:02:35,182
or at a 45-degree angle upward.

1274
01:02:35,182 --> 01:02:36,640
And that might have gotten me here.

1275
01:02:36,640 --> 01:02:38,380
And I'm pretty far from a cube.

1276
01:02:38,380 --> 01:02:42,430
But now, I could say something
like turn 90 degrees to the left

1277
01:02:42,430 --> 01:02:47,370
and draw a line of
equal length northwest.

1278
01:02:47,370 --> 01:02:49,470
And I could continue
with similar directions.

1279
01:02:49,470 --> 01:02:50,720
And it's not going to be easy.

1280
01:02:50,720 --> 01:02:53,345
And frankly, we probably would
have been here for five minutes.

1281
01:02:53,345 --> 01:02:59,600
But maybe we would have gotten to
something that, at the end of the day,

1282
01:02:59,600 --> 01:03:04,280
ends up being a cube, but we
dived inside of that abstraction

1283
01:03:04,280 --> 01:03:06,370
to do it at such a low
level that you can't really

1284
01:03:06,370 --> 01:03:09,795
see what you're doing until the whole
thing is actually there on the page.

1285
01:03:09,795 --> 01:03:12,670
And so this is a general principle,
again, of programming-- this idea

1286
01:03:12,670 --> 01:03:13,320
of abstraction.

1287
01:03:13,320 --> 01:03:15,920
It's so wonderfully
powerful, because again,

1288
01:03:15,920 --> 01:03:19,281
she just said, draw a cube, which all of
us pretty much would grok very quickly.

1289
01:03:19,281 --> 01:03:21,030
We would just understand,
OK, draw a cube.

1290
01:03:21,030 --> 01:03:24,030
We might not know the orientation,
so we could be a little more precise,

1291
01:03:24,030 --> 01:03:26,297
but we can generally picture
or know what a cube is.

1292
01:03:26,297 --> 01:03:28,130
And that's useful,
because if every time you

1293
01:03:28,130 --> 01:03:31,540
sat down as a programmer at
your keyboard to write code,

1294
01:03:31,540 --> 01:03:33,912
if you had to think at such
a low level, none of us

1295
01:03:33,912 --> 01:03:35,120
would ever get anything done.

1296
01:03:35,120 --> 01:03:38,259
And certainly, none of us would
enjoy the process of writing code.

1297
01:03:38,259 --> 01:03:41,550
It would be like writing in 0's and 1's,
which frankly wasn't all that long ago

1298
01:03:41,550 --> 01:03:43,680
humans were writing code in 0's and 1's.

1299
01:03:43,680 --> 01:03:46,960
And we very quickly came up with
these higher level languages--

1300
01:03:46,960 --> 01:03:49,410
C++ and Java and others.

1301
01:03:49,410 --> 01:03:52,500
>> So let's try this once more just to
flip the tables, so that all of us

1302
01:03:52,500 --> 01:03:55,450
have the chance to think
in rather the same way.

1303
01:03:55,450 --> 01:03:59,230
Could we get one more volunteer this
time to come up to the board and draw,

1304
01:03:59,230 --> 01:04:01,480
not recite?

1305
01:04:01,480 --> 01:04:02,070
Yeah, OK.

1306
01:04:02,070 --> 01:04:04,820
Ben, come on up.

1307
01:04:04,820 --> 01:04:08,510
And, Ben, in this case, once you
face the board, don't look left,

1308
01:04:08,510 --> 01:04:09,370
don't look right.

1309
01:04:09,370 --> 01:04:12,367
Only do what your
colleagues here tell you.

1310
01:04:12,367 --> 01:04:14,950
And for everyone else in the
room, you now are the programmer.

1311
01:04:14,950 --> 01:04:16,020
He's the computer.

1312
01:04:16,020 --> 01:04:21,395
And the picture I've chosen here
in advance is this one here.

1313
01:04:21,395 --> 01:04:24,490

1314
01:04:24,490 --> 01:04:27,660
They're just-- they're thinking
of a funny joke is all.

1315
01:04:27,660 --> 01:04:31,510
>> So would does someone like to
volunteer the first instruction

1316
01:04:31,510 --> 01:04:35,470
or statement that should
command Ben's pen?

1317
01:04:35,470 --> 01:04:40,850
And we'll do this collectively, maybe
one instruction from each person.

1318
01:04:40,850 --> 01:04:41,440
I'm sorry?

1319
01:04:41,440 --> 01:04:42,440
>> AUDIENCE: Draw a circle.

1320
01:04:42,440 --> 01:04:45,866
DAVID MALAN: Draw a circle
is the first thing I heard.

1321
01:04:45,866 --> 01:04:47,100
>> AUDIENCE: Up top.

1322
01:04:47,100 --> 01:04:48,140
>> DAVID MALAN: Up top.

1323
01:04:48,140 --> 01:04:52,504
OK, we can let you delete, undo.

1324
01:04:52,504 --> 01:04:53,420
And now, someone else.

1325
01:04:53,420 --> 01:04:55,994
Dan, would you be comfy
offering the next instruction?

1326
01:04:55,994 --> 01:05:02,070
>> AUDIENCE: Sure, draw the center
of the bottom of the circle,

1327
01:05:02,070 --> 01:05:07,121
with a small-- a little
small space from that,

1328
01:05:07,121 --> 01:05:15,420
draw a straight line down to three
quarters of the way down the board

1329
01:05:15,420 --> 01:05:17,845
a slight angle to your left.

1330
01:05:17,845 --> 01:05:21,250

1331
01:05:21,250 --> 01:05:22,620
>> DAVID MALAN: Good.

1332
01:05:22,620 --> 01:05:24,086
>> AUDIENCE: Slight angle.

1333
01:05:24,086 --> 01:05:32,807
>> DAVID MALAN: Undo, Control-Z. OK.

1334
01:05:32,807 --> 01:05:34,890
Andrew, you want to offer
up the next instruction?

1335
01:05:34,890 --> 01:05:35,515
>> AUDIENCE: Sure.

1336
01:05:35,515 --> 01:05:43,250
From the bottom of that line,
a further slight angle--

1337
01:05:43,250 --> 01:05:49,024
whoops-- maybe about a third
of the length [INAUDIBLE],

1338
01:05:49,024 --> 01:05:52,928
slight angle downward and like a
third of the length of [INAUDIBLE].

1339
01:05:52,928 --> 01:05:57,550

1340
01:05:57,550 --> 01:06:00,578
So yeah, from that point,
draw a line a third

1341
01:06:00,578 --> 01:06:04,150
of the length of the previous
line further to the left.

1342
01:06:04,150 --> 01:06:08,416

1343
01:06:08,416 --> 01:06:10,040
>> DAVID MALAN: That OK?

1344
01:06:10,040 --> 01:06:12,330
Straight line, that's OK?

1345
01:06:12,330 --> 01:06:14,900
OK, Olivier, you want
to offer up the next?

1346
01:06:14,900 --> 01:06:28,564
>> AUDIENCE: [INAUDIBLE] from the
bottom of the circle, [INAUDIBLE].

1347
01:06:28,564 --> 01:06:32,000

1348
01:06:32,000 --> 01:06:45,126
Draw on the right hand side
of [INAUDIBLE] centimeters.

1349
01:06:45,126 --> 01:06:46,560
>> [LAUGHTER]

1350
01:06:46,560 --> 01:06:49,872
>> DAVID MALAN: I think you're going to
have to convert that's inches here.

1351
01:06:49,872 --> 01:06:50,764
>> AUDIENCE: Stop.

1352
01:06:50,764 --> 01:06:52,186
>> [LAUGHTER]

1353
01:06:52,186 --> 01:06:54,570
>> DAVID MALAN: OK.

1354
01:06:54,570 --> 01:06:56,660
[? Ara, ?] you want
to offer up the next?

1355
01:06:56,660 --> 01:07:00,653

1356
01:07:00,653 --> 01:07:15,443
>> AUDIENCE: Draw a [INAUDIBLE]
the upper [INAUDIBLE] the same.

1357
01:07:15,443 --> 01:07:28,829
[INAUDIBLE] circle, draw to the
[INAUDIBLE] and draw [INAUDIBLE].

1358
01:07:28,829 --> 01:07:33,799

1359
01:07:33,799 --> 01:07:36,730
>> DAVID MALAN: OK, no more undo.

1360
01:07:36,730 --> 01:07:38,390
Let's do one or two more instructions.

1361
01:07:38,390 --> 01:07:40,825
Chris, you want to offer one?

1362
01:07:40,825 --> 01:07:46,182
>> AUDIENCE: At the bottom
of the circle, [INAUDIBLE]

1363
01:07:46,182 --> 01:07:51,528
draw an equal line slopping
downward to the left [INAUDIBLE].

1364
01:07:51,528 --> 01:07:59,304

1365
01:07:59,304 --> 01:08:00,590
>> DAVID MALAN: OK.

1366
01:08:00,590 --> 01:08:01,170
Andrew?

1367
01:08:01,170 --> 01:08:02,472
We did-- Karim?

1368
01:08:02,472 --> 01:08:06,891

1369
01:08:06,891 --> 01:08:13,765
>> AUDIENCE: Starting from the right line,
the end of the left line, the bottom,

1370
01:08:13,765 --> 01:08:21,012
you're going to go right about
the same length as that line

1371
01:08:21,012 --> 01:08:27,680
you're on, drawing to
the right [INAUDIBLE].

1372
01:08:27,680 --> 01:08:33,572

1373
01:08:33,572 --> 01:08:37,991
[INAUDIBLE] degrees, so [INAUDIBLE]
degrees on the right side.

1374
01:08:37,991 --> 01:08:41,919

1375
01:08:41,919 --> 01:08:43,500
>> DAVID MALAN: All right.

1376
01:08:43,500 --> 01:08:44,029
Let's pause.

1377
01:08:44,029 --> 01:08:44,950
Don't turn around yet.

1378
01:08:44,950 --> 01:08:46,783
Let's pause, and let's
try one other attempt

1379
01:08:46,783 --> 01:08:48,850
before we reveal to Ben
what he's been drawing.

1380
01:08:48,850 --> 01:08:51,189
Can you shuffle Ben to
the right-- or actually,

1381
01:08:51,189 --> 01:08:54,080
no, let's just give you
another board, even better.

1382
01:08:54,080 --> 01:08:57,640
So would someone now like
to take more of the approach

1383
01:08:57,640 --> 01:09:02,149
that Victoria took earlier on, where
we speak in a higher level abstraction

1384
01:09:02,149 --> 01:09:05,149
and in just a sentence
or two describe to Ben

1385
01:09:05,149 --> 01:09:07,229
what to draw without
getting into the weeds,

1386
01:09:07,229 --> 01:09:10,670
so to speak, at this a lower level?

1387
01:09:10,670 --> 01:09:11,206
Victoria.

1388
01:09:11,206 --> 01:09:11,706
[LAUGHTER]

1389
01:09:11,706 --> 01:09:14,249
AUDIENCE: Draw a figure
of the walking man.

1390
01:09:14,249 --> 01:09:18,866
And his legs and arms
have to be the right side.

1391
01:09:18,866 --> 01:09:20,505
>> DAVID MALAN: OK, that's all you get.

1392
01:09:20,505 --> 01:09:27,210

1393
01:09:27,210 --> 01:09:27,710
All right.

1394
01:09:27,710 --> 01:09:31,609
Why don't we reveal to Ben what he did.

1395
01:09:31,609 --> 01:09:32,890
So a round of applause.

1396
01:09:32,890 --> 01:09:35,700
That was the hardest perhaps.

1397
01:09:35,700 --> 01:09:37,931
>> So even though we're talking
in fairly silly terms

1398
01:09:37,931 --> 01:09:39,680
about just drawing
pictures, hopefully you

1399
01:09:39,680 --> 01:09:44,226
can really appreciate the degree of
expressiveness that might be necessary

1400
01:09:44,226 --> 01:09:45,850
in order to tell a computer what to do.

1401
01:09:45,850 --> 01:09:50,370
And in fact, the fact that Ben
was able to draw this so quickly

1402
01:09:50,370 --> 01:09:54,227
is sort of testament to using a
language, maybe a higher level

1403
01:09:54,227 --> 01:09:57,060
version of English, that allows him
to just use words, or hear words

1404
01:09:57,060 --> 01:09:59,990
from Victoria, that allow him
these abstractions-- just draw

1405
01:09:59,990 --> 01:10:03,020
a figure walking to the
right-- that sort of has

1406
01:10:03,020 --> 01:10:07,100
some semantic meaning to it that isn't
nearly as obvious when you're just

1407
01:10:07,100 --> 01:10:10,310
saying, put your pen down, draw
to the right, draw to the left.

1408
01:10:10,310 --> 01:10:12,420
>> And so this, too, is very
common in programming.

1409
01:10:12,420 --> 01:10:15,253
This would be said to be like a
very low level language, programming

1410
01:10:15,253 --> 01:10:16,730
in 0's and 1's if you will.

1411
01:10:16,730 --> 01:10:19,320
And this would be a higher level
language programming in Java,

1412
01:10:19,320 --> 01:10:20,278
or something like that.

1413
01:10:20,278 --> 01:10:22,050
A bit of an
oversimplification, but that's

1414
01:10:22,050 --> 01:10:24,310
the sort of like emotional
feeling that you feel when

1415
01:10:24,310 --> 01:10:26,630
using one kind of thing or another.

1416
01:10:26,630 --> 01:10:32,650
A bit of frustration here by the need
for such precision, but the opportunity

1417
01:10:32,650 --> 01:10:34,930
to be a little looser with
the interpretation here.

1418
01:10:34,930 --> 01:10:38,060
But of course, bugs
can arise as a result.

1419
01:10:38,060 --> 01:10:40,500
>> If you'd like at home-- we
won't do this one in class--

1420
01:10:40,500 --> 01:10:41,900
but if you'd like to
bring this one home,

1421
01:10:41,900 --> 01:10:43,387
I thought we would dive into this.

1422
01:10:43,387 --> 01:10:45,970
So if you'd like to play this
game with your significant other

1423
01:10:45,970 --> 01:10:49,180
or kids or the like, you
might enjoy that as well.

1424
01:10:49,180 --> 01:10:54,460
>> So let's go ahead and look at one last
thing here for computational thinking.

1425
01:10:54,460 --> 01:10:57,010
And that brings us to John
Oliver, not for the clip

1426
01:10:57,010 --> 01:11:00,070
you might have seen last night,
but to a somewhat recent issue.

1427
01:11:00,070 --> 01:11:03,310
A few months back, Volkswagen
took quite a bit of flak

1428
01:11:03,310 --> 01:11:05,651
for what reason, if you know?

1429
01:11:05,651 --> 01:11:07,025
What did they get in trouble for?

1430
01:11:07,025 --> 01:11:10,270

1431
01:11:10,270 --> 01:11:14,030
>> Yeah, so emissions-- they
were trying to beat emissions

1432
01:11:14,030 --> 01:11:19,100
tests by essentially having their
cars pollute the environment less

1433
01:11:19,100 --> 01:11:23,620
when their cars were being tested
and pollute the environment more

1434
01:11:23,620 --> 01:11:25,547
when the cars were not being tested.

1435
01:11:25,547 --> 01:11:28,630
And what's increasingly interesting
in the world, as you may have inferred

1436
01:11:28,630 --> 01:11:34,072
from discussions of like-- what is
it-- CarPlay, Apple's software for cars

1437
01:11:34,072 --> 01:11:35,780
and the fact that many
of us increasingly

1438
01:11:35,780 --> 01:11:38,390
have touch screens in our cars,
there's a frightening amount

1439
01:11:38,390 --> 01:11:41,250
of software in people's
cars today, which

1440
01:11:41,250 --> 01:11:45,650
frankly opens a whole can of worms when
it comes to security and physical risk.

1441
01:11:45,650 --> 01:11:48,070
But for today, let's
focus on just what's

1442
01:11:48,070 --> 01:11:52,170
involved in writing software
that might have gamed the system.

1443
01:11:52,170 --> 01:11:54,510
>> For the definition of the
problem, for those unfamiliar,

1444
01:11:54,510 --> 01:11:55,740
let's take a look at John Oliver.

1445
01:11:55,740 --> 01:11:58,115
And for those familiar with
the problem, let's look at it

1446
01:11:58,115 --> 01:12:00,480
in a fun lens via John Oliver as well.

1447
01:12:00,480 --> 01:12:05,810
So let me hit play on this, I
think, three-minute introduction.

1448
01:12:05,810 --> 01:12:07,074
Damn it.

1449
01:12:07,074 --> 01:12:07,740
[VIDEO PLAYBACK]

1450
01:12:07,740 --> 01:12:08,170
-Cars--

1451
01:12:08,170 --> 01:12:09,919
DAVID MALAN: Obviously,
on YouTube, it's--

1452
01:12:09,919 --> 01:12:12,500
- --the smartest characters in
the Fast and Furious movies.

1453
01:12:12,500 --> 01:12:16,080
This week, German automaker
Volkswagen found itself

1454
01:12:16,080 --> 01:12:19,430
in the middle of a scandal of
potentially criminal proportions.

1455
01:12:19,430 --> 01:12:23,020
>> -Volkswagen is bracing for billions
in fines, possible criminal charges

1456
01:12:23,020 --> 01:12:25,530
for its executives, as
the company apologizes

1457
01:12:25,530 --> 01:12:28,790
for rigging 11 million cars to
help it beat emissions tests.

1458
01:12:28,790 --> 01:12:32,110
>> -Certain diesel models were designed
with sophisticated software that

1459
01:12:32,110 --> 01:12:35,410
used information, including the position
of the steering wheel and vehicle

1460
01:12:35,410 --> 01:12:38,820
speed, to determine the car was
undergoing emissions testing.

1461
01:12:38,820 --> 01:12:42,620
Under that circumstance, the engine
would reduce toxic emissions.

1462
01:12:42,620 --> 01:12:46,040
But the car was rigged to bypass
that when it was being driven.

1463
01:12:46,040 --> 01:12:51,370
Emissions increased 10 to 40
times above acceptable EPA levels.

1464
01:12:51,370 --> 01:12:55,920
>> -Wow, 10 to 40 times
greater than the EPA allows.

1465
01:12:55,920 --> 01:12:59,570
That is the worst thing
Volkswagen has ever done,

1466
01:12:59,570 --> 01:13:04,200
is something you might say if
you'd never heard of World War II.

1467
01:13:04,200 --> 01:13:09,710
But maybe the surest sign of how
much trouble Volkswagen is in,

1468
01:13:09,710 --> 01:13:12,730
is that people at the very
top have stepped down.

1469
01:13:12,730 --> 01:13:16,320
The CEO resigned on Wednesday after
scrambling to do damage control,

1470
01:13:16,320 --> 01:13:20,380
saying he was endlessly sorry, which
sounded great until it turned out

1471
01:13:20,380 --> 01:13:22,920
he was only 10% sorry
but had rigged his mouth

1472
01:13:22,920 --> 01:13:25,600
to artificially inflate his sorriness.

1473
01:13:25,600 --> 01:13:29,700
And meanwhile, Volkswagen's US
chief had an apology of his own.

1474
01:13:29,700 --> 01:13:33,580
>> -Let's be clear about this,
our company was dishonest.

1475
01:13:33,580 --> 01:13:37,140
And in my German words, we
have totally screwed up.

1476
01:13:37,140 --> 01:13:41,360
>> -Yeah, but totally screwed
up are not German works.

1477
01:13:41,360 --> 01:13:43,750
And the German language
has many beautiful phrases

1478
01:13:43,750 --> 01:13:50,070
to describe situations just like this,
such as [GERMAN], which means roughly,

1479
01:13:50,070 --> 01:13:52,870
the sadness that comes
from business related lies,

1480
01:13:52,870 --> 01:13:59,060
or [GERMAN], which translates
as shaming ones father involving

1481
01:13:59,060 --> 01:14:00,352
clouds of gasoline.

1482
01:14:00,352 --> 01:14:02,060
It's a beautiful language.

1483
01:14:02,060 --> 01:14:04,660
It just sails off the tongue.

1484
01:14:04,660 --> 01:14:07,920
And by the way, while that man's
apology may have sounded sincere,

1485
01:14:07,920 --> 01:14:12,260
it's worth noting he was speaking at
an official launch party for the 2016

1486
01:14:12,260 --> 01:14:17,310
Volkswagen Passat, meaning that shortly
after saying sorry, he said this.

1487
01:14:17,310 --> 01:14:18,850
>> -Thank you very much for coming.

1488
01:14:18,850 --> 01:14:19,630
Enjoy the evening.

1489
01:14:19,630 --> 01:14:21,300
Up next is Lenny Kravitz.

1490
01:14:21,300 --> 01:14:24,640
>> [MUSIC PLAYING]

1491
01:14:24,640 --> 01:14:28,230
>> -OK, OK, ending your
apology with up next

1492
01:14:28,230 --> 01:14:31,940
Lenny Kravitz does not
scream sober contrition.

1493
01:14:31,940 --> 01:14:35,830
It screams, we asked Bon
Jovi, and he said no.

1494
01:14:35,830 --> 01:14:38,600
Volkswagen's brand has
been badly damaged.

1495
01:14:38,600 --> 01:14:42,466
And frankly, their new ad
campaign is not exactly helping.

1496
01:14:42,466 --> 01:14:47,289
>> --[GERMAN], we at Volkswagen would like
to apologize for deceiving you with

1497
01:14:47,289 --> 01:14:47,930
our vehicles.

1498
01:14:47,930 --> 01:14:48,513
>> [END PLAYBACK]

1499
01:14:48,513 --> 01:14:54,090
DAVID MALAN: So this was a
roundabout way of-- sorry--

1500
01:14:54,090 --> 01:14:58,730
this was a roundabout way of
introducing a fundamental problem

1501
01:14:58,730 --> 01:15:02,810
in software, which is that you
need to detect certain conditions.

1502
01:15:02,810 --> 01:15:07,680
And so the question at hand here
is, how does a car potentially,

1503
01:15:07,680 --> 01:15:09,870
as implemented in software
by these programmers,

1504
01:15:09,870 --> 01:15:11,850
detect that it's actually being tested?

1505
01:15:11,850 --> 01:15:14,150
So to be super clear,
what they were doing

1506
01:15:14,150 --> 01:15:17,940
was, in environments where
the programmers figured

1507
01:15:17,940 --> 01:15:20,460
the car was being
tested, they somehow made

1508
01:15:20,460 --> 01:15:24,840
the car emit less emissions, fewer
emissions, so less toxic fumes

1509
01:15:24,840 --> 01:15:25,470
and such.

1510
01:15:25,470 --> 01:15:27,261
But when it's normally
driving on the road,

1511
01:15:27,261 --> 01:15:30,350
it would just emit as much
pollution as it wanted.

1512
01:15:30,350 --> 01:15:33,870
>> So how could we write the
pseudocode for this algorithm?

1513
01:15:33,870 --> 01:15:37,820
How could we write the pseudocode
for the software running in the car?

1514
01:15:37,820 --> 01:15:43,390
I mean, in a nutshell, it boils
down to something like this.

1515
01:15:43,390 --> 01:15:48,000
if being tested, emit less.

1516
01:15:48,000 --> 01:15:50,750
else emits more.

1517
01:15:50,750 --> 01:15:52,630
But that's a little
too high level, right?

1518
01:15:52,630 --> 01:15:58,580
>> Let's try to dive in as to what this
abstraction of being tested means.

1519
01:15:58,580 --> 01:16:06,340
In other words, even if you know nothing
about cars, what sort of questions

1520
01:16:06,340 --> 01:16:13,440
might you ask in order to determine if
you're being tested, if you're the car?

1521
01:16:13,440 --> 01:16:19,638
What characteristics might be
present if a car is being tested?

1522
01:16:19,638 --> 01:16:21,026
>> AUDIENCE: Testing equipment.

1523
01:16:21,026 --> 01:16:22,420
>> DAVID MALAN: Testing equipment.

1524
01:16:22,420 --> 01:16:26,060
So if testing equipment
nearby, then emit less.

1525
01:16:26,060 --> 01:16:28,669
So I could imagine implementing
that with some kind of cameras

1526
01:16:28,669 --> 01:16:29,960
or detecting what's around you.

1527
01:16:29,960 --> 01:16:32,870
And let me propose, that
just feels too complicated

1528
01:16:32,870 --> 01:16:37,914
to actually have additional
hardware just for that purpose.

1529
01:16:37,914 --> 01:16:44,830
>> AUDIENCE: If you're in
park, if your hood is open.

1530
01:16:44,830 --> 01:16:47,320
>> DAVID MALAN: In park or
hood open, so that's good.

1531
01:16:47,320 --> 01:16:47,420
>> AUDIENCE: And car running.

1532
01:16:47,420 --> 01:16:50,480
>> DAVID MALAN: So that's a little
more concrete-- and car running.

1533
01:16:50,480 --> 01:16:55,690
So this would be the conjunction of a
few different conditions, if you will.

1534
01:16:55,690 --> 01:16:59,227
So if the car is in park, and even
though this is a very mechanical thing

1535
01:16:59,227 --> 01:17:01,060
typically, I could
imagine writing software,

1536
01:17:01,060 --> 01:17:03,476
especially because there's
often a light there these days,

1537
01:17:03,476 --> 01:17:07,400
I could imagine there being
software that can query the shifter

1538
01:17:07,400 --> 01:17:10,634
or what not, are you in park, are
you in drive, are you in reverse.

1539
01:17:10,634 --> 01:17:12,550
And I can get back an
answer that's either yes

1540
01:17:12,550 --> 01:17:14,400
or no to those kinds of questions.

1541
01:17:14,400 --> 01:17:17,630
>> And so I could also probably answer
a question like, is the hood open.

1542
01:17:17,630 --> 01:17:21,860
Maybe, there's some kind of sensor
that either gives me back a 1 or 0,

1543
01:17:21,860 --> 01:17:23,720
true or false, the hood is open.

1544
01:17:23,720 --> 01:17:28,180
And then car running, I could detect
that somehow via what mechanism?

1545
01:17:28,180 --> 01:17:30,430
Like, the car is running, I
could detect that it's on,

1546
01:17:30,430 --> 01:17:32,127
could I detect somehow
that the car is moving?

1547
01:17:32,127 --> 01:17:32,881
>> AUDIENCE: RPMs.

1548
01:17:32,881 --> 01:17:35,190
>> DAVID MALAN: Yeah, so there's
always that needle that

1549
01:17:35,190 --> 01:17:38,034
tells you how many rotations per
minute the wheels are experiencing.

1550
01:17:38,034 --> 01:17:39,200
And so I could look at that.

1551
01:17:39,200 --> 01:17:43,090
And if it's not 0, that probably
means the car is moving.

1552
01:17:43,090 --> 01:17:45,400
But we have to be a
little careful there,

1553
01:17:45,400 --> 01:17:49,780
because-- let's simplify this--
if we just said, if car running,

1554
01:17:49,780 --> 01:17:53,070
we don't want to just emit less,
we want if the car is running

1555
01:17:53,070 --> 01:17:54,310
and it's being tested.

1556
01:17:54,310 --> 01:17:56,320
>> So there are a few other
ingredients that folks

1557
01:17:56,320 --> 01:18:00,550
have hypothesized the software is doing,
because absent the actual source code,

1558
01:18:00,550 --> 01:18:05,130
you can only sort of infer from the
physical effects of the car as to what

1559
01:18:05,130 --> 01:18:08,280
might be going on underneath
the hood in software.

1560
01:18:08,280 --> 01:18:17,090
So if car running and maybe,
say, rear wheels not moving,

1561
01:18:17,090 --> 01:18:19,420
might this be indicative
of some kind of test?

1562
01:18:19,420 --> 01:18:22,830
What am I hinting at here?

1563
01:18:22,830 --> 01:18:24,830
Yeah, maybe, it's on one
of those roller things,

1564
01:18:24,830 --> 01:18:28,340
where like the wheels are turning
in the front or in the back,

1565
01:18:28,340 --> 01:18:32,570
depending on whether it's front wheel or
rear wheel drive, so half of the wheels

1566
01:18:32,570 --> 01:18:34,420
are moving, but the
other two aren't, which

1567
01:18:34,420 --> 01:18:36,320
is a weird situation in the real world.

1568
01:18:36,320 --> 01:18:38,110
If you're driving on the
road, that shouldn't happen.

1569
01:18:38,110 --> 01:18:40,568
But if you're in a warehouse
on some kind of roller system,

1570
01:18:40,568 --> 01:18:41,630
that might indeed happen.

1571
01:18:41,630 --> 01:18:46,980
>> I think folks also proposed that maybe,
if the car is running and steering

1572
01:18:46,980 --> 01:18:51,300
wheel not moving, that
too might be a signal,

1573
01:18:51,300 --> 01:18:54,090
because that's reasonable for
like a straightaway on a road.

1574
01:18:54,090 --> 01:18:57,960
But even then, the human is probably
moving it a little bit or certainly

1575
01:18:57,960 --> 01:18:59,100
over a few seconds.

1576
01:18:59,100 --> 01:19:01,030
Or the course of a
minute, odds are it's not

1577
01:19:01,030 --> 01:19:03,510
going to be fixated in
exactly the same position.

1578
01:19:03,510 --> 01:19:05,440
>> So in other words, we
can take substraction,

1579
01:19:05,440 --> 01:19:08,200
are you being tested, and
break down that functionality

1580
01:19:08,200 --> 01:19:10,420
into these component ingredients.

1581
01:19:10,420 --> 01:19:13,440
And that's truly what Volkswagen's
engineers somehow did.

1582
01:19:13,440 --> 01:19:17,070
They wrote software consciously to
detect if the car is being tested,

1583
01:19:17,070 --> 01:19:20,440
therefore emit less, else
emit in the usual way.

1584
01:19:20,440 --> 01:19:22,690
>> And the problem here, too,
is that software is not

1585
01:19:22,690 --> 01:19:26,080
something you can really see unless
you have the so-called source code.

1586
01:19:26,080 --> 01:19:29,060
So there's two different types of
code-- at least two different types

1587
01:19:29,060 --> 01:19:30,130
of code in the world.

1588
01:19:30,130 --> 01:19:33,150
There's something called source
code, which is not unlike what

1589
01:19:33,150 --> 01:19:37,240
we've been writing, source code.

1590
01:19:37,240 --> 01:19:40,099
>> This is source code written in
a language called pseudocode,

1591
01:19:40,099 --> 01:19:41,640
which is just something English-like.

1592
01:19:41,640 --> 01:19:43,140
There's no formal definition of it.

1593
01:19:43,140 --> 01:19:46,770
But C, and Java, C++, those
are all formal languages that,

1594
01:19:46,770 --> 01:19:50,610
when you write in them, what you have
is a text file containing source code.

1595
01:19:50,610 --> 01:19:54,850
>> But there is also something in
the world called machine code.

1596
01:19:54,850 --> 01:20:00,579
And machine code, unfortunately,
is just 0's and 1's.

1597
01:20:00,579 --> 01:20:02,870
So machine code is what
machines understand, of course.

1598
01:20:02,870 --> 01:20:04,470
Source code is what humans understand.

1599
01:20:04,470 --> 01:20:08,390
>> And generally, but not
always, there is a program

1600
01:20:08,390 --> 01:20:14,090
that a programmer uses that takes source
code and turns it into machine code.

1601
01:20:14,090 --> 01:20:17,400
And that program is
generally called a compiler.

1602
01:20:17,400 --> 01:20:19,820
So your input is source code,
your output is machine code,

1603
01:20:19,820 --> 01:20:22,890
and the compiler is a piece of
software that does that process.

1604
01:20:22,890 --> 01:20:26,260
So this actually maps nicely to
our inputs, algorithms, outputs.

1605
01:20:26,260 --> 01:20:30,400
>> But this is a very specific incarnation
of that, which is to say that,

1606
01:20:30,400 --> 01:20:34,200
even if you own one of Volkswagen's
cars that is guilty of this,

1607
01:20:34,200 --> 01:20:38,390
it's not like you can just open the
hood or open the user's manual or look

1608
01:20:38,390 --> 01:20:42,690
at the source code, because by the time
it reaches your car in your driveway,

1609
01:20:42,690 --> 01:20:45,580
it's already been
converted into 0's and 1's.

1610
01:20:45,580 --> 01:20:51,310
And it's very hard, not impossible,
but very hard to glean much of anything

1611
01:20:51,310 --> 01:20:53,710
from just looking at the
underlying 0's and 1's.

1612
01:20:53,710 --> 01:20:57,150
So you can figure it out, ultimately, if
you understand how a machine operates--

1613
01:20:57,150 --> 01:20:59,870
Intel inside-- if you understand
the Intel architecture,

1614
01:20:59,870 --> 01:21:01,440
but it's very time consuming.

1615
01:21:01,440 --> 01:21:05,010
And even there, you might
not be able to see everything

1616
01:21:05,010 --> 01:21:08,220
that the code can actually do.

1617
01:21:08,220 --> 01:21:12,521
>> Any questions about this or this
kind of process more generally?

1618
01:21:12,521 --> 01:21:15,134

1619
01:21:15,134 --> 01:21:18,300
And actually, we can tie this discussion
to yesterday's discussion of Apple.

1620
01:21:18,300 --> 01:21:22,500
This, too, is why the FBI can't just
go and look in the suspect's phone

1621
01:21:22,500 --> 01:21:26,820
and find the lines of code, for
instance, that enable the passcode

1622
01:21:26,820 --> 01:21:28,940
or enable that 80-millisecond delay.

1623
01:21:28,940 --> 01:21:31,630
Because by the time it's
on the fellow's iPhone,

1624
01:21:31,630 --> 01:21:34,975
it's already been
converted to 0's and 1's.

1625
01:21:34,975 --> 01:21:38,015

1626
01:21:38,015 --> 01:21:40,820
>> Well, let's pause here for our
look at computational thinking.

1627
01:21:40,820 --> 01:21:42,320
Why don't we take a 15 minute break.

1628
01:21:42,320 --> 01:21:44,130
And when we return, we'll
take a look at programming

1629
01:21:44,130 --> 01:21:46,550
itself and start to map some
of these high level concepts

1630
01:21:46,550 --> 01:21:49,780
to an actual, if playful,
programming language.

1631
01:21:49,780 --> 01:21:51,089