CIS 212: Project #3D
Assigned: Thursday November 28th, 2019
Due: you decide ... I will accept it for full credit (not late) through Weds December 11th
Note: No work will be accepted starting 6am Thursday December 12th. (You cannot submit this late for half credit.)
Example 1: you submit it on Dec 1st (before dead week starts): graded with no late
penalty
Example 2: you submit it on Dec 6th (end of dead week) graded with no late penalty
Example 3: you submit it on Dec 11th (Weds of finals week): graded with no late
penalty
Example 4: you submit it on Dec 12th 559am: graded with no late penalty
Example 4: you submit it on Dec 12th 601am: not graded, returned as 0 points
Worth 12% of your grade
Please read this entire prompt!
I have implemented significant starter code.
This code:
- Implements a map based on hash tables
- Reads a CSV file of company information
- Defines a “Company” struct
- Hashes the data from the CSV file into a map
Your job:
1) Implement double hashing. This will involve modifying my code. Do some
research on hashing and find a hash function you like for the second hash.
2) Implement a map based on linked lists. The key for the map should be based
on the company’s symbol name.
3) Do a performance study. Measure the time to store and fetch with both map
types. The workload for fetching should be to fetch every company.
a. Your performance study should use “gettimeofday” (see lecture 13,
slide 21)
4) Write a report. This report should be very short. I will grade these
personally. Just a paragraph will do. Include:
a. One or two sentences on your choice of second hash function.
b. Your findings from your performance study.
What to upload:
1) One file:
a. Your code
b. In a commented section at the bottom of the file: your report. Your
report should be an ASCII text file (no MS-Word). If you use vi, type it
in vi. If you use something else, type it in that.
Note: I should be able to run your code and reproduce your performance study.
This means there should be print statements for each portion you timed. It is
understood that I would not reproduce it exactly … there will be variations in timing
based on hardware.
Grading rubric:
1) Complete linked lists: 5 points
2) Double hashing: 3 points
3) Performance study / report: 4 points
You can submit this homework having completed only some of the above. (Please
indicate which ones you have completed in the comments at the top of proj3D.c.)