COMP4600/COMP8460 — Assignment 1 for 2018

This article provides solutions for COMP4600/COMP8460 — Assignment 1 for 2018. It includes simplification of expressions, finding summations, analyzing algorithms, proving inequalities, and more. The time complexity, recurrence, and running time of the algorithms are discussed. The article also proves the inequalities using Markov's inequality and provides a tight bound for the number of triangles in a diagram.

COMP4600/COMP8460 — Assignment 1 for 2018 1
COMP4600/COMP8460 — Assignment 1 for 2018
Student’s name
Institutional affiliations

COMP4600/COMP8460 — Assignment 1 for 2018 2
COMP4600/COMP8460 — Assignment 1 for 2018
1 (a) Simplify the expressions
(i) Ω (n 8 (log n) 9 + 4e n (log n) 3 − 7(log n) 3 )
n 8 (log n) 9 + 4e n (log n) 3 − 7(log n) 3= n 8. log n 9 + 4e n .log n 3 – 7.log n. 3
let n8 =K, 4e n=m
K. log K n + m .log n 3 – 7.log n 3
Ω (( n+k)(log K) + 3m (log n)– 10(log n))
Ω(log (K n+k +n3m)/(n10) )
(ii) n2 log n+O(n)
( logn)2+O(log n)
0(n) =1
0(log n) =log n
Taking n2 as k
Then :
(log nk +1 )/(log nk)
(iii) Θ(g(n)) + o(g(n)), where g(n) is a function that is positive for large enough n
Definition:
Let f and g be two functions f, g : N → R + . We say that
f(n) ∈ Θ(g(n))
if there exist constants c1, c2 ∈ R + and n0 ∈ N such that for every integer n ≥ n0,
c1g(n) ≤ f(n) ≤ c2g(n)
Θ(g(n)) = O(g(n)) ∩ Ω(g(n))
Replacing Θ(g(n))
Then:
O(g(n)) ∩ Ω(g(n)) + O(g(n))
(b) Find expressions for the following summations (as a function of n) using the Θ( ) notation
∑
k =1
n
¿¿
∑
k =1
n
( 3 n2−9 ) 3
=( 27 n6
727 )= 27 n!6
729! ( n ) !
¿ 1
27 n6 ( n )= 1
27 n7

COMP4600/COMP8460 — Assignment 1 for 2018 3
The time complexity is Θ(n7)
(c) Using the Θ( ) notation, what is the running time of this code fragment as a function of n?
i := 1
sum := 0
while i ≤ n do
for j from 1 to i do
prod := 1
for k from 1 to i do
prod := prod ∗ k
endfor
sum := sum + prod
endfor
i := i ∗ 3
endwhile
Solution
At the while loop, the increment of i is not linear as it in goes from 1,3,9,…i*3.
Analysis of the increment of i :
i = 1, i<=n, i=i*3
1st execution i=1=30
2nd execution i=3 = 31
3rd execution i=9 = 32
Nth exection i= 3n-1
The algorithm stops when 3n-1 =n
Taking n-1=k
Then while loop stops when 3k=n

COMP4600/COMP8460 — Assignment 1 for 2018 4
Time taken
K= log3n
Note that when n is 1, the estimation runs one times. This shows the lower bound of the
computation as Ω(n). The for-circles are dependent of the expansion of I, which implies every
increase result to i3 number of times. In this way the time unconventionality of the estimation if
0(log3n) - the upper bound. Relating the lower bound and upper bound, we can for the most part
reason that the two cases fuse the 3k=n. Giving it a tight bound of Ө(log3n).
(d) (i) Write a recurrence for the running time.
COMP4600 Is a recursive function that calls itself referencing to the value of n. S1, S2, S3 call the
function are run equal times since the values of P1, P2, P3 is the same. Values of S1, S 2, S3 are
gotten when n is less than 3. The function ends when n is less than 3.
Recurrence
funtion COMP4600(problem P of size n)
if n ≤ 3 then
return the solution --------- base case=T(o)
else
Divide P into 3 subproblems P1, P2, P3 of size n/3
S1 := COMP4600(P1) ----- 0(n)
S2 := COMP4600(P2)------ 0(n)
S3 := COMP4600(P3) ----- 0(n)
Combine S1, S2, S3 into the solution S
return S -----------------------T(n)
endif
endfunction
recursive relation = n+n+n = 3n
T(n)= Ө(3n).
(ii) Demonstrate how to guess a solution of the recurrence by applying the recurrence repeatedly
to it.
Since S1, S 2, S3 take the same time, while n reduces by the factors of 3. Then estimation of the
solution would base on the factors of 3 in n while assuming the decimals in the result. Given the
factors of 3 in n to be k, then:
Recursive relation = kn + kn + kn = 3kn
T(n)= Ө(3kn).
(iii) Use induction to prove your guess is correct.
Induction: assume for some arbitrary value of n than T(n)= Ө(3kn), decimals are assumed
(Bubeck, 2015, Pg. 234).
T(n)=0---base case

COMP4600/COMP8460 — Assignment 1 for 2018 5
Let n=1, 2
K= 1/3, 2/3,
K of 2, 3 =0.33, 0.66 assuming the decimals, k=o,o
Induction case
T(1)= Ө(3*0*1)
T(1)=0
T(2)= Ө(3*0*2)
T(2)=0
Conclusion:
Thus we conclude that T(n)= Ө(3kn).
2(a) The procedure is a sorting function – Mysort, that takes two arguments A and n. In this
algorithm, a nested loop is used. The different invariant holds – in the j-th times of the outer
loop, there is a relative ordering of in the items of A[0] through A[j-1]. In order to insert an item
in a relative position of the sort, there is a necessity of moving values to the right to make room.
The first two items are put in the correct relative order, and then the third item correct to the first
two in that order until the whole array of data is sorted.
(b)
(n-1)+(n-2)+….+1=∑
i=1
n −i
i=∑
i=1
n−1
( i
1 )
∑
i=1
n −1
( i
1 )=(n
2 )= n !
2! ( n−1 ) ! = 1
2 n ( n−1 )=1
2 n2−n
The time complexity is Θ(n2 )---Worst case scenario.
(c) Basing on distinct elements of a random order that would give equally likely n! possible
orders under this sort, then the lower bound would not be any different from the time complexity
(Deb, 2014, Pg. 415). Hence Ω(n2 ).
3. (a) Prove that when the following algorithm finishes, the stack contains exactly those students
who can see the screen. Initialize a stack S
for i from 1 to n do
while S is not empty and h[i] > h[Top(s)] do
Pop S
Endwhile

COMP4600/COMP8460 — Assignment 1 for 2018 6
Push i onto S
Endfor
First, the algorithm runs
The for-loop runs n times, and for each i-th time, the while –loop runs to pop S if S is not empty
and the height of the student in the h[i] position is greater than that of h[Top(s)], or the position I
is pushed onto S. By the time the algorithm runs n times, only those heights that meet the while
condition shall be popped. Hence, when the algorithm finishes, the stack will contain students
who can see the screen only.
b)
for i from 1 to n do -------------n
while S is not empty and h[i] > h[Top(s)] do----------1
Pop S
Endwhile
Push i onto S
Endfor
T(n)=n+1
Time complexity = Ө(n)
(c) Given that the while loop runs one in every i-th time the for-loop runs, it is evident that the
algorithm depends on the nth times to finish. Hence, the time complexity of 0(n) as provided by
Pal & Wang (2017).
(d) Prove that time complexity
Definition:
f(n)= 0(g(n))
if f(n) ≤ C.g(n) for all n≥ k ….where C and k are positive
(f(n))/(g(n)) ≤ C for all n≥ k
Taking C=4 then:………number of students in the raw

COMP4600/COMP8460 — Assignment 1 for 2018 7
n+1 ≤ 4* g(n) for all n ≥ 1
n+1 ≤ 4* n……………….n=1
2 ≤ 4
Then f(n) = 0(g(n))
Conclusion: we have proved that time complexity of the algorithm is indeed 0(n)
4. Proof that Prob(X ≥ 1) ≤ E(X).
Using Markov’s inequality (Schacht, 2016, pg)
P(X ≥ a) ≤ E(X)/a
Indicator function 1 X ≥ a
Multiplying the indicator function by a constant a:
a(1 X ≥ a)
If x<a then:
a(1 X ≥ a) =0<x
if X ≥ a then:
a (1 X ≥ a) =a≤ x
a (1 X ≥ a)/a= P(X ≥ a) = a/a ≤ x/a ----an equivalent to the probability equation
hence: P(X ≥ a) ≤ E(x/a)
replacing a with 1
P(X ≥ 1) ≤ E(x/1) == P(X ≥ 1) ≤ E(x)
Conclusion: We have proven that Prob (X ≥ 1) ≤ E(x)

COMP4600/COMP8460 — Assignment 1 for 2018 8
5. (a)Let Ik be the indicator function for the edge k, i.e.,
IIk= { 1if kth edge is present
o if k th edge is not present
Quantity of interest:
E (∑
k=1
(n
2 ) IIk )=∑
k=1
(n
2 ) E ( IIk ) --------By linearity of expectation (Le, Levina, & Vershynin, 2017, Pg.
545)
¿ ∑
k=1
(n
2 )
P ( IIk=1 ) =∑
k=1
(n
2 )
P ( kth edge is present )
¿ ∑
k=1
(n
2 )
(1
2 )
Assuming that the likelihood of an edge to be present or absent is equal, then:
1
2 ( n
2)
The approximate tight bound would be Θ( n
2 )
(b) An arbitrary diagram with n vertices and edge likelihood d/n, has a normal number of
triangles that is autonomous of n, to be specific d3/6.
E ( x )❑=E (∑
ijk
∆ijk )=∑
ijk
E ∆ijk= (n
3 ) ( d
n )3
≈ d3
6
Theta notation θ ( d3 )
(c) For each vertex v, there is a random variable Xv that is 1 if v has degree 0 and 0 otherwise as
explained by Dellamonica et al., (2015, Pg. 288).
Then, E(Xv)=P(Xv=1)E(Xv)=P(Xv=1), where the probability is the fraction of random
selections of k edges that leave v isolated, over all possible selections of k edges

COMP4600/COMP8460 — Assignment 1 for 2018 9
Then, by linearity of expectation, the number of isolated vertices is nE(Xv).
(d) To begin, n vectors (of n vertices) v1,...,vn are picked i.i.d. as per some likelihood
appropriation on R k . In the wake of taking this decision, particular vertices I and j are made
nearby with likelihood vi · vj . All sets are viewed as free. Care ought to be taken to guarantee the
conveyance on R k fulfills P( vi · vj ∈/ [0,1]) = 0.
(e) if p(n) = n −1/2 log n
With:
Prob(X ≥ 1) ≤ E(X) and P( vi · vj ∈/ [0,1]) = 0
Then: p(n)= (log n)/n2
Assuming that n ≥ 1:
Then the equation fits in to Markov’s inequality. So Prob(n ≥ 1) ≤ E(n)

COMP4600/COMP8460 — Assignment 1 for 2018 10
Reference List
Bubeck, S., 2015. Convex optimization: Algorithms and complexity. Foundations and Trends®
in Machine Learning, 8(3-4), 231-357.
Deb, K., 2014. Multi-objective optimization. In Search methodologies (pp. 403-449). Springer,
Boston, MA.
Dellamonica Jr, D., Kohayakawa, Y., Rödl, V., and Ruciński, A., 2015. An improved upper
bound on the density of universal random graphs. Random Structures &
Algorithms, 46(2), 274-299.
Le, C. M., Levina, E., and Vershynin, R., 2017. Concentration and regularization of random
graphs. Random Structures & Algorithms, 51(3), 538-561.
Pal, S. K., and Wang, P. P., 2017. Genetic algorithms for pattern recognition. CRC press.
Coja‐Oghlan, A. and Efthymiou, C., 2015. On independent sets in random graphs. Random
Structures & Algorithms, 47(3), pp.436-486.