## Question 1

(a) Determine the time complexity of the function binary _{—}min (arr) below, based on the number of comparisons mini < min2 in line 8.

def binary_min(arr):

if len(arr) == 1:

return arr[0]

else:

mid = len(arr)//2

min1 = binary_min(arr[0:mid))

min2 = binary min(arr(midden(arr)))

if minl < min2:

return minl**else:****return min2**

(b) What is the time complexity of binary_min(arr) in Big-0 notation? Show your derivation steps clearly.

## Question 2

- Discuss how a stack can be implemented using two queues. Provide the push, pop, peek, and count algorithms in terms of the queue’s enqueue, dequeue, peek, and count operations. Determine the Big-0 time complexity in each case.
- Are you able to implement a stack using just one queue
^{,}If Yes, please provide the Pop(only) algorithm to simulate the stack operations with just one queue. If no, explain.

**Question 3**

(a) Design a non-recursive algorithm print_kth_level_leaves (root, k) that will take in the root of a binary tree and a positive integer k and print out the values of all the leaf nodes at level k of the tree. Note that the root is at level 1 and its child nodes are at level 2 and so on.

As an illustration, for the given binary tree t in figure 1:

- print_kth_level_leaves (t. root, 3) will print D and G
- print_kth_level_leaves (t. root, 4) will print F
- print_kth_level_leaves (t. root, k) will print nothing for k = land 2 since there is no leaf nodes at level 1 and 2.