# Assignment VII Solution

\$30.00

Category:

## Description

1. Write a C program that finds ith order statistics of n elements in linear time.

1. You are given n elements. You can make a pair by taking any two elements from n elements; however, difference of the elements in pair must be less than or equal to a predefined number m. Finally you may end with at most n/2 pairs; however in final pair list any element can be included at most one time (it is ok if any element is not included for single time). Sum of final pair list calculate the sum of all elements in final pairs you formed. You want to maximize this sum. Write a efficient dynamic

program which will choose a final pair list such that sum of final pair list is maximized.

For example: 10, 3, 57, 15, 27, 35, 42, 50 is the list of numbers m=8 Then set of valid pairs are

(3,10), (10,15), (27,35), (35,42), (42,50), (50,57)

Final pair list can be

1. (3,10), (27,35), (42,50) (sum = 167)

2. (3,10),(35,42),(50,57) (sum = 197)

1. (3,10),(27,35),(50,57) (sum = 182)

2. (10,15), (27,35),(42,50) (sum = 179)

3. (10,15),(27,35,(42,50) (sum = 194)

4. (10,15),(35,42),(50,57) (sum = 209)

So final pair list which maximizes the sum is (10,15),(35,42),(50,57)