BCS 042 Solved Guess Paper for Introduction to Algorithm Design | IGNOU Bachelor of Computer Applications (BCA)

Sample 1: Recursion Tree Method and Master Theorem

Question: (a) Solve the recurrence T(n) = T(n/3) + T(2n/3) + n using the recursion tree method. (5)
(b) State the Master Theorem and use it to give tight asymptotic bounds for T(n) = 4T(n/2) + n² and T(n) = 2T(n/2) + n√n. (5)

(a) Recursion tree method. A recursion tree shows what happens when a recurrence is expanded again and again. We put the non-recursive cost at each node, add the cost of every level (row sum) and then add all the levels (column sum).

T(n) = T(n/3) + T(2n/3) + n

Level 0 cost :  n
Level 1 cost :  n/3 + 2n/3                    = n
Level 2 cost :  n/9 + 2n/9 + 2n/9 + 4n/9      = n
Every full level costs n.

Shortest path : n, n/3, n/9, ... 1     height = log_3 n
Longest path  : n, 2n/3, 4n/9, ... 1   height = log_(3/2) n

So   n log_3 n  <=  T(n)  <=  n log_(3/2) n
Both bounds differ only by a constant log base, hence
T(n) = Θ(n log n)

(b) Master Theorem. For T(n) = aT(n/b) + f(n), with a ≥ 1 and b > 1, compare f(n) with n^(log_b a).

• Case 1: if f(n) = O(n^(log_b a − ε)) for some ε > 0, then T(n) = Θ(n^(log_b a)).
• Case 2: if f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) log n).
• Case 3: if f(n) = Ω(n^(log_b a + ε)) for some ε > 0 and a·f(n/b) ≤ c·f(n) for some c < 1, then T(n) = Θ(f(n)).

(i)  T(n) = 4T(n/2) + n²
     a = 4, b = 2, n^(log_2 4) = n²
     f(n) = n² = Θ(n²)            Case 2
     T(n) = Θ(n² log n)

(ii) T(n) = 2T(n/2) + n√n
     a = 2, b = 2, n^(log_2 2) = n
     f(n) = n^1.5 = Ω(n^(1 + 0.5))   so ε = 0.5
     Regularity: 2(n/2)^1.5 = n^1.5 / √2 <= 0.71 n^1.5   (c = 0.71 < 1)
     Case 3
     T(n) = Θ(n√n)

Conclusion: The recursion tree works even when the two branches are unequal, while the Master Theorem is quicker but only fits the form aT(n/b) + f(n).

Sample 2: Euclid's GCD Algorithm and Horner's Rule

Question: (a) State Euclid's algorithm for GCD and find GCD(595, 252). Also discuss its complexity. (5)
(b) Write the basic algorithm to evaluate a polynomial by Horner's rule and find its complexity. (5)

(a) Euclid's algorithm. The GCD of two non-negative integers m and n, not both zero, is the largest integer that divides both without a remainder. Euclid's method uses the fact that GCD(m, n) = GCD(n, m mod n).

function gcd(m, n)
{   while (n != 0)
    {   r = m mod n
        m = n
        n = r
    }
    return m
}

Hence GCD(595, 252) = 7.

Complexity. Each loop pass does one division, so the cost depends on the number of passes. In the best case n divides m and a single pass is enough, which is O(1). Every two passes at least halve the larger number, so the number of passes is O(log n), where n is the smaller input. The worst case happens when m and n are consecutive Fibonacci numbers.

(b) Horner's rule. Horner's rule rewrites p(x) = a_n xⁿ + ... + a_1 x + a_0 in nested form, for example ax² + bx + c = (ax + b)x + c, so no power is computed separately.

Evaluate_Horner(a[0..n], n, x)
{   p = a[n]
    for (i = n - 1; i >= 0; i--)
        p = p * x + a[i]
    return p
}

Complexity: the loop runs n times and each pass does one multiplication and one addition, so Horner's rule takes O(n) time. Evaluating every term with separate powers needs about n²/2 multiplications, which is why Horner's form is preferred.

Sample 3: Bubble Sort and Selection Sort

Question: (a) Write an algorithm for bubble sort and give its worst case, average case and best case analysis. (5)
(b) Write the selection sort algorithm and analyse its complexity. Sort the list 23, 18, 15, 37, 8, 11 using selection sort. (5)

(a) Bubble sort. The list is treated as an unsorted part and a sorted part. In each pass adjacent elements are compared and swapped, so the largest remaining element bubbles to the end.

function bubblesort(a, n)
{   flag = true
    for (i = 0; i < n-1 and flag == true; i++)
    {   flag = false
        for (j = 0; j < n-i-1; j++)
            if (a[j] > a[j+1])
            {   swap(a[j], a[j+1])
                flag = true
            }
    }
}

• Best case: the list is already sorted, the first pass makes n − 1 comparisons and no swaps, the flag stays false and the loop ends, so O(n).
• Worst case: the list is in descending order, needing n(n − 1)/2 comparisons and the same number of swaps, so O(n²).
• Average case: about half the pairs are out of order, which still gives O(n²).

(b) Selection sort. In each pass the smallest element of the unsorted part is found and swapped with the first element of that part.

function selectionsort(a, n)
{   for (i = 0; i < n-1; i++)
    {   min = i
        for (j = i+1; j < n; j++)
            if (a[j] < a[min])  min = j
        swap(a[i], a[min])
    }
}

Complexity: comparisons are (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2 whatever the input, so best, worst and average case are all Θ(n²). Swaps are at most n − 1, the fewest among the simple sorts.

Sample 4: Greedy Technique and Fractional Knapsack

Question: (a) Briefly explain the greedy technique for designing algorithms and list its characteristics. (4)
(b) Define the fractional knapsack problem. Find the optimal solution for n = 7 and m = 15, where (P1 ... P7) = (10, 5, 15, 7, 6, 18, 3) and (W1 ... W7) = (2, 3, 5, 7, 1, 4, 1). (6)

(a) Greedy technique. A greedy algorithm builds a solution one step at a time and always takes the choice that looks best at that moment, hoping the local best leads to the overall best.

• It is used for optimisation problems where we maximise or minimise an objective.
• Each choice must be feasible, locally optimal and never reversed later.
• It is simple to design and usually fast to run.
• It does not always give the optimal answer, but it does for fractional knapsack, Prim's, Kruskal's and Dijkstra's algorithms.

(b) Fractional knapsack. Given n objects with profit p_i and weight w_i and a knapsack of capacity m, choose fractions 0 ≤ x_i ≤ 1 to maximise Σ p_i x_i subject to Σ w_i x_i ≤ m. The greedy rule that gives the optimum is to pick objects in decreasing order of p_i / w_i.

Solution vector (x1 ... x7) = (1, 2/3, 1, 0, 1, 1, 1)
Total weight = 2 + 2 + 5 + 0 + 1 + 4 + 1 = 15
Total profit = 10 + 3.33 + 15 + 0 + 6 + 18 + 3 = 55.33

Running time: sorting by p_i / w_i takes O(n log n) and the selection loop takes O(n), so the whole method is O(n log n). Objects 3 and 7 tie at a ratio of 3, and taking either first gives the same profit of 55.33.

Sample 5: Divide and Conquer Approach and Merge Sort

Question: (a) Define the divide and conquer approach of problem solving and write its general recurrence. (4)
(b) Explain the merge sort algorithm and show that its running time is Θ(n log n). (6)

(a) Divide and conquer. This method breaks a problem into smaller sub-problems of the same type, solves them recursively and joins their answers. It has three steps at every level: divide, conquer and combine.

T(n) = Θ(1)                          if n <= c
T(n) = a T(n/b) + D(n) + C(n)        otherwise

a      = number of sub-problems
n/b    = size of each sub-problem
D(n)   = time to divide
C(n)   = time to combine

(b) Merge sort. Merge sort splits the array into two halves, sorts each half recursively and then merges the two sorted halves into one.

MERGE-SORT(A, p, r)
1. if (p < r)
2.     q = floor((p + r) / 2)      // divide
3.     MERGE-SORT(A, p, q)         // conquer left half
4.     MERGE-SORT(A, q+1, r)       // conquer right half
5.     MERGE(A, p, q, r)           // combine
Initial call: MERGE-SORT(A, 1, n)

• Divide cost: finding the middle index q takes constant time, so D(n) = Θ(1).
• Conquer cost: two halves of size n/2 are sorted recursively, giving 2T(n/2).
• Combine cost: MERGE compares the front elements of the two halves and copies the smaller one each time, so C(n) = Θ(n).

T(n) = 2T(n/2) + cn

Recursion tree : every level costs cn
Number of levels = log_2 n + 1
T(n) = cn (log_2 n + 1) = cn log_2 n + cn
T(n) = Θ(n log n)

Check with Master Theorem: a = 2, b = 2, n^(log_2 2) = n = f(n), Case 2

Example: 80, 45, 15, 95, 55, 98, 60, 20, 70 is split until each part holds one element and is merged back as 15, 20, 45, 55, 60, 70, 80, 95, 98. Merge sort takes Θ(n log n) in the best, worst and average case, though it needs O(n) extra space for merging.