Script started on Wed Oct 25 11:26:28 2000 bash$ cat S <--- CONcatENATE set S (file S) --- 223456 % 17 S contains a set of legal 345123 % 17 bc calculator expressions 456123 % 17 so we can find out f(x) 222555 % 17 value for each ID number, where 111444 % 17 333777 % 17 f(x) = x mod 17 125000 % 17 424242 % 17 f(223456) = 8 and f(125000) = 16 242426 % 17 bash$ bc < S **** < is the input redirection operator 8 **** > would be used for output redirection 6 **** | would be used for piping the output 13 of one command to become the input 8 for another command. 9 16 16 7 **** When you understand < and > and | operators 6 for DOS and UNIX, you will understand domains, codomains, ranges, and composition bash$ bc of functions from section 4.4 readings. 2*17 34 123 / 20 / What is quotient when divisor = 20 6 and dividend = 123 ? 123 % 20 % What is the remainder when dividend is 123 3 and divisor is 20 ? 123 % 50 23 123 / 50 2 ^D *** Use control-d to exit bc calculator bash$ exit script done on Wed Oct 25 11:28:57 2000 -------------------------------------------------------------------------- EXERCISE: Do the following for the data shown above. See page 307, #43 in textbook and lecture notes to supplement this exercise. Review terms load factor, synonyms, collision, linear probe method of collision resolution, and home address as you do the exercise. Can you define all of the terms? Can you compare the successful and unsuccessful search results for a regular, non-hash table array list of the data? -------------------------------------------------------------------------- The hashing function is ( UNI-ID-Number MOD 17 ) The 6 digit ID numbers shown ABOVE on left hand side of the % operator might be UNI student ID numbers. 333777 % 17 f(x) = x mod 17 125000 % 17 424242 % 17 f(223456) = 8 and f(125000) = 16 1. Calculate the successful search average performance for the table. 2. Calculate the unsuccessful average search performance for the table. --------------------------------------------------------------------------- --------------------------------------------------------------------------- ***** FALL 1999 hash table exercise and COBOL program output ***** Script started on Mon Nov 01 10:04:03 1999 <33 chaos:~/cobol > runcbl semihash.run Storing 625066 at 01 Storing 367525 at 09 Storing 462019 at 21 Storing 538510 at 10 Storing 428822 at 29 Storing 594119 at 26 Storing 328669 at 13 Storing 296287 at 24 *** Checking for open address at 10 *** Checking for open address at 11 Stored 192597 at 11 instead of 09 Storing 201506 at 15 Storing 295389 at 25 *** Checking for open address at 10 *** Checking for open address at 11 *** Checking for open address at 12 Stored 009375 at 12 instead of 09 *** Checking for open address at 12 *** Checking for open address at 13 *** Checking for open address at 14 Stored 347401 at 14 instead of 11 Storing 790735 at 22 Storing 863157 at 02 *** Checking for open address at 02 *** Checking for open address at 03 Stored 837926 at 03 instead of 01 Storing 761269 at 20 Storing 909375 at 23 *** Checking for open address at 25 *** Checking for open address at 26 *** Checking for open address at 27 Stored 147401 at 27 instead of 24 *** Checking for open address at 10 *** Checking for open address at 11 *** Checking for open address at 12 *** Checking for open address at 13 *** Checking for open address at 14 *** Checking for open address at 15 *** Checking for open address at 16 Stored 990735 at 16 instead of 09 <34 chaos:~/cobol >^D script done on Mon Nov 01 10:04:54 1999 The hashing function is ((ID MOD 29) + 1) The 6 digit ID numbers might be UNI ID numbers. 1. Calculate the successful search average performance for the table. 2. Calculate the unsuccessful average search performance for the table.