Searching

This chapter discusses searching algorithms, including sequential search and binary search. It covers their algorithms, complexities, and comparisons. The chapter also explores hashing techniques and collision resolution methods.

Question and Solution.

2079 Chaitra

Explain how collision occur? Use quadratic probing to insert follwing keys 72, 27, 36, 24, 63, 81, and 101 into hash table, Considerring hash table size 10. And also list advantages and disadvantages.

Solution A collision occurs when more than one value to be hashed by a particular hash function hash to the same slot in the table or data structure (hash table) being generated by the hash function.

Quadratic Probing

Advantages

faster inserts (for reason of simpler storage)
reduced storage requirement in general

Disadvantages
Typically not all hash table slots will be on the probe sequence.

2079 Ashwin

What is Hashing ? why do we need Hashing ? Discuss linear probing in detail.

Solution The process of mapping large amount of of data into a smaller table is called Hashing.

Hashing gives a more secure and adjustable method of retrieving data compared to any other data structure. It is quicker than searching for lists and arrays. In the very range, Hashing can recover data in 1.5 probes, anything that is saved in a tree.

Linear Probing: A hash table in which a collision is resolved by putting the item in the next empty place within the occupied array space is called linear probing. The disadvantage of this process is clustering problem.

Example: Insert keys 58 with the hash function h(x) = x mod 10 using linear probing.

2077 Poush

Write an recursive algorithm for binary search. Explain how chaining method avoids collision.

Solution Recursive algorithm for binary search.

Step 1 : Find the middle element of array. using ,
middle = initial_value + (end_value - initial_value) / 2 ;
Step 2 : If middle = element, return ‘element found’ and index.
Step 3 : if middle > element, call the function with end_value = middle - 1 .
Step 4 : if middle < element, call the function with start_value = middle + 1 .
Step 5 : exit.

Pseudocode

RecursiveBinarySearch(arr, tar, start, end){
    if(start<= end){
        int mid = start + (end - start)/2
        if(tar > arr[mid]){
            return RecursiveBinarySearch(arr, tar, mid+1, end)
        }else if(arr[mid]>tar){
            return RecursiveBinarySearch(arr, tar, start, mid-1)
        }else{
            return mid
        }
    }
    return -1
}

Chaining: Chaining is an alternative method for handling the collision problem by allowing each slot to hold a reference to collecction (or chain) of items. It allows many items to exist at the same location in the hash table. Fig. below shows the items as they are added to a hash table that uses Chaining to resolve collision.

2076 Bhadra

Insert following keys: 30, 25, 79, 19, 48, 28, 21 and 44 in hash table using linear probing method where h(key) = key % 10.

Solution To find the proper position for above keys using hash function.

2076 Baisakh

Define binary search with example. What is the cause of collision in hashing and explain any one method for the collision resolution.

Solution Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half.

Example:

#include <iostream>
#include <vector>

using namespace std;
int binarySearch(vector<int> &arr, int tar)
{
    int st = 0, end = arr.size(), mid = 0;
    while (st <= end)
    {
        mid = st + (end - st) / 2;
        if (tar > arr[mid])
        {
            st = mid + 1;
        }
        else if (tar < arr[mid])
        {
            end = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

int main()
{
    vector<int> arr = {-1, 0, 3, 4, 5, 9, 12};
    int tar = 4;
    cout << tar << " is found at index  " << binarySearch(arr, tar) << "of the given array." << endl;
    ;
    return 0;
}

A hashing collision occurs when two different inputs produce the same hash value. This can happen for various reasons, such as using a weak or flawed hashing algorithm, having a small hash space, or having a large number of inputs.

2075 Bhadra

Draw hash table obtained from double hashing with hash functions: h(K) = K mod 11 and h(K) = K mod 9 for the given keys: 76, 36, 47, 49, 21, 65 with table size 11. use hp(k,i) = (h1(k) + i * h2(k)) mod m.

Solution: Here, hp(k,i) = (h1(k) + i * h2(K)) mod m [where m= 11]
Initially, we take i = 0 to find the position for above keys. if collision occurs, we have to take i = 1, 2, 3 and so on.

2071 Bhadra

What is collision. What are the techniques used for collision resolution in hashing technique ? Explain two different methods with suitable example.

The technique used for collision resolution in hashing technique are:
1. Linear Probing
2. Chaining.
3. Quadratic Probing.
4. Double hashing.
5. Rehashing.

Two different method are: Linear Probing: A hash table in which a collision is resolved by putting the item in the next empty place within the occupied array space is called linear probing. The disadvantage of this process is clustering problem.