Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4

Maintain an integer len, initially zero, with len = length xs:

PROCEDURE Add(x: INTEGER);
BEGIN
  ASSERT(len < N);
  u[len] := x;
  len := len+1
END Add;

The precondition is the abstract capacity condition. Appending at the first unused array index establishes

u [0.. len) = x s^{'}

in constant running time.

If get(k) first applies a comparison sort to all

n = len

entries, the comparison sorting lower bound gives at least

⌈ lo g_{2} (n!)⌉ = Ω (n lo g n)

comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:

add : Θ (1), get by comparison sorting : Θ (n lo g n) optimally in the worst case .

(1)

This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.

b

 0  0

Solution

 0  0

Keep u[0..len) sorted, with the coupling invariant

0 \leq len \leq N, len = length (x s), u [0.. len) = sort (x s) .

(1)

The abstract list retains insertion order, while the concrete array retains its sorted multiset. Initially both are empty.

PROCEDURE Add(x: INTEGER);
VAR i: INTEGER;
BEGIN
  ASSERT(len < N);
  i := len;
  WHILE i > 0 DO
    IF u[i-1] <= x THEN EXIT END;
    u[i] := u[i-1];
    i := i-1
  END;
  u[i] := x;
  len := len+1
END Add;

PROCEDURE Get(k: INTEGER): INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  RETURN u[k]
END Get;

For insertion, conceptually treat index i as a hole. If

U

is the old sorted prefix of length

n

, the loop invariant is

0 \leq i \leq n

u [0.. i) = U [0.. i)

and

u [i + 1.. n + 1) = U [i .. n)

, with every shifted value strictly greater than

x

. The loop variant is

i

. The exit condition gives either no left neighbour or a left neighbour at most

x

; filling the hole establishes sortedness and adds exactly one occurrence, preserving the coupling invariant.

get : Θ (1), add : O (n) and worst-case Θ (n) .

(2)

When the new entry is smaller than every old entry, all

n

old values must move in this contiguous sorted-prefix representation. Binary search can reduce comparisons to locate the insertion point, but cannot remove that linear movement cost. Appending a new largest value takes constant time in this implementation.

c

 0  0

Solution

 0  0

The original page permits

m = r

, but also indexes

a [m]

. The meaningful pivot-position contract is the stronger

l \leq m < r

, with

a [l .. m) < a [m]

and

a [m .. r) \geq a [m]

. Implement this two-way array partition by reserving the last entry as pivot:

PROCEDURE Partition(l, r: INTEGER): INTEGER;
VAR pivot, i, j, tmp: INTEGER;
BEGIN
  ASSERT(l < r);
  pivot := a[r-1];
  i := l; j := l;
  WHILE j < r-1 DO
    IF a[j] < pivot THEN
      tmp := a[i]; a[i] := a[j]; a[j] := tmp;
      i := i+1
    END;
    j := j+1
  END;
  tmp := a[i]; a[i] := a[r-1]; a[r-1] := tmp;
  RETURN i
END Partition;

The loop invariant is

l \leq i \leq j \leq r - 1, a [l .. i) < pivot, a [i .. j) \geq pivot, a [r - 1] = pivot .

(1)

The segment's multiset is preserved and entries outside

[l, r)

are unchanged. The unclassified part is

[j, r - 1)

. A smaller entry is swapped into the left group; if

i < j

, the displaced entry belongs to the greater-or-equal group. Otherwise the entry simply joins that group. The loop variant is

r - 1 - j

At exit the final swap installs the pivot at i, giving

m = i \in [l, r), a [l .. m) < a [m] \leq a [m .. r), T = Θ (r - l) .

(2)

A singleton segment is handled without loop iterations. Equality belongs on the pivot's right side, as required by the printed strict left inequality.

d

 0  0

Solution

 0  0

Store the current multiset in an unsorted prefix a[0..len); Add appends exactly as in part (a). The coupling invariant is equality of length and multiset with abstract xs, rather than equality of insertion order. Get applies quickselect:

PROCEDURE Get(k: INTEGER): INTEGER;
VAR l, r, m: INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  l := 0; r := len;
  LOOP
    m := Partition(l, r);
    IF k = m THEN RETURN a[m]
    ELSIF k < m THEN r := m
    ELSE l := m+1
    END
  END
END Get;

The loop invariant is

0 \leq l \leq k < r \leq len

, the complete array has its original multiset, every discarded entry on the left is at most every active entry, and every active entry is at most every discarded entry on the right. Thus the desired global order statistic is the local one of rank

k - l

. The two-way array partition result either identifies it or excludes the pivot and the irrelevant side. The positive loop variant

r - l

strictly decreases unless the procedure returns.

Balanced pivots give

T (n) \leq T (⌈ n /2 ⌉) + c n

, whose geometric series is

O (n)

. More generally, choosing a uniformly random pivot before each call, by swapping a random active entry into a[r-1], gives expected

Θ (n)

running time on distinct keys: with constant probability, the pivot is in the middle half and the retained side has size at most

3 n /4

. Expected work over these shrinking stages is a convergent geometric series.

add : Θ (1); get : expected Θ (n) under suitable pivot assumptions, worst-case Θ (n^{2}) .

(1)

The particular last-entry pivot in the displayed code has no unconditional expected guarantee without an input distribution. Its worst case repeatedly discards one entry. Duplicate keys require further care: on an all-equal segment, the strict partition always returns

l

, so selecting the last rank costs

n + (n - 1) + \dots + 1 = Θ (n^{2})

even with randomized pivot positions. A three-way array partitioning that groups all keys equal to the pivot restores the usual randomized linear expectation with duplicates; alternatively the stated expectation assumes distinct keys. This is a qualification to the bound, not to the algorithm correctness of the displayed code.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4

a

Solution

b

Solution

c

Solution

d

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion