Sign inSign in

Directed acyclic graph

A DAG is a directed graph with no directed cycles.
as Victor Costan defines itMITThe wording closest to all 8 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Cycle3Directed graph3Graph theory3Computation graph1Directed cycle1Partial order1Physical operators1Poset1

Opens up

Concepts that name this one as a prerequisite.

Lecturers

6

Each in their own terms, from the easiest level.

  • Erik Demaine

    MIT · Undergraduate

    A directed graph with no directed cycles, often used to represent dependencies between subproblems in dynamic programming.
    • 42:52Depth-First Search (DFS), Topological Sort
    • 23:18Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
  • Marten van Dijk

    MIT · Undergraduate

    A directed graph with no directed cycles, obtained by deleting self-loops from a poset.
    • 43:51Graph Theory III
    • 47:17Relations, Partial Orders, and Scheduling
  • Sara Beery

    MIT · Undergraduate

    A directed graph with no cycles, meaning information flows in one direction without loops.
    • 29:09How to Train a Neural Net
  • Martin Kleppmann

    University of Cambridge · Graduate

    A directed acyclic graph is a data structure representing a partial order with branching and merging events.
    • 36:03Thinking in Events: From Databases to Distributed Collaboration Software
  • Andy Pavlo

    Carnegie Mellon University · Graduate

    A structure for a query plan where operators can have multiple parents, allowing for the reuse of computation.
    • 37:13Modern OLAP Database Systems

Lectures that assume it

21

The first 12 are shown.

Connections

37

The lectures that define it or assume it, and the concepts next to it.

Concepts8

Show 2 more

Lectures29

Show 23 more

6 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.