ConceptTheory & Algos
Directed acyclic graph
A DAG is a directed graph with no directed cycles.
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
6Each in their own terms, from the easiest level.
Erik Demaine
A directed graph with no directed cycles, often used to represent dependencies between subproblems in dynamic programming.Marten van Dijk
A directed graph with no directed cycles, obtained by deleting self-loops from a poset.Sara Beery
A directed graph with no cycles, meaning information flows in one direction without loops.Martin Kleppmann
A directed acyclic graph is a data structure representing a partial order with branching and merging events.Andy Pavlo
A structure for a query plan where operators can have multiple parents, allowing for the reuse of computation.
Lectures that assume it
21The first 12 are shown.
- Spelled-Out Intro to Neural Networks & Backpropagation: Building micrograd
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Races and Parallelism
- Dynamic Programming I: Fibonacci, Shortest Paths
- Bayes' Nets: Sampling
- Architectures: Memory
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- History of Memory Models
- Arch4Health: 4th Workshop on Architecture for Health
- Persistent Data Structures
- Hopcroft–Paul–Valiant Theorem
- Computational Models: Circuits
Connections
37The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures29
- Thinking in Events: From Databases to Distributed Collaboration Software
- Depth-First Search (DFS), Topological Sort
- Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
- How to Train a Neural Net
- Modern OLAP Database Systems
- Graph Theory III
Show 23 moreShow fewer
- Relations, Partial Orders, and Scheduling
- Depth-First Search (DFS) (MIT 6.006, Recitation 14)
- Spelled-Out Intro to Neural Networks & Backpropagation: Building micrograd
- Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
- Races and Parallelism
- Dynamic Programming I: Fibonacci, Shortest Paths
- Bayes' Nets: Sampling
- Architectures: Memory
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- History of Memory Models
- Arch4Health: 4th Workshop on Architecture for Health
- Persistent Data Structures
- Hopcroft–Paul–Valiant Theorem
- Computational Models: Circuits
- Boolean Satisfiability (SAT)
- Probabilistic Computation
- Dynamic Programming II: Text Justification, Blackjack
- Building the Blueprint of Life: Genome Assembly
- Probabilistic Computation, BPP
- Algebraic Circuit Complexity
- Dynamic Programming: Crazy Eights and Shortest Path (MIT 6.006, Recitation 19)
- Optimising for Fast Builds with GHC
- Dynamic Programming: Dance Dance Revolution (MIT 6.006 Recitation 22)