En Book 學習
最近在看一些EN的pdf~
學習一下~
Algorithm Design Manual:
(S.S. Skiena, The Algorithm Design Manual, 2nd ed)
首先，關於 快速排序~
1、隨機化排列。
2. 三點取樣~
3. 小的數列留給選擇排序~
4、（最囧了~）先做小區間的快排~？（據說能減少棧空間的利用~ 太扯了~）
第二，有關二分圖染色，是這麼介紹的：
[Application of Breadth First Search.]
A graph is bipartite if it can be colored without conflicts while using only two
colors. Bipartite graphs are important because they arise naturally in many appli-
cations. Consider the "had-sex-with" graph in a heterosexual world. Men have sex
only with women, and vice versa. Thus, gender defines a legal two-coloring, in this
simple model.
... ...
最後作者不忘再幽默一回~
We can assign the first vertex in any connected component to be whatever
color/sex we wish. BFS can separate the men from the women, but we can't tell
them apart just by using the graph structure.
那本書比較重視建模（modelling）吧。有一個section叫“Design Graphs, Not Algorithms”。
圖論部份作者是這樣分類的：
Polynomial time:
Connected Components
Topological Sorting
Minimum Spanning Tree
Shortest Path
Transitive Closure
Matching
Eulerian Cycle/ E. Tour/ Chinese Postman
Edge and Vertex Connectivity
Network Flow
(3 more topics excluded here)
Hard Problems (NP)
Clique
Independent Set
Vertex Cover
Traveling Salesman Problem
Hamiltonian Cycly
Graph Cycle
Graph Partition
Vertex Coloring
Edge Coloring
Graph Isomophism (同構)
Steiner Tree ( a spanning tree connecting a given set of points, with at most k extra points added to obtain the minimum cost )
至於Introduction to Algorithms，我看過才知道，原來我的快排 Quicksort 寫得不夠標準~
CLRS建議道，in a hash function like this:
h(x)=x mod m
A prime not too close to an exact power of 2 is often a good choice for m.
| 
