#3 Activity Scheduling with Revenue(15 pts) Activity scheduling problem from the greedy algorithm class: Suppose that different activities earn different amounts of revenue. In addition to their start and finish times s and f, each activity a,has revenue r, and our objective is now to maximize the total revenue: a EA In class you found out that we can't use a greedy algorithm to maximize the revenue from activities, and we noted that dynamic programming will apply. Here you will develop the DP solution following the same steps as for the other problems (e.g., problem 3 above), but you are responsible for the details. Your analysis in (a) and (b) below should mirror that of section 16.1 of CLRS. (a) (3 pts) Describe the structure of an optimal solution A for S, as defined in CLRS, and use a cut and paste argument to show that the problem has optimal substructure (b) (3 pts) Write a recursive definition of the value val[i.j] of the optimal solution for S, val[i,j] (c) (6 pts) Translate that definition into pseudocode that computes the optimal solution Hints: Create fictitious activities ao with fo- 0 and ant with Sn. Define tables val[0..n+1,0..n+1] for the values and activity[0..n+1,0..n+1], where activity[i.j] is the activity k that is chosen for A. Use a bottom-up approach, filling in the tables for smallest problems first and then by increasing difference ofj-i. (d) (2 pts) Write pseudocode to print out the set of activities chosen. (e) (1 pt) What is the asymptotic runtime of your solution including (c) and (d) #3 Activity Scheduling with Revenue(15 pts) Activity scheduling problem from the greedy algorithm class: Suppose that different activities earn different amounts of revenue. In addition to their start and finish times s and f, each activity a,has revenue r, and our objective is now to maximize the total revenue: a EA In class you found out that we can't use a greedy algorithm to maximize the revenue from activities, and we noted that dynamic programming will apply. Here you will develop the DP solution following the same steps as for the other problems (e.g., problem 3 above), but you are responsible for the details. Your analysis in (a) and (b) below should mirror that of section 16.1 of CLRS. (a) (3 pts) Describe the structure of an optimal solution A for S, as defined in CLRS, and use a cut and paste argument to show that the problem has optimal substructure (b) (3 pts) Write a recursive definition of the value val[i.j] of the optimal solution for S, val[i,j] (c) (6 pts) Translate that definition into pseudocode that computes the optimal solution Hints: Create fictitious activities ao with fo- 0 and ant with Sn. Define tables val[0..n+1,0..n+1] for the values and activity[0..n+1,0..n+1], where activity[i.j] is the activity k that is chosen for A. Use a bottom-up approach, filling in the tables for smallest problems first and then by increasing difference ofj-i. (d) (2 pts) Write pseudocode to print out the set of activities chosen. (e) (1 pt) What is the asymptotic runtime of your solution including (c) and (d)
