# lec05

Views:

Category: Education

## Presentation Description

No description available.

## 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 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 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.