> 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