Unit 3: Greedy technique
Design and Analysis of Algorithm notes · PTU syllabus (UGCC2519)
On this page
Unit summary
A greedy algorithm builds a solution step by step, always choosing the option that looks best at the moment. It is simple and fast, and gives optimal answers for many important problems. This unit covers the greedy method, the fractional (general) knapsack problem, minimum spanning trees with Prim's and Kruskal's algorithms, and Dijkstra's shortest path algorithm.
After this unit you can
- Explain the greedy approach and when it works
- Solve the fractional knapsack problem
- Find minimum spanning trees with Prim's and Kruskal's algorithms
- Find single-source shortest paths with Dijkstra's algorithm
PTU syllabus topics
- General concept
- general Knapsack problem
- minimum weight spanning trees via Prim's and Kruskal's algorithms
- Dijkstra's algorithm for single-source shortest paths
Builds
One growing tree from a start vertex
A forest that merges into a tree
Picks
Cheapest edge leaving the tree
Cheapest edge that forms no cycle
Best for
Dense graphs
Sparse graphs
Key structure
Priority queue
Union-find
Topic 1
The greedy method
At each step the greedy method makes the locally optimal choice, hoping it leads to a globally optimal solution. It works when the problem has the greedy-choice property and optimal substructure. Greedy algorithms never reconsider earlier choices.
Topic 2
Fractional (general) knapsack problem
Given items with weights wᵢ and profits pᵢ and a knapsack of capacity W, maximise profit. Items may be split.
- 1Compute profit/weight ratio for each item
- 2Sort items by ratio, highest first
- 3Take whole items while they fit
- 4Take a fraction of the next item to fill the knapsack
Example
W = 50; items (w, p): (10, 60), (20, 100), (30, 120). Ratios 6, 5, 4. Take items 1 and 2 fully (weight 30, profit 160) and 20/30 of item 3 (profit 80). Total profit = 240.
Exam tip
The greedy method is optimal for fractional knapsack but not for 0/1 knapsack, which needs dynamic programming.
Topic 3
Minimum spanning trees: Prim's and Kruskal's
A spanning tree connects all vertices of a connected graph without cycles (V − 1 edges). A minimum spanning tree (MST) has the smallest total edge weight.
Approach
Grows one tree from a starting vertex, adding the cheapest edge to a new vertex
Sorts all edges and adds the cheapest edge that doesn't form a cycle
Data structure
Priority queue
Disjoint sets (union-find)
Complexity
O(E log V)
O(E log E)
Best for
Dense graphs
Sparse graphs
Topic 4
Dijkstra's single-source shortest paths
Dijkstra's algorithm finds the shortest distance from a source to every vertex in a graph with non-negative weights. It repeatedly picks the unvisited vertex with the smallest tentative distance and relaxes its edges: if d[u] + w(u, v) < d[v], set d[v] = d[u] + w(u, v). Complexity: O(V²) with an array, O((V + E) log V) with a min-heap.
Example
Source S: S–A = 2, S–B = 5, A–B = 1, B–C = 3. d(A) = 2, d(B) = min(5, 2 + 1) = 3, d(C) = 3 + 3 = 6.
Key terms
- Greedy algorithm
- Makes the best local choice at each step
- Optimal substructure
- An optimal solution contains optimal sub-solutions
- Spanning tree
- A tree connecting all vertices of a graph
- Minimum spanning tree
- A spanning tree with the least total weight
- Relaxation
- Updating a vertex's distance if a shorter path is found
Quick revision
- Greedy: local best choice; no backtracking.
- Fractional knapsack: sort by p/w; greedy is optimal.
- Prim grows a tree; Kruskal sorts edges and avoids cycles.
- Dijkstra needs non-negative weights.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is the greedy method?
- Q2.Why does greedy work for fractional but not 0/1 knapsack?
- Q3.Define a minimum spanning tree.
- Q4.Differentiate between Prim's and Kruskal's algorithms.
- Q5.What is relaxation in Dijkstra's algorithm?
Long-answer questions
- Q1.Solve a fractional knapsack problem with the greedy method, showing each step.
- Q2.Find the MST of a given graph using Prim's and Kruskal's algorithms.
- Q3.Explain Dijkstra's algorithm with an example and analyse its complexity.
Stuck on this unit?
Message SBS on WhatsApp for help with Design and Analysis of Algorithm, or to ask about studying BCA at Synetic.