Lab Assignment #3 Solution

Description

Goals:

1. Understanding of dynamic programming.

2. Understanding of subset sums.

Requirements:

1. Design, code, and test a C program to compute subset sums for all possible cardinalities.

The input is to be read from standard input (which will be one of: a. keyboard typing, b. a shell redirect (<) from a file, or c. cut-and-paste. Do NOT prompt for a file name!). The first input line will have n, the number of positive integer values appearing on the subsequent lines, and m, the target value. Each of the remaining input lines will include one of the m sequence values (unordered).

The output is to include: a. the input, appropriately labeled, b. the dynamic programming table, and c. backtrace for a computed solution for every subset cardinality that has a solution.

2. Submit your program on Blackboard by 10:45 am (section 004) or 1:45 pm (section 003) on October 23. One of the comment lines should indicate the compilation command used on OMEGA.

Getting Started:

1. Suppose the input is:

7 25

1

3

4

6

7

10

25

There would be solutions of cardinality 1: { 25 } and 5: { 1 3 4 7 10 }.

2. You may modify existing code (e.g. http://ranger.uta.edu/~weems/NOTES2320/subsetSum.c ).

3. The cost function must include the cardinality as a parameter, but the ordering concepts in Notes 07.F are still useful.

4. Arrays are to be dynamically allocated.

5. Your solution must use dynamic programming.