Date: Mon, 05 Apr 2004 14:46:03 -0500 (CDT) From: Mark Jacobson To: 810-080-01@uni.edu, 810-080-02@uni.edu Subject: [810-080-01] Assignment due on Wednesday, see web page... The assignment handed out today in class requires you to create two different hash tables and one binary search tree. See the URL: http://www.cns.uni.edu/~jacobson/c080.html if you missed class or if you want to make a size 13 hash table instead of a size 19 hash table. The size 19 hash table turns out to be kind of boring for the given data, as there were no collisions to resolve! I would prefer you do the size 13 instead of size 19. Part Number f(n) = n mod 17 g(n) = n mod 19 h(n) = n mod 13 ----------- --------------- --------------- --------------- PART f(n) g(n) h(n) ---- ---- ---- ---- Feel free to use h(n) = n mod 13 328 5 5 3 207 3 17 12 and ignore g(n) = n mod 19 304 15 0 5 ------ 206 2 16 11 367 10 6 3 400 9 1 10 g(n) had NO COLLISIONS! 465 6 9 10 -------------- 395 4 15 5 246 8 18 12 315 9 11 3 269 14 3 9 ---- ---- ---- ---- PART f(n) g(n) h(n) ---- ---- ---- ---- Draw the size 17 address hash table and fill in the Automobile Part Numbers as they would exist if we resolve collisions with the linear probe method. Calculate both the successful and the unsuccessful search performance average for your table. Do the same for the size 19 table and calculate its performance for the above data as well. Calculate both successful and unsuccessful. Draw the binary search tree for the same data shown above. You do NOT need to calculate the successful search average for your binary search tree! VIP Note: You may do the n mod 13 instead of n mod 19, if you see this on the web page! The n mod 19 turned out to be totally boring, as it was amazingly an injective function! The Excel spreadsheet is linked to from our web page. That URL is: http://www.cns.uni.edu/~jacobson/080/HashingAndBinarySearchTrees.htm linked to from http://www.cns.uni.edu/~jacobson/c080.html See you on Wednesday. Mark