COMP220 506 Assignment 1

DUE ON 4 JULY, 2023 (TUE)

Q1. (60 marks)

Prove or disprove the following statements:

1. $2^{2n} = O(2^n)$
2. $(n + a)^b = \Theta(n^b)$ given $b > 0$
3. $nlgn = \Omega(n^2)$
4. $O(log_{10} n) = O(log_2 n)$ Note: you need to give formal prove or disprove.

Q2. (40 marks)

• a. Implement a Queue using as few Stacks as you can. How many stacks do you need? You also need to show the pseudocode of enqueue() and dequeue() operations.
• b. Implement a Stack using as few Queues as you can. 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).