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 KZfaq ever,

For those who don't understand the formula here is an explanation. It took a while for me too. Everytime you try to add the nth node on to a tree with n - 1 nodes, you have to pick a root point k and k - 1 nodes on the left tree, n - k nodes on the right tree. k - 1 and n - k each as INDIVIDUAL TREE should already be calculated previously according to the table, so you just have to find where those are on the table which is at c[0, k - 1] and c[k, n] Look now we have the rank of 2 trees and 1 single root, to push the left or right tree into a sub tree you need add one level on each of their node therefore add the entire weight of the tree The combined tree with k as root have: Rank(k) = Rank(left) + Rank(left) + weight(left) + weight(right) + weight(root) = Rank(left) + Rank(right) + weight(0 - n) = c[0, k-1] + c[k, n] + w(0, n)

You can see. He teaches with love, reveals everything that needs to be mastered. Thanks Abdul. You are the best.

You are a life saver, sir! Honestly, you make this subject look so easy and fun! Hooked.

Thank you Sir for the video. The effort you put in making these videos is really commendable.

such an amazing explanation of optimal binary search trees!!! thank you so much for making this video!

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 :)

ur videos r great sir...thank u for saving us...gitam students love u a lot

great video! Explain things so well!

Great video so easy to understand , clear pronunciation and clear handwriting

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 😂.

you're amazing thank you so much for your effort

Sir, I have to thank you a lot for saving me. Great content and explanation! Please keep up the good work!

You just saved my life in a Data Structure exam, thaks very much 😍😍😍

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

The video is like explaining the steps involved but i need the reason behind why we are doing ot in that way?

sir,could you explain how to generate a tree from the data at the end?

Wt a teaching sir..... Really no one can say like u sir..... With out disturbance....super sirrr

6:32 How it came 18?? It will be 22.. Right?

tomorrow is my viva and i am here that makes u life saver thankuh so much sir

Thanks for telling us how the formula works :)))))))

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!

Sir's explanation is great, i just love his explaining techniques.

Thank you, Sir 🙏

You are truly a saviour, Tysm.

I have gone through few video lectures of ur's sir..Very qualitative, easily understandable.. Thank you.. :-) Playlist is matching VTU syllabus..

Sir, Thank you so much for the video. Best explanation I have seen. Expecting more videos.

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.

Thank you sir, for your great explanation. 🙏🙏

sir root iam confuse to finding in root value example if i taken the value is 4, then how to find the value of root is [0,3] & [4,4] plese explane me

I want to salute u sir for your efforts in making such amazing videos. It made all my concepts clear. Thank you sir

@Abdul Bari - Sir How did you get 4(3,4) as 4 not 3 ? can you please explain

before you start filling the matrix , please mention what is the behind filling like that ..for example.....telling that j-i=1 but what is the motive of doing that because when i will get a problem i will not start thinking like first i-j=1 then i-j=2 ..in fact i will start thinking it practically why i need to do that then converting it into matrix .l have seen you explaining like this before also . al though everytime i am able to figure out why it is needed bt still start with the motive why we need to proceed like that.

Thank you sir it's a very understandable example 🙏🙏

A very good explanation. Thank you.

@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.

@7:46 when he said: this is the optimal binary search tree! I made dua for this teacher.

How do we come up with the formula for the number of binary search trees for a given number of vertices?

If you are a faculty in our college we always rock in the exams Your lectures are Superb 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..

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 so much for the explanation! It helped me a lot!

how you have chosen the child of r(0,4) are r(0,2) and r(3,4). plz explain

Sir can you please explain how the idea of such formula strikes. Same case even in knapsack problem. Please help sir.

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..

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

do we need to sort the keys?

In 6:35 it was actually 22.Also thanks for a great video!

How did sir calculated probability of n keys , from where did the formula came ?

I like ur way of teaching... Ur teaching is very clear sir about the topic

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.

Thank finally I understand it :D

Sir , I had a dought that what if the values of q1,q2 .....are not given 🤔🤔🤔🤔🤔🤔🤔🤔

Sir you have explained the concepts so well.

Using what logic do you construct the tree at the last?

Could you explain the working of that formula c[i,j]

For this to work keys should be in sorted order or not?

Thank you very much. You are a genius. 👍👍🔝🔝🙏🙏👌👌

what's the logic behind the w (weight) term?

sir how you take r(0,2),r(3,4) as child of 3?

We can also directly generate tree by taking max frequency key as an root.

Dear sir, are you going to take session on data structure and advanced data structures like you give session on algorithm . It is wonderful.

great content ! thank you

This is the best explanation I have found on You tube thanks

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?

I did'nt Understand this really

Hello sir..... After the tree formation when I cross checked then it's giving cost as 31 instead of 26.......why?

how to calculate [2.4 ] using formula

Sir which books you have referred to gain this much knowledge ❤️

I don't think for smaller values we need to use this much big formula, by seeing frequencies we can generate OBST.

sir , can you explain the algorithm for bst

It's some what difficult problem to solve but this video made it easy for implementing

Sir which ide you use for coding?

Amazing explanation!!!! Thank you so much!

Why is this Method so much more complicated in comparison to building the Huffman Code? Cant we just combine always the nodes with least frequency to get the tree?

how come 15+3+4=18 iy is 22 right????

Sir in last step how did you draw that tree

Your teaching is great sir

wonderfully taught. but u should have explained formula in the start and not revealed it at the end. that wud have made it better

Thanks Abdul, you the real g, if you need a homie, hit me up

can anyone explain.. how did he get c[0,1]+c[2,2] at 14:43

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 ?

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)

Hi Sir, What is time complexity?

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.

Thank u so much sir. How c(0,0) in the first step i didn't understand

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)

Sir how did u get child of root 3 as r[0,2] and r[3,4]??

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.

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?

For l = j - i => 3, This possibility is true or not, Where 20 is root node, with left child as 10 and 10's right child as 30? If yes, then there are more than 5 different ways forming a Binary tree.

Explanation part was good, but as dint know the formula earlier it was a bit confusing in between...

Big Thanks sir ......you are awesome.

Nice explanation sir aapke sabhi videos bahot hi ache se samjh ate hain thanks

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

Learning this is easy, but how do we figure out what values to take and how to fill the table when given with a new dp problem?

How many engineers out here, give a like.

in 23:10 why did he take c[1,1] instead of c[1,0]?

sir how to write down the formula