IGNOU BCS-042 Solved Question Paper PDF Download

IGNOU BCS-042 Previous Year Solved Question Paper in Hindi

IGNOU BCS-042 Previous Year Solved Question Paper in English

Q1. (a) Explain the concept of the space complexity in context of algorithm analysis. How is it different from time complexity ? Provide an example to illustrate the calculation of space complexity. (5) (b) Given a list of distinct integers, write an algorithm to determine the position of an integer in the list using linear search and count the number of comparison operations required. (5) (c) Describe any three of the following : (3×2=6) () Greedy technique (ii) Cycle in a Directed Graph (iii) Upper Bound (iv) Branch and Bound (d) Use Master Theorem to give tight asymptotic bounds of the following : (2×2=4) (i) T(n)= 4T(n/2) + n^2 (ii) T(n) = 2T(n/3) + n√n

Ans.

(a) Space Complexity

In algorithm analysis, space complexity refers to the total amount of memory space used by an algorithm as a function of the size of the input. It measures how much memory or storage an algorithm needs to complete its execution.

It consists of two types of space:

• Fixed Space (Auxiliary Space): This is the extra or temporary space used by the algorithm, which includes memory used for variables, pointers, etc. It does not depend on the size of the input.
• Variable Space: This space varies with the size of the input. It includes dynamic memory allocation, recursion stack space, etc.

Difference from Time Complexity:

The key difference is that time complexity measures the time it takes for an algorithm to run (in terms of the number of operations), whereas space complexity measures the memory space required to run that algorithm. An algorithm may be efficient in time but inefficient in space, or vice-versa. Ideally, an algorithm is efficient in both.

Example: Consider a function to sum the elements of an array.

function sum(arr, n) { let total = 0; // 1 unit of space for (let i = 0; i < n; i++) { // 1 unit for 'i' total += arr[i]; } return total;}

Here, the input array `arr` requires `n` space. Inside the function, variables like `total` and `i` require constant space. Therefore, the space complexity S(n) = (Input Space) + (Auxiliary Space) = O(n) + O(1) = O(n). If we only consider the auxiliary space, it is O(1).

(b) Linear Search Algorithm and Comparison Count

Algorithm: LinearSearch(List A, value x)

1. Set `n` as the number of elements in list A.
2. Initialize `comparisons` to 0.
3. Loop for `i` = 0 to `n-1`.
   1. Increment `comparisons` by 1.
   2. If `A[i]` is equal to `x`, then:
      1. Return `i` (the position) and the number of `comparisons`.
4. If the loop finishes and `x` is not found, return -1 (or ‘not found’) and the number of `comparisons`.

Counting Comparison Operations:

In linear search, every element is compared with the target value.

• Best Case: If the desired element is at the very first position in the list, only 1 comparison will be required.
• Average Case: On average, if the element is present in the list, about n/2 comparisons will be required.
• Worst Case: If the element is at the end of the list or not present in the list at all, it will be compared with all `n` elements. Thus, n comparisons will be required.

For example, to find 30 in the list {10, 50, 30, 70}, the algorithm will compare 10, 50, and then 30. It will be found at position 2 after 3 comparisons .

(c) Description of any three

(i) Greedy Technique

The greedy technique is an algorithmic paradigm that solves problems by making locally optimal choices at each stage with the hope that these local optimal choices will lead to a globally optimal solution. A greedy algorithm does not consider all possible solutions for a problem; instead, it makes one choice at a time that looks best at the moment. It does not always guarantee a globally optimal solution, but for some problems, such as Kruskal’s and Prim’s algorithms (Minimum Spanning Tree) and Dijkstra’s algorithm (single source shortest path), it does.

(ii) Cycle in a Directed Graph

A cycle in a directed graph (digraph) is a path that starts and ends at the same vertex. Formally, it is a non-empty sequence of vertices v ₀ , v ₁ , …, v _k-1 , v _k where v ₀ = v _k and there is a directed edge from v _i to v _i+1 for each i from 0 to k-1. Detecting cycles is crucial in many applications, such as topological sorting in a graph (not possible in a cyclic graph), and detecting deadlocks in operating systems. A common method to detect a cycle is by using Depth-First Search (DFS). During a DFS, if we visit a vertex that is already present in the current recursion stack, a cycle is detected.

(iv) Branch and Bound

Branch and Bound is an algorithm design paradigm generally used for combinatorial optimization problems. It is a state space search technique. The method involves two main processes:

1. Branching: Dividing the problem into smaller sub-problems. This creates a state-space tree.
2. Bounding: For each sub-problem (a node in the tree), we calculate a bound (upper or lower) on the best possible solution that can be obtained within that sub-problem. If this bound is worse than the best solution found so far, then the entire sub-tree does not need to be explored further, and we can “prune” that branch.

It systematically searches for a solution and significantly reduces the search space through pruning. It is used to solve problems like the Traveling Salesman Problem (TSP).

(d) Using the Master Theorem

The Master Theorem is used to provide asymptotic bounds for recurrence relations of the form T(n) = aT(n/b) + f(n). We compare n ^{log _b a} with f(n).

(i) T(n) = 4T(n/2) + n ²

• Here, a = 4, b = 2, and f(n) = n ² .
• Calculate n ^{log _b a} = n ^{log ₂ 4} = n ² .
• Since f(n) = n ² = Θ(n ^{log _b a} ), we apply Case 2 of the Master Theorem.
• Therefore, T(n) = Θ(n ^{log _b a} log n) = Θ(n ² log n) .

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

• Here, a = 2, b = 3, and f(n) = n√n = n ^1.5 .
• Calculate n ^{log _b a} = n ^{log ₃ 2} ≈ n ^0.63 .
• Since f(n) = n ^1.5 , f(n) = Ω(n ^{log ₃ 2 + ε} ) for some ε > 0 (e.g., ε = 0.87). This points to Case 3 .
• We must check the regularity condition: a f(n/b) ≤ c f(n) for some c < 1. 2 f(n/3) = 2 (n/3) ^1.5 = 2 n ^1.5 / 3 ^1.5 = (2 / 3√3) n ^1.5 . Since c = 2 / (3√3) ≈ 0.385, which is less than 1, the condition holds.
• Therefore, T(n) = Θ(f(n)) = Θ(n√n) .

Q2. (a) State Euclid’s algorithm and find GCD (595, 252) by this algorithm. (5) (b) Write the iterations for sorting the following list of numbers using bubble sort and selection sort : 5 45, 67, 3, 90, 2, 35, 28, 0

Ans.

(a) Euclid’s Algorithm and GCD(595, 252)

Euclid’s Algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers, the largest number that divides them both without leaving a remainder.

The Algorithm:

Given two non-negative integers `a` and `b`, where `a >= b`:

1. If `b` is 0, then the GCD is `a`.
2. Otherwise, the GCD of `a` and `b` is the same as the GCD of `b` and `a mod b` (the remainder when `a` is divided by `b`).

The recursive formula is: GCD(a, b) = GCD(b, a % b) .

Calculation of GCD(595, 252):

We apply the algorithm step-by-step:

• Step 1: GCD(595, 252) 595 = 2 * 252 + 91. The remainder is 91. So, we find GCD(252, 91).
• Step 2: GCD(252, 91) 252 = 2 * 91 + 70. The remainder is 70. So, we find GCD(91, 70).
• Step 3: GCD(91, 70) 91 = 1 * 70 + 21. The remainder is 21. So, we find GCD(70, 21).
• Step 4: GCD(70, 21) 70 = 3 * 21 + 7. The remainder is 7. So, we find GCD(21, 7).
• Step 5: GCD(21, 7) 21 = 3 * 7 + 0. The remainder is 0. So, we find GCD(7, 0).
• Step 6: According to the algorithm, when the second number is 0, the GCD is the first number.

Therefore, the GCD(595, 252) is 7 .

(b) Sorting Iterations

Original List: [45, 67, 3, 90, 2, 35, 28, 0]

Bubble Sort Iterations:

In each pass, the largest unsorted element “bubbles” to its correct position at the end of the unsorted part.

• Pass 1: [45, 3, 67, 2, 90, 28, 35, 0] -> [45, 3, 2, 67, 28, 35, 0, 90 ] After many swaps, 90 is at the end. (Simplified view: compare adjacent, swap if needed) Correct Pass 1 Trace: [ 45, 67 , 3, 90, 2, 35, 28, 0] -> No swap [45, 67, 3 , 90, 2, 35, 28, 0] -> [45, 3, 67 , 90, 2, 35, 28, 0] …and so on. The final list after pass 1: [45, 3, 67, 2, 35, 28, 0, 90 ]
• Pass 2: [3, 45, 2, 67, 28, 0, 35 , 90] (67 moves to its position) [3, 2, 45, 28, 0, 35, 67 , 90]
• Pass 3: [2, 3, 28, 0, 35, 45 , 67, 90]
• Pass 4: [2, 3, 0, 28, 35 , 45, 67, 90]
• Pass 5: [2, 0, 3, 28 , 35, 45, 67, 90]
• Pass 6: [0, 2, 3 , 28, 35, 45, 67, 90]
• Pass 7: [0, 2 , 3, 28, 35, 45, 67, 90] (List is now sorted, but algorithm may do one more pass)

Final Sorted List: [0, 2, 3, 28, 35, 45, 67, 90]

Selection Sort Iterations:

In each pass, find the minimum element in the unsorted part and swap it with the first element of the unsorted part.

• Pass 1: Find min (0). Swap with 45. [ 0 , 67, 3, 90, 2, 35, 28, 45]
• Pass 2: Unsorted: [67, 3, 90, 2, 35, 28, 45]. Find min (2). Swap with 67. [0, 2 , 3, 90, 67, 35, 28, 45]
• Pass 3: Unsorted: [3, 90, 67, 35, 28, 45]. Min is 3 (already in place). No swap. [0, 2, 3 , 90, 67, 35, 28, 45]
• Pass 4: Unsorted: [90, 67, 35, 28, 45]. Find min (28). Swap with 90. [0, 2, 3, 28 , 67, 35, 90, 45]
• Pass 5: Unsorted: [67, 35, 90, 45]. Find min (35). Swap with 67. [0, 2, 3, 28, 35 , 67, 90, 45]
• Pass 6: Unsorted: [67, 90, 45]. Find min (45). Swap with 67. [0, 2, 3, 28, 35, 45 , 90, 67]
• Pass 7: Unsorted: [90, 67]. Find min (67). Swap with 90. [0, 2, 3, 28, 35, 45, 67 , 90]

Final Sorted List: [0, 2, 3, 28, 35, 45, 67, 90]

Q3. (a) Differentiate between Kruskal’s algorithm and Prim’s algorithm. (4) (b) Apply Dijkstra’s algorithm to find shortest path from source vertex A to each of the other vertices of the following directed graph : (6)

Ans.

(a) Difference between Kruskal’s and Prim’s Algorithm

Both Kruskal’s and Prim’s algorithms are greedy algorithms used to find the Minimum Spanning Tree (MST) of a connected, undirected, and weighted graph. However, they approach the problem differently.

Feature	Kruskal’s Algorithm	Prim’s Algorithm
Core Idea	It is an edge-based algorithm. It selects the edge with the minimum weight from the entire graph, as long as it does not form a cycle.	It is a vertex-based algorithm. It starts from an arbitrary vertex and grows the MST by adding the cheapest edge connecting a vertex in the MST to a vertex outside the MST.
Intermediate State	The intermediate graph is a forest (a collection of disjoint trees). At the end, the forest becomes a single tree (the MST).	The intermediate graph is always a single connected tree.
Cycle Detection	Requires a mechanism (like the Union-Find data structure) to check if adding an edge will form a cycle.	Does not need explicit cycle detection, as it only adds edges connecting a visited vertex to an unvisited one, which can never form a cycle.
Data Structure	Typically uses a Disjoint Set Union (DSU) data structure for efficient cycle detection.	Typically uses a Priority Queue (like a min-heap) to efficiently select the minimum weight edge to an unvisited vertex.
Complexity	O(E log E) or O(E log V), depending on sorting edges and DSU operations. Works well on sparse graphs (where E is close to V).	O(E log V) with a binary heap, or O(E + V log V) with a Fibonacci heap. Works well on dense graphs (where E is close to V 2 ).

(b) Dijkstra’s Algorithm Application

The goal is to find the shortest path from the source vertex A to all other vertices. We will maintain a set of visited vertices and a distance array `dist` which stores the shortest distance found so far from A.

The graph has vertices {A, B, C, D, E} and the following edges:

• A → B (3)
• A → D (5)
• B → C (10)
• B → D (2)
• C → E (4)
• D → C (1)
• D → E (7)

Let `dist` be an array for distances and `prev` for path reconstruction. Initialize: `dist = {A:0, B:∞, C:∞, D:∞, E:∞}`, `visited = {}`

Step 1: Visit A (Current Vertex)

• `visited = {A}`
• Update neighbors of A:
  • dist(B) = min(∞, dist(A) + 3) = 3. prev(B) = A.
  • dist(D) = min(∞, dist(A) + 5) = 5. prev(D) = A.
• `dist` becomes: {A:0, B:3, C:∞, D:5, E:∞}

Step 2: Visit B (Next smallest distance is 3)

• `visited = {A, B}`
• Update neighbors of B:
  • dist(C) = min(∞, dist(B) + 10) = 13. prev(C) = B.
  • dist(D) = min(5, dist(B) + 2) = min(5, 5) = 5. No change.
• `dist` becomes: {A:0, B:3, C:13, D:5, E:∞}

Step 3: Visit D (Next smallest distance is 5)

• `visited = {A, B, D}`
• Update neighbors of D:
  • dist(C) = min(13, dist(D) + 1) = min(13, 6) = 6. prev(C) = D.
  • dist(E) = min(∞, dist(D) + 7) = min(∞, 12) = 12. prev(E) = D.
• `dist` becomes: {A:0, B:3, C:6, D:5, E:12}

Step 4: Visit C (Next smallest distance is 6)

• `visited = {A, B, D, C}`
• Update neighbors of C:
  • dist(E) = min(12, dist(C) + 4) = min(12, 10) = 10. prev(E) = C.
• `dist` becomes: {A:0, B:3, C:6, D:5, E:10}

Step 5: Visit E (Last remaining vertex, distance 10)

• `visited = {A, B, D, C, E}`
• E has no outgoing edges. No updates.

Final Shortest Paths from A:

• To B: Path A → B. Cost = 3
• To C: Path A → D → C. Cost = 5 + 1 = 6
• To D: Path A → D. Cost = 5
• To E: Path A → D → C → E. Cost = 5 + 1 + 4 = 10

Q4. (a) Consider the following sorted array A with 8 elements : 7, 5, 9, 27, 30, 48, 56, 59, 75, 87, 94 20, 7 Illustrate the working of Binary search algorithm while searching for ITEM: (5) (i) 9 (ii) 94 (b) Show that the runtime of QUICK SORT algorithm in the best case is O(n log n). (5)

Ans.

(a) Binary Search Illustration

Note: The question provides a garbled, unsorted list of numbers but states it is a sorted array. For binary search to work, the array must be sorted. We will assume the intended array is a sorted collection of these numbers:

Let the sorted array A be: [5, 7, 9, 20, 27, 30, 48, 56, 59, 75, 87, 94] . The indices range from 0 to 11 (n=12).

The binary search algorithm works by repeatedly dividing the search interval in half. We use three pointers: `low`, `high`, and `mid`.

(i) Searching for ITEM = 9

• Iteration 1:
  • `low = 0`, `high = 11`
  • `mid = floor((0 + 11) / 2) = 5`
  • Compare ITEM with `A[mid]`: `A[5]` is 30.
  • Since `9 < 30`, the item must be in the left half. Update `high`.
  • `high = mid – 1 = 4`
• Iteration 2:
  • `low = 0`, `high = 4`
  • `mid = floor((0 + 4) / 2) = 2`
  • Compare ITEM with `A[mid]`: `A[2]` is 9.
  • Since `9 == 9`, the item is found at index 2.

The element 9 is found at index 2 .

(ii) Searching for ITEM = 94

• Iteration 1:
  • `low = 0`, `high = 11`
  • `mid = floor((0 + 11) / 2) = 5`
  • Compare ITEM with `A[mid]`: `A[5]` is 30.
  • Since `94 > 30`, the item must be in the right half. Update `low`.
  • `low = mid + 1 = 6`
• Iteration 2:
  • `low = 6`, `high = 11`
  • `mid = floor((6 + 11) / 2) = 8`
  • Compare ITEM with `A[mid]`: `A[8]` is 59.
  • Since `94 > 59`, the item must be in the right half. Update `low`.
  • `low = mid + 1 = 9`
• Iteration 3:
  • `low = 9`, `high = 11`
  • `mid = floor((9 + 11) / 2) = 10`
  • Compare ITEM with `A[mid]`: `A[10]` is 87.
  • Since `94 > 87`, the item must be in the right half. Update `low`.
  • `low = mid + 1 = 11`
• Iteration 4:
  • `low = 11`, `high = 11`
  • `mid = floor((11 + 11) / 2) = 11`
  • Compare ITEM with `A[mid]`: `A[11]` is 94.
  • Since `94 == 94`, the item is found at index 11.

The element 94 is found at index 11 .

(b) Quick Sort Best Case Runtime Analysis

The runtime of Quick Sort is highly dependent on the choice of the pivot element and the resulting partitions.

The Best Case Scenario:

The best case for Quick Sort occurs when the `partition` process always splits the array into two sub-arrays of almost equal size. This happens when the pivot element chosen is the median of the array. In this ideal scenario, an array of size `n` is divided into two sub-arrays of size approximately `n/2`.

Recurrence Relation:

Let T(n) be the time taken to sort an array of size `n`.

1. Divide: The `partition` step takes linear time to rearrange the elements around the pivot. This is O(n) .
2. Conquer: The algorithm recursively sorts the two sub-arrays. In the best case, the sizes are `n/2` and `n/2`. The time taken is 2T(n/2) .
3. Combine: No work is needed to combine the sub-arrays, as the sorting is done in-place. This is O(1) .

This leads to the recurrence relation for the best case: T(n) = 2T(n/2) + O(n)

Solving the Recurrence:

We can solve this recurrence using the Master Theorem or by drawing a recurrence tree.

Using the Master Theorem (T(n) = aT(n/b) + f(n)):

• a = 2, b = 2, f(n) = n
• We compare f(n) with n ^{log _b a} = n ^{log ₂ 2} = n ¹ .
• Since f(n) = O(n) and n ^{log _b a} = O(n), we are in Case 2 of the Master Theorem.
• Therefore, T(n) = Θ(n ^{log _b a} log n) = Θ(n log n) .

Using the Recurrence Tree method:

• The root of the tree has a cost of `cn`.
• The next level has 2 subproblems of size `n/2`, with a total cost of 2 * c(n/2) = `cn`.
• The next level has 4 subproblems of size `n/4`, with a total cost of 4 * c(n/4) = `cn`.
• This continues until the subproblem size is 1. The height of the tree is log ₂ n .
• At each of the `log n` levels, the total work done is `cn`.
• Total work = (work per level) (number of levels) = `cn log n`.

Thus, the best-case time complexity of Quick Sort is O(n log n) .

Q5. (a) Multiply 026782 x 0732920 using divide and conquer technique using Karatsuba method. (5) (b) Write an algorithm for Depth First Search (DFS) and traverse the following graph using DFS. Starting vertex is A: (5)

Ans.

(a) Karatsuba Multiplication

Note: The numbers in the question, `026782` and `0732920`, have subscripts `2` which are likely typos, and the second number contains a `9` which makes it invalid in base 8 (octal). We will assume the question intended to multiply two decimal integers of equal length. Let’s use `2678` and `7329` as a 4-digit example, which is standard for demonstrating this method.

We want to compute 2678 × 7329 .

Let X = 2678 and Y = 7329. Here n = 4.

1. Split the numbers into two halves (n/2 = 2):

• X = 26 × 10 ² + 78. So, a = 26, b = 78 .
• Y = 73 × 10 ² + 29. So, c = 73, d = 29 .

2. Perform three recursive multiplications:

• p1 = a × c = 26 × 73 = 1898
• p2 = b × d = 78 × 29 = 2262
• p3 = (a + b) × (c + d) = (26 + 78) × (73 + 29) = 104 × 102 = 10608

3. Calculate the middle term (ad + bc):

• ad + bc = p3 – p1 – p2
• ad + bc = 10608 – 1898 – 2262 = 6448

4. Combine the results: The final product is given by the formula: p1 × 10 ⁿ + (ad + bc) × 10 ^n/2 + p2

• = 1898 × 10 ⁴ + 6448 × 10 ² + 2262
• = 18980000 + 644800 + 2262
• = 19624800 + 2262
• = 19627062

Checking with direct multiplication: 2678 × 7329 = 19627062. The result is correct.

(b) Depth First Search (DFS) Algorithm and Traversal

DFS Algorithm (Recursive):

We need a `visited` array or set to keep track of visited vertices to avoid cycles and redundant processing.

DFS(graph, vertex u, visited): 1. Mark u as visited. 2. Print or process vertex u. 3. For each neighbor v of u in graph: 4. If v has not been visited: 5. DFS(graph, v, visited)

Initial Call: To start the traversal from a source vertex `s`: 1. Create a `visited` array/set, initialized to false/empty for all vertices. 2. Call `DFS(graph, s, visited)`.

Traversal of the Given Graph:

The graph has vertices {A, B, C, D} and edges connecting them. Assuming the graph is undirected based on the drawing:

• A is connected to B, C
• B is connected to A, D
• C is connected to A, D
• D is connected to B, C

We will traverse starting from vertex A . We will assume alphabetical order when choosing the next neighbor to visit.

Steps:

1. Start at A. Call `DFS(A)`.
   • Mark A as visited. Print A.
   • Visited: {A}. Traversal Order: A
2. Explore neighbors of A. Let’s pick B first.
   • Call `DFS(B)`. Mark B as visited. Print B.
   • Visited: {A, B}. Traversal Order: A, B
3. Explore neighbors of B. A is already visited. Pick D .
   • Call `DFS(D)`. Mark D as visited. Print D.
   • Visited: {A, B, D}. Traversal Order: A, B, D
4. Explore neighbors of D. B is visited. Pick C .
   • Call `DFS(C)`. Mark C as visited. Print C.
   • Visited: {A, B, D, C}. Traversal Order: A, B, D, C
5. Explore neighbors of C. Both A and D are visited. `DFS(C)` returns.
6. Back to `DFS(D)`. All neighbors of D (B, C) have been visited. `DFS(D)` returns.
7. Back to `DFS(B)`. All neighbors of B (A, D) have been visited. `DFS(B)` returns.
8. Back to `DFS(A)`. Next neighbor of A is C , but C is already visited.
9. All neighbors of A have been processed. `DFS(A)` finishes.

The Depth First Search traversal starting from vertex A is: A → B → D → C .