Description
Each student begins with four late days that may be used throughout the quarter. You may submit this assignment 24 hours late by using one late day or 48 hours late using two late days. No submissions will be accepted more than 48 hours after the due date without prior approval by the head TA. See the syllabus for more information about our late policies.
All due dates and submission times are expressed in Pacifc time.
You are permitted to work on this assignment in pairs.
Hash tables are one of the most ubiquitous data structures in software engineering, and a lot of efort has been placed into getting them to work quickly and efciently. In this assignment, you’ll explore how efcient those strategies are in practice and will look into their tradeofs.
This assignment has two main pieces:
Linear Probing: You’ll implement the linear probing hashing strategy we discussed in class, getting a feel for how to use hash functions and what open addressing looks like in practice.
Performance Analysis: Having coded up this hash table, you’ll see how fast your code runs on a variety of workfows. From there, you’ll explore the performance numbers, identify the tradeofs between the diferent hash table representations, and make a recommendation of which hashing strategy you think is best.
As usual, we recommend making slow and steady progress on this assignment throughout the week rather than trying to do everything here in one sitting. Here’s our recommended timetable for this assignment:
Aim to complete Enumerations Warmup the day this assignment goes out.
Aim to complete Linear Probing Warmup the day this assignment goes out.
Aim to complete Implementing Linear Probing within fve days.
Aim to complete Performance Analysis component within seven days.
An important note: although the Performance Analysis does not require writing any code, you should make sure to leave appropriate bufer time to complete it. It will require you to think critically about the code you’ve written and to identify tradeofs in the implementations. Historically, we’ve found that students who try doing this part of the assignment the night before it’s due get surprised by how much nuanced analysis is required.
Assignment Logistics
Starter Files
We provide a ZIP of the starter project. Download the zip, extract the fles, and double-click the .pro fle to open the project in Qt Creator.
2023/3/28 22:03 CS106B The Great Stanford Hash-Off
https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1234/assignments/a6/ 10/10
