algorithm - CLRS Solution 8.4 example of decision tree -

do have example of decision tree solution problem.

i want draw decision tree use in response question (for understand). don't know how draw decision tree. example don't know leaf used representation of algorithm

question 2

suppose given n red , n blue water jugs, of different shapes , sizes. red jugs hold different amounts of water, blue ones. moreover, every red jug, there blue jug holds same amount of water, , vice versa.

your task find grouping of jugs pairs of red , blue jugs hold same amount of water. so, may perform following operation: pick pair of jugs in 1 red , 1 blue, fill red jug water, , pour water blue jug. operation tell whether red or blue jug can hold more water, or have same volume. assume such comparison takes 1 time unit. goal find algorithm makes minimum number of comparisons determine grouping. remember man not directly compare 2 red jugs or 2 blue jugs.

1.describe deterministic algorithm user Θ(n2) comparisons group jugs pairs. 2.prove lower bound of Ω(nlgn) number of comparisons algorithm solving problem must make.

to solve problem, algorithm has perform series of comparisons until has enough information determine matching. can view computation of algorithm in terms of decision tree. every internal node labeled 2 jugs (one red, 1 blue) compare, , has 3 outgoing edges (red jug smaller, same size, or larger blue jug). leaves labeled unique matching of jugs. solutions chapter 8: sorting in linear time 8-17 height of decision tree equal worst-case number of comparisons algorithm has make determine matching. bound size, let first compute number of possible matchings n red , n blue jugs. if label red jugs 1 n , label blue jugs 1 n before starting comparisons, every outcome of algorithm can represented set {(i,π(i)) : 1 ≤ ≤ n , π permutation on {1,..., n}} , contains pairs of red jugs (first component) , blue jugs (second component) matched up. since every permutation π corresponds different outcome, there must n! different results. can bound height h of our decision tree. every tree branching factor of 3 (every inner node has @ 3 children) has @ 3h leaves. since decison tree must have @ least n! children, follows 3h ≥ n! ≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . algorithm solving problem must use (n lg n) comparisons.