Brute Force algorithms with real life examples | Study Algorithms
Brute Force algorithms with real life examples | Study Algorithms
To see more videos like this, you can buy me a coffee: https://www.buymeacoffee.com/studyalg…
Usually a developer’s first choice to approach a problem, a Brute force method simply means that try out all the alternatives until you are exhausted of options. If the problem is solvable, you will eventually find an answer.
00:00 - Intro
00:29 - Definition and example
01:58 - Real life example (Solving a Rubik’s cube)
04:02 - Solving a magic square with Brute Force
05:42 - When does this method fail?
My favorite book on Introduction To Algorithms: https://amzn.to/35RrVuK
📘 The description and some of these approaches are available at: https://studyalgorithms.com/theory/al…
📘 Some examples where we use brute force method:
https://studyalgorithms.com/string/va…
https://studyalgorithms.com/string/fi…
📚 Algorithmic Paradigms:
Brute Force: • Brute Force algorithms with real life…
Divide and Conquer: • Divide and Conquer algorithms with re…
Dynamic Programming (Part 1): • Dynamic Programming easy to understan…
Dynamic Programming (Part 2): • 0/1 Knapsack Problem easy explanation…
🔗 To see more videos like this, you can show your support on https://www.buymeacoffee.com/studyalg…
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: https://studyalgorithms.com/feed/
#studyAlgorithms #programming #interview
Content
0.64 -> hello guys welcome to study algorithms
3.28 -> and today we would be looking at
6.48 -> brute force algorithmic paradigms first
9.84 -> i would tell you the definition and show
11.92 -> you an example
13.44 -> we would then see what limitations this
15.599 -> method might have
17.279 -> going forward i would explain you why
19.68 -> you should even consider using this
21.279 -> method
21.92 -> and in what scenarios it can fail so let
24.64 -> us dive into it
26.24 -> so what do you exactly mean by a brute
28.48 -> force method
30 -> the best way to understand any problem
32.32 -> would be by an example
34 -> i am taking over here an example of a
36.079 -> padlock you must have seen these kind of
38.399 -> padlocks in day-to-day life
40.48 -> so this one can be opened using a
42.48 -> three-digit combination
44 -> now this has a combination of two three
46.559 -> four
47.44 -> if you know this combination then it is
49.52 -> fairly simple to open it
51.52 -> but what if you don't know this
52.96 -> combination and you still want to open
54.96 -> this padlock desperately
56.48 -> and you're trying that maybe i can just
58.239 -> open this padlock somehow
60.559 -> well what do you do one thing that would
63.92 -> come to your mind is
65.36 -> what if i try all the combinations that
67.36 -> are possible so i would go with 0 0 0
70.96 -> then 0 0 1 0 0 2
74.56 -> 0 0 3 and then so on you get the idea
79.04 -> and eventually what would happen is you
81.52 -> would land upon the code
83.119 -> 2 3 4 and this padlock would open
87.759 -> so what did you just do you just
90.079 -> exhausted all of your possibilities
92.24 -> to open the padlock and this exactly is
95.36 -> a brute force method
97.52 -> you are deploying all the resources
99.2 -> available to you no matter how much the
101.28 -> time
101.92 -> and you're trying to solve a problem
105.28 -> in this case the maximum number of
107.119 -> combinations that you could have
108.72 -> was 1000
111.84 -> and going on and on and on you would
114 -> eventually try to figure it out
115.759 -> but do you see the problem with this
117.439 -> method momentarily
119.28 -> it may seem that given some time i
122.24 -> should be able to solve
123.36 -> any problem using a brute force method
125.84 -> well that is true
127.439 -> but it is quite limited in an earlier
130.959 -> example
131.599 -> of a padlock the maximum combinations
133.84 -> that we had
134.8 -> were just one thousand let me take up
137.52 -> another problem
138.48 -> and that is some one of my favorite
140 -> problems of a rubik's cube
142.16 -> all of you must be familiar with rubik
144 -> cube it has got six
145.52 -> faces and six colors and ultimately what
148.64 -> i need to do is
149.68 -> each face should have a single color you
152 -> cannot even
153.12 -> start to think how many total number of
155.2 -> combinations are possible
157.12 -> this for instance is one combination if
159.68 -> i rotate it in this way
161.2 -> this is another combination i rotate it
163.599 -> another
164.319 -> this is again another combination in
167.12 -> fact
168.239 -> any combination you try there is a very
171.12 -> slight chance that you would be
172.4 -> repeating one of your choices
174.319 -> and this rubik's cube has a total of 43
178.159 -> quintillion total combinations that's
180.72 -> like
181.2 -> 43 followed by 18 zeros
184.4 -> that's too much right so you cannot
187.76 -> even hope to solve this rubik's cube
190.4 -> using a brute force method
192.239 -> yes given a lot of time you would
194.48 -> eventually arrive at a solution
196.239 -> and you would be able to solve it but
198.319 -> that won't be optimal
200.48 -> since i'm a kind of a control freak i
202.64 -> would just go ahead and solve
204.48 -> one of the faces for you
214.48 -> so i made one of the faces what i did
217.28 -> here was
217.92 -> i applied some tricks to solve this one
220.159 -> phase and that
221.44 -> is not a brute force method to summarize
224.4 -> a brute force method
225.599 -> what you can say is you are exhausting
227.92 -> all of your options
229.36 -> to find at a solution in most of my
232.08 -> videos
232.64 -> you must have seen that i always
234.159 -> emphasize upon the fact that
236.159 -> do find a brute force solution do find a
238.08 -> brutal solution why is that so
240.56 -> let us try to have a look at it i always
243.599 -> emphasize on the fact
245.04 -> that a good developer would always try
247.12 -> to come up with the brute force solution
248.72 -> first
249.2 -> and then try to optimize it but why do i
251.84 -> say that
252.64 -> that is because a brute force method
255.12 -> would guarantee you
256.4 -> to find a solution if that exists
259.44 -> what do i mean by that let us take up
261.919 -> the problem of a magic square
264 -> so a magic square is a three by three
267.36 -> grid
268.08 -> in which you have to fill the digits
269.919 -> from one to nine
271.12 -> in such a way that sum of all the rows
274.16 -> columns and the diagonals are the same
277.36 -> now how do you go about filling this a
279.6 -> brute force approach
280.88 -> would be you start filling up the
282.8 -> numbers randomly
286 -> and then try to calculate the sums of
288 -> all the rows and columns
292.32 -> in this case we found the sums to be
294.479 -> pretty different and hence this is not
296.4 -> the solution
297.6 -> if you just keep on applying the brute
299.36 -> force method something like this
308.96 -> i just took up some random combinations
311.199 -> to just find out the sums
313.12 -> and while applying all of these
314.639 -> combinations you would eventually
317.039 -> maybe after 32 000 possibilities you
319.68 -> would land up
320.479 -> on the exact solution which would be
322.96 -> something like
326.32 -> in this case the sum of all rows columns
328.88 -> and diagonal
329.84 -> comes out to be 50. but you were able to
333.52 -> arrive at the solution
334.96 -> because a solution to this problem
337.12 -> existed
338.24 -> let me take up an example of a problem
340.08 -> to which a solution does not exist
343.039 -> so instead of a three by three magic
344.96 -> square this time
346.16 -> i have a two by two magic square and i'm
348.32 -> required to fill in numbers from one to
350.84 -> four
352.32 -> such that sum of all rows columns and
354.96 -> diagonals
355.759 -> are the same no matter how many
359.199 -> combinations i try
366.08 -> i would never reach an answer so this is
368.8 -> what makes a brute force method
370.88 -> so important if a solution to a problem
373.68 -> exists
374.4 -> you will always be able to find it using
376.56 -> a brute force method
378 -> and hence that is what makes it the
380 -> developer's favorite
381.759 -> so i would like to end this by saying
384.479 -> that as a good rule of thumb
385.919 -> you should always try to focus on a
388.08 -> brute force method first
389.44 -> to try to come up with a solution to the
391.36 -> problem you can always optimize it later
394.479 -> this would also ensure that you have
396.4 -> understood the problem statement
397.759 -> correctly
398.72 -> i hope i was able to give you some
400.56 -> insights about brute force algorithmic
402.88 -> paradigms
403.919 -> you can find a text based explanation to
406.08 -> this using the link provided in the
407.919 -> description below
409.36 -> also please let me know your thoughts
411.12 -> and suggestions in the comments below
413.199 -> thank you
Source: https://www.youtube.com/watch?v=kdTpUjd71G8