Show Bid Request

EASY Hashing questions
Bid Request Id: 14530

Posted by:	Brickle (4 ratings) (Software buyer rating 10)
Posted:	4/24/2002 8:02:47 PM EST
Bidding Closes:	4/25/2002 9:46:57 PM EST
Viewed:	130 times

Phase:	100% of work was accepted by buyer. Coder account has been credited.
Max Accepted Bid:	Bidding is closed
Project Type:	Personal Project / Homework Help
Bidding Type:	Open Auction
Categories:	C++ / C

Enter chat room for this bid request
(0 active users at 7/20/2002 12:12:53 PM EST)

Description:
Use the function hash (KEY, MAXAD)
int Hash (char key[12], int maxAddress)
{
int sum = 0;
for (int j=0; j< 12; j += 2)
sum=(sum+100*key[j]+key[j+1])%19937;)
return sum % maxAddress;
}
to answer the following questions:

a) What is the value of hash (“Jacobs ”, 101) ?

Letter ASCII code

J - 74

a - 97

c - 99

o - 111;

b - 98

s - 115

white space - 32

b) It is assumed in the text that the function hash does not need to generate an integer greater than 19937. This could present a problem if we have a file with addresses larger than 19937. Suggest some ways to get around this problem.

2. There is a surprising mathematical result called the birthday paradox that says that if there are more than 23 people in the room, there is a better than 50/50 chance that two of them have the same birthday. How is the birthday paradox illustrative of a major problem associated with hashing?

3. In understanding hashing, it is important to understand the relationship between the size of the available memory and the number of keys to be hashed, the range of possible keys, and the nature of the keys. Let us give names to these quantities, as follows:

M = number of available slots (each for one record only);

r = number of records;

n = number of unique addresses produced by hashing function;

K = a key, which can be any combination of exactly five uppercase letters.

Suppose h(K) is a hash function that generates addresses between 0 and M-1

a) How many unique keys are possible? (Hint: if K were only one uppercase letter rather then five, there would be 26 possible unique keys;

b) How are n and r related?

c) How are r and M related?

d) If the function h, where a minimum perfect hashing function, how would n, r, and M be related?

4. Suppose that 10 000 addresses are located to hold 8 000 records in a randomly hashed file and the each address can hold one record.

Compute the following values:

a) The packing density for the file;

b) The expected number of addresses with no records assigned to them by the hash function;

c) The expected number of addresses with one record assigned (no synonyms);

d) Expected number of addresses with one record plus one or more synonyms;

e) The expected number of overflow records;

f) The expected percentage of overflow records.

Deliverables:
Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

Complete copyrights to all work purchased.
Answers on Microsoft word

Platform:
Must be in Microsoft Word. PLEASE PLEASE restore my faith in Rentacoder! My last coder did not contact or finish the assignemtn until 3 days past the due date. I must have this by my deadline. No exceptions. No deadline = no money.

Must be 100% finished and received by buyer on:
Time legal notes: All times are expressed in the time zone of the site EST (GMT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EST on the indicated date.
4/26/2002

Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements. We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation. If you notice a violation, you can report it to: abuse@rentacoder.com.

Bidding/Comments:

All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests.

See all rejected bids (and all comments)

Name Bid Amount
Date Coder Rating

This bid was accepted by the buyer!

progwriter
(14 ratings)
in Sofia, Stolichna
Bulgaria

$15 4/25/2002 4:43:19 AM EST 9.71
(Excellent)

I have already completed most of the points.Waiting to see whos bid you will accept.

See 1 private reply(ies)
to/from progwriter.