Greedy Algorithms (Part - 1) Study Notes for Computer Science Engineering

E - 40%; A - 30%; M-20%; N-5%; T-5%

Solution: 

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)

Fractional Knapsack

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. 

Example :

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.

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.

ALGORITHM :

• 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.

Solution :

          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.

Hence ,

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.