logging in or signing up e computer notes - Data Structures - 37 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 21 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.37 Data Structures http://ecomputernotes.comRecap: Recap Collision Strategies in Hashing Linear Probing Quadratic Probing Linked List chaining http://ecomputernotes.comHashing Animation: Hashing Animation Let’s see the hashing animation. We will see linear probing, quadratic probing and link list chaining in it. This is an example of how do we solve collision. We have an array shown in four different columns. The size of the array is 100 and the index is from 0 to 99. Each element of the array has two locations so we can store 200 elements in it. When we have first collision the program will use the 2nd part of the array location. When there is a 2nd collision the data is stored using the linear probing. At the top right corner we have hash function x and its definition is “mod 100”. That is when a number is passed to it, it will take mod with 100 and return the result which is used as index of the array. In this example we are using numbers only and not dealing with the characters. We also have a statistical table on the right side. This program will generate 100 random numbers and using the hash function it will store these in the array. The numbers will be stored in the array at different locations. In the bottom left we have hashing algorithms. We have chosen the linear probing. Now the program will try to solve this problem using the linear probing. Press the run button to start it. It is selecting the numbers randomly, dividing it by 100 and the remainder is the hash value which is used as array index. Here we have number 506. It is divided by 100 and the remainder is 6. It means that this number will be stored at the sixth array location. Similarly we have a number 206, now its remainder is also 6. As location 6 is already occupied so we will store 206 at the 2nd part of the location 6. Now we have the number 806. Its remainder is also 6. As both the parts of location 6 are occupied. Using the linear probing we will store it in the next array location i.e. 7. If we have another number having the remainder as 6, we will store it at the 2nd part of location 7. If we have number 807, its remainder is 7. The location 7 is already occupied due to the linear probing. Therefore the number 807 will be stored using the linear probing in the location 8. http://ecomputernotes.comHashing Animation: Hashing Animation Let’s change the collision resolution algorithm to quadratic probing. Run the animation again. Now we have array size as 75 and the array is shown in three columns. Each location of the array can store two numbers. In quadratic probing we add square of one first i.e. 1 and then the square of two and so on in case of collisions. Here we have used a different hash function. We will take the mod with 75. When the both parts of the array location is filled we will use the quadratic probing to store the next numbers. Analyze the numbers and see where the collisions have happened. Lets see the animation using the linked list chaining. Now the hash function uses 50 to take mod with the numbers. So far pointers are not shown. When both parts of the location are filled, we will see the link list appearing. We have four numbers having remainder 0. The two numbers will be stored in the array and the next two will be stored using the link list which is attached at the 0 location. We are not covering the hashing topic in much depth here as it is done in algorithms and analysis of algorithms domain. This domain is not part of this course. For the time being, we will see the usage of hashing. For certain situations, table ADT can be used, which internally would be using hashing. http://ecomputernotes.comApplications of Hashing: Applications of Hashing Compilers use hash tables to keep track of declared variables (symbol table). A hash table can be used for on-line spelling checkers — if misspelling detection (rather than correction) is important, an entire dictionary can be hashed and words checked in constant time. http://ecomputernotes.comApplications of Hashing: Applications of Hashing Game playing programs use hash tables to store seen positions, thereby saving computation time if the position is encountered again. Hash functions can be used to quickly check for inequality — if two elements hash to different values they must be different. http://ecomputernotes.comWhen is hashing suitable?: When is hashing suitable? Hash tables are very good if there is a need for many searches in a reasonably stable table. Hash tables are not so good if there are many insertions and deletions, or if table traversals are needed — in this case, AVL trees are better. Also, hashing is very slow for any operations which require the entries to be sorted e.g. Find the minimum key http://ecomputernotes.comSorting Integers: Sorting Integers 20 8 5 10 7 5 7 8 10 20 How to sort the integers in this array? http://ecomputernotes.comElementary Sorting Algorithms: Elementary Sorting Algorithms Selection Sort Insertion Sort Bubble Sort http://ecomputernotes.comSelection Sort : Selection Sort Main idea: find the smallest element put it in the first position find the next smallest element put it in the second position … And so on, until you get to the end of the list http://ecomputernotes.com You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
e computer notes - Data Structures - 37 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 21 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.37 Data Structures http://ecomputernotes.comRecap: Recap Collision Strategies in Hashing Linear Probing Quadratic Probing Linked List chaining http://ecomputernotes.comHashing Animation: Hashing Animation Let’s see the hashing animation. We will see linear probing, quadratic probing and link list chaining in it. This is an example of how do we solve collision. We have an array shown in four different columns. The size of the array is 100 and the index is from 0 to 99. Each element of the array has two locations so we can store 200 elements in it. When we have first collision the program will use the 2nd part of the array location. When there is a 2nd collision the data is stored using the linear probing. At the top right corner we have hash function x and its definition is “mod 100”. That is when a number is passed to it, it will take mod with 100 and return the result which is used as index of the array. In this example we are using numbers only and not dealing with the characters. We also have a statistical table on the right side. This program will generate 100 random numbers and using the hash function it will store these in the array. The numbers will be stored in the array at different locations. In the bottom left we have hashing algorithms. We have chosen the linear probing. Now the program will try to solve this problem using the linear probing. Press the run button to start it. It is selecting the numbers randomly, dividing it by 100 and the remainder is the hash value which is used as array index. Here we have number 506. It is divided by 100 and the remainder is 6. It means that this number will be stored at the sixth array location. Similarly we have a number 206, now its remainder is also 6. As location 6 is already occupied so we will store 206 at the 2nd part of the location 6. Now we have the number 806. Its remainder is also 6. As both the parts of location 6 are occupied. Using the linear probing we will store it in the next array location i.e. 7. If we have another number having the remainder as 6, we will store it at the 2nd part of location 7. If we have number 807, its remainder is 7. The location 7 is already occupied due to the linear probing. Therefore the number 807 will be stored using the linear probing in the location 8. http://ecomputernotes.comHashing Animation: Hashing Animation Let’s change the collision resolution algorithm to quadratic probing. Run the animation again. Now we have array size as 75 and the array is shown in three columns. Each location of the array can store two numbers. In quadratic probing we add square of one first i.e. 1 and then the square of two and so on in case of collisions. Here we have used a different hash function. We will take the mod with 75. When the both parts of the array location is filled we will use the quadratic probing to store the next numbers. Analyze the numbers and see where the collisions have happened. Lets see the animation using the linked list chaining. Now the hash function uses 50 to take mod with the numbers. So far pointers are not shown. When both parts of the location are filled, we will see the link list appearing. We have four numbers having remainder 0. The two numbers will be stored in the array and the next two will be stored using the link list which is attached at the 0 location. We are not covering the hashing topic in much depth here as it is done in algorithms and analysis of algorithms domain. This domain is not part of this course. For the time being, we will see the usage of hashing. For certain situations, table ADT can be used, which internally would be using hashing. http://ecomputernotes.comApplications of Hashing: Applications of Hashing Compilers use hash tables to keep track of declared variables (symbol table). A hash table can be used for on-line spelling checkers — if misspelling detection (rather than correction) is important, an entire dictionary can be hashed and words checked in constant time. http://ecomputernotes.comApplications of Hashing: Applications of Hashing Game playing programs use hash tables to store seen positions, thereby saving computation time if the position is encountered again. Hash functions can be used to quickly check for inequality — if two elements hash to different values they must be different. http://ecomputernotes.comWhen is hashing suitable?: When is hashing suitable? Hash tables are very good if there is a need for many searches in a reasonably stable table. Hash tables are not so good if there are many insertions and deletions, or if table traversals are needed — in this case, AVL trees are better. Also, hashing is very slow for any operations which require the entries to be sorted e.g. Find the minimum key http://ecomputernotes.comSorting Integers: Sorting Integers 20 8 5 10 7 5 7 8 10 20 How to sort the integers in this array? http://ecomputernotes.comElementary Sorting Algorithms: Elementary Sorting Algorithms Selection Sort Insertion Sort Bubble Sort http://ecomputernotes.comSelection Sort : Selection Sort Main idea: find the smallest element put it in the first position find the next smallest element put it in the second position … And so on, until you get to the end of the list http://ecomputernotes.com