4.6 Optimal Binary Search Tree (Successful Search Only) - Dynamic Programming
Вставка
- Опубліковано 26 вер 2024
- This problem is a partial, considering only successful search.
What is Binary Search Tree?
What is Optimal Binary Search Tree?
How to create Optimal Binary Search Tree by applying Dynamic Programming
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
![4.6.2 [New] Optimal Binary Search Tree Successful and Unsuccessful Probability - Dynamic Programming](http://i.ytimg.com/vi/wAy6nDMPYAE/mqdefault.jpg)
![4.6.2 [New] Optimal Binary Search Tree Successful and Unsuccessful Probability - Dynamic Programming](/img/tr.png)
Abdul Sir, I work for Microsoft in Redmond Seattle. I have 15 years industry experience, but I have never seen such crisp explanation of DP. Chained Matrix mult and this one with OST, is one of the best explanation videos on UA-cam ever,
Hi , I am Saptarshi Rudra from India. I have a passion for working at Microsoft and a good grasp over DS and Algo and years of Software Development experience. I would really love if someone like you recommend me for a Software Developer / Engineer position. I have applied for these positions for the past 2 months, but yet to receive any call. So I would be extremely grateful if you recommend me.
My full name is Saptarshi Rudra.
Thanks.
@@Akaash449 waste of time bro he might have changed his mail I'd so only no response
he told the formula to fill the table after filling the table..all the time i was thinking how he is filling.....so how can you say this is best......
@@Akaash449 Why do people wanna work in foreign I don't get it? You guys don't like it here? Proximity to family and friends don't matter to you?
@@atharvameher5880 please inform yourself before rashly posting a comment. Microsoft, Google and Amazon have local offices in the country in many states. Where is even your statement coming from!!
You can see. He teaches with love, reveals everything that needs to be mastered. Thanks Abdul. You are the best.
enna sollu thaliva
Thank you, Sir 🙏
Dear, check the amount once. I think, it’s by mistake.
Bro?? 8900?? Was it by mistake or what?👀
You are a life saver, sir! Honestly, you make this subject look so easy and fun! Hooked.
It's relatively impossible to not understand what you convey . You are a legend ❤️.
For all concepts in DAA i watch your videos .
First time when I watched your video on this concept i couldn't understand as I was bit hurried due to upcoming test in an hour .😁😁
But now here I am again for the second time , watching this concept and understanding it properly .
Note : for those of you who don't understand Abdul Bari sir , maybe you need to be relaxed and give some time to the video without any hurry . This is specially for those who come here an hour before exam 😂.
How many engineers out here, give a like.
For the recurrence relation, it would be more appropriate to write C[i, j] (for i < j) as the min {C[i, k-1] + C[k+1, j]} + w(i, j) where i
tomorrow is my viva and i am here that makes u life saver thankuh so much sir
Abdul Sir, I am a 5 year experienced Software Engineer. I have Google interview coming up on June 10th. So I started watching your algorithm videos and reached this lecture. Although I found this playlist very late after referring to a number of resources, your videos are very effective and easy to understand..
How did you do?
The technical rounds went well. The process is not complete yet. I will share the result soon.
@@coolone5561 I hope you get it, good luck! 🍀💪
@@coolone5561 how is it going its been 2 months
i never hated any subject until i encountered Design and analysis of algorithms. also my university prof who makes the ppr so difficult and calculative.
Sir I am from GGSIPU (Delhi), Today i hava ADA exam and I prepared only your videos, and kudos to your playlist thanku so much!
Kesa gya bhai ?
@@ankushgarg2188 Rula diya yaar, difficult exam aaya tha!
@@abdul_bari Sir 100%, these videos contains even more, thanks sir for replying, you are legend, and god for us!
@@abdul_bari Sir...ur videos are very helpful 😇 ur way of teaching, deep knowledge of the this subject 👏
Lots of love and huge respect 😇
From🇮🇳
You are a wonderful teacher. Thank you, so much for helping me to understand these concepts in an easy way.
Abdul Bari Sir (love) for ur passion to teach us, with every new video you raise the bar even higher,
I cannot thank you enough for this, hope u always stay healthy & wealthy :)
such an amazing explanation of optimal binary search trees!!! thank you so much for making this video!
In 6:35 it was actually 22.Also thanks for a great video!
Hemanth on fire 🔥🔥🔥
😂
😂
The video is like explaining the steps involved but i need the reason behind why we are doing ot in that way?
read the book h.cormen for why's of everything
Check leetcode site
true mann. he is just writing the steps involved
Great video so easy to understand , clear pronunciation and clear handwriting
You just saved my life in a Data Structure exam, thaks very much 😍😍😍
Wt a teaching sir..... Really no one can say like u sir..... With out disturbance....super sirrr
Formula = c[I,j]={c[I,k]+c[k+1,j]+weight}
Where k values are
C[0,3] then k values are 0,1,2
Then I=0 and j=3
Substitute the values
C[0,0]+C[1,3]+12
Hope it helps
Why did u only took k=0,but k can be 1,2 also??
@@naveen_kotha That was just a part of that example. Yes k can also be 1 and 2
Thanks for formula
Sir, I have to thank you a lot for saving me. Great content and explanation! Please keep up the good work!
I have gone through few video lectures of ur's sir..Very qualitative, easily understandable..
Thank you.. :-)
Playlist is matching VTU syllabus..
+Abdul Bari Yeah sir.. Visvesvaraya Technological University..
Exams for my students will be in Jun-Jul
@14:45 how are you getting the values using formula.....and also please tell how u calculated it in brief? Sir.....thank you.....I am finding it very difficult to understand this part.
same problem
if any one knows pls replay
Your explanation is great, but I was kind of confused about the 9:05, when you conduct j-i, I do not understand the meaning of j-i, and the meaning of l, what that expression stands for? and why we use 1 represent 10, 2 represent 20 and so on, if we use 4 represent 10 ,it is a different story.
@7:46 when he said: this is the optimal binary search tree! I made dua for this teacher.
Thank you Sir for the video. The effort you put in making these videos is really commendable.
I did'nt Understand this really
6:32 How it came 18?? It will be 22.. Right?
yeah even i was shocked, but I guess its a minor mistake
yeah, I was like wtf happened haha
yeah 15+3+4=22,Sir unexpectedly did a mistake.
Yaa right
why 2nCn / n + 1 = 5? Please help
It's (2n)Cn/(n+1) or (2n)!/(n!*(n+1)! and you get 6C3/4 = 5
@@recensionemthanks!!
sir,could you explain how to generate a tree from the data at the end?
14:45 top moment, thank you
Sir you have explained the concepts so well.
Please clarify my query..
1. when j-i =1 -> Here we calculated the cost for all the 4 keys (10, 20, 30 40)
2. when j-i =2 -> Why do we only take these 3 combination (10, 20) (20, 30) (30, 40) only ??
3. As we already know to select 2 keys out for keys is 4C2 => 6
4. So why we dont consider (10, 40) (10, 30) (20 40)
5. |||y for 3 pairs and so on ??
Could you please clarify this point .. ?? Thanks in Advance..
how you have chosen the child of r(0,4) are r(0,2) and r(3,4). plz explain
because as the matrix he created , the root for r(0,4) is 3...thus, k =3 here...
so the child will become for c[i,j] ---> c[i,k-1] and c[k,j]
@@aayushkumar5361 thanks dude, saved my time!!!
wonderfully taught.
but u should have explained formula in the start and not revealed it at the end.
that wud have made it better
Totally agree, had me scratching my head the whole time.
I like ur way of teaching... Ur teaching is very clear sir about the topic
a quick shortcut for exam or observation just add the corresponding element from the row and column u are supposed to find....
for example u want to find
c[0,3]=(0,0)+(3,1),(0,1)+(3,2),(0,2)+(3,3) hope u found the pattern...
Thank you sir it's a very understandable example 🙏🙏
A very good explanation. Thank you.
ur videos r great sir...thank u for saving us...gitam students love u a lot
Sir's explanation is great, i just love his explaining techniques.
just wow! it was great...
ABDUL BARI I LOVE YOU SO MUCH
For this to work keys should be in sorted order or not?
6:32 answer is by adding the values 22
Ya i also noticed
Hi Sir,
Really Informative, great use of examples . I am able to grasp the content so well..
Just a quick suggestion, could you also device the algorithm or pseudo-code at the end, to help us get a more generalized view on solving the problem.
Maybe next time. Or Sir u can add like a Part-2 for this video
We love you ❤😊, sir
Sir, why are we adding the weight of all the keys in the formula?.....How is it related to the formula and the BST if we consider 2 nodes BST or 3 nodes BST?
Since you aren't considering the "zeroth" level when you split the tree into left and right subtrees (C[i, k-1] on the left and C[k, j] on the right), you need to add the frequency for each node at the end.
Thank you sir, for your great explanation. 🙏🙏
Sir, first of all, thank you very much for the wonderful content.
Sir, it looks like you have not covered some contents from Algorithms, which is generally part of the syllabus. So I request you to cover the following contents also:
Lower-Bound Theory:
Introduction to Algebraic problems, Introduction to lower bounds, Comparison Trees,Techniques for Algebraic problems, Some Lower Bounds on Parallel Computation
Thank you very much Sir.
It's some what difficult problem to solve but this video made it easy for implementing
Yeah I saw it quite easier
sir the first one for frequenct check the count would be 22 not 18
Your teaching is great sir
This is great video but in this video 6: 29 part of video is some mistake cost of 1st tree is 22 due to given frequency but you write 18
Sir which ide you use for coding?
Thank you very much. You are a genius. 👍👍🔝🔝🙏🙏👌👌
You are truly a saviour,
Tysm.
I observe one thing in the above problem that consider the frequencies in descending order and then form binary search tree. We get answer(you need cost then find the cost from tree)
13:30...Formula is C[i,j]=C[i,k-1]+C[k,j]+w[i,j]... i and j value and weight.. u know..now value of K..😆😆
For value of k.
10 is 1st so key no. of 10 is..k=1...
20 is 2nd so key no. of 20 is.k=2..
30 is 3rd so key no of 30 is..k=3..
40 is 4th so key no of 40 is k=4..
..Now to select k ..u have to take root node key no..if ur root node is 10 then k=1..if ur root node is 20 then k=2..so on..
C[0,2] that first 2 numbers..
10 and 20..
C[i,j]=C[i,k-1]+C[k,j]+w[i,j]
FOR 10..K=1..
C[0,2]={C[0,0]+c[1,2]}+w[0,2]
=0+2+4+2
=8
FOR 20..K=2..
C[0,2]=C[0,1]+C[2,2]+w[i,j]
=4+0+4+2
=10..
U know which one to select :)
If you are a faculty in our college we always rock in the exams Your lectures are Superb sir 👏👏👏👏👏👏👏🙏🙏🙏🙏
Thank you sir
It was so helpful
Amazing sir
Brilliant
sir how you take r(0,2),r(3,4) as child of 3?
yes sir, why did we do that?! Please answer ASAP. I have test tom for this!!!!!!!!!!!!!
great video! Explain things so well!
this video is little confusing to me. it is not clear to me , how are we getting the formulas.
But as an alternate solution, we could have sorted the input as per the frequency and then inserted one by one into a BST ?
pradip biswas i got same prblm little bit confusion how to make formula 😇
its not clear through video without formula ..... it might better if you wrote that before applying
Excuse sir! First of all great explanation but I didn't understand the last part where you construct the tree. I'm unable to understand the way you are diving the branches.
Sir, why should we multipy number of comparisons with frequency🤔?
Sir, Thank you so much for the video. Best explanation I have seen. Expecting more videos.
Thank u so much sir. How c(0,0) in the first step i didn't understand
how come 15+3+4=18 iy is 22 right????
Big Thanks sir ......you are awesome.
I want to salute u sir for your efforts in making such amazing videos. It made all my concepts clear. Thank you sir
Can anyone explain from 27:45
How he created the tree
Thank u sir but if you check the calculation problem on this 6:29
We can also directly generate tree by taking max frequency key as an root.
Does this work all the time?
Btw tq for that, 😅
you are just showing the method, but not why it is done so..
Why we are following the hectic process if we insert them in a tree according to their frequency value then the result will be same like you are solving it with the formula
Your teaching is extremely awesome❤️ but I didn't understand how you split r[0,4] as r[0,2] and r[3,4] while writing tree
Me too same doubt if u understood let me know
@@girijayk811 even I didn't understand properly but what I thought was 26 was least ryt how did you get 26 it's by adding C[0,2] + C[3,4] + 15 therefore we will split r[0,4] as r[0,2] and r[3,4] and again we will split r[0,2] on the same basis..check what is the least number in r[0,2] then split those two... I tried my best to make you to understand 😃 if you still don't understand feel free to ask 😊
@@girijayk811 [0,4] means the keys which we take are 10,20,30,40 and when we draw trees for these keys we get different trees having root 10,20,30,40 so when we split c[0,4] to c[0,2],c[3,4] it is representing the trees which are having 30(whose frequency is 3) as root.
Very good teaching 😊
c[i,j]=min{c[i,k-1]+c[k,j]+w[i,j]} where k=i+1 to j and w=sum of frequencies
f(n) = 16n3 +10 n log n and g(n) = 8758 n2 log n + 9248 n2
Sir, which function has greater value f(n) or g(n)
I would've given up my final exams if you were not here.
The video discusses the concept of an optimal binary search tree, where the keys have different search frequencies. The dynamic programming approach is used to find the optimal tree organization that minimizes the total search cost.
Key moments:
00:00 Binary search trees are efficient for searching keys with a time complexity of log n. Different binary search trees can be formed for a given set of keys, impacting the search cost.
-Binary search trees provide efficient key searching with a time complexity of log n, based on the tree height.
-Different binary search trees can be formed for a set of keys, affecting the number of comparisons needed for key search, leading to a balanced binary search tree.
-Optimal binary search trees consider the frequency of key searches, prioritizing more frequently searched keys, impacting the overall search efficiency.
06:04 The video discusses optimizing binary search trees based on key frequencies. Dynamic programming is used to find the optimal organization for keys with different frequencies.
-Explanation of how to determine the optimal binary search tree organization based on key frequencies using dynamic programming.
-Detailed step-by-step process of filling values in a table to calculate the cost of different binary search tree organizations.
12:43 The video explains a process of finding the minimum cost of forming a binary search tree using dynamic programming and frequency values. It demonstrates selecting keys, calculating costs, and determining the optimal arrangement of keys.
-Demonstrating the calculation of costs and comparisons for different key selections in forming a binary search tree.
-Exploring the process of selecting keys and frequencies to determine the optimal arrangement for minimizing the cost of the binary search tree.
-Illustrating the expansion of the process to consider three keys at a time to further optimize the arrangement and minimize the cost of the binary search tree.
19:18 The video discusses the concept of finding the optimal cost of a binary search tree using a formula based on frequencies and weights of keys. It demonstrates the calculation process step by step.
-Calculation of optimal cost for different key possibilities using a formula based on frequencies and weights.
-Determining the root key for optimal cost calculation and selecting the minimum cost among different possibilities.
-Expanding the analysis to consider more keys and calculating the optimal cost for a larger set of keys in a binary search tree.
27:40 The video explains the concept of an optimal binary search tree using a formula to minimize the cost of searching based on frequency. It demonstrates how to apply the formula for optimal tree construction.
-Explanation of the concept of an optimal binary search tree and its importance in minimizing search costs based on frequency of search.
-Demonstration of the formula for constructing an optimal binary search tree to minimize search costs and how to apply it effectively.
How do we come up with the formula for the number of binary search trees for a given number of vertices?
please someone can explain why the formula here on the board says that c(i, k-1) + c(k, j), not c(i, k-1) + c(k+1, j)? we are looking for the root so is it not c(i, k-1) + c(k+1, j), is it? I want to understand...
thank you sir for your better techer thank you a lot sir
for those who are confused about the formula he has given the formula at the last of the video
Explanation part was good, but as dint know the formula earlier it was a bit confusing in between...
If we represent this in the form of an array then what exactly does the organisation mean and how they help + what do you mean by cost is it how easily a frequent element can be searched?
Okay this is me replying to myself to watch the next video 🙂
How did sir calculated probability of n keys , from where did the formula came ?
Ideal speed for 2x speed
i have doubt in the formula i didn"t understood the formula
First you have to see the formula to understand the problem
29:31
If helped
Like👍
Watch out the following playlist.
ua-cam.com/video/PU4fgVbzIUs/v-deo.html
You will find the best and clear explanation for this question there. That will prepare you for the other related problems such as chain multiplication.
Very confusing, but watching till end made it clear
Ok sir, got it :-)
Sir why are we checking "l = j-i=0" 9:00 ?
Thanks for telling us how the formula works :)))))))
Could someone pls tell me how he got 5 over there? I am not able to understand how he solved that formula, searched on youtube as well but could not get anything.
13:45 how does c(0,0) c(1,2) came pls help
@Virendra Negistill that part is unclear
In range of (0,2)
Two value are coming 1 and 2
So possible value= MIN ((C(0,1)+C(2,2)+C(0,0)+C(1,2)))
+W(0,2)
= ANSWER
HOPE U UNDERSTAND
Formula = c[I,j]={c[I,k]+c[k+1,j]+weight}
Where k values are
C[0,3] then k values are 0,1,2
Then I=0 and j=3
Substitute the values
C[0,0]+C[1,3]+12
Hope it helps
@@sandeepkumar-ty3kt values of k shouldn't include i . Then how come the values of k are 0,1,2?
I am also confused about 2nCn / n + 1 = 5. What exactly is Cn?
is it 2*n*Cn or it is Cn to power of 2n?
if it is 2*n*Cn/(n+1) and n =3, then Cn = 20/6 and I don't get what this might represents.
it comes from the combination law. He meant combination of (2n,n) and it is written like C(2n,n) such that C(y,x)= y!/(x! * (y - x)!).
where y! is called "y factorial" such that y! = y*(y-1)*(y-2) .....(3)*(2)*(1)
so 3! = 3*2*1 = 6
You can find more about it here:
www.mathsisfun.com/combinatorics/combinations-permutations.html
Brief explanation of combination law:
if you want to select 2 objects from a list of three elements such that the order doesn't matter you use this combination to get all the possible configuration law.
EX:
what are possible configuration to select 2 objects from list containing 3 elements such this list: {a,b,c} ??
all possible configurations are: {a,b}, {b,c},{a,d}
and the number of all possible configuration are 3
and we still can get this number by using the combination law:
C(6,3) = 3!/(2! * 1!) = 3*2*1/( (2*1) * (1) ) = 3
@@Heshammehrem I was confused on this as well. Thank you for the information!