1
00:00:00,000 --> 00:00:00,090

2
00:00:00,090 --> 00:00:01,800
The following
content is provided

3
00:00:01,800 --> 00:00:04,040
under a Creative
Commons license.

4
00:00:04,040 --> 00:00:06,880
Your support will help MIT
OpenCourseWare continue

5
00:00:06,880 --> 00:00:10,740
to offer high quality
educational resources for free.

6
00:00:10,740 --> 00:00:13,360
To make a donation or
view additional materials

7
00:00:13,360 --> 00:00:17,260
from hundreds of MIT courses,
visit MIT OpenCourseWare

8
00:00:17,260 --> 00:00:17,885
at ocw.mit.edu.

9
00:00:17,885 --> 00:00:21,959

10
00:00:21,959 --> 00:00:23,750
PROFESSOR: I want to
talk about two things,

11
00:00:23,750 --> 00:00:26,139
maybe, depending on
the level of interest.

12
00:00:26,139 --> 00:00:28,430
We can talk a little bit
about PSET five and the things

13
00:00:28,430 --> 00:00:32,830
that I think are weird in
the coding part of PSET five.

14
00:00:32,830 --> 00:00:35,802
By the way, how many
people started PSET five?

15
00:00:35,802 --> 00:00:37,367
[LAUGHTER]

16
00:00:37,367 --> 00:00:38,450
AUDIENCE: I downloaded it.

17
00:00:38,450 --> 00:00:41,380
PROFESSOR: Hmm, maybe we are not
going to talk about P set five.

18
00:00:41,380 --> 00:00:43,576
You guys need to start early!

19
00:00:43,576 --> 00:00:44,829
AUDIENCE: I did.

20
00:00:44,829 --> 00:00:45,620
PROFESSOR: You did.

21
00:00:45,620 --> 00:00:46,460
Yeah.

22
00:00:46,460 --> 00:00:49,020
I guess I can't punish
you for everyone else.

23
00:00:49,020 --> 00:00:52,110
So P set five, and I
can talk about graphs.

24
00:00:52,110 --> 00:00:54,560
I can talk about whatever
didn't make sense in class

25
00:00:54,560 --> 00:00:59,230
and I can talk about
background stuff for graphs.

26
00:00:59,230 --> 00:01:00,400
So how do people feel?

27
00:01:00,400 --> 00:01:04,520
Who wants talk about the
PSET that we haven't read?

28
00:01:04,520 --> 00:01:06,870
[LAUGHTER]

29
00:01:06,870 --> 00:01:09,852
Who wants to talk about graphs?

30
00:01:09,852 --> 00:01:12,816
AUDIENCE: It's really easy.

31
00:01:12,816 --> 00:01:14,300
We took 604 two.

32
00:01:14,300 --> 00:01:19,430
PROFESSOR: Yeah, if you took
604 two, nothing here is new.

33
00:01:19,430 --> 00:01:21,720
I mean nothing in the
recitation is new.

34
00:01:21,720 --> 00:01:25,820
We're going to take it to new
heights of graph knowledge,

35
00:01:25,820 --> 00:01:28,460
and you'll be able to
do many more cool things

36
00:01:28,460 --> 00:01:30,690
that you're able to do before.

37
00:01:30,690 --> 00:01:31,230
OK, so PSET.

38
00:01:31,230 --> 00:01:33,930

39
00:01:33,930 --> 00:01:37,870
For people who
started early, what

40
00:01:37,870 --> 00:01:41,390
was the gist of the
coding assignments?

41
00:01:41,390 --> 00:01:44,410
AUDIENCE: So we have
to speed up something.

42
00:01:44,410 --> 00:01:50,559
When I ran the tests-- do I
say what I got as results?

43
00:01:50,559 --> 00:01:53,100
PROFESSOR: The time isn't on
the PSET so you can say what you

44
00:01:53,100 --> 00:01:53,626
got as --

45
00:01:53,626 --> 00:01:53,972
AUDIENCE: Pardon?

46
00:01:53,972 --> 00:01:55,513
PROFESSOR: The time
isn't on the PSET

47
00:01:55,513 --> 00:01:57,240
so you can say what
you got as a time.

48
00:01:57,240 --> 00:02:01,807
AUDIENCE: OK, the slowest
was like add for me.

49
00:02:01,807 --> 00:02:04,140
PROFESSOR: You should look
to see add is a valid answer.

50
00:02:04,140 --> 00:02:06,579
Look at the questions and
see if add is a valid answer.

51
00:02:06,579 --> 00:02:07,120
AUDIENCE: OK.

52
00:02:07,120 --> 00:02:10,430

53
00:02:10,430 --> 00:02:12,920
PROFESSOR: It's not like what
was lowest function, right?

54
00:02:12,920 --> 00:02:14,800
There's more text there.

55
00:02:14,800 --> 00:02:16,330
You should read the
rest of the text

56
00:02:16,330 --> 00:02:18,565
and see if add makes
sense as a valid answer.

57
00:02:18,565 --> 00:02:19,190
AUDIENCE: Sure.

58
00:02:19,190 --> 00:02:21,297
OK.

59
00:02:21,297 --> 00:02:23,130
PROFESSOR: What you're
doing-- big picture--

60
00:02:23,130 --> 00:02:27,170
is you have some processor,
that's not a real processor,

61
00:02:27,170 --> 00:02:31,830
and it can do arithmetic
with bytes and 16-bit words.

62
00:02:31,830 --> 00:02:34,130
And we give you the
basic operations

63
00:02:34,130 --> 00:02:36,890
and then they give you a library
for large number arithmetic

64
00:02:36,890 --> 00:02:38,280
because, guess what?

65
00:02:38,280 --> 00:02:41,160
16 bytes addition, subtraction?

66
00:02:41,160 --> 00:02:46,090
Not going to cut it for
science applications

67
00:02:46,090 --> 00:02:50,280
are for cryptography,
what we want to play with.

68
00:02:50,280 --> 00:02:54,276
What are the basic operations
that that processor can do?

69
00:02:54,276 --> 00:02:55,650
Front of the PSET,
so even if you

70
00:02:55,650 --> 00:02:56,840
didn't get to the
coding assignment

71
00:02:56,840 --> 00:02:57,756
you can still tell me.

72
00:02:57,756 --> 00:03:01,656
AUDIENCE: Divide,
and zeros, I think.

73
00:03:01,656 --> 00:03:03,920
Zeros.

74
00:03:03,920 --> 00:03:07,980
PROFESSOR: Plus, minus,
multiply, divide, and mod.

75
00:03:07,980 --> 00:03:10,710
Let's start to these.

76
00:03:10,710 --> 00:03:12,690
So you have two primitives
in that processor.

77
00:03:12,690 --> 00:03:20,100
You have have bytes, which
are basically 8-bit digits.

78
00:03:20,100 --> 00:03:22,490
There's 200.

79
00:03:22,490 --> 00:03:27,640
The range is 0 to 256.

80
00:03:27,640 --> 00:03:35,080
And the word is 16-bit,
from 0 to the 16 minus 1.

81
00:03:35,080 --> 00:03:38,677
If you care to know
this is 6, 5, 5, 3, 5.

82
00:03:38,677 --> 00:03:41,660

83
00:03:41,660 --> 00:03:44,710
So, if you take two bytes
and add them together what do

84
00:03:44,710 --> 00:03:47,490
you get?

85
00:03:47,490 --> 00:03:48,454
AUDIENCE: [INAUDIBLE].

86
00:03:48,454 --> 00:03:53,274

87
00:03:53,274 --> 00:03:54,720
PROFESSOR: Not right.

88
00:03:54,720 --> 00:03:56,820
It's a trick question.

89
00:03:56,820 --> 00:03:57,550
You get word.

90
00:03:57,550 --> 00:04:00,450

91
00:04:00,450 --> 00:04:04,260
The processor cannot do
simple math on bytes.

92
00:04:04,260 --> 00:04:08,750
It converts them up to words and
all the math happens on words.

93
00:04:08,750 --> 00:04:15,650
Now if you guess two words,
and add them up together

94
00:04:15,650 --> 00:04:17,917
what do you get?

95
00:04:17,917 --> 00:04:19,652
AUDIENCE: Two words?

96
00:04:19,652 --> 00:04:21,360
PROFESSOR: You do if
we're not that nice.

97
00:04:21,360 --> 00:04:24,870

98
00:04:24,870 --> 00:04:28,310
AUDIENCE: A world in carry bit?

99
00:04:28,310 --> 00:04:31,270
PROFESSOR: Sorry,
you just get word.

100
00:04:31,270 --> 00:04:33,010
At least nobody said a byte.

101
00:04:33,010 --> 00:04:36,580
I was like, please don't say
byte, please don't say byte.

102
00:04:36,580 --> 00:04:37,922
You said carry bit.

103
00:04:37,922 --> 00:04:39,380
Why do we care
about the carry bit?

104
00:04:39,380 --> 00:04:41,380
What is the problem if
you do addition this way?

105
00:04:41,380 --> 00:04:43,080
AUDIENCE: If you're
going too high.

106
00:04:43,080 --> 00:04:47,975
If the highest bit is
one on both of them.

107
00:04:47,975 --> 00:04:49,845
Then it's like
overflow, kind of.

108
00:04:49,845 --> 00:04:50,470
PROFESSOR: Yep.

109
00:04:50,470 --> 00:04:55,690
Suppose we're trying to add
2 to the 16 minus 1 plus 2

110
00:04:55,690 --> 00:04:57,960
to the 16 minus 1.

111
00:04:57,960 --> 00:05:00,000
By the way, does anyone
remember hex notation?

112
00:05:00,000 --> 00:05:02,180
Hexadecimal?

113
00:05:02,180 --> 00:05:03,920
OK, people who started
the PSET remember.

114
00:05:03,920 --> 00:05:06,340
That's good.

115
00:05:06,340 --> 00:05:11,110
It will be easy to write
things hex for the PSET.

116
00:05:11,110 --> 00:05:17,346
If you try to add these numbers
you're going to get 1, F, F, F,

117
00:05:17,346 --> 00:05:21,200
E. You can use the
math here to see

118
00:05:21,200 --> 00:05:23,540
that this is more
than the words.

119
00:05:23,540 --> 00:05:27,409
So you would like to know that
this thing overflows, right?

120
00:05:27,409 --> 00:05:28,700
You like to know that there is.

121
00:05:28,700 --> 00:05:30,230
Well we don't give you that.

122
00:05:30,230 --> 00:05:33,580

123
00:05:33,580 --> 00:05:35,860
All you get to this.

124
00:05:35,860 --> 00:05:41,885
So addition happens,
modulo 2 to the 16.

125
00:05:41,885 --> 00:05:44,510
If you want to be able to detect
overflow what they have to do?

126
00:05:44,510 --> 00:05:47,450

127
00:05:47,450 --> 00:05:51,170
AUDIENCE: Just tests those bits.

128
00:05:51,170 --> 00:05:53,790
PROFESSOR: That one
way of doing it.

129
00:05:53,790 --> 00:05:57,770
It would take quite a
few instructions, though.

130
00:05:57,770 --> 00:05:59,780
If you want to do
overflow detection,

131
00:05:59,780 --> 00:06:06,190
the easiest way I think of
doing it this to use this form.

132
00:06:06,190 --> 00:06:07,780
So suppose you have two bytes.

133
00:06:07,780 --> 00:06:10,520

134
00:06:10,520 --> 00:06:12,450
This is the maximum
value in a byte, right?

135
00:06:12,450 --> 00:06:15,480
255, 2 to the 8 minus 1.

136
00:06:15,480 --> 00:06:18,520
If you have 2 bytes and
you add them all together

137
00:06:18,520 --> 00:06:23,270
you're going to
get 1, F, E. Right?

138
00:06:23,270 --> 00:06:26,805
It's just like the case here,
except you have a fewer F's.

139
00:06:26,805 --> 00:06:32,890

140
00:06:32,890 --> 00:06:34,000
Where is the carry here?

141
00:06:34,000 --> 00:06:36,560

142
00:06:36,560 --> 00:06:38,260
AUDIENCE: Could be the 1, right?

143
00:06:38,260 --> 00:06:40,170
PROFESSOR: Yep.

144
00:06:40,170 --> 00:06:45,380
This guy here is the carry
and this guy's the low result.

145
00:06:45,380 --> 00:06:46,970
Does anyone know how
these are called?

146
00:06:46,970 --> 00:06:49,415
If you have a word and
you have two bytes, what

147
00:06:49,415 --> 00:06:51,916
is the first byte, what
is the second bytes?

148
00:06:51,916 --> 00:06:54,470
AUDIENCE: [INAUDIBLE].

149
00:06:54,470 --> 00:06:57,311
PROFESSOR: Most
significant byte,

150
00:06:57,311 --> 00:07:00,315
M, S, B, and least
significant byte,

151
00:07:00,315 --> 00:07:03,860
L, S, B. If you want to
figure out your carries,

152
00:07:03,860 --> 00:07:06,140
then you should do
your math this way.

153
00:07:06,140 --> 00:07:09,040
You're going to have
byte 1 plus byte 2.

154
00:07:09,040 --> 00:07:10,500
Add them together.

155
00:07:10,500 --> 00:07:13,825
And then you call L, S,
B to get the byte result.

156
00:07:13,825 --> 00:07:16,500

157
00:07:16,500 --> 00:07:21,660
And then you call M,
S, B to get the carry.

158
00:07:21,660 --> 00:07:26,120

159
00:07:26,120 --> 00:07:28,500
This is addition.

160
00:07:28,500 --> 00:07:31,250
Everyone with me so far?

161
00:07:31,250 --> 00:07:36,115
By the way, are these
numbers signed or unsigned?

162
00:07:36,115 --> 00:07:37,085
AUDIENCE: [INAUDIBLE].

163
00:07:37,085 --> 00:07:40,817

164
00:07:40,817 --> 00:07:42,400
PROFESSOR: No negative
numbers, right?

165
00:07:42,400 --> 00:07:43,820
So no support for
negative numbers.

166
00:07:43,820 --> 00:07:45,300
Everything is going
to be positive.

167
00:07:45,300 --> 00:07:46,320
And we're going to
build everything

168
00:07:46,320 --> 00:07:48,300
we need off of positive
numbers because they're

169
00:07:48,300 --> 00:07:50,070
easier to deal with.

170
00:07:50,070 --> 00:07:57,770
What if I have two words
and I subtract them?

171
00:07:57,770 --> 00:07:59,850
What do I get?

172
00:07:59,850 --> 00:08:01,527
AUDIENCE: Word.

173
00:08:01,527 --> 00:08:02,110
PROFESSOR: OK.

174
00:08:02,110 --> 00:08:06,130

175
00:08:06,130 --> 00:08:11,840
What if I have 0 minus 1?

176
00:08:11,840 --> 00:08:13,845
What do I get?

177
00:08:13,845 --> 00:08:16,220
AUDIENCE: 0.

178
00:08:16,220 --> 00:08:19,175
PROFESSOR: Not quite.

179
00:08:19,175 --> 00:08:21,115
AUDIENCE: If you're
not using signs?

180
00:08:21,115 --> 00:08:24,469
Do you get O, 1?

181
00:08:24,469 --> 00:08:25,385
PROFESSOR: O, 1's, OK.

182
00:08:25,385 --> 00:08:26,556
AUDIENCE: Ya.

183
00:08:26,556 --> 00:08:27,780
Wait--

184
00:08:27,780 --> 00:08:33,822
PROFESSOR: So, O 1's
would be this, F, F, F, F.

185
00:08:33,822 --> 00:08:38,452
AUDIENCE: That's assuming
if you signed then.

186
00:08:38,452 --> 00:08:40,880
It will overflow.

187
00:08:40,880 --> 00:08:42,340
That's a really big number then.

188
00:08:42,340 --> 00:08:45,145
PROFESSOR: So fancy
CS, 2's complement.

189
00:08:45,145 --> 00:08:49,980

190
00:08:49,980 --> 00:08:54,245
For people who think in
math mode, what is this?

191
00:08:54,245 --> 00:08:54,995
AUDIENCE: I think.

192
00:08:54,995 --> 00:08:57,700

193
00:08:57,700 --> 00:09:02,730
PROFESSOR: It's minus
1 mod 2 to the 16.

194
00:09:02,730 --> 00:09:05,790
Remember, when we were doing
modular arithmetic before,

195
00:09:05,790 --> 00:09:09,150
to figure out a number's
multiplicative inverse?

196
00:09:09,150 --> 00:09:12,197
And when we were
doing rolling hashes?

197
00:09:12,197 --> 00:09:13,530
We didn't want negative numbers.

198
00:09:13,530 --> 00:09:14,446
We made them positive.

199
00:09:14,446 --> 00:09:17,310

200
00:09:17,310 --> 00:09:21,260
So minus 1 lot to the
16 is 2 to the 16.

201
00:09:21,260 --> 00:09:23,860
Minus 1, and comes
out to this value.

202
00:09:23,860 --> 00:09:26,517

203
00:09:26,517 --> 00:09:28,100
So you get minus 1,
it's just that you

204
00:09:28,100 --> 00:09:29,155
have to know your basis.

205
00:09:29,155 --> 00:09:34,170

206
00:09:34,170 --> 00:09:35,980
So we got the addition
and subtraction.

207
00:09:35,980 --> 00:09:38,114
Let's talk about multiplication.

208
00:09:38,114 --> 00:09:39,530
What do you do for
multiplication?

209
00:09:39,530 --> 00:09:42,390
What can you multiply?

210
00:09:42,390 --> 00:09:43,820
Two bytes, very good.

211
00:09:43,820 --> 00:09:44,445
Just two bytes.

212
00:09:44,445 --> 00:09:49,150

213
00:09:49,150 --> 00:09:52,290
What do you get?

214
00:09:52,290 --> 00:09:52,820
A word.

215
00:09:52,820 --> 00:09:55,190
Thank you.

216
00:09:55,190 --> 00:09:57,109
You multiply two
bytes, you get a word.

217
00:09:57,109 --> 00:09:58,150
What if there's overflow?

218
00:09:58,150 --> 00:10:09,570

219
00:10:09,570 --> 00:10:10,987
It's a trick question.

220
00:10:10,987 --> 00:10:12,420
AUDIENCE: There's no overflow.

221
00:10:12,420 --> 00:10:13,880
PROFESSOR: There is no overflow.

222
00:10:13,880 --> 00:10:18,500
So two bytes, 2 to the
eighth minus 1 times 2

223
00:10:18,500 --> 00:10:22,300
to the eighth minus 1,
is 2 to the 16 minus 2

224
00:10:22,300 --> 00:10:25,230
to the 8th minus 2
to the eighth plus 1.

225
00:10:25,230 --> 00:10:27,740

226
00:10:27,740 --> 00:10:31,250
You can say this safely without
doing the arithmetic, right?

227
00:10:31,250 --> 00:10:33,910

228
00:10:33,910 --> 00:10:36,470
This is how much you can
hold, in other words.

229
00:10:36,470 --> 00:10:40,835
This is how much you
can holding in a byte.

230
00:10:40,835 --> 00:10:42,230
AUDIENCE: Why do you minus 1?

231
00:10:42,230 --> 00:10:43,260
PROFESSOR: Ya, minus 1.

232
00:10:43,260 --> 00:10:45,770
There's a minus 1 here,
and there's a minus 1 here,

233
00:10:45,770 --> 00:10:48,520
but I can't find it
here, so roughly this.

234
00:10:48,520 --> 00:10:49,996
But there is an overflow.

235
00:10:49,996 --> 00:10:52,229
AUDIENCE: But where did
you get the minus 1 from?

236
00:10:52,229 --> 00:10:53,770
PROFESSOR: Where do
you get the-- so,

237
00:10:53,770 --> 00:10:56,730
this is how much you
can hold in a byte.

238
00:10:56,730 --> 00:10:58,740
Byte has 8 bits, right?

239
00:10:58,740 --> 00:11:03,896
From 0 0 to F F. This is
2 to the eighth minus 1.

240
00:11:03,896 --> 00:11:05,120
AUDIENCE: OK.

241
00:11:05,120 --> 00:11:06,500
PROFESSOR: OK, so
multiplication?

242
00:11:06,500 --> 00:11:07,400
There is an overflow.

243
00:11:07,400 --> 00:11:08,691
I don't have to deal with that.

244
00:11:08,691 --> 00:11:10,820
You guys have to figure
out how to deal with it.

245
00:11:10,820 --> 00:11:11,880
How about division?

246
00:11:11,880 --> 00:11:12,740
What can you divide?

247
00:11:12,740 --> 00:11:15,488

248
00:11:15,488 --> 00:11:16,870
AUDIENCE: Some words?

249
00:11:16,870 --> 00:11:18,478
PROFESSOR: Almost.

250
00:11:18,478 --> 00:11:19,790
AUDIENCE: Words like--

251
00:11:19,790 --> 00:11:25,060
PROFESSOR: A word
divided by a byte.

252
00:11:25,060 --> 00:11:28,430
What do you get out of it?

253
00:11:28,430 --> 00:11:30,830
AUDIENCE: Words?

254
00:11:30,830 --> 00:11:32,210
PROFESSOR: That would be nice.

255
00:11:32,210 --> 00:11:33,426
Nope.

256
00:11:33,426 --> 00:11:37,110
Sorry, you get a byte.

257
00:11:37,110 --> 00:11:39,470
And if you do module,
you also get a byte.

258
00:11:39,470 --> 00:11:43,730

259
00:11:43,730 --> 00:11:45,490
What if there's overflow
in the division?

260
00:11:45,490 --> 00:11:46,031
What happens?

261
00:11:46,031 --> 00:11:48,670

262
00:11:48,670 --> 00:11:51,174
What would you expect to happen?

263
00:11:51,174 --> 00:11:55,158
AUDIENCE: We don't have any
best flowing point numbers,

264
00:11:55,158 --> 00:12:00,150
so, we shouldn't
get overflow, right?

265
00:12:00,150 --> 00:12:05,810
PROFESSOR: How about 2 to
the 16 minus 1 divided by 1?

266
00:12:05,810 --> 00:12:09,210

267
00:12:09,210 --> 00:12:10,120
So what do get?

268
00:12:10,120 --> 00:12:10,995
AUDIENCE: Same thing?

269
00:12:10,995 --> 00:12:12,536
PROFESSOR: Will this
fit in the byte?

270
00:12:12,536 --> 00:12:13,183
AUDIENCE: Yes?

271
00:12:13,183 --> 00:12:13,683
No.

272
00:12:13,683 --> 00:12:14,545
[LAUGHTER]

273
00:12:14,545 --> 00:12:15,808
No.

274
00:12:15,808 --> 00:12:18,907
Well, that time I
don't get a word.

275
00:12:18,907 --> 00:12:20,240
PROFESSOR: You don't get a word.

276
00:12:20,240 --> 00:12:22,830
I promise you get a byte.

277
00:12:22,830 --> 00:12:26,295
What will that byte be?

278
00:12:26,295 --> 00:12:29,676
AUDIENCE: It's going
to be modulo something.

279
00:12:29,676 --> 00:12:30,642
Most significant--

280
00:12:30,642 --> 00:12:34,030

281
00:12:34,030 --> 00:12:37,690
PROFESSOR: That's
reasonable, right?

282
00:12:37,690 --> 00:12:40,000
Modulo to 56 because
that's what it can carry.

283
00:12:40,000 --> 00:12:42,850

284
00:12:42,850 --> 00:12:44,545
What about modulo?

285
00:12:44,545 --> 00:12:46,170
What happens there
if you get overflow?

286
00:12:46,170 --> 00:12:54,962

287
00:12:54,962 --> 00:12:57,397
AUDIENCE: The same thing.

288
00:12:57,397 --> 00:13:01,293
It's just going to loop, right?

289
00:13:01,293 --> 00:13:04,116
0?

290
00:13:04,116 --> 00:13:05,490
PROFESSOR: So if
you do a modulo,

291
00:13:05,490 --> 00:13:08,870
this is going to be,
at most, 255 right?

292
00:13:08,870 --> 00:13:12,340
If you do modulo
255, the remainder

293
00:13:12,340 --> 00:13:15,640
is going to be
between 0 and 254.

294
00:13:15,640 --> 00:13:19,450
Will that ever overflow byte?

295
00:13:19,450 --> 00:13:19,997
No overflow.

296
00:13:19,997 --> 00:13:21,080
No need to worry about it.

297
00:13:21,080 --> 00:13:26,170

298
00:13:26,170 --> 00:13:27,830
Word addition can overflow.

299
00:13:27,830 --> 00:13:29,730
Subtraction can overflow.

300
00:13:29,730 --> 00:13:31,230
Multiplication doesn't overflow.

301
00:13:31,230 --> 00:13:32,980
Division overflows,
modulo doesn't.

302
00:13:32,980 --> 00:13:36,228

303
00:13:36,228 --> 00:13:40,910
AUDIENCE: What do you mean, like
will it see the space confined?

304
00:13:40,910 --> 00:13:41,795
PROFESSOR: Yes.

305
00:13:41,795 --> 00:13:43,190
It sees the space of the result.

306
00:13:43,190 --> 00:13:44,680
Because here, if you're
adding two words,

307
00:13:44,680 --> 00:13:46,305
the result exceeds
the space of a word.

308
00:13:46,305 --> 00:13:49,152
Which is what you get.

309
00:13:49,152 --> 00:13:54,460
AUDIENCE: Is it just in all
cases it's just [INAUDIBLE].

310
00:13:54,460 --> 00:13:56,450
PROFESSOR: Exactly.

311
00:13:56,450 --> 00:13:59,520
So the reason you have to
deal with this weird system

312
00:13:59,520 --> 00:14:04,510
is this is, pretty much, how
Intel does their arithmetic.

313
00:14:04,510 --> 00:14:07,770
If you look at old school,
16-bit Intel processors,

314
00:14:07,770 --> 00:14:10,600
you have registers and you
have exactly these operations.

315
00:14:10,600 --> 00:14:14,250
For newer processors, there are
32 bits, but then it's just,

316
00:14:14,250 --> 00:14:17,645
you write more F's on the board
and you get the same thing.

317
00:14:17,645 --> 00:14:20,930
AUDIENCE: Is it most significant
bit, or most significant byte?

318
00:14:20,930 --> 00:14:24,440
PROFESSOR: Most
significant byte.

319
00:14:24,440 --> 00:14:27,020
On a real processor,
you have registers

320
00:14:27,020 --> 00:14:28,520
that are the size
of a word and then

321
00:14:28,520 --> 00:14:30,470
you can pull out the
bytes in constant time.

322
00:14:30,470 --> 00:14:33,750

323
00:14:33,750 --> 00:14:34,910
What constant do we have?

324
00:14:34,910 --> 00:14:37,380
These are the operations.

325
00:14:37,380 --> 00:14:38,470
What constants do we have?

326
00:14:38,470 --> 00:14:43,690

327
00:14:43,690 --> 00:14:47,800
Only two constants, 0 and 1.

328
00:14:47,800 --> 00:14:51,262

329
00:14:51,262 --> 00:14:52,970
What if you want to
get something bigger?

330
00:14:52,970 --> 00:14:54,060
What if you want to get 2?

331
00:14:54,060 --> 00:14:56,800
How do you get 2?

332
00:14:56,800 --> 00:14:57,770
AUDIENCE: Two 1's?

333
00:14:57,770 --> 00:14:58,855
1 plus 1?

334
00:14:58,855 --> 00:14:59,480
PROFESSOR: Yep.

335
00:14:59,480 --> 00:15:02,930

336
00:15:02,930 --> 00:15:06,300
What if you want
to get this number?

337
00:15:06,300 --> 00:15:12,696

338
00:15:12,696 --> 00:15:14,664
AUDIENCE: Do that several times?

339
00:15:14,664 --> 00:15:16,474
[LAUGHTER]

340
00:15:16,474 --> 00:15:18,140
PROFESSOR: It's kind
of painful to type,

341
00:15:18,140 --> 00:15:21,020
even if you copy paste.

342
00:15:21,020 --> 00:15:24,310
There's a method on
Word called from-bytes.

343
00:15:24,310 --> 00:15:28,480

344
00:15:28,480 --> 00:15:32,670
And it takes an M,
S, B and an L, S, B

345
00:15:32,670 --> 00:15:34,300
and it gives you a word.

346
00:15:34,300 --> 00:15:35,350
So what would I give it?

347
00:15:35,350 --> 00:15:38,098

348
00:15:38,098 --> 00:15:40,390
AUDIENCE: [INAUDIBLE].

349
00:15:40,390 --> 00:15:42,725
PROFESSOR: Let's give it
a 1 and let's give it a 0.

350
00:15:42,725 --> 00:15:45,490

351
00:15:45,490 --> 00:15:52,100
So this will get 1,
0, 0 and then minus 1.

352
00:15:52,100 --> 00:15:58,855

353
00:15:58,855 --> 00:15:59,355
Yes?

354
00:15:59,355 --> 00:16:03,540

355
00:16:03,540 --> 00:16:05,659
OK.

356
00:16:05,659 --> 00:16:07,200
Intel is pretty nice
about constants,

357
00:16:07,200 --> 00:16:08,650
but some other
processors aren't.

358
00:16:08,650 --> 00:16:11,620
So I figured, why not
let's get you acquainted

359
00:16:11,620 --> 00:16:13,846
to these kind of tricks, to too.

360
00:16:13,846 --> 00:16:17,400
Let's make the PSETS
more interesting.

361
00:16:17,400 --> 00:16:19,650
All right, so any questions
on this fake processor

362
00:16:19,650 --> 00:16:22,041
that you have to code for?

363
00:16:22,041 --> 00:16:26,762
AUDIENCE: Can you explain
the last one again?

364
00:16:26,762 --> 00:16:27,734
PROFESSOR: Here?

365
00:16:27,734 --> 00:16:29,690
AUDIENCE: Yeah, Word from-bytes.

366
00:16:29,690 --> 00:16:32,310
PROFESSOR: So in Word
from-bytes a word is 2 bytes.

367
00:16:32,310 --> 00:16:34,520
One next to the other.

368
00:16:34,520 --> 00:16:37,150
It gives you the first byte,
and gives you the second byte.

369
00:16:37,150 --> 00:16:40,340
In this case, the
first byte is 1.

370
00:16:40,340 --> 00:16:42,190
The second byte is 0.

371
00:16:42,190 --> 00:16:42,690
Right?

372
00:16:42,690 --> 00:16:43,650
So 2 bytes.

373
00:16:43,650 --> 00:16:45,150
A 1 and a 0.

374
00:16:45,150 --> 00:16:47,760
How do you write this in hex?

375
00:16:47,760 --> 00:16:49,530
1, 0, 0.

376
00:16:49,530 --> 00:16:52,060
One byte, second byte.

377
00:16:52,060 --> 00:16:58,500
And then I subtract
1 and I get this.

378
00:16:58,500 --> 00:17:03,890

379
00:17:03,890 --> 00:17:06,089
While I erase the
board, I want you guys

380
00:17:06,089 --> 00:17:08,040
to think of graph
questions because this

381
00:17:08,040 --> 00:17:10,550
is the other topic
we're looking at today.

382
00:17:10,550 --> 00:17:12,020
What was unclear
about the lecture?

383
00:17:12,020 --> 00:17:13,839
What is unclear about
graphs in general?

384
00:17:13,839 --> 00:17:15,790
Do guys remember the
handshaking lemma?

385
00:17:15,790 --> 00:17:16,560
What does it mean?

386
00:17:16,560 --> 00:17:17,810
How do you prove it?

387
00:17:17,810 --> 00:17:20,740
Things of that sort.

388
00:17:20,740 --> 00:17:23,287
What do you guys
want to cover today?

389
00:17:23,287 --> 00:17:25,924
AUDIENCE: Handshaking,
that's the thing where

390
00:17:25,924 --> 00:17:30,450
you have a bunch nodes
and they're all connected,

391
00:17:30,450 --> 00:17:36,008
like they're all in a closed
graph, that the number of edges

392
00:17:36,008 --> 00:17:40,270
is equal to twice the
number of vertices?

393
00:17:40,270 --> 00:17:41,866
PROFESSOR: OK.

394
00:17:41,866 --> 00:17:43,650
AUDIENCE: That's
all it is, right?

395
00:17:43,650 --> 00:17:44,305
PROFESSOR: The
number of vertices?

396
00:17:44,305 --> 00:17:44,880
No.

397
00:17:44,880 --> 00:17:46,296
AUDIENCE: The
number of handshakes

398
00:17:46,296 --> 00:17:49,900
that occurred are twice
the number of edges.

399
00:17:49,900 --> 00:17:53,410
You said the number
of vertices, wait--

400
00:17:53,410 --> 00:17:56,189
PROFESSOR: No, vertices and
edges are not related in here.

401
00:17:56,189 --> 00:17:57,980
AUDIENCE: Yeah, think
of a triangle, right?

402
00:17:57,980 --> 00:18:00,330
That's three edges,
three vertices.

403
00:18:00,330 --> 00:18:05,590
Which is like not two times,
which is what you said.

404
00:18:05,590 --> 00:18:08,301
It's the number of degrees
is twice the number of edges.

405
00:18:08,301 --> 00:18:10,090
That's what I was
thinking of then.

406
00:18:10,090 --> 00:18:12,620
PROFESSOR: All right, so
let's start with simple stuff.

407
00:18:12,620 --> 00:18:15,208
What's a graph?

408
00:18:15,208 --> 00:18:16,670
AUDIENCE: Nodes and edges?

409
00:18:16,670 --> 00:18:17,545
PROFESSOR: All right.

410
00:18:17,545 --> 00:18:18,900
Fancy word for nodes?

411
00:18:18,900 --> 00:18:19,609
AUDIENCE: Vertex.

412
00:18:19,609 --> 00:18:20,358
PROFESSOR: Vertex.

413
00:18:20,358 --> 00:18:21,230
Vertices and edges.

414
00:18:21,230 --> 00:18:22,430
How do I draw vertices?

415
00:18:22,430 --> 00:18:23,400
How do I draw edges?

416
00:18:23,400 --> 00:18:24,680
AUDIENCE: Circles and lines.

417
00:18:24,680 --> 00:18:26,516
PROFESSOR: Circles and lines.

418
00:18:26,516 --> 00:18:27,974
AUDIENCE: 0's and 1's.

419
00:18:27,974 --> 00:18:31,035
Possibly arrows.

420
00:18:31,035 --> 00:18:32,160
PROFESSOR: Possibly arrows.

421
00:18:32,160 --> 00:18:32,920
I like that.

422
00:18:32,920 --> 00:18:34,386
You want to get fancy.

423
00:18:34,386 --> 00:18:36,697
[LAUGHTER}

424
00:18:36,697 --> 00:18:38,530
PROFESSOR: When do I
draw an edge as a line?

425
00:18:38,530 --> 00:18:40,818
When do I draw it as an arrow?

426
00:18:40,818 --> 00:18:43,240
AUDIENCE: Directed under.

427
00:18:43,240 --> 00:18:44,532
PROFESSOR: Which one's which?

428
00:18:44,532 --> 00:18:46,008
AUDIENCE: Directed as an arrow.

429
00:18:46,008 --> 00:18:46,992
Character number.

430
00:18:46,992 --> 00:18:56,014

431
00:18:56,014 --> 00:18:56,680
PROFESSOR: Cool.

432
00:18:56,680 --> 00:18:58,455
Let's draw this graph here.

433
00:18:58,455 --> 00:19:05,130

434
00:19:05,130 --> 00:19:06,970
Yeah, looks like a
pretty boring graph.

435
00:19:06,970 --> 00:19:11,570

436
00:19:11,570 --> 00:19:14,442
Is this graph connected or not?

437
00:19:14,442 --> 00:19:16,960
AUDIENCE: Yes.

438
00:19:16,960 --> 00:19:19,903
PROFESSOR: What's
a connected graph?

439
00:19:19,903 --> 00:19:21,278
AUDIENCE: I think
that we can get

440
00:19:21,278 --> 00:19:23,880
to any other node
following some path.

441
00:19:23,880 --> 00:19:27,880
PROFESSOR: There's a path
from any to any other node.

442
00:19:27,880 --> 00:19:31,570
How do I make this
unconnected using

443
00:19:31,570 --> 00:19:32,830
the least amount of effort?

444
00:19:32,830 --> 00:19:36,290

445
00:19:36,290 --> 00:19:38,630
It's a bit of a trick question.

446
00:19:38,630 --> 00:19:39,732
Any guess is fine.

447
00:19:39,732 --> 00:19:41,340
AUDIENCE: What was
the question again?

448
00:19:41,340 --> 00:19:43,110
PROFESSOR: How do I
make this unconnected

449
00:19:43,110 --> 00:19:47,084
using the least amount
of effort on my behalf?

450
00:19:47,084 --> 00:19:48,994
AUDIENCE: Just add a node?

451
00:19:48,994 --> 00:19:50,410
PROFESSOR: I heard
you move pages.

452
00:19:50,410 --> 00:19:55,950
I don't like you racing
because I don't like the-- So

453
00:19:55,950 --> 00:20:00,170
I like that answer out
of the two I heard.

454
00:20:00,170 --> 00:20:02,560
Now it's not a connected graph.

455
00:20:02,560 --> 00:20:04,310
How many connected
component does it have?

456
00:20:04,310 --> 00:20:08,900

457
00:20:08,900 --> 00:20:09,630
Two and five.

458
00:20:09,630 --> 00:20:11,510
AUDIENCE: Or one
connected component,

459
00:20:11,510 --> 00:20:13,787
but there are two components?

460
00:20:13,787 --> 00:20:15,620
PROFESSOR: OK, what's
a connected component?

461
00:20:15,620 --> 00:20:23,340

462
00:20:23,340 --> 00:20:26,600
AUDIENCE: It's like in that part
of the graph the neck follows

463
00:20:26,600 --> 00:20:33,035
the prognito beacon and puts
them in two parts [INAUDIBLE]

464
00:20:33,035 --> 00:20:35,510
two connected components--

465
00:20:35,510 --> 00:20:37,020
PROFESSOR: So, a
connected component

466
00:20:37,020 --> 00:20:40,510
is a bunch of vertices such
that you can get from one vertex

467
00:20:40,510 --> 00:20:43,220
to all the other vertices.

468
00:20:43,220 --> 00:20:45,230
If the graph is
undirected, that's

469
00:20:45,230 --> 00:20:48,020
true for any vertex in the set.

470
00:20:48,020 --> 00:20:50,590
We also want the
sets to be maximal

471
00:20:50,590 --> 00:20:54,060
because, if we say this
is a connected component,

472
00:20:54,060 --> 00:20:55,824
it's not very useful.

473
00:20:55,824 --> 00:20:58,115
Noticing that this whole
thing is a connected component

474
00:20:58,115 --> 00:20:59,650
is useful.

475
00:20:59,650 --> 00:21:00,850
So this is one component.

476
00:21:00,850 --> 00:21:03,060
This is the other component.

477
00:21:03,060 --> 00:21:05,950
Make sense?

478
00:21:05,950 --> 00:21:08,310
So, we have the world.

479
00:21:08,310 --> 00:21:10,190
We have cities.

480
00:21:10,190 --> 00:21:12,610
You can bike from a city to
another city and that's it.

481
00:21:12,610 --> 00:21:15,140
No other a route
of transportation.

482
00:21:15,140 --> 00:21:16,390
How many connected components?

483
00:21:16,390 --> 00:21:19,856

484
00:21:19,856 --> 00:21:20,827
AUDIENCE: Seven?

485
00:21:20,827 --> 00:21:21,410
PROFESSOR: OK.

486
00:21:21,410 --> 00:21:24,300
Roughly seven.

487
00:21:24,300 --> 00:21:24,800
Why?

488
00:21:24,800 --> 00:21:28,150

489
00:21:28,150 --> 00:21:29,760
OK, so it only seven?

490
00:21:29,760 --> 00:21:30,967
AUDIENCE: Seven continents?

491
00:21:30,967 --> 00:21:31,550
PROFESSOR: OK.

492
00:21:31,550 --> 00:21:36,320

493
00:21:36,320 --> 00:21:37,360
Let's say roughly seven.

494
00:21:37,360 --> 00:21:38,470
So this is what I wanted.

495
00:21:38,470 --> 00:21:40,507
I wanted some thinking.

496
00:21:40,507 --> 00:21:42,840
If you try to get from a
continent to another continent,

497
00:21:42,840 --> 00:21:45,765
presumably you'd go
through some patch of sea.

498
00:21:45,765 --> 00:21:47,765
Otherwise, why are they
calling them continents?

499
00:21:47,765 --> 00:21:50,870

500
00:21:50,870 --> 00:21:53,010
Does anyone want to
give out another answer?

501
00:21:53,010 --> 00:21:54,510
I asked this in the
previous section

502
00:21:54,510 --> 00:21:57,270
and some people there give
me some very precise answers

503
00:21:57,270 --> 00:21:58,636
that are not continents.

504
00:21:58,636 --> 00:22:00,260
This is what I had
in mind, by the way.

505
00:22:00,260 --> 00:22:03,070

506
00:22:03,070 --> 00:22:06,950
As far as I'm concerned,
this is a good answer.

507
00:22:06,950 --> 00:22:10,090
Come on guys, world.

508
00:22:10,090 --> 00:22:18,770
Two things, islands and
Europe and Asia are connected,

509
00:22:18,770 --> 00:22:20,470
so you can go from
one to the other.

510
00:22:20,470 --> 00:22:21,500
They're weird.

511
00:22:21,500 --> 00:22:23,060
Why are they
separate continents?

512
00:22:23,060 --> 00:22:24,420
I have no idea.

513
00:22:24,420 --> 00:22:26,292
The geography people might--

514
00:22:26,292 --> 00:22:28,440
AUDIENCE: [INAUDIBLE].

515
00:22:28,440 --> 00:22:29,148
PROFESSOR: Sorry?

516
00:22:29,148 --> 00:22:31,530
AUDIENCE: You roll mountains?

517
00:22:31,530 --> 00:22:34,002
PROFESSOR: OK, so it would
be a pain bike through them,

518
00:22:34,002 --> 00:22:35,374
but presumably you can.

519
00:22:35,374 --> 00:22:37,665
If you have a robot that
doesn't get tired or something

520
00:22:37,665 --> 00:22:38,764
you can bike.

521
00:22:38,764 --> 00:22:41,229
AUDIENCE: It doesn't
mind falling off cliffs.

522
00:22:41,229 --> 00:22:43,270
PROFESSOR: The answer,
depending on my geography,

523
00:22:43,270 --> 00:22:46,190
we know is somewhere
between 7 and 10,000,

524
00:22:46,190 --> 00:22:48,330
or whatever the
number of islands is.

525
00:22:48,330 --> 00:22:51,480
There are a lot of tiny
island somewhere, right?

526
00:22:51,480 --> 00:22:54,570
Anyways, between seven
and a big number.

527
00:22:54,570 --> 00:22:57,500
These are connected
components in the world.

528
00:22:57,500 --> 00:22:58,920
What's the degree of A?

529
00:22:58,920 --> 00:23:01,920

530
00:23:01,920 --> 00:23:03,855
2.

531
00:23:03,855 --> 00:23:07,645
What's the degree of the D?

532
00:23:07,645 --> 00:23:10,130
AUDIENCE: [INAUDIBLE].

533
00:23:10,130 --> 00:23:11,250
PROFESSOR: Very good.

534
00:23:11,250 --> 00:23:11,980
Let's make this.

535
00:23:11,980 --> 00:23:15,860

536
00:23:15,860 --> 00:23:22,660
The degrees of F,
G, H are 2, 2, 2.

537
00:23:22,660 --> 00:23:27,690
The degree of C is 2.

538
00:23:27,690 --> 00:23:29,570
The degree of B is?

539
00:23:29,570 --> 00:23:30,500
AUDIENCE: --2.

540
00:23:30,500 --> 00:23:31,390
PROFESSOR: Thank you.

541
00:23:31,390 --> 00:23:32,970
And the degree of E is?

542
00:23:32,970 --> 00:23:33,470
AUDIENCE: 2.

543
00:23:33,470 --> 00:23:35,817

544
00:23:35,817 --> 00:23:38,150
PROFESSOR: If you add up all
these numbers together what

545
00:23:38,150 --> 00:23:38,720
you get?

546
00:23:38,720 --> 00:23:50,230

547
00:23:50,230 --> 00:23:52,180
18.

548
00:23:52,180 --> 00:23:54,040
I can't do math, so
I couldn't possibly

549
00:23:54,040 --> 00:23:56,310
have added all these
numbers together, right?

550
00:23:56,310 --> 00:23:57,340
I used something else.

551
00:23:57,340 --> 00:24:01,200

552
00:24:01,200 --> 00:24:04,900
How many edges do I
have in the graph?

553
00:24:04,900 --> 00:24:08,610
1, 2, 3, 4, 5, 6, 7, 8, 9.

554
00:24:08,610 --> 00:24:12,370

555
00:24:12,370 --> 00:24:14,998
Do you see your connection here?

556
00:24:14,998 --> 00:24:15,980
AUDIENCE: Yeah.

557
00:24:15,980 --> 00:24:17,830
PROFESSOR: This is
the handshaking lemma.

558
00:24:17,830 --> 00:24:21,210
That's all there is to it.

559
00:24:21,210 --> 00:24:23,660
So if you look at
the degrees of a node

560
00:24:23,660 --> 00:24:26,230
each edge adds one
to two degrees.

561
00:24:26,230 --> 00:24:28,750
For instance, this edge
adds one to C's degree

562
00:24:28,750 --> 00:24:32,844
and adds one to D's degree.

563
00:24:32,844 --> 00:24:34,760
If you're a math person
and you write this up,

564
00:24:34,760 --> 00:24:37,650
you have to write sums.

565
00:24:37,650 --> 00:24:41,580
You have big sums using
intimidating notation,

566
00:24:41,580 --> 00:24:42,930
so it's not as obvious.

567
00:24:42,930 --> 00:24:45,120
But this is really
all there is to it.

568
00:24:45,120 --> 00:24:49,329
Each edge contributes
one to two nodes degrees.

569
00:24:49,329 --> 00:24:50,870
If you add up all
the degrees, you're

570
00:24:50,870 --> 00:24:52,730
going to get to times
the number of edges.

571
00:24:52,730 --> 00:24:55,790

572
00:24:55,790 --> 00:24:58,750
So far so good?

573
00:24:58,750 --> 00:25:01,890
What if we have directed graphs?

574
00:25:01,890 --> 00:25:03,570
What if I had this?

575
00:25:03,570 --> 00:25:16,580

576
00:25:16,580 --> 00:25:24,560
A, B, C, D, E, F. What
is the degree of A?

577
00:25:24,560 --> 00:25:28,648

578
00:25:28,648 --> 00:25:30,755
AUDIENCE: 2?

579
00:25:30,755 --> 00:25:31,630
PROFESSOR: Not quite.

580
00:25:31,630 --> 00:25:32,480
Sorry, that was trick question.

581
00:25:32,480 --> 00:25:33,790
A doesn't have a degree.

582
00:25:33,790 --> 00:25:36,580

583
00:25:36,580 --> 00:25:39,090
If you have directed graphs,
you don't have degrees.

584
00:25:39,090 --> 00:25:41,690
You have in degrees
and out degrees.

585
00:25:41,690 --> 00:25:43,730
Now that I've said that
you have no idea, right?

586
00:25:43,730 --> 00:25:46,440
What's the out degree of A?

587
00:25:46,440 --> 00:25:48,690
AUDIENCE: [INAUDIBLE].

588
00:25:48,690 --> 00:25:54,300
PROFESSOR: Sometimes this is
known as the degree of edges.

589
00:25:54,300 --> 00:25:55,685
This is 2.

590
00:25:55,685 --> 00:25:57,330
What's the in degree of A?

591
00:25:57,330 --> 00:26:00,506

592
00:26:00,506 --> 00:26:01,478
AUDIENCE: [INAUDIBLE].

593
00:26:01,478 --> 00:26:04,120

594
00:26:04,120 --> 00:26:09,160
PROFESSOR: So A has two edges
going out, 0 edges going in.

595
00:26:09,160 --> 00:26:10,045
How about D?

596
00:26:10,045 --> 00:26:11,240
What's the out degree of D?

597
00:26:11,240 --> 00:26:14,621

598
00:26:14,621 --> 00:26:15,590
AUDIENCE: [INAUDIBLE].

599
00:26:15,590 --> 00:26:16,970
PROFESSOR: Come on guys.

600
00:26:16,970 --> 00:26:20,200
Don't scare me. (LAUGHS)
What's the in degree of D?

601
00:26:20,200 --> 00:26:21,630
AUDIENCE: 2?

602
00:26:21,630 --> 00:26:22,982
PROFESSOR: 2, very good.

603
00:26:22,982 --> 00:26:24,440
PROFESSOR: So what's
the equivalent

604
00:26:24,440 --> 00:26:27,100
of the handshaking lemma
on oriented graphs?

605
00:26:27,100 --> 00:26:29,920

606
00:26:29,920 --> 00:26:32,740
AUDIENCE: The sum of the
in degrees and out degrees?

607
00:26:32,740 --> 00:26:35,090
PROFESSOR: OK, what about them?

608
00:26:35,090 --> 00:26:39,110
AUDIENCE: They're equal to
twice the number of vertices?

609
00:26:39,110 --> 00:26:42,240
PROFESSOR: Not quite.

610
00:26:42,240 --> 00:26:43,990
They're equal to?

611
00:26:43,990 --> 00:26:45,460
You had 80 percent
of the answer.

612
00:26:45,460 --> 00:26:51,808
AUDIENCE: Oh. (LAUGHS)

613
00:26:51,808 --> 00:26:57,600
PROFESSOR: So the sum of the in
degrees and the sum of the out

614
00:26:57,600 --> 00:26:58,944
degrees.

615
00:26:58,944 --> 00:26:59,985
AUDIENCE: So add them up?

616
00:26:59,985 --> 00:27:03,814

617
00:27:03,814 --> 00:27:05,230
PROFESSOR: If you
add them up, you

618
00:27:05,230 --> 00:27:07,530
will get two times
the number of edges.

619
00:27:07,530 --> 00:27:09,470
That is correct.

620
00:27:09,470 --> 00:27:13,140
But, I want something more--

621
00:27:13,140 --> 00:27:14,480
AUDIENCE: They equal each other?

622
00:27:14,480 --> 00:27:15,105
PROFESSOR: Yep.

623
00:27:15,105 --> 00:27:17,750

624
00:27:17,750 --> 00:27:20,660
This is cooler, right?

625
00:27:20,660 --> 00:27:22,740
So why is that?

626
00:27:22,740 --> 00:27:24,300
Does anyone see why
that's the case?

627
00:27:24,300 --> 00:27:26,940

628
00:27:26,940 --> 00:27:33,970
Each edge-- Come on, guys.

629
00:27:33,970 --> 00:27:35,200
So what does each edge do?

630
00:27:35,200 --> 00:27:37,770
AUDIENCE: [INAUDIBLE].

631
00:27:37,770 --> 00:27:39,520
PROFESSOR: So if I
look at this edge here,

632
00:27:39,520 --> 00:27:44,840
this edge is going to
contribute 1 to B's out degree,

633
00:27:44,840 --> 00:27:48,260
and 1 to D's in degree.

634
00:27:48,260 --> 00:27:50,680
Each edge contributes
1 to an out degree

635
00:27:50,680 --> 00:27:52,760
and 1 to an in degree.

636
00:27:52,760 --> 00:27:56,040
That means that total
sum of out degrees

637
00:27:56,040 --> 00:27:59,050
equals the total
sum of in degrees.

638
00:27:59,050 --> 00:28:02,560
Both of them are E and
they combined to E. Sorry,

639
00:28:02,560 --> 00:28:05,784
eyed I don't know why that
didn't click to me right away.

640
00:28:05,784 --> 00:28:08,181
AUDIENCE: OK.

641
00:28:08,181 --> 00:28:09,680
PROFESSOR: The
intuition behind this

642
00:28:09,680 --> 00:28:12,682
is, that for every node,
if you take an edge

643
00:28:12,682 --> 00:28:14,140
you're going to
get somewhere else.

644
00:28:14,140 --> 00:28:16,980

645
00:28:16,980 --> 00:28:19,129
If the sum of the out
degrees was bigger,

646
00:28:19,129 --> 00:28:20,670
then you have a
black hole somewhere.

647
00:28:20,670 --> 00:28:22,490
If you go on an edge
you don't come back.

648
00:28:22,490 --> 00:28:23,660
Same four in degrees.

649
00:28:23,660 --> 00:28:28,090

650
00:28:28,090 --> 00:28:29,880
OK, how do we represent graphs?

651
00:28:29,880 --> 00:28:34,820

652
00:28:34,820 --> 00:28:37,125
AUDIENCE: I think we just did.

653
00:28:37,125 --> 00:28:38,750
PROFESSOR: Sure, if
you're drawing them

654
00:28:38,750 --> 00:28:40,666
on the board that's what
you do, but if you're

655
00:28:40,666 --> 00:28:42,220
in Python what do you do?

656
00:28:42,220 --> 00:28:43,946
AUDIENCE: You can
have a link list.

657
00:28:43,946 --> 00:28:44,763
PROFESSOR: Of?

658
00:28:44,763 --> 00:28:50,920
AUDIENCE: Of each node having
its neighbors linked with.

659
00:28:50,920 --> 00:28:53,050
PROFESSOR: OK, so I
have one big link list?

660
00:28:53,050 --> 00:28:55,960
Or how does this work?

661
00:28:55,960 --> 00:28:58,520
AUDIENCE: You'd have a
starting point of some sort.

662
00:28:58,520 --> 00:29:00,250
A starting node.

663
00:29:00,250 --> 00:29:04,514
Then from that node you can have
its neighbors connected to it.

664
00:29:04,514 --> 00:29:07,720

665
00:29:07,720 --> 00:29:09,304
So it was a link list , I guess.

666
00:29:09,304 --> 00:29:10,470
PROFESSOR: I wasn't precise.

667
00:29:10,470 --> 00:29:12,200
That is not trivial to build.

668
00:29:12,200 --> 00:29:15,700
By the time we build that we're
done with this recitation.

669
00:29:15,700 --> 00:29:20,294
What do you get is the
vertices and the edges.

670
00:29:20,294 --> 00:29:22,960
We want an easier representation
that just looks at the vertices

671
00:29:22,960 --> 00:29:24,420
and build something,
then looks at the edges

672
00:29:24,420 --> 00:29:25,295
and builds something.

673
00:29:25,295 --> 00:29:30,602

674
00:29:30,602 --> 00:29:32,486
AUDIENCE: You could
have a table of values.

675
00:29:32,486 --> 00:29:36,498
Like, A has these
neighbors-- a dictionary.

676
00:29:36,498 --> 00:29:42,190

677
00:29:42,190 --> 00:29:43,560
PROFESSOR: Let's go for that.

678
00:29:43,560 --> 00:29:45,480
So we have a dictionary.

679
00:29:45,480 --> 00:29:48,780
For each vertex
you have the list

680
00:29:48,780 --> 00:29:51,260
of vertices that
are connected to it.

681
00:29:51,260 --> 00:29:52,400
What's the list for A?

682
00:29:52,400 --> 00:29:55,731

683
00:29:55,731 --> 00:29:56,480
AUDIENCE: B and C?

684
00:29:56,480 --> 00:30:00,329

685
00:30:00,329 --> 00:30:01,870
PROFESSOR: OK, what's
the list for B?

686
00:30:01,870 --> 00:30:04,870

687
00:30:04,870 --> 00:30:18,795
AUDIENCE: A, D, and E.

688
00:30:18,795 --> 00:30:19,670
PROFESSOR: All right.

689
00:30:19,670 --> 00:30:22,740
For Python this would
be a dictionary, right?

690
00:30:22,740 --> 00:30:26,650
So how much total
space does this take?

691
00:30:26,650 --> 00:30:28,477
AUDIENCE: The number of nodes?

692
00:30:28,477 --> 00:30:29,560
PROFESSOR: The number of--

693
00:30:29,560 --> 00:30:30,049
AUDIENCE: --nodes.

694
00:30:30,049 --> 00:30:32,483
Well, then there's also the
space you made for the list,

695
00:30:32,483 --> 00:30:32,983
though.

696
00:30:32,983 --> 00:30:36,730

697
00:30:36,730 --> 00:30:38,960
PROFESSOR: If these were
actual slots in an array--

698
00:30:38,960 --> 00:30:41,840
so this would be an array-- I
would have the number of nodes.

699
00:30:41,840 --> 00:30:44,340
You're giving away the
answer to my next question.

700
00:30:44,340 --> 00:30:45,760
So I have these slots here.

701
00:30:45,760 --> 00:30:48,142

702
00:30:48,142 --> 00:30:49,100
This would be an array.

703
00:30:49,100 --> 00:30:51,477
It's order V just to store this.

704
00:30:51,477 --> 00:30:53,810
The thing in Python is that
have these dictionaries that

705
00:30:53,810 --> 00:30:57,850
are fancy hashes where
they grow as you need them.

706
00:30:57,850 --> 00:30:59,880
For example, you
have 10,000 vertices

707
00:30:59,880 --> 00:31:01,700
but you don't have any edge.

708
00:31:01,700 --> 00:31:04,400
Your dictionary size is going
to be order 1 because it only

709
00:31:04,400 --> 00:31:05,854
grows as you add edges to it.

710
00:31:05,854 --> 00:31:08,700

711
00:31:08,700 --> 00:31:11,220
So this is assuming that
I don't store empty lists.

712
00:31:11,220 --> 00:31:14,430
If I have a stray
node here, if I

713
00:31:14,430 --> 00:31:20,320
have a node I-- say this is
I-- if I don't store anything,

714
00:31:20,320 --> 00:31:21,600
I don't have to pay for it.

715
00:31:21,600 --> 00:31:25,020
If I store an empty list here,
then I have to pay for it.

716
00:31:25,020 --> 00:31:29,080
There is an order V
component that you mentioned.

717
00:31:29,080 --> 00:31:31,040
AUDIENCE: Let's say, if
there's a graph there,

718
00:31:31,040 --> 00:31:34,470
everything is not connected
so there are a bunch of words

719
00:31:34,470 --> 00:31:35,450
instead.

720
00:31:35,450 --> 00:31:38,362
Then in that case it
would be order V, right?

721
00:31:38,362 --> 00:31:40,320
PROFESSOR: It's order V
if we store empty lists

722
00:31:40,320 --> 00:31:42,212
for the nodes that
don't have edges.

723
00:31:42,212 --> 00:31:43,116
AUDIENCE: Right.

724
00:31:43,116 --> 00:31:45,330
And if none of the
nodes have edges,

725
00:31:45,330 --> 00:31:47,009
they're all unconnected--

726
00:31:47,009 --> 00:31:49,300
PROFESSOR: On the other hand,
if I don't store anything

727
00:31:49,300 --> 00:31:51,383
for the nodes that don't
have edges, it's order 1.

728
00:31:51,383 --> 00:31:54,300

729
00:31:54,300 --> 00:31:59,240
AUDIENCE: If you get no
edges do we do an empty list

730
00:31:59,240 --> 00:32:01,480
or do we not store it?

731
00:32:01,480 --> 00:32:03,590
PROFESSOR: Depends
on what you want.

732
00:32:03,590 --> 00:32:05,000
So if we store
empty lists you're

733
00:32:05,000 --> 00:32:06,560
going to have an
order V cost here.

734
00:32:06,560 --> 00:32:08,460
But your code is going to
be simpler, presumably,

735
00:32:08,460 --> 00:32:10,293
because you don't have
to check if something

736
00:32:10,293 --> 00:32:12,430
is or isn't in the dictionary.

737
00:32:12,430 --> 00:32:14,040
How about this stuff?

738
00:32:14,040 --> 00:32:18,164
What's the total size
of this stuff here?

739
00:32:18,164 --> 00:32:19,086
AUDIENCE: [INAUDIBLE].

740
00:32:19,086 --> 00:32:21,547

741
00:32:21,547 --> 00:32:22,130
PROFESSOR: OK.

742
00:32:22,130 --> 00:32:28,700
Order E. How many elements
do I have in here in total?

743
00:32:28,700 --> 00:32:33,080

744
00:32:33,080 --> 00:32:35,940
In this thing here.

745
00:32:35,940 --> 00:32:41,008
So what's the sum of
the length of the lists?

746
00:32:41,008 --> 00:32:45,370
AUDIENCE: Average value of E
times the number of vertices?

747
00:32:45,370 --> 00:32:47,660
PROFESSOR: Let's go
over something else.

748
00:32:47,660 --> 00:32:48,950
AUDIENCE: The degree--

749
00:32:48,950 --> 00:32:49,825
PROFESSOR: All right.

750
00:32:49,825 --> 00:32:52,350
That's what I wanted to hear.

751
00:32:52,350 --> 00:32:53,870
A lists its neighbors, right?

752
00:32:53,870 --> 00:32:56,520

753
00:32:56,520 --> 00:33:02,780
The number of neighbors that
A has is the degree of A. B

754
00:33:02,780 --> 00:33:08,350
lists its neighbors, so
this is the degree of B.

755
00:33:08,350 --> 00:33:13,550
If you sum up over all of them,
what is the sum of all the

756
00:33:13,550 --> 00:33:15,750
agrees in the graph?

757
00:33:15,750 --> 00:33:17,190
AUDIENCE: 2, E.

758
00:33:17,190 --> 00:33:21,710
PROFESSOR: 2, E. We
learned about this, right?

759
00:33:21,710 --> 00:33:24,530
The handshaking
lemma, 2, E. So what

760
00:33:24,530 --> 00:33:27,070
is the total cost for
storing this data structure?

761
00:33:27,070 --> 00:33:32,782

762
00:33:32,782 --> 00:33:33,734
AUDIENCE: [INAUDIBLE].

763
00:33:33,734 --> 00:33:36,590

764
00:33:36,590 --> 00:33:40,410
PROFESSOR: So V plus E,
assuming empty lists.

765
00:33:40,410 --> 00:33:41,910
Let's look at another
data structure

766
00:33:41,910 --> 00:33:46,510
for storing things in a graph.

767
00:33:46,510 --> 00:33:50,780
So instead of using
lists, let's use a matrix.

768
00:33:50,780 --> 00:33:58,730
A, B, C, D, E on top, and
A, B, C, D, E on the left.

769
00:33:58,730 --> 00:34:01,190
Let's pretend our graph is
just that component over there.

770
00:34:01,190 --> 00:34:05,360
Otherwise, it just gets big
and there's no extraneous site.

771
00:34:05,360 --> 00:34:09,254
Does anyone know
how this is called?

772
00:34:09,254 --> 00:34:10,670
If I put numbers
here, does anyone

773
00:34:10,670 --> 00:34:12,920
know what this is called?

774
00:34:12,920 --> 00:34:15,320
AUDIENCE: Is that a matrix?

775
00:34:15,320 --> 00:34:18,131
PROFESSOR: There's
a fancy name for it.

776
00:34:18,131 --> 00:34:18,964
It ends with matrix.

777
00:34:18,964 --> 00:34:21,530

778
00:34:21,530 --> 00:34:23,100
OK.

779
00:34:23,100 --> 00:34:25,790
I don't think we taught
it to you, so don't worry.

780
00:34:25,790 --> 00:34:32,560
The fancy name is maybe it's
misspelled, but something

781
00:34:32,560 --> 00:34:35,820
that looks and sounds like
this., adjacency matrix.

782
00:34:35,820 --> 00:34:39,080

783
00:34:39,080 --> 00:34:39,580
Misspelled?

784
00:34:39,580 --> 00:34:42,595

785
00:34:42,595 --> 00:34:45,836
AUDIENCE: [INAUDIBLE].

786
00:34:45,836 --> 00:34:48,560
PROFESSOR: I hope
someone will help me.

787
00:34:48,560 --> 00:34:50,820
OK so if this is an
adjacency matrix,

788
00:34:50,820 --> 00:34:54,179
what should this element
between B and A tell me?

789
00:34:54,179 --> 00:34:58,230

790
00:34:58,230 --> 00:35:00,134
If it's an adjacency
matrix, it better

791
00:35:00,134 --> 00:35:01,300
tell me if they're adjacent.

792
00:35:01,300 --> 00:35:05,070
They're adjacent if they
have an edge between them.

793
00:35:05,070 --> 00:35:08,527
For A and B, what
does it happen to be?

794
00:35:08,527 --> 00:35:09,110
AUDIENCE: One?

795
00:35:09,110 --> 00:35:12,870

796
00:35:12,870 --> 00:35:13,480
PROFESSOR: OK.

797
00:35:13,480 --> 00:35:13,980
A and A?

798
00:35:13,980 --> 00:35:14,563
What do we do?

799
00:35:14,563 --> 00:35:17,806

800
00:35:17,806 --> 00:35:18,880
AUDIENCE: What with 1?

801
00:35:18,880 --> 00:35:20,130
It's adjacent to itself.

802
00:35:20,130 --> 00:35:21,880
PROFESSOR: What's
easier for the algorithm

803
00:35:21,880 --> 00:35:23,473
that you're trying to implement?

804
00:35:23,473 --> 00:35:24,380
AUDIENCE: 1?

805
00:35:24,380 --> 00:35:26,004
PROFESSOR: So it
doesn't really matter.

806
00:35:26,004 --> 00:35:28,140
We use 1's most of the
time, but sometimes it's

807
00:35:28,140 --> 00:35:30,983
easier to use a 0.

808
00:35:30,983 --> 00:35:33,388
AUDIENCE: Then you can
get to A from A, right?

809
00:35:33,388 --> 00:35:34,350
PROFESSOR: Yeah.

810
00:35:34,350 --> 00:35:35,540
So that's why you'd use a 1.

811
00:35:35,540 --> 00:35:37,415
Sometimes, though, you
don't want to in code.

812
00:35:37,415 --> 00:35:40,760

813
00:35:40,760 --> 00:35:42,870
So someone dictate this to me.

814
00:35:42,870 --> 00:35:46,220
Or, everyone dictate this to
me so I know it makes sense.

815
00:35:46,220 --> 00:35:48,726
A and C, is there an
edge between them?

816
00:35:48,726 --> 00:35:49,700
AUDIENCE: Yes.

817
00:35:49,700 --> 00:35:50,866
PROFESSOR: What do I write?

818
00:35:50,866 --> 00:35:51,589
AUDIENCE: 1.

819
00:35:51,589 --> 00:35:52,380
PROFESSOR: A and D?

820
00:35:52,380 --> 00:35:56,440

821
00:35:56,440 --> 00:35:57,772
A and E?

822
00:35:57,772 --> 00:35:59,930
AUDIENCE: 0.

823
00:35:59,930 --> 00:36:00,778
PROFESSOR: B, A?

824
00:36:00,778 --> 00:36:03,120
AUDIENCE: 1.

825
00:36:03,120 --> 00:36:04,164
PROFESSOR: B, C?

826
00:36:04,164 --> 00:36:06,020
AUDIENCE: 0.

827
00:36:06,020 --> 00:36:06,930
PROFESSOR: B, D?

828
00:36:06,930 --> 00:36:08,160
AUDIENCE: 1.

829
00:36:08,160 --> 00:36:09,052
PROFESSOR: The E?

830
00:36:09,052 --> 00:36:10,440
AUDIENCE: 1.

831
00:36:10,440 --> 00:36:11,600
PROFESSOR: OK.

832
00:36:11,600 --> 00:36:12,666
C, A?

833
00:36:12,666 --> 00:36:13,640
AUDIENCE: 1.

834
00:36:13,640 --> 00:36:15,035
PROFESSOR: C, B?

835
00:36:15,035 --> 00:36:16,430
AUDIENCE: 2.

836
00:36:16,430 --> 00:36:17,326
PROFESSOR: C, D?

837
00:36:17,326 --> 00:36:18,024
AUDIENCE: 1.

838
00:36:18,024 --> 00:36:18,690
PROFESSOR: C, E?

839
00:36:18,690 --> 00:36:20,590
AUDIENCE: 0.

840
00:36:20,590 --> 00:36:21,720
PROFESSOR: All right.

841
00:36:21,720 --> 00:36:23,290
Now I'm going to
use the bits you

842
00:36:23,290 --> 00:36:27,574
gave me to come to get this.

843
00:36:27,574 --> 00:36:29,540
Let's see if I can
do it correctly.

844
00:36:29,540 --> 00:36:31,122
And D?

845
00:36:31,122 --> 00:36:33,580
I'm not looking at the graph,
by the way, I'm trusting you.

846
00:36:33,580 --> 00:36:35,204
So you better give
me the right answer.

847
00:36:35,204 --> 00:36:35,931
D?

848
00:36:35,931 --> 00:36:36,430
AUDIENCE: 1.

849
00:36:36,430 --> 00:36:41,760

850
00:36:41,760 --> 00:36:43,510
PROFESSOR: How many
1's do I have in this?

851
00:36:43,510 --> 00:36:50,272

852
00:36:50,272 --> 00:36:51,549
AUDIENCE: [INAUDIBLE].

853
00:36:51,549 --> 00:36:53,340
PROFESSOR: To see if
you guys are thinking.

854
00:36:53,340 --> 00:36:57,678

855
00:36:57,678 --> 00:36:59,124
AUDIENCE: 2, E? [INAUDIBLE].

856
00:36:59,124 --> 00:37:01,820

857
00:37:01,820 --> 00:37:05,507
PROFESSOR: Each edge
contributes to two 1's, right?

858
00:37:05,507 --> 00:37:07,090
And that accounts
for most of the 1's.

859
00:37:07,090 --> 00:37:10,024

860
00:37:10,024 --> 00:37:17,530
AUDIENCE: O plus V.

861
00:37:17,530 --> 00:37:20,920
PROFESSOR: So this is
how many 1's I have.

862
00:37:20,920 --> 00:37:25,270
How many 0's do I have?

863
00:37:25,270 --> 00:37:28,201
AUDIENCE: V squared
minus 2, E plus V?

864
00:37:28,201 --> 00:37:34,222

865
00:37:34,222 --> 00:37:35,680
PROFESSOR: This is
a non-boring way

866
00:37:35,680 --> 00:37:38,289
of asking how many elements
I have in this matrix.

867
00:37:38,289 --> 00:37:39,580
This is what I was looking for.

868
00:37:39,580 --> 00:37:42,300

869
00:37:42,300 --> 00:37:47,070
So V columns, right?

870
00:37:47,070 --> 00:37:49,005
Zeros V squared's
total elements.

871
00:37:49,005 --> 00:37:52,080

872
00:37:52,080 --> 00:37:54,870
How much memory do I
need to store this?

873
00:37:54,870 --> 00:37:55,746
AUDIENCE: V squared.

874
00:37:55,746 --> 00:37:56,870
PROFESSOR: V squared. what?

875
00:37:56,870 --> 00:38:00,020
If I want to store it as
compactly as possible?

876
00:38:00,020 --> 00:38:01,860
I want to pack these
as tight as I can.

877
00:38:01,860 --> 00:38:04,650

878
00:38:04,650 --> 00:38:06,962
AUDIENCE: You mean you need
the entire array arranged?

879
00:38:06,962 --> 00:38:08,420
PROFESSOR: Yes, so
what do I store?

880
00:38:08,420 --> 00:38:09,512
V squared what?

881
00:38:09,512 --> 00:38:10,720
AUDIENCE: Oh, you mean units.

882
00:38:10,720 --> 00:38:11,386
PROFESSOR: Yeah.

883
00:38:11,386 --> 00:38:12,650
What's the unit?

884
00:38:12,650 --> 00:38:13,610
AUDIENCE: 1 bit?

885
00:38:13,610 --> 00:38:14,485
PROFESSOR: All right!

886
00:38:14,485 --> 00:38:25,460
So V squared bits Whereas,
this is V plus E words

887
00:38:25,460 --> 00:38:28,070
because you have to store
pointers everywhere here.

888
00:38:28,070 --> 00:38:30,640

889
00:38:30,640 --> 00:38:32,770
So sometimes if your
graph is really dense

890
00:38:32,770 --> 00:38:34,670
you might prefer
this representation.

891
00:38:34,670 --> 00:38:38,670

892
00:38:38,670 --> 00:38:42,300
Let me see, how much do I have?

893
00:38:42,300 --> 00:38:44,070
Oh, plenty of time.

894
00:38:44,070 --> 00:38:47,840
Who remembers
breadth-first search?

895
00:38:47,840 --> 00:38:48,718
Yes?

896
00:38:48,718 --> 00:38:51,008
AUDIENCE: Basically you
just start at some node

897
00:38:51,008 --> 00:38:56,560
and you check all its neighbors,
and check all those neighbors.

898
00:38:56,560 --> 00:38:57,514
PROFESSOR: All right.

899
00:38:57,514 --> 00:38:59,180
In breadth-first
search we have a graph.

900
00:38:59,180 --> 00:39:04,350

901
00:39:04,350 --> 00:39:06,800
What did I draw there?

902
00:39:06,800 --> 00:39:24,480
A. B, E. So suppose
this is our graph.

903
00:39:24,480 --> 00:39:28,920
And I do a breadth-first
search starting at A.

904
00:39:28,920 --> 00:39:29,910
How does that work?

905
00:39:29,910 --> 00:39:32,470

906
00:39:32,470 --> 00:39:36,687
I started with the list of the
nodes that I'm going to visit.

907
00:39:36,687 --> 00:39:39,020
I initialization it with A
because this is the only node

908
00:39:39,020 --> 00:39:40,075
that I know about.

909
00:39:40,075 --> 00:39:45,340

910
00:39:45,340 --> 00:39:48,100
What happens next?

911
00:39:48,100 --> 00:39:49,885
AUDIENCE: It goes with B and C.

912
00:39:49,885 --> 00:39:50,760
PROFESSOR: All right.

913
00:39:50,760 --> 00:39:54,200
So I take out of the list
the first thing that I can.

914
00:39:54,200 --> 00:39:55,900
This is my current node.

915
00:39:55,900 --> 00:39:58,540
You said I visit B and C
because they're the neighbors.

916
00:39:58,540 --> 00:39:59,040
Right.

917
00:39:59,040 --> 00:40:02,230

918
00:40:02,230 --> 00:40:06,130
I took A out of the list.

919
00:40:06,130 --> 00:40:07,460
A was definitely visited.

920
00:40:07,460 --> 00:40:12,350
And I'm visiting B and C. What
do I do when I visit them?

921
00:40:12,350 --> 00:40:13,812
AUDIENCE: Put them in the list.

922
00:40:13,812 --> 00:40:15,145
PROFESSOR: Put them in the list.

923
00:40:15,145 --> 00:40:18,630

924
00:40:18,630 --> 00:40:21,420
This means I discovered them and
I'm going to visit the later.

925
00:40:21,420 --> 00:40:23,590
So I discovered them and
I know of their existence.

926
00:40:23,590 --> 00:40:26,725
What happens next?

927
00:40:26,725 --> 00:40:29,320
AUDIENCE: Check if
B is what you want.

928
00:40:29,320 --> 00:40:35,078
PROFESSOR: So B gets out of
the list, and what do I do?

929
00:40:35,078 --> 00:40:36,950
AUDIENCE: Discover
it's neighbors.

930
00:40:36,950 --> 00:40:38,700
PROFESSOR: All right,
so its neighborhoods

931
00:40:38,700 --> 00:40:41,552
are A, B, and E. What Now?

932
00:40:41,552 --> 00:40:42,926
AUDIENCE: If they
haven't already

933
00:40:42,926 --> 00:40:46,241
been on that list then
add a [INAUDIBLE].

934
00:40:46,241 --> 00:40:47,615
PROFESSOR: A was
already visited.

935
00:40:47,615 --> 00:40:48,845
D and E weren't.

936
00:40:48,845 --> 00:40:52,410

937
00:40:52,410 --> 00:40:58,350
D and E, then what happens?

938
00:40:58,350 --> 00:41:01,944
AUDIENCE: Then you
check C's neighbors.

939
00:41:01,944 --> 00:41:03,860
PROFESSOR: Any neighbor's
that I haven't seen?

940
00:41:03,860 --> 00:41:05,320
Nope.

941
00:41:05,320 --> 00:41:06,548
Then?

942
00:41:06,548 --> 00:41:07,820
AUDIENCE: D?

943
00:41:07,820 --> 00:41:09,708
AUDIENCE: D and?

944
00:41:09,708 --> 00:41:11,829
AUDIENCE: E.

945
00:41:11,829 --> 00:41:12,370
PROFESSOR:OK.

946
00:41:12,370 --> 00:41:14,596
And then?

947
00:41:14,596 --> 00:41:16,137
PROFESSOR: I guess
you could go to F,

948
00:41:16,137 --> 00:41:18,492
but it's not
connected to anything.

949
00:41:18,492 --> 00:41:20,344
But how did you
get A then, right?

950
00:41:20,344 --> 00:41:21,760
PROFESSOR: So A
is the first node.

951
00:41:21,760 --> 00:41:23,300
I started with A
because I said I'm

952
00:41:23,300 --> 00:41:26,200
doing a breadth-first
search starting from A.

953
00:41:26,200 --> 00:41:29,490
So BFS starts from somewhere.

954
00:41:29,490 --> 00:41:32,110
A BFS has a source.

955
00:41:32,110 --> 00:41:34,270
We'll see why that
matters in a bit.

956
00:41:34,270 --> 00:41:36,166
So you ever get to see F?

957
00:41:36,166 --> 00:41:37,000
AUDIENCE: No.

958
00:41:37,000 --> 00:41:37,666
PROFESSOR: Nope.

959
00:41:37,666 --> 00:41:40,740

960
00:41:40,740 --> 00:41:43,170
So if I start at A what
are the nodes that I visit

961
00:41:43,170 --> 00:41:44,920
and what are the nodes
that I don't visit?

962
00:41:44,920 --> 00:41:47,609

963
00:41:47,609 --> 00:41:50,150
AUDIENCE: Well you visit all
the ones in the connected graph.

964
00:41:50,150 --> 00:41:52,410
PROFESSOR: All right, in
the connected component.

965
00:41:52,410 --> 00:41:54,785
So the whole graph can be
connected or not connected.

966
00:41:54,785 --> 00:41:57,950

967
00:41:57,950 --> 00:41:59,520
The nodes that I
visit are the nodes

968
00:41:59,520 --> 00:42:02,190
in A's connected component
because, by definition, those

969
00:42:02,190 --> 00:42:05,680
are the nodes that
I can reach from A.

970
00:42:05,680 --> 00:42:07,230
If I have many kind
of the components

971
00:42:07,230 --> 00:42:09,260
and I use BFS starting
from one node,

972
00:42:09,260 --> 00:42:11,160
I might not visit
the entire graph.

973
00:42:11,160 --> 00:42:14,760

974
00:42:14,760 --> 00:42:17,260
How do I keep track of what
node that I've discovered

975
00:42:17,260 --> 00:42:18,294
and haven't discovered?

976
00:42:18,294 --> 00:42:20,460
What data structure do I
use for these smiley faces?

977
00:42:20,460 --> 00:42:27,428

978
00:42:27,428 --> 00:42:29,340
AUDIENCE: [INAUDIBLE].

979
00:42:29,340 --> 00:42:30,950
PROFESSOR:So for
the smiley faces.

980
00:42:30,950 --> 00:42:33,376
For this thing I
probably want a queue.

981
00:42:33,376 --> 00:42:34,750
We'd teach you
something simpler,

982
00:42:34,750 --> 00:42:37,680
but most of the time when
you write the code you

983
00:42:37,680 --> 00:42:39,620
actually use queue.

984
00:42:39,620 --> 00:42:41,730
What do I want for
the smiley faces?

985
00:42:41,730 --> 00:42:45,006
When I pull a node out,
say I pulled out B,

986
00:42:45,006 --> 00:42:48,940
and I see A, D, E, I want
to know that I visited A

987
00:42:48,940 --> 00:42:51,490
and I didn't visit the D
and E. You guys remember

988
00:42:51,490 --> 00:42:54,420
that we didn't visit D and E,
right, by the time we got to 2?

989
00:42:54,420 --> 00:42:55,190
OK.

990
00:42:55,190 --> 00:42:57,560
So I want to be able to check
whether I visited a node

991
00:42:57,560 --> 00:42:58,990
or not really fast.

992
00:42:58,990 --> 00:43:02,294
What data structure should
I use for the smileys?

993
00:43:02,294 --> 00:43:03,482
AUDIENCE: A hash table.

994
00:43:03,482 --> 00:43:04,440
PROFESSOR: A has table.

995
00:43:04,440 --> 00:43:04,939
Cool.

996
00:43:04,939 --> 00:43:07,404
What's a hash table in Python?

997
00:43:07,404 --> 00:43:08,707
AUDIENCE: A dictionary.

998
00:43:08,707 --> 00:43:09,707
PROFESSOR: A dictionary.

999
00:43:09,707 --> 00:43:12,630

1000
00:43:12,630 --> 00:43:16,140
All right, so this is
going to be a seen, which

1001
00:43:16,140 --> 00:43:22,060
is a dictionary, and it
maps vertices to maybe true.

1002
00:43:22,060 --> 00:43:26,830

1003
00:43:26,830 --> 00:43:28,110
AUDIENCE: [INAUDIBLE].

1004
00:43:28,110 --> 00:43:28,960
PROFESSOR:Yep.

1005
00:43:28,960 --> 00:43:30,157
Python has a set, right?

1006
00:43:30,157 --> 00:43:30,990
So you can use that.

1007
00:43:30,990 --> 00:43:34,430

1008
00:43:34,430 --> 00:43:40,230
The smileys needs to be
some sort of a dictionary.

1009
00:43:40,230 --> 00:43:43,510
So given that, and
assuming that this

1010
00:43:43,510 --> 00:43:46,375
is a queue that we
can extract and you

1011
00:43:46,375 --> 00:43:48,506
can start from in
constant time, what

1012
00:43:48,506 --> 00:43:49,630
is the running time of BFS?

1013
00:43:49,630 --> 00:43:52,906

1014
00:43:52,906 --> 00:43:53,780
Let's make life easy.

1015
00:43:53,780 --> 00:43:55,900
Let's assume the graph is
connected and let's assume just

1016
00:43:55,900 --> 00:43:56,660
doesn't exist.

1017
00:43:56,660 --> 00:44:00,200

1018
00:44:00,200 --> 00:44:01,515
BFS was the running time.

1019
00:44:01,515 --> 00:44:06,850

1020
00:44:06,850 --> 00:44:09,014
AUDIENCE: [INAUDIBLE] visiting.

1021
00:44:09,014 --> 00:44:10,680
PROFESSOR: So you
visit every node once,

1022
00:44:10,680 --> 00:44:13,030
so it's at least
V. That's a start.

1023
00:44:13,030 --> 00:44:15,774
Now what do you do when
you visit the node?

1024
00:44:15,774 --> 00:44:17,690
AUDIENCE: Check out all the--

1025
00:44:17,690 --> 00:44:19,740
PROFESSOR: All the
neighbors, right?

1026
00:44:19,740 --> 00:44:21,930
Given the node, you have
to go to the data structure

1027
00:44:21,930 --> 00:44:24,250
that you have that's
either this or this,

1028
00:44:24,250 --> 00:44:27,150
and you have to get
a list of neighbors.

1029
00:44:27,150 --> 00:44:29,700
If I have this data
structure, how fast

1030
00:44:29,700 --> 00:44:31,930
do I get a list of
neighbors for a node?

1031
00:44:31,930 --> 00:44:34,185
AUDIENCE: Order of the degree?

1032
00:44:34,185 --> 00:44:34,810
PROFESSOR: Yep.

1033
00:44:34,810 --> 00:44:36,160
Order of the degree of the node.

1034
00:44:36,160 --> 00:44:36,810
That's good.

1035
00:44:36,810 --> 00:44:38,300
How about this data structure?

1036
00:44:38,300 --> 00:44:43,701

1037
00:44:43,701 --> 00:44:46,660
AUDIENCE: Same-- oh,
no that's order of V.

1038
00:44:46,660 --> 00:44:47,510
PROFESSOR: Yep.

1039
00:44:47,510 --> 00:44:49,900
So in this data structure,
for example, C only

1040
00:44:49,900 --> 00:44:55,020
has two edges coming out of it.

1041
00:44:55,020 --> 00:44:57,540
But I have to go through the
entire lining of the matrix

1042
00:44:57,540 --> 00:45:01,130
to see where I have my 0's
and where I have my 1's.

1043
00:45:01,130 --> 00:45:04,890
In order to list the neighbors,
here is straight up order V,

1044
00:45:04,890 --> 00:45:11,420
whereas this is order of
the degree of the node

1045
00:45:11,420 --> 00:45:15,020
that I'm looking for.

1046
00:45:15,020 --> 00:45:17,229
So for this, where it's
nice and simple, order of V,

1047
00:45:17,229 --> 00:45:18,520
what is the total running time?

1048
00:45:18,520 --> 00:45:22,384

1049
00:45:22,384 --> 00:45:25,040
AUDIENCE: Wait, because
it's B plus B. Oh no, it's

1050
00:45:25,040 --> 00:45:27,230
the same one.

1051
00:45:27,230 --> 00:45:28,860
PROFESSOR: So for
each node I have to?

1052
00:45:28,860 --> 00:45:29,707
AUDIENCE: V squared.

1053
00:45:29,707 --> 00:45:30,290
PROFESSOR: OK.

1054
00:45:30,290 --> 00:45:33,680

1055
00:45:33,680 --> 00:45:36,950
So we're up to V
squared already.

1056
00:45:36,950 --> 00:45:38,195
What else do we need to do?

1057
00:45:38,195 --> 00:45:42,890

1058
00:45:42,890 --> 00:45:45,265
Anything that they need to
do on a node is order of V,

1059
00:45:45,265 --> 00:45:47,390
so V squared is going to
be the total running time.

1060
00:45:47,390 --> 00:45:48,590
That's it.

1061
00:45:48,590 --> 00:45:51,980
So if we use an
adjacency matrix we

1062
00:45:51,980 --> 00:45:56,340
get order of V squared as
the total running time.

1063
00:45:56,340 --> 00:45:59,655
What about if we lists,
what the running time?

1064
00:45:59,655 --> 00:46:00,530
I'll give you a hint.

1065
00:46:00,530 --> 00:46:03,140
You have to use
amortized analysis.

1066
00:46:03,140 --> 00:46:05,230
Shivers anyone?

1067
00:46:05,230 --> 00:46:07,574
[LAUGHTER]

1068
00:46:07,574 --> 00:46:08,990
We know it's order
V because we're

1069
00:46:08,990 --> 00:46:11,350
going to visit every node.

1070
00:46:11,350 --> 00:46:14,139
And you guys didn't see what
I was going to write here.

1071
00:46:14,139 --> 00:46:15,361
[LAUGHTER]

1072
00:46:15,361 --> 00:46:15,860
OK.

1073
00:46:15,860 --> 00:46:18,270
So for every node I go
through the neighbors

1074
00:46:18,270 --> 00:46:19,660
and I do something to them.

1075
00:46:19,660 --> 00:46:20,160
Right?

1076
00:46:20,160 --> 00:46:22,490
I check if they're in
seen, if not then I

1077
00:46:22,490 --> 00:46:25,820
add them to the list.

1078
00:46:25,820 --> 00:46:29,814
So for every node the work is?

1079
00:46:29,814 --> 00:46:31,620
AUDIENCE: it's degrees.

1080
00:46:31,620 --> 00:46:32,940
PROFESSOR: Yep.

1081
00:46:32,940 --> 00:46:35,416
So if I look at all the nodes?

1082
00:46:35,416 --> 00:46:37,035
AUDIENCE: That's E.

1083
00:46:37,035 --> 00:46:37,660
PROFESSOR: Yep.

1084
00:46:37,660 --> 00:46:41,010

1085
00:46:41,010 --> 00:46:43,180
For every node I have
to look at its neighbors

1086
00:46:43,180 --> 00:46:45,407
and I have to see which
neighbors are in seen.

1087
00:46:45,407 --> 00:46:46,990
For the neighbors
that are not in seen

1088
00:46:46,990 --> 00:46:50,890
I have to add to my queue.

1089
00:46:50,890 --> 00:46:53,230
Checking if a neighbor is
in seen or not is order 1.

1090
00:46:53,230 --> 00:46:55,620
Adding it to the
queue is order 1.

1091
00:46:55,620 --> 00:46:57,430
So the total work
for a node is order

1092
00:46:57,430 --> 00:47:04,390
of neighbors because of the
adjacency list, not matrix.

1093
00:47:04,390 --> 00:47:06,590
If I look at the
entire graph, here I

1094
00:47:06,590 --> 00:47:08,641
can't do a local analysis
like I did before.

1095
00:47:08,641 --> 00:47:11,015
If I look at the entire graph
and I look at all the nodes

1096
00:47:11,015 --> 00:47:14,740
slash vertices,
then the total work

1097
00:47:14,740 --> 00:47:17,490
is the sum of their degrees.

1098
00:47:17,490 --> 00:47:18,670
For each node is degree.

1099
00:47:18,670 --> 00:47:19,920
For total work,
sum of the degrees.

1100
00:47:19,920 --> 00:47:21,503
And I have that nice
handshaking lemma

1101
00:47:21,503 --> 00:47:24,550
that says that the sum
of the degrees is 2,

1102
00:47:24,550 --> 00:47:27,610
E. So order E. So
total running time?

1103
00:47:27,610 --> 00:47:32,860
V plus E.

1104
00:47:32,860 --> 00:47:37,030
OK, can I say that the
running time is order E?

1105
00:47:37,030 --> 00:47:38,966
With no V's?

1106
00:47:38,966 --> 00:47:41,007
AUDIENCE: No, because you
have to look at every--

1107
00:47:41,007 --> 00:47:44,935

1108
00:47:44,935 --> 00:47:46,382
PROFESSOR: Is it?

1109
00:47:46,382 --> 00:47:47,881
AUDIENCE: V greater
than [INAUDIBLE]

1110
00:47:47,881 --> 00:47:50,724
in case of not
connected components?

1111
00:47:50,724 --> 00:47:51,640
AUDIENCE: [INAUDIBLE].

1112
00:47:51,640 --> 00:48:01,548

1113
00:48:01,548 --> 00:48:03,131
AUDIENCE: It's
possible that you could

1114
00:48:03,131 --> 00:48:06,887
have more vertices than edges--

1115
00:48:06,887 --> 00:48:07,470
PROFESSOR: OK.

1116
00:48:07,470 --> 00:48:10,920
So it's possible that I have
more vertices than edges.

1117
00:48:10,920 --> 00:48:13,220
I agree with that, but I
do anything to the vertices

1118
00:48:13,220 --> 00:48:14,080
that I haven't seen?

1119
00:48:14,080 --> 00:48:24,220

1120
00:48:24,220 --> 00:48:26,081
So this is subtle.

1121
00:48:26,081 --> 00:48:28,860
The difference
between this and this

1122
00:48:28,860 --> 00:48:31,770
is a matter of how you
implement everything.

1123
00:48:31,770 --> 00:48:34,980
In CLRS they assume that
the seen is an array.

1124
00:48:34,980 --> 00:48:38,220
So all of their nodes
have numbers from 1 to V.

1125
00:48:38,220 --> 00:48:40,740
So then they initialize an
array, everything is false,

1126
00:48:40,740 --> 00:48:42,880
and then they set
the true elements.

1127
00:48:42,880 --> 00:48:44,255
In Python we can
use a dictionary

1128
00:48:44,255 --> 00:48:47,010
and not initialize
it with anything.

1129
00:48:47,010 --> 00:48:49,750
So if you do it that way in
Python and code carefully,

1130
00:48:49,750 --> 00:48:53,320
you can get to order E.
The parts of the graph

1131
00:48:53,320 --> 00:48:55,930
that you don't discover, you
don't have to pay for them.

1132
00:48:55,930 --> 00:48:58,010
If you look at CLRS
code, it is definitely

1133
00:48:58,010 --> 00:49:02,210
V plus E. The difference
between this and this

1134
00:49:02,210 --> 00:49:04,850
depends on the code.

1135
00:49:04,850 --> 00:49:07,000
What's the point
of BFS, by the way?

1136
00:49:07,000 --> 00:49:07,740
Why do we care?

1137
00:49:07,740 --> 00:49:08,850
What does it give us?

1138
00:49:08,850 --> 00:49:12,140

1139
00:49:12,140 --> 00:49:15,870
AUDIENCE: The
shortest word path.

1140
00:49:15,870 --> 00:49:19,105
PROFESSOR:The shortest
path from point?

1141
00:49:19,105 --> 00:49:22,450
AUDIENCE: From your start
to where you're going.

1142
00:49:22,450 --> 00:49:26,650
PROFESSOR:So it gives you the
shortest path from the node

1143
00:49:26,650 --> 00:49:29,610
that I'm starting the BFS from.

1144
00:49:29,610 --> 00:49:32,590
So only from this node?

1145
00:49:32,590 --> 00:49:34,630
If I start BFS at A
it's going to give me

1146
00:49:34,630 --> 00:49:38,140
the length of the shortest
path from A to which node?

1147
00:49:38,140 --> 00:49:41,430

1148
00:49:41,430 --> 00:49:44,209
AUDIENCE: [INAUDIBLE].

1149
00:49:44,209 --> 00:49:45,250
PROFESSOR: All the nodes?

1150
00:49:45,250 --> 00:49:45,995
AUDIENCE: Yeah.

1151
00:49:45,995 --> 00:49:47,370
PROFESSOR: All
the nodes that are

1152
00:49:47,370 --> 00:49:51,450
visited by BFS are reachable
and we have a path from them.

1153
00:49:51,450 --> 00:49:53,860
How do you compute
this distance?

1154
00:49:53,860 --> 00:49:57,004
Let's see, so what's the
distance from A to A?

1155
00:49:57,004 --> 00:49:57,729
AUDIENCE: 0?

1156
00:49:57,729 --> 00:49:58,270
PROFESSOR: 0.

1157
00:49:58,270 --> 00:50:00,860

1158
00:50:00,860 --> 00:50:03,750
When I start from A and I see
that its neighbors are B and C,

1159
00:50:03,750 --> 00:50:08,323
what's the distance from
A to B and from A to C?

1160
00:50:08,323 --> 00:50:09,239
AUDIENCE: [INAUDIBLE].

1161
00:50:09,239 --> 00:50:11,737

1162
00:50:11,737 --> 00:50:12,320
PROFESSOR: OK.

1163
00:50:12,320 --> 00:50:16,950
Now I look at B. What's the
distance between A and A?

1164
00:50:16,950 --> 00:50:19,694
A is B's neighbor.

1165
00:50:19,694 --> 00:50:20,854
AUDIENCE: With A and A?

1166
00:50:20,854 --> 00:50:21,520
PROFESSOR: Yeah.

1167
00:50:21,520 --> 00:50:23,630
So I have three neighbors.

1168
00:50:23,630 --> 00:50:26,400
B has three neighbors,
A, D, and E.

1169
00:50:26,400 --> 00:50:35,310
So I care about the distances
between A and A, D, E. Distance

1170
00:50:35,310 --> 00:50:44,230
A, A, distance A, D, and
distance A, E. This one is 0.

1171
00:50:44,230 --> 00:50:48,620
How about the distances
between A and D and A and E?

1172
00:50:48,620 --> 00:50:49,350
They're 2.

1173
00:50:49,350 --> 00:50:52,930

1174
00:50:52,930 --> 00:50:55,375
So the way I would
compute these distances

1175
00:50:55,375 --> 00:50:57,910
is that I start with A being 0.

1176
00:50:57,910 --> 00:50:59,830
The distance from A to A is 0.

1177
00:50:59,830 --> 00:51:03,120
And then when I look at a node,
when I discover the neighbors,

1178
00:51:03,120 --> 00:51:05,520
all the neighbors that don't
have smiley faces on them

1179
00:51:05,520 --> 00:51:08,107
get the node's distance plus 1.

1180
00:51:08,107 --> 00:51:10,190
You can get to them by
getting in the current node

1181
00:51:10,190 --> 00:51:12,740
and then traversing an edge.

1182
00:51:12,740 --> 00:51:15,150
When you do that it's
important that you don't update

1183
00:51:15,150 --> 00:51:17,340
the distances of the nodes
that have smiley faces.

1184
00:51:17,340 --> 00:51:19,840
If you do, you're going to say
that the distance from A to A

1185
00:51:19,840 --> 00:51:22,890
is 2 and all hell
breaks lose from there.

1186
00:51:22,890 --> 00:51:25,521

1187
00:51:25,521 --> 00:51:27,520
AUDIENCE: Wait, why would
you say it would be 2?

1188
00:51:27,520 --> 00:51:30,820
PROFESSOR: If I forget the
fact that it has a smiley face.

1189
00:51:30,820 --> 00:51:33,360
So if I go through
all these neighbors

1190
00:51:33,360 --> 00:51:35,140
and I say the
distance from A to B

1191
00:51:35,140 --> 00:51:39,180
is one then the distance from
A to all of B's neighbors

1192
00:51:39,180 --> 00:51:41,330
has to be 2.

1193
00:51:41,330 --> 00:51:43,004
That would be wrong.

1194
00:51:43,004 --> 00:51:44,420
AUDIENCE: Wait,
from A to all of--

1195
00:51:44,420 --> 00:51:46,500
PROFESSOR: B's neighbors.

1196
00:51:46,500 --> 00:51:48,750
AUDIENCE: From A to all of--
Oh, because A is one Of--

1197
00:51:48,750 --> 00:51:49,862
PROFESSOR: B's neighbors.

1198
00:51:49,862 --> 00:51:51,240
AUDIENCE: Yeah OK.

1199
00:51:51,240 --> 00:51:53,910
PROFESSOR: The
smileys tell me which

1200
00:51:53,910 --> 00:51:56,350
vertices I've already
seen and I've already,

1201
00:51:56,350 --> 00:51:58,450
presumably computed
distances for them.

1202
00:51:58,450 --> 00:52:01,960
We don't want to update those.

1203
00:52:01,960 --> 00:52:04,230
OK this is BFS in essence.

1204
00:52:04,230 --> 00:52:05,960
One question.

1205
00:52:05,960 --> 00:52:08,130
Between Facebook and
Twitter, which one's directed

1206
00:52:08,130 --> 00:52:09,255
and which one's undirected?

1207
00:52:09,255 --> 00:52:12,670

1208
00:52:12,670 --> 00:52:15,020
AUDIENCE: Facebook
is undirected.

1209
00:52:15,020 --> 00:52:15,920
PROFESSOR: OK.

1210
00:52:15,920 --> 00:52:23,970
Facebook is undirected.

1211
00:52:23,970 --> 00:52:27,662
Why is it undirected?

1212
00:52:27,662 --> 00:52:28,690
AUDIENCE: [INAUDIBLE].

1213
00:52:28,690 --> 00:52:29,606
AUDIENCE: [INAUDIBLE].

1214
00:52:29,606 --> 00:52:33,717

1215
00:52:33,717 --> 00:52:36,050
AUDIENCE: When you follow
someone they don't necessarily

1216
00:52:36,050 --> 00:52:37,177
follow you.

1217
00:52:37,177 --> 00:52:37,760
PROFESSOR: OK.

1218
00:52:37,760 --> 00:52:38,843
So this is Twitter, right?

1219
00:52:38,843 --> 00:52:42,630

1220
00:52:42,630 --> 00:52:49,430
Twitter, directed
because of follows.

1221
00:52:49,430 --> 00:52:50,980
Has anyone used
Facebook recently?

1222
00:52:50,980 --> 00:52:53,460
Did you guys see
there's a new option?

1223
00:52:53,460 --> 00:52:56,440
AUDIENCE: The little
scroll bar on the side?

1224
00:52:56,440 --> 00:52:57,700
PROFESSOR: Subscribers.

1225
00:52:57,700 --> 00:52:59,170
AUDIENCE: Oh, ya.

1226
00:52:59,170 --> 00:53:01,455
PROFESSOR: OK, so how
do subscribers work?

1227
00:53:01,455 --> 00:53:02,455
AUDIENCE: You subscribe.

1228
00:53:02,455 --> 00:53:04,395
It's like google plus.

1229
00:53:04,395 --> 00:53:05,337
[LAUGHTER]

1230
00:53:05,337 --> 00:53:05,920
PROFESSOR: OK.

1231
00:53:05,920 --> 00:53:07,220
Directed are undirected?

1232
00:53:07,220 --> 00:53:10,231
If I subscribe to you do
you have to subscribe to me?

1233
00:53:10,231 --> 00:53:11,022
AUDIENCE: Directed.

1234
00:53:11,022 --> 00:53:20,410

1235
00:53:20,410 --> 00:53:22,671
PROFESSOR: So which one is it?

1236
00:53:22,671 --> 00:53:24,754
AUDIENCE: I guess Facebook
is kind of directed now

1237
00:53:24,754 --> 00:53:28,210
because you can
unsubscribe from people.

1238
00:53:28,210 --> 00:53:30,410
PROFESSOR: Is it?

1239
00:53:30,410 --> 00:53:33,320
So Facebook has
two graphs in it.

1240
00:53:33,320 --> 00:53:35,020
They happen to have
the same vertices.

1241
00:53:35,020 --> 00:53:37,740
The people are the
vertices in both graphs.

1242
00:53:37,740 --> 00:53:43,350
But the friends relationship
defines an undirected graph.

1243
00:53:43,350 --> 00:53:46,750
The subscribers relationship
defines a directed graph.

1244
00:53:46,750 --> 00:53:48,499
The graphs are
completely different.

1245
00:53:48,499 --> 00:53:49,540
And there are two graphs.

1246
00:53:49,540 --> 00:53:52,364
That's the right way
to reason about them.

1247
00:53:52,364 --> 00:53:53,780
that's why it was
slightly tricky.

1248
00:53:53,780 --> 00:53:57,040

1249
00:53:57,040 --> 00:54:00,180
Can someone think of a cool
way to use BFS on Facebook?

1250
00:54:00,180 --> 00:54:03,470

1251
00:54:03,470 --> 00:54:05,124
AUDIENCE: That's
networks, right?

1252
00:54:05,124 --> 00:54:07,290
Figuring out how many people
are in the first degree

1253
00:54:07,290 --> 00:54:09,260
or second degree.

1254
00:54:09,260 --> 00:54:10,632
MySpace was really into that.

1255
00:54:10,632 --> 00:54:12,340
PROFESSOR: Lincoln
also does that, right?

1256
00:54:12,340 --> 00:54:13,721
How many people
are your friends?

1257
00:54:13,721 --> 00:54:15,470
How many people are
your friend's friends?

1258
00:54:15,470 --> 00:54:17,730
So and so forth.

1259
00:54:17,730 --> 00:54:21,486
Now suppose you want to
get to someone in Facebook

1260
00:54:21,486 --> 00:54:22,860
and you don't know
them directly.

1261
00:54:22,860 --> 00:54:25,190
They're not your friends.

1262
00:54:25,190 --> 00:54:27,170
Presumably, you
want to get to them

1263
00:54:27,170 --> 00:54:29,240
through the minimum
amount of effort.

1264
00:54:29,240 --> 00:54:32,610
So you want to see do you
have a friend that knows them?

1265
00:54:32,610 --> 00:54:34,010
If not, do you
have a friend that

1266
00:54:34,010 --> 00:54:35,130
knows a friend that knows them?

1267
00:54:35,130 --> 00:54:36,590
Do you have a friend
that knows a friend that

1268
00:54:36,590 --> 00:54:37,881
knows a friend that knows them?

1269
00:54:37,881 --> 00:54:38,780
So and so forth.

1270
00:54:38,780 --> 00:54:40,957
So BFS will give you
that minimum path.

1271
00:54:40,957 --> 00:54:43,711

1272
00:54:43,711 --> 00:54:44,210
OK.

1273
00:54:44,210 --> 00:54:46,144
do the graphs make sense?

1274
00:54:46,144 --> 00:54:47,560
So by the way, the
BFS on Facebook

1275
00:54:47,560 --> 00:54:50,150
is just the beginning
of a ton of cool things

1276
00:54:50,150 --> 00:54:51,833
you can with graph algorithms.

1277
00:54:51,833 --> 00:54:52,333