[低端筆記] MIT算法導論 1.Algorithmic Thinking

MIT的算法導論公開課有兩種版本, 我選較新版的
MIT 6.006 Introduction to Algorithms, Fall 2011

官方筆記

Algorithmic thinking, peak finding (PDF)

先備課程

• 6.042 計算機數學(離散, 線代...)
• 複雜度分析(e.g. Big-O)

Course content(8:37)

• Algorithmic Thinking
• Peak Finding
• Sorting & Trees
• Event Simulating
• Hashing
• Genome comparison
• Numeric
• RSA encryption
• Graphs
• Rubik's cube
• Shortest Paths
• A->B
• Dynamic Programming
• Image compression
• Advanced topics

Peak finder

#一維(15:31)

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

*a - i 代表數字

Position 2 is a peak iff b >= a and b >= c
Position 9 is a peak iff i >= h

Find a peak (if it exists)

## "Straight forward" algorithm(18:53)
由左至右依序尋找Peak

1	2	.	.	n/2	.	.	n-1	n
				Peak

worst-case θ(n)

## "Divide & Conquer" (a recursive) algorithm(27:42)

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

觀察n/2
if a[n/2] < a[n/2 - 1] then 只看1 ~ n/2 - 1
else if a[n/2] < a[n/2 + 1] then 只看n/2 + 1 ~ n
else n/2 是 peak

T(n) = T(n/2) + θ(1)
=>best: T(1) = θ(1)
=>worst: T(n) = θ(1) + θ(1) + --- + θ(1)
=>θ(lgn)

#二維(36:16)
定義:
給定一個n*m矩陣

.	c	.	.
b	a	d	.
.	e	.	.
.	.	.	.

a是二維peak iff a>=b, a>=c, a>=d, a>=e

## "Greedy Ascent" algorithm(37:30)
選定一方向, 並依循該方向找到peak
e.g.

.	.	10	.
14	13	12	.
15	9	11	17
16	17	19	20

假設從12開始, 會經過以下路徑
12-13-14-15-16-17-19-20

worst-case: θ(nm) 或 θ(n^2)(方陣)

## "Divide & Conquer 2D" algorithm (defunct)(42:40)
1. 選定中位行 j = m/2
2. 找出一維Peak (i, j)
3. 選擇(i, j)作為起始點, 找到該列的一維Peak

不正確,
2D peak或許不存在在第 i 列上

定義給的矩陣即為反例, 12為該行的一個peak(因為>10和11)
但該列的peak, 14, 並不是2D peak

## "A working 2D recursive" algorithm(47:35)
1. 選定中位行 j = m/2
2. 找出該行
最大值(i, j)
3. 比較(i, j-1), (i, j), (i, j+1)
4. if(i, j-1) > (i, j) 選擇左半部, 同理, if(i, j+1) > (i, j) 選擇右半部
若(i, j) >=(i, j-1), (i, j+1), 則 (i, j) 為2D peak
5. 只剩一行時, 該行最大值為2D peak
6. 重複執行直到找出2D peak

T(n, m) = T(n, m/2) + θ(n)
=>Best: T(n, 1) = θ(n)
=>worst: T(n, m) = θ(n) + θ(n) + ... + θ(n)
=>θ(nlgm)