Rewrite the insertion algorithm

Assignment Help Basic Computer Science

Reference no: EM13968107

In the quadratic probing hash table, suppose that instead of inserting a new item into the location suggested by findPos, we insert it into the ?rst inactive cell on the search path (thus, it is possible to reclaim a cell that is marked deleted, potentially saving space).

a. Rewrite the insertion algorithm to use this observation. Do this by having findPos maintain, with an additional variable, the location of the ?rst inactive cell it encounters.

b. Explain the circumstances under which the revised algorithm is faster than the original algorithm. Can it be slower?

Reference no: EM13968107

Questions Cloud

Series of statements numbered in ascending order : An (old-style) BASIC program consists of a series of statements numbered in ascending order. Control is passed by use of a goto or gosub and a statement number.

What rate is the area of the triangle formed by the ladder : A 13-foot ladder is leaning against a house when its base starts to slide away. By the time the base is 12 feet from the house, the base of the ladder is moving at the rate of 5 ft/sec.

Program to implement the alternative strategy : a. Write a program to implement the alternative strategy. b. If the output polynomial has about O(M + N) terms, what is the running time of both methods?

Can company competitive if they do not continue to innovate : List an example of a company that has been successful due to innovation and forecast what you believe their potential for continued success may be in the next decade?

Rewrite the insertion algorithm : Rewrite the insertion algorithm to use this observation. Do this by having findPos maintain, with an additional variable, the location of the ?rst inactive cell it encounters.

What are the earnings per share on common stock : Percentage analyses, ratios, turnovers, and other measures of financial position and operating results are

Identify a recent entrepreneur who demonstrated a successful : Identify a recent entrepreneur who demonstrated a successful harvest strategy or an unsuccessful harvest strategy and explain the factors contributing to failure (if unsuccessful) using the Capital Cow. (need another example besides Martha Stewar..

Separate chaining hash tables : Reimplement separate chaining hash tables using a vector of singly linked lists instead of vectors. The isEmpty routine for quadratic probing has not been written. Can you implement it by returning the expression currentSize==0?

Write a memo to me that describes your career aspirations : Write a memo to me that describes your career aspirations.

User Account

All Pages