代写代考 ECE 374 A, Spring 2022 – cscodehelp代写

Discussion 07a: Mar 2 (Wed) Version: 1.0 CS/ECE 374 A, Spring 2022
A subsequence of a sequence (for example, an array, linked list, or 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 (and therefore subsequences) of the string SUBSEQUENCE;
􏰀 SBSQNC, SQUEE, and EEE are all subsequences of SUBSEQUENCE but not substrings;

Copyright By cscodehelp代写 加微信 cscodehelp

􏰀 QUEUE, EQUUS, and DIMAGGIO are not subsequences (and therefore not substrings) of SUBSEQUENCE.
Describe recursive backtracking algorithms for the following problems. Don’t worry about running times.
1 Given an array A[1 .. n] of integers, compute the length of a longest increasing subsequence . A sequence
B[1 .. l] is increasing if B[i] > B[i − 1] for every index i ≥ 2. For example, given the array
⟨3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,7⟩
your algorithm should return the integer 6, because ⟨1, 4, 5, 6, 8, 9⟩ is a longest increasing subsequence (one
2 Given an array A[1 .. n] of integers, compute the length of a longest decreasing subsequence . A sequence
B[1 .. l] is decreasing if B[i] < B[i − 1] for every index i ≥ 2. For example, given the array ⟨3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,7⟩ your algorithm should return the integer 5, because ⟨9, 6, 5, 4, 2⟩ is a longest decreasing subsequence (one 3 Given an array A[1 .. n] of integers, compute the length of a longest alternating subsequence . 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.
For example, given the array
⟨3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,7⟩
your algorithm should return the integer 17, because ⟨3,1,4,1,5,2,6,5,8,7,9,3,8,4,6,2,7⟩ is a longest
alternating subsequence (one of many).
To think about later:
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.
For example, given the array
⟨3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,7⟩
your algorithm should return the integer 6, because ⟨3, 1, 1, 2, 5, 9⟩ is a longest convex subsequence (one of many).

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.
For example, given the array
⟨3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,7⟩
your algorithm should return the integer 7, because ⟨4, 9, 5, 3, 5, 9, 4⟩ is a longest palindrome subsequence (one of many).

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com