5 marks question

1. Apply Bubble sort to sort the following numbers: 14, 33, 27, 35, 10.

Bubble sort works by repeatedly comparing adjacent elements and swapping them if they are in the
wrong order. The algorithm continues to perform passes over the list until the entire list is sorted.

Given array: 14, 33, 27, 35, 10

Steps for Bubble Sort:

 Pass 1:

o Compare 14 and 33 → no swap.

o Compare 33 and 27 → swap → 14, 27, 33, 35, 10

o Compare 33 and 35 → no swap.

o Compare 35 and 10 → swap → 14, 27, 33, 10, 35

 Pass 2:

o Compare 14 and 27 → no swap.

o Compare 27 and 33 → no swap.

o Compare 33 and 10 → swap → 14, 27, 10, 33, 35

o Compare 33 and 35 → no swap.

 Pass 3:

o Compare 14 and 27 → no swap.

o Compare 27 and 10 → swap → 14, 10, 27, 33, 35

o Compare 27 and 33 → no swap.

o Compare 33 and 35 → no swap.

 Pass 4:

o Compare 14 and 10 → swap → 10, 14, 27, 33, 35

o The array is now sorted.

Sorted Array: 10, 14, 27, 33, 35

2. Convert the following Infix into Postfix expression: A+(B*C)/D

Steps to convert Infix to Postfix (using a stack):

1. Infix: A + (B * C) / D

2. Start reading the expression left to right.

3. A: Operand, add directly to the postfix expression → A

5. (: Opening parenthesis, push onto the stack.

6. B: Operand, add directly to the postfix expression → A B

7. *: Operator, push onto the stack.

8. C: Operand, add directly to the postfix expression → A B C

9. ): Closing parenthesis, pop until opening parenthesis. Pop *, add to postfix expression → A B
C*

10. /: Operator, push onto the stack.

11. D: Operand, add directly to the postfix expression → A B C * D

12. End of expression, pop the remaining operators (/) and add to postfix expression → A B C * D
/+

Postfix Expression: A B C * D / +

3. Write an algorithm to insert an item in a Queue data structure and explain each step.

Queue Insertion (Enqueue) Algorithm:

1. Initialize: Create an empty queue with a fixed or dynamic size.

2. Check for Full Queue: Before inserting an item, check if the queue is full (if it is, return an
error).

3. Insert Item:

o If the queue is not full, insert the item at the rear end (or tail) of the queue.

o Update the rear pointer to the next position.

4. Handle Circular Queue (if applicable): In the case of a circular queue, when the rear pointer
reaches the end of the array, reset it to the beginning of the array.

Example Code:

class Queue:

def __init__(self, size):

self.queue = [None] * size

self.front = self.rear = -1

self.size = size

def enqueue(self, item):

if (self.rear + 1) % self.size == self.front:

return

if self.front == -1: # If the queue is empty

self.front = self.rear = 0

else:

self.rear = (self.rear + 1) % self.size

self.queue[self.rear] = item

4. Construct a maximum heap tree from the following sequence of inputs: 45, 32, 50, 22, 65, 55, 77

Steps to construct the maximum heap:

1. Insert 45 → [45]

2. Insert 32 → [45, 32]

3. Insert 50 → [50, 32, 45]

4. Insert 22 → [50, 32, 45, 22]

5. Insert 65 → [65, 50, 45, 32, 22]

6. Insert 55 → [65, 50, 55, 32, 22, 45]

7. Insert 77 → [77, 65, 55, 50, 22, 45, 32]

Max Heap Tree:

77

/ \

65 55

/ \ / \

50 22 45 32

5. Write an algorithm for Quick Sort and Heap Sort and explain.

Quick Sort Algorithm:

1. Choose a pivot element from the array (usually the last element).

2. Partition the array into two sub-arrays:

o One with elements smaller than the pivot.

o One with elements greater than the pivot.

3. Recursively apply the same steps to the sub-arrays.

def quick_sort(arr):

if len(arr) <= 1:

return arr

pivot = arr[len(arr) - 1]

left = [x for x in arr[:-1] if x <= pivot]

right = [x for x in arr[:-1] if x > pivot]

return quick_sort(left) + [pivot] + quick_sort(right)

Heap Sort Algorithm:

1. Build a max heap from the given array.

2. Swap the root (maximum value) with the last element of the heap.

3. Remove the last element from the heap.

4. Reheapify the heap to maintain the max-heap property.

5. Repeat steps 2–4 until the heap size is reduced to 1.

Heap Sort Example:

def heapify(arr, n, i):

largest = i

left = 2 * i + 1

right = 2 * i + 2

if left < n and arr[largest] < arr[left]:

largest = left

if right < n and arr[largest] < arr[right]:

largest = right

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

def heap_sort(arr):

n = len(arr)

for i in range(n//2, -1, -1):

heapify(arr, n, i)
 for i in range(n-1, 0, -1):

arr[i], arr[0] = arr[0], arr[i]

heapify(arr, i, 0)

6. Create an algorithm for Push and Pop operations on Stack using Arrays

Stack Operations (Push & Pop):

1. Push: Add an element to the top of the stack.

o Check if the stack is full.

o Increment the top pointer and place the element at the top.

2. Pop: Remove the top element from the stack.

o Check if the stack is empty.

o Decrement the top pointer and return the popped element.

Push Algorithm:

def push(stack, top, element):

if top == len(stack) - 1:

print("Stack Overflow")

return top

top += 1

stack[top] = element

return top

Pop Algorithm:

def pop(stack, top):

if top == -1:

print("Stack Underflow")

return top

top -= 1

return top

7. Define Stack. What are the various Operations performed on the Stack?

Stack: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The most
recent element added is the first to be removed.
Operations on Stack:

1. Push: Add an element to the top of the stack.

2. Pop: Remove the top element from the stack.

3. Peek: View the top element without removing it.

4. IsEmpty: Check if the stack is empty.

5. IsFull: Check if the stack is full (in case of fixed-size arrays).

8. Draw and explain Adjacency Matrix and mention the advantages of adjacency matrix

Adjacency Matrix is a 2D array used to represent a graph. If a graph has VVV vertices, an adjacency
matrix is a V×VV \times VV×V matrix. The value at position (i,j)(i, j)(i,j) represents the presence or
absence of an edge between vertex iii and vertex jjj.

 For undirected graphs, if there is an edge between iii and jjj, then both (i,j)(i, j)(i,j) and (j,i)(j,
i)(j,i) are set to 1.

 For directed graphs, the value (i,j)(i, j)(i,j) is 1 if there is a directed edge from vertex iii to
vertex jjj, and 0 otherwise.

Example:

For the undirected graph with 4 vertices (A, B, C, D) and the edges A-B, A-C, and B-D:

mathematica

Copy code

Graph:

/\

B C

Adjacency Matrix:

ABCD

A[0110]

B[1001]

C[1000]

D[0100]
Advantages of Adjacency Matrix:

1. Efficient Edge Lookup: It provides O(1)O(1)O(1) time complexity for checking if an edge exists
between two vertices.

2. Space Efficiency for Dense Graphs: If the graph is dense (i.e., most pairs of vertices are
connected), the adjacency matrix is an efficient representation.

3. Simplicity: It is simple to implement and use, especially for small graphs.

4. Easy to Traverse: Easy to traverse all neighbors of a vertex in a matrix representation.

9. Explain the Pre-order, In-order, and Post-order traversal in Tree data structure

These are different methods for traversing a binary tree.

1. Pre-order Traversal:

o Visit the root node first, then recursively traverse the left subtree, followed by the
right subtree.

o Order: Root → Left Subtree → Right Subtree

o Example: For a tree:

css

Copy code

/\

B C

Pre-order traversal: A, B, D, C

2. In-order Traversal:

o Recursively traverse the left subtree first, then visit the root node, and finally
traverse the right subtree.

o Order: Left Subtree → Root → Right Subtree

o Example: For the same tree: In-order traversal: D, B, A, C

3. Post-order Traversal:

o Recursively traverse the left subtree, then the right subtree, and finally visit the root
node.

o Order: Left Subtree → Right Subtree → Root

o Example: For the same tree: Post-order traversal: D, B, C, A

Given postfix expression: P = BC*DEF^/-

 B=5,C=6,D=24,E=2,F=3B = 5, C = 6, D = 24, E = 2, F = 3B=5,C=6,D=24,E=2,F=3

Postfix expression: 5 6 * 24 2 3 ^ / -

Steps to evaluate:

1. Read 5 → Push to stack → Stack: [5]

2. Read 6 → Push to stack → Stack: [5, 6]

3. Read * → Pop 6 and 5, multiply them → 5 * 6 = 30, Push the result → Stack: [30]

4. Read 24 → Push to stack → Stack: [30, 24]

5. Read 2 → Push to stack → Stack: [30, 24, 2]

6. Read 3 → Push to stack → Stack: [30, 24, 2, 3]

7. Read ^ → Pop 3 and 2, calculate 2^3 = 8, Push the result → Stack: [30, 24, 8]

8. Read / → Pop 8 and 24, calculate 24 / 8 = 3, Push the result → Stack: [30, 3]

9. Read - → Pop 3 and 30, calculate 30 - 3 = 27, Push the result → Stack: [27]

Final Result: P = 27

11. Construct a BST with the following input values: 70, 20, 11, 45, 95, 76, 29, 59, 99

Steps to construct the BST:

1. Insert 70: Root is 70.

2. Insert 20: 20 is less than 70, so it goes to the left of 70.

3. Insert 11: 11 is less than 70, less than 20, so it goes to the left of 20.

4. Insert 45: 45 is less than 70 but greater than 20, so it goes to the right of 20.

5. Insert 95: 95 is greater than 70, so it goes to the right of 70.

6. Insert 76: 76 is greater than 70 but less than 95, so it goes to the left of 95.

7. Insert 29: 29 is less than 70, greater than 20, but less than 45, so it goes to the left of 45.

8. Insert 59: 59 is less than 70, greater than 45, so it goes to the right of 45.

9. Insert 99: 99 is greater than 70, greater than 95, so it goes to the right of 95.

BST Structure:

markdown
Copy code

70

/ \

20 95

/ \ / \

11 45 76 99

/ \

29 59

12. What is B-Tree? Write the characteristics of B-Tree

B-Tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion,
deletion, and search operations. It is commonly used in databases and file systems.

Characteristics of a B-Tree:

1. Balanced Tree: All leaf nodes are at the same level.

2. Nodes Contain Multiple Keys: Each node can have multiple keys and children.

3. Sorted Keys: Keys within each node are sorted in ascending order.

4. Root Node: The root node can have as few as one child or be empty.

5. Nodes with Multiple Children: A node with nnn keys will have n+1n+1n+1 children.

6. Efficient Operations: All operations (insert, delete, search) have O(log⁡n)O(\log n)O(logn) time
complexity.

13. What is a Linked List? Write and explain the algorithm for create, insertion, and traverse
operations in a doubly linked list with an example.

A Linked List is a linear data structure in which elements are stored in nodes. Each node contains
data and a reference (or link) to the next node in the sequence.

Doubly Linked List:

In a Doubly Linked List, each node has two references: one to the next node and one to the previous
node.

Doubly Linked List Operations:

1. Create: Initialize an empty list or create the first node.

2. Insert: Insert a node at the beginning, end, or at a specific position.

3. Traverse: Traverse the list from head to tail or tail to head.

Example (Doubly Linked List):

Copy code

class Node:

def __init__(self, data):

self.data = data

self.next = None

self.prev = None

class DoublyLinkedList:

def __init__(self):

self.head = None

# Insert at the beginning

def insert_at_beginning(self, data):

new_node = Node(data)

if self.head is None:

self.head = new_node

else:

new_node.next = self.head

self.head.prev = new_node

self.head = new_node

# Traverse the list

def traverse(self):

current = self.head

while current:

print(current.data, end=" ")

current = current.next

Example Operations:

python

Copy code
dll = DoublyLinkedList()

dll.insert_at_beginning(10)

dll.insert_at_beginning(20)

dll.traverse() # Output: 20 10

14. What is Stack? Write algorithm for operations of stack with examples

Refer to the Stack section above for a complete explanation of Stack and its operations.

15. What are the limitations of Queue? Explain the algorithms for various operations of circular
queue

The limitations of a Queue are primarily:

1. Fixed size: In simple queues, the size is fixed and may lead to overflow or underutilization.

2. No direct access: You can only access the front and rear elements, not any arbitrary element.

In Circular Queue, these limitations are resolved by using the available space more efficiently.
Circular queue operates in a circular manner, where the end of the queue connects back to the front.

16. Insertion, Deletion, and Searching Operations on AVL Trees

An AVL Tree is a self-balancing binary search tree (BST) in which the difference in heights between
the left and right subtrees (balance factor) of any node is at most 1. The key operations in AVL trees
are insertion, deletion, and searching. Here's how each operation works:

Insertion in AVL Tree:

1. BST Insertion: First, insert the node in the tree as you would in a standard binary search tree
(i.e., if the value is less than the current node, insert in the left subtree, otherwise insert in
the right subtree).

2. Balance Factor Calculation: After inserting the node, traverse back from the inserted node to
the root, calculating the balance factor at each node. The balance factor is the difference
between the heights of the left and right subtrees (balance_factor = height(left subtree) -
height(right subtree)).

3. Balancing the Tree: If the balance factor of any node becomes greater than 1 or less than -1,
the tree is unbalanced, and you need to perform rotations:

o Left-Left (LL) Case: If the left child of the left subtree is higher, perform a Right
Rotation.

o Right-Right (RR) Case: If the right child of the right subtree is higher, perform a Left
Rotation.
 o Left-Right (LR) Case: If the right child of the left subtree is higher, perform a Left
Rotation on the left child followed by a Right Rotation on the current node.

o Right-Left (RL) Case: If the left child of the right subtree is higher, perform a Right
Rotation on the right child followed by a Left Rotation on the current node.

Deletion in AVL Tree:

1. BST Deletion: First, delete the node from the tree as you would in a standard binary search
tree (find the node, replace it with its in-order predecessor or successor if necessary, and
remove it).

2. Balance Factor Calculation: After deletion, traverse back from the parent node to the root,
recalculating the balance factor at each node.

3. Balancing the Tree: If the balance factor becomes greater than 1 or less than -1 at any node,
perform rotations to restore the balance:

o Similar to insertion, you will need to perform rotations based on whether the tree is
left-heavy or right-heavy at any node.

Searching in AVL Tree:

 Searching in an AVL tree is similar to searching in a regular binary search tree. Starting from
the root, if the search value is less than the current node's value, move to the left child; if it’s
greater, move to the right child.

 Since an AVL tree is balanced, searching will take O(log n) time, where n is the number of
nodes in the tree.

17. What is a Binary Search Tree? How do you insert an element into a Binary Search Tree?

Binary Search Tree (BST):

A Binary Search Tree (BST) is a binary tree in which every node has at most two children, and the
following conditions hold:

 The value of every node in the left subtree is less than the value of the root node.

 The value of every node in the right subtree is greater than the value of the root node.

 Both the left and right subtrees are also BSTs.

Insertion into a Binary Search Tree:

To insert an element into a BST, the following steps are followed:

1. Start at the Root: Begin at the root of the tree.

2. Traverse the Tree:

o If the element to be inserted is smaller than the current node’s value, move to the
left child.
 o If the element to be inserted is greater than the current node’s value, move to the
right child.

3. Insert the Node: Once a null (empty) child is reached, insert the new node at that position.

4. Maintain BST Property: Ensure that the BST properties are maintained by continuing the
traversal until a valid insertion point is found.

Example:

Insert 25 into the following BST:

30

/ \

20 40

/ \

10 25

Insert 25:

- 25 is less than 30, so move to the left child.

- 25 is greater than 20, so move to the right child.

- Position 25 to the right of 20, as the left of 25 is null.

18. Discuss Floyd’s Algorithm

Floyd's Algorithm, also known as Floyd-Warshall Algorithm, is a well-known algorithm used to find
the shortest paths between all pairs of vertices in a weighted graph (with both positive and negative
weights). It is a dynamic programming algorithm and works for both directed and undirected graphs.

Steps in Floyd’s Algorithm:

1. Initialization:

o Initialize a distance matrix dist[i][j] where dist[i][j] is the shortest path from vertex i
to vertex j.

o If there is an edge between vertex i and j, set dist[i][j] to the edge weight; if no edge
exists, set dist[i][j] to infinity (∞).

o Set dist[i][i] = 0 for all vertices i.

2. Update the Matrix:

o The key idea is that, for each intermediate vertex k, check if a path from vertex i to
vertex j that goes through k is shorter than the existing path.
 o The update rule is: dist[i][j]=min⁡(dist[i][j],dist[i][k]+dist[k][j])dist[i][j] = \min(dist[i][j],
dist[i][k] + dist[k][j])

o Repeat this process for every possible intermediate vertex k.

3. Result:

o After processing all vertices as intermediates, the matrix dist[i][j] contains the
shortest path lengths between all pairs of vertices.

Time Complexity:

 The time complexity of Floyd's algorithm is O(V3)O(V^3), where V is the number of vertices
in the graph. This is because there are three nested loops (for each of the vertices) iterating
over the graph.

19. With an Example, Discuss Warshall’s Algorithm

Warshall’s Algorithm is used to find the transitive closure of a directed graph. The transitive closure
of a graph is a matrix that shows which vertices are reachable from other vertices. It’s essentially a
special case of Floyd’s algorithm where the goal is to determine reachability (whether a path exists)
rather than shortest path distances.

Steps in Warshall's Algorithm:

1. Initialization:

o Start with an adjacency matrix A where A[i][j] = 1 if there is an edge from vertex i to
vertex j, otherwise A[i][j] = 0.

o Set A[i][i] = 1 for all vertices (a vertex can always reach itself).

2. Update Matrix:

o For each vertex k, update the matrix A[i][j] to reflect whether there is a path from
vertex i to vertex j through vertex k.

o The update rule is: A[i][j]=A[i][j]∨(A[i][k]∧A[k][j])A[i][j] = A[i][j] \lor (A[i][k] \land A[k]
[j]) where \lor is the logical OR operator, and \land is the logical AND operator.

3. Result:

o After completing the algorithm, A[i][j] = 1 means there is a path from vertex i to
vertex j, and A[i][j] = 0 means no such path exists.

Example:

Consider the following directed graph with 4 vertices:

0→1

1→2

2→3

The adjacency matrix is:

After applying Warshall’s algorithm, the matrix A will be updated to:

A=[1111011100110001]A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 &
0 & 1 \end{bmatrix}

This matrix indicates that every vertex can reach every other vertex, either directly or indirectly.

Time Complexity:

 The time complexity of Warshall's algorithm is O(V3)O(V^3), where V is the number of