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

Looking For Something at vustudents.ning.com? Click Here to Search

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

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

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

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:

  • • 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 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?


See Your Saved Posts Timeline

Views: 3344

.

+ 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)

Attachments:

Replies to This Discussion

Please disscuss 

get recomended book solution manual ... 

1st and second this assignment both solution are available there..

Best of luck

Please Discuss here about this assignment.Thanks

Our main purpose here discussion not just Solution

ab kro na solution upload ..............HHEHEHEHEHEHEHEHEH......kia DHANSO kisamka assignment aya hey.............

Cs502 2nd Assignment Solution & Discussion Fall Due date:27-11-2012

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:

• 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 grade

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.)

solution:

Consider a cheap of n nodes where the root node has been changed to contain the smallest value of all the nodes. Now when we call max_heap on the root, the value will have to be exchanged down with its child at every level, until it reaches the lowest level. this is because, after every swapping, the value will still be smaller than both its children (since it is the minimum), until it reaches the lowest level where it has no more children .in such a heap, the number of exchange to max- heapify the root will be equal to the height of the tree, which is log n. so the worst case running time is Ω (n log n).

 

Question 2:

Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 /span> α 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.)

solution:

The minimum depth occurs for the path that always takes the smaller portion Of the split, i.e., the nodes that takes α proportion of work from the parent node.The first node in the path (after the root) gets α proportion of work (the size of Data processed by this node is α n), the second one gets α 2 so on. The recursion Bottoms out when the size of data becomes 1. Assuming the recursion ends at Level m, we have:

α mn = 1

or

m = lg(1=n)=lg(α)

Similar argument can be used for showing that the maximum depth is-lgn=lg(1-

α).



sister mil solve ho gai assignment????????

Question No.01

Consider a cheap of n nodes where the root node has been changed to contain the smallest value of all the nodes. Now when we call max_heap on the root, the value will have to be exchanged down with its child at every level, until it reaches the lowest level. this is because, after every swapping, the value will still be smaller than both its children (since it is the minimum), until it reaches the lowest level where it has no more children .in such a heap, the number of exchange to max- heapify the root will be equal to the height of the tree, which is log n. so the worst case running time is Ω (n log n).

Question No.02

The minimum depth occurs for the path that always takes the smaller portion Of the split, i.e., the nodes that takes α proportion of work from the parent node.The first node in the path (after the root) gets α proportion of work (the size of Data processed by this node is α n), the second one gets α 2 so on. The recursion Bottoms out when the size of data becomes 1. Assuming the recursion ends at Level m, we have:

α mn = 1

or

m = lg(1=n)=lg(α)

Similar argument can be used for showing that the maximum depth is-lgn=lg(1-

α).

kya ye solution theek hy?

lagta to theek hi ha

Note @ All: You don’t need to go any other site for this assignment/GDB/Online Quiz solution, Because All discussed data of our members in this discussion are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links.

question 1 solution 100% corect:

solution:

Consider a heap of n nodes where the root node has been changed to contain the smallest value of all the nodes. Now when we call MAX-HEAPIFY on the root, the value will have to be exchanged down with its child at every level, until it reaches the lowest level. This is because, after every swapping, the value will still be smaller than both its children (since it is the minimum), until it reaches the lowest level where it has no more children. In such a heap, the number of exchanges to MAX-HEAPIFY the root will be equal to the height of the tree, which is lg n. So the worst case running time is Ω (lg n).

question 2 solution 100% corect:

Solution:

The minimum depth occurs for the path that always takes the smaller portion Of the split, i.e., the nodes that takes α proportion of work from the parent node.The first node in the path (after the root) gets α proportion of work (the size of Data processed by this node is α n), the second one gets α 2 so on. The recursion Bottoms out when the size of data becomes 1. Assuming the recursion ends at Level m, we have:
α mn = 1
or
m = lg(1=n)=lg(α)
Similar argument can be used for showing that the maximum depth is-lgn=lg(1-α).

best ov luck dont copy paste

RSS

© 2020   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service

.