Opening Dynamic Programming: Crazy Eights and Shortest Path (MIT 6.006, Recitation 19)
Dynamic Programming: Crazy Eights and Shortest Path (MIT 6.006, Recitation 19)
- Length
- 53 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 7: Before the lecture
Costan turns Crazy Eights into a longest path on a DAG, then negates edge weights to solve it as a shortest path.
Dynamic programming in this MIT 6.006 recitation, led by Victor Costan, is treated as shortest-path computation over a graph of states. Costan models the Crazy Eights longest matching subsequence as a longest path in a directed acyclic graph. Negating the edge weights turns that into a shortest path problem, solved by processing vertices in topological sort order. A Manhattan grid problem follows, with compact recurrences and code that never builds the graph explicitly. The session closes on graphs with cycles, unrolling states into layered copies and reading Bellman-Ford as a DAG algorithm run on those layers.
Dynamic programming in this MIT 6.006 recitation, led by Victor Costan, is treated as shortest-path computation over a graph of states. Costan models the Crazy Eights longest matching subsequence as a longest path in a directed acyclic graph. Negating the edge weights turns that into a shortest path problem, solved by processing vertices in topological sort order. A Manhattan grid problem follows, with compact recurrences and code that never builds the graph explicitly. The session closes on graphs with cycles, unrolling states into layered copies and reading Bellman-Ford as a DAG algorithm run on those layers.

This lecture
Lecture 30 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in