CP5602 - Assignment 2 Solution: Advanced Algorithm Analysis

This assignment solution covers several key concepts in advanced algorithm analysis. It includes proving properties of trees with specific node structures, demonstrating insertions into various data structures such as min heaps, binary search trees, AVL trees, and (2,4) trees. Furthermore, it analyzes the time complexity of a modified merge sort algorithm using insertion sort for small sublists, determining the optimal size of these sublists. The solution also applies the Master Theorem and recursive tree method to solve recurrence relations and implements a brute force algorithm for pattern matching in strings. This comprehensive solution aims to enhance understanding of algorithm design and analysis.

Running head: ANSWER TO ASSIGNMENT 2
ANSWER TO ASSIGNMENT 2
Name of the Student
Name of the University
Author Note

1ANSWER TO ASSIGNMENT 2
1. It is given that nI is the number of internal nodes and nE is the number of external
nodes. Now, it is needed to be found that if each internal node in T has 3 children then
nE=2nI +1.
Now, let the statement is true for m nodes (m < n)
Hence, mE =2∗mI +1
Now, let the internal nodes is increased by 1.
Hence, mInew = mI + 1.
Hence, mEnew = mE – 1+3 (as with the increase of each external nodes 3 internal nodes
are increased excluding the external node).
= 2∗mI +1 – 1 + 3 = (2mI + 2) + 1 = 2(mI + 1) + 1 = 2∗mInew +1
Now, in the similar way extending the result by method of induction it can be shown
that if every internal node of T has exactly 3 children then nE=2nI +1.
2. a)
The heap min binary tree after insertion of 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19,
23, 14 is shown by the following tree.
Min heap tree:

2ANSWER TO ASSIGNMENT 2
b) Binary Search tree is given below.

3ANSWER TO ASSIGNMENT 2
c) AVL tree:

4ANSWER TO ASSIGNMENT 2
d) [2,4] tree:
3.
i) Given the input is of size k and the worst-case time of insertion sort runs by O(k^2)
of worst-case time. Hence, the running time is of the quadratic form given by ak^2 +
bk + c. Thus the worst case time required for sorting n/k sublists having length k for
insertion sort algorithm is given by the following equation.
T(k) = (n/k)*(ak^2 + bk + c) = ank + bn + cn/k
As k is very small than n hence if n is very large then the last two terms of T(k) can be
ignored.
Hence, T(k) = O(nk).
ii) It is given that there are total of n elements that are divided into n/k sorted sublists
having each of k length. Now, for merging the sorted sublists it is required to take 2
sublists at a time and then the merge needs to be continued. All total the steps
required for merging n/k sorted sublists is log(n/k). In each step n elements are being
compared and hence the time complexity of the whole process will be O(nlog(n/k)).

5ANSWER TO ASSIGNMENT 2
iii) Now, in order to have the modified algorithm, exact same asymptotic running time
like the standard sort the time complexity O(nk + nlog(n/k)) needs to be same as
O(nlogn).
If the above condition needs to be satisfied then k can’t go any faster than the
asymptotic increase of log(n). This is because if increase of k becomes faster than
log(n) then the algorithm will be running at worst case asymptotic time more than
O(nlog(n)) because of having the nk terms.
Now, if k = O(log(n)) then
O(nk + nlog(n/k)) = O(nk + nlog(n) – nlog(k)) = O(nlog(n) + nlog(n) – nlog(log(n)))
= O(2nlog(n) – nlog(log(n))) = O(nlog(n)) (as log(logn)) is significantly smaller than
log(n) for large n)
Hence, the best value of k is O(log(n)).
4.
i) The general for of the master theorem is given by,
If the recurrence relation is of form
T(n) = aT(n/b) + f(n)
Here,
a,b >=1 are positive constants and f(n) is asymptotically positive.
If f(n) = O (nlogb (a −e ) ) for some e > 0, then
T(n) = Θ ( nlogb a )
Now, the given recurrence relation is T(n) = 3T(n/2) + n
a = 3, b = 2, e=1 and f(n) = n = nlog2 (3−1 )

6ANSWER TO ASSIGNMENT 2
Hence, T(n) = Θ ( nlog2 3 ) by Master theorem.
Hence, the fixed asymptotic bound by Master theorem of the recurrence relation is
T(n) = Θ ( nlog2 3 ).
ii)
Recursive tree method:
At level 0 cost = n
Level 1 cost = n/2 + n/2 + n/2 = 3n/2
Level 2 cost = (n/4)*9
Let at x level the cost is 1.
Hence, by recursion T(n) = Θ ( nlogb a )
iii) Similarly, by substitution method it can be shown that for substitution method the
asymptotic bound is T(n) = Θ (nlogb a )
5. Given text is ‘advancedalgorithmanalysis’. Now, for finding the ‘rithm’ pattern the
brute force algorithm is chosen to be employed.
Brute force algorithm:

7ANSWER TO ASSIGNMENT 2
S = ‘advancedalgorithmanalysis’
P = ‘rithm’
SL = len(S)
PL = len(P)
if PL > SL:
print("pattern is larger than source string. No match found")
else:
Found = False
for i in range(0,SL):
j = 0
while j < PL and S* == P[j] :
i=i+1
j=j+1
if j == PL:
Found = True
print("found match at " + str(i-PL+1))
if not Found:
print("No Matching Found")