[Recommended]CSCE 3110 Data Structures & Algorithms Summer 2019

CSCE 3110 Data Structures & Algorithms Summer 2019 1 of 12 Project 3 – Hopscotch Hash Table Due: 11:59 PM on Friday, June 21, 2019…

CSCE 3110 Data Structures & Algorithms Summer 2019
1 of 12
Project 3 – Hopscotch Hash Table Due: 11:59 PM on Friday, June 21, 2019
PROGRAM DESCRIPTION In this C++ program, you will implement an efficient hopscotch hash table that improves on the classic linear probing algorithm. Specifically, you will use a TABLE_SIZE = 17 and use the single hash function ℎ(𝑥) = 𝑥 mod 𝑇𝐴𝐵𝐿𝐸_𝑆𝐼𝑍𝐸. You shall resolve collisions using linear probing where the maximal length of the probe sequence (i.e., distance away from the original hash location) is bound by the hopscotch hash algorithm where MAX_DIST = 4.
You shall support the following five operations that are menu driven: 1. Insert Value 2. Delete Value 3. Search Value 4. Output Table 5. Exit Program
All data shall be entered through the console and consist of integers. You may assume valid data, though data may be out of range (i.e., zero, negative integers or possibly out of range of menu options). Your algorithm to find the next available slot is bound by the end of the table so that the linear probe sequence need not be circular. In other words, you do not need to wrap around beyond the last element of the array to the first for either the linear probe or the bound for the hopscotch algorithm. For example, if the user attempts to insert 33 which hashes to index position 16 (i.e., 33 % TABLE_SIZE) in the array, but an element already exists at that location, the insert will fail as there are no more array locations beyond this to attempt to insert the element. You must keep an item array containing the elements as well as an associated hop array that indicates positions in the item array that are occupied with items that hash to the same value. You should also provide specific feedback to the user on successful operations or when an operation failed. The search should utilize the hash value and then perhaps a linear probe of MAX_DIST – 1 index locations, but you should not simply search the entire array to accomplish this operation. Be sure to handle the case that requires multiple hops (i.e., using recursion) to get the value within the correct range. REQUIREMENTS
• Your code should be well documented in terms of comments. For example, good comments in general consist of a header (with your name, course section, date, and brief description), comments for each variable, and commented blocks of code.
• Your program will be graded based largely on whether it works correctly on the CSE machines (e.g., cse01, cse02, …, cse06), so you should make sure that your program compiles and runs on a CSE machine.
aemalki
aemalki
aemalki
aemalki
aemalki
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
2 of 12
• You should contact your instructor if there is any question about what is being asked for.
• This is an individual programming assignment that must be the sole work of the individual student. Any instance of academic dishonesty will result in a grade of “F” for the course, along with a report filed into the Academic Integrity Database.
SAMPLE OUTPUT (input in bold): $ ./a.out HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 5 5 inserted at position 5. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 7 ERROR: Please select operation between 1 and 5, inclusively. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 6 6 inserted at position 6. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 22 22 inserted at position 7. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 23 23 inserted at position 8. HOPSCOTCH HASH MENU: 1 – Insert Value
aemalki
aemalki
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
3 of 12
2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | | 0000 | | 1 | | 0000 | | 2 | | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | 5 | 1010 | | 6 | 6 | 1010 | | 7 | 22 | 0000 | | 8 | 23 | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | | 0000 | | 16 | | 0000 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 39 39 inserted at position 6. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | | 0000 | | 1 | | 0000 | | 2 | | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | 5 | 1110 | | 6 | 39 | 0011 | | 7 | 22 | 0000 | | 8 | 23 | 0000 | | 9 | 6 | 0000 |
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
4 of 12
| 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | | 0000 | | 16 | | 0000 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 56 ERROR: Unable to insert 56 into Hash Table: Hopscotch Hash Failed HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 3 Enter positive integer value to search for in Hopscotch Hash Table: 39 39 found at position 6. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 2 Enter positive integer value to delete from Hopscotch Hash Table: 6 6 deleted from position 9. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | | 0000 | | 1 | | 0000 | | 2 | | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | 5 | 1110 | | 6 | 39 | 0010 | | 7 | 22 | 0000 | | 8 | 23 | 0000 | | 9 | | 0000 | | 10 | | 0000 |
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
5 of 12
| 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | | 0000 | | 16 | | 0000 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 19 19 inserted at position 2. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 50 50 inserted at position 16. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 56 56 inserted at position 8. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | | 0000 | | 1 | | 0000 | | 2 | 19 | 1000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | 5 | 1111 | | 6 | 39 | 0001 | | 7 | 22 | 0000 | | 8 | 56 | 0000 | | 9 | 23 | 0000 | | 10 | | 0000 | | 11 | | 0000 |
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
6 of 12
| 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | | 0000 | | 16 | 50 | 1000 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: -5 Enter positive integer value to insert into Hopscotch Hash Table: 16 ERROR: Unable to insert 16 into Hash Table: Linear Probe Failed HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 5 Program terminated by user… BONUS OPPORTUNITY:
• For those students who have completed all the requirements, you may attempt to add circular functionality to the linear probe (i.e., not just to the end of the table) for up to 15 bonus points.
• SAMPLE OUTPUT for BONUS showing circular table rolling over (input in bold): $ ./a.out HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 16 16 inserted at position 16. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 15 15 inserted at position 15. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
7 of 12
4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 33 33 inserted at position 0. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | | 0000 | | 2 | | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | 15 | 1000 | | 16 | 16 | 1100 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 50 50 inserted at position 1. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | 50 | 0000 | | 2 | | 0000 |
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
8 of 12
| 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | 15 | 1000 | | 16 | 16 | 1110 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 32 32 inserted at position 16. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | 50 | 0000 | | 2 | 16 | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | 15 | 1100 | | 16 | 32 | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
9 of 12
4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 67 ERROR: Unable to insert 67 into Hash Table: Hopscotch Hash Failed HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | 50 | 0000 | | 2 | 16 | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | | 0000 | | 15 | 15 | 1100 | | 16 | 32 | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 14 14 inserted at position 14. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | 50 | 0000 | | 2 | 16 | 0000 |
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
10 of 12
| 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | 14 | 1000 | | 15 | 15 | 1100 | | 16 | 32 | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 31 ERROR: Unable to insert 31 into Hash Table: Hopscotch Hash Failed HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0000 | | 1 | 50 | 0000 | | 2 | 16 | 0000 | | 3 | | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | 14 | 1000 | | 15 | 15 | 1100 | | 16 | 32 | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value
aemalki
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
11 of 12
4 – Output Table 5 – Exit Program Enter operation to perform: 1 Enter positive integer value to insert into Hopscotch Hash Table: 17 17 inserted at position 3. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0001 | | 1 | 50 | 0000 | | 2 | 16 | 0000 | | 3 | 17 | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | 14 | 1000 | | 15 | 15 | 1100 | | 16 | 32 | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 2 Enter positive integer value to delete from Hopscotch Hash Table: 32 32 deleted from position 16. HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 4 HOPSCOTCH HASH TABLE: +——————+ | # | item | hop | +——————+ | 0 | 33 | 0001 | | 1 | 50 | 0000 | | 2 | 16 | 0000 |
aemalki
aemalki
CSCE 3110 Data Structures & Algorithms Summer 2019
12 of 12
| 3 | 17 | 0000 | | 4 | | 0000 | | 5 | | 0000 | | 6 | | 0000 | | 7 | | 0000 | | 8 | | 0000 | | 9 | | 0000 | | 10 | | 0000 | | 11 | | 0000 | | 12 | | 0000 | | 13 | | 0000 | | 14 | 14 | 1000 | | 15 | 15 | 1000 | | 16 | | 0111 | +——————+ HOPSCOTCH HASH MENU: 1 – Insert Value 2 – Delete Value 3 – Search Value 4 – Output Table 5 – Exit Program Enter operation to perform: 5 Program terminated by user…
SUBMISSION:
• You will electronically submit your source code file(s) and a README file where you explain all of the information for the grader to properly grade your program (e.g., how to compile it, how to run it, etc.) to the Project 3 dropbox in Canvas by the due date. Also submit a screen-shot (or use the “script” command) of your program running. Be sure to include your name in each program file and in the README file.
• Note that this program should be done individually. The program will be checked using a code plagiarism tool against other solutions, so please be sure that all work submitted is your own.
aemalki
aemalki
aemalki
aemalki
aemalki

The post CSCE 3110 Data Structures & Algorithms Summer 2019 appeared first on ExpertCustomWritings.
Assignment status: Solved by our experts

>>>Click here to get this paper written at the best price. 100% Custom, 0% plagiarism.<<<

Leave a Reply

Your email address will not be published. Required fields are marked *