Algorithms and Data Structures/Algorithms

[MIT 6.006] Algorithmic Thinking & Peak Finding

brightlightkim 2022. 5. 10. 13:50
  • 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.