[SOLVED] Cs5800 – algorithms problem set #5 problem #1 a complete binary tree of height h has “no holes”: i.e reading from top-bottom and left-to-right

CS5800 – Algorithms
Problem Set #5
Problem #1
A complete binary tree of height h has “no holes”: i.e reading from top-bottom and left-to-right, every
node exists. An almost complete binary tree has every node until the last row, which is allowed to stop
early.
Figure 1: complete (perfect) binary tree (left) and almost complete binary tree (right)
(a) Prove by mathematical induction that a complete binary tree with height, h, contains precisely
2
h+1 − 1 nodes
(b) How many leaves does an almost complete binary tree of height, h, have? Give the smallest and
largest possible values, and explain. Note, by definition every complete binary tree is almost complete tree.
(c) The diameter of a tree or a graph is the maximum distance (length of the longest path) between
nodes. Whats the diameter of an almost complete binary tree of height, h. Give the smallest and
largest possible values and explain
(d) Suppose that we “reroot” a complete binary tree of height, h, by designating one of the erstwhile
leaves as the root. What is the height of the rerooted tree?
(e) What is the diameter of a complete binary tree rerooted at one of its leaves?

Problem #2
A binary heap is called a max heap if it has the property that for every node i other than the root, the
value of the node is at most the value of its parent.
Below is an example of a max heap with 10 nodes (i.e., 10 elements), presented both as a binary tree and
as an array.
Figure 2: Max Heap with 10 nodes
(a) The height of a heap is defined to the number of edges on the longest downward path from the root
node to a leaf node. Thus, in the example above, the height of the heap is h = 3.
If a (binary) heap has height h = 6, determine the minimum number and maximum number of
elements that can be in this heap. Clearly justify your answer.
(b) Consider an unsorted array of n elements. Recall that the Heapsort Algorithm consists of two
parts: first we run BUILD-MAX-HEAP to convert our input array into a max heap, and then we
run MAX-HEAPIFY n times to generate the n elements of our sorted array.
Demonstrate the Heapsort Algorithm on the input array [5, 2, 1, 7, 6, 3, 4]. Clearly show your steps.
(c) In part (b) above, you should have noticed that after the i = 2 iteration of MAX-HEAPIFY, your
heap was [5, 3, 4, 2, 1, 6, 7]. Notice how the first n − i elements form a max heap, and the last i
elements are sorted and are the i largest elements of the array.
Show that this property holds for any max heap with n elements. Specifically, prove that for
all 1 ≤ i ≤ n, after the i
th iteration of MAX-HEAPIFY, the first n − i elements form a max heap,
and the last i elements are sorted and are the i largest elements of the array.
(d) Let P be a permutation of the first 7 positive integers. Sometimes this permutation is a max heap;
examples include [7, 6, 5, 4, 3, 2, 1], [7, 6, 4, 2, 5, 1, 3], [7, 5, 6, 2, 4, 3, 1], and [7, 3, 6, 2, 1, 4, 5].
If P is a randomly-chosen permutation of [1, 2, 3, 4, 5, 6, 7], determine the probability that it is
a max heap. Clearly and carefully justify your answer.