# Algorithm – COSC 3P03 Design and Analysis of Algorithms

### Assignment 3

Algorithm – 这个题目属于一个Algorithm设计的代写任务, 涵盖了Algorithm等代做方面

### Fall 2019

What to submit: Hard copy: for all questions, submit a hard copy including (when applicable) the definition of your cost function, recurrence, justification that the principle of optimality holds, Algorithm (high level description, not actual code), analysis. test results.

Soft copy: for programming questions Q1 and Q2, submit a softcopy for each of your programs as well as test results (on Sandcastle: submit3p03).

1. (30) Let S be a sequence ofndistinct integers stored in an array as array elementsS[1], S[2], , S[n]. Use the technique of dynamic programming to find the length ofa longest ascending subsequence of entries inSand print out one such a sequence. For example, if the entriesofSare 11, 17, 5, 8, 6, 4, 7, 12, 3, then one longest ascending subsequence is 5, 6,7, 12 with length 4. Please follow the general steps when designing an algorithm using the technique of dynamic programming:
• define an appropriate function;
• write the recurrence;
• show that the principle of optimality holds with respect to the function;
• design an algorithm using the recurrence;
• (programming) implement your algorithm that asks the user for input and then computes the optimal result.
• be sure to test your program on several input.
``````Your algorithm must run inO(n^2 ) time. Explain why your algorithm has a complexity ofO(n^2 ).
``````
1. (30) Implement the algorithm discussed in class to find an optimal way to multiplynmatrices. Please note that you need to follow the following steps:
• ask the user for an input,nandr 0 , r 1 , , rnthat represent the dimensions of thenmatrices.
• implement the dynamic programming algorithm covered in class.
• then print out the optimal way of multiplying thesenmatrices. For example, ifn= 4 and the optimal way is to multiplyM 2 andM 3 first, followed by multiplying the product just obtained withM 4 , followed by multiplyingM 1 with the last product, you should print out (M 1 ((M 2 M 3 )M 4 )).
1. (20) Fill the table used by the dynamic programming methodto find optimal order to multiply nmatrices. Please note that you should try to do it without writing a program (a program should only be used to verify your answers): n= 5,r 0 = 8,r 1 = 3,r 2 = 2,r 3 = 19,r 4 = 18,r 5 = 7. Important:Show your work by writing down how each entrymijin the cost matrix is computed.
2. (20) Two character strings may have many common substrings. Substrings are required to be contiguous in the original string. For example,photographandtomographyhave several common substrings of length one (i.e., single letters), and commonsubstringsph,to, andographas well as all the substrings ofograph. The maximum common substring length is 6. LetX=x 1 x 2 xm andY =y 1 y 2 ynbe two character strings. Using dynamic programming, design an algorithm to find the maximum common substring length forXandY using dynamic programming. Please follow the general steps for designing a dynamic programming solution as in Q1 (other than the actual programming part).