MODULE -2

1. Write any three applications of Stack.

 Function calls: Stacks are used to keep track of the return addresses of function
calls, allowing the program to return to the correct location after a function has
finished executing.
 Recursion: Stacks are used to store the local variables and return addresses of
recursive function calls, allowing the program to keep track of the current state
of the recursion.
 Expression evaluation: Stacks are used to evaluate expressions in postfix notation
(Reverse Polish Notation).
 Syntax parsing: Stacks are used to check the validity of syntax in programming
languages and other formal languages.
 Memory management: Stacks are used to allocate and manage memory in some
operating systems and programming languages.
Write any 3 applications for 3 Marks
2. Write any three applications of Queue.
 Task Scheduling: Queues can be used to schedule tasks based on priority or the
order in which they were received.
 Resource Allocation: Queues can be used to manage and allocate resources, such
as printers or CPU processing time.
 Batch Processing: Queues can be used to handle batch processing jobs, such as
data analysis or image rendering.
 Message Buffering: Queues can be used to buffer messages in communication
systems, such as message queues in messaging systems or buffers in computer
networks.
 Event Handling: Queues can be used to handle events in event-driven systems,
such as GUI applications or simulation systems.
 Traffic Management: Queues can be used to manage traffic flow in transportation
systems, such as airport control systems or road networks.
 Operating systems: Operating systems often use queues to manage processes and
resources. For example, a process scheduler might use a queue to manage the
order in which processes are executed.
 Network protocols: Network protocols like TCP and UDP use queues to manage
packets that are transmitted over the network. Queues can help to ensure that
packets are delivered in the correct order and at the appropriate rate.
 Printer queues :In printing systems, queues are used to manage the order in which
print jobs are processed. Jobs are added to the queue as they are submitted, and
the printer processes them in the order they were received.
 Web servers: Web servers use queues to manage incoming requests from clients.
Requests are added to the queue as they are received, and they are processed by
the server in the order they were received.
 Breadth-first search algorithm: The breadth-first search algorithm uses a queue
to explore nodes in a graph level-by-level. The algorithm starts at a given node,
adds its neighbors to the queue, and then processes each neighbor in turn.
Write any 3 applications for 3 Marks
3. Explain PUSH and POP operations in the stack.
The Last-In-First-Out (LIFO) concept is used by Stacks, a type of linear data structure.
It follows LIFO (Last In First Out) Principle. It only has one pointer, top pointer,
which points to the stack's topmost member. When an element is added to the stack, it is
always added to the top, and it can only be removed from the stack. To put it another
way, a stack is a container that allows insertion and deletion from the end known as the
stack's top.

Push Operation in Stack Data Structure:

Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.

Algorithm for Push Operation:

1. Before pushing the element to the stack, we check if the stack is full .
2. If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the
element to the stack.
3. Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is
inserted at top position .
4. The elements can be pushed into the stack till we reach the capacity of the stack.

Pop Operation in Stack Data Structure:

Removes an item from the stack. The items are popped in the reversed order in which
they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Algorithm for Pop Operation:

1. Before popping the element from the stack, we check if the stack is empty .
2. If the stack is empty (top == -1), then Stack Underflows and we cannot remove
any element from the stack.
3. Otherwise, we store the value at top, decrement the value of top by 1 (top = top
– 1) and return the stored top value.

4. Write an algorithm to insert an element to a circular queue using array.

The steps of enqueue operation are given below:

First, we will check whether the Queue is full or not.

Initially the front and rear are set to -1. When we insert the first element in a
Queue, front and rear both are set to 0.
When we insert a new element, the rear gets incremented, i.e., rear=rear+1.
Scenarios for inserting an element
There are two scenarios in which queue is not full:

If rear != max - 1, then rear will be incremented to mod(maxsize) and the new
value will be inserted at the rear end of the queue.
If front != 0 and rear = max - 1, it means that queue is not full, then set the value
of rear to 0 and insert the new element there.
There are two cases in which the element cannot be inserted:

When front ==0 && rear = max-1, which means that front is at the first position
of the Queue and rear is at the last position of the Queue.
front== rear + 1;

Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT = -1 and REAR = -1
 SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT
5. Write an algorithm to search an element using binary search. Discuss its
time complexity.
Step 1 - Read the search element from the user.
Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
Step 4 - If both are matched, then display "Given element is found!!!" and
terminate the function.
Step 5 - If both are not matched, then check whether the search element is
smaller or larger than the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3,
4 and 5 for the left sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4
and 5 for the right sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or
until sublist contains only one element.
Step 9 - If that element also doesn't match with the search element, then display
"Element is not found in the list!!!" and terminate the function.
Time Complexity of Binary Search Algorithm

The binary search algorithm works in logarithmic time complexity with constant space. Check
the binary search algorithm’s best, average and worst time complexity below.

Time Complexity of Binary Search Algorithm

Case Time Complexity

Best Case O(1)

Average Case O(logN)

Worst Case O(logN)

 The best-case complexity happens when our target element is found in the first
iteration, i,e. It is the first middle element. The best time complexity of the binary
search algorithm is O(1).
 The average time complexity of the binary search algorithm is O(logn).
 The worst time complexity occurs when our target element is the last. We keep
dividing until the last element is left, our target element. The worst time complexity of
the binary search algorithm is O(logn).

6. Find the postfix expressions of the following infix expression

a) (A+B)*K+D/(E+F*G)+H
 b) ((A/D+B)*(K^Y))

7. Given a matrix having 10 rows and 10 columns and 12 nonzero elements.

How much space can be saved by representing the matrix in sparse (tuple)
form?
Sparse matrices are those matrices that have the majority of their elements equal to zero. In other
words, the sparse matrix can be defined as the matrix that has a greater number of zero elements
than the non-zero elements.
Representing a sparse matrix by a 2D array leads to the wastage of lots of memory. This is because
zeroes in the matrix are of no use, so storing zeroes with non-zero elements is wastage of memory.
To avoid such wastage, we can store only non-zero elements. If we store only non-zero elements, it
reduces the traversal time and the storage space.

In 2D array representation of sparse matrix, there are three fields used that are named as -

o Row - It is the index of a row where a non-zero element is located in the matrix.
o Column - It is the index of the column where a non-zero element is located in the matrix.
o Value - It is the value of the non-zero element that is located at the index (row, column).
We can observe a 10x10 sparse matrix containing 12 non-zero elements. The above matrix
occupies 10x10 = 100 memory space. Therefore total number of nonzero elements=100-12=88
memory space.
In tuple form
number of rows=Nonzero element+1=12+1=13
number of columns =3
therefore space occupied in tuple=13x3=39 memory space

The memory is saved in tuple form=100-39= 61 memory space

8. What is Polish and Reverse polish notation? Give examples for each?
 9. Represent the polynomial P(X,Y)= 10X7Y7+5X6Y5+4X4Y2+8X2+25 using
array of structures.

To represent a multivariable polynomial involving x and y, we can use a tabular structure

where:

1. First row contains the coefficients of each term.

2. Second row contains the exponents of x in each term.
3. Third row contains the exponents of y in each term.

𝟏𝟎 𝟓 𝟒 𝟖 𝟐𝟓
[ 𝟕 𝟔 𝟒 𝟐 𝟎 ]
𝟕 𝟓 𝟐 𝟎 𝟎

10. Convert the expression A+B*C-D/E*H to postfix form. Show each step in
the conversion including the stack contents.
 11. What is DEQUEUE

The dequeue() is a data manipulation operation that is used to remove elements from the
queue.

12. Write the algorithm for inserting an element to a circular queue

13. Given an infix expression (A +B)^C-(D*C)/F, convert into its prefix form.

14. Write the algorithms for linear and binary search and compare their
performances.
Linear search Algorithm
int linear_search(int array[], int n, int x)
{

// Going through array sequencially

for (int i = 0; i < n; i++)
if (array[i] == x)
return i;
return -1;
}
Binary search Algorithm
int binarySearch(int array[], int x, int low, int high)
{
// Repeat until the pointers low and high meet each other

while (low <= high) {

int mid =( low + high ) / 2;
 if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

15. Write an algorithm to add two polynomials.

16. Evaluate the following expressions written in reverse polish notation.
Assume single digit operands and ^ represents exponentiation operator
i) 123*+42/^ ii) 63/45-*
17. Define the properties of circular queue. How will you check whether the
circular queue is
i) Full ii) Empty
The properties of Circular queue is

a) Fixed size
The size of a circular queue is determined when it's initialized and remains
fixed.
b) Circular nature
When the end of the array is reached, the queue wraps around to the beginning,
making use of all available space.
c) Efficient space utilization
Circular queues reuse vacated spaces to avoid wasting memory.
d) Two pointers
Circular queues use two pointers, front and rear, to keep track of the positions
for dequeuing and enqueuing operations.
e) First In First Out (FIFO) principle
Circular queues follow the FIFO principle, where items are added to the rear
and deleted from the front.
f) Circular link
The last node of a circular queue is connected to the first node by forming a
circular link, which is why it's also called a Ring Buffer.
g) Insertion and deletion
In a circular queue, insertion takes place at the rear pointer and deletion takes
place at the front pointer.
Condition for checking Circular Queue is full
if (rear + 1) % size == front
Condition for checking Circular Queue is empty
if ((rear ==-1)&&(front==-1))
18. Write an algorithm for deleting a node from a specified position in a
circular queue.
1. First, find the length of the list. That is, the number of nodes in the list.
2. Take two pointers previous and current to traverse the list. Such that
previous is one position behind the current node.
3. Take a variable count initialized to 0 to keep track of the number of nodes
traversed.
4. Traverse the list until the given index is reached.
5. Once the given index is reached, do previous->next = current->next.
19. Write a program of binary search which tells how many comparisons it did
to search an element given as user input.
Binary search Algorithm
int binarySearch(int array[], int x, int low, int high)
{
// Repeat until the pointers low and high meet each other

while (low <= high) {

 int mid =( low + high ) / 2;

if (array[mid] == x)
return mid;

if (array[mid] < x)
low = mid + 1;

else
high = mid - 1;
}

return -1;
}

To determine how many comparisons a binary search performs to find an element, we can
count the steps taken during the search process. Binary search works by dividing the search
range in half repeatedly, and in each step, it compares the target element with the middle
element of the current range.

The number of comparisons depends on:

1. The size of the array (nnn).

2. Whether the element exists in the array.

20. What is a double ended queue?

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion
and deletion operations are performed from both ends. We can say that deque is a generalized
version of the queue.
Though the insertion and deletion in a deque can be performed on both ends, it does not follow
the FIFO rule. The representation of a deque is given as follows –
Types of deque
There are two types of deque -

o Input restricted queue

o Output restricted queue
Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion
can be performed from both ends.
Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion
can be performed from both ends.

Operations performed on deque

There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear

21. What is a circular queue? How it is different from normal queue?

A Circular Queue is an extended version of a normal queue where the last
element of the queue is connected to the first element of the queue forming a
circle.
Write any 3 differences
22. Write an algorithm to reverse a string using stack.
Step 1. Creating an empty stack.

Step 2. Then pick the characters from the string one by one and put them to the
stack, so that the last character of the string comes at the top of the stack.

Step 3. pop the stack and put the popped characters back in the empty string.
23. What is sparse matrix? Write an algorithm to add two sparse matrices.
A sparse matrix is a matrix in which most of the elements are zero.
24. Discuss an algorithm to convert an infix expression to a postfix expression.
25. Write an algorithm to find the transpose of a matrix represented in tuple
form.