Solution breakdown is fine but we would love to learn the idea behind detecting DP pattern in a given problem. Understand how this problem qualifies for DP.
His explanation is missing a lot of key details. Here is my take on the problem, We are initially given a set of keys in the sorted order. So let's consider a subset of the initial problem set [i,j], consisting of elements, Ai...Aj We would need to consider all solutions(Binary Search Trees) that can be formed using these elements. Let's say we have Ak(i A[i,j] = min(A[i,k-1] + sum(i,j) + A[k+1, j]) Where sum(i,j) is sum of all keys between i, j Why this is a DP problem is because we have an optimal substructure, and that we have overlapping subproblems, as Tushar explained, we use solutions of left and right subtree directly from our matrix stored, and dont compute them again.
this is good explaination for how we came to the algorithm showed in the video. I guess Tushar demoonstrated the white boarding process during an interview. it could be better this analysis process also included
I thought this was excellent up until the very end, there isn't much of an explanation as to why 16 is the root. Afterwards, why each key becomes the following node. Otherwise, very well done!
To get the root, we return the upper right entry in the table: T(1, n). In this particular case, the top right corner has (2) as the root. And given that, for a binary search tree, a give node's left children will be smaller and similarly, the node's right children will be greater.
Some more definition of how cost is calculated would be better: “The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1.” e.g from geeksforgeeks www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/ keys[] = {10, 12}, freq[] = {34, 50} There can be following two possible BSTs 10 12 \ / 12 10 I II Frequency of searches of 10 and 12 are 34 and 50 respectively. The cost of tree I is 34*1 + 50*2 = 134 The cost of tree II is 50*1 + 34*2 = 118 Now understanding how cost is calculated, we"ll know why in this video the presenter will get the sum of a range [i, j] as first step in each subarray. Since when we pick a new root, all nodes in the range will have their level incremented by one, resulting in the total cost increment by the sum of freq in range [i...j]
This is to do with the way the dp[][] (int[][]) matrix was populated. It is a form of divide & conquer, if you like. You take a range for subtree [0:3], locate its root (at index 2 in the first iteration), then, recursively, you find roots for left and right subtrees (range [0:1], root at index 0 and [3:3], 3 respectively) . Base case for the recursion is when the range consists of 1 element (because this clearly is a leaf). Hope this helps.
Thank you for explaining the implementation of the algorithm. Due to time crunch not all concepts here can be understood, however, it would be great if you could also create videos on the conceptual part of the problem and how to deduce such a solution of dynamic programming.
Your video is fantastic, but I got lost right at the end. I am hoping you could further explain the layout of the tree ? Like why the root is 16 and why 10 is the root for the left subtree?
Dynamic programming is too clever and tricky to be solvable, hey Tushar can you tell, how to choose the matrix rows and columns in any DP problem. When I tried to solve this problem particularly, I made a matrix with frequency and keys, it was solvable though needed much calculations. In longest palindromic subsequence problem you chose length again, like in this problem. What's the similarity?, is it because of permutations(ordering of elements) or something else? Awesome work!, Hats off.
Check out the previous video in the playlist: ruclips.net/video/s6FhG--P7z0/видео.html He explains how the subset is chosen. This is no different. Your subproblem is, given a subset of keys, what should be the optimal BST. A cell at location [i,j] means what is the best way to form a BST using keys from position i to j. Thus the solution will be in the matrix's [0,N-1] cell. So you build the matrix all the way to M[0,N-1]. Since this video is in continuation, that part is assumed to be understood. :)
Hi Tushar, thanks for uploading the video tutorials. It really helped me refresh my algos which I did in grad school in late 70's. My only complain is you are an Aggie and I am a Longhorn. Kidding. :-) Anyway. my question is how do you remember all those algorithms? I also would like if you can make video tutorials on Kd Trees, Cover Trees, R-Trees and Suffix Trees. Thanks.
Nicely Explained. Thank you. It would been complete if you could have explained about what are the overlapping sub problems here? Why we have to construct the table in this manner? What is the need to add the frequencies of all the keys in first?
we can sort the array comparing frequency in a decreasing order and then follow the greedy algorithm to place most repeated on lowest level as possible correct me if am wrong for example the sorted array for this example is 16,10,21,12.So we place 16 as root on lowest level and then choose next two 10 and 21 as its children and then so on we follow level wise insertion until we reach the end of array correct me if iam wrong thank you
Great work, watching the explanation on courseras Algorithms 2 course from stanford the algorithm was unclear. This helps to solve it up . The big oh is N^3 , correct? The n*n filling of the dynamic table , multiplied by the work done to calculate each cell , which is our min function that does n work .
Hi Tushar! thanks for the video. The concept is crystal clear. On finding an optimal root at every stage, you are saying to store it. Where do i store? The source code in mission-peace wiki has the optimal search cost calculation, is there a version which prints the optimal bst?
Why can't we just build the tree based on decreasing order of frequencies. I mean in your example make 16 as root (because it has highest frequency), then insert 10 in the tree (second highest frequency) followed by 21 (third highest) and lastly insert 12 (least frequency). This is create tree in the following order 16, 10, 21, 12 because the frequencies are 6, 4, 3, 2 in decreasing order.
A larger set of elements would have been more explanatory while you are forming the tree. How the tree node traversal is happening here is not clearly mentioned for a larger set of data.
thanks for explanation.But I didn't understand how to create a table.I mean, you created kind of upper triangular matrix as a table, but one can also make a lower triangular matrix.So how to decide, whether to make a lower triangular matrix or upper triangular matrix?
Hi Tushar, thanks for sharing solution and explaining in better way. I just have once question regarding code : why you have started first for loop with l=2 ( for(int l = 2; l
I understand how to build the table. But couldn't understand how you create the optimal BST based on the calculated table. How you choose 16 as a root ,10 and 20 as its left and right children and so on?
Hi Tushar, how can you get value (0,2) as 20 if you go by keeping 2nd index as root it would give 22 not 20 , SImilarly for (0,3) instead of giving 26 it is giving 28, Can you recheck it with tree structure ? Thanks for the great work
Hi Tushar, One point which I could not understand in this video is this: When l = 3, key = 10, 12, 16 freq= 4, 2, 6 From my calculation we should have val = 4+2+6 + min ( 10 as root, 12 as root, 16 as root) = 12 + min ( 2 + 6*2, 4 + 6, 2 + 4*2) = 12 + min( 14, 10, 10) = 12 + 10 = 22.. From your video val = 4+2+6 + min(10, 10, 8) I don't understand how you got 10, 10, 8 in place of 14, 10, 10 ? Would you please explain?
What the hell do the rows and columns in the table represent? How can you start the explanation without letting people know what are you filling up in the matrix
sir, i think keys should be sorted becoz that is the only reason=> while making all trees consisting of 2 nodes (i.e.for l=2) we consider only the continuous adjacent members ...so on for l=3 ,4,.....
Wat can be done if we got all the 4 values same when l=4... suppose all the values at root 0,1,2&3 are same then which value is to be selected as a minimum
Can we sort frequencies in decreasing order and start inserting elements in BST from the highest frequency key to least. Complexity O(nLogn) Can this be a possible solution?
Could you'll please explain that while we are considering l=2 we are computing (0,1),(1,2),(2,3) but why are we ignoring other doublets like (1,3) which is even more optimal giving answer 7. Can't we build our solution using that doublet. Kindly help ::)
If you are making videos then please first give resursion explanation then overlapping subproblems and then hot to decrease and idea behind it.. Just dont do all thing as layman terms..
+yogesh upadhyay , When we calculate a new cost from the existing costs , we have actually moved a level up . The moment we are at a level higher , the total cost of the new tree would increase by 1*(sum of cost of all nodes of the tree) apart from the previous tree's cost.
Your videos are one of the best as they explain concepts in a very easy way! Thanks a lot !
Solution breakdown is fine but we would love to learn the idea behind detecting DP pattern in a given problem. Understand how this problem qualifies for DP.
😮
😮
You have perfectly solved the problem ! Anybody with some background of DP and theory of Optimal BST problem can surely follow your approach.
His explanation is missing a lot of key details.
Here is my take on the problem,
We are initially given a set of keys in the sorted order.
So let's consider a subset of the initial problem set [i,j], consisting of elements, Ai...Aj
We would need to consider all solutions(Binary Search Trees) that can be formed using these elements.
Let's say we have Ak(i A[i,j] = min(A[i,k-1] + sum(i,j) + A[k+1, j])
Where sum(i,j) is sum of all keys between i, j
Why this is a DP problem is because we have an optimal substructure, and that we have overlapping subproblems, as Tushar explained,
we use solutions of left and right subtree directly from our matrix stored, and dont compute them again.
this is good explaination for how we came to the algorithm showed in the video. I guess Tushar demoonstrated the white boarding process during an interview. it could be better this analysis process also included
This explained how he got the sum that was being prefixed in every step. Thanks for the explanation.
That was a great articulation out there in youtube about Optimal BST. Appreciate it
Without your videos..i would be lost..Thanks
Awesome explanation .Was searching for dry run for this problem .You nailed it perfectly .Thanks :)
Wonderful Tushar.Got an clear idea about OBST
I thought this was excellent up until the very end, there isn't much of an explanation as to why 16 is the root. Afterwards, why each key becomes the following node. Otherwise, very well done!
To get the root, we return the upper right entry in the table: T(1, n). In this particular case, the top right corner has (2) as the root. And given that, for a binary search tree, a give node's left children will be smaller and similarly, the node's right children will be greater.
Thank you so much for the explanation on how to get binary search tree after 2D matrix is filled. :)
Superb Explanation, Really Enjoyed...
Some more definition of how cost is calculated would be better: “The cost of a BST node is level of that node multiplied by its frequency. Level of root is 1.” e.g from geeksforgeeks www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/
keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs
10 12
\ /
12 10
I II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118
Now understanding how cost is calculated, we"ll know why in this video the presenter will get the sum of a range [i, j] as first step in each subarray. Since when we pick a new root, all nodes in the range will have their level incremented by one, resulting in the total cost increment by the sum of freq in range [i...j]
This topic is a little complicated but you have explained it well. Thank you, sir! :)
9:35 "Then we go to 0 to 1". ok, but why? I see why you do it here, but I have no clue what to do in general when constructing that tree.
This is to do with the way the dp[][] (int[][]) matrix was populated. It is a form of divide & conquer, if you like. You take a range for subtree [0:3], locate its root (at index 2 in the first iteration), then, recursively, you find roots for left and right subtrees (range [0:1], root at index 0 and [3:3], 3 respectively) . Base case for the recursion is when the range consists of 1 element (because this clearly is a leaf). Hope this helps.
you are explaining really good in all videos .Makes it easy to understand. thanx for helpng (y)
Thanks for doing this thanks to you I finally understood this topic!
Great explanation, this video is awesome!!! Great job!!!!
Thank you for explaining the implementation of the algorithm. Due to time crunch not all concepts here can be understood, however, it would be great if you could also create videos on the conceptual part of the problem and how to deduce such a solution of dynamic programming.
Literally saved my life. Best youtube channel I have come across for my algorithms course... THUMBS UP!!!
Thanks for your explanations. Great help! :)
Awesome video,very clear explanation!
great explanation sir!! things became pretty much easy!!thanx a lot... helped a lot
!!
Your video is fantastic, but I got lost right at the end. I am hoping you could further explain the layout of the tree ? Like why the root is 16 and why 10 is the root for the left subtree?
Nice illustration! Really like your videos on algorithm :)
I thought it was quite a good explanation. Thanks!
This video is very helpful.Thank you very much
thanks for the explanation sir......it made things look so easy and simple!! please do a tutorial on Huffman trees using dynamic programming ,
Can you please explain more about constructing tree back from matrix?
Very good explanation in all videos .Makes it easy to understand ..Thanks :)
Dynamic programming is too clever and tricky to be solvable, hey Tushar can you tell, how to choose the matrix rows and columns in any DP problem. When I tried to solve this problem particularly, I made a matrix with frequency and keys, it was solvable though needed much calculations. In longest palindromic subsequence problem you chose length again, like in this problem. What's the similarity?, is it because of permutations(ordering of elements) or something else? Awesome work!, Hats off.
This is great! Thank you so much. I can now make a cost matrix, and a root matrix from the concepts I have learnt here. :)
Really helpful. Thank you So much Tushar :)
Why we go from zero to one at approx 9:47 in to video??? i think It doesn't make any sense right???
Thanks in advance.
Awesome explanation Sir
💫💫🌈🌈
Sorry...But you are not explaining properly. I am not getting how you are solving problem
see video more than one times ,finally u got
watch it again, it was 1000x easier than in the CLRS book
Truth...the CRLS book explanation was subpar
He was probably explaining to himself xD
Check out the previous video in the playlist: ruclips.net/video/s6FhG--P7z0/видео.html
He explains how the subset is chosen. This is no different. Your subproblem is, given a subset of keys, what should be the optimal BST. A cell at location [i,j] means what is the best way to form a BST using keys from position i to j. Thus the solution will be in the matrix's [0,N-1] cell. So you build the matrix all the way to M[0,N-1].
Since this video is in continuation, that part is assumed to be understood. :)
great video Tushar!
Thank you very much for this tutorial.
Could you please make a video for "Activity Selection Problem"
Kindly Regards
Hi Tushar, thanks for uploading the video tutorials. It really helped me refresh my algos which I did in grad school in late 70's. My only complain is you are an Aggie and I am a Longhorn. Kidding. :-) Anyway. my question is how do you remember all those algorithms? I also would like if you can make video tutorials on Kd Trees, Cover Trees, R-Trees and Suffix Trees. Thanks.
Just liked your comment to remember this
Thanks for your clear explanation.
Thank you Gautam Gambhir 🙌
Nicely Explained. Thank you. It would been complete if you could have explained about what are the overlapping sub problems here? Why we have to construct the table in this manner? What is the need to add the frequencies of all the keys in first?
awesome! The explanation is very clear
very helpful in exam coz we are having module system in college all syllabus of daa in 6 weeks and then exam
Max binary heap would have done the job right ?
You are freaking awesome!
Wish you the best!
Great explanation!, thank you so much
we can sort the array comparing frequency in a decreasing order and then follow the greedy algorithm to place most repeated on lowest level as possible correct me if am wrong for example the sorted array for this example is 16,10,21,12.So we place 16 as root on lowest level and then choose next two 10 and 21 as its children and then so on we follow level wise insertion until we reach the end of array
correct me if iam wrong
thank you
Amazing explanation! Thanks.
keep updating the algorithm lesson. you really great at explanation
Great work, watching the explanation on courseras Algorithms 2 course from stanford the algorithm was unclear. This helps to solve it up .
The big oh is N^3 , correct? The n*n filling of the dynamic table , multiplied by the work done to calculate each cell , which is our min function that does n work .
its O(n^4) - u forgot the sum
Nope, @Mark was right.
The time complexity of this algorithm is O(n^3).
Hi Tushar! thanks for the video. The concept is crystal clear. On finding an optimal root at every stage, you are saying to store it. Where do i store? The source code in mission-peace wiki has the optimal search cost calculation, is there a version which prints the optimal bst?
Why can't we just build the tree based on decreasing order of frequencies. I mean in your example make 16 as root (because it has highest frequency), then insert 10 in the tree (second highest frequency) followed by 21 (third highest) and lastly insert 12 (least frequency). This is create tree in the following order 16, 10, 21, 12 because the frequencies are 6, 4, 3, 2 in decreasing order.
How come u are assuming addresses from 9:36
Great video! Actually there is a typo on the white board, and the title on it should be 'Optimal Binary Search Tree'. : )
Do u have any plans to do a playlist on greedy algorithms??
dude. u need to explain it to others here, not yourself!
Virendra Singh Bais this is the same thing our teacher gives lecture. Neither understood then nor understood this guy also
Couldn't understand...the worst explaination...he kept on teaching and practising for himself..
A larger set of elements would have been more explanatory while you are forming the tree. How the tree node traversal is happening here is not clearly mentioned for a larger set of data.
thanks for explanation.But I didn't understand how to create a table.I mean, you created kind of upper triangular matrix as a table, but one can also make a lower triangular matrix.So how to decide, whether to make a lower triangular matrix or upper triangular matrix?
move from in front of the damn board man. very good tutorial but we can't see anything.
True...😂😂😂😂😂
Hi Tushar, thanks for sharing solution and explaining in better way. I just have once question regarding code :
why you have started first for loop with l=2 ( for(int l = 2; l
I understand how to build the table. But couldn't understand how you create the optimal BST based on the calculated table. How you choose 16 as a root ,10 and 20 as its left and right children and so on?
Super. It would be perfect if you also provided the formula in the end
Why it can't be a greedy solution?
If take a greedy approach of taking the key with maximum cost as root. Will it give an optimal solution?
By the way i appreciate you aap khidmat e khalq kar rahay ho
@Tushar, Why take the sum of frequencies into consideration for L > 1 ?
Kindly Elaborate!
nice explanation! great work :)
I have been following your tutorial on DP for quite some time. They are wonderful. However, I am curious to know why do you employ bottom-up approach?
***** Cool. Thanks
Excellent explanation
Hi Tushar, how can you get value (0,2) as 20 if you go by keeping 2nd index as root it would give 22 not 20 , SImilarly for (0,3) instead of giving 26 it is giving 28, Can you recheck it with tree structure ? Thanks for the great work
Hi Tushar,
One point which I could not understand in this video is this:
When l = 3,
key = 10, 12, 16
freq= 4, 2, 6
From my calculation
we should have val = 4+2+6 + min ( 10 as root, 12 as root, 16 as root)
= 12 + min ( 2 + 6*2, 4 + 6, 2 + 4*2)
= 12 + min( 14, 10, 10)
= 12 + 10
= 22..
From your video
val = 4+2+6 + min(10, 10, 8)
I don't understand how you got 10, 10, 8 in place of 14, 10, 10 ?
Would you please explain?
What the hell do the rows and columns in the table represent? How can you start the explanation without letting people know what are you filling up in the matrix
you may replace the 10,12, 16, 21 by characters which less confusing.
really nice and helpful video....
Can u explain how you constructed the tree after determining the table values
I think keys should be sorted for this to work !
sir, i think keys should be sorted becoz that is the only reason=> while making all trees consisting of 2 nodes (i.e.for l=2) we consider only the continuous adjacent members ...so on for l=3 ,4,.....
yup, you are correct, sorting is not needed
I wonder how can we rebuild the BST based on this algo?
Why not reverse sort the array and place them in level order??
Only you knows that what you are teaching....
how was the binary tree derived? from 2nd level
Prannav Krishna
The definition of the binary search tree, left nodes are less than the root, and the root is less than the right nodes.
is the numbers should be sorted order?
Explain making the tree from the matrix in a better way please. I did not see any logic as to how you made the final OBST.
awesome video!!!!!
hey could you make a video on multi-stage graph and reliability design plz
Why don't we sort the costs in decreasing order and insert the nodes accordingly
You are suggesting greedy solution for this problem. Greedy algorithm will not work here.
Excellent Explanation
not very well explained..specially when you were doing it for l = 3
Wat can be done if we got all the 4 values same when l=4... suppose all the values at root 0,1,2&3 are same then which value is to be selected as a minimum
Mst find karna hai ... toh same values kaise ho sakti hai
Can we sort frequencies in decreasing order and start inserting elements in BST from the highest frequency key to least.
Complexity O(nLogn)
Can this be a possible solution?
***** Got it! Thanks.. your videos are very helpful. :) Keep posting more!
How about the quadratic solution?
Could you'll please explain that while we are considering l=2 we are computing (0,1),(1,2),(2,3) but why are we ignoring other doublets like (1,3) which is even more optimal giving answer 7.
Can't we build our solution using that doublet.
Kindly help ::)
we are building a BST, if we wanted just a binary tree then that would be valid
sir i need ellis horowitz book slides in optimal binary search tree
is there no greedy algorithm for problem
CAN U SUGGEST FORMULA FOR THIS APPROACH
just before pressing the unlike button make sure you watch it more than one time
thanks tushar
If you are making videos then please first give resursion explanation then overlapping subproblems and then hot to decrease and idea behind it.. Just dont do all thing as layman terms..
But giving same explanation in every video would be boring, though he can show how and why the problem is solvable by DP?
I come here to directly understand DP solution.
Exactly! He should explain the recursion behind this and improve it by giving a DP solution.
sir,the keys should be sorted ... u didnt mentioned it !
nice explanation sir , but a genuine feedback , you are blocking the board too much( move aside and turn and explain in between ) :)
is it work for un sorted list
bro thanks Alot i need algorithms for this tutorials
What is the reason for adding the sum from (i to j) .
+yogesh upadhyay , When we calculate a new cost from the existing costs , we have actually moved a level up . The moment we are at a level higher , the total cost of the new tree would increase by 1*(sum of cost of all nodes of the tree) apart from the previous tree's cost.
u r explaining well but explain it to us,.. board to dikhne do