Q1.

(a) Design and develop an efficient algorithm to find the list of prime
numbers in the range 501 to 2000. What is the complexity of this algorithm?

Sieve of Eratosthenes can be used to efficiently find prime numbers in the given
range.

Algorithm:

●​ Create a boolean array isPrime[2001] and initialize all entries as true.

●​ Mark isPrime[0] and isPrime[1] as false (since 0 and 1 are not primes).
●​ For each number p from 2 to √2000:
If isPrime[p] is true, mark all multiples of p as false (starting from
p²).
●​ Collect all numbers from 501 to 2000 where isPrime[i] is true.

Complexity:

●​ Time Complexity: O(n log log n) (for the Sieve of Eratosthenes).

●​ Space Complexity: O(n) (for the boolean array).

(b) Differentiate between Cubic-time and Factorial-time algorithms. Give

example of one algorithm each for these two running times.

Cubic-time Algorithms (O(n^3)):

●​ Definition: The time complexity grows proportionally to the cube of the input size.
●​ Example: Matrix Multiplication (naive algorithm)

Factorial-time Algorithms (O(n!)):

●​ Definition: The time complexity grows proportionally to the factorial of the input
size, making it extremely slow for large inputs.
●​ Example: Solving the Traveling Salesman Problem (using brute-force search)

The key difference between these two is that the Cubic-time algorithms are
polynomial-time and feasible for moderate inputs, while factorial-time algorithms are
exponential-time and impractical for large inputs.
(c) Write an algorithm to multiply two square matrices of order n*n. Also,
explain the time complexity of this algorithm.

Here is a simple algorithm to multiply two square matrices of order n*n:

Algorithm:

●​ Initialize a result matrix CC of size n×nn \times n with all elements set to 0.
●​ For each element C[i][j]C[i][j] in the result matrix:
○​ Compute the sum of the products A[i][k]⋅B[k][j]A[i][k] \cdot B[k][j] for all kk
from 0 to n−1n-1.
●​ Return the result matrix CC.

Time Complexity

The time complexity of this algorithm is O(n^3). This is because there are three nested
loops, each iterating over the size n of the matrices. For each pair of elements
C[i][j]C[i][j], we perform n multiplications and additions.

(d) What are asymptotic bounds for analysis of efficiency of algorithms?

Why are asymptotic bounds used? What are their shortcomings? Explain
the Big O and Big Θ notation with the help of a diagram. Find the Big
O-notation and Θ notation for the function: 𝑓(𝑛)= 100𝑛4 +1000𝑛3 +100000

Asymptotic Bounds for Analysis of Efficiency of Algorithms

Asymptotic bounds describe the growth rate of an algorithm's time or space complexity
as the input size 𝑛 approaches infinity. They provide a high-level understanding of an
algorithm's efficiency.

Asymptotic Bounds usage

●​ Simplicity: They abstract away constants and lower-order terms, focusing on the
dominant term that affects growth.
●​ Comparison: They allow easy comparison of algorithms' efficiency.
●​ Scalability: They help predict how an algorithm will perform as the input size
grows.

Shortcomings of Asymptotic Bounds

●​ Ignore Constants: They do not account for constant factors, which can be
significant for small inputs.
 ●​ Worst-Case Focus: They often describe worst-case scenarios, which may not
reflect real-world performance.
●​ No Practical Timing: They do not provide actual running time or space usage.

Big O-notation
It is used to describe the asymptotic upper bound of an algorithm, i.e. its worst-case
scenario.An algorithm with a running time of f(n) is equivalent to O(g(n)) if and only if
there are constants c and n0 such that the below expression is satisfied along with its
graph below.

Big Θ-notation

This notation describes both the upper and lower bound of a function and is often
referred to as the average time complexity. Big-Theta notation is described
mathematically as follows which can be visualised in the graph below.
​
Big O and Θ Notation for the function 𝑓(𝑛)= 100𝑛4 +1000𝑛3 +100000

●​ Dominant term is 𝑛4
●​ Big O: O(𝑛4)
●​ Big Θ: Θ(𝑛4)

(e) Write and explain the Left to Right binary exponentiation algorithm.
Demonstrate the use of this algorithm to compute the value of 329 (Show
the steps of computation). Explain the worst-case complexity of this
algorithm.

The Left-to-Right Binary Exponentiation algorithm efficiently computes ab using the

binary representation of the exponent b. It reduces the number of multiplications by
squaring and multiplying based on the bits of b.

Algorithm:
●​ Convert the exponent b to its binary representation.
●​ Initialize the result res=1.
●​ Iterate through each bit of b from left (most significant bit) to right (least
significant bit):
○​ Square the result: res=res×res
○​ If the current bit is 1, multiply the result by a: res=res×a.
●​ Return the final result res.
 Steps for computing 329
Step 1: Binary Representation of 29
●​ 29 in binary: 11101

Step 2: Initialize
●​ res=1

​ Step 3: Iterate Through Bits (Left to Right)

●​ Bit 1 (Leftmost):
○​ Square: res = 1×1=1.
○​ Multiply by a (since bit is 1): res = 1 × 3 = 3

●​ Bit 1:
○​ Square: res=3×3=9
○​ Multiply by a (since bit is 1): res=9×3=27

●​ Bit 1:
○​ Square: res=27×27=729
○​ Multiply by a (since bit is 1): res=729×3=2187

●​ Bit 0:
○​ Square: res = 2187 × 2187 = 4782969
○​ Do not multiply by a (since bit is 0)

●​ Bit 1 (Rightmost):
○​ Square: res = 4782969 × 4782969 = 22876792454961
○​ Multiply by a (since bit is 1 ): res = 2287679245496 1 × 3 =
68630377364883
●​ Final Result:
○​ 329 = 68630377364883

Worst-Case Complexity
●​ The algorithm processes each bit of the exponent b.
●​ For an exponent b with k bits:
○​ It performs k squaring operations.
○​ It performs at most k multiplications (one for each bit that is 1).
●​ Thus, the total number of operations is O(logb).
(f) Write and explain the Bubble sort algorithm. Discuss its best and
worst-case time complexity.

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through

the list, compares adjacent elements, and swaps them if they are in the wrong order.
This process is repeated until the list is sorted.

Algorithm Steps:
●​ Initialize: Start from the first element.
●​ Compare and Swap: Compare each pair of adjacent elements. If the first element
is greater than the second, swap them.
●​ Repeat: Move to the next pair of adjacent elements and repeat the comparison
and swap process.
●​ Iterate: Continue this process for multiple passes through the list until no swaps
are needed.

Time Complexity:

Case Complexity Explanation

Worst-case O(n²) Occurs when the array is in reverse order, requiring maximum
swaps.

Best-case O(n) If the array is already sorted, the algorithm exits early
(optimized version).

Bubble Sort is not the most efficient algorithm for large datasets, but its simplicity makes
it useful for small datasets or educational purposes.

(g) What are the uses of recurrence relations? Solve the following
recurrence relations using the Master’s method
𝑛
(I) 𝑇(𝑛) = 4𝑇 ( 4 ) + 𝑛1
3𝑛
​ (II) 𝑇(𝑛) = 4𝑇 ( 4
) + 𝑛1

Recurrence Relations usage

​
Recurrence relations are used to analyze the time complexity of recursive algorithms.
They help in:
 ●​ Estimating algorithm efficiency – Helps determine the runtime of
divide-and-conquer algorithms.
●​ Understanding recursive function growth – Models how recursive calls break
down the problem.
●​ Algorithm optimization – Guides improvements in recursive algorithms.
●​ Mathematical problem-solving – Used in dynamic programming, combinatorics,
and sequence analysis.

Master’s Theorem

Master’s theorem is used for recurrence relations of the form:

T(n)=aT(n/b)+f(n)
where:
●​ a = number of recursive calls,
●​ b = factor by which the problem size reduces,
●​ f(n) = additional work done outside recursion.

The complexity depends on comparing f(n) with O(nlog⁡ba)

𝑛
(I) Solving: 𝑇(𝑛) = 4𝑇( 4 )+𝑛1

●​ Here: a=4 b=4, f(n)=n1

●​ Compute: log⁡
4(4)=1

●​ Since f(n)=O(n1) matches O(n1), we use Case 2 of Master’s Theorem:

T(n)=Θ(n1log n)=Θ(n log n)

Final Complexity: Θ(n log n)

(II) Solving 𝑇(𝑛) = 4𝑇 ( 3𝑛

4
) + 𝑛1

●​ Here: a=4, b=4/3, f(n)=n1

●​ Compute: log4/3​ (4)=log(4)/log(4/3)≈2.409
●​ Since f(n)=O(n1) and 1<2.4091, we use Case 1 of Master’s Theorem:
T(n)=Θ(nlog4/3​4)=Θ(n2.409)

Final Complexity: Θ(n2.409)

Q2: (a) What is an Optimisation Problem? Explain with the help of an
example. When would you use a Greedy Approach to solve optimization
problem? Formulate the Task Scheduling Problem as an optimization
problem and write a greedy algorithm to solve this problem. Also, solve the
following fractional Knapsack problem using the greedy approach. Show
all the steps.
Suppose there is a knapsack of capacity 20 Kg and the following 6 items
are to packed in it. The weight and profit of the items are as under:
(p1, p2,…, p6) = (30,16,18,20,10, 7)
(w1, w2,…, w6) = ( 5, 4, 6, 4, 5, 7)
Select a subset of the items that maximize the profit while keeping the total
weight below or equal to the given capacity.

An optimization problem involves finding the best solution from a set of possible
solutions, given certain constraints. The goal is to either maximize or minimize a
particular objective function.

Example:

○​ Problem: Finding the shortest path between two points in a graph

○​ Objective: Minimize the total distance traveled.
○​ Constraints: Only use available paths (edges) in the graph.

Greedy Approach

A Greedy Approach is used to solve optimization problems by making a series of

decisions, each of which is the best at the moment. This approach does not always
guarantee an optimal solution but works well for certain problems.

When to Use:

●​ When a problem has an optimal substructure (an optimal solution to the problem
contains optimal solutions to subproblems).
●​ When a problem exhibits the Greedy-choice property (a global optimum can be
reached by choosing the local optimum).

Task Scheduling Problem

 ●​ Objective: Maximize the number of tasks completed.
●​ Constraints: Each task has a start and end time, and only one task can be
performed at a time.

Greedy Algorithm for Task Scheduling

●​ Sort tasks by profit in descending order.

●​ Schedule tasks in the latest available slot before the deadline.
●​ If a slot is available, assign the task; otherwise, discard it.

Fractional Knapsack Problem (Greedy Approach)

Given data:

●​ Capacity = 20 Kg
●​ Profits (p): (30, 16, 18, 20, 10, 7)
●​ Weights (w): (5, 4, 6, 4, 5, 7)
●​ Profit/Weight Ratio: (30/5​, 16/4​, 18/6​, 20/4​, 10/5​, 7/7​) = (6,4,3,5,2,1)

Steps:
●​ Sort items by highest p/w ratio:
(p1​
,p4​,p2​,p3​,p5​,p6​)=(30,20,16,18,10,7)
●​ Add items until knapsack is full:

Item Weight Taken Profit Gained

p1​(6) 5 kg 30

p2 (5) 4 kg 20

p3​(4) 4 kg 16

p4​(3) 6 kg 18

p5​(2) 1 kg (fractional) (10/5)×1=2

●​ Total Profit: 30 + 20 + 16 + 18 + 2 = 86.

●​ Maximum profit = 86 with a weight of 20 Kg
(b) Assuming that data to be transmitted consists of only characters ‘a’ to
‘g’, design the Huffman code for the following frequencies of character
data. Show all the steps of building a huffman tree. Also, show how a
coded sequence using Huffman code can be decoded.
​ ​ a:5, b:25, c:10, d:15, e:8, f:7, g:30

Building the Huffman Tree:

1. Initialize a Priority Queue:

We start by placing all the characters into a min-heap based on their frequencies.

Symbol Frequency

a 5

f 7

e 8

c 10

d 15

b 25

g 30

2. Combine the Two Smallest Nodes:

●​ Step 1:
○​ Combine a (5) and f (7).
○​ Create a new node (a,f) with frequency 12.
○​ Insert (a,f) back into the queue.

Symbol Frequency

e 8

c 10

(a,f) 12
d 15

b 25

g 30

●​ Step 2:
○​ Combine e (8) and c (10).
○​ Create a new node (e,c) with frequency 18.
○​ Insert (e,c) back into the queue.

Updated Priority Queue:

Symbol Frequency

(a,f) 12

d 15

(e.c) 18

b 25

g 30

●​ Step 3:
○​ Combine (a,f) (12) and d (15).
○​ Create a new node (a,f,d) with frequency 27.
○​ Insert (a,f,d) back into the queue.

Updated Priority Queue:

Symbol Frequency

(e,c) 18

b 25

(a,f,d) 27

g 30
 ●​ Step 4:
○​ Combine (e,c) (18) and b (25).
○​ Create a new node (e,c,b) with frequency 43.
○​ Insert (e,c,b) back into the queue.

Updated Priority Queue:

Symbol Frequency

(a,f,d) 27

g 30

(e.c.b) 43

●​ Step 5:
○​ Combine (a,f,d) (27) and g (30).
○​ Create a new node (a,f,d,g) with frequency 57.
○​ Insert (a,f,d,g) back into the queue.

Updated Priority Queue:

Symbol Frequency

(e,c,b) 43

(a,f,d,g) 57

●​ Final Step:
○​ Combine (e,c,b) (43) and (a,f,d,g) (57).
○​ Create the root node (a,b,c,d,e,f,g) with frequency 100.

Assigning Codes to Characters:

Now, we'll traverse the tree to assign binary codes to each character. We'll use:

●​ Left Edge: 0
●​ Right Edge: 1
1. Start from the Root:

●​ Root Node (100)

○​ Left Child: (e,c,b) (43)
■​ Code Prefix: 0
○​ Right Child: (a,f,d,g) (57)
■​ Code Prefix: 1

2. Traverse Left Subtree:

●​ Node (e,c,b) (43) with Code Prefix 0

○​ Left Child: (e,c) (18)
■​ Code Prefix: 00
○​ Right Child: b (25)
■​ Code: 01
●​ Traverse (e,c) (18):
○​ Left Child: e (8)
■​ Code: 000
○​ Right Child: c (10)
■​ Code: 001

3. Traverse Right Subtree:

●​ Node (a,f,d,g) (57) with Code Prefix 1

○​ Left Child: (a,f,d) (27)
■​ Code Prefix: 10
○​ Right Child: g (30)
■​ Code: 11
●​ Traverse (a,f,d) (27):
○​ Left Child: (a,f) (12)
■​ Code Prefix: 100
○​ Right Child: d (15)
■​ Code: 101
●​ Traverse (a,f) (12):
○​ Left Child: a (5)
■​ Code: 1000
○​ Right Child: f (7)
 ■​ Code: 1001

Summary of Assigned Huffman Codes:

Character Huffman Code

a 1000

b 01

c 001

d 101

e 000

f 1001

g 11

Decoding a Huffman Encoded Sequence:

Let's decode the sequence: 1000101100001

Step-by-Step Decoding:

1.​ Starting with the first bit 1:

○​ Path: 1
○​ Possible Characters: g, or continue traversing.
2.​ Next bit 0:
○​ Path: 10
○​ Possible Characters: Subtree (a,f,d)
3.​ Next bit 0:
○​ Path: 100
○​ Possible Characters: Subtree (a,f)
4.​ Next bit 0:
 ○​ Path: 1000
○​ Matches a
○​ Decoded Symbol: a

Remaining Sequence: 101100001

5.​ Next bits 1 0 1:

○​ Path: 1 0 1
○​ Matches d
○​ Decoded Symbol: d

Remaining Sequence: 100001

6.​ Next bits 1 0 0 0 0 1:

○​ Decode each symbol similarly.

Let's proceed step by step.

●​ Third Symbol:
○​ Bits: 1 0 0 0
○​ Path: 1 0 0 0
○​ Matches a
○​ Decoded Symbol: a

Remaining Sequence: 01

●​ Fourth Symbol:
○​ Bits: 0 1
○​ Path: 0 1
○​ Matches b
○​ Decoded Symbol: b

Final Decoded Sequence: a d a b

(c) Explain the Merge procedure of the Merge Sort algorithm. Demonstrate
the use of recursive Merge sort algorithm for sorting the following data of
size 8: [19, 18, 16, 12, 11, 10, 9, 8]. Compute the complexity of Merge Sort
algorithm.

Merge Procedure of Merge Sort

The Merge procedure is a key part of the Merge Sort algorithm. It combines two sorted
subarrays into a single sorted array. It works as follows:

1.​ Initialize Pointers:

●​ Use three indices:
○​ i (for left subarray)
○​ j (for right subarray)
○​ k (for merged array)
2.​ Compare and Merge:
●​ Compare the elements from both subarrays.
●​ Copy the smaller element into the merged array.
●​ Move the corresponding index (i or j) forward.
3.​ Copy Remaining Elements:
●​ If elements remain in the left subarray, copy them.
●​ If elements remain in the right subarray, copy them.

Recursive Merge Sort Algorithm

Merge Sort follows the divide-and-conquer approach:

1.​ Divide:
○​ Split the array into two halves recursively.
2.​ Sort:
○​ Recursively sort each half.
3.​ Merge:
○​ Use the Merge procedure to combine the two sorted halves.
Step-by-Step Merge Sort for Given Array

Input Array:
[19, 18, 16, 12, 11, 10, 9, 8]

Step 1: Split the Array

Left: [19, 18, 16, 12]
Right: [11, 10, 9, 8]

Step 2: Recursively Split Each Half

Left → [19, 18] and [16, 12]
Right → [11, 10] and [9, 8]

Step 3: Merge Sorted Subarrays

●​ Merge [19] and [18] → [18, 19]
●​ Merge [16] and [12] → [12, 16]
●​ Merge [11] and [10] → [10, 11]
●​ Merge [9] and [8] → [8, 9]

Update subarrays:
Left: [18, 19] and [12, 16]
Right: [10, 11] and [8, 9]

●​ Merge [18, 19] and [12, 16] → [12, 16, 18, 19]
●​ Merge [10, 11] and [8, 9] → [8, 9, 10, 11]

Left: [12, 16, 18, 19]

Right: [8, 9, 10, 11]

●​ Final Merge:
○​ Merge [12, 16, 18, 19] and [8, 9, 10, 11]
○​ Compare and arrange elements.

Final Sorted Array: [8, 9, 10, 11, 12, 16, 18, 19]
Complexity of Merge Sort

Time Complexity Analysis

●​ Divide Step: The array is divided into two halves recursively.​

→ T(n) = 2T(n/2) + O(n)
●​ Merge Step: Merging two sorted subarrays takes O(n) time.
●​ Recurrence Relation Solving:​
Using Master Theorem:
○​ T(n)=2T(n/2)+O(n)
○​ Solves to O(n log n).

Final Complexity:

●​ Best Case: O(n log n)

●​ Average Case: O(n log n)
●​ Worst Case: O(n log n)

Space Complexity: O(n) (for temporary arrays used in merging)

(d) Explain the divide and conquer approach of multiplying two large
integers. Compute the time complexity of this approach. Also, explain the
binary search algorithm and find its time complexity.

The Divide and Conquer method for multiplication is an efficient way to multiply large
integers by breaking the problem into smaller subproblems and combining the results. A
famous example is Karatsuba’s Algorithm.

Steps for Divide and Conquer Multiplication

1.​ Divide:​
Given two large numbers XXX and YYY, split them into two halves:
●​ Let X=10mA+B
●​ Let Y=10mC+D

where A, B, C, D are the split parts of X and Y, and m is the midpoint.

2.​ Compute Smaller Products:

●​ Multiply A × C (high parts)
 ●​ Multiply B × D (low parts)
●​ Multiply (A + B) × (C + D)

3.​ Combine Results Using Formula:​

X×Y=AC×102m+[(A+B)(C+D)−AC−BD]×10m+BD

This reduces multiplication complexity compared to traditional methods.

Time Complexity of Divide and Conquer Multiplication

For traditional multiplication of two n-digit numbers, the time complexity is O(n²).

Using Karatsuba’s Algorithm, the recurrence relation is: T(n)=3T(n/2)+O(n)

Using Master Theorem, this gives:T(n)=O(nlog 2​3)≈O(n1.585)

This is faster than O(n²).

Binary Search Algorithm

Binary Search is an efficient algorithm to search for an element in a sorted array.

Steps for Binary Search

1.​ Initialize Pointers:

○​ Low pointer (low = 0).
○​ High pointer (high = n-1).
2.​ Find Middle Element:​
mid=(low+high)/2
○​ If arr[mid] == target, return mid (element found).
○​ If arr[mid] > target, search in left half (high = mid - 1).
○​ If arr[mid] < target, search in right half (low = mid + 1).
3.​ Repeat Until low > high.

Time Complexity of Binary Search

Each step reduces the search space by half:

T(n)=T(n/2)+O(1)

Solving this using the Master Theorem gives:

T(n)=O(log⁡n)

●​ Best Case: O(1) (if the middle element is the target).

●​ Worst & Average Case: O(log n).

(e) Explain the Topological sorting with the help of an example. Also,
explain the algorithm of finding strongly connected components in a
directed Graph.

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG)

such that for every directed edge (u → v), vertex u appears before v in the ordering.

Example:

Consider a DAG with the following edges:

5 → 0
5 → 2
4 → 0
4 → 1
2 → 3
3 → 1

Step-by-Step Topological Sorting using DFS:

1.​ Perform DFS on the graph.

2.​ Push each vertex to a stack after exploring all its adjacent nodes.
3.​ Pop elements from the stack to get the topological order.

Execution

●​ Start DFS from 5 → visit 2 → visit 3 → visit 1.

●​ DFS backtracks and visits 4 → visit 0.
Final Topological Order (from stack output):​
[5, 4, 2, 3, 1, 0]

Finding Strongly Connected Components (SCCs)

A strongly connected component (SCC) of a directed graph is a maximal subgraph

where every node is reachable from every other node within that subgraph. Kosaraju’s
Algorithm finds SCCs in O(V + E) time.

Steps:

1.​ First DFS (Original Graph):

○​ Perform DFS and push nodes to a stack when finished.
2.​ Transpose the Graph:
○​ Reverse all edges.
3.​ Second DFS (Transposed Graph):
○​ Pop nodes from the stack and run DFS on the transposed graph.
○​ Each DFS run gives one SCC.

Example:

1→2
2→3
3→1
3→4
4→5
5→4

Step 1: First DFS (Stack Order)

●​ DFS completes 1 → 2 → 3 → 4 → 5.
●​ Stack after DFS: [3, 1, 2, 5, 4].

Step 2: Transpose the Graph

2→1
3→2
1→3
4→3
5→4
4→5

Step 3: Second DFS (On Transposed Graph)

●​ Start popping from stack:

○​ (3, 1, 2) form SCC-1.
○​ (4, 5) form SCC-2.

Final Output:

SCCs = {(1,2,3), (4,5)}

Conclusion

Concept Algorithm Complexity

Topological Sort DFS + Stack O(V + E)

Finding SCCs Kosaraju’s Algorithm O(V + E)

Q3: Consider the following Graph:

a) Write the Prim’s algorithm to find the minimum cost spanning tree of a
graph. Also, find the time complexity of Prim’s algorithm. Demonstrate the
use of Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree for the Graph given in Figure 1. Show all the steps.
> Prim’s Algorithm

1.​ Initialize:
●​ Select any arbitrary node as the starting node.
●​ Create an empty MST set.
●​ Maintain a priority queue (or min heap) for selecting the
minimum-weight edge.

2.​ Grow the MST:

●​ Pick the minimum-weight edge that connects a new vertex to the MST.
●​ Add this edge to the MST.
●​ Update the priority queue with edges connected to the newly added
vertex.

3.​ Repeat Until MST Covers All Vertices.

> Time Complexity of Prim’s Algorithm:

●​ Using an adjacency matrix: O(V²)

●​ Using a priority queue (Min-Heap) with an adjacency list: O(E log V)

> Prim’s Algorithm for MST

Graph from the given figure (Vertices: A, B, C, D, E, F, G)

Edge Weight

A→B 10

A→E 15

B→C 20

B→D 4

C→D 8
C→G 16

D→F 7

E→F 6

F→G 5

Step-by-Step Execution of Prim’s Algorithm:

●​ Start with A.
●​ Choose the smallest edge: A → B (10).
●​ Add B to MST. Smallest edge from B: B → D (4).
●​ Add D. Smallest edge: D → F (7).
●​ Add F. Smallest edge: F → G (5).
●​ Add G. Smallest edge: C → D (8).
●​ Add C. Smallest edge: E → F (6).
●​ Add E.

Final MST Edges:

A → B (10)
B → D (4)
D → F (7)
F → G (5)
C → D (8)
E → F (6)
Total MST cost: 40

> Kruskal’s Algorithm for MST

Algorithm:

1.​ Sort all edges by weight.

2.​ Pick the smallest edge that does not form a cycle.
3.​ Repeat until all vertices are connected.

Time Complexity of Kruskal’s Algorithm:

 ●​ Sorting edges: O(E log E)
●​ Union-Find operations: O(E log V)
●​ Total Complexity: O(E log E + E log V) ≈ O(E log V)

Steps to Find MST:

Step 1: Sort Edges by Weight

Edge Weight

B→D 4

F→G 5

E→F 6

D→F 7

C→D 8

A→B 10

C→G 16

A→E 15

B→C 20

Step 2: Pick the Smallest Edge (Avoid Cycles)

●​ B → D (4)
●​ F → G (5)
●​ E → F (6)
●​ D → F (7)
●​ C → D (8)
●​ A → B (10)

Final MST Edges:

B → D (4)
F → G (5)
E → F (6)
D → F (7)
C → D (8)
A → B (10)

Total MST cost: 40

(b) Write the Dijkstra’s shortest path algorithm. Also, find the time
complexity of this shortest path algorithm. Find the shortest paths
from the vertex ‘A’ using Dijkstra’s shortest path algorithm for the
graph given in Figure 1. Show all the steps of computation.

> Dijkstra’s Shortest Path Algorithm

1.​ Initialize:
●​ Set the distance of the starting vertex to 0 and all others to ∞.
●​ Use a priority queue (min-heap) to select the vertex with the smallest
distance.
2.​ Relax Edges:
●​ Pick the vertex u with the smallest distance.
●​ Update distances for all adjacent vertices v if: d[v]>d[u] + w(u,v)
●​ Push updated vertices into the priority queue.
3.​ Repeat Until All Nodes Are Processed.

Time Complexity
●​ Using a priority queue (Min-Heap + Adjacency List): O((V + E) log V)
●​ Using an adjacency matrix: O(V²)

> Finding Shortest Paths from A (Step-by-Step)

Step 1: Initialization
A: 0, B: ∞, C: ∞, D: ∞, E: ∞, F: ∞, G: ∞

Step 2: Start from A

●​ A → B (10), A → E (15)
A: 0, B: 10, C: ∞, D: ∞, E: 15, F: ∞, G: ∞
Step 3: Pick B (smallest distance)

●​ B → D (10 + 4 = 14)
●​ B → C (10 + 20 = 30)

A: 0, B: 10, C: 30, D: 14, E: 15, F: ∞, G: ∞

Step 4: Pick D (14)

●​ D → F (14 + 7 = 21)
●​ D → C (min(30, 14+8) = 22)

A: 0, B: 10, C: 22, D: 14, E: 15, F: 21, G: ∞

Step 5: Pick E (15)

●​ E → F (min(21, 15+6) = 21) (No change)

Step 6: Pick F (21)

●​ F → G (21 + 5 = 26)
A: 0, B: 10, C: 22, D: 14, E: 15, F: 21, G: 26

Step 7: Pick C (22)

●​ No better path found.

Step 8: Pick G (26)

●​ No more updates.

> Final Shortest Paths from A

Vertex Distance from A Path

A 0 A

B 10 A→B

C 22 A→B→D→C
D 14 A→B→D

E 15 A→E

F 21 A→B→D→F

G 26 A→B→D→F→G

Conclusion

●​ Dijkstra’s Algorithm Complexity: O((V + E) log V)

●​ Shortest path from A to G: 26 (A → B → D → F → G).

(c) Explain the algorithm to find the optimal Binary Search Tree.
Demonstrate this algorithm to find the Optimal Binary Search Tree for
the following probability data (where pi represents the probability that
the search will be for the key node ki, whereas qi represents that the
search is for dummy node di. Make suitable assumptions, if any)
i 0 1 2 3 4

pi 0.10 0.15 0.20 0.10

qi 0.05 0.10 0.10 0.10 0.10

The Optimal Binary Search Tree (OBST) minimizes the expected search cost by
arranging the keys in a way that reduces the weighted path length. This is done using
dynamic programming.

Step-by-Step Algorithm:

1.​ Input:
●​ Probabilities pi​for searching keys ki
●​ Probabilities qi​for searching dummy nodes di
2.​ Define Matrices:
 ●​ Cost Matrix C[i][j] → Minimum cost for searching between keys
ki to kj
●​ Weight Matrix W[i][j] → Sum of all p and q values in the range.
●​ Root Matrix R[i][j] → Stores the root of the subtree.

3.​ Initialization:
●​ C[i][i] = qi​for dummy nodes.
●​ W[i][i] = qi​for dummy nodes.

4.​ Compute OBST using Dynamic Programming:

●​ For every range (i,j) compute:
​ W[i][j] = W[i][j−1] + pj ​
+ qj​
​ C[i][j]=rmin​
(C[i][r−1]+C[r+1][j]+W[i][j])
●​ The minimum cost C[i][j] is chosen by trying each key kr as the root.

5.​ Construct the OBST using the Root Matrix R[i][j].

Applying OBST to the Given Data

Given Probabilities Table:

i 0 1 2 3 4

pi 0.10 0.15 0.20 0.10

qi 0.05 0.10 0.10 0.10 0.10

Step 1: Initialize Matrices

●​ Compute W, C, and R matrices using dynamic programming.

Step 2: Compute W[i][j]

For example:

W[0][1 ]= q0+p1+q1 = 0.05+0.10+0.10 = 0.25

Compute similarly for all W[i][j]

Step 3: Compute C[i][j] Using DP

For small subtrees, set

C[i][i] = qi

Then, recursively find the best root for each range.

Step 4: Construct OBST

Using the R matrix, determine which keys should be the root of each subtree.

Time Complexity

●​ Dynamic programming approach takes O(n3) time.

(d) Given the following sequence of chain multiplication of the

matrices. Find the optimal way of multiplying these matrices.

Matrix Dimension
A1 10 x 15
A2 15 x 5
A3 5 x 20
A4 20 x 10

We have matrices:

●​ A1: 10×15
●​ A2: 15×5
●​ A3: 5×20
●​ A4: 20×10
Step 1: Define Dimensions

Array: p=[10,15,5,20,10]

Step 2: Compute Using DP

Using the Matrix Chain Multiplication formula:

1.​ Cost for 2 matrices

○​ m[1,2]=750
○​ m[2,3]=1500
○​ m[3,4]=1000
2.​ Cost for 3 matrices
○​ m[1,3]=1750
○​ m[2,4]=1750
3.​ Cost for full multiplication
○​ Minimum: m[1,4]=2250

Step 3: Optimal Parenthesization

(A1×(A2×A3))×A4

Therefore,

●​ Optimal Order: (A1(A2A3))A4

●​ Minimum Cost: 2250 multiplications
●​ Time Complexity: O(n3)

(e) Explain the Rabin Karp algorithm for string matching with the help
of an example. Find the time complexity of this algorithm.

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find a

pattern within a text efficiently. Instead of checking each substring one by one, it
computes a hash value and compares it, reducing unnecessary character comparisons.
Algorithm Steps

1.​ Compute the hash value of the pattern and the first window of text.
2.​ Slide the window over the text one character at a time:
○​ If the hash values match, do a character-by-character check.
○​ If they don't match, slide to the next position and update the hash
efficiently.
3.​ Repeat until the end of the text.

Example

Text: "ABCDABCD"​
Pattern: "BCD"​
Using a simple hash function H:

●​ Compute hash of "BCD" → hash = 4

●​ Compute hash of "ABC" (first window) → hash = 3 (not a match)
●​ Compute hash of "BCD" (next window) → hash = 4 (match, verify manually)
●​ Compute hash of "CDA" → hash = 2 (not a match)
●​ Compute hash of "DAB" → hash = 5 (not a match)
●​ Compute hash of "ABC" → hash = 3 (not a match)
●​ Compute hash of "BCD" → hash = 4 (match, verify manually)

Matches found at indices: 1 and 5

Time Complexity

●​ Best/Average Case: O(n+m)O(n + m)O(n+m) (using efficient hashing)

●​ Worst Case: O(nm)O(nm)O(nm) (when hash collisions occur frequently)

This makes Rabin-Karp efficient for multiple pattern searches in large texts.

Q4. a) Explain the term Decision problem with the help of an example.
Define the following problems and identify if they are decision
problem or optimization problem? Give reasons in support of your
answer. ​
(i) Travelling Salesman Problem​
(ii) Graph Colouring Problem ​
(iii) 0-1 Knapsack Problem

A decision problem is a problem that can be posed as a yes/no question regarding the
existence of a solution that satisfies given constraints. In other words, it asks whether a
certain condition or property is true or false.

Example:

●​ Problem: Is there a path in a graph that visits each vertex exactly once and
returns to the starting point?
●​ Yes/No Question: Does a Hamiltonian cycle exist in the given graph?

Decision problems are often used in computational theory and algorithm design to
determine the feasibility of certain solutions before tackling optimization problems.

(i) Travelling Salesman Problem (TSP)

●​ Definition: Given a set of cities and distances between them, find the shortest
possible route that visits each city exactly once and returns to the starting point.
●​ Type: Optimisation Problem
●​ Reason: The goal is to find the shortest route, not just to check if a route exists.

(ii) Graph Colouring Problem

●​ Definition: Given a graph and a number k, can the graph be coloured using k
colours such that no two adjacent vertices have the same colour?
●​ Type: Decision Problem
●​ Reason: The answer is either "Yes" (if the graph can be coloured with k colours)
or "No" (if it cannot be coloured with k colours).

(iii) 0-1 Knapsack Problem

●​ Definition: Given items with weights and values, and a knapsack of limited
capacity, determine the maximum value that can be obtained without exceeding
the capacity.
●​ Type: Optimisation Problem
 ●​ Reason: The goal is to maximise the total value rather than just answering a
yes/no question.

(b) What are P and NP class of Problems? Explain each class with the
help of at least two examples.

P-Class Problems

P (Polynomial time) class problems are those problems that can be solved by a
deterministic algorithm in polynomial time. In simpler terms, if a problem belongs to
class P, there exists an algorithm that can solve the problem in a reasonable amount of
time as the input size grows. These problems are considered efficiently solvable.

Examples:

1.​ Sorting Algorithms:

○​ Problem: Given a list of numbers, sort them in ascending order.
○​ Algorithm: Merge Sort, Quick Sort, and Bubble Sort all run in polynomial
time (e.g., Merge Sort runs in O(n log n) time).
2.​ Shortest Path Problem:
○​ Problem: Given a graph and a source node, find the shortest path from the
source node to all other nodes in the graph.
○​ Algorithm: Dijkstra's algorithm runs in polynomial time (O(V^2) or O(V log
V) with a priority queue), where V is the number of vertices.

NP-Class Problems

NP (Nondeterministic Polynomial time) class problems are those problems for which a
given solution can be verified in polynomial time by a deterministic algorithm. In other
words, if you are given a potential solution to an NP problem, you can quickly check if it
is correct. However, finding the solution from scratch may not be possible in polynomial
time. NP problems are not necessarily efficiently solvable, but their solutions can be
verified efficiently.

Examples:

1.​ Travelling Salesman Problem (TSP):

○​ Problem: Given a list of cities and the distances between each pair of
cities, find the shortest possible route that visits each city exactly once and
returns to the starting city.
 ○​ Verification: If given a proposed route, you can quickly calculate the total
distance and verify if it is indeed the shortest route.
2.​ Subset Sum Problem:
○​ Problem: Given a set of integers, determine if there exists a subset whose
sum is equal to a given target value.
○​ Verification: If given a subset, you can quickly sum the elements and
check if it matches the target value.

Key Differences Between P and NP

Aspect N NP

Definition Problems solvable in polynomial time Problems verifiable in polynomial time

Solution Can be found efficiently May or may not be found efficiently

Verification Solutions can be verified efficiently Solutions can be verified efficiently

Example Problems Shortest Path, Primality Testing TSP, SAT

(c) Define the NP-Hard and NP-Complete problem. How are they
different from each other? Explain the use of polynomial time
reduction with the help of an example.

> NP-Hard Problems:

●​ Definition: NP-Hard problems are at least as hard as the hardest problems in

NP. They do not have to be in NP, meaning they might not even have a solution
that can be verified in polynomial time.
●​ Key Characteristics: A problem XX is NP-Hard if every problem YY in NP can
be polynomial-time reduced to XX. This implies that if we could solve XX in
polynomial time, we could solve every problem in NP in polynomial time as well.
●​ Example: The Halting Problem (deciding whether a given program halts or runs
forever) is NP-Hard but not in NP because it is undecidable and cannot be
verified in polynomial time.

> NP-Complete Problems:

 ●​ Definition: NP-Complete problems are a subset of NP problems that are both in
NP and NP-Hard. This means they can be verified in polynomial time and are at
least as hard as the hardest problems in NP.
●​ Key Characteristics: A problem XX is NP-Complete if:
1.​ XX is in NP.
2.​ Every problem YY in NP can be polynomial-time reduced to XX.
●​ Example: The Satisfiability Problem (SAT) is an NP-Complete problem. Given
a Boolean formula, we can verify a solution in polynomial time, and every
problem in NP can be reduced to SAT.

> Differences

Feature NP-Hard NP-Complete

Belongs to NP? Not necessarily Yes

Verification in P time? May not be possible Yes

Hardness At least as hard as NP problems Hardest problems in NP

Example Halting Problem 3-SAT, Hamiltonian Cycle

> Polynomial Time Reduction

Polynomial time reduction is a method to transform one problem into another in

polynomial time. If Problem A is reducible to Problem B in polynomial time, solving B
helps solve A efficiently.

Example

Consider 3-SAT and Clique Problem:

1.​ 3-SAT is a decision problem where we check if a boolean formula in CNF can be
satisfied.
2.​ We can reduce any instance of 3-SAT to the Clique Problem in polynomial time
by constructing a graph such that finding a clique of a specific size corresponds
to satisfying the formula.
3.​ Since 3-SAT is NP-Complete, and we reduced it to Clique, Clique is also
NP-Hard.
This method helps in proving problems are NP-Hard or NP-Complete.

(d) Define the following Problems:

I.​ SAT Problem

II.​ Clique problem
III.​ Hamiltonian Cycle Problem
IV.​ Subset Sum Problem

​
​
​
(a) SAT Problem (Boolean Satisfiability Problem)

Definition: The SAT problem is the first problem that was proven to be NP-Complete. It
asks whether there exists an assignment of truth values (true or false) to the variables
of a Boolean formula such that the formula evaluates to true.

Example: Given the Boolean formula: (A∨¬B)∧(B∨C)∧(¬A∨C)

●​ Question: Is there an assignment of truth values to A, B, and C that makes the

formula true?
●​ Answer: Yes, one such assignment could be A=true,B=false,C=true

(b) Clique Problem

Definition: The Clique problem asks whether there exists a subset of vertices in a given
graph such that every pair of vertices in the subset is connected by an edge, and the
size of the subset (clique) is at least kk.

Example: Given a graph with vertices V={1,2,3,4} and edges

E={(1,2),(2,3),(3,4),(1,3)}

●​ Question: Is there a clique of size 3?

●​ Answer: Yes, the vertices {1,2,3} form a clique of size 3.
(c) Hamiltonian Cycle Problem

Definition: The Hamiltonian Cycle problem asks whether there exists a cycle in a given
graph that visits each vertex exactly once and returns to the starting vertex.

Example: Given a graph with vertices V={A,B,C,D} and edges

E={(A,B),(B,C),(C,D),(D,A),(A,C)}

●​ Question: Is there a Hamiltonian cycle?

●​ Answer: Yes, one such cycle is A→B→C→D→A

(d) Subset Sum Problem

Definition: The Subset Sum problem asks whether there exists a subset of a given set
of integers such that the sum of the subset is equal to a given target value.

Example: Given the set of integers {3,34,4,12,5,2} and a target sum of 9:

●​ Question: Is there a subset whose sum is 9?

●​ Answer: Yes, the subset {4,5} sums to 9.

These problems are central to the study of computational complexity, particularly in

understanding the boundaries between efficiently solvable problems (P class) and those
that are believed to be inherently difficult (NP class). Each problem has real-world
applications and highlights the diverse challenges in algorithm design and optimization.