Binary-search-tree sort 7∈ b Create an empty Bst for i=i to n do trEe-INSert(,AiD) Perform an inorder tree walk of t Example:

ynamic order statistics OS-SELECT(i, S): returns the i th smallest element in the dynamic set S. OS-RANK(, S): returns the rank ofx E S in the sorted order of s s elements IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\\S): Add x to s DELETE(X E S): Remove x from S

Dynamic programming Design technique, like divide-and-conquer Example: Longest Common Subsequence (LCs) Given two sequences x[l.. m] and yll.n], find a longest subsequence common to them both a' not the

Paths in graphs Consider a digraph g=(v, E)with edge-weight function w:E→>R. The weight of path p=v1→ →>…→> vi is defined to be (D)=∑(n,1)

Shortest paths Single-source shortest paths nonnegative edge weights Dijkstra's algorithm: O(E+ vlg n General

麻省理工学院：《算法导论》（英文版） Lecture 21 Prof charles e. leiserson

Recall from lecture 22 °Flow value:f=f(s,V) Cut: Any partition (S, T)of y such that s E S andt∈T Lemma. f=f(s, T) for any cut(S, T) Corollary. f(s, T) for any cut(S, T) Residual graph: The graph G=(v, ef) with strictly positive residual capacities c u, v) c(u,)-f(2y)>0

第二章积分习题课 一.小结

一、收敛性:有类似实幂级数的able定理 1.ble定理:若ak(z-b)在z=z收敛