- 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.
'Algorithms and Data Structures > Algorithms' 카테고리의 다른 글
Bit Manipulation (0) | 2022.06.11 |
---|---|
How to Optimize Solutions for Coding Problems (0) | 2022.05.17 |
[Coding Test] How to Solve Coding Problems (0) | 2022.05.15 |
[Big O] Missed Questions (0) | 2022.05.14 |
Big O Notation and Frequently missed questions (0) | 2022.05.13 |