COMP 3035J: Advanced Program Construction Assignment 2021/22 

Please attempt problem 1 and 2 of the other problems.

Please submit your solutions on Brightspace before the deadline 27th May 2022.

Problem 1 (20% weighting).

What do you mean by the state of a program?

What is a Weakest Precondition of a statement? Show an example of how to calculate the Weakest Precondition of an assignment statement.

Why do we sometimes Strengthen a Postcondition?

Explain the role that an Invariant has in the construction of a loop. What does “Establish the Invariant” mean.

Problem 2 (40% weighting).

The function f on the natural numbers is defined as follows

(0) f.0

(1) f.1

(2) f.(n+2)

= 0

= 1

= 4*f.n + 5*f.(n+1) , 0 ≤ n

Given some natural number N we would like you to construct an efficient algorithm to compute f.N. Specifically, we would like you to construct an O(N) algorithm and then transform this into an O(Log(N)) solution.

Problem 3 (40% weighting).

Given f[0..M), g[0..N) of int. f is ascending and g is descending. Given the following function

h.x.y = 1 <= x + y < 0 h.x.y = 0 <= 0 ≤ x + y

Construct a program to establish the following post condition. Post: r = 〈+ i, j : 0 ≤ i < M ∧ 0 ≤ j < N : h.(f.i).(g.j) 〉

Problem 4 (40% weighting).

Given f[0..N) of int, 0 ≤ N and X : int. Construct a program to establish Post : r = 〈 + i : 0 ≤ i < N : f.i * Xi 〉

Problem 5 (40% weighting).

Given X[0..M), Y[0..N) of integer, Z is a super-sequence of both X and Y if both X and Y are subsequences of Z.

Construct a program to determine the length of the shortest common super-sequence of X and Y.