alg0505

1.0Camdemy1.0http://media.usc.edu.twalg0505http://media.usc.edu.tw/user/http://media.usc.edu.tw/sysdata/doc/0/05afee3409a83d81/thumb_l.jpg360640<iframe width='720' height='405' id='ccShare3540' frameborder='0' src='http://media.usc.edu.tw/media/e/3540' allowfullscreen></iframe>video7204051:34:33index 1001An example of Kruskal’s algorithm235728302** after Algorithm_greedy.pptx239464903An example of Kruskal’s algorithm241974904The Details for Constructing an MST288447805Slide 12288534406Time Complexity of Kruskal’s Algorithm288647807Prim’s Algorithm for Finding an MST311700908An Example for Prim’s Algorithm316110809Prim’s Algorithm for Finding an MST3733903010Time Complexity of Kruskal’s Algorithm3735503011Slide 123735903012Time Complexity of Kruskal’s Algorithm3736336013Prim’s Algorithm for Finding an MST3737036014An Example for Prim’s Algorithm3737803015The Single-Source Shortest Path Problem3738303016An Example for Prim’s Algorithm3739169017The Single-Source Shortest Path Problem3943634018An Example for Prim’s Algorithm3945801019The Single-Source Shortest Path Problem4105432020Dijkstra’s Algorithm to Generate Single Source Shortest Paths4109566021The Single-Source Shortest Path Problem4110666022An Example for Prim’s Algorithm4111499023** after Algorithm_greedy.pptx4122565024Two Feasible Solutions4500995025The 2-terminal One to Any Special Channel Routing Problem4551161026Gaussian elimination4554061027Step 2:How to find all cycles in a graph?[Reingold, Nievergelt and Deo 1977]How many cycles are there in a graph in the worst case?In a complete digraph of n vertices and n(n-1) edges:Step 3:How to check if a cycle is a linear combination of some cycles?U4554694028Gaussian elimination4555094029The 2-terminal One to Any Special Channel Routing Problem4555461030Two Feasible Solutions4555928031** after Algorithm_greedy.pptx4563461032Two Feasible Solutions4566094033Redrawing Solutions4623160034At each point, the local density of the solution is the number of lines the vertical line intersects.The problem: to minimize the density. The density is a lower bound of the number of tracks.Upper row terminals: P1 ,P2 ,…, Pn from left to right.Lower ro4625994035Suppose that we have the minimum density d of a problem instance. We can use the following greedy algorithm: Step 1 : P1 is connected Q1. Step 2 : After Pi is connected to Qj, we check whether Pi+1 can be connected to Qj+1. If the density is incre4626960036Slide 414628027037The knapsack Problem4629327038Slide 434630094039The knapsack algorithm4630594040** after Algorithm_greedy.pptx4646394041The knapsack algorithm4665360042Slide 434993423043The knapsack Problem4993990044Slide 414994623045Suppose that we have the minimum density d of a problem instance. We can use the following greedy algorithm: Step 1 : P1 is connected Q1. Step 2 : After Pi is connected to Qj, we check whether Pi+1 can be connected to Qj+1. If the density is incre4995457046At each point, the local density of the solution is the number of lines the vertical line intersects.The problem: to minimize the density. The density is a lower bound of the number of tracks.Upper row terminals: P1 ,P2 ,…, Pn from left to right.Lower ro4996090047Redrawing Solutions4997057048Two Feasible Solutions4997623049The 2-terminal One to Any Special Channel Routing Problem4998357050Gaussian elimination4999357051Step 2:How to find all cycles in a graph?[Reingold, Nievergelt and Deo 1977]How many cycles are there in a graph in the worst case?In a complete digraph of n vertices and n(n-1) edges:Step 3:How to check if a cycle is a linear combination of some cycles?U5004157052Detailed Steps for the Minimal Cycle Basis Problem5004990053A greedy algorithm for finding a minimal cycle basis:Step 1: Determine the size of the minimal cycle basis, denoted as k.Step 2: Find all of the cycles. Sort all cycles by weights.Step 3: Add cycles to the cycle basis one by one. Check if the added cycle 5010123054Slide 315010890055Slide 305011790056The minimal cycle basis problem5012623057An example of Huffman algorithm5017556058Huffman codes5021556059Slide 265022723060An example of 2-way merging5024456061A Greedy Algorithm to Generate an Optimal 2-Way Merge Tree5026256062Slide 235029556063Linear Merge Algorithm5032656064Slide 215034256065Slide 205035790066Slide 215036556067Linear Merge Algorithm5037123068Slide 235151688069A Greedy Algorithm to Generate an Optimal 2-Way Merge Tree5152888070An example of 2-way merging5153788071Slide 265290254072** after Algorithm_greedy.pptx5379853073An example of Huffman algorithm5387786074fs1920x1080720x4041280x7201920x1080http://media.usc.edu.tw/sysdata/doc/0/05afee3409a83d81/thumb.jpghttp://media.usc.edu.tw/sysdata/doc/0/05afee3409a83d81/cover.jpghttp://media.usc.edu.tw/sysdata/doc/0/05afee3409a83d81/video/thumbs/storyboard.jpghttp://media.usc.edu.tw/sysdata/doc/0/05afee3409a83d811