Description

Assignment 4
There will likely be time in class to discuss these problems in small groups and I highly encourage you to collaborate with one another outside of class. However, you must write up your own solutions independently of one another. Feel free to communicate via Discord and to post questions on the appropriate forum in Blackboard. Do not post solutions. Also, please include a list of the people you work with at the top of your submission.
Written Problems
1. Consider the following refined notion of bitonicity. Call a sequence S = [s1,s2,…,sn] an initially increasing bitonic sequence if there is an index 1 ≤ i ≤ n such that s1 < s2 < ··· < si and si > si+1 > ··· > sn. On the other hand, call S an initially decreasing bitonic sequence if there is an index 1 ≤ j ≤ n such that s1 > s2 > ··· > sj and sj < sj+1 < ··· < sn. S is bitonic if it is either initially increasing or initially decreasing and bitonic.
Given a sequence A, we would like to determine its longest bitonic subsequence.
(a) (5 pts) Find a longest bitonic subsequence of the sequence A = [5,8,8,3,4,1,7,−3,2,9,12]. Show your work.
(c) (10 pts) Write pseudocode for a function LBS(A) which returns the length of a longest bitonic subsequence of A. You are given a function LIS(A) that returns a list L that is the same length as A such that L[i] is the length of the longest increasing subsequence of A ending at index i.
(d) (5 pts) Analyze the asymptotic run time of your algorithm.
2. Given two strings A and B, we can transform A to B using insertions, deletions, and substitutions. Each of these operations comes with a prespecified cost. Our goal is to determine the minimum cost of changing A to B. We call this cost the edit distance from A to B.
For example, suppose A = “ataccg” and B = “aacgca” and insertions, deletions, and substitutions all have cost 1. Then we can transform A to B by (1) deleting the t, (2) inserting a g between the two c’s, and (3) substituting the last g for an a. This process has total cost 3 and the edit distance from A to B is 3.
We can represent this transformation with the following alignment:
A a c c g
Ba c g c a
Here, insertions are represented by an underscore (“ ”) in A, deletions are represented by an underscore in B, and substitutions are represented by mismatched characters.
(a) (5 pts) Determine the edit distance and an optimal alignment between the strings “exponential” and “polynomial”. Show your work (draw the resulting alignment).
(b) (15 pts) Describe the optimal substructure of this problem. In particular, define the edit distance between A and B in terms of the solution for shorter strings. Justify your answer.
(c) (10 pts) Write pseudocode for a function editDistance(A, B, ins, del, sub) which returns the edit distance between A and B given costs for insertions, deletions, and substitutions. Assume that matches have a cost of 0. This function does not need to generate an alignment.
(d) (5 pts) Analyze the asymptotic run time of your algorithm.
Coding Problem
• Input will come from cin
– The first line contains a single integer n indicating the number of examples. n+1 lines follow.
– The next n lines each contain two space separated strings, A and B.
• Print output to cout
– Your output should consist of three lines per example.
– The first line is the alignment of string A.
– The second line is the alignment of string B.
– The third line is the cost or score associated with the alignment.
• If there is ever a choice between multiple actions which would result in different optimal alignments, prefer substitutions to deletions and deletions to insertions (first try substitution, then try deletion, and finally try insertion).
Examples
Example 1:
Input:
4
1 1 1
expon poly snowy sunny coarse course ataccg aacgca
Expected output: expo n poly 4 snowy sunny 3 coarse course 1 atac cg a acgca
3
Example 2:
Input:
2
3 3 2
ataagcc gtacc aagtaac gcccgtaa
Expected output: ataagcc gt a cc 8 aagtaac
gcccgtaa
13
Example 3:
Input:
2
1 3 5
coarse course break brake Expected output: co arse cou rse 4 break br ake 4