Free MCS-211 Solved Assignment | July 2025 | MCA_NEW, MCAOL | English & Hindi Medium | IGNOU

Abstract Classes ®

Question:-1(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?

Answer:

🔍 Sieve of Eratosthenes Algorithm for Primes (501 to 2000)

🧠 Step 1: Algorithm Design

  1. Create a boolean list is_prime[0..2000], initialize all entries as True.
  2. Mark is_prime[0] and is_prime[1] as False.
  3. For i = 2 i = 2 i=2i = 2i=2 to 2000 44 2000 44 sqrt2000~~44\sqrt{2000} \approx 44200044:
    • If is_prime[i] is True, mark all multiples of i i iii (from i 2 i 2 i^(2)i^2i2 to 2000) as False.
  4. Extract all primes between 501 and 2000 where is_prime[i] is True.

⚙️ Step 2: Pseudocode

n = 2000
is_prime = [True] * (n+1)
is_prime[0] = False
is_prime[1] = False

for i from 2 to int(sqrt(n)) + 1:
    if is_prime[i] is True:
        for j from i*i to n, step i:
            is_prime[j] = False

primes = []
for k from 501 to n:
    if is_prime[k]:
        primes.append(k)

⏱️ Step 3: Complexity Analysis

  • Time Complexity: O ( n log log n ) O ( n log log n ) O(n log log n)O(n \log \log n)O(nloglogn)
    (Efficient due to inner loop marking multiples only for primes)
  • Space Complexity: O ( n ) O ( n ) O(n)O(n)O(n)
    (For the boolean list of size 2001)

✅ Why Efficient?

  • Eliminates multiples of each prime starting from i 2 i 2 i^(2)i^2i2, reducing redundant checks.
  • Optimal for fixed ranges like 501–2000.

🧾 Example Output (First 5 primes in range):

  • 503, 509, 521, 523, 541...

🎯 Conclusion:
Sieve of Eratosthenes is optimal for generating primes in a contiguous range due to its near-linear time complexity.

Question:-1(b)

Differentiate between Cubic-time and Factorial-time algorithms. Give example of one algorithm each for these two running times.

Answer:

⏱️ Cubic-Time vs. Factorial-Time Algorithms

🧊 Cubic-Time Algorithms

  • Time Complexity: O ( n 3 ) O ( n 3 ) O(n^(3))O(n^3)O(n3)
  • Description: Running time grows proportional to the cube of the input size.
  • Example:
    3 nested loops that each iterate n n nnn times:
    for i in range(n):
        for j in range(n):
            for k in range(n):
                # constant-time operation
    
    Real-world example: Naive matrix multiplication for two n × n n × n n xx nn \times nn×n matrices.

🧮 Factorial-Time Algorithms

  • Time Complexity: O ( n ! ) O ( n ! ) O(n!)O(n!)O(n!)
  • Description: Running time grows factorial with input size (extremely fast).
  • Example:
    Generating all permutations of n n nnn distinct elements:
    def generate_permutations(arr, start=0):
        if start == len(arr):
            print(arr)
        for i in range(start, len(arr)):
            swap(arr, start, i)
            generate_permutations(arr, start+1)
            swap(arr, start, i)  # backtrack
    
    Real-world example: Solving the Traveling Salesman Problem via brute-force.

📊 Key Differences:

Aspect Cubic-Time ( O ( n 3 ) O ( n 3 ) O(n^(3))O(n^3)O(n3)) Factorial-Time ( O ( n ! ) O ( n ! ) O(n!)O(n!)O(n!))
Growth Rate Moderate Explosive
Feasibility Practical for small n n nnn Impractical even for small n n nnn (e.g., n > 10 n > 10 n > 10n > 10n>10)
Use Case Matrix operations Combinatorial problems

Question:-1(c)

Write an algorithm to multiply two square matrices of order n × n n × n n xx nn \times nn×n. Also explain the time complexity of this algorithm.

Answer:

🔢 Algorithm for Matrix Multiplication (n × n)
Input: Two matrices A A AAA and B B BBB of size n × n n × n n xx nn \times nn×n
Output: Product matrix C = A × B C = A × B C=A xx BC = A \times BC=A×B of size n × n n × n n xx nn \times nn×n

📝 Algorithm Steps:

  1. Initialize a result matrix C C CCC of size n × n n × n n xx nn \times nn×n with zeros.
  2. For each row i i iii from 0 to n 1 n 1 n-1n-1n1:
    • For each column j j jjj from 0 to n 1 n 1 n-1n-1n1:
      • Set C [ i ] [ j ] = 0 C [ i ] [ j ] = 0 C[i][j]=0C[i][j] = 0C[i][j]=0
      • For each index k k kkk from 0 to n 1 n 1 n-1n-1n1:
        • C [ i ] [ j ] + = A [ i ] [ k ] × B [ k ] [ j ] C [ i ] [ j ] + = A [ i ] [ k ] × B [ k ] [ j ] C[i][j]+=A[i][k]xx B[k][j]C[i][j] += A[i][k] \times B[k][j]C[i][j]+=A[i][k]×B[k][j]
  3. Return C C CCC

🧮 Example:

Let A = [ a b c d ] A = a b c d A=[[a,b],[c,d]]A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}A=[abcd], B = [ e f g h ] B = e f g h B=[[e,f],[g,h]]B = \begin{bmatrix} e & f \\ g & h \end{bmatrix}B=[efgh]
Then C = [ a e + b g a f + b h c e + d g c f + d h ] C = a e + b g a f + b h c e + d g c f + d h C=[[ae+bg,af+bh],[ce+dg,cf+dh]]C = \begin{bmatrix} ae+bg & af+bh \\ ce+dg & cf+dh \end{bmatrix}C=[ae+bgaf+bhce+dgcf+dh]

⏱️ Time Complexity:

  • 3 nested loops, each running n n nnn times.
  • Total operations: n × n × n = n 3 n × n × n = n 3 n xx n xx n=n^(3)n \times n \times n = n^3n×n×n=n3
  • Time Complexity: O ( n 3 ) O ( n 3 ) O(n^(3))O(n^3)O(n3)


Question:-1(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 Θ Θ Theta\ThetaΘ notation with the help of a diagram. Find the Big O-notation and Θ Θ Theta\ThetaΘ-notation for the function: f ( n ) = 100 n 4 + 1000 n 3 + 100000 f ( n ) = 100 n 4 + 1000 n 3 + 100000 f(n)=100n^(4)+1000n^(3)+100000f(n) = 100n^4 + 1000n^3 + 100000f(n)=100n4+1000n3+100000

Answer:

📈 Asymptotic Bounds for Algorithm Efficiency

🔍 What are Asymptotic Bounds?

Asymptotic bounds describe how an algorithm’s resource usage (time or space) grows as the input size n n nnn approaches infinity. They provide a high-level understanding of efficiency without constant factors or lower-order terms.

🎯 Why Use Asymptotic Bounds?

  • Simplification: Ignore constants and focus on growth rate.
  • Comparison: Easily compare algorithms based on scalability.
  • Predictive: Help estimate performance for large inputs.

⚠️ Shortcomings:

  • Ignore constants: May mislead for small inputs (e.g., O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2) might be faster than O ( n ) O ( n ) O(n)O(n)O(n) for small n n nnn if constants are large).
  • Not exact: Do not give actual running time, only growth trend.
  • Worst-case focus: Some bounds (e.g., Big O) often describe worst-case, not average or best-case.

📊 Big O and Big Θ Θ Theta\ThetaΘ Notation

  • Big O ( O O OOO): Upper bound (worst-case growth rate).
    Example: f ( n ) = O ( g ( n ) ) f ( n ) = O ( g ( n ) ) f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) means f f fff grows at most as fast as g g ggg.
  • Big Theta ( Θ Θ Theta\ThetaΘ): Tight bound (both upper and lower bounds).
    Example: f ( n ) = Θ ( g ( n ) ) f ( n ) = Θ ( g ( n ) ) f(n)=Theta(g(n))f(n) = \Theta(g(n))f(n)=Θ(g(n)) means f f fff grows exactly as fast as g g ggg (within constant factors).

📉 Diagram Concept:

Growth Rate:
^
| Big O: f(n) ≤ c·g(n) (above curve)
| Big Θ: c₁·g(n) ≤ f(n) ≤ c₂·g(n) (sandwiched)
|
|----------------------------------> n

🧮 For f ( n ) = 100 n 4 + 1000 n 3 + 100000 f ( n ) = 100 n 4 + 1000 n 3 + 100000 f(n)=100n^(4)+1000n^(3)+100000f(n) = 100n^4 + 1000n^3 + 100000f(n)=100n4+1000n3+100000:

  • Dominant term: 100 n 4 100 n 4 100n^(4)100n^4100n4 (highest power).
  • Big O: O ( n 4 ) O ( n 4 ) O(n^(4))O(n^4)O(n4) (since f ( n ) c n 4 f ( n ) c n 4 f(n) <= c*n^(4)f(n) \leq c \cdot n^4f(n)cn4 for c = 1000 c = 1000 c=1000c = 1000c=1000, n n 0 n n 0 n >= n_(0)n \geq n_0nn0).
  • Big Θ: Θ ( n 4 ) Θ ( n 4 ) Theta(n^(4))\Theta(n^4)Θ(n4) (since c 1 n 4 f ( n ) c 2 n 4 c 1 n 4 f ( n ) c 2 n 4 c_(1)n^(4) <= f(n) <= c_(2)n^(4)c_1 n^4 \leq f(n) \leq c_2 n^4c1n4f(n)c2n4 for c 1 = 100 c 1 = 100 c_(1)=100c_1 = 100c1=100, c 2 = 1000 c 2 = 1000 c_(2)=1000c_2 = 1000c2=1000, n n 0 n n 0 n >= n_(0)n \geq n_0nn0).

✅ Final Notations:

  • Big O: O ( n 4 ) O ( n 4 ) O(n^(4))O(n^4)O(n4)
  • Big Θ: Θ ( n 4 ) Θ ( n 4 ) Theta(n^(4))\Theta(n^4)Θ(n4)

Question:-1(e)

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

Answer:

🔢 Left-to-Right Binary Exponentiation Algorithm

This algorithm efficiently computes a n a n a^(n)a^nan by processing the exponent n n nnn in binary form from left to right (most significant bit first). It reduces the number of multiplications by using squaring and conditional multiplication.

📝 Algorithm Steps:

  1. Convert n n nnn to binary. Let b b bbb be the binary digits.
  2. Initialize result r = 1 r = 1 r=1r = 1r=1.
  3. For each binary digit b i b i b_(i)b_ibi (from left to right):
    • r = r × r r = r × r r=r xx rr = r \times rr=r×r (square)
    • If b i = 1 b i = 1 b_(i)=1b_i = 1bi=1:
      • r = r × a r = r × a r=r xx ar = r \times ar=r×a (multiply by base)
  4. Return r r rrr.

🧮 Compute 3 29 3 29 3^(29)3^{29}329:

  • Binary of 29: 11101 11101 111011110111101 (left-to-right: 1,1,1,0,1)
  • Steps:
Step Bit Operation Value
1 1 r = 1 2 × 3 r = 1 2 × 3 r=1^(2)xx3r = 1^2 \times 3r=12×3 3
2 1 r = 3 2 × 3 r = 3 2 × 3 r=3^(2)xx3r = 3^2 \times 3r=32×3 27
3 1 r = 27 2 × 3 r = 27 2 × 3 r=27^(2)xx3r = 27^2 \times 3r=272×3 2187
4 0 r = 2187 2 r = 2187 2 r=2187^(2)r = 2187^2r=21872 4782969
5 1 r = 4782969 2 × 3 r = 4782969 2 × 3 r=4782969^(2)xx3r = 4782969^2 \times 3r=47829692×3 68630377364883
Result: 3 29 = 68630377364883 3 29 = 68630377364883 3^(29)=686303773648833^{29} = 68630377364883329=68630377364883

⏱️ Worst-Case Complexity:

  • Number of bits: log 2 n + 1 log 2 n + 1 |__log_(2)n __|+1\lfloor \log_2 n \rfloor + 1log2n+1
  • Each step requires a square (and sometimes a multiply).
  • Total operations: O ( log n ) O ( log n ) O(log n)O(\log n)O(logn) multiplications.
This is efficient for large exponents! 🚀

Question:-1(f)

Write and explain the Bubble sort algorithm. Discuss its best and worst-case time complexity.

Answer:

🔁 Bubble Sort Algorithm
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

📝 Algorithm Steps:
  1. Start with an unsorted list of n n nnn elements.
  2. For each pass from i = 0 i = 0 i=0i = 0i=0 to n 1 n 1 n-1n-1n1:
    • For each element from j = 0 j = 0 j=0j = 0j=0 to n i 1 n i 1 n-i-1n-i-1ni1:
      • Compare a r r [ j ] a r r [ j ] arr[j]arr[j]arr[j] and a r r [ j + 1 ] a r r [ j + 1 ] arr[j+1]arr[j+1]arr[j+1].
      • If a r r [ j ] > a r r [ j + 1 ] a r r [ j ] > a r r [ j + 1 ] arr[j] > arr[j+1]arr[j] > arr[j+1]arr[j]>arr[j+1], swap them.
  3. Repeat until no swaps are needed in a full pass.

Example:
Sort: [5, 2, 9, 1]
  • Pass 1: [2, 5, 1, 9]
  • Pass 2: [2, 1, 5, 9]
  • Pass 3: [1, 2, 5, 9] → Sorted

⏱️ Time Complexity:
  • Worst-case (reverse sorted): O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2)
  • Best-case (already sorted): O ( n ) O ( n ) O(n)O(n)O(n) (with optimized check)
  • Average-case: O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2)


Question:-1(g)

What are the uses of recurrence relations? Solve the following recurrence relations using the Master’s method:

a . T ( n ) = 4 T ( n 4 ) + n a . T ( n ) = 4 T n 4 + n a.T(n)=4T((n)/(4))+na.\ T(n) = 4T\left(\frac{n}{4}\right) + na. T(n)=4T(n4)+n
b . T ( n ) = 4 T ( 3 n 4 ) + n b . T ( n ) = 4 T 3 n 4 + n b.T(n)=4T((3n)/(4))+nb.\ T(n) = 4T\left(\frac{3n}{4}\right) + nb. T(n)=4T(3n4)+n

Answer:

📈 Uses of Recurrence Relations

  • Analyzing algorithm efficiency (e.g., divide-and-conquer algorithms).
  • Modeling problems in computer science, engineering, and mathematics.
  • Predicting time/space complexity of recursive functions.

🧮 Master’s Method

The Master Theorem solves recurrences of the form:
T ( n ) = a T ( n b ) + f ( n ) T ( n ) = a T n b + f ( n ) T(n)=aT((n)/(b))+f(n)T(n) = aT\left(\frac{n}{b}\right) + f(n)T(n)=aT(nb)+f(n)
Compare f ( n ) f ( n ) f(n)f(n)f(n) with n log b a n log b a n^(log _(b)a)n^{\log_b a}nlogba to determine the case.

🔹 (a) T ( n ) = 4 T ( n 4 ) + n T ( n ) = 4 T n 4 + n T(n)=4T((n)/(4))+nT(n) = 4T\left(\frac{n}{4}\right) + nT(n)=4T(n4)+n

  • a = 4 a = 4 a=4a = 4a=4, b = 4 b = 4 b=4b = 4b=4, f ( n ) = n f ( n ) = n f(n)=nf(n) = nf(n)=n
  • n log b a = n log 4 4 = n 1 = n n log b a = n log 4 4 = n 1 = n n^(log _(b)a)=n^(log_(4)4)=n^(1)=nn^{\log_b a} = n^{\log_4 4} = n^1 = nnlogba=nlog44=n1=n
  • Since f ( n ) = n = Θ ( n log b a ) f ( n ) = n = Θ ( n log b a ) f(n)=n=Theta(n^(log _(b)a))f(n) = n = \Theta(n^{\log_b a})f(n)=n=Θ(nlogba), Case 2 applies.
  • Solution: T ( n ) = Θ ( n log b a log n ) = Θ ( n log n ) T ( n ) = Θ ( n log b a log n ) = Θ ( n log n ) T(n)=Theta(n^(log _(b)a)log n)=Theta(n log n)T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)T(n)=Θ(nlogbalogn)=Θ(nlogn)

🔹 (b) T ( n ) = 4 T ( 3 n 4 ) + n T ( n ) = 4 T 3 n 4 + n T(n)=4T((3n)/(4))+nT(n) = 4T\left(\frac{3n}{4}\right) + nT(n)=4T(3n4)+n

  • a = 4 a = 4 a=4a = 4a=4, b = 4 3 b = 4 3 b=(4)/(3)b = \frac{4}{3}b=43, f ( n ) = n f ( n ) = n f(n)=nf(n) = nf(n)=n
  • n log b a = n log 4 / 3 4 n log b a = n log 4 / 3 4 n^(log _(b)a)=n^(log_(4//3)4)n^{\log_b a} = n^{\log_{4/3} 4}nlogba=nlog4/34.
    Note: log 4 / 3 4 > 1 log 4 / 3 4 > 1 log_(4//3)4 > 1\log_{4/3} 4 > 1log4/34>1 (since 4 / 3 < 4 4 / 3 < 4 4//3 < 44/3 < 44/3<4), so n log b a n log b a n^(log _(b)a)n^{\log_b a}nlogba grows faster than n n nnn.
  • Specifically, log 4 / 3 4 4.82 log 4 / 3 4 4.82 log_(4//3)4~~4.82\log_{4/3} 4 \approx 4.82log4/344.82, so n log b a n 4.82 n log b a n 4.82 n^(log _(b)a)~~n^(4.82)n^{\log_b a} \approx n^{4.82}nlogban4.82.
  • Since f ( n ) = n = O ( n log b a ε ) f ( n ) = n = O ( n log b a ε ) f(n)=n=O(n^(log _(b)a-epsi))f(n) = n = O(n^{\log_b a - \varepsilon})f(n)=n=O(nlogbaε) for some ε > 0 ε > 0 epsi > 0\varepsilon > 0ε>0, Case 1 applies.
  • Solution: T ( n ) = Θ ( n log 4 / 3 4 ) T ( n ) = Θ ( n log 4 / 3 4 ) T(n)=Theta(n^(log_(4//3)4))T(n) = \Theta(n^{\log_{4/3} 4})T(n)=Θ(nlog4/34)

✅ Final Answers:

  • (a) Θ ( n log n ) Θ ( n log n ) Theta(n log n)\Theta(n \log n)Θ(nlogn)
  • (b) Θ ( n log 4 / 3 4 ) Θ ( n log 4 / 3 4 ) Theta(n^(log_(4//3)4))\Theta(n^{\log_{4/3} 4})Θ(nlog4/34) (exponential in log, but often simplified as Θ ( n 4.82 ) Θ ( n 4.82 ) Theta(n^(4.82))\Theta(n^{4.82})Θ(n4.82))

Question:-2(a)

What is an Optimisation Problem? Explain with the help of an example. When would you use a Greedy Approach to solve optimisation problem? Formulate the Task Scheduling Problem as an optimisation problem and write a greedy algorithm to solve this problem. Also, solve the following fractional Knapsack problem using greedy approach. Show all the steps. Suppose there is a knapsack of capacity 20 Kg and the following 6 items are to be packed in it. The weight and profit of the items are as under:

( p 1 , p 2 , , p 6 ) = ( 30 , 16 , 18 , 20 , 10 , 7 ) ( p 1 , p 2 , , p 6 ) = ( 30 , 16 , 18 , 20 , 10 , 7 ) (p_(1),p_(2),dots,p_(6))=(30,16,18,20,10,7)(p_1, p_2, \ldots, p_6) = (30, 16, 18, 20, 10, 7)(p1,p2,,p6)=(30,16,18,20,10,7)
( w 1 , w 2 , , w 6 ) = ( 5 , 4 , 6 , 4 , 5 , 7 ) ( w 1 , w 2 , , w 6 ) = ( 5 , 4 , 6 , 4 , 5 , 7 ) (w_(1),w_(2),dots,w_(6))=(5,4,6,4,5,7)(w_1, w_2, \ldots, w_6) = (5, 4, 6, 4, 5, 7)(w1,w2,,w6)=(5,4,6,4,5,7)
Select a subset of the items that maximises the profit while keeping the total weight below or equal to the given capacity.

Answer:

🎯 Optimization Problem

An optimization problem involves finding the best solution from all feasible solutions, typically to maximize or minimize a function under constraints.
Example:
Finding the shortest path between two cities on a map.

⚡ Greedy Approach

Use a greedy approach when:
  • The problem has the greedy choice property (local optimal choices lead to global optimum).
  • It has optimal substructure (solution to subproblems helps solve the main problem).

📅 Task Scheduling as Optimization

Problem: Schedule tasks to maximize the number of non-overlapping tasks.
Formulation:
  • Each task has start and end times.
  • Goal: Select maximum tasks without overlap.
Greedy Algorithm:
  1. Sort tasks by end time.
  2. Select first task.
  3. For each next task, if start ≥ last end time, select it.

🎒 Fractional Knapsack Problem

Capacity: 20 kg
Items:
Item Profit Weight Profit/Weight
1 30 5 6.0
2 16 4 4.0
3 18 6 3.0
4 20 4 5.0
5 10 5 2.0
6 7 7 1.0
Greedy Steps:
  1. Sort by profit/weight (descending):
    Order: Item1 (6.0), Item4 (5.0), Item2 (4.0), Item3 (3.0), Item5 (2.0), Item6 (1.0)
  2. Add items fully until capacity allows:
    • Item1: w=5, p=30 → cap=15, profit=30
    • Item4: w=4, p=20 → cap=11, profit=50
    • Item2: w=4, p=16 → cap=7, profit=66
    • Item3: w=6 > cap=7? Add fraction: (7/6)*18 = 21 → profit=66+21=87, cap=0
Max Profit: 87 ✅

Question:-2(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 a : 5 , b : 25 , c : 10 , d : 15 , e : 8 , f : 7 , g : 30 a:5,b:25,c:10,d:15,e:8,f:7,g:30a: 5,\ b: 25,\ c: 10,\ d: 15,\ e: 8,\ f: 7,\ g: 30a:5, b:25, c:10, d:15, e:8, f:7, g:30

Answer:

🌳 Huffman Coding Steps

📊 Given Frequencies:

Char Freq
a 5
b 25
c 10
d 15
e 8
f 7
g 30

🔨 Step 1: Build Huffman Tree

  1. Sort by frequency (ascending):
    a:5, f:7, e:8, c:10, d:15, b:25, g:30
  2. Merge two smallest (a:5 + f:7 = 12):
    New list:
    e:8, c:10, 12, d:15, b:25, g:30
    (Node: a+f → 12)
  3. Merge next two (e:8 + c:10 = 18):
    New list:
    12, 18, d:15, b:25, g:30
  4. Merge 12 and d:15 = 27:
    New list:
    18, 27, b:25, g:30
  5. Merge 18 and b:25 = 43:
    New list:
    27, 43, g:30
  6. Merge 27 and g:30 = 57:
    New list:
    43, 57
  7. Merge 43 and 57 = 100 (root)

🧩 Huffman Tree Structure:

         (100)
        /     \
     (43)     (57)
    /    \    /   \
 (18)   (25)b (27) (30)g
 /   \      /   \
(8)e (10)c (12) (15)d
         /   \
       (5)a  (7)f

🔤 Huffman Codes (Assign 0/0 to left/right):

  • g: 11
  • b: 01
  • d: 101
  • c: 001
  • e: 000
  • a: 1000
  • f: 1001

🔍 Decoding a Coded Sequence

Example: Decode 11011001000 (Assume: g=11, b=01, d=101, etc.)
  • Start at root.
  • Read bits:
    • 11 → g
    • 01 → b
    • 10 → partial (d? Wait, d=101, so need more)
    • 101 → d
    • 000 → e
Decoded: g, b, d, e

✅ Summary:

  • Huffman codes are variable-length, prefix-free.
  • Decoding traverses tree until a leaf is reached.

Question:-2(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.

Answer:

🔄 Merge Procedure in Merge Sort

The merge procedure combines two sorted subarrays into a single sorted array. It works by:
  1. Comparing the smallest elements of each subarray.
  2. Taking the smaller element and placing it in the result.
  3. Repeating until all elements are merged.

🧩 Example Merge:

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

🧠 Recursive Merge Sort on [19,18,16,12,11,10,9,8]

Step 1: Split recursively
  • [19,18,16,12] and [11,10,9,8]
  • [19,18] and [16,12]; [11,10] and [9,8]
  • [19] and [18]; [16] and [12]; [11] and [10]; [9] and [8]
Step 2: Merge pairs
  • Merge [19] & [18] → [18,19]
  • Merge [16] & [12] → [12,16]
  • Merge [11] & [10] → [10,11]
  • Merge [9] & [8] → [8,9]
Step 3: Merge groups
  • Merge [18,19] & [12,16] → [12,16,18,19]
  • Merge [10,11] & [8,9] → [8,9,10,11]
Step 4: Final merge
  • Merge [12,16,18,19] & [8,9,10,11] → [8,9,10,11,12,16,18,19]

⏱️ Complexity Analysis

  • Time: O ( n log n ) O ( n log n ) O(n log n)O(n \log n)O(nlogn) in all cases (split and merge steps).
  • Space: O ( n ) O ( n ) O(n)O(n)O(n) for temporary arrays.

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

Question:-2(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.

Answer:

🧮 Divide and Conquer for Large Integer Multiplication

📦 Approach:

Split two n n nnn-digit numbers x x xxx and y y yyy into halves:
x = a 10 n / 2 + b , y = c 10 n / 2 + d x = a 10 n / 2 + b , y = c 10 n / 2 + d x=a*10^(n//2)+b,quad y=c*10^(n//2)+dx = a \cdot 10^{n/2} + b, \quad y = c \cdot 10^{n/2} + dx=a10n/2+b,y=c10n/2+d
Then:
x y = ( a c ) 10 n + ( a d + b c ) 10 n / 2 + ( b d ) x y = ( a c ) 10 n + ( a d + b c ) 10 n / 2 + ( b d ) x*y=(a*c)*10 ^(n)+(a*d+b*c)*10^(n//2)+(b*d)x \cdot y = (a \cdot c) \cdot 10^n + (a \cdot d + b \cdot c) \cdot 10^{n/2} + (b \cdot d)xy=(ac)10n+(ad+bc)10n/2+(bd)
Recursively compute a c a c a*ca \cdot cac, a d a d a*da \cdot dad, b c b c b*cb \cdot cbc, b d b d b*db \cdot dbd.

⏱️ Time Complexity:

  • Recurrence: T ( n ) = 4 T ( n / 2 ) + O ( n ) T ( n ) = 4 T ( n / 2 ) + O ( n ) T(n)=4T(n//2)+O(n)T(n) = 4T(n/2) + O(n)T(n)=4T(n/2)+O(n)
  • Using Master Theorem: O ( n log 2 4 ) = O ( n 2 ) O ( n log 2 4 ) = O ( n 2 ) O(n^(log_(2)4))=O(n^(2))O(n^{\log_2 4}) = O(n^2)O(nlog24)=O(n2)
    (Same as school method, but Karatsuba improves to O ( n 1.58 ) O ( n 1.58 ) O(n^(1.58))O(n^{1.58})O(n1.58))

🔍 Binary Search Algorithm

🎯 Steps:

  1. Start with sorted array.
  2. Compare target with middle element.
  3. If equal, return index.
  4. If target < middle, search left half.
  5. If target > middle, search right half.
  6. Repeat until found or subarray size becomes 0.

⏱️ Time Complexity:

  • Each step halves the search space.
  • Recurrence: T ( n ) = T ( n / 2 ) + O ( 1 ) T ( n ) = T ( n / 2 ) + O ( 1 ) T(n)=T(n//2)+O(1)T(n) = T(n/2) + O(1)T(n)=T(n/2)+O(1)
  • Solution: O ( log n ) O ( log n ) O(log n)O(\log n)O(logn)

Summary:
  • Integer Multiplication: O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2) with divide and conquer (baseline).
  • Binary Search: O ( log n ) O ( log n ) O(log n)O(\log n)O(logn) for sorted arrays.

Question:-2(e)

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

Answer:

🔝 Topological Sorting

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge u v u v u rarr vu \to vuv, vertex u u uuu comes before v v vvv in the ordering. It is used to schedule tasks with dependencies.

📌 Example:

Consider a DAG with edges:
A C A C A rarr CA \to CAC, B C B C B rarr CB \to CBC, B D B D B rarr DB \to DBD, C E C E C rarr EC \to ECE, D E D E D rarr ED \to EDE
Valid topological orders:
  • A , B , C , D , E A , B , C , D , E A,B,C,D,EA, B, C, D, EA,B,C,D,E
  • B , A , D , C , E B , A , D , C , E B,A,D,C,EB, A, D, C, EB,A,D,C,E
    (Note: A A AAA and B B BBB have no constraints relative to each other)

⚙️ Algorithm (Kahn’s Algorithm):

  1. Compute in-degree (number of incoming edges) for each vertex.
  2. Enqueue all vertices with in-degree 0.
  3. While queue not empty:
    • Dequeue a vertex u u uuu, add it to the topological order.
    • For each neighbor v v vvv of u u uuu:
      • Reduce in-degree of v v vvv by 1.
      • If in-degree becomes 0, enqueue v v vvv.

🔄 Strongly Connected Components (SCCs)

A strongly connected component of a directed graph is a maximal subgraph where every vertex is reachable from every other vertex.

⚙️ Algorithm (Kosaraju’s Algorithm):

  1. Step 1: Perform DFS on the graph to compute finishing times.
  2. Step 2: Compute the transpose graph (reverse all edges).
  3. Step 3: Perform DFS on the transpose graph in decreasing order of finishing times.
Each DFS tree in step 3 is an SCC.

📌 Example:

Graph:
A B A B A rarr BA \to BAB, B C B C B rarr CB \to CBC, C A C A C rarr AC \to ACA, C D C D C rarr DC \to DCD, D E D E D rarr ED \to EDE, E D E D E rarr DE \to DED
SCCs:
  • { A , B , C } { A , B , C } {A,B,C}\{A, B, C\}{A,B,C} (cycle)
  • { D , E } { D , E } {D,E}\{D, E\}{D,E} (cycle)


Question:-3(a)

Consider the following Graph:
KfHDGGS.png

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.

Answer:

Prim’s Algorithm for Minimum Spanning Tree (MST)

Prim’s algorithm is a greedy algorithm that finds the MST of a connected, undirected, weighted graph. It starts from an arbitrary vertex and grows the MST by repeatedly adding the smallest-weight edge that connects a vertex in the MST to a vertex outside of it.

Pseudocode

PrimMST(Graph G = (V, E), weights w: E → R, start_vertex s ∈ V):
    // Initialize
    MST = empty set  // Set of edges in the MST
    inMST = array of size |V|, initialized to False  // Tracks vertices in MST
    key = array of size |V|, initialized to infinity  // Minimum weight to connect to MST
    parent = array of size |V|, initialized to -1  // Parent in MST
    
    key[s] = 0  // Start from s
    
    // Use a priority queue (min-heap) to select minimum key vertex
    PQ = priority_queue of all vertices, keyed by key values
    
    while PQ is not empty:
        u = extract_min(PQ)  // Vertex with smallest key not in MST
        inMST[u] = True
        
        for each neighbor v of u:
            if not inMST[v] and w(u, v) < key[v]:
                key[v] = w(u, v)
                parent[v] = u
                update PQ with new key for v  // Decrease key operation
    
    // Construct MST edges from parent array (excluding root)
    for each v in V except s:
        add edge (parent[v], v) to MST with weight key[v]
    
    return MST

How to Arrive at the Solution

  • Initialization: Start with a single vertex (arbitrary choice) in the MST. Set its key to 0 and others to infinity.
  • Growth: Use a priority queue to always pick the next vertex outside the MST with the smallest connecting edge. Update keys for its neighbors if a better edge is found.
  • Termination: Continues until all vertices are included (|V| - 1 edges in MST).
  • This ensures the MST is built by always choosing the locally optimal (smallest) safe edge, guaranteeing global optimality for undirected graphs with positive weights (by the greedy choice property).

Time Complexity

  • With a binary heap for the priority queue and adjacency list representation:
    • Extract-min: O(V log V) total (V extractions).
    • Decrease-key: O(E log V) total (up to E updates).
    • Overall: O((V + E) log V), which simplifies to O(E log V) since E ≥ V-1 in connected graphs.
  • For dense graphs (E ≈ V²) using an adjacency matrix without heap: O(V²).
  • The O(E log V) is common for sparse graphs.

Demonstration on the Given Graph

The graph has vertices: A, B, C, D, E, F, G.
Edges with weights:
  • 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
It is connected and undirected.

Kruskal’s Algorithm Demonstration

Kruskal’s algorithm sorts all edges by increasing weight and adds them to the MST if they do not form a cycle (using Union-Find for cycle detection).
  1. Sort edges by weight:
    (B-D: 4), (F-G: 5), (E-F: 6), (D-F: 7), (C-D: 8), (A-B: 10), (A-E: 15), (C-G: 16), (B-C: 20).
  2. Initialize Union-Find: Each vertex is its own component: {A}, {B}, {C}, {D}, {E}, {F}, {G}.
  3. Add edges one by one:
    • Add B-D: 4 (connects {B} and {D} → {B,D}; no cycle). MST: {B-D}, cost = 4.
    • Add F-G: 5 (connects {F} and {G} → {F,G}; no cycle). MST: {B-D, F-G}, cost = 9.
    • Add E-F: 6 (connects {E} and {F,G} → {E,F,G}; no cycle). MST: {B-D, F-G, E-F}, cost = 15.
    • Add D-F: 7 (connects {B,D} and {E,F,G} → {B,D,E,F,G}; no cycle). MST: {B-D, F-G, E-F, D-F}, cost = 22.
    • Add C-D: 8 (connects {C} and {B,D,E,F,G} → {B,C,D,E,F,G}; no cycle). MST: {B-D, F-G, E-F, D-F, C-D}, cost = 30.
    • Add A-B: 10 (connects {A} and {B,C,D,E,F,G} → {A,B,C,D,E,F,G}; no cycle). MST: {B-D, F-G, E-F, D-F, C-D, A-B}, cost = 40.
    • Skip A-E: 15 (A and E already connected; cycle).
    • Skip C-G: 16 (C and G already connected; cycle).
    • Skip B-C: 20 (B and C already connected; cycle).
  4. Final MST: Edges {A-B: 10, B-D: 4, C-D: 8, D-F: 7, E-F: 6, F-G: 5}. Total cost: 40.

How to Arrive at the Solution (Kruskal’s)

  • Sorting ensures we consider smallest edges first.
  • Union-Find efficiently checks cycles (find if roots are same) and merges components (union by rank/path compression for O(α(E)) amortized time, where α is inverse Ackermann).
  • Stop after |V|-1 = 6 edges. The greedy choice avoids cycles while minimizing total weight.

Prim’s Algorithm Demonstration

Using the pseudocode above, starting from vertex A (arbitrary choice). We use a priority queue for minimum keys.
  1. Initialize:
    • inMST: All False.
    • key: All ∞ except key[A] = 0.
    • parent: All -1.
    • PQ: All vertices, min is A.
  2. Iterations:
    • Extract A (key=0). inMST[A]=True. Update neighbors: key[B]=10 (parent[B]=A), key[E]=15 (parent[E]=A).
    • Extract B (min key=10). inMST[B]=True. Update: key[D]=4 (parent[D]=B), key[C]=20 (parent[C]=B). (Ignore A.)
    • Extract D (min key=4). inMST[D]=True. Update: key[C]=8 (better than 20, parent[C]=D), key[F]=7 (parent[F]=D). (Ignore B.)
    • Extract F (min key=7). inMST[F]=True. Update: key[E]=6 (better than 15, parent[E]=F), key[G]=5 (parent[G]=F). (Ignore D.)
    • Extract G (min key=5). inMST[G]=True. Update: key[C]=8 (no change). (Ignore F.)
    • Extract E (min key=6). inMST[E]=True. Update: No better updates. (Ignore A, F.)
    • Extract C (min key=8). inMST[C]=True. No better updates. (Ignore B, D, G.)
  3. Final MST: From parents: B←A (10), D←B (4), F←D (7), G←F (5), E←F (6), C←D (8). Edges {A-B: 10, B-D: 4, D-C: 8, D-F: 7, F-E: 6, F-G: 5}. Total cost: 40.

How to Arrive at the Solution (Prim’s)

  • Start from A and grow the tree by always adding the cheapest edge to the fringe (priority queue handles this).
  • Updates ensure each vertex's key is the minimum possible at each step.
  • Different starting vertex (e.g., G) may yield a different tree but same cost, as the algorithm is correct for connected graphs.

Question:-3(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.

Answer:

Dijkstra’s Shortest Path Algorithm

Dijkstra’s algorithm is a greedy algorithm that finds the shortest paths from a single source vertex to all other vertices in a connected, undirected or directed graph with non-negative edge weights. It maintains a set of vertices whose shortest paths are finalized and grows it by selecting the vertex with the minimum distance estimate.

Pseudocode

Dijkstra(Graph G = (V, E), weights w: E → R ≥ 0, source s ∈ V):
    // Initialize
    dist = array of size |V|, initialized to infinity  // Shortest distance from s
    prev = array of size |V|, initialized to -1  // Previous vertex in path
    dist[s] = 0
    
    // Priority queue (min-heap) for vertices not yet finalized, keyed by dist
    PQ = priority_queue of all vertices, keyed by dist values
    
    while PQ is not empty:
        u = extract_min(PQ)  // Vertex with smallest dist
        
        for each neighbor v of u:
            if dist[v] > dist[u] + w(u, v):
                dist[v] = dist[u] + w(u, v)
                prev[v] = u
                update PQ with new dist for v  // Decrease key operation
    
    // To reconstruct path to a target t: backtrack from t using prev until s
    return dist, prev

Time Complexity

  • With a binary heap for the priority queue and adjacency list representation:
    • Extract-min: O(V log V) total (V extractions).
    • Decrease-key: O(E log V) total (up to E updates).
    • Overall: O((V + E) log V), which simplifies to O(E log V) since E ≥ V-1 in connected graphs.
  • For dense graphs (E ≈ V²) using a simple array for minimum selection (no heap): O(V²).
  • The O(E log V) variant is common for sparse graphs and assumes a heap that supports efficient decrease-key (e.g., binary or Fibonacci heap; Fibonacci reduces to amortized O(E + V log V)).

Demonstration on the Given Graph: Shortest Paths from A

The graph has vertices A, B, C, D, E, F, G and the edges with weights as shown (undirected, so bidirectional). We apply Dijkstra’s from source A, showing step-by-step updates. We use a priority queue (min-heap) for the next vertex selection.

Initialization

  • dist: [A: 0, B: ∞, C: ∞, D: ∞, E: ∞, F: ∞, G: ∞]
  • prev: [all -1]
  • PQ: All vertices (min keyed on dist; initially A at 0, others ∞)

Step-by-Step Computation

We tabulate the process: each iteration extracts the minimum dist vertex u, then relaxes (updates) its neighbors.
Iteration Extracted u (dist[u]) Updates to Neighbors
1 A (0) - B: dist[B] = 0 + 10 = 10 (prev[B] = A)
- E: dist[E] = 0 + 15 = 15 (prev[E] = A)
Current dist: [A:0, B:10, C:∞, D:∞, E:15, F:∞, G:∞]
2 B (10) - C: dist[C] = 10 + 20 = 30 (prev[C] = B)
- D: dist[D] = 10 + 4 = 14 (prev[D] = B)
(A already extracted, ignored)
Current dist: [A:0, B:10, C:30, D:14, E:15, F:∞, G:∞]
3 D (14) - C: dist[C] = 14 + 8 = 22 (< 30, update; prev[C] = D)
- F: dist[F] = 14 + 7 = 21 (prev[F] = D)
(B already extracted, ignored)
Current dist: [A:0, B:10, C:22, D:14, E:15, F:21, G:∞]
4 E (15) - F: 15 + 6 = 21 (== 21, no update)
(A already extracted, ignored)
Current dist: [A:0, B:10, C:22, D:14, E:15, F:21, G:∞]
5 F (21) - G: dist[G] = 21 + 5 = 26 (prev[G] = F)
(D, E already extracted, ignored)
Current dist: [A:0, B:10, C:22, D:14, E:15, F:21, G:26]
6 C (22) - G: 22 + 16 = 38 (> 26, no update)
(B, D already extracted, ignored)
Current dist: [A:0, B:10, C:22, D:14, E:15, F:21, G:26]
7 G (26) (C, F already extracted, ignored)
Current dist: [A:0, B:10, C:22, D:14, E:15, F:21, G:26]
PQ is now empty; all vertices processed.

Final Shortest Distances from A

  • A: 0
  • B: 10
  • C: 22
  • D: 14
  • E: 15
  • F: 21
  • G: 26

Shortest Paths from A (Reconstructed using prev)

  • To A: A (distance 0)
  • To B: A → B (distance 10)
  • To C: A → B → D → C (distance 10 + 4 + 8 = 22)
  • To D: A → B → D (distance 10 + 4 = 14)
  • To E: A → E (distance 15)
  • To F: A → B → D → F (distance 10 + 4 + 7 = 21)
    Note: Alternative path A → E → F (15 + 6 = 21) has the same distance; the algorithm found one via D.
  • To G: A → B → D → F → G (distance 10 + 4 + 7 + 5 = 26)
    Note: Alternative A → E → F → G (15 + 6 + 5 = 26) equivalent.

How to Arrive at the Solution

  • Initialization: Set source distance to 0, others to infinity.
  • Relaxation: For each extracted u, check if a shorter path to v exists via u; update if so.
  • Priority Queue: Ensures the next u is always the one with the current smallest dist (greedy choice).
  • Correctness: Relies on non-negative weights; once a vertex is extracted, its dist is finalized (no shorter path can be found later).
  • The steps guarantee optimality by the invariant: at each extraction, dist[u] is the true shortest path.

Question:-3(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 p i p i p_(i)p_ipi represents the probability that the search will be for the key node k i k i k_(i)k_iki, whereas q i q i q_(i)q_iqi represents that the search is for dummy node d i d i d_(i)d_idi. Make suitable assumptions, if any):

i 0 1 2 3 4 p i 0.10 0.15 0.20 0.10 q i 0.05 0.10 0.10 0.10 0.10 i 0 1 2 3 4 p i 0.10 0.15 0.20 0.10 q i 0.05 0.10 0.10 0.10 0.10 {:[i,0,1,2,3,4],[p_(i),,0.10,0.15,0.20,0.10],[q_(i),0.05,0.10,0.10,0.10,0.10]:}\begin{array}{c|ccccc} i & 0 & 1 & 2 & 3 & 4 \\ \hline p_i & & 0.10 & 0.15 & 0.20 & 0.10 \\ q_i & 0.05 & 0.10 & 0.10 & 0.10 & 0.10 \\ \end{array}i01234pi0.100.150.200.10qi0.050.100.100.100.10

Answer:

Algorithm to Find the Optimal Binary Search Tree

The optimal binary search tree (BST) problem involves constructing a BST that minimizes the expected search cost, given probabilities p i p i p_(i)p_ipi (for successful searches to key k i k i k_(i)k_iki) and q i q i q_(i)q_iqi (for unsuccessful searches ending at dummy node d i d i d_(i)d_idi). The keys k 1 < k 2 < < k n k 1 < k 2 < < k n k_(1) < k_(2) < cdots < k_(n)k_1 < k_2 < \dots < k_nk1<k2<<kn are sorted, and dummies represent failure points: d 0 d 0 d_(0)d_0d0 for keys less than k 1 k 1 k_(1)k_1k1, d n d n d_(n)d_ndn for keys greater than k n k n k_(n)k_nkn, and d i d i d_(i)d_idi (for 1 i < n 1 i < n 1 <= i < n1 \leq i < n1i<n) for keys between k i k i k_(i)k_iki and k i + 1 k i + 1 k_(i+1)k_{i+1}ki+1.
The expected search cost is defined as i = 1 n p i ( depth ( k i ) + 1 ) + i = 0 n q i depth ( d i ) i = 1 n p i ( depth ( k i ) + 1 ) + i = 0 n q i depth ( d i ) sum_(i=1)^(n)p_(i)("depth"(k_(i))+1)+sum_(i=0)^(n)q_(i)"depth"(d_(i))\sum_{i=1}^n p_i (\text{depth}(k_i) + 1) + \sum_{i=0}^n q_i \text{depth}(d_i)i=1npi(depth(ki)+1)+i=0nqidepth(di), where depth is the number of edges from the root (root depth = 0). This accounts for the number of nodes examined during searches.
The algorithm uses dynamic programming:
  • Let e [ i ] [ j ] e [ i ] [ j ] e[i][j]e[i][j]e[i][j] be the minimum expected search cost for the subtree containing keys k i k i k_(i)k_iki to k j k j k_(j)k_jkj (for 1 i j n 1 i j n 1 <= i <= j <= n1 \leq i \leq j \leq n1ijn).
  • Let w [ i ] [ j ] w [ i ] [ j ] w[i][j]w[i][j]w[i][j] be the total probability mass for this subtree: w [ i ] [ j ] = l = i j p l + l = i 1 j q l w [ i ] [ j ] = l = i j p l + l = i 1 j q l w[i][j]=sum_(l=i)^(j)p_(l)+sum_(l=i-1)^(j)q_(l)w[i][j] = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_lw[i][j]=l=ijpl+l=i1jql.
  • Base cases:
    • For empty subtrees ( j = i 1 j = i 1 j=i-1j = i-1j=i1): e [ i ] [ i 1 ] = 0 e [ i ] [ i 1 ] = 0 e[i][i-1]=0e[i][i-1] = 0e[i][i1]=0, w [ i ] [ i 1 ] = 0 w [ i ] [ i 1 ] = 0 w[i][i-1]=0w[i][i-1] = 0w[i][i1]=0 (for i = 1 i = 1 i=1i = 1i=1 to n + 1 n + 1 n+1n+1n+1).
  • Recurrence:
    • w [ i ] [ j ] = w [ i ] [ j 1 ] + p j + q j w [ i ] [ j ] = w [ i ] [ j 1 ] + p j + q j w[i][j]=w[i][j-1]+p_(j)+q_(j)w[i][j] = w[i][j-1] + p_j + q_jw[i][j]=w[i][j1]+pj+qj
    • e [ i ] [ j ] = min r = i j ( e [ i ] [ r 1 ] + e [ r + 1 ] [ j ] + w [ i ] [ j ] ) e [ i ] [ j ] = min r = i j e [ i ] [ r 1 ] + e [ r + 1 ] [ j ] + w [ i ] [ j ] e[i][j]=min_(r=i)^(j)(e[i][r-1]+e[r+1][j]+w[i][j])e[i][j] = \min_{r=i}^j \left( e[i][r-1] + e[r+1][j] + w[i][j] \right)e[i][j]=minr=ij(e[i][r1]+e[r+1][j]+w[i][j])
  • To track the tree structure, record root [ i ] [ j ] root [ i ] [ j ] "root"[i][j]\text{root}[i][j]root[i][j] as the r r rrr that achieves the minimum.
  • Compute in order of increasing subtree size l = j i + 1 l = j i + 1 l=j-i+1l = j - i + 1l=ji+1 (from 1 to n n nnn).
  • The optimal cost is e [ 1 ] [ n ] e [ 1 ] [ n ] e[1][n]e[1][n]e[1][n]; the tree is constructed recursively using the root table.

Time Complexity

  • The DP fills an O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2) table, and for each e [ i ] [ j ] e [ i ] [ j ] e[i][j]e[i][j]e[i][j], it tries O ( n ) O ( n ) O(n)O(n)O(n) choices for r r rrr.
  • Total: O ( n 3 ) O ( n 3 ) O(n^(3))O(n^3)O(n3).

Demonstration for the Given Probabilities

Given n = 4 n = 4 n=4n=4n=4 keys with:
  • p = [ p 1 = 0.10 , p 2 = 0.15 , p 3 = 0.20 , p 4 = 0.10 ] p = [ p 1 = 0.10 , p 2 = 0.15 , p 3 = 0.20 , p 4 = 0.10 ] p=[p_(1)=0.10,p_(2)=0.15,p_(3)=0.20,p_(4)=0.10]p = [p_1=0.10, p_2=0.15, p_3=0.20, p_4=0.10]p=[p1=0.10,p2=0.15,p3=0.20,p4=0.10]
  • q = [ q 0 = 0.05 , q 1 = 0.10 , q 2 = 0.10 , q 3 = 0.10 , q 4 = 0.10 ] q = [ q 0 = 0.05 , q 1 = 0.10 , q 2 = 0.10 , q 3 = 0.10 , q 4 = 0.10 ] q=[q_(0)=0.05,q_(1)=0.10,q_(2)=0.10,q_(3)=0.10,q_(4)=0.10]q = [q_0=0.05, q_1=0.10, q_2=0.10, q_3=0.10, q_4=0.10]q=[q0=0.05,q1=0.10,q2=0.10,q3=0.10,q4=0.10]
We assume the keys are k 1 , k 2 , k 3 , k 4 k 1 , k 2 , k 3 , k 4 k_(1),k_(2),k_(3),k_(4)k_1, k_2, k_3, k_4k1,k2,k3,k4 (specific values not needed, as the algorithm depends only on probabilities and order).

Step-by-Step Computation

We compute w [ i ] [ j ] w [ i ] [ j ] w[i][j]w[i][j]w[i][j] and e [ i ] [ j ] e [ i ] [ j ] e[i][j]e[i][j]e[i][j] for subtrees of increasing length l l lll. The root choices are noted in parentheses.
  1. Length l = 0 l = 0 l=0l=0l=0 (empty subtrees): e [ i ] [ i 1 ] = 0 e [ i ] [ i 1 ] = 0 e[i][i-1]=0e[i][i-1] = 0e[i][i1]=0, w [ i ] [ i 1 ] = 0 w [ i ] [ i 1 ] = 0 w[i][i-1]=0w[i][i-1] = 0w[i][i1]=0 for i = 1 i = 1 i=1i=1i=1 to 5 5 555.
  2. Length l = 1 l = 1 l=1l=1l=1 (single-key subtrees):
    • i = 1 , j = 1 i = 1 , j = 1 i=1,j=1i=1, j=1i=1,j=1: w [ 1 ] [ 1 ] = 0 + 0.10 + 0.10 = 0.25 w [ 1 ] [ 1 ] = 0 + 0.10 + 0.10 = 0.25 w[1][1]=0+0.10+0.10=0.25w[1][1] = 0 + 0.10 + 0.10 = 0.25w[1][1]=0+0.10+0.10=0.25, e [ 1 ] [ 1 ] = 0 + 0 + 0.25 = 0.25 e [ 1 ] [ 1 ] = 0 + 0 + 0.25 = 0.25 e[1][1]=0+0+0.25=0.25e[1][1] = 0 + 0 + 0.25 = 0.25e[1][1]=0+0+0.25=0.25 (root=1)
    • i = 2 , j = 2 i = 2 , j = 2 i=2,j=2i=2, j=2i=2,j=2: w [ 2 ] [ 2 ] = 0 + 0.15 + 0.10 = 0.35 w [ 2 ] [ 2 ] = 0 + 0.15 + 0.10 = 0.35 w[2][2]=0+0.15+0.10=0.35w[2][2] = 0 + 0.15 + 0.10 = 0.35w[2][2]=0+0.15+0.10=0.35, e [ 2 ] [ 2 ] = 0.35 e [ 2 ] [ 2 ] = 0.35 e[2][2]=0.35e[2][2] = 0.35e[2][2]=0.35 (root=2)
    • i = 3 , j = 3 i = 3 , j = 3 i=3,j=3i=3, j=3i=3,j=3: w [ 3 ] [ 3 ] = 0 + 0.20 + 0.10 = 0.40 w [ 3 ] [ 3 ] = 0 + 0.20 + 0.10 = 0.40 w[3][3]=0+0.20+0.10=0.40w[3][3] = 0 + 0.20 + 0.10 = 0.40w[3][3]=0+0.20+0.10=0.40, e [ 3 ] [ 3 ] = 0.40 e [ 3 ] [ 3 ] = 0.40 e[3][3]=0.40e[3][3] = 0.40e[3][3]=0.40 (root=3)
    • i = 4 , j = 4 i = 4 , j = 4 i=4,j=4i=4, j=4i=4,j=4: w [ 4 ] [ 4 ] = 0 + 0.10 + 0.10 = 0.30 w [ 4 ] [ 4 ] = 0 + 0.10 + 0.10 = 0.30 w[4][4]=0+0.10+0.10=0.30w[4][4] = 0 + 0.10 + 0.10 = 0.30w[4][4]=0+0.10+0.10=0.30, e [ 4 ] [ 4 ] = 0.30 e [ 4 ] [ 4 ] = 0.30 e[4][4]=0.30e[4][4] = 0.30e[4][4]=0.30 (root=4)
  3. Length l = 2 l = 2 l=2l=2l=2:
    • i = 1 , j = 2 i = 1 , j = 2 i=1,j=2i=1, j=2i=1,j=2: w [ 1 ] [ 2 ] = 0.25 + 0.15 + 0.10 = 0.50 w [ 1 ] [ 2 ] = 0.25 + 0.15 + 0.10 = 0.50 w[1][2]=0.25+0.15+0.10=0.50w[1][2] = 0.25 + 0.15 + 0.10 = 0.50w[1][2]=0.25+0.15+0.10=0.50
      • r=1: 0 + 0.35 + 0.50 = 0.85 0 + 0.35 + 0.50 = 0.85 0+0.35+0.50=0.850 + 0.35 + 0.50 = 0.850+0.35+0.50=0.85
      • r=2: 0.25 + 0 + 0.50 = 0.75 0.25 + 0 + 0.50 = 0.75 0.25+0+0.50=0.750.25 + 0 + 0.50 = 0.750.25+0+0.50=0.75
      • e [ 1 ] [ 2 ] = 0.75 e [ 1 ] [ 2 ] = 0.75 e[1][2]=0.75e[1][2] = 0.75e[1][2]=0.75 (root=2)
    • i = 2 , j = 3 i = 2 , j = 3 i=2,j=3i=2, j=3i=2,j=3: w [ 2 ] [ 3 ] = 0.35 + 0.20 + 0.10 = 0.65 w [ 2 ] [ 3 ] = 0.35 + 0.20 + 0.10 = 0.65 w[2][3]=0.35+0.20+0.10=0.65w[2][3] = 0.35 + 0.20 + 0.10 = 0.65w[2][3]=0.35+0.20+0.10=0.65
      • r=2: 0 + 0.40 + 0.65 = 1.05 0 + 0.40 + 0.65 = 1.05 0+0.40+0.65=1.050 + 0.40 + 0.65 = 1.050+0.40+0.65=1.05
      • r=3: 0.35 + 0 + 0.65 = 1.00 0.35 + 0 + 0.65 = 1.00 0.35+0+0.65=1.000.35 + 0 + 0.65 = 1.000.35+0+0.65=1.00
      • e [ 2 ] [ 3 ] = 1.00 e [ 2 ] [ 3 ] = 1.00 e[2][3]=1.00e[2][3] = 1.00e[2][3]=1.00 (root=3)
    • i = 3 , j = 4 i = 3 , j = 4 i=3,j=4i=3, j=4i=3,j=4: w [ 3 ] [ 4 ] = 0.40 + 0.10 + 0.10 = 0.60 w [ 3 ] [ 4 ] = 0.40 + 0.10 + 0.10 = 0.60 w[3][4]=0.40+0.10+0.10=0.60w[3][4] = 0.40 + 0.10 + 0.10 = 0.60w[3][4]=0.40+0.10+0.10=0.60
      • r=3: 0 + 0.30 + 0.60 = 0.90 0 + 0.30 + 0.60 = 0.90 0+0.30+0.60=0.900 + 0.30 + 0.60 = 0.900+0.30+0.60=0.90
      • r=4: 0.40 + 0 + 0.60 = 1.00 0.40 + 0 + 0.60 = 1.00 0.40+0+0.60=1.000.40 + 0 + 0.60 = 1.000.40+0+0.60=1.00
      • e [ 3 ] [ 4 ] = 0.90 e [ 3 ] [ 4 ] = 0.90 e[3][4]=0.90e[3][4] = 0.90e[3][4]=0.90 (root=3)
  4. Length l = 3 l = 3 l=3l=3l=3:
    • i = 1 , j = 3 i = 1 , j = 3 i=1,j=3i=1, j=3i=1,j=3: w [ 1 ] [ 3 ] = 0.50 + 0.20 + 0.10 = 0.80 w [ 1 ] [ 3 ] = 0.50 + 0.20 + 0.10 = 0.80 w[1][3]=0.50+0.20+0.10=0.80w[1][3] = 0.50 + 0.20 + 0.10 = 0.80w[1][3]=0.50+0.20+0.10=0.80
      • r=1: 0 + 1.00 + 0.80 = 1.80 0 + 1.00 + 0.80 = 1.80 0+1.00+0.80=1.800 + 1.00 + 0.80 = 1.800+1.00+0.80=1.80
      • r=2: 0.25 + 0.40 + 0.80 = 1.45 0.25 + 0.40 + 0.80 = 1.45 0.25+0.40+0.80=1.450.25 + 0.40 + 0.80 = 1.450.25+0.40+0.80=1.45
      • r=3: 0.75 + 0 + 0.80 = 1.55 0.75 + 0 + 0.80 = 1.55 0.75+0+0.80=1.550.75 + 0 + 0.80 = 1.550.75+0+0.80=1.55
      • e [ 1 ] [ 3 ] = 1.45 e [ 1 ] [ 3 ] = 1.45 e[1][3]=1.45e[1][3] = 1.45e[1][3]=1.45 (root=2)
    • i = 2 , j = 4 i = 2 , j = 4 i=2,j=4i=2, j=4i=2,j=4: w [ 2 ] [ 4 ] = 0.65 + 0.10 + 0.10 = 0.85 w [ 2 ] [ 4 ] = 0.65 + 0.10 + 0.10 = 0.85 w[2][4]=0.65+0.10+0.10=0.85w[2][4] = 0.65 + 0.10 + 0.10 = 0.85w[2][4]=0.65+0.10+0.10=0.85
      • r=2: 0 + 0.90 + 0.85 = 1.75 0 + 0.90 + 0.85 = 1.75 0+0.90+0.85=1.750 + 0.90 + 0.85 = 1.750+0.90+0.85=1.75
      • r=3: 0.35 + 0.30 + 0.85 = 1.50 0.35 + 0.30 + 0.85 = 1.50 0.35+0.30+0.85=1.500.35 + 0.30 + 0.85 = 1.500.35+0.30+0.85=1.50
      • r=4: 1.00 + 0 + 0.85 = 1.85 1.00 + 0 + 0.85 = 1.85 1.00+0+0.85=1.851.00 + 0 + 0.85 = 1.851.00+0+0.85=1.85
      • e [ 2 ] [ 4 ] = 1.50 e [ 2 ] [ 4 ] = 1.50 e[2][4]=1.50e[2][4] = 1.50e[2][4]=1.50 (root=3)
  5. Length l = 4 l = 4 l=4l=4l=4:
    • i = 1 , j = 4 i = 1 , j = 4 i=1,j=4i=1, j=4i=1,j=4: w [ 1 ] [ 4 ] = 0.80 + 0.10 + 0.10 = 1.00 w [ 1 ] [ 4 ] = 0.80 + 0.10 + 0.10 = 1.00 w[1][4]=0.80+0.10+0.10=1.00w[1][4] = 0.80 + 0.10 + 0.10 = 1.00w[1][4]=0.80+0.10+0.10=1.00
      • r=1: 0 + 1.50 + 1.00 = 2.50 0 + 1.50 + 1.00 = 2.50 0+1.50+1.00=2.500 + 1.50 + 1.00 = 2.500+1.50+1.00=2.50
      • r=2: 0.25 + 0.90 + 1.00 = 2.15 0.25 + 0.90 + 1.00 = 2.15 0.25+0.90+1.00=2.150.25 + 0.90 + 1.00 = 2.150.25+0.90+1.00=2.15
      • r=3: 0.75 + 0.30 + 1.00 = 2.05 0.75 + 0.30 + 1.00 = 2.05 0.75+0.30+1.00=2.050.75 + 0.30 + 1.00 = 2.050.75+0.30+1.00=2.05
      • r=4: 1.45 + 0 + 1.00 = 2.45 1.45 + 0 + 1.00 = 2.45 1.45+0+1.00=2.451.45 + 0 + 1.00 = 2.451.45+0+1.00=2.45
      • e [ 1 ] [ 4 ] = 2.05 e [ 1 ] [ 4 ] = 2.05 e[1][4]=2.05e[1][4] = 2.05e[1][4]=2.05 (root=3)

How to Arrive at the Solution

  • DP Table Construction: Start with empty subtrees (cost 0). For each larger subtree, compute the probability mass w [ i ] [ j ] w [ i ] [ j ] w[i][j]w[i][j]w[i][j] incrementally. For each possible root r r rrr, calculate the cost as the sum of left and right subtree costs plus w [ i ] [ j ] w [ i ] [ j ] w[i][j]w[i][j]w[i][j] (which adds 1 to the depth of all elements in the subtree). Choose the r r rrr minimizing this.
  • Optimal Cost: e [ 1 ] [ 4 ] = 2.05 e [ 1 ] [ 4 ] = 2.05 e[1][4]=2.05e[1][4] = 2.05e[1][4]=2.05.
  • Tree Construction: Use the root table recursively:
    • Root: k 3 k 3 k_(3)k_3k3 (from root[1][4]=3)
    • Left subtree (keys 1-2): Root k 2 k 2 k_(2)k_2k2 (root[1][2]=2)
      • Left of k 2 k 2 k_(2)k_2k2: k 1 k 1 k_(1)k_1k1 (root[1][1]=1)
      • Right of k 2 k 2 k_(2)k_2k2: Empty
    • Right subtree (keys 4-4): Root k 4 k 4 k_(4)k_4k4 (root[4][4]=4)
The optimal BST is:
  • Root: k 3 k 3 k_(3)k_3k3
    • Left: k 2 k 2 k_(2)k_2k2
      • Left: k 1 k 1 k_(1)k_1k1
      • Right: None
    • Right: k 4 k 4 k_(4)k_4k4
This structure favors higher-probability keys ( k 3 = 0.20 k 3 = 0.20 k_(3)=0.20k_3 = 0.20k3=0.20, k 2 = 0.15 k 2 = 0.15 k_(2)=0.15k_2 = 0.15k2=0.15) closer to the root.

Question:-3(d)

Given the following sequence of chain multiplication of the matrices. Find the optimal way of multiplying these matrices:

Matrix Dimension A 1 10 × 15 A 2 15 × 5 A 3 5 × 20 A 4 20 × 10 Matrix Dimension A 1 10 × 15 A 2 15 × 5 A 3 5 × 20 A 4 20 × 10 {:["Matrix","Dimension"],[A_(1),10 xx15],[A_(2),15 xx5],[A_(3),5xx20],[A_(4),20 xx10]:}\begin{array}{c|c} \text{Matrix} & \text{Dimension} \\ \hline A_1 & 10 \times 15 \\ A_2 & 15 \times 5 \\ A_3 & 5 \times 20 \\ A_4 & 20 \times 10 \\ \end{array}MatrixDimensionA110×15A215×5A35×20A420×10

Answer:

Algorithm to Find the Optimal Matrix Chain Multiplication

The matrix chain multiplication problem involves finding the most efficient way to multiply a sequence of matrices A 1 , A 2 , , A n A 1 , A 2 , , A n A_(1),A_(2),dots,A_(n)A_1, A_2, \dots, A_nA1,A2,,An, where the cost of multiplication depends on the dimensions. The number of scalar multiplications for matrices A [ p × q ] A [ p × q ] A[p xx q]A[p \times q]A[p×q] and B [ q × r ] B [ q × r ] B[q xx r]B[q \times r]B[q×r] is p × q × r p × q × r p xx q xx rp \times q \times rp×q×r. The goal is to minimize the total number of scalar multiplications by determining the optimal parenthesization.
This is solved using dynamic programming:
  • Let m [ i ] [ j ] m [ i ] [ j ] m[i][j]m[i][j]m[i][j] be the minimum number of scalar multiplications needed to compute the product A i A i + 1 A j A i A i + 1 A j A_(i)*A_(i+1)*cdots*A_(j)A_i \cdot A_{i+1} \cdot \dots \cdot A_jAiAi+1Aj (for 1 i j n 1 i j n 1 <= i <= j <= n1 \leq i \leq j \leq n1ijn).
  • Let s [ i ] [ j ] s [ i ] [ j ] s[i][j]s[i][j]s[i][j] store the index k k kkk where the optimal split occurs (i.e., the last multiplication is A i A k A i A k A_(i)*cdots*A_(k)A_i \cdot \dots \cdot A_kAiAk and A k + 1 A j A k + 1 A j A_(k+1)*cdots*A_(j)A_{k+1} \cdot \dots \cdot A_jAk+1Aj).
  • Dimensions are given as d [ 0 ] , d [ 1 ] , , d [ n ] d [ 0 ] , d [ 1 ] , , d [ n ] d[0],d[1],dots,d[n]d[0], d[1], \dots, d[n]d[0],d[1],,d[n], where d [ i 1 ] × d [ i ] d [ i 1 ] × d [ i ] d[i-1]xx d[i]d[i-1] \times d[i]d[i1]×d[i] is the dimension of A i A i A_(i)A_iAi. The cost of multiplying A i A i + 1 A j A i A i + 1 A j A_(i)*A_(i+1)*cdots*A_(j)A_i \cdot A_{i+1} \cdot \dots \cdot A_jAiAi+1Aj involves finding the best k k kkk to split.
  • Recurrence:
    • m [ i ] [ i ] = 0 m [ i ] [ i ] = 0 m[i][i]=0m[i][i] = 0m[i][i]=0 (cost to multiply one matrix is 0).
    • m [ i ] [ j ] = min i k < j ( m [ i ] [ k ] + m [ k + 1 ] [ j ] + d [ i 1 ] d [ k ] d [ j ] ) m [ i ] [ j ] = min i k < j m [ i ] [ k ] + m [ k + 1 ] [ j ] + d [ i 1 ] d [ k ] d [ j ] m[i][j]=min_(i <= k < j)(m[i][k]+m[k+1][j]+d[i-1]*d[k]*d[j])m[i][j] = \min_{i \leq k < j} \left( m[i][k] + m[k+1][j] + d[i-1] \cdot d[k] \cdot d[j] \right)m[i][j]=minik<j(m[i][k]+m[k+1][j]+d[i1]d[k]d[j]) for j > i j > i j > ij > ij>i.
  • Compute for increasing chain lengths l = j i + 1 l = j i + 1 l=j-i+1l = j - i + 1l=ji+1 from 1 to n n nnn.
  • The optimal cost is m [ 1 ] [ n ] m [ 1 ] [ n ] m[1][n]m[1][n]m[1][n]; the structure is reconstructed using s s sss.

Time Complexity

  • The DP table is O ( n 2 ) O ( n 2 ) O(n^(2))O(n^2)O(n2), and for each m [ i ] [ j ] m [ i ] [ j ] m[i][j]m[i][j]m[i][j], O ( n ) O ( n ) O(n)O(n)O(n) splits are tried.
  • Total: O ( n 3 ) O ( n 3 ) O(n^(3))O(n^3)O(n3).

Demonstration for the Given Matrices

Given matrices:
  • A 1 A 1 A_(1)A_1A1: 10 × 15
  • A 2 A 2 A_(2)A_2A2: 15 × 5
  • A 3 A 3 A_(3)A_3A3: 5 × 20
  • A 4 A 4 A_(4)A_4A4: 20 × 10
Dimensions array d d ddd: [10, 15, 5, 20, 10] (where d [ i 1 ] × d [ i ] d [ i 1 ] × d [ i ] d[i-1]xx d[i]d[i-1] \times d[i]d[i1]×d[i] is A i A i A_(i)A_iAi's dimension).

Step-by-Step Computation

We compute m [ i ] [ j ] m [ i ] [ j ] m[i][j]m[i][j]m[i][j] and s [ i ] [ j ] s [ i ] [ j ] s[i][j]s[i][j]s[i][j] for subchains of increasing length l l lll.
  1. Length l = 1 l = 1 l=1l=1l=1 (single matrices):
    • m [ i ] [ i ] = 0 m [ i ] [ i ] = 0 m[i][i]=0m[i][i] = 0m[i][i]=0 for i = 1 i = 1 i=1i = 1i=1 to 4.
    • s [ i ] [ i ] s [ i ] [ i ] s[i][i]s[i][i]s[i][i] is undefined (no split).
  2. Length l = 2 l = 2 l=2l=2l=2 (two matrices):
    • i = 1 , j = 2 i = 1 , j = 2 i=1,j=2i=1, j=2i=1,j=2: d [ 0 ] d [ 1 ] d [ 2 ] = 10 15 5 = 750 d [ 0 ] d [ 1 ] d [ 2 ] = 10 15 5 = 750 d[0]*d[1]*d[2]=10*15*5=750d[0] \cdot d[1] \cdot d[2] = 10 \cdot 15 \cdot 5 = 750d[0]d[1]d[2]=10155=750
      • m [ 1 ] [ 2 ] = m [ 1 ] [ 1 ] + m [ 2 ] [ 2 ] + 750 = 0 + 0 + 750 = 750 m [ 1 ] [ 2 ] = m [ 1 ] [ 1 ] + m [ 2 ] [ 2 ] + 750 = 0 + 0 + 750 = 750 m[1][2]=m[1][1]+m[2][2]+750=0+0+750=750m[1][2] = m[1][1] + m[2][2] + 750 = 0 + 0 + 750 = 750m[1][2]=m[1][1]+m[2][2]+750=0+0+750=750
      • s [ 1 ] [ 2 ] = 1 s [ 1 ] [ 2 ] = 1 s[1][2]=1s[1][2] = 1s[1][2]=1 (only one split at k = 1 k = 1 k=1k=1k=1)
    • i = 2 , j = 3 i = 2 , j = 3 i=2,j=3i=2, j=3i=2,j=3: d [ 1 ] d [ 2 ] d [ 3 ] = 15 5 20 = 1500 d [ 1 ] d [ 2 ] d [ 3 ] = 15 5 20 = 1500 d[1]*d[2]*d[3]=15*5*20=1500d[1] \cdot d[2] \cdot d[3] = 15 \cdot 5 \cdot 20 = 1500d[1]d[2]d[3]=15520=1500
      • m [ 2 ] [ 3 ] = 1500 m [ 2 ] [ 3 ] = 1500 m[2][3]=1500m[2][3] = 1500m[2][3]=1500
      • s [ 2 ] [ 3 ] = 2 s [ 2 ] [ 3 ] = 2 s[2][3]=2s[2][3] = 2s[2][3]=2
    • i = 3 , j = 4 i = 3 , j = 4 i=3,j=4i=3, j=4i=3,j=4: d [ 2 ] d [ 3 ] d [ 4 ] = 5 20 10 = 1000 d [ 2 ] d [ 3 ] d [ 4 ] = 5 20 10 = 1000 d[2]*d[3]*d[4]=5*20*10=1000d[2] \cdot d[3] \cdot d[4] = 5 \cdot 20 \cdot 10 = 1000d[2]d[3]d[4]=52010=1000
      • m [ 3 ] [ 4 ] = 1000 m [ 3 ] [ 4 ] = 1000 m[3][4]=1000m[3][4] = 1000m[3][4]=1000
      • s [ 3 ] [ 4 ] = 3 s [ 3 ] [ 4 ] = 3 s[3][4]=3s[3][4] = 3s[3][4]=3
  3. Length l = 3 l = 3 l=3l=3l=3:
    • i = 1 , j = 3 i = 1 , j = 3 i=1,j=3i=1, j=3i=1,j=3: d [ 0 ] d [ 2 ] d [ 3 ] = 10 5 20 = 1000 d [ 0 ] d [ 2 ] d [ 3 ] = 10 5 20 = 1000 d[0]*d[2]*d[3]=10*5*20=1000d[0] \cdot d[2] \cdot d[3] = 10 \cdot 5 \cdot 20 = 1000d[0]d[2]d[3]=10520=1000
      • k = 1 k = 1 k=1k=1k=1: m [ 1 ] [ 1 ] + m [ 2 ] [ 3 ] + 1000 = 0 + 1500 + 1000 = 2500 m [ 1 ] [ 1 ] + m [ 2 ] [ 3 ] + 1000 = 0 + 1500 + 1000 = 2500 m[1][1]+m[2][3]+1000=0+1500+1000=2500m[1][1] + m[2][3] + 1000 = 0 + 1500 + 1000 = 2500m[1][1]+m[2][3]+1000=0+1500+1000=2500
      • k = 2 k = 2 k=2k=2k=2: m [ 1 ] [ 2 ] + m [ 3 ] [ 3 ] + 1000 = 750 + 0 + 1000 = 1750 m [ 1 ] [ 2 ] + m [ 3 ] [ 3 ] + 1000 = 750 + 0 + 1000 = 1750 m[1][2]+m[3][3]+1000=750+0+1000=1750m[1][2] + m[3][3] + 1000 = 750 + 0 + 1000 = 1750m[1][2]+m[3][3]+1000=750+0+1000=1750
      • m [ 1 ] [ 3 ] = 1750 m [ 1 ] [ 3 ] = 1750 m[1][3]=1750m[1][3] = 1750m[1][3]=1750, s [ 1 ] [ 3 ] = 2 s [ 1 ] [ 3 ] = 2 s[1][3]=2s[1][3] = 2s[1][3]=2
    • i = 2 , j = 4 i = 2 , j = 4 i=2,j=4i=2, j=4i=2,j=4: d [ 1 ] d [ 3 ] d [ 4 ] = 15 20 10 = 3000 d [ 1 ] d [ 3 ] d [ 4 ] = 15 20 10 = 3000 d[1]*d[3]*d[4]=15*20*10=3000d[1] \cdot d[3] \cdot d[4] = 15 \cdot 20 \cdot 10 = 3000d[1]d[3]d[4]=152010=3000
      • k = 2 k = 2 k=2k=2k=2: m [ 2 ] [ 2 ] + m [ 3 ] [ 4 ] + 3000 = 0 + 1000 + 3000 = 4000 m [ 2 ] [ 2 ] + m [ 3 ] [ 4 ] + 3000 = 0 + 1000 + 3000 = 4000 m[2][2]+m[3][4]+3000=0+1000+3000=4000m[2][2] + m[3][4] + 3000 = 0 + 1000 + 3000 = 4000m[2][2]+m[3][4]+3000=0+1000+3000=4000
      • k = 3 k = 3 k=3k=3k=3: m [ 2 ] [ 3 ] + m [ 4 ] [ 4 ] + 3000 = 1500 + 0 + 3000 = 4500 m [ 2 ] [ 3 ] + m [ 4 ] [ 4 ] + 3000 = 1500 + 0 + 3000 = 4500 m[2][3]+m[4][4]+3000=1500+0+3000=4500m[2][3] + m[4][4] + 3000 = 1500 + 0 + 3000 = 4500m[2][3]+m[4][4]+3000=1500+0+3000=4500
      • m [ 2 ] [ 4 ] = 4000 m [ 2 ] [ 4 ] = 4000 m[2][4]=4000m[2][4] = 4000m[2][4]=4000, s [ 2 ] [ 4 ] = 2 s [ 2 ] [ 4 ] = 2 s[2][4]=2s[2][4] = 2s[2][4]=2
  4. Length l = 4 l = 4 l=4l=4l=4:
    • i = 1 , j = 4 i = 1 , j = 4 i=1,j=4i=1, j=4i=1,j=4: d [ 0 ] d [ 3 ] d [ 4 ] = 10 20 10 = 2000 d [ 0 ] d [ 3 ] d [ 4 ] = 10 20 10 = 2000 d[0]*d[3]*d[4]=10*20*10=2000d[0] \cdot d[3] \cdot d[4] = 10 \cdot 20 \cdot 10 = 2000d[0]d[3]d[4]=102010=2000
      • k = 1 k = 1 k=1k=1k=1: m [ 1 ] [ 1 ] + m [ 2 ] [ 4 ] + 2000 = 0 + 4000 + 2000 = 6000 m [ 1 ] [ 1 ] + m [ 2 ] [ 4 ] + 2000 = 0 + 4000 + 2000 = 6000 m[1][1]+m[2][4]+2000=0+4000+2000=6000m[1][1] + m[2][4] + 2000 = 0 + 4000 + 2000 = 6000m[1][1]+m[2][4]+2000=0+4000+2000=6000
      • k = 2 k = 2 k=2k=2k=2: m [ 1 ] [ 2 ] + m [ 3 ] [ 4 ] + 2000 = 750 + 1000 + 2000 = 3750 m [ 1 ] [ 2 ] + m [ 3 ] [ 4 ] + 2000 = 750 + 1000 + 2000 = 3750 m[1][2]+m[3][4]+2000=750+1000+2000=3750m[1][2] + m[3][4] + 2000 = 750 + 1000 + 2000 = 3750m[1][2]+m[3][4]+2000=750+1000+2000=3750
      • k = 3 k = 3 k=3k=3k=3: m [ 1 ] [ 3 ] + m [ 4 ] [ 4 ] + 2000 = 1750 + 0 + 2000 = 3750 m [ 1 ] [ 3 ] + m [ 4 ] [ 4 ] + 2000 = 1750 + 0 + 2000 = 3750 m[1][3]+m[4][4]+2000=1750+0+2000=3750m[1][3] + m[4][4] + 2000 = 1750 + 0 + 2000 = 3750m[1][3]+m[4][4]+2000=1750+0+2000=3750
      • m [ 1 ] [ 4 ] = 3750 m [ 1 ] [ 4 ] = 3750 m[1][4]=3750m[1][4] = 3750m[1][4]=3750, s [ 1 ] [ 4 ] = 2 s [ 1 ] [ 4 ] = 2 s[1][4]=2s[1][4] = 2s[1][4]=2 (or 3, tie; choose 2 for consistency)

Optimal Parenthesization

  • m [ 1 ] [ 4 ] = 3750 m [ 1 ] [ 4 ] = 3750 m[1][4]=3750m[1][4] = 3750m[1][4]=3750 is the minimum cost.
  • Reconstruct using s s sss:
    • s [ 1 ] [ 4 ] = 2 s [ 1 ] [ 4 ] = 2 s[1][4]=2s[1][4] = 2s[1][4]=2: Split after A 2 A 2 A_(2)A_2A2.
    • Left: A 1 A 2 A 1 A 2 A_(1)*A_(2)A_1 \cdot A_2A1A2 (cost 750, s [ 1 ] [ 2 ] = 1 s [ 1 ] [ 2 ] = 1 s[1][2]=1s[1][2] = 1s[1][2]=1).
    • Right: A 3 A 4 A 3 A 4 A_(3)*A_(4)A_3 \cdot A_4A3A4 (cost 1000, s [ 3 ] [ 4 ] = 3 s [ 3 ] [ 4 ] = 3 s[3][4]=3s[3][4] = 3s[3][4]=3).
    • Final multiplication: ( A 1 A 2 ) ( A 3 A 4 ) ( A 1 A 2 ) ( A 3 A 4 ) (A_(1)*A_(2))*(A_(3)*A_(4))(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)(A1A2)(A3A4), cost = 750 + 1000 + 2000 = 3750.

How to Arrive at the Solution

  • DP Approach: Build costs bottom-up, considering all possible splits. The cost includes previous subproblems plus the multiplication cost.
  • Optimality: The recurrence ensures the minimum by trying all k k kkk, leveraging the principle that optimal subproblems combine optimally.
  • The chosen split minimizes the total scalar multiplications, validated by the computed m [ 1 ] [ 4 ] m [ 1 ] [ 4 ] m[1][4]m[1][4]m[1][4].

Question:-3(e)

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

Answer:

Rabin-Karp Algorithm for String Matching

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to efficiently find occurrences of a pattern (substring) within a larger text. It avoids comparing every possible substring character-by-character by instead computing hash values for the pattern and sliding windows of the text. If the hash of a text window matches the pattern's hash, a full character comparison is performed to confirm a match (to handle potential hash collisions).

Key Concepts

  • Hashing: Treat strings as numbers in a large base (e.g., base d = 256 d = 256 d=256d = 256d=256 for ASCII characters). Compute a numerical hash for the pattern and text substrings.
  • Rolling Hash: Efficiently update the hash for the next window in constant time, rather than recomputing from scratch. This is done by subtracting the contribution of the outgoing character and adding the incoming one.
  • Modulo Operation: Use a large prime modulus q q qqq to keep hash values manageable and prevent overflow.
  • Handling Collisions: Hashes may collide (different strings with same hash), so always verify matches with direct comparison.

Steps of the Algorithm

  1. Let n n nnn be the length of the text T T TTT, m m mmm be the length of the pattern P P PPP (assume m n m n m <= nm \leq nmn).
  2. Choose a base d d ddd (e.g., 256) and a large prime q q qqq (e.g., 101 or larger).
  3. Precompute d m 1 mod q d m 1 mod q d^(m-1)modqd^{m-1} \mod qdm1modq (highest power for the leftmost character).
  4. Compute the hash of the pattern:
    p _ h a s h = ( P [ 0 ] d m 1 + P [ 1 ] d m 2 + + P [ m 1 ] d 0 ) mod q p _ h a s h = ( P [ 0 ] d m 1 + P [ 1 ] d m 2 + + P [ m 1 ] d 0 ) mod q p_hash=(P[0]*d^(m-1)+P[1]*d^(m-2)+cdots+P[m-1]*d^(0))modqp\_hash = (P[0] \cdot d^{m-1} + P[1] \cdot d^{m-2} + \dots + P[m-1] \cdot d^0) \mod qp_hash=(P[0]dm1+P[1]dm2++P[m1]d0)modq.
  5. Compute the initial hash of the first m m mmm characters of the text:
    t _ h a s h = ( T [ 0 ] d m 1 + T [ 1 ] d m 2 + + T [ m 1 ] d 0 ) mod q t _ h a s h = ( T [ 0 ] d m 1 + T [ 1 ] d m 2 + + T [ m 1 ] d 0 ) mod q t_hash=(T[0]*d^(m-1)+T[1]*d^(m-2)+cdots+T[m-1]*d^(0))modqt\_hash = (T[0] \cdot d^{m-1} + T[1] \cdot d^{m-2} + \dots + T[m-1] \cdot d^0) \mod qt_hash=(T[0]dm1+T[1]dm2++T[m1]d0)modq.
  6. If p _ h a s h == t _ h a s h p _ h a s h == t _ h a s h p_hash==t_hashp\_hash == t\_hashp_hash==t_hash, compare T [ 0. . m 1 ] T [ 0. . m 1 ] T[0..m-1]T[0..m-1]T[0..m1] and P P PPP character-by-character. If they match, record the starting index 0.
  7. For each subsequent window i = 1 i = 1 i=1i = 1i=1 to n m n m n-mn-mnm:
    • Update t _ h a s h t _ h a s h t_hasht\_hasht_hash: t _ h a s h = ( d ( t _ h a s h T [ i 1 ] d m 1 ) + T [ i + m 1 ] ) mod q t _ h a s h = ( d ( t _ h a s h T [ i 1 ] d m 1 ) + T [ i + m 1 ] ) mod q t_hash=(d*(t_hash-T[i-1]*d^(m-1))+T[i+m-1])modqt\_hash = (d \cdot (t\_hash - T[i-1] \cdot d^{m-1}) + T[i+m-1]) \mod qt_hash=(d(t_hashT[i1]dm1)+T[i+m1])modq.
      (Handle negative values by adding q q qqq if needed.)
    • If p _ h a s h == t _ h a s h p _ h a s h == t _ h a s h p_hash==t_hashp\_hash == t\_hashp_hash==t_hash, compare T [ i . . i + m 1 ] T [ i . . i + m 1 ] T[i..i+m-1]T[i..i+m-1]T[i..i+m1] and P P PPP character-by-character. If they match, record index i i iii.

Example

Consider the text T = " A B C D A B C A B " T = " A B C D A B C A B " T="ABCDABCAB"T = "ABCDABCAB"T="ABCDABCAB" and pattern P = " A B C " P = " A B C " P="ABC"P = "ABC"P="ABC" (lengths n = 9 n = 9 n=9n=9n=9, m = 3 m = 3 m=3m=3m=3). For simplicity, treat characters as their ASCII values (A=65, B=66, C=67, D=68), but we'll use a small base d = 10 d = 10 d=10d=10d=10 and prime q = 13 q = 13 q=13q=13q=13 for easy calculation (in practice, use larger d d ddd and q q qqq).
  1. Precompute d m 1 = 10 2 = 100 mod 13 = 100 7 13 = 100 91 = 9 d m 1 = 10 2 = 100 mod 13 = 100 7 13 = 100 91 = 9 d^(m-1)=10^(2)=100mod13=100-7**13=100-91=9d^{m-1} = 10^2 = 100 \mod 13 = 100 - 7*13 = 100-91=9dm1=102=100mod13=100713=10091=9.
  2. Pattern hash ( P = " A B C " P = " A B C " P="ABC"P = "ABC"P="ABC"):
    p _ h a s h = ( 65 10 2 + 66 10 1 + 67 10 0 ) mod 13 = ( 6500 + 660 + 67 ) = 7227 mod 13 p _ h a s h = ( 65 10 2 + 66 10 1 + 67 10 0 ) mod 13 = ( 6500 + 660 + 67 ) = 7227 mod 13 p_hash=(65*10^(2)+66*10^(1)+67*10^(0))mod13=(6500+660+67)=7227mod13p\_hash = (65 \cdot 10^2 + 66 \cdot 10^1 + 67 \cdot 10^0) \mod 13 = (6500 + 660 + 67) = 7227 \mod 13p_hash=(65102+66101+67100)mod13=(6500+660+67)=7227mod13.
    7227 ÷ 13 = 555*13=7215, remainder 12. So p _ h a s h = 12 p _ h a s h = 12 p_hash=12p\_hash = 12p_hash=12.
  3. Initial text window "ABC":
    t _ h a s h = ( 65 100 + 66 10 + 67 ) = 7227 mod 13 = 12 t _ h a s h = ( 65 100 + 66 10 + 67 ) = 7227 mod 13 = 12 t_hash=(65*100+66*10+67)=7227mod13=12t\_hash = (65 \cdot 100 + 66 \cdot 10 + 67) = 7227 \mod 13 = 12t_hash=(65100+6610+67)=7227mod13=12.
    Hashes match (12==12). Compare strings: "ABC" == "ABC" → Match at index 0.
  4. Next window (i=1): "BCD"
    Update: t _ h a s h = ( 10 ( 12 65 9 ) + 68 ) mod 13 t _ h a s h = ( 10 ( 12 65 9 ) + 68 ) mod 13 t_hash=(10*(12-65*9)+68)mod13t\_hash = (10 \cdot (12 - 65 \cdot 9) + 68) \mod 13t_hash=(10(12659)+68)mod13.
    First, 659=585 mod 13: 585-4513=585-585=0, so 12 - 0 =12.
    1012=120 +68=188 mod13: 188-1413=188-182=6.
    "BCD" hash=6 ≠12 → No match.
  5. Next (i=2): "CDA"
    Update from previous: Subtract C's contrib (679 mod13:679=603,603-46*13=603-598=5), so 6-5=1, then 10=10 +65=75 mod13=75-513=75-65=10 ≠12.
  6. Next (i=3): "DAB" → Continues, no match.
  7. Next (i=4): "ABC" → Hash will compute to 12, match at index 4 (after update steps).
  8. And so on. Matches found at 0 and 4.
In a real implementation, characters are treated as integers, and larger primes reduce collisions.

Time Complexity

  • Preprocessing: O(m) to compute pattern hash and initial text hash.
  • Sliding Window: O(n - m + 1) updates, each O(1) time.
  • Verifications: In the average case, few collisions, so O(m) per true match, leading to overall average O(n + m).
  • Worst Case: If every hash matches (many collisions), verify all n-m+1 windows, each O(m), so O((n - m + 1) * m) ≈ O(nm). With a good hash (large prime), collisions are rare, making average close to O(n + m).

Question:-4(a)

Explain the term Decision problem with the help of an example. Define the following problems and identify if they are decision problem or optimisation problem? Give reasons in support of your answer.

(i) Travelling Salesman Problem
(ii) Graph Colouring Problem
(iii) 0-1 Knapsack Problem

Answer:

❓ Decision Problem

A decision problem is a question with a yes/no answer.
Example:
"Is there a path from node A to node B in a graph with length ≤ k?"

🧳 (i) Travelling Salesman Problem (TSP)

  • Standard form: Find the shortest route visiting each city exactly once and returning to the start.
  • This is an optimization problem (minimize route length).
  • Decision version: "Is there a route of length ≤ k?"
    • This is a decision problem.
Reason: The core question seeks a minimum value, but it can be framed as a decision problem by asking if a solution exists within a bound.

🎨 (ii) Graph Colouring Problem

  • Standard form: Assign colours to vertices so no adjacent vertices share a colour, using the fewest colours.
  • This is an optimization problem (minimize colours).
  • Decision version: "Can the graph be coloured with k colours?"
    • This is a decision problem.
Reason: The goal is to minimize colours, but it is often treated as a decision problem for complexity analysis (e.g., k-colouring).

🎒 (iii) 0-1 Knapsack Problem

  • Standard form: Select items to maximize profit without exceeding weight capacity.
  • This is an optimization problem (maximize profit).
  • Decision version: "Is there a subset of items with profit ≥ P and weight ≤ W?"
    • This is a decision problem.
Reason: The natural form seeks maximum profit, but it can be converted to a decision problem by introducing a profit threshold.

✅ Summary:

  • All three are optimization problems in their standard form.
  • Each has a decision version used in computational complexity theory (e.g., NP-completeness).
  • Decision problems are easier to analyze in terms of complexity classes.

Question:-4(b)

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

Answer:

🧠 P and NP Classes of Problems

🟢 Class P (Polynomial Time)

Definition: Problems that can be solved by a deterministic Turing machine in polynomial time ( O ( n k ) O ( n k ) O(n^(k))O(n^k)O(nk) for some constant k k kkk).
Examples:
  1. Sorting a list
    • Algorithms like Merge Sort run in O ( n log n ) O ( n log n ) O(n log n)O(n \log n)O(nlogn), which is polynomial.
  2. Finding the shortest path in a graph (Dijkstra's algorithm)
    • Runs in O ( V 2 ) O ( V 2 ) O(V^(2))O(V^2)O(V2) or O ( E + V log V ) O ( E + V log V ) O(E+V log V)O(E + V \log V)O(E+VlogV) with a priority queue.

🔴 Class NP (Nondeterministic Polynomial Time)

Definition: Problems whose solutions can be verified in polynomial time by a deterministic Turing machine. Note: NP does NOT mean "not polynomial"; it means "nondeterministic polynomial".
Examples:
  1. Boolean Satisfiability (SAT)
    • Given a Boolean formula, is there an assignment of variables that makes it true?
    • Verification: Check if a given assignment satisfies the formula in linear time.
  2. Traveling Salesman Problem (Decision Version)
    • Is there a route of length ≤ k?
    • Verification: Check if a given route visits all cities and has length ≤ k in polynomial time.

🔑 Key Points:

  • P ⊆ NP (If you can solve it, you can verify it).
  • Open Question: Is P = NP? (One of the Millennium Prize Problems).
  • NP includes problems that are "easy" to verify but may be "hard" to solve.

📊 Comparison:

Class Solvable in Poly-Time Verifiable in Poly-Time Examples
P Yes Yes Sorting, Shortest Path
NP Unknown Yes SAT, TSP
Understanding P and NP is crucial for complexity theory and cryptography! 🎯

Question:-4(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.

Answer:

🧩 NP-Hard and NP-Complete Problems

🔴 NP-Hard

A problem is NP-hard if it is at least as hard as the hardest problems in NP. This means any problem in NP can be reduced to it in polynomial time. NP-hard problems may not be in NP themselves.
Example:
  • Halting Problem (undecidable, but NP-hard)
  • Traveling Salesman Problem (optimization version)

🟠 NP-Complete

A problem is NP-complete if it is:
  1. In NP (verifiable in polynomial time).
  2. NP-hard (all NP problems reduce to it).
Examples:
  • Boolean Satisfiability (SAT)
  • Graph Coloring
  • Subset Sum

🔍 Key Differences:

NP-Hard NP-Complete
May not be in NP Must be in NP
Includes optimization problems Typically decision problems
e.g., Halting Problem e.g., 3-SAT

⏱️ Polynomial-Time Reduction

A reduction transforms problem A to problem B in polynomial time such that solving B solves A. Used to prove NP-hardness.
Example: Reducing 3-SAT to Graph Coloring:
  • Show that if we can solve Graph Coloring quickly, we can solve 3-SAT quickly.
  • Construct a graph from a 3-CNF formula where coloring the graph with k colors implies a satisfying assignment.
This proves Graph Coloring is NP-hard if 3-SAT is NP-hard.


Question:-4(d)

Define the following Problems:

(i) SAT Problem
(ii) Clique Problem
(iii) Hamiltonian Cycle Problem
(iv) Subset Sum Problem

Answer:

📌 (i) SAT Problem (Boolean Satisfiability Problem)

Definition: Given a Boolean formula (e.g., in conjunctive normal form), is there an assignment of truth values to variables that makes the entire formula true?
Example:
Formula: ( x 1 ¬ x 2 ) ( ¬ x 1 x 3 ) ( x 1 ¬ x 2 ) ( ¬ x 1 x 3 ) (x_(1)vv notx_(2))^^(notx_(1)vvx_(3))(x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3)(x1¬x2)(¬x1x3)
Is there values for x 1 , x 2 , x 3 x 1 , x 2 , x 3 x_(1),x_(2),x_(3)x_1, x_2, x_3x1,x2,x3 that make this true? (Yes, e.g., x 1 = true , x 2 = false , x 3 = true x 1 = true , x 2 = false , x 3 = true x_(1)="true",x_(2)="false",x_(3)="true"x_1 = \text{true}, x_2 = \text{false}, x_3 = \text{true}x1=true,x2=false,x3=true)

👥 (ii) Clique Problem

Definition: A clique is a complete subgraph (every pair of vertices connected). The decision problem: Does a graph contain a clique of size k k kkk?
Example:
In a social network, is there a group of k k kkk people where all know each other?

🔁 (iii) Hamiltonian Cycle Problem

Definition: Does a graph contain a cycle that visits every vertex exactly once and returns to the start?
Example:
Can a salesperson visit each city exactly once and return home?

💰 (iv) Subset Sum Problem

Definition: Given a set of integers and a target sum T T TTT, is there a subset that adds to T T TTT?
Example:
Set: { 3 , 7 , 2 , 8 } { 3 , 7 , 2 , 8 } {3,7,2,8}\{3, 7, 2, 8\}{3,7,2,8}, Target: 10 → Yes (3+7=10)


Search Free Solved Assignment

Just Type atleast 3 letters of your Paper Code

Scroll to Top
Scroll to Top