Homework 3 PDF

Preview

Summary

Homework 3...

Description

Sawyer Mahony 1210002141 CSE 310 MW 12:15 Homework 3 1. a. The root node would be in A[1] it’s children nodes are in t such that A[2]…..A[1+t] where they are in order. From there the next level would be A[2+t]…..A[1+ t + t^2] this continues on. b. Extract-max(Array,n) Value=Array[1] Array[1]=A[n] N=n-1 MakeHeap(Array,1,n) Return Value Insert(Array, t, n, d) N=n+1 Array[n]=-inf Array[k]=max(array[k],d) If d = array[k] Array[k]=array[k-1] K=array[k-1] c. Heap-Increase-key(A,I,k) A[i]=max(A[i],k) If k=A[i] While i>1 A[i]=A[i-1] I=A[i-1] d. The higher d, or the base of the log. The more efficient the algorithm 2. 9 – 3,2,1,0,7,5,4,8,6 8 – 3,2,1,0,7,5,4,6 7 – 3,2,1,0,6,5,4 6 – 3,2,1,0,4,5 5 – 3,2,1,0,4 4 – 3,2,0,1 3 – 2,0,1 2 – 0,1 1 –0

3.

4. The running time Is proportional to the length of the list O(1+a), thus the modifications doesn’t affect running time. Same holds for deletion it doesn’t affect the running time, however on insertion the time is O(1) which changes to O(1+a) which is affected by his modifications 5. Smallest leaf is n-1 so smallest number of comparisons is also n-1...