Description

Introduction
In this programming assignment, you will be practicing implementing dynamic programming solutions. As usual, in some code problems you just need to implement an algorithm covered in the lectures, while for some others your goal will be to first design an algorithm and then implement it.
Learning Outcomes
Upon completing this programming assignment you will be able to:
1. Apply the dynamic programming technique to solve various computational problems. This will usually require you to design an algorithm that solves a problem by solving a collection of overlapping subproblems (as opposed to the divide-and-conquer technique where subproblems are usually disjoint) and combining the results.
2. See examples of optimization problems where a natural greedy strategy produces a non-optimal result. You will see that a natural greedy move for these problems is not safe.
3. Design and implement an efficient algorithm for the following computational problems:
(a) Implement an efficient algorithm to compute the difference between two files or strings. Such algorithms are widely used in spell checking programs and version control systems.
(b) Design and implement a dynamic programming algorithm for a novel computational problem.
Passing Criteria: 3 out of 5
Passing this programming assignment requires passing at least 3 out of 5 programming challenges from this assignment. In turn, passing a programming challenge requires implementing a solution that passes all the tests for this problem in the grader and does so under the time and memory limits specified in the problem statement.
Contents
1 Money Change Again 2
2 Primitive Calculator 3
3 Edit Distance 5
4 Longest Common Subsequence of Two Sequences 7
5 Longest Common Subsequence of Three Sequences 8

1 Money Change Again
As we already know, a natural greedy strategy for the change problem does not work correctly for any set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). Your goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.
Problem Description
Input Format. Integer money.
Output Format. The minimum number of coins with denominations 1, 3, 4 that changes money.
Constraints. 1 ≤ money ≤ 103.
Sample 1.
Input:
2
Output:
2
2 = 1 + 1.
Sample 2.
Input:
34
Output:
9
34 = 3 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4.
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
2 Primitive Calculator
Problem Introduction
You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.
Problem Description
Task. Given an integer n, compute the minimum number of operations needed to obtain the number n starting from the number 1.
Input Format. The input consists of a single integer 1 ≤ n ≤ 106.
Output Format. In the first line, output the minimum number k of operations needed to get n from 1. In the second line output a sequence of intermediate numbers. That is, the second line should contain positive integers a0,a2,…,ak−1 such that a0 = 1, ak−1 = n and for all 0 ≤ i < k − 1, ai+1 is equal to either ai + 1, 2ai, or 3ai. If there are many such sequences, output any one of them.
Sample 1.
Input:
1
Output:
0
1
Sample 2.
Input:
5
Output:
3
1245
Here, we first multiply 1 by 2 two times and then add 1. Another possibility is to first multiply by 3 and then add 1 two times. Hence “1 3 4 5” is also a valid output in this case.
Sample 3.
Input:
96234
Output:
14
139101122661985941782534616038160393207896234
Again, another valid output in this case is “1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117
96234”.
Starter Files
Going from 1 to n is the same as going from n to 1, each time either dividing the current number by 2 or 3 or subtracting 1 from it. Since we would like to go from n to 1 as fast as possible it is natural to repeatedly reduce n as much as possible. That is, at each step we replace n by min{n/3,n/2,n − 1} (the terms n/3 and n/2 are used only when n is divisible by 3 and 2, respectively). We do this until we reach 1. This gives rise to the following algorithm and it is implemented in the starter files:
GreedyCalculator(n): numOperations ← 0 while n > 1:
numOperations ← numOperations + 1 if n mod 3 = 0: n ← n/3
else if n mod 2 = 0: n ← n/2 else:
n ← n − 1
return numOperations
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
3 Edit Distance
Problem Introduction
The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform one string into another. It is a measure of similarity of two strings. Edit distance has applications, for example, in computational biology, natural language processing, and spell checking. Your goal in this problem is to compute the edit distance between two strings.
Problem Description
Task. The goal of this problem is to implement the algorithm for computing the edit distance between two strings.
Input Format. Each of the two lines of the input contains a string consisting of lower case latin letters.
Constraints. The length of both strings is at least 1 and at most 100.
Output Format. Output the edit distance between the given two strings.
Sample 1.
Input:
ab ab
Output:
0
Sample 2.
Input:
short ports
Output:
3
An alignment of total cost 3:
s h o r t −
− p o r t s
Sample 3.
Input:
editing distance
Output:
5
An alignment of total cost 5:
e d i − t i n g −
− d i s t a n c e
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
4 Longest Common Subsequence of Two Sequences
Problem Introduction
Compute the length of a longest common subsequence of three sequences.
Problem Description
Task. Given two sequences A = (a1,a2,…,an) and B = (b1,b2,…,bm), find the length of their longest common subsequence, i.e., the largest non-negative integer p such that there exist indices 1 ≤ i1 < i2 < ··· < ip ≤ n and 1 ≤ j1 < j2 < ··· < jp ≤ m, such that ai1 = bj1,…,aip = bjp.
Input Format. First line: n. Second line: a1,a2,…,an. Third line: m. Fourth line: b1,b2,…,bm.
Constraints. 1 ≤ n,m ≤ 100; −109 < ai,bi < 109.
Output Format. Output p.
Sample 1.
Input:
3
275
2
25
Output:
2
A common subsequence of length 2 is (2,5).
Sample 2.
Input:
1
7
4
1234
Output:
0
The two sequences do not share elements.
Sample 3.
Input:
4
2783
4
5287
Output:
2
One common subsequence is (2,7). Another one is (2,8).
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.
5 Longest Common Subsequence of Three Sequences
Problem Introduction
Compute the length of a longest common subsequence of three sequences.
Problem Description
Task. Given three sequences A = (a1,a2,…,an), B = (b1,b2,…,bm), and C = (c1,c2,…,cl), find the length of their longest common subsequence, i.e., the largest non-negative integer p such that there exist indices 1 ≤ i1 < i2 < ··· < ip ≤ n, 1 ≤ j1 < j2 < ··· < jp ≤ m, 1 ≤ k1 < k2 < ··· < kp ≤ l such
that ai1 = bj1 = ck1,…,aip = bjp = ckp
Input Format. First line: n. Second line: a1,a2,…,an. Third line: m. Fourth line: b1,b2,…,bm. Fifth line: l. Sixth line: c1,c2,…,cl.
Constraints. 1 ≤ n,m,l ≤ 100; −109 < ai,bi,ci < 109.
Output Format. Output p.
Sample 1.
Input:
3
123
3
213
3
135
Output:
2
A common subsequence of length 2 is (1,3).
Sample 2.
Input:
5
83217
7
82138107
6
683147
Output:
3
One common subsequence of length 3 in this case is (8,3,7). Another one is (8,1,7).
Need Help?
Ask a question or see the questions asked by other learners at this forum thread.