FUNDAMENTAL ALGORITHMS Homework #5

Due Monday March 8-th

1. Below is a list of integers. Please determine, without transforming the list into an actual tree, whether it represents a HEAP. While keeping the list in list form, implement the heapsort procedure on it and show the intermediary partially ordered lists generated by the algorithm until a fully ordered list is achieved.

64,42,39,31,20,30,40,19,33,50

2. Provide an algorithm, based on the heapsort algorithm, for finding the number second to the biggest, in a given list of keys. How many comparisons does your algorithm require in the worst case?
3. Provide an algorithm that rearranges all the numbers, in a given list of positive and negative integers, so that all the negative integers precede all the positive ones , using the minimum possible number of exchanges (the list need not be sorted, just separate between positive and negative numbers).
4. We are given two SORTED lists of n keys each. We want to find the median of the 2n keys. One possible way to do it is to merge the 2 lists into an ordered 2n list and find the median directly. How many comparisons does this method require. Can you think of another method which is O(logn)? Hint: Recal that a key cannot be the median if it is bigger or smaller than n+1 elements and take a clue from binary search.