A4 Sol
A4 Sol
A4 Sol
r ← a;
q ← 0;
while r ≥ d do
begin
r ← r − d;
q ← q + 1;
end
Use the following steps in order to verify that the program is correct with respect to
the initial assertion “a and d are positive integers” and final assertion “q and r are
integers such that a = dq + r and 0 ≤ r < d”.
(a) Find an appropriate loop invariant that is strong enough to give the final assertion,
and prove that it is a loop invariant.
(b) Using part (a) and other inference rules for program verification, prove the pro-
gram is partially correct with respect to the initial and final assertions.
(c) Complete a proof of correctness by formally proving the termination of the loop.
(a) We claim that the loop invariant we need is the following proposition p:
p = “a = qd + r and r ≥ 0”.
1
the condition of the loop, r ≥ d, we have that rn = r − d ≥ d − d = 0.
Furthermore:
a = qd + r = qd + r − d + d = (qd + d) + (r − d) = (q + 1)d + (r − d) = qn d + rn .
2. (a) Find the characteristic roots of the linear homogeneous recurrence relation an =
2an−1 − 2an−2 . (Note these are complex numbers)
(b) Find the solution of the recurrence relation in part (a) with a0 = 1 and a1 = 2.
r2 − 2r + 2 = 0.
2
for some numbers α, β. We use the initial values to determine α and β:
a0 = 1 = α + β
a1 = 2 = α(1 + i) + β(1 − i)
α(1 + i) + (1 − α)(1 − i) = 2
2iα = 1 + i
1+i 1+i i 1−i
α= = × = .
2i 2i i 2
Thus:
1−i 1+i
β =1−α=1− = .
2 2
Hence, the solution to the recurrence relation is:
1−i n 1+i
an = (1 + i) + (1 − i)n .
2 2
3. Find all solutions of the recurrence relation an = 7an−1 − 16an−2 + 12an−3 + n4n with
a0 = −2, a1 = 0 and a2 = 5.
r3 − 7r2 + 16r − 12 = 0
(r − 2)2 (r − 3) = 0
a(h) n n
n = α2 + βn2 + γ3
n
for some real numbers α, β, γ, which we will find later via the initial values after we
have the general solution to the full recurrence.
We now need the particular solution. We have that:
F (n) = n4n
3
This has polynomial part n, so the degree of the polynomial part is t = 1. It has
exponential part 4n , so s = 4. By S7.2 Theorem 6, the particular solution thus has
form:
a(p)
n = (qn + p)4
n
for some real numbers p, q. We find the values of p and q by substituting the particular
solution a(p) into the original recurrence relation:
(p) (p) (p)
a(p)
n = 7an−1 − 16an−2 + 12an−3 + n4
n
This can be separated into two equations by setting the coefficients of the polynomials
to be equal:
4q − 64 = 0
4p − 20q = 0
a(p) n
n = (16n − 80)4 .
Thus, the format of the general solution to the recurrence relation is:
an = a(h) (p) n n n n
n + an = α2 + βn2 + γ3 + (16n − 80)4 .
a0 = −2 = α + γ − 80
a1 = 0 = 2α + 2β + 3γ + (−64) · 4
a2 = 5 = 4α + 8β + 9γ + (−48) · 16
This gives a system of three linear equations in three unknowns, which has solution
α = 17, β = 39
2
, γ = 61. Hence, the recurrence relation has solution:
39 n
an = 17 · 2n + n2 + 61 · 3n + (16n − 80)4n
2
= 17 · 2n + 39n2n−1 + 61 · 3n + (16n − 80)4n .
4
4. Consider the following recursive procedure to compute the fibonacci numbers:
(a) Set up a recurrence relation that counts the number of times the sum (+) is
executed considering all the recursive calls used for input n. (Don’t forget to
provide initial conditions as well)
(b) Solve the recurrence relation of part (a).
Let an be the number of sum operations that are performed in calculating the nth
fibonacci number using the recursive procedure. If n = 0 or n = 1, no sum operations
are performed, which gives the initial conditions a0 = a1 = 0. For n > 1, we have
that the recursive procedure calculates the (n − 1)th and (n − 2)th number and adds
them together. Calculating the (n − 1)th number requires an−1 sum operations, and
calculating the (n − 2)th number requires an−2 of them. We then have one more sum
operation to add the two numbers together, giving that:
an = an−1 + an−2 + 1.
This is a nonhomogeneous recurrence relation. The associated homogeneous recurrence
relation is:
(h) (h)
a(h)
n = an−1 + an−2
for values α, β that we will later derive from the initial values.
We now need to find a particular solution to the original recurrence. Since F (n) = 1,
we have that the polynomial part is 1, so t = 0, and the exponential part is 1 = 1n , so
s = 1. Thus, the particular solution has form:
a(p) n
n = (p)1 = p
5
for some value p. To find p, we substitute the particular solution into the original
relation:
an = an−1 + an−2 + 1
p=p+p+1
p = −1
5. Consider the method by Karatsuba for multiplication of large integers given below:
(a) Based on the program we can see that the number of basic operations for line 1
is 1 and the total number of basic operations for lines 2, 3 and 7 is at most C · n
for some constant C (since the operations are on numbers of at most n bits).
Write a recurrence relation for T (n), the number of basic operations used in all
recursive calls for the cases in which n is a power of 2 (i.e. n = 2k for some k).
6
(b) Use the master theorem (page 479) to find a big-Oh estimate for T (n).
We have that there are three recursive calls to KMULT with sequences of about half
the number of the original number of bits, thus giving that the recurrence relation is:
n
T (n) = 3T + C · n.
2
Additionally, T (1) = 1 since when n = 1, we perform one operation (line 1). This,
however, is not necessary to apply the master theorem. Using the master theorem,
we have that a = 3, b = 2, and d = 1. Thus, bd = 21 = 2, and we have that
a > bd . Hence, we are in the third case of the master theorem, which says that T (n)
is O(nlogb a ) = O(nlog2 3 ) = O(n1.585 ).