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.
