Question

The following two questions can be solved by dynamic programming. For each question, please describe optimal substructure and express recurrence relation. Give pseudo-code and analyze time and space complexity of your algorithm.

1. Longest palindrome subsequence A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, “civic”, “racecar”, and “aibohphobia” (fear of palindromes). Design a dynamic programming algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input “character”, your algorithm should return “carac”.

2. Coin changing Design a dynamic programming algorithm to find the change of n cents using the fewest number of coins given any set of k different coin denominations. For example, coins in America are in denominations of 1, 5, 10, and 25 cents. However, this question does not have any specific denomination. It only assumes that each coin’s value is an integer and one of the coins is a penny.

Answer 1

PROBLEM 1

Dynamic Programming Solution

We can solve this problem using the solution to another similar problem - the Longest Common Subsequence (LCS) problem. The idea is:

• Reverse the given sequence. Let’s call the original sequence original. Let’s call the reversed sequence reverse.
• Use the LCS algorithm to find the longest common subsequence between original and reverse. Let LCS(original, reverse) be a function that returns the longest common subsequence between the pair of strings.
• The answer from LCS will in fact be the longest palindromic subsequence.

More specifically, consider the illustration below:

The last characters match for both original and reverse in the figure above, hence we recur on both of them excluding the last character.

Next, consider the case illustrated below:

In the case where the last characters do not match, we have to solve two subproblems:

1. Ignore the last character of reverse, and recur on original and updated reverse again.

2. Ignore the last character of original and recur on the updated original and reverse again.

Select the best result from these two subproblems.

Optimal Substructure:-

The solution to this problem satisfies the overlapping subproblem property, as shown in the diagram below. The diagram is a partial LCS of "PXYM" and "PYQX":

The boxes in purple above are the same subproblem - this means we do not need to solve it twice. Using memoization, overlapping subproblems are solved only once and their result is stored to be used if the subproblem shows up again.

For this problem, a two dimensional array LCS can be made as a memo, where LCS[i][j] represents the length of the longest common subsequence between original with length i and reverse, with length j. After populating the memo using the above algorithm, the longest palindromic subsequence can be reconstructed using backtracking on the memo.

Problem 2

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

1) Optimal Substructure
To count the total number of solutions, we can divide all set solutions into two sets.
1) Solutions that do not contain mth coin (or S[m]).
2) Solutions that contain at least one S[m].
Let Rec(S[], m, N) be the function to count the number of solutions, then it can be written as sum of Rec(S[], m-1, N) and Rec(S[], m, N-S[m]).

Therefore, the problem has optimal substructure property as the problem can be solved using solutions to subproblems.

Algorithm and pseudo code

We can approach the problem by thinking of a recursive solution and then convert it to dp. We can break this into 2 parts for a particular coin:

1. we use this coin.
2. we do not use this coin.

Let us define the function as

int Rec(S[], m, N)

S[] is the set of coins.
m is current coin which you will either include or avoid.
N is the sum you want to make.

The possible states to go from Rec are
Case 1 : You include the coin -> Rec(S[], m, N-S[m])
Case 2 : You avoid the coin -> Rec(S[], m-1, N)

Base Cases are:

1. N = 0, m >= 0 Since the sum is already been made return 1.
2. N > 0, m = 0 Sum cannot be made as no coins left return 0.
3. N < 0, We have overshot the required sum return 0.

Lets say we can make the sum N - S[i] in X ways. Then if we have a coin of value S[i] we can also make a sum of N in X ways. We can memoize the number of ways in which we can make all the sums < N. This can be done by keeping a count array for all sums less than N which gives us the expected space complexity of O(N). A sum of 0 is always possible as we can pick no coins, so the base case will be count[0] = 1
Remember to avoid counting a way more than once. This can be done by choosing the coins in a particular order.