{"version":"1.0","provider_name":"Camdemy1.0","provider_url":"http:\/\/media.usc.edu.tw","title":"alg0505","description":"","author_name":null,"author_url":"http:\/\/media.usc.edu.tw\/user\/","thumbnail_url":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/0\/05afee3409a83d81\/thumb_l.jpg","thumbnail_height":360,"thumbnail_width":640,"html":"<iframe width='720' height='405' id='ccShare3540' frameborder='0'  src='http:\/\/media.usc.edu.tw\/media\/e\/3540' allowfullscreen><\/iframe>","type":"video","width":720,"height":405,"duration":"1:34:33","index":{"item_1":{"title":"index 1","time":"0","indent":"0","sn":"1"},"item_2":{"title":"An example of Kruskal\u2019s algorithm","time":"2357283","indent":"0","sn":"2"},"item_3":{"title":"** after Algorithm_greedy.pptx","time":"2394649","indent":"0","sn":"3"},"item_4":{"title":"An example of Kruskal\u2019s algorithm","time":"2419749","indent":"0","sn":"4"},"item_5":{"title":"The Details for Constructing an MST","time":"2884478","indent":"0","sn":"5"},"item_6":{"title":"Slide 12","time":"2885344","indent":"0","sn":"6"},"item_7":{"title":"Time Complexity of Kruskal\u2019s Algorithm","time":"2886478","indent":"0","sn":"7"},"item_8":{"title":"Prim\u2019s Algorithm for Finding an MST","time":"3117009","indent":"0","sn":"8"},"item_9":{"title":"An Example for Prim\u2019s Algorithm","time":"3161108","indent":"0","sn":"9"},"item_10":{"title":"Prim\u2019s Algorithm for Finding an MST","time":"3733903","indent":"0","sn":"10"},"item_11":{"title":"Time Complexity of Kruskal\u2019s Algorithm","time":"3735503","indent":"0","sn":"11"},"item_12":{"title":"Slide 12","time":"3735903","indent":"0","sn":"12"},"item_13":{"title":"Time Complexity of Kruskal\u2019s Algorithm","time":"3736336","indent":"0","sn":"13"},"item_14":{"title":"Prim\u2019s Algorithm for Finding an MST","time":"3737036","indent":"0","sn":"14"},"item_15":{"title":"An Example for Prim\u2019s Algorithm","time":"3737803","indent":"0","sn":"15"},"item_16":{"title":"The Single-Source Shortest Path Problem","time":"3738303","indent":"0","sn":"16"},"item_17":{"title":"An Example for Prim\u2019s Algorithm","time":"3739169","indent":"0","sn":"17"},"item_18":{"title":"The Single-Source Shortest Path Problem","time":"3943634","indent":"0","sn":"18"},"item_19":{"title":"An Example for Prim\u2019s Algorithm","time":"3945801","indent":"0","sn":"19"},"item_20":{"title":"The Single-Source Shortest Path Problem","time":"4105432","indent":"0","sn":"20"},"item_21":{"title":"Dijkstra\u2019s Algorithm to Generate Single Source Shortest Paths","time":"4109566","indent":"0","sn":"21"},"item_22":{"title":"The Single-Source Shortest Path Problem","time":"4110666","indent":"0","sn":"22"},"item_23":{"title":"An Example for Prim\u2019s Algorithm","time":"4111499","indent":"0","sn":"23"},"item_24":{"title":"** after Algorithm_greedy.pptx","time":"4122565","indent":"0","sn":"24"},"item_25":{"title":"Two Feasible Solutions","time":"4500995","indent":"0","sn":"25"},"item_26":{"title":"The 2-terminal One to Any Special Channel Routing Problem","time":"4551161","indent":"0","sn":"26"},"item_27":{"title":"Gaussian elimination","time":"4554061","indent":"0","sn":"27"},"item_28":{"title":"Step 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?U","time":"4554694","indent":"0","sn":"28"},"item_29":{"title":"Gaussian elimination","time":"4555094","indent":"0","sn":"29"},"item_30":{"title":"The 2-terminal One to Any Special Channel Routing Problem","time":"4555461","indent":"0","sn":"30"},"item_31":{"title":"Two Feasible Solutions","time":"4555928","indent":"0","sn":"31"},"item_32":{"title":"** after Algorithm_greedy.pptx","time":"4563461","indent":"0","sn":"32"},"item_33":{"title":"Two Feasible Solutions","time":"4566094","indent":"0","sn":"33"},"item_34":{"title":"Redrawing Solutions","time":"4623160","indent":"0","sn":"34"},"item_35":{"title":"At 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 ,\u2026, Pn  from left to right.Lower ro","time":"4625994","indent":"0","sn":"35"},"item_36":{"title":"Suppose 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 incre","time":"4626960","indent":"0","sn":"36"},"item_37":{"title":"Slide 41","time":"4628027","indent":"0","sn":"37"},"item_38":{"title":"The knapsack Problem","time":"4629327","indent":"0","sn":"38"},"item_39":{"title":"Slide 43","time":"4630094","indent":"0","sn":"39"},"item_40":{"title":"The knapsack algorithm","time":"4630594","indent":"0","sn":"40"},"item_41":{"title":"** after Algorithm_greedy.pptx","time":"4646394","indent":"0","sn":"41"},"item_42":{"title":"The knapsack algorithm","time":"4665360","indent":"0","sn":"42"},"item_43":{"title":"Slide 43","time":"4993423","indent":"0","sn":"43"},"item_44":{"title":"The knapsack Problem","time":"4993990","indent":"0","sn":"44"},"item_45":{"title":"Slide 41","time":"4994623","indent":"0","sn":"45"},"item_46":{"title":"Suppose 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 incre","time":"4995457","indent":"0","sn":"46"},"item_47":{"title":"At 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 ,\u2026, Pn  from left to right.Lower ro","time":"4996090","indent":"0","sn":"47"},"item_48":{"title":"Redrawing Solutions","time":"4997057","indent":"0","sn":"48"},"item_49":{"title":"Two Feasible Solutions","time":"4997623","indent":"0","sn":"49"},"item_50":{"title":"The 2-terminal One to Any Special Channel Routing Problem","time":"4998357","indent":"0","sn":"50"},"item_51":{"title":"Gaussian elimination","time":"4999357","indent":"0","sn":"51"},"item_52":{"title":"Step 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?U","time":"5004157","indent":"0","sn":"52"},"item_53":{"title":"Detailed Steps for the Minimal Cycle Basis Problem","time":"5004990","indent":"0","sn":"53"},"item_54":{"title":"A 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 ","time":"5010123","indent":"0","sn":"54"},"item_55":{"title":"Slide 31","time":"5010890","indent":"0","sn":"55"},"item_56":{"title":"Slide 30","time":"5011790","indent":"0","sn":"56"},"item_57":{"title":"The minimal cycle basis problem","time":"5012623","indent":"0","sn":"57"},"item_58":{"title":"An example of Huffman algorithm","time":"5017556","indent":"0","sn":"58"},"item_59":{"title":"Huffman codes","time":"5021556","indent":"0","sn":"59"},"item_60":{"title":"Slide 26","time":"5022723","indent":"0","sn":"60"},"item_61":{"title":"An example of 2-way merging","time":"5024456","indent":"0","sn":"61"},"item_62":{"title":"A Greedy Algorithm to Generate an Optimal 2-Way Merge Tree","time":"5026256","indent":"0","sn":"62"},"item_63":{"title":"Slide 23","time":"5029556","indent":"0","sn":"63"},"item_64":{"title":"Linear Merge Algorithm","time":"5032656","indent":"0","sn":"64"},"item_65":{"title":"Slide 21","time":"5034256","indent":"0","sn":"65"},"item_66":{"title":"Slide 20","time":"5035790","indent":"0","sn":"66"},"item_67":{"title":"Slide 21","time":"5036556","indent":"0","sn":"67"},"item_68":{"title":"Linear Merge Algorithm","time":"5037123","indent":"0","sn":"68"},"item_69":{"title":"Slide 23","time":"5151688","indent":"0","sn":"69"},"item_70":{"title":"A Greedy Algorithm to Generate an Optimal 2-Way Merge Tree","time":"5152888","indent":"0","sn":"70"},"item_71":{"title":"An example of 2-way merging","time":"5153788","indent":"0","sn":"71"},"item_72":{"title":"Slide 26","time":"5290254","indent":"0","sn":"72"},"item_73":{"title":"** after Algorithm_greedy.pptx","time":"5379853","indent":"0","sn":"73"},"item_74":{"title":"An example of Huffman algorithm","time":"5387786","indent":"0","sn":"74"}},"resolution":{"playtype":"fs","subtype":"","src":"1920x1080","mp4":"720x404","mp4_hd":"1280x720","mp4_4k":"","mp4_1920":"1920x1080","mp4_src":"","mp4_base":""},"base_image":{"thumb":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/0\/05afee3409a83d81\/thumb.jpg","cover":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/0\/05afee3409a83d81\/cover.jpg","storyboard":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/0\/05afee3409a83d81\/video\/thumbs\/storyboard.jpg"},"srcFrom":"","base_url":"http:\/\/media.usc.edu.tw\/sysdata\/doc\/0\/05afee3409a83d81","status":true}