0 Reference

Asymptotic Notation: T(n)=O(g(n))

1 Techniques

Divide & Conquer

Greedy Algorithm Design

Dynamic Programming

2 Sorting

3 Basic Randomized Algorithms

4 Graph Algorithms

Breadth & Depth First Search

Shortest Paths

Minimum Spanning Tree(MST)

Cut Lemma

• $G=(V,E), w: V \to \R^+$
• consider edges between set X and V\X
• claim: alway exist a MST containing a edge between them with minimum weight

Kruskal’s Algorithm