Expected depth of the kth smallest element

Assignment Help Basic Computer Science

Reference no: EM13968203

1. Show the following regarding the maximum item in the heap:

a. It must be at one of the leaves.

b. There are exactly fN/21 leaves.

c. Every leaf must be examined to ?nd it.

2. Show that the expected depth of the kth smallest element in a large complete heap (you may assume N = 2k - 1) is bounded by log k.

3. a. Give an algorithm to ?nd all nodes less than some value, X, in a binary heap. Your algorithm should run in O(K), where K is the number of nodes output.

b. Does your algorithm extend to any of the other heap structures discussed in this chapter?

c. Give an algorithm that ?nds an arbitrary item X in a binary heap using at most roughly 3N/4 comparisons.

Reference no: EM13968203

Questions Cloud

Problem regarding the complexity of algorithm : If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?

For the soon-to-be-incorporated firm of ebroadcast sports : Dennis is a promoter for the soon-to-be-incorporated firm of eBroadcast Sports, Inc. Dennis signs a contract with Fitz & Geraldo, Accountants, to render their services before eBroadcast Sports is incorporated and for one year after the incorporation.

Running time of both algorithms for sorted : Compare the running time of both algorithms for sorted, reverse-ordered, and random inputs.

Marketing decision that results in dramatic decrease : Donatello is a director and officer of Enzio's Pizza Corporation. Donatello selects an ad campaign that consumers find offensive? a marketing decision that results in a dramatic decrease in profits for the firm and its shareholders. Donatello is a di..

Expected depth of the kth smallest element : Show that the expected depth of the kth smallest element in a large complete heap (you may assume N = 2k - 1) is bounded by log k.

Discuss norman augustine and dilbert contribution : Why was the DII so important to the eventual success of Lockheed Martin's ethics program? Discuss Norman Augustine's and Dilbert's contribution in helping Lockheed Martin turn the corner with its ethics program

Identify also range of discounting rates in which project : "Carolina Company is considering Projects S and L, whose cash flows are shown below. These projects are mutually exclusive, equally risky, and are not repeatable. If the decision is made by choosing the project with the higher IRR, how much value wil..

Cause safety stock to increase : Which of the following would cause safety stock to increase?

Order to minimize the total production cost : Golf Shafts, Inc. (GSI)) produces graphite shafts for several manufacturers of golf clubs. Two GSI manufacturing facilities, one locate in San Diego and the other in Tampa , have the capabilities to produce shafts in varying degrees of stiffness, For..

User Account

All Pages