Formula Sheets: Greedy Techniques

 Page 1


Greedy T ec hniques
General Concepts
Greedy Choice Prop ert y
• Optimal solution ac hiev ed b y making lo cally optimal c hoices at eac h step.
Optimal Substructure
• Problem’s optimal solution con tains optimal solutions to subproblems.
Key Algorithms
A ctivit y Selection Problem
• Sort activities b y finish time: f
1
=f
2
= ··· =f
n
.
• Select activit y with earliest finish time, remo v e conflicting activities.
• Time Complexit y: O(nlogn) (sorting dominates).
• Space Complexit y: O(1) (excluding input storage).
F ractional Knapsac k
• Sort items b y v alue-to-w eigh t ratio: v
i
/w
i
in descending order.
• Fill knapsac k with highest ratio items, tak e fractions if needed.
• Time Complexit y: O(nlogn) (sorting dominates).
• Space Complexit y: O(1) (excluding input storage).
Job Sequencing with Deadlines
• Sort jobs b y profit in descending order.
• Sc hedule jobs in a v ailable slots b efore deadlines.
• Time Complexit y: O(nlogn+n·d) , where d is max deadlin e.
• Space Complexit y: O(d) for slot arra y .
Huffman Co ding
• Build min-heap of c haracter frequencies: O(nlogn) .
• Construct Huffman tree b y merging no des: O(nlogn) .
• T ime Complexit y: O(nlogn) , where n is n um b er of c haracters.
• Spac e Complexit y: O(n) for heap and tree.
Minim um Spanning T ree
• Kruskal’s Algorithm :
– Sort edges b y w eigh t: O(ElogE) .
– Use Union-Find to detect cycles: O(Ea(V)) , where a is in v erse A c k ermann.
– Time Complexit y: O(ElogE) .
– Space Complexit y: O(V +E) .
• Prim’s Algorithm :
– Use min-heap for edges: O((V +E)logV) .
– Time Complexit y: O((V +E)logV) with binary heap.
– Space Complexit y: O(V) for heap and visited arra y .
Dijkstra’s Shortest P ath
1
Page 2


Greedy T ec hniques
General Concepts
Greedy Choice Prop ert y
• Optimal solution ac hiev ed b y making lo cally optimal c hoices at eac h step.
Optimal Substructure
• Problem’s optimal solution con tains optimal solutions to subproblems.
Key Algorithms
A ctivit y Selection Problem
• Sort activities b y finish time: f
1
=f
2
= ··· =f
n
.
• Select activit y with earliest finish time, remo v e conflicting activities.
• Time Complexit y: O(nlogn) (sorting dominates).
• Space Complexit y: O(1) (excluding input storage).
F ractional Knapsac k
• Sort items b y v alue-to-w eigh t ratio: v
i
/w
i
in descending order.
• Fill knapsac k with highest ratio items, tak e fractions if needed.
• Time Complexit y: O(nlogn) (sorting dominates).
• Space Complexit y: O(1) (excluding input storage).
Job Sequencing with Deadlines
• Sort jobs b y profit in descending order.
• Sc hedule jobs in a v ailable slots b efore deadlines.
• Time Complexit y: O(nlogn+n·d) , where d is max deadlin e.
• Space Complexit y: O(d) for slot arra y .
Huffman Co ding
• Build min-heap of c haracter frequencies: O(nlogn) .
• Construct Huffman tree b y merging no des: O(nlogn) .
• T ime Complexit y: O(nlogn) , where n is n um b er of c haracters.
• Spac e Complexit y: O(n) for heap and tree.
Minim um Spanning T ree
• Kruskal’s Algorithm :
– Sort edges b y w eigh t: O(ElogE) .
– Use Union-Find to detect cycles: O(Ea(V)) , where a is in v erse A c k ermann.
– Time Complexit y: O(ElogE) .
– Space Complexit y: O(V +E) .
• Prim’s Algorithm :
– Use min-heap for edges: O((V +E)logV) .
– Time Complexit y: O((V +E)logV) with binary heap.
– Space Complexit y: O(V) for heap and visited arra y .
Dijkstra’s Shortest P ath
1
• Select v ertex with minim um distance, up date distances to neigh b ors.
• Time Complexit y: O((V +E)logV) with binary heap, O(V
2
) with arra y .
• Space Complexit y: O(V) for distance arra y and heap.
Optimal Merge P atterns
• Us e min-heap to merge files in increasing order of size.
• T ime Complexit y: O(nlogn) , where n is n um b er of files.
• Spac e Complexit y: O(n) for heap.
Minim um Num b er of Coins
• Sort d enominations in descending order.
• G reedily select largest denomination that fits remaining amoun t.
• T ime Complexit y: O(nlogn+V) , where n is n um b er of denominations, V is amoun t.
• Space Complexit y: O(1) (excluding output).
2