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 >= aandb >= 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.
