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

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

Courses on Udemy
================
Java Programming

Data Structures using C and C++

C++ 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 Youtube ever,

[eddiesengola]

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

[fenggeliu]

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)

[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 <= k <= j; k is the root; the nodes with index i to k-1 are the nodes in the left sub tree of the root and node with index k+1 to j are in the right sub tree of the root. The cost of any sub tree C[i, j] is 0 if i > j; C[i, j] = pi if i = j

[Maryam_Qureshi]

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

[softwareengineer]

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

[paulz_san]

How many engineers out here, give a like.

[yogesh]

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

[RoyalEXO_]

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

[anasjamal]

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

[Sahasra_Chowdary]

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

[sandeepkumar-tykt]

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

[piyushverma]

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.

[HimanshuSharma-usgz]

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!

[iago]

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

[coolone]

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

[aradhyajain]

@14:45 how are you getting the values using also please tell how u calculated it in brief? am finding it very difficult to understand this part.

[ImSoumenMukherjee]

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

[P_S_PATIL]

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

[souravkalal]

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