View more random threads:
- Needed solution of phy(101).
- mcm515 radio news reporting assignment no 2 solution fall...
- Assignment # 1 Computer Proficiency License (CS 001) Fall...
- CS408 Human Computer Interaction Assignment No. 1 Fall...
- MTH301 Calculus II Assignment 3 Solution Fall Semester 2012
- Vuhelp.net website is easy as compare to other websites?
- CS506 Web Design and Development Assignment No 03 Solutions...
- Communication Skills- MCM301 first assignment solution fall...
- First assignment of spring 2011 is cs506 Webdevelopment in...
- CS304 Solution 2nd Assignment Spring 2010 May 4
CS502 Fundamentals of Algorithms Assignment No.2 Fall Semester 26th 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
Sponsored Links
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.)