Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 6 / c / ii / Solution

Version snapshots simplify correctness: a complicated command restores the complete prior state, so a bespoke inverse cannot accidentally omit an auxiliary field. Redo restores the recorded result without re-executing behavior that might depend on time, randomness or external input. Restoring an immutable root takes constant time, though refreshing the display can cost more.

The storage comparison depends on the representation. A change-specific record for these elementary edits retains only a few indices and song references. Copying a length-$m$ array for each of $h$ edits can require $\Theta (hm)$ storage and $\Theta (m)$ copying per edit. A persistent data structure with structural sharing can preserve many versions much more cheaply; balanced path copying can make small edits allocate $O(\log m)$ new entries. Retaining versions also keeps their reachable data alive. Snapshot references are only constant-sized roots, not a guarantee of constant total retained memory. Neither scheme automatically reverses external effects such as playing audio or writing files. The desired undo boundary must be specified.