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.