 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/imperative-programming-resit/2/d/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 / 2016 / Imperative programming (resit) / 2 / d / Solution by

Codex  0 2026-10-31

Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):

PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
    table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
  table[0,0] := 1; j := 1;
  WHILE j <= n DO table[0,j] := 0; j := j+1 END;
  i := 1;
  WHILE i <= n DO
    table[i,0] := 1; j := 1;
    WHILE j <= n DO
      table[i,j] := table[i-1,j];
      IF j >= i THEN
        table[i,j] := table[i,j] + table[i,j-i]
      END;
      j := j+1
    END;
    i := i+1
  END;
  RETURN table[n,n]
END CountPartitions;

Require

0 \leq n \leq MaxN

. The outer loop invariant says all rows below

i

equal

p (\cdot, \cdot)

. The inner loop invariant additionally says entries before column

j

in the current row are correct. Its dependencies are the previous row and the earlier column

j - i

, so no future entry is read. Each state is evaluated once, giving $Θ (n^{2})$ arithmetic operations and $Θ (n^{2})$ stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.

 Read the full article

 New to topics? Read the docs here!