CS502 Fundamentals of Algorithms Assignment No.2 Fall Semester 26th November 2012

[Vuhelper]

View more random threads:

• Check Online ACC 501 Mid Term Current Paper 2014-15
• Solution (Spring 2010) English Comprehension (ENG 101)
• CS410 Visual Programming Assignment No.2 Fall Semester 23rd...
• IT430 E-Commerce Assignments No. 1 Solution and Discussion...
• isl201 assignment
• CS502 Assignment 6 Idea Solution 31 July 2010
• Assignment solution eng 301 due date 20 may 2015
• Needed solution of phy(101).
• MKT501 Marketing Management Assignment Solution May 6, 2010
• MGT503 First Assignment idea solution October, fall 2012

CS502 Fundamentals of Algorithms Assignment No.2 Fall Semester 26th November 2012

Sponsored Links


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