CS502 Fundamentals of Algorithms Assignment 2 Solution Spring 2014

Question  1                     (10)

Arrange the following in the Most to least complexity. Here “n “is the input size for the some complexity function and j> k  where j , k are numbers greater than 2.Every function is separated by “comma” and note that there are 20 functions to arrange.

Question  2 (5+5)

a) You have to build Max heap for the given array elements along with their respective array positions;

Array =  { 25,13,20,8,7,17,2,5,4}

  b) You have to perform Heap sort on the tree that you have built in Q.No.1. Illustrate all steps of Heap sort one-by-one in sequential way. Also show all elements in sorted order in an array.    

Important Note: Where the base of “log “has not been mentioned take it as base “2”

Build your Max heap and sorted Array positions graphically as presented in Figure No. 4.2 at Page 42 in handouts. You have to follow the same style.