17. Dynamic Programming, Part 3: APSP, Parens, Piano

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

This is the third of four lectures on dynamic programming. This focusses on applying subproblem constraints and expansions to example problems including, Bellman-Ford SSSP, Floyd-Warshall APSP, arithmetic parenthesization, and piano/guitar fingering.

License: Creative Commons BY-NC-SA

[davidloter]

I wish I was smart enough to understand what Eric is professing. Kudos to those that do. 💯

[analll]

Erik is the best teacher, he is so thorough and engaging. If only he taught the whole class.

[milesyan]

12:37: All-Pairs Shortest Paths
25:13: Arithmetic Parenthesization
46:41: Piano Fingering

[MrJesterboi]

7:53: Bellman-Ford reframed in SRTBOT Method

[paulluckner]

24:00 Dense graph should be Theta(|E|)=|V|^2. He mixed up the exponents.

[pengliu]

Insipired by his comments at 58:19 on the subproblem DAG, we can solve the pinao fingering problem from the graph theory perspective using Dikstra's algorithm. The subprblem graph has F source vertices: (t1, f1), (t1, f2), ..., (t1, f_F) which correspond to the begining note t1 played by one of the F fingers, and F destination vertices: (tn, f1), (tn, f2), ..., (tn, f_F) which correspond to the finishing note tn played by one of the F fingers. We also have n-2 stages of intermediate vertices: (t_i, f_x), i = 2, ..., n-1, x = 1, ..., F. The weight for each edge is modeled by the difficulty function: weight((ti, f)->(tj, f')) = d(ti, f, tj, f') (please note that we only have edges between two successive stage of vertices because we have to play the n notes in order). Our goal is to find a shortest path from any of the F sources to any of the F destinations. This problem can be solved using the multi-source Dijkstra algorithm: we dump the F source vertices into the heap and run Dijkstra's algorithm until any of the n-th stage vertices is popped out of the heap. This achieves time complexity O(nFlognF), which is close to the optimal O(nF). To achieve the optimal O(nF) performance, we may directly apply DP on this n-stage DAG, which amounts to the same solution as in this lecture.

[surfmaster]

47:24 Not the two finger algorithm 👀

Noted.

[el_chivo]

love seeing these simple approaches then easing through LC questions i formerly thought were impossible. thanks!!!

[sungjuyea]

1:00:40 where we have a REAL algorithm lesson

[mohammadsalehdehghanpour]

59:10 shouldn't this be F^T? Aside from intuition, in case T=1 this will not reduce the single note problem!

[nullentrophy]

Why bellman ford base case k is equal to 0. Shouldn't it be 0 and positive values?

[paulluckner]

10:27 Should it not be delta_{k-1}(s, v) instead of u?

[rnrnrkrk]

why is the time complexity of Theta(N^3) considered polynomial in 43:20 ?

[codingWorld]

Sir, i want to learn Computer Science at home. But where to start, i don't have any idea. Please suggest me from which course start?
As i am beginner

[dennis]

Can someone explain to me 45:12
How to use this algo for division ➗