上海交通大学：《C程序与算法设计》课程教学资源（课件讲稿）Lecture 01 Greedy and Dynamic Programming

上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Computer Algorithm Design and Analysis Lecture 1 Week 13:Greedy and Dynamic Programming Yongxin ZHU,Weiguang SHENG 强 LAMMAMARAU SHANC 1日g

Computer Algorithm Design and Analysis Lecture 1 Week 13: Greedy and Dynamic Programming Yongxin ZHU, Weiguang SHENG

上海充通大学 Greedy Algorithm vs Dynamic SHANGHAI JLAO TONG UNIVERSITY Programming? General idea: Dynamic Programming means Dynamic Planning Greedy algorithm is a special case of dynamic programming Greedy algorithm approaches (approximately sometimes)the global optimum with local optimum Dynamic Programming can handle the optimization issues without local optimum 3/12/2022

3/12/2022 Greedy Algorithm vs Dynamic Programming? General idea: • Dynamic Programming means Dynamic Planning • Greedy algorithm is a special case of dynamic programming • Greedy algorithm approaches (approximately sometimes) the global optimum with local optimum • Dynamic Programming can handle the optimization issues without local optimum

上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Greedy Coin Changing WE NT IE T H C E N T U RY。X SE L E C T I O N S 里迈ESE☒TH Greed is good.Greed is right.Greed works. Greed clarifies,cuts through,and captures the essence of the evolutionary spirit. Gordon Gecko (Michael Douglas) Cashier would say:"Making change with dollars, nickels,and pennies. SH 1日g

Greedy Coin Changing Greed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit. - Gordon Gecko (Michael Douglas) Cashier would say: "Making change with dollars, nickels, and pennies

上海充通大学 Coin Changing SHANGHAI JLAO TONG UNIVERSITY Goal.Given currency denominations:1,5,10,25,100,devise a method to pay amount to customer using fewest number of coins. ©EX:34. Cashier's algorithm.At each iteration,add coin of the largest value that does not take us past the amount to be paid. Ex: $2.89

4 Coin Changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex: 34¢. Cashier's algorithm. At each iteration, add coin of the largest value that does not take us past the amount to be paid. Ex: $2.89

上海充通大学 SHANGHAI JLAO TONG UNIVERSITY Greedy Algorithm Example1: Minimum Spanning Tree 强 MARARAAA月 奏 SHANG 1日

Greedy Algorithm Example1: Minimum Spanning Tree

上充通大Minimum Spanning Tree(MST) SHANGHAI JLAO TONG UNIVERSITY Spanning tree of a connected graph G:a connected acyclic subgraph of G that includes all of G's vertices Minimum spanning tree of a weighted,connected graph G:a spanning tree of G of the minimum total weight Example: 6 6 C a a a 4 2 2 d 6 d 3 3

Minimum Spanning Tree (MST) Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G’s vertices Minimum spanning tree of a weighted, connected graph G: a spanning tree of G of the minimum total weight Example: c d b a 6 2 4 3 1 c d b a 2 3 1 c d b a 6 4 1

上游充通大粤 Prim's MST algorithm SHANGHAI JLAO TONG UNIVERSITY Start with tree T1 consisting of one (any)vertex and "grow"tree one vertex at a time to produce MST through a series of expanding subtrees T1,T2,...,T On each iteration,construct Ti1 from T;by adding vertex not in T;that is closest to those already in Ti(this is a 'greedy”step！) Stop when all vertices are included

Prim’s MST algorithm Start with tree T1 consisting of one (any) vertex and “grow” tree one vertex at a time to produce MST through a series of expanding subtrees T1 , T2 , …, Tn On each iteration, construct Ti+1 from Ti by adding vertex not in Ti that is closest to those already in Ti (this is a “greedy” step!) Stop when all vertices are included

上游究通大学 Example SHANGHAI JLAO TONG UNIVERSITY 4 4 4 C a 6 6 2 2 2 d d 3 3 b 3 4 4 C a a 1 2 2 3 3

Example c d b a 4 2 6 1 3 c d b a 4 2 6 1 3 c d b a 4 2 6 1 3 c d b a 4 2 6 1 3 c d b a 4 2 6 1 3

上海克通大Notes about Prim's algorithm SHANGHAI JLAO TONG UNIVERSITY Proof by induction that this construction actually yields an MST(CLRS,Ch.23.1).Main property is given in the next page. Needs priority queue for locating closest fringe vertex.The Detailed algorithm can be found in Levitin,P.310. Efficiency O(n2)for weight matrix representation of graph and array implementation of priority queue O(m log n)for adjacency lists representation of graph with n vertices and m edges and min-heap implementation of the priority queue

Notes about Prim’s algorithm Proof by induction that this construction actually yields an MST (CLRS, Ch. 23.1). Main property is given in the next page. Needs priority queue for locating closest fringe vertex. The Detailed algorithm can be found in Levitin, P. 310. Efficiency • O(n 2 ) for weight matrix representation of graph and array implementation of priority queue • O(m log n) for adjacency lists representation of graph with n vertices and m edges and min-heap implementation of the priority queue

The Crucial Property behind Prim's Algorithm SHANGHAI JLAO TONG UNIVERSITY Claim:Let G=(V,E)be a weighted graph and (X,y)be a partition of V (called a cut).Suppose e (x,y)is an edge of E across the cut, where x is in X and y is in Y,and e has the minimum weight among all such crossing edges(called a light edge).Then there is an MST containing e. Y X

The Crucial Property behind Prim’s Algorithm Claim: Let G = (V,E) be a weighted graph and (X,Y) be a partition of V (called a cut). Suppose e = (x,y) is an edge of E across the cut, where x is in X and y is in Y, and e has the minimum weight among all such crossing edges (called a light edge). Then there is an MST containing e. y x X Y