Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
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).