1

Q1) a) Write pseudo ‘Python’ algorithm (recursive) for binary search. Apply your
algorithm on the following numbers stored in array from A[0] to A[10] 9, 17,
23,38,45,50,57,76,90,100 to search numbers 10 & 100.[9]
Ans:- Here is a pseudo 'Python' algorithm for binary search:
def binary_search(arr, low, high, target):
if high >= low:
mid = (low + high) // 2

if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, low, mid - 1, target)
else:
return binary_search(arr, mid + 1, high, target)
else:
return -1

# Example usage
arr = [9, 17, 23, 38, 45, 50, 57, 76, 90, 100]
target1 = 10
target2 = 100

result1 = binary_search(arr, 0, len(arr) - 1, target1)

result2 = binary_search(arr, 0, len(arr) - 1, target2)

print("Index of", target1, "in the array:", result1)

print("Index of", target2, "in the array:", result2)

In this algorithm, the binary_search function takes an array arr, the lower index low, the higher
index high, and the target value target. It recursively divides the array in half and checks if the middle
element is equal to the target. If it is, the function returns the index of the middle element. If the middle
element is greater than the target, the function recursively calls itself on the left half of the array. If the
middle element is less than the target, the function recursively calls itself on the right half of the array. If
the target is not found, the function returns -1.
In the example usage, the algorithm is applied to the array [9, 17, 23, 38, 45, 50, 57, 76, 90, 100] to
search for the numbers 10 and 100. The results are printed, showing the index of each target in the
array.

b) Explain the quick sort algorithm. Show the contents of array a er every
iter on of your algorithm start from following status of array.- 27, 76, 17, 9, 57,
90, 45, 100, 79. [9]
Ans:- QuickSort is a popular sor ng algorithm that follows the divide-and-conquer paradigm. It works by
selec ng a "pivot" element from the array and par oning the other elements into two sub-arrays
2

according to whether they are less than or greater than the pivot. The sub-arrays are then sorted
recursively.

Here's a step-by-step explana on of the QuickSort algorithm applied to the given array [27, 76, 17, 9, 57,
90, 45, 100, 79]:

1. **Ini al array:** [27, 76, 17, 9, 57, 90, 45, 100, 79]

2. **First Itera on:**

- Choose a pivot (e.g., the last element): 79 (pivot index = 8)

- Par on the array into two sub-arrays: [27, 17, 9, 57, 45] (elements less than 79) and [76, 90, 100, 79]
(elements greater than 79).

- The pivot is now in its sorted posi on.

- Recursive calls are made on the two sub-arrays.

**Array a er the first itera on:** [27, 17, 9, 57, 45, 79, 76, 90, 100]

3. **Second Itera on (Le Sub-array):**

- Choose a pivot: 45 (pivot index = 4)

- Par on the le sub-array into two sub-arrays: [27, 17, 9] (elements less than 45) and [57, 45]
(elements greater than 45).

- Recursive calls are made on the two sub-arrays.

**Array a er the second itera on (Le Sub-array):** [9, 17, 27, 45, 57, 79, 76, 90, 100]

4. **Third Itera on (Le Sub-array):**

- Choose a pivot: 27 (pivot index = 2)

- Par on the le sub-array into two sub-arrays: [9, 17] (elements less than 27) and [27] (element
greater than 27).

- Recursive calls are made on the two sub-arrays.

**Array a er the third itera on (Le Sub-array):** [9, 17, 27, 45, 57, 79, 76, 90, 100]

- The le sub-array is now sorted.

5. **Third Itera on (Right Sub-array):**

- Choose a pivot: 90 (pivot index = 6)

- Par on the right sub-array into two sub-arrays: [79, 76] (elements less than 90) and [90, 100]
(elements greater than 90).

- Recursive calls are made on the two sub-arrays.

**Array a er the third itera on (Right Sub-array):** [9, 17, 27, 45, 57, 76, 79, 90, 100]
3

- The right sub-array is now sorted

6. **The recursion con nues un l all sub-arrays are sorted.**

The final sorted array is: [9, 17, 27, 45, 57, 76, 79, 90, 100]

Q2) a) Explain in brief the different searching techniques. What is the me

complexity of each of them? [9]
Ans:- There are several searching techniques used to find the presence or loca on of an element in a
collec on of data. Here is a brief explana on of some common searching techniques along with their
me complexi es:

1. **Linear Search:**In linear search, each element in the collec on is sequen ally checked un l a
match is found or the en re collec on has been traversed.

- **Time Complexity:** O(n) - Linear me complexity, where 'n' is the number of elements in the
collec on.

2. **Binary Search:**Binary search is applicable to sorted collec ons. It repeatedly divides the search
interval in half un l the target element is found or the interval becomes empty.

- **Time Complexity:** O(log n) - Logarithmic me complexity, where 'n' is the number of elements in
the collec on.

3. **Hashing (Hash Table):**Hashing involves the use of a hash func on to map keys to indices in a data
structure (hash table). It allows for constant- me average-case search complexity.

- **Time Complexity:** O(1) - Constant me on average, but worst-case complexity depends on the
quality of the hash func on and poten al collisions.

4. **Jump Search:-Jump search is similar to binary search but divides the array into smaller blocks and
performs a linear search within each block.

- **Time Complexity:** O(√n) - Square root me complexity, where 'n' is the number of elements in
the collec on.

5. **Interpola on Search:-Interpola on search is an improvement over binary search, especially for

uniformly distributed data. It es mates the posi on of the target element based on the value of the key.

- **Time Complexity:** O(log log n) on average for uniformly distributed data, but it can be O(n) in the
worst case.

6. **Exponen al Search:**Exponen al search involves searching by repeatedly doubling the index un l

a range is found in which the target element may exist, followed by a binary search in that range.

- **Time Complexity:** O(log n) - Logarithmic me complexity, but may perform be er than binary
search in some scenarios.
4

7. **Fibonacci Search:**Fibonacci search is a modifica on of binary search that uses Fibonacci numbers
to divide the array into smaller segments.

- **Time Complexity:** O(log n) - Logarithmic me complexity.

8. **Ternary Search:**Ternary search is a divide-and-conquer algorithm that works similar to binary

search but divides the array into three parts instead of two.

- **Time Complexity:** O(log3 n) - Logarithmic me complexity.

9. **Linear Probing (in Hashing):**Linear probing is a collision resolu on technique in hash tables. If a
collision occurs, it searches for the next available slot linearly un l an empty slot is found.

- **Time Complexity:** O(n) in the worst case if the table is nearly full, but can be efficient in prac ce
with good hash func ons.

b) Write an algorithm of selec on sort and sort the following numbers using
selec on sort and show the contents of an array a er every pass:- 81, 5, 27, –6,
61, 93, 4, 8, 104, 15 [9]
Ans:- Selec on Sort is a simple sor ng algorithm that repeatedly selects the minimum element from the
unsorted part of the array and swaps it with the first unsorted element. Here's the algorithm for
Selec on Sort:

Selec on Sort Algorithm:

procedure selec onSort(arr):

n = length(arr)

for i from 0 to n-2:

minIndex = i

for j from i+1 to n-1:

if arr[j] < arr[minIndex]:

minIndex = j

swap(arr, i, minIndex)

procedure swap(arr, i, j):

temp = arr[i]

arr[i] = arr[j]

arr[j] = temp

Now, let's apply the selec on sort algorithm to the given array [81, 5, 27, -6, 61, 93, 4, 8, 104, 15] and
show the contents of the array a er every pass:
5

Pass-wise Sor ng:

1. **Pass 1:** Select the minimum element from the en re array and swap it with the first element.

Array: [ -6, 5, 27, 81, 61, 93, 4, 8, 104, 15]

2. **Pass 2:** Select the minimum element from the unsorted part (excluding the first element) and
swap it with the second element.

Array: [ -6, 4, 27, 81, 61, 93, 5, 8, 104, 15]

3. **Pass 3:** Con nue this process un l the en re array is sorted.

Array: [ -6, 4, 5, 81, 61, 93, 27, 8, 104, 15]

Array: [ -6, 4, 5, 8, 61, 93, 27, 81, 104, 15]

Array: [ -6, 4, 5, 8, 15, 93, 27, 81, 104, 61

... Con nue un l the en re array is sorted.

Final Sorted Array:

Array: [ -6, 4, 5, 8, 15, 27, 61, 81, 93, 104]

The array is now sorted in ascending order using the selec on sort algorithm.

Q3) a) What is linked list? Write a pseudo C++ code to sort the elements. [9]
Ans:- A linked list is a data structure in which elements, called nodes, are connected through pointers.
Each node contains data and a reference (or link) to the next node in the sequence. Linked lists can be
singly linked, where nodes only have a link to the next node, or doubly linked, where nodes have links to
both the next and previous nodes.

Here's a pseudo C++ code to sort the elements of a singly linked list. This code uses the Bubble Sort
algorithm for simplicity, but other sor ng algorithms can be applied as needed.

#include <iostream>

// Node structure for a singly linked list

struct Node {

int data;

Node* next;

Node(int val) : data(val), next(nullptr) {}

};

// Func on to print the linked list

void printList(Node* head) {

6

while (head != nullptr) {

std::cout << head->data << " ";

head = head->next;

std::cout << std::endl;

// Func on to perform bubble sort on a linked list

void bubbleSortLinkedList(Node* head) {

if (head == nullptr || head->next == nullptr) {

return; // Empty or single-node list is already sorted

Node* current;

Node* nextNode;

bool swapped;

do {

swapped = false;

current = head;

nextNode = head->next;

while (nextNode != nullptr) {

if (current->data > nextNode->data) {

// Swap data

int temp = current->data;

current->data = nextNode->data;

nextNode->data = temp;

swapped = true;

// Move to the next pair of nodes

current = nextNode;

nextNode = nextNode->next;
7

} while (swapped);

int main() {

// Crea ng a linked list

Node* head = new Node(3);

head->next = new Node(1);

head->next->next = new Node(4);

head->next->next->next = new Node(2);

std::cout << "Original linked list: ";

printList(head);

// Sor ng the linked list

bubbleSortLinkedList(head);

std::cout << "Sorted linked list: ";

printList(head);

return 0;

Explana on:

- The `Node` struct represents a node in the linked list, containing data and a pointer to the next node.

- The `printList` func on prints the elements of the linked list.

- The `bubbleSortLinkedList` func on uses the Bubble Sort algorithm to sort the linked list.

- In the `main` func on, a linked list is created, printed, and then sorted using the `bubbleSortLinkedList`
func on.

b) What is doubly linked list? Explain the process of dele on of an element from
doubly linked list with example. [9]
Ans:- A doubly linked list is a type of linked list in which each node contains data and two pointers: one
poin ng to the next node in the sequence (similar to a singly linked list), and another poin ng to the
previous node. This bidirec onal linking allows for easier traversal in both direc ons.

The process of dele on from a doubly linked list involves upda ng the pointers of the adjacent nodes to
bypass the node being deleted. Here's an explana on of the dele on process with an example:
8

Doubly Linked List Dele on Process:

1. **Iden fy the Node to Delete:**

- Locate the node to be deleted based on the value or posi on in the doubly linked list.

2. **Update Pointers:**

- Adjust the pointers of the previous and next nodes to bypass the node being deleted.

3. **Free Memory:**

- Deallocate the memory occupied by the node being deleted.

Example:

Consider the following doubly linked list:

NULL <-> 3 <-> 8 <-> 12 <-> 5 <-> 10 <-> NULL

Let's say we want to delete the node with the value `5`.

1. **Iden fy the Node to Delete:**

- Traverse the list to find the node with the value `5`.

2. **Update Pointers:**

- Adjust the pointers of the previous and next nodes to bypass the node with the value `5`.

NULL <-> 3 <-> 8 <-> 12 <----------> 10 <-> NULL

|__ Deleted Node (5)

3. **Free Memory:**

- Deallocate the memory occupied by the node with the value `5`.

NULL <-> 3 <-> 8 <-> 12 <-> 10 <-> NULL

Pseudo Code for Dele on:

Here's a simplified pseudo code for dele ng a node from a doubly linked list:

func on deleteNode(doublyLinkedList, valueToDelete):

current = doublyLinkedList.head

while current is not NULL and current.data is not valueToDelete:

current = current.next

if current is NULL:

print("Node not found.")

return
9

# Update pointers to bypass the node

if current.prev is not NULL:

current.prev.next = current.next

else:

# If the node is the head, update the head

doublyLinkedList.head = current.next

if current.next is not NULL:

current.next.prev = current.prev

# Free memory

free(current)

Note: This is a generic example, and in a real implementa on, you may need to consider edge cases (e.g.,
dele ng the head or tail of the list) and handle memory dealloca on appropriately.

Q4) a) Explain Generalized Linked List with example. [9]

Ans:- A Generalized Linked List is a linked list in which each node can contain different types of data.
Unlike a tradi onal linked list where each node holds a single element, a generalized linked list allows
each node to store a structure that includes various data types. This flexibility makes it suitable for
represen ng different kinds of data in a single linked list.

Example:

Let's consider a generalized linked list that represents informa on about students, where each node
contains details such as the student's name, roll number, and a list of courses they are enrolled in.

Node 1:

- Name: Alice

- Roll Number: 101

- Courses: [Math, English, History]

Node 2:

- Name: Bob

- Roll Number: 102

- Courses: [Physics, Chemistry, Biology]

Node 3:

- Name: Carol
10

- Roll Number: 103

- Courses: [Computer Science, Economics]

In this example, each node in the generalized linked list represents a student. The data stored in each
node is not limited to a single value; it includes a combina on of different data types, such as strings (for
names), integers (for roll numbers), and lists (for courses).

### Pseudo Code:

Here's a simplified pseudo code to illustrate the concept of a generalized linked list:

struct CourseNode {

string courseName;

CourseNode* nextCourse;

};

struct StudentNode {

string name;

int rollNumber;

CourseNode* courses;

StudentNode* nextStudent;

};

class GeneralizedLinkedList {

public:

StudentNode* head;

GeneralizedLinkedList() {

head = nullptr;

void addStudent(string name, int rollNumber, vector<string> courseNames) {

StudentNode* newStudent = new StudentNode;

newStudent->name = name;

newStudent->rollNumber = rollNumber;

newStudent->courses = nullptr;

// Add courses to the courses linked list

11

for (const string& courseName : courseNames) {

CourseNode* newCourse = new CourseNode;

newCourse->courseName = courseName;

newCourse->nextCourse = newStudent->courses;

newStudent->courses = newCourse;

// Add the new student to the students linked list

newStudent->nextStudent = head;

head = newStudent;

};

In this pseudo code, `GeneralizedLinkedList` contains a linked list of students, and each `StudentNode`
has a linked list of courses (`CourseNode`). This structure allows for flexibility in represen ng different
types of data within a single linked list.

b) Write Pseudo C++ code for addi on of two polynomials using singly linked
list.
And:- Certainly! Below is a pseudo C++ code for the addi on of two polynomials using singly linked lists:

#include <iostream>

using namespace std;

// Node structure for a term in the polynomial

struct TermNode {

int coefficient;

int exponent;

TermNode* next;

TermNode(int coef, int exp) : coefficient(coef), exponent(exp), next(nullptr) {}

};

// Func on to add two polynomials represented as linked lists

TermNode* addPolynomials(TermNode* poly1, TermNode* poly2) {

12

TermNode* resultHead = nullptr;

TermNode* resultTail = nullptr;

while (poly1 != nullptr || poly2 != nullptr) {

// Create a new term for the result

TermNode* resultTerm = new TermNode(0, 0);

resultTerm->next = nullptr;

// Compare exponents of the current terms in poly1 and poly2

if (poly1 != nullptr && (poly2 == nullptr || poly1->exponent > poly2->exponent)) {

resultTerm->coefficient = poly1->coefficient;

resultTerm->exponent = poly1->exponent;

poly1 = poly1->next;

} else if (poly2 != nullptr && (poly1 == nullptr || poly1->exponent < poly2->exponent)) {

resultTerm->coefficient = poly2->coefficient;

resultTerm->exponent = poly2->exponent;

poly2 = poly2->next;

} else {

// Add coefficients if exponents are equal

resultTerm->coefficient = poly1->coefficient + poly2->coefficient;

resultTerm->exponent = poly1->exponent;

poly1 = poly1->next;

poly2 = poly2->next;

// A ach the result term to the result polynomial

if (resultHead == nullptr) {

resultHead = resultTerm;

resultTail = resultTerm;

} else {

resultTail->next = resultTerm;

resultTail = resultTerm;
13

return resultHead;

// Func on to print a polynomial

void printPolynomial(TermNode* poly) {

while (poly != nullptr) {

cout << poly->coefficient << "x^" << poly->exponent;

if (poly->next != nullptr) {

cout << " + ";

poly = poly->next;

cout << endl;

// Func on to insert a term into a polynomial

void insertTerm(TermNode*& poly, int coef, int exp) {

TermNode* newTerm = new TermNode(coef, exp);

newTerm->next = poly;

poly = newTerm;

int main() {

// Polynomial 1: 2x^3 + 3x^2 + 4x^1

TermNode* poly1 = nullptr;

insertTerm(poly1, 2, 3);

insertTerm(poly1, 3, 2);

insertTerm(poly1, 4, 1);

// Polynomial 2: 1x^3 + 2x^2 + 3x^1

TermNode* poly2 = nullptr;

14

insertTerm(poly2, 1, 3);

insertTerm(poly2, 2, 2);

insertTerm(poly2, 3, 1);

cout << "Polynomial 1: ";

printPolynomial(poly1);

cout << "Polynomial 2: ";

printPolynomial(poly2);

TermNode* result = addPolynomials(poly1, poly2);

cout << "Sum of Polynomials: ";

printPolynomial(result);

return 0;

This code defines a `TermNode` structure represen ng a term in the polynomial and provides func ons
to add two polynomials, print a polynomial, and insert a term into a polynomial. The `main` func on
demonstrates the usage by crea ng two polynomials, adding them, and prin ng the results.

Q5) a) Write an algorithm for pos ix evalua on with suitable example. [8]
Ans:- Pos ix evalua on is the process of evalua ng expressions given in pos ix nota on. In pos ix
nota on, also known as Reverse Polish Nota on (RPN), the operators come a er their operands. To
evaluate a pos ix expression, you can use a stack data structure.

Here's an algorithm for pos ix evalua on:

1. **Ini alize an empty stack.**

2. **Scan the pos ix expression from le to right.**

- For each symbol (operand or operator):

- If the symbol is an operand, push it onto the stack.

- If the symbol is an operator, pop the required number of operands from the stack, perform the
opera on, and push the result back onto the stack.

3. **A er scanning the en re expression, the result is on the top of the stack. Pop it to get the final
result.**

Let's go through an example to illustrate the algorithm:

15

### Example:

Pos ix expression: `6 3 / 2 + 5 *`

1. **Ini alize an empty stack.**

2. **Scan the expression from le to right:**

- `6`: Push onto the stack.

- Stack: `6`

- `3`: Push onto the stack.

- Stack: `6 3`

- `/`: Pop two operands (`3` and `6`), perform the division (`6 / 3`), and push the result (`2`) onto the
stack.

- Stack: `2`

- `2`: Push onto the stack.

- Stack: `2 2`

- `+`: Pop two operands (`2` and `2`), perform the addi on (`2 + 2`), and push the result (`4`) onto the
stack.

- Stack: `4`

- `5`: Push onto the stack.

- Stack: `4 5`

- `*`: Pop two operands (`5` and `4`), perform the mul plica on (`4 * 5`), and push the result (`20`)
onto the stack.

- Stack: `20`

3. **The result (`20`) is on the top of the stack. Pop it to get the final result.**

- Stack: `Empty`

- Final Result: `20`

So, the result of the pos ix expression `6 3 / 2 + 5 *` is `20`.

b) What is concept of recursion? Explain the use of stack in recursion with

example. [9]
Ans:- **Concept of Recursion:**
16

Recursion is a programming concept where a func on calls itself directly or indirectly to solve a smaller
instance of the same problem. In simple terms, a func on is said to be recursive if it calls itself. Recursion
provides an elegant and concise way to solve certain types of problems, especially those that exhibit a
repe ve or self-similar structure.

Recursion involves breaking down a problem into smaller sub-problems and solving each sub-problem
independently, and then combining their solu ons to obtain the solu on to the original problem. The
key components of a recursive func on are a base case (a condi on that stops the recursion) and a
recursive case (where the func on calls itself with modified arguments).

**Use of Stack in Recursion:**

The func on call stack plays a crucial role in the execu on of recursive func ons. Each me a func on is
called, a new stack frame is created and pushed onto the call stack. The stack frame contains informa on
about the local variables, parameters, and the return address of the func on. When a func on
completes its execu on, its stack frame is popped from the call stack.

The stack is essen al for maintaining the state of each recursive call. It allows the program to remember
where to return a er the base case is reached and enables the correct execu on of mul ple nested
recursive calls.

**Example of Recursion with Stack:**

Consider the classic example of calcula ng the factorial of a number using recursion:

#include <iostream>

int factorial(int n) {

// Base case: factorial of 0 is 1

if (n == 0) {

return 1;

// Recursive case: n! = n * (n-1)!

return n * factorial(n - 1);

int main() {

int num = 5;

std::cout << "Factorial of " << num << " is: " << factorial(num) << std::endl;

return 0;

}
17

Q6) a) What is need to convert the infix expression into pos ix; convert the
following expression into pos ix expression (a+b) * d + e/(f + a*d) + c. [8]
Ans:- Conver ng an infix expression to pos ix is beneficial for efficient expression evalua on, especially
when using a stack-based algorithm. The conversion process simplifies the expression representa on,
making it easier to evaluate with a stack. Here are the main reasons for conver ng an infix expression to
pos ix:

1. **Operator Precedence:**

- In an infix expression, operators have different precedences (priority levels). Conver ng to pos ix
eliminates the need for parentheses to explicitly specify the order of opera ons. Pos ix nota on
inherently captures the correct order of opera ons without the need for parentheses.

2. **Elimina on of Ambiguity:**

- In infix expressions, parentheses are o en used to indicate the order of opera ons, which can lead to
ambiguity. Conver ng to pos ix eliminates this ambiguity by represen ng the expression in a way that
explicitly shows the order of opera ons without relying on parentheses.

3. **Ease of Evalua on:**

- Pos ix expressions are inherently suitable for stack-based evalua on. The pos ix nota on allows for
straigh orward implementa on of a stack algorithm, where operands are pushed onto the stack, and
operators trigger the necessary calcula ons based on the operands present on the stack.

4. **No Operator Precedence Considera ons:**

- In pos ix expressions, there is no need to consider operator precedence during the evalua on
process. The le -to-right order of operands and operators inherently reflects the correct order of
opera ons.

5. **Simplified Parsing:**

- Conver ng to pos ix simplifies the parsing process for expression evalua on. Each operand and
operator are processed in a linear manner, making it easier to implement an algorithm that reads and
evaluates the expression from le to right.

6. **Reduced Complexity:**

- Pos ix expressions o en have reduced complexity compared to their infix counterparts. The absence
of parentheses and the explicit order of opera ons make pos ix expressions more straigh orward for
both human readability and algorithmic evalua on.

7. **Stack-Based Algorithm:**

- The conversion to pos ix facilitates the use of a stack-based algorithm for evalua on. This algorithm
is efficient, and the stack naturally reflects the order of opera ons without the need for recursive
parsing.
18

Example Conversion: Infix expression: (a+b)*d+e/(f+a*d)+c

Conversion Steps:

1. Scan from le to right:

 (a+b)*d+e/(f+a*d)+c

Pos ix expressiojn :- ab+d*efad*+/+c+

b) What is backtracking algorithm design strategy? How stack is useful in

backtracking [9]
Ans:- **Backtracking Algorithm Design Strategy:**

Backtracking is an algorithm design strategy that involves searching for a solu on to a problem
incrementally and undoing the choices that lead to a dead-end. It is par cularly useful for solving
problems where mul ple decisions need to be made, and the algorithm needs to explore different
possibili es.

The backtracking process involves making a series of choices, exploring the consequences of those
choices, and backtracking (undoing) when a chosen path leads to a situa on where no solu on is
possible. The algorithm then makes alterna ve choices and con nues un l a solu on is found or all
possibili es have been explored.

Here are the key steps in a backtracking algorithm:

1. **Choose:**

- Make a choice to move forward in the search space. This choice could involve selec ng a value for a
variable or deciding on a par cular path.

2. **Explore:**

- Explore the consequences of the chosen path. This may involve further choices and recursive
explora on.

3. **Backtrack:**

- If the chosen path leads to a dead-end (no solu on or invalid solu on), undo the last choice
(backtrack) and explore alterna ve paths.

4. **Termina on:**

- If a solu on is found, record it. The backtracking algorithm may con nue searching for addi onal
solu ons or terminate.

**Use of Stack in Backtracking:**

A stack is a fundamental data structure used in backtracking algorithms to keep track of the choices
made during the explora on process. The stack helps maintain the state of the algorithm, enabling it to
19

backtrack when needed. The key idea is to store informa on about each decision point on the stack so
that it can be easily undone when backtracking.

Here's how a stack is useful in backtracking:

1. **Decision Stack:**

- The stack keeps track of the decisions made during the explora on. Each decision point corresponds
to a specific state of the problem.

2. **Push and Pop:**

- When making a choice, relevant informa on is pushed onto the stack. This informa on includes the
current state and the chosen op on.

- When backtracking, the algorithm pops the top of the stack, effec vely undoing the last choice and
returning to the previous state.

3. **Maintaining State:**

- The stack maintains the state of the algorithm, allowing it to remember the path taken and revert to
previous states when needed.

4. **Depth-First Search (DFS):**

- Backtracking o en involves a depth-first search (DFS) strategy. The stack naturally supports DFS by
keeping track of the explora on path in a Last In, First Out (LIFO) manner.

5. **Efficient Memory Usage:**

- The use of a stack helps op mize memory usage by storing only the necessary informa on for
backtracking. This is par cularly important when exploring large solu on spaces.

Q7) a) Write pseudo C++ code to represent dequeue and perform the following
opera ons on dequeue: [8
] i) Create
ii) Insert
iii) Delete
iv) Display
Ans:- Certainly! Below is a pseudo C++ code for represen ng a deque (double-ended queue) and
performing the men oned opera ons: create, insert, delete, and display.

#include <iostream>

using namespace std;

20

// Node structure for a deque element

struct DequeNode {

int data;

DequeNode* next;

DequeNode* prev;

DequeNode(int value) : data(value), next(nullptr), prev(nullptr) {}

};

// Deque class

class Deque {

private:

DequeNode* front;

DequeNode* rear;

public:

// Constructor to ini alize an empty deque

Deque() : front(nullptr), rear(nullptr) {}

// Func on to insert an element at the front of the deque

void insertFront(int value) {

DequeNode* newNode = new DequeNode(value);

if (isEmpty()) {

front = rear = newNode;

} else {

newNode->next = front;

front->prev = newNode;

front = newNode;

// Func on to insert an element at the rear of the deque

void insertRear(int value) {

DequeNode* newNode = new DequeNode(value);

21

if (isEmpty()) {

front = rear = newNode;

} else {

newNode->prev = rear;

rear->next = newNode;

rear = newNode;

// Func on to delete an element from the front of the deque

void deleteFront() {

if (isEmpty()) {

cout << "Deque is empty. Cannot delete from the front." << endl;

} else {

DequeNode* temp = front;

front = front->next;

if (front == nullptr) {

rear = nullptr; // Deque becomes empty

} else {

front->prev = nullptr;

delete temp;

// Func on to delete an element from the rear of the deque

void deleteRear() {

if (isEmpty()) {

cout << "Deque is empty. Cannot delete from the rear." << endl;

} else {

DequeNode* temp = rear;

22

rear = rear->prev;

if (rear == nullptr) {

front = nullptr; // Deque becomes empty

} else {

rear->next = nullptr;

delete temp;

// Func on to display the elements of the deque

void display() {

if (isEmpty()) {

cout << "Deque is empty." << endl;

} else {

cout << "Deque Elements: ";

DequeNode* current = front;

while (current != nullptr) {

cout << current->data << " ";

current = current->next;

cout << endl;

// Func on to check if the deque is empty

bool isEmpty() {

return front == nullptr && rear == nullptr;

};

int main() {
23

// Create a deque

Deque deque;

// Insert elements

deque.insertFront(2);

deque.insertRear(4);

deque.insertFront(1);

deque.insertRear(6);

// Display elements

deque.display();

// Delete elements

deque.deleteFront();

deque.deleteRear();

// Display elements a er dele on

deque.display();

return 0;

b) What is circular queue? Explain the advantages of circular queue area linear
queue. [9]
Ans:- **Circular Queue:**

A circular queue is a type of queue data structure where the last element is connected to the first
element, forming a circular chain. In a regular (linear) queue, when elements are dequeued, the front
pointer moves forward, and the space previously occupied by the dequeued element becomes
unavailable. However, in a circular queue, when the last element is dequeued, the front pointer wraps
around to the beginning of the queue, u lizing the available space more efficiently.
24

**Advantages of Circular Queue over Linear Queue:**

1. **Efficient Use of Space:**

- Circular queues make efficient use of available space by avoiding the need to shi elements when the
front pointer reaches the end. The circular arrangement allows con nuous u liza on of the available
memory.

2. **Reduced Wastage of Memory:**

- In a linear queue, when elements are dequeued, the front pointer moves forward, leaving unused
space at the beginning. In contrast, a circular queue eliminates this wastage by wrapping around and
reusing the space that becomes available a er dequeuing.

3. **Avoiding Full Queue Condi on:**

- In a linear queue, even if there is space available at the front a er dequeuing, it may not be used un l
the front pointer reaches the beginning. In a circular queue, the space at the front is immediately
available for enqueuing new elements, avoiding a situa on where the queue appears full even though
space is available.

4. **Simpler Implementa on:**

- Circular queues simplify the implementa on of certain algorithms and opera ons. For example, when
implemen ng a circular buffer for streaming data, a circular queue allows con nuous reading and wri ng
without the need to reset pointers or allocate new memory.

5. **Logical Representa on of Circular Data:**

- Circular queues are well-suited for represen ng and manipula ng circular data structures or
processes. For instance, in scheduling algorithms where processes repeat in a circular manner, a circular
queue can naturally model the cyclic nature of the system.

6. **Easy to Implement Circular Buffer:**

- Circular queues are commonly used to implement circular buffers, which are useful in scenarios
where a fixed-size buffer is needed for streaming or buffering data. The circular nature allows for
efficient management of the buffer.

7. **Avoiding Fragmenta on:**

- In a circular queue, there is no issue of fragmenta on that can occur in linear queues due to
con nuous enqueue and dequeue opera ons. The circular arrangement ensures that the queue remains
cohesive and well-organized.

Q8) a) Define queue as an ADT. Write pseudo C++ code to represent queue.[8]
Ans:- **Queue as an Abstract Data Type (ADT):**
25

A queue is an abstract data type that represents a collec on of elements with two main opera ons:
enqueue and dequeue. It follows the First-In-First-Out (FIFO) principle, meaning that the element that is
enqueued first will be the first to be dequeued

**Queue ADT Opera ons:**

1. **Enqueue:** Adds an element to the rear (end) of the queue.

2. **Dequeue:** Removes and returns the element from the front (beginning) of the queue.

3. **Front:** Returns the element at the front of the queue without removing it.

4. **IsEmpty:** Checks if the queue is empty.

5. **Size:** Returns the number of elements in the queue.

**Pseudo C++ Code to Represent Queue:**

#include <iostream>

using namespace std;

// Node structure for a queue element

struct QueueNode {

int data;

QueueNode* next;

QueueNode(int value) : data(value), next(nullptr) {}

};

// Queue class

class Queue {

private:

QueueNode* front;

QueueNode* rear;

public:

// Constructor to ini alize an empty queue

Queue() : front(nullptr), rear(nullptr) {}

// Func on to enqueue an element to the rear of the queue

void enqueue(int value) {

QueueNode* newNode = new QueueNode(value);

26

if (isEmpty()) {

front = rear = newNode;

} else {

rear->next = newNode;

rear = newNode;

// Func on to dequeue an element from the front of the queue

void dequeue() {

if (isEmpty()) {

cout << "Queue is empty. Cannot dequeue." << endl;

} else {

QueueNode* temp = front;

front = front->next;

delete temp;

if (front == nullptr) {

rear = nullptr; // Queue becomes empty

// Func on to get the element at the front of the queue

int getFront() {

if (isEmpty()) {

cout << "Queue is empty." << endl;

return -1; // Assuming -1 represents an invalid value

return front->data;

// Func on to check if the queue is empty

27

bool isEmpty() {

return front == nullptr && rear == nullptr;

// Func on to get the size of the queue

int size() {

int count = 0;

QueueNode* current = front;

while (current != nullptr) {

count++;

current = current->next;

return count;

};

int main() {

// Create a queue

Queue myQueue;

// Enqueue elements

myQueue.enqueue(2);

myQueue.enqueue(4);

myQueue.enqueue(6);

// Display front element

cout << "Front element: " << myQueue.getFront() << endl;

// Dequeue an element

myQueue.dequeue();

// Display front element and size a er dequeue

cout << "Front element a er dequeue: " << myQueue.getFront() << endl;

cout << "Size of the queue: " << myQueue.size() << endl;
28

return 0;

b) Explain Array implementa on of priority queue with all basic opera ons. [9]
Ans:- **Priority Queue:**

A priority queue is an abstract data type that stores elements along with their associated priori es. The
element with the highest priority is served before elements with lower priori es. In the case of equal
priori es, the order of inser on is typically considered.

**Array Implementa on of Priority Queue:**

In an array implementa on of a priority queue, elements and their priori es are stored in an array. The
priority of each element is used to determine its posi on in the array. The highest priority element is
placed at the beginning of the array, and lower priority elements follow in order. The basic opera ons
include inser on and dele on of elements based on their priori es.

**Basic Opera ons:**

1. **Inser on (Enqueue):**

- Insert an element into the priority queue according to its priority.

2. **Dele on (Dequeue):**

- Remove and return the element with the highest priority.

3. **Peek (Get Highest Priority):**

- Retrieve the element with the highest priority without removing it.

4. **isEmpty:**

- Check if the priority queue is empty.

5. **Size:**

- Get the number of elements in the priority queue.

**Pseudo C++ Code:**

#include <iostream>

using namespace std;

const int MAX_SIZE = 100;

// Structure to represent an element in the priority queue

struct PriorityQueueElement {
29

int data;

int priority;

PriorityQueueElement(int value, int p) : data(value), priority(p) {}

};

// Priority Queue class using array implementa on

class PriorityQueue {

private:

PriorityQueueElement array[MAX_SIZE];

int size;

public:

// Constructor to ini alize an empty priority queue

PriorityQueue() : size(0) {}

// Func on to insert an element with a given priority

void enqueue(int value, int priority) {

if (size == MAX_SIZE) {

cout << "Priority queue is full. Cannot enqueue." << endl;

return;

// Insert at the correct posi on based on priority

int i = size - 1;

while (i >= 0 && array[i].priority < priority) {

array[i + 1] = array[i];

i--;

array[i + 1] = PriorityQueueElement(value, priority);

size++;

// Func on to remove and return the element with the highest priority

int dequeue() {
30

if (isEmpty()) {

cout << "Priority queue is empty. Cannot dequeue." << endl;

return -1; // Assuming -1 represents an invalid value

int highestPriorityElement = array[0].data;

// Shi elements to fill the gap

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

array[i - 1] = array[i];

size--;

return highestPriorityElement;

// Func on to get the element with the highest priority without removing it

int peek() {

if (isEmpty()) {

cout << "Priority queue is empty." << endl;

return -1; // Assuming -1 represents an invalid value

return array[0].data;

// Func on to check if the priority queue is empty

bool isEmpty() {

return size == 0;

// Func on to get the size of the priority queue

int getSize() {

return size;

};
31

int main() {

// Create a priority queue

PriorityQueue myPriorityQueue;

// Enqueue elements with priori es

myPriorityQueue.enqueue(2, 3);

myPriorityQueue.enqueue(4, 1);

myPriorityQueue.enqueue(6, 2);

// Dequeue and display the highest priority element

cout << "Dequeued Element: " << myPriorityQueue.dequeue() << endl;

// Display the element with the highest priority without dequeuing

cout << "Peek Element: " << myPriorityQueue.peek() << endl;

// Display size of the priority queue

cout << "Size of Priority Queue: " << myPriorityQueue.getSize() << endl;

return 0;