Week - 3

*Greedy Algorithm

1. Define the following terms and relate them to the interval scheduling problem Feasible solution - the solution that satisfies the problem constraint Here, the tasks included in the solution should be non-overlapping Optimal solution - the solution which maximizes (or) minimizes the objective criterion Here, the subset with maximum non-overlapping tasks is the optimal solution Objective criterion - Used for evaluating solutions and find the optimal one Here, no of tasks in the solution set is the criterion A Greedy strategy is applied to construct the solution. It is used for selecting the components Proposition used to verify the correctness Statement which evaluates to either true (or) false

2. Differentiate global and local optimal solution Global Optimal - Best possible solution Local Optimal - Good solution when compared to nearby solutions

3. Job scheduling Consider the problem of scheduling n jobs of known durations $t_{1}, t_{2},...,t_{n}$ for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. (The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.) Design a greedy algorithm for this problem. Does the greedy algorithm always yield an optimal solution? Schedule jobs in the increasing order of time Similar to Optimal Storage on Tapes

4. Identify the optimal substructure for the coin change problem. Write pseudocode of the greedy algorithm for the change-making problem, with an amount n and coin denominations d1 > d2 > ... > dm as its input. What is the time efficiency class of your algorithm? Let coins [m,i] denote the number of coins for providing change for the amount m using denomination i $coins[m,i] = coins[m,i+1] , 1+coins[m-di, i]$ def FindCoins_Greedy(denom, money, n): numCoins=0 for i in range(n): if(denom[i]<=m): numCoins = numCoins + (m/denom[i]) m= m % denom[i] if(m==0): break Time Complexity = O(n)

5. You are planning to rob banks. All banks are arranged in a circular manner. Which means, the first and last banks are neighbor to each other. Each bank has a certain amount of money stashed. Adjacent banks have a security system connected which will automatically contact the police if two adjacent banks were broken into on the same day, which is the only constraint stopping you from robbing each of them. Given a list of non-negative integers representing the amount of money of each bank, determine the maximum amount of money you can rob tonight without alerting the police. Return -1 when no banks are there. If array: [1, 2, 3] then output is 3, You cannot rob the first bank (money = 1) and then rob the last bank (money = 3), because they are adjacent banks. So here, you can rob any one bank. So the maximum possible money you can rob is from the last bank. If you adopt the greedy approach, sort the banks in decreasing order of amount, rob the bank with the max amount, next bank can be robbed only if it is not adjacent to the previously robbed banks. This may provide approximate solution but not global solution. The following procedure can help find the global solution. class MoneyHeist: def robMaximumMoney(self, nums): banks = len(nums) MAX = 0 if(banks==0): return -1 elif(banks==1): return nums[0] else: for j in range(2): opt = [0] * banks prev1=0 prev2=0 for i in range(j,banks-1+j): opt[i] = nums[i]+prev1 if nums[i]+prev1 > prev2 else prev2 prev1=prev2 prev2=opt[i] MAX = opt[banks-2+j] if opt[banks-2+j]>MAX else MAX return MAX