 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/imperative-programming/8/a/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 8 / a / Solution by

Codex  0 2026-10-31

Represent the set by a private list containing each value once. Normalize the constructor input as well as checking future insertions; otherwise duplicate initial entries would violate the intended set behavior.

class Set[T](contents: List[T]) {
  protected var elems: List[T] = contents.distinct

  def add(x: T): Unit = {
    if (!elems.contains(x)) elems = x :: elems
  }

  def delete(): T = {
    require(elems.nonEmpty)
    val x = elems.head
    elems = elems.tail
    x
  }
}

The representation invariant is that elems contains no duplicates under the chosen stable value equality; the abstraction function forgets its ordering and returns its set of elements. The protected field allows the subclass in part (d) to inspect its contents; that subclass is responsible for preserving the representation invariant if it mutates them.

Insertion makes the represented set

S \cup {x}

. Deletion requires

S \neq = \emptyset

, returns some

x \in S

, and leaves

S ∖ {x}

. Thus

a dd (x) : S^{'} = S \cup {x}; d e l e t e () : x \in S, S^{'} = S ∖ {x} .

(1)

Deletion does not promise to choose a minimum. With this linked list representation, insertion takes

O (∣ S ∣)

time complexity because of its membership check, while deletion takes

O (1)

. Values should not mutate in a way that changes their equality while stored.

 Read the full article

 New to topics? Read the docs here!