Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:00,000 --> 00:00:02,639
in this python algorithms course you
2
00:00:02,639 --> 00:00:04,720
will learn to work with recursion data
3
00:00:04,720 --> 00:00:07,359
structures greedy algorithms dynamic
4
00:00:07,359 --> 00:00:09,360
programming and more
5
00:00:09,360 --> 00:00:11,759
you don't need any previous experience
6
00:00:11,759 --> 00:00:14,000
and algorithms to follow along
7
00:00:14,000 --> 00:00:15,759
algorithms help us solve problems
8
00:00:15,759 --> 00:00:18,480
efficiently and employers pay good money
9
00:00:18,480 --> 00:00:20,320
for good problem solvers
10
00:00:20,320 --> 00:00:22,720
your instructor for this course is joy
11
00:00:22,720 --> 00:00:23,760
brock
12
00:00:23,760 --> 00:00:26,000
she has an amazing talent for breaking
13
00:00:26,000 --> 00:00:28,560
down complex topics using humor and
14
00:00:28,560 --> 00:00:31,560
visualizations
15
00:00:32,659 --> 00:00:51,770
[Music]
16
00:00:55,280 --> 00:00:56,000
hi
17
00:00:56,000 --> 00:00:58,719
can i ask you a question raise your hand
18
00:00:58,719 --> 00:01:02,239
if you love being bossed around
19
00:01:02,239 --> 00:01:04,640
i'm not seeing any hands
20
00:01:04,640 --> 00:01:06,479
i know that i don't like to be bossed
21
00:01:06,479 --> 00:01:07,520
around
22
00:01:07,520 --> 00:01:08,960
now you might be wondering why i would
23
00:01:08,960 --> 00:01:11,200
ask a question like that and what does
24
00:01:11,200 --> 00:01:13,439
that have to do with computer algorithms
25
00:01:13,439 --> 00:01:15,119
but that's just it
26
00:01:15,119 --> 00:01:18,560
computers love to be lost around in fact
27
00:01:18,560 --> 00:01:21,200
a computer can't do anything on its own
28
00:01:21,200 --> 00:01:23,920
without being told what to do and that
29
00:01:23,920 --> 00:01:26,400
my friends is what an algorithm is
30
00:01:26,400 --> 00:01:28,479
an algorithm is a specific set of
31
00:01:28,479 --> 00:01:30,159
instructions that we write to the
32
00:01:30,159 --> 00:01:33,200
computer to tell it what to do after all
33
00:01:33,200 --> 00:01:35,600
that's why you're here right to learn
34
00:01:35,600 --> 00:01:37,520
how to tell that old ball and chain
35
00:01:37,520 --> 00:01:40,159
who's boss you know the one that keeps
36
00:01:40,159 --> 00:01:42,399
us perpetually locked in a prison of
37
00:01:42,399 --> 00:01:45,759
screen time so without further ado
38
00:01:45,759 --> 00:01:47,360
welcome to the introduction to
39
00:01:47,360 --> 00:01:49,920
algorithms course i am so glad you're
40
00:01:49,920 --> 00:01:52,720
here we are going to have an insane
41
00:01:52,720 --> 00:01:55,119
amount of fun so grab your beverage of
42
00:01:55,119 --> 00:01:58,159
choice grab a notepad for notes and be
43
00:01:58,159 --> 00:02:00,719
prepared to learn the five basic
44
00:02:00,719 --> 00:02:02,960
algorithms that every programmer should
45
00:02:02,960 --> 00:02:05,119
know
46
00:02:05,119 --> 00:02:07,200
by official definition an algorithm can
47
00:02:07,200 --> 00:02:09,758
be defined as being the current term of
48
00:02:09,758 --> 00:02:12,160
choice for a problem solving procedure
49
00:02:12,160 --> 00:02:14,160
it is commonly used nowadays for the set
50
00:02:14,160 --> 00:02:16,640
of rules a machine especially a computer
51
00:02:16,640 --> 00:02:19,360
follows to achieve a particular goal it
52
00:02:19,360 --> 00:02:21,280
does not always apply to computer
53
00:02:21,280 --> 00:02:24,319
mediated activity however the term may
54
00:02:24,319 --> 00:02:26,560
is accurately be used for the steps
55
00:02:26,560 --> 00:02:28,560
followed in making a pizza or solving a
56
00:02:28,560 --> 00:02:30,959
rubik's cube as for computer powered
57
00:02:30,959 --> 00:02:32,640
data analysis
58
00:02:32,640 --> 00:02:34,879
algorithms are often paired with words
59
00:02:34,879 --> 00:02:37,120
specifying the activity for which a set
60
00:02:37,120 --> 00:02:39,200
of rules have been designed
61
00:02:39,200 --> 00:02:41,200
a search algorithm for example is a
62
00:02:41,200 --> 00:02:43,200
procedure that determines what kind of
63
00:02:43,200 --> 00:02:45,200
information is retrieved from a large
64
00:02:45,200 --> 00:02:48,160
mass of data an encryption algorithm is
65
00:02:48,160 --> 00:02:50,239
a set of rules by which information or
66
00:02:50,239 --> 00:02:52,080
messages are encoded so that
67
00:02:52,080 --> 00:02:54,800
unauthorized persons cannot read them
68
00:02:54,800 --> 00:02:56,879
this comes from the merriam-webster
69
00:02:56,879 --> 00:03:01,599
dictionary what does algorithm mean
70
00:03:02,080 --> 00:03:04,560
mathematically speaking algorithms have
71
00:03:04,560 --> 00:03:07,920
been around for nearly 900 years pretty
72
00:03:07,920 --> 00:03:10,640
amazing isn't it in fact algorithms are
73
00:03:10,640 --> 00:03:13,120
all around us every day and have been
74
00:03:13,120 --> 00:03:15,519
our whole lives in this course we're
75
00:03:15,519 --> 00:03:17,440
going to dive into algorithms that are
76
00:03:17,440 --> 00:03:19,840
finite or determine sequences of
77
00:03:19,840 --> 00:03:22,000
explicit instructions that are used to
78
00:03:22,000 --> 00:03:24,080
solve problems and or perform
79
00:03:24,080 --> 00:03:26,879
computations these computations are
80
00:03:26,879 --> 00:03:29,680
generally to perform calculations or to
81
00:03:29,680 --> 00:03:32,239
manipulate data using natural language
82
00:03:32,239 --> 00:03:34,799
processing natural language processing
83
00:03:34,799 --> 00:03:37,760
or nlp for short is what tells the
84
00:03:37,760 --> 00:03:40,640
computer how to comprehend and interpret
85
00:03:40,640 --> 00:03:42,480
written text
86
00:03:42,480 --> 00:03:44,080
it's important to distinguish the
87
00:03:44,080 --> 00:03:46,000
difference between using well-defined
88
00:03:46,000 --> 00:03:48,560
formal languages to calculate functions
89
00:03:48,560 --> 00:03:50,879
versus algorithms used in artificial
90
00:03:50,879 --> 00:03:53,200
intelligence or machine learning
91
00:03:53,200 --> 00:03:55,200
those algorithms are where automated
92
00:03:55,200 --> 00:03:57,680
deductions are made using mathematical
93
00:03:57,680 --> 00:03:59,360
and logical tests
94
00:03:59,360 --> 00:04:01,760
or where predictions are made based on
95
00:04:01,760 --> 00:04:04,080
patterns learned from experience for
96
00:04:04,080 --> 00:04:05,920
example the other day when i was looking
97
00:04:05,920 --> 00:04:08,400
at the front page of google on their
98
00:04:08,400 --> 00:04:11,120
news i thought you know this algorithm
99
00:04:11,120 --> 00:04:13,680
better be so good that i can read about
100
00:04:13,680 --> 00:04:16,320
the news before it even happens
101
00:04:16,320 --> 00:04:18,560
those types of algorithms are for
102
00:04:18,560 --> 00:04:22,079
another video on another day
103
00:04:22,079 --> 00:04:24,560
the objective here in this course is to
104
00:04:24,560 --> 00:04:26,320
give you the tools you'll need to
105
00:04:26,320 --> 00:04:28,000
undertake the journey of using a
106
00:04:28,000 --> 00:04:30,240
well-defined formal language in this
107
00:04:30,240 --> 00:04:33,040
case python to calculate functions
108
00:04:33,040 --> 00:04:35,520
within a defined amount of space and
109
00:04:35,520 --> 00:04:37,600
time that may be asked of you for
110
00:04:37,600 --> 00:04:39,600
interviews or tests
111
00:04:39,600 --> 00:04:42,400
in other words the goal is for you to be
112
00:04:42,400 --> 00:04:43,440
able to
113
00:04:43,440 --> 00:04:45,440
find differences in algorithmic
114
00:04:45,440 --> 00:04:47,440
approaches based on computational
115
00:04:47,440 --> 00:04:48,800
efficiency
116
00:04:48,800 --> 00:04:51,600
this means that how we write our program
117
00:04:51,600 --> 00:04:54,880
is very important in regards to how much
118
00:04:54,880 --> 00:04:57,520
space it can use up on our computer or
119
00:04:57,520 --> 00:04:59,440
how quickly it can run
120
00:04:59,440 --> 00:05:01,759
and it all begins with the foundational
121
00:05:01,759 --> 00:05:04,639
principles that every algorithm has
122
00:05:04,639 --> 00:05:06,160
in input
123
00:05:06,160 --> 00:05:08,160
well-defined instructions
124
00:05:08,160 --> 00:05:10,880
execution of those instructions step by
125
00:05:10,880 --> 00:05:14,000
step leading to an output that ends in
126
00:05:14,000 --> 00:05:16,160
termination of the program
127
00:05:16,160 --> 00:05:19,039
now there are many different algorithms
128
00:05:19,039 --> 00:05:20,479
that accomplish
129
00:05:20,479 --> 00:05:22,639
these basics when it comes to
130
00:05:22,639 --> 00:05:25,440
programming and as much as i love
131
00:05:25,440 --> 00:05:27,600
spending time with you all
132
00:05:27,600 --> 00:05:29,840
it would be so difficult to cover every
133
00:05:29,840 --> 00:05:32,560
single one so for the sake of brevity
134
00:05:32,560 --> 00:05:35,280
we'll be covering the following
135
00:05:35,280 --> 00:05:37,840
simple recursive algorithms
136
00:05:37,840 --> 00:05:40,560
algorithms within data structures
137
00:05:40,560 --> 00:05:42,479
divide and conquer
138
00:05:42,479 --> 00:05:44,160
greedy algorithms
139
00:05:44,160 --> 00:05:47,440
and last but certainly not least dynamic
140
00:05:47,440 --> 00:05:49,280
programming
141
00:05:49,280 --> 00:05:51,440
for this course you'll need some
142
00:05:51,440 --> 00:05:53,680
understanding of the python language
143
00:05:53,680 --> 00:05:55,680
like writing functions variables
144
00:05:55,680 --> 00:06:00,400
conditionals for loops and basic syntax
145
00:06:02,160 --> 00:06:04,880
an ide or integrated development
146
00:06:04,880 --> 00:06:08,000
environment an ide is the virtual place
147
00:06:08,000 --> 00:06:09,600
to write our programs
148
00:06:09,600 --> 00:06:11,120
now if you don't have a downloaded
149
00:06:11,120 --> 00:06:13,840
platform like pycharm jupiter notebook
150
00:06:13,840 --> 00:06:16,240
or visual studio code you can just use
151
00:06:16,240 --> 00:06:19,280
any online python ide through a google
152
00:06:19,280 --> 00:06:21,199
search
153
00:06:21,199 --> 00:06:22,960
if you would like to download your own
154
00:06:22,960 --> 00:06:26,880
personal ide such as pycharm vsc or
155
00:06:26,880 --> 00:06:29,199
jupiter you can definitely do that as
156
00:06:29,199 --> 00:06:31,600
each one of those platforms are free to
157
00:06:31,600 --> 00:06:33,520
install
158
00:06:33,520 --> 00:06:35,520
go ahead and pause the video now if you
159
00:06:35,520 --> 00:06:38,000
need to get situated otherwise let's get
160
00:06:38,000 --> 00:06:40,240
this party started enroll into our very
161
00:06:40,240 --> 00:06:42,319
first lesson on simple recursive
162
00:06:42,319 --> 00:06:43,440
algorithms
163
00:06:43,440 --> 00:06:45,919
in our first lesson we're going to learn
164
00:06:45,919 --> 00:06:47,840
what is recursion and we're going to
165
00:06:47,840 --> 00:06:50,000
examine three different problems ranging
166
00:06:50,000 --> 00:06:54,080
from easy to mind-breaking
167
00:06:54,240 --> 00:06:55,680
we're going to look at the differences
168
00:06:55,680 --> 00:06:58,160
in computational efficiency and see
169
00:06:58,160 --> 00:07:00,319
which approach is best
170
00:07:00,319 --> 00:07:03,440
is implementing recursion the best way
171
00:07:03,440 --> 00:07:06,319
let's find out
172
00:07:07,730 --> 00:07:12,269
[Music]
173
00:07:12,400 --> 00:07:14,479
if the easiest way to define recursion
174
00:07:14,479 --> 00:07:15,919
is to say it's where a function calls
175
00:07:15,919 --> 00:07:18,160
itself then what's the hard way to
176
00:07:18,160 --> 00:07:20,240
define it in all truth it's easy to
177
00:07:20,240 --> 00:07:21,680
throw a statement out hand on hip that
178
00:07:21,680 --> 00:07:23,759
goes oh it's a function that calls
179
00:07:23,759 --> 00:07:24,880
itself
180
00:07:24,880 --> 00:07:27,759
sure okay good for you but what does
181
00:07:27,759 --> 00:07:30,160
that really mean i think oftentimes when
182
00:07:30,160 --> 00:07:32,080
it comes to programming it's easy to
183
00:07:32,080 --> 00:07:33,599
take for granted this idea that we
184
00:07:33,599 --> 00:07:35,440
should automatically know what it all
185
00:07:35,440 --> 00:07:36,319
means
186
00:07:36,319 --> 00:07:38,800
i don't know about you but i wasn't born
187
00:07:38,800 --> 00:07:40,880
with the ability to comprehend various
188
00:07:40,880 --> 00:07:43,440
methods to solve problems let alone be
189
00:07:43,440 --> 00:07:45,520
able to decipher which which method is
190
00:07:45,520 --> 00:07:47,599
better in the first place you know
191
00:07:47,599 --> 00:07:49,680
we all need to learn these concepts
192
00:07:49,680 --> 00:07:52,960
layer upon layer step by step so let's
193
00:07:52,960 --> 00:07:54,800
start at the very first layer and build
194
00:07:54,800 --> 00:07:56,720
up from there now when we write our
195
00:07:56,720 --> 00:07:58,479
program recursively it's important to
196
00:07:58,479 --> 00:08:00,639
understand that this is in contrast to
197
00:08:00,639 --> 00:08:02,639
writing it iteratively or through
198
00:08:02,639 --> 00:08:04,560
iteration when we do that we're
199
00:08:04,560 --> 00:08:06,560
generally using for loops to iterate
200
00:08:06,560 --> 00:08:08,720
over an object instead of making a
201
00:08:08,720 --> 00:08:10,879
function call back within the program
202
00:08:10,879 --> 00:08:12,400
you'll see what i mean when we get into
203
00:08:12,400 --> 00:08:15,599
our ides and and start to write the code
204
00:08:15,599 --> 00:08:16,960
recursion
205
00:08:16,960 --> 00:08:19,280
is it originates from a latin verb that
206
00:08:19,280 --> 00:08:22,080
means to run back and this is what the
207
00:08:22,080 --> 00:08:24,400
program we're going to write together is
208
00:08:24,400 --> 00:08:26,639
going to do it will run back to itself
209
00:08:26,639 --> 00:08:28,960
over and over as many times as it needs
210
00:08:28,960 --> 00:08:31,120
until the program terminates so does
211
00:08:31,120 --> 00:08:33,279
this mean that we can't use for loops
212
00:08:33,279 --> 00:08:35,599
with recursion no of course you can use
213
00:08:35,599 --> 00:08:38,080
them in fact they will be needed and
214
00:08:38,080 --> 00:08:40,320
you'll see how that all works in just a
215
00:08:40,320 --> 00:08:42,320
moment in order to get started with our
216
00:08:42,320 --> 00:08:44,800
very first lesson involving factorials
217
00:08:44,800 --> 00:08:47,279
and the algorithmic method that we are
218
00:08:47,279 --> 00:08:49,120
going to use for better efficiency we
219
00:08:49,120 --> 00:08:50,880
will calculate the factorial of a number
220
00:08:50,880 --> 00:08:53,519
using the leaf method or last in first
221
00:08:53,519 --> 00:08:55,200
out and it all begins with a mental
222
00:08:55,200 --> 00:08:57,040
picture of a bookshelf that doesn't have
223
00:08:57,040 --> 00:08:59,680
any books on it yet to perform a lethal
224
00:08:59,680 --> 00:09:02,080
operation on your hypothetical bookshelf
225
00:09:02,080 --> 00:09:03,519
you will grab some books and begin
226
00:09:03,519 --> 00:09:05,519
placing them on the shelf let's say you
227
00:09:05,519 --> 00:09:08,560
ordered some britannica encyclopedias
228
00:09:08,560 --> 00:09:10,240
wait why would you do that
229
00:09:10,240 --> 00:09:12,640
why did any of us do that oh right it
230
00:09:12,640 --> 00:09:14,560
was our grandparents that saw to it to
231
00:09:14,560 --> 00:09:16,320
make sure that we had our own modern day
232
00:09:16,320 --> 00:09:18,640
google machine thanks grandma your
233
00:09:18,640 --> 00:09:21,600
legacy lives on at the donation center
234
00:09:21,600 --> 00:09:23,519
okay that was a wonderful trip down
235
00:09:23,519 --> 00:09:26,080
memory lane wasn't it okay so back to
236
00:09:26,080 --> 00:09:28,399
lefo or lifo if that's what you call it
237
00:09:28,399 --> 00:09:30,080
so you put your encyclopedias on the
238
00:09:30,080 --> 00:09:32,800
shelf a to z in a last in first out
239
00:09:32,800 --> 00:09:34,880
scenario what was the last book you you
240
00:09:34,880 --> 00:09:37,440
sat on the shelf z what's the first book
241
00:09:37,440 --> 00:09:39,839
that's going to come off z
242
00:09:39,839 --> 00:09:42,160
so last in first out and this would be
243
00:09:42,160 --> 00:09:43,600
important to remember in our number
244
00:09:43,600 --> 00:09:45,839
oriented recursive function coming up
245
00:09:45,839 --> 00:09:47,839
that the last number that goes in will
246
00:09:47,839 --> 00:09:49,600
be the first number that gets called out
247
00:09:49,600 --> 00:09:51,200
or computed
248
00:09:51,200 --> 00:09:53,040
now if you're a little bit confused it's
249
00:09:53,040 --> 00:09:55,200
okay you won't be for long we're going
250
00:09:55,200 --> 00:09:57,680
to see this in action right now and talk
251
00:09:57,680 --> 00:09:59,760
about the computationally efficient way
252
00:09:59,760 --> 00:10:02,160
to solve as we write our first recursive
253
00:10:02,160 --> 00:10:04,800
program to calculate the factorial of a
254
00:10:04,800 --> 00:10:07,120
number
255
00:10:09,839 --> 00:10:12,560
for a quick recap on factorials say you
256
00:10:12,560 --> 00:10:14,560
take the number 5 and multiply it by
257
00:10:14,560 --> 00:10:17,200
itself minus 1 all the way down until
258
00:10:17,200 --> 00:10:18,640
you hit one
259
00:10:18,640 --> 00:10:21,760
your answer will equal 120. remember
260
00:10:21,760 --> 00:10:23,519
factorials only involve positive
261
00:10:23,519 --> 00:10:25,760
integers so once you hit one the program
262
00:10:25,760 --> 00:10:27,040
terminates
263
00:10:27,040 --> 00:10:30,399
now let's get to work
264
00:10:30,399 --> 00:10:33,120
we're going to look at two ways that we
265
00:10:33,120 --> 00:10:35,040
can write a program that will calculate
266
00:10:35,040 --> 00:10:37,360
the factorial of a number this is going
267
00:10:37,360 --> 00:10:40,399
to be a wonderful foray into differences
268
00:10:40,399 --> 00:10:42,480
regarding complexity and program
269
00:10:42,480 --> 00:10:45,120
efficiency in our first method we're
270
00:10:45,120 --> 00:10:48,160
going to tackle this iteratively or like
271
00:10:48,160 --> 00:10:50,079
i mentioned before through iteration
272
00:10:50,079 --> 00:10:52,320
this means that our program will cycle
273
00:10:52,320 --> 00:10:55,279
through or iterate each and every step
274
00:10:55,279 --> 00:10:58,000
we tell it to
275
00:10:58,079 --> 00:11:00,320
first we define our function with one
276
00:11:00,320 --> 00:11:02,079
parameter the number we want to
277
00:11:02,079 --> 00:11:04,320
calculate in this case we'll just call
278
00:11:04,320 --> 00:11:05,519
it n
279
00:11:05,519 --> 00:11:07,360
then we're going to create a variable
280
00:11:07,360 --> 00:11:10,000
and start it at one positive numbers
281
00:11:10,000 --> 00:11:13,279
remember no zeros here next we construct
282
00:11:13,279 --> 00:11:16,079
a for loop to iterate over that variable
283
00:11:16,079 --> 00:11:18,160
or object if you like
284
00:11:18,160 --> 00:11:20,640
and do something to it in this case
285
00:11:20,640 --> 00:11:22,959
we're going to multiply it by every
286
00:11:22,959 --> 00:11:25,360
number in a range starting at 2 and
287
00:11:25,360 --> 00:11:27,920
adding in our ending at our number plus
288
00:11:27,920 --> 00:11:30,399
one this gives us a range of four
289
00:11:30,399 --> 00:11:34,160
numbers two three four five now why not
290
00:11:34,160 --> 00:11:37,440
six since n or five plus one equals six
291
00:11:37,440 --> 00:11:39,360
remember we're using python so if we
292
00:11:39,360 --> 00:11:41,600
loop to a range of two
293
00:11:41,600 --> 00:11:44,640
comma 6 in parenthesis our indices will
294
00:11:44,640 --> 00:11:46,800
always be minus 1 because python starts
295
00:11:46,800 --> 00:11:49,600
at 0. so an index position of 6 will
296
00:11:49,600 --> 00:11:51,200
give us our last number for our
297
00:11:51,200 --> 00:11:54,240
calculation 5. then we take our object
298
00:11:54,240 --> 00:11:56,639
called fact and multiply it by every
299
00:11:56,639 --> 00:11:58,959
number in our range because we can use
300
00:11:58,959 --> 00:12:01,519
the asterisk and equal sign to condense
301
00:12:01,519 --> 00:12:04,480
our code a little fact equals fact time
302
00:12:04,480 --> 00:12:07,120
asterisk i that assignment operator is
303
00:12:07,120 --> 00:12:09,600
reassigning our variable each time it
304
00:12:09,600 --> 00:12:11,519
cycles through our loop
305
00:12:11,519 --> 00:12:13,519
when the cycling or iteration is
306
00:12:13,519 --> 00:12:15,920
finished we simply return our finished
307
00:12:15,920 --> 00:12:18,399
fact variable if you want to see the
308
00:12:18,399 --> 00:12:20,000
results of each
309
00:12:20,000 --> 00:12:21,920
iteration you can just place a print
310
00:12:21,920 --> 00:12:23,600
statement within the for loop and run
311
00:12:23,600 --> 00:12:24,959
the program
312
00:12:24,959 --> 00:12:27,120
for a recursive method it's going to be
313
00:12:27,120 --> 00:12:29,200
already typed out while i talk
314
00:12:29,200 --> 00:12:31,279
this is where our last in first out
315
00:12:31,279 --> 00:12:33,040
comes into play remember when we talked
316
00:12:33,040 --> 00:12:35,200
about that this is in contrast to our
317
00:12:35,200 --> 00:12:37,360
iterative method that starts at the top
318
00:12:37,360 --> 00:12:39,279
are fact variables starting at 1 and
319
00:12:39,279 --> 00:12:41,440
then iterates through our range going up
320
00:12:41,440 --> 00:12:43,519
until our number is reached in the
321
00:12:43,519 --> 00:12:46,079
algorithmic method of recursion
322
00:12:46,079 --> 00:12:48,079
when we go to call the function if our
323
00:12:48,079 --> 00:12:50,240
number isn't 1 it moves to our else
324
00:12:50,240 --> 00:12:52,079
statement where in our else statement we
325
00:12:52,079 --> 00:12:54,639
have a temp variable that runs back to
326
00:12:54,639 --> 00:12:56,800
our function call and creates a pocket
327
00:12:56,800 --> 00:12:59,120
of space if you will for each number
328
00:12:59,120 --> 00:13:00,320
minus one
329
00:13:00,320 --> 00:13:02,480
it will run back all the way down until
330
00:13:02,480 --> 00:13:05,600
it hits one our last n if you will once
331
00:13:05,600 --> 00:13:07,600
that happens the return statement and
332
00:13:07,600 --> 00:13:09,200
our else statement starts working its
333
00:13:09,200 --> 00:13:11,760
magic and then we start heading back up
334
00:13:11,760 --> 00:13:14,560
our last in which was one becomes our
335
00:13:14,560 --> 00:13:15,920
first out
336
00:13:15,920 --> 00:13:18,800
our first number to get computed
337
00:13:18,800 --> 00:13:19,820
ta-da
338
00:13:19,820 --> 00:13:22,880
[Applause]
339
00:13:22,880 --> 00:13:24,720
now you might be tempted to think that
340
00:13:24,720 --> 00:13:27,440
the recursive method is top dog here but
341
00:13:27,440 --> 00:13:30,320
alas you'd be wrong our iterative method
342
00:13:30,320 --> 00:13:32,160
is twice as fast
343
00:13:32,160 --> 00:13:33,600
for what we're trying to accomplish
344
00:13:33,600 --> 00:13:34,399
which is
345
00:13:34,399 --> 00:13:36,880
just a basic calculation of a factorial
346
00:13:36,880 --> 00:13:38,800
what's important what's important to be
347
00:13:38,800 --> 00:13:41,199
able to understand is a how recursion
348
00:13:41,199 --> 00:13:43,360
works by using a simple program such as
349
00:13:43,360 --> 00:13:46,480
momentous did and b how how and why one
350
00:13:46,480 --> 00:13:48,720
approach can be better than another
351
00:13:48,720 --> 00:13:51,040
in this case recursion is taking up more
352
00:13:51,040 --> 00:13:53,199
space and time by running back to the
353
00:13:53,199 --> 00:13:55,360
function call to create those pockets
354
00:13:55,360 --> 00:13:56,639
for our numbers
355
00:13:56,639 --> 00:13:58,639
versus iteration where it's simply
356
00:13:58,639 --> 00:14:00,800
multiplying each number in place and not
357
00:14:00,800 --> 00:14:03,199
creating anything new
358
00:14:03,199 --> 00:14:05,519
it's simply iterating over each number
359
00:14:05,519 --> 00:14:07,519
reassigning our variable each time and
360
00:14:07,519 --> 00:14:09,360
producing a final output
361
00:14:09,360 --> 00:14:11,680
the objective for our basic exercise is
362
00:14:11,680 --> 00:14:13,760
to just understand and see recursive
363
00:14:13,760 --> 00:14:16,399
algorithms in action so that as you gain
364
00:14:16,399 --> 00:14:18,560
experience you'll be able to exercise
365
00:14:18,560 --> 00:14:20,480
different modes of expression or
366
00:14:20,480 --> 00:14:22,480
expressivity in your writing
367
00:14:22,480 --> 00:14:25,120
and in some cases use your readability
368
00:14:25,120 --> 00:14:28,760
check out this example
369
00:14:34,240 --> 00:14:36,720
on the upside being able to write
370
00:14:36,720 --> 00:14:38,800
code in three lines instead of seven or
371
00:14:38,800 --> 00:14:40,399
eight can be a huge deal depending on
372
00:14:40,399 --> 00:14:42,480
the circumstance however on the flip
373
00:14:42,480 --> 00:14:45,519
side may decrease the performance of the
374
00:14:45,519 --> 00:14:48,320
code let's like this example that we
375
00:14:48,320 --> 00:14:50,000
just coded together
376
00:14:50,000 --> 00:14:52,160
it's just not as efficient as iteration
377
00:14:52,160 --> 00:14:54,240
in this case so if you're ready let's
378
00:14:54,240 --> 00:14:56,240
move up to a more advanced recursive
379
00:14:56,240 --> 00:15:00,399
algorithm involving permutations
380
00:15:02,000 --> 00:15:04,560
a permutation is when you take a set of
381
00:15:04,560 --> 00:15:06,480
elements and find all the different
382
00:15:06,480 --> 00:15:08,800
variations that can be made with it for
383
00:15:08,800 --> 00:15:11,920
instance if we take a b and c we can get
384
00:15:11,920 --> 00:15:14,320
six variations out of these three
385
00:15:14,320 --> 00:15:16,560
letters mathematically speaking we can
386
00:15:16,560 --> 00:15:17,920
find the number of variations by
387
00:15:17,920 --> 00:15:19,519
calculating the factorial of the
388
00:15:19,519 --> 00:15:21,279
elements just like we did a few minutes
389
00:15:21,279 --> 00:15:23,360
ago
390
00:15:23,360 --> 00:15:25,519
for a hands-on approach to understanding
391
00:15:25,519 --> 00:15:27,680
a level up on recursion let's take a
392
00:15:27,680 --> 00:15:29,519
peek under the hood and see how this
393
00:15:29,519 --> 00:15:32,980
will work in a program shelby
394
00:15:32,980 --> 00:15:34,800
[Music]
395
00:15:34,800 --> 00:15:36,880
the underlying basis of how most
396
00:15:36,880 --> 00:15:39,199
functions for permutations work is to
397
00:15:39,199 --> 00:15:41,440
take off the first element and then
398
00:15:41,440 --> 00:15:43,920
create two subsets of numbers that get
399
00:15:43,920 --> 00:15:46,880
swapped like this
400
00:15:46,880 --> 00:15:49,120
then the original first element gets put
401
00:15:49,120 --> 00:15:51,680
back onto the front of each subset then
402
00:15:51,680 --> 00:15:53,920
we do this all over again this time
403
00:15:53,920 --> 00:15:55,920
instead of popping out the first element
404
00:15:55,920 --> 00:15:57,920
we pop out the second one and create two
405
00:15:57,920 --> 00:16:01,120
new subsets and so on and so forth
406
00:16:01,120 --> 00:16:03,360
the algorithm behind permutations can
407
00:16:03,360 --> 00:16:05,279
really make your head spin so take a
408
00:16:05,279 --> 00:16:06,560
deep breath
409
00:16:06,560 --> 00:16:09,600
find your center and jump in
410
00:16:09,600 --> 00:16:10,480
to
411
00:16:10,480 --> 00:16:11,839
a puddle
412
00:16:11,839 --> 00:16:14,399
let's not jump into the ocean just yet
413
00:16:14,399 --> 00:16:16,800
it's good to start small and by small
414
00:16:16,800 --> 00:16:19,360
let's recursively swap just two letters
415
00:16:19,360 --> 00:16:21,600
of a string this is a little bit harder
416
00:16:21,600 --> 00:16:23,759
to do than a list because strings are
417
00:16:23,759 --> 00:16:25,440
immutable but
418
00:16:25,440 --> 00:16:27,360
this is a good launch point for us to
419
00:16:27,360 --> 00:16:29,920
build up from here also we'll start with
420
00:16:29,920 --> 00:16:32,000
recursion this time and then afterwards
421
00:16:32,000 --> 00:16:33,519
we'll look at a different method for
422
00:16:33,519 --> 00:16:36,519
comparison
423
00:16:37,040 --> 00:16:38,720
to write a recursive function that will
424
00:16:38,720 --> 00:16:40,800
swap just two letters we will need to
425
00:16:40,800 --> 00:16:43,120
create a pocket for where our strings
426
00:16:43,120 --> 00:16:45,839
need to go remember again strings are
427
00:16:45,839 --> 00:16:47,920
immutable and if this were a list we
428
00:16:47,920 --> 00:16:49,759
could simply slice it and create a
429
00:16:49,759 --> 00:16:52,320
variable swap but that's a no go for
430
00:16:52,320 --> 00:16:54,560
strings we're moving into a little bit
431
00:16:54,560 --> 00:16:57,199
steeper territory here but stay with me
432
00:16:57,199 --> 00:16:59,519
okay you can do this
433
00:16:59,519 --> 00:17:01,519
let's create our function and call it
434
00:17:01,519 --> 00:17:04,079
permute with two parameters one called
435
00:17:04,079 --> 00:17:06,480
string and for the string of two letters
436
00:17:06,480 --> 00:17:08,880
that we want to swap and an empty pocket
437
00:17:08,880 --> 00:17:10,959
to put our new string in this is our
438
00:17:10,959 --> 00:17:13,679
parameter default defaulted to an empty
439
00:17:13,679 --> 00:17:15,839
string then we create an if statement
440
00:17:15,839 --> 00:17:17,919
for an edge case in the event that the
441
00:17:17,919 --> 00:17:19,839
string is empty and if it's empty we
442
00:17:19,839 --> 00:17:22,559
just return our empty pocket now we'll
443
00:17:22,559 --> 00:17:25,039
start with looping through the range of
444
00:17:25,039 --> 00:17:27,359
the length of our string and within our
445
00:17:27,359 --> 00:17:29,440
loop we'll start with creating three
446
00:17:29,440 --> 00:17:32,559
variables that will contain one each
447
00:17:32,559 --> 00:17:34,640
letter on our string two we'll need to
448
00:17:34,640 --> 00:17:35,840
take off the front of the string that
449
00:17:35,840 --> 00:17:37,840
we're going to call front and then three
450
00:17:37,840 --> 00:17:39,919
a variable called back that will slice
451
00:17:39,919 --> 00:17:42,000
off the back of our string if you study
452
00:17:42,000 --> 00:17:43,440
this algorithm you'll see some
453
00:17:43,440 --> 00:17:45,760
programmers call it head and tail
454
00:17:45,760 --> 00:17:49,200
current and the rust first next or front
455
00:17:49,200 --> 00:17:51,280
and back i like the terms front and back
456
00:17:51,280 --> 00:17:53,039
as it gives me a better mental picture
457
00:17:53,039 --> 00:17:54,799
but you can use whatever terms you're
458
00:17:54,799 --> 00:17:57,360
more comfortable with
459
00:17:57,360 --> 00:17:59,200
now those first three variables are
460
00:17:59,200 --> 00:18:01,520
fairly obvious but this is where it
461
00:18:01,520 --> 00:18:03,760
might get a little hazy we need to
462
00:18:03,760 --> 00:18:05,760
create a fourth variable that will put
463
00:18:05,760 --> 00:18:08,320
our front and back together and we'll
464
00:18:08,320 --> 00:18:10,400
need this variable of combined elements
465
00:18:10,400 --> 00:18:13,360
to plug into our function call
466
00:18:13,360 --> 00:18:16,240
this is what creates spaces to in our
467
00:18:16,240 --> 00:18:17,919
pocket to be able to move our letters
468
00:18:17,919 --> 00:18:19,840
around i know this may sound a little
469
00:18:19,840 --> 00:18:22,080
complicated at the moment but you'll see
470
00:18:22,080 --> 00:18:23,679
shortly that we're going to need each
471
00:18:23,679 --> 00:18:25,919
and every letter of our string even
472
00:18:25,919 --> 00:18:28,000
however many that will eventually come
473
00:18:28,000 --> 00:18:30,720
to be to have the space it needs to go
474
00:18:30,720 --> 00:18:33,440
into the right place in our pocket now
475
00:18:33,440 --> 00:18:34,960
whether that's going to lead up to
476
00:18:34,960 --> 00:18:37,520
eventually being three letters or four
477
00:18:37,520 --> 00:18:39,440
keep in mind our strengths can't be too
478
00:18:39,440 --> 00:18:41,840
long because of two things the rate of
479
00:18:41,840 --> 00:18:43,600
exponential growth and the fact that
480
00:18:43,600 --> 00:18:46,480
recursion can get exhaustive very fast
481
00:18:46,480 --> 00:18:48,640
the more letters you have recursively
482
00:18:48,640 --> 00:18:51,520
that's a lot of running back okay we
483
00:18:51,520 --> 00:18:53,679
have all the variables we need right now
484
00:18:53,679 --> 00:18:56,000
our letter a front which is just an
485
00:18:56,000 --> 00:18:58,240
empty string right now our back which is
486
00:18:58,240 --> 00:19:00,400
the last set of our string b
487
00:19:00,400 --> 00:19:02,559
and are together that combines our front
488
00:19:02,559 --> 00:19:04,960
and back now for our algorithm this is
489
00:19:04,960 --> 00:19:08,000
where the magic happens this is the true
490
00:19:08,000 --> 00:19:11,200
ham in our sandwich we call our function
491
00:19:11,200 --> 00:19:12,640
premium and then incorporate two
492
00:19:12,640 --> 00:19:14,960
parameters are together
493
00:19:14,960 --> 00:19:17,679
and our letter added to our pocket hence
494
00:19:17,679 --> 00:19:19,600
the addition operator
495
00:19:19,600 --> 00:19:21,760
this is the heartbeat of our algorithm
496
00:19:21,760 --> 00:19:24,000
it needs to run back and put our letters
497
00:19:24,000 --> 00:19:26,559
into our pocket once in reverse and then
498
00:19:26,559 --> 00:19:28,480
the second time in a copy of its
499
00:19:28,480 --> 00:19:29,840
original form because it's still
500
00:19:29,840 --> 00:19:32,080
considered a permutation watch how this
501
00:19:32,080 --> 00:19:35,559
works in the visualizer
502
00:19:43,120 --> 00:19:44,799
i think that if you get really get a
503
00:19:44,799 --> 00:19:46,320
really good handle on this concept and
504
00:19:46,320 --> 00:19:48,400
you have a solid foundation
505
00:19:48,400 --> 00:19:50,240
it becomes so much easier to see how
506
00:19:50,240 --> 00:19:52,480
this works with additional letters if
507
00:19:52,480 --> 00:19:54,720
you can see it mentally this makes all
508
00:19:54,720 --> 00:19:57,679
the difference in the world
509
00:19:58,240 --> 00:20:00,480
it's a neat little program that only has
510
00:20:00,480 --> 00:20:03,760
11 lines of code which is really nice
511
00:20:03,760 --> 00:20:07,039
however this program isn't as efficient
512
00:20:07,039 --> 00:20:09,039
as a program that uses iteration and
513
00:20:09,039 --> 00:20:12,000
swapping again
514
00:20:12,000 --> 00:20:14,640
that program has nearly double the lines
515
00:20:14,640 --> 00:20:17,360
of code i'll spare you the direction of
516
00:20:17,360 --> 00:20:19,600
watching me type it all out and just
517
00:20:19,600 --> 00:20:22,400
show you here
518
00:20:25,919 --> 00:20:28,400
this would be the code that executes
519
00:20:28,400 --> 00:20:29,760
just like the beginning
520
00:20:29,760 --> 00:20:31,039
[Music]
521
00:20:31,039 --> 00:20:33,039
that you saw on the earlier slides where
522
00:20:33,039 --> 00:20:35,280
it pops off the first letter and then
523
00:20:35,280 --> 00:20:37,360
swaps the it pops out the first letter
524
00:20:37,360 --> 00:20:39,520
swaps the last two and then
525
00:20:39,520 --> 00:20:41,840
pops the first letter back on then it
526
00:20:41,840 --> 00:20:44,080
rotates to the second letter
527
00:20:44,080 --> 00:20:45,760
swaps those two
528
00:20:45,760 --> 00:20:48,320
and then puts it back on
529
00:20:48,320 --> 00:20:50,400
check the output here and you'll see
530
00:20:50,400 --> 00:20:52,799
what i mean now if you needed to know
531
00:20:52,799 --> 00:20:54,640
all the permutations of a string and
532
00:20:54,640 --> 00:20:56,720
don't really have time to write the code
533
00:20:56,720 --> 00:20:59,360
or the patience you could use the inner
534
00:20:59,360 --> 00:21:02,080
tools permutations module it's really
535
00:21:02,080 --> 00:21:03,039
easy
536
00:21:03,039 --> 00:21:03,840
but
537
00:21:03,840 --> 00:21:06,400
that would be primarily for you
538
00:21:06,400 --> 00:21:08,559
just to know for yourself or for a quick
539
00:21:08,559 --> 00:21:10,960
look up when it comes to interviews or
540
00:21:10,960 --> 00:21:14,000
testing companies would generally prefer
541
00:21:14,000 --> 00:21:16,000
that you know the mechanics behind the
542
00:21:16,000 --> 00:21:18,320
method for solving whether that's using
543
00:21:18,320 --> 00:21:21,280
recursion or swapping
544
00:21:21,280 --> 00:21:23,520
as with any program the caveat must
545
00:21:23,520 --> 00:21:25,440
always be made can this program be
546
00:21:25,440 --> 00:21:26,960
written differently
547
00:21:26,960 --> 00:21:30,080
as always yes however you will see very
548
00:21:30,080 --> 00:21:31,679
little difference when it comes to
549
00:21:31,679 --> 00:21:34,720
recursion of most programs like this
550
00:21:34,720 --> 00:21:37,760
very generally speaking they will call
551
00:21:37,760 --> 00:21:40,320
the function in a very similar way as it
552
00:21:40,320 --> 00:21:42,880
is written here by taking the front and
553
00:21:42,880 --> 00:21:45,280
back together and incorporating it in
554
00:21:45,280 --> 00:21:46,559
some way
555
00:21:46,559 --> 00:21:48,720
within the function call
556
00:21:48,720 --> 00:21:50,559
along with the letter
557
00:21:50,559 --> 00:21:52,720
hopefully you were able to distinctly
558
00:21:52,720 --> 00:21:55,520
see how recursion works in this program
559
00:21:55,520 --> 00:21:57,520
even just for two letters
560
00:21:57,520 --> 00:22:00,799
it can work great on small strings but
561
00:22:00,799 --> 00:22:03,360
it will get computationally expensive
562
00:22:03,360 --> 00:22:05,840
the longer the string now if you're not
563
00:22:05,840 --> 00:22:07,760
too overwhelmed hopefully not we've only
564
00:22:07,760 --> 00:22:08,880
done two
565
00:22:08,880 --> 00:22:11,520
we're going to move into the mind
566
00:22:11,520 --> 00:22:13,760
breaker section like it should be the
567
00:22:13,760 --> 00:22:16,799
mind blowing section
568
00:22:16,799 --> 00:22:18,559
the end cleans
569
00:22:18,559 --> 00:22:20,960
problem
570
00:22:23,280 --> 00:22:25,280
this computational problem is about
571
00:22:25,280 --> 00:22:27,760
placing eight chess queens on an eight
572
00:22:27,760 --> 00:22:30,960
by eight board so that no two queens are
573
00:22:30,960 --> 00:22:33,280
able to attack each other according to
574
00:22:33,280 --> 00:22:35,280
wikipedia the problem finding all
575
00:22:35,280 --> 00:22:37,120
solutions to the eight queens problem
576
00:22:37,120 --> 00:22:40,080
can be quite computationally expensive
577
00:22:40,080 --> 00:22:42,480
there are 4 billion possible
578
00:22:42,480 --> 00:22:45,120
arrangements of the 8 queens on an 8x8
579
00:22:45,120 --> 00:22:48,240
board but only 92 solutions wikipedia
580
00:22:48,240 --> 00:22:49,840
also goes on to say that the use of
581
00:22:49,840 --> 00:22:51,520
shortcuts and various rules of thumb
582
00:22:51,520 --> 00:22:53,919
that avoid brute force techniques can
583
00:22:53,919 --> 00:22:55,679
greatly reduce the number of possible
584
00:22:55,679 --> 00:22:58,159
combinations which i'm sure is always a
585
00:22:58,159 --> 00:23:00,559
good thing but what is brute force
586
00:23:00,559 --> 00:23:01,760
though
587
00:23:01,760 --> 00:23:04,400
well that's would be brute force would
588
00:23:04,400 --> 00:23:06,559
be looking at every single possible
589
00:23:06,559 --> 00:23:09,360
arrangement 4 billion of them to find
590
00:23:09,360 --> 00:23:11,840
the 92 solutions how long do you think
591
00:23:11,840 --> 00:23:13,039
that would take
592
00:23:13,039 --> 00:23:14,960
probably take decades for our computers
593
00:23:14,960 --> 00:23:17,039
to run a program like that but guess
594
00:23:17,039 --> 00:23:19,440
what the use of permutations can reduce
595
00:23:19,440 --> 00:23:21,679
the possibilities from 4 billion down to
596
00:23:21,679 --> 00:23:25,200
just 40 000. that's a big reduction
597
00:23:25,200 --> 00:23:27,039
now we're not are we going to use
598
00:23:27,039 --> 00:23:28,720
permutations on the end queen's problem
599
00:23:28,720 --> 00:23:31,760
today no way jose
600
00:23:31,760 --> 00:23:33,280
but it's good to know that this problem
601
00:23:33,280 --> 00:23:35,200
is often used in examples for various
602
00:23:35,200 --> 00:23:37,200
programming techniques such as solving
603
00:23:37,200 --> 00:23:40,000
it by using recursive algorithms it's
604
00:23:40,000 --> 00:23:41,039
also used
605
00:23:41,039 --> 00:23:42,960
as an example in constraint programming
606
00:23:42,960 --> 00:23:44,640
which is a paradigm for solving
607
00:23:44,640 --> 00:23:47,120
combinatorial problems that draws on a
608
00:23:47,120 --> 00:23:49,360
wide range of techniques from artificial
609
00:23:49,360 --> 00:23:51,440
intelligence computer science and
610
00:23:51,440 --> 00:23:53,679
operations research
611
00:23:53,679 --> 00:23:55,440
to get a better idea of what that would
612
00:23:55,440 --> 00:23:58,080
be we can use a real world example like
613
00:23:58,080 --> 00:24:00,480
employee scheduling say for instance a
614
00:24:00,480 --> 00:24:02,799
company operates continuously like a
615
00:24:02,799 --> 00:24:04,799
factory they need to create weekly
616
00:24:04,799 --> 00:24:07,039
schedules for their employees and if
617
00:24:07,039 --> 00:24:09,120
that company runs three eight hour
618
00:24:09,120 --> 00:24:11,440
shifts per day in a science three of its
619
00:24:11,440 --> 00:24:13,840
four employees different shifts each day
620
00:24:13,840 --> 00:24:16,880
while giving a fourth one's a day off
621
00:24:16,880 --> 00:24:19,279
even in such a small case like that the
622
00:24:19,279 --> 00:24:22,159
number of possible schedules is huge
623
00:24:22,159 --> 00:24:24,480
each day there are factorially 24
624
00:24:24,480 --> 00:24:26,559
possible employee assignments for four
625
00:24:26,559 --> 00:24:27,520
people
626
00:24:27,520 --> 00:24:28,880
so the number of possible weekly
627
00:24:28,880 --> 00:24:32,640
schedules is 247 which calculates over
628
00:24:32,640 --> 00:24:34,799
4.5 billion
629
00:24:34,799 --> 00:24:36,320
constraint programming methods keep
630
00:24:36,320 --> 00:24:38,480
track of which solutions remain feasible
631
00:24:38,480 --> 00:24:40,320
and makes it a powerful tool for solving
632
00:24:40,320 --> 00:24:42,559
real world
633
00:24:42,559 --> 00:24:44,960
scheduling problems who knew queens on a
634
00:24:44,960 --> 00:24:46,559
chessboard combined with computer
635
00:24:46,559 --> 00:24:48,480
programming could help solve real world
636
00:24:48,480 --> 00:24:51,440
problems like that
637
00:24:54,400 --> 00:24:57,039
so what did we learn in our very first
638
00:24:57,039 --> 00:24:59,520
lesson in our algorithms course
639
00:24:59,520 --> 00:25:01,919
we learned simple recursion and saw it
640
00:25:01,919 --> 00:25:04,080
in action that when a function calls
641
00:25:04,080 --> 00:25:06,320
itself it creates new spaces to store
642
00:25:06,320 --> 00:25:08,799
information and sometimes this may not
643
00:25:08,799 --> 00:25:11,360
be an efficient solution to a problem
644
00:25:11,360 --> 00:25:13,600
it's definitely more elegant with fewer
645
00:25:13,600 --> 00:25:15,600
lines of code
646
00:25:15,600 --> 00:25:17,440
that can come in handy depending on the
647
00:25:17,440 --> 00:25:19,120
problem but it's not always cost
648
00:25:19,120 --> 00:25:20,400
effective
649
00:25:20,400 --> 00:25:22,080
but it is important to see and
650
00:25:22,080 --> 00:25:24,240
understand the difference
651
00:25:24,240 --> 00:25:27,440
factorials and permutations are used in
652
00:25:27,440 --> 00:25:29,679
a lot of computational mathematical and
653
00:25:29,679 --> 00:25:31,840
real world applications
654
00:25:31,840 --> 00:25:33,520
learning how to write programs rather
655
00:25:33,520 --> 00:25:35,679
recursively or iteratively to find the
656
00:25:35,679 --> 00:25:36,960
best method
657
00:25:36,960 --> 00:25:39,039
in this area can go a long way and may
658
00:25:39,039 --> 00:25:40,799
lead to unknown opportunities for you
659
00:25:40,799 --> 00:25:43,120
down the road as a programmer
660
00:25:43,120 --> 00:25:45,200
we learned about constraint programming
661
00:25:45,200 --> 00:25:47,440
where recursion plays a role for solving
662
00:25:47,440 --> 00:25:49,279
mind-bending problems
663
00:25:49,279 --> 00:25:51,440
not only within board games such as
664
00:25:51,440 --> 00:25:53,840
chess but real life issues that
665
00:25:53,840 --> 00:25:55,360
companies can face
666
00:25:55,360 --> 00:25:57,520
as a programmer that works to gain the
667
00:25:57,520 --> 00:26:00,080
tools needed to understand these types
668
00:26:00,080 --> 00:26:02,240
of methods to solve problems can make
669
00:26:02,240 --> 00:26:07,240
them a valuable asset to any company
670
00:26:07,510 --> 00:26:17,919
[Music]
671
00:26:17,919 --> 00:26:20,799
welcome to level two
672
00:26:20,799 --> 00:26:22,720
working with data
673
00:26:22,720 --> 00:26:24,880
that is structured i like to think of
674
00:26:24,880 --> 00:26:26,559
data structures like something that
675
00:26:26,559 --> 00:26:28,960
holds money say for instance you have on
676
00:26:28,960 --> 00:26:31,679
your person a big wad of cash consisting
677
00:26:31,679 --> 00:26:33,679
of a lot of different bills what could
678
00:26:33,679 --> 00:26:36,320
you do with it well you could store it
679
00:26:36,320 --> 00:26:39,600
sort it search it add it spend it
680
00:26:39,600 --> 00:26:40,799
delete it
681
00:26:40,799 --> 00:26:42,880
count it so with data structures they're
682
00:26:42,880 --> 00:26:45,679
simply containers or collections of data
683
00:26:45,679 --> 00:26:47,360
they provide a means of managing small
684
00:26:47,360 --> 00:26:49,520
or large amounts of values for uses and
685
00:26:49,520 --> 00:26:50,960
such things like
686
00:26:50,960 --> 00:26:53,840
databases web traffic monitoring user
687
00:26:53,840 --> 00:26:56,640
registrations and or indexing within a
688
00:26:56,640 --> 00:26:59,919
contiguous memory location like an array
689
00:26:59,919 --> 00:27:02,640
they can range from as simple as lists
690
00:27:02,640 --> 00:27:05,360
to linked lists stacks cues hash tables
691
00:27:05,360 --> 00:27:07,200
trees and heaps
692
00:27:07,200 --> 00:27:09,039
these are all examples of data
693
00:27:09,039 --> 00:27:10,960
structures and since algorithms are
694
00:27:10,960 --> 00:27:13,520
steps to solving problems what kind of
695
00:27:13,520 --> 00:27:15,760
problem-solving techniques are common
696
00:27:15,760 --> 00:27:17,919
with data structures well just like
697
00:27:17,919 --> 00:27:20,799
watts of cache data often needs storage
698
00:27:20,799 --> 00:27:23,440
sorting counting retrieving searching
699
00:27:23,440 --> 00:27:26,399
spending all those fun things now arrays
700
00:27:26,399 --> 00:27:28,640
can be a really basic container for
701
00:27:28,640 --> 00:27:30,880
information but don't let that fool you
702
00:27:30,880 --> 00:27:32,799
many different algorithms can be used on
703
00:27:32,799 --> 00:27:34,720
one-dimensional arrays but what about
704
00:27:34,720 --> 00:27:37,039
two-dimensional arrays what about 32
705
00:27:37,039 --> 00:27:39,120
dimensions since that's the maximum
706
00:27:39,120 --> 00:27:41,360
amount can you imagine
707
00:27:41,360 --> 00:27:43,840
arrays are among the oldest and most
708
00:27:43,840 --> 00:27:45,919
important data structures and are used
709
00:27:45,919 --> 00:27:48,720
for almost every program for a basic
710
00:27:48,720 --> 00:27:50,799
level of algorithms with data structures
711
00:27:50,799 --> 00:27:53,679
we'll go easy and stick to a linear or
712
00:27:53,679 --> 00:27:55,760
one-dimensional array
713
00:27:55,760 --> 00:27:57,840
a one-dimensional array is just an array
714
00:27:57,840 --> 00:28:00,480
stored in an unbroken block of memory to
715
00:28:00,480 --> 00:28:02,399
access the next value in an array we
716
00:28:02,399 --> 00:28:04,000
just move sequentially to the next
717
00:28:04,000 --> 00:28:06,320
memory address it's best to see this
718
00:28:06,320 --> 00:28:08,399
visually so check these slides out for a
719
00:28:08,399 --> 00:28:11,799
better idea
720
00:28:17,600 --> 00:28:19,600
in our basic section we're going to
721
00:28:19,600 --> 00:28:20,480
cover
722
00:28:20,480 --> 00:28:23,440
linear search binary search
723
00:28:23,440 --> 00:28:24,720
bubble sort
724
00:28:24,720 --> 00:28:26,960
and insertion sort
725
00:28:26,960 --> 00:28:29,440
we'll be covering a little bit more for
726
00:28:29,440 --> 00:28:31,360
the basic level on data structures
727
00:28:31,360 --> 00:28:34,399
because it's a really big topic actually
728
00:28:34,399 --> 00:28:36,480
entire books are written about them let
729
00:28:36,480 --> 00:28:39,200
alone design techniques and algorithms
730
00:28:39,200 --> 00:28:42,000
i'll do my best not to put you to sleep
731
00:28:42,000 --> 00:28:43,440
hopefully it'll be enough to watch your
732
00:28:43,440 --> 00:28:45,600
appetite where array is our concern as
733
00:28:45,600 --> 00:28:48,399
this is a huge topic as well and as much
734
00:28:48,399 --> 00:28:50,640
as python is a wonderful program with
735
00:28:50,640 --> 00:28:52,159
tons of features like built-ins and
736
00:28:52,159 --> 00:28:54,080
libraries and modules that can help
737
00:28:54,080 --> 00:28:56,240
programmers code faster it's still
738
00:28:56,240 --> 00:28:58,000
really important to understand how these
739
00:28:58,000 --> 00:29:00,480
features work algorithmically and the
740
00:29:00,480 --> 00:29:02,320
concepts underneath it all
741
00:29:02,320 --> 00:29:05,360
let's get started
742
00:29:10,720 --> 00:29:13,039
a linear search could be equated to
743
00:29:13,039 --> 00:29:15,200
pulling that a lot of cash out of your
744
00:29:15,200 --> 00:29:16,480
wallet
745
00:29:16,480 --> 00:29:19,840
wait does anyone carry cash anymore no
746
00:29:19,840 --> 00:29:22,399
okay well let's pretend that you have a
747
00:29:22,399 --> 00:29:24,720
wallet full of really big bills i mean
748
00:29:24,720 --> 00:29:26,799
go big or go home right and you need a
749
00:29:26,799 --> 00:29:29,520
500 bill from your stack
750
00:29:29,520 --> 00:29:31,760
why well you're at the mall of course
751
00:29:31,760 --> 00:29:33,520
and you want to buy that really cool
752
00:29:33,520 --> 00:29:35,440
pair of socks that you saw in the window
753
00:29:35,440 --> 00:29:37,760
and you might be thinking 500 for a pair
754
00:29:37,760 --> 00:29:40,000
of socks and i would say yup that's
755
00:29:40,000 --> 00:29:42,640
inflation for you but this is a fantasy
756
00:29:42,640 --> 00:29:45,760
remember besides inflation slomation you
757
00:29:45,760 --> 00:29:47,679
got a wallet full of big bills and in
758
00:29:47,679 --> 00:29:50,240
this fantasy let's go for a big ticket
759
00:29:50,240 --> 00:29:51,360
item
760
00:29:51,360 --> 00:29:54,559
well maybe not sucks but maybe a t-shirt
761
00:29:54,559 --> 00:29:56,640
in a linear or sequential search we
762
00:29:56,640 --> 00:29:59,279
could technically transpose transposo
763
00:29:59,279 --> 00:30:01,200
those terms you would have to go through
764
00:30:01,200 --> 00:30:03,679
each bill to find that 500 same with an
765
00:30:03,679 --> 00:30:07,520
array of say six random integers
766
00:30:07,520 --> 00:30:09,919
if we were wanting to find the eight we
767
00:30:09,919 --> 00:30:12,480
we would have to manually check each
768
00:30:12,480 --> 00:30:14,559
element in order to return the position
769
00:30:14,559 --> 00:30:15,520
of the eight
770
00:30:15,520 --> 00:30:18,159
algorithmically it would look like this
771
00:30:18,159 --> 00:30:20,240
and can you imagine if we had an array
772
00:30:20,240 --> 00:30:22,399
containing a large amount of numbers it
773
00:30:22,399 --> 00:30:25,679
would be very very time consuming and
774
00:30:25,679 --> 00:30:27,679
inefficient to use a linear search
775
00:30:27,679 --> 00:30:29,840
because it would be comparing each
776
00:30:29,840 --> 00:30:31,840
integer one by one
777
00:30:31,840 --> 00:30:34,480
now can it be used for searching sure
778
00:30:34,480 --> 00:30:36,080
but it's only when the numbers are
779
00:30:36,080 --> 00:30:39,760
relatively few and relatively sorted but
780
00:30:39,760 --> 00:30:42,159
hey let's code this out anyway we'll
781
00:30:42,159 --> 00:30:44,399
define our function with two parameters
782
00:30:44,399 --> 00:30:46,159
our array and the element that we're
783
00:30:46,159 --> 00:30:48,000
searching for then we'll write a for
784
00:30:48,000 --> 00:30:49,600
loop to iterate over the length of our
785
00:30:49,600 --> 00:30:51,760
array and if there is an element there
786
00:30:51,760 --> 00:30:54,080
that's the same as our element then just
787
00:30:54,080 --> 00:30:56,080
return where it is in the array when we
788
00:30:56,080 --> 00:30:59,200
print it out we get index position 4 as
789
00:30:59,200 --> 00:31:04,200
that is where our 10 is
790
00:31:05,600 --> 00:31:07,440
a more efficient way to search is to
791
00:31:07,440 --> 00:31:09,519
move up to a binary search and the clue
792
00:31:09,519 --> 00:31:12,240
is in the name binary as in by meaning
793
00:31:12,240 --> 00:31:14,240
something that has two parts
794
00:31:14,240 --> 00:31:16,240
in this search algorithm we would create
795
00:31:16,240 --> 00:31:18,559
two pointers and repeatedly divide the
796
00:31:18,559 --> 00:31:21,679
search interval by half naturally this
797
00:31:21,679 --> 00:31:23,279
would reduce our search space so that
798
00:31:23,279 --> 00:31:25,840
we're not searching the whole array but
799
00:31:25,840 --> 00:31:28,080
only the divided parts
800
00:31:28,080 --> 00:31:30,399
the catches at the binary search
801
00:31:30,399 --> 00:31:33,279
is that it is usually mostly
802
00:31:33,279 --> 00:31:34,960
generally
803
00:31:34,960 --> 00:31:37,200
done on sorted arrays that looks like
804
00:31:37,200 --> 00:31:38,159
this
805
00:31:38,159 --> 00:31:39,600
and this way the algorithm checks
806
00:31:39,600 --> 00:31:41,279
whether the middle element is equal to
807
00:31:41,279 --> 00:31:43,519
the target that we're searching for in
808
00:31:43,519 --> 00:31:45,600
every iteration if the target value
809
00:31:45,600 --> 00:31:48,000
matches the element then its position in
810
00:31:48,000 --> 00:31:50,640
the array is returned if the if the
811
00:31:50,640 --> 00:31:52,480
target value is less than the element
812
00:31:52,480 --> 00:31:54,320
the search continues in the lower half
813
00:31:54,320 --> 00:31:57,200
of the array the target value is greater
814
00:31:57,200 --> 00:31:59,200
than it searches in the upper half of
815
00:31:59,200 --> 00:32:01,679
the array ultimately the algorithm
816
00:32:01,679 --> 00:32:03,840
doesn't need to search the half our
817
00:32:03,840 --> 00:32:06,880
target isn't in with each iteration
818
00:32:06,880 --> 00:32:09,679
now let's look at some code
819
00:32:09,679 --> 00:32:11,919
because our program is only searching
820
00:32:11,919 --> 00:32:14,480
half the array it makes it a much better
821
00:32:14,480 --> 00:32:15,440
search
822
00:32:15,440 --> 00:32:17,840
let's look at the iterative method first
823
00:32:17,840 --> 00:32:19,840
in our function we can create four
824
00:32:19,840 --> 00:32:23,440
parameters our array a start point an
825
00:32:23,440 --> 00:32:24,640
endpoint
826
00:32:24,640 --> 00:32:26,960
and the target that we're searching for
827
00:32:26,960 --> 00:32:28,880
we'll create a while loop to iterate
828
00:32:28,880 --> 00:32:31,039
over our array from start to end and
829
00:32:31,039 --> 00:32:33,519
then create our midpoint our variable
830
00:32:33,519 --> 00:32:36,480
called mid is the magic in the sauce we
831
00:32:36,480 --> 00:32:38,320
only want to traverse the half that
832
00:32:38,320 --> 00:32:40,640
contains our element feel free to print
833
00:32:40,640 --> 00:32:42,320
out the mid when you run the whole
834
00:32:42,320 --> 00:32:44,480
program for yourself to get a good idea
835
00:32:44,480 --> 00:32:45,919
of this
836
00:32:45,919 --> 00:32:48,799
next we can implement our if statements
837
00:32:48,799 --> 00:32:50,480
we'll only need three
838
00:32:50,480 --> 00:32:52,960
check if our target is in the upper half
839
00:32:52,960 --> 00:32:55,360
then reassign our start to begin moving
840
00:32:55,360 --> 00:32:57,600
to the right of the array
841
00:32:57,600 --> 00:33:00,480
if our target is lower than our mid we
842
00:33:00,480 --> 00:33:02,720
reassign our end to begin moving to the
843
00:33:02,720 --> 00:33:05,600
left of the array if our target matches
844
00:33:05,600 --> 00:33:09,120
our mid then just return it easy peasy
845
00:33:09,120 --> 00:33:11,440
then we just return our start or we can
846
00:33:11,440 --> 00:33:13,440
return something like negative one to
847
00:33:13,440 --> 00:33:15,200
print out some strings to make it a
848
00:33:15,200 --> 00:33:16,480
little fancy
849
00:33:16,480 --> 00:33:18,080
but either way you prefer to have your
850
00:33:18,080 --> 00:33:20,159
results printed we have to be sure to
851
00:33:20,159 --> 00:33:22,320
declare our start and end in the
852
00:33:22,320 --> 00:33:24,960
function call our start is zero from the
853
00:33:24,960 --> 00:33:26,559
beginning of the array and our end is
854
00:33:26,559 --> 00:33:28,159
the last element
855
00:33:28,159 --> 00:33:32,080
our length of array minus one
856
00:33:35,440 --> 00:33:38,159
for our recursive function i won't spend
857
00:33:38,159 --> 00:33:39,519
a lot of time here because the
858
00:33:39,519 --> 00:33:41,600
difference between our iterative program
859
00:33:41,600 --> 00:33:43,519
and the recursive program is very
860
00:33:43,519 --> 00:33:46,880
minimal runtime and memory space is very
861
00:33:46,880 --> 00:33:48,880
very close meaning they're both really
862
00:33:48,880 --> 00:33:49,919
efficient
863
00:33:49,919 --> 00:33:51,440
either way it's good to see both
864
00:33:51,440 --> 00:33:52,960
programs
865
00:33:52,960 --> 00:33:54,960
basically all we're doing is just
866
00:33:54,960 --> 00:33:57,039
calling back to the original function
867
00:33:57,039 --> 00:33:58,799
within our else statements
868
00:33:58,799 --> 00:34:00,559
feel free to pause the video for a
869
00:34:00,559 --> 00:34:05,399
moment and take a closer look
870
00:34:06,960 --> 00:34:10,079
okay now that we have some super basic
871
00:34:10,079 --> 00:34:12,800
searches under our belt let's move into
872
00:34:12,800 --> 00:34:16,719
a deeper section of sorting because well
873
00:34:16,719 --> 00:34:18,239
sorting is fun
874
00:34:18,239 --> 00:34:20,639
who doesn't like to sort money piles of
875
00:34:20,639 --> 00:34:24,079
50s here piles of honey is there
876
00:34:24,079 --> 00:34:26,560
holy crap i sound like mr krabs
877
00:34:26,560 --> 00:34:28,239
all right all right let's mix the money
878
00:34:28,239 --> 00:34:30,639
references let's get to sorting our
879
00:34:30,639 --> 00:34:33,760
boring old elements
880
00:34:33,760 --> 00:34:36,560
as for sorting there are a vast array of
881
00:34:36,560 --> 00:34:38,239
techniques
882
00:34:38,239 --> 00:34:40,239
that are available and here's a little
883
00:34:40,239 --> 00:34:42,799
quick list
884
00:34:43,040 --> 00:34:44,320
actually
885
00:34:44,320 --> 00:34:46,719
it's not that quick as there are many to
886
00:34:46,719 --> 00:34:49,838
choose from
887
00:34:53,440 --> 00:34:55,520
bubble sort is the simplest sorting
888
00:34:55,520 --> 00:34:57,599
algorithm that works by repeatedly
889
00:34:57,599 --> 00:34:59,680
swapping the adjacent elements if they
890
00:34:59,680 --> 00:35:02,400
are in the wrong order for instance the
891
00:35:02,400 --> 00:35:05,280
largest integer bubbles up to the top or
892
00:35:05,280 --> 00:35:08,079
iterates its way to the end of the array
893
00:35:08,079 --> 00:35:10,240
through a comparison of each element
894
00:35:10,240 --> 00:35:12,160
although this isn't a very efficient
895
00:35:12,160 --> 00:35:14,880
algorithm perhaps the worst it's still
896
00:35:14,880 --> 00:35:17,040
an important concept to understand the
897
00:35:17,040 --> 00:35:19,200
only real perk the bubble sort has
898
00:35:19,200 --> 00:35:21,440
compared to other algorithms is its
899
00:35:21,440 --> 00:35:23,440
built-in ability to detect whether or
900
00:35:23,440 --> 00:35:25,440
not an array is sorted in the first
901
00:35:25,440 --> 00:35:28,160
place in a best case scenario the list
902
00:35:28,160 --> 00:35:31,599
is already sorted or nearly sorted and
903
00:35:31,599 --> 00:35:33,680
this is in contrast to other algorithms
904
00:35:33,680 --> 00:35:35,280
even those with better than average
905
00:35:35,280 --> 00:35:37,680
performance whose entire sorting process
906
00:35:37,680 --> 00:35:39,440
caused more causes more inversions
907
00:35:39,440 --> 00:35:42,160
reversals reversals or swaps to happen
908
00:35:42,160 --> 00:35:44,320
an optimized algorithm for the bubble
909
00:35:44,320 --> 00:35:46,720
sort is to find the nth largest element
910
00:35:46,720 --> 00:35:49,040
and put it at the end of the array there
911
00:35:49,040 --> 00:35:51,119
is an unoptimized version that you can
912
00:35:51,119 --> 00:35:53,599
check out for comparison purposes if you
913
00:35:53,599 --> 00:35:54,960
want to look that up on your own you're
914
00:35:54,960 --> 00:35:56,800
more than welcome to do that but the
915
00:35:56,800 --> 00:35:58,400
optimized version is done so that the
916
00:35:58,400 --> 00:36:00,320
inner loop can avoid having to look all
917
00:36:00,320 --> 00:36:02,240
the way at the end when it's running the
918
00:36:02,240 --> 00:36:04,800
last iteration it's just saving time and
919
00:36:04,800 --> 00:36:07,359
energy by not having to do that although
920
00:36:07,359 --> 00:36:09,839
bubble sort is one of the simplest
921
00:36:09,839 --> 00:36:11,760
sorting algorithms to understand and
922
00:36:11,760 --> 00:36:14,480
implement its performance means that
923
00:36:14,480 --> 00:36:16,880
it's that its efficiency decreases
924
00:36:16,880 --> 00:36:19,359
dramatically on arrays of larger amounts
925
00:36:19,359 --> 00:36:21,520
of elements and it's even been argued
926
00:36:21,520 --> 00:36:23,839
that it shouldn't even be taught anymore
927
00:36:23,839 --> 00:36:27,119
as it's outdated and is even hazardous
928
00:36:27,119 --> 00:36:29,440
to some cpus
929
00:36:29,440 --> 00:36:31,760
yikes i bet you didn't realize that
930
00:36:31,760 --> 00:36:33,599
you'd be entering dangerous territory
931
00:36:33,599 --> 00:36:35,760
here i mean who knew conan could be
932
00:36:35,760 --> 00:36:38,320
fraught with such tenuous escapades such
933
00:36:38,320 --> 00:36:39,359
as this
934
00:36:39,359 --> 00:36:40,720
how sexy
935
00:36:40,720 --> 00:36:43,440
let's code it
936
00:36:46,079 --> 00:36:47,599
our function will take just one
937
00:36:47,599 --> 00:36:49,680
parameter our array
938
00:36:49,680 --> 00:36:51,520
and then i implemented an iteration
939
00:36:51,520 --> 00:36:54,960
count just for informational purposes
940
00:36:54,960 --> 00:36:57,520
next we create a for loop to iterate
941
00:36:57,520 --> 00:36:59,920
over our indices in the array going to
942
00:36:59,920 --> 00:37:02,480
the right combined with a nested loop
943
00:37:02,480 --> 00:37:04,960
inside that iterates over our indices
944
00:37:04,960 --> 00:37:06,640
going left
945
00:37:06,640 --> 00:37:10,880
or reverse that we're going to call j
946
00:37:10,880 --> 00:37:12,960
i strongly encourage you to write this
947
00:37:12,960 --> 00:37:14,800
program for yourself and within our
948
00:37:14,800 --> 00:37:17,839
nested loop print out j just to see it
949
00:37:17,839 --> 00:37:19,760
in action
950
00:37:19,760 --> 00:37:22,560
we have our iteration counter when this
951
00:37:22,560 --> 00:37:25,200
prints you'll see why i added this now
952
00:37:25,200 --> 00:37:27,359
we just tell it to swap elements if they
953
00:37:27,359 --> 00:37:29,200
are lower than the one to the left in
954
00:37:29,200 --> 00:37:31,520
our if statement if our element to the
955
00:37:31,520 --> 00:37:34,320
left is greater then swap it
956
00:37:34,320 --> 00:37:36,240
then we just return our newly sorted
957
00:37:36,240 --> 00:37:39,119
array so let's print this so you can see
958
00:37:39,119 --> 00:37:40,640
our iteration count
959
00:37:40,640 --> 00:37:43,040
with 36 iterations that's pretty
960
00:37:43,040 --> 00:37:44,400
efficient
961
00:37:44,400 --> 00:37:47,440
check this out now i know i said that it
962
00:37:47,440 --> 00:37:49,680
wasn't going to look at the unoptimized
963
00:37:49,680 --> 00:37:52,400
but guys check this out double the
964
00:37:52,400 --> 00:37:55,040
iterations for two functions and it's
965
00:37:55,040 --> 00:37:57,040
double the code
966
00:37:57,040 --> 00:37:58,960
i liked our first program
967
00:37:58,960 --> 00:38:02,800
simple shorter faster
968
00:38:02,800 --> 00:38:05,800
unstable
969
00:38:07,920 --> 00:38:08,720
oh
970
00:38:08,720 --> 00:38:11,520
that was dangerous i kind of like it but
971
00:38:11,520 --> 00:38:14,160
hey if dangerous not your thing you
972
00:38:14,160 --> 00:38:15,839
thrive in a more stable and secure
973
00:38:15,839 --> 00:38:17,440
environment that's fine too we can
974
00:38:17,440 --> 00:38:20,240
totally move on to the insertion sort
975
00:38:20,240 --> 00:38:22,480
algorithm insertion sort is another
976
00:38:22,480 --> 00:38:24,640
simple sorting algorithm that builds the
977
00:38:24,640 --> 00:38:26,960
final array one item at a time
978
00:38:26,960 --> 00:38:29,440
it's still inefficient on large lists
979
00:38:29,440 --> 00:38:31,280
like the bubble sore but it can have
980
00:38:31,280 --> 00:38:33,520
some advantages such as simple
981
00:38:33,520 --> 00:38:36,240
implementation meaning a reduced amount
982
00:38:36,240 --> 00:38:38,800
of code and performs well in small data
983
00:38:38,800 --> 00:38:41,440
sets and relatively sorted arrays and it
984
00:38:41,440 --> 00:38:43,359
doesn't require much space meaning that
985
00:38:43,359 --> 00:38:45,839
it can be done in place therefore not
986
00:38:45,839 --> 00:38:48,000
using much computer memory in order to
987
00:38:48,000 --> 00:38:50,079
perform well the concept of the
988
00:38:50,079 --> 00:38:52,480
insertion sort is to split the array
989
00:38:52,480 --> 00:38:54,720
into two sections in order to compare
990
00:38:54,720 --> 00:38:57,359
its elements we can consider one side
991
00:38:57,359 --> 00:39:00,480
sorted and the other side unsorted our
992
00:39:00,480 --> 00:39:03,280
algorithm takes one element at a time
993
00:39:03,280 --> 00:39:05,359
from the unsorted side and compares it
994
00:39:05,359 --> 00:39:07,839
to our elements on the sorted side
995
00:39:07,839 --> 00:39:10,160
if our element is larger or smaller it
996
00:39:10,160 --> 00:39:12,400
places it where it needs to be on our
997
00:39:12,400 --> 00:39:15,599
sorted side each generation takes an
998
00:39:15,599 --> 00:39:17,520
element from the unsorted side and
999
00:39:17,520 --> 00:39:19,760
places it into our sorted side all the
1000
00:39:19,760 --> 00:39:21,440
way till there are no more elements to
1001
00:39:21,440 --> 00:39:22,640
compare to
1002
00:39:22,640 --> 00:39:24,960
and in the end we are left with a sorted
1003
00:39:24,960 --> 00:39:27,359
array
1004
00:39:27,680 --> 00:39:30,240
for our program our parameter in our
1005
00:39:30,240 --> 00:39:32,800
function call will be our array starting
1006
00:39:32,800 --> 00:39:34,640
with a for loop that will iterate
1007
00:39:34,640 --> 00:39:37,680
starting at our second element we don't
1008
00:39:37,680 --> 00:39:40,079
need to start at our first integer
1009
00:39:40,079 --> 00:39:43,359
because that's our sorted side
1010
00:39:43,359 --> 00:39:45,680
we leave that alone for now we create
1011
00:39:45,680 --> 00:39:48,240
two variables our key which is our
1012
00:39:48,240 --> 00:39:50,720
current element and a pointer to the
1013
00:39:50,720 --> 00:39:52,560
left of our key
1014
00:39:52,560 --> 00:39:54,880
we'll implement a while loop to iterate
1015
00:39:54,880 --> 00:39:57,440
as long as our index is greater or equal
1016
00:39:57,440 --> 00:40:00,400
to zero and our index is greater than
1017
00:40:00,400 --> 00:40:02,079
our key
1018
00:40:02,079 --> 00:40:04,560
we then program it to reassign the
1019
00:40:04,560 --> 00:40:06,800
larger one to the right position and
1020
00:40:06,800 --> 00:40:09,440
then move down and put our small element
1021
00:40:09,440 --> 00:40:10,880
to the left
1022
00:40:10,880 --> 00:40:13,760
we do this all in place without creating
1023
00:40:13,760 --> 00:40:15,200
extra space
1024
00:40:15,200 --> 00:40:17,520
it's fairly simple and straight to the
1025
00:40:17,520 --> 00:40:19,839
point
1026
00:40:20,800 --> 00:40:25,839
working with arrays can last for days
1027
00:40:26,319 --> 00:40:28,640
you like that no but seriously what
1028
00:40:28,640 --> 00:40:30,480
we've touched on is only the tip of the
1029
00:40:30,480 --> 00:40:32,480
iceberg as a personal challenge to
1030
00:40:32,480 --> 00:40:34,800
yourself try searching and sorting a
1031
00:40:34,800 --> 00:40:37,680
two-dimensional array are you up to the
1032
00:40:37,680 --> 00:40:40,160
challenge
1033
00:40:45,040 --> 00:40:48,000
for our advanced level algorithm section
1034
00:40:48,000 --> 00:40:51,119
we're going to dive into linked lists a
1035
00:40:51,119 --> 00:40:53,200
linked list is a linear data structure
1036
00:40:53,200 --> 00:40:55,839
in which the elements are are not stored
1037
00:40:55,839 --> 00:40:58,480
at contiguous memory locations
1038
00:40:58,480 --> 00:41:00,319
remember this picture
1039
00:41:00,319 --> 00:41:02,560
also remember that arrays are stored at
1040
00:41:02,560 --> 00:41:05,599
contiguous memory locations
1041
00:41:05,599 --> 00:41:08,400
a wikipedia definition states a linked
1042
00:41:08,400 --> 00:41:11,040
list is a linear collection of data
1043
00:41:11,040 --> 00:41:12,880
elements whose order is not given by
1044
00:41:12,880 --> 00:41:15,119
their physical placement in memory
1045
00:41:15,119 --> 00:41:18,800
instead each element points to the next
1046
00:41:18,800 --> 00:41:21,040
it's a data structure consisting of a
1047
00:41:21,040 --> 00:41:23,200
collection of nodes which together
1048
00:41:23,200 --> 00:41:26,000
represent a sequence in its most basic
1049
00:41:26,000 --> 00:41:28,720
form each node contains data and a
1050
00:41:28,720 --> 00:41:30,800
reference in other words a link to the
1051
00:41:30,800 --> 00:41:33,599
next node in the sequence
1052
00:41:33,599 --> 00:41:35,680
this structure allows for efficient
1053
00:41:35,680 --> 00:41:38,160
insertion or removal of elements from
1054
00:41:38,160 --> 00:41:40,000
any position in the sequence during
1055
00:41:40,000 --> 00:41:41,119
iteration
1056
00:41:41,119 --> 00:41:44,079
more complex variants and additional
1057
00:41:44,079 --> 00:41:46,560
links allowing more efficient insertion
1058
00:41:46,560 --> 00:41:48,400
or removal of nodes at arbitrary
1059
00:41:48,400 --> 00:41:51,119
positions a drawback of linked lists is
1060
00:41:51,119 --> 00:41:53,599
that access time is linear and difficult
1061
00:41:53,599 --> 00:41:55,680
to pipeline
1062
00:41:55,680 --> 00:41:58,240
some say that linked lists are among the
1063
00:41:58,240 --> 00:42:02,319
simplest and most common data structures
1064
00:42:02,319 --> 00:42:03,680
are they though
1065
00:42:03,680 --> 00:42:05,119
as an example
1066
00:42:05,119 --> 00:42:07,839
think of a photo storage website if you
1067
00:42:07,839 --> 00:42:10,319
click on the website landing page this
1068
00:42:10,319 --> 00:42:12,800
would be considered your header
1069
00:42:12,800 --> 00:42:13,599
then
1070
00:42:13,599 --> 00:42:15,839
when you click on the first image this
1071
00:42:15,839 --> 00:42:17,839
would become a node
1072
00:42:17,839 --> 00:42:20,240
the arrow next to it that you can click
1073
00:42:20,240 --> 00:42:22,319
to see the next picture would be your
1074
00:42:22,319 --> 00:42:23,440
pointer
1075
00:42:23,440 --> 00:42:25,359
now if you get to the third or fourth
1076
00:42:25,359 --> 00:42:28,079
picture and want to go back to the first
1077
00:42:28,079 --> 00:42:29,119
picture
1078
00:42:29,119 --> 00:42:30,800
and look at that again
1079
00:42:30,800 --> 00:42:32,319
those back arrows would mean that you're
1080
00:42:32,319 --> 00:42:34,640
on a doubly linked list
1081
00:42:34,640 --> 00:42:36,720
a doubly linked list means that you can
1082
00:42:36,720 --> 00:42:40,000
traverse the list forward and backward
1083
00:42:40,000 --> 00:42:42,319
however for this lesson we're only going
1084
00:42:42,319 --> 00:42:44,880
to cover a list that we can go forward
1085
00:42:44,880 --> 00:42:47,520
on the singly linked list
1086
00:42:47,520 --> 00:42:49,359
now the upside of a linked list over a
1087
00:42:49,359 --> 00:42:51,359
conventional array is that the list
1088
00:42:51,359 --> 00:42:53,520
elements can be easily inserted or
1089
00:42:53,520 --> 00:42:56,079
removed without re allocation or
1090
00:42:56,079 --> 00:42:58,640
reorganization of the entire structure
1091
00:42:58,640 --> 00:43:01,040
because the data items do not need to be
1092
00:43:01,040 --> 00:43:02,880
stored contiguously
1093
00:43:02,880 --> 00:43:05,599
linked lists allow insertion and removal
1094
00:43:05,599 --> 00:43:07,839
of nodes at any point in the list and
1095
00:43:07,839 --> 00:43:09,839
they keep up with a constant number of
1096
00:43:09,839 --> 00:43:12,319
operations by storing the link previous
1097
00:43:12,319 --> 00:43:14,720
to any link being added or removed
1098
00:43:14,720 --> 00:43:17,599
during a list traversal so let's talk
1099
00:43:17,599 --> 00:43:20,160
about our four basic algorithms or
1100
00:43:20,160 --> 00:43:22,560
common problem solving operations for
1101
00:43:22,560 --> 00:43:24,319
singly linked lists
1102
00:43:24,319 --> 00:43:26,400
every programmer needs to be able to do
1103
00:43:26,400 --> 00:43:29,280
the following traverse a linked list or
1104
00:43:29,280 --> 00:43:31,440
be able to travel along the nodes and
1105
00:43:31,440 --> 00:43:32,560
pointers
1106
00:43:32,560 --> 00:43:35,119
search a list for the header a node or
1107
00:43:35,119 --> 00:43:38,000
tail a tail is the last and final node
1108
00:43:38,000 --> 00:43:40,720
insert a new header note or tail
1109
00:43:40,720 --> 00:43:43,520
and to delete a note or tail a link to
1110
00:43:43,520 --> 00:43:46,079
list generally always needs a header
1111
00:43:46,079 --> 00:43:48,480
let's create a simple linked list
1112
00:43:48,480 --> 00:43:51,359
representing a small family member group
1113
00:43:51,359 --> 00:43:53,040
we want to be able to do all the
1114
00:43:53,040 --> 00:43:55,280
operations mentioned above this will
1115
00:43:55,280 --> 00:43:57,440
require a little bit of object oriented
1116
00:43:57,440 --> 00:43:59,040
programming so hopefully you are
1117
00:43:59,040 --> 00:44:01,440
somewhat familiar with that but if not
1118
00:44:01,440 --> 00:44:03,760
that's okay we'll stay simple and make
1119
00:44:03,760 --> 00:44:05,359
it easy peasy
1120
00:44:05,359 --> 00:44:08,079
we need our pretty standard class node
1121
00:44:08,079 --> 00:44:11,599
and class linked list to start our nodes
1122
00:44:11,599 --> 00:44:13,359
will be our family members and our
1123
00:44:13,359 --> 00:44:15,119
linked list will represent our whole
1124
00:44:15,119 --> 00:44:17,359
family this can be considered a little
1125
00:44:17,359 --> 00:44:19,119
backwards but i like to instantiate our
1126
00:44:19,119 --> 00:44:20,960
objects first so it's easier to see what
1127
00:44:20,960 --> 00:44:22,880
we're dealing with being able to
1128
00:44:22,880 --> 00:44:24,640
visualize what we're doing is an
1129
00:44:24,640 --> 00:44:26,319
important skill in programming and
1130
00:44:26,319 --> 00:44:28,079
design because it helps us think about
1131
00:44:28,079 --> 00:44:31,359
the big picture throughout the solution
1132
00:44:31,359 --> 00:44:33,520
let's picture our knowns as a family of
1133
00:44:33,520 --> 00:44:36,240
mom dad and two kids we'll create our
1134
00:44:36,240 --> 00:44:39,520
family head as bob his wife amy our
1135
00:44:39,520 --> 00:44:41,520
header will point to amy as the next
1136
00:44:41,520 --> 00:44:44,319
node and then our two little nodes max
1137
00:44:44,319 --> 00:44:46,640
and jenny they all need to point to each
1138
00:44:46,640 --> 00:44:48,960
other as they will be linked together in
1139
00:44:48,960 --> 00:44:50,720
our list so we will make sure our
1140
00:44:50,720 --> 00:44:52,520
pointers are created which is
1141
00:44:52,520 --> 00:44:54,480
object.next
1142
00:44:54,480 --> 00:44:56,720
everything looks good and we have all
1143
00:44:56,720 --> 00:44:59,119
our members individually as nodes but to
1144
00:44:59,119 --> 00:45:00,960
really see our algorithm in action we
1145
00:45:00,960 --> 00:45:02,960
need to link all our members together in
1146
00:45:02,960 --> 00:45:05,119
our linked list where we can operate on
1147
00:45:05,119 --> 00:45:07,040
that list and design them to be really
1148
00:45:07,040 --> 00:45:09,440
complex or really simple
1149
00:45:09,440 --> 00:45:11,599
linked list problems are often used as
1150
00:45:11,599 --> 00:45:13,599
interview and exam questions so knowing
1151
00:45:13,599 --> 00:45:15,440
how to create linked lists how to
1152
00:45:15,440 --> 00:45:17,839
traverse them how to add and take away
1153
00:45:17,839 --> 00:45:20,400
elements is very important once you get
1154
00:45:20,400 --> 00:45:22,160
really familiar with those concepts you
1155
00:45:22,160 --> 00:45:24,160
can move into learn learning how to
1156
00:45:24,160 --> 00:45:27,280
traverse how to reverse a list swap
1157
00:45:27,280 --> 00:45:29,359
elements maybe even go on to doubly
1158
00:45:29,359 --> 00:45:31,599
linked lists or circular
1159
00:45:31,599 --> 00:45:33,839
it's a really big topic to explore and
1160
00:45:33,839 --> 00:45:36,880
fun too and if you're not having fun
1161
00:45:36,880 --> 00:45:41,359
why are why are you here like why
1162
00:45:41,359 --> 00:45:43,599
so back to our family
1163
00:45:43,599 --> 00:45:45,760
let's get them created and then set it
1164
00:45:45,760 --> 00:45:48,160
up to where we can traverse this family
1165
00:45:48,160 --> 00:45:49,040
list
1166
00:45:49,040 --> 00:45:51,040
once we have established our class we
1167
00:45:51,040 --> 00:45:53,200
just need to implement our functions
1168
00:45:53,200 --> 00:45:55,359
that tell our linked list class what to
1169
00:45:55,359 --> 00:45:56,319
do
1170
00:45:56,319 --> 00:45:58,160
this is where we implement all the
1171
00:45:58,160 --> 00:46:00,480
things we need done with our nodes and
1172
00:46:00,480 --> 00:46:02,000
the first thing we're going to do is
1173
00:46:02,000 --> 00:46:04,480
make our nodes by creating the data and
1174
00:46:04,480 --> 00:46:05,599
a pointer
1175
00:46:05,599 --> 00:46:09,040
let's create our objects
1176
00:46:09,040 --> 00:46:11,599
then create pointers that go to each
1177
00:46:11,599 --> 00:46:13,520
family member
1178
00:46:13,520 --> 00:46:15,599
now that we have our nodes we can now
1179
00:46:15,599 --> 00:46:17,520
link them in a list by creating our
1180
00:46:17,520 --> 00:46:20,000
linked list class this is where we
1181
00:46:20,000 --> 00:46:23,119
create a function to traverse our nodes
1182
00:46:23,119 --> 00:46:24,960
in a list and be able to print them all
1183
00:46:24,960 --> 00:46:27,200
out
1184
00:46:27,200 --> 00:46:30,000
we only need one argument self because
1185
00:46:30,000 --> 00:46:32,400
it doesn't need any other value or input
1186
00:46:32,400 --> 00:46:35,119
to be to be able to do what we need
1187
00:46:35,119 --> 00:46:36,800
which is starting at our header and
1188
00:46:36,800 --> 00:46:39,280
printing them all out next by next by
1189
00:46:39,280 --> 00:46:40,560
nuts
1190
00:46:40,560 --> 00:46:44,880
then we just call family.traversal
1191
00:46:44,880 --> 00:46:47,520
and out pops our family members now if
1192
00:46:47,520 --> 00:46:48,560
you want to shoot these out in a
1193
00:46:48,560 --> 00:46:50,640
particular way such as in a list or
1194
00:46:50,640 --> 00:46:52,640
fancy strings that would have to be done
1195
00:46:52,640 --> 00:46:54,880
within another function in the linked
1196
00:46:54,880 --> 00:46:58,079
list class which unfortunately is not
1197
00:46:58,079 --> 00:47:00,400
within the scope of this course that's
1198
00:47:00,400 --> 00:47:02,400
more in tune with object oriented
1199
00:47:02,400 --> 00:47:05,680
programming a whole other separate topic
1200
00:47:05,680 --> 00:47:07,520
the goal here is to focus on being able
1201
00:47:07,520 --> 00:47:10,000
to operate or solve problems to creating
1202
00:47:10,000 --> 00:47:12,960
simple function calls on linked lists
1203
00:47:12,960 --> 00:47:14,960
now our family member list is looking
1204
00:47:14,960 --> 00:47:17,280
pretty good but word on the street is
1205
00:47:17,280 --> 00:47:20,000
that bob isn't treating amy too well and
1206
00:47:20,000 --> 00:47:22,480
he's been running around on her
1207
00:47:22,480 --> 00:47:24,319
from the looks of it bob might be
1208
00:47:24,319 --> 00:47:26,559
packing his bags and leaving the family
1209
00:47:26,559 --> 00:47:28,960
but it's not all bad because dave has
1210
00:47:28,960 --> 00:47:30,960
been hanging around a bit and although
1211
00:47:30,960 --> 00:47:33,520
he's bob's brother he's a really good
1212
00:47:33,520 --> 00:47:34,720
guy
1213
00:47:34,720 --> 00:47:38,079
i know i know it sounds really back once
1214
00:47:38,079 --> 00:47:40,319
but seriously dave is going to step up
1215
00:47:40,319 --> 00:47:42,319
to the plate and he's looking forward to
1216
00:47:42,319 --> 00:47:44,240
being a dunkle to the kids
1217
00:47:44,240 --> 00:47:46,240
you know you know a dunkle like when
1218
00:47:46,240 --> 00:47:48,240
your uncle becomes your dad and it's not
1219
00:47:48,240 --> 00:47:49,839
weird at all
1220
00:47:49,839 --> 00:47:52,079
so for our list we need to put dave as
1221
00:47:52,079 --> 00:47:54,720
the new header position and because this
1222
00:47:54,720 --> 00:47:56,720
is a computer and it can't do anything
1223
00:47:56,720 --> 00:47:59,200
that we don't tell it to do we need to
1224
00:47:59,200 --> 00:48:01,040
implement some functions
1225
00:48:01,040 --> 00:48:04,160
let's call it insert new header
1226
00:48:04,160 --> 00:48:06,000
and this is going to fall under our
1227
00:48:06,000 --> 00:48:08,000
insertion algorithm
1228
00:48:08,000 --> 00:48:10,079
we need to know how to insert elements
1229
00:48:10,079 --> 00:48:12,079
into the list and not only that we have
1230
00:48:12,079 --> 00:48:14,880
to tell it where to insert for davis the
1231
00:48:14,880 --> 00:48:16,880
new head we are going to put him at the
1232
00:48:16,880 --> 00:48:18,400
front of the list
1233
00:48:18,400 --> 00:48:21,119
so for our function apart from self we
1234
00:48:21,119 --> 00:48:23,440
need new data or information to be added
1235
00:48:23,440 --> 00:48:25,280
to the parameter since we are adding a
1236
00:48:25,280 --> 00:48:26,400
new name
1237
00:48:26,400 --> 00:48:29,200
our new name is our new node so we will
1238
00:48:29,200 --> 00:48:31,200
need our node class
1239
00:48:31,200 --> 00:48:33,119
remember the nodes are our family
1240
00:48:33,119 --> 00:48:35,520
members then all we need to do is assign
1241
00:48:35,520 --> 00:48:37,680
him as the next new node to the
1242
00:48:37,680 --> 00:48:40,480
self.head and then assign yourself.head
1243
00:48:40,480 --> 00:48:43,359
to the new node let's traverse the list
1244
00:48:43,359 --> 00:48:46,359
now
1245
00:48:51,520 --> 00:48:54,079
oh boy bob is still in the picture and
1246
00:48:54,079 --> 00:48:56,240
you know what amy can't have her new
1247
00:48:56,240 --> 00:48:59,119
hubby under the same roof as her ex that
1248
00:48:59,119 --> 00:49:01,359
is just not gonna work this is a little
1249
00:49:01,359 --> 00:49:04,480
two backwoods so bob needs to
1250
00:49:04,480 --> 00:49:05,760
go go
1251
00:49:05,760 --> 00:49:08,319
creating our new header simply pushed
1252
00:49:08,319 --> 00:49:10,880
all our nodes down so we need to get bob
1253
00:49:10,880 --> 00:49:12,960
out of there let's create a function
1254
00:49:12,960 --> 00:49:15,839
that deletes a node however we can't
1255
00:49:15,839 --> 00:49:18,640
just delete some rando node we have to
1256
00:49:18,640 --> 00:49:21,119
tell our computer where bob the node is
1257
00:49:21,119 --> 00:49:22,720
in the first place
1258
00:49:22,720 --> 00:49:25,040
this means we have to search our family
1259
00:49:25,040 --> 00:49:27,440
list so let's create a search search
1260
00:49:27,440 --> 00:49:31,040
function with one parameter x
1261
00:49:31,040 --> 00:49:33,040
see what i did there pretty clever we
1262
00:49:33,040 --> 00:49:34,720
need to know if bob is even in there to
1263
00:49:34,720 --> 00:49:36,880
delete so in order to search we need to
1264
00:49:36,880 --> 00:49:39,200
start at the beginning of the list
1265
00:49:39,200 --> 00:49:41,359
let's create a temp variable assigned to
1266
00:49:41,359 --> 00:49:44,160
the self.head and make a while loop that
1267
00:49:44,160 --> 00:49:46,480
will traverse as long as that list or
1268
00:49:46,480 --> 00:49:49,359
header isn't empty if any node or temp
1269
00:49:49,359 --> 00:49:52,079
node isn't equal to x or whatever it is
1270
00:49:52,079 --> 00:49:54,000
we're searching for we want to return
1271
00:49:54,000 --> 00:49:56,559
true or else return false
1272
00:49:56,559 --> 00:49:58,800
then we need to assign our temp to the
1273
00:49:58,800 --> 00:50:01,680
next node because in a while loop it
1274
00:50:01,680 --> 00:50:03,680
will need to continue until the node is
1275
00:50:03,680 --> 00:50:07,119
not is none then it will return our pool
1276
00:50:07,119 --> 00:50:09,839
great let's find out if bob is in there
1277
00:50:09,839 --> 00:50:12,880
by printing our search function uh oh
1278
00:50:12,880 --> 00:50:15,040
it's true bob's still there and he's
1279
00:50:15,040 --> 00:50:17,680
giving amy a hard time about leaving
1280
00:50:17,680 --> 00:50:19,920
let's help her out and create a delete
1281
00:50:19,920 --> 00:50:21,040
function
1282
00:50:21,040 --> 00:50:23,440
this is going to be similar to our other
1283
00:50:23,440 --> 00:50:25,440
functions where we need to put our data
1284
00:50:25,440 --> 00:50:27,119
in the parameter and begin at the head
1285
00:50:27,119 --> 00:50:28,240
of our list
1286
00:50:28,240 --> 00:50:31,359
we need our if else statements and we
1287
00:50:31,359 --> 00:50:32,240
will
1288
00:50:32,240 --> 00:50:34,240
and we will say bob isn't there then
1289
00:50:34,240 --> 00:50:37,119
tell us and if he is let's kick him out
1290
00:50:37,119 --> 00:50:39,040
we do this by changing the pointers from
1291
00:50:39,040 --> 00:50:40,880
the previous node and pointing it to the
1292
00:50:40,880 --> 00:50:43,280
node after bob so in essence we're
1293
00:50:43,280 --> 00:50:46,079
skipping over bob but watch what happens
1294
00:50:46,079 --> 00:50:49,280
when we try to try to delete amy
1295
00:50:49,280 --> 00:50:51,040
bob will come back
1296
00:50:51,040 --> 00:50:53,440
why does this happen
1297
00:50:53,440 --> 00:50:56,480
because our list has four nodes
1298
00:50:56,480 --> 00:50:58,079
as created here
1299
00:50:58,079 --> 00:51:00,559
and those nodes will always be there
1300
00:51:00,559 --> 00:51:03,280
unless we go in and manually delete the
1301
00:51:03,280 --> 00:51:05,040
object itself
1302
00:51:05,040 --> 00:51:07,599
so far we've traversed our list searched
1303
00:51:07,599 --> 00:51:10,319
our list inserted a new header deleted a
1304
00:51:10,319 --> 00:51:12,559
node and last but not least we're going
1305
00:51:12,559 --> 00:51:14,240
to delete our tail
1306
00:51:14,240 --> 00:51:16,880
yep that would be poor jenny
1307
00:51:16,880 --> 00:51:18,319
she's had enough of these adult
1308
00:51:18,319 --> 00:51:20,400
shenanigans and she's out of here
1309
00:51:20,400 --> 00:51:22,000
heading to new york to become the
1310
00:51:22,000 --> 00:51:24,400
greatest fashion editor that vogue has
1311
00:51:24,400 --> 00:51:26,880
ever known she's ambitious okay
1312
00:51:26,880 --> 00:51:29,200
we started the head and as long as the
1313
00:51:29,200 --> 00:51:32,000
temp dot next next is not none our
1314
00:51:32,000 --> 00:51:34,480
pointer is two nodes ahead we make our
1315
00:51:34,480 --> 00:51:37,200
temp the next node and set it to none
1316
00:51:37,200 --> 00:51:38,480
voila
1317
00:51:38,480 --> 00:51:41,599
best of luck jenny
1318
00:51:44,559 --> 00:51:46,800
so there you have it some very basic
1319
00:51:46,800 --> 00:51:49,359
foundational algorithms for linked lists
1320
00:51:49,359 --> 00:51:52,559
which in itself is a complicated subject
1321
00:51:52,559 --> 00:51:54,480
but if you get these classical concepts
1322
00:51:54,480 --> 00:51:56,960
down solid it becomes easier and easier
1323
00:51:56,960 --> 00:51:59,839
to build up from on your own once you're
1324
00:51:59,839 --> 00:52:01,680
more comfortable with singly linked
1325
00:52:01,680 --> 00:52:04,000
lists try to challenge yourself with
1326
00:52:04,000 --> 00:52:06,000
doubly linked lists with pointers that
1327
00:52:06,000 --> 00:52:08,800
point back who knows maybe bob will
1328
00:52:08,800 --> 00:52:11,200
shape up and amy will go
1329
00:52:11,200 --> 00:52:14,079
or point get it
1330
00:52:14,079 --> 00:52:17,559
back to bob
1331
00:52:21,040 --> 00:52:24,720
for our mind breakers section in data
1332
00:52:24,720 --> 00:52:27,200
structures we're going to be looking at
1333
00:52:27,200 --> 00:52:29,839
hash tables right off the rib i'm going
1334
00:52:29,839 --> 00:52:31,680
to tell you the key phrases or terms you
1335
00:52:31,680 --> 00:52:33,359
need to be familiar with when it comes
1336
00:52:33,359 --> 00:52:36,960
to hash tables associative arrays
1337
00:52:36,960 --> 00:52:38,960
hash functions
1338
00:52:38,960 --> 00:52:41,839
key value pairs collision
1339
00:52:41,839 --> 00:52:43,280
and chaining
1340
00:52:43,280 --> 00:52:45,280
a hash table consists of an array of
1341
00:52:45,280 --> 00:52:48,000
pockets or buckets where each stores a
1342
00:52:48,000 --> 00:52:50,800
key value pair in order to locate the
1343
00:52:50,800 --> 00:52:52,720
pocket where a key value pair should be
1344
00:52:52,720 --> 00:52:54,559
stored the key is passed through a
1345
00:52:54,559 --> 00:52:56,480
hashing function
1346
00:52:56,480 --> 00:52:58,480
this function returns an integer which
1347
00:52:58,480 --> 00:53:01,280
is used as the pairs index in the array
1348
00:53:01,280 --> 00:53:03,280
of buckets when we want to retrieve a
1349
00:53:03,280 --> 00:53:06,400
key value pair we supply the key to the
1350
00:53:06,400 --> 00:53:08,880
same hashing function receive its index
1351
00:53:08,880 --> 00:53:10,559
and use the index to find it in the
1352
00:53:10,559 --> 00:53:11,680
array
1353
00:53:11,680 --> 00:53:14,240
associative arrays can be implemented
1354
00:53:14,240 --> 00:53:16,000
with many different underlying data
1355
00:53:16,000 --> 00:53:18,160
structures and it refers to an array
1356
00:53:18,160 --> 00:53:20,640
with strings as an index rather than
1357
00:53:20,640 --> 00:53:22,960
storing element values in a strict
1358
00:53:22,960 --> 00:53:25,599
linear index order this stores them in
1359
00:53:25,599 --> 00:53:28,319
combination with key values multiple
1360
00:53:28,319 --> 00:53:31,079
indices are used to access values in a
1361
00:53:31,079 --> 00:53:33,599
multi-dimensional array which contains
1362
00:53:33,599 --> 00:53:37,200
one or more arrays a non-performant one
1363
00:53:37,200 --> 00:53:39,200
can be implemented by simply storing
1364
00:53:39,200 --> 00:53:41,599
items in an array and iterating through
1365
00:53:41,599 --> 00:53:43,760
the array when searching remember the
1366
00:53:43,760 --> 00:53:46,000
wallet with lots of cash
1367
00:53:46,000 --> 00:53:48,319
associative arrays and hash tables are
1368
00:53:48,319 --> 00:53:50,079
often confused because associative
1369
00:53:50,079 --> 00:53:52,800
arrays are so often implemented as hash
1370
00:53:52,800 --> 00:53:55,680
tables according to wikipedia
1371
00:53:55,680 --> 00:53:58,400
a hash table uses a hash function to
1372
00:53:58,400 --> 00:54:01,280
compute an index also called a hash code
1373
00:54:01,280 --> 00:54:03,599
into arrays of buckets or slots from
1374
00:54:03,599 --> 00:54:06,480
which the desired value can be found
1375
00:54:06,480 --> 00:54:09,440
during lookup the key is hashed and the
1376
00:54:09,440 --> 00:54:11,359
resulting hash indicates where the
1377
00:54:11,359 --> 00:54:13,599
corresponding value is stored
1378
00:54:13,599 --> 00:54:16,000
in many situations hash tables turn out
1379
00:54:16,000 --> 00:54:18,240
to be on average more efficient than
1380
00:54:18,240 --> 00:54:20,880
search trees or any other table lookup
1381
00:54:20,880 --> 00:54:22,800
structure for this reason they are
1382
00:54:22,800 --> 00:54:25,040
widely used in many kinds of computer
1383
00:54:25,040 --> 00:54:27,440
software particularly for associative
1384
00:54:27,440 --> 00:54:31,839
arrays database indexes caches and sets
1385
00:54:31,839 --> 00:54:34,079
to summarize we can use hash tables to
1386
00:54:34,079 --> 00:54:37,359
store retrieve and delete data uniquely
1387
00:54:37,359 --> 00:54:39,920
based on their unique key
1388
00:54:39,920 --> 00:54:42,400
the most valuable aspect of a hash table
1389
00:54:42,400 --> 00:54:44,799
over other abstract data structures is
1390
00:54:44,799 --> 00:54:47,599
its speed to perform insertion deletion
1391
00:54:47,599 --> 00:54:49,359
and search operations
1392
00:54:49,359 --> 00:54:51,040
hash tables can do
1393
00:54:51,040 --> 00:54:53,200
all of them in constant time
1394
00:54:53,200 --> 00:54:54,640
for those unfamiliar with time
1395
00:54:54,640 --> 00:54:58,559
complexity big o notation constant time
1396
00:54:58,559 --> 00:55:01,200
is the fastest possible time complexity
1397
00:55:01,200 --> 00:55:03,119
hash tables can perform nearly all
1398
00:55:03,119 --> 00:55:07,200
methods except list very fast in o b o
1399
00:55:07,200 --> 00:55:08,880
one time
1400
00:55:08,880 --> 00:55:11,200
hash tables have to support three
1401
00:55:11,200 --> 00:55:12,240
functions
1402
00:55:12,240 --> 00:55:14,720
insert for key value
1403
00:55:14,720 --> 00:55:15,599
get
1404
00:55:15,599 --> 00:55:16,400
key
1405
00:55:16,400 --> 00:55:18,960
or delete a key
1406
00:55:18,960 --> 00:55:21,119
collision happens when there could
1407
00:55:21,119 --> 00:55:23,520
possibly be two or more pieces of data
1408
00:55:23,520 --> 00:55:24,319
in
1409
00:55:24,319 --> 00:55:26,640
data set x that will hash to the same
1410
00:55:26,640 --> 00:55:28,880
integer and data set y
1411
00:55:28,880 --> 00:55:30,799
this means that whenever two keys have
1412
00:55:30,799 --> 00:55:33,359
the same hash value it's considered a
1413
00:55:33,359 --> 00:55:34,480
collision
1414
00:55:34,480 --> 00:55:36,799
what should our hash table do if it just
1415
00:55:36,799 --> 00:55:38,960
wrote the data into the location anyway
1416
00:55:38,960 --> 00:55:41,200
we would be losing the object that is
1417
00:55:41,200 --> 00:55:43,359
already stored under a different key
1418
00:55:43,359 --> 00:55:45,760
ideally we want our hash values to be
1419
00:55:45,760 --> 00:55:48,000
evenly distributed among our buckets as
1420
00:55:48,000 --> 00:55:50,720
possible to take full advantage of each
1421
00:55:50,720 --> 00:55:53,119
bucket and avoid collisions
1422
00:55:53,119 --> 00:55:55,599
but generally speaking this is unlikely
1423
00:55:55,599 --> 00:55:58,319
so this is where two common methods to
1424
00:55:58,319 --> 00:56:00,880
solve are employed separate chaining
1425
00:56:00,880 --> 00:56:02,960
using linked lists or binary search
1426
00:56:02,960 --> 00:56:05,680
trees for example and local addressing
1427
00:56:05,680 --> 00:56:08,480
using linear probing
1428
00:56:08,480 --> 00:56:10,880
with some basic concepts of hash tables
1429
00:56:10,880 --> 00:56:13,200
under your belt a fun exercise or
1430
00:56:13,200 --> 00:56:15,520
challenge that you can try would be
1431
00:56:15,520 --> 00:56:17,440
pattern matching on strings using the
1432
00:56:17,440 --> 00:56:19,680
robin carp algorithm
1433
00:56:19,680 --> 00:56:22,160
yes it's fairly advanced and yes this is
1434
00:56:22,160 --> 00:56:25,040
our mind breaker problem but shoot for
1435
00:56:25,040 --> 00:56:27,440
the stars people who knows you might
1436
00:56:27,440 --> 00:56:31,000
just surprise yourself
1437
00:56:31,520 --> 00:56:33,599
what have we learned what have we
1438
00:56:33,599 --> 00:56:35,200
learned from lesson two
1439
00:56:35,200 --> 00:56:36,319
okay
1440
00:56:36,319 --> 00:56:39,760
we touched on a one-dimensional raise as
1441
00:56:39,760 --> 00:56:41,520
our data structure of choice at our
1442
00:56:41,520 --> 00:56:42,960
basic level
1443
00:56:42,960 --> 00:56:45,280
we looked at contiguous versus
1444
00:56:45,280 --> 00:56:48,319
non-contiguous different ways to search
1445
00:56:48,319 --> 00:56:49,440
linear
1446
00:56:49,440 --> 00:56:50,640
binary
1447
00:56:50,640 --> 00:56:53,359
and we sort bubble insert and even
1448
00:56:53,359 --> 00:56:55,359
talked about an array with more than one
1449
00:56:55,359 --> 00:56:58,640
dimension we learned about dunkles
1450
00:56:58,640 --> 00:57:01,280
no no no no we learned about link list
1451
00:57:01,280 --> 00:57:03,200
by creating a family of sorts to
1452
00:57:03,200 --> 00:57:06,400
demonstrate how to traverse search add
1453
00:57:06,400 --> 00:57:08,240
and delete headers
1454
00:57:08,240 --> 00:57:10,799
nodes tails on linked lists some of the
1455
00:57:10,799 --> 00:57:12,799
most common operations used that every
1456
00:57:12,799 --> 00:57:15,200
programmer should be familiar with
1457
00:57:15,200 --> 00:57:18,000
we broke our heads on hash tables and
1458
00:57:18,000 --> 00:57:20,160
hashing functions by going over what
1459
00:57:20,160 --> 00:57:21,839
they are and what can happen when
1460
00:57:21,839 --> 00:57:24,319
problems arise from colliding data
1461
00:57:24,319 --> 00:57:27,680
within a bucket ultimately hash tables
1462
00:57:27,680 --> 00:57:30,240
are for storing retrieving and deleting
1463
00:57:30,240 --> 00:57:32,799
data based on key value pairs and on
1464
00:57:32,799 --> 00:57:34,640
average are more efficient than search
1465
00:57:34,640 --> 00:57:36,319
trees or any other table lookup
1466
00:57:36,319 --> 00:57:39,319
structure
1467
00:57:40,230 --> 00:57:50,559
[Music]
1468
00:57:50,559 --> 00:57:52,720
i learned about the divide and conquer
1469
00:57:52,720 --> 00:57:55,119
concept from a very early age
1470
00:57:55,119 --> 00:57:57,440
it was traumatizing actually you see my
1471
00:57:57,440 --> 00:57:59,440
brother and i used to fight all the time
1472
00:57:59,440 --> 00:58:01,599
when we'd swim in the pool and finally
1473
00:58:01,599 --> 00:58:04,000
one day our mom came and said to us just
1474
00:58:04,000 --> 00:58:06,079
divide it in half and you stand once and
1475
00:58:06,079 --> 00:58:08,400
you stay on another side
1476
00:58:08,400 --> 00:58:10,559
my brother picked the top half
1477
00:58:10,559 --> 00:58:12,880
so yeah divide and conquer
1478
00:58:12,880 --> 00:58:15,920
i drowned but only momentarily
1479
00:58:15,920 --> 00:58:18,000
in programming when we cross paths with
1480
00:58:18,000 --> 00:58:19,920
programs that are too complicated to be
1481
00:58:19,920 --> 00:58:22,079
solved all at once we can implement
1482
00:58:22,079 --> 00:58:24,000
methods to break them down into smaller
1483
00:58:24,000 --> 00:58:26,400
pieces and if we solve all the smaller
1484
00:58:26,400 --> 00:58:28,720
pieces we are in essence dividing out
1485
00:58:28,720 --> 00:58:29,760
the big
1486
00:58:29,760 --> 00:58:31,760
solving the small and in the end this
1487
00:58:31,760 --> 00:58:34,640
makes our lives so much easier a divide
1488
00:58:34,640 --> 00:58:36,880
and conquer algorithm paradigm can solve
1489
00:58:36,880 --> 00:58:39,680
a large problem by recursively breaking
1490
00:58:39,680 --> 00:58:42,079
it down into smaller sub-problems until
1491
00:58:42,079 --> 00:58:43,760
they become simple enough to be solved
1492
00:58:43,760 --> 00:58:45,760
directly it could be compared to the
1493
00:58:45,760 --> 00:58:47,920
age-old problem of swallowing an
1494
00:58:47,920 --> 00:58:48,880
elephant
1495
00:58:48,880 --> 00:58:51,200
can't do that so we devour it one bite
1496
00:58:51,200 --> 00:58:52,319
at a time
1497
00:58:52,319 --> 00:58:54,079
actually it's more of a solution of
1498
00:58:54,079 --> 00:58:56,720
three bytes dividing solving and then
1499
00:58:56,720 --> 00:58:58,640
merging it all back together
1500
00:58:58,640 --> 00:59:00,720
unfortunately since divide and conquer
1501
00:59:00,720 --> 00:59:02,720
algorithms are usually implemented
1502
00:59:02,720 --> 00:59:04,960
recursively this means they require
1503
00:59:04,960 --> 00:59:07,599
additional memory allocation and without
1504
00:59:07,599 --> 00:59:10,480
sufficient memory a stack overflow error
1505
00:59:10,480 --> 00:59:12,559
can or will occur
1506
00:59:12,559 --> 00:59:14,400
this is due to the overhead of the
1507
00:59:14,400 --> 00:59:17,119
repeated subroutine calls along with
1508
00:59:17,119 --> 00:59:19,359
storing the call stack the state of each
1509
00:59:19,359 --> 00:59:21,520
point in the recursion and that can
1510
00:59:21,520 --> 00:59:24,319
outweigh advantages of any approach
1511
00:59:24,319 --> 00:59:26,960
on the flip side if the dnc solutions
1512
00:59:26,960 --> 00:59:28,720
are implemented by a non-recursive
1513
00:59:28,720 --> 00:59:30,880
algorithm that stores the partial sub
1514
00:59:30,880 --> 00:59:32,960
problems in some explicit data structure
1515
00:59:32,960 --> 00:59:35,359
like a stack queue or priority queue it
1516
00:59:35,359 --> 00:59:37,200
can allow more freedom in the choice of
1517
00:59:37,200 --> 00:59:39,119
the sub-problem that is to be solved
1518
00:59:39,119 --> 00:59:41,599
next a feature that is important in some
1519
00:59:41,599 --> 00:59:44,480
applications including breath first
1520
00:59:44,480 --> 00:59:46,400
recursion and the branch and brown
1521
00:59:46,400 --> 00:59:48,640
branch and bound method
1522
00:59:48,640 --> 00:59:51,040
for function optimization
1523
00:59:51,040 --> 00:59:53,440
second even if a solution to the full
1524
00:59:53,440 --> 00:59:56,400
problem is already known like sorting a
1525
00:59:56,400 --> 00:59:58,480
brute force comparison of all elements
1526
00:59:58,480 --> 01:00:00,799
with one another divide and conquer can
1527
01:00:00,799 --> 01:00:03,760
substantially reduce computational cost
1528
01:00:03,760 --> 01:00:06,799
lower cost means higher efficiency
1529
01:00:06,799 --> 01:00:09,359
third explicitly recursive subdivision
1530
01:00:09,359 --> 01:00:11,280
can have benefits to the temporary
1531
01:00:11,280 --> 01:00:13,599
memory of the computer not the main hard
1532
01:00:13,599 --> 01:00:14,640
drive
1533
01:00:14,640 --> 01:00:16,559
which is called a cache
1534
01:00:16,559 --> 01:00:18,640
using divide and conquer one can even
1535
01:00:18,640 --> 01:00:20,880
design an algorithm to use all levels of
1536
01:00:20,880 --> 01:00:23,280
the cache hierarchy in such a way as to
1537
01:00:23,280 --> 01:00:25,280
have an algorithm that is optimally
1538
01:00:25,280 --> 01:00:28,160
cached oblivious which means operating
1539
01:00:28,160 --> 01:00:30,319
independently from its temporary memory
1540
01:00:30,319 --> 01:00:31,839
storage
1541
01:00:31,839 --> 01:00:33,920
this approach has been successfully
1542
01:00:33,920 --> 01:00:36,160
applied to many problems including
1543
01:00:36,160 --> 01:00:38,160
matrix multiplication which we're going
1544
01:00:38,160 --> 01:00:40,960
to get into in just a few minutes
1545
01:00:40,960 --> 01:00:43,119
so let's get into it and start at the
1546
01:00:43,119 --> 01:00:44,880
base level algorithm for divide and
1547
01:00:44,880 --> 01:00:48,559
conquer the merge sort
1548
01:00:51,280 --> 01:00:55,520
conceptually merge sort works as follows
1549
01:00:55,520 --> 01:00:58,559
divide the unsorted list into two sub
1550
01:00:58,559 --> 01:01:00,880
lists about half the size
1551
01:01:00,880 --> 01:01:03,520
sort each of the two sub lists
1552
01:01:03,520 --> 01:01:06,400
merge the two sorted sublists back into
1553
01:01:06,400 --> 01:01:08,079
one sorted list
1554
01:01:08,079 --> 01:01:11,599
invented by john von neumann in 1945 the
1555
01:01:11,599 --> 01:01:13,599
merger sort is an efficient general
1556
01:01:13,599 --> 01:01:15,680
all-purpose and comparison-based sorting
1557
01:01:15,680 --> 01:01:18,079
algorithm an example of merge sort would
1558
01:01:18,079 --> 01:01:19,920
be to first divide the list into the
1559
01:01:19,920 --> 01:01:23,200
smallest unit one element this becomes a
1560
01:01:23,200 --> 01:01:24,880
list itself
1561
01:01:24,880 --> 01:01:26,799
then compare each element which is a
1562
01:01:26,799 --> 01:01:29,280
list itself remember with the adjacent
1563
01:01:29,280 --> 01:01:31,760
list to sort and merge them done
1564
01:01:31,760 --> 01:01:33,839
repetitively the end results in the
1565
01:01:33,839 --> 01:01:36,400
elements sorted and merged
1566
01:01:36,400 --> 01:01:37,920
i understand that can be a little bit
1567
01:01:37,920 --> 01:01:40,079
confusing but let's think of it in this
1568
01:01:40,079 --> 01:01:41,599
way
1569
01:01:41,599 --> 01:01:43,280
say we have two different lists of
1570
01:01:43,280 --> 01:01:46,000
numbers list a and list b and then we'll
1571
01:01:46,000 --> 01:01:49,119
have an empty list we'll call c
1572
01:01:49,119 --> 01:01:52,079
lists a and b are ordered from least to
1573
01:01:52,079 --> 01:01:53,839
greatest and what we would do is
1574
01:01:53,839 --> 01:01:57,599
repeatedly compare least value min of a
1575
01:01:57,599 --> 01:02:01,200
to the least value min of b and remove
1576
01:02:01,200 --> 01:02:03,119
the lesser value and then append that
1577
01:02:03,119 --> 01:02:04,960
value into c
1578
01:02:04,960 --> 01:02:07,920
when one list is exhausted we append the
1579
01:02:07,920 --> 01:02:10,079
the remaining items into c they're
1580
01:02:10,079 --> 01:02:12,160
already started so we're good there
1581
01:02:12,160 --> 01:02:14,079
then we just return list c which is
1582
01:02:14,079 --> 01:02:16,640
sorted we're systematically merging a
1583
01:02:16,640 --> 01:02:20,079
and b together and appending it into c
1584
01:02:20,079 --> 01:02:22,640
but for this lesson and although you can
1585
01:02:22,640 --> 01:02:26,000
append or extend on an empty list to see
1586
01:02:26,000 --> 01:02:28,079
we're going to swap our elements i just
1587
01:02:28,079 --> 01:02:29,920
wanted to share a very simplistic
1588
01:02:29,920 --> 01:02:32,160
explanation for that hoping that would
1589
01:02:32,160 --> 01:02:34,319
give you an idea of the concept
1590
01:02:34,319 --> 01:02:36,559
typically creating more space for an
1591
01:02:36,559 --> 01:02:39,200
empty list or temporary list for storage
1592
01:02:39,200 --> 01:02:41,680
isn't always the best approach we want
1593
01:02:41,680 --> 01:02:43,920
we want to do our best to optimize our
1594
01:02:43,920 --> 01:02:46,160
program if we can
1595
01:02:46,160 --> 01:02:48,799
let's head into our ides and write our
1596
01:02:48,799 --> 01:02:51,280
programs
1597
01:02:53,520 --> 01:02:55,440
the best way to see the different
1598
01:02:55,440 --> 01:02:57,599
methods of the merge store and their
1599
01:02:57,599 --> 01:02:59,920
efficiencies is to compare four programs
1600
01:02:59,920 --> 01:03:01,280
that i have here
1601
01:03:01,280 --> 01:03:03,200
some things i wrote myself
1602
01:03:03,200 --> 01:03:05,440
some things i borrowed
1603
01:03:05,440 --> 01:03:07,599
we're going to look at a single array of
1604
01:03:07,599 --> 01:03:09,920
10 integers and just sort it by brute
1605
01:03:09,920 --> 01:03:12,240
force this means that the program takes
1606
01:03:12,240 --> 01:03:15,280
the first number in index position 0 and
1607
01:03:15,280 --> 01:03:17,760
compares it to each and every number in
1608
01:03:17,760 --> 01:03:18,880
the array
1609
01:03:18,880 --> 01:03:21,680
if it's the lowest it gets reassigned at
1610
01:03:21,680 --> 01:03:23,920
the first position
1611
01:03:23,920 --> 01:03:25,920
then it moves to the next number and
1612
01:03:25,920 --> 01:03:28,400
does the same thing it gets compared to
1613
01:03:28,400 --> 01:03:30,480
each and every integer and the lowest
1614
01:03:30,480 --> 01:03:33,200
number gets reassigned at index position
1615
01:03:33,200 --> 01:03:35,359
one and so on and so forth
1616
01:03:35,359 --> 01:03:37,640
for this little iterative program it's
1617
01:03:37,640 --> 01:03:40,640
168 iterations or cycles to get an
1618
01:03:40,640 --> 01:03:43,760
output and that's just for 10 elements
1619
01:03:43,760 --> 01:03:45,520
keep that in mind as we look at the
1620
01:03:45,520 --> 01:03:47,920
differences within the merge sort
1621
01:03:47,920 --> 01:03:49,760
our first real program for the merge
1622
01:03:49,760 --> 01:03:52,400
sort is about as simple as we can get it
1623
01:03:52,400 --> 01:03:54,160
we're starting with an array that is
1624
01:03:54,160 --> 01:03:56,559
already split in half and sorted the
1625
01:03:56,559 --> 01:03:58,640
program we're looking at right now won't
1626
01:03:58,640 --> 01:04:01,119
work properly if our two halves are not
1627
01:04:01,119 --> 01:04:02,720
already sorted
1628
01:04:02,720 --> 01:04:03,599
why
1629
01:04:03,599 --> 01:04:05,920
because ultimately this is our divide
1630
01:04:05,920 --> 01:04:08,400
and conquer algorithm we are dividing
1631
01:04:08,400 --> 01:04:11,280
our array into two parts and conquering
1632
01:04:11,280 --> 01:04:14,000
both halves separately by sorting them
1633
01:04:14,000 --> 01:04:16,640
and then merging them back together
1634
01:04:16,640 --> 01:04:18,720
remember just a few minutes ago when we
1635
01:04:18,720 --> 01:04:21,119
talked about list a list b and empty
1636
01:04:21,119 --> 01:04:22,240
list c
1637
01:04:22,240 --> 01:04:24,480
this program is comparing each number at
1638
01:04:24,480 --> 01:04:27,039
each index position determining which is
1639
01:04:27,039 --> 01:04:29,359
lower and then popping it out and then
1640
01:04:29,359 --> 01:04:32,880
appending it into our empty list c
1641
01:04:32,880 --> 01:04:33,760
and
1642
01:04:33,760 --> 01:04:36,240
then just in case either list is longer
1643
01:04:36,240 --> 01:04:38,880
than the other that leftover portion
1644
01:04:38,880 --> 01:04:41,039
just gets added to c and since it's
1645
01:04:41,039 --> 01:04:43,200
already sorted we'll have no problems
1646
01:04:43,200 --> 01:04:44,559
there
1647
01:04:44,559 --> 01:04:46,480
this is a neat little non-recursive
1648
01:04:46,480 --> 01:04:48,480
merge sort for an array that has a small
1649
01:04:48,480 --> 01:04:50,559
amount of elements and is already
1650
01:04:50,559 --> 01:04:53,440
divided in half however since this isn't
1651
01:04:53,440 --> 01:04:55,760
a perfect world and you'll be more than
1652
01:04:55,760 --> 01:04:57,680
likely asked to write a program for an
1653
01:04:57,680 --> 01:04:59,599
array that isn't divided and sorted
1654
01:04:59,599 --> 01:05:00,799
beforehand
1655
01:05:00,799 --> 01:05:03,520
we're going to have to rewrite this
1656
01:05:03,520 --> 01:05:06,160
so here's our big dilemma do we sort our
1657
01:05:06,160 --> 01:05:08,640
halves recursively or do we sort them
1658
01:05:08,640 --> 01:05:09,920
iteratively
1659
01:05:09,920 --> 01:05:12,640
or do we sort our halves using python's
1660
01:05:12,640 --> 01:05:16,799
built-in feature called sort or sorted
1661
01:05:17,119 --> 01:05:18,880
let's shoot for sorting our halves
1662
01:05:18,880 --> 01:05:21,200
recursively this is what is called the
1663
01:05:21,200 --> 01:05:23,119
top-down method
1664
01:05:23,119 --> 01:05:25,119
what it does is repeatedly produce
1665
01:05:25,119 --> 01:05:27,760
sub-lists half by half by half until
1666
01:05:27,760 --> 01:05:30,319
there's only one sub-list or one element
1667
01:05:30,319 --> 01:05:33,119
remaining which becomes a list all in
1668
01:05:33,119 --> 01:05:36,559
itself a list of one element how many of
1669
01:05:36,559 --> 01:05:38,960
you are willing to but it's the optimal
1670
01:05:38,960 --> 01:05:41,520
or optimized method
1671
01:05:41,520 --> 01:05:44,079
well it's not
1672
01:05:44,079 --> 01:05:46,559
once we have our have sorted we continue
1673
01:05:46,559 --> 01:05:49,039
on very much like before we compare each
1674
01:05:49,039 --> 01:05:51,119
element and append it into our empty
1675
01:05:51,119 --> 01:05:52,960
list
1676
01:05:52,960 --> 01:05:55,119
now if recursion isn't the optimal
1677
01:05:55,119 --> 01:05:58,400
method then it must be iteration right
1678
01:05:58,400 --> 01:06:00,079
well yes
1679
01:06:00,079 --> 01:06:03,200
mostly this is the bottom up method
1680
01:06:03,200 --> 01:06:05,920
think of the top down just in reverse it
1681
01:06:05,920 --> 01:06:08,319
starts at one element then two elements
1682
01:06:08,319 --> 01:06:11,359
then four remember that very first brute
1683
01:06:11,359 --> 01:06:14,319
force method of sorting a list we can do
1684
01:06:14,319 --> 01:06:16,799
that after we divide the array into two
1685
01:06:16,799 --> 01:06:18,640
parts and then merge it all back
1686
01:06:18,640 --> 01:06:20,240
together hmm
1687
01:06:20,240 --> 01:06:22,319
let's see what happens when we run it in
1688
01:06:22,319 --> 01:06:24,480
something like leeco that'll really put
1689
01:06:24,480 --> 01:06:27,590
it to the test
1690
01:06:27,590 --> 01:06:44,840
[Music]
1691
01:06:51,920 --> 01:06:54,960
okay well that didn't go as planned but
1692
01:06:54,960 --> 01:06:57,760
it does work it's just bad on really big
1693
01:06:57,760 --> 01:06:58,880
arrays
1694
01:06:58,880 --> 01:07:00,880
so what is the bust
1695
01:07:00,880 --> 01:07:03,920
using python's awesome sort or sorted
1696
01:07:03,920 --> 01:07:05,520
feature of course
1697
01:07:05,520 --> 01:07:07,839
well splitter array have python sorted
1698
01:07:07,839 --> 01:07:10,559
for us and the rest is good to go with
1699
01:07:10,559 --> 01:07:13,520
our 10 element array it's only 34 steps
1700
01:07:13,520 --> 01:07:15,920
to completion compare that to our brute
1701
01:07:15,920 --> 01:07:18,400
force program no dividing no conquering
1702
01:07:18,400 --> 01:07:21,760
with almost 170 iterations our bottom up
1703
01:07:21,760 --> 01:07:24,480
iterative method is smoking
1704
01:07:24,480 --> 01:07:26,160
check it in leak code
1705
01:07:26,160 --> 01:07:28,640
talk about optimization
1706
01:07:28,640 --> 01:07:31,599
now let's move out into deeper waters
1707
01:07:31,599 --> 01:07:35,599
with some matrix multiplication
1708
01:07:41,520 --> 01:07:45,440
matrix multiplication is wild y'all
1709
01:07:45,440 --> 01:07:47,200
but it is a fundamental concept to
1710
01:07:47,200 --> 01:07:49,200
understanding computing among the most
1711
01:07:49,200 --> 01:07:51,119
common tools in electrical engineering
1712
01:07:51,119 --> 01:07:53,280
and computer science are rectangular
1713
01:07:53,280 --> 01:07:56,400
grids of numbers known as matrices the
1714
01:07:56,400 --> 01:07:58,720
numbers in a matrix can represent data
1715
01:07:58,720 --> 01:08:00,720
and they can also represent mathematical
1716
01:08:00,720 --> 01:08:01,920
equations
1717
01:08:01,920 --> 01:08:03,920
in many time sensitive engineering
1718
01:08:03,920 --> 01:08:06,079
applications multiplying matrices can
1719
01:08:06,079 --> 01:08:08,559
give a quick but good approximations of
1720
01:08:08,559 --> 01:08:11,119
much more complicated calculations did
1721
01:08:11,119 --> 01:08:12,799
you know that one of the areas of
1722
01:08:12,799 --> 01:08:14,559
computer science in which matrix
1723
01:08:14,559 --> 01:08:17,040
multiplication is particularly useful is
1724
01:08:17,040 --> 01:08:19,520
graphics it's crazy to think that a
1725
01:08:19,520 --> 01:08:22,560
digital image is basically a matrix with
1726
01:08:22,560 --> 01:08:25,439
rows and columns of another matrix
1727
01:08:25,439 --> 01:08:27,600
corresponding to rows and columns of
1728
01:08:27,600 --> 01:08:29,600
pixels and the numerical entries
1729
01:08:29,600 --> 01:08:32,960
correspond to a pixel color value
1730
01:08:32,960 --> 01:08:35,439
decoding digital video for instance
1731
01:08:35,439 --> 01:08:37,839
requires matrix multiplication and did
1732
01:08:37,839 --> 01:08:40,080
you know that mit researchers were able
1733
01:08:40,080 --> 01:08:42,080
to build one of the first tips to
1734
01:08:42,080 --> 01:08:44,719
implement a high efficiency video coding
1735
01:08:44,719 --> 01:08:47,600
standard for ultra high definition tvs
1736
01:08:47,600 --> 01:08:48,960
partly because of patterns they
1737
01:08:48,960 --> 01:08:50,799
discerned in the matrices
1738
01:08:50,799 --> 01:08:52,479
pretty cool huh
1739
01:08:52,479 --> 01:08:55,040
so the dimensions are listed as rows and
1740
01:08:55,040 --> 01:08:58,960
columns or in many equations n times m
1741
01:08:58,960 --> 01:09:00,719
where n represents the number of rows
1742
01:09:00,719 --> 01:09:03,520
and n represents the number of columns
1743
01:09:03,520 --> 01:09:05,359
be careful that you that you know the
1744
01:09:05,359 --> 01:09:07,600
difference between rows and columns and
1745
01:09:07,600 --> 01:09:10,479
don't mix them up rows go across columns
1746
01:09:10,479 --> 01:09:12,960
go up and down to see how matrices are
1747
01:09:12,960 --> 01:09:15,120
multiplied check out this graphic that
1748
01:09:15,120 --> 01:09:18,000
shows how it all works we multiply each
1749
01:09:18,000 --> 01:09:20,319
element in the row by each element in
1750
01:09:20,319 --> 01:09:22,719
the column and then we add them together
1751
01:09:22,719 --> 01:09:24,560
in order to code this we'll start with
1752
01:09:24,560 --> 01:09:26,719
the naive method it's not too bad to
1753
01:09:26,719 --> 01:09:28,719
learn however just know that it can get
1754
01:09:28,719 --> 01:09:31,040
very expensive as we increase the size
1755
01:09:31,040 --> 01:09:33,439
of our matrices for larger matrix
1756
01:09:33,439 --> 01:09:34,399
operations
1757
01:09:34,399 --> 01:09:36,399
we wouldn't want to use too many nested
1758
01:09:36,399 --> 01:09:38,158
loops because it could really start
1759
01:09:38,158 --> 01:09:39,439
bogging down
1760
01:09:39,439 --> 01:09:41,679
ideally we would want to use optimized
1761
01:09:41,679 --> 01:09:44,158
software packages like numpy
1762
01:09:44,158 --> 01:09:46,080
numpy should be the go-to which is
1763
01:09:46,080 --> 01:09:49,439
insanely faster and easy too but before
1764
01:09:49,439 --> 01:09:52,640
we start cheating we really need to
1765
01:09:52,640 --> 01:09:54,158
examine what's going on underneath the
1766
01:09:54,158 --> 01:09:56,320
hood like how a program is created that
1767
01:09:56,320 --> 01:09:59,040
multiplies matrices in python
1768
01:09:59,040 --> 01:10:01,040
because if we can get a really good
1769
01:10:01,040 --> 01:10:02,480
handle on this
1770
01:10:02,480 --> 01:10:05,280
we'll get a better handle on the mind
1771
01:10:05,280 --> 01:10:06,670
breaker
1772
01:10:06,670 --> 01:10:12,000
[Music]
1773
01:10:12,000 --> 01:10:14,640
okay so what we're doing is basically
1774
01:10:14,640 --> 01:10:16,880
creating a calculator in python that
1775
01:10:16,880 --> 01:10:19,120
multiplies matrices and you might be
1776
01:10:19,120 --> 01:10:21,920
wondering hey what's the deal here how
1777
01:10:21,920 --> 01:10:24,320
is this part of dividing and conquering
1778
01:10:24,320 --> 01:10:26,560
algorithms we're definitely going to get
1779
01:10:26,560 --> 01:10:28,800
into that but this is all preparation
1780
01:10:28,800 --> 01:10:31,280
for the mind breaker lesson you'll need
1781
01:10:31,280 --> 01:10:33,760
this under your belt first plus it's a
1782
01:10:33,760 --> 01:10:36,159
really good foray into matrices which is
1783
01:10:36,159 --> 01:10:38,320
one of the most well studied problems in
1784
01:10:38,320 --> 01:10:41,679
numerical computing today so yeah let's
1785
01:10:41,679 --> 01:10:42,800
dig in
1786
01:10:42,800 --> 01:10:46,640
we'll create two matrices x and y and to
1787
01:10:46,640 --> 01:10:48,800
store the results of our products we'll
1788
01:10:48,800 --> 01:10:51,760
create an empty matrix we'll call result
1789
01:10:51,760 --> 01:10:54,159
the most popular method in my humble
1790
01:10:54,159 --> 01:10:56,400
opinion is to use nested loops to
1791
01:10:56,400 --> 01:10:58,640
iterate over the rows and columns and
1792
01:10:58,640 --> 01:11:01,360
implement the results into our matrix of
1793
01:11:01,360 --> 01:11:04,239
zeros using an addition operator that
1794
01:11:04,239 --> 01:11:06,560
adds our product of the rows
1795
01:11:06,560 --> 01:11:08,640
and the columns of x and y
1796
01:11:08,640 --> 01:11:11,920
we could do this recursively sure but it
1797
01:11:11,920 --> 01:11:14,320
wouldn't really be advantageous the goal
1798
01:11:14,320 --> 01:11:16,159
is to help you understand the logic
1799
01:11:16,159 --> 01:11:18,239
behind matrix multiplication so we can
1800
01:11:18,239 --> 01:11:20,880
move on to our mind breaker lesson
1801
01:11:20,880 --> 01:11:22,960
strassen's algorithm for matrix
1802
01:11:22,960 --> 01:11:25,960
multiplication
1803
01:11:28,800 --> 01:11:31,040
volker strassen is a german
1804
01:11:31,040 --> 01:11:32,640
mathematician who made important
1805
01:11:32,640 --> 01:11:34,800
contributions to the analysis of
1806
01:11:34,800 --> 01:11:37,199
algorithms and has received many awards
1807
01:11:37,199 --> 01:11:39,600
over his lifetime he's still alive by
1808
01:11:39,600 --> 01:11:40,400
the way
1809
01:11:40,400 --> 01:11:43,520
he began his research as a probabilist
1810
01:11:43,520 --> 01:11:47,280
his 1964 paper an invariance principle
1811
01:11:47,280 --> 01:11:49,360
for the law of the iterated logarithm
1812
01:11:49,360 --> 01:11:51,679
defined a functional form of the law of
1813
01:11:51,679 --> 01:11:53,840
the iterated logarithm showing a form of
1814
01:11:53,840 --> 01:11:57,040
scale scale and variance in random walks
1815
01:11:57,040 --> 01:11:59,120
this result now known as strassen's
1816
01:11:59,120 --> 01:12:01,280
environments principle or strassen's law
1817
01:12:01,280 --> 01:12:03,199
of the iterated logarithm has been
1818
01:12:03,199 --> 01:12:05,760
highly cited and led to the 1966
1819
01:12:05,760 --> 01:12:07,920
presentation at the international
1820
01:12:07,920 --> 01:12:10,239
congress of mathematicians
1821
01:12:10,239 --> 01:12:12,400
now if you know what an iterative
1822
01:12:12,400 --> 01:12:15,120
logarithm is that shows a form of scale
1823
01:12:15,120 --> 01:12:17,600
and variance in random walks or in
1824
01:12:17,600 --> 01:12:20,159
variance principles in general well then
1825
01:12:20,159 --> 01:12:22,159
please by all means invite us to your
1826
01:12:22,159 --> 01:12:24,480
latest book site
1827
01:12:24,480 --> 01:12:26,880
but if you're a mere mortal like the
1828
01:12:26,880 --> 01:12:28,080
rest of us
1829
01:12:28,080 --> 01:12:30,080
hold on to your hats because that was
1830
01:12:30,080 --> 01:12:32,320
only the beginning for strassen
1831
01:12:32,320 --> 01:12:34,960
three years later strassen shifted his
1832
01:12:34,960 --> 01:12:37,040
research efforts toward the analysis of
1833
01:12:37,040 --> 01:12:39,600
algorithms with a paper on the gaussian
1834
01:12:39,600 --> 01:12:42,239
elimination come on everybody knows what
1835
01:12:42,239 --> 01:12:45,040
the gaussian elimination is
1836
01:12:45,040 --> 01:12:48,000
and there in that paper he introduced
1837
01:12:48,000 --> 01:12:50,400
the first algorithm for performing
1838
01:12:50,400 --> 01:12:53,199
matrix matrix multiplication faster than
1839
01:12:53,199 --> 01:12:55,840
the o and three time bound that would
1840
01:12:55,840 --> 01:12:58,000
result from the naive method
1841
01:12:58,000 --> 01:13:01,280
this means that his algorithm is like
1842
01:13:01,280 --> 01:13:03,520
the best of the best when it comes to
1843
01:13:03,520 --> 01:13:05,760
computing the product of two two by two
1844
01:13:05,760 --> 01:13:08,719
matrices there is no formula that uses
1845
01:13:08,719 --> 01:13:11,199
fewer than seven multiplications
1846
01:13:11,199 --> 01:13:13,920
how he did it he doesn't say maybe
1847
01:13:13,920 --> 01:13:15,920
somebody flew into german can call him
1848
01:13:15,920 --> 01:13:18,880
up and ask him like what kind of person
1849
01:13:18,880 --> 01:13:20,880
do you have to be to discover some great
1850
01:13:20,880 --> 01:13:22,800
mathematical algorithm like what are
1851
01:13:22,800 --> 01:13:25,280
your hobbies can we talk what do you do
1852
01:13:25,280 --> 01:13:27,679
on the weekends i mean at this point at
1853
01:13:27,679 --> 01:13:30,400
the time of recording this he's 85 so i
1854
01:13:30,400 --> 01:13:32,719
don't know he probably just relaxes his
1855
01:13:32,719 --> 01:13:34,560
brain muscles for the most part i mean i
1856
01:13:34,560 --> 01:13:36,560
know i would they're probably still
1857
01:13:36,560 --> 01:13:39,440
smoking anyway not to knock on this
1858
01:13:39,440 --> 01:13:41,280
awesome person and as great as the
1859
01:13:41,280 --> 01:13:43,600
algorithm is and the contribution it's
1860
01:13:43,600 --> 01:13:45,760
made to matrix multiplication
1861
01:13:45,760 --> 01:13:48,320
unfortunately it's too numerically
1862
01:13:48,320 --> 01:13:51,440
unstable for some applications
1863
01:13:51,440 --> 01:13:54,480
in practice fast matrix multiplication
1864
01:13:54,480 --> 01:13:56,880
implementation for dense matrices use
1865
01:13:56,880 --> 01:13:59,120
strawson's algorithm for matrix sizes
1866
01:13:59,120 --> 01:14:01,360
above a breaking point then they switch
1867
01:14:01,360 --> 01:14:03,520
to a simpler method once the subproblem
1868
01:14:03,520 --> 01:14:06,640
size reduces to below the breakover see
1869
01:14:06,640 --> 01:14:08,719
divide and conquer in any event the
1870
01:14:08,719 --> 01:14:10,800
publication of its algorithm did result
1871
01:14:10,800 --> 01:14:13,440
in much more research about multi matrix
1872
01:14:13,440 --> 01:14:15,120
multiplication that led to faster
1873
01:14:15,120 --> 01:14:17,600
approaches it opened the door to bigger
1874
01:14:17,600 --> 01:14:20,480
and greater things which is pretty neat
1875
01:14:20,480 --> 01:14:22,640
okay now that we've got that all under
1876
01:14:22,640 --> 01:14:24,719
our belt let's take a deep dive into
1877
01:14:24,719 --> 01:14:27,120
what the algorithm really does just a
1878
01:14:27,120 --> 01:14:29,600
few minutes ago we saw the naive method
1879
01:14:29,600 --> 01:14:31,600
so you should be somewhat familiar with
1880
01:14:31,600 --> 01:14:32,400
it
1881
01:14:32,400 --> 01:14:35,360
in two two by two matrices we have eight
1882
01:14:35,360 --> 01:14:37,920
multiplications with stress since we can
1883
01:14:37,920 --> 01:14:40,080
get this down to seven with basic
1884
01:14:40,080 --> 01:14:41,840
mathematical formulas
1885
01:14:41,840 --> 01:14:44,000
and i've gotten it all written out so
1886
01:14:44,000 --> 01:14:46,719
you can see it all work in a program
1887
01:14:46,719 --> 01:14:49,600
let's take a peek
1888
01:14:50,560 --> 01:14:52,640
we're still going to keep our 2x2
1889
01:14:52,640 --> 01:14:55,600
matrices for simplicity yay
1890
01:14:55,600 --> 01:14:58,480
but we're going to look at our famous or
1891
01:14:58,480 --> 01:15:01,040
infamous methods of optimization
1892
01:15:01,040 --> 01:15:03,840
iteration and recursion for strassen's
1893
01:15:03,840 --> 01:15:05,920
algorithm we're dividing our matrices
1894
01:15:05,920 --> 01:15:08,400
not by halves but by quarters and then
1895
01:15:08,400 --> 01:15:10,480
we'll solve or conquer
1896
01:15:10,480 --> 01:15:12,640
each sub-matrix to solve the entire
1897
01:15:12,640 --> 01:15:14,080
problem
1898
01:15:14,080 --> 01:15:15,840
in our iterative method we're breaking
1899
01:15:15,840 --> 01:15:17,679
down the two matrices all the way down
1900
01:15:17,679 --> 01:15:20,800
to each individual square or quadrant
1901
01:15:20,800 --> 01:15:23,360
we'll name our passes p and simply plug
1902
01:15:23,360 --> 01:15:25,360
in our mathematical formula used to
1903
01:15:25,360 --> 01:15:27,840
compute our multiplication and addition
1904
01:15:27,840 --> 01:15:29,520
on the quadrants
1905
01:15:29,520 --> 01:15:32,400
now although we called numpy cheating
1906
01:15:32,400 --> 01:15:34,239
we're going to implement it here just
1907
01:15:34,239 --> 01:15:36,080
for a little bit of ease by instead
1908
01:15:36,080 --> 01:15:39,360
creating a result matrix of zeros we're
1909
01:15:39,360 --> 01:15:42,159
going to make a new matrix called c and
1910
01:15:42,159 --> 01:15:46,560
number each quadrant of c as c1 c2 c3
1911
01:15:46,560 --> 01:15:49,679
and c4 for each quadrant we plug in our
1912
01:15:49,679 --> 01:15:52,880
equations for our passes these equations
1913
01:15:52,880 --> 01:15:55,360
are our conquered solutions to the
1914
01:15:55,360 --> 01:15:56,880
quadrants
1915
01:15:56,880 --> 01:15:59,920
lastly we use numpy to implement a new
1916
01:15:59,920 --> 01:16:03,199
matrix by using the np dot array feature
1917
01:16:03,199 --> 01:16:06,400
and input our four c quadrants
1918
01:16:06,400 --> 01:16:09,040
pretty cool
1919
01:16:12,000 --> 01:16:14,480
the recursive solution is very similar
1920
01:16:14,480 --> 01:16:16,320
only we're recursively splitting the
1921
01:16:16,320 --> 01:16:18,239
matrices into our quadrants and
1922
01:16:18,239 --> 01:16:22,880
recursively computing our seven passes
1923
01:16:33,199 --> 01:16:36,400
what did we learn what did we learn we
1924
01:16:36,400 --> 01:16:38,560
learned that the merge store is an
1925
01:16:38,560 --> 01:16:41,199
efficient general purpose sort that can
1926
01:16:41,199 --> 01:16:43,840
be implemented in several ways including
1927
01:16:43,840 --> 01:16:46,880
the top-down and bottom-up approach
1928
01:16:46,880 --> 01:16:49,840
we learned that matrix multiplication is
1929
01:16:49,840 --> 01:16:51,760
used in simple graphics all the way up
1930
01:16:51,760 --> 01:16:55,040
to hd tvs and we wrote our own python
1931
01:16:55,040 --> 01:16:58,480
program to calculate two matrices
1932
01:16:58,480 --> 01:17:00,800
we looked at strassen's algorithm for
1933
01:17:00,800 --> 01:17:02,480
matrix multiplication
1934
01:17:02,480 --> 01:17:04,000
and learned that he discovered how to
1935
01:17:04,000 --> 01:17:06,480
get the lowest amount of calculations
1936
01:17:06,480 --> 01:17:09,679
possible for multiplying two matrices
1937
01:17:09,679 --> 01:17:12,400
to this day computational efficiency of
1938
01:17:12,400 --> 01:17:15,120
matrix multiplication is still a hot
1939
01:17:15,120 --> 01:17:20,199
topic in theoretical computer science
1940
01:17:21,190 --> 01:17:31,520
[Music]
1941
01:17:31,520 --> 01:17:34,239
apparently if you google greediest
1942
01:17:34,239 --> 01:17:37,920
person a real live person does pop up
1943
01:17:37,920 --> 01:17:40,320
can you imagine like googling the worst
1944
01:17:40,320 --> 01:17:42,800
person in the world and your face gets
1945
01:17:42,800 --> 01:17:44,560
blasted on the screen
1946
01:17:44,560 --> 01:17:46,239
now i'm not going to show who this
1947
01:17:46,239 --> 01:17:48,560
person is because i don't know who he is
1948
01:17:48,560 --> 01:17:50,159
and it's not really important just kind
1949
01:17:50,159 --> 01:17:52,480
of funny but it does tie in with our
1950
01:17:52,480 --> 01:17:53,760
algorithm
1951
01:17:53,760 --> 01:17:56,800
what is greed to you like what is a
1952
01:17:56,800 --> 01:17:58,640
greedy approach
1953
01:17:58,640 --> 01:18:01,360
say your beautiful old granny baked a
1954
01:18:01,360 --> 01:18:03,679
pie for your family and uncle bob shows
1955
01:18:03,679 --> 01:18:06,320
up you know amy's ex-husband
1956
01:18:06,320 --> 01:18:08,320
and he takes the biggest piece of pie
1957
01:18:08,320 --> 01:18:10,480
for himself that'd be pretty greedy
1958
01:18:10,480 --> 01:18:12,880
wouldn't it by him eating the largest
1959
01:18:12,880 --> 01:18:15,040
portion that sure would make the pie
1960
01:18:15,040 --> 01:18:17,040
easier to finish wouldn't it it wouldn't
1961
01:18:17,040 --> 01:18:19,600
be great for everyone else or their
1962
01:18:19,600 --> 01:18:21,840
rumbling tummies but by taking the
1963
01:18:21,840 --> 01:18:24,880
biggest portion and leaving just little
1964
01:18:24,880 --> 01:18:26,719
portions to take care of
1965
01:18:26,719 --> 01:18:27,920
that's
1966
01:18:27,920 --> 01:18:30,560
sort of the concept behind the algorithm
1967
01:18:30,560 --> 01:18:32,880
the paradigm behind the green concept is
1968
01:18:32,880 --> 01:18:35,040
that it builds up a solution piece by
1969
01:18:35,040 --> 01:18:37,600
piece always choosing the next piece
1970
01:18:37,600 --> 01:18:40,159
that offers the mo the obvious and most
1971
01:18:40,159 --> 01:18:41,760
immediate benefit
1972
01:18:41,760 --> 01:18:43,840
by using several iterations and by
1973
01:18:43,840 --> 01:18:46,159
obtaining the best result at a certain
1974
01:18:46,159 --> 01:18:48,719
iteration the results should be computed
1975
01:18:48,719 --> 01:18:50,400
in other words it follows the
1976
01:18:50,400 --> 01:18:52,480
problem-solving method of making the
1977
01:18:52,480 --> 01:18:55,360
locally optimum choice at each stage
1978
01:18:55,360 --> 01:18:57,199
with the hope of finding the global
1979
01:18:57,199 --> 01:18:59,360
optimum something to keep in mind though
1980
01:18:59,360 --> 01:19:01,360
is that they do not consistently find
1981
01:19:01,360 --> 01:19:04,400
the globally optimum solution because
1982
01:19:04,400 --> 01:19:06,480
generally speaking they don't operate
1983
01:19:06,480 --> 01:19:08,880
exhaustively on all the data
1984
01:19:08,880 --> 01:19:11,120
nevertheless they are useful because
1985
01:19:11,120 --> 01:19:13,520
they are quick and often give good
1986
01:19:13,520 --> 01:19:16,400
approximations to the optimum if a
1987
01:19:16,400 --> 01:19:18,640
greedy algorithm can be proven to yield
1988
01:19:18,640 --> 01:19:20,960
the global optimum for a given problem
1989
01:19:20,960 --> 01:19:23,920
class it typically becomes the method of
1990
01:19:23,920 --> 01:19:26,320
choice
1991
01:19:30,800 --> 01:19:33,120
a really fun problem that we can lead
1992
01:19:33,120 --> 01:19:36,239
off with is called assign mice to holes
1993
01:19:36,239 --> 01:19:38,640
what we need to do is put every mouse to
1994
01:19:38,640 --> 01:19:41,360
its nearest hole to minimize the time
1995
01:19:41,360 --> 01:19:43,600
how can we do that and what's the
1996
01:19:43,600 --> 01:19:45,679
optimal approach
1997
01:19:45,679 --> 01:19:47,600
what would you think about sorting the
1998
01:19:47,600 --> 01:19:50,480
positions of the mice and holes first
1999
01:19:50,480 --> 01:19:52,560
that would be pretty greedy of us
2000
01:19:52,560 --> 01:19:53,920
wouldn't it
2001
01:19:53,920 --> 01:19:56,320
this allows us to put a particular mouse
2002
01:19:56,320 --> 01:19:58,640
closest to the corresponding hole in the
2003
01:19:58,640 --> 01:20:01,600
holes list we can then find the maximum
2004
01:20:01,600 --> 01:20:03,679
difference between the mice and the
2005
01:20:03,679 --> 01:20:06,159
corresponding hole position to determine
2006
01:20:06,159 --> 01:20:09,120
how much time it will take to get there
2007
01:20:09,120 --> 01:20:12,080
now does being greedy always equate to
2008
01:20:12,080 --> 01:20:14,080
maximum of something regarding problem
2009
01:20:14,080 --> 01:20:17,120
solutions not necessarily don't let that
2010
01:20:17,120 --> 01:20:18,639
word fool you
2011
01:20:18,639 --> 01:20:20,560
for this problem we're finding the
2012
01:20:20,560 --> 01:20:23,679
maximum difference hint subtraction to
2013
01:20:23,679 --> 01:20:25,679
find the minimum amount of time it takes
2014
01:20:25,679 --> 01:20:27,679
for our mice to travel
2015
01:20:27,679 --> 01:20:29,760
as a quick side note another problem
2016
01:20:29,760 --> 01:20:31,280
that i would encourage you to learn on
2017
01:20:31,280 --> 01:20:33,920
your own a triple dog dare you is the
2018
01:20:33,920 --> 01:20:36,400
kids with greatest candies problem using
2019
01:20:36,400 --> 01:20:38,000
the greedy approach
2020
01:20:38,000 --> 01:20:40,159
this is considered an easy problem so
2021
01:20:40,159 --> 01:20:42,400
don't worry too much the problem is
2022
01:20:42,400 --> 01:20:44,320
similar to this one by asking for the
2023
01:20:44,320 --> 01:20:46,320
distribution of the minimum number of
2024
01:20:46,320 --> 01:20:49,199
candies that can be given to a kid
2025
01:20:49,199 --> 01:20:51,760
and then seeing which kid will contain
2026
01:20:51,760 --> 01:20:54,080
the maximum number of candies
2027
01:20:54,080 --> 01:20:57,040
so again the greedy approach can be
2028
01:20:57,040 --> 01:20:59,520
tricky we have to carefully decipher
2029
01:20:59,520 --> 01:21:01,840
word usages to make sure we're solving
2030
01:21:01,840 --> 01:21:03,679
the problem accurately
2031
01:21:03,679 --> 01:21:05,679
but with that being said the assigned
2032
01:21:05,679 --> 01:21:07,920
mice to holes problem will help set you
2033
01:21:07,920 --> 01:21:10,239
on some solid ground and make it a bit
2034
01:21:10,239 --> 01:21:13,199
easier to work on other challenges now
2035
01:21:13,199 --> 01:21:15,120
if you do decide to tackle the candy
2036
01:21:15,120 --> 01:21:17,280
problem and i do highly encourage you to
2037
01:21:17,280 --> 01:21:19,600
do that i'll give you a little hint
2038
01:21:19,600 --> 01:21:22,000
the brute force method would be a one by
2039
01:21:22,000 --> 01:21:24,320
one distribution of candies to each
2040
01:21:24,320 --> 01:21:27,280
child until the condition satisfies
2041
01:21:27,280 --> 01:21:29,280
and yet the greedy way would be to
2042
01:21:29,280 --> 01:21:31,760
traverse the array just twice from
2043
01:21:31,760 --> 01:21:34,159
beginning to end and back again by
2044
01:21:34,159 --> 01:21:36,159
greedily determining the minimum number
2045
01:21:36,159 --> 01:21:38,960
of candies required by each child
2046
01:21:38,960 --> 01:21:41,600
as a personal challenge to yourself work
2047
01:21:41,600 --> 01:21:43,760
out how that could be written it'll be
2048
01:21:43,760 --> 01:21:48,000
fun let's head over to our ides and slam
2049
01:21:48,000 --> 01:21:51,840
dunk some mice into holes
2050
01:21:51,840 --> 01:21:54,400
okay we need to get our mice into holes
2051
01:21:54,400 --> 01:21:56,480
and we have to do it quickly but first
2052
01:21:56,480 --> 01:21:58,800
things first we have to make sure that
2053
01:21:58,800 --> 01:22:00,960
there are an equal amount of holes to
2054
01:22:00,960 --> 01:22:03,840
our mice this is our base
2055
01:22:03,840 --> 01:22:04,719
now
2056
01:22:04,719 --> 01:22:06,800
we initialize our greedy approach by
2057
01:22:06,800 --> 01:22:09,280
sorting the mice first then we create a
2058
01:22:09,280 --> 01:22:12,880
variable to store our maximum difference
2059
01:22:12,880 --> 01:22:16,800
and loop through the length of our mice
2060
01:22:16,800 --> 01:22:18,960
in our if statement we create the
2061
01:22:18,960 --> 01:22:20,880
condition that if the position of the
2062
01:22:20,880 --> 01:22:23,199
mouse subtracted from the position of
2063
01:22:23,199 --> 01:22:25,760
the hole is greater than the maximum
2064
01:22:25,760 --> 01:22:26,719
difference
2065
01:22:26,719 --> 01:22:29,760
our max diff variable gets reassigned to
2066
01:22:29,760 --> 01:22:31,679
hold that difference
2067
01:22:31,679 --> 01:22:33,840
lastly we just return the largest
2068
01:22:33,840 --> 01:22:36,320
difference our last mouse gets to the
2069
01:22:36,320 --> 01:22:40,159
hole in x amount of time
2070
01:22:44,880 --> 01:22:48,159
by sorting our two lists first this puts
2071
01:22:48,159 --> 01:22:50,159
us at an advantage to finding the
2072
01:22:50,159 --> 01:22:52,560
minimum time faster
2073
01:22:52,560 --> 01:22:55,679
our code is concise short and along with
2074
01:22:55,679 --> 01:22:58,480
python's sort feature we are really
2075
01:22:58,480 --> 01:23:00,080
rocking it out
2076
01:23:00,080 --> 01:23:02,400
next up is kind of a doozy the
2077
01:23:02,400 --> 01:23:05,120
fractional knapsack a pretty well known
2078
01:23:05,120 --> 01:23:07,760
problem for our greedy algorithm
2079
01:23:07,760 --> 01:23:09,760
if you were a little bored with our mice
2080
01:23:09,760 --> 01:23:12,159
and no holes you won't be with the
2081
01:23:12,159 --> 01:23:14,880
knapsack
2082
01:23:18,880 --> 01:23:21,360
for a step up on the greedy method let's
2083
01:23:21,360 --> 01:23:23,440
take a peek into what's called the
2084
01:23:23,440 --> 01:23:27,280
fractional knapsack now this is intense
2085
01:23:27,280 --> 01:23:30,719
fractional knapsack freshness people
2086
01:23:30,719 --> 01:23:32,960
okay so this problem on the surface
2087
01:23:32,960 --> 01:23:34,800
seems really complicated but it's only
2088
01:23:34,800 --> 01:23:37,280
as complicated as you want to make it
2089
01:23:37,280 --> 01:23:39,600
you know what i mean so let's not make
2090
01:23:39,600 --> 01:23:42,480
it complicated okay so just so what you
2091
01:23:42,480 --> 01:23:44,639
can do is just envision me it's the
2092
01:23:44,639 --> 01:23:47,360
apocalypse it's the end of the world
2093
01:23:47,360 --> 01:23:49,760
wait maybe it's just a monday food is
2094
01:23:49,760 --> 01:23:52,000
scarce people are bartering water is
2095
01:23:52,000 --> 01:23:54,320
practically non-existent so i need to
2096
01:23:54,320 --> 01:23:56,560
conserve every bit of energy i have to
2097
01:23:56,560 --> 01:23:58,719
walk to the market and try to trade what
2098
01:23:58,719 --> 01:24:01,120
i have to stay alive okay now i have
2099
01:24:01,120 --> 01:24:04,400
five objects i can take our knapsack or
2100
01:24:04,400 --> 01:24:06,800
bag is our container for holding our
2101
01:24:06,800 --> 01:24:09,600
objects think of our array as a storage
2102
01:24:09,600 --> 01:24:10,719
device
2103
01:24:10,719 --> 01:24:13,600
and each object is worth something some
2104
01:24:13,600 --> 01:24:15,920
are worth more than others and each
2105
01:24:15,920 --> 01:24:19,600
object weighs something some objects way
2106
01:24:19,600 --> 01:24:22,080
more than others the key to this problem
2107
01:24:22,080 --> 01:24:24,480
is to make the right decision on which
2108
01:24:24,480 --> 01:24:26,880
objects are going to bring me the most
2109
01:24:26,880 --> 01:24:29,280
profit i mean i gotta know i have
2110
01:24:29,280 --> 01:24:31,120
animals to feed
2111
01:24:31,120 --> 01:24:32,800
that haven't become somebody else's
2112
01:24:32,800 --> 01:24:35,679
dinner you know while at the same time
2113
01:24:35,679 --> 01:24:37,840
they can't be too heavy that i can't
2114
01:24:37,840 --> 01:24:40,080
carry in my container because this is
2115
01:24:40,080 --> 01:24:42,719
crucial i might have to make a decision
2116
01:24:42,719 --> 01:24:45,679
based on its object the weight of the
2117
01:24:45,679 --> 01:24:48,639
object not necessarily its profit if i
2118
01:24:48,639 --> 01:24:50,560
want to make it back alive from zombies
2119
01:24:50,560 --> 01:24:51,600
r us
2120
01:24:51,600 --> 01:24:54,159
now the real kick in the head on solving
2121
01:24:54,159 --> 01:24:55,120
this
2122
01:24:55,120 --> 01:24:57,760
lies in that little teeny tiny word
2123
01:24:57,760 --> 01:25:00,320
fractional this means that my objects
2124
01:25:00,320 --> 01:25:03,440
can be divided if they are divisible
2125
01:25:03,440 --> 01:25:05,679
say one of my objects contains three
2126
01:25:05,679 --> 01:25:08,159
chapsticks i can divide that object and
2127
01:25:08,159 --> 01:25:10,400
bring only two chapsticks if it will
2128
01:25:10,400 --> 01:25:13,040
make a difference who knows cat fat
2129
01:25:13,040 --> 01:25:15,040
might be a real hot commodity remember
2130
01:25:15,040 --> 01:25:16,960
in that book of eli movie where he
2131
01:25:16,960 --> 01:25:18,639
killed that cat
2132
01:25:18,639 --> 01:25:20,800
well it was for food but he also made
2133
01:25:20,800 --> 01:25:22,480
chapstick out of it
2134
01:25:22,480 --> 01:25:25,199
not saying my chapstick would be that
2135
01:25:25,199 --> 01:25:28,080
it'd probably be made from beeswax or
2136
01:25:28,080 --> 01:25:29,120
something
2137
01:25:29,120 --> 01:25:31,600
don't forget i'm risking my brains to go
2138
01:25:31,600 --> 01:25:33,600
to the market to feed my animals in the
2139
01:25:33,600 --> 01:25:36,480
first place so no cancel be harmed here
2140
01:25:36,480 --> 01:25:39,600
no siree bob okay wow that was a really
2141
01:25:39,600 --> 01:25:40,400
long
2142
01:25:40,400 --> 01:25:42,719
way off the beaten path if let's get
2143
01:25:42,719 --> 01:25:44,719
back to the problem so the weight is
2144
01:25:44,719 --> 01:25:47,679
divisible and it would help to best fit
2145
01:25:47,679 --> 01:25:49,520
how many profitable objects in my
2146
01:25:49,520 --> 01:25:52,400
backpack then we should do that why we
2147
01:25:52,400 --> 01:25:54,880
need to fill to the brim in our fixed
2148
01:25:54,880 --> 01:25:57,760
size knapsack the most valuable items
2149
01:25:57,760 --> 01:25:59,840
that we are able to carry
2150
01:25:59,840 --> 01:26:01,760
for the steps of our algorithm keep in
2151
01:26:01,760 --> 01:26:04,000
mind we are given weights and values of
2152
01:26:04,000 --> 01:26:06,639
n items and we need to put these items
2153
01:26:06,639 --> 01:26:10,719
in a knapsack of capacity w to get the
2154
01:26:10,719 --> 01:26:13,600
maximum total value in the knapsack by
2155
01:26:13,600 --> 01:26:16,560
the way in the o1 knapsack problem a
2156
01:26:16,560 --> 01:26:18,400
whole different problem is one where
2157
01:26:18,400 --> 01:26:20,719
we're not allowed to break items down or
2158
01:26:20,719 --> 01:26:22,639
divide them using fractions
2159
01:26:22,639 --> 01:26:24,960
we either take the whole item or don't
2160
01:26:24,960 --> 01:26:27,440
take it but in this problem fractions
2161
01:26:27,440 --> 01:26:28,880
can be used
2162
01:26:28,880 --> 01:26:30,800
a really efficient solution to this
2163
01:26:30,800 --> 01:26:33,840
problem is to use the greedy approach as
2164
01:26:33,840 --> 01:26:36,719
opposed to brute force remember brute
2165
01:26:36,719 --> 01:26:39,199
force is calculating every possible
2166
01:26:39,199 --> 01:26:40,800
solution and is typically
2167
01:26:40,800 --> 01:26:43,440
computationally expensive meaning it
2168
01:26:43,440 --> 01:26:46,560
takes a lot of runtime and memory space
2169
01:26:46,560 --> 01:26:49,920
the basic idea is to calculate the ratio
2170
01:26:49,920 --> 01:26:52,480
of value slash weight for each item and
2171
01:26:52,480 --> 01:26:55,600
sort the item on the basis of this ratio
2172
01:26:55,600 --> 01:26:57,440
then take the item with the highest
2173
01:26:57,440 --> 01:27:00,719
ratio greedy remember and add them until
2174
01:27:00,719 --> 01:27:03,280
we can't add the next item as a whole
2175
01:27:03,280 --> 01:27:05,520
and at the end add the next item as much
2176
01:27:05,520 --> 01:27:06,719
as we can
2177
01:27:06,719 --> 01:27:08,960
this will generally always be the
2178
01:27:08,960 --> 01:27:11,679
optimal solution to this problem
2179
01:27:11,679 --> 01:27:13,760
you'll see what i mean when we get into
2180
01:27:13,760 --> 01:27:16,159
our ides and start coding it so let's
2181
01:27:16,159 --> 01:27:19,400
get to work
2182
01:27:19,920 --> 01:27:20,880
okay
2183
01:27:20,880 --> 01:27:23,040
we'll define our functions with three
2184
01:27:23,040 --> 01:27:24,239
parameters
2185
01:27:24,239 --> 01:27:26,960
we need our values our weights and the
2186
01:27:26,960 --> 01:27:29,280
capacity of the bag
2187
01:27:29,280 --> 01:27:32,320
now we have our created variables here
2188
01:27:32,320 --> 01:27:34,719
but i implemented print calls to show
2189
01:27:34,719 --> 01:27:36,400
you what's going on
2190
01:27:36,400 --> 01:27:39,199
we have our items a range of zero to
2191
01:27:39,199 --> 01:27:41,920
four equaling five items
2192
01:27:41,920 --> 01:27:44,960
the ratios are values divided by weight
2193
01:27:44,960 --> 01:27:48,080
using floor division to eliminate floats
2194
01:27:48,080 --> 01:27:50,080
list comprehension is good to use when
2195
01:27:50,080 --> 01:27:51,440
you can
2196
01:27:51,440 --> 01:27:54,560
then we'll sort our ratios in decreasing
2197
01:27:54,560 --> 01:27:55,760
order
2198
01:27:55,760 --> 01:27:58,800
lastly the ratios index positions are
2199
01:27:58,800 --> 01:28:01,600
printed here to show the to show you the
2200
01:28:01,600 --> 01:28:05,120
order that it will be computed in
2201
01:28:05,120 --> 01:28:06,639
i'm going to
2202
01:28:06,639 --> 01:28:09,520
take out the third variable here it as
2203
01:28:09,520 --> 01:28:11,600
it won't be needed
2204
01:28:11,600 --> 01:28:14,080
i just wanted to show you how it matches
2205
01:28:14,080 --> 01:28:16,239
up with its index position
2206
01:28:16,239 --> 01:28:19,360
our ratios being sorted is taken care of
2207
01:28:19,360 --> 01:28:22,880
in the items.sort line
2208
01:28:22,880 --> 01:28:25,040
we need a counter to keep a running
2209
01:28:25,040 --> 01:28:27,679
tally of our max value
2210
01:28:27,679 --> 01:28:29,840
we will create a list that is the length
2211
01:28:29,840 --> 01:28:32,000
of our values we'll call fractions that
2212
01:28:32,000 --> 01:28:34,080
will contain all zeros
2213
01:28:34,080 --> 01:28:36,560
i'll tell you why we're doing this at
2214
01:28:36,560 --> 01:28:39,360
the end of the program now it's time to
2215
01:28:39,360 --> 01:28:42,159
run our for loop we'll iterate over our
2216
01:28:42,159 --> 01:28:44,639
items and if the weight of our item is
2217
01:28:44,639 --> 01:28:47,440
less than capacity it will add a one to
2218
01:28:47,440 --> 01:28:50,320
our fractions list of zeros at its index
2219
01:28:50,320 --> 01:28:52,800
position then we'll add that value to
2220
01:28:52,800 --> 01:28:55,440
our max value and subtract the weight
2221
01:28:55,440 --> 01:28:57,840
from our capacity now when all those
2222
01:28:57,840 --> 01:29:01,120
conditions satisfy and we hit our else
2223
01:29:01,120 --> 01:29:03,199
we take the fractional difference of our
2224
01:29:03,199 --> 01:29:06,480
last item and add it to our max value
2225
01:29:06,480 --> 01:29:09,520
then we return our maximum value which
2226
01:29:09,520 --> 01:29:13,120
is 500 now here's the key you might be
2227
01:29:13,120 --> 01:29:14,560
wondering this
2228
01:29:14,560 --> 01:29:17,280
we have an item that weighs
2229
01:29:17,280 --> 01:29:20,080
a 10 and it's worth 90.
2230
01:29:20,080 --> 01:29:24,400
at a capacity of 150 we could put 15
2231
01:29:24,400 --> 01:29:27,040
of these items into our bag for a value
2232
01:29:27,040 --> 01:29:31,120
of 15 times 90 equaling 1350.
2233
01:29:31,120 --> 01:29:33,600
why can't we just do that
2234
01:29:33,600 --> 01:29:36,080
we can't do that because what we're
2235
01:29:36,080 --> 01:29:38,000
looking at today is what is called the
2236
01:29:38,000 --> 01:29:41,440
bounded knapsack problem or bkp for
2237
01:29:41,440 --> 01:29:42,320
short
2238
01:29:42,320 --> 01:29:45,199
the scenario i just painted a 15
2239
01:29:45,199 --> 01:29:47,600
15 of the same items would be allowing
2240
01:29:47,600 --> 01:29:50,400
for copies of that item called the
2241
01:29:50,400 --> 01:29:53,920
called the ukp type short for unbounded
2242
01:29:53,920 --> 01:29:56,880
knapsack problem and that's a whole
2243
01:29:56,880 --> 01:29:59,360
other ball of wax kids
2244
01:29:59,360 --> 01:30:02,480
this is why we set up the fractions list
2245
01:30:02,480 --> 01:30:04,639
containing nothing but zeros
2246
01:30:04,639 --> 01:30:06,960
this is important because it's putting
2247
01:30:06,960 --> 01:30:09,920
in our highest values first
2248
01:30:09,920 --> 01:30:12,239
and then taking a fraction of the last
2249
01:30:12,239 --> 01:30:15,520
item from maximum capacity in our bag
2250
01:30:15,520 --> 01:30:18,080
each item counts as one in our fractions
2251
01:30:18,080 --> 01:30:21,120
list until every zero is turned into a
2252
01:30:21,120 --> 01:30:23,520
one but our very last item to change
2253
01:30:23,520 --> 01:30:26,480
from zero to one is that special one
2254
01:30:26,480 --> 01:30:28,960
that gets the remaining capacity divided
2255
01:30:28,960 --> 01:30:30,480
by the weight
2256
01:30:30,480 --> 01:30:33,120
that figure gets multiplied to our value
2257
01:30:33,120 --> 01:30:35,600
and then added to our max value in the
2258
01:30:35,600 --> 01:30:38,080
case of our program that ends up being
2259
01:30:38,080 --> 01:30:41,120
28 and a half percent and what's 28 and
2260
01:30:41,120 --> 01:30:43,440
a half percent of 140
2261
01:30:43,440 --> 01:30:46,639
is the value of 40 that puts us up to
2262
01:30:46,639 --> 01:30:49,679
500. sorting our ratios in decreasing
2263
01:30:49,679 --> 01:30:52,000
order gives us the optimal or best
2264
01:30:52,000 --> 01:30:54,960
approach this is considered greedy as
2265
01:30:54,960 --> 01:30:57,199
you are placing items with the largest
2266
01:30:57,199 --> 01:31:00,159
ratios into our bag first
2267
01:31:00,159 --> 01:31:03,440
now you can sort by price and you can
2268
01:31:03,440 --> 01:31:06,080
sort by weight as those are considered
2269
01:31:06,080 --> 01:31:08,800
methods and they will get you close to
2270
01:31:08,800 --> 01:31:10,080
500
2271
01:31:10,080 --> 01:31:12,480
but it's just not 500. and we should
2272
01:31:12,480 --> 01:31:14,960
always strive for the best method
2273
01:31:14,960 --> 01:31:17,760
algorithmically
2274
01:31:17,760 --> 01:31:19,920
hopefully you now understand a pretty
2275
01:31:19,920 --> 01:31:22,560
well-known problem not only in logistics
2276
01:31:22,560 --> 01:31:24,400
but other fields as well like
2277
01:31:24,400 --> 01:31:27,600
manufacturing and finance it's all about
2278
01:31:27,600 --> 01:31:29,120
optimization
2279
01:31:29,120 --> 01:31:31,840
what is the optimal way to get the items
2280
01:31:31,840 --> 01:31:34,800
of highest value into a bag that you can
2281
01:31:34,800 --> 01:31:36,560
reasonably carry
2282
01:31:36,560 --> 01:31:39,280
and this greedy concept can be carried
2283
01:31:39,280 --> 01:31:41,440
out in other reasonable scenarios as
2284
01:31:41,440 --> 01:31:42,320
well
2285
01:31:42,320 --> 01:31:44,480
with the goal of calculating solutions
2286
01:31:44,480 --> 01:31:47,600
whether that be approximations or actual
2287
01:31:47,600 --> 01:31:48,800
figures
2288
01:31:48,800 --> 01:31:52,159
let's move on to our last section with
2289
01:31:52,159 --> 01:31:55,719
good old fibonacci
2290
01:31:58,960 --> 01:32:01,760
in our mind breaker episode we're going
2291
01:32:01,760 --> 01:32:03,360
to talk about another well-known
2292
01:32:03,360 --> 01:32:07,120
mathematician leonardo alpisa aka
2293
01:32:07,120 --> 01:32:09,760
fibonacci considered to be the most
2294
01:32:09,760 --> 01:32:11,920
talented western mathematician of the
2295
01:32:11,920 --> 01:32:13,360
middle ages
2296
01:32:13,360 --> 01:32:15,360
according to wikipedia he wrote the
2297
01:32:15,360 --> 01:32:18,080
libre abachi the book of calculation and
2298
01:32:18,080 --> 01:32:20,800
is it is a historic 13th century latin
2299
01:32:20,800 --> 01:32:23,199
manuscript on arithmetic which includes
2300
01:32:23,199 --> 01:32:25,440
the posing and solving of a problem
2301
01:32:25,440 --> 01:32:27,120
involving the population growth of
2302
01:32:27,120 --> 01:32:30,239
rabbits based on idealized assumptions
2303
01:32:30,239 --> 01:32:31,520
the solution
2304
01:32:31,520 --> 01:32:33,840
generate generation by generation of
2305
01:32:33,840 --> 01:32:36,400
rabbit offspring was a sequence of
2306
01:32:36,400 --> 01:32:38,400
numbers later known as the famous
2307
01:32:38,400 --> 01:32:41,760
fibonacci numbers or fibonacci sequence
2308
01:32:41,760 --> 01:32:43,440
in a little side compartment of
2309
01:32:43,440 --> 01:32:45,920
mathematics however what we are going to
2310
01:32:45,920 --> 01:32:48,239
talk about today is the greedy algorithm
2311
01:32:48,239 --> 01:32:51,040
for egyptian fractions first described
2312
01:32:51,040 --> 01:32:54,159
by fibonacci for transforming rational
2313
01:32:54,159 --> 01:32:56,719
numbers into egyptian fractions
2314
01:32:56,719 --> 01:32:59,199
an egyptian fraction is a representation
2315
01:32:59,199 --> 01:33:02,000
of an irreducible fraction as a sum of
2316
01:33:02,000 --> 01:33:04,880
distinct unit fractions and this means
2317
01:33:04,880 --> 01:33:07,440
that every positive fraction can be
2318
01:33:07,440 --> 01:33:10,239
represented as a sum of unique unit
2319
01:33:10,239 --> 01:33:12,800
fractions a fraction is a unit fraction
2320
01:33:12,800 --> 01:33:14,480
if the numerator is 1 and the
2321
01:33:14,480 --> 01:33:16,800
denominator is a positive integer for
2322
01:33:16,800 --> 01:33:18,719
example 1 3
2323
01:33:18,719 --> 01:33:21,760
is a unit fraction to take a closer look
2324
01:33:21,760 --> 01:33:24,880
we'll reduce a fraction of 7 14 in a
2325
01:33:24,880 --> 01:33:29,880
pizza example the egyptian way
2326
01:33:30,550 --> 01:33:33,739
[Applause]
2327
01:33:35,780 --> 01:33:35,940
[Applause]
2328
01:33:35,940 --> 01:33:40,880
[Music]
2329
01:33:40,880 --> 01:33:42,800
in order to generate egyptian fractions
2330
01:33:42,800 --> 01:33:44,719
we will utilize the greedy algorithm
2331
01:33:44,719 --> 01:33:46,719
because although possible to use brute
2332
01:33:46,719 --> 01:33:49,040
force search algorithms to find it it
2333
01:33:49,040 --> 01:33:51,440
would be extremely inefficient
2334
01:33:51,440 --> 01:33:53,360
remember 3d algorithms are for
2335
01:33:53,360 --> 01:33:56,080
optimizing our problems we always want
2336
01:33:56,080 --> 01:33:58,000
to know and understand the optimal
2337
01:33:58,000 --> 01:34:00,400
solution as a side note although
2338
01:34:00,400 --> 01:34:02,480
fibonacci's greedy algorithm isn't the
2339
01:34:02,480 --> 01:34:04,159
only way to efficiently solve our
2340
01:34:04,159 --> 01:34:07,360
problem he's our focus for today
2341
01:34:07,360 --> 01:34:10,560
let's look at a program
2342
01:34:10,560 --> 01:34:13,679
so yeah i got this program here
2343
01:34:13,679 --> 01:34:16,800
we're importing some tools
2344
01:34:16,800 --> 01:34:18,960
scroll down some
2345
01:34:18,960 --> 01:34:21,679
we got three functions going strong a
2346
01:34:21,679 --> 01:34:25,440
main a validate a converting function we
2347
01:34:25,440 --> 01:34:28,400
got some wrappers nestled functions we
2348
01:34:28,400 --> 01:34:30,840
got some yields which means it's a
2349
01:34:30,840 --> 01:34:34,239
generator not even gonna touch that
2350
01:34:34,239 --> 01:34:36,880
this is a lot of code
2351
01:34:36,880 --> 01:34:39,840
heading into nearly 50 lines
2352
01:34:39,840 --> 01:34:40,960
is it good
2353
01:34:40,960 --> 01:34:41,760
yes
2354
01:34:41,760 --> 01:34:43,440
hard to write
2355
01:34:43,440 --> 01:34:45,520
depends but if you're looking for
2356
01:34:45,520 --> 01:34:47,920
kindergarten style programming you come
2357
01:34:47,920 --> 01:34:49,520
to the right place
2358
01:34:49,520 --> 01:34:52,080
i totally dumbed it down to show you the
2359
01:34:52,080 --> 01:34:55,360
mechanics not that you're dumb i love
2360
01:34:55,360 --> 01:34:58,800
simple make it plain am i right
2361
01:34:58,800 --> 01:35:01,840
so we have this pie remember that bob
2362
01:35:01,840 --> 01:35:04,400
took a big old chunk of let's change
2363
01:35:04,400 --> 01:35:07,199
that to a pizza since it kind of goes
2364
01:35:07,199 --> 01:35:10,560
with our theme of leonardo of pizza
2365
01:35:10,560 --> 01:35:12,560
or fibonacci
2366
01:35:12,560 --> 01:35:15,520
so to get this real simple we'll write a
2367
01:35:15,520 --> 01:35:17,679
function that takes our numerator and
2368
01:35:17,679 --> 01:35:20,000
our denominator
2369
01:35:20,000 --> 01:35:22,239
we'll implement an empty list for our
2370
01:35:22,239 --> 01:35:25,199
denominators we won't need one for our
2371
01:35:25,199 --> 01:35:27,360
numerators because we already know that
2372
01:35:27,360 --> 01:35:29,440
they're going to be ones
2373
01:35:29,440 --> 01:35:31,840
then we write our while loop that as
2374
01:35:31,840 --> 01:35:34,560
long as our numerator isn't zero we can
2375
01:35:34,560 --> 01:35:36,560
create a variable that stores our
2376
01:35:36,560 --> 01:35:39,440
quotient using the math dot seal that
2377
01:35:39,440 --> 01:35:41,280
will round it up
2378
01:35:41,280 --> 01:35:43,440
this is important for when we have a
2379
01:35:43,440 --> 01:35:47,520
number that's a float lower than one
2380
01:35:47,520 --> 01:35:50,080
next we reassign our numerator to be the
2381
01:35:50,080 --> 01:35:51,760
product of the quotient and the
2382
01:35:51,760 --> 01:35:54,159
difference of our denominator subtracted
2383
01:35:54,159 --> 01:35:57,360
from our numerator then we reassign our
2384
01:35:57,360 --> 01:35:59,520
denominator to be multiplied by our
2385
01:35:59,520 --> 01:36:02,000
quotient or x
2386
01:36:02,000 --> 01:36:05,280
for our fraction of 7 12 this is going
2387
01:36:05,280 --> 01:36:09,360
to put a 2 and a 12 into our egypt list
2388
01:36:09,360 --> 01:36:11,440
and those two numbers are our lowest
2389
01:36:11,440 --> 01:36:15,440
common denominators or lcd for short
2390
01:36:15,440 --> 01:36:18,639
all that's left to do now is put a 1
2391
01:36:18,639 --> 01:36:21,199
over those lcds as those are our
2392
01:36:21,199 --> 01:36:23,600
egyptian fractions and that can be
2393
01:36:23,600 --> 01:36:26,719
accomplished a few ways but basically i
2394
01:36:26,719 --> 01:36:28,880
just implemented some good old-fashioned
2395
01:36:28,880 --> 01:36:31,520
string formatting by iterating over our
2396
01:36:31,520 --> 01:36:34,080
egypt list of denominators and adding
2397
01:36:34,080 --> 01:36:36,800
them to an empty string
2398
01:36:36,800 --> 01:36:39,440
once we do that we just return it the
2399
01:36:39,440 --> 01:36:41,679
caveat to this really simple program is
2400
01:36:41,679 --> 01:36:44,000
that it probably doesn't work for really
2401
01:36:44,000 --> 01:36:46,880
complex fractions or when the numerator
2402
01:36:46,880 --> 01:36:49,679
is larger than the denominator
2403
01:36:49,679 --> 01:36:52,639
but this is a good exercise in
2404
01:36:52,639 --> 01:36:54,159
understanding how to break down a
2405
01:36:54,159 --> 01:36:57,360
fraction the egyptian way ultimately all
2406
01:36:57,360 --> 01:36:59,360
of this runs more along the line of
2407
01:36:59,360 --> 01:37:01,280
recreational mathematics however there
2408
01:37:01,280 --> 01:37:03,199
are still open problems involving
2409
01:37:03,199 --> 01:37:05,040
egyptian fractions that have yet to be
2410
01:37:05,040 --> 01:37:06,560
solved or proved
2411
01:37:06,560 --> 01:37:08,800
who knows maybe you can be the next
2412
01:37:08,800 --> 01:37:13,119
mathematical genius to solve one of them
2413
01:37:13,600 --> 01:37:15,520
so what did we learn about greedy
2414
01:37:15,520 --> 01:37:18,239
algorithms we learned optimization of
2415
01:37:18,239 --> 01:37:20,239
solutions to problems using the greedy
2416
01:37:20,239 --> 01:37:22,560
algorithm provided in our example with
2417
01:37:22,560 --> 01:37:24,639
the mice in the holes it's like a
2418
01:37:24,639 --> 01:37:26,880
delicious big pie where you take the
2419
01:37:26,880 --> 01:37:28,880
biggest slice out first
2420
01:37:28,880 --> 01:37:31,679
this makes the pie easier to finish we
2421
01:37:31,679 --> 01:37:34,000
learned that chapstick made from cats is
2422
01:37:34,000 --> 01:37:36,400
a hot commodity in the apocalypse
2423
01:37:36,400 --> 01:37:37,679
kidding
2424
01:37:37,679 --> 01:37:40,320
we walk through the fractional nap stack
2425
01:37:40,320 --> 01:37:42,159
problem where we find the largest value
2426
01:37:42,159 --> 01:37:44,800
of an item in a way to maximize the
2427
01:37:44,800 --> 01:37:47,520
total value within the knapsack we want
2428
01:37:47,520 --> 01:37:49,119
to avoid brute force here because
2429
01:37:49,119 --> 01:37:51,280
finding all the possible subsets would
2430
01:37:51,280 --> 01:37:53,760
take too much time we learned that
2431
01:37:53,760 --> 01:37:55,840
fibonacci was the first to describe an
2432
01:37:55,840 --> 01:37:57,840
algorithm for transforming rational
2433
01:37:57,840 --> 01:38:00,320
numbers into egyptian fractions and it
2434
01:38:00,320 --> 01:38:03,280
is where we really take the largest unit
2435
01:38:03,280 --> 01:38:06,080
fraction we can and then and then repeat
2436
01:38:06,080 --> 01:38:08,080
that on the remainder although this is
2437
01:38:08,080 --> 01:38:10,320
purely mathematics it's still a good
2438
01:38:10,320 --> 01:38:15,239
representation of the greedy algorithm
2439
01:38:15,740 --> 01:38:20,040
[Music]
2440
01:38:22,180 --> 01:38:26,629
[Music]
2441
01:38:26,719 --> 01:38:29,199
what do you think when you hear the word
2442
01:38:29,199 --> 01:38:30,719
dynamic
2443
01:38:30,719 --> 01:38:32,639
well if you're a programmer or an
2444
01:38:32,639 --> 01:38:34,560
aspiring programmer
2445
01:38:34,560 --> 01:38:37,119
you may not know what to think
2446
01:38:37,119 --> 01:38:40,960
what does being dynamic really mean
2447
01:38:40,960 --> 01:38:43,760
for once in my life it would be awesome
2448
01:38:43,760 --> 01:38:46,320
to be described as dynamic because when
2449
01:38:46,320 --> 01:38:49,679
we talk about a dynamic person
2450
01:38:49,679 --> 01:38:52,080
it means energetic
2451
01:38:52,080 --> 01:38:53,520
spirited
2452
01:38:53,520 --> 01:38:54,719
active
2453
01:38:54,719 --> 01:38:56,840
lively
2454
01:38:56,840 --> 01:38:59,600
zestful vital
2455
01:38:59,600 --> 01:39:01,360
vigorous
2456
01:39:01,360 --> 01:39:03,520
maybe this is why when it comes to
2457
01:39:03,520 --> 01:39:06,000
computer science students can become
2458
01:39:06,000 --> 01:39:08,480
intimidated with the subject of dynamic
2459
01:39:08,480 --> 01:39:09,760
programming
2460
01:39:09,760 --> 01:39:12,719
ultimately the word dynamic means a
2461
01:39:12,719 --> 01:39:15,920
process or system characterized by
2462
01:39:15,920 --> 01:39:19,360
constant change activity or progress
2463
01:39:19,360 --> 01:39:21,760
with its roots in greek to the word
2464
01:39:21,760 --> 01:39:25,119
dynamous meaning power
2465
01:39:25,119 --> 01:39:27,760
hint dynamite
2466
01:39:27,760 --> 01:39:30,800
so it's no wonder we subconsciously shy
2467
01:39:30,800 --> 01:39:33,360
away from it because it just sounds like
2468
01:39:33,360 --> 01:39:36,960
a handful it dangerous pretty wild how
2469
01:39:36,960 --> 01:39:39,679
words and their meanings really deep
2470
01:39:39,679 --> 01:39:42,000
down can make us feel a certain way you
2471
01:39:42,000 --> 01:39:42,880
know
2472
01:39:42,880 --> 01:39:46,320
but i'm here to help you out and put you
2473
01:39:46,320 --> 01:39:49,280
at ease and tell you a little secret
2474
01:39:49,280 --> 01:39:51,760
they introduce dynamic programming to
2475
01:39:51,760 --> 01:39:53,199
children
2476
01:39:53,199 --> 01:39:56,320
okay maybe not children children but
2477
01:39:56,320 --> 01:40:00,480
like upper elementary middle schoolers
2478
01:40:00,480 --> 01:40:03,119
kids like that so if they can learn
2479
01:40:03,119 --> 01:40:05,199
about it so can you
2480
01:40:05,199 --> 01:40:07,520
but first we have to unplug our
2481
01:40:07,520 --> 01:40:10,400
preconditioned mentality if you will to
2482
01:40:10,400 --> 01:40:11,840
think and believe that anything in
2483
01:40:11,840 --> 01:40:14,480
computer science is too hard
2484
01:40:14,480 --> 01:40:17,600
it's not it's all just one big treasure
2485
01:40:17,600 --> 01:40:20,080
hunt to find information and knowledge
2486
01:40:20,080 --> 01:40:23,679
that best suits your intellectual filter
2487
01:40:23,679 --> 01:40:25,920
not all people teach all things the same
2488
01:40:25,920 --> 01:40:26,880
way
2489
01:40:26,880 --> 01:40:29,119
not all people learn information or
2490
01:40:29,119 --> 01:40:32,080
absorb knowledge the same way so let's
2491
01:40:32,080 --> 01:40:35,440
take a deep breath and step back to look
2492
01:40:35,440 --> 01:40:38,080
at the different dynamics that are out
2493
01:40:38,080 --> 01:40:39,840
there
2494
01:40:39,840 --> 01:40:41,760
that's a long list
2495
01:40:41,760 --> 01:40:44,239
for us there should only be two that
2496
01:40:44,239 --> 01:40:46,080
should really mean something
2497
01:40:46,080 --> 01:40:48,480
that's dynamic programming languages and
2498
01:40:48,480 --> 01:40:51,280
dynamic programming as a methodology you
2499
01:40:51,280 --> 01:40:53,040
can have programming languages that are
2500
01:40:53,040 --> 01:40:55,840
either dynamic or static python is
2501
01:40:55,840 --> 01:40:57,679
dynamic by the way and then you have
2502
01:40:57,679 --> 01:40:59,199
programming methodologies that are
2503
01:40:59,199 --> 01:41:01,520
concerned with analyzing a problem by
2504
01:41:01,520 --> 01:41:03,760
developing algorithms based on modern
2505
01:41:03,760 --> 01:41:05,520
programming techniques
2506
01:41:05,520 --> 01:41:07,840
in the world of dynamic programming
2507
01:41:07,840 --> 01:41:10,239
dp is used when the solution to a
2508
01:41:10,239 --> 01:41:12,239
problem can be viewed as a result of a
2509
01:41:12,239 --> 01:41:14,480
sequence of decisions with the intended
2510
01:41:14,480 --> 01:41:17,119
outcome of reducing run time and any
2511
01:41:17,119 --> 01:41:18,880
implementation that can make a solution
2512
01:41:18,880 --> 01:41:21,199
more efficient is considered optimizing
2513
01:41:21,199 --> 01:41:21,920
it
2514
01:41:21,920 --> 01:41:24,159
in an early lesson we saw several
2515
01:41:24,159 --> 01:41:26,400
problems that can be viewed in this way
2516
01:41:26,400 --> 01:41:28,800
i.e the knapsack problem
2517
01:41:28,800 --> 01:41:30,560
essentially the difference between the
2518
01:41:30,560 --> 01:41:33,040
greedy method and dp is that in the
2519
01:41:33,040 --> 01:41:36,000
greedy method only one decision sequence
2520
01:41:36,000 --> 01:41:39,199
is ever generated and in dp many
2521
01:41:39,199 --> 01:41:41,920
decision sequences may be generated
2522
01:41:41,920 --> 01:41:44,639
however sequences containing sub-optimal
2523
01:41:44,639 --> 01:41:47,280
sub-sequences cannot be optimal and as
2524
01:41:47,280 --> 01:41:49,760
far as possible will not be generated
2525
01:41:49,760 --> 01:41:51,840
and this is the key that helps make a
2526
01:41:51,840 --> 01:41:54,960
reduced run time optimal substructure
2527
01:41:54,960 --> 01:41:56,719
means that optimal solutions of
2528
01:41:56,719 --> 01:41:58,800
subproblems can be used to find the
2529
01:41:58,800 --> 01:42:01,679
optimal solutions of the overall problem
2530
01:42:01,679 --> 01:42:04,000
in dp this is called the principle of
2531
01:42:04,000 --> 01:42:06,639
optimality the principle of optimality
2532
01:42:06,639 --> 01:42:08,639
as relayed by richard bellman who
2533
01:42:08,639 --> 01:42:11,679
introduced dynamic programming in 1953
2534
01:42:11,679 --> 01:42:13,840
states that an optimal policy has the
2535
01:42:13,840 --> 01:42:16,080
property that whatever the initial state
2536
01:42:16,080 --> 01:42:18,560
and initial decision are the remaining
2537
01:42:18,560 --> 01:42:20,960
decisions must constitute an optimal
2538
01:42:20,960 --> 01:42:22,800
policy with regard to the state
2539
01:42:22,800 --> 01:42:25,119
resulting from the first decision
2540
01:42:25,119 --> 01:42:26,960
so what does that mean
2541
01:42:26,960 --> 01:42:29,199
in general we can solve a problem with
2542
01:42:29,199 --> 01:42:31,760
optimal substructure by doing three
2543
01:42:31,760 --> 01:42:32,719
things
2544
01:42:32,719 --> 01:42:34,960
breaking the problem down into smaller
2545
01:42:34,960 --> 01:42:37,040
sub problems
2546
01:42:37,040 --> 01:42:40,000
solving the sub problems recursively
2547
01:42:40,000 --> 01:42:42,480
and then using the optimal solutions to
2548
01:42:42,480 --> 01:42:45,040
construct an optimal solution for the
2549
01:42:45,040 --> 01:42:46,639
original problem
2550
01:42:46,639 --> 01:42:48,639
but there's an issue with this that we
2551
01:42:48,639 --> 01:42:50,480
need to be aware of and that is
2552
01:42:50,480 --> 01:42:53,280
sometimes when we do this we can get
2553
01:42:53,280 --> 01:42:56,400
overlapping subproblems we want to avoid
2554
01:42:56,400 --> 01:42:57,520
that
2555
01:42:57,520 --> 01:43:00,080
for instance in the fibonacci sequence
2556
01:43:00,080 --> 01:43:04,480
f3 equals f1 plus f2 and f4 equals f2
2557
01:43:04,480 --> 01:43:07,440
plus f3 computing each number involves
2558
01:43:07,440 --> 01:43:11,600
computing f2 because both f3 and f4 are
2559
01:43:11,600 --> 01:43:14,480
needed to compute f5 a naive approach to
2560
01:43:14,480 --> 01:43:17,920
computing f5 may end up computing f2
2561
01:43:17,920 --> 01:43:19,520
twice or more
2562
01:43:19,520 --> 01:43:22,239
in order to avoid this we instead save
2563
01:43:22,239 --> 01:43:24,800
or store the solutions to problems we
2564
01:43:24,800 --> 01:43:27,440
have already solved in dynamic
2565
01:43:27,440 --> 01:43:29,760
programming there are three basic
2566
01:43:29,760 --> 01:43:30,880
methods
2567
01:43:30,880 --> 01:43:32,800
we have recursion
2568
01:43:32,800 --> 01:43:35,760
top down with memoization and bottom up
2569
01:43:35,760 --> 01:43:38,000
with tabulation
2570
01:43:38,000 --> 01:43:40,480
and although we could have chosen the
2571
01:43:40,480 --> 01:43:43,920
well-worn path of the fibonacci sequence
2572
01:43:43,920 --> 01:43:45,360
to do this
2573
01:43:45,360 --> 01:43:47,040
oh no
2574
01:43:47,040 --> 01:43:49,600
i'm encouraging you to step out and
2575
01:43:49,600 --> 01:43:52,480
think bigger have confidence
2576
01:43:52,480 --> 01:43:55,760
you are smart and you can do big things
2577
01:43:55,760 --> 01:43:57,280
so
2578
01:43:57,280 --> 01:44:00,000
let's get ugly with it in our first
2579
01:44:00,000 --> 01:44:02,400
lesson
2580
01:44:05,760 --> 01:44:08,960
what are ugly numbers and why do we call
2581
01:44:08,960 --> 01:44:12,880
them ugly and what do we do with them
2582
01:44:12,880 --> 01:44:16,239
to answer the first question i saw this
2583
01:44:16,239 --> 01:44:21,159
and i think it will give you a big hint
2584
01:44:23,920 --> 01:44:24,880
okay
2585
01:44:24,880 --> 01:44:26,960
that's funny and i wish i could have
2586
01:44:26,960 --> 01:44:29,840
been the one to think it up but alas i
2587
01:44:29,840 --> 01:44:32,320
was too slow to the game
2588
01:44:32,320 --> 01:44:33,440
darn
2589
01:44:33,440 --> 01:44:36,080
i stumbled upon a pretty funny thread
2590
01:44:36,080 --> 01:44:38,960
about ugly numbers and i stole that so
2591
01:44:38,960 --> 01:44:40,960
shh don't tell on me
2592
01:44:40,960 --> 01:44:43,679
but the long and short of it is this
2593
01:44:43,679 --> 01:44:46,320
to check if a number is ugly in the
2594
01:44:46,320 --> 01:44:47,600
first place
2595
01:44:47,600 --> 01:44:50,000
we divide the number by the greatest
2596
01:44:50,000 --> 01:44:53,280
divisible powers of two three and five
2597
01:44:53,280 --> 01:44:55,600
and if the number becomes one
2598
01:44:55,600 --> 01:44:58,080
then it's an ugly number otherwise it's
2599
01:44:58,080 --> 01:44:58,960
not
2600
01:44:58,960 --> 01:45:01,520
we're employing our power of prime
2601
01:45:01,520 --> 01:45:03,040
factorization
2602
01:45:03,040 --> 01:45:05,119
we learned that way back in the fifth
2603
01:45:05,119 --> 01:45:07,440
grade so that tells me that you probably
2604
01:45:07,440 --> 01:45:08,880
don't remember
2605
01:45:08,880 --> 01:45:12,239
but it'll all come back to you today
2606
01:45:12,239 --> 01:45:15,280
the sequence of one to six eight nine 10
2607
01:45:15,280 --> 01:45:19,280
12 15 shows the first 11 ugly numbers by
2608
01:45:19,280 --> 01:45:22,239
convention one is included
2609
01:45:22,239 --> 01:45:24,080
all right now that you got that under
2610
01:45:24,080 --> 01:45:26,800
your belt let's tackle the problem of
2611
01:45:26,800 --> 01:45:29,520
finding the nth ugly number
2612
01:45:29,520 --> 01:45:32,800
can we find the hundredth ugly number
2613
01:45:32,800 --> 01:45:34,800
would you believe that if we crafted a
2614
01:45:34,800 --> 01:45:37,360
program using brute force it would be
2615
01:45:37,360 --> 01:45:40,400
over a thousand iterations
2616
01:45:40,400 --> 01:45:42,239
for the hundredth number
2617
01:45:42,239 --> 01:45:44,400
i think i broke my visualizer trying to
2618
01:45:44,400 --> 01:45:45,520
run it
2619
01:45:45,520 --> 01:45:47,840
and we don't want to break things or
2620
01:45:47,840 --> 01:45:50,320
make our computers smoke out the back or
2621
01:45:50,320 --> 01:45:52,639
anything like that so it's time to
2622
01:45:52,639 --> 01:45:55,600
incorporate our spirited energized
2623
01:45:55,600 --> 01:45:57,840
vigorous programming that's like
2624
01:45:57,840 --> 01:46:00,880
dinomite but not a lot of dynamite
2625
01:46:00,880 --> 01:46:03,679
we'll start small and just find the 15th
2626
01:46:03,679 --> 01:46:06,480
ugly number how does that sound
2627
01:46:06,480 --> 01:46:09,440
since we're going big and not going home
2628
01:46:09,440 --> 01:46:11,679
we're gonna shoot for the bottom up
2629
01:46:11,679 --> 01:46:14,159
method for a dynamic approach
2630
01:46:14,159 --> 01:46:17,199
if we use a pretty simple iterative with
2631
01:46:17,199 --> 01:46:19,679
some recursion solution we're still
2632
01:46:19,679 --> 01:46:22,400
looking at nearly 600 steps or
2633
01:46:22,400 --> 01:46:24,320
iterations in the program
2634
01:46:24,320 --> 01:46:26,880
to get our results as compared to just a
2635
01:46:26,880 --> 01:46:29,199
little over a hundred steps for the
2636
01:46:29,199 --> 01:46:31,920
bottom-up dynamic programming method
2637
01:46:31,920 --> 01:46:34,480
talk about optimization
2638
01:46:34,480 --> 01:46:36,840
if we use simple iteration and
2639
01:46:36,840 --> 01:46:39,040
continuously loop through all the
2640
01:46:39,040 --> 01:46:41,199
numbers to find whether each number is
2641
01:46:41,199 --> 01:46:44,159
ugly or not it can really bog down when
2642
01:46:44,159 --> 01:46:46,239
we get to larger numbers
2643
01:46:46,239 --> 01:46:48,560
with dynamic programming instead of
2644
01:46:48,560 --> 01:46:50,560
starting from the head we start from the
2645
01:46:50,560 --> 01:46:53,520
bottom we're also using a table to help
2646
01:46:53,520 --> 01:46:56,880
us store the values for easy access if
2647
01:46:56,880 --> 01:46:59,360
we look at the ugly number sequence 1 to
2648
01:46:59,360 --> 01:47:02,800
6 8 9 10 12 15 we can see that it can be
2649
01:47:02,800 --> 01:47:06,000
further divided into sub sequences of 2
2650
01:47:06,000 --> 01:47:08,960
3 and 5. and these subsequences
2651
01:47:08,960 --> 01:47:11,760
themselves are ugly numbers therefore we
2652
01:47:11,760 --> 01:47:14,480
take every ugly number from the above
2653
01:47:14,480 --> 01:47:17,600
sequences and choose the smallest ugly
2654
01:47:17,600 --> 01:47:19,760
number in every step to make sure that
2655
01:47:19,760 --> 01:47:22,000
we don't miss any number in between
2656
01:47:22,000 --> 01:47:25,840
let's head into our ides
2657
01:47:26,560 --> 01:47:29,199
okay so if we're looking for the nth
2658
01:47:29,199 --> 01:47:31,679
ugly number in a sequence we have to
2659
01:47:31,679 --> 01:47:33,360
write a function that will tell us if
2660
01:47:33,360 --> 01:47:34,719
our numbers
2661
01:47:34,719 --> 01:47:36,960
can be evenly divided in the first place
2662
01:47:36,960 --> 01:47:38,800
meaning no remainder
2663
01:47:38,800 --> 01:47:41,920
x modulo y equaling 0 gives us what we
2664
01:47:41,920 --> 01:47:43,840
need to prove that if there is a
2665
01:47:43,840 --> 01:47:46,400
remainder we'll just write it to return
2666
01:47:46,400 --> 01:47:48,719
our original number for our second step
2667
01:47:48,719 --> 01:47:50,880
before we can find the nth ugly number
2668
01:47:50,880 --> 01:47:53,199
position we have to check if it's an
2669
01:47:53,199 --> 01:47:55,679
ugly number we can do this recursively
2670
01:47:55,679 --> 01:47:58,159
by going back to our first function the
2671
01:47:58,159 --> 01:48:00,320
successive division
2672
01:48:00,320 --> 01:48:02,480
what this does is plug in the number
2673
01:48:02,480 --> 01:48:05,040
we're checking and successively or
2674
01:48:05,040 --> 01:48:07,119
successfully if you want to think of it
2675
01:48:07,119 --> 01:48:09,840
that way dividing it by two three and
2676
01:48:09,840 --> 01:48:12,159
five if our number is successfully
2677
01:48:12,159 --> 01:48:14,239
divided by two three and five with no
2678
01:48:14,239 --> 01:48:16,840
remainder we have an ugly number on our
2679
01:48:16,840 --> 01:48:20,000
hands let's check a six
2680
01:48:20,000 --> 01:48:22,639
it's true six is ugly
2681
01:48:22,639 --> 01:48:24,960
okay so we have what we need to find our
2682
01:48:24,960 --> 01:48:28,080
nth number six is fairly easy since
2683
01:48:28,080 --> 01:48:30,320
every number before it is ugly so the
2684
01:48:30,320 --> 01:48:32,560
sixth ugly number is
2685
01:48:32,560 --> 01:48:36,239
six but what's the 15th number well
2686
01:48:36,239 --> 01:48:38,400
let's write a program to find out
2687
01:48:38,400 --> 01:48:40,000
essentially what we're doing is merely
2688
01:48:40,000 --> 01:48:42,159
creating a counter coupled with
2689
01:48:42,159 --> 01:48:44,960
recursively calling back our ugly check
2690
01:48:44,960 --> 01:48:47,679
function we'll create two variables one
2691
01:48:47,679 --> 01:48:50,239
for i to iterate up our sequence and one
2692
01:48:50,239 --> 01:48:52,159
for our counter and then we just
2693
01:48:52,159 --> 01:48:54,400
incorporate a while loop to say as long
2694
01:48:54,400 --> 01:48:56,080
as our number is greater than our
2695
01:48:56,080 --> 01:48:59,119
counter we'll add one to i heading up
2696
01:48:59,119 --> 01:49:01,040
our number sequence and if that number
2697
01:49:01,040 --> 01:49:03,920
within our while loop is ugly add a 1 to
2698
01:49:03,920 --> 01:49:05,119
our counter
2699
01:49:05,119 --> 01:49:07,600
then we just return i
2700
01:49:07,600 --> 01:49:11,280
so what's our 15th ugly number
2701
01:49:11,280 --> 01:49:13,199
it's 24.
2702
01:49:13,199 --> 01:49:15,599
now if we run this program we have a lot
2703
01:49:15,599 --> 01:49:17,599
of running back in our recursive calls
2704
01:49:17,599 --> 01:49:20,000
for every number in our sequence
2705
01:49:20,000 --> 01:49:22,239
and that's a lot of running back with
2706
01:49:22,239 --> 01:49:25,679
600 steps or iterations that's a lot
2707
01:49:25,679 --> 01:49:28,400
considering with dp we can write a much
2708
01:49:28,400 --> 01:49:30,480
more efficient program that cuts all
2709
01:49:30,480 --> 01:49:33,440
those iterations by nearly 80 percent
2710
01:49:33,440 --> 01:49:35,599
let's check out the difference the first
2711
01:49:35,599 --> 01:49:38,480
major thing we can do is eliminate those
2712
01:49:38,480 --> 01:49:40,400
three functions within our original
2713
01:49:40,400 --> 01:49:42,880
program we won't need those remember
2714
01:49:42,880 --> 01:49:45,199
when i said we were going to implement a
2715
01:49:45,199 --> 01:49:47,760
table to store information
2716
01:49:47,760 --> 01:49:49,840
well that's what we're doing then we'll
2717
01:49:49,840 --> 01:49:52,159
start our first position in that table
2718
01:49:52,159 --> 01:49:54,480
or in other words a dynamic programming
2719
01:49:54,480 --> 01:49:58,080
array to store the ugly numbers next set
2720
01:49:58,080 --> 01:50:01,760
pointers for our multiples of 2 3 and 5
2721
01:50:01,760 --> 01:50:04,639
and we can do this all in one line which
2722
01:50:04,639 --> 01:50:07,040
is pretty cool you'll see how this works
2723
01:50:07,040 --> 01:50:09,760
as we get deeper into the program here's
2724
01:50:09,760 --> 01:50:12,400
our multiples of two three and five in
2725
01:50:12,400 --> 01:50:15,280
their own variables after that we loop
2726
01:50:15,280 --> 01:50:18,560
from one to n at each step and we find
2727
01:50:18,560 --> 01:50:21,119
the minimum ugly number out of three
2728
01:50:21,119 --> 01:50:24,400
multiples and store it in our dp array
2729
01:50:24,400 --> 01:50:26,880
we're also increasing the pointer for
2730
01:50:26,880 --> 01:50:29,440
the number whose multiple has been added
2731
01:50:29,440 --> 01:50:32,719
and replace it by its next multiple so
2732
01:50:32,719 --> 01:50:34,880
suppose a multiple of two has been added
2733
01:50:34,880 --> 01:50:37,360
to the array we increase twos pointer by
2734
01:50:37,360 --> 01:50:39,760
one and multiply the previous multiple
2735
01:50:39,760 --> 01:50:42,480
to two to get the next multiple and so
2736
01:50:42,480 --> 01:50:44,639
on and so forth for other numbers as
2737
01:50:44,639 --> 01:50:47,040
well and this way starting from the base
2738
01:50:47,040 --> 01:50:49,199
case we generate all the ugly numbers
2739
01:50:49,199 --> 01:50:51,199
and then apply dynamic programming to
2740
01:50:51,199 --> 01:50:53,920
store the numbers in the array until we
2741
01:50:53,920 --> 01:50:57,520
get the nth ugly number
2742
01:50:59,360 --> 01:51:01,840
this approach is way better than the
2743
01:51:01,840 --> 01:51:04,080
previous one because instead of checking
2744
01:51:04,080 --> 01:51:06,400
all the numbers for being ugly we just
2745
01:51:06,400 --> 01:51:08,719
used the previous ugly numbers to
2746
01:51:08,719 --> 01:51:10,239
generate new ones
2747
01:51:10,239 --> 01:51:14,599
watch how this runs through the program
2748
01:51:27,280 --> 01:51:30,000
this really is the better way
2749
01:51:30,000 --> 01:51:32,320
very efficient now let's put this
2750
01:51:32,320 --> 01:51:35,360
knowledge to good use on a very famous
2751
01:51:35,360 --> 01:51:38,639
problem called the traveling salesman
2752
01:51:38,639 --> 01:51:40,159
problem
2753
01:51:40,159 --> 01:51:42,480
if you haven't heard of this yet you
2754
01:51:42,480 --> 01:51:43,280
will
2755
01:51:43,280 --> 01:51:46,239
best to get it in your brain bucket now
2756
01:51:46,239 --> 01:51:49,840
rather than later
2757
01:51:52,239 --> 01:51:54,560
the traveling salesman problem is one of
2758
01:51:54,560 --> 01:51:57,520
the most intensely studied and famous
2759
01:51:57,520 --> 01:52:00,000
problems in computational mathematics
2760
01:52:00,000 --> 01:52:03,920
with its main main really main focus on
2761
01:52:03,920 --> 01:52:05,599
optimization
2762
01:52:05,599 --> 01:52:08,080
so much research has gone into this
2763
01:52:08,080 --> 01:52:10,000
challenge of finding the cheapest
2764
01:52:10,000 --> 01:52:12,960
shortest fastest route in the visitation
2765
01:52:12,960 --> 01:52:16,239
of locations by this dashingly handsome
2766
01:52:16,239 --> 01:52:18,159
or beautiful salesperson
2767
01:52:18,159 --> 01:52:21,599
this person starts in their home city
2768
01:52:21,599 --> 01:52:23,840
travels around and returns to their
2769
01:52:23,840 --> 01:52:26,480
starting point most easily expressed in
2770
01:52:26,480 --> 01:52:27,599
a graph
2771
01:52:27,599 --> 01:52:30,960
the general form of the tsp traveling
2772
01:52:30,960 --> 01:52:33,119
salesperson appears to have been first
2773
01:52:33,119 --> 01:52:34,960
studied by mathematicians during the
2774
01:52:34,960 --> 01:52:39,280
1930s in vienna and at harvard notably
2775
01:52:39,280 --> 01:52:41,040
by karl menger
2776
01:52:41,040 --> 01:52:44,080
menger defines the problem considers the
2777
01:52:44,080 --> 01:52:46,760
brute force algorithm and observes the
2778
01:52:46,760 --> 01:52:49,520
non-optimality of the nearest neighbor
2779
01:52:49,520 --> 01:52:52,159
heuristic using the mailman as an
2780
01:52:52,159 --> 01:52:54,560
example now the order in which the
2781
01:52:54,560 --> 01:52:57,199
person travels isn't cared about as long
2782
01:52:57,199 --> 01:52:59,360
as he visits each one
2783
01:52:59,360 --> 01:53:01,119
once during his trip
2784
01:53:01,119 --> 01:53:03,599
and finishes where he was at the first
2785
01:53:03,599 --> 01:53:06,000
in the most cost effective way but
2786
01:53:06,000 --> 01:53:07,440
there's a catch
2787
01:53:07,440 --> 01:53:10,000
maybe the salesman needs to take a plane
2788
01:53:10,000 --> 01:53:12,320
to one of the cities and this will cost
2789
01:53:12,320 --> 01:53:14,560
him a pretty penny
2790
01:53:14,560 --> 01:53:17,199
maybe he can walk to one of his cities
2791
01:53:17,199 --> 01:53:20,480
therefore making it a free trip the cost
2792
01:53:20,480 --> 01:53:23,119
associated with the trip describes how
2793
01:53:23,119 --> 01:53:25,520
difficult it is to to traverse the
2794
01:53:25,520 --> 01:53:28,159
journey or graph for us computer
2795
01:53:28,159 --> 01:53:31,040
scientists whether that's money or time
2796
01:53:31,040 --> 01:53:33,360
or distance required to complete the
2797
01:53:33,360 --> 01:53:36,560
traversal the salesman ideally wants to
2798
01:53:36,560 --> 01:53:39,199
keep every cost as low as possible he
2799
01:53:39,199 --> 01:53:41,760
wants the cheapest fastest shortest
2800
01:53:41,760 --> 01:53:44,880
route wouldn't you the easiest and most
2801
01:53:44,880 --> 01:53:46,800
expensive solution
2802
01:53:46,800 --> 01:53:49,360
is to simply try all the permutations
2803
01:53:49,360 --> 01:53:51,840
and then see which one is cheapest using
2804
01:53:51,840 --> 01:53:54,960
brute force the problem with this though
2805
01:53:54,960 --> 01:53:58,560
is that for n cities you have n minus 1
2806
01:53:58,560 --> 01:54:00,960
factorial possibilities this means that
2807
01:54:00,960 --> 01:54:04,960
just for 10 cities there are over 180
2808
01:54:04,960 --> 01:54:08,000
000 combinations to try since the start
2809
01:54:08,000 --> 01:54:09,520
city is defined there could be
2810
01:54:09,520 --> 01:54:12,480
permutations on the remaining nine
2811
01:54:12,480 --> 01:54:15,920
and at 20 cities this just becomes
2812
01:54:15,920 --> 01:54:17,520
simply infeasible
2813
01:54:17,520 --> 01:54:19,840
this is why four is often used in the
2814
01:54:19,840 --> 01:54:22,159
majority of problems as you'll quite
2815
01:54:22,159 --> 01:54:25,360
often see in the 4x4 matrices keeping it
2816
01:54:25,360 --> 01:54:27,840
small makes it much more manageable and
2817
01:54:27,840 --> 01:54:30,320
understandable which is good
2818
01:54:30,320 --> 01:54:32,639
the awesome news for us is that the
2819
01:54:32,639 --> 01:54:35,199
problem is solvable but keep in mind
2820
01:54:35,199 --> 01:54:37,280
that there can also be solutions to the
2821
01:54:37,280 --> 01:54:39,520
problems that are approximations or
2822
01:54:39,520 --> 01:54:42,239
commonly called heuristic algorithms if
2823
01:54:42,239 --> 01:54:45,040
that's what is being asked for according
2824
01:54:45,040 --> 01:54:47,960
to wikipedia even though the problem is
2825
01:54:47,960 --> 01:54:50,320
computationally difficult many
2826
01:54:50,320 --> 01:54:52,960
heuristics and exact algorithms are
2827
01:54:52,960 --> 01:54:56,000
known so that some instances with tens
2828
01:54:56,000 --> 01:54:59,119
of thousands of cities can be solved and
2829
01:54:59,119 --> 01:55:01,599
even problems with millions of cities
2830
01:55:01,599 --> 01:55:04,560
can be approximated within a fraction of
2831
01:55:04,560 --> 01:55:06,320
one percent
2832
01:55:06,320 --> 01:55:07,920
wow
2833
01:55:07,920 --> 01:55:10,400
so let's get to the nitty gritty and
2834
01:55:10,400 --> 01:55:13,040
look at our steps number one consider
2835
01:55:13,040 --> 01:55:15,760
city one as the starting and ending
2836
01:55:15,760 --> 01:55:16,639
point
2837
01:55:16,639 --> 01:55:19,840
number two generate all n
2838
01:55:19,840 --> 01:55:23,360
one factorial permutations of cities
2839
01:55:23,360 --> 01:55:25,360
three calculate cost of every
2840
01:55:25,360 --> 01:55:27,679
permutation and keep track of minimum
2841
01:55:27,679 --> 01:55:30,080
cost permutation four return the
2842
01:55:30,080 --> 01:55:32,880
permutation with minimum cost
2843
01:55:32,880 --> 01:55:34,880
it's not hard to see how this could get
2844
01:55:34,880 --> 01:55:36,960
computationally expensive in a very
2845
01:55:36,960 --> 01:55:39,280
short amount of time so we will move
2846
01:55:39,280 --> 01:55:42,159
into the optimize method right away for
2847
01:55:42,159 --> 01:55:43,440
our savings
2848
01:55:43,440 --> 01:55:45,280
and our sanity
2849
01:55:45,280 --> 01:55:47,840
the goal is to break this problem down
2850
01:55:47,840 --> 01:55:49,920
into the smallest pieces possible and
2851
01:55:49,920 --> 01:55:52,159
then solve solve solve
2852
01:55:52,159 --> 01:55:55,199
let's get into it
2853
01:55:57,679 --> 01:56:00,000
because permutations are a big part of
2854
01:56:00,000 --> 01:56:02,880
the tsp problem we're going to import
2855
01:56:02,880 --> 01:56:05,280
intertools permutations to make our
2856
01:56:05,280 --> 01:56:07,760
lives a whole lot easier
2857
01:56:07,760 --> 01:56:10,400
it's totally okay for this one
2858
01:56:10,400 --> 01:56:12,159
we'll implement a variable that we'll
2859
01:56:12,159 --> 01:56:13,280
call v
2860
01:56:13,280 --> 01:56:16,960
short for vertices and vertices are the
2861
01:56:16,960 --> 01:56:19,199
dots on our graph think of our sales
2862
01:56:19,199 --> 01:56:21,440
person traveling to four cities on our
2863
01:56:21,440 --> 01:56:24,719
graph a single dot is called a vertex
2864
01:56:24,719 --> 01:56:27,119
on our graph and they link or connect to
2865
01:56:27,119 --> 01:56:29,599
one another now we can move on to
2866
01:56:29,599 --> 01:56:31,760
implementing our function call here with
2867
01:56:31,760 --> 01:56:34,159
two parameters our graph that will be a
2868
01:56:34,159 --> 01:56:37,280
four by four matrix and s is going to be
2869
01:56:37,280 --> 01:56:39,199
our counter that will need to calculate
2870
01:56:39,199 --> 01:56:41,679
the sum of our path i'll explain this a
2871
01:56:41,679 --> 01:56:43,040
little bit deeper at the end of the
2872
01:56:43,040 --> 01:56:44,000
program
2873
01:56:44,000 --> 01:56:45,920
we'll create an empty list for our
2874
01:56:45,920 --> 01:56:48,400
vertices to be stored in and we'll call
2875
01:56:48,400 --> 01:56:51,599
this vertex just to make it plain this
2876
01:56:51,599 --> 01:56:54,000
is going to tell us the best route for
2877
01:56:54,000 --> 01:56:56,800
our rows in the graph again this is
2878
01:56:56,800 --> 01:56:59,199
going to be come real clear at the end
2879
01:56:59,199 --> 01:57:02,639
of the program so hold on to yourselves
2880
01:57:02,639 --> 01:57:05,440
then we iterate over our range of v and
2881
01:57:05,440 --> 01:57:08,320
if the index does not equal us which is
2882
01:57:08,320 --> 01:57:10,960
zero we append it to our empty vertex
2883
01:57:10,960 --> 01:57:13,440
list this is going to show us where our
2884
01:57:13,440 --> 01:57:15,599
salesperson is traveling within the
2885
01:57:15,599 --> 01:57:18,239
graph but here's a little catch that we
2886
01:57:18,239 --> 01:57:21,119
need to be aware of check out our graph
2887
01:57:21,119 --> 01:57:23,760
see those trails of zeros
2888
01:57:23,760 --> 01:57:26,080
we have no need to calculate those so
2889
01:57:26,080 --> 01:57:28,560
when we append our indices to our vertex
2890
01:57:28,560 --> 01:57:31,679
list we're only producing three integers
2891
01:57:31,679 --> 01:57:33,760
one two and three
2892
01:57:33,760 --> 01:57:36,560
next we create another empty list that
2893
01:57:36,560 --> 01:57:38,800
we'll call min path
2894
01:57:38,800 --> 01:57:40,880
we need to know the best route so this
2895
01:57:40,880 --> 01:57:42,880
will store our lowest combination of
2896
01:57:42,880 --> 01:57:45,199
vertices within the graph
2897
01:57:45,199 --> 01:57:46,960
then we create a variable that we'll
2898
01:57:46,960 --> 01:57:49,360
call next permutation and we'll
2899
01:57:49,360 --> 01:57:51,360
implement the inter tools permutations
2900
01:57:51,360 --> 01:57:53,199
module here to give us all the
2901
01:57:53,199 --> 01:57:55,599
combinations of the vertices for one two
2902
01:57:55,599 --> 01:57:56,639
and three
2903
01:57:56,639 --> 01:57:59,520
since we have three numbers we know that
2904
01:57:59,520 --> 01:58:02,560
the amount of permutations will be six
2905
01:58:02,560 --> 01:58:04,800
then we iterate over all those
2906
01:58:04,800 --> 01:58:06,880
combinations and create a counter that
2907
01:58:06,880 --> 01:58:08,960
we'll call current pathway we'll
2908
01:58:08,960 --> 01:58:11,360
reassign our s to a variable we'll call
2909
01:58:11,360 --> 01:58:14,159
k and k will represent the row in our
2910
01:58:14,159 --> 01:58:15,280
graph
2911
01:58:15,280 --> 01:58:17,679
and as we iterate over our indices
2912
01:58:17,679 --> 01:58:20,880
within our permutations by using j
2913
01:58:20,880 --> 01:58:23,280
this becomes our columns i know this
2914
01:58:23,280 --> 01:58:25,040
sounds i know this all sounds really
2915
01:58:25,040 --> 01:58:28,000
confusing but stay with me when we add
2916
01:58:28,000 --> 01:58:30,639
the k and j of our graph to our current
2917
01:58:30,639 --> 01:58:35,040
pathway look what prints out
2918
01:58:35,040 --> 01:58:37,679
this is calculating all the paths within
2919
01:58:37,679 --> 01:58:40,000
our graph and adding them together
2920
01:58:40,000 --> 01:58:41,760
pretty cool isn't it
2921
01:58:41,760 --> 01:58:45,440
next we reassign k to j and then use an
2922
01:58:45,440 --> 01:58:48,159
addition operator to add the sums to our
2923
01:58:48,159 --> 01:58:50,800
graph to the current pathway append them
2924
01:58:50,800 --> 01:58:53,760
to our min pass hold them in a variable
2925
01:58:53,760 --> 01:58:56,400
called x that's sorted
2926
01:58:56,400 --> 01:58:59,040
and simply return the very first number
2927
01:58:59,040 --> 01:59:01,679
in our sorted list which is our lowest
2928
01:59:01,679 --> 01:59:02,480
number
2929
01:59:02,480 --> 01:59:05,119
our shortest route on the graph to see
2930
01:59:05,119 --> 01:59:07,040
how this travels
2931
01:59:07,040 --> 01:59:11,639
on the graph watch this
2932
01:59:17,679 --> 01:59:20,480
this is how it is adding up within our
2933
01:59:20,480 --> 01:59:21,599
program
2934
01:59:21,599 --> 01:59:24,719
hopefully you can see and understand how
2935
01:59:24,719 --> 01:59:27,760
this is all working it sounds so much
2936
01:59:27,760 --> 01:59:30,880
more complicated than it really is but
2937
01:59:30,880 --> 01:59:32,800
it's only math
2938
01:59:32,800 --> 01:59:35,440
we're simply calculating the paths of a
2939
01:59:35,440 --> 01:59:37,520
matrix by pulling out all the
2940
01:59:37,520 --> 01:59:39,760
combinations or permutations of the
2941
01:59:39,760 --> 01:59:42,719
indices and returning the lowest number
2942
01:59:42,719 --> 01:59:45,920
or lowest sum of the path it's not too
2943
01:59:45,920 --> 01:59:49,040
bad my recommendation to you would be to
2944
01:59:49,040 --> 01:59:51,360
create your own graph and then run it in
2945
01:59:51,360 --> 01:59:53,760
the program once you do that
2946
01:59:53,760 --> 01:59:56,239
map that course on paper or even
2947
01:59:56,239 --> 01:59:59,840
whiteboard it to see it visually
2948
02:00:03,440 --> 02:00:06,800
for our very last lesson today and not
2949
02:00:06,800 --> 02:00:09,280
only for dp but
2950
02:00:09,280 --> 02:00:10,880
all together
2951
02:00:10,880 --> 02:00:14,080
i'm so sad to leave you
2952
02:00:14,080 --> 02:00:17,520
so let's make this session a great one
2953
02:00:17,520 --> 02:00:19,280
what we're doing for our mindbreaker
2954
02:00:19,280 --> 02:00:21,440
sounds really intimidating but i can
2955
02:00:21,440 --> 02:00:24,000
assure you that once we break this down
2956
02:00:24,000 --> 02:00:26,239
you're gonna say wow that wasn't even
2957
02:00:26,239 --> 02:00:28,560
that bad and then you can brag to all
2958
02:00:28,560 --> 02:00:31,199
your friends and then they'll shun you
2959
02:00:31,199 --> 02:00:33,280
for your genius
2960
02:00:33,280 --> 02:00:36,320
but it'll be totally worth it i i mean
2961
02:00:36,320 --> 02:00:41,280
because who needs friends am i right
2962
02:00:41,280 --> 02:00:44,159
now your brain won't break too much if
2963
02:00:44,159 --> 02:00:46,560
we take each word out and examine it
2964
02:00:46,560 --> 02:00:48,880
first we have palindromic which is
2965
02:00:48,880 --> 02:00:51,679
religious palindrome matrix we'll keep
2966
02:00:51,679 --> 02:00:54,960
it low and slow with a 3x3
2967
02:00:54,960 --> 02:00:56,800
and then just paths which we're only
2968
02:00:56,800 --> 02:00:59,679
going to go right and down only
2969
02:00:59,679 --> 02:01:01,840
since we worked on a matrix in our last
2970
02:01:01,840 --> 02:01:04,719
problem this should be old hat hopefully
2971
02:01:04,719 --> 02:01:06,400
by now you have a decent handle on
2972
02:01:06,400 --> 02:01:08,239
breaking down the problem into smaller
2973
02:01:08,239 --> 02:01:10,719
ones called sub problems and solving
2974
02:01:10,719 --> 02:01:12,960
them little by little in order to solve
2975
02:01:12,960 --> 02:01:14,159
the whole
2976
02:01:14,159 --> 02:01:16,000
tips for getting started on the
2977
02:01:16,000 --> 02:01:18,960
palindromic matrix path problem would be
2978
02:01:18,960 --> 02:01:21,520
to first know how to check whether a
2979
02:01:21,520 --> 02:01:23,280
string is a palindrome or not in the
2980
02:01:23,280 --> 02:01:24,560
first place
2981
02:01:24,560 --> 02:01:27,520
you can use python's python has a little
2982
02:01:27,520 --> 02:01:29,599
pip install program called
2983
02:01:29,599 --> 02:01:31,360
palindrome that
2984
02:01:31,360 --> 02:01:33,360
checks whether a string is pendulum or
2985
02:01:33,360 --> 02:01:35,440
not but i do highly recommend you learn
2986
02:01:35,440 --> 02:01:37,840
how to do this on your own
2987
02:01:37,840 --> 02:01:40,159
because it will help with this problem
2988
02:01:40,159 --> 02:01:42,960
the second tip would be knowing how to
2989
02:01:42,960 --> 02:01:45,520
traverse a matrix going right and down
2990
02:01:45,520 --> 02:01:46,480
only
2991
02:01:46,480 --> 02:01:48,880
we're not going to get too crazy for our
2992
02:01:48,880 --> 02:01:51,520
final lesson and just have some fun with
2993
02:01:51,520 --> 02:01:54,320
it by printing our palindrome strings
2994
02:01:54,320 --> 02:01:57,040
we're not going to return counts or find
2995
02:01:57,040 --> 02:01:59,599
the longest because that might make some
2996
02:01:59,599 --> 02:02:01,119
of us cry
2997
02:02:01,119 --> 02:02:04,159
and there will be no crying today any
2998
02:02:04,159 --> 02:02:07,199
tears that gets shed must be happy tears
2999
02:02:07,199 --> 02:02:09,920
only whether that's joy at finishing
3000
02:02:09,920 --> 02:02:13,040
this course or not seeing my face
3001
02:02:13,040 --> 02:02:14,800
anymore
3002
02:02:14,800 --> 02:02:18,159
tears of accomplishment are fine but no
3003
02:02:18,159 --> 02:02:21,199
tears of sadness okay to keep it simple
3004
02:02:21,199 --> 02:02:23,119
we'll start at ground zero and start
3005
02:02:23,119 --> 02:02:25,599
with an empty three by three matrix and
3006
02:02:25,599 --> 02:02:28,080
find all the unique paths
3007
02:02:28,080 --> 02:02:30,320
what's really cool about this is that
3008
02:02:30,320 --> 02:02:33,119
it's actually just a math problem
3009
02:02:33,119 --> 02:02:35,920
what we'll do is create in our three by
3010
02:02:35,920 --> 02:02:38,639
three by starting with a row of ones
3011
02:02:38,639 --> 02:02:41,040
that we will build up from
3012
02:02:41,040 --> 02:02:43,920
our bottom row and far right column will
3013
02:02:43,920 --> 02:02:46,400
be ones and when we add their adjacent
3014
02:02:46,400 --> 02:02:48,960
numbers together and build up we get a
3015
02:02:48,960 --> 02:02:51,679
row of ones one one one at the bottom
3016
02:02:51,679 --> 02:02:53,920
and then three two one in the middle and
3017
02:02:53,920 --> 02:02:56,800
then six three one at the top
3018
02:02:56,800 --> 02:03:00,080
if we return row zero
3019
02:03:00,080 --> 02:03:02,239
that will give us six and that tells us
3020
02:03:02,239 --> 02:03:04,639
that we have six unique paths in our
3021
02:03:04,639 --> 02:03:05,760
matrix
3022
02:03:05,760 --> 02:03:07,760
this will come in handy later when we
3023
02:03:07,760 --> 02:03:09,920
implement this principle into our matrix
3024
02:03:09,920 --> 02:03:11,040
of strings
3025
02:03:11,040 --> 02:03:12,880
we can know that we will have six
3026
02:03:12,880 --> 02:03:15,280
strings returned to us and all we need
3027
02:03:15,280 --> 02:03:17,280
to do is check whether they're
3028
02:03:17,280 --> 02:03:20,080
palindromes and print those out
3029
02:03:20,080 --> 02:03:23,199
so we're not going to talk much if at
3030
02:03:23,199 --> 02:03:26,000
all about the naive approach or brute
3031
02:03:26,000 --> 02:03:27,920
force or whatever the difference is in
3032
02:03:27,920 --> 02:03:29,920
optimization no
3033
02:03:29,920 --> 02:03:32,880
let's part ways on a good note and have
3034
02:03:32,880 --> 02:03:34,320
some fun with this
3035
02:03:34,320 --> 02:03:37,360
i mean we walked through 14 other
3036
02:03:37,360 --> 02:03:40,159
problems with multiple methods in a
3037
02:03:40,159 --> 02:03:42,560
relatively short amount of time
3038
02:03:42,560 --> 02:03:45,440
and here we are breaking our minds on
3039
02:03:45,440 --> 02:03:49,040
palindromic matrix paths so yeah let's
3040
02:03:49,040 --> 02:03:52,159
get straight to the optimum let's code
3041
02:03:52,159 --> 02:03:54,880
the paths problem first shall we we'll
3042
02:03:54,880 --> 02:03:56,800
start by creating our function with two
3043
02:03:56,800 --> 02:03:59,840
parameters our row and our column we
3044
02:03:59,840 --> 02:04:01,599
already know it's going to be a three by
3045
02:04:01,599 --> 02:04:03,840
three then we create our dynamic
3046
02:04:03,840 --> 02:04:06,719
programming array of all ones which you
3047
02:04:06,719 --> 02:04:09,360
can envision as our bottom row of ones
3048
02:04:09,360 --> 02:04:12,239
next we iterate over our rows in a for
3049
02:04:12,239 --> 02:04:14,880
loop and then create another dp array
3050
02:04:14,880 --> 02:04:16,480
which can be envisioned as an
3051
02:04:16,480 --> 02:04:19,440
accumulative next row up in our matrix
3052
02:04:19,440 --> 02:04:21,360
our original for loop is going to
3053
02:04:21,360 --> 02:04:24,400
iterate three times 0 1 2
3054
02:04:24,400 --> 02:04:27,520
for each row in our matrix in a second
3055
02:04:27,520 --> 02:04:29,679
for loop we now want to iterate from the
3056
02:04:29,679 --> 02:04:31,840
bottom up and reassign our new row
3057
02:04:31,840 --> 02:04:34,079
elements by adding one element to the
3058
02:04:34,079 --> 02:04:36,960
one next to it going left
3059
02:04:36,960 --> 02:04:38,560
we do this twice
3060
02:04:38,560 --> 02:04:40,639
while in our final iteration it has
3061
02:04:40,639 --> 02:04:43,679
accumulated each row to end with six
3062
02:04:43,679 --> 02:04:46,719
three one we then reassign our original
3063
02:04:46,719 --> 02:04:49,199
row as the final row and return the very
3064
02:04:49,199 --> 02:04:51,360
first element which will be six
3065
02:04:51,360 --> 02:04:53,840
our answer to the number of paths now
3066
02:04:53,840 --> 02:04:56,159
this isn't super necessary but it will
3067
02:04:56,159 --> 02:04:58,560
give you an idea of the path traversal
3068
02:04:58,560 --> 02:05:00,560
within a three by three matrix and will
3069
02:05:00,560 --> 02:05:02,719
give us a good launch point to moving up
3070
02:05:02,719 --> 02:05:05,280
to a matrix consisting of letters we'll
3071
02:05:05,280 --> 02:05:08,079
keep it in the realm of just two letters
3072
02:05:08,079 --> 02:05:08,880
a
3073
02:05:08,880 --> 02:05:10,960
and b and we'll write a very quick
3074
02:05:10,960 --> 02:05:12,639
little program to see how many
3075
02:05:12,639 --> 02:05:15,599
palindromes of a and b there are
3076
02:05:15,599 --> 02:05:18,400
let's import intertools to help us and
3077
02:05:18,400 --> 02:05:20,239
then create our rows and columns of
3078
02:05:20,239 --> 02:05:21,280
letters
3079
02:05:21,280 --> 02:05:23,599
a neat little feature of inter tools is
3080
02:05:23,599 --> 02:05:26,719
product with an asterisk on our matrix
3081
02:05:26,719 --> 02:05:29,199
this will print out every combination of
3082
02:05:29,199 --> 02:05:33,199
letters in our matrix totaling 27. yes
3083
02:05:33,199 --> 02:05:35,679
there will be duplicates here but it's
3084
02:05:35,679 --> 02:05:39,119
nothing that python's set can't handle
3085
02:05:39,119 --> 02:05:41,679
let's create an empty list called p1 and
3086
02:05:41,679 --> 02:05:45,199
then iterate over our list of 27 tuples
3087
02:05:45,199 --> 02:05:47,280
join them together to make it easy on
3088
02:05:47,280 --> 02:05:49,520
the eyes and append them to our empty
3089
02:05:49,520 --> 02:05:50,320
list
3090
02:05:50,320 --> 02:05:52,719
then all that's left to do is check
3091
02:05:52,719 --> 02:05:54,719
which ones are palindromes by making a
3092
02:05:54,719 --> 02:05:57,920
new function plugging in our p1 create
3093
02:05:57,920 --> 02:06:01,280
another empty list p2 and then iterating
3094
02:06:01,280 --> 02:06:04,719
over a non-duplicate set of p1
3095
02:06:04,719 --> 02:06:07,040
incorporate an if statement is it a
3096
02:06:07,040 --> 02:06:10,320
palindrome yes put it in our empty list
3097
02:06:10,320 --> 02:06:11,679
then return it
3098
02:06:11,679 --> 02:06:14,480
okay so far we've traversed a matrix in
3099
02:06:14,480 --> 02:06:16,560
order to count the number of paths in it
3100
02:06:16,560 --> 02:06:18,639
we created a three by three matrix of
3101
02:06:18,639 --> 02:06:21,199
just two letters found every possible
3102
02:06:21,199 --> 02:06:24,239
combination and created a function to
3103
02:06:24,239 --> 02:06:26,320
pull the palindromes from it
3104
02:06:26,320 --> 02:06:29,679
we are doing fabulously if you know how
3105
02:06:29,679 --> 02:06:31,920
to count the paths of a matrix and find
3106
02:06:31,920 --> 02:06:34,239
the palindromes in a matrix you're
3107
02:06:34,239 --> 02:06:36,320
totally equipped to take on the
3108
02:06:36,320 --> 02:06:39,360
palindromic paths problem
3109
02:06:39,360 --> 02:06:41,760
let's get cracking
3110
02:06:41,760 --> 02:06:42,560
so
3111
02:06:42,560 --> 02:06:45,119
before we start i have to tell you
3112
02:06:45,119 --> 02:06:47,199
there's going to be a little bit of a
3113
02:06:47,199 --> 02:06:49,360
difference here for this program
3114
02:06:49,360 --> 02:06:52,639
it's the order of traversal we're going
3115
02:06:52,639 --> 02:06:55,920
to go from the top and right to the
3116
02:06:55,920 --> 02:06:58,400
bottom not the bottom up and left to the
3117
02:06:58,400 --> 02:06:59,360
top
3118
02:06:59,360 --> 02:07:02,719
so keep that in mind as we march forward
3119
02:07:02,719 --> 02:07:05,119
we're going to throw in our little
3120
02:07:05,119 --> 02:07:08,159
palindrome checker up here first before
3121
02:07:08,159 --> 02:07:10,079
we print them out at the end of our
3122
02:07:10,079 --> 02:07:12,320
function hopefully by now you're
3123
02:07:12,320 --> 02:07:14,239
familiar with that
3124
02:07:14,239 --> 02:07:16,079
next we're going to create our main
3125
02:07:16,079 --> 02:07:18,880
function with several parameters
3126
02:07:18,880 --> 02:07:21,760
a string that will be empty but we're
3127
02:07:21,760 --> 02:07:24,719
just going to call it string here
3128
02:07:24,719 --> 02:07:27,840
a for our array
3129
02:07:27,840 --> 02:07:32,079
our pointers that we'll call i and j
3130
02:07:32,079 --> 02:07:35,599
our row and column that we'll call m and
3131
02:07:35,599 --> 02:07:36,719
n
3132
02:07:36,719 --> 02:07:39,280
now our conditional if statements are
3133
02:07:39,280 --> 02:07:42,320
going to traverse the paths of our array
3134
02:07:42,320 --> 02:07:45,119
we minus one from m and n because as you
3135
02:07:45,119 --> 02:07:47,520
know this is python and we only need to
3136
02:07:47,520 --> 02:07:50,320
iterate from indices starting at zero
3137
02:07:50,320 --> 02:07:53,280
then one then two for our total size of
3138
02:07:53,280 --> 02:07:56,079
rows and columns three by three see the
3139
02:07:56,079 --> 02:07:59,199
i plus one and the j plus one within our
3140
02:07:59,199 --> 02:08:01,920
recursive callbacks look at these slides
3141
02:08:01,920 --> 02:08:05,480
to see the paths
3142
02:08:09,520 --> 02:08:12,560
you could also print i and j within the
3143
02:08:12,560 --> 02:08:14,400
conditional statements on your own to
3144
02:08:14,400 --> 02:08:17,040
see it as well but when we add one to
3145
02:08:17,040 --> 02:08:19,440
our pointers we're moving to the next
3146
02:08:19,440 --> 02:08:21,199
element then
3147
02:08:21,199 --> 02:08:24,079
once the traversal is completed it hits
3148
02:08:24,079 --> 02:08:26,400
our else statement and that hits up our
3149
02:08:26,400 --> 02:08:29,840
palindrome checker if it's true it'll
3150
02:08:29,840 --> 02:08:32,560
print then it moves on to do the next
3151
02:08:32,560 --> 02:08:35,679
reversal over and over until it's done
3152
02:08:35,679 --> 02:08:37,280
and there you have it
3153
02:08:37,280 --> 02:08:40,639
four palindrome strings in our matrix
3154
02:08:40,639 --> 02:08:43,040
yay
3155
02:08:43,200 --> 02:08:46,300
[Applause]
3156
02:08:46,480 --> 02:08:50,719
so what did we learn on our final lesson
3157
02:08:50,719 --> 02:08:53,040
we learned about dynamic programming
3158
02:08:53,040 --> 02:08:55,440
which is finding the optimal solution to
3159
02:08:55,440 --> 02:08:57,520
sub problems that can be used to find
3160
02:08:57,520 --> 02:09:00,000
the optimal solutions to the overall
3161
02:09:00,000 --> 02:09:01,280
problem
3162
02:09:01,280 --> 02:09:03,599
we saw this in our lesson with ugly
3163
02:09:03,599 --> 02:09:06,159
numbers the traveling salesman problem
3164
02:09:06,159 --> 02:09:09,040
and palindromic matrix paths
3165
02:09:09,040 --> 02:09:11,280
in the easy lesson we learned about ugly
3166
02:09:11,280 --> 02:09:13,920
numbers what they are and how to write a
3167
02:09:13,920 --> 02:09:16,639
program to find the nth ugly number in
3168
02:09:16,639 --> 02:09:20,159
the sequence avoiding brute force and
3169
02:09:20,159 --> 02:09:22,159
recursion we were able to implement
3170
02:09:22,159 --> 02:09:24,800
dynamic programming to optimize the
3171
02:09:24,800 --> 02:09:27,199
solution from over one thousand
3172
02:09:27,199 --> 02:09:30,239
iterations down to just a little over
3173
02:09:30,239 --> 02:09:31,520
one
3174
02:09:31,520 --> 02:09:34,000
we looked at the very famous traveling
3175
02:09:34,000 --> 02:09:37,119
salesman problem with its main focus in
3176
02:09:37,119 --> 02:09:39,520
optimizing a solution to finding the
3177
02:09:39,520 --> 02:09:43,520
most efficient route a solution used
3178
02:09:43,520 --> 02:09:46,960
across the board for so many companies
3179
02:09:46,960 --> 02:09:50,239
in order to keep operational costs low
3180
02:09:50,239 --> 02:09:53,040
and lastly we broke down the mind
3181
02:09:53,040 --> 02:09:55,920
breaker lesson by studying unique paths
3182
02:09:55,920 --> 02:09:57,280
in a matrix
3183
02:09:57,280 --> 02:09:59,920
string palindromes within a matrix and
3184
02:09:59,920 --> 02:10:02,560
combining those two problems together to
3185
02:10:02,560 --> 02:10:05,760
find all the palindromic paths within a
3186
02:10:05,760 --> 02:10:08,320
matrix
3187
02:10:09,040 --> 02:10:12,239
are you excited i know that i am we
3188
02:10:12,239 --> 02:10:14,480
covered so much ground in this course
3189
02:10:14,480 --> 02:10:16,560
it's crazy
3190
02:10:16,560 --> 02:10:18,960
hopefully you took lots of notes so you
3191
02:10:18,960 --> 02:10:21,920
can practice later you should be coding
3192
02:10:21,920 --> 02:10:24,960
something every day even if it's just
3193
02:10:24,960 --> 02:10:28,320
for a couple minutes 10 to 15. since
3194
02:10:28,320 --> 02:10:30,400
every little bit helps now listen to
3195
02:10:30,400 --> 02:10:32,320
your mother thank you so much for
3196
02:10:32,320 --> 02:10:34,400
joining me today and if you made it all
3197
02:10:34,400 --> 02:10:37,840
the way here kudos to you i wish you all
3198
02:10:37,840 --> 02:10:42,920
the best in your programming journey bye
222506
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.