 Imperative programming

Worked solutions for the held Oxford preliminary examination of 14 June 2023. Source release: released examination PDF. All eight questions and all 42 answerable leaves are addressed below, without reproducing question statements. The three printed sections are retained as context within the question hierarchy.

Code uses the Scala 2 syntax of the paper. Array inputs described as sorted are assumed nondecreasing and stable during an operation. Unless explicitly discussing machine behavior, mathematical proofs state their arithmetic assumptions. In particular, the printed routines in Question 2 have genuine fixed-width arithmetic limitations, which are analyzed rather than silently attributed exact-integer behavior. Implementations below handle empty structures and document their sentinels, capacity bounds and invalid-input behavior.