CLRS 2: Advanced
4610 2013-01-08 16:43This post is the second pard of my series notes on the remarkable textbook Introduction to Algorithm (a.k.a CLRS).
IV Advanced Design and Analysis Techniques Introduction 357
- Three important but more sophisticated techniques used in designing and analyzing efficient algorithms:
- dynamic programming
- used to optimize problems in which we make a set of choices to get optimal solution
- store the solution to each such subproblem in case it should reappear.
- greedy algorithms
- used to optimize problems in which we make a set of choices to get optimal solution
- make each choice in a locally optimal manner. e.g. 买东西找钱算法
- matroid theory as a mathematical basis
- amortized analysis
- used to analyze certain algorithms that perform a sequence of similar operations.
- Bound the cost of the entire sequence s.t. although some operations might be expensive, many others might be cheap.
- dynamic programming
- We have covered before:
- Divide-and-conquer
- Randomization
- Recurrence
15 Dynamic Programming 359
- Divide-and-conquer: subproblems are disjoint
- Dynamic Programming: subproblems overlap.
- solve subproblems just once and save it in a table, avoiding recomputing
- applied to optimization problems: find a solution with the optimal (min/max) value
- four steps:
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion (get the result)
- Construct an optimal solution from computed information (get how to compute the result)
15.1 Rod cutting 360
- Input: a rod of length n inches. a table of prices pi for i = 1,2,…,n
- Output: max revenue rn
15.2 Matrix-chain multiplication 370
15.3 Elements of dynamic programming 378
15.4 Longest common subsequence 390
15.5 Optimal binary search trees 397
16 Greedy Algorithms 414
16.1 An activity-selection problem 415
16.2 Elements of the greedy strategy 423
16.3 Huffman codes 428
16.4 Matroids and greedy methods 437
16.5 A task-scheduling problem as a matroid 443
17 Amortized Analysis 451
17.1 Aggregate analysis 452
17.2 The accounting method 456
17.3 The potential method 459
17.4 Dynamic tables 463
V Advanced Data Structures Introduction 481
18 B-Trees 484
18.1 Definition of B-trees 488 18.2 Basic operations on B-trees 491 18.3 Deleting a key from a B-tree 499
19 Fibonacci Heaps 505
19.1 Structure of Fibonacci heaps 507 19.2 Mergeable-heap operations 510 19.3 Decreasing a key and deleting a node 518 19.4 Bounding the maximum degree 523
20 van Emde Boas Trees 531
20.1 Preliminary approaches 532 20.2 A recursive structure 536 20.3 The van Emde Boas tree 545
21 Data Structures for Disjoint Sets 561
21.1 Disjoint-set operations 561 21.2 Linked-list representation of disjoint sets 564 21.3 Disjoint-set forests 568 21.4 Analysis of union by rank with path compression 573
VI Graph Algorithms
Introduction 587
22 Elementary Graph Algorithms 589
22.1 Representations of graphs 589
- Sparse graphs: |E| is much less than |V|^2
- adjacency list Θ(V+E)
- Dense graphs: |E| is close to |V|^2 or when we need to be able to tell quickly if there is an edge connecting two given vertices.
- adjacency matrices Θ(V^2)
- edge (u,v) has attribute ƒ
22.2 Breadth-first search 594
- BFS with queue
- u.color (WHITE for ones having not been to, GRAY for ones in the queue, BLACK for ones having been dequeued and enqueued their white neighbors), u.π the predecessor, u.d distance
BFS(G, s)
initialize vertices except source
initialize the source vertex
enqueue the source
while (queue) {
dequeue u
for each white neigbor
mark attributes
enqueue
u.color = BLACK
}
22.3 Depth-first search
- DFS with recursion (stack)
- timestamps are integers between 1 and 2 jV j, since there is one discovery event and one finishing event for each of the jV j vertices.
22.4 Topological sort 612
- topological sort with DFS
- DAG(directed acyclic graph)
- a topological sort of a graph as an ordering of its vertices along a horizontal line so that all directed edges go from left to right.
- to indicate precedence among events.
- TODO 有多个入度为0的
toplogicalSort(G) {
call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return the linked list of vertices
}
22.5 Strongly connected components 615
- decomposing a directed graph into its strongly connected components with DFS
23 Minimum Spanning Trees 624
23.1 Growing a minimum spanning tree 625 23.2 The algorithms of Kruskal and Prim 631
24 Single-Source Shortest Paths 643
24.1 The Bellman-Ford algorithm 651
24.2 Single-source shortest paths in directed acyclic graphs
24.3 Dijkstra’s algorithm 658
- faster than Bellmen-Ford algorithm
24.4 Difference constraints and shortest paths 664 24.5 Proofs of shortest-paths properties 671 655
25 All-Pairs Shortest Paths 684
25.1 Shortest paths and matrix multiplication 25.2 The Floyd-Warshall algorithm 693 25.3 Johnson’s algorithm for sparse graphs 686 700
26 Maximum Flow 708
26.1 Flow networks 709
- Flow networks. Let directed graph G = (V, E) be a flow network with a capacity function c. Let s be the source of the network, and let t be the sink. A flow in G is a real-valued function f: V*V -> R that satisfies:
- Capacity constraint. For all u,v in V, we require 0 <= f(u,v) <= c(u,v)
- Flow conservation. The rate at which material enters a ver- tex must equal the rate at which it leaves the vertex.
- Value |f| of a flow f is the total flow out of the source minus the flow into the source. maximum-flow problem: we are given a flow network G with source s and sink t, and we wish to find a flow of maximum value.
26.2 The Ford-Fulkerson method 714
- dependent on
- residual networks
- augmenting path
- cuts
- We repeatedly augment the flow until the residual network has no more augmenting paths.
26.3 Maximum bipartite matching 732 26.4 Push-relabel algorithms 736 26.5 The relabel-to-front algorithm 748
如果这篇文章对你有帮助
