[MIT 6.006] Algorithmic Thinking & Peak Finding

• Efficient Procedures for solving large scale problems
• Scalability
• Classical Data Structures
  • Sorting & Matching
• Real Implementation of Algorithms in Python

 

• Order of this classes
  • Algorithmic Thinking: Peak Finding
  • Sorting & Trees: Event simulation
  • Hashing: Genome comparison
  • Numerics: RSA Encryption (SSL | Backend)
  • Graphs: Rubik's Cube
  • Shortest Paths: Caltech -> MIT
  • Dynamic Programming: Image Compression (number of pixels reduces) 
  • Advanced Topics: 

 

Peak Finder

• One-dimensional version

Position a is a peak if and only if b >= a and b >= c

 

Find a peak if it exists.

 

Straightforward Algorithm:

- Start from left and one triversal

- Worst Case: O(n)

Binary Search Algorithms:

- If it's sorted >> break it to smaller arrays to find one

- Worst Case: O(log(n))

 

2D Version of Peak Finding

• n: rows
• m: columns
• a is 2D peak if a>=b, a>=d, a>=c, a>=d

 

Straightforward Algorithms: Greedy Ascent Algorithms

• Where to Start (Gives it)
• Keep Going Left or Right >> and edge >> goes down or bottom
• Worst Case: O(n*m), O(n^2) .. if m=n

Another Algorithm: 

- 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

   - 2D peak may not exist on row i

- Incorrect! (Worse than inefficient)

 

Better Algorithm that works:

- Pick middle column J = m/2

- Find global max on column j at (i, j)

- Compare(i, j-1), (i, j), (i, j+1)

- Pick left cols if (i,j-1) > (i,j) Similar for right

- If (i,j) >= (i,j-1), (i, j+1) => (i,j) is the peak

- Solve the new problem with half the number of columns

- when you have a single column, find a global maximum and you are done.

 

- Complexity of this algrithm: T(n, m) = T(n, m/2) + O(n) -> global maximium to scan it

- T(n, 1) = O(n)

- T(n, m) = O(n) ... + O(n) = O(nlog2m)

                (log2m)

- **2 is under log.