(a) (10 points) Suppose that you are asked to find the minimum and the maximum number...

 

Transcribed Image Text:

(a) (10 points) Suppose that you are asked to find the minimum and the maximum number in a given array of 16 elements. By using a linear scanning approach, you can find the min after 15 comparisons. Similarly, finding max can be achieved by using 15 comparisons based on a separate linear scanning pass over the input. Hence you'll need 30 comparisons by this approach to find both the min and the max. As Sabanci University students having taken CS301, you should never be satisfied with such an initial naive approach and question immediately if there could be a better approach. For some cases there may not be a better approach, however (as you may guess since now you are in an exam), there is a better approach for this specific case. Design a divide and conquer an algorithm that would use only 22 comparisons to find min and max of the given 16 numbers. (b) (5 points) Derive the recurrence for the number of comparisons C(n) required by your algorithm given in (a) for n inputs. C(n) = n = 2 n> 2 Give the expression for the case cases of the recurrence when n = 2, and when n> 2. )give solve the recurrence exactly (not asymptotically). You can assume that n is a power of two. (c) (5 points) Show that for n = 16, you have C(n) = 22. Act Go (d) (5 points) Solve the recurrence in part (a) to give an upper bound for C(n) as tight as possible. You can use any recurrence solution method that you want. (a) (10 points) Suppose that you are asked to find the minimum and the maximum number in a given array of 16 elements. By using a linear scanning approach, you can find the min after 15 comparisons. Similarly, finding max can be achieved by using 15 comparisons based on a separate linear scanning pass over the input. Hence you'll need 30 comparisons by this approach to find both the min and the max. As Sabanci University students having taken CS301, you should never be satisfied with such an initial naive approach and question immediately if there could be a better approach. For some cases there may not be a better approach, however (as you may guess since now you are in an exam), there is a better approach for this specific case. Design a divide and conquer an algorithm that would use only 22 comparisons to find min and max of the given 16 numbers. (b) (5 points) Derive the recurrence for the number of comparisons C(n) required by your algorithm given in (a) for n inputs. C(n) = n = 2 n> 2 Give the expression for the case cases of the recurrence when n = 2, and when n> 2. )give solve the recurrence exactly (not asymptotically). You can assume that n is a power of two. (c) (5 points) Show that for n = 16, you have C(n) = 22. Act Go (d) (5 points) Solve the recurrence in part (a) to give an upper bound for C(n) as tight as possible. You can use any recurrence solution method that you want.