Assignment Task

• Our institute decided to split the students into four groups to conduct an The procedure for splitting is as follows:

h(A) = (Sum of ASCII value of the characters in the first name of ‘A’ + age of ‘A’) % 4, where ‘A’ represents a student.

• As part of MNTIP scholarship programme, first name, last name, gender, date of bith, department and CGPA of fourth semester students of NITC are The scholarship is for four semesters from fifth semester onwards. The record information is organized using a hash table with the help of a separate chaining technique. In separate chaining, the size of the hash table is 26, such that to insert a record into the hash table, ASCII value of the first character of first name starts with A points to index 0, ASCII value of the first character of first name starts with B points to index 1 and so on. The resulting location contains a pointer to a Binary Search Tree(BST), in this case the root of a binary search tree (BST), where all elements with the same index are stored. Since a BST requires that its nodes be comparable to each other, we need to define an order among the records being stored in the BST lexiographically. The key value of each node in BST is student’s (firstname, lastname) pair, assuming it is unique to a student. The update function updates the CGPA of the corresponding key. The insert/update/delete function should return the number of nodes touched in the BST (except the current node) while performing the given operation. The location function returns index-bstsequence, where index represents the index of the key in the hash table, and bstsequence represents the sequence of L/R steps taken on the binary search tree of all records whose index is the same.
• Open addressing is a method for handling collisions in hashing. The three different methods for open addressing are linear probing, quadratic probing, and double hashing. A brief description of the three methods is given below:

In linear probing, the function used to calculate the next location during collision is: h ^′ ( k ) = ( h ( k ) + i ) mod m, i = 1 , 2 . . . .

In quadratic probing, the function used to calculate the next location during collision is: h ^′ ( k ) = ( h ( k ) + i ² ) mod m, i = 1 , 2 . . .

In double hashing scheme, the primary hash function is, h 1( k ) = k mod N , where N is the table size. The secondary hash function is, h 2( k ) = R − ( key mod R ) where R is the maximum prime number less than the table size. Double hashing can be done using: ( h 1( key ) + i ∗ h 2( key )) mod N, i = 0 , 1 , 2 .

Given a set of keys and the table size, write a program to print the locations at which the keys are stored using the above-mentioned three methods and also print the total number of collisions that occur during mapping for each of the three methods.

• Write a program to create an AVL Tree A and perform the operations insertion , deletion , search and traversal . Assume that the AVL Tree A does not contain duplicate values. Your program should contain the following functions.
• Write a program to compute the median element of the set of elements stored in the AVL The median of a set of n numbers is the element that appears in the n/2 th position, when the set is written in sorted order. When n is even, n/2 and when n is odd, (n + 1)/2 is the position for the median element. For example, if the set is 3, 2, 1, 4, 6 then the set in sorted order is 1, 2, 3, 4, 6, and the median is 3.

Consider a modified AVL tree in which each parent node stores both a key and the total no of nodes in the right and left subtree + 1 .

1. A Red-Black tree is a self-balancing binary search tree where every node obeys the following

• Every node is either red or black
• The root is always black
• There are no two adjacent red nodes (A red node cannot have a red parent or red child)
• All paths from a node to descendant nodes contain the same number of black nodes

Write a program to create a Red Black Tree from the given input. Your program should include the following function

• InsertRedBlack(struct node* root, key) : Inserts a new node with the ‘key’ into the tree and prints parenthesized representation (with corresponding colors) of the created red-black