logging in or signing up lec05 BAWare Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 1715 Category: Education License: All Rights Reserved Like it (3) Dislike it (0) Added: February 29, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Tournament Trees: Tournament Trees Winner trees. Loser Trees.Winner Tree – Definition: Winner Tree – Definition Complete binary tree with n external nodes and n – 1 internal nodes. External nodes represent tournament players. Each internal node represents a match played between its two children; the winner of the match is stored at the internal node. Root has overall winner.Winner Tree For 16 Players: Winner Tree For 16 PlayersWinner Tree For 16 Players: Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 Smaller element wins => min winner tree. 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1Winner Tree For 16 Players: Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 height is log2 n (excludes player level) 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1Complexity Of Initialize: Complexity Of Initialize O(1) time to play match at each match node. n – 1 match nodes. O(n) time to initialize n-player winner tree.Winner Tree Operations: Winner Tree Operations Initialize O(n) time Get winner O(1) time Replace winner and replay O(log n) time More precisely Theta(log n) Tie breaker (player on left wins in case of a tie).Replace Winner And Replay: Replace Winner And Replay Replace winner with 6.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Opponent is player who lost last match played at this node.Loser Tree: Loser Tree Each match node stores the match loser rather than the match winner.Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 3 8Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 1 7 Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 1 6 2 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 2 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9Slide20: 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9 1 WinnerComplexity Of Loser Tree Initialize: Complexity Of Loser Tree Initialize Start with 2 credits at each node. Use one to pay for the match played at that node. Use the other to pay for the store of a left child winner. Total time is O(n). More precisely Theta(n).Slide22: Winner Replace winner with 9 and replay matches.Complexity Of Replay: Complexity Of Replay One match at each level that has a match node. O(log n) More precisely Theta(log n).Tournament Tree Applications: Tournament Tree Applications Run generation. k-way merging of runs during an external merge sort. Truck loading.Truck Loading: Truck Loading n packages to be loaded into trucks each package has a weight each truck has a capacity of c tons minimize number of trucksBin Packing: Bin Packing n items to be packed into bins each item has a size each bin has a capacity of c tons minimize number of binsBin Packing: Bin Packing Truck loading is same as bin packing. Truck is a bin that is to be packed (loaded). Package is an item/element. Bin packing to minimize number of bins is NP-hard. Several fast heuristics have been proposed.Bin Packing Heuristics: Bin Packing Heuristics First Fit. Bins are arranged in left to right order. Items are packed one at a time in given order. Current item is packed into leftmost bin into which it fits. If there is no bin into which current item fits, start a new bin.Bin Packing Heuristics: Bin Packing Heuristics First Fit Decreasing. Items are sorted into decreasing order. Then first fit is applied.Bin Packing Heuristics: Bin Packing Heuristics Best Fit. Items are packed one at a time in given order. To determine the bin for an item, first determine set S of bins into which the item fits. If S is empty, then start a new bin and put item into this new bin. Otherwise, pack into bin of S that has least available capacity.Bin Packing Heuristics: Bin Packing Heuristics Best Fit Decreasing. Items are sorted into decreasing order. Then best fit is applied.Performance: Performance For first fit and best fit: Heuristic Bins <= (17/10)(Minimum Bins) + 2 For first fit decreasing and best fit decreasing: Heuristic Bins <= (11/9)(Minimum Bins) + 4Max Winner-Tree For 16 Bins: Max Winner-Tree For 16 Bins Item size = 7Max Winner-Tree For 16 Bins: 7 1 Max Winner-Tree For 16 Bins 6 4 3 6 1 5 7 3 2 6 9 4 5 2 5 8 4 6 5 7 6 9 5 8 7 9 8 9 9Complexity Of First Fit: Complexity Of First Fit O(n log n), where n is the number of items. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
lec05 BAWare Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINTLite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 1715 Category: Education License: All Rights Reserved Like it (3) Dislike it (0) Added: February 29, 2008 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Tournament Trees: Tournament Trees Winner trees. Loser Trees.Winner Tree – Definition: Winner Tree – Definition Complete binary tree with n external nodes and n – 1 internal nodes. External nodes represent tournament players. Each internal node represents a match played between its two children; the winner of the match is stored at the internal node. Root has overall winner.Winner Tree For 16 Players: Winner Tree For 16 PlayersWinner Tree For 16 Players: Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 Smaller element wins => min winner tree. 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1Winner Tree For 16 Players: Winner Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 height is log2 n (excludes player level) 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1Complexity Of Initialize: Complexity Of Initialize O(1) time to play match at each match node. n – 1 match nodes. O(n) time to initialize n-player winner tree.Winner Tree Operations: Winner Tree Operations Initialize O(n) time Get winner O(1) time Replace winner and replay O(log n) time More precisely Theta(log n) Tie breaker (player on left wins in case of a tie).Replace Winner And Replay: Replace Winner And Replay Replace winner with 6.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Replay matches on path to root.Replace Winner And Replay: Replace Winner And Replay 4 3 6 8 6 5 7 3 2 6 9 4 5 2 5 8 3 6 1 3 2 4 2 5 3 1 2 2 1 2 1 Opponent is player who lost last match played at this node.Loser Tree: Loser Tree Each match node stores the match loser rather than the match winner.Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 3 8Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 1 7 Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 1 6 2 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 2 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 1 6 4 9Min Loser Tree For 16 Players: Min Loser Tree For 16 Players 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9Slide20: 4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8 4 6 8 3 5 3 7 2 5 5 8 2 6 4 9 1 WinnerComplexity Of Loser Tree Initialize: Complexity Of Loser Tree Initialize Start with 2 credits at each node. Use one to pay for the match played at that node. Use the other to pay for the store of a left child winner. Total time is O(n). More precisely Theta(n).Slide22: Winner Replace winner with 9 and replay matches.Complexity Of Replay: Complexity Of Replay One match at each level that has a match node. O(log n) More precisely Theta(log n).Tournament Tree Applications: Tournament Tree Applications Run generation. k-way merging of runs during an external merge sort. Truck loading.Truck Loading: Truck Loading n packages to be loaded into trucks each package has a weight each truck has a capacity of c tons minimize number of trucksBin Packing: Bin Packing n items to be packed into bins each item has a size each bin has a capacity of c tons minimize number of binsBin Packing: Bin Packing Truck loading is same as bin packing. Truck is a bin that is to be packed (loaded). Package is an item/element. Bin packing to minimize number of bins is NP-hard. Several fast heuristics have been proposed.Bin Packing Heuristics: Bin Packing Heuristics First Fit. Bins are arranged in left to right order. Items are packed one at a time in given order. Current item is packed into leftmost bin into which it fits. If there is no bin into which current item fits, start a new bin.Bin Packing Heuristics: Bin Packing Heuristics First Fit Decreasing. Items are sorted into decreasing order. Then first fit is applied.Bin Packing Heuristics: Bin Packing Heuristics Best Fit. Items are packed one at a time in given order. To determine the bin for an item, first determine set S of bins into which the item fits. If S is empty, then start a new bin and put item into this new bin. Otherwise, pack into bin of S that has least available capacity.Bin Packing Heuristics: Bin Packing Heuristics Best Fit Decreasing. Items are sorted into decreasing order. Then best fit is applied.Performance: Performance For first fit and best fit: Heuristic Bins <= (17/10)(Minimum Bins) + 2 For first fit decreasing and best fit decreasing: Heuristic Bins <= (11/9)(Minimum Bins) + 4Max Winner-Tree For 16 Bins: Max Winner-Tree For 16 Bins Item size = 7Max Winner-Tree For 16 Bins: 7 1 Max Winner-Tree For 16 Bins 6 4 3 6 1 5 7 3 2 6 9 4 5 2 5 8 4 6 5 7 6 9 5 8 7 9 8 9 9Complexity Of First Fit: Complexity Of First Fit O(n log n), where n is the number of items.