Final Exam: Section 1 Programming Solution

Programming Q1: (20 points) - Longest Common Subsequence

Attachments provided: subsequence.cc

Subsequences are sequences within a string that appear in the same relative order but are not necessarily contiguous. For example, if given a string “123456”, then some potential subsequences are, “123”, “12”, “456”, “14”, “236”, “46”, etc.

The longest common subsequence problem is as follows:

Given two sequences A= a1,a2,…am and B= b1,b2,…bN find the length, k, of the longest subsequence C= c1,c2,…cm such that C is a subsequence (not necessarily contiguous) of both A and B.

Example 1: If A = dynamic and B = programming then the longest common subsequence is ami and has a length of 3.

Example 2: If A = apples and B = oranges then the longest common subsequence is aes and has a length of 3.

Write an algorithm to solve the longest common subsequence problem in O(MN) time.

Your program should take two arguments, word_a and word_b.

Given a call, ./subsequence <word_a> <word_b>, your program should output in the following format.

<length_of_longest_subsequence>

<longest_subsequence>

Example: Given, ./subsequence apples oranges your program should return:

3

aes




Q1 Deliverables:

    • subsequence.cc (modified)

        o subsequence_driver()

    • README file (one comprehensive README about all Q’s)
Programming Q2: (30 points) – Optimal Matrix Multiplication

Attachments provided: optimal_multiplications.cc, optimal_ordering.cc, dimension_file.txt, dimension_file2.txt

Given the sizes of several matrices, calculate the optimal multiplication ordering using dynamic programming. The sizes will be presented in a file containing dimensions in a sequence:

For example, dimensions_file.txt can be

50

10
40
30

5

That means that c0 = 50, c1 = 10, c2 = 40, c3 = 30, and c4 = 5. Therefore. the matrices to be multiplied have sizes:

Matrix 1: 50 x 10

Matrix 2: 10 x 40

Matrix 3: 40 x 30

Matrix 4: 30 x 5

Obviously when the dimensions_file.txt contains N numbers, then the matrices to be multiplied are N–1.

Write a program that runs as follows:

./optimal_multiplications <dimensions_file>

The program should produce the optimal number of multiplications.

./optimal_multiplications dimensions_file.txt, should output a single number.

10500

Note: This output is not necessarily representative of any particular input.


Q2 deliverables:

    • optimal_multiplications.cc (modified)

        o multiplication_driver()

    • README file. (one comprehensive README about all Q’s)
Programming Q2 Extra Credit (10 points) – Optimal Matrix Multiplication Ordering

For 10 points of extra credit, submit optimal_ordering.cc, that upon the input:

./optimal_ordering <dimensions_filename> outputs the correct optimal matrix multiplication order.

You should use parentheses, and the matrices should be named A through Z, in order, left to right. You can and should use your work in Q2.

For example:

./optimal_ordering dimensions_file.txt    should print:

(A(B(CD)))

Note: This output is not necessarily representative of any particular file.

More potential output examples: (not necessarily representative of any files)

((AB)((CD)E))

((A(BC))D)

Your output should be of this form, with parentheses surrounding every grouping, including the outermost. You can assume that there will not be more than 26 matrices in a given dimensions file.

Please make sure that all functionality is called from the function ordering_driver().

Q2 EC deliverables

    • optimal_ordering.cc (modified)

        o ordering_driver()

    • Readme file. (one comprehensive README about all Q’s)