COMSATS University Islamabad

CSC301 – Design and Analysis of Algorithms

Assignment #4
Spring 2024

Submitted by: Munib Ur Rehman Qasim

SP22-BAI-036

Class: BSAI-5A

Submitted to: Sir Tanveer Ahmed

Due date: 26th May 2024

 Question #1:

Prove the correctness of the algorithm provided below using Principal of

Mathematical Induction. Begin by clearly defining the loop invariant of the
given algorithm. Subsequently, show all three steps: initialization,
maintenance, and termination.

Sol.

Let xi, yi, zi denote the value at iteration i.

Let yorig, zorig be the original values of y and z.

Let y = 3 and z = 5

iteration (i) xi yi zi
0 0 3 5
1 3 6 2
2 3 12 1
3 15 24 0

Observing from the trace table

We can see that P(i): yorig * zorig = xi + yi * zi

Page | 1
So, loop invariant is:
P(i): yorig * zorig = xi + yi * zi

Where ‘i’ is the ith iteration of the loop.

Pre-conditions:
y and z should be integers and z >= 0

Post-conditions:
Return product of y and z

Initialization:
Before first iteration y = yorig and z = zorig and x = 0
P(0):
yorig * zorig = xi + yi * zi
yorig * zorig = 0 + yorig * zorig
yorig * zorig = yorig * zorig
Proved

Maintenance:
Assume p(k) is true.
P(k): yorig * zorig = xk + yk * zk

Prove for P(k+1): yorig * zorig = xk+1 + yk+1 * zk+1 ---- (1)

So, there are 2 cases, either z is even or odd:

Page | 2
• Case 1: (z % 2 == 1, i.e. z is odd):

From the code we have:

xk+1 = xk + yk
yk+1 = yk * 2
zk+1 = ⌊zk/2⌋

substitute values in (1)

yorig * zorig = xk+1 + yk+1 * zk+1
yorig * zorig = xk + yk + yk * 2 * ⌊zk/2⌋

since z is odd, we can write zk = 2t + 1, for some integer t.

⌊zk/2⌋ = ⌊2t/2 + 1/2⌋ = ⌊t + 1/2⌋ = t

Substituting zk = 2t + 1

yorig * zorig = xk + yk + yk * 2 * t
yorig * zorig = xk + yk * (1 + 2t)

put value of zk = 2t + 1

yorig * zorig = xk + yk * zk

which is equal to the loop invariant.

Page | 3
• Case 2: (z % 2 == 0, i.e. z is even):

From the code we have:

xk+1 = xk
yk+1 = yk * 2
zk+1 = ⌊zk/2⌋

substitute values in (1)

yorig * zorig = xk+1 + yk+1 * zk+1
yorig * zorig = xk + yk * 2 * ⌊zk/2⌋

since z is even, we can write zk = 2t, for some integer t.

⌊zk/2⌋ = ⌊2t/2⌋ = ⌊t⌋ = t

Substituting zk = 2t

yorig * zorig = xk + yk * 2 * t
yorig * zorig = xk + yk * (2t)

put value of zk = 2t

yorig * zorig = xk + yk * zk

which is equal to the loop invariant.

Proved.

Page | 4
Termination:
Loop terminates when z = 0.
Put z = 0 in loop invariant
P(i): yorig * zorig = xi + yi * zi
yorig * zorig = xi + yi * 0
yorig * zorig = xi

so, x = yorig * zorig

which is the post-condition.

Proved.

Page | 5
 Question #2:

Establish the correctness of the following algorithm using Principal of

Mathematical Induction. You must clearly define the loop invariant of the
given algorithm and then show all three steps i.e. initialization, maintenance
and termination.

Sol.

Let xi, yi, zi denote the value at iteration i.

Let yorig, zorig be the original values of y and z.

Let y = 3 and z = 5

iteration (i) xi yi zi
0 0 3 5
1 3 6 2
2 3 12 1
3 15 24 0

Observing from the trace table

We can see that P(i): yorig * zorig = xi + yi * zi

Page | 6
So, loop invariant is:
P(i): yorig * zorig = xi + yi * zi

Where ‘i’ is the ith iteration of the loop.

Pre-conditions:
y and z should be integers and z >= 0

Post-conditions:
Return product of y and z

Initialization:
Before first iteration y = yorig and z = zorig and x = 0
P(0):
yorig * zorig = xi + yi * zi
yorig * zorig = 0 + yorig * zorig
yorig * zorig = yorig * zorig
Proved

Maintenance:
Assume p(k) is true.
P(k): yorig * zorig = xk + yk * zk

Prove for P(k+1): yorig * zorig = xk+1 + yk+1 * zk+1 ---- (1)

So, there are 2 cases, either z is even or odd:

Page | 7
• Case 1: (z % 2 == 1, i.e. z is odd):

From the code we have:

xk+1 = xk + yk * 1
yk+1 = yk * 2
zk+1 = ⌊zk/2⌋

substitute values in (1)

yorig * zorig = xk+1 + yk+1 * zk+1
yorig * zorig = xk + yk + yk * 2 * ⌊zk/2⌋

since z is odd, we can write zk = 2t + 1, for some integer t.

⌊zk/2⌋ = ⌊2t/2 + 1/2⌋ = ⌊t + 1/2⌋ = t

Substituting zk = 2t + 1

yorig * zorig = xk + yk + yk * 2 * t
yorig * zorig = xk + yk * (1 + 2t)

put value of zk = 2t + 1

yorig * zorig = xk + yk * zk

which is equal to the loop invariant.

Page | 8
• Case 2: (z % 2 == 0, i.e. z is even):

From the code we have:

xk+1 = xk + yk * 0 = xk
yk+1 = yk * 2
zk+1 = ⌊zk/2⌋

substitute values in (1)

yorig * zorig = xk+1 + yk+1 * zk+1
yorig * zorig = xk + yk * 2 * ⌊zk/2⌋

since z is even, we can write zk = 2t, for some integer t.

⌊zk/2⌋ = ⌊2t/2⌋ = ⌊t⌋ = t

Substituting zk = 2t

yorig * zorig = xk + yk * 2 * t
yorig * zorig = xk + yk * (2t)

put value of zk = 2t

yorig * zorig = xk + yk * zk

which is equal to the loop invariant.

Proved.

Page | 9
 Termination:
Loop terminates when z = 0.
Put z = 0 in loop invariant
P(i): yorig * zorig = xi + yi * zi
yorig * zorig = xi + yi * 0
yorig * zorig = xi

so, x = yorig * zorig

which is the post-condition.

Proved.

Page | 10
 Question #3:

Sate the Loop Invariant, I(n) of the following algorithm.

ALGORITHM Palindromes(𝐴[0…𝑛−1])
Pre-Condition: 𝑛≥1 𝑎𝑛𝑑 𝐴[0…..𝑛−1] 𝑖𝑠 𝑎 𝑐ℎ𝑎𝑟𝑎𝑐𝑡𝑒𝑟 𝑎𝑟𝑟𝑎𝑦
1. 𝑖←0
2. while(𝑖<⌊𝑛/2⌋) do
3. if(𝐴[𝑖]≠𝐴[𝑛−𝑖−1]) then
4. return F
5. end if
6. 𝑖←𝑖+1
7. end while
8. return T
Post-Condition: Return T iff 𝐴 is a palindrome.

Establish the correctness of the above algorithm using loop invariant that you define in part
(a). Show all steps i.e., initialization, maintenance and termination.

Loop Invariant:
At the start of each iteration of the while loop, the subarray A[0...i−1] is symmetric to
A[n−i...n−1].
i.e.
For all k such that 0 ≤ k < i, A[k] = A[n−k−1].

Initialization:
Before the first iteration, i=0. The subarray A[0...i−1] is empty, and by definition, an empty
subarray is symmetric. Therefore, the loop invariant holds.

Page | 11
Maintenance:
Assume the loop invariant holds at the start of an ‘i'
During this iteration, the algorithm checks if 𝐴[i]≠𝐴[n−i−1]

• Case (they are not equal):

The algorithm returns F, which is correct since that means the array isn’t a palindrome.

Else i gets incremented by 1.

Now we need to check if the loop invariant holds for next iteration i.e. (i+1)

For all k such that 0 ≤ k < i + 1, A[k] = A[n−k−1].

The loop invariant was true for iteration ‘k = i' as shown above, and all previous values were
also true by the assumption of the loop invariant, it continues to hold.

Termination:
The loop terminates when i reaches ⌊n/2⌋.
At this point, all pairs (A[k], A[n−k−1]) for 0 ≤ k < ⌊n/2⌋ have been checked and found to be
equal.
Therefore, the subarray A[0...⌊n/2⌋−1] is symmetric to A[n−⌊n/2⌋...n−1].
If the loop completes without returning F, it means all the necessary pairs are equal, and thus
the array A is a palindrome. Hence, the algorithm correctly returns T.

Proved.

Page | 12
 Question #4 (a):

Mr. Tanveer Ahmed proposes the following version of Binary search:

Is Mr. Tanveer’s version correct i.e., does it find the key if it is present and return -1 if is not
present).Justify your answer

No, it is not correct.

It doesn’t always find the key if its present, and doesn’t return -1 if it isn’t present, as the array
size doesn’t decrease in certain situations, and it becomes an infinite loop.
We can prove this using a counter example:

Let L = [2]
i = 0, j = 0
key = 1

using these inputs, we enter the while loop.

Page | 13
k = (0+0)/2 = 0
L[k] is not equal to key
Since key is less than L[k] (L[k] is 2):
j=k=0

so after the loop, nothing changed,

i=0
j=0
and L = [2]

The array isn’t decrementing, so we entered an infinite loop.

Page | 14
 Question #4 (b):

Mr. Tanveer Ahmed proposes the following version of Binary search:

Is Mr. Tanveer’s version correct i.e., does it find the key if it is present and return -1 if is not
present).Justify your answer

The algorithm searches for key in L for the interval i to j inclusive, if key is present, it should
return the key else It should return -1.

Base case:
First, we check the base case.
If (i > j) it returns -1, which is correct as that’s an invalid interval.

Page | 15
Inductive step:
Assuming the algorithm works correctly for intervals j – i < n, where n is the number of
elements in L.

First, we calculate a point (assuming integer division) k = (i + j) / 2 which is the mid-point of

the interval.
i <= k <= j

Then we check if key is present at index k, if it is then we return k, which is the correct result.

Else it searches the interval [i..k -1]. By inductive hypothesis, it will return the correct result
(index of the key if its present, else -1), which will be stored in flag.

Then it checks if key wasn’t found in interval [i..k-1], by checking if flag has value -1. If it wasn’t
found then it searches the interval [k+1..j], and by inductive hypothesis, this also return the
correct result. And then this result is returned. Which is the correct response.

Else if it was found in interval [i..k-1] it returns flag, which holds the index, which is the correct
response.

So, the algorithm correctly searched in interval [i..k-1], [k+1..j] and at index k, which covers
the whole range. So, we can conclude that the algorithm works correctly.
Also, the size of the interval gets smaller with each recursive call, so we can be sure that it will
eventually reach the base case and not run infinitely.

Page | 16
 Question #4 (c):

Mr. Tanveer Ahmed proposes the following version of Binary search:

Is Mr. Tanveer’s version correct i.e., does it find the key if it is present and return -1 if is not
present).Justify your answer

No, it’s not correct.

The algorithm searches for key in L for the interval i to j inclusive, if key is present, it should
return the key else It should return -1.

Base Case:
First, we check the base case.
If (i > j) it returns -1, which is correct as that’s an invalid interval.

Recursive call:
Then it selects a point k = (j+j)/2 which simplifies to k = j.
It checks if the key is present at this index k, if it is then it returns the index which is correct.

But, if the key is smaller than the value at index k, then it searches for the key in interval [i..k],
which is the same as [i..j] (as k=j), which is the interval in the current recursive call. So, the

Page | 17
size of the interval doesn’t shrink. It would infinitely call itself with the same interval and never
reach the base case, hence the algorithm doesn’t terminate and is incorrect.

Page | 18