## Description

## 1 Overview

For this project, you will develop an algorithm to compute the maximum alignment between a target

sequence and any possible combination of two given subsequences. Designing and implementing

this solution will require you to model the problem using dynamic programming, then understand

and implement your model.

You are only allowed to consult the class slides, the textbook, the TAs, and the professor. In

particular, you are not allowed to use the Internet. This is a group project. The only people you

can work with on this project are your group members. This policy is strictly enforced.

In addition to the group submission, you will also evaluate your teammates’ cooperation and

contribution. These evaluations will form a major part of your grade on this project, so be sure

that you respond to messages promptly, communicate effectively, and contribute substantially to

your group’s solution.

Details for your team evaluations are in Section 6.2. You will submit the

peer evaluations to another assignment on Canvas, labelled “Project 2 (individual).”

A word of warning: this project is team-based, but it is quite extensive and a nontrivial task.

You are highly encouraged to start working on (and start asking questions about) this project early;

teams who wait to start until the week before the due date may find themselves unable to complete

it in time.

## 2 Problem Description

In this problem, you are given three arrays, seq1, seq2, and target, and the solution to this problem

will be the maximum alignment score s of target and a sequence soln, where soln is formed by

combining the values in seq1 and seq2 in some order (i.e., seq1 and seq2 are subsequences of soln).

Moreover, s will be the maximum alignment score of target with any combination of seq1 and seq2.

For this project, we will calculate alignment scores as the unnormalized cosine similarity. In

general, we compute cosine similarity of two normalized vectors or sequences ~a and ~b as a sumproduct (or dot product):

h~a,~bi =

Xn

i=1

ai

· bi

,

where n is the length of ~a and ~b, and ai and bi represent element i in ~a and ~b, respectively.

This

score is only referred to as cosine similarity when the sequences are normalized; that is, they have

the property that h~a, ~ai = 1; however, we will calculate the alignment score using the dot product

1

even if the sequences involved are not normalized. That said, you may assume that the input

sequences you are given for this problem will be designed so that target and any combination of

seq1 and seq2 will be normalized.

3 Worked example

Consider the problem with seq1 = (1, 2, 7), seq2 = (1, 3, 6), and target = (1, 2, 1, 3, 7, 6). Note:

after working through this example, we will discuss what a normalized version of this problem

would look like.

The solution to this problem will be a score of 100, achieved by the sequence (1, 2, 1, 3, 7, 6)

(seq1 and seq2 highlighted in red and blue, respectively).

If we compute the dot product of this

sequence with target, we see that it has an alignment score of:

h(1, 2, 1, 3, 7, 6),(1, 2, 1, 3, 7, 6)i =

X

6

i=1

ai

· bi

= 1(1) + 2(2) + 1(1) + 3(3) + 7(7) + 6(6)

= 1 + 4 + 1 + 9 + 49 + 36

= 100

If we compare this score to the alignment score for all of the other unique sequences we could

produce using seq1 and seq2, shown in the table below, we see that this is the highest possible

alignment score with target:

Possible sequence Alignment score

1, 2, 7, 1, 3, 6 72

1, 2, 1, 7, 3, 6 84

1, 2, 1, 3, 7, 6 100

1, 2, 1, 3, 6, 7 99

1, 1, 2, 7, 3, 6 83

1, 1, 2, 3, 7, 6 99

1, 1, 2, 3, 6, 7 98

1, 1, 3, 2, 7, 6 97

1, 1, 3, 2, 6, 7 96

1, 1, 3, 6, 2, 7 80

1, 3, 1, 2, 7, 6 99

1, 3, 1, 2, 6, 7 98

1, 3, 1, 6, 2, 7 82

1, 3, 6, 1, 2, 7 72

Note: there could be more than one sequence that has the maximum alignment score.

As an example of one of the calculations in the table above, the alignment score of the sequence

in the first row with target ((1, 2, 7, 1, 3, 6) with (1, 2, 1, 3, 7, 6)) is:

2

h(1, 2, 7, 1, 3, 6),(1, 2, 1, 3, 7, 6)i = 1(1) + 2(2) + 7(1) + 1(3) + 3(7) + 6(6)

= 1 + 4 + 7 + 3 + 21 + 36

= 72

## Normalization

Cosine similarity should be a value between −1 and 1 indicating how closely aligned two sequences

are, but when the sequences are not normalized, this score can be much larger than 1 or smaller

than −1. A normalized version of this problem might look like seq1 = (0.1, 0.2, 0.7), seq2 = (0.1,

0.3, 0.6), and target = (0.1, 0.2, 0.1, 0.3, 0.7, 0.6).

Note that the cosine similarity of target with itself is 0.1(0.1) + 0.2(0.2) + 0.1(0.1) + 0.3(0.3)

+ 0.7(0.7) + 0.6(0.6) = 0.01 + 0.04 + 0.01 + 0.09 + 0.49 + 0.36 = 1, and this is also the cosine

similarity of the solution with target. Meanwhile, the cosine similarity of target with the incorrect

answer (0.1, 0.2, 0.7, 0.1, 0.3, 0.6) is 0.1(0.1) + 0.2(0.2) + 0.7(0.1) + 0.1(0.3) + 0.3(0.7) + 0.6(0.6)

= 0.01 + 0.04 + 0.07 + 0.03 + 0.21 + 0.36 = 0.72.

You may notice that scaling the input vectors by a constant factor also scales the dot product.

Because of this property and the fact that all possible answers are scaled by the same factor, we

get the same sequence for the original problem above as we do for the scaled problem. Thus,

even though the alignment scores we calculated in the unscaled problem are not technically cosine

similarity, which must always be between −1 and 1, we still identify the same combination of seq1

and seq2 to solve the problem.

All of the test problems you will be given for this project will be normalized, and your final

answers should be real numbers in the range −1 to 1 (up to round-off errors). That said, the

subproblems you evaluate recursively will probably not have this property, and you should not

try to normalize the inputs to the problem in your algorithm.

## 4 Project report

In your project report, you should include brief answers to 7 questions. Note that you must use

dynamic programming to solve this problem; other solutions will not receive substantial credit.

1. How would you break down the problem of calculating the maximum alignment score for a

combination of two sequences seq1 and seq2 (length n and m, respectively) with the sequence

target (length n+m) into one or more smaller instances of this problem? Your answer should

include what subproblems you are evaluating, as well as how you are using the answers to

these subproblems to solve the original problem.

2. What are the base cases of this recurrence?

3. What data structure would you use to recognize repeated problems? You should describe

both the abstract data structure as well as its implementation.

4. Give pseudocode for a memoized dynamic programming algorithm to find the maximum

alignment score when combining seq1 and seq2 to align with target.

5. Give pseudocode for an iterative algorithm to find the maximum alignment score when combining seq1 and seq2 to align with target. This algorithm does not need to have a reduced

space complexity relative to the memoized solution.

3

6. Can the space complexity of the iterative algorithm be improved relative to the memoized

algorithm? Justify your answer.

7. Give pseudocode for an algorithm that identifies the sequence which will achieve the maximum

alignment score. If there is more than one sequence that yields the maximum score, you may

return any such sequence. Your algorithm may be iterative or recursive.

#### 5 Coding your solutions

In addition to the report, you should implement a dynamic programming algorithm that can

compute a maximum cosine similarity for a combination of two subsequences with a target. Your

code may be iterative or recursive, but it must be a dynamic programming algorithm.

You may

code your solution in C++ or Java, but it must compile and run in a Linux environment. If you

are using C++ and your code cannot be compiled using the command

g++ -o align *.cpp

you should include a Makefile that is capable of compiling the code via the make command.

If you choose to implement your code in Java, you should submit an executable jar file with

your source. In either case, your source code may be split into any number of files.

Your code will not need to handle invalid input (e.g., non-normalized sequences or problems

where the length of target doesn’t equal the length of seq1 and seq2 combined).

#### 5.1 Input format

Your program should read its input from the file input.txt, in the following format. The first line

of the file has two positive integers n and m specifying the lengths of seq1 and seq2, respectively.

The second line will list the n real numbers (in the range −1 to 1) that make up seq1, the third

line will have the m real numbers that make up seq2, and the fourth line will have the n + m real

numbers that make up target. All numbers on a line will be separated by spaces.

#### 5.2 Output

Your program should write its output to the file output.txt. The first line of your output should

contain the maximum cosine similarity for seq1, seq2, and target. The second line of your output should list the solution sequence (n + m) that achieves this maximum cosine similarity, with

consecutive values separated by spaces. (seq1 and seq2 should be subsequences of this solution

sequence.)

#### 6 Submission

Your submission for this project will be in two parts, the group submission and your individual

peer evaluations.

4

6.1 Group submission

The submission for your group should be a zip archive containing 1) your report (described in

Section 4) as a PDF document, and 2) your code (described in Section 5). If your code requires

more than a simple command to compile and run then you must also provide a Makefile and/or

shell script. You should submit this zip archive to the “Project 2 (group)” assignment on Canvas.

Be aware that your project report and code will be checked for plagiarism.

6.2 Teamwork evaluation

The second part of your project grade will be determined by a peer evaluation. Your peer evaluation

should be a text file that includes 1) the names of all of your teammates (including yourself), 2) the

team member responsibilities, 3) whether or not your teammates were cooperative, 4) a numeric

rating indicating the proportional amount of effort each of you put into the project, and 5) other

issues we should be aware of when evaluating your and your teammates’ relative contribution. The

numeric ratings must be integers that sum to 30.

It’s important that you be honest in your evaluation of your peers. In addition to letting your

team members whether they do (or do not) need to work on their teamwork and communication

skills, we will also evaluate your group submission in light of your team evaluations. For example,

a team in which one member refused to contribute would be assessed differently than a team with

three functioning members.

You should submit your peer evaluation to the “Project 2 (individual)” assignment on Canvas.

7 Grading

Report 40 points

Question 1, 4, and 5 8 points

Questions 2, 3, 6, and 7 4 each

Code 30 points

Compiles 5

Uses correct input and output format 5

Computes correct alignment score 10

Computes correct sequence 5

Good coding style 5

Teamwork 30 points

Note that if your algorithm is inefficient, you may lose points for both your pseudocode and

your submission. Also, in extreme cases, the teamwork portion of your grade may become negative

or greater than 30. In particular, if you do not contribute to your group’s solution at all, you can

expect to receive an overall grade of 0 on the project.

5