# 1. Give an algorithm for the following problem. Given a list of n distinct positive integers,… 1 answer below »

1. Give an algorithm for the following problem. Given a list of n distinct positive integers, partition the list into two subsists, each of size n/2, such that the difference between the sums of the integers in the two subsists is minimized. Determine the time complexity of your algorithm. You may assume that n is a multiple of 2.

2. Algorithm 1.7 (nth Fibonacci Term, Iterative) is clearly linear in n, but is it a linear time algorithm? In Section 1.3.1 we defined the input size as the size of the input. In the case of the nth Fibonacci term, n is the input, and the number of bits it takes to encode n could be used as the input size. Using this measure, the size of 64 is lg 64 = 6, and the size of 1,024 is lg 1,024 = 10. Show that Algorithm 1.7 is exponential-time in terms of its input size. Show further that any algorithm for computing the nth Fibonacci term must be an exponential-time algorithm because the size of the output is exponential in the input size. (See Section 9.2 for a related discussion of the input size.)