1
00:00:00,000 --> 00:00:02,743


2
00:00:02,743 --> 00:00:04,410
CARTER ZENKE: All right, hello everyone.

3
00:00:04,410 --> 00:00:07,730
Welcome to our first test review
session of the fall semester.

4
00:00:07,730 --> 00:00:08,480
My name is Carter.

5
00:00:08,480 --> 00:00:10,400
I'm [INAUDIBLE]
preceptor, joined also by

6
00:00:10,400 --> 00:00:12,680
Phyllis, one of our
head course assistants.

7
00:00:12,680 --> 00:00:15,080
Super excited to be here
today and to help you all

8
00:00:15,080 --> 00:00:17,690
go through some of the key
concepts from this test.

9
00:00:17,690 --> 00:00:19,820
It is just about 7
o'clock, which is the time

10
00:00:19,820 --> 00:00:21,800
we said we would start at the session.

11
00:00:21,800 --> 00:00:22,898
Or is it?

12
00:00:22,898 --> 00:00:25,690
Because on the course website, we
said that we start at November 10

13
00:00:25,690 --> 00:00:28,730
at 7:00 PM in quotes,
direct characters, right?

14
00:00:28,730 --> 00:00:31,943
But on your computer, I would
argue that actually this

15
00:00:31,943 --> 00:00:33,110
isn't what actually went on.

16
00:00:33,110 --> 00:00:35,027
We actually have this
number in your computer,

17
00:00:35,027 --> 00:00:37,070
this Unix time representing
how many seconds

18
00:00:37,070 --> 00:00:39,140
have passed since January 1, 1970.

19
00:00:39,140 --> 00:00:42,810
So what time is it really is a great
question that is going on right here.

20
00:00:42,810 --> 00:00:46,430
So if we're trying to represent
this session start time right now,

21
00:00:46,430 --> 00:00:49,723
7:00 PM on November 10th, well,
I might say that this string

22
00:00:49,723 --> 00:00:51,140
is the best way to represent that.

23
00:00:51,140 --> 00:00:54,473
Like I could send an email, I could send
a text that is saying November 10, 7:00

24
00:00:54,473 --> 00:00:55,760
PM, those actual characters.

25
00:00:55,760 --> 00:00:57,510
But Phyllis on the
other hand, might say,

26
00:00:57,510 --> 00:00:59,720
well, this integer is
actually a better way

27
00:00:59,720 --> 00:01:03,510
to actually represent this because
maybe it's more clean, right?

28
00:01:03,510 --> 00:01:05,900
But in talking about
these different ways

29
00:01:05,900 --> 00:01:09,840
to represent this actual date, this
actual time that we're in right now,

30
00:01:09,840 --> 00:01:12,920
well these would lead us to
different binary representations

31
00:01:12,920 --> 00:01:14,270
of this same date.

32
00:01:14,270 --> 00:01:16,730
So in the chat if you'd
like, how would this

33
00:01:16,730 --> 00:01:20,660
actually change our
representation of this date,

34
00:01:20,660 --> 00:01:24,710
depending on if we held this date
as a string or as an integer?

35
00:01:24,710 --> 00:01:27,680
What should we be thinking
about as we go through and write

36
00:01:27,680 --> 00:01:31,550
some of these dates in actual
machine language, or machine code,

37
00:01:31,550 --> 00:01:33,553
this language computer speak?

38
00:01:33,553 --> 00:01:36,470
And go ahead and put some answers
in the chat based on what you think.

39
00:01:36,470 --> 00:01:41,970


40
00:01:41,970 --> 00:01:44,145
So one thing I'm seeing
is that if we chose

41
00:01:44,145 --> 00:01:47,430
to represent this date
as a string, well,

42
00:01:47,430 --> 00:01:51,900
we'd be dealing with maybe ASCII
characters, right, ASCII characters

43
00:01:51,900 --> 00:01:55,530
where each character would have its
own code that we could put into binary.

44
00:01:55,530 --> 00:01:59,250
So for example, if I were to look at
this string notation, or this string

45
00:01:59,250 --> 00:02:03,480
representation of this date,
well, that N there would be--

46
00:02:03,480 --> 00:02:09,000
not sure the ASCII code actually,
but the binary for that is 0100110.

47
00:02:09,000 --> 00:02:10,919
And I looked that up earlier, right?

48
00:02:10,919 --> 00:02:14,220
But this would be the
binary representation

49
00:02:14,220 --> 00:02:17,490
of the ASCII number for N in November.

50
00:02:17,490 --> 00:02:20,790
Now, further we go on to the o
and we might say, well, that's o--

51
00:02:20,790 --> 00:02:26,670
lowercase o specifically-- is 01101111.

52
00:02:26,670 --> 00:02:29,250
And that again is the
binary representation

53
00:02:29,250 --> 00:02:33,510
for the ASCII value of this o character.

54
00:02:33,510 --> 00:02:36,210
But for this integer, right,
this is a whole different way

55
00:02:36,210 --> 00:02:37,450
representing that date.

56
00:02:37,450 --> 00:02:39,870
And so we might have to actually
use something different.

57
00:02:39,870 --> 00:02:46,350
Here we have this integer that is
actually going to be a 32-bit number,

58
00:02:46,350 --> 00:02:54,120
or represented with 32 bits, or in
this case, let's see, 4 bytes right?

59
00:02:54,120 --> 00:02:55,380
So this would be--

60
00:02:55,380 --> 00:03:03,000
I don't type all of it out, but
0110000110011 and so on, all the way

61
00:03:03,000 --> 00:03:08,680
to having 32 bits that would show
off this entire integer number here.

62
00:03:08,680 --> 00:03:11,670
So on Stack Overflow I
found this question of,

63
00:03:11,670 --> 00:03:16,680
if 32-bit machines can only handle
numbers that go up to 2 to the 32,

64
00:03:16,680 --> 00:03:19,560
if we can only have numbers
represented with 32 bits,

65
00:03:19,560 --> 00:03:22,120
how come we can write
this number right here?

66
00:03:22,120 --> 00:03:24,090
This 1 trillion number, right?

67
00:03:24,090 --> 00:03:27,630
Well I hope looking at this shows
us that, well, actually we're

68
00:03:27,630 --> 00:03:30,000
typing in the ASCII
characters for this number

69
00:03:30,000 --> 00:03:32,582
and not necessarily storing
it in 32 bits, right?

70
00:03:32,582 --> 00:03:35,040
There's a difference between
representing things with ASCII

71
00:03:35,040 --> 00:03:38,020
and representing things
with actual numbers.

72
00:03:38,020 --> 00:03:40,320
So these are all questions
of representation,

73
00:03:40,320 --> 00:03:43,440
right, these issues of how we can
store numbers, how we can talk

74
00:03:43,440 --> 00:03:45,520
about numbers inside of a computer.

75
00:03:45,520 --> 00:03:49,290
But what happens when things might
go wrong with representation?

76
00:03:49,290 --> 00:03:51,690
That's a big theme from this
first week of the course.

77
00:03:51,690 --> 00:03:55,590
Well let's say we wanted to
add the year to our date,

78
00:03:55,590 --> 00:04:00,690
not just November 10, 7:00 PM,
but November 10, 7:00 PM, 2021.

79
00:04:00,690 --> 00:04:07,140
And we have 1,000 years until we're
going to change from 2000 to 3000

80
00:04:07,140 --> 00:04:10,620
or even hundreds years before
we change from 2020 to 2100,

81
00:04:10,620 --> 00:04:13,120
so I think we'll be safe
with just two digits, right?

82
00:04:13,120 --> 00:04:14,940
But as we go through--

83
00:04:14,940 --> 00:04:19,140
if we start with 21, maybe next
year 2022, and so on, well we

84
00:04:19,140 --> 00:04:22,740
could get all the way to 98, and 99.

85
00:04:22,740 --> 00:04:25,800
And then eventually, right,
we would hit this point

86
00:04:25,800 --> 00:04:28,050
where we can't count any higher.

87
00:04:28,050 --> 00:04:33,570
And we'd get this overflow, this
transition from 99 to 00, right?

88
00:04:33,570 --> 00:04:36,240
Because if we added 1
to the 9 on the right,

89
00:04:36,240 --> 00:04:38,280
we'd have to carry a 1,
which would make it a 0,

90
00:04:38,280 --> 00:04:40,210
and then add this other 0 to their side.

91
00:04:40,210 --> 00:04:45,330
And so of course we can only count
up to 99, but then if we get to 00,

92
00:04:45,330 --> 00:04:47,520
what year are we talking
about anymore, right?

93
00:04:47,520 --> 00:04:49,410
Are we talking about 2000?

94
00:04:49,410 --> 00:04:51,270
Are we talking about 2100?

95
00:04:51,270 --> 00:04:52,360
We don't know anymore.

96
00:04:52,360 --> 00:04:55,680
And so we didn't have enough information
to represent all of the possible years

97
00:04:55,680 --> 00:04:58,300
we could be talking about here.

98
00:04:58,300 --> 00:05:00,190
Now, that again is a
question of overflow,

99
00:05:00,190 --> 00:05:04,540
this idea of running out of space
to store the information that we're

100
00:05:04,540 --> 00:05:06,820
trying to store in this case.

101
00:05:06,820 --> 00:05:11,950
Now the Unix time we talked
about earlier sort of actually

102
00:05:11,950 --> 00:05:16,750
came in to play here and when we were
talking about the January 1, 2000 Y2K

103
00:05:16,750 --> 00:05:17,260
bug, right?

104
00:05:17,260 --> 00:05:24,060
We went from basically two digits to
store the year, from 1999 to 2000,

105
00:05:24,060 --> 00:05:25,070
flipping back over.

106
00:05:25,070 --> 00:05:31,370
But again, this was sort of going
into 1900 and not 2000 in this case.

107
00:05:31,370 --> 00:05:34,030
But of course, we've since
sort of developed better ways

108
00:05:34,030 --> 00:05:37,630
to represent numbers now, and
we have these 32-bit integers

109
00:05:37,630 --> 00:05:39,350
that can count even higher.

110
00:05:39,350 --> 00:05:44,140
But of course, we're running the same
problem later on on 19 of January 2038.

111
00:05:44,140 --> 00:05:47,770
So maybe the key here is to
use these 64-bit numbers that

112
00:05:47,770 --> 00:05:51,250
would give us much more space to
represent all kinds of possible times

113
00:05:51,250 --> 00:05:52,180
here.

114
00:05:52,180 --> 00:05:54,970
But again, this gets
at this idea of having

115
00:05:54,970 --> 00:05:59,130
a certain amount of space in the
computer to represent our information.

116
00:05:59,130 --> 00:06:01,640
So certainly welcome here to
pose questions in the chat

117
00:06:01,640 --> 00:06:03,830
if you have anything you want to talk
about based on the representation

118
00:06:03,830 --> 00:06:07,400
question before we move on to some of
these topics on programming languages

119
00:06:07,400 --> 00:06:08,358
and so on.

120
00:06:08,358 --> 00:06:11,525
I'll just wait out a minute here for
some questions to come in via the chat.

121
00:06:11,525 --> 00:06:23,170


122
00:06:23,170 --> 00:06:25,518
All right, so I don't see
any questions coming in.

123
00:06:25,518 --> 00:06:28,060
But definitely feel free to
message them to me or to Phyllis,

124
00:06:28,060 --> 00:06:31,540
and we'll do our best
to respond to them live.

125
00:06:31,540 --> 00:06:32,720
Ah, I see a question here.

126
00:06:32,720 --> 00:06:34,330
So what is stack overflow?

127
00:06:34,330 --> 00:06:37,150
Right, there's this idea
of going back to overflow.

128
00:06:37,150 --> 00:06:41,080
Well we were talking about overflow
in terms of representation of numbers,

129
00:06:41,080 --> 00:06:42,490
representation of digits here.

130
00:06:42,490 --> 00:06:46,540
But stack overflow can be
somewhat similar in the sense

131
00:06:46,540 --> 00:06:49,450
that when we call a function
in our computer, right,

132
00:06:49,450 --> 00:06:52,720
we keep putting the computer's
memory higher and higher

133
00:06:52,720 --> 00:06:57,270
on that stack that we talked about
earlier, in week probably four or so.

134
00:06:57,270 --> 00:06:59,500
And as we keep calling
more and more functions,

135
00:06:59,500 --> 00:07:01,240
we keep adding more and more memory.

136
00:07:01,240 --> 00:07:04,457
Well, the stack only has a
finite amount of space, right?

137
00:07:04,457 --> 00:07:06,790
So if we were to climb all
the way to top of that stack,

138
00:07:06,790 --> 00:07:09,787
you eventually reach the top of
that and run out of space there.

139
00:07:09,787 --> 00:07:12,370
So that is what's called stack
overflow, the same idea of sort

140
00:07:12,370 --> 00:07:16,180
of running out of space to store
the information we need to store.

141
00:07:16,180 --> 00:07:20,170
And another question is saying, can
an integer be represented high as 2

142
00:07:20,170 --> 00:07:22,300
to the 31 minus 1?

143
00:07:22,300 --> 00:07:25,990
And in this case,
that's actually correct.

144
00:07:25,990 --> 00:07:30,520
If we have a 32-bit
integer, right, let's see--

145
00:07:30,520 --> 00:07:32,620
I don't think I have an
example of 32 bits here.

146
00:07:32,620 --> 00:07:34,330
I can go ahead and type one in.

147
00:07:34,330 --> 00:07:39,520
So here we left off at 11, and
let's go ahead and just add--

148
00:07:39,520 --> 00:07:41,950
let's say that's about 32 bits, right?

149
00:07:41,950 --> 00:07:45,400
We could theoretically represent
numbers that can go as high as 2

150
00:07:45,400 --> 00:07:49,660
to the 31 minus 1 if we were
only caring about numbers

151
00:07:49,660 --> 00:07:54,340
that were positive or unsigned, they
don't have a positive or negative sign

152
00:07:54,340 --> 00:07:55,570
in front of them.

153
00:07:55,570 --> 00:07:58,660
If we wanted to represent both
positive and negative numbers,

154
00:07:58,660 --> 00:08:05,455
we'd only have half that
much room to go away from 0,

155
00:08:05,455 --> 00:08:07,780
right, because we're sort of
dividing our space in half

156
00:08:07,780 --> 00:08:10,690
as we include both negative
and positive numbers.

157
00:08:10,690 --> 00:08:13,448


158
00:08:13,448 --> 00:08:15,490
Another question about
stack overflow I'm seeing,

159
00:08:15,490 --> 00:08:17,830
how would there is a
stack overflow error?

160
00:08:17,830 --> 00:08:20,290
And would it say that there is one?

161
00:08:20,290 --> 00:08:23,733
I think most compilers would tell you if
there is a stack overflow error, right?

162
00:08:23,733 --> 00:08:25,900
They're going to be running
your code, going through

163
00:08:25,900 --> 00:08:29,260
and most cases, probably a
recursion issue would happen.

164
00:08:29,260 --> 00:08:31,510
And so it can tell you, look,
we've run out of memory.

165
00:08:31,510 --> 00:08:32,802
This is a stack overflow error.

166
00:08:32,802 --> 00:08:39,260


167
00:08:39,260 --> 00:08:41,479
And certainly feel free to
take other questions here.

168
00:08:41,479 --> 00:08:51,330


169
00:08:51,330 --> 00:08:52,640
All right.

170
00:08:52,640 --> 00:08:56,690
So, going back to this idea
of running out of time.

171
00:08:56,690 --> 00:09:01,190
We have certainly enough time
before this January 19, 2038

172
00:09:01,190 --> 00:09:03,260
to think about how we
can address this issue.

173
00:09:03,260 --> 00:09:05,600
And maybe part of that
would involve thinking

174
00:09:05,600 --> 00:09:09,780
more deeply about programming languages,
how they store data, and so on.

175
00:09:09,780 --> 00:09:12,290
So when we're talking about
programming languages,

176
00:09:12,290 --> 00:09:16,010
one of the very first things that come
to mind is this idea of a variable,

177
00:09:16,010 --> 00:09:17,870
storing information, right?

178
00:09:17,870 --> 00:09:21,710
In this case, we have
a date, in this case

179
00:09:21,710 --> 00:09:25,190
is pointing to this location in
memory of this actual integer

180
00:09:25,190 --> 00:09:27,320
representation of that date.

181
00:09:27,320 --> 00:09:29,210
But how did it get there?

182
00:09:29,210 --> 00:09:32,090
Well that's where assignment in a
programming language can come in.

183
00:09:32,090 --> 00:09:35,270
We have this equal sign, which
is this assignment operator that

184
00:09:35,270 --> 00:09:39,200
can take whatever you put on the right
and store it in a name sort of space

185
00:09:39,200 --> 00:09:39,790
on the left.

186
00:09:39,790 --> 00:09:43,290
So here we have this high number
that's representing the date right now

187
00:09:43,290 --> 00:09:47,690
and storing that in this location
that we're calling date, right?

188
00:09:47,690 --> 00:09:49,460
Now if we want to keep
track of the date,

189
00:09:49,460 --> 00:09:52,400
we could keep assigning new
numbers to this date location.

190
00:09:52,400 --> 00:09:55,480
We could go ahead and give
it the next second on,

191
00:09:55,480 --> 00:09:58,890
the next second on, and then so on.

192
00:09:58,890 --> 00:10:01,755
But a better way to do that
is with these operators

193
00:10:01,755 --> 00:10:03,380
that are part of programming languages.

194
00:10:03,380 --> 00:10:06,230
And in this case, we have an
operator that is just plus, right?

195
00:10:06,230 --> 00:10:12,180
We can add to current values that we
have stored in our computer's memory.

196
00:10:12,180 --> 00:10:15,598
So here we have this operator
that is first looking at date,

197
00:10:15,598 --> 00:10:18,140
the variable that is stored,
reading from right to left here.

198
00:10:18,140 --> 00:10:21,180
And it's going to add
a 1 to this location,

199
00:10:21,180 --> 00:10:23,460
so I might go ahead and add one here.

200
00:10:23,460 --> 00:10:27,470
And it's going to restore that
value in that same location there.

201
00:10:27,470 --> 00:10:29,940
So these operators allow
us to take certain data,

202
00:10:29,940 --> 00:10:33,880
manipulate it, and store it
back in the same location.

203
00:10:33,880 --> 00:10:36,970
But what if we also wanted to
ask questions about our data,

204
00:10:36,970 --> 00:10:40,937
right, not just store things,
and add to them, and so on?

205
00:10:40,937 --> 00:10:42,770
Well, that's where
conditionals can come in.

206
00:10:42,770 --> 00:10:48,100
And we saw these both in Python, in C,
and even in JavaScript a little bit.

207
00:10:48,100 --> 00:10:51,230
Asking questions of our data,
is date greater than zero?

208
00:10:51,230 --> 00:10:52,850
Well, certainly it is in this case.

209
00:10:52,850 --> 00:10:55,510
So we'd get back this value of true.

210
00:10:55,510 --> 00:10:59,110
Or is date greater than maybe
2 million, or 2 trillion?

211
00:10:59,110 --> 00:11:01,190
And in this case, well, it's not.

212
00:11:01,190 --> 00:11:02,690
And so we get back this false value.

213
00:11:02,690 --> 00:11:06,100
So conditionals are what help us
sort of ask questions of our data

214
00:11:06,100 --> 00:11:09,190
and get back answers that are
either yes or no, true or false,

215
00:11:09,190 --> 00:11:14,410
these Boolean values but we can
talk about in computer programming.

216
00:11:14,410 --> 00:11:17,590
Now that's OK, right?

217
00:11:17,590 --> 00:11:21,220
But what if we have something
that we want to do that's

218
00:11:21,220 --> 00:11:23,060
not just the single operation.

219
00:11:23,060 --> 00:11:26,500
So if we go back to our
operators here, we've added 1

220
00:11:26,500 --> 00:11:29,590
but since time keeps
moving, time keeps going on,

221
00:11:29,590 --> 00:11:32,410
we want actually be able
to keep updating this time.

222
00:11:32,410 --> 00:11:35,480
That's where this idea
of loops come in handy.

223
00:11:35,480 --> 00:11:38,410
So here we have this sort of
English sentence of saying,

224
00:11:38,410 --> 00:11:44,090
I want to do something until the date
is less than, let's say 2 trillion here.

225
00:11:44,090 --> 00:11:49,370
And again, we're counting seconds
from January 1, 1970 in this case.

226
00:11:49,370 --> 00:11:53,688
So this combination of conditions,
or this implementation of conditions,

227
00:11:53,688 --> 00:11:55,480
allows us to define
this loop that can help

228
00:11:55,480 --> 00:12:02,430
us do something until this date
reaches a certain state of being true.

229
00:12:02,430 --> 00:12:06,980
So here is basically what
we're trying to implement

230
00:12:06,980 --> 00:12:08,820
in the terms of a while loop, right?

231
00:12:08,820 --> 00:12:12,830
We saw that this while loop
can help us do something

232
00:12:12,830 --> 00:12:17,060
until a certain condition
is no longer true, right?

233
00:12:17,060 --> 00:12:19,340
While something is true, we'll do that.

234
00:12:19,340 --> 00:12:23,210
But when it's no longer true, let's
go ahead and break out of this loop

235
00:12:23,210 --> 00:12:25,770
and not do it anymore.

236
00:12:25,770 --> 00:12:28,820
Now, of course, there's
more than a while loop.

237
00:12:28,820 --> 00:12:32,870
But most loops actually come
from this very simple collection

238
00:12:32,870 --> 00:12:34,440
of conditions and these loops here.

239
00:12:34,440 --> 00:12:37,460
So if I go here to
this next kind of loop,

240
00:12:37,460 --> 00:12:40,340
here I'm doing a few different
things at once, right?

241
00:12:40,340 --> 00:12:43,340
I'm defining a certain value for date.

242
00:12:43,340 --> 00:12:48,980
I'm asking, is date less than,
let's see, 2 trillion here?

243
00:12:48,980 --> 00:12:52,370
And if it is, I want to do
something, and at the very end

244
00:12:52,370 --> 00:12:53,900
I want to add 1 to our date.

245
00:12:53,900 --> 00:12:56,900
So here we're combining assignment
in that first line there.

246
00:12:56,900 --> 00:13:00,980
We're adding conditionals in that
second line, and on that fourth line,

247
00:13:00,980 --> 00:13:04,490
we're working with operators
to add 1 to our date, right?

248
00:13:04,490 --> 00:13:07,548
But this is pretty much
equivalent to a for loop, right?

249
00:13:07,548 --> 00:13:09,590
We could sort of combine
all this into one place,

250
00:13:09,590 --> 00:13:12,200
which is what Python
and C allow us to do

251
00:13:12,200 --> 00:13:14,340
when we have these different for loops.

252
00:13:14,340 --> 00:13:17,150
So again, thinking about
programming languages here,

253
00:13:17,150 --> 00:13:21,350
the important thing is not so much
the individual syntax of Python,

254
00:13:21,350 --> 00:13:26,060
or C, or JavaScript, and so on, but
more this idea of loops and building

255
00:13:26,060 --> 00:13:28,325
from those loops, all
the kinds of functions

256
00:13:28,325 --> 00:13:31,470
that programming languages can have.

257
00:13:31,470 --> 00:13:35,180
So thinking about this and using these
as building blocks, a question for us

258
00:13:35,180 --> 00:13:38,300
in the chat is, you know, Phyllis
and I have developed this programming

259
00:13:38,300 --> 00:13:41,730
language that we've
sort of shown so far,

260
00:13:41,730 --> 00:13:43,582
but we've only added
this addition operator.

261
00:13:43,582 --> 00:13:46,790
I didn't show you subtraction, I didn't
show you division, or multiplication,

262
00:13:46,790 --> 00:13:48,800
but we actually want to be
able to multiply things.

263
00:13:48,800 --> 00:13:48,920
Right?

264
00:13:48,920 --> 00:13:51,500
We don't actually want to add
them, we want to multiply them.

265
00:13:51,500 --> 00:13:54,260
And so if we can have variables,
if we can have conditions,

266
00:13:54,260 --> 00:13:57,080
if we can have loops,
well, what constructs could

267
00:13:57,080 --> 00:13:59,660
we use to actually make
multiplication here?

268
00:13:59,660 --> 00:14:01,760
And I'll give you all
about two minutes to think

269
00:14:01,760 --> 00:14:04,820
in the chat about what kinds
of constructs from the past

270
00:14:04,820 --> 00:14:08,365
would we be able to use here to build
multiplication into our programming

271
00:14:08,365 --> 00:14:11,210
language, based on only the
building blocks we've had so far.

272
00:14:11,210 --> 00:14:14,603


273
00:14:14,603 --> 00:14:17,770
And I'll also look for questions as
well if you would like to ask those too.

274
00:14:17,770 --> 00:14:32,028


275
00:14:32,028 --> 00:14:33,820
All right, I'm seeing
some answers come in.

276
00:14:33,820 --> 00:14:36,925
I'll give folks about a minute more.

277
00:14:36,925 --> 00:14:51,740


278
00:14:51,740 --> 00:14:53,960
All right, I'm seeing some more answers.

279
00:14:53,960 --> 00:14:56,960
And a lot of these are
talking about addition, right,

280
00:14:56,960 --> 00:14:58,520
we know we can do addition.

281
00:14:58,520 --> 00:15:01,640
And they're also talking
about loops, right?

282
00:15:01,640 --> 00:15:05,180
If we sort of think about
it, multiplication is really

283
00:15:05,180 --> 00:15:07,220
just addition but looped, right?

284
00:15:07,220 --> 00:15:14,540
If we want to say do 5 times 5,
we would add 5 together 5 times.

285
00:15:14,540 --> 00:15:18,800
5 plus 5 plus 5 plus 5 plus 5.

286
00:15:18,800 --> 00:15:24,620
And so in this case, we could
actually have basically a few more

287
00:15:24,620 --> 00:15:26,930
variables here that
could help us define,

288
00:15:26,930 --> 00:15:29,580
are we all the way
through our number or not?

289
00:15:29,580 --> 00:15:32,720
But basically, this idea of using
loops to sort of add more to this some

290
00:15:32,720 --> 00:15:35,620
that we're making for multiplication.

291
00:15:35,620 --> 00:15:36,820
All right.

292
00:15:36,820 --> 00:15:38,980
And again, any other
questions here before we

293
00:15:38,980 --> 00:15:43,195
move on to functions and talking about
how functions and programs might work?

294
00:15:43,195 --> 00:15:54,420


295
00:15:54,420 --> 00:15:56,670
Let's see.

296
00:15:56,670 --> 00:15:58,050
All right.

297
00:15:58,050 --> 00:16:00,780
I'm seeing a few, and some
will come back to even later.

298
00:16:00,780 --> 00:16:01,810
All right.

299
00:16:01,810 --> 00:16:04,962
So let's go ahead and
move on to functions.

300
00:16:04,962 --> 00:16:07,920
Now, there's this idea that we saw
at the very beginning of the course,

301
00:16:07,920 --> 00:16:12,420
as functions as these black boxes that
take inputs and then give us outputs,

302
00:16:12,420 --> 00:16:13,410
right?

303
00:16:13,410 --> 00:16:15,690
But as I hope we've seen,
these functions actually

304
00:16:15,690 --> 00:16:17,130
have pretty predictable elements.

305
00:16:17,130 --> 00:16:18,838
We can actually use
these building blocks

306
00:16:18,838 --> 00:16:22,690
to make functions, including variables,
assignments, operations, conditionals,

307
00:16:22,690 --> 00:16:23,190
and loops.

308
00:16:23,190 --> 00:16:25,590
These are all parts of
functions and building blocks

309
00:16:25,590 --> 00:16:28,720
we can use to make our own functions.

310
00:16:28,720 --> 00:16:32,280
Now, when you're writing your
functions in Python for example,

311
00:16:32,280 --> 00:16:35,970
you use syntax like this
where you say, define

312
00:16:35,970 --> 00:16:41,340
a function called add time that
takes two inputs, time and addition,

313
00:16:41,340 --> 00:16:45,040
and then gives us back or
outputs time plus addition.

314
00:16:45,040 --> 00:16:48,060
So here I could give a certain
time, like the start of the seminar,

315
00:16:48,060 --> 00:16:51,570
add maybe 30 minutes to it and
we'd arrive at maybe the time

316
00:16:51,570 --> 00:16:53,610
that we're at right about now, right?

317
00:16:53,610 --> 00:16:56,460
But the key thing here I
want to highlight for you all

318
00:16:56,460 --> 00:16:59,880
is not necessarily the
Python syntax, but this idea

319
00:16:59,880 --> 00:17:03,130
of these inputs and these return values.

320
00:17:03,130 --> 00:17:06,420
So here we have again, our
inputs of time and addition,

321
00:17:06,420 --> 00:17:08,790
and this return statement
giving us back a value we

322
00:17:08,790 --> 00:17:11,730
can use later on in our program, right?

323
00:17:11,730 --> 00:17:15,040
So instead of inputs and
outputs, maybe more specifically,

324
00:17:15,040 --> 00:17:17,760
we could say functions
take arguments, again,

325
00:17:17,760 --> 00:17:20,220
that we've defined here
like time and addition.

326
00:17:20,220 --> 00:17:23,460
And they give back return
values that we can say

327
00:17:23,460 --> 00:17:25,740
or we can name with these
return functions that

328
00:17:25,740 --> 00:17:31,037
occur in most any programming language,
even in C, in Python, and so on.

329
00:17:31,037 --> 00:17:33,370
And these return values are
different from side effects,

330
00:17:33,370 --> 00:17:36,540
for example, which are things
of happen as the function runs.

331
00:17:36,540 --> 00:17:40,020
These return values are actually
data we can use and, later on,

332
00:17:40,020 --> 00:17:45,910
incorporate into our program that these
functions give back to us over time.

333
00:17:45,910 --> 00:17:50,970
Now, programs themselves can be seen
in a very similar way when we're

334
00:17:50,970 --> 00:17:53,370
writing programs, especially later on.

335
00:17:53,370 --> 00:17:56,760
In weeks 2 and 3, we were talking
about giving command line arguments

336
00:17:56,760 --> 00:17:58,110
to our programs.

337
00:17:58,110 --> 00:18:02,160
Well, in Python, defining
the main part of our program

338
00:18:02,160 --> 00:18:04,020
is very similar to defining a function.

339
00:18:04,020 --> 00:18:06,730
We have this main function
that is our program.

340
00:18:06,730 --> 00:18:10,470
And in this case, you'll see
where we could sys.argv and so

341
00:18:10,470 --> 00:18:12,080
on to get the command line arguments.

342
00:18:12,080 --> 00:18:14,580
But we have this very similar
value of returning something--

343
00:18:14,580 --> 00:18:18,390
in this case, a status code to say,
hey, we were successful at returning 0

344
00:18:18,390 --> 00:18:21,370
or returning 1 in those cases.

345
00:18:21,370 --> 00:18:23,930
So programs can be seen as a
more general case of functions.

346
00:18:23,930 --> 00:18:25,180
They are functions themselves.

347
00:18:25,180 --> 00:18:27,555
They take command line arguments,
which are their inputs.

348
00:18:27,555 --> 00:18:31,710
And they give us status
codes as their outputs.

349
00:18:31,710 --> 00:18:35,970
And so what questions are there
on functions and algorithms

350
00:18:35,970 --> 00:18:38,060
so far-- before we move
on to algorithms, that is?

351
00:18:38,060 --> 00:18:45,350


352
00:18:45,350 --> 00:18:47,170
So good question, what's a status code?

353
00:18:47,170 --> 00:18:53,860
So earlier on in our programs,
we'd talk about giving

354
00:18:53,860 --> 00:18:55,750
a program a certain number of inputs.

355
00:18:55,750 --> 00:18:59,080
I believe for Cesar,
for example, we were

356
00:18:59,080 --> 00:19:01,630
trying to give it maybe one
command line argument that

357
00:19:01,630 --> 00:19:06,820
said dot slash Cesar, the number of
steps we wanted to rotate our key.

358
00:19:06,820 --> 00:19:11,260
So a status code can tell us, did
our program function as we intended

359
00:19:11,260 --> 00:19:13,658
or did the user use our
program as intended.

360
00:19:13,658 --> 00:19:16,450
If we didn't give Cesar the right
number of command line arguments,

361
00:19:16,450 --> 00:19:19,687
we might return 2 or we might
return 3 to symbolize-- hey,

362
00:19:19,687 --> 00:19:20,770
this is actually not here.

363
00:19:20,770 --> 00:19:22,330
You're supposed to use this program.

364
00:19:22,330 --> 00:19:24,620
And later on, thinking
about web programming

365
00:19:24,620 --> 00:19:28,420
and talking about HTTP 404
errors, These are basically

366
00:19:28,420 --> 00:19:32,298
numbers that give us a clue as to
what happened when our program ran.

367
00:19:32,298 --> 00:19:34,090
And so these are the
outputs of our program

368
00:19:34,090 --> 00:19:37,330
that help us interpret what
happened as it finished running.

369
00:19:37,330 --> 00:19:45,240


370
00:19:45,240 --> 00:19:48,600
And I'll also pause here for a few
more questions before moving on.

371
00:19:48,600 --> 00:19:55,380


372
00:19:55,380 --> 00:19:58,770
So programs themselves
can implement algorithms.

373
00:19:58,770 --> 00:20:00,458
And that was the topic for week 3.

374
00:20:00,458 --> 00:20:02,250
Phyllis, here, is our
expert on algorithms.

375
00:20:02,250 --> 00:20:05,580
So I'll turn it over to Phyllis
to talk to us about algorithms.

376
00:20:05,580 --> 00:20:08,480


377
00:20:08,480 --> 00:20:10,470
PHYLLIS ZHANG: Cool.

378
00:20:10,470 --> 00:20:14,060
We'll talk about some algorithms
and have some fun thinking

379
00:20:14,060 --> 00:20:17,773
about how some algorithms--
how much time they'll take,

380
00:20:17,773 --> 00:20:18,940
how much space they'll take.

381
00:20:18,940 --> 00:20:20,030
It'll be quite fun.

382
00:20:20,030 --> 00:20:23,810


383
00:20:23,810 --> 00:20:28,070
So let's do a quick review about
some of the sorting algorithms you

384
00:20:28,070 --> 00:20:30,060
might remember from week 3.

385
00:20:30,060 --> 00:20:32,150
The three that we'll
be talking about today

386
00:20:32,150 --> 00:20:35,120
is bubble sort, selection
sort, and merge sort.

387
00:20:35,120 --> 00:20:40,040
We'll talk about their best case,
as well as their worst case,

388
00:20:40,040 --> 00:20:42,080
as well as how much
space they might take.

389
00:20:42,080 --> 00:20:45,560
So just as a quick
thing for bubble sort,

390
00:20:45,560 --> 00:20:47,940
let me come up with unsorted list.

391
00:20:47,940 --> 00:20:55,640
So I will do 5, 0, 1, 2, and 1.

392
00:20:55,640 --> 00:20:58,640
So what bubble sort will
do-- you might remember we

393
00:20:58,640 --> 00:21:00,560
take a look at the first two elements.

394
00:21:00,560 --> 00:21:04,200
And we notice that they are
not in the ascending order

395
00:21:04,200 --> 00:21:07,350
we would like them to be in, so
we're going to make a switch.

396
00:21:07,350 --> 00:21:12,230
And so we're going to switch
them to be 0, 5, 1, 2, and 1.

397
00:21:12,230 --> 00:21:14,900
And then, we look at the
two elements including

398
00:21:14,900 --> 00:21:17,653
this one that we just switched.

399
00:21:17,653 --> 00:21:19,820
And we notice they're not
in the right place either.

400
00:21:19,820 --> 00:21:25,730
So we're also going to switch
that over to 0, 1, 5, 2, 1.

401
00:21:25,730 --> 00:21:29,070
Similarly, we're going to
continue going down the line.

402
00:21:29,070 --> 00:21:33,530
So we switch those, the 5 and the 2.

403
00:21:33,530 --> 00:21:36,680
And then, finally, we're going
to switch that 1 and the 5.

404
00:21:36,680 --> 00:21:39,970


405
00:21:39,970 --> 00:21:42,680
So this was the very first iteration.

406
00:21:42,680 --> 00:21:47,480
And what we did here is, we went
through all n of these elements

407
00:21:47,480 --> 00:21:50,880
and compared it to another,
performing swaps as necessary.

408
00:21:50,880 --> 00:21:54,880
So for the first iteration,
we took n total steps.

409
00:21:54,880 --> 00:21:57,580
And notice that this is
not anywhere near sorted.

410
00:21:57,580 --> 00:22:00,280
This is actually not in
ascending order-- surprising.

411
00:22:00,280 --> 00:22:06,160
So this will continue until
this is in sorted order

412
00:22:06,160 --> 00:22:09,220
or whenever we stop making passes.

413
00:22:09,220 --> 00:22:15,310
And so can someone in a chat
tell me what the worst case time

414
00:22:15,310 --> 00:22:17,170
complexity for bubble sort might be?

415
00:22:17,170 --> 00:22:24,210


416
00:22:24,210 --> 00:22:26,110
We'll go with n square, that is correct.

417
00:22:26,110 --> 00:22:29,720
So we'll go with n square.

418
00:22:29,720 --> 00:22:35,810
And this is because we can't make a
total on the order of n total passes

419
00:22:35,810 --> 00:22:37,658
in order to--

420
00:22:37,658 --> 00:22:41,780
n total iterations to make sure
that this bubble is already sorted.

421
00:22:41,780 --> 00:22:44,600
And then, if we consider
the case where we have 1,

422
00:22:44,600 --> 00:22:48,860
2, 3, 4, 5, where it's already sorted--

423
00:22:48,860 --> 00:22:52,130
then, bubble sort will
only take one pass

424
00:22:52,130 --> 00:22:55,173
because it's going to go through
the entire thing and look--

425
00:22:55,173 --> 00:22:56,340
hey, this is already sorted.

426
00:22:56,340 --> 00:22:56,930
We're good.

427
00:22:56,930 --> 00:22:58,320
And then, it's going
to look at these two.

428
00:22:58,320 --> 00:22:59,630
It's going to be like,
oh, we're already sorted.

429
00:22:59,630 --> 00:23:00,200
We're good too.

430
00:23:00,200 --> 00:23:01,250
I'm going to look at these two.

431
00:23:01,250 --> 00:23:01,640
They're sorted.

432
00:23:01,640 --> 00:23:02,932
I'm going to look at these two.

433
00:23:02,932 --> 00:23:03,890
They're sorted.

434
00:23:03,890 --> 00:23:06,890
We did not make any
changes in this pass.

435
00:23:06,890 --> 00:23:07,880
We are good.

436
00:23:07,880 --> 00:23:10,550
And so bubbles sort is going to
be like, all right, I'm done.

437
00:23:10,550 --> 00:23:12,470
And we only made n total checks.

438
00:23:12,470 --> 00:23:17,280
And so this is only going to
take linear time for best case.

439
00:23:17,280 --> 00:23:20,850
So in the best case, we
do this big omega here.

440
00:23:20,850 --> 00:23:22,640
And it takes linear time.

441
00:23:22,640 --> 00:23:25,860


442
00:23:25,860 --> 00:23:30,060
And then, how much space does it take?

443
00:23:30,060 --> 00:23:30,880
Think about it.

444
00:23:30,880 --> 00:23:34,560
So in terms of space, if
we are just making swaps,

445
00:23:34,560 --> 00:23:36,570
we don't take up any extra space.

446
00:23:36,570 --> 00:23:39,712
We're saying, on the very
first thing here, for example,

447
00:23:39,712 --> 00:23:41,045
we're switching the 5 and the 0.

448
00:23:41,045 --> 00:23:43,050
If you remember, that's three lines.

449
00:23:43,050 --> 00:23:46,230
We maybe have a temporary integer.

450
00:23:46,230 --> 00:23:48,960
And that's all we need in
order to make these swaps.

451
00:23:48,960 --> 00:23:52,080
And since bubble sort is
just a bunch of these swaps,

452
00:23:52,080 --> 00:23:56,860
then the space complexity is just
going to be a bunch of constant things.

453
00:23:56,860 --> 00:24:01,420
And so the space complexity,
overall, is going to be constant.

454
00:24:01,420 --> 00:24:04,570
So we'll say this is going to
be the worst case is constant.

455
00:24:04,570 --> 00:24:07,100


456
00:24:07,100 --> 00:24:11,730
So For selection sort, we'll
use the exact same example.

457
00:24:11,730 --> 00:24:15,660
And we'll also use the first iteration.

458
00:24:15,660 --> 00:24:21,228
We'll have 5, 0, 1, 2, and 1.

459
00:24:21,228 --> 00:24:24,270
And so if you remember what selection
sort does is at every single point,

460
00:24:24,270 --> 00:24:27,880
it's going to look at the unsorted
part of the list and find the minimum.

461
00:24:27,880 --> 00:24:32,555
So I'm going to, in my first
iteration, go through the list

462
00:24:32,555 --> 00:24:33,430
and find the minimum.

463
00:24:33,430 --> 00:24:34,890
So I'm currently at 5.

464
00:24:34,890 --> 00:24:36,400
That's the smallest I have.

465
00:24:36,400 --> 00:24:38,227
I'm like, OK, the minimum is 5.

466
00:24:38,227 --> 00:24:39,810
And then, we're going to go look at 0.

467
00:24:39,810 --> 00:24:41,040
And 0 smaller than 5.

468
00:24:41,040 --> 00:24:43,657
So I'm like, OK, 0 is now the smallest.

469
00:24:43,657 --> 00:24:45,240
And then, we're going to go look at 1.

470
00:24:45,240 --> 00:24:46,500
It's not smaller than 0.

471
00:24:46,500 --> 00:24:48,450
Look at 2, it's also not smaller than 0.

472
00:24:48,450 --> 00:24:49,350
We'll look at 1.

473
00:24:49,350 --> 00:24:51,480
It's also not smaller than 0.

474
00:24:51,480 --> 00:24:55,080
And so then, selection sort is going to
note that this is the current smallest.

475
00:24:55,080 --> 00:24:58,340
And I'm going to swap it
with the beginning one.

476
00:24:58,340 --> 00:25:04,862
And so after the first iteration,
I'm going to get 0, 5, 1, 2, and 1.

477
00:25:04,862 --> 00:25:07,320
And so notice that we have to
look through the entire thing

478
00:25:07,320 --> 00:25:09,990
to figure out what was the minimum.

479
00:25:09,990 --> 00:25:13,320
And so in that case, since we
had to look to the entire thing

480
00:25:13,320 --> 00:25:17,110
to figure out what was the minimum,
this took n total comparisons.

481
00:25:17,110 --> 00:25:21,524


482
00:25:21,524 --> 00:25:27,360
And we'll have to do this every
single time for n total iterations

483
00:25:27,360 --> 00:25:29,020
because every single time--

484
00:25:29,020 --> 00:25:32,040
now that we're on a second iteration,
we have to find the new smallest

485
00:25:32,040 --> 00:25:35,370
and move it here until we get to
the very end, the n-th one who,

486
00:25:35,370 --> 00:25:37,760
we'll know that is the largest one.

487
00:25:37,760 --> 00:25:42,040
So the worst case for selection sort,
you might remember, is O of n squared.

488
00:25:42,040 --> 00:25:45,190
And does someone want
to send me, in the chat,

489
00:25:45,190 --> 00:25:47,860
with the best case
for selection sort is?

490
00:25:47,860 --> 00:25:56,210


491
00:25:56,210 --> 00:25:57,200
Awesome, yes.

492
00:25:57,200 --> 00:25:59,390
It is n square.

493
00:25:59,390 --> 00:26:02,750
And it's n squared
because even though it's

494
00:26:02,750 --> 00:26:06,240
in sorted order, every single time, we
still have to go look for the smallest.

495
00:26:06,240 --> 00:26:08,157
So we still have to go
through the whole thing

496
00:26:08,157 --> 00:26:10,340
to make sure that value is the smallest.

497
00:26:10,340 --> 00:26:16,785
To solidify things-- if we have 1, 2, 3,
4, 5, my thing is going to be like, oh.

498
00:26:16,785 --> 00:26:18,660
So it's going to look
for the smallest thing.

499
00:26:18,660 --> 00:26:21,248
So it's going to start with
1 and go, OK, 1 is small.

500
00:26:21,248 --> 00:26:23,540
I'm going to compare it to
2, and then compare it to 3,

501
00:26:23,540 --> 00:26:26,240
and then compare it to
4, then compare to 5.

502
00:26:26,240 --> 00:26:29,000
And then, there's 1 is the smallest,
so 1 is going to stay here.

503
00:26:29,000 --> 00:26:30,833
But I have to do the
exact same thing that I

504
00:26:30,833 --> 00:26:35,490
did before because I still have to
check if that is indeed the smallest.

505
00:26:35,490 --> 00:26:41,765
So the or the best-case time
complexity is going to n squared.

506
00:26:41,765 --> 00:26:44,390
The space complexity is actually
the same thing as bubble sort.

507
00:26:44,390 --> 00:26:47,000
Notice that all we're
doing is about to swaps.

508
00:26:47,000 --> 00:26:49,200
We don't actually need
to store anything.

509
00:26:49,200 --> 00:26:51,760
So this is also going to be a constant.

510
00:26:51,760 --> 00:26:54,320


511
00:26:54,320 --> 00:26:57,760
And then in terms merge
sort, we get to exploit

512
00:26:57,760 --> 00:27:03,940
a very nice property of dividing our
array into two parts and [INAUDIBLE]..

513
00:27:03,940 --> 00:27:08,320
And so if we were to have
this example earlier--

514
00:27:08,320 --> 00:27:11,350
5, 0, 1, 2, 1--

515
00:27:11,350 --> 00:27:12,790
I would split it into two parts.

516
00:27:12,790 --> 00:27:15,580
So let's say I split it down here.

517
00:27:15,580 --> 00:27:19,060
And then, now, I sort the two arrays--

518
00:27:19,060 --> 00:27:22,600
5, 0, 1 and then 2, 1.

519
00:27:22,600 --> 00:27:25,790
5, 0, 1 can be split
into two arrays again.

520
00:27:25,790 --> 00:27:29,350
And so let's say I do 5.

521
00:27:29,350 --> 00:27:34,015
And then, we'll put it here.

522
00:27:34,015 --> 00:27:38,220


523
00:27:38,220 --> 00:27:40,220
And then, I can split this again.

524
00:27:40,220 --> 00:27:44,818
But really, when I split this
again, it's going to be a 5 and a 0.

525
00:27:44,818 --> 00:27:46,610
And then, I'm going to
merge them together.

526
00:27:46,610 --> 00:27:50,780
The array with a 0 it's going
to be smaller than that 5.

527
00:27:50,780 --> 00:27:53,990
And so we can put 0 and 5.

528
00:27:53,990 --> 00:27:58,790
And then, when I merge this
with the 1 here, I'm going to--

529
00:27:58,790 --> 00:28:00,230
I'm running out of space.

530
00:28:00,230 --> 00:28:02,700
When I merge this with the 1
here, I'm going to realize--

531
00:28:02,700 --> 00:28:04,910
so 0 is the smallest.

532
00:28:04,910 --> 00:28:07,070
And between 1 and 5, 1 is the smallest.

533
00:28:07,070 --> 00:28:08,488
I'm going to have 5.

534
00:28:08,488 --> 00:28:10,280
And then, the same
thing is going to happen

535
00:28:10,280 --> 00:28:14,450
on the right-hand side, where I'm
going to have resorted to a 1 and 2.

536
00:28:14,450 --> 00:28:16,340
And then, I'm going to
merge these together

537
00:28:16,340 --> 00:28:21,590
to be the smallest out of these two
arrays, the leftmost pointer for each,

538
00:28:21,590 --> 00:28:23,810
the smallest is 0.

539
00:28:23,810 --> 00:28:25,790
So I'm going to take out the 0.

540
00:28:25,790 --> 00:28:29,955
And then, the smallest
of the leftmost is 1.

541
00:28:29,955 --> 00:28:32,240
So I can mark out either one.

542
00:28:32,240 --> 00:28:35,840
And then, the smallest of
this 5 and this 1 is also 1.

543
00:28:35,840 --> 00:28:37,880
So I can mark out this one.

544
00:28:37,880 --> 00:28:40,910
And then, the smallest
between the 2 and the 5

545
00:28:40,910 --> 00:28:45,770
is going to be 2, so write
down 2 and mark this down.

546
00:28:45,770 --> 00:28:51,530
And then, the smallest left,
the only thing left is the 5.

547
00:28:51,530 --> 00:28:53,960
So that's how merge sort works.

548
00:28:53,960 --> 00:28:56,840
And the nice thing about merge
sort is that every single time, we

549
00:28:56,840 --> 00:29:00,290
keep dividing the array in two.

550
00:29:00,290 --> 00:29:03,170
And so whenever we divide
the array into two,

551
00:29:03,170 --> 00:29:09,300
consecutively, this is going to
take log n total of these divisions.

552
00:29:09,300 --> 00:29:14,760
So it's worst case is
going to be part log n.

553
00:29:14,760 --> 00:29:18,120
But in addition to dividing it,
we also have to merge it together.

554
00:29:18,120 --> 00:29:21,088
And merging them together
ultimately does take n total

555
00:29:21,088 --> 00:29:23,130
because we have to make
all of these comparisons.

556
00:29:23,130 --> 00:29:26,255
If you remember, at the very end, we
made all of these sorts of comparisons

557
00:29:26,255 --> 00:29:28,450
in order to merge them together.

558
00:29:28,450 --> 00:29:31,800
So it's going to be n log n.

559
00:29:31,800 --> 00:29:36,710
And just like selection sort, it doesn't
matter what order it's already in.

560
00:29:36,710 --> 00:29:39,330
Merge sort will take these
and still merge them together,

561
00:29:39,330 --> 00:29:42,670
still cut them all down into tiny
pieces and try to piece them together.

562
00:29:42,670 --> 00:29:47,770
So the best case is also
going to be n log n.

563
00:29:47,770 --> 00:29:52,720
And so finally, the space
is going to be linear

564
00:29:52,720 --> 00:29:55,870
because we have to copy this array.

565
00:29:55,870 --> 00:30:00,070
We can't just like chop the
array in the space they already

566
00:30:00,070 --> 00:30:01,390
give us and make swaps.

567
00:30:01,390 --> 00:30:06,830
We have to store it somewhere else
before being able to move them around.

568
00:30:06,830 --> 00:30:09,535
So it's just going to take linear.

569
00:30:09,535 --> 00:30:12,250


570
00:30:12,250 --> 00:30:20,590
So we're going to take a look at some
examples of space and time complexity.

571
00:30:20,590 --> 00:30:21,680
I have an example here.

572
00:30:21,680 --> 00:30:24,050
It's going to be called
the mega-lazy sort.

573
00:30:24,050 --> 00:30:29,620
So in this sorting mechanism, I'm going
to go through a list number by number.

574
00:30:29,620 --> 00:30:32,530
And when I see a number that
is not in the right order,

575
00:30:32,530 --> 00:30:34,930
I'm going to throw it
away because I'm lazy

576
00:30:34,930 --> 00:30:37,960
and it can't be a problem
if it's not there.

577
00:30:37,960 --> 00:30:42,190
So can someone tell me what
the worst case time complexity

578
00:30:42,190 --> 00:30:45,940
is via chat in this particular example?

579
00:30:45,940 --> 00:30:54,610


580
00:30:54,610 --> 00:30:56,360
Perfect.

581
00:30:56,360 --> 00:31:00,290
We'll go ahead and do something
like the example that we did.

582
00:31:00,290 --> 00:31:01,550
But you're right.

583
00:31:01,550 --> 00:31:02,400
This is linear.

584
00:31:02,400 --> 00:31:05,840
So if we did our 5, 0, 1, 2, and 1.

585
00:31:05,840 --> 00:31:06,470
I'm lazy.

586
00:31:06,470 --> 00:31:07,310
I look at the 5.

587
00:31:07,310 --> 00:31:09,428
I'm like, OK, cool.

588
00:31:09,428 --> 00:31:11,720
Now, looking at the 0, I'm
like 0 is not bigger than 5.

589
00:31:11,720 --> 00:31:12,755
I'm going to throw it away.

590
00:31:12,755 --> 00:31:14,213
And then, I'm going to check the 1.

591
00:31:14,213 --> 00:31:15,307
1 is not bigger than 5.

592
00:31:15,307 --> 00:31:16,640
I'm also going to throw it away.

593
00:31:16,640 --> 00:31:17,960
2 is also not greater than 5.

594
00:31:17,960 --> 00:31:19,100
We can throw it away way.

595
00:31:19,100 --> 00:31:20,540
The 1 is also not greater than 5.

596
00:31:20,540 --> 00:31:22,440
I'm also going to throw it away.

597
00:31:22,440 --> 00:31:26,030
So basically, I have a sorted array.

598
00:31:26,030 --> 00:31:28,430
But really, it's not sorted
from the previous array.

599
00:31:28,430 --> 00:31:31,040
But this is indeed sorted.

600
00:31:31,040 --> 00:31:37,370
And I had to look through every single
one of the elements inside this array

601
00:31:37,370 --> 00:31:42,290
in order to make this new 5 here.

602
00:31:42,290 --> 00:31:44,980
So for those of you that
said linear, you're right.

603
00:31:44,980 --> 00:31:50,540
This worst case time complexity is O of
n if there are n elements in this list.

604
00:31:50,540 --> 00:31:53,670


605
00:31:53,670 --> 00:31:58,090
And so now, we're going to do
mega-lazy sort but with friends.

606
00:31:58,090 --> 00:32:03,010
So Carter and I are going to
divide my list into two parts.

607
00:32:03,010 --> 00:32:05,450
And the Carter and I are both mega lazy.

608
00:32:05,450 --> 00:32:09,220
So we're going to use that
to sort our respective parts.

609
00:32:09,220 --> 00:32:12,790
And then, I'm going to take
the time to merge the two

610
00:32:12,790 --> 00:32:15,520
lists that Carter and I get.

611
00:32:15,520 --> 00:32:20,260
So does someone want to tell me what
the time complexity for this is?

612
00:32:20,260 --> 00:32:26,298


613
00:32:26,298 --> 00:32:27,590
We'll go ahead and get started.

614
00:32:27,590 --> 00:32:28,798
And you can still message me.

615
00:32:28,798 --> 00:32:31,460


616
00:32:31,460 --> 00:32:35,300
So let's do 5, 0, 1, 2, and 1.

617
00:32:35,300 --> 00:32:38,450
And we're going to divide it like this.

618
00:32:38,450 --> 00:32:42,790
But because I'm lazier than Carter,
I'm going to take the first half--

619
00:32:42,790 --> 00:32:43,850
me.

620
00:32:43,850 --> 00:32:47,990
So whenever I sort this,
I'm going to write down a 5.

621
00:32:47,990 --> 00:32:52,590
And I'm going to say 0 is not bigger
than 5, so I'm going to throw it away.

622
00:32:52,590 --> 00:32:56,480
That's now my list, my new
list, "my sorted list."

623
00:32:56,480 --> 00:33:00,780


624
00:33:00,780 --> 00:33:03,300
And then, whenever
Carter sorts his list,

625
00:33:03,300 --> 00:33:06,000
he's going to notice that there is a 1.

626
00:33:06,000 --> 00:33:07,710
And then, there's also a 2.

627
00:33:07,710 --> 00:33:08,850
That's in the right order.

628
00:33:08,850 --> 00:33:10,810
But the 1 after is not
in the right order.

629
00:33:10,810 --> 00:33:13,020
So he's going to throw away in that one.

630
00:33:13,020 --> 00:33:14,760
And so this is now Carter's sorted list.

631
00:33:14,760 --> 00:33:20,120


632
00:33:20,120 --> 00:33:23,270
Now, I'm going to take
the effort to merge it.

633
00:33:23,270 --> 00:33:26,960
And I'm going to notice
that the left-most on mine

634
00:33:26,960 --> 00:33:29,880
and the left-most on his--
the 1 is the smallest.

635
00:33:29,880 --> 00:33:33,480
So my final answer is going to have a 1.

636
00:33:33,480 --> 00:33:40,020
And then, now that we've written the 1,
we can take a look at the 5 and the 2.

637
00:33:40,020 --> 00:33:42,750
And then, Carter's
next smallest is the 2.

638
00:33:42,750 --> 00:33:45,120
And so we're going to get rid of that 2.

639
00:33:45,120 --> 00:33:46,980
And the last number left is 5.

640
00:33:46,980 --> 00:33:49,590
So now, I have a 1, 2, and a 5.

641
00:33:49,590 --> 00:33:51,540
And that's my final sorted array.

642
00:33:51,540 --> 00:33:57,430


643
00:33:57,430 --> 00:33:58,870
And we'll take a look.

644
00:33:58,870 --> 00:34:07,920
And this is actually linear again
because whenever I did this sort,

645
00:34:07,920 --> 00:34:10,570
I had about half of the elements.

646
00:34:10,570 --> 00:34:17,460
And so I had to make a pass that took
about n over 2 total comparisons.

647
00:34:17,460 --> 00:34:21,489
And then, Carter also did
about n over 2 comparisons.

648
00:34:21,489 --> 00:34:25,050
So if you combine the
amount of comparisons

649
00:34:25,050 --> 00:34:29,219
that Carter and I did in the beginning,
that's about n total comparisons.

650
00:34:29,219 --> 00:34:33,780
And then, whenever I put our list
together, whenever I merged it,

651
00:34:33,780 --> 00:34:38,489
there is a maximum of n total
comparisons I have to make.

652
00:34:38,489 --> 00:34:42,110
That is assuming that
I don't delete anything

653
00:34:42,110 --> 00:34:44,250
and Carter doesn't
believe anything, then

654
00:34:44,250 --> 00:34:46,739
I would have to make a total
of n total comparisons.

655
00:34:46,739 --> 00:34:48,989
And so the number of
comparisons I have to make

656
00:34:48,989 --> 00:34:52,199
while merging is upper bounded by n.

657
00:34:52,199 --> 00:34:59,160
And so we have n for the original
sorting, and then n for the merging.

658
00:34:59,160 --> 00:35:00,520
And that's going to be 2n.

659
00:35:00,520 --> 00:35:04,390
And remember, we can drop multiplicative
constants for our time complexity.

660
00:35:04,390 --> 00:35:08,560
So this is linear, or O of n.

661
00:35:08,560 --> 00:35:10,375
We will go to our next example.

662
00:35:10,375 --> 00:35:13,220


663
00:35:13,220 --> 00:35:15,940
So next, I'm going to use internet sort.

664
00:35:15,940 --> 00:35:19,240
I'm going to go through a
list of a, b, c, d, and e.

665
00:35:19,240 --> 00:35:22,210
And first, I'm going to Google,
"which is bigger, a or b?"

666
00:35:22,210 --> 00:35:25,390
And then, if Google says,
a, then I swap a and b.

667
00:35:25,390 --> 00:35:28,600
And then, I ask Google about the
next two elements, c and whichever

668
00:35:28,600 --> 00:35:30,700
was larger between a and b.

669
00:35:30,700 --> 00:35:36,140
And then, I make as many passes through
the list as necessary to sort the list.

670
00:35:36,140 --> 00:35:40,580
So if you can send me in chat what
sort of sort this remind you of,

671
00:35:40,580 --> 00:35:42,110
that would be great.

672
00:35:42,110 --> 00:35:48,677
I'll give you a second to
consider what sort this is like.

673
00:35:48,677 --> 00:35:51,260
Hint, it's one of those three
sorts that we just talked about.

674
00:35:51,260 --> 00:35:59,010


675
00:35:59,010 --> 00:36:02,920
So most of you, yes, it
is bubble sort, in fact.

676
00:36:02,920 --> 00:36:07,080
Let's run a quick simulation with
the numbers that we had earlier.

677
00:36:07,080 --> 00:36:15,480
Let's have a be 5, b be 0,
c be 1, d be 2, and e be 1.

678
00:36:15,480 --> 00:36:18,150
And then, I'm asking Google,
"which one's bigger, a or b?"

679
00:36:18,150 --> 00:36:19,680
5 or 0.

680
00:36:19,680 --> 00:36:22,480
Google's probably going to
tell me that 5 is bigger.

681
00:36:22,480 --> 00:36:27,600
And so then, I'm going
to swap them to get this.

682
00:36:27,600 --> 00:36:31,380
And then, I ask Google, which one's
bigger between c-- which is this one--

683
00:36:31,380 --> 00:36:33,863
and whichever was larger
a and b, so this one.

684
00:36:33,863 --> 00:36:36,030
I'm going to ask Google,
is 5 bigger or is 1 bigger?

685
00:36:36,030 --> 00:36:39,760
And Google's probably also going
to tell me that 5 is bigger.

686
00:36:39,760 --> 00:36:43,190
So then, I'm going to make this switch.

687
00:36:43,190 --> 00:36:48,630
And then, I just keep going over and
over until the end of this iteration.

688
00:36:48,630 --> 00:36:52,370
So I make as many passes through the
list as necessary to sort the list.

689
00:36:52,370 --> 00:36:56,145
So I have, here, this first pass.

690
00:36:56,145 --> 00:36:58,750


691
00:36:58,750 --> 00:37:02,410
And you might notice that
this is, in fact, not sorted.

692
00:37:02,410 --> 00:37:07,940
And so I would have to make more and
more passes until this is done sorting.

693
00:37:07,940 --> 00:37:10,750
And so this is the exact
same as bubble sort.

694
00:37:10,750 --> 00:37:16,390
And the worst case time complexity
would be just like bubble sort,

695
00:37:16,390 --> 00:37:18,400
for o of n squared.

696
00:37:18,400 --> 00:37:21,370
And the space complexity is going
to be constant because all I'm doing

697
00:37:21,370 --> 00:37:22,520
is making a bunch of swaps.

698
00:37:22,520 --> 00:37:26,550


699
00:37:26,550 --> 00:37:27,110
Cool.

700
00:37:27,110 --> 00:37:29,210
Next here is bogosort.

701
00:37:29,210 --> 00:37:33,380
Next, we're going to do the
very, very fun and not tedious

702
00:37:33,380 --> 00:37:36,560
sort of modified bogosort.

703
00:37:36,560 --> 00:37:39,200
I am brilliant at sorting.

704
00:37:39,200 --> 00:37:43,040
And I'm going to generate all
possible permutations of a list

705
00:37:43,040 --> 00:37:45,888
and then store it in a list of lists.

706
00:37:45,888 --> 00:37:48,680
And then, I'm going to check every
single one of these permutations

707
00:37:48,680 --> 00:37:52,380
to see if it's ordered correctly.

708
00:37:52,380 --> 00:37:55,910
So if you could type in chat what you
think the time and space complexity is,

709
00:37:55,910 --> 00:37:57,750
that would be great.

710
00:37:57,750 --> 00:38:01,550
And we're going to go for just a
slightly smaller example this time

711
00:38:01,550 --> 00:38:05,432
so I don't have to sit here for the
next hour writing out the permutations.

712
00:38:05,432 --> 00:38:08,090


713
00:38:08,090 --> 00:38:12,110
So let's say I have 2, 5, and 1.

714
00:38:12,110 --> 00:38:14,495
So n equals 3 this time.

715
00:38:14,495 --> 00:38:16,850
And I would have to write
out every single permutation.

716
00:38:16,850 --> 00:38:26,920
So I have 2, 5, 1; 2, 1, 5; 5,
1, 2; 5, 2, 1; 1, 2, 5; 1, 5, 2.

717
00:38:26,920 --> 00:38:29,420
And then, we're going to go
through every single one of them

718
00:38:29,420 --> 00:38:31,880
to see which of them are sorted.

719
00:38:31,880 --> 00:38:33,620
So 2,5, 1.

720
00:38:33,620 --> 00:38:37,790
5 seems greater than
2, so that's not it.

721
00:38:37,790 --> 00:38:40,800
Sorry, 1 seems less than
5, so that's not it.

722
00:38:40,800 --> 00:38:45,080
And then, this one, 1 is less
than 2, so that also seems not it.

723
00:38:45,080 --> 00:38:45,960
1 seems less than 5.

724
00:38:45,960 --> 00:38:47,930
That's not it.

725
00:38:47,930 --> 00:38:49,280
2 seems to be less than 5.

726
00:38:49,280 --> 00:38:50,670
That's not it.

727
00:38:50,670 --> 00:38:52,550
This one, 1 is less than 2, that's good.

728
00:38:52,550 --> 00:38:54,290
2 is less than 5, that seems good.

729
00:38:54,290 --> 00:38:56,120
Cool, we found it.

730
00:38:56,120 --> 00:38:59,010
That did not take forever.

731
00:38:59,010 --> 00:39:01,280
So let's take a look.

732
00:39:01,280 --> 00:39:09,230
Each time we check one of these to see
if it is actually a ascending ordering,

733
00:39:09,230 --> 00:39:10,950
we have to look at every single number.

734
00:39:10,950 --> 00:39:13,610
So when we check this one,
we checked is 1 less than 2?

735
00:39:13,610 --> 00:39:14,250
Yeah.

736
00:39:14,250 --> 00:39:15,390
Is 2 less than 5?

737
00:39:15,390 --> 00:39:16,190
Yeah.

738
00:39:16,190 --> 00:39:25,760
So each time, we check something,
a list, it takes n comparisons.

739
00:39:25,760 --> 00:39:30,890
And then, whenever we are
making all these permutations,

740
00:39:30,890 --> 00:39:35,060
you might know the number of
permutations is n factorial.

741
00:39:35,060 --> 00:39:40,120


742
00:39:40,120 --> 00:39:43,070
And so the total amount
of time it takes,

743
00:39:43,070 --> 00:39:48,050
then, it is going to
be n times n factorial

744
00:39:48,050 --> 00:39:51,690
because for every single permutation,
we're going to have to compare it.

745
00:39:51,690 --> 00:39:54,150
So that's the worst
case time complexity.

746
00:39:54,150 --> 00:39:58,190
And then, because I store
it all in a list of lists,

747
00:39:58,190 --> 00:40:00,650
I have to store all of these.

748
00:40:00,650 --> 00:40:03,590
And so since there are
n factorial permutations

749
00:40:03,590 --> 00:40:09,860
and each one takes n space, I also
have a worst case space complexity,

750
00:40:09,860 --> 00:40:13,680
or an actual space complexity,
of n times n factorial.

751
00:40:13,680 --> 00:40:18,320
So in this case, both of these
are O of n times n factorial.

752
00:40:18,320 --> 00:40:22,990


753
00:40:22,990 --> 00:40:27,430
Finally, we're going
to go do a zen sort.

754
00:40:27,430 --> 00:40:31,570
I'm achieving enlightenment
now after writing out

755
00:40:31,570 --> 00:40:34,420
factorial permutations of numbers.

756
00:40:34,420 --> 00:40:36,340
And I now have a list.

757
00:40:36,340 --> 00:40:39,460
And I realize that the list,
like all things, is ephemeral

758
00:40:39,460 --> 00:40:41,552
and its order is insignificant.

759
00:40:41,552 --> 00:40:42,760
So I just leave it like that.

760
00:40:42,760 --> 00:40:46,330
And I pursue enlightenment instead.

761
00:40:46,330 --> 00:40:50,950
If you want to send me how much time
and how much space this might take,

762
00:40:50,950 --> 00:40:52,960
do let me know in the chat.

763
00:40:52,960 --> 00:41:00,890


764
00:41:00,890 --> 00:41:03,270
Yeah, this takes constant time.

765
00:41:03,270 --> 00:41:04,940
In fact, it takes one operation.

766
00:41:04,940 --> 00:41:09,350
It takes me sitting here and quitting
because I'm achieving enlightenment

767
00:41:09,350 --> 00:41:10,230
instead.

768
00:41:10,230 --> 00:41:14,240
So no matter how long
the list is, I am going

769
00:41:14,240 --> 00:41:16,965
to realize that the list,
like all things, is ephemeral.

770
00:41:16,965 --> 00:41:18,090
And I'm just going to quit.

771
00:41:18,090 --> 00:41:19,465
So it doesn't really depend on n.

772
00:41:19,465 --> 00:41:20,270
It's all constant.

773
00:41:20,270 --> 00:41:23,580
I sit there and I have to
make that realization myself.

774
00:41:23,580 --> 00:41:27,490
And so the worst case time and
space is going to be constant time.

775
00:41:27,490 --> 00:41:31,350


776
00:41:31,350 --> 00:41:33,930
Now, we're going to talk a
little bit about searches.

777
00:41:33,930 --> 00:41:38,610
So let's say I have an unordered
list and I'm searching for a 5.

778
00:41:38,610 --> 00:41:44,140
And I want to figure out what is the
fastest way to solve this problem.

779
00:41:44,140 --> 00:41:47,860
Can y'all send me in the chat what the
fastest way to solve this problem is

780
00:41:47,860 --> 00:41:49,150
if I have an unordered list?

781
00:41:49,150 --> 00:41:57,520


782
00:41:57,520 --> 00:42:01,900
So let's consider linear search.

783
00:42:01,900 --> 00:42:04,550


784
00:42:04,550 --> 00:42:09,040
So linear search is going to require
that I look through the entire list.

785
00:42:09,040 --> 00:42:12,440
And this is going to have
a worst case of linear time

786
00:42:12,440 --> 00:42:17,930
because I have to go through every
single one of them to search for a 5.

787
00:42:17,930 --> 00:42:21,290
And so in this case, we actually
cannot use binary search

788
00:42:21,290 --> 00:42:22,700
because it's unordered.

789
00:42:22,700 --> 00:42:30,200
And so for example, if I was
looking for a 5, 0, 1, 2, and 1.

790
00:42:30,200 --> 00:42:32,615
And let's say I was looking for--

791
00:42:32,615 --> 00:42:35,570


792
00:42:35,570 --> 00:42:36,380
what else?

793
00:42:36,380 --> 00:42:38,450
Let's put it negative 1 here.

794
00:42:38,450 --> 00:42:41,990
Let's say I was looking
for a negative 1.

795
00:42:41,990 --> 00:42:47,365


796
00:42:47,365 --> 00:42:48,490
I start with binary search.

797
00:42:48,490 --> 00:42:49,573
I go to the middle number.

798
00:42:49,573 --> 00:42:50,260
This is 1.

799
00:42:50,260 --> 00:42:52,692
So binary search told me
I should go to the left.

800
00:42:52,692 --> 00:42:54,400
And as you can tell,
if I go to the left,

801
00:42:54,400 --> 00:42:57,800
I'll never find a negative 1,
even though it exists right here.

802
00:42:57,800 --> 00:43:01,360
So for an unordered list, you
cannot use a binary search.

803
00:43:01,360 --> 00:43:04,600
But for an ordered list,
you can use a binary search.

804
00:43:04,600 --> 00:43:09,605
And the fastest way to solve this
problem is, indeed, a binary search.

805
00:43:09,605 --> 00:43:18,550


806
00:43:18,550 --> 00:43:21,678
Any questions before
we go on to recursion?

807
00:43:21,678 --> 00:43:28,740


808
00:43:28,740 --> 00:43:30,660
So whenever we talk
about recursion, which

809
00:43:30,660 --> 00:43:34,170
is a technique that allows us to
continuously call on the same function

810
00:43:34,170 --> 00:43:41,070
or call our own function, we're going
to consider a few different things.

811
00:43:41,070 --> 00:43:44,460
So if you just sent me a
question, I will answer it later.

812
00:43:44,460 --> 00:43:48,788
We're going to consider the base case,
which is when does the recursion stop?

813
00:43:48,788 --> 00:43:50,580
We have to define when
the recursion stops,

814
00:43:50,580 --> 00:43:52,890
or else we'll get stack
overflow because there's going

815
00:43:52,890 --> 00:43:54,900
to be too many functions being called.

816
00:43:54,900 --> 00:43:56,950
And the stack frame won't
be able to handle it,

817
00:43:56,950 --> 00:43:58,620
so we'll get a stack overflow--

818
00:43:58,620 --> 00:44:04,015
so "when we stop the recursion."

819
00:44:04,015 --> 00:44:08,970


820
00:44:08,970 --> 00:44:13,220
And then, the recursive step is
how do we call our own function?

821
00:44:13,220 --> 00:44:17,150
"How to call own function."

822
00:44:17,150 --> 00:44:20,400


823
00:44:20,400 --> 00:44:22,470
And the impacts on
space complexity-- like

824
00:44:22,470 --> 00:44:27,420
I said, every single time we make a
function, that goes into the stack.

825
00:44:27,420 --> 00:44:30,760
And so we call this
function infinite times.

826
00:44:30,760 --> 00:44:32,650
And we don't have a base case.

827
00:44:32,650 --> 00:44:34,860
We're going to add to
the stack infinite times.

828
00:44:34,860 --> 00:44:37,800
And then, we're going to
have a stack overflow.

829
00:44:37,800 --> 00:44:43,920
So just as a quick example, we're
going to take a look at this function.

830
00:44:43,920 --> 00:44:45,780
I've called it nom.

831
00:44:45,780 --> 00:44:50,370
And whenever x is less than or
equal to 0, I'm going to return.

832
00:44:50,370 --> 00:44:55,250
And then, otherwise, I'm going to
print("nom") and then return nom(x -

833
00:44:55,250 --> 00:44:56,950
1).

834
00:44:56,950 --> 00:45:00,580
So if you could, in the chat,
tell me what this prints

835
00:45:00,580 --> 00:45:03,430
and what its time and space
complexity is, that would be great.

836
00:45:03,430 --> 00:45:06,530


837
00:45:06,530 --> 00:45:14,853
So for example, if we had nom(3),
this would print "nom nom nom."

838
00:45:14,853 --> 00:45:18,930


839
00:45:18,930 --> 00:45:22,520
So then, nom(3) is going
to go check x equals 3.

840
00:45:22,520 --> 00:45:24,062
And it's not less than or equal to 0.

841
00:45:24,062 --> 00:45:25,353
And it's going to print("nom").

842
00:45:25,353 --> 00:45:28,500
And then, it's going to call nom(2),
which is not less than or equal to 0.

843
00:45:28,500 --> 00:45:29,750
So it's going to print("nom").

844
00:45:29,750 --> 00:45:33,140
And then, it's going to call nom(1),
which is not less than or equal to 0.

845
00:45:33,140 --> 00:45:36,207
So it's going to print("nom")
again and then call nom(0).

846
00:45:36,207 --> 00:45:37,790
And then, it's going to be equal to 0.

847
00:45:37,790 --> 00:45:39,710
So it's going to return.

848
00:45:39,710 --> 00:45:42,930
And then, it will stop there.

849
00:45:42,930 --> 00:45:50,640
And so in terms of space
and time, that's right.

850
00:45:50,640 --> 00:45:55,840
This takes linear time, linear for both.

851
00:45:55,840 --> 00:46:00,780
So for a time, at least, every
single time I have a number,

852
00:46:00,780 --> 00:46:03,752
I do a constant time of operation.

853
00:46:03,752 --> 00:46:05,460
And then, I go to that
number of minus 1.

854
00:46:05,460 --> 00:46:11,610
So I make n total of those
constant time operations.

855
00:46:11,610 --> 00:46:16,800
And then, in terms of the space, I
make n total calls to the nom function.

856
00:46:16,800 --> 00:46:22,580
And since there are n total calls to the
nom function, it's going to be linear.

857
00:46:22,580 --> 00:46:25,100
And so we'll do a quick problem.

858
00:46:25,100 --> 00:46:26,310
I hate climbing stairs.

859
00:46:26,310 --> 00:46:27,990
This is a true statement.

860
00:46:27,990 --> 00:46:30,200
And so I always have
to make snarky comments

861
00:46:30,200 --> 00:46:32,930
when my friends have
to flex their cool legs

862
00:46:32,930 --> 00:46:36,210
and climb up the stairs one
or two steps at the time.

863
00:46:36,210 --> 00:46:40,220
And so let's suppose it takes n steps
to reach the top of the staircase.

864
00:46:40,220 --> 00:46:45,560
And every time, my cool friends
can either climb one or two steps.

865
00:46:45,560 --> 00:46:50,600
And instead of climbing stairs, I like
to think about how many distinct ways

866
00:46:50,600 --> 00:46:53,280
my friends can climb to the top.

867
00:46:53,280 --> 00:46:55,860
So there are multiple
ways to solve this.

868
00:46:55,860 --> 00:46:57,490
We'll talk about both ways.

869
00:46:57,490 --> 00:47:00,420
The first way is to use the recursion.

870
00:47:00,420 --> 00:47:02,910
And the second one is more
of an iterative solution,

871
00:47:02,910 --> 00:47:07,420
where we build up to an answer.

872
00:47:07,420 --> 00:47:11,700
For recursion, we will
write a function in Python.

873
00:47:11,700 --> 00:47:15,270
And we'll call it climb_stairs.

874
00:47:15,270 --> 00:47:20,300
And it's going to take a number,
n, that's the number of floors.

875
00:47:20,300 --> 00:47:25,650
And so let's do first component
recursion, we talked about,

876
00:47:25,650 --> 00:47:26,770
is a base case.

877
00:47:26,770 --> 00:47:30,930
So we want to check if n equals 1.

878
00:47:30,930 --> 00:47:33,670
If n equals 1, that
means there's one stairs.

879
00:47:33,670 --> 00:47:35,670
There's only one way to go about it.

880
00:47:35,670 --> 00:47:38,720
No matter how cool my friends
are, they can only take one step.

881
00:47:38,720 --> 00:47:41,860
So then, we're going to return 1.

882
00:47:41,860 --> 00:47:49,830
If there are two steps,
my friends can be cool,

883
00:47:49,830 --> 00:47:54,790
could go up the two steps in one go
or go up the two steps one at a time.

884
00:47:54,790 --> 00:48:00,280
There are two ways to do it,
so we're going to return 2.

885
00:48:00,280 --> 00:48:06,570
Otherwise, we can think about it
like if there are three steps,

886
00:48:06,570 --> 00:48:11,865
then they can either take one step
and then make the two-step hop.

887
00:48:11,865 --> 00:48:15,210
Or they're on the second step
and they make the one-step hop.

888
00:48:15,210 --> 00:48:28,560
So otherwise, we can return
climb_stairs(n-1) plus

889
00:48:28,560 --> 00:48:29,670
climb_stairs(n-2).

890
00:48:29,670 --> 00:48:33,220


891
00:48:33,220 --> 00:48:36,400
Think about if we're on
the n-th step, then they

892
00:48:36,400 --> 00:48:40,330
can either take one
step from the n minus 1

893
00:48:40,330 --> 00:48:44,670
or they can take that two-step
hop from the minus 2 step.

894
00:48:44,670 --> 00:48:47,410


895
00:48:47,410 --> 00:48:51,670
And we will think about the
iterative solution really quickly.

896
00:48:51,670 --> 00:48:55,850
And then, if you have questions,
I can answer them afterwards.

897
00:48:55,850 --> 00:48:59,060
So the iterative solution is
building up towards that answer.

898
00:48:59,060 --> 00:49:01,060
So earlier, we said
if there are n steps,

899
00:49:01,060 --> 00:49:05,080
I want to think about the n minus
1 step and the n minus 2 step.

900
00:49:05,080 --> 00:49:08,440
The iterative solution
lets us think about--

901
00:49:08,440 --> 00:49:11,570
how do I get one step, how do I get
two steps, how do I get to three steps,

902
00:49:11,570 --> 00:49:15,450
how do I get to four steps, all the
way up to how do I get to n steps.

903
00:49:15,450 --> 00:49:19,940
So instead of going top-down,
we're going to go from 1 to n.

904
00:49:19,940 --> 00:49:24,830
So that's part of another solution where
we have another climb_stairs function

905
00:49:24,830 --> 00:49:28,170
just like earlier.

906
00:49:28,170 --> 00:49:30,750
And we're also going to do it
like if n equals 1, same thing.

907
00:49:30,750 --> 00:49:33,600
We want to go ahead and return 1.

908
00:49:33,600 --> 00:49:37,760
And if n equals 2, we're going
to go ahead and return 2.

909
00:49:37,760 --> 00:49:40,400


910
00:49:40,400 --> 00:49:46,250
And then, in order to store all of
this information, 1 all the way to n,

911
00:49:46,250 --> 00:49:49,260
we're going to have an array.

912
00:49:49,260 --> 00:49:53,760
I'm going to instantiate
this array with some zeros.

913
00:49:53,760 --> 00:49:56,338
This is some syntax
that you might not be

914
00:49:56,338 --> 00:49:58,130
familiar with that we
can talk about later.

915
00:49:58,130 --> 00:50:03,340
But essentially, this gives me n 0's.

916
00:50:03,340 --> 00:50:09,820
And then, we're going to say, in this
particular answer, the 0-th one--

917
00:50:09,820 --> 00:50:12,070
or in this case, it's the 0 index.

918
00:50:12,070 --> 00:50:15,430
The first step, there's only
one possible way to do it.

919
00:50:15,430 --> 00:50:20,180
And then, the second step has
two possible ways to do it.

920
00:50:20,180 --> 00:50:22,770
And then, we can do a for loop.

921
00:50:22,770 --> 00:50:33,570
So for the rest of them, what I
can do is look at the two before.

922
00:50:33,570 --> 00:50:38,120
So just like I did earlier, where
I did n minus 1 plus n minus 2,

923
00:50:38,120 --> 00:50:41,130
I'm going to populate this
array in the same way.

924
00:50:41,130 --> 00:50:52,620
So answer i it's going to be answer
i minus 1 plus answer i minus 2.

925
00:50:52,620 --> 00:50:58,260
And at the very end, since I computed
it from 1 to n, all I have to do

926
00:50:58,260 --> 00:51:02,490
is return that last number, which
is going to be the minus 1 index.

927
00:51:02,490 --> 00:51:06,550


928
00:51:06,550 --> 00:51:10,420
Any questions on that,
we will answer shortly.

929
00:51:10,420 --> 00:51:11,980
But I'll hand it back to Carter.

930
00:51:11,980 --> 00:51:16,710


931
00:51:16,710 --> 00:51:19,530
CARTER ZENKE: So for our
last about 10 minutes, here,

932
00:51:19,530 --> 00:51:22,350
we thought we would do some
practice with practice questions

933
00:51:22,350 --> 00:51:23,340
from the past test.

934
00:51:23,340 --> 00:51:26,160
And so go ahead and
open two breakout rooms.

935
00:51:26,160 --> 00:51:28,560
One will be for practice
with programming constructs.

936
00:51:28,560 --> 00:51:31,500
And there's a prior test
question called programming in B

937
00:51:31,500 --> 00:51:32,637
that might be useful there.

938
00:51:32,637 --> 00:51:34,470
And then, for more
practice with complexity,

939
00:51:34,470 --> 00:51:37,260
we'll have this past test question
called complexities of a space.

940
00:51:37,260 --> 00:51:39,520
I think it might be useful there.

941
00:51:39,520 --> 00:51:43,140
I think Phyllis will be able to help
in the complexity breakout room.

942
00:51:43,140 --> 00:51:46,320
I'll be able to help in the
programming constructs breakout room.

943
00:51:46,320 --> 00:51:49,170
And we'll certainly be able to be
here until about 8 o'clock or so.

944
00:51:49,170 --> 00:51:50,878
But the goal here is
to give you practice

945
00:51:50,878 --> 00:51:53,227
with some of these past test questions.

946
00:51:53,227 --> 00:51:55,560
And certainly happy to answer
any questions that you all

947
00:51:55,560 --> 00:51:59,310
have in the moment from the
past algorithms work, as well.

948
00:51:59,310 --> 00:52:16,560


949
00:52:16,560 --> 00:52:19,660
I think that's going to
conclude our review session.

950
00:52:19,660 --> 00:52:24,410
So we're going to go ahead and do some
practice with past test questions.

951
00:52:24,410 --> 00:52:25,000