CS & AI&DS

SPPU
2019 PATTERN
SUBJECT :-DATA
PRINCIPLES
SOFTWARE STRUCTURES
OF PROGRAMING
ENGINEERING ALGOLITHMS
LANGUAGES
INSEM IMP WITH
INSEM IMP WITH SOLUTION
SOLUTION
CLICK ON LOGO JOIN SOCIAL MEDIA PLATFORM

JOIN PRIVATE WHATSAPP GROUP

10000 + STUDENT TRUSTED

TELEGRAM CHANNEL

PROVIDED BY:- OMKAR TULE

 Hash Table: a data structure which makes use of hash function to map key value
into it.

Why Hashing?

Hash Function: it maps key value to hash table, it returns an address to which
key is mapped

Types of Hash Function:

 division method
 multiplication method
 midsquare method
 Folding

1) Division Method:

let x be any key val

then we use the following hash function:
f(x)=x%(size of hash table)

2) Multiplication Method:
The hash function used for the multiplication method is –

h(k) = floor( n( kA ) )

Here, k is the key and A can be any constant value between 0 and 1.
Both k and A are multiplied then their fractional part is separated.
This is then multiplied with n to get the hash value.

An example of the Multiplication Method is as follows –

k=123
n=100
A=0.618033

https://t.me/SPPU_SE_COMP
h(123) = floor(100* (123 * 0.618033))
= floor (100* (76.018059 ))
= floor (100* (0.018059))
= floor (1.8059)
The hash value obtained is 1

3) Mid Square Method:

The mid square method is a very good hash function. It involves squaring the value
of the key and then extracting the middle r digits as the hash value. The value of r
can be decided according to the size of the hash table.

An example of the Mid Square Method is as follows −

Suppose the hash table has 100 memory locations. So r=2 because two digits are
required to map the key to memory location.
k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

4) Folding Method:
We break a key into groups of digits and then do the addition of groups. This
ensures that all the digits contribute the hash code. The number of digits in a group
correspond to the size of the array.
There are 2 types of folding methods used Fold shift and Fold boundary.
Fold Shift:
Key: 123456789 and size of required address is 3 digits.
123+456+789 = 1368. To reduce the size to 3, either 1 or 8 is removed and
accordingly the key would be 368 or 136 respectively.
Fold Boundary:
Key: 123456789 and size of required address is 3 digits
321 (folding applied)+456+987 (folding applied) = 1764(discard 1 or 4)

https://t.me/SPPU_SE_COMP
Properties of a Hash Function:
- avoids collision
-easy to compute
-uniform key distributation

Two Different Forms of Hashing:

-open hashing / external hashing
-close hashing / internal hashing

Two Different Forms of Hashing:

1) Open Hashing / External Hashing
2) Close Hashing / Internal Hashing

Open Hashing / External Hashing:

Open hashing is a collision avoidance method which uses array of linked
list to resolve the collision.
It is also known as the separate chaining method (each linked list is
considered as a chain). Following is an example
Keys: 11, 21, 43, 66, 86, 78

https://t.me/SPPU_SE_COMP
Close Hashing / Internal Hashing: It uses fixed size space for storage & thus
limits size of the hash table. Only one element can be put into the bucket. If
collision occurs then that element is rehashed. Following is an example.
Keys: 11, 21, 43, 66, 86, 78

https://t.me/SPPU_SE_COMP
Collision Resolution Strategies:
1) Separate Chaining/Open Hashing
2) Open Addressing

Separate Chaining / Open Hashing:

It is used with open hashing.
It requires additional memory for pointers.
Explained Above with an example

Open addressing:
It is an alternative method for handling collisions.
If collisions occur then alternative cells are tried until an empty cell is found.
Commonly used strategies in open addressing are:
 Linear probing
 Quadratic Probing
 Double Hashing

https://t.me/SPPU_SE_COMP
Linear Probing: In linear probing, we linearly probe for next slot. For example,
the typical gap between two probes is 1 as seen in the example below.
Let hash(x) be the slot index computed using a hash function and S be the table
size
If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
..................................................
..................................................
Let us consider a simple hash function as “key mod 7” and a sequence of keys as
50, 700, 76, 85, 92, 73, 101.

https://t.me/SPPU_SE_COMP
Quadratic Probing in Hashing

Quadratic Probing: Quadratic probing is an open-addressing scheme where we

look for i2‘th slot in i’th iteration if the given hash value x collides in the hash
table.
How Quadratic Probing is done?
Let hash(x) be the slot index computed using the hash function.
 If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.
 If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
 If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
 This process is repeated for all the values of i until an empty slot is found.
For example: Let us consider a simple hash function as “key mod 7” and
sequence of keys as 50, 700, 76, 85, 92, 73, 101.

https://t.me/SPPU_SE_COMP
Double Hashing:

Double hashing is a collision resolving technique in Open Addressed Hash tables.

Double hashing uses the idea of applying a second hash function to key when a
collision occurs.

Double hashing can be done using :

(hash1(key) + i * hash2(key)) % TABLE_SIZE
Here hash1() and hash2() are hash functions and TABLE_SIZE
is size of hash table.
(We repeat by increasing i when collision occurs)

First hash function is typically hash1(key) = key % TABLE_SIZE

A popular second hash function is : hash2(key) = PRIME – (key %
PRIME) where PRIME is a prime smaller than the TABLE_SIZE.

https://t.me/SPPU_SE_COMP
Skip list

A skip list is a probabilistic data structure. The skip list is used to store a sorted list
of elements or data with a linked list. It allows the process of the elements or data
to view efficiently. In one single step, it skips several elements of the entire list,
which is why it is known as a skip list. The skip list is an extended version of the
linked list. It allows the user to search, remove, and insert the element very
quickly. It is built in two layers: The lowest layer and Top layer. The lowest layer
of the skip list is a common sorted linked list, and the top layers of the skip list are
like an "express line" where the elements are skipped.

Working of the Skip list

Let's take an example to understand the working of the skip list. In this example,
we have 14 nodes, such that these nodes are divided into two layers, as shown in
the diagram. The lower layer is a common line that links all nodes, and the top
layer is an express line that links only the main nodes, as you can see in the
diagram.

Suppose you want to find 47 in this example. You will start the search from the
first node of the express line and continue running on the express line until you
find a node that is equal a 47 or more than 47.

You can see in the example that 47 does not exist in the express line, so you search
for a node of less than 47, which is 40. Now, you go to the normal line with the
help of 40, and search the 47, as shown in the diagram.

Advantages of the Skip list:

https://t.me/SPPU_SE_COMP
 1. The skip list is simple to implement as compared to the hash table and the
binary search tree.
2. It is very simple to find a node in the list because it stores the nodes in sorted
form.
3. The skip list algorithm can be modified very easily in a more specific
structure, such as indexable skip lists, trees, or priority queues.
4. The skip list is a robust and reliable list.

Disadvantages of the Skip list:

1. It requires more memory than the balanced tree.
2. Reverse searching is not allowed.

Applications of the Skip list:

1. It is used in distributed applications, and it represents the pointers and
system in the distributed applications.
2. It is used to implement a dynamic elastic concurrent queue with low lock
contention.
3. It is also used with the QMap template class.
4. The indexing of the skip list is used in running median problems.
5. The skip list is used for the delta-encoding posting in the Lucene search.

https://t.me/SPPU_SE_COMP
Linear Probing: In linear probing, we linearly probe for next slot. For example,
the typical gap between two probes is 1 as seen in the example below.
Let hash(x) be the slot index computed using a hash function and S be the table
size
If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
..................................................
..................................................
Let us consider a simple hash function as “key mod 7” and a sequence of keys as
50, 700, 76, 85, 92, 73, 101.

https://t.me/SPPU_SE_COMP
Quadratic Probing in Hashing

Quadratic Probing: Quadratic probing is an open-addressing scheme where we

look for i2‘th slot in i’th iteration if the given hash value x collides in the hash
table.
How Quadratic Probing is done?
Let hash(x) be the slot index computed using the hash function.
● If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.
● If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.
● If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.
● This process is repeated for all the values of i until an empty slot is found.
For example: Let us consider a simple hash function as “key mod 7” and
sequence of keys as 50, 700, 76, 85, 92, 73, 101.

https://t.me/SPPU_SE_COMP
Double Hashing:

Double hashing is a collision resolving technique in Open Addressed Hash tables.

Double hashing uses the idea of applying a second hash function to key when a
collision occurs.

Double hashing can be done using :

(hash1(key) + i * hash2(key)) % TABLE_SIZE
Here hash1() and hash2() are hash functions and TABLE_SIZE
is size of hash table.
(We repeat by increasing i when collision occurs)

First hash function is typically hash1(key) = key % TABLE_SIZE

A popular second hash function is : hash2(key) = PRIME – (key %
PRIME) where PRIME is a prime smaller than the TABLE_SIZE.

https://t.me/SPPU_SE_COMP
void hash1(int hash[])
{
int add,temp,i,x;
char ch;
for(i=0;i<10;i++)
hash[i]=-1;
do
{
printf("\nEnter The NO:");
scanf("%d",&x);
add=f(x);

if(hash[add]==-1)
hash[add]=x;
else
{
temp=(add+1)%10;
while(temp!=add)
{
if(hash[temp]==-1)
{
hash[temp]=x;
break;
}
else
temp=(temp+1)%10;
}
if(temp==add&&hash[temp]!=x)
{
printf("\nOverflow");
break;
}
}printf("\nDo U Wanna Continue(Y/N):");
ch=getche();

}while(ch=='y'||ch=='Y');

for(i=0;i<10;i++)
printf("\n%d",hash[i]);

int f(int x)
{

https://t.me/SPPU_SE_COMP
 int temp;
temp=x%10;
return(temp);
}

https://t.me/SPPU_SE_COMP
Skip list

A skip list is a probabilistic data structure. The skip list is used to store a sorted list
of elements or data with a linked list. It allows the process of the elements or data
to view efficiently. In one single step, it skips several elements of the entire list,
which is why it is known as a skip list. The skip list is an extended version of the
linked list. It allows the user to search, remove, and insert the element very
quickly. It is built in two layers: The lowest layer and Top layer. The lowest layer
of the skip list is a common sorted linked list, and the top layers of the skip list are
like an "express line" where the elements are skipped.

Working of the Skip list

Let's take an example to understand the working of the skip list. In this example,
we have 14 nodes, such that these nodes are divided into two layers, as shown in
the diagram. The lower layer is a common line that links all nodes, and the top
layer is an express line that links only the main nodes, as you can see in the
diagram.

Suppose you want to find 47 in this example. You will start the search from the
first node of the express line and continue running on the express line until you
find a node that is equal a 47 or more than 47.

You can see in the example that 47 does not exist in the express line, so you search
for a node of less than 47, which is 40. Now, you go to the normal line with the
help of 40, and search the 47, as shown in the diagram.

https://t.me/SPPU_SE_COMP
Advantages of the Skip list:
1. The skip list is simple to implement as compared to the hash table and the
binary search tree.
2. It is very simple to find a node in the list because it stores the nodes in sorted
form.
3. The skip list algorithm can be modified very easily in a more specific
structure, such as indexable skip lists, trees, or priority queues.
4. The skip list is a robust and reliable list.

Disadvantages of the Skip list:

1. It requires more memory than the balanced tree.
2. Reverse searching is not allowed.

Applications of the Skip list:

1. It is used in distributed applications, and it represents the pointers and
system in the distributed applications.
2. It is used to implement a dynamic elastic concurrent queue with low lock
contention.
3. It is also used with the QMap template class.
4. The indexing of the skip list is used in running median problems.
5. The skip list is used for the delta-encoding posting in the Lucene search.

https://t.me/SPPU_SE_COMP
Tree:
Tree represents the nodes connected by edges. It is a graph without any cycle.
Binary Tree is a special data structure used for data storage purposes. A binary tree has a special
condition that each node can have a maximum of two children.

Following are the important terms with respect to tree.

 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one root per tree and
one path from the root node to any node.
 Parent − Any node except the root node has one edge upward to a node called parent.
 Child − The node below a given node connected by its edge downward is called its
child node.
 Leaf − The node which does not have any child node is called the leaf node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control is on the node.
 Traversing − Traversing means passing through nodes in a specific order.
 Levels − Level of a node represents the generation of a node. If the root node is at level
0, then its next child node is at level 1, its grandchild is at level 2, and so on.
 keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.

https://t.me/SPPU_SE_COMP
 The following are common types of Binary Trees.
Full Binary Tree A Binary Tree is a full binary tree if every node has 0 or 2 children.
The following are the examples of a full binary tree. We can also say a full binary tree
is a binary tree in which all nodes except leaf nodes have two children.
The following are the examples of Fully Binary Trees.

Perfect Binary Tree A Binary tree is a Perfect Binary Tree in which all the internal nodes
have two children and all leaf nodes are at the same level.
The following are the examples of Perfect Binary Trees.

https://t.me/SPPU_SE_COMP
Complete Binary Tree: A Binary Tree is a Complete Binary Tree if all the levels are
completely filled except possibly the last level and the last level has all keys as left as possible
The following are examples of Complete Binary Trees

Skewed Binary Tree: A skewed binary tree is a type of binary tree in which all the nodes have
only either one child or no child.
Types of Skewed Binary trees
there are 2 special types of skewed tree:
1. Left Skewed Binary Tree:
These are those skewed binary trees in which all the nodes are having a left child or no
child at all. It is a left side dominated tree. All the right children remain as null.
2. Right Skewed Binary Tree:
These are those skewed binary trees in which all the nodes are having a right child or
no child at all. It is a right side dominated tree. All the left children remain as null.

https://t.me/SPPU_SE_COMP
Non Recursive Definitions of Tree Traversals:

void inorder(node *root)

{
node *temp;
temp=root;
while(1)
{
while(temp!=NULL)
{
push(temp);
temp=temp->L;
}
if(top==-1)
{
break;
}
temp=pop();
cout<<temp->data;
temp=temp->R;
}
}

Stack Definitions:

https://t.me/SPPU_SE_COMP
node * s[10];

int top=-1;

void push(node *temp)

{
top++;
s[top]=temp;
}

node *pop()
{
node *temp;
temp=s[top];
top--;
return temp;
}

void preorder(node *root)

{
node *temp;
temp=root;

https://t.me/SPPU_SE_COMP
 while(1)
{
while(temp!=NULL)
{
cout<<temp->data;
push(temp);
temp=temp->L;
}
if(top==-1)
{
break;
}
temp=pop();
temp=temp->R;
}
}

void postorder(node *root)

{
node *temp;
temp=root;
while(1)
{
while(temp!=NULL)

https://t.me/SPPU_SE_COMP
 {
push(temp);
temp=temp->L;
}

if(s[top]->R==NULL)
{
temp=pop();
cout<<temp->data;
}

while(s[top]->R==temp && top!=-1)

{
temp=pop();
cout<<temp->data;
}

it(top==-1)
break;
temp=s[top]->R;
}
}

https://t.me/SPPU_SE_COMP
Binary Search Tree Delete Algorithm
1) Node to be deleted is leaf: Simply remove from the tree.

2) Node to be deleted has only one child: Copy the child to the node and
delete the child .

3) Node to be deleted has two children: Find inorder successor of the node.
Copy contents of the inorder successor to the node and delete the inorder
successor. Note that inorder predecessor can also be used.
The important thing to note is, inorder successor is needed only when right
child is not empty. In this particular case, inorder successor can be obtained
by finding the minimum value in right child of the node.

node* deleteNode(node* root, int key)

{

https://t.me/SPPU_SE_COMP
 Node *small;
if (root == NULL)
return root;

if (key < root->data)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else
{
if(root->right!=NULL)
{
Small=smallest(root->right);
root->data=small->data;
root->right=deleteNode(root->right, small->data);
}

else
return root->left;
}
return root;
}

Node *smallest(node *root)

{
Node *temp;
Temp=root;
While(temp->L!=NULL)
{
Temp=temp->L;
}
Return Temp;
}

https://t.me/SPPU_SE_COMP