Data Structures and Algorithms · Unit 7
Searching and Hashing
Exam-focused notes for Searching and Hashing (Data Structures and Algorithms, BIT201): what the TU syllabus asks and how it has actually been tested, with 6 solved past questions from this unit.
What this unit covers
- Sequential search algorithm
- Binary search algorithm
- Comparison between sequential and binary search
- Hashing definition and advantages
- Hash collision definition
- Quadratic probing collision resolution
- Double hashing collision resolution
- Hashing versus binary search comparison
Quadratic probing collision resolution
Why do we need hashing? Explain quadratic probing. [5]
In many applications, we need to search, insert, and delete data efficiently. Traditional data structures have the following limitations: Structure Search Time ------ Unsorted Array O(n) Sorted Array (Binary Search) O(log n) BST (balanced) O(log n) Hashing ...
Full solved answer →Define hashing. Explain quadratic probing with example. [5]
Hashing is a technique used to map a key to a specific location (index) in a hash table using a hash function. The hash function computes an index from the key, allowing for O(1) average-case time complexity for insertion, deletion, and search operations. H...
Full solved answer →Double hashing collision resolution
Explain collision and collision resolution in hashing. What is double hashing? [5]
A collision occurs when two or more different keys are mapped to the same hash table index by the hash function. For example, if hash function is h(k) = k mod 10: - h(23) = 3 - h(33) = 3 → Collision! Collisions are unavoidable when the number of possible ke...
Full solved answer →Sequential search algorithm
Write short notes on: a) Linear Search Write short notes on: b) Minimum Spanning Tree [2.5+2.5]
Definition: Linear search (also called sequential search) is the simplest searching algorithm that checks each element of a list one by one, from the beginning to the end, until the desired element (key) is found or the list is exhausted. Algorithm: Working...
Full solved answer →Comparison between sequential and binary search
Explain sequential search. How is it different from binary search? [5]
Sequential search (also called linear search) is the simplest searching technique in which each element of the array or list is examined one by one, from the beginning to the end, until the desired element (key) is found or the entire list has been traverse...
Full solved answer →Hashing versus binary search comparison
Is hashing better than binary search algorithm? Give reasons. Define any two collision resolution techniques. [5]
It depends on the use case, but in many scenarios hashing is considered better than binary search. Here is a comparison: Criteria Hashing Binary Search --------- Time Complexity (Average) O(1) O(log n) Time Complexity (Worst) O(n) O(log n) Data Requirement ...
Full solved answer →Make Unit 7 stick
Practice BIT201 with flashcards & quizzes