Books · 0121 · reading

TuringAward

1986 - Robert Tarjan

打孔。fortran。高中。在斯坦福认为AI比较模糊,更感兴趣复杂性理论。

I want to develop the theory, what is graph search, what is dfs, what can you do with it, what it can do with the graph.

Use dfs to find biconnected components. Apply the idea to planar testing and working for a year. PhD paper, nlogn to linear. Knuth had developed the idea of concrete analysis of algorithms, he paid attention to const factors. Tarjan ignore the const factors to make algorithm machine independent.

BFPRT, Median of Medians

upper bound is easy to figure out, the lower bound is not easy.

disjoint set union 复杂度是 Knuth 提出的 open problem。当时有人在尝试证明是线性,他认为不可能是线性,提出 double recursion construction, proved with Ackermann function complexity. (Efficiency of a Good But Not Linear Set Union Algorithm, 1975)[Amortized Analysis, inverse ackermann function, path compression and union by rank], 用1-1.5年证明这个界限是严格的。

network flow with Karp in 1972. He collected all algorithms, and think it is a data structure problem! bias search tree.

无法拒绝的价格,因此到了贝尔实验室工作。

50:36-56:00,讲解最大流算法原理。 https://www.bilibili.com/video/BV18q4y1z726/

1h01,splay,move to front.