Hashing, B - Trees and Red – Black Trees using Parallel Algorithms & Sequential AlgorithmsRoad mapIntroductionHashingDefinitionsSymbol – table problemHash functionsChoosing a hash functionDivision methodDivision method (continued)Multiplication methodMultiplication method exampleResolving collisions by chainingAnalysis of chainingSearch costResolving collisions by open addressingExample of open addressingSlide 18Slide 19Slide 20Probing strategiesRed-Black TreesRoadmapRed-Black TreeHeight of a Red-Black TreeInsertionRemedying a Double RedSlide 28RestructuringRestructuring (cont.)RecoloringAnalysis of InsertionDeletionRemedying a Double BlackRed-Black Tree ReorganizationBinary TreesSlide 37Example: Expression TreesSlide 39Compare: Implementation of a general treeBinary Search TreesSlide 42Binary search treesImplementationSearching BSTSlide 46Searching (Find)Inorder traversal of BSTFindMin/ FindMaxInsertDeleteSlide 52Slide 53Sequential algorithmsSlide 55Sequential algorithmsBest-First Search (BFS) AlgorithmsSlide 58Best-First Search: ExampleSearch Overhead FactorParallel algorithmsSlide 62Slide 63Parallel Best-First SearchSlide 65Slide 66Slide 67Slide 68Slide 69Parallel Best-First Graph SearchSpeedup Anomalies in Parallel SearchSlide 72Speedup Anomalies in Parallel SearchTo here, The Presentation endsWhat are the two methods of Resolving collusions in addressing hashing functions mentioned in the presentation? In Parallel systems, when a processor runs out of work, it gets more work from another processor (How?).Hashing, B - Trees and Red – Black Trees using Parallel Algorithms & Sequential AlgorithmsBy Yazeed K. Almarshoud2January 14, 2019Road map Introduction.Definitions.Hashing.B TreesRed Black Trees.Sequential algorithmsParallel algorithms3January 14, 2019IntroductionIn this presentation I ‘m glad to present to you the importance of parallel computations and how it is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones which are then solved concurrentlyHashing5January 14, 2019DefinitionsHashing: A hash function is any well – defined procedure or mathematical function which converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index into an array. i.e. keys made up for alphabetical characters could be replaced by their ASCII equivalents.Two standards hashing techniques:Division methodsMultiplication method.6January 14, 2019Symbol – table problem7January 14, 2019Hash functions8January 14, 2019Choosing a hash functionThe assumption of simple uniform hashing is hard to guarantee, but several common techniques tend to work well in practice as long as their deficiencies can be avoided.Desirata: A good hash function should distribute thekeys uniformly into the slots of the table.Regularity in the key distribution shouldnot affect this uniformity.9January 14, 2019Division methodAssume all keys are integers, and defineh(k) = k mod m.Deficiency: Don’t pick an m that has a small divisor d. A preponderance of keys that are congruent modulo d can adversely affect uniformity.Extreme deficiency: If m = 2r, then the hashdoesn’t even depend on all the bits of k: If k = 10110001110110102 and r = 6, thenh(k) = 0110102 .10January 14, 2019Division method (continued)h(k) = k mod m.Pick m to be a prime not too close to a powerof 2 or 10 and not otherwise used prominentlyin the computing environment.Annoyance: Sometimes, making the table size a prime isinconvenient.But, this method is popular, although the nextmethod we’ll see is usually superior.11January 14, 2019Multiplication methodAssume that all keys are integers, m = 2r, and ourcomputer has w-bit words. Define h(k) = (A·k mod 2w) rsh (w – r),where rsh is the “bit-wise right-shift” operatorand A is an odd integer in the range 2w–1 < A < 2w.Don’t pick A too close to 2w.Multiplication modulo 2w is fast.The rsh operator is fast.12January 14, 2019Multiplication methodexample13January 14, 2019Resolving collisions bychaining14January 14, 2019Analysis of chaining15January 14, 2019Search cost16January 14, 2019Resolving collisions by open addressingNo storage is used outside of the hash table itself..The hash function depends on both the key and probe number:h : U X {0, 1, …, m–1}  {0, 1, …, m–1}.E.g. h(k) = (k+i) mod m ; h(k) = (k+i2 ) mod mInserting a key k:we check T[h(k,0)]. If empty we insert k, there. Otherwise,we check T[h(k,1)]. If empty we insert k, there. Otherwise,…otherwise etc for h(k,2), h(k,1), …, h(k,m–1).Finding a key k:we check if T[h(k,0)] is empty, and if =k. If notwe check if T[h(k,1)] is empty, and if =k. If nototherwise etc for h(k,2), h(k,1), …, h(k,m–1).Deleting a key kFind it are replace with a dummy (why)17January 14, 2019Example of open addressing18January 14, 2019Example of open addressing19January 14, 2019Example of open addressing20January 14, 2019Example of open addressing21January 14, 2019Probing strategiesLinear probing:Given an ordinary hash function h ‘(k), linearprobing uses the hash functionh(k,i) = (h’(k) + i) mod m.This method, though simple, suffers from primaryclustering, where long runs of occupied slots buildup, increasing the average search time. Moreover,the long runs of occupied slots tend to get longer.Red-Black Trees6384vz23January 14, 2019RoadmapDefinitionHeightInsertionrestructuringrecoloringDeletionrestructuringrecoloringadjustment24January 14, 2019Red-Black TreeA red-black tree can also be defined as a binary search tree that satisfies the following properties:Root Property: the root is blackExternal Property: every leaf is blackInternal Property: the children of a red node are blackDepth Property: all the leaves have the same black depth915462 1272125January 14, 2019Height of a Red-Black TreeTheorem: A red-black tree storing n items has height O(log n)The search algorithm for a red-black search tree is the same as that for a binary search treeBy the above theorem, searching in a red-black tree takes O(log n) time26January 14, 2019InsertionTo perform operation insertItem(k, o), we execute the insertion algorithm for binary search trees and color red the newly inserted node z unless it is the