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
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 ❤️.
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
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...
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
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.
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.
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
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
Bhai last me 10 hai 3 ki jagah
*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.
best comment in the comment section 👍👍
iska phir jo vertexes bana rahe wo zyada arha ha
Cost (1,4 ) is 11 with root 4 & c(0,4) is 19 with root 3
answer is wrong I filled all blocks
C(1,4)=11
C(0,4)=19
And root is vertex 3
BUT ISKA TREE KAISE BANEGA
@@manjeetmanu4547 wahi process follow karo
Bhai final answer bta de yrr...
Kll paper hai...!!!
@@mahiransh9894 video poori dekhlo phir apne aap samaj mai aa jayega
UP se ho kya AKTU University ?
C[0,4]= 14
Shi h C[0,4] ka answer
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
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
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 ❤️.
Welcome
Thank you bro very useful content ✌🏻
Sir the value of c(1,4)=11 with root Vertex 4.please let u clear this doubt.
Literally cramming of algorithm
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
thankyouu
Bro, mujhe tho (0,4) ka 16 aaya hai, aur root 3. If possible kuch recall kar sakte ho kaisa aaya?
True
Right
💯% right...
impressed bhai,after watching too many videos ,this clearifies the concept
Thanks
Cost (1,4) mai w(1,4) ki value add nhi ki hai
Kya hi samjhae aap bhaiya luv u upar wala aapko bohot khushiyaan de tysm !!!!
Thanks
Thankyou sooo much you saved my whole life in just 30 mins :)
.
.
.
.
.
.
.
.
.
recommendation: go for only concept not for calculation.
Welcome
how you calculated (1,3) please tell
C[1,4]= 11 root 4
C[0,4]= 19 root 3
15
/\
5. 20
\
10
totally correct👌👌👌👌
crct 👍
How this 15 came as a root?
@Mayur Chipade it's 2 bro if you see
marked as best answer.
Thank you bhau
General formula for calculating the minimum cost is:
C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)
what is K here?
@@umesh6245 root vertex
1 number shikavle tumchyamul maze 6 marks fix zale sir....👍🙏
The mistake you made in calculation of c(1,4) made me recheck all my calculations and understand the concept more clearly.
thank you sir
Badiya video hai ;)
Why did u not fill the all block ?
tum jio ek lakh saal :)
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...
You are genius
Notes khaan h sir ...koi link nhi h notes ka
Bhai h tu mera😘
Tqs sir
Final Optimal BST :- 15
/ \
5 20
\
10
Tree in video is wrong?
There he is starting from 5 then 20 , 15 ,10
@@vishalghule4807 yes it is wrong in video , this is right answer
@@rajat129 ok thanks 👍
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
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
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.
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.
Thanks 👍
Welcome
Good 👍👍👍👍👍
Was method rightly explained ?
Should I consider it for my exam
besttttt ever
Tree and answer are wrong because C[1,4] is 11 and C[0,4] is 19. so the root will be 3.
Exactly
exactly bro...
Par root 3 .. 2 bar aaya hai tho kisa tree build Kara
True
Ha na bhai..main tension main agya tha😅😅
c(1,4)=11
thanks bhai
Welcome
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.
Then we will take min nd consider 0s all values in (0,1) nd soo on!!!
Aapne sare box fill q nhi kiye
C(1,4)=11
C[0,4] is 14 is correct because we have to select the least value
only c[1,4] is 11
Yes absolutely 14 is correct
And cost of [0,4] will be 19
You not added w(1,4) in cost(1,4)
any doubt??
ask me
Excellent explanation but values are wrongly calculated
what have u done....its a blunder....optimal weight is 19 not 14....tree is fully wrong...check before uploading
[1,4] is 14
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)
waah kya ladka hai
In C (1,3) it's coming 7 instead of 4 with root vertex 3
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
thanks bro
doubt?
[1,3]=4. is it right??? my answer is different
answer is wrong I filled all blocks
C(1,4)=11
C(0,4)=19
And root is vertex 3
Final Optimal BST :- 15
/ \
5 20
\
10
Bhai apne ye neeche ke blocks kyon nhi fill kare
Coz there u got (0,0) vertices and it means value is nothing. Hope u understand
Half part kyu ni solve kiya apne
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
(1, 4) = 11 with root 4 and (0,4)=19 with root 3
Answer is wrong sir
itne time me to 3 question solve hojayenge
answer is wrong...
why we are not considering keys here 😅
can anyone please explain
Dislike to missed the typical part of the video..
c(1,4) = 4 ❌
hence ans is wrong!
Wrong answer brooh!
khud confuse h
It's wrong solution
Bhai kaunsa answer sahi hai bata do kal exam hai
🥲
answer
. 15
/ \
5. 20
\
10
barabar nahii samjta bhaii , thoda explanation , writing ka tarika improve karo
😶😒😑😪
Isko kuch ata nahi hai buus kuch bhi samjha raha hai
Are acche se samjha phela khud Sikh ke aa
Thanks bhai