Homework 6 (assigned May 6, due May 13)

Reading: CLRS sections 15.1, 15.3, 15.4

Written assignment: Solve the following exercises and problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both exercises and problems.

"Do" Exercises (not to be handed in):

1. Coin changing problem
   Design a dynamic programming algorithm for the following version of the coin changing problem:
   Given coins of denominations d[1], d[2], ..., d[n], we wish to make change for an amount A, that is, we wish to find a set of coins whose total value is A, but we are allowed to use each denomination at most once. For instance, if the denominations are 1, 5, 10, 20, then we can make change for 16 = 1 + 5 + 10 and for 31 = 1 + 10 + 20 but not for 40 (because we cannot use 20 twice).
   Input: Positive integers d[1], d[2], ..., d[n]; another positive integer A.
   Output: Is it possible to make change for A, using each denomination d[i] at most once?
   1. Give an O(nA) dynamic programming algorithm to solve this problem.
   2. Apply your algorithm to the input denominations 10, 5, 2, 1, and amount A = 12 and show the output on this input.
   Note: This problem can be viewed as a boolean variation of the knapsack problem.

2. Subset-sum problem
   Given an array A[1..n] of positive integers, and a positive integer k, determine if there exists a subset S of the array indices {1, 2, ..., n} such that the sum of the array elements A[i], where i is in S, equals k.

Problems (to be handed in):

1. 0/1 knapsack problem
   We are given n items and a knapsack of capacity W > 0. Each item i has a weight w_i > 0 and a value v_i > 0. The values v_i are real numbers; the weights w_i and W are integers.
   The problem is to find a subset S ⊆ {1,..., n} which maximizes the sum
           ∑v_k for k ∈ S
   subject to the constraint
           ∑w_k ≤ W for k ∈ S.
   The dynamic programming algorithm for the knapsack problem presented in class follows. The input is an array of weights w[1.. n], an array of values v[1.. n], the number of items n, and a capacity W.
   
   dynamic-knapsack(w[1.. n], v[1.. n], n, W)
   01 for i <- 0 to n
   02       do m[i, 0] <- 0
   03 for j <- 1 to W
   04       do m[0, j] <- 0
   05 for i <- 1 to n
   06       do for j <-1 to W
   07                 do if j < w[i] then m[i, j] <- m[i-1, j]
   08                      else m[i, j] <- max{m[i-1, j], v[i] + m[i-1, j-w[i]]}
   09 return m
   1. Apply the algorithm dynamic-knapsack to the following input values w_i and v_i. The capacity W = 5; n = 4. Your output should be a table m of values. Show the output table m. What is the maximum value of an optimal subset? (10 points)

      item i	weight wi	value vi
      1	2	12
      2	1	10
      3	3	20
      4	2	15

   2. Find the composition of an optimal subset for the above input by tracing back the computations of the entry (4, 5) (i.e., the bottom right cell) in your output table. Show your work. (10 points)
   3. Write pseudocode for an algorithm that finds the composition of an optimal subset from the table m output by the algorithm dynamic-knapsack. What is the running time of your algorithm? (10 points)

2. Checkboard problem
   Problem 15-6 on CLRS page 368. Break your solution into the following parts:
   1. Define the entries of your table, i.e., what does your table compute? (5 points)
   2. State the recurrence for entries of your table in terms of smaller subproblems. (10 points)
   3. Write the solution for the base case (i.e., smallest subproblems). (2 points)
   4. Write pseudocode for an algorithm to fill the remaining entries of your table. (10 points)
   5. Analyze the running time of your algorithm. (3 points)

3. Sorting in linear time
   
   1. Exercise 8.2-1 on CLRS page 170. Use the pseudocode for Counting-Sort on CLRS page 168. (5 points)
   2. Problem 8-3, part a, on CLRS page 179. (15 points)

   ---

   Gerry Brady
   Wednesday May 7 02:47:32 CDT 2008