University of Maryland, College ParkCMSC 351hwk8-sol-ALL ANSWERS CORRECT-GRADED A.

Document Content and Description Below

1. One way to find the median of a list is to sort the list and then take the middle element. (a) Assume you use Bubble Sort to sort a list with 13 elements (i.e. n = 13). Exactly how many compariso... ns do you use (in the worst case)? Solution: n(n − 1) 2 = 13(13 − 1) 2 = 78 (b) Assume you use Mergesort to sort a list with 13 elements (i.e. n = 13). Exactly how many comparisons do you use (in the worst case)? Solution: 37 2. You can actually find the median by running a sorting algorithm and stopping early, as soon as you know the median. (a) Assume you use Bubble Sort to find the median of 13 elements (i.e. n = 13), but stop as soon as you know the median. Exactly how many comparisons do you use (in the worst case)? Solution: 12 + 11 + 10 + 9 + 8 + 7 + [Show More]

Last updated: 1 year ago

Preview 1 out of  pages