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

please make sure the answer is correct.

1. 1-5. [4]

2. 1-7. [3] .

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  T) // toss it and get a new sum! { cout  T) // skip it! { cout  0); cout   n a, b 1 and b=-5 fod.ro. S i4-)