1
00:00:01,090 --> 00:00:09,730
OK, so let's go ahead and move on to the actual algorithms now for traversing graphs.

2
00:00:10,210 --> 00:00:18,730
So this first algorithm is going to be depth first search, which I have abbreviated here DFS.

3
00:00:19,240 --> 00:00:20,780
So let's get right into it.

4
00:00:22,630 --> 00:00:27,400
So we've talked about graphs a little bit, but what if we want to traverse a given graph and then make

5
00:00:27,400 --> 00:00:34,060
sure that we visit every single node or vertex while we traverse it in complete and completion, like

6
00:00:34,720 --> 00:00:41,890
from some starting node all the way through it and coming back to where we started, but making sure

7
00:00:41,890 --> 00:00:44,680
that we stopped at each one of the nodes.

8
00:00:45,400 --> 00:00:46,960
There are multiple ways you can do that.

9
00:00:47,080 --> 00:00:52,000
Two of the most popular ways are depth first search and breath, first search.

10
00:00:52,360 --> 00:00:55,090
And in this lecture, we're going to be talking about depth, first search.

11
00:00:55,840 --> 00:00:58,690
So as the name implies, you search deep first.

12
00:00:58,690 --> 00:01:04,780
So that would be like just taking a path, continuing on some path until you get to the end.

13
00:01:05,050 --> 00:01:09,600
Rather than like visiting everything that stems out from a vertex would be which would be breath for

14
00:01:09,600 --> 00:01:11,320
a search, which we'll talk about later.

15
00:01:12,410 --> 00:01:18,410
So you try and go deep first and then you basically come back when you can't explore anymore and then

16
00:01:18,410 --> 00:01:20,630
you explore another path going deep again.

17
00:01:22,090 --> 00:01:24,250
So let's look more into that.

18
00:01:24,820 --> 00:01:30,250
We're going to go ahead and traverse this, I have put some letters here is labels for the vertices.

19
00:01:31,090 --> 00:01:37,930
So we will start traversing it in depth first search fashion until we have visited all the nodes and

20
00:01:37,930 --> 00:01:38,920
are back where we started.

21
00:01:39,610 --> 00:01:40,990
So you can pick any starting point.

22
00:01:40,990 --> 00:01:43,180
I am going to pick see right here.

23
00:01:44,110 --> 00:01:51,130
You see that I'm also going to be labeling the order in which I am exploring and visiting these vertices.

24
00:01:52,180 --> 00:01:58,150
But you can pick any starting point and then from any given node link, for example, here you see that

25
00:01:58,150 --> 00:02:02,380
see has the potential to go to a D or F.

26
00:02:02,410 --> 00:02:04,990
You could really choose any one of those.

27
00:02:05,290 --> 00:02:10,690
Any one of those is going to be a valid move on a depth first search algorithm path.

28
00:02:11,800 --> 00:02:15,010
So I'm just going to go ahead and choose a.

29
00:02:16,450 --> 00:02:25,690
And once I have chosen a you see that I have also labeled it as the second note that we have visited.

30
00:02:26,950 --> 00:02:33,250
So from a I can go to B, and that is because I could also go to see from A.

31
00:02:33,280 --> 00:02:34,660
But we've already visited.

32
00:02:34,660 --> 00:02:38,770
See, so that's why I'm going to go to be so from B.

33
00:02:38,770 --> 00:02:42,760
We have a lot of choices since we've already visited A.

34
00:02:42,790 --> 00:02:49,720
We won't consider that, but we have D, E, H and J, so we'll go over to H.

35
00:02:50,410 --> 00:02:58,090
You notice that H has no other neighbors besides the one that it came from, so no other adjacent vertices.

36
00:02:59,170 --> 00:03:05,620
And so we're going to have to go back to B and then so after we go back to B, we can explore E is the

37
00:03:05,620 --> 00:03:07,030
same situation as F.

38
00:03:07,750 --> 00:03:11,920
Basically, there is no other adjacent businesses besides the one we came from.

39
00:03:12,760 --> 00:03:17,110
So we go back to B again and then we will go out to D.

40
00:03:18,190 --> 00:03:26,740
Vardy visited to see, so we had to f already visited D, so we had to g r f, so we had to I I has

41
00:03:26,740 --> 00:03:29,650
no other businesses to visit, so we come back to G.

42
00:03:30,070 --> 00:03:35,590
Everything is visited from G already, so we go to f same case for f f.

43
00:03:35,590 --> 00:03:36,550
Everything is visited.

44
00:03:37,240 --> 00:03:42,880
Go back to D because that's where we came from and then everything's visited there.

45
00:03:42,890 --> 00:03:48,310
We got to D from B, so we go back to B and everything is visited there.

46
00:03:48,520 --> 00:03:53,020
But except for this, J, so all of these are visible, except for this J.

47
00:03:53,030 --> 00:03:54,610
So we will go out to this J.

48
00:03:55,980 --> 00:04:02,580
The Jazz, the same cases, the H in the E and I, there's no other adjacent verses, so we have to

49
00:04:02,580 --> 00:04:03,600
go back to B.

50
00:04:04,440 --> 00:04:06,240
We originally came to be from A.

51
00:04:06,270 --> 00:04:07,440
So we'll go back to A..

52
00:04:07,890 --> 00:04:11,400
And then we originally came to a from C, so we'll go back to C.

53
00:04:11,400 --> 00:04:14,850
And now we have visited everything and gone back to where we started out.

54
00:04:16,500 --> 00:04:17,820
So that was a lot.

55
00:04:18,300 --> 00:04:21,330
How do we even do all of this in code, you're probably wondering.

56
00:04:21,540 --> 00:04:26,190
And one of the main things is how do we know where to get back from, where we came from?

57
00:04:27,410 --> 00:04:35,480
So that is actually the reason why I started out first by going over the stack in the queue data structure

58
00:04:35,480 --> 00:04:38,540
because those are both going to be necessary for this section.

59
00:04:39,380 --> 00:04:43,310
So the stack in particular is going to be used with depth first search.

60
00:04:44,240 --> 00:04:49,760
And you can think of this as the stack that we just went over in that previous subsection about Stacks

61
00:04:49,760 --> 00:04:56,090
and Qs, where we had an actual steel container, which was the stack and we were pushing things to

62
00:04:56,090 --> 00:04:57,560
it and probably things from it.

63
00:04:58,010 --> 00:05:03,080
Or you can think of it if you're going to implement depth first search as a recursive algorithm, you

64
00:05:03,080 --> 00:05:05,120
can think of it as the call stack.

65
00:05:05,120 --> 00:05:09,410
The recursive call stack like functions and stack frames from recursive calls.

66
00:05:10,040 --> 00:05:16,790
That stack functions in the same way for us for depth for search, so we can do both a recursive version

67
00:05:16,790 --> 00:05:22,340
and an iterative version where we the iterative version, we would implement our own stack in the recursive

68
00:05:22,340 --> 00:05:23,870
version and we could use a call stack.

69
00:05:24,840 --> 00:05:29,760
So you can think about it either way, I'm going to go ahead and walk through this depth first search

70
00:05:29,760 --> 00:05:35,070
traversal of this graph again, just like we did, but I'm going to use a stack over here and you can

71
00:05:35,070 --> 00:05:42,060
think of it as the recursive stack or the iterative kind of like we would have our own stack that we're

72
00:05:42,060 --> 00:05:42,750
pushing to.

73
00:05:44,130 --> 00:05:45,690
The way that I'm going to be talking about.

74
00:05:45,690 --> 00:05:52,410
It is slightly more aligned with the iterative algorithm, but it can work either way.

75
00:05:52,440 --> 00:05:54,060
So let's get started.

76
00:05:54,060 --> 00:05:56,940
I'm going to start out at sea again and I'll be labeling them again.

77
00:05:57,810 --> 00:06:07,500
So from see, I went to a room, and since I went to a from see, I am going to push that to the stack.

78
00:06:07,500 --> 00:06:14,490
So I push sea to the stack there from a I went to B since I came from a push eight in the stack.

79
00:06:15,690 --> 00:06:19,310
From B, we have all these choices, J.

80
00:06:19,320 --> 00:06:20,190
C and D..

81
00:06:20,670 --> 00:06:21,690
I go to H.

82
00:06:21,840 --> 00:06:27,660
So I push B to the stack because I came from B h we can't explore anymore, like we said.

83
00:06:27,660 --> 00:06:29,310
So we have to go back to B.

84
00:06:29,310 --> 00:06:36,840
And at this point, the reason I know how to go back to B is because B is at the top of the stack over

85
00:06:36,840 --> 00:06:37,200
here.

86
00:06:38,100 --> 00:06:43,200
So when I'm when I can't explore anything else, I'm basically going to be like, OK, what's at the

87
00:06:43,200 --> 00:06:43,970
top of the stack?

88
00:06:43,980 --> 00:06:45,270
Oh, be great.

89
00:06:45,270 --> 00:06:49,680
I'm going to pop that off now I'm at B, so that gets popped off the stack.

90
00:06:50,600 --> 00:06:52,270
So now we had to E!

91
00:06:52,340 --> 00:06:57,050
And same thing since we came from B to E, we're going to have to push B back to the stack.

92
00:06:57,230 --> 00:06:58,730
So I push back to the stack.

93
00:06:59,390 --> 00:07:01,930
Nothing to explore from here.

94
00:07:01,940 --> 00:07:04,910
So we come back to b same thing.

95
00:07:04,910 --> 00:07:10,390
Pop it off and then we're going to head over to D just like we did before.

96
00:07:10,400 --> 00:07:13,610
We need to push B back to the stack because we came from B.

97
00:07:15,590 --> 00:07:18,800
Already saw see, so we're going to head to F..

98
00:07:19,400 --> 00:07:24,620
So let's go ahead and head to F. And then we're going to push to the stack since we came from there

99
00:07:25,580 --> 00:07:31,190
already saw D and C, so we're going to head over to G.

100
00:07:31,550 --> 00:07:35,060
And after we do that, we're going to push F to the stack.

101
00:07:36,080 --> 00:07:36,830
Same thing.

102
00:07:36,830 --> 00:07:41,720
We'll head to AI and one plus g to the stack and then I we can't explore anymore.

103
00:07:42,200 --> 00:07:45,260
So we have to come back to G.

104
00:07:46,700 --> 00:07:51,230
And the way that we're doing that is looking at the top of the stack, which is Gee.

105
00:07:51,590 --> 00:07:53,930
And so we pop that off now we're at G.

106
00:07:55,460 --> 00:08:03,260
Where do we come from to get to G F and we're looking at that because we can't go, everything's been

107
00:08:03,260 --> 00:08:04,760
explored already, so.

108
00:08:05,680 --> 00:08:11,680
You know where we come from, effortless pop that off now, we're f same situation where we explored

109
00:08:11,680 --> 00:08:15,010
everything we came from D, because that's at the top of the stack.

110
00:08:15,010 --> 00:08:16,060
So pop that off.

111
00:08:16,060 --> 00:08:16,960
Now we're at the.

112
00:08:18,130 --> 00:08:23,470
Go back to be because that's how we got to D and that's at the top of the stack, that's how we know

113
00:08:23,470 --> 00:08:23,950
why.

114
00:08:25,240 --> 00:08:27,910
And then now that we're it be, we can explore.

115
00:08:28,190 --> 00:08:35,890
Jay, so let's go out to Jay because that's unexplored since we went out to Jay from B, where push

116
00:08:35,890 --> 00:08:41,320
B back to the stack can explore anything from Jay, so we have to head back.

117
00:08:41,330 --> 00:08:43,630
So what do we have to act to be?

118
00:08:43,980 --> 00:08:47,650
He's been pushed and popped a lot, but we're going to have to pop it again from the stack.

119
00:08:48,580 --> 00:08:55,690
And now everything from B has been explored as well, so now we're going to have to see where to head

120
00:08:55,690 --> 00:08:58,840
back to from B, which is a that's at the top of the stack.

121
00:08:58,840 --> 00:09:02,590
So head back to A and then everything's being explored from A..

122
00:09:02,710 --> 00:09:04,340
So where do we have to?

123
00:09:04,360 --> 00:09:05,170
What's at the top?

124
00:09:05,320 --> 00:09:06,850
C is the only item left.

125
00:09:06,850 --> 00:09:07,630
It's at the top.

126
00:09:07,900 --> 00:09:09,970
We have to see and we are done with our depth.

127
00:09:09,970 --> 00:09:11,620
First traversal depth.

128
00:09:11,620 --> 00:09:12,790
First search to Russell now.

129
00:09:14,890 --> 00:09:22,300
So like I said, you can think of those as kind of like recursive calls, whereas like each stack frame

130
00:09:22,300 --> 00:09:24,010
would have been for the particular node.

131
00:09:24,400 --> 00:09:30,940
Otherwise, if you're doing the iterative algorithm, it would be kind of like once you are going out

132
00:09:30,940 --> 00:09:31,540
to.

133
00:09:34,080 --> 00:09:41,250
Basically, explore another Vertex, you're going to have to push the one that you came from, so let's

134
00:09:41,250 --> 00:09:42,540
go ahead and continue.

135
00:09:43,170 --> 00:09:49,020
So another important thing to note is, you know, and I was saying, OK, we've already seen this or

136
00:09:49,020 --> 00:09:54,210
we've already seen that, and I had marked yellow ring for when we visited something.

137
00:09:54,960 --> 00:09:56,550
We need a way to keep track of that.

138
00:09:56,560 --> 00:10:01,890
So you might have been thinking about how to do that already, but a pretty good way is to have some

139
00:10:01,890 --> 00:10:03,840
container for that.

140
00:10:04,410 --> 00:10:12,720
And I like to just fill it all with zeros and then basically you have indices that align with the specific

141
00:10:12,720 --> 00:10:13,440
vertex.

142
00:10:13,920 --> 00:10:21,000
And if you visit one, you just change the zero at that specific vertex index to a one.

143
00:10:21,870 --> 00:10:25,590
So that's a way to keep track of which ones are visited and which ones are not.

144
00:10:25,590 --> 00:10:27,480
If it's a zero is unexplored.

145
00:10:27,480 --> 00:10:29,790
If it has a one there, it's already been explored.

146
00:10:29,790 --> 00:10:30,870
It's already been visited.

147
00:10:32,920 --> 00:10:40,570
So definitely want to think back to our two ways of implementing graphs, so we have the adjacency list

148
00:10:40,570 --> 00:10:48,340
and the adjacency matrix in addition to it, like I mentioned, there's two ways to implement the dips

149
00:10:48,340 --> 00:10:51,730
versus traversal, which is recursive and iterative.

150
00:10:51,730 --> 00:10:58,690
So we have two types of implementations for the graph and two ways to implement the depth of research

151
00:10:58,960 --> 00:10:59,830
traversal.

152
00:11:00,220 --> 00:11:04,900
There could be multiple ways like thinking about it, you know, kind of like many ways, depending

153
00:11:04,900 --> 00:11:06,190
on how you write your code, but.

154
00:11:07,500 --> 00:11:11,550
I'm just talking about the two types of depth First Search recursive the narrative.

155
00:11:12,960 --> 00:11:15,090
So let's look at some pseudocode here.

156
00:11:15,630 --> 00:11:18,060
We have the recursive on the left and on the right.

157
00:11:18,510 --> 00:11:20,910
I'll go ahead and start out with the recursive one.

158
00:11:21,360 --> 00:11:24,240
So you can just imagine this is like maybe a void function.

159
00:11:24,780 --> 00:11:28,590
And what's going to happen is this we this past, there's an argument.

160
00:11:28,590 --> 00:11:32,960
Up at the top is the first vertex, the initial start vertex.

161
00:11:32,970 --> 00:11:35,850
So we started C here.

162
00:11:35,850 --> 00:11:36,390
Remember?

163
00:11:36,390 --> 00:11:38,340
So that's what I'm talking about right now.

164
00:11:40,690 --> 00:11:50,380
So all of this pseudocode is basically indented, and so all of this right here is in the scope of this

165
00:11:50,380 --> 00:11:51,250
f block.

166
00:11:52,250 --> 00:11:52,740
Same here.

167
00:11:52,760 --> 00:11:59,390
All of this right here, this indented in is in the scope of the four and then this recursive calls

168
00:11:59,390 --> 00:12:00,650
and the scope of the if so.

169
00:12:02,180 --> 00:12:11,270
Not the strain of C++ and not straight up like Python or anything, it's just pseudo code, so just

170
00:12:11,270 --> 00:12:12,200
wanted to point that out.

171
00:12:13,640 --> 00:12:20,000
So if the Vertex is not visited, so all this only happens at the vertex is not vested in.

172
00:12:21,060 --> 00:12:26,010
You're going to process the vertex, and this can basically be anything this is just the work you want

173
00:12:26,010 --> 00:12:28,650
to do once you're on that vertex.

174
00:12:28,650 --> 00:12:34,080
So we're just traversing the graph, but these nodes that we're traversing to, they can have any kind

175
00:12:34,080 --> 00:12:38,520
of information there and you might need to like do certain things like call some functions and change

176
00:12:38,520 --> 00:12:39,360
that information.

177
00:12:39,360 --> 00:12:42,210
So whatever you need to do, that's going to happen right here.

178
00:12:42,810 --> 00:12:48,270
And when we implement the code in the next video, I'm just going to print the vertex out.

179
00:12:48,270 --> 00:12:53,400
So like, let's say it was like Vertex C, I would just print out, see, just to it, that's just for

180
00:12:53,400 --> 00:12:55,290
the purpose of explaining the algorithm.

181
00:12:55,290 --> 00:12:59,310
So we're we're not going to like do any fancy stuff because we want to focus on the algorithm.

182
00:12:59,730 --> 00:13:01,070
But you could put anything here.

183
00:13:01,080 --> 00:13:03,600
So just imagine an x thing you want to do goes here.

184
00:13:04,770 --> 00:13:09,670
After that, you mark v is visited, so think back to this container here.

185
00:13:10,500 --> 00:13:11,340
So.

186
00:13:12,510 --> 00:13:16,080
You know, if we were at sea, we would mark sea one for sea.

187
00:13:18,280 --> 00:13:27,370
Then you start a loop after that and you're going to go for every one of the neighbors of the current

188
00:13:27,370 --> 00:13:31,360
Vertex V, so you're going to live through all of those.

189
00:13:31,750 --> 00:13:38,710
So if you think about it, we have these two implementations here at the adjacency matrix in the Jason

190
00:13:38,710 --> 00:13:39,370
C list.

191
00:13:40,410 --> 00:13:47,370
And so since we're having to loop through all of the neighbors, it kind of changes the way we were

192
00:13:47,370 --> 00:13:54,240
thinking about that before, you know, it was nice that we could just subscript this subscript index,

193
00:13:54,240 --> 00:13:59,690
this matrix and have constant time to search for some given Vertex.

194
00:13:59,700 --> 00:14:05,790
But the thing is that we actually have to go through all the neighbors of a specific vertex anyways.

195
00:14:07,000 --> 00:14:12,400
So just want you to keep that in mind when you're thinking about like the efficiency of this or if you

196
00:14:12,400 --> 00:14:17,080
remember back, one of the other things we talked about was that the adjacency list is slightly more

197
00:14:17,080 --> 00:14:19,600
space efficient than the Matrix as well.

198
00:14:19,600 --> 00:14:21,850
So something else to consider as well.

199
00:14:23,080 --> 00:14:24,820
So either way, you want to imagine it.

200
00:14:25,270 --> 00:14:31,390
Let's say it's an adjacency list when you'd have to come down and go through that list after we index

201
00:14:32,140 --> 00:14:37,330
the original array or hash table or whatever you're using.

202
00:14:37,780 --> 00:14:41,500
We would have to look at the neighbor list there and go through all of them.

203
00:14:42,460 --> 00:14:47,050
So for each neighbor, if that neighbor is not visited, we're actually going to start this whole process

204
00:14:47,050 --> 00:14:50,230
over again with a recursive call and pass that neighbor.

205
00:14:50,440 --> 00:14:55,480
And that's basically synonymous with saying like, now let's explore from that vertex.

206
00:14:56,260 --> 00:14:59,080
So we explored from one Vertex was like, you know.

207
00:15:00,410 --> 00:15:02,930
Let's just say, hey, all the neighbors are there.

208
00:15:03,560 --> 00:15:09,890
But since we're doing death for service, it's just like, OK, let's recall this function immediately

209
00:15:09,890 --> 00:15:10,970
and just go deep.

210
00:15:11,400 --> 00:15:16,670
You know, let's do a recursive call and head to that first vortex that was the first of the neighbors

211
00:15:16,670 --> 00:15:17,570
or something like that.

212
00:15:17,780 --> 00:15:23,870
And I said it didn't matter which one you go to first, but I'm just saying that now, you know, if

213
00:15:23,870 --> 00:15:29,390
you're looping from like the beginning of this, you know, you of course, would like head to the first

214
00:15:29,390 --> 00:15:30,770
one and then the next one.

215
00:15:31,930 --> 00:15:36,490
Like, if you were on this in the foil loop and this was the first and you were just obviously call

216
00:15:36,500 --> 00:15:43,480
this recursively with that first vertex neighboring vertex and start this whole process again.

217
00:15:44,200 --> 00:15:47,590
So that is the recursive implementation.

218
00:15:49,490 --> 00:15:57,110
And then the iterative implementation is very similar, except, of course, the stack frames in this

219
00:15:57,110 --> 00:16:00,920
hour or if the stack in this is the stack frames itself.

220
00:16:01,370 --> 00:16:05,390
So, you know, it's going in the order of these recursive calls.

221
00:16:05,390 --> 00:16:12,500
So basically, when it gets down to the end, when it doesn't have any neighbors and it's not going

222
00:16:12,500 --> 00:16:17,210
to hit this visited thing, this void function would just return and you'd be going back up the stack

223
00:16:17,570 --> 00:16:19,490
and those stack frames would be popping off.

224
00:16:19,490 --> 00:16:26,000
So the recursive process would work similar to us pushing and popping from an actual stack that we implement

225
00:16:26,000 --> 00:16:26,510
over here.

226
00:16:28,200 --> 00:16:33,690
So for the iterative one, though, we will have to push to an actual stacks, we have to create a stack.

227
00:16:33,930 --> 00:16:41,160
This just assumes that we have one in the pseudocode and this is not going to be like necessarily perfect

228
00:16:41,160 --> 00:16:42,060
C++ code.

229
00:16:42,060 --> 00:16:45,180
Like I already said, it's just pseudocode, so just bear with me here.

230
00:16:45,720 --> 00:16:48,160
We'll actually do the implementation in the next video.

231
00:16:48,630 --> 00:16:54,900
So you push the first vertex to the stack, then you say, Wow, the stack is not empty because this

232
00:16:54,900 --> 00:16:57,210
is like the key that we're done with it.

233
00:16:57,210 --> 00:16:59,970
If the stack is empty, we have explored everything.

234
00:17:00,980 --> 00:17:07,850
So whilst it's not empty, pop the thing off the top of the stack and store it in this car, if that

235
00:17:07,850 --> 00:17:12,350
current is not visited, then market and then processes.

236
00:17:12,350 --> 00:17:16,640
So marketing is like Mark is visited, markers visited.

237
00:17:16,640 --> 00:17:20,690
It's like, I remember back to this, we would market in this container that we have.

238
00:17:22,600 --> 00:17:25,820
Then processing will just be printing out for us then.

239
00:17:27,430 --> 00:17:29,280
But you can do whatever you want here, of course.

240
00:17:29,290 --> 00:17:33,910
Like I said, then you go through all the neighbors again, just like in the recursive implementation.

241
00:17:35,530 --> 00:17:37,960
And the same exact thing if it's not visited.

242
00:17:38,440 --> 00:17:44,830
Rather than doing the recursive call, which would make a new stack frame, we are just going to push

243
00:17:44,830 --> 00:17:45,730
the neighbors to the stack.

244
00:17:45,740 --> 00:17:50,920
So the one thing that's slightly different is that this for a loop will just go and just push all the

245
00:17:50,920 --> 00:17:56,450
neighbors to the stack before we go back up to the top here.

246
00:17:56,950 --> 00:17:58,960
And that's like the one thing that's different.

247
00:17:58,960 --> 00:18:04,540
So all these neighbors will be already pushed to the stack and then we will go to the top of the while

248
00:18:04,540 --> 00:18:08,950
loop and we'll just pop like the first neighbor off and then keep going.

249
00:18:10,260 --> 00:18:14,310
So that's like the one thing that's slightly different than the recursive implementation, but they

250
00:18:14,310 --> 00:18:15,720
really work the same.

251
00:18:15,900 --> 00:18:25,140
So in the next video, we will actually be starting out with the recursive implementation and I will.

252
00:18:26,680 --> 00:18:34,000
Most likely be introducing a not new date structure, but something we've talked about before and be

253
00:18:34,000 --> 00:18:39,790
doing it in an adjacency list style, that's what I'll be using for the representation of the graph.

254
00:18:40,680 --> 00:18:44,400
So with that, I will see you in the next lecture.