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.