Recitation 04 sol PDF

Preview

Summary

Recitation answers...

Description

CSE 310 Recitation 4 Name Section – Dr. Richa (M/W/Th/F) (Circle one) ASU ID Instruction 1. Binary tree, Heaps (array representation, tree representation, max heap, min heap), Heapify Recitation Exercise Quiz 1. Derive the recurrence relation and solve it to find the Big-O for the HEAPIFY algorithm shown below.

1

2

2. A. Give the complete binary tree representation for the following integer array [100, 10, 50, 60, 40, 25, 35, 20, 25, 25, 15, 17, 13, 30, 3, 5, 10, 8] B. You can see that this is not a max heap. Use the pseudo code for HEAPIFY in the previous problem to draw the intermediate complete binary trees until you obtain a max heap.

3

3. Show that the height of a complete binary tree on n = 2h+1 - 1 nodes, where h is an integer ≥ 0, is Θ(log n).

4...