Discussion 07b: Mar 4 (Fri) Version: 1.0 CS/ECE 374 A, Spring 2022
A subsequence of a sequence (for example, an array, a linked list, or a string), obtained by removing zero or more elements and keeping the rest in the same sequence order. A subsequence is called a substring if its elements are contiguous in the original sequence. For example:
SUBSEQUENCE, UBSEQU, and the empty string ε are all substrings of the string SUBSEQUENCE; SBSQNC, UEQUE, and EEE are all subsequences of SUBSEQUENCE but not substrings;
QUEUE, SSS, and FOOBAR are not subsequences of SUBSEQUENCE.
Copyright By PowCoder代写 加微信 powcoder
Describe and analyze dynamic programming algorithms for the following problems. For the rst three, use the backtracking algorithms you developed on Wednesday.
1 Given an array A[1 .. n] of integers, compute the length of a longest increasing subsequence of A. A se- quence B[1 .. l] is increasing if B[i] > B[i − 1] for every index i ≥ 2.
2 Given an array A[1 .. n] of integers, compute the length of a longest decreasing subsequence of A. A se- quence B[1 .. l] is decreasing if B[i] < B[i − 1] for every index i ≥ 2.
3 Given an array A[1..n] of integers, compute the length of a longest alternating subsequence of A. A sequence B[1..l] is alternating if B[i] < B[i − 1] for every even index i ≥ 2, and B[i] > B[i − 1] for every odd index i ≥ 3.
4 Given an array A[1 .. n] of integers, compute the length of a longest convex subsequence of A. A sequence B[1..l]isconvex ifB[i]−B[i−1]>B[i−1]−B[i−2]foreveryindexi≥3.
5 Given an array A[1..n], compute the length of a longest palindrome subsequence of A. Recall that a sequence B[1 .. l] is a palindrome if B[i] = B[l − i + 1] for every index i.
Formulate the problem recursively. This is the hard part. There are two distinct but equally impor- tant things to include in your formulation.
1.A. Specication. First, give a clear and precise English description of the problem you are claiming to solve. Not how to solve the problem, but what the problem actually is. Omitting this step in homeworks or exams is an automatic zero.
1.B. Solution. Second, give a clear recursive formula or algorithm for the whole problem in terms of the answers to smaller instances of exactly the same problem. It generally helps to think in terms of a recursive denition of your inputs and outputs. If you discover that you need a solution to a similar problem, or a slightly related problem, you are attacking the wrong problem; go back to step 1.
Basic steps in developing a dynamic programming algorithm
2 Build solutions to your recurrence from the bottom up. Write an algorithm that starts with the base cases of your recurrence and works its way up to the nal solution, by considering intermediate subproblems in the correct order. This stage can be broken down into several smaller, relatively mechanical steps:
2.A. Identify the subproblems. What are all the dierent ways can your recursive algorithm call itself, starting with some initial input?
2.B. Analyze running time. Add up the running times of all possible subproblems, ignoring the recursive calls.
2.C. Choose a memoization data structure. For most problems, each recursive subproblem can be identied by a few integers, so you can use a multidimensional array. But some problems need a more complicated data structure.
2.D. Identify dependencies. Except for the base cases, every recursive subproblem depends on other subproblemswhich ones? Draw a picture of your data structure, pick a generic element, and draw arrows from each of the other elements it depends on. Then formalize your picture.
2.E. Find a good evaluation order. Order the subproblems so that each subproblem comes after the subproblems it depends on. Typically, you should consider the base cases rst, then the subproblems that depends only on base cases, and so on. Be careful!
2.F. Write down the algorithm. You know what order to consider the subproblems, and you know how to solve each subproblem. So do that! If your data structure is an array, this usually means writing a few nested for-loops around your original recurrence.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com