CS 3343/3341: Recitation 7, Question 5

CS3343/3341
Analysis of Algorithms
Spring 2012

Recitation 7, Question 5
Extended Hints

Initial Question: Recently a student asked the following question, which is also on the "Questions" page (I made a number of editing changes):

I'm really confused about question 5 on recitation 7. We are first to take out the second condition from calcWork (i.e. (W[k] != a)), and also the fourth condition from calcWork (i.e. (W[k + a] == -1)). Then we are to make another array C that runs "parallel" to the array W. After that, I'm lost as to what to do.
After taking off the two conditions and running the function say on A = {1,9,5,3,8}, with a work array of 27 and trying to find sums that add up to 13, the function doesn't seem to work well and gives me this as a result: W = {0,1,1,3,3,3,3,3,8,8,8, (all 8s) }. I don't know what I'm supposed to do with that information and how to tie in the C array to work parallel with W. I see that I'm supposed to find the least count of coins to add up to a certain number, but how do I do that with a modification of the calcWork function?

Comments: This data is not a particularly interesting choice for the "minimum coins" problems, but let's go with it anyway. Here is the original output of the subset sum program ,showing the process of construction the W array. Notice that we are using each number (or "coin") at most once, and once a location in W is changed from -1, that location is never changed again.

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1}: 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9}: 0 1 -1 -1 -1 -1 -1 -1 -1 9 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5}: 0 1 -1 -1 -1 5 5 -1 -1 9 9 -1 -1 -1 5 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5,3}: 0 1 -1 3 3 5 5 -1 3 9 9 -1 3 3 5 5 -1 3 3 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5,3,8}: 0 1 -1 3 3 5 5 -1 3 9 9 8 3 3 5 5 8 3 3 -1 8 8 8 8 -1 8 8

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1}: 0 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9}: 0 1 -1 -1 -1 -1 -1 -1 -1 9 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5}: 0 1 -1 -1 -1 5 5 -1 -1 9 9 -1 -1 -1 5 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5,3}: 0 1 -1 3 3 5 5 -1 3 9 9 -1 3 3 5 5 -1 3 3 -1 -1 -1 -1 -1 -1 -1 -1 {1,9,5,3,8}: 0 1 -1 3 3 5 5 -1 3 9 9 8 3 3 5 5 8 3 3 -1 8 8 8 8 -1 8 8

For example, notice that W[16] = 8 above means that the last number we added in to get a sum of 16 was 8. Going back to W[16-8], we get W[8] = 5, so the last number added in to get a sum of 8 was 5. Then W[8-5] = w[3] = 3, shows that the last (=first) number added in to get a sum of 3 was 3. Hence 16 = 8 + 5 + 3.

Now do as the student did, and run the same program, eliminating two conditions, so that each number ("coin") can be used any number times, and each new result for the W array overwrites the previous result. Then building the W array goes in the following steps:

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1}: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 {1,9}: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 {1,9,5}: 0 1 1 1 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 {1,9,5,3}: 0 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 {1,9,5,3,8}: 0 1 1 3 3 3 3 3 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 {1}: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 {1,9}: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 {1,9,5}: 0 1 1 1 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 {1,9,5,3}: 0 1 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 {1,9,5,3,8}: 0 1 1 3 3 3 3 3 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8

The last line above is what the student got, so his program may be working at this stage.

Notice that this table is giving real information, so that the entry W[20], and other entries W[12], and W[4], show that 20 = 8+8+3+1.

Question 5: Here, along with each W (for "Work") entry, you are also to maintain a C (for "Count") entry. The C value gives the count of the smallest number of coins needed so far. In case a new count is equal or even greater than the old one, we leave both W and C alone for that index. In case the count of coins is less than the number stored in the C array, put the new (better) count into C, and the new value (last number added in) into the W array. If you do that for this example, you get the following data. (The diagram shows at each stage, the W array with the C array below it in red. In the C array, 99 stands for +∞.)

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 {1}: W: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Count: C: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 {1,9}: W: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Count: C: 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10 {1,9,5}: W: 0 1 1 1 1 5 5 5 5 9 9 9 9 9 5 5 5 5 9 9 9 9 9 5 5 5 5 Count: C: 0 1 2 3 4 1 2 3 4 1 2 3 4 5 2 3 4 5 2 3 4 5 6 3 4 5 6 {1,9,5,3}:W: 0 1 1 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 Count: C: 0 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 4 3 2 3 4 3 4 3 4 5 4 {1,9,5,3,8}W:0 1 1 3 3 5 5 5 8 9 9 8 3 8 5 5 8 8 9 9 8 3 8 5 8 8 8 Count: C: 0 1 2 1 2 1 2 3 1 1 2 2 2 2 2 3 2 2 2 3 3 3 3 3 3 3 3

Possible #s <-------------------- W Array Index ----------------------------------------> in sum 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Initial: 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99 99
{1}: W: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Count: C: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
{1,9}: W: 0 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 Count: C: 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10
{1,9,5}: W: 0 1 1 1 1 5 5 5 5 9 9 9 9 9 5 5 5 5 9 9 9 9 9 5 5 5 5 Count: C: 0 1 2 3 4 1 2 3 4 1 2 3 4 5 2 3 4 5 2 3 4 5 6 3 4 5 6
{1,9,5,3}:W: 0 1 1 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 9 9 9 3 3 5 5 5 3 Count: C: 0 1 2 1 2 1 2 3 2 1 2 3 2 3 2 3 4 3 2 3 4 3 4 3 4 5 4
{1,9,5,3,8}W:0 1 1 3 3 5 5 5 8 9 9 8 3 8 5 5 8 8 9 9 8 3 8 5 8 8 8 Count: C: 0 1 2 1 2 1 2 3 1 1 2 2 2 2 2 3 2 2 2 3 3 3 3 3 3 3 3

Let's look at a getting a total of 20, just as an example:

With just a single coin of value 1, we get a sum of 20 by taking 20 1-coins. We see that in the line labeled with "{1}:" and with the count of 20 below the entry of 1, under index 20.
The next line down add a second coin with value 9. Here, under the index 20, we get 20 = 9+9+1+1, for a count of 4. Taking new coins with values 5 and 3 doesn't give any fewer coins.
Now suppose you have gotten to the last line, where there are coins with values 1, 9, 5, 3, and 8. During processing, when we get to index 20, working with the coin value of 8, the old W entry is 9 and C entry is 4. Now take 20-8 = 12 and look at the entry under 12: W is 3 and C is 2, so one more coin will give a count of 3, which is an improvement over the old count of 4. So we set W[20] = 8 and C[20] = 3. This means we can get to 20 with 3 coins, namely 8, plus 3 from the entry W[12], plus 9 from the entry W[9]. So 20 = 8+3+9.
Notice that when we started processing the value 5, at the entries for 20 we would have checked the value W[15] = 5 and C[15] = 3. This means that we could get to 20 with 4 coins, namely 20=5+5+9+1, but the count of 4 coins is not better than the 4 coins we already had with 20=9+9+1+1, so these new values don't replace the old. (We could replace them, if we wanted to write the code that way.)

Revision date: 2012-03-15. (Please use ISO 8601, the International Standard.)