Solved-Assignment VII- Solution

Description

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

Upload file Assignment7A.c

2. 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)

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

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

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

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

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

Upload file Assignment7B.c

3. A number n can be reduced to n/2 if n is divisible by 2; can be reduced to n/3 if n is divisible by 3; can be reduced to n/5 if n is divisible by 5; can be reduced to n/7 if n is divisible by 7; can be reduced to n – 1 if n is greater than 1. Write an efficient dynamic programming algorithm to find out the minimum steps required to reduce n to 1.

Upload file Assignment7C.c