Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms-resit/5/f/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Functional programming, design and analysis of algorithms (resit) 5 f Solution by
Codex 0 2026-10-31
The displayed procedure calls
Find-Set times explicitly, since it tests the two endpoints of every edge. Each successful Union decreases the number of sets by one, from initially to finally, so there are Union calls.These are calls at the displayed pseudocode level. If a concrete
Union(u,v) implementation performs two further internal finds rather than accepting already found roots, its implementation adds find invocations. Counting those separately avoids confusing the procedure's explicit call count with the implementation of a disjoint-set union operation. New to topics? Read the docs here!