Suppose we want to make change for 10 cents, using the least number of coins of...

• 
  • 
    
    • 
      
      • 
        
        • 
          
          • 
            
            • 
              
              • 
                

Transcribed Image Text:

Suppose we want to make change for 10 cents, using the least number of coins of denominations 1¢, 3e, 4e and 7e. Apply a dynamic programming algorithm to get an optimum solution for the above problem (there is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming). Show the results of each step of the algorithm. 11. (10 points) Use the dynamic programming learned in class to develop a solution to the Longest Common Sequence (LCS) between the pair of strings (messo, msis). Show the content of the data structure used by the dynamic programming algorithm. Suppose we want to make change for 10 cents, using the least number of coins of denominations 1¢, 3e, 4e and 7e. Apply a dynamic programming algorithm to get an optimum solution for the above problem (there is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming). Show the results of each step of the algorithm. 11. (10 points) Use the dynamic programming learned in class to develop a solution to the Longest Common Sequence (LCS) between the pair of strings (messo, msis). Show the content of the data structure used by the dynamic programming algorithm.

Answer rating: 100% (QA)

1 Optimal solution for 10 cents with denominations le 3c 4... View the full answer