Q1 Coin change
CSC373 Fall’20 Tutorial 3 Tuesday, Sept. 29, 2020
Consider the problem of making change with fewest possible coins.
Input: A positive integer A, and positive integer “denominations” d[1] < d[2] < . . . < d[m].
Output: A list of “coins” c[1 . . . n] is feasible when each c[i] is in d, repeated coins are allowed (i.e. it is possible that c[i] = c[j] with i ̸= j), and ni=1 c[i] = A. Output the smallest n such that a feasible list of coins of size n exists. If no feasible solution exists, output n = 0.
Example: If we only have pennies, nickels, dimes and quarters (i.e. d = [1, 5, 10, 25]) to make change for 30g (i.e. A = 30), then the output should be n = 2 (with, e.g., c = [5,25]), and not n = 3 (with, e.g., c = [10,10,10]). If the input was d = [5,10,25] and A = 52, then the output would be n = 0 as no solution exists.
We want to use dynamic programming to solve this problem.
(a) Define an array which stores the necessary information needed from various subproblems. Clearly identify what each entry of your array means.
(b) Write a Bellman equation describing the recurrence relation for the array identified above, and briefly justify its correctness. Pay close attention to the base cases.
(c) Write a bottom-up algorithm (pseudocode) to implement the Bellman equation identified above.
(d) Analyze the worst-case running time and space complexity of your algorithm. Does it run in polynomial time? Explain.
(e) Modify your Bellman equation and bottom-up implementation to compute a smallest feasible list of coins c[1...n], in addition to the minimum number of coins n needed. When n = 0, you can return an empty list c = []. When necessary, define a second array to store partial information regarding the optimal solution. Analyze the worst-case running time and space complexity of your algorithm.
Solution to Q1
(a) For i ∈ {0,1,...,A} and j ∈ {1,...,m}, let C[i,j] be the minimum number of coins needed to make change for amount i using denominations d[1], . . . , d[j]. If it’s impossible to make change in this way, let C[i,j] = ∞.
The desired solution is then C[A,m]. (Note: Do not forget to mention this.)
1
(b) The Bellman equation is given below. 0
if i = 0, ifi>0andj=0, otherwise.
Justification:
C[i,j]= ∞
min{1 + C[i − d[j], j], C[i, j − 1]}
• C[0, j] = 0 for all j because making change for 0g does not require any coins.
• C[i,0] = ∞ for i > 0 but j = 0 represents the fact that no change can be made for a positive
amount i when no denominations are available.
• For C[i,j], there are two cases regarding an optimal solution:
– If it contains at least one coin of denomination d[j], then ignoring one such coin, the remaining solution must be the optimal change for i − d[j] using denominations d[1], . . . , d[j], i.e., contain C[i − d[j], j] coins. Here, denomination d[j] is allowed in the remaining solution because the optimal solution may contain multiple coins of denomi- nation d[j].
– If it does not contain any coin of denomination d[j], then it must be the optimal change for i using denominations d[1], . . . , d[j − 1], i.e., contain C [i, j − 1] coins.
Because each quantity used in the expression for C[i,j] has either a smaller i term or a smaller j term, the recurrence relation is not cyclic (i.e. no C[i,j] depends on itself).
(c) The bottom-up algorithm is shown below. It ensures that when C[i,j] is being computed, C[·, j − 1] column is fully computed, and C[i′, j] is also computed for all i′ < i. Because C[i, j] only depends on entries from C[·, j] and C[·, j − 1], we can delete C[·, j − 2] column, thus only storing two columns at a time.
Algorithm 1: Bottom-Up Coin Change
forj=1,...,mdo
If j > 2, delete the column C[·, j − 2] and free up memory for i = 0,…,A do
Compute C[i,j] using the Bellman equation above end
1 2 3 4 5 6
Hence, the worst-case running time is Θ(m · A).
The algorithm does not run in polynomial time because its running time is linear in A, whereas the number of bits required to represent the integer A in input is only log A. Hence, the running time is not polynomial in the length of the input.
Because the algorithm only stores two columns at any given time, its space complexity is O(A).
2
end
(d) The algorithm computes Θ(m · A) entries of array C, and each computation takes Θ(1) time.
Note: You can also solve this question using a 1D array. Let D[i] denote the minimum number of coins needed to make change for amount i. So we do not constrain ourselves to use only certain denominations here. Then, you can write the following Bellman equation:
0
D[i]= ∞
1 + minj:d[j]≤i D[i − d[j]]
if i = 0, if0
Then, we can compute C and S together as follows. Note that we now need to remember the optimal solution can be computed as follows.
Algorithm 2: Optimal Solution for Coin Change
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
forj=1,…,mdo for i = 0,…,A do
Compute C[i, j] using its Bellman equation
Compute S[i, j] using its Bellman equation end
end
Setc←[],i←A,andj←m whilei>0andj>0do
if S[i,j] = L then c ← [cd[j]]
i ← i − d[j] else
j←j−1 end
end
The running time is still O(m · A), but the space complexity now increases to O(m · A).
3
Q2 Longest Increasing Subsequence
Consider the following Longest Increasing Subsequence (LIS) problem: Input: Array A[1 . . . n] of integers.
Output: Length of the longest subsequence S such that each element of S is strictly larger than all the elements before it.
Example: If A = [4,1,7,3,10,2,5,9], then the longest subsequence is S = [1,3,5,9] or S = [1,2,5,9], so the answer is 4. Note that [6,7,8] and [1,2,3] are not subsequences (they either in- clude integers not in A or include integers out-of-order); [4, 1, 7, 10] is not increasing; [1, 3, 9] is not the longest possible.
(a) Define an array which stores the necessary information needed from various subproblems. Clearly identify what each entry of your array means.
(b) Write a Bellman equation describing the recurrence relation for the array identified above, and briefly justify its correctness. Pay close attention to the base cases.
(c) Write a bottom-up algorithm (pseudocode) to implement the Bellman equation identified above.
(d) Analyze the worst-case running time and space complexity of your algorithm. Solution to Q2
(a) For i ∈ {1, . . . , n}, let L[i] be the length of a longest increasing subsequence of A that ends at A[i] (i.e. the longest increasing subsequence of A[1, . . . , i] which contains A[i]).
The desired solution is then maxi∈{1,…,n} L[i]. (Note: Do not forget to mention this.) (b) The Bellman equation is as follows.
Justification:
1 if i = 1,
L[i] =
1 + maxj∈{1,…,i−1}:A[j]
(c) We can compute L in the order of i = 1, . . . , n according to the Bellman equation above.
(d) There are O(n) entries in L, and computing each takes O(n) time given the previous entries. Hence, it takes a total of O(n2) time to compute L, and then finding the maximum entry in L takes O(n) time. Hence, the overall running time is O(n2). The space complexity is O(n).
4
Note: While the question does not ask you to do this, you might be interested to know that the running time can be improved from O(n2) to O(nlogn) using a simple binary search trick on top of the DP.
The trick is to maintain another array C in the bottom-up implementation. When we have processed the first i elements of array A in the bottom-up implementation, C[k] will be equal to the smallest value such that there is an increasing subsequence of A[1 . . . i] that ends at that value. Note that C is always going to remain sorted. At each iteration i, after updating C, we compute L[i] as 1 + k∗, where k∗ is the largest index such that C[k∗] < A[i]. Here, k∗ can be computed using binary search.
5