CS2223 Algorithms 
Homework 4 - B Term 2013

PROF. CAROLINA RUIZ 

Due Date: Friday Dec. 6th at 1:30 PM 
Submit all homework problems on myWPI
See course policy regarding late homework submissions

Homework Instructions:

• For this homework you must study:
  • Chapter 15 of your textbook.
  • Dynamic Programming materials posted on this course's Lecture Notes webpage.
  • Useful logarithm and exponential facts.
• This is an individual homework. No collaboration is allowed.
• SUBMISSION INSTRUCTIONS: Submit all homework problems on myWPI. No need to submit hardcopies of your solutions.
• Remember to show your work and explain your answers. Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.
• See the course webpage for the late homework submission policy.

Homework Problems:

---

1. (70 Points) Problem I. Weighted Interval Scheduling

   In this homework problem, you will implement the dynamic programming solution to the weighted interval scheduling problem described in Chapter 6 of Jon Kleinberg's and Éva Tardos' Algorithm Design textbook. Available at Prof. Kevin Wayne's Algorithms Course Webpage at Princeton University.

   • Chapter 6 - Dynamic Programming, pages 251-260.
   • Slides - Dynamic Programming. Part I, slides 6-15.

   After studying the above materials, you need to implement the algorithms in slides 6-15 inside the Python skeleton provided. You can make small modifications to the skeleton if needed to correct errors or make improvements.

   1. (5 points) Adapt the mergeSort code from HW2 Problem 5 to sort the list of jobs in ascending order by finish time.
   2. (5 points) Implement the LargestIndexCompatible function that constructs the list p[1...n], where p[j] = largest index i < j such that job i is compatible with j. See slide 8.
   3. (5 points) Implement the "brute-force" Compute_Opt(j) function based on the pseudo-code in slide 10.
   4. (5 points) Implement the "memoization" M_Compute_Opt(j) function based on the pseudo-code in slide 12.
   5. (5 points) Implement the "bottom-up" version, which we will name the Compute_Opt_Bottom_Up() function, based on the pseudo-code in slide 15.
   6. (5 points) Implement the Find_Solution(j) function that outputs the names of the jobs in the optimal solution based on the pseudo-code in slide 14.
   7. Consider the following input:

      n = 20
      JobsList = \
      [0,
      job('job1', 24, 28, 100 ), \
      job('job2', 16, 17, 98 ),  \
      job('job3', 2, 10, 16 ),   \
      job('job4', 20, 23, 16 ),  \
      job('job5', 4, 19, 86 ),   \
      job('job6', 28, 30, 36 ),  \
      job('job7', 22, 31, 18 ),  \
      job('job8', 18, 31, 13 ),  \
      job('job9', 3, 17, 5 ),    \
      job('job10', 17, 21, 6 ),  \
      job('job11', 14, 28, 14 ), \
      job('job12', 7, 21, 68 ),  \
      job('job13', 2, 10, 2 ),   \
      job('job14', 21, 29, 67 ), \
      job('job15', 17, 32, 40 ), \
      job('job16', 20, 34, 3 ),  \
      job('job17', 20, 29, 89 ), \
      job('job18', 25, 34, 80 ), \
      job('job19', 0, 8, 2 ),    \
      job('job20', 12, 20, 72 )  \
      ]
      

      1. (2 points) Use the prettyPrintJobs function provided in the skeleton to print the above set of job requests. Include the printout in your report.
      2. (2 points) Use your implementation of MergeSortJobs to sort the above JobsList in ascending order of finish time, SortedJobsList. Use the prettyPrintJobs function provided in the skeleton to print the sorted list. Include the printout in your report.
      3. Starting with SortedJobsList, run each of the following combinations of functions
         1. (2 points) Compute_Opt(n)
         2. (2 points) M_Compute_Opt(n),then Find_Solution(n), and then prettyPrintJobs()
         3. (2 points) Compute_Opt_Bottom_Up(n)then Find_Solution(n), and then prettyPrintJobs().
         4. (4 points) Compare the results. If they all produce the same optimal solution, include this solution in your report. Verify that the solution is indeed optimal. Show your work. If they produce different solutions, check your code.
   8. Experimental Runtime Comparison.
      1. (3 points) Implement a GenerateTestInput(n) function that generates a list JobsList of n job requests. This list should satisfy the following properties:
         • JobsList[0] = 0.
         • For all i, 1 <= i <= n:
           • JobsList[i].name = 'job'i.
           • JobsList[i].start = i
           • JobsList[i].finish = i + 3
           • JobsList[i].value = 10
           (The generated set of job requests will look like that in slide 11, except that here job1 starts at time 1 instead of time 0.)
      2. Use that function with values of n = 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000. For each of the resulting JobLists do:
         1. (5 points total) Run Compute_Opt(n), timing its execution.
         2. (5 points total) Run M_Compute_Opt(n), timing its execution.
         3. (5 points total) Compute_Opt_Bottom_Up(n), timing its execution.
      3. (3 points) Include those running times in your report. Plot a graph comparing those running times across the 3 algorithms. The x-axis of the plot should be the size of the input n, and the y-axis should be the execution time for each of the 3 algorithms.
      4. (5 points) Discuss whether or not the curves in your plot reflect the asymptotic behavior analysis presented in the slides for the runtime of the above functions.

   ---

2. (60 Points) Problem II. Coin Changing

   Consider the coin changing problem: Given coin denominations and an amount to be paid, devise a method to pay that amount using the fewest possible number of coins.

   When we study greedy algorithms, we'll see that the greedy cashier's strategy (i.e., at each iteration we add a coin of the largest denomination that does not take us past the amount to be paid) produces an optimal solution IF the coin denominations are those of the US coins (i.e., 1, 5, 10, 25, and 100 cents). However, for other denominations, this greedy cashier's strategy might not be optimal. For example, if the coin denominations are {1, 10, 21, 34, 70, 100}, and the amount to be paid is 140 cents then the greedy cashier strategy will produce {100, 34, 1, 1, 1, 1, 1, 1} for a total of 8 coins, when the optimal answer is {70, 70} with a total of 2 coins.

   In this problem you are asked to provide a dynamic programming solution to the coin changing problem that always produces an optimal solution (i.e., minimum number of coins) regardless of the coin denominations.

   Input:

   • An array denominations[1..n] containing the n coin denominations d₁,...,d_n that you can use (for example, [1, 10, 21, 34, 70, 100], in this case n=6). You can assume that this array is already sorted in increasing order (with no repetitions, of course). You can also assume that you have an unlimited number of coins of each denomination.
   • The amount M that you need to pay (in the example above, M = 140 cents).
   You can assume that all the coin denominations and M are positive integer numbers.

   Output:

   • The optimal (minimum) number of coins needed to make change for M (in the example above where M=140, the optimal number of coins is 2).
   • The number of coins of each denomination used in the optimal solution (in the example above where M=140, the optimal answer is 2 coins of 70 cents. Note that in this example only one denomination was used, but in the general case more denominations might be used). In case that more than one optimal solution exists, output just one of them.

   Solve this problem following the steps below.

   1. (30 Points) Dynamic Programming Solution. Design a dynamic programming solution to this problem. Explain in detail:
      1. (10 points) how you plan to divide this problem into subproblems,
      2. (5 points) in what order you plan to solve the subproblems so that the solutions to smaller subproblems are available to larger subproblems, and
      3. (5 points) how you plan to use the solutions of these subproblems to produce a solution to the original problem.
      4. (10 points) At each stage argue decisively that your solution is correct.

      Hint: Consider using a 2-dimensional array OPT[1..n][0..M], where OPT[i,j] = the minimum number of coins that are needed to make change for j cents using only the first i coin denominations d₁,...,d_i, where 1 ≤ i ≤ n, and 0 ≤ j ≤ M (both i and j are integer numbers).

      Find a recurrence relation that expresses the solution of OPT[i,j] in terms of the solutions of slightly "smaller" problems (i.e., other cells in the matrix OPT whose values can be calculated before). Include suitable boundary conditions for the recurrence relation. Based on this, determine in what order you'll calculate the values of the cells in OPT. Explain.

   2. (15 Points) Algorithm. Write a dynamic programming algorithm (in detailed pseudo-code) implementing the solution you designed above.

   3. (15 Points) Time Complexity. Determine the asymptotic running time of your dynamic programming algorithm above, as a function of the input array size n and M. Give the simplest possible big Theta expression for the running time.

   ---