Question

A sequence of n distinct values A[O..n – 1] is said to be downup if there is an index p with 0 < p < n such that the values o

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Algorithm :

For an array of size 'n', let's assume the valley index is p. Iterate over the array and keep updating the value of p, while array is still decreasing.

p = 0

min = arr[0]

for ( i = 1; i < n ; i++)

{

if ( arr[i] < min)

{

min = arr[i]

p = i

}

}

Time - Complexity Analysis : For worst case, array will be sorted in descending order. In this case, Algorithm will iterate over all the elements one by one, resulting in over all 'n' iterations in total. So, worst case time complexity is o(n).

Add a comment
Know the answer?
Add Answer to:
A sequence of n distinct values A[O..n – 1] is said to be downup if there...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • 3. (6 pts) A sequence A = [a1, a2, . . . , anjis called a...

    3. (6 pts) A sequence A = [a1, a2, . . . , anjis called a valley sequence if there is an index i with 1 < t < n such that al > a2 > . . . > ai and ai < ai+1 < . . . < an. A valley sequence must contain at least three elements. (a) (2 pts) Given a valley sequence A of length n, describe an algorithm that finds the element a, as...

  • Let A = [A[1], A[2],…..,A[n]] be an array of n distinct integers. For 1 <= j...

    Let A = [A[1], A[2],…..,A[n]] be an array of n distinct integers. For 1 <= j <= n, the index j is a happy index if A[i] < A[j] for all 1 <= i < j. Describe an O(n)- time algorithm that finds all the happy indices in the array A. Partial credit will be given for an O(n log(n))-time algorithm and a minimal credit will be given for an O(n^2) –time algorithm. What is the running time of your...

  • Describe in pseudocode an algorithm that takes as input a sequence of distinct numbers a0, a1, .....

    Describe in pseudocode an algorithm that takes as input a sequence of distinct numbers a0, a1, ..., an and returns 1 if the sequence is ordered increasingly, -1 if the sequence is in decreasing order, and 0 otherwise. What are the worse-case, best-case, and avergae-case of the algorithm? Analyze the running time in each of the three cases using asymptotic notation.

  • (20 points) You are given an array A of distinct integers of size n. The sequence...

    (20 points) You are given an array A of distinct integers of size n. The sequence A[1], A[2], ..., A[n] is unimodal if for some index k between 1 and n the values increase up to position k and then decrease the reminder of the way until position n. (example 1, 4, 5, 7, 9, 10, 13, 14, 8, 6, 4, 3, 2 where the values increase until 14 and then decrease until 1). (a) Propose a recursive algorithm to...

  • An array A[1,2,... ,n is unimodal if its consists of an increasing sequence followed by sequence...

    An array A[1,2,... ,n is unimodal if its consists of an increasing sequence followed by sequence a decreasing sequence. More precisely, there exists an index k є {1,2,… ,n} such that there exists an indes . AlE]< Ali1 for all 1 i< k, and Ai]Ali 1 for all k< i< n A1,2,..,n] in O(logn) time the loop invariant (s) that your algorithm maintains and show why they lead to the correctness Give an algorithm to compute the maximum element of...

  • 1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers...

    1. a) Describe an O(m)-time algorithm that, given a set of S of n distinct numbers and a positive integer k c n, determines the top k numbers in s b) Describe an O(n)-time algorithm that, given a set of S of n distinct numbers and a positive integer k < n, determines the smallest k numbers in S.

  • 6. Let T(1..n] be a sorted array of distinct integers, some of which may be negative....

    6. Let T(1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <i<n and T[i] = i, provided such an index exists. Your algorithm should take a time in O(lg n) in the worst case. Answers must be proven (or at least well justified)

  • ALGORITHM PROBLEM: A) Significant Inversions: We are given a sequence of n arbitrary but distinct real...

    ALGORITHM PROBLEM: A) Significant Inversions: We are given a sequence of n arbitrary but distinct real numbers <a1 , a2 ,..., an>. We define a significant inversion to be a pair i < j such that ai > 2 aj . Design and analyze an O(n log n) time algorithm to count the number of significant inversions in the given sequence. [Hint: Use divide-&-conquer. Do the “combine” step carefully] B) The Maximum-Sum Monotone Sub-Array Problem: Input: An array A[1..n] of...

  • Using the pseudocode answer these questions Algorithm 1 CS317FinalAlgorithm (A[O..n-1]) ito while i<n - 2 do...

    Using the pseudocode answer these questions Algorithm 1 CS317FinalAlgorithm (A[O..n-1]) ito while i<n - 2 do if A[i]A[i+1] > A[i+2) then return i it i+1 return -1 1. Describe what it does and compute what value is returned when the input is the list {1, 2, 3, 4, 5}. (Hint: We're using 0-based array indexing, so 0 would represent the index of the first element, 1 the second element, etc.) 2. Identify and describe the worst-case input. 3. Identify and...

  • 1. Design and write a Divide& Conquer algorithm that, given an array A of n distinct...

    1. Design and write a Divide& Conquer algorithm that, given an array A of n distinct integers which is already sorted into ascending order, will find if there is some i such that Ali] in worst-case 0(log n) time.

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT