Last modified:
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not attempted" (not applicable). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Hint: A d-ary heap is an array indexed starting at 0 where the parent of the element in position i, p(i), and the k-th child of the element in position i, childk(i), are defined as follows:
The purpose of this problem is to derive the optimal constant in front of the log by using the optimal base (instead of 2) in the definition of exponential height.
for all k >= 1.
Hint: Use an integral approximation to the summation; see pg. 1067 in CLRS.
is
Hint: Use (strong) induction on n and the fact you proved above.
Finally, we note that the quantity
is minimized when c is approximately 2.155, yielding a constant factor of 2.9882 in front of the lg n. This constant is provably as small as possible.