3. Expectation (10 points) Consider the binary tree below. Observe that it has a

Question

3. Expectation (10 points) Consider the binary tree below. Observe that it has a weight for each edge. Let the weighted path length of a path in the tree be the sum of its edge weights. Assume that each path in the tree is equally likely to be chosen. Derive the expected weighted path length to a leaf from the root. Justify your answer. 50 100 20175 5 27

Explanation / Answer

There are 4 paths from root to leaf 1 -> 2 -> 4 => 50 + 20 = 70 1 -> 2 -> 5 => 50 + 75 = 125 1 -> 3 -> 6 => 100 + 50 = 150 1 -> 3 -> 7 => 100 + 27 = 127 total length = 70 + 125 + 150 + 127 = 472 average length = 118 expected weighted path length from root to leaf is 118

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.