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

Normalize the amount to

r = k mod N

, with

0 \leq r < N

; negative

k

then naturally denotes a right rotation. When

r = 0

, return without touching the elements. Otherwise the map

j \mapsto (j + r) mod N

has

g = g cd (N, r)

disjoint permutation cycles, each of length

N / g

. Use representatives

0, \dots, g - 1

PROCEDURE RotateLeft(k: INTEGER);
VAR r, g, x, y, h, s, j, next: INTEGER; saved: T;
BEGIN
  r := k MOD N;
  IF r # 0 THEN
    x := N; y := r;
    WHILE y # 0 DO h := x MOD y; x := y; y := h END;
    g := x; s := 0;
    WHILE s < g DO
      saved := a[s]; j := s;
      IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END;
      WHILE next # s DO
        a[j] := a[next]; j := next;
        IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END
      END;
      a[j] := saved; s := s+1
    END
  END
END RotateLeft;

The conditional calculation of next implements addition modulo

N

without first forming a possibly overflowing j+r. Oberon's MOD with positive divisor supplies the nonnegative remainder. The first loop is the Euclidean algorithm, with loop invariant

g cd (x, y) = g cd (N, r)

and decreasing nonzero remainder.

For the outer loop, cycles with representatives below s are complete and every other cycle retains its original values. In one cycle, write

c_{t} = (s + t r) mod N

. The inner loop invariant is saved = A[s],

j = c_{t}

, and

a [c_{u}] = A [c_{u + 1}]

for

0 \leq u < t

, with the remaining sources still untouched. When the next index returns to s, the saved value closes the cycle. The cycle length is

N / g

: writing

N = g N^{'}

and

r = g r^{'}

with

g cd (N^{'}, r^{'}) = 1

, the least positive

t

with

t r \equiv 0 (mod N)

N^{'}

. Each residue class modulo

g

is one cycle, justifying the chosen representatives.

Every element is read once and written once: $2 N$ element accesses, compared with

2 N k

for

k > 1

repetitions of part (b). The zero rotation uses none. The running time is

O (N)

and auxiliary space is constant; the original array

A

is proof notation, not a copy made by the program.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version

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

Solution

 Ancestors (11)

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

 Articles by others on the same topic (0)

 Discussion (0) New discussion