Unformatted text preview:

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 2009OutlineHash TableRecursionSortingA basic problemWe have to store some records and perform the following:add new recorddelete recordsearch a record by keyFind 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 tableStore the records in a huge array where the index corresponds to the keyadd - 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 MethodCertain values of m may not be good:When m = 2p then h(k) is the p lower-order bits of the keyGood 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 701CollisionFor most cases, we cannot avoid collisionCollision 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 approachLinear 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.OutlineHash TableRecursionSortingGeneral 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

GSU CSC 2320 - CSCI2320 Final Review

Download CSCI2320 Final Review
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 Final Review and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Final Review 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?