SECTION - A

Answer any Four questions. Each question carries 2 marks

1. List any two important characteristics of an algorithm

• Finiteness: An algorithm must always terminate after a finite number of steps.

• Definiteness: Each step of the algorithm must be clearly definite

2. Define divide and conquer technique

Divide and Conquer is a problem-solving strategy that divides a problem into smaller sub-
problems, solves each sub-problem recursively, and then combines their results to solve
the original problem

3. What is minimum cost spanning tree? Give an example.

A Minimum Cost Spanning Tree (MST) is a subset of edges of a connected, weighted

graph that connects all the vertices with the minimum possible total edge weight, without
forming any cycle
Example: In a graph with nodes A, B, C and weights: AB=1, AC=3, BC=2, the MST includes
AB and BC (total weight = 3)

4. Define binary tree. List three types of binary tree traversal.

A Binary Tree is a tree data structure where each node has at most two children: left and
right.

Types of Traversal:

• Inorder (Left, Root, Right)

• Preorder (Root, Left, Right)
• Postorder (Left, Right, Root)
5. Define Huffman codes.

Huffman codes are variable-length binary codes assigned to input characters based on
their frequencies. Characters that occur more frequently are assigned shorter codes. This
method is used in data compression (e.g., ZIP files).

6. What is backtracking?

Backtracking is a problem-solving algorithm that builds a solution incrementally and

removes solutions that fail to satisfy the problem constraints at any point (i.e., it
“backtracks” to try a different option).
Used in: N-Queens, Sudoku, etc.

SECTION - B
Answer any Four questions. Each question carries 5 marks.

7. Explain worst case, best case, and average case efficiencies with
examples.

• Worst Case: The input is in the least favorable condition.

Example: For Linear Search, worst case is when the element is not found or at the
last position.
Time Complexity: O(n)
• Best Case: The input is in the most favorable condition.
Example: For Linear Search, best case is when the element is found at the first
position.
Time Complexity: O(1)
 • Average Case: Considers all possible inputs and calculates the average
performance.
Example: For Linear Search, average case assumes the element is in the middle.
Time Complexity: O(n)

8. What is recursive algorithm? Analyse time efficiency for finding

factorial.

A recursive algorithm solves a problem by calling itself with a smaller input. It must have a
base case to stop recursion.

Example – Factorial:

python
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

Time Complexity:

• Each call reduces the problem size by 1.

• Total of n recursive calls → Time Complexity: O(n)
• Space Complexity: O(n) (due to function call stack)
Topological Sorting:
Topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such
that for every directed edge u → v, vertex u comes before v.

Source Removal Method: Steps:

1. Identify nodes with no incoming edges (called sources).

2. Remove them and add to the result.
3. Repeat until all nodes are processed.

Given Graph:

C1 → C3 → C5
C2 → C3
C4 → C5

In-degree Calculation:

• C1: 0
• C2: 0
• C3: 2 (from C1, C2)
• C4: 0
• C5: 2 (from C3, C4)

Step-by-step removal:

1. Sources: C1, C2, C4

2. Remove C1 → update in-degrees: C3 becomes 1
3. Remove C2 → C3 becomes 0 → add C3 to source list
4. Remove C4 → C5 becomes 1
 5. Remove C3 → C5 becomes 0
6. Remove C5

Topological Sort (One possible order):

C1, C2, C4, C3, C5

11. Find the minimum weight spanning tree using Prim’s algorithm.

Prim’s Algorithm Steps:

1. Start from any vertex (let’s start with vertex 1).

2. Choose the smallest weight edge that connects a new vertex.
3. Repeat until all vertices are included.

Graph Edges with Weights:

(1–2): 11
(1–3): 7
(1–5): 8
(2–3): 13
(2–4): 14
(2–5): 15
(3–4): 12
(3–5): 9
(4–5): 6

Step-by-step Prim’s (starting at vertex 1):

• Start at 1 → choose edge (1–3): 7

• Vertices in MST: {1, 3}
• From 3, choose (3–5): 9
• Vertices: {1, 3, 5}
• From these, choose (5–4): 6
• Vertices: {1, 3, 5, 4}
• Next, from available edges, choose (1–2): 11
• Vertices: {1, 2, 3, 4, 5} → MST complete
MST Edges:
(1–3), (3–5), (5–4), (1–2)

Total Weight = 7 + 9 + 6 + 11 = 33

12. Construct solution space tree for a set S = {1, 13, 24, 7} and M = 31

This is a subset sum problem: Find subsets of S whose sum is 31.

We'll draw a solution space tree, exploring inclusion/exclusion of each element.

Set S: [1, 13, 24, 7]

Target Sum (M): 31

Tree root:

• Start at level 0 with sum = 0, index = 0

Branching (Include/Exclude at each level):

markdown
(0, 0)
/ \
(1, 1) (0, 1)
/ \ / \
(14,2) (1,2) (13,2) (0,2)
/ \ ... ... ...
(38,3)(14,3) ...

One valid path (solution):

Include 7 → Include 24 → Include 0 → Include 0
Sum = 7 + 24 = 31 → Subset: [24, 7]

Other valid subset: [1, 13, 7, 10], but not present in set, so only [24, 7] is valid.
13. Explain Strassen’s Matrix Multiplication Method. Compare its
efficiency with conventional matrix multiplication.

Conventional Matrix Multiplication:

For two 2×2 matrices:

• Requires 8 multiplications and 4 additions.

Strassen’s Algorithm:
Reduces the number of multiplications to 7 by using 7 specific products (P1 to P7) and
combining them:
Let A, B be 2×2 matrices:

ini
P1 = A11 × (B12 − B22)
P2 = (A11 + A12) × B22
P3 = (A21 + A22) × B11
P4 = A22 × (B21 − B11)
P5 = (A11 + A22) × (B11 + B22)
P6 = (A12 − A22) × (B21 + B22)
P7 = (A11 − A21) × (B11 + B12)

Then calculate resulting submatrices using combinations of these.

Efficiency:

• Conventional: O(n³)
• Strassen’s: O(n^log₂7) ≈ O(n^2.81)
• Faster for large matrices but not always practical for small sizes due to overhead.
Given graph:

markdown
1
/ \
2 3
/| \
4 5 6
/
7

DFS (starting from 1):

• Visit 1
• Go to 2
• Go to 4 (from 2)
• Backtrack to 2 → Go to 5
• Backtrack to 1 → Go to 3
• Go to 6 → Go to 7

DFS Traversal Order:

1→2→4→5→3→6→7

15. Trace the quick sort algorithm for the numbers:

45, 36, 15, 92, 35, 71, 64, 39, 73, 37

Step 1: Choose pivot (say last element = 37)

Partition:

• Left: [36, 15, 35]

• Pivot: 37
• Right: [45, 92, 71, 64, 39, 73]

Repeat recursively:
Left Partition [36, 15, 35]:

• Pivot: 35 → [15] 35 [36]

→ Sorted: [15, 35, 36]

Right Partition [45, 92, 71, 64, 39, 73]

• Pivot: 73
→ Partition: [45, 71, 64, 39], 73, [92]
Continue:
• Pivot: 39 → [ ], 39, [45, 71, 64]
Then sort [45, 71, 64]
→ Pivot: 64 → [45], 64, [71]

Final Sorted List:

[15, 35, 36, 37, 39, 45, 64, 71, 73, 92]

16. Solve 4-queue problem using backtracking. Draw solution space tree.

This is a variation of the N-Queens problem (place 4 queens on 4×4 board without
attacks).
Use backtracking to place one queen per row such that no two attack each other.

Solution Space Tree (Partial):

• Level 0: Try Q at (0,0), (0,1), (0,2), (0,3)

For each valid placement, move to next row and repeat.

One Valid Solution:

• Row 0 → Col 2
• Row 1 → Col 0
• Row 2 → Col 3
• Row 3 → Col 1

Positions: (0,2), (1,0), (2,3), (3,1)

17. Knapsack Problem: M = 40

Weights: [20, 25, 10, 15]

Profits: [20, 40, 35, 45]

Use 0/1 Knapsack and choose items to maximize profit without exceeding 40.

Check combinations:

• (W1 + W4) = 20 + 15 = 35 → P = 20 + 45 = 65
• (W2 + W3) = 25 + 10 = 35 → P = 40 + 35 = 75
• (W3 + W4) = 10 + 15 = 25 → P = 35 + 45 = 80
• (W2 + W4) = 25 + 15 = 40 → P = 40 + 45 = 85 Best so far

Optimal solution: W2 + W4 = 25 + 15 = 40 → Max profit = 85

18. Short notes:

a. Hamilton Circuit Problem:

A Hamiltonian circuit is a path in a graph that visits each vertex exactly once and returns
to the starting point.
Used in: Travelling Salesman Problem, circuit design.

b. Decision Tree:

A Decision Tree is a tree-like model used for making decisions and predicting outcomes.
Each internal node represents a decision test, branches represent outcomes, and leaf
nodes represent final decisions or classifications.

[Link]