CSE 204 (Data Structures Sessional)
Assignment #5(Section A1, B1)

HASHING: RELATIVE PERFORMANCE OF COLLISION RESOLUTION TECHNIQUES

You are to compare three collision resolution techniques in Hashing:
    1. Coalesced chaining
    2. Linear Probing
    3. Double hashing

The performance criteria are:
    a. Average number of probes in successful search
    b. Average number of probes in unsuccessful search

The Table:
Each element of the table is a positive integer. Element value <= 0 indicates empty table location. Table size m <= 100. m is an input. If m is not prime then replace it with nearest prime number <= 100.

The Hash function :
h(z) = z mod m
d(z) = max(1, z mod (m - 1))    [for double hashing]

Procedure:

1. Take 3 tables T1, T2, T3 of size m.
2. Initialize all locations to empty.
3. Generate a random number x, 0 < x < 10000
4. Insert x in
         a. T1 : using coalesced chaining
         b. T2: using linear probing
         c. T3: using double hashing
5. If table size < 3*m/4 then go to step 3 else go to step 6.
6. Print all the tables in a file. Also Print the link fields for T1 .
7. Calculate average cost using two processes:
       Process 1: Follow the methods for calculating average number of probes in successful and
                          unsuccessful search described in the examples of chapter 7.4(page 345, 349).
                          Let
                            Average # of probes in successful search (in table T_j ) = Sm_j, (1 <= j <= 3)
                            Average # of probes in unsuccessful search (in table T_j )= Um_j. (1 <= j <= 3)
       Process 2: follow these steps --
                              i. Set u_j = 0, Sn_j = 0, Un_j = 0 (1 <= j <= 3)
                              ii. for i = 1 to 1000 do
                                         y = a random number (0 < y < 10000)
                                         for j = 1 to 3
                                               search y in table Tj.
                                               let n be the number of probes required to search y.
                                               If the search was successful,
                                                        then Sn_j = Sn_j + n
                                                        else Un_j = Un_j + n, u_j = u_j + 1.
                             iii. Sn_j = Sn_j / (1000 - u_j), Un_j = Un_j / u_j. (1 <= j <= 3)
                             iv. Now Average # of probes in successful search = Sn_j, (1 <= j <= 3)
                                          Average # of probes in unsuccessful search = Un_j. (1 <= j <= 3)

8. Print the results in tabular form:

Marks distribution:

Implementing all 3 collision resolution techniques = 6 (=3 x 2)
Cost calculation using process 1 = 6 (= 3 x 2)
Cost calculation using process 2 = 6 (=3 x 2)
Showing all outputs (including file output) = 2

Total = 20

Last date of submission:  May 24, 2003(B1)
                                                 May 28, 2003(A1)