M.C.A.

(Management)
IT – 12 : DATA STRUCTURES AND ALGORITHMS
(2024 Pattern) (Semester – I)
Solution
NOTE:

1. Please don’t give marks if in place of an algorithm, a student has written the Python
code.
2. Please don’t give marks if a student has used the library function of Python directly. We
are expecting them to write the logic of the predefined function.

Q.1 a) Write an algorithm to generate fibonacci series upto 5 numbers using array elements.

[6 marks]

Ans 1 a)

Fibo(A,5):

STEP 1: Start

STEP 2: Declare A as an array and I as an integer

STEP 3: Set A[0]  0

STEP 4: Set A[1]  1

STEP 5: For I  2 to 5 do

Set A[I]  A[I - 1] + A[I - 2]

Next I

[End of For loop]

STEP 6: For I  0 to 5 do

Print A[I]

Next I

[End of For loop]

STEP 7: Stop

If a student have written the algorithm and given an example for the same, allot 6 marks.

Q.1 b) Explain various 1D array applications. [4 marks]

Ans 1 b) Applications of Array Data Structure:

Arrays mainly have advantages like random access and cache friendliness over other data structures
that make them useful.
Below are some applications of arrays.
 Storing and accessing data: Arrays store elements in a specific order and allow constant-time
O(1) access to any element.
 Searching: If data in array is sorted, we can search an item in O(log n) time. We can also find
floor(), ceiling(), ―n‖ th smallest, ―n‖ th largest, etc efficiently.
 Implementing other data structures: Arrays are used as the underlying data structure for
implementing stacks and queues.
 Dynamic programming: Dynamic programming algorithms often use arrays to store
intermediate results of sub-problems in order to solve a larger problem.
 Data Buffers: Arrays serve as data buffers and queues, temporarily storing incoming data like
network packets, file streams, and database results before processing.
 Arrays are extensively used to store and process data in mathematical and scientific computations,
making them invaluable in fields like engineering and physics.
 Strings can be represented as one-dimensional character arrays, enabling various string
manipulation operations.

Q.1 c) Write an algorithm to insert elements at the last position of the list.
Ans 1 c) To insert an element at the end of the list, first we have to find the length of the list and then
we can perform the append operation.

Insert(A, len, Val):

STEP 1: Start

STEP 2: Declare A as a list, I, n, Val, len as integers

STEP 3: Set len  0

[Create the list and find the length of the list]

STEP 4: For I  0 to n do

Read A[I]

Set len = len + 1

[End of For Loop]

STEP 4: Print ― Enter a value to insert ―

STEP 5: Read Val

[Append the new value at the end of the list]

STEP 6: Set A[len - 1]  Val

STEP 7: For I  0 to len do

Print A[I]

Next I

[ End of For loop]

STEP 8: Stop

If a student have written the algorithm first and given an example for the same, allot 6 marks.
If only append function is written or a Python code is written then NO MARKS.

Student must be assigned step marking.

Q.1 d) Explain spare matrix with an example. [4 marks]

Ans 1 d) Sparse Matrix: A sparse matrix is a special case of a matrix in which the number of zero
elements is much higher than the number of non-zero elements. As a rule of thumb, if 2/3 of the total
elements in a matrix are zeros, it can be called a sparse matrix. Using a sparse matrix representation
— where only the non-zero values are stored — the space used for representing data and the time for
scanning the matrix are reduced significantly.

Example:
00304
00570
00000
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the
matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we
only store non-zero elements. This means storing non-zero elements with triples- (Row, Column,
value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row, column)

Method 2: Using Linked List:

In a linked list representation, the linked list data structure is used to represent the sparse matrix. The
advantage of using a linked list to represent the sparse matrix is that the complexity of inserting or
deleting a node in a linked list is lesser than the array.

Unlike the array representation, a node in the linked list representation consists of four fields. The
four fields of the linked list are given as follows -

o Row - It represents the index of the row where the non-zero element is located.
o Column - It represents the index of the column where the non-zero element is located.
o Value - It is the value of the non-zero element that is located at the index (row, column).
o Next node - It stores the address of the next node.
The node structure of the linked list representation of the sparse matrix is shown in the below image -

Consider the sparse matrix -

In the above figure, we can observe a 4x4 sparse matrix containing 5 non-zero elements and
11 zero elements. Above matrix occupies 4x4 = 16 memory space. Increasing the size of
matrix will increase the wastage space.

The linked list representation of the above matrix is given below -

If the student has explained the 3-Tuple form of the sparse matrix then you can allot full 4
marks, otherwise give step marking.

Q. 2 a) Write an algorithm to print sum of alternate node elements in a doubly linked list. [6 marks]

Ans 2 a) Consider that the doubly linked list is already being created. For example,

STEP 1: Start
STEP 2: Declare curr as a marker and sum as an integer
STEP 3: Set sum  0
STEP 4: Set curr  head
STEP 5: While(curr < > NULL) [curr not equal to NULL, to traverse up to the last node of the
list]
Set sum  sum + curr. info
Set curr  (curr.Next).Next
[ End of While Loop]
STEP 6: Print sum
STEP 7: Stop
Student must be assigned step marking.

Q. 2 b) Differentiate between a Doubly Linked List and a Circular Linked List. [4 marks]
Ans 2 b)
Sr. Doubly Linked List Circular Linked List
No.
1 It is a bi-directional list. It is a unidirectional list.
2 The node consists of 3 fields: The node consists of 2 fields:
 1. Back: Address of Previous Node 1. Info: Information about a Node
2. Info: Information about a Node 2. Next: Address of Next Node
3. Next: Address of Next Node
3 It can be traversed in both the directions. It can be traversed in one direction only.
The Next field of last node contains NULL. The Next field of last node contains the
4
address of the first node.

Q.2 c) Write an algorithm to reverse the single linked list elements. [6 marks]
Ans 2 c) Consider that the single linked list is already being created.
The algorithm:
Reverse( ):
STEP 1: Start
STEP 2: Declare head, curr, temp, trail as markers
[Check whether the linklist is empty. If it is empty, then print appropriate message.]
STEP 3: If head == NULL
Print ― Link list is empty‖
Goto Step 10
STEP 4: Else
Set curr  head
[Traverse the linked list to reach to the end.]
STEP 5: While (curr < > NULL) [ curr not equal to NULL]
Set curr  curr.Next
[End of While loop]
STEP 6: Set temp  curr
STEP 7: While(curr < > head)
Set trail  head
While(trail.Next < > curr)
Set trail  trail. Next
[End of Inner While Loop]
Set curr.Next  trail
Set curr  trail
[End of Outer While Loop]
STEP 8: Set curr. Next  NULL
STEP 9: Set head  temp
STEP 10: Stop
Student must be assigned step marking.

Q.2 d) Write an algorithm to delete a node from the beginning in singly linked list. [4 marks]
Ans 2 c) Consider that the single linked list is already being created.
STEP 1: Start
STEP 2: Declare head, temp, trail as markers
STEP 3: [Check whether the linklist is empty. If it is empty, then print appropriate message.]
STEP 3: If head == NULL
Print ― Link list is empty‖
Goto Step
STEP 4: Else
STEP 5: Set Temp  head
STEP 6: Set head  head. Next
STEP 7: Delete Temp
STEP 8: Stop

Q. 3 a) Write an algorithm to perform all operations of Queue using Linked List. (Insert, Delete,
Peek and Traverse) [6 marks]
Ans 3 a)
Insertion operation on a linked queue is known as Enqueue. The Node structure will be as that
of a singly linked list. At the start of the insert operation, both Front and Rear will be NULL.

Enqueue() :

STEP 1: Start
STEP 2: Declare Front, Rear, New as markers and val as an integer
STEP 3: Allocate memory space for a New node
STEP 4: Set New. info  val
STEP 5: Set New. Next  NULL
[Checking the underflow condition. If the Queue is empty then the New node becomes the first
node of the linked queue and both Front and Rear points to New

STEP 6: If (Front == NULL AND Rear == NULL)

Set Front  Rear  New
Else [ Insertion is done with respect to Rear, so Rear is pointed to New]
Set Rear. Next  New
Set Rear  New
STEP 7: Stop

Deletion operation on a Linked Queue is known as Dequeue. The deletion is done with respect to
Front and hence, Rear will remain fixed and we will move the Front.
Dequeue():
STEP 1: Start
STEP 2: Declare Front, Rear, Temp as markers
STEP 3: If (Front == NULL AND Rear == NULL)
Print ― Queue Underflow‖
Goto Step 5
STEP 4: Else
Print Front. Info is deleted
Set Temp  Front
[If there is only a single node, then after deleting it, we have to bring both Front and Rear to NULL]
If (Front == Rear)
Set Front  Rear  NULL
Else
Set Front  Front. Next
STEP 5: Stop

Peek():
STEP 1: Start
STEP 2: Declare Front, Rear as markers
STEP 3: If (Front == NULL AND Rear == NULL)
Print ― Queue Underflow‖
Goto Step 4
Else
Print ―The first element in the queue is ", Front. Info
STEP 4: Stop

Traverse():
We have to check whether the Queue is empty or not. If it is empty then Print an appropriate
message else, traverse from Front to Rear.
STEP 1: Start
STEP 2: Declare Front, Rear and curr as markers
STEP 3: If (Front == NULL AND Rear == NULL)
Print ― Queue Underflow‖
Goto Step 5
STEP 4: Else
Set curr  Front
While(curr < > NULL)
Print curr. Info
Set curr  curr. Next
[End of While Loop]
STEP 5: Stop

Q. 3 b) Explain applications of Stack with suitable examples. [4 marks]

Ans 3 b) Stack is a linear data structure in which one end is closed. All the operations are performed
from the other open end, with the help of a marker called Top.
Applications of a Stack:

1. Expression Evaluation and Conversion: There are three types of expression that you use
in programming, they are:
a. Infix (Operand1 – Operator – Operand2): A + B
b. Prefix (Operator – Operand1 – Operand2): +AB
c. Postfix(Operand1 – Operand2 – Operator): AB+
Stack is used to evaluate and convert prefix, postfix & infix expressions.
2. Syntax Parsing : Since many programming languages are context-free languages, the stack
is used for syntax parsing by many compilers.
3. Backtracking : Backtracking is a recursive algorithm mechanism that is used to solve
optimization problems. It is also used in Game playing, finding paths, exhaustive searching.
4. Parenthesis Checking: Stack in data structures is used to check if the parentheses like ( ), {
} are valid or not in programming while matching opening and closing brackets are balanced or
not. So it stores all these parentheses in the stack and controls the flow of the program.
For e.g ((a + b) * (c + d)) is valid but {{a+b})) *(b+d}] is not valid.
5. String Reversal: Another exciting application of stack is string reversal. Each character of
a string gets stored in the stack. The string's first character is held at the bottom of the stack,
and the last character of the string is held at the top of the stack, resulting in a reversed string
after performing the pop operation.
6. Function Call: Whenever you call one function from another function in programming, the
reference of calling function stores in the stack. When the function call is terminated, the
program control moves back to the function call with the help of references stored in the stack.
So stack plays an important role when you call a function from another function.
7. Recursion
8. Used in "undo" mechanism in text editor.
9. Memory Management: Memory management is an essential feature of the operating
system, so the stack is heavily used to manage memory.

If the students have written half of it, then give them 2 marks. If the full list is provided without
the theory, you can give 3 to 4 marks based on the content written.
 Q. 3 c) Convert the given infix expression to postfix expression.
A + B * (C – D) / (E – F) [6 marks]
Ans 3 c)
Input Stack Postfix Sequence
A A
+ + A
B + AB
* +* AB
( +*( AB
C +*( ABC
- +*(- ABC
D +*(- ABCD
Since there is a closing ― ) ―, it will pop the ― – ―
operator from stack and add it to the Postfix Sequence.
) +* ABCD -
Next there is a ― / ― operator, which has same priority
with ― * ― operator. So we will pop the ― * ― operator
from the stack and add it to the Postfix Sequence. And
the push ― / ― operator onto the stack.
/ +/ ABCD - *
( +/( ABCD - *
E +/( ABCD - *E
- +/(- ABCD - *E
F +/(- ABCD - *EF
Since there is a closing ― ) ―, it will pop the ― – ―
operator from stack and add it to the Postfix Sequence.
) +/ ABCD - *EF -
Now since the end of input is reached, pop the
remaining operators from the stack in LIFO style and
add it to the Postfix Sequence.
End of Empty
ABCD - *EF - / +
input Stack

You can give students step marking. If they have solved the expression till ABCD – correctly, then
give 3 marks.
Q. 3 d) Explain advantages of Queue over Stack. [4 marks]
Ans 3 d) Advantages of Queue
1. Simplicity and Predictability: Queues operate on a simple and predictable First In, First
Out (FIFO) principle, which is easy to implement and understand.

2. Fairness: By processing elements in the order they arrive, queues ensure fairness in
systems like scheduling processes in an operating system or managing customers in
service industries.

3. Resource Sharing: Queues help manage resources efficiently in various applications,

such as print spooling and task scheduling, by maintaining a queue of tasks that await
processing.

4. Asynchronous Data Handling: Queues are excellent for handling data from
asynchronous processes, such as buffering inputs in I/O operations, where data can arrive
at any time and needs to be processed in the correct order.

5. Load Balancing: In distributed computing environments, queues can help in load

balancing by queuing tasks and distributing them evenly amongst multiple servers.
6. Breadth-first search in graphs.
7. A large amount of data can be managed efficiently with ease.
8. Queues can be used in the implementation of other data structures.

Q. 4 a) Create an AVL tree by inserting the values 48, 72, 36, 8, 79, 22, 84, 66. [6 marks]

Ans 4 a) AVL is a balanced Binary Search Tree, where every node contains an extra parameter,
called Balance Factor, where,

Balance Factor (k) = height (left(k)) - height (right(k))

Since it is the first element, it will n=be the Root 48 BF = 0

Since 72 > 48, it will be added to the right of 48. 48 BF = -1

72 BF = 0

Since 36 < 48, it will be added to the left of 48.

48 BF = 0

BF = 0 36 72 BF = 0

Since 8 < 48, it will be added to the left of 48.

Since 8 < 36, it will be added to the left of 36.

48 BF = 1

BF = 1 36 72 BF = 0

BF = 0 8
Since 79 > 48, it will be added to the right of 48.

Since 79 < 72, it will be added to the right of 72.

48 BF = 0

BF = 1 36 72 BF = -1

BF = 0 8 79 BF = 0

Since 22 < 48, it will be added to the left of 48.

Since 22 < 36, it will be added to the left of 36.

Since 22 > 8, it will be added to the right of 8.

48 BF = 1

BF = 2 36 72 BF = -1

BF = -1 8 79 BF = 0

BF = 0 22

A node has been inserted into the right subtree of the left subtree. This makes 36 an
unbalanced node. Hence we have to perform left-right rotation(LR). We first perform the left
rotation on the left subtree of 36. This makes 8, the left subtree of 22.

48 BF = 1

BF = 2 36 72 BF = -1

BF = 1 22 79 BF = 0

BF = 0 8

We shall now right-rotate the tree, making 22 the new root node of this subtree. 36 now
becomes the right subtree of its own left subtree.

48 BF = 1

BF = 0 22 72 BF = -1

BF = 0 8 36 79 BF = 0
BF = 0

Since 84 > 48, it will be added to the right of 48.

Since 84 < 72, it will be added to the right of 72.

Since 84 < 79, it will be added to the right of 79.

48 BF = -1

BF = 0 22 72 BF = -2

BF = 0 8 36 79 BF = -1
BF = 0
84 BF = 0
Here, after insertion of 84, node 72 has become unbalanced. So, we perform LL rotation, on
node 72, by which, node 79 will become the parent of 72 which will move to the left of 79 and
84 will become the right child.

48 BF = 0

BF = 0 22 79 BF = 0

BF = 0 8 36 72 84 BF = 0
BF = 0
Since 66 > 48, it will be added to the right of 48.

Since 66 < 79, it will be added to the left of 79.

Since 66 < 72, it will be added to the left of 72.

48 BF = -1

BF = 0 22 79 BF = 1

BF = 0 8 36 72 84 BF = 0
BF = 0 BF = 1

66 BF = 0

Please give step marking. The students must take 1 value at a time, place it properly depending on
the conditions and also mention the type of rotation performed. If the students have drawn the final
tree without the steps give 1 mark.

Q. 4 b) Draw a Binary Tree from the given traversal and print its preorder traversal. [4 marks]

Post-order: 4, 5, 2, 6, 3, 1

In-order: 4, 2, 5, 1, 3, 6

Ans 4 b) There are two rules to create a tree form the given post-order and in-order sequence:

Rule 1: Check the postorder sequence from Right to Left. It will give the root of the tree.

Rule 2: Check the position of the selected node from post-order. It will give the left and

right sub-trees.

Since the rightmost number in the post-order sequence is 1, hence the root of the Binary
Tree will be 1.

1 (Root)

In the in-order sequence, values 4,2,5 is at the left side and values 3, 6 are in the right side.

Hence, the binary tree will be

1 (Root)

4, 2, 5 3, 6
 Next value in the post-order sequence is 3. So, it will be connected to the right of node 1. And
after checking the in-order sequence, we found that 6 is to the right of 3. So the Binary Tree
will be:

1 (Root)

4, 2, 5 3

Next value in the post-order sequence is 6, which is already been added to the Binary Tree.

Next values in the post-order sequence is 2. And after checking the in-order sequence, we
found that 4 is to the left of 2 and 5 is to the right of 2. So the Binary Tree will be:

1 (Root)

2 3

4 5 6

The pre-order traversal is (Root – Left – Right ): 1, 2, 4, 5, 3, 6

If the students have drawn the final tree without the steps and the pre-order traversal, give 1 mark.

Q. 4 c) Apply the BFS algorithm to traverse the following graph. [6 marks]

Ans 4 c) For performing BFS on the given graph, a queue is used where the sequence of vertices are
inserted and depending upon the adjacent vertices, a vertex is added to the final BFS sequence. At the
start queue is empty. We perform the operations, till the queue becomes empty.

At start set the status of all the vertices = 1 (Ready state)

Let the starting vertex be ‗a‘. Its status = 1 (Ready state)

Queue = { } empty, front = rear = -1

Q[0] = a, Status of a = 2 (Waiting state), front = 0, rear = 0 Queue = {a}

Now insert the adjacent vertices of ‗a‘ in the Queue and set their status = 2.

Q[1] = c, status of c = 2, front = 0, rear = 1 Queue = {a, c}

Q[2] = d, status of d = 2, front = 0, rear = 2 Queue = {a, c, d}

Q[3] = e, status of e = 2, front = 0, rear = 3 Queue = {a, c, d, e}

Once all adjacent vertices of ‗a‘ in is the Queue, remove vertex ‗a‘ from the Queue, set its status = 3
(Processed) and update the BFS sequence.

BFS = {a}, status of ‘a’ = 3 Queue ={c, d, e}

Q[1] = c status of c = 2, front = 1, rear = 3 Queue ={c, d, e}

Now bring all the adjacent vertices of ‗c‘ in the queue and set their status = 2

The adjacent vertices of ‗c‘ are a, d, f. ‗a‘ is processed and ‗d‘ is already in Queue, so we will add ‗f‘
in the queue.

Q[4] = f, status of f= 2, front = 1, rear = 4 Queue ={c, d, e, f}

BFS = {a, c}, status of ‘c’ = 3, front = 2, rear = 4 Queue ={d, e, f}

Q[2] = d, status of d = 2, front = 2, rear = 4 Queue = {d, e, f. }

The adjacent vertices of ‗d‘ are a, c, b. ‗a‘ and ‗c‘ is processed hence ‗b‘ will be inserted in Queue

Q[5] = b, status of b = 2, front = 2, rear = 5 Queue = {d, e, f, b}

BFS = {a, c, d}, status of ‘d’ = 3, front = 3, rear = 5 Queue ={e, f, b}

The adjacent vertices of ‗e‘ are a, f, b. ‗a‘ is processed and ‗f‘ and ‗b‘ are already in the Queue.

BFS = {a, c, d, e}, status of ‘e’ = 3, front = 4, rear = 5 Queue = {f, b}

The adjacent vertices of ‗f‘ are c, e, b. ‗c‘ and ‗e‘ are processed and ‗b‘ is already in the Queue.

BFS = {a, c, d, e, f}, status of ‘f’ = 3, front = 5, rear = 5 Queue = {b}

Since both the adjacent vertices of ‗b‘ i.e., ‗e‘ and ‗f‘ are processed, add vertex ‗b‘ to BFS sequence
and Queue becomes empty again, and front and rear is assigned -1.

BFS = {a, c, d, e, f, b}, status of ‘b’ = 3, front = -1, rear = -1 Queue = { } empty.

In this question, it is expected that the students draw the Queue, every time a vertex is inserted in or
deleted from a Queue. Also check the sequence of alphabets, inserted in the Queue.

Q. 4 d) Construct step-by-step Binary Search Tree for the following data: [4 marks]

12, 10, 17, 14, 15, 9, 11, 19, 22, 20, 6.

Ans 4 d) Since the first value in the given sequence is 12, hence it will be taken as the Root of the
Binary Search Tree.

12 (Root)

10 => Since 10 < 12, it will move to the left of 12. 12

10

17 => Since 17 > 12, it will move to the right of 12.

 12

10 17

14 => Since 14 > 12, it will move to the right of 12.

Since 14 < 17, it will move to the left of 17. 12

10 17

14

15 => Since 15 > 12, it will move to the right of 12.

Since 15 < 17, it will move to the left of 17.
Since 15 > 14, it will move to the right of 14
12

10 17

14

15
9 => Since 9 < 12, it will move to the left of 12.
Since 9 < 10, it will move to the left of 10.
12

10 17

9 14

15
11 => Since 11 < 12, it will move to the left of 12.
Since 11 > 10, it will move to the right of 10.
12

10 17

9 11 14

15
19 => Since 19 > 12, it will move to the right of 12.

Since 19 > 17, it will move to the right of 17.

12

10 17

9 11 14 19

15
22 => Since 22 > 12, it will move to the right of 12.
Since 22 > 17, it will move to the right of 17.
Since 22 > 19, it will move to the right of 19.
12

10 17

9 11 14 19

15 22

20 => Since 20 > 12, it will move to the right of 12.

Since 20 > 17, it will move to the right of 17.
Since 20 > 19, it will move to the right of 19.
Since 20 < 22, it will move to the right of 19.
12

10 17

9 11 14 19

15 22

20

6 => Since 6 < 12, it will move to the left of 12.

Since 6 < 10, it will move to the left of 10.
Since 6 < 9, it will move to the left of 9.
12

10 17

9 11 14 19

6 15 22

20
If the students don‘t draw the tree stepwise, don‘t give any marks. 1 mark for the final tree without
steps. Give step marking.

Q. 5 a) Apply Binary Search algorithm for the following data: [ 6 marks]

88, 12, 14, 26, 31, 41, 53, 58, 71, where search key = 58

Ans 5 a) Since Binary Search method only works on a sorted array, first we have to sort the entire
array and then perform the search.
We can use any sorting mechanism to 1st sort the entire array. Let the given sequence be array A.

88 12 14 26 31 41 53 58 71
0 1 2 3 4 5 6 7 8

88 12 14 26 31 41 53 58 71
0 1 2 3 4 5 6 7 8

88 12 14 26 31 41 53 58 71
0 1 2 3 4 5 6 7 8

88 12 14 26 31 41 53 58 71
0 1 2 3 4 5 6 7 8

88 12 14 26 31 41 53 58 71
0 0 2 3 4 5 6 7 8

12 88 14 26 31 41 53 58 71
0 1 2 3 4 5 6 7 8

12 14 26 88 31 41 53 58 71
0 1 2 3 4 5 6 7 8

12 14 26 31 41 53 58 71 88 The array is sorted. Now we will apply the

0 1 2 3 4 5 6 7 8 Binary Search algorithm to search.

low mid high

While(low <= high) … 0 <= 8 True

mid = (low + high) / 2 … (0+8)/2 = 4

If (Key = = A[mid]) … 58 = = A[4] …58 = = 41 …False

low = mid + 1, 4 + 1 = 5

53 58 71 88
5 6 7 8

low mid high While(low <= high) ….5 <= 8 True

mid = (5 + 8)/2 = 13/2 = 6

If (Key = = A[mid]) … 58 = = A[6] …58 = = …True, 58 found at location 6.

The student has to perform sorting 1st. 3 marks is on sorting and 3 marks is on searching. If student
perform the binary search directly on unsorted array, then NO MARKS.

If a student directly writes the sorted array and then perform the algorithm correctly…4 marks.

Q. 5 b) Explain Hashing with example. [4 marks]

Ans 5 b) Consider following two scenarios :

SCENARIO 1:

There is a small company of 100 employees, each employer is assigned and EMP_ID in the range 0 –
99.

To store the records in an array, each employee‘s EMP_ID acts as an index into the array, where the
employee‘s record will be stored.

In this case we can directly access the record of any employee, once we know his EMP_ID.

But this scenario is not feasible.

SCENARIO 2:

Let us assume that the same company uses a 5-digit EMP_ID, as the primary key.

In this case value will range from 00000 – 99999.

We need an array of size, 100,000 of which only 100 elements will be used.

Here also we need a large storage space.

SOLUTION:

We can use the last 2 digits of the key to identify each employee. E.g., The employee with EMP_ID
88464, will be stored at the index 64. Similarly, the employee with EMP_ID 12456 can be stored at
the index 56.

Here the elements are not stored according to the value of the key. Here we need a way to convert a 5-
digit key number to a 2-digit array index.

We need a function which will do the transformation. This function is known as a HASH
FUNCTION, and the array in which it will store the key value is called a HASH TABLE.

HASH TABLE is a data structure in which keys are mapped to array position by a hash function.
Hence a value stored in the hash table can be searched in O(1) time using a hash function.

In a hash table, an element with key ‗k‘ is stored at index h(k) and not ‗k‘.

A hash function ‗h‘ is used to calculate the index at which the element with key ‗k‘ will be stored.

Thus the process of mapping the keys to appropriate locations or indices in a hash table is known as
HASHING.

When two or more keys map to the same memory location, a COLLISION is said to occur.

A hash function is simply a Mathematical formula which when applied to a key, produces an integer
which can be used as an index for the key in the hash table.

The main aim of a hash function is that the elements should be relatively, randomly, and universally
distributed. It produces a unique set of integers within some suitable range.
Hash functions are used to reduce the number of collisions.

In practice, there is no hash function that eliminates collision completely.

A good hash function can only minimize the number of collisions by spreading the elements
uniformly throughout the array.

There are four popular hash functions:

1. Division Method

2. Multiplication Method

3. Mid- Square Method

4. Folding Method

1. Division Method: It is the most simple method of hashing an integer ‘k’. It can be given as :
h( k ) = k % M…where ‘M’ can be any value.
Generally, we choose ‘M’ to be a large prime number. Because it increases the likelihood
that the keys are mapped with uniformity in the output range of values.
e.g., Calculate the hash values of the keys 2345 and 1267.
Let M = 97
h (2345) = 2345 % 97 = 17
h (1267) = 1267 % 97 = 06

2. Multiplication Method: The steps involved in the multiplication method are as follows:
Step 1: Choose a constant ‗A‘ such that 0 < A < 1.
Step 2: Multiply the key ‗k‘ by ‗A‘.
Step 3: Extract the fraction part of ‗kA‘.
Step 4: Multiply the result of Step 3 by ‗m‘ and take the floor.
hash function, h(k) = [ m * (kA mod 1) ], where kA mod 1 gives the fractional part of kA
and m is the size of hash table.

3. Mid Square Method: It is a good hash function which works in 2 steps:

Step 1: Square the value of the key.

Step 2: Extract the middle ‘x’ bits of the result obtained in step 1.

In this method same ‘x’ bits must be chosen for all keys.
e.g., Calculate the hash values of the keys 2345 and 1267. The hash table has 100 locations.
Note that since hash table has 100 locations, the indices vary from 0 to 99. This means only 2
digits are needed to map the key to a location in the hash table. So x = 2.
k1 = 2345 = 23452 = 5499025, h(k1) = 49 (2nd and 3rd bit from left are chosen).
k2 = 1267 = 12672 = 16,05,289, h(k2) = 60 (2nd and 3rd bit from left are chosen).

4. Folding Method: It works in following 2 steps:

Step 1: Divide the key into number of parts, where each part has same number of digits,
except the last part which may have lesser digits than the other parts.
Step 2: Add the individual parts. The hash value is produced by ignoring the last carry, if any.
The number of digits in each part depends on the size of the hash table.
If the hash table is of size 1000, then the indices will be from 0 to 999.
Hence each part of the key must have 3 digits.

If any two methods are discussed with the theory, then please give at least 75% marks.

Q. 5 c) Apply Quick Sort Algorithm to sort the given data: [6 marks]

 5, 4, 2, 3, 6, 10, 8, 11, 7

Ans. 5 c) We will take the first element of array as Pivot, P.

5 4 2 3 6 10 8 11 7
0 1 2 3 4 5 6 7 8
P
Now, select an element from Right to Left, which is smaller than 5. It is 3. Swap 5 and 3.

3 4 2 5 6 10 8 11 7
0 1 2 3 4 5 6 7 8
P

Now, select an element from Left to Right, which is larger than 5. There are no elements. Hence we
can say that ‗5‘ has reached to its required location and here we will divide the array in 3 parts.

Part 1 Part 2 Part 3

3 4 2 5 6 10 8 11 7
0 1 2 3 4 5 6 7 8
P

For Part 1, we will again select the 1st element as pivot, and select an element from Right to Left,
which is smaller than 3. It is 2. Swap 2 and 3.

2 3 4 5 6 10 8 11 7
0 2 1 3 4 5 6 7 8
P
Now, select an element from Left to Right, which is larger than 3. It is 4. Swap 4 and 3.

2 3 4 5 6 10 8 11 7
0 1 2 3 4 5 6 7 8
P

Hence, Part1 and Part2 is sorted.

For Part 3, we will select the element at location ‗4‘ as Pivot, i.e., 6.

2 3 4 5
6 10 8 11 7
0 1 2 3
4 5 6 7 8
P
Select an element from Right to Left, which is smaller than 6. There is none. So the array is now:

2 3 4 5 6 10 8 11 7
0 1 2 3 4 5 6 7 8
P

Part 4

For Part 4, we will select the element at location ‗5‘ as Pivot, i.e., 10. From Right to Left, select an
element less than 10. It is 7, so swap 7 and 10.

2 3 4 5 6 7
11 10 8
0 1 2 3 4 7 85 6
P
Now, select an element from Left to Right, which is larger than 10. It is 11, so swap 11 and 10.

2 3 4 5 6 7 8 10 11
0 1 2 3 4 5 6 7 8
P
We can see now, the array has been sorted. The final array is,

2 3 4 5 6 7 8 10 11
0 1 2 3 4 5 6 7 8
Give step marking.

Q. 5 d) Explain min heap and max heap with example. [4 marks]

Ans 5 d) Heap: A Heap is a complete binary tree with elements at every node being either less,
greater than or equal to the element at its left and the right child. All the levels of the tree except the
last level are completely filled.

There are two types of Binary heap:

1. Min Heap
2. Max Heap

1. Min Heap: A Min-Heap is a Data Structure with the following properties.

 It is a complete binary tree.
 The value of the root node must be the smallest among all its descendant nodes and the same
thing must be done for its left and right sub-tree.

Therefore, Min Heap stores the minimum value at the root of the heap. Min Heap is used to
maintain the minimum element in a collection of data.
For example…

Consider the sequence of numbers: 4, 5, 2, 6, 3, 1

4 => 4

5 => 4

2=> 4

5 2 Since 2 is less than 4, we perform heapify and swap 2 and 4.

5 4

6=> 2

5 4

3=>
2 Since 3 is less than 5, we perform heapify and swap 5 and 3.

5 4

6 3
 2 .

3 4

6 5

1=> 2

3 4

6 5 1 Since 1 is the smallest value, we will perform heapify twice,

and swap, 1 with 4 and then 1 with 2.

3 2

6 5 4

2. Max Heap: A Max-Heap is a Data Structure with the following properties.

 It is a complete binary tree.
 The value of the root node must be the largest among all its descendant nodes and the same
thing must be done for its left and right sub-tree.

Therefore, Max Heap stores the maximum value at the root of the heap.
For example…

Consider the sequence of numbers: 4, 5, 2, 6, 3, 1

4 => 4

5 => 4 Heapify and sway 4 and 5

2=> 5

4 2

6=> 5 Since 6 is the largest value, we will perform heapify twice, and
swap 6 with 4 and then 6 with 5
4 2

5 6

6 2 5 2

4 4
3 => 6

5 2

4 3

1=> 6

5 2

4 3 1