@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)
@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
@tutotechie9043
All of Prof. Devadas lectures are just amazing. In particular, this is probably the best video I watched about DP.
@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!
@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
@stormanning1163
Srinivas and Erik you guys are the real Gs!
@adityasahu96
why we need to add all of the node (51:40) i though we need add wr (i<= r <= j)
@mattg9601
"If you go first your guaranteed to not lose". Man goes second and still won.
@SphereofTime
1:20 You can skip some 1:04:04 dp mazimize
@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
@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?
@nanto-x
Erik Demaine 16:17
@anshprakash1778
It was a very good lecture, everything simplified and quite interactive class.Thanks
@xiaomengli8681
The third question should be MinMax problem.
@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
@loam
One thing I don't get about all those recursions is, why are you guys don't mention that stack is limited and able to hold limited recursive calls to functions, and for some big enough input number for problem to be solved for, you might get stack overflow. Or is this all just theory and one shouldn't be thinking about how to use it in practice?
@gormelkumyan3573