Greedy

Question 1

Greedy Algorithms

Answer 1

Useful for optimization problems for example maximizing or minimizing something.
Greedy algorithms may not always work/ give most optimal solution consider coins[]= {18, 1, 10} and amount =20. Here, greedy outputs coins required = while optimal is 2.
Another example is longest path.

Question 2

Greedy general structure

Answer 2

General structure:
getOptimal(Item arr[], int n):
  res=0
  while all items not considered:
        i = selectAnItem()
        if feasible(i):
             res = res +i
   return res

Question 3

Applications of Greedy Approach

Answer 3

Finding optimal solutions: Activity selection, fractional knapsack, job sequencing, Prim’s algo, Kruskal’s, Dijktra’s, Huffman coding.

Finding close to optimal solutions for NP Hard Problems like TSP.

Question 4

Job Sequencing Problem

Answer 4

Every job has a deadline that needs to be met in order to earn profit. Target is to maximize the profit.
Rules:
1. Every job takes 1 unit of time.
2. Only one job can be assigned at a time.
3. Time starts with 0.

Optimal greedy algorithm:
Sort jobs in decreasing order of profit and find the maximum deadline. Then initialize the result array with first job in the sorted list. Assign the latest possible slot.
for remaining (N-1) jobs: if this job cannot be added, ignore else add it to the latest possible slot.

Question 5

Infinite supply of following coins: 10, 5, 2, 1. Pay a given amount using minimum no of coins.

Answer 5

Consider the coins in decreasing order of value. Then check how many coins of greater elements can fit in the amount.

Question 6

Activity Selection Problem

Answer 6

Find maximum number of activities that can be performed on a single machine given a no of machine with {start time, end time) tuples. We can only perform a single task at a time. (Can also be solved by DP by converting into LICS problem.

Much better greedy solution: Sort the job tuples by the finish time (ascending). Initialize solution by first activity.
For remaining activities: if current activity overlaps with the last picked activity, ignore the current activity else add it to the solution. Time: O(nlogn)

Question 7

Fractional Knapsack

Answer 7

Given n items with tuples (weight, value) and the max capacity of knapsack, find the max value that can fit.

Sort the items by the ratio (value/weight) in decreasing order. Then for each element in sorted order: if item weight <= curr capacity: add element, reduce capacity or else take fraction value*(cap/wt) and return result.
Time: O(nlogn + n)