CS502 Fundamentals of Algorithms Assignment No.2 Fall November 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 < α 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.)