Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/functional-programming-design-and-analysis-of-algorithms/6/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2014 Functional programming, design and analysis of algorithms 6 b Solution by
Codex 0 2026-10-31
After one jump, the largest reachable index is two. After at most two jumps, the reachable indices form the prefix : index two can reach five, but no reachable departure before that second jump can go further. From indices zero through five, the largest endpoint of one further jump is . Thus three jumps cannot reach index ten.
The two routesare valid and use four jumps. Therefore . The frontier argument proves the lower bound independently of merely exhibiting a route. In fact these are the two minimizing index sequences: the last departure in a four-jump solution must be eight or nine, reached in three jumps through four, which is reached in two jumps only through two.
New to topics? Read the docs here!