ConceptTheory & Algos
Greedy algorithm
An algorithmic approach that makes the locally optimal choice at each stage with the intent of finding a global optimum.
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.
Algorithm2Optimization2Action-value estimation1Algorithm design1Dynamic programming1Monte-Carlo evaluation1
Opens up
Concepts that name this one as a prerequisite.
Cut and paste argument1Decision tree learning algorithm1Dijkstra's algorithm1Dijkstra's algorithm greedy step1Earliest finish time1Event overlap problem (interval partitioning)1Fractional make-change1Greedy approval voting1Greedy ascent algorithm1Greedy-choice property1Interval scheduling1L prime definition1
Lecturers
6Each in their own terms, from the easiest level.
Erik Demaine & Srini Devadas
An algorithmic strategy for optimization where choices are made step-by-step to maximize local benefit.Tom Leighton
An algorithm that makes the locally optimal choice at each stage without backtracking or global optimization.David Jerison
An algorithm that tries to do the best possible at each stage.David Silver
An algorithm that always selects the action with the currently estimated highest value without exploring alternatives.Srini Devadas
An algorithm that makes locally optimal choices at each step in the hope of finding a global optimum.
Lectures that assume it
10- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Complexity: Approximation Algorithms
- Algorithmic Thinking & Peak Finding in 1D and 2D
- Graph Theory II: Minimum Spanning Trees
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Optimality II
- Greedy Algorithms: Minimum Spanning Tree
- Greedy Algorithms (MIT 6.046J, Recitation 6)
- AI in Science and Engineering: Proportionality in Multiwinner Voting
- Machine Learning: Neural Networks and Decision Trees
Connections
24The lectures that define it or assume it, and the concepts next to it.
Concepts8
- Algorithm
- Optimization
- Dynamic programming
- Cut and paste argument
- Decision tree learning algorithm
- Dijkstra's algorithm
Show 2 moreShow fewer
Lectures16
- Course Overview, Interval Scheduling
- Graph Theory and Coloring
- Taylor's Series
- Exploration and Exploitation
- Dynamic Programming: Advanced DP
- Information Theory: A Sample Lecture
Show 10 moreShow fewer
- Dijkstra's Shortest Path Algorithm: Graph Theory and Optimization
- Complexity: Approximation Algorithms
- Algorithmic Thinking & Peak Finding in 1D and 2D
- Graph Theory II: Minimum Spanning Trees
- Dijkstra's Algorithm: Greedy Single-Source Shortest Paths
- Dynamic Optimality II
- Greedy Algorithms: Minimum Spanning Tree
- Greedy Algorithms (MIT 6.046J, Recitation 6)
- AI in Science and Engineering: Proportionality in Multiwinner Voting
- Machine Learning: Neural Networks and Decision Trees