Final ReviewOutlineA basic problemArray as tableSlide 5Hash functionHash TableDivision MethodCollisionChained Hash TableOpen Address approachSlide 12General format for Many Recursive FunctionsWhen a function is called...A recursive functionRun-Time Stack Activation Records x = Func(5, 2);// original call at instruction 100Slide 17Too much recursion Can Be DangerousSlide 19Recursive Traversal ImplementationSlide 21What’s Binary HeapStructure PropertyBasic Operations of Binary HeapInsertion Sort: CodeExample of shell sortBinary Merge SortQuicksortSlide 29Quicksort ExampleSlide 31Radix SortSlide 33Bucket sortSlide 35Does it Work for Real Numbers?Final ReviewDr. Bernard Chen Ph.D.University of Central ArkansasSpring 2009OutlineHash TableRecursionSortingA basic problemWe have to store some records and perform the following:add new recorddelete recordsearch a record by keyFind a way to do these efficiently!Array as table:0033333:00123450000000::betty:andy::90:81.5:name score0056789david 56.8:9908080:::bill:::49::9999999One ‘stupid’ way is to store the records in a huge array (index 0..9999999). The index is used as the student id, i.e. the record of the student with studid 0012345 is stored at A[12345]One ‘stupid’ way is to store the records in a huge array (index 0..9999999). The index is used as the student id, i.e. the record of the student with studid 0012345 is stored at A[12345]Array as tableStore the records in a huge array where the index corresponds to the keyadd - very fast O(1)delete - very fast O(1)search - very fast O(1)But it wastes a lot of memory! Not feasible.Hash functionfunction Hash(key: KeyType): integer;Imagine that we have such a magic function Hash. It maps the key (studID) of the 1000 records into the integers 0..999, one to one. No two different keys maps to the same number.Imagine that we have such a magic function Hash. It maps the key (studID) of the 1000 records into the integers 0..999, one to one. No two different keys maps to the same number.H(‘0012345’) = 134H(‘0033333’) = 67H(‘0056789’) = 764…H(‘9908080’) = 3Hash Table:betty:bill::90:49:name scoreandy 81.5::david:::56.8::0033333:9908080:0012345::0056789:3670764999134To store a record, we compute Hash(stud_id) for the record and store it at the location Hash(stud_id) of the array. To search for a student, we only need to peek at the location Hash(target stud_id).To store a record, we compute Hash(stud_id) for the record and store it at the location Hash(stud_id) of the array. To search for a student, we only need to peek at the location Hash(target stud_id).Division MethodCertain values of m may not be good:When m = 2p then h(k) is the p lower-order bits of the keyGood values for m are prime numbers which are not close to exact powers of 2. For example, if you want to store 2000 elements then m=701 (m = hash table length) yields a hash function: h(k) = k mod mh(key) = k mod 701CollisionFor most cases, we cannot avoid collisionCollision resolution - how to handle when two different keys map to the same indexH(‘0012345’) = 134H(‘0033333’) = 67H(‘0056789’) = 764…H(‘9903030’) = 3H(‘9908080’) = 3Chained Hash Table24103nilnilnil5nil:HASHMAXKey: 9903030name: tomscore: 73 One way to handle collision is to store the collided records in a linked list. The array now stores pointers to such lists. If no key maps to a certain hash value, that array entry points to nil.One way to handle collision is to store the collided records in a linked list. The array now stores pointers to such lists. If no key maps to a certain hash value, that array entry points to nil.Open Address approachLinear probing: Given auxiliary hash function h, the probe sequence starts at slot h(k) and continues sequentially through the table, wrapping after slot m − 1 to slot 0. Given key k and probe number i (0 ≤ i < m), h(k, i ) = (h(k) + i ) mod m. Quadratic probing: As in linear probing, the probe sequence starts at h(k). Unlike linear probing, it examines cells 1,4,9, and so on, away from the original probe point: h(k, i ) = (h(k) + c1i + c2i 2) mod m (if c1=0, c2=1, it’s the example given by book) Double hashing: Use two auxiliary hash functions, h1 and h2. h1 gives the initial probe, and h2 gives the remaining probes: h(k, i ) = (h1(k) + ih2(k)) mod m.OutlineHash TableRecursionSortingGeneral format forMany Recursive Functions if (some easily-solved condition) // base case solution statement else // general case recursive function callWhen a function is called...a transfer of control occurs from the calling block to the code of the function--it is necessary that there be a return to the correct place in the calling block after the function code is executed; this correct place is called the return address when any function is called, the run-time stack is used--on this stack is placed an activation record for the function callint Func ( /* in */ int a, /* in */ int b ){ int result; if ( b == 0 ) // base case result = 0;else if ( b > 0 ) // first general case result = a + Func ( a , b - 1 ) ) ; // instruction 50return result; } A recursive functionFCTVAL ? result ? b 2 a 5Return Address 100 Run-Time Stack Activation Records x = Func(5, 2);// original call at instruction 100 original call at instruction 100 pushes on this record for Func(5,2)FCTVAL 0 result 0 b 0 a 5Return Address 50 FCTVAL ? result 5+Func(5,0) = ? b 1 a 5Return Address 50 FCTVAL ? result 5+Func(5,1) = ? b 2 a 5Return Address 100record for Func(5,0)is popped first with its FCTVALrecord for Func(5,2)record for Func(5,1) Run-Time Stack Activation Records x = Func(5, 2);// original call at instruction 100Too much recursion Can Be DangerousFibonacci numbers.Long fib (int n){ If (n <=1) return n; Else return fib(n-1) + fib(n-2);}Too much recursion Can Be DangerousRecursive Traversal ImplementationVoid PrintInorder (root) if root != null PrintInorder(root->left); print(root->data); PrintInorder(root->right); endif;Void PrintInorder (root) if root != null
View Full Document