CSCI411 -  Advanced Algorithms - Complexity - Assignment 4 - Solved

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.

(b)    (15 pts) Describe the optimal substructure of this problem. In particular, define the longest bitonic subsequence of A in terms of the solution for shorter sequences. You may assume that we have a solution for the longest increasing subsequence problem. Justify your answer.

(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
(30 pts) Write a C++ implementation of the pseudocode you developed for problem (2c) modified to return an alignment and submit to Blackboard and to turnin as assignment 4.cpp. You may find the skeleton code in assignment 4  skeleton.cpp on Blackboard helpful.

•    Input will come from cin

–    The first line contains a single integer n indicating the number of examples. n+1 lines follow.

–    The second line contains three space separated integers. These represent the cost of an insertion, a deletion, and a substitution respectively and may be positive, negative, or zero. The cost of a match is assumed to be 0.

–    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