## Description

Problem 1. (10 marks)

Consider the following definition of Fibonacci numbers:

F(n) =

0 if n = 0

1 if n = 1

F(n − 1) + F(n − 2) if n ≥ 2

a. (3 marks) Give the set of all natural numbers q for which F(q) ≥ 1.6

q−2

. Justify briefly. (In the

textbook, the set of natural numbers, denoted N, starts from 0. This is what we adopt in this course.)

b. (3 marks) Does your answer to a imply the following assertion: ∃c, n0 > 0, such that 0 ≤ c·1.6

n ≤ F(n),

∀n ≥ n0, where c is a real number and n0 a natural number. Explain briefly.

c. (4 marks) Consider the following recursive implementation of function F(n) (which differs slightly from

the one given in the lecture notes).

procedure fib(n)

if (n = 0) then

return 0

else if (n = 1 or n = 2) then

return 1

else

return fib(n − 1) + fib(n − 2)

Prove by induction that the procedure fib(n) is correct.

1

Problem 2. (10 marks) Consider the following recursive version of InsertionSort:

procedure InsertionSort(A, n)

**Sorts array A of size n

if n > 1 then

InsertionSort(A, n − 1)

x ← A[n]

PutInPlace(A, n − 1, x)

end if

procedure PutInPlace(A, j, x)

if (j = 0) then

A[1] ← x

else if x > A[j] then

A[j + 1] ← x

else ∗∗ i.e., x ≤ A[j]

A[j + 1] ← A[j]

PutInPlace(A, j − 1, x)

end if

a. (6 marks)

[3 marks] First, prove (using induction) the correctness of PutInPlace by showing that:

For any array A, and natural number j such that (i) A has (at least) j + 1 cells, and (ii)

the subarray A[1..j] is sorted, when PutInPlace(A, j, x) terminates, the first j + 1 cells of

A contain all the elements that were originally in A[1..j] plus x in sorted order.

We provide a partial solution here.

We prove the predicate by induction. The base case is when j = 0, for which the claim is true as

PutInPlace just puts x in the first cell of A.

Induction step: Let j ≥ 1 be an arbitrary integer and assuming the claim holds for j − 1 we show it

also holds for j. If x is greater than A[j], then x is greater than all elements in A[1..j], so by putting

x in the j + 1-th cell the array A[1..j + 1] satisfies the required: sorted, and contain all the required

elements. … You are asked to complete this proof.

[3 marks] Use induction and the correctness of PutInPlace() to prove the correctness of InsertionSort(A, n).

b. (4 marks) For each state of array A below, indicate whether it ever occurs during the call, InsertionSort(A, n),

where A = [4, 7, 2, 8, 6, 5] and n = 6.

i. A = [4, 2, 7, 8, 6, 5]

ii. A = [2, 4, 7, 8, 6, 5]

iii. A = [2, 4, 7, 6, 8, 5]

iv. A = [2, 4, 6, 7, 8, 5]

v. A = [2, 4, 6, 7, 5, 8]

vi. A = [2, 4, 6, 5, 7, 8]

vii. A = [2, 4, 5, 6, 7, 8]

2

Problem 3. (8 marks) Consider the following code, which takes as input an array A of n integers, where

n > 0.

procedure Unknown(A, n)

i ← 1

p ← A[1] + 1

while (i < n) do

j ← i + 1

p ← p + (A[j] + j)

i ← i + 1

return p

(i) Suppose the input array is A = [2, 5, 3, 6]. What does the procedure return?

(ii) Give a loop invariant (LI) for the loop in the code.

Hint: Here is a partial analysis: At the start of each iteration i (1 ≤ i ≤ n), we have

– when i = 1, the value of p is A[1] + 1;

– when i = 2, the value of p is (A[1] + 1) + (A[2] + 2);

– when i = 3, the value of p is (A[1] + 1) + (A[2] + 2) + (A[3] + 3);

– ……

– when i = n, the loop terminates.

(iii) Prove the the properties of Initialization, Maintenance, and Termination (including both Termination

#1 and Termination #2). Since the problem does not specify what procedure Unknown(.) is supposed

to compute, in proving Termination #2 you only need to indicate what is returned by the procedure

when the loop terminates and and argue why it is implied by LI.

Problem 4. (12 marks) Describe an algorithm for finding both the minimum and maximum of n numbers

using fewer than 3n/2 key comparisons.

Hints:

The case of n = 1 or 2 is trivial, at most 1 key comparision is needed. When n > 2, one can use a loop

to examine each element after the first two and conduct two key comparisons to determine whether

it is a new candidate minimum/maximum. This algorithm requires 1 + 2(n − 2) key comparisons,

which does not satisfy the condition given in the problem.

To reduce key comparisons, process each pair of elements (after the first two) using a loop and

determine if the smaller of the pair is a new candidate minimum and if the larger one is a new

candidate maximum. You need to handle both cases when n is even or odd.

Here are what you need to do for this problem.

Write a pseudocode for your algorithm, which must use exactly one loop (as sketched above, you

don’t need multiple loops).

Explain why your algorithm uses fewer than 3n/2 key comparisons.

Write a loop invariant that your algorithm maintains and show the properties of Initialization, Maintenance, and Termination (including both Termination #1 and Termination #2)

3