CS502-Spring2014
Assignment 2
Deadline
Your assignment must be uploaded/submitted at or before 23rd May 2014.
Uploading instructions
Please view the assignment submission process document provided to you by the Virtual University to upload the assignment. And submit your solution as Microsoft word file.
Rules for Marking
It should be clear that your assignment will not get any credit if:
- oThe assignment is submitted after due date.
- oThe submitted assignment does not open or run.
- oThe assignment is copied
Objectives
.This assignment will help you to understand the concepts of Asymptotic Growth rate and how growth rates participate in for efficiency of algorithms, designing code for different scenario, and asymptotic function understanding and perception Heap sort and its variants..
Guidelines
Guidelines: Function Growth rate concept:
If some function f1(x)>f2(x) for positive values of x then the function f1(x) is said to have greater growth rate then f2(x). For example f1(x)=x5 and f2(x)= x6 it is obvious that f2(x) has greater growth rate ( 26 > 25).This concept relate to complexity of algorithm ,an algorithm having greater growth rate function means the algorithm has greater complexity here f2(x) is more complex then f1(x).
Estimated Time 2.5 hours
For all parts of the question to understand maximum time is 1.25 hours and for understandings and searches and 1.25 hour for developing solution. It all depends upon your sheer and devoted concentration.
Special notes:
To solve the assignment you should have grip on the delivered lessons and also consult above guidelines to perceive completely. And third chapter of third chapter “Growth of Functions” of your text book introduction to Algorithms by “Thomas H.Coreman” with peace of mind and heart.
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.
