Algorithm Thinking, Peaking Find

1. Course Overview

• Efficient procedures for solving problems.
• Scalability
• Classic data structures & classical algorithms
• Real implementations in Python

2. Content

• Sorting & trees: Event simulation
• Hashing: Genome comparison
• Numerics: RSA encryption
  • Concern about the complexity
• Graphs: Rubik's cube
• Shortest paths: Caltech -> MIT
• Dynamic programming: Used in Image compression
• Advance topics: Nil

3. Peaking finding

3.1 One-dimensional version

Find a peak in the array if it exists.

a	b	c	d	e	f	g	h	i
1	2	3	4	5	6	7	8	9

• Definition: a-i are numbers. Position 2 is a peak if and only if b >= a and b >= c.

• Straightforward algorithm: Start from left to the right.

  • Worst case complexity:

    
    Complexity

• Divide and conquer algorithm:

		...					...
		...	n/2 - 1	n/2	n/2 + 1		...	n

Look at the n/2 position. If a[n/2] < a[n/2 -1] then only look at the left halt 1 ~ (n/2 - 1) to look for a peak. Else if a[n/2] < a[n/2 + 1] then look at the right half. Else n/2 position is a peak.

• Complexity of divide and conquer:

Complexity formula

Where \theta(1) is to choose whether look at the right or the left side. The complexity of which is

Complexity

3.2 2D Version

Pick middle column j = m/2. Find a 1D-peak at (i, j) use (i,j) as a start to find a 1D-peak on row i.