page 28 http://mimoza.marmara.edu.tr/~msakalli/cse706_12/SkienaTheAlgorithmDesignManual.pdf

please make sure the answer is correct.

1. 1-5. [4] The knapsack problem is as follows: given a set of integers S = {s1, s2, . . . , sn}, and a target number T , find a subset of S which adds up exactly to T . For example, there exists a subset within S = {1,2,5,9,10} that adds up to T = 22 but notT = 23.

2. 1-7. [3] Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants c 2.

Knapsack Algorithm

Well it turns out that the algorithm we came up with during the 2nd half of class last Tuesday is really good. Here it is in all its glory

As promised I have cleaned it up and implemented it in c++ along with an implementation of quickSort to prep arrays for the algorithm. Try them out in the IDE of your choice.

Here is a recap of the problem were were trying to solve:

• Our knapsack has a threshold of T.
• Using only a predefined set of values, we want to add values to the knapsack and fill it to T without going over.
• If we cant match T exactly then we want to be as close as possible, and we want to be sure that if a solution exists, that our algorithm finds it.

Your solution to the problem was to work backwards from high values to low ones, and toss out any big clunky values that would put us over the limit along the way.

Assignment

So, does it work (is it correct)?

Is it efficient?

1. Proof

Prove that the algorithm is correct, or prove that it is incorrect.

1. To prove that it is correct, use the same process as in assignment 1 (as described in the Skiena book on p.11).
   1. Statement of what you are trying to prove
   2. Assumptions - things you are assuming to be true. For example, think of problem 1.7 where the constant c had to be >= 2 - that is an example of an assumption.
   3. Chain of reasoning and QED at the end
2. To prove that it is incorrect, provide a counter example where the algorithm does not yield a solution, even though you can demonstrate that one exists.

You may use the main.cpp file I provided to create your counter example - for example by modifying T, or modifying the initial array.

// // main.cpp #include  #include  #include "rickSort.h" using namespace std; void printArray(int arr[], int n, string s) { cout << "The " << s << " is: "; for (int i=0; i < n; i++) { cout << arr[i]; if (i != n-1) cout << ", "; } cout << endl << endl; } int main() { // int arr[] = {10, 16, 22, 4, 68, 11, 126, 1000, 7, 40, 8, 6, 0, 9, 1, 25}; Original array int arr[] = {10, 16, 22, 4, 68, 11, 126, 1000, 7, 40, 8, 6, 0, 9, 1, 25}; // Copy for experimentation int n = sizeof(arr)/sizeof(arr[0]); // sort ascending printArray(arr, n, "original array"); rickSort(arr, 0, n-1); // get it?? (rick rhymes with quick!) printArray(arr, n, "sorted array"); // fill knapsack int T = 176; // T for "threshold" // I also tried 89, 1096, 30, 136 int sum = arr[n-1]; int i = n-1; cout << "T is set to " << T << endl << endl; do { if (sum !=T) { if (sum > T) // toss it and get a new sum! { cout << "skipped " << sum << endl; i -= 1; sum = arr[i]; cout << "added " << sum << " to the knapsack" << endl; } else { if ((sum + arr[i - 1]) > T) // skip it! { cout << "skipped " << arr[i-1] << endl; i--; } else // add it to knapsack! { cout << "added " << arr[i-1] << " to the knapsack" << endl; sum += arr[i-1]; cout << "total is now " << sum << endl; i--; } } } else // knapsack filled!!! { cout << " T is: " << T << ", final sum is: " << sum << endl; cout << "The knapsack is perfectly filled!! " << endl; return 0; } } while(i > 0); cout << "knapsack is a close to being filled as possible, but there is no perfect solution" << endl; return 0; }