1. Algorithmic Paradigms (25 marks) (a) Consider the activity selection problem. An instance is a set of proposed activities that wish to use a resource. Each activity A S is defined by a pair consisting of a start time s(A) (a non-negative number) and a finish time f(A) with f(A) > S(A). Two activities A and A are compatible if s(A) > f(A') or (A) = f(A). The problem is to select a set of as many activities as possible from S so that all of the selected activities are compatible with each other. Consider the following greedy algorithm. i. Input S, the set of available activities. ii. Choose an activity A e S such that the finish time s(A) is as small as possible. iii. Form a sub-problem S' from S by removing A and removing any activities that are incompatible with A. iv. Recursively choose a set of activities X' from S. v. Output the activity A together with the activities in X'. Prove that the worst case running time of the following greedy activity selection problem is O(rf), where n is the number of activities in the set S. (5 marks) (b) Modify the algorithm in the sub-question (a) to reduce the running time if it is known that a set of proposed activities has been already sorted with nondecreasing finish time. What would be the running time of this modified algorithm? Justify your answer. (5 marks) (c) Let S = {A1,..., An} be a set of weighted activities and each activity A e S has a positive integer value w(A). Assume that the activities are sorted by nondecreasing finish time so f(A1)