All lessonsOpen Open Open Open Open
11. DP, Greedy & Tries
Greedy algorithms
0 of 5 activities0%
Reading 1
Local best, global hope
Greedy picks the best-looking option at each step without reconsidering.
Works when a greedy choice property and optimal substructure hold — e.g., activity selection, Huffman, many scheduling problems.
Counterexamples exist; prove or recognize patterns. Contrast with DP when subproblems overlap and greedy fails.
// activity selection: sort by end time, take next compatibleCheck 2
Always optimal?
Greedy algorithms are
Fill in 3
Activity
Try it 4
Coin greedy
US coins style.
main.cpp
Loading editor…
Output will appear here.
Assignment 5
Min coins canonical
Read n. Using coins 25,10,5,1 print minimum number of coins (greedy works here).
main.cpp
Loading editor…