6
$\begingroup$

I am given the following problem in an Algorithms class:

Assume that you are given an array A[1 . . . n] of distinct numbers. You are told that the sequence of numbers in the array is unimodal, in other words, there is an index i such that the sequence A[1 . . . i] is increasing (A[j] < A[j + 1] for 1 ≤ j < i), and the sequence A[i . . . n] is decreasing. The index i is called the mode of A. Give an O(log n) algorithm that find the mode of A

I have written this draft solution as my solution but I want to make sure that this is an acceptable CORRECT solution.

My Algorithm:

FIND_MODE(A)
n = A.length
if n == 1
    return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
    return FIND_MODE(A[1 … mid])
else
    return mid + FIND_MODE(A[mid+1 … n])

Is it this acceptable and correct pseudocode algorithm?

Is it correct that this is a Big-O(log n) algorithm?

$\endgroup$
4
$\begingroup$

Almost correct. Just a small correction. It should be

if A[mid] > a[mid+1]

If two consecutive elements are increasing then they are in the increasing portion of the array, so the mode is to the right. Hence the correction.

$\endgroup$
1
$\begingroup$

There's a neat, provably "optimal" (in some sense) algorithm for this problem in Structure and interpretation of computer programs (free online version) by Abelson and Sussman. It involves partitioning the line in two pieces in a ratio $\phi$. I am not sure where the original algorithm came from in the literature, but maybe someone else can cite it.

$\endgroup$
  • $\begingroup$ ps am looking for an exact analysis of the runtime of this algorithm also. $\endgroup$ – vzn Feb 18 '13 at 23:46
0
$\begingroup$

Prologue:

Let L be a list of integers.
Let L[p : q] be an nonempty slice, i.e., 0 ≤ p < q ≤ len(L).
We say that L[p : q] is unimodal iff there is a natural number m such that

(a) p≤m<q;
(b) L[p : m + 1] strictly increasing;
(c) L[m : q] is strictly decreasing.

Furthermore, such a number m, if it exists, is call the mode of L[p : q].

Since L is the same as L[0 : len(L)], we also say that L is unimodal if L[0 : len(L)] is unimodal.

Algorithm:

def Mode(A,p,q): 

if p+1==q:
   return A[p] 
else:
   m=⌊p+q⌋ 2

ifA[m−1]<A[m]: 
   return Mode(A,m,q)
else:
   return Mode(A,p,m)

Proof of Correctness:

Let P(n) denote the assertion that if A is a list of integers, 0 ≤ p < q ≤ len(A), A[p : q] is unimodal, and n = q − p, then M ax(A, p, q) terminates and returns the maximum element of A[p : q].

Note that we are using q − p (length of the slice being considered) as size of input.

We prove that for all integers n ∈ N, n ≥ 1, P (n) holds.

Base Case: Let n = 1. Then q − p = 1, or equivalently, p + 1 = q. Thus A[p : q] is a slice of one element, and A[p] is its maximum element.

By Line 2, A[p] is returned as wanted.

Induction Step: Let n ∈ N,n > 1. Suppose for all j ∈ N, 1 ≤ j < n,P(j) holds. [IH]

WTP: P(n) holds.

Since q − p = n > 1, Lines 4-8 run. There are two cases to consider.

Case 1: A[m − 1] < A[m].

Then by Line 6, Max(A,m,q) is called and returned.

By Line 4 and Hint 2, p < m < q, and so 1 ≤ q − m < q − p.

By the IH, M ax(A, m, q) terminates and returns the maximum element of A[m : q].

Since A[m − 1] < A[m], the mode of A[p : q] must equal the mode of A[m : q].

So the maximum element of A[p : q] equals the maximum element of A[m : q]. Therefore M ax(A, p, q) terminates and returns the maximum element of A[p : q], as wanted.

Case 2: A[m − 1] > A[m]:

Similar to Case 1; left as an exercise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.