Foundation of algorithm

#13

Edit View Go Store Window Help Foundations of Alg Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is maxi- mized. You may assume that n is a multiple of 2 11. Write a nonrecursive algorithm for Mergesort (Algorithms 2.2 and 2.4). 12. Show that the recurrence equation for the worst-case time complexity for Mergesort (Algorithms 2.2 and 2.4) is given by when n is not restricted to being a power of 2 13. Write an algorithm that sorts a list of n items by dividing it into three sublists of about n/3 items, sorting each sublist recursively and merging the three sorted sublists. Analyze your algorithn, and give the results under order notation. Sections 2.3 14. Given the recurrence relation ) +10n for n > 1 T(n)-TI, T(1) = 1 find T(625). Back to page 1,161 Page 193 9 pages left in this chapter