Agent Bond and Agent Carter have agreed on a way to covertly communicate a positive integer...

Transcribed Image Text:

Agent Bond and Agent Carter have agreed on a way to covertly communicate a positive integer within the range of 1 to n. Bond will send a sequence of n positive integers A[1], A[2], ..., A[n] to Carter. Upon receiving the sequence, Carter will attempt to look for the presence of increasing arcs in the sequence. A subsequence A[i], A[12],, A[im], where 1 <m <n, is considered an increasing arc whenever the following conditions hold: 11 and im ≤n, = i₁ <i₂ < <im, and A[i] A[i+1] for 1 <j <m. For example, suppose the following sequence of positive integers are given: 7,2, 33, 8, 11, 17, 1,5,9 The following are some of the increasing arcs for this sequence: 7,33 7,8, 11, 17 7,8,9 7,9 (1) (3) (4) A longest increasing arc is an increasing are that is the longest within the given se- quence (i.e., m is maximized). For example, (2) is the longest increasing arc: it has a length of 4. The positive number that Bond intends to send to Carter covertly is the length of the longest increasing arc. That means Carter, upon receiving a sequence from Bond, will have to recover the length of the longest increasing are in order to com- plete her mission and save humanity. Design an efficient algorithm that Carter can use to find the length of the longest increasing are from any given sequence of positive integers. Justify the correctness and analyze the running time of your algorithm. Agent Bond and Agent Carter have agreed on a way to covertly communicate a positive integer within the range of 1 to n. Bond will send a sequence of n positive integers A[1], A[2], ..., A[n] to Carter. Upon receiving the sequence, Carter will attempt to look for the presence of increasing arcs in the sequence. A subsequence A[i], A[12],, A[im], where 1 <m <n, is considered an increasing arc whenever the following conditions hold: 11 and im ≤n, = i₁ <i₂ < <im, and A[i] A[i+1] for 1 <j <m. For example, suppose the following sequence of positive integers are given: 7,2, 33, 8, 11, 17, 1,5,9 The following are some of the increasing arcs for this sequence: 7,33 7,8, 11, 17 7,8,9 7,9 (1) (3) (4) A longest increasing arc is an increasing are that is the longest within the given se- quence (i.e., m is maximized). For example, (2) is the longest increasing arc: it has a length of 4. The positive number that Bond intends to send to Carter covertly is the length of the longest increasing arc. That means Carter, upon receiving a sequence from Bond, will have to recover the length of the longest increasing are in order to com- plete her mission and save humanity. Design an efficient algorithm that Carter can use to find the length of the longest increasing are from any given sequence of positive integers. Justify the correctness and analyze the running time of your algorithm.

Answer rating: 100% (QA)

This Question is similar to Longest Common Subsequence Algorithm a7 2 33 8 11 17 1 5 9 step1 ... View the full answer