Data Structures CS205 Note-Module 6

CS205 Data Structures

Sixth Module Full Note

DSA Sixth Module Syllabus

Linear and Binary search. (Performance comparison expected.Detailed analysis not required) Hash Tables – Hashing functions – Mid square, division,folding, digit analysis, collusion resolution and Overflow handling techniques.

SEQUENTIAL SEARCH

Sequential_search(key)

Input: An unsorted array a[], n is the no.of elements, key indicates the element to be searched

Output: Target element found status

DS: Array

1. Start

2. i=0

3. flag=0

4. While i<n and flag=0

   1. If a[i]=key

      1. Flag=1

      2. Index=i

   2.end if

   3. i=i+1

5. end while

6. if flag=1

   1. print “the key is found at location index”

7. else

   1.print “key is not found”

8.end if

9. stop

Analysis

In this algorithm the key is searched from first to last position in linear manner. In the case of a successful search, it search elements up to the position in the array where it finds the key. Suppose it finds the key at first position, the algorithm behaves like best case, If the key is at the last position, then algorithm behaves like worst case. Thus the worst case time complexity is equal to the no. of comparison at worst case ie., equal to O(n). The time complexity in best case is O(1).

The average case time complexity =( no. of comparisons required when the key is in the first position + no. of comparisons required when the key is in second position+...+ no. of comparison when key is in nth position)

HASHING

We have seen about different search techniques (linear search, binary search) where search time is basically dependent on the no of elements and no. of comparisons performed. Hashing is a technique which gives constant search time. In hashing the key value is stored in the hash table depending on the hash function. The hash function maps the key into corresponding index of the array(hash table).

The main idea behind any hashing technique is to find one-to-one correspondence between a key value and an index in the hash table where the key value can be placed. Mathematically, this can be expressed as shown in figure below where K denotes a set of key values, I denotes a range of indices, and H denotes the mapping function from K to I.

Download Full pdf