COMP220/506 ASSIGNMENT 1
DUE ON 3 JAN, 2022 (MON)
Q1. (40 marks)
Rank the following functions by order of growth; that is, find an arrangement g1, g2, · · · , g30
of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), · · · , g29 = Ω(g30). Partition your list
into equivalence classes such that functions f(n) and g(n) are in the same class if and only
if f(n) = Θ(g(n)).
lg(lg∗ n) 2lg
∗ n (
√
2)lgn n2 n! (lg n!)
(32)
n n3 lg2 n lg(n!) 22
n
n1/ lgn
ln lnn lg∗ n n · 2n nlg lgn lnn 1
2lgn (lg n)lgn en 4lgn (n+ 1)!
√
lg n
lg∗(lg n) 2
√
2 lgn n 2n n lg n 22
n+1
Q2. (60 marks)
a. Implement a Queue using Stack(s). How many stacks do you need? You also need
to show the pseudocode of enqueue() and dequeue() operations.
b. Implement a Stack using Queue(s). How many queues do you need? You also need
to show the pseudocode of push() and pop() operations.
Late Penalty. 0 mark if not submit on time (i.e., firm deadline).