CS6033 Homework Assignment 3∗ Turn in this assignment as a PDF file on Gradescope
No late assignments accepted
1. Suppose you are given the following keys: 112, 2542, 9992, 5502 and the following hash function h(x)=x mod10.
Hash the keys using the hash function. How many keys collide?
Choose a random1 hash function, ha,b from H10007,10. Include your random choice of ha,b with your answer to this problem. Before you rehash the numbers with the new hash function, determine the probability that the keys 112 and 2542 collide when hashed with ha,b? Hash each of the keys 112, 2542, 9992, 5502 with ha,b. How many keys collided?
If you had 1000 keys (all keys were positive integers less than 10000) inserted into a hash table of size 2000 using a hash function, ha,b, randomly chosen from H10007,2000 (the family of universal hash functions we defined in class). What is the expected number of collisions you would have if you inserted a new key, x, into the hash table?
2. Using the technique for perfect hashing that we discussed in class, store the set of keys: {10, 22, 37, 40, 52, 60, 70, 72, 75}.
Foryourfirsthashfunction(”outerhash”function)useha,b(k)=((ak+b) modp) modm, where a = 3, b = 42, p = 101, m = 9.
3. What is a bound on the probability that you use at most 16n space for the secondary hash tables? (i.e. Pm−1(nj)2 ≤ 16n.)
i=0
What is a bound on the probability (in terms of k) that you use at most kn space (for some constant k)?
Use the technique we discussed in class.
4. (10 points) How many times must you attempt to construct one of a perfect hash table’s sub-tables so you have one with probability greater than 99.99999%? This is a failure rate of 1 out of one ten million.
∗Many of these questions came from outside sources. 1Use a random number generator.
5. You keep thinking back to the question for homework assignment 1. You are sure you could have solved this faster on average. Here is part of question 10 and the new running time you think you can achieve:
Write the pseudocode for finding all the people aunt Mary should invite, so each person’s name appears only one time in the list. Your algorithm must run in time O(n) average case running time.
Justify that your algorithm runs in O(n) average case time.
State the worst case running time is of your algorithm in big-Oh notation. Justify your
reasoning.
6. News alert!
Great hoards of space rats2 have caused food shortages in the the eastern galaxy. As part of the relief effort, the federation is sending cheese to all the colonies in the eastern galaxy.
The huge battleship INS Engorged Larder has been requisitioned to distribute the food. The cheese has been put into missile like containers, and the battleship will shoot it down to a hungry colony. One cheese “missile” per colony.
Unfortunately the warehouse was attacked by the space rats, who before they were stopped, used a laser to cut the food containers into two pieces; those pieces now lay in a jumbled pile. Using duck tape3, the containers can be put back together. Unfortunately you don’t know which two pieces belong together.
You are given the weight of every broken piece of container in an array w of length n. Your job is to find which two pieces belong together. Two pieces go together if they weigh w.4.
Find an O(n) average case running time algorithm to determine which pieces belong together and save the Chancellors vacation - oops, I mean save the people from starvation! Justify your run time.
7. Unfortunately, the ungrateful colonies didn’t respond well to their new cheese diets5. Piracy is on an all time high. New space recruits have been gathered from all over the galaxy to combat the pirates. The recruits are ranked from 1 to k.
In O(n + k) worst case time, develop an algorithm to sort the n fresh faced recruits based on their ranking where those ranked 1 occur before those ranked 2, etc. Justify your run time.
8. Political unrest has developed again. Some colonies say they are providing more recruits than others. Rumors are flying that The Spiral Colonies provide the most recruits. Others say The Galactic Core provide the most. To settle the rumors before the big academy party, you want to set the story straight.
Given a list of recruits and which colony they came from, find the colonies that provided the most recruits. You should find the list of colonies sorted by which colony provided the most recruits in decreasing order. (i.e If c = 10, you find the colony providing the most recruits listed first, then colony providing the second most recruits listed second, etc. The last item in the list returned is the colony which provided the 10th most recruits.)
2The effects of genetic engineering at the beginning of the 20th century.
3Space vessels and missile are routinely patched up with duct tape to save money. 4This is really large number, much larger than the number of colonies needing food. 5Who knew that piracy could occur from the peace loving Tortuga.
You must find this list quickly or there will be no food at the party since everyone will be arguing instead of preparing. Your algorithm must run in O(n + c log c) average case running time where n is the number of recruits and c is the number of colonies. Justify your running time.
9. Peace has come again to the galaxy! The space pirates have been defeated!6
Celebrations are happening all over the galaxy. The best party will be at the Chancellor’s
house. The Chancellor has invited all star captains to the party. This is a very large list.
To speed things up, the guest list will not be a list of names, instead it will be a hash table containing only zeros and ones. The guest list is created by the following steps. Initially, the hash table T is initialized to 0 for all locations. Then for each person on the guest list their name is hashed7, let i = h(name), and that location in the hash table is set to one, T[i] = 1.
When a guest arrives, their name will be hashed, let i = h(name); if the array T has a one in the ith position, they will be allowed in. If the array’s ith position has a zero, they will be put in prison.
• What is the probability that a person on the guest list was put in prison?
• What is the probability that a person who wasn’t on the guest list was allowed into the
party (i.e. wasn’t put in prison)?
• If instead of a single hash function, what if two hash functions h1,h2 were used. Could you improve the probability that only people on the guest list were invited into the party? The table size T will remain the same.
10. (3 bonus points) Think of a good8 exam question for the material covered in Lecture 3.
6History will note that the victory came just as the federation started to provide crackers as well as cheese to the colonies. I am sure that is just a coincidence.
7For this problem assume the hash function has the simple uniform hashing assumption. 8Only well thought out questions will receive the bonus points.
