Great Deal! Get Instant $25 FREE in Account on First Order + 10% Cashback on Every Order Order Now

ASSIGNMENT INSTRUCTIONS Information: Hashing is a very common technique used in many areas including cryptography. You will be implementing a parallel hash table of integers with chaining mechanism...

1 answer below »
ASSIGNMENT INSTRUCTIONS
Information:
Hashing is a very common technique used in many areas including cryptography.
You will be implementing a parallel hash table of integers with chaining mechanism used as collusion resolution.
A hash table looks like this:
A hash table is a way to combine the advantages of random access (a
ays) retrieval with a better insertion/deletion than a
ays.
In a hash table, the key is being first processed through hashing then the program is attempting to store/find it in an a
ay (the hash table). If the item can be stored, it is done. If it can’t, the situation is called a collusion. There are many collusion resolutions, and we will use chaining, i.e. a linked list of items is used to store the overflow of that particular place.  Note that the elements are not sorted inside the linked list.
When deleting an element from the hashing table, a similar process is followed. The element is first hashed, then the program looks for it in the co
ect hashing cell. If the element is found, the first occu
ence is removed from the list. If it is not found, nothing happens.
The hashing table will contain 13 spots.
The hashing technique will be the following:  number modulo 13
The elements will be read from a file (hashInputDOS.txt or hashInputUnix.txt) and a thread will be created for each element placement in the hash table. Note that this will happen in parallel, i.e. the reading will be continuous, and the thread will be created as soon as the element is read. Your program CANNOT wait until a thread is terminated to start a new thread.
The file will contain the following structure: ( the
are explaining what it is to be done)
1. Blank lines
nothing
2. Comments starting with #
3. ADD number
adds the number to the hash table
4. DELETE number
will delete the first occu
ence of the number in the hash table
5. PRINT number
will print all the content of the hash table at number modulo 13.
 
 
Assignment programming requirements:
· You will *use one or more a
ays, and pointer arithmetic.
· You will *use one or more structure or enums
· Your loops will be well structured, i.e. no infinite loops, no returns inside the loops
· You will not have any
eaks aside from within a switch statement, no gotos, no labels, no continue.
· You will use the right type of loop for the job and you will use it appropriately, i.e. if it is a pretest loop, it is primed. If it is an indefinite loop, you will use an indefinite loop
· You will use descriptive variable names and descriptive function names.
· You will have more than 2 .h files, and more than 2 .c files, and they will have a heade
· You will create complex functions (i.e. they will have pointers parameters, return something…).
· Your program will *use threads and run in parallel
* when I say use, your program will either not compile or not work if I remove the item.
Hints:
Debugging in parallel is very complex. Entire theses have been written on it. In this particular case, you will have a shared resource, which is (part of ) the hashing table.
I highly recommend you work and test as you go.
Here is what my personal approach would be:
1. Writing the hashing function, check it.
2. Write the reading from the file and check that you get what you expect
3. Write the chaining part so that you can store/delete the value in the right spot.
4. Create your threads but have them work one at a time first (so it will be serial)
5. Examine your shared resource. What do you want to protect and when?
6. Parallelize the whole thing, i.e. have no restriction on the creation of threads.
Penalties:
1. Lack of readability (indentation) 5 points
2. Goto,
eaks in loops, continue 5 points.
3. Your loops will be well structured, i.e. no infinite loops, no returns inside the loops. 5 points.
· You will use the right type of loop for the job and you will use it appropriately, i.e. if it is a pretest loop, it is primed. If it is an indefinite loop, you will use an indefinite loop
5. Your functions will be well structured, i.e. one entry, one exit, 5 points.
6. Your functions will have headers stating the purpose of the function and explaining each parameter 2 points.
7. All your files will have headers. 2 points
8. You will use descriptive variable names and descriptive function names. 5 points.
9. You will not use any global variables. 5 points.
10. Dangling pointers 5 points
11. Memory leaks 5 points
12. Unsafe use of pointers, i.e. you don’t check the pointer’s validity before you use it. – 5

# O.Wolf
# 11/4/2019
# Capstone 2019
ADD 13
ADD 27
ADD 41
DELETE 52
ADD 65
PRINT 78
PRINT 92
ADD 110
ADD 15
PRINT 114
DELETE 13
ADD 14
ADD 27
DELETE 27
PRINT 1
Answered Same DayDec 09, 2021

Solution

Ria answered on Dec 15 2021
49 Votes
Hash/Add.c
#include "Hash.h"
#include "Functions.h"
void ADD (int item)
insert item
{
    hash *newnode = malloc(sizeof(hash));
create new node for insertion
    newnode->key = item;
    newnode->next = NULL;
    int h = hash_function (item);
hashing
    if (table[h] == NULL)
no collision; no chaining
    {
        table[h] = newnode;
    }
    else
collision; chaining
    {
        hash* temp = table[h];
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = newnode;
    }
    printf("%d inserted.\n\n",item);
}
Hash/Delete.c
#include "Hash.h"
#include "Functions.h"
int DELETE(int item)
delete item
{
    int h;
    hash *temp, *temp1;
    h = hash_function(item);
hashing
    temp = table[h];
if (temp != NULL)
{
if (temp->key == item)
first item of list
{
temp1 = temp;
temp = temp->next;
table[h] = temp;
free(temp1);
deallocate memory
return 1;
}
else
{
while (temp->next)
not first
{
if (temp->next->key == item)
{
temp1 = temp->next;
temp->next =...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here