15. Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine

This is the first of four lectures on dynamic programing. This begins with how to solve a problem recursively and continues with three examples: Fibonacci, DAG shortest paths, and bowling.

License: Creative Commons BY-NC-SA

[Wepper]

I use these concepts when working on performance. The project stakeholders are always amazed how much better our systems respond when I integrate those changes. These lectures are literal career makers :)

[ParthPatel-vjzv]

0:00 intro, DP = SRTBOT + memoization
3:05 SRTBOT - recursive algo design paradigm
5:58 merge-sort algo as SRTBOT
8:41 solving fibonacci with SRTBOT
13:43 memoization
26:57 solving DAG shortest path with DP
37:00 bowling problem
52:05 bottom-up DP, intuition of DP as local brute force

[brunofenalialmeida]

The moment that he defined the bowling with that 3 elements in a so simple and cleaver way, and a huge moment of a aha happened! Demaine is insane! o/

[RAJSINGH-jcej]

Great to see a new version of 6.006. I love it. The recording is much more smooth and the quality is better.

[pedrov]

It's great to see both lectures a decade apart. They both have interesting nuances.

[pedrolopes]

Love this guy's lectures. Interesting parts in this especially the tricks to design the DP sub-problem. Really helpful

[himeyprogramming]

I love when Eric write on board and explain.

[huhnturr]

Man I love hearing him talk! So brilliant and clear

[fxrcode]

1:15 In general, this class-- all of algorithms-- is about RECURSIVE algorithm design at some level, cuz we want to write constant-sized pieces of code that solve problems of arbitrary size.

[soonshin-sam-kwon]

pure golden giant withstanding the test of time about 10 years. really appreciate sharing this invaluable humankind resources

[JosephCaburnay]

Mindblown about the bottom up version of the solution of the bowling problem!

[raymondwang]

Wow! A new version of 6.006.Missing Victor a little bit. Erik is always brilliant! Now I got a deeper understanding of DP every time I have this lecture!

[dohjohn]

I really appreciate these institutes for uploading such a good lecture like this for free.

[devmahad]

For my own reference:
0:00 intro, DP = SRTBOT + memoization
3:05 SRTBOT - recursive algo design paradigm to solve diverse range of problems
5:58 merge-sort algo as SRTBOT
8:41 solving fibonacci with SRTBOT, reusing our calculation
13:43 memoization (top down and bottom up approach)
26:57 solving DAG shortest path with DP (DP is same DFS as it uses small problems to large, or to say large problems need smaller problems for calculation)
37:00 bowling problem (a toy problem, in which we uses the power of DP)
52:05 bottom-up DP, intuition of DP as local brute force

[lamidaj]

13:05 Erik: "Fibonacci growth is the golden ratio to the n... This is exponential growth. As we know especially in this time, exponential growth is bad." :D :"(

[jakewatkins]

l always rewatch the OCW dynamic programming videos for my interview prep and everytime i re- remember how the recurrence relation works and how to find it i get the same a-ha feeling and all the good brain chemicals that come with it :-)

[suindude]

There is a wonderful usage of Best time complexity in calculating the DAC as nlogn time complexity to divide the whole array and the resulting array sorted generation as we don't have to take order the previous DAC with respect to pivotal element.
Thus the additive summative logarithm a little bit less in calculation of nlogn but approximated.

[michaelarend]

1:33 after so many lecture the camera cut blew my mind

[tarunpahuja]

You can use topological order to write iterative version

[suindude]

Today I found a resemblance in the case of the BST creation in case of the Divide option in case of division of array in merge sort and the same recursive ordering in the resultant arrays.
Thus, we find a great relation in case of creation of bipartite scenario creation in case of the Quick or Merge sort array generation.