2013-01-08 16:43

This post is the second pard of my series notes on the remarkable textbook Introduction to Algorithm (a.k.a CLRS).

- 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

- 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**: findsolution with the optimal (min/max) value*a* - 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)

- Input: a rod of length
*n_ inches. a table of prices _pi*for i = 1,2,...,n - Output: max revenue rn

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.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.1 Preliminary approaches 532 20.2 A recursive structure 536 20.3 The van Emde Boas tree 545

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

￼Introduction 587

- 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 ƒ

- 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

```

cpp BFS_pseudo_code.c

```
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的
``` cpp Toplogical_sort_pseudo_code.c
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
}
```

- decomposing a directed graph into its strongly connected components
**with DFS**

23.1 Growing a minimum spanning tree 625 23.2 The algorithms of Kruskal and Prim 631

24.2 Single-source shortest paths in directed acyclic graphs

- faster than Bellmen-Ford algorithm

24.4 Difference constraints and shortest paths 664 24.5 Proofs of shortest-paths properties 671 655

25.1 Shortest paths and matrix multiplication 25.2 The Floyd-Warshall algorithm 693 25.3 Johnson’s algorithm for sparse graphs 686 700

**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.

- 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

© 2010-2018 Tian

Built with ❤️ in San Francisco