Lecture- (Greedy Algorithms)

Prévia do material em texto

Analysis of Algorithms – Know Well but need revision
Lecture – 12
Greedy Algorithms:
A greedy algorithm, as the name suggests, always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.
· A Greedy algorithm is one of the problem-solving methods which takes optimal solution in each step. 
· The Greedy algorithm attempts to take the best in each step and it doesn't care about the overall result. 
· Greedy Approach - "Living in the present. Don't overthink about the future".
Greedy is a strategy that works well on optimization problems with the following characteristics:
1. Greedy-choice property: A global optimum can be arrived at by selectin g a local optimum.
2. Optimal substructure: An optimal solution to the problem contains an optimal solution to subproblems. 
The second property may make greedy algorithms look like dynamic programming. However, the two techniques are quite different.
Activity Selection Problem:
Given a set of n activities with their start and finish times, we need to select maximum number of non-conflicting activities that can be performed by a single person, given that the person can handle only one activity at a time." The Activity Selection problem follows Greedy approach i.e. at every step, we can make a choice that looks best at the moment to get the optimal solution of the complete problem.
Our objective is to complete maximum number of activities. So, choosing the activity which is going to finish first will leave us maximum time to adjust the later activities. This is the intuition that greedily choosing the activity with earliest finish time will give us an optimal solution. By induction on the number of choices made, making the greedy choice at every step produces an optimal solution, so we chose the activity which finishes first. If we sort elements based on their starting time, the activity with least starting time could take the maximum duration for completion, therefore we won't be able to maximise number of activities.
Some points to note here:
· It might not be possible to complete all the activities, since their timings can collapse.
· Two activities, say i and j, are said to be non-conflicting if si >= fj or sj >= fi where si and sj denote the starting time of activities i and j respectively, and fi and fj refer to the finishing time of the activities i and j respectively.
· Greedy approach can be used to find the solution since we want to maximize the count of activities that can be executed. This approach will greedily choose an activity with earliest finish time at every step, thus yielding an optimal solution.
Algorithm:
Example: In this example, we take the start and finish time of activities as follows:
start = [1, 3, 2, 0, 5, 8, 11]; finish = [3, 4, 5, 7, 9, 10, 12] 
 
 In this example, in all the activities 0, 1, 4 and 6 get selected, while others get rejected.
Time Complexity Analysis:
Following are the scenarios for computing the time complexity of Activity Selection Algorithm:
· Case 1: When a given set of activities are already sorted according to their finishing time, then there is no sorting mechanism involved, in such a case the complexity of the algorithm will be O(n)
· Case 2: When a given set of activities is unsorted, then we will have to use the sort() method defined in bits/stdc++ header file for sorting the activities list. The time complexity of this method will be O(nlogn), which also defines complexity of the algorithm. (The time complexity in this case will depend on the sorting algorithm used).
Real-life Applications of Activity Selection Problem:
Following are some of the real-life applications of this problem:
· Scheduling multiple competing events in a room, such that each event has its own start and end time.
· Scheduling manufacturing of multiple products on the same machine, such that each product has its own production timelines.
· Activity Selection is one of the most well-known generic problems used in Operations Research for dealing with real-life business problems.
References:
https://iq.opengenus.org/activity-selection-problem-greedy-algorithm/
https://www.studytonight.com/data-structures/activity-selection-problem
Coin Change Problem:
Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Pakistani currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?
The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0. 
Example
coins[] = {5,10,20,25}
value = 50
Possible Solutions
{coin * count}
{5 * 10} = 50 [10 coins]
{5 * 8 + 10 * 1} = 50 [9 coins] goes on.
{10 * 5} = 50 [5 coins]
{20 * 2 + 10 * 1} = 50 [3 coins]
{20 * 2 + 5 * 2} = 50 [4 coins]
{25 * 2} = 50 [2 coins]
etc etc
Best Solution
Two 25 rupees. Total coins two.
25 * 2 = 50
Minimum Coin Change Problem Algorithm
1. Get coin array and a value.
2. Make sure that the array is sorted.
3. Take coin[i] as much we can.
4. Increment the count.
5. If solution found,
    break it.
6. Otherwise,
     follow step 3 with the next coin. coin[i+1].
4. Finally, print the count.
Example
coin[] = {25,20,10,5}
value = 50
Take coin[0] twice. (25+25 = 50).
Total coins = 2 (25+25)
Example
coin[] = {25,20,10,5}
value = 70
Take coin[0] twice. (25+25 = 50).
If we take coin[0] one more time, the end result will exceed the given value. So, change the next coin.
Take coin[1] once. (50 + 20 = 70).
Total coins needed = 3 (25+25+20).
In this approach, we are not bothering about the overall result.
We just pick the best option in each step and hoping that it might produce the best overall result.
Hence, this method called as the greedy approach.
When does the above greedy algorithm fail?
Let's take this scenario.
coins[] = {25,20,10,5}
value = 40
The greedy solution will be 25+10+5 [3 coins].
But the optimal solution will be 20+20 [2 coins].
So, we can't guarantee that the greedy algorithm always produces the overall best result.
Note that above approach may not work for all denominations. For example, it doesn’t work for denominations {9, 6, 5, 1} and V = 11. The above approach would print 9, 1 and 1. But we can use 2 denominations 5 and 6. For general input, we use dynamic programming approach.
Time Complexity :
What will the time complexity of the implementation? First of all, we are sorting the array of coins of size n, hence complexity with O(nlogn). Overall complexity for coin change problem becomes O(n log n) + O(amount (n)).
References:
https://www.geeksforgeeks.org/greedy-algorithm-to-find-minimum-number-of-coins/
https://www.log2base2.com/algorithms/greedy/greedy-algorithm.html