You must follow these instructions for Problems: 1. describe the algorithm you d

Question

You must follow these instructions for Problems:

1. describe the algorithm you design for the problem in English,

2. write pseudocode in the style of the CLRS text for your algorithm,

3. define tight asymptotic upper bounds for your algorithm’s running time.

Problem 1 (25 points) A unimodal sequence is a sequence kao, a1, a2, an-1 for which there exists a t such that k a, a 1, at+2, at n-1> strictly increases and then strictly decreases, where the subscript calculations are performed modulo n. That is, if the sequence

Explanation / Answer

Algorithm
-----------
The unimodal subsequence as per definition will be like below two cases:

if t=0 for given sequence then it will contain an increasing sequence followed by a decreasing sequence
else it will contain a decreasing sequence followed by an increasing sequence followed by a decreasing sequence.

For t=0, we will pick the middle element in the sequence and compare with next element, if it is more then it is part of
decreasing sequence so the maximaum lies in the first half, so we continue searching in first half of sequence. else it is
part of increasing sequence, so the maximaum lies in the second half, so we continue searching in second half of sequence.

for t non-zero, same approach if we encounter the middle element in increasing sequence. But if we encounter it in decreasing sequence
then there are 2 decreasing sequences. For identifying which decreasing sequence the element belongs to we compare the
element with first element, if it is more than first element then it is in second decreasing sequence so will continue searching
first half for maximum, else it is in first decreasing sequence so we continue searching in second half.

Irrespective of whether t is 0 or not the second approch would work for both.

Algorithm
--------------

Let A[] be the sequence with length n

MAX(A[],n)
{
a=1
b=n
while a < b
do
mid = (a + b)/2
if A[mid] < A[mid + 1]
a = mid + 1
if A[mid] > A[mid + 1]
if A[1] < A[mid]
b = mid
else
a = mid
done
return A[a]
}

Time Complexity
-----------------
Since at each iteration we are reducing the size by half, the ttime complexity would be T(n)=O(logn)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.