We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# CS502 - Fundamentals of Algorithms Assignment # 2 discussion and solution Due date is November 27, 2012.

CS 502 Fundamental of Algorithms

Assignment # 02

Fall 2012

Total Marks = 20

Your assignment must be uploaded / submitted before or on Nov 27, 2012

Rules for Marking

• • It is submitted after due date
• • The file you uploaded does not open
• • The file you uploaded is copied from someone else or from internet
• • It is in some format other than .doc

Note: Material that is an exact copy from handouts or internet would be graded

Zero marks. Your solution should consist of the material found through different sources and written in your own words.

Assignment Statements:

Question 1:

Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω (lg n).

(Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)

Question 2:

Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 /b> α which is ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 3345

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Attachments:

### Replies to This Discussion

it is collect from related books so its correct

dua mje is book ka link 2 l.ms se

Yes........... I agreeeeeeeee

is mai changing kese krain??

ap in is link sy book ka solution manual download kr k apnin assignment khud sy solve krai

Dua mai yad rakhna ap sub log(دعا میں یاد رکھنا آپ سب لوگ)

thanks a lot bhai

CS502_Assignment#02_Solution

Attachments:

Q2

Solution:

The minimum depth follows a path that always takes the smaller part of the partition

.i.e., that multiplies the number of elements by α. One iteration reduces

the number of elements from n to αn, and i iterations reduces the number of elements

to αin. At a leaf, there is just one remaining element, and so at a minimumdepth

leaf of depth m, we have αmn = 1. Thus, αm = 1/n. Taking logs, we get

m lg α = −lg n, or m = −lg n/ lg α.

Similarly, maximum depth corresponds to always taking the larger part of the partition,

i.e., keeping a fraction 1 − α of the elements each time. The maximum

depth M is reached when there is one element left, that is, when (1 − α)Mn = 1.

Thus, M = −lg n/ lg(1 − α).

All these equations are approximate because we are ignoring ßoors and ceilings.

poucha  max  heap  gaya  ha  lakin ans  me  root  nood  ko  smallest  kaha  gaya  than  how it  will  be  right  ans??????

Heap is implemented by a tree stored in an array.

guys please confirm me that the posted solution is right or wrong??

koi bta dy k yai solution true hai kya

## Latest Activity

Rabia Imran joined + M.Tariq Malik's group

### ENG201 Business and Technical English Writing

2 minutes ago
2 minutes ago
3 minutes ago
+ + + Haniya + + + liked + + + Haniya + + +'s discussion HAZRAT ALI (R.A)
5 minutes ago
+ + + Haniya + + + posted discussions
5 minutes ago
6 minutes ago
+ + + Haniya + + + liked + + + Haniya + + +'s discussion WAQT DOST OR RELATION
8 minutes ago
Rao ! posted a status
"guys my account was deleted due to non participation in group activities. please guide me, how it is recovered ."
11 minutes ago
14 minutes ago
+ + + Haniya + + + liked + + + Haniya + + +'s discussion FOR MY BEST FRIEND
15 minutes ago
21 minutes ago
23 minutes ago

1

2

3