 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/functional-programming-design-and-analysis-of-algorithms-resit/2/a/solution

w = 2^{h + 1} - 1

, and the next size is

2 w + 1

. Suppose two size-

w

trees have at least one smaller tree before them. The portion represented by these trees and that nonempty preceding portion has at least

2 w + 1

elements. The greedy choice would have used a larger perfect binary tree instead, contradicting the specified representation. Three size-

w

trees are likewise impossible, since

3 w \geq 2 w + 1

. Therefore the only possible repeated size is a pair at the beginning. This is the representation invariant of a skew-binary random-access list.

 New to topics? Read the docs here!