Optimal Binary Search Trees with Example in Hindi #2 | Dynamic Programming

[@aalishanhunzai]

amazing video corrections: c(0,4) 19 with root 3 c(1,4) 11 with root 4 graph is: r(0,4) / 3 \ r(0,2) r(3,4) / 1 \ / 4 \ r(0,0) r(1,2) r(3,3) r(4,4) / \ r(1,1) r(2,2) result: 15 / \ 5 20 \ 3

[@adultlucifergremory5435]

Bhai last me 10 hai 3 ki jagah

[@SonuYadav-ub1zx]

Cost (1,4 ) is 11 with root 4 & c(0,4) is 19 with root 3

[@kumarabhinav1577]

*Correction* C[1,4] is 11 and root is 4 C[0,4] is 19 and root is 3 //it's okay we're here to learn the concept.

[@User-student-404]

best comment in the comment section 👍👍

[@aalishanhunzai]

iska phir jo vertexes bana rahe wo zyada arha ha

[@thefuntech2810]

answer is wrong I filled all blocks C(1,4)=11 C(0,4)=19 And root is vertex 3

[@manjeet_manu]

BUT ISKA TREE KAISE BANEGA

[@thefuntech2810]

@@manjeet_manu wahi process follow karo

[@mahiransh9894]

Bhai final answer bta de yrr... Kll paper hai...!!!

[@thefuntech2810]

@@mahiransh9894 video poori dekhlo phir apne aap samaj mai aa jayega UP se ho kya AKTU University ?

[@jaxim8520]

C[0,4]= 14 Shi h C[0,4] ka answer

[@devaganeshnair5883]

C[1,4]= 11 root 4 C[0,4]= 19 root 3 15 /\ 5. 20 \ 10

[@rahulray7650]

totally correct👌👌👌👌

[@AnkitSingh-ye4xj]

crct 👍

[@yogeshwarimarathe2277]

How this 15 came as a root?

[@jacobabineshjoseph2523]

@Mayur Chipade it's 2 bro if you see

[@amanmourya6078]

marked as best answer.

[@ombothre2350]

Final Optimal BST :- 15 / \ 5 20 \ 10

[@vishalghule4807]

Tree in video is wrong?

[@vishalghule4807]

There he is starting from 5 then 20 , 15 ,10

[@rajat129]

@@vishalghule4807 yes it is wrong in video , this is right answer

[@vishalghule4807]

@@rajat129 ok thanks 👍

[@alinajaved2165]

Final Optimal BST :- (0,4) 15 / \ r(0,0) 5 20 r(1,4) \ 10 how 5 came here becoz on r(0,0) it will stop

[@hanzalamansuri9996]

Formula : C[i][j] = C[i][k] + C[k+1][j] + W[i, j] With k = (1

[@hanzalamansuri9996]

For c[1][2] , k = 2... Because k is between i

[@ankitgitm]

The entry of (0, 4) will be 21 with root 3 Entry for (1,4) will be 11 with root 4 The final answer will be changed accordingly According to me, The final answer will be Root (15) / \ 5 20 \ 10

[@ashakharkwal548]

thankyouu

[@deeepsss]

Bro, mujhe tho (0,4) ka 16 aaya hai, aur root 3. If possible kuch recall kar sakte ho kaisa aaya?

[@shavnamsharma8340]

True

[@sayalis_rangoli_art]

Right

[@tdm2146]

💯% right...

[@Morris64]

General formula for calculating the minimum cost is: C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)

[@umesh6245]

what is K here?

[@rajbelwal1634]

@@umesh6245 root vertex

[@coderx7177]

Bhaiya bohot sahi video tha apne jo choti choti tricks batai isse remember krne k lie voh lajvab thi mene kai sare videos dekhe pr kuch nahi smjha apne har ek step achhese bataya hai bohot bohot dhanywaad ❤️.

[@Lastmomenttuitions]

Welcome

[@aguyfromindia]

Thankyou sooo much you saved my whole life in just 30 mins :) . . . . . . . . . recommendation: go for only concept not for calculation.

[@Lastmomenttuitions]

Welcome

[@prakashnavin6245]

thank you so much last moment tuition you guys are doing a really great job today is my final exam and after watching your video at 4: 35 am I got the concept very clearly. please keep uploading such informative video #engineers #btech

[@neeketasaini3695]

Sir the value of c(1,4)=11 with root Vertex 4.please let u clear this doubt.

[@navjyoti3075]

Bhai apko pranam kitna acche seh apne samjhaya ❤️ mera abhi 4 sem m ei topic h smj nhi arha tha toh search kia aur baki smj a gya pura 😁😁 thnks bhai

[@anupsingh9978]

Cost of [1,4] =11 because weight of w[1,4] =7 So 7 + 4 = 11 And 11 is answer not 4 ok students don't be confused.

[@zilesingh6349]

Sir aapse (1,4) mistake ho gye hai usme aapne weight ko add nahi kiya Vo 11 hona tha uske vajah se (0,4) b galat ho gya . But sir aapne bahut acha samjaya mera exact tree create huya hai thanku so much...

[@shivamtiwari9040]

The mistake you made in calculation of c(1,4) made me recheck all my calculations and understand the concept more clearly.

[@mihirnaidu5211]

Kya hi samjhae aap bhaiya luv u upar wala aapko bohot khushiyaan de tysm !!!!

[@Lastmomenttuitions]

Thanks

[@goonbanode7988]

C[0,4] is 14 is correct because we have to select the least value only c[1,4] is 11

[@codingmania8856]

Tree and answer are wrong because C[1,4] is 11 and C[0,4] is 19. so the root will be 3.

[@EnglsihCommByNawaz]

Exactly

[@sayantanbandyopadhyay7803]

exactly bro...

[@chandamourya7101]

Par root 3 .. 2 bar aaya hai tho kisa tree build Kara

[@educationsingh2038]

True

[@Techie_jay03]

Ha na bhai..main tension main agya tha😅😅

[@sp8976]

GAJAB EXPLAINATION 🔥

[@Error-zp3bn]

Cost (1,4) mai w(1,4) ki value add nhi ki hai

[@zohakhan1934]

Was method rightly explained ? Should I consider it for my exam

[@63yashshimpi79]

Q: Construct OBST for the given instances, If N=4, Set of Identifiers {a1, a2, a3, a4}= {do, if, int, while }, P(1:4)={p1,p2,p3,p4}={3,3,1,1} and Q(0:4)= {q0,q1,q2,q3,q4}={2,3,1,1,1} Construct a Optimal Binary Search Tree . 👆👆👆👆👆👆 koi muze iss question mese VERTEX , KEY ,& FREQUENCY batao plzzzzz

[@harsshadshivsharan.6539]

To construct an optimal binary search tree (OBST) for the given instances, we can use the dynamic programming approach. Let's go through the steps to construct the OBST: Step 1: Initialize the tables and arrays. Create two-dimensional tables cost and root of size (N+2) x (N+1). Create an array P of size (N+1) to store the probabilities. Create an array Q of size (N+2) to store the cumulative probabilities. Step 2: Calculate cumulative probabilities. Initialize Q(0) = 0. For i = 1 to N+1: Q(i) = Q(i-1) + P(i-1). Step 3: Initialize the cost table. For i = 1 to N+1: cost(i, i-1) = Q(i) + Q(i-1). Step 4: Build the optimal binary search tree. For L = 1 to N: For i = 1 to N-L+1: j = i + L - 1 cost(i, j) = infinity For r = i to j: c = cost(i, r-1) + cost(r+1, j) + sum of P(i:j) + sum of Q(i:j+1) If c < cost(i, j): cost(i, j) = c root(i, j) = r Step 5: Print the optimal binary search tree. Call a recursive function printOBST(root, i, j): If i > j: Print "d" + (j+1) Else: Print "if" + (root(i, j)) + " (d" + (root(i, j)-1) + ", " + "d" + (root(i, j)+1) + ")" Recursively call printOBST(root, i, root(i, j)-1) Recursively call printOBST(root, root(i, j)+1, j) Now, let's apply these steps to the given instances: Step 1: Initialize the tables and arrays. N = 4 Set of Identifiers: {do, if, int, while } P(1:4) = {3, 3, 1, 1} Q(0:4) = {2, 3, 1, 1, 1} Step 2: Calculate cumulative probabilities. Q(0) = 0 Q(1) = Q(0) + P(0) = 0 + 3 = 3 Q(2) = Q(1) + P(1) = 3 + 3 = 6 Q(3) = Q(2) + P(2) = 6 + 1 = 7 Q(4) = Q(3) + P(3) = 7 + 1 = 8 Step 3: Initialize the cost table. cost(1, 0) = Q(1) + Q(0) = 3 + 2 = 5 cost(2, 1) = Q(2) + Q(1) = 6 + 3 = 9 cost(3, 2) = Q(3) + Q(2) = 7 + 6 = 13 cost(4, 3) = Q(4) + Q(3) = 8 + 7 = 15 Step 4: Build the optimal binary search tree. For L = 1: For i = 1: j = 1 + 1 - 1 = 1 cost(1, 1) = infinity For r = 1 to 1: c = cost(1, 1-1) + cost(1+1, 1) + P(1) + Q(1:2) If c < cost(1, 1): cost(1, 1) = c root(1, 1) = 1 For L = 2: For i = 1: j = 1 + 2 - 1 = 2 cost(1, 2) = infinity For r = 1 to 2: c = cost(1, 1-1) + cost(1+1, 2) + sum of P(1:2) + sum of Q(1:3) If c < cost(1, 2): cost(1, 2) = c root(1, 2) = 2 For i = 2: j = 2 + 2 - 1 = 3 cost(2, 3) = infinity For r = 2 to 3: c = cost(2, 2-1) + cost(2+1, 3) + P(2) + Q(2:4) If c < cost(2, 3): cost(2, 3) = c root(2, 3) = 3 For L = 3: For i = 1: j = 1 + 3 - 1 = 3 cost(1, 3) = infinity For r = 1 to 3: c = cost(1, 1-1) + cost(1+1, 3) + sum of P(1:3) + sum of Q(1:4) If c < cost(1, 3): cost(1, 3) = c root(1, 3) = 2 For i = 2: j = 2 + 3 - 1 = 4 cost(2, 4) = infinity For r = 2 to 4: c = cost(2, 2-1) + cost(2+1, 4) + sum of P(2:4) + sum of Q(2:5) If c < cost(2, 4): cost(2, 4) = c root(2, 4) = 3 For i = 3: j = 3 + 3 - 1 = 5 cost(3, 5) = infinity For r = 3 to 5: c = cost(3, 3-1) + cost(3+1, 5) + sum of P(3:4) + sum of Q(3:5) If c < cost(3, 5): cost(3, 5) = c root(3, 5) = 4 Step 5: Print the optimal binary search tree. Call printOBST(root, 1, 4): Print "if3 (d2, d4)" Call printOBST(root, 1, 2): Print "do (d1, d2)" Print "int (d3, d4)" Call printOBST(root, 4, 4): Print "while (d5)" The optimal binary search tree is as follows: Copy code if3 / \ do while int Note: The "d" + (index) represents a dummy node.

[@ashwinikakade3418]

1 number shikavle tumchyamul maze 6 marks fix zale sir....👍🙏

[@rakshitmehra9199]

C(1,4)=11

[@kunalbudhiraja7761]

Literally cramming of algorithm

[@SalimShaikh-fx4kz]

impressed bhai,after watching too many videos ,this clearifies the concept

[@Lastmomenttuitions]

Thanks

[@manjirikulkarni805]

c(1,4)=11

[@shreechatane9215]

Thank you bro very useful content ✌🏻

[@anupsingh9978]

And cost of [0,4] will be 19

[@spiritual487]

[1,4] is 14

[@krishi2760]

Excellent explanation but values are wrongly calculated

[@sahilchoudharypublicvlogs4456]

how you calculated (1,3) please tell

[@saurabhkumarkardam8782]

Why did u not fill the all block ?

[@shahjee-iy4gu]

You are genius

[@unknownman1]

tum jio ek lakh saal :)

[@meenakshirawat6213]

[1,3]=4. is it right??? my answer is different

[@devanshgupta2772]

answer is wrong I filled all blocks C(1,4)=11 C(0,4)=19 And root is vertex 3

[@devanshgupta2772]

Final Optimal BST :- 15 / \ 5 20 \ 10

[@satyammahajan2773]

In C (1,3) it's coming 7 instead of 4 with root vertex 3

[@deftme5440]

Don't include weight of 1 in the calculation of w(1,3), therefore weight will be 1+2 =3 , so calculation part will be , C(1,3)=c(1,2)+c(3,3)+3 C(1,3)= 1+0+3=4

[@kushalbhatt6266]

thanks bro

[@djagadeshwar7983]

You not added w(1,4) in cost(1,4)

[@awesomechintz7076]

Bhai h tu mera😘

[@studywarriors-i1h]

besttttt ever

[@amrutkajave6787]

c(1,4) = 4 ❌

[@amrutkajave6787]

hence ans is wrong!

[@yunusahmed5799]

(1, 4) = 11 with root 4 and (0,4)=19 with root 3

[@suryakantasundaray932]

any doubt?? ask me

[@CSEBivekKumarSahNirala]

thank you sir

[@anshagarwal5999]

waah kya ladka hai

[@danish_gaming01]

Good 👍👍👍👍👍

[@siddhantking7659]

itne time me to 3 question solve hojayenge

[@rockiggo]

Tqs sir

[@amanchaurasiya3065]

Thanks bhai

[@sumitsharma5058]

Dislike to missed the typical part of the video..

[@aishwaryatiwari3618]

what have u done....its a blunder....optimal weight is 19 not 14....tree is fully wrong...check before uploading

[@Zmayur143]

Sir, can you please tell me what if the vertex is starting from 0 rather than 1? Means in your example vertex are 1,2,3,4 but what if they are 0,1,2,3? I'm very confused in this situation. I can't ignore the previous value because of that 0.

[@mihirnaidu5211]

Then we will take min nd consider 0s all values in (0,1) nd soo on!!!

[@poojapatil4584]

Aapne sare box fill q nhi kiye

[@thefuntech2810]

Badiya video hai ;)

[@69miXxX]

Explain dynamic programming approach and apply it to construct optimal binary search tree using Huffman coding for weights given below (2,3,5,7,9,13)

[@amrit8445]

Half part kyu ni solve kiya apne

[@suryakantasundaray932]

doubt?

[@nikhilmatta6686]

why we are not considering keys here 😅

[@nikhilmatta6686]

can anyone please explain

[@g13arpitrajput76]

Notes khaan h sir ...koi link nhi h notes ka

[@RaveenRajSingh]

Answer is wrong sir

[@khedkarsonali1680]

answer is wrong...

[@saurabhkumarkardam8782]

Bhai apne ye neeche ke blocks kyon nhi fill kare

[@sumitsharma5058]

Coz there u got (0,0) vertices and it means value is nothing. Hope u understand

[@OmkarBcw]

Bhai kaunsa answer sahi hai bata do kal exam hai 🥲

[@OmkarBcw]

answer . 15 / \ 5. 20 \ 10

[@swapnilpatel9831]

Wrong answer brooh!

[@djagadeshwar7983]

It's wrong solution

[@racingarena04]

khud confuse h

[@VARINDERSINGH-zn8mp]

not a proper explanation does not tell how to fill block c[1,3] and c[2,4] , because of that man i waste my 3 hour ,dislike

[@prajwalmehare_]

barabar nahii samjta bhaii , thoda explanation , writing ka tarika improve karo 😶😒😑😪

[@Your_father78678]

Isko kuch ata nahi hai buus kuch bhi samjha raha hai

[@Your_father78678]

Are acche se samjha phela khud Sikh ke aa

[@mfaraday4044]

Thank you bhau

[@bhushanvashist7556]

Thanks 👍

[@Lastmomenttuitions]

Welcome

[@shishpal512]

thanks bhai

[@Lastmomenttuitions]

Welcome