Skip to content
Hallway
0:00 / 0:00

#dynamicprogramming#shortestpath#dag

Recitation 19: Dynamic Programming: Crazy Eights, Shortest Path

MIT OpenCourseWare

6.5M subscribers • 36 videos on Hallway • University channel

YouTube
  • Recommended by 1 person: 1 on Stack Overflow and its sister sites.
  • Presented by Victor Costan

Intermediate. Assumes working knowledge.

43K views13 years ago1 recommendation

Computer scienceAlgorithmsData structures

Victor Costan explains dynamic programming concepts, including the Crazy Eights game and finding the shortest path in a DAG.

MIT 6.006 Introduction to Algorithms, Fall 2011 View the complete course: ocw.mit.edu/6-006F11 Instructor: Victor Costan License: Creative Commons BY-NC-SA More information at ocw.mit.edu/terms More courses at ocw.mit.edu

Why it's here

1 person recommends this

What people say. Recommended for its explanation of converting cyclic graphs into directed acyclic graphs.

Dexterson Stack Overflow • Recommends

…e useful. for example consider this below graph. A->B B->C C->A I saw a solution in an MIT lecture but the lecture skimmed over it with reference to something taught earlier and couldn't catch it. In short it kind of replicates the nodes in layers in a way that the end graph denotes a DAG but conveys the same path information. See 46:59 link to this video Edit : There is an explanation of turning cyclic graphs into dags in this MIT recitation at 36:57 link to this video Se also Wikipedia : cycle and forest Edit: I want to apply dynamic programming over a problem which is a cyclic graph e.g) say shortest path problem Delta(S,D) wh……
9View the answer