@vishnusingh4118
5:13 Longest Common Palindromic Sequence ( problem 1) 21:55 Second problem (optimal Search Trees) starts 54:14 Alternating Coins Game (3rd and last example)
@Hallo.Q
One of the best DP lectures I have ever seen. Thanks to MIT open course ware and Prof. Srinivas Devadas
@brysongalapon877
A counter-example to the greedy optimal BST algorithm using 3 nodes has w1 = 10, w2 = 11, w3 = 12. Cheers!
@gormelkumyan3573
There is a tiny mistake in the formula at line 54:13. You can see it by setting i = 1, j = 2, and r = 1, which leads to the expression e[1, 0] + e[2, 2] + ..., where e[1, 0] is undefined. The correct formula can be found in CLRS, Section 15.5, on Optimal Binary Search Trees.
@stormanning1163
Srinivas and Erik you guys are the real Gs!
@RuiLopesFR
If you really want a counter example for 3 nodes, I suggest 1(w=20), 2(w=19), 3(w=18) Greedy would unbalance the tree in 1->2->3 giving a cost of 112 Optimal solution would give a balanced tree of 1<-2->3 that would cost 95
@Garentei
dp[i, j] = min(dp[i, j], e(i, r-1) + e(r+1, j) + wr * (depth+1)) also works if you add the depth every time you go down the recursion tree.
@prachikhobragade4631
I can see Eric Demaine sitting in the first row at (16:16) , he might be wondering, no subproblems and guessing, just directly the recurrence relation :D
@anshprakash1778
It was a very good lecture, everything simplified and quite interactive class.Thanks
@mattg9601
"If you go first your guaranteed to not lose". Man goes second and still won.
@ariellubonja7856
First example question: the pseudocode shown at 22:33 only works with contiguous palindromes, am I wrong? Whereas the brain teasers at the start weren’t necessarily contiguous e.g. “rotator” out of “turboventilator” I do not see how the code can ever figure out “rotator” if you start it with L(0,end) Also I don’t see why nr. Of subproblems is n squared
@nanto-x
Erik Demaine 16:17
@SphereofTime
1:20 You can skip some 1:04:04 dp mazimize
@albertoferrada2075
In the last example I don't really understand why should we assume that the second player chooses the min of his options at the moment. Isn't they running a greedy?, it is said that they play optimally, so why don't we model them decision as another dp?
@adityasahu96
why we need to add all of the node (51:40) i though we need add wr (i<= r <= j)
@xiaomengli8681
The third question should be MinMax problem.
@kongzilla2897
Thank You sir !! :)
@islams_beauty-c8c
what is wi's and pi's I didn't understand it yet.
@EliotMcLellan
Greedy al gore rhythm sounds like my kind of thing! I use greedy algorithms at my home in my own programs all the time
@tutotechie9043