CLRS 2: Advanced

102 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).

# IV Advanced Design and Analysis Techniques Introduction 357

  • Three important but more sophisticated techniques used in designing and analyzing efficient algorithms:
    1. 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.
    2. 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
    3. 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.
  • We have covered before:
    1. Divide-and-conquer
    2. Randomization
    3. 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:
      1. Characterize the structure of an optimal solution.
      2. Recursively define the value of an optimal solution.
      3. Compute the value of an optimal solution, typically in a bottom-up fashion (get the result)
      4. 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
		}

  • 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:
    1. Capacity constraint. For all u,v in V, we require 0 <= f(u,v) <= c(u,v)
    2. 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
    1. residual networks
    2. augmenting path
    3. 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