CS 3343
Analysis of Algorithms
Fall 2012 Recitation 11
Graph Rep, Etc. Partial Answers
See
Hints and
Help With Recitation 11 for help with some of the
problems people in the recitation sessions were having.
In-class Problems:
The first problems will be made accessible during the
Recitation hour:
Rec 11,
In-Class Problems
(password protected, use "CS3343" without quotes for "User Name" and
password from class just before the recitation). Answers:
Rec 11,
In-Class Answers.
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 of course 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 Recitation 10.]
[This is straightforward, basically
simpler than the next problem.]
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.
You must allow repetitions, and once again it's important
to have the elements of A appear in decreasing order.
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.
[You must use the two arrays above in your program.
No dynamic programming is wanted for this problem.]
[See
Several Roman Numeral Programs. Also
3894=MMMDCCCXCIV, 3448=MMMCDXLVIII.]
Revision date:2012-11-01.
(Please use ISO
8601, the International Standard.)
