We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution |
+ 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
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
CS 502 Fundamental of Algorithms
Assignment # 02
Fall 2012
Total Marks = 20
Deadline
Your assignment must be uploaded / submitted before or on Nov 27, 2012
Rules for Marking
Please note that your assignment will not be graded if:
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.)
Tags:
+ How to Follow the New Added Discussions at Your Mail Address?
+ 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?.
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)it is collect from related books so its correct
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(دعا میں یاد رکھنا آپ سب لوگ)
CS502_Assignment#02_Solution
See the attached file please
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??
© 2020 Created by + M.Tariq Malik. Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
VU Students reserves the right to delete profile, which does not show any Activity at site nor has not activity more than 01 month.
We are user-generated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post