CS21003 Algorithms ICS29003 Algorithms Laboratory |
Autumn 2012, L-T-P: 3-1-0 L-T-P: 0-0-3 |

## Programming Assignment 3

The government of CSA (Confederation of States of Algorithmia) has built a new city with

nhouses. These houses need to be furnished before they are allocated to people. Mr. Contractor is appointed to take care of furnishing all thenhouses. Mr. Contractor knows the profitP_{i}that can be obtained from furnishing thei-th house. Assume that eachP_{i}is a positive integer in the range 1...M, whereMis the maximum profit that can be achieved from a single house.Mr. Contractor wants to allocate the duty to his two sons. Suppose that his first son bags a profit

S_{1}, and the second son bags a profitS_{2}. LetT=P_{0}+P_{1}+...+P_{n-1}be the total profit from all the houses. SoT=S_{1}+S_{2}. Mr. Contractor loves his first son twice as much as his second son (don't ask me why, it is his family matter). Therefore, he likes to ensure thatS_{1}is as close to 2S_{2}as possible. Ideally, we should haveS_{1}= 2T/ 3 andS_{2}=T/ 3, but this is not necessarily achievable, since there need not exist a subset of houses, the total profit from which is exactly 2T/ 3. So Mr. Contractor plans to divide the houses to his two sons in such a way that the absolute difference |S_{1}- 2S_{2}| is as small as possible.Since there are 2

^{n}subsets of houses, computing the sums of profits for all these subsets leads to an exponential amount of work. Mr. Contractor uses a dynamic-programming algorithm instead. He builds a two-dimensional tableA[i,j], whereiruns from 0 throughn-1, andjfrom 0 throughT. The elementA[i,j] stores the possibility whether a profit ofj(exactly) can be achieved from a subset of Houses 0,1,2,...,i. He initializes the first rowA[0,j] suitably. Fori>= 1, he computesA[i,j] as follows. IfA[i-1,j] stores a non-zero value, then the profitjcan be achieved from Houses 0,1,2,...,i-1. If so, he stores a non-zero value inA[i,j]. Otherwise, ifA[i-1,j-P_{i}] is a non-zero value, then by including Houseithe exact profitjcan be achieved. In this case too, he stores a non-zero value atA[i,j]. If both the above conditions fail, there is no way to achieve the exact profitjfrom Houses 0,1,2,...,i, and so he setsA[i,j] to 0.After the entire array

Ais prepared, Mr. Contractor looks at the last (that is, (n-1)-th) row to obtain the best partitioning of the houses to his two sons.Write a program to implement Mr. Contractor's algorithm.

- Read the number of houses (
n) and the profit bound for one house (M) from the user.- Populate the profit array
P[ ] with random integer entries in the range 1,2,...,M.- Initialize the d-p array
A(its first row).- Use Mr. Contractor's algorithm to populate the remaining rows of
A. For your future convenience, you may use two seperate non-zero values to differentiate between the two cases that make an entry inAnon-zero.- From the last row of
A, decide the sumsS_{1}andS_{2}which minimize the imbalance |S_{1}- 2S_{2}|.- Compute a subset (this need not be unique) of houses for the first son so that his total profit from this subset is exactly
S_{1}. The remaining houses go to the second son. Print the lists of houses for the two sons.## Sample Output

Enter number of houses (n) : 20 Enter profit bound (M) : 1000000 Profits are 618470 562398 186275 346181 972780 668101 188523 288997 866492 711633 80067 928084 299838 852255 232332 280079 180655 525332 707770 801006 Profit for first son : 6864839 Profit for second son : 3432429 Imbalance (S1 - 2*S2) : -19 First son gets houses 0 2 3 4 7 8 9 11 12 14 16 17 18 Second son gets houses 1 5 6 10 13 15 19## Remarks

The running time of this d-p algorithm is dominated by the time to prepare the table

A, and is Θ(nT), which is O(n^{2}M). So long asMis a constant, the input size is Θ(n), and this running time is a polynomial in the input size. If we allowMtoo to grow, then the input size is O(nlogM), and the running time is exponential in logM. However, if we choose to represent the individual profits in unary (instead of binary), the input size becomes O(nM), and the running time is polynomial in this unary input size. Such algorithms are calledpseudopolynomial-time.Mr. Contractor's problem is one of a class of NP-Complete problems (including the knapsack problem, the subset-sum problem, and the balanced-partitioning problem) that admit pseudopolynomial-time algorithms. These problems are called

weakly NP-Complete. Your Algo-II course would have a discussion on these problems.Let Mr. Contractor's sons furnish the houses. Meanwhile, the CSA government would plan for allocation of these houses to suitable families, and would be likely to face new computational problems. If needed, CSA government officials will again call for your help. Those may be future programming assignments for you.

## Submission Site