Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343
 Analysis of Algorithms
 Fall 2012
 Recitation 11 
 Graph Rep, Etc. 
    Week 11: Nov 06-Nov 08
 Due (on time): 2012-11-12  23:59:59
 Due (late):        2012-11-16  23:59:59

Recitation 11 should be submitted following directions at: submissions with deadlines
  • 2012-11-12  23:59:59 (that's Mon, 12 Nov 2012, 11:59:59 pm) for full credit.
  • 2012-11-16  23:59:59 (that's Fri, 12 Nov 2012, 11:59:59 pm) for 75% credit.

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).

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.]

  1. 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.]
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

Then each successive "coin" has one of the following "names":

  1. 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.]

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