Problem 1. (10 points: 2+2+2+4) Given an unsorted array of n unique integers, you need to...

Transcribed Image Text:

Problem 1. (10 points: 2+2+2+4) Given an unsorted array of n unique integers, you need to return the k smallest of them in sorted order, where k is between 1 and n. You come up with three algorithms to solve this problem: They are: A1: Sort the array in increasing order, then list the first k integers after sorting. A2: Build a min-heap from these n integers, and then call EXTRACT-MIN k times. A3: Use the linear time selection algorithm to find the kth smallest integer, then partition the array about that number, and finally sort these k smallest numbers. Assume that you are using the sorting algorithm with the best worst-case time complexity (e.g. merge-sort) in both A1 and A3. Answer the following questions. (a) Let Ti(n, k) denote the worst-case running time of Algorithm A1. Analyze Ti(n, k) using the O() notation, in terms of n and k. Justify your answer. (b) Let T₂(n, k) denote the worst-case running time of Algorithm A2. Analyze T₂(n, k) using the O() notation, in terms of n and k. Justify your answer. (c) Let T3(n, k) denote the worst-case running time of Algorithm A3. Analyze T3(n, k) using the O() notation, in terms of n and k. Justify your answer. (d) Among the three algorithms, which algorithm would you choose to find the k smallest integers in sorted order, and why? Problem 1. (10 points: 2+2+2+4) Given an unsorted array of n unique integers, you need to return the k smallest of them in sorted order, where k is between 1 and n. You come up with three algorithms to solve this problem: They are: A1: Sort the array in increasing order, then list the first k integers after sorting. A2: Build a min-heap from these n integers, and then call EXTRACT-MIN k times. A3: Use the linear time selection algorithm to find the kth smallest integer, then partition the array about that number, and finally sort these k smallest numbers. Assume that you are using the sorting algorithm with the best worst-case time complexity (e.g. merge-sort) in both A1 and A3. Answer the following questions. (a) Let Ti(n, k) denote the worst-case running time of Algorithm A1. Analyze Ti(n, k) using the O() notation, in terms of n and k. Justify your answer. (b) Let T₂(n, k) denote the worst-case running time of Algorithm A2. Analyze T₂(n, k) using the O() notation, in terms of n and k. Justify your answer. (c) Let T3(n, k) denote the worst-case running time of Algorithm A3. Analyze T3(n, k) using the O() notation, in terms of n and k. Justify your answer. (d) Among the three algorithms, which algorithm would you choose to find the k smallest integers in sorted order, and why?

Answer rating: 100% (QA)

a The worstcase running time of Algorithm A1 Tin k is Onlogn This is because the algorithm first sor... View the full answer