Advanced Algorithm Analysis Homework: Solutions and Analysis, CS 420

This document presents solutions to an advanced algorithm analysis homework assignment, covering various topics in algorithm design and analysis. The solutions address five key questions, beginning with a proof related to external nodes in a binary tree. The second question delves into the divide-and-conquer technique for finding the median of two sorted arrays, analyzing its time complexity. The third question explores sorting algorithms, specifically using InsertionSort within a merge sort framework and deriving the optimal value of k. The fourth question focuses on the Master Theorem, applying it to solve a recurrence relation, and constructing a recurrence tree to analyze its time complexity. Finally, the fifth question presents an algorithm to identify a universal sink in a directed graph. The solutions are well-structured, referencing relevant literature to support the analysis.

ADVANCED ALGORITHM ANALYSIS
[Author Name(s), First M. Last, Omit Titles and Degrees]
[Institutional Affiliation(s)]

Question 1
Suppose we have nI=0, then nE=2nI+1=1
and for nI=1, nE=2nI+1=2+1=3
by making an assumption that nE holds for k’<k, it would translate to a situation that for a given
equation nI= k’<k, then the actual value of nE=2nI+1
considering nI=k, then nE=2(k-1) + (3-1). Such an equation demonstrates that the total external
nodes is equivalent to the number of external nodes that the tree having k-+1 internal nodes
added to 3 (which stands for the inclusion of the internal nodes which are to be of 3 children)
less 1(in the creation of the new internal node, one of the external nodes was converted to an
internal node). Thus it is proved that nE=2k-2+3=2k+1 (Weiss, 2012)
Question 2
The algorithm adopts the divide-and-conquer technique. While adopting this divide-and-conquer
technique, an alternation in the lengths of the two sorted arrays T and S is notice. Len (T) is used
in the denotation of the length of T while the length of S is denoted using len (S) at any provided
time.
Any certain iteration given, ms=lens (S)/2 is used in the denotation of the medium index of S
besides medium of S by S[ms]. On a similar note, mT=len (T)/ 2 is used in the denotation of the
medium index of T alongside as the medium of T is denoted by T[mt]. mt+ms and S[ms] can
then be compared against T[mt] that aids in finding the half part i.e. right or left of the arrays i.e.
S or T that may be eliminated or discarded to leave the smaller sub-problems for recursion
(Nissim, 2017).

The algorithm
1st Condition (ms+mt ≥ k)
Condition 1.1 when S[ms] ≥ T [mt ]
Elimination of the right bigger half of array S can be done which means elimination from
S[ms] to one of its ends and followed by recursive calculation of the k-th smallest element that is
in T alongside the left smaller half of S
Condition 1.2 when T[mt] ¿ S[ms]
Under this condition, it is observed that there is direct symmetry with condition 1.1 with the only
difference being that T and S have been exchanged
Condition 2 (ms+mt<k):
Condition 2.1 S[ms]≥ T [ mt ]
This condition involves the elimination of the left smaller half of T array and then the
determination of the (k-mt)-th of the smallest element in S as well as in the right large half of
array S
Condition 2.2 T[mt]>S[ms]
Just like condition 1.2, condition 2.2 has an exact symmetry with condition 1.1, with the only
deviations being an exchange in T and S
Complexity of Time

At a given iteration, there is discarding of half of the certain array and hence the time complexity
is found by O (log (len(S)) +log (len (T))) which is equivalent to O (logn) when the input arrays
S and T are of size n
Question 3
i) Every sub-list having a length of k adopts Ɵ (k2) worst-case time with the use of Insertion-
Sort. n/k* Ɵ (k2) = Ɵ (nk) is used as the worst case time in the sorting of n/k for sublists as this.
ii) Formation of n/2k sub-lists from merging n/k sub-lists takes Ɵ (n) as the worst time case
Formation of n/4k sub-lists from merging n/2k sub-lists takes Ɵ (n) as the worst time case
Formation of n/8k sub-lists from merging n/4k sub-lists takes Ɵ (n) as the worst time case
In general, the merging of 2 sub-lists to form one list needs Ɵ (n) worst-case time
In case there is need to merge lg (n/k), it is possible to merge n/k into a single list and this would
call for Ɵ (n lg (n/k)) to be adopted as the worst case time (Nissim, 2017).
ii) Having Ɵ (nk+n lg (n/k)) =Ɵ (n lg n) demands either of the two conditions which is n lg (n/k)
=Ɵ (n lg n) or nk=Ɵ (n lg n). going by the previous two possibilities, it can be affirmed that the
biggest asymptotic value of k is Ɵ (lg n)
Question 4
i) T (n) = 3T (n/2) + n

a=2, b=3 while f (n) =n for this recurrence and thus the value will be as follows nlogb a =nlog3 2.
Given that f (n) =Ω=(n¿ ¿ log3 2+ ϵ)¿ in which ϵ =0.2, then the case 3 may be adopted of the
master theorem if it can be proved that regularity condition for f (n) exists
proving that the regularity condition remains demands proving the af (n/b)≤ cf (n) when we have
a constant c such that c<1 and all the values of n are adequately large. Should this be proved,
then it can be concluded that T (n) =⊝( f ( n)) when case 3 of the master theorem is used.
Proof of condition regularity
af (n/b) =3(n/4)≤ cf ( n ) for c=0.7 and ≥ 2
the condition regularity has been proved and hence a conclusion can be made that T (n) =
⊝( f ( n))=⊝(n)
ii) Since the lower and upper boundaries of the recurrence are never mandatory in the
determination of the recurrence, a recurrence tree for the recurrence T (n) = 3T (n/2) + n can be
generated
the table is generated on the assumption that n is to an exact power of 2 to facilitate the finding
of the solution as this would make all the sizes of the subproblem be integers. A recurrence tree
as shown below is thus attained:

Being that there is a decrease by a content 2 from a level to the next of the subproblem sizes, T
(1) boundary condition is attained. In finding the depth of the tree, the subproblem size for one
node at a given depth i is established to be n/2i leading to the attainment of n=1 at the pint i=lgn
or otherwise its equivalent at the pint n/2i =1. This would thus see the tree have lgn +1 levels
with the depths ranging from 0, 1, 2, 3… lgn
Calculation of the cost at every level of the tree forms of the basis of the subsequent step. Since
every level is composed of three times more nodes as compared to the previous levels, 3i will be
the number of nodes when the depth is at i and because there is a factor 2 reduction at each level
of the sizes of the subproblem as one moves down the roots, the equation 3i* n/2i=(3/2)in is
adopted in the calculation of the cost of very node at a given depth i where i ranges from
0,1,2,3,…,lgn-1. At the lowest level of the tree in which the depth is lgn, a cost of T (1) is
contributed by 3lgn=3lg3nodes for every node and hence the entire cost of nlg3 T(1) which is
basically ⊝(nlg3) as it is assumed that T(1) is constant and has no effects on the other variables
(Weiss, 2012). The cost of the whole tree is determined through summing up all the cost as
shown:

T ( n ) =n+ 3
2 n+( 3
2 )
2
n+( 3
2 )
3
n+…+ ( 3
2 )
lgn−1
n+⊝(nlg 3)
¿ ∑
k=0
lgn−1
(3
2 )
k
n+¿ ⊝(nlg3 )¿
=
( 3
2 )
lgn−1
3
2 −1
n+⊝(nlg3 )
=2 nlg 3−2 n+⊝( nlg3 )
=⊝( nlg3 )
iii) A correlation appears to exist between the closed form T (n)≤ dnlg 3−cn for some constants d
and c s.t when d>0 and c>0 thereby resembling the recurrence T (n) = 3T (n/2) + n
Question 5: The i-th column is ‘1’ while the i-th row is ‘o’ for a vertex i that is a universal sink
except for aii. Staring from a current entry aii and assuming it is equal to 0; j=j+1 and when the
entry aij be equal to 1; i=i+1. There will be a stop at the entry akn or of the last column of the entry
ank (n=|V|, 1 ≦k ≦∨V ∨¿). No return of a vertex by the algorithm illustrates a universal sink
(Weiss, 2012).

References
Weiss, M. A. (2012). Data structures & algorithm analysis in C++. Pearson Education
Nissim, K. (2017). Using your privacy budget: Tree algorithm and Advanced Composition