Introduction to the Design and Analysis of Algorithms
(Textbook. Click for information.)
 CS 3343/3341
 Analysis of Algorithms
 Spring 2012
 Recitation 7
 Dynamic Programming, Etc.
    Week 7: Feb 28-Mar 01
Note: New Due Dates (after Spring Break)
 Due (on time): 2012-03-21  23:59:59
 Due (late):        2012-03-23  23:59:59

NOTE: Second change to full-credit due date, which is now Wednesday, March 21, so that you will have a chance to ask questions in class on March 20. The part-credit due date is unchanged, only two days later.

Recitation 7 should be submitted following directions at: submissions with deadlines
  • 2012-03-21  23:59:59 (that's Wednesday, 21 March 2012, 11:59:59 pm) for full credit.
  • 2012-03-23  23:59:59 (that's Friday, 23 March 2012, 11:59:59 pm) for 75% credit.

Subset Sum Problem. We covered this problem in Subset Sum. [I altered this page on Sunday, Feb 26.]
  1. 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.)

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

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

    3. Finally, use A = {1728,1913,2285,2732,3260,3334,3645,4413,4666,4866,5085,5471,5712,8462,9197,9745};
      and the sum 30622.

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

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

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.

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

Smallest Number of Coins. As you saw in problem 4 above, the greedy algorithm doesn't always yield the smallest number of coins.
  1. 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.]

    1. Use A = {25,20,15,10,7,5,1} and a sum of 40, as in Problem 4, for a trial run.

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

    3. In the same way get two different representations of 64 as a sum of 4 coins.

      [See Hints for Rec 7, Question 5 for some additional help with this question.]

  2. Oops! No problem 6 anymore!

Another weird problem, Newton's Method 2.
  1. 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.

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

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

    3. Plug x0 = 2 / 3 back into the iteration formula and get the answer again as a fraction in lowest terms.

    4. Try plugging in the result from iii above into x0 one more time. [Final ans: 610 / 987.]

    5. 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?

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