CS502-Fundamentals of Algorithms Assignment No. 02 Solution Last Date 23rd May 2014

[Vuhelper]

[SIZE="3"]

CS502-Fundamentals of Algorithms Assignment No. 02 Solution and Discussion Fall 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.
NOTE: Submit “.doc” file only. Every student should provide his/her own work, exact copying of the assignment (or some portion of the assignment) from the internet or other students will lead to copy case and zero marks will be awarded.

[/SIZE]

[vuassignments]

Max-heaps

We define a max-heap as a heap that satisfies the property that A[PARENT(i)] ≥ A[i] for all i, i.e. the value of every parent is greater than both children. Thus for a max-heap, the largest value is stored at the root.

Creating a max-heap

Building a max-heap from an array involves two routines

MAX-HEAPIFY(A,i) - maintains the max-heap property by assuming that the branches of the binary tree rooted at the children of node i are max-heaps but that node i may be smaller than either (or both) of its children. Thus it percolates node i down through the max-heap such that the branch starting at node i is a max-heap.
BUILD-MAX-HEAP(A) - creates a max-heap from an array by calling MAX_HEAPIFY() from the "bottom up" of the array (such that at each step the bottom branches are max-heaps).

[vuassignments]

CS502-Fundamentals of Algorithms Assignment No. 02 Idea Solution




  Untitled.jpg (Size: 44.68 KB / Downloads: 530)