Consider a sequence of 2n values as input. Give an efficient algorithm that partitions the...

 

Transcribed Image Text:

Consider a sequence of 2n values as input. • Give an efficient 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 (2,3,5,9). The possible partitions are ((2,3),(5,9)), ((2,5), (3,9)), and ((2,9),(3,5)). The pair sums for these partitions are (5,14), (7,12), and (11,8). Thus the third partition has 11 as its maximum sum, which is the minimum over the three partitions. Give and justify its complexity. Consider a sequence of 2n values as input. • Give an efficient 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 (2,3,5,9). The possible partitions are ((2,3),(5,9)), ((2,5), (3,9)), and ((2,9),(3,5)). The pair sums for these partitions are (5,14), (7,12), and (11,8). Thus the third partition has 11 as its maximum sum, which is the minimum over the three partitions. Give and justify its complexity.

Answer rating: 100% (QA)

To solve this problem efficiently you can sort the input sequence in ascending order Then pair the s... View the full answer