Opening Greedy Algorithms (MIT 6.046J, Recitation 6)
Greedy Algorithms (MIT 6.046J, Recitation 6)
- Length
- 22 min
- Level
- Undergraduate
- Recorded
- MIT2016
Chapter 1 of 4: Before the lecture
Greedy algorithms solve three problems in Biswas's recitation for MIT 6.046J, Design and Analysis of Algorithms. A continuous make-change problem comes first: metals are sorted by cost per unit weight and the most expensive is used first, minimizing total weight. Process scheduling then orders jobs by execution time, and an exchange argument shows that swapping any inversion lowers average completion time. A variant handles online job requests by tracking remaining execution times. Interval partitioning sorts events by start time and opens a new clone only when every existing one conflicts, assuming familiarity with sorting, Kruskal's algorithm and induction.

Your comment is kept while you sign up.Sign in
Biswas proves shortest-job-first scheduling optimal by an exchange argument that swaps inversions.
Greedy algorithms solve three problems in Biswas's recitation for MIT 6.046J, Design and Analysis of Algorithms. A continuous make-change problem comes first: metals are sorted by cost per unit weight and the most expensive is used first, minimizing total weight. Process scheduling then orders jobs by execution time, and an exchange argument shows that swapping any inversion lowers average completion time. A variant handles online job requests by tracking remaining execution times. Interval partitioning sorts events by start time and opens a new clone only when every existing one conflicts, assuming familiarity with sorting, Kruskal's algorithm and induction.
This lecture
Lecture 14 of 27 of Design and Analysis of 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.