Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS566 Homework-3

(1) [20 pts.]  

Take as input a sequence of 2n real numbers. Design an

O(n log n) algorithm that partitions the numbers into n pairs,

with the property that the partition minimizes the maximum

sum of a pair.

For example, say we are given the numbers (1,3,5,9).

The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and

((1,9),(3,5)). The pair sums for these partitions are (4,14),

(6,12), and (10,8). Thus the third partition has 10 as

its maximum sum, which is the minimum over the three

partitions.

(2) [20 pts] You wish to store a set of n numbers in either a max-heap or a sorted array.

For each application below, state which data structure is better, or if it does not

matter. Explain your answers.

(a) Want to find the maximum element quickly.

(b) Want to be able to delete an element quickly.

(c) Want to be able to form the structure quickly.

(d) Want to find the minimum element quickly.

(3) [20 pts] Implement an external sort, which uses intermediate files to sort files bigger

than main memory. Why Mergesort is a better algorithm than heapsort or quicksort to base such an implementation

on? Test your program both on files with small records and on files with large

records.

(4) [20 pts.] Given the following file:

26,5,77,1,61,11,59,15,48,19  

Sort this file by hand using Heapsort and answer the following questions:

(a)    Draw the initial COMPLETE tree representation of the file BEFORE the HEAP is created.

(b)   Draw the initial heap.

(c)    Continue with the sort for two iterations PAST the initial heap – i.e., you pop off 77 and 61 from the root. NOW RESTRUCTURE THE HEAP AFTER 61 is popped – what is the NEW ROOT?

(5) [20 pts.] Use Quicksort as shown in class and sort the following file by hand and selectin the first element as the split element:

72,20,73,42,11,80,39,30,100,46,88,32,21

(a)    After the initial swapping, there are two subfiles – one to the left of 72 and one to the right of 72. Are they in order? 

(b)   Continue sorting the entire file until totally sorted. During the entire sort – what was the maximum number of inversions removed by a single comparison and swap?