Programming Assignment 5: Dynamic Programming 1 Solution

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 usu-ally 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 : multiply by 2, multiply by 3, or add 1 to . Your goal is given a positive integer , find the minimum number of operations needed to obtain the number starting from the number 1.


Problem Description

Task. Given an integer , compute the minimum number of operations needed to obtain the number starting from the number 1.

Input Format. The input consists of a single integer 1 ≤    ≤ 106.

Output Format. In the first line, output the minimum number of operations needed to get from 1. In the second line output a sequence of intermediate numbers. That is, the second line should contain positive integers 0, 2, . . . , −1 such that 0 = 1, −1 = and for all 0 ≤ < − 1, +1 is equal to either + 1, 2 , or 3 . 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

1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

Again, another valid output in this case is “1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234”.






3
Starter Files

Going from 1 to is the same as going from 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 to 1 as fast as possible it is natural to repeatedly reduce as much as possible. That is, at each step we replace by min{  /3,   /2, − 1} (the terms   /3 and   /2 are used only when 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( ):

← 0
while    > 1:
←    + 1

if    mod 3 = 0:

←   /3

else if    mod 2 = 0:

←   /2
else:

←    − 1

return

This seemingly correct algorithm is in fact incorrect. You may want to submit one of the starter files to ensure this. Hence in this case moving from to min{  /3,   /2, − 1} is not safe.
Need Help?

Ask a question or see the questions asked by other learners at this forum thread.
































4
    • 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



5
Need Help?

Ask a question or see the questions asked by other learners at this forum thread.




























































6
    • 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 = ( 1, 2, . . . , ) and = ( 1, 2, . . . , ), find the length of their longest common subsequence, i.e., the largest non-negative integer such that there exist indices 1 ≤ 1 < 2 < · · · < ≤ and 1 ≤ 1 < 2 < · · · < ≤ , such that 1 = 1 , . . . , = .
Input Format. First line:  . Second line:  1, 2, . . . ,    . Third line:    . Fourth line:  1, 2, . . . ,    .

Constraints. 1 ≤   ,    ≤ 100; −109 <    ,    < 109.

Output Format. Output  .

Sample 1.

Input:

3

2 7 5

2

2 5

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.


7
    • 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 = ( 1, 2, . . . , ), = ( 1, 2, . . . , ), and = ( 1, 2, . . . , ), find the length of their longest common subsequence, i.e., the largest non-negative integer such that there exist indices 1 ≤ 1 < 2 < · · · < ≤ , 1 ≤ 1 < 2 < · · · < ≤ , 1 ≤ 1 < 2 < · · · < ≤ such that 1 = 1 = 1 , . . . , = =

Input Format. First line:  . Second line:  1, 2, . . . ,    . Third line:    . Fourth line:  1, 2, . . . ,    . Fifth line:
. Sixth line:  1, 2, . . . ,    .

Constraints. 1 ≤   ,   ,  ≤ 100; −109 <    ,    ,    < 109.

Output Format. Output  .

Sample 1.

Input:

3

1 2 3

3

2 1 3

3

1 3 5

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.








8