DS MAY 19

12 March 2023 10:54 AM

Searched ,Sorted & Merged By

@official_stranger

Q1 Solve any Two of the following.

(a) What is Data Structure? Explain the various
characteristics of an algorithm.

ANSWER:-

Data structure refers to a way of organizing and

storing data in a computer program or application
so that it can be accessed and used efficiently.
Data structures are an essential part of computer
science and programming and are used in various
areas, including database management systems,
operating systems, compilers, and many more.
There are several types of data structures,
including arrays, linked lists, stacks, queues, trees,
graphs, and hash tables. Each data structure has
its own advantages and disadvantages, and
choosing the right data structure depends on the
specific requirements of the program.
An algorithm is a set of instructions or steps that
are followed to solve a particular problem or
perform a specific task. The characteristics of an
algorithm include:
1. Input: An algorithm takes input data from the user
or from an external source.
DS MAY 19 STRANGER Page 1
1.
or from an external source.
2. Output: An algorithm produces output based on
the input and the processing it performs.
3. Definiteness: The steps of an algorithm must be
clear and unambiguous, with no room for
interpretation.
4. Finiteness: An algorithm must terminate after a
finite number of steps.
5. Effectiveness: Each step of an algorithm must be
executable and should result in a valid operation.
6. Generality: An algorithm should be general
enough to solve a variety of problems in the same
domain.
7. Efficiency: An algorithm should be designed to use
the least amount of resources possible, such as
time and memory, to solve the problem.
8. Optimality: An algorithm is said to be optimal if it
produces the best possible solution among all
possible solutions to a problem.

(a) What is time complexity? the frequency count for:

For I : =1 to n
For j : =i+1 to n
For k : =j+1 to n
For l : = k+1 to n
x = x + 1;

ANSWER:-

DS MAY 19 STRANGER Page 2

Time complexity refers to the measure of the
amount of time required to run an algorithm or a
piece of code as a function of its input size. It is
usually expressed in terms of the Big O notation,
which gives an upper bound on the growth rate of
the time taken as the input size increases.
For the given code snippet, the time complexity
can be calculated by analyzing the nested loops.
The outermost loop runs from i=1 to n, and for
each value of i, the inner loop runs from j=i+1 to n.
The second inner loop runs from k=j+1 to n, and
the third inner loop runs from l=k+1 to n. The x = x
+ 1 statement is executed inside the innermost
loop.
Therefore, the number of times the x = x + 1
statement is executed can be calculated as
follows:
∑_(i=1)^n ∑_(j=i+1)^n ∑_(k=j+1)^n ∑_(l=k+1)^n 1
This can be simplified as:
(n-3)C_4 = (n-3)!/(4!(n-7)!)
Therefore, the time complexity of the given code is
O((n-3)!/(4!(n-7)!)) or O(n^4), which means that the
time taken to execute the code increases
exponentially with the input size n.

(c) What is an algorithm? Write an algorithm to find

Greatest common divisor (GCD).

ANSWER:-

DS MAY 19 STRANGER Page 3

 An algorithm is a set of instructions or a step-by-
step procedure for solving a problem or performing
a task. It is a sequence of computational steps that
transform the input into the desired output.
Here is an algorithm to find the Greatest Common
Divisor (GCD) of two numbers:
Algorithm: GCD(a, b)
1. Set c = a mod b (where mod is the modulo
operator)
2. If c is zero, return b as the GCD
3. Otherwise, set a = b, b = c, and go to step 1
The above algorithm uses the Euclidean algorithm
to find the GCD of two numbers a and b. The
algorithm works by iteratively reducing the problem
of finding the GCD of a and b to the problem of
finding the GCD of b and c, where c is the
remainder when a is divided by b.
The algorithm continues this process until the
remainder c is zero, at which point b is the GCD of
the original numbers a and b.
Here is an example of how to use the algorithm to
find the GCD of 12 and 18:
GCD(12, 18)
Step 1: 18 mod 12 = 6, set a = 12, b = 6
Step 2: 12 mod 6 = 0, return 6 as the GCD
Therefore, the GCD of 12 and 18 is 6.

Q2 Solve the following.

(a) Write a "C" code to find the transpose of a sparse
matrix stored in this way.

DS MAY 19 STRANGER Page 4

ANSWER:-

#include <stdio.h>

void transpose(int row, int col, int num, int A[num][3],

int B[num][3])
{
int count[col], index[col];
int i, j, k;

// Initialize count array with zeros

for (i = 0; i < col; i++)
count[i] = 0;

// Count the number of non-zero elements in each

column
for (i = 0; i < num; i++)
count[A[i][1]]++;

// Compute the starting index of each column in the

transpose matrix
index[0] = 0;
for (i = 1; i < col; i++)
index[i] = index[i - 1] + count[i - 1];

// Compute the transpose matrix

for (i = 0; i < num; i++)
{
j = A[i][1]; // column of A[i]
k = index[j]; // starting index of column j in B
B[k][0] = A[i][1]; // row of B[k]
DS MAY 19 STRANGER Page 5
 B[k][0] = A[i][1]; // row of B[k]
B[k][1] = A[i][0]; // column of B[k]
B[k][2] = A[i][2]; // value of B[k]
index[j]++; // increment index for next element in
column j
}
}

int main()
{
int row, col, num, i, j;

printf("Enter the number of rows: ");

scanf("%d", &row);

printf("Enter the number of columns: ");

scanf("%d", &col);

printf("Enter the number of non-zero elements: ");

scanf("%d", &num);

int A[num][3], B[num][3];

printf("Enter the matrix in compressed row format

(row, column, value):\n");
for (i = 0; i < num; i++)
scanf("%d %d %d", &A[i][0], &A[i][1], &A[i][2]);

transpose(row, col, num, A, B);

printf("The transpose of the matrix in compressed

row format (row, column, value) is:\n");
DS MAY 19 STRANGER Page 6
row format (row, column, value) is:\n");
for (i = 0; i < num; i++)
printf("%d %d %d\n", B[i][0], B[i][1], B[i][2]);

return 0;
}

(b) Using linear probing insert the following values in

hash table of size 10. Elements are 28, 55, 71, 67, 11,
10, 90, 44,

ANSWER:-

Assuming the hash function is simply the modulo

operator % with a table size of 10, and linear
probing is used to handle collisions, here is how
the values can be inserted into the hash table:
Initial state:

Initial state:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | | | | | | | | | | |

Insert 28:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28| | | | | | | | | |

Insert 55:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 | | | | | | | | |
DS MAY 19 STRANGER Page 7
Element | 28|55 | | | | | | | | |

Insert 71:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 | | | | | | | |

Insert 67:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 |67 | | | | | | |

Insert 11:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 |67 |11 | | | | | |

Insert 10:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 |67 |11 |10 | | | | |

Insert 90:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 |67 |11 |10 |90 | | | |

Insert 44:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Element | 28|55 |71 |67 |11 |10 |90 |44 | | |

Note that for each insertion, if the computed index is

already occupied, linear probing is used to find the
next available index. In this case, we simply increment
the index by 1 until we find an empty slot or reach the
end of the table. In this example, no collisions occur.

DS MAY 19 STRANGER Page 8

 3. Solve the following.
(a) Explain sequential search, Write an algorithm for
sequential search.
ANSWER:-
Sequential search, also known as linear search, is
a method for finding a particular element in a list
by examining each element in order, starting from
the beginning of the list until the target element is
found or the end of the list is reached.
The algorithm works by comparing each element
of the list with the target element until a match is
found. If a match is found, the algorithm returns
the index of the element in the list. If no match is
found after examining all elements in the list, the
algorithm returns a value indicating that the target
element is not in the list.

The algorithm for sequential search is as follows:

4. Set a variable found to false
5. Set a variable index to 0
6. While found is false and index is less than the
length of the list: a. If the item at the current index
is equal to the target item: i. Set found to true b.
Else, increment index by 1
7. If found is true, return the index of the target item
8. If found is false, return -1 to indicate that the target
item was not found.

Sequential search has a time complexity of O(n), where

n is the length of the list, because in the worst case
DS MAY 19 STRANGER Page 9
n is the length of the list, because in the worst case
scenario, the algorithm must examine every element in
the list before determining that the target element is
not present. Despite its simplicity, sequential search
can be useful for small lists or lists that are not sorted.
However, for large lists or lists that are sorted, more
efficient search algorithms such as binary search or
hash tables may be more appropriate.

(b) What is skip list? Give its representation. Write an

algorithm to insert new item (k,e) in the skip list S

ANSWER:-

A skip list is a probabilistic data structure that

allows for efficient searching, insertion, and
deletion operations. It consists of a sorted linked
list with additional linked lists called "skip lists" that
allow for faster search operations.
The skip list is represented by a series of layers,
with the bottom layer being an ordinary linked list
containing all the elements in sorted order. Each
layer above the bottom layer is a sub-list of the
previous layer, and each element in a higher layer
appears in that layer with a certain probability. The
highest layer contains only a single element, which
is a sentinel node that marks the end of the list.
Each element in a skip list contains two fields: a
key field that holds the value of the element, and a
pointer field that points to the next element in the
list. In addition, each element in a higher layer also
has a pointer field that points to the next element
DS MAY 19 STRANGER Page 10
 has a pointer field that points to the next element
in the higher layer.
To insert a new item (k,e) into a skip list S, we can
use the following algorithm:
9. Traverse the skip list from the highest layer to the
bottom layer, searching for the appropriate
location to insert the new item. During this
traversal, maintain an array "update" that contains
the nodes that need to be updated when the new
item is inserted.
10. Once the appropriate location has been found,
check if the node at that location already contains
the key "k". If it does, then update the value of that
node to "e". Otherwise, proceed to step 3.
11. Generate a random number between 0 and 1. If
the number is less than or equal to a pre-
determined probability p, then insert a new node
with key "k" and value "e" at each layer up to a
new random layer. Otherwise, only insert the new
node at the bottom layer.
12. Update the pointers of the nodes in the "update"
array to point to the new node at each layer where
the new node was inserted.
By using skip lists, we can achieve logarithmic
time complexity for searching, insertion, and
deletion operations on average. The probability p
can be adjusted to balance the trade-off between
space and time complexity.

4. Solve the following.

(a) Write a program in C to create a singly linked list
and perform the following operations (1) Insert into list
DS MAY 19 STRANGER Page 11
and perform the following operations (1) Insert into list
(2) search for data Delete from list.

ANSWER:-

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

struct Node* head = NULL;

// Insert a new node at the beginning of the list

void insert(int data) {
struct Node* new_node = (struct Node*)
malloc(sizeof(struct Node));
new_node->data = data;
new_node->next = head;
head = new_node;
printf("%d inserted into list.\n", data);
}

// Search for a node with the given data

void search(int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
printf("%d found in list.\n", data);
DS MAY 19 STRANGER Page 12
 printf("%d found in list.\n", data);
return;
}
current = current->next;
}
printf("%d not found in list.\n", data);
}

// Delete the first occurrence of a node with the given

data
void delete(int data) {
struct Node* current = head;
struct Node* prev = NULL;
while (current != NULL) {
if (current->data == data) {
if (prev == NULL) {
// Node to be deleted is the first node
head = current->next;
} else {
// Node to be deleted is not the first node
prev->next = current->next;
}
free(current);
printf("%d deleted from list.\n", data);
return;
}
prev = current;
current = current->next;
}
printf("%d not found in list.\n", data);
}

DS MAY 19 STRANGER Page 13

int main() {
int choice, data;
while (1) {
printf("1. Insert into list\n");
printf("2. Search for data\n");
printf("3. Delete from list\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
insert(data);
break;
case 2:
printf("Enter data to search: ");
scanf("%d", &data);
search(data);
break;
case 3:
printf("Enter data to delete: ");
scanf("%d", &data);
delete(data);
break;
case 4:
exit(0);
default:
printf("Invalid choice.\n");
}
}
DS MAY 19 STRANGER Page 14
 }
return 0;
}

(b) Construction algorithm for following operations on

a Doubly linked List
(1) CREATE AT END (2) DELETE AT START (3) TRAVERSE

ANSWER:-

Here is a construction algorithm for the following

operations on a doubly linked list:
(1) CREATE AT END:
13. Initialize a new node with the given data and
pointers to the previous and next nodes, setting
both to NULL.
14. If the list is empty (i.e. head is NULL), set the head
to the new node.
15. Otherwise, traverse the list to find the last node
and set its next pointer to the new node, and set
the new node's prev pointer to the last node.
16. Display a message indicating that the node has
been created.
(2) DELETE AT START:
17. If the list is empty (i.e. head is NULL), display a
message indicating that the list is empty and
return.
18. Otherwise, set a temporary node pointer to the
head of the list.
19. If the list contains only one node, set the head to
NULL.
DS MAY 19 STRANGER Page 15
19.
NULL.
20. Otherwise, set the next pointer of the second node
to NULL, and set the head to point to the second
node.
21. Free the memory allocated for the temporary node
pointer.
22. Display a message indicating that the node has
been deleted.
(3) TRAVERSE:
23. If the list is empty (i.e. head is NULL), display a
message indicating that the list is empty and
return.
24. Otherwise, set a temporary node pointer to the
head of the list.
25. Traverse the list, displaying the data of each node
and setting the temporary node pointer to the next
node.
26. Repeat step 3 until the temporary node pointer is
NULL.

5. Solve the following.

(a) With the help of suitable example, explain following
operation, Enqueue and Dequeue and traverse
operation of circular queue.

ANSWER:-

A circular queue is a data structure that behaves

like a regular queue, except that the rear end of
the queue is connected to the front end, forming a
circle. This allows elements to be efficiently
DS MAY 19 STRANGER Page 16
 circle. This allows elements to be efficiently
inserted and removed from the queue in a circular
manner. The enqueue and dequeue operations
work similarly to those of a regular queue, with the
exception that the queue is circular.
Let's consider an example of a circular queue of
size 5. Initially, the queue is empty and all pointers
point to -1.

Front = -1, Rear = -1

27. Enqueue: We add elements to the queue by

incrementing the rear pointer and adding the
element to that index. Suppose we want to add the
elements 10, 20, 30, 40, and 50 in that order.

10 | - | - | - | - |
Front = 0, Rear = 0

10 | 20 | - | - | - |
Front = 0, Rear = 1

10 | 20 | 30 | - | - |
Front = 0, Rear = 2

10 | 20 | 30 | 40 | - |
Front = 0, Rear = 3

10 | 20 | 30 | 40 | 50 |
Front = 0, Rear = 4

28. Dequeue: We remove elements from the queue by

DS MAY 19 STRANGER Page 17
28. Dequeue: We remove elements from the queue by
incrementing the front pointer and returning the
element at that index. Suppose we dequeue two
elements.

- | 20 | 30 | 40 | 50 |
Front = 1, Rear = 4

- | - | 30 | 40 | 50 |
Front = 2, Rear = 4

29. Traverse: To traverse the circular queue, we can

start from the front index and iterate through the
elements until we reach the rear index. For
example, if we want to print the elements of the
queue in order, we can do the following:

for (int i = front; i <= rear; i = (i + 1) % size) {

printf("%d ", queue[i]);
}
This will output:

30 40 50

Note that the % operator is used to wrap around to

the front of the queue when we reach the end of the
circular buffer. This allows us to efficiently traverse the
queue without having to copy elements to a new
buffer.

(b) Convert the A*B+C/D expression into postfix using

DS MAY 19 STRANGER Page 18
 (b) Convert the A*B+C/D expression into postfix using
stack.

ANSWER:-

To convert the infix expression A*B+C/D to postfix

using a stack, we can follow the following steps:
30. Create an empty stack and an empty output string.
31. Iterate through each symbol in the infix expression
from left to right.
32. If the symbol is an operand (i.e., a letter or a
number), add it to the output string.
33. If the symbol is an operator (+, -, *, /), pop all
operators from the stack that have higher or equal
precedence than the current operator, and append
them to the output string. Then push the current
operator onto the stack.
34. If the symbol is an opening parenthesis, push it
onto the stack.
35. If the symbol is a closing parenthesis, pop
operators from the stack and append them to the
output string until an opening parenthesis is
encountered. Discard the opening and closing
parentheses.
36. After all symbols have been processed, pop any
remaining operators from the stack and append
them to the output string.
Using this algorithm, we can convert the infix
expression A*B+C/D to the postfix expression
AB*CD/+.
Here is a step-by-step explanation of the
conversion process:

Symbol Stack Output

DS MAY 19 STRANGER Page 19
Symbol Stack Output
A A
* * A
B * AB
+ + AB*
C + AB*
/ / AB*C+
D / AB*C+D
AB*C+D

Therefore, the postfix expression of A*B+C/D is

AB*C+D/.

6.Solve the following.

(a) Explain breadth first search technique for graph
traversal.

ANSWER:-

Breadth-First Search (BFS) is a graph traversal

technique that visits all the vertices of a graph in
breadth-first order, i.e., it visits all the vertices at
the same level before moving to the vertices at the
next level.
The algorithm starts at a source vertex and
explores all the vertices at the same level before
moving on to the next level. To achieve this, BFS
uses a queue to store the vertices that have been
visited but whose neighbors have not been
DS MAY 19 STRANGER Page 20
 visited but whose neighbors have not been
explored yet.
Here is the step-by-step process for BFS:
37. Initialize a queue and add the source vertex to it.
38. Mark the source vertex as visited.
39. While the queue is not empty, do the following:
• Dequeue the next vertex from the queue.
• Visit the vertex.
• For each neighbor of the vertex, if it has not been
visited yet, mark it as visited and enqueue it.
40. Repeat step 3 until the queue is empty.
The BFS algorithm visits all the vertices of the
graph in the order of their distance from the source
vertex. That is, it visits all the vertices at a distance
of 1 from the source vertex first, then all the
vertices at a distance of 2, and so on.
BFS can be used to find the shortest path between
two vertices in an unweighted graph, as the
algorithm guarantees that it visits all the vertices at
a certain distance from the source vertex before
moving on to the vertices at the next distance
level.
For example, consider the following undirected
graph:

1--2--3
/ | |
4 5--6

Starting from vertex 1, the BFS algorithm will visit the

vertices in the following order: 1, 2, 4, 3, 5, 6. The
queue will contain the following vertices at each step:

Step 1: queue = [1]

DS MAY 19 STRANGER Page 21
Step 1: queue = [1]
Step 2: queue = [2, 4]
Step 3: queue = [4, 3, 5]
Step 4: queue = [3, 5, 6]
Step 5: queue = [5, 6]
Step 6: queue = [6]

Therefore, the BFS algorithm will visit all the vertices of

the graph in breadth-first order, starting from vertex 1.

(b) What is Binary Tree. Explain inorder and postorder

traversals with example.

ANSWER:-

A binary tree is a data structure where each node

has at most two children, which are referred to as
the left child and the right child. Each node in a
binary tree can have up to two children, but it can
also have zero or one child if it is a leaf node or a
parent node with only one child.
Inorder and postorder traversals are two methods
used to traverse a binary tree.
Inorder traversal of a binary tree means visiting all
the nodes in the tree in the order of left subtree,
root, and right subtree. In other words, we first visit
the left subtree, then the root, and finally the right
subtree.
Here is an example of inorder traversal of a binary
tree:

1
DS MAY 19 STRANGER Page 22
 1
/ \
2 3
/\ /\
4 56 7

The inorder traversal of this binary tree is: 4, 2, 5,

1, 6, 3, 7.
Postorder traversal of a binary tree means visiting
all the nodes in the tree in the order of left subtree,
right subtree, and root. In other words, we first visit
the left subtree, then the right subtree, and finally
the root.
Here is an example of postorder traversal of a
binary tree:

1
/ \
2 3
/\ /\
4 56 7

The postorder traversal of this binary tree is: 4, 5,

2, 6, 7, 3, 1.
In inorder traversal, we visit the left subtree first,
so we visit the leftmost node in the tree, which is 4.
Then we visit its parent node, which is 2, and then
we visit the right child of 2, which is 5. After that,
we visit the root node, which is 1, and then we visit
its right child, which is 3. Finally, we visit the
rightmost subtree, which is rooted at 7.
In postorder traversal, we visit the left subtree first,
so we visit the leftmost node in the tree, which is 4.
Then we visit its right sibling, which is 5, and then
DS MAY 19 STRANGER Page 23
Then we visit its right sibling, which is 5, and then
we visit their parent node, which is 2. After that, we
visit the left child of 2, which is 6, and then we visit
its right sibling, which is 7. Finally, we visit the root
node, which is 1.

DS MAY 19 STRANGER Page 24