Greedy Design Technique
- Greedy algorithms uses heuristic approach to make optimal choice at each stage while problem solving to find a globally optimized solution.
- We can use Greedy approach to solve an optimization problem by following:
- Greedy-choice property: This property says a global optimum solution can be achieved by selecting a local optimum.
- Optimal substructure: Optimal Substructure is an optimal solution to the problem that contains an optimal solution to each of its subproblems.
There are various greedy algorithms', some of them are mentioned below:
- Dijkstra's Algorithm (Single Source shortest path)
- Kruskal's algorithm (Minimum Spanning Tree)
- Prim's algorithm (Minimum Spanning Tree)
- Huffman Coding (Optimal prefix code)
- Fractional knapsack problem
- Job Sequencing with deadline
- The Huffman coding is a greedy approach to obtain an optimal prefix-free binary code.
- In Huffman coding we save storage space for files by compressing files, while compression each symbol can be replaced by a unique binary string.
- Codewords can be of different lengths.
- Each codeword should be free of prefix, i.e. no codeword should be a prefix of any other code.
E - 40%; A - 30%; M-20%; N-5%; T-5%
Following Huffman tree can be constructed using the given frequencies.
Average word length is 2.
Running Time Complexity of Huffman coding Algorithm :
Time Complexity , T(n) = (Sort all the elements) + (Pick each element one by one and add them)
T(n) = O(nlogn) + O(n)
Hence T(n) = O(nlogn)
Let's suppose we're provided with weights and values for ‘n’ number of items. Now if we want to keep all these items in a knapsack(bag) whose capacity is W in such a way so that we get the maximum total profit value in the knapsack.
Mainly, we have two types of knapsack :
- 0/1 Knapsack : In 0/1 Knapsack we are not allowed to break items. Either we have to take the item completely or leave it.
- Fractional Knapsack : To maximize the profit value, in fractional knapsack we can break the items and take fractional profit from them.
Fractional Knapsack uses greedy approach to solve the problem, and 0/1 knapsack follows dynamic programming approach. Both approaches will give different answer to same problem.
Consider a knapsack with capacity = 20 and fractions are allowed.
Consider three items, say i1 , i2 and i3 with following weight and profit.
Find the maximized profit by using fractional knapsack.
Solution: Follow the given steps to solve the problem using fractional knapsack
Step 1 : First of all find the ratio of profit per unit and then sort all the items according to the ratio.
Step 2 : Now select them according to increasing ratio order and break them into parts if they have more weight than the capacity of knapsack.
Step 3 : Repeat step 2 until knapsack is full.
25/18 = 1.38
18/10 = 1.8
8/6 = 1.33
As object 2 has maximum per unit profit , so pick that first.
Current knapsack = 10 , profit = 18
Now next object 1 has maximum profit, so we will pick it. Weight of object is more than left over capacity of knapsack , hence we have to fragment it in fractions.
Remaining capacity = 10
So pick weight = 10 from I1 , hence profit from I1 = (10/18)*25
Now , knapsack is full
Total Profit = (1*18) + (10/18)*25 = 31.8
Time Complexity of Fractional Knapsack :
Time Complexity , T(n) = Sorting according to priority + Picking up objects
= nlogn + n
T(n) = O(nlogn)
Job Sequencing with deadline
Input : Given a number of jobs where every job have a deadline and have some profit associated with it, if the job is finished before the deadline. Every job takes single unit of your time, the minimum possible deadline for any job is 1.
Output : To get the maximum combined profit if only one job can be scheduled at a time.
Example : Find the maximum feasible profit to complete the jobs in their individual deadline.
The possible solutions are :
(J2,J3) -> profit = 350
(J2,J1) -> profit = 300
(J4,J3) -> profit = 400 <---- OPTIMAL
(J4,J1) -> profit = 350
and so on
There can be many solutions possible but optimal is where profit is maximum.
- Try to fill the slots from back to front.
- To find the exact location use searching algorithms.
- If required, sort the jobs according to the profit.
Example: Find the maximum possible profit to complete the jobs in their respective deadline.
1 2 3 4 5
Total Profit = 25 + 50 + 120 + 55 + 75 = 325
Time Complexity of Job Sequencing :
To identify the correct position of each job we need to conduct linear search for every job.
Time to search and place one job = O(n)
Time to search and place n jobs = O(n^2)
So, here we have discussed three techniques whihc uses Greedy approach, Spanning tree will be discussed in next post.
You can follow the detailed champion study plan for GATE CS 2022 from the following link: