MIT 6.006 Introductions to Algorithms

Lecture 1: Peak Finding

One-dimensional Version

Definition of a peak: Given array A, index A[n] is a peak if and only if A[n] > A[n - 1] and A[n] > A[n + 1]

Problem: Find a peak if it exists

Straightforward Algorithm

Start from left to the end, find the peak by definition.

In worst case, runtime complexity would be θ(n).

Better Idea

Divide and Conquer

Given an array A:

a = [1, 2, ..., n / 2 - 1, n / 2, n / 2 + 1, ..., n - 1, n]

Look at n / 2 position:

if a[n / 2] < a[n / 2 - 1]:
    // only look at left half to look for a peak
    [1, ..., n / 2 - 1]
else if a[n / 2] < a[n / 2 + 1]:
    // only look at right half to look for a peak
    [n / 2 + 1, ..., n]
else:
    a[n / 2] is a peak

What is the complexity?

if T(n) denotes work required to solve problem with n elements,

T(n) = T(n / 2) + θ(1) = θ(1) * lb(n) = θ(lb(n))

*T: The amount of work to solve the problem **lb: Binary logarithm

Two-dimensional Version

Definition: Given two-dimensional array A which has n rows and m columns, A[i][j] is a peak, if,

A[i][j] >= A[i][j - 1] and
A[i][j] >= A[i][j + 1] and
A[i][j] >= A[i - 1][j] and
A[i][j] >= A[i + 1][j]

Attemp #1: Extend 1-D Divide and Conquer to 2-D

• first, pick middle column j = m / 2.
• And then, find a 1-D peak at (i, j).
• Use (i, j) as a start point on row i to find 1-D peak on row i.

But it's not working!. 2-D peak may not exist on row i.

Attemp #2

• Pick middle column j = m / 2.(Again)
• Find global maximum on column j at (i, j).
• Compare (i, j - 1), (i, j), (i, j + 1).
• Pick left columns of (i, j - 1) > (i, j).
• Similary for right.
• (i, j) is a 2-D peak if neither condition holds.
• Solve the new problem with half the number of columns.
• When you have a single column, find global maximum and you are done.

Complexity of Attemp #2

if T(n, n) denotes work required to solve problem with n rows and m columns:

T(n, m) = T(n, m / 2) + θ(n)
        = θ(n) + ... + θ(n)
        = θ(nlog(m)) = θ(nlog(n)) if m = n