For the programming problems below, include in your hardcopy submission a printout of your algorithm and of the output. Please follow attached submission instructions.
1. (U&G-required) [30 points]
Exercise 6.3-1 (page 159).
Exercise 8.2-1 (page 196).
(U&G-required) [20 points] Exercise 8.2-3 (page 196).
(U&G-required) [30 points] Implement in C/C++ an algorithm that checks if an array of n elements is a max-heap and determine its running time. The algorithm should print “YES, heap” or “Not a heap”, depending on the outcome. Show how your algorithm works
on the following arrays A = [16 14 10 8 7 9 3 2 4 1] and B = [10 3 9 7 2 11 5 1 6].
(U & G-required) [20 points] Exercise 6.3-2 (page 159).
(G-required) [20 points] Exercise 8.2-4 (page 197).
Extra credit:
6. [20 points]
Find the smallest and the largest number of keys that a heap of height h can have.
Prove that the height of a heap with n nodes is ⌊log% ⌋.
