lec05

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 Players


Winner 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 1


Winner 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 1


Complexity 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 8


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 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 9


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 2 5 2 8 1 6 4 9


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 2 5 5 8 1 6 4 9


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 2 5 5 8 1 6 4 9


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 2 5 5 8 2 6 4 9


Slide20 : 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 Winner


Complexity 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 trucks


Bin 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 bins


Bin 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) + 4


Max Winner-Tree For 16 Bins : Max Winner-Tree For 16 Bins Item size = 7


Max 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 9


Complexity Of First Fit : Complexity Of First Fit O(n log n), where n is the number of items.