COMP3821 Extended Algorithms and Programming Techniques

COMP3821 Assignment 1
Jinming Dong(z5211275)
March 9, 2020
1
Algorithm:
Sorting the list of integers in ascending order using merge sort takes O(n log n)
running time,and assume we have more than two elements in the array.
For each query,searching the index ix of x and the index iy of y using binary
search takes O(log n) running time.|ix − iy | − 1 is the number of points lying on
the interval between x and y, n queries takes O(n log n) running time.
Time Complexity:
For the above algorithm, the time complexity can be calculate as the the time
taken to sort the array plus the time to search the index of x and y.That is,
time complexity = O(n log n) + O(n log n) = O(n log n)
2
Algorithm:
Sorting the list of integers in ascending order using merge sort takes O(n log n)
running time,and assume we have more than two elements in the array.
To find out whether there exist two elements x, y ∈ S wherex
y = p , we use two
iterators i and j,placed at the index 0 and index 1 of the array respectively.
We computes[j]
s[i] , if it is greater than p, j remains the same and increment i by
1, if it is less than x, i remains the same and increment j by 1.Otherwise, we
have p,then return true.If we loop through the whole array and do not find
the appropriate i and j, then return false.Since we simply go through the array
once, time complexity for this operation is roughly O(n).
Time Complexity:
For the above algorithm, the time complexity can be calculate as the the time
taken to sort the array plus the time to compute iand j. That is, time com-
plexity = O(n log n) + O(n) = O(n log n)
Another algorithm:
For each integer x,if there exists another integer y satisfying thata
b = p, x =
aorx = b, then y must be one of x × p and x \ p .For this question, we have an
array of size 2n, so there are at most 2n potential integers that meet the above
1
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00
https://www.coursehero.com/file/70008924/a1pdf/
This study resource was
shared via CourseHero.com

statement.Thus we can store them in a hash map with size 2n.
For each element x in the array, first check whether it is in the hash map, that
is, hash(x) == 1,if it is,then return true since it has another element y that
we have seen before in the array satisfingx
y = p or y
x = p. Otherwise, compute
its possible matches, namely x × p and x \ p,and store them into the hash map.
We do not need to solve collisions, because duplicate values are allowed.
Time Complexity:
Time complexity of the above algorithm is O(n).We need a loop to go through
the entire array,which is O(n).The check step can be done in O(1) and com-
putation can be done in constant time.Time complexity = O(n) + O(1) + c,
where c is a constant.Therefore, time complexity is O(n).
3
3.1
For each empty containeridentify the balls which is not in containers,if the con-
tainer lights up green,then let the ballin the container and let another empty
container to repeat the same operation until all balls are in containers.
3.2
We set array B contains the balls and array C contains the container
cl:the start index of C
ch:the end index of C
bl:start index of B
bh:the end index of B
Algorithm:
MainAlgorithm(C, B, cl, ch, bl, bh)
· · ·if cl < ch:
· · · · · ·p = SubAlgorithm(B, C[ch], bl, bh)
· · · · · ·i=cl
· · · · · ·for j=cl to ch-1:
· · · · · · · · ·if C[i] identify ball B[p] lights blue or green:
· · · · · · · · · · · ·swap C[i] with C[j]
· · · · · · · · · · · ·i=i+1
· · · · · ·swap C[i] with C[ch]
· · ·MainAlgorithm(C, B, cl, i-1,bl,p-1)
· · ·MainAlgorithm(C, B, i+1, ch,p+1,bh)
cc:the container to partition balls bl:start index of B
bh:the end index of B
SubAlgorithm(B,cc,bl, bh)
· · ·for i = bl to bh:
2
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00
https://www.coursehero.com/file/70008924/a1pdf/
This study resource was
shared via CourseHero.com

· · · · · ·if cc identify ball B[i] lights green:
· · · · · · · · ·swap B[i] with B[bh]
· · · · · · · · ·break
· · ·i=bl
· · ·for j = bl to bh-1:
· · · · · ·if cc identify ball B[j] lights red or green:
· · · · · · · · ·swap B[i] with B[j]
· · · · · · · · ·i=i+1
· · ·swap B[i] with B[bh]
· · ·return i
Time complexity:
It takes O(n log n).
3.3
1. We keep partitioning the array B[bl,...,bh]into lighter balls array parti-
tion B[bl,...,p-1] and heavier balls array partition B[p+1,...,bh], partition-
ing the array C[cl,...,ch] into lighter containers array partition C[cl,...,i-1]
and heavier containers array partition C[i+1,...,ch],handle sub-problem
C[cl,...,i-1] with B[bl,...,p-1] and sub-problem C[i+1,...,ch] with B[p+1,...,bh]
together.For each sub-problem do the same operation until the length of
a sub-array is 1.Thus, it terminates.
2. we first use C[ch]to identify B[bl,bh]to partitioning the array B into
lighterballs array partition B[bl,...,p-1]and heavierballs array parti-
tion B[p+1,...,bh],and then use p identified by C[cl,...,ch]to partition-
ing the array C[cl,...,ch]into lighter containers array partition C[cl,...,i-
1] and heavier containers array partition C[i+1,...,ch].Each container can
be paired with a ballof the appropriate weight.So the size of C[cl,...,i-1]
and B[bl,...,p-1]is same,and the size of C[i+1,...,ch]and B[p+1,...,bh]is
same.Thus the algorithm canassign the balls into the containers one-to-one
so that in each case the balls weight matches the containers expected.
4
4.1
f (n) = Γ(n) = (n−1)!Γ(1) = (n−1)!
R+∞
0 e−t dt = (n−1)!(−e−t ) |+∞
0 = (n−1)!
g(n) = n2
all n ≥ 1,we havef (n) ≤ g(n),so f (n) = O(g(n))
Since we have limn→∞ (n−1)!
n2 = 0,f (n) 6= Θ(g(n)),f (n) 6= Ω(g(n)).Therefore
f (n) = O(g(n)).
3
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00
https://www.coursehero.com/file/70008924/a1pdf/
This study resource was
shared via CourseHero.com

4.2
f (n) = log3 n2nn logn
3 = 2 log3 n + n(log3 n)2
g(n) = n(log3 n)2
Hence,when n ≥ 3,f (n) ≤ c1g(n) and f (n) ≥ c2g(n) for some constant c1 >
2,0 < c2 < 1,so f (n) = Θ(g(n))
4.3
f (n) = (log5 n)5
3
g(n) = log5 3
√ n = 1
3 log5 n
let us assume f (n) ≥ cg(n),where c is a constant,since f (n) grows faster.
For n0 = 1,and n ≥ n0,we have f (n) ≥ cg(n) for some constant c and limn→∞ f (n)
g(n) =
∞ since 3(log5 n)2
3 is not bounded.Thus,f (n) = Ω(g(n)).
4.4
f(n) = n2(3n + cos(πn
2 )) = 3n3 + n2 cos(πn
2 )
g(n) = n3
Hence,when n ≥ 1,f (n) ≤ c1g(n) and f (n) ≥ c2g(n) for some constant c1 >
4,0 < c2 < 2,so f (n) = Θ(g(n))
5
5.1
For the given equation T (n) = 5T (n
4 ) + 2n + n sinn
2
a = 5,b = 4,f (n) = 2n + n sinn
2 = O(n) because sinn
2 is bounded at [−1, 1]
so we have a ≥ 1,b ≥ 1,nlogb a = nlog4 5 ≈ n1.16,then f (n) = O(nlog4 5− ),for
some 0 < < 0.1,which is case 1 of Master Theorem, Then T (n) = Θ(log4 5)
5.2
For the given equation T (n) = 2T (n
5 ) + n2√ n
a = 2,b = 5,f (n) = n2√ n = n5
2
so we have a ≥ 1,b ≥ 1,nlogb a = nlog5 2 ≈ n0.43,then f (n) = Ω(nlog5 2+ ),for
some 0 < < 2.07,there exit some constant c > 0 such that af (n/b) = cf (n)
which is case 3 of Master Theorem, Then T (n) = Θ(f (n)) = Θ(n
5
2 )
5.3
For the given equation T (n) = 3T (n
2 ) + 3log2
n+3
4
a = 3,b = 2,f (n) = 3log2
n+3
4 = 3log 3 n+3
4
log 3 2 = n+3
4
log2 3 = 1
9 (n + 3)log2 3
so we have a ≥ 1,b ≥ 1,let g(n) = n logb a = n log2 3,then we should have
f (n) = Θ(g(n)) to apply master theorem.
4
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00
https://www.coursehero.com/file/70008924/a1pdf/
This study resource was
shared via CourseHero.com

To show,f (n) = Θ(g(n)) there exit constant c1,c2 and n0 such that
0 ≤ c1g(n) ≤ f (n) ≤ c2g(n) for all n ≥ n0
We know that n is an integer,f (n)
g(n) = 1
9 ( n+3
n )log2 3 and c1 ≤ min(f (n)
g(n) ), c2 ≥
max(f (n)
g(n) )
Thus we take 0 < c1 ≤ 1
9 and c2 ≥ 1,the equation holds for alln > n 0.By
Master Theorem,T (n) = Θ(nlog2 3 lg n).
5.4
For the given equation T (n) = T (n − 1) + logn−1
n
a = 1,b = 1,f (n) = logn−1
n ,which does not satisfy the condition of Master The-
orem.
T (n) = T (n − 1) + logn−1
n
= T (n − 2) + logn−2
n−1 + logn−1
n
= T (n − 3) + logn−3
n−2 + logn−2
n−1 + logn−1
n
= T (1) + log1
2 + .... + logn−1
n
= T (1) + log1
2 × 2
3 ...., n−2
n−1 × n−1
n
= T (1) − log n
= Θ(log n)
5
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00
https://www.coursehero.com/file/70008924/a1pdf/
This study resource was
shared via CourseHero.com
Powered by TCPDF (www.tcpdf.org)