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. ---------------------------------------------------------------------- Date: Mon, 26 Nov 2001 23:03:19 -0600 (CST) From: Mark Jacobson To: 810-080-01@uni.edu, 810-080-02@uni.edu Subject: hash table review exercise... The hash function is h(x) = x mod 17 The codomain of the function h is: {0, 1, 2, 3, ..., 15, 16} The data to be stored in the hash table is: 23, then 14, then 52, then 40, then 24, then 18, followed by 33, 58 and finally 50 gets stored. The collision resolution method is linear probe, as shown in class. Treat the hash table as a circular array, with location 16 being followed by location 0. 1. Draw the hash table with the stored data items. 2. Calculate the average successful search performance value. 3. Calculate the average unsuccessful search number of probes. 4. Describe the search for item 58 and how it proceeds, probe by probe. 5. What is the cardinality of the range of the function h? Do this exercise before Wednesday's class. If you want to read more about hash tables, see pages 649-650 of the textbook, Example 14.14 material only one those two pages. Also see http://www.cns.uni.edu/~jacobson/hashingOct2000.txt which is easily linked from http://www.cns.uni.edu/~jacobson and http://www.cns.uni.edu/~jacobson/c080.html The http://www.cns.uni.edu/~jacobson/hashingOct2000.txt material is also good review and preview for the Friday Nov 30th hands-on class.