4.6 Optimal Binary Search Tree (Successful Search Only) - Dynamic Programming

[@raiakil]

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

[@Akaash449]

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.

[@ArvindKumar-fv6mv]

@@Akaash449 waste of time bro he might have changed his mail I'd so only no response

[@anubhavpandey7682]

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

[@atharvameher5880]

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

[@Akaash449]

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

[@eddiesengola4491]

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

[@i.cipher2006]

enna sollu thaliva

[@fenggeliu4241]

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)

[@debarunmukherjee9069]

This is an application of knuth optimization for Dynamic Programming

[@AKASHGUPTA4055]

Thanks!

[@mfaraday4044]

nice bro but I did not understand anything.

[@sanchitraina1346]

@@mfaraday4044 😂🤙

[@NileshwarShukla]

Well explained :)

[@chitnat]

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

[@Sahasra_Chowdary]

What an Explanation!!😮 Clear and clarity He need best lecturer award❤

[@yogesh1478]

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

[@anasjamal7206]

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

[@piyushverma826]

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.

[@softwareengineer8923]

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

[@HimanshuSharma-us1gz]

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!

[@ankushgarg2188]

Kesa gya bhai ?

[@HimanshuSharma-us1gz]

@@ankushgarg2188 Rula diya yaar, difficult exam aaya tha!

[@HimanshuSharma-us1gz]

@@abdul_bari Sir 100%, these videos contains even more, thanks sir for replying, you are legend, and god for us!

[@naziyafirdoussayyed8491]

@@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🇮🇳

[@sandeepkumar-ty3kt]

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

[@naveen_kotha]

Why did u only took k=0,but k can be 1,2 also??

[@poonawala2303]

@@naveen_kotha That was just a part of that example. Yes k can also be 1 and 2

[@deepaksehrawat970]

Thanks for formula

[@Maryam_Qureshi]

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

[@coolone5561]

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

[@helvosthecreator1920]

How did you do?

[@coolone5561]

The technical rounds went well. The process is not complete yet. I will share the result soon.

[@helvosthecreator1920]

@@coolone5561 I hope you get it, good luck! 🍀💪

[@harshitha.m.4189]

@@coolone5561 how is it going its been 2 months

[@ASHUTOSHSHARMA-us6hd]

@@coolone5561 ?? update

[@iago8200]

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

[@RoyalEXO_]

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

[@aster22380]

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

[@rajithaneerugatti4373]

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

[@souravseal7262]

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

[@srinivaskari]

Sir you have explained the concepts so well.

[@knoName5691]

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

[@knoName5691]

+Abdul Bari Yeah sir.. Visvesvaraya Technological University.. Exams for my students will be in Jun-Jul

[@syedmahasibali2324]

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

[@syedmahasibali2324]

Yeah I saw it quite easier

[@hassansyed5661]

You are a wonderful teacher. Thank you, so much for helping me to understand these concepts in an easy way.

[@P_S_PATIL]

first see the formla and then see it will be of great help 29:29

[@Diana-np5so]

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

[@prashant7622]

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.

[@lokeshagarwal6701]

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

[@rachanasingh2231]

read the book h.cormen for why's of everything

[@mohammedfalih8713]

Check leetcode site

[@samkitjain2136]

true mann. he is just writing the steps involved

[@fahadshajahan2554]

Hemanth on fire 🔥🔥🔥

[@marunkumar]

😂

[@niminijin9523]

😂

[@kanni295]

If you are a faculty in our college we always rock in the exams Your lectures are Superb sir 👏👏👏👏👏👏👏🙏🙏🙏🙏

[@kasiiragavarapu673]

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)

[@jaatharsh]

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

[@karthikadharmaraj1557]

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

[@ruturajkadam5164]

for those who are confused about the formula he has given the formula at the last of the video

[@paulz_san]

How many engineers out here, give a like.

[@gogroot9745]

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

[@donavarghese6273]

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

[@rufusmcgee4383]

Totally agree, had me scratching my head the whole time.

[@AmanSharma-me7ho]

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

[@souravkalal3831]

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

[@aniketnangare904]

Your teaching is great sir

[@charmingpetal]

14:45 top moment, thank you

[@Sahasra_Chowdary]

It's to find cost as (c[i],[r-1])+c([r+1],[j])+w(i,j) r=root

[@dheerajkafaltia8474]

Very confusing, but watching till end made it clear

[@dheerajkafaltia8474]

Ok sir, got it :-)

[@trishalarora6619]

See when u r watching this for first time, the formula used can be confusing, so either u try to think on your own, that what the formula can be, based on observations or simply skip to the end at 29:30 and note the formula and then understand. But I won't prefer latter way as it the essence of dynamic programming is to find a formula. So don't do this unless you are absolutely clueless.

[@Hari-fb4dw]

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

[@mynameisGYAN]

He did not explain the formula, and in his mind agreed that everyone must have understood.

[@iiluffytaro4835]

ABDUL BARI I LOVE YOU SO MUCH

[@gabrielmachado146]

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

[@ChandanG94805]

I did'nt Understand this really

[@yashwanthseeram3488]

No one can save you bro. Are you passed or not ? 😅😅

[@MOHIT-rg8ge]

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

[@girrajjangid4681]

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

[@hushhhhhhhhhh]

Does this work all the time? Btw tq for that, 😅

[@rb_honest]

Thank you, Sir 🙏

[@abdul_bari]

Dear, check the amount once. I think, it’s by mistake.

[@Bitofmeforyou]

Bro?? 8900?? Was it by mistake or what?👀

[@nonstopcodingcodewithadity8238]

@@abdul_bari :) sir u r best

[@nigarattar4079]

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

[@karansunchanakota6624]

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

[@ashish.Mishra00]

Everything is fine, but it would have been even better if he had given the formula earlier...👍 #JustASuggestion

[@dr.vinodkumarchauhan3454]

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

[@dr.vinodkumarchauhan3454]

Thank you very much Sir.

[@hrushikeshvazurkar]

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

[@rupalishirkande6163]

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

[@berylbose7006]

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.

[@berylbose7006]

Maybe next time. Or Sir u can add like a Part-2 for this video

[@meimei1572]

I would've given up my final exams if you were not here.

[@Dhanunjayp-fz5cj]

6:32 answer is by adding the values 22

[@haviof4420]

Ya i also noticed

[@sashankyakkali3029]

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

[@manasakuncham4547]

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

[@marinakulagina4711]

A very good explanation. Thank you.

[@AnubhavSingh-sb7xw]

cost of 1st tree will be 22 (3x1 + 2x2 + 5x3) not 18

[@harekrishnamahto6512]

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

[@TheGreatMind55]

First you have to see the formula to understand the problem 29:31 If helped Like👍

[@ritviknurchal5993]

sir the first one for frequenct check the count would be 22 not 18

[@vakhariyajay2224]

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

[@akash.manna.]

Please upload videos on Approximation algorithm and randomized algorithm. 🙏

[@yichizhang973]

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.

[@ImSoumenMukherjee]

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

[@pritomdasradheshyam2154]

yeah even i was shocked, but I guess its a minor mistake

[@Marina-pe1gx]

yeah, I was like wtf happened haha

[@dvmanjunadh3258]

yeah 15+3+4=22,Sir unexpectedly did a mistake.

[@anirudhgrack7560]

Yaa right

[@harishmax4236]

Thank you sir, for your great explanation. 🙏🙏

[@kshitijakulkarni8292]

This video is very helpful..Thank you so much sir.It is really easy to understand..

[@sgsolutions1682]

Very good teaching 😊

[@Rakeshrajeev94]

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

[@tanusharma3874]

Very well explaind thank you sir ... and it is easy to understand also i like your way of explaining sir i have a daubts in multistage

[@ryanstobbe864]

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

[@shaikparveen5312]

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

[@roopa4610]

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

[@girijayk811]

Me too same doubt if u understood let me know

[@roopa4610]

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

[@MothukuriKavya]

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

[@aradhyajain9575]

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

[@P_S_PATIL]

same problem

[@P_S_PATIL]

if any one knows pls replay

[@naklecha]

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

[@aradhyajain9575]

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?

[@BanothAnusha-hv4qn]

thank you sir for your better techer thank you a lot sir

[@techstudio9802]

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

[@aayushkumar5361]

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]

[@abhirajsingh7005]

@@aayushkumar5361 thanks dude, saved my time!!!

[@cipherwills7877]

You are truly a saviour, Tysm.

[@oppalinfo]

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)

[@abhinashjena216]

We love you ❤😊, sir

[@40_fps_gamer]

#######Hemanth on fire

[@DeepteshLovesTECH]

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.

[@naklecha]

Ideal speed for 2x speed

[@mohamedatef3526]

I noticed that the Optimal binary search tree is solved using tabulation just like matrix chain multiplication. I think this algorithm pattern can be used to find the optimal permutation of a set of weighted objects by finding the optimal permutation of one object (Trivial case), then the optimal arrangement of two objects, then the optimal permutation of three objects ( using the previous permutation of 2 objects) and so on.

[@amirhosseinmovahedi507]

just wow! it was great...

[@likhithakande2902]

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

[@yamunahanumanthu6254]

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

[@Kanukritiii]

Sir nice explanation but formula should be written first..

[@mathialagant]

6:33 15+4+3 .. 18 😂 I love his lectures by the way.

[@basharatafghan8121]

Thank u sir but if you check the calculation problem on this 6:29

[@Afzalkhan-yw8eu]

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

[@kavinilaga5719]

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

[@kaizoku712]

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

[@kvk812]

sir, your explanation was great but why did you have to hide the formula till the end? I had to wrack my brain trying to derive it manually understand it :')