CS 3343/3341
Analysis of Algorithms
Spring 2012 Recitation 7
Dynamic Programming, Etc. Partial Answers
Subset Sum Problem. We covered this problem in
Subset Sum. [I altered this page
on Sunday, Feb 26.]
Write as simple a program as you can manage that will
produce the same results as in the above page for the
subset sum problem. Notice that you've been given code to calculate the
array W. You will need to supply code to recover the
actual sum from W. (If you use an entirely different
program, I expect you to convince me that you wrote it yourself
and didn't find it on the Internet.)
First have your program
use the array A = {1,9,5,3,8}
and try to find numbers that add up to 13.
Use a work array of size 27. For this run only, print
the successive steps of the work array W.
As a second test, try
it out with the array A = {31,25,17,10,6,5,1}
and the sum 40. (Your work array W will
need to be larger than 27.)
Finally, use A =
{1728,1913,2285,2732,3260,3334,3645,4413,4666,4866,5085,5471,5712,8462,9197,9745};
and the sum 30622.
[The subset numbers are:
1728 1913 3260 3645 4413 4866 5085 5712.
Note that there are 216 = 65536 subsets altogether,
so a brute
force approach would be almost out of the question "by hand",
although not by computer. Even if you knew that the subset
contained 8 numbers, there are still C(16,8) =
16!/(8!*8!) = 12870 of these.]
Greedy Algorithms. Your text, starting on page 414,
has a great deal to say about greedy algorithms. We're not
going to do too much with them right now. A greedy
algorithm makes the best choice it can see at each
stage and hopes for the best overall result. In many cases
the result is optimum. ("Just go for it", is the greedy motto.)
The Huffman coding algorithm that you (supposedly) saw in
the Data Structures course was a greedy algorithm.
Later in the course we will have some greedy graph algorithms.
One simple greedy algorithm is the common way to make
change with coins of denominations {25,10,5,1}.
If you want any sum less than 99, just keep trying
the largest coin you can that is still <= the remaining sum
after subtracting coins already chosen. Thus to make up
67, you select in order 25, 25, 10, 5, 1, and 1.
Here, unlike the previous problem, we allow repetitions.
[It turns out that for these particular denominations, the
greedy strategy yields the smallest number of coins for a given
total. Note that it's essential to process the coins from
largest to smallest.]
Use the simple greedy strategy mentioned in the previous
paragraph to write a greedy program that will make
change for 93 cents. [You should use the greedy
strategy, and not an version of the dynamic programming
code in Problem 1.]
[The Roman numerals programs below
illustrate this greedy change-making strategy.]
Roman Numerals.
[Note: I was going to do more with Roman numerals, but a recent
newspaper report said that many of today's young people no longer
even know how to recognize this lovely archaic system.]
Conversion of an integer to Roman numerals can easily be
done with the same greedy strategy from problem 2. The trick is to have
"coins" in denominations of
A = {1000,900,500,400,100,90,50,40,10,9,5,4,1};.
Then each successive "coin" has one of the following
"names":
B =
{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};.
Write a greedy program similar to the one
in problem 2 above will also handle this
conversion. Just use the A array above to get a sum of
values for the "coins". Then concatenate the "names" of these
coins (from the B array) in order to get Roman numerals.
Test your program with the numbers 3894
and 3448. [For example, just by hand, the number
2496 = 1000+1000+400+90+5+1 and the Roman numeral
for this number is M+M+CD+XC+V+I = MMCDXCVI.
No dynamic programming is needed for this problem.]
[See
Several Roman Numeral Programs. Also
3894=MMMDCCCXCIV, 3448=MMMCDXLVIII.]
Other Denominations for Coins.
It turns out that for some coin denominations
the greedy strategy doesn't always yield the smallest number of
coins for a given amount. For this we need some version of
dynamic programming.
Using A = {25,20,10,5,1}, show that an amount
40 gives an example in
which the greedy strategy does not yield the smallest number of
coins. (No program is asked for here.)
[The greedy strategy gives
40 = 25+10+5, three coins,
whereas 40 = 20+20 is two coins.]
Smallest Number of Coins.
As you saw in problem 4 above, the greedy algorithm doesn't
always yield the smallest number of coins.
Make modifications to the subset sum algorithm in Problem 1
so that it will (1)allow repetitions, will (2)try all sums,
and will (3)keep
track of the number of "coins" (numbers) in a sum and reject
all but the smallest number of coins that is produced.
For condition (1) above, leave off the second condition in
the calcWork function.
For condition (2) above, leave off the
fourth condition in the calcWork function.
To handle condition (3) above, introduce another "counting"
array C parallel to the working array W.
(Or separate fields in a class or struct.)
The numbers in the C array let the algorithm keep track of the
least number of coins produced at each stage. If a new number is
less than the stored value, it replaces the table entry
with the new one, and otherwise is sticks with the old
table entry. (It might be convenient to set C[0] = 0, and
all other C values equal to +infinity, or maybe just a big
number, such as 10000.)
[Note that the Internet is saturated with "smallest number of coins"
programs, and that is the reason I want you to modify the
subset sum program for this purpose.]
Use A = {25,20,15,10,7,5,1} and a
sum of 40, as in Problem 4, for a trial run.
[40=20+20.]
There can be more than one way to represent
a sum with the least number of coins.
Use A = {25,21,13,10,7,4,1}, and a sum of 70
to get two different sums with 4 coins:
70=25+25+10+10, and 70=7+21+21+21.
(To get the second sum with the program as I have described
it, you can process the elements of A in the opposite order:
A = {1,4,7,10,13,21,25}.)
[Answers in the question.
Mr. Santacroce noted that there is a third way to
get a sum of 70: 70=25+25+13+7. My program wasn't searching for
all possible ways to get 70.
I was already surprised that there were 2 different
ways. Humm! I think that searching for all possible sums
might be intractable -- must think about this.]
In the same way get two different representations
of 64 as a sum of 4 coins.
[The two ways to get a sum of 64
with 4 coins are:
64=25+13+13+13 and 64=1+21+21+21.
Oops, another sum from Ms. Bleistein: 64=25+25+13+1.]
[The following page was given as an
additional extended hint to the above problem:
Hints for Rec 7,
Question 5.]
Oops! No problem 6 anymore!
Another weird problem, Newton's Method 2.
For this problem you will be using
Newton's method to find the root of
x2 + x - 1 = 0.
The positive root of this equation is
φ - 1 = 1 / φ,
where φ = 1.60803398875 is the golden ratio.
Plug f(x) =
x2 + x - 1 = 0 into
the formula for Newton's Method to get the iteration
formula. [Ans:
x1 =
(x02 + 1) / (2 x0 + 1).]
Plug x0 = 1 into the iteration
formula and get the answer
as a fraction in lowest terms, not as a real number.
[Ans: 2 / 3.]
Plug x0 = 2 / 3 back
into the iteration formula and get the answer again
as a fraction in lowest terms.
Try plugging in the result from iii above into
x0
one more time. [Final ans: 610 / 987.]
Now try it symbolically: plug
x0 = p / q into the
formula, getting the result as a fraction involving
p and q. Are you getting anything that
looks familiar?
[See
Weird Topic 11:
Newton's Method 2.}
Revision date:2012-03-15.
(Please use ISO
8601, the International Standard.)
