(Activity problem)

Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence (16.2). Have your algorithm compute the sizes c[i,j]c[i,j] as defined above and also produce the maximum-size subset of mutually compatible activities. Assume that the inputs have been sorted as in equation (16.1). Compare the running time of your solution to the running time of GREEDY-ACTIVITY-SELECTOR.

Problem 7. Analyze the runtime of the dynamic programming algorithm for the activity selection problem (see class on 10/30 or CLR(S) 16.1). Given the array c filled in by the algorithm and a two-dimensional array d such that dli]jl gives the value k that maximizes cli][k ck1, give pseudocode to print the indices of the selected activities. Lastly, how would the algorithm have to be adapted if activities were assigned a value and the task was to select not the largest subset but the subset with the greatest value? Problem 7. Analyze the runtime of the dynamic programming algorithm for the activity selection problem (see class on 10/30 or CLR(S) 16.1). Given the array c filled in by the algorithm and a two-dimensional array d such that dli]jl gives the value k that maximizes cli][k ck1, give pseudocode to print the indices of the selected activities. Lastly, how would the algorithm have to be adapted if activities were assigned a value and the task was to select not the largest subset but the subset with the greatest value