1) (2 pts ea.) Use Master Theorem to solve the following recurrence relations or indicate “not applicable” if Master Theorem does not apply. Explain why.

1. T(n) = T(n/4) + 6 (n²) + n

1. T(n) = 1/6 T(n/4) + sqrt(n) + O(1)

1. T(n) = 5T(n/2) + 4n + 1

2) (4 pts) A function Max-Heapify(A, i) ensures that element i is in its correct location in a max heap.  Show the array after a call to Max-Heapify(Array, 3).

Input Array = [ 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0 ]

3) (4 pts) In the following array representation of a heap, which of the following values are contained in leaf nodes?

A = [ 5, 3, 17, 10, 84, 19, 6, 22, 9 ]

4) (2 pts) In an undirected graph, the sum of the degrees of all vertices is equal to?

5) (4 pts) The post-order traversal of a binary tree is D,E,B,F,C,A.  What is the pre-order traversal?

6) (4 pts) True or false – In a max-heap, the smallest element must be in a leaf node. Justify your answer.

7) (2 pt ea.) Indicate the space complexity (i.e. the extra space required, in big-O terms) for each of the following algorithms:

1. A) Insertion sort

1. B) Merge sort

1. C) Quicksort

8) (4 pts) The height of a binary search tree with n nodes is on the order of?

DETAILED ASSIGNMENT

20201013201149data_stucture_homework