ZuoTi.Pro
Question

Project Description Allow the user to specify M (the size of the hash table) then, (1)...

Project Description
Allow the user to specify M (the size of the hash table) then, (1) add items found in text file "Project1.txt" to h, an initially-empty instance of a HASH (reject all items that have a key that duplicates the key of a previously added item—item keys must be unique); (2) display h (see format shown below); (3) delete 4 randomly-chosen items from the h; and finally, (4) display h. Note M must be a prime number, so your logic must ensure that the value used is the first prime number greater than or equal to the M value specified by the user.
Each item consists of a 3-character, random-content string (the item’s key) and an integer that represents the sequence number of the key in the text file "Project1.txt" (the item’s data).
Display the items contained in h using the following format. Note N is the number of items contained in h.
         111111111122222222223
123456789012345678901234567890
N = XXXXX, M = XXXXX
0: (CCC,XXX)(CCC,XXX)...(CCC,XXX)
1: (CCC,XXX)(CCC,XXX)...(CCC,XXX)
.         .        .
.         .        .
XXX: ***EMPTY*** .         .        .
.         .        .
XXX: (CCC,XXX)(CCC,XXX)...(CCC,XXX)

where XXX: is the hash table index and (CCC ,XXX) is the item key/item data tuple for the item whose item key hashes to XXX.


Sample Program Dialog
M? 12
Loading "Project1.txt"...
(ZZZ, 18) duplicate key. Ignored.
(AAA, 34) duplicate key. Ignored.

Before deletions...
N =    32, M =    13
0: (AAA, 1)(USM, 5)(ZZZ, 7)(MCL, 16)(BIQ, 30)
1: (UPO, 24)(NUQ, 28)(AGM, 31)
2: (CFD, 2)(CCR, 9)
3: (LJG, 6)(KDY, 14)(LNJ, 21)
4: (JMZ, 8)(LXL, 29)
5: (WDQ, 3)(PKN, 12)(INH, 13)
6: (ZSD, 11)(EOL, 22)
7: ***EMPTY***
8: (ADH, 15)
9: ***EMPTY***
10: (XSA, 10)
11: (YVK, 17)(MVH, 19)(XCP, 23)(HKR, 26)(BAV, 27)
12: (OJG, 4)(OLB, 20)(XKW, 25)(DBU, 32)(KCD, 33)

Making   4 deletions...
(ADH, 15) found after   1050 tries. Deleted.
(MVH, 19) found after     11 tries. Deleted.
(WDQ, 3) found after    898 tries. Deleted.
(KDY, 14) found after    439 tries. Deleted.

After   4 deletions...
N =    28, M =    13
0: (AAA, 1)(USM, 5)(ZZZ, 7)(MCL, 16)(BIQ, 30)
1: (UPO, 24)(NUQ, 28)(AGM, 31)
2: (CFD, 2)(CCR, 9)
3: (LJG, 6)(LNJ, 21)
4: (JMZ, 8)(LXL, 29)
5: (PKN, 12)(INH, 13)
6: (ZSD, 11)(EOL, 22)
7: ***EMPTY***
8: ***EMPTY***
9: ***EMPTY***
10: (XSA, 10)
11: (YVK, 17)(XCP, 23)(HKR, 26)(BAV, 27)
12: (OJG, 4)(OLB, 20)(XKW, 25)(DBU, 32)(KCD, 33)

import sys,os,math,random

# Student provides import statement to import HASH class from Project1Module.py

#-------------------------------------------------------------
def HashF_str(key,M) :
#-------------------------------------------------------------
   r = 0
   for c in key : r = r*256 + ord(c)
   return( r%M )

#-------------------------------------------------------------
# main
#-------------------------------------------------------------
M = int(input("M? "))

print("\nLoading \"Project1.txt\"...")

IN = open("Project1.txt",'r')
h = HASH(M,HashF_str)
itemdata = 0
for itemkey in IN :
   key = key.rstrip('\n')
   itemdata += 1
   if ( itemkey in h ) :
      print("({},{:3d}) duplicate key. Ignored.".format(itemkey,itemdata))
   else :
      if   ( itemdata%4 == 0 ) : h.Add(itemkey,itemdata)
      elif ( itemdata%4 == 1 ) : h = h + (itemkey,itemdata)
      elif ( itemdata%4 == 2 ) : h = (itemkey,itemdata) + h
      else :                     h += (itemkey,itemdata)
IN.close()

try :
   assert ( h.M < len(h) )
except AssertionError :
   print("\nYour choice of M is too big! Try again")

print("\nBefore deletions...")
print(str(h))

DELETIONS = 4

print("Making {:3d} deletions...".format(DELETIONS))
random.seed()
for i in range (0,DELETIONS) :
   deleted = False
   count = 0
   while ( not deleted ) :
      itemkey = ""
      for i in range(1,3+1) :
         itemkey += chr(random.randint(0,25)+ord('A'))
      count += 1
      try :
         print("({},{:3d}) found after {:6d} tries. Deleted.".format(itemkey,h[itemkey],count))
         if   ( h[itemkey]%4 == 0 ) : h.Sub(itemkey)
         elif ( h[itemkey]%4 == 1 ) : h = h - itemkey
         elif ( h[itemkey]%4 == 2 ) : h = itemkey - h
         else :                       h -= itemkey
         deleted = True
      except KeyError :
         pass

print("\nAfter {:3d} deletions...".format(DELETIONS))
print(str(h))

del h

sys.exit( 0 )

import sys,os,math

#-------------------------------------------------------------
class HASH :
#-------------------------------------------------------------

   """HASH table implementation by Dr. Hanna"""

#-------------------------------------------------------------
# HASH uses a "dictionary" of (key,value) pairs to implement a hash table
#    containing items represented as "tuples" = (itemkey,itemdata)
#    * dictionary key is an integer in [ 0,M-1 ]
#    * dictionary value is a "list" of "tuples" (itemkey,itemdata)
#-------------------------------------------------------------

   def __init__(self,M,HashF) :

# Student provides missing code

   def __del__(self) :

# Student provides missing code

   def __str__(self) :

# Student provides missing code
  
   def Add(self,itemkey,itemdata) :

# Student provides missing code

   def __add__(self,item) :

# Student provides missing code

   def __radd__(self,item) :

# Student provides missing code

   def __iadd__(self,item) :

# Student provides missing code

   def Sub(self,itemkey) :
      hindex = self.HashF(itemkey,self.M)
      i = 0
      for i in range(0,len(self.table[hindex])) :
         item = self.table[hindex][i]
         if ( itemkey == item[0] ) :
            self.table[hindex].remove(item)
            self.N -= 1
            return
      else :
         raise( KeyError )

   def __sub__(self,itemkey) :

# Student provides missing code

   def __rsub__(self,itemkey) :

# Student provides missing code

   def __isub__(self,itemkey) :

# Student provides missing code

   def __contains__(self,itemkey) :

# Student provides missing code

   def __len__(self) :

# Student provides missing code

   def __getitem__(self,itemkey) :
      hindex = self.HashF(itemkey,self.M)
      for item in self.table[hindex] :
         if ( itemkey == item[0] ) : return( item[1] )
      raise( KeyError )

   def __IsPrime__(self,x) :
      r = True
      for d in range(2,int(math.sqrt(x)+1)) : r = r and (x%d != 0)
      return( r )

   def __NextPrime__(self,x) :
      while ( not self.__IsPrime__(x) ) : x += 1
      return( x )

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Working code implemented in Python and comments for better understanding:

Here I am attaching code for 3 files and 1 input file:

  1. Project1Module.py
  2. hashtable.py
  3. Two_Partner.py
  4. hash_key.txt

Code for Project1Module.py:

import sys,os,math,random,pdb

from hashtable import HASH

def HashF_str(key,M) :
r = 0
for c in key : r = r*256 + ord(c)
return( r%M )
M = int(input("M? "))
print("\nLoading \"Project1.txt\"...")

IN = open("hash_key.txt",'r')
h = HASH(M,HashF_str)
itemdata = 0
for itemkey in IN :
key = itemkey.rstrip('\n')
itemdata += 1
if ( key in h ):
print("({},{:3d}) duplicate key. Ignored.".format(key,itemdata))
else :
if ( itemdata%4 == 0 ) : h.Add(key,itemdata)
elif ( itemdata%4 == 1 ) : h = h + (key,itemdata)
elif ( itemdata%4 == 2 ) : h = (key,itemdata) + h
else : h += (key,itemdata)
IN.close()
try :
assert ( h.M <= len(h) )
except AssertionError :
print("\nYour choice of M is too big! Try again")
print("\nBefore deletions...")
print ('N = \t%d, M = \t%d'%(h.N,h.M))
print(str(h))
DELETIONS = 4

print("Making {:3d} deletions...".format(DELETIONS))
random.seed()
for i in range (0,DELETIONS) :
deleted = False
count = 0
while ( not deleted ) :
itemkey = ""
for i in range(1,3+1) :
itemkey += chr(random.randint(0,25)+ord('A'))
count += 1
try :
print("({},{:3d}) found after {:6d} tries. Deleted.".format(itemkey,h[itemkey],count))
if ( h[itemkey]%4 == 0 ) : h.Sub(itemkey)
elif ( h[itemkey]%4 == 1 ) : h = h - itemkey
elif ( h[itemkey]%4 == 2 ) : h = itemkey - h
else : h.Sub(itemkey)
deleted = True
except KeyError :
pass

print("\nAfter {:3d} deletions...".format(DELETIONS))
print ('N = \t%d, M = \t%d'%(h.N,h.M))
print(str(h))

del h
sys.exit( 0 )

Code Screenshots:

1 3 5 6 11 12 13 14 15 import sys,os,math, random,pdb from hashtable import HASH def HashF_str(key,M) : r = 0 for c in key :

Code for hashtable.py:

import sys, os, math
class HASH:
def __init__(self, M, HashF):
if HASH.__IsPrime__(self,M):
self.M= M
else:
self.M = HASH.__NextPrime__(self, M)
self.HashF=HashF
self.N=0
self.table = {}
for num in range(self.M):
self.table.update({num:[]})
def __del__(self):
item = self.__len__()
del self.table[item-1]
def __str__(self):
str2ret = ""
for elem in self.table.keys():
str2ret = str2ret + str(elem)+':\t'
if self.table[elem]:
for item in self.table[elem]:
str2ret = str2ret + '({}, {})'.format(item[0],item[1])+" "
else:
str2ret = str2ret + '***EMPTY***'
str2ret = str2ret + "\n"
return str2ret

def Add(self, itemkey, itemdata):
hindex = self.HashF(itemkey, self.M)
self.table[hindex].append((itemkey,itemdata))
self.N += 1

def __add__(self, item):
hindex = self.HashF(item[0], self.M)
self.table[hindex].append((item[0], item[1]))
self.N += 1
return self

def __radd__(self, item):
hindex = self.HashF(item[0], self.M)
self.table[hindex].append((item[0], item[1]))
self.N += 1
return self

def __iadd__(self, item):
hindex = self.HashF(item[0], self.M)
self.table[hindex].append((item[0], item[1]))
self.N += 1
return self

def Sub(self, itemkey):
hindex = self.HashF(itemkey, self.M)
i = 0
for i in range(0, len(self.table[hindex])):
item = self.table[hindex][i]
if (itemkey == item[0]):
self.table[hindex].remove(item)
self.N -= 1
return
else:
raise (KeyError)

def __sub__(self, itemkey):
hindex = self.HashF(itemkey, self.M)
i = 0
for i in range(0, len(self.table[hindex])):
item = self.table[hindex][i]
if (itemkey == item[0]):
self.table[hindex].remove(item)
self.N -= 1
return self
else:
raise (KeyError)

def __rsub__(self, itemkey):
hindex = self.HashF(itemkey, self.M)
i = 0
for i in range(0, len(self.table[hindex])):
item = self.table[hindex][i]
if (itemkey == item[0]):
self.table[hindex].remove(item)
self.N -= 1
return self
else:
raise (KeyError)

def __isub__(self, itemkey):
hindex = self.HashF(itemkey, self.M)
i = 0
for i in range(0, len(self.table[hindex])):
item = self.table[hindex][i]
if (itemkey == item[0]):
self.table[hindex].remove(item)
self.N -= 1
return self
else:
raise (KeyError)

def __contains__(self, itemkey):
hindex = self.HashF(itemkey, self.M)
ret2con = False
for i in range(0, len(self.table[hindex])):
item = self.table[hindex][i]
if (itemkey == item[0]):
ret2con = True
return ret2con
def __len__(self):
return len(self.table)
def __getitem__(self, itemkey):
hindex = self.HashF(itemkey, self.M)
for item in self.table[hindex]:
if (itemkey == item[0]): return (item[1])
raise (KeyError)
def __IsPrime__(self, x):
r = True
for d in range(2, int(math.sqrt(x) + 1)): r = r and (x % d != 0)
return (r)
def __NextPrime__(self, x):
while (not self.__IsPrime__(x)): x += 1
return (x)

Code Screenshots:

1 2 import sys, os, math class HASH: def __init__(self, M, HashF): if HASH._IsPrime_(self,M): self.M= M else: self.M = HASH.raise (KeyError) def __sub_(self, itemkey): hindex = self.HashF(itemkey, self.M) i = 0 for i in range(@, len(self.table[hinde

Code for Two_Partner.py:

import itertools,time

time_start = time.clock()
sol_count = 0
path_count = 0
for num in itertools.permutations([0,1,2,3,4,5,6,7,8,9]):
path_count +=1
x= 1000*num[0] + 100*5 + 10*num[1]+ num[2]
y=1000*num[3] + 100*num[4] + 10*num[5]+ 5
z = 10000*num[6]+1000*num[7] + 100*6 + 10*num[8]+num[9]
if x+y==z:
sol_count += 1
print("%2d: %4d + %4d = %5d"%(sol_count, x, y, z))
time_elapsed = (time.clock() - time_start)
print ("Game tree contain {} paths,{} solutions\n".format(path_count,sol_count))
print ("Run took {} seconds\n".format(time_elapsed))

time_start = time.clock()
sol_count = 0
path_count = 0
for num in itertools.product([1,2,3,7,8,9],repeat=10):
path_count +=1
x = 1000*num[0] + 100*5 + 10*num[1] + num[2]
y = 1000*num[3] + 100*num[4] + 10*num[5] + 5
z = 10000*num[6] + 1000*num[7] + 100*6 + 10*num[8] + num[9]
if x+y==z:
sol_count += 1
time_elapsed = (time.clock() - time_start)
print ("Game tree contain {} paths,{} solutions\n".format(path_count,sol_count))
print ("Run took {} seconds\n".format(time_elapsed))

Code Screenshots:

import itertools, time time_start = time.clock() sol_count = 0 path_count = 0 for num in itertools.permutations([0,1,2,3,4,5,

Input File hash_key.txt:

AAA
CFD
WDQ
OJG
USM
LJG
ZZZ
JMZ
CCR
XSA
ZSD
PKN
INH
KDY
ADH
MCL
YVK
ZZZ
MVH
OLB
LNJ
EOL
XCP
UPO
XKW
HKR
BAV
NUQ
LXL
BIQ
AGM
DBU
KCD
AAA

hash_key.txt Screenshots:

hash_key.txt - Notepad File Edit Format View Help ААА CFD WDQ OJG USM LJG ZZZ JMZ CCR XSA ZSD PKN INH KDY ADH MCL YVK ZZZ MVH

Output Screenshots:

- C:\Windows\System32\cmd.exe Microsoft Windows [Version 10.0.18362.535] (c) 2019 Microsoft Corporation. All rights reserved.

Hope it helps, if you like the answer give it thumbs up. Thank you.

0 0
Add a comment
Know the answer?
Add Answer to:
Project Description Allow the user to specify M (the size of the hash table) then, (1)...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • 5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and...

    5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...

  • Hey I have a task which consists of two part. Part A asks for writing a...

    Hey I have a task which consists of two part. Part A asks for writing a program of WORD & LINE CONCORDANCE APPLICATION in python which I have completed it. Now the second part has given 5 dictionary implementation codes namely as: (ChainingDict, OpenAddrHashDict with linear probing, OpenAddrHashDict with quadratic probing, and 2 tree-based dictionaries from lab 12 (BST-based dictionary implementation) and asks for my above program WORD & LINE CONCORDANCE APPLICATION  to use these implemented code and show the time...

  • I am having trouble with my Python code in this dictionary and pickle program. Here is...

    I am having trouble with my Python code in this dictionary and pickle program. Here is my code but it is not running as i am receiving synthax error on the second line. class Student: def__init__(self,id,name,midterm,final): self.id=id self.name=name self.midterm=midterm self.final=final def calculate_grade(self): self.avg=(self.midterm+self.final)/2 if self.avg>=60 and self.avg<=80: self.g='A' elif self.avg>80 and self.avg<=100: self.g='A+' elif self.avg<60 and self.avg>=40: self.g='B' else: self.g='C' def getdata(self): return self.id,self.name.self.midterm,self.final,self.g CIT101 = {} CIT101["123"] = Student("123", "smith, john", 78, 86) CIT101["124"] = Student("124", "tom, alter", 50,...

  • I am currently facing a problem with my python program which i have pasted below where i have to design and implement python classes and record zoo database and takes user input as query. the error i...

    I am currently facing a problem with my python program which i have pasted below where i have to design and implement python classes and record zoo database and takes user input as query. the error i am recieving says that in line 61 list index is out of range. kindly someone help me with it as soon as possible. Below is the program kindly check and correct it. Thanks! class Animal: def __init__(self, name, types, species, mass): self.name=name self.type=types...

  • Type up and get the Hash table on pages 19 - 22 to work. Show your...

    Type up and get the Hash table on pages 19 - 22 to work. Show your sample test run at the bottom of your code using a multiline comment I typed everything but the code is not working please help me fix the mistakes. These are pages 19-22. The code I have: #include <iostream> #inlcude <iomanip> #include <stack> #include <vector> #include <cstdlib> #include <ctime> using namespace std; //////////////////////////////HASH TABLE/////////////////////////////////////////////// //hash.cpp //demonstrate hash table with linear probing /////////////////////////////////////////////////////////////////////////////////////// class DataItem {...

  • In this part, you will complete the code to solve a maze.

    - Complete the code to solve a maze- Discuss related data structures topicsProgramming-----------In this part, you will complete the code to solve a maze.Begin with the "solveMaze.py" starter file.This file contains comment instructions that tell you where to add your code.Each maze resides in a text file (with a .txt extension).The following symbols are used in the mazes:BARRIER = '-' # barrierFINISH = 'F' # finish (goal)OPEN = 'O' # open stepSTART = 'S' # start stepVISITED = '#' #...

  • I have a python project that requires me to make a password saver. The major part...

    I have a python project that requires me to make a password saver. The major part of the code is already giving. I am having trouble executing option 2 and 3. Some guidance will be appreciated. Below is the code giving to me. import csv import sys #The password list - We start with it populated for testing purposes passwords = [["yahoo","XqffoZeo"],["google","CoIushujSetu"]] #The password file name to store the passwords to passwordFileName = "samplePasswordFile" #The encryption key for the caesar...

  • Zybooks 11.12 LAB*: Program: Online shopping cart (continued) Python 3 is the code needed and this...

    Zybooks 11.12 LAB*: Program: Online shopping cart (continued) Python 3 is the code needed and this is in Zybooks Existing Code # Type code for classes here class ItemToPurchase: def __init__(self, item_name="none", item_price=0, item_quantity=0): self.item_name = item_name self.item_price = item_price self.item_quantity = item_quantity # def __mul__(self): # print_item_cost = (self.item_quantity * self.item_price) # return '{} {} @ ${} = ${}' .format(self_item_name, self.item_quantity, self.item_price, print_item_cost) def print_item_cost(self): self.print_cost = (self.item_quantity * self.item_price) print(('{} {} @ ${} = ${}') .format(self.item_name, self.item_quantity, self.item_price,...

  • C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can...

    C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can be used to implement a Set ADT. Let's try to use the template below to implement a Set with double hashing. Here we assume the Set contains names with 3 characters long. Since it is a Set, we do not need to have an explicit value for each key. We will use a token value of 1 if a name belongs to the Set....

  • YOU NEED TO MODIFY THE PROJECT INCLUDED AT THE END AND USE THE INCLUDED DRIVER TO...

    YOU NEED TO MODIFY THE PROJECT INCLUDED AT THE END AND USE THE INCLUDED DRIVER TO TEST YOUR CODE TO MAKE SURE IT WORK AS EXPECTED. Thanks USING PYTHON, complete the template below such that you will provide code to solve the following problem: Please write and/or extend the project5 attached at the end. You will have to do the following for this assignment: Create and complete the methods of the PriceException class. Create the processFile function. Modify the main...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT